Systems, Methods, and Media for Outputting Data Based Upon Anomaly Detection

• US 20090193293A1
• Filed: 02/28/2007
• Published: 07/30/2009
• Est. Priority Date: 02/28/2006
• 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, Parekh, Janak
• Granted Patent: US 8,448,242 B2
• Time in Patent Office: Days
• US Class Current: 714/26
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

Systems, methods, and media for outputting data based on anomaly detection are provided. In some embodiments, methods for outputting data based on anomaly detection include: receiving a known-good dataset; storing distinct n-grams from the known-good dataset to form a binary anomaly detection model; receiving known-good new n-grams; computing a rate of receipt of distinct n-grams in the new n-grams; determining whether further training of the anomaly detection model is necessary based on the rate of receipt on distinct n-grams; using the binary anomaly detection model to determine whether an input dataset contains an anomaly; and outputting the input dataset based on whether the input dataset contains an anomaly.

Claims

1. A method for outputting data based on anomaly detection, comprising:

receiving a known-good dataset;

storing distinct n-grams from the known-good dataset to form a binary anomaly detection model;

receiving known-good new n-grams;

computing a rate of receipt of distinct n-grams in the new n-grams;

determining whether further training of the anomaly detection model is necessary based on the rate of receipt on distinct n-grams;

using the binary anomaly detection model to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

2. The method of claim 1, wherein the binary detection model is represented using a Bloom filter.

3. The method of claim 1, wherein the rate of receipt of distinct n-grams is based on how many distinct n-grams are received in a given time period.

4. The method of claim 1, wherein the rate of receipt of distinct n-grams is based on how many distinct n-grams are received in a given volume of data.

5. The method of claim 1, wherein the binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

6. A method for outputting data based on anomaly detection, comprising:

receiving known anomaly signatures;

generating n-grams of different sizes using the known anomaly signatures;

storing abnormal n-grams in the n-grams of different sizes in a binary anomaly detection model;

using the binary anomaly detection model to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

7. The method of claim 6, wherein the anomaly signatures include Snort rules.

8. The method of claim 6, wherein the binary anomaly detection model is represented using a Bloom filter.

9. The method of claim 6, wherein the binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

10. A method for outputting data based on anomaly detection, comprising:

receiving a shared binary anomaly detection model;

comparing the shared binary anomaly detection model with a local anomaly detection model;

combining the shared binary anomaly detection model with the local anomaly detection model to form a new binary anomaly detection model;

using the model to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

11. The method of claim 10, wherein the shared binary anomaly detection model is represented using a Bloom filter.

12. The method of claim 10, wherein the local binary anomaly detection model is represented using a Bloom filter.

13. The method of claim 10, wherein the comparing is performed using a bitwise AND operation.

14. The method of claim 10, wherein the combining is performed using a bitwise OR operation.

15. The method of claim 10, wherein the new binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the new binary anomaly detection model for an n-gram in the input dataset.

16. A method for outputting data based on anomaly detection, comprising:

receiving an input dataset;

generating n-grams of different sizes from the input dataset;

counting the number of distinct n-grams in the n-grams of different sizes that are not present in a binary anomaly detection model;

computing an anomaly score based upon the number of distinct n-grams and a total count of the n-grams in the input dataset;

using the anomaly score to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

17. The method of claim 16, wherein the binary anomaly detection model is represented using a Bloom filter.

18. The method of claim 16, wherein the n-grams of different sizes are generated using a window applied to the input dataset.

19. The method of claim 16, wherein the anomaly score is compared to a threshold level to determine whether the input dataset contains an anomaly.

20. A method for outputting data based on anomaly detection, comprising:

receive an input dataset;

using a binary anomaly detection model to determine whether an input dataset is likely to contain an anomaly;

if the input dataset is determined to be likely to contain an anomaly, dropping the input dataset; and

if the input dataset is determined to be unlikely to contain an anomaly, outputting the input dataset based on whether the input dataset contains an anomaly.

21. The method of claim 20, wherein the binary anomaly detection model is represented using a Bloom filter.

22. The method of claim 20, wherein the binary anomaly detection model is used to determine if the input dataset is likely to contain an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

23. The method of claim 20, further comprising:

