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

На правах рукописи

Аникеев Максим Владимирович

РАЗРАБОТКА АЛГОРИТМИЧЕСКИХ И ПРОГРАММНЫХ СРЕДСТВ, ПОВЫШАЮЩИХ ЭФФЕКТИВНОСТЬ ОБНАРУЖЕНИЯ ВТОРЖЕНИЙ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ СКРЫТЫХ МАРКОВСКИХ МОДЕЛЕЙ

05 13 19 - Методы и системы защиты информации, информационная безопасность

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

2 2 СЕН 2003

Таганрог 2008

003446699

Работа выполнена в Технологическом институте Южного федерального университета в г Таганроге на кафедре «Безопасность информационных технологий»

НАУЧНЫЙ РУКОВОДИТЕЛЬ

доктор технических наук, профессор Макаревич Олег Борисович

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ

доктор технических наук, профессор

Аграновский Александр Владимирович (г Ростов-на-Дону) кандидат технических наук

Дордопуло Алексей Игоревич (г Таганрог)

ВЕДУЩАЯ ОРГАНИЗАЦИЯ

ФГУП Концерн «Системпром» (г Москва)

Защита диссертации состоится «3» октября 2008 г в 14 20 на заседании диссертационного совета Д 212 208 25 Южного федерального университета по адресу 347928, Ростовская область, г Таганрог, ул Чехова, 2, ауд И-419

Отзывы на автореферат просьба направлять по адресу 347928, Ростовская область, г Таганрог, пер Некрасовский, 44, Технологический институт Южного федерального университета в г Таганроге, Ученому секретарю диссертационного совета Д 212 208 25 Брюхомицкому Ю А

С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу 344007, Ростовская область, г Ростов-на-Дону, ул Пушкинская, 148

Автореферат разослан «2» сентября 2008 г

Ученый секретарь диссертационного совета, кандидат технических наук, доцент

Брюхомицкий Ю А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность.

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

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

Таким образом, задача исследования и совершенствования подхода к обнаружению вторжений с использованием СММ является актуальной

Целью работы является разработка метода обнаружения вторжений на основе подхода, предполагающего использование СММ для описания профилей процессов Разработанный метод позволяет уменьшить время обучения СММ для их более эффективного использования при решении задач обнаружения вторжений

Для достижения указанной цели необходимо решить следующие задачи

1 Разработать модель системы обнаружения вторжений

2 Разработать алгоритмы формирования профилей нормального поведения процессов в виде СММ и обнаружения вторжений с их помощью

3 Разработать параллельный алгоритм обучения для уменьшения времени обучения СММ

4 Провести экспериментальное исследование и сравнительный анализ последовательного и параллельного алгоритма обучения СММ

Методы исследования основаны на использовании теории вероятностей и математической статистики, математического моделирования, теории алгоритмов, теории параллельных вычислений Широко применялось компьютерное моделирование, в том числе и с использованием самостоятельно разработанного программного обеспечения

Основные результаты, выносимые на защиту

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

2 Параллельный масштабируемый алгоритм обучения СММ для множественных последовательностей наблюдений, позволяющий проводить обучение СММ быстрее, чем широко используемый в настоящее время последовательный алгоритм Баума-Уэлча

Научная новизна работы заключается в следующем

1 Разработан метод обнаружения вторжений, использующий профили нормального поведения контролируемых процессов в виде СММ Метод позволяет локализовать анома-

лию, вызванную вторжением, с точностью до системного вызова, основываясь на условной вероятности его возникновения

2 Разработан масштабируемый параллельный алгоритм обучения СММ для множественных последовательностей наблюдений, реализованный с помощью технологии MPI Реализация параллельного алгоритма демонстрирует производительность близкую к теоретическому пределу даже при работе на недорогих сетевых кластерах, развернутых на вычислительных сетях типа Fast Ethernet

Практическая ценность работы.

Практическая значимость результатов диссертации заключается в следующем

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

2 Разработан параллельный алгоритм обучения СММ, позволяющий сократить время их обучения Использование алгоритма возможно в других приложениях СММ, например, в распознавании речи, оптическом распознавании текста, генетике

3 Разработана параллельная программа быстрого обучения СММ, обеспечивающая производительность, близкую к теоретическому пределу даже при запуске на недорогих сетевых кластерах

Использование результатов. Основные результаты исследований использованы на кафедре «Безопасность информационных технологий» .Технологического института Южного федерального университета в г Таганроге при выполнении ряда научно-исследовательских и опытно-конструкторских работ для государственного заказчика, научных исследований, поддержанных грантом РФФИ, а также совместным грантом Министерства образования и науки Российской Федерации и Германской службы академических обменов (DAAD)

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

Апробация работы Основные результаты, полученные в ходе работы над диссертацией, были представлены на

1 Международных научно-практических конференциях «Информационная безопасность», Таганрог, 2002,2003,2004 и 2005 гг

2 XXXIII региональной молодежной конференции «Проблемы теоретической и прикладной математики», Екатеринбург, 2002 г

3 Конференциях профессорско-преподавательского состава Таганрогского государственного радиотехнического университета, Таганрог, 2004 и 2005 гг

4 Семинаре стипендиатов программы «Михаил Ломоносов», Бонн (Германия), 2005 г

5 Международной конференции «Информатика и информационные технологии» ("Computer Science and Information Technologies"), Карлсруэ (Германия), 2006

Публикации. По теме диссертации имеется 12 публикаций, из них 11 научных статей и тезисов докладов и одно свидетельство о регистрации программы для ЭВМ Три статьи опубликованы в журнале «Известия Таганрогского государственного радиотехнического университета (ТРТУ)» за 2003-2005 гг из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных работ

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

объём работы - 158 страниц. В работе приведен графический материал в объеме 19 рисунков, содержится 28 страниц приложений.

СОДЕРЖАНИЕ РАБОТЫ

Во введении кратко рассматривается актуальность работы, цели и основные задачи, научная новизна и практическая ценность работы.

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

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

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

Процесс 1

Процесс 2

Ядро ОС

-и БД • примеров j

</

Модуль д. ----- Модуль Л —--------

реагирования обнаружения

БД моделей

Модуль обучения СММ

ь--

Журнал событий

Рисунок 1 — Общая структура предлагаемой модели СОА

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

Функционирование системы включает два этапа: обучение и обнаружение. Целью этапа обучения является сбор в базе данных примеров максимально полной и в то же время

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

Наиболее обоснованным решением для реализации сбора исходной информации в разрабатываемой системе является специализированный модуль ядра, осуществляющий перехват системных вызовов Из известных решений можно использовать BSM для ОС Solaris или LinuxBSM для ОС семейства GNU/Linux

Профиль нормального поведения процесса формируется следующим образом Пусть имеется множество последовательностей системных вызовов О = {0<'),0(2,, ,0<к'}, элементы которого О'*' = {0\к) ,Of\- ,0'тк]), в достаточной степени характеризующих нормальное поведение анализируемого процесса Непосредственно обучение инициализированной СММ производится по алгоритму Еаума-Уэлча для множественных последовательностей наблюдений с использованием множества О в качестве набора символов наблюдения Сформированная таким образом СММ представляет собой модель профиля поведения процесса, в работе которого будет производиться обнаружение аномалий

