Author:
Abstract
We propose a comprehensive game-theoretic model pertaining to the security of computer networks, specifically addressing the interaction between defenders and attackers. The model incorporates attack graphs to outline potential attacker strategies and defender responses. To account for the attacker's capacity to execute multiple attempts, we introduce a probabilistic element, wherein the success or failure at any arc of the attack graph is treated as stochastic. This characterization gives rise to a multi-stage stochastic network-interdiction problem. In this problem formulation, the defender strategically interdicts a set of arcs in anticipation of the likely actions of the attacker, who, in turn, can make multiple attempts to traverse the network. We mathematically articulate this scenario as a stochastic bilevel mixed-integer program with a "min-max" objective. The defender's aim is to minimize the probability of the attacker's success, while the attacker seeks to maximize the probability of successfully traversing the network across multiple attempts. The defender's stochastic bilevel optimization model is solved using the integer L-shaped method. Upon analyzing the defender's perspective, we observe the anticipated trend that the overall success probability of the attacker diminishes with an increasing level of defense. Notably, in the sensitivity analysis involving relatively small attack graphs, we discover that the optimal defense strategy against a myopic attacker often aligns with that against a non-myopic attacker. Furthermore, in instances where deviations exist, the disparity in performance is generally marginal. However, our findings demonstrate a potential divergence in optimal defense strategies when the available attack paths share numerous common arcs.
Keywords
Abstract
We propose a comprehensive game-theoretic model pertaining to the security of computer networks, specifically addressing the interaction between defenders and attackers. The model incorporates attack graphs to outline potential attacker strategies and defender responses. To account for the attacker's capacity to execute multiple attempts, we introduce a probabilistic element, wherein the success or failure at any arc of the attack graph is treated as stochastic. This characterization gives rise to a multi-stage stochastic network-interdiction problem. In this problem formulation, the defender strategically interdicts a set of arcs in anticipation of the likely actions of the attacker, who, in turn, can make multiple attempts to traverse the network. We mathematically articulate this scenario as a stochastic bilevel mixed-integer program with a "min-max" objective. The defender's aim is to minimize the probability of the attacker's success, while the attacker seeks to maximize the probability of successfully traversing the network across multiple attempts. The defender's stochastic bilevel optimization model is solved using the integer L-shaped method. Upon analyzing the defender's perspective, we observe the anticipated trend that the overall success probability of the attacker diminishes with an increasing level of defense. Notably, in the sensitivity analysis involving relatively small attack graphs, we discover that the optimal defense strategy against a myopic attacker often aligns with that against a non-myopic attacker. Furthermore, in instances where deviations exist, the disparity in performance is generally marginal. However, our findings demonstrate a potential divergence in optimal defense strategies when the available attack paths share numerous common arcs.