Intrusion Detection Systems (IDSs) are security tools widely used in computer networks. While they seem to be promising technologies, they pose some serious drawbacks: When utilized in large and high traffic networks, IDSs generate high volumes of low-level alerts which are hardly manageable. Accordingly, there emerged a recent track of security research, focused on alert correlation, which extracts useful and high-level alerts, and helps to make timely decisions when a security breach occurs.
In this paper, we propose an alert correlation system consisting of two major components; first, we introduce an Attack Scenario Extraction Algorithm (ASEA), which mines the stream of alerts for attack scenarios. The ASEA has a relatively good performance, both in speed and memory consumption. Contrary to previous approaches, the ASEA combines both prior knowledge as well as statistical relationships. Second, we propose a Hidden Markov Model (HMM)-based correlation method of intrusion alerts, fired from different IDS sensors across an enterprise. We use HMM to predict the next attack class of the intruder, also known as plan recognition. This component has two advantages:
Firstly, it does not require any usage or modeling of network topology, system vulnerabilities, and system configurations; Secondly, as we perform high-level prediction, the model is more robust against over-fitting. In contrast, other published plan-recognition methods try to predict exactly the next attacker action. We applied our system to DARPA 2000 intrusion detection scenario dataset. The ASEA experiment shows that it can extract attack strategies efficiently. We evaluated our plan-recognition component both with supervised and unsupervised learning techniques using DARPA 2000 dataset. To the best of our knowledge, this is the first unsupervised method in attack plan recognition.
 F. Valeur, G. Vigna, C. Kruegel, and R.A. Kemmerer. A Comprehensive Approach to Intrusion Detection Alert Correlation. IEEE Transactions on Dependable and Secure Computing, 1(3):146-169, 2004.
 T. Pietraszek. Using Adaptive Alert Classification to Reduce False Positives in Intrusion Detection. In Recent Advances in Intrusion Detection, pages 102-124, 2004.
 R. Smith, N. Japkowicz, M. Dondo, and P. Mason. Using Unsupervised Learning for Network Alert Correlation. In Advances in Artificial Intelligence, pages 308-319, 2008.
 B. Morin, L. Mé, H. Debar, and M. Ducassé. M2D2: A Formal Data Model for IDS Alert Correlation. In Proceedings of the 5th International Symposium on Recent Advances in Intrusion Detection, RAID '02, pages 115-137, 2002.
 F. Cuppens and A. Miège. Alert Correlation in a Cooperative Intrusion Detection Framework. In Proceedings of the 2002 IEEE Symposium on Security and Privacy, 2002.
 X. Peng, Y. Zhang, S. Xiao, Z. Wu, J. Cui, L. Chen, and D. Xiao. An Alert Correlation Method Based on Improved Cluster Algorithm. In Proceedings of Computational Intelligence and Industrial Application, PACIIA '08, pages 342-347, 2008.
 W. Li, L. Zhi-tang, L. Jie, and L. Yao. A Novel Algorithm SF for Mining Attack Scenarios Model. In Proceedings of IEEE International Conference on e-Business Engineering, ICEBE '06, pages 55-61, 2006.
 B. Zhu and A.A. Ghorbani. Alert Correlation for Extracting Attack Strategies. International Journal of Network Security, 3(3):244258, 2006.
 S.O. Al-Mamory and H. Zhang. IDS Alerts Correlation Using Grammar-based Approach. Journal in Computer Virology, 2008.
 S.J. Templeton and K. Levitt. A Requires/ Provides Model for Computer Attacks. In Proceedings of New Security Paradigms Workshop, 2000.
 M.S. Shin and K.J. Jeong. An Alert Data Mining Framework for Network-Based Intrusion Detection System. In Proceedings of the 6th International Workshop Information Security Applications, pages 38-53, 2006.
 O. De Vel, N. Liu, T. Caelli, and T.S. Caetano. An Embedded Bayesian Network Hidden Markov Model for Digital Forensics. In Proceedings of the International Conference on Intelligence and Security Informatics, ISI '06, pages 459-465, 2006.
 D. Ourston, S. Matzner, W. Stump, and B. Hopkins. Applications of Hidden Markov Models to Detecting Multi-Stage Network Attacks. In Proceedings of the 36th Annual Hawaii International Conference on System Sciences, HICSS '03, 2003.
 D. Lee, D. Kim, and J. Jung. Multi-Stage Intrusion Detection System Using Hidden Markov Model Algorithm. In Proceedings of the International Conference on Information Science and Security, ICISS '08, pages 72-77, 2008.
 Y. Zhai, P. Ning, P. Iyer, and D.S. Reeves. Reasoning About Complementary Intrusion Evidence. In Proceedings of the 20th Annual Computer Security Applications Conference, ACSAC '04, pages 39-48, 2004.
 A. Ehrenfeucht and J. Mycielski. A Pseudorandom Sequence - How Random Is It? The American Mathematical Monthly, 99:373-375, 1992.
 X. Qin and W. Lee. Attack Plan Recognition and Prediction Using Causal Networks. In Proceedings of the 20th Annual Computer Security Applications Conference, ACSAC '04, pages 370-379, 2004.
 W. Lee and X. Qin. Statistical Causality Analysis of Infosec Alert Data. In Proceedings of the 6th International Symposium on Recent Advances in Intrusion Detection, RAID '03, pages 73-93, 2003.
 Z. Ning and J. Gong. An Intrusion Plan Recognition Algorithm Based on Max-1-Connected Causal Networks. In Proceedings of the 7th International Conference Computational Science, ICCS '07, 2007.
 D.S. Fava, S.R. Byers, and S.J. Yang. Projecting Cyber-attacks Through Variable-Length Markov Models. IEEE Transactions on Information Forensics and Security, 3:359-369, 2008.
 H. Farhady, R. Jalili, and M. Khansari. Attack Plan Recognition Using Markov Model. In Proceedings of the 7th International ISC Conference on Information Security and Cryptology, 2010.
 P. Bahreini, M. AmirHaeri, and R. Jalili. A Probabilistic Approach to Intrusion Alert Correlation. In Proceedings of 5th International ISC Conference on Information Security & Cryptology, 2008.
 A. Valdes and K. Skinner. Probabilistic Alert Correlation. In Proceedings of the 4th International Symposium on Recent Advances in Intrusion Detection, 2001.
 S. K. Harms and J. S. Deogun. Sequential Association Rule Mining with Time Lags. Journal of Intelligent Information Systems, 2004.
 L.R. Rabiner. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Readings in Speech Recognition, 53:267-296, 1990.
 P.R. Cohen, C.R. Perrault, and J.F. Allen. Beyond Question-Answering. Bolt Branek and Newman Inc., 1981.
 T.C. Bell. Text Compression. Prentice Hall PTR, 1990.
 M. Roesch. Snort-Lightweight Intrusion Detection for Networks. In Proceedings of the 13th USENIX Conference on System Administration, 1999.
 MIT Lincoln Laboratory. 2000 DARPA Intrusion Detection Scenario Specific Data Sets, 2000.
 North Carolina State University Cyber Defense Laboratory. TIAA: A Toolkit for Intrusion Alert Analysis, Accessed May 24, 2009. Available from: http://discovery.csc.ncsu.edu/ software/correlator/ver1.0/.
 P. Ning, Y. Cui, and D. Reeves. Analyzing Intensive Intrusion Alerts Via Correlation. In Proceedings of the 5th International Symposium on Recent Advances in Intrusion Detection, RAID'02, pages 74-94, 2002.