Year: 2019

Abstract:
Adversarial examples of deep neural networks are receiving ever increasing attention because they help in understanding and reducing the sensitivity to their input. This is natural given the increasing applications of deep neural networks in our everyday lives. When white-box attacks are almost always successful, it is typically only the distortion of the perturbations that matters in their evaluation. In this work, we argue that speed is important as well, especially when considering that fast attacks are required by adversarial training. Given more time, iterative methods can always find better solutions. We investigate this speed-distortion trade-off in some depth and introduce a new attack called boundary projection (BP) that improves upon existing methods by a large margin. Our key idea is that the classification boundary is a manifold in the image space: we therefore quickly reach the boundary and then optimize distortion on this manifold.

heading: 1 INTRODUCTION
text: Adversarial examples (Szegedy et al., 2013) are small, usually imperceptible perturbations of images or other data (Carlini & Wagner, 2018) that can arbitrarily modify a classifier’s prediction. They have been extended to other tasks like object detection or semantic segmentation (Xie et al., 2017), and image retrieval (Li et al., 2018; Tolias et al., 2019). They are typically generated in a white-box setting, where the attacker has full access to the classifier model and uses gradient signals through the model to optimize for the perturbation. They are becoming increasingly important because they reveal the sensitivity of neural networks to their input (Simon-Gabriel et al., 2018; Fawzi et al., 2016; Amsaleg et al., 2017) including trivial cases (Azulay & Weiss, 2018; Engstrom et al., 2017) and they easily transfer between different models (Moosavi-Dezfooli et al., 2016a; Tramèr et al., 2017b).
Adversarial examples are typically evaluated by probability of success and distortion. In many cases, white-box attacks have probability of success near one, then only distortion matters, as a (weak) measure of imperceptibility and also of the ease with which adversarial samples can be detected. The speed of an attack is less frequently discussed. The fast single-step FGSM attack (Goodfellow et al., 2014) produces high-distortion examples where adversarial patterns can easily be recognized. At the other extreme, the Carlini & Wagner (C&W) attack (Carlini & Wagner, 2017), considered state of the art, is notoriously expensive. Decoupling direction and norm (DDN) (Rony et al., 2018) has recently shown impressive progress in distortion but mostly in speed.
Speed becomes more important when considering adversarial training (Goodfellow et al., 2014). This defense, where adversarial examples are used for training, was in fact introduced in the same work as FGSM. The latter remains the most common choice for generating those examples because of its speed. However, unless a powerful iterative attack is used (Madry et al., 2017), adversarial training is easily broken (Tramèr et al., 2017a).
In this work, we investigate in more depth the speed-distortion trade-off in the regime of probability of success near one. We observe that iterative attacks often oscillate across the classification boundary, taking long time to stabilize. We introduce a new attack that rather walks along the boundary. As a result, we improve the state of the art in distortion while keeping iterations at a minimum.
Illustrating the attacks. To better understand how our attack works, we illustrate it qualitatively against a number of existing attacks in Fig. 1. On this toy 2d classification problem, the class boundary and the path followed by the optimizer starting at input x can be easily visualized.
PGD2, an `2 version of I-FGSM (Kurakin et al., 2016), a.k.a. PGD (Madry et al., 2017), is controlled by a distortion target and eventually follows a path on a ball of radius centered at x (cf . Fig. 1(a)). Section 4 shows that varying is an effective yet expensive strategy. It can only be done for a limited set of values so that the optimal distortion target per image may only be found by luck.
C&W (Carlini & Wagner, 2017) depends on a parameter that controls the balance between distortion and classification loss. A low value may lead to failure. A higher value may indeed reach the optimal perturbation, but with oscillations across the class boundary (cf . Fig. 1(b)). Therefore, an expensive line search over is performed internally.
DDN (Rony et al., 2018) (cf . Fig. 1(c)) increases or decreases distortion on the fly depending on success and at the same time pointing towards the gradient direction. It arrives quickly near the optimal perturbation but still suffers from oscillations across the boundary.
On the contrary, boundary projection (BP), introduced in this work (cf . Fig. 1(d)), cares more about quickly reaching the boundary, not necessarily near the optimal solution, and then walks along the boundary, staying mostly in the adversarial (red) region. It therefore makes steady progress towards the solution rather than going back and forth.
Our attack. Our key idea is that, once we reach the adversarial region near the boundary, the problem becomes optimization on a manifold (Absil et al., 2009): in particular, minimization of the `2 distortion on a level set of the classification loss. When in the adversarial region, we project the distortion gradient on the tangent space of this manifold. We do this simply by targeting a particular reduction of the distortion while moving orthogonally to the gradient of the classification loss.
Our benchmark. Quantization is another major issue in this literature. Most papers implicitly assume that the output of a white-box attack is a matrix where pixel values are real numbers in [0; 1]. Rony et al. (2018) is one of the rare works where the output is a quantized. We agree with this definition of the problem. Indeed, an adversarial image is above all an image. The goal of an attacker is to publish images deluding the classifier (for instance on the web), and publishing implies compliance with pixels encoded in bytes.
Contributions. We make the following contributions. To our knowledge, we are the first to
1. Study optimization on the manifold of the classification boundary for an adversarial attack, providing an analysis under a number of constraints, such as staying on the tangent space of the manifold and reaching a distortion target. 2. Investigate theoretically and experimentally the quantization impact on the perturbation. 3. Achieve at the same speed as I-FGSM (Kurakin et al., 2016) (20 iterations) and under the
constraint of a quantization, less distortion than state-of-the-art attacks including DDN, which needs 100 iterations on ImageNet.

