Toward Fast Regex Pattern Matching Using Simple Patterns

摘要

Nowadays network solutions employ pattern matching methods to apply protocol identification, traffic billing, load balancing, or detecting network malicious activities. Although regular expression (regex) patterns provide a powerful option to express signatures more effectively, they make the matching procedure more challenging. Dozens of finite automata based methods have been proposed to deal with regex patterns and boost the matching procedure. However, they suffer from high spatial or temporal complexity. Recently, we proposed HES as a practical novel method to match thousands of regex patterns in a reasonable time. Although HES was extremely faster than DFA, it was unable to support regex patterns without simple pattern (SP-Free regex patterns). In this paper we developed Enhanced HES (E-HES) to handle these kinds of patterns. Experimental results revealed that E-HES not only supported SP-Free regex patterns, but also it significantly optimized the regex handler check procedure. It leads us to match any kind of regex patterns in high bandwidth networks without spatial or temporal limitation.