Back to results
US 2015/0310342 A1Published application
Overlay automata approach to regular expression matching for intrusion detection and prevention system
AssigneeBoard of Trustees of Michigan State University
InventorsAlex Liu, Eric Torng
Life of this patent
Estimating the term…
Abstract
Embodiments are described for automata models for use in deep packet inspection. Various embodiments are described for a new automata model, Overlay DFA (ODFA), which captures state replication in DFAs. Additional embodiments include combining the ODFA model with a D2FA model to provide an Overlay Delayed Input DFA (OD2FA). As the DFA model captures transition sharing, the OD2FA model captures both state replication and transition sharing. Algorithms are disclosed for efficiently constructing the OD2FA model and for implementing the OD2FA model in Ternary Content Addressable Memory (TCAM).
Claims20
(ODFA algorithm) A computer-implemented method for implementing regular expression matching, comprising:
- receiving, by one or more processors, (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern;
- identifying, by one or more processors, a plurality of deterministic finite automata (DFA) state groups, each of the plurality of DFA state groups having a common nondeterministic finite automata (NFA) state and including DFA source states and DFA destination states;
- grouping, by one or more processors, each of the plurality of DFA state groups into overlay DFA (ODFA) super states such that replicated transitions between DFA source states grouped within the same source ODFA super state and the same DFA destination state are aggregated as a single transition between the source ODFA super state and the DFA destination state;
- constructing, by one or more processors, an ODFA model by replacing the plurality of DFA state groups with the plurality of OFDA super states based upon the received plurality of regular expressions;
- executing, by one or more processors, the plurality of regular expressions in accordance with the model of the ODFA model to identify search pattern matches within the plurality of data packets;
- and
- performing, by one or more processors, deep packet inspection on the plurality of data packets based upon identified search pattern matches.
4 more elements
A non-transitory, tangible computer-readable medium storing machine readable instructions that, when executed by a processor, cause the processor to:
- receive (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern;
- identify a plurality of deterministic finite automata (DFA) state groups, each of the plurality of DFA state groups having a common nondeterministic finite automata (NFA) state and including DFA source states and DFA destination states;
- group each of the plurality of DFA state groups into overlay DFA (ODFA) super states such that replicated transitions between DFA source states grouped within the same source ODFA super state and the same DFA destination state are aggregated as a single transition between the source ODFA super state and the DFA destination state;
- construct an ODFA model by replacing the plurality of DFA state groups with the plurality of OFDA super states based upon the received plurality of regular expressions;
- execute the plurality of regular expressions in accordance with the model of the ODFA model to identify search pattern matches within the plurality of data packets;
- and
- perform deep packet inspection on the plurality of data packets based upon identified search pattern matches.
4 more elements
(OD2FA model) A computer-implemented method for implementing regular expression matching, comprising:
- receiving, by one or more processors, (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern;
- identifying, by one or more processors, a plurality of default transitions between deterministic finite automata (DFA) states in a DFA transition function based upon the plurality of received regular expressions, each of the default transitions representing a plurality of common transitions between DFA states and constituting a deferment transition, constructing, by one or more processors, a delayed DFA (D2FA) model by replacing the plurality of common transitions with their corresponding default transitions;
- identifying, by one or more processors, a plurality of D2FA state groups within the D2FA state model, each of the plurality of D2FA state groups having a common DFA state and including D2FA source states and D2FA destination states;
- grouping, by one or more processors, each of the plurality of D2FA state groups into overlay D2FA (OD2FA) super states such that (i) replicated transitions between D2FA source states grouped within the same source OD2FA super state and D2FA destination states grouped within the same destination OD2FA super state are aggregated as a single transition between the source OD2FA super state and the destination OD2FA super state, and (ii) deferment transition relationships between D2FA states are represented as transitions between one or more OD2FA super states;
- constructing, by one or more processors, an OD2FA model by replacing the plurality of D2FA state groups with the plurality of OD2FA super states based upon the received plurality of regular expressions;
- executing, by one or more processors, the plurality of regular expressions in accordance with the OD2FA model to identify search pattern matches within the plurality of data packets;
- and
- performing, by one or more processors, deep packet inspection on the plurality of data packets based upon identified search pattern matches.
5 more elements
A non-transitory, tangible computer-readable medium storing machine readable instructions that, when executed by a processor, cause the processor to:
- receive (i) a plurality of data packets, and (ii) a plurality of regular expressions that specify a search pattern;
- identify a plurality of default transitions between deterministic finite automata (DFA) states in a DFA transition function based upon the plurality of received regular expressions, each of the default transitions representing a plurality of common transitions between DFA states and constituting a deferment transition,
- construct a delayed DFA (D2FA) model by replacing the plurality of common transitions with their corresponding default transitions;
- identify a plurality of D2FA state groups within the D2FA state model, each of the plurality of D2FA state groups having a common DFA state and including D2FA source states and D2FA destination states;
- group each of the plurality of D2FA state groups into overlay D2FA (OD2FA) super states such that (i) replicated transitions between D2FA source states grouped within the same source OD2FA super state and D2FA destination states grouped within the same destination OD2FA super state are aggregated as a single transition between the source OD2FA super state and the destination OD2FA super state, and (ii) deferment transition relationships between D2FA states are represented as transitions between one or more OD2FA super states;
- construct an OD2FA model by replacing the plurality of D2FA state groups with the plurality of OD2FA super states based upon the received plurality of regular expressions;
- execute the plurality of regular expressions in accordance with the OD2FA model to identify search pattern matches within the plurality of data packets;
- and
- perform deep packet inspection on the plurality of data packets based upon identified search pattern matches.
6 more elements
Dependencies are inferred from the claim text.