Apparatus method and medium for detecting payload anomaly using n-gram distribution of normal data

• US 20050281291A1
• Filed: 11/12/2004
• Published: 12/22/2005
• Est. Priority Date: 11/12/2003
• Status: Active Grant

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Stolfo, Salvatore J., Wang, Ke
• Granted Patent: US 7,639,714 B2
• Time in Patent Office: Days
• US Class Current: 370/506
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06F 21/562 Static detection
• CPC Class Codes: G06F 21/563 by source code analysis
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 63/0218 Distributed architectures, e.g. distributed firewalls
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/029 Firewall traversal, e.g. tunnelling or, creating pinholes
• 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 method, apparatus and medium are provided for detecting anomalous payloads transmitted through a network. The system receives payloads within the network and determines a length for data contained in each payload. A statistical distribution is generated for data contained in each payload received within the network, and compared to a selected model distribution representative of normal payloads transmitted through the network. The model payload can be selected such that it has a predetermined length range that encompasses the length for data contained in the received payload. Anomalous payloads are then identified based on differences detected between the statistical distribution of received payloads and the model distribution. The system can also provide for automatic training and incremental updating of models.

Claims

1. A method of detecting anomalous payloads transmitted through a network, comprising the steps of:

receiving at least one payload within the network;

determining a length for data contained in the at least one payload;

generating a statistical distribution of data contained in the at least one payload received within the network;

comparing at least one portion of the generated statistical distribution to a corresponding portion of a selected model distribution representative of normal payloads transmitted through the network;

wherein the selected model distribution has a predetermined length range that encompasses the length for data contained in the at least one payload; and

identifying whether the at least one payload is an anomalous payload based, at least in part, on differences detected between the at least one portion of the statistical distribution for the at least one payload and the corresponding portion of the model distribution.

2. The method of claim 1, wherein the predetermined length range of the model distribution is based on partitions selected using kernel estimates for the statistical distribution of all normal payloads.

3. The method of claim 1, wherein the predetermined length range of the model distribution is based on partitions selected by applying at least one clustering algorithm to the statistical distribution of all normal payloads.

4. The method of claim 1, wherein the statistical distribution of the at least one payload is a byte value distribution of the average frequency and variance of data contained in the at least one payload, and the model distribution is a byte value distribution of the average frequency and variance representative of normal payloads.

5. The method of claim 1, wherein the statistical distribution of the at least one payload is a byte value distribution of data contained in the at least one payload, and the model distribution is a byte value distribution representative of normal payloads.

6. The method of claim 5, wherein the byte value distribution of the at least one payload is a byte frequency count of data contained in the at least one payload, and the model distribution is a byte frequency count for normal payloads.

7. The method of claim 5, wherein the byte value distribution of the at least one payload is a rank ordered byte frequency count of data contained in the at least one payload, and the model distribution is a rank ordered byte frequency count for normal payloads.

8. The method of claim 1, wherein:

the step of comparing further comprises a step of measuring a distance metric between the statistical distribution of data contained in the at least one payload and the model distribution; and

the step of identifying further comprises a step of identifying anomalous payloads as payloads that, at least in part, exceed a predetermined distance metric.

9. The method of claim 8, wherein the distance metric is calculated based on a Mahalanobis distance between the statistical distribution of data contained in the at least one payload and the model distribution.

10. The method of claim 8, wherein the statistical distribution of data contained in the at least one payload has a decaying profile, and wherein measurement of the distance metric is initiated at the decaying end.

11. The method of claim 8, further comprising the steps of:

setting an alert threshold corresponding to a desired number of alerts for detected anomalous payloads; and

automatically adjusting the predetermined distance metric until the alert threshold is reached.

12. The method of claim 1, wherein the predetermined length range is selected from at least a prefix portion of the model distribution.

13. The method of claim 1, wherein the predetermined length range is selected from at least a suffix portion of the model distribution.

14. The method of claim 1, wherein the predetermined length range is selected from at least a central portion of the model distribution

