Detecting malicious endpoints using network connectivity and flow information

• US 8,813,236 B1
• Filed: 01/07/2013
• Issued: 08/19/2014
• Est. Priority Date: 01/07/2013
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: Narus, Inc. (Gen Digital Inc.)
• Inventors: Saha, Sabyasachi, Liu, Lei, Torres, Ruben, Nucci, Antonio, Xu, Jianpeng
• Primary Examiner(s): PERUNGAVOOR, VENKATANARAY
• Application Number:
  US13/735,196
• Time in Patent Office: 589 Days
• US Class Current: 726/25
• CPC Class Codes: H04L 2463/146 Tracing the source of attacks
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

A method for detecting hidden malicious network nodes. Starting from a pool of seed nodes that have previously been identified as malicious, a two-phase score propagation algorithm is employed to propagate threat scores from the seeded nodes to other nodes in an IP-address connectivity graph. Nodes with high threat score after propagation are declared to be malicious.

Claims

1. A method for detecting a malicious endpoint in a network, comprising:

obtaining, from the network, flows among a plurality of endpoints of the network, wherein the plurality of endpoints comprise servers and clients;

assigning, to each of the plurality of endpoints, a pre-identified endpoint threat level specific to each of the plurality of endpoints;

assigning, to each of the flows, a pre-identified flow threat level specific to each of the flows;

calculating, by a computer processor, for a server and a client in the plurality of endpoints, and based on the pre-identified flow threat level assigned to a flow between the server and the client, a server-to-client (SC) score propagation parameter and a client-to-server (CS) propagation parameter,

performing, by the computer processor, iterative score propagation based on a sequence of iterations, comprising;

initializing, prior to the sequence of iterations, a client score of the client and a server score of the server according to the pre-identified endpoint threat levels assigned to the client and the server, respectively;

updating, in a first iteration in the sequence of iterations, the client score of the client by a SC adjustment amount determined at least based on the server score of the server and the SC score propagation parameter;

updating, in a second iteration adjacent to the first iteration in the sequence of iterations, the server score of the server by a CS adjustment amount determined at least based on the client score of the client and the CS score propagation parameter; and

generating, in response to at least updating the client score and the server score in the first iteration and the second iteration, respectively, the final scores of the plurality of endpoints based on at least the client score and the server score; and

detecting an endpoint of the plurality of endpoints as malicious in response to a corresponding one of the final scores exceeding a pre-determined threshold, wherein the endpoint is not identified as malicious based on the pre-identified endpoint threat level assigned to the endpoint.

2. The method of claim 1, further comprising:

identifying, using an intrusion detection system (IDS), a binary malicious status of each of the plurality of endpoints, wherein the pre-identified endpoint threat level of the at least one endpoint is set according to at least the binary malicious status; and

determining, using a flow-based classifier, the pre-identified flow threat level of each of the flows, wherein the pre-identified flow threat level represents a continuous-valued probability of each of the flows to be malicious.

3. The method of claim 1,

wherein the SC score propagation parameter is normalized with respect to all pre-identified flow threat levels associated with the client, and

wherein the CS score propagation parameter is normalized with respect to all pre-identified flow threat levels associated with the server.

4. The method of claim 1, further comprising:

generating a bipartite graph to represent the plurality of endpoints and the flows among the plurality of endpoints, wherein the bipartite graph comprises server nodes, client nodes, and server/client links linking the server nodes and the client nodes according to the flows; and

generating a normalized transition matrix representing the server/client links of the bipartite graph, wherein transitions in the normalized transition matrix are weighted based on corresponding pre-identified flow threat levels of the server/client links,

wherein calculating, for the server and the client, the SC score propagation parameter and the CS score propagation parameter comprises computing a matrix element of the normalized transition matrix in SC direction and CS direction, respectively, and

wherein the matrix element corresponds to one of the server/client links linking a server node of the server and a client node of the client.

5. The method of claim 4, further comprising:

determining the SC adjustment amount by a first matrix multiplication between a server score vector and the transition matrix in SC direction, wherein the server score vector comprises all server scores of all servers in the plurality of endpoints; and

determining the CS adjustment amount by a second matrix multiplication between a client score vector and the transition matrix in CS direction, wherein the client score vector comprises all client scores of all clients in the plurality of endpoints.

