Software Toolchain for Large-Scale RE-NFA Construction on FPGA

Abstract EN

We present a software toolchain for constructing large-scale regular expression matching (REM) on FPGA.

The software automates the conversion of regular expressions into compact and high-performance nondeterministic finite automata (RE-NFA).

Each RE-NFA is described as an RTL regular expression matching engine (REME) in VHDL for FPGA implementation.

Assuming a fixed number of fan-out transitions per state, an n-state m-bytes-per-cycle RE-NFA can be constructed in O(n×m) time and O(n×m) memory by our software.

A large number of RE-NFAs are placed onto a two-dimensional staged pipeline, allowing scalability to thousands of RE-NFAs with linear area increase and little clock rate penalty due to scaling.

On a PC with a 2 GHz Athlon64 processor and 2 GB memory, our prototype software constructs hundreds of RE-NFAs used by Snort in less than 10 seconds.

We also designed a benchmark generator which can produce RE-NFAs with configurable pattern complexity parameters, including state count, state fan-in, loop-back and feed-forward distances.

Several regular expressions with various complexities are used to test the performance of our RE-NFA construction software.