15. The method of claim 1, wherein the predetermined length range of the model distribution is selected from a partition group consisting of:

0-50 bytes, 50-150 bytes, 150-155 bytes, 0-255 bytes, less than 1000 bytes, greater than 2000 bytes, and greater than 10,000 bytes.

16. The method of claim 1, wherein the statistical distribution for the at least one payload and a statistical distribution of the model distribution are generated using an n-gram distribution, wherein each n-gram is a variable byte grouping.

17. The method of claim 16, wherein n is a mixed value of byte groupings.

18. The method of claim 16, wherein n=1.

19. The method of claim 16, wherein n=2.

20. The method of claim 16, wherein n=3.

21. The method of claim 1, further comprising a step of determining whether a detected anomalous payload is a virus or worm.

22. The method of claim 21, further comprising the steps of:

identifying a port which has been probed by the virus or worm;

comparing egress traffic to the statistical distribution for the virus or worm in order to detect probes to the same port on other machines; and

detecting propagation of the worm or virus based on the step of comparing.

23. The method of claim 21, further comprising a step of assigning different weight factors to selected byte values.

24. The method of claim 23, wherein higher weight factors are assigned to byte values corresponding to operational codes of a computer system.

25. The method of claim 21, further comprising a step of generating a signature for any anomalous payload determined to be a virus or worm.

26. The method of claim 25, wherein the step of generating a signature further comprises the steps of:

identifying the longest common string for data contained in the payload determined to be a virus or worm; and

generating the signature based, at least in part, on the longest common string.

27. The method of claim 25, wherein the step of generating further comprises the steps of:

identifying the longest common subsequence for data contained in the payload determined to be a virus or worm; and

generating the signature based, at least in part, on the longest common subsequence.

28. The method of claim 25, further comprising a step of exchanging virus or worm signatures with one or more servers.

29. A method of modeling payload data received in a network, comprising the steps of:

receiving a plurality of payload data in the network;

creating a payload length distribution for all payload data received;

partitioning the payload length distribution into a plurality of payload ranges;

generating a statistical distribution for each received payload data; and

constructing a model payload for each payload range based on the statistical distributions of all received payload data encompassed by the payload range.

30. The method of claim 29, wherein the step of constructing a model payload further comprises a step of computing at least one centroid for the statistical distribution of all payload data encompassed by each payload range.

31. The method of claim 29, wherein the payload length distribution is partitioned using kernel estimates.

32. The method of claim 29, wherein the payload length distribution is partitioned using at least one clustering algorithm.

33. The method of claim 29, further comprising the steps of:

creating a payload length distribution for each partition;

clustering the payload length distributions in each payload range into a plurality of clusters;

computing a plurality of centroids, one for each of the plurality of clusters; and

computing a model centroid for the plurality of centroids in each payload range;

wherein each model centroid is representative of normal payloads received in the network for the corresponding payload range.

34. The method of claim 29, wherein payload data is continually received, and the model payload is constructed based on all received payload data.

35. The method of claim 34, further comprising a step of aging out received payload data that is older than a predetermined threshold, and wherein the model payload is constructed based on current payload data.

36. The method of claim 29, wherein the statistical distributions are generated using an n-gram distribution, wherein each n-gram is a variable byte grouping.

37. The method of claim 36, wherein n is a mixed value of byte groupings.

38. The method of claim 36, wherein n=1.

39. The method of claim 36, wherein n=2.

40. The method of claim 36, wherein n=3.

41. The method of claim 29, wherein the statistical distribution of each received payload data is a byte value distribution for the received payload data.

42. The method of claim 41, wherein the byte value distribution of each received payload data is a byte frequency count of data contained in the received payload data.

43. The method of claim 41, wherein the byte value distribution of each received payload data is a rank ordered byte frequency count of data contained in the received payload data.

44. The method of claim 29, further comprising a step of automatically detecting when sufficient payload data has been received to construct the model payload.

45. The method of claim 44, wherein the step of automatically detecting further comprises the steps:

defining an epoch having a predetermined length of time;

