Detail publikace

Efficient Mapping of Nondeterministic Automata to FPGA for Fast Regular Expression Matching

Originální název

Efficient Mapping of Nondeterministic Automata to FPGA for Fast Regular Expression Matching

Anglický název

Efficient Mapping of Nondeterministic Automata to FPGA for Fast Regular Expression Matching

Jazyk

en

Originální abstrakt

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.  We propose new NFA--Split architecture, which reduces the amount of consumed FPGA resources in order to match larger set of regular expressions at multi-gigabit speed. The proposed reduction uses model of nondeterministic and deterministic automaton for effective mapping of regular expressions to FPGA. A new algorithm is designed to split the nondeterministic automaton transition table in order to map a part of the table into memory. The algorithm can place more than 49\% of transition table to memory, which reduces the amount of look-up tables by more than 43\% and flip-flops by more than 38\% for all selected sets of regular expressions. Moreover, a sparse transition table is mapped to memory with overlapped rows, which enables to store the table in a highly compact form.

Anglický abstrakt

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.  We propose new NFA--Split architecture, which reduces the amount of consumed FPGA resources in order to match larger set of regular expressions at multi-gigabit speed. The proposed reduction uses model of nondeterministic and deterministic automaton for effective mapping of regular expressions to FPGA. A new algorithm is designed to split the nondeterministic automaton transition table in order to map a part of the table into memory. The algorithm can place more than 49\% of transition table to memory, which reduces the amount of look-up tables by more than 43\% and flip-flops by more than 38\% for all selected sets of regular expressions. Moreover, a sparse transition table is mapped to memory with overlapped rows, which enables to store the table in a highly compact form.

BibTex


@inproceedings{BUT35427,
  author="Jan {Kořenek} and Vlastimil {Košař}",
  title="Efficient Mapping of Nondeterministic Automata to FPGA for Fast Regular Expression Matching",
  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.  We propose new
NFA--Split architecture, which reduces the amount of consumed FPGA resources in
order to match larger set of regular expressions at multi-gigabit speed. The
proposed reduction uses model of nondeterministic and deterministic automaton for
effective mapping of regular expressions to FPGA. A new algorithm is designed to
split the nondeterministic automaton transition table in order to map a part of
the table into memory. The algorithm can place more than 49\% of transition table
to memory, which reduces the amount of look-up tables by more than 43\% and
flip-flops by more than 38\% for all selected sets of regular expressions.
Moreover, a sparse transition table is mapped to memory with overlapped rows,
which enables to store the table in a highly compact form.",
  address="IEEE Computer Society",
  booktitle="Proceedings of the 13th IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems DDECS 2010",
  chapter="35427",
  edition="NEUVEDEN",
  howpublished="print",
  institution="IEEE Computer Society",
  year="2010",
  month="april",
  pages="54--59",
  publisher="IEEE Computer Society",
  type="conference paper"
}