Synthesis of Regular Expressions for FPGAs

• Type: Article in International Scientific Journal
• Date: 2008

Authors

João Bispo (Author) FEUP; João M. P. Cardoso (Author) FEUP

Journal

Title: International Journal of Electronics

Vol. 95 No. 7

Pages: 685-704

ISSN: 0020-7217

Publisher: Taylor & Francis

Indexing

ISI Web of Knowledge - 6 Citations

ISI Web of Science

Scopus - 6 Citations

INSPEC

COMPENDEX

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

CORDIS: Technological sciences > Engineering > Electronic engineering

Other information

Authenticus ID: P-004-3NA

DOI: DOI:10.1080/00207210801924107

Abstract (EN): Regular expressions are being used in many applications to specify multiple and complex text patterns in a compact way. In some of these applications large sets of regular expressions need to be evaluated to detect matched content. Specialised hardware engines are employed when software-based regular expression engines are not able to meet the performance requirements imposed by such applications. Since the sets of regular expressions are periodically modified and/or extended, FPGAs are an attractive hardware solution to achieve both programmability and high-performance demands. However, efficient automatic synthesis tools are of paramount importance to achieve fast prototyping of regular expression engines on these devices. This paper presents an overview of the synthesis of regular expressions with the aim of achieving high-performance engines for FPGAs. We focus on describing current solutions, proposing new solutions for constraint repetitions and overlapped matching, and discussing a number of challenges and open issues. As a case study, we present FPGA implementations of the regular expressions included in two rule-sets of network intrusion detection system (NIDS), Bleeding Edge and Snort, obtained using a state-of-the-art synthesis approach.

Language: English

Type (Professor's evaluation): Scientific