Алгоритм отрицательного отбора

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

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

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

• Определим свое как совокупность S строк длины l над конечным алфавитом, которую необходимо защищать или контролировать. Например, в качестве S могут выступать программа, файл данных (любое программное обеспечение) или нормальная форма активности, подразделяемые на подстроки равной длины.

• Образуем набор детекторов R, каждый из которых не должен соответствовать любой строке в S. Вместо точного, или идеального, соответствия используем правило частичного соответствия, при котором две строки соответствуют друг другу, если и только если они совпадают, по крайней мере, в r следующих друг за другом позициях, где r – некоторый целочисленный параметр.

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

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

Впоследствии Хелман и Форрест предложили более эффективный алгоритм генерации детекторов с линейной зависимостью от размерности своего. Также были предложены другие методы генерации детекторов, имеющие разную степень вычислительной сложности.

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