Fast Minimum-norm Adversarial Attacks through Adaptive Norm Constraints
Authors: Maura Pintor
Fabio Roli
Wieland Brendel
Battista Biggio
Venue: NeurIPS 2021 Poster (2021)
Keywords: machine learning
adversarial machine learning
computer vision
adversarial robustness
adversarial attacks

Abstract: Evaluating adversarial robustness amounts to finding the minimum perturbation needed to have an input sample misclassified. 
The inherent complexity of the underlying optimization requires current gradient-based attacks to be carefully tuned, initialized, and possibly executed for many computationally-demanding iterations, even if specialized to a given perturbation model.
In this work, we overcome these limitations by proposing a fast minimum-norm (FMN) attack that works with different $\ell_p$-norm perturbation models ($p=0, 1, 2, \infty$), is robust to hyperparameter choices, does not require adversarial starting points, and converges within few lightweight steps. 
It works by iteratively finding the sample misclassified with maximum confidence within an $\ell_p$-norm constraint of size $\epsilon$, while adapting $\epsilon$ to minimize the distance of the current sample to the decision boundary.
Extensive experiments show that FMN significantly outperforms existing $\ell_0$, $\ell_1$, and $\ell_\infty$-norm attacks in terms of perturbation size, convergence speed and computation time, while reporting comparable performances with state-of-the-art $\ell_2$-norm attacks. Our open-source code is available at: https://github.com/pralab/Fast-Minimum-Norm-FMN-Attack.

