Network anomaly detection based on Eigen equation compression

ABSTRACT

This paper addresses the issue of unsupervised network anomaly detection. In recent years, networks have played more and more critical roles. Since their outages cause serious economic losses, it is quite significant to monitor their changes over time and to detect anomalies as early as possible. In this paper, we specifically focus on the management of the whole network. In it, it is important to detect anomalies which make great impact on the whole network, and the other local anomalies should be ignored. Further, when we detect the former anomalies, it is required to localize nodes responsible for them. It is challenging to simultaneously perform the above two tasks taking into account the nonstationarity and strong correlations between nodes.

We propose a network anomaly detection method which resolves the above two tasks in a unified way. The key ideas of the method are: (1)construction of quantities representing feature of a whole network and each node from the same input based on eigen equation compression, and (2)incremental anomalousness scoring based on learning the probability distribution of the quantities.

We demonstrate through the experimental results using two benchmark data sets and a simulation data set that anomalies of a whole network and nodes responsible for them can be detected by the proposed method.

REFERENCES

• 1: Eamonn Keogh , Jessica Lin , Sang-Hee Lee , Helga Van Herle, Finding the most unusual time series subsequence: algorithms and applications, Knowledge and Information Systems, v.11 n.1, p.1-27, December 2006 [doi>10.1007/s10115-006-0034-6]
• 2: Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
• 3: Kenji Yamanishi , Jun-ichi Takeuchi, A unifying framework for detecting outliers and change points from non-stationary time series data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775148]
• 4: Tsuyoshi IDÉ , Hisashi KASHIMA, Eigenspace-based anomaly detection in computer systems, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014102]
• 5: Jimeng Sun , Huiming Qu , Deepayan Chakrabarti , Christos Faloutsos, Neighborhood Formation and Anomaly Detection in Bipartite Graphs, Proceedings of the Fifth IEEE International Conference on Data Mining, p.418-425, November 27-30, 2005 [doi>10.1109/ICDM.2005.103]
• 6: Spiros Papadimitriou , Jimeng Sun , Philip S. Yu, Local Correlation Tracking in Time Series, Proceedings of the Sixth International Conference on Data Mining, p.456-465, December 18-22, 2006 [doi>10.1109/ICDM.2006.99]
• 7: J. Sun, Y. Xie, H. Zhang, and C. Faloutsos. Less is more: Compact matrix decomposition for large sparse graphs. In Proceedings of SIAM SDM2007, 2007.
• 8: Tsuyoshi Idé , Spiros Papadimitriou , Michail Vlachos, Computing Correlation Anomaly Scores Using Stochastic Nearest Neighbors, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.523-528, October 28-31, 2007 [doi>10.1109/ICDM.2007.12]
• 9: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 10: S. R. White. Density matrix formulation for quantum renormalization groups. Physical Review Letters 69, 1992.
• 11: A. K. Gupta and D. K. Nagar. Matrix Variate Distributions. 1999.
• 12: J. N. Bandyopadhyay and S. Jalan. Universality in Complex Networks: Random Matrix Analysis. Physical Review E 76, 026109, 2004.
• 13: E. Keogh and T. Folias. The UCR time series data mining archive. http://www.cs.ucr.edu/~eamonn/TSDMA/index.html. 2002.
• 14: A. L. Barabasi and R. Albert. Emergence of scaling in random networks . Science 286, pp509--512, 1999.
• 15: Kenji Yamanishi , Yuko Maruyama, Dynamic syslog mining for network failure monitoring, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081927]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management

General Terms:
Algorithms, Management

Keywords:
Eigen equation compression, network anomaly detection