Machine learning based botnet detection using real-time connectivity graph based traffic features

• US 8,762,298 B1
• Filed: 01/05/2011
• Issued: 06/24/2014
• Est. Priority Date: 01/05/2011
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: Narus, Inc. (Gen Digital Inc.)
• Inventors: Ranjan, Supranamaya, Robinson, Joshua, Chen, Feilong
• Primary Examiner(s): Chen, Alan
• Assistant Examiner(s): Chubb, Mikayla
• Application Number:
  US12/985,263
• Time in Patent Office: 1,266 Days
• US Class Current: 706/12
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: H04L 2463/144 Detection or countermeasures against botnets
• CPC Class Codes: H04L 63/14 for detecting or protecting against malicious traffic

Abstract

A method for identifying a botnet in a network, including analyzing historical network data using a pre-determined heuristic to determine values of a connectivity graph based feature in the historical network data, obtaining a ground truth data set having labels assigned to data units in the historical network data identifying known malicious nodes in the network, analyzing the historical network data and the ground truth data set using a machine learning algorithm to generate a model representing the labels as a function of the values of the connectivity graph based feature, analyzing real-time network data using the pre-determined heuristic to determine a value of the connectivity graph based feature for a data unit in the real-time network data, assigning a label to the data unit by applying the model to the value of the connectivity graph based feature, and categorizing the data unit as associated with the botnet based on the label.

Claims

1. A method for identifying a botnet in a network, comprising:

obtaining historical network data in the network, the historical network data comprising a first plurality of data units;

analyzing, by a central processing unit (CPU) of a computer and using a pre-determined heuristic, the historical network data to determine a plurality of values of a connectivity graph based feature for the first plurality of data units, wherein a first value of the connectivity graph based feature for a first data unit of the first plurality of data units is determined based on and representing connectivity characteristics of at least a portion of the historical network data associated with the first data unit;

obtaining a ground truth data set associated with the historical network data, the ground truth data set comprising a plurality of labels with each label assigned to a corresponding data unit of the first plurality of data units, said each label comprising one of a first label categorizing said corresponding data unit as associated with the botnet and a second label categorizing said corresponding data unit as not associated with the botnet;

analyzing, by the CPU and using a machine learning algorithm, the historical network data and the ground truth data set to generate a model comprising statistical predictions of the plurality of labels as a function of the plurality of values of the connectivity graph based feature with respect to the first plurality of data units;

obtaining real-time network data in the network, the real-time network data comprising a second plurality of data units;

analyzing, by the CPU and using the pre-determined heuristic, the real-time network data to determine a second value of the connectivity graph based feature for a second data unit of the second plurality of data units, wherein the second value is determined based on and representing connectivity characteristics of at least a portion of the real-time network data associated with the second data unit;

assigning a third label to the second data unit by applying the model to the second value of the connectivity graph based feature; and

categorizing the second data unit as associated with the botnet based on the third label,

wherein the first plurality of data units comprise a plurality of IP (Internet Protocol) addresses,

wherein analyzing the historical network data using the pre-determined heuristic comprises;

constructing a graph comprising nodes representing the plurality of IP addresses and edges each representing communication within the historical network data between two of the plurality of IP addresses;

analyzing the graph to determine at least a portion of the plurality of values of the connectivity graph based feature corresponding to the plurality of IP addresses;

identifying botnet nodes among the nodes according to the ground truth data set; and

determining an anti-trust rank that is calculated using a page rank algorithm and at least one edge weight assigned to at least one of the edges, wherein the at least one edge weight is determined based on whether the at least one of the edges is related to any of the botnet nodes, and

wherein the connectivity graph based feature represents connectivity characteristics associated with the nodes and comprises the anti-trust rank.

2. The method of claim 1,

wherein the graph is time dependent and comprises a first graph corresponding to a first version of the historical network data within a first time window and a second graph corresponding to a second version of the historical network data within a second time window,

wherein analyzing the graph comprises:

representing the first and second graphs as first and second matrices; and

generating a time averaged matrix from the first and second matrices based on a pre-determined statistical formula,

wherein said at least a portion of the plurality of values of the connectivity graph based feature are determined for the plurality of IP addresses based on the time averaged matrix.

