Title: Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack

Abstract: The evaluation of robustness against adversarial manipulations of neural networks-based classifiers is mainly tested with empirical attacks as the methods for the exact computation, even when available, do not scale to large networks. We propose in this paper a new white-box adversarial attack wrt the l p -norms for p ∈ {1, 2, ∞} aiming at finding the minimal perturbation necessary to change the class of a given input. It has an intuitive geometric meaning, yields quickly high quality results, minimizes the size of the perturbation (so that it returns the robust accuracy at every threshold with a single run). It performs better or similarly to state-of-the-art attacks which are partially specialized to one l p -norm.

1. Introduction:

The finding of the vulnerability of neural networks-based classifiers to adversarial examples, that is small perturbations of the input able to modify the decision of the models, started a fast development of a variety of attack algorithms. The high effectiveness of adversarial attacks reveals the fragility of these networks which questions their safe and reliable use in the real world, especially in safety critical applications. Many defenses have been proposed to fix this issue (Gu & Rigazio, 2015; Zheng et al., 2016; Papernot et al., 2016; Huang et al., 2016; Bastani et al., 2016; Madry et al., 2018) , but with limited success, as new more powerful attacks showed (Carlini & Wagner, 2017b; Athalye et al., 2018; Mosbach et al., 2018) . In order to trust the decision of a model, it is necessary to evaluate the exact adversarial robustness. Although this is possible for ReLU networks (Katz et al., 2017; Tjeng et al., 2019) these techniques do not scale to commonly used large networks. Thus, the robustness is evaluated approximating the solution of the minimal adversarial perturbation problem through adversarial attacks. One can distinguish attacks into black-box (Narodytska & Kasiviswanathan, 2016; Brendel et al., 2018; Su et al., 2019) , where one is only allowed to query the classifier, and white-box attacks, where one has full control over the network, according to the attack model used to create adversarial examples (typically some l p -norm, but others have become popular as well, e.g. Brown et al. (2017) ; Engstrom et al. (2017) ; Wong et al.), whether they aim at the minimal adversarial perturbation (Carlini & Wagner, 2017a; Chen et al., 2018; Croce et al., 2019) or rather any perturbation below a threshold (Kurakin et al., 2017; Madry et al., 2018; Zheng et al., 2019) , if they have lower (Moosavi-Dezfooli et al., 2016; Modas et al., 2019) or higher (Carlini & Wagner, 2017a; Croce et al., 2019) computational cost. Moreover, it is clear that due to the non-convexity of the problem there exists no universally best attack (apart from the exact methods), since this depends on runtime constraints, networks architecture, dataset, etc. However, our goal is to have an attack which performs well under a broad spectrum of conditions with minimal amount of hyperparameter tuning.

In this paper we propose a new white-box attacking scheme which performs comparably or better than established attacks and has the following features: first, it tries to produce adversarial samples with minimal distortion compared to the original point, measured wrt the l p -norms with p ∈ {1, 2, ∞}. Respect to the quite popular PGD-attack of Madry et al. (2018) this has the clear advantage that our method does not need to be restarted for every threshold if one wants to evaluate the success rate of the attack with perturbations constrained to be in {δ ∈ R d | δ p ≤ }. Thus it is particularly suitable to get a complete picture on the robustness of a classifier with low computational cost. Second, it achieves fast good quality in terms of average distortion or robust accuracy. At the same time we show that increasing the number of restarts keeps improving the results and makes it competitive with the strongest available attacks. Third, although it comes with a few parameters, these mostly generalize across datasets, architectures and norms considered, so that we have an almost off-the-shelf method. Most importantly, unlike PGD and other methods, there is no step size parameter which potentially has to be carefully adapted to every new network.

2. FAB: a Fast Adaptive Boundary Attack:

We first introduce minimal adversarial perturbations, then we recall the definition and properties of the projection wrt the l p -norms of a point on the intersection of a hyperplane and box constraints, as they are an essential part of our attack. Finally, we present our FAB-attack algorithm to generate minimally distorted adversarial examples.

2.1. Minimal adversarial examples:

Let f : R d → R K be a classifier which assigns every input x ∈ R d (with d the dimension of the input space) to one of the K classes according to arg max r=1,...,K f r (x). In many scenarios the input of f has to satisfy a specific set of constraints C, e.g. images are represented as elements of [0, 1] d . Then, given a point x ∈ R d with true class c, we define the minimal adversarial perturbation for x wrt the l p -norm as

δ min,p = arg min δ∈R d δ p , s.th. max l =c f l (x + δ) ≥ f c (x + δ), x + δ ∈ C.

(1)

The optimization problem (1) is non-convex and NP-hard for non-trivial classifiers (Katz et al. (2017) ) and, although for some classes of networks it can be formulated as a mixed-integer program (see Tjeng et al. (2019) ), the computational cost of solving it is prohibitive for large, normally trained networks. Thus, δ min,p is usually approximated by an attack algorithm, which can be seen as a heuristic to solve (1). We will see in the experiments that current attacks sometimes drastically overestimate δ min,p p and thus the robustness of the networks.

2.2. Projection on a hyperplane with box constraints:

Let w ∈ R d and b ∈ R be the normal vector and the offset defining the hyperplane π : w, x + b = 0. Let x ∈ R d , we denote by the box-constrained projection wrt the l p -norm of x on π (projection onto the intersection of the box C = {z ∈ R d : l i ≤ z i ≤ u i } and the hyperplane π) the following minimization problem:

EQUATION

where l i , u i ∈ R are lower and upper bounds on each component of z. For p ≥ 1 the optimization problem (2) is convex. Hein & Andriushchenko (2017) proved that for p ∈ {1, 2, ∞} the solution can be obtained in O(d log d) time, that is the complexity of sorting a vector of d elements, as well as determining that it has no solution.

Since this projection is part of our iterative scheme, we need to handle specifically the case of (2) being infeasible. In this case, defining ρ = sign( w, x + b), we instead compute

EQUATION

whose solution is given componentwise, for every i = 1, . . . , d, by

z i =    l i if ρw i > 0, u i if ρw i < 0, x i if w i = 0 .

Assuming that the point x satisfies the box constraints (as it will be in our algorithm), this is equivalent to identifying the corner of the d-dimensional box defined by the componentwise constraints on z closest to the hyperplane π. Notice that if (2) is infeasible then the objective function of (3) stays positive and the points x and z are strictly contained in the same of the two halfspaces divided by π. Finally, we define the operator

proj p : (x, π, C) -→ z * if Problem (2) is feasible z else (4)

yielding the point which gets as close as possible to π without violating the box constraints.

2.3. FAB Attack:

We introduce now our algorithm to produce minimally distorted adversarial examples, wrt any l p -norm for p ∈ {1, 2, ∞}, for a given point x orig initially correctly classified by f as class c. The high-level idea is that we use the linearization of the classifier at the current iterate x (i) , compute the box-constrained projections of x (i) respectively x orig onto the approximated decision hyperplane and take a convex combinations of these projections depending on the distance of x (i) and x orig to the decision hyperplane, followed by some extrapolation step.

We explain below the geometric motivation behind these steps. The attack closest in spirit is DeepFool (Moosavi-Dezfooli et al. (2016) ) which is known to be very fast but suffers from low quality. DeepFool just tries to find the decision boundary quickly but has no incentive to provide a solution close to x orig . Our scheme resolves this main problem and, together with the exact projection we use, leads to a principled way to track the decision boundary (the surface where the decision of f changes) close to x orig .

If f was a linear classifier then the closest point to x (i) on the decision hyperplane could be found in closed form. Although neural networks are highly non-linear, ReLU networks (neural networks which use ReLU as activation function) are piecewise affine functions and thus locally a linearization of the network is an exact description of the classifier. Let l = c, then the decision boundary between classes l and c can be locally approximated using a first order Taylor expansion at x (i) by the hyperplane

EQUATION

)

Moreover the l p -distance d p (π, x (i) ) of x (i) to π l is given by

EQUATION

)

Note that if d p (π l , x (i) ) = 0 then x (i) belongs to the true decision boundary. Moreover, if the local linear approximation of the network is correct then the class s with the decision hyperplane closest to the point x (i) can be computed as

EQUATION

)

Thus, given that the approximation holds in some large enough neighborhood, the projection proj p (x (i) , π s , C) of x (i) onto π s lies on the decision boundary (unless (2) is infeasible).

