| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] | [ 20] | [ 21] | [ 22] | [ 23] |
¡@
CHANG-CHING YANG, CHEN-MOU CHENG AND SHENG-DE WANG
Department of Electrical Engineering
National Taiwan University
Taipei, 106 Taiwan
Regular expressions are used to describe security threats¡¦ signatures in network intrusion
detection (NID) systems. To identify suspicious packets using regular expression
matching, many NID systems use memory-based deterministic finite-state automata
(DFA) with one-pass-scanning model, which is fast and allows dynamic updates. However,
a number of practical signature patterns commonly found in a variety of NID systems,
e.g., ".*A.{N}B", can cause a state-explosion problem in such a model. In this
paper, we propose a two-phase pattern matching engine (TPME) to solve this problem.
In our proposed approach, the state storage cost is reduced to linearly dependent on the
number of repetitions N in the patterns. With the new approach, we are now able to handle
those practical patterns that would have caused the state-explosion problem in memory-
based DFA. We report our implementation of TPME on a field programmable gate
array (FPGA). With our prototype implementation, we can achieve a throughput of more
than 1.86 gigabits per second for pattern matching in a practical NID system.
Received March 5, 2009; revised June 22, 2009; accepted August 13, 2009.
Communicated by Tzong-Chen Wu.