Methods of unsupervised anomaly detection using a geometric framework

• US 8,544,087 B1
• Filed: 01/30/2008
• Issued: 09/24/2013
• Est. Priority Date: 12/14/2001
• 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: Eskin, Eleazar, Stolfo, Salvatore J., Arnold, Andrew Oliver, Prerau, Michael, Portnoy, Leonid
• Primary Examiner(s): TRAN, ELLEN C
• Application Number:
  US12/022,425
• Time in Patent Office: 2,064 Days
• Field of Search: 726/22, 726/23, 726/24
• US Class Current: 726/22
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

A method for unsupervised anomaly detection, which are algorithms that are designed to process unlabeled data. Data elements are mapped to a feature space which is typically a vector space . Anomalies are detected by determining which points lies in sparse regions of the feature space. Two feature maps are used for mapping data elements to a feature apace. A first map is a data-dependent normalization feature map which we apply to network connections. A second feature map is a spectrum kernel which we apply to system call traces.

Claims

1. A method for unsupervised detection of an anomaly in the operation of a computer system comprising the steps of:

(a) receiving a set of unlabeled data instances which do not indicate any anomaly occurrence, the set of unlabeled data instances corresponding to a computer operation and having features;

(b) implicitly mapping the set of unlabeled data instances to a feature space;

(c) calculating one or more sparse regions in the feature space; and

(d) designating one or more data instances from the set of unlabeled data instances as an anomaly if said one or more data instances is located in said one or more sparse regions of the feature space.

2. The method of claim 1, wherein receiving the set of unlabeled data instances comprises receiving the set of unlabeled data instances from an audit stream.

3. The method of claim 2, wherein receiving the set of unlabeled data instances comprises receiving a set of system call trace data.

4. The method of claim 2, wherein receiving the set of unlabeled data instances comprises receiving a set of network connections records data.

5. The method of claim 4, wherein receiving the set of unlabeled data instances comprises receiving a sequence of TCP packets.

6. The method of claim 5, wherein the features of the TCP packets comprise at least one of a duration of the network connection, a protocol type, and number of byte transferred by the connection, and an indication of the status of the connection.

7. The method of claim 1, wherein implicitly mapping the set of unlabeled data instances comprises implicitly mapping the set of unlabeled data instances to a vector space.

8. The method of claim 1, wherein implicitly mapping the set of unlabeled data instances comprises normalizing the set of unlabeled data instances based on respective values of features of the set of unlabeled data instances.

9. The method of claim 8, further comprising normalizing each data instance in the set of unlabeled data instances based on a corresponding number of standard deviations of each data instance from a mean of the set of unlabeled data instances.

10. The method of claim 1, wherein implicitly mapping the set of unlabeled data instances comprises applying a convolution kernel to the set of unlabeled data instances.

11. The method of claim 10, wherein applying a convolution kernel comprises applying a spectrum kernel to the set of unlabeled data instances.

12. The method of claim 1, further comprising, after implicitly mapping the set of unlabeled data instances to a feature space, associating each data instance in the set of unlabeled data instances with one of a plurality of clusters.

13. The method of claim 12, further comprising, determining a distance between a selected data instance and a nearest cluster in the plurality of clusters.

14. The method of claim 13, further comprising, if the distance between the selected data instance and the nearest cluster is less than or equal to a predetermined cluster width, associating the selected data instance with the selected cluster.

15. The method of claim 13, further comprising, if the distance between the selected data instance and the selected cluster is greater than the cluster width, creating a new cluster and associating the selected data instance with the new cluster.

16. The method of claim 12, further comprising, determining a percentage of clusters having the greatest number of data instances respectively associated therewith.

17. The method of claim 16, wherein the percentage of clusters having the greatest number of data instances are labeled as dense regions in the feature space and wherein the remaining clusters are labeled as sparse regions in the feature space.

18. The method of claim 17, wherein designating one or more data instances as an anomaly comprises associating each data instance in the set of unlabeled data instances with a respective cluster.

19. The method of claim 1, further comprising, determining a sum of distances between a selected data instance and k nearest data instances to the selected data instance, wherein k is a predetermined value.

20. The method of claim 19, wherein determining the sum of the distances comprises determining a nearest cluster as a cluster corresponding to a shortest distance between the respective center of the cluster and the selected data instance.

21. The method of claim 20, further comprising, if a distance between the selected data instance and each data instance in the nearest cluster is less than a predetermined minimum distance, designating the point the cluster as one of the k nearest neighbors.

22. The method of claim 21, wherein designating one or more data instances as an anomaly comprises determining whether sum of the distances to the k nearest neighbors exceeds a predetermined threshold.

23. The method of claim 1, wherein designating one or more data instances as an anomaly comprises determining a decision function to separate the set of data instances from an origin and computing the decision function.

24. A method for unsupervised detection of an anomaly in the operation of a computer system based on a set of unlabeled data instances corresponding to computer operation and having features, comprising the steps of

(a) receiving a set of unlabeled data instances which do not indicate any anomaly occurrence;

(b) implicitly mapping the set of unlabeled data instances to a feature space comprising normalizing the set of unlabeled data instances based on respective values of the features;

(c) calculating one or more sparse regions in the feature space; and

(d) designating one or more data instances from the set of unlabeled data instances as an anomaly if said one or more data instances is located in said one or more sparse regions of the feature space.

25. The method of claim 24, wherein receiving the set of unlabeled data instances comprises receiving the set of unlabeled data instances from an audit stream.

