Методика обнаружения полиморфных вирусов на основе искусственных иммунных систем и генетических алгоритмов

Размещено на http://www.allbest.ru/

Методика обнаружения полиморфных вирусов на основе искусственных иммунных систем и генетических алгоритмов

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

1. Проблематика исследования

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

Вся классификация в иммунной системе человека на «свои» и «чужие» клетки основана на химических связях, которые образуются между белковыми цепями. В работе смоделированы белковые цепи в виде HEX-строк определенной длины. Множество всех возможных строк делится на два подмножества: «свои» и «чужие». Перед искусственной иммунной системой стоит задача классификации строки, то есть отнесения ее к одному из двух подмножеств. В подобной модели теоретически возможны два вида ошибок - «чужая» строка классифицируется как «своя», и «своя» строка классифицируется как «чужая». [2] Целью разработанной ИИС является снижение уровня этих ошибок. Данная модель применима в задачах обнаружения вирусов. [7,8]

2. Иммунная система

Иммунная система состоит из множества клеток и молекул, которые взаимодействуют между собой различными способами для обнаружения и уничтожения инфекционных патогенов (болезнетворных микроорганизмов). Поверхности клеток иммунной системы покрыты рецепторами, некоторые из которых химически связаны с патогенами, некоторые - с другими клетками ИС: все это необходимо для построения сложной модели сигнализации, которая вызовет иммунный ответ. Большинство клеток ИС циркулируют по всему организму через кровь и лимфу, образуя систему распределенного обнаружения и реагирования, где нет централизованного управления. Обнаружение и устранение патогенов является результатом работы триллионов клеток, взаимодействующих с помощью простых, локализованных правил. Следствием этого является то, что ИС очень устойчива к выходу из строя отдельных компонентов и атак на саму систему. [7,9]

2.1 Лимфоциты (детекторы)

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

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

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

1) Расстояние Левенштейна - это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. Расстояние Левенштейна для бинарных строк определятся как сумма числа позиций, в которых символы строк различны.

2) Подсчет значения r - максимального числа смежных бит. Данный подход нашел широкое применение в биологических исследованиях, суть его заключается в нахождении максимальной одинаковой подстроки. В работе r задано таким образом, чтобы совпадающая подстрока была длиной не более r.

Активация лимфоцита произойдет тогда и только тогда, когда заранее заданное количество рецепторов среагируют на патоген.

2.2 Подготовка системы обнаружения, иммунологическое обучение клеток

иммунный математический детектор

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

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

2.3 Память иммунной системы

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

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

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

3. Генетические алгоритмы

Для повышения эффективности работы искусственной иммунной системы в работе предлагается использовать класс генетических алгоритмов, которые представляют собой эвристические методы оптимизации, основанные на определении лучших представителей своей популяции, наиболее приспособленных к текущим условиям, и передачи генов будущим потомкам. На первые роли выходят такие операторы как скрещивание, селекция, мутация и кроссинговер. [1,3-6]

3.1 Кроссинговер

Под кроссинговером понимают обмен участками гомологичных хромосом. Существует два подхода к реализации этого оператора:

- создание случайной маски;

- склеивание родительских хромосом относительно точки (одноточечный кроссинговер).

Оператор кроссинговера (создание случайной маски) применяется к двум детекторам-родителям (обозначим их родитель1 и родитель2), на выходе получается новый детектор-потомок. На первом этапе кроссинговера для нового детектора составляют маску длиной, равной количеству бит, которые потомок должен унаследовать от родителей. Маску заполняют случайными значениями: 1 или 0. Если значение маски равно 1, то данный бит унаследуется от первого родителя, иначе - от второго. В табл. 1 приведен пример набора родительских бит и бит потомка.

Таблица 1 - Набор родительских бит и бит потомка

3.2 Мутация

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

- одноточечный оператор мутации;

- многоточечный оператор мутации;

- инверсия k - случайных бит;

- инверсия бит относительно выбранной точки разреза.

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

