Attack Graphs & Subset Sabotage Games

Issue title: WOA 2022: From Objects to Agents

Guest editors: Angelo Ferrando and Viviana Mascardi

Article type: Research Article

Authors: Catta, Davide^{; *} | Leneutre, Jean | Malvone, Vadim

Affiliations: LTCI, Télécom Paris, Institut Polytechnique de Paris, Paris, France

Correspondence: [*] Corresponding author: Davide Catta, LTCI, Télécom Paris, Institut Polytechnique de Paris, Paris, France. E-mail: [email protected].

Abstract:  We consider an extended version of sabotage games played over Attack Graphs. Such games are two-player zero-sum reachability games between an Attacker and a Defender. This latter player can erase particular subsets of edges of the Attack Graph. To reason about such games we introduce a variant of Sabotage Modal Logic (that we call Subset Sabotage Modal Logic) in which one modality quantifies over non-empty subset of edges. We show that we can characterize the existence of winning Attacker strategies by formulas of Subset Sabotage Modal Logic.

Keywords: Attack Graphs, Sabotage Games, Logics in Games

DOI: 10.3233/IA-221080

Journal: Intelligenza Artificiale, vol. 17, no. 1, pp. 77-88, 2023