Method and Device for High Performance Regular Expression Pattern Matching

• US 20100198850A1
• Filed: 02/10/2010
• Published: 08/05/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
• Granted Patent: US 7,945,528 B2
• Time in Patent Office: Days
• US Class Current: 707/758
• 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. In 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 and a plurality of possible next states, the input string comprising a plurality of input symbols, the improvement comprising:

the device comprising at least two parallel pipeline stages;

a first one of the pipeline stages being configured to retrieve a plurality of transitions to a possible next state of the DFA from a pre-populated memory; and

a second one of the pipeline stages that is configured to choose, based at least in part upon the DFA'"'"'s current state, one of said retrieved transitions from which the integrated circuit will determine the next state of the DFA, wherein the second one of the pipeline stages is downstream from the first one of the pipeline stages.

2. The device of claim 1 wherein the improvement further comprises the first one of the pipeline stages being configured to retrieve a plurality of transitions to a possible next state of the DFA from a pre-populated memory without consideration of the current state of the DFA.

3. The device of claim 2 wherein the improvement further comprises the second one of the pipeline stages being the final downstream pipeline stage of the device.

4. A method for matching an input string to a pattern in a device that realizes a deterministic finite automaton (DFA), the DFA comprising a plurality of states including a current state and a plurality of possible next states, the input string comprising a plurality of input symbols, the device comprising at least two parallel pipeline stages, the method comprising:

within one of the pipeline stages, retrieving from a memory a plurality of stored transitions to a next possible state of the DFA; and

within another of the pipeline stages that is downstream in the pipeline from the pipeline stage from which the plurality of transitions were retrieved, selecting one of the retrieved transitions to identify the next state of the DFA, wherein the selecting is based at least in part upon the current state of the DFA.

5. The method of claim 4 wherein the retrieving step is performed without consideration of the current state of the DFA.

6. A device comprising:

a multi-stage pattern matching pipeline configured to receive an input data stream comprising a plurality of input symbols and process the received data stream, wherein the pipeline realizes a pattern matching deterministic finite automaton (DFA) that is configured to determine whether any string of input symbols within the data stream matches a pattern, the DFA having a plurality of states including a current state, the pipeline comprising a plurality of stages including a final stage, each stage having at least one stage input and at least one stage output, the final stage being configured to provide as outputs a next state for the DFA, wherein the only stage of the pipeline that receives a feedback loop based on a stage output is the final stage.

7. The device of claim 6 wherein the final stage is configured to receive the next state in the feedback loop such that the next state is used as the current state when processing a next input symbol of the input data stream.

8. The device of claim 7 wherein the pipeline is further configured with a plurality of the multi-stage pattern matching pipelines for processing the input data stream in parallel.

9. The device of claim 7 wherein the pipeline comprises an FPGA.

10. The device of claim 7 wherein the pipeline comprises an ASIC.

11. The device of claim 7 wherein the pipeline comprises a processing system, the processing system comprising a plurality of different processors that are arranged in a pipeline, each processor being configured to implement at least one of the pipeline stages.

12. A device comprising:

a data processing pipeline configured to receive an input data stream comprising a plurality of input symbols and process the received data stream through a logic circuit to determine whether any input symbol string within the input data stream matches a pattern, the logic circuit being configured to realize a deterministic finite automaton (DFA), the DFA comprising a plurality of states, an alphabet of input symbols, an alphabet of equivalence class identifiers (ECIs), a set of functions that map groups of m input symbols to corresponding ECIs, and a set of functions that define transitions between states of the DFA, each state transition function being indexed by an ECI and comprising a next state identifier and a match flag, wherein m is an integer that is greater than or equal to one.

13. The device of claim 12 wherein the DFA further comprises a set of functions that map each ECI to at least one state transition function.

14. The device of claim 13 wherein each state transition function further comprises a match restart flag.

15. The device of claim 14 wherein the DFA further comprises a variable that tracks the starting input symbol of each potential pattern match.

16. The device of claim 15 wherein the DFA further comprises a variable that tracks the final input symbol of an actual pattern match.

17. A device for defining a deterministic finite automaton (DFA), the DFA comprising a plurality of states, the DFA being configured to detect whether a pattern exists within a stream of input symbols as it progresses through the plurality of states, the device comprising:

a processor configured to (1) receive data describing the pattern that is to be matched against the stream of input symbols, (2) process the received pattern data to determine the plurality of DFA states and determine a plurality of transitions defining how the DFA is to progress from a current state to a next state as each group of m input symbols is processed by the DFA, wherein m is an integer that is greater than or equal to one, wherein each transition corresponds to a group of m input symbols, wherein each transition comprises a next state identifier and a match flag, the match flag of each transition being indicative of whether the input symbol group corresponding to that transition caused a match to occur between the pattern and the stream of input symbols, and wherein the determined states and the determined transitions at least partially defining the DFA.

18. The device of claim 17 wherein the processor is further configured to run-length code the plurality of transitions.

19. The device of claim 18 wherein the processor is further configured to define an allocation of the run-length coded transitions into a memory, the memory comprising a plurality of addressable words, each word having capacity to store a plurality w of run-length coded transitions, wherein the processor allocates the run-length coded transitions to the memory such that each run-length coded transition corresponding to a common input symbol group is allocated to available capacity in one or more sequentially addressed memory words.

