Graph-based method to detect malware command-and-control infrastructure

• US 9,195,826 B1
• Filed: 05/30/2013
• Issued: 11/24/2015
• Est. Priority Date: 05/30/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Fang, ChunSheng, Lin, Derek, Zadeh, Joseph A.
• Primary Examiner(s): Cervetti, David Garcia
• Application Number:
  US13/906,200
• Time in Patent Office: 908 Days
• Field of Search: 726/23
• US Class Current: 1/1
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: H04L 2463/144 Detection or countermeasures against botnets
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

Potentially infected internal device(s) and potential malware command and control device(s) are identified by generating a bipartite graph that includes internal device(s) inside a network and destination(s) outside the network which communicate over a period of time. The bipartite graph is reduced to obtain a reduced bipartite graph, including by eliminating those connections that include a whitelisted internal device and those connections that include a whitelisted destination. From the reduced graph, a cluster of potentially infected internal device(s) and potential malware command and control device(s) are identified based at least in part on (1) the cluster'"'"'s degree of isolation from other clusters and (2) an isolation threshold.

Claims

1. A method for identifying one or more potentially infected internal devices and one or more potential malware command and control devices, comprising:

generating a bipartite graph that includes one or more internal devices inside a protected network and one or more destinations outside the protected network which communicate over a period of time, including by receiving communication information that includes;

(1) one or more internal devices, (2) one or more destinations that those internal devices communicated with, and (3) one or more times at which those internal devices communicated with those destinations;

reducing the bipartite graph to obtain a reduced bipartite graph, including by;

eliminating any communication information associated with times outside of the period of time; and

eliminating those connections that include a whitelisted internal device inside the protected network and those connections that include a whitelisted destination outside the protected network;

determining a degree of isolation representative of a degree to which a cluster, within the reduced bipartite graph and which includes one or more internal devices and one or more destinations, is isolated from one or more other clusters based at least in part on a number of connections between the cluster and said other clusters; and

using a processor to identify the cluster as being a potentially infected cluster of one or more potentially infected internal devices inside the protected network and one or more potential malware command and control devices outside the protected network in the event the cluster'"'"'s degree of isolation from other clusters exceeds an isolation threshold.

2. The method of claim 1 further comprising receiving, from an Internet reputation system, reputation information for one or more destinations.

3. The method of claim 1, wherein identifying is further based at least in part on:

(1) the cluster'"'"'s degree of internal connectivity and (2) an internal connectivity threshold.

4. The method of claim 1, wherein generating the bipartite graph further includes obtaining structured data and unstructured data from a log aggregator.

5. The method of claim 4, wherein the log aggregator includes one or more of the following:

a security information management (SIM) device, a security information and event management (SIEM) device, or a security event manager (SEM).

6. The method of claim 4, wherein the information obtained from the log aggregator includes information associated with one or more of the following:

a firewall, a proxy server, or a dynamic host configuration protocol (DHCP) server.

7. The method of claim 4, wherein reducing the bipartite graph to obtain the reduced bipartite graph further includes eliminating all fields of information other than internal device and destination.

8. The method of claim 7, wherein:

generating the bipartite graph further includes;

loading the structured data from the log aggregator onto a massively parallel processing (MPP) system; and

loading the unstructured data from the log aggregator onto a Hadoop system; and

reducing the bipartite graph to obtain the reduced bipartite graph further includes;

eliminating at least some of the structured data using the MPP system; and

eliminating at least some of the unstructured data using the Hadoop system.

9. A computer program product for identifying one or more potentially infected internal devices and one or more potential malware command and control devices, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

generating a bipartite graph that includes one or more internal devices inside a protected network and one or more destinations outside the protected network which communicate over a period of time, including by receiving communication information that includes;

(1) one or more internal devices, (2) one or more destinations that those internal devices communicated with, and (3) one or more times at which those internal devices communicated with those destinations;

reducing the bipartite graph to obtain a reduced bipartite graph, including by;

