Вчера я писала статью о том, как алгоритм Бойера-Мура помогает 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 за четыре качества:
- Поиск множества сигнатур «раз и навсегда». Поток анализируется единственным сканером, а не сотней независимых.
- Детерминизм и потоковость. Никаких бэктреков и смещений назад — значит, нулевая буферизация и минимальные задержки.
- Шеринг префиксов. Огромные правила IDS построены на общих паттернах («HTTP/1.1», «Content-Type:»). AC хранит их ровно в одном месте.
- Лёгкая аппаратная реализация. 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
Реальные системы строят «каскад» из нескольких двигателей:
- Prefilter — быстрый хеш/байт-фильтр отбрасывает 99 % «невиновных» пакетов.
- Aho-Corasick — проверяет оставшиеся кандидаты, быстро находит точные строки.
- PCRE/RegEx — дорогая, но гибкая проверка только по настоящим подозрениям.
Так удаётся сохранить задержку на уровне микросекунд и при этом покрыть гигантский сигнатурный сет.
Заключение
Aho-Corasick — идеальный «оркестр» для поиска множества шаблонов: он делит память, не делает лишних движений и читает поток строго один раз. В мире DPI, где ценен каждый наносекундный прыжок, AC превращает список из 50 000 правил в послушный автомат, способный анализировать трафик линий уровня backbone.
Разумеется, это не серебряная пуля — шифрование, regex и гигабайтные словари требуют дополнительных техник. Но без AC современная IDS/IPS попросту захлебнулась бы в собственных сигнатурах. А значит, если вам нужно проверять всё и сразу, запоминайте рецепт: строим trie, добавляем failure-ссылки, поджимаем DFA — и вперёд, навстречу сетевым бурям.
P.S. А завтра, быть может, мы посмотрим, как этот автомат дружит с машинным обучением и зачем Intel скрещивает AC с гипер-блум-фильтрами. Но это уже совсем другая история…