20. The device of claim 19 wherein the processor is further configured to perform an optimal memory word packing algorithm on the run-length coded transitions such that a total number of run-length coded transitions that correspond to a common input symbol group and that span multiple memory words is minimized.

21. The device of claim 20 wherein the input symbols of the stream comprise members of an alphabet of available input symbols, wherein the processor is further configured to (1) process the alphabet, the determined states and the determined transitions to determine a plurality of equivalence class identifiers (ECIs) for the alphabet, (2) define at least one table for mapping input symbol groups to their associated ECIs, and (3) define an indirection table having a plurality of entries, each indirection table entry corresponding to an ECI and identifying where each transition that corresponds to the input symbol group that is associated with that entry'"'"'s corresponding ECI is located in the memory.

22. The device of claim 21 wherein each indirection table entry comprises (1) a pointer to the word where a first transition corresponding to the input symbol group that is associated with that entry'"'"'s corresponding ECI is stored, (2) a transition index to where the first transition is located within that word, and (3) a transition count indicative of how many transitions in the memory correspond to the input symbol group that is associated with that entry'"'"'s corresponding ECI.

23. The device of claim 21 wherein each indirection table entry comprises (1) a pointer to the word where a first transition corresponding to the input symbol group that is associated with that entry'"'"'s corresponding ECI is stored, (2) an initial transition index to where the first transition is located within that word, (3) a terminal transition index to where a final transition corresponding to the input symbol group that is associated with that entry'"'"'s corresponding ECI is located within that word, and (4) a word count indicative of how many words store a transition that corresponds to the input symbol group that is associated with that entry'"'"'s corresponding ECI.

24. The device of claim 21 wherein the processor is in communication with a pattern matching circuit, the pattern matching circuit comprising a memory, and wherein the processor is further configured to (1) load pattern matching circuit memory with the defined transitions in accordance with the defined allocation, (2) load the pattern matching circuit memory with the defined mapping table, and (3) load the pattern matching circuit with the defined indirection table.

25. The device of claim 24 wherein the pattern matching circuit comprises a multi-stage pattern matching pipeline.

26. The device of claim 25 wherein the pipeline is implemented on reconfigurable hardware logic.

27. The device of claim 21 wherein the data describing the pattern comprises a user-specified regular expression.

28. The device of claim 21 wherein each transition further comprises a match restart flag that is indicative of whether the input symbol group corresponding to that transition caused a restart to occur with respect to matching the stream against the pattern.

29. The device of claim 21 wherein the processor is further configured to re-order the transitions prior to run-length coding the transitions to thereby minimize an amount of memory consumed by the run length coded transitions.

30. A method of compiling a set of transitions for a deterministic finite automaton (DFA), the DFA comprising a plurality of states, the DFA being configured to detect whether a pattern exists within a stream of input symbols as it progresses through the plurality of states, the method comprising:

receiving data describing the pattern from the user;

responsive to the received pattern data, defining a plurality of transitions, each transition corresponding a group of m input symbols, wherein m is an integer greater than or equal to 1, each transition comprising a next state identifier and a match flag, the match flag being indicative of whether the input symbol group corresponding thereto caused a match to occur between the stream and the pattern.

31. The method of claim 30 further comprising:

determining an allocation of the defined transitions into a memory, the memory comprising a plurality of addressable words, each word having a capacity for storing a plurality of transitions, wherein the allocation determining steps comprises assigning each transition to available capacity in the memory words such that a total number of transitions corresponding to a common input symbol group that span multiple memory words is minimized.

32. A method for creating a reduced state deterministic finite automaton (DFA) from a canonical DFA, each DFA being configured to match an input string to a pattern, the input string comprising a plurality of input symbols, each DFA comprising a plurality of states and a transition table, the transition table comprising a plurality of transitions that define how the DFA progresses from a current state to a next state in response to at least one new input symbol being received by the DFA, and wherein at least one of the states of the canonical DFA is an accept state, the method comprising:

eliminating each accept state from the canonical DFA to thereby create the reduced state DFA; and

augmenting the transition table such that each transition includes a flag indicative of whether the at least one new input symbol received by the reduced state DFA has caused a match to occur between the input string and the pattern.

33. The method of claim 32 wherein the transition table augmenting step further comprises augmenting the transition table such that each transition further includes a flag indicative of whether the at least one new input symbol received by the reduced state DFA has caused the pattern matching to restart.

34. The method of claim 33 further comprising:

processing a plurality m of new input symbols through the reduced state DFA each clock cycle.

35. A computer readable storage medium for determining how a plurality of state transitions are to be ordered in a transition table for a deterministic finite automaton (DFA) having a plurality of states, each transition being indexed by a DFA state, the computer readable storage medium comprising:

a code segment executable by a processor for reading the transition table to determine the plurality of transitions therein; and

a code segment executable by a processor that is configured to perform a state re-ordering algorithm on the determined transitions to optimize the order of the states in the transition table;

wherein the code segments are resident on the computer readable storage medium.

36. A computer readable storage medium for determining how a plurality of run-length coded state transitions are to be stored in a transition table memory, the transition table memory comprising a plurality of words, each word having a width sufficient to store a plurality of run-length coded state transitions, the computer readable storage medium comprising:

a code segment executable by a processor for reading the run-length coded state transitions; and

a code segment executable by a processor that is configured to perform an optimal memory word packing algorithm on the read run-length coded state transitions to determine how the run-length coded state transitions are to be stored in the words of the transition table memory;

wherein the code segments are resident on the computer readable storage medium.