ПРОБЛЕМЫ СИНТЕЗА И АНАЛИЗА ГРАФОВ АТАК

Томский государственный университет, г. Томск

E-mail: kden@sibmail.com

В статье приводится обзор основных подходов к синтезу и анализу графов атак. Описываются конкретные системы анализа защищенности компьютерных систем, использующие графы атак. Предлагается общая архитектура топологических сканеров безопасности.

Ключевые слова: топологический анализ защищенности, сканеры безопасности, графы атак, modelchecking, экспертные системы, теория графов, конечно-автоматные модели,  моделирование атак

Введение

Исследования, связанные с построением, анализом и применением графов атак, ведутся приблизительно с 1994 года. В отечественной литературе данной тематике уделяется незначительное внимание, несмотря на то, что в зарубежных публикациях приводятся примеры эффективно работающих систем, в том числе и коммерческих.

Неформально, граф атак – это граф, представляющий всевозможные последовательности действий нарушителя для достижения угроз (целей). Такие последовательности действий называются трассами (путями) атак.

На рис. 1–3 изображены примеры графов атак. Можно выделить следующие виды графов атак [1, 2] :

state enumeration graph (рис. 1) – в таких графах вершинам соответствуют тройки (s, d, a), где s – источник атаки, d – цель атаки, a – элементарная атака; дуги обозначают переходы из одного состояния в другое;

condition-orienteddependency graph (рис. 2) – вершинам соответствуют результаты атак, а дугам – элементарные атаки, приводящие к таким результатам;

exploit dependency graph (рис. 3) – вершины соответствуют результатом атак или элементарным атакам, дуги отображают зависимости между вершинами – условия, необходимые для выполнения атаки и следствие атаки. Например, атака RSH возможна, если нарушитель имеет привилегии суперпользователя на хосте 1 и хост 3 доверяет хосту 1. В результате атаки нарушитель получает привилегии пользователя на хосте 3.

                                          

     Рис. 1                                                                                                   Рис. 2

Под элементарной атакой (atomic attack) понимают использование нарушителем уязвимости. Примером элементарной атаки служит, например, переполнение буфера службы SSH, позволяющее удаленно получить права администратора системы.

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

В основном графы атак рассматриваются в контексте анализа защищенности сетей. Обычно такой анализ сводится к последовательному сканированию всех хостов сети на наличие известных уязвимостей. Результатом является отчет, содержащий перечень найденных уязвимостей и рекомендации по их устранению. В настоящее время постепенно внедряется другая парадигма анализа защищенности, учитывающая “топологию” компьютерной системы – взаимосвязь объектов компьютерной системы, их свойств и характеристик. Такой анализ защищенности называется топологическим, а средства, его выполняющие, топологическими сканерами безопасности.

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

минимизационный и т.д.).

 Построенный граф содержит все известные сценарии атак для достижения нарушителем угроз. Результатом его анализа может являться:

• перечень успешных атак, не обнаруживаемых IDS;
• соотношение реализуемых мер безопасности и уровня защищенности сети;
• перечень наиболее критичных уязвимостей;
•   перечень мер, позволяющих предотвратить использование уязвимостей в ПО, для которого отсутствуют обновления;
•  наименьшее множество мер, реализация которых сделает сеть защищенной.

Графы атак также используются при расследовании компьютерных инцидентов [3], для анализа рисков [4] и   корреляций предупреждений систем обнаружения атак [5, 6].

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

Основные подходы к синтезу графов атак

Проверка на модели (model сheсking) – это автоматический метод верификации систем с конечным числом состояний. Применение данного метода состоит из следующих этапов: моделирование – формальное описание M исследуемой системы; спецификация – выражение свойства P, которым должна обладать система, в формулах темпоральной логики, позволяющей описывать поведение системы во времени; верификация – проверка наличия у модели M заданного свойства P. Если модель M обладает свойством P, то возвращается “истина”; иначе приводится трасса – последовательность состояний системы, на которой возникает ошибка и, таким образом, не выполняется проверяемое свойство P.

