Two-phase Pattern Matching for Regular Expressions in Intrusion Detection Systems.
Journal
Journal of Information Science and Engineering
Journal Volume
26
Journal Issue
5
Pages
1563-1582
Date Issued
2010
Author(s)
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., ". *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.
SDGs
Other Subjects
Dynamic update; Finite-state automata; Gigabits per second; Intrusion Detection Systems; Network intrusion detection; New approaches; One-pass; Prototype implementations; Regular expressions; Regular-expression matching; Security threats; Storage costs; Two-phase matching engine; Computer crime; Field programmable gate arrays (FPGA); Network security; Pattern matching; Phase matching; Problem solving; Software prototyping; Intrusion detection
Type
journal article