P-AC tornou a correspondência de múltiplas cadeias adequada ao hardware ao reduzir o autômato

Sistemas de segurança de rede precisam comparar um fluxo de dados rápido com milhares de assinaturas em tempo real. A parte atraente do Aho-Corasick é que seu tempo de execução é independente do número de cadeias, mas sua tabela de transições pode ser grande.

O artigo de Pao, Lin e Liu de 2010 na ACM TACO manteve o comportamento linear útil do fluxo enquanto atacava o custo de memória. Ao incorporar processamento em pipeline, o grafo de estados é reduzido a um trie de caracteres contendo apenas arestas para frente.

O artigo relata cerca de 18 bits por caractere para um conjunto de 6.166 assinaturas extraído do Snort, baixo custo de lógica de controle e a capacidade de dobrar a vazão com memórias FPGA de porta dupla ao processar dois fluxos simultaneamente.

Colocar o autômato em pipeline na forma de um trie

Separa a promessa de correspondência do algoritmo de uma implementação volumosa de seu autômato.

O arranjo de trie e tabela troca transições gerais por memória adequada ao pipeline.

Alterações incrementais de assinaturas podem atualizar tabelas de consulta sem reconfigurar os circuitos da FPGA.

Preservar o invariante algorítmico enquanto se altera a representação física. A mesma lógica de busca pode se tornar prática quando a máquina de estados é organizada para o hardware.

O P-AC é uma boa lição de hardware vinda da detecção de intrusão: o avanço não foi uma nova regra de correspondência, mas uma representação que tornou uma regra conhecida pequena, paralela e atualizável o suficiente para fluxos rápidos de pacotes.