Performance enhancement for signature based pattern matching

• US 7,810,155 B1
• Filed: 03/30/2005
• Issued: 10/05/2010
• Est. Priority Date: 03/30/2005
• Status: Active Grant

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Ravi, Sunil
• Primary Examiner(s): Shiferaw; Eleni A
• Application Number:
  US11/096,248
• Time in Patent Office: 2,015 Days
• Field of Search: 726/22, 726/23, 726/24, 726/25, 726/26, 709/224, 380/201, 380/202, 380/203
• US Class Current: 726/22
• 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

Abstract

Performance enhancement for signature based pattern matching may include one or more signature preprocessing steps. The signatures in the signature set may be preprocessed prior to performing pattern matching, including by breaking each signature broken down into one or more components. For at least one of the one or more components, boundary values as well as possible offsets of the boundary values may be identified and matched against a data stream to determine whether the data stream does not match a particular signature, thereby allowing a quick narrowing of the set of signatures to be applied fully to the data stream.

Claims

1. A method of determining whether a data stream matches a signature, comprising:

parsing, using a processor, the signature into one or more components;

identifying, using the processor, for at least one of said one or more components a plurality of boundary values, wherein identifying for at least one of said one or more components the plurality of boundary values includes determining for each boundary value one or more boundary value locations at which the boundary value would be expected to occur in a target data stream if the target data stream matched the signature, wherein for each component the plurality of boundary values include a first value and a last value of the component and further comprising determining for each component one or more offsets of the last value of the component from the first value of the component, wherein each component (1) has a component minimum length and a component maximum length that define a first range of component length values and (2) includes a subcomponent having a subcomponent minimum length and a subcomponent maximum length that define a second range of subcomponent length values; and

concluding, without fully applying the signature to the data stream, that the data stream does not match the signature if for any component an associated boundary value does not match at least one corresponding value in the data stream at the determined boundary value location of the data stream;

concluding that the signature is a potential match if all the boundary values of all the components of the signature match at least one corresponding value in the data stream; and

applying the signature to the data stream in the event it is concluded that the signature is a potential match;

wherein at least one boundary value associated with the signature does not occur in a prefix portion of the signature.

2. The method as recited in claim 1, wherein concluding without fully applying the signature to the data stream that the data stream does not match the signature if for any component an associated boundary value does not match at least one corresponding value in the data stream includes comparing each boundary value only to respective data stream values that occur at the one or more boundary value locations associated with the boundary value.

3. The method as recited in claim 1, wherein the boundary values include an initial boundary value associated with an initial portion of the signature and the boundary value locations for boundary values other than the initial boundary value include one or more offset values each indicating a position relative to the initial boundary value.

4. The method as recited in claim 1, further comprising checking the data stream for multiple matches of one or more of the boundary values.

5. The method as recited in claim 1, wherein fully applying the signature includes comparing each value of the signature to each corresponding value in the data stream.

6. The method as recited in claim 1, further comprising:

recording one or more locations in the data stream at which the boundary values of the components matched corresponding values in the data stream; and

fully applying the signature to the data stream utilizing the recorded one or more locations in the data stream at which the boundary values of the components matched.

7. The method as recited in claim 6, wherein utilizing the recorded one or more locations in the data stream at which the boundary values of the components matched includes for each pair of boundary values comparing signature values, if any, that occur between the pair of boundary values with the corresponding values in the data stream that occur between the recorded locations at which values matching the pair of boundary values were found.

8. The method as recited in claim 1, further comprising comparing each boundary value to one or more corresponding values in the data stream.

9. The method as recited in claim 8, further comprising determining, prior to comparing the boundary values associated with a component to one or more corresponding values in the data stream, whether enough data is available in the data stream to compare each boundary value associated with the component to one or more corresponding values in the data stream.

10. The method as recited in claim 9, further comprising waiting for enough data to become available if it is determined that enough data is not yet available in the data stream to compare each boundary value associated with the component to one or more corresponding values in the data stream.

