Approximate Solutions for Attack Graph Games with Imperfect Information
Karel Durkota, Viliam Lisy, Branislav Bosansky, and Christopher Kiekintveld
In IJCAI Workshop on Behavioral, Economic and
Computational Intelligence for Security (BECIS). 2015.
This is the author's version of the work.
Download
Abstract
We focus on network hardening with honeypots
which could trap and expose the attacker. We
model this problem as a general-sum extensiveform
game with imperfect information. Based on
a specific computer network, the defender seeks
for an optimal deployment of honeypots while
the attacker uses an attack plan from a library
of possible attacks compactly modeled by attack
graphs. We detecting the attacker's rationalizable
strategies and compute Stackelberg Equilibrium by
solving mixed-integer linear programming formulations
and improve it with iterative oracle approach.
However, this approach has limited scalability.
Therefore, we also analyze a trade-off between
complexity and optimality of game approximations,
which bring useful results for the games
in security domain.
