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

• US 20100199349A1
• Filed: 10/26/2004
• Published: 08/05/2010
• Est. Priority Date: 10/26/2004
• Status: Active Grant

• Current Assignee: Mitre Corporation
• Original Assignee: Mitre Corporation
• Inventors: Ellis, Daniel R.
• Granted Patent: US 8,032,937 B2
• Time in Patent Office: Days
• 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 identify a possible worm-infected host in the computer network.

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, wherein step (c) comprises:

(1) using the data structure to determine an average branching factor of each depth 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, wherein step (c) comprises:

(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.

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

(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.

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

(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.

11. The method of claim 10, 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.

12. The method of claim 10, 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.

13. The method of claim 1, further comprising:

(d) 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.

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

(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.

15. 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.

47. 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.

48. The method of claim 47, 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.

49. The method of claim 48, 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.

50. The method of claim 47, further comprising:

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

51. The method of claim 47, 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.

52. The method of claim 47, 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.

53. The method of claim 47, 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.

54. The method of claim 47, 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.

55. The method of claim 47, 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.

16. 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

an using module to use the data structure to identify a possible worm-infected host in the computer network.

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

detecting means for detecting a sequence of packets between a first host and a second host that match a predetermined pattern; and

indicating means for indicating a traffic behavior occurrence when a matching sequence is detected.

18. The apparatus according to claim 17, wherein the detecting means comprises:

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

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

detecting means 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.

19. The apparatus according to claim 16, wherein the monitoring module comprises monitoring means for 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.

20. The apparatus according to claim 16, wherein the using module comprises:

using means for using the data structure to determine the depth of the tree; and

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

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

using means for using the data structure to determine the number of nodes in the tree; and

indicating means for 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.

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

using means for using the data structure to determine an average branching factor of each depth of the tree; and

indicating means for 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.

23. The apparatus according to claim 16, wherein the using module comprises:

using means for using the data structure to determine an average branching factor of the internal nodes of the tree; and

indicating means for 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.

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

using means for using the data structure to determine an average propagation time of the tree; and

indicating means for 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.

25. The apparatus according to claim 16, wherein the using module comprises:

selecting means for 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

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

26. The apparatus according to claim 25, wherein the using means comprises identifying means for 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.

27. The apparatus according to claim 25, wherein the using means comprises identifying means for 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.

28. The apparatus according to claim 16, further comprising:

identifying means for 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.

29. The apparatus according to claim 16, wherein the using module comprises:

selecting means for selecting a host in the data structure that should be prohibited from exhibiting a traffic behavior;

using means for using the data structure to determine if the host exhibited the traffic behavior; and

indicating means for indicating that the host is a possible worm-infected host if the host exhibited the traffic behavior.

30. The apparatus according to claim 16, wherein the organizing module comprises:

placing means for placing the traffic behavior occurrences into a sequence;

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

processing means for performing 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.

31. A computer program product comprising a computer useable medium having control logic stored therein, said control logic causing a processor to detect worms in a computer network, the control logic comprising:

first computer readable program code means for causing a processor to monitor traffic in the computer network to identify one or more traffic behavior occurrences;

second computer readable program code means for causing a processor 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

third computer readable program code means for causing a processor to use the data structure to identify a possible worm-infected host in the computer network.

32. The computer program product according to claim 31, wherein the first computer readable program code means comprises:

fourth computer readable program code means for causing a processor to detect a sequence of packets between a first host and a second host that match a predetermined pattern; and

fifth computer readable program code means for causing a processor to indicate a traffic behavior occurrence when a matching sequence is detected.

33. The computer program product according to claim 32, wherein the fourth computer readable program code means comprises:

sixth computer readable program code means for causing a processor to detect first packets indicating the establishment of a TCP connection between a first host and a second host;

seventh computer readable program code means for causing a processor to detect a second packet representing a TCP FIN message transmitted from the first host to the second host; and

eighth computer readable program code means for causing a processor to detect 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.

34. The computer program product according to claim 31, wherein the first computer readable program code means comprises a computer readable program code means for causing a processor to monitor 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.

35. The computer program product according to claim 31, wherein the third computer readable program code means comprises:

fourth computer readable program code means for causing a processor to use the data structure to determine the depth of the tree; and

fifth computer readable program code means for causing a processor to indicate that at least one host of the tree is a possible worm-infected host if the depth is greater than a threshold.

36. The computer program product according to claim 31, wherein the third computer readable program code means comprises:

fourth computer program product means for causing a processor to use the data structure to determine the number of nodes in the tree; and

fifth computer readable program code means for causing a processor to indicate that at least one host of the tree is a possible worm-infected host if the number of nodes is greater than a threshold.

37. The computer program product according to claim 31, wherein the third computer readable program code means comprises:

fourth computer readable program code means for causing a processor to use the data structure to determine an average branching factor of each depth the tree; and

fifth computer readable program code means for causing a processor 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.

38. The computer program product according to claim 31, wherein the third computer readable program code means comprises:

fourth computer readable program code means for causing a processor to use the data structure to determine an average branching factor of the internal nodes of the tree; and

fifth computer readable program code means for causing a processor 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.

39. The computer program product according to claim 31, wherein the third computer readable program code means comprises:

fourth computer readable program code means for causing a processor to use the data structure to determine an average propagation time of the tree; and

fifth computer readable program code means for causing a processor to indicate that at least one host of the tree is a possible worm-infected host if the average propagation time is less than a threshold.

40. The computer program product according to claim 31, wherein the third computer readable program code means comprises:

fourth computer readable program code means for causing a processor to select 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

fifth computer readable program code means for causing a processor to use the subtree to identify the host represented by the second node as a possible worm-infected host in the computer network.

41. The computer program product according to claim 40, wherein the fifth computer readable program code means comprises a computer readable program code means for causing a processor to identify 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.

42. The computer program product according to claim 40, wherein the fifth computer readable program code means comprises a computer readable program code means for causing a processor to identify 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.

43. The computer program product according to claim 31, the control logic further comprising:

fourth computer readable program code means for causing a processor 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.

44. The computer program product according to claim 31, wherein the third computer readable program code means comprises:

fourth computer readable program code means for causing a processor to select a host in the data structure that should be prohibited from exhibiting a traffic behavior;

fifth computer readable program code means for causing a processor to use the data structure to determine if the host exhibited the traffic behavior; and

sixth computer readable program code means for causing a processor to indicate that the host is a possible worm-infected host if the host exhibited the traffic behavior.

45. The computer program product according to claim 31, wherein the second computer readable program code means comprises:

fourth computer readable program code means for causing a processor to place the traffic behavior occurrences into a sequence;

fifth computer readable program code means for causing a processor to 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

sixth computer readable program code means for causing a processor to process traffic behavior occurrences in the sequence as follows;

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.

46. 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 identify a possible worm-infected host in the computer network.