Paper Info
Title
Two-phase Pattern Matching for Regular Expressions in Intrusion Detection Systems
Abstract
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.,". (star)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.
Year
Venue
Keywords
2010
JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
network intrusion detection,pattern matching,regular expressions,deterministic finite-state automata,two-phase matching engine
Field
DocType
Volume
Regular expression,Deterministic automaton,Computer science,Automaton,Network packet,Algorithm,Finite-state machine,Throughput,Pattern matching,Intrusion detection system
Journal
26
Issue
ISSN
Citations 
5
1016-2364
3
PageRank 
References 
Authors
0.43
16
3
Name
Order
Citations
PageRank
Chang-Ching Yang130.43
Chen-Mou Cheng229528.77
Sheng-De Wang372068.13