Graph-based network anomaly detection across time and entities

• US 10,609,059 B2
• Filed: 12/13/2018
• Issued: 03/31/2020
• Est. Priority Date: 01/30/2017
• Status: Active Grant

• Current Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Original Assignee: Splunk Inc. (Cisco Systems, Inc.)
• Inventors: Apostolopoulos, Georgios
• Primary Examiner(s): Chen, Shin-Hon (Eric)
• Application Number:
  US16/219,852
• Publication Number:
  US 20190124104A1
• Time in Patent Office: 474 Days
• Field of Search: None
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

The disclosed techniques relate to a graph-based network security analytic framework to combine multiple sources of information and security knowledge in order to detect risky behaviors and potential threats. In some examples, the input can be anomaly events or simply regular events. The entities associated with the activities can be grouped into smaller time units, e.g., per day. The riskiest days of activity can be found by computing a risk score for each day and according to the features in the day. A graph can be built with links between the time units. The links can also receive scoring based on a number of factors. The resulting graph can be compared with known security knowledge for adjustments. Threats can be detected based on the adjusted risk score for a component (i.e., a group of linked entities) as well as a number of other factors.

Claims

1. A method comprising:

accessing a relationship graph having entities as nodes, and relationships among the nodes as links, the relationship graph reflecting a batch of events that occurred during a time range;

assigning the nodes in the relationship graph to groups based on event timestamps, each group including nodes associated with activities that occurred in a corresponding time unit;

constructing links for nodes across different groups, wherein a link representing a relationship is established based on a respective activity recorded in the batch of events, each chain of linked nodes forming a component;

computing a total interest score for the formed component, wherein the total interest score reflects a totality of interest generated from all nodes attached to a given link; and

identifying a component for further security scrutiny based on the total interest score.

2. The method of claim 1, further comprising:

adjusting the total interest score for the formed component based on comparing events underlying a component with a pattern of interest, wherein the pattern of interest identifies an expected temporal order and/or logical relationship in underlying events for such component to be of interest.

3. The method of claim 1, wherein the plurality of events comprise events that have been earmarked as anomalies, and wherein each node carries an anomaly score that is assigned from a previous data analytic stage.

4. The method of claim 1, wherein the relationship graph is a subset of a composite relationship graph that includes edges representing a plurality of anomaly activities conducted by entities.

5. The method of claim 1, further comprising:

determining a group interest score for each of the groups, based on steps including;

generating the group interest score based on a set of features from a respective group, wherein the set of features are identified by a predetermined list of features that are characteristic of the activities recorded in the events in the respective group.

6. The method of claim 1, further comprising:

determining a group interest score for each of the groups, based on steps including;

generating the group interest score based on a set of features from a respective group, wherein the set of features are identified by a predetermined list of features that are characteristic of the activities recorded in the events in the respective group,

wherein a feature in the set of features carries a different weight than another feature.

7. The method of claim 1, further comprising:

determining a group interest score for each of the groups, based on steps including;

generating the group interest score based on a set of features from a respective group, wherein the set of features are identified by a predetermined list of features that are characteristic of the activities recorded in the events in the respective group,

wherein the total interest score for a formed component factors in the group interest score of the groups to which the nodes in the formed component belong.

8. The method of claim 1, further comprising:

determining a group interest score for each of the groups, based on steps including;

generating the group interest score based on a set of features from a respective group, wherein the set of features are identified by a predetermined list of features that are characteristic of the activities recorded in the events in the respective group; and

ranking the number of groups based on their group interest scores, wherein only a predetermined number of top ranked groups are further processed for constructing links for nodes between different groups.

9. The method of claim 1, further comprising:

determining a group interest score for each of the groups, based on steps including;

generating the group interest score based on a set of features from a respective group, wherein the set of features are identified by a predetermined list of features that are characteristic of the activities recorded in the events in the respective group;

ranking the number of groups based on their group interest scores, wherein only a predetermined number of top ranked groups are further processed for constructing links for nodes between different groups; and

performing clustering for the number of groups after normalizing values in the set of features in each group.

10. The method of claim 1, further comprising:

determining a link score for each link in formed components.

11. The method of claim 1, further comprising:

determining a link score for each link in formed components,

