Intelligent graph walking

• US 20090119399A1
• Filed: 11/01/2007
• Published: 05/07/2009
• 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: Badr, Imrar, Goyal, Rajan, Hussain, Muhammad Raghib
• Granted Patent: US 8,819,217 B2
• Time in Patent Office: Days
• 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 for performing a search for a match of at least one expression in an input stream, the method comprising:

generating a graph of expressions including a plurality of interconnected nodes, at least one ending node, and at least one starting node, the 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 nodes of the graph to search for the match of the at least one expression in the input stream;

upon reaching the at least one starting node in the graph, detecting a common sub-string in the at least one expression and the sub-string value in the location table, using the comparison command; and

upon detection of the common sub-string, bypassing at least two consecutively interconnected nodes to reach the at least one ending node.

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

3. The method of claim 1 wherein 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 wherein the ending node is a mark node, the mark node indicating a matched expression.

5. The method of claim 1 wherein the ending node is an other starting node.

6. The method of claim 5 wherein 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 wherein 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 wherein generating a searchable graph comprises:

generating the graph with an optimization strategy wherein a node configuration is designed to eliminate duplicate sub-strings.

9. The method of claim 1 comprising:

selecting the at least one ending node in the location table with an optimization algorithm.

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

11. A processor configured to search for a match of at least one expression in an input stream, the processor comprising:

a compiler configured to generate a graph of expressions including a plurality of interconnected nodes, at least one ending node, and at least one starting node, the 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 unit configured to store the graph; and

a walker process configured to traverse the nodes of the graph to search for the match of the at least one expression in the input stream, upon reaching the at least one starting node, the walker process configured to detect a common sub-string in the at least one expression and the sub-string value in the location table, using the comparison command, and upon detection of the common sub-string, the walker process further being configured to bypass at least two consecutively interconnected nodes to reach the at least one ending node.

12. The processor of claim 11 wherein the at least one starting node is a root node.

13. The processor of claim 11 wherein the at least one starting node is an interconnecting node, the interconnecting node including at least two interconnections to at least two other nodes.

14. The processor of claim 11 wherein the ending node is a mark node, the mark node indicating a matched expression.

15. The processor of claim 11 wherein the ending node is an other starting node.

16. The processor of claim 15 wherein the other starting node is an interconnecting node, the interconnecting node including at least two interconnections to at least two other nodes.

17. The processor of claim 11 wherein 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.

18. A processor configured to search for a match of at least one expression in an input stream, the processor comprising:

means for generating a graph of expressions including a plurality of interconnected nodes, at least one ending node, and at least one starting node, the 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;

means for traversing the nodes of the graph to search for the match of the at least one expression in the input stream;

means for detecting, upon reaching the at least one starting node, a common sub-string in the at least one expression and the sub-string value in the location table, using the comparison command; and

means for bypassing, upon detection of the common sub-string, at least two consecutively interconnected nodes to reach the at least one ending node.

19. A computer implemented method for traversing a deterministic finite automata-based graph comprising:

traversing nodes in the graph, with a walker process, to search for an expression in an input stream based on pointers to next nodes stored in a node; and

upon detecting a string comparison match associated with at least one node, executing a bypass function identified by the string comparison to manage the walker process.

20. The computer implemented method of claim 19 wherein the string comparison match reports a match between at least two bytes in the expression in the input stream and at least two consecutive nodes in the graph.

21. The computer implemented method of claim 19 wherein the bypass function is configured to obtain position information of at least two interconnected nodes with a single access to a memory unit.

22. A processor comprising:

a memory unit configured to store a graph having a plurality of nodes; and

a content search mechanism, the content search mechanism comprising a walker that walks the plurality of nodes in the graph to search for an expression in an input stream by executing a string comparison function in at least one node to manage a bypass function of the walker.

23. The processor of claim 22 wherein the bypass function is configured to bypass at least two nodes in an occurrence of a string match, wherein the walker obtains node position information of the at least two nodes with a single memory access.

24. A method for performing a search for a match for plural expressions in a string of characters, the method comprising:

generating a graph for the expressions, the graph including a plurality of interconnected nodes, each node having a location table comprising an array of next node pointers, each next node pointer indicating the next node for a particular character;

for at least one starting node in the graph, the location table further including at least one bypass node pointer indicating a bypass node for a common substring;

traversing the graph to search for the expressions in an input stream based on the pointers stored in the location table at each node; and

upon reaching a starting node in the graph, bypassing, with the bypass node pointer, intermediate nodes if the corresponding substring matches.