Regex compiler

Patent metadata

Field	Value
Publication number	US-9858051-B2
Application number	US-201113168450-A
Country	US
Kind code	B2
Filing date	Jun 24, 2011
Priority date	Jun 24, 2011
Publication date	Jan 2, 2018
Grant date	Jan 2, 2018

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.

First claim

What is claimed is:

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.

2. The method of claim 1 wherein the first and second hash values are cryptographic/perfect hash values.

3. The method of claim 1 wherein mapping includes:
determining whether there are unmarked DFA states within the number of DFA states;
selecting one of the unmarked DFA states to produce an unmarked DFA state;
marking the unmarked DFA state to produce a marked DFA state; and
determining the transitions of the one or more NFA states of the NFA graph mapped to the marked DFA state to other NFA states for the character of the alphabet recognized by the NFA graph.

4. The method of claim 3 wherein determining the transitions includes mapping the other NFA states and an epsilon closure of the other NFA states to a possible new unmarked DFA state.

5. The method of claim 4 wherein mapping the possible new unmarked DFA state to the epsilon closure of the other NFA states includes obtaining the epsilon closure of the other NFA states from the EC cache table, and if the epsilon closure of the other NFA states does not exist within the EC cache table, computing the epsilon closure of the other NFA states.

6. The method of claim 5 further including adding the possible new unmarked DFA state to the number of DFA states if the other NFA states and the epsilon closure of the other NFA states mapped to the possible new unmarked DFA state are not mapped to an existing DFA state of the number of DFA states and storing the possible new unmarked DFA state in the DFA states table.

7. The method of claim 6 wherein adding the possible new unmarked DFA state includes:
comparing a third hash value of the epsilon closure of the other NFA states mapped to the possible new unmarked DFA state to a fourth hash value of NFA states mapped to each of the number of DFA states.

8. The method of claim 6 wherein adding the possible new unmarked DFA state to the number of DFA states further includes determining whether the epsilon closure of the other NFA states mapped to the possible new unmarked states belongs to a final accepting NFA state, and if so, adding the possible unmarked state as a final accepting DFA state.

9. The method of claim 6 further comprising adding the possible new unmarked state as a transition from the marked DFA state for the character of the alphabet recognized by the NFA graph.

10. The method of claim 4 further comprising replacing the mapping of the other NFA states and the epsilon closure of the other NFA states to the possible new unmarked DFA state with a different mapping of a computed hash value of the other NFA states and the epsilon closure of the other NFA states to the possible new unmarked DFA state.

11. The method of claim 10 wherein replacing includes deleting the other NFA states and the epsilon closure of the other NFA states.

12. The method of claim 3 further comprising deleting the transitions of the one or more NFA states of the NFA graph from the DFA states table.

13. The method of claim 1 wherein mapping includes:
determining a DFA start state; and
adding the DFA start state as an unmarked state to a data structure including the number of DFA states.

14. The method of claim 13 wherein determining the DFA start state includes:
determining an epsilon closure of an NFA start state;
computing a third hash value of the epsilon closure of the NFA start state; and
mapping the DFA start state to the third hash value of the epsilon closure of the NFA start state.

15. The method of claim 13 wherein mapping includes:
determining whether there are unmarked DFA states within the number of DFA states;
selecting one of the unmarked DFA states to produce an unmarked DFA state;
marking the unmarked DFA state to produce a marked DFA state; and
determining the transitions of the one or more NFA states of the NFA graph mapped to the marked DFA state to other NFA states for the character of the alphabet recognized by the NFA graph.

16. The method of claim 15 wherein determining the transitions includes determining the transition DFA state from the marked DFA state for the character of the alphabet recognized by the NFA graph.

17. The method of claim 16 wherein determining the transition DFA state includes:
computing the second hash value for the transitions of the one or more NFA states of the NFA graph; and
comparing the second hash value to the hash value entries in the EC cache table.

18. The method of claim 1 further comprising:
in an event the second hash value does not exist in the EC cache table, computing an epsilon closure for the transitions of the one or more NFA states of the NFA graph;
computing a third hash value of the epsilon closure;
adding a new entry into the EC cache table, the new entry mapping a new DFA state to the third hash value of the epsilon closure; and
setting the new DFA state as the transition DFA state for the character of the alphabet recognized by the NFA graph.

19. The method of claim 18 further comprising:
deleting the transitions of the one or more NFA states of the NFA graph corresponding to the marked DFA state from the DFA states table.

20. The method of claim 1 further comprising:
determining active characters of a given pattern associated with the alphabet recognized by the NFA graph and the DFA graph; and
creating the NFA graph and the DFA graph to recognize patterns consisting of only the active characters of the given pattern associated with the alphabet recognized by the NFA graph and the DFA graph.

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 v

Assignees

• Goyal Rajan
• Billa Satyanarayana Lakshmipathi
• Bullis Ken
• Cavium Inc

Inventors

• Goyal Rajan
• Billa Satyanarayana Lakshmipathi
• Bullis Ken

Classifications

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L63/0245

  Filtering by information in the payload · CPC title

• G06F8/41 Primary

  Compilation · CPC title

• H04L63/1416

  Event detection, e.g. attack signature detection · CPC title

• G06F9/444

  Physics · mapped topic