Methods and apparatus for detecting patterns in a data stream

• US 7,440,461 B2
• Filed: 12/23/2003
• Issued: 10/21/2008
• Est. Priority Date: 12/23/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Rajagopal, Priya, Sahita, Ravi, Durham, David
• Primary Examiner(s): Yao; Kwang B.
• Assistant Examiner(s): LOO, JUVENA W
• Application Number:
  US10/744,709
• Publication Number:
  US 20050135380A1
• Time in Patent Office: 1,764 Days
• Field of Search: None
• US Class Current: 370/395.32
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

In some embodiments, a method includes generating a prefix trie for a set of patterns, generating a suffix trie for the set of patterns, and establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie. In some embodiments, a method includes adding a suffix to a suffix tree, so that the suffix (which is at least a portion of a pattern) is represented in the tree by a path that begins at a first node and ends at a second node, and associating with at least the first node and the second node a pattern identifier that identifies the pattern.

Claims

1. A method comprising:

generating a prefix trie for a set of patterns;

generating a suffix trie for the set of patterns;

establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detecting a prefix from a pattern of the set of patterns at an end of a data packet, the prefix corresponding to a node of the prefix trie; and

in response to detecting the prefix, storing data in association with a node of the suffix trie;

wherein;

the node of the suffix trie in association with which the data is stored corresponds to the node of the prefix trie which corresponds to the detected prefix; and

the stored data is indicative of a flow with which the data packet is associated.

2. The method of claim 1, wherein the stored data is a hash of source and destination data for the flow.

5. The method of claim 1, further comprising:

in response to detecting the prefix, determining whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the prefix corresponds; and

in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the prefix corresponds, indicating that the pattern is detected in the flow with which the data packet is associated.

3. A method comprising:

generating a prefix trie for a set of patterns;

generating a suffix trie for the set of patterns;

establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detecting a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie; and

in response to detecting the suffix, storing data in association with a node of the prefix trie;

wherein;

the node of the prefix trie in association with which the data is stored corresponds to the node of the suffix trie which corresponds to the detected suffix; and

the stored data is indicative of a flow with which the data packet is associated.

4. The method of claim 3, wherein the stored data is a hash of source and destination data for the flow.

6. A method comprising:

generating a prefix trie for a set of patterns;

generating a suffix trie for the set of patterns;

establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detecting a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie;

in response to detecting the suffix, determining whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the suffix corresponds; and

in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the suffix corresponds, indicating that the pattern is detected in the flow with which the data packet is associated.

7. An apparatus comprising:

a processor; and

a memory in communication with the processor;

the processor operative to;

generate a prefix trie for a set of patterns;

generate a suffix trie for the set of patterns;

establish respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detect a prefix from a pattern of the set of patterns at an end of a data packet, the prefix corresponding to a node of the prefix trie; and

store data, in response to detecting the prefix, in association with a node of the suffix trie;

wherein;

the node of the suffix trie in association with which the data is stored corresponds to the node of the prefix trie which corresponds to the detected prefix; and

the stored data is indicative of a flow with which the data packet is associated.

9. The apparatus of claim 7, wherein the processor is further operative to:

determine, in response to detecting the prefix, whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the prefix corresponds; and

indicate, in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the prefix corresponds, that the pattern is detected in the flow with which the data packet is associated.

8. An apparatus comprising:

a processor; and

a memory in communication with the processor;

the processor operative to;

generate a prefix trie for a set of patterns;

generate a suffix trie for the set of patterns;

establish respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detect a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie; and

store data, in response to detecting the suffix, in association with a node of the prefix trie;

wherein;

the node of the prefix trie in association with which the data is stored corresponds to the node of the suffix trie which corresponds to the detected suffix; and

the stored data is indicative of a flow with which the data packet is associated.

10. An apparatus comprising:

a processor; and

a memory in communication with the processor;

the processor operative to;

generate a prefix trie for a set of patterns;

generate a suffix trie for the set of patterns;

establish respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detect a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie;

determine, in response to detecting the suffix, whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the suffix corresponds; and

