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. 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: | |
---|
| 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}
} |
|