receiving the plurality of payload data in the network for a current epoch;

constructing a current payload model as the model payload for the plurality of payload data received in the current epoch;

comparing the current payload model to the model payload for a previous epoch;

repeating the steps of receiving, constructing, and comparing until a predetermined stability condition is reached.

46. The method of claim 45, wherein the stability condition is based, at least in part, on the distance between the current payload model and the model payload for the previous epoch.

47. A system for detecting anomalous payloads transmitted through a network, comprising:

a computer coupled to the network, and receiving at least one payload through the network; and

at least one model distributions representative of normal payloads received through the network;

said computer being configured to;

determine a length for data contained in said at least one payload,

generate a statistical distribution of data contained in said at least one payload received within the network,

compare at least one portion of said generated statistical distribution to a corresponding portion of a selected one of said model distributions having a predetermined length range that encompasses the length for data contained in said at least one, and

identify whether said at least one payload is an anomalous payload based, at least in part, on differences detected between the at least one portion of the statistical distribution for said at least one payload and the corresponding portion of said selected model distribution.

48. The system of claim 47, wherein said computer is further configured to:

measure a distance metric between the statistical distribution of data contained in said at least one payload and said selected model distribution; and

identify anomalous payloads as payloads that, at least in part, exceed a predetermined distance metric.

49. The system of claim 47, wherein said computer is further configured to:

set an alert threshold corresponding to a desired number of alerts for detected anomalous payloads; and

automatically adjust said predetermined distance metric until said alert threshold is reached.

50. The system of claim 47, wherein said computer comprises at least one port and is further configured to:

determine whether a detected anomalous payload is a virus or worm;

identify one of said ports which has been probed by said virus or worm; and

detect propagation of said worm or virus by comparing egress traffic to the statistical distribution for said virus or worm in order to detect probes to the same port on at least one other computer.

51. A system for modeling payload data received in a network, comprising:

a computer coupled to the network, and receiving a plurality of payload data through the network;

said computer being configure to;

create a payload length distribution for all payload data received,

partition said payload length distribution into a plurality of payload ranges,

generate a statistical distribution for each received payload data, and

construct a model payload for each payload range based on the statistical distributions of all received payload data encompassed by said payload range.

52. The system of claim 51, wherein said computer is further configured to:

create a payload length distribution for each partition;

cluster said payload length distributions in each payload range into a plurality of clusters;

compute a plurality of centroids, one for each of said plurality of clusters; and

compute a model centroid for said plurality of centroids in each payload range;

each said model centroids being representative of normal payloads received in the network for said corresponding payload range.

53. The system of claim 51, wherein said computer is further configured to:

define an epoch having a predetermined length of time;

receive said plurality of payload data in the network for a current epoch;

construct a current payload model as the model payload for said plurality of payload data received in said current epoch;

compare said current payload model to the model payload for a previous epoch; and

continue to receive, construct, and compare until a predetermined stability condition is reached.

54. A computer readable medium carrying instructions executable by a computer for modeling payload data received in a network, said instructions causing said computer to perform the acts of:

receiving at least one payload through the network;

determining a length for data contained in the at least one payload;

generating a statistical distribution of data contained in the at least one payload received within the network;

comparing at least one portion of the generated statistical distribution to a corresponding portion of a selected one of said model distributions having a predetermined length range that encompasses the length for data contained in said received payload; and

identifying whether the at least one payload is an anomalous payload based, at least in part, on differences detected between the at least one portion of the statistical distribution for said at least one payload and the corresponding portion of said selected model distribution.

55. The computer readable medium claim 54, further comprising instructions for causing said computer to perform the acts of:

measuring a distance metric between the statistical distribution of data contained in said at least one payload and said selected model distribution; and

identifying anomalous payloads as payloads that, at least in part, exceed a predetermined distance metric.

56. The computer readable medium of claim 54, further comprising instructions for causing said computer to perform the acts of:

setting an alert threshold corresponding to a desired number of alerts for detected anomalous payloads; and

