Adversarial Machine Learning with Double Oracle

Kai WangIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of making machine learning models more robust against adversarial attacks by framing the problem as a game between an attacker and a defender. They propose using the "double oracle" method from game theory to find a randomized defense strategy, which can then be converted into a more practical deterministic ensemble, leading to improved robustness.

What Problem Does This Paper Address?

Adversarial machine learning is crucial for building reliable AI systems, especially in areas like spam detection and autonomous driving. While adversarial training can make models more robust, setting up this training effectively is a challenge. Current defenses often rely on "obfuscated gradients," which can be circumvented by sophisticated attacks. The problem is essentially a minimax game: the defender wants to minimize the loss, while the attacker wants to maximize it by crafting malicious inputs. Existing methods often focus on finding a single "best" defense strategy, but this paper argues that a randomized or mixed strategy, inspired by game theory, might be more effective, much like how a mixed strategy in rock-paper-scissors is superior to a single pure strategy.

Methods

The core of this paper is the application of the double oracle method, a game theory technique for solving sequential zero-sum games, to the adversarial machine learning problem. They formulate the defender-attacker interaction as a Stackelberg game.

Here's a breakdown of their approach:

  • Game Formulation: The problem is framed as a zero-sum minimax problem between a learner (defender) and an attacker.
  • Double Oracle: This iterative method is used to find an equilibrium in the game. It involves:
  • Oracle: A mechanism to compute the best response for one player given the other player's current strategy. In this context, the "oracle" is typically a gradient-based method like Projected Gradient Descent (PGD) for finding adversarial examples.
  • Iterative Improvement: The attacker and defender take turns improving their strategies. The attacker finds the worst-case attack against the defender's current strategy, and the defender updates its model to be more robust against this attack.
  • Randomized Strategy: Instead of a single defense model, the authors propose finding a mixed strategy for the defender. This means the defender uses a distribution over multiple defense models. This is achieved by solving the minimax problem with a randomized defender strategy.
  • Derandomization: A key insight is that the randomized defense strategy can be "derandomized" into a deterministic ensemble of models without losing robustness. This is because the expected loss of an ensemble is always less than or equal to the expected loss of a randomized strategy, and the attacker aims to maximize this loss.

Datasets

Not discussed in the paper. The paper focuses on the theoretical formulation and algorithmic approach rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Game Theory for Robustness: Framing adversarial training as a game theory problem, specifically a Stackelberg game, provides a powerful lens for developing more robust models.
  • The Power of Randomized Defense: A single, fixed defense strategy might be vulnerable. A randomized strategy, where the defender chooses among multiple models with certain probabilities, can be inherently more robust against an adaptive attacker.
  • Derandomization for Practicality: The theoretical advantage of randomized strategies can be translated into practical benefits through ensemble methods. This is a significant insight as ensembles are more straightforward to implement and deploy than true randomized models.
  • Double Oracle as a General Framework: The double oracle method offers a principled way to iteratively improve both attacker and defender strategies, potentially leading to more stable and robust equilibria.

Key Results

The paper primarily presents a theoretical framework and an algorithmic approach. It doesn't report specific quantitative results on accuracy or robustness metrics. The main "result" is the proposed method for finding a randomized defense strategy and the subsequent derandomization into an ensemble, which is argued to enhance robustness.

Limitations and Future Work

  • Theoretical Guarantee: The authors acknowledge that their approach uses gradient-based oracles and potentially infinite strategy spaces, meaning they don't have theoretical guarantees of convergence to an equilibrium, unlike finite-strategy games.
  • Empirical Validation: The paper is largely theoretical and lacks empirical results to demonstrate the effectiveness of their proposed method compared to existing adversarial training techniques.
  • Computational Cost: Solving minimax problems with iterative methods like double oracle can be computationally expensive, especially with large models and datasets.
  • Future Work: The authors suggest that the idea of using game theory and randomized strategies can be applied to other domains to achieve robustness. Further empirical studies would be needed to validate the practical benefits of their approach.

Summary updated

BibTeX
@inproceedings{wang2019adversarial,
  author = {Kai Wang},
  title = {{Adversarial Machine Learning with Double Oracle}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/925},
}
Figure