Deep packet inspection with DFA-trees and parametrized language overapproximation

IPSs determine whether incoming traffic matches a database of vulnerability signatures defined as regular ex- pressions. DFA representations are popular, but suffer from the state-explosion problem. We introduce a new matching structure: a tree of DFAs where the DFA associated with a node over- approximates those at its children, and the DFAs at the leaves represent the signature set. Matching works top-down, starting at the root of the tree and stopping at the first node whose DFA does not match. In the common case (benign traffic) matching does not reach the leaves. DFA-trees are built using Compact Overapproximate DFAs (CODFAs). A CODFA Dfor D over- approximates the language accepted by D, has a smaller number of states than D, and has a low false-match rate. Although built from approximate DFAs, DFA-trees perform exact matching faster than a commonly used method, have a low memory overhead and a guaranteed good worst case performance. I. INTRODUCTION Intrusion Prevention System (IPSs) scan network traffic for signs of suspicious activity. Many IPSs, such as Snort (20), rely on attack signatures, i.e. patterns strongly associated with malicious traffic. Deployed systems use hundreds or thousands of signatures, usually represented as regular expressions (REs) due to their flexibility. Matching each packet against each signature in such a large set is a significant challenge. A set of REs corresponding to signatures can be combined into into a single Nondeterministic Finite Automaton (NFA), but matching with NFAs is slow because a frontier of states has to be maintained. Deterministic Finite Automata (DFA) match quickly, but they suffer from the state-space explosion problem. When DFAs are combined, in the worst case the number of states can be the product of the number of states of the components, and the DFA that correspondsto all signatures becomes too large to fit in memory. Alternative compact representations for DFAs, such as XFAs (24), come at the cost of increased program complexity and processing time. A simple, practical approach (28) partitions a signature set such that signatures in each partition can be grouped into a single DFA of a bounded size. The processing time is proportional to the number of elements in the resulting DFA- set representation, which is significantly smaller than the size of the signature set, but it can still be large. In this paper we introduce the DFA-tree, a novel data structure for matching REs. We use DFAs organized in a tree structure. The leaves of the tree are the DFAs obtained by grouping a signature set. The DFA at each node acts as a filter for the DFAs in the subtree rooted at that node. Payload scanning is performed top down: start with the root of the tree and, if it doesn't match we stop, otherwise we check whether it is a real match by recursively matching with the children. If a DFA at any of the leaves matches, then it is a real match (the traffic matches a real exploit or a vulnerability). In the common case of benign traffic, the payload does not match, and it is usually rejected before reaching the leaves. A DFA-tree performs exact matching of a signature set, as if using a single DFA that combines all REs in the set. There are no false positives or negatives: if a DFA-tree rejects a payload, then it doesn't match any RE in the signature set, and if it accepts a payload, then at least one RE matches. The main challenge in building a DFA-tree is generating the intermediate filter nodes. To do so, we introduce the concept of Compact Overapproximate DFA (CODFA) as the building block for the DFA-tree construction. An overapproximation for a DFA, D, is another DFA Dwhich accepts a superset of D's language (L(D) ⊆ L(D ' )). A CODFA is an overap- proximation which is more compact in terms of the number of states, and which has a low approximation error rate. We believe that finding the best CODFA, i.e. with the fewest number of states that does not exceed a given error rate,