- 期刊
- OpenAccess
Two-phase Pattern Matching for Regular Expressions in Intrusion Detection Systems
摘要
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.
延伸閱讀
- Tsai, W. Y. (2006). A Novel Multi-pattern Matching Algorithm and Implementation in SoC System [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-1303200709331594
- Wei, S. D. (2008). Efficient and Robust Pattern Matching Algorithms for Different Applications [doctoral dissertation, National Tsing Hua University]. Airiti Library. https://doi.org/10.6843/NTHU.2008.00028
- Huang, D. C., Lo, H. C., Lai, P. L., & Chen, W. M. (2012). A Multiple Pattern Matching Method for Malicious Code Detection. 網際網路技術學刊, 13(2), 181-193. https://doi.org/10.6138/JIT.2012.13.2.02
- 陳建麟（2007）。A Parallel String Matching Algorithm for High Speed Network Intrusion Detection System〔碩士論文，國立清華大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0016-1411200715165341
- Chang, M. C. (2004). Applying Multi-Pattern Matching Solution to Enhance the Efficiency of Intrusion Detection [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2004.10228