Approximate Solutions for Attack Graph Games with Imperfect Information

Karel Durkota, Viliam Lisy, Branislav Bosansky, and Christopher Kiekintveld

In Conference On Decision and Game Theory for Security (GameSec). 2015.

This is the author's version of the work.

Download

Abstract

We study the problem of network security hardening, in which a network administrator decides what security measures to use to best improve the security of the network. Specifically, we focus on deploying decoy services or hosts called honeypots. We model the problem as a general-sum extensive-form game with imperfect information and seek a solution in the form of Stackelberg Equilibrium. The defender seeks the optimal randomized honeypot deployment in a specific computer network, while the attacker chooses the best response as a contingency attack policy from a library of possible attacks compactly represented by attack graphs. Computing an exact Stackelberg Equilibrium using standard mixed-integer linear programming has a limited scalability in this game.We propose a set of approximate solution methods and analyze the trade-offs between the computation time and the quality of the strategies calculated.