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

• US 10,423,788 B2
• Filed: 08/25/2016
• Issued: 09/24/2019
• 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
• Application Number:
  US15/247,154
• Publication Number:
  US 20160364568A1
• Time in Patent Office: 1,125 Days
• 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 of computing a model of program execution behavior, 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 running a program that executes the first sequence of function calls and the second sequence of function calls, wherein the first computing device of the application community monitors a first portion of the program and the second computing device of the application community monitors a second portion of the program, and wherein the first portion of the program and the second portion of the program are the same portion of the program;

receiving, using the hardware processor, a first model of the first sequence of function calls from the first computing device and a second model of the second sequence of function calls from the second computing device;

generating, using the hardware processor, a combined model that combines at least a portion of the first model and at least a portion of the second model; and

notifying, using the hardware processor, at least one of the plurality of computing devices in the application community of an anomalous function call that was detected using the combined model.

2. The method of claim 1, wherein at least one of the first model and the second model is generated using probabilistic modeling that generates a density estimation of sequences of function calls.

3. The method of claim 2, further comprising:

applying first and second order consistency checks, wherein the first order consistency check comprises computing a first probability of an observation of a first given feature value and the second order consistency check comprises computing a second probability of the first given feature value given another feature value; and

identifying the first given feature value as anomalous if at least one of the first probability and the second probability are less than a predetermined threshold probability.

4. The method of claim 1, wherein at least one of the first model and the second model is generated using a one-class support vector machine.

5. The method of claim 1, further comprising:

determining whether a function call from at least one of the first sequence of function calls and the second sequence of function calls has been executed less than a threshold number of times; and

in response to the determination, identifying the function call as having a greater likelihood of including an anomaly.

6. The method of claim 1, further comprising transmitting the second model from the second computing device to the first computing device.

7. The method of claim 1, further comprising transmitting the first model from the first computing device to the second computing device.

8. The method of claim 1, further comprising:

modifying a first portion of the combined model with newly obtained data; and

removing a second portion of the combined model, wherein the second part of the combined model was generated with older data.

9. The method of claim 1, further comprising assigning a third sequence of function calls to a third computing device of the application community, wherein the application community includes the plurality of computing devices running the program that executes the third sequence of function calls in addition to the first sequence of function calls and the second sequence of function calls, wherein the third computing device of the application community monitors a third portion of the program, wherein the first portion of the program and the third portion of the program are different portions of the program.

10. The method of claim 1, wherein the plurality of computing devices in the application community run the program or a portion thereof, or run an application that allows the plurality of computing devices to share information that is used to build the combined model for the program.

11. The method of claim 1, wherein the combined model is generated in whole or in part from executing the first sequence of function calls and the second sequence of function calls, wherein the detection of the anomalous function call using the combined model indicates behavior that deviates from normal and may correspond to an attack, wherein the detection is based on a statistical analysis, and wherein the combined model incorporates information about known or suspected attacks against at least a part of the program.

12. A system for computing a model of program execution behavior, comprising:

a hardware processor that is programmed to;

assign 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 running a program that executes the first sequence of function calls and the second sequence of function calls, wherein the first computing device of the application community monitors a first portion of the program and the second computing device of the application community monitors a second portion of the program, and wherein the first portion of the program and the second portion of the program are the same portion of the program;

receive a first model of the first sequence of function calls from the first computing device and a second model of the second sequence of function calls from the second computing device;

generate a combined model that combines at least a portion of the first model and at least a portion of the second model; and

notify at least one of the plurality of computing devices in the application community of an anomalous function call that was detected using the combined model.

13. The system of claim 12, wherein at least one of the first model and the second model is generated using probabilistic modeling that generates a density estimation of sequences of function calls.

14. The system of claim 13, wherein the hardware processor is further programmed to:

apply first and second order consistency checks, wherein the first order consistency check comprises computing a first probability of an observation of a first given feature value and the second order consistency check comprises computing a second probability of the first given feature value given another feature value; and

identify the first given feature value as anomalous if at least one of the first probability and the second probability are less than a predetermined threshold probability.

15. The system of claim 12, wherein at least one of the first model and the second model is generated using a one-class support vector machine.

16. The system of claim 12, wherein the hardware processor is further programmed to:

determine whether a function call from at least one of the first sequence of function calls and the second sequence of function calls has been executed less than a threshold number of times; and