heading: 2 PROBLEM, BACKGROUND AND RELATED WORK

heading: 2.1 PROBLEM FORMULATION
text: Preliminaries. Let X := f0; ; : : : ; 1 ; 1gn with := 1=(L 1) denote the set of grayscale images of n pixels quantized to L levels, and let X̂ := [0; 1]n denote the corresponding real-valued images. An image of more than one color channels is treated independently per channel; in this case n stands for the product of pixels and channels. A classifier f : X̂ ! Rk maps an image x to a vector f(x) 2 Rc+ representing probabilities per class over c given classes. The parameters of the classifier are not shown here because they remain fixed in this work. The classifier prediction : X̂ ! [c] := f1; : : : ; cg maps x to the class label having the maximum probability:
(x) := argmax k2[c] f(x)k: (1)
If a true label t 2 [c] is known, the prediction is correct if (x) = t. Problem. Let x 2 X be a given image with known true label t. An adversarial example y 2 X is an image such that the distortion kx yk is small and the probability f(y)t is also small. This problem takes two forms:
1. Target distortion, minimal probability:
min y2X f(y)t (2)
subject to kx yk ; (3) where is a given distortion target. The performance is then measured by the probability of success Psuc := P( (y) 6= t) as a function of .
2. Target success, minimal distortion:
min y2X kx yk (4) subject to (y) 6= t: (5)
The performance is then measured by the expected distortion D := E(kx yk). This work focuses on the second form, but we present example attacks of both forms in section 2.2.
Untargeted attack. The constraint (y) 6= t in (5) is referred to as an untargeted attack, meaning that y is misclassified regardless of the actual prediction. As an alternative, a targeted attack requires that the prediction (y) = t0 is a target label t0 6= t. We focus on the former. Loss function. We focus on a white-box attack in this work. Such an attack is specific to f , which is public. In this setting, attacks typically rely on exploiting the gradient of some loss function, using variants of gradient descent. A classification loss is defined on the probability vector p = f(y) with respect to the true label t. For an untargeted attack, this is typically the negative of cross-entropy
`(p; t) := log pt: (6)
We should warn that, while the cross-entropy is appropriate for bringing examples into the region of class t during classifier training, its negative (6) is in general not appropriate for pulling them out during an attack. This is because this function is mostly flat in the class region. A common solution is to normalize the gradient of ` (Goodfellow et al., 2014; Rony et al., 2018), assuming it is nonzero. We consider more options in this work. A targeted attack on the other hand may use log pt0 , which works fine because it brings examples into class t0 region.
Distortion. This work focuses on the 2-norm k k as a measure of distortion. Alternatives like 1-norm and 1-norm are also common (Goodfellow et al., 2014; Carlini & Wagner, 2017). It is known that none is appropriate for measuring the imperceptibility of adversarial attacks, while more sophisticated measures like structural similarity (SSIM) (Wang et al., 2004) are limited too (Sharif et al., 2018). Measuring imperceptibility is arguably as difficult as classification itself.
Integral constraint. The constraint y 2 X in (3) and (5) is typically relaxed to y 2 X̂ during optimization. Some works conclude the attack by loosely quantizing the optimal solution onto X ,
typically by truncation towards zero. To our knowledge, DDN (Rony et al., 2018) is the only work to do rounding instead, and at the end of each iteration. Quantization is becoming an important issue in adversarial examples because the distortions achieved in recent papers are so small that quantization impacts a lot the perturbations. Appendix A provides a more in-depth study of the impact of the quantization.

