Node Configuration for the Aho-Corasick Algorithm in Intrusion Detection Systems
| Title | Node Configuration for the Aho-Corasick Algorithm in Intrusion Detection Systems |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Lacroix, Alexsandre B., Langlois, J.M. Pierre, Boyer, François-Raymond, Gosselin, Antoine, Bois, Guy |
| Conference Name | Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-4183-7 |
| Keywords | Aho-Corasick algorithm, composability, Computing Theory, deep packet inspection, Deep Packet Inspection (DPI), Intrusion Detection System (IDS), Metrics, node configuration, Pattern matching, pubcrawl, Scalability, security metrics, string matching |
| 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 12x compared with the single node-type case. |
| URL | http://doi.acm.org/10.1145/2881025.2889473 |
| DOI | 10.1145/2881025.2889473 |
| Citation Key | lacroix_node_2016 |