Intrusion Tolerance as a Two-Level Game
We formulate intrusion tolerance for a system with service
replicas as a two-level game: a local game models intrusion recovery, and
a global game models replication control. For both games, we prove the
existence of equilibria and show that the best responses have a threshold
structure, which enables efficient computation of strategies. State-of-theart intrusion-tolerant systems can be understood as instantiations of our
model with heuristic control strategies. Our analysis shows the conditions under which such heuristics can be significantly improved through
game-theoretic reasoning. This reasoning allows us to derive the optimal control strategies and evaluate them against 10 types of network
intrusions on a testbed. The testbed results demonstrate that our game-theoretic strategies can significantly improve service availability and reduce the operational cost of state-of-the-art intrusion-tolerant systems.
In addition, our game strategies can ensure any chosen level of service
availability and time-to-recovery, bridging the gap between theoretical
and operational performance.