<  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

Poster (2016)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Accepted Version
Terms of Use: All rights reserved
Download (182kB)
Show abstract
Hide abstract

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).

Subjects: 2700 Information technology > 2719 Computer architecture and design
2700 Information technology > 2722 VLSI systems
Department: Department of Computer Engineering and Software Engineering
Funders: Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG)
Grant number: CRDPJ 462474-2013
PolyPublie URL: https://publications.polymtl.ca/2854/
Conference Title: ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2016)
Conference Location: Santa Clara, Californie
Conference Date(s): 2016-03-17 - 2016-03-18
Publisher: ACM
DOI: 10.1145/2881025.2889473
Official URL: https://doi.org/10.1145/2881025.2889473
Date Deposited: 15 Jan 2018 14:06
Last Modified: 19 Oct 2023 18:25
Cite in APA 7: 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 [Poster]. ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2016), Santa Clara, Californie (2 pages). https://doi.org/10.1145/2881025.2889473

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only

View Item View Item