Fast Minimum-norm Adversarial Attacks through Adaptive Norm Constraints
Year: 2021

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 `p-norm perturbation models (p = 0, 1, 2,∞), 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 `p-norm constraint of size , while adapting to minimize the distance of the current sample to the decision boundary. Extensive experiments show that FMN significantly outperforms existing `0, `1, and `∞-norm attacks in terms of perturbation size, convergence speed and computation time, while reporting comparable performances with state-of-the-art `2-norm attacks. Our open-source code is available at: https://github.com/pralab/Fast-Minimum-Norm-FMN-Attack.

heading: 1 Introduction
text: Learning algorithms are vulnerable to adversarial examples, i.e., intentionally-perturbed inputs aimed to mislead classification at test time [24, 3]. While adversarial examples have received much attention, evaluating the robustness of deep networks against them remains a 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-box attacks [5, 1]. Having an arsenal of diverse attacks that can be adapted to specific defenses is one of the most promising avenues for increasing confidence in white-box robustness evaluations [6, 25]. 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 (see, e.g., [25], in which projected-gradient attacks all fail similarly against the “Ensemble Diversity” defense).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this work, we focus on minimum-norm attacks for evaluating adversarial robustness, i.e., attacks that aim to mislead classification by finding the smallest input perturbation according to a given norm. In contrast to maximum-confidence attacks, which maximize confidence in a wrong class within a given perturbation budget, the former are better suited to evaluate adversarial robustness as one can compute the accuracy of a 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 sub-categories: (i) soft-constraint attacks, (ii) boundary attacks and (iii) projected-gradient 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 a 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 a relatively expensive optimization problem in each step. Finally, recent minimum-norm projected-gradient attacks like DDN [23] perform a maximum-confidence attack in each step under a given perturbation budget , 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, it is specific to the `2 norm and cannot be readily extended to other norms.
To overcome the aforementioned limitations, in this work we propose a novel, fast minimum-norm (FMN) attack (Sect. 2), which retains the main advantages of DDN while generalizing it to different `p norms (p = 0, 1, 2,∞). We perform large-scale experiments on different datasets and models (Sect. 3), showing that FMN is able to significantly outperform current minimum-norm attacks in terms of convergence speed and computation time (except for `2-norm attacks, for which FMN achieves comparable results), while finding equal or better optima, on average, across almost all tested scenarios and `p 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).

