Joint anomaly detection across IOT devices

• US 10,193,913 B2
• Filed: 08/04/2016
• Issued: 01/29/2019
• Est. Priority Date: 08/04/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Machlica, Lukas, Sofka, Michal
• Primary Examiner(s): Smithers, Matthew
• Application Number:
  US15/228,980
• Publication Number:
  US 20180041528A1
• Time in Patent Office: 908 Days
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks

Abstract

Systems and methods of the present disclosure provide technology to identify when network-connected devices are likely infected with malware. Network communications are be monitored during a specific time window and a graph is created for a conditional random field (CRF) model. Vertices of the graph represent devices connected to the network and an edge between two vertices indicates that one or more network communications occurred between two devices represented by the two vertices during the time window. Network devices can report observations about network behavior during the time window and the observations can be used as input for the CRF model. The CRF model can then be used to determine infection-status values for the network devices.

Claims

1. A method, comprising:

monitoring, at a gateway device, network communications between a plurality of computing devices connected to a network associated with the gateway device;

creating, at the gateway device, a graph, wherein each vertex of the graph represents one of the computing devices connected to the network and each edge of the graph represents network communication that has occurred between the computing devices connected by that edge during a time window;

receiving, from each of the computing devices, a collection of one or more performance metrics observed by that computing device during the time window;

determining, based on the graph and the collections of one or more performance metrics, a respective measure of risk for each of the computing devices for the time window;

determining, from the graph, a clique of computing devices that are linked by edges in the graph;

adjusting the respective measure of risk for the time window for one of the computing devices in the clique based on the measures of risk for the remaining computing devices in the clique; and

in response to determining that a given computing device in the clique is infected with malware based on the respective measure of risk exceeding a threshold, setting an alert flag at the gateway device indicating that the given computing device is infected.

2. The method of claim 1, further comprising:

creating a conditional probability function of measures of risk based on a conditional random field (CRF) model, wherein the conditional probability function is defined using a plurality of feature functions that are associated with a plurality of weights; and

determining, at the gateway device, the respective measures of risk based on the conditional probability function, the graph, and the collections of one or more performance metrics received from each of the computing devices.

3. The method of claim 2, further comprising:

determining an anomaly-suspicion value for at least a first computing device using a first classifier, wherein the first classifier uses a collection of one or more performance metrics observed by the first computing device as input.

4. The method of claim 3, wherein at least one feature function of the plurality of feature functions uses the anomaly-suspicion value as an input to determine an output value associated the first computing device.

5. The method of claim 3, further comprising:

determining a difference between the respective measure of risk for the first computing device and the anomaly-suspicion value for the first computing device exceeds a predefined threshold; and

tuning the first classifier to predict the respective measure of risk for the first device when given an observation vector.

6. The method of claim 2, further comprising:

receiving training data for the CRF model; and

determining the plurality of weights by training the CRF model using the training data.

7. The method of claim 1, further comprising:

calculating a sum of the respective measures of risk for the computing devices;

determining that the sum of the respective measures of risk exceeds a predefined threshold value; and

triggering an alert based on the determination.

8. A system comprising:

one or more processors; and

a memory storing one or more applications that, when executed on the one or more processors, perform an operation, the operation comprising;

monitoring, at a gateway device, network communications between a plurality of computing devices connected to a network associated with the gateway device,

creating, at the gateway device, a graph, wherein each vertex of the graph represents one of the computing devices connected to the network and each edge of the graph represents network communication that has occurred during a time window between the computing devices connected by that edge,

receiving, from each of the computing devices, a collection of one or more performance metrics observed by that computing device during the time window,

determining, based on the graph and the collections of one or more performance metrics, a respective measure of risk for each of the computing devices for the time window;

determining, from the graph, a clique of computing devices that are linked by edges in the graph;

adjusting the respective measure of risk for the time window for one of the computing devices in the clique based on the measures of risk for remaining computing devices in the clique; and

in response to determining that a given computing device in the clique is infected with malware based on the respective measure of risk exceeding a threshold, setting an alert flag at the gateway device that the given computing device is infected.