indicate, in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the suffix corresponds, that the pattern is detected in the flow with which the data packet is associated.

11. A storage medium having stored thereon instructions that when executed by a machine result in the following:

generating a prefix trie for a set of patterns;

generating a suffix trie for the set of patterns;

establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detecting a prefix from a pattern of the set of patterns at an end of a data packet, the prefix corresponding to a node of the prefix trie; and

in response to detecting the prefix, storing data in association with a node of the suffix trie;

 

wherein;

the node of the suffix trie in association with which the data is stored corresponds to the node of the prefix trie which corresponds to the detected prefix; and

the stored data is indicative of a flow with which the data packet is associated.

13. The storage medium of claim 11, wherein the storage medium further has stored thereon instructions that when executed by a machine result in the following:

in response to detecting the prefix, determining whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the prefix corresponds; and

in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the prefix corresponds, indicating that the pattern is detected in the flow with which the data packet is associated.

12. A storage medium having stored thereon instructions that when executed by a machine result in the following:

generating a prefix trie for a set of patterns;

generating a suffix trie for the set of patterns;

establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detecting a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie; and

in response to detecting the suffix, storing data in association with a node of the prefix trie;

 

wherein;

the node of the prefix trie in association with which the data is stored corresponds to the node of the suffix trie which corresponds to the detected suffix; and

the stored data is indicative of a flow with which the data packet is associated.

14. A storage medium having stored thereon instructions that when executed by a machine result in the following:

generating a prefix trie for a set of patterns;

generating a suffix trie for the set of patterns;

establishing respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detecting a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie;

in response to detecting the suffix, determining whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the suffix corresponds; and

in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the suffix corresponds, indicating that the pattern is detected in the flow with which the data packet is associated.

15. A system comprising:

a fabric interface chip; and

a network processor coupled to the fabric interface chip;

wherein the network processor includes;

a processing unit; and

a memory in communication with the processing unit;

the processing unit operative to;

generate a prefix trie for a set of patterns;

generate a suffix trie for the set of patterns;

establish respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detect a prefix from a pattern of the set of patterns at an end of a data packet, the prefix corresponding to a node of the prefix trie; and

store data, in response to detecting the prefix, in association with a node of the suffix trie;

wherein;

the node of the suffix the in association with which the data is stored corresponds to the node of the prefix trie which corresponds to the detected prefix; and

the stored data is indicative of a flow with which the data packet is associated.

17. The system of claim 15, wherein the processing unit is further operative to:

determine, in response to detecting the prefix, whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the prefix corresponds; and

indicate, in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the prefix corresponds, that the pattern is detected in the flow with which the data packet is associated.

16. A system comprising:

a fabric interface chip; and

a network processor coupled to the fabric interface chip;

wherein the network processor includes;

a processing unit; and

a memory in communication with the processing unit;

the processing unit operative to;

generate a prefix trie for a set of patterns;

generate a suffix trie for the set of patterns;

establish respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detect a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie; and

store data, in response to detecting the suffix, in association with a node of the prefix trie;

wherein;

the node of the prefix trie in association with which the data is stored corresponds to the node of the suffix trie which corresponds to the detected suffix; and

the stored data is indicative of a flow with which the data packet is associated.

18. A system comprising:

a fabric interface chip; and

a network processor coupled to the fabric interface chip;

wherein the network processor includes;

a processing unit; and

a memory in communication with the processing unit;

the processing unit operative to;

generate a prefix trie for a set of patterns;

generate a suffix trie for the set of patterns;

establish respective links between nodes of the prefix trie and respective corresponding nodes of the suffix trie;

detect a suffix from a pattern of the set of patterns at a beginning of a data packet, the suffix corresponding to a node of the suffix trie;

determine, in response to detecting the suffix, whether data indicative of a flow with which the data packet is associated is stored in association with the node to which the suffix corresponds; and

indicate, in response to the data indicative of the flow with which the data packet is associated being found stored in association with the node to which the suffix corresponds, that the pattern is detected in the flow with which the data packet is associated.