Нейронная сеть против DDoS'а

Предисловие

Некоторые из вас наверняка недавно проходили Stanford'ские курсы, в частности ai-class и ml-class. Однако, одно дело просмотреть несколько видео-лекций, поотвечать на вопросики quiz'ов и написать десяток программ в Matlab/Octave, другое дело начать применять полученные знания на практике. Дабы знания полученые от Andrew Ng не угодили в тот же тёмный угол моего мозга, где заблудились dft, Специальная теория относительности и Уравнение Эйлера Лагранжа, я решил не повторять институтских ошибок и, пока знания ещё свежи в памяти, практиковаться как можно больше.

И тут как раз на наш сайтик приехал DDoS. Отбиваться от которого можно было админско-программерскими (grep / awk / etc) способами или же прибегнуть к использованию технологий машинного обучения.

Далее пойдёт рассказ о создании нейронной сети на Python 2.7 / PyBrain и её применении для защиты от DDoS'а.

Введение

Что мы имеем: сервер под DDoS'ом средненьким ботнетом (20,000-50,000) и access.log'и с него. Иметь access.log до начала DDoS'а весьма полезно, т.к. он описывает практически 100% легитимных клиентов, а следовательно, отличный dataset для тренировки нейронной сети.

Что мы хотим получить: классификатор, который по записи в access.log'е говорил бы нам с некоторой долей вероятности от кого пришел запрос: от бота или от человека. Благодаря такому классификатору мы сможем сформировать вектор атаки (набор подсетей) и отправить их в firewall / хостеру.

Подготовка

