Cache-Based Scalable Deep Packet Inspection with Predictive Automaton

Abstract—Regular expression (Regex) becomes the standard signature language for security and application detection. De-terministic finite automata (DFAs) are widely used to perform multiple regex matching in linear time. However, when imple-mented by modern memories, the matching speed turns out to be a tradeoff with the size of DFA. To improve the performance, we propose a generalized caching scheme that strike the boundaries of memory size. We define the concept of local prediction which predicts the memory accesses to the DFA and guides the cache to be replaced with proper states so that the cache hit rate is greatly raised. The idea of using predictive DFA matching specifies an entire new class of approaches. We also develop techniques to intelligently store the DFA using local prediction so that given any replacement policy, the caching scheme would produce nice performance. Evaluation shows that our storage achieves a 30% higher cache hit in comparison with the previously proposed approaches. Especially, our approach appears to be more robust when processing malicious traffics. By analyzing numeric results, the optimal configurations that achieve the ultimate performances in various traffic are provided. Index Terms—Pattern Matching, Deep Packet Inspection I