Aho-Corasick Algorithm

https://cp-algorithms.com/string/aho_corasick.html

by thunderbong • 2 years ago

36 2 2 years ago

teleforce• 2 years ago

Still remember when first heard Aho-Corasick from the Snort IDS mailing list circa 2002. This paper described the optimization of Snort detection engine based on Aho-Corasick in the later version of Snort [1]. Not sure though which algorithm that the latest Snort 3 IDS is using for its detection engine [2].

[1] Optimizing Pattern Matching for Intrusion Detection:

https://www.semanticscholar.org/paper/Optimizing-Pattern-Mat...

[2] Snort:

https://www.snort.org/

dalf• 2 years ago

This might be relevant here: there is a Rust implementation of this algorithm by BurntSushi [1], and discussion [2] about the performances and Hyperscan [3] in the case of Suricata [4]. HyperScan being regular expression matching library using AMD64 SIMD instructions by Intel. HyperScan is in low maintenance mode, but there is a maintained fork which is compatible with more architectures: Vectorscan [5]

[1] https://github.com/BurntSushi/aho-corasick/

[2] https://github.com/BurntSushi/aho-corasick/discussions/136

[3] https://github.com/intel/hyperscan

[4] https://github.com/OISF/suricata

[5] https://github.com/VectorCamp/vectorscan

Aho-Corasick Algorithm

Related Stories