Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack
Year: 2019

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 lp-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 lp-norm.

heading: 1 Introduction
text: 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 lp-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 lp-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 {δ ∈ Rd | ‖δ‖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.

heading: 2 FAB: a Fast Adaptive Boundary Attack
text: We first introduce minimal adversarial perturbations, then we recall the definition and properties of the projection wrt the lp-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.

heading: 2.1 Minimal adversarial examples
text: Let f : Rd → RK be a classifier which assigns every input x ∈ Rd (with d the dimension of the input space) to one of the K classes according to arg max
r=1,...,K fr(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 ∈ Rd with true class c, we define the minimal adversarial perturbation for x wrt the lp-norm as
δmin,p = arg min δ∈Rd ‖δ‖p , s.th. max l 6=c fl(x+ δ) ≥ fc(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.

heading: 2.2 Projection on a hyperplane with box constraints
text: Let w ∈ Rd and b ∈ R be the normal vector and the offset defining the hyperplane π : 〈w, x〉+ b = 0. Let x ∈ Rd, we denote by the box-constrained projection wrt the lp-norm of x on π (projection onto the intersection of the box C = {z ∈ Rd : li ≤ zi ≤ ui} and the hyperplane π) the following minimization problem:
z∗ = arg min z∈Rd ‖z − x‖p s.th. 〈w, z〉+ b = 0, li ≤ zi ≤ ui, i = 1, . . . , d, (2)
where li, ui ∈ 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
z′ = arg min z∈Rd ρ(〈w, z〉+ b) s.th. li ≤ zi ≤ ui, i = 1, . . . , d, (3)
whose solution is given componentwise, for every i = 1, . . . , d, by zi =  li if ρwi > 0, ui if ρwi < 0, xi if wi = 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
projp : (x, π, C) 7−→ { z∗ if Problem (2) is feasible z′ else (4)
yielding the point which gets as close as possible to π without violating the box constraints.

heading: 2.3 FAB Attack
text: We introduce now our algorithm to produce minimally distorted adversarial examples, wrt any lp-norm for p ∈ {1, 2,∞}, for a given point xorig 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 xorig onto the approximated decision hyperplane and take a convex combinations of these projections depending on the distance of x(i) and xorig 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 xorig. 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 xorig.
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 6= 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
πl(z) : fl(x(i))− fc(x(i)) + 〈 ∇fl(x(i))−∇fc(x(i)), z − x(i) 〉 = 0. (5)
Moreover the lp-distance dp(π, x(i)) of x(i) to πl is given by
dp(πl, x(i)) = |fl(x(i))− fc(x(i))|∥∥∇fl(x(i))−∇fc(x(i))∥∥q , with 1p + 1q = 1. (6)
Note that if dp(π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
s = arg min l 6=c |fl(x(i))− fc(x(i))|∥∥∇fl(x(i))−∇fc(x(i))∥∥q . (7) Thus, given that the approximation holds in some large enough neighborhood, the projection projp(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) = projp(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 xorig, 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 projp(xorig, πs, C) and use instead the iterative step, with x(0) = xorig, defined as
x(i+1) = (1− α) · projp(x(i), πs, C) + α · projp(xorig, πs, C), (8)
which biases the step towards xorig (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
a scheme with minimal amount of parameters, we want to have an automatic selection of α based on the available geometric quantities. Let
δ(i) = projp(x(i), πs, C)− x(i) and δ (i) orig = projp(xorig, πs, C)− xorig.
Note that ∥∥δ(i)∥∥
p and ∥∥∥δ(i)orig∥∥∥ p are the distances of x(i) and xorig to πs (inside C). We
propose to use for the parameter α the relative magnitude of these two distances, that is
α = min  ∥∥δ(i)∥∥ p∥∥δ(i)∥∥ p + ∥∥∥δ(i)orig∥∥∥
p
, αmax  ∈ [0, 1]. (9) 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 xorig is farther away). On the other hand we want to have the bias towards xorig in order not to go too far away from xorig. This is why α depends on the distances of x(i) and xorig 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:
x(i+1) = projC ( (1− α)(x(i) + ηδ(i)) + α(xorig + ηδ(i)orig) ) , (10)
where α is chosen as in (9), η ≥ 1 and projC 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 projp(xorig, πs, C): The projection of the target point onto the intersection of πs and C is defined as
arg min z∈Rd ‖z − xorig‖p s.th. 〈w, z〉+ b = 0, li ≤ zi ≤ ui,
Note that replacing z by x(i) + δ we can rewrite this as
arg min δ∈Rd ∥∥∥x(i) + δ − xorig∥∥∥ p s.th. 〈w, x+ δ〉+ b = 0, li ≤ xi + δi ≤ ui.
This can be interpreted as the minimization of the distance of the next iterate x(i) + δ to the target point xorig so that x(i) + δ lies on the intersection of the (approximate) decision hyperplane and the box C. This point of view on the projection projp(xorig, π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
x(i+1) = (1− β)xorig + βx(i+1), β ∈ (0, 1), (11) that is we go back towards xorig on the segment [x(i+1), xorig], 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 xorig we successively find adversarial perturbations of smaller norm, meaning that the algorithm tracks the decision boundary while getting closer to xorig.
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 Niter iterations of our algorithmic scheme, we perform a last, fast step to further improve the quality of the adversarial examples. Let xout be the closest point to xorig classified differently from c, say s 6= c, found with the iterative scheme. It holds that fs(xout)−fc(xout) > 0 and fs(xorig)−fc(xorig) < 0. This means that, assuming f continuous, there exists a point x∗ on the segment [xout, xorig] such that fs(x∗)− fc(x∗) = 0 and ‖x∗ − xorig‖p < ‖xout − xorig‖p. If f is linear
x∗ = xout − fs(xout)− fc(xout)
fs(xout)− fc(xout) + fs(xorig)− fc(xorig) (xout − xorig). (12)
Since f is typically non-linear, but close to linear, we compute iteratively for a few steps
xtemp = xout − fs(xout)− fc(xout)
fs(xout)− fc(xout) + fs(xorig)− fc(xorig) (xout − xorig), (13)
each time replacing in (13) xout with xtemp if fs(xtemp)− fc(xtemp) > 0 or xorig with xtemp if instead fs(xtemp)− fc(xtemp) < 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 xorig instead of being xorig 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 lp-sphere centered in the original point with radius half the lp-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
Niter ×Nrestarts × (2× forward passes + 1× backward pass). (14)
One has to add the forward passes for the final search, fixed to 3, that happens just once.

heading: 2.4 Comparison to DeepFool
text: 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 : xorig original point, c original class, Nrestarts, Niter, αmax, β, η, , p Output : xout adversarial example
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.

heading: 3 Experiments
text: Models: We run experiments on MNIST, CIFAR-10 (Krizhevsky et al.) and Restricted ImageNet (Tsipras et al. (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 l2-norm (l2-AT) (see A.1).
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)), CarliniWagner l2-attack (CW) (Carlini & Wagner (2017a)), Linear Region l2-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 l1 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 lp-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 lp-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 l2 and l1. Interestingly, the second best attack, at least in terms of average robust accuracy, is different for every norm (PGD for l∞, LRA for l2, EAD for l1), 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 l1, while for l∞ and l2, although PGD performs often better, the difference in "avg. robust accuracy" is small, meaning that FAB performs mostly similarly to PGD.
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 lp-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 lp-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∞/l2 and PGD-100 14106s for l1, CW 944s, EAD 606s, FAB-10 161s, FAB-100 1613s. CIFAR-10: DAA-50 11625s, PGD-100 31900s
for l∞/l2 and 70110s for l1, CW 3691s, EAD 3398s, FAB-10 1209s, FAB-100 12093s. RImageNet: DAA-10 6890s, PGD-10 4738s for l∞/l2 and PGD-5 24158s for l1, FAB-10 2268s for l∞/l2 and FAC-5 3146s for l1 (note that different numbers of restarts/iterations for l1 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.

heading: 4 Conclusion
text: 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.

heading: A Experiments

heading: A.1 Models
text: 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%, l2-AT 98.6%. The models on CIFAR-10 achieve the following clean accuracy: plain 89.2%, l∞-AT 79.4%, l2-AT 81.2%.

heading: A.2 Attacks
text: values of used for random restarts
MNIST CIFAR-10 Restricted ImageNet
plain l∞-AT l2-AT plain l∞-AT l2-AT plain l∞-AT l2-AT l∞ 0.15 0.3 0.3 0.0 0.02 0.02 0.02 0.08 0.08 l2 2.0 2.0 2.0 0.5 4.0 4.0 5.0 5.0 5.0 l1 40.0 40.0 40.0 10.0 10.0 10.0 100.0 250.0 250.0

heading: A.3 Complete results
text: In Tables 5 to 13 we report the complete values of the robust accuracy, wrt either l∞, l2 or l1, computed by every attack, for 3 datasets, 3 models for each dataset, 5 thresholds for each model (135 evaluations overall).

heading: A.4 Further results
text: In Table 4 we report the average lp-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 l2, and the best in 4 out of 6 cases in l1 (lower values mean a stronger attack).

heading: MNIST

heading: B Analysis of the attacks

heading: B.1 Choice of the step size of PGD
text: We here show the performance of PGD wrt l2 on MNIST and CIFAR-10 under different choices of the step size. In particular we focus here on the largest and the middle values chosen in the evaluation where the different stepsize choices have the largest impact. We report the robust accuracy for at each of the 150 iterations. We test step sizes /t for t ∈ {1, 2, 4, 10, 25, 75}. For each step size we run the attack 10 times with random initialization and show the run which achieves the lowest robust accuracy after 150 iterations. Note however that the behaviour of different runs varies minimally. In Figure 3 we show the results for the three models for MNIST and CIFAR-10 for two different choices of used in Section 3, with step size decreasing the blue becoming darker, while our chosen step size, that is /4, is highlighted in red. We see that it achieves in all the models best or close to best robust accuracy and is clearly the best on average.

heading: B.2 Evolution across iteration
text: We here want to compare the evolution of the robust accuracy across the iterations of a single run of PGD and FAB, that is PGD-1 and FAB-1 from Tables 5 to 13. Since PGD performs 1 forward and 1 backward pass for each iteration and FAB 2 forward passes and 1 backward pass, we rescale the robust accuracy so to compare the two methods when they have exploited the same number of passes of the network. Then 300 passes correspond to 150 iterations of PGD and to 100 of FAB. In Figures 4, 5 and 6 we show the evolution of robust accuracy for the different dataset, models and threat models (l∞, l2 and l1), computed at the threshold median among the five used in Tables 5 to 13.

heading: MNIST, l1

heading: MNIST, l2

heading: MNIST, l∞
text: CIFAR-10, l∞
CIFAR-10, l2
CIFAR-10, l1
Restricted ImageNet, l∞
Restricted ImageNet, l2
Restricted ImageNet, l1

Review summaries:
The authors propose a new gradient-based method (FAB) for constructing adversarial perturbations for deep neural networks. At a high level, the method repeatedly estimates the decision boundary based on the linearization of the classifier at a given point and projects to the closest "misclassified" example based on that estimation (similar to DeepFool). The authors build on this idea, proposing several improvements and evaluate their attack empirically against a variety of models.

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.