A Scalable Architecture For High-Throughput Regular-Expression Pattern Matching
Authors:
- D.E. TaylorDTD.E. Taylor
- R.K. CytronRCR.K. Cytron
- 21 July 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636897,p. 191-202
Abstract
We present and evaluate an architecture for high-throughput pattern matching of regular expressions. Our approach matches multiple patterns concurrently, responds rapidly to changes in the pattern set, and is well suited for synthesis in an ASIC or FPGA. Our approach is based on a new and easily pipelined state-machine representation that uses encoding and compression techniques to improve density. We have written a compiler that translates a set of regular expressions and optimizes their deployment in the structures used by our architecture. We analyze our approach in terms of its throughput, density, and efficiency. We present experimental results from an implementation in a commodity FPGA, showing better throughput and density than the best known approachesKeywords
This publication has 13 references indexed in Scilit:
- High-throughput linked-pattern matching for intrusion detection systems2005
- A High Throughput String Matching Architecture for Intrusion Detection and PreventionACM SIGARCH Computer Architecture News, 2005
- Configurable string matching hardware for speeding up intrusion detectionACM SIGARCH Computer Architecture News, 2005
- Characterizing antivirus workload executionACM SIGARCH Computer Architecture News, 2005
- Scalable Pattern Matching for High Speed Networks2004
- A recursive MISD architecture for pattern matchingIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2004
- Deep packet inspection using parallel bloom filtersIEEE Micro, 2004
- FPsed: a streaming content search-and-replace module for an Internet firewall2004
- Fast, Large-Scale String Match for a 10Gbps FPGA-Based Network Intrusion Detection System2003
- Assisting network intrusion detection with reconfigurable hardware2003