Anomaly detection in a signal

• US 9,471,544 B1
• Filed: 05/24/2012
• Issued: 10/18/2016
• Est. Priority Date: 05/24/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yu, Kevin, Zhang, Xinyi
• Primary Examiner(s): Ngon, Ricky
• Application Number:
  US13/480,042
• Time in Patent Office: 1,608 Days
• Field of Search: 702181-183
• US Class Current: 1/1
• 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 2218/10 by analysing the shape of a waveform, e.g. extracting parameters relating to peaks

Abstract

Systems and methods are disclosed herein for detecting an anomaly in a discrete signal, where a long-term trend of the discrete signal is identified. Samples in the signal correspond to a number of data packets arriving at a location in a network within a time interval. The long-term trend is subtracted from the discrete signal to obtain a detrended signal. A cyclic pattern is identified in the detrended signal and is subtracted from the detrended signal to obtain a residual signal. Anomaly detection is performed on the residual signal.

Claims

1. A method for detecting anomalies in a discrete signal from network traffic flow comprising:

receiving, by an anomaly detector including one or more processors, a network traffic signal comprising discretized samples corresponding to data packets arriving at a network node within a sampled time interval;

identifying, by the anomaly detector, a trend component of the network traffic signal, the trend component corresponding to frequency components of the network traffic signal below a first cut-off frequency threshold calculating, by the anomaly detector, a detrended network traffic signal based on the trend component and the network traffic signal;

identifying, by the anomaly detector, a cyclic component in the detrended network traffic signal, the cyclic component corresponding to frequency components of the detrended network traffic signal above a second cut-off frequency, the second cut-off frequency greater than the first cut-off frequency;

calculating, by the anomaly detector, a residual network traffic signal based on the cyclic component and the detrended network traffic signal;

detecting, by the anomaly detector, an anomaly in the residual network traffic signal based on at least one of an amplitude-based anomaly detection algorithm or a statistics-based anomaly detection algorithm; and

reconfiguring, by the anomaly detector, a network comprising the network node responsive to detecting the anomaly.

2. The method of claim 1, wherein the anomaly corresponds to an amount of data flow larger than a threshold.

3. The method of claim 1, wherein detecting the anomaly comprises detecting the anomaly based on the statistics-based anomaly detection algorithm, comprising:

identifying a characteristic range of a plurality of samples in the residual network traffic signal, wherein at least a subset of the plurality of samples in the residual network traffic signal are within the characteristic range; and

identifying a sample point in the residual network traffic signal outside the characteristic range as the anomaly.

4. The method of claim 1, wherein detecting the anomaly comprises detecting the anomaly by based on the amplitude-based anomaly detection algorithm, comprising:

generating a historical probability distribution of the residual network traffic signal based on previously received network traffic signal samples;

computing a likelihood for each sample point in the residual network traffic signal based at least in part on the historical probability distribution;

selecting a likelihood threshold; and

identifying a set of consecutive sample points as the anomaly, wherein each sample point in the set of consecutive sample points has a computed likelihood below the likelihood threshold.

5. The method of claim 1, wherein identifying the trend component of the network traffic signal comprises:

selecting a parameter L, wherein L corresponds to a minimum number of sample points in a linear trend;

appending L consecutive sample points of the network traffic signal to a buffer;

fitting a first curve to sample points in the buffer preceding a sample point in the buffer;

fitting a second curve to sample points in the buffer following the sample point;

computing a probability that a sample point of the sample points is a trend change point based on a deviation between the sample points in the buffer and the fitted first and second curves;

determining that there is a trend change point in the buffer based at least in part on the computed probability; and

identifying the sample point in the buffer as the trend change point based at least in part on the computed probability.

6. The method of claim 1, wherein identifying the trend component of the network traffic signal comprises:

subdividing the network traffic signal into a plurality of signal components, wherein each signal component of the plurality of signal components correspond to a range of frequencies;

selecting a cut-off frequency for identifying a non-linear trend component in the network traffic signal;

identifying a signal component, for each of the plurality of signal components, as the trend subcomponent based on a comparison between the cut-off frequency and an identified frequency associated with the signal component; and

determining the trend component based at least in part on a sum of identified trend subcomponents.

7. The method of claim 1, wherein identifying the cyclic component in the detrended network traffic signal comprises:

selecting a period of the cyclic component;

identifying an index for each sample point in a plurality of sample points in the network traffic signal;

forming a plurality of subsets of sample points, wherein each subset of sample points is associated with a respective remainder value less than the period of the cyclic component;

sorting each sample point in the plurality of sample points to one of the subsets based on a remainder of the index of the respective sample point divided by the period;

computing, for each subset of sample points, a value associated with the respective subset; and

determining the cyclic component by ordering the computed values according to the associated remainder values.

8. The method of claim 1, wherein reconfiguring the network comprising the network node comprises altering a size of a buffer at the network node.

9. The method of claim 1, wherein reconfiguring the network comprising the network node comprises replacing a first buffer at the network node with a second buffer at the network node, a size of the second buffer greater than a size of the first buffer.

10. An apparatus for detecting anomalies in a discrete signal from network traffic flow, comprising:

a non-transitory memory;

a processor for;

receiving a network traffic signal comprising discretized samples corresponding to data packets arriving at a network node within a sampled time interval;

identifying a trend component of the network traffic signal, the trend component corresponding to frequency components of the network traffic signal below a first cut-off frequency threshold;

calculating a detrended network traffic signal based on the trend component and the network traffic signal;

identifying a cyclic component in the detrended network traffic signal, the cyclic component corresponding to frequency components of the detrended network traffic signal above a second cut-off frequency, the second cut-off frequency greater than the first cut-off frequency;

calculating, by the anomaly detector, a residual network traffic signal based on the cyclic component and the detrended network traffic signal;

detecting an anomaly in the residual network traffic signal based on at least one of an amplitude-based anomaly detection algorithm or a statistics-based anomaly detection algorithm; and

reconfiguring, by the anomaly detector, a network comprising the network node responsive to detecting the anomaly.

11. The apparatus of claim 10, wherein the anomaly corresponds to an amount of data flow larger than a threshold.

12. The apparatus of claim 10, wherein detecting the anomaly comprises detecting the anomaly based on the statistics-based anomaly detection algorithm, comprising:

identifying a characteristic range of a plurality of samples in the residual network traffic signal, wherein at least a subset of the plurality of samples in the residual network traffic signal are within the characteristic range; and

identifying a sample point in the residual network traffic signal outside the characteristic range as the anomaly.

13. The apparatus of claim 10, wherein detecting the anomaly comprises detecting the anomaly by based on the amplitude-based anomaly detection algorithm, comprising:

generating a historical probability distribution of the residual network traffic signal based on previously received network traffic signal samples;

computing a likelihood for each sample point in the residual network traffic signal based at least in part on the historical probability distribution;

selecting a likelihood threshold; and

identifying a set of consecutive sample points as the anomaly, wherein each sample point in the set of consecutive sample points has a computed likelihood below the likelihood threshold.

14. The apparatus of claim 10, wherein identifying the trend component of the network traffic signal comprises:

selecting a parameter L, wherein L corresponds to a minimum number of sample points in a linear trend;

appending L consecutive sample points of the network traffic signal to a buffer;

fitting a first curve to sample points in the buffer preceding a sample point in the buffer;

fitting a second curve to sample points in the buffer following the sample point;

computing a probability that a sample point of the sample points is a trend change point based on a deviation between the sample points in the buffer and the fitted first and second curves;

determining that there is a trend change point in the buffer based at least in part on the computed probability; and

identifying the sample point in the buffer as the trend change point based at least in part on the computed probability.

15. The apparatus of claim 10, wherein identifying the trend component of the network traffic signal comprises:

subdividing the network traffic signal into a plurality of signal components, wherein each signal component of the plurality of signal components correspond to a range of frequencies;

selecting a cut-off frequency for identifying a non-linear trend component in the network traffic signal;

identifying a signal component, for each of the plurality of signal components, as the trend subcomponent based on a comparison between the cut-off frequency and an identified frequency associated with the signal component; and

determining the trend component based at least in part on a sum of identified trend subcomponents.

16. The apparatus of claim 10, wherein identifying the cyclic component in the detrended network traffic signal comprises:

selecting a period of the cyclic component;

identifying an index for each sample point in a plurality of sample points in the network traffic signal;

forming a plurality of subsets of sample points, wherein each subset of sample points is associated with a respective remainder value less than the period of the cyclic component;

sorting each sample point in the plurality of sample points to one of the subsets based on a remainder of the index of the respective sample point divided by the period;

computing, for each subset of sample points, a value associated with the respective subset; and

determining the cyclic component by ordering the computed values according to the associated remainder values.

17. The apparatus of claim 10, wherein reconfiguring the network comprising the network node comprises altering a size of a buffer at the network node.

18. The apparatus of claim 10, wherein reconfiguring the network comprising the network node comprises replacing a first buffer at the network node with a second buffer at the network node, a size of the second buffer greater than a size of the first buffer.