COMPUTER NETWORKS RESEARCH LAB

TSP Lab

Department of Electrical and Computer Engineering, McGill University

  NAVIGATION

Home
People
Photos
 

  RESEARCH

Projects
Publications
 

  LINKS

AAPN
MITACS
McGill TSP
McGill ECE
 

  LOCAL ACCESS
Local Info
 
 

Project Description Return to Network Monitoring Projects

Detailed Description of Algorithm
Result Snapshots and Sample Code
References
Related Publications

   
Online Sequential Diagnosis of Network Anomalies
 

Student: Tarem Ahmed, Ph.D. Student
Supervisor: Prof. Mark Coates

Description: High-speed backbones are regularly affected by network anomalies generated by a wide range of sources, from malicious denial-of-service attacks and viruses to harmless large data transfers and accidental equipment failures.  Different types of anomalies affect the network in different ways, and it is difficult to know a priori how a potential anomaly will exhibit itself in traffic statistics.

The goal of this project is to develop sequential, learning algorithms for anomaly detection that are suitable for online use with multivariate data.  Most prior work in anomaly detection has used block-based methods such as Principal Component Analysis (PCA), which are only suitable for offline applications, requiring waits of up to hours before alerts occur [1-2].

We suggest an alternative approach and propose an online, recursive algorithm that detects anomalies in multivariate network-wide data within minutes.  We propose a Kernel-based Online Anomaly Detection (KOAD) algorithm that assumes no prior model for normal or anomalous network traffic.  Instead, it sequentially builds up a dictionary of features that approximately spans the subspace of normal network behaviour.  The dictionary is dynamic, and it adapts to variations in the structure of normal traffic itself. The algorithm then raises an alarm immediately upon encountering a deviation from the norm.

 

What is a Network Anomaly?

An anomaly is understood to have occurred when traffic patterns in a network experience a sudden deviation from usual behaviour. An example of an anomaly observed in the NYC core router in the Abilene backbone network appears below.


Fig. 1: (a) Total number of packets per second in the network remains fairly constant over this time interval.  However, (b) there is a drastic change in the distribution of source IPs within a particular flow at t = 2016, compared to t = 2014 and t = 2018.  This means that some network anomaly occurred at t = 2016.  This kind of behaviour is often observed during port scans and denial-of-service attacks.