FAST SIGNATURE SCAN

• US 20090100055A1
• Filed: 10/20/2008
• Published: 04/16/2009
• Est. Priority Date: 11/07/2003
• Status: Active Grant

• Current Assignee: Light Speed Microelectronics, LLC
• Original Assignee: Qiang Wang
• Inventors: Wang, Qiang
• Granted Patent: US 7,870,161 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: G06V 10/70 using pattern recognition or machine learning optical pattern recognition or electronic computations therefor G06V10/88
• CPC Class Codes: G06V 40/1335 Combining adjacent partial images (e.g. slices) to create a composite input or reference pattern; Tracking a sweeping finger movement
• CPC Class Codes: G06V 40/1365 Matching; Classification
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

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 processing one or more signatures into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature or signature substring such that the number of fingerprints for each fixed-size signature or signature substring 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, receiving a particular string field, identifying any signatures included in the particular string field including scanning for the fingerprints for each scan step size and searching for the follow-on search data structures at the locations where one or more fingerprints are found, and outputting any identified signatures.

Claims

1. A method for string signature scanning, comprising:

processing one or more signatures into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature or each fixed-size signature substring of a variable-size signature, the one or more fingerprints including a J^th fingerprint for a particular fixed-size signature or signature substring having a first basic unit in a scanning direction at a location within the particular fixed-size signature or signature substring that has a remainder equaling J when divided by a step size for a signature scanning operation such that the number of fingerprints is equal to the step size for signature scanning and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, where each fingerprint includes one or more fragments of a particular fixed-size signature or signature substring, the one or more fragments having particular locations anywhere within the particular fixed-size signature or signature substring;

receiving a particular string field comprising a string of data values;

identifying any signatures included in the particular string field including scanning the particular string field for the one or more fingerprints associated with the one or more signatures for each scan step size and searching the particular string field for the one or more follow-on search data structures at the locations where one or more fingerprints are found; and

outputting any identified signatures in the particular string field.

2. The method of claim 1, where a plurality of fingerprints are selected for each fixed-size signature or signature substring and the scanning includes scanning the particular string field for a plurality of fingerprints associated with the one or more signatures including two or more fingerprints in parallel for each scan step size.

3. The method of claim 1, where each fingerprint of the one or more fingerprints of a particular signature is fully specified either originally or after mapping them into one or more shadow spaces where the shadow spaces are spaces that correspond to a generalized format from the original space where the shadow spaces are spaces that introduce some ambiguity to the original space such that a single fingerprint in a particular shadow space corresponds to one or more fingerprints in the original space.

4. The method of claim 1, where scanning for the one or more fingerprints associated with the one or more signatures further includes scanning either using one or more of one or more hash tables and one or more bloom filters with or without one or more of a hash value de-multiplexer and a fingerprint length de-multiplexer or using one or more of one or more content addressable memories (CAM) and one or more finite automata (FA).

5. The method of claim 1, where the one or more fingerprints are selected such that their lengths are limited to a length list that covers one or more lengths within one or more ranges of lengths providing multiple resolution fingerprint scanning and a number of unique fingerprint lengths is less than a number of unique signature lengths for a plurality of signatures, and the scanning comprises scanning the particular string field for a plurality of fingerprints for the plurality of signatures including two or more fingerprints of a same length in parallel for each scan step size.

6. The method of claim 1, further comprising:

decomposing each fingerprint of a plurality of fingerprints for a plurality of signatures into one or more fingerprint segments such that a number of unique fingerprint segment lengths is less than a number of unique fingerprint lengths for the plurality of signatures;

scanning the particular string field for the plurality of fingerprint segments including two or more fingerprint segments in parallel; and

synthesizing identified fingerprint segments into any fingerprint matches using one or more of a fingerprint segment bitmap specifying one or more possible locations within any fingerprints for a particular fingerprint segment, fingerprint length information specifying one or more possible fingerprint lengths for a particular fingerprint segment, and one or more finite automata (FA) for the plurality of fingerprint segments.

7. The method of claim 1, further comprising:

constructing a differential search structure using one or more distinct basic units among a plurality of fixed-size signatures or signature substrings associated with a fingerprint; and

searching the particular string field for the one or more follow-on search data structures including searching for a plurality of fixed-size signatures or signature substrings associated with an identified fingerprint differentially.

