Eigenspace-based anomaly detection in computer systems

ABSTRACT

We report on an automated runtime anomaly detection method at the application layer of multi-node computer systems. Although several network management systems are available in the market, none of them have sufficient capabilities to detect faults in multi-tier Web-based systems with redundancy. We model a Web-based system as a weighted graph, where each node represents a "service" and each edge represents a dependency between services. Since the edge weights vary greatly over time, the problem we address is that of anomaly detection from a time sequence of graphs.In our method, we first extract a feature vector from the adjacency matrix that represents the activities of all of the services. The heart of our method is to use the principal eigenvector of the eigenclusters of the graph. Then we derive a probability distribution for an anomaly measure defined for a time-series of directional data derived from the graph sequence. Given a critical probability, the threshold value is adaptively updated using a novel online algorithm.We demonstrate that a fault in a Web application can be automatically detected and the faulty services are identified without using detailed knowledge of the behavior of the system.

REFERENCES

• 1: Arindam Banerjee , Inderjit Dhillon , Joydeep Ghosh , Suvrit Sra, Generative model-based clustering of directional data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956757]
• 2: Paul Barford , Jeffery Kline , David Plonka , Amos Ron, A signal analysis of network traffic anomalies, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637210]
• 3: A. Berman and R. J. Plemmons. Nonnegative Matrices in the Mathematical Sciences, volume 9 of Classics in applied mathematics. SIAM, 1994.
• 4: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 5: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha, A spectral method to separate disconnected and nearly-disconnected web graph components, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.275-280, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502551]
• 6: A. G. Ganek , T. A. Corbi, The dawning of the autonomic computing era, IBM Systems Journal, v.42 n.1, p.5-18, January 2003
• 7: M. Gupta, A. Neogi, M. K. Agarwal, and G. Kar. Discovering dynamic dependencies in enterprise environments for problem determination. In Proceedings of 14th IFIP/IEEE Workshop on Distributed Systems: Operations and Management, pages 221--233, 2003.
• 8: H. Hajji. Baselining network traffic and online faults detection. In Proceedings of IEEE International Conference on Communications, volume 1, pages 301--308, 2003.
• 9: John Hopcroft , Omar Khan , Brian Kulis , Bart Selman, Natural communities in large linked networks, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956816]
• 10: Jun Huan , Wei Wang , Jan Prins, Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, Proceedings of the Third IEEE International Conference on Data Mining, p.549, November 19-22, 2003
• 11: IBM. Trade3; http://www-306.ibm.com/software/webservers/appserv/benchmark3.html.
• 12: Akihiro Inokuchi , Hisashi Kashima, Mining Significant Pairs of Patterns from Graph Structures with Class Labels, Proceedings of the Third IEEE International Conference on Data Mining, p.83, November 19-22, 2003
• 13: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, Complete Mining of Frequent Patterns from Graphs: Mining Graph Data, Machine Learning, v.50 n.3, p.321-354, March 2003 [doi>10.1023/A:1021726221443 ]
• 14: Michihiro Kuramochi , George Karypis, Discovering Frequent Geometric Subgraphs, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.258, December 09-12, 2002
• 15: A. Y. Ng, A. X. Zheng, and M. I. Jordan. Link analysis, eigenvectors and stability. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 903--910, 2001.
• 16: Caleb C. Noble , Diane J. Cook, Graph-based anomaly detection, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956831]
• 17: Sudeep Sarkar , Kim L. Boyer, Quantitative measures of change based on feature organization: eigenvalues and eigenvectors, Computer Vision and Image Understanding, v.71 n.1, p.110-136, July 1, 1998 [doi>10.1006/cviu.1997.0637 ]
• 18: G. Strang. Linear Algebra and its Applications. Academic Press, 1976.
• 19: The Open Group. Application response measurement --- ARM; http://www.opengroup.org/tech/management/arm/.
• 20: M. Thottan and C. Ji. Anomaly detection in IP networks. IEEE Transactions on Signal Processing, 51(8):2191-- 2204, 2003.
• 21: H. Wang, D. Zhang, and K. G.Shin. Detecting SYN flooding attacks. In Proceedings IEEE INFOCOM 2002, pages 1530 --1539, 2002.
• 22: Takashi Washio , Hiroshi Motoda, State of the art of graph-based data mining, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959249]
• 23: 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]
• 24: Kenji Yamanishi , Jun-Ichi Takeuchi , Graham Williams , Peter Milne, On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.320-324, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347160]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

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

General Terms:
Algorithms, Management

Keywords:
Perron-Frobenius theorem, principal eigenvector, singular value decomposition, time sequence of graphs, von Mises-Fisher distribution