Abstract
A majority of attacks on computer systems result from a combination of vulnerabilities exploited by an intruder to break into the system. An Attack Graph is a general formalism used to model security vulnerabilities of a system and all possible sequences of exploits which an intruder can use to achieve a specific goal. Attack Graphs can be constructed automatically using off-the-shelf model-checking tools. However, for real systems, the size and complexity of Attack Graphs greatly exceeds human ability to visualize, understand and analyze. Therefore, it is useful to identify relevant portions of an Attack Graph. To achieve this, we propose a ranking scheme for the states of an Attack Graph. Rank of a state shows its importance based on factors like the probability of an intruder reaching that state. Given a Ranked Attack Graph, the system administrator can concentrate on relevant subgraphs to figure out how to start deploying security measures. We also define a metric of security of the system based on ranks which the system administrator can use to compare Attack Graphs and determine the effectiveness of various defense measures. We present two algorithms to rank states of an Attack Graph based on the probability of an attacker reaching those states. The first algorithm is similar to the PageRank algorithm used by Google to measure importance of web pages on the World Wide Web. It is flexible enough to model a variety of situations, efficiently computable for large sized graphs and offers the possibility of approximations using graph partitioning. The second algorithm ranks individual states based on the reachability probability of an attacker in a random simulation. Finally, we give examples of an application of ranking techniques to multi-stage cyber attacks.
This research was sponsored by the Office of Naval Research under grant no. N00014-01-1-0796, the Army Research Office under grant no. DAAD19-01-1-0485, and the National Science Foundation under grant nos. CNS-0411152, CCF-0429120, and 0433540. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other entity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bianchini, M., Gori, M., Scarselli, F.: Inside pagerank. ACM Transactions on Internet Technology, pp. 92–128 (2005)
Brin, S., Page, L.: Anatomy of a large-scale hypertextual web search engine. In: Proceedings of the 7th International World Wide Web Conference, Brisbane, Australia (1998)
Clarke, E., Grumberg, O., Peled, D.: Model checking. MIT Press, Cambridge (2000)
Dacier, M., Deswarte, Y., Kaaniche, M.: Quantitative assessment of operational security: Models and tools. Technical Report 96493, LAAS (May 1996)
Dawkins, J., Hale, J.: A systematic approach to multi-stage network attack analysis. In: Proceedings of the Second IEEE International Information Assurance Workshop (2004)
Haveliawala, T.: Efficient computation of pagerank. Stanford DB Group Technical Report (1999)
Haveliawala, T., Kamvar, S., Jeh, G.: An analytical comparison of approaches to personalizing pagerank. Stanford University Technical Report (2003)
Jha, S., Sheyner, O., Wing, J.M.: Minimization and reliability analysis of attack graphs. In: CMU CS Technical Report (February 2002)
Jha, S., Sheyner, O., Wing, J.M.: Two formal analyses of attack graphs. In: Proceedings of the 15th IEEE Computer Security Foundations Workshop, Nova Scotia, Canada, pp. 49–63 (June 2002)
Jha, S., Wing, J.M.: Survivability analysis of networked systems. In: 23rd International Conference on Software Engineering (ICSE 2001), p. 0307 (2001)
Kamvar, S., Haveliawala, T., Golub, G.: Adaptive methods for the computation of pagerank. In: Stanford University Technical Report (2003)
Kamvar, S., Haveliawala, T., Manning, C., Golub, G.: Exploiting the block structure of the web for computing pagerank. In: Stanford University Technical Report (2003)
Kamvar, S., Haveliawala, T., Manning, C., Golub, G.: Extrapolation methods for accelerating pagerank computations. In: Proceedings of the Twelfth International World Wide Web Conference (2003)
Kuehlmann, A., McMilan, K.L., Brayton, R.K.: Probabilistic state space search. In: Proceedings of ACM/IEEE international conference on Computer Aided Design (1999)
Langville, A.N., Meyer, C.D.: Deeper inside pagerank. Internet Mathematics, 335–400 (2004)
Lee, C.P.-C., Golub, G.H., Zenios, S.A.: A fast two-stage algorithm for computing pagerank and its extensions. Scientific Computation and Computational Mathematics (2003)
Madan, B.B., Popstojanova, K.G., Vaidyanathan, K., Trivedi, K.S.: A method for modeling and quantifying the security attributes of intrusion tolerant systems. In: Dependable Systems and Networks-Performance and Dependability Symposium, pp. 167–186 (2004)
Noel, S., Jajodia, S.: Managing attack graph complexity through visual hierarchical aggregation. In: Proceedings of the 2004 ACM workshop on Visualization and data mining for computer security, Washington DC, USA (2004)
Ortalo, R., Deshwarte, Y., Kaaniche, M.: Experimenting with quantitative evaluation tools for monitoring operational security. IEEE Transactions on Software Engineering, 633–650 (October 1999)
Phillips, C.A., Swiler, L.P.: A graph-based system for network vulnerability analysis. In: Proceedings of the DARPA Information Survivability Conference and Exposition, pp. 71–79 (June 2000)
Sheyner, O., Haines, J., Jha, S., Lippmann, R., Wing, J.M.: Automated generation and analysis of attack graphs. In: Proceedings of the IEEE Symposium on Security and Privacy, Oakland, CA (May 2002)
Sheyner, O., Wing, J.M.: Tools for generating and analyzing attack graphs. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, W.-P. (eds.) FMCO 2003. LNCS, vol. 3188, pp. 344–371. Springer, Heidelberg (2004)
Staniford, S., Paxson, V., Weaver, N.: How to own the internet in your spare time. In: Proceedings of the 11th USENIX Security symposium (2002)
Zhu, H.F.: The methematical models of computer virus infection and methods of prevention. Mini-Micro Systems (Journal of China Computer Society) 11(7), 14–21 (1990)
Zou, C.C., Towsley, D., Gong, W.: Email virus and worm propagation simulation. In: 13th International conference on Computers Communications and Networks, Chicago (October 2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mehta, V., Bartzis, C., Zhu, H., Clarke, E., Wing, J. (2006). Ranking Attack Graphs. In: Zamboni, D., Kruegel, C. (eds) Recent Advances in Intrusion Detection. RAID 2006. Lecture Notes in Computer Science, vol 4219. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11856214_7
Download citation
DOI: https://doi.org/10.1007/11856214_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-39723-6
Online ISBN: 978-3-540-39725-0
eBook Packages: Computer ScienceComputer Science (R0)