Regex compiler
First Claim
Patent Images
1. A method comprising:
- in a processor of a security appliance coupled to a network, by the processor;
monitoring data received by the security appliance from the network;
converting a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph having a number of DFA states, the processor employing the DFA graph in order to apply the given set of patterns to the data for the monitoring, wherein the converting includes;
mapping a DFA state of the number of DFA states to a corresponding set of one or more NFA states of the NFA graph;
computing a first hash value of the one or more NFA states of the corresponding set;
storing the first hash value in an entry of a DFA states table correlating the DFA state to the first hash value; and
determining a transition DFA state from the DFA state for a character of an alphabet recognized by the NFA graph, based on whether a second hash value of transitions of the one or more NFA states for the character exists in an Epsilon Closure (EC) cache table, the EC cache table including hash value entries mapped to DFA states, and wherein, in an event the second hash value exists, setting the transition DFA state to be a given DFA state, the given DFA state mapped to the second hash value in the EC cache table.
6 Assignments
0 Petitions
Accused Products
Abstract
A method and corresponding apparatus relate to converting a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph having a number of states. Each of the DFA states is mapped to one or more states of the NFA graph. A hash value of the one or more states of the NFA graph mapped to each DFA state is computed. A DFA states table correlates each of the number of DFA states to the hash value of the one or more states of the NFA graph for the given pattern.
-
Citations
58 Claims
-
1. A method comprising:
in a processor of a security appliance coupled to a network, by the processor; monitoring data received by the security appliance from the network; converting a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph having a number of DFA states, the processor employing the DFA graph in order to apply the given set of patterns to the data for the monitoring, wherein the converting includes; mapping a DFA state of the number of DFA states to a corresponding set of one or more NFA states of the NFA graph; computing a first hash value of the one or more NFA states of the corresponding set; storing the first hash value in an entry of a DFA states table correlating the DFA state to the first hash value; and determining a transition DFA state from the DFA state for a character of an alphabet recognized by the NFA graph, based on whether a second hash value of transitions of the one or more NFA states for the character exists in an Epsilon Closure (EC) cache table, the EC cache table including hash value entries mapped to DFA states, and wherein, in an event the second hash value exists, setting the transition DFA state to be a given DFA state, the given DFA state mapped to the second hash value in the EC cache table. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
21. A method comprising:
-
in a processor of a security appliance coupled to a network, by the processor; monitoring data received by the security appliance from the network, converting a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph, the processor employing the DFA graph in order to apply the given set of patterns to the data for the monitoring, wherein the converting includes; receiving a set of NFA states, the set of NFA states being transition states for a character of an alphabet recognized by the NFA graph; and hashing the set of NFA states received to produce a first hash value and comparing the first hash value with hash value entries in an Epsilon Closure (EC) cache table to determine whether the first hash value is present in the EC cache table, the EC cache table mapping epsilon closures of sets of NFA states with corresponding hash values of the sets of NFA states and, in an event the first hash value is present, hashing a stored set of NFA states, the stored set of NFA states mapped to the first hash value in the EC cache table, to produce a second hash value and, in an event the second hash value is present in a DFA states table, setting a transition DFA state from a DFA state for the character to be a given DFA state, the given DFA state associated with the second hash value in the DFA states table. - View Dependent Claims (22, 23, 24, 25)
-
-
26. A method comprising:
-
in a processor of a security appliance coupled to a network, by the processor; monitoring data received by the security appliance from the network, converting a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph, the processor employing the DFA graph in order to apply the given set of patterns to the data for the monitoring, wherein the converting includes; receiving a set of NFA states, the set of NFA states being transition states for a character of an alphabet recognized by the NFA graph; and hashing the set of NFA states received to produce a hash value and comparing the hash value with hash value entries in an Epsilon Closure (EC) cache table to determine whether the hash value is present in the EC cache table, the EC cache table mapping hash values of epsilon closures associated with sets of NFA states to corresponding DFA states and, in an event the hash value is present, setting a transition DFA state from a DFA state for the character to be a given DFA state, the given DFA state mapped to the hash value in the EC cache table. - View Dependent Claims (27, 28, 29)
-
-
30. A security appliance coupled to a network, the security appliance comprising:
a processor coupled to a data store, the processor configured to monitor data received by the security appliance from the network and to convert a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph having a number of DFA states, wherein the processor employs the DFA graph in order to apply the given set of patterns to the data to monitor the data and wherein to convert the NFA graph to the DFA graph the processor is further configured to; map a DFA state of the number of DFA states to a corresponding set of one or more NFA states of the NFA graph; compute a first hash value of the one or more NFA states of the corresponding set; store the first hash value in an entry of a DFA states table in the data store, the DFA states table correlating the DFA state to the first hash value; and determine a transition DFA state from the DFA state for a character of an alphabet recognized by the NFA graph, based on whether a second hash value of transitions of the one or more NFA states for the character exists in an Epsilon Closure (EC) cache table, the EC cache table including hash value entries mapped to DFA states, and wherein, in an event the second hash value exists, setting the transition DFA state to be a given DFA state, the given DFA state mapped to the second hash value in the EC cache table. - View Dependent Claims (31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
-
49. A security appliance coupled to a network, the security appliance comprising:
a processor, the processor configured to; monitor data received by the security appliance from the network, convert a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph, employ the DFA graph in order to apply the given set of patterns to the data to monitor the data, wherein to convert the NFA graph to the DFA graph, the processor is further configured to; receive a set of NFA states, the set of NFA states being transition states for a character of an alphabet recognized by the NFA graph; and hash the set of NFA states received to produce a first hash value and compare the first hash value with hash value entries in an Epsilon Closure (EC) cache table to determine whether the first hash value is present in the EC cache table, the EC cache table mapping epsilon closures of sets of NFA states with corresponding hash values of the sets of NFA states and, in an event the first hash value is present, hash a stored set of NFA states, the stored set of NFA states mapped to the first hash value in the EC cache table, to produce a second hash value and, in an event the second hash value is present in a DFA states table, set a transition DFA state from a DFA state for the character to be a given DFA state, the given DFA state associated with the second hash value in the DFA states table. - View Dependent Claims (50, 51, 52, 53)
-
54. A security appliance coupled to a network, the security appliance comprising:
a processor, the processor configured to; monitor data received by the security appliance from the network, convert a nondeterministic finite automata (NFA) graph for a given set of patterns to a deterministic finite automata (DFA) graph, employ the DFA graph in order to apply the given set of patterns to the data to monitor the data, wherein to convert the NFA graph to the DFA graph, the processor is further configured to; receive a set of NFA states, the set of NFA states being transition states for a character of an alphabet recognized by the NFA graph; and hash the set of NFA states received to produce a hash value and compare the hash value with hash value entries in an Epsilon Closure (EC) cache table to determine whether the hash value is present in the EC cache table, the EC cache table mapping hash values of epsilon closures associated with sets of NFA states to corresponding DFA states and, in an event the hash value is present, set a transition DFA state from a DFA state for the character to be a given DFA state, the given DFA state mapped to the hash value in the EC cache table. - View Dependent Claims (55, 56, 57, 58)
Specification