Two-Phase Pattern Matching for Regular Expressions in Intrusion Detection Systems
Date Issued
2008
Date
2008
Author(s)
Yang, Chang-Ching
Abstract
Recently, network security has become an important issue. Agood number of network intrusion detection (NID) systems are employed to detect potential attacks. Some NID systems may use regular expressions to describe the signatures of security threats. Traditionally, we can build finite-state automata corresponding to these regular expressions to identify the suspicious packets. Because of the high speed and update ability, the memory-based deterministic finite-state automata(DFA) with one-pass-scanning model are desirable for NID systems. However in practical implementations, there are some signature patterns that can cause the state explosion problem when applying this model. A prototype of these signature patterns is “.*A.{N}B”.n this thesis, we first argue that the state explosion problem does exist in the common signature patterns of an NID system. Then we propose a two-phase matching approach for regular expressions to solve the state explosion problem. It reduces the state storage cost from the exponential complexity to linear complexity with respect to N. By applying this approach as a co-processing unit with the traditional DFA, the memory-based DFA approaches can be achieved in practice. We also implement the two-phase matching engine, which is called TPME unit, in a field programmable gate array(FPGA) and the throughput of the pattern matching process can achieve over 1.86 gigabits per second.
Subjects
Network Intrusion Detection
Pattern Matching
Regular Expressions
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95921079-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):2ca6934f2ff23671b5e95b9092cbb47f