Title: THWARTING FINITE DIFFERENCE ADVERSARIAL ATTACKS WITH OUTPUT RANDOMIZATION

Abstract: Adversarial input poses a critical problem to deep neural networks (DNN). This problem is more severe in the "black box" setting where an adversary only needs to repeatedly query a DNN to estimate the gradients required to create adversarial examples. Current defense techniques against attacks in this setting are not effective. Thus, in this paper, we present a novel defense technique based on randomization applied to a DNN's output layer. While effective as a defense technique, this approach introduces a trade off between accuracy and robustness. We show that for certain types of randomization, we can bound the probability of introducing errors by carefully setting distributional parameters. For the particular case of finite difference black box attacks, we quantify the error introduced by the defense in the finite difference estimate of the gradient. Lastly, we show empirically that the defense can thwart three adaptive black box adversarial attack algorithms.

1. INTRODUCTION:

The success of deep neural networks has led to scrutiny of the security vulnerabilities in deep neural network based models. One particular area of concern is weakness to adversarial input: carefully crafted inputs that resist detection and can cause arbitrary errors in the model (1; 2) . This is especially highlighted in the domain of image classification, where an adversary creates an image that resembles a natural image to a human observer but easily fools deep neural network based image classifiers (3) .

Different types of adversarial attacks exists throughout the lifecycle of a deep neural network model. For example, adversaries can attack a model during training by injecting corrupting data into the training set or by modifying data in the training set. However, inference time attacks are more worrisome as they represent the bulk of realistic attack surfaces (4; 5; 6) .

The input created under an inference time attack is known as an adversarial example and methods for generating such examples have recently attracted much attention. In most cases, the adversarial example is created by perturbing a (correctly classified) input such that the model commits an error. The perturbation applied to the "clean" input is typically constrained to be undetectably small (7; 8; 9) . Defending againsts adversarial attacks on deep neural networks is crucial and has seen relatively slow progress compared to the sophistication and progress of adversarial attacks (10; 11; 12; 13; 14; 15) . This is because it is difficult to prove a defense can withstand the types of attacks it is designed for especially when the defense must prove capable of withstanding "adaptive" adversaries that have knowledge of the details of the defense (16) .

A defense against adversarial attacks is defined by the threat model it is designed to defend against (16) . The most permissive threat model makes the weakest assumptions about the adversary. One such threat model can be assuming the adversary has complete knowledge of the model, including architecture and parameters of the underlying network. This is known as the "white-box" setting. Other threat models can also be useful, such as assuming the adversary has knowledge of the network architecture but not the parameters of the model. More restrictive threat models allow only so called "black-box" attacks, attacks that can create adversarial examples without having access to the model architecture or weights and only accessing some form of output of the model. The rest of the paper is organized as follows. In Section 2, we discuss the threat model considered. In Section 3, we describe valid black box attacks under the threat model. Output randomization as a defense is described in Section 4. We show empirical results in Section 5, cover related approaches in Section 6, and conclude in Section 7.

2. THREAT MODEL:

Adversary goals: The goal of the adversary is to force the classifier to commit an error within a distortion limit, such that the example crafted by the adversary is similar to the original example. The adversary induces such an error in an untargeted or targeted attack. The goal of an untargeted attack is misclassification of an input, whereas the goal of a targeted attack is misclassification of an input as a class specified by the adversary.

Adversary knowledge::

The adversary has access to the model only at the input and output level, and has no knowledge of its architecture or parameters. This black-box adversary is aware of the details of the defenses protecting the model and the type of randomness associated with any defense but not the exact random numbers generated.

Adversary capability::

The adversary only has access to the model by providing examples as input and observing the output probability vector generated by the model as output. The adversary can modify aspects of the input in any way as long as it remains similar to the original input. This similarity is controlled by an l p distortion penalty on the adversarial image. Common choices for the distortion penalty include l 1 , l 2 and l ∞ . We use the l 2 perturbation penalty as this type of attack results in the strongest attacks (17) . Attackers are allowed to query the model up to a maximum limit, which we increase to our computational limit to strengthen attacks. In addition to a maximum query limit, attackers often use an early stopping parameter to avoid wasting computation on unpromising direction during optimization. We also increase this parameter to test our defense against stronger attacks.