3. The method of claim 2, wherein the pre-determined statistical formula comprises at least one selected from a group consisting of moving average, auto regressive model, and exponentially weighted moving average (EWMA).

4. The method of claim 1,

wherein the first plurality of data units comprise a plurality of client IP (Internet Protocol) addresses and a plurality of domain names, and

wherein analyzing the historical network data using the pre-determined heuristic comprises:

constructing a graph comprising client nodes representing the plurality of IP addresses, server nodes representing the plurality of domain names, and edges each representing communication within the historical network data between a client node and a server node; and

analyzing the graph to determine at least a portion of the plurality of values of the connectivity graph based feature corresponding to the first plurality of data units.

5. The method of claim 1, wherein the machine learning algorithm comprises at least one selected from a group consisting of Bayesian network, Multi-layer perceptron, Decision tree, Alternating Decision Tree, and Naives Bayes Tree.

6. A system for identifying a botnet in a network, comprising:

a processor; and

memory storing instructions, when executed by the processor, comprising functionalities for;

obtaining historical network data in the network, the historical network data comprising a first plurality of data units;

analyzing, using a pre-determined heuristic, the historical network data to determine a plurality of values of a connectivity graph based feature for the first plurality of data units, wherein a first value of the connectivity graph based feature for a first data unit of the first plurality of data units is determined based on and representing connectivity characteristics of at least a portion of the historical network data associated with the first data unit;

obtaining a ground truth data set associated with the historical network data, the ground truth data set comprising a plurality of labels with each label assigned to a corresponding data unit of the first plurality of data units, said each label comprising one of a first label categorizing said corresponding data unit as associated with the botnet and a second label categorizing said corresponding data unit as being not associated with the botnet;

analyzing, using a machine learning algorithm, the historical network data and the ground truth data set to generate a model comprising statistical predictions of the plurality of labels as a function of the plurality of values of the connectivity graph based feature with respect to the first plurality of data units;

obtaining real-time network data in the network, the real-time network data comprising a second plurality of data units;

analyzing, using the pre-determined heuristic, the real-time network data to determine a second value of the connectivity graph based feature for a second data unit of the second plurality of data units, wherein the second value is determined based on and representing connectivity characteristics of at least a portion of the real-time network data associated with the second data unit;

assigning a third label to the second data unit by applying the model to the second value of the connectivity graph based feature; and

categorizing the second data unit as associated with the botnet based on the third label,

wherein the first plurality of data units comprise a plurality of IP (Internet Protocol) addresses,

wherein analyzing the historical network data using the pre-determined heuristic comprises;

constructing a graph comprising nodes representing the plurality of IP addresses and edges each representing communication within the historical network data between two of the plurality of IP addresses;

analyzing the graph to determine at least a portion of the plurality of values of the connectivity graph based feature corresponding to the plurality of IP addresses;

identifying botnet nodes among the nodes according to the ground truth data set; and

determining an anti-trust rank that is calculated using a page rank algorithm and at least one edge weight assigned to at least one of the edges, wherein the at least one edge weight is determined based on whether the at least one of the edges is related to any of the botnet nodes, and

wherein the connectivity graph based feature represents connectivity characteristics associated with the nodes and comprises the anti-trust rank.

7. The system of claim 6,

wherein the graph is time dependent and comprises a first graph corresponding to a first version of the historical network data within a first time window and a second graph corresponding to a second version of the historical network data within a second time window,

wherein analyzing the graph comprises:

representing the first and second graphs as first and second matrices; and

generating a time averaged matrix from the first and second matrices based on a pre-determined statistical formula,

wherein said at least a portion of the plurality of values of the connectivity graph based feature are determined for the plurality of IP addresses based on the time averaged matrix.

8. The system of claim 7, wherein the pre-determined statistical formula comprises at least one selected from a group consisting of moving average, auto regressive model, and exponentially weighted moving average (EWMA).

9. The system of claim 6,

wherein the first plurality of data units comprise a plurality of client IP (Internet Protocol) addresses and a plurality of domain names, and

wherein analyzing the historical network data using the pre-determined heuristic comprises:

constructing a graph comprising client nodes representing the plurality of IP addresses, server nodes representing the plurality of domain names, and edges each representing communication within the historical network data between a client node and a server node; and

