SYSTEMS AND METHODS FOR ROBUST ANOMALY DETECTION

• US 20190102276A1
• Filed: 11/16/2017
• Published: 04/04/2019
• Est. Priority Date: 10/04/2017
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: ServiceNow Incorporated
• Inventors: Dang, Kanwaldeep K., Amradkhar, Purushottam, Crotinger, James, Tucker, Stephen Scott, Lennon, Dustin
• Granted Patent: US 10,635,565 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/3072 where the reporting involves data filtering, e.g. pattern matching, time or event triggered, adaptive or policy-based reporting
• CPC Class Codes: G06F 11/323 Visualisation of programs or trace data
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3419 by assessing time
• 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/24155 Bayesian classification
• CPC Class Codes: G06F 18/2433 Single-class perspective, e.g. one-against-all classification; Novelty detection; Outlier detection
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A system, includes: a distributed cache that stores state information for a plurality of configuration items (CIs). Management, instrumentation, and discovery (MID) servers form a cluster, each of the MID servers including one or more processors that receive, from the distributed cache, a subset of the state information associated with assigned CIs and perform a statistical analysis on the subset of the state information.

Claims

1. A system, comprising:

a distributed cache configured to store state information for a plurality of configuration items (CIs);

a plurality of management, instrumentation, and discovery (MID) servers forming a cluster, each of the plurality of MID servers comprising;

one or more processors, configured to execute machine readable instructions;

a tangible, non-transitory, machine-readable medium, comprising machine-readable instructions that, when executed by the one or more processors;

receive, from the distributed cache, a subset of the state information associated with assigned CIs; and

perform a statistical analysis on the subset of the state information.

2. The system of claim 1, wherein each of the MID services comprise:

an anomaly detector, configured to;

identify statistical outliers of the statistical analysis;

identify an anomaly of the statistical outliers by tracking a history of the statistical outliers;

wherein the anomaly is determined based upon a magnitude of deviation between the subset of the state information and a statistical model.

3. The system of claim 2, comprising:

a change detector, configured to;

identify the statistical outliers using a first filter applied to the subset of the state information;

determine when a data transition associated with the statistical outliers indicates noise;

determine when the data transition associated with the statistical outliers indicates a level change; and

when the data transition associated with the statistical outliers indicates the level change, present a notification of the level change.

4. The system of claim 3, wherein the filter comprises a Kalman filter that produces estimates of unknown variables using Bayesian inference and joint probability distribution estimation over the unknown variables for a timeframe.

5. The system of claim 4, wherein the machine-readable instructions, when executed by the one or more processors:

determine when the data transition associated with the statistical outliers indicates noise and determine when the data transition associated with the statistical outliers indicate a level change, by;

upon identifying the statistical outliers, feed data to a second filter that represents data indicative of no statistical outlier occurring;

upon stabilization of a change in the first filter, use an output of the second filter as a reference to determine is the change is statically significant;

when the change is statistically significant, classify the data transition associated with the statistical outliers as a level shift, and

otherwise, when the change is not statistically significant, classify the data transition associated with the statistical outliers as noise.

6. The system of claim 1, wherein each of the MID servers comprise:

a time-series analyzer, configured to;

classify the subset of the state information into at least one of a plurality of classifications based at least in part upon historical time-series data; and

construct a statistical model representative of the stream of current time-series data based upon the at least one of the plurality of classifications;

an anomaly detector, configured to;

monitor the stream of current time-series data;

perform a statistical analysis on the stream of the current time-series data based at least in part upon the statistical model constructed by the time-series analyzer;

identify statistical outliers of the stream of the current time-series data based at least on the statistical analysis;

determine an anomalous score for the statistical outliers based at least on a history of the statistical outliers;

wherein the anomalous score indicates a magnitude of deviation between the current time-series data and the statistical model; and

present the anomalous score to a client communicatively coupled to the system, for subsequent reporting, client action, or both.

7. The system of claim 6, wherein the plurality of classifications comprise:

a quasi-normal classification, indicating that the subset of the state information appears to adhere to a stationary process;

a seasonal classification, indicating that the subset of the state information appears to adhere to a process having periodic non-normal distribution, a general trend over time, or both;

a near-constant classification, indicating that the subset of the state information appears to adhere to a constant value;

