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. A processor-implemented method for string signature scanning, comprising:
 receiving, by a processor, a particular string field comprising a string of data values; 
 scanning, by the processor, the particular string field for a plurality of fingerprints with either a zero or non-zero false positive rate at each possible location for the plurality of fingerprints, where wherein only one fingerprint is selected for each fixed-size signature when the a plurality of signatures includes one or more fixed-size signatures and only one fingerprint is selected for each of one or more fixed-size signature substrings of each variable-size signature when the plurality of signatures includes one or more variable-size signatures, where wherein each of the plurality of fingerprints of the plurality of signatures is one fragment of a particular fixed-size signature or signature substring, the one fragment having a particular location anywhere within the a particular fixed-size signature or signature substring, where wherein two or more of the plurality of fingerprints are at different locations within their fixed-size signatures or fixed-size signature substrings, where wherein location of a plurality of basic units is location of the first basic unit of the plurality of basic units; 
 searching, by the processor, the particular string field for one or more signatures associated with one or more identified fingerprints at each of locations of the one or more signatures, where wherein location of a particular signature associated with a particular fingerprint in a particular string field is determined by location of the particular fingerprint in the particular string field and location of the particular fingerprint in the particular signature; and 
 outputting, by the processor, any identified signatures in the particular string field. 
 
     
     
       2. The processor-implemented method of  claim 1 , where wherein scanning the particular string field for the plurality of fingerprints of the plurality of signatures is performed including in one or more shadow spaces, where wherein the shadow spaces are spaces that introduce some ambiguity to original space such that one single basic unit in a particular shadow space corresponds to one or more single basic units in the original space, where wherein the original space is a space where all basic units are in original format without any mapping. 
     
     
       3. The processor-implemented method of  claim 1 , where wherein scanning the particular string field for the plurality of fingerprints of the plurality of signatures includes using one or more hash values of a fragment of the particular string field to look up one or more of one or more hash tables and one or more bloom filters for the plurality of fingerprints. 
     
     
       4. The processor-implemented method of  claim 3 , where wherein the one or more of the one or more hash tables and the one or more bloom filters includes using one or both of a hash value de-multiplexer and a hash key length de-multiplexer. 
     
     
       5. The processor-implemented method of  claim 1 , where wherein scanning the particular string field for the plurality of fingerprints of the plurality of signatures including includes using one or more finite automata (FA). 
     
     
       6. The processor-implemented method of  claim 1 , where wherein scanning the particular string field for the plurality of fingerprints of the plurality of signatures including includes using one or more content addressable memories (CAM). 
     
     
       7. The processor-implemented method of  claim 1 , where wherein the plurality of fingerprints are fully specified. 
     
     
       8. The processor-implemented method of  claim 1 , where wherein the plurality of fingerprints are fully specified either originally or after being mapped into one or more shadow spaces, where wherein the shadow spaces are spaces that introduce some ambiguity to original space such that one basic unit in a particular shadow space corresponds to one or more basic units in the original space, where wherein the original space is a space where all basic units are in original format without any mapping. 
     
     
       9. The processor-implemented method of  claim 1 , where wherein a plurality of lengths are selected for the plurality of fingerprints of the plurality of signatures. 
     
     
       10. The processor-implemented method of  claim 9 , where wherein the plurality of lengths are either linear or exponential. 
     
     
       11. The processor-implemented method of  claim 1 , where wherein scanning the particular string field for the plurality of fingerprints further comprise scanning the particular string field for a plurality of fingerprint segments of the plurality of fingerprints and synthesizing identified fingerprint segments into any fingerprint matches, where wherein each of one or more of the plurality of fingerprints is decomposed into a plurality of fingerprint segments. 
     
     
       12. The processor-implemented method of  claim 11 , where wherein all of the plurality of fingerprint segments have a same size. 
     
     
       13. The processor-implemented method of  claim 1 , where wherein one or more additional fingerprints are selected for each fixed-size signature when the plurality of signatures includes one or more fixed-size signatures and one or more additional fingerprints are selected for each of one or more fixed-size signature substrings of each variable-size signature when the plurality of signatures includes the one or more variable-size signature, where signatures, wherein each successive fingerprint of a particular fixed-size signature or signature substring having a first basic unit in a scanning direction that is shifted one or more units from the previous fingerprint of the particular fixed-size signature or signature substrings such that the number of fingerprints for the particular fixed-size signature or signature substrings is equal to a step size for a signature scanning operation and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, where wherein the step size for a signature scanning operation is number of one or more basic scan units advanced in the string field for a signature scanning operation and the step size is constant for all signature scanning operations. 
     
     
       14. The processor-implemented method of  claim 1 , where wherein searching the particular string field for the one or more signatures associated with the one or more identified fingerprints includes comparing the one or more signatures with the corresponding fragments of the particular string field either entirely or partially. 
     
     
       15. The processor-implemented method of  claim 1 , where wherein searching the particular string field for the one or more signatures associated with the one or more identified fingerprints includes comparing the one or more signatures with the corresponding fragments of the particular string field either entirely or partially with one or more mask bits including one or more mask bits for specifying one or more of a don't care, a case-sensitivity, a negation, a predefined range, a logic operation, and an arbitrary range. 
     
     
       16. The processor-implemented method of  claim 1 , where wherein searching the particular string field for the one or more signatures associated with the one or more identified fingerprints includes using one or more finite automata (FA). 
     
     
       17. The processor-implemented method of  claim 1 , where wherein searching the particular string field for the one or more signatures associated with the one or more identified fingerprints at each of locations of the one or more signatures further comprising comprises:
 searching, by the processor, the particular string field for the one or more fixed-size signatures or signature substrings associated with one or more identified fingerprints at each of locations of the one or more fixed-size signatures or signature substrings, where wherein location of a particular fixed-size signature or signature substring associated with a particular fingerprint in a particular string field is determined by location of the particular fingerprint in the string field and location of the particular fingerprint in the particular fixed-size signature or signature substring; and 
 searching, by the processor, the particular string field for one or more variable-size signatures associated with one or more identified fixed-size signature substrings at each of locations where the one or more fixed-size signature substrings are found. 
 
     
     
       18. The processor-implemented method of  claim 17 , where wherein searching, by the processor, the particular string field for the one or more fixed-size signatures or signature substrings includes comparing the one or more fixed-size signatures or fixed-size signature substrings with the corresponding fragments of the particular string field either entirely or partially. 
     
     
       19. The processor-implemented method of  claim 17 , where wherein searching the particular string field for the one or more fixed-size signatures or signature substrings includes comparing the one or more fixed-size signatures or fixed-size signature substrings with the corresponding fragments of the particular string field either entirely or partially with one or more mask bits including one or more mask bits for specifying one or more of a don't care, a case-sensitivity, a negation, a pre-defined range, a logic operation, and an arbitrary range. 
     
     
       20. The processor-implemented method of  claim 17 , where wherein searching the particular string field for the one or more fixed-size signatures or signature substrings includes using one or more finite automata (FA). 
     
     
       21. The processor-implemented method of  claim 17 , where wherein searching the particular string field for the one or more variable-size signatures associated with the one or more identified fixed-size signature substrings includes one or more of checking location information of each of the one or more identified fixed-size signature substrings, verifying identification of each of the one or more variable-size signatures, and updating a signature synthesis state for the one or more variable-size signatures. 
     
     
       22. The processor-implemented method of  claim 21 , where wherein checking the location information of each of the one or more identified fixed-size signature substrings includes checking one or more of an order, a distance or distance range to the next fixed-size signature substring, and a last flag. 
     
     
       23. The processor-implemented method of  claim 17 , where wherein searching the particular string field for the one or more variable-size signatures includes using one or more finite automata (FA). 
     
     
       24. The processor-implemented method of  claim 23 , where wherein each of the one or more finite automata (FA) is for one or more variable-size signatures. 
     
     
       25. The processor-implemented method of  claim 17 , where wherein the fixed-size signature substrings of the variable-size signatures are as long as possible. 
     
     
       26. The processor-implemented method of  claim 17 , where wherein one or more variable-size substrings of the variable-size signatures is other than arbitrary basic units of arbitrary length. 
     
     
       27. The processor-implemented method of  claim 1 , where wherein scanning the particular string field for the plurality of fingerprints of the plurality of signatures is performed in original space, where and wherein the original space is a space where all basic units are in original format without any mapping. 
     
     
       28. The processor-implemented method of  claim 2 , where wherein a shadow space is a space after changing all the characters in both upper and lower cases in the original space to a same case or all numerical digits from 0 to 9 in the original space to a same digit or both “space” and in the original space to one of a “space” or “_”. 
     
     
       29. A string signature scanning system used to inspect an incoming data stream, said data stream comprising packet source address information, destination address information, transmission sequence information, and payload content, the system comprising:
 a non-transitory machine-readable storage device including a computer program; and 
 one or more processors or one or more special purpose logic circuits that execute the computer program, and perform operations including providing one or more modules including:
 a first set of scan engines that includes either one scan engine or a plurality of parallel identical scan engines which scan a string field comprising a string of data values for a first set of one or more signatures using a first scan step size of single scan engine, and identify any of the first set of signatures anywhere within the string field; and 
 a second set of scan engines that includes a plurality of parallel identical scan engines which scan the string field for a second set of one or more signatures using a second scan step size of single scan engine, and identify any of the second set of signatures anywhere within the string field;,  
 
 wherewherein the first scan step size of single scan engine is larger than the second scan step size of single scan engine while the first set of scan engines has a smaller number of scan engines than the second set of scan engines such that a first product of the first scan step size of single scan engine and the number of scan engines of the first set of scan engines is the same as a second product of the second scan step size of single scan engine and the number of scan engines of the second set of scan engines, wherewherein the scan step size of single scan engine is a number of one or more basic scan units advanced in the string field for a signature scanning operation when a single scan engine is used and the scan step size of single scan engine is constant for all signature scanning operations, whereand wherein the first product isand second product result from a multiplication operation. 
 
     
     
       30. The method string signature scanning system of  claim 29 , where wherein the plurality of parallel identical scan engines of a particular set of scan engines covering a plurality of sets of non-overlapping and interleaving locations in the particular string field such that the resultant scan step size of the set of scan engines is a product of the scan step size of single scan engine of the set of scan engines and the number of scan engines of the set of scan engines. 
     
     
       31. A string signature scanning system, the system comprising:
 a non-transitory machine-readable storage device including a computer program; and 
 one or more processors or one or more special purpose logic circuits that execute the computer program, and perform operations including providing one or more modules including: 
 a fingerprint scan engine which scans a string field for a plurality of non-hashed fingerprints of a plurality of signatures with either a zero or non-zero false positive rate, where wherein only one first fingerprint is selected for each fixed-size signature when the plurality of signatures includes one or more fixed-size signatures and only one second fingerprint is selected for each of one or more fixed-size signature substrings of each variable-size signature when the plurality of signatures includes one or more variable-size signatures, where wherein each of the plurality of fingerprints of the plurality of signatures is one fragment of a particular fixed-size signature or signature substring, the one fragment having a particular location anywhere within the particular fixed-size signature or signature substring, where wherein two or more of the plurality of fingerprints are at different locations within their fixed-size signatures or fixed-size signature substrings, where wherein a location of a plurality of basic units is the location of the first basic unit of the plurality of basic units; and 
 a signature search engine which searches the string field for one or more signatures associated with one or more identified fingerprints in the event the one or more fingerprints are identified by the fingerprint scan engine; 
 wherewherein the fingerprint scan engine and the signature search engine are connected in serial fashion and formedcombined to form a multiple-pipeline stage scanning system such that the fingerprint scan engine scans the string field for the plurality of fingerprints in an earlya first pipeline stage and the signature search engine searches the string field for the one or more signatures associated with the one or more identified fingerprints in a later pipeline stage. 
 
     
     
       32. The string signature scanning system of  claim 31 , where wherein the fingerprint scan engine scans the string field for the plurality of fingerprints in original space, where wherein the original space is a space where all basic units are in original format without any mapping. 
     
     
       33. The string signature scanning system of  claim 31 , where wherein the fingerprint scan engine scans the string field for the plurality of fingerprints including in one or more shadow spaces, where the shadow spaces are spaces that introduce some ambiguity to original space such that one single basic unit in a particular shadow space corresponds to one or more single basic units in the original space, where the original space is a space where all basic units are in original format without any mapping. 
     
     
       34. The string signature scanning system of  claim 33 , where wherein a shadow space is a space after changing all the characters in both upper and lower cases in the original space to a same case or all numerical digits from 0 to 9 in the original space to a same digit or both “space” and “-” in the original space to one of a “space” or “-”. 
     
     
       35. The string signature scanning system of  claim 31 , where wherein the fingerprint scan engine includes one or more hash engines and one or more of one or more hash tables and one or more bloom filters. 
     
     
       36. The string signature scanning system of  claim 35 , where wherein the one or more of one or more hash tables and one or more bloom filters includes using one or both of a hash value de-multiplexer and a hash key length de-multiplexer. 
     
     
       37. The string signature scanning system of  claim 31 , where wherein the fingerprint scan engine includes one or more finite automata (FA). 
     
     
       38. The string signature scanning system of  claim 31 , where wherein the fingerprint scan engine includes one or more content addressable memories (CAM). 
     
     
       39. The string signature scanning system of  claim 31 , where wherein the plurality of fingerprints are fully specified. 
     
     
       40. The string signature scanning system of  claim 31 , where wherein the plurality of fingerprints are fully specified either originally or after being mapped into one or more shadow spaces, where the shadow spaces are spaces that introduce some ambiguity to original space such that one basic unit in a particular shadow space corresponds to one or more basic units in the original space, where the original space is a space where all basic units are in original format without any mapping. 
     
     
       41. The string signature scanning system of  claim 31 , where wherein a plurality of lengths are selected for the plurality of fingerprints of the plurality of signatures. 
     
     
       42. The string signature scanning system of  claim 41 , where wherein the plurality of lengths are either linear or exponential. 
     
     
       43. The string signature scanning system of  claim 31 , where wherein the fingerprint scan engine comprises a fingerprint segment scan engine and a fingerprint synthesis engine. 
     
     
       44. The string signature scanning system of  claim 43 , where wherein all fingerprint segments have a same size. 
     
     
       45. The string signature scanning system of  claim 31 , where wherein one or more additional fingerprints are selected for each fixed-size signature when the plurality of signatures includes one or more fixed-size signatures and one or more additional fingerprints are selected for each of one or more fixed-size signature substrings of each variable-size signature when the plurality of signatures includes one or more variable-size signature, where wherein each successive fingerprint of a particular fixed-size signature or signature substring having a first basic unit in a scanning direction that is shifted one or more units from the previous fingerprint of the particular fixed-size signature or signature substrings such that the number of fingerprints for the particular fixed-size signature or signature substrings is equal to a step size for a signature scanning operation and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, where wherein the step size for a signature scanning operation is number of one or more basic scan units advanced in the string field for a signature scanning operation and the step size is constant for all signature scanning operations. 
     
     
       46. The string signature scanning system of  claim 31 , where wherein the signature search engine compares the one or more signatures associated with one or more identified fingerprints with the corresponding fragments of the string field either entirely or partially. 
     
     
       47. The string signature scanning system of  claim 31 , where wherein the signature search engine compares the one or more signatures associated with one or more identified fingerprints with the corresponding fragments of the string field either entirely or partially with one or more mask bits including one or more mask bits for specifying one or more of a don't care, a case-sensitivity, a negation, a pre-defined range, a logic operation, and an arbitrary range. 
     
     
       48. The string signature scanning system of  claim 31 , where wherein the signature search engine includes one or more finite automata (FA). 
     
     
       49. The string signature scanning system of  claim 31 , where wherein the signature search engine further comprising:
 a fixed-size signature search engine which searches the string field for one or more fixed-size signatures or signature substrings associated with one or more identified fingerprints in the event the one or more fingerprints are identified by the fingerprint scan engine; and 
 a variable-size signature search engine which searches the string field for one or more variable-size signatures associated with one or more identified fixed-size signature substrings in the event the one or more fixed-size signature substrings are identified by the fixed-size signature search engine. 
 
     
     
       50. The string signature scanning system of  claim 49 , where wherein the fixed-size signature search engine compares the one or more fixed-size signatures or signature substrings with the corresponding fragments of the particular string field either entirely or partially. 
     
     
       51. The string signature scanning system of  claim 49 , where wherein the fixed-size signature search engine compares the one or more fixed-size signatures or signature substrings with the corresponding fragments of the particular string field either entirely or partially with one or more mask bits including one or more mask bits for specifying one or more of a don't care, a case-sensitivity, a negation, a pre-defined range, a logic operation, and an arbitrary range. 
     
     
       52. The string signature scanning system of  claim 49 , where wherein the fixed-size signature search engine includes one or more finite automata (FA). 
     
     
       53. The string signature scanning system of  claim 49 , where wherein the variable-size signature search engine performs one or more of checking location information of each of the one or more identified fixed-size signature substrings, verifying identification of each of the one or more variable-size signatures, and updating a signature synthesis state for the one or more variable-size signatures. 
     
     
       54. The string signature scanning system of  claim 53 , where wherein checking the location information of each of the one or more identified fixed-size signature substrings includes checking one or more of an order, a distance or distance range to the next fixed-size signature substring, and a last flag. 
     
     
       55. The string signature scanning system of  claim 49 , where wherein the variable-size signature search engine includes one or more finite automata (FA). 
     
     
       56. The string signature scanning system of  claim 55 , where wherein each of the one or more finite automata (FA) is for one or more variable-size signatures. 
     
     
       57. The string signature scanning system of  claim 49 , where wherein the fixed-size signature substrings of the variable-size signatures are as long as possible. 
     
     
       58. The string signature scanning system of  claim 49 , where wherein one or more variable-size substrings of the variable-size signatures is other than arbitrary basic units of arbitrary length. 
     
     
       59. The string signature scanning system of claim 31, wherein the processor comprises multiple processing devices. 
     
     
       60. The string signature scanning system of claim 31, wherein the processor is configured to perform parallel processing. 
     
     
       61. The string signature scanning system of claim 31, wherein the hashed data value is stored substantially in an on-chip memory comprising a non-transitory machine-readable volatile memory device. 
     
     
       62. The string signature scanning system of claim 31, wherein the hashed data value is stored substantially in an off-chip memory comprising a non-transitory machine-readable volatile memory device. 
     
     
       63. The string signature scanning system of claim 31, wherein the hashed data value is stored in a table located at least partially on an on-chip memory of the one or more processors or one or more special purpose logic circuits. 
     
     
       64. The string signature scanning system of claim 31, wherein the one or more processors comprises at least one of an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA), system on a chip (SoC), and central processing unit (CPU).