8. The method of claim 1, further comprising:

encoding each of one or more fixed-size signatures or signature substrings 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, the one or more mask bits including one or more of one or more per basic unit or sub-basic unit mask bits, one or more segment mask bits, and one or more fixed-size signature or signature substring mask bits; and

searching the particular string field for the one or more follow-on search data structures including searching for the mask encoded fixed-size signatures or signature substrings.

9. The method of claim 1, further comprising:

decomposing each variable-size signature of the one or more signatures into a plurality of fixed-size signature substrings and one or more variable-size signature substrings and building either a static signature synthesis rule database that comprises location information of each fixed-size signature substring including an order and a distance range to the next fixed-size signature substrings with or without a description of a variable-size signature substring between each pair of consecutive fixed-size signature substrings or one or more finite automata (FA) in which each fixed-size signature substring is consumed as a whole as an input symbol;

identifying any signatures included in the particular string field including scanning the particular string field for the plurality of fixed-size signatures or signature substrings and synthesizing identified fixed-size signature substrings into any variable-sized signatures using either the static signature synthesis rule database or the one or more finite automata (FA) of fixed-size signature substrings at the location where one or more fixed-size signature substrings are identified.

10. A method for string signature scanning, comprising:

selecting one or more fixed-size signatures for each of one or more string objects;

receiving a particular string field comprising a string of data values;

identifying any string objects included the particular string field including scanning the particular string field for the one or more fixed-size signatures associated with the one or more string objects for each step size for a signature scanning operation where the scan step size is equal to the number of the one or more fixed-size signatures for each string object; and

outputting any identified string objects in the particular string field.

11. The method of claim 10, a plurality of fixed-size signatures being selected for each of the one or more string objects, the plurality of fixed-size signatures for a particular string object including a J^th fixed-size signature having a first basic unit in a scanning direction at a location within the particular string object that has a remainder equaling J when divided by a step size for a signature scanning operation such that a number of fixed-size signatures for the particular string object is equal to the step size for a signature scanning operation and the particular string object is identifiable at any location within any string fields to be scanned, and identifying any string objects included the particular string field including scanning the particular string field for the plurality of fixed-size signatures associated with the one or more string objects including two or more fixed-size signatures in parallel for each scan step size.

12. The method of claim 11, further comprising:

selecting a plurality of variable-size signatures based a plurality of non-overlapping, ordered sets of the plurality of fixed-size signatures for each of the one or more string objects, each of the plurality of variable-size signatures including a fixed-size signature from each set of fixed-size signatures and a variable-size string linked each pair of consecutive fixed-size signatures such that the number of signatures for each string object is equal to Sⁿ, where S is the scan step size or the number of fixed-size signatures in each of the sets and n is the number of the sets; and

identifying any string objects included the particular string field including scanning the particular string field for the fixed-size signature substrings of the plurality of variable-size signatures associated with the one or more string objects for each scan step size and synthesizing identified fixed-size signature substrings into any variable-size signatures at the locations where one or more fixed-size signature substrings are found.

13. The method of claim 10, further comprising:

processing the one or more fixed-size signatures for the one or more string objects into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature, the plurality of fingerprints for a particular string object including a J^th fingerprint having a first basic unit in a scanning direction at a location within the particular string object that has a remainder equaling J when divided by a step size for a signature scanning operation such that the number of fingerprints for the particular string object is equal to the step size for a signature scanning operation and the particular string object is identifiable at any location within any string fields to be scanned, where each fingerprint includes one or more fragments of a particular fixed-size signature of the one or more fixed-size signatures for the particular string object, the one or more fragments having particular locations anywhere within the particular fixed-size signature; and

identifying any string objects included the particular string field including scanning the particular string field for the plurality of fingerprints associated with the one or more string objects including two or more fingerprints in parallel for each scan step size and searching the particular string field for the follow-on search data structures at the locations where one or more fingerprints are found.

14. The method of claim 13, further comprising:

selecting a plurality of variable-size signatures based on one or more non-overlapping, ordered sets of the one or more fixed-size signatures for each of the one or more string objects, each of the plurality of variable-size signatures including a fixed-size signature from each set of fixed-size signatures and a variable-size string linked each pair of consecutive fixed-size signatures such that the number of signatures for each string object is equal to the product of the sizes of the plurality of sets of fixed-size signatures; and

