Online Internet Anomaly Detection with High Accuracy: A Fast Tensor Factorization Solution

Traffic anomaly detection is critical for advanced Internet management. Existing detection algorithms usually work off-line and cannot timely detect anomalies. They also suffer from high cost for storage and computation. Although online and accurate traffic anomaly detection is very important, it very difficult to achieve. We propose to utilize tensor model to well exploit the multi-dimensional information hidden in the traffic data for more accurate online Internet anomaly detection. We decouple the tensor recovery problem to iteratively solve two sub problems, a tensor factorization sub-problem and an anomaly detection sub-problem. To reduce the high cost for computation and storage involved in tensor factorization, we propose two lightweight techniques to effectively derive factor matrices of tensor in the current window and iteration, taking advantage of tensor decomposition results of the previous window and iteration. We have done extensive experiments using two real traffic traces to compare with three tensor based algorithms and three matrix based algorithms. The experiment results demonstrate that our online anomaly detection algorithm can achieve the same anomaly detection accuracy as that of the best offline tensor based algorithm, but at 6100 times faster speed and with very low storage cost.