Для тренировки классификатора нам понадобятся два набора данных: для "плохих" и "хороших" запросов. Да, довольно забавно, что для того, чтобы найти ботов, нужно сначала найти ботов. Тут нам как раз и понадобятся grep, например, для того, чтобы вытащить из лога все запросы с IP'шников с большим кол-вом 503'их ошибок (rate limiting nginx'а).

В итоге у нас должны получиться 3 access.log'а:

• Dataset с "хорошими" запросами из access.log'а до начала DDoS'а
• Dataset с "плохими" запросами, нагрепанными на предыдущем этапе.
• Dataset, который нам необходимо классифицировать, разделив запросы на плохие и хорошие. Обычно это tail -f access.log'а с сервра под DDoS'ом

Далее необходимо научиться парсить т.н. combined лог nginx'а. Наверняка уже где-то в интернетах есть готовая регулярка, но я изобрёл свой велосипед:

(?P<ip>[0-9.:a-f]+) [^ ]+ [^ ]+ \[.*\] "(?P<url>.*)" (?P<code>[0-9]+) (?P<size>[0-9]+) "(?P<refer>.*)" "(?P<useragent>.*)"$

/* В связи с тем, что я написал yet another log parser, в очередной раз вспомнилась идея о изначальной сериализации лога в json, ибо логи на продакшне в большинстве своём не для людей, а для программ. */

После того как мы научились парсить лог, необходимо выделить features (особенности/маркеры/признаки), составить их словарь и по нему в дальнейшем составлять feature-vector для каждой записи dataset'ов. Об этом дальше.

Машинное обучение в общем

Мы остановились на выделении features из логов, для этого берём "хороший" и "плохой" логи и пытаемся найти в них всевозможные features aka признаки. В combined логе их не так уж и много, я взял следующие:

• Сам запрос, попарсенный на тип запроса(HEAD/GET/POST/etc), url и http_version. Url парсится на протокол, имя хоста, путь и все ключи от query_string
• Referer, попарсенный аналогично url в запросе.
• User-Agent, попарсенный волшебной уличной магией, ибо его формат довольно сильно варьируется от браузера к браузеру. В RFC2616 про него сказано совсем немного. Наверняка можно много лучше.
• status, только в случае кодов 503/404/403. Вообще, во время DDoS'а сервер любит отвечать 500/502, поэтому учитывать будем только вышеописанные коды.

/* Кстати, первая версия скрипта, которую я использовал для защиты от DDoS'а, содержала злостный баг, благодаря которому не учитывалась примерно половина признаков. Однако, даже в таком состоянии код умудрялся вполне сносно работать, благодаря чему собственно баг долгое время и скрывался. В этом плане очень прав оказался Andrew, говоря, что побеждает не самый умный алгоритм, а тот, которому скормят больше данных. */

Итак, мы подошли к моменту, когда имеем на руках огромный список всевозможных features, которые могут присутствовать в запросе. Это и есть наш словарь. Словарь нужен для того, чтобы из любого возможного запроса создать feature-vector. Бинарный (состоящий из нулей и единиц) M-мерный вектор (где M — длина словаря), который отражает присутствие каждого признака из словаря в запросе.
Очень хорошо, если словарь с точки зрения струкруры данных будет hash-таблицей, ибо к нему будет множество обращений типа if word in dictionary.
Подробнее об этом можно почитать в Lecture Notes 11: Machine Learning System Design

Пример построения словаря и feature-vector'а

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

Запись из "плохого" лога:

0.0.0.0 - - [20/Dec/2011:20:00:08 +0400] "POST /forum/index.php HTTP/1.1" 503 107 "http://www.mozilla-europe.org/" "-"

Запись из "хорошего" лога:

0.0.0.0 - - [20/Dec/2011:15:00:03 +0400] "GET /forum/rss.php?topic=347425 HTTP/1.0" 200 1685 "-" "Mozilla/5.0 (Windows; U; Windows NT 5.1; pl; rv:1.9) Gecko/2008052906 Firefox/3.0"

Получившийся словарь:

['__UA___OS_U', '__UA_EMPTY', '__REQ___METHOD_POST', '__REQ___HTTP_VER_HTTP/1.0', '__REQ___URL___NETLOC_', '__REQ___URL___PATH_/forum/rss.php', '__REQ___URL___PATH_/forum/index.php', '__REQ___URL___SCHEME_', '__REQ___HTTP_VER_HTTP/1.1', '__UA___VER_Firefox/3.0', '__REFER___NETLOC_www.mozilla-europe.org', '__UA___OS_Windows', '__UA___BASE_Mozilla/5.0', '__CODE_503', '__UA___OS_pl', '__REFER___PATH_/', '__REFER___SCHEME_http', '__NO_REFER__', '__REQ___METHOD_GET', '__UA___OS_Windows NT 5.1', '__UA___OS_rv:1.9', '__REQ___URL___QS_topic', '__UA___VER_Gecko/2008052906']

Тестовая запись:

0.0.0.0 - - [20/Dec/2011:20:00:01 +0400] "GET /forum/viewtopic.php?t=425550 HTTP/1.1" 502 107 "-" "BTWebClient/3000(25824)"

Её feature-vector:

[False, False, False, False, True, False, False, True, True, False, False, False, False, False, False, False, False, True, True, False, False, False, False]

Заметьте, насколько "разрежен" (sparse) feature-vector — такое поведение будет наблюдаться для всех запросов.

Разделение Dataset'а

Хорошей практикой является разделение dataset'а на несколько частей. Я бил на две части в пропорции 70/30:

• Training set. На нём мы обучаем нашу нейронную сеть.
• Test set. Им мы проверяем, насколько хорошо обучена наша нейронная сеть.

Такое разбиение обусловлено тем фактом, что нейронная сеть с наименьшим training error (ошибкой на training set) будет выдавать большую ошибку на новых данных, ибо мы «переобучили» сеть, заточив её под training set.
В дальнейшем, если придётся озадачиться выбором оптимальных констант, dataset надо будет разбить на 3 части в соотношении 60/20/20: Training set, Test set и Cross validation. Последний как раз и будет служить для выбора оптимальных параметров нейронной сети (например weightdecay).

Нейронная сеть в частности

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

Начнём с выбора структуры. Я выбрал сеть из одного скрытого слоя размером с удвоенный входной слой. Почему? Всё просто: так завещал Andrew Ng в случае, если не знаете с чего начать. Думаю, в дальнейшем с этим можно поиграться, порисовав графики обучения.
Функцией активации для скрытого слоя выбрана многострадальная сигмойда, а для выходного слоя — Softmax. Последний выбран на случай, если придётся делать
многоклассовую класиффикацию c mutually exclusive классами. Например, "хорошие" запросы отправлять на бэкенд, "плохие" — в бан на фаерволе, а "серые" — разгадывать капчу.

Нейронная сеть склонна к уходу в локальный минимум, поэтому у себя в коде я строю несколько сетей и выбираю ту, у которой наименьший Test error (Заметьте, именно ошибка на test set, а не trainig set).

Disclaimer

Я не настоящий сварщик. О Machine Learning я знаю только то, что подчерпнул из ml-class и ai-class. На питоне программировать начал относительно недавно, а код ниже был написан минут за 30 (время, как вы понимаете, поджимало) и в дальнейшем был лишь слегка подпилен напильником.

Код

Сам скрипт небольшой — 2-3 страницы A4 в зависимости от шрифта. С ним можно ознакомиться тут: github.com/SaveTheRbtz/junk/tree/master/neural_networks_vs_ddos

Также этот код не самодостаточен. Ему всё равно нужна скриптовая обвязка. Например, если IP сделал N плохих запросов в течение X минут, то банить его на firewall'е.

Производительность

• lfu_cache. Портировал с ActiveState, дабы сильно ускорить обработку запросов-"высокочастотников". Down-side — повышенное потребление памяти.
• PyBrain, внезапно, написан на python и поэтому не очень быстр, однако, он может использовать ATLAS-based-модуль arac, если при создании сети указать Fast=True. Подробнее про это можно почитать в документации к PyBrain.
• Распараллеливание. Свою нейронную сеть я обучил на довольно "толстом" серверном Nehalem'е, однако, даже там чувствовалась ущербность однопоточного обучения. Можно поразмыслить на тему распараллеливания обучения нейронной сети. Простое решение — тренировать сразу несколько нейронных сетей параллельно и из них выбирать лучшую, но это создаст дополнительную нагрузку на память, что тоже не очень хорошо. Хотелось бы более универсальное решение. Возможно имеет смысл просто переписать всё на C, благо вся теоретическая база в ml-class'е была расжевана.
• Потребление памяти и кол-во features. Хорошей оптимизацией по памяти являлся переход со стндартных питоновских массивов на numpy'ные. Так же уменьшение размера dictionary и/или использование PCA может очень хорошо помочь, об этом чуть ниже.

На будущее

• Дополнительные поля в лог. В combined лог можно добавить ещё много всего, стоит подумать на тему, какие поля помогут в идентификации ботов. Возможно, имеет смысл учитывать первый октет IP адреса, ибо в не интернациональном web-проекте китайские пользователи вероятнее всего боты.
• Principal Component Analysis. Позволит сильно сократить размерность feature-vector'ов, тем самым уменьшив время тренировки нейронной сети.
• Preprocessing/Normalizing для features. Например, всё, что попадает под regexp [a-fA-F0-9]{32}, можно заменять словом __MD5__, всё, что похоже на дату — словом __DATE__ и т.д., тем самым уменьшить кол-во малочастотных features и соответственно размер словаря.
• Тюнинг констант и струкруры нейронной сети. Текущие были взяты с потолка, а именно из мануала по созданию классификатора на базе PyBrain (да-да, помните, я писал, что код был написан ну оооочень быстро). Имело бы смысл порисовать графики обучения нейронной сети при разных значениях параметров, благо matplotlib под рукой.
• Online обучение. Стратегия умных атакующих часто меняется. Хорошо бы было придумать способы для до-/переобучения нейронной сети "на ходу". Впрочем, это легче сказать, чем сделать.

Ещё почитать

Machine Learning Lecture Notes — Записи по курсу ml-class.
UFLDL — Unsupervised Feature Learning and Deep Learning. Так же от профессора Andrew Ng.

Вместо заключения

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