Detecting outliers in network traffic time series

• US 8,676,964 B2
• Filed: 11/06/2008
• Issued: 03/18/2014
• Est. Priority Date: 07/31/2008
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Riverbed Technology Incorporated
• Inventors: Gopalan, Prem K., Elverson, Bryan Thomas
• Primary Examiner(s): Serrao, Ranodhi
• Assistant Examiner(s): Hussain, Farrukh
• Application Number:
  US12/266,105
• Publication Number:
  US 20100030544A1
• Time in Patent Office: 1,958 Days
• Field of Search: 709/201, 709/223, 709/224, 370/230.1, 370/235
• US Class Current: 709/224
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/067 using time frame reporting
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 47/127 by using congestion prediction

Abstract

According to an aspect of the invention, a system and method is configured to detect time series outliers in network traffic.

Claims

1. A computer program product residing on a non-transitory computer readable medium for intrusion detection, the computer program product comprising instructions for causing a processor to:

for each of a plurality of multiple different network traffic metrics,

generate a forecast of network traffic using a model, the forecast being based on previously observed network traffic;

generate a prediction interval that extends above and below the forecast of the network traffic, the prediction interval being based on previously observed deviations from predicted network traffic;

compare observed network traffic to the prediction interval;

identify an outlier for the metric if the observed network traffic is outside of the prediction interval during a time period;

compute a count of outliers for the metric that are identified during the time period; and

identify an anomaly in network traffic for the metric only when the computed count of outliers identified for the metric during the time period is greater than or equal to two and the computed count of outliers identified for the metric during the time period exceeds an anomaly threshold for the metric that is greater than or equal to one; and

merge anomalies for each of the multiple different network traffic metrics to identify a single event.

2. The computer program product of claim 1, wherein the computer program product further comprises instructions for causing the processor to provide information about the network traffic at the time of the event to a user.

3. The computer program product of claim 1, wherein the computer program product further comprises instructions for causing the processor to:

generate the forecast using a model that includes at least a first and a second seasonality, the forecast being based on previously observed network traffic at first and second time periods associated with the first and the second seasonality.

4. The computer program product of claim 3, wherein the computer program product further comprises instructions for causing the processor to generate the forecast using a Holt-Winters model having daily and weekly seasonality.

5. The computer program product of claim 3, wherein:

the first seasonality comprises a weekly seasonality;

the first time period comprises a time period one week prior to the time of the observed network traffic;

the second seasonality comprises a daily seasonality; and

the second time period comprises a time period one day prior to the time of the observed network traffic.

6. The computer program product of claim 4, wherein the computer program product further comprises instructions for causing the processor to:

initialize the model used to generate the forecast based on at least two weeks of network traffic data; and

initialize errors used to generate the prediction interval using at least one week of network traffic data.

7. The computer program product of claim 4, wherein the instructions for causing the processor to generate the prediction interval comprise instructions for causing the processor to define a distribution identifying the variance of errors and use the variance to determine the expected variance about a the forecast of network traffic.

8. The computer program product of claim 7, wherein the forecast and the prediction interval are based on network data associated with a sliding window of prior network data.

9. An anomaly detection system, comprising:

a computing device configured to;

for each of a plurality of multiple different network traffic metrics,

generate a forecast of network traffic using a model, the forecast being based on previously observed network traffic;

generate a prediction interval that extends above and below the forecast of the network traffic, the prediction interval being based on previously observed deviations from predicted network traffic;

compare observed network traffic to the prediction interval;

identify an outlier for the metric if the observed network traffic is outside of the prediction interval during a time period;

compute a count of outliers for the metric that are identified during the time period; and

identify an anomaly in network traffic for the metric only when the computed count of outliers identified for the metric during the time period is greater than or equal to two and the computed count of outliers identified for the metric during the time period exceeds an anomaly threshold for the metric that is greater than or equal to one; and

merge identified anomalies for each of the multiple different network traffic metrics to identify a single event.

10. The anomaly detection system of claim 9, wherein the computer device is further configured to:

generate the forecast using a model that includes at least a first and a second seasonality, the forecast being based on previously observed network traffic at first and second time periods associated with the first and the second seasonality.

11. The anomaly detection system of claim 10, wherein the computing device is further configured to generate the forecast using a Holt-Winters model having daily and weekly seasonality.

12. The anomaly detection system of claim 10, wherein:

the first seasonality comprises a weekly seasonality;

the first time period comprises a time period one week prior to the time of the observed network traffic;

the second seasonality comprises a daily seasonality; and

the second time period comprises a time period one day prior to the time of the observed network traffic.

13. The anomaly detection system of claim 11, wherein the computing device is further configured to:

initialize the model used to generate the forecast based on at least two weeks of network traffic data; and

initialize errors used to generate the prediction interval using at least one week of network traffic data.

14. The anomaly detection system of claim 11, wherein the computing device is further configured to define a distribution identifying the variance of errors and use the variance to determine the expected variance about a the forecast of network traffic.

15. A computer implemented method comprising:

for each of a plurality of multiple different network traffic metrics,

generating a forecast of network traffic using a model, the forecast being based on previously observed network traffic;

generating a prediction interval that extends above and below the forecast of the network traffic, the prediction interval being based on previously observed deviations from predicted network traffic;

comparing observed network traffic to the prediction interval;

identifying, by computer, an outlier for the metric if the observed network traffic is outside of the prediction interval during a time period;

computing a count of outliers for the metric that are identified during the time period; and

identifying an anomaly for the metric in network traffic only when the computed count of outliers for the metric identified during the time period is greater than or equal to two and the computed count of outliers identified for the metric during the time period exceeds an anomaly threshold for the metric that is greater than or equal to one; and

merging identified anomalies for each of the multiple different network traffic metrics to identify a single event.

16. The computer implemented method of claim 15, the method further comprising:

generating the forecast using a model that includes at least a first and a second seasonality, the forecast being based on previously observed network traffic at first and second time periods associated with the first and the second seasonality.

17. The computer implemented method of claim 16, further comprising generating the forecast using a Holt-Winters model having daily and weekly seasonality.

18. The computer implemented method of claim 17, further comprising

initializing the model used to generate the forecast based on at least two weeks of network traffic data;

and

initializing errors used to generate the prediction interval using at least one week of network traffic data.

19. The computer implemented method of claim 17, further comprising defining a distribution identifying the variance of errors and use the variance to determine the expected variance about the forecast of network traffic.