The detection of network intrusion by evolutionary immune algorithm with clonal selection

Full Text

Введение. В последние годы большое внимание уделяется вопросам защиты информации (ЗИ), накапливаемой, хранимой и обрабатываемой в информационных системах (ИС). Системы обнаружения вторжений (СОВ) являются одним из обязательных компонентов инфраструктуры безопасности ИС. Особую роль в области информационной безопасности занимают вопросы создания систем превентивной ЗИ. Благодаря свойствам и принципам работы искусственной иммунной системы (ИИС) стало возможным применение вычислительных моделей ИИС в качестве эвристического метода СОВ для обнаружения сетевых вторжений [1; 2]. Иммунная система представляет собой сложную адаптивную структуру, основная задача которой заключается в распознавании и классификации клеток (или макромолекул) организма как «своих» или «чужих». ИИС строятся по аналогии с иммунной системой живого организма с учетом различного рода допущений. Как правило, при моделировании иммунной системы используют только два центральных положениях: антиген - антитело (детектор). В настоящее время представляют интерес следующие вычислительные модели иммунных систем: алгоритмы клональной селекции и негативного отбора, иммунные сетевые алгоритмы [3]. Алгоритм клональной селекции ИИС. Алгоритмы клональной селекции - класс алгоритмов, использующих методы клоновой селекции и теорию приобретенного иммунитета. Клонально-селекционная теория была сформулирована в 1957 г. независимо друг от друга М. Ф. Бернетом [4] в Австралии и Д. Тол-мейджем [5] в США. Она объясняет, как иммунная система противостоит чужеродным макромолекулам (антигенам). Согласно теории, у каждого индивидуума система клеток, вырабатывающих антитела, еще до встречи с антигеном содержит всю информацию, необходимую для синтеза любого из самых разнообразных антител. Антиген не доставляет этим клеткам-антителам информацию, а просто отбирает те клетки, которые синтезируют соответствующие ему антитела, и побуждает их к размножению и к усиленной выработке этих антител. Клетки, синтезирующие данный вид антител, принадлежат к одному клону, слагающемуся из всех потомков одной родоначальной клетки, которая в результате случайного процесса приобрела наследственную способность реагировать на данный антиген. Пока этот антиген не появился, клон остается относительно малочисленным. Присутствие антигена стимулирует размножение клона, способного синтезировать соответствующие антитела, и чем лучше распознавание антигена, тем большее количество потомства (клонов) будет сгенерировано [6]. В процессе репродукции отдельные клетки-антитела подвергаются мутации, которая позволяет им иметь более высокое соответствие к распознаваемому антигену - аффинность антител. Чем выше аффинность родительской клетки, тем в меньшей степени они подвергаются мутации, и наоборот. Обучение достигается путем увеличения относительного размера популяции и аффинности тех антител, которые доказали свою ценность при распознавании представленного антигена. Каждое новое поколение содер-жит более высокое соотношение характеристик, которыми обладают лучшие члены предыдущих поколений. Схема генерации детекторов на основе алгоритма ИИС с клональной селекцией приведена на рис. 1. По результатам проведенных исследований [7; 8] алгоритм клональной селекции ИИС позволяет обнаружить преднамеренные изменения в контролируемых данных. Основные отличия работ [7; 8] от представленных ранее - применение генератора псевдослучайных чисел на базе алгоритма Блюма-Блюма-Шуба [9] (Blum-Blum-Shub, BBS), процедуры формирования и мутации детекторов, которые в итоге позволили стабилизировать среднее количество ошибок I рода на один детектор и сделать их зависимыми от ресурсов, выделяемых алгоритму. Однако уровень ошибок I рода оставался достаточно высоким, таким образом появилась проблема формирования представительного множества высокоаффинных детекторов. В данной работе авторами предлагается повышение «качества» генерируемых детекторов за счет применения стратегии эволюционных алгоритмов. Модифицированный алгоритм ИИС с клональной селекцией. Вследствие того, что ИИС относится к классу биоинспирированных алгоритмов, для формирования детекторов предлагается замещение стандартного для алгоритма клональной селекции механизма репродукции и мутации детекторов на внешнюю оптимизационную процедуру, принцип работы которой основан на применении стратегии эволюционных алгоритмов. Эволюционный алгоритм в рамках выделенного ресурса исследует пространство поиска и формирует множество высокоаффинных детекторов, итеративно улучшая их качество путем реализации принципа наследования и естественного отбора. Полученное множество детекторов ИИС используют для обнаружения антигенов. С учетом применения эволюционной стратегии модифицированный алгоритм ИИС будет иметь вид, представленный на рис. 2. Генерация детекторов производится на блок антигенов, а не на каждый отдельный антиген. Генерация начальной популяции детекторов Получение обучающей популяции антигенов Выбор детекторов с наибольшей аффинностью Запись детекторов в базу данных детекторов Модификация (процедура мутации) Рис. 1. Обобщенная схема генерации детекторов алгоритмом клональной селекции ИИС 42 Математика, механика, информатика Ç Начало ) Ç Конец Загрузка блока антигенов размером z 4 у Генерация начальной популяции детекторов Расчет аффинности детекторов Эволюционная стратегия , Рис. 2. Обобщенная схема генерации детекторов модифицированным алгоритмом клональной селекции ИИС В ИИС детекторы и антигены имеют формальное представление в виде множеств элементов заданной длины над конечным алфавитом. Допустим, что мощность множеств детекторов D и антигенов A одинаковая и задана статично. В таком случае под аффинностью антигенов с детекторами понимается частичное или полное соответствие элемента aj є A элементу dj є D. Аффинность растет с увеличением количества идентичных элементов и рассчитывается в данной исследовательской работе с помощью метрики «процент согласования»: . / Г 1 ЛГ 1\ ^ m f1, f y = countx ([x] = d[x]) = y x=1 j0, else, где m=\a\ = \d\. Функция аффинности также является функцией пригодности для эволюционного алгоритма. Генерация начальной популяции детекторов осуществляется с помощью генератора псевдослучайных чисел на основе алгоритма BBS. На этапе селекции с помощью стратегии турнирного отбора формируется подмножество детекторов S œ D, которым разрешено участвовать в формировании нового поколения детекторов. На этапе рекомбинации с помощью генератора псевдослучайных чисел BBS выбираются два элемента из подмножества S, к которым применяется оператор многоточечного скрещивания по следующей схеме: а) в диапазоне [1; М-1] выбираются k позиций с помощью генератора псевдослучайных чисел BBS, при этом устанавливается следующее ограничение: k < /4-М, где М- число бит, выделенное под хранение значения детектора; б) сгенерированные значения k упорядочиваются в порядке возрастания и удаляются дублирующие значения; в) выбранные два элемента множества S обмениваются фрагментами, заключенными между соседними позициями k, в результате образуются детекторы-потомки. При этом допускается, что детекторы могут представлять собой некоторую совокупность закодированных значений нескольких параметров, тогда шаги «а»-«в» оператора рекомбинации выполняются для каждого параметра отдельно. Оператор рекомбинации выполняется |S| раз, в результате получаем множество детекторов-потомков мощностью, равной |D|. Оператор мутации выполняется для каждого де-тектора-потомка с вероятностью Pm = 1/y, при этом используется защищенное деление. Для формирования множества детекторов следующего поколения используется пропорциональная селекция (алгоритм «колесо рулетки»). 43 Вестник СибГАУ. 2014. № 4(56) Следующим этапом проверяется присутствие во множестве детекторов следующего поколения лучшего детектора, обладающего самым высоким значением аффинности (принцип элитизма). В случае отсутствия такового, происходит его добавление вместо самого низкоаффинного детектора. Процесс формирования детекторов продолжается до достижения критерия остановки работы. Критерием остановки выполнения алгоритма является достижение p поколений детекторов или 60%-го порога аффинности множества детекторов D к каждому антигену. Могут быть рассмотрены и другие значения порога аффинности, что является направлением для дальнейших исследований. Методика исследования эффективности модифицированного алгоритма ИИС с клональной селекцией. Для обучения и тестирования реализованного алгоритма использовались данные, собранные Калифорнийским университетом, в общедоступной базе образцов сетевого трафика KDD Cup 1999 [10] (далее - база KDD’99). Отдельная запись KDD’99 представляется соответствием параметров состояния системы с записью о типе атаки или ее отсутствии. В единичную запись входит 41 параметр, каждый из которых характеризует состояние системы. В данной работе используется сокращенный список из 13 ключевых параметров [11]. В работе представлен фрагмент результатов исследования для данных класса Normal и данных типа Neptune класса атак DoS. Для преобразования исходных данных базы KDD’99 к унифицированному виду использовался рефлексивный двоичный код Грея [12]. Методика исследования эффективности ИИС заключается в последовательном выполнении следующих шагов: 1. Загрузка штатных событий Normal, выбранных случайно из базы KDD’99 во множество G с помощью генератора псевдослучайных чисел BBS мощностью x, где x є [100, 500] и изменяется с шагом т = 100. 2. Загрузка нештатных событий (антигенов) Neptune, выбранных случайно из базы KDD’99 во множество A с помощью генератора псевдослучайных чисел BBS мощностью z, где z є |^0, у2 J и изменяется с шагом т2 = 5 . 3. Формирование множества детекторов D мощностью 15, 20, 25 % от множества нештатных событий A итерационно с помощью алгоритма клональной селекции (соответственно ID = A-15 %, DI = A • 20 %, |D = A • 25 %). 4. Формирование множества тестовых данных E из случайно выбранных элементов множества штатных событий G и нештатных событий (антигенов) A, так что IE = ID = x, где x є [100, 500] и изменяется с шагом т1 = 100. Следует отметить, что для каждого значения мощности множества тестовых данных E количество элементов aj є A в E составляет последовательно 25, 50, 75 и 100 % от A. 5. Множество тестовых данных E обрабатывается алгоритмом поиска нештатных событий с помощью элементов множества детекторов D. Результатом работы алгоритма является количество обнаруженных антигенов в контролируемом множестве тестовых данных E, количество ошибок I рода (штатное событие детектировалось как нештатное (ложное срабатывание)) и II рода (нештатное событие детектировалось как штатное), усредненные по многократным запускам. Результаты экспериментальных исследований разработанного алгоритма. На рис. 3-5 представлен сравнительный анализ результатов алгоритма клональной селекции ИИС (Алгоритм 1) с результатами работы алгоритма клональной селекции ИИС с применением эволюционной стратегии (Алгоритм 2) в зависимости от размера блока антигенов z. 1-1 С'1 -і Алгоритм Алгоритм s CL. О 5 È. С и < |D|-|A|-15% Р|-|А -20% < I ^ |D|-|А|-25% ■ Среднее количество ошибок I рода на один детектор Рис. 3. Среднее количество ошибок I рода, приходящееся на один детектор при z = 10 ІІІІІІ S Си о Г'1 ? s Си £ си о 1 Си О І Си о Г'1 ? S Си о и $ і и_ 1 1 |D|-|A|-15K> р|-|Л|-20% |D|-|A|-25K> ■ Среднее количество о шибок I рода на один детектор Рис. 4. Среднее количество ошибок I рода, приходящееся на один детектор при z = 20 iiiiii Алгоритм 11 Алгоритм 2 Р|-|Л|-15% Алгоритм 11 Алгориги2 Алгориїм 1 Алгоріггм 2 р-|Л-2П% |Л|“|Л|-25% ■ Среднее mrnmecTRfl оппгбок Т рода на одтгп детектор Рис. 5. Среднее количество ошибок I рода, приходящееся на один детектор при z = 30 44 Математика, механика, информатика Результаты экспериментов получены в процессе обнаружения антигенов в контролируемом множестве тестовых данных E с помощью элементов множества детекторов D, в соответствии с методикой исследования эффективности, усредненных по многократным запускам. Количество запусков равно 100. Для сравнительного анализа были выбраны данные по среднему количеству ошибок I рода, приходящихся на один детектор. Ошибок II рода в процессе исследования обнаружено не было. По результатам экспериментов (рис. 3-5) можно сделать вывод, что алгоритм клональной селекции ИИС с применением эволюционной стратегии позволяет снизить количество ошибок I рода, приходящихся на один детектор. При этом увеличение мощности множества детекторов D закономерно приводит к уменьшению количества ошибок I рода независимо от размера блока антигенов z. Разработанный эволюционный иммунный алгоритм клональной селекции отличается от известных тем, что для реализации стохастической процедуры поиска авторами предложено применение генератора псевдослучайных чисел на основе алгоритма Блюма-Блюма-Шуба, а для формирования высокоаффинных детекторов предлагается замещение стандартного для алгоритма клональной селекции механизма репродукции и мутации детекторов на внешнюю оптимизационную процедуру, принцип работы которой основан на применении стратегии эволюционных алгоритмов. Предложенные модификации позволяют повысить эффективность алгоритма по критериям «Среднее количество ошибок I рода, приходящееся на один детектор» и «Среднее количество ошибок II рода, приходящееся на один детектор» по сравнению с классическим алгоритмом клональной селекции. Сравнение результатов тестирования модифицированного алгоритма ИИС с результатами работы алгоритмов, представленных в других работах на базе KDD’99. Для оценки эффективности разработанного авторами алгоритма клональной селекции ИИС с применением эволюционной стратегии - эволюционного иммунного алгоритма клональной селекции - проведем сравнительный анализ результатов работы алгоритма с результатами работы различных алгоритмов на тестовом множестве KDD’99. На рис. 6 представлены результаты сравнительного анализа с нейросетевой системой обнаружения и распознавания сетевых атак [13] (лаборатория «Искусственные нейронные сети» Брестского государственного технического университета) для моделей с различными архитектурами искусственных нейронных сетей. На рис. 7 представлены результаты сравнительного анализа с алгоритмом на основе решающих деревьев. В основе алгоритма - модель, предложенная А. А. Брюховецким и др. (Севастопольский национальный технический университет), по обнаружению уязвимостей в критических приложениях на основе решающих деревьев [14]. В качестве критериев эффективности используются: уровень выявления атак (Detection Rate, DR), уровень пропуска атак (False Acceptence Rate, FAR), рассчитываемые по следующим формулам: TP ..... FP DR =- •100%, FAR =- •100%. TP + FN FP + TN где TP (true positive) - количество правильно определенных образцов сетевых соединений, содержащих атаку; FP (false positive) - количество образцов сетевых соединений, содержащих атаку, определенных системой как нормальные (пропуск атаки); TN (true negative) - количество правильно идентифицированных системой образцов нормальных сетевых соединений; FN (false negative) - количество нормальных образцов сетевых соединений, определенных системой как содержащие атаки. На рис. 8 представлены результаты сравнительного анализа с результатами исследований H. M. Shirazi и другими работами [15]. H. M. Shirazi и др. предложили модель СОВ, в которой анализ собранных данных осуществляется с помощью алгоритма, построенного на основе меметического алгоритма и сетей Байеса. В качестве критерия эффективности использовался уровень выявления атак (DR). 160 140 120 100 80 60 40 20 0 і 47,75 41,9 - 113.771 1 19>9 1 99.98 99,8 99,95 100 - Модель L Модель 2 Модель 3 Эволюционный иммунный алгоритм ■ Количество ошибок] рода (%) ■ Количество обнаруженных атак (%) Рис. 6. Сравнительный анализ результатов работы нейро-сетевой системы и разработанного эволюционного иммунного алгоритма клональной селекции Рис. 7. Сравнительный анализ результатов работы алгоритма на основе решающих деревьев и разработанного эволюционного иммунного алгоритма клональной селекции 45 Вестник СибГАУ. 2014. N 4(56) Рис. 8. Сравнительный анализ результатов исследований H. M. Shirazi с другими работами и эволюционным иммунным алгоритмом клональной селекции Из рис. 6-8 видно, что уровень обнаружения атак и количество ошибок I и II рода сопоставимы с аналогами, базисы которых построены на различных методах искусственного интеллекта. Заключение. Замещение стандартного для алгоритма клональной селекции механизма репродукции и мутации детекторов на внешнюю оптимизационную процедуру позволило усовершенствовать процесс генерации высокоаффинных детекторов и снизить количество ошибок I рода при обнаружении вторжений. В целом же, проанализировав полученные результаты, можно сделать вывод о том, что разработанный алгоритм позволяет обнаружить преднамеренные изменения в контролируемых данных и является перспективным базисом для разработки и совершенствования алгоритмического обеспечения эвристических методов анализа данных в задаче обнаружения сетевых вторжений в ИС, например, коллективами интеллектуальных информационных технологий или многоагентными системами, где разработанный эволюционный иммунный алгоритм клональной селекции является одним из агентов. Построение алгоритмического обеспечения СОВ на базе эволюционного иммунного алгоритма клональной селекции позволит повысить эффективность работы СОВ в ИС с точки зрения адаптации к неизвестным угрозам ИБ. Благодарности. Работа поддержана грантом Президента молодым кандидатам наук, договор № 14.124.13.473-МК от 04.02.2013 г. Acknowledgements. This work was financially supported by the grant of the President of the Russian Federation for young scientists, the agreement № 14.124.13.473 - МК, d.d. 04.02.2013. Библиографические ссылки

About the authors

Vadim Genadjevich Zhukov

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: zhukov.sibsau@gmail.com. Shiracom@mail.ru
Cand. Sc.-Ing., Docent, Docent of the Information technology security department

Tatyana Andreevna Salamatova

Siberian State Aerospace University named after academician M. F. Reshetnev

Email: shiracom@mail.ru
Master’s Degree student

References

Supplementary files