Способ повышения скорости проверки сигнатур

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

На сегодняшний день в области информационных технологий одной из основных проблем являются компьютерные преступления. Количество преступлений растет с каждым годом. Задачу защиты от внешних и внутренних атак пытаются решить системы выявления вторжений [1-2]. Разработано более десятка различных классов систем, среди которых наибольшее распространение получили сетевые (Network Based) и хостовые системы выявления вторжений (Host Based).

Основнойнедостатокхостовыхсистемвыявле-ния вторжений заключается в низкой производительности, которая обусловлена необходимостью обработки большого объема аудита и проверкой большого числа сигнатур [3-4]. В данной статье предлагается один из вариантов увеличения производительности систем за счет повышения скорости проверки сигнатур.

Тривиальный вариант проверки сигнатур анализирующей компонентой состоит в том, что компонента последовательно просматривает все сигнатуры. У каждой сигнатуры пропускается уже активизированная часть и определяется первое неактивизированное событие (или несколько событий). Если событие, обрабатываемое на текущий момент, совпадает с первым неактиви-зированным событием сигнатуры, то сигнатура увеличивает длину активизированной части. Если считать, что пропуск активизированной части сигнатуры не предполагает последовательную проверку ее событий, а выполняется непосредственным переходом к неактивизированным событиям, то для проверки всех сигнатур потребуется следующее время:

NNn

Т = Z tB + Z tC + Z tA , (1)

где TТ – время проверки всех сигнатур по тривиальному алгоритму; tВ – время выбора неакти-визированного события в сигнатуре; tС – время сравнения обрабатываемого события с неакти- визированным событием сигнатуры; tА – время активизации события сигнатуры; N – общее количество сигнатур; n – число сигнатур, активизируемых на текущем шаге.

Количество сигнатур, активизируемых на текущем шаге ( n ), не может быть больше общего количества сигнатур ( N ). Чаще всего n много меньше N . Поэтому при обработке очередного события не требуется проверять весь список сигнатур, достаточно проверить только те сигнатуры, которые связаны с данным событием. Для этого предлагается использовать список ожидаемых событий.

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

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

n

T O = ∑ t А , (2)

где T_O – время проверки сигнатур по алгоритму с использованием списка ожидаемых событий.

После обработки очередного события возможно изменение состава активизированных сигнатур и длины активизированной части сигнатур. Это требует корректировки списка ожидаемых событий. Суммарное время работы алгоритма с использованием списка ожидаемых событий

Рис. 1. Массив ожидаемых событий

(проверка плюс корректировка списка), с учетом принятых допущений, следующее:

nnn

T o = E t а + E t B + E t д ,         (3)

где t_Д – время добавления сигнатуры в список события (формирование списка ожидаемых событий).

Наихудший случай тривиального алгоритма: все сигнатура активизируются. Время проверки

NNN

T t max = E t B + E t c + E t А .         (4)

Наилучший случай тривиального алгоритма: ни одна сигнатуры не активизируются. Время проверки:

NN

T t min = E t B ⁺ E t c .            (⁵)

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

NNN

T o max = E t а + E t B + E t д .        ⁽⁶⁾

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

T О ^min = 0.                   (7)

Сравнивая (1) и (3), можно отметить, что различия заключаются во времени t_С (1) и t_Д (3).

Если положить, что tС и tД равны, то получается, что время работы алгоритма с использовани- ем списка ожидаемых событий меньше времени работы тривиального алгоритма. Время становится одинаковым только в наихудшем случае. Следовательно, алгоритм с использованием списка ожидаемых событий будет работать быстрее тривиального алгоритма.

Если t_С меньше t_Д , то в наихудшем случае тривиальный алгоритм работает быстрее. Графически зависимость времени работы алгоритмов от количества активизируемых сигнатур показана на рис. 2.

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

Для того чтобы оценить величину n’ операцию сравнения события с неактивизированным событием сигнатуры, обрабатываемого на текущем шаге, упрощенно представим как одну команду сравнения (время t_С в формуле (1)). Операцию добавления сигнатуры в список ожидаемых событий, для реализации в виде статического массива событий и набора коллекций, со ссылками на сигнатуры (см. рис. 1), упрощенно представим как одну команду сохранения указателя на сигнатуру

Рис. 2. Зависимость времени работы алгоритмов от количества активизируемых сигнатур

и одну команду увеличения счетчика сигнатур в коллекции (время t_Д ). Операции выбора (время t_В ) и активизации события сигнатуры (время t_А ) – это команды сравнения и присвоения значения. В этом случае, если положить, что время выполнения команд приблизительно равно, получается, что:

• -    время добавления сигнатуры в список (время t_Д ) в два раза больше времени сравнения события (время t_С );

• -    минимальное времяработы тривиального алгоритма относится к максимальному времени как 2:3.

Согласно предложенным допущениям значение n’ равно

n'=2N.

По формуле (8) видно, что значение n’ равно 2:3 от общего количества сигнатур N . Это означает, что если в списке ожидаемых событий в список к одному событию попадут менее 2/3 всех сигнатур, то время работы данного алгоритма будет меньше времени работы тривиального алгоритма.

Если в какой-то момент времени появляется событие, соответствующее наихудшему случаю, к которому привязаны все сигнатуры (время определяется формулой (6)), то ко всем остальным событиям в списке больше не привязана ни одна сигнатура. То есть, очень велика вероятность, что следующий шаг будет соответствовать наилучшему случаю – см. формулу (7). Суммарное время на обработку двух событий с использованием списка ожидаемых событий меньше суммарного времени работы тривиального алгоритма.

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

V = 2/3 = 0,67; (9)

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

Вероятность получения временных характеристик худших, чем у тривиального алгоритма, определяется формулой

Ф = 2 * y , (10)

где ϕ – вероятность получения худших временных характеристик; λ – вероятность появления события, к которому привязаны более 2:3 всех сигнатур; γ – вероятность превышения процента допустимых случаев, когда суммарное время работы алгоритма с использованием списка ожидаемых событий меньше суммарного времени работы тривиального алгоритма.

Применение списка ожидаемых событий позволяет сократить число проверяемых сигнатур, за счет исключения из проверки тех из них, которые на текущем шаге не могут быть активизированы. В случае применения списка время проверки сигнатур сокращается и определяется формулой (3). Максимальное время проверки определяется формулой (6), а минимальное время – формулой (7). Согласно проведенным расчетам получает-

ся, что применение списка ожидаемых событий практически всегда сокращает время проверки сигнатур, даже с учетом накладных расходов на поддержание списка. Вероятность получения худших временных характеристик невелика и определяется формулой (10). 2.    Астахов А. Актуальные вопросы выявления сетевых атак // Jet Info, 2002, №3. –28 с. 3.    Гриняев С. Системы обнаружения вторжений. Обзор зарубежных систем обнаружения вторжений // Byte, 2001, №10. http://www. bytemag. ru/?ID=600494 Литература 1. Галатенко А. Jet Info (Информационный бюлле- 4. Костров Д.. Системы обнаружения атак// Byte, 2002, №8. http://www.

тень) // Активный аудит, № 8 (75), 1999.– 28 с.