Faculty of Information Technology, BUT

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