Intelligent Graph Walking

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.

What is claimed is: 
     
         1 . A method comprising:
 generating a graph including a plurality of interconnected nodes in a device operatively coupled to a network, the plurality of interconnected nodes including at least one starting node and a plurality of ending nodes, the at least one starting node associated with a comparison command and a location table including multiple entries, each entry of the multiple entries including node position information of a respective ending node of the plurality of ending nodes and a location table string value of a sub-string between the at least one starting node and the respective ending node; and   employing the comparison command to compare at least one location table string value of the multiple entries with an input sub-string value from an input stream to detect a common sub-string of at least one expression matching in the input stream, the input stream received from the network via a hardware interface of the device.   
     
     
         2 . The method of  claim 1 , wherein employing is based on positively matching a given segment from the input stream at the at least one starting node and identifying the at least one starting node as a given node of the plurality of interconnected nodes associated with a corresponding location table. 
     
     
         3 . The method of  claim 1 , further comprising determining a first length of the input sub-string value based on a second length of a given location table string value of the at least one location table string value of the multiple entries. 
     
     
         4 . The method of  claim 3 , further comprising selecting a given entry of the multiple entries having a longest length location table string value of the at least one location table string value in an event multiple location table string values of the at least one location table string value are identified as matching multiple input sub-string values. 
     
     
         5 . The method of  claim 1 , further comprising recognizing the at least one starting node as a starting node type of a plurality of node types and employing the comparison command based on the recognition. 
     
     
         6 . The method of  claim 1 , wherein employing the comparison command is based on determining that the at least one starting node is associated with a forward arc that is associated with a given segment from the input stream based on traversing the at least one starting node with the given segment. 
     
     
         7 . The method of  claim 6 , wherein the segment is a beginning character of the at least one location table string value. 
     
     
         8 . The method of  claim 1 , further comprising traversing a given end node of the plurality of end nodes based on node position information of a given entry of the multiple entries, the given entry identified based on matching a given location table string value of the multiple entries with the input sub-string value. 
     
     
         9 . The method of  claim 1 , wherein to detect the common sub-string includes comparing location table string values of the multiple entries in any order. 
     
     
         10 . The method of  claim 1 , wherein to detect the common sub-string includes comparing each location table string value of the multiple entries with different input sub-string values, concurrently. 
     
     
         11 . The method of  claim 1 , wherein the device is a security appliance. 
     
     
         12 . An apparatus comprising:
 a compiler configured to generate a graph including a plurality of interconnected nodes; and   a memory configured to store the generated graph, the plurality of interconnected nodes including at least one starting node and a plurality of ending nodes, the at least one starting node associated with a comparison command and a location table including multiple entries, each entry of the multiple entries including node position information of a respective ending node of the plurality of ending nodes and a location table string value of a sub-string between the at least one starting node and the respective ending node, the comparison command enabling a comparison of at least one location table string value of the multiple entries with an input sub-string value from an input stream received via a hardware interface of the apparatus to detect a common sub-string of at least one expression matching in the input stream.   
     
     
         13 . An apparatus comprising:
 a hardware interface configured to receive an input stream; and   a walker configured to:
 traverse a graph including a plurality of interconnected nodes, the plurality of interconnected nodes including at least one starting node and a plurality of ending nodes, the at least one starting node associated with a comparison command and a location table including multiple entries, each entry of the multiple entries including node position information of a respective ending node of the plurality of ending nodes and a location table string value of a sub-string between the at least one starting node and the respective ending node; and 
 employ the comparison command to compare at least one location table string value of the multiple entries with an input sub-string value from an input stream to detect a common sub-string of at least one expression matching in the input stream, the input stream received from the network via a hardware interface of the device. 
   
     
     
         14 . The apparatus of  claim 13 , wherein the comparison command is employed based on positively matching a given segment from the input stream at the at least one starting node and identifying the at least one starting node as a given node of the plurality of interconnected nodes associated with a corresponding location table. 
     
     
         15 . The apparatus of  claim 13 , wherein the walker is further configured to determine a first length of the input sub-string value based on a second length of a given location table string value of the at least one location table string value of the multiple entries. 
     
     
         16 . The apparatus of  claim 15 , wherein the walker is further configured to select a given entry of the multiple entries having a longest length location table string value of the at least one location table string value in an event multiple location table string values of the at least one location table string value are identified as matching multiple input sub-string values. 
     
     
         17 . The apparatus of  claim 13 , wherein the walker is further configured to recognize the at least one starting node as a starting node type of a plurality of node types and employing the comparison command based on the recognition. 
     
     
         18 . The apparatus of  claim 13 , wherein the walker is further configured to employ the comparison command based on determining that the at least one starting node is associated with a forward arc that is associated with a given segment from the input stream based on traversing the at least one starting node with the given segment. 
     
     
         19 . The apparatus of  claim 18 , wherein the segment is a beginning character of the at least one location table string value. 
     
     
         20 . The apparatus of  claim 13 , wherein the walker is further configured to traverse a given end node of the plurality of end nodes based on node position information of a given entry of the multiple entries, the given entry identified based on matching a given location table string value of the multiple entries with the input sub-string value. 
     
     
         21 . The apparatus of  claim 13 , wherein to detect the common sub-string the walker is further configured to compare location table string values of the multiple entries in any order. 
     
     
         22 . The apparatus of  claim 13 , wherein to detect the common sub-string the walker is further configured to compare each location table string value of the multiple entries with different input sub-string values, concurrently.