Network anomaly detection based on TCM-KNN algorithm

ABSTRACT

Intrusion detection is a critical component of secure information systems. Network anomaly detection has been an active and difficult research topic in the field of Intrusion Detection for many years. However, it still has some problems unresolved. They include high false alarm rate, difficulties in obtaining exactly clean data for the modeling of normal patterns and the deterioration of detection rate because of some "noisy" data in the training set. In this paper, we propose a novel network anomaly detection method based on improved TCM-KNN (Transductive Confidence Machines for K-Nearest Neighbors) machine learning algorithm. A series of experimental results on the well-known KDD Cup 1999 dataset demonstrate it can effectively detect anomalies with high true positive rate, low false positive rate and high confidence than the state-of-the-art anomaly detection methods. In addition, even interfered by "noisy" data (unclean data), the proposed method is robust and effective. Moreover, it still retains good detection performance after employing feature selection aiming at avoiding the "curse of dimensionality".

REFERENCES

• 1: M. Bykova, S. Ostermann, and B. Tjaden. Detecting network intrusions via a statistical analysis of network packet characteristics. In Proceedings of the 33rd Southeastern Symp. on System Theory (SSST 2001), Athens, IEEE, 2001.
• 2: Dorothy E. Denning, An intrusion-detection model, IEEE Transactions on Software Engineering, v.13 n.2, p.222-232, Feb. 1987 [doi>10.1109/TSE.1987.232894]
• 3: W. Lee, and S. J. Stolfo. Data mining approaches for intrusion detection. In Proceedings of the 1998 USENIX Security Symposium, 1998.
• 4: A. Ghosh, and A. Schwartzbard. A study in using neural networks for anomaly and misuse detection. In Proceedings of the 8th USENIX Security Symposium, 1999.
• 5: Matthew V. Mahoney , Philip K. Chan, Learning nonstationary models of normal network traffic for detecting novel attacks, 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.775102]
• 6: D. Barbara, N. Wu, S. Jajodia. Detecting novel network intrusions using Bayes estimators. First SIAM Conference on Data Mining, Chicago, IL, 2001.
• 7: N. Ye. A markov chain model of temporal behavior for anomaly detection. In Proceedings of the 2000 IEEE Systems, Man, and Cybernetics Information Assurance and Security Workshop, 2000.
• 8: E. Eskin, A. Arnold, M. Prerau, L. Portnoy, and S. Stolfo. A geometric framework for unsupervised anomaly detection: detecting intrusions in unlabeled data. Applications of Data Mining in Computer Security, Kluwer, 2002.
• 9: Alex Gammerman , Volodya Vovk, Prediction algorithms and confidence measures based on algorithmic randomness theory, Theoretical Computer Science, v.287 n.1, p.209-217, 25 September 2002 [doi>10.1016/S0304-3975(02)00100-7]
• 10: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 11: Kostas Proedrou , Ilia Nouretdinov , Volodya Vovk , Alexander Gammerman, Transductive Confidence Machines for Pattern Recognition, Proceedings of the 13th European Conference on Machine Learning, p.381-390, August 19-23, 2002
• 12: Daniel Barbará , Carlotta Domeniconi , James P. Rogers, Detecting outliers using transduction and statistical testing, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150413]
• 13: Knowledge discovery in databases DARPA archive. Task Description. http://www.kdd.ics.uci.edu/databases/kddcup99/task.htm
• 14: John McHugh, The 1998 Lincoln Laboratory IDS Evaluation, Proceedings of the Third International Workshop on Recent Advances in Intrusion Detection, p.145-161, October 02-04, 2000
• 15: R. P. Lippmann, D. J. Fried, I. Graf, J. W. Haines, K. R. Kendall, D. McClung, D. Weber, S. E. Webster, D. Wyschogrod, R. K. Cunningham, and M. A. Zissman. Evaluating intrusion detection systems: The 1998 DARPA off-line intrusion detection evaluation. In DARPA Information Survivability Conference and Exposition (DISCEX), volume 2, 2000, 12--26.
• 16: Huan Liu , Lei Yu, Toward Integrating Feature Selection Algorithms for Classification and Clustering, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.491-502, April 2005 [doi>10.1109/TKDE.2005.66]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

General Terms:
Algorithms, Security

Keywords:
TCM-KNN algorithm, anomaly detection, machine learning, network security