Abstract
Attack graphs have been widely used for attack modeling, alert correlation, and prediction. In order to address the limitations of current approaches – scalability and impact analysis – we propose a novel framework to analyze massive amounts of alerts in real time, and measure the impact of current and future attacks. Our contribution is threefold. First, we introduce the notion of generalized dependency graph, which captures how network components depend on each other, and how the services offered by an enterprise depend on the underlying infrastructure. Second, we extend the classical definition of attack graph with the notion of timespan distribution, which encodes probabilistic knowledge of the attacker’s behavior. Finally, we introduce attack scenario graphs, which combine dependency and attack graphs, bridging the gap between known vulnerabilities and the services that could be ultimately affected by the corresponding exploits. We propose efficient algorithms for both detection and prediction, and show that they scale well for large graphs and large volumes of alerts. We show that, in practice, our approach can provide security analysts with actionable intelligence about the current cyber situation, enabling them to make more informed decisions.
The work presented in this paper is supported in part by the Army Research Office MURI award number W911NF-09-1-0525.
Chapter PDF
Similar content being viewed by others
References
Albanese, M., Chellappa, R., Moscato, V., Picariello, A., Subrahmanian, V.S., Turaga, P., Udrea, O.: A constrained probabilistic petri net framework for human activity detection in video. IEEE Transactions on Multimedia 10(8), 1429–1443 (2008)
Bahl, P., Chandra, R., Greenberg, A., Kandula, S., Maltz, D.A., Zhang, M.: Towards highly reliable enterprise network services via inference of multi-level dependencies. ACM SIGCOMM Computer Communication Review 37, 13–24 (2007)
Bahl, P.V., Barham, P., Black, R., Chandra, R., Goldszmidt, M., Isaacs, R., Kandula, S., Li, L., MacCormick, J., Maltz, D., Mortier, R., Wawrzoniak, M., Zhang, M.: Discovering Dependencies for Network Management. In: Proceedings of the 5th ACM Workshop on Hot Topics in Networking (HotNets) (November 2006)
Chen, X., Zhang, M., Mao, Z.M., Bahl, P.: Automating network application dependency discovery: experiences, limitations, and new solutions. In: Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI 2008, pp. 117–130. USENIX Association, Berkeley (2008)
Dain, O., Cunningham, R.K.: Fusing a heterogeneous alert stream into scenarios. In: Proceedings of the 2001 ACM Workshop on Data Mining for Security Applications, pp. 1–13 (2001)
Duong, T., Bui, H., Phung, D., Venkatesh, S.: Activity Recognition and Abnormality Detection with the Switching Hidden Semi-Markov Model. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2005), vol. 1, pp. 838–845 (2005)
Golab, L., Özsu, M.T.: Issues in data stream management. SIGMOD Record 32, 5–14 (2003)
Habra, N., Charlier, B., Mounji, A., Mathieu, I.: Asax: Software architecture and rule-based language for universal audit trail analysis. In: Deswarte, Y., Eizenberg, G., Quisquater, J.-J. (eds.) ESORICS 1992. LNCS, vol. 648, pp. 435–450. Springer, Heidelberg (1992)
Hamid, R., Huang, Y., Essa, I.: ARGMode Activity Recognition Using Graphical Models. In: Proceedings of the IEEE Computer Society International Conference on Computer Vision and Pattern Recognition (CVPR 2003), vol. 3, pp. 38–43 (2003)
Ingols, K., Lippmann, R., Piwowarski, K.: Practical attack graph generation for network defense. In: Proceedings of 22nd Annual Computer Security Applications Conference (ACSAC 2006), pp. 121–130. IEEE Computer Society, Los Alamitos (2006)
Jajodia, S., Noel, S.: Topological Vulnerability Analysis. In: Cyber Situational Awareness: Issues and Research. Advances in Information Security, vol. 46, pp. 139–154. Springer, Heidelberg (2009)
Kandula, S., Chandra, R., Katabi, D.: What’s going on?: learning communication rules in edge networks. ACM SIGCOMM Computer Communication Review 38, 87–98 (2008)
Kheir, N., Cuppens-Boulahia, N., Cuppens, F., Debar, H.: A service dependency model for cost-sensitive intrusion response. In: Gritzalis, D., Preneel, B., Theoharidou, M. (eds.) ESORICS 2010. LNCS, vol. 6345, pp. 626–642. Springer, Heidelberg (2010)
Lamport, L.: Distributed system (May 1987), http://research.microsoft.com/enus/um/people/lamport/pubs/distributed-system.txt
Leversage, D.J., Byres, E.J.: Estimating a system’s mean time-to-compromise. IEEE Security and Privacy 6, 52–60 (2008)
Mörchen, F.: Unsupervised pattern mining from symbolic temporal data. SIGKDD Explorations Newsletter 9(1), 41–55 (2007)
Ning, P., Xu, D.: Learning attack strategies from intrusion alerts. In: Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS 2003), pp. 200–209 (2003)
Ning, P., Xu, D., Healey, C.G., Amant, R.S.: Building attack scenarios through integration of complementary alert correlation methods. In: Proceedings of the 11th Annual Network and Distributed System Symposium (NDSS 2004), pp. 97–111 (2004)
Noel, S., Robertson, E., Jajodia, S.: Correlating intrusion events and building attack scenarios through attack graph distances. In: Proceedings of the 20th Annual Computer Security Applications Conference (ACSAC 2004), pp. 350–359 (2004)
Qin, X., Lee, W.: Statistical causality analysis of INFOSEC alert data. In: Vigna, G., Krügel, C., Jonsson, E. (eds.) RAID 2003. LNCS, vol. 2820, pp. 73–93. Springer, Heidelberg (2003)
Valdes, A., Skinner, K.: Probabilistic alert correlation. In: Lee, W., Mé, L., Wespi, A. (eds.) RAID 2001. LNCS, vol. 2212, pp. 54–68. Springer, Heidelberg (2001)
Wang, L., Liu, A., Jajodia, S.: Using attack graphs for correlating, hypothesizing, and predicting intrusion alerts. Computer Communications 29(15), 2917–2933 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Albanese, M., Jajodia, S., Pugliese, A., Subrahmanian, V.S. (2011). Scalable Analysis of Attack Scenarios. In: Atluri, V., Diaz, C. (eds) Computer Security – ESORICS 2011. ESORICS 2011. Lecture Notes in Computer Science, vol 6879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23822-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-23822-2_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23821-5
Online ISBN: 978-3-642-23822-2
eBook Packages: Computer ScienceComputer Science (R0)