heading: 2.2 ATTACKS
text: Target Distortion. Given a distortion target , the fast gradient sign method (FGSM) (Goodfellow et al., 2014) performs a single step in the opposite direction of the (element-wise) sign of the loss gradient with1-norm ,
y := x signrx`(f(x); t): (7) This is the fastest method for problem (2)-(3). In the same work adversarial training was introduced, this method quickly generates adversarial examples for training. However, the perturbations are usually high-distortion and visible. The iterative-FGSM (I-FGSM) (Kurakin et al., 2016) initializes y0 := x and then iterates
yi+1 := projB1[x; ](yi signrx`(f(yi); t)); (8) where projection1 is element-wise to the closed1-norm ball B1[x; ] of radius and center x, and also to X̂ (element-wise clipping to interval [0; 1]). This method is also known as basic iterative method (BIM) (Papernot et al., 2018) and as projected gradient descent (PGD) (Madry et al., 2017). We refer to as PGD2 a 2-norm version replacing (8) with
yi+1 := projB2[x; ](yi (rx`(f(yi); t))); (9) where (x) := x= kxk denotes 2-normalization, and projection is to the closed 2-norm ball B2[x; ] of radius and center x, followed again by element-wise clipping to [0; 1]. Although this method is part of Cleverhans library (Papernot et al., 2018), it is not published according to our knowledge.
Target Success. This family of attacks is typically more expensive. Szegedy et al. (2013) propose a Lagrangian formulation of problem (4)-(5), minimizing the cost function
J(y; c) := kx yk2 + `(f(y); t); (10) where variable is a Lagrange multiplier for (5). They carry out this optimization by boxconstrained L-BFGS.
The attack of Carlini & Wagner (2017), denoted by C&W in the sequel, pertains to this approach. A change of variable eliminates the box constraint, replacing y 2 X by (w), where w 2 Rn and is the element-wise sigmoid function. The classification loss encourages the logit log pt to be less than any other log pk for k 6= t by at least margin m 0,
`m(p; t) := [log pt max k 6=t log pk +m]+; (11)
where [ ]+ denotes the positive part. This function is similar to the multi-class SVM loss by Crammer and Singer (Crammer & Singer, 2001), where m = 1, and, apart from the margin, it is a hard version of negative cross-entropy ` where softmax is producing the classifier probabilities. It does not have the problem of being flat in the region of class t. The C&W attack uses the Adam optimizer (Kingma & Ba, 2015) to minimize the cost function
J(w; ) := k (w) xk2 + `m(f( (w)); t): (12) for w 2 Rn. When the margin is reached, loss `m vanishes and the distortion term pulls (w) back towards x, causing oscillations around the margin. This is repeated for different 2 by line search, which is expensive.
Decoupling direction and norm (DDN) (Rony et al., 2018) is iterating similarly to PGD2 (9),
yi+1 := projS[x; i](yi (rx`(f(yi); t))); (13) 1We define projA(u) := argminv2A ku vk. 2Referred to as c in Carlini & Wagner (2017).
but projection is to the sphere S[x; i] of radius i and center x, and the radius is adapted to the current distortion: It is set to i = (1 )kyi xk if yi is adversarial and to (1 + )kyi xk otherwise, where 2 (0; 1) is a parameter. Another major difference is that each iteration is concluded by a projection onto X (rather than X̂ ) by element-wise clipping to [0; 1] and rounding. Discussion. Optimizing around the class boundary is not a new idea. All of the above attacks do so in order to minimize distortion; implicitly, even attacks targeting distortion like PGD2 do so, if the minimum parameter is sought (cf . Figure 1(a) and Section 4.2). Even black-box attacks do so (Brendel et al., 2018), without having access to the gradient function. The difference of our attack is that our updates are along the class boundary, i.e., in a direction normal to the gradient. DeepFool (Moosavi-Dezfooli et al., 2016b) is a popular attack targeting success, that is not optimizing for distortion and not following a path around the class boundary.

heading: 2.3 OTHER RELATED WORK
text: Optimization on manifolds. In the context of deep learning, stochastic gradient descent on Riemanian manifolds has been studied, e.g. RSGD (Bonnabel, 2013) and RSVRG (Zhang et al., 2016). It is usually applied to manifolds whose geometry is known in analytic form, for instance Grassmann manifolds (Bonnabel, 2013), optimizing orthogonal matrices on Stiefel manifolds (Harandi & Fernando, 2016) or embedding trees on the Poincaré ball (Nickel & Kiela, 2017).
In most cases, the motivation is to optimize a very complex function (e.g. a classification loss) on a well-studied manifold, e.g. matrix manifold (Absil et al., 2009). On the contrary, we are optimizing a very simple quadratic function (the distortion) on a complex manifold not known in analytic form, i.e. a level set of the classification loss.

heading: 3 METHOD
text: Our attack is an iterative process with a fixed number K of iterations. Stage 1 aims at quickly producing an adversarial image, whereas Stage 2 is a refinement phase decreasing distortion. The key property of our method is that while in the adversarial region during refinement, it tries to walk along the classification boundary by projecting the distortion gradient onto the tangent hyperplane of the boundary. Hence we call it boundary projection (BP).

heading: 3.1 STAGE 1
text: This stage begins at y0 = x and iteratively updates in the direction of the gradient of the loss function as summarized in Algorithm 1. The gradient is normalized and then scaled by two parameters: a fixed parameter that is large s.t., with high probability, Stage 1 returns an adversarial image yi 2 X̂ ; and a parameter i that is increasing linearly with iteration i as follows
i := min + i
K + 1 ( max min); (14)
such that updates are slow at the beginning to keep distortion low, then faster until the attack succeeds, where min 2 (0; max) and max = 1. Clipping is element-wise.
Algorithm 1 Stage 1 Input: x: original image to be attacked Input: t: true label (untargeted) Output: y with (y) 6= t or failure, iteration i
1: Initialize y0 x, i 0 2: while ( (yi) = t) ^ (i < K) do 3: ĝ (rx`(f(yi); t)) 4: yi+1 clip[0;1](yi iĝ) 5: i i+ 1 6: end while

heading: 3.2 STAGE 2
text: Once Stage 1 has succeeded, Stage 2 continues by considering two cases: if yi is adversarial, case OUT aims at minimizing distortion while staying in the adversarial region. Otherwise, case IN aims at decreasing the loss while controlling the distortion. Both work with a first order approximation of the loss around yi: `(f(yi + u); t) `(f(yi); t) + u>g; (15) where g = rx`(f(yi); t). The perturbation at iteration i is i := yi x. Stage 2 is summarized in Algorithm 2. Cases OUT and IN illustrated in Fig. 2 are explained below.
Algorithm 2 Stage 2 Input: t: true label (untargeted), i current iteration number Input: yi: current adversarial image, : target distortion Output: yK
1: while i < K do 2: i yi x . perturbation 3: ĝ (rx`(f(yi); t)) . direction 4: r h i; ĝi 5: if (yi) 6= t then . OUT 6: i k ik . target distortion 7: v? x+ rĝ 8: z v? + (yi v?) p [ 2 r2]+
9: yi+1 QOUT(z;yi) 10: else . IN 11: k ik = i . target distortion 12: z yi r + q 2 k ik2 + r2 ĝ
13: yi+1 QIN(z;yi) 14: end if 15: i i+ 1 16: end while
Case OUT takes as input yi outside class t region, i.e. (yi) 6= t. We set a target distortion = i k ik < k ik (14) such that updates decelerate to convergence once the attack has already succeeded. We then solve the following problem:
z := argmin v2V kv yik (16)
V := argmin v2P jkv xk j ; (17)
where P := fv 2 Rn : hv yi; ĝi = 0g is the tangent hyperplane of the level set of the loss at yi, normal to ĝ. The constraint v 2 P aims at maintaining the value of the loss, up to the first order. On this hyperplane, V is the set of points having distortion close to .
Consider the projection v? := x+ rĝ of x onto that hyperplane, where r := h i; ĝi. If r , then V = fv?g, and the solution of (16) is trivially z = v?. Note that v? = yi if i; ĝ are collinear. If r < , there is an infinity of solutions to (17). We pick the one closest to yi:
z = v? + (yi v?) p 2 r2: (18)
This case is illustrated in Fig. 2(a), where V is a circle that is the intersection of sphere S[x; ] and P ; then z is the intersection of V and the line through yi and v?.
Directly quantizing vector z onto X by Q( ), the component-wise rounding, modifies its norm (see App. A). This pulls down our effort to control the distortion. Instead, the process QOUT(z;yi) in line 9 looks for the scale of the perturbation to be applied s.t. kQ(yi + (z yi))k = kzk. This is done with a simple line search over .
Case IN takes as input yi inside class t region, i.e. (yi) = t. We set a target distortion = k ik = i > k ik (14) such that updates decelerate as in Case OUT. We then solve the problem:
z := arg min v2S[x; ]
hv; ĝi ; (19)
i.e., find the point z at the intersection of sphere S[x; ] and the ray through yi in the direction opposite of g as shown in Fig. 2(b). The solution is simple:
z = yi r + q 2 k ik2 + r2 ĝ; (20)
Vector z moves away from yi along direction ĝ by a step size so to reach S[x; ]. Case IN is not guaranteed to succeed, but invoking it means that Stage 1 has succeeded.
Again a direct rounding jeopardizes the norm of the update z yi. Especially, quantization likely results inQ(z) = Q(yi) if kz yik < min = 0:1 (see App. A). Instead of a line search as in method OUT, line 13 just makes sure that this event will not happen: QIN(z;yi) = Q(yi + (z yi)) with = max(1; min=kz yik).

heading: 4 EXPERIMENTS
text: In this section we compare our method boundary projection (BP) to the attacks presented in Sect. 2, namely: FGSM (Goodfellow et al., 2014), I-FGSM (Kurakin et al., 2016), PGD2 (9), C&W (Carlini & Wagner, 2017), and DDN (Rony et al., 2018). This benchmark is carried out on three well-known datasets, with a different neural network for each.

heading: 4.1 DATASETS, NETWORKS, AND PARAMETERS
text: For the target distortion attacks i.e. FGSM, I-FGSM and PGD2, we test a set of and calculate Psuc and D according to our evaluation protocol (cf . section 4.2). For C&W, we test several parameter settings and pick up the optimum setting as specified below. For DDN, the parameter settings are the default (Rony et al., 2018), i.e. 0 = 1:0 and = 0:05. Below we specify different networks and parameters for each dataset.
MNIST (LeCun et al., 2010). We use is a simple network with three convolutional layers and one fully connected layer achieving accuracy 0:99, referred to as C4. The first convolutional layer has 64 features, kernel of size 8 and stride 2; the second has 128 features, kernel 6 and stride 2; the third has also 128 features, but kernel 5 and stride 1. It uses LeakyRelu activation (Maas et al., 2013).
Parameters. We set = 0:08 for I-FGSM and = =2 for PGD2. For C&W: for 5 20 iterations3, learning rate = 0:5 and initial constant = 1:0; for 1 100 iterations, = 0:1 and = 10:0. CIFAR10 (Krizhevsky & Hinton, 2009). We use a simple CNN network with nine convolutional layers, two max-pooling layers, ending in global average pooling and a fully connected layer. Its accuracy is 0:927. Batch normalization (Ioffe & Szegedy, 2015) is applied after every convolutional layer. It also uses LeakyRelu.
Parameters. We set = 0:08 for I-FGSM and = =2 for PGD2. For C&W: for 5 20 iterations, learning rate = 0:1 and initial constant = 0:1; for 1 100 iterations, = 0:01, and = 1:0.
3C&W performs line search on : “5 20” means 5 values of , 20 iterations for each.
ImageNet (Kurakin et al., 2018) comprises 1,000 images from ImageNet (Deng et al., 2009). We use InceptionV3 (Szegedy et al., 2016) whose accuracy is 0:96.
Parameters. We set = 0:08 for I-FGSM and = 3 for PGD2. For C&W: for 5 20 iterations, learning rate = 0:01 and initial constant = 20; for 1 100 iterations, = 0:01 and = 1:0.

heading: 4.2 EVALUATION PROTOCOL
text: We evaluate an attack by its runtime, two global statistics Psuc and D, and by an operating characteristic curve D ! P(D) measuring distortion vs. probability of success as described below. Since we focus on the speed-distortion trade-off, we measure the required time for all attacks. For the iterative attacks, the complexity of one iteration is largely dominated by the computation of the gradient, which requires one forward and one backward pass through the network. It is thus fair to gauge their complexity by this number, referred to as iterations or ‘# Grads’. Indeed, the actual timings of 100 iterations for I-FGSM, PGD2, C&W, DDN and BP are 1.08, 1.36, 1.53, 1.46 and 1.17 s/image on average respectively on ImageNet, using Tensorflow, Cleverhans implementation for I-FGSM and C&W, and authors implementation for DDN.
We measure distortion when the adversarial images are quantized by rounding each element to the nearest element in X . This makes sense since adversarial images are meant to be stored or communicated as images rather than real-valued matrices. DDN and BP adversarial images are already quantized. For reference, we report distortion without quantization in Appendix B.3.
Given a test set of N 0 images, we only consider its subset X of N images that are classified correctly without attack. The accuracy of the classifier is N=N 0. Let Xsuc be the subset of X with Nsuc := jXsucj where the attack succeeds and let D(x) := kx yk be the distortion for image x 2 Xsuc. The global statistics are the success probability Psuc and conditional average distortion D
Psuc := Nsuc N ; D := 1
Nsuc X x2Xsuc D(x): (21)
Here, D is conditioned on success. Indeed, distortion makes no sense for a failure.
We define the operating characteristic of a given attack over the set X as the function P : [0; Dmax] ! [0; 1], where Dmax := maxx2Xsuc D(x). Given D 2 [0; Dmax], P(D) is the probability of success subject to distortion being upper bounded by D,
P(D) := 1
N jfx 2 Xsuc : D(x) Dgj: (22)
This function increases from P(0) = 0 to P(Dmax) = Psuc. We sample one intermediate point: Pupp := P(Dupp) is the success rate within a distortion upper bounded by Dupp 2 (0; Dmax). It is difficult to define a fair comparison of distortion targeting attacks to success targeting attacks (see section 2.2). For the first family, we run a given attack several times over the test set with different target distortion . The attack succeeds on image x 2 X if it succeeds on at least one of the runs, and the distortion D(x) is the minimum distortion over all successful runs. All statistics are then evaluated as above.

heading: 4.3 QUANTIZATION
text: Before addressing the benchmark, Table 1 shows the critical role of quantization in our method BP. Since this attack is iterative and works with continuous vectors, one may quantize only at the end of the process, or at the end of each iteration. Another option is to anticipate the detrimental action of quantizing by adapting the length of each step accordingly, as done by QIN( ) and QOUT( ) in Algorithm 2. The experimental results show that the key is to quantize often so to let the next iterations compensate. Anticipating and adapting gives a substantial extra improvement.

heading: 4.4 ATTACK EVALUATION
text: Table 2 summarizes the global statistics of the benchmark. Fig. 3 offers a more detailed view per dataset with operating characteristic plots.
In terms of average distortion, all iterative attacks perform much better than the single-step FGSM. The performances of C&W are on par with those of I-FGSM, which is unexpected for this more elaborated attack design. The reason is that C&W is put under stress in our benchmark. It usually requires a bigger number of iterations to deliver high quality images. Note that it is possible to avoid the line search on parameter as shown in row 1 100. However, it requires a fine tuning so that this single value works over all the images of the dataset. This is not possible for ImageNet.
DDN and our method BP are clearly ahead of the benchmark. DDN yields lower distortion on MNIST at fewer iterations, but its probability of success is not satisfying. DDN is indeed better than BP only on CIFAR10 at 100 iterations. Fig. 3 reveals that the two attacks have similar operating characteristic on all datasets but this is because it refers to 100 iterations.
In terms of success rate, FGSM fails on MNIST; on CIFAR10, I-FGSM and PGD2 fail as well; finally on ImageNet, C&W fails too. DDN also fails on ImageNet at 20 iterations.
Increasing the number of iterations helps but not at the same rate for all the attacks. For instance, going from 20 to 100 iterations is waste of time for I-FGSM while it is essential for decreasing the distortion of DDN or making PGD2 efficient on ImageNet. Most importantly, our attack BP brings a dramatic improvement in the speed vs. distortion trade-off. Just within 20 iterations, the
distortion achieved on ImageNet is very low compared to the others. Appendix B.2 shows the speed vs. distortion trade-off in more detail.
Statistics of BP stages are as follows: On CIFAR-10 and MNIST, Stage 1 takes 7 iterations on average. On ImageNet, Stage 1 takes on average 3 iterations out of 20, or 8 iterations out of 100.
Appendix C shows examples of images along with corresponding adversarial examples and perturbations for different methods.

heading: 4.5 DEFENSE EVALUATION WITH ADVERSARIAL TRAINING
text: We also test under adversarial training (Goodfellow et al., 2014). The network is re-trained with a dataset composed of the original training set and the corresponding adversarial images. This training is special: at the end of each epoch, the network is updated and fixed, then the adversarial images for this new update are forged by some reference attack, and the next epoch starts with this new set. This is tractable only if the reference attack is fast. We use it with FGSM as the reference attack.
It is more interesting to study DDN and BP as alternatives to FGSM: at 20 iterations, they are fast enough to play the role of the reference attack in adversarial training. In this case, we follow the training process suggested by Rony et al. (2018): the model is first trained on clean examples, then fine-tuned for 30 iterations with adversarial examples. As shown in Table 3, DDN and BP perform equally better than FGSM on CIFAR10, in terms of either average distortion or success rate. Among the reliable attacks (i.e. whose Psuc is close to 1), the worst attack now requires a distortion three times larger than the distortion of the worst attack without defense. In the same way, on MNIST, the distortion of the worst case attack doubles going from 1:37 (baseline) to 2:73 (BP defense). In most cases, BP is a better defense than DDN, forcing the attacker to have 20% more distortion. Note that for a given defense, the strongest attack is almost always BP.

heading: 5 DISCUSSION
text: The main idea of BP is to travel on the manifold defined by the class boundary while seeking to minimize distortion. This travel is operated by the refinement stage, which alternates on both sides of the boundary, but attempts to stay mostly in the adversarial region. Referring to section 2.1, BP is in effect doing for the target success problem what PGD2 is doing for the target distortion problem: BP minimizes distortion on the class boundary manifold (a level set of the classification loss), while PGD2 minimizes the classification loss on a sphere (a level set of the distortion).
BP also takes into account the detrimental effect of quantization. By doing so, the amplitude of the perturbation is controlled from one iteration to another. The main advantage of our attack is the small number of iterations required to achieve both reliability (probability of success close to one) and high quality (low average distortion).

heading: A PREDICTING DISTORTION AFTER QUANTIZATION
text: This appendix aims at predicting the norm of the update after quantization, assuming that it is independent from the computation of the perturbation. Iteration i starts with a quantized image yi 2 X , adds update u 2 Rn, and then quantizes s.t. yi+1 = Q(yi + u). Quantization is done by rounding with := 1=(L 1) the quantization step. Pixel j is quantized to
yi+1;j = yi;j + ej (23)
for some ej 2 Z such that uj 2 (ej =2; ej + =2]. Border effects where yi;j + ej =2 X are neglected.
We now take a statistical point of view where the update is modelled by a random vectorU uniformly distributed over the hypersphere of radius . That parameter is the norm of the perturbation before quantization. This yields random quantization values, denoted by Ej 2 Z for pixel j. The distortion between the two images is
D2 = nX j=1 (yi+1;j yi;j)2 = nX j=1 E2j : (24)
A common approach in source coding theory is the additive noise model for quantization error in the high resolution regime (Gersho & Gray, 1991). It states that Ej = Uj + Qj where Qj 2 ( =2; =2] is the quantization error. When , then Qj becomes uniformly distributed (s.t. E(Qj) = 0 and E(Q2j ) =
2=12) and independent of Uj (s.t. E(UjQj) = E(Uj)E(Qj) = 0). Under these assumptions, Eq. 24 simplifies in expectation to:
E(D2) = E 0 @ nX j=1 U2j +Q 2 j + 2UjQj 1 A = 2 + n 2 12 : (25)
This shows that quantization increases the distortion on expectation.
Yet, this simple analysis is wrong outside the high resolution regime, and we need to be more careful. The expectation of a sum is always the sum of the expectations, whatever the dependence between the summands: E(D2) = Pn j=1 E(E 2 j ) = nE(E 2 j ) with
E(E2j ) = 2 L 1X `=0 `2P(jEj j = ` ): (26)
We need the distribution of Ej to compute the expected distortion after quantizarion. This random variable Ej takes a value depending on the scalar product Sj := U>cj , where cj is the j-th canonical vector. This scalar product lies in [ ; ], so that P(Ej ` ) = 0 if ` =2 > k k. Otherwise, Ej ` when jSj j ` =2, which happens whenU lies inside the dual hypercone of axis cj and semi-angle (`) = arccos(s(`)) with s(`) := (2` 1) =2k k. The probability of this event is equal to the ratio of the solid angles of this dual hypercone and the full space Rn. This quantity can be expressed via the incomplete regularized beta function I , and approximately equals 2 ( p ns(`)=2) for large n. In the end, 8` 2 f0; : : : ; L 1g,
P(jEj j ` ) = 8< : 1; if ` = 0 1 Is(`)2(1=2; (n 1)=2); if 0 s(`) 1 0; otherwise
Computing E(D2) is now possible because P(jEj j = ` ) = P(jEj j ` ) P(jEj j (`+1) ). This expected distortion after quantization depends on , n, and the norm of the perturbation before quantization. Figure 4 shows that quantization reduces the distortion outside the high resolution regime. Indeed, p E(D2) is close to 0 for < 0:1 when n = 3 2992 (i.e. ImageNet). When the update has a small norm , quantization is likely to kill it, yi+1 = yi, and we waste one iteration. On the contrary, p E(D2) converges to p 2 + n 2=12 for large (i.e. in the high resolution regime).
Note that the ratio of the distortions before and after quantization = p
E(D2) quickly converges to 1 for large .

