A pattern-matching scheme with high throughput performance and low memory requirement

Tsern-Huei Lee, Nai Lun Huang

Research output: Contribution to journalArticle

11 Scopus citations

Abstract

Pattern-matching techniques have recently been applied to network security applications such as intrusion detection, virus protection, and spam filters. The widely used Aho-Corasick (AC) algorithm can simultaneously match multiple patterns while providing a worst-case performance guarantee. However, as transmission technologies improve, the AC algorithm cannot keep up with transmission speeds in high-speed networks. Moreover, it may require a huge amount of space to store a two-dimensional state transition table when the total length of patterns is large. In this paper, we present a pattern-matching architecture consisting of a stateful pre-filter and an AC-based verification engine. The stateful pre-filter is optimal in the sense that it is equivalent to utilizing all previous query results. In addition, the filter can be easily realized with bitmaps and simple bitwise-AND and shift operations. The size of the two-dimensional state transition table in our proposed architecture is proportional to the number of patterns, as opposed to the total length of patterns in previous designs. Our proposed architecture achieves a significant improvement in both throughput performance and memory usage.

Original languageEnglish
Article number6357263
Pages (from-to)1104-1116
Number of pages13
JournalIEEE/ACM Transactions on Networking
Volume21
Issue number4
DOIs
StatePublished - 1 Jan 2013

Keywords

  • Aho-Corasick (AC) algorithm
  • Bloom filter
  • Pattern matching
  • deep packet inspection

Fingerprint Dive into the research topics of 'A pattern-matching scheme with high throughput performance and low memory requirement'. Together they form a unique fingerprint.

  • Cite this