Real-Time intrusion detection alert correlation and attack scenario extraction based on the prerequisite consequence approach




Alert correlation systems attempt to discover the relations among alerts produced by one or more intrusion detection systems to determine the attack scenarios and their main motivations. In this paper a new IDS alert correlation method is proposed that can be used to detect attack scenarios in real-time. The proposed method is based on a causal approach due to the strength of causal methods in practice. To provide a picture of the current intrusive activity on the network, we need a real-time alert correlation. Most causal methods can be deployed offline but not in real-time due to time and memory limitations. In the proposed method, the knowledge base of the attack patterns is represented in a graph model called the Causal Relations Graph. In the offline mode, we construct Queue trees related to alerts' probable correlations. In the real-time mode, for each received alert, we can find its correlations with previously received alerts by performing a search only in the corresponding tree. Therefore, the processing time of each alert decreases significantly. In addition, the proposed method is immune to deliberately slowed attacks. To verify the proposed method, it was implemented and tested using DARPA2000 dataset. Experimental results show the correctness of the proposed alert correlation and its efficiency with respect to the running time.


[1] F. Valeur, G. Vigna, C. Kruegel, and R. Kemmerer. A Comprehensive Approach to Intrusion Detection Alert Correlation. IEEE Trans. on Dependable and Secure Computing, 1(3):146-169, July 2004.

[2] F. Cuppens. Managing Alerts in a Multi-Intrusion Detection Environment. In Proceedings of 17th Computer Security Applications Conference, pages 22-31, 2001.

[3] S. Staniford, J.A. Hoagland, and J.M. McAlerney. Practical Automated Detection of Stealthy Portscans. Journal of Computer Security, 10(1-2):105-136, 2002.

[4] A. Valdes and K. Skinner. Probabilistic Alert Correlation. In Proceedings of the 4th Int. Symposium on Recent Advances in Intrusion Detection (RAID 2001), pages 54-68, 2001.

[5] B. Zhu and A. Ghorbani. Alert Correlation for Extracting Attack Strategies. Int. Journal of Network Security, 3(3):244-258, 2006.

[6] S.O. Al-Mamory, H. Zhang, and A.R. Abbas. IDS Alarms Reduction Using Data Mining. In IEEE World Congress on Computational Intelligence, pages 3564-3570, June 2008.

[7] F. Cuppens and R. Ortalo. LAMBDA: A Language to Model a Database for Detection of Attacks. In Proceedings of the 3th Int. Workshop on the Recent Advances in Intrusion Detection (RAID 2000), pages 197-216, June 2008.

[8] S. Eckmann, G. Vigna, and R. Kemmerer. STATL: An Attack Language for State-based Intrusion Detection. Journal of Computer Security, 10(1-2):71-104, 2002.

[9] O. Dain and R. Cunningham. Building Scenarios from a Heterogeneous Alert Stream. In Proceedings of the 2001 IEEE Workshop on Information Assurance and Security, pages 231-235, June 2001.

[10] S.J. Templeton and K. Levitt. A Requires/Provides Model for Computer Attacks. In Proceedings of the 2000 Workshop on New Security Paradigms, pages 31-38, Sep. 2000.

[11] P. Ning, Y. Cui, and D.S. Reeves. Constructing Attack Scenarios through Correlation of Intrusion Alerts. In Proceedings of the 9th ACM Conference on Computer and Communications Security, pages 245-254, Nov. 2002.

[12] D. Xu and P. Ning. Alert Correlation through Triggering Events and Common Resources. In Proceedings of the 20th Annual Computer Security Applications Conference, pages 360-369, Dec. 2004.

[13] F. Cuppens and A. Miege. Alert Correlation in a Cooperative Intrusion Detection Framework. In Proceedings of IEEE Security and Privacy Symposium, pages 202-215, 2002.

[14] H. Farhady, M. Amirhaeri, and M. Khansari. Alert Correlation and Prediction Using Data Mining and HMM. ISeCure - The ISC International Journal of Information Security, 3(2): 77-102, 2011.

[15] L. Wang, A. Liu, and S. Jajodia. Using Attack Graphs for Correlating, Hypothesizing, and Predicting Intrusion Alerts. Journal of Computer Communications, pages 2917-2933, Vol. 29, No. 15, 2006.

[16] J. Zhou, M. Heckman, B. Reynolds, A. Carlson, and M. Bishop. Modeling Network Intrusion Detection Alerts for Correlation. ACM Trans. on Information and System Security, 10(1):1-31, Feb. 2007.

[17] Hanli Ren, Natalia Stakhanova, and Ali A. Ghorbani. An online adaptive approach to alert correlation. In Proceedings of the 7th Int. Conference on Detection of Intrusions and Malware, and Vulnerability Assessment, DIMVA'10, 2010.

[18] D. Xu. Correlation Analysis of Intrusion Alerts. PhD thesis, Department of Computer Science, University of North Carolina State, 2006.

[19] L. Zhaowen, L. Shan, and M. Yan. Real-Time Intrusion Alert Correlation System Based on Pre-requisites and Consequence. In Proceedings of the 6th Int. Conference on Wireless Communications Networking and Mobile Computing (WiCOM), pages 1-5, 2010.

[20] N.K. Pandey, S.K. Gupta, S. Leekha, and J. Zhou. ACML: Capability Based Attack Modeling Language. In Proceedings of 4th Int. Conference on Assurance and Security, pages 147-154, Sep. 2008.

[21] S. Jajodia and S. Noel. Topological Vulnerability Analysis: A Powerful New Approach for Network Attack Prevention, Detection, and Response. In Algorithms, Architectures, and Information Systems Security, B. Bhattacharya, S. Sur-Kolay, S. Nandy, and A. Bagchi (eds.), 2007.

[22] X. Qin and W. Lee. Discovering Novel Attack Strategies from INFOSEC Alerts. In Proceedings of the 9th European Symposium on Research in Computer Security (ESORICS 2004), pages 439-456, Sep. 2004.

[23] S. Zhang, J. Li, X. Chen, and L. Fan. Building Network Attack Graph for Alert Causal Correlation. Journal of Computers and Security, 27(5-6):188-196, Oct. 2008.

[24] P. Ning, Y. Cui, and D.S. Reeves. Techniques and Tools for Analyzing Intrusion Alerts. ACM Trans. on Information and Systems Security, 7(2):274-318, May 2004.