ИССЛЕДОВАНИЕ И СИНТЕЗ ЭЛЕМЕНТОВ СИСТЕМЫ ФИЗИЧЕСКОЙ ЗАЩИТЫ ОБЪЕКТА НА ОСНОВЕ ЗАДАЧИ О ПОКРЫТИИ НА ГРАФЕ

Аннотация: Объектом исследования является система физической защиты объекта информатизации. Предметом исследования является информационная поддержка решения задачи проектирования систем физической защиты объектов информатизации. Особое внимание уделено исследованию и синтезу элементов системы физической защиты на основе разработки алгоритмов решения задачи о покрытии на основе рангового подхода. Методы исследования включают методы рангового подхода к решению задачи о покрытии, многокритериальный анализ вариантов и теорию графов.

Ключевые слова: граф, покрытие, ранговый подход, оптимизация, синтез.

Введение. На протяжении последних лет в Российской Федерации (РФ) наблюдается стабильно высокий уровень преступлений, касающихся нарушения сохранности и безопасности различного рода объектов и имеющихся на них материальных и информационных ресурсов [3-5].

Обострение указанной проблемы демонстрируется широким распространением таких явлений, как возрастающий терроризм, несанкционированный доступ к ценным ресурсам и их хищение, а в некоторых случаях вредительство (вандализм). При этом, по данным экспертов, действия злоумышленников стали носить все более ухищренный, системно продуманный с точки зрения профессионализма характер, в то время как государственный аппарат по пресечению такого рода преступлений не был готов и лишь недавно начал развиваться [5].

Для противодействия факторам, воздействующим на безопасность объекта защиты, используются различные средства защиты информации [1].

Различные средства в совокупности представляют собой системы защиты для поддержки информационной безопасности объекта. Например: системы контроля управления доступом, системы обнаружения и предотвращения сетевых вторжений, системы предотвращения утечек конфиденциальной информации, антивирусные средства, межсетевые экраны, криптографические средства, системы резервного копирования, системы бесперебойного питания и т. п. [2].

Создание системы информационной безопасности, включающей в себя все виды средств (технические, программные и программно-технические), является чрезвычайно сложной проблемой. В частности, требуется рассматривать сильно различающиеся по принципам воздействия на объект защиты (ОЗ) факторы, и соответственно анализировать множество способов защиты от всех видов факторов. Поэтому целесообразно разделить задачу создания системы защиты на несколько подзадач, например, по видам средств защиты, и в дальнейшем объединять результаты решения в единую систему, защищающую ОЗ от всех видов угроз информационной безопасности.

Определим подробнее понятие физических средств защиты. К физическим средствам относят механические, электромеханические, оптические, акустические, лазерные, радиоволновые и другие устройства, системы и сооружения, предназначенные для создания препятствий на пути к защищаемой информации и способные выполнять функции физической защиты. Система физической защиты (СФЗ) по определению это объединение сил охраны и технического оснащения - комплекса инженерно-технических средств охраны. Состав СФЗ в виде структурной схемы отображен на рисунке 1 [2].

Рисунок 1. Обобщенная структурная схема системы физической защиты

Технические средства СФЗ сертифицированы в соответствии с законодательством Российской Федерации. Технические и программные средства системы физической защиты, используемые при обработке информации в ИС, составляющей государственную и служебную тайну, подлежат в установленном порядке обязательной сертификации [4, 5].

Для анализа угроз и оценки эффективности ИК СФЗ применяется так называемая модель нарушителя - абстрактное (формализованное или неформализованное) описание нарушителя. При организации системы физической защиты объекта используется классический принцип последовательных рубежей, при нарушении которых угрозы своевременно обнаружены и их распространению будут препятствовать надежные преграды. Оптимальное расположение зон безопасности и размещение в них технических средств защиты (обнаружения и противодействия) составляют основу физической защиты любого объекта. Автоматизация процесса синтеза оптимального варианта размещения технических средств защиты на объекте позволит значительно повысить эффективность СФЗ.

Если провести синтез технологических процессов проектирования, представленных в различных руководящих документах, то получим следующий агрегированный технологический процесс проектирования СФЗ, который представлен на рис, 2.

Рисунок 2. Технологический процесс проектирования СФЗ

