Systems and methods for detecting online attacks

• US 9,183,387 B1
• Filed: 06/05/2013
• Issued: 11/10/2015
• Est. Priority Date: 06/05/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Altman, Alon, Epasto, Alessandro
• Primary Examiner(s): Pearson, David
• Assistant Examiner(s): Plecha, Thaddeus
• Application Number:
  US13/911,011
• Time in Patent Office: 888 Days
• Field of Search: 726/23
• US Class Current: 1/1
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• 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

Abstract

Detecting online attacks is described, including identifying one or more events associated with users on a social graph. For each type of event of the one or more events, generating at least one directed acyclic graph (DAG), where each node on the DAG represents a node on the social graph where an event of the type occurs and each edge on the DAG represents a propagation of the event from a first node of the edge to a second node of the edge.

Claims

1. A computer-implemented method, comprising:

detecting a plurality of events based on an analysis of a data stream by identifying the plurality of events as being associated with users on a social graph, the social graph comprising a plurality of social graph nodes and social graph edges and each of the plurality of events having a type, to receive one or more indicators of an online attack;

analyzing propagation of the plurality of events by, for each type of the plurality of events, generating at least one directed acyclic graph (DAG) comprising a plurality of DAG nodes and DAG edges, where each DAG node on the DAG represents a corresponding social graph node on the social graph where a subset of events of the plurality of events having a particular type occur and each of the DAG edges of the DAG represents a propagation of each event of the subset of events of the particular type from a first social graph node to a second social graph node, and assessing a confidence level that the plurality of events are online attack events;

performing a cluster analysis comprising analysis of pairs of the plurality of events that have been graphed on the DAG as having been propagated, wherein the cluster analysis is repeated for each type of the plurality of events and one or more timings of the plurality of events; and

providing an updated confidence level associated with the plurality of events being the online attack events based on the cluster analysis,

wherein an identity of an online attacker associated with the online attack events is further associated with the social graph.

2. The method of claim 1, wherein the propagation of each event of the subset of events of the particular type from the first social graph node to the second social graph node is based on each event of the subset of events of the particular type occurring at a time T1 at the first social graph node, each event of the subset of events of the particular type occurring at a time T2 at the second social graph node, and T1 is earlier than T2.

3. The method of claim 1, wherein the propagation of each event of the subset of events of the particular type from the first social graph node to the second social graph node comprises propagation of a first event of the subset of events of the particular type occurring at the first social graph node to a second event of the subset of events of the particular type occurring at the second social graph node, and content of the first event is related to content of the second event.

4. The method of claim 1, wherein one of the plurality of events comprises a posting of information on a social network.

5. The method of claim 1, further comprising:

determining a cluster of the at least one DAG; and

determining a score associated with the cluster, wherein the score is based on a size of the cluster, which is a sum of a number of the DAG nodes of the at least one DAG.

6. The method of claim 1, further comprising:

performing the cluster analysis concurrently on the pairs of the plurality of events that have been propagated.

7. The method of claim 1, wherein the generating the DAG comprises determining whether the plurality of events are an online attack events, determining a degree of the online attack events, and determining a direction of the online attack events.

8. At least one computing device comprising non-transitory storage and a hardware processor configured to perform:

detecting a plurality of events based on an analysis of a data stream by identifying the plurality of events as being associated with users on a social graph, the social graph comprising a plurality of social graph nodes and social graph edges and each of the plurality of events having a type, to receive one or more indicators of an online attack;

analyzing propagation of the plurality of events by, for each type of the plurality of events, generating at least one directed acyclic graph (DAG) comprising a plurality of DAG nodes and DAG edges, where each DAG node on the DAG represents a corresponding social graph node on the social graph where a subset of events of the plurality of events having a particular type occur and each of the DAG edges of the DAG represents a propagation of each event of the subset of events of the particular type from a first social graph node to a second social graph node, and assessing a confidence level that the plurality of events are online attack events;

performing a cluster analysis comprising analysis of pairs of the plurality of events that have been graphed on the DAG as having been propagated, wherein the cluster analysis is repeated for each type of the plurality of events and one or more timings of the plurality of events; and

providing an updated confidence level associated with the plurality of events being the online attack events based on the cluster analysis,

wherein an identity of an online attacker associated with the online attack events is further associated with the social graph.

9. The at least one computing device of claim 8, wherein the propagation of each event of the subset of events of the particular type from the first social graph node to the second social graph node is based on each event of the subset of events of the particular type occurring at a time T1 at the first social graph node, each event of the subset of events of the particular type occurring at a time T2 at the second social graph node, and T1 is earlier than T2.

10. The at least one computing device of claim 8, wherein the propagation of each event of the subset of events of the particular type from the first social graph node to the second social graph node comprises propagation of a first event of the subset of events of the particular type occurring at the first social graph node to a second event of the subset of events of the particular type occurring at the second social graph node, and content of the first event is related to content of the second event.

11. The at least one computing device of claim 8, further comprising:

determining a cluster of the at least one DAG; and

determining a score associated with the cluster.

12. The at least one computing device of claim 11, wherein the score is based on a size of the cluster, which is a sum of a number of the DAG nodes of the at least one DAG.

13. A non-transitory computer readable medium having stored therein computer executable instructions for:

(a) detecting an event of a plurality of events that is associated with a first user, each of the plurality of events having a type;

(b) determining that the first user is associated with a first social graph node on a social graph;

(c) adding a directed acyclic graph (DAG) node to a DAG corresponding to the first social graph node on the social graph;

(d) assigning the DAG node on the DAG as a current node;

(e) determining that the event occurs at a time T1;

(f) identifying at least one or more second users associated with at least one second social graph node adjacent to the first social graph node on the social graph corresponding with the current node;

(g) determining if the one or more second users are associated with an occurrence of another event having a same type as the event associated with the first user and for each of the determined one or more second users;

(g1) adding a second DAG node to the DAG corresponding to the at least one second social graph node on the social graph, the added second DAG node being considered as one new node;

(g2) determining that the another event having the same type as the event associated with the first user occurs at a time T2; and

(g3) adding a directed edge between the current node and the one new node to indicate propagation of the another event with the directed edge pointing to the current node if T1 is later than T2 or pointing to the one new node if T2 is later than T1;

(h) storing the DAG;

(i) assessing a confidence level that the plurality of events are online attack events based on the DAG;

(j) performing a cluster analysis comprising analysis of pairs of the plurality of events that have been graphed on the DAG as having been propagated, wherein the cluster analysis is repeated for each type of the plurality of events and one or more timings of the plurality of events; and

(k) providing an updated confidence level associated with the plurality of events being the online attack events based on the cluster analysis.

14. The computer readable medium of claim 13, further comprising:

for the one new node;

assigning the one new node as the current node;

assigning a current value of T2 associated with the one new node as a new value of T1, and setting a new value of T2; and

repeating the operations (f), (g), (g1), (g2), and (g3);

wherein each of the operations (f), (g), (g1), (g2), and (g3) is terminated when a stopping condition is reached.

15. The computer readable medium of claim 13, wherein the event associated with the first user comprises a posting of information on a social network.

16. The computer readable medium of claim 13, wherein content of the another event is related to content of the event associated with the first user.

17. The computer readable medium of claim 13, further comprising determining a score based on a size of the DAG.

18. The computer readable medium of claim 13, further comprising determining a score based on comparing at least one aspect of the DAG with the at least one aspect of at least one other DAG.