6. The method of claim 1, wherein performing the iterative score propagation further comprises:

updating the client score and the server score in at least a third iteration and a fourth iteration, respectively,

wherein the final scores are generated further in response to at least one selected from a group consisting of the SC adjustment amount and CS adjustment amount being less than a convergence threshold.

7. The method of claim 1, further comprising:

generating, in response to the detecting, an alert indicating the endpoint as malicious; and

initiating, in response to the detecting, a security operation with respect to the endpoint.

8. A system for detecting a malicious endpoint in a network, comprising:

a computer processor;

a flow parser configured to obtain, from the network, flows among a plurality of endpoints of the network, wherein each of the plurality of endpoints is assigned a pre-identified endpoint threat level specific to each of the plurality of endpoints, wherein each of the flows is assigned a pre-identified flow threat level specific to each of the flows, wherein the plurality of endpoints comprise servers and clients;

a connectivity analyzer executing on the computer processor and configured to;

calculate, for a server and a client in the plurality of endpoints, and based on the pre-identified flow threat level assigned to a flow between the server and the client, a server-to-client (SC) score propagation parameter and a client-to-server (CS) propagation parameter;

an iterative score calculator executing on the computer processor and configured to perform iterative score propagation based on a sequence of iterations, comprising;

initializing, prior to the sequence of iterations, a client score of the client and a server score of the server according to the pre-identified endpoint threat levels assigned to the client and the server, respectively;

updating, in a first iteration in the sequence of iterations, the client score of the client by a SC adjustment amount determined at least based on the server score of the server and the SC score propagation parameter;

updating, in a second iteration adjacent to the first iteration in the sequence of iterations, the server score of the server by a CS adjustment amount determined at least based on the client score of the client and the CS score propagation parameter; and

generating, in response to at least updating the client score and the server score in the first iteration and the second iteration, respectively, the final scores of the plurality of endpoints based on at least the client score and the server score; and

a malicious endpoint detector executing on the computer processor and configured to detect an endpoint of the plurality of endpoints as malicious in response to a corresponding one of the final scores exceeding a pre-determined threshold, wherein the endpoint is not identified as malicious based on the pre-identified endpoint threat level assigned to the endpoint; and

a repository configured to store the pre-identified endpoint threat level, the pre-identified flow threat level, the SC score propagation parameter, the CS score propagation parameter, the server score, the client score, and the final scores.

9. The system of claim 8, further comprising:

an intrusion detection system (IDS) configured to determine, a binary malicious status of each of the plurality of endpoints, wherein the pre-identified endpoint threat level of the at least one endpoint is set according to at least the binary malicious status; and

a flow-based classifier configured to determine the pre-identified flow threat level of each of the flows, wherein the pre-identified flow threat level represents a continuous-valued probability of each of the flows to be malicious.

10. The system of claim 8,

wherein the SC score propagation parameter is normalized with respect to all pre-identified flow threat levels associated with the client, and

wherein the CS score propagation parameter is normalized with respect to all pre-identified flow threat levels associated with the server.

11. The system of claim 8, the connectivity analyzer further configured to:

generate a bipartite graph to represent the plurality of endpoints and the flows among the plurality of endpoints, wherein the bipartite graph comprises server nodes, client nodes, and server/client links linking the server nodes and the client nodes according to the flows; and

generate a normalized transition matrix representing the server/client links of the bipartite graph, wherein transitions in the normalized transition matrix are weighted based on corresponding pre-identified flow threat levels of the server/client links,

wherein calculating, for the server and the client, the SC score propagation parameter and the CS score propagation parameter comprises computing a matrix element of the normalized transition matrix in SC direction and CS direction, respectively, and

wherein the matrix element corresponds to one of the server/client links linking a server node of the server and a client node of the client.

12. The system of claim 11, the iterative score calculator further configured to:

determine the SC adjustment amount by a first matrix multiplication between a server score vector and the transition matrix in SC direction, wherein the server score vector comprises all server scores of all servers in the plurality of endpoints; and

determine the CS adjustment amount by a second matrix multiplication between a client score vector and the transition matrix in CS direction, wherein the client score vector comprises all client scores of all clients in the plurality of endpoints.

13. The system of claim 8, wherein performing the iterative score propagation further comprises:

updating the client score and the server score in at least a third iteration and a fourth iteration, respectively,

