Проблема защиты вычислительных систем от компьютерных вредоносных программ (ВП), в частности компьютерных вирусов, является и еще долго будет оставаться актуальной, поскольку, во-первых, в настоящее время существует огромное количество ВП, на поиск и выявление которых затрачиваются значительные компьютерные ресурсы, что часто является неудобным и даже неприемлемым; во-вторых, интервал времени между появлением новых ВП (вирусов) и средств противодействия им обычно составляет несколько месяцев, в течение которых компьютерная среда подавляющего большинства пользователей совершенно беззащитна по отношению к этим ВП; в-третьих, активное присутствие подавляющего большинства людей в глобальной сети Интернет, которая является одним из наиболее опасных каналов проникновения компьютерных вирусов, существенно повышает вероятность заражения пользовательского компьютера вредоносными программами. Проблеме анализа процесса распространения вирусных и иных атак на пользовательские рабочие места посвящено много работ, в частности [1-3]. Однако работ, опирающихся при анализе на методы теории графов, крайне мало [3, 4]. Близкой работой является [5]. Ниже предлагается один из возможных подходов к анализу различных характеристик, связанных с вирусными атаками, на основе методов теории графов. Среди зарубежных изданий отметим работы [6, 7]. Оценка основных характеристик процесса распространения вредоносных программ Представим процесс распространения ВП в виде графа следующим образом. Рассмотрим процесс распространения ВП, привязанных к программным средствам либо информационным документам (назовем их объектами обработки (ОО)). В этом случае граф отображает взаимосвязи между различными ОО и, как следствие, потенциальные пути распространения ВП от одних ОО к другим. Граф является ориентированным, направление дуги (стрелка) указывает на тот ОО, в который может проникнуть ВП из ОО, примыкающего к началу дуги. Заданы также вероятности {, 1 ≤ i ≤ N} (N - число всех вершин графа) того, что атака ВП на i-й узел графа окажется успешной. Тогда типовые методы анализа характеристик графов [7] позволяют оценить ряд важных характеристик распространения ВП. Перечислим эти характеристики. 1. Для j-го объекта графа (т. е. вершины графа) найти длину Пнач(j) цепочки минимальной длины, т. е. номер такта процесса функционирования сети и связанного с этим процесса обработки объектов, к которому хотя бы один из ОО, из которых может произойти обращение (запуск, обработка и т. п.) к j-му объекту, уже мог быть подвергнут воздействию ВП. То есть Пнач(j) есть минимальный номер такта обработки данных, на котором j-й ОО может уже быть подвергнут воздействию ВП. Ниже есть вероятность того, что на m-ом такте i-й ОО обратится к j-му. Для вычисления Пнач(j) находится наибольшее число k ≤ N такое, что хотя бы для одного i и для всех текущих i и m, таких, что m ≤ k. Если для всех , то полагаем k = N. Здесь матрица . Полагаем Пнач(j) = k. При этом вероятность того, что ВП воздействовала на j-й ОО, равна сумме (i, j)-х элементов матрицы , где , т. е. . 2. Для j-го ОО найти длину цепочки (номер такта движения обработки объектов) , к которому вероятность воздействия ВП на j-й объект будет больше заданного уровня pдоп, либо достигает своего наибольшего значения. То есть П(j) есть наименьший момент, когда заражение j-го ОО станет недопустимо большим либо максимально возможным. Данная характеристика учитывает возможность циклической взаимосвязи объектов друг с другом, при которой заражение объекта вредоносной программой может произойти на одном циклов. Для вычисления находится наименьшее число k такое, что либо , либо и для всех хотя бы для одного i, и для всех i и m таких, что k ≤ m ≤ 10. Если , то полагаем k = 10. Здесь матрица . Полагаем П(j) = k. Затем находится величина - номер такта, к которому все ОО уже подвергнуты воздействию угроз. 3. Выяснить, есть ли циклические маршруты взаимосвязи ОО, что создает возможности для повторных атак. Для этого вычислить матрицу . Если матрица Ω имеет ненулевые элементы на диагонали, то в системе имеются циклы. Матрица Аn имеет квадратично-блочную структуру. При этом номера строк (столбцов), описывающих один квадратичный блок, указывают на номера вершин, образующих цикл. 4. Найти концевые (исходные и конечные) ОО. Исходным ОО соответствуют столбцы матрицы А, в которых все элементы нулевые. Конечным документам соответствуют строки матрицы А, в которых все элементы равны 0. Оценить степень опасности (как источника угроз) каждого исходного ОО для каждого конечного ОО. В качестве меры важности взять число путем lij, соединяющим исходную вершину под номером i с конечной вершиной под номером j, lij = wij , где . Вывести для каждой конечной вершины список важностей различных исходных вершин. 5. Для каждого документа определить номер такта τi, к которому этот документ окажет вредоносное воздействие на другие документы: . Оценить число тактов ti, в течение которых i-й ОО активен: ti = τi - П (i). Найти время Т заражения системы: . Для многозвенной (многоэшелонированной) структуры системы время заражения может достигать своего максимального значения: T = N = 10. Оценить оперативность L заражения системы: . 6. Для каждого ОО найти множество Ri тех ОО, которые могут воздействовать на i-й ОО. Ri есть множество номеров j, таких, что . Для каждого ОО найти множество Qi таких ОО, которые могут воздействовать (заразить вирусом) i-й ОО. Qi есть множество номеров столбцов, таких, что . Сделать выводы по результатам вычислений. Нахождение наиболее опасных путей распространения вирусных атак Рассмотрим задачу выявления наименее защищенных маршрутов проникновения на объект защиты. Данная задача актуальна при обеспечении структурно-технологической комплексности. Приведем постановку задачи. На основе анализа объекта защиты (в качестве объекта защиты был выбран один из фрагментов вуза) и экспертной оценки (в качестве экспертов были выбраны пять студентов группы; процедура проведения экспертизы описана выше) вероятностей движения угрозы (в частности, злоумышленника) от одной точки объекта защиты к другой, соседней (эти вероятности являются весами соответствующих ребер в графе), был сформирован граф проникновения, описывающий процесс движения угрозы (злоумышленника) по территории вуза (рис.) [8]. Граф проникновения на объект защиты Таким образом, вершинами графа являются определенные ключевые места (точки) на плане объекта защиты - в данном случае территории здания вуза. Основное требование к выбору этих точек - они должны располагаться внутри участка территории, однородной по своим характеристикам безопасности. Дуги графа отображают возможные направления перемещения злоумышленника по территории. Веса этих дуг (т. е. вероятности преодоления соответствующих участков территории) могут быть получены на основе экспертных методов либо путем проведения натурных экспериментов. Особое внимание следует обратить на выбор возможных точек проникновения в здание извне - это начальные точки искомого ориентированного графа. Этим точкам возможного проникновения в здание также приписываются весовые коэффициенты, описывающие относительные вероятности использования злоумышленником именно данной точки для проникновения в здание. Считаем, что все введенные вероятности описывают независимые события - это позволяет при расчетах пользоваться формулой умножения вероятностей. Конечными вершинами искомого ориентированного графа являются объекты интереса злоумышленника. В рассматриваемой задаче это серверное помещение. Тогда рассматриваемая задача может быть формализована следующим образом: выявить такой маршрут проникновения в серверное помещение, который имеет наибольшую вероятность проникновения. Поставленная задача относится к классу задач поиска на графах. Имеется ряд алгоритмов ее решения [9]. Одним из возможных методов решения является метод динамического программирования (ДП) [10, 11]. Процесс решения задачи включает пять этапов [8]. На первом выделяются последовательные уровни достижения вершин (табл. 1). Таблица 1 Разбиение графа на уровни иерархии Этап просмотра графа Вершины (в порядке просмотра) Вершины (в порядке неубывания) Этап решения (слой графа) 1 14 14 VIII 2 12, 13 12, 13 VII 3 11, 8 8, 11 VI 4 9, 4 4, 9 V 5 5, 6, 10 5, 6, 10 IV 6 1, 2, 7, 8 1, 2, 7, 8 III 7 3, 8, 4 3, 4, 8 II 8 4 4 I На втором этапе вводится целевая функция - функция Беллмана Fi (xi), на третьем этапе записывается основное уравнение ДП - уравнение Беллмана. В рассматриваемой задаче функция Беллмана Fi (xi) есть максимальное значение вероятности проникновения злоумышленника из вершины xi, входящей в i-й слой, в конечную (14-ю) вершину (). Для записи уравнения Беллмана необходимо ввести также переходные функции fi(xi, yi), описывающие успешное движение злоумышленника из вершины xi, входящей в i-й слой, в вершину yi, входящую в (i+1)-й слой, если вершины соединены. В противном случае указанная вероятность равна нулю. Значениями функции fi(xi, yi) являются веса соответствующих дуг графа. В результате приходим к следующему уравнению Беллмана для рассматриваемой задачи: , где максимум берется по всем вершинам yi, входящим в (I + 1)-й слой. Полагаем по определению . Четвертый этап, наиболее трудоемкий, заключается в построении таблиц расчета текущих вероятностей. В работе выбран метод ДП обратного хода, который лучше зарекомендовал себя при решении задач с неизменной (стационарной) структурой, каковой является и рассматриваемая задача. Поэтому вычисления выполняют, начиная с последнего этапа. Результаты вычислений приведены в табл. 2. Таблица 2 Расчетные таблицы метода динамического программирования № Входная вершина Переходная функция Функция Беллмана Выходная вершина 1 X7 f7 (x7, y7) F7(y7) y7 y7 = 14 12 13 0,2 0,3 0,2 0,3 14 14 2 X6 f6(x6, y6) ∙ F7(y6) F6(y6) y6 y6 = 12 y6 = 13 8 11 0,7 ∙ 0,2 0,5 ∙ 0,2 0,5 ∙ 0,3 - 0,15 0,1 13 12 3 X5 f5 (x5, y5) ∙ F6(y5) F5(y5) y5 y5 = 8 y5 = 11 4 9 0,5 ∙ 0,15 - - 0,9 ∙ 0,1 0,075 0,1 8 11 4 X4 f4 (x4, y4) ∙ F5(y4) F4(y4) y4 y4 = 4 y4 = 9 5 6 10 - - - 0,9 ∙ 0,1 0,9 ∙0,1 0,9 ∙ 0,1 0,09 0,09 0,09 9 9 9 5 X3 f3(x3, y3) X3 F3(y3) F3(y3) y3 y3 = 5 y3 = 6 y3 = 10 1 2 7 8 0,2 ∙ 0,09 - - - - 0,8 ∙ 0,09 - - - - 0,9 ∙ 0,09 0,3 ∙ 0,09 0,018 0,072 0,081 0,027 5 6 10 10 6 X2 f2(x2, y2) ∙ F2(y2) F3(y3) y3 y2 = 1 y2 = 2 y2 = 7 y2 = 8 3 4 8 - - - - - - 0,2 ∙ 0,081 - 0,3 ∙ 0,081 - 0,5 ∙ 0,027 - 0,016 2 0,013 5 0,024 3 7 8 7 7 X1 f1 (x1, y1) ∙ F2(y1) F1(y1) y1 y1 = 3 y1 = 4 y1 = 8 4 - - 0,5 ∙ 0,0243 0,012 15 8 В предпоследнем столбце (функция Беллмана) табл. 2 выделяются те значения, которые начинаются из какой-либо входной вершины Х. Именно среди этих значений и следует выбирать наибольшее значение целевой функции. В рассматриваемой задаче это наибольшее значение равно 0,075 - это и есть наибольшее значение целевой функции. На пятом этапе формируется непосредственно маршрут, на котором достигается указанное значение целевой функции. Из последней табл. 2 получаем, что максимальное значение достигается из входной вершины 4, из которой попадаем в вершину 8. Просматривая таблицы в обратном порядке, в результате получаем: из вершины 8 происходит переход в вершину 13, а из 13 - в конечную (14-ю). Таким образом, наиболее уязвимым маршрутом злоумышленного проникновения в защищаемое помещение (серверную) является следующий: 4 → 8 → 13→ 14, вероятность успешного проникновения по этому маршруту равна 0,075 (т. е. 7,5 %). Можно также найти следующие, наиболее вероятные по опасности, маршруты проникновения. Для этого необходимо последовательно по убыванию значений выбирать вероятности из последних столбцов таблиц, полученных на четвертом этапе. В рассматриваемой задаче следующим по величине значением является 0,072 (или 7,2 %) от входной вершины X3. Тогда аналогично предыдущему находим соответствующий маршрут: 2 → 6 → 9 → 11 → 12 → 14. Другие возможные маршруты не рассматриваются ввиду незначительности соответствующих вероятностей. Решение рассматриваемой задачи представляет особый интерес применительно к большим объектам. В этом случае граф проникновения может содержать очень много вершин и ребер, поэтому метод ДП может оказаться неэффективным. Таким образом, выбор метода решения поставленной задачи применительно к большим системам остается открытым. Отметим, что для больших систем граф проникновения может быть сформирован на основе автоматизированных процедур путем выделения однородных зон на плане объекта защиты. Заключение В работе рассматривается задача анализа возможных путей распространения вредоносных программ (ВП) на основе взвешенных графов, где граф описывает взаимосвязи между различными программами, а веса отображают вероятности перехода ВП от одной программной системы (файла) к другой (к другому файлу). Ставится задача выявления наиболее вероятных маршрутов распространения ВП и выявления наиболее вероятных путей их проникновения к заданному программному продукту. Предлагается для решения указанной задачи использовать метод динамического программирования. Процедура решения задачи продемонстрирована на конкретном примере. По результатам вычислений найден наиболее уязвимый маршрут проникновения и оценена вероятность успешной реализации атаки ВП на искомый программный продукт. Методы теории графов позволили также оценить ряд других числовых характеристик, связанных с процессом распространения ВП, в частности минимальное число тактов работы системы, после реализации которых возможно проникновение ВП к заданному программному продукту; количество тактов работы системы, когда вероятность проникновения ВП к конкретному файлу станет больше заданной величины; выявить циклические маршруты распространения ВП, что характеризует повторные попытки воздействия ВП на программный продукт; найти наиболее вероятные источники (файлы), откуда началось распространение ВП; найти множество тех файлов, откуда возможно проникновение ВП к заданному программному продукту.