Intelligent graph walking

• US 8,819,217 B2
• Filed: 11/01/2007
• Issued: 08/26/2014
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Hussain, Muhammad Raghib, Goyal, Rajan, Badr, Imrar
• Primary Examiner(s): Nguyen, Phuoc
• Assistant Examiner(s): SISON, JUNE Y
• Application Number:
  US11/982,433
• Publication Number:
  US 20090119399A1
• Time in Patent Office: 2,490 Days
• Field of Search: 709/224
• US Class Current: 709/224
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

An apparatus, and corresponding method, for performing a search for a match of at least one expression in an input stream is presented. A graph including a number of interconnected nodes is generated. A compiler may assign at least one starting node and at least one ending node. The starting node includes a location table with node position information of an ending node and a sub-string value associated with the ending node. Using the node position information and a string comparison function, intermediate nodes located between the starting and ending nodes may be bypassed. The node bypassing may reduce the number of memory accesses required to read the graph.

Claims

1. A method comprising:

in a security appliance having a physical interface receiving an input stream;

generating a graph including a plurality of interconnected nodes, at least one ending node, and at least one starting node, the at least one starting node including a comparison command and a location table, the location table including node position information of the at least one ending node and a value of a sub-string between the at least one starting node and the at least one ending node;

traversing the plurality of interconnected nodes of the generated graph to search for a match of at least one expression in the input stream;

upon reaching the at least one starting node in the generated graph and upon finding a forward arc from the at least one starting node, the forward arc representing a match between the at least one expression and a character from the input stream, detecting a common sub-string in the at least one expression and the value of the sub-string in the location table using the comparison command;

upon detection of the common sub-string, bypassing at least two consecutively interconnected nodes in the generated graph by using the location table included in the at least one starting node to reach the at least one ending node indicated by the node position information of the at least one ending node, wherein the generated graph includes plural ending nodes and the location table includes multiple entries, each entry including node position information of a corresponding ending node of the plural ending nodes and a value of a sub-string between the at least one starting node and the corresponding ending node; and

using the comparison command to detect a common sub-string in the at least one expression and the value of the sub-string in the location table for each of the multiple entries in any order.

2. The method of claim 1 in which the at least one starting node is a root node.

3. The method of claim 1 in which the at least one starting node is an interconnecting node, the interconnecting node including at least two interconnections to at least two other nodes.

4. The method of claim 1 in which the at least one ending node is a mark node, the mark node indicating a matched expression.

5. The method of claim 1 in which the at least one ending node is an other starting node.

6. The method of claim 5 in which the other starting node is an interconnecting node, the interconnecting node including at least two interconnections to at least two other nodes.

7. The method of claim 1 where bypassing comprises retrieving node position information of the at least two consecutively interconnected nodes with a single memory access.

8. The method of claim 1 further comprising selecting the at least one ending node with a longest common sub-string, a shortest common sub-string, or both.

9. An apparatus comprising:

a hardware interface configured to receive an input stream;

a compiler configured to generate a graph including a plurality of interconnected nodes, at least one ending node, and at least one starting node, the at least one starting node including a comparison command and a location table, the location table including node position information of the at least one ending node and a value of a sub-string between the at least one starting node and the at least one ending node;

a memory communicatively coupled to the compiler and configured to store the generated graph; and

a walker process communicatively coupled to the hardware interface and configured to;

traverse the plurality of interconnected nodes of the generated graph to search for a match of at least one expression in the input stream;

upon reaching the at least one starting node and upon finding a forward arc from the at least one starting node, the forward arc representing a match between the at least one expression and a character from the input stream, the walker process configured to detect a common sub-string in the at least one expression and the value of the sub-string in the location table, using the comparison command;

upon detection of the common sub-string, bypass at least two consecutively interconnected nodes in the generated graph by using the location table included in the at least one starting node to reach the at least one ending node indicated by the node position information of the at least one ending node, wherein the generated graph includes plural ending nodes and the location table includes multiple entries, each entry including node position information of a corresponding ending node of the plural ending nodes and a value of a sub-string between the at least one starting node and the corresponding ending node; and

use the comparison command to detect a common sub-string in the at least one expression and the value of the sub-string in the location table for each of the multiple entries in any order.

10. The apparatus of claim 9 in which the at least one starting node is a root node.

11. The apparatus of claim 9 in which the at least one starting node is an interconnecting node, the interconnecting node including at least two interconnections to at least two other nodes.

12. The apparatus of claim 9 in which the at least one ending node is a mark node, the mark node indicating a matched expression.

13. The apparatus of claim 9 in which the at least one ending node is an other starting node.

14. The apparatus of claim 13 in which the other starting node is an interconnecting node, the interconnecting node including at least two interconnections to at least two other nodes.

15. The apparatus of claim 9 in which the walker process is configured to bypass the at least two consecutively interconnected nodes and retrieve node position information of the at least two consecutively interconnected nodes with a single memory access.