A Memory-Efficient Parallel String Matching Architecture for High-Speed Intrusion Detection

Citations Over TimeTop 10% of 2006 papers

Abstract

The ability to inspect both packet headers and payloads to identify attack signatures makes network intrusion detection system (NIDS) a promising approach to protect Internet systems. Since most of the known attacks can be represented with strings or combinations of multiple substrings, string matching is a key component, as well as the bottleneck in NIDS to address the requirement of constantly increasing capacity. We propose a memory-efficient multiple-character-approaching architecture consisting of multiple parallel deterministic finite automata (DFAs), called TDP-DFA. By employing efficient representations for the transition rules in each DFA, TDP-DFA significantly reduces the complexity. We also present a novel scheme to share the storage of transition rules among multiple DFAs, substantially decreasing the total storage cost, and avoiding the cost increase being proportional to the number of DFAs. We evaluate this design through theoretical analysis and comprehensive experiments. Results show that TDP-DFA is able to meet the critical requirement of OC-768 wirespeed processing, as well as constituting a promising way for scaling up to cope with throughput over 100 Gb/s in the future.

Related Papers

• → A Memory-Efficient Deterministic Finite Automaton-Based Bit-Split String Matching Scheme Using Pattern Uniqueness in Deep Packet Inspection(2015)12 cited
• → Deterministic Finite Automata for pattern matching in FPGA for intrusion detection(2011)10 cited
• → DFA-Based Regular Expression Matching on Compressed Traffic(2011)7 cited
• → A survey on Finite Automata based pattern matching techniques for network Intrusion Detection System (NIDS)(2014)6 cited
• → String Localization and Regular Expressions(2021)