Methods and apparatus for regular expression matching

• US 7,308,446 B1
• Filed: 01/10/2003
• Issued: 12/11/2007
• Est. Priority Date: 01/10/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Panigrahy, Rina, Nguyen, Anh Tien, Nelson, William
• Primary Examiner(s): Rodriguez, Paul
• Assistant Examiner(s): Osborne, Luke
• Application Number:
  US10/340,392
• Time in Patent Office: 1,796 Days
• Field of Search: 707/6, 707/3, 707/101, 706/48
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Methods and apparatus are disclosed for regular expression matching, especially for, but not limited to high-speed applications such as in a packet switching system (e.g., a router). One implementation includes a matching mechanism for processing each character of a plurality of input characters to progressively generate keyword indications of matched keywords as matched keywords are identified, and for generating one or more matching indications of matched base expressions and non-keyword expressions. These indications are received by a matched regular expression detection mechanism which generates one or more matched regular expression indications based on said one or more keyword indications and said one or more matching indications. In one implementation, the matched regular expression detection mechanism maintains a keyword data structure, which is updated as matched keyword indications are received to ensure they are matched in a proper order. One implementation uses a bitmap to track the matched keywords and AND-SHIFT-OR operations to efficiently update the bitmap.

Claims

1. An apparatus for performing regular expression matching, the apparatus comprising:

a matching mechanism configured to process the value of each character of a plurality of input characters in order to progressively generate matched indications in response to matching a keyword, base expression or non-keyword expression based on processing the values of said input characters; and

a matched regular expression detection mechanism, coupled to the matching mechanism, configured to receive said matched indications from the matching mechanism, to process said received matched indications based on their relative order to identify whether or not one or more regular expressions have been matched, and to generate one or more matched regular expression indications in response to said processing of said received matched indications identifying said one more regular expressions as being matched.

2. The apparatus of claim 1, wherein the matched regular expression detection mechanism includes a keyword data structure, and said received keyword indications include a reference to an entry in the keyword data structure for identifying a particular entry of a plurality of entries for tracking an ordered matching of keywords of a regular expression corresponding to the particular entry.

3. The apparatus of claim 2, wherein the matched regular expression detection mechanism includes a final state data structure, the final state data structure including a plurality of final state entries, each of the plurality of final state entries identifying matched base expressions and non-keyword expressions for a corresponding final state.

4. The apparatus of claim 3, wherein the keyword data structure is updated based on one or more matched base expressions identified in the final state data structure based on said one or more matching indications.

5. The apparatus of claim 1, wherein the matched regular expression detection mechanism includes a final state data structure, the final state data structure including a plurality of final state entries, each of the plurality of final state entries identifying matched base expressions and non-keyword expressions for a corresponding final state.

6. The apparatus of claim 1, wherein said one or more matched regular expression indications indicate one or more of said regular expressions identified as being matched or a single, highest-priority matching expression of said regular expressions identified as being matched.

7. The apparatus of claim 1, wherein the matched regular expression detection mechanism includes one or more keyword bitmaps;

wherein a particular bit of a particular keyword bitmap of said one or more keyword bitmaps corresponding to a particular keyword identified as matched in a particular keyword indication of said received matched indications is set only if the previous adjacent bit in particular keyword bitmap is currently set if it is not a first bit of the particular keyword bitmap.

8. The apparatus of claim 1, wherein the matching mechanism includes a state machine used in said processing the value of each character of the plurality of input characters.

9. The apparatus of claim 8, wherein the state machine is a deterministic finite automation.

10. A method for performing regular expression matching in order to identify one or more matching expressions, the method comprising:

a first stage state machine processing the value of each character of a string of characters on which to perform matching, said processing including;

determining a next state of a state machine;

identifying for said determined next state whether there are any newly matched keywords, and if so, generating an indication of said newly matched keywords; and

identifying whether said determined next state is a final state, and if so, generating an indication of a base or non-keyword matching expression; and

a second stage receiving said indications of the said newly matched keywords in the order generated and of the base or non-keyword matching expression, updating a keyword expression data structure based on said received indications of said newly matched keywords for all occurrences of said newly matched keywords in which all keywords preceding said newly matched keywords in an expression have been previously matched, and determining and generating indications of said one or more matching expressions based on the keyword expression data structure and said indications of base and non-keyword matching expressions.

11. The method of claim 10, wherein said indication of base and non-keyword matching expression include an index into a final state data structure;