Результаты анализа показывают [2-7], что одной из актуальных задач является синтез элементов системы физической защиты объекта на основе задачи о покрытии на графе

Анализ источников. Проводимые исследования, посвященные проблемам проектирования и оценки систем физической защиты, выполнялись научными школами под руководством М. Гарсия, Джеймс Ф. Бродера, А.В. Бояринцева, А.Н. Бражника, А.Г. Зуева, В.В. Волхонского, В.С. Зарубина и др. Описываются методы определения требований к СФЗ, способы оценки эффективности существующих и разрабатываемых систем. При этом среди исследований нет метода решения задачи проектирования СФЗ, позволяющего использовать средства информационной поддержки на этапе создания проекта СФЗ, определяющего размещение средств защиты на территории объекта.

Основной материал

Математическая постановка задачи. После определения величины затрат (Сопт) на обеспечение защиты объекта необходимо сформировать систему элементов объекта на которых будет строиться СФЗ, удовлетворяющая заданным ограничениям.

Количество функций определяет количество возможных вариантов проникновения угрозы на объект. Причем каждая угроза может предотвращена путем прерывания маршрута хотя бы в одной дуге. Необходимо исключить все сто маршрутов (функций) проникновения. Это задача о нахождении минимального сечения на графе, которая решается путем определения минимального покрытия на матрице инцидентности.

Целью решения задачи о покрытии является: минимальным количеством дуг покрыть (перекрыть) все возможные маршруты проникновения на объект. Результат покрытия - это минимальный набор дуг (препятствий) для исключения проникновения на объект, т.е. реализации угрозы.

Дуга в графе может ассоциироваться с каким-то типом варианта защиты объекта, который будет характеризоваться вероятностью защиты и стоимостью. Так как задача о покрытии решается на максимум эффективности, то в качестве показателя выберем количество перекрываемых маршрутов с минимальной избыточностью. Тогда результатом будет множество покрытий, каждое из которых перекрывает все маршруты проникновения. Математическая постановка задачи: необходимо минимизировать целевую функцию

при ограничениях

где

Ограничение (2) означает, что каждый маршрут проникновения должен покрываться (прерываться). Исходные данные задаются с помощью матрицы инцидентности .

где   -  количество маршрутов, которые должны быть перекрыты;

- количество действующих элементов (дуг), которые могут перекрывать (покрывать) определенные маршруты;

Для решения задачи о покрытии предлагается использовать ранговый подход. 

Разработка приближенного и точного алгоритмов решения задачи о покрытии на основе рангового подхода

Пусть А^т – транспонированная матрица смежности графа G с единичными диагональными элементами. Задача определения наименьшего доминирующего множества графа G эквивалентна задаче нахождения такого наименьшего     множества столбцов в матрице А^т, что каждая строка матрицы содержит единицу хотя бы в одном из выбранных столбцов. Эта задача о поиске наименьшего множества столбцов, «покрывающих» единицами все строки, получила названия задачи о минимальном покрытии (ЗНП). В общем случае матрица, состоящая из 0 и 1, не обязательно является квадратной. Кроме того, каждому столбцу j (вершине x_j) в матрице А^т сопоставляется некоторый вес, и требуется найти покрытие с наименьшей общей стоимостью. В случае же равенства коэффициентов задача трансформируется в задачу минимизации числа столбцов, покрывающих все строки в матрице А^т.

Рассмотрение алгоритмов решения ЗНП начнем с приближенного алгоритма решения задачи (1 – 3) для случая равенства коэффициентов c_i с использованием правил объединения L₁ и L₂. Наиболее простым и естественным правилом отсечения путей L₁ во множествах  является удаление путей , у которых d_i^п = ¥, поскольку эти пути не удовлетворяют свойству n. Тогда ЗНП можно рассматривать как задачу определения кратчайших путей на основе рангового подхода [8-9] в графе D_D, с учетом принципа оптимизации по направлению. Пошаговое описание алгоритма определения кратчайших путей в графе D_D, удовлетворяющих свойству n, имеет вид:

Приближенный алгоритм решения невзвешенной ЗНП (процедура А_к)

Шаг 1. Формируем калибровочные вектора H⁽ⁱ⁾, выделяем множества путей {m_si^r=1}, удовлетворяющие свойствуn. Если все эти множества пусты, то алгоритм заканчивает работу, т.к. это означает, что покрытия не существует. Если же есть хотя бы одно непустое множество, то определяем в каждом из них пути m^*_si^r=1, минимальные по весу d_i^п и делаем переход к шагу 3.

