Enhanced Aho-Corasick Algorithm for Network Intrusion Detection Systems

Document Type : Original Article

Authors

1 Computer Systems, FCIS

2 Computer systems department. FCIS

3 Department of Computer Systems, Faculty of Computer & Information Sciences, Ain Shams University, Abbasia, Cairo 11566, Egypt

4 Prof at Faculty of Computer & Information Sciences, Computer Systems Department, Ain Shams University, Cairo , Egypt.

Abstract

The exponential growth in internet data usage has created a pressing demand for highly efficient Network Intrusion Detection Systems (NIDS) capable of scaling with ever-increasing bandwidths to safeguard sensitive information. A cornerstone of NIDS, packet inspection, hinges on the ability to rapidly identify and analyze patterns within incoming data streams. The more diverse and extensive the pattern database, the more robust and effective the NIDS becomes. While the parallel failure-less version of the Aho-Corasick (AC) algorithm provides maximum parallelism, it faces significant memory constraints due to the large transition tables generated when dealing with a vast number of patterns. To mitigate this limitation and enhance the scalability of NIDS, we introduce a novel parallel failure-less compressed hashed variation of the Aho-Corasick algorithm. Our proposed approach leverages the power of compression and hashing techniques to significantly reduce memory consumption without compromising performance. Empirical evaluations demonstrate that our algorithm requires only a fraction (approximately the square root) of the memory footprint compared to the original parallel failure-less Aho-Corasick algorithm, making it a more practical and scalable solution for modern NIDS architectures.

Keywords