Walking on the Edge: Fast, Low-Distortion Adversarial Examples
Authors: Hanwei Zhang
Teddy Furon
Yannis Avrithis
Laurent Amsaleg
Venue:  (2020)
Keywords: Deep learning
adversarial attack

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.

Under review as a conference paper at ICLR 2020
WALKING ON THE EDGE: FAST, LOw-DISTORTION ADVERSARIAL EXAMPLES
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial examples of deep neural networks are receiving ever increasing at- tention because they help in understanding and reducing the sensitivity 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- -redddistorrton trude-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.
INTRODUCTION
Adversarial examples (Szegedy 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 al.. (017)) and image retrieval (Li et al. 20188) 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-Gabri Gabriel et al. 2018 Fawzi et al. 2016 Amsaleg et al. 2017) including trivial cases (Azulay & Weiss 201 8 Engstrom et al.]| (0117) and they easily transfer between different models (Moosavi-Deztooll et al. 2016a Tramèr et al. 20175).
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) 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, 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 powerful iterative attack is used (Madry et al. 2017). adversarial training is easily broken (Tramè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 bound- ary, taking long time stabilize. We introduce 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, illustrate it qualitatively against a number of existing attacks in Fig. [ On this toy 2d classification problem, the class boundary and the path followed by the optimizer starting input x can be easily visualized.

---

Under review as a conference paper at ICLR 2020
x
(a) PGD2
(b) C&W
(c) DDN
(d) BP (this work)
Figure I: Adversarial attacks on a binary classifier in two dimensions. The two class regions are shown in red and blue. Contours indicate class probabilities. The objective is to find a point in the red (adversarial) region that is at the minimal distance to input x. Gray (black) paths correspond low (high) distortion target for PGD; (Kurakin al., 2016) (a, in green) or parameter for C&W (Carlini & Wagner (017) (b). The simulation is only meant to illustrate basic properties of the methods. In particular, does not include Adam optimizer (Kingma & Ba 2015) C&W W.
PGD2, by version of I-FGSM (Kurakin 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. [a]). Section 4 shows that varying is an effective yet expensive strategy. It can only be done for limited set of values so that the optimal distortion target per image may only be found by luck.
C&W (Carlini & Wagner 2017) depends tion 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 (ef. Fig. lb). Therefore, an expensive line search over À is performed internally.
parameter À that controls the balance between distor-
DDN Ronn al., 2018) (cf. Fig. [(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 (ef. Fig. dd), 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 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 la distortion on 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 white-box attack is matrix where pixel values 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 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 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 quantization, less distortion than state-of-ther the--r- art attacks including DDN, which needs 100 iterations on ImageNet.
2

---

Under review as a conference paper at ICLR 2020
2 PROBLEM, BACKGROUND AND RELATED WORK
2.1 PROBLEM FORMULATION
Preliminaries. Let t' {0, A,, ..,,,, 1 -...,,,,,,,,"" 1, with A 1/(L- 1) denote the set of grayscale images of n pixels quantized to L levels, and let X' == [0, 1]"h denote the corresponding real-valued images. An image of more than one color channels is treated independently per channel; in this case stands for the product of pixels and channels. A classifier f X' + E maps an image to a vector fxx) E IRC representing probabilities per class over e given classes. The parameters of the classifier not shown here because they remain fixed in this work. The classifier prediction & [c] (), maps to the class label having the maximum probability:
(x) == arg max fx)) kElcl
(1)
If a true label E [c] is known, the prediction is correct if =t
Problem. Let x E X' be a given image with known true label t. adversarial example y X is an image such that the distortion ||x - yll is small and the probability f(y), is also small. This problem takes two forms:
1. Target distortion, minimal probability:
min f(y): yEX
(2)
subject to ||x - yll S,
(3)
where is given distortion larget. The performance is then measured by the probability of success Psne := P(((y))+ # f) as a function of e.
2. Target success, minimal distortion:
min ||x - yll yEX
(4)
subject to =(y) #
(5)
The performance is then measured by the expected distortion D := E[[[x - yll).
This work focuses on the second form, but we present example attacks both forms section 2.2
Untargeted attack. The constraint न (y) * in (5) is referred to as an untargeted attack, meaning that y misclassified regardless of the actual prediction. As an alternative, a targeted attack requires that the prediction 7 (y) = t' is a target label t' * t. We focus on the former.
Loss function. We focus on a white-box attack in this work. Such an attack 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. classification loss is defined on the probability vector p f(y with respect to the true label f. 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 during classifier training, its negative
(6 is in general not appropriate for pulling them out during an attack. This because this function mostly flat in the class region. A common solution is to normalize the gradient of f (Goodfellow et al. 2014 |ony et al.) 2018), assuming it is nonzero. We consider more options in this work. targeted attack on the other hand may use - logpr, pr. which works fine because it brings examples into class t' region.
Distortion. This work focuses on the 2-norm ||:|| as measure of distortion. Alternatives like 1-norm and co-norm are also common (Goodfellow al. 2014] Carlini & Wagner 2017). It is known that none is appropriate for measuring the imperceptibility sophisticated measures like structural similarity (SSIM) (Wang et al. (004)) are limited too (Shaiil et al. 2018). Measuring imperceptibilityy arguably as difficult as classification itself.
adversarial attacks, while more
Integral constraint. The constraint y E N' in (3) and (5) is typically relaxed to y E L during optimization. Some works conclude the attack by loosely quantizing the optimal solution onto X,
3

---

Under review as a conference paper at ICLR 2020
typically by truncation towards zero. To our knowledge, DDN (onny et 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.
2.2 ATTACKS
Target Distortion. Given distortion target the fast gradient sign method (FGSM) (Goodfellow al., 2014) performs single step in the opposite direction of the (element-wise) sign of the loss gradient with cx-norm
y = esign (x)()(x),1)
This is the fastest method for problem - 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 ierrtive-FGSM (I-FGSM) (Kurakin et al. (016) initializes Yo = x and then itcrates
Yi+1 proj (y: sign V vx((f(vs),t)..
where projection is clement-wise the closed oo-norm ball 3 [x; e] of radius and center x, and also to & (element-wise clipping to interval [0, 1J.. This method is also known as basic iterative method (BIM) (Papernot et al.) 2018) and as projected gradient descent (PGD) (Madry al. 2017) We refer to as PGD2 a 2-norm version replacing (8) with
Y++1 = projo, [x:c]] (y: ( V (((()):)
(9)
where rx) := x/ ||||| denotes 2 --nommalization, and projection is to the closed 2 2-norm ball By[x; e] 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), is not published according to knowledge.
Target Success. This family of attacks is typically more expensive, Szegedy et al. (2013) propose a
Lagrangian formulation of problem 44.5) minimizing the cost function
( r) = ||x- yl1 + xe(())))
(10)
where variable is Lagrange multiplier for 5 They carry out this optimization by box- constrained L-BFGS.
The attack of Carlini & Wagner (017). denoted by C&W in the sequel, pertains to this approach. A change of variable eliminates the box constraint, replacing y X' by (w)) where w I and a is the element-wise sigmoid function. The classification loss encourages the logit log pa to be less than any other log Ps for l * by at least margin m 0,
Lm (p. t) = [log - max log Pk + m]+ k
(11)
where [:]+ denotes the positive part. This function similar to the multi-class SVM loss by Crammer and Singer (Crammer & Singer 200T), where 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
(12) for E R. When the margin is reached, loss f. vanishes and the distortion term pulls (ww) back towards x, causing oscillations around the margin. This is repeated for different X by line search, which is expensive.
J(w, A) == [[a(w) x||² + Xe, ())
Decoupling direction and norm (DDN) Rony et al. 2018) is iterating similarly to PGDa D.
yit
s (y: (Vx(((()))
(13)
We define proj (u)) arg min vll-
Reeerred in Carlini Wagner 2017
4

---

Under review as a conference paper at ICLR 2020
but projection is to the sphere S(x: Pi] of radius Ps and center and the radius is adapted to the current distortion: It is set to P: = (1 >>lly; - x|| if ys adversarial and to (1 + >>lly;
x|| otherwise, where Y (0, 1) is parameter. Another major difference is that each iteration is concluded by projection onto (rather than X²) by element-wise clipping [0, 1] and rounding.
Discussion. Optimizing around the class boundary is not a new idea. All of the above attacks do so in order minimize distortion; implicitly, even attacks targeting distortion like PGD2 do so, if the minimum parameter e is sought (cf. Figure [[a) and Section 4.2). Even black-bor 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, Le., in a direction normal to the gradient. Deep- Fool Moooavi-Dezzoooli et al. 201 a popular attack targeting success, that is not optimizing for distortion and not following path around the class boundary.
2.3 OTHER RELATED WORK
Optimization on manifolds. the context of deep learning, stochastic gradient descent on Rie- manian manifolds has been studied, e.g. RSGD (Bonnabel) (013) and RSVRG (Zhang et al. 2016)) usually applied to manifolds whose geometry known analytic form, for instance Grass- mann manifolds (Bonnabel, 2013), optimizing orthogonal matrices on Stiefel manifolds (Harandi & Fernando 2016) or embedding trees on the Poincaré ball (Nickel & Kiela 2017).
In most cases, the motivation is to optimize a very complex function (e.g. classification loss) well-studied manifold, e.g. matrix manifold (Absil et al. 2009). On the contrary, we are optimizing very simple quadratic function (the distortion) on complex manifold not known in analytic form, iee a level set of the classification loss.
METHOD
Our attack an iterative process with fixed number K of iterations. Stage I aims quickly producing an adversarial image, whereas Stage 2 is a refinement phase decreasing distortion. The key property of our method is that while the adversarial region during refinement, tries to walk along the classification boundary by projecting the distortion gradient onto the tangent hyperplane of the boundary. Hence we call boundary projection (BP).
3.1 STAGE 1
This stage begins at and iteratively updates in the direction of the gradient of the loss function summarized in Algorithm [ 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 y; E Ai; and a parameter that is increasing linearly with iteration as follows
3 = Timin
K +1 (7max - Pmin):
(14)
such that updates are slow at the beginning to keep distortion low, then faster until the attack suc- ceeds, where Ymin E (0, 7 and Tmmxx = 1. Clipping is element-wise.
Algorithm Stage 1
Input: x: original image to be attacked
Input: t: true label (untargeted)
Output: y with v(y) # or failure, iteration i
1: Initialize yo +- x, 0
2: while (m( t) A (i K) do
3: g+
4: Y41 clip
5: i
6: end while
5

---

Under review as a conference paper at ICLR 2020
3.2 STAGE 2
Once Stage I has succeeded, Stage 2 continues by considering two cases: if y; 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 y::
(15) where g = V (x))) t). The perturbation at iteration i is d; :- Stage 2 is summarized in Algorithm Cases OUT and IN illustrated in Fig. 2 are explained below.
Ryf +). ~ t) +u
Algorithm Stage 2
Input: t: true label (untargeted), i current iteration number
Input: y;: current adversarial image, e: target distortion
Output: Yk
while K do
2:
ò; - y;
b perturbation direction
3:
g [==((v((((x))))))
4:
r (8,,,, ())
5:
if (y,) # then
D OUT target distortion
6:
< %/4 ||o:|l
7:
v* + x rg
8:
z + v* +rly; vt) 22
9:
Yi+1 Qou
10:
else
b IN
11:
|| /78
target distortion
12:
-
r v 2 -16,11 +
13:
Yi+1 + Qix(z,ys)
14:
end if
15:
i --i+1
end while
Case OUT takes imput y, outside class region, i.e. (y,) t. We set target distortion e = % || < || (14) such that updates decelerate to convergence once the attack has already succeeded. We then solve the following problem:
Z arg min ||v
yill
(16)
VEV
V arg min vEP
|||v x| cl,
(17)
0} the tangent hyperplane of the level set of the loss at Yis normal to g. The constraint E 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 e.
y., y,,g) where :: (v=
Consider the projection v*
+ rg of x onto that hyperplane, where r (8,, g). Ifr 2 e, then V = {v*), and the solution of (16) is trivially x = v". Note that v* = =y if i, are collinear. < 6, there an infinity of solutions (17.. We pick the closest to y;:
== + - -')=+=
(18)
This case illustrated Fig. a). where is circle that is the intersection of sphere S(x; and P: then is the intersection of and the line through y; and v*.
Directly quantizing vector z onto by Q(-), the component-we rounding, modifies its norm (see App. This pulls down our effort to control the distortion. Instead, the process Qoer (z) in line 9 Tooks for the scale 3 of the perturbation to applied s.t. [|Q(y: 3(z y:))ll = ||]| This is done with simple line search over B.
Case IN takes as input y, inside class region, i.e. =(y;) t. We set a target distortion = [|6.]] /72 ||o:|| (14) such that updates decelerate as in Case OUT. We then solve the problem:
z = arg min (v, vCS'
(19)

---

Under review as a conference paper at ICLR 2020
Yi
x
V
P
(a)
(b)
Figure Refinement stage of BP. Case OUT when V (a): case IN (b). See text for details.
ie., find the point at the intersection of sphere S[x; and the ray through yi in the direction opposite of as shown in Fig. bb... The solution simple:
z = r 11,1 +2 g:
(20)
Vector z moves away from y; along direction -g by a step size so to reach S(x, e]. Case IN is not guaranteed succeed, but invoking it means that Stage has succeeded.
Again a direct rounding jeopardizes the norm of the update z - Y,. Especially, quantization likely results in (z) (yys) if l < 9min 0.1 (sce App.(A). Instead of line search in method y:ll
OUT, line 13 just makes sure that this event will not happen: (2, y:) Q + 3(z y:)) with
max 1, 1mmii//l yell).
EXPERIMENTS
In this section we compare our method boundary projection (BP) to the attacks presented in Sect namely: FGSM (Goodfellow al., 2014), I-FGSM (Kurakin al., 2016), PGDD; (), C&W (Carlini & Wagner 2017), and DDN (Rony et al. 2018). This benchmark is carried out on three well-known datasets, with different neural network for each.
4.1 DATASETS, NETWORKS, AND PARAMETERS
For the target distortion attacks i.e. FGSM, I-FGSM and PGD we test set of e and calculate Pauc and according to our evaluation protocol (ef. 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 the default (Rony et al. 2018). i.e. c = 1.0 and y = 0.05. Below we specify different networks and parameters for each dataset.
MNIST (LeCun et al. (2010). We use a simple network with three convolutional layers and one fully connected layer achieving accuracy 0.99, referred as C4. The first convolutional layer has 64 features, kernel of size 8 and stride 2; the second has 128 features, kernel and stride 2; the third has also 128 features, but kernel and stride It uses Leaky Relu activation (Maas et al. 2013).
Parameters. We set a = 0.08 for I-FGSM and = e/2 22 for PGD2 For C&W: for 5 x 20 iterations learning rate 7 0.5 and initial constant 1.0; for 1 100 iterations, 7j 0.1 and À 10.0.
CIFARIO (Krizhevsky & Hinton, 2009). We use a simple CNN network with nine convolutional layers, two max-pooling layers, ending in global average pooling and fully connected layer. Its accuracy is 0.927. Batch normalization (Ioffe & Szegedy 2015) is applied after every convolutional layer. also uses LeakyRelu.
Parameters. We set 0.08 for I-FGSM and a = e/2 for PGDz For C&W: for 5 x 20 iterations, learning rate 7) = 0.1 and initial constant 0.1; for 1 100 iterations, rj = 0.01, and 1.0.
"C&W performs line search "5 20" means 5 values of X, 20 iterations for each.

---

Under review as a conference paper at ICLR 2020
Graad
Poc
Rounding in the end
20
1.00
1.44
1.00
1,00
0.41
Rounding iteration
100
1.00
0.32
Rounding with Qw. QUET
1.00
100
1,00
0.28
Table 1: Success probability Pauc and average distortion D of our method BP on ImageNet with different quantization strategies.
ImageNet (Kurakin et al.) 2018) comprises 1,000 images from ImageNet (Deng et al. 2009). We use Inception V3 (Szegedy al. 2016) whose accuracy is 0.96.
Parameters. We set a 0.08 for I-FGSM and a 3 for PGD2. For C&W: for x 20 iterations, learning rate 7) 0.01 and initial constant À = 20; for 1 100 iterations, 0.01 and À = 1.0.
4.2 EVALUATION PROTOCOL
We evaluate an attack by its runtime, two global statistics Pas and D, and by an operating charac- teristic curve D - (DD) measuring distortion vs. probability of success as described below.
Since we focus on the speed-distortion trade-off, we measure the required time for 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 gauge their complexity by this number, referred to iterations '# 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 average respectively 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 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 test set of N' images, we only consider its subset X of N images that are classified correctly without attack. The accuracy of the classifier is N/N'. Let X be the subset of X with Nuue := sux where the attack succeeds and let (xx) == ||x yll be the distortion for image x X The global statistics are the success probability Psuc and conditional average distortion D
Naw N
PSuc
D:
Σ D(x).
(21)
N
suc
Xx
Here, D is conditioned on success. Indeed, distortion makes no sense for a failure.
We define the operating characteristic of given attack over the set X as the function P [0, Dmax] + [0, 1]. where Dmax maxxeX... Dxx). Given D E [0, Dmax]. P(D) is the prob- ability of success subject to distortion being upper bounded by D,
1 P(D)
N I Xas D(x) D)}-
(22)
This function increases from P(O) 0 to P(Dmax) = Psnc- We sample one intermediate point: Papp : ((Dg)) is the success rate within a distortion upper bounded by Dupo E D0x)).
It is difficult to define fair comparison of distortion targeting attacks to success targeting attacks (see section 2.2). For the first family, we rum a given attack several times over the test set with different target distortion The attack succeeds on image X if it succeeds at least one of the runs, and the distortion (xx) is the minimum distortion over all successful runs. All statistics then evaluated as above.
8

---

Under review as a conference paper at ICLR 2020
MNIST
CIFAR TO
ImageNet
Attack
Grads
Pus
D
Pape
Pasc
Pape
Pax
D
Pape
FGSM
0.99
9.18
0.00
LEGSM
20
1.00
3.29
0.17
1.00
3.54
0.00
1.00
4,90
0.00
100
1.00
3.23
0.18
1.00
3.53
0.00
1.00
4,90
0.00
1.00
1.00
0.70
0.63
3.63
0.00
PGDs
100
1.00
1.74
0.66
1.00
0.60
0.84
1.00
1.85
0.00
C&W
5x
1.00
1.94
0.56
0.99
0.56
0.81
1.00
1,70
0.00
100
2.57
0.00
20
0.82
1,40
0.70
1.00
0.63
0.74
0.99
1,18
0.05
DDN
100
1.00
1.41
0.87
1.00
0.21
0.98
1.00
0.43
0.97
(this work)
20
1.00
1.45
0.86
0.97
0.49
0.87
1,00
0.35
0.96
100
1.00
1.37
0.91
0.97
0.30
0.97
1.00
0.28
1,00
Table 2: Success probability Psuc and average distortion with quantization. Papp is the success rate under distortion budget Dupp
2 for MNIST, 0.7 for CIFARIO, and for ImageNet.
0.8
0.8
0.8
0.6
0.6
0.6
RCOM
0.1
0.4
0.4
0.2
0.2
0.2
0
D
D
(a) MNIST
(b) CIFARIO
(c) ImageNet
Figure 3: Operating characteristics MNIST, CIFAR10 and ImageNet. The number of iterations
is 5 x 20 for C&W and 100 for I-FGSM, PGD2, DDN and our BP.
4.3 QUANTIZATION
Before addressing the benchmark, Table [ shows the critical role of quantization in method BP. Since this attack is iterative and works with continuous vectors, one may quantize only at the end of the process, at the end of each iteration. Another option to anticipate the detrimental action of quantizing by adapting the length of each step accordingly. as done by Qis(.) and Qorr (-) in Algorithm 2
The experimental results show that the key is quantize often so let the next iterations compensate. Anticipating and adapting gives substantial extra improvement.
4.4 ATTACK EVALUATION
Table 2 summarizes the global statisties of the benchmark. Fig. offeer more detailed view per
datasel 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 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 100. However, requires 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 CIFAR1O at 100 iterations. Fig. 3 reveals that the two attacks have similar operating characteristic on all datasets but this is because refers to 100 iterations.
In terms of success rate, FGSM fails on MNIST; on CIFARIO, I-FGSM and PGD₂ 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 PGD, efficient on ImageNet. Most importantly, our attack BP brings dramatic improvement in the speed vs. distortion trade-off. Just within 20 iterations, the

---

Under review as a conference paper at ICLR 2020
MNIST
CIFARIO
Attack
PGD,
DDN
BP
PGDg
DDN
BP
J Defense
20
100
20
100
20
100
20
100
20
100
20
100
P
1.00
1.00
0.82
1,00
1.00
1,00
1.00
1.00
1.00
1.00
0.97
0.97
haseline
D
1.80
1.74
1.40
1.41
1.45
1.37
0.66
0.59
0.63
0.21
0.49
0.30
Pure
0.63
0.66
0.70
0.87
0.86
0.91
0.76
0.84
0.74
0.98
0.87
0.97
Pax
1.00
1.00
1,00
0.89
1.00
1.00
1.00
1.00
1.00
0.99
FUSM
T7
1.92
1.85
1.28
1.60
1.92
1.58
0.68
0.62
0.59
0.24
0.67
0.24
Par
0.48
0,53
0.44
0.72
0.53
0.73
0.72
0.79
0.80
0.98
0.72
0.99
Pax
0.99
1.00
1.00
1.00
0.98
DDN
3.03
2.27
0.95
0.94
0.77
Pup
0.12
0,14
0.20
0.32
0.28
0.34
0.52
0.52
0.54
0.55
0.56
0.58
Pax
0.94
0.96
0.36
1.00
0.95
1,00
1.00
1.00
0.97
1.00
1.00
1.00
BP
17
3.14
3.12
2.73
0.96
0.94
0.75
0.76
P
0.15
0.15
0.24
0.27
0.25
0.26
0.55
0.55
0.57
0.59
0.56
0.59
Table 3: Success probability Psuce average distortion D, and success rate Pupp under adversarial training defense with I-FGSM, DDN, or BP (with 20 iterations) as the reference attack. For the MNIST, the model is trained from scratch. For CIFARIO, it is fine-tuned for 30 extra epochs as suggested by |ony et al. (2018) with DDN and BP, and trained from scratch for 200 epochs with FGSM. upp measured distortion D Pup = 2 for MNIST, and 0.7 for CIFAR10.
distortion achieved on ImageNet is very low compared 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 takes 7 iterations on average. On ImageNet, Stage takes on average iterations out of 20, or 8 iterations out of 100.
Appendix C shows examples of images along with corresponding adversarial examples and pertur- bations for different methods.
4.5 DEFENSE EVALUATION WITH ADVERSARIAL TRAINING
We also test under adversarial training (Goodffelow 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 with FGSM as the reference attack.
It is more interesting to study DDN and BP 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 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 CIFARIO, in terms of either average distortion or success rate. Among the reliable attacks (i.e. whose l' ae is close to I), 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 a better defense than DDN, forcing the attacker have 20% more distortion. Note that for given defense, the strongest attack is almost always BP.
5 DISCUSSION
The main idea of BP is to travel on the manifold defined by the class boundary while seeking to minimize distortion. This travel 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 BP is in effect doing for the target success problem what PGD, is doing for the target distortion problem: BP minimizes distortion on the class boundary manifold (a level set of the classification loss), while PGD, 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 achieve both reliability (probability of success close one) and high quality (low average distortion).
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithmss on matrix manifolds. Princeton University Press, 2009.
Laurent Amsaleg, James E. Bailey, Dominique Barbe, Sarah Erfani, Michael Houle, Vinh Nguyen, and Miloš Radovanovic. The Vulnerability of Learning to Adversarial Perturbation Increases with Intrinsic Dimensionality. In Proc. of WIFS 2017, Rennes, France, December 2017.
Aharon Azulay and Yair Weiss. Why do deep convolutional networks generalize so poorly to small image transformations? Technical report, 2018.
Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Trunsactions on Automatic Control, 58(9):2217-222,, 2013.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. In ICLR, 2018.
Nicholas Carlini and David Wagner. Towards evaluating robustness of neural networks, IEEE Symp. on Security and Privacy, 2017.
Nicholas Carlini and David Wagner. Audio adversarial examples: Targeted attacks on speech-to-text. Technical report, 2018.
Koby Crammer and Yoram Singer. On algorithmic implementation of multiclass kerne-bbased vector ma- chines. Journal of Machine Learning Research, 2(Dec), 2001.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Li, and Li Fei-Fei. Imagenet: large-scale hierarchical image database. In CVPR, pp. 248-255. Ieee, 2009.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. rotation and translation suffice: Fooling cnns with simple transformations. Technical report, 2017.
Alhussein Fawzi, Seyed-Mohsen Moosavi- Dezfooli, and Pascal Frossard. Robustness of classifiers: From adversarial to random noise. Technical report, 2016.
Doosavi-Dezzooll,
A. Gersho and R.M. Gray. Vector Quantization Signal Compression. The Springer International Series Engineering and Computer Science. Springer US, 1991. ISBN 9780792391814
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and hamessingg adversarial examples. arXiv:1412.6572, 2014.
Mehrtash Harandi and Basura Fernando. Generalized backpropagation, ctude de cas: Orthogonality, Technical report, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. International Conference on Machine Learning, 2015.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv:1412.6980 2015.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, 2009.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. arXiv: /0l../660.0000 00.53333.,, 2016.
Adversarial examples in the physical world.
Alexey Kurakin, lan Goodfellow, Samy Bengio, Yinpeng Dong, Fangzhou Liao, Ming Liang, Tianyu Pang, Jun Zhu, Xiaolin Hu, Cihang Xie, et al. Adversarial attacks and defences competition. 1804 00097, 2018.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. AT&T Labs [Online]. Avail- able: http://yann. lecun. com/exdh/nmisr, 2, 2010.
Jie Li, Rongrong Ji, Hong Liu, Xiaopeng Hong, Yue Gao, and Qi Tian. Universal perturbation attack against image retrieval. Technical report, 2018.
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlincarities improve neural network acoustic models. In ICML, volume 30, 2013.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep 2017.
learning models resistant adversarial attacks.
11

---

Under review as a conference paper at ICLR 2020
Seyed-Mohsen Moosavi-Dezfoolii Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. arXiv:/610.08401, 2016a.
Seyed-Mohsen Moosavi-Dezfore Albussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In CVPR, 2016b.
Maximilian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Technical report, 2017.
Nicolas Papernot, Fartash Faghri, Nicholas Carlini, Ian Goodfellow, Reuben Feinman, Alexey Kurakin, Cihang Xie. Yash Sharma, Tom Brown, Aurko Roy, Alexander Matyasko, Vahid Behzadan, Karen Hambardzumyan, Zhishuai Zhang, Yi-Lin Juang, Zhi Li, Ryan Sheatsley, Abhibhav Garg, Jonathan Uesato, Willi Gierke, Yinpeng Dong, David Berthelot, Paul Hendricks, Jonas Rauber, and Rujun Long. Technical report on the cleverhans 12.1.0 adversarial examples library.
2018.
Jéróme Rony. Luiz G. Hafemann, Luis S. Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. Decoupling direction and norm for efficient gradient-based 12 adversarial attacks and defenses. Technical report, 2018.
Mahmood Sharif, Lujo Bauer, and Michael K. Reiter. On the suitability l--n-oms for creating and preventing adversarial examples. arXiv:/802.096:: 2018.
Carl-Johann Limon-Gabriel, Yann Ollivier, Bernhard Schölkopf, Léon Bottou, and David Lopez-Paz. Adver- sarial vulnerability neural networks increases with input dimension. Technical report, 2018.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv: 1312,6199, 2013.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the incep- tion architecture for computer vision. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818 2826, 2016.
G. Tolias, F. Radenovic, and O. Chum. Targeted mismatch adversarial attack: Query with a flower retrieve the tower. In Proc. of ICCV, 2019.
Florian Tramēr, Alexey Kurakin, Nicolas Papernot, Boneh, and Patrick McDaniel. Ensemble adversarial training: Attacks and defenses. 1705::1705.0204 201
Florian Tramèr, Nicolas Papernot, Ian Goodfellow, Dan Bonch, and Patrick McDaniel. The space of transfer- able adversarial examples. arX4::170..03455 2017b.
Zhou Wang, Alan Bovik, Hamid Sheikh, and Eero Simoncelli. Image quality assessment: from error visibility to structural similarity, IEFE Trans. on image processing, 13(4), 2004.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan Yuille. Adversarial examples for semantic segmentation and object detection. arXiv:1703.0800 2017.
Hongyi Zhang, Sashank Reddi, and Suvrit Sra. Riemannian svrg: Fast stochastic optimization on riemannian manifolds, In NIPS, pp. 4592-4600, 2016.
12

---

Under review as a conference paper at ICLR 2020
A PREDICTING DISTORTION AFTER QUANTIZATION
This appendix aims at predicting the norm of the update after quantization, assuming that it is inde- pendent from the computation of the perturbation. Iteration i starts with quantized image y; E X, adds update E IR". and then quantizes s.t. y++1 = Q + + Quantization is done by rounding with A 1 -0-1 the quantization step. Pixel is quantized to
Mitij = yi.jj +
(23)
for some ej AZ such that uj (e, A 2, ej + A2].. Border effects where Vi, + e, X' neglected.
We now take statistical point of view where the update is modelled by random vector U uniformly distributed over the hypersphere of radius p. That parameter is the norm of the perturbation before quantization. This yields random quantization values, denoted by Ej Až for pixel j. The distortion between the two images is
D
(i++ - -wi))² E
(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 E, U; + Q2 where Q2 e A, then Q2 becomes uniformly distributed (s.t.
(- is the quantization error. When E(Q,) 0 and E(Q}) = >²/12) and independent of Uy (s.t. E(U,Q,) = E(U)) = 0).
Under these assumptions, Eq. 24 simplifies in expectation to:
A
E(D?) = E Σ 0Z = + 12
(25)
This shows that quantization increases the distortion on expectation.
Yet, this simple mislysisii is wrong outside the high resolution regime, and we need to be more careful. The expectation of sum is always the sum of the expectations, whatever the dependence between the summands: E(D²)= = E E(EG) = E(E with
E A Σ EP(EE)= = (A).
(26)
We need the distribution of E, to compute the expected distortion after quantizarion. This ran- dom variable Ej takes value depending on the scalar product S, := U cj. where c, is the j-th UTC,
canonical vector. This scalar product lies in [-p, pl. so that PEE; 2 LA) Of - A/2 llell- Otherwise, Ej 2 fA when S, lA A /2, which happens when U lies inside the dual hypercone of axis y, and semi-angle ((E) (rt) with s(E) := (2f- 1) /2||e||. The probability of this event is equal to the ratio of the solid angles of this dual hypercone and the full space Rt. This quantity can be expressed via the incomplete regularized beta function 1, and approximately equals
24( (vnn((e)/2) for large n. In the end, Ve E {O...., 1)..
--1).
1, if 0 P( E, 2 (A)=
Tep 11/2, (m-1)/2), if if0 (() $1) 1
0, otherwise
Computing E E(D?) is now possible because P( = (A) = P(EE (A) PA)E)( > ((+1)A) This expected distortion after quantization depends A, n, and the norm of the perturbation be- fore quantization. Asswws that quantization reduces the distortion outside the high resolution regime. Indeed, /E /E(D*) ) is close to 0 for p < 0.1 when n = 3 * 299 (i.e. ImageNet). When the update has small norm p. quantization is likely kill it, y yi, and we waste one iteration. On the contrary, / /ED converges to /p² 2/2 for large p (i.e. the high resolution regime).
Note that the ratio of the distortions before and after quantization p/ /E(D2) quickly converges to 1 for large p.
13

---

Under review as a conference paper at ICLR 2020
identity
EED2) high res.
1.5
0.5
1.5
P
Figure 4: (D())) as a function of p for n = * 299 and A = 1/255.
B ADDITIONAL EXPERIMENTS
B. PARAMETER STUDY
There are two parameters in BP: and Ymin- Both determine the step size of stage while Ymin also determines the step size of stage 2. We consider values for i.e. 1,2,3, 4 and 9 values for Tmins Lee. 0.1, 0....... 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 CIFARIO, and 1000 images for ImageNet. As shown Fig. 5 success probability close one in all cases, while average distortion is in general stable up to Vminn 0.8. We choose 2 and Tmin 0.7 for all experiments.
2.5
2
15
1.5
1.6
1.5
1.5
0.5
Temin
MNIST
(b) CIFARI0
(c) ImageNet
0.99
0.99
0.99
Poo
Pos
0.98
0.98
0.98
0.97
0.97
0.97
0.96
0.98
0.96
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Tomis
Ymin
Tre io
(d) MNIST
(c) CIFAR1O
(f) ImageNet
Figure 5: Success probability Psuc and average distortion for different values of parameters a and Ymin of BP with 20 iterations.
B.2 SPEED DISTORTION TRADE-OFF
Figure ((a) is graphical view of some results reported in Table 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 attacks, that its decrease (-20% at 100 iterations) not visible in Fig. On the contrary, more iterations useless for I-FGSM, and PGD, achieve low distortion only with number of iterations bigger than 50. Figure b(b) confirms that the probability of success close to for both DDN and BP for the numbers of iterations considered.
much lower than that of other
14

---

Under review as a conference paper at ICLR 2020
DDN
DDN
BP
0.98
BP
7
C&W
1-FGSM
0.94
PGD₂
PGD2
0.92
C&W
0.9
20
40
60
80
100
20
40
60
80
100
Grad
Grad
(b)
Figure 6: (a) Average distortion number of iterations for I-FGSM, PGD2, C&W, DDN and our method BP on ImageNet. I-FGSM is not improving with iterations because is constrained by c. (b) Corresponding probability of success number of iterations for PGD, and BP.
B.3 ATTACK EVALUATION WITHOUT QUANTIZATION
Table the equivalent of Table Dabble2bur 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. App.[AJes exppains this: We are in the high resolution regime and the extra term in Eq. 25]is is negligible compared to the perturbation distortion before quantization. This is especially true when the number of samples is small (Lee. 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 back in the true class region. More importantly, the impact of the quantization on distortion is longer negligible. This is clearly visible when comparing Table 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 PGD, and C& 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 PGD, and C& W are not failing as they do in Table 2 with quantization. Our BP is still the strongest attack over all datasets.
MNIST
CIFAR I0
ImageNet
Attack
Grads
P.s.
D
Pape
Pas
D
Pur
P.x
D
Pare
0.99
3,02
0.00
LFGSM
20
1.00
3.22
0.27
1.00
3.54
0.00
1.00
4.47
0.00
100
1.00
3.16
0.29
1.00
3.53
0.00
1.00
4.47
0.00
1.00
1.76
1.00
0.51
0.77
3.94
0.36
PGDs
100
1.00
1.70
0.66
1.00
0.43
0.85
0.95
1.11
0.61
C&W
5x220
1.00
1.93
0.56
1.00
0.56
0.81
1.00
1.37
0.23
0.06
DDN
20
0.82
1.39
0.70
1.00
0.62
0.74
1.00
0.76
0.95
100
1.00
1.41
0.87
1.00
1.00
0.28
0.99
BP (this work)
20
1.00
1.41
0.86
0.97
0.33
0.87
1.000
0.20
1.00
100
1.00
1.35
0.91
0.97
0.18
0.97
1.00
0.16
1.00
Table 4: Success probability Puu: and average distortion D without quantization. Pupp measured at D upp for MNIST, 0.7 for CIFARI0, and 1 for ImageNet.
15

---

Under review as a conference paper at ICLR 2020
C4N
0.8
0.8
0.8
DBN
Pa
0.2
100g
0
4
4
D
(a) MNIST
(b) CIFARTO
(c) ImageNet
Figure 7: Operating characteristics on MNIST, CIFARIO and ImageNet without quantization. The
number of iterations is 5 x 20 for C&W and 100 for I-FGSM, PGD2, DDN and our BP.
B.4 ATTACK EVALUATION ON ROBUST MODELS
Table 5 is similar to Table but is evaluating attacks on robust models. particular, on MNIST and CIFARIO, according to Madry et al. 2017). On ImageNet, we use off-the shelf Inception V3 obtained by ensemble adversarial training four models Tramer al. (0077)).
the same models as deseribed in Section 4.1 which we adversarially train
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 CIFÁR1O. 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. ( 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 DDN, but this is because Fig. g refers to 100 iterations. The two attacks outperform all others by large margin.
MNIST
CIFARIO
ImageNet Tramšr al.
Madry
2017
Madry al. 2017
2017g)
Attack
Grads
Poge
Pur
D
Pap
Pac
Pep
FGSM
0.48
5.69
0.05
0.98
6.21
0.00
0.44
2.98
0.00
4.53
1.00
4.92
0.00
I-FGSM
100
1,00
4.99
0.08
1.00
4.56
0.00
1.00
4.93
0.00
20
0.99
2.76
0.19
1.00
1.03
0.41
0.76
2.14
0.00
PGDx
0.98
1.59
0.00
C&W
2x
0.99
2.75
0.27
0.98
1.41
0.23
0.98
2.85
0.00
100
0.94
2.22
0.34
0.60
0.77
0.27
0.97
2.41
0.00
20
0.43
T.61
0.97
0.41
0.99
1.10
0.23
DDN
100
1.00
2.12
0.48
1.00
0.87
0.42
1.00
0.34
0.98
BP (this work)
1.00
0.94
100
1.00
2.00
0.51
1.00
0.88
0.43
1.00
0.23
0.99
Table 5: Success probability Panc, average distortion 77, and success rate Pupp under adversarial training with PGD as the reference attack, following (Madry et al. al. 2017) for MNIST and CIFARIO; and ensemble adversarial training (Tramèr et al. (017 for ImageNet. Pupp measured at Dupp for MNIST, 0.7 for CIFAR10, and for ImageNet.
http:://hhiiaaaaeeeeoooeo////eee imagenet_models
16

---

Under review as a conference paper at ICLR 2020
C4N
0.8
Pa
DIGN
0.2
100g
D
(a) MNIST
(b) CIFARTO
(c) ImageNet ens4
Figure 8: Operating characteristics of attacks against robust models: adversarial training with PGD as the reference attack (Madry et al.) 2017) for MNIST and CIFARIO, and ensemble adversarial training (Tramèr et al., (2077a) for ImageNet. The number of iterations is 5 x for C&W and 100 for I-FGSM, PGD2, DDN and our BP.
C ADVERSARIAL IMAGE EXAMPLES
Fig. 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 oc-norm distortion. Observe that for method is the perturbation visible, although this worst-case example.
17

---

Under review as a conference paper at ICLR 2020
original image
FGSM: D=6.08
L-FGSM: D= 5.05
PGDa: D= 3.23
C&W:
DDN:
BP: D=1.00
D=1.74
D=2.11
D=6.08
D= 4.97
D= 3,23
D=1.84
D=2.02
D=0.86
D=6.07
D= 5.01
D= 3.24
D=2.04
D=1.45
D=0.82
D=6.09
D= 4.98
D= 3.24
D=2.45
D=1.75
D=0.82
D=6.04
D= 5.00
D= 3.22
D=1.82
D=1.67
D=081
Figure 9: Original (left), adversarial (top row) and scaled perturbation (below) images against In- c3ptionV3 on ImageNet. The five images are the worst 5 images for BP requiring the strongest distortions, yet these are smaller than the distortions necessary with all other methods (The red color means that the forged image is not adversarial). Perturbations colored, per channel) and scaled in the same way for a fair comparison.
inverted (low is white; high is
18


Reviews:
[{"review_id": "SJxJXx2Bcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe idea is novel, interesting and well-formulated, while the intuition could be better explained. The paper is a good read, has an adequate amount of literature review, and the results are supporting the claims of the paper: lower distortion while having comparable accuracy, the use of generated samples in fortifying the classifier, and keeping distortion to a reasonable level (qualitative results in appendix). However, one of the claims is to trade the distortion level to speed that needs verifying in the main manuscript, therefore, it is suggested that the section B.1 moves to the main manuscript and discussed more thoroughly. Also the effect of other parameters on this trade-off (such as the number of iterations K).\n\nIt is also interesting to discuss how the algorithm performs in classes that are linearly separable on a toy dataset.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1eWEHyecr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed an adversarial attack method based on optimization on the manifold. The authors claim it is a fast and effective attack even with quantization. \n\nIt would better to also evaluate the method on the state of the art robust models (such as Madry et al ICLR'18) instead of only testing it on natural models. Generating adversarial examples on natural models is rather a well-solved problem and I do not think a 0.1 decrease in L2 norm is a big contribution since it is already so small that humans cannot distinguish. A better way to prove the strength would be to test it on a robust model to achieve higher success rates given a maximum distortion.\n\nI do not think the results in Table 3 are convincing or necessary. It is well-known that the FGSM is so weak that the adversarial examples produced by it are not strong enough for adversarial training. The state of the art adversarial training defense uses the adversarial examples obtained from PGD. Also, a popular way to evaluate model robustness would be to evaluate the attack success rate under a given upper bound of distortion (e.g. 0.3 for MNIST). If there is no constraint on the distortion, we can always achieve a 100% attack success rate by simply use an image from another class. So in Table 3, the authors may either make sure all attacks have a 100% success rate and compare the distortion, or set an upper bound of distortion and compare the success rate (just as in the operating characteristics plot). With the current results, I do not believe the robust training with BP can be any better than FGSM. Similar issues also exist in Table 2. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgdRMs6tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers efficiently producing adversarial examples for deep neural networks and proposes boundary projection (BP), which quickly searches an adversarial example around the classification boundary. The BP approach is tested on three benchmark datasets and compared with existing adversarial attacking methods.\n\nThe key idea of BP, searching on the class boundary manifold, is interesting and promising. However, despite the excess of the recommended 8 pages, the main parts of the proposed method are not so clearly explained.\n\n- It is not so clear which parts of the proposed method (Section 3) are mathematically justified. For example, \\gamma_i in Eq. (14) looks heuristically introduced.\n- Although the abstract and introduction emphasize that the main focus of BP is speed-distortion tradeoff, the experiments section does not discuss it so much and so clearly. While the operating characteristic of probability of success and distortion is mainly discussed, it is unclear which argument most demonstrate the improvement in speed-distortion tradeoff.\n\np.5, l.7: 1(a) -> Figure 1(a)\np.8, l.10: measure measure\np.8, right after Eq. (21): `\"`is conditioned is\" -> ``\"is conditioned\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper the authors highlight the role of time in adversarial training and study various speed-distortion trade-offs. They introduce an attack called boundary projection BP which relies on utilizing the classification boundary. The reviewers agree that searching on the class boundary manifold, is interesting and promising but raise important concerns about evaluations on state of the art data sets. Some of the reviewers also express concern about the quality of presentation and lack of detail. While the authors have addressed some of these issues in the response, the reviewers continue to have some concerns. Overall I agree with the assessment of the reviewers and do not recommend acceptance at this time.
Decision: Reject