Contextual graph matching based anomaly detection

Patent metadata

Field	Value
Publication number	US-9367809-B2
Application number	US-201414173533-A
Country	US
Kind code	B2
Filing date	Feb 5, 2014
Priority date	Oct 11, 2013
Publication date	Jun 14, 2016
Grant date	Jun 14, 2016

Abstract

Contextual graph matching based anomaly detection may include evaluating computer-generated log file data to create a master directed graph that specifies known events and transitions between the known events. The master directed graph may be processed to determine a plurality of decomposed master graph walks. Incoming computer-generated log file data may be evaluated to create an incoming directed graph that specifies unknown events and transitions between the unknown events. The incoming directed graph may be processed to determine a decomposed incoming walk. Overlap, distance difference, and correlation scores may be determined for each walk pair of a plurality of walk pairs including each of the plurality of decomposed master graph walks and the decomposed incoming walk. One of the decomposed master graph walks may be selected based on the overlap score, the difference score, and the correlation score, to detect an anomaly.

First claim

What is claimed is:

1. A contextual graph matching based anomaly detection system comprising:
at least one processor;
a master directed graph generator, executed by the at least one processor, to evaluate computer-generated log file data to create, in a computer memory, a master directed graph that specifies known events and transitions between the known events;
a master directed graph decomposer, executed by the at least one processor, to process the master directed graph to identify a plurality of unique walks through the master directed graph, and to decompose the plurality of unique walks into their probability distributions as a plurality of decomposed master graph walks;
an incoming directed graph generator, executed by the at least one processor, to evaluate incoming computer-generated log file data to create an incoming directed graph that specifies unknown events and transitions between the unknown events;
an incoming directed graph decomposer, executed by the at least one processor, to process the incoming directed graph to identify an incoming walk through the incoming directed graph, and to decompose the incoming walk into its probability distribution as a decomposed incoming walk;
a graph matcher, executed by the at least one processor, to:
determine an overlap score for each walk pair of a plurality of walk pairs including each of the plurality of decomposed master graph walks and the decomposed incoming walk,
determine a distance difference score for each walk pair of the plurality of walk pairs, and
determine a correlation score for each walk pair of the plurality of walk pairs; and

an anomaly detector, executed by the at least one processor, to select one of the plurality of decomposed master graph walks based on the overlap score, the difference score, and the correlation score, and to detect an anomaly based on the selected one of the plurality of decomposed master graph walks.

2. The contextual graph matching based anomaly detection system according to claim 1 , wherein the graph matcher is to determine the overlap score by evaluating an intersection and a union of an edge set of one of the plurality of decomposed master graph walks and an edge set of the decomposed incoming walk.

3. The contextual graph matching based anomaly detection system according to claim 1 , wherein the graph matcher is to determine the distance difference score by evaluating an edge weight from an edge set of one of the plurality of decomposed master graph walks and an edge weight from an edge set of the decomposed incoming walk.

4. The contextual graph matching based anomaly detection system according to claim 1 , wherein the graph matcher is to determine the correlation score by evaluating an edge belonging to an edge set of one of the plurality of decomposed master graph walks and an edge belonging to an edge set of the decomposed incoming walk.

5. The contextual graph matching based anomaly detection system according to claim 1 , wherein the master directed graph decomposer is to rank the plurality of unique walks through the master directed graph according to a probability of occurrence, wherein the probability of occurrence is based on an edge set of one of the plurality of decomposed master graph walks and adjacent nodes within the master directed graph.

6. The contextual graph matching based anomaly detection system according to claim 1 ,
wherein the master directed graph decomposer is to rank the plurality of unique walks through the master directed graph according to a probability of occurrence, wherein the probability of occurrence is based on an edge set of one of the plurality of decomposed master graph walks and adjacent nodes within the master directed graph, and
wherein the anomaly detector is to evaluate a scaled fitness metric related to each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein the scaled fitness metric is based on a ranking coefficient related to the rank of the plurality of unique walks through the master directed graph, and a degree of fitness metric related to each walk pair of the plurality of walk pairs.

7. The contextual graph matching based anomaly detection system according to claim 1 ,
wherein the master directed graph decomposer is to rank the plurality of unique walks through the master directed graph according to a probability of occurrence, wherein the probability of occurrence is based on an edge set of one of the plurality of decomposed master graph walks and adjacent nodes within the master directed graph, and
wherein the anomaly detector is to determine a maximal anomaly metric from scaled fitness metrics related to each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein a scaled fitness metric of the scaled fitness metrics is based on a ranking coefficient related to the rank of the plurality of unique walks through the master directed graph, and a degree of fitness metric related to each walk pair of the plurality of walk pairs.

8. The contextual graph matching based anomaly detection system according to claim 1 ,
wherein the master directed graph decomposer is to rank the plurality of unique walks through the master directed graph according to a probability of occurrence, wherein the probability of occurrence is based on an edge set of one of the plurality of decomposed master graph walks and adjacent nodes within the master directed graph, and
wherein the anomaly detector is to evaluate a scaled identified maximal walkpair fitness metric for each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein the scaled identified maximal walkpair fitness metric is based on a ranking coefficient related to the rank of the plurality of unique walks through the master directed graph, a degree of fitness metric related to each walk pair of the plurality of walk pairs, and the correlation score.

9. The contextual graph matching based anomaly detection system according to claim 8 , wherein the scaled identified maximal walkpair fitness metric is to provide a percentage anomalousness of the decomposed incoming walk.

10. The contextual graph matching based anomaly detection system according to claim 1 , wherein the anomaly detector is to evaluate a kernel transformation function related to each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks.

11. The contextual graph matching based anomaly detection system according to claim 10 , wherein the anomaly detector is to evaluate a degree of fitness metric for each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks, wherein the degree of fitness metric is based on the kernel transformation function, the overlap score, and the distance difference score.

12. The contextual graph matching based anomaly detection system according to claim 1 , wherein the anomaly detector is to evaluate a directionality for each walk pair of the plurality of walk pairs for selecting the one of the plurality of decomposed master graph walks.

13. A method for contextual graph matching based anomaly detection, the method comprising:
evaluating, by a processor, computer-generated log file data to create, in a computer memory, a master directed graph that specifies known events and transitions between the known events;
processing the master directed graph to identify a plurality of unique walks through the master directed graph, and to decompose the plurality of unique

Assignees

• Puri Colin A
• Nguyen John K
• Kurth Scott W
• Accenture Global Services Ltd

Inventors

• Puri Colin A
• Nguyen John K
• Kurth Scott W

Classifications

• H04L63/1425

  Traffic logging, e.g. anomaly detection · CPC title

• G06F11/0751

  Error or fault detection not based on redundancy (power supply failures G06F1/30; network fault management H04L41/06) · CPC title

• G06F16/2455

  Query execution · CPC title

• G06F11/0709

  in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems · CPC title

• G06F21/552

  involving long-term monitoring or reporting · CPC title