3. EXISTING BLACK BOX ATTACKS:

Black box attacks are called "gradient-free" attacks since they do not involve computing gradients of the input by backpropagation on the model under attack. Instead the gradients of the input are estimated by using the finite difference estimate for each input feature.

Black box attacks can be categorized by the type of output the adversary is allowed to observe: logit layer, class probabilities/softmax layer, or top k class probabilities/labels. In general, designing successful black box attacks in the label only setting is much harder than the setting where the logit layer or softmax layer is available to the attacker. We consider the easiest setting for black box attacks, where all the class probabilities are available.

3.1. ZOO BLACK BOX ATTACK:

The Zeroth Order Optimization based black-box (ZOO) attack ( 18) is a method for creating adversarial examples for deep neural networks that only requires input and output access to the model. ZOO adopts a similar iterative optimization based approach to adversarial example generation as other successful attacks, such as the Carlini & Wagner (C&W) attack (17) . The attack begins with a correctly classified input image x, defines an adversarial loss function that scores perturbations δ applied to the input, and optimizes the adversarial loss function using gradient descent to find δ * that creates a succesful adversarial example. Specifically, gradient descent is used to find δ * such that:

f (x + δ * ) = y a x -(x + δ * ) ≤

Namely, that the perturbed input x + δ * successfully fools the classifier f to predict the incorrect class y a and that the perturbed input is similar to the original input up to some distortion limit .

The primary (and strongest) adversarial loss used by the ZOO attack for targeted attacks is given by:

EQUATION

Where x is an input image, t is a target class, and κ is a tuning parameter. Minimizing this loss function over the input x causes the classifier to predict class t for the optimized input. For untargeted attacks, a similar loss function is used:

EQUATION

where i is the original label for the input x. This loss function simply pushes x to enter a region of misclassification for the classifier f .

In order to limit distortion of the original input, the adversarial loss function is combined with a distortion penalty in the full optimization problem. This is given by:

min x x -x 0 2 2 + c • L(x, t) subject to x ∈ [0, 1] n

In the white box setting, attackers can take advantage of the backprogation algorithm to calculate the gradient of the adversarial loss function with respect to the input coordinates ( δL δxi ) and solve the optimization problem using gradient descent. In lieu of this, ZOO uses "zeroth order stochastic coordinate descent" to optimize input on the adversarial loss directly. This is most easily understood as a finite difference estimate of the gradient of the input with the symmetric difference quotient (18) :

δL δx i ≈ g i := L(x + he i ) -L(x -he i )

2h with e i as the basis vector for coordinate/pixel i and h set to a small constant. The ZOO attack uses this approximation to the gradients to create an adversarial example from the given input. Note that for an image with n pixels, computing an estimate of the gradient with respect to each pixel requires 2n queries to the model. Since this is usually prohibitive, the ZOO attack circumvents this by only estimating the gradients for a subset of coordinates at each step. ZOO also uses dimensionality reduction and a hierarchical approach to further increase the efficiency of the attack and show empirically that these methods are effective (18).

3.2. QUERY LIMITED (QL) BLACK BOX ATTACK:

A similar approach to ZOO is adopted by (19) in a query limited setting. Like ZOO, the QL attack estimates the gradients of the adversarial loss using a finite difference based approach. However, the QL attack reduces the number of queries required to estimate the gradients by employing a search distribution. Natural Evolutionary Strategies (NES) (20) is used as a black box to estimate gradients from a limited number of model evaluations. Projected Gradient Descent (PGD) ( 12) is used to update the adversarial example using the estimated gradients. PGD uses the sign of the estimated gradients to perform an update: x t = x t-1 -η • sign(g t ), with a step size η and the estimated gradient g t . The estimated gradient for the QL attack using NES is given by:

g t = m i=1 L(x + σ • u i ) • u i -L(x -σ • u i ) • u i 2mσ

