Содержание к диссертации
Введение
1 Анализ существующих методов обнаружения вторжений 13
1.1 Основные понятия 13
1.2 Типовая структура СОВ 14
1.3 Методологии обнаружения вторжений 16
1.4 Обнаружение злоупотреблений 18
1.4.1 Сопоставление строк 18
1.4.2 Использование экспертных систем 19
1.4.3 Анализ переходов между состояниями 20
1.4.4 Методы добычи данных 21
1.5 Обнаружение аномалий 21
1.5.1 Статистические методы 21
1.5.2 Предсказание поведения 23
1.5.3 Методы добычи данных 24
1.5.4 Нейросетевые методы 24
1.5.5 Обнаружение аномалий в последовательностях системных вызовов... 26
1.6 Классификация СОВ 34
1.7 Цели и задачи исследования 36
1.8 Выводы 39
2 Разработка модели системы обнаружения вторжений на основе СММ 40
2.1 Сведения из теории СММ 40
2.1.1 Основные определения 40
2.1.2. Постановка типовых задач, связанных с СММ 43
2.1.3 Решение задачи оценивания 44
2.1.4 Решение задачи распознавания 45
2.1.5 Решение задачи обучения 46
2.1.6 Применение масштабирования в алгоритмах СММ 48
2.1.7 Решение задачи обучения для множественных последовательностей наблюдений 50
2.2 Принцип функционирования модели СОА 51
2.2.1 Общая схема СОА 51
2.2.2 Этапы функционирования системы 53
2.2.3 Выбор используемой подсистемы аудита 54
2.2.4 Формирование профиля нормального поведения процесса 55
2.2.5 Алгоритм обнаружения аномалий в работе процесса 57
2.3 Исследование возможности работы разработанной СОА в составе комплексной СОВ 60
2.4 Выводы 65
3 Экспериментальное исследование модели системы обнаружения вторжений 66
3.1 Описание тестовой базы данных 66
3.1.1 Обоснование выбора тестовой базы данных 66
3.1.2 Данные процесса 1рг 67
3.1.3 Данные процесса named 68
3.1.4 Данные процесса xlock 68
3.1.5 Данные процесса login 69
3.1.6 Данные процесса ps 69
3.1.7 Данные процесса inetd 70
3.1.8 Данные процесса stide 70
3.2 Иллюстрация работы алгоритма обнаружения аномалий на примере данных процесса named : 71
3.3 Исследование зависимости эффективности обнаружения вторжений от выбранного числа состояний СММ 73
3.3.1 Постановка задачи исследования 73
3.3.2 Процесс lpr 76
3.4 Обсуждение результатов экспериментов 80
3.5 Выводы 81
4 Разработка параллельного алгоритма обучения СММ 83
4.1 Известные решения по ускорению обучения СММ 83
4.2 Обоснование возможности эффективной организации параллельных вычислений в алгоритме обучения СММ 86
4.2.1 Анализ алгоритма обучения СММ для однократных последовательностей наблюдений 86
4.2.2 Анализ алгоритма обучения для многократных последовательностей наблюдений 88
4.3 Разработка параллельного алгоритма обучения СММ 90
4.4. Теоретическая оценка эффективности параллельного алгоритма 95
4.5 Особенности программной реализация параллельного алгоритма обучения СММ 97
4.5.1 Выбор средств реализации 97
4.5.2 Описание программной реализации 99
4.5.3 Экспериментальное подтверждение функционального соответствия параллельной и последовательной реализаций алгоритма обучения СММ. 104
4.6 Выводы 105
5 Экспериментальное исследование эффективности параллельного алгоритма обучения СММ 107
5.1 Условия проведения экспериментов 107
5.2 Исследование эффективности работы параллельного алгоритма обучения СММ на сетевом кластере 107
5.3 Исследование эффективности работы параллельного алгоритма обучения СММ на многопроцессорном кластере 112
5.4 Выводы 115
Заключение 116
Список использованных источников
- Методологии обнаружения вторжений
- Постановка типовых задач, связанных с СММ
- Обоснование выбора тестовой базы данных
- Обоснование возможности эффективной организации параллельных вычислений в алгоритме обучения СММ
Введение к работе
В связи с совершенствованием вычислительной техники и бурным ростом телекоммуникационных технологий, наблюдается повышение сложности используемого программного обеспечения. В таких условиях усложняется анализ разрабатываемых программ с точки зрения безопасности. По данным Национального института стандартов и технологий США (NIST), если количество зарегистрированных уязвимостей широко используемого программного обеспечения до 1996 года составляло десятки в год, то в 2004 году этот показатель достиг 2356, в 2005 году — 4914, и в 2006 — 6600 [1].
Рост числа уязвимостей программного обеспечения обуславливает актуальность не только таких превентивных мер противодействия, как использование межсетевых экранов и обманных систем, но также и внедрения систем обнаружения вторжений (СОВ), позволяющих активно противодействовать попыткам несанкционированного доступа. При этом очевидно, что со временем СОВ, целиком основанные на использовании пополняемых баз сигнатур известных вторжений, не будут способны гарантировать оперативное обнаружение вторжений, основанных на только что открытых уязвимостях.
В последнем выпуске ежегодного бюллетеня института SANS, отражающего десять наиболее важных тенденций в развитии информационной безопасности [2], прогнозируется дальнейший рост эксплуатации неизвестных ранее уязвимостей (0-day vulnerabilities), а также увеличение числа скомпрометированных узлов глобальной сети, позволяющих злоумышленникам осуществлять распределённые атаки и затруднять впоследствии поиск источника вторжения. В таких условиях актуальность приобретает развитие новых подходов к обнаруженшо вторжений, обеспечивающих своевременное обнаружение факта вторжения вне зависимости от наличия его точной сигнатуры.
Актуальность темы
Основной проблемой, с которой сталкиваются разработчики современных систем обнаружения вторжений (СОВ), является низкая эффективность существующих механизмов обнаружения принципиально новых видов вторжений, признаки которых не изучены и не занесены в базы данных сигнатур. Развитая в последние годы теория обнаружения аномалий, призванная решить эту проблему, не находит широкого применения из-за низкой надёжности используемых методов. Системы, построенные на основе этой теории, характеризуются недопустимо высоким уровнем ложных срабатываний.
В последнее время распространение получили более эффективные методы обнаружения вторжений, основанные на анализе последовательностей системных вызовов, поступающих к ядру операционной системы. Среди них одним из наиболее перспективных направлений является использование скрытых марковских моделей (СММ) для описания модели профиля нормального поведения того или иного процесса и обнаружения отклонений от этого профиля, свидетельствующих о возможном вторжении. Методы, основанные на использовании СММ, превосходят другие методы в эффективности обнаружения, однако требуют применения более трудоёмких алгоритмов [54, 63, 64].
Таким образом, задача исследования и совершенствования подхода к обнаружению вторжений с использованием СММ является актуальной.
Целью работы является разработка метода обнаружения вторжений на основе подхода, предполагающего использование СММ для описания профилей процессов. Разработанный метод позволяет уменьшить время обучения СММ для их более эффективного использования при решении задач обнаружения вторжений.
Исходя из основной цели данной работы, определяется перечень решаемых задач:
1) Разработать модель системы обнаружения вторжений.
2) Разработать алгоритмы формирования профилей нормального поведения процессов в виде СММ и обнаружения вторжений с их помощью.
3) Разработать параллельный алгоритм обучения для уменьшения времени обучения СММ.
4) Провести экспериментальное исследование и сравнительный анализ последовательного и параллельного алгоритма обучения СММ.
В рамках исследования используются методы теории вероятностей и математической статистики, математического моделирования, теории алгоритмов, теории параллельных вычислений. Широко применялось компьютерное моделирование, в том числе и с использованием самостоятельно разработанного программного обеспечения.
Основные результаты, выносимые на защиту
1) Модель СОВ, основанная на обнаружении аномалий в последовательностях системных вызовов, идущих от контролируемых процессов, использует профили нормального поведения контролируемых процессов в виде СММ. В основе модели лежит метод, позволяющий локализовать аномалию, вызванную вторжением, с точностью до системного вызова, основываясь на условной вероятности его возникновения.
2) Параллельный масштабируемый алгоритм обучения СММ для множественных последовательностей наблюдений, позволяющий проводить обучение СММ быстрее, чем широко используемый в настоящее время последовательный алгоритм Баума-Уэлча.
Научная новизна работы заключается в следующем: Разработан метод обнаружения вторжений, использующий профили нормального поведения контролируемых процессов в виде СММ. Метод позволяет локализовать аномалию, вызванную вторжением, с точностью до системного вызова, основываясь на условной вероятности его возникновения.
Разработан масштабируемый параллельный алгоритм обучения СММ для множественных последовательностей наблюдений, реализованный с помощью технологии MPI. Реализация параллельного алгоритма демонстрирует производительность близкую к теоретическому пределу даже при работе на недорогих сетевых кластерах, развёрнутых на вычислительных сетях типа Fast Ethernet.
Практическая значимость и внедрение результатов работы Практическая значимость результатов диссертации заключается в следующем:
- Разработана модель системы обнаружения вторжений, основанная на обнаружении аномалий в последовательностях системных вызовов, идущих от контролируемых процессов. Принципы, заложенные в систему, позволяют обнаруживать вторжения, признаки (сигнатуры) которых априорно не известны.
- Разработан параллельный алгоритм обучения СММ, позволяющий сократить время их обучения. Использование алгоритма возможно в других приложениях СММ, например, в распознавании речи, оптическом распознавании текста, генетике.
- Разработана параллельная программа быстрого обучения СММ, обеспечивающая производительность, близкую к теоретическому пределу даже при запуске на недорогих сетевых кластерах.
Основные результаты исследований использованы на кафедре «Безопасность информационных технологий» Технологического института Южного федерального университета в г. Таганроге при выполнении ряда научно-исследовательских и опытно-конструкторских работ для государственного заказчика, научных исследований, поддержанных грантом РФФИ, а также совместным грантом Министерства образования и науки Российской Федерации и Германской службы академических обменов (DAAD).
Достоверность полученных результатов подтверждается полнотой и корректностью теоретических обоснований и результатами экспериментов, проведенных с помощью разработанных в диссертации программ.
Публикации
По теме диссертации имеется 12 публикаций, из них 11 научных статей и тезисов докладов и одно свидетельство о регистрации программы для ЭВМ. Три статьи опубликованы в журнале «Известия Таганрогского государственного радиотехнического университета (ТРТУ)» за 2003-2005 гг. из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных работ.
Основные результаты работы докладывались и обсуждались на:
1) Международных научно-практических конференциях «Информационная безопасность», Таганрог, 2002, 2003, 2004 и; 2005 гг.
2) XXXIII региональной молодёжной конференции «Проблемы-теоретической и прикладной математики», Екатеринбург, 2002 г.
3) Конференциях профессорско-преподавательского состава Таганрогского государственного радиотехнического университета, Таганрог, 2004 и 2005 гг.
4) Семинаре стипендиатов программы «Михаил Ломоносов», Бонн (Германия), 2005 г.
5) Международной конференции «Информатика и информационные технологии» ("Computer Science and Information Technologies"), Карлсруэ (Германия), 2006 г.
Структура и объем диссертации
Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников (113 наименований) и приложения. Общий объем работы - 158 страниц. В работе приведен графический материал в объеме 19 рисунков, содержится 28 страниц приложений.
Содержание работы
Во введении кратко рассматривается актуальность работы, цели и основные задачи, научная новизна и практическая ценность работы.
В первой главе представлены основные сведения из теории СММ, позволяющие разработать алгоритмы обучения и обнаружения, используемые в разрабатываемой модели СОВ. Описана общая структура модели; разработаны алгоритмы формирования профилей поведения процессов в виде СММ и обнаружения вторжений с их помощью.
Во второй главе представлены основные сведения из теории скрытых марковских моделей, позволяющие разработать алгоритмы обучения и обнаружения, используемые в исследуемой модели системы обнаружения вторжений. Описана общая структура разрабатываемой модели системы, разработаны алгоритмы формирования профилей поведения процессов в виде скрытых марковских моделей и обнаружения вторжений с их помощью. В третьей главе описана тестовая база данных последовательностей системных вызовов, используемая во всех проведённых экспериментах. Проиллюстрована способность разработанного алгоритма обнаружения вторжений обнаруживать атаку на переполнение буфера без априорного знания её сигнатуры. Приведены результаты исследования зависимости показателей эффективности обнаружения вторжений от выбранного числа состояний СММ. Установлено, что процесс обучения СММ зачастую сходится к локальному минимуму целевой функции. Этот факт ещё более усложняет процесс обучения, так как возникает дополнительная необходимость поиска значения числа состояний, обеспечивающего необходимые уровни вероятностей правильного обнаружение и ложного срабатывания. Таким образом, задача сокращения времени обучения СММ становится ещё более актуальной.
Четвёртая глава посвящена разработке и реализации параллельного алгоритма обучения скрытых марковских моделей для множественных последовательностей наблюдений. В главе приведено краткое описание попыток быстрой реализации классического алгоритма обучения, проанализированы недостатки этих решений для использования в исследуемой системе обнаружения аномалий (СОА). На основе анализа возможности эффективной декомпозиции стандартного алгоритма обучения СММ разработан параллельный алгоритм их обучения; приводится описание реализации параллельного алгоритма на основе технологии MPI.
В пятой главе исследована эффективность параллельного алгоритма обучения СММ. Показано, что он может быть реализован на недорогих сетевых кластерах, а также на многопроцессорных кластерах, с ускорением близким к предельно возможному теоретически.
В заключении излагаются основные результаты диссертационной работы, полученные в процессе проводимых исследований, делаются общие выводы.
В приложении приведены листинги программных модулей.
Методологии обнаружения вторжений
Рассмотрим наиболее общие методологии, которые могут быть положены в основу работы подсистем анализа СОВ. Выход в 1987 году работы Деннинг [7] положил начало появлению двух основных направлений в развитии обнаружения вторжений — обнаружению злоупотреблений и обнаружению аномалий.
Методология обнаружения злоупотреблений основывается на допущении, что вторжения могут быть описаны некоторым шаблоном или сигнатурой, способной учитывать возможные незначительные отклонения. Эта методология аналогична базовому принципу действия современных антивирусных систем, основным компонентом которых является база вирусных сигнатур, требующая постоянного пополнения для поддержания возможности обнаружения новых вирусов.
Системы обнаружения злоупотреблений содержат чётко определённые характеристики обнаруживаемых вторжений и ищут их в данных аудита, используя относительно простые и эффективные методы. Уровень ложных срабатываний в современных системах обнаружения злоупотреблений, как правило, весьма близок к нулю.
С другой стороны, разработка сигнатур для систем обнаружения злоупотреблений является трудоёмкой операцией, требующей высокой квалификации персонала, который её выполняет. В зависимости от того насколько правильно была описана сигнатура, некоторые варианты реализации того же вторжения могут быть пропущены системой. Разумеется, подходы к обнаружению злоупотреблений имеют весьма ограниченные возможности обобщения тех знаний, которые они содержат. Поэтому обнаружение новых разновидностей вторжений системами обнаружения злоупотреблений является скорее исключением, чем правилом.
Методология обнаружения аномалий исходит из предположения, что любые вторжения ведут к возникновению аномалий в работе системы. То есть если возможно некоторыми средствами описать профиль системы, теоретически можно обнаруживать существенные отклонения от него и сигнализировать о возможной попытке вторжения. Из того факта, что вторжения и аномалии не всегда возникают одновременно, очевидны два основных недостатка принципа обнаружения аномалий: 1) аномальная активность, не вызванная попыткой вторжения, может привести к ложному срабатыванию; 2) вторжение, не вызывающее заметных отклонений в значениях отслеживаемых параметров, может быть не обнаружено. В то же время, обнаружение аномалий имеет одно существенное преимущество перед обнаружением злоупотреблений: с его помощью можно обнаруживать новые разновидности вторжений, не содержащие в своей структуре ранее исследованные сигнатуры.
Основным достоинством систем обнаружения аномалий является отсутствие необходимости периодической перенастройки со стороны оператора: система обнаружения аномалий автоматически изучает поведение некоторого набора субъектов и способна функционировать самостоятельно. Поскольку она не опирается на какие-либо знания о том, как проявляется то или иное вторжение, у неё есть возможность обнаруживать как принципиально новые разновидности вторжений, так и необычные варианты реализации известных вторжений.
Основной недостаток систем обнаружения аномалий заметен в самом определении. Система обнаружения аномалий выявляет признаки необычного поведения, а не явно злонамеренных действий. Это может быть существенной проблемой, если эти две разновидности поведения не проявляются одновременно и не находятся в рамках одной причинно-следственной связи. Кроме того, если система постоянно обновляет профиль нормального поведения субъекта в процессе работы, субъект в ряде случаев может постепенно «приучить» систему к злонамеренному поведению, начав с абсолютно нормального режима работы и постепенно двигаясь к реализации вторжения. Также современные подходы к обнаружению аномалий, как правило, не позволяют произвести даже минимальную классификацию вторжения, а лишь констатируют факт его наличия.
Рассмотрим известные методы обнаружения злоупотреблений и аномалий более подробно.
Постановка типовых задач, связанных с СММ
С СММ связаны следующие типовые задачи.
1) Задача оценивания. Дана СММ X и последовательность наблюдений О. Требуется найти вероятность, что последовательность О будет сгенерирована моделью X (найти Р(0 X)).
2) Задача распознавания. Дана последовательность наблюдений О = Оь о2з... от и СММ X (О є (Ух) ). Необходимо установить наиболее вероятную последовательность состояний, которую проходила модель при генерации данной последовательности наблюдений.
3) Задача обучения. Дана СММ X и последовательность наблюдений О. Необходимо подстроить параметры А, В и П модели таким образом, чтобы максимально повысить вероятность генерации последовательности О в процессе дальнейших серий наблюдений.
Рассмотрим решение задачи оценивания. Принимая во внимание формулу (2.5) можно получить следующее выражение для расчёта вероятности генерации последовательности наблюдений заданной моделью. Р(01 Я) = 2 Р(01 2Д)Д 21 Я) = 2ХД_ {0,)ambqi (02)- -а Х (От) (2.8) Q Q
Необходимо отметить, что в выражении (2.8) суммирование производится по всем возможным цепочкам Q. Поэтому трудоёмкость нр вычисления вероятности напрямую составляет 0(TN ). На практике для вычисления вероятности используется следующий рекуррентный алгоритм, называемый алгоритмом прямого хода (forward algorithm), трудоёмкость которого составляет 0(TN ). Для алгоритма прямого хода вводится следующая специальная переменная: at (і) = Р(0{02 Ot,qt=si\A,) — совместная вероятность наблюдения частичной последовательности О], 02,... Ot и нахождения модели в момент времени t в состоянии S;. Её расчёт производится по следующей рекуррентной схеме: 1) Инициализация: СС\ (0 = nf)i (о}) (2.9); 2) Индукция: ос,+х (у) /=1 bj(ot+l) (2.10). После того, как сформирован последний столбец матрицы а, можно вычислить итоговую вероятность Р(0\Х), просуммировав его элементы. N N P{0\Z) = YJp(0\qT=si) = Y XT( ) (2.11). /=1 /=i
Приведём также аналогичный алгоритм обратного хода (backward algorithm), который будет необходим для решения задачи обучения СММ. Он выражается следующими двумя формулами: 1) Инициализация /?г(0-1 (2.12); N M0 = Zaffbj(ol+l)/?MU) 2) Индукция /=1 (2.13); Задача распознавания в теории СММ решается по рекуррентному алгоритму Витерби: 1) Инициализация 4(i) = A( i ),!/ # ,(/) = 0 2) Рекурсия St(i) = bi(ol)max{S!__l(j)aJi;j = h.N\,l i N,2 t T V, l(i) = argmax{Sl_l(j)aJi;j = l..N},\ i N,2 t T 3) Завершение Р{01 Я) = max{ST (г); / = 1 ..N] qT = argmax{ r(/); і = 1. JV) 4) Обратный проход Я =Hq +i) t = T-1,..,1
Полученный вектор Q ={qi ,.--,Чт } — наиболее вероятная последовательность состояний, которые проходила модель А, в процессе генерации последовательности наблюдений О.
Третья задача решается по алгоритму Баума-Уэлча. Для его реализации используется вспомогательная величина t(i, j), характеризующую вероятность нахождения СММ в состоянии s, в момент времени t и в состоянии Sj в момент времени t+І при заданной модели X и последовательности наблюдений О: 0",У ) = P{qt = s„ql+i = S; \0,Я).
Если для момента времени t известны все значения ott(i), а для момента t+1 — все значения p\+i(j), то можно вычислить соответствующие значения t(i, j) по формуле
Другой вспомогательной величиной, используемой при обучении СММ, ЯВЛЯеТСЯ ВерОЯТНОСТЬ НаХОЖДеНИЯ В МОМеНТ Времени t В СОСТОЯНИИ Sj при заданной последовательности наблюдений и модели: yt(i) = P(qt = Sj О, А,). Используя переменные прямого и обратного хода, можно вычислить величину у следующим образом: Л1 т . „ч N Р(0\Я) r,fln (2.15) У=1
С помощью переменных и у можно провести переоценку параметров СММ следующим образом: Я{=Г,(?) (2.16); т-\ Е ?,(и а„ - /=1 4 й /л (2Л7); І ,(у) (=1 DjKK)- т (2.18). /=i Баум и Селл [72] доказали, что после проведения такого преобразования для модели Я будет справедливо одно из следующих утверждений: 1) Р(01Я) Р(0\Я); 2) Я=Я. Второе выражение справедливо только если значения коэффициентов модели А, соответствуют локальному максимуму функции Р(0Х,). Таким образом, процедура обучения СММ заключается в последовательном выполнении итерации, включающей алгоритмы прямого и обратного хода (2.9)-(2.13), расчёт величин yt(i) (2.14) и t(i,j) (2.15) и обновление значений коэффициентов А, В и п (2.16)-(2.18).
Условием остановки обучения является приближение обучаемой СММ к локальному максимуму вероятности генерации требуемой последовательности наблюдений. Признаком этого приближения может быть момент, когда разность между значением целевой функции Р(0Я,) на очередной и на предыдущей итерации оказывается меньше заранее выбранного и близкого к нулю порогового значения. Поскольку в формулах (2.16)-(2.18) элементам СММ присваиваются нормированные значения, то после выполнения каждой итерации вновь полученная модель автоматически сохраняет необходимые свойства СММ (2.1)-(2.4), (2.6), (2.7).
Необходимо отметить, что обучение СММ по алгоритму Баума-Уэлча приводит модель только к ближайшему локальному максимуму целевой функции. В реальных практических задачах таких локальных максимумов может быть достаточно много.
Обоснование выбора тестовой базы данных
Подсистема сбора данных, необходимая в рамках рассматриваемого подхода, должна перехватывать все системные вызовы от анализируемого процесса к ядру операционной системы. Для решения этой задачи могут быть использованы различные средства, реализующие эту функцию, например, стандартные системы аудита, утилиты перехвата системных вызовов, модули ядра.
Примером стандартной системы аудита, реализующей перехват системных вызовов, является Basic Security Module (BSM) ОС Solaris [73] или его аналоги для POSIX/BSD/Linux-совместимых ОС — LinuxBSM [74] и OpenBSM [75]. BSM был добавлен в ОС Solaris, начиная с версии 2.5, для перевода её из класса защищённости СІ в класс С2 согласно критериям оценки доверенной компьютерной системы министерства обороны США [76]. Основным предназначением BSM является сбор информации для её последующего избирательного анализа системным администратором и расследования имевших место нарушений политики безопасности. Недостатком применения BSM для решения рассматриваемой задачи является тот факт, что она генерирует множество избыточной информации, при этом используя значительные вычислительные ресурсы.
В состав дистрибутивов UNIX-подобных операционных систем, как правило, входит специализированная утилита strace, позволяющая осуществлять перехват системных вызовов как в запускаемых программах, так и в уже работающих процессах. Недостатком применения утилиты strace в рассматриваемой системе является тот факт, что она оказывает влияние на работу процесса, за которым наблюдает, и даже может нарушить его функциональность [70].
Таким образом, наиболее обоснованным решением для реализации сбора исходной информации в разрабатываемой системе является специализированный модуль ядра, осуществляющий перехват системных вызовов. Из известных решений можно использовать BSM для ОС Solaris или LinuxBSM для ОС семейства GNU/Linux, предусмотрев фильтрацию избыточных данных, например, с помощью стандартной утилиты grep.
Профиль нормального поведения процесса формируется следующим образом. Пусть имеется множество последовательностей системных вызовов
U-{(J ,U ,---,и )з элементы которого V —\и\ - иі UTk ), в
достаточной степени характеризующих нормальное поведение анализируемого процесса. Необходимо отметить, что размерность элементов О может быть как различной [58], так и одинаковой [27, 54].
В первом случае система аудита может формировать последовательности с момента старта процесса до момента его завершения. Такой подход более применим для СОА, к которым не предъявляются требования оперативного реагирования, т.е. к тем, которые используются для облегчения расследования уже случившихся инцидентов.
Во втором случае система аудита будет разбивать весь поток системных вызовов на кадры фиксированной длины. При этом построенная база будет лучше подходить для использования в системах реального времени, в особенности при длине кадра порядка нескольких единиц.
Далее в собранных последовательностях отбрасываются аргументы системных вызовов, а сами они кодируются порядковыми номерами. Множество полученных цепочек номеров затем используются при обучении смм.
Перед обучением СММ необходимо инициализировать её весовые коэффициенты. Поскольку процедура обучения СММ относится к методам градиентного поиска, она нацелена на нахождение локального максимума функции Р(0Л,). Таким образом, от инициализации значений элементов А, В и тс зависит качество обучения, то есть конечная настройка коэффициентов СММ и соответствующее ей значение Р(0Я,). В [71] констатируется, что при решении практических задач не существует какого-либо универсального подхода к инициализации СММ, в особенности для элементов матрицы А и вектора л, поэтому обычно элементы А, В и ті инициализируются равномерно распределёнными случайными величинами с сохранением свойств нормирования (2.2), (2.4) и (2.7). В ряде случаев удаётся построить эвристические процедуры инициализации элементов матрицы В, позволяющие повысить вероятность попадания в глобальный максимум целевой функции. В частности в [54] при обнаружении аномалий в работе процесса 1рг в СММ выделяются два специальных состояния для описания характерного длительного чередования системных вызовов read-write. В итоге, отношение экспериментальной оценки вероятности ложного срабатывания для СММ, инициализированной специальным образом, к такой же вероятности для СММ, полностью инициализированной псевдослучайными числами, достигает значения 0,5.
Непосредственно обучение инициализированной СММ производится по алгоритму Баума-Уэлча для множественных последовательностей наблюдений с использованием множества О в качестве набора символов наблюдения. Сформированная таким образом СММ представляет собой модель профиля поведения процесса, в работе которого будет производиться обнаружение аномалий.
Обоснование возможности эффективной организации параллельных вычислений в алгоритме обучения СММ
Проанализируем алгоритм обучения СММ с точки зрения возможности его распараллеливания. Для этого приведём алгоритм Баума-Уэлча для однократных последовательностей наблюдений в виде блок-схемы на рисунке 4.2.
Блоки 2 и 3 на рисунке 4.2 включают достаточно трудоёмкие рекурсивные вычисления. В частности, в алгоритме прямого хода первоначально вычисляются элементы первого столбца, а затем элементы последующих столбцов, зависящие от предыдущих столбцов. Таким образом, существует зависимость по данным между последующей и предыдущей итерациями алгоритма прямого хода. Алгоритм обратного хода обладает таким же свойством, только зависимость по данным прослеживается от последних столбцов матрицы 3 к первым. Наличие такой жёсткой зависимости по данным делает невозможной эффективную организацию параллельных вычислений внутри блоков 2 и 3.
Способ распараллеливания, при котором одновременно выполнялись бы блоки 2 и 3 также неосуществим, поскольку для работы алгоритма обратного хода с масштабированием необходимо знать значения масштабных коэффициентов, для расчёта которых, в свою очередь, необходимо выполнение алгоритма прямого хода.
Анализируя дальнейшие шаги алгоритма, можно отметить, что параллельное выполнение блоков 4 и 5 возможно, поскольку между этими этапами нет никаких зависимостей по данным. Однако, исходя из формул (2.14) и (2.15), можно оценить трудоёмкость блока 4 как 0(N Т), а блока 5 как 0(NT). Это означает, что при подобном параллельном выполнении расчёт матрицы у, как правило, будет заканчиваться существенно раньше расчёта массива ,. Экспериментальные данные профилирования программной реализации подтвердили это предположение. Такая несогласованность во времени выполнения блоков 4 и 5 приводит к длительным простоям вычислительных ресурсов, что значительно ограничивает эффективность распараллеливания таким способом.
На основании вышеизложенных соображений, можно прийти к выводу о невозможности эффективной организации распараллеливания алгоритма обучения СММ для однократных последовательностях наблюдений. Рассмотренные варианты распараллеливания при решении практических задач могут обеспечить сокращение времени обучения не более чем на несколько процентов.
Рассмотрим теперь возможность распараллеливания алгоритма обучения СММ при использовании множественных последовательностей наблюдений. Приведём блок-схему последовательного алгоритм обучения СММ для множественных последовательностей наблюдений на рисунке 4.3.
Приведённый алгоритм принципиально отличается от алгоритма для однократных последовательностей наблюдений наличием внутреннего цикла по отдельным последовательностям, включающего блоки 3-8. Необходимо отметить, что задача, рассматриваемая в данной работе, характеризуется большим количеством обучающих последовательностей и их большой длиной. В таких условиях цикл от блока 3 до блока 8 будет выполняться значительно дольше блока 9.
Перечислим данные, используемые и модифицируемой каждой итерацией цикла 3-8:
а) текущие значения параметров обучаемой СММ (А, В и %) используются в процессе вычислений, но до передачи управления блоку 9 не модифицируются;
б) итерация с номером к использует только одну уникальную последовательность наблюдений Ok из обучающей выборки;
в) каждая итерация модифицирует только относящиеся к ней вспомогательные переменные ак, рк, ук, ,к.
Перечисленные выше факты позволяют прийти к идее декомпозиции рассматриваемого алгоритма обучения, необходимой для эффективной организации распараллеливания.
