Method, apparatus, and computer program product for detecting computer worms in a network

• US 8,032,937 B2
• Filed: 10/26/2004
• Issued: 10/04/2011
• Est. Priority Date: 10/26/2004
• Status: Active Grant

• Current Assignee: Mitre Corporation
• Original Assignee: Mitre Corporation
• Inventors: Ellis, Daniel R.
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): Tolentino, Roderick
• Application Number:
  US10/972,787
• Publication Number:
  US 20100199349A1
• Time in Patent Office: 2,534 Days
• Field of Search: 726 22- 25, 713150-158
• US Class Current: 726/24
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/566 Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

A worm is a malicious process that autonomously spreads itself from one host to another. To infect a host, a worm must somehow copy itself to the host. The method in which a worm transmits a copy of itself produces network traffic patterns that can be generalized as a traffic behavior. As a worm spreads itself across the network, the propagation of the traffic behavior can be witnessed as hosts are infected, one after another. By monitoring the network traffic for propagations of traffic behaviors, a presence of a worm can be detected.

Claims

1. A computer-based method for detecting worms in a computer network, comprising:

(a) monitoring traffic in the computer network to identify one or more traffic behavior occurrences;

(b) organizing the traffic behavior occurrences into a data structure representing a tree having nodes and links, wherein a node represents a host and a link represents one or more traffic behavior occurrences between two nodes, and wherein a new node is added to the tree after a host represented by the new node receives traffic from another host represented by another node already contained in the tree; and

(c) using the data structure to determine an average branching factor of each depth of the tree; and

(d) indicating that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

2. The method of claim 1, wherein step (a) comprises:

(1) detecting a sequence of packets between a first host and a second host that match a predetermined pattern; and

(2) indicating a traffic behavior occurrence when a matching sequence is detected.

3. The method of claim 2, wherein step (1) comprises:

(i) detecting first packets indicating the establishment of a TCP connection between a first host and a second host;

(ii) detecting a second packet representing a TCP FIN message transmitted from the first host to the second host; and

(iii) detecting an absence of a third packet representing a TCP RST or TCP FIN message transmitted from the second host to the first host, thereby identifying a half-open TCP connection traffic behavior.

4. The method of claim 1, wherein step (a) comprises monitoring traffic between a first host and a second host to identify one or more traffic behavior occurrences, wherein the identified traffic behavior occurrence is a transmission of a packet from the first host to the second host.

5. The method of claim 1, wherein step (c) comprises:

(1) using the data structure to determine the depth of the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the depth is greater than a threshold.

6. The method of claim 1, wherein step (c) comprises:

(1) using the data structure to determine the number of nodes in the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the number of nodes is greater than a threshold.

7. The method of claim 1, further comprising:

(1) using the data structure to determine an average branching factor of the internal nodes of the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

8. The method of claim 1, further comprising:

(1) using the data structure to determine an average propagation time of the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the average propagation time is less than a threshold.

9. The method of claim 1, further comprising:

(1) selecting a subtree of the data structure wherein the subtree is composed of a first node, a second node, a third node, a first link connecting the first node and the second node, and a second link connecting the second node and the third node; and

(2) using the subtree to identify the host represented by the second node as a possible worm-infected host in the computer network.

10. The method of claim 9, wherein step (2) comprises identifying the host represented by the second node as a possible worm-infected host exhibiting an alpha-in alpha-out worm-like symptom if the first link and the second link indicate the same traffic behavior occurrence.

11. The method of claim 9, wherein step (2) comprises identifying the host represented by the second node as a possible worm-infected host exhibiting a server-to-client worm-like symptom if the first link and the second link indicate the same traffic behavior occurrence wherein the traffic behavior occurrence indicates that a packet was sent to a particular port.

12. The method of claim 1, further comprising:

(e) identifying one or more hosts in the data structure that exhibited the same traffic behavior as the possible worm-infected host to indicate that the hosts are possible worm-infected hosts in the computer network.

13. The method of claim 1, further comprising:

