Применение генетических алгоритмов

Генетические алгоритмы — представители класса алгоритмов, называемых эволюционными. Эволюционные алгоритмы опираются на концепцию естественного отбора Ч. Дарвина для оптимального решения проблем. Идея генетического алгоритма заимствована у живой природы и основана на принципах эволюции естественного отбора. Генетический алгоритм был разработан Голландом выдвинул ряд гипотез и предложений, полагающих глубже понять природу ГА. В общем случае ГА использует подход, наблюдаемый в живой природе: естественный отбор, приспособляемость к изменившимся условиям среды, наследование потомками жизненно важных свойств от родителей.

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

Если на шаге k алгоритма имается популяция G (k), состоящая из N строк Sik, то средняя целостность популяции может быть определена следующим образом:

Fср[ G (k)]=1/N?F (Sik), i=1,2,…, N.

Генетический алгоритм осуществляет переход от популяции G (k) к популяции G (k+1) таким образом, средняя целостность составляющих ее строк увеличивалась. Можно рассматривать случай, когда количество элементов (строк) в новой популяции N (k+1)=?N (k), где? — коэффициент новизны популяции. Если? < 1, то популяция будет перекрывающейся. Если? =1б то популяция будет перекрывающейся, т. е. подвергается полному обновлению.

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

Оператор селекции — для формирования новой популяции с максимальным значением целевой функции. Операторы селекции строятся таким образом, чтобы с нулевой вероятностью любой элемент популяции мог бы быть выбран в качестве «родителя». Иногда допускается случай, когда один член популяции является родителем один и родителем два.

Оператор скрещивания — по имеющимся членам популяции ki и kj строится новое поколение kj строиться новое решение km. Существует множество версий этого оператора. Одним из простейших является однородный оператор, который по членам ki и kj строит решение km, присваивая каждой координате этого члена с вероятностью 0,5 соответствующее значение одного из родителей. Поэтому какая — то координата у родителей совпадает, то новый элемент бедующей популяции унаследует это значение. Возможен случай, когда для получения нового элемента используется более двух «родителей».

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

Общая схема генетического алгоритма показана на рис. 4.8.

Генетический алгоритм работает с представленными в конечном алфавите строками S конечной длины n, которые используются для кодирования некоторого множества альтернатив W.

Каждая строка представляет собой упорядоченный набор из n элементов: S={s1,s2,…sn }, каждый из которых может быть задан в своем собственном алфавите Vi, i=1,2,…, n.

Для работы ГА необходимо на множество строк задать неотрицательную функцию F (S), определяющую «ценность» строки S. Алгоритм происходит поиск строки, для которой F*(S)=arg max F (S).

Если элемент wпри отражении исходного множества W на множество строк был составлен строке S.

Популяция G (k) на шаге k представляет собой конечный набор строк.

G (k)=(s1k, s2k,…snk).

где N — размер популяции. Отметим, что строки в популяции могут повторятся.

Рассмотрим пример, поясняющий работу операторов ГА.

Пусть в качестве родителей выбраны следующие хромосомы (N=16, для наглядности заменим нули и единицы на буквы):

• (a, b, b, b, a, b, b, a, a, a, a, b, b, b, a, a, a)
• (х, y, y, x, x, x, x, y, x, x, y, y, x, x, y, x, y)

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

• (a, b, b, b, a, b, b, a, a, y, y, x, x, y, x, y)
• (x, y, y, x, x, x, y, x, x, a, a, b, b, b, a, a)

Таким образом, для первой хромосомы все гены на позициях 1−9 останется, а гены на позициях с 10 по 16 заменяются соответствующими генами второй хромосомы. Во второй хромосоме останутся гены на позициях 1−9, а гены позиций 10−16 заменяются генами первой хромосомы.

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

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

Схема анализа на основе генетических алгоритмов включает в себя две стадии:

• 1) Кодирование решений проблемы строкой бит;
• 2) Нахождение значений функции пригодности для проверки каждого индивидуума популяции, удовлетворяющей некоторому эволюционному критерию.

В системе GASSATA генетические алгоритмы применяются к проблеме классификации системы событий с использованием множества векторов гипотез {h} размерностью n. По определению h=1, если оно представляет атаку, и h=0, если атака отсутствует.

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

В приведенных экспериментах средняя вероятность точного обнаружения реальной атаки составила 0,996, а средняя вероятность ложных срабатываний -0,0044. Время, требуемое для настройки фильтров, было незначительным множество из 200 атак потребовало для системы 10 мин 25 с для оценки записей аудита, генерируемых средним пользователем за 30 мин интенсивного использования системы.

