Adversarial Machine Learning with Double Oracle

1 Introduction

Adversarial machine learning has been proven to be useful in many domains including spam detection, image recognition, and self-driving car. With adversarial training technique, we can make the model more robust against noisy input features. We can also reduce overfitting to the training set by introducing variant adversarial examples. How to correctly and efficiently setup the adversarial machine learning has become a big interest to people.

There are two main directions in the adversarial machine learning: i) as an attacker, how to conduct an attack. ii) as a defender, how to defend against the attacker given the attacker knows how to attack. The first direction is generally done by simply using Fast Gradient Sign Method (FGSM) introduced by [Goodfellow et al., 2014]. FGSM can construct the adversarial examples very efficiently, therefore solving the scalability issue of general adversarial training. A variant to the FGSM method is Projected Gradient Descent proposed by [Madry et al., 2017]. They propose an intuitive way to run gradient descent with constraints, which also leads to an efficient way to further train a robust model against such attack. In [Athalye et al., 2018], they categorize the common attacks into several categories. But all fall into the "obfuscated gradient" based method. They further propose an attack method to conquer "obfuscated gradient" based defense model, which is trained against an obfuscated gradient based attacks.

On the defense side, the problem can be formulated as a minimax optimization problem or so called the robust optimization problem. People usually solve it by using common minimax technique [Goodfellow et al., 2014; Madry et al., 2017]. This technique can iteratively solve the saddle point of the objective surface, leading to a solution of the minimax problem. The adversarial training model is proven and tested to be much more robust against adversarial attacks.

From the attacker's perspective, depending on the accessibility of the model, it could be divided into i) white-box attack, ii) black-box attack. Here we mainly focus on the white-box attack, which assumes the attacker knows all the hyper-parameters of the model. Therefore the attacker can also access to arbitrary gradient of the entire model, which enables him to run the gradient based attack.

On the other hand, from the game theory perspective, this problem can be formulated as a sequential game, where the defender decides the model first, then the attacker comes and conducts the attack, which is generally called Stackelberg game. There are many efficient methods been proposed to solve the Stackelberg equilibrium very efficiently. Among them, double oracle is proposed by [McMahan et al., 2003] and is commonly used to solve large-scale problems in security game [Jain et al., 2011].

In this paper, we aim to solve the Stackelberg equilibrium of the minimax adversarial problem by using double oracle method. In the previous literature, a single predictor is usually proposed to solve the adversarial problem. However, from the game theory perspective, it is quite rare that a single strategy can perform very well against a attacker playing against to the defender. For example, in the rock-paper-scissors game, given the assumption that the defender moves first, it is hard to defend against the attacker's strategy with a single defender pure strategy. Instead, a mixed strategy including randomization could outperform a single pure strategy quite a lot in many cases. Therefore, we aim to compute a mixed strategy over the defender's strategy space to further improve the robustness against a malicious attacker.

2 Problem Statement

Given the training instances Dtrain = {(xi, yi)} and testing instance Dtest, where xi is the feature and yi is the label. The defender is using a specific model m(x, θ), where x is the feature fed into the model and θ ∈ Θ is the hyper-parameter of the model. Given a prediction m(x, θ) ∈ Rn and a loss function L : Rn ×Rn → R, the loss is L(m(x, θ), y). The expected loss over the entire training set can be written as E(x,y)∼Dtrain L(m(x, θ), y).

Once the defender's model θ and the instances D are given, the attacker can decide an attack δ(x,y) ∈ ∆ for each instance (x, y) subject to some constraints ∆. So the attacker is maxi-

Algorithm 1: Entire Double Oracle

• 1 Input: training instance Dtrain = {(x, y)} feature x and label y; number of defender/attacker strategies k
• 2 Parameters: defender strategies {θ1 , ..., θk } with probabilities {p1, ..., pk}; attacker strategies
• 3 Initialization: θi = θ ∀i where θ is the pre-trained non-adversarial model; δi = 0 ∀i.
• {δ1 , ..., δk } with probabilities {q1, ..., qk}.
• 4 for iteration = 1, 2, ... do
• 5 Compute the payoff of each defender/attacker strategy given the current adversarial strategy.
• 6 Attacker: Choose δa the worst attacker strategy. Compute the optimal attack δ∗ against the defender mixed strategy, which uses model θi with probability pi. Replace δa by δ∗ .
• 7 Defender: Choose θ the worst defender strategy. Improve model θ against the adversarial example {x + δx, y|δ ∼ attacker mixed strategy}(x,y)∈Dtrain to update the current model θ.
• 8 Core linear program: compute the payoff matrix M of every pair of defender/attacker strategy. Solve a Stackelberg game with matrix M and obtain the defender optimal mixed strategy {p∗1 , ..., p∗k } and attacker optimal mixed strategy {q∗ 1 , ..., q∗ k }.
• 9 Update the probability p and q by p∗ , q∗ .

mizing the expected defender loss:

which can be generally solved by running gradient descent based method like PGD [Madry et al., 2017].

Given the attacker is maximizing the expected loss, the defender wants to prevent it, which leads to a minimax problem:

In [Madry et al., 2017], they propose an iterative algorithm to solve the above minimax problem by computing the saddle point of the expected loss function. Here, instead of using a single defender model θ here, we aim to randomize over multiple defender models ˆΘ = {θ1 , θ2 , ..., θk } with probability {p1, p2, ..., pk}, where k is the number of models. Under such condition, the defender's problem becomes:

3 Methodology and Algorithms

Our algorithm iteratively chooses the worst defender/attacker strategy to improve. Each player trains its strategy based on the current adversarial mixed strategy, where we call an oracle. The double oracle method comes from the idea of iteratively updating players' strategy, which is guaranteed to converge to equilibrium eventually when the strategy space is finite and the oracle is optimal. In our case, we use gradientbased oracles (hill climbing algorithm) and both strategy spaces are not finite. Therefore we do not possess the theoretical guarantee. This is the common issue of non-convexity of neural network. But empirically, we expect it to outperform the existing single gradient-based adversarial training since we are using randomized model.

3.1 Randomization and Ensemble

If we randomize over several models {θ1, ..., θk} with probability distribution {p1, ..., pk}, given an attack δ ∈ ∆|Dtest| then the expected testing loss would be

If we are using ensemble, then we have to combine the predicted probability before making prediction, resulting to the following testing loss:

Since the loss function is convex, given an attack δ, the testing loss by using ensemble method is always smaller than the testing loss by using randomization. By introducing an optimal attack, the attacker aims to maximize the expected testing loss in equations (3) and (4) respectively. But for every attack δ, (4) is always smaller than (3). Therefore, even after taking a maximization over δ, the optimal testing loss of ensemble is still always smaller than the testing loss of randomization. This implies that we can derandomize the original mixed strategy to a deterministic ensemble method without lossing solution quality.

4 Consclusion

With the help of game theory, we can construct the randomized strategy (model) to defend the attacker. By the convexity and the Jenson inequality, we can further derandomize the randomized strategy to a deterministic strategy without lossing solution quality. This helps enhance the robustness of the machine learning model. The idea can also be adopted to many other domains to gain robustness for free.