wherein the link score is determined based on a number of common nodes between the groups with which the formed component is associated.

12. The method of claim 1, further comprising:

determining a link score for each link in formed components,

wherein the link score is determined based on a distance in time between the groups with which the formed component is associated.

13. The method of claim 1, further comprising:

determining a link score for each link in formed components,

wherein the link score is determined based on an anomaly score of each node in the formed component.

14. The method of claim 1, further comprising:

determining a link score for each link in formed components,

wherein the total interest score for the formed component factors in the link score of the link that connects the nodes in the formed component.

15. The method of claim 1, further comprising:

creating a new graph using formed components, wherein the new graph includes the nodes with respective links and corresponding groups.

16. The method of claim 1, further comprising:

creating a new graph using formed components, wherein the new graph includes the nodes with respective links and corresponding group,

wherein the nodes in the new graph are coupled to underlying events so that, responsive to a request, the underlying events are produced as supporting evidence.

17. The method of claim 1, further comprising:

before assigning nodes to groups, filtering the nodes and links in the relationship graph by removing nodes that include a whitelisted entity.

18. The method of claim 1, further comprising:

before assigning nodes to groups, filtering the nodes and links in the relationship graph by removing nodes that include an entity having an exceeding number of anomaly links to other entities as compared to a threshold.

19. The method of claim 1, wherein the total interest score for a formed component increases exponentially when the events underlying the formed component matches the pattern of interest.

20. The method of claim 1, wherein the total interest score for a formed component increases exponentially when the events underlying the formed component matches the pattern of interest,

wherein the total interest score for a formed component decreases exponentially when the events underlying the formed component mismatches the pattern of interest.

21. The method of claim 1, wherein the pattern of interest includes definitions for a sequence and an anti-sequence associated with an anomaly.

22. The method of claim 1, wherein the pattern of interest includes definitions for a sequence and an anti-sequence associated with an anomaly,

wherein the total interest score for a formed component decreases exponentially when the events underlying the formed component matches the anti-sequence.

23. The method of claim 1, wherein the pattern of interest includes a malware installation followed by a file transfer or a beaconing anomaly.

24. The method of claim 1, further comprising:

performing a network security related action on the identified component.

25. The method of claim 1, wherein the entities are users, computing devices, or any combination thereof.

26. The method of claim 1, wherein the time range is more than one day, and wherein a time unit is one day.

27. The method of claim 1, wherein steps recited in the method are repeated at a predetermined periodicity.

28. The method of claim 1, wherein steps recited in the method are performed by a batch analysis engine that is implemented using APACHE SPARK™

, and wherein the relationship graph is stored in a data store that is implemented using APACHE HADOOP®

.

29. A computer system comprising:

a processor; and

a communication device, operatively coupled to the processor, through which to receive first event data indicative of computer network activity of an entity that is part of or interacts with a computer network and second event data indicative of additional computer network activity associated with the entity;

wherein the processor is configured to perform steps including;

accessing a relationship graph having entities as nodes, and relationships among the nodes as links, the relationship graph reflecting a batch of events that occurred during a time range;

assigning the nodes in the relationship graph to groups based on event timestamps, each group including nodes associated with activities that occurred in a corresponding time unit;

constructing links for nodes across different groups, wherein a link representing a relationship is established based on a respective activity recorded in the batch of events, each chain of linked nodes forming a component;

computing a total interest score for the formed component, wherein the total interest score reflects a totality of interest generated from all nodes attached to a given link; and

identifying a component for further security scrutiny based on the total interest score.

30. A non-transitory machine-readable storage medium for use in a processing system, the non-transitory machine-readable storage medium storing instructions, an execution of which in the processing system causes the processing system to perform operations comprising:

accessing a relationship graph having entities as nodes, and relationships among the nodes as links, the relationship graph reflecting a batch of events that occurred during a time range;

assigning the nodes in the relationship graph to groups based on event timestamps, each group including nodes associated with activities that occurred in a corresponding time unit;

constructing links for nodes across different groups, wherein a link representing a relationship is established based on a respective activity recorded in the batch of events, each chain of linked nodes forming a component;

computing a total interest score for the formed component, wherein the total interest score reflects a totality of interest generated from all nodes attached to a given link; and

identifying a component for further security scrutiny based on the total interest score.