Optimization of pattern matching algorithm for memory based architecture

Cheng Hung Lin, Yu Tang Tai, Shih Chieh Chang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

Due to the advantages of easy re-configurability and scalability, the memory-based string matching architecture is widely adopted by network intrusion detection systems (NIDS). In order to accommodate the increasing number of attack patterns and meet the throughput requirement of networks, a successful NIDS system must have a memory-efficient pattern-matching algorithm and hardware design. In this paper, we propose a memory-efficient pattern-matching algorithm which can significantly reduce the memory requirement. For total Snort string patterns, the new algorithm achieves 29% of memory reduction compared with the traditional Aho-Corasick algorithm [5]. Moreover, since our approach is orthogonal to other memory reduction approaches, we can obtain substantial gain even after applying the existing state-of-the-art algorithms. For example, after applying the bit-split algorithm [9], we can still gain an additional 22% of memory reduction.

Original languageEnglish
Title of host publicationANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications
Pages11-16
Number of pages6
DOIs
Publication statusPublished - 2007 Dec 1
Event3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2007 - Orlando, FL, United States
Duration: 2007 Dec 32007 Dec 4

Publication series

NameANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications

Other

Other3rd ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS 2007
CountryUnited States
CityOrlando, FL
Period07/12/307/12/4

    Fingerprint

Keywords

  • DFA
  • intrusion detection
  • pattern matching

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

Lin, C. H., Tai, Y. T., & Chang, S. C. (2007). Optimization of pattern matching algorithm for memory based architecture. In ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications (pp. 11-16). (ANCS'07 - Proceedings of the 2007 ACM Symposium on Architecture for Networking and Communications). https://doi.org/10.1145/1323548.1323551