Fast signature scan

• US 7,454,418 B1
• Filed: 11/05/2004
• Issued: 11/18/2008
• Est. Priority Date: 11/07/2003
• Status: Active Grant

• Current Assignee: Light Speed Microelectronics, LLC
• Original Assignee: Qiang Wang
• Inventors: Wang, Qiang
• Primary Examiner(s): Lee; Wilson
• Assistant Examiner(s): Gofman; Alex
• Application Number:
  US10/982,057
• Time in Patent Office: 1,474 Days
• Field of Search: 707/3, 707/6, 726/25
• US Class Current: 1/1
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• 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
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Systems and methods for scanning signatures in a string field. In one implementation, the invention provides a method for string signature scanning. The method includes processing one or more signatures into one or more formats, receiving a string field, translating the string field into one of the one or more formats of a signature database, identifying any string signatures included in the string field including scanning the string field for one or more fingerprints associated with string signatures, and outputting any identified string signatures.

Claims

1. A method for signature scanning for one or more fully specified signatures, comprising:

processing one or more signatures into one or more formats that include a plurality of fingerprints and one or more follow-on search data structures for each signature, each successive fingerprint of a particular signature having a first basic unit in a scanning direction that is shifted one or more units from the previous fingerprint of the particular signature such that the number of shifted fingerprints is equal to a step size for a signature scanning operation and the particular signature is identifiable at any location within any string fields to be scanned, the step size used to identify a plurality of locations to scan in one or more string fields, where each fingerprint of the plurality of fingerprints includes one or more fragments of the particular signature, the one or more fragments having particular locations anywhere within the particular signature;

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 plurality of fingerprints associated with the one or more signatures, where the scanning includes scanning for the plurality of fingerprints including two or more fingerprints in parallel for each step size, and searching the particular string field for the follow-on search data structures only 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 the 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.

3. The method of claim 2, where each of the lengths of the fingerprints is a multiple of the scan step size.

4. The method of claim 1, further comprising:

decomposing a fingerprint into one or more fingerprint segments;

scanning the particular string field;

identifying one or more fingerprint segments; and

synthesizing the identified fingerprint segments into one or more fingerprint matches.

5. The method of claim 4, where all fingerprint segments have a same length and the scan step size is a multiple of the length.

6. The method of claim 1, further comprising scanning for the fingerprints using one or more hash tables or bloom filters.

7. The method of claim 6, where scanning for the fingerprints further comprises using one or more of:

a hash value de-multiplexer; and

a fingerprint length de-multiplexer.

8. The method of claim 1, further comprising:

constructing a differential search structure using one or more distinct basic units among a plurality of string signatures; and

searching for one or more signatures differentially.

9. A signature scanning system for one or more fully specified signatures, 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 a plurality of fingerprints and one or more follow-on search data structures for each signature, each successive fingerprint of a particular signature having a first basic unit in a scanning direction that is shifted one or more units from the previous fingerprint of the particular signature such that the number of shifted fingerprints is equal to a step size for a signature scanning operation and the particular signature is identifiable at any location within any string fields to be scanned, the step size used to identify a plurality of locations to scan in one or more string fields, where each fingerprint of the plurality of fingerprints includes one or more fragments of the particular signature, the one or more fragments having particular locations anywhere within the particular signature;

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

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

a signature search engine operable to identify corresponding signatures for the identified fingerprints.

10. The system of claim 9, the signature pre-processing module being operable to construct a signature database, comprising:

a fingerprint database; and

a signature database.

11. The system of claim 9, the signature pre-processing module being operable to decompose one or more fingerprints into a plurality of fingerprint segments and store synthesis information for said each fingerprint segment of the plurality of fingerprint segments in a fingerprint database.

12. The system of claim 9, the signature pre-processing module being operable to construct a differential search structure using one or more distinct basic unit among a plurality of signatures.

13. The system of claim 9, the scan pre-processing engine being operable to process a string field in a plurality of blocks, the processing including decoding, normalizing, and translating, each block of the plurality of blocks comprising:

a fingerprint scan region for performing a fingerprint scan and for signature search;

a front signature search region in advance of the fingerprint scan region for signature search; and

a rear signature search region behind the fingerprint scan region for signature search.

14. The system of claim 9, the fingerprint scan engine being operable to detect one or more fingerprints using one or more hash tables or bloom filters.

15. The system of claim 9, the fingerprint scan engine further comprising:

a fingerprint scan controller;

