Regular Expression Matching in Reconfigurable Hardware

• Tipo: Artigo em Revista Científica Internacional
• Data: 2008

Autores

Yiannis Sourdis (Autor) Outra; Stamatis Vassiliadis (Autor) Outra; João Bispo (Autor) Outra; João M. P. Cardoso (Autor) FEUP

Revista

Título: Journal of Signal Processing Systems

Vol. 51 Nº 1

Páginas: 99-121

ISSN: 1939-8018

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 44 Citações

ISI Web of Science

Scopus - 56 Citações

COMPENDEX

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia electrotécnica, electrónica e informática

CORDIS: Ciências Tecnológicas

Outras Informações

ID Authenticus: P-004-0M9

DOI: 10.1007/s11265-007-0131-0

Abstract (EN): In this paper we describe a regular expression pattern matching approach for reconfigurable hardware. Following a Non-deterministic Finite Automata direction, we introduce three new basic building blocks to support constraint repetitions syntaxes more efficiently than previous works. In addition, a number of optimization techniques are employed to reduce the area cost of the designs and maximize performance. Our design methodology is supported by a tool that automatically generates the circuitry for the given regular expressions and outputs Hardware Description Language representations ready for logic synthesis. The proposed approach is evaluated on network Intrusion Detection Systems (IDS). Recent IDS use regular expressions to represent hazardous packet payload contents. They require high-speed packet processing providing a challenging case study for pattern matching using regular expressions. We use a number of IDS rulesets to show that our approach scales well as the number of regular expressions increases, and present a step-by-step optimization to survey the benefits of our techniques. The synthesis tool described in this study is used to generate hardware engines to match 300 to 1,500 IDS regular expressions using only 10-45 K logic cells and achieving throughput of 1.6-2.2 and 2.4-3.2 Gbps on Virtex2 and Virtex4 devices, respectively. Concerning the throughput per area required per matching non-Meta character, our hardware engines are 10-20 x more efficient than previous Field Programmable Gate Array approaches. Furthermore, the generated designs have comparable area requirements to current application-specific integrated circuit solutions.

Idioma: Português

Tipo (Avaliação Docente): Científica