Research On Automatic Generation Methods Of Regular Expression Matching Engines On FPGA

Regular expression is a pattern matching mechanism, which is being used on text processing and network intrusion detection due to its advantages of expressibility and compactness. The popular deep packet inspection system snort utilizes regular expression as pattern language. With the increase of network bandwidth, regular expression matching becomes the bottleneck of the software-based Intrusion Detection Systems(IDS). Many researchers have been studying hardware architectures for regular expressions matching overcoming the performance achievable with software. Hardware engine is used as a co-processor by IDS to improve the performance of regular expression matching. However, the current hardware engines need manual construction. With the rapid update and of ruleset, it has thus been impossible to generate hardware engine manually.By studying the principle of regular expression matching and compiler technology, an automatic generation method of regular expression matching engine on FPGA was presented. Automatic generation is performed in threes steps:parsing the regular expression into tree structures, constructing the NFAs, maping NFAs into structural VHDL suitable for FPGA implementation. The automatic system takes advantages of previous works, performs conversion of regular expression into FPGA circuits by adopting general modules and NFA approach. The system can not only to generate a regular expression matching engine for implementation in a small amount of time, but also to avoid the tedious and error-prone circuit construction. Experimental results show that our system generates a regular expression matching engine circuit matching over hundreds of regular expression in just a few seconds, and the generation matching engine achieves a high-performance.