Method and device for high performance regular expression pattern matching

• US 7,702,629 B2
• Filed: 12/02/2005
• Issued: 04/20/2010
• Est. Priority Date: 12/02/2005
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Exegy Incorporated
• Inventors: Taylor, David Edward, Cytron, Ron K., Brodie, Benjamin Curry
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Veillard; Jacques
• Application Number:
  US11/293,619
• Publication Number:
  US 20070130140A1
• Time in Patent Office: 1,600 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Disclosed herein is an improved architecture for regular expression pattern matching. Improvements to pattern matching deterministic finite automatons (DFAs) that are described by the inventors include a pipelining strategy that pushes state-dependent feedback to a final pipeline stage to thereby enhance parallelism and throughput, augmented state transitions that track whether a transition is indicative of a pattern match occurring thereby reducing the number of necessary states for the DFA, augmented state transition that track whether a transition is indicative of a restart to the matching process, compression of the DFA'"'"'s transition table, alphabet encoding for input symbols to equivalence class identifiers, the use of an indirection table to allow for optimized transition table memory, and enhanced scalability to facilitate the ability of the improved DFA to process multiple input symbols per cycle.

Claims

1. A device for matching an input string to a pattern via a deterministic finite automaton (DFA), the DFA comprising a plurality of states including a current state, the input string comprising a plurality of input symbols, the device comprising:

a pattern matching circuit that implements the DFA, the pattern matching circuit being configured to receive and serially process the input symbols of the input string in groups of m input symbols, wherein m is an integer that is greater than or equal to 1, the pattern matching circuit comprising;

(1) a transition table memory comprising a plurality of stored transitions, each stored transition being indexed by data corresponding to at least one input symbol, each transition comprising a next state identifier, (2) transition retrieval logic configured to retrieve from the transition table memory each transition that is indexed by data corresponding to the at least one input symbol of the received input symbol group without consideration of the current state, and (3) state selection logic configured to receive each retrieved transition, determine which of the retrieved transitions corresponds to the current state, determine a next state for the DFA based on the next state identifier of the determined transition, and determine whether a match exists between the input string and the pattern.

2. The device of claim 1 wherein each input symbol of the input string is one of a plurality of input symbols that are members of an alphabet, wherein the pattern matching circuit further comprises alphabet encoding logic configured to translate each received input symbol group to an equivalence class identifier (ECI), and wherein the data corresponding to an input symbol group by which each transition is indexed in the transition table memory comprises data corresponding to the ECI for that input symbol group.

3. The device of claim 2 further comprising a regular expression compiler in communication with the pattern matching circuit, the regular expression compiler being configured to receive and process a regular expression from a user to determine the DFA to be implemented by the pattern matching circuit, populate the transition table memory based on the processed regular expression, and define the ECIs based on the processed regular expression, the regular expression identifying the pattern against which the input string is matched.

4. The device of claim 3 wherein the transition table memory comprises a plurality of words that are indexed by memory addresses, each word comprising a plurality of transitions that are run length coded.

5. The device of claim 4 wherein the pattern matching circuit further comprises an indirection table memory and indirection table logic, wherein the indirection table memory comprises a plurality of entries, each entry being indexed by an ECI, each entry comprising a pointer to the memory address where a word is stored in the transition table memory that contains at least one transition that is indexed by that ECI, and wherein the indirection table logic is configured to retrieve the pointer from the indirection table memory that is indexed by the received input symbol group and provide the retrieved pointer to the transition retrieval logic, and wherein the data corresponding to the ECI for that input symbol group by which each transition is indexed comprises the memory address identified by the retrieved pointer.

6. The device of claim 5 wherein each indirection table memory entry further comprises a transition index and a transition count, the transition index identifying where a first transition indexed by the ECI for the input symbol group is located in the word identified by the pointer for that entry, and the transition count identifying how many transitions are indexed by the ECI for the input symbol group, and wherein the indirection table logic is configured to retrieve the transition index and the transition count from the indirection table memory entry that is indexed by the received input symbol group and provide the retrieved transition index and the transition count to the transition retrieval logic.

