Method and Apparatus for Approximate Pattern Matching

• US 20070260602A1
• Filed: 05/02/2006
• Published: 11/08/2007
• Est. Priority Date: 05/02/2006
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Exegy Incorporated
• Inventors: Taylor, David
• Granted Patent: US 7,636,703 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04W 12/71 Hardware identity

Abstract

A system and method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error, which includes filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms, detecting a plurality of potential pattern piece matches, identifying a plurality of potentially matching patterns, reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns with a reduction stage, providing associated data and the reduced set of potentially matching patterns, each having an associated allowable error, to a verification stage, and verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations and associated allowable errors with the verification stage.

Claims

1. A method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine comprising:

filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms each configured to detect one or more patterns each with an associated allowable error;

detecting a plurality of potential pattern piece matches with the plurality of parallel filter mechanisms;

identifying a plurality of potentially matching patterns, each having an associated allowable error, from the plurality of parallel filter mechanisms;

reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error with a reduction stage;

providing associated data and the reduced set of potentially matching patterns, each having an associated allowable error, to a verification stage; and

verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations and associated allowable errors with the verification stage that includes an approximate match engine utilizing the associated data and the reduced set of potentially matching patterns.

2. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 1, further comprising providing the data stream prior to the step of filtering a data stream from the group consisting of a communication link, a redundant array of independent disks (“

RAID”

), or a storage area network (“

SAN”

).

3. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 1, wherein the plurality of parallel filter mechanisms is a group consisting of a set of parallel Bloom filters, a set of parallel Bloom filter arrays or a set of parallel Bloom filter arrays that utilize a single hash key generator.

4. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 1, wherein the plurality of parallel filter mechanisms is selected from the group consisting of at least one reconfigurable logic device or at least one integrated circuit, the reduction stage is selected from the group consisting of at least one reconfigurable logic device or at least one integrated circuit.

5. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 4, wherein the plurality of parallel filter mechanisms is selected from the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) or the at least one Application-Specific Integrated Circuit (“

ASIC”

), the reduction stage is selected from the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) or the at least one Application-Specific Integrated Circuit (“

ASIC”

)

6. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 1, wherein the plurality of parallel filter mechanisms include at least one Bloom filter array that utilizes a single hash key generator for computing hash values that correspond to a bit vector and positions in the bit vector that identify whether an inputted data segment is a match with one of the pattern pieces stored in the Bloom filter array.

7. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 1, wherein the step of reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, further includes:

utilizing data from the plurality of parallel filter mechanisms to lookup one or more pattern piece identifiers for each data segment piece that produced a match in the plurality of parallel filter mechanisms;

utilizing the one or more pattern piece identifiers for retrieving at least one pattern identifier;

utilizing the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error; and

utilizing the at least one potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations with a verification stage.

8. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 7, wherein the step of reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, further includes utilizing a first lookup function with a bin index.

9. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 8, wherein the bin index is selected from the group consisting of different hash keys or portions of hash keys.

10. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 1, wherein the step of reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, further includes:

utilizing the at least one data segment that produced a match from the step of filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms for retrieving at least one pattern identifier;

utilizing the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error; and

utilizing the potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.

14. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 1, wherein the step of reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, further includes utilizing a plurality of parallel Bloom filter arrays, where each Bloom filter array utilizes a single hash key generator for extracting a plurality of hash values from a single hash value for inspecting the data stream for data segments matching one or more pattern pieces with false positive errors.

11. A method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine comprising:

filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms each configured to detect one or more patterns each with an associated allowable error, wherein the plurality of parallel filter mechanisms is a group consisting of a set of parallel Bloom filters, a set of parallel Bloom filter arrays or a set of parallel Bloom filter arrays that utilize a single hash key generator;

detecting a plurality of potential pattern piece matches with the plurality of parallel filter mechanisms;

identifying a plurality of potentially matching patterns, each having an associated allowable error, from the plurality of parallel filter mechanisms;

reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error;

providing associated data and the reduced set of potentially matching patterns, each having an associated allowable error, to a verification stage; and

verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations and associated allowable errors with the verification stage that includes an approximate match engine utilizing the associated data and the reduced set of potentially matching patterns.

12. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 11, wherein the step of reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, further includes:

utilizing data from the plurality of parallel filter mechanisms to lookup one or more pattern piece identifiers for each data segment piece that produced a match in the plurality of parallel filter mechanisms;

utilizing a plurality of pattern piece identifiers for retrieving at least one pattern identifier;