Biased gradient step::

The iterative algorithm x (i+1) = proj p (x (i) , π s , C) would be similar to DeepFool except that our projection operator is exact whereas they project onto the hyperplane and then clip to [0, 1] d . This scheme is not biased towards the original target point x orig , thus it goes typically further than necessary to find a point on the decision boundary as basically the algorithm does not aim at the minimal adversarial perturbation. Thus we consider additionally proj p (x orig , π s , C) and use instead the iterative step, with x (0) = x orig , defined as

EQUATION

)

which biases the step towards x orig (see Figure 1 ). Note that this is a convex combination of two points on π s and in C and thus also x (i+1) lies on π s and is contained in C. As we wish Figure 1 : Visualization of FAB-attack scheme, with on the left the case η = 1, on the right η > 1. In blue we represent the next iterate x (i+1) one would get without any bias toward the original point x orig , in green the effect of the bias we introduce and in red the x (i+1) obtained with our scheme in (10). We see that our algorithm tends to stay closer to the original point compared to the one with an unbiased gradient step.

a scheme with minimal amount of parameters, we want to have an automatic selection of α based on the available geometric quantities. Let

δ (i) = proj p (x (i) , π s , C) -x (i) and δ (i) orig = proj p (x orig , π s , C) -x orig .

Note that δ (i) p and δ

(i) orig p

are the distances of x (i) and x orig to π s (inside C). We propose to use for the parameter α the relative magnitude of these two distances, that is

EQUATION

The motivation for doing so is that if x (i) is close to the decision boundary, then we should stay close to this point (note that π s is the approximation of f computed at x (i) and thus it is valid in a small neighborhood of x (i) , whereas x orig is farther away). On the other hand we want to have the bias towards x orig in order not to go too far away from x orig . This is why α depends on the distances of x (i) and x orig to π s but we limit it from above with α max . Finally, we use a small extrapolation step as we noted empirically, similarly to Moosavi-Dezfooli et al. (2016) , that this helps to cross faster the decision boundary and get an adversarial sample. This leads to the final scheme:

EQUATION

)

where α is chosen as in (9), η ≥ 1 and proj C is just the projection onto the box which can be done by clipping. In Figure 1 we visualize the scheme: in black one can see the hyperplane π s and the vectors δ

(i)

orig and δ (i) , in blue the step we would make going to the decision boundary with the DeepFool variant, while in red the actual step we have in our method. The green vector represents instead the bias towards the original point we introduce. On the left of Figure 1 we use η = 1, while on the right we use overshooting η > 1.

Interpretation of proj p (x orig , π s , C)::

The projection of the target point onto the intersection of π s and C is defined as arg min

z∈R d z -x orig p s.th. w, z + b = 0, l i ≤ z i ≤ u i ,

Note that replacing z by x (i) + δ we can rewrite this as arg min

δ∈R d x (i) + δ -x orig p s.th. w, x + δ + b = 0, l i ≤ x i + δ i ≤ u i .

This can be interpreted as the minimization of the distance of the next iterate x (i) + δ to the target point x orig so that x (i) + δ lies on the intersection of the (approximate) decision hyperplane and the box C. This point of view on the projection proj p (x orig , π s , C) again justifies using a convex combination of the two projections in our iterative scheme in (10).

Backward step::

The described scheme finds in a few iterations adversarial perturbations. However, we are interested in minimizing their norms. Thus, once we have a new point x (i+1) , we check whether it is assigned by f to a class different from c. In this case, we apply

EQUATION

that is we go back towards x orig on the segment [x (i+1) , x orig ], effectively starting again the algorithm at a point which is quite close to the decision boundary. In this way, due to the bias of the method towards x orig we successively find adversarial perturbations of smaller norm, meaning that the algorithm tracks the decision boundary while getting closer to x orig .

Final search: Our scheme finds points close to the decision boundary but often they are slightly off as the linear approximation is not exact and we apply the extrapolation step with η > 1. Thus, after finishing N iter iterations of our algorithmic scheme, we perform a last, fast step to further improve the quality of the adversarial examples. Let x out be the closest point to x orig classified differently from c, say s = c, found with the iterative scheme. It holds that

EQUATION

)

Since f is typically non-linear, but close to linear, we compute iteratively for a few steps

EQUATION

each time replacing in (13)

x out with x temp if f s (x temp ) -f c (x temp ) > 0 or x orig with x temp if instead f s (x temp ) -f c (x temp ) < 0.

With this kind of modified binary search one can find a better adversarial sample with the cost of a few forward passes of the network.

Random restarts::

So far all the steps are deterministic. To improve the results, we introduce the option of random restarts, that is x (0) is randomly sampled in proximity of x orig instead of being x orig itself. Most attacks benefit from random restarts, e.g. Madry et al. (2018) ; Zheng et al. ( 2019), especially dealing with gradient-masking defenses (Mosbach et al. (2018) ), as it allows a wider exploration of the input space. We choose to sample from the l p -sphere centered in the original point with radius half the l p -norm of the current best adversarial perturbation (or a given threshold if no adversarial example has been found yet).

Computational cost: Our attack, in Algorithm 1, consists of two main operations: the computation of f and its gradients and solving the projection (2). We perform, for each iteration, a forward and a backward pass of the network in the gradient step and a forward pass in the backward step. The projection can be efficiently implemented to run in batches on the GPU and its complexity depends only on the input dimension. Thus, except for shallow models, its cost is much smaller than the passes through the network. We can approximate the computational cost of our algorithm by the total number of calls of the classifier

EQUATION

)

One has to add the forward passes for the final search, fixed to 3, that happens just once.

2.4. Comparison to DeepFool:

The idea of exploiting the first order local approximation of the decision boundary is not novel but the basis of one of the first white-box adversarial attacks, DeepFool (DF) from Moosavi-Dezfooli et al. (2016) . While DF and our FAB-attack share the strategy of using a linear approximation of the classifier and projecting on the decision hyperplanes, we want to point out many key differences: first, DF does not solve the projection (2) but its simpler version without box constraints, clipping afterwards. Second, their gradient step does not have any bias towards the original point, that is equivalent to α = 0 in (10). Third, DF does Algorithm 1: FAB-attack Input : x orig original point, c original class, N restarts , N iter , α max , β, η, , p Output : x out adversarial example u ← +∞ for j = 1, . . . , N restarts do if j = 1 then x (0) ← x orig ; else x (0) ← randomly sampled s.th. x (0) -x orig p = min{u, } /2;

for i = 0, . . . , N iter -1 do s ← arg min l =c |f l (x (i) )-fc(x (i) )| ∇f l (x (i) )-∇fc(x (i) ) q δ (i) ← proj p (x (i) , π s , C) δ (i) orig ← proj p (x orig , π s , C)

compute α as in Equation ( 9)

x (i+1) ← proj C (1 -α) x (i) + ηδ (i) + α(x orig + ηδ (i) orig ) if x (i+1) is not classified in c then if x (i+1) -x orig p < u then x out ← x (i+1) u ← x (i+1) -x orig p end x (i+1) ← (1 -β)x orig + βx (i+1)

end end end perform 3 steps of final search on x out as in ( 13)

Figure 2 : Ablation study to DeepFool for l ∞ -attacks. The introduction of the convex combination (α max = 0.1, no backward step) already improves over DeepFool. Moreover, if one does our full approach, the case α max = 0 (can be seen as an improved iterative DeepFool) is worse than α max = 0.1 with the same number of restarts. In the plots we show the robust accuracy as a function of the threshold under the different attacks on the l ∞ -AT model on MNIST.

not have any backward step, final search or restart, as it stops as soon as a misclassified point is found (its goal is to provide quickly an adversarial perturbation of average quality). We perform an ablation study of the differences to DF in Figure 2 , where we show the curves of the robust accuracy as a function of the threshold (lower is better). We present the results of DeepFool (blue) and FAB-attack with the following variations: α max = 0.1 and no backward step (magenta), α max = 0 (that is no bias in the gradient step) and no restarts (light green), α max = 0.1 and no restarts (orange), α max = 0 and 100 restarts (dark green) and α max = 0.1 and 100 restarts, that is FAB-attack, (red). We can see how every addition we make to the original scheme of DeepFool contributes to the significantly improved performance of FAB-attack when compared to the original DeepFool. 2019)). For each dataset we consider a naturally trained model (plain) and two adversarially trained ones as in Madry et al. (2018) , one to achieve robustness wrt the l ∞ -norm (l ∞ -AT) and the other wrt the l 2 -norm (l 2 -AT) (see A.1).

