PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic Anomaly Detection in the Cloud Via Statistical Learning

Jordan Hochenbaum, Owen S. Vallis, Arun Kejariwal

arXiv:1704.07706v1cs.LG

TL;DR

Seasonal and trending cloud infrastructure data make existing anomaly-detection techniques difficult to apply, motivating automated methods for application and system metrics. The paper combines seasonal decomposition with statistical anomaly tests, using robust statistics for highly anomalous data, and evaluates the methods on production data across three perspectives. Overall, S-H-ESD outperformed S-ESD, with F-Measure increases of 17.5%, 29.5%, and 0.62% for CapEng, UB, and Inj, respectively.

  • Problem

    Seasonal and trending cloud infrastructure data limit the applicability of existing anomaly-detection techniques, while cloud systems contain many services and metrics requiring automatic detection.

  • Method

    The paper proposes S-ESD using seasonal decomposition and ESD, then extends it as S-H-ESD with median and MAD for robust detection when many observations are anomalous.

  • Results

    Overall, S-H-ESD outperformed S-ESD, with F-Measure increasing by 17.5%, 29.5%, and 0.62% for CapEng, UB, and Inj respectively.

  • Takeaways & Limitations

    The techniques were evaluated on production data for capacity engineering, user behavior, and supervised learning using core, system, and application metrics.

  • Takeaways & Limitations

    S-ESD does not fare well when applied to data sets with a high percentage of anomalies, whereas S-H-ESD is more computationally expensive.

Abstract

from arXiv · show

Performance and high availability have become increasingly important drivers, amongst other drivers, for user retention in the context of web services such as social networks, and web search. Exogenic and/or endogenic factors often give rise to anomalies, making it very challenging to maintain high availability, while also delivering high performance. Given that service-oriented architectures (SOA) typically have a large number of services, with each service having a large set of metrics, automatic detection of anomalies is non-trivial. Although there exists a large body of prior research in anomaly detection, existing techniques are not applicable in the context of social network data, owing to the inherent seasonal and trend components in the time series data. To this end, we developed two novel statistical techniques for automatically detecting anomalies in cloud infrastructure data. Specifically, the techniques employ statistical learning to detect anomalies in both application, and system metrics. Seasonal decomposition is employed to filter the trend and seasonal components of the time series, followed by the use of robust statistical metrics -- median and median absolute deviation (MAD) -- to accurately detect anomalies, even in the presence of seasonal spikes. We demonstrate the efficacy of the proposed techniques from three different perspectives, viz., capacity planning, user behavior, and supervised learning. In particular, we used production data for evaluation, and we report Precision, Recall, and F-measure in each case.

1. INTRODUCTION

Cloud infrastructure time series contain seasonal and trend components that make anomaly detection difficult, so the paper proposes two statistical techniques and evaluates them on production data across three perspectives.

  • Motivation: Seasonality and trend in social-network time series limit the applicability of existing anomaly-detection techniques.Production data can contain multiple modes within a seasonal period and both positive and negative anomalies.
  • Proposed techniques: The paper proposes S-ESD, which decomposes a time series to isolate seasonality before applying ESD to the residual series.The approach targets anomalies in application metrics such as Tweets Per Sec and system metrics such as CPU utilization.
  • Proposed techniques: S-H-ESD extends S-ESD with median and MAD, making detection more robust when a high percentage of observations are anomalous.This robustness addresses the sensitivity of mean and standard deviation to many anomalies, at the cost of greater computational expense.
  • Evaluation: The techniques were evaluated with production data from capacity planning, user behavior, and supervised-learning perspectives.The supervised-learning evaluation injected anomalies into smoothed production data while varying injection time, magnitude, and width.
  • Evaluation: Capacity planning links anomaly detection to potential SLA violations, end-user impact, and provisioning additional capacity.The evaluation tests detection of system-metric anomalies exceeding a specified SLA threshold.

2. BACKGROUND

This section introduces statistical anomaly-detection methods, robust alternatives to mean-based measures, and the evaluation metrics used later in the paper.

  • A time series is a sequence of observations collected over time, denoted by x_t and X.
  • Existing hypothesis tests evaluate whether data contain outliers by rejecting a null hypothesis at a specified significance level.
  • 2.1.1 Grubbs Test: Grubbs’ test assumes normality and is not suited to detecting multiple outliers because its critical-value procedure is not updated across iterations.
  • 2.1.2 ESD Test: ESD detects multiple anomalies using an upper bound k, repeatedly comparing test statistics with recalculated critical values.
  • 2.2 Median and Median Absolute Deviation: Median and MAD are robust alternatives because the mean and standard deviation are sensitive to anomalous observations.
  • 2.3 Precision, Recall, and F-Measure: The paper evaluates anomaly detectors using Precision, Recall, and F-measure, with F1 weighting Precision and Recall equally.

3. TECHNIQUES

The paper develops Seasonal ESD and Seasonal Hybrid ESD through an incremental evaluation of production anomaly-detection methods; both approaches are deployed daily on production data.

  • The authors detail Seasonal ESD (S-ESD) and Seasonal Hybrid ESD (S-H-ESD) for automatically detecting anomalies in production data.
  • The techniques were developed incrementally, beginning with evaluation of the Three Sigma Rule on production data.
  • Both approaches are currently deployed to automatically detect anomalies in production data on a daily basis.

3.1 Three-Sigma Rule

The Three Sigma Rule is inadequate for the paper’s production time series because seasonal anomalies, non-stationarity, and non-normal distributions undermine its assumptions and detection behavior.

  • The 3 · σ rule labels points more than three sample standard deviations from the mean as anomalous, but it is ill-suited to seasonal anomalies.
  • Segmenting the non-stationary series into windows changes σ over time, but per-window application still fails to capture seasonal anomalies.
  • The rule assumes a normal distribution, whereas production time series are seldom normal.
  • The authors therefore find the 3·σ rule inapplicable in this context and proceed to investigate moving averages.

3.2 Moving Averages

Moving averages were explored as a way to smooth noise before anomaly detection, but production time series showed that they filter seasonal anomalies and lag behind real-time changes.

  • Moving averages were proposed to filter white noise before anomaly detection.
  • SMA weights the previous n data points equally, whereas EWMA gives greater weight to recent observations through α.
  • EWMA can be volatile to abrupt transient changes, while PEWMA adapts α using the probability of the current observation.
  • Moving averages filter out most seasonal anomalies, causing ESD on PEWMA to miss true anomalies in production data.
  • Moving averages are lagging indicators and therefore are not suited for real-time anomaly detection.
  • Shorter windows better trace the input series but increase the standard error of σ as window length decreases.

3.3 Seasonality and STL

Seasonal decomposition addresses heavy seasonality and multimodal distributions by separating a time series into seasonal, trend, and residual components; STL improves robustness to anomalies.

  • Heavy seasonality and multimodal distributions limit Grubbs and ESD because those techniques assume normally distributed data.
  • Time series decomposition separates X into seasonal SX, trend TX, and residual RX components, with the residual suited to anomaly detection.
  • A sub-cycle series contains values at each position of a seasonal cycle, such as all January values in monthly data with yearly periodicity.
  • Additive decomposition estimates trend with a moving-average filter, then estimates seasonality by averaging corresponding sub-cycle values.
  • Extreme anomalies can corrupt the residual component, so STL uses LOESS and an outer robustness loop to estimate decomposition components.
  • STL’s bisquare weights are used to converge closer to the true decomposed components during subsequent inner-loop iterations.

3.4 Seasonal ESD (S-ESD)

S-ESD combines modified STL decomposition with ESD to detect global and seasonal local anomalies, while its standard formulation can produce spurious or missed anomalies in difficult data.

  • The existing techniques are limited by seasonal and multimodal Twitter time-series data.
  • S-ESD extracts the residual component with modified STL decomposition and applies ESD to detect anomalies.
  • This two-step process detects global anomalies beyond seasonal bounds and local anomalies masked by seasonality.
  • STL Variant: Using STL on system metrics can create spurious residual anomalies when continuous raw-data anomalies produce a breakout in the trend component.
  • STL Variant: S-ESD computes residuals by subtracting the STL seasonal component and raw-series median from X, then applies ESD to the residual.
  • Global and Local Anomalies: S-ESD exposes local anomalies that remain within seasonal minimum and maximum values and may indicate changes in user behavior or cloud systems.
  • Limitations: S-ESD performs poorly when a time series contains a high percentage of anomalies, because ESD’s mean and standard deviation become inflated.

3.5 Seasonal Hybrid ESD (S-H-ESD)

S-H-ESD replaces ESD’s mean and standard deviation with the more robust median and MAD, improving detection when anomalous observations are prevalent at the cost of higher runtime.

  • S-H-ESD extends S-ESD with robust statistics to estimate central tendency consistently when a high percentage of observations are anomalous.
  • S-H-ESD replaces ESD’s mean and standard deviation with the median and MAD, which have a higher breakdown point.
  • S-ESD detects 1.11% of the input as anomalous, whereas S-H-ESD detects 29.68% for the highly anomalous time series.
  • Using median and MAD requires sorting the data, making S-H-ESD more computationally expensive than S-ESD.
  • S-ESD is advised for large time series with relatively few anomalies, while S-H-ESD is more robust to a higher anomaly percentage.

4. EVALUATION

The evaluation uses production time series spanning system and core-driver metrics, assessing S-ESD and S-H-ESD through capacity engineering, user behavior, and injected-anomaly perspectives. S-H-ESD generally improves F-measure, while threshold definitions and anomaly magnitude affect performance.

  • Evaluation data: The evaluation covers more than 20 production data sets, including system metrics sampled hourly and core-driver metrics sampled per minute.System-metric periods span two to four weeks, while core-driver periods cover four weeks.
  • Evaluation design: The three evaluation perspectives are capacity engineering, user behavior, and supervised learning with injected anomalies.Capacity and user-behavior cases use service-owner thresholds, while injection provides labeled anomaly positions and magnitudes.
  • Capacity engineering and user behavior: Precision increases from about 75% to 100% for S-ESD and from about 59% to 95% for S-H-ESD between CapEng and UB.CapEng thresholds can label off-peak anomalies as false positives, whereas UB thresholds operate on the residual component.
  • Capacity engineering and user behavior: S-H-ESD recall rises from 47.5% to 77% for CapEng and from 31.5% to 65% for UB relative to S-ESD.The UB threshold is applied after trend and seasonal components are removed.
  • Injected anomalies: Injected anomalies with magnitude 3σ or greater achieve an F-measure of 1.00, while smaller 0.75σ anomalies yield lower values.At 0.75σ, F-measure is 0.84 for S-ESD and 0.88 for S-H-ESD at 95% confidence.
  • Overall results: At 95% confidence, S-H-ESD increases average F-measure by 17.5%, 29.5%, and 0.62% for CapEng, UB, and Inj, respectively.The improvement is attributed to median and MAD being robust against many outliers.

5. PREVIOUS WORK

Previous work spans statistical, signal-processing, manufacturing, finance, and network-intrusion approaches to anomaly detection. These methods include distributional bounds, control charts, spectral and wavelet techniques, filtering, PCA, and rule-based or learning-based models.

  • Manufacturing: Traditional control charts use sample means and standard deviations to define center lines and control limits over time.EWMA charts emphasize recent samples and detect small shifts more efficiently, while Shewhart charts detect larger shifts more efficiently.
  • Finance: Finance research studies seasonal market anomalies such as January, Monday, and turn-of-the-month effects, with some findings disputed across studies.The cited literature reports both evidence for and challenges to specific calendar effects.
  • Signal processing: Signal-processing approaches include spectral analysis, wavelet decomposition, Kalman filtering, and PCA for detecting anomalies across frequencies or network signals.Wavelet methods provide time-frequency decomposition, while combined Kalman and statistical models were reported to outperform PCA-KL in one comparison.
  • Network traffic: Network-intrusion research includes rule-based profiling, comparative evaluations of detection schemes, and statistical, knowledge-based, and learning-based classifiers.These approaches use network or user data to identify abnormal behavior or intrusion patterns.
  • Statistics: Statistical anomaly detection research includes inequality-based bounds, control charts, and methods for identifying observations that depart from an underlying distribution.Markov and Chebyshev bounds are non-parametric but relatively weak.

6. CONCLUSION

The conclusion presents S-ESD and S-H-ESD for anomaly detection in seasonal and trending cloud infrastructure data. Across the three evaluation perspectives, S-H-ESD outperforms S-ESD, but its higher computational cost and challenges with long time series constrain deployment choices.

  • Contribution: S-ESD combines seasonal decomposition with the Generalized ESD test, while S-H-ESD adds median and MAD for robustness when up to 50% of data is anomalous.Both techniques target automatic anomaly detection in cloud infrastructure data.
  • Results: S-H-ESD increases F-measure by 17.5%, 29.5%, and 0.62% for CapEng, UB, and Inj, respectively.Evaluation covers core, system, and application metrics using precision, recall, and F-measure.
  • Scope and trade-offs: S-ESD is recommended for large time series with relatively few anomalies because S-H-ESD is more computationally expensive and requires sorting.The recommendation reflects the computational trade-off between the two methods.
  • Future work: Extending the techniques to long time series remains future work because estimating the underlying trend is difficult in the presence of anomalies.The authors identify quantile and robust regression as possible directions.
Loading 1704.07706v1…