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

Patent metadata

Field	Value
Publication number	US-10423788-B2
Application number	US-201615247154-A
Country	US
Kind code	B2
Filing date	Aug 25, 2016
Priority date	Oct 30, 2006
Publication date	Sep 24, 2019
Grant date	Sep 24, 2019

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.

First claim

What is claimed is:

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 t

Assignees

• Keromytis Angelos D
• Stolfo Salvatore J
• Univ Columbia

Inventors

• Keromytis Angelos D
• Stolfo Salvatore J

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F11/08

  Error detection or correction by redundancy in data representation, e.g. by using checking codes · CPC title

• G06F21/566 Primary

  Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities · CPC title

• G06F2221/033

  Test or assess software · CPC title

• G06F11/3688

  for test execution, e.g. scheduling of test suites · CPC title