Data-agnostic anomaly detection

• US 10,241,887 B2
• Filed: 03/29/2013
• Issued: 03/26/2019
• Est. Priority Date: 03/29/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Poghosyan, Arnak, Harutyunyan, Ashot Nshan, Grigoryan, Naira Movses, Marvasti, Mazda A.
• Primary Examiner(s): Mehrmanesh, Elmira
• Application Number:
  US13/853,321
• Publication Number:
  US 20140298098A1
• Time in Patent Office: 2,188 Days
• Field of Search: 714 26, 714 37, 714 472, 714 473
• CPC Class Codes: G05B 23/0235 based on a comparison with predetermined threshold or range, e.g. "classical methods", carried out during normal operation; threshold adaptation or choice; when or how to compare with the threshold
• CPC Class Codes: G06F 11/0706 the processing taking place on a specific hardware platform or in a specific software environment
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: G06F 2218/12 Classification; Matching

Abstract

This disclosure presents computational systems and methods for detecting anomalies in data output from any type of monitoring tool. The data is aggregated and sent to an alerting system for abnormality detection via comparison with normalcy bounds. The anomaly detection methods are performed by construction of normalcy bounds of the data based on the past behavior of the data output from the monitoring tool. The methods use data quality assurance and data categorization processes that allow choosing a correct procedure for determination of the normalcy bounds. The methods are completely data agnostic, and as a result, can also be used to detect abnormalities in time series data associated with any complex system.

Claims

1. A data-anomaly detection system comprising:

one or more processors;

one or more computer-readable media; and

a routine that executes on the one or more processors to analyze digitally encoded data output from a system monitoring tool and stored in the computer-readable media by

identifying the output data as qualified data or corrupted data;

identifying and sorting the qualified data into categorized data;

calculating normalcy bounds for the categorized data;

discarding the corrupted data from the computer-readable media; and

inputting the categorized data and normalcy bounds to an alerting engine that generates an alert when the categorized data is outside the normalcy bounds.

2. The system of claim 1, wherein identifying qualified data further comprises

determining whether the input data is qualified data or corrupted data;

and

determining whether the qualified data is dense data or sparse data.

3. The system of claim 2, wherein determining whether the qualified data is dense data or sparse data further comprises

calculating a percentage of gaps in the qualified data, based on a user defined gap parameter;

calculating data-to-data, data-to-gap, gap-to-gap, and gap-to-data transition probabilities; and

based on the transitions probabilities and the percentage of gaps, classifying the qualified data as dense data, sparse data, or corrupted data.

4. The system of claim 1, wherein identifying the qualified data further comprises

determining whether the qualified data is stable data or corrupted data;

and

categorizing stable qualified data as high-variability data or low-variability data.

5. The system of claim 4, wherein determining whether the qualified data is stable data or corrupted data further comprises

generating a stabilochart for the qualified data;

and

for each stabilochart value,

when the stabilochart value is less than a user defined value, the qualified data is stable data, otherwise the qualified data is corrupted data.

6. The system of claim 4, wherein categorizing stable data as high-variability data or low-variability data further comprises

calculating jumps for the stable qualified data;

calculating a measure of variability based on the jumps and the stable data; and

identifying the stable data as low-variability data when the measure of variability is less than a user defined threshold, otherwise the stable data is high-variability data.

7. The system of claim 1, wherein identifying and sorting the qualified data into categorized data further comprises

determining whether the qualified data as parametric data or regular data;

and

when the qualified data is parametric data, calculating normalcy bounds for the parametric data.

8. The system of claim 7, wherein determining whether the qualified data is parametric data further comprises

checking the qualified data for categories of multinomial data;

when no categories of multinomial data are found, de-noising the qualified data followed by rechecking the qualified data for categories of multinomial data;

determining whether the qualified data is periodic or non-periodic; and

calculating normalcy bounds for the qualified data based on the periodicity.

9. The system of claim 7, wherein determining whether the qualified data is parametric data further comprises

searching for two or more modes in the qualified data;

checking each mode of qualified data for inertia;

checking each mode identified as having inertia for transiency;

for each inertial mode,

determining whether the mode is periodic or non-periodic; and