Пусть M – модель сети, свойство Pозначает ”сеть безопасна”. Тогда, если при верификации окажется, что свойство P ложно, средство верификации выдаст трассу атаки, ведущую к нарушению свойства системы.

Впервые данную технику применили Ramakrishnan и Sekar в 1998 году [7] для анализа защищенности UNIX-хоста. В 2000 году Ritchey и Ammann [8] использовали не модифицированную систему modelchecker SMV для анализа защищенности сети. Символьный верификатор моделей SMV – это инструментальное средство, предназначенное для проверки того, что модель системы удовлетворяет спецификации, заданной CTL. В нем применяется символьный алгоритм верификации моделей, основанный на OBDD (Ordered Binary Decision Diagrams). При ложности спецификации демонстрируется путь вычислений, служащий контрпримером, и программа завершает работу. Модель сети задается вручную на языке SMV. Эти две реализации получают только один путь, где нарушается спецификация системы. Другими словами, вычисляется только одна из атак, приводящих к угрозе.

Jha, Sheyner и Wing [9] применили модифицированную систему верификации NuSMV. Модификация заключается в выдаче всех путей вычислений, для которых оказывается ложной спецификация безопасности системы (см. рис. 1). Множество всех таких путей есть граф атак. Время работы программы для сети из 4 хостов и 4 уязвимостей составляет 5 сек., а для сети из 5 хостов и 8 уязвимостей – более двух часов.

Основное достоинство данного подхода – формальность: если анализируемая система (а точнее, модель системы) признана безопасной, то это означает, что все варианты атак были рассмотрены, и вопросов касательно полноты анализа не возникает. Если же система не обладает данным свойством, то в процессе проверки всегда будет построен контрпример, представляющий собой последовательность действий нарушителя для достижения угрозы. Недостаток – при большом числе хостов сети число возможных состояний становится необозримым, а анализ – невозможным. Например, применение последнего средства к сети, состоящей из 10 хостов и 5 уязвимостей, позволило получить граф атак, содержащий порядка 10 миллионов ребер. В настоящее время факт неадекватности методов верификации для построения графов атак является общепризнанным.

В настоящее время следующие направления исследований, связанные с подходом modelchecking, являются актуальными:

1. использование логик LTL, CTL* и µ-исчисления для задания спецификаций системы,
2. использование различных систем верификаций моделей (например, SPIN и SVC).

Интерес представляет также возможность применения подходов автоматического доказательства теорем (например, HOL) для построения графов атак.

Экспертные системы. Подход к построению графов атак с использованием экспертных систем предложен Danforth [1]. В работе использовалась экспертная система Java ExpertSystem Shell (JESS). Выбор обосновывается тем, что данная система, во-первых, использует реализацию эффективного алгоритма Рете (Rete) для нахождения соответствия фактов и правил, и, во-вторых, имеет язык, позволяющий достаточно просто добавлять описания новых элементарных атак. В контексте построения графов атак правила соответствуют выполнению элементарных атак, а факты – состояниям сети. Для описания атак используется модель requires/provides [10, 11], так как хорошо подходит для поиска экспертной системой. В ней всякая элементарная атака представляется множеством условий (предусловий), необходимых для реализации атаки, и множеством следствий (постусловий) – изменений состояния сети вследствие атаки. Например, предусловия: на хосте B запущена уязвимая SSH служба, нарушитель имеет необходимые привилегии на хосте A, 22 порт на хосте B доступен с хоста A; постусловие: нарушитель имеет права администратора на хосте B.

Подход заключается в применении правил к фактам, т.е. ищется предусловие, удовлетворяющее состоянию сети, и состояние изменяется в соответствии с постусловием. Данный подход является более эффективным по сравнению с подходами, использующими model checking, и позволяет анализировать небольшие сети (порядка 1000 хостов) с небольшим числом служб и уязвимостей.

