Abstract
This paper presents and analyzes an attack graph optimization problem that arises in modeling certain adversarial cyber attack and defend scenarios. The problem formulation is based on representing attacks againt a system as a finite, weighted, directed graph in which the directed edges represent transitions between states in an attack and edge weights represent the estimated cost to an attacker for traversing the edge. An attacker strives to traverse the graph from a specified start node to a specified end node using the least weight cost directed path between those nodes. On the other hand, the defender seeks to allocate defensive measures in such a way as to maximize the attacker’s minimal cost attack path. We study the role that minimal cut sets play in hardening the attack graph and prove that under this simple model minimal cut sets are optimal defensive investments in the limit even though minimal cut sets may not play a role in hardening a system initially. Viewing attackers and defenders as players in a two person, non-zero sum game, the results in this paper describe the asyptotic behavior of optimal solutions to the game under certain conditions.
Supported by the US Army Research Office (ARO) MURI grant W911NF-13-1-0421.
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
Similar content being viewed by others
Notes
- 1.
Although Bruce Schneier originally introduced the concept of “attack trees” [8], by adding a start node connected to the leaves of all the nodes in the tree, the tree trivially becomes an acyclic directed graph and therefore an attack graph in our sense of the term.
References
Carin, L., Cybenko, G., Hughes, J.: Cybersecurity strategies: the QuERIES methodology. Computer 41(8), 20–26 (2008)
Fulkerson, D.R., Harding, G.C.: Maximizing the minimum source-sink path subject to a budget constraint. Math. Program. 13, 116–118 (1977). https://doi.org/10.1007/BF01584329
Golden, B.: A problem in network interdiction. Naval Res. Logist. Quarter. 25(4), 711–713 (1978)
Israeli, E., Wood, R.K.: Shortest-path network interdiction. Networks 40(2), 97–111 (2002). https://doi.org/10.1002/net.10039
Menger, K.: Zur allgemeinen kurventheorie. Fundam. Math. 10(1), 96–115 (1927)
Noel, S., Jajodia, S., O’Berry, B., Jacobs, M.: Efficient minimum-cost network hardening via exploit dependency graphs. In: Proceedings of 19th Annual Computer Security Applications Conference, pp. 86–95. IEEE (2003)
Noel, S.E., Jajodia, S., O’Berry, B.C., Jacobs, M.A.: Minimum-cost network hardening. US Patent 7,555,778, 30 June 2009
Schneier, B.: Attack trees. Dr. Dobb’s J. 24(12), 21–29 (1999)
Schudel, G., Wood, B.: Adversary work factor as a metric for information assurance. In: Proceedings of the 2000 Workshop on New Security Paradigms, pp. 23–30. ACM (2001)
Sheyner, O., Haines, J., Jha, S., Lippmann, R., Wing, J.M.: Automated generation and analysis of attack graphs. In: Proceedings of the 2002 IEEE Symposium on Security and Privacy, pp. 273–284. IEEE (2002)
Wang, L., Noel, S., Jajodia, S.: Minimum-cost network hardening using attack graphs. Comput. Commun. 29(18), 3812–3824 (2006)
West, D.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Cybenko, G., Stocco, G.F. (2018). Asymptotic Behavior of Attack Graph Games. In: Samarati, P., Ray, I., Ray, I. (eds) From Database to Cyber Security. Lecture Notes in Computer Science(), vol 11170. Springer, Cham. https://doi.org/10.1007/978-3-030-04834-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-04834-1_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04833-4
Online ISBN: 978-3-030-04834-1
eBook Packages: Computer ScienceComputer Science (R0)