Graph-based techniques for detecting coordinated network attacks

• US 9,942,252 B1
• Filed: 12/21/2015
• Issued: 04/10/2018
• Est. Priority Date: 09/08/2015
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Kondaveeti, Anirudh, Yu, Jin
• Primary Examiner(s): Arani, Taghi
• Assistant Examiner(s): Naghdali, Khalil
• Application Number:
  US14/976,168
• Time in Patent Office: 841 Days
• Field of Search: 726 23
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: H04L 2463/144 Detection or countermeasures against botnets
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0281 Proxies
• 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/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

One or more proxy logs are processed in order to generate a graph of domains, wherein those domain pairs in the graph that are connected have low support and high confidence. One or more domains within the graph that are highly connected to other domains in the graph are identified. The identified domains are flagged as suspicious domains.

Claims

1. A system, comprising:

a processor; and

a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions which when executed cause the processor to;

process one or more proxy logs in order to generate a graph of domains, wherein those domain pairs in the graph that are connected have low support in that the number of times the domain pairs are visited is lower than a predetermined support threshold and high confidence in that users accessing the domain pairs are redirected to another domain a greater number of times than a predetermined confidence threshold;

identify one or more domains within the graph that are highly connected to other domains in the graph in that the one or more domains have a degree of connectivity to said other domains higher than a connectivity threshold; and

flag the identified domains as suspicious domains, wherein processing the proxy logs includes;

deciding whether to normalize domain names;

in the event it is decided to normalize domain names, normalizing domain names so that all domain names are at a same level;

deciding whether to filter domain names using a whitelist;

in the event it is decided to filter domain names, filtering out whitelisted domains using the whitelist;

filtering out invalid domain names;

performing user-specific sessionization using a specified time window to create a plurality of buckets;

calculating a support value and a confidence value for each possible domain pair from the overall plurality of buckets in the full dataset; and

creating an edge in the graph between those domain pairs that have a support value that is less than a support threshold and a confidence value that is greater than a confidence threshold.

2. The system recited in claim 1, wherein processing the proxy logs includes:

for each domain in the graph, determining an OddBall ratio for that domain;

comparing each of the determined OddBall ratios against the connectivity threshold; and

identifying those domains with an OddBall ratio greater than the connectivity threshold as being highly connected.

3. The system recited in claim 1, wherein identifying the domains includes:

for each domain in the graph, determining a clique percentage for that domain;

comparing each of the determined clique percentages against the connectivity threshold; and

selecting those domains with a clique percentage greater than the connectivity threshold.

4. The system recited in claim 1, wherein identifying the domains includes:

identifying one or more connected components in the graph, wherein each of the connected components has a size; and

comparing each of the sizes of the connected components against a size threshold; and

selecting those connected components with a size smaller than the size threshold.

5. The system recited in claim 1, wherein the system includes a parallel database.

6. A method, comprising:

using a processor to process one or more proxy logs in order to generate a graph of domains, wherein those domain pairs in the graph that are connected have low support in that the number of times the domain pairs are visited is lower than a predetermined support threshold and high confidence in that users accessing the domain pairs are redirected to another domain a greater number of times than a predetermined confidence threshold;

identifying one or more domains within the graph that are highly connected to other domains in the graph in that the one or more domains have a degree of connectivity to said other domains higher than a connectivity threshold; and

flagging the identified domains as suspicious domains, wherein processing the proxy logs includes;

deciding whether to normalize domain names;

in the event it is decided to normalize domain names, normalizing domain names so that all domain names are at a same level;

deciding whether to filter domain names using a whitelist;

in the event it is decided to filter domain names, filtering out whitelisted domains using the whitelist;

filtering out invalid domain names;

performing user-specific sessionization using a specified time window to create a plurality of buckets;

calculating a support value and a confidence value for each possible domain pair from the overall plurality of buckets in the full dataset; and

creating an edge in the graph between those domain pairs that have a support value that is less than a support threshold and a confidence value that is greater than a confidence threshold.

7. The method recited in claim 6, wherein processing the proxy logs includes:

for each domain in the graph, determining an OddBall ratio for that domain;

comparing each of the determined OddBall ratios against the connectivity threshold; and

identifying those domains with an OddBall ratio greater than the connectivity threshold as being highly connected.

8. The method recited in claim 6, wherein identifying the domains includes:

for each domain in the graph, determining a clique percentage for that domain;

comparing each of the determined clique percentages against the connectivity threshold; and

selecting those domains with a clique percentage greater than the connectivity threshold.

9. The method recited in claim 6, wherein identifying the domains includes:

identifying one or more connected components in the graph, wherein each of the connected components has a size; and

comparing each of the sizes of the connected components against a size threshold; and

selecting those connected components with a size smaller than the size threshold.

10. The method recited in claim 6, wherein the method is performed by a parallel database.

11. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

processing one or more proxy logs in order to generate a graph of domains, wherein those domain pairs in the graph that are connected have in that the number of times the domain pairs are visited is lower than a predetermined support threshold and high confidence in that users accessing the domain pairs are redirected to another domain a greater number of times than a predetermined confidence threshold;

identifying one or more domains within the graph that are highly connected to other domains in the graph in that the one or more domains have a degree of connectivity to said other domains higher than a connectivity threshold; and

flagging the identified domains as suspicious domains, wherein processing the proxy logs includes;

deciding whether to normalize domain names;

in the event it is decided to normalize domain names, normalizing domain names so that all domain names are at a same level;

deciding whether to filter domain names using a whitelist;

in the event it is decided to filter domain names, filtering out whitelisted domains using the whitelist;

filtering out invalid domain names;

performing user-specific sessionization using a specified time window to create a plurality of buckets;

calculating a support value and a confidence value for each possible domain pair from the overall plurality of buckets in the full dataset; and

creating an edge in the graph between those domain pairs that have a support value that is less than a support threshold and a confidence value that is greater than a confidence threshold.

12. The computer program product recited in claim 11, wherein processing the proxy logs includes:

for each domain in the graph, determining an OddBall ratio for that domain;

comparing each of the determined OddBall ratios against the connectivity threshold; and

identifying those domains with an OddBall ratio greater than the connectivity threshold as being highly connected.

13. The computer program product recited in claim 11, wherein identifying the domains includes:

for each domain in the graph, determining a clique percentage for that domain;

comparing each of the determined clique percentages against the connectivity threshold; and

selecting those domains with a clique percentage greater than the connectivity threshold.

14. The computer program product recited in claim 11, wherein identifying the domains includes:

identifying one or more connected components in the graph, wherein each of the connected components has a size; and

comparing each of the sizes of the connected components against a size threshold; and

selecting those connected components with a size smaller than the size threshold.