Spectral Clustering Based Regular Expression Grouping

Regular expression matching has been playing an import role in today’s network security systems with deep inspection function. However, compiling a set of regular expressions into one Deterministic Finite Automata (DFA) often leads to state explosion, which means huge or even impractical memory cost. Distributing regular expressions into several groups and building DFAs independently has been proved an efficient solution, but the previous grouping algorithms are either locally optimal or time-consuming. In this work, we proposed a new grouping method based on Spectral Clustering, which defines the similarity between regular expressions and then transforms grouping problem to clustering problem. Preliminary experiments illustrate that our grouping algorithm achieves efficient result with much less processing time