Формальные грамматики. Котенко и Городецкий в [12, 13] предложили подход, основанный на стохастических контекстно-свободных формальных грамматиках, для моделирования атак и построения графов атак. В их работах описывается онтология сетевых атак – систематизация и классификация всевозможных угроз и атак. Формально, онтология есть дерево, на множестве узлов которого заданы отношения: “часть”, “вид”, “последовательность” и “пример”. Две вершины дерева соединены ребром, если и только если они принадлежат одному из отношений. Всякую угрозу можно представить последовательностью символов. Эти последовательности рассматриваются как слова языка, сгенерированного формальной грамматикой. Соединение двух узлов в дереве (онтологии) определяется операцией подстановки, где терминальные символы родительского узла рассматриваются как аксиомы формальной грамматики, соответствующей дочернему узлу.

    Логический подход. В [14] предложен подход, основанный на логическом программировании, для построения графов атак. Авторы модифицировали систему анализа защищенности сетей MulVAL [15], использующую логическое программирование для вычисления возможных атак.

Логический граф атак состоит из вершин вывода (derivation node) и вершин фактов (facts node). Всякой вершине факта соответствует логическое высказывание в форме предиката p(t₁, . . . , t_k), истинное или ложное в зависимости от его аргументов. Вершине вывода соответствует правило вывода вида: L₀ |– L₁, . . . , L_n. Дуги в графе обозначают отношение зависимости. Модель сети представляет собой множество высказываний языка Datalog вида:

hacl(internet, webServer, TCP, 80),
vulExists(webServer, ’CAN-2002-0392’, httpd),
networkService(webServer, httpd, TCP, 80, apache)

Атаки моделируются правилами Datalog.

Рассмотрим, например, следующее правило:

execCode(Attacker, Host, User) |–
networkService(Host, Program, Protocol, Port, User),
vulExists(Host, VulID, Program, remoteExploit, privEscalation),
netAccess(Attacker, Host, Protocol, Port)

В нем предикаты networkService, vulExists, remoteExploit являются примитивными, а предикаты ecexCode и netAccess выводимыми. Правило определяет предусловия и постусловия для атаки: если сервис Program запущен с правами пользователя User на хосте Host, использует порт Port, протокол Protocol и имеет уязвимость с идентификатором VulnID, позволяющую повысить привилегии, и нарушитель имеет сетевой доступ к службе, то он может выполнить код на машине Host от имени User.

Для вычисления всех возможных трасс атак используется модифицированная система доказательств MulVAL, сохраняющая найденные трассы атак. Для этого в правила вывода MulVAL добавляется специальная функция, которая сохраняет вывод всякого истинного правила. По этим сохраненным данным строится граф атак. Доказано, что для построения графа атак сети из N хостов необходимо время между O(N ²) и O(N ³). Данным средством был построен граф атак для сети из 1000 хостов (Pentium 4 CPU, 1 GB RAM).

Graph-based подходы (подходы основанные на теории графов).Данные подходы в своей основе используют методы теории графов. В 1999 году Брюс Шнайер [16] ввел неформальное понятие деревьев атак для систематизации и категоризации различных сценариев атак на компьютерные системы. Дерево атак представляет собой методологию описания угроз и мер противодействия для защиты систем. Дерево атак определяется следующим образом: корню дерева соответствует цель нарушителя, потомкам всякой вершины (подцелям) – действия нарушителя для достижения цели. Действия комбинируются с помощью логических И и ИЛИ. Вершинам и ребрам могут назначаться различные числовые значения, которые характеризуют вероятность успеха, сложность, стоимость действий нарушителя. Всякий путь, ведущий от листа к корню – трасса атаки (см. рис. 4).

рис.4

В [6] предлагается формальный способ моделирования и обнаружения атак. Определяется расширенное дерево атак введением двух атрибутов: времени жизни TTL и степени уверенности PC. Первый атрибут отражает временные зависимости между этапами атаки и позволяет уменьшить число ложных срабатываний системы обнаружения атак (СОА). Второй характеризует вероятность достижения цели при достигнутых подцелях. Затем, используя [18], строится автомат расширенного дерева атаки. Обнаружение атак заключается в обходе расширенного дерева атак. Параллельный автомат представляет собой формальное объединение автоматов и применяется для обнаружения атак. В качестве примера разбирается обнаружение комплексных атак в беспроводных сетях для стандарта 802.11. Прототип СОА успешно обнаруживает сценарии атак с небольшим числом ложных срабатываний.