(1) selecting a host in the data structure that should be prohibited from exhibiting a traffic behavior;

(2) using the data structure to determine if the host exhibited the traffic behavior; and

(3) indicating that the host is a possible worm-infected host if the host exhibited the traffic behavior.

14. The method of claim 1, wherein step (b) comprises:

(1) placing the traffic behavior occurrences into a sequence;

(2) creating a data structure representing a tree for at least one host in the sequence wherein the root of the tree represents the host;

(3) selecting a traffic behavior occurrence from the start of the sequence;

(4) identifying a source host and a destination host from the traffic behavior occurrence wherein the source host initiated the traffic behavior and the destination host was the target of the traffic behavior;

(5) adding the destination host as a leaf node to the tree if the destination host is not already in the tree and there exists a node in the tree that represents the source host;

(6) removing the traffic behavior occurrence from the start of the sequence; and

(7) repeating steps (3)-(6) for all traffic behavior occurrences in the sequence.

15. The method of claim 1, wherein addition of the new node to the data structure reflects a causal relationship between the host represented by the new node and the another host represented by the another node.

16. The method of claim 15, wherein the causal relationship is time based, as the new node is added to the data structure after occurrence of the event.

33. The method of claim 1, further comprising organizing the traffic behavior occurrences into a descendants matrix for each type of traffic behavior, wherein the descendants matrix includes a vector of ports.

34. The method of claim 33, wherein each vector of ports includes a link to a vector of depths, the vector of depths comprising hosts which exhibited a traffic behavior initiated on a particular port.

35. The method of claim 34, wherein each vector of depths includes a linked list of host nodes indicating that a host at one depth exhibited a traffic behavior with a host from the previous depth.

36. The method of claim 33, further comprising:

examining the descendants matrix to determine if propagation of the traffic behavior occurrences exhibits worm-like propagation behavior.

37. The method of claim 33, further comprising:

(1) determining a depth associated with the descendants matrix; and

(2) indicating that at least one host of the descendants matrix is a possible worm-infected host if the depth is greater than a threshold.

38. The method of claim 33, further comprising:

(1) determining a number of nodes associated with the descendants matrix; and

(2) indicating that at least one host in the descendants matrix is a possible worm-infected host if the number of nodes is greater than a threshold.

39. The method of claim 33, further comprising:

(1) determining an average branching factor of each depth of the tree using the descendants matrix; and

(2) indicating that at least one host in the descendants matrix is a possible worm-infected host if the average branching factor is greater than a threshold.

40. The method of claim 33, further comprising:

(1) determining an average branching factor of internal nodes of the tree using the descendants matrix; and

(2) indicating that at least one host in the descendants matrix is a possible worm-infected host if the average branching factor is greater than a threshold.

41. The method of claim 33, further comprising:

(1) determining an average propagation time of the tree using the descendants matrix; and

(2) indicating that at least one host in the descendants matrix is a possible worm-infected host if the average propagation time is less than a threshold.

17. An apparatus for detecting worms in a computer network, comprising:

a monitoring module to monitor traffic in the computer network to identify one or more traffic behavior occurrences;

an organizing module to organize the traffic behavior occurrences into a data structure representing a tree having nodes and links, wherein a node represents a host and a link represents one or more traffic behavior occurrences between two nodes, and wherein a new node is added to the tree after a host represented by the new node receives traffic from another host represented by another node already contained in the tree; and

a using module to use the data structure to determine an average branching factor of each depth of the tree; and

an indicating module to indicate that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

18. The apparatus according to claim 17, wherein the monitoring module comprises:

a first detecting module to detect a sequence of packets between a first host and a second host that match a predetermined pattern; and

a second indicating module to indicate a traffic behavior occurrence when a matching sequence is detected.

19. The apparatus according to claim 18, wherein the first detecting module comprises:

a second detecting module for detecting first packets indicating the establishment of a TCP connection between a first host and a second host;

a third detecting module for detecting a second packet representing a TCP FIN message transmitted from the first host to the second host; and

