Los sistemas de seguridad de red deben comparar un flujo de datos rápido contra miles de firmas en tiempo real. La parte atractiva de Aho-Corasick es que su tiempo de ejecución es independiente del número de cadenas, pero su tabla de transiciones puede ser grande.
El artículo de Pao, Lin y Liu de 2010 en ACM TACO conservó el comportamiento lineal útil del flujo mientras atacaba el costo de memoria. Al incorporar procesamiento canalizado, el grafo de estados se reduce a un trie de caracteres que contiene solo aristas hacia adelante.
El artículo reporta unos 18 bits por carácter para un conjunto de firmas de 6.166 cadenas extraído de Snort, bajo costo de lógica de control y la capacidad de duplicar el rendimiento con memorias FPGA de doble puerto al procesar dos flujos de forma concurrente.
Canalizar el autómata en un trie
Separa la promesa de coincidencia del algoritmo de una implementación voluminosa de su autómata.
La disposición de trie y tabla intercambia transiciones generales por memoria apta para canalización.
Los cambios incrementales de firmas pueden actualizar las tablas de búsqueda sin reconfigurar la circuitería de la FPGA.
Preservar el invariante algorítmico mientras se cambia la representación física. La misma lógica de búsqueda puede volverse práctica cuando la máquina de estados se dispone para el hardware.
P-AC es una buena lección de hardware proveniente de la detección de intrusiones: el avance no fue una nueva regla de coincidencia, sino una representación que hizo que una regla conocida fuera lo bastante pequeña, paralela y actualizable para flujos de paquetes rápidos.
CONSULTA LAS PRUEBAS
Las fuentes
- A memory-efficient pipelined implementation of the aho-corasick string-matching algorithm ACM Transactions on Architecture and Code Optimization via OpenAlex · api.openalex.org ·