В [19] дается формальное определение деревьев атак [14] с помощью дизъюнктивных сетей Петри. В этой модели места соответствуют атакам, а переходы часто выражают логические зависимости, моделируя тем самым действия нарушителей, что расширяет данную модель по сравнению с деревьями атак Шнайера.

Swiler, Philips в [20, 21] строят граф, вершины которого соответствуют состояниям, а дуги – переходам из одних состояний в другие. Всякой дуге приписано значение, характеризующее успех атаки или ее длительность. Из графа удаляются вся избыточные пути. Далее на графе ищутся кратчайшие пути к целевым вершинам алгоритмом Дейкстры.

Ammann, Wijesekera, Kaushik [10] использовали условие монотонности для анализа графа атак алгоритмом, сложность которого O (N ⁶). Условие монотонности означает, во-первых, невозможность изменения числа предусловий элементарной атаки, а во-вторых, определяет только однонаправленное изменение. Например, если нарушителю для получения доступа с правами администратора на хосте A требуются такие предусловия, как наличие уязвимости и сетевого доступа, то, получив доступ, нарушитель никогда его не утратит, а количество предусловий никогда не изменится. Стоит отметить, что подходы с использованием modelchecking не используют данное приближение.

Jajodia, Noel и O'Berry в [2, 22, 23] исследуют графы аналогичные [10]. Рассматривается задача предотвращения угроз путем изменения начальных свойств системы. Решение состоит из двух частей. Сначала трасса атаки представляется в алгебраической форме, а затем определяются начальные условия, изменение которых может устранить угрозы. В [23] описывается представление трасс атак в виде КНФ для вычисления всевозможных решений устранения уязвимостей.

Основные проблемы синтеза графов атак

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

Кроме этого, необходимо определить достижимость между всеми хостами, учитывая, например, МЭ и маршрутизаторы. Во многих работах граф строится в предположении наличия таких данных. Простейший подход вычисления доступности требует дополнительных N ² шагов перед построением графа и заключается в построении матрицы достижимости A размера N×N, где a[i][j] = 1 тогда и только тогда, когда хост j доступен хосту i. Определение достижимости устройств в крупной сети является трудной задачей. Не всегда возможно определить достижимость устройства, используя только сканеры безопасности. Точное определение достижимости между хостами требует анализа конфигурационных правил МЭ, маршрутизаторов, коммутаторов, VPN-шлюзов, персональных МЭ и других устройств. На рис. 5 приведена архитектура топологического сканера безопасности NetSPA. 

Рис. 5

Применимость алгоритмов для реальных сетей. Многие алгоритмы построения графов не могут быть применены для реальных сетей. Так, все подходы, основанные на использовании полных графов, являются не эффективными. Например, полный граф атак часто не мог быть вычислен в [24] даже при наличии 13 уязвимостей в файловой системе UNIX-хоста.

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

Генерация рекомендаций по графу атак. В результате построения графа атак и его анализа необходимо выдать рекомендации по предотвращению возможных атак. Данные рекомендации могут предполагать как изменения в сетевой архитектуре, так и установку обновлений ПО. Noel и Jajodia в [2] разработали подходы для выдачи подобных рекомендаций.

Системы топологического анализа защищенности

Далее рассматриваются три наиболее мощные и интересные системы анализа защищенности. Приводится их архитектура, иллюстрируются примеры графов атак и, где это возможно, экспериментальные данные.

