Security alerting using n-gram analysis of program execution data

• US 9,329,980 B2
• Filed: 03/05/2014
• Issued: 05/03/2016
• Est. Priority Date: 03/05/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gounares, Alexander G., Krajec, Russell S., Baril, Bryce B.
• Primary Examiner(s): Vo, Ted T
• Application Number:
  US14/198,254
• Publication Number:
  US 20150254172A1
• Time in Patent Office: 790 Days
• Field of Search: 717124-133
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 11/3616 using software metrics
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites

Abstract

N-grams of input streams or functions executed by an application may be analyzed to identify security breaches or other anomalous behavior. A histogram of n-grams representing sequences of executed functions or input streams may be generated through baseline testing or production use. An alerting system may compare real time n-gram observations to the histogram of n-grams to identify security breaches or other changes in application behavior that may be anomalous. An alert may be generated that identifies the anomalous behavior. The alerting system may be trained using known good datasets and may identify deviations as bad behavior. The alerting system may be trained using known bad datasets and may identify matching behavior as bad behavior.

Claims

1. A method performed on at least one computer processor, said method comprising:

receiving first tracer data observed from a first execution of an application, said first tracer data comprising first production input data representing inputs that were provided to said application during said first execution of said application;

identifying a plurality of n-grams representing unique input data sequences within said first tracer data;

generating a set of usage statistics comprising one usage statistic for each of said plurality of n-grams;

storing said set of usage statistics and said n-grams in a database;

receiving second tracer data observed from a second execution of said application, said second tracer data comprising second production input data representing inputs that were provided to said application during said second execution of said application;

identifying a first n-gram within said second tracer data, said first n-gram representing a first unique input data sequence within said second tracer data;

comparing said first n-gram to said database to determine a first usage statistic for said first n-gram from the set of usage statistics; and

determining said first usage statistic for said first n-gram is below a predefined threshold and determining that said first n-gram represents behavior anomalous to said first tracer data.

2. The method of claim 1 further comprising:

identifying a second n-gram within said second tracer data, said second n-gram representing a second unique input data sequence within said second tracer data;

comparing said second n-gram to said database to determine a second usage statistic for said second n-gram from the set of usage statistics; and

determining that said second usage statistic for said second n-gram is above a predefined threshold and determining that said second n-gram represents behavior consistent with said first tracer data.

3. The method of claim 2, said first tracer data being gathered from known bad behavior of said application.

4. The method of claim 3, said first tracer data being gathered from monitoring said application while executing a first test suite.

5. The method of claim 3 further comprising generating an alert based on said second usage statistic for said first n-gram.

6. The method of claim 1, said first tracer data being gathered from known good behavior of said application.

7. The method of claim 6, said first tracer data being gathered from monitoring said application while executing a first test suite.

8. The method of claim 6 further comprising generating an alert based on said first usage statistic for said first n-gram.

9. The method of claim 1, said first tracer data also comprising sequences of functions executed during said first execution of said application.

10. The method of claim 9, said functions being executed in a single thread and wherein generating a set of usage statistics further comprises grouping the functions by thread and generating the set of usage statistics with respect to each thread group.

11. The method of claim 1, said first tracer data also comprising sequences of outputs generated during said first execution of said application.

12. The method of claim 1, said first usage statistic being a frequency of occurrence for said first n-gram.

13. The method of claim 12, said first usage statistic being multiplied by an amount of a resource consumed during execution of said first n-gram.

14. The method of claim 13, said resource comprising at least one of a group composed of:

processor resources;

memory resources;

storage resources;

network resources;

peripheral resources;

input/output resources;

database resources;

local service resources; and

remote service resources.

15. The method of claim 1, said n-grams comprising at least one of a group composed of:

bi-grams, tri-grams, 4-grams, 5-grams, 6-grams, and 7-grams.

16. A system comprising:

one or more hardware processors;

a database comprising a plurality of n-grams representing unique input data sequences observed in a first tracer data from a first execution of an application, said first tracer data comprising first production input data representing inputs that were provided to said application during said first execution of said application, and a set of usage statistics comprising one usage statistic for each of said plurality of n-grams; and