utilizing the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error; and

utilizing the at least one potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream.

13. The method for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 11, wherein the step of reducing the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, further includes:

utilizing the at least one data segment that produced a match from the step of filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms for retrieving at least one pattern identifier;

utilizing the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error; and

utilizing the potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.

15. A system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine comprising:

a filter stage, which utilizes a plurality of parallel filter mechanisms each configured to detect one or more patterns, each with an associated allowable error, that filter a data stream for a plurality of patterns of symbol combinations and detect a plurality of potential pattern piece matches, and identify a plurality of potentially matching patterns, each having an associated allowable error;

a reduction stage, which reduces the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error; and

a verification stage, which includes an approximate match engine, that receives and utilizes associated data and the reduced set of potentially matching patterns and associated allowable errors to verify a presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.

16. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 15, further comprising a data stream provider from the group consisting of a communication link, a redundant array of independent disks (“

RAID”

), or a storage area network (“

SAN”

).

17. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 15, wherein the plurality of parallel filter mechanisms is a group consisting of a set of parallel Bloom filters, a set of parallel Bloom filter arrays or a set of parallel Bloom filter arrays that utilize a single hash key generator.

18. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 15, wherein the filter stage is selected from the group consisting of at least one reconfigurable logic device or at least one integrated circuit, the reduction stage is selected from the group consisting of at least one reconfigurable logic device or at least one integrated circuit

19. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 18, wherein the filter stage is selected from the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) or the at least one Application-Specific Integrated Circuit (“

ASIC”

), the reduction stage is selected from the group consisting of at least one Field Programmable Gate Array (“

FPGA”

) or the at least one Application-Specific Integrated Circuit (“

ASIC”

).

20. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 15, wherein the filter stage includes a plurality of parallel filter mechanisms which includes at least one Bloom filter array that utilizes a single hash key generator for computing hash values that correspond to the position of a Bloom filter in the at least one Bloom filter array and the positions of bits in the Bloom filter that identify whether an inputted piece of a data segment is a match with at least one of the plurality of potentially matching pattern pieces.

21. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 15, wherein the reduction stage that reduces the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, also utilizes data from the plurality of parallel filter mechanisms to lookup one or more pattern piece identifiers for each data segment piece that produced a match in the plurality of parallel filter mechanisms and utilizes a plurality of pattern piece identifiers for retrieving at least one pattern identifier and utilizes the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error and utilizes the at least one potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.

22. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 21, wherein the reduction stage utilizes a first lookup function with a bin index.

23. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 22, wherein the bin index is selected from the group consisting of different hash keys or portions of hash keys.

24. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 15, wherein the reduction stage that reduces the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, also utilizes the at least one data segment that produced a match from the step of filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms for retrieving at least one pattern identifier and utilizes the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error and utilizes the potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.

25. A system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine comprising:

a plurality of parallel filter mechanisms, wherein the plurality of parallel filter mechanisms is a group consisting of a set of parallel Bloom filters, a set of parallel Bloom filter arrays or a set of parallel Bloom filter arrays that utilize a single hash key generator;

each configured to detect one or more patterns, each with an associated allowable error, that filter a data stream for a plurality of patterns of symbol combinations and detect a plurality of potential pattern piece matches and identify a plurality of potentially matching patterns, each having an associated allowable error;

a reduction stage that reduces the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error; and

a verification stage, which includes an approximate match engine, that receives and utilizes associated data and the reduced set of potentially matching patterns and associated allowable errors to verify a presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.

26. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 25, wherein the reduction stage that reduces the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, also utilizes data from the plurality of parallel filter mechanisms to lookup one or more pattern piece identifiers for each data segment piece that produced a match in the plurality of parallel filter mechanisms and utilizes a plurality of pattern piece identifiers for retrieving at least one pattern identifier and utilizes the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error and utilizes the at least one potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.

27. The system for inspecting a data stream for data segments matching one or more patterns each having a predetermined allowable error with at least one search engine according to claim 25, wherein the reduction stage that reduces the identified plurality of potentially matching patterns to a set of potentially matching patterns, each having an associated allowable error, also utilizes the at least one data segment that produced a match from the step of filtering a data stream for a plurality of patterns of symbol combinations with a plurality of parallel filter mechanisms for retrieving at least one pattern identifier and utilizes the at least one pattern identifier for retrieving at least one potentially matching pattern and an associated allowable error and utilizes the potentially matching pattern and the associated allowable error for verifying presence of a pattern match in the data stream from the plurality of patterns of symbol combinations.