Алгоритм обнаружения аномалий основан на сопоставлении профиля нормального поведения процесса, представленного в виде СММ, с данными о работе этого процесса в течение рассматриваемого промежутка времени Пусть дана СММ X = (А, В, ж), где А — матрица вероятностей переходов между состояниями, В — матрица вероятностей появления символа наблюдения в зависимости от текущего состояния, ил — вектор начального распределения вероятностей состояний СММ "к описывает нормальное поведение некоторого процесса Пусть дана также последовательность номеров системных вызовов (символов наблюдений) О = (oí, Ог, , От) В качестве критерия, характеризующего степень соответствия того или иного символа наблюдения в последовательности нормальному поведению, предлагается выбрать величину с,"1 = Р(о, | X, Оц, о,2, , о,) Эта величина обратна соответствующему масштабному коэффициенту с,, вычисляемому в процессе работы алгоритма прямого хода с масштабированием, известного по классическим работам теории СММ

Признаком несоответствия появления в последовательности наблюдений символа Ot нормальному поведению является значение соответствующей величины с,'1 ниже определенного порога с Этот порог может быть вычислен экспериментально как разграничитель между интервалом, содержащим характеристики известных нормальных переходов от предыдущих системных вызовов к последующим, и интервалом, содержащим такие же характеристики аномальных переходов В случае если эти интервалы пересекаются, выбор того или иного конкретного значения классифицирующего порога обусловлен изначально закладываемыми в систему оценками максимально допустимых вероятностей ложного пропуска и ложного срабатывания Алгоритм обнаружения аномалий позволяет рассматривать каждый системный вызов индивидуально, что обеспечивает принципиальную возможность реагирования на аномальный вызов еще до его поступления к ядру ОС Иными словами, алгоритм может быть использован не только в составе СОВ пакетной, но и непрерывной обработки, обеспечивая возможность своевременного реагирования

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

возможность применения разработанного метода обнаружения аномалий в возможной структуре комплексной СОВ

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

Таким образом, разработанный метод обнаружения аномалий можно использовать в комплексе с произвольной системой обнаружения злоупотреблений уровня узла, анализирующей системные вызовы Такая комплексная СОВ может испочьзовать единую систему аудита, причем на вход модуля обнаружения злоупотреблений целесообразно подавать весь объем поступающих данных, а на вход модуля обнаружения аномалий — системные вызовы без учета их аргументов При использовании д рамках комплексной СОВ модулей обнаружения аномалий и модуля обнаружения злоупотреблений возникает необходимость агрегации сообщений от этих двух источников, анализа динамики и выявления типовых сценариев вторжений Агрегация и корреляция событий необходима для устранения традиционных недостатков обнаружения злоупотреблений и обнаружения аномалий

Учитывая изложенные выше соображения, сформулируем общий алгоритм функционирования комплексной СОВ (рисунок 2)

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

Фильтрация

аргументов

системных вызовов

I

Сравнение с

профилем • виде

СММ

} До принудительной ! > остановки основной [

с

Л /

Рисунок 2 — Общий алгоритм функционирования комплексной СОВ

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

В третьей главе приведены результаты исследования зависимости показателей эффективности обнаружения вторжений от выбранного числа состояний СММ Установлено,

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

Для экспериментального исследования метода обнаружения аномалий был использован набор данных, содержащий последовательности системных вызовов и собранный группой компьютерных иммунных систем факультета информатики университета Нью-Мексико (UNM) с использованием данных лаборатории искусственного интеллекта Массачусетского технологического института (MIT) Набор содержит последовательности системных вызовов, полученные в процессе мониторинга программ различных классов (в частности, как работающих длительно в режиме «демона», так и запускаемых на короткое время) Программы также подвергались воздействию различных видов вторжений, таких как переполнение буфера, атака через символическую ссылку, троянский код В основном, были проанализированы программы, запускаемые в режиме сервера, как наиболее распространенные цели вторжений Частично информация была собрана на специализированных стендах, частично — в процессе штатной эксплуатации программ

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

Среди изложенных сценариев вторжений, представленных в тестовых данных, наиболее сильные изменения в последовательностях системных вызовов, должны содержаться в данных процесса named, реализующего службу сервера доменных имен Переполнение буфера, отраженное в этих данных, вызывает переход к выполнению кода злоумышленника, который содержит действия, ранее не известные по обучающей выборке Разделим последовательности системных вызовов, собранные в нормальном режиме работы процесса named на обучающую выборку и нормальную тестовую выборку Если обучить СММ по алгоритму Баума-Уэлча, используя обучающую выборку, можно ожидать, что найдутся такие системные вызовы в аномальной тестовой выборке, для которых разработанный алгоритм обучения аномалий будет выдавать необычно низкие оценки вероятности их появления, не характерные для нормальной тестовой выборки

На рисунке 3 приведены графики зависимости условной эмпирической вероятности появления текущего системного вызова от его номера в последовательности (в терминах СММ — зависимости эмпирической вероятности генерации моделью символа наблюдения от дискретного времени) для имеющихся нормальных и аномальных данных процесса named Для лучшей наглядности на графике отражены не все значения, а только минимальные из каждых десяти соседних

На рисунке 3 график «norm» отражает эмпирические вероятности для нормальных данных, серия точек «anom 1 » и «anom2» — для данных атаки переполнения буфера В качестве модели профиля нормального поведения была использована СММ с числом состояний равным 10, обученная по алгоритму Баума-Уэлча Точки, наиболее наглядно свидетельствующие о признаках аномальной ситуации, обведены пунктирной линией Отметим, что даже однократная эксплуатация уязвимости переполнения буфера приводит к появлению как минимум шести аномальных значений, выдаваемых СММ, обученной на данных о нормальном поведении процесса named При этом аналогичные значения для нормальных данных, не принадлежащих обучающей выборке, даже в худшем случае превосходят аномаль-

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

Рисунок 3 — Графики зависимости условной эмпирической вероятности появления текущего системного вызова от его номера в последовательности (для нормальных и аномальных

данных процесса named)

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

Целью экспериментов, описанных далее, является поиск методологии выбора минимального числа состоянии СММ, обеспечивающего обнаружение вторжений с некоторой изначально выбранной степенью надёжности. Эмпирической вероятностью пропуска вторжения или FNR (от англ. "False Negative Rate") мы будем называть отношение числа последовательностей системных вызовов, содержащих аномалии и распознанных COA как аномальные, к общему числу аномальных последовательностей. Эмпирической вероятностью ложного срабатывания или FPR (от англ. "False Positive Rate") обозначим отношение числа системных вызовов, принадлежащих нормальным последовательностям, но классифицированных COA как аномальные, к общему числу системных вызовов, содержащихся в нормальных последовательностях.

Ранее была приведена методика расчета величины, характеризующей степень соответствия того или иного символа наблюдения (системного вызова) в последовательности нормальному поведению процесса в данный момент, то есть P(ot | X, о,.ь ot.2.....оО- В дальнейшем мы будем называть эту величину неаномальностью. Пороговое значение неаномальности, ниже которого лежат значения, классифицируемые COA как аномалии, а выше — как норма, будем называть классифицирующим порогом. Выбор классифицирующего порога обеспечивает некоторое компромиссное сочетание вероятности пропуска вторжения и вероятности ложного срабатывания.

Результаты проведенных экспериментов по оценке FNR и FPR для разработанного метода обнаружения аномалий в целом соответствуют данным, изложенным в публикациях, посвященных использованию СММ для обнаружения аномалий в системных вызовах Основной проблемой, выявленной в процессе исследования зависимости FNR и FPR от выбранного числа состояний СММ, является частое попадание параметров СММ в локальные максимумы целевой функции в процессе обучения Это явление значительно затрудняет априорную оценку числа состояний, достаточного для обеспечения требуемого уровня FNR и FPR

Если бы при увеличении числа состояний экспериментальные FNR и FPR монотонно убывали, то оптимальное число состояний можно было бы найти достаточно быстро, начав эксперименты для СММ с небольших значений числа состояний и экстраполировав получающиеся кривые до требуемых значений Поскольку в реальности у экспериментальных кривых FNR и FPR наблюдаются значительные отклонения от монотонного убывания, наилучшим решением для поиска достаточного числа состояний будет, по-видимому, перебор возможных значений до тех пор, пока FNR и FPR ни достигнут требуемого уровня

Такая процедура поиска числа состояний имеет преимущество перед эвристическим выбором этого числа, изложенным в публикациях Поскольку входными данными для поиска являются требуемые значения FNR и FPR, не исключено, что в ряде случаев удастся найти меньшее число состояний, чем согласно известной эвристике, тем самым, снизив трудоемкость собственно процедуры обнаружения аномалий, и как следствие, снизить потерю производительности вычислительного узла из-за использования COA В то же время, применение известной эвристики может не обеспечить требуемых уровней FPR и FNR Тогда поиск достаточного числа состояний необходимо проводить уже в сторону увеличения, начиная от значения, предсказанного эвристикой

Таким образом, проведенные эксперименты демонстрируют, что выбор числа состояний СММ для решения поставленной задачи обнаружения аномалий с заданными характеристиками является нетривиальной проблемой и не может быть в настоящий момент решен при помощи универсального алгоритма или метода Введение процедуры поиска оптимального числа состояний делает создание СММ для COA еще более трудоемким, чем обычное обучение по алгоритму Баума-Уэлча Кроме того, выявленное частое попадание СММ в локальные максимумы целевой функции обуславливает проведение многократного обучения СММ с одинаковым числом состояний, но разными случайными начальными настройками, с последующим выбором наилучшего варианта Все эти факты дополнительно обуславливают актуальность разработки быстрого алгоритма обучения СММ в контексте поставленной задачи В следующей главе для решения этой проблемы предлагается параллельный алгоритм обучения СММ

Четвертая пава посвящена разработке и реализации параллельного алгоритма обучения скрытых марковских моделей для множественных последовательностей наблюдений В главе приведено краткое описание попыток быстрой реализации классического алгоритма обучения, проанализированы недостатки этих решений для использования в исследуемой COA На основе анализа возможности эффективной декомпозиции стандартного алгоритма обучения СММ разработан параллельный алгоритм их обучения, приводится описание реализации параллельного алгоритма на основе технологии MPI

Существующие подходы к ускорению процесса обучения СММ обладают рядом недостатков и не позволяют эффективно решить проблему уменьшения времени обучения СММ для рассматриваемой задачи обнаружения аномалий в последовательностях системных вызовов Вместе с тем алгоритм Баума-Уэлча содержит в себе значительный ресурс распараллеливания при использовании больших обучающих выборок

Основная идея декомпозиции алгоритма Баума-Уэлча для множественных последовательностей наблюдений заключается в разбиении обучающей выборки на подмножества и расчета промежуточных значений для каждого подмножества отдельным процессом, работающим одновременно с аналогичными.

Пусть обучающая выборка, содержащая более одной последовательности наблюде-

и

о^ и°»

ний, разбита на следующие непересекающиеся подмножества: . Для каждого под-

множества Пи определим следующие соответствующие ему промежуточные параметры:

питА^^Ш) п»тВ^ = 1 %Г,Ц) ¿еп^^Ъ.и)