one or more computer-readable media having stored thereon computer-executable instructions that are executable by the one or more hardware processors to implement an analysis engine that is configured to perform at least the following;

receive second tracer data observed from a second execution of said application, said second tracer data comprising second production input data representing inputs that were provided to said application during said second execution of said application;

identify a first n-gram within said second tracer data, said first n-gram representing a first unique input data sequence within said second tracer data;

compare said first n-gram to said database to determine a first usage statistic for said first n-gram from the set of usage statistics; and

determine said first usage statistic for said first n-gram is below a predefined threshold and determines that said first n-gram represents behavior anomalous to said first tracer data.

17. The system of claim 16, said analysis engine further being configured to perform at least the following:

identify a second n-gram within said second tracer data, said second n-gram representing a second unique input data sequence within said second tracer data;

compare said second n-gram to said database to determine a second usage statistic for said second n-gram; and

determine that said second usage statistic for said second n-gram is above a predefined threshold and determines that said second n-gram represents behavior consistent with said first tracer data.

18. The system of claim 17, said first tracer data being gathered from known bad behavior of said application.

19. The system of claim 18, said first tracer data being gathered from monitoring said application while executing a first test suite.

20. The system of claim 18, said analysis engine further being configured to generate an alert based on said second usage statistic for said first n-gram.

21. The system of claim 20, said first tracer data being gathered from known good behavior of said application.

22. The system of claim 21, said first tracer data being gathered from monitoring said application while executing a first test suite.

23. The system of claim 21, said analysis engine further being configured to generate an alert based on said first usage statistic for said first n-gram.

24. The system of claim 16, said first tracer data also comprising sequences of functions executed during said first execution of said application.

25. The system of claim 24, said functions being executed in a single thread and further comprising generating the set of usage statistics by grouping the functions by thread and generating the set of usage statistics with respect to each thread group.

26. The system of claim 16, said first tracer data also comprising sequences of outputs generated during said first execution of said application.

27. The system of claim 16, said first usage statistic being a frequency of occurrence for said first n-gram.

28. The system of claim 27, said first usage statistic being multiplied by an amount of a resource consumed during execution of said first n-gram.

29. The system of claim 28, said resource comprising at least one of a group composed of:

processor resources;

memory resources;

storage resources;

network resources;

peripheral resources;

input/output resources;

database resources;

local service resources; and

remote service resources.

30. The system of claim 16, said n-grams comprising at least one of a group composed of:

bi-grams, tri-grams, 4-grams, 5-grams, 6-grams, and 7-grams.

31. A computer program product comprising one or more hardware storage devices having stored thereon computer-executable instructions that are executable by one or more processors of a computer system to configure the computer system to perform at least the following:

receive first tracer data observed from a first execution of an application, said first tracer data comprising first production input data representing inputs that were provided to said application during said first execution of said application;

identify a plurality of n-grams representing unique input data sequences within said first tracer data;

generate a set of usage statistics comprising one usage statistic for each of said plurality of n-grams;

store said set of usage statistics and said n-grams in a database;

receive second tracer data observed from a second execution of said application, said second tracer data comprising second production input data representing inputs that were provided to said application during said second execution of said application;

identify a first n-gram within said second tracer data, said first n-gram representing a first unique input data sequence within said second tracer data;

compare said first n-gram to said database to determine a first usage statistic for said first n-gram from the set of usage statistics; and

determine said first usage statistic for said first n-gram is below a predefined threshold and determining that said first n-gram represents behavior anomalous to said first tracer data.

32. The computer program product of claim 31, the computer-executable instructions executable to configure the computer system to also perform at least the following:

identify a second n-gram within said second tracer data, said second n-gram representing a second unique input data sequence within said second tracer data;

compare said second n-gram to said database to determine a second usage statistic for said second n-gram from the set of usage statistics; and

determine that said second usage statistic for said second n-gram is above a predefined threshold and determining that said second n-gram represents behavior consistent with said first tracer data.