Ing. Martin Žádník, Ph.D.
KOŠAŘ Vlastimil, ŽÁDNÍK Martin and KOŘENEK Jan. NFA Reduction for Regular Expressions Matching Using FPGA. In: Proceedings of the 2013 International Conference on Field Programmable Technology. Kyoto: IEEE Computer Society, 2013, pp. 338341. ISBN 9781479921997.  Publication language:  english 

Original title:  NFA Reduction for Regular Expressions Matching Using FPGA 

Title (cs):  Redukce NKA pro vyhledávání řetězců popsaných regulárními výrazy v FPGA 

Pages:  338341 

Proceedings:  Proceedings of the 2013 International Conference on Field Programmable Technology 

Conference:  The 2013 International Conference on FieldProgrammable Technology 

Place:  Kyoto, JP 

Year:  2013 

ISBN:  9781479921997 

Publisher:  IEEE Computer Society 

Files:  

 Keywords 

FPGA, NFA, Reduction, Regular expressions matching

Annotation 

Many algorithms have been proposed to accelerate regular expression matching via mapping of a nondeterministic finite automaton into a circuit implemented in an FPGA. These algorithms exploit unique features of the FPGA to achieve high throughput. On the other hand the FPGA poses a limit on the number of regular expressions by its limited resources. In this paper, we investigate applicability of NFA reduction techniques  a formal aparatus to reduce the number of states and transitions in NFA prior to its mapping into FPGA. The paper presents several NFA reduction techniques, each with a different reduction power and time complexity. The evaluation utilizes regular expressions from Snort and L7 decoder. The best NFA reduction algorithms achieve more than 66% reduction in the number of states for a Snort ftp module. Such a reduction translates directly into 66% LUT and FF saving in the FPGA.

BibTeX: 

@INPROCEEDINGS{
author = {Vlastimil Ko{\v{s}}a{\v{r}} and Martin
{\v{Z}}{\'{a}}dn{\'{i}}k and Jan Ko{\v{r}}enek},
title = {NFA Reduction for Regular Expressions Matching Using FPGA},
pages = {338341},
booktitle = {Proceedings of the 2013 International Conference on Field
Programmable Technology},
year = {2013},
location = {Kyoto, JP},
publisher = {IEEE Computer Society},
ISBN = {9781479921997},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=10306}
} 