a fingerprint hash engine;

a fingerprint search engine;

a fingerprint synthesis engine; and

a fingerprint database.

16. The system of claim 15, the fingerprint synthesis engine being operable to synthesize a plurality of fingerprint segments into one or more fingerprint matches if there is at least one matched fingerprint.

17. The system of claim 15, the fingerprint hash engine being operable to compute a plurality of hash values for a plurality of hash keys sequentially in non-overlapping prefix segments using a sequential hash function.

18. The system of claim 9, the signature search engine further comprising:

a signature finder;

a signature verifier; and

a signature database.

19. The system of claim 18, wherein the signature finder is operable to search for one or more signatures differentially.

20. The system of claim 9, where one or more engines includes one or more of content addressable memories (CAM) and finite automata (FA).

21. The system of claim 9, where the fingerprint scan engine includes one or more content addressable memories (CAM).

22. A method for signature scanning for one or more signatures that at least one of them is not fully specified, comprising:

processing the one or more signatures into one or more formats that include one or more fingerprints for each fixed-size signature or each fixed-size portion of each variable-size signature and one or more follow-on search data structures, each successive fingerprint of a particular signature having a first basic unit in a scanning direction that is shifted one or more units from the previous fingerprint of the particular signature such that the number of shifted fingerprints is equal to a step size for a signature scanning operation and the particular signature is identifiable at any location within any string fields to be scanned, the step size used to identify one or more locations to scan in one or more string fields, where each fingerprint of the one or more fingerprints includes one or more fragments of the particular signature, the one or more fragments having particular locations within the particular signature and that are 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;

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

identifying signatures included in the particular string field including scanning the particular string field in an original space when all of the one or more fingerprints are fully specified in the original space the scanning including scanning for one or more fingerprints for each step size, scanning the particular string field in each of the one or more shadow spaces that have at least one fingerprint the scanning including scanning for one or more fingerprints for each step size, and then verifying the identified fingerprints in the original space at the scan location where one or more identified fingerprints are found in at least one of the one or more shadow spaces for the one or more fingerprints associated with one or more signatures in the particular string field, and searching the particular string field for the follow-on search data structures only at the scan locations where one or more fingerprints are found; and

outputting any identified signatures in the particular string field.

23. The method of claim 22, wherein scanning the particular string field further comprises:

identifying a match between a fingerprint and an associated signature;

determining if the associated signature corresponds to a fixed-size signature or a fixed-size signature substring of a variable-size signature when there is at least one variable-size signature in the one or more signatures; and

synthesizing fixed-size signature substrings of a variable-size signature to identify a variable-sized signature when there is at least one variable-size signature in the one or more signatures.

24. The method of claim 22, further comprising:

decomposing a signature containing at least one variable-size symbol into a plurality of fixed-size signature substrings and one or more variable-size signature substrings.

25. The method of claim 22, further comprising:

encoding one or more fragments of a signature with one or more mask bits and store the one or more mask bits with the one or more fragments for a signature.

26. The method of claim 22, wherein the 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.

27. The method of claim 26, where each of the lengths of the fingerprints is a multiple of the scan step size.

28. The method of claim 22, further comprising:

normalizing the particular string field, including one or more of;

decompressing the particular string field if the particular string filed is in a compressed format;

decoding the particular string field if the particular string field is encoded; and

removing unnecessary string data.

29. The method of claim 22, further comprising:

decomposing a fingerprint into one or more fingerprint segments;

scanning the particular string field;

identifying one or more fingerprint segments; and

synthesizing the identified fingerprint segments into one or more fingerprint matches.

30. The method of claim 29, where all fingerprint segments have a same length and the scan step size is a multiple of the length.

31. The method of claim 22, wherein scanning for the fingerprints using one or more hash tables or bloom filters.

32. The method of claim 31, where scanning for the fingerprints further comprises using one or more of a hash value de-multiplexer;

and

a fingerprint length de-multiplexer.

33. The method of claim 22, further comprising:

constructing a differential search structure using one or more distinct basic units among a plurality of string signatures; and

searching for one or more signatures differentially.

34. The method of claim 22, wherein a shadow space is a space after changing all the characters in both upper and lower cases in an original space to a same case or all numerical digits from 0 to 9 in an original space to a same digit or both “

space” and

“

-”

in an original space to one of a “

space”

or “

-”

.

35. The method of claim 26, where a plurality of the fingerprints are selected for each fixed-sized signature or each fixed-size portion of each variable-size signature based on a cost function of a particular signature scanning system.