where u i is sampled from a standard normal distribution with the same dimension as the input x, σ is the search variance, and m is the number of samples used to estimate the gradient. The difference between this approach and ZOO is that ZOO attempts to estimate the gradient with respect to one coordinate at a time while this approach averages over perturbations to many coordinates to estimate the entire gradient directly.

In the next section, we show that applying a simple randomization function (that does not affect model accuracy) to the output of a model causes these types of attacks to fail even if the attack is adapted to the specific randomization function.

4. THWARTING BLACK BOX ATTACKS:

The intuition behind output randomization is that a model may deliberately make errors in its predictions in order to thwart a potential attacker. This simple idea introduces a tradeoff between accurate predictions and the effectiveness of finite difference based black box adversarial attacks.

Output randomization for a model that produces a probability distribution over class labels replaces the output of the model p by a stochastic function d(p). The function d must satisfy two conditions:

1. The probability of misclassifying an input due to applying d is bounded by K 2. The vector d(p) prevents adversaries under the given threat model from generating adversarial examples.

The first condition ensures that the applied defense minimally impacts non-adversarial users of the model, such as users of an online image classification service. The effectiveness of the defense comes from satisfying the second condition as the introduced randomness must prevent an adversary (in the appropiate setting) from producing an adversarial example.

In the following two sections, we consider a simple noise-inducing function d(p) = p + where is a random variable. To verify that this function satisfies the first condition above, we wish to know the probability that the class predicted by the undefended model is the same as the class predicted by the defended model. If the output of the model for an input x is p, we will refer to the maximum element of p as p m and the rest of the elements of p in decreasing order as p 2 , p 3 , ...p C .

Suppose the model correctly classifies the input x in the vector p, we can express the probability that x is misclassified in the vector d(p) as:

C i=2 P(d(p i ) > d(p m ))

We can write P(d(p i ) > d(p m )) for i = 2, 3, ...C as:

P(d(p i ) > d(p m )) = P(p i + i > p m + m )

If we define δ i = p m -p i , as shown in Figure 1a , and since e i := im is itself a gaussian with mean µ i -µ m and variance σ 2 i + σ 2 m then we can write:

P(e i > δ i ) = 1 -P(e i ≤ δ i ) = 1 -P e i -µ i + µ m σ 2 i + σ 2 m ≤ δ i -µ i + µ m σ 2 i + σ 2 m

Using the cumulative distribution function of a standard gaussian distribution Φ, we can write the misclassification probability as:

K := P(d(p i ) > d(p m )) = 1 -Φ δ i -µ i + µ m σ 2 i + σ 2 m = Φ - δ i -µ i + µ m σ 2 i + σ 2 m

For the special case of a gaussian noise function d(p) with mean 0 and variance σ 2 we would like to fix the probability of misclassification to a value K and compute the appropiate variance σ 2 . We can use the inverse of the standard gaussian cdf Φ -1 , or the probit function, to write this easily:

σ 2 = - δ i 2Φ -1 (K)

Note that the desired misclassification rate K < 0.5 in any real case and so the rhs will be positive. If we consider δ i as the confidence of the model, then the allowable variance will be larger when the model is confident and smaller otherwise. We show the calculations above for one class i, the misclassification probability (K) and level of noise (σ 2 ) can be set for each class separately. In Figure 1b we show the maximum allowable variance for different misclassification rates. 

4.2. FINITE DIFFERENCE GRADIENT ERROR:

To verify the function d(p) satisfies the second condition, that it introduces error that prevents a finite difference based black box attack, we show the effect of the output randomization on the gradient accessible to the adversary.

Finite difference (FD) based approaches involve evaluating the adversarial loss at two points, x + he i and x -he i , close to x (with small h and unit vector e i ) and using the slope to estimate the gradient of the loss with respect to pixel i of the input. For a loss function L, the finite difference estimate of the gradient of pixel i is given by:

EQUATION

Here, we write the adversarial loss function (either the untargeted loss in Equation 2 or the targeted loss in Equation 1) in terms of the output of the model to make explicit the dependence of L on the output vector of the network p = f (•). p and p are used to distinguish between the two output vectors needed to compute the gradient estimate.When the network is defended using output randomization, the function d() is applied to the output vector of the network. Thus, the finite difference gradient computed by the attacker is:

γ i = L(d(p)) -L(d(p )) 2h

The error in the FD gradient introduced by the defense is given by |g i -γ i |. When d is a function that adds noise to the output of the network, the expected value of the error is:

|E[g i -γ i ]| = g i -E L(p + ) -L(p + ) 2h

This error term depends on the choice of the adversarial loss function L(•). Since the untargeted attack is generally considered easier than the targeted attack, consider how the gradient error of the defended model behaves under the untargeted adversarial loss function. For untargeted attacks, we simplify the loss function to: L u (p) = log(p c ) -log(p o ) = log( pc po ) where p c is the probability of the true class and p o is the maximum probability assigned to a class other than the true class of the input image.

Substituting the untargeted adversarial loss for L(•) we see:

|E[g i -γ i ]| = g i - 1 2h E log( p c + c p o + o ) -log( p c + c p o + o )

We use a second order Taylor series approximation of

E[log(X)] ≈ log(E[X]) -V ar[X] 2E[X]

2 to approximate the expectations. If we further assume is zero-mean with variance σ 2 , then E[p + ] = p and the expectation of the defended gradient is approximately:

|E[g i -γ i ]| ≈ σ 2 4h σ 2 + p 2 o + p 2 c p 2 c p 2 o - σ 2 + p 2 o + p 2 c p 2 c p 2 o

This approximation summarizes the suprising effect output randomization has on finite difference based black box attacks. Firstly, it is easy to see that the error scales with the variance of (in the zero mean case). Even when the adversary adapts to the defense by averaging over the output randomization the variance is only reduced linearly by the number of samples. Secondly, even in expectation the error is never non-zero. This is because one of two cases must be true in order for the error to be zero: The reason for this behavior is mostly due to the log operation in the adversarial loss function L. As noted by the authors in ( 18), the log is crucial to the success of finite difference black box attacks as well trained models yield skewed distributions in the output p = f (x). In our experiments, we show that this behavior holds in real world experiments on image classification datasets.

5. EMPIRICAL RESULTS:

To evaluate the output randomization defense against black box attacks, we select three successful black box attacks (ZOO (18) , QL (19) , and BAND ( 21)) on benchmark image classification datasets (MNIST (22) , CIFAR10 (23) , and ImageNet (24) ). For all defended models, we use ∼ N (0, σ 2 •I C ). Details of both the attacks and defenses can be found in our code1 and the appendix. We follow the guidelines laid out in (16) , most importantly we attempt to adapt the attacks to the proposed defense. In this case, this means the attacker is aware of the type of randomization applied to the output of the network. Therefore, we adapt the attacks by allowing the attacker to average over the output randomization in an attempt to bypass the defense. This type of adaptation has been shown to overcome certain types of input and model randomization defenses (25) . In our results, we refer to this as the adaptive attack.

As a sanity check, we also measure the attack success rate of a white box attacker (Carlini & Wagner L2 (17) attack) with randomized output. We find that the defense has some success in defending against this attack in the non-adaptive case. However the adaptive white box attacker is able to overcome the output randomization by averaging over a small number of samples. This is summarized in Figure 2 .

Our main set of experiments is shown in Figure 3 and show the effects of output randomization on the non-adaptive and adaptive ZOO attacks. We show that the defense reduces the attack success rate significantly even in the adaptive attacker setting, where we average over randomness and double attack iterations. The effectiveness of the defense was not affected by targeted or untargeted attacks. Table 1 summarizes the results for three finite difference based black box attacks on ImageNet.

