Unsupervised learning techniques for an intrusion detection system

ABSTRACT

With the continuous evolution of the types of attacks against computer networks, traditional intrusion detection systems, based on pattern matching and static signatures, are increasingly limited by their need of an up-to-date and comprehensive knowledge base. Data mining techniques have been successfully applied in host-based intrusion detection. Applying data mining techniques on raw network data, however, is made difficult by the sheer size of the input; this is usually avoided by discarding the network packet contents.In this paper, we introduce a two-tier architecture to overcome this problem: the first tier is an unsupervised clustering algorithm which reduces the network packets payload to a tractable size. The second tier is a traditional anomaly detection algorithm, whose efficiency is improved by the availability of data on the packet payload content.

REFERENCES

• 1: J. P. Anderson. Computer security threat monitoring and surveillance. Technical report, J. P. Anderson Co., Ft. Washington, Pennsylvania, Apr 1980.
• 2: Tim Bass, Intrusion detection systems and multisensor data fusion, Communications of the ACM, v.43 n.4, p.99-105, April 2000 [doi>10.1145/332051.332079]
• 3: D. Boley, V. Borst, and M. Gini. An unsupervised clustering tool for unstructured data. In IJCAI 99 Int'l Joint Conf. on Artificial Intelligence, Stockholm, Aug 1999.
• 4: T. F. Cox and M. A. A. Cox. Multidimensional Scaling. Monographs on Statistics and Applied Probability. Chapman & Hall, 1995.
• 5: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 6: J. Frank. Artificial intelligence and intrusion detection: Current and future directions. In Proc. of the 17th Nat'l Computer Security Conf., Baltimore, MD, 1994.
• 7: Luc Girardin, An Eye on Network Intruder-Administrator Shootouts, Proceedings of the Workshop on Intrusion Detection and Network Monitoring, p.19-28, April 09-12, 1999
• 8: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 9: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 10: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 11: D. Hawkins. Identification of Outliers. Chapman and Hall, London, 1980.
• 12: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 13: I. T. Jolliffe. Principal Component Analysis. Springer Verlag, 1986.
• 14: K. Kendall. A database of computer attacks for the evaluation of intrusion detection systems. Master's thesis, Massachussets Institute of Technology, 1998.
• 15: Teuvo Kohonen, Self-organizing maps, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 16: K. Labib and R. Vemuri. NSOM: A real-time network-based intrusion detection system using self-organizing maps. Technical report, Dept. of Applied Science, University of California, Davis, 2002.
• 17: Terran Lane , Carla E. Brodley, Temporal sequence learning and data reduction for anomaly detection, ACM Transactions on Information and System Security (TISSEC), v.2 n.3, p.295-331, Aug. 1999 [doi>10.1145/322510.322526]
• 18: R. Larsen. Lanczos bidiagonalization with partial reorthogonalization. PhD thesis, Dept. Computer Science, University of Aarhus, DK-8000 Aarhus C, Denmark, Oct 1998.
• 19: W. Lee and S. Stolfo. Data mining approaches for intrusion detection. In Proc. of the 7th USENIX Security Symp., San Antonio, TX, 1998.
• 20: Wenke Lee , Salvatore J. Stolfo , Kui W. Mok, Mining in a data-flow environment: experience in network intrusion detection, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.114-124, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312212]
• 21: E. A. Levy. Smashing the stack for fun and profit. Phrack magazine, 7(49), Nov 1996.
• 22: P. Lichodzijewski, A. Zincir-Heywood, and M. Heywood. Dynamic intrusion detection using self organizing maps. In 14th Annual Canadian Information Technology Security Symp., May 2002.
• 23: A. Likas, N. Vlassis, and J. J. Verbeek. The global k-means clustering algorithm. Pattern Recognition, 36(2), 2003.
• 24: M. Mahoney and P. Chan. Detecting novel attacks by identifying anomalous network packet headers. Technical Report CS-2001-2, Florida Institute of Technology, 2001.
• 25: Testing Intrusion detection systems: a critique of the 1998 and 1999 DARPA intrusion detection system evaluations as performed by Lincoln Laboratory, ACM Transactions on Information and System Security (TISSEC), v.3 n.4, p.262-294, Nov. 2000 [doi>10.1145/382912.382923]
• 26: P. A. Porras and P. G. Neumann. EMERALD: Event monitoring enabling responses to anomalous live disturbances. In Proc. 20th NIST-NCSC Nat'l Information Systems Security Conf., pages 353--365, 1997.
• 27: T. H. Ptacek and T. N. Newsham. Insertion, evasion, and denial of service: Eluding network intrusion detection. Technical Report T2R-0Y6, Secure Networks, Calgary, Canada, 1998.
• 28: S. Savaresi and D. L. Boley. On the performance of bisecting k-means and PDDP. In Proc. of the 1st SIAM Conf. on Data Mining, pages 1--14, 2001.
• 29: S. Savaresi, D. L. Boley, S. Bittanti, and G. Gazzaniga. Cluster selection in divisive clustering algorithms. In Proc. of the 2nd SIAM Int'l Conf. on Data Mining, pages 299--314, 2002.
• 30: G. Serazzi and S. Zanero. Computer virus propagation models. In M. C. Calzarossa and E. Gelenbe, editors, Tutorials of the 11th IEEE/ACM Int'l Symp. on Modeling, Analysis and Simulation of Computer and Telecom. Systems - MASCOTS 2003. Springer-Verlag, 2003.
• 31: K. M. C. Tan , B. S. Collie, Detection and classification of TCP/IP network services, Proceedings of the 13th Annual Computer Security Applications Conference, p.99, December 08-12, 1997
• 32: 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]
• 33: Calvin Chow, Parzen-Window Network Intrusion Detectors, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 4, p.40385, August 11-15, 2002

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Experimentation, Security

Keywords:
K-means, anomaly detection, intrusion detection, principal direction divisive partitioning, quality of clusters, self-organizing maps, unsupervised clustering