<  Back to the Polytechnique Montréal portal

Node configuration for the Aho-Corasick algorithm in Intrusion Detection Systems

Alexsandre B. Lacroix, J.M. Pierre Langlois, François-Raymond Boyer, Antoine Gosselin and Guy Bois

Conference or Workshop Item - Paper (2017)

Accepted Version
Terms of Use: All rights reserved.
Download (304kB)
Cite this document: Lacroix, A. B., Langlois, J.M. P., Boyer, F.-R., Gosselin, A. & Bois, G. (2016, March). Node configuration for the Aho-Corasick algorithm in Intrusion Detection Systems. Paper presented at ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2016), Santa Clara, Californie (2 pages). doi:10.1145/2881025.2889473
Show abstract Hide abstract


In this paper, we analyze the performance and cost trade-off from selecting two representations of nodes when implementing the Aho-Corasick algorithm. This algorithm can be used for pattern matching in network-based intrusion detection systems such as Snort. Our analysis uses the Snort 2.9.7 rules set, which contains almost 26k patterns. Our methodology consists of code profiling and analysis, followed by the selection of a parameter to maximize a metric that combines clock cycles count and memory usage. The parameter determines which of two types of nodes is selected for each trie node. We show that it is possible to select the parameter to optimize the metric, which results in an improvement by up to 12× compared with the single node-type case.

Uncontrolled Keywords

Aho-Corasick algorithm, node configuration, pattern matching, string matching, Deep Packet Inspection (DPI), Intrusion Detection System (IDS).

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2719 Architecture d'ordinateur et conception
2700 Technologie de l'information > 2722 Systèmes intégrés très grande échelle (VLSI)
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Funders: Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG)
Grant number: CRDPJ 462474-2013
Date Deposited: 15 Jan 2018 14:06
Last Modified: 24 Oct 2018 16:12
PolyPublie URL: https://publications.polymtl.ca/2854/


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only