Regex compiler

• US 9,858,051 B2
• Filed: 06/24/2011
• Issued: 01/02/2018
• Est. Priority Date: 06/24/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi, Bullis, Ken
• Primary Examiner(s): Desrosiers, Evans
• Application Number:
  US13/168,450
• Publication Number:
  US 20120331554A1
• Time in Patent Office: 2,384 Days
• Field of Search: 726 23
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 9/4498 Finite state machines
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

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.

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.

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 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.

22. The method of claim 21 further comprising:

if the first hash value is present in the EC cache table, setting the stored set of NFA states mapped to the first hash value in the EC cache table as an epsilon closure of the set of NFA states received.

23. The method of claim 22 further comprising:

if the first hash value is not present in the EC cache table, computing an epsilon closure of the set of NFA states received; and

adding a new entry into the EC cache table, the new entry mapping the first hash value of the set of NFA states received to the epsilon closure computed.

24. The method of claim 23, wherein adding an entry includes:

determining whether there is sufficient memory to add the new entry; and

if there is not sufficient memory, adding the new entry according to a replacement policy.

25. The method of claim 24 wherein the replacement policy adds the new entry by deleting a least recently used entry of the EC cache table.

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.

27. The method of claim 26, wherein the hash value is a first hash value and wherein the method further comprises:

if the first hash value is not present, computing the epsilon closure of the set of NFA states received;

hashing the epsilon closure computed to produce a second hash value;

adding a new entry into the EC cache table, the new entry mapping the second hash value to a new DFA state, the new DFA state mapped to the first hash value in a DFA states table; and

setting the new DFA state as the transition DFA state from the DFA state for the character of the alphabet recognized by the NFA graph.

28. The method of claim 27, wherein adding an entry includes:

determining whether there is sufficient memory to add the new entry; and

if there is not sufficient memory, adding the new entry according to a replacement policy.

29. The method of claim 28 wherein the replacement policy adds the new entry by deleting a least recently used entry of the EC cache table.

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.

31. The security appliance of claim 30 wherein the first and second hash values are cryptographic/perfect hash values.

32. The security appliance of claim 30 wherein the processor is further configured to:

determine whether there are unmarked DFA states within the number of DFA states;

select one of the unmarked DFA states to produce an unmarked DFA state;

mark the unmarked DFA state to produce a marked DFA state; and

determine 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.

33. The security appliance of claim 32 wherein the processor is configured to determine the transitions by mapping the other NFA states and an epsilon closure of the other NFA states to a possible new unmarked DFA state.

34. The security appliance of claim 33 wherein the processor is configured to map the possible new unmarked DFA state to the epsilon closure of the other NFA states by 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, the processor is further configured to compute the epsilon closure of the other NFA states.

35. The security appliance of claim 34 wherein the processor is further configured to add 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 store the possible new unmarked DFA state in the DFA states table.

36. The security appliance of claim 35 wherein the processor is configured to add the possible new unmarked DFA state by 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.

37. The security appliance of claim 35 the complier is configured to add the possible new unmarked DFA state to the number of DFA states by 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, the processor is further configured to add the possible unmarked state as a final accepting DFA state.

38. The security appliance of claim 35 wherein the processor is further configured to add the possible new unmarked state as a transition from the marked DFA state for the character of the alphabet recognized by the NFA graph.

39. The security appliance of claim 33 wherein the processor is further configured to replace 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.

40. The security appliance of claim 39 wherein the processor is configured to delete the other NFA states and the epsilon closure of the other NFA states.

41. The security appliance of claim 32 wherein the processor is further configured to delete the transitions of the one or more NFA states of the NFA graph from the DFA states table.

42. The security appliance of claim 30 wherein the processor is configured to map each of the number of DFA states to the one or more NFA states of the NFA graph by 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.

43. The security appliance of claim 42 wherein the processor is further configured to:

determine an epsilon closure of an NFA start state;

compute a third hash value of the epsilon closure of the NFA start state; and

map the DFA start state to the third hash value of the epsilon closure of the NFA start state.

44. The security appliance of claim 42 wherein the processor is further configured to:

determine whether there are unmarked DFA states within the number of DFA states;

select one of the unmarked DFA states to produce an unmarked DFA state;

mark the unmarked DFA state to produce a DFA marked state; and

determine 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.

45. The security appliance of claim 44 wherein the processor is configured to determine the transitions by determining the transition DFA state from the marked DFA state for the character of the alphabet recognized by the NFA graph.

46. The security appliance of claim 45 wherein the processor is further configured to:

a compute the second hash value for the transitions of the one or more NFA states of the NFA graph; and

compare the second hash value computed to the hash value entries in the EC cache table.

47. The security appliance of claim 30 wherein the processor is further configured to:

in an event the second hash value does not exist in the EC cache table, compute an epsilon closure for the transitions of the one or more NFA states of the NFA graph;

compute a third hash value of the epsilon closure;

add 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

set the new DFA state as the transition DFA state for the character of the alphabet recognized by the NFA graph.

48. The security appliance of claim 47 wherein the processor is further configured to:

delete the transitions of the one or more NFA states of the NFA graph corresponding to the marked DFA state from the DFA states table.

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.

50. The security appliance of claim 49 wherein the processor is further configured to:

if the first hash value is present in the EC cache table, set the stored set of NFA states mapped to the first hash value in the EC cache table as an epsilon closure of the set of NFA states received.

51. The security appliance of claim 50 wherein the processor is further configured to:

if the first hash value is not present in the EC cache table, compute an epsilon closure of the set of NFA states received; and

add a new entry into the EC cache table, the new entry mapping the first hash value of the set of NFA states received to the epsilon closure computed of the set of NFA states received.

52. The security appliance of claim 51, wherein the processor is further configured to:

determine whether there is sufficient memory to add the new entry; and

if there is not sufficient memory, add the new entry according to a replacement policy.

53. The security appliance of claim 52 wherein the replacement policy adds the new entry by deleting a least recently used entry of the EC cache table.

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.

55. The security appliance of claim 54, wherein the hash value is a first hash value and wherein the processor is further configured to:

if the first hash value is not present, compute the epsilon closure of the set of NFA states received;

hash the epsilon closure computed to produce a second hash value;

add a new entry into the EC cache table, the new entry mapping the second hash value to a new DFA state, the new DFA state mapped to the first hash value in a DFA states table; and

set the new DFA state as the transition DFA state from the DFA state the character of the alphabet recognized by the NFA graph.

56. The security appliance of claim 55, wherein the processor is further configured to:

determine whether there is sufficient memory to add the new entry; and

if there is not sufficient memory, add the new entry according to a replacement policy.

57. The security appliance of claim 56 wherein the replacement policy adds the new entry by deleting a least recently used entry of the EC cache table.

58. The security appliance of claim 54 wherein the processor is further configured to:

determine active characters of a given pattern associated with the alphabet recognized by the NFA graph and the DFA graph; and

create 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.