36. The method of claim 22, where a plurality of the fingerprints for each fixed-sized signature or each fixed-size portion of each variable-size signature are selected along with the selection of one or more shadow spaces.

37. The method of claim 22, where the number of the one or more shadow spaces are selected for a maximum scanning speed.

38. A signature scanning system for one or more signatures where at least one of the one or more signatures is not fully specified, 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 signatures into one or more formats that include one or more fingerprints for each fixed-size signature or each fixed-size portion of a variable-size signature and one or more follow-on search data structures, each successive fingerprint of a particular signature having a first basic unit in a scanning direction that is shifted one or more units from the previous fingerprint of the particular signature such that the number of shifted fingerprints is equal to a step size for a signature scanning operation and the particular signature is identifiable at any location within any string fields to be scanned, the step size used to identify one or more locations to scan in one or more string fields, where each fingerprint includes one or more fragments of the particular signature, the one or more fragments having particular locations within the particular signature that are 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;

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

a fingerprint scan engine operable to identify fingerprints associated with one or more signatures on the input string field, the identifying including scanning the input string field, where the scanning includes scanning for one or more fingerprints for each 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 when there is at least one variable-size signature in the signature scanning system.

39. The system of claim 38, the signature pre-processing module being operable to construct a signature database, comprising:

a fingerprint database;

a fixed-size signature database; and

a variable-size signature database when there is at least one variable-size signature in the signature scanning system.

40. The system of claim 38, the signature pre-processing module being operable to decompose each of one or more fingerprints into one or more fingerprint segments and store synthesis information for the plurality of fingerprint segments in a fingerprint database.

41. The system of claim 38, the signature pre-processing module being operable to select one or more shadow spaces and translate one or more fingerprints into the one or more of the selected shadow spaces for scanning.

42. The system of claim 38, the signature pre-processing module being operable to encode one or more fragments of a signature with one or more mask bits and store the one or more mask bits with the one or more fragments for a complex signatures.

43. The system of claim 38, the signature pre-processing module being operable to construct a differential search structure using one or more distinct basic units among a plurality of signatures.

44. The system of claim 38, the scan pre-processing engine being operable to process a string field in a plurality of blocks, the processing including one or more of feeding, decoding, normalizing, and translating, each block of the plurality of blocks comprising:

a fingerprint scan region for performing a fingerprint scan and for signature search;

a front signature search region in advance of the fingerprint scan region for signature search; and

a rear signature search region behind the fingerprint scan region for signature search.

45. The system of claim 38, the fingerprint scan engine being operable to detect one or more fingerprints using one or more hash tables or bloom filters.

46. The system of claim 45, where the fingerprint scan engine further comprises one or more of:

a hash value de-multiplexer; and

a fingerprint length de-multiplexer.

47. The system of claim 38, the scan pre-processing engine further comprising:

a scan feeder,

a shadow translator;

a string memory; and

a shadow memory.

48. The system of claim 38, the fingerprint scan engine further comprising:

a fingerprint scan controller;

a fingerprint hash engine;

a fingerprint search engine;

a fingerprint synthesis engine; and

a fingerprint database.

49. The system of claim 48, the fingerprint synthesis engine being operable to synthesize a plurality of fingerprint segments into one or more fingerprint matches if there is at least one matched fingerprint.

50. The system of claim 48, the fingerprint hash engine being operable to compute a plurality of hash values for a plurality of hash keys sequentially in non-overlapping prefix segments using a sequential hash function.

51. The system of claim 38, the fixed-size signature search engine further comprising:

a signature finder;

a signature verifier; and

a fixed-size signature database.

52. The system of claim 51, wherein the signature finder and the signature verifier are operable to compare a plurality of masked fragments of a signature using a signature unit comparator and a signature segment comparator to identify one or more fixed-size signatures.

53. The system of claim 51, wherein the signature finder is operable to search for one or more signatures differentially.

54. The system of claim 38, the variable-size signature search engine further comprising:

a signature rule lookup engine;

a signature state verifier;

a signature rule database; and

a signature state table.

55. The system of claim 38, a plurality of the fingerprints are selected for each fixed-sized signature or each fixed-size portion of each variable-size signature based on a cost function of the system.

56. The system of claim 38, where one or more engines includes one or more of content addressable memories (CAM) and finite automata (FA).

57. The system of claim 38, where the fingerprint scan engine includes one or more content addressable memories (CAM).