Fingerprinting event logs for system management troubleshooting

• US 8,069,374 B2
• Filed: 02/27/2009
• Issued: 11/29/2011
• Est. Priority Date: 02/27/2009
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Junfeng, Yuan, Ding, Verbowski, Chad, Panigrahy, Rina, Xie, Yinglian
• Primary Examiner(s): GUYTON, PHILIP A
• Application Number:
  US12/394,451
• Publication Number:
  US 20100223499A1
• Time in Patent Office: 1,005 Days
• Field of Search: 714/38, 714/38.1, 714/39, 714/45
• US Class Current: 714/38.1
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0715 in a system implementing multitasking multitasking per se G06F9/46
• CPC Class Codes: G06F 11/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence

Abstract

A technique for automatically detecting and correcting configuration errors in a computing system. In a learning process, recurring event sequences, including e.g., registry access events, are identified from event logs, and corresponding rules are developed. In a detecting phase, the rules are applied to detected event sequences to identify violations and to recover from failures. Event sequences across multiple hosts can be analyzed. The recurring event sequences are identified efficiently by flattening a hierarchical sequence of the events such as is obtained from the Sequitur algorithm. A trie is generated from the recurring event sequences and edges of nodes of the trie are marked as rule edges or non-rule edges. A rule is formed from a set of nodes connected by rule edges. The rules can be updated as additional event sequences are analyzed. False positive suppression policies include a violation-consistency policy and an expected event disappearance policy.

Claims

1. A computer-implemented method for troubleshooting configuration errors, comprising:

obtaining a log of events which are generated as a program executes in a learning process;

analyzing events of the learning process to identify recurring event sequences, each recurring event sequence includes a time sequence of multiple events and occurs a number of times above a predefined threshold;

generating rules based on the recurring event sequences;

obtaining a log of events which are generated as the program executes in a detection process;

applying the rules to events of the detection process to determine if a sequence of events of the detection process violates at least one of the rules; and

determining that an error has been detected in the program, and reporting an alarm, when the sequence of the events of the detection process violates at least one of the rules.

2. The computer-implemented method of claim 1, wherein:

the applying of the rules includes applying a violation-consistency policy which determines whether a violated rule is consistently violated within a specified amount of time, where if a violated rule has been both followed and violated in the specified amount of time, a violation is treated as a false positive.

3. The computer-implemented method of claim 1, wherein:

the sequence of events of the detection process violates at least one of the rules when a violating event appears in place of an expected event; and

the applying of the rules includes applying an expected event disappearance policy which determines whether the expected event appears after the violating event within a specified amount of time;

where if the expected event appears after the violating event within a specified amount of time, a violation is treated as a false positive.

4. The computer-implemented method of claim 1, wherein the generating rules comprises:

generating a trie based on at least a first of the recurring event sequences;

the trie comprises nodes arranged in a hierarchy according to the at least a first of the recurring event sequences, each node corresponding to an event in the at least a first of the recurring event sequences;

marking, as rule edges, edges of nodes which are determined to have, based on the at least a first of the recurring event sequences, only one outgoing transition to a lower node; and

updating the trie based on at least one additional recurring event sequence, the updating comprises unmarking a rule edge of one of the nodes which is determined to have, based further on the at least one additional recurring event sequence, more than one outgoing transition to a lower node.

5. The computer-implemented method of claim 1, wherein the generating rules comprises:

generating a trie based on the recurring event sequences;

the trie comprises nodes arranged in a hierarchy according to the recurring event sequences, each node corresponding to an event in at least one of the recurring event sequences; and

marking, as rule edges, edges of nodes which are determined to have only one outgoing transition to a lower node;

the rules are generated based on sets of nodes connected by rule edge transitions in the trie, the sets of nodes have a specified minimum number of nodes corresponding to a specified minimum number of events.

6. The computer-implemented method of claim 1, wherein:

the events which are generated as the program executes in the learning process and in the detection process are from at least one of;

(a) different threads of a process, and (b) different threads from different processes, as long as their corresponding processes are launched from a common executable.

7. The computer-implemented method of claim 1, wherein:

the events which are generated as the program executes in the learning and detection processes are from different hosts, and the rules are shared across the different hosts in the applying the rules to the events of the detection process.

8. The computer-implemented method of claim 1, wherein:

