An Efficient Hardware Matching Engine for Regular Expression with Nested Kleene Operators

In this paper, we propose a systolic pattern-independent hardware regular expression matching (REM) engine which handles nested Kleene operators used in virus patterns. Pattern-independent systolic REM engines are suitable to network intrusion detection systems for quick updating of virus pattern. In the proposed engine, we introduce a compact pattern-independent NFA circuit, which can handle any small regular expression patterns, into a systolic REM engine to handle nested Kleene operators. Experimental results show that the extended engine implemented on an FPGA handles nested Kleene operators with efficient circuit size and high performance (2.17 Gbps).