Split-DFA (SDFA) for Scalable Pattern Matching in Network Security

摘要

Security tasks such as network intrusion detection and virus scanning require high-speed pattern matching in order to be effective. A current problem is that high-speed pattern matching engines are not scalable. For instance, although Deterministic Finite Automata (DFA) are ideal for pattern matching in terms of speed because of their deterministic behavior, they are not scalable due to their excessive storage requirements. In this work we present Split-DFA (SDFA), a simple partition-based approach to DFA which dramatically reduces DFA storage requirements without affecting performance. We test SDFA with two pattern matching engines which implement SDFA with binary encoding and a structured clustered encoding. Both implementations show drastic reductions in DFA storage requirements, making SDFA scalable while preserving the performance of DFA, allowing for effective implementations of high-speed network intrusion detection, virus detection and other pattern matching tasks.