Searching for strings in messages

• US 20070106640A1
• Filed: 10/05/2005
• Published: 05/10/2007
• Est. Priority Date: 10/05/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Shankara, Udaya
• Granted Patent: US 8,095,549 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload

Abstract

A network device to determine the presence of one or more of the pre-defined strings in a message based on searching for a suffix and a reverse prefix in response to receiving a key search data indicating possible presence of any of the plurality of pre-defined strings. The network device indicates the presence or absence of one or more of the pre-defined strings in the message based on the suffix and prefix search results.

Claims

1. A method of searching a pre-defined string in a message, comprising

sending a key and a corresponding index of the key in response to determining the presence of a sub-string of the pre-defined string in the message, and

detecting whether the pre-defined string is present in the message based on searching for a suffix and a reverse prefix in response to receiving the key and the index of the key.

2. The method of claim 1 further comprising

matching the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key, and

storing one or more suffix tags of each suffix node in response to determining that the elements of the suffix node represents a valid suffix of the sub-string.

3. The method of claim 2 the suffix tag comprises a string identifier representing the pre-defined string to be detected.

4. The method of claim 1 comprising

matching the reverse prefix elements of the sub-string in the message with the elements of one or more reverse prefix nodes present in a path until a reverse prefix node representing a longest matching valid reverse prefix is found, wherein a starting reverse prefix element to begin matching the reverse prefix elements is based on the element corresponding to the index of the key,

storing one or more reverse prefix tags of each reverse prefix node in response to determining that the elements of the reverse prefix node represents a valid reverse prefix of the sub-string, and

continuing to search for valid suffixes and reverse prefixes for each key received.

5. The method of claim 4 further comprising

indicating the presence of the pre-defined string in response to determining that the reverse prefix tag and the suffix tag corresponding to the pre-defined string to be detected is stored, and

indicating the absence of the pre-defined string to be detected in response to determining the absence of the corresponding suffix tag or the reverse prefix tag.

6. The method of claim 1 comprising

matching the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key,

matching the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes of a first branch of a modified reverse prefix tree, wherein the first reverse prefix node is determined based on the index of the key,

storing a first tag of the first branch in response to determining that the elements of the plurality reverse prefix nodes of the first branch represent a valid reverse prefix, and

indicating the presence of a first pre-defined string corresponding to the first tag stored.

7. The method of claim 1 comprising

matching the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key,

matching the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a first branch of a modified reverse prefix tree, wherein the first reverse prefix node is determined based on the index of the key,

matching the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a second branch of a modified reverse prefix tree, if the sub-string comprises two reverse prefixes comprising an element corresponding to the first node of the first branch as the common element,

storing a first tag of the first branch and a second tag of the second branch in response to determining that the elements of the reverse prefix nodes of the first branch and the second branch represent two valid reverse prefixes, and

indicating the presence of a first pre-defined string and a second pre-defined string in the message.

8. A network device comprising

a network interface to receive a message,

a content addressable memory system to send a key and a corresponding index of the key in response to determining the presence of a sub-string of a pre-defined string in a message, and

a processor to detect whether the pre-defined string is present in the message based on searching for a suffix and a reverse prefix in response to receiving the key and the index of the key.

9. The network device of claim 8 comprising

the processor to match the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key, and

the memory to store one or more suffix tags of each suffix node in response to determining that the elements of the suffix node represents a valid suffix of the sub-string.

10. The network device of claim 9 the suffix tag comprises a string identifier representing the pre-defined string to be detected.

11. The network device of claim 8 comprising

the processor to match the reverse prefix elements of the sub-string in the message with the elements of one or more reverse prefix nodes present in a path until a reverse prefix node representing a longest matching valid reverse prefix is found, wherein a starting reverse prefix element to begin matching the reverse prefix elements is based on the element corresponding to the index of the key,

a memory to store one or more reverse prefix tags of each reverse prefix node in response to determining that the elements of the reverse prefix node represents a valid reverse prefix of the sub-string, and

the processor to continue to search for valid suffixes and reverse prefixes for each key received.

12. The network device of claim 11 comprising

the processor to indicate the presence of the pre-defined string in response to determining that the reverse prefix tag and the suffix tag corresponding to the pre-defined string to be detected is stored, and

the processor to indicate the absence of the pre-defined string to be detected in response to determining the absence of the corresponding suffix tag or the reverse prefix tag.

13. The network device of claim 8 comprising

the processor to match the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key,

the processor to match the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a first branch of a modified reverse prefix tree, wherein the first reverse prefix node is determined based on the index of the key,

a memory to store a first tag of the first branch in response to determining that the elements of the plurality reverse prefix nodes of the first branch represent a valid reverse prefix, and

the processor to indicate the presence of a first pre-defined string corresponding to the first tag stored.

14. The network device of claim 8 comprising

the processor to match the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key,

the processor to match the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a first branch of a modified reverse prefix tree, wherein the first reverse prefix node is determined based on the index of the key,

the processor to match the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a second branch of a modified reverse prefix tree, if the sub-string comprises two reverse prefixes comprising an element corresponding to the first node of the first branch as the common element,

a memory to store a first tag of the first branch and a second tag of the second branch in response to determining that the elements of the reverse prefix nodes of the first branch and the second branch represent two valid reverse prefixes, and

