Publication detail

Fast Regular Expression Matching Using FPGA

KOŘENEK, J.

Original Title

Fast Regular Expression Matching Using FPGA

English Title

Fast Regular Expression Matching Using FPGA

Type

journal article - other

Language

en

Original Abstract

With the growing number of viruses and network attacks, Intrusion Detection Systems have to match a large set of regular expressions at multi-gigabit speed to detect malicious activities on the network.  Many algorithms and architectures have been designed to accelerate pattern matching, but most of them can be used only for strings or a small set of regular expressions. The capacity of available FPGA chips is a limitation for architectures based on a nondeterministic finite automaton. Therefore we propose new algorithm to find a non-collision set of states which enables to map a part of the transition table to the memory instead of the FPGA logic cells. For all analysed sets of regular expressions, the algorithm was able to find a non-collision set with 61.4% of states in average and a non-collision set with 83.6 % of states for the best case. System of Parallel Automaton Parts is introduced, it is a model which represent a division of the automaton by sets of states. New NFA Split architecture is proposed for mapping of the model to the FPGA. As non-collision sets of states are mapped to the hardware architecture with embedded memory blocks, the amount of consumed flip-flop registers and look-up tables is significantly decreased. For all tested sets of regular expressions, the NFA Split architecture reduces the amount of consumed flip-flops to 43.3% and look-up tables to 66.8% in average.

English abstract

With the growing number of viruses and network attacks, Intrusion Detection Systems have to match a large set of regular expressions at multi-gigabit speed to detect malicious activities on the network.  Many algorithms and architectures have been designed to accelerate pattern matching, but most of them can be used only for strings or a small set of regular expressions. The capacity of available FPGA chips is a limitation for architectures based on a nondeterministic finite automaton. Therefore we propose new algorithm to find a non-collision set of states which enables to map a part of the transition table to the memory instead of the FPGA logic cells. For all analysed sets of regular expressions, the algorithm was able to find a non-collision set with 61.4% of states in average and a non-collision set with 83.6 % of states for the best case. System of Parallel Automaton Parts is introduced, it is a model which represent a division of the automaton by sets of states. New NFA Split architecture is proposed for mapping of the model to the FPGA. As non-collision sets of states are mapped to the hardware architecture with embedded memory blocks, the amount of consumed flip-flop registers and look-up tables is significantly decreased. For all tested sets of regular expressions, the NFA Split architecture reduces the amount of consumed flip-flops to 43.3% and look-up tables to 66.8% in average.

Keywords

Regular expression, matching, nondeterministic automaton, FPGA

RIV year

2010

Released

02.12.2010

Publisher

NEUVEDEN

Location

NEUVEDEN

ISBN

1338-1237

Periodical

Information Sciences and Technologies Bulletin of the ACM Slovakia

Year of study

2

Number

2

State

SK

Pages from

103

Pages to

111

Pages count

9

Documents

BibTex


@article{BUT50432,
  author="Jan {Kořenek}",
  title="Fast Regular Expression Matching Using FPGA",
  annote="With the growing number of viruses and network attacks, Intrusion Detection
Systems have to match a large set of regular expressions at multi-gigabit speed
to detect malicious activities on the network.  Many algorithms and architectures
have been designed to accelerate pattern matching, but most of them can be used
only for strings or a small set of regular expressions. The capacity of available
FPGA chips is a limitation for architectures based on a nondeterministic finite
automaton. Therefore we propose new algorithm to find a non-collision set of
states which enables to map a part of the transition table to the memory instead
of the FPGA logic cells. For all analysed sets of regular expressions, the
algorithm was able to find a non-collision set with 61.4% of states in average
and a non-collision set with 83.6 % of states for the best case. System of
Parallel Automaton Parts is introduced, it is a model which represent a division
of the automaton by sets of states. New NFA Split architecture is proposed for
mapping of the model to the FPGA. As non-collision sets of states are mapped to
the hardware architecture with embedded memory blocks, the amount of consumed
flip-flop registers and look-up tables is significantly decreased. For all tested
sets of regular expressions, the NFA Split architecture reduces the amount of
consumed flip-flops to 43.3% and look-up tables to 66.8% in average.",
  address="NEUVEDEN",
  chapter="50432",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  number="2",
  volume="2",
  year="2010",
  month="december",
  pages="103--111",
  publisher="NEUVEDEN",
  type="journal article - other"
}