Dynamic graph anomaly detection framework and scalable system architecture

Patent metadata

Field	Value
Publication number	US-9898604-B2
Application number	US-201514924550-A
Country	US
Kind code	B2
Filing date	Oct 27, 2015
Priority date	Jun 21, 2013
Publication date	Feb 20, 2018
Grant date	Feb 20, 2018

Abstract

Machine generated event log data which includes events occurring over a window of time is received where each event includes a first node, a second node, and a timestamp. The events are aggregated into a plurality of aggregated graph snapshots. Communities within the plurality of aggregated graph snapshots are identified and community tracking links are determined between communities in the plurality of aggregated graph snapshots. A community that has an anomalous evolution in the plurality of aggregated graph snapshots compared to the evolution of other communities is identified based at least in part on the community tracking links. The communities are displayed where the display includes the community tracking links and identifies the community that has the anomalous evolution.

First claim

What is claimed is:

1. A method, comprising:
receiving, at a first segment and a second segment in a massively parallel processing (MPP) database system, machine generated event log data which includes one or more events occurring during a first window of time and one or more one or more events occurring during a first window of time, wherein each event includes a first node, a second node, and a timestamp;
aggregating the events into a plurality of aggregated graph snapshots, including by:
sending, from the first segment to the second segment, any machine generated event log data associated with events occurring during the second window of time;
sending, from the second segment to the first segment, any machine generated event log data associated with events occurring during the first window of time;
using a first hardware processor on the first segment to generate a first aggregated graph snapshot associated with the first window of time; and
using a second hardware processor on the second segment to generate a second aggregated graph snapshot associated with the second window of time;

identifying one or more communities within the plurality of aggregated graph snapshots, including by:
identifying, on the first segment, one or more communities within the first aggregated graph snapshot;
storing, on the first segment, the communities identified in the first aggregated graph snapshot;
identifying, on the second segment, one or more communities within the second aggregated graph snapshot; and
storing, on the second segment, the communities identified in the second aggregated graph snapshot;

determining one or more community tracking links between communities in the plurality of aggregated graph snapshots, including by:
sending, from the first segment to the second segment, the communities identified in the first aggregated graph snapshot;
comparing, on the second segment, the communities identified in the first aggregated graph snapshot and the communities identified in the second aggregated graph snapshot in order to generate one or more community tracking links between the communities identified in the first aggregated graph snapshot and the communities identified in the second aggregated graph snapshot; and
storing, on the second segment, the community tracking links between the communities identified in the first aggregated graph snapshot and the communities identified in the second aggregated graph snapshot;

using a processor to identify, based at least in part on the community tracking links, a community that has an anomalous evolution in the plurality of aggregated graph snapshots compared to the evolution of other communities; and
displaying the communities, wherein the display includes the community tracking links and identifies the community that has the anomalous evolution.

2. The method of claim 1 , wherein displaying further includes:
displaying a legend which indicates one or more selected communities in a current aggregated graph snapshot; and
displaying a backward navigation arrow and a forward navigation arrow associated with displaying one or more linked communities in a prior aggregated graph snapshot or a next aggregated graph snapshot, respectively, that are linked to the selected communities in the current aggregated graph snapshot.

3. The method of claim 1 , wherein displaying further includes:
displaying a legend which indicates one or more selected communities in a current aggregated graph snapshot; and
using a plurality of colors to foreshadow one or more vertices which are associated with one or more linked communities in a next aggregated graph snapshot that are linked to the selected communities in the current aggregated graph snapshot, wherein a different color is used for each linked community.

4. The method of claim 1 , wherein displaying further includes displaying, for one or more selected communities, one or more of the following characteristics: a Jaccard coefficient, a modified Jaccard coefficient, a size of a front community (F), a size of a current community, or a ratio of a size of a front community (F) to a size of a current community (C).

5. The method of claim 1 , wherein displaying further includes displaying a two-feature scatter plot, wherein a first axis of the two-feature scatter plot is associated with a modified Jaccard coefficient and a second axis of the two-feature scatter plot is associated with a ratio of a size of a front community (F) to a size of a current community (C).

6. A system, comprising:
a processor; and
a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to:
receive, at a first segment and a second segment in a massively parallel processing (MPP) database system, machine generated event log data which includes one or more events occurring during a first window of time and one or more one or more events occurring during a first window of time, wherein each event includes a first node, a second node, and a timestamp;
aggregate the events into a plurality of aggregated graph snapshots, including by:
sending, from the first segment to the second segment, any machine generated event log data associated with events occurring during the second window of time;
sending, from the second segment to the first segment, any machine generated event log data associated with events occurring during the first window of time;
generating, on the first segment, a first aggregated graph snapshot associated with the first window of time; and
generating, on the second segment, a second aggregated graph snapshot associated with the second window of time;

identify one or more communities within the plurality of aggregated graph snapshots, including by:
identifying, on the first segment, one or more communities within the first aggregated graph snapshot;
storing, on the first segment, the communities identified in the first aggregated graph snapshot;
identifying, on the second segment, one or more communities within the second aggregated graph snapshot; and
storing, on the second segment, the communities identified in the second aggregated graph snapshot;

determine one or more community tracking links between communities in the plurality of aggregated graph snapshots, including by:
sending, from the first segment to the second segment, the communities identified in the first aggregated graph snapshot;
comparing, on the second segment, the communities identified in the first aggregated graph snapshot and the communities identified in the second aggregated graph snapshot in order to generate one or more community tracking links between the communities identified in the first aggregated graph snapshot and the communities identified in the second aggregated graph snapshot; and
storing, on the second segment, the community tracking links between the communities identified in the first aggregated graph snapshot and the communities identified in the second aggregated graph snapshot;

identify, based at least in part on the community tracking links, a community that has an anomalous evolution in the plurality of aggregated graph snapshots compared to the evolution of other communities; and
display the communities, wherein the display includes the community tracking links and identifies the community that has the anomalous evolution.

7. The system of claim 6 , wherein displaying further includes:
displaying a legend which indicates one or more selected communities in a current aggregated graph snapshot; and
displaying a backward navigation arrow and a forward navigation arrow associated with displaying one or more linked communities in a prior aggregated graph snapshot or a next aggregated gr

Assignees

• Emc Ip Holding Co Llc

Inventors

• Fang Chunsheng
• Lin Derek
• Wang Teng

Classifications

• H04L63/1425 Primary

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

• G06F2221/034

  Test or assess a computer or a system · CPC title

• G06F21/56 Primary

  Computer malware detection or handling, e.g. anti-virus arrangements · CPC title

• G06F21/552

  involving long-term monitoring or reporting · CPC title

• H04L63/14

  for detecting or protecting against malicious traffic · CPC title