analyzing the graph to determine at least a portion of the plurality of values of the connectivity graph based feature corresponding to the first plurality of data units.

10. The system of claim 6, wherein the machine learning algorithm comprises at least one selected from a group consisting of Bayesian network, Multi-layer perceptron, Decision tree, Alternating Decision Tree, and Naives Bayes Tree.

11. A non-transitory computer readable medium storing instructions for identifying a botnet in a network, the instructions, when executed by a processor of a computer, comprising functionality for:

obtaining historical network data in the network, the historical network data comprising a first plurality of data units;

analyzing, using a pre-determined heuristic, the historical network data to determine a plurality of values of a connectivity graph based feature for the first plurality of data units, wherein a first value of the connectivity graph based feature for a first data unit of the first plurality of data units is determined based on and representing connectivity characteristics of at least a portion of the historical network data associated with the first data unit;

obtaining a ground truth data set associated with the historical network data, the ground truth data set comprising a plurality of labels with each label assigned to a corresponding data unit of the first plurality of data units, said each label comprising one of a first label categorizing said corresponding data unit as associated with the botnet and a second label categorizing said corresponding data unit as being not associated with the botnet;

analyzing, using a machine learning algorithm, the historical network data and the ground truth data set to generate a model comprising statistical predictions of the plurality of labels as a function of the plurality of values of the connectivity graph based feature with respect to the first plurality of data units;

obtaining real-time network data in the network, the real-time network data comprising a second plurality of data units;

analyzing, using the pre-determined heuristic, the real-time network data to determine a second value of the connectivity graph based feature for a second data unit of the second plurality of data units, wherein the second value is determined based on and representing connectivity characteristics of at least a portion of the real-time network data associated with the second data unit;

assigning a third label to the second data unit by applying the model to the second value of the connectivity graph based feature; and

categorizing the second data unit as associated with the botnet based on the third label,

wherein the first plurality of data units comprise a plurality of IP (Internet Protocol) addresses,

wherein analyzing the historical network data using the pre-determined heuristic comprises;

constructing a graph comprising nodes representing the plurality of IP addresses and edges each representing communication within the historical network data between two of the plurality of IP addresses;

analyzing the graph to determine at least a portion of the plurality of values of the connectivity graph based feature corresponding to the plurality of IP addresses;

identifying botnet nodes among the nodes according to the ground truth data set; and

determining an anti-trust rank that is calculated using a page rank algorithm and at least one edge weight assigned to at least one of the edges, wherein the at least one edge weight is determined based on whether the at least one of the edges is related to any of the botnet nodes, and

wherein the connectivity graph based feature represents connectivity characteristics associated with the nodes and comprises the anti-trust rank.

12. The non-transitory computer readable medium of claim 11,

wherein the graph is time dependent and comprises a first graph corresponding to a first version of the historical network data within a first time window and a second graph corresponding to a second version of the historical network data within a second time window,

wherein analyzing the graph comprises:

representing the first and second graphs as first and second matrices; and

generating a time averaged matrix from the first and second matrices based on a pre-determined statistical formula,

wherein said at least a portion of the plurality of values of the connectivity graph based feature are determined for the plurality of IP addresses based on the time averaged matrix.

13. The non-transitory computer readable medium of claim 12, wherein the pre-determined statistical formula comprises at least one selected from a group consisting of moving average, auto regressive model, and exponentially weighted moving average (EWMA).

14. The non-transitory computer readable medium of claim 11,

wherein the first plurality of data units comprise a plurality of client IP (Internet Protocol) addresses and a plurality of domain names, and

wherein analyzing the historical network data using the pre-determined heuristic comprises:

constructing a graph comprising client nodes representing the plurality of IP addresses, server nodes representing the plurality of domain names, and edges each representing communication within the historical network data between a client node and a server node; and

analyzing the graph to determine at least a portion of the plurality of values of the connectivity graph based feature corresponding to the first plurality of data units.

15. The non-transitory computer readable medium of claim 11, wherein the machine learning algorithm comprises at least one selected from a group consisting of Bayesian network, Multi-layer perceptron, Decision tree, Alternating Decision Tree, and Naives Bayes Tree.