Hierarchical pattern matching devices and methods

Abstract

A network device includes a substring indicator memory and a signature search module for detecting a signature pattern within a stream of network traffic. The signature search module is configured to receive the stream of network traffic, identify a first subject substring from the stream of network traffic, generate a first substring indicator for the first subject substring using a first bitmask on the first subject substring, the first bitmask identifying a plurality of masked bits of the first subject substring, identify a first counter using the first substring indicator as an address into the substring indicator memory, and generate an indication that the signature pattern may be present in the stream of network traffic based on a value of the first counter.

What is claimed is: 
     
         1 . A network device comprising:
 a substring indicator memory including a first search block and a second search block, the first search block is configured for detection of signature pattern substrings of a first substring length, the second search block is configured for detection of signature pattern substrings of a second substring length that is less than the first substring length; and   a signature search hardware module for detecting a signature pattern within a stream of network traffic, the signature search hardware module is configured to:
 receive the stream of network traffic, the stream of network traffic including a window of bytes equal to the first substring length; 
 identify a first subject substring that includes all of the bytes of the window of bytes; 
 identify a second subject substring of a length equal to the second substring length and that includes a subset of bytes of the window of bytes; 
 search the first search block to determine whether a first signature substring is present in the stream of network traffic; 
 search the second search block to determine whether a second signature substring is present in the stream of network traffic; and 
 generate an indication that the signature pattern may be present in the stream of network traffic based on the searches. 
   
     
     
         2 . The network device of  claim 1 , wherein searching the first block and searching the second block are performed simultaneously during each clock cycle. 
     
     
         3 . The network device of  claim 2 , wherein the signature search module is further configured to generate a first substring indicator for the first subject substring and a second substring indicator for the second subject substring prior to the simultaneous searching, wherein searching the first search block includes using the first substring indicator as an address into the first search block, wherein searching the second search block includes using the second substring indicator as an address into the second search block. 
     
     
         4 . The network device of  claim 3 , wherein generating the first substring indicator includes using a first bitmask on the first subject substring, the first bitmask identifying a plurality of masked bits of the first subject substring. 
     
     
         5 . The network device of  claim 1 , wherein the first substring length is 16 bytes, wherein the second substring length is one of 4 bytes and 8 bytes. 
     
     
         6 . The network device of  claim 1 , wherein the signature search hardware module is further configured to:
 compare, in response to the generated indication, the first subject substring to a configuration substring to determine whether the first subject substring matches the configuration substring; and   generate, based on the comparing, an indication that the configuration substring is present in the stream of network traffic.   
     
     
         7 . The network device of  claim 6 , wherein the signature search hardware module is further configured to:
 generate a plurality of indications that a plurality of configurations substrings associated with the signature pattern are present in the stream of network traffic;   compare, based on the generated plurality of indications, the signature pattern to the stream of network traffic to determine that the signature pattern is found in the stream of network traffic; and   generate, based on the determining that the signature pattern is found in the stream of network traffic, an indication that the signature pattern is present in the stream of network traffic.   
     
     
         8 . The network device of  claim 1  further comprising a signature update hardware module for configuring the signature search hardware module to detect the signature pattern, the signature update hardware module is configured to:
 receive, during a configuration operation, the signature pattern to be detected within the stream of network traffic, the signature pattern includes a signature string of data; 
 identify a configuration substring from the signature string, the configuration substring including a plurality of bytes of the signature string; 
 generate a second substring indicator for the configuration substring using the first bitmask on the substring, the first bitmask identifying a first plurality of masked bits of the configuration substring; 
 identify the first counter within the substring indicator memory by using the second substring indicator as an address into the substring indicator memory; and 
 increment the identified first counter. 
 
     
     
         9 . The network device of  claim 8 , further comprising a substring memory hardware module that includes a substring memory space, wherein the signature update hardware module is further configured to:
 generate an address for a substring memory region within the substring memory space using a hashing function on the first and second substring indicators; and   store the configuration substring in the substring memory region using the generated address.   
     
     
         10 . A method for performing hardware-based pattern matching in a network device, the network device including a substring indicatory memory including a first search block and a second search block, the first search block is configured for detection of signature pattern substrings of a first substring length, the second search block is configured for detection of signature pattern substrings of a second substring length that is less than the first substring length, the method comprising:
 receiving the stream of network traffic, the stream of network traffic including a window of bytes equal to the first substring length;   identifying a first subject substring that includes all of the bytes of the window of bytes;   identifying a second subject substring of a length equal to the second substring length and that includes a subset of bytes of the window of bytes;   searching the first search block to determine whether a first signature substring is present in the stream of network traffic;   searching the second search block to determine whether a second signature substring is present in the stream of network traffic; and   generating an indication that the signature pattern may be present in the stream of network traffic based on the searches.   
     
     
         11 . The method of  claim 10 , wherein searching the first block and searching the second block are performed simultaneously during each clock cycle. 
     
     
         12 . The method of  claim 11 , wherein the signature search module is further configured to generate a first substring indicator for the first subject substring and a second substring indicator for the second subject substring prior to the simultaneous searching, wherein searching the first search block includes using the first substring indicator as an address into the first search block, wherein searching the second search block includes using the second substring indicator as an address into the second search block. 
     
     
         13 . The method of  claim 12 , wherein generating the first substring indicator includes using a first bitmask on the first subject substring, the first bitmask identifying a plurality of masked bits of the first subject substring. 
     
     
         14 . The method of  claim 10 , wherein the first substring length is 16 bytes, wherein the second substring length is one of 4 bytes and 8 bytes. 
     
     
         15 . The method of  claim 10  further comprising:
 comparing, in response to the generated indication, the first subject substring to a configuration substring to determine whether the first subject substring matches the configuration substring; and 
 generating, based on the comparing, an indication that the configuration substring is present in the stream of network traffic. 
 
     
     
         16 . The method of  claim 15  further comprising:
 generating a plurality of indications that a plurality of configurations substrings associated with the signature pattern are present in the stream of network traffic; 
 comparing, based on the generated plurality of indications, the signature pattern to the stream of network traffic to determine that the signature pattern is found in the stream of network traffic; and 
 generating, based on the determining that the signature pattern is found in the stream of network traffic, an indication that the signature pattern is present in the stream of network traffic. 
 
     
     
         17 . The method of  claim 10  further comprising:
 receiving, during a configuration operation, the signature pattern to be detected within the stream of network traffic, the signature pattern includes a signature string of data; 
 identifying a configuration substring from the signature string, the configuration substring including a plurality of bytes of the signature string; 
 generating a second substring indicator for the configuration substring using the first bitmask on the substring, the first bitmask identifying a first plurality of masked bits of the configuration substring; 
 identifying the first counter within the substring indicator memory by using the second substring indicator as an address into the substring indicator memory; and 
 incrementing the identified first counter. 
 
     
     
         18 . The method of  claim 17  further comprising:
 generating an address for a substring memory region within a substring memory space using a hashing function on the first and second substring indicators; and 
 storing the configuration substring in the substring memory region using the generated address. 
 
     
     
         19 . A network interface card for performing hardware-based pattern matching in a network device, the network interface card comprising:
 a connector configured to allow the network interface card to electronically couple with the network device;   one or more ports configured to receive a stream of network traffic;   a substring indicator memory; and   a signature search hardware module for detecting a signature pattern within the stream of network traffic, the signature search hardware module is configured to:
 receive the stream of network traffic, the stream of network traffic including a window of bytes equal to the first substring length; 
 identify a first subject substring that includes all of the bytes of the window of bytes; 
 identify a second subject substring of a length equal to the second substring length and that includes a subset of bytes of the window of bytes; 
 search the first search block to determine whether a first signature substring is present in the stream of network traffic; 
 search the second search block to determine whether a second signature substring is present in the stream of network traffic; and 
 generate an indication that the signature pattern may be present in the stream of network traffic based on the searches. 
   
     
     
         20 . The network interface card of  claim 19 , wherein searching the first block and searching the second block are performed simultaneously during each clock cycle, wherein the signature search module is further configured to generate a first substring indicator for the first subject substring and a second substring indicator for the second subject substring prior to the simultaneous searching, wherein searching the first search block includes using the first substring indicator as an address into the first search block, wherein searching the second search block includes using the second substring indicator as an address into the second search block, wherein generating the first substring indicator includes using a first bitmask on the first subject substring, the first bitmask identifying a plurality of masked bits of the first subject substring.