a trendy classification, indicating that the subset of the state information comprises noisy data with a trend;

an accumulator classification, indicating that the subset of the state information comprises an accumulation of low-noise data;

a categorical classification, indicating that the subset of the state information appears to adhere to a process having a set of discrete values;

a switching classification, indicating that the subset of the state information appears to adhere to a process of jumping from at least one first state to at least one second state via one or more state transitions; and

an arrival classification, indicating that the subset of the state information appears to adhere to a process dependent upon a timing of a particular event.

8. The system of claim 7, wherein the one or more processors determine whether the subset of the state information adheres to a weekly model or a daily model when the subset of the state information is seasonal.

9. The system of claim 8, wherein the one or more processors determine whether the subset of the state information adheres to the weekly model or the daily model by comparing a log-likelihood for a fit of the weekly model and the daily model to a fit threshold.

10. The system of claim 9, wherein the fit threshold is identified based upon Wilks'"'"' Theorem.

11. A tangible, non-transitory, machine-readable medium, comprising machine-readable instructions to:

receive a stream of the current time-series data;

at periodic intervals, classify the stream of current time-series data into at least one of a plurality of classifications based at least in part upon historical time-series data;

when the classification comprises a seasonal classification, identify a statistical model representative of the stream of current time-series data from a selection between a weekly statistical model and a daily statistical model; and

perform a statistical analysis on the stream of the current time-series data based at least in part upon the statistical model constructed by the time-series analyzer; and

provide a graphical indication of results of the statistical analysis at a communicatively coupled instance.

16. The machine-readable medium of claim 11, comprising instructions to:

receive only a subset of the stream of the current time-series data associated with assigned configuration items (CIs).

13. The machine-readable medium of claim 12, comprising instructions to:

identify statistical outliers of the stream of the current time-series data based at least on the statistical analysis;

determine an anomalous score for the statistical outliers by tracking a history of the statistical outliers;

wherein the anomalous score indicates a magnitude of deviation between the stream of current time-series data and the statistical model; and

store the anomalous score, for subsequent reporting, client action, or both.

14. The machine-readable medium of claim 12, comprising instructions to:

identify a statistical outlier of the stream of the current time-series data based at least on the statistical analysis; and

classify the statistical outlier as either noise or a level shift.

15. The machine-readable medium of claim 14, comprising instructions to classify the one or more statistical outliers as either noise or a level shift, by:

feeding unobserved data that that suggests that no statistical outlier has occurred into a filter;

determining, via filtering of the unobserved data by the filter, whether a data transition associated with the statistical outlier is statistically significant;

classifying the statistical outlier as a level shift when the data transition is statistically significant; and

classifying the statistical outlier as noise when the data transition is not statistically significant.

17. A management, instrumentation, and discovery (MID) server, comprising:

one or more processors, configured to execute machine readable instructions;

a tangible, non-transitory, machine-readable medium, comprising machine-readable instructions that, when executed by the one or more processors;

receive a subset of a stream of current time-series data that is associated with assigned configuration items (CIs) of the MID server;

classify the subset of the stream of current time-series data as seasonal data;

select a statistical model representative of the subset of the stream of current time-series data from a selection between a weekly statistical model and a daily statistical model;

perform a statistical analysis on the stream of the current time-series data based at least in part upon the statistical model constructed by the time-series analyzer;

identify statistical outliers of the stream of the current time-series data based at least on the statistical analysis;

classify the statistical outliers as either transient or a level shift; and

when the statistical outliers are classified as transient, identify an anomaly from the statistical outliers by tracking a history of the statistical outliers;

wherein the anomaly is identified based upon a magnitude of deviation between the current time-series data and the statistical model.

18. The MID server of claim 17, comprising a first Kalman filter used to identify the anomaly and a second Kalman filter user to classify the statistical outliers.

19. The MID server of claim 17, wherein the machine-readable medium comprises machine-readable instructions that, when executed by the one or more processors:

cause the MID server to act as a redundant MID server for an offline MID server of a cluster comprising the MID server and the offline MID server.

20. The MID server of claim 17, comprising a System Center-Operations Manager (SCOM), a Representational State Transfer (REST) application-programming-interface (API), or both that is used to receive the subset of a stream of current time-series data from a distributed cache.