wherein the final scores are generated further in response to at least one selected from a group consisting of the SC adjustment amount and CS adjustment amount being less than a convergence threshold.

14. The system of claim 8, the malicious endpoint detector further configured to:

generate, in response to the detecting, an alert indicating the endpoint as malicious; and

initiate, in response to the detecting, a security operation with respect to the endpoint.

15. A non-transitory computer readable medium embodying instructions for profiling network traffic of a network, the instructions when executed by a processor comprising functionality for:

obtaining, from the network, flows among a plurality of endpoints of the network, wherein the plurality of endpoints comprise servers and clients;

assigning, to each of the plurality of endpoints, a pre-identified endpoint threat level specific to each of the plurality of endpoints;

assigning, to each of the flows, a pre-identified flow threat level specific to each of the flows;

calculating, by a computer processor, for a server and a client in the plurality of endpoints, and based on the pre-identified flow threat level assigned to a flow between the server and the client, a server-to-client (SC) score propagation parameter and a client-to-server (CS) propagation parameter,

performing, by the computer processor, iterative score propagation based on a sequence of iterations to generate final scores of the plurality of endpoints, wherein the iterative score propagation comprises;

initializing, prior to the sequence of iterations, a client score of the client and a server score of the server according to the pre-identified endpoint threat levels assigned to the client and the server, respectively;

updating, in a first iteration in the sequence of iterations, the client score of the client by a SC adjustment amount determined at least based on the server score of the server and the SC score propagation parameter;

updating, in a second iteration adjacent to the first iteration in the sequence of iterations, the server score of the server by a CS adjustment amount determined at least based on the client score of the client and the CS score propagation parameter; and

generating, in response to at least updating the client score and the server score in the first iteration and the second iteration, respectively, the final scores of the plurality of endpoints based on at least the client score and the server score; and

detecting an endpoint of the plurality of endpoints as malicious in response to a corresponding one of the final scores exceeding a pre-determined threshold, wherein the endpoint is not identified as malicious based on the pre-identified endpoint threat level assigned to the endpoint.

16. The non-transitory computer readable medium of claim 15, the instructions when executed by a processor further comprising functionality for:

identifying, using an intrusion detection system (IDS), a binary malicious status of each of the plurality of endpoints, wherein the pre-identified endpoint threat level of the at least one endpoint is set according to at least the binary malicious status; and

determining, using a flow-based classifier, the pre-identified flow threat level of each of the flows, wherein the pre-identified flow threat level represents a continuous-valued probability of each of the flows to be malicious.

17. The non-transitory computer readable medium of claim 15,

wherein the SC score propagation parameter is normalized with respect to all pre-identified flow threat levels associated with the client, and

wherein the CS score propagation parameter is normalized with respect to all pre-identified flow threat levels associated with the server.

18. The non-transitory computer readable medium of claim 15, the instructions when executed by a processor further comprising functionality for:

generating a bipartite graph to represent the plurality of endpoints and the flows among the plurality of endpoints, wherein the bipartite graph comprises server nodes, client nodes, and server/client links linking the server nodes and the client nodes according to the flows; and

generating a normalized transition matrix representing the server/client links of the bipartite graph, wherein transitions in the normalized transition matrix are weighted based on corresponding pre-identified flow threat levels of the server/client links,

wherein calculating, for the server and the client, the SC score propagation parameter and the CS score propagation parameter comprises computing a matrix element of the normalized transition matrix in SC direction and CS direction, respectively, and

wherein the matrix element corresponds to one of the server/client links linking a server node of the server and a client node of the client.

19. The non-transitory computer readable medium of claim 18, the instructions when executed by a processor further comprising functionality for:

determining the SC adjustment amount by a first matrix multiplication between a server score vector and the transition matrix in SC direction, wherein the server score vector comprises all server scores of all servers in the plurality of endpoints; and

determining the CS adjustment amount by a second matrix multiplication between a client score vector and the transition matrix in CS direction, wherein the client score vector comprises all client scores of all clients in the plurality of endpoints.

20. The non-transitory computer readable medium of claim 15, the instructions when executed by a processor further comprising functionality for:

generating, in response to the detecting, at least one selected from a group consisting of an alert indicating the endpoint as malicious and a security operation with respect to the endpoint.