Intelligent graph walking
First Claim
Patent Images
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.
7 Assignments
0 Petitions
Accused Products
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.
87 Citations
15 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
Specification