Synthesis of regular expressions for FPGAs

Abstract

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.

Keywords:

• regular expressions
• hardware synthesis
• field programmable gate arrays (FPGA)
• reconfigurable hardware
• hardware acceleration
• network intrusion detection systems

Acknowledgements

We would like to thank INESC-ID for a PhD scholarship and the partial support by the Portuguese Foundation for Science and Technology (FCT)–FEDER and POSI programs–under the CHIADO project (POSI/CHS/48018/2002). We also are in debt to Ioannis Sourdis for his help in some parts of this work.

Notes

Notes

1. Snort® is a registered trademark of Sourcefire®, Inc.

2. E.g., the April 2007 rule-set of Snort IDS (Snort 2007) includes about 3,610 distinct static patterns and 1,714 distinct regular expressions.

3. The main idea seems to have been introduced in Mukhopadhyay (1979).

4. SP-overlaps occur when the RegExpr is able to generate strings with equal suffix and prefix sets of chars among them.

5. A group is represented by a regular expression between parentheses.

6. The back-references in the rules have not been implemented.