System and method for performing regular expression matching with high parallelism

• US 7,225,188 B1
• Filed: 02/13/2002
• Issued: 05/29/2007
• Est. Priority Date: 02/13/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Gai, Silvano, Malagrino, Dante
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Filipczyk; Marcin R.
• Application Number:
  US10/074,616
• Time in Patent Office: 1,931 Days
• Field of Search: 707 1- 10, 707/100, 707/200, 707/101, 711/108
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system and method for searching data strings, such as network messages, for one or more predefined regular expressions is provided. Regular expressions are programmed into a pattern matching engine so that multiple characters, e.g., 32, of the data strings can be searched at the same time. The pattern matching engine includes a regular expression storage device having one or more content-addressable memories (CAMs) whose rows may be divided into sections. Each predefined regular expression is analyzed so as to identify the “borders” within the regular expression. A border is preferably defined to exist at each occurrence of one or more predefined metacharacters, such as “.*”, which finds any character zero, one or more times. The borders separate the regular expression into a sequence of sub-expressions each of which may be one or more characters in length. Each sub-expression is preferably programmed into a corresponding section of the pattern matching engine. The system may also be configured so as to search multiple regular expressions in parallel.

Claims

1. A method for operating a pattern matching engine having a plurality of information storage entries with two or more regular expressions, each regular expression including a plurality of characters and each regular expression associated with a corresponding action to be applied when matching strings are found, the method comprising the steps of:

identifying one or more borders within each regular expression, the one or more borders separating the regular expression into a plurality of sub-expressions, each sub-expression having a plurality of sequential characters;

loading each entry of the plurality of entries of the pattern matching engine with the plurality of the sequential characters from one of the sub-expressions of the plurality of sub-expressions, wherein the borders are defined by a predetermined sequence of regular expression metacharacters, and the entries stored in content addressable memory (CAM);

applying a string from a network message to the entries of the pattern matching engine to search the string simultaneously in parallel for sub-expressions from each of the two or more regular expressions;

determining that the sub-expressions of at least one regular expression match the string; and

executing the corresponding action associated with that at least one regular expression on the network message.

2. The method of claim 1 wherein the predetermined sequence of regular expression metacharacters is a first regular expression metacharacter defined to match any one character of the plurality of sequential characters from one of the sub-expressions followed immediately by a second regular expression metacharacter defined to match the one character zero, one, or more times.

3. The method of claim 1 further comprising a step of organizing at least part of the pattern matching engine into a plurality of sections, and wherein each section of the pattern matching engine is loaded with a plurality of search patterns for a corresponding sub-expression.

4. The method of claim 3 wherein the plurality of search patterns of a section are loaded with a search pattern that includes a complete match of a respective sub-expression, a search pattern that includes a partial match of the respective sub-expression, and a mismatch pattern.

5. The method of claim 4 further comprising the steps of:

associating at least one sub-expression with a current state variable; and

loading the associated current state variable into each entry of a section of the pattern matching engine that contains the at least one sub-expression.

6. The method of claim 1 wherein

the CAM is a ternary content addressable memory, a TCAM, that supports don'"'"'t care values, and

each regular expressions loaded to the CAM has a plurality of search patterns including a mismatch pattern having don'"'"'t care values.

7. The method of claim 6 wherein each entry of the TCAM identifies a corresponding entry of a second memory device.

8. The method of claim 7 wherein at least one TCAM entry is associated with a next state variable, the method further comprising the step of loading an entry of the second memory device that is identified by the at least one TCAM entry with the associated next state variable.

9. The method of claim 8 wherein

the at least one TCAM entry is located in a TCAM section whose entries are associated with a current state variable having a first value, and

the next state variable has a second value that differs from the first value, wherein the next state variable specifies a new TCAM section to be searched.

10. The method of claim 9 wherein each TCAM entry has a match cell that contains the complete match, the partial match or the mismatch pattern.

11. The method of claim 1 wherein

the pattern matching engine further includes a second memory device having a plurality of entries, and

the entries of the second memory device are loaded with the corresponding actions associated with the two or more regular expressions.

12. An apparatus comprising:

means for pattern matching having a plurality of information storage entries with two or more regular expressions, each regular expression including a plurality of characters and each regular expression associated with a corresponding action to be applied when matching strings are found;

means for identifying one or more borders within each regular expression, the one or more borders separating the regular expression into a plurality of sub-expressions, each sub-expression having a plurality of sequential characters;

means for loading each of the plurality of entries of the means for pattern matching with the plurality of the sequential characters from one of the sub-expressions of the plurality of sub-expressions, the entries stored in content addressable memory (CAM);

means for applying a string from a network message to the entries of the pattern matching engine to search the string simultaneously in parallel for sub-expressions from each of the two or more regular expressions;

means for determining that the sub-expressions of at least one regular expression match the string; and

means for executing the corresponding action associated with that at least one regular expression on the network message.

13. The apparatus of claim 12, further comprising:

means for organizing at least part of the CAM into a plurality of sections, and wherein each section of the CAM is loaded with a plurality of search patterns for a corresponding sub-expression.

14. The apparatus of claim 12, further comprising:

means for associating at least one sub-expression with a current state variable; and

means for loading the associated current state variable into each entry of the CAM that contains the at least one sub-expression.

15. The apparatus of claim 12, further comprising:

means for including at the pattern matching engine a memory device having a plurality of entries;

means for loading the memory device with the corresponding actions associated with the two or more regular expressions.

16. The apparatus of claim 12, further comprising:

means for using a ternary content addressable memory (TCAM) for the CAM, each entry of the TCAM identifying a corresponding entry of the memory device.

17. An apparatus comprising:

a pattern matching engine having a plurality of information storage entries configured to store two or more regular expressions, each regular expression including a plurality of characters and associated with a corresponding action to be applied to a network message, the pattern matching engine configured to identify one or more borders within a regular expression, the one or more borders separating the regular expression into a plurality of sub-expressions, each sub-expression having a plurality of sequential characters, each entry of the plurality of entries of the pattern matching engine including the plurality of sequential characters from one of the sub-expressions of the plurality of subexpressions, the pattern matching engine configured to apply a string from a network message to the entries to search the string simultaneously in parallel for sub-expressions from each of the two or more regular expression and to determine that the plurality of sequential characters from the sub-expressions of at least one regular expression match the string, and then to execute the corresponding action associated with that at least one regular expression on the network message; and

a content addressable memory (CAM), the CAM configured to store the plurality of sequential characters from the plurality of sub-expressions.

18. The apparatus of claim 17, further comprising:

at least part of the CAM organized into a plurality of sections wherein each section is loaded with a plurality of search patterns for a corresponding sub-expression.

19. The apparatus of claim 17, further comprising:

the pattern matching engine configured to associate each sub-expression with a current state variable; and

the pattern matching engine configured to store each associated current state variable into a CAM entry that contains at least one sub-expression.

20. The apparatus of claim 17, further comprising:

a second memory device having a plurality of entries, the second memory device configured to store the corresponding actions associated with the two or more regular expressions.

21. The apparatus of claim 17, further comprising:

the CAM configured as a ternary content addressable memory (TCAM), the TCAM storing a corresponding entry for each entry of the second memory device.

22. A method for operating a pattern matching engine comprising the steps of:

obtaining two or more regular expressions;

identifying one or more borders within each regular expression using a deterministic finite state machine, the one or more borders separating the regular expression into a plurality of sub expressions, each sub expression including one or more characters, each border indicated by one or more predetermined metacharacters;

loading separate portions of a memory of the pattern matching engine with the sequential characters from each of the plurality of sub expressions of the two or more regular expressions;

applying a string from a network message to the memory to search the string in parallel for sub expressions from each of the two or more regular expression; and

determining that at least one of the two or more regular expressions matches the string and executing in response thereto a corresponding action associated with that regular expression;

wherein the memory is a content addressable memory (CAM).

23. The method of claim 22 wherein the step of loading further comprises the step of:

generating a plurality of search patterns for the sequential characters from each of the plurality of sub expressions and loading these search patterns into the separate portions of the memory.

24. The method of claim 22 wherein the deterministic finite state machine is constructed by combining separate deterministic finite state machines of each of the two or more regular expressions into a single deterministic finite state machine that identifies borders in the two or more regular expressions.

25. The method of claim 22 wherein the deterministic finite state machine is configured to parse regular expressions one character at a time.

26. The method of claim 25 wherein the deterministic finite state machine is configured to transition between states in response to valid character matches with parsed characters of regular expressions.

27. The method of claim 22 wherein the one or more predetermined metacharacters comprise a specific sequence of metacharacters.

28. The method of claim 27 wherein the specific sequence of metacharacters comprises a first regular expression metacharacter that defines a match to any one character followed by a second regular expression metacharacter defined to match a preceding element zero, one, or more than one times.

29. An apparatus comprising:

a pattern matching engine configured to obtain two or more regular expressions and to identify one or more borders within each regular expression using a deterministic finite state machine, the one or more borders separating the regular expression into a plurality of sub expressions, each sub expression including one or more characters, each border indicated by one or more predetermined metacharacters;

a memory of the pattern matching engine configured to store the sequential characters from each of the plurality of sub expressions of the two or more regular expressions in separate portions of memory, the memory further configured to, in response to application of a string from a network message, search the string in parallel for sub expressions from each of the two or more regular expression, and to determine that at least one of the two or more regular expressions matches the string; and

the pattern matching engine further configured to cause the execution of a corresponding action associated with that regular expression that matches;

wherein the memory is a content addressable memory (CAM).

30. The apparatus of claim 29 wherein the memory is further configured to store a plurality of search patterns for the sequential characters of each of the plurality of sub expressions.

31. The apparatus of claim 29 wherein the deterministic finite state machine is constructed by combining separate deterministic finite state machines of each of the two or more regular expressions into a single deterministic finite state machine that identifies borders in the two or more regular expressions.

32. The apparatus of claim 29 wherein the deterministic finite state machine is configured to parse regular expressions one character at a time.

33. The apparatus of claim 29 wherein the deterministic finite state machine is configured to transition between states in response to valid character matches with parsed characters of regular expressions.

34. The apparatus of claim 29 wherein the one or more predetermined metacharacters comprise a specific sequence of metacharacters.

35. The apparatus of claim 34 wherein the specific sequence of metacharacters comprises a first regular expression metacharacter that defines a match to any one character followed by a second regular expression metacharacter defined to match a preceding element zero, one, or more than one times.