Многоточечный оператор мутации заключается в выборе произвольной точки строки, которой будет присвоен индекс 0, всем точкам справа от нее будут присвоены положительные индексы от 1 до n, где n - длина бинарной строки. После этого значение точки с индексом i, где i - нечетное число, меняется на значение точки с индексом i+1. Пример подобной мутации относительно 4-го бита исходной строки приведен в табл. 2.

Таблица 2 - Многоточечный оператор мутации

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

Таблица 3 - Набор бит до мутации и после мутации

Метод инверсии бит относительно выбранной точки разреза заключается в выборе точки разреза и инвертировании значения бит справа от выбранной точки.

3.3 Селекция

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

- метод колеса рулетки;

- элитная селекция;

- турнирная селекция.

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

P = , (1)

где - значение функции аффинности для данного детектора,

- сумма значений функций аффинности всех детекторов.

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

Под функцией аффинности или показателем приспособленности будем понимать отношение, представленное формулой (2):

K = , (2)

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

Соотнесем описанные выше компоненты иммунной системы со смоделированными компонентами и свойствами искусственной иммунной системы. Результат представим в виде таблицы 4.

Таблица 4 - Соответствие компонентов и свойств ИС и ИИС

4. Методика обнаружения вирусов на основе ИИС и ГА

1) Генерация начальной популяции детекторов. На первом шаге алгоритма определяется длина строки детектора и происходит ее генерация случайным образом на основе алгоритма Блюм - Блюма - Шуба.

2) Иммунологическое обучение детекторов. Задается период обучения детекторов T, во время которого детекторы взаимодействуют друг с другом и гарантированно невредоносными файлами. Детекторы, переходящие в активное состояние, подлежат «программной смерти», таким образом детекторы обучаются быть толерантными по отношения к себе.

3) Функционирование детектора в системе:

3.1 Детектор выбирает случайным образом файл, который не был им проверен, и начинает его сканирование.

3.2 Если пороговое значение превышено не было, то переход на шаг 3.1.

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

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

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

4) Вычисление функции аффинности для каждого детектора на основе формулы.

5) Формирование выборки детекторов, к которым будет применен оператор многоточечного кроссинговера.

6) Кроссинговер. Получение новой выборки детекторов, к которой будет применен оператор мутации.

7) Мутация. Задается число k - количество случайных бит, которые будут выбраны случайным образом у детектора и будут инвертированы.

8) Поддержание постоянной численности популяции детекторов, «программная смерть» для детекторов с низким показателем функции аффинности.

9) Занесение эффективных детекторов в память.

10) Возврат на шаг 3.

Рисунок 1 - Процедура повышения меры аффинности популяции детекторов

Процедура повышения меры аффинности популяции детекторов представлена на рисунке 1. На рисунке 2 представлен жизненный цикл детектора.

Рисунок 2 - Жизненный цикл детектора

Таким образом, описанная искусственная иммунная система представляет собой высоко распараллеленную и распределенную среду, большое количество детекторов (лимфоцитов) делают систему стабильной, а отсутствие единой точки выхода из строя (является децентрализованной) делает ее надежной. Фундаментальные компоненты и свойства ИИС говорят о ее применимости для задач распознавания полиморфных вирусов. Также стоит отметить результативность использования класса генетических алгоритмов: применение концепций генетических операторов позволяет увеличить скорость обучения детекторов, а, следовательно, и эффективность работы самой системы.

Литература

1. Частикова В.А. Идентификация механизмов реализации операторов генетического алгоритма в экспертных системах продукционного типа //Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. 2012. № 75. С. 308-320.

Частикова В.А., Картамышев Д.А. Искусственные иммунные системы: основные подходы и особенности их реализации //Научные труды Кубанского государственного технологического университета. 2016. № 8. С. 193-208.

2. Частикова В.А. Исследование основных параметров генетического алгоритма метода генетических схем в интеллектуальных системах, основанных на знаниях // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета. 2011. № 69. С. 151-163.

3. Частикова В.А. Оптимизация процессов поиска решений в интеллектуальных системах обработки экспертной информации на основе генетических алгоритмов // Диссертация на соискание ученой степени кандидата технических наук / Кубанский государственный технологический университет. Краснодар, 2005.

Размещено на Allbest.ru