Detail publikačního výsledku

NFA Reduction for Regular Expressions Matching Using FPGA

KOŠAŘ, V.; ŽÁDNÍK, M.; KOŘENEK, J.

Originální název

NFA Reduction for Regular Expressions Matching Using FPGA

Anglický název

NFA Reduction for Regular Expressions Matching Using FPGA

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

FPGA, NFA, Reduction, Regular expressions matching

Klíčová slova v angličtině

FPGA, NFA, Reduction, Regular expressions matching

Autoři

KOŠAŘ, V.; ŽÁDNÍK, M.; KOŘENEK, J.

Rok RIV

2014

Vydáno

09.12.2013

Nakladatel

IEEE Computer Society

Místo

Kyoto

ISBN

978-1-4799-2199-7

Kniha

Proceedings of the 2013 International Conference on Field Programmable Technology

Strany od

338

Strany do

341

Strany počet

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/"
}

Dokumenty

paper