and

wherein said determining one or more matching expression includes;

performing a lookup operation of the final state data structures based on said the index to identifying matched base expressions and non-keyword expressions; and

updating the keyword data structure based on said matched base expressions and non-keyword expressions.

12. The method of claim 10 comprising:

initializing the keyboard expression data structure when said indication of base and non-keyword matching expressions corresponds to a suffix keyword expression ending in a tab or new line character.

13. The method of claim 10, comprising:

initializing the keyword expression data structure when said indication of base and non-keyword matching expressions corresponds to a predetermined keyword trigger.

14. The method of claim 13, wherein the predetermined keyword trigger includes a TAB-NEW LINE sequence.

15. The method of claim 10, wherein the keyword expression data structure includes one or more keyword bitmaps;

and wherein said updating a keyword expression data structure includes setting a particular bit of a particular keyword bitmap of said one or more keyword bitmaps corresponding to a particular keyword identified as matched in a particular keyword indication of said one or more keyword indications only if the previous adjacent bit in particular keyword bitmap is currently set if it is not a first bit of the particular keyword bitmap.

16. An apparatus for performing regular expression matching in order to identify one or more matching expressions, the apparatus comprising:

a matching mechanism including;

means for processing the value of each character of a string of characters on which to perform matching, said means for processing including;

means for determining a next state;

means for identifying whether there are newly matched keywords, and if so, generating an indication of said newly matched keywords; and

means for identifying whether the next state is a final state, and if so, generating an indication of base and non-keyword matching expressions;

a matched regular expression detection mechanism, coupled to the matching mechanism, configured to received said indications of the said newly matched keywords in the order generated and said indication of base and non-keyword matching expressions;

the matched regular expression detection mechanism including;

means for updating a keyword expression data structure based on said newly matched keywords for all occurrences in of said newly matched keywords in which all keywords preceding said newly matched keywords in an expression have been previously matched; and

means for determining and generating indications thereof said one or more matching expressions based on the keyword expression data structure and said indication of base and non-keyword matching expressions.

17. The apparatus of claim 16, wherein said indication of base and non-keyword matching expressions include an index into a final state data structure;

and

wherein said means for determining and generating indications thereof said one or more matching expressions includes;

means for performing a lookup operation of the final state data structure based on said the index to identifying matched base expressions and non-keyword expressions; and

means for updating the keyword data structure based on said matched base expressions and non-keyword expressions.

18. The apparatus of claim 16, wherein the keyword expression data structure includes one or more keyword bitmaps;

and wherein said means for updating a keyword expression data structure includes means for setting a particular bit of a particular keyword bitmap of said one or more keyword bitmaps corresponding to a particular keyword identified as matched in a particular keyword identification of said one or more keyword identifications only if the previous adjacent bit in particular keyword bitmap is currently set if it is not a first bit of the particular keyword bitmap.

19. An apparatus for performing regular expression matching, the apparatus comprising:

a matching mechanism configured to process the value of each character of a plurality of input characters in order to progressively generate one or more keyword indications of matched keywords when one or more matched keywords are identified; and

a matched regular expression detection mechanism, coupled to the matching mechanism, and configured to receive said keyword indications of matched keywords from the matching mechanism and configured to generate one or more matched regular expression indications based on said received keyword indications in response to the matched regular expression detection mechanism identifying one or more regular expressions as being matched.

20. The apparatus of claim 19, wherein the matched regular expression detection mechanism includes a keyword data structure, and said received keyword indications include a reference to an entry in the keyword data structure for identifying a particular entry of a plurality of entries for tracking an ordered matching of keywords for a regular expression corresponding to the particular entry.

21. The apparatus of claim 19, wherein the matched regular expression detection mechanism includes one or more keyword bitmaps;

wherein a particular bit of a particular keyword bitmap of said one or more keyword bitmaps corresponding to a particular keyword identified as matched in a particular keyword indication of said received keyword indications is set if it is not a first bit of the particular keyword bitmap only if the previous adjacent bit in particular keyword bitmap is currently set.

22. The apparatus of claim 21, wherein the matched regular expression detection mechanism includes means for bit manipulating said keyword bitmaps, including means for performing an AND-SHIFT-OR operation on said keyword bitmaps.

23. The apparatus of claim 19, wherein the matching mechanism includes a state machine used in said processing the value each character of the plurality of input characters.

24. The apparatus of claim 23, wherein the state machine is a deterministic finite automation.