26. The method of claim 25, wherein receiving the set of unlabeled data instances comprises receiving a set of network connections records data.

27. The method of claim 26, wherein receiving a set of unlabeled data instances comprises receiving a sequence of TCP packets.

28. The method of claim 27, wherein the features of the TCP packets comprise at least one of a duration of the network connection, a protocol type, and number of byte transferred by the connection, and an indication of the status of the connection.

29. The method of claim 24, wherein normalizing the set of unlabeled data instances comprises implicitly mapping the set of unlabeled data instances to a vector space.

30. The method of claim 29, wherein normalizing the set of unlabeled data instances comprises normalizing each data instance in the set of unlabeled data instances based on a corresponding number of standard deviations of each data instance from a mean of the set of unlabeled data instances.

31. The method of claim 24, further comprising, after normalizing the set of unlabeled data instances, associating each data instance in the set of unlabeled data instances with a plurality of clusters.

32. The method of claim 31, further comprising, determining a distance between a selected data instance and a nearest cluster in the plurality of clusters.

33. The method of claim 32, further comprising, if the distance between the selected data instance and the nearest cluster is less than or equal to a predetermined cluster width, associating the selected data instance with the selected cluster.

34. The method of claim 32, further comprising, if the distance between the selected data instance and the selected cluster is greater than the cluster width, creating a new cluster and associating the selected data instance with the new cluster.

35. The method of claim 31, further comprising, determining a percentage of clusters having the greatest number of data instances respectively associated therewith.

36. The method of claim 35, wherein the percentage of clusters having the greatest number of data instances are labeled as dense regions in the feature space and wherein the remaining clusters are labeled as sparse regions in the feature space.

37. The method of claim 36, wherein designating one or more data instances as an anomaly comprises associating each data instance in the set of unlabeled data instances with a respective cluster.

38. The method of claim 24, further comprising, determining a sum of distances between a selected data instance and k nearest data instances to the selected data instance, wherein k is a predetermined value.

39. The method of claim 38, wherein determining the sum of the distances comprises determining a nearest cluster as a cluster corresponding to a shortest distance between the respective center of the cluster and the selected data instance.

40. The method of claim 39, further comprising, if a distance between the selected data instance and each data instance in the nearest cluster is less than a predetermined minimum distance, designating the point the cluster as one of the k nearest neighbors.

41. The method of claim 40, wherein designating one or more data instances as an anomaly comprises determining whether sum of the distances to the k nearest neighbors exceeds a predetermined threshold.

42. The method of claim 24, wherein designating one or more data instances as an anomaly comprises determining a decision function to separate the set of data instances from an origin, and computing the decision function.

43. A method for unsupervised detection of an anomaly in the operation of a computer system based on a set of unlabeled data instances corresponding to computer operation and having features, comprising the step of:

(a) receiving a set of unlabeled data instances which do not indicate any anomaly occurrence, the set of unlabeled data instances corresponding to a computer operation and having features;

(b) implicitly mapping the set of unlabeled data instances to a feature space comprising applying a string kernel to the set of unlabeled data instances;

(c) calculating one or more sparse regions in the feature space; and

(d) designating one or more data instances from the set of unlabeled data instances as an anomaly if said one or more data instances is located in said one or more sparse regions of the feature space.

44. The method of claim 43, wherein receiving the set of unlabeled data instances comprises receiving the set of unlabeled data instances from an audit stream.

45. The method of claim 44, wherein receiving a set of unlabeled data instances comprises receiving a set of system call trace data.

46. The method of claim 44, wherein applying a string kernel to the set of unlabeled data instances comprises applying a spectrum kernel to the set of unlabeled data instances.

47. The method of claim 43, further comprising, after applying a string kernel to the set of unlabeled data instances, associating each data instance in the set of unlabeled data instances with a plurality of clusters.

48. The method of claim 47, further comprising, determining a distance between a selected data instance and a nearest cluster in the plurality of clusters.

49. The method of claim 48, further comprising, if the distance between the selected data instance and the nearest cluster is less than or equal to a predetermined cluster width, associating the selected data instance with the selected cluster.

50. The method of claim 48, further comprising, if the distance between the selected data instance and the selected cluster is greater than the cluster width, creating a new cluster and associating the selected data instance with the new cluster.

51. The method of claim 47, further comprising, determining a percentage of clusters having the greatest number of data instances respectively associated therewith.

52. The method of claim 51, wherein the percentage of clusters having the greatest number of data instances are labeled as dense regions in the feature space and wherein the remaining clusters are labeled as sparse regions in the feature space.

53. The method of claim 52, wherein designating one or more data instances as an anomaly comprises associating each data instance in the set of unlabeled data instances with a respective cluster.

54. The method of claim 43, further comprising, determining a sum of distances between a selected data instance and k nearest data instances to the selected data instance, wherein k is a predetermined value.

55. The method of claim 54, wherein determining the sum of the distances comprises determining a nearest cluster as a cluster corresponding to a shortest distance between the respective center of the cluster and the selected data instance.

56. The method of claim 55, further comprising, if a distance between the selected data instance and each data instance in the nearest cluster is less than a predetermined minimum distance, designating the point the cluster as one of the k nearest neighbors.

57. The method of claim 56, wherein designating one or more data instances as an anomaly comprises determining whether sum of the distances to the k nearest neighbors exceeds a predetermined threshold.

58. The method of claim 43, wherein designating one or more data instances as an anomaly comprises determining a decision function to separate the set of data instances from an origin, and computing the decision function.