3. Experiments:



Attacks::

We compare the performances of FAB-attack to those of attacks representing the state-of-the-art in each norm: DeepFool (DF) (Moosavi-Dezfooli et al. ( 2016)), Carlini-Wagner l 2 -attack (CW) (Carlini & Wagner (2017a) ), Linear Region l 2 -Attack (LRA) (Croce et al. (2019) ), Projected Gradient Descent on the cross-entropy function (PGD) (Kurakin et al., 2017; Madry et al., 2018; Tramèr & Boneh, 2019) , Distributionally Adversarial Attack (DAA) (Zheng et al. ( 2019)), SparseFool (SF) (Modas et al. (2019) ), Elastic-net Attack (EAD) (Chen et al. (2018) ). We use DF from Rauber et al. (2017) , CW and EAD as in Papernot et al. (2017) , DAA and LRA with the code from the original papers, while we reimplemented SF and PGD. For MNIST and CIFAR-10 we used DAA with 50 restarts, PGD and FAB with 100 restarts. For Restricted ImageNet, we used DAA, PGD and FAB with 10 restarts (for l 1 we used 5 restarts, since both methods benefit from more iterations). Moreover, we could not use LRA since it hardly scales to such models and CW and EAD for compatibility issues between the implementations of attacks and models. See A.2 for more details e.g. regarding number of iterations and other hyperparameters.

Evaluation metrics::

The robust accuracy of a model at a threshold is defined as the classification accuracy (in percentage) the model achieves when an attack is allowed to change every input of the test set with perturbations of l p -norm smaller than in order to change the decision. Thus stronger attacks produce lower robust accuracies. For each model and dataset we fix five thresholds at which we compute the robust accuracy for each attack (we choose the thresholds to have values of the robust accuracy that cover the range between clean accuracy and 0). We evaluate the attacks through the following statistics: i) avg. rob. accuracy: the mean of all the values of robust accuracy given by the attack over all models and thresholds, ii) # best: how many times the attack achieves the lowest robust accuracy (it is the most effective), iii) avg. difference to best: for each model/threshold we compute the difference between the robust accuracy of the attack and the best one across all the attacks, then we average over all models/thresholds, iv) max difference to best: as "avg. difference to best", but with the maximum difference instead of the average one. In A.4 we report the average l p -norm of the adversarial perturbations given by the attacks.

Results::

We report the complete results in Tables 5 to 13 of the Appendix, while we summarize them in Tables 1 (MNIST and CIFAR-10 aggregated, as we used the same attacks) and 2 (Restricted ImageNet). Our FAB-attack achieves the best results in all statistics for every norm (with the only exception of "max diff. to best" in l ∞ ) on MNIST+CIFAR-10, meaning that it is the most effective attack. In particular, while on l ∞ the "avg. robust accuracy" of PGD is not far from that of FAB, the gap is large when considering l 2 and l 1 . Interestingly, the second best attack, at least in terms of average robust accuracy, is different for every norm (PGD for l ∞ , LRA for l 2 , EAD for l 1 ), which implies that FAB outperforms algorithms specialized in the individual norms. We also report the results of FAB-10, that is our attack with only 10 restarts, to show that FAB yields high quality results already with a low budget in terms of time/computational cost. In fact, FAB-10 has "avg. robust accuracy" better than or very close to that of the strongest versions of the other methods (see below for a runtime analysis, where one observes that FAB-10 is the fastest attack excluding DF and SF which however give much worse results). On Restricted ImageNet, FAB-attack gets the best results in all statistics for l 1 , while for l ∞ and l 2 , although PGD performs often better, the difference in "avg. robust accuracy" is small, meaning that FAB performs mostly similarly to PGD.

Table 1 : Performance summary of all attacks on MNIST and CIFAR-10 (aggregated). We report, for each norm, "avg. rob. acc.", the mean of the values of robust accuracy across all the models and datasets, "# best", number of times the attack is the best one, "avg. diff. to best" and "max diff. to best", the mean and maximum differences between the robust accuracy of the attack and that of the best attack for each model/threshold (on the first 1000 points for l ∞ and l 1 , 500 for l 2 , of the test sets). The numbers after the name of the attacks indicates the number of restarts used. In total we consider 5 thresholds × 6 models = 30 cases for each of the 3 norms. *Note that for FAB-10 (i.e. with 10 restarts) the "# best" is computed excluding the results of FAB-100. In general, both average and maximum difference to best of FAB-attack are small for all the datasets and norms, implying that it does not suffer severe failures, which makes it an efficient, high quality technique to evaluate the robustness of classifiers for all l p -norms. Finally, we show in Table 4 that FAB-attack outperforms or matches the competitors in 16 out of 18 cases when comparing the average l p -norms of the generated adversarial perturbations.

Runtime comparison: DF and SF are definitely much faster than the others as their primary goal is to find as soon as possible adversarial examples, without emphasis on minimizing their norms, while LRA is rather expensive as noted in the original paper. Below we report the runtimes (for 1000 points on MNIST and CIFAR-10, 50 on R-ImageNet) for the attacks as used in the experiments (if not specified otherwise, it includes all the restarts).

For PGD and DAA this is the time for evaluating the robust accuracy at 5 thresholds, while for the other methods a single run is sufficient to compute all the statistics. MNIST: DAA-50 11736s, PGD-100 3825s for l ∞ /l 2 and PGD-100 14106s for l 1 , CW 944s, EAD 606s, FAB-10 161s, FAB-100 1613s. CIFAR-10: DAA-50 11625s, PGD-100 31900s for l ∞ /l 2 and 70110s for l 1 , CW 3691s, EAD 3398s, FAB-10 1209s, FAB-100 12093s. R-ImageNet: DAA-10 6890s, PGD-10 4738s for l ∞ /l 2 and PGD-5 24158s for l 1 , FAB-10 2268s for l ∞ /l 2 and FAC-5 3146s for l 1 (note that different numbers of restarts/iterations for l 1 are used on R-ImageNet). PGD needs a forward and a backward pass of the network for each iteration. Thus it is given 1.5 times more iterations than FAB, so that overall they have same budget of passes (we assume here that forward and backward passes take the same amount of time). In Appendix B.2 we compare PGD-1 versus FAB-1 as a function of the number of passes (2 passes are one iteration of PGD, 3 passes are one iteration of FAB -the plots show 300 passes meaning 150 iterations of PGD and 100 iterations of FAB) so that the comparison is fair concerning runtime in order to compare the performance of PGD-1 and FAB-1 as a function of runtime.

If one considers just the performance up to 20 passes (10 iterations PGD, 7 iterations FAB) then FAB outperforms PGD in 18 out of 27 cases. However, one also observes that there is no general superiority of one method. For both PGD-1 and FAB-1 there are cases where the method requires the full amount of 300 passes to get to a good performance whereas the other method achieves it with significantly less iterations/passes.

4. Conclusion:

In summary, our geometrically motivated FAB-attack outperforms in terms of runtime and on average in terms of quality all other high quality state-of-the-art attacks and can be used for all p-norms in p ∈ {1, 2, ∞} which is not the case for most other methods.

A Experiments:

A.1 Models

The plain and l ∞ -AT models on MNIST are those available at https://github.com/ MadryLab/mnist_challenge and consist of two convolutional and two fully-connected layers. The architecture of the CIFAR-10 models has 8 convolutional layers (with number of filters increasing from 96 to 384) and 2 dense layers, while on Restricted ImageNet we use the models (ResNet-50 He et al. ( 2016)) from Tsipras et al. ( 2019) and available at https://github.com/MadryLab/robust-features-code.

The models on MNIST achieve the following clean accuracy: plain 98.7%, l ∞ -AT 98.5%, l 2 -AT 98.6%. The models on CIFAR-10 achieve the following clean accuracy: plain 89.2%, l ∞ -AT 79.4%, l 2 -AT 81.2%.

A.2 Attacks:

We use CW with 10000 iterations and confidence 0, EAD with 1000 iterations, l 1 decision rule and β = 0.05. In both cases we set the parameters to achieve minimally (wrt l 2 for CW and l 1 for EAD) distorted adversarial examples. We could not use these methods on Restricted ImageNet since, to be compatible with the attack from Papernot et al. (2017) , it would be necessary to reimplement from scratch the models of Tsipras et al. ( 2019), as done in https://github.com/tensorflow/cleverhans/tree/master/ cleverhans/model_zoo/madry_lab_challenges for a similar situation.

For DAA we use 200 iterations for MNIST, 50 for the other datasets and, given a threshold , a step size of /30 for MNIST, /10 otherwise.

We perform PGD with 150 iterations, except for the case of l 1 on Restricted ImageNet where we use 450 iterations. For PGD wrt l ∞ we use, given a threshold , a step size of /10 in the direction of the sign of the gradient of the cross entropy loss, for PGD wrt l 2 we perform at each iteration a step in the direction of the gradient of size /4, for PGD wrt l 1 we use the gradient step suggested in Tramèr & Boneh (2019) (with sparsity levels of 1% for MNIST and 10% for CIFAR-10 and Restricted ImageNet), with size /2. The above stepsize parameters /4 for l 2 and /10 for l ∞ for PGD were obtained, by doing a grid search for each norm separately and using the values working best on average on MNIST and CIFAR-10. In Appendix we discuss the influence of the step-size and show that our chosen values perform best on average, see Figure 3 .

For FAB-attack we set 100 iterations, except for the case of l 1 on Restricted ImageNet where we use 300 iterations. Moreover, we use the following parameters for all the cases on MNIST and CIFAR-10: α max = 0.1, η = 1.05, β = 0.9. On Restricted ImageNet we set α max = 0.05, η = 1.3, β = 0.9. When using random restarts, FAB-attack needs a value for the parameters . It represents the radius of the l p -ball around the original point inside which we sample the starting point of the algorithm, at least until a sufficiently small adversarial perturbation is found (see Algorithm 1). We use the values of reported in Table 3 . Note however that the attack usually finds at the first run an adversarial perturbation small enough so that in practice rarely comes into play. 

A.3 Complete results:

In Tables 5 to 13 we report the complete values of the robust accuracy, wrt either l ∞ , l 2 or l 1 , computed by every attack, for 3 datasets, 3 models for each dataset, 5 thresholds for each model (135 evaluations overall).

A.4 Further results:

In Table 4 we report the average l p -norm of the adversarial perturbations found by the different attacks, computed on the originally correctly classified points on which the attack is successful. Note that we cannot show this statistic for the attacks which do not minimize the distance of the adversarial example to the clean input (PGD and DAA). FAB-attack produces also in this metric the best results in most of the cases, being the best for every model when considering l ∞ and l 2 , and the best in 4 out of 6 cases in l 1 (lower values mean a stronger attack). We compare the robust accuracy of PGD-1 (magenta) and FAB-1 (black) as a function of the employed forward/backward passes in the algorithm (one iteration of PGD corresponds to 2 passes, one iteration of FAB corresponds to 3 passes). Models: plain in the first column, l ∞ -at in the second and l 2 -at in the third. Threat models: l ∞ in the first row, l 2 in the second and l 1 in the third. The thresholds used can be read above the plots. Note that the result of FAB-1 on l ∞ -at wrt l 1 does not match that in Table 6 due to a typo in the statistics in the table.

:



Figures and Tables:

We run experiments on MNIST, CIFAR-10 (Krizhevsky et al.) and Restricted ImageNet (Tsipras et al. (

Figure4: Evolution of accuracy across iterations on MNIST. We compare the robust accuracy of PGD-1 (magenta) and FAB-1 (black) as a function of the employed forward/backward passes in the algorithm (one iteration of PGD corresponds to 2 passes, one iteration of FAB corresponds to 3 passes). Models: plain in the first column, l ∞ -at in the second and l 2 -at in the third. Threat models: l ∞ in the first row, l 2 in the second and l 1 in the third. The thresholds used can be read above the plots. Note that the result of FAB-1 on l ∞ -at wrt l 1 does not match that in Table6due to a typo in the statistics in the table.

As in Table1statistics of the performance of different attacks on Restricted ImageNet (on the first 500 points of the validation set). In total we consider 5 thresholds × 3 models = 15 cases for each of the 3 norms.

Table content: <table><tr><td/><td/><td colspan="6">statistics on Restricted ImageNet</td><td/><td/><td/></tr><tr><td/><td/><td colspan="2">l∞-norm</td><td/><td/><td>l2-norm</td><td/><td/><td>l1-norm</td><td/></tr><tr><td/><td>DF</td><td>DAA-</td><td>PGD-</td><td>FAB-</td><td>DF</td><td>PGD-</td><td>FAB-</td><td colspan="2">EAD PGD-</td><td>FAB-</td></tr><tr><td/><td/><td>10</td><td>10</td><td>10</td><td/><td>10</td><td>10</td><td/><td>5</td><td>5</td></tr><tr><td>avg. rob. acc.</td><td colspan="4">35.61 38.44 26.91 27.83</td><td colspan="3">45.69 31.75 33.24</td><td colspan="3">71.31 40.64 38.12</td></tr><tr><td># best</td><td>0</td><td>1</td><td>13</td><td>3</td><td>0</td><td>14</td><td>1</td><td>0</td><td>3</td><td>12</td></tr><tr><td>avg. diff. best</td><td>8.75</td><td colspan="2">11.57 0.04</td><td>0.96</td><td colspan="2">13.99 0.04</td><td>1.53</td><td colspan="2">33.52 2.85</td><td>0.33</td></tr><tr><td>max diff. best</td><td colspan="3">14.60 37.20 0.40</td><td>2.00</td><td colspan="2">25.40 0.60</td><td>3.40</td><td colspan="2">59.00 6.20</td><td>2.40</td></tr></table>

We report the values of used for sampling in case our FAB-attack uses random restarts.

Table content: <table><tr><td/><td/><td/><td colspan="4">values of used for random restarts</td><td/><td/><td/></tr><tr><td/><td/><td>MNIST</td><td/><td/><td>CIFAR-10</td><td/><td colspan="3">Restricted ImageNet</td></tr><tr><td/><td>plain</td><td>l∞-AT</td><td>l2-AT</td><td>plain</td><td>l∞-AT</td><td>l2-AT</td><td>plain</td><td>l∞-AT</td><td>l2-AT</td></tr><tr><td>l∞</td><td>0.15</td><td>0.3</td><td>0.3</td><td>0.0</td><td>0.02</td><td>0.02</td><td>0.02</td><td>0.08</td><td>0.08</td></tr><tr><td>l2</td><td>2.0</td><td>2.0</td><td>2.0</td><td>0.5</td><td>4.0</td><td>4.0</td><td>5.0</td><td>5.0</td><td>5.0</td></tr><tr><td>l1</td><td>40.0</td><td>40.0</td><td>40.0</td><td>10.0</td><td>10.0</td><td>10.0</td><td>100.0</td><td>250.0</td><td>250.0</td></tr></table>

We report mean l p -norm of the adversarial perturbations found by the attacks (when successful, excluding the already misclassified points) for every model.

Table content: <table><tr><td colspan="5">average norm of adversarial perturbations</td><td/></tr><tr><td>l∞-norm</td><td/><td/><td/><td>DF</td><td>FAB</td></tr><tr><td/><td>plain</td><td/><td/><td>0.078</td><td>0.066</td></tr><tr><td>MNIST</td><td>l∞-at</td><td/><td/><td>0.508</td><td>0.326</td></tr><tr><td/><td>l2-at</td><td/><td/><td>0.249</td><td>0.170</td></tr><tr><td/><td>plain</td><td/><td/><td>0.008</td><td>0.006</td></tr><tr><td>CIFAR-10</td><td>l∞-at</td><td/><td/><td>0.032</td><td>0.024</td></tr><tr><td/><td>l2-at</td><td/><td/><td>0.026</td><td>0.019</td></tr><tr><td>l2-norm</td><td/><td>DF</td><td>CW</td><td>LRA</td><td>FAB</td></tr><tr><td/><td>plain</td><td>1.13</td><td>1.01</td><td>1.00</td><td>1.00</td></tr><tr><td>MNIST</td><td>l∞-at</td><td>4.95</td><td>1.76</td><td>1.25</td><td>1.12</td></tr><tr><td/><td>l2-at</td><td>3.10</td><td>2.35</td><td>2.25</td><td>2.24</td></tr><tr><td/><td>plain</td><td>0.28</td><td>0.21</td><td>0.22</td><td>0.21</td></tr><tr><td>CIFAR-10</td><td>l∞-at</td><td>0.96</td><td>0.74</td><td>0.74</td><td>0.73</td></tr><tr><td/><td>l2-at</td><td>0.91</td><td>0.71</td><td>0.72</td><td>0.70</td></tr><tr><td>l1-norm</td><td/><td/><td/><td>EAD</td><td>FAB</td></tr><tr><td/><td>plain</td><td/><td/><td>6.38</td><td>6.04</td></tr><tr><td>MNIST</td><td>l∞-at</td><td/><td/><td>8.26</td><td>3.36</td></tr><tr><td/><td>l2-at</td><td/><td/><td>12.18</td><td>12.16</td></tr><tr><td/><td>plain</td><td/><td/><td>3.01</td><td>2.87</td></tr><tr><td>CIFAR-10</td><td>l∞-at</td><td/><td/><td>5.79</td><td>6.03</td></tr><tr><td/><td>l2-at</td><td/><td/><td>7.94</td><td>8.05</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on a naturally trained model on MNIST. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 1000 points on the test set for l ∞ and l 1 , on 500 points for l 2 .

Table content: <table><tr><td/><td/><td colspan="6">Robust accuracy of MNIST plain model</td><td/><td/><td/></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>50</td><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>0.03</td><td>93.2</td><td>91.9</td><td>91.9</td><td>92.0</td><td>91.9</td><td>91.9</td><td>92.0</td><td>92.0</td><td>92.0</td></tr><tr><td/><td>0.05</td><td>83.4</td><td>78.2</td><td>76.7</td><td>76.0</td><td>74.9</td><td>74.6</td><td>77.2</td><td>76.8</td><td>76.1</td></tr><tr><td>l∞</td><td>0.07</td><td>61.5</td><td>59.8</td><td>56.3</td><td>43.8</td><td>41.8</td><td>40.4</td><td>44.3</td><td>43.1</td><td>42.6</td></tr><tr><td/><td>0.09</td><td>33.2</td><td>46.7</td><td>41.0</td><td>16.5</td><td>14.2</td><td>12.8</td><td>16.2</td><td>14.8</td><td>14.4</td></tr><tr><td/><td>0.11</td><td>13.1</td><td>34.4</td><td>26.2</td><td>4.0</td><td>2.8</td><td>2.4</td><td>3.3</td><td>3.1</td><td>2.4</td></tr><tr><td/><td/><td>CW</td><td>DF</td><td colspan="2">LRA PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>0.5</td><td>92.6</td><td>93.6</td><td>92.6</td><td>92.6</td><td>92.6</td><td>92.6</td><td>92.6</td><td>92.6</td><td>92.6</td></tr><tr><td/><td>1</td><td>47.4</td><td>58.6</td><td>47.4</td><td>48.4</td><td>47.4</td><td>46.2</td><td>47.0</td><td>46.8</td><td>46.2</td></tr><tr><td>l2</td><td>1.5</td><td>8.8</td><td>19.8</td><td>7.8</td><td>9.8</td><td>8.8</td><td>8.2</td><td>7.8</td><td>7.2</td><td>7.0</td></tr><tr><td/><td>2</td><td>0.6</td><td>1.8</td><td>0.2</td><td>1.2</td><td>0.6</td><td>0.6</td><td>0.2</td><td>0.2</td><td>0.2</td></tr><tr><td/><td>2.5</td><td>0.0</td><td>0.0</td><td>0.0</td><td>0.6</td><td>0.2</td><td>0.2</td><td>0.0</td><td>0.0</td><td>0.0</td></tr><tr><td/><td/><td colspan="2">SparseFool</td><td colspan="2">EAD PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>2</td><td/><td>95.5</td><td>93.6</td><td>94.4</td><td>93.9</td><td>93.7</td><td>94.2</td><td>93.7</td><td>93.5</td></tr><tr><td/><td>4</td><td/><td>88.9</td><td>76.7</td><td>79.8</td><td>77.5</td><td>76.9</td><td>80.2</td><td>76.6</td><td>75.2</td></tr><tr><td>l1</td><td>6</td><td/><td>75.8</td><td>48.1</td><td>57.4</td><td>52.2</td><td>49.3</td><td>54.5</td><td>47.2</td><td>43.3</td></tr><tr><td/><td>8</td><td/><td>60.3</td><td>26.6</td><td>46.7</td><td>36.3</td><td>31.6</td><td>31.3</td><td>25.3</td><td>22.4</td></tr><tr><td/><td>10</td><td/><td>43.8</td><td>11.2</td><td>40.0</td><td>27.4</td><td>22.1</td><td>15.2</td><td>9.8</td><td>8.4</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on an l ∞ -robust model on MNIST. We report the accuracy on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 1000 points on the test set for l ∞ and l 1 , on 500 points for l 2 .

Table content: <table><tr><td/><td/><td colspan="7">Robust accuracy of MNIST l∞-robust model</td><td/><td/></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>50</td><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>0.2</td><td>95.2</td><td>94.6</td><td>93.7</td><td>95.0</td><td>94.2</td><td>93.7</td><td>94.6</td><td>94.4</td><td>93.9</td></tr><tr><td/><td>0.25</td><td>94.7</td><td>92.7</td><td>91.1</td><td>93.1</td><td>91.8</td><td>91.4</td><td>93.3</td><td>92.1</td><td>91.7</td></tr><tr><td>l∞</td><td>0.3</td><td>93.9</td><td>89.5</td><td>87.2</td><td>91.3</td><td>88.3</td><td>87.6</td><td>91.2</td><td>89.2</td><td>88.5</td></tr><tr><td/><td>0.325</td><td>92.5</td><td>72.1</td><td>64.2</td><td>74.9</td><td>68.4</td><td>64.7</td><td>86.2</td><td>83.1</td><td>81.3</td></tr><tr><td/><td>0.35</td><td>89.8</td><td>19.7</td><td>11.7</td><td>32.1</td><td>19.3</td><td>13.8</td><td>48.7</td><td>32.0</td><td>23.8</td></tr><tr><td/><td/><td>CW</td><td>DF</td><td colspan="2">LRA PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>1</td><td>88.8</td><td>94.6</td><td>73.6</td><td>92.2</td><td>90.8</td><td>89.8</td><td>84.2</td><td>70.6</td><td>65.4</td></tr><tr><td/><td>1.5</td><td>77.6</td><td>93.0</td><td>25.8</td><td>86.0</td><td>81.2</td><td>77.0</td><td>47.0</td><td>20.6</td><td>12.2</td></tr><tr><td>l2</td><td>2</td><td>64.4</td><td>91.6</td><td>3.2</td><td>77.8</td><td>67.0</td><td>57.8</td><td>15.6</td><td>1.8</td><td>0.2</td></tr><tr><td/><td>2.5</td><td>53.8</td><td>89.6</td><td>0.4</td><td>68.2</td><td>49.6</td><td>36.4</td><td>3.8</td><td>0.0</td><td>0.0</td></tr><tr><td/><td>3</td><td>46.8</td><td>84.6</td><td>0.0</td><td>59.8</td><td>29.6</td><td>13.4</td><td>1.4</td><td>0.0</td><td>0.0</td></tr><tr><td/><td/><td colspan="2">SparseFool</td><td colspan="2">EAD PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>2.5</td><td/><td>96.8</td><td>92.2</td><td>94.1</td><td>93.7</td><td>93.6</td><td>90.1</td><td>74.3</td><td>56.9</td></tr><tr><td/><td>5</td><td/><td>96.5</td><td>76.0</td><td>90.9</td><td>88.9</td><td>88.2</td><td>85.8</td><td>39.4</td><td>17.6</td></tr><tr><td>l1</td><td>7.5</td><td/><td>96.4</td><td>49.5</td><td>85.2</td><td>81.4</td><td>79.0</td><td>82.6</td><td>19.8</td><td>5.0</td></tr><tr><td/><td>10</td><td/><td>96.4</td><td>27.4</td><td>80.2</td><td>73.5</td><td>70.3</td><td>78.4</td><td>11.9</td><td>2.4</td></tr><tr><td/><td>12.5</td><td/><td>96.4</td><td>14.6</td><td>74.9</td><td>65.6</td><td>58.7</td><td>74.5</td><td>7.7</td><td>0.5</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on an l 2 -robust model on MNIST. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 1000 points on the test set for l ∞ and l 1 , on 500 points for l 2 .

Table content: <table><tr><td/><td/><td colspan="7">Robust accuracy of MNIST l2-robust model</td><td/><td/></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>50</td><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>0.05</td><td>96.7</td><td>96.4</td><td>96.3</td><td>96.4</td><td>96.3</td><td>96.3</td><td>96.4</td><td>96.3</td><td>96.3</td></tr><tr><td/><td>0.1</td><td>93.4</td><td>91.0</td><td>90.2</td><td>90.7</td><td>90.4</td><td>90.2</td><td>90.8</td><td>90.4</td><td>90.4</td></tr><tr><td>l∞</td><td>0.15</td><td>86.4</td><td>74.3</td><td>72.3</td><td>74.6</td><td>73.2</td><td>72.4</td><td>74.0</td><td>72.3</td><td>72.0</td></tr><tr><td/><td>0.2</td><td>73.8</td><td>34.5</td><td>27.2</td><td>36.2</td><td>29.8</td><td>26.5</td><td>34.1</td><td>28.2</td><td>24.4</td></tr><tr><td/><td>0.25</td><td>55.1</td><td>1.5</td><td>0.9</td><td>2.6</td><td>1.5</td><td>1.0</td><td>1.9</td><td>0.9</td><td>0.8</td></tr><tr><td/><td/><td>CW</td><td>DF</td><td colspan="2">LRA PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>1</td><td>92.6</td><td>93.8</td><td>92.6</td><td>93.0</td><td>93.0</td><td>93.0</td><td>92.6</td><td>92.6</td><td>92.6</td></tr><tr><td/><td>1.5</td><td>84.8</td><td>87.2</td><td>83.4</td><td>83.8</td><td>83.4</td><td>83.4</td><td>83.8</td><td>83.6</td><td>83.6</td></tr><tr><td>l2</td><td>2</td><td>70.6</td><td>79.0</td><td>68.0</td><td>68.8</td><td>68.0</td><td>67.6</td><td>69.8</td><td>69.0</td><td>67.8</td></tr><tr><td/><td>2.5</td><td>46.4</td><td>67.4</td><td>41.6</td><td>45.6</td><td>40.4</td><td>37.6</td><td>45.6</td><td>41.8</td><td>39.2</td></tr><tr><td/><td>3</td><td>17.2</td><td>54.2</td><td>11.2</td><td>17.4</td><td>12.4</td><td>10.2</td><td>18.6</td><td>13.4</td><td>11.0</td></tr><tr><td/><td/><td colspan="2">SparseFool</td><td colspan="2">EAD PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>5</td><td/><td>94.9</td><td>89.8</td><td>90.3</td><td>90.2</td><td>90.2</td><td>90.5</td><td>90.2</td><td>90.0</td></tr><tr><td/><td>8.75</td><td/><td>89.1</td><td>71.2</td><td>75.5</td><td>74.0</td><td>72.7</td><td>75.3</td><td>73.7</td><td>72.2</td></tr><tr><td>l1</td><td>12.5</td><td/><td>81.0</td><td>45.9</td><td>61.1</td><td>57.5</td><td>54.9</td><td>55.6</td><td>49.2</td><td>45.7</td></tr><tr><td/><td>16.25</td><td/><td>72.8</td><td>20.6</td><td>49.2</td><td>42.3</td><td>38.4</td><td>32.2</td><td>24.1</td><td>20.8</td></tr><tr><td/><td>20</td><td/><td>60.8</td><td>8.3</td><td>41.4</td><td>29.6</td><td>23.2</td><td>15.2</td><td>9.4</td><td>7.7</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on a naturally trained model on CIFAR-10. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 1000 points on the test set for l ∞ and l 1 , on 500 points for l 2 .

Table content: <table><tr><td>Robust</td></tr></table>



Table content: <table><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>50</td><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>1 /255</td><td>62.6</td><td>65.7</td><td>64.1</td><td>56.1</td><td>55.8</td><td>55.6</td><td>56.5</td><td>55.9</td><td>55.7</td></tr><tr><td/><td>1.5 /255</td><td>49.3</td><td>63.2</td><td>60.8</td><td>38.9</td><td>37.9</td><td>37.4</td><td>38.5</td><td>37.7</td><td>37.4</td></tr><tr><td>l∞</td><td>2 /255</td><td>37.3</td><td>62.4</td><td>58.5</td><td>24.3</td><td>23.3</td><td>22.9</td><td>23.4</td><td>21.9</td><td>21.2</td></tr><tr><td/><td>2.5 /255</td><td>26.4</td><td>61.2</td><td>56.3</td><td>16.2</td><td>14.8</td><td>14.0</td><td>13.2</td><td>12.0</td><td>11.8</td></tr><tr><td/><td>3 /255</td><td>19.0</td><td>60.2</td><td>54.4</td><td>10.7</td><td>9.2</td><td>8.6</td><td>7.4</td><td>5.8</td><td>5.4</td></tr><tr><td/><td/><td>CW</td><td>DF</td><td colspan="2">LRA PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>0.1</td><td>69.4</td><td>72.2</td><td>69.0</td><td>68.4</td><td>67.6</td><td>67.6</td><td>68.4</td><td>68.4</td><td>68.4</td></tr><tr><td/><td>0.15</td><td>55.4</td><td>62.6</td><td>55.0</td><td>54.6</td><td>53.8</td><td>53.8</td><td>54.6</td><td>54.0</td><td>53.8</td></tr><tr><td>l2</td><td>0.2</td><td>43.4</td><td>51.2</td><td>43.4</td><td>43.8</td><td>42.8</td><td>42.0</td><td>42.4</td><td>42.0</td><td>41.8</td></tr><tr><td/><td>0.3</td><td>21.6</td><td>33.8</td><td>22.0</td><td>24.8</td><td>24.2</td><td>23.6</td><td>21.6</td><td>20.8</td><td>20.6</td></tr><tr><td/><td>0.4</td><td>9.4</td><td>20.8</td><td>9.8</td><td>18.2</td><td>16.2</td><td>15.4</td><td>9.6</td><td>8.2</td><td>8.0</td></tr><tr><td/><td/><td colspan="2">SparseFool</td><td colspan="2">EAD PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>2</td><td/><td>72.1</td><td>54.7</td><td>54.9</td><td>54.4</td><td>53.9</td><td>55.5</td><td>52.2</td><td>50.8</td></tr><tr><td/><td>4</td><td/><td>58.6</td><td>24.1</td><td>30.0</td><td>29.1</td><td>28.9</td><td>30.7</td><td>25.1</td><td>22.4</td></tr><tr><td>l1</td><td>6</td><td/><td>45.6</td><td>8.9</td><td>18.8</td><td>18.6</td><td>18.4</td><td>17.0</td><td>10.5</td><td>8.1</td></tr><tr><td/><td>8</td><td/><td>34.3</td><td>3.0</td><td>14.2</td><td>14.1</td><td>14.0</td><td>7.8</td><td>3.8</td><td>2.5</td></tr><tr><td/><td>10</td><td/><td>27.2</td><td>0.7</td><td>12.9</td><td>12.5</td><td>12.3</td><td>4.7</td><td>1.5</td><td>1.0</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on an l ∞ -robust model on CIFAR-10. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 1000 points on the test set for l ∞ and l 1 , on 500 points for l 2 .

Table content: <table><tr><td/><td/><td colspan="7">Robust accuracy of CIFAR-10 l∞-robust model</td><td/><td/></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>50</td><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>2 /255</td><td>66.8</td><td>66.9</td><td>66.3</td><td>65.5</td><td>65.5</td><td>65.5</td><td>65.8</td><td>65.8</td><td>65.7</td></tr><tr><td/><td>4 /255</td><td>53.2</td><td>63.8</td><td>61.4</td><td>49.8</td><td>49.3</td><td>49.0</td><td>49.2</td><td>49.1</td><td>48.9</td></tr><tr><td>l∞</td><td>6 /255</td><td>42.9</td><td>63.1</td><td>58.4</td><td>38.0</td><td>36.9</td><td>36.6</td><td>35.4</td><td>34.7</td><td>34.6</td></tr><tr><td/><td>8 /255</td><td>32.9</td><td>61.2</td><td>56.3</td><td>30.5</td><td>30.0</td><td>29.6</td><td>23.8</td><td>23.5</td><td>23.3</td></tr><tr><td/><td>10 /255</td><td>24.5</td><td>59.8</td><td>54.1</td><td>25.8</td><td>23.7</td><td>22.4</td><td>15.4</td><td>14.7</td><td>14.4</td></tr><tr><td/><td/><td>CW</td><td>DF</td><td colspan="2">LRA PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>0.25</td><td>64.6</td><td>67.0</td><td>64.4</td><td>64.4</td><td>64.4</td><td>64.4</td><td>64.8</td><td>64.6</td><td>64.4</td></tr><tr><td/><td>0.5</td><td>48.4</td><td>53.0</td><td>48.8</td><td>49.0</td><td>48.4</td><td>48.0</td><td>48.4</td><td>48.4</td><td>48.2</td></tr><tr><td>l2</td><td>0.75</td><td>33.4</td><td>41.4</td><td>33.4</td><td>39.0</td><td>38.2</td><td>37.4</td><td>33.6</td><td>33.2</td><td>33.0</td></tr><tr><td/><td>1</td><td>22.8</td><td>32.6</td><td>22.8</td><td>35.0</td><td>34.4</td><td>33.8</td><td>22.2</td><td>21.6</td><td>21.4</td></tr><tr><td/><td>1.25</td><td>12.0</td><td>24.2</td><td>13.0</td><td>34.6</td><td>34.2</td><td>33.2</td><td>12.2</td><td>11.2</td><td>11.2</td></tr><tr><td/><td/><td colspan="2">SparseFool</td><td colspan="2">EAD PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>5</td><td/><td>57.8</td><td>36.8</td><td>47.3</td><td>46.6</td><td>46.2</td><td>43.1</td><td>39.9</td><td>37.9</td></tr><tr><td/><td>8.75</td><td/><td>44.7</td><td>19.2</td><td>37.4</td><td>37.0</td><td>36.8</td><td>25.7</td><td>22.5</td><td>20.2</td></tr><tr><td>l1</td><td>12.5</td><td/><td>34.9</td><td>7.1</td><td>34.0</td><td>33.9</td><td>33.9</td><td>13.7</td><td>10.9</td><td>8.7</td></tr><tr><td/><td>16.25</td><td/><td>27.6</td><td>3.0</td><td>33.3</td><td>33.2</td><td>33.1</td><td>7.1</td><td>4.3</td><td>3.5</td></tr><tr><td/><td>20</td><td/><td>20.2</td><td>0.9</td><td>32.9</td><td>32.8</td><td>32.8</td><td>3.8</td><td>1.7</td><td>1.3</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on an l 2 -robust model on CIFAR-10. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 1000 points on the test set for l ∞ and l 1 , on 500 points for l 2 .

Table content: <table><tr><td/><td/><td colspan="7">Robust accuracy of CIFAR-10 l2-robust model</td><td/><td/></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>50</td><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>2 /255</td><td>64.1</td><td>67.2</td><td>66.3</td><td>62.6</td><td>62.5</td><td>62.4</td><td>62.7</td><td>62.6</td><td>62.6</td></tr><tr><td/><td>4 /255</td><td>49.0</td><td>65.0</td><td>62.8</td><td>45.3</td><td>45.0</td><td>44.9</td><td>44.4</td><td>44.2</td><td>44.2</td></tr><tr><td>l∞</td><td>6 /255</td><td>36.9</td><td>64.2</td><td>60.8</td><td>32.9</td><td>31.6</td><td>31.1</td><td>27.2</td><td>26.8</td><td>26.7</td></tr><tr><td/><td>8 /255</td><td>25.8</td><td>62.3</td><td>58.0</td><td>25.7</td><td>24.9</td><td>23.9</td><td>14.8</td><td>14.1</td><td>13.8</td></tr><tr><td/><td>10 /255</td><td>17.6</td><td>61.9</td><td>54.8</td><td>21.9</td><td>19.8</td><td>18.6</td><td>8.6</td><td>8.0</td><td>7.9</td></tr><tr><td/><td/><td>CW</td><td>DF</td><td colspan="2">LRA PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>0.25</td><td>66.0</td><td>67.0</td><td>65.6</td><td>65.8</td><td>65.6</td><td>65.6</td><td>65.6</td><td>65.6</td><td>65.6</td></tr><tr><td/><td>0.5</td><td>48.2</td><td>53.8</td><td>47.8</td><td>49.6</td><td>48.8</td><td>48.8</td><td>48.4</td><td>48.2</td><td>48.0</td></tr><tr><td>l2</td><td>0.75</td><td>32.6</td><td>42.2</td><td>32.4</td><td>38.4</td><td>37.2</td><td>36.4</td><td>32.8</td><td>32.4</td><td>32.2</td></tr><tr><td/><td>1</td><td>21.6</td><td>30.0</td><td>21.6</td><td>35.4</td><td>33.6</td><td>33.0</td><td>21.8</td><td>21.4</td><td>21.0</td></tr><tr><td/><td>1.25</td><td>11.4</td><td>22.4</td><td>12.4</td><td>34.2</td><td>31.6</td><td>31.2</td><td>12.2</td><td>12.2</td><td>11.4</td></tr><tr><td/><td/><td colspan="2">SparseFool</td><td colspan="2">EAD PGD-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>100</td><td>1</td><td>10</td><td>100</td></tr><tr><td/><td>3</td><td/><td>69.5</td><td>62.2</td><td>64.5</td><td>64.4</td><td>64.4</td><td>63.4</td><td>63.2</td><td>63.0</td></tr><tr><td/><td>6</td><td/><td>61.6</td><td>45.5</td><td>51.9</td><td>51.9</td><td>51.8</td><td>48.6</td><td>47.2</td><td>45.6</td></tr><tr><td>l1</td><td>9</td><td/><td>53.1</td><td>27.7</td><td>42.8</td><td>42.5</td><td>42.5</td><td>33.9</td><td>30.6</td><td>28.8</td></tr><tr><td/><td>12</td><td/><td>44.4</td><td>17.9</td><td>38.5</td><td>38.3</td><td>38.0</td><td>23.8</td><td>19.8</td><td>17.3</td></tr><tr><td/><td>15</td><td/><td>37.0</td><td>10.4</td><td>35.8</td><td>35.8</td><td>35.4</td><td>16.0</td><td>12.4</td><td>11.2</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on a naturally trained model on Restricted ImageNet. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 500 points of the test set.

Table content: <table><tr><td/><td colspan="7">Robust accuracy of Restricted ImageNet plain model</td><td/></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>10</td><td>1</td><td>10</td><td>1</td><td>10</td></tr><tr><td/><td>0.25 /255</td><td>76.6</td><td>74.8</td><td>74.8</td><td>74.8</td><td>74.6</td><td>75.2</td><td>75.2</td></tr><tr><td/><td>0.5 /255</td><td>52.0</td><td>51.8</td><td>48.2</td><td>38.2</td><td>37.8</td><td>39.6</td><td>39.6</td></tr><tr><td>l∞</td><td>0.75 /255</td><td>26.8</td><td>46.0</td><td>41.0</td><td>12.2</td><td>12.2</td><td>14.2</td><td>14.2</td></tr><tr><td/><td>1 /255</td><td>11.2</td><td>43.2</td><td>39.4</td><td>3.8</td><td>3.8</td><td>3.6</td><td>3.6</td></tr><tr><td/><td>1.25 /255</td><td>5.0</td><td>41.2</td><td>38.2</td><td>1.0</td><td>1.0</td><td>1.2</td><td>1.0</td></tr><tr><td/><td/><td/><td/><td colspan="2">DF PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>1</td><td>10</td></tr><tr><td/><td>0.2</td><td/><td/><td>80.2</td><td>76.0</td><td>76.0</td><td>77.0</td><td>76.8</td></tr><tr><td/><td>0.4</td><td/><td/><td>58.4</td><td>40.8</td><td>40.6</td><td>43.0</td><td>42.2</td></tr><tr><td>l2</td><td>0.6</td><td/><td/><td>33.8</td><td>15.4</td><td>14.8</td><td>19.0</td><td>18.2</td></tr><tr><td/><td>0.8</td><td/><td/><td>18.8</td><td>4.0</td><td>4.0</td><td>4.6</td><td>4.4</td></tr><tr><td/><td>1</td><td/><td/><td>8.6</td><td>1.6</td><td>1.6</td><td>1.2</td><td>1.0</td></tr><tr><td/><td/><td/><td colspan="3">SparseFool PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>5</td><td>1</td><td>5</td></tr><tr><td/><td>5</td><td/><td/><td>88.6</td><td>81.8</td><td>81.8</td><td>79.6</td><td>78.0</td></tr><tr><td/><td>16</td><td/><td/><td>80.0</td><td>45.2</td><td>45.2</td><td>46.8</td><td>40.0</td></tr><tr><td>l1</td><td>27</td><td/><td/><td>70.6</td><td>17.8</td><td>17.4</td><td>25.6</td><td>19.8</td></tr><tr><td/><td>38</td><td/><td/><td>65.0</td><td>6.2</td><td>6.0</td><td>13.6</td><td>7.0</td></tr><tr><td/><td>49</td><td/><td/><td>55.4</td><td>2.2</td><td>2.2</td><td>6.8</td><td>3.8</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on an l ∞ -robust model on Restricted ImageNet. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 500 points of the test set.

Table content: <table><tr><td colspan="9">Robust accuracy of Restricted ImageNet l∞-robust model</td></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>10</td><td>1</td><td>10</td><td>1</td><td>10</td></tr><tr><td/><td>2 /255</td><td>75.8</td><td>75.0</td><td>75.0</td><td>74.6</td><td>74.6</td><td>75.2</td><td>75.2</td></tr><tr><td/><td>4 /255</td><td>53.0</td><td>46.2</td><td>46.2</td><td>45.4</td><td>45.4</td><td>47.4</td><td>47.4</td></tr><tr><td>l∞</td><td>6 /255</td><td>32.4</td><td>24.6</td><td>23.8</td><td>19.4</td><td>19.4</td><td>21.2</td><td>21.0</td></tr><tr><td/><td>8 /255</td><td>19.4</td><td>17.0</td><td>14.6</td><td>6.2</td><td>6.2</td><td>6.8</td><td>6.8</td></tr><tr><td/><td>10 /255</td><td>10.8</td><td>12.8</td><td>11.6</td><td>1.0</td><td>0.8</td><td>1.2</td><td>1.2</td></tr><tr><td/><td/><td/><td/><td colspan="2">DF PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>10</td><td>1</td><td>10</td></tr><tr><td/><td>1</td><td/><td/><td>79.4</td><td>76.6</td><td>76.6</td><td>77.0</td><td>76.8</td></tr><tr><td/><td>2</td><td/><td/><td>65.0</td><td>46.8</td><td>46.2</td><td>49.8</td><td>49.2</td></tr><tr><td>l2</td><td>3</td><td/><td/><td>46.8</td><td>22.4</td><td>21.4</td><td>24.4</td><td>23.8</td></tr><tr><td/><td>4</td><td/><td/><td>32.8</td><td>9.0</td><td>8.6</td><td>10.8</td><td>10.6</td></tr><tr><td/><td>5</td><td/><td/><td>20.4</td><td>3.0</td><td>2.8</td><td>3.2</td><td>3.2</td></tr><tr><td/><td/><td/><td colspan="3">SparseFool PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>5</td><td>1</td><td>5</td></tr><tr><td/><td>15</td><td/><td/><td>81.8</td><td>69.8</td><td>69.8</td><td>69.6</td><td>68.2</td></tr><tr><td/><td>25</td><td/><td/><td>76.4</td><td>58.6</td><td>58.2</td><td>56.2</td><td>53.6</td></tr><tr><td>l1</td><td>40</td><td/><td/><td>71.4</td><td>41.0</td><td>41.0</td><td>41.2</td><td>37.6</td></tr><tr><td/><td>60</td><td/><td/><td>63.2</td><td>28.8</td><td>28.8</td><td>28.2</td><td>23.8</td></tr><tr><td/><td>100</td><td/><td/><td>49.2</td><td>12.0</td><td>11.6</td><td>14.6</td><td>11.2</td></tr></table>

Comparison of l ∞ -, l 2 -and l 1 -attacks on an l 2 -robust model on Restricted ImageNet. We report the accuracy in percentage of the classifier on the test set if the attack is allowed to perturb the test points of in l p -distance. The statistics are computed on the first 500 points of the test set.

Table content: <table><tr><td colspan="9">Robust accuracy of Restricted ImageNet l2-robust model</td></tr><tr><td>metric</td><td/><td colspan="2">DF DAA-</td><td>DAA-</td><td>PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td>1</td><td>10</td><td>1</td><td>10</td><td>1</td><td>10</td></tr><tr><td/><td>2 /255</td><td>74.4</td><td>73.0</td><td>73.0</td><td>73.0</td><td>73.0</td><td>73.8</td><td>73.8</td></tr><tr><td/><td>4 /255</td><td>49.0</td><td>39.6</td><td>39.2</td><td>37.6</td><td>37.6</td><td>39.6</td><td>39.4</td></tr><tr><td>l∞</td><td>6 /255</td><td>27.4</td><td>22.6</td><td>21.0</td><td>13.2</td><td>13.2</td><td>15.0</td><td>15.0</td></tr><tr><td/><td>8 /255</td><td>13.8</td><td>18.6</td><td>16.8</td><td>3.6</td><td>3.6</td><td>3.6</td><td>3.2</td></tr><tr><td/><td>10 /255</td><td>6.6</td><td>15.6</td><td>13.8</td><td>0.4</td><td>0.4</td><td>0.8</td><td>0.8</td></tr><tr><td/><td/><td/><td/><td colspan="2">DF PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>50</td><td>1</td><td>10</td></tr><tr><td/><td>2</td><td/><td/><td>74.2</td><td>71.8</td><td>71.8</td><td>72.8</td><td>72.8</td></tr><tr><td/><td>3</td><td/><td/><td>61.6</td><td>51.4</td><td>51.0</td><td>52.4</td><td>52.4</td></tr><tr><td>l2</td><td>4</td><td/><td/><td>45.6</td><td>31.0</td><td>30.8</td><td>34.4</td><td>33.8</td></tr><tr><td/><td>5</td><td/><td/><td>34.6</td><td>20.4</td><td>20.4</td><td>22.6</td><td>21.8</td></tr><tr><td/><td>6</td><td/><td/><td>25.2</td><td>9.6</td><td>9.6</td><td>11.8</td><td>11.6</td></tr><tr><td/><td/><td/><td colspan="3">SparseFool PGD-</td><td>PGD-</td><td>FAB-</td><td>FAB-</td></tr><tr><td/><td/><td/><td/><td/><td>1</td><td>5</td><td>1</td><td>5</td></tr><tr><td/><td>50</td><td/><td/><td>85.4</td><td>81.0</td><td>81.0</td><td>78.6</td><td>78.4</td></tr><tr><td/><td>100</td><td/><td/><td>79.6</td><td>63.8</td><td>63.6</td><td>60.8</td><td>59.0</td></tr><tr><td>l1</td><td>150</td><td/><td/><td>74.4</td><td>48.4</td><td>48.4</td><td>45.2</td><td>42.2</td></tr><tr><td/><td>200</td><td/><td/><td>68.6</td><td>32.2</td><td>32.2</td><td>31.0</td><td>29.0</td></tr><tr><td/><td>250</td><td/><td/><td>60.0</td><td>23.0</td><td>22.4</td><td>22.8</td><td>20.2</td></tr></table>

Peer review (iclr2020):
Authors extend deepFool by adding extra steps and constraints to find closer points to the source image as the adversarial image. They both project onto the decision boundary. Deepfool does and adhoc clipping to keep the pixel values in (0,1) but the new proposed method respects the constraints during the steps. Also during the steps they combine projection of last step result and original image to keep it closer to the original image. Moreover, at the end of the optimization they perform extra search steps to get closer to the original image. Also they add random restarts. Rather than considering the original image, they randomly choose an image in the half ballpark of the total delta. According to the results in fig.2 the backward steps has the highest impact in comparison to deepfool. But mixing with original projection always helps a little and random restarts help a little too. Without the backward steps there is almost no gain from mixing the projections. Considering the full results in the appendix, the results are mixed with no obvious advantage in comparison to PGD specially.