It is important to show how a defense affects the "normal" operating properties of a model and this is typically demonstrated by comparing the test set accuracy of the defended model to the undefended model. Figure 2a and Figure 3a show the effect of increasing noise levels on test set accuracy. Output randomization is an effective defense against black box attacks at noise levels as small as σ 2 = 1e-4 where model performance is identical to undefended models. (a) Attack success rate (solid) and test set accuracy (dashed) vs variance for the non-adaptive attacker. Output randomization is not effective against a white box attacker at small noise levels. Defensive techniques without output randomization are still vulnerable to black box attacks. We evaluated defensive distillation (10) and input randomization (26) against the ZOO attack and found that these defenses did not reduce the attack success rate significantly as shown in Table 2 . Distillation is shown to be vulnerable to white box attacks in (17) , we show it is also vulnerable to finite difference black box attacks. Input randomization (26) has limited success in defending against ZOO (reducing attack success rate to 0.76), however it is not as effective as output randomization. This is because randomization applied at the input is not guaranteed to affect the finite difference gradient estimates.

In addition,input randomization also does not allow fine control over model accuracy. 

6. RELATED WORK:

In this section, we discuss related gradient masking or obfuscated gradient defenses. We will focus on proactive defenses, which attempt to make a network robust, compared to reactive defenses, which attempt to detect adversarial examples. ( 25) defined three ways to obfuscate gradients: shattered gradients, exploding/vanishing gradients, and stochastic gradients.

Shattered gradients are a non-differentiable defense that causes a gradient to be nonexistent or incorrect. This can be done unintentionlly by introducing numeric instability. ( 27) and ( 28) proposed shattered gradients defenses that introduce a non-differentiable and non-linear discretization to a model's input. These transformation are ineffective as black box attacks are agnostic of input randomization.

Exploding gradients make a network hard to train because of an extremely deep neural network. This is generally done by using an output of a neural network as the input of another. ( 29) and ( 30) both proposed defenses that utilize GANs. However, (25) shows that these defenses can be bypassed using transferability of adversarial attacks. The transferability property allows an attacker to use adversarial examples created using one model (often a surrogate model) to fool another model (31) .

Although this is a valid attack vector for even black box models, we do not consider this type of attack in this work.

Stochastic gradients randomize gradients by introducing some randomization to the network or randomly transforming the input to the network. (32) proposed a stochastic gradients defense in which a random subset of activations are pruned. (26) introduced randomness by randomly rescaling input images. (25) showed that an adaptive attacker can bypass these defenses by computing the expected value over multiple queries. We test a similar approach on output randomization and show it is not effective in the black box case (Figure 3b ).

Although other defense methods consider introducing randomness to the input or model itself, this work is the first to our knowledge to consider randomizing the output of the model directly.

7. CONCLUSION:

Black box attacks based on finite difference gradient estimates pose a threat to classification models without needing priveleged access to the model. In this paper, we show that this threat can averted by introducing simple types of randomization to the output of the model. Our empirical results show that even very small (σ 2 = 1e-6) perturbations to the output can prevent these type of attacks.

Although our work shows an encouraging result for defending against black box attacks, we show that output randomization (or other types of randomization) do not prevent white box attacks (25) . Furthermore, output randomization only prevents query based black box attacks and does not address the problem of transfer attacks (33; 31) . Other attacks, such as N Attack (34), utilize derivative-free optimization to find adversarial examples bypassing the need for finite difference estimates. We leave defense against these types of attacks to future work.

:

Our attack code is based on https://github.com/IBM/ZOO-Attack, https://github. com/labsix/limited-blackbox-attacks, and https://github.com/MadryLab/ blackbox-bandits for the ZOO, QL, and BAND attacks respectively.

Figures and Tables:

Figure 1: Controlling misclassification caused by output randomization

Attack success rate vs variance (groups) for adaptive attacker with increasing averaging (10, 50, 100 samples). Averaging allows the white box adaptive attacker to overcome output randomization.

Figure 2: Carlini & Wagner (17) white box attack versus output randomization. Top row shows untargeted attacks, bottom row shows targeted attacks.

Attack success rate (solid) and test set accuracy (dashed) vs variance for the non-adaptive attacker. Output randomization blocks attacks even at very small noise levels (σ 2 < 1e-6).

Attack success rate vs variance (bar groups) for adaptive attacker with increasing averaging (10, 50, 100 samples). Averaging does not improve attack success rate of the black box attacker.