determining whether the input dataset contains malicious n-grams; and

if the input dataset is determined to not contain malicious n-grams, using the input dataset to perform a function related to the input dataset.

24. The method of claim 23, further comprising updating the binary anomaly detection model using the input dataset.

25. The method of claim 20, further comprising generating a content anomaly signature using the input dataset.

26. A computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for outputting data based on anomaly detection, the method comprising:

receiving a known-good dataset;

storing distinct n-grams from the known-good dataset to form a binary anomaly detection model;

receiving known-good new n-grams;

computing a rate of receipt of distinct n-grams in the new n-grams;

determining whether further training of the anomaly detection model is necessary based on the rate of receipt on distinct n-grams;

using the binary anomaly detection model to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

27. The medium of claim 26, wherein the binary detection model is represented using a Bloom filter.

28. The medium of claim 26, wherein the rate of receipt of distinct n-grams is based on how many distinct n-grams are received in a given time period.

29. The medium of claim 26, wherein the rate of receipt of distinct n-grams is based on how many distinct n-grams are received in a given volume of data.

30. The medium of claim 26, wherein the binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

31. A computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for outputting data based on anomaly detection, the method comprising:

receiving known anomaly signatures;

generating n-grams of different sizes using the known anomaly signatures;

storing abnormal n-grams in the n-grams of different sizes in a binary anomaly detection model;

using the binary anomaly detection model to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

32. The medium of claim 31, wherein the anomaly signatures include Snort rules.

33. The medium of claim 31, wherein the binary anomaly detection model is represented using a Bloom filter.

34. The medium of claim 31, wherein the binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

35. A computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for outputting data based on anomaly detection, the method comprising:

receiving a shared binary anomaly detection model;

comparing the shared binary anomaly detection model with a local anomaly detection model;

combining the shared binary anomaly detection model with the local anomaly detection model to form a new binary anomaly detection model;

using the model to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

36. The medium of claim 35, wherein the shared binary anomaly detection model is represented using a Bloom filter.

37. The medium of claim 35, wherein the local binary anomaly detection model is represented using a Bloom filter.

38. The medium of claim 35, wherein the comparing is performed using a bitwise AND operation.

39. The medium of claim 35, wherein the combining is performed using a bitwise OR operation.

40. The medium of claim 35, wherein the new binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the new binary anomaly detection model for an n-gram in the input dataset.

41. A computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for outputting data based on anomaly detection, the method comprising:

receiving an input dataset;

generating n-grams of different sizes from the input dataset;

counting the number of distinct n-grams in the n-grams of different sizes that are not present in a binary anomaly detection model;

computing an anomaly score based upon the number of distinct n-grams and a total count of the n-grams in the input dataset;

using the anomaly score to determine whether an input dataset contains an anomaly; and

outputting the input dataset based on whether the input dataset contains an anomaly.

42. The medium of claim 41, wherein the binary anomaly detection model is represented using a Bloom filter.

43. The medium of claim 41, wherein the n-grams of different sizes are generated using a window applied to the input dataset.

44. The medium of claim 41, wherein the anomaly score is compared to a threshold level to determine whether the input dataset contains an anomaly.

45. A computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for outputting data based on anomaly detection, the method comprising:

receiving an input dataset;

using a binary anomaly detection model to determine whether an input dataset is likely to contain an anomaly;

if the input dataset is determined to be likely to contain an anomaly, dropping the input dataset; and

if the input dataset is determined to be unlikely to contain an anomaly, outputting the input dataset based on whether the input dataset contains an anomaly.

46. The medium of claim 45, wherein the binary anomaly detection model is represented using a Bloom filter.

47. The medium of claim 45, wherein the binary anomaly detection model is used to determine if the input dataset is likely to contain an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

48. The medium of claim 45, the method further comprising:

determining whether the input dataset contains malicious n-grams; and

if the input dataset is determined to not contain malicious n-grams, using the input dataset to perform a function related to the input dataset.

49. The medium of claim 48, the method further comprising updating the binary anomaly detection model using the input dataset.

50. The medium of claim 45, the method further comprising generating a content anomaly signature using the input dataset.

51. A system for outputting data based on anomaly detection, comprising:

a digital processing device that;

receives a known-good dataset;

