An effective algorithm for building a set of the shortest attacks within the context of one model of attack development .pdf Впервые идея представлять множество атак в сети в виде графа специального вида высказана в [1], где были использованы программные средства решения задач символьной верификации. Однако довольно быстро стало ясно, что такой способ представления атак неэффективен с вычислительной точки зрения. В [2, 3] и ряде других работ предложены иные подходы к построению графов атак. Ценность работы [2] заключается в том, что в ней впервые представлена модель развития атак, в рамках которой граф, представляющий все атаки в сети, строится за полиномиальное от числа хостов сети время. Помимо собственно генерации графов атак, в [1, 2] исследованы задачи оптимизационного характера. Так, в [1] показано, что в рамках использованной в данной работе модели задача поиска «минимальной атаки» является NP-трудной. В [2] описан полиномиальный алгоритм поиска «локально минимальной атаки». По-видимому, наиболее эффективными на сегодняшний день способами представления атак являются модели, описанные в [3-5]. На наш взгляд, основной недостаток этих моделей заключается в том, что получаемые в них графы содержат петли, что не позволяет корректно определять длину атаки. В настоящей работе рассматривается модель развития атак в сети, при которой задача представления множества кратчайших атак имеет эффективное решение. Следует отметить, что во многих ключевых работах по графам атак, к сожалению, недостаточно чётко прописана система базовых понятий - абстратные понятия часто путаются с конкретными. Такая ситуация имеет место, например, по отношению к понятию «доступ». Наилучшим образом в плане таксономии организована диссертация М. Данфорт [6], но и в ней имеется ряд упущений. Например, Данфорт выделяет два уровня доступа, которые злоумышленник может иметь на атакуемом им хосте: это «user» и «root». Эти формы доступа злоумышленник получает, эксплуатируя уязвимости, имеющиеся на хосте. Возникает вопрос об уровне доступа, который был у злоумышленника в тот момент, когда он провёл первую элементарную атаку. Этот и другие похожие вопросы никак не акцентируются в подавляющем большинстве работ. Далее мы пытаемся исправить указанные недостатки: строим конкретный пример набора базовых понятий, в рамках которого доказываем основной результат о сложности представления множества кратчайших атак. Используемая система понятий и соответствующая ей модель являются весьма простыми, однако при необходимости их легко дополнить до уровня, достаточного для описания атак в реальных компьютерных сетях. Будем рассматривать компьютерную сеть в виде простого неориентированного помеченного графа G = (V, E,Ly). Здесь V - множество вершин, называемых далее хостами, | V| = n. Выделим в V две вершины: vm (M от Malefactor) -хост злоумышленника, vT - «целевой хост». Через E обозначено множество рёбер графа G. Произвольное ребро (v1,v2) Е E отображает прямую физическую связь между хостами v1 и v2, простейшая конкретизация - проводное соединение компьютера с маршрутизатором. Окрестность вершины v Е V - множество смежных с ней вершин. С хостом v Е V связывается двоичное слово , называемое вектором уязвимостей. Множество всех слов вида обозначается через Ly. Далее потребуется такое важнейшее понятие, как «доступ». В соответствии с [7] доступ объекта A (обычно называемого субъектом) к объекту B - это возможность A читать, а в некоторых случаях и модифицировать данные, которыми располагает B. В рамках рассматриваемой далее (базовой) модели развития атак целесообразно выделить следующие три уровня доступа: 1) Уровень доступа, обозначаемый user0, хоста v' к хосту v" предполагает возможность v' читать вектор Zv«. Данный уровень доступа - то, чего не хватает в упомянутых выше работах. Он соответствует ситуации, когда хост v' (v' может быть как хостом vm , так и хостом, на котором M получил некие права) может физически связаться с хостом v'' (например, сканируя некоторые порты). 2) Уровень доступа, обозначаемый user, хоста v' к хосту v'' предполагает, что v' может вычислять все функции из некоторого списка S, аргументами которых являются координаты вектора . 3) Уровень доступа, обозначаемый root, хоста v' к хосту v'' предполагает, что v' получает право user0 на все хосты, находящиеся в окрестности v'' в графе G. Здесь необходимо оговориться, что в контексте представления атак на сеть G нас интересуют только действия злоумышленника. Везде далее предполагаем, что повышение прав доступа с хоста v' на хост v'' осуществляет M, который действует «от имени» v'. В таком контексте удобно рассмотреть развитие атак в сети как дискретный динамический процесс: например, получению M права user на v'' в момент t + 1 предшествует получение M права user0 на v'' в момент t плюс некоторые дополнительные действия. При этом получению M права user0 на v'' в момент t предшествует получение M в момент t - 1 права root на хосте v', таком, что (v',v'') Е E. Далее понадобится ещё одно ключевое понятие - уязвимость. Уязвимости хоста v - это условия, наличие которых позволяет злоумышленнику, атакующему данный хост, поднять свой уровень доступа к v. Через U будем обозначать список всех возможных уязвимостей в сети. В произвольном векторе координаты, равные 1, указывают на те уязвимости из U, которые присутствуют на хосте v. Повышение прав доступа (privilege escalation [3, 4, 6]) M с хоста v' на хост v'' (с user0 до user и root) происходит за счёт процесса, называемого эксплуатацией уяз-вимостей. Эксплуатация уязвимостей - это последовательность вычислений значений функций из некоторого списка S. Каждое такое вычисление называется элементарной атакой [6] (или правилом взаимодействия [3, 4]). Тот факт, что при переходе от момента t к моменту t +1 M получает на v более высокий уровень доступа, будем отображать в специальном регистре (одномерном массиве), который связывается с M в моменты времени t = 0,1,... Состояние регистра в момент t будем обозначать R(t). В регистре R в момент t с каждым хостом v связано множество ячеек, разбитое на три подобласти. Первая подобласть, обозначаемая aV, содержит один бит, который равен 1, если M в момент t имеет на v доступ usero. Вторая подобласть Ъ\, в свою очередь, разбивается на две подобласти. Первая содержит один бит, который равен 1, если M в момент t имеет на v доступ с правом user. Во второй хранится множество пар вида (u, f), u G U, f G S: каждая такая пара отображает тот факт, что M в момент t реализовал элементарную атаку f, эксплуатирующую уязвимость u, и получил в результате право user на хосте v. Аналогично устроена область c^, в которой содержится информация о получении M права root на v в момент t. Атака на сеть состоит из элементарных атак, последовательно реализуя которые, M получает доступ на всё большее число хостов сети. Атака считается успешной, если существует такая последовательность элементарных атак, реализуя которую, M в некоторый момент времени получает право root на целевой хост vy. Далее постулируем следующие два факта (первый акцентируется во всех отмеченных выше работах, второй явно упоминается не всегда): 1) Требование монотонности: будем считать, что любое действие, совершённое злоумышленником в момент t ^ 1, не может быть отменено в последующие моменты времени. Это означает, что если в некоторый момент t в некоторую ячейку регистра R была записана 1, то в каждый момент вида t + e, e ^ 1, в данной ячейке в состоянии R(t + e) также будет находиться 1. 2) Полагаем, что мощности множеств U и S - константы, не зависящие от n. Учитывая второе свойство, отмечаем, что размер областей Ъ, и cV ограничен константой, соответственно длина регистра R - O(n) бит. Опишем алгоритм построения множества атак в сети G, основанный на процедуре обхода G (вариант обхода в ширину). Действуя в стиле [8], будем представлять развитие атак в G как дискретный динамический процесс, происходящий в моменты t = 0,1,... Состояния соответствующей дискретной динамической системы (ДДС) - это R(t). Все состояния регистра R(t) сохраняются. Алгоритм состоит из трёх стадий: начальной, инициализации и переходов в новые состояния. Начальная стадия соответствует моменту t = 0. Стадий инициализации и переходов в новые состояния может быть несколько. Приведём неформальное описание алгоритма. B (начальная стадия). Строится состояние R(0) -нулевой вектор. I (стадия инициализации). Вход: множество хостов Wj = {vi1,... , vip}, выход: множество хостов Wo = {v0l,..., v0q} (детализация далее). T (стадия переходов в новые состояния). Вход: множество Wo. Полагаем, что построены состояния R(0),..., R(t). 1) Рассматривается момент t. В состоянии R(t) области aV}Ъ\,cV заполнены нулями для всех v G Wo. В момент t +1 aV+1) = 1 для всех v G Wo. Итог: состояние R(t + 1). 2) Рассматривается момент t + 1. По всем вершинам v G Wo проверяется, может ли M получить на них право user. Выделяется множество Wo С Wo вершин, на которых M получает право user, вычисляя некоторые функции из S. Соответствующая информация записывается в область bit+2). Итог: состояние R(t + 2). 3) Рассматривается момент t + 2. По всем вершинам v G Wo проверяется, может ли M получить на них право root. Выделяется множество Wo С Wo вершин, на которых M получает право root, вычисляя некоторые функции из S. Соответствующая информация записывается в область cit+3). Итог: состояние R(t + 3). Конец стадии переходов. Множество Wo является входом следующей стадии инициализации. Алгоритм завершает работу в некоторый момент t* тогда и только тогда, когда R(t*) = R(t* + 1). Остановимся более детально на стадиях инициализации. Первая стадия инициализации - это выбор всех вершин из G, смежных с Vm. Обозначим данное множество W и пометим все вершины в нём как пройденные. Множество W - выход первой стадии инициализации (к W применяется стадия переходов в новые состояния). Пусть Wki - вход стадии инициализации с номером k ^ 2. Инициализация Ik заключается в следующем: рассматриваются окрестности всех вершин из Wki и выбираются только те вершины, которые не были помечены как пройденные. Объединяем полученные множества вершин. Результат - множество W^, все его вершины помечаются как пройденные. Отметим, что алгоритм формирования множеств Wk,Wk близок по смыслу алгоритму обхода графа в ширину (требуется помечать некоторые вершины как пройденные и исключать их из дальнейшего рассмотрения). Таким образом, сложность данного этапа составляет (в худшем случае) O(n2). Легко понять, что алгоритм всегда завершит работу: в силу свойства монотонности обязательно найдётся такое t*, что R(t* + 1) = R(t*) (R(t*) -неподвижная точка рассматриваемой ДДС). В силу определения массива R и предположения о множествах U и S значение t* ограничено сверху величиной O(n). Полагая, что вычислительное устройство имеет прямой доступ к памяти, заключаем, что сложность алгоритма равна O(n2). Отметим, что граф (рис. 1) является графом перехода между состояниями рассматриваемой ДДС. Будем обозначать его Г^. Покажем, как по графу Г^ представить множество кратчайших атак. R(0)-- ... -- R(t*^) Рис. 1 Сначала построим специальный граф, обозначаемый A(G). Будем считать, что в состоянии R(t*) M имеет права root на хосте Vt, поскольку в противном случае множество успешных атак пусто. Обозначим через t0, t0 ^ t*, момент, в который M получает право root на хосте Vt. Пусть I1,... , Id - стадии инициализации, пройденные алгоритмом до момента времени t0. Будем считать, что выходом стадии Id является множество вершин Qd, такое, что в окрестности некоторой вершины w G Qd находится вершина vT. Построим (d + 1)-дольный граф A(G). В доле с номером d +1 находится одна вершина Vt . В доле с номером d находятся вершины из Qd, смежные с Vt в графе G. Данное множество вершин обозначим Qd. В доле с номером r находятся вершины, смежные с вершинами из ПO+i, r = d - 1,..., 2. В доле с номером 1 графа A(G) находится одна вершина Vm . Определение 1. Пусть A - произвольная успешная атака. Назовём длиной A число функций вида f Е S (элементарных атак), значения которых были вычислены в процессе реализации A. Лемма 1. В рамках рассмотренной модели развития атак в сети G длина кратчайшей атаки равна 2d. Построим граф A* (G), который представляет все кратчайшие атаки в рамках рассматриваемой модели. Он строится на основе графа A(G): добавляем в граф A(G) дополнительные доли, в которых отображаются шаги из стадии переходов в новые состояния (стадия Т), которые совершаются между соседними стадиями инициализации. Данная информация берётся из соответствующих состояний регистра R. На рис. 2 приведены две соседние доли графа A(G) и соответствующий им фрагмент графа A*(G). Через Su, j Е {/ + 1,..., / + m}, обозначены списки элементарных атак, реализация которых (произвольной атаки из списка) приводит к получению M права user на хосте Vj . Аналогичный смысл (в отношении права root) имеет запись Sr (j Е {/ + 1,... , / + m}). Д(О) t+l t+2 t+3 A*(G) Рис. 2. Пример графов A(G) и A*(G) Теорема 1. В рамках рассмотренной модели развития атак в сети G граф, представляющий все кратчайшие атаки в сети, строится за время O(n2). Авторы благодарят рецензента за ряд конструктивных замечаний, учёт которых способствовал улучшению качества представляемого материала.

Скачать электронную версию публикации