calculating normalcy bounds for the inertial mode based on the periodicity of the mode.

10. The system of claim 7, wherein determining whether the qualified data is parametric data further comprises

checking parameters of the qualified data for semi-constant data;

when no semi-constant data is found, searching the qualified data for the longest data portion of the data that is semi-constant;

detecting the number of outliers in the semi-constant data;

determining whether the semi-constant data is periodic or non-periodic; and

calculating normalcy bounds for the semi-constant data based on the periodicity.

11. The system of claim 7, wherein determining whether the qualified data is parametric data further comprises

searching the qualified data for a trend;

identifying the trend of the qualified data as linear, log-linear, or non-trendy; and

calculating normalcy bounds based on the identified trend for the qualified data.

12. The system of claim 1, wherein calculating the normalcy bounds further comprises

removing abnormal outliers from the data;

smoothing the data;

generating a footprint matrix of the smooth data;

determining whether the data in the footprint matrix is periodic or non-periodic; and

calculating upper and lower normalcy bounds based on the footprint matrix.

13. A method carried out within a computer system having one or more processors and an electronic memory that analyzes digitally encoded data stored in one or more computer-readable media, the method comprising:

identifying data output from a system monitoring tool as qualified data or corrupted data;

identifying and sorting the qualified data into categorized data;

calculating normalcy bounds for the categorized data;

discarding the corrupted data from the computer-readable media; and

inputting the categorized data and normalcy bounds to an alerting engine that generates an alert when the categorized data is outside the normalcy bounds.

14. The method of claim 13, wherein identifying qualified data further comprises

determining whether the input data is qualified data or corrupted data;

and

determining whether the qualified data is dense data or sparse data.

15. The method of claim 14, wherein determining whether the qualified data is dense data or sparse data further comprises

calculating a percentage of gaps in the qualified data, based on a user defined gap parameter;

calculating data-to-data, data-to-gap, gap-to-gap, and gap-to-data transition probabilities; and

based on the transitions probabilities and the percentage of gaps, classifying the qualified data as dense data, sparse data, or corrupted data.

16. The method of claim 13, wherein identifying the qualified data further comprises

determining whether the qualified data is stable data or corrupted data;

and

categorizing stable qualified data as high-variability data or low-variability data.

17. The method of claim 16, wherein determining whether the qualified data is stable data or corrupted data further comprises

generating a stabilochart for the qualified data;

and

for each stabilochart value,

when the stabilochart value is less than a user defined value, the qualified data is stable data, otherwise the qualified data is corrupted data.

18. The method of claim 16, wherein categorizing stable data as high-variability data or low-variability data further comprises

calculating jumps for the stable qualified data;

calculating a measure of variability based on the jumps and the stable data; and

identifying the stable data as low-variability data when the measure of variability is less than a user defined threshold, otherwise the stable data is high-variability data.

19. The method of claim 13, wherein identifying and sorting the qualified data into categorized data further comprises

determining whether the qualified data as parametric data or regular data;

and

when the qualified data is parametric data, calculating normalcy bounds for the parametric data.

20. The method of claim 19, wherein determining whether the qualified data is parametric data further comprises

checking the qualified data for categories of multinomial data;

when no categories of multinomial data are found, de-noising the qualified data followed by rechecking the qualified data for categories of multinomial data;

determining whether the qualified data is periodic or non-periodic; and

calculating normalcy bounds for the qualified data based on the periodicity.

21. The method of claim 19, wherein determining whether the qualified data is parametric data further comprises

searching for two or more modes in the qualified data;

checking each mode of qualified data for inertia;

checking each mode identified as having inertia for transiency;

for each inertial mode,

determining whether the mode is periodic or non-periodic; and

calculating normalcy bounds for the inertial mode based on the periodicity of the mode.

22. The method of claim 19, wherein determining whether the qualified data is parametric data further comprises

checking parameters of the qualified data for semi-constant data;

when no semi-constant data is found, searching the qualified data for the longest data portion of the data that is semi-constant;

detecting the number of outliers in the semi-constant data;

determining whether the semi-constant data is periodic or non-periodic; and

calculating normalcy bounds for the semi-constant data based on the periodicity.

23. The method of claim 19, wherein determining whether the qualified data is parametric data further comprises