stores distinct n-grams from the known-good dataset to form a binary anomaly detection model;

receives known-good new n-grams;

computes a rate of receipt of distinct n-grams in the new n-grams;

determines whether further training of the anomaly detection model is necessary based on the rate of receipt on distinct n-grams;

uses the binary anomaly detection model to determine whether an input dataset contains an anomaly; and

outputs the input dataset based on whether the input dataset contains an anomaly.

52. The system of claim 51, wherein the binary detection model is represented using a Bloom filter.

53. The system of claim 51, wherein the rate of receipt of distinct n-grams is based on how many distinct n-grams are received in a given time period.

54. The system of claim 51, wherein the rate of receipt of distinct n-grams is based on how many distinct n-grams are received in a given volume of data.

55. The system of claim 51, wherein the binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

56. A system for outputting data based on anomaly detection, comprising:

a digital processing device that;

receives known anomaly signatures;

generates n-grams of different sizes using the known anomaly signatures;

stores abnormal n-grams in the n-grams of different sizes in a binary anomaly detection model;

uses the binary anomaly detection model to determine whether an input dataset contains an anomaly; and

outputs the input dataset based on whether the input dataset contains an anomaly.

57. The system of claim 56, wherein the anomaly signatures include Snort rules.

58. The system of claim 56, wherein the binary anomaly detection model is represented using a Bloom filter.

59. The system of claim 56, wherein the binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

60. A system for outputting data based on anomaly detection, comprising:

a digital processing device that;

receives a shared binary anomaly detection model;

compares the shared binary anomaly detection model with a local anomaly detection model;

combines the shared binary anomaly detection model with the local anomaly detection model to form a new binary anomaly detection model;

uses the model to determine whether an input dataset contains an anomaly; and

outputs the input dataset based on whether the input dataset contains an anomaly.

61. The system of claim 60, wherein the shared binary anomaly detection model is represented using a Bloom filter.

62. The system of claim 60, wherein the local binary anomaly detection model is represented using a Bloom filter.

63. The system of claim 60, wherein the comparing is performed using a bitwise AND operation.

64. The system of claim 60, wherein the combining is performed using a bitwise OR operation.

65. The system of claim 60, wherein the new binary anomaly detection model is used to determine if the input dataset contains an anomaly by checking the new binary anomaly detection model for an n-gram in the input dataset.

66. A system for outputting data based on anomaly detection, comprising:

a digital processing device that;

receives an input dataset;

generates n-grams of different sizes from the input dataset;

counts the number of distinct n-grams in the n-grams of different sizes that are not present in a binary anomaly detection model;

computes an anomaly score based upon the number of distinct n-grams and a total count of the n-grams in the input dataset;

uses the anomaly score to determine whether an input dataset contains an anomaly; and

outputs the input dataset based on whether the input dataset contains an anomaly.

67. The system of claim 66, wherein the binary anomaly detection model is represented using a Bloom filter.

68. The system of claim 66, wherein the n-grams of different sizes are generated using a window applied to the input dataset.

69. The system of claim 66, wherein the anomaly score is compared to a threshold level to determine whether the input dataset contains an anomaly.

70. A system for outputting data based on anomaly detection, comprising:

a digital processing device that;

receives an input dataset;

uses a binary anomaly detection model to determine whether an input dataset is likely to contain an anomaly;

if the input dataset is determined to be likely to contain an anomaly, drops the input dataset; and

if the input dataset is determined to be unlikely to contain an anomaly, outputs the input dataset based on whether the input dataset contains an anomaly.

71. The system of claim 70, wherein the binary anomaly detection model is represented using a Bloom filter.

72. The system of claim 70, wherein the binary anomaly detection model is used to determine if the input dataset is likely to contain an anomaly by checking the binary anomaly detection model for an n-gram in the input dataset.

73. The system of claim 70, wherein the digital processing device also:

determines whether the input dataset contains malicious n-grams; and

if the input dataset is determined to not contain malicious n-grams, uses the input dataset to perform a function related to the input dataset.

74. The system of claim 73, wherein the digital processing device also updates the binary anomaly detection model using the input dataset.

75. The system of claim 70, wherein the digital processing device also generates a content anomaly signature using the input dataset.