Security Games with Layered Defenses: Adaptive Adversaries and Gittins Indices

Abstract

Real-world security applications (e.g., cybersecurity) often involve multiple attack paths, each with layers of defenses that an attacker needs to sequentially overcome before a successful attack on the entire system. Each defensive resource changes dynamically in efficacy as the attack unfolds. In this paper, we study the case where attackers are adaptive, potentially switching paths over time in response to these changes with the goal to minimize the expected time until a successful attack. We formalize this as a min-max game and give examples where adaptive attackers are more powerful than non-adaptive ones. We show that defenses that do not account for adaptivity can perform arbitrarily worse. A connection between the attacker's optimal strategy with the classical theory of multi-armed bandits and the Gittins index is made, yielding a simple gradient based algorithm to solve our proposed min-max game. Experiments on synthetic settings validate our approach.