Я, '=1 1.1.0,=«, £2„ '=]

где у и ^ —матрицы промежуточных значений, определяемые в классических описаниях алгоритма Баума-Уэлча для множественных последовательностей наблюдений. Вычисления по формулам (1) могут выполняться в контексте параллельных процессов.

С учётом величин (1), можно вывести следующие выражения для обновления элементов матриц А и В обучаемой СММ:

питА^ (1) + пит А. (2) +... + питА! (II)

Ь\(1) =

питВ., (1) + питВЛ 2) + ... + питВ.,((/)

¿еп^ + Леп^ + .-. + аеп^и) ' ~ ' с!еп]{\) +с1еп^2) ++¿еп^и)

Вычисления по формулам (2) не могут быть эффективно распараллелены и должны выполняться в контексте одного процесса.

На рисунке 4 приведена блок-схема предлагаемого параллельного алгоритма обучения СММ.

Оценим трудоёмкость этапов, поддающихся распараллеливанию, в сравнении с этапами, которые могут выполняться только последовательно. Проанализировав формулы вычисления параметров а и |3 можно оценить трудоёмкость блоков 3 и 4 алгоритма, приведённого на рисунке 4. При обобщении для случая многократных последовательностей получим ОП\т2<Т>К), где <Т> — средняя длина последовательности наблюдений в обучающей выборке, а К — число элементов в обучающей выборке.

Трудоёмкость вычисления промежуточных значений I, в блоках 5 также будет составлять 0(Г\,2<ТЖ). Трудоёмкость вычисления у будет на порядок меньше — 0(ЖТ>К), поэтому в сравнении с остальными рассмотренными этапами им можно пренебречь.

Инициализация '

Ю

и

~Т

11.1x11.1

| питА(2) I питВ(2) |

| ^питА(и) ¡_ I

«3

Р-Р<д Конец

Рисунок 4 — Блок-схема параллельного алгоритма обучения СММ

Поддаются распараллеливанию также вычисления по формулам (1), чья трудоёмкость также оценивается как 0(Ы2<Т>К). Таким образом, суммарную трудоёмкость распа-

раллеливаемого участка алгоритма обучения СММ для многократных последовательностей наблюдений можно оценить как 0(N2<T>K)

Вычисления, неподдающиеся распараллеливанию, ограничиваются формулами (2) Трудоемкость вычисления всех значений а'у по формуле (2) ограничена оценкой 0(N2U), и значений Ь/1) по формуле (2) — оценкой 0(NMU) Соотношение числа состояний СММ (N) и числа символов наблюдений (М) может быть различным, однако при решении практических задач N и М обычно сопоставимы, т е общую трудоемкость нераспараллеливаемого участка алгоритма можно приближенно оценить как 0(N2U)

Поскольку говорить о параллельном алгоритме обучения СММ можно только при наличии весьма большой обучающей выборки, то можно считать справедливым соотношение <Т>К » U, следовательно, справедливо и 0(N2<T>K) » 0(N2U) Иными словами, оценка трудоемкости распараллеливаемых участков алгоритма обучения СММ в практических приложениях значительно превышает оценку трудоемкости последовательных участков, что свидетельствует об обоснованности выбора изложенной стратегии распараллеливания