eliminating any communication information associated with times outside of the period of time; and

eliminating those connections that include a whitelisted internal device inside the protected network and those connections that include a whitelisted destination outside the protected network;

determining a degree of isolation representative of a degree to which a cluster, within the reduced bipartite graph and which includes one or more internal devices and one or more destinations, is isolated from one or more other clusters based at least in part on a number of connections between the cluster and said other clusters; and

identifying the cluster as being a potentially infected cluster of one or more potentially infected internal devices inside the protected network and one or more potential malware command and control devices outside the protected network in the event the cluster'"'"'s degree of isolation from other clusters exceeds an isolation threshold.

10. The computer program product of claim 9, wherein identifying is further based at least in part on:

(1) the cluster'"'"'s degree of internal connectivity and (2) an internal connectivity threshold.

11. The computer program product of claim 9, wherein the computer instructions for generating the bipartite graph further include computer instructions for obtaining structured data and unstructured data from a log aggregator.

12. The computer program product of claim 11, wherein the computer instructions for reducing the bipartite graph to obtain the reduced bipartite graph further include computer instructions for eliminating all fields of information other than internal device and destination.

13. The computer program product of claim 12, wherein:

the computer instructions for generating the bipartite graph further include computer instructions for;

loading the structured data from the log aggregator onto a massively parallel processing (MPP) system; and

loading the unstructured data from the log aggregator onto a Hadoop system; and

the computer instructions for reducing the bipartite graph to obtain the reduced bipartite graph further include computer instructions for;

eliminating at least some of the structured data using the MPP system; and

eliminating at least some of the unstructured data using the Hadoop system.

14. A system for identifying one or more potentially infected internal devices and one or more potential malware command and control devices, 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;

generate a bipartite graph that includes one or more internal devices inside a protected network and one or more destinations outside the protected network which communicate over a period of time, including by receiving communication information that includes;

(1) one or more internal devices, (2) one or more destinations that those internal devices communicated with, and (3) one or more times at which those internal devices communicated with those destinations;

reduce the bipartite graph to obtain a reduced bipartite graph, including by;

eliminating any communication information associated with times outside of the period of time; and

eliminating those connections that include a whitelisted internal device inside the protected network and those connections that include a whitelisted destination outside the protected network;

determine a degree of isolation representative of a degree to which a cluster, within the reduced bipartite graph and which includes one or more internal devices and one or more destinations, is isolated from one or more other clusters based at least in part on a number of connections between the cluster and said other clusters; and

identify the cluster as being a potentially infected cluster of one or more potentially infected internal devices inside the protected network and one or more potential malware command and control devices outside the protected network in the event the cluster'"'"'s degree of isolation from other clusters exceeds an isolation threshold.

15. The system of claim 14, wherein the memory is further configured to provide the processor with instructions which when executed cause the processor to receive, from an Internet reputation system, reputation information for one or more destinations.

16. The system of claim 14, wherein generating the bipartite graph further includes obtaining structured data and unstructured data from a log aggregator.

17. The system of claim 16, wherein the log aggregator includes one or more of the following:

a security information management (SIM) device, a security information and event management (SIEM) device, or a security event manager (SEM).

18. The system of claim 16, wherein the information obtained from the log aggregator includes information associated with one or more of the following:

a firewall, a proxy server, or a dynamic host configuration protocol (DHCP) server.

19. The system of claim 16, wherein reducing the bipartite graph to obtain the reduced bipartite graph further includes eliminating all fields of information other than internal device and destination.

20. The system of claim 19, wherein:

generating the bipartite graph further includes;

loading the structured data from the log aggregator onto a massively parallel processing (MPP) system; and

loading the unstructured data from the log aggregator onto a Hadoop system; and

reducing the bipartite graph to obtain the reduced bipartite graph further includes;

eliminating at least some of the structured data using the MPP system; and

eliminating at least some of the unstructured data using the Hadoop system.