16.07.2015 @ 14:02 Введение в системы обнаружения вторжений (IDS). Часть 2 algorithms, ids, network ids, nids, search, signature-based, snort Ссылка на первую часть статьи. Сигнатурные методы детектирования в IDS В данной статье мы рассмотрим методы детектирования, использующие предопределенные правила, в которых содержатся сигнатуры — признаки определенного события. Сигнатурный подход к детектированию берет начало с самых ранних реализаций систем обнаружения вторжений и используется до сих пор. Во-первых, попробуем решить эту задачу «с нуля». Как понять что происходит что-то не то? Видимо, для начала надо определить то, что мы можем детектировать как «не то». Первое что приходит в голову — если мы знаем как выглядят атаки, их поведение и действия в сети — будем просматривать трафик на предмет такой активности. Но как быть если у атаки несколько шагов? Что искать в трафике? И как? Основная идея сигнатурного подхода к детектированию состоит в выявлении короткого паттерна для каждой известной атаки, и затем весь трафик просматривается на наличие таких паттернов. На первый взгляд довольно просто. Все становится не так радужно, когда дело доходит до реализации. Давайте пройдемся по реализациям некоторых методов, используемых в IDS. Для простоты будем считать что мы ищем в трафике любое активность связанную с использованием /bin/sh. И попробуем детектировать такие активности. Естественно, для начала нам нужные сами данные, которые мы будем просматривать. Здесь на помощь приходит библиотека LibPCAP и утилита TCPDump (TCPdump). TCPDump сохранит в файл нужный объем трафика и мы можем с ним работать дальше Трафик у нас есть. TCPDump может писать и бинарные файлы, но для наглядности мы будет писать все как plain-text. Для начала сохраним некоторые количество трафика себе в файл. Это не сложно. Следующий шаг — решить как мы будем просматривать файл и искать в нем /bin/sh. По сути задача сводится с задаче поиска подстроки в строке. Для этого существует несколько методов. Начнем с простейших методов поиска подстроки и будем двигаться в сторону усложнения. Простой поиск (naive string search) Простой поиск представляет из себя не что иное как просмотр текста с сравнение с поисковой строкой посимвольно. А дальше двигаемся на один символ вперед и все повторяется. #include<stdio.h> #include<string.h> void naivesearch(char *pattern, char *text) { int patternLength = strlen(pattern); int textLength = strlen(text); /* sliding pattern[] one by one */ for (int i = 0; i <= (textLength - patternLength); i++) { int j; /* check for pattern */ for (j = 0; j < patternLength; j++) { if (text[i+j] != pattern[j]) break; } if (j == patternLength) { printf("Pattern found at index %d \n", i); } } } int main() { char *txt = "AABAACAADAABAAABAA"; char *p = "AABA"; naivesearch(p, txt); getchar(); return 0; } Вот простая реализация. Как видно из кода, цикл for (строка 11) выполнится максимум textLength — patternLength + 1 раз. А внутренний цикл patternLength раз. Таким образом, общая сложность алгоритма будет O((textLength — patternLength + 1) * patternLength) что равно O(textLength * patternLength) В худшем случае, когда подстрока и строка будут равны во всех символах кроме последнего, алгоритм имеет квадратичную сложность. Теперь попробуем использовать данный метод в поиске /bin/sh в трафике. #include <stdio.h> #include <time.h> #include <stdlib.h> #include <string.h> #include <ctype.h> void naivesearch(char *pattern, char *text) { int patternLength = strlen(pattern); int textLength = strlen(text); /* sliding pattern[] one by one */ for (int i = 0; i <= (textLength - patternLength); i++) { int j; /* check for pattern */ for (j = 0; j < patternLength; j++) { if (text[i+j] != pattern[j]) break; } if (j == patternLength) { printf("Pattern found at index %d \n", i); } } } int main(int argc, char *argv[]) { FILE *fp; long lSize; char *buffer; fp = fopen( argv[1], "r" ); if( !fp ) { perror( argv[1] ); exit( 1 ); } fseek( fp , 0L , SEEK_END); lSize = ftell( fp ); rewind( fp ); /* allocate memory for entire content */ buffer = (char *) malloc(lSize + 1); if ( !buffer ) { fclose(fp); fputs("memory alloc fail ", stderr); exit(1); } /* copy the file into the buffer */ fread( buffer , lSize, 1 , fp); /* now we have file in our buffer */ char *p = "/bin/sh"; time_t mytime; mytime = time(NULL); printf(ctime(&mytime)); naivesearch(p, buffer); time_t mytime2; mytime2 = time(NULL); printf(ctime(&mytime2)); free(buffer); getchar(); return 0; } Вы можете сами попробовать эту реализацию на больших файлах чтобы оценить скорость работы. Далее, чтобы сравнить скорость, мы рассмотрим более сложный алгоритм. Алгоритм Ахо-Корасик Данный алгоритм разработан Альфредом Ахо и Маргарет Корасик. Он является разновидностью алгоритма поиска множества подстрок из словаря в заданной строке. Алгоритм использует конечный автомат. Если говорить кратко, то алгоритм находит все подстроки в тексте. Для этого алгоритм строит конечный автомат, используя Trie, в русском варианте Бор и связи между внутренними узлами. Для этого паттерны должны быть закреплены и не могут меняться во время поиска. Для каждого паттерна в конечном автомате будет построен путь состояний. Основное правило чтобы не было дубликатов путей. Рассмотрим все на примере. Мы имеем словарь из следующих паттернов: {a,ab,bab,bc,bca,c,caa} Из этого получаем граф состояний. Для визуализации можно использовать вот это Реализация для примера есть вот тут Сейчас в сети довольно много реализаций, но обращайте внимание на корректность кода, потому что многие из них содержат ошибки и пропускают некоторые совпадения. Такие ошибки возникают из-за некорректного построения конечного автомата, что приводит к неполному покрытию всех возможных путей. Реализация multifast корректна, используем ее. Для этого Вам надо будет скачать и скомпилировать пример. Сначала надо скомпилировать саму библиотеку ahocorasick, а затем приложение. В данном примере используется File Tree Walker (ftw.h), соответственно эта библиотека должна присутствовать. В библиотеке определено следующее: AC_AUTOMATA_t* ac_automata_init (void); AC_STATUS_t ac_automata_add (AC_AUTOMATA_t * thiz, AC_PATTERN_t *pat); void ac_automata_finalize AC_AUTOMATA_t * thiz); int ac_automata_search AC_AUTOMATA_t * thiz, AC_TEXT_t *txt, int *keep, AC_MATCH_CALBACK_f * callback, void * param); void ac_automata_settext (AC_AUTOMATA_t * thiz, AC_TEXT_t *text, int keep); AC_MATCH_t* ac_automata_findnext (AC_AUTOMATA_t * thiz); void ac_automata_release (AC_AUTOMATA_t * thiz); void ac_automata_display (AC_AUTOMATA_t * thiz, char repcast); и следующие типы: 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 # comment a (yahoo) {I am filling lucky} a {disclosed } x (maloos) {56 10 23 Ef EB 1D e9 09 d3 7c a4} a (firy) {from \{23\} to } x {20 b3 7e 0a 40 97 79 ff ac 2d 84 2c 0c 3d 60 8d} # comments x(popy) {50 55 42 5 1 6 c c c 0 a} x (wood) {00 00 00 fe002345 e3} Данный алгоритм работает намного быстрее простого поиска, но все же не насколько хорошо чтобы использовать его в детектировании с большой нагрузкой. Его вычислительная сложность будет O(nx + H + k) где H — длина текста, n — общая длина всех паттернов, x — размер алфавита, а k — общая длина всех совпадений. При этом, сложность зависит от варианта реализации, если использовать не индексный массив, а красно-черное дерево, то снизится расход памяти, но вычислительная сложность увеличится до O((H + n) log x + k). В следующей статье мы рассмотрим более совершенные алгоритмы: Алгоритм Кнута-Морриса-Пратта(KMP, префикс-функция, 1977) и алгоритм Рабина-Карпа (хэш-функции, 1987г) icewind 8909 Network security Читать дальше >>