Ing. Jan Kořenek, Ph.D.
KOŘENEK Jan. Fast Regular Expression Matching Using FPGA. Information Sciences and Technologies Bulletin of the ACM Slovakia. Bratislava: Vydavateľstvo STU, 2010, vol. 2, no. 2, pp. 103111. ISSN 13381237.  Publication language:  english 

Original title:  Fast Regular Expression Matching Using FPGA 

Title (cs):  Rychlé vyhledávání regulárních výrazů s využitím technologie FPGA 

Pages:  103111 

Place:  SK 

Year:  2010 

Journal:  Information Sciences and Technologies Bulletin of the ACM Slovakia, Vol. 2, No. 2, Bratislava, SK 

ISSN:  13381237 

Keywords 

Regular expression, matching, nondeterministic automaton, FPGA

Annotation 

With the growing number of viruses and network attacks, Intrusion Detection Systems have to match a large set of regular expressions at multigigabit speed to detect malicious 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 available FPGA chips is a limitation for architectures based on a nondeterministic finite automaton. Therefore we propose new algorithm to find a noncollision 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 noncollision set with 61.4% of states in average and a noncollision 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 noncollision sets of states are mapped to the hardware architecture with embedded memory blocks, the amount of consumed flipflop registers and lookup tables is significantly decreased. For all tested sets of regular expressions, the NFA Split architecture reduces the amount of consumed flipflops to 43.3% and lookup tables to 66.8% in average.

BibTeX: 

@ARTICLE{
author = {Jan Ko{\v{r}}enek},
title = {Fast Regular Expression Matching Using FPGA},
pages = {103111},
journal = {Information Sciences and Technologies Bulletin of the ACM
Slovakia},
volume = {2},
number = {2},
year = {2010},
ISSN = {13381237},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9511}
} 
