FREME: A pattern partition based engine for fast and scalable regular expression matching in practice

Regular expression matching has been widely used in modern content-aware network devices, where the content of interest (i.e., patterns) is often specified by regular expressions. Due to the ever-increasing number of patterns, implementing fast and scalable regular expression matching becomes a big challenge. Practical solutions rely mainly on a variety of deterministic finite automata (DFA) deflation techniques, but cannot guarantee both high speed and linear scalability simultaneously. To fully address the problem, in this paper, we present a fundamentally different design: (1) following principles to partition all regular expression patterns (in the given pattern set) into segments, so that state explosion never occurs when converting these segments to DFA, and (2) compiling the resulting segments and their syntagmatic relations, respectively, into DFA and relation mapping table (RMT), which together make up the final matching engine named FREME. Despite the pattern partition, FREME does not sacrifice any matching correctness with the aid of RMT. Evaluation based on real-world pattern sets (open source and commercial) shows that FREME scales linearly with the size of pattern set, meanwhile keeps fast matching based on nonexplosive DFA. In contrast, FREME outperforms state-of-the-art matching engines up to two orders of magnitude.