Как искать тысячи паттернов в трафике и не сойти с ума: секреты Aho-Corasick

Вчера я писала  статью о том, как алгоритм Бойера-Мура помогает DPI-системам быстро находить одиночные сигнатуры в потоках данных. И хотя он хорош, у него есть слабое место: один шаблон за раз. Что делать, если шаблонов сотни или тысячи, а сеть несётся на скорости 100 Гбит/с? Именно здесь на авансцену выходит Aho-Corasick (далее — AC) — настоящий командный игрок, умеющий искать целый словарь строк в один-единственный проход по данным. Сегодня расскажу, как работает этот «комбо-сканер», почему он так любим разработчиками DPI и на какие подводные камни стоит обратить внимание.

Почему одного Бойера-Мура мало

Перечислим классические проблемы, которые всплывают, когда попытаться натянуть Бойера-Мура (или другой одиночный алгоритм) на огромный список сигнатур:

• N шаблонов → N проходов. Сотня строк — сто проходов, тысяча — … вы поняли.
• Пространственные расходы. Для каждой сигнатуры нужна отдельная таблица сдвигов. В IDS уровень L3/L7 таких шаблонов легко переваливает за 30 000.
• Нулевая синергия. Общие префиксы («GET /» и «GET /admin»), встречающиеся в половине правил, никак не переиспользуются.

В итоге процессор напоминает белку в колесе, перебирающую сигнатуры по кругу. AC предлагает другой подход: а давайте соберём все шаблоны в общий «лес» и будем гулять по нему одним курсором.

Основы Aho-Corasick: trie + «откатные» ссылки

Алгоритм был придуман в 1975 году Алфредом Ахо и Маргарет Корасиком. Его ядро — компактная структура данных trie (префиксное дерево), к которой добавлены специальные ссылки неудачи (failure links). Получается детерминированный конечный автомат (DFA), который читает поток символ за символом, никогда не возвращается назад и в любой момент знает, какие шаблоны уже «выстроились в очередь на совпадение».

Этап 1. Построение trie

Берём все сигнатуры, разбиваем их на символы и прокладываем ветки. Общие префиксы складываются в одни и те же вершины. Итоговый размер дерева растёт линейно от суммы длин шаблонов, а не квадратично от их количества — приятно.

Этап 2. Добавление ссылок неудачи

Для каждой вершины строим указатель на «глубочайший» префикс, совпадающий с суффиксом пути к текущей вершине. Если при чтении потока символ не нашёлся в ребёнке — прыгаем по ссылке неудачи и повторяем проверку. Механизм напоминает fallback в КМП, только в объёме целого словаря.

Этап 3. Поиск

Запускаем автомат в состояние root и скармливаем ему поток. Каждое потребление символа — константная операция. Если достигли вершины, помеченной «здесь оканчивается шаблон», фиксируем совпадение. При этом:

• Время работы — O(n + m + k), где n — длина текста, m — суммарная длина всех шаблонов, k — число совпадений.
• Память — зависит от алфавита. В ASCII — 256 ссылок с каждой вершины, но большинство пусты. Сжатые представления решают проблему.

Чем AC хорош именно для DPI

DPI-движки обожают AC за четыре качества:

1. Поиск множества сигнатур «раз и навсегда». Поток анализируется единственным сканером, а не сотней независимых.
2. Детерминизм и потоковость. Никаких бэктреков и смещений назад — значит, нулевая буферизация и минимальные задержки.
3. Шеринг префиксов. Огромные правила IDS построены на общих паттернах («HTTP/1.1», «Content-Type:»). AC хранит их ровно в одном месте.
4. Лёгкая аппаратная реализация. DFA идеально ложится на FPGA и ASIC: массив состояний + таблица переходов.

Примеры «в живой природе»

Suricata

Открытая IDS Suricata использует гибрид: быструю первые буквы ищет Rabin–Karp, а затем кандидат фильтрует через AC, построенный из оставшихся правил. Такая двухступенчатая цепочка выжимает максимум из CPU-кэша.

