PROCESSING NETWORK DATA USING A GRAPH DATA STRUCTURE

• US 20180152468A1
• Filed: 05/28/2015
• Published: 05/31/2018
• Est. Priority Date: 05/28/2015
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Nor, Igor, Hayun, Eyal, Barkol, Omer
• Granted Patent: US 10,791,131 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/14 Network analysis or design
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• 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 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

Certain described examples are directed towards analyzing network data. The network data is processed to generate a graph data structure that has edges that are associated with communication times from the network data and nodes that are associated with computer devices. Representations of the graph data structure are generated over time. Given an indication of at least a computing device, for example as involved in anomalous activity or a security incident, the representations of the graph data structure may be used to determine further associated computer devices that are associated with the indicated device.

Claims

1. A method for analyzing network data, comprising:

obtaining network data indicative of communications between a plurality of computing devices across at least one network;

processing the network data to generate a time-varying graph data structure, the time-varying graph data structure comprising node representations coupled by edge representations, each node representation corresponding to one of the plurality of computing devices, each edge representation corresponding to a communication between two of said computing devices in the at least one network and comprising data indicating a time of the communication;

indexing the time-varying graph data structure for a plurality of time periods to generate a respective plurality of indexed time period representations, each indexed time period representation of the time-varying graph data structure comprising edge representations with a time of communication within a given time period in the plurality of time periods;

obtaining an indication of at least one computing device within the plurality of computing devices that is associated with anomalous behavior and a time said anomalous behavior is detected;

identifying an indexed time period representation associated with the time said anomalous behavior is detected; and

starting from said identified indexed time period representation, processing the plurality of indexed time period representations to determine at least one further computing device within the plurality of computing devices that is also associated with the anomalous behavior.

2. The method of claim 1, wherein the network data comprises network security data.

3. The method of claim 1, wherein the network data comprises Domain Name System data.

4. The method of claim 1, wherein the indexing comprises generating at least one indexing metric for each indexed time period representation.

5. The method of claim 4, wherein the at least one indexing metric comprises at least one of a graph clustering metric, a belief propagation metric, and a page rank metric.

6. The method of claim 1, wherein:

each of the plurality of indexed time period representations is associated with a corresponding time after the time said anomalous behavior is detected; and

the plurality of indexed time period representations are used to detect anomalous behavior exhibited by the at least one further computing device after the time said anomalous behavior is detected, such that the at least one further computing device is associated with an effect of anomalous behavior of the at least one computing device.

7. The method of claim 1, wherein:

each of the plurality of indexed time period representations is associated with a corresponding time before the time said anomalous behavior is detected; and

the plurality of indexed time period representations are used to detect anomalous behavior exhibited by the at least one further computing device before the time said anomalous behavior is detected, such that the at least one further computing device is associated with a cause of anomalous behavior the at least one computing device.

8. The method of claim 1, wherein the anomalous behavior is associated with an attack on the at least one computing device.

9. The method of claim 1, wherein said obtaining comprises:

processing the plurality of indexed time period representations to determine the indication of at least one computing device within the plurality of computing devices that is associated with anomalous behavior and the time said anomalous behavior is detected.

10. An apparatus for analyzing network data comprising:

a data interface to obtain network data from an accessible data storage device;

a data storage device to store a graph data structure, the graph data structure comprising node representations coupled by edge representations;

a graph constructor to process the network data obtained via the data interface and to construct the graph data structure,

the graph constructor being configured to represent computing devices indicated in the network data as nodes of the graph data structure and to represent communications between computing devices indicated in the network data as edges of the graph data structure,

wherein the graph constructor is further configured to store representations of the graph data structure over time by associating a time of communication between computing devices with each edge in the graph data structure;

a graph indexer to index time period representations of the graph data structure, each time period representation comprising edges with a time of communication within a given time period; and

a network security analyzer to obtain an indication of at least one computing device and a time that are associated with a security incident and to process the time period representations of the graph data structure from the graph indexer, starting from a time period representation associated with the obtained time, to determine at least one further computing device associated with the security incident.

11. An apparatus according to claim 10, comprising a display device configured to output a user interface comprising a graphical representation of the graph data structure, the user interface comprising user interface components enabling playback of changes in the graph data structure over time.

12. An apparatus according to claim 11, wherein at least one metric generated by the graph indexer are used to generate the graphical representation of the graph data structure.

13. An apparatus according to claim 10, wherein the graph constructor is configured to store a classification indication for each node representation.

14. An apparatus according to claim 10, wherein the data interface is configured to implement a packet inspection tool on the at least one network to obtain the network data.

15. A non-transitory computer-readable storage medium comprising a set of computer-readable instructions stored thereon which, when executed by at least one processor, cause the at least one processor to:

obtain network data indicative of communications between a plurality of computing devices across at least one network within a particular time period,

the network data comprising, for each communication, a timestamp, a network identifier of a sending device and a network identifier of a receiving device;

process the network data to update a dynamic graph data structure to include the particular time period, the dynamic graph data structure representing a plurality of nodes coupled by edges, wherein each edge has an associated timestamp,

including causing the at least one processor to, for each communication in the network data;

associate the network identifiers of the sending device and the receiving device with respective representations of nodes in the dynamic graph data structure,

generate a representation of an edge associated with said representations of nodes and set the associated timestamp of the edge to the timestamp of the communication;

update a set of time-series metrics for the dynamic graph data structure to include the particular time period;

obtain an indication of at least one computing device within the plurality of computing devices that exhibits a presence of malicious computer program code; and

identify, using the set of time-series metrics and the indication of the at least one computing device, at least one further computing device within the plurality of computing devices that is deemed associated with the presence of malicious computer program code.