Improving Deep Packet Inspection Through Extended Automata

Опубликовано 6 сентября 2016, 17:58

Deep packet inspection is playing an increasingly important role in novel network services. Regular expressions are the language of choice for writing signatures used in deep packet inspection, but standard signature matching solutions are not suitable for high-speed environments. Deterministic finite automata (DFAs) are fast but combining the DFAs for multiple signatures often leads to state space explosion. Non-deterministic finite automata (NFAs) are small but matching can be slow for large signature sets. This talk presents a new solution that simultaneously addresses these problems. Extended finite automata (XFAs) augment deterministic finite automata (DFAs) with finite auxiliary variables and simple instructions that manipulate them. The introduction of auxiliary variables allows us to eliminate state space explosion. In experiments with signature sets used for intrusion prevention by Snort and Cisco Systems, XFAs simultaneously reduce memory and run time by more than an order of magnitude when compared to earlier solutions.