Detection of clustering in graphs in network security analysis

• US 10,003,605 B2
• Filed: 10/30/2015
• Issued: 06/19/2018
• Est. Priority Date: 08/31/2015
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Muddu, Sudhakar, Tryfonas, Christos
• Primary Examiner(s): DADA, BEEMNET W
• Application Number:
  US14/929,182
• Publication Number:
  US 20170063909A1
• Time in Patent Office: 963 Days
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/0484 for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06F 3/04847 Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
• CPC Class Codes: G06F 40/134 Hyperlinking
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06V 10/225 based on a marking or identifier characterising the area
• CPC Class Codes: H04L 2463/121 Timestamp cryptographic mechanisms or cryptographic arrangements involving time stamps H04L9/3297
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 43/00 : Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/045 : for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/062 : related to network traffic
• CPC Class Codes: H04L 43/08 : Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/1408 : by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 63/1416 : Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/1425 : Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/1433 : Vulnerability analysis
• CPC Class Codes: H04L 63/1441 : Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 63/20 : for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H05K 999/99 : dummy group

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.

Claims

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 connected; and

identifying one said node group as the node cluster.

19. A method as recited in claim 1, wherein the graph is a bipartite graph and the plurality of nodes are 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 minimum and maximum of 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 midpoint between said minimum and maximum positions;

determining whether any normal node of the plurality of normal nodes moved during a last iteration of said creating one or more node groups; and

in response to determining that at least one normal node moved during the last iteration of said creating one or more node groups, repeating said creating one or more node groups;

or

in response to determining that no normal node moved during the last iteration of said creating one or more node groups, identifying one said node group as the node cluster.

20. A computer system comprising:

a processor; and

a communication device, operatively coupled to the processor, through which to receive event data indicative of network activity of a plurality of entities that are part of or that interact with a computer network;

wherein the processor is configured to

construct, based on the event data, a graph that represents relationships among the plurality of entities that are part of or that interact with the computer network, the graph including a plurality of nodes that each represent a different one of the entities and a plurality of edges that represent relationships between pairs of the nodes;

perform 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 plurality of 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

detect a network security anomaly based on the identified node cluster.

21. A computer system as recited in claim 20, wherein the event data comprise timestamped machine data.

22. A computer system as recited in claim 20, wherein the cluster identification process comprises assigning to each node a position on the1D grid where an L1-norm for the node has a minimum value.

23. A computer system as recited in claim 20, wherein detecting the network security anomaly comprises detecting a deviation from a normal behavioral pattern of an entity based on the identified node cluster.

24. A computer system as recited in claim 20, wherein 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.

25. A computer system as recited in claim 20, 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.

26. 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:

receiving event data indicative of network activity of a plurality of entities that are part of or that interact with a computer network;

constructing, 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 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 plurality of 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 a network security anomaly based on the identified node cluster.

27. A non-transitory machine-readable storage medium as recited in claim 26, wherein the cluster identification process comprises assigning to each node a position on the1D grid where an L1-norm for the node has a minimum value.

28. A non-transitory machine-readable storage medium as recited in claim 26, wherein detecting the network security anomaly comprises detecting a deviation from a normal behavioral pattern of an entity based on the identified node cluster.

29. A non-transitory machine-readable storage medium as recited in claim 26, wherein 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.

30. A non-transitory machine-readable storage medium as recited in claim 26, 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.