identifying any string objects included in the particular string field including scanning the particular string field for the plurality of fingerprints associated with the one or more string objects including two or more fingerprints in parallel for each scan step size and searching the particular string field for the follow-on search data structures at the locations where one or more fingerprints are found.

15. The method of claim 10, further comprising:

decomposing each signature of a plurality of signatures into one or more signature segments;

scanning the particular string field for the plurality of signature segments for the plurality of signatures including two or more signature segments in parallel using one or more of one or more hash tables and one or more bloom filters with or without one or more of a hash value de-multiplexer and a fingerprint length de-multiplexer;

synthesizing identified signature segments into any signature matches using one or more of a signature segment bitmap specifying one or more possible locations within any signatures for a particular signature segment, signature length information specifying one or more possible signature lengths for a particular signature, and one or more finite automata (FA) for the plurality of signature segments.

16. A string signature scanning system, the system comprising:

a machine-readable storage device including a computer program product; and

one or more processors operable to execute the computer program product, and perform operations including providing one or more modules including;

a signature pre-processing module operable to process one or more signatures into one or more formats that include one or more fingerprints and one or more follow-on search data structures for each fixed-size signature or each fixed-size signature substring of a variable-size signature, the one or more fingerprints including a J^th fingerprint for a particular fixed-size signature or signature substring having a first basic unit in a scanning direction at a location within the particular fixed-size signature or signature substring that has a remainder equaling J when divided by a step size for a signature scanning operation such that the number of fingerprints is equal to the step size for signature scanning and the particular fixed-size signature or signature substring is identifiable at any location within any string fields to be scanned, where each fingerprint includes one or more fragments of a particular fixed-size signature or signature substring, the one or more fragments having particular locations anywhere within the particular fixed-size signature or signature substring;

a scan pre-processing engine operable to process an input string field comprising a string of data values into one or more formats for scanning;

a fingerprint scan engine operable to identify one or more fingerprints associated with one or more signatures on the input string field, the identifying including scanning the input string field for the one or more fingerprints associated with the one or more signatures for each scan step size;

a fixed-size signature search engine operable to identify fixed-size signatures or fixed-size substrings of variable-size signatures for the identified fingerprints; and

a variable-size signature search engine operable to identify variable-size signatures including synthesizing identified fixed-size substrings of variable-size signatures into any variable-size signatures.

17. The system of claim 16, one or more fingerprints of one or more lengths being scanned by one or more fingerprint scan engines that have a same scan step size, each of the one or more fingerprint scan engines either covering one or more non-overlapping, interleaving locations in the input string field such that the resultant scan step size of the one or more fingerprint scan engines is the product of the number of the one or more fingerprint scan engines and the original scan step size of a single fingerprint scan engine or covering one or more partially overlapping, interleaving locations in the input string field such that the resultant scan step size of the one or more fingerprint scan engines is between the original scan step size of a single fingerprint scan engine and the product of the number of the one or more fingerprint scan engines and the original scan step size of a single fingerprint scan engine.

18. The system of claim 16, each of one or more fingerprints of one or more lengths being decomposed into one or more fingerprint segments and the plurality of fingerprint segments for the one or more fingerprints being scanned by one or more fingerprint scan engines, each of the one or more fingerprint scan engines including a fingerprint synthesis engine that is operable to synthesize a plurality of fingerprint segments into any fingerprint matches either in parallel or sequentially using either one or more of a fingerprint segment bitmap and fingerprint length information or one or more of one or more content addressable memories (CAM) and one or more finite automata (FA).

19. The system of claim 16, one or more memories used for one or more fingerprint scan engines covering one or more fingerprints that are shorter in average having the same speed as or are faster than one or more memories used for one or more fingerprint scan engines covering one or more fingerprints that are longer in average, and one or more memories used for one or more fixed-size signature search engines covering one or more fingerprints that are shorter in average having the same speed as or are faster than one or more memories used for one or more fixed-size signature search engines covering one or more fingerprints that are longer in average.

20. The system of claim 16, a plurality of fingerprint scan engines being used such that the number of fingerprint scan engines having a smaller product of a scan step size and a memory speed are more than the number of fingerprint scan engines having a larger product of a scan step size and a memory speed.