A Fast Two-Phase Multi-Character Dynamically Reconfigurable Regular Expression Matching Architecture
Date Issued
2009
Date
2009
Author(s)
Hsu, Shu-Wei
Abstract
Network security has recently become an important issue. With the growing of high-speed networks, there is a growing demand for high performance network intrusion detection systems (NIDSs). Some NIDSs may use regular expressions to describe the signatures of security threats. Traditionally, we can build finite-state automaton corresponding to these regular expressions to identify the suspicious packets. Deterministic finite-state automata (DFA) and non-deterministic finite-state automata (NFA) are commonly used for regular expressions matching. The DFA does one-pass scanning with a larger storage cost, while the NFA does multi-pass scanning with a less storage cost. his thesis focuses on the state explosion problem existing in the common signature patterns of an NIDS, and how to reduce the state storage cost from the exponential complexity to linear complexity. Through the common string states sharing, we propose a two-phases matching architecture combining DFA and NFA. This architecture constructs circuit-based parallel matching with prefix sharing, while the remains state transition tables stored in off-chip memory spaces. Furthermore, with multiplexers, fully system matching patterns are dynamically reconfigurable. We also implement the two-phase matching engine in a field programmable gate array (FPGA). Through parallel state operations, the optimized architecture will process four characters at 230 MHz, resulting in a concurrent throughput of 1.84 Gbps. If the 4-character processing module is implemented, higher throughput can be achieved.
Subjects
Network Intrusion Detection
Multi-Character
Dynamically Reconfigurable
Pattern Matching
Regular Expressions
DFA
NFA
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-J96921021-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):c9f32e813a6e2e61450b706e64cad9d0