Intelligent graph walking

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.