Statistics-based anomaly detection

Patent metadata

Field	Value
Publication number	US-9628499-B1
Application number	US-201213569688-A
Country	US
Kind code	B1
Filing date	Aug 8, 2012
Priority date	Aug 8, 2012
Publication date	Apr 18, 2017
Grant date	Apr 18, 2017

Abstract

Systems and methods are described herein for detecting an anomaly in a discrete signal, where samples in the signal correspond to amounts of data flow in a network within a time interval. The discrete signal is received, and a sequence of likelihoods corresponding to the sample values in the signal is generated. The likelihoods are based at least in part on a historical probability distribution of previously received sample values, and a likelihood is a probability of occurrence of a corresponding sample value in the signal. Likelihood change points are identified in the likelihood sequence, and the discrete signal is segmented into a plurality of segments at samples corresponding to the identified change points. A segment is identified as an anomaly based on a comparison between a statistic of the segment and a statistic of the historical probability distribution.

First claim

The invention claimed is:

1. A method for identifying an anomaly in a signal, comprising:
receiving a discrete signal, having sample values corresponding to amounts of data flow in a network within a time interval;
generating a sequence of likelihoods corresponding to sample values in the signal and based at least in part on a historical probability distribution of previously received sample values corresponding to amounts of data flow in the network, wherein a likelihood is a probability of occurrence of a corresponding sample value in the signal;
identifying likelihood change points in the likelihood sequence by:
selecting a parameter L corresponding to a minimum number of samples in a segment;
appending L consecutive likelihoods to a buffer;
computing a sequence of first sum values of the likelihoods in the buffer;
obtaining a sequence of second sum values;
determining the presence of a change point in the buffer based at least in part on a comparison between the first and second sum values, wherein a plurality of likelihoods preceding the change point have a first statistic value and a plurality of likelihoods following the change point have a second statistic value different from the first statistic value; and
identifying a likelihood in the buffer as a change point based at least in part on the comparison;

segmenting the discrete signal into a plurality of segments at samples corresponding to the identified change points such that a respective one of the samples corresponding to the identified change points is at one of a beginning or an end of each of the plurality of segments;
identifying a segment as an anomaly based on a comparison between a statistic of the segment and a statistic of the historical probability distribution; and
reconfiguring, responsive to identifying the segment as the anomaly, a component of the network.

2. The method of claim 1 , wherein an anomaly is indicative of a deviation in the data flow from standard network operation.

3. The method of claim 1 , wherein the historical probability distribution represents amounts of data flow during standard network operation.

4. The method of claim 1 , wherein:
the first and second statistic values are mean values of the corresponding likelihoods;
the sequence of first sum values is based on a cumulative sum sequence of the likelihoods in the buffer; and
the sequence of second sum values is based on a cumulative sum sequence of randomly reordered likelihoods in the buffer.

5. The method of claim 4 , wherein:
a cumulative sum sequence is computed based on a sequence of differences between the likelihoods and a mean of the likelihoods in the buffer;
a change point is determined to be in the buffer when a maximal absolute first sum value exceeds a maximal absolute second sum value; and
the change point corresponds to the maximal absolute first sum value.

6. The method of claim 1 , wherein:
the first and second statistic values are median values of the corresponding likelihoods; the sequence of first sum values is based on a rank sum sequence of the likelihoods in the buffer;
the sequence of second sum values is based on a rank sum sequence of a linear function; and
the change point is identified as the likelihood corresponding to a first sum value substantially equal to a corresponding second sum value.

7. The method of claim 1 , comprising:
removing samples preceding the identified change point from the buffer; and
appending another L likelihoods to the buffer.

8. The method of claim 1 , wherein the statistic of the segment and the statistic of the historical probability distribution are medians of the corresponding sample values.

9. The method of claim 1 , wherein the component is a network buffer.

10. An apparatus for identifying an anomaly in a signal, comprising a processor and a memory unit storing computer executable instructions that when executed by the processor cause the processor to:
receive a discrete signal, having sample values corresponding to amounts of data flow in a network within a time interval;
generate a sequence of likelihoods corresponding to sample values in the signal and based at least in part on a historical probability distribution of previously received sample values corresponding to amounts of data flow in the network, wherein a likelihood is a probability of occurrence of a corresponding sample value in the signal;
identify likelihood change points in the likelihood sequence, by:
selecting a parameter L corresponding to a minimum number of samples in a segment;
appending L consecutive likelihoods to a buffer;
computing a sequence of first sum values of the likelihoods in the buffer;
obtaining a sequence of second sum values;
determining the presence of a change point in the buffer based at least in part on a comparison between the first and second sum values, wherein a plurality of likelihoods preceding the change point have a first statistic value and a plurality of likelihoods following the change point have a second statistic value different from the first statistic value; and
identifying a likelihood in the buffer as a change point based at least in part on the comparison;

segment the discrete signal into a plurality of segments at samples corresponding to the identified change points such that a respective one of the samples corresponding to the identified change points is at one of a beginning or an end of each of the plurality of segments;
identify a segment as an anomaly based on a comparison between a statistic of the segment and a statistic of the historical probability distribution; and
reconfigure, responsive to identifying the segment as the anomaly, a component of the network.

11. The apparatus of claim 10 , wherein an anomaly is indicative of a deviation in the data flow from standard network operation.

12. The apparatus of claim 10 , wherein the historical probability distribution represents amounts of data flow during standard network operation.

13. The apparatus of claim 10 , wherein:
the first and second statistic values are mean values of the corresponding likelihoods;
the sequence of first sum values is based on a cumulative sum sequence of the likelihoods in the buffer; and
the sequence of second sum values is based on a cumulative sum sequence of randomly reordered likelihoods in the buffer.

14. The apparatus of claim 13 , wherein:
a cumulative sum sequence is computed based on a sequence of differences between the likelihoods and a mean of the likelihoods in the buffer;
a change point is determined to be in the buffer when a maximal absolute first sum value exceeds a maximal absolute second sum value; and
the change point corresponds to the maximal absolute first sum value.

15. The apparatus of claim 10 , wherein:
the first and second statistic values are median values of the corresponding likelihoods; the sequence of first sum values is based on a rank sum sequence of the likelihoods in the buffer;
the sequence of second sum values is based on a rank sum sequence of a linear function; and
the change point is identified as the likelihood corresponding to a first sum value substantially equal to a corresponding second sum value.

16. The apparatus of claim 10 , the instructions causing the processor to:
remove samples preceding the identified change point from the buffer; and
append another L likelihoods to the buffer.

17. The apparatus of claim 10 , wherein the statistic of the segment and the statistic of the historical probability distribution are medians of the corresponding samp

Assignees

• Yu Kevin
• Zhang Xinyi
• Google Inc

Inventors

• Yu Kevin
• Zhang Xinyi

Classifications

• H04L63/1425 Primary

  Traffic logging, e.g. anomaly detection · CPC title

• G06F21/316

  by observing the pattern of computer usage, e.g. typical user behaviour · CPC title

• H04L63/1416

  Event detection, e.g. attack signature detection · CPC title

• G06F21/552

  involving long-term monitoring or reporting · CPC title

• H04L41/0677

  Localisation of faults · CPC title