LOG MESSAGE ANOMALY DETECTION

• US 20110296244A1
• Filed: 05/25/2010
• Published: 12/01/2011
• Est. Priority Date: 05/25/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jiang, Fu, Qiang, Lou, Jian-Guang
• Granted Patent: US 8,495,429 B2
• Time in Patent Office: Days
• US Class Current: 714/37
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013

Abstract

One or more techniques and/or systems are disclosed for detecting anomalies in a message log. A log message is parsed from an unstructured text string to a structured form, comprising messages signature and parameter values. Structured log messages that contain a same parameter value of a same program variable are grouped together. One or more invariants for are identified from respective types of log message groups. Invariants are applied to log sequences of respective log types.

Claims

1. A computer-based method for detecting anomalies in a message log, comprising:

parsing a log message, which is stored in computer-based memory, from an unstructured text string to a structured form;

grouping structured log messages that contain a same value of a same program variable;

identifying one or more invariants for respective types of log message groups; and

applying invariants to log sequences of respective log types to detect anomalies using a computer-based processor.

2. The method of claim 1, parsing the log message comprising:

extracting a message signature from the log message; and

extracting one or more parameter values from the log message.

3. The method of claim 1, parsing the log message comprising:

using empirical rules to extract parameter values leaving raw message signatures;

applying a clustering algorithm to the raw message signatures to obtain a set of clusters; and

extracting a common string from a cluster to obtain a signature, leaving parameter values to be extracted.

4. The method of claim 1, grouping structured log messages comprising grouping log messages together that comprise log parameters with one or more same parameter values.

5. The method of claim 1, grouping structured log messages comprising:

enumerating a value range of a log parameter for a log message;

determining whether a first log parameter and a second log parameter are cogenetic, comprising determining one of;

whether the value range of the first log parameter and the value range of the second log parameter are equivalent; and

whether the value range of the first log parameter and the value range of the second log parameter are equivalent.

6. The method of claim 5, defining the log parameter by a corresponding message signature and a position index from the log message for the log parameter.

7. The method of claim 5, comprising deriving a value range by collecting a parameter value for a parameter from a plurality of log messages derived from running a target program under different conditions.

8. The method of claim 5, grouping log messages comprising:

grouping cogenetic log parameters; and

grouping the log messages that contain the log parameters belonging to a parameter group, where the log parameter'"'"'s values in the log messages are a same value.

9. The method of claim 1, identifying one or more invariants comprising determining invariants of one or more log message groups corresponding to a same target program variable.

10. The method of claim 1, identifying one or more invariants comprising:

extracting a set of message count vectors for respective log message groups that are related to a same target program variable to form a count matrix;

identifying an invariant space of the count matrix;

identifying one or more invariant candidates in the invariant space; and

validating invariants from the invariant candidates using collected historical log data.

11. The method of claim 10, extracting a set of message count vectors comprising counting a number for respective log message types in a log message group to obtain a message count vector.

12. The method of claim 10, identifying an invariant space comprising estimating the invariant space by singular value decomposition (SVD) operation.

13. The method of claim 10, identifying one or more invariant candidates in the invariant space comprising using combinations of non-zero coefficients in different dimensions to construct an invariant candidate.

14. The method of claim 10, validating invariants comprising determining that an invariant candidate fits with the collected historical log data if it is satisfied by a desired threshold of log message groups.

15. A system for detecting anomalies in a message log, comprising:

a memory component configured to store data;

a processor configured process data;

a log message parsing component operably coupled with the memory component and processor, and configured to parse a log message from an unstructured text string to a structured form;

a grouping component operably coupled with the memory component and processor, and configured to group structured log messages that contain a same value of a same program variable;

an invariant identification component operably coupled with the memory component and processor, and configured to identify one or more invariants for respective types of log message groups; and

an anomaly detection component operably coupled with the memory component and processor, and configured to apply invariants to respective log sequences to detect anomalies.

16. The system of claim 15, the log message parsing component comprising:

a parameter value extraction component configured to extract one or more parameter values from the log message using empirical rules; and

a signature extraction component configured to extract a message signature from the log message using a clustering algorithm.

17. The system of claim 15, the grouping component comprising:

a parameter value determination component configured to enumerate a value range of a log parameter for a log message; and

a parameter comparison component configured to compare log value ranges of parameters to determine if the parameters can be grouped based on value ranges.

18. The system of claim 15, the invariant identification component comprising:

a vector extraction component configured to extract a set of message count vectors for respective log message groups that are related to a same target program variable, where the count vectors form a count matrix; and

an invariant space determination component configured to identify an invariant space of the count matrix.

19. The system of claim 18, comprising:

an invariant candidate identification component configured to identify one or more invariant candidates in the invariant space using combinations of non-zero coefficients in different dimensions to construct the invariant candidate; and

an invariant validation component configured to validate invariants from the invariant candidates using collected historical log data.

20. A computer-based method for detecting anomalies in a message log, comprising:

parsing a log message, which is stored in computer-based memory, from an unstructured text string to a structured form, comprising;

extracting one or more parameter values from the log message using empirical rules to extract parameter values leaving raw message signatures; and

extracting a message signature from the log message using a clustering algorithm;

grouping structured log messages that contain a same value of a same program variable, comprising;

enumerating a value range of a log parameter for a log message;

determining whether a first log parameter and a second log parameter are cogenetic, comprising determining one of;

whether the value range of the first log parameter and the value range of the second log parameter are equivalent; and

whether the value range of the first log parameter is a subset of the value range of the second log parameter; and

grouping log messages that comprise cogenetic log parameters;

identifying one or more invariants for respective types of log message groups, comprising;

extracting a set of message count vectors for respective log message groups that are related to a same target program variable to form a count matrix;

identifying an invariant space of the count matrix;

identifying one or more invariant candidates in the invariant space using combinations of non-zero coefficients in different dimensions to construct an invariant candidate; and

validating invariants from the invariant candidates comprising determining that an invariant candidate fits with the collected historical log data if it is satisfied by a desired threshold of log message groups; and

applying invariants to respective log sequences to detect anomalies using a computer-based processor.