Anomaly detection method

• US 6,889,218 B1
• Filed: 05/15/2000
• Issued: 05/03/2005
• Est. Priority Date: 05/17/1999
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nassehi, Mehdi
• Primary Examiner(s): Knight, Anthony
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/571,137
• Time in Patent Office: 1,814 Days
• Field of Search: 706/47, 706/48, 707/6, 714/2, 714/38
• US Class Current: 706/45
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures

Abstract

A computerized method, encoded on a computer-readable medium, of detecting anomalies in an event stream. The method comprises at least two acts. In a first act, the method uses a tree structure to extract a grammar having an associated set of rules, from a sample of normal behavior. In a second act, the method checks an event stream against the rules of the grammar to detect anomalies.

Claims

1. A computerized method, encoded on a computer-readable medium and executable on a computing device, of detecting anomalies in a data stream, the method comprising:

(a) in an off-line process, using a tree structure comprising a suffix tree having suffixes representing certain patterns of interest which have an associated length to extract a grammar from a sample of normal behavior, the grammar having an associated set of rules;

(b) in a subsequent on-line process, checking the data stream against the rules of the grammar to detect deviations; and

(c) generating an alarm indication when a deviation is detected.

2. The method of claim 1 wherein the sample of normal behavior is extracted more quickly by imposing an upper limit on the length of the patterns of interest and then inserting a prefix of a representing suffix not exceeding the number of patterns of interest into the pattern tree wherein the suffix tree is created by:

(a) selecting a maximum pattern length equal to the sum of a maximum preamble representing a portion of the data stream which precedes a repetition and twice a maximum length of the repetition;

(b) after the suffix tree under the maximum pattern length is created, constructing an auxiliary grammar; and

(c) using the auxiliary grammar to filter the sample of normal behavior such that unnecessary rules are eliminated.

3. The method of claim 1 wherein suffixes are truncated before being inserted in the suffix tree.

4. The method of claim 1 wherein a rule-matching automaton is used to detect anomalies.

5. The method of claim 1 wherein the rule-matching automaton is used to take a second pass over the sample in order to reduce the set of rules.

6. The method of claim 5 wherein an upper limit is imposed on the length of the patterns of interest in order to shorten the time required to create a suffix tree of the sample.

7. The method of claim 2 further comprising the step of performing repetition-compaction for identifying repetitions in said data stream and compacting the repetitions found, wherein said auxiliary grammar is constructed to account for said repetitions of event sequences in the rules.

8. A computerized method, encoded on a computer-readable medium executable on a computing device, of detecting anomalies in a data steam, the method comprising:

(a) in an off-line process, extracting a grammar from a sample of normal behavior, the grammar having an associated set of rules;

(b) in a subsequent on-line process, checking the data stream against the rules of the grammar to detect anomalies and generating an alarm indication when a data stream anomaly is detected; and

(c) using a rule-matching automaton to take a second pass over the sample in order to reduce the set of rules, for application in subsequent processes.