Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23]

@

Journal of Information Science and Engineering, Vol. 26 No. 5, pp. 1563-1582 (September 2010)

Two-phase Pattern Matching for Regular Expressions in Intrusion Detection Systems

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.

Keywords: network intrusion detection, pattern matching, regular expressions, deterministic finite-state automata, two-phase matching engine

Full Text () Retrieve PDF document (201009_01.pdf)

Received March 5, 2009; revised June 22, 2009; accepted August 13, 2009.
Communicated by Tzong-Chen Wu.