IEEE Journal on Selected Areas in Communications · 2006 · 74 citations · 28 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureComputer SecurityParallel ComputingAutomata TheoryFinite AutomataIntrusion DetectionMemory Hierarchy OptimizationParallel ArchitecturesParallel Computer ArchitectureAttack Signature MatchingDeterministic Finite AutomataFinite Automata TheoryMemory ArchitectureNetwork Intrusion DetectionNetwork-based Intrusion DetectionParallel String Matching
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.
28
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Introduction to automata theory, languages, and computation
Computer Languages · 1980 · 6.9K citations
Alfred V. Aho, Margaret J. Corasick · Communications of the ACM · 1975 · 2.9K citations · Full text