Title: WALKING ON THE EDGE: FAST, LOW-DISTORTION ADVERSARIAL EXAMPLES

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.

1. INTRODUCTION:

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; Tramè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 (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 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. 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 to low (high) distortion target for PGD 2 (Kurakin et al., 2016 ) (a, in green) or parameter for C&W (Carlini & Wagner, 2017 ) (b). The simulation is only meant to illustrate basic properties of the methods. In particular, it does not include Adam optimizer (Kingma & Ba, 2015) for C&W.

PGD 2 , 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 . , 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 H; I. 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.

2. PROBLEM, BACKGROUND AND RELATED WORK:



2.1. PROBLEM FORMULATION:

Preliminaries. Let Xa fH; ¡; : : : ; I ¡; Ig n with ¡ Xa I=@L IA denote the set of grayscale images of n pixels quantized to L levels, and let Xa H; I 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 f@xA k :

(1)

If a true label t P c is known, the prediction is correct if @xA a t.

Problem. Let x P be a given image with known true label t. An adversarial example y P is an image such that the distortion kx yk is small and the probability f@yA t is also small. This problem takes two forms:

1. Target distortion, minimal probability:

min yP f@yA t (2)

subject to kx yk ;

(

where is a given distortion target. The performance is then measured by the probability of success P suc Xa @@yA T a tA as a function of .

2. Target success, minimal distortion:

EQUATION

subject to @yA T a t:

(5)

The performance is then measured by the expected distortion D Xa i@kx ykA.

This work focuses on the second form, but we present example attacks of both forms in section 2.2.

Untargeted attack. The constraint @yA T a 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 @yA a t H is a target label t H T a 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 a f@yA with respect to the true label t. For an untargeted attack, this is typically the negative of cross-entropy `@p; tA Xa log p t :

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 p t 0 , which works fine because it brings examples into class t H region.

Distortion. This work focuses on the P-norm k¡k as a measure of distortion. Alternatives like I-norm and I-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 P in (3) and ( 5) is typically relaxed to y P during optimization. Some works conclude the attack by loosely quantizing the optimal solution onto , 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.

2.2. ATTACKS:

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 with I-norm , y Xa x sign r x `@f@xA; tA:

(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 y 0 Xa x and then iterates y i+1 Xa proj B1[x;] @y i sign r x `@f@y i A; tAA;

(8)

where projection1 is element-wise to the closed I-norm ball B I xY of radius and center x, and also to (element-wise clipping to interval H; I). 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 PGD 2 a P-norm version replacing (8) with y i+1 Xa proj B2[x;] @y i @r x `@f@y i A; tAAA;

where @xA Xa x=kxk denotes P-normalization, and projection is to the closed P-norm ball B 2 xY of radius and center x, followed again by element-wise clipping to H; I. 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; cA Xa kx yk2 C `@f@yA; tA;

(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 P by @wA, where w P R n and is the element-wise sigmoid function. The classification loss encourages the logit log p t to be less than any other log p k for k T a t by at least margin m ! H, `m@p; tA Xa log p t mx kT =t log p k C 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 a I, 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; A Xa k@wA xk 2 C `m@f@@wAA; tA:

(12)

for w P R n . When the margin is reached, loss `m vanishes and the distortion term pulls @wA 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 PGD 2 (9), y i+1 Xa proj S[x;i] @y i @r x `@f@y i A; tAAA;

(13) but projection is to the sphere SxY i of radius i and center x, and the radius is adapted to the current distortion: It is set to i a @I Aky i xk if y i is adversarial and to @I C Aky i xk otherwise, where P @H; IA is a parameter. Another major difference is that each iteration is concluded by a projection onto (rather than ) by element-wise clipping to H; I 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 PGD 2 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. Deep-Fool (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.

2.3. OTHER RELATED WORK:

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 Poincaré 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.

3. METHOD:

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).

3.1. STAGE 1:

This stage begins at y 0 a 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 y i P

; and a parameter i that is increasing linearly with iteration i as follows i Xa min C i K C I @ max min A;

(14) such that updates are slow at the beginning to keep distortion low, then faster until the attack succeeds, where min P @H; max A and max a I. Clipping is element-wise.

Algorithm 1 Stage 1:

Input: x: original image to be attacked Input: t: true label (untargeted)

Output: y with @yA T a t or failure, iteration i 1: Initialize y 0 2 x, i 2 H 2: while @@y i A a tA @i < KA do 3:

g 2 @r x `@f@y i A; tAA 4: y i+1 2 lip [0;1] @y i i gA 5:

i 2 i C I 6: end while

3.2. STAGE 2:

Once Stage 1 has succeeded, Stage 2 continues by considering two cases: if y i 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 i : `@f@y i C uA;tA % `@f@y i A; tA C u b g;

(15) where g a r x `@f@y i A; tA. 

2 i k i k . target distortion 7: v ? 2 x C r g 8:

z 2 v ? C @y i v ? A p 2 r 2 + 9:

y i+1 2 Q OUT @z; y i A 10: else . IN 11: 2 k i k = i . target distortion 12: z 2 y i r C q 2 k i k 2 C r 2 g 13: y i+1 2 Q IN @z; y i A 14:

end if 15:

i 2 i C I 16: end while Case OUT takes as input y i outside class t region, i.e. @y i A T a t. We set a target distortion a i k i k < k i k (14) such that updates decelerate to convergence once the attack has already succeeded. We then solve the following problem:

z Xa rg min vPV kv y i k

V Xa rg min vPP jkv xk j ;

(17)

where P Xa fv P R n X hv y i ; gi a Hg is the tangent hyperplane of the level set of the loss at y i , normal to g. The constraint v P 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 ? Xa x C r g of x onto that hyperplane, where r Xa h i ; gi. If r ! , then V a fv ? g, and the solution of ( 16) is trivially z a v ? . Note that v ? a y i if i ; g are collinear. If r < , there is an infinity of solutions to (17). We pick the one closest to y i : z a v ? C @y i v ? A p 2 r 2 :

(18

)

This case is illustrated in Fig. 2 (a), where V is a circle that is the intersection of sphere SxY and P ; then z is the intersection of V and the line through y i and v ? . Directly quantizing vector z onto by Q@¡A, the component-wise rounding, modifies its norm (see App. A). This pulls down our effort to control the distortion. Instead, the process Q OUT @z;y i A in line 9 looks for the scale of the perturbation to be applied s.t. kQ@y i C @z y i AAk a kzk. This is done with a simple line search over .

Case IN takes as input y i inside class t region, i.e. @y i A a t. We set a target distortion a i.e., find the point z at the intersection of sphere SxY and the ray through y i in the direction opposite of g as shown in Fig. 2(b ). The solution is simple:

k i k = i > k i k (

EQUATION

Vector z moves away from y i along direction g by a step size so to reach Sx; . 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 y i . Especially, quantization likely results in Q@zA a Q@y i A if kz y i k < min a H:I (see App. A). Instead of a line search as in method OUT, line 13 just makes sure that this event will not happen: Q IN @z; y i A a Q@y i C @z y i AA with a mx@I; min =kz y i kA.

4. EXPERIMENTS:

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) , PGD 2 (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.

4.1. DATASETS, NETWORKS, AND PARAMETERS:

For the target distortion attacks i.e. FGSM, I-FGSM and PGD 2 , we test a set of and calculate P suc 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) 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 H:WT.

Parameters. We set a H:HV for I-FGSM and a Q for PGD 2 . For C&W: for S ¢ PH iterations, learning rate a H:HI and initial constant a PH; for I ¢ IHH iterations, a H:HI and a I:H.

4.2. EVALUATION PROTOCOL:

We evaluate an attack by its runtime, two global statistics P suc and D, and by an operating characteristic curve D 3 P@DA 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, PGD 2 , 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 . 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 H images, we only consider its subset X of N images that are classified correctly without attack. The accuracy of the classifier is N=N H . Let X suc be the subset of X with N suc Xa jX suc j where the attack succeeds and let D@xA Xa kx yk be the distortion for image x P X suc .

The global statistics are the success probability P suc and conditional average distortion D

EQUATION

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 X H; D max 3 H; I, where D max Xa mx xPXsuc D@xA. Given D P H; D max , P@DA is the probability of success subject to distortion being upper bounded by D, P@DA Xa I N jfx P X suc X D@xA Dgj:

(22)

This function increases from P@HA a H to P@D max A a P suc . We sample one intermediate point:

P upp Xa P@D upp A is the success rate within a distortion upper bounded by D upp P @H; D max A.

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 P X if it succeeds on at least one of the runs, and the distortion D@xA is the minimum distortion over all successful runs. All statistics are then evaluated as above. 

4.3. QUANTIZATION:

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 Q IN @¡A and Q OUT @¡A 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.

4.4. ATTACK EVALUATION:

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 I ¢ IHH. 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 PGD 2 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 2 efficient on ImageNet. Most importantly, our attack BP brings a dramatic improvement in the speed vs. distortion trade-off. Just within 20 iterations, the Appendix C shows examples of images along with corresponding adversarial examples and perturbations for different methods.

4.5. DEFENSE EVALUATION WITH ADVERSARIAL TRAINING:

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 P suc 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 I:QU (baseline) to P:UQ (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.

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 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 PGD 2 is doing for the target distortion problem: BP minimizes distortion on the class boundary manifold (a level set of the classification loss), while PGD 2 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).

A PREDICTING DISTORTION AFTER QUANTIZATION:

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 y i P , adds update u P R n , and then quantizes s.t. y i+1 a Q@y i C uA. Quantization is done by rounding with ¡ Xa I=@L IA the quantization step. Pixel j is quantized to y i+1;j a y i;j C e j

for some e j P ¡Z such that u j P @e j ¡=P; e j C ¡=P. Border effects where y i;j C e j = P are neglected.

We now take a statistical point of view where the update is modelled by a random vector U uniformly distributed over the hypersphere of radius . That parameter is the norm of the perturbation before quantization. This yields random quantization values, denoted by E j P ¡Z for pixel j. The distortion between the two images is

EQUATION

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 j a U j C Q j where Q j P @ ¡=P; ¡=P is the quantization error. When ) ¡, then Q j becomes uniformly distributed (s.t. i@Q j A a H and i@Q 2 j A a ¡ 2 =IP) and independent of U j (s.t. i@U j Q j A a i@U j Ai@Q j A a H).

Under these assumptions, Eq. 24 simplifies in expectation to:

EQUATION

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: i@D 2 A a P n j=1 i@E 2 j A a ni@E 2 j A with i@E 2 j A a ¡ 2 L 1 X `=0

`2@jE j j a `¡A:

(26)

We need the distribution of E j to compute the expected distortion after quantizarion. This random variable E j takes a value depending on the scalar product S j Xa U b c j , where c j is the j-th canonical vector. This scalar product lies in ; , so that @E j ! `¡A a H if `¡ ¡=P > kk.

Otherwise, E j ! `¡ when jS j j ! `¡ ¡=P, which happens when U lies inside the dual hypercone of axis c j and semi-angle @`A a ros@s@`AA with s@`A Xa @P` IA¡=Pkk. The probability of this event is equal to the ratio of the solid angles of this dual hypercone and the full space R n . This quantity can be expressed via the incomplete regularized beta function I, and approximately equals P¨@ p ns@`A=PA for large n. In the end, V`P fH; : : : ; L Ig, @jE j j ! `¡A a 8 < :

I; if `a H I I s(`) 2 @I=P; @n IA=PA; if H s@`A I H; otherwise Computing i@D 2 A is now possible because @jE j j a `¡A a @jE j j ! `¡A @jE j j ! @`CIA¡A. 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 i@D 2 A is close to 0 for < H:I when n a Q £ PWW 2 (i.e. ImageNet). When the update has a small norm , quantization is likely to kill it, y i+1 a y i , and we waste one iteration. On the contrary, p i@D 2 A converges to p 2 C n¡ 2 =IP for large (i.e. in the high resolution regime).

Note that the ratio of the distortions before and after quantization = p i@D 2 A quickly converges to 1 for large . 

B ADDITIONAL EXPERIMENTS 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 R values for , i.e. I; P; Q; R and W values for min , i.e. H:I; H:P; :::; H:W. For each pair of values, we evaluate BP with PH iterations on a validation set, which we define as a random subset sampled of the training set: IHHHH images for MNIST and CIFAR10, and IHHH 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 a H:V. We choose a P and min a H:U for all experiments. 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 PGD 2 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. 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 Observe that for no method is the perturbation visible, although this is a worst-case example. 

:

We define proj A (u) := arg minv2A ku vk.

Referred to as c inCarlini & Wagner (2017).

C&W performs line search on : "5 ¢ 20" means 5 values of , 20 iterations for each.

https://github.com/tensorflow/models/tree/master/research/adv_ imagenet_models

Figures and Tables:

Figure 1: 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

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))

R k maps an image x to a vector f@xA P R c + 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 3 c Xa fI; : : : ; cg maps x to the class label having the maximum probability: @xA Xa rg mx kP[c]

Figure 2: Refinement stage of BP. Case OUT when jV j > I (a); case IN (b). See text for details.

Figure 3: Operating characteristics on MNIST, CIFAR10 and ImageNet. The number of iterations is S ¢ PH for C&W and IHH for I-FGSM, PGD 2 , DDN and our BP.

Figure 4: p i@D 2 A as a function of for n a Q £ PWW 2 and ¡ a I=PSS.

Figure 5: Success probability P suc and average distortion D for different values of parameters and min of BP with 20 iterations.

Figure 6: (a) Average distortion vs. number of iterations for I-FGSM, PGD 2 , C&W, DDN and our method BP on ImageNet. I-FGSM is not improving with iterations because it is constrained by . (b) Corresponding probability of success vs. number of iterations for PGD 2 and BP.

Figure 7: Operating characteristics on MNIST, CIFAR10 and ImageNet without quantization. The number of iterations is S ¢ PH for C&W and IHH for I-FGSM, PGD 2 , DDN and our BP.

Figure8: Operating characteristics of attacks against robust models: adversarial training with PGD as the reference attack(Madry et al., 2017) for MNIST and CIFAR10, and ensemble adversarial training(Tramèr et al., 2017a)  for ImageNet. The number of iterations is S ¢ PH for C&W and IHH for I-FGSM, PGD 2 , DDN and our BP.

Figure 9: Original (left), adversarial (top row) and scaled perturbation (below) images against In-ceptionV3 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 are inverted (low is white; high is colored, per channel) and scaled in the same way for a fair comparison. 18

The perturbation at iteration i is i Xa y i x. Stage 2 is summarized in Algorithm 2. Cases OUT and IN illustrated in Fig.2are explained below.

Table content: <table><tr><td>Algorithm 2 Stage 2</td><td/></tr><tr><td>Input: t: true label (untargeted), i current iteration number Input: y i : current adversarial image, : target distortion Output: y K 1: while i &lt; K do 2: i 2 y i x 3: g 2 @r x `@f@y i A; tAA 4: r 2 h i ; gi 5: if @y i A T a t then 6:</td><td>. perturbation . direction . OUT</td></tr></table>

, i.e. 0 a I:H and a H:HS. 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 H:WW, referred to as C4. The first convolutional layer has 64 features, kernel of size V and stride P; the second has IPV features, kernel T and stride P; the third has also IPV features, but kernel S and stride I. It uses LeakyRelu activation(Maas et al., 2013). Parameters. We set a H:HV for I-FGSM and a =P for PGD 2 . For C&W: for S¢PH iterations 3 , learning rate a H:S and initial constant a I:H; for I ¢ IHH iterations, a H:I and a IH:H. Success probability P suc and average distortion D of our method BP on ImageNet with different quantization strategies.

Table content: <table><tr><td>CIFAR10 (Krizhevsky &amp; 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</td></tr></table>

Success probability P suc and average distortion D with quantization. P upp is the success rate under distortion budget D upp a P for MNIST, H:U for CIFAR10, and I for ImageNet.

Table content: <table><tr><td/><td/><td/><td>MNIST</td><td/><td/><td>CIFAR10</td><td/><td/><td>ImageNet</td><td/></tr><tr><td>Attack</td><td># Grads</td><td>Psuc</td><td>D</td><td>Pupp</td><td>Psuc</td><td>D</td><td>Pupp</td><td>Psuc</td><td>D</td><td>Pupp</td></tr><tr><td>FGSM I-FGSM PGD2 C&amp;W DDN</td><td>1 20 100 20 100 5¢20 1¢100 20 100</td><td>0.99 1.00 1.00 1.00 1.00 1.00 0.98 0.82 1.00</td><td>5.80 3.29 3.23 1.80 1.74 1.94 1.90 1.40 1.41</td><td>0.00 0.17 0.18 0.63 0.66 0.56 0.57 0.70 0.87</td><td>0.95 1.00 1.00 1.00 1.00 0.99 0.87 1.00 1.00</td><td>5.65 3.54 3.53 0.66 0.60 0.56 0.38 0.63 0.21</td><td>0.00 0.00 0.00 0.76 0.84 0.81 0.76 0.74 0.98</td><td>0.88 1.00 1.00 0.63 1.00 1.00 0.97 0.99 1.00</td><td>9.18 4.90 4.90 3.63 1.85 1.70 2.57 1.18 0.43</td><td>0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.05 0.97</td></tr><tr><td>BP (this work)</td><td>20 100</td><td>1.00 1.00</td><td>1.45 1.37</td><td>0.86 0.91</td><td>0.97 0.97</td><td>0.49 0.30</td><td>0.87 0.97</td><td>1.00 1.00</td><td>0.35 0.28</td><td>0.96 1.00</td></tr></table>

Success probability P suc , average distortion D, and success rate P upp 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 CIFAR10, it is fine-tuned for 30 extra epochs as suggested by Rony et al. (2018) with DDN and BP, and trained from scratch for 200 epochs with FGSM. P upp measured at distortion D upp a P for MNIST, and H:U for CIFAR10. 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.

Table content: <table><tr><td>Attack 3 5 Defense</td><td/><td>20</td><td colspan="2">PGD2 100</td><td>20</td><td colspan="2">MNIST DDN 100</td><td>20</td><td>BP</td><td>100</td><td>20</td><td colspan="2">PGD2 100</td><td>CIFAR10 DDN 20 100</td><td>20</td><td>BP</td><td>100</td></tr><tr><td>baseline FGSM DDN BP</td><td>Psuc D Pupp Psuc D Pupp Psuc D Pupp Psuc D Pupp</td><td colspan="2">1.00 1.80 0.63 1.00 1.92 0.48 0.99 3.03 0.12 0.94 3.14 0.15</td><td>1.00 1.74 0.66 1.00 1.85 0.53 1.00 2.89 0.14 0.96 3.12 0.15</td><td colspan="2">0.82 1.40 0.70 0.51 1.28 0.44 0.29 1.68 0.20 0.36 1.65 0.24</td><td>1.00 1.41 0.87 1.00 1.60 0.72 1.00 2.38 0.32 1.00 2.81 0.27</td><td>1.00 1.45 0.86 0.89 1.92 0.53 0.99 2.69 0.28 0.95 2.98 0.25</td><td/><td>1.00 1.37 0.91 1.00 1.58 0.73 1.00 2.27 0.34 1.00 2.73 0.26</td><td colspan="2">1.00 0.66 0.76 1.00 0.68 0.72 1.00 0.95 0.52 1.00 0.96 0.55</td><td>1.00 0.59 0.84 1.00 0.62 0.79 1.00 0.94 0.52 1.00 0.94 0.55</td><td>1.00 0.63 0.74 1.00 0.59 0.80 0.98 0.77 0.54 0.97 0.75 0.57</td><td>1.00 0.21 0.98 1.00 0.24 0.98 1.00 0.71 0.55 1.00 0.70 0.59</td><td>0.97 0.49 0.87 0.99 0.67 0.72 1.00 0.75 0.56 1.00 0.76 0.56</td><td>0.97 0.30 0.97 1.00 0.24 0.99 1.00 0.68 0.58 1.00 0.69 0.59</td></tr></table>

is the equivalent of Table2but without the integral constraint: the attack is free to output any real matrix provided that the pixel values all belong to H;I. 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.

Table content: <table/>

without the integral constraint. By comparing the two figures, it can be seen that PGD 2 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 Table4, where PGD 2 and C&W are not failing as they do in Table2with quantization. Our BP is still the strongest attack over all datasets.

Table content: <table><tr><td/><td/><td/><td>MNIST</td><td/><td/><td>CIFAR10</td><td/><td/><td>ImageNet</td><td/></tr><tr><td>Attack</td><td># Grads</td><td>Psuc</td><td>D</td><td>Pupp</td><td>Psuc</td><td>D</td><td>Pupp</td><td>Psuc</td><td>D</td><td>Pupp</td></tr><tr><td>FGSM I-FGSM PGD2 C&amp;W DDN</td><td>1 20 100 20 100 5¢20 1¢100 20 100</td><td>0.99 1.00 1.00 1.00 1.00 1.00 1.00 0.82 1.00</td><td>5.81 3.22 3.16 1.76 1.70 1.93 1.89 1.39 1.41</td><td>0.00 0.27 0.29 0.63 0.66 0.56 0.57 0.70 0.87</td><td>0.97 1.00 1.00 1.00 1.00 1.00 0.97 1.00 1.00</td><td>4.78 3.54 3.53 0.51 0.43 0.56 0.38 0.62 0.20</td><td>0.00 0.00 0.00 0.77 0.85 0.81 0.84 0.74 0.98</td><td>0.85 1.00 1.00 0.64 0.95 1.00 1.00 1.00 1.00</td><td>3.02 4.47 4.47 3.94 1.11 1.37 1.87 0.76 0.28</td><td>0.00 0.00 0.00 0.36 0.61 0.23 0.06 0.95 0.99</td></tr><tr><td>BP (this work)</td><td>20 100</td><td>1.00 1.00</td><td>1.41 1.35</td><td>0.86 0.91</td><td>0.97 0.97</td><td>0.33 0.18</td><td>0.87 0.97</td><td>1.00 1.00</td><td>0.20 0.16</td><td>1.00 1.00</td></tr></table>

Success probability P suc and average distortion D without quantization. P upp measured at

Table content: <table/>

is similar to Table2but 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 toMadry et al. (2017). On ImageNet, we use off-the shelf 4 InceptionV3 obtained by ensemble adversarial training on four modelsTramèr et al. (2017a).In general, DDN and BP outperform all other attacks in terms of either average distortion D or success rate P upp . 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.8is showing a more detailed view of operating characteristics, similarly to Fig.3for 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.8refers to 100 iterations. The two attacks outperform all others by a large margin.

Table content: <table><tr><td/><td/><td colspan="3">MNIST (Madry et al., 2017)</td><td colspan="3">CIFAR10 (Madry et al., 2017)</td><td colspan="3">ImageNet (Tramèr et al., 2017a)</td></tr><tr><td>Attack</td><td colspan="2"># Grads Psuc</td><td>D</td><td>Pupp</td><td>Psuc</td><td>D</td><td>Pupp</td><td>Psuc</td><td>D</td><td>Pupp</td></tr><tr><td>FGSM I-FGSM PGD2 C&amp;W DDN</td><td>1 20 100 20 100 5¢20 1¢100 20 100</td><td colspan="3">0.48 5.69 0.05 1.00 4.99 0.08 1.00 4.99 0.08 0.99 2.76 0.19 1.00 2.68 0.20 0.99 2.75 0.27 0.94 2.22 0.34 0.43 1.61 0.32 1.00 2.12 0.48</td><td colspan="3">0.98 6.21 0.00 1.00 4.53 0.00 1.00 4.56 0.00 1.00 1.03 0.41 1.00 1.02 0.41 0.98 1.41 0.22 0.60 0.77 0.27 0.97 0.92 0.41 1.00 0.87 0.42</td><td colspan="2">0.44 2.98 1.00 4.92 1.00 4.93 0.76 2.14 0.98 1.59 0.98 2.85 0.97 2.41 0.99 1.10 1.00 0.34</td><td>0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.23 0.98</td></tr><tr><td>BP (this work)</td><td>20 100</td><td colspan="3">1.00 2.17 0.46 1.00 2.00 0.51</td><td colspan="3">1.00 0.94 0.41 1.00 0.88 0.43</td><td colspan="2">1.00 0.35 1.00 0.23</td><td>0.94 0.99</td></tr></table>

Success probability P suc , average distortion D, and success rate P upp under adversarial training with PGD as the reference attack, following(Madry et al., 2017) for MNIST and CIFAR10; and ensemble adversarial training(Tramèr et al., 2017a)  for ImageNet. P upp measured at D upp a P for MNIST, H:U for CIFAR10, and I for ImageNet.

Table content: <table/>

Peer review (iclr2020):
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. The 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. - 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. - 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. p.5, l.7: 1(a) -> Figure 1(a) p.8, l.10: measure measure p.8, right after Eq. (21): `*`is conditioned is* -> ``*is conditioned