Проанализируем разработанный параллельный алгоритм обучения СММ с точки зрения его реализации на конкретной вычислительной архитектуре Каждая параллельная ветвь алгоритма, представленная блоками 2-10 на рисунке 4, не обменивается информацией с другими ветвями кроме как в момент собственного старта и завеошекия Кроме того, каждая ветвь требует значительных затрат памяти для размещения вспомогательных переменных, необходимых в конечном итоге для вычислений выходных значений numA, пишВ и den Таким образом, наиболее подходящей архитектурой для реализации алгоритма будет параллельная система с распределенной (индивидуальной) памятью Этот класс систем включает в себя системы с массовым параллелизмом и кластерные системы

Превосходство трудоемкости параллельного участка алгоритма над трудоемкостью последовательного позволяет прийти к выводу о применимости алгоритма для реализации на кластерных системах Поскольку объемы передачи данных между отдельными процессами в разработанном алгоритме невелики, можно надеяться на то, что реализация алгоритма не будет чувствительна к пропускной способности коммуникационной среды Таким образом, алгоритм может, в частности, быть достаточно эффективно реализован даже на сетевом кластере на базе недорогого сетевого оборудования стандарта Ethernet

Для реализации параллельного алгоритма был выбран стандарт MPI (Message-Passing Interface) из-за своей универсальности, открытости и доступности

Необходимо отметить, что реализованный алгоритм распределения обучающей выборки по различным параллельным процессам не является оптимальным Известно доказательство NP-полноты в сильном смысле задачи, эквивалентной оптимальному распределению обучающей выборки по процессам Учитывая тот факт, что сам алгоритм обучения СММ является полиномиальным, было бы нецелесообразно использовать в его структуре другой NP-полный алгоритм только для оптимизации распараллетивания

Эксперименты показали, что несложная эвристика позволяет добиться распределения, достаточно близкого к теоретической оценке оптимума, за линейное время (в особенности, при большом числе элементов обучающей выборки) Идея этого эвристического метода распределения заключается в следующей последовательности действий Вначале определяется общее число символов наблюдений в обучающей выборке Затем происходит последовательный перебор элементов обучающей выборки Каждый текущий элемент назначается на обработку процессу с номером, равным общему числу процессов, умноженному на отношение накопленного числа символов наблюдения к их общему числу Если число элементов обучающей выборки существенно превосходит число параллельных процессов и

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

Для проверки эквивалентности параллельного алюритма последовательному алгоритма Баума-Уэлча, случайным образом был сгенерирован тестовый набор СММ, которые впоследствии были обучены с помощью последовательного, а затем параллельного алгоритма В качестве обучающей выборки использовались последовательности системных вызовов процесса named, перехваченные в нормальном режиме работы В результате обучения по обоим методам были получены файлы с настройками СММ, попарно содержащие одинаковые значения параметров А, В и л, что свидетельствует о функциональной эквивалентности параллельной и последовательной реализаций обучения

В пятой главе исследована эффективность параллельного алгоритма обучения СММ Показано, что он может быть реализован на недорогих сетевых кластерах, а также на многопроцессорных кластерах, с ускорением близким к предельно возможному теоретически

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

Исходя из имеющихся в наличии вычислительных ресурсов, был реализован сетевой кластер, включающий рабочие станции сети Fast Ethernet с пропускной способностью ЮОМбит/с Каждый рабочая станция представляет собой персональный компьютер с процессором Intel Pentium 4 Prescott 2,8 ГГц и объемом оперативной памяти 512 Мб На рабочие станции была установлена стандартная конфигурация ОС Linux Fedora Core 3, на которую, в свою очередь, был установлен пакет mpich, реализующий поддержку интерфейса MPI Вычислительная сеть была развернута на основе единственного коммуникатора, реализующего полнодоступную коммутацию'сетевых соединений

На рисунке 5 приведен график экспериментальной зависимости ускорения алгоритма обучения от количества задействованных узлов кластера Зависимость была получена при обучении СММ с числом состояний равным 6 с использованием части обучающей выборки для процесса named и другой СММ с числом состояний равным 10 с использованием части обучающей выборки процесса 1рг

Из рисунка 5 видно, что фактические значения ускорения достаточно близки к теоретическому пределу Более медленный рост ускорения для алгоритма, использующего данные процесса named, вполне обоснован и ожидаем В самом деле, трудоемкость последовательной части алгоритма при использовании небольшого числа параллельных ветвей оценивается как 0(N2), а трудоемкость параллельного участка алгоритма как 0(N3<T>K) Таким образом, чем меньший объем обучающей выборки (<Т>К) обрабатывается каждой параллельной ветвью, тем более соизмеримым становится соотношение времени работы последовательных и параллельных участков, что в итоге отрицательно сказывается на эффективности распараллеливания Однако следует отметить, что актуальным распараллеливание становится именно при больших объемах обучающей выборки Таким образом, разработанный параллельный алгоритм можно считать эффективным для решения задачи сокращения времени обучения СММ

Рисунок 5 — Экспериментальная зависимость ускорения параллельного алгоритма обучения от количества задействованных узлов сетевого кластера

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

Эффективность параллельного алгоритма обучения СММ была также исследована при запуске его реализации на высокопроизводительной вычислительной системе Hewlett-Packard C-class Blade System, содержащей пять четырёхпроцессорных вычислительных узлов. На рисунке 6 приведена экспериментальная зависимость ускорения параллельного алгоритма обучения СММ от количества процессорных ядер, задействованных в вычислениях.

ния СММ от количества процессорных ядер, задействованных в вычислениях

График демонстрирует, что в обоих экспериментах не удаётся существенно превысить шестикратный уровень ускорения, однако он достигается при задействовании в вычислениях только семи процессорных ядер. Рост ускорения до этого предела достаточно близок к линейному, что свидетельствует о высокой эффективности использования вычислительных ресурсов при распараллеливании.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

При решении поставленных в диссертационной работе задач получены следующие научные результаты

1 Разработана модель СОВ, основанная на обнаружении аномалий в последовательностях системных вызовов, идущих от контролируемых процессов Принципы, заложенные в систему, позволяют обнаруживать вторжения, признаки (сигнатуры) которых априорно не известны Модель использует профили нормального поведения контролируемых процессов в виде СММ В основе модели лежит метод, позволяющий локализовать аномалию, вызванную вторжением, с точностью до системного вызова, основйваясь на условной вероятности его возникновения Исследована возможность интеграции модели в состав комплексной СОВ

2 Проведено экспериментальное исследование зависимости показателей эффективности обнаружения вторжений от выбранного числа состояний СММ Установлено, что процесс обучения СММ зачастую сходится к локальному минимуму целевой функции Этот факт еще более усложняет процесс обучения, так как возникает дополнительная необходимость поиска значения числа состояний, обеспечивающего необходимые уровни сероятностей правильного обнаружение и ложного срабатывания Таким образом, задача сокращения времени обучения СММ становится еще более актуальной

3 Разработан параллельный масштабируемый алгоритм обучения СММ, позволяющий проводить обучение быстрее, чем широко используемый в настоящее время последовательный алгоритм Баума-Уэлча для множественных последовательностей наблюдений, а также его программная реализация на основе технологии MPI Использование алгоритма возможно в других приложениях СММ, например, в распознавании речи, оптическом распознавании текста, генетике

4 Проведено экспериментальное исследование эффективности параллельного алгоритма обучения СММ Данные исследований демонстрируют возможность реализации алгоритма на недорогих сетевых кластерах с ускорением близким к теоретически предельному