the reporting of an alarm includes providing an output which identifies at least one of;

(a) the sequence of the events of the detection process which violates at least one of the rules, (b) a violating event, and (c) an expected event.

9. The computer-implemented method of claim 1, further comprising:

obtaining hierarchical sequences which represent sequences of the events of the learning process by taking one or more input event sequences, and flattening the hierarchical sequences to obtain flattened hierarchical sequences, wherein the flattened hierarchical sequences includes symbols which represent single events but not multiple events, and the recurring event sequences are identified from the flattened hierarchical sequences.

10. The computer-implemented method of claim 1, wherein the log of events of the learning process and the log of events of the detection process comprise registry events regarding registry key accesses, the method further comprising;

when the sequence of the events of the detection process violates at least one of the rules, determining if the registry key involved in either a violating event or an expected event has been one of;

(a) deleted and (b) modified; and

restoring the registry key of either the violating event or expected event to an expected key if the registry key has been one of;

(a) deleted and (b) modified, the rules identify the expected key.

11. The computer-implemented method of claim 10, further comprising:

restoring a value associated with the registry key to an expected value if the registry key has been one of;

(a) deleted and (b) modified, the rules identify the expected value.

12. The computer-implemented method of claim 10, further comprising:

searching earlier registry events in the log of events of the detection process to identifying a process of the program which has one of;

(a) deleted and (b) modified, the registry key; and

reporting the process.

13. A computer-implemented method for troubleshooting configuration errors, comprising:

obtaining a log of events which are generated as a program executes, the log of events includes registry events regarding registry key accesses;

applying rules to the events of the log to determine if a sequence of events violates at least one of the rules;

when the sequence of events violates at least one of the rules, determining if the registry key involved in a violating event or an expected event has been one of;

(a) deleted and (b) modified; and

restoring the registry key to an expected key if the registry key has been one of;

(a) deleted and (b) modified, the rules identify the expected key.

14. The computer-implemented method of claim 13, further comprising:

restoring values associated with the registry key to expected values if the registry key has been one of;

(a) deleted and (b) modified, the rules identify the expected values.

15. The computer-implemented method of claim 13, further comprising:

searching earlier registry events in the log of events to identifying a process of the program which has one of;

(a) deleted and (b) modified, the registry key; and

reporting the process.

16. Computer storage media having computer-readable software embodied thereon for programming at least one processor to perform a method for anomaly detection, the method comprising:

obtaining a log of events which are generated in a learning process;

analyzing events of the learning process to identify recurring event sequences, each recurring event sequence includes a time sequence of multiple events;

generating rules based on the recurring event sequences;

obtaining a log of events which are generated in a detection process, the log of events of the learning process and the log of events of the detection process comprise registry events regarding registry key accesses;

applying the rules to events of the detection process to determine if a sequence of events of the detection process violates at least one of the rules;

determining that an error has been detected in the program, and reporting an alarm, when the sequence of the events of the detection process violates at least one of the rules;

when the sequence of the events of the detection process violates at least one of the rules, determining if the registry key involved in either a violating event or an expected event has been one of;

(a) deleted and (b) modified; and

restoring the registry key of either the violating event or expected event to an expected key if the registry key has been one of;

(a) deleted and (b) modified, the rules identify the expected key.

17. The computer storage media of claim 16, wherein the method performed further comprises:

obtaining hierarchical sequences which represent sequences of the events of the learning process by taking one or more input event sequences, and flattening the hierarchical sequences to obtain flattened hierarchical sequences, wherein the flattened hierarchical sequences includes symbols which represent single events but not multiple events, and the recurring event sequences are identified from the flattened hierarchical sequences.

18. The computer storage media of claim 16, wherein the generating rules comprises:

generating a trie based on at least a first of the recurring event sequences;

the trie comprises nodes arranged in a hierarchy according to the at least a first of the recurring event sequences, each node corresponding to an event in the at least a first of the recurring event sequences;

marking, as rule edges, edges of nodes which are determined to have, based on the at least a first of the recurring event sequences, only one outgoing transition to a lower node; and

updating the trie based on at least one additional recurring event sequence, the updating comprises unmarking a rule edge of one of the nodes which is determined to have, based further on the at least one additional recurring event sequence, more than one outgoing transition to a lower node.