Fast Minimum-norm Adversarial Attacks through Adaptive Norm Constraints
Maura Pintor
Fabio Roli
University of Cagliari, Italy Pluribus One, Italy
University of Cagliari, Italy Pluribus One, Italy roli@unica. it
maura.pintonn pinropppaarrr it
Wieland Brendel
Battista Biggio
Tübingen Al Center,
University of Cagliari, Italy Pluribus One, Italy battista. biggiouuniaa.....mmooooooomo it
University of Tübingen, Germany wieland. brendel @uni Wwwi-ntnninnnenneeeee -tuebingen.de
Abstract
Evaluating adversarial robustness amounts to finding the minimum perturbation needed to have an input sample misclassified. The inherent complexity of the underlying optimization requires current gradient-based attacks be carefully tuned, initialized, and possibly executed for many iterations, even specialized
pepputationalyydemmaddd given perturbation model. In this work, we overcome these limitations by proposing fast minimum-norm (FMN) attack that works with different fp-norm perturbation models (p = 1,2, no), is ro- bust hyperparameter choices, does not require adversarial starting points, and converges within few lightweight steps. works by iteratively finding the sam- ple misclassified with maximum confidence within fy-norm constraint of size e, while adapting e to minimize the distance the current sample to the decision boundary. Extensive experiments show that FMN significantly out- performs existing to. f1, and fg -norm attacks terms of perturbation size, convergence speed and computation time, while reporting comparable perfor- mances with state-of-the-art norm attacks. Our open-source code is available at: https://giithbb http:://ggthhbb.coo/paaaaaa////s Sonttt-Miiimmmmm Norm- FMoo-m--NNAtttcck
Introduction
Learning algorithms are vulnerable to adversarial examples, i.e., antentionalllypertueee inputs aimed to mislead classification test time 24 3. While adversarial examples have received much attention, evaluating the robustness of deep networks against them remains challenge. Adversarial attacks solve a non-convex optimization problem and are thus prone to finding suboptimal solutions; in particular, all attacks make certain assumptions about the underlying geometry and properties of the optimization problem which, if violated, can derail the attack and may lead to premature conclusions regarding model robustness. That is why the vast majority of defenses published in recent years have later shown to be ineffective against more powerful white-bos box attacks I. Having an arsenal of diverse attacks that can be adapted specific defenses is one of the most promising avenues for increasing confidence in white-box robustness evaluations 6 255 While it may seem that the number of attacks already large, most of them are just small variations of the same technique, make similar underlying assumptions and thus tend to fail jointly (see, e.g., (25] in which projected-gradict attacks all fail similarly against the "Ensemble Diversity" defense).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.0
d-step
1.00-
Lipe 8.
0.8
0.75
Tp-1
0.6
0.50-
LE 8.y.8) =
0.4
0.25-
[1] e-step
0.2
0.0
0.2
0.1
0.6
0.8
20
stegs
Figure 1: (a) Conceptual representation of the FMN attack algorithm (leftmost plot). The e-step updates the constraint size e to minimize its distance to the boundary. The 8-step updates the perturbation with projected-gradiet step to maximize misclassification confidence within the current c-sized constraint. (b) Example of execution of our attack on a bi-dimensional problem (middle plot), along with the corresponding values of the loss function L and the constraint size e across iterations (rightmost plot). Our algorithm works by first pushing the initial point (red dot) towards the adversarial region (in red), and then perturbing around the decision boundary to improve the current solution towards local optimum. The vertical lines in the rightmost plot highlight the steps in which a better solution (smaller [|ō*| and < 0) is found.
In this work, we focus on minimum-norn attacks for evaluating adversarial robustness, i.e., attacks that aim to mislead classification by finding the smallest input perturbation according to given norm. In contrast to maximum-conffdere attacks, which maximize confidence in wrong class within a given perturbation budget, the former are better suited to evaluate adversarial robustness as can compute the accuracy of classifier under attack for any perturbation budget without re-running the attack. Within the class of gradient-based minimum- norm attacks, there are three main attacks. Soft-constraint attacks like CW (5] optimize a trade-off between confidence of the misclassified samples and perturbation size. This class of attacks needs sample wise tuning of the trade-off hyperparameter to find the smallest possible perturbation, thus requiring many steps to converge. Boundary attacks like BB 4 and FAB [10] move along the decision boundary towards the closest point to the input sample. These attacks converge within relatively few steps, but BB requires an adversarial starting point, and both attacks need to solve relatively expensive optimization problem in each step. Finally, recent minimum-norm maximem-confidence attack each step under a given perturbation budget e, while iteratively adjusting to reduce the perturbation size. DDN combines the effectiveness of boundary attacks with the simplicity and per-step speed of soft-constraint attacks; however, is specific to the lg norm and cannot be readily extended to other norms.
sub-categone cub-categorie:: (i) noft-constraint attacks, (ii) boundary attacks and (iii) projected-gradee
attacks like DDN (23] perform
To overcome the aforementioned limitations, in this work we propose novel, fast minimum-norm (FMN) attack (Sect. 2) which retains the main advantages of DDN while generalizing it to different lp norms (p 0, 1,2, oo). We perform large-scale experiments on different datasets and models (Sect.3). 3. showing that FMN is able to significantly outperform current minimum-norm attacks in terms of convergence speed and computation time (except for fn-norm attacks, for which FMN achieves comparable results), while finding equal or better optima, on average, across almost all tested scenarios and lp norms. FMN thus combines all desirable traits a good adversarial attack should have, providing an important step towards improving adversarial robustness evaluations. We conclude the paper by discussing related work (Sect. 4 and future research directions (Sect. (5).
2 Minimum-Nore Adversarial Examples with Adaptive Projections
Problem formulation. Given an input sample [0, 1]d, belonging to class y E (1...., c}, the goal of untargeted attack is find the minimum-noo norm perturbation 8* such that the corresponding adversarial example x² = x + 8" is misclassified. This problem can be formulated as:
8" E arg min
||0|pp
(1)
s.t.
L(x + 8, 0) 0,
(2)
+ 8 E 10, 1
33)

---

Algorithm Fast Minimum-norm (FMN) Attack
Input:
æ. the input sample; 4, a variable denoting whether the attack is targeted (1 = +1) on untargeted 1);; y, the target (true) class label if the attack is targeted (untargeted); To and TK. the initial and final e-step sizes; Ogg and ox,, the initial and final 8-step sizes; K, the total number of iterations.
Output: The minimum-none adversarial example x".
20 t 2, 6o 0, d0 < O, 8
2: for k = 1..... K do
3: g f -. VoL
8. y. 0) // loss gradient
4:
* f- h(70: NK. k. K) // c-step size decay (Eq.
5:
if L( 1.y. 8) 2 then
6:
6k 1 1lp L(xx-11 v, 00/ |glا if adversarial not found yet else = -k=-1(1 + 7k)
7:
else
8:
if
8x .lpp S 11001p
1p then
9:
8' + 8k-1 // update best min-non nin-norm solution
10:
end if
11:
Eg = min(ex-1(L -7k); (1)))))))
12:
end if
13:
ag t h(ao, 0k k, K) // 8-sp size decay (Eq. 6
14:
åz t 5k-1 + a3 9/|l|//2 1/ gradient-scaling step
15:
dR t (20 + 6%) In
du t clip( 5x) xo
17: Tk +- xo + dç
18: end for
19: return x²' + xo + 0
where ||
llp indicates the f--norm operator. The loss L in the constraint in Eq. is defined as:
L(x, y, 0) = (x, 0) max fz (),
j&y
where [a 0) is the confidence given by the model for classifying ær as class j. and @ is the set of its learned parameters. Assuming that the classifier assigns æ to the class exhibiting the highest confidence, i.e., y" arg max, f, (xx 0). the loss function L L(xx, y, 0) takes on negative values only when x is misclassified. Finally, the box constraint in Eq. (3) ensures that the perturbed sample lies in the feasible input space. The aforementioned problem typically involves a non-convex loss function L. (w.rt. its first argument), due to the non-convexity of the underlying decision function f. For this reason, it may admit different optimal solutions. Note also that the solution is trivial (i.e., 8* = 0) when the input sample x is already adversarial (i.e., L(x, 0) < 0).
Extension to the targeted case. The goal of targeted attack have the input sample misclassified in a given target class y'- This can be accounted for by modifying the loss function in Eq. 4 as I.' (, v/ 0) = max [ 0) l (ar, 0) LL y/, 0), i.e., changing its sign and using the target class label y' instead of the true class label
Solution algorithm. To solve Problem
reformulate it using an upper bound on ||
min c, s.t. ||0l|p Sc 6,5
(5)
and to the constraints in Eqs. steps, similarly to DDN (23], by updating the maximum perturbation size e separately from the actual perturbation 6. as represented in Fig. [a). In particular, the constraint size is adapted to reduce the distance of the constraint to the boundary (e-step), while the perturbation d is updated using projected-gradicst (6-step). This essentially amounts to a projected gradient descent algorithm that iteratively adapts the constraint size to find the minimum-now norm adversarial example. The complete algorithm is given as Algorithm|] [ while more detailed explanation the two aforementioned steps is given below.
This allows to derive algorithm that works in two main
step to minimize the loss function L within the given e-sized constraint
c-step. This step updates the upper bound on the perturbation norm (lines 4 12 in Algorithm The underlying idea is to increase e the current sample is not adversarial (i.e., T. 9, 0) 2 0), and to decrease it otherwise, while reducing the step size to dampen oscillations around the boundary
3

---

and reach convergence. In the former case (e-increase). the increment of e depends on whether an adversarial example has been previously found or not. If not, we estimate the distance to the boundary with first-order linear approximation, and set éA = | 11pp + (, y, 0)/1 V)/lVV..z VI v, 0)11g- where q is the dual norm of p. This approximation allows the attack point to make faster progress towards the decision boundary. Conversely, if an adversarial sample has been previously found, but the current sample is not adversarial, it is likely that the current estimate of E is only slightly smaller than the minimum-norm solution. We thus increase by small fraction as Eg Ek-1 (1 + me)), being > a decaying step size. In the latter case (e-decrease), if the current sample is adversarial, i.e. L( y, 9) < O, we decrease as c = CR-1 (1 - )k,,,, to check whether the current solution can be improved. If the corresponding E value is larger than the optimal ||8* lpp found so far, we retain the best value and set c₁ = ||0*|] llp. These multiplicative updates of exhibit oscillating behavior around the decision boundary, due to the conflicting requirements of minimizing the perturbation size and finding an adversarial point. To ensure convergence, anticipated before, the step size * is decayed with cosine annealing:
The 14700 7k. k. K)- "KK + (70 - -KK) (1+ + cos
kz
(6)
being 1: the current step, K the total number of steps, and To and 7K the initial and final step sizes.
Ò-step. This step updates 8 (lines 13 [7 in Algorithm[I [T]. The goal is to find the adversarial example that is misclassified with maximum confidence (i.e., for which L is minimized) within the current c-sized constraint (Eq. 5) and bounds (Eq. 33. This amounts to performing
srgjected-gradien step along the negative gradient of L. We consider normalized steepest descent with decaying step size to overcome potential issues related to noisy gradients while ensuring convergence (line (4). Note that this step only rescales the gradient by its lg norm, while preserving its direction. The step size a is decayed using cosine annealing (Eq. 6 Once ò is updated, we project it onto the given e-sized fn-norm constraint via a projection operator II, (line [5). to fulfill the constraint in Eq. (5). The projection is trivial for 0o and p = 2. For p 1, we use the efficient algorithm by Duchi et al. [1].. For p = 0, we retain only the first e components of exhibiting the largest absolute value. We finally clip the components of ò that violate the bounds in Eq. (3) (line I6p.
Execution example. In Fig. Tbb), we report an example of execution of our algorithm on bi- dimensional problem. The initial sample is updated to follow the negative gradient of L towards the decision boundary. When an adversarial point is found, the algorithm reduces c to find better solution. The point is thus projected back onto the non-ad non-adversarial region, and e increased (by a smaller, decaying amount). These oscillations allow the point to walk on the boundary towards a local optimum, i.e., an adversarial point lying on the boundary, where the gradient of the loss function and that of the norm constraint have opposite direction. FMN tends to quickly converge to a value and that
good local optimum, provided that the step size is reduced to sufficiently sufficiently- large number of iterations are performed. This is also confirmed empirically in Sect. 3
Adversarial initialization. Our attack can be initialized from the input sample æ, or from a point Pinit belonging either to different class (if the attack is untargeted) or to the target class (if the attack is targeted). When initializing the attack from Zinit, we perform a 10-step binary search between æ and Tinit, to find an adversarial point which is closer to the decision boundary. In particular, we aim to find the minimum such that L(x + (Zinit x), y, 0) < 0 (or L' < 0 for targeted attacks). Then we run our attack starting from the corresponding values of Ft, ck. òn and 8*.
Differences with DDN. FMN applies substantial changes to both the algorithm and the formulation of DDN. The main difference is that (i) DDN always rescales the perturbation to have size e. This operation is problematic when using other norms, especially sparse ones, as it hinders the ability of the attack explore the neighboring space and find suitable descent direction. Another difference is that (ii) FMN does not use the cross-entropy loss, but it uses the logit difference as the loss function L, since the latter is less affected by saturation effects. Moreover, (ii) FMN does not need an initial value for as is dynamically estimated; and (iv) y is decayed to improve convergence around better minimum-norm solutions, by more effectively dampening oscillations around the boundary. Finally, we include the possibility of (v) initializing the attack from an adversarial point, which can greatly increase the convergence speed of the algorithm, as it uses a fast line-search algorithm to find the boundary and the remaining queries to refine the result.

---

3 Experiments
We report here an extensive experimental analysis involving several state-of-the-an the-art defenses and minimum-norm attacks, covering lo. f1. E2 and &x norms. The goal is to empirically benchmark our attack and assess its effectiveness and efficiency as a tool for adversarial robustness evaluation.
3.1 Experimental Setup
Datasets. We consider two commonly-used datasets for benchmarking adversarial robustness of deep neural networks, i.e., the MNIST handwritten digits and CIFARIO. Following the experimental setup in [4], we use subset of 1000 test samples to evaluate the considered attacks and defenses.
Models. We use diverse selection of models thoroughly evaluate attacks under different con- ditions. For MNIST, we consider the following four models: MI, the 9-layer network used as the undefended baseline model by Papernot et al. [20]. Carlini and Wagner (5) M2, the robust model by Madry et al. (17). trained on &oo attacks (robustness claim: 89.6% accuracy with |00| S 0.3, current best evaluation: 88.0%); M3, the robust model by Rony al. [3], trained on E attacks (robustness claim: 87.6% accuracy with ||ōl|2 < 1.5); and M4, the IBP Large Model by Zhang et al. 27 (robustness claim: 94.3% accuracy with |8||= I 0.3). For CIFARIO, we consider three state-of- the-art robust models from RobustBench [I CI, the robust model by Madry et al. [17], trained on to attacks (robustness claim: 44.7% accuracy with ||0||> < 8//25,, current best evaluation: 44.0%) C2, the defended model by Carmon et al. 7 (top-5 in RobustBench), trained on lor attacks and additional unsupervised data (robustness claim: 62.5% accuracy with ||]||= S 8/255,, current best evaluation: 59.5%); and C3, the robust model by Rony et al. [23], trained on Eg attacks (robustness claim: 67.9% accuracy with ||ö||2 |2 I 0.5, current best evaluation: 66.4%).
Attacks. We compare our algorithm against different state-of-the-art attacks for finding minimum- norm adversarial perturbations across different norms: the Carlini & Wagner (CW) attack [5] the Decoupling Direction and Norm (DDN) attack [23), the Brendel & Bethge (BB) attack [4], and the
Fast Adaptive Boundary (FAB) attack [1O]. We use the implementation of FAB from Ding et al. [2].
while for all the remaining attacks we use the implementation available in Foolbox (21 22 All these attacks are defined on the & norm. BB and FAB are also defined on the & and &o norms, and only
BB is defined on the lo norm. We consider both untargeted and targeted attack scenarios, as defined
in Sect. 2
except for FAB, which is only evaluated in the untargeted case !
Hy perpaaarrsttsss. To ensure a fair comparison, we perform an extensive hyperparameter search for each of the considered attacks. We consider two main scenarios: tuning the hyperparameters at the sample-level and at the dataset-level. In the sample-level scenario, we select the optimal hyperparameters separately for each input sample by running each attack 10 to 16 times per sample, with different hyperparameter configuration or random initialization point each time. In the dataset- level scenario, we choose the same hyperparameters for all samples, selecting the configuration that yields the best attack performance. While sample-level tuning provides a fairer comparison across attacks, it is more computationally demanding and less practical than detaset-level tuning. addition, the latter allows us to understand how robust attacks are to suboptimal hyperparameter choices. We select the hyperparameters to be optimized for each attack as recommended by the corresponding authors 4 5 10 23). The hyperparameter configurations considered for each attack are detailed below. For attacks that are claimed to be robust to hyperparameter changes, like BB and FAB, we follow the recommendation of using larger number of random restarts rather than increasing the number of hyperparameter configurations to be tested. In addition, as BB requires being initialized from adversarial starting point, we initialize it by randomly selecting sample either from different class (in the untargeted case) or from the target class (in the targeted case). Finally, as each attack performs operations with different levels of complexity within each iteration, possibly querying the model multiple times, we set the number of steps for each attack such that at least 1, 000 forward passes (i.e., queries) are performed. This ensures fairer comparison also in terms of the computational time and resources required to execute each attack.
'The reason is that FAB does not support generating adversarial examples with particular target label. The targeted version of FAB aims to find a closer untargeted misclassification by running the attack a number of times, each time targeting different candidate class, and then selecting the best solution [10 9
5

---

60
PAR
PAR
Otec
CW
BB
Distanee
Onze
665
30
107
124
10.0
38
900
01e
138
CW
BB
1000
Ohaza
BB
Distance
100
DON
50-
10-
127
107
117
3.7
Number of quieries
Figure 2: Query- -nerr-distortion curves for MNIST (M2, top) and CIFARIO (C1, bottom) models (untar-
geted scenario).
CW. This attack minimizes the soft-constraint version our problem, i.e., mins || p + min (L 8, y. 0). -x). The hyperparameters ń and c are used to tune the trade-off between perturbation size and misclassification confidence. To find minimum- norm perturbations, CW requires setting s while the constant is tuned via binary search (re-running the attack at each iteration). We set the number binary-search steps to 9, and maximum number of iterations to 250, to ensure that at least 1, 000 queries are performed. We also set different values for c, rJ E {10-3 10-2, 10-1,1)
DDN. This attack, similarly to ours, maximizes the misclassification confidence within an e-sized constraint, while adjusting to minimize the perturbation size. We consider initial values of eo e {0.03, 0.1, 0.3, 3), and run the attack with a different number of iterations E {200, 1000}, as this affects the size of each update on 5.
BB. This attack starts from randomly drawn adversarial point, performs 10-step binary search to find a point which closer to the decision boundary, and then updates the point to minimize its per- turbation size by following the decision boundary. In each iteration, BB computes the optimal update within a given trust region of radius We consider different values for E {10-3 10-2, 10-2,11111 11,, while fix the number of steps 1000. We the attack 3 times by considering different initialization points, and eventually retain the best solution.
FAB. This attack iteratively optimizes the attack point linearly approximating its distance to the decision boundary. It uses an adaptive step size bounded by Omax and an extrapolation step n facilitate finding adversarial points. As suggested by Croce and Hein [10), tune Omax (0.1, 0.05] and 1 E (1.05, 1, 1, We consider 3 different random initialization points, and run the attack for 500 steps each time, eventually selecting the best solution.
1000 steps, using "n (0.05, 0.3), 7K 10-1, and ax 10-5, For lo. &,, and f2, we set E 51,5, 10). For loo. set [10*, 102, 103). as the normalized & step yiclds much smaller updates in the fo norm. For each hyperparameter setting we run the attack twice, starting from (i) the input sample and (ii) adversarial point.
FMN. We run FMN
Evaluation criteria. We evaluate the attacks along four different criteria: (i) perturbation size and (ii) robustness to hyperparameter selection, measured the median |81' on the test set (for a fixed budget of Q queries and for sample- and dataset-level hyperparameter tuning, where by "robustness" we mean that fixed hyperparameter configuration works well across different samples); (iii) execution time, measured convergence speed, measured as the average number of queries required converge to good-enough solution (within 10% the best value found at Q = 1000). When computing the median, we follow the evaluation in 4 the perturbation size is set 0 if clean sample is misclassified, while it is set
average time spent per query (in milliseconds): and (iv)

---

to oo when the attack fails (no adversarial is found). The median perturbation size thus represents the value for which 50% of the samples evade a particular model.
3.2 Experimental Results
Query-distortion (QD) curves. To evaluate each attack in terms of perturbation size under the same query budget Q, we use the so-called QD curves introduced by Brendel et al. 4 These curves report, for each attack, the median value of 8" as a function of the number of queries Q. For each given Q value, the optimal 8* for each point is selected among the different attack executions (i.e.. using different hyperparameters and/or initialization points, as described in Sect. 3.I). In Fig. 2 we report the QD curves for the MNIST and CIFAR 10 challenge models (i.e., M2 and CI) in the untargeted scenario. The remaining QD curves exhibit a similar behavior and can be found in the supplementary material. It is worth noting that our attack attains comparable results in terms of perturbation size across all norms, while significantly outperforming FAB and BB in the & case. typically requires also less iterations than the other attacks to converge. While the QD curves show the complete behavior of each attack as Q increases, more compact and thorough summary of our evaluation is reported below, according to the four evaluation criteria described in Sect. 3.1
Perturbation size. Table 1 reports the median value of ||ō*|| at Q 1000 queries (i.e., the last value from the query-distortion curve), for all models, attacks and norms. The values obtained with sample-level hyperparamter tuning confirm that our attack can find smaller comparable perturbations with those found by the competing attacks, in most of the untargeted and targeted cases, and that the biggest margin is achieved in the & case. FMN is only slightly worse than DDN and BB in few cases, including D2DDDN on M4 and -BB on M2 and M4. The reason may be that these robust models exhibit noisy gradients and flat regions around the clean input samples, hindering the initial optimization steps of the FMN attack.
Robustness to hyperparameter selection. The values reported in the lower part of Table showw that, when using dataset-level hyperparameter tuning, FMN outperforms the other attacks in a much larger number of cases. This shows that FMN is more robust hyperparameter changes, while other attacks like f-- and BB- suffer when using the same hyperparameters for all samples.
Execution time. The average runtime per query for each tttack-model pair, measured on worksta- tion with an NVIDIA GeForce RTX 2080 Ti GPU with 11GB of RAM, can be found in Table The results show that our attack is up 2-3 times faster, with the exception of DDN in the &g case. This is however compensated by the fact that FMN finds better solutions. The advantage is that our attack avoids costly inner projections in BB and FAB. FMN is slightly less time-efficient than DDN and CW, as it simultaneously updates the adversarial point and the norm constraint. In particular, the update on the constraint may initially require computing the norm of the gradient g (line 6 in Al Algorithm|] D. which increases the runtime of our attack. FAB computes a similar step, but for all the output classes, which hinders its scalability to problems with many classes.
Convergence speed. To get an estimate of the convergence speed, we measure the number of queries required by each attack to reach a perturbation size that is within 10% of the value found at Q = 1000 queries (the lower the better). Results are shown in Table 3 Our attack converges on par with or faster than all other attacks for almost all models, often requiring only half fifth many queries as the state of the art. Exceptions are MNIST and CIFAR 10 challenge models (M2 and C1) for &g and loo. where BB and DDN occasionally converge faster. FMN rarely needs more than 100 steps, reaching the minimal perturbation after only 10-30 queries on many datasets, models and norms.
Robust accuracy. Despite our attack being not tailored to target specific defenses, and our evaluation restricted to a subset of the testing samples, it is worth remarking that the robust accuracies of the models against attack are aligned with that reported in current evaluations, with the notable exception of C3, where our attack can decrease robust accuracy from 67.9% to 65.5%.
Experiments on ImageNet. We conclude our experiments by running an additional comparison between FMN and a widely-used (PGD) attack [17], on two pretrained ImageNet models (i.e., ResNet18 and VGG16), considering f1, l2 and Exo norms. The hyperparameters are tuned at the dataset-level using 20 validation samples. For FMN, we fix the hyperparameters as discussed before, and only tune og E (0.1, 1, 2,8), without using adversarial initialization. For PGD, we tune the step size a E {0.001, 0.01, 0.1, 1, 1,2,8) 8). We run both attacks for Q 1, 000 queries a separate set of 1, 000 samples. The success rates of both
ceciimum-confidenne attack, i..., the Projected Gradient Descent
7

---

Table 1: Median | 1p value at Q 1000 queries for targeted and untargeted attacks, with sample- level and dataset-level hyperparameter tuning.
MNIST
CIFARIO
Untorgeted M3
Targeted
Unttargeted
Targeted
Model
M2
M3
Sample level Hyperparumeter Tuning
to
BB
8
15
94
27
24
93
8
12
13
19
32
25
15
20
24
23
8
14
19
FAB
6.60
3.08
14.23
109.4
4.79
5.17
8.79
BB
6.26
5.81
13.16
5.44
12.42
10.38
20.41
6.25
3.75
4.29
8.62
8.04
10.93
15.71
Ours
5.57
2.95
12.04
1.96
12.20
6.75
18.79
7.31
3.04
3.43
8.26
7.07
9.40
15.24
FAB
1.45
1.36
2.62
2.97
0.66
0.72
0.94
CW
1.49
4.22
2.78
2.33
6.97
3.54
0.67
0.74
0.91
1.08
1.27
1.38
BB
1.43
1.34
2.61
1.61
2.27
2.04
3.23
1.79
0.63
0.70
0.91
1.07
1.26
1.38
DDN
1.46
1.71
2.56
0.79
2.29
2.20
3.27
1.33
0.64
0.73
0.91
1.09
1.29
1.39
1.23
2.50
0.94
1.89
3.19
0.61
0.91
1.03
1.38
600
FAB
.138
.337
.233
.421
.033
.043
.025
BB
.138
.330
.227
.402
.202
.355
.271
.403
.032
.041
.024
.I55
.064
.037
.134
.339
.226
.201
.399
2222
.032
.040
.024
.055
.037
Dotaset Jevel Hyperporameter Tuning
to
BB
12
152
52
145
20
179
39
183
28
44
32
29
65
33
33
18
48
28
55
16
25
FAB
8.66
225.7
163.9
312.3
20.48
BB
10.60
49.83
17.57
46.99
16.60
53.11
29.89
54.31
7.02
10.20
17.13
11.41
15.26
23.37
7.13
4.18
13.66
4,99
13.18
8.33
21.37
12.16
4.28
4.82
9.52
8.51
10.40
17.32
FAB
1.54
1.59
2.81
16.30
0.77
1.11
1.06
CW
1.63
5.15
3.71
2.50
4.72
0.86
1.00
0.99
1.36
2.90
1.55
BB
1.75
1.82
3.02
4.57
2.64
2.59
3.52
5.31
0.86
0.95
1.10
1.25
1.45
1.73
DDN
1.47
2.01
2.62
1.15
2.31
2.72
3.36
1.96
0.66
0.77
0.91
1.11
1.31
1.40
2.61
2.13
3.24
0.67
0.74
0.91
1.09
1.38
1.0
FAB
.148
.365
.248
.900
.038
.052
.029
BB
.559
.336
.243
.409
.233
.361
.280
.477
.044
004
.029
.059
.074
.022
.140
.377
.233
.426
.277
.034
.042
.024
.057
.037
Table Average execution time (milliseconds query) for each attack-oodel pair.
CIFARIO
Untargeted M2
Targeted M2
Untargeted C2
Targeted C2
Model
M1
M4
MI
M3
M4
C1
CI
fg
BB
10.76
11.85
10.19
12.02
60.88
62.17
17
62.31
57.
46.51
50.31
50.43
99.71
105.28 38
103.53
4.87
5.87
9.70
4.75
26.26
30.54
30.89
26.13
30.26
FAB
9.38
8.88
12.61
36.00
84.04
108.91
108 64
BB
6.73
7.03
7.31
12.50
43.25
43.54
43.69
43.86
32.56
37.40
37.59
68.99
73.33
74.03
Ours
5.43
5.14
6.10
9.35
5.44
5.10
6.09
9.35
27.34
31.17
31.18
26.00
30.98
31,03
FAB
10.22
10.13
13.45
36.72
84:27
109.43
108.87 87
CW
4.22
4.09
5,17
10:07
4.23
4.14
5.15
10.06
25.90
31.32
31.31
25.78
31.32
31.30
BB
4.44
4.15
5,03
12.38
26.20
26.76
27.24
31.00
26.64
31.82
31.90
48.74
54,35
54.07
DDN
3,42
3.33
4.30
8.59
3,42
3.35
4.32
8.60
24.14
29.62
29.48
23.61
29.61
29.52
Ours
4.42
5.48
9.15
4.50
4.44
5.47
24.88
30:22
30.08
25.39
30.21
30.04
Fr
FAB
10.85
10.61
14.05
36.23
84.62
109.83
109.57
BB
14.26
16.36
13.51
15.44
38.61
38.87
36.39
34.85
61.34
62.36
62.63
83.70
87.64
88.90
Ours
4.25
4.33
5.30
9.17
4.33
4.23
5.31
9.10
24.84
30.15
30,01
24.78
30.19
30.03
attacks at fixed values are reported in Table PGD in all norms.
The results show that FMN outperforms or equals
4 Related Work
Gradient-based attacks on machine learning have long history B 2
Maximum-confidence attacks optimize the adversarial loss (e.g.. the difference between the logits of the true class and the best non-true class) to find an adversarial point misclassifed with maximum confidence within given, bounded perturbation size. While attacks in this category like FGSM [15) PGD [66 17 and popular, they only partially evaluate the adversarial
momentum based extensions of PGD 26 13
8

---

Table 3: Number of queries required by each attack to reach perturbation size that is within 10% of the value obtained at Q = 1000.
MNIST
CIFARIO
Untorgeted
Targeted
Untargeted C2
Targeted C2
Model
M1
M2
M3
M4
MI
M2
M3
M4
C1
C3
C3
Eu
BB
22
43
68
114
443
71
376
497
372
58
384
500
Ours
22
82
38
182
165
46
145
48
71
37
271
146
81
FAB
44
242
152
569
124
220
72
24
314
391
614
233
722
674
570
526
464
206
Ours
21
363
34
631
25
243
37
336
48
85
31
89
1,30
38
Eg
FAB
14
60
40
532
18
28
14
CW
110
799
913
67
144
BB
20
24
20
337
21
61
20
692
22
23
22
26
27
29
DDN
12
136
474
149
670
13
19
Ours
16
94
16
190
11
136
16
188
28
23
25
29
13
800
FAB
36
50
44
11
50
50
54
BB
19
17
20
5
24
17
22
20
24
27
33
29
Ours
9
10
22
8
26
22
20
29
34
robustness of a model. Minimum-nome attacks aim to minimize the norm of the perturbation subject to being adversarial. Attacks from this class give a more complete picture of the model robustness and allow us to compute the accuracy of the model under attacks with any post-hoc defined maximum perturbation size. L-BFGS (24) solves this problem with a quasi-Newtor optimizer while CW [5] and EAD X use first-order gradient- based optimizers to minimize a weighted loss between perturbation size and misclassification confidence. To find the smallest adversarial perturbation, both CW and FAD need to tune the relative weighting which makes them query-inefficient DeepFool 19 and
SparseFool [18] compute gradients with respect to all classes in each step to estimate a linear approximation of the model from which the optimal adversarial perturbation can be computed. These two attacks are fast but do not converge to competitive solutions. BB [4] and FAB [10] use complex projections and approximations to stay close to the decision boundary (using the gradient to estimate the local geometry of the boundary) while minimizing the norm. This way of formulating minimum-nore norm optimization bypasses the tuming of a weighting term, but in the case of BB also requires an adversarial starting point to begin with. The DDN attack (23) maximizes the adversarial criterion within a given norm constraint, and iteratively reduces the norm to find the smallest possible adversarial perturbation; however, it is constrained to lg and does not perform well on other Ep norms.
The proposed FMN attack belongs to the category of minimum-nome attacks, and builds on BB, FAB and DDN to retain their main advantages. First, FMN is not spe- cific to a given norm, and converges in many fewer steps than soft-constraint attacks like CW, as it does not need to optimize the tra between perturbation size and misclassification confidence. FMN needs significantly less computational time per step than the other attacks, it is very accurate and easy to use, and it does not necessarily require being initialized from an adversarial starting point.
Table 4: Success rate (%) of FMN
against PGD on ImageNet models. ResNet18
VGG
PGD
31.4
30.4
& (c (<=1.0) L.0)
FMN
38.4
39.8
Eg (s 0.15)
PGD
61.7
61.4
FMN
65.8
66.2
8.0 (e 4-
PGD
51.0
49.0
FMN
55.2
49.0
5 Contributions, Limitations, and Future Work
This work introduces a novel minimum-norm attack that combines all desirable traits to help improve current adversarial evaluations: (i) finding smaller or comparable minimum-norm perturbations across a range of models and datasets; (ii) being less sensitive to hyperparameter choices; and being extremely fast, by (iii) reducing runtime up 3 times per query with respect to competing attacks and (iv) converging within less iterations. FMN also works with different lp norms (p- = O, 1, 2, oc) and it does not necessarily require being initialized from an adversarial starting point. Our experiments have shown that FMN rivals or surpasses other attacks in speed, reliability, efficacy and versatility. While FMN is able to find smaller perturbations consistently when compared against to and & attacks, only rivals the performance of other attacks for l2 and fox norms, especially when tested against robust models which may present obfuscated gradients. To overcome this limitation, FMN may be extended using smoothing strategies that help find better descent directions, c.g., by averaging

---

gradients on randomly-perturbee inputs. This can be regarded as an interesting extension of FMN towards attacking robust models. In this respect, we also believe that FMN may facilitate minimum- norm adaptive evaluations in a more general sense. Adaptive evaluations, where the attack is modified to be maximally effective against a new defense, are the key element towards properly evaluating adversarial robustness [6| PGD attacks are popular in part for the ease by which they can be adapted to new defenses. Since FMN combines PGD with a dynamic minimization of the perturbation size, we argue that our attack can also be easily adapted to new defenses, thereby facilitating adaptive evaluations. FMN may also benefit from other improvements that have been suggested for PGD, including momentum, cyclical step sizes or restarts. We leave such improvements to future work.
To conclude, we firmly believe that FMN will establish itself as a useful tool in the arsenal of robust- ness evaluation. By facilitating more reliable robustness evaluations, we expect that FMN will foster advancements the development of machine-learning models with improved robustness guarantees. We thus argue that there are neither ethical aspects nor evident future societal consequences with potential negative impacts that should be specifically addressed in the context of this work.
Acknowledgements
This work has been partly supported by the PRIN 2017 project RexLearn (grant no. 2017TWNMH2), funded by the Italian Ministry of Education, University and Research; by the EU H2020 project ALOHA, under the European Union's 's Horizon 2020 research and innovation programme (grant no. 780788); and by BMK, BMDW, and the Province of Upper Austria the frame of the COMET Programme managed by FFG in the COMET Module S3AL Wieland Brendel acknowledges support from the German Federal Ministry of Education and Research (BMBF) through the Competence Center for Machine Learning (TUEAAI, FKZ 011S 18039A), from the German Science Foundation (DFG) under grant no. BR 6382/1-1 (Emmy Noether Program) as well as support by Open Philantropy and the Good Ventures Foundation.
References
[1] A. Athalye, N. Carlini, and D. A. Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In ICML, volume 80 of JMLR Workshop and Conf. Proceedings, pages 274 JMLR.org, 2018.
[2] B. Biggio and F. Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Puttern Recognition, 84:317-331, 2018
[3] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šıdiić, P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In H. Blockeel, K. Kersting, S. Nijssen, and F. Zelezný, editors, Machine Learning and Knowledge Discovery in Databases (ECML PKDD), Part III, volume 8190 of LNCS, pages 387-402. Springer Berlin Heidelberg, 2013.
[4] W. Brendel, J. Rauber, M. Kümmerer, I. Ustyuzhaninov, and M. Bethge. Accurate, reliable and fast robustness evaluation. In Advances in Neural Inf. Proc. Systems, pages 12861-12871 2019.
[5] N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pages 39-57. IEEE, 2017.
[6] N. Carlini, A. Athalye, N. Papernot, W. Brendel, J. Rauber, D. Tsipras, I. Goodfellow. A. Madry, and A. Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv: 2019.
[7] Y. Carmon, A. Raghunathan, L. Schmidt, J. C. Duchi, and P. S. Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Inf. Proc. Systems, pages 11 192-1 1203, 2019.
[8] P.-Y. Chen, Y. Sharma, H. Zhang, J. Yi, and C.-J. Hsieh. EAD: Elastic-net attacks to deep neural networks via adversarial examples. arXiv preprint 17Xiv:1709.041 14, 2017.
[9] F. Croce and M. Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In ICML, 2020.
[10] Croce and M. Hein. Minimally distorted adversarial examples with a fast adaptive boundary attack. In Int'l Conf. on Machine Learning, pages 2196-2205. PMLR, 2020.
10

---

[11] F. Croce, M. Andriushchenko. V. Sehwag, N. Flammarion, M. Chiang, P. Mittal, and M. Hein. Robustbench: a standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.09677, 2020.
[12] G. W. Ding, L. Wang, and X. Jin. AdverTorch v0.1: I: An adversarial robustness toolbox based on pytorch. arXiv preprint arXiv: 07000........... 2019.
[13] Y. Dong, F. Liao, T. Pang, H. Su, J. Zhu, X. Hu, and Li. Boosting adversarial attacks with momentum. In Proceedings of the IEEE Conf. Computer Vision and Pattern Recognition, 2018.
[14] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the 1-ball for learning in high dimensions. In Proceedings of the 25th Int'l Conf. on Machine learning. pages 272-279, 2008
[15] I. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. In Int'l Conf. on Learning Representations, 2015. URL http:://arxi..org/////./
6572
[16] A. Kurakin, I. Goodfellow, and S. Bengio. Adversarial examples in the physical world. arXiv preprint 1rXiv: 2016.
[17] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint (aoe:/706000.5 2017.
[18] A. Modas, S.-M. Moosavi-Dezfooli, and P. Frossard. Sparsefool: a few pixels make big difference. In The IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). 2019.
[19] S.-M. Mozoovi- A. Fawzi, and Frossard. Deepfool: simple and accurate method to fool deep neural networks. In The IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), June 2016.
[20] N. Papernot, P. McDaniel, X. Wu, S. Jha, and A. Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In 2016 IEEE symposium security and privacy (SP), pages 582-597. IEEE, 2016.
[21] J. Rauber, W. Brendel, and M. Bethge. Foolbox: A python toolbox to benchmark the robustness of machine learning models. In Reliable Machine Learning in the Wild Workshop, 34th Int'l Conf. on Machine Learning, 2017. Uttp://://aaxtt org/abs. 0abbb//777.0041111
[22] J. Rauber, R. Zimmermann, M. Bethge, and W. Brendel. Foolbox native: Fast adversarial attacks benchmark the robustmess of machine learning models in pytorch, tensorflow, and jax. Journal of Open Source Software, 5653),2607, 2020. doi: 10.21 02607 URL https: org/10 10. 21105 02607
[23] J. Rony, L. G. Hafemann, L. S. Oliveira, I. B. Ayed, R. Sabourin, and E. Granger. Decoupling direction and norm for efficient gradient-based 12 adversarial attacks and defenses. In Pro- ceedings of the IEEE Conf. on Computer Vision and Pattern Recognition, pages 4322-4330, 2019.
[24] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, Goodfellow, and R. Fergus. Intriguing properties of neural networks. In Int'l Conf. on Learning Representations, 2014. URL http:ttt://arxivvorr org/ abs/13122 6199
[25] Tramer, N. Carlini, W. Brendel, and A. Madry. On adaptive attacks to adversarial example defenses. In Advances in Neural Inf. Proc. Systems, 2020.
[26] J. Uesato, B. O'Donoghue, A. d. Oord, and P. Kohli. Adversarial risk and the dangers of evaluating against weak attacks. arXiv preprint arXiv: (00.::0600.0066 2018
[27] H. Zhang, H. Chen, C. Xiao, S. Gowal, R. Stanforth, B. Li. D. Boning, and C.-J. Hsich. Towards stable and efficient training of verifiably robust neural networks. In Int'l Conf. on Learning Representations, 2020. htt.ttttt///onnreeee
net/forunt www.ummmiddduuuuiiie Slskkkkk1rrF


Reviews:
[{"review_id": "s0_rM1nxsnV", "reviewer": "Reviewer_sShH", "summary": "This paper presents an adversarial attack (FMN) that generates minimum-norm adversarial examples. The attack builds on the DDN attack but generalizes to $l_p$ norms beyond the $l_2$ norm that the DDN attack is specialized for.\n\n- For the $l_0$, $l_1$ and $l_\\infty$ norms, the attack has better performance: it has a consistently lower execution time per query, is more query efficient, and results in adversarial examples of comparable or smaller norm compared to the state-of-the-art.\n- For the $l_2$ norm, the attack has comparable performance to the DDN attack: it has a slightly higher execution time per query, has comparable query efficiency, and results in adversarial examples of comparable norm compared to the state of the art (DDN).\n\nIn addition to the advantages in execution time and query efficiency, the method does not require adversarial starting points as some other methods do.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Review Summary\n\n## Strengths\n\n- The paper has conducted a very thorough evaluation comparing the proposed attack to other attacks that are the state-of-the-art.\n- The faster execution time for FMN means that it will be a useful tool for practitioners trying to estimate the minimum-norm attack on a classifier for a particular clean example.\n\n## Areas of Improvement\n\n- The experimental data provided does not substantiate the claim that FMN is more robust to the choice of hyperparameter.\n  - The fact that FMN performs better when hyper-parameters are tuned at the dataset-level could simply mean that the best hyperparameter is the same across most of the samples (allowing, for example, the same hyperparameters to be applied to a test sample once hyperparameter tuning has been carried out on the training set), but does not mean that changing the hyperparameters at the dataset-level would not have a significant impact on attack performance.\n  - Furthermore, for the $l_2$ and $l_\\infty$ norms, the best alternative method (DDN and BB respectively) see a similar degradation in attack performance to FMN when comparing the sample-level and dataset-level hyperparameter tuning.\n- As detailed in the section on originality, it is not clear what changes to the DDN algorithm enable FMN to generalize to norms other than $l_2$.\n- As detailed in the section on clarity, this paper has some statements that are not supported by either references or any of the results presented, and would be greatly improved by clarifying these statements. One that I would like to highlight in particular is the claim in the abstract that \"FMN significantly outperforms existing attacks in terms of convergence speed and computation time\"; this is not borne out in the data for the $l_2$ norm. (The success of FMN on other norms is still valuable, and I'd rather this paper not overstate its contribution.)\n\n---\n\n# Originality\n\nThe presented FMN attack appears similar to the DDN attack [25] in many respects, such as the choice of how to decrease / increase $\\epsilon$ and the projection and clipping step at the end of the for loop.\n\nWhile there are differences in details that make for a substantially different algorithm (as identified at the end of Section 2), it would be helpful to understand which of the differences (if any) contribute to the performance improvement (e.g. via an ablation study). This is particularly important since DDN and FMN perform basically on par with each other on the $l_2$ examples shown. In addition, this paper claims in Line 44 that DDN \"is specific to the $l_2$ norm and cannot be readily extended to other norms\" --- is the issue that it is not possible to project $\\delta_k$ onto an $\\epsilon-k$ sphere in the appropriate norm, or is it simply that this leads to poor performance (perhaps this is what Lines 124-126)?\n\n# Quality\n\nThis work presents thorough experimental results comparing FMN against state-of-the-art attacks, comparing the strength of the attacks as well as their runtime.\n\n# Clarity\n\n## Unsupported Statements\n\nThis work has some statements that are not supported by either references or any of the results presented. These statements should be clarified to avoid confusing readers with unsupported assertions, and ensure that the contributions of the paper can be clearly understood.\n\n- Line 20: \"all attacks make certain assumptions about the underlying geometry and properties of the optimization problem\" -> Is there a reference to support this assertion? What assumptions are made about the geometry?\n- Line 26: \"most (attacks) ... are just small variations of the same technique, make similar underlying assumptions and thus tend to fail jointly\" -> Is there a reference to support this assertion? In particular, which sets of attacks tend to fail jointly, and which are distinct?\n- Line 39: \"These attacks (like BB or FAB) ... may require an adversarial starting point\" -> Do some of these attacks require an adversarial starting point, or do all of them require one sometimes?\n- Line 50: \"while finding equal or better optima\" -> this phrasing suggests that FMN finds a successful adversarial attack of smaller norm on a per-sample basis (which _may_ be true; my objection is merely that the presented results do not demonstrate this); this paper should either show results to prove this, or emphasize that the claim is that the _average_ minimum norm found by FMN is smaller.\n- Line 131: \"initializing the attack from an adversarial point, which can greatly increase the convergence speed of the algorithm\" -> while this may be true for other attacks (and makes intuitive sense), I could not find evidence in the paper to support the assertion that initializing attacks from an adversarial point increases convergence speed - much less \"greatly\".\n- Line 160 + Footnote 1:\n  - The footnote explains that FAB is not evaluated in the targeted case because it \"implements a substantially different attack\", but does not elaborate on why making a comparison to this different attack is not appropriate. It seems like the issue that this paper is alluding to is that the \"targeted\" FAB attack is actually a method to accelerate finding an untargeted adversarial example, and does not guarantee (despite the name) that the resulting adversarial example will be labelled as belonging to the target category by the classifier. If so, it would be very helpful to make this clear; a short explanation like \"FAB does not support generating adversarial examples with a particular target label\" should suffice.\n- Line 234: \"The reason may be that these robust models exhibit noisy gradients and flat regions around the clean input samples\" -> M2, M3, M4 and C1, C2, C3 are all robust models - is there any evidence to suggest that some of them have noisier gradients / flatter regions around the clean input samples than others?\n\n## Miscellaneous Issues\n\n- Line 1: \"Evaluating adversarial robustness amounts to finding the minimum perturbation needed to have an input sample misclassified\" -> not necessarily; the robustness of defended models is often reported against attacks with a fixed budget; determining whether or not such an attack exists can be computationally less expensive than finding the minimum perturbation.\n- Algorithm 1, Line 6: The variable $q$ is referenced here without being introduced (it is first introduced in Line 86)\n- Algorithm 1, Line 14: normalizes $g$ by its $l_2$ norm, similar to DDN --- is this meant to be the $l_q$ norm or is it intended?\n- Figure 2: It would be helpful to label which figures correspond to the M2 and C1 model.\n\n## Suggestions\n\n- Table 3: I'm finding it challenging to interpret the results presented in Table 3 as it relates to the efficiency of each attack. If the final perturbation size $\\epsilon$ at Q=1000 is the same, then an attack with a smaller number of queries required to reach a perturbation size $\\epsilon'$ within 10% of $d$ would be superior - but Table 1 shows that there _is_ significant variation in the value at Q=1000 itself. If Attack 1 makes slow but steady progress to a significantly smaller perturbation size at Q=1000, while Attack 2 makes quick progress, but plateauing at a larger perturbation size, most practitioners would probably prefer to select Attack 1. Personally, I find that the query-distortion curves already encapsulate this information well; if data in tabular form is still preferred, perhaps presenting the number of queries required by each attack to reach a perturbation size within 10% of _the best known value across all attacks_ would be better.\n- While I appreciated the detailed experiments provided, providing all of the data in tabular form in the main body of the paper made it harder for me to understand. (I understand that a previous reviewer may have asked for all of the data). Summarizing the data (for example showing the ratio of average execution time of other attacks to that of FMN in a scatter plot) would make it easier for a reader to grasp the information.\n\n# Additional Questions\n\n- When an adversarial example has been previously found, it seems like the $\\epsilon$-increase amount is selected such that the algorithm could test an $\\epsilon$ value that is larger than the best known adversarial example. (In particular, we could have $\\epsilon_{k+1} = \\epsilon_{k-1}(1-\\gamma_k)(1+\\gamma_{k+1}) \\leq \\epsilon_{k-1}(1-\\gamma_k)(1+\\gamma_k) = \\epsilon_{k-1}(1-\\gamma_k^2) < \\epsilon_{k-1}$, so we would have another $\\epsilon$-increase if the true minimum value of $\\epsilon$ is between $\\epsilon_{k-1}(1-\\gamma_k^2)$ and $\\epsilon_{k-1}$.) This seems like it would waste queries; I am curious why a binary-search approach is not used instead.\n\n---\n\n# Updated Review\n\nI am updating the score for this submission (6 -> 7) as the authors have effectively addressed my concerns (both in the \"areas for improvement\" and in \"clarity\") which were affecting my overall evaluation. Please see the commen thread below for specifics.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "qwA2JJUl47t", "reviewer": "Reviewer_qsb1", "summary": "The paper proposes a new adversarial attack called Fast Minimum Norm (FMN) attack. FNM retains the major advantages of DDN (Decoupled direction and norm attack) [1]. While DDN is specific to the l_{2} norm and cannot be easily extended to other norms, the authors show that FMN can be directly extended to other norms such as l_{0}, l_{1} and l_{\\infty} norms. \n\nThe authors conduct experiments using many different models and datasets and FMN outperforms previous attacks in terms of convergence speed. The minima found are either comparable or better across almost all tested scenarios. \n\nI agree with the author's assessment that it can be a very useful tool for adversarial robustness evaluation.\n\n[1] J. Rony, L. G. Hafemann, L. S. Oliveira, I. B. Ayed, R. Sabourin, and E. Granger. Decoupling direction and norm for efficient gradient-based l2 adversarial attacks and defenses.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors propose a new adversarial attack called FMN which keeps the advantages of the previously proposed DDN, while also allowing threat models with norms other than l_{2}. \n\nThis paper is clearly written and easy to understand.\n\nPros:\n\n1. The experimental setup uses multiple different models and datasets (MNIST, CIFAR-10 and Imagenet). The evaluation is very comprehensive. \n\n2. FMN has the additional advantage that it does not require the starting point of the optimization to be an adversarial example. \n\n3. The proposed attack achieves smaller (or comparable) perturbation sizes with lesser computation time when compared to the existing state-of-the-art methods. It can be a very useful tool when carrying out robustness evaluations.\n\n4. The proposed attack works well under different l_{p} norm threat models. Results are significantly better than the previous state of the art for the l_{0} and l_{1} threat models. \n\nCons:\n\n1. The authors should clarify why they use the median as a measure of robustness instead of the widely used mean. But I did not let this negatively affect my review because median has been used in a previous NeurIPS publication [1]. \n\nOverall, I believe it is a solid contribution and recommend acceptance. \n\n\n[1] W. Brendel, J. Rauber, M. Kümmerer, I. Ustyuzhaninov, and M. Bethge. Accurate, reliable and fast robustness evaluation. In Advances in Neural Information Processing Systems, pages 12861–12871, 2019.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since the paper proposes a new adversarial attack that can be used to comprehensively test robustness of a neural network against many different threat models, I do not foresee any potential negative societal consequences of this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "DwoJWuj2th", "reviewer": "Reviewer_Qt35", "summary": "This papers present new white-box minimum-norm adversarial attacks adapted to the case of the $\\ell_p$ balls for $p=0,1,2,\\infty$. It extends the DDN attacks which only considered $\\ell_2$ norms.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The experimental part is caried with much care and the paper is very well written and interesting to read. The main contribution of the paper is to extend a known technique that deal with $\\ell_2$ constraints to deal with $\\ell_p$ (for $p=0,1,2,\\infty$). This contribution seems however not sufficiently original and motivated for such a conference as NeurIPS. I also found some unclear statements that I will now details.\n\n- Extension to other norms. The main contribution of this paper is to extend a known technique DNN dealing with $\\ell_2$ constraints to adversarial attacks that can deal with $\\ell_p$ for $p=0,1,2,\\infty$. Yet, it is not sufficiently motivated:\n1) The motivation for using different norms is not sufficiently pointed out. \n2) Among the chosen norms, why choosing only the $\\ell_p$ for $p=0,1,2,\\infty$? There are several papers considering other norms as a way to \"having an arsenal of diverse attacks that can be adapted to specifics defense [...]\", see, e.g., Wasserstein balls [W2019] or group-lasso [Xu2018].\n3) Can your algorithm adapt to other norms? If so, what are the experimental performances?\n4) Looking only at $\\ell_p$ type of neighborhood is very reminiscent of one of the claims of the authors that \"most of them [adversarial attacks] are just small variations of the same technique, make similar assumptions [...]\". Indeed, we can, for instance, understand this choice of the $\\ell_p$ norms for a measure of perturbation as such a similar assumption shared by most of works.\n\n\n- Line 25-27 \"While it may seem that the number of attacks is already large, most of them are just small variations of the same technique, make similar underlying assumptions and thus tend to fail jointly\".\nThis sentence is much too vague and unprecise:\n1) Can you defend this negative statement with a better explanation or references? \n2) What type of \"similar underlying assumptions\" are you referring to? \n3) Your sentence might be understood as a claim of a causal link between the failure of the methods and the fact that they make the same underlying assumptions. Can you write more explicitly that this is an observation rather than an established causal link? Or if not provide refs, explanations or numerical evidences?\n4) To what same technique are you referring? \n5) \"Most of them\" is an unprecised claim.\n\n\nSome minor comments:\n- Title: the title misleading let the reader believe that there is a great generality in the variety of different norms the paper deal with while it focuses only on the $\\ell_p$ with $p=0,1,2,\\infty$. So, could you either modify the title or explicit in the paper that your method is versatile to any norms?\n\n- Line 96 \"decayed with cosine annealing\": It would be nice to add a reference.\n\n- Line 127 FMN does not use the cross-entropy loss but rather the logit difference as the loss function $L$\". Can you explain the rationale behind this difference with DNN?\n\n[Xu 2018] Kaidi Xu, Sijia Liu, Pu Zhao, Pin-Yu Chen, Huan Zhang, Quanfu Fan, Deniz Erdogmus, Yanzhi Wang, and\nXue Lin. Structured adversarial attack: Towards general implementation and better interpretability\n\n[W2019] Eric Wong, Frank R Schmidt, and J Zico Kolter. Wasserstein adversarial examples via projected sinkhorn\niterations.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours."}, "extra_text": {}}, {"review_id": "BNNcegebNzb", "reviewer": "Reviewer_Rii9", "summary": "This paper proposes a new adversarial attack algorithm for finding the smallest perturbation necessary to fool a classifier under various $\\ell_p$ norms. The algorithm is similar to DDN, but includes a few improvements, including using the logit margin loss instead of cross-entropy, using a more complex algorithm for updating the bound $\\epsilon$, and not always projecting the adversarial example to the boundary. They evaluate the new attack, FMN, on a variety of classifiers on MNIST and CIFAR-10.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "First, I would like to commend the authors on the clear presentation and extensive experiments in the paper. I found the paper easy to read, with the algorithm and experiments clearly organized and explained. The separation of the sample-level and dataset-level hyperparameter tuning was helpful to compare typical attack use (dataset-level tuning) and best-case performance. The authors were also clear about the relationship with prior work.\n\nThe novelty of FMN is somewhat limited, since it is quite similar to DDN. Accordingly, the results for FMN are quite similar to DDN, although they seem to generally improve on it slightly. The applicability of FMN to the $\\ell_0$ and $\\ell_1$ norms is useful. Since the differences between FMN and DDN are heuristics and the results empirical, it would improve the paper if an ablation study were done to show which changes between DDN and FMN actually lead to the improved performance of FMN. This could lead to more general insights about how to improve adversarial attacks.\n\nOverall, while the paper is well-presented, the results are somewhat marginal and it is not clear which changes in FMN lead to the improved performance over DDN.\n\nPotential typos/grammatical issues:\n * Line 72: should \"and\" be \"added\"?\n * Line 86: \"being *q*\" should be \"*q* being\"\n * Line 298: \"much\" should be \"many\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact were adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a fast minimum-norm (FMN) attack that works with different norm perturbation models and is robust to hyper-parameter choices. Some reviewers had concerns regarding the novelty of the work with respect to prior works (e.g. DDN). Authors clarified some of these concerns in the discussion period. Overall I think the paper makes good contributions. I suggest authors to take reviewers' suggestions into account in the final draft of their work.  
Decision: Accept (Poster)