TVA tool (Topological vulnerability analysis tool) [22]. Система разработана в университете Джорджа Мэйсона. Описания элементарных атак, сети и цели нарушителя вводятся вручную в модели предусловий и постусловий. Для генерации и анализа графа атак используется полиномиальный алгоритм. Данная система не только генерирует граф, но и предлагает меры по повышению уровня безопасности. Данное средство имеет много недостатков: модели описываются вручную, при определении достижимости хостов правила МЭ и ACL маршрутизаторов не анализируются (вместо этого используется сканер Nessus, который определяет достижимость двух любых хостов), алгоритм, лежащий в основе TVA, имеет оценку вычислительной сложности O(N ⁶). Данный алгоритм будет работать в сетях, где число хостов не превышает сотни. Стоит отметить, что данный подход ограничен монотонными атаками. Для описания атак требуются низкоуровневые детали. Подход предполагает, что возможно получить информацию, необходимую для детального моделирования низкоуровневых атак, и использовать ее корректно, что обычно невозможно в силу непрактичности и трудности. На рис 6. изображена анализируемая сеть и соответствующий ей граф атак.

Рис. 6

Система NetSPA[25-28] разработана в Массачусетском технологическом институте. Исследования в области анализа защищенности ведутся с 1999 года. Первая версия NetSPA строит полные графы атак и способна анализировать небольшие сети (порядка 100 хостов). С введением графов предсказаний (predictive graph) производительность системы значительно повысилась – были проанализированы реальные сети из 3400 хостов и моделируемые сети из 10000 хостов. Последняя ее редакция на сегодняшний день является наиболее мощной и способна анализировать моделируемые сети из 50000 хостов за 4 мин. (Windows Server 2003, Xeon 3.2 GHz, 2 GB). Архитектура системы изображена на рис. 6. NetSPA может импортировать данные из сканера Nessus, МЭ Sidewinder и Checkpoint, из баз уязвимостей CVE и NVD. Система строит MP-граф (multiple-prerequisite graph), затем автоматически анализирует его, создает отчет и выдает рекомендации. Для более эффективного определения достижимости хостов используются BDD-графы. Для выдачи изображения графа используется сжатие вершин. На рис. 7 показана анализируемая сеть и часть соответствующего ей графа атак (реальный граф содержит 8901 вершин и 23315 дуг). Основной этап построения графа занял 24 сек., использовалась рабочая станция Pentium-M 1,6 GHz, 1Gb, Linux 2,6.

Рис. 7

Интеллектуальная система анализа защищенности (САЗ). Разработана в 2006 в СПИИРАН [12, 13]. В данной системе анализа защищенности используются две базовые модели: модель формирования общего графа атак и модель оценки уровня защищенности. Архитектура САЗ представлена на рис. 8. Граф атак отражает возможные распределенные сценарии атак с учетом конфигурации сети, реализуемой политики безопасности, а также местоположения, целей, уровня знаний и стратегий нарушителя.

Рис. 8

Метрики защищенности (CVSS, методики SANS/GIAC, FRAP) позволяют оценивать защищенность компьютерной сети и ее компонентов с различной степенью детализации и с учетом разнообразных аспектов.

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

Рис. 9

 

Общая архитектура топологического сканера безопасности

На основе приведенных выше архитектур можно предложить общую архитектуру топологического сканера безопасности. Схематически она представлена на рис. 10.

Рис. 10

Опишем назначение основных систем.

Система сбора данных (Data Collector) включает сетевые и хостовые сенсоры и предназначена для сбора данных, необходимых для моделирования компьютерной системы. Хостовые сенсоры устанавливаются на МЭ, маршрутизаторах, серверах, рабочих станциях и служат для проверок наличия уязвимостей, анализа конфигурационных файлов, таблиц маршрутизации и т.п. Сетевой сенсор устанавливается на отдельную систему и осуществляет сбор сведений и проверки на наличие уязвимостей по сети, выполняя или моделируя атаки.

Система хранения данных (Data Storage) состоит из баз данных и предназначена для хранения данных, собранных сенсорами, топологии сети, моделей компьютерных систем, графов атак и отчетов.

Система построения графов атак (Graph Builder) предназначена для синтеза графа атак по имеющимся данным. Система анализа (Graph analyzer) служит для проведения анализа защищенности путем исследования графа атак и формирования отчета. В ходе анализа графа система вычисляет всевозможные сценарии нападения, наиболее значимые угрозы и пути их достижения, минимизирует и визуализирует граф атаки.

Подходы к анализу графов атак

