Reverse NFA generation and processing

• US 9,762,544 B2
• Filed: 09/24/2015
• Issued: 09/12/2017
• 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
• Primary Examiner(s): LYNCH, SHARON S
• Application Number:
  US14/863,484
• Publication Number:
  US 20160021060A1
• Time in Patent Office: 719 Days
• 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 an apparatus including a multi-layer protocol processor configured to inspect content of data received from a network;

improving inspection performance of the processor by (a) determining whether or not a given regular expression pattern requires a match of at least one back-reference and (b) in response to determining that the given regular expression pattern requires the match and prior to inspecting the content received from the network, generating a reverse non-deterministic finite automata (rNFA) graph for the given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters for inspecting the content 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 at least one back reference, the apparatus forwarding the content of the data to the network based on the inspecting.

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

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

generating the rNFA graph using the revised pattern.

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

determining locations of the given regular expression pattern requiring the match of the at least one back-reference; and

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

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

the beginning offset of the at least one back-reference corresponding to a first offset of the sequence of characters, the end offset of the at least one back-reference corresponding to a second offset of the sequence of characters, and a length of the at least one back-reference within the sequence of characters.

5. The method of claim 2 wherein generating the rNFA graph further includes:

determining locations of the given regular expression pattern including the capture group associated with the at least one 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.

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

the beginning offset of the capture group corresponding to a first offset of the sequence of characters, the 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.

7. An apparatus, the apparatus comprising:

a multi-layer protocol processor implemented in hardware, the processor configured to inspect content of data received from a network and to implement a compiler configured to;

improve inspection performance of the processor by (a) determining whether or not a given regular expression pattern requires a match of at least one back-reference and (b) in response to determining that the given regular expression pattern requires the match and prior to inspecting the content received from the network, generating a reverse non-deterministic finite automata (rNFA) graph for the given regular expression pattern, the rNFA graph including processing nodes for walking a sequence of characters for inspecting the content 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 at least one back reference, the apparatus configured to forward the content of the data to the network based on the inspecting.

8. The apparatus of claim 7 wherein the compiler is further configured to:

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

generate the rNFA graph using the revised pattern.

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

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

the beginning offset of the at least one back-reference corresponding to a first offset of the sequence of characters, the end offset of the at least one back-reference corresponding to a second offset of the sequence of characters, and a length of the at least one back-reference within the sequence of characters.

11. The apparatus of claim 8 wherein the compiler is further configured to determine locations of the given regular expression pattern including the capture group associated with the at least one 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.

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

the beginning offset of the capture group corresponding to a first offset of the sequence of characters, the 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.