11. The method as recited in claim 10, further comprising concluding that the data stream does not match the signature if it is determined that enough data is not and will not become available in the data stream to compare each boundary value associated with a component to one or more corresponding values in the data stream.

12. The method as recited in claim 1, wherein the signature comprises one of a plurality of signatures.

13. The method as recited in claim 12, further comprising:

parsing each signature into one or more components; and

identifying for each component of each signature one or more boundary values.

14. The method as recited in claim 1, wherein the signature is associated with malicious data known to have been used or known to be capable of being used to attack a computer.

15. The method as recited in claim 1, wherein the signature is associated with a policy.

16. The method as recited in claim 1, wherein the signature comprises a regular expression.

17. The method as recited in claim 1, wherein the first value of the component is a first byte of the component and the last value of the component is a last byte of the component.

18. The method as recited in claim 1, wherein:

for each component the offsets of the last value of the component occur at a set of locations each of which is determined by multiplying a value from the second range of subcomponent length values for that component by a value from the first range of component length values for that component.

19. The method as recited in claim 1, wherein:

for each component the offsets of the last value of the component occur at a set of locations each of which is determined by multiplying one of the possible subcomponent length values for that component by one of the component length values in the range of component length values for that component.

20. The method as recited in claim 1, wherein the prefix portion comprises a contiguous series of one or more values beginning with a first value associated with the signature.

21. The method as recited in claim 1

wherein said parsing and identifying comprise pre-processing performed prior to the data stream becoming available for analysis.

22. The method as recited in claim 1, wherein the processor is associated with a detection system.

23. The method as recited in claim 22, wherein the detection system comprises an intrusion detection system.

24. A system configured for determining whether a data stream matches a signature, comprising:

a communication interface configured to receive the data stream; and

a processor configured to;

parse the signature into one or more components;

identify for at least one of said one or more components a plurality of boundary values, wherein identifying for at least one of said one or more components the plurality of boundary values includes determining for each boundary value one or more boundary value locations at which the boundary value would be expected to occur in a target data stream if the target data stream matched the signature, wherein for each component the plurality of boundary values include a first value and a last value of the component and further comprising determining for each component one or more offsets of the last value of the component from the first value of the component, wherein each component (1) has a component minimum length and a component maximum length that define a first range of component length values and (2) includes a subcomponent having subcomponent minimum length and a subcomponent maximum length that define a second range of subcomponent length values; and

conclude, without fully applying the signature to the data stream, that the data stream does not match the signature if for any component an associated boundary value does not match at least one corresponding value in the data stream at the determined boundary value location of the data stream;

conclude that the signature is a potential match if all the boundary values of all the components of the signature match at least one corresponding-value in the data stream; and

apply the signature to the data stream in the event it is concluded that the signature is a potential match;

wherein at least one boundary value associated with the signature does not occur in a prefix portion of the signature.

25. A computer readable storage medium for determining whether a data stream matches a signature, the computer readable storage medium comprising stored computer instructions for:

parsing the signature into one or more components;

identifying for at least one of said one or more components a plurality of boundary values, wherein identifying for at least one of said one or more components the plurality of boundary values includes determining for each boundary value one or more boundary value locations at which the boundary value would be expected to occur in a target data stream if the target data stream matched the signature, wherein for each component the plurality of boundary values include a first value and a last value of the component and further comprising determining for each component one or more offsets of the last value of the component from the first value of the component, wherein each component (1) has a component minimum length and a component maximum length that define a first range of component length values and (2) includes a subcomponent having a subcomponent minimum length and a subcomponent maximum length that define a second range of subcomponent length values; and

concluding, without fully applying the signature to the data stream, that the data stream does not match the signature if for any component an associated boundary value does not match at least one corresponding value in the data stream at the determined boundary value location of the data stream;

concluding that the signature is a potential match if all the boundary values of all the components of the signature match at least one corresponding-value in the data stream; and

applying the signature to the data stream in the event it is concluded that the signature is a potential match;

wherein at least one boundary value associated with the signature does not occur in a prefix portion of the signature.