7. The device of claim 6 wherein the transition retrieval logic is configured to retrieve from the transition table memory each word identified by the retrieved pointer and the retrieved transition count, and wherein the state selection logic is further configured to mask out any portions of each retrieved word that correspond to transitions that are not indexed by the ECI for the input symbol group.

8. The device of claim 5 wherein each indirection table memory entry further comprises an initial transition index, a terminal transition index, and a word count, the initial transition index identifying where a first transition indexed by the ECI for the input symbol group is located in the word identified by the pointer for that entry, the word count identifying how many words in which all transitions that are indexed by the ECI for the received input symbol group are sequentially stored, and the terminal transition index identifying where a last transition indexed by the ECI for the input symbol group is located in the final word identified by the word count for that entry, and wherein the indirection table logic is configured to retrieve the initial transition index, the terminal transition index, and the word count from the indirection table memory entry that is indexed by the received input symbol group and provide the retrieved initial transition index, terminal transition index, and word count to the transition retrieval logic.

9. The device of claim 8 wherein the transition retrieval logic is configured to retrieve from the transition table memory each word identified by the retrieved pointer and the retrieved word count, and wherein the state selection logic is further configured to mask out any portions of each retrieved word that correspond to transitions that are not indexed by the ECI for the input symbol group.

10. The device of claim 5 wherein each transition further comprises a precomputed run-length prefix sum.

11. The device of claim 5 wherein m is greater than one.

12. The device of claim 5 further comprising a regular expression compiler in communication with the pattern matching circuit, the regular expression compiler being configured to receive and process a regular expression from a user to determine the DFA to be implemented by the pattern matching circuit, populate the transition table memory based on the processed regular expression, define the ECIs based on the processed regular expression, and populate the indirection table memory based on the processed regular expression, the regular expression identifying the pattern against which the input string is matched.

13. The device of claim 5 wherein the pattern matching circuit is implemented on an FPGA.

14. The device of claim 5 wherein the pattern matching circuit is implemented on an ASIC.

15. The device of claim 3 wherein each transition further comprises a match flag, and wherein the state selection logic is further configured to determine whether a match exists between the input string and the pattern based on the match flag of the determined transition.

16. The device of claim 15 wherein the DFA comprises a position-independent DFA.

17. The device of claim 16 wherein each transition further comprises a match restart flag, and wherein the state selection logic is further configured to determine whether the pattern matching process has been restarted in the DFA based on the match restart flag of the determined transition.

18. The device of claim 17 wherein m is greater than one.

19. The device of claim 1 further comprising a regular expression compiler in communication with the pattern matching circuit, the regular expression compiler being configured to receive and process a regular expression from a user to determine the DFA to be implemented by the pattern matching circuit, and populate the transition table memory based on the processed regular expression, the regular expression identifying the pattern against which the input string is matched.

20. The device of claim 19 wherein the pattern matching circuit is implemented on an FPGA.

21. The device of claim 19 wherein the pattern matching circuit is implemented on an ASIC.

22. The device of claim 1 wherein the pattern matching circuit is implemented on an FPGA.

23. The device of claim 1 wherein the pattern matching circuit is implemented on an ASIC.

24. The device of claim 1 wherein the pattern matching circuit is implemented on a multi-processor system.

25. A device for matching an input string to a pattern via a deterministic finite automaton (DFA), the DFA comprising a plurality of states including a current state, the input string comprising a plurality input symbols, the device comprising:

a memory that stores a transition table in a plurality of addressable memory words, each memory word storing at least one transition, each transition corresponding to at least one input symbol, each transition comprising a next state identifier and a match flag, the match flag being indicative of whether the transition indicates that a match has occurred between the input string and the pattern;

an input for receiving a group of m input symbols, wherein m is an integer that is greater than or equal to 1; and

a logic circuit in communication with the input and the memory, wherein the logic circuit is configured to (1) resolve each received input symbol group to at least one memory word that stores at least one transition corresponding to the received input symbol group, (2) retrieve from memory the at least one memory word to which the received input symbol group was resolved, (3) determine a next state for the DFA based on the at least one retrieved memory word, and (4) determine whether the received input symbol group caused a match to the pattern based on a match flag within the at least one retrieved memory word.

26. The device of claim 25 wherein each transition further comprises a match restart flag that is indicative of whether the transition indicates that the pattern matching process is to restart with the next state of the DFA, and wherein the logic circuit is further configured to track a match restart flag within the at least one retrieved memory word to identify a possible starting position of an input string that matches the pattern.

