Anomaly detection for cloud monitoring
View Patent ↗Technologies are presented for anomaly detection in a cloud environment using a sparsity measure. In some examples, cloud metric data may be gathered and processed into a dictionary base. Linear transform coefficients for a test sample may then be calculated from the dictionary base using l 1 -norm minimization. A sparsity measure may then be computed from the linear transform coefficients. If the sparsity measure does not exceed a predefined threshold, the test sample may be determined as anomalous.
1. A method for detecting anomalies in cloud monitoring, the method comprising:
collecting training samples from a plurality of metrics associated with operations of a cloud based entity;
forming a dictionary from the training samples;
determining linear transform coefficients for a test sample using the dictionary;
determining a sparsity measure of the linear transform coefficients for the test sample; and
in response to a determination that the sparsity measure is below a predefined threshold, classifying the test sample as an anomaly.
2. The method according to claim 1 , further comprising:
in response to a determination that the sparsity measure is above the predefined threshold, classifying the test sample as a normal pattern.
3. The method according to claim 1 , further comprising:
determining the linear transform coefficients based on minimizing a Euclidean distance between the test sample and the dictionary and minimizing an h-norm of the linear transform coefficients at the same time.
4. The method according to claim 1 , further comprising:
pre-processing the test sample prior to computing the linear transform coefficients.
5. The method according to claim 4 , wherein pre-processing includes:
normalizing a sample value by dividing the sample value by a mean of values of the same type in a current time instant;
data-binning by hashing the normalized sample value into one of a plurality of bins; and
constructing a metric histogram based on the binned sample value.
6. The method according to claim 5 , wherein the linear transform coefficients are computed from the metric histogram.
7. The method according to claim 6 , wherein data binning comprises:
predefining a value range [0, r];
dividing the value range into B-1 substantially equal-sized bins indexed from 0 to B-2; and
defining an additional bin indexed B-1 for capturing values larger than r, where B and r are statistically predefined, configurable parameters.
8. The method according to claim 7 , wherein an x-axis of the metric histogram denotes a bin index and a y-axis of the metric histogram denotes a percentage of the total sample values for an individual bin index.
9. The method according to claim 8 , wherein each metric histogram is a vector with its components being a percentage value at each bin index.
10. The method according to claim 9 , further comprising:
forming the dictionary by stacking a plurality of metric histogram vectors.
11. A cloud-based data center configured to detect anomalies in cloud monitoring, the cloud-based data center comprising:
a plurality of virtual machines operable to be executed on one or more physical machines; and
a data center controller configured to:
collect training samples from a plurality of metrics associated with operations of the data center;
form a dictionary from the training samples;
determine linear transform coefficients for a test sample using the dictionary;
determine a sparsity measure of the linear transform coefficients for the test sample;
in response to a determination that the sparsity measure is below a predefined threshold classify the test sample as an anomaly; and
in response to a determination that the sparsity measure is above the predefined threshold, classify the test sample as a normal pattern.
12. The data center according to claim 11 , wherein the data center controller is further configured to:
employ a buffer to maintain the dictionary.
13. The data center according to claim 12 , wherein the buffer slides metric histograms one by one during a monitoring process.
14. The data center according to claim 11 , wherein the data center controller is further configured to:
evaluate the sparsity measure of the linear transform coefficients by computing a sparsity concentration index (SCI) as:
SCI
(
A
)
=
N
*
max
i
(
δ
i
(
A
)
δ
(
A
)
)
-
1
N
-
1
,
where δ i (A) returns a number of non-zero coefficients within a i =[a i,1 , a i,2 , . . . a i, N] corresponding to an i th dictionary element and δ (A) returns a total number of non-zero coefficients within A, linear transform coefficients vector for the test sample.
15. The data center according to claim 14 , wherein the data center controller is further configured to:
compare the SCI to the predefined threshold.
16. The data center according to claim 15 , wherein the predefined threshold is one of application-specific and user-defined.
17. The data center according to claim 11 , wherein the dictionary is an over-complete dictionary.
18. The data center according to claim 11 , wherein the plurality of metrics includes one or more of operating system metrics, application metrics, and platform metrics.
19. The data center according to claim 11 , wherein the data center controller is further configured to:
compute the coefficients globally in terms of the training samples of normal patterns to harness a joint distribution of the normal patterns for validating whether the test sample is normal or not.
20. A non-transitory computer-readable storage medium having instructions stored thereon for detecting anomalies in cloud monitoring, the instructions comprising:
collecting training samples from a plurality of metrics associated with operations of a cloud based entity;
forming a dictionary from the training samples;
determining linear transform coefficients for a test sample using the dictionary;
determining a sparsity measure of the linear transform coefficients for the test sample;
in response to a determination that the sparsity measure is below a predefined threshold classifying the test sample as an anomaly; and
in response to a determination that the sparsity measure is above the predefined threshold, classifying the test sample as a normal pattern.
21. The non-transitory computer-readable storage medium according to claim 20 , wherein the instructions further comprise:
pre-processing the test sample prior to computing the linear transform coefficients by:
normalizing a sample value by dividing the sample value by a mean of values of same type in a current time instant, data binning by hashing the normalized sample value into one of a plurality of bins, and constructing a metric histogram based on the binned sample value.