9. The system of claim 8, wherein the operation further comprises:

creating a conditional probability function of measures of risk based on a conditional random field (CRF) model, wherein the conditional probability function is defined using a plurality of feature functions that are associated with a plurality of weights; and

determining, at the gateway device, the respective measures of risk based on the conditional probability function, the graph, and the collections of one or more performance metrics received from each of the computing devices.

10. The system of claim 9, wherein the operation further comprises:

determining an anomaly-suspicion value for at least a first computing device using a first classifier, wherein the first classifier uses a collection of one or more performance metrics observed by the first computing device as input.

11. The system of claim 10, wherein at least one feature function of the plurality of feature functions uses the anomaly-suspicion value as an input to determine an output value associated the first computing device.

12. The system of claim 10, wherein the operation further comprises:

determining a difference between the respective measure of risk for the first computing device and the anomaly-suspicion value for the first computing device exceeds a predefined threshold; and

tuning the first classifier to predict the respective measure of risk for the first device when given an observation vector.

13. The system of claim 9, wherein the operation further comprises:

receiving training data for the CRF model; and

determining the plurality of weights by training the CRF model using the training data.

14. The system of claim 8, wherein the operation further comprises:

calculating a sum of the respective measures of risk for the computing devices;

determining that the sum of the respective measures of risk exceeds a predefined threshold value; and

triggering an alert based on the determination.

15. One or more non-transitory computer readable storage media encoded with software comprising computer executable instructions and when the software is executed is operable to:

monitor, at a gateway device, network communications between a plurality of computing devices connected to a network associated with the gateway device;

create, at the gateway device, a graph, wherein each vertex of the graph represents one of the computing devices connected to the network and each edge of the graph represents network communication that has occurred during a time window between the computing devices connected by that edge;

receive, from each of the computing devices, a collection of one or more performance metrics observed by that computing device during the time window;

determine, based on the graph and the collections of one or more performance metrics, a respective measure of risk for each of the computing devices for the time window;

determine, from the graph, a clique of computing devices that are linked by edges in the graph;

adjust the respective measure of risk for the time window for one computing device in the clique based on measures of risk for remaining computing devices in the clique; and

in response to determining that a given computing device of the clique is infected with malware based on the respective measure of risk exceeding a threshold, set an alert flag at the gateway device that the given computing device is infected.

16. The one or more non-transitory computer readable storage media of claim 15, wherein the software, when executed, is further operable to:

create a conditional probability function of measures of risk based on a conditional random field (CRF) model, wherein the conditional probability function is defined using a plurality of feature functions that are associated with a plurality of weights; and

determine, at the gateway device, the respective measures of risk based on the conditional probability function, the graph, and the collections of one or more performance metrics received from each of the computing devices.

17. The one or more non-transitory computer readable storage media of claim 16, wherein the software, when executed, is further operable to:

determine an anomaly-suspicion value for at least a first computing device using a first classifier, wherein the first classifier uses a collection of one or more performance metrics observed by the first computing device as input.

18. The one or more non-transitory computer readable storage media of claim 17, wherein at least one feature function of the plurality of feature functions uses the anomaly-suspicion value as an input to determine an output value associated the first computing device.

19. The one or more non-transitory computer readable storage media of claim 17, wherein the software, when executed, is further operable to:

determine a difference between the respective measure of risk for the first computing device and the anomaly-suspicion value for the first computing device exceeds a predefined threshold; and

tune the first classifier to predict the respective measure of risk for the first device when given an observation vector.

20. The one or more non-transitory computer readable storage media of claim 16, wherein the software, when executed, is further operable to:

receive training data for the CRF model; and

determine the plurality of weights by training the CRF model using the training data.

21. The one or more non-transitory computer readable storage media of claim 15, wherein the software, when executed, is further operable to:

calculate a sum of the respective measures of risk for the computing devices;

determine that the sum of the respective measures of risk exceeds a predefined threshold value; and

trigger an alert based on the determination.