P-AC a rendu la correspondance multi-chaînes adaptée au matériel en réduisant l'automate

Les systèmes de sécurité réseau doivent comparer un flux de données rapide à des milliers de signatures en temps réel. L'aspect séduisant d'Aho-Corasick est que son temps d'exécution est indépendant du nombre de chaînes, mais sa table de transitions peut être volumineuse.

L'article de Pao, Lin et Liu publié en 2010 dans ACM TACO a conservé le comportement linéaire utile du flux tout en s'attaquant au coût mémoire. En intégrant un traitement pipeline, le graphe d'états est réduit à un trie de caractères ne contenant que des arcs avant.

L'article rapporte environ 18 bits par caractère pour un ensemble de 6 166 chaînes de signatures extraites de Snort, un faible coût de logique de contrôle et la capacité de doubler le débit avec des mémoires FPGA à double port en traitant deux flux simultanément.

Mettre l'automate en pipeline sous forme de trie

Cela sépare la promesse de correspondance de l'algorithme d'une implémentation volumineuse de son automate.

La disposition en trie et en table échange des transitions générales contre une mémoire adaptée au pipeline.

Des modifications incrémentales des signatures peuvent mettre à jour les tables de correspondance sans reconfigurer les circuits du FPGA.

Préserver l'invariant algorithmique tout en changeant la représentation physique. La même logique de recherche peut devenir pratique lorsque la machine à états est agencée pour le matériel.

P-AC est une belle leçon matérielle issue de la détection d'intrusion : la percée n'a pas été une nouvelle règle de correspondance, mais une représentation qui a rendu une règle connue suffisamment compacte, parallèle et actualisable pour des flux de paquets rapides.