Přístupnostní navigace
E-application
Search Search Close
Publication detail
KOŠAŘ, V. ŽÁDNÍK, M. KOŘENEK, J.
Original Title
NFA Reduction for Regular Expressions Matching Using FPGA
Type
article in a collection out of WoS and Scopus
Language
English
Original 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.
Keywords
FPGA, NFA, Reduction, Regular expressions matching
Authors
KOŠAŘ, V.; ŽÁDNÍK, M.; KOŘENEK, J.
RIV year
2013
Released
9. 12. 2013
Publisher
IEEE Computer Society
Location
Kyoto
ISBN
978-1-4799-2199-7
Book
Proceedings of the 2013 International Conference on Field Programmable Technology
Pages from
338
Pages to
341
Pages count
4
URL
https://www.fit.vut.cz/research/publication/10306/
BibTex
@inproceedings{BUT104513, author="Vlastimil {Košař} and Martin {Žádník} and Jan {Kořenek}", title="NFA Reduction for Regular Expressions Matching Using FPGA", booktitle="Proceedings of the 2013 International Conference on Field Programmable Technology", year="2013", pages="338--341", publisher="IEEE Computer Society", address="Kyoto", isbn="978-1-4799-2199-7", url="https://www.fit.vut.cz/research/publication/10306/" }