Detection of signatures in disordered message segments

• US 7,957,390 B2
• Filed: 05/18/2005
• Issued: 06/07/2011
• Est. Priority Date: 04/08/2005
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Stack, Eoghan, O'Keeffe, Daniel Martin, Furlong, Peter, Loughran, Kevin
• Primary Examiner(s): Ryman; Daniel J
• Assistant Examiner(s): BLANTON, JOHN D
• Application Number:
  US11/133,039
• Publication Number:
  US 20060227787A1
• Time in Patent Office: 2,211 Days
• Field of Search: 370/394
• US Class Current: 370/394
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/166 at the transport layer

Abstract

A method of detecting signatures in message segments comprises employing a state machine for the detection of character strings in the message segments. The state machine executes for each input character a transition determined by a current state of the machine and a current input character. The message segments conform to TCP or other ordering transport protocol. The order of arrival of the message segments is monitored. In the event that an intermediate message segment is missing between a processed segment and an immediately subsequent message segment, the current state of said state machine at the end of the said processed segment is stored. The machine is restarted from its null or datum state for the examination of the immediately subsequent message segment, which is then temporarily stored. When the missing segment eventually arrives, it and the stored segment are successively examined for signatures by means of the state machine, beginning at the stored state. The invention allows for examination of overlapping signatures without requiring re-assembly of the segments or substantial buffering.

Claims

1. A method of detecting digital signatures in messages transmitted over a packet based network, said messages being composed of message segments having a predefined order, said method comprising:

processing a first received message segment using a deterministic finite state automaton (DFA) operating on a network unit, said DFA defining each of a plurality of digital signatures associated with unwanted intrusion as a respective succession of states;

storing a first state of the DFA after processing the first received message segment and forwarding the first received message segment;

receiving a third message segment out of the predefined order;

processing the third message segment using the DFA starting at a null state;

receiving a second message segment following processing of the third message segment, wherein the second message segment is a next message segment in the predefined order following the first received message, wherein the third message segment is a next message segment in the predefined order following the second received message; and

processing the second message segment using the DFA starting at the stored first state.

2. The method of claim 1, further comprising:

storing the third message segment; and

storing a second state of the DFA after processing the third message segment.

3. The method of claim 2, further comprising:

in response to a determination that no digital signature is detected in the second message segment and the stored third message segment,

storing a third state of the DFA for subsequent use after the processing of the second message segment and the stored third message segment.

4. The method of claim 2, further comprising:

receiving a fourth message segment prior to receiving the second message segment, wherein the fourth message segment follows the third message segment in the predefined order; and

processing the fourth message segment using the DFA starting at the second state.

5. The method of claim 4, wherein processing the fourth message segment further comprises processing the fourth message segment without storing the fourth message segment in a buffer.

6. The method of claim 4, further comprising:

storing a fourth state of the DFA after processing the fourth message segment.

7. The method of claim 6, further comprising:

receiving a fifth message segment following processing of the second message segment and the third message segment, wherein the fifth message segment follows the fourth message segment in the predefined order; and

processing the fifth message segment using the DFA starting at the fourth state.

8. The method of claim 1, wherein the message segments conform to an ordering transport protocol.

9. The method of claim 1, further comprising:

discarding a message associated with the received message segments if one of the plurality of digital signatures is detected by the DFA in at least one of the second message segment and the third message segment.

10. A network unit for detecting digital signatures in messages transmitted over a packet based network, said messages being composed of message segments having predefined order, said network unit comprising:

a deterministic finite state automaton (DFA) operating on the network unit, said DFA defining each of a plurality of digital signatures associated with unwanted intrusion as a respective succession of states; and

a controller configured to process a first received message segment using the DFA, to store a first state of the DFA after the first received message segment has been processed, wherein the controller is further configured to receive a third message segment out of the predefined order, to process the third message segment using the DFA at a null state, to receive a second message segment following processing of the third message segment, wherein the second message segment is a next message segment in the predefined order following the first received message, wherein the third message segment is a next message segment in the predefined order following the second received message, and to process the second message segment using the DFA starting at the stored first state.

11. The network unit of claim 10, further comprising:

a buffer, wherein the controller is further configured to store the third message segment in the buffer and to store a second state of the DFA after processing the third message segment.

12. The network unit of claim 11, wherein, in response to a determination that no digital signature is detected in the second message segment and the stored third message segment, the controller is further configured to store a third state of the DFA for subsequent use after the processing of the second message segment and the stored third message segment.

13. The network unit of claim 11, wherein the controller is further configured to receive a fourth message segment prior to receiving the second message segment, wherein the fourth message segment follows the third message segment in the predefined order, and to process the fourth message segment using the DFA starting at the second state.

14. The network unit of claim 13, wherein the controller is further configured to process the fourth message segment without storing the fourth message segment in the buffer.

15. The network unit of claim 13, wherein the controller is further configured to store a fourth state of the DFA after processing the fourth message segment.

16. The network unit of claim 10, wherein the message segments conform to an ordering transport protocol.

17. The network unit of claim 10, wherein the controller is further configured to discard a message associated with the received message segments if one of the plurality of digital signatures is detected by the DFA in at least one of the second message segment and the third message segment.