Ing. Jan Kořenek, 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. 338-341. ISBN 978-1-4799-2199-7.
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:338-341
Proceedings:Proceedings of the 2013 International Conference on Field Programmable Technology
Conference:The 2013 International Conference on Field-Programmable Technology
Place:Kyoto, JP
Year:2013
ISBN:978-1-4799-2199-7
Publisher:IEEE Computer Society
Files: 
++Type Name Title Size Last modified
iconpaper.pdf121 KB2014-01-06 12:35:47
^ Select all
With selected:
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 = {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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=10306}
}

Your IPv4 address: 54.158.55.5
Switch to IPv6 connection

DNSSEC [dnssec]