Learning attack strategies from intrusion alerts

ABSTRACT

Understanding strategies of attacks is crucial for security applications such as computer and network forensics, intrusion response, and prevention of future attacks. This paper presents techniques to automatically learn attack strategies from correlated intrusion alerts. Central to these techniques is a model that represents an attack strategy as a graph of attacks with constraints on the attack attributes and the temporal order among these attacks. To learn the intrusion strategy is then to extract such a graph from a sequences of intrusion alerts. To further facilitate the analysis of attack strategies, which is essential to many security applications such as computer and network forensics, this paper presents techniques to measure the similarity between attack strategies. The basic idea is to reduces the similarity measurement of attack strategies into error-tolerant graph/subgraph isomorphism problem, and measures the similarity between attack strategies in terms of the cost to transform one strategy into another. Finally, this paper presents some experimental results, which demonstrate the potential of the proposed techniques.

REFERENCES

• 1: Paul Ammann , Duminda Wijesekera , Saket Kaushik, Scalable, graph-based network vulnerability analysis, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586140]
• 2: AT& T Research Labs. Graphviz - open source graph layout and drawing software. http://www.research.att.com/sw/tools/graphviz/.
• 3: Horst Bunke , Kim Shearer, A graph distance metric based on the maximal common subgraph, Pattern Recognition Letters, v.19 n.3-4, p.255-259, March 1998 [doi>10.1016/S0167-8655(97)00179-7]
• 4: CERT Coordination Center. Cert advisory CA-2001-10 buffer overflow vulnerability in microsoft IIS 5.0.
• 5: Microsoft Corporation. Microsoft security bulletin (ms00-029). 2000.
• 6: Microsoft Corporation. Microsoft security bulletin (ms00-078). 2000.
• 7: Microsoft Corporation. Microsoft security bulletin (ms01-023). 2001.
• 8: F. Cuppens, Managing Alerts in a Multi-Intrusion Detection Environment, Proceedings of the 17th Annual Computer Security Applications Conference, p.22, December 10-14, 2001
• 9: Frédéric Cuppens , Alexandre Miège, Alert Correlation in a Cooperative Intrusion Detection Framework, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.202, May 12-15, 2002
• 10: Frédéric Cuppens , Rodolphe Ortalo, LAMBDA: A Language to Model a Database for Detection of Attacks, Proceedings of the Third International Workshop on Recent Advances in Intrusion Detection, p.197-216, October 02-04, 2000
• 11: O. Dain and R.K. Cunningham. Building scenarios from a heterogeneous alert stream. In Proc. of the 2001 IEEE Workshop on Info. Assurance and Security, 2001.
• 12: 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
• 13: Steven T. Eckmann , Giovanni Vigna , Richard A. Kemmerer, STATL: an attack language for state-based intrusion detection, Journal of Computer Security, v.10 n.1-2, p.71-103, 2002
• 14: Fyodor. Nmap free security scanner. http://www.insecure.org/nmap, 2003.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: Internet Security Systems. RealSecure intrusion detection system. http://www.iss.net.
• 17: D. A. Jackson, K. M. Somers, and H. H. Harvey. Similarity coefficients: Measures of co-occurence and association or simply measures of occurrence? The American Naturalist, 133(3):436--453, March 1989.
• 18: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 19: S. Jha , O. Sheyner , J. Wing, Two Formal Analys s of Attack Graphs, Proceedings of the 15th IEEE Computer Security Foundations Workshop (CSFW'02), p.49, June 24-26, 2002
• 20: 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
• 21: B. T. Messmer. Efficient Graph Matching Algorithms for Preprocessed Model Graphs. PhD thesis, University of Bern, Switzerland, November 1995.
• 22: Bruno T. Messmer , Horst Bunke, A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.493-504, May 1998 [doi>10.1109/34.682179]
• 23: Bruno T. Messmer , Horst Bunke, Efficient Subgraph Isomorphism Detection: A Decomposition Approach, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.307-323, March 2000 [doi>10.1109/69.842269]
• 24: B.T. Messmer and H. Bunke. A decision tree approach to graph and subgraph isomorphism detection. Pattern Recognition, 32(12):1979--1998, 1999.
• 25: MIT Lincoln Lab. 2000 DARPA intrusion detection scenario specific datasets. http://www.ll.mit.edu/IST/ideval/data/2000/2000_data_index.html.
• 26: B. Morin, L. Me, H. Debar, and M. Ducasse. M2D2: A formal data model for IDS alert correlation. In Proc. of RAID 2002, 2002.
• 27: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 28: P. Ning and Y. Cui. Intrusion alert correlator (version 0.2). http://discovery.csc.ncsu.edu/software/correlator/ver0.2/iac.html, 2002.
• 29: Peng Ning , Yun Cui , Douglas S. Reeves, Constructing attack scenarios through correlation of intrusion alerts, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586144]
• 30: P. Ning and D. Xu. Learning attack stratagies from intrusion alerts. TR-2003-16, Dept. of Comp. Sci., NCSU, 2003.
• 31: Packet storm. http://packetstormsecurity.nl. Accessed on April 30, 2003.
• 32: P.A. Porras, M.W. Fong, and A. Valdes. A mission impact based approach to INFOSEC alarm correlation. In Proc. of RAID 2002, pages 95--114, 2002.
• 33: C. R. Ramakrishnan , R. Sekar, Model-based analysis of configuration vulnerabilities, Journal of Computer Security, v.10 n.1-2, p.189-209, 2002
• 34: Martin Roesch, Snort - Lightweight Intrusion Detection for Networks, Proceedings of the 13th USENIX conference on System administration, November 07-12, 1999, Seattle, Washington
• 35: Oleg Sheyner , Joshua Haines , Somesh Jha , Richard Lippmann , Jeannette M. Wing, Automated Generation and Analysis of Attack Graphs, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.273, May 12-15, 2002
• 36: Stuart Staniford , James A. Hoagland , Joseph M. McAlerney, Practical automated detection of stealthy portscans, Journal of Computer Security, v.10 n.1-2, p.105-136, 2002
• 37: Steven J. Templeton , Karl Levitt, A requires/provides model for computer attacks, Proceedings of the 2000 workshop on New security paradigms, p.31-38, September 18-21, 2000, Ballycotton, County Cork, Ireland [doi>10.1145/366173.366187]
• 38: 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:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

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

General Terms:
Performance, Security

Keywords:
alert correlation, intrusion detection, profiling attack strategies