Performance enhancement for signature based pattern matching
First Claim
Patent Images
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
25 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
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.
-
Specification