heading: B ADDITIONAL EXPERIMENTS
text: B.1 PARAMETER STUDY
There are two parameters in BP: and min. Both determine the step size of stage 1, while min also determines the step size of stage 2. We consider 4 values for , i.e. 1; 2; 3; 4 and 9 values for min, i.e. 0:1; 0:2; :::; 0:9. For each pair of values, we evaluate BP with 20 iterations on a validation set, which we define as a random subset sampled of the training set: 10000 images for MNIST and CIFAR10, and 1000 images for ImageNet. As shown in Fig. 5, success probability is close to one in all cases, while average distortion is in general stable up to min = 0:8. We choose = 2 and min = 0:7 for all experiments.
B.2 SPEED vs. DISTORTION TRADE-OFF
Figure 6(a) is a graphical view of some results reported in Table 2 with more choices of number of iterations between 20 and 100, and only for ImageNet where our performance gain is the most significant. Just within 20 iterations, its distortion D is already so much lower than that of other attacks, that its decrease (-20% at 100 iterations) is not visible in Fig. 6. On the contrary, more iterations are useless for I-FGSM, and PGD2 can achieve low distortion only with a number of iterations bigger than 50. Figure 6(b) confirms that the probability of success is close to 1 for both DDN and BP for the numbers of iterations considered.
B.3 ATTACK EVALUATION WITHOUT QUANTIZATION
Table 4 is the equivalent of Table 2 but without the integral constraint: the attack is free to output any real matrix provided that the pixel values all belong to [0; 1]. When the distortion is large, there is almost no difference. The model of App. A explains this: We are in the high resolution regime and the extra term in Eq. 25 is negligible compared to the perturbation distortion before quantization. This is especially true when the number of samples n is small (i.e. MNIST, and to some extend, CIFAR-10).
When an attack delivers low distortion on average with real matrices, the quantization may lower the probability of success. This is especially true with the iterative attacks finding adversarial examples just nearby the border between the two classes. Quantization jeopardizes this point and sometimes brings it back in the true class region. More importantly, the impact of the quantization on the distortion is no longer negligible. This is clearly visible when comparing Table 4 and Table 2 for DDN and BP over ImageNet.
Similarly, Fig. 7 is the equivalent of Fig. 3 without the integral constraint. By comparing the two figures, it can be seen that PGD2 and C&W, but also DDN and BP, are improving on ImageNet by having significantly lower distortion. This agrees with measurements of success rate in Table 4, where PGD2 and C&W are not failing as they do in Table 2 with quantization. Our BP is still the strongest attack over all datasets.
B.4 ATTACK EVALUATION ON ROBUST MODELS
Table 5 is similar to Table 2 but is evaluating attacks on robust models. In particular, on MNIST and CIFAR10, we use the same models as described in Section 4.1, which we adversarially train according to Madry et al. (2017). On ImageNet, we use off-the shelf4 InceptionV3 obtained by ensemble adversarial training on four models Tramèr et al. (2017a).
In general, DDN and BP outperform all other attacks in terms of either average distortion D or success rate Pupp. On ImageNet in particular, all other attacks have significantly higher distortion and fail in terms of success rate. DDN and BP have similar performance on CIFAR10. On MNIST, DDN fails in terms of probability of success at 20 iterations, while at 100 iterations BP is superior. On ImageNet, DDN has significantly greater distortion than BP and fails in terms of success rate at 20 iterations, while at 100 iterations BP still has lower distortion.
Fig. 8 is showing a more detailed view of operating characteristics, similarly to Fig. 3 for models trained on natural images. We can see that BP is still ahead of the competition. It is close to DDN, but this is because Fig. 8 refers to 100 iterations. The two attacks outperform all others by a large margin.
4https://github.com/tensorflow/models/tree/master/research/adv_ imagenet_models

heading: C ADVERSARIAL IMAGE EXAMPLES
text: Fig. 9 shows the worst-case ImageNet example for BP along with the adversarial examples generated by all methods and the corresponding normalized perturbations. FGSM has the highest distortion over all methods in this example and BP the lowest. DDN has the highest 1-norm distortion. Observe that for no method is the perturbation visible, although this is a worst-case example.

Review summaries:
This paper introduces a parameterized approach to generate adversarial samples by balancing the speed-distortion trade-off. The method first tries to reach the boundary of classes in the classifier space, then walks on the classifier manifold to find adversarial samples that make the classifier to fail in prediction while minimizing the level of distortion in the sample. Having a limited number of iterations, the method reduces the fluctuations around the boundary and paves the classification manifold.