in response to the determination, identify the function call as having a greater likelihood of including an anomaly.

17. The system of claim 12, wherein the hardware processor is further programmed to transmit the second model from the second computing device to the first computing device.

18. The system of claim 12, wherein the hardware processor is further programmed to transmit the first model from the first computing device to the second computing device.

19. The system of claim 12, wherein the hardware processor is further programmed to:

modify a first portion of the combined model with newly obtained data; and

remove a second portion of the combined model, wherein the second part of the combined model was generated with older data.

20. The system of claim 12, wherein the hardware processor is further programmed to assign a third sequence of function calls to a third computing device of the application community, wherein the application community includes the plurality of computing devices running the program that executes the third sequence of function calls in addition to the first sequence of function calls and the second sequence of function calls, wherein the third computing device of the application community monitors a third portion of the program, wherein the first portion of the program and the third portion of the program are different portions of the program.

21. The system of claim 12, wherein the plurality of computing devices in the application community run the program or a portion thereof, or run an application that allows the plurality of computing devices to share information that is used to build the combined model for the program.

22. The system of claim 12, wherein the combined model is generated in whole or in part from executing the first sequence of function calls and the second sequence of function calls, wherein the detection of the anomalous function call using the combined model indicates behavior that deviates from normal and may correspond to an attack, wherein the detection is based on a statistical analysis, and wherein the combined model incorporates information about known or suspected attacks against at least a part of the program.

23. A non-transitory computer-readable medium containing computer executable instructions that, when executed by a processor, cause the processor to perform a method of computing a model of program execution behavior, 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 running a program that executes the first sequence of function calls and the second sequence of function calls, wherein the first computing device of the application community monitors a first portion of the program and the second computing device of the application community monitors a second portion of the program, and wherein the first portion of the program and the second portion of the program are the same portion of the program;

receiving a first model of the first sequence of function calls from the first computing device and a second model of the second sequence of function calls from the second computing device;

generating a combined model that combines at least a portion of the first model and at least a portion of the second model; and

notifying at least one of the plurality of computing devices in the application community of an anomalous function call that was detected using the combined model.

24. The non-transitory computer-readable medium of claim 23, wherein at least one of the first model and the second model is generated using probabilistic modeling that generates a density estimation of sequences of function calls.

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

applying first and second order consistency checks, wherein the first order consistency check comprises computing a first probability of an observation of a first given feature value and the second order consistency check comprises computing a second probability of the first given feature value given another feature value; and

identifying the first given feature value as anomalous if at least one of the first probability and the second probability are less than a predetermined threshold probability.

26. The non-transitory computer-readable medium of claim 23, wherein at least one of the first model and the second model is generated using a one-class support vector machine.

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

determining whether a function call from at least one of the first sequence of function calls and the second sequence of function calls has been executed less than a threshold number of times; and

in response to the determination, identifying the function call as having a greater likelihood of including an anomaly.

28. The non-transitory computer-readable medium of claim 23, wherein the method further comprises transmitting the second model from the second computing device to the first computing device.

29. The non-transitory computer-readable medium of claim 23, wherein the method further comprises transmitting the first model from the first computing device to the second computing device.

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

modifying a first portion of the combined model with newly obtained data; and

removing a second portion of the combined model, wherein the second part of the combined model was generated with older data.

31. The non-transitory computer-readable medium of claim 23, wherein the method further comprises assigning a third sequence of function calls to a third computing device of the application community, wherein the application community includes the plurality of computing devices running the program that executes the third sequence of function calls in addition to the first sequence of function calls and the second sequence of function calls, wherein the third computing device of the application community monitors a third portion of the program, wherein the first portion of the program and the third portion of the program are different portions of the program.

32. The non-transitory computer-readable medium of claim 23, wherein the plurality of computing devices in the application community run the program or a portion thereof, or run an application that allows the plurality of computing devices to share information that is used to build the combined model for the program.

33. The non-transitory computer-readable medium of claim 23, wherein the combined model is generated in whole or in part from executing the first sequence of function calls and the second sequence of function calls, wherein the detection of the anomalous function call using the combined model indicates behavior that deviates from normal and may correspond to an attack, wherein the detection is based on a statistical analysis, and wherein the combined model incorporates information about known or suspected attacks against at least a part of the program.