Snort 3

У «старика» Snort свой движок MPSE (Multi-Pattern Search Engine), внутри которого AC-автомат компилируется в сверходсжатый DFA с ремапом алфавита: редкие символы переносятся в мини-таблицы, а ядро остаётся маленьким.

Hyperscan

Библиотека Hyperscan от Intel компилирует AC в векторный код, который параллельно обрабатывает 16 – 32 байта входа, используя AVX-512. Пиковая скорость — десятки Гбит/с на одном ядре.

Оптимизации под капотом

Сжатые DFA

Наивно хранить 256 переходов для каждого состояния — избыточно. Популярные техники:

• Sparse table. Словарь «символ → состояние» хранится только для реально встречающихся символов.
• Bit-packed row. Номер состояния кодируется разрядным полем, длина которого зависит от размера под-автомата.
• Path compression. Последовательности состояний без разветвлений схлопываются в одну «супер-дугу».

Алфавитное ремапирование

Если в сигнатурах присутствуют лишь 50 уникальных байт, зачем держать таблицу на 256? Перенумеруем встречающиеся символы компактно, а «пустые» отправим в состояние «dead».

Vectorized AC

На современных CPU поиск можно распараллелить по входу или по состояниям. Подходы:

• SIMD-Sherwood. AVX переходит сразу по 32 символам, что требует альфа-маски и таблицы префиксов.
• Thread-per-flow. Каждый сетевой поток (TCP session) сканируется своим ядром; автомат хранится read-only.

Аппаратные ускорители

DPI-боксы Telco-класса часто строятся на FPGA/ASIC, где AC реализуется на чистых регистрах:

• Ib finetables. Таблица переходов кладётся в SRAM, каждое состояние — адрес строки.
• Pipeline DFA. Состояния идут конвейером, что позволяет сканировать несколько байтов за такт.
• Hybrid CAM + AC. Сначала CAM ищет подозрительные префиксы, затем DFA уточняет результат.

Минус — стоимость и сложность прошивок, зато производительности хватит, чтобы фильтровать 400 Гбит/с вслепую.

Где AC пасует

• Огромный словарь коротких шаблонов (по 3-4 байта). Объём автомата взрывается, проще пустить Rabin-Karp с Bloom-фильтрами.
• Регулярные выражения. AC ищет только фиксированные строки; для regex нужен Thompson-NFA или PCRE-DFA.
• Шифрованный трафик. Когда payload зашифрован TLS, ни AC, ни Бойер-Мур не увидят сигнатуру. Помогают лишь TLS-IN-TLS прокси или ML-детекторы на статистике потока.

Сочетание алгоритмов: конвейер DPI

Реальные системы строят «каскад» из нескольких двигателей:

1. Prefilter — быстрый хеш/байт-фильтр отбрасывает 99 % «невиновных» пакетов.
2. Aho-Corasick — проверяет оставшиеся кандидаты, быстро находит точные строки.
3. PCRE/RegEx — дорогая, но гибкая проверка только по настоящим подозрениям.

Так удаётся сохранить задержку на уровне микросекунд и при этом покрыть гигантский сигнатурный сет.

Заключение

Aho-Corasick — идеальный «оркестр» для поиска множества шаблонов: он делит память, не делает лишних движений и читает поток строго один раз. В мире DPI, где ценен каждый наносекундный прыжок, AC превращает список из 50 000 правил в послушный автомат, способный анализировать трафик линий уровня backbone.

Разумеется, это не серебряная пуля — шифрование, regex и гигабайтные словари требуют дополнительных техник. Но без AC современная IDS/IPS попросту захлебнулась бы в собственных сигнатурах. А значит, если вам нужно проверять всё и сразу, запоминайте рецепт: строим trie, добавляем failure-ссылки, поджимаем DFA — и вперёд, навстречу сетевым бурям.

P.S. А завтра, быть может, мы посмотрим, как этот автомат дружит с машинным обучением и зачем Intel скрещивает AC с гипер-блум-фильтрами. Но это уже совсем другая история…