Анализ графа атак является необходим, так как построенный граф атак ввиду его размера и сложности не всегда может быть информативным для человека; хотя и существуют методы изображения графов, позволяющие снизить их визуальную сложность. Результат анализа определяется предназначением графа атак. Так для расследования инцидентов и подсистем корреляционного анализа IDS анализ должен позволять предсказывать дальнейшие действия нарушителя и предоставлять перечень систем на пути атакующего для расследования. Для IPS анализ должен предсказывать шаги атакующего и выбирать разумные ответные действия (response) для блокирования атаки нарушителя. И, наконец, для топологических сканеров безопасности анализ должен найти всевозможные сценарии нападения атакующего и вычислить меры для их устранения. Далее речь пойдет о последнем виде анализа – его цель: определить меры, которые предотвратят угрозы, и тем самым повысят уровень защищенности системы. В [1] мера определяется как действие, удаляющее предусловие элементарной атаки. Этими действиями может быть обновление ПО, изменения правил МЭ (фильтрация порта), размещение сенсора IDS. Всем действиям назначаются стоимости, определяемые политикой безопасности сети. Например, если в политике заявлено, что web-сервер на машине A является общедоступным, то мера “firewall port 80 to machine A” должна иметь огромную стоимость, такую что ее применение становится невозможным.

Рассмотрим основные методы и подходы к анализу графов атак. Philips и Swiler в [21] определяют кратчайшие пути к целям алгоритмом Дейкстры. Также вычисляется множество путей наименьшей стоимости алгоритмом Наора-Брутлага. Показывается, что задача определения множества эффективных мер защиты (в смысле стоимости) является NP-трудной. Предлагается следующая интерактивная техника: администратор в соответствии с принятыми мерами защиты изменяет модель сети в конфигурационном файле, а затем выполняет пересчет кратчайших путей, чтобы увидеть повысили ли данные изменения уровень защищенности сети или нет. Sheyner [29, 30] проводит анализ, целью которого является нахождение минимального критического множества атак – множество атак наименьшей мощности, удаление которых из арсенала нарушителя приведет к невозможности достижения им цели. Показывается, что задача поиска такого множества является NP-полной, и предлагается “жадный” эвристический алгоритм ее решения сложности O(mn), где m – число состояний и ребер, n – число атак.

Jajodia, Noel и O'Berry [22, 23] выполняют рекурсивный алгебраический анализ графа атак. Всякая цель, элементарная атака или предусловие интерпретируются логическими переменными. Взаимосвязь между ними характеризуется логическим выражением. Цель нарушителя достигается при выполнении всех предусловий элементарной атаки, поэтому над логическими переменными, соответствующим предусловиям выполняется операция конъюнкция. Разные атаки могут привести к одним и тем же целям, поэтому над логическими переменными, соответствующим элементарным атакам, выполняется операция дизъюнкция. Такие замены производятся рекурсивно, пока предусловиями не окажутся начальные условия. Итоговое выражение затем записывается в ДНФ. Таким образом, итоговое выражение состоит из термов, каждый из которых есть наименование начального условия, определя меры по предотвращению угрозы. Ниже изображен граф атак для примера сети на рис. 6.

рис. 11

Отсюда вычисляем ДНФ

g = δβ)c₄c₅c₇c₈c₉ =

= αc₄c₅c₆c₁c₂c₄c₅c₇c₈c₉= c₁c₂c₄c₅(c₆ c₇c₈c₉).

Так как администратор не может контролировать начальные условия на машине нарушителя, то c₂ = c₉ = c₈ = 1 и, следовательно,

g = c₁c₄c₅(c₆  c₇).

Получаем следующие возможные решения:

1. c₁= 0: обновить или отключить IIS на хосте maude;
2. c₄ = 0: запретить исходящий rsh с хоста maude;
3. c₅ = 0: удалить rcp с хоста maude;

4.       c₆  c₇ = 0: отключить или обновить сервис wu_ftpd на хосте ned и заблокировать все неиспользуемые порты на хосте maude.

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

