Deflating the big bang

摘要: Deep packet inspection is playing an increasingly important role in the design of novel network services. Regular expressions are language choice for writing signatures, but standard DFA or NFA representations unsuitable high-speed environments, requiring too much memory, time, per-flow state. DFAs fast and can be readily combined, doing so often leads to state-space explosion. NFAs, while small, require large state slow.We propose a solution that simultaneously addresses all these problems. We start with first-principles characterization explosion give conditions eliminate it when satisfied. show how auxiliary variables used transform automata they satisfy conditions, which we codify formal model augments simple instructions manipulating them. Building on this model, present techniques, inspired by principles compiler optimization, systematically reduce runtime In our experiments, signature sets from Snort Cisco Systems achieve reductions over four orders magnitude, up factor six, runtimes approach DFAs.