In the latest study group, Nigel and Theo talked about FlipIt: The Game of "Stealthy Takeover", the subject of the 2011 IACR Distinguished Lecture given by Ron Rivest at CRYPTO. FlipIt is a two-player game that aims to model various computer security scenarios, allowing these scenarios to be analysed using a game-theoretic framework. Van Dijk, Juels, Oprea and Rivest formally define FlipIt and show that there are many possible interesting variants of the game that correspond to different applications. They also show that even in simple cases the analysis can become quite complex.
To understand the FlipIt game in its most simple form, consider the following example implementation. There are two players in seperate rooms, as well as a 'resource' that neither of the players can see. This resource can be 'controlled' or 'owned' by either of the players. Both players have a control panel with a light and a single button which they can press at any time. When a player moves, i.e., presses their button, they are given ownership of the resource. If they did not own the resource before they moved, the light on their control panel will flash. This is called a 'takeover'. When the light does not flash after a player moves, this means the resource was already under their control.
An important feature of this game is that neither player can see who is currently in control of the resource, nor can they see when the other player presses their button to take control, hence the description "Stealthy Takeover". The players can only find out who owns the resource by pressing the button. Players gain 'points' for every second that they own the resource. However, making a move comes with a certain cost. The goal of the players is to maximize their own score, which consists of the total time they owned the resource minus the cost of the player's combined moves. To do this, both players implement some sort of strategy that decides when they should press the button.
What makes this game interesting is that it models the behaviour of several applications in the area of computer security. For example, FlipIt can be used as a macro-level game to model Advanced Persistent Threats, where one player (the 'defender') tries to keep his sensitive assets (which are modeled as an aggregate FlipIt resource) secure from the other player (the 'attacker'). Here, a move by the attacker corresponds to a campaign that results in the attacker breaching the system and gaining 'control' of the sensitive assets. A move by the defender corresponds to a system-wide remediation campaign, such as patching all machines, resetting passwords, reinstalling servers and so on.
There are many more applications, especially when moving away from the simple implementation mentioned before and introducing additional elements. For example, it is possible that players can make several moves, each of which as a different cost and efficacy in gaining ownership of the resource. An attacker might have access to a known exploit but also a zero-day exploit. If he chooses to take control of the resource using the known exploit, the defender can regain control by applying a security patch that fixes this known exploit. However, if the attacker chooses to use the more costly zero-day exploit, the defender is forced to reinstall the software of the resource, which is also more costly than applying a patch. This gives the players several options to consider when choosing their strategy.
It is also interesting to consider variations of the game where at least one of the players gets additional feedback from pressing the button, which can be incorporated in his strategy. For example, the player could learn the last time that his opponent played ('Last Move') or he could learn the complete history of moves made by both players so far ('Full History'). When a player gets no additional feedback, his strategy must be fixed at the start of the game ('Nonadaptive'). Another interesting variation is where one of the players receives feedback before the first move, such as the strategy of his opponent.
In the paper, the authors analyse the most simple form of the game, where there is only one move for both players. The strategy of the first player, the defender, is always nonadaptive, whereas the strategy of the second player, the attacker, is possibly adaptive, up to the point where he gets information on the last move of the defender. They model everything formally and apply game theory to analyse the strategies of both players. Formally, both players have a 'view', which encodes their knowledge of the history and includes all their previous moves and the feedback they received for these moves. Then, their strategy consists of a function that maps a view on the positive real numbers and tells a player how long they should wait until their next move. This strategy function is possibly randomized. Another important concept is the rate of play, which is the average number of moves the players perform as time goes on.
The simplest class of strategies arises when both players fix their strategy before the first move. Here the authors consider a so-called 'periodic strategy', where both players select a random phase p and a rate of play d and then make a move at time p + k*d for k = 0,1,2,... In this case, the authors find a Nash equilibrium, which is a choice of strategies for both players such that neither player stands to gain by changing his strategy if the strategy of the other player would remain unchanged.
They also consider 'renewal strategies' where players move according to a renewal process. Such a process 'renews' itself after every move, i.e., the time until the next move is independent from the previous time, but distributed identically. Here, the authors try to find 'strongly dominant' strategies. A strategy is strongly dominant if it nets the player a better score than all his other strategies would, given that the strategy of his opponent can be any one from some set of strategies. They show that when a player has a fixed rate of play a, the periodic strategy with period a strongly dominates all non-arithmetic renewal strategies. This result holds for both players and even transfers to the case where the players get some information on the rate of play of the other player before the game.
The analysis of FlipIt teaches some valuable lessons to the security community. First of all, systems should be designed under the assumption that they can be completely compromised at times. This includes the theft of cryptographic keys. "Many times, attackers cross the line of secrecy cryptographers assume in their protocol designs." Secondly, the defender can force the attacker out of the game in some cases, by playing very aggressively. This is especially interesting when the move cost for the defender is quite low. The authors mention the example of Virtual Machines that can easily be refreshed from clean images and whose data can be restored from a centralized server. Finally, the analysis shows that any extra amount of feedback will benefit the player during the game. Thus, defenders should monitor their systems frequently to gain insight into the strateegy of the attacker.
The work also raises many open questions, especially as the strategy classes get bigger. Most of them are of the form "If player A uses a strategy from class X, which strategy from class Y would be strongly dominant for player B?" The authors state that the most interesting open questions arise when one of the players uses an adaptive strategy, but that the most challenging instances are when both players can use adaptive strategies.
No comments:
Post a Comment