Algorithms for Subgame Abstraction with Applications to Cyber Defense
(A. Basak, M. Gutierrez, and C. Kiekintveld)
In Conference on Decision and Game Theory for Security (GameSec) 2018.
This is the author's version of the work.
Download
Abstract
It is typically infeasible to use automated intrusion detection systems
to scan every single host in a network with high sensitivity and frequency due to
high costs and large network sizes. We present a game-theoretic model between
a network administrator and a worm using normal form games with a particular
structure where the network admin wants to maximize the security of the network
using limited resources, and the attacker wants to infect the network without getting
caught. However, a large number of hosts in a network can result in a massive
game, making it problematic to compute standard solutions like Nash equilibrium.
We propose an abstraction approach for solving large games that have a
subgame structure and show that it can be used to solve much larger instances of
this cybersecurity scenario than standard algorithms.