27. The device of claim 26 wherein m is greater than one.

28. The device of claim 27 wherein the logic circuit is further configured to encode each received input symbol group to an equivalence class identifier (ECI).

29. The device of claim 28 wherein the logic circuit is further configured to resolve each received input symbol group to at least one memory word that stores at least one transition corresponding to the received input symbol group without consideration of the DFA'"'"'s current state.

30. The device of claim 29 wherein the stored transitions comprise run-length encoded transitions.

31. The device of claim 30 wherein the run-length encoded transitions comprise run-length encoded transitions having precomputed run-length prefix sums.

32. The device of claim 30 wherein the memory is optimized such that the number of transitions that correspond to a common input symbol group and span multiple memory words is minimized.

33. The device of claim 32 further comprising a memory for storing an indirection table, and wherein the logic circuit is configured to access the indirection table memory to resolve each ECI to at least one memory word in the transition table memory corresponding to that ECI.

34. The device of claim 33 wherein the logic circuit comprises a plurality of pipeline stages implemented on an FPGA.

35. The device of claim 25 wherein the logic circuit comprises a pipelined hardware architecture.

36. The device of claim 35 wherein the pipelined hardware architecture comprises hardware logic.

37. The device of claim 36 wherein the hardware logic comprises at least one reconfigurable hardware device.

38. The device of claim 37 wherein the at least one reconfigurable hardware device comprises an FPGA.

39. The device of claim 36 wherein the hardware logic comprises at least one nonreconfigurable hardware device.

40. The device of claim 39 wherein the at least one nonreconfigurable hardware device comprises an ASIC.

41. The device of claim 35 wherein the pipelined hardware architecture comprises a multi-processor system.

42. A method of matching an input string to a pattern using a state machine, the input string comprising a plurality of input symbols, each input symbol comprising a plurality of bits, the method comprising:

defining a plurality of states for the state machine, the state machine having a current state and being configured to progress through the plurality of states as input symbols of the input string are received and processed to thereby detect whether a plurality of the input symbols of the input string match a pattern;

defining a plurality of transitions between the states of the state machine, each transition being indexed by data corresponding to a current state of the state machine and by data corresponding to at least one input symbol, each transition comprising an identifier for a next state of the state machine and a match flag to indicate whether a match exists between a plurality of the input symbols and the pattern;

receiving at least one input symbol of the input string;

retrieving at least one defined transition based on the at least one received input symbol;

determining which of the at least one retrieved transition is indexed by the current state;

updating the current state of the state machine as the state identified by the next state identifier of the determined retrieved transition;

determining whether a match exists between a plurality of the input symbols and the pattern based on the match flag of the retrieved transition; and

repeating the retrieving, transition determining, updating and match determining steps as additional input symbols of the input string are received; and

wherein the receiving, retrieving, transition determining, updating, match determining steps, and repeating steps are performed by a circuit.

43. The method of claim 42 wherein each transition further comprises a match restart flag to indicate whether the received at least one input symbol results in a restart of a matching process to the pattern, the method further comprising:

determining whether a match restart exists based on the match restart flag of the retrieved transition; and

wherein the repeating step comprises repeating the retrieving, transition determining, updating, match determining, and partial match start determining steps as additional input symbols of the input string are received.

44. The method of claim 43 wherein the receiving step comprises receiving a plurality m of input symbols each clock cycle, and wherein the retrieving step comprises retrieving at least one defined transition based on the m received input symbols.

45. The method of claim 44 further comprising:

defining a plurality of equivalence class identifiers for an alphabet of input symbols that may be processed through the state machine such that each input symbol maps to an equivalence class identifier, wherein the data corresponding to the at least one input symbol by which each transition is indexed comprises the equivalence class identifier for that at least one input symbol, and

mapping the received at least one input symbol to its equivalence class identifier,

wherein the retrieving step comprises retrieving at least one defined transition based on the equivalence class identifier for the at least one received input symbol; and

wherein the repeating step comprises repeating the mapping, retrieving, transition determining, updating, match determining, and partial match start determining steps as additional input symbols of the input string are received.

