Identifying significant anomalous segments of a metrics dataset

• US 10,129,274 B2
• Filed: 09/22/2016
• Issued: 11/13/2018
• Est. Priority Date: 09/22/2016
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Sheth, Suraj Satishkumar, Sodhani, Shagun, Bajaj, Rohit, Goel, Nitin, Awasthi, Manoj, Malik, Kapil, Rathi, Harsh, Krishnamurthy, Balaji
• Primary Examiner(s): Turchen, James R
• Application Number:
  US15/273,213
• Publication Number:
  US 20180083995A1
• Time in Patent Office: 782 Days
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
• 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 43/00 Arrangements for monitoring or testing data switching networks
• 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/1416 Event detection, e.g. attack signature detection

Abstract

In some embodiments, a processor accesses a metrics dataset, which includes metrics whose values indicate data network activity. The metrics dataset has segments. Each segment is a respective subset of the data items having a common feature. The processor identifies anomalous segments in the metrics dataset. Each anomalous segment has a segment trend that is different from a trend associated with the larger metrics dataset. The processor generates a data graph that includes nodes, which represent anomalous segments, and edges connecting the nodes. The processor applies weights to the edges. Each weight indicates (i) a similarity between a pair of anomalous segments represented by the nodes connected by the weighted edge and (ii) a relationship between the anomalous segments and the metrics dataset. The processor ranks the anomalous segments based on the applied weights and selects one or more segments with sufficiently high ranks.

Claims

1. A computing system for detecting anomalous metrics data representing activity over a data network, the computing system comprising:

a non-transitory computer-readable medium storing a metrics dataset comprising data items whose metrics values indicate data network activity, wherein the metrics dataset includes segments, wherein each segment comprises a respective subset of the data items having a common feature with respect to computing devices or users of the computing devices involved in the data network activity;

a processing device communicatively coupled to the non-transitory computer-readable medium and configured to access the metrics data set and to execute program code stored in the non-transitory computer-readable medium or another non-transitory computer-readable medium,

wherein, when executed by the processing device, the program code configures the processing device to perform operations comprising;

identifying anomalous segments in the metrics dataset based on each anomalous segment having a respective segment trend that is different from a trend for the metrics dataset,

generating a data graph comprising nodes and edges, wherein each node represents a respective one of the anomalous segments and is connected to the other nodes of the data graph via a respective subset of the edges,

applying respective weights to the edges, wherein each weight applied to a respective edge between a respective pair of nodes is computed from (i) a respective similarity between a respective pair of anomalous segments represented by the nodes and (ii) a respective relationship between the respective pair of anomalous segments and the metrics dataset, wherein the operations further comprise determining each relationship between the respective pair of anomalous segments by performing additional operations comprising;

(a) computing a respective correlation score indicating a respective degree of correlation between the metrics dataset and at least one anomalous segment from the respective pair of anomalous segments,

(b) computing a respective contribution score indicating a respective contribution of the at least one anomalous segment to the metrics values of the metrics dataset, and

(c) determining the relationship from a respective combination of the respective correlation score and the respective contribution score,

ranking the anomalous segments based on the weights applied to the edges, and

selecting one of the anomalous segment having a rank that is greater than a threshold rank.

2. The computing system of claim 1, wherein identifying an anomalous segment comprises:

computing a correlation score indicating a correlation between the anomalous segment and the metrics dataset; and

selecting the anomalous segment based on the correlation score being below a threshold correlation score.

3. The computing system of claim 1, wherein each data item comprises a first attribute having a metrics data value and a second attribute indicating a feature of a computing device or a user of the computing device involved in the data network activity, wherein the common feature for a segment comprises each data item in the segment having a common value for the second attribute or a value within a common range of values for the second attribute.

4. The computing system of claim 3, wherein the second attribute comprises at least one of:

a geographic attribute of the computing device or the user;

a demographic attribute of the user;

a hardware attribute of the computing device;

or

a software attribute of the computing device.

5. The computing system of claim 1, wherein the data graph is a directed graph and wherein ranking the anomalous segments comprises executing a PageRank algorithm with the nodes and the edges as inputs.

6. The computing system of claim 5, wherein ranking the anomalous segments comprises:

determining a first ranking for a first node in the data graph;

identifying a first weight for an edge from the first node to a second node and a second weight for an edge from the first node to a third node;

computing a second ranking for the second node based on a portion of the first ranking, wherein the portion of the first ranking is determined based on the first weight; and

computing a third ranking for the third node based on a different portion of the first ranking, wherein the different portion of the first ranking is determined based on the second weight.

7. A method comprising:

a step for accessing a metrics dataset comprising data items whose metrics values indicate data network activity, wherein the metrics dataset includes segments, wherein each segment comprises a respective subset of the data items having a common feature with respect to computing devices or users of the computing devices involved in the data network activity;

a step for identifying anomalous segments in the metrics dataset;

a step for generating a data graph comprising nodes and edges, wherein each node represents a respective one of the anomalous segments and is connected to the other nodes of the data graph via a respective subset of the edges;

