Reverse NFA Generation And Processing

• US 20160021060A1
• Filed: 09/24/2015
• Published: 01/21/2016
• Est. Priority Date: 11/23/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Goyal, Rajan, Billa, Satyanarayana Lakshmipathi
• Granted Patent: US 9,762,544 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/0254 Stateful filtering
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

In a processor of a security appliance, an input of a sequence of characters is walked through a finite automata graph generated for at least one given pattern. At a marked node of the finite automata graph, if a specific type of the at least one given pattern is matched at the marked node, the input sequence of characters is processed through a reverse non-deterministic finite automata (rNFA) graph generated for the specific type of the at least one given pattern by walking the input sequence of characters backwards through the rNFA beginning from an offset of the input sequence of characters associated with the marked node. Generating the rNFA for a given pattern includes inserting processing nodes for processing an input sequence of patterns to determine a match for the given pattern. In addition, the rNFA is generated from the given type of pattern.

Claims

1. A method comprising:

in a processor;

generating a reverse non-deterministic finite automata (rNFA) graph for a given type of a given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters to determine a match for the given regular expression pattern to enable recognition of the given regular expression pattern in the sequence of characters, the rNFA graph having at least one processing node inserted into the rNFA graph based on the given type of the given regular expression pattern.

2. The method of claim 1 wherein the given type of the given regular expression pattern includes at least one of the following:

start offset, back reference, capture group, and assertion, or a combination thereof.

3. The method of claim 1 wherein generating the rNFA graph includes:

converting the given regular expression pattern including a back-reference into a revised pattern, wherein converting includes replacing the back-reference with a capture group corresponding to the back-reference; and

generating the rNFA graph using the revised pattern.

4. The method of claim 3 wherein generating the rNFA graph further includes:

determining locations of the given regular expression pattern requiring a back-reference match; and

inserting back-reference processing nodes into the rNFA graph corresponding to locations associated with a beginning offset of the back-reference and an end offset of the back-reference, the beginning offset and end offset of the back-reference corresponding to offset locations of the revised pattern.

5. The method of claim 4 wherein the back-reference processing nodes enable a determination of at least one of the following:

a start offset of the back-reference corresponding to a first offset of the sequence of characters, an end offset of the back-reference corresponding to a second offset of the sequence of characters, and a length of the back-reference within the sequence of characters.

6. The method of claim 3 wherein generating the rNFA graph further includes:

determining locations of the given regular expression pattern including a capture group associated with the back-reference of the given regular expression pattern; and

inserting capture group processing nodes into the rNFA graph corresponding to locations associated with a beginning offset of the capture group and an end offset of the capture group, the beginning offset and end offset of the capture group corresponding to offset locations of the revised pattern.

7. The method of claim 6 wherein the capture group processing nodes enable a determination of at least one of the following:

a start offset of the capture group corresponding to a first offset of the sequence of characters, an end offset of the capture group corresponding to a second offset of the sequence of characters, and a length of the capture group within the sequence of characters.

8. The method of claim 1 wherein generating the rNFA graph includes converting the given regular expression pattern including an assertion into a revised pattern, wherein converting includes removing the assertion.

9. The method of claim 8 further comprising determining a location of the removed assertion of the revised pattern and inserting an assertion processing node in the rNFA graph corresponding to an offset of the revised pattern associated with the location of the removed assertion.

10. The method of claim 9 further comprising determining a subset pattern of the given regular expression pattern corresponding to the removed assertion.

11. The method of claim 10 further comprising:

for the subset pattern, generating a finite automata graph, the finite automata corresponding to a type of assertion; and

linking the generated finite automata graph to the assertion processing node.

12. An apparatus comprising:

a processor implemented in hardware, the processor configured to implement a compiler configured to;

generate a reverse non-deterministic finite automata (rNFA) graph for a given type of a given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters to determine a match for the given regular expression pattern to enable recognition of the given regular expression pattern in the sequence of characters, the rNFA graph having at least one processing node inserted into the rNFA graph based on the given type of the given regular expression pattern.

13. The apparatus of claim 12 wherein the given type of the given regular expression pattern includes at least one of the following:

start offset, back reference, capture group, and assertion.

14. The apparatus of claim 12 wherein the compiler is further configured to:

convert the given regular expression pattern including a back-reference into a revised pattern and replace the back-reference with a capture group corresponding to the back-reference in the revised pattern; and

generate the rNFA graph using the revised pattern.

15. The apparatus of claim 14 wherein the compiler is further configured to determine locations of the given regular expression pattern requiring a back-reference match and insert back-reference processing nodes into the rNFA graph corresponding to locations associated with a beginning offset of the back-reference and an end offset of the back-reference, the beginning offset and end offset of the back-reference corresponding to offset locations of the revised pattern.

16. The apparatus of claim 15 wherein the back-reference processing nodes enable a determination of at least one of the following:

a start offset of the back-reference corresponding to a first offset of the sequence of characters, an end offset of the back-reference corresponding to a second offset of the sequence of characters, and a length of the back-reference within the sequence of characters.

17. The apparatus of claim 14 wherein the compiler is further configured to determine locations of the given regular expression pattern including a capture group associated with the back-reference of the given regular expression pattern and insert capture group processing nodes into the rNFA graph corresponding to locations associated with a beginning offset of the capture group and an end offset of the capture group, the beginning offset and end offset of the capture group corresponding to offset locations of the revised pattern.

18. The apparatus of claim 17 wherein the capture group processing nodes enable a determination of at least one of the following:

a start offset of the capture group corresponding to a first offset of the sequence of characters, an end offset of the capture group corresponding to a second offset of the sequence of characters, and a length of the capture group within the sequence of characters.

19. The apparatus of claim 12 wherein the compiler is further configured to convert the given regular expression pattern including an assertion into a revised pattern and remove the assertion from the revised pattern.

20. The apparatus of claim 19 wherein the compiler is further configured to determine a location of the removed assertion of the revised pattern and insert an assertion processing node in the rNFA graph corresponding to an offset of the revised pattern associated with the location of the removed assertion.

21. The apparatus of claim 20 further wherein the compiler is further configured to determine a subset pattern of the given regular expression pattern corresponding to the removed assertion.

22. The apparatus of claim 21 wherein the compiler is further configured to:

for the subset pattern, generate a finite automata graph, the finite automata graph corresponding to a type of assertion; and

link the generated finite automata graph to the assertion processing node.