Fast Regular Expression Matching Using FPGA
Jan Koÿ · 2010
With the growing number of viruses and network attacks, Intrusion Detection Systems have to match a large set of regular expressions at multi-gigabit speed to detect ma- licious activities on the network. Many algorithms and architectures have been designed to accelerate pattern matching, but most of them can be used only for strings or a small set of regular expressions. The capacity of avail- able FPGA chips is a limitation for architectures based on a nondeterministic finite automaton. Therefore we pro- pose new algorithm to find a non-collision set of states which enables to map a part of the transition table to the memory instead of the FPGA logic cells. For all analysed sets of regular expressions, the algorithm was able to find a non-collision set with 61.4 % of states in average and a non-collision set with 83.6 % of states for the best case. System of Parallel Automaton Parts is introduced, it is a model which represent a division of the automaton by sets of states. New NFA Split architecture is proposed for mapping of the model to the FPGA. As non-collision sets of states are mapped to the hardware architecture with embedded memory blocks, the amount of consumed flip- flop registers and look-up tables is significantly decreased. For all tested sets of regular expressions, the NFA Split architecture reduces the amount of consumed flip-flops to 43.3 % and look-up tables to 66.8 % in average.