Detection of Internet Traffic Anomalies Using Sparse Laplacian Component Analysis

We consider the problem of anomaly detection in network traffic. It is a challenging problem because of high-dimensional and noisy nature of network traffic. A popularly used technique is subspace analysis. Principal component analysis (PCA) and its improvements have been applied for subspace analysis. In this work, we take a different approach to determine the subspace, and propose to capture the essence of the traffic using the eigenvectors of graph Laplacian, which we refer as Laplacian components (LCs). Our main contribution is to propose a regression framework to compute LCs followed by its application in anomaly detection. This framework provides much flexibility in incorporating different properties into the LCs, notably LCs with sparse loadings, which we exploit in detail. Furthermore, different from previous work that uses sample graphs to preserve local structure, we advocate modelling with a dual-input feature graph that encodes the correlation of the time series data and prior information. Therefore, the proposed model can readily incorporate the 'physics' of some applications as prior information to improve the analysis. We perform experiments on volume anomaly detection using only link-based traffic measurements. We demonstrate that the proposed model can correctly uncover the essential low-dimensional principal subspace containing the normal Internet traffic and achieve outstanding detection performance.