В [1] предложен генетический алгоритм вычисления мер максимально повышающих защищенность сети с минимальной стоимостью. Возможными методами защиты являются:

1. обновление ПО – применение данного метода влечет удаление из графа атак вершины, соответствующей устраненной уязвимости;
2. фильтрация трафика между двумя хостами МЭ – удаление из графа атак ребер, соответствующих данным сетевым соединениям;
3. размещение сенсора IDS для обнаружения атаки – метка ребер в графе атак.

Каждый метод защиты имеет стоимость, определяемую политикой безопасности сети или целями анализа сети.

В [1] предлагается генетический метод анализа графов атак. В основе его лежит применение генетического алгоритма для определения множества мер наименьшей стоимости максимально повышающих защищенность сети.

К возможным мерам относятся:

1. обновление ПО, что влечет удаление вершины соответствующей устраненной уязвимости в графе атак;
2. запрет соединения на данный порт хоста a с хоста b, что влечет удаление дуги, соответствующей данному соединению;
3. размещение сенсора IDS для обнаружения атак выполняемых с хоста a на хост b; соответствующие дуги помечаются, как “наблюдаемые”.

Каждая мера имеет стоимость (cost), определяемую политикой безопасности сети. Хромосома есть конкатенация трех булевых векторов, каждый из которых соответствует одной из мер защиты. Длина первого булева вектора равна количеству уязвимостей, которые можно устранить обновлением ПО; если бит i равен 1, то это означает что i-ая уязвимость будет устранена обновлением. Второй и третий булевы вектора соответствуют дугам в графе атак. Наличие единичной компоненты означает соответственно фильтрацию или размещение сенсора IDS (добавление правила для IDS). Функция приспособленности (fitness) для хромосомы h определяется как f  = benefit (h)/cost(h), где cost(h) – сумма стоимостей всех реализованных мер защиты в данной хромосоме, benefit(h) – количество входящих дуг в вершину, удаляемых после реализации мер определяемых хромосомой.

Данный метод является более гибким по сравнению с предыдущими: позволяет рассматривать альтернативные меры защиты (фильтрация трафика, обнаружение атак) и учитывать политику безопасности сети.

Заключение

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

Литература