heading: 2 Minimum-Norm Adversarial Examples with Adaptive Projections
text: Problem formulation. Given an input sample x ∈ [0, 1]d, belonging to class y ∈ {1, . . . , c}, the goal of an untargeted attack is to find the minimum-norm perturbation δ? such that the corresponding adversarial example x? = x+ δ? is misclassified. This problem can be formulated as:
δ? ∈ arg min δ
‖δ‖p , (1)
s.t. L(x+ δ, y,θ) < 0 , (2)
x+ δ ∈ [0, 1]d , (3)
Algorithm 1 Fast Minimum-norm (FMN) Attack Input: x, the input sample; t, a variable denoting whether the attack is targeted (t = +1) or
untargeted (t = −1); y, the target (true) class label if the attack is targeted (untargeted); γ0 and γK , the initial and final -step sizes; α0 and αK , the initial and final δ-step sizes; K, the total number of iterations.
Output: The minimum-norm adversarial example x?. 1: x0 ← x, 0 = 0, δ0 ← 0, δ? ←∞ 2: for k = 1, . . . ,K do 3: g ← t · ∇δL(xk−1 + δ, y,θ) // loss gradient 4: γk ← h(γ0, γK , k,K) // -step size decay (Eq. 6) 5: if L(xk−1, y,θ) ≥ 0 then 6: k = ‖δk−1‖p + L(xk−1, y,θ)/‖g‖q if adversarial not found yet else k = k−1(1 + γk) 7: else 8: if ‖δk−1‖p ≤ ‖δ?‖p then 9: δ? ← δk−1 // update best min-norm solution 10: end if 11: k = min( k−1(1− γk), ‖δ?‖p) 12: end if 13: αk ← h(α0, αK , k,K) // δ-step size decay (Eq. 6) 14: δk ← δk−1 + αk · g/‖g‖2 // gradient-scaling step 15: δk ← Π (x0 + δk)− x0 16: δk ← clip(x0 + δk)− x0 17: xk ← x0 + δk 18: end for 19: return x? ← x0 + δ?
where || · ||p indicates the `p-norm operator. The loss L in the constraint in Eq. (2) is defined as: L(x, y,θ) = fy(x,θ)−max
j 6=y fj(x,θ) , (4)
where fj(x,θ) is the confidence given by the model f for classifying x as class j, and θ is the set of its learned parameters. Assuming that the classifier assigns x to the class exhibiting the highest confidence, i.e., y? = arg maxj∈1,...,c fj(x,θ), the loss function L(x, y,θ) takes on negative values only when x is misclassified. Finally, the box constraint in Eq. (3) ensures that the perturbed sample x+ δ lies in the feasible input space. The aforementioned problem typically involves a non-convex loss function L (w.r.t. its first argument), due to the non-convexity of the underlying decision function f . For this reason, it may admit different locally-optimal solutions. Note also that the solution is trivial (i.e., δ? = 0) when the input sample x is already adversarial (i.e., L(x, y,θ) < 0).
Extension to the targeted case. The goal of a targeted attack is to 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 Lt(x, y′,θ) = maxj 6=y′ fj(x,θ)− fy′(x,θ) = −L(x, y′,θ), i.e., changing its sign and using the target class label y′ instead of the true class label y.
Solution algorithm. To solve Problem (1)-(3), we reformulate it using an upper bound on ‖δ‖p: min ,δ , s.t. ‖δ‖p ≤ , (5)
and to the constraints in Eqs. (2)-(3). This allows us to derive an algorithm that works in two main steps, similarly to DDN [23], by updating the maximum perturbation size separately from the actual perturbation δ, as represented in Fig. 1(a). In particular, the constraint size is adapted to reduce the distance of the constraint to the boundary ( -step), while the perturbation δ is updated using a projected-gradient step to minimize the loss function L within the given -sized constraint (δ-step). This essentially amounts to a projected gradient descent algorithm that iteratively adapts the constraint size to find the minimum-norm adversarial example. The complete algorithm is given as Algorithm 1, while a more detailed explanation of the two aforementioned steps is given below.
-step. This step updates the upper bound on the perturbation norm (lines 4-12 in Algorithm 1). The underlying idea is to increase if the current sample is not adversarial (i.e., L(xk−1, y,θ) ≥ 0), and to decrease it otherwise, while reducing the step size to dampen oscillations around the boundary
and reach convergence. In the former case ( -increase), the increment of depends on whether an adversarial example has been previously found or not. If not, we estimate the distance to the boundary with a first-order linear approximation, and set k = ‖δk−1‖p + L(xk−1, y,θ)/||∇L(xk−1, y,θ)||q , 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 is only slightly smaller than the minimum-norm solution. We thus increase by a small fraction as k = k−1 (1 + γk), being γk a decaying step size. In the latter case ( -decrease), if the current sample is adversarial, i.e., L(xk−1, y,θ) < 0, we decrease as k = k−1 (1− γk), to check whether the current solution can be improved. If the corresponding k value is larger than the optimal ‖δ?‖p found so far, we retain the best value and set k = ‖δ?‖p. These multiplicative updates of exhibit an oscillating behavior around the decision boundary, due to the conflicting requirements of minimizing the perturbation size and finding an adversarial point. To ensure convergence, as anticipated before, the step size γk is decayed with cosine annealing:
γk = h(γ0, γK , k,K) = γK + 1 2 (γ0 − γK)
( 1 + cos ( kπ K )) , (6)
being k the current step, K the total number of steps, and γ0 and γK the initial and final step sizes.
δ-step. This step updates δ (lines 13-17 in Algorithm 1). The goal is to find the adversarial example that is misclassified with maximum confidence (i.e., for which L is minimized) within the current -sized constraint (Eq. 5) and bounds (Eq. 3). This amounts to performing a projected-gradient step along the negative gradient of L. We consider a normalized steepest descent with decaying step size α to overcome potential issues related to noisy gradients while ensuring convergence (line 14). Note that this step only rescales the gradient by its `2 norm, while preserving its direction. The step size α is decayed using cosine annealing (Eq. 6). Once δ is updated, we project it onto the given -sized `p-norm constraint via a projection operator Π (line 15), to fulfill the constraint in Eq. (5). The projection is trivial for p =∞ and p = 2. For p = 1, we use the efficient algorithm by Duchi et al. [14]. For p = 0, we retain only the first components of δ exhibiting the largest absolute value. We finally clip the components of δ that violate the bounds in Eq. (3) (line 16).
Execution example. In Fig. 1(b), we report an example of execution of our algorithm on a bidimensional 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 to find a better solution. The point is thus projected back onto the non-adversarial region, and 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 good local optimum, provided that the step size is reduced to a sufficiently-small value and that a 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 x, or from a point xinit belonging either to a different class (if the attack is untargeted) or to the target class (if the attack is targeted). When initializing the attack from xinit, we perform a 10-step binary search between x and xinit, to find an adversarial point which is closer to the decision boundary. In particular, we aim to find the minimum such that L(x + Π (xinit − x), y,θ) < 0 (or Lt < 0 for targeted attacks). Then we run our attack starting from the corresponding values of xk, k, δk and δ?.
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 . This operation is problematic when using other norms, especially sparse ones, as it hinders the ability of the attack to explore the neighboring space and find a 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, (iii) FMN does not need an initial value for , as is dynamically estimated; and (iv) γ 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.

heading: 3 Experiments
text: We report here an extensive experimental analysis involving several state-of-the-art defenses and minimum-norm attacks, covering `0, `1, `2 and `∞ norms. The goal is to empirically benchmark our attack and assess its effectiveness and efficiency as a tool for adversarial robustness evaluation.

heading: 3.1 Experimental Setup
text: Datasets. We consider two commonly-used datasets for benchmarking adversarial robustness of deep neural networks, i.e., the MNIST handwritten digits and CIFAR10. Following the experimental setup in [4], we use a subset of 1000 test samples to evaluate the considered attacks and defenses.
Models. We use a diverse selection of models to thoroughly evaluate attacks under different conditions. For MNIST, we consider the following four models: M1, 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 `∞ attacks (robustness claim: 89.6% accuracy with ‖δ‖∞ ≤ 0.3, current best evaluation: 88.0%); M3, the robust model by Rony et al. [23], trained on `2 attacks (robustness claim: 87.6% accuracy with ‖δ‖2 ≤ 1.5); and M4, the IBP Large Model by Zhang et al. [27] (robustness claim: 94.3% accuracy with ‖δ‖∞ ≤ 0.3). For CIFAR10, we consider three state-ofthe-art robust models from RobustBench [11]: C1, the robust model by Madry et al. [17], trained on `∞ attacks (robustness claim: 44.7% accuracy with ‖δ‖∞ ≤ 8/255, current best evaluation: 44.0%); C2, the defended model by Carmon et al. [7] (top-5 in RobustBench), trained on `∞ attacks and additional unsupervised data (robustness claim: 62.5% accuracy with ‖δ‖∞ ≤ 8/255, current best evaluation: 59.5%); and C3, the robust model by Rony et al. [23], trained on `2 attacks (robustness claim: 67.9% accuracy with ‖δ‖2 ≤ 0.5, current best evaluation: 66.4%). Attacks. We compare our algorithm against different state-of-the-art attacks for finding minimumnorm 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 [10]. We use the implementation of FAB from Ding et al. [12], while for all the remaining attacks we use the implementation available in Foolbox [21, 22]. All these attacks are defined on the `2 norm. BB and FAB are also defined on the `1 and `∞ norms, and only BB is defined on the `0 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.1
Hyperparameters. 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 a different hyperparameter configuration or random initialization point each time. In the datasetlevel 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 dataset-level tuning. In 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 a larger number of random restarts rather than increasing the number of hyperparameter configurations to be tested. In addition, as BB requires being initialized from an adversarial starting point, we initialize it by randomly selecting a sample either from a 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 a fairer comparison also in terms of the computational time and resources required to execute each attack.
1The reason is that FAB does not support generating adversarial examples with a 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 a different candidate class, and then selecting the best solution [10, 9].
CW. This attack minimizes the soft-constraint version of our problem, i.e., minδ ‖δ‖p+c ·min(L(x+ δ, y,θ),−κ). 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 κ = 0, while the constant c is tuned via binary search (re-running the attack at each iteration). We set the number of binary-search steps to 9, and the maximum number of iterations to 250, to ensure that at least 1, 000 queries are performed. We also set different values for c, η ∈ {10−3, 10−2, 10−1, 1}. DDN. This attack, similarly to ours, maximizes the misclassification confidence within an -sized constraint, while adjusting to minimize the perturbation size. We consider initial values of 0 ∈ {0.03, 0.1, 0.3, 1, 3}, and run the attack with a different number of iterations K ∈ {200, 1000}, as this affects the size of each update on δ.
BB. This attack starts from a randomly-drawn adversarial point, performs a 10-step binary search to find a point which is closer to the decision boundary, and then updates the point to minimize its perturbation 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 ρ ∈ {10−3, 10−2, 10−1, 1}, while we fix the number of steps to 1000. We run the attack 3 times by considering different initialization points, and eventually retain the best solution.
FAB. This attack iteratively optimizes the attack point by linearly approximating its distance to the decision boundary. It uses an adaptive step size bounded by αmax and an extrapolation step η to facilitate finding adversarial points. As suggested by Croce and Hein [10], we tune αmax ∈ {0.1, 0.05} and η ∈ {1.05, 1, 3}. We consider 3 different random initialization points, and run the attack for 500 steps each time, eventually selecting the best solution.
FMN. We run FMN for K = 1000 steps, using γ0 ∈ {0.05, 0.3}, γK = 10−4, and αK = 10−5. For `0, `1, and `2, we set α0 ∈ {1, 5, 10}. For `∞, we set α0 ∈ {101, 102, 103}, as the normalized `2 step yields much smaller updates in the `∞ norm. For each hyperparameter setting we run the attack twice, starting from (i) the input sample and (ii) an adversarial point.
Evaluation criteria. We evaluate the attacks along four different criteria: (i) perturbation size and (ii) robustness to hyperparameter selection, measured as the median ‖δ?‖p 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 a fixed hyperparameter configuration works well across different samples); (iii) execution time, measured as the average time spent per query (in milliseconds); and (iv) convergence speed, measured as the average number of queries required to converge to a good-enough solution (within 10% of the best value found at Q = 1000). When computing the median, we follow the evaluation in [4]: the perturbation size is set to 0 if a clean sample is misclassified, while it is set
to∞ 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.