Рассмотрим один из примеров применения ГА к обнаружению вторжений [73], когда ГА применяется для создания простых правил поиска атак в сетевом трафике. Эти правила используются, чтобы отличить нормальные сетевые соединения от аномальных. Аномальные события вероятно связаны с вторжением. Правила хранятся в базе правил в следующей форме:

If (условие) then (действие) Условие означает совпадение между текущим соединением и правилом СОВ. Действие определяется ПБ организации.

Правило для определения аномального соединения может быть следующим.

If {соединение содержит следующую информацию:

Адрес источника:10.0.0.15;

Адрес назначения:192.168.0.5;

Порт назначения:555;

Продолжительность соединения: 7,5 секунд}.

Then {разорвать соединение}.

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

В качестве исходных данных выбираются те поля сетевых пакетов, которые связаны с соединениями. Для простоты рассмотрим ограниченное число атрибутов, которые представлены ниже в табл.4.7.

If {соединение: адрес источника: 10.0???;

Адрес назначения: 192.168.176+?.?;

Порт источника: 33 337; порт назначения: 80;

Время соединения: 482 с.;

Соединение закончено инициатором; протокол TCP;

Инициатор послал: 7320 байт;

Приемник получил: 38 891 байт}.

Then {разорвать соединение}.

Преобразуем данное правило в форму хромосомы (для наглядности вставим пробелы, разделяющие поля):

(0,а, 0,0,-1,-1,-1, с, 0, а, 8, b, -1, -1, -1, 3,3,3,3,7, 0,0,8,0, 0,0,0,0,0,4,8,2, 1,1,2,0,0,0,0,0,0,7,3,2,0, 0,0,0,0,0,3,8,8,9,1).

В данном представлении для задания адресов использовалось шестнадцатеричное представление и знаки «?» и «*» замены на -1. Видно, что данная хромосома содержит 57 генов.

Это правило проверяется на архивных записях сетевых соединений. Если правило способно обнаружить аномальное поведение, то при получении новой популяции его хромосоме дается. Если же это правило укажет на нормальное соединение, то его хромосома «наказывается».

Так как одно правило не может обнаружить все нормальные соединения, необходима популяция. Начальная популяция формируется случайным образом. Последовательно применяются операторы ГА. Применение функции оценивания позволяет научным правилам смещается к правилам, которые соответствуют нормальным соединениям.

Рассмотрим некоторые параметры ГА данного эксперимента.

Функция оценки определяет расхождение и соответствие. Расхождение вычисляется в зависимости от того, что соответствует ли поле соединения множеству данных до классификации, и умножается на все соотвующего поля:

Расхождение =? соответствующие х вес Где суммирование ведется по всем 57 генам.

Значение весов задаются в следующем порядке (по убыванию):

Адрес назначения, адрес источника, порт назначения, время соединения, количество посланных инициатором соединения, протокол, порт источника (такое расположение полей соответствует порядку полей, фиксируемых анализаторами, сниферами). При соответствии значения поля правилу устанавливается значение 1, при несоответствии — 0).

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

?=¦расхождение — уровень подозрительнсоти¦

Ранжирование показывает, легко ли идентифицируется аномалия. Через ранжирования определяется величина наказания:

Наказание =(??Ранг)/100.

Это позволяет вычислить сходство хромосомы:

Сходство =1 — наказание.

Видно, что значение сходства находится в интервале от 0 до 1.

Используется ГА, необходимо найти локальные максимумы (множество хороших решений) вместо глобального максимума (одного наилучшего решения), так как множество правил обнаружения лучше одного правила.

Для нахождения множества локальных правил можно использовать технологии ниш. Данная технология также заимствована из живой природы. Она основывается на том, что внутри каждого окружения есть различные пространства, в которых могут существовать различные виды жизни. Подобное тому, ГА может устанавливать разброс каждой популяции в одном многомодульном домене, который соответствует доменам, требуемым для идентификации множества оптимумов.

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

Особенностью применения операторами мутации для рассмотренной задачи обнаружения является возможность выхода поля хромосомы за разрешенные переделы, например выход значения адреса за значение 255. Это обстоятельство требует контроля результатов применения операторов. К числу других особенностей необходимо отнести следующее: число хромосом в различной популяции, вероятности скрещивания и мутации, а также допустимое число поколений. Эти и другие особенности приводят к тому, что использование ГА для обнаружения вторжений в настоящий момент носит только исследовательский характер, хотя результаты показывает перспективность данного подхода.