46. The method of claim 42 further comprising:

defining a plurality of equivalence class identifiers for an alphabet of input symbols that may be processed through the state machine such that each input symbol maps to an equivalence class identifier, wherein the data corresponding to the at least one input symbol by which each transition is indexed comprises data corresponding to the equivalence class identifier for that at least one input symbol; and

mapping the received at least one input symbol to its equivalence class identifier;

wherein the retrieving step comprises retrieving at least one defined transition based on the equivalence class identifier for the at least one received input symbol; and

wherein the repeating step comprises repeating the mapping, retrieving, transition determining, updating, match determining, and partial match start determining steps as additional input symbols of the input string are received.

47. The method of claim 46 further comprising compressing the transitions in a memory via run length coding.

48. The method of claim 47 wherein the compressing step further comprises compressing the transitions in a memory via run length coding having precomputed prefix sums.

49. The method of claim 46 wherein the memory comprises a plurality words, each word being indexed by a memory address, each word comprising a plurality x of compressed transitions, the method further comprising:

defining an indirection table for accessing the compressed transitions based on the equivalence class identifier for the at least one received input symbol, the indirection table comprising a plurality of entries, each entry being indexed by an equivalence class identifier, each entry comprising a pointer to a memory address where a word is stored that contains at least one compressed transition that is indexed by the equivalence class identifier for the at least one received input symbol,

wherein the data corresponding to the equivalence class identifier by which each transition is indexed comprises the indirection table pointer for that equivalence class identifier;

the method further comprising;

accessing the indirection table based on the equivalence class identifier for the at least one received input symbol to determine the pointer indexed thereby;

wherein the retrieving step further comprises retrieving at least one defined transition based on the determined pointer for the equivalence class identifier of the at least one received input symbol; and

wherein the repeating step further comprises repeating the mapping, accessing, retrieving, transition determining, updating, match determining, and partial match start determining steps as additional input symbols of the input string are received.

50. The method of claim 49 wherein each indirection table entry further comprises a transition index and a transition count, the transition index identifying where a first compressed transition for the equivalence class identifier of the at least one received symbol is located in the word identified by the pointer, the transition count identifying how many compressed transitions for the equivalence class identifier of the at least one received symbol are sequentially stored in the memory, wherein the accessing step comprises accessing the indirection table based on the equivalence class identifier for the at least one received input symbol to determine the pointer, transition index, and transition count indexed thereby, and wherein the retrieving step further comprises retrieving each defined transition based on the determined pointer, transition index, and transition count for the equivalence class identifier of the at least one received input symbol.

51. The method of claim 49 wherein each indirection table entry further comprises an initial transition index, a terminal transition index, and a word count, the initial transition index identifying where a first compressed transition for the equivalence class identifier of the at least one received symbol is located in the word identified by the pointer, the word count indicating how many words in which the at least one compressed transition for the equivalence class identifier of the at least one received symbol are sequentially stored in the memory, the terminal transition index identifying where the last compressed transition is located in the last word identified by the word count, and wherein the accessing step comprises accessing the indirection table based on the equivalence class identifier for the at least one received input symbol to determine the pointer, initial transition index, terminal transition index, and word count indexed thereby.

52. The method of claim 51 wherein the retrieving step further comprises retrieving from memory each word identified by the determined pointer and the determined word count, and wherein the transition determining step comprises masking out any compressed transitions that are located in each retrieved word that are not within a range identified by the determined initial transition index, the determined terminal transition index, and the determined word count.

53. The method of claim 52 wherein the state defining step comprises defining a plurality of states for the state machine from a set of regular expressions.

54. The method of claim 42 wherein the circuit comprises a pipelined hardware architecture.

55. The method of claim 54 wherein the pipelined hardware architecture comprises hardware logic.

56. The method of claim 55 wherein the hardware logic comprises at least one reconfigurable hardware device.

57. The method of claim 56 wherein the at least one reconfigurable hardware device comprises an FPGA.

58. The method of claim 55 wherein the hardware logic comprises at least one nonreconfigurable hardware device.

59. The method of claim 58 wherein the at least one nonreconfigurable hardware device comprises an ASIC.

60. The method of claim 54 wherein the pipelined hardware architecture comprises a multi-processor system.