searching the qualified data for a trend;

identifying the trend of the qualified data as linear, log-linear, or non-trendy; and

calculating normalcy bounds based on the identified trend for the qualified data.

24. The method of claim 13, wherein calculating the normalcy bounds further comprises

removing abnormal outliers from the data;

smoothing the data;

generating a footprint matrix of the smooth data;

determining whether the data in the footprint matrix is periodic or non-periodic; and

calculating upper and lower normalcy bounds based on the footprint matrix.

25. A non-transitory computer-readable medium encoded with machine-readable instructions that implement a method carried out by one or more processors of a computer system to perform the operations of

identifying data output from a system monitoring tool as qualified data or corrupted data;

identifying and sorting the qualified data into categorized data;

calculating normalcy bounds for the categorized data;

discarding the corrupted data from the computer-readable media; and

inputting the categorized data and normalcy bounds to an alerting engine that generates an alert when the categorized data is outside the normalcy bounds.

26. The medium of claim 25, wherein identifying qualified data further comprises

determining whether the input data is qualified data or corrupted data;

and

determining whether the qualified data is dense data or sparse data.

27. The medium of claim 26, wherein determining whether the qualified data is dense data or sparse data further comprises

calculating a percentage of gaps in the qualified data, based on a user defined gap parameter;

calculating data-to-data, data-to-gap, gap-to-gap, and gap-to-data transition probabilities; and

based on the transitions probabilities and the percentage of gaps, classifying the qualified data as dense data, sparse data, or corrupted data.

28. The medium of claim 25, wherein identifying the qualified data further comprises

determining whether the qualified data is stable data or corrupted data;

and

categorizing stable qualified data as high-variability data or low-variability data.

29. The medium of claim 28, wherein determining whether the qualified data is stable data or corrupted data further comprises

generating a stabilochart for the qualified data;

and

for each stabilochart value,

when the stabilochart value is less than a user defined value, the qualified data is stable data, otherwise the qualified data is corrupted data.

30. The medium of claim 28, wherein categorizing stable data as high-variability data or low-variability data further comprises

calculating jumps for the stable qualified data;

calculating a measure of variability based on the jumps and the stable data; and

identifying the stable data as low-variability data when the measure of variability is less than a user defined threshold, otherwise the stable data is high-variability data.

31. The medium of claim 25, wherein identifying and sorting the qualified data into categorized data further comprises

determining whether the qualified data as parametric data or regular data;

and

when the qualified data is parametric data, calculating normalcy bounds for the parametric data.

32. The medium of claim 31, wherein determining whether the qualified data is parametric data further comprises

checking the qualified data for categories of multinomial data;

when no categories of multinomial data are found, de-noising the qualified data followed by rechecking the qualified data for categories of multinomial data;

determining whether the qualified data is periodic or non-periodic; and

calculating normalcy bounds for the qualified data based on the periodicity.

33. The medium of claim 31, wherein determining whether the qualified data is parametric data further comprises

searching for two or more modes in the qualified data;

checking each mode of qualified data for inertia;

checking each mode identified as having inertia for transiency;

for each inertial mode,

determining whether the mode is periodic or non-periodic; and

calculating normalcy bounds for the inertial mode based on the periodicity of the mode.

34. The medium of claim 31, wherein determining whether the qualified data is parametric data further comprises

checking parameters of the qualified data for semi-constant data;

when no semi-constant data is found, searching the qualified data for the longest data portion of the data that is semi-constant;

detecting the number of outliers in the semi-constant data;

determining whether the semi-constant data is periodic or non-periodic; and

calculating normalcy bounds for the semi-constant data based on the periodicity.

35. The medium of claim 31, wherein determining whether the qualified data is parametric data further comprises

searching the qualified data for a trend;

identifying the trend of the qualified data as linear, log-linear, or non-trendy; and

calculating normalcy bounds based on the identified trend for the qualified data.

36. The medium of claim 25, wherein calculating the normalcy bounds further comprises

removing abnormal outliers from the data;

smoothing the data;

generating a footprint matrix of the smooth data;

determining whether the data in the footprint matrix is periodic or non-periodic; and

calculating upper and lower normalcy bounds based on the footprint matrix.