По теме диссертационной работы опубликованы следующие основные работы'

1 Аникеев, M В Разработка системы оптического распознавания факсимильного текста на основе скрытых марковских моделей // Проблемы теоретической и прикладной математики Труды 33-й Региональной молодежной конференции — Екатеринбург УрО РАН, 2002 —С 272-274

2 Макаревич, О Б , Бабенко, Л К , Аникеев, M В , Цопкало, H H Метод оптического распознавания печатного текста на основе псевдодвумерных скрытых марковских моделей // Сборник трудов научно-практической конференции «Информационная безопасность» — Таганрог ТРТУ, 2002 —С 195-197

3 Абрамов, Е С , Аникеев, M В , Макаревич, О Б Подготовка данных для использования в обучении и тестировании нейросетей при обнаружении сетевых атак // Известия ТРТУ Тематический выпуск Материалы V международной научно-практической конференции «Информационная безопасность», Таганрог 2003 г — Таганрог ТРТУ, 2003 г — С 204-206

4 Аникеев, M В , Сидоров, И Д Обнаружение аномального поведения пользователя в операционной системе Windows на основе анализа работы с приложениями И Извес-

тия ТРТУ Тематический выпуск Материалы V Международной научно-практической конференции «Информационная безопасность» — 2003 — №4(33) — С 202-204

5 Сидоров, И Д, Аникеев, М В Нейросетевое обнаружение аномального поведения пользователя в консольном режиме ОС Linux // Материалы VI Международной научно-практической конференции «Информационная безопасность» — Таганрог ТРТУ,

2004 —С 159-161

6 Аникеев, М В О возможности использования механизма скрытых марковских моделей в системах обнаружения информационных вторжений // Материалы VI Международной научно-практической конференции «Информационная безопасность» — Таганрог ТРТУ, 2004 — С 209-211

7 Аникеев, М В Выбор достаточного числа состояний в скрытых марковских моделях для решения задач обнаружения аномалий // Известия ТРТУ — 2005 — №9 — С 133

8 Аникеев, М В Метод обнаружения аномалий на основе скрытых марковских моделей с поиском оптимального числа состояний // Материалы VII Международной научно-практической конференции «Информационная безопасность» — Таганрог, ТРТУ 2005 —С 58-60

9 Amkeev, MVA Hardware/Software system of anomaly detection based on hidden Markov models // Materialien zum Wissenschaftlichen Seminar der Stipendiaten des „Michail Lomonosov" - Programms 2004/05 — Bonn Deutscher Akademischer Austauschdienst,

2005 — P 8-11

10 Tumoian, E , Amkeev, M Network-based detection of passive covert Channels in TCP/IP // LCN '05 Proc IEEE Conf on Local Computer Networks — Washington, DC IEEE Comp Soc, 2005 — P 802-809

11 Amkeev, M , Makarevich, О Parallel Implementation of Baum-Weich algorithm // Proc Workshop on Computer Science and Information Technologies (CSIT'2006), Karlsruhe, Germany, September 28-29, 2006 — Vol 1 —Ufa USATU, 2006 — P 197-200

12 Библиотека для работы со скрытыми марковскими моделями с параллельной реализацией обучения I М В Аникеев — Федеральная служба по интеллектуальной собственности, патентам и товарным знакам Свидетельство об официальной регистрации программы для ЭВМ №2007614524 от 26 10 2007

Личный вклад автора в работах, написанных в соавторстве, заключается в следующем [2] — алгоритм распознавания на основе СММ, [3, 4, 5] — определение достаточных наборов признаков для разработанных методов обнаружения аномалий, [10] — выбор архитектуры нейронной сети для обнаружения скрытых каналов передачи данных, [11] — разработка параллельного алгоритма обучения СММ

Формат 60x84 1/16 Бумага офсетная

Печать офсетная Уел п л - 1

Заказ № кЧ9 Тираж 100 экз

Издательство Технологического института ЮФУ ГСП 17А, Таганрог, 28, Некрасовский, 44 Типография Технологического института ЮФУ ГСП 17А, Таганрог, 28, Энгельса, 1

Содержание.

Введение.

1 Анализ существующих методов обнаружения вторжений.

1.1 Основные понятия.

1.2 Типовая структура СОВ.

1.3 Методологии обнаружения вторжений.

1.4 Обнаружение злоупотреблений.

1.4.1 Сопоставление строк.

1.4.2 Использование экспертных систем.

1.4.3 Анализ переходов между состояниями.

1.4.4 Методы добычи данных.

1.5 Обнаружение аномалий.

1.5.1 Статистические методы.

1.5.2 Предсказание поведения.

1.5.3 Методы добычи данных.

1.5.4 Нейросетевые методы.

1.5.5 Обнаружение аномалий в последовательностях системных вызовов.

1.6 Классификация СОВ.

1.7 Цели и задачи исследования.

1.8 Выводы.

2 Разработка модели системы обнаружения вторжений на основе СММ.

2.1 Сведения из теории СММ.

2.1.1 Основные определения.

2.1.2. Постановка типовых задач, связанных с СММ.

2.1.3 Решение задачи оценивания.

2.1.4 Решение задачи распознавания.

2.1.5 Решение задачи обучения.

2.1.6 Применение масштабирования в алгоритмах СММ.

2.1.7 Решение задачи обучения для множественных последовательностей наблюдений.

2.2 Принцип функционирования модели COA.

2.2.1 Общая схема COA.

2.2.2 Этапы функционирования системы.

2.2.3 Выбор используемой подсистемы аудита.

2.2.4 Формирование профиля нормального поведения процесса.

2.2.5 Алгоритм обнаружения аномалий в работе процесса.

2.3 Исследование возможности работы разработанной COA в составе комплексной СОВ.

2.4 Выводы.

3 Экспериментальное исследование модели системы обнаружения вторжений

3.1 Описание тестовой базы данных.

3.1.1 Обоснование выбора тестовой базы данных.

3.1.2 Данные процесса 1рг.

3.1.3 Данные процесса named.

3.1.4 Данные процесса xlock.

3.1.5 Данные процесса login.

3.1.6 Данные процесса ps.

3.1.7 Данные процесса inetd

3.1.8 Данные процесса stide.

3.2 Иллюстрация работы алгоритма обнаружения аномалий на примере данных процесса named.:.

3.3 Исследование зависимости эффективности обнаружения вторжений от выбранного числа состояний СММ.

3.3.1 Постановка задачи исследования.

3.3.2 Процесс lpr.

3.4 Обсуждение результатов экспериментов.

3.5 Выводы.

4 Разработка параллельного алгоритма обучения СММ.

4.1 Известные решения по ускорению обучения СММ.

4.2 Обоснование возможности эффективной организации параллельных вычислений в алгоритме обучения СММ.

4.2.1 Анализ алгоритма обучения СММ для однократных последовательностей наблюдений.

4.2.2 Анализ алгоритма обучения для многократных последовательностей наблюдений.

4.3 Разработка параллельного алгоритма обучения СММ.

4.4. Теоретическая оценка эффективности параллельного алгоритма.

4.5 Особенности программной реализация параллельного алгоритма обучения СММ.

4.5.1 Выбор средств реализации.

4.5.2 Описание программной реализации.

4.5.3 Экспериментальное подтверждение функционального соответствия параллельной и последовательной реализаций алгоритма обучения СММ.

