Содержание к диссертации
Введение
Глава 1 Анализ систем обнаружения вторжений 15
1.1 Системы обнаружения вторжений 15
1.2 Обзор проблем обнаружения вторжений 17
1.3 Различие между системой обнаружения атак и системой обнаружения вторжений 22
1.4 Выводы 23
Глава 2 Вероятностные модели обнаружения вторжений 25
2.1 Обзор вероятностных моделей 25
2.1.1 Марковские сети 27
2.1.2 Скрытая Марковская модель 27
2.1.3 Авторегрессивная скрытая Марковская сеть 29
2.1.4 Задачи, решаемые с помощью скрытых Марковских моделей 30
2.1.5 Фильтр Калмана 30
2.1.6 Байесовские сети 32
2.1.7 Вероятностные запросы 34
2.1.8 Байесовский вывод
2.2 Динамические байесовские сети 36
2.3 Обучение динамических байесовских сетей
2.3.1 Алгоритмы обучения параметров байесовской сети 42
2.3.2 Алгоритмы обучения структуры байесовской сети 43
2.4 Вероятностный вывод на основе динамических байесовских сетей 46
2.4.1 Алгоритмы вероятностного вывода 47
2.5 Проблема задания априорных вероятностей 49
2.6 Выводы 52
Глава 3 Разработка модели и методов обнаружения вторжений
3.1 Разработка метода анализа информативных характеристик сетевого трафика 55
3.1.1 Критерий прироста информации 56
3.1.2 Коэффициент усиления информации 59
3.1.3 Описание набора данных KDD 99 60
3.1.4 Описание и анализ набора данных NSL-KDD 63
3.1.5 Сравнительный анализ набора данных KDD 99 3.2 Разработка вероятностной модели обнаружения вторжений 74
3.3 Разработка метода поиска новых типов вторжений с использованием вероятностного вывода 79
3.4 Выбор числа срезов динамических байесовских сетей 82
3.5 Выводы 83
Глава 4 Разработка параллельного алгоритма обучения структуры динамических байесовских сетей 85
4.1 Обзор алгоритмов обучения структуры байесовских сетей 85
4.1.1 Алгоритмы обучения структуры байесовской сети на основании ограничений условной независимости 86
4.1.2 Алгоритмы обучения структуры байесовской сети на основании оптимизации меры качества сети 88
4.1.3 Гибридные алгоритмы 90
4.2 Последовательный алгоритм обучения Max-Min Hill-Climbing 91
4.2.1 Преимущества гибридного алгоритма Max-Min Hill-Climbing 92
4.2.2 Недостатки гибридного алгоритма Max-Min Hill-Climbing 93
4.2.3 Описание гибридного алгоритма Max-Min Hill-Climbing
4.3 Разработка параллельного алгоритма обучения Max-Min Hill-Climbing...99
4.4 Сравнение последовательного и параллельного алгоритмов обучения структуры байесовской сети Max-Min Hill-Climbing 105
4.5 Выводы 107
Глава 5 Разработка и тестирование системы обнаружения вторжений на основе динамических байесовских сетей 109
5.1 Описание разработанной системы обнаружения вторжений 109
5.2 Тестирование разработанной системы обнаружения вторжений 111
5.3 Рекомендации для практического внедрения разработанной системы обнаружения вторжений 115
5.4 Выводы 116
Заключение 117
Список литературы
- Различие между системой обнаружения атак и системой обнаружения вторжений
- Задачи, решаемые с помощью скрытых Марковских моделей
- Описание набора данных KDD 99
- Алгоритмы обучения структуры байесовской сети на основании ограничений условной независимости
Введение к работе
Актуальность темы. Развитие средств защиты для компьютерных систем продиктовано применением со стороны злоумышленников новых техник проникновения и появлением новых видов использования уязвимостей в компьютерных системах. С каждым годом количество вредоносных программ, реализующих новые типы атак, увеличивается. Для построения комплексной системы защиты наравне с остальными традиционно используемыми инструментами защиты все чаще применяют системы обнаружения вторжений (СОВ).
К сожалению, низкая надежность работы СОВ приводит к необходимости частого участия человека в обслуживании СОВ для корректировки метода обнаружения. Система обнаружения вторжений после ввода в эксплуатацию способна в течение некоторого промежутка времени эффективно функционировать. Однако с течением времени эффективность системы может снижаться, что приводит к увеличению ложных срабатываний и отсутствию реакции на вторжения. Поэтому СОВ сложны в наладке и требуют высококвалифицированного обслуживающего персонала. Изложенные особенности функционирования известных СОВ делают решение проблемы автономности работы СОВ актуальной.
Автором предложен подход для построения сетевой системы обнаружения вторжений на основе вероятностной модели, которая способна описывать процессы в условиях нехватки данных. Задачи, способные решать вероятностные модели, используют процедуры вероятностного вывода. Различные процессы порождают последовательности данных, которые находят свое отражение в пространстве окружения протекания процесса. Процесс вторжения в компьютерных системах проявляется в изменениях последовательности сетевого трафика, профиля поведения пользователя, последовательности системных вызовов к ядру операционной системы. В работе для сетевых СОВ предлагается вероятностная модель на основе последовательности характеристик сетевого трафика, так как большинство вторжений происходит с использованием компьютерных сетей. Как правило, выделяют три этапа вторжения: сканирование сети; воздействие на уязвимость; повторное получение управления системой через загруженную программу, использующую недокументированный вход в систему. Среди разновидностей вероятностных моделей наиболее перспективным является применение динамических байесовских сетей (ДБС), которые описываются в пространстве состояний в виде ориентированных графов. Методы и алгоритмы, основанные на использовании ДБС, превосходят другие вероятностные модели в точности описания моделируемых процессов и гибкости применения, однако требуют применения более трудоемких алгоритмов, чем, например, скрытые Марковские модели или фильтр Калмана. В развитие теории ДБС большой вклад внести зарубежные ученые Murphy К., Pearl J., Zweig G. Для построения и использования динамических байесовских сетей требуется обучить параметры и структуру сети. Алгоритмы обучения структуры ДБС требуют высоких вычислительных затрат, поэтому задача разработки параллельного алгоритма обучения является также актуальной.
Таким образом, задача разработки методов и алгоритмов обнаружения вторжений с использованием ДБС также является актуальной.
Объектом исследования являются сетевые системы обнаружения процесса вторжения в компьютерную сеть.
Предметом исследования являются алгоритмы обучения и методы вероятностного вывода с использованием динамических байесовских сетей.
Цель диссертационной работы заключается в разработке модели и алгоритмов обнаружения вторжений на основе протоколирования характеристик сетевого трафика в компьютерной сети с использованием динамических байесовских сетей.
Задачи исследования. Для достижения указанной цели необходимо решить следующие задачи:
-
Разработать метод анализа информативных характеристик сетевого трафика для обнаружения вторжений.
-
Разработать вероятностную модель процесса вторжения в компьютерную сеть.
-
Разработать метод поиска новых типов вторжений с использованием вероятностного вывода в динамических байесовских сетях.
-
Разработать параллельный алгоритм обучения структуры байесовских сетей.
-
Провести экспериментальное исследование и сравнительный анализ последовательного и параллельного алгоритма обучения структуры байесовских сетей.
-
Разработать систему обнаружения вторжений на основе функционирования динамических байесовских сетей и сравнить с существующими системами.
Методы исследования основаны на использовании теории вероятности, теории информации, математической статистики, математического моделирования, теории параллельных вычислений. В работе широко применяется компьютерное моделирование, в том числе с использованием самостоятельно разработанного программного обеспечения (ПО).
Информационной базой исследования являются отечественные и зарубежные литературные источники: методические рекомендации, монографии, публикации в отраслевых периодических журналах, материалы крупных исследовательских и методических центров. Также использованы материалы, размещенные в сети Интернет.
Научная новизна работы. В результате проведенного исследования были получены следующие результаты, характеризующиеся научной новизной:
-
Разработан метод анализа информативных характеристик сетевого трафика для обучающих наборов данных при использовании в системах обнаружения.
-
Разработана вероятностная модель обнаружения вторжений на основе динамических байесовских сетей. В отличие от существующих вероятностных моделей вторжений данная модель учитывает три основных этапа вторжения в компьютерную сеть.
-
Разработан оригинальный метод поиска новых типов вторжений с использованием вероятностного вывода в динамических байесовских сетях, который в отличие от существующих методов позволяет эффективно обнаруживать как известные, так и новые типы вторжений.
-
Разработан параллельный алгоритм обучения структур байесовских сетей с использованием технологии вычислений на основе графических видеокарт.
-
Разработана структура системы обнаружения вторжений, основанная на функционировании динамических байесовских сетей.
Реализация и внедрение результатов исследования. Основные результаты исследований использованы на кафедре проектирования и безопасности компьютерных систем НИУ ИТМО при вьшолнении ряда научно-исследовательских работ и внедрении в образовательный процесс лабораторных работ по защите информационных процессов в компьютерных сетях.
Достоверность полученных результатов подтверждается корректностью математического аппарата и теоретических обоснований, а также результатами экспериментов, проведенных с помощью разработанного в диссертации ПО.
Практическая значимость результатов диссертации заключается в следующем.
-
Разработанный метод анализа информативных характеристик сетевого трафика позволяет сократить затраты на вычисления в обучении и вероятностном выводе при выборе числа переменных в вероятностных моделях с заданным порогом отбора.
-
Разработанная вероятностная модель адекватно работает на всех трех этапах вторжения и может быть расширена для более точного описания различных аспектов особенностей атаки на сетевую систему.
-
Разработанная система обнаружения вторжений на основе функционирования динамических байесовских сетей позволяет обнаружить новые типы вторжений.
-
Разработан параллельный алгоритм обучения структуры байесовской сети, позволяющий сократить время ее обучения, реализованный в виде нескольких программных модулей. Их можно использовать и в других задачах, решаемых ДБС, например, в других областях исследований.
Внедрение и реализация. Практические результаты работы были внедрены и использованы в НИУ ИТМО, что подтверждено соответствующим актом о внедрении.
Публикации по теме диссертации. По теме диссертации опубликовано десять научных работ, из них семь выполнено самостоятельно, три в соавторстве. Две статьи опубликованы в рецензируемом научном журнале, определенном в перечне ВАК.
Апробация работы. Основные научные положения и практические результаты работы были представлены и обсуждены на следующих научно-технических конференциях:
-
VII всероссийской межвузовской конференции молодых ученых, 2010 г.;
-
XL научной и учебно-методической конференции, 2011 г.;
-
VIII всероссийской межвузовской конференции молодых ученых, 2011 г.;
-
IX всероссийской межвузовской конференции молодых ученых, 2012 г.;
-
XLI научной и учебно-методической конференции, 2012 г.;
-
VIII mezinarodni vedecko-prakticka konference «Aktualni vymozenosti — 2012», 2012 г.;
-
XLII научной и учебно-методической конференции НИУ ИМТО, 2013 г. Основные научные положения, выносимые на защиту:
-
Метод анализа информативных характеристик сетевого трафика для обучающих наборов данных при использовании в системах обнаружения вторжений. Метод не зависит от количества принимаемых значений для свойств.
-
Вероятностная модель обнаружения вторжений на основе динамических байесовских сетей. В отличие от существующих вероятностных моделей вторжения данная модель учитывает три основных этапа вторжения в компьютерную сеть и может быть уточнена путем включения в модель дополнительных переменных.
-
Оригинальный метод поиска новых типов вторжений с использованием вероятностного вывода в динамических байесовских сетях, который в отличие от существующих методов позволяет эффективно обнаруживать как известные, так и новые типы вторжений.
-
Параллельный алгоритм обучения структур байесовских сетей с использованием технологии вычислений на основе графических видеокарт, что позволяет добиться уменьшения времени обучения и стоимости оборудования по сравнению с применением кластерных систем.
-
Структура системы обнаружения вторжений, основанная на функционировании динамических байесовских сетей.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения, списка литературы. Материал изложен на 130 страницах компьютерного текста, иллюстрирован 31 рисунком и 10 таблицами.
Различие между системой обнаружения атак и системой обнаружения вторжений
Современное направление исследований в области обнаружения вторжений направлено на использование более сложных вероятностных моделей, способных описывать процессы более полно. В результате, все больше внимания уделяется методу обнаружения вторжений, который анализирует последовательности контролируемого процесса, описанных с помощью вероятностных моделей. Применительно к решению задач информационной защиты в качестве анализируемых последовательностей могут использоваться: — характеристики сетевого трафика в компьютерных сетях; — профили поведения пользователя на уровне приложения или операционной системы; — последовательности системных вызовов, поступающих к ядру операционной системы от работающих процессов и т. д.
Данные последовательности могут находить свое отражение (отклик) в работе компьютерной сети и операционной системы компьютера в виде наблюдаемых характеристик контролируемого процесса. Тем не менее, не все процессы можно наблюдать непосредственно. Поэтому в случае неизвестного или скрытного процесса не все характеристики процесса наблюдаемы, а только те, которые имеют причинно-следственную природу. В системе появляются только второстепенные характеристики процесса. Для описания таких последовательностей используют вероятностные модели процесса, которые способны моделировать различные последовательности или временные ряды в условиях нехватки или недостоверности данных.
Для решения проблемы обнаружения новых типов вторжений с применением вероятностных моделей используют вероятностный вывод (ВВ), основанный на применении теоремы Байеса. ВВ является статистически корректным инструментом, позволяющим производить прогнозирование, фильтрацию и оценивание текущей вероятностной модели. Отметим, что оценка модели позволяет ответить на вопрос корректности описания наблюдаемых последовательностей событий в прошлом и настоящем.
Рассмотрим также проблему, влияющую на надежность СОВ, а именно на необходимость участия человека в обслуживании системы [6]. Система обнаружения вторжений после ввода в эксплуатацию способна в течение некоторого промежутка времени функционировать эффективно. Тем не менее, с течением времени контролируемая система и ее среда функционирования начинают меняться, что приводит к неучету новых свойств или, наоборот, к учету свойств уже неактуальных. Как следствие, в СОВ увеличивается число ложных срабатываний, когда вторжение не имело места, из-за увеличения ошибок первого рода, и происходит пропуск вторжений, когда вторжение не было выявлено, из-за увеличения ошибок второго рода. Для того чтобы этого не происходило, требуется участие человека в обслуживании и настройке системы в течение жизненного цикла системы. Для СОВ уровень порога срабатывания тревоги, как правило, выставляется индивидуально в ходе отладки системы обнаружения, что вызывает сложность в настройке и необходимость привлечения высококвалифицированных специалистов для поддержания работоспособности системы на надлежащем уровне в процессе эксплуатации. Решение проблем интеллектуального задания пороговых уровней и повышения автономности работы СОВ является актуальным. В [13] авторами отмечается проблема методов обнаружения вторжений, которая заключается в выявлении вторжений, распределенных во времени. На функционирование СОВ также оказывает влияние фактор времени [7]. Факт обнаружения не предотвращает самого вторжения, поэтому несвоевременное информирование администратора о вторжении приводит к беспрепятственному осуществлению атаки злоумышленником на уязвимую сеть. Как следствие, одной из основных функций СОВ является безотлагательное информирование администратора безопасности. Этап обучения экспертной системы, во время которого определяются характеристики нормального поведения сети, характеризуется значительными временными затратами, что является дорогим и длительным процессом при внедрении СОВ на объекте, даже при применении обучаемых систем.
В научно-технической и исследовательской литературе часто встречаются разные названия систем охраны периметра сети или отдельных узлов сети: системы обнаружения атак (СОА) или системы обнаружения вторжений. Для устранения путаницы в терминологии сравним, что понимается под системами обнаружений в различных источниках. В статье [14] дается следующее определение для процесса обнаружения вторжений: «обнаружение вторжений является процессом мониторинга событий, происходящих в компьютерной системе или сети, и процессом анализа событий на предмет возможных инцидентов, которые являются нарушением или несут неминуемую угрозу нарушением компьютерной безопасности, политики безопасности и стандартным методам обеспечения безопасности». Таким образом, процесс обнаружения вторжений сводится к мониторингу и к сообщению об инцидентах администратору безопасности то есть сосредоточен на выявлении возможных инцидентов и их регистрации. Под вторжением, в отличие от атаки, будем понимать действия злоумышленника, находящее свое отражение в защищаемой системе в виде событий, направленных на получение не 23
санкционированного доступа в защищаемую систему, которые могут привести к нарушению доступности, целостности и конфиденциальности системы. Под атакой же будем понимать последовательность действий со стороны злоумышленника направленную на использование уязвимости в защищаемой системе с целью достижения своих целей. Таким образом, процесс вторжения находит свое отображение со стороны злоумышленника (атаки) в изменениях защищаемой системы. Далее в данной работе будет использоваться термин СОВ, вместо СОА.
Задачи, решаемые с помощью скрытых Марковских моделей
Недостатки информационного подхода заключаются в следующем [58]: — сложность трактуется через количество информации, а для подсчета количества информации необходимо знать модель источника информации, то есть априорную вероятность источника. Количество информации снова является вероятной величиной; — если рассматривать последовательности как цепочки символов, то количество информации можно оценить через длину цепочки. Происходит переход от задания гипотез к заданию языка представления, что удобнее для практического применения. Тем не менее, возникает необходимость решения проблемы определения языка представления.
Алгоритмическая сложность Колмогорова. Понятие сложности получило адекватную формализацию в алгоритмической сложности Колмогорова. Выбор лучшей модели производится на основании того, что если есть несколько программ, которые по строке а воспроизводят строку /?, то /и — наикратчайшая из них. В (15) рассчитывается относительная сложность. Выбор лучшей модели производится по формуле (16) [58]. К(ц\Р) = К(Р\») + К(»)-К(Р), (15) MMDL = агё_ min[/(/0 + K(fi I М)], (16) м где, /л — бинарная строка, соответствующая модели данных; /? — бинарная строка, соответствующая данным наблюдений; 1(/л) — длинна модели данных; КЦ5 /л) — соответствует длине наиболее короткой строки а, такой, что если она дана на вход программы /л, то программа напечатает на выходе строку Р; сумма l(ju) + K(fi\/Li) задает описание строки /?, обладающей минимальной длинной.
Недостатком можно считать то, что алгоритмическая сложность является не вычисляемой. Поэтому в решении практических задач используют практическую алгоритмическую сложность, вводят эвристические приемы для сокращения пространства гипотез благодаря знаниям о предметной области.
Положительными свойствами алгоритмического подхода являются [58]: — алгоритмическая полнота не накладывает никаких принципиальных ограничений на пространство гипотез; — статистическая согласованность с теорией Байеса; — возможность инкрементального обучения без ограничения на новые понятия, которые система может выучить. Это позволяет использовать полученный опыт для решения задач отражения атак в будущем.
В главе дается описание метода анализа последовательности данных. Предложено использование вероятностных моделей для обнаружения вторжений. Дан обзор вероятностных моделей, используемых для анализа последовательностей данных. Отмечаются положительные и отрицательные стороны рассмотренных вероятностных моделей. Обоснован выбор вероятностной модели в виде ДБС для использования в решении задач обнаружения вторжений, заключающийся в следующих преимуществах:
1. ДБС являются универсальными вероятностными моделями, способными описывать разнообразные процессы. В случае использовании различных ограничений, ДБС сводятся к более простым вероятностным моделям.
2. Расширяемость. ДБС может работать с большим числом переменных, при условии, что граф структуры редкий. 3. Вычислительная эффективность. В зависимости от топологии графа, уменьшение параметров модели может способствовать сокращению времени работы с ДБС.
4. Статистическая эффективность. По сравнению с не факторизованны-ми СММ с одинаковым числом возможных состояний ДБС с редкими связями между переменными требуют экспоненциально меньшего число параметров, чем СММ.
5. Интерпретируемость. Каждая переменная представляет собой определенную концепцию моделируемого процесса.
6. Нелинейность. При использовании табличного представления условных вероятностей достаточно легко перейти к представлению произвольных нелинейных явлений. Также возможно сделать вычисления эффективными для ДБС, когда переменные являются непрерывными и условные вероятности представлены распределением Гаусса.
В работе [54] приводится сравнение перечисленных выше в данной главе критериев качества сети. При сравнении в [60] критерии Байеса хорошо работают для больших наборов данных. Тем не менее, наиболее лучший результат показал критерий НМП. Большая часть критериев оценки основана на теории информации. Особое внимание следует уделять критериям НМП, МДО, ВИ. При этом ВИ сочетает лучшие качества БД и МДО. МДО имеет большую скорость работы. НМП является перспективным, так как использует понятие алгоритмической сложности, и уже сейчас показывает хорошие результаты на небольшом количестве данных.
В связи с отмеченными преимуществами, динамические байесовские сети обладают некоторыми недостатками: необходимость дополнительных построений в связи со сложной структурой; сложность в обучении; высокие вычислительные затраты.
Так же в главе приведены задачи, которые решаются с помощью вероятностного вывода в вероятностных моделях. Для решения задачи обнаружения вторжений предложено использовать вероятностный вывод. Описываются необходимые настройки для использования ДБС в решении прикладных задач.
Описание набора данных KDD 99
В главе описываются разработанные методы и модели, позволяющие использовать ДБС в решении задачи обнаружения вторжений. Дается описание разработанному методу анализа информативных характеристик сетевого трафика для выбора оптимальной структуры ДБС. Для того чтобы произвести настройку ДБС, требуется решить следующие задачи:
1. Произвести анализ данных обучения и выбрать размер вероятностной модели для обучения, что позволит избежать проблемы переобучения вероятностной модели в задаче обнаружения вторжений и сократить вычислительные затраты при использовании вероятностного вывода.
2. Задать модель переходов между скрытыми узлами во временных срезах. Модель переходов должна описывать непосредственно процесс вторжения, который является ненаблюдаемым и скрытым. С применением вероятностного вывода в ДБС производится разгадывание скрытых состояний процесса вторжения. Таким образом выявляется вероятность факта вторжения.
3. Разработать с учетом вероятностного вывода в ДБС метод поиска вторжений, обладающий способностью к обнаружению новых типов вторжения, априорно неизвестных на этапе обучения ДБС.
Разработанные модели и методы легли в основу предложенной структуры СОВ, основанной на ДБС.
При использовании ДБС требуется произвести ее обучение. Для этого необходимо выбрать существующие наборы для обучения и тестирования или создать подобные наборы самостоятельно. Наборы обучающих данных могут содержать избыточную информацию для обучения, поэтому сокращениє обучающих атрибутов позволяет повысить производительность применяемых методов и алгоритмов на практике. При тестировании и сравнении с другими СОВ разрабатываемых подходов для обнаружения сетевых вторжений часто применяют два стандартных набора данных: KDD 99 [61] и NSL-KDD. Указанные наборы данных состоят из протоколируемых свойств сетевого трафика, циркулирующего в компьютерной сети. Протоколирование свойств сетевого трафика основано на понятии сессий в компьютерных сетях. Для наборов данных под сессией будем понимать промежуток времени между запросом на соединение и запросом на разрыв соединения, в течение которого между двумя IP-адресатами посылаются потоки данных по определенному протоколу [59]. Каждая запись о сессии в наборе данных помечается как нормальная, или как вторжение, имеющее единственный тип атаки. Выбор наиболее информативных свойств сетевого трафика заключается в расчете зависимости свойств от проводимых вторжений.
Рассмотрим два набора данных KDD 99 и NSL-KDD. Сетевой трафик данных наборов протоколирован на основании 41 свойства, что является избыточным для использования байесовской сети и приводит к значительному увеличению вычислительной сложности обучения и вероятностного вывода. Поэтому количество используемых свойств необходимо сократить. Для решения проблемы избыточности свойств сетевого трафика предлагается метод анализа информативных характеристик сетевого трафика, призванный сократить число используемых свойств в БС.
В основу метода анализа информативных характеристик сетевого трафика положен критерий из теории информации — прирост информации (от англ. information gain, I). Прирост информации I(Y,X) атрибута X по отношению к атрибуту Y класса показывает снижение неопределенности относительно значения Y, когда известно значение атрибута X . Неопределенность значения Y измеряется через энтропию H(Y). Относительная неопределенность значения Y, когда известно значение X, определяется по условной энтропии 7 относительно X, H(Y\X). Если прирост информации равен энтропии атрибута 7, то есть 7(7,X) = H(Y), тогда два атрибута являются независимыми. Прирост информации рассчитывается по формуле (17) [62]:
Когда 7 и X представляют собой дискретные переменные, которые принимают значения в диапазоне {у\...у } и {хх...хк} соответственно, то энтропия атрибута 7 определяется выражением (18) [62]: H(Y) = -YJP(J = yi)-\og2{P(Y = yi)). (18) Условная энтропия 7 относительно X находится по формуле (19) [62]: H{Y\X) = -f4P(X = xi)-H(Y\X = xi). (19) 7=1 Кроме того, с учетом использования правила Байеса, согласно которому прирост информации определяется по следующей формуле (20): I(Y,X) = H(X) + H(Y)-H(XJ), (20) где Н{Х, 7) — совместная энтропия атрибутов X и 7, которая может быть найдена по формуле (21): H(X,Y) = -Т,Р(Х = х„7 = д.) log2P(X = xnY = Уі). (21) Поскольку прирост информации рассчитывается только для дискретных значений, непрерывные значения из набора данных следует дискретизиро-вать. В работе применяется метод дискретизации равных интервалов частот.
Существует два распространенных метода дискретизации непрерывных данных: 1. Квантование. Этот метод классифицирует данные на некоторое число категорий, имеющих равное количество единиц в каждой категории.
Равные интервалы частот. Этот метод задает диапазоны значений частот в каждой категории. Весь диапазон значений данных — от минимального до максимального — делится на равные части. Для этого непрерывное значение разбивают на равные диапазоны, используя равные интервалы частот [63]. Метод равных интервалов позволяет добиться лучшей классификации значений данных, чем метод разбития интервалов по значениям. Отметим возможные недостатки этих методов.
Метод квантования разбивает непрерывную функцию на равное число членов, принадлежащих своему классу. Это может привести к тому, что члены с одинаковыми значениями атрибутов помещаются в разные классы. Для устранения этого недостатка необходимо расширить границу класса, что противоречит сути данного метода.
Метод равных интервалов частот имеет очевидную проблему — наличие пустых классов, так как новые сформированные классы могут вообще не содержать точек данных и иметь нулевую частоту.
В методе анализа информативных характеристик сетевого трафика используется метод равных интервалов частот. В методе равных интервалов частот значения пространства разбиваются на произвольное число разделов, каждый раздел содержит одинаковое количество точек данных, то есть одинаковую частоту. Иными словами, для каждого раздела пространства атрибута диапазон содержит N экземпляров наборов данных. Если значение встречается более чем ./V раз в пространстве раздела, ему присваивается следующий раздел. Значения используемых интервалов частот для каждого из 41 свойства в расчетах показаны в табл. 2.
Алгоритмы обучения структуры байесовской сети на основании ограничений условной независимости
Статистика G2 является асимптотически распределенной, как и Xі с соответствующей степенью свободы. Для того чтобы вычислить статистики G2 и подсчитать возможные варианты переменных каждого теста, создается массив хранения каждого шаблона, а затем производится один раз обучающая выборка, чтобы вычислить каждый шаблон. При наличии более чем трех переменных формула относится к ожидаемому значению предельного количества I, J, К — значения первых трех переменных, полученных путем суммирования по всем другим переменным.
Число независимых ограничений, которые накладываются условной независимостью гипотезы на распределение, является экспоненциальной функцией порядка условного отношения независимости, а также зависит от числа различных значений каждой переменной. Поскольку число суммирования растет экспоненциально с ростом числа переменных, легко построить случай для гораздо большего количества ячеек, чем число точек данных. В этом случае большинство сумм в полном совместном распределении будет пустым, и даже непустые суммы могут иметь лишь небольшое значение. Может легко случиться так, что некоторые маргинальные суммы равны нулю, и в этих случаях число степеней свободы должно быть уменьшено в тесте. Для надежной оценки и тестирования размер выборки должен быть в пять раз больше числа сумм, а ожидаемые значения определяются при помощи гипотезы в стадии тестирования [89].
Во второй фазе алгоритм ММСРС пытается удалить ложные срабатывания, которые могут быть получены на этапе первой фазы. Это достигается путем повторного тестирования на независимость Ind(X; Т \ S) для некоторого подмножества S с СРС. Если условие независимости выполнено, то X удаляется из множества СРС, тем самым убирается ложное срабатывание.
Алгоритм ММСРС даже после второй фазы может вернуть ложно включенного кандидата в множество СРС. В этом случае СРС содержит неверную переменную в РСТ, которая не зависит от целевой Т. Для исправления ошибок во вспомогательном алгоритме ММСРС, алгоритм ММРС использует следующую процедуру. Для всех входящих переменных СРС рассчитывается повторно алгоритм ММСРС, но только в рамках сети, состоящей из переменных СРС. Поскольку соотношение родителей и потомков в PC должно быть симметричным, разрыв симметрии на выходе повторного алгоритма является показателем ложного срабатывания. Алгоритм ММРС проверяет, является ли Те ММСРС (X,D) для всех X є ММСРС(T,D). В случае если это не так, он удаляет X из СРС. С кэшированием всех вызовов в алгоритме ММРС общая вычислительная сложность построения «скелета» байесовской сети (то есть вызов ММРС со всеми целевыми переменными) оценивается как 0(\V\ -\РС\ ) [79], где PC — крупнейшее множество родителей и потомков по всем переменным в вершинах V, / — размер подмножества СРС.
Алгоритм простого «жадного» локального поиска является алгоритмом Hill-Climbing в пространстве ориентированных графов. Поиск начинается с пустого графа и производится с помощью функции оценки ЭБД. На каждом шагу используется один из возможных операторов: добавление ребра, удаление ребра или инвертирование ребра. Очевидно, что полученный граф должен оставаться ациклическим на каждом шагу, и оператор добавления ребра используется только тогда, когда переменные взаимно связаны. На каждом этапе операций с графом, оценка может возрасти до максимально возможной или уменьшиться, но если 15 итераций проходят без общего улучшения оценки, алгоритм останавливается — и возвращается лучший найденный граф. Список «запретов» (от англ. tabu) содержит последние 100 графов, которые были получены при помощи данного алгоритма. Они используются, чтобы избежать повторного рассмотрения решений для графов.
Преимущества, которые параллельные вычисления могут привнести в гибридные алгоритмы обучения, зависят от точности реализации алгоритма ограничения пространства структуры сети и алгоритма поиска в ограниченном пространстве.
Заметим, что динамика роста производительности центральных процессоров в персональных компьютерах отстает от роста производительности в графических процессорах видеокарт. Возможность использовать вычислительные возможности графических процессоров (от англ. graphics processing unit, GPU) появилась уже с начала 2000 г., однако широкого распространения не получила в связи со сложностью и неудобством использования. Появление программно-аппаратной архитектуры CUDA (от англ. compute unified device architecture) позволило избавиться от прошлых проблем. Использование технологии вычислений на основе графических видеокарт позволяет добиться значительного выигрыша по времени в вычислении. Так первое поколение графических процессоров обладало не более, чем 128 потоковыми процессорами. Для поколения Geforce 600 данной архитектуры можно предложить 1536 потоковых процессоров на одном графическом процессоре, которые возможно объединить парами на одной видеокарте. Благодаря возможности устанавливать до 4-х видеокарт на материнскую плату персонального компьютера, на практике возможно создание персонального компьютера, который способен работать с 12 288 потоковыми процессорами.