1. DanforthM. Models for Threat Assessment in Networks. – http://www.cs.ucdavis.edu/research/tech- reports/2006/CSE-2006-13.pdf
2. Jajodia S., Noel S. Managing Attack Graph Complexity Through Visual Hierarchical Aggregation. // In 1st International Workshop on Visualization and Data Mining for Computer Security, Washington, DC, USA. – October 2004. – P. 109 – 118.
3. Stephenson P. Using formal methods for forensic analysis of intrusion events – a preliminary examination. – http://www.imfgroup.com/Document Library.html.
4. Amenaza. A Quick Tour of Attack Tree Based Risk Analysis Using. http:// www.amenaza.com.
5.  Cuppens F. Alert Correlation in a Cooperative Intrusion Detection Framework // Proc. of the 2002 IEEE    Symposium on Security and Privacy. – 2002.
6. Camtepe S., Yener B. A Formal Method for Attack Modeling and Detection. http:// cs.rpi.edu/research/pdf/06- 01.pdf.
7.  Ramakrishnan C.R., Sekar R. Model-Based Analysis of Configuration Vulnerabilities. – http://seclab.      cs.sunysb.edu/seclab1/pubs/papers/wids00.pdf
8. Amman P., Ritchey R. Using Model Checking to Analyze Network Vulnerabilities // Proc. of the 2000 IEEE    Symposium on Security and Privacy. – 2000. – P. 156-165.
9. Sheyner O., Jha S., Wing J., Lippmann R., Haines J. Automated Generation and Analysis of Attack Graphs // In 2002 IEEE Symposium on Security and Privacy. – Oakland, California, 2002.
10. Ammann P., Wijesekera D., Kaushik S. Scalable Graph-Based Network Vulnerability Analysis // Proc. of the 9th ACM Conference on Computer and Communications Security, New York: ACM Press. – 2002. – P. 217–224.
11. Templeton S., Levitt K. A Requires/Provides Model for Computer Attacks // Proc. of the 2000 Workshop on   New Security Paradigms. – New York: ACM Press, 2001.
12. Котенко И.В., Степашкин М.В., Богданов В.С. Интеллектуальная система анализа защищенности    компьютерных сетей. – http://www.positif.org/docs/SPIIRAS-NCAI'06-Stepashkin.pdf.
13. Gorodetski V., Kotenko I. Attacks against Computer Network: Formal Grammar-based Framework and Simulation Tool. Lecture Notes in Computer Science, vol. 2516. – http:// www.springerlink.com/index/P74E2CPBPTT38N7X.pdf
14.  Ou X., Boyer W.F., McQueen M.A. A Scalable Approach to Attack Graph Generation. – http://www.cis. ksu.edu/~xou/publications/ccs06.pdf.
15. Ou X., Govindavajhala S., Appel A.W. MulVAL: A logic-based network security analyzer // In 14th USENIX    Security Symposium, Baltimore, MD, USA, August 2005. – http://www.cis.ksu.Edu/~xou/publications/  mulval_sec05.pdf
16. Schneier B. Attack Trees. – Dr. Dobbs Journal, December 1999.
17. Moore A., Ellison R., Linger R. Attack Modeling for Information Security and Survivability // Software  Engineering Institute, Technical Note CMU/SEI-2001-TN-01, March 2001.
18.  Comon H., Dauchet M., et al. Tree automata techniques and applications. http://www.grappa.univ-lille3.fr/tata.
19.  McDermott J.P. Attack Net Penetration Testing // Proc. of the 2000 Workshop on New Security Paradigms. New York: ACM Press. – 2001. – P. 15–21.
20.  Swiler L.P., Phillips C., Ellis D., Chakerian S. Computer-Attack Graph Generation Tool. // Proc. of the Second DARPA Information Survivability Conference & Exposition (DISCEX II), Los Alamitos, California, IEEE Computer Society. – 2001. – V. II. – P. 307 – 321.
21.  Phillips C., Swiler L.. A Graph-Based System for Network-Vulnerability Analysis // In Proceedings of the New   Security Paradigms Workshop, Charlottesville, VA, 1998.
22.   Jajodia S., Noel S., O'Berry B. Managing Cyber Threats: Issues, Approaches and Challenges, ch. Topological Analysis of Network Attack Vulnerability, Kluwer Academic Publisher, 2003.
23.   Jajodia S., Noel S., et al. Efficient Minimum-Cost Network Hardening Via Exploit Dependency Graphs. // In Proceedings of the 19th Annual Computer Security Applications Conference, Las Vegas, NV, USA, December 2003.
24. Ortalo R., Deswarte Y., Kaaniche M. Experimenting with Quantitative Evaluation Tools for Monitoring Operational Security. // IEEE Transactions on Software Engineering. – 1999, – v. 25. – P. 633 – 650.
25.  Artz M. NETspa, A Network Security Planning Architecture, M.S. Thesis, Cambridge: Massachusetts Institute of Technology, May 2002.
26. Lippmann R.P., Ingols K.W. An Annotated Review of Past Papers on Attack Graphs. – http://www. ll.mit.edu/IST/pubs/0502_Lippmann.pdf
27. Lippmann R., Ingols K., Scott C., et al. Evaluating and Strengthening Enterprise Network Security Using Attack Graphs. – http://www.ll.mit.edu/IST/pubs/0507_Lippmann.pdf
28.  Lippmann R.P., Ingols K.W., Piwowarski K. Practical Attack Graph Generation for Network Defense. –http://www.ll.mit.edu/IST/pubs/70.pdf
29. Sheyner O. Scenario Graphs and Attack Graphs. // Ph.D. dissertation, Carnegie Mellon University. –     Pittsburgh, PA, USA, April 2004.
30. Sheyner O., Jha S., Wing J. Two Formal Analyses of Attack Graphs. // IEEE Computer Security Foundations    Workshop, Cape Brenton, Nova Scotia, Canada. – June 2002. – P. 49–63.