4.6 Выводы.

5 Экспериментальное исследование эффективности параллельного алгоритма обучения СММ.

5.1 Условия проведения экспериментов.

5.2 Исследование эффективности работы параллельного алгоритма обучения СММ на сетевом кластере.

5.3 Исследование эффективности работы параллельного алгоритма обучения СММ на многопроцессорном кластере.

5.4 Выводы.

В связи с совершенствованием вычислительной техники и бурным ростом телекоммуникационных технологий, наблюдается повышение сложности используемого программного обеспечения. В таких условиях усложняется анализ разрабатываемых программ с точки зрения безопасности. По данным Национального института стандартов и технологий США (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 страниц приложений.

5.4 Выводы

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

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

Заключение

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

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

2) Проведено экспериментальное исследование зависимости показателей эффективности обнаружения вторжений от выбранного числа состояний СММ. Установлено, что процесс обучения СММ зачастую сходится к локальному минимуму целевой функции. Этот факт ещё более усложняет процесс обучения, так как возникает дополнительная необходимость поиска значения числа состояний, обеспечивающего необходимые уровни вероятностей правильного обнаружение и ложного срабатывания. Таким образом, задача сокращения времени обучения СММ становится ещё более актуальной.

3) Разработан параллельный масштабируемый алгоритм обучения СММ, позволяющий проводить обучение быстрее, чем широко используемый в настоящее время последовательный алгоритм Баума-Уэлча для множественных последовательностей наблюдений, а также его программная реализация на основе технологии MPI. Использование алгоритма возможно в других приложениях СММ, например, в распознавании речи, оптическом распознавании текста, генетике.

4) Проведено экспериментальное исследование эффективности параллельного алгоритма обучения СММ. Данные исследований демонстрируют возможность реализации алгоритма на недорогих сетевых кластерах с ускорением близким к теоретически предельному.

1. National Institute of Standards and Technology. E-resource. — Available: http://nvd.nist.gov.

2. The ten most important security trends of the coming year / Edited by S. Northcutt et al. — SANS Institute, 2006. — 3 p. — Available: http://www.sans.org/resources/10securitytrends.pdf.

3. Kumar, S. Classification and detection of computer intrusions: PhD thesis. —Purdue university, 1995. — 180 p.

4. Лукацкий, А. В. Обнаружение атак. — СПб.: БХВ-Петербург, 2001. —624 с.

5. Милославская, Н. Г., Толстой, А. И. Интрасети: обнаружение вторжений: Учеб. пособие для вузов. — М.: Юнити-Дана, 2001. — 587 с.

6. Lundin, Е., Jonsson, Е. Survey of intrusion detection research: Technical report No. 02-04. — Goteborg: Chalmers University of Technology, 2002 — 43 p.

7. Denning, D. E. An intrusion-detection model // IEEE Transaction on software engineering. — 1987. —No. 2. — P. 222-232.

8. Hansen, S. E., Atkins, E. T. Automated system monitoring andthnotification with swatch // Proc. 7 System Administration Conference (LISA 93). — Monterey. — 1993. — P. 101-108.

9. Абрамов, E. С. Разработка и исследование методов построения систем обнаружения атак: дис. . канд. техн. наук: 05.13.19 — Таганрог, 2005. — 140 с.

10. Абрамов, Е. С. Разработка методов функционального тестирования СОА // Сборник научных трудов XI всероссийской научной конференции «Проблемы информационной безопасности в системе высшей школы». — М.: МИФИ, 2004.

11. Wu, S., Manber, U. Fast text searching with errors. Technical report TR 91-11. —Tucson: Univ. of Arizona, 1991. — 18 p.

12. Lindqvist, U., Porras, P. A. Detecting computer and network misuse through the production-based expert system toolset (P-BEST) // Proc. 1999 IEEE Symposium of Security and Privacy, Oakland, California, May 1999. — IEEE Сотр. Soc., 1999, —P. 141-161.

13. Snort — the de facto standard for intrusion detection/prevention. — 2006. — Available: http://snort.org

14. Snort™ user manual. 2.6.0. — Sourcefire, Inc., 2006. — Available: http://snort.Org/docs/snortmanual/2.6/snortmanual.pdf

15. Habra, N., Le Charlier, В., Mounji, A., Mathieu, I. ASAX: Software architecture and rule-based language for universal audit trail analysis // European Symposium on Research in Computer Security (ESORICS). — 1992. — P. 435450.

16. Porras, P. A., Neumann, P. G. Emerald: Event monitoring enabling responses to anomalous live disturbances. — Proc. 20th National Information Systems Security Conference. — Baltimore: NIST/NCSC, 1997. — P. 353-365.

17. Vigna, G., Eckmann S. Т., Kemmerer, R. A. The STAT tool suite // Proc. DISCEX 2000. — IEEE Press, 2000.

18. Ilgun, K., Kemmerer, R. A., Porras, P. A. State transition analysis: a rule-base intrusion detection approach // IEEE Trans. Software Engineering. — No. 3, Vol. 21.— 1995.— P. 181-199.

19. Sun, J. BSM security auditing for Solaris servers. GIAC security essentials certification practical. — 2003. — 12 p. — Available: http://www.giac.org/practical/gsec/JohnSunGSEC.pdf

20. Eckmann, S. T., Vigna, G., Kemmerer, R. A. STATL: An attack language for state-based intrusion detection. — 2000. —24 p. — Available: http://citeseer.ist.psu.edu/452116.html

21. Kumar, S., Spafford, E. H. A pattern-matching model for misusefUintrusion detection. // Proc. 17 National Computer Security Conference. — 1994. — P. 11-21.

22. Lee, W., Stolfo, S. J., Mok, K. W. Adaptive Intrusion- Detection: A Data Mining Approach // Artificial Intelligence Review. — 2000. — Vol. 14, No. 6.—P. 533-567.

23. Fink, G., Levitt, K. Property-based testing of privileged programs // Proc. 10th Annual Computer Security Applications Conference. — IEEE, 1994. — P. 154-163.

24. Ko, C., Fink, G., Levitt, K. Automated detection of vulnerabilities in privileged programs by execution monitoring // Proc. 10th Annual Computer Security Applications Conference. — IEEE Comp. Soc. Press, 1994. — P. 134144.

25. Forrest, S., Hofmeyr, S. A., Somayaji, A., Longstaff, T. A. A sense of self for Unix processes // Proc. 1996 IEEE Symposium on Security and Privacy. — IEEE Comp. Soc. Press, 1996. — P. 120-128.

26. Ghosh, A. K., Wanken, J., Charron, F. Detecting anomalous and unknown intrusions against programs // Proc. Annual Computer Security Applications Conference (ACSAC'98), December 1998. — 1998. — P. 259-267.

27. Eslcin, E. et al. Adaptive model generation for intrusion detection. I I Proc. ACMCCS Workshop on Intrusion Detection and Prevention, Athens, Greece, 2000. — 2000. — Available: http://citeseer.ist.psu.edu/eskinOOadaptive.html.

28. Okazaki, Y., Sato, L, Goto, S. A new intrusion detection method based on process profiling. // Proc. IEEE Symposium on Applications and the Internet (SAINT'02). — 2002. — P. 82-91.