Шаг 2. На основе пути множества путей {m^*_si^r} текущего ранга формируем множества путей m_si^r+1 следующего ранга, удовлетворяющих свойству n, Выделяем в них пути m^*_si^r+1 с наименьшим значением d_i^п (правило L₂) и переходим к выполнению следующего шага.

Шаг 3. Если есть d_i^п = 0, то алгоритм заканчивает работу, иначе – выполняем шаг 4.

Шаг 4. Если есть d_i^п = 1, то формируем путь следующего ранга с d_i^п = 0 и алгоритм заканчивает работу, иначе – значение r увеличиваем на 1 и переходим к шагу 2. Приведенный алгоритм отображает основное функциональное уравнение динамического программирования, которое для данной задачи можно представить в следующем виде

где  – условное минимальное расстояние от вершины s до вершины j в D_D, найденное на (k-1)-м  шаге работы процедуры;

 – величины весов вершин, образующих пути к вершинам i=(1, n) на k-м шаге.

Уравнение (5) позволяет по цепочке находить условные оптимальные решения. Таким образом, определение калибровочных векторов H⁽ⁱ⁾ эквивалентно маркировке путей в графе D_D от конца к началу, а использование затем процедуры А_к есть ни что иное, как идентификация кратчайшего пути по сделанной маркировке на основе функционального уравнения динамического программирования (5), когда процесс программирования разворачивается от начала к концу. В случае взвешенных столбцов в матрице В пошаговое описание приближенного алгоритма А^в_k решения задачи (1 – 3) с использованием правила отсечения L₂ остается тем же, но при этом поиск кратчайших путей идет по весовой характеристике d_i^пв, определяемой соотношениями (5).

Приближенный алгоритм решения взвешенной ЗНП (процедура А^в_к)

Шаг 1. Формируем калибровочные вектора H⁽ⁱ⁾, выделяем множества путей {m_si^r=1}, удовлетворяющие свойству n. Если все эти множества пусты, то алгоритм заканчивает работу, т.к. это означает, что покрытия не существует. Если же есть хотя бы одно непустое множество, то определяем в каждом из них пути m^*_si^r=1, минимальные по весу d_i^пв и переходим к шагу 2.

Шаг 2. Если есть пути с d_i^пв = 0, то выделяем среди них путь, минимальный по весу, определяющий локальный экстремум на ранге, и переходим к следующему шагу.

Шаг 3. На основе пути множества путей {m^*_si^r} текущего ранга r формируем множества путей m_si^r+1 следующего ранга в соответствии с правилом L₂ и переходим к выполнению следующего шага.

Шаг 4. Если все множества следующего ранга пусты, то выделяем из множества локальных экстремумов глобальный и алгоритм заканчивает работу. Если же есть хотя бы одно непустое множество, то увеличиваем значение текущего ранга r:=r+1 и переходим к шагу 2.

Точное решение задачи (1-3) в случае равенства коэффициентов c_i возможно только с использованием правил L₁ и p. При этом пошаговое описание алгоритма, реализуемого на основе процедуры A₀, имеет вид:

Точный алгоритм решения невзвешенной ЗНП (процедура А)

Шаг 1. Формируем калибровочные вектора H⁽ⁱ⁾, выделяем множества путей {m_si^r=1}, удовлетворяющие свойству n. Если все эти множества пусты, то алгоритм заканчивает работу, т.к. это означает, что покрытия не существует. Если же есть хотя бы одно непустое множество, то для всех вершин графа D_D вычисляем вспомогательные вектора z_i, определяем для каждого пути характеристики d_i^п и d_i^o в соответствии с соотношениями (6 – 9) и переходим к выполнению следующего шага.

Назовем наименьшее число вершин d_i^о, подсоединение которых к пути  удовлетворяет неравенству

оптимистическим негарантированным прогнозом, определяющим минимальное число вершин d_i^о, которое необходимое присоединить к пути  для того, чтобы получить путь , соответствующий покрытию в матрице В. Вершины i отсортированы в графе D_D   в порядке возрастания g_i и, следовательно, в порядке убывания a_i. Введем для каждой вершины i вспомогательный вектор z_i(z_i+1, z_i+2, ... , z_i+k), где i + k £ n, а компоненты вектора определяются следующими рекуррентными соотношениями