Figure 3: ZOO (18) black box attack versus output randomization. Top row shows untargeted attacks, bottom row shows targeted attacks. Compare this figure with the white box attack results in Figure 2.

1. p c == p o and p c == p o 2. p c == p c and p o == p

Table content: <table/>

Output randomization vs 3 black box attacks on 100 correctly classified ImageNet examples measured by attack success rate (fraction of examples misclassified)

Table content: <table><tr><td colspan="4">Noise Variance ZOO (18) QL (19) BAND (21)</td></tr><tr><td>(undefended)</td><td>0.69</td><td>1.00</td><td>0.92</td></tr><tr><td>1.00e-4</td><td>0.03</td><td>0.73</td><td>0.58</td></tr><tr><td>1.00e-2</td><td>0.00</td><td>0.02</td><td>0.07</td></tr><tr><td>5.76e-2</td><td>0.00</td><td>0.01</td><td>0.06</td></tr></table>

ZOO black box attack success rate vs three defenses

Table content: <table><tr><td>Dataset</td><td>Ex. Type</td><td colspan="3">Distillation(10) Mitigation(26) OR (ours)</td></tr><tr><td>MNIST</td><td>Targeted</td><td>1.00</td><td>-</td><td>0.00</td></tr><tr><td>MNIST</td><td>Untargeted</td><td>0.99</td><td>-</td><td>0.01</td></tr><tr><td colspan="2">CIFAR10 Targeted</td><td>1.00</td><td>-</td><td>0.011</td></tr><tr><td colspan="2">CIFAR10 Untargeted</td><td>1.00</td><td>-</td><td>0.19</td></tr><tr><td colspan="2">ImageNet Untargeted</td><td>-</td><td>0.76</td><td>0.005</td></tr></table>

Peer review (iclr2020):
This paper proposes to introduce randomness in a classifier’s predictions to mitigate black-box attacks that rely on gradient estimation through finite differences. The intuition behind the defense is correct: finite differences rely on the outputs of the neural network being non-deterministic and accurate to estimate gradients near the test points being attacked. However, the threat model chosen in this paper is not well justified: the adversary cannot be forced to use a particular strategy. Unlike what is suggested in Section 3, estimating gradients through finite differences is not the only strategy available in the black-box threat model (this is later mentioned in Section 6). In this case, the adversary could for instance decide to adapt by instead mounting a black-box attack that relies on transferability. Because Figure 2 shows that the defense does not provide robustness in the white-box setting, this suggests that other forms of black-box attacks that either (a) rely on transferability or (b) are label-based only would still evade the model. This limitation should be addressed to understand how applicable the defense strategy is in a realistic deployment. Putting this aside, it is not clear from Figure 3 that an adaptive strategy was evaluated in the limited black-box setting that is considered here (the caption of Figure 3.b only describes a “white-box” adaptive adversary), or that the defense is effective. The attack success rates are high for many graphs and increase as the adversary averages over more runs. Moving forward, increasing further the highest number of runs would help appreciate the limitations of the approach: it is currently set to at most 100, which is low. As far as organization is concerned, a lot of real estate is spent on background material, and few experimental results are presented to support claims made in the introduction. Addressing the above comments would probably require compressing background material a bit. Page-by-page details: 1/ An attack is always adversarial by definition, “adversarial attack” is a tautology. 2 / What do you mean by “successful attacks”? 2/ What do you mean by “strongest” loss? 2/ Having a perturbation limited to be small does not guarantee it won’t impact the semantics of the input, even in the vision domain. Have you verified that the perturbations that you chose left semantics unperturbed? 2/ It is best to avoid making broad statements such as “We use the l2 perturbation penalty as this type of attack results in the strongest attacks” because they are unlikely to hold across datasets and models. 7/ Figures are difficult to parse (e.g., does T and U stand for targeted and untargeted?) 7/ Distillation was already shown to be vulnerable to black-box attacks in [7] 8/ Gradient masking was introduced in [7] prior to [25]. 8/ It would be good to justify the following statement (see my comment above): “Although this is a valid attack vector for even black box models, we do not consider this type of attack in this work”