Graph-based anomaly detection

ABSTRACT

Anomaly detection is an area that has received much attention in recent years. It has a wide variety of applications, including fraud detection and network intrusion detection. A good deal of research has been performed in this area, often using strings or attribute-value data as the medium from which anomalies are to be extracted. Little work, however, has focused on anomaly detection in graph-based data. In this paper, we introduce two techniques for graph-based anomaly detection. In addition, we introduce a new method for calculating the regularity of a graph, with applications to anomaly detection. We hypothesize that these methods will prove useful both for finding anomalies, and for determining the likelihood of successful anomaly detection within graph-based data. We provide experimental results using both real-world network intrusion data and artificially-created data.

REFERENCES

• 1: Diane J. Cook , Lawrence B. Holder, Graph-Based Data Mining, IEEE Intelligent Systems, v.15 n.2, p.32-41, March 2000 [doi>10.1109/5254.850825]
• 2: Wenke Lee , Dong Xiang, Information-Theoretic Measures for Anomaly Detection, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.130, May 14-16, 2001
• 3: Roy A. Maxion , Kymie M. C. Tan, Benchmarking Anomaly-Based Detection Systems, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.623-630, June 25-28, 2000
• 4: Miller, G. A. Note on the Bias of Information Estimates. Information Theory in Psychology: Problems and Methods, Free Press, 1955.
• 5: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 6: http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html

INDEX TERMS

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

Keywords:
anomaly detection, data mining, graph regularity