Detection of clustering in graphs in network security analysis

Patent metadata

Field	Value
Publication number	US-10003605-B2
Application number	US-201514929182-A
Country	US
Kind code	B2
Filing date	Oct 30, 2015
Priority date	Aug 31, 2015
Publication date	Jun 19, 2018
Grant date	Jun 19, 2018

Abstract

A security platform employs a variety techniques and mechanisms to detect security related anomalies and threats in a computer network environment. The security platform is “big data” driven and employs machine learning to perform security analytics. The security platform performs user/entity behavioral analytics (UEBA) to detect the security related anomalies and threats, regardless of whether such anomalies/threats were previously known. The security platform can include both real-time and batch paths/modes for detecting anomalies and threats. By visually presenting analytical results scored with risk ratings and supporting evidence, the security platform enables network security administrators to respond to a detected anomaly or threat, and to take action promptly.

First claim

What is claimed is:

1. A method comprising:
receiving, at a computer system, event data indicative of network activity of a plurality of entities that are part of or that interact with a computer network;
constructing, by the computer system and based on the event data, a graph that represents relationships among the plurality of entities, the graph including a plurality of nodes that each represent a different one of the entities that are part of or that interact with the computer network and a plurality of edges that represent relationships between pairs of the nodes;
performing, by the computer system, a cluster identification process to identify a node cluster of the plurality nodes, the cluster identification process including computing L1-norm values for the nodes to assign positions to the nodes on a one-dimensional (1D) grid, based on the graph, and identifying the node cluster based on the assigned positions of the nodes on the 1D grid; and
detecting, by the computer system, a network security anomaly based on the identified node cluster.

2. A method as recited in claim 1 , wherein the event data comprise machine data.

3. A method as recited in claim 1 , wherein the event data comprise timestamped machine data.

4. A method as recited in claim 1 , wherein the cluster identification process comprises assigning to each node a position on the 1D grid where an L1-norm for the node has a minimum value.

5. A method as recited in claim 1 , providing, via a user interface, an indication of the detected network security anomaly.

6. A method as recited in claim 1 , further comprising:
performing the cluster identification process to identify a plurality of node clusters of the plurality nodes, based on the graph; and
identifying a network security anomaly associated with network activity on the computer network, based on the plurality of node clusters.

7. A method as recited in claim 1 , wherein the cluster identification process is a logic process of a machine learning model.

8. A method as recited in claim 1 , wherein at least one of the entities is a device on the computer network.

9. A method as recited in claim 1 , wherein at least one of the entities is a user of a device on the computer network.

10. A method as recited in claim 1 , wherein at least one of the entities is a device on the computer network and at least one other of the entities is a user of a device on the computer network.

11. A method as recited in claim 1 , wherein said detecting the network security anomaly comprises detecting a deviation from a normal behavioral pattern of an entity based on the identified node cluster.

12. A method as recited in claim 1 , wherein said detecting the network security anomaly comprises:
identifying a relationship between an entity and the identified node cluster;
detecting a deviation from a normal behavioral pattern of an entity based on the identified relationship between the entity and the identified node cluster; and
detecting the network security anomaly in response to detecting the deviation.

13. A method as recited in claim 1 , wherein said detecting the network security anomaly comprises:
determining that an entity is a member of the identified node cluster or normally interacts with an entity that is a member of the identified node cluster;
detecting that the entity has engaged in an activity that represents a divergence from the identified node cluster; and
detecting the network security anomaly in response to detecting that the entity has engaged in an activity that represents a divergence from the identified node cluster.

14. A method as recited in claim 1 , further comprising:
receiving additional event data indicative of network activity of at least one entity that is part of or has interacted with the computer network;
adding a new node to the graph data structure based on the additional event data; and
determining an optimal position of the new node on the 1D grid by computing L1-norm values for the new node, without altering a position of at least one other node on the 1D grid.

15. A method as recited in claim 1 , wherein the cluster identification process comprises:
mapping each of the plurality of nodes onto the 1D grid;
creating one or more node groups from the plurality of nodes, each said node group being two or more nodes that have the same position on the 1D grid, by iteratively relocating one or more of the nodes on the 1D grid to positions where an L1-norm value for each node is minimized;
determining whether any node in any said node group is a floater node, a floater node being a node whose total number of external edges have a weight that exceeds a weight of the total number of internal edges of the node;
in response to determining that a node in one said node group is a floater node, relocating the floater node within the 1D grid; and
in response to determining that no node in any said node group is a floater node, identifying one said node group as the node cluster.

16. A method as recited in claim 1 , wherein the cluster identification process comprises:
mapping each of the plurality of nodes onto the 1D grid;
creating one or more node groups from the plurality of nodes, each said node group being two or more nodes that have the same position on the 1D grid, by iteratively:
computing L1-norm values for the node at positions on the 1D grid corresponding to each other node to which the node is directly connected in the graph,
determining an optimal position for each node as a position on the1D grid where an L1-norm value for the node is minimized, and
relocating one or more of the nodes on the 1D grid according to the optimal position determined for each node;

counting, for each node in each of the node groups, a number of internal edges of the node and a number of external edges of the node;
determining whether any node of the plurality of nodes is a floater node, a floater node being a node whose total number of external edges have a weight that exceeds a weight of the total number of internal edges of the node;
in response to determining that at least one node in at least one node group is a floater node, relocating each said floater node within the 1D grid;
repeating said creating, said counting and said determining until none of the plurality of nodes is a floater node; and
after completion of said repeating, identifying a remaining node group as the node cluster.

17. A method as recited in claim 1 , wherein the graph is a bipartite graph.

18. A method as recited in claim 1 , wherein the graph is a bipartite graph, the plurality of nodes being normal nodes of the bipartite graph, the bipartite graph further including a plurality of pseudo-nodes connected by edges to the normal nodes; and
wherein the cluster identification process comprises:
mapping each of the normal nodes onto the 1D grid;
creating one or more node groups from the plurality of normal nodes, each said node group being two or more normal nodes that have the same position on the 1D grid, wherein said creating one or more node groups includes, for each said normal node,
identifying all pseudo-nodes to which the normal node is directly connected in the bipartite graph,
identifying positions, on the 1D grid, of all normal nodes to which the identified pseudo-node(s) is/are connected, and
assigning, to the normal node, a position on the 1D grid that corresponds to a minimized L1-norm for the normal node, relative to the positions on the 1D grid of the normal nodes to which the identified pseudo-node(s) is/are

Assignees

• Splunk Inc

Inventors

• Muddu Sudhakar
• Tryfonas Christos

Classifications

• G06N20/20 Primary

  Ensemble learning · CPC title

• H04L63/1416 Primary

  Event detection, e.g. attack signature detection · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F40/134

  Hyperlinking · CPC title

• G06F3/04847

  Interaction techniques to control parameter settings, e.g. interaction with sliders or dials · CPC title