a fourth detecting module for detecting an absence of a third packet representing a TCP RST or TCP FIN message transmitted from the second host to the first host, thereby identifying a half-open TCP connection traffic behavior.

20. The apparatus according to claim 17, wherein the monitoring module monitors traffic between a first host and a second host to identify one or more traffic behavior occurrences, wherein the identified traffic behavior occurrence is a transmission of a packet from the first host to the second host.

21. The apparatus according to claim 17, wherein the using module:

uses the data structure to determine the depth of the tree and indicates that at least one host of the tree is a possible worm-infected host if the depth is greater than a threshold.

22. The apparatus according to claim 17, wherein the using module:

uses the data structure to determine the number of nodes in the tree and

indicates that at least one host of the tree is a possible worm-infected host if the number of nodes is greater than a threshold.

23. The apparatus according to claim 17, wherein the using module

uses the data structure to determine an average branching factor of each depth of the tree and

indicates that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

24. The apparatus according to claim 17, wherein the using module:

uses the data structure to determine an average branching factor of the internal nodes of the tree; and

indicates that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

25. The apparatus according to claim 17, wherein the using module

uses the data structure to determine an average propagation time of the tree;

and

indicates that at least one host of the tree is a possible worm-infected host if the average propagation time is less than a threshold.

26. The apparatus according to claim 17, wherein the using module:

selects a subtree of the data structure wherein the subtree is composed of a first node, a second node, a third node, a first link connecting the first node and the second node, and a second link connecting the second node and the third node and

uses the subtree to identify the host represented by the second node as a possible worm-infected host in the computer network.

27. The apparatus according to claim 26, wherein the host represented by the second node as a possible worm-infected host exhibits an alpha-in alpha-out worm-like symptom if the first link and the second link indicate the same traffic behavior occurrence.

28. The apparatus according to claim 26, wherein the host represented by the second node as a possible worm-infected host exhibits a server-to-client worm-like symptom if the first link and the second link indicate the same traffic behavior occurrence wherein the traffic behavior occurrence indicates that a packet was sent to a particular port.

29. The apparatus according to claim 17, further comprising:

an identifying module to identify one or more hosts in the data structure that exhibited the same traffic behavior as the possible worm-infected host to indicate that the hosts are possible worm-infected hosts in the computer network.

30. The apparatus according to claim 17, wherein the using module is further configured to:

select a host in the data structure that should be prohibited from exhibiting a traffic behavior;

use the data structure to determine if the host exhibited the traffic behavior; and

indicate that the host is a possible worm-infected host if the host exhibited the traffic behavior.

31. The apparatus according to claim 17, wherein the organizing module is further configured to:

place the traffic behavior occurrences into a sequence;

create a data structure representing a tree for at least one host in the sequence wherein the root of the tree represents the host; and

process the following functions for traffic behavior occurrences in the sequence;

selecting a traffic behavior occurrence from the start of the sequence,

identifying a source host and a destination host from the traffic behavior occurrence, wherein the source host initiated the traffic behavior and the destination host was the target of the traffic behavior,

adding the destination host as a leaf node to the tree if the destination host is not already in the tree and there exists a node in the tree that represents the source host, and

removing the traffic behavior occurrence from the start of the sequence.

32. A computer-based method for detecting worms in a computer network, comprising:

(a) monitoring traffic in the computer network to identify one or more traffic behavior occurrences;

(b) generating a graph-based representation of the traffic behavior occurrences comprising a tree having nodes and links, wherein a node represents a host and a link represents one or more traffic behavior occurrences between two nodes, and wherein a new node is added to the tree after a host represented by the new node receives traffic from another host represented by another node already contained in the tree; and

(c) using the graph based representation to determine an average branching factor of each depth of the tree; and

(d) indicating that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

42. A computer program product including a non-transitory computer-readable medium having instructions stored thereon that, when executed by a computing device, cause the computing device to perform operations comprising:

(a) monitoring traffic in the computer network to identify one or more traffic behavior occurrences;

(b) organizing the traffic behavior occurrences into a data structure representing a tree having nodes and links, wherein a node represents a host and a link represents one or more traffic behavior occurrences between two nodes, and wherein a new node is added to the tree after a host represented by the new node receives traffic from another host represented by another node already contained in the tree;

(c) using the data structure to determine an average branching factor of each depth of the tree; and

(d) indicating that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

43. The computer program product of claim 42, wherein step (a) comprises:

(1) detecting a sequence of packets between a first host and a second host that match a predetermined pattern; and

(2) indicating a traffic behavior occurrence when a matching sequence is detected.

44. The computer program product of claim 43, wherein step

(1) comprises:

(i) detecting first packets indicating the establishment of a TCP connection between a first host and a second host;

(ii) detecting a second packet representing a TCP FIN message transmitted from the first host to the second host; and

(iii) detecting an absence of a third packet representing a TCP RST or TCP FIN message transmitted from the second host to the first host, thereby identifying a half-open TCP connection traffic behavior.

45. The computer program product of claim 42, wherein step (a) comprises monitoring traffic between a first host and a second host to identify one or more traffic behavior occurrences, wherein the identified traffic behavior occurrence is a transmission of a packet from the first host to the second host.

46. The computer program product of claim 42, wherein step (c) comprises:

(1) using the data structure to determine the depth of the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the depth is greater than a threshold.

47. The computer program product of claim 42, wherein step (c) comprises:

(1) using the data structure to determine the number of nodes in the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the number of nodes is greater than a threshold.

48. The computer program product of claim 42, further comprising:

(1) using the data structure to determine an average branching factor of the internal nodes of the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the average branching factor is greater than a threshold.

49. The computer program product of claim 42, further comprising:

(1) using the data structure to determine an average propagation time of the tree; and

(2) indicating that at least one host of the tree is a possible worm-infected host if the average propagation time is less than a threshold.

50. The computer program product of claim 42, further comprising:

(1) selecting a subtree of the data structure wherein the subtree is composed of a first node, a second node, a third node, a first link connecting the first node and the second node, and a second link connecting the second node and the third node; and

(2) using the subtree to identify the host represented by the second node as a possible worm-infected host in the computer network.

51. The computer program product of claim 50, wherein step (2) comprises identifying the host represented by the second node as a possible worm-infected host exhibiting an alpha-in alpha-out worm-like symptom if the first link and the second link indicate the same traffic behavior occurrence.

52. The computer program product of claim 50, wherein step (2) comprises identifying the host represented by the second node as a possible worm-infected host exhibiting a server-to-client worm-like symptom if the first link and the second link indicate the same traffic behavior occurrence wherein the traffic behavior occurrence indicates that a packet was sent to a particular port.

53. The computer program product of claim 42, the operations further comprising:

(e) identifying one or more hosts in the data structure that exhibited the same traffic behavior as the possible worm-infected host to indicate that the hosts are possible worm-infected hosts in the computer network.

54. The computer program product of claim 42, the operations further comprising:

(1) selecting a host in the data structure that should be prohibited from exhibiting a traffic behavior;

(2) using the data structure to determine if the host exhibited the traffic behavior; and

(3) indicating that the host is a possible worm-infected host if the host exhibited the traffic behavior.

55. The computer program product of claim 42, wherein step (b) comprises:

(1) placing the traffic behavior occurrences into a sequence;

(2) creating a data structure representing a tree for at least one host in the sequence wherein the root of the tree represents the host;

(3) selecting a traffic behavior occurrence from the start of the sequence;

(4) identifying a source host and a destination host from the traffic behavior occurrence wherein the source host initiated the traffic behavior and the destination host was the target of the traffic behavior;

(5) adding the destination host as a leaf node to the tree if the destination host is not already in the tree and there exists a node in the tree that represents the source host;

(6) removing the traffic behavior occurrence from the start of the sequence; and

(7) repeating steps (3)-(6) for all traffic behavior occurrences in the sequence.