heading: 3.2 Experimental Results
text: 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 δ? as a function of the number of queries Q. For each given Q value, the optimal δ? for each point is selected among the different attack executions (i.e., using different hyperparameters and/or initialization points, as described in Sect. 3.1). In Fig. 2, we report the QD curves for the MNIST and CIFAR10 challenge models (i.e., M2 and C1) 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 `1 case. It 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, a 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 or 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 `1 case. FMN is only slightly worse than DDN and BB in a few cases, including `2-DDN 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 1 show 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 to hyperparameter changes, while other attacks like `0- and `1-BB suffer when using the same hyperparameters for all samples.
Execution time. The average runtime per query for each attack-model pair, measured on a workstation with an NVIDIA GeForce RTX 2080 Ti GPU with 11GB of RAM, can be found in Table 2. The results show that our attack is up to 2-3 times faster, with the exception of DDN in the `2 case. This is however compensated by the fact that FMN finds better solutions. The advantage is that our attack avoids costly inner projections as 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 Algorithm 1), 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 or a fifth as many queries as the state of the art. Exceptions are MNIST and CIFAR10 challenge models (M2 and C1) for `2 and `∞, 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 our 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 maximum-confidence attack, i.e., the Projected Gradient Descent (PGD) attack [17], on two pretrained ImageNet models (i.e., ResNet18 and VGG16), considering `1, `2 and `∞ 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 α0 ∈ {0.1, 1, 2, 8}, without using adversarial initialization. For PGD, we tune the step size α ∈ {0.001, 0.01, 0.1, 1, 2, 8}. We run both attacks for Q = 1, 000 queries on a separate set of 1, 000 samples. The success rates of both
attacks at fixed values are reported in Table 4. The results show that FMN outperforms or equals PGD in all norms.

heading: 4 Related Work
text: Gradient-based attacks on machine learning have a long history [3, 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 a given, bounded perturbation size. While attacks in this category like FGSM [15], PGD [16, 17] and momentum-based extensions of PGD [26, 13] are popular, they only partially evaluate the adversarial
robustness of a model. Minimum-norm 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-Newton optimizer while CW [5] and EAD [8] 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 EAD 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-norm optimization bypasses the tuning of a weighting term, but in the case of BB it 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 `2 and does not perform well on other `p norms.
The proposed FMN attack belongs to the category of minimum-norm attacks, and builds on BB, FAB and DDN to retain their main advantages. First, FMN is not specific to a given norm, and converges in many fewer steps than soft-constraint attacks like CW, as it does not need to optimize the trade-off 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.

heading: 5 Contributions, Limitations, and Future Work
text: 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 to 3 times per query with respect to competing attacks and (iv) converging within less iterations. FMN also works with different `p norms (p = 0, 1, 2,∞) 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 `0 and `1 attacks, it only rivals the performance of other attacks for `2 and `∞ 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, e.g., by averaging
gradients on randomly-perturbed 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 minimumnorm 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, 25]. 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 robustness evaluation. By facilitating more reliable robustness evaluations, we expect that FMN will foster advancements in 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.

heading: Acknowledgements
text: 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 Horizon 2020 research and innovation programme (grant no. 780788); and by BMK, BMDW, and the Province of Upper Austria in the frame of the COMET Programme managed by FFG in the COMET Module S3AI. Wieland Brendel acknowledges support from the German Federal Ministry of Education and Research (BMBF) through the Competence Center for Machine Learning (TUE.AI, FKZ 01IS18039A), 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.

Review summaries:
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.  - 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. - 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).  In addition to the advantages in execution time and query efficiency, the method does not require adversarial starting points as some other methods do.

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. 

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.   The 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.   I agree with the author's assessment that it can be a very useful tool for adversarial robustness evaluation.  [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.