Publication Details

NFA Reduction for Regular Expressions Matching Using FPGA

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. 338-341. ISBN 978-1-4799-2199-7.
Czech title
Redukce NKA pro vyhledávání řetězců popsaných regulárními výrazy v FPGA
Type
conference paper
Language
english
Authors
Keywords

FPGA, NFA, Reduction, Regular expressions matching

Abstract

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.

Published
2013
Pages
338-341
Proceedings
Proceedings of the 2013 International Conference on Field Programmable Technology
Conference
The 2013 International Conference on Field-Programmable Technology, Kyoto, JP
ISBN
978-1-4799-2199-7
Publisher
IEEE Computer Society
Place
Kyoto, JP
BibTeX
@INPROCEEDINGS{FITPUB10306,
   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 = "338--341",
   booktitle = "Proceedings of the 2013 International Conference on Field Programmable Technology",
   year = 2013,
   location = "Kyoto, JP",
   publisher = "IEEE Computer Society",
   ISBN = "978-1-4799-2199-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/10306"
}
Files
Back to top