Apparatus and method for parallel regular expression matching

• US 8,990,232 B2
• Filed: 05/15/2012
• Issued: 03/24/2015
• Est. Priority Date: 05/15/2012
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Rossi, Frederic
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): Sultana, Nargis
• Application Number:
  US13/472,318
• Publication Number:
  US 20130311495A1
• Time in Patent Office: 1,043 Days
• Field of Search: 707/758, 707/737, 709/223
• US Class Current: 707/758
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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 69/22 Parsing or analysis of headers

Abstract

A regular expression matching hardware implementation comprises two tightly coupled hardware engines. A regex engine performs state transitions and accepts (as matching) or rejects (as not matching) an input string. The regex engine takes also care of the logic of the operators and deals with the complexity of the state machine. A lookup engine reads characters from an input (e.g., tape, memory, network packets, or the like), and provides them to the regex engine. A preprocessing procedure transforms a regular expression into a regex state transition table and a lookup table, for use by the regex engine and lookup engine, respectively. The two hardware engines are synchronized by a global state machine. The regex engine advances the state machine, and the lookup engine reads it.

Claims

1. A method of matching a stream of characters against a predetermined regular expression, implemented using computational hardware comprising at least two hardware engines, the at least two hardware engines comprising a lookup engine and a regex engine, the method comprising:

obtaining a transition table representing the regular expression as a graph comprising one or more input-conditional state transition specifications not limited to single-character inputs;

generating a lookup table based on the transition table, the lookup table containing exactly one entry for each state of a state machine, each entry specifying a number n of characters to obtain from the character stream, wherein n is a non-negative integer not limited to 0 or 1;

initializing the state machine;

executing the lookup engine operative to, at each state of the state machine, retrieve the n characters specified in the lookup table for that state, and provide the n characters to the regex engine; and

executing the regex engine operative to, at each state of the state machine, perform one of;

calculating a next state of the state machine based on the current state, the n characters received from the lookup engine, and the graph of state transition specifications; and

terminating the method if all characters received from the lookup engine fail to match input conditions for all active state transition specifications or if a match succeeds.

2. The method of claim 1 wherein obtaining a transition table comprises compiling a regular expression into a graph comprising a plurality of input-conditional state transition specifications not limited to single-character inputs.

3. The method of claim 1 further comprising optimizing the transition table by eliminating any state transition specifications, not referenced elsewhere within the graph, that are not conditional on an input and operate only to advance the state machine.

4. The method of claim 1 further comprising optimizing the transition table by combining two or more sequential input-conditional state transition specifications into one state transition specification dependent on a combined input, if the input-conditional state transition specifications prior to the last one are not referenced elsewhere within the graph.

5. The method of claim 1 wherein the regular expression syntax differentiates between:

parallel evaluation of two or more sub-expressions, wherein the state machine forks and the regex engine evaluates characters from the character stream against the sub-expressions in parallel; and

backtracking evaluation of two or more sub-expressions, wherein the regex engine evaluates characters from the character stream against the sub-expressions sequentially.

6. The method of claim 1, further comprising evaluating a plurality of regular expressions, by:

obtaining a plurality of transition tables, each representing a regular expression;

generating a plurality of lookup tables based on the plurality of transition tables;

initializing a plurality of state machines;

executing a lookup engine operative to retrieve characters as specified in each lookup table, and provide the characters to the associated regex engine; and

executing a plurality of regex engines, each operative to advance an associated state machine based on input from an associated transition table.

7. The method of claim 6 wherein the lookup engine is operative to provide characters to each regex engine in response to the lookup table associated with that regex engine.

8. The method of claim 6 wherein the lookup engine is operative to, for each iteration of character retrieval, select one of a plurality of active regex engines, and is further operative to disable all non-selected regex engines.

9. A regular expression matching apparatus, comprising:

an input operative to provide characters to be matched to a regular expression in groups of zero, one, and multiple characters;

memory operative to store;

a first lookup table containing exactly one entry for each state of a state machine, each entry specifying a number n of characters to retrieve from the input, wherein n is a non-negative integer not limited to 0 or 1; and

a first transition table representing a first regular expression as a graph comprising a plurality of input-conditional state transition specifications for the first state machine, wherein the input-conditional state transition specifications are not limited to zero- or single-character inputs;

computational hardware comprising at least two hardware engines, the at least two hardware engines comprising;

a lookup engine operative to, at each step of the first state machine, retrieve the n characters specified in the first lookup table from the input and provide the n characters to a first regex engine; and

a first regex engine operative to, at each state of the first state machine, perform one of;

calculating a next state of the first state machine based on its current state, any characters received from the lookup engine, and the graph of input-conditional state transition specifications; and

terminating the matching process if all characters received from the lookup engine fail to match input conditions for all active state transition specifications or if a match succeeds.

10. The apparatus of claim 9 wherein the memory is further operative to store:

a second lookup table specifying a variable number n of characters to retrieve from the input at each state of a second state machine; and

a second transition table representing a second regular expression as a graph comprising a plurality of input-conditional state transition specifications for the second state machine, wherein the input-conditional state transition specifications are not limited to zero- or single-character inputs;

wherein the lookup engine is further operative to, at each step of the second state machine, retrieve the n characters specified in the second lookup table from the input and provide the n characters to a second regex engine; and

further comprising a second regex engine operative to, at each state of the second state machine, perform one of;

calculating a next state of the second state machine based on its current state, any characters received from the lookup engine, and the graph of input-conditional state transition specifications; and

terminating the matching process if all characters received from the lookup engine fail to match input conditions for all active state transition specifications or if a match succeeds.

11. The apparatus of claim 10 wherein the lookup engine is further operative to arbitrate among the first and second regex engines that are active;

select one of the first or second regex engines;

enable the selected regex engine; and

perform character lookup in response to the corresponding lookup table and the current state of the corresponding state machine.

12. The apparatus of claim 11 wherein the lookup engine is further operative to suspend the matching process of the non-selected first or second regex engine while retrieving characters for the selected first or second regex engine.

13. The apparatus of claim 12 wherein the lookup engine is operative to suspend the matching process of the non-selected first or second regex engine by employing a mutual exclusion (mutex) mechanism.