THWARTING FINITE DIFFERENCE ADVERSARIAL ATTACKS WITH OUTPUT RANDOMIZATION
Year: 2019

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 THREAT MODEL
text: 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 lp distortion penalty on the adversarial image. Common choices for the distortion penalty include l1, l2 and l∞. We use the l2 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.

heading: 3 EXISTING BLACK BOX ATTACKS
text: 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.

heading: 3.1 ZOO BLACK BOX ATTACK
text: 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+ δ∗) = ya
‖x− (x+ δ∗)‖ ≤ Namely, that the perturbed input x + δ∗ successfully fools the classifier f to predict the incorrect class ya 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:
L(x, t) = max { max i 6=t {log f(x)i − log f(x)t},−κ } (1)
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:
L(x) = max { log f(x)i −max
j 6=i
{ log f(x)j } ,−κ } (2)
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− x0‖22 + 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 δxi ≈ gi := L(x+ hei)− L(x− hei) 2h
with ei 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).

heading: 3.2 QUERY LIMITED (QL) BLACK BOX ATTACK
text: 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: xt = xt−1−η · sign(gt), with a step size η and the estimated gradient gt. The estimated gradient for the QL attack using NES is given by:
gt = m∑ i=1 L(x+ σ · ui) · ui − L(x− σ · ui) · ui 2mσ
where ui 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.

heading: 4 THWARTING BLACK BOX ATTACKS
text: 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 adversar-
ial 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.

heading: 4.1 MISSCLASSIFICATION RATE
text: A simple function useful for defending a model is the gaussian noise function d(p) = p+ where is a gaussian random variable with mean µ and variance σ2 ( ∼ N (µ, σ2 · IC)). In the black box setting, a user querying the model with an input x receives the perturbed vector d(p) instead of the true probability vector p. Note that d(p) does not necessarily represent a probability mass function like p.
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 pm and the rest of the elements of p in decreasing order as p2, p3, ...pC .
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(pi) > d(pm))
We can write P(d(pi) > d(pm)) for i = 2, 3, ...C as:
P(d(pi) > d(pm)) = P(pi + i > pm + m)
If we define δi = pm − pi, as shown in Figure 1a, and since ei := i − m is itself a gaussian with mean µi − µm and variance σ2i + σ2m then we can write:
P(ei > δi) = 1− P(ei ≤ δi) = 1− P ( ei − µi + µm σ2i + σ 2 m ≤ δi − µi + µm σ2i + σ 2 m ) Using the cumulative distribution function of a standard gaussian distribution Φ, we can write the misclassification probability as:
K := P(d(pi) > d(pm)) = 1− Φ ( δi − µi + µm σ2i + σ 2 m ) = Φ ( −δi − µi + µm σ2i + σ 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.

heading: 4.2 FINITE DIFFERENCE GRADIENT ERROR
text: 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+ hei and x− hei, close to x (with small h and unit vector ei) 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:
gi = L(f(x+ hei))− L(f(x− hei))
2h
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 |gi − γi|. When d is a function that adds noise to the output of the network, the expected value of the error is:
|E[gi − γi]| = ∣∣∣∣gi − 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: Lu(p) = log(pc)− log(po) = log( pcpo ) where pc is the probability of the true class and po 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[gi − γi]| = ∣∣∣∣gi − 12hE [ log( pc + c po + 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[gi − γi]| ≈ ∣∣∣∣∣σ24h ( σ2 + p2o + p 2′ c
p2′c p 2 o
− σ 2 + p2
′
o + p 2 c
p2cp 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:
1. pc == po and p′c == p ′ o 2. pc == p′c and po == p ′ o
Case 1 cannot occur because it implies the model is predicting two different classes simultaneously. Case 2 will only occur if L(p) == L(p′) which means gi = 0.
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.

heading: 5 EMPIRICAL RESULTS
text: 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 ·IC). Details of both the attacks and defenses can be found in our code 1 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.
1Our 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.
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.

heading: 6 RELATED WORK
text: 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.

heading: 7 CONCLUSION
text: 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 NAttack (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.

Review summaries:
This paper proposes applying randomization to the output layer of a DNN to defend against query-based attacks based on finite difference estimates. Then some theoretical analysis is provided, showing that with perturbation of a suitable scale, the randomization layer will not affect the accuracy of the model, while causing a large estimation error of finite difference methods that prevents finite-difference based attacks. Empirical results verify that the proposed defense is still effective against adaptive attacks where the randomness is averaged.