Вспомогательный вектор z_i для вершины i графа D_D позволяет определить оптимистический негарантированный прогноз для произвольного пути , характеризуемого вектором H⁽ⁱ⁾. Для этого определяется величина a_i^H = m – p_i, и тогда

где j – значение, начиная с которого выполняется неравенство

Если величина пессимистической оценки пути  d_i^п  = ¥, то  и d_i^о  =  ¥.

Шаг 2. На основе пути множества путей {m^*_si^r} текущего ранга r формируем множества путей m_si^r+1 следующего ранга r+1 на основе рекуррентного соотношения (10)

определяем характеристики этих путей d_i^п и d_i^o в соответствии с (6 – 9) и выделяем коридор во множестве  по правилу p, определяемому соотношением (11):

Шаг 3. Если есть d_i^п = 0, то алгоритм заканчивает работу, т.к. именно этот путь образует минимальное покрытие, иначе - выполняем шаг 4.

Шаг 4. Если есть d_i^п = 1, то формируем путь следующего ранга с d_i^п = 0 и алгоритм заканчивает работу, иначе – значение r увеличиваем на 1 и переходим к шагу 2.

Вывод. Таким образом, представление n-мерного единичного куба в виде графа D_D в сочетании с разработанными правилами отсечения {L_w} и принципом оптимизации по направлению в n-мерном единичном кубе позволило разработать точные  алгоритмы решения задач дискретного программирования, в общем случае имеющие экспоненциальную сложность, но работающие   в среднем с полиномиальной сложностью при решении задач, содержащих до нескольких сотен переменных.

Показана возможность применения метода решения оптимизационных задач с БП на основе рангового подхода к решению ЗНП. Поскольку ЗНП полиномиально сводится к задачам: «наименьшее доминирующее множество вершин в графе»; «независимое наибольшее множество вершин в графе»; «наибольшая клика в графе»; «наибольшее паросочетание в графе», то рассмотренные приближенные и точные алгоритмы решения ЗНП могут быть использованы и для решения перечисленных задач, имеющих широкое прикладное значение в теории сложных систем.

Список литературы:

1. Боровский, А.С. Приближенная оценка защищенности потенциально-опасных объектов. Структурные параметры защищенности объектов / А.С. Боровский, А.Д. Тарасов // Программные продукты и системы. - №3(103). 2013 г. - С. 235-243.
2. Бирюков, А.А. Информационная безопасность: защита и нападение / А.А. Бирюков. - М.: ДМК Пресс. 2012. - 474 с.: ил.
3. Доктрина информационной безопасности Российской Федерации от 5 декабря 2016 г. N Пр-646. - М., 2016. - 16 с.
4. Костин, В.Н.  Проектирование систем физической защиты потенциально опасных объектов на основе развития современных информационных технологий и методов синтеза сложных систем: монография / В. Н. Костин, С. Н. Шевченко, Н. В. Гарнова; Оренбургский гос. ун-т. - Оренбург: ОГУ, 2013. - 202 с.
5. Родичев, Ю.А. Нормативная база и стандарты в области информационной безопасности. Учебное пособие / Ю.А. Родичев. - СПб.: Питер. 2017. - 256 с
6. Степанов, В.Н. Дискретная математика: графы и алгоритмы на графах: учебное пособие / В.Н. Степанов. - Изд-во ОмГТУ. 2010. - 118 с.
7. Царегородцев, А.В. Методы и средства защиты информации в государственном управлении. Учебное пособие / А.В. Царегородцев, М.М. Тараскин. - Издательство «Проспект». 2017. - 193 с.
8. Listrovoy, S.V., Tretjak, V.F. and Listrovaya, A.S. (1999), “Parallel algorithms of calculation process optimization for the Boolean programming problems”,Ibid., Vol. 16, pp. 569-579.
9. Третьяк В.Ф., Пашнева А. А. Оптимизация структуры хранилища данных в узлах сети инфокоммуникационной сети облачного хранилища // Системы навигации и связи Полтавского национального университета имени Юрия Кондратюка. №4 (44). - 2017 - С. 122-128.