29. Cho, S.-B. Incorporating soft computing techniques into a probabilistic intrusion detection system. // IEEE Transactions on Systems, Man, and Cybernetics, Part C. — Vol. 32, No.2, 2002. — P. 154-160.

30. Yin, Q., Shen, L., Zhang, R., Li, X. A new intrusion detection methodfhbased on behavioral model. // Proc. 5 World Congress on Intelligent Control and Automation, June 15-19, 2004, Hangzhou, P. R. China. — 2004. — P. 4370-4374.

31. Gudkov, V., Johnson, J. E. New approach for network monitoring and intrusion detection // CoRR. — 2001. — Vol. cs.CR/0110019. — Available: http://arxiv.org/abs/cs.CR/0110019.

32. Gudkov, V., Johnson, J. E. Multidimensional network monitoring for intrusion detection // CoRR. — 2002. — Vol. cs.CR/0206020. — Available: http://arxiv.org/abs/cs.CR/0206020.

33. Barford, P., Plonka, D. Characteristics of network traffic flow anomalies // Proc. 1st ACM SIGCOMM Workshop on Internet Measurement, San Francisco, California, USA, November 1-2, 2001. — ACM, 2001. — P. 69-73.

34. Smaha, S. E. Haystack: an intrusion detection system // Proc. 4th IEEE Aerospace Computer Security Applications Conference. — Orlando, FL: IEEE, 1988. —P. 37-44.

35. Lane, T., Brodley, C. E. Sequence matching and learning in anomaly detection for computer security // Proc. AAAI-97 Workshop on AI Approaches to Fraud Detection and Risk Management. — 1997. — P. 43-49.

36. Lane, T., Brodley, C. E. An application of machine learning to anomaly detection // Proc. of the 12th National Information Systems Security Conference. — Vol. 1. — Gaithersburg, MD: NIST, 1997. — P. 366-380.

37. Lane, T. Filtering techniques for rapid user classification // Proc. AAAI-98/ICML-98 Joint Workshop on AI Approaches to Time-series Analysis. — Menlo Park, CA: AAAI Press, 1998. — P. 58-63.

38. Lane, T., Brodley, C. E. Temporal Sequence Learning and Data Reduction for Anomaly Detection // Proc. 5th ACM Conference on Computer and Communications Security. — Assoc. for Computing Machinery, 1998. — P. 150158.

39. Lane, T. Hidden Markov models for human/computer interface modeling // Proc. IJCAI-99 Workshop on Learning About Users. — 1999. — P. 35-^4.

40. Debar, H., Becker, M., Siboni, D. A neural network component for an intrusion detection system // Proc. 1992 IEEE Comp. Soc. Symposium on Research in Security and Privacy. — Los Alamos, CA: IEEE Comp. Soc. Press, 1992. —P. 240-250.

41. Cannady, J. Artificial neural networks for misuse detection // Proc. 1998 National Information Systems Security Conference (NISSC'98). — 1998. — P. 443-456.

42. Сидоров, И. Д., Аникеев, М. В. Нейросетевое обнаружение аномального поведения пользователя в консольном режиме ОС Linux // Материалы VI Международной научно-практической конференции «Информационная безопасность». — Таганрог: ТРТУ, 2004. — С. 159-161.

43. Tumoian, Е., Anikeev, М. Network-based detection of passive covert Channels in TCP/IP // LCN *05: Proc. IEEE Conf. on Local Computer Networks. — Washington, DC: IEEE Comp. Soc., 2005 — P. 802-809.

44. Elman, J. L. Finding structure in time // Cognitive Science. — 1990. — Vol. 14, No. 2. — P. 179-211.

45. Fink, G., Ko, C., Archer, M., Levitt, K. Towards a property-based testing environment with applications to security-critical software // Proceedings of the 4th Irvine Software Symposium. — 1994. — P. 39-48.

46. Warrender, C., Forrest, S., Pearlmutter, B. A. Detecting intrusions using system calls: alternative data models // Proc. IEEE Symposium on Security and Privacy. — Oakland, CA: IEEE Comp. Soc., 1999. — P. 133-145.

47. Hofmeyr, S. A., Forrest, S., Somayaji, A. Intrusion detection using sequences of system calls // Journal of Computer Security. — 1998. — Vol. 6, No. 3. —P. 151-180.

48. Cohen, W. W. Fast effective rule reduction // Machine Learning: the 12th Intl. Conference. — Morgan Kaufmann, 1995. — P. 115-123.

49. Yin, Q.-B. et al. Intrusion detection based on hidden Markov model. — Proc. 2nd Intl. Conference on Machine Learning and Cybernetics. Xi'an, November. 2003. — IEEE, 2003. — Vol. 5. — P. 3115-3118.

50. Wespi, A., Dacier, M., Debar, H. An intrusion-detection system'based" on the TEIRESIAS pattern-discovery algorithm // Proc. EICAR'99. — Aalborg, Denmark: Aalborg Universitet, 1999.— P. 1-15.

51. Rigoutsos, I., Floratos, A. Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm // Bioinformatics. — 1998. — Vol.14, No. 1. —P. 55-67.

52. Marceau, C. Characterizing the behavior of a program using multiple-length N-grams // Proc. 2000 workshop on New security paradigms. — Ballycotton, County Cork, Ireland: ACM Press, 2000. — P. 101-110.

53. Ghosh, A., Wanken, J., Charron, F. Detecting anomalous and unknown intrusions against programs // Proc. 1998 Annual Computer Security Applications Conference (ACSAC'98). — Los Alamitos, CA: IEEE Comp. Soc, 1998. — P. 259-267.

54. Ghosh, A., Schwartzbard, A., Schatz, M. Learning program behavior profiles for intrusion detection // Proc. 1st USENIX Workshop on Intrusion Detection and Network Monitoring. — 1999. —P. 51-62.

55. Yeung, D., Ding, Y. Host-based intrusion detection using dynamic and static behavioral models // Pattern Recognition. — 2002. — Vol. 36. — P. 229243.

56. Al-Subaie, M., Zulkernine, M. Efficacy of hidden Markov models overthneural networks in anomaly intrusion detection // Proc. 30 Annual International Computer Software and Applications Conference (COMPSAC). — Chicago: IEEE CS Press, 2006. — P. 325-332.

57. Heberlein, L. T. Network security monitor. Final report. — Davis, CA: UC Davis, 1993. — 53 p. — Available: http://seclab.cs.ucdavis.edu/papers/NSM-final.pdf.

58. Paxson, V. Bro: a system for detecting network intruders in real-time // Computer Networks (Amsterdam, Netherlands: 1999). — 1999. — Vol. 31, No. 23-24.—P. 2435-2463.

59. Ilgun, K. USTAT: a real-time intrusion detection system for UNIX // Proc. 1993 IEEE Symposium on Research in Security and Privacy. — Oakland, CA: IEEE Comp. Soc, 1993. — P. 16-28.

60. Staniford-Chen, S. et al. GrIDS — A graph-based intrusion detection system for large networks // Proc. 19th National Information Systems Security Conference. — 1996. — P. 361-370.

61. Jou, Y. F, Gong, F., Sargor, C., Wu, S. F., Cleaveland, W. R. Architecture design of a scalable intrusion detection system for the emerging network infrastructure. Technical Report CDRL A005. — Releigh: North Carolina State University, 1997. — 42 p.

