Detail publikace

NFA Reduction for Regular Expressions Matching Using FPGA

Originální název

NFA Reduction for Regular Expressions Matching Using FPGA

Anglický název

NFA Reduction for Regular Expressions Matching Using FPGA

Jazyk

en

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.

BibTex


@inproceedings{BUT104513,
  author="Vlastimil {Košař} and Martin {Žádník} and Jan {Kořenek}",
  title="NFA Reduction for Regular Expressions Matching Using FPGA",
  annote="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.",
  address="IEEE Computer Society",
  booktitle="Proceedings of the 2013 International Conference on Field Programmable Technology",
  chapter="104513",
  edition="NEUVEDEN",
  howpublished="electronic, physical medium",
  institution="IEEE Computer Society",
  year="2013",
  month="december",
  pages="338--341",
  publisher="IEEE Computer Society",
  type="conference paper"
}