Netzwerksicherheitssysteme müssen einen schnellen Datenstrom in Echtzeit mit Tausenden von Signaturen vergleichen. Das Attraktive an Aho-Corasick ist, dass seine Laufzeit unabhängig von der Anzahl der Strings ist, aber seine Übergangstabelle kann groß werden.
Die Arbeit von Pao, Lin und Liu aus dem Jahr 2010 in ACM TACO behielt das nützliche lineare Stromverhalten bei und griff gleichzeitig die Speicherkosten an. Durch die Einbeziehung pipelined Verarbeitung wird der Zustandsgraph auf einen Zeichen-Trie reduziert, der nur Vorwärtskanten enthält.
Die Arbeit berichtet über etwa 18 Bit pro Zeichen für einen aus Snort extrahierten Signatursatz mit 6.166 Strings, geringe Kosten für die Steuerlogik und die Fähigkeit, den Durchsatz mit Dual-Port-FPGA-Speichern durch die gleichzeitige Verarbeitung zweier Ströme zu verdoppeln.
Den Automaten in einen Trie pipelinen
Es trennt das Matching-Versprechen des Algorithmus von einer sperrigen Implementierung seines Automaten.
Das Trie-und-Tabellen-Layout tauscht allgemeine Übergänge gegen pipelinefreundlichen Speicher.
Inkrementelle Signaturänderungen können Nachschlagetabellen aktualisieren, ohne die FPGA-Schaltkreise neu zu konfigurieren.
Die algorithmische Invariante bewahren, während die physische Repräsentation geändert wird. Dieselbe Suchlogik kann praktikabel werden, wenn die Zustandsmaschine für die Hardware ausgelegt wird.
P-AC ist eine schöne Hardware-Lektion aus der Intrusion Detection: Der Durchbruch war keine neue Matching-Regel, sondern eine Repräsentation, die eine bekannte Regel klein, parallel und ausreichend aktualisierbar für schnelle Paketströme machte.
DEN BELEGEN FOLGEN
Die Quellen
- A memory-efficient pipelined implementation of the aho-corasick string-matching algorithm ACM Transactions on Architecture and Code Optimization via OpenAlex · api.openalex.org ·