62. Somayaji, A., Forrest, S. Automated response using system-call delays // Proc. USENIX Security Syposium. — Denver: USENIX, 2000. — P. 185-197.

63. Рабинер, JI. Р. Скрытые марковские модели и их применение в избранных приложениях при распознавании речи: обзор // ТИИЭР. — 1989. — т. 77, №2. —С. 86-120.

64. Baum, L. Е., Sell, G. R. Growth functions for transformations and manifolds // Pacific Journal of Mathematics. — 1968. — Vol. 27, No. 2. — P. 211-227.

65. Sun, J. BSM Security Auditing for Solaris Servers. — Bethesda, Mayland: SANS, 2003. — 12 p. — Available: http://www.securitydocs.com/go/2329.

66. The Linux BSM project Е-resource. — 2001. — Available: http://linuxbsm.sourceforge.net.

67. TrustedBSD — OpenBSM Е-resource. — 2006. — Available: http://www.trustedbsd.org/openbsm.html.

68. Trusted Computer System Evaluation Criteria, DoD 5200.28-STD. — Fort Meade, MD: National Computer Security Center, 1985. — 116 p. — Available: http://csrc.nist.gov/publications/history/dod85.pdf.

69. Computer Immune Systems — Data Sets and Software Е-resource. — Albuquerque, NM: University of New Mexico, 2004. — Available: http://www.cs.unm.edu/~immsec/data-sets.htm.

70. Baras, J. S., Rabi, M. Intrusion detection with support vector machines and generative models. Technical report TR 2002-22. — College Park: University of Maryland, 2002. — 17 p.

71. Hoang, X. D., Hu, J., Bertok, P. A multi-layer model for anomaly intrusion detection using program sequences of system calls. — Proc. ICON'2003. The 11th IEEE Conference on Networks. — IEEE, 2003. — P. 531-536.

72. Raj wade, A. Some experiments with hidden Markov models. Technical report. — University of Florida, 2005. — 18 p. — Available: http://www.cise.ufl.edu/~avr/HMM.pdf.

73. Gtinter, S., Bunlce, H. Optimizing the number of states, training iterations and Gaussians in an HMM-based handwritten word recognizer // Proc. 7th Intl. Conf. on Document Analysis and Recognition, Edinburgh, Scotland. — 2003. — Vol. 1. — P. 472-476.

74. Аникеев, M. В. Выбор достаточного числа состояний в скрытых марковских моделях для решения задач обнаружения аномалий // Известия ТРТУ. —2005. —№9. —С. 133.

75. Аникеев, М. В. Метод обнаружения аномалий на основе скрытых марковских моделей с поиском оптимального числа состояний // Материалы VII Международной научно-практической конференции «Информационная безопасность». — Таганрог, ТРТУ: 2005. — С. 58-60.

76. Noise reduction in speech application / Edited by G. M. Davis. — Boca Raton, FL: CRC Press LLC, 2002. — 432 p.

77. Ронжин, A. JL, Карпов, А. А., Ли, И. В. Система автоматического распознавания русской речи SIRIUS // Научно-теоретический журнал «Искусственный интеллект». — 2005. — №3. — С. 590-601.

78. Eickeller, S., Mtiller, S., Rigoll, G. Recognition of JPEG compressed face images based on statistical methods // Image and Vision Computing. — 2000. — Vol. 18. —P. 279-287.

79. Elms, A. J., Procter, S., Illingworth, J. The advantage of using and HMM-based approach for faxed word recognition // International Journal on Document Analysis and Recognition (IJDAR). — 1998. — No. 1(1). — P. 18-36.

80. Kulp, D., Haussler, D., Reese, M. G., Eeckman, F. H. A generalized hidden Markov model for the recognition of human genes in DNA // Proc. 4th Intl. Conf. on Intelligent Systems for Molecular Biology. — 1996. — P. 134-142.

81. Henderson, J., Salzberg, S., Fasman, К. H. Finding genes in DNA with a hidden Markov model // Journal of Computational Biology. — 1997. — Vol. 4, No. 2. —P. 127-142.

82. Моттль, В. В., Мучник, И. Б. Скрытые марковские модели в структурном анализе сигналов. —М.: Физматлит, 1999. — 352 с.

83. Turin, W., van Nobelen, R. Hidden Markov modeling of flat fading channels // IEEE Journal on Selected Areas is Communications. — 1998. — Vol. 16. —P. 1809-1817.

84. Nechyba, M. C., Xu, Y. Stochastic similarity for validating human control strategy models // IEEE Trans. Robotics and Automation. — 1998. — Vol. 14, Issue 3, —P. 437-451.

85. Mangold, S., Kyriazakos, S. Applying pattern recognition techniques based on hidden Markov models for vehicular position location in cellular networks // Proc. IEEE Vehicular Technology Conference. — 1999. — Vol. 2. — P. 780-784.

86. Chari, S. N., Cheng, P. C. BlueBoX: a policy-driven host-based intrusion detection system // ACM Trans, on Information and System Security. — 2003. — Vol. 6. — P. 173-200.

87. Kang, D.-K., Fuller, D., Honavar, V. Learning classifiers for misuse detection using a bag of system calls representation // Lecture Notes in Computer Science. —2005, —Vol. 3495. —P. 511-516.

88. Valdes, A., Skinner, K. Probabilistic alert correlation // Lecture Notes in Computer Science. — 2001. — Vol. 2212. —P. 54-68.

89. Goldman, R. P., Heimerdinger, W., Harp, S. A. Information modeling for intrusion report aggregation // Proc. of the DARPA Information Survivability Conference and Exposition (DISCEX II). —Anaheim: IEEE Comp. Soc., 2001. — P. 329-342.

90. Cuppens, F., Miége, A. Alert correlation in a cooperative intrusion detection framework // IEEE Symposium on Security and Privacy. — 2002. —P. 187-200.

91. Turin, W. Unidirectional and parallel Baum-Welch algorithms // IEEE Trans. Of Speech and Audio Processing. — 1998. — Vol. 6, issue 6. — P. 516523.

92. Espinosa-Manzo, A., López-López, A., Arias-Estrada, M. O. Implementing hidden Markov models in a hardware architecture // Proc. Intl. Meeting of Computer Science ENC '01, Aguascalientes, México, September 15-19 2001. —Vol. II. —2001. —P. 1007-1016.

93. Anikeev, M., Makarevich, O. Parallel implementation of Baum-Welch algorithm // Proc. Workshop on Computer Science and Information Technologies (CSIT'2006), Karlsruhe, Germany, September 28-29, 2006. — Vol. 1. — Ufa: USATU, 2006. — P. 197-200.

94. Message Passing Interface Е-resource. — 2007. — Available: http://www-unix.mcs.anl.gov/mpi.

95. Argonne National Laboratory. Mathematics and computer science division. Е-resource. — 2007. — Available: http://www.mcs.anl.gov.

96. MPICH2 home page. Е-resource. — 2007. — Available: http://www-unix.mcs.anl.gov/mpi/mpich.

97. Ш.Гэри, M., Джонсон, Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 412 с.

98. ITU-TS Recommendation Z.120: Message-sequence chart (MSC), 04/2004. — Geneva: International Telecommunication Union, 2004. — 136 p.

99. Шпаковский, Г. И., Серикова, Н. В. Программирование для многопроцессорных систем в стандарте MPI. — Минск: БГУ, 2002. — 323 с.