Security alerting using n-gram analysis of program execution data

Patent metadata

Field	Value
Publication number	US-9329980-B2
Application number	US-201414198254-A
Country	US
Kind code	B2
Filing date	Mar 5, 2014
Priority date	Mar 5, 2014
Publication date	May 3, 2016
Grant date	May 3, 2016

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.

First claim

What is claimed is:

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 occurrenc

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Baril Bryce B
• Gounares Alexander G
• Krajec Russell S

Classifications

• G06F11/3616 Primary

  using software metrics · CPC title

• G06F11/3636

  by tracing the execution of the program · CPC title

• G06F11/3688 Primary

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

• G06F11/3466

  Performance evaluation by tracing or monitoring · CPC title