the processor to indicate the presence of a first pre-defined string and a second pre-defined string in response to determining that the first tag and the second tag respectively corresponding to the first pre-defined string and the second pre-defined string is stored.

15. A machine readable medium comprising a plurality of instructions that in response to being executed result in a computing device

sending a key and a corresponding index of the key in response to determining the presence of a sub-string of a pre-defined string in a message, and

detecting whether the pre-defined string is present in the message based on searching for a suffix and a reverse prefix in response to receiving the key and the index of the key.

16. The machine readable medium of claim 15 further comprising

matching the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key, and

storing one or more suffix tags of each suffix node in response to determining that the elements of the suffix node represents a valid suffix of the sub-string

17. The machine readable medium of claim 15 comprising

matching the reverse prefix elements of the sub-string in the message with the elements of one or more reverse prefix nodes present in a path until a reverse prefix node representing a longest matching valid reverse prefix is found, wherein a starting reverse prefix element to begin matching the reverse prefix elements is based on the element corresponding to the index of the key,

storing one or more reverse prefix tags of each reverse prefix node in response to determining that the elements of the reverse prefix node represents a valid reverse prefix of the sub-string, and

continuing to search for valid suffixes and reverse prefixes for each key received.

18. The machine readable medium of claim 17 further comprising

indicating the presence of the pre-defined string in response to determining that the reverse prefix tag and the suffix tag corresponding to the pre-defined string to be detected is stored, and

indicating the absence of the pre-defined string to be detected in response to determining the absence of the corresponding suffix tag or the reverse prefix tag.

19. The machine readable medium of claim 15 comprising

matching the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key,

matching the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a first branch of a modified reverse prefix tree, wherein the first reverse prefix node is determined based on the index of the key,

storing a first tag of the first branch in response to determining that the elements of the plurality reverse prefix nodes of the first branch represent a valid reverse prefix, and

indicating the presence of a first pre-defined string corresponding to the first tag stored.

20. The machine readable medium of claim 15 comprising

matching the suffix elements of the sub-string in the message with the elements of one or more suffix nodes present in a path until a suffix node representing a longest matching valid suffix is found, wherein a starting suffix element to begin matching the suffix elements is based on the element corresponding to the index of the key,

matching the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a first branch of a modified reverse prefix tree, wherein the first reverse prefix node is determined based on the index of the key,

matching the reverse prefix elements of the sub-string in the message with the elements of reverse prefix nodes, starting from a first reverse prefix node, of a second branch of a modified reverse prefix tree, if the sub-string comprises two reverse prefixes comprising an element corresponding to the first node of the first branch as the common element,

storing a first tag of the first branch and a second tag of the second branch in response to determining that the elements of the reverse prefix nodes of the first branch and the second branch represent two valid reverse prefixes, and

indicating the presence of a first pre-defined string and a second pre-defined string in the message.

21. A method of generating a search tree in a computer readable medium, comprising

generating a suffix tree comprising plurality of invalid suffix nodes and valid suffix nodes coupled to a suffix root node, wherein the valid suffix nodes comprise elements that represent valid suffixes of a plurality of pre-defined strings to be detected in a message, and

generating a reverse prefix tree comprising plurality of invalid prefix nodes and valid prefix nodes, wherein the valid reverse prefix nodes comprise elements that represent valid reverse suffixes of a plurality of pre-defined strings to be detected in a message.

22. The method of generating a search tree in a computer readable medium of claim 21 wherein each valid suffix node of the suffix tree is linked to the root prefix node of the reverse prefix tree using node-to-node pointers.

23. The method of generating a search tree in a computer readable medium of claim 21, comprising

generating the suffix tree comprising plurality of invalid suffix nodes and valid suffix nodes coupled to a suffix root node, wherein the valid suffix nodes comprise elements that represent valid suffixes of a plurality of pre-defined strings to be detected in the message, and

generating the reverse prefix tree comprising one or more branches, wherein each branch comprises one or more reverse prefix nodes together representing a longest matching reverse prefix.

24. The method of generating a search tree in a computer readable medium of claim 23 wherein each valid suffix node of the suffix tree is linked to a reverse prefix node of the one or more branches of the reverse prefix tree based on the element corresponding to the index of the key, wherein each valid suffix node and the corresponding reverse prefix node is linked using a node-to-node pointer.

25. The method of generating a search tree in a computer readable medium of claim 24 wherein the one or more branches of the reverse prefix tree comprising common elements are linked using one or more jump pointers.

26. A system comprising

a first network device of a plurality of network devices

to receive a message sent by a second network device,

to receive a key and the index of the key in response to determining the presence of a sub-string in the message, and

to detect whether a pre-defined string is present in the message based on searching a suffix and a reverse prefix in response to receiving the key and the index of the key.

27. The system of claim 26 wherein the second network device sends one or more packets comprising payloads to a first network device over the network.

28. The system of claim 26 the first network device comprises a router and the second network device comprises a client system, wherein the first network device and the second network device is coupled by the network.

29. The system of claim 26 the pre-defined string represents a signature.

30. The system of claim 26 the presence of the signature indicates presence of virus in the message.