Single controller stochastic games for optimized moving target defense

AbdelRahman Eldosouky, Walid Saad, Dusit NiyatoICC 2016 · DOI · OpenReview

TL;DR

This paper introduces a novel game-theoretic framework for optimizing Moving Target Defense (MTD) in wireless networks. By modeling the interaction between a base station (defender) and an eavesdropper (attacker) as a single-controller stochastic game, the authors provide a method to derive optimal strategies for randomizing cryptographic techniques and keys, significantly improving the defender's utility and security.

What Problem Does This Paper Address?

Modern wireless networks, especially those leveraging software-defined networking and radio, are increasingly vulnerable to sophisticated cyber threats like jamming, eavesdropping, and node forgery. Moving Target Defense (MTD) offers a promising solution by continuously randomizing network configurations (e.g., cryptographic keys, IP addresses) to increase attacker uncertainty and cost. However, a significant challenge has been the lack of analytical tools to quantify the benefits and tradeoffs of MTD, making it difficult to design and implement effective defense strategies. This paper aims to bridge this gap by providing a rigorous game-theoretic approach to optimize MTD implementation, specifically focusing on randomizing cryptographic techniques and keys.

Methods

The core of this paper is the formulation of the MTD problem as a single-controller stochastic game. In this model, the base station (BS) acts as the defender, strategically choosing cryptographic techniques and keys to thwart an eavesdropper (attacker). The "single-controller" aspect is crucial: only the defender's actions influence the transition to the next game state, which represents a change in the cryptographic configuration.

The authors define the game with players (defender, attacker), states (defined by the current encryption technique and key), actions (defender chooses technique/key, attacker attempts decryption), transition probabilities (controlled by the defender), and utility functions (reward for protecting data, cost of power consumption, and transition rewards).

To find the optimal strategies, they leverage existing work on bimatrix games. The stochastic game is converted into a bimatrix game where rows and columns represent pure stationary strategies for each player. The elements of these matrices are the accumulated discounted utilities over all possible states. Algorithms like Lemke-Howson are then used to find the Nash equilibrium of this bimatrix game, which in turn provides the equilibrium strategies for the original stochastic game.

A novel aspect is the introduction of a defense cost function that accounts for the overhead of reconfiguring the system. This cost is modeled as a function of the number of consecutive changes in encryption methods, with two proposed forms: a linear function ($C(q, n) = q \cdot n$) and a logarithmic function ($C(q, n) = q \cdot \ln(n+1)$). The paper proves that even with these costs, the game still admits an equilibrium.

Datasets

Not discussed in the paper. The evaluation is based on simulated scenarios with defined parameters.

Key Insights and Ideas

  • Single-Controller Stochastic Game for MTD: This is the central innovation. By framing MTD as a game where only the defender controls state transitions, the model accurately reflects the defender's proactive role in randomizing defenses. This simplifies analysis and guarantees an equilibrium.
  • Cryptographic Randomization as a Game: The paper elegantly maps the abstract concept of MTD to concrete actions like selecting encryption techniques and keys, making the game-theoretic approach directly applicable to practical security implementations.
  • Quantifying MTD Benefits: The framework moves beyond qualitative discussions of MTD by providing a mathematical model to calculate the defender's expected utility and derive optimal strategies, allowing for a quantitative assessment of MTD's effectiveness.
  • Impact of Defense Costs: The inclusion of defense costs (reconfiguration overhead) is a realistic addition. The analysis shows that while costs reduce overall utility, the game still maintains an equilibrium, and the choice of cost function can significantly impact the defender's outcome.
  • Defender's Utility is State-Dependent: Simulation results highlight that the defender's expected utility varies significantly across different states (cryptographic configurations), emphasizing the importance of state-aware strategy selection.

Key Results

  • The proposed game-theoretic framework guarantees the existence of a Nash equilibrium for the MTD problem.
  • Simulation results demonstrate that the equilibrium MTD strategy significantly improves the defender's expected utility compared to randomly selecting actions. For instance, at a discount factor of $\beta > 0.75$, the percentage increase in utility can range from 5% to 40% depending on the state.
  • The defender's utility is higher when using the first encryption technique (lower power consumption) compared to the second, especially in the initial states.
  • Introducing defense costs, particularly the linear cost function ($C(q, n) = q \cdot n$), leads to a noticeable decrease in the defender's expected utility, underscoring the tradeoff between security and operational cost. The logarithmic cost function had a less pronounced effect.
  • The equilibrium strategies derived are shown to be robust, meaning neither player has an incentive to deviate if the other adheres to their equilibrium strategy.

Limitations and Future Work

  • Simplified Attacker Model: The attacker's strategy is primarily based on brute-force decryption. More sophisticated adaptive attackers or attackers with prior knowledge of the system could present different challenges.
  • Network Model: The paper focuses on a single base station and its interaction with an eavesdropper. Extending the model to multiple base stations, distributed wireless sensor networks, or more complex network topologies would be valuable.
  • Specific Cryptographic Techniques: While the paper discusses randomizing techniques and keys, it doesn't delve into the specifics of which cryptographic algorithms are most suitable or how their security properties interact with MTD.
  • Future Work: The authors suggest exploring more complex attacker models, extending the framework to distributed systems, and investigating the impact of different MTD cost functions. They also mention the potential for using this framework to analyze other MTD techniques beyond cryptographic randomization.

Summary updated

Abstract

Moving target defense (MTD) techniques that enable a system to randomize its configuration to thwart prospective attacks are an effective security solution for tomorrow's wireless networks. However, there is a lack of analytical techniques that enable one to quantify the benefits and tradeoffs of MTDs. In this paper, a novel approach for implementing MTD techniques that can be used to randomize cryptographic techniques and keys in wireless networks is proposed. In particular, the problem is formulated as a stochastic game in which a base station (BS), acting as a defender seeks to strategically change its cryptographic techniques and keys in an effort to deter an attacker that is trying to eavesdrop on the data. The game is shown to exhibit a single-controller property in which only one player, the defender, controls the state of the game. For this game, the existence and properties of the Nash equilibrium are studied, in the presence of a defense cost for using MTD. Then, a practical algorithm for deriving the equilibrium MTD strategies is derived. Simulation results show that the proposed game-theoretic MTD framework can significantly improve the overall utility of the defender, while enabling effective randomization over cryptographic techniques.
BibTeX
@inproceedings{eldosouky2016single,
  author = {AbdelRahman Eldosouky and Walid Saad and Dusit Niyato},
  title = {{Single controller stochastic games for optimized moving target defense}},
  booktitle = {ICC},
  year = {2016},
  doi = {10.1109/icc.2016.7510985},
}
Figure