a step for applying respective weights to the edges, wherein each weight applied to a respective edge between a respective pair of nodes is computed from (i) a respective similarity between a respective pair of anomalous segments represented by the nodes and (ii) a respective relationship between the respective pair of anomalous segments and the metrics dataset, wherein the method further comprises determining each relationship between the respective pair of anomalous segments by performing operations comprising;

(a) computing a respective correlation score indicating a respective degree of correlation between the metrics dataset and at least one anomalous segment from the respective pair of anomalous segments,

(b) computing a respective contribution score indicating a respective contribution of the at least one anomalous segment to the metrics values of the metrics dataset, and

(c) determining the relationship from a respective combination of the respective correlation score and the respective contribution score;

a step for ranking the anomalous segments based on the weights applied to the edges; and

a step for selecting one of the anomalous segment having a rank that is greater than a threshold rank.

8. The method of claim 7, wherein identifying an anomalous segment comprises:

computing a correlation score indicating a correlation between the anomalous segment and the metrics dataset; and

selecting the anomalous segment based on the correlation score being below a threshold correlation score.

9. The method of claim 7, wherein each data item comprises a first attribute having a metrics data value and a second attribute indicating a feature of a computing device or a user of the computing device involved in the data network activity, wherein the common feature for a segment comprises each data item in the segment having a common value for the second attribute or a value within a common range of values for the second attribute.

10. The method of claim 9, wherein the second attribute comprises at least one of:

a geographic attribute of the computing device or the user;

a demographic attribute of the user;

a hardware attribute of the computing device;

or

a software attribute of the computing device.

11. The method of claim 7, wherein the data graph is a directed graph and wherein the step for ranking the anomalous segments comprises executing a PageRank algorithm with the nodes and the edges as inputs.

12. The method of claim 11, wherein ranking the anomalous segments comprises:

determining a first ranking for a first node in the data graph;

identifying a first weight for an edge from the first node to a second node and a second weight for an edge from the first node to a third node;

computing a second ranking for the second node based on a portion of the first ranking, wherein the portion of the first ranking is determined based on the first weight; and

computing a third ranking for the third node based on a different portion of the first ranking, wherein the different portion of the first ranking is determined based on the second weight.

13. A non-transitory computer-readable medium having program code executable by a processing device stored thereon, the program code comprising:

program code for accessing a metrics dataset comprising data items whose metrics values indicate data network activity, wherein the metrics dataset includes segments, wherein each segment comprises a respective subset of the data items having a common feature with respect to computing devices or users of the computing devices involved in the data network activity;

program code for identifying anomalous segments in the metrics dataset based on each anomalous segment having a respective segment trend that is different from a trend for the metrics dataset;

program code for generating a data graph comprising nodes and edges, wherein each node represents a respective one of the anomalous segments and is connected to the other nodes of the data graph via a respective subset of the edges;

program code for applying respective weights to the edges, wherein each weight applied to a respective edge between a respective pair of nodes is computed from (i) a respective similarity between a respective pair of anomalous segments represented by the nodes and (ii) a respective relationship between the respective pair of anomalous segments and the metrics dataset, wherein the program code further comprises program code for determining each relationship between the respective pair of anomalous segments by performing operations comprising;

(a) computing a respective correlation score indicating a respective degree of correlation between the metrics dataset and at least one anomalous segment from the respective pair of anomalous segments,

(b) computing a respective contribution score indicating a respective contribution of the at least one anomalous segment to the metrics values of the metrics dataset, and

(c) determining the relationship from a respective combination of the respective correlation score and the respective contribution score,

program code for ranking the anomalous segments based on the weights applied to the edges; and

program code for selecting one of the anomalous segment having a rank that is greater than a threshold rank.

14. The non-transitory computer-readable medium of claim 13, wherein identifying an anomalous segment comprises:

computing a correlation score indicating a correlation between the anomalous segment and the metrics dataset; and

selecting the anomalous segment based on the correlation score being below a threshold correlation score.

15. The non-transitory computer-readable medium of claim 13, wherein each data item comprises a first attribute having a metrics data value and a second attribute indicating a feature of a computing device or a user of the computing device involved in the data network activity, wherein the common feature for a segment comprises each data item in the segment having a common value for the second attribute or a value within a common range of values for the second attribute.

16. The non-transitory computer-readable medium of claim 13, wherein the data graph is a directed graph and wherein ranking the anomalous segments comprises executing a PageRank algorithm with the nodes and the edges as inputs,

wherein ranking the anomalous segments comprises:

determining a first ranking for a first node in the data graph;

identifying a first weight for an edge from the first node to a second node and a second weight for an edge from the first node to a third node;

computing a second ranking for the second node based on a portion of the first ranking, wherein the portion of the first ranking is determined based on the first weight; and

computing a third ranking for the third node based on a different portion of the first ranking, wherein the different portion of the first ranking is determined based on the second weight.

17. The non-transitory computer-readable medium of claim 13, wherein the program code further comprises program code for computing each weight from (i) the respective similarity between the respective pair of anomalous segments represented by the nodes and (ii) the respective relationship between the respective pair of anomalous segments and the metrics dataset.