Fast signature scan

Abstract

Systems and methods for scanning signatures in a string field. In one implementation, the invention provides a method for signature scanning. The method includes receiving a particular string field, scanning the particular string field for a plurality of signatures using a larger scan step size, scanning the particular string field for the remaining signatures that are shorter than what can be scanned by the larger scan step size separately either using the same scanning method but a smaller scan step size or using a different scan method and the same or a smaller scan step size, and outputting any identified signatures in the particular string field.

What is claimed is: 
     
         1 . An electronic system for inspecting a string field and matching it with a targeted string signature, comprising:
 a first chip;   a memory located on said first chip;   a processor located on said first chip; and   a matching engine of said processor, wherein after said processor receives an incoming string field, for a plurality of shifted scan locations in the incoming string field, said matching engine is configured to:
 (a) identify an unhashed fragment of the incoming string field at each of the plurality of shifted scan locations, each said unhashed fragment comprising a substring of the incoming string field, wherein at least one of said plurality of unhashed fragments is of a size that is smaller than the incoming string field; 
 (b) derive at least one hash value for each said unhashed fragment that has a size smaller than the incoming string field; 
 (c) scan a plurality of table values, at least one table value representing the hash value of a fingerprint of one of a first targeted fixed-size string signature, said fingerprint located anywhere within the first targeted fixed-size string signature and of a size that is less than the size of the first targeted fixed-size string signature; 
 (d) utilize the at least one derived hash value for each said fragment that has a size smaller than the incoming string field and the plurality of table values as a first-stage determination on said first chip of a potential match between the incoming string field and the first targeted fixed-size string signature; and 
 (e) based on the first-stage determination, compare a substring of the incoming string field of a size that is smaller than the incoming string field to a pattern representing a text string of the first targeted fixed-size string signature, in a second-stage determination on said first chip of whether there is a potential match between the incoming string field and the targeted fixed-size string signature. 
   
     
     
         2 . The system of  claim 1 , wherein the first targeted fixed-size string signature is a first fixed-sized string signature and the fingerprint is at a location within the first fixed-size string signature and smaller than the first fixed-sized string signature. 
     
     
         3 . The system of  claim 1 , wherein the first targeted fixed-size string signature is a first fixed-sized string signature and the fingerprint is a first substring of the first fixed-sized string signature, and wherein the fingerprint is at a location within the first substring and is of a size that is smaller than the first substring. 
     
     
         4 . The system of  claim 1 , wherein the fingerprint is one of a plurality of fingerprints, each of said plurality of fingerprints located at different locations within the first fixed-size signature. 
     
     
         5 . The system of  claim 1 , wherein the fingerprint is one of a plurality of fingerprints, each of said plurality of fingerprints located at different locations within a first substring of the first fixed-sized string signature. 
     
     
         6 . The system of  claim 1 , wherein the first-stage determination precedes the second-stage determination in a pipelined process. 
     
     
         7 . The system of  claim 1 , wherein the pattern representing a text string of the first targeted fixed-size string signature is an expression comprising a combination of at least one alphanumeric character and at least one wildcard symbol. 
     
     
         8 . The system of  claim 1 , wherein at least one of the first-stage determination and second-stage determination includes a non-deterministic finite automaton (NFA) based comparison. 
     
     
         9 . The system of  claim 1 , wherein, as part of said table access and first-stage determination, said matching engine does not retrieve data from a non-transitory storage device. 
     
     
         10 . The system of  claim 1 , wherein said matching engine further comprises a first sub-engine responsible for executing the first-stage determination and a second sub-engine responsible for the second-stage determination, and, wherein, in the case of a potential match, the first sub-engine passes the incoming string field to the second sub-engine. 
     
     
         11 . The system of  claim 1 , wherein a data stream comprises a data packet comprising the incoming string field, the data packet further comprising packet source address information, destination address information, transmission sequence information, and payload content, and wherein said unhashed fragment excludes packet source address information, destination address information, and transmission sequence information. 
     
     
         12 . The system of  claim 11 , wherein when the incoming string field contains the first targeted fixed-size string signature, the incoming string field is identified as malicious. 
     
     
         13 . A digital electronic circuitry used to inspect a string field and match it with a targeted string signature, comprising:
 (a) a receiving circuit of a processor located on a first chip that receives a plurality of incoming string fields, and   (b) a finding circuit of said processor that finds a plurality of unhashed fragments associated with a particular incoming string field of the plurality of incoming string fields, wherein:
 the finding comprises finding an unhashed fragment at least a first shifted scan location, the unhashed fragment comprising a substring of a particular incoming string field, the unhashed fragment is of a size that is smaller than the particular incoming string field; 
   (c) a deriving circuit of said processor that derives a hash value for the found unhashed fragment;   (d) a look-up circuit of said processor that looks up a table stored substantially in a memory located in said first chip to find at least one table value of a plurality of table values, said at least one table value representing a hash value of an otherwise unhashed fingerprint of a targeted string signature, wherein:
 the targeted string signature is a targeted fixed-size signature or a targeted variable-size signature, the unhashed fingerprint is located within the targeted string signature and is of a size that is less than the size of the targeted string signature; 
   (e) a determining circuit of said processor that determines a potential match between the particular incoming string field and the targeted string signature based upon the derived hash value and the at least one table value; and   (f) a comparing circuit of said processor that, based on the determining, compares at least one of the particular incoming string field or a substring of the particular incoming string field that is smaller in size than the particular incoming string field to a pattern representing a text string of the targeted string signature, to determine, based in whole or in part on the use by the processor of a non-deterministic finite automaton (NFA) based-matching, whether the particular incoming string field matches in whole or in part the targeted string signature, wherein the pattern representing the text string of the targeted string signature is an expression comprising a combination of at least one of a first alphanumeric character, and at least one of a second alphanumeric character, and a wildcard symbol.   
     
     
         14 . The digital electronic circuitry of  claim 13 , wherein the circuit of said processor that determines a potential match between the particular incoming string field and the targeted string signature based upon the derived hash value and the at least one table value is a first engine, and the circuit that compares at least one of the particular incoming string field or a substring of the particular incoming string field that is smaller in size than the particular incoming string field to a pattern representing a text string of the targeted string signature, to determine, based in whole or in part on the use by the processor of a non-deterministic finite automaton (NFA) based-matching, whether the particular incoming string field matches in whole or in part the targeted string signature, is a second engine. 
     
     
         15 . The digital electronic circuitry of  claim 14 , wherein, based on the determining, said first engine passes at least one of the particular incoming string field or a substring of the particular incoming string field that is smaller in size than the particular incoming string field to said second engine. 
     
     
         16 . The digital electronic circuitry of  claim 14 , wherein the unhashed fingerprint is of a targeted variable-size signature located within the targeted string signature at an undefined location. 
     
     
         17 . The digital electronic circuitry of  claim 14 , wherein said receiving circuit, said finding circuit, said deriving circuit, said look-up circuit, said determining circuit, and said comparing circuit comprise at least one of an integrated circuit, ASIC and FPGA. 
     
     
         18 . The digital electronic circuitry of  claim 17 , wherein a data stream comprises a data packet comprising the particular incoming string field, the data packet further comprising packet source address information, destination address information, transmission sequence information, and payload content, and wherein said unhashed fragment excludes packet source address information, destination address information, and transmission sequence information. 
     
     
         19 . The digital electronic circuitry of  claim 18 , wherein when the particular incoming string field contains the targeted string signature, the incoming string field is identified as malicious. 
     
     
         20 . An electronic system for inspecting a string field and matching it with a targeted string signature, comprising:
 (a) a receiving circuit located on a first chip that receives a plurality of incoming string fields;   (b) a finding circuit located on said first chip that finds an unhashed fragment associated with a incoming string field of the plurality of incoming string fields for a plurality of shifted scan locations in the incoming string field, wherein:
 the finding circuit finds at least a first unhashed fragment at a first shifted scan location, 
 the first unhashed fragment comprising a substring of the incoming string field, and 
 the first unhashed fragment is of a size that is smaller than the incoming string field; 
   (c) a deriving circuit located on said first chip that derives a hash value for the first unhashed fragment;   (d) a look-up circuit located on said first chip that looks up a plurality of table values located substantially in memory located on said first chip, at least one table value representing a hash value of an otherwise unhashed fingerprint of a targeted string signature, wherein:
 the targeted string signature is a targeted fixed-size signature or a targeted variable-size signature, the unhashed fingerprint is located within the targeted string signature and is of a size that is less than the size of the targeted string signature, 
   (e) a determining circuit located on said first chip further comprising a first engine, wherein said first engine is used to determine a potential match between the incoming string field and the targeted string signature based upon the hash value and the at least one table value; and   (f) a comparing circuit located on said first chip further comprising a second engine, wherein said second engine is used to receive from the determining circuit the incoming string field based on the determining of the potential match, the comparing circuit comparing, as part of the pipelined process, at least one of the incoming string field or a subpart thereof to a pattern representing a text string of the targeted string signature, to determine based in whole or in part a non-deterministic finite automaton (NFA) based-matching whether the incoming string field matches in whole or in part the targeted string signature, wherein the pattern representing the text string of the targeted string signature is an expression comprising a combination of (i) at least one alphanumeric character, and (ii) at least one of a second alphanumeric character and a wildcard symbol,   and wherein said receiving circuit, said finding circuit, said deriving circuit, said look-up circuit, said determining circuit, and said comparing circuit are each located on said first chip, and collectively further comprise at least one of a single integrated circuit, microprocessor and processor.