Multi-dimensional system anomaly detection

• US 10,333,958 B2
• Filed: 11/14/2016
• Issued: 06/25/2019
• Est. Priority Date: 07/19/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Huang, Xinyuan, Ranjan, Sarvesh, Zhang, Olivia, Udupi, Yathiraj B., Dutta, Debojyoti
• Primary Examiner(s): Siddiqi, Mohammad A
• Application Number:
  US15/350,717
• Publication Number:
  US 20180027004A1
• Time in Patent Office: 953 Days
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04L 63/162 at the data link layer

Abstract

In one embodiment, a device in a network receives a first plurality of measurements for network metrics captured during a first time period. The device determines a first set of correlations between the network metrics using the first plurality of measurements captured during the first time period. The device receives a second plurality of measurements for the network metrics captured during a second time period. The device determines a second set of correlations between the network metrics using the second plurality of measurements captured during the second time period. The device identifies a difference between the first and second sets of correlations between the network metrics as a network anomaly.

Claims

1. A method comprising:

receiving, at a device in a network, a first plurality of measurements for network metrics captured during a first time period;

determining, by the device, a first set of correlations between the network metrics using the first plurality of measurements captured during the first time period;

receiving, at the device, a second plurality of measurements for the network metrics captured during a second time period;

determining, by the device, a second set of correlations between the network metrics using the second plurality of measurements captured during the second time period;

in response to determining the first and second sets of correlations, generating, by the device, a plurality of persistence diagrams based on the first and second sets of correlations as sets, each diagram of the plurality of persistence diagrams a set of topological features associated with the first and second sets of correlations;

computing, by the device, a distance between at least two of the plurality of generated persistence diagrams, wherein the distance represents an anomaly score associated with a change in the topology of the network; and

identifying, by the device, a difference between the first and second sets of correlations between the network metrics as a network anomaly based on the anomaly score.

2. The method as in claim 1, further comprising:

generating, by the device, an alert indicative of the network anomaly.

3. The method as in claim 1, further comprising:

projecting, by the device, the first and second pluralities of measurements onto one or more hyperplanes that each comprise a hash function, to generate measurement signatures; and

using, by the device, the measurement signatures to determine the first and second sets of correlations.

4. The method as in claim 3, wherein the measurement signatures comprises hashes of the projected first and second pluralities of measurements.

5. The method as in claim 1, further comprising:

performing, by the device, spectral analysis on the first and second pluralities of measurements, to determine the first and second sets of correlations.

6. The method as in claim 1, wherein the topological features comprise clusters and holes of one or more manifolds in which measurements from the first or second pluralities of measurements are data points in the one or more manifolds.

7. The method as in claim 1, wherein the network metrics comprise at least one of:

a byte size of a traffic flow, a time associated with a traffic flow, or an available resource of a node in the network.

8. An apparatus, comprising:

one or more network interfaces to communicate with a network;

a processor coupled to the network interfaces and configured to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

receive a first plurality of measurements for network metrics captured during a first time period;

determine a first set of correlations between the network metrics using the first plurality of measurements captured during the first time period;

receive a second plurality of measurements for the network metrics captured during a second time period;

determine a second set of correlations between the network metrics using the second plurality of measurements captured during the second time period;

in response to determining the first and second sets of correlations, generate a plurality of persistence diagrams based on the first and second sets of correlations as sets, each diagram of the plurality of persistence diagrams a set of topological features associated with the first and second sets of correlations;

compute a distance between at least two of the plurality of generated persistence diagrams, wherein the distance represents an anomaly score associated with a change in the topology of the network; and

identify a difference between the first and second sets of correlations between the network metrics as a network anomaly based on the anomaly score.

9. The apparatus as in claim 8, wherein the process when executed is further operable to:

generate an alert indicative of the network anomaly.

10. The apparatus as in claim 8, wherein the process when executed is further operable to:

project the first and second pluralities of measurements onto one or more hyperplanes that each comprise a hash function, to generate measurement signatures; and

use the measurement signatures to determine the first and second sets of correlations.

11. The apparatus as in claim 10, wherein the measurement signatures comprises hashes of the projected first and second pluralities of measurements.

12. The apparatus as in claim 8, wherein the process when executed is further operable to:

perform spectral analysis on the first and second pluralities of measurements, to determine the first and second sets of correlations.

13. The apparatus as in claim 8, wherein the topological features comprise clusters and holes of one or more manifolds in which measurements from the first or second pluralities of measurements are data points in the one or more manifolds.

14. The apparatus as in claim 8, wherein the network metrics comprise at least one of:

a byte size of a traffic flow, a time associated with a traffic flow, or an available resource of a node in the network.

15. A tangible, non-transitory, computer-readable medium storing program instructions that cause a device in a network to execute a process comprising:

receiving a first plurality of measurements for network metrics captured during a first time period;

determining a first set of correlations between the network metrics using the first plurality of measurements captured during the first time period;

receiving a second plurality of measurements for the network metrics captured during a second time period;

determining a second set of correlations between the network metrics using the second plurality of measurements captured during the second time period;

in response to determining the first and second sets of correlations, generating a plurality of persistence diagrams based on the first and second sets of correlations as sets, each diagram of the plurality of persistence diagrams a set of topological features associated with the first and second sets of correlations;

computing a distance between the generated persistence diagrams, wherein the distance represents an anomaly score; and

identifying a difference between the first and second sets of correlations between the network metrics as a network anomaly based on the anomaly score.

16. The computer-readable medium as in claim 15, wherein the process further comprises:

generating an alert indicative of the network anomaly.

17. The computer-readable medium as in claim 15, wherein the process further comprises:

performing spectral analysis on the first and second pluralities of measurements, to determine the first and second sets of correlations.

18. The computer-readable medium as in claim 15, wherein the process further comprises:

using locality-sensitive hashing to identify the network anomaly.