Log message anomaly detection

• US 8,495,429 B2
• Filed: 05/25/2010
• Issued: 07/23/2013
• Est. Priority Date: 05/25/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Fu, Qiang, Lou, Jian-Guang, Li, Jiang
• Primary Examiner(s): Manoskey, Joseph D
• Application Number:
  US12/786,837
• Publication Number:
  US 20110296244A1
• Time in Patent Office: 1,155 Days
• Field of Search: 714/20, 714/25, 714/37, 714/38.1, 714/39, 714/45, 714/47.1, 714/47.3, 714/49
• US Class Current: 714/38.1
• 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 one or more anomalies in a message log, comprising:

grouping one or more structured log messages comprising a same value of a same program variable into a group, the grouping comprising;

determining whether a first log parameter of a first structured log message and a second log parameter of a second structured log message are cogenetic, comprising determining at least one of;

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

or

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

identifying one or more invariants for the group; and

applying at least some of the one or more invariants to one or more log sequences to detect one or more anomalies, at least some of at least one of the grouping, the identifying, or the applying implemented at least in part using a computer-based processor.

2. The method of claim 1, comprising parsing a log message from an unstructured text string to a structured form, 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, comprising parsing a log message from an unstructured text string to a structured form, parsing the log message comprising:

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

applying a clustering algorithm to at least some of the one or more raw message signatures to obtain a set of one or more clusters; and

extracting a common string from a cluster to obtain a signature.

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

5. The method of claim 1, comprising parsing a log message from an unstructured text string to a structured form.

6. The method of claim 1, comprising defining a log parameter by a corresponding message signature.

7. The method of claim 1, comprising deriving a value range.

8. The method of claim 1, grouping one or more structured log messages comprising grouping one or more cogenetic log parameters.

9. The method of claim 1, identifying one or more invariants comprising determining one or more 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 one or more message count vectors for one or more log message groups related to a same target program variable and forming a count matrix;

identifying an invariant space of the count matrix;

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

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

11. The method of claim 10, extracting a set of one or more message count vectors comprising counting a number for one or more 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 one or more combinations of one or more non-zero coefficients in one or more different dimensions to construct an invariant candidate.

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

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

a grouping component configured to group one or more structured log messages comprising a same value of a same program variable into a group, the grouping component comprising;

a parameter comparison component configured to compare one or more log value ranges of a plurality of log parameters of at least some of the one or more structured log messages to determine if at least some of the plurality of log parameters can be grouped;

an invariant identification component configured to identify one or more invariants for the group; and

an anomaly detection component configured to apply at least some of the one or more invariants to one or more log sequences to detect one or more anomalies, at least some of at least one of the grouping component, the invariant identification component, or the anomaly detection component implemented at least in part via a processor.

16. The system of claim 15, comprising a log message parsing component configured to parse a log message from an unstructured text string to a structured form, the log message parsing component comprising:

a parameter value extraction component configured to extract one or more parameter values from the log message using one or more 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, comprising a log message parsing component configured to parse a log message from an unstructured text string to a structured form.

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

a vector extraction component configured to extract a set of one or more message count vectors for one or more log message groups related to a same target program variable, the one or more count vectors configured to 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 one or more different dimensions to construct an invariant candidate; and

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

20. A tangible computer-readable storage device comprising instructions that when executed by a processor perform a method for detecting one or more anomalies in a message log, comprising:

grouping one or more structured log messages comprising a same value of a same program variable into one or more groups;

identifying one or more invariants for at least some of the one or more groups, the identifying comprising;

extracting a set of one or more message count vectors for at least some of the one or more groups related to a same target program variable;

forming a count matrix based at least in part on at least some of the set of one or more message count vectors; and

identifying an invariant space of the count matrix; and

applying at least some of the one or more invariants to one or more log sequences to detect one or more anomalies.