@article{DJOR13,
author = { Marten van Dijk and Ari Juels and Alina Oprea and Ronald L. Rivest },
title = { {FlipIt}: The Game of ``Stealthy Takeover'' },
date = { 2013 },
OPTyear = { 2013 },
journal = { J. Cryptology },
volume = { 26 },
pages = { 655-713 },
doi = { 10.1007/s00145-012-9134-5 },
publisher = { Springer },
abstract = {
Recent targeted attacks have increased significantly in sophistication,
undermining the fundamental assumptions on which most cryptographic primitives
rely for security. For instance, attackers launching an Advanced Persistent Threat
(APT) can steal \emph{full} cryptographic keys, violating the very secrecy of ``secret''
keys that cryptographers assume in designing secure protocols. In this article, we introduce
a game-theoretic framework for modeling various computer security scenarios prevalent today,
including targeted attacks. We are particularly interested in situations in which an attacker
periodically compromises a system or critical resource \emph{completely}, learns all its secret
information and is not immediately detected by the system owner or \emph{defender}.
\par
We propose a two-player game between an attacker and defender called {\em \FlipIt} or
The Game of ``Stealthy Takeover.'' In \FlipIt, players compete to control a shared resource.
Unlike most existing games, \FlipIt\ allows players to move at any given time, taking control
of the resource. The identity of the player controlling the resource, however, is not revealed
until a player actually moves. To move, a player pays a certain move cost. The objective of
each player is to control the resource a large fraction of time, while minimizing his total
move cost. \FlipIt\ provides a simple and elegant framework in which we can formally reason
about the interaction between attackers and defenders in practical scenarios.
\par
In this article, we restrict ourselves to games in which one of the players (the defender) plays
with a \emph{renewal strategy}, one in which the intervals between consecutive moves are chosen
independently and uniformly at random from a fixed probability distribution. We consider attacker
strategies ranging in increasing sophistication from simple periodic strategies (with moves spaced
at equal time intervals) to more complex \emph{adaptive strategies}, in which moves are determined
based on feedback received during the game. For different classes of strategies employed by the
attacker, we determine \emph{strongly dominant} strategies for both players (when they exist),
strategies that achieve higher benefit than all other strategies in a particular class. When
strongly dominant strategies do not exist, our goal is to characterize the residual game
consisting of strategies that are not strongly dominated by other strategies. We also prove
equivalence or strict inclusion of certain classes of strategies under different conditions.
\par
Our analysis of different \FlipIt\ variants teaches cryptographers, system designers, and the
community at large some valuable lessons:
\par
\begin{enumerate}
\item
Systems should be designed under the assumption of repeated total compromise, including theft
of cryptographic keys. \FlipIt\ provides guidance on how to implement a cost-effective
defensive strategy.
\item
Aggressive play by one player can motivate the opponent to drop out of the game (essentially
not to play at all). Therefore, moving fast is a good defensive strategy, but it can only be
implemented if move costs are low. We believe that virtualization has a huge potential in
this respect.
\item
Close monitoring of one's resources is beneficial in detecting potential attacks faster,
gaining insight into attacker's strategies, and scheduling defensive moves more effectively.
\end{enumerate}
\par
Interestingly, \FlipIt\ finds applications in other security realms besides modeling of
targeted attacks. Examples include cryptographic key rotation, password changing policies,
refreshing virtual machines, and cloud auditing.
},
}