Methods, media, and systems for detecting an anomalous sequence of function calls

• US 8,694,833 B2
• Filed: 07/15/2013
• Issued: 04/08/2014
• Est. Priority Date: 10/30/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: Keromytis, Angelos D., Stolfo, Salvatore J.
• Primary Examiner(s): Maskulinski, Michael
• Assistant Examiner(s): MILES, NEIL D
• Application Number:
  US13/942,632
• Publication Number:
  US 20130305098A1
• Time in Patent Office: 267 Days
• Field of Search: 714/38.1
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/566 Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 2221/033 Test or assess software
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

Methods, media, and systems for detecting an anomalous sequence of function calls are provided. The methods can include compressing a sequence of function calls made by the execution of a program using a compression model; and determining the presence of an anomalous sequence of function calls in the sequence of function calls based on the extent to which the sequence of function calls is compressed. The methods can further include executing at least one known program; observing at least one sequence of function calls made by the execution of the at least one known program; assigning each type of function call in the at least one sequence of function calls made by the at least one known program a unique identifier; and creating at least part of the compression model by recording at least one sequence of unique identifiers.

Claims

1. A method for detecting an anomalous sequence of function calls, the method comprising:

assigning, using a hardware processor, a first sequence of function calls to a first computing device of an application community and a second sequence of function calls to a second computing device of the application community, wherein the application community includes a plurality of computing devices;

determining a presence of an anomalous sequence of function calls in at least one of the first and second sequences of function calls by compressing at least one of the first sequence of function calls and the second sequence of function calls; and

notifying the other computing devices of the application community of the anomalous sequence of function calls.

2. The method of claim 1, further comprising:

in response to determining the presence of the anomalous sequence of function calls, isolating a portion the anomalous sequence of function calls; and

constructing a vaccine that makes the anomalous sequence of function calls non-anomalous.

3. The method of claim 2, wherein the vaccine includes at least one of an emulator-based vaccine, source-code changes, and binary rewriting.

4. The method of claim 1, wherein the assigning is based on a length of the first sequence or the second sequence of function calls and a number of the plurality of computing devices in the application community.

5. The method of claim 1, wherein the assigning is based on an amount of available memory in each of the plurality of computing devices of the application community.

6. The method of claim 1, wherein the assigning is based on a workload and a number of the plurality of computing devices needed for monitoring.

7. The method of claim 1, wherein the assigning further comprises receiving a bid for the at least one of the first and second sequences of function calls from one of the plurality of computing devices in the application community.

8. A system for detecting an anomalous sequence of function calls, the system comprising:

a hardware processor that;

assigns a first sequence of function calls to a first computing device of an application community and a second sequence of function calls to a second computing device of the application community, wherein the application community includes a plurality of computing devices;

determines a presence of an anomalous sequence of function calls in at least one of the first and second sequences of function calls by compressing at least one of the first sequence of function calls and the second sequence of function calls; and

notifies the other computing devices of the application community of the anomalous sequence of function calls.

9. The system of claim 8, wherein the hardware processor is further configured to:

in response to determining the presence of the anomalous sequence of function calls, isolate a portion the anomalous sequence of function calls; and

construct a vaccine that makes the anomalous sequence of function calls non-anomalous.

10. The system of claim 9, wherein the vaccine includes at least one of an emulator-based vaccine, source-code changes, and binary rewriting.

11. The system of claim 8, wherein the hardware processor is further configured to assign the sequence of function calls based on a length of the first sequence or the second sequence of function calls and a number of the plurality of computing devices in the application community.

12. The system of claim 8, wherein the hardware processor is further configured to assign a sequence of function calls based on an amount of available memory in each of the plurality of computing devices of the application community.

13. The system of claim 8, wherein the hardware processor is further configured to assign a sequence of function calls based on a workload and a number of the plurality of computing devices needed for monitoring.

14. The system of claim 8, wherein the hardware processor is further configured to assign a sequence of function calls based on receiving a bid for the at least one of the first and second sequences of function calls from one of the plurality of computing devices in the application community.

15. A non-transitory computer-readable medium containing computer-executable instructions that, when executed by a processor, cause the processor to perform a method for detecting an anomalous sequence of function calls, the method comprising:

assigning a first sequence of function calls to a first computing device of an application community and a second sequence of function calls to a second computing device of the application community, wherein the application community includes a plurality of computing devices;

determining a presence of an anomalous sequence of function calls in at least one of the first and second sequences of function calls by compressing at least one of the first sequence of function calls and the second sequence of function calls; and

notifying the other computing devices of the application community of the anomalous sequence of function calls.

16. The non-transitory computer-readable medium of claim 15, wherein the method further comprises:

in response to determining the presence of the anomalous sequence of function calls, isolating a portion the anomalous sequence of function calls; and

constructing a vaccine that makes the anomalous sequence of function calls non-anomalous.

17. The non-transitory computer-readable medium of claim 16, wherein the vaccine includes at least one of an emulator-based vaccine, source-code changes, and binary rewriting.

18. The non-transitory computer-readable medium of claim 15, wherein the assigning is based on a length of the first sequence or the second sequence of function calls and a number of the plurality of computing devices in the application community.

19. The non-transitory computer-readable medium of claim 15, wherein the assigning is based on an amount of available memory in each of the plurality of computing devices of the application community.

20. The non-transitory computer-readable medium of claim 15, wherein the assigning is based on a workload and a number of the plurality of computing devices needed for monitoring.

21. The non-transitory computer-readable medium of claim 15, wherein the assigning further comprises receiving a bid for the at least one of the first and second sequences of function calls from one of the plurality of computing devices in the application community.