Cómo detectar miles de patrones en el tráfico sin volverse loco: los secretos del algoritmo Aho–Corasick

Ayer escribí un artículo sobre cómo el algoritmo de Boyer-Moore ayuda a los sistemas DPI a encontrar rápidamente firmas individuales en flujos de datos. Y aunque es bueno, tiene una limitación: un patrón a la vez. ¿Qué hacer si hay cientos o miles de patrones y la red corre a 100 Gbit/s? Ahí entra en escena Aho-Corasick (en adelante — AC): un verdadero jugador de equipo capaz de buscar todo un diccionario de cadenas en una sola pasada por los datos. Hoy explicaré cómo funciona este «explorador combinado», por qué es tan apreciado por los desarrolladores de DPI y en qué trampas conviene fijarse.

Por qué un solo Boyer-Moore no basta

Enumeremos los problemas clásicos que aparecen cuando se intenta adaptar Boyer-Moore (u otro algoritmo para un solo patrón) a una lista enorme de firmas:

• N patrones → N pasadas. Cien cadenas — cien pasadas, mil — … ya se entiende.
• Coste espacial. Cada firma necesita su propia tabla de desplazamientos. En un IDS a nivel L3/L7 el número de esos patrones fácilmente supera los 30 000.
• Cero sinergia. Prefijos comunes («GET /» y «GET /admin»), que aparecen en la mitad de las reglas, no se reutilizan de ninguna forma.

Al final la CPU parece una ardilla en una rueda, revisando patrones en ciclos. AC propone otro enfoque: juntamos todos los patrones en un «bosque» común y lo recorremos con un solo cursor.

Fundamentos de Aho-Corasick: trie + enlaces de fallo

El algoritmo fue ideado en 1975 por Alfred Aho y Margaret Corasick. Su núcleo es una estructura de datos compacta, el trie (árbol de prefijos), a la que se añaden enlaces especiales de fallo (failure links). El resultado es un autómata finito determinista (DFA) que lee el flujo símbolo por símbolo, nunca retrocede y en cualquier momento sabe qué patrones ya «están a la espera» de coincidir.

Etapa 1. Construcción del trie

Tomamos todas las firmas, las descomponemos en símbolos y trazamos las ramas. Los prefijos comunes se agrupan en los mismos nodos. El tamaño final del árbol crece linealmente con la suma de las longitudes de los patrones, no cuadráticamente con su número — agradable.

Etapa 2. Adición de enlaces de fallo

Para cada nodo construimos un puntero al prefijo «máximo» que coincide con el sufijo del camino hasta el nodo actual. Si al leer el flujo un símbolo no se encuentra entre los hijos, saltamos por el enlace de fallo y volvemos a comprobar. El mecanismo recuerda al fallback en KMP, pero aplicado a todo un diccionario.

Etapa 3. Búsqueda

Arrancamos el autómata en el estado root y le damos el flujo. Cada consumo de símbolo es una operación constante. Si alcanzamos un nodo marcado como «aquí termina un patrón», registramos la coincidencia. Además:

• Tiempo de ejecución — O(n + m + k), donde n es la longitud del texto, m la suma de las longitudes de todos los patrones y k el número de coincidencias.
• Memoria — depende del alfabeto. En ASCII son 256 enlaces por nodo, pero la mayoría están vacíos. Representaciones comprimidas solucionan el problema.

Por qué AC es especialmente bueno para DPI

Los motores DPI adoran AC por cuatro cualidades:

1. Búsqueda de múltiples firmas «una vez por todas». El flujo se analiza con un único escáner, no con cientos independientes.
2. Determinismo y flujo continuo. Sin backtracks ni desplazamientos hacia atrás — eso significa cero buffering y latencias mínimas.
3. Compartición de prefijos. Las enormes reglas de un IDS se basan en patrones comunes («HTTP/1.1», «Content-Type:»). AC los almacena en un único lugar.
4. Fácil implementación en hardware. Un DFA encaja perfectamente en FPGA y ASIC: matriz de estados + tabla de transiciones.

Ejemplos «en la naturaleza»

Suricata

La IDS de código abierto Suricata utiliza un híbrido: las primeras letras rápidas las busca con Rabin–Karp y luego filtra los candidatos mediante un AC construido a partir de las reglas restantes. Esa cadena en dos etapas exprime al máximo la caché de la CPU.

Snort 3

El veterano Snort tiene su propio motor MPSE (Multi-Pattern Search Engine), dentro del cual el autómata AC se compila en un DFA altamente comprimido con remapeo del alfabeto: los símbolos raros se trasladan a mini-tablas y el núcleo permanece pequeño.

Hyperscan

La biblioteca Hyperscan de Intel compila AC a código vectorizado que procesa en paralelo 16–32 bytes de entrada, usando AVX-512. La velocidad pico alcanza decenas de Gbit/s en un solo núcleo.

Optimizaciones bajo el capó

DFA comprimidos

Almacenar ingenuamente 256 transiciones por estado es redundante. Técnicas populares:

• Sparse table. El diccionario «símbolo → estado» se almacena solo para los símbolos que realmente aparecen.
• Bit-packed row. El número de estado se codifica en un campo de bits cuya longitud depende del tamaño del sub-autómata.
• Path compression. Secuencias de estados sin bifurcaciones se colapsan en una «super-arista».

Remapeo alfabético

Si en las firmas aparecen solo 50 bytes únicos, ¿por qué mantener una tabla de 256? Renumeramos compactamente los símbolos presentes y enviamos los «vacíos» al estado «dead».

AC vectorizado

En CPUs modernas la búsqueda se puede paralelizar sobre la entrada o sobre los estados. Enfoques:

• SIMD-Sherwood. AVX avanza sobre 32 símbolos a la vez, lo que requiere una máscara alfa y una tabla de prefijos.
• Thread-per-flow. Cada flujo de red (sesión TCP) se escanea en su propio núcleo; el autómata se almacena en modo lectura.

Aceleradores hardware

Los appliances DPI de clase telco suelen construirse sobre FPGA/ASIC, donde AC se implementa con registros puros:

• Ib finetables. La tabla de transiciones se coloca en SRAM; cada estado es la dirección de una fila.
• Pipeline DFA. Los estados se organizan en un pipeline, lo que permite escanear varios bytes por ciclo.
• Hybrid CAM + AC. Primero una CAM busca prefijos sospechosos y luego el DFA afina el resultado.

La contrapartida es el coste y la complejidad del firmware, pero la performance basta para filtrar 400 Gbit/s de forma ciega.

Dónde AC se queda corto

• Diccionario enorme de patrones cortos (de 3–4 bytes). El tamaño del autómata se dispara; es más sencillo usar Rabin-Karp con filtros Bloom.
• Expresiones regulares. AC solo busca cadenas fijas; para regex se necesita un Thompson-NFA o un PCRE-DFA.
• Tráfico cifrado. Cuando la carga útil está cifrada con TLS, ni AC ni Boyer-Moore verán la firma. Solo ayudan proxies TLS-in-TLS o detectores ML basados en estadísticas del flujo.

Combinación de algoritmos: la línea de montaje DPI

Los sistemas reales construyen una «cascada» de varios motores:

1. Prefiltro — un hash rápido/filtro por bytes descarta el 99 % de los paquetes «inocentes».
2. Aho-Corasick — verifica los candidatos restantes y encuentra rápidamente las cadenas exactas.
3. PCRE/RegEx — comprobación costosa pero flexible solo sobre las sospechas reales.

Así se consigue mantener la latencia a nivel de microsegundos y al mismo tiempo cubrir una red de firmas gigantesca.

Conclusión

Aho-Corasick es la «orquesta» ideal para buscar múltiples patrones: comparte memoria, evita movimientos innecesarios y lee el flujo estrictamente una sola vez. En el mundo DPI, donde cada salto de nanosegundos cuenta, AC convierte una lista de 50 000 reglas en un autómata obediente capaz de analizar el tráfico del backbone.

Por supuesto, no es una bala de plata: el cifrado, las expresiones regulares y los diccionarios de gigabytes exigen técnicas adicionales. Pero sin AC la IDS/IPS moderna simplemente se ahogaría en sus propias firmas. Así que, si necesita comprobar todo a la vez, recuerde la receta: construya el trie, añada los enlaces de fallo, comprima el DFA — y adelante, a enfrentar las tormentas de red.

P.S. Mañana, quizá, veremos cómo este autómata se lleva con el aprendizaje automático y por qué Intel combina AC con hiperfiltros Bloom. Pero esa ya es otra historia…