automatically adjusting said predetermined distance metric until said alert threshold is reached.

57. The computer readable medium of claim 54, further comprising instructions for causing said computer to perform the acts of:

determining whether a detected anomalous payload is a virus or worm;

identifying one of said ports which has been probed by said virus or worm; and

detecting propagation of said worm or virus by comparing egress traffic to the statistical distribution for said virus or worm in order to detect probes to the same port on at least one other computer.

58. A computer readable medium carrying instructions executable by a computer for modeling payload data received in a network, said instructions causing said computer to perform the acts of:

receiving a plurality of payload data through the network;

creating a payload length distribution for all payload data received;

partitioning said payload length distribution into a plurality of payload ranges;

generating a statistical distribution for each received payload data; and

constructing a model payload for each payload range based on the statistical distributions of all received payload data encompassed by the payload range.

59. The computer readable medium of claim 58, further comprising instructions for causing said computer to perform the steps of:

creating a payload length distribution for each partition;

clustering said payload length distributions in each payload range into a plurality of clusters;

computing a plurality of centroids, one for each of said plurality of clusters; and

computing a model centroid for said plurality of centroids in each payload range;

each said model centroids being representative of normal payloads received in the network for said corresponding payload range.

60. The computer readable medium of claim 58, further comprising instructions for causing said computer to perform the steps of:

defining an epoch having a predetermined length of time;

receiving said plurality of payload data in the network for a current epoch;

constructing a current payload model as the model payload for said plurality of payload data received in said current epoch;

comparing said current payload model to the model payload for a previous epoch; and

repeating said steps of receiving, constructing, and comparing until a predetermined stability condition is reached.

61. A system for detecting anomalous payloads transmitted through a network, comprising:

means for receiving at least one payload through the network;

means for determining a length for data contained in said at least one payload;

means for generating a statistical distribution of data contained in said at least one payload received within the network;

means for comparing at least one portion of the generated statistical distribution to a corresponding portion of a selected one of said model distributions having a predetermined length range that encompasses the length for data contained in said received payload; and

means for identifying whether the at least one payload is an anomalous payload based, at least in part, on differences detected between the at least one portion of the statistical distribution for said at least one payload and the corresponding portion of said selected model distribution.

62. The system of claim 61, further comprising:

means for measuring a distance metric between the statistical distribution of data contained in said at least one payload and said selected model distribution; and

means for identifying anomalous payloads as payloads that, at least in part, exceed a predetermined distance metric.

63. The system of claim 61, further comprising:

means for setting an alert threshold corresponding to a desired number of alerts for detected anomalous payloads; and

means for automatically adjusting said predetermined distance metric until said alert threshold is reached.

64. The system of claim 61, further comprising:

means for determining whether a detected anomalous payload is a virus or worm;

means for identifying one of said ports which has been probed by said virus or worm; and

means for detecting propagation of said worm or virus by comparing egress traffic to the statistical distribution for said virus or worm in order to detect probes to the same port on at least one other computer.

65. A system for modeling payload data received in a network, comprising:

means for receiving a plurality of payload data through the network;

means for creating a payload length distribution for all payload data received;

means for partitioning said payload length distribution into a plurality of payload ranges;

means for generating a statistical distribution for each received payload data; and

means for constructing a model payload for each payload range based on the statistical distributions of all received payload data encompassed by the payload range.

66. The system of claim 65, further comprising:

means for creating a payload length distribution for each partition;

means for clustering said payload length distributions in each payload range into a plurality of clusters;

means for computing a plurality of centroids, one for each of said plurality of clusters; and

means for computing a model centroid for said plurality of centroids in each payload range.

67. The system of claim 65, further comprising:

means for defining an epoch having a predetermined length of time;

means for receiving said plurality of payload data in the network for a current epoch;

means for constructing a current payload model as the model payload for said plurality of payload data received in said current epoch;

means for comparing said current payload model to the model payload for a previous epoch; and

means for repeating said steps of receiving, constructing, and comparing until a predetermined stability condition is reached.