Space Optimization on Counters for FPGA-Based Perl Compatible Regular Expressions

• Published in: ACM transactions on reconfigurable technology and systems 2009-09, Vol.2 (4), p.1-18
• Main Authors: Lo, Chia-Tien Dan, Tai, Yi-Gang
• Format: Article
• Language: English
• ISSN: 1936-7406; 1936-7414
• DOI: 10.1145/1575779.1575783

With their expressiveness and simplicity, Perl compatible regular expressions (PCREs) have been adopted in mainstream signature based network intrusion detection systems (NIDSs) to describe known attack signatures, especially for polymorphic worms. NIDSs rely on an underlying string matching engine that simulates PCREs to inspect each network packet. PCRE is a superset of traditional regular expressions, and provides advanced features. However, this pattern matching becomes a performance bottleneck of software-based NIDSs, causing a big portion of their execution time to be dedicated to payload inspection, which results in an unacceptable packet drop rate. The penetration of these unexamined packets creates a security hole in such systems. Over the past decade, hardware acceleration for the pattern matching has been studied extensively and a marginal performance has been achieved. Among hardware approaches, FPGA-based acceleration engines provide great flexibility because new signatures can be compiled and programmed into their reconfigurable architecture. As more and more malicious signatures are discovered, it becomes harder to map a complete set of malicious signatures specified in PCREs to an FPGA chip. One of the space consuming components is the counter used in the constrained repetitions for PCREs. Therefore, we propose a space efficient SelectRAM counter for PCREs that use counting. The design takes advantage of the basic components contained in a configurable logic block, and thus optimizes space usage. A set of basic PCRE blocks has been built in hardware to implement PCREs. Experimental results show that the proposed scheme outperforms existing designs by at least fivefold.