A PCRE Pattern Matching Architecture with Counter Sharing
Date Issued
2010
Date
2010
Author(s)
Li, Ying-Hsien
Abstract
Regular expressions and PCREs are widely used as a description language in many Network Intrusion Detection Systems (NIDS). To keep up with the high speed of modern networks, several NFA-based hardware architectures for performing regular expression matching were proposed previously. However, due to the rapid increase in the amount of signature patterns, the minimizing of the area of the circuit to accommodate all patterns has become a challenge. This thesis proposes a novel counter sharing architecture to reduce the number of counters used in NFA circuits and thus reduce the gate count of the regular expression matching circuit. We design an algorithm to determine if a counter can be shared with others. Also, a graph coloring algorithm is implemented to decide a group of counters that can share a common counter, making the total number of counters as small as possible. In addition, rather than competing with other area-optimized techniques, our approach can be integrated with them, hence achieving a higher reduction rate. Experimental results show that our approach can indeed reduce the area of the matching circuit, and a much higher reduction is achieved through integrating with other area-optimized approach.
Subjects
NIDS
Regular Expression
PCRE
Pattern Matching
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-99-R97921064-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):70cae23fdce1ee6f15b135c6bd9224f9