Page History

Overview

Wiki MarkupIn this project we study and investigate network anomaly detection algorithms \[1\], \[2\] and \[3\] for Internet Paths. We also develop a _Decision Theoretic Approach_ (DTA) based on our observations regarding the characteristics of the performance-measurement statistics obtained from the [IEPM-BW] project.

To study and compare the algorithms we use the data sets collected by IEPM-BW spanning approximately 2 3 years (i.e. 2006 2005 - 2008). The Internet paths observed were the links between Stanford Linear Accelerator Center (SLAC) and the following sites:

1. University of Toronto, Canada.
2. Deutsches Elektronen-Synchrotron, Germany.
3. Forschungszentrum Karlsruhe, Germany.
4. San Diego Supercomputing Center (SDSC) USA,
5. Oak Ridge National Laboratory (ORNL) USA,
6. European Organization for Nuclear Research (CERN) , Geneva, Switzerland,
7. Forschungszentrum Karlsruhe (FZK) Germany,
8. Deutsches Elektronen-Synchrotron (DESY) Germany,
9. .
10. San Diego Supercomputing Center, USA.
11. Switch, Switzerland.
12. University of Florida, USA.University of Toronto (UTORONTO) Canada and
13. National Laboratory for Particle and Nuclear Physics (TRIUMF) , Canada.
14. Oak Ridge National Laboratory, USA.
15. Budker Institute of Nuclear Physics, Russia.
16. Daresbury Laboratory, United Kingdom.
17. California Institute of Technology - CACR, USA.
18. Istituto Nazionale di Fisica Nucleare, Italy.
19. Czech NREN Operator, Czech Republic.
20. Brookhaven National Laboratory, USA.
21. Argonne National Laboratory, USA.
22. California Institute of Technology - Ultralight, USA.

The topology of the monitoring framework is shown in figure 1.

...

The data sets used in the study may be downloaded from the links listed below. These data sets were collected by the IEPM-BW project and the latest performance statistics may be accessed from here.

Download the complete data archive \[[zip|http://www.slac.stanford.edu/~kalim/event-detection/published-data/published-data.zip] 10 MB\] or \[[7z|http://www.slac.stanford.edu/~kalim/event-detection/published-data/published-data.7z] 8 MB\]

Labeling and Detection Algorithms

To perform a fair comparison between \[1\], \[2\], \[3\] and the proposed DTA we devised a labeling algorithm to identify true anomalies in the data sets. This labeled data was then used to determine the accuracy (true-positive rate), corresponding false-positive rate and the detection delay. The labeling algorithm and the decision theoretic approach for real-time anomaly detection are discussed at length in the research paper. (_The paper will be posted soon_.)
\\

Implementations and Parameter Tuning

The source code of the implementations and the tuning of parameters is discussed below. Please consider two important factors while we discuss the parameters tuning: a) We define an anomalous event as one which significantly varies from the normal behaviour of the Internet Path and the perturbation persists for at least three hours. b) The measurements made by IEPM-BW are at least 45 mins apart.

a) Plateau Algorithm

The Plateau Algorithm takes four input parameters - history buffer length, trigger buffer length, sensitivity and threshold. We define the trigger buffer length to hold observations spanning at least 3 hours (since we define an anomalous event as one that persists for at least 3 hours). Since the measurements made by IEPM are 45 mins apart, we get about 6 observations. We then empirically determine the optimal length of the history buffer to span at least 5 days ~ 240 observations.

We initially define the sensitivity as one (1) and determine the optimal threshold value for each link (i.e. the value with the optimal ratio of true-positives to false positives). As suggested by the authors, this threshold falls between 30%-40%. Finally for the history buffer length, the trigger buffer length and the optimal threshold, we vary the sensitivity to determine the spectrum of the ratio of true-positive rate to false positive rate. Based on the observations we plot the ROC curves as shown in figure 2.

The source code of the implementation is available in [C#|http://www.slac.stanford.edu/~kalim/event-detection/published-src/c-plateau-impl.html] \[[cs|http://www.slac.stanford.edu/~kalim/event-detection/published-src/plateau.cs]\] and [perl|http://www.slac.stanford.edu/~kalim/event-detection/published-src/plateau.pl.html] \[[pl|http://www.slac.stanford.edu/~kalim/event-detection/published-src/plateau.pl]\]

b) Adaptive Fault Detection

Adaptive Fault Detection

c) Kalman Filters

Kalman Filters

d) Decision Theoretic Approach

Decision Theoretic Approach employs four parameters - the desired false positive rate (alpha), the desired detection rate (beta), the history buffer length and the low-pass median filter length.

This algorithm use three parameters one is threshold which is calculated in terms of Alpha and Beta, and other two are buffer lengths (History buffer and n-Tap Median filter). Same scheme is used for this algorithm, such that minimum value of n = 7 is used for n-Tap Median filter with some appropriate value of History buffer. By keeping these values same and changing different values of Alpha and Beta (Threshold) for each dataset ROCs are generated.

([utilityFunctions|http://www.slac.stanford.edu/~kalim/event-detection/published-src/utilityFunctions.pm.html] \[[pm|http://www.slac.stanford.edu/~kalim/event-detection/published-src/utilityFunctions.pm]\]).

References

...

number of measurements made to the following sites from SLAC:

Data Sets

The data sets used in the study may be downloaded from the links listed below. These data sets were collected by the IEPM-BW project

Table 1: Performance measurement statistics compiled by IEPM, as seen from SLAC.

All files with name "filename_raw_dataset.pathchirp" contain the raw data i.e the available bandwidth measurements along with the timestamps which are used in all algorithms.
All files with name "filename_event_file.txt" contain the list of events identified.

Technical Report - Labeling and Comparative Analysis

The technical report titled "A performance evaluation of anomaly detection algorithms for Internet Paths" will be available soon.

Input/Tuning parameters

Plateau Algorithm (PL)

Kalman Filters Method (KF)

Holt Winter's Method (HW)

Adaptive Fault Detector (AFD)

Decision Theoretic Approach (DTA)

ROC Results

Datasets with Gaussian Distributions

Datasets with Weibull Distributions

...