Ссылка на первую часть статьи.

Сигнатурные методы детектирования в IDS

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

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

Но как быть если у атаки несколько шагов? Что искать в трафике? И как?

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

На первый взгляд довольно просто.

Все становится не так радужно, когда дело доходит до реализации.

Давайте пройдемся по реализациям некоторых методов, используемых в IDS.

Для простоты будем считать что мы ищем в трафике любое активность связанную с использованием /bin/sh. И попробуем детектировать такие активности.

Естественно, для начала нам нужные сами данные, которые мы будем просматривать. Здесь на помощь приходит библиотека LibPCAP и утилита TCPDump (TCPdump).

TCPDump сохранит в файл нужный объем трафика и мы можем с ним работать дальше

IDS-tcpdump_ex

Трафик у нас есть. TCPDump может писать и бинарные файлы, но для наглядности мы будет писать все как plain-text.

Для начала сохраним некоторые количество трафика себе в файл. Это не сложно.

IDS-commandline

Следующий шаг — решить как мы будем просматривать файл и искать в нем /bin/sh.

По сути задача сводится с задаче поиска подстроки в строке. Для этого существует несколько методов.

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

Простой поиск (naive string search)

Простой поиск представляет из себя не что иное как просмотр текста с сравнение с поисковой строкой посимвольно. А дальше двигаемся на один символ вперед и все повторяется.

 

Вот простая реализация.

Как видно из кода, цикл for (строка 11) выполнится максимум

textLength — patternLength  + 1

раз. А внутренний цикл patternLength раз. Таким образом, общая сложность алгоритма будет

O((textLength — patternLength  + 1) * patternLength)

что равно

O(textLength * patternLength)

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

Теперь попробуем использовать данный метод в поиске /bin/sh  в трафике.

 

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

Далее, чтобы сравнить скорость, мы рассмотрим более сложный алгоритм.

Алгоритм Ахо-Корасик

Данный алгоритм разработан Альфредом Ахо и Маргарет Корасик. Он является разновидностью алгоритма поиска множества подстрок из словаря в заданной строке. Алгоритм использует конечный автомат.

Если говорить кратко, то алгоритм находит все подстроки в тексте. Для этого алгоритм строит конечный автомат, используя Trie, в русском варианте Бор и связи между внутренними узлами.

Для этого паттерны должны быть закреплены и не могут меняться во время поиска. Для каждого паттерна в конечном автомате будет построен путь состояний. Основное правило чтобы не было дубликатов путей.

Рассмотрим все на примере.

Мы имеем словарь из следующих паттернов:

{a,ab,bab,bc,bca,c,caa}

 

IDS-stategraph

Из этого получаем граф состояний.

Для визуализации можно использовать вот это

Реализация для примера есть вот тут

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

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

Реализация multifast корректна, используем ее. Для этого Вам надо будет скачать и скомпилировать пример. Сначала надо скомпилировать саму библиотеку ahocorasick, а затем приложение.

В данном примере используется File Tree Walker (ftw.h), соответственно эта библиотека должна присутствовать.

В библиотеке определено следующее:

 

и следующие типы:

AC_AUTOMATA_t

основная структура, содержит все вершины,ребра и паттерны.

AC_PATTERN_t

Тип, описывающий сам паттерн.

AC_TEXT_t

Входной текст

AC_MATCH_t

Тип, описывающий совпадение.

AC_MATCH_CALLBACK_f

А это функция обратного вызова(callback), которая должна быть определена пользователем, и вызовется когда совпадение будет найдено.

Запуск multifast выглядит вот так:

multifast -P pattern_file [-ndxrpfivh] file1 [file2 …]

Можно указывать несколько входных файлов, в linux также работает вариант в получением данных из стандартного потока.

Единственная вещь, не очень понятная сразу, это формат для паттернов который использует эта реализация:

AX (REP) {PAT}

Часть AX может принимать только одно из значений — A или X. Это выбор между ASCII (A) и Hexadecimal(X). Это часть обязательна, от нее зависит как будет пониматься часть PAT — где собственно и находится паттерн.

Часть REP опциональна, это что-то типа ключа или тега. Больше для наглядности вывода, чтобы не выводить весь паттерн выводится его тег/имя/ключ.

Примеры паттернов есть в multifast/test

 

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

Его вычислительная сложность будет

O(nx + H + k)

где H — длина текста, n — общая длина всех паттернов, x — размер алфавита, а k — общая длина всех совпадений.

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

O((H + n) log x + k).

 

В следующей статье мы рассмотрим более совершенные алгоритмы:

Алгоритм Кнута-Морриса-Пратта(KMP, префикс-функция, 1977) и алгоритм Рабина-Карпа (хэш-функции, 1987г)