Mining intrusion detection alarms for actionable knowledge

ABSTRACT

In response to attacks against enterprise networks, administrators increasingly deploy intrusion detection systems. These systems monitor hosts, networks, and other resources for signs of security violations. The use of intrusion detection has given rise to another difficult problem, namely the handling of a generally large number of alarms. In this paper, we mine historical alarms to learn how future alarms can be handled more efficiently. First, we investigate episode rules with respect to their suitability in this approach. We report the difficulties encountered and the unexpected insights gained. In addition, we introduce a new conceptual clustering technique, and use it in extensive experiments with real-world data to show that intrusion detection alarms can be handled efficiently by using previously mined knowledge.

REFERENCES

• 1: J. Allen, A. Christie, W. Fithen, J. McHugh, J. Pickel, and E. Stoner. State of the Practice of Intrusion Detection Technologies. Technical report, Carnegie Mellon University, January 2000. http://www.cert.org/archive/pdf/99tr028.pdf.
• 2: Rebecca Gurley Bace, Intrusion detection, Macmillan Publishing Co., Inc., Indianapolis, IN, 1999
• 3: D. Barbará, J. Couto, S. Jajodia, L. Popyack, and N. Wu. ADAM: Detecting Intrusions by Data Mining. In IEEE Workshop on Information Assurance and Security, 2001.
• 4: Daniel Barbara , Sushil Jajodia, Applications of Data Mining in Computer Security, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: D. Barbará, N. Wu, and S. Jajodia. Detecting Novel Network Intrusions Using Bayes Estimators. In First SIAM Int'l Conf. on Data Mining (SDM'01), 2001.
• 6: Steven M. Bellovin, Packets found on an internet, ACM SIGCOMM Computer Communication Review, v.23 n.3, p.26-31, July 1993 [doi>10.1145/174194.174199]
• 7: Gilles Bisson, Conceptual clustering in a first order logic representation, Proceedings of the 10th European conference on Artificial intelligence, p.458-462, August 1992, Vienna, Austria
• 8: E. Bloedorn, B. Hill, A. Christiansen, C. Skorupka, L. Talboot, and J. Tivel. Data Mining for Improving Intrusion Detection, 2000. http://www.mitre.org/support/papers/tech_papers99_00/.
• 9: J. Broderick -- Editor. IBM Outsourced Solution, 1998. http://www.infoworld.com/cgi-bin/displayTC.pl?/980504sb3-ibm.htm.
• 10: P. Chan and S. Stolfo. Toward Scalable Learning with Non-Uniform Class and Cost Distributions: A Case Study in Credit Card Fraud Detection. In 4th Int'l Conf. on Knowledge Discovery and Data Mining, pages 164--168, 1998.
• 11: C. Clifton and G. Gengo. Developing Custom Intrusion Detection Filters Using Data Mining. In Military Communications Int'l Symposium (MILCOM2000), October 2000.
• 12: O. Dain and R. K. Cunningham. Fusing Heterogeneous Alert Streams into Scenarios. In Barbará and Jajodia {4}.
• 13: H. Debar, M. Dacier, and A. Wespi. A Revised Taxonomy for Intrusion Detection Systems. Annales des Télécommunications, 55(7--8):361--378, 2000.
• 14: Hervé Debar , Andreas Wespi, Aggregation and Correlation of Intrusion-Detection Alerts, Proceedings of the 4th International Symposium on Recent Advances in Intrusion Detection, p.85-103, October 10-12, 2001
• 15: Tom Fawcett , Foster Provost, Adaptive Fraud Detection, Data Mining and Knowledge Discovery, v.1 n.3, p.291-316, 1997 [doi>10.1023/A:1009700419189]
• 16: Douglas H. Fisher, Knowledge Acquisition Via Incremental Conceptual Clustering, Machine Learning, v.2 n.2, p.139-172, September 1987 [doi>10.1023/A:1022852608280]
• 17: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, CACTUS—clustering categorical data using summaries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.73-83, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312201]
• 18: M. Carofalakis and R. Rastogi. Data Mining Meets Network Management: The Nemesis Project. In ACM SIGMOD Int'l Workshop on Research Issues in Data Mining and Knowledge Discovery, May 2001.
• 19: A. Gordon. Classification. Chapman and Hall, 1999
• 20: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems, v.25 n.5, p.345-366, July 2000 [doi>10.1016/S0306-4379(00)00022-3]
• 21: J. Han , Y. Cai , N. Cercone, Data-Driven Discovery of Quantitative Rules in Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.29-40, February 1993 [doi>10.1109/69.204089]
• 22: J. Han and Y. Fu. Dynamic Generation and Refinement of Concept Hierarchies for Knowledge Discovery in Databases. In Workshop on Knowledge Discovery in Databases, pages 157--168, 1994.
• 23: Jiawei Han , Yongjian Fu, Attribute-oriented induction in data mining, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 24: P. Hansen, B. Jaumard, and N. Mladenovic. How to Choose K Entries Among N. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 19:105--116, 1995.
• 25: O. Heinonen and H. Mannila. Attribute-Oriented Induction and Conceptual Clustering. Technical Report C-1996-2, University of Helsinki, 1996.
• 26: J. L. Hellerstein and S. Ma. Mining Event Data for Actionable Patterns. In The Computer Measurement Group, 2000.
• 27: Koral Ilgun , R. A. Kemmerer , Phillip A. Porras, State Transition Analysis: A Rule-Based Intrusion Detection Approach, IEEE Transactions on Software Engineering, v.21 n.3, p.181-199, March 1995 [doi>10.1109/32.372146]
• 28: 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]
• 29: H. S. Javitz and A. Valdes. The SRI IDES Statistical Anomaly Detector. In IEEE Symposium on Security and Privacy, Oakland, CA. SRI International, May 1991.
• 30: K. Julisch, Mining Alarm Clusters to Improve Alarm Handling Efficiency, Proceedings of the 17th Annual Computer Security Applications Conference, p.12, December 10-14, 2001
• 31: M. Klemettinen. A Knowledge Discovery Methodology for Telecommunication Network Alarm Data. PhD thesis, University of Helsinky (Finland), 1999.
• 32: Wenke Lee , Salvatore J. Stolfo, A framework for constructing features and models for intrusion detection systems, ACM Transactions on Information and System Security (TISSEC), v.3 n.4, p.227-261, Nov. 2000 [doi>10.1145/382912.382914]
• 33: Stefanos Manganaris , Marvin Christensen , Dan Zerkle , Keith Hermiz, A data mining analysis of RTID alarms, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.34 n.4, p.571-577, Oct. 2000 [doi>10.1016/S1389-1286(00)00138-9]
• 34: H. Mannila and H. Toivonen. Discovering Generalized Episodes Using Minimal Occurences. In 2nd Int'l Conf. on Knowledge Discovery and Data Mining, pages 146--151, 1996.
• 35: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 36: 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
• 37: R. S. Michalski and R. E. Stepp. Automated Construction of Classifications: Conceptual Clustering Versus Numerical Taxonomy. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5(4):396--410, 1983.
• 38: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7]
• 39: Leonard Pitt , Robert E. Reinke, Criteria for Polynomial-Time (Conceptual) Clustering, Machine Learning, v.2 n.4, p.371-396, April 1988 [doi>10.1023/A:1022825229661]
• 40: S. Staniford, J. A. Hoagland, and J. M. McAlerney. Practical Automated Detection of Stealthy Portscans. In ACM Computer and Communications Security IDS Workshop, pages 1--7, 2000.
• 41: Luis Talavera , Javier Béjar, Generality-Based Conceptual Clustering with Probabilistic Concepts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.2, p.196-206, February 2001 [doi>10.1109/34.908969]
• 42: Alfonso Valdes , Keith Skinner, Probabilistic Alert Correlation, Proceedings of the 4th International Symposium on Recent Advances in Intrusion Detection, p.54-68, October 10-12, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Experimentation, Measurement, Security

Keywords:
alarm investigation, conceptual clustering, data mining, episode rules, intrusion detection