Graph based detection of anomalous activity

• US 9,225,730 B1
• Filed: 03/19/2014
• Issued: 12/29/2015
• Est. Priority Date: 03/19/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Brezinski, Dominique Imjya
• Primary Examiner(s): Gee, Jason K
• Application Number:
  US14/219,819
• Time in Patent Office: 650 Days
• Field of Search: 726/23
• US Class Current: 1/1
• CPC Class Codes: G06F 21/00 Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Techniques are described for graph-based analysis of event data in a computing environment. Event data is collected from host devices, the event data describing events in which devices, processes, or services are accessed in the environment. The event data is arranged into a graph that includes vertices corresponding to devices, processes, or services, and edges that connect pairs of vertices. Each edge may identify an event by connecting two vertices corresponding to two devices, processes, or services included in the event. A rarity metric is determined for each edge, indicating a rarity of events of a particular type connecting two vertices. A risk metric may also be determined for each edge, indicating a security risk associated with the event type or the target of the event. The graph may be traversed according to the risk and rarity metrics, to identify patterns of anomalous activity in the event data.

Claims

1. A computer-implemented method, comprising:

accessing event data describing a plurality of events associated with a plurality of host devices, individual ones of the plurality of events including an interaction between a first entity and a second entity, the first and second entities including two of;

a host device of the plurality of host devices;

a process that is executable on at least one of the host devices;

or

a service that is provided by the plurality of host devices, the service comprising a plurality of executable processes;

generating a graph based at least partially on the event data, the graph relating the plurality of events, wherein the graph includes;

a plurality of vertices, individual ones of the plurality of vertices associated with one of the first or second entities included in the plurality of events; and

a plurality of edges, individual ones of the plurality of edges indicating an event by connecting two of the plurality of vertices corresponding to the first and second entities included in the event, individual ones of the plurality of edges including;

a type attribute indicating a type of the event; and

a timestamp attribute indicating a time when the event occurred;

determining a rarity metric associated with one or more of the plurality of edges, the rarity metric of an edge being based on a number of edges that include a same type attribute as the edge and that connect a same two vertices as the edge;

determining a risk metric of one or more of the plurality of edges, the risk metric of the edge indicating a degree of security risk associated with the event corresponding to the edge;

determining a start vertex associated with an earliest timestamp attribute within a time period;

traversing the graph, beginning from the start vertex, along at least a portion of the plurality of edges, wherein each successive traversed edge includes a timestamp attribute greater than that of a previously traversed edge to identify a subset of the plurality of edges for which the rarity metric satisfies a rarity threshold and the risk metric satisfies a risk threshold;

determining the subset of the plurality of edges for which the rarity metric satisfies the rarity threshold and the risk metric satisfies the risk threshold to indicate anomalous activity;

storing data indicative of the subset of the plurality of edges as anomalous activity data for determining a pattern of anomalous activity within the plurality of host devices; and

performing one or more interdiction operations based on the anomalous activity data, the one or more interdiction operations including suspending a communication with at least one host device indicated by the anomalous activity data.

2. The method of claim 1, wherein:

the one or more of the plurality of edges further include a user attribute indicating a user associated with the event; and

the risk metric of an edge is based on access privileges of the user.

3. The method of claim 1, wherein:

at least one edge of the plurality of edges indicates a network connection event associated with a network connection between the first entity and the second entity; and

the risk metric of the at least one edge is based on whether the network connection is encrypted.

4. The method of claim 1, wherein the start vertex is associated with the first entity that corresponds to a desktop computing device and that is connected by the edge that includes the earliest timestamp attribute within the time period.

5. The method of claim 1, further comprising:

determining the type attribute to be associated with at least two edges connecting a first vertex and a second vertex;

determining one or more summary attribute values based on attribute values associated with the at least two edges;

providing the graph with an overlay edge associated with the type attribute and the one or more summary attribute values; and

associating the rarity metric with the overlay edge.

6. A system, comprising:

at least one computing device configured to implement one or more services, wherein the one or more services are configured to;

generate a graph corresponding to a plurality of events, individual ones of the plurality of events including an interaction between entities present in a plurality of host devices, the entities including at least two of;

a host device, a process, or a service, the graph comprising;

a plurality of vertices, individual ones of the plurality of vertices associated with one of the entities included in the plurality of events; and

a plurality of edges, individual ones of the plurality of edges indicating an event by connecting two of the plurality of vertices corresponding to the entities included in the event, individual ones of the plurality of edges including a timestamp attribute indicating a time when the event occurred;

determine a rarity metric of one or more of the plurality of edges, the rarity metric of an edge being based at least partly on a number of edges that connect a same two vertices as the edge;

traverse the graph along at least a portion of the plurality of edges in an order in which each successive edge traversed includes the timestamp attribute greater than that of a previously traversed edge to identify a subset of the plurality of edges for which the rarity metric satisfies a rarity threshold;

determine the subset of the plurality of edges for which the rarity metric satisfies the rarity threshold to indicate anomalous activity;

store data indicative of the subset of the plurality of edges as anomalous activity data for determining a pattern of anomalous activity within the plurality of host devices; and

suspend a communication with at least one host device indicated by the anomalous activity data.

7. The system of claim 6, wherein:

individual ones of the plurality of edges include a type attribute indicating a type of the event; and

the rarity metric of the edge is based on the number of edges that include a same type attribute as the edge and that connect the same two vertices as the edge.

8. The system of claim 6, wherein:

individual ones of the plurality of edges include a type attribute and a user attribute, the type attribute indicating a type of the event and the user attribute indicating a user associated with the event; and

the rarity metric of the edge is based on the number of edges that include a same type attribute as the edge, that include a same user attribute as the edge, and that connect the same two vertices as the edge.

9. The system of claim 6, wherein:

the one or more services are further configured to determine a risk metric of one or more of the plurality of edges, the risk metric of the edge indicating a degree of security risk associated with the event corresponding to the edge; and

the traversing of the graph identifies the subset of the plurality of edges for which the rarity metric satisfies the rarity threshold and the risk metric satisfies a risk threshold.

10. The system of claim 9, wherein:

one or more of the plurality of edges further include a user attribute indicating a user associated with the event; and

the risk metric of the edge is based on access privileges of the user.

11. The system of claim 9, wherein:

at least one edge of the plurality of edges indicates a network connection event associated with a network connection between the entities; and

the risk metric of the at least one edge is based on whether the network connection is encrypted.

12. The system of claim 9, wherein:

at least one of the entities is the host device;

at least one edge of the plurality of edges indicates a data access event including an access to data stored on the host device; and

the risk metric of the at least one edge is based on whether the data includes confidential data.

13. The system of claim 6, the traversing of the graph further comprising:

selecting a start vertex from the plurality of vertices, the start vertex being one or more of;

a vertex that corresponds to a desktop computing device;

or

the vertex that is connected by the edge that includes an earliest timestamp attribute within a time period; and

the traversing of the graph beginning from the start vertex.

14. The system of claim 6, wherein the one or more services are further configured to:

determine a common attribute value to be associated with at least two edges connecting a first vertex and a second vertex;

determine one or more summary attribute values based on attribute values associated with the at least two edges;

provide the graph with an overlay edge associated with the common attribute value and the one or more summary attribute values;

remove the at least two edges from the graph; and

associate the rarity metric with the overlay edge.

15. One or more non-transitory computer-readable media storing instructions which, when executed by at least one processor, instruct the at least one processor to perform actions comprising:

generating a graph corresponding to a plurality of events, individual ones of the plurality of events including interactions between entities present in a plurality of host devices, the entities including at least two of;

a host device, a process, or a service, the graph including;

a plurality of vertices, individual ones of the plurality of vertices associated with one of the entities included in the plurality of events; and

a plurality of edges, individual ones of the plurality of edges indicating an event by connecting two of the plurality of vertices corresponding to the entities included in the event, individual ones of the plurality of edges including a timestamp attribute indicating a time when the event occurred;

determining a risk metric of one or more of the plurality of edges, the risk metric of an edge indicating a degree of security risk associated with the event corresponding to the edge;

traversing the graph along at least a portion of the plurality of edges in an order in which each successive edge traversed includes a timestamp attribute greater than that of a previously traversed edge to identify a subset of the plurality of edges for which the risk metric satisfies a risk threshold;

determining the subset of the plurality of edges for which the risk metric satisfies the risk threshold to indicate anomalous activity;

storing data indicative of the subset of the plurality of edges as anomalous activity data for determining a pattern of anomalous activity within the plurality of host devices; and

performing one or more interdiction operations based on the anomalous activity data, the one or more interdiction operations including suspending communications with at least one host device indicated by the anomalous activity data.

16. The one or more non-transitory computer-readable media of claim 15, wherein:

the actions further comprise determining a rarity metric of one or more of the plurality of edges, the rarity metric of the one or more of the plurality of edges being based at least partly on a number of edges that connect a same two vertices as the edge; and

the traversing of the graph identifies the subset of the plurality of edges for which the rarity metric satisfies a rarity threshold and the risk metric satisfies the risk threshold.

17. The one or more non-transitory computer-readable media of claim 15, the traversing of the graph further comprising:

selecting a start vertex from the plurality of vertices, the start vertex being one or more of;

a vertex that corresponds to a desktop computing device;

or

the vertex that is connected by the edge that includes an earliest timestamp attribute within a time period; and

the traversing of the graph beginning from the start vertex.

18. The one or more non-transitory computer-readable media of claim 15, wherein:

individual ones of the plurality of edges include a directionality from a first vertex to a second vertex;

the first vertex corresponds to a first entity that initiates the event; and

the second vertex corresponds to a second entity that is a target of the event.

19. The one or more non-transitory computer-readable media of claim 15, wherein:

individual ones of the plurality of edges further include a user attribute indicating a user associated with the event; and

the risk metric of the edge is based on access privileges of the user.

20. The one or more non-transitory computer-readable media of claim 15, the actions further comprising:

determining a common attribute value to be associated with at least two edges connecting a first vertex and a second vertex;

determine one or more summary attribute values based on attribute values associated with the at least two edges;

provide the graph with an overlay edge associated with the common attribute value and the one or more summary attribute values;

determine a rarity metric associated with the overlay edge, wherein the rarity metric is based at least partly on a number of edges connecting the first vertex and the second vertex.