SuperDeepFool: a new fast and accurate minimal adversarial attack
Authors: Alireza Abdolahpourrostam
Mahed Abroshan
Seyed-Mohsen Moosavi-Dezfooli
Venue: NeurIPS 2024 poster (2024)
Keywords: Deep Learning
Adversarial Attacks
Robustness
Interpretable AI
ML Security
Primary area: privacy
TL;DR: We have introduced a family of parameter-free, fast, and parallelizable algorithms for crafting optimal adversarial perturbations.

Abstract: Deep neural networks have been known to be vulnerable to adversarial examples, which are inputs that are modified slightly to fool the network into making incorrect predictions. This has led to a significant amount of research on evaluating the robustness of these networks against such perturbations. One particularly important robustness metric is the robustness to minimal $\ell_{2}$ adversarial perturbations. However, existing methods for evaluating this robustness metric are either computationally expensive or not very accurate. In this paper, we introduce a new family of adversarial attacks that strike a balance between effectiveness and computational efficiency. Our proposed attacks are generalizations of the well-known DeepFool (DF) attack, while they remain simple to understand and implement. We demonstrate that our attacks outperform existing methods in terms of both effectiveness and computational efficiency. Our proposed attacks are also suitable for evaluating the robustness of large models and can be used to perform adversarial training (AT) to achieve state-of-the-art robustness to minimal $\ell_{2}$ adversarial perturbations.

SuperDeepFool:
a new fast and accurate minimal adversarial attack
Alireza Abdollahpoorrostmm
Mahed Abroshan Imperial College, London, UK
EPFL
Lausanne, Switzerland
m. abroshan2$@imperial. ac. uk
alireza. allresa.abbollahporrrottaaaaaa ch
Seyed-Mohsen Moosavi-Dezfooli Apple Zürich, Switzerland smoosavi@apple.. com
Abstract
Deep neural networks have been known to be vulnerable to adversarial examples, which are inputs that are modified slightly fool the network into making incorrect predictions. This has led to a significant amount research on evaluating the robustness of these networks against such perturbations. One particularly important robustness metric the robustness to minimal le adversarial perturbations. However, existing methods for evaluating this robustness metric either compu- tationally expensive or not very accurate. In this paper, we introduce a new family of adversarial attacks that strike balance between effectiveness and computational efficiency. Our proposed attacks are generalizations of the well-known DeepFool (DF) attack, while they remain simple to understand and implement. We demon- strate that our attacks outperform existing methods in terms of both effectiveness and computational efficiency. Our proposed attacks are also suitable for evaluating the robustness of large models and can be used to perform adversarial training (AT) to achieve
robustness to minimal lg adversarial perturbations.
Introduction
Number of Grasteen Compucationn dLog Scaaee
DDN
FAR
Deep learning has achieved breakthrough im- provement in numerous tasks and has developed as a powerful tool in various applications, in-
cluding computer vision [32] and speech pro- cessing [35]. Despite their success, deep neu- ral networks are known be vulnerable ad- versarial examples, carefully perturbed exam- ples perceptually indistinguishable from origi- nal samples [54]. This can lead to a significant disruption of the inference result of deep neu- ral networks. It has important implications for safety and security-criticas applications of ma- chine learning models.
DF
0.50
0.75
1.00
1.25
1.00
Nom ol Parkabation
Figure 1: The average number of gradient com- putations vs the mean norm of perturbations. It shows that our novel fast and accurate method, SDF, outperforms other minimum-nome attacks. SDF finds significantly smaller perturbations com- pared to DF, with only a small increase in computa- tional cost. SDF also outperforms other algorithms in optimality and speed. The numbers are taken from Table 5.
Our goal in this paper is to introduce parameter-free and simple method for accu- rately and reliably evaluating the adversarial robustness of deep networks in fast and geometrically-basee fashion. Most of the current
attack methods rely on general-purpose optimization
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

techniques, such as Projected Gradient Descent (PGD) [33] and Augmented Lagrangian [49], which are oblivious to the geometric properties of models. However, deep neural networks' robustness to adversarial perturbations is closely tied to their geometric landscape [14, 29, 38, 41J. Given this, it would be beneficial to exploit such properties when designing and implementing adversarial attacks. This allows to create more effective and computationally efficient attacks on classifiers. Formally, for given classifier k and input æ, we define adversarial perturbation the minimal perturbation that is sufficient to change the estimated label k(z)):
(a:; min ||rll2 s.t k(x + +r) A k(x)).
DeepFool (DF) [36] was among the earliest attempts to exploit the "excessive linearity" [23] of deep networks to find minimum-norm adversarial perturbations. However, more sophisticated attacks were later developed that could find smaller perturbations at the expense of significantly greater computation time.
In this paper, we exploit the geometric characteristics of minimum-norm adversarial perturbations to design family of fast yet simple algorithms that achieves a better trade-off between computational cost and accuracy in finding lg adversarial perturbations (see Fig. 1). Our proposed algorithm, guided by the characteristics of the optimal solution to Eq. (1), enhances DF to obtain smaller perturbations, while maintaining simplicity and computational efficiency that are only slightly inferior to those of DE. Our main contributions are summarized follows:
We introduce a novel family of fast yet accurate algorithms to find minimal adversarial perturbations. We conduct comprehensive evaluation of our algorithms against state-of-the- art (SOTA) adversarial attack methods across multiple scenarios. Our findings demonstrate that our algorithm identifies minimal yet accurate perturbations with significantly greater efficiency than competing SOTA approaches (4).
Our algorithms are developed in a systematic and well-grounded manner, based on theoreti- cal analysis (3).
We further improve the robustness of state-of-the-art image classifiers to minimum-norm adversarial attacks via adversarial training the examples obtained by our algorithms (4.3).
We significantly improve the time efficiency of the sfate-of-the-art Auto-Attack (AA) [12]
by adding our proposed method to the set of attacks in AA (4.3).
We revisit the importance of minimal adversarial perturbations as a proxy to demystify deep neural network properties (Appendix G, Appendix O).
Related works. It has been observed that deep neural networks are vulnerable adversarial examples [23, 36, 54). To exploit this vulnerability, a range of methods have been developed for generating adversarial perturbations for image classifiers. These attacks occur two settings: white- box. where the attacker has complete knowledge of the model, including its architecture, parameters, defense mechanisms, etc.; and black-box, where the attacker's knowledge is limited, mostly relying on input queries to observe outputs [10, 44]. Further, adversarial attacks can be broadly categorized into two categories: bounded-nen norm attacks (such as FGSM [23] and PGD [33]) and minimum- norm attacks (such as DF and C&W [6]) with the latter aimed at solving Eq. (1). In this work, we specifically focus on white-box minimum fz-norm attacks.
The authors in [54] studied adversarial examples by solving a penalized optimization problem. The optimization approach used in [54] is complex and computationally inefficient; therefore, it cannot scale to large datasets. The method proposed in [23] applied single-step of the input gradient to generate adversarial examples efficiently. DF was the first method seek minimum-now morm adversarial perturbations, employing an iterative approach. It lincarizes the classifier at each step to estimate the minimal adversarial perturbations efficiently. C&W attack [6] transform the optimization problem in [54] into an unconstrained optimization problem. C&W leverages the first-order gradient- based optimizers to minimize a balanced loss between the norm of the perturbation and misclassification confidence. Inspired by the geometric idea of DF, FAB [11] presents an approach to minimize the norm of adversarial perturbations by employing complex projections and approximations while maintaining proximity to the decision boundary. By utilizing gradients to estimate the local geometry of the boundary, this method formulates minimum-norm optimization without the need for tuning a weighting term. DDN [48] uses projections on the ball for given perturbation budget FMN [40]

---

extends the DDN attack to other lp fp-nomms. By formulating (1) with Lagrange's method, ALMA [49] introduced a framework for finding adversarial examples for several distances.
Why does Eg white-box adversarial robustness matter? The reasons for using & norm perturbations are manifold. We acknowledge that l threat model may not seem particularly realistic in practical scenarios (at least for images); however, it can be perceived as a basic threat model amenable to both theoretical and empirical analyses, potentially leading insights in tackling adversarial robustness in more complex settings. The fact that, despite considerable advancements yet to solve adversarial vulnerability, motivates part of community return
in AI/ML, to the basics and work towards finding fundamental solutions to this issue [9, 25, 34j. In particular, thanks to their intuitive geometric interpretation, l2 perturbations provide valuable insights into the geometry of classifiers. They can serve as an effective tool in the "inteppeetatio/eepllaaatoor toolbox shed light on what/how these models learn. Moreover, it has been demonstrated that [19, 38), & robustness has several applications beyond security (for more details on the necessity of robustness to Ep norms, please refer to Appendix O).
2 DeepFool (DF) and Minimal Adversarial Perturbations
In this section, we first discuss the geometric interpretation of the minimum- norm adversarial pertur- bations, i.e., solutions to the optimization problem in Eq. (1). We then examine DF to demonstrate why it may fail to find the optimal minimum-norm perturbation. Then in the next section, we introduce our proposed method that exploits DF to find smaller perturbations.
Let f: _2 + I denote a C-class classifier, where f& represents the classifier's output associated to the kth class. Specifically, for a given datapoint æ E Rd, the estimated label is obtained by ((x) = argmax (x),, where fü (x) is the 1thh component of f(x) that corresponds the 1thh class. Note that the classifier f can be seen as a mapping that partitions the input space IRd into classification regions, each of which has constant estimated label (i.e., k(.) is constant for each such region). The decision boundary Ø is defined the set of points in IRd such that fx()) = (ax max (ar) for some distinct i and j. Additive f--norm adversarial perturbations are inherently related to the
geometry of the decision boundary. More formally, Let æ E Rdd and r (a:) be the minimal adversarial perturbation defined as the minimizer of Eq. (1). Then:
Properties of minimal adversarial perturbation -> (z)) ① is orthogonal to the decision boundary of the classifier B.
2 Its norm, i.e., ||r (æ)]|2 measures the Euclidean distance between a and B, that is + rr lies on B.
We aim investigate whether the perturbations generated by DF satisfy the aforementioned two conditions. Let "DF denote the perturbation found by DF for a datapoint x. We expect x + TDF to lie on the decision boundary. Hence, if is the minimal perturbation, for all 0 < 7 < 1, we expect the perturbation "rr to remain in the same decision region as of x and thus fail to fool the model.
[(x)) 5.0
f(x) >
Fig. 2 illustrates the two conditions discussed in Section 2. In the figure, ni and 722 represent two orthogonal vectors to the decision boundary. The optimal perturbation vector r" aligns parallel nzg. On the other hand, a non-optimal perturbation TDF forms an angle a with ni.
m
m1
In Fig. 3 (left), we consider the fooling rate of y PDF for 0.2 < 7 < 1. For a minimum-norm perturbation, we expect an immediate sharp decline for y close to one. However, in Fig. 3 (top-left) we cannot observe such a decline (a sharp decline happens close to y 0.9, not 1). This is a confirmation that DF typically finds an overly perturbed point. One potential reason for this is the fact that DF stops when a misclassified point is found, and this point might be overly perturbed one within the adversarial region, and not necessarily on the decision boundary.
7DF
TTD
Figure 2: Illustration of the optimal ad- versarial example - r- for binary classifier f: the example lies on the de- cision boundary (set of points where f(x) 0) and the perturbation vector r² is orthogonal to this boundary.
Now, let us consider the other characteristic of the minimal adversarial perturbation. That is, the perturbation should be orthogonal to the decision boundary. We measure the angle between the found
3

---

perturbation "DF and the normal vector orthogonal to the decision boundary (Vf(@ + TDE)). To do so, we first scale "DF such that x + yFDF lies on the decision boundary. It can be simply done via performing line search along PDr. We then compute the cosine of the angle between PDF and the normal to the decision boundary a: + DrDF (this angle denoted by cos(a)). condition for DF to be an optimal perturbation is that it must be parallel to the normal vector of the decision boundary. In Fig. 3 (right). we show the distribution of cosine of this angle. Ideally, we wanted this distribution to be accumulated around one. However, it clearly shows that this is not the case, which is a confirmation that PDF is not necessarily the minimal perturbation.
necessary
Fooling rate scaled SDF & perturbations
Orthognality SDF & perturbations
1.0
0.8
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
cos (a))
Figure 3: (Left) we generated 1000 images with one hundred y between zero and one, and the fooling rate of the DeepFool and SuperDeepFool is reported. This experiment is done on the CIFAR10 10 dataset and ResNet18 model. (Right) histogram of the cosine angle between the normal to the decision boundary and the perturbation vector obtained by DeepFool and SuperDeepFool has been showed.
3 FoperleepFool: Efficient Algorithms to Find Minimal Perturbations
In this section, propose new class of methods that modifies DF to address the afore- mentioned challenges in the previous section. The goal to maintain the desired character- istics of DF, i.e., computational efficiency and the fact that it is parameter-fiee while finding smaller adversarial perturbations. We achieve this by introducing an additional projection step which its goal is steer the direction of perturbation towards the optimal solution of Eq. (1). Let us first briefly recall how DF finds an adversarial per- turbations for classifier f. Given the current point æ; DF updates it according to the following equation:
f(x,) {
0i+1 = Dc
Vf(x))
(2)
Here the gradient taken w.r.t. the input. The intuition is that, in each iteration, DF finds the minimum perturbation for a linear classifier that approximates the model around H;. The below proposition shows that under certain con- ditions, repeating this update step eventually converges to a point on the decision boundary.
Proposition 1 Let the binary classifier Fl; Rd + R
Figure 4: Histogram of the cosine an- gle between the normal to the decision boundary and the perturbation vector ob- tained by C&W and FMN.
be continuously differentiable and its gradient VJ 3- Lipschitz. For given input sample Do, suppose B(xo, E) a ball centered around Dy with radius e, such that there
S
exists x= E B(xo,e) E) that f(x") = O. If VFl22 2 for all x E and E <
then DF
iterations converge to a point on the decision boundary.
Proof: We defer the proof to the Appendix.
Notice while the proposition guarantees the perturbed sample lie on the decision boundary, it does not state anything about the orthogonality of the perturbation to the decision boundary.
To find perturbations that are more aligned with the normal to the decision boundary, introduce an additional projection step that steers the perturbation direction towards the optimal solution of
For the sake of clarity, use F to denote binary classifiers for this proposition.

---

Eq. (1). Formally, the optimal perturbation, r", and the normal to the decision boundary at z r", Va +r"), should be parallel. Equivalently, r" should be a solution of the following maximization
problem:
Vi + +)
max V (2t + +
(3)
which is the cosine of the angle between r and V/( + r). A necessary condition for r" to be solution of Eq. (3) is that the projection of r", i.e. (Ps) the subspace orthogonal to V V r")
should be zero. Then, r" can be seen as a fixed point of the following iterative map:
rit1 = T(r:) Ti V + r.).
Vi(20 + rs)
[V ri)ll
V rx)ll
The scalar multiplier on the right-hand side of Eq. (4) represents the norm of the projection of the vector T; along the gradient direction. The following proposition shows that this iterative process can converge to solution of Eq. (3).
Proposition 2 For differentiable f and a given To. Tú in the iterations Eq. (4) either converge to solution of Eq. (3) or a trivial solution (i.e., T; 0).
Proof: We defer the proof to the Appendix.
Intuitively, by the geometrical properties of decision boundary (3) small portion of the boundary can be enclosed between two affine parallel hyperplane. The following proposition from ([5)) states that the angle between V f(x)) and the optimal direction ff(x + rr" can be bounded neighborhood of the boundary B.
Proposition 3 ([5]) Given a radius r > O and , the set of all samples whose distance from the decision boundary 3 is less than For each angle |0] E (0, }). there exists distance F(o), such that, for all æ E Viy the following inequality holds: cos(O),
(5)
where Ps is the unique projection of x on the B.
Proof: We defer the proof to the Appendix.
3.1 A Family of Adversarial Attacks
Finding minimum-norm adversarial perturbations can be seen as a multi-objective optimization problem, where we want f(x + r) 0 and the perturbation r to be orthogonal to the decision boundary. So far we have seen that DF finds a solution satisfying the former objective and the iterative map Eq. (4) can be used to find a solution for the latter. A natural approach to satisfy both objectives is to alternate be- tween these two iterative steps, namely Eq. (2) and Eq. (4). We propose family of adversarial attack algorithms, coined SuperDeepPFool, by varying how frequently we alternate between these two steps. We denote this family of algorithms with SDF(m, n). where is the number of DF steps Eq. (2) followed by n repetition of the projection step Eq. (4). This process is summarized in Algorithm 1. One inter- esting case is SDF(xc, 1) which, each iteration, continues DF steps till point the decision bound- ary is found and then applies the projection step.
Algorithm SDF (m,n) for binary clas- sifiers
Input:
image no, classifier J, m, and n. Output: perturbation r
Initialize:
æ +-
2 while sign (x)) sign (f (f (xx)) do
repeat m times
(1)) V (()) M
5 end
repeat n times
(x (0) [V)(x)) V (x(x)
x Lo
[V](=)]
8
end
end
10 return 1' = 2 ZV
This particular case has resemblance with the strategy used in [44] to find black-box adversarial perturbations. This algorithm can be interpreted as iteratively approximating the decision boundary with hyperplanc and then analytically calculating the minimal adversarial perturbation for linear
5

---

classifier for which this hyperplane is the decision boundary. It is justified by the observation that the decision boundary of of-the---teearr deep networks has small mean curvature around data samples [21, 22]. A geometric illustration of this procedure is shown in Figure 5.
3.2 SDF Attack
We empirically compare the performance of SDF(m,, n) for different values of m and n in Section 4.1. Interestingly, we observe that we get better attack performance when we apply several DF steps followed by single projection. Since the standard DF typically finds adversarial example in less than four iterations for state-of-the-art image classifiers, one possibility is to continue DF steps till an adversarial example is found and then apply single projection step. We simply call this particular version SDF( 1) of our algorithm SDF, which we will extensively evaluate in Section 4.
SDF can be understood substituting the first inner loop of Algorithm with the standard multi-class DF algorithm. The label of the obtained adversarial example determines the boundary performed. A summary of multi-class SDF presented in Algorithm 2. Compared to the standard DF, this algorithm has additional projection step. We will see later that such simple modification leads to significantly smaller perturbations.
generic algorithm that can also work for the multi-class case by simply
which the projection step will be
Table demonstrates that SDF family outperforms DF in finding more accurate perturbations, particu- larly SDF(,o,1) which significantly outperforms DF at a small cost.
Table Comparison of 22-norm perturba- tions using DF and SDF algorithms CI- FAR10, employing consistent model archi- tectures and hyperparameters as those used in [6. 48] studies.
Like any other gradient-based optimization method tackling a non-convex problem, providing a defini- tive explanation for why one algorithm outperforms others is not straightforward. We have the following speculation on why SDF( 1) consistently outper- forms the other configurations: Note that each projec- tion step reduces the perturbation, while each DF step moves the perturbation nearer to the boundary. So when projection is repeated multiple times (n > 1),
Attack
Median- l2
Grads
DF
0.15
14
SDF (1,1)
0.13
22
SDF (1,3)
0.14
26
SDF (3,1)
0.11
30
SDF(xo,1)
0.10
32
might undo the progress made by DF, potentially slowing down the algorithm's 's convergence. On the other hand, by first reaching boundary point through multiple DF steps and then applying the projection operator just once, we at least ensure that the algorithm has reached intermediate adversarial examples. Each subsequent outer loop is hoped to incrementally move the adversarial example closer to the optimal point (see 5).
Algorithm 2: SDF for multi-class classifiers
f(x) < 0
Input: image no, classifier f. Output: perturbation r
3.
32
32
Initialize: æ æ0
2 while k(x) = k( do
N + (e))Fool(x))
w - V fk (
V Ficmoo (x)
+ æo +
( mg w
f(x) >
end
Figure 5: Illustration of two iterations of the SDF oo..1) algorithm. Here 2o is the original data point and æ. is the minimum-norm ad- versarial example.
return Z0
4 Experimental Results
In this section, we conduct extensive experiments to demonstrate the effectiveness of our method in different setups and for several natural and adversarially trained networks. We first introduce our experimental settings, including datasets, models, and attacks. Next, we compare our method with state-of-the-arr 22-norm adversarial attacks in various settings, demonstrating the superiority of our simple yet fast algorithm for finding accurate adversarial examples. Moreover, we add SDF to the collection of attacks used in AutoAttack, and call the new set of attacks AutoAttack++. This setup

---

meaningfully speeds up the process of finding norm- coun-bunded adversarial perturbations. We also demonstrate that a model udversarially training using the SDF perturbations becomes more robust compared to the models trained using other minimum-norm attacks. Please refer to Appendix B for details of the experimental setup and metries.
4.1 Comparison with DeepFool (DF)
In this part, compare our algorithm in terms of orthogonality and size of the f2-norm perturbations especially with DF. Assume r is the perturbation vector obtained by an adversarial attack. First, we measure the orthogonality of perturbations by measuring the inner product between f + r) and r. As we explained in Section 2, a larger inner product between r and the gradient vector at f(x + indicates that the perturbation vector is closer the optimal perturbation vector r". We compare the orthogonality of different members of the SDF family and DF.
The results are shown in Table 2.
We observe that DF finds perturbations orthogonal to the decision bound- ary for low-complexity models such as LeNet, but fails to perform effectively when evaluated against more complex ones. In contrast, attacks from the SDF family consistently found perturbations with a larger cosine of the angle for all three models.
Table 2: The cosine similarity between the perturbation vector(r) and ff(x + r). We performed this experiment on three models trained on CIFAR1O.
Models
Attack
LeNet
RN18
WRN-28-10
DF
0.89
0.14
0.21
Verifying optimality conditions for SDF. We val- idate the optimality conditions of the perturbations generated by SDF using the procedure outlined in Section 2. Comparing Fig. DF and SDF, it becomes evident that our approach effectively mitigates the two issues previously highlighted for DF.
SDF (1.1)
0.90
0.63
0.64
SDF (1.3)
0.88
0.61
0.62
SDF (3,1)
0.92
0.70
0.72
SDF (oo, 1)
0.92
0.72
0.80
Namely, the alignment of the perturbation with the normal to the decision boundary and the problem of pver-perturbation. We can see that unlike DF, the cosine of the angle for SDF is more concentrated around one, which indicates that the SDF perturbations are more aligned with the normal to the deci- sion boundary. Moreover, Fig. 3 shows sharper decline in the fooling rate (going down quickly to zero) when decreases. This is consistent with our expectation for an accurate minimal perturbation attack.
4.2 Comparison with minimum-norm attacks
Table 3: We evaluate the performance of iteration-based attacks on MNIST using IBP models, noting the iteration count in parentheses. Our analysis focuses on the best-performing versions, highlighting their significant costs when encountered powerful robust models.
We now compare SDF with SOTA minimum &y-norm at- tacks: C&W, FMN, DDN, ALMA, and FAB. For C& W,
we use the same hyperparameters in [48]. We use FMN, FAB, DDN, and ALMA with budgets of 100 and 1000 iter- ations and report the best performance. For fair compari- son, we clip the pixel-values of SDF-generated adversarial images 0, 1]. consistent with the other minimum-nome attacks. We report the average number of gradient compu- tations per sample, as these operations are computationally intensive and provide a consistent metric unaffected by hardware differences. We also provide runtime compar- ison (Appendix Table 19).
Attack
FR
Median-Ca
Grads
DF
93.4
5.31
43
ALMA (1000)
100
1.26
1000
DDN (1000)
99.27
1.46
1000
FAB (1000)
99.98
3.34
10000
FMN (1000)
89.08
1.34
1000
We evaluate the robustness of the IBP model, which is adversarially trained on the MNIST dataset, against SOTA attacks in Table 3. We choose this robust model as allows us to have a more nuanced comparison between different adversarial attacks. SDF and ALMA are the only attacks that achieve a 100% percent fooling rate against this model, whereas C&W is unsuccessful on most of the data samples. The fooling rates of the remaining attacks also degrade when evaluated with 100 iterations. For instance, FMN's fooling rate decreases from 89% 67.8% when the number of iterations reduced from 1000 to 100. This observation shows that, unlike SDF, selecting the necessary number of iterations is critical for the success of fixed-iteration attacks, Even for ALMA which can achieve
C&W
4.63
900
SDF
100
1.37
52
We only compare publicly available models.
7

---

nearly perfect FR. decreasing the number of iterations from 1000 to 100 causes the median norm of perturbations to increase fourfold. In contrast, SDF is able to compute adversarial perturbations using the fewest number of gradient computations while still outperforming the other algorithms, except ALMA, in terms of the perturbation norm. However, it worth noting that ALMA requires twenty times more gradient computations compared to SDF to achieve a marginal improvement in the perturbation norm.
Table 4 compares SDF with SOTA attacks on the CIFARIO dataset. The results show that SOTA at- tacks have a similar norm of perturbations, but an essential point is the speed of attacks. SDF finds more accurate adversarial perturbation very quickly rather than other algorithms.
Table 4: Performance of attacks on the CIFAR- 10 dataset with naturally trained WRN-28-10.
Attacks
FR
Median-&2
Grads
DF
100
0.26
14
ALMA
100
0.10
100
DDN
100
0.13
100
We also evaluated all attacks on an adversarially trained model for the CIFARIO dataset. SDF achieves smaller perturbations with half the gradient calculations than other attacks. SDF finds smaller adversarial perturbations for adversarially trained networks at a significantly lower cost than other at- tacks, requiring only 20% of FAB's 's cost and 50% of DDN's and ALMA's (See Tables 11, 19 in the Appendix).
FAB
100
0.11
100
FMN
97.3
0.11
100
C&W
100
0.12
90000
SDF
100
0.09
25
Table 5 demonstrates the performance of SDF on naturally and adversarially trained models on ImageNet dataset. Unlike models trained on CIFARIO, where the attacks typically result in perturbations with similar norm, the differences between attacks are more nuanced for ImageNet
Table 5: Performance comparison of SDF with other SOTA attacks on ImageNet dataset with natu- ral trained RN-50 and adversarially trained RN-50.
RN-50
RNT30(ATT
Attack
FR
Median-é, é,
Grads
FR
Median-Sa
Grads
DF
96.1
0.31
23
98.8
1.36
34
ATMA
100
0.10
100
100
0.85
100
models.
DDN
98.9
0.17
1,000
99.7
1.10
1,000
In particular, FAB, DDN, and FMN performance degrades when the dataset changes. In contrast, SDF achieves smaller perturbations cantly lower cost than ALMA. This shows that the geometric interpretation of optimal adversarial perturbation, rather than viewing (1) non-convex optimization problem, lead to efficient solution. On the complexity aspect, the proposed approach is substantially faster than the other methods. In contrast, these approaches involve costly minimization of series of objective functions. We empirically observed that SDF converges in less than 5 or 6 iterations to a fooling perturbation; our observations show that SDF consistently achieves SOTA minimum norm perturbations across different datasets, models, and training strategies, while requiring the least number of gradient com- putations. This makes it readily suitable to be used as baseline method to estimate the robustness of very deep neural networks on large datasets.
FMN
C&W
98.3
100
0.21
82, 067
1,000
98:9
98.9
1.17
52, 000
SDF
100
0.09
37
100
0.85
49)
signifi-
4.3 SDF Adversarial Training (AT)
In this section, we evaluate the performance of a model adversarially trained using SDF against minimum-norm attacks and Attok. Our experiments provide valu- able insights into the effectiveness of adversarial training with SDF and sheds light on its potential applications in building more robust models. Adversarial training requires computationally efficient attacks, making costly options such as C unsuitable. Therefore, attack that is parallelizable (both on batch size and gradient computation) is desired for successful adversarial train- ing. SDF possesses these crucial properties, making a promising candidate for building more robust models.
Table 6: The comparison between & ro-
bustness of our adversarial trained model and [48] model.
SDF (Ours)
DDN
Attack
Mean
Median
Mean
Median
DDN
1.09
1.02
0.86
0.73
FAB
1.12
1.03
0.92
0.75
FMN
1.48
1.43
1.47
1.43
ALMA
1.17
0.84
0.71
SDF
1.06
1.01
0.81
0.73
We adversarially train a WRN-28-10 on CIFAR10. Similar to the procedure followed in [48], we restrict &g normos of perturbation to 2.6 and set the maximum number of iterations for SDF to 6.
8

---

We train the model on clean examples for the first 200 epochs, and we then fine-tune it with SDF generated adversarial examples for 60 more epochs. Since a model trained using DDN- -Dnggreertted samples [48] has demonstrated greater robustness compared to model trained using PGD [33], we compare our model with that one (for more details about AT please refer to Appendix O). Our model reaches test accuracy of 90.8% while the model by [48] obtains 89.0%. SDF advensarially trained model does not overfit to SDF attack because, as Table 6 shows, SDF obtains the smallest perturbation. It is evident that SDF adversarially trained model can significantly improve the robustness of model against minimum-nore attacks up to 30%. In terms of comparison these two adversarially trained models with AA, our model outperformed the [48] by improving about 8.4% against &o AAA, for E = 8/255, and 0.6% against AA, for = 0.5.
Furthermore, compared to a network trained on DDN samples, our adversarially trained model has smaller input curvature (Table 7). The second column shows the average spectral-norm of the Hessian w.r.t. input, [x)]l( and the third column shows the average of the same quantity normalized by the norm of the input gradient, Cj (x) | f(x))((2x / f(x) ||.. The standard
Table 7: Average input curvature of AT models. According to the measures pro- posed in [53].
Model
[ f(x)ll
[xCy(x)
Standard
600 06 (29.76)
73.90 (6.62)
DDN AT SDF AT (Ours)
2.86 (1.22)
4.32 (2.91)
0.73 (0.08)
1.66 (0.86)
deviation is denoted by numbers enclosed in brackets.
This observation corroborates the idea that more robust network will exhibit a smaller input curvature [1, 37, 39, 42, 53].
AutoAttack++
Although it is not the primary focus of this paper, in this section we notably enhance the time efficiency of the AA [12] by incorporating SDF method into the set of attacks in AA.
Table 8: Analysis of robust accuracy for various de- fense strategies against AA++ and AA with e = 0.5 for six adversarially trained models on CIFAR1O. All models are taken from the RobustBench li- brary [13].
We introduce new variant of AA by intro- ducing AutoAttack*+ (AA++). AA is a reli- able and powerful ensemble attack that con- tains three types of white-box and a strong black-box attacks. AA evaluates the robustness of a trained model to adversarial perturbations whose -norm is bounded by c. By sub- stituting SDF with the attacks in the AA, we significantly increase the performance of AA in terms of computational time. Since SDF is an 2--norm attack, we use the by-norm version of AA as well. We restrict maximum iterations of SDF 10. If the norm of perturbations exceeds E, we renormalize the perturbation to ensure its norm stays S E. In this context, we have modified the AA algorithm by replacing APGD [12] with SDF due to the former's cost and computation bottleneck in the context of AA (See Appendix F.1 for more details). Our decision to replace APGD with SDF was primarily motivated by the former being a computational bottleneck in AA. As it shown in Table 8, AA and AA+ achieve similar fooling rates, with AÄ+ being notably faster. We compared the sets of points that were fooled or not fooled by SDF/APGI T across 1000 samples (E 0.5). The results indicate that both algorithms fool approximately the same set of points, differing only in handful of samples for this epsilon value. Therefore, the primary benefit of using SDF is the reduction in computation time. We compare the fooling rate and computational time of AA++ and AA on the models from the RobustBench. In Table 8, we observe that AA+ is up to three times faster than AA. In alternative scenario. added the SDF to the beginning of the AA set, resulting in version that is up to two times faster than the original AA, despite now containing five attacks (See Appendix F). This outcome highlights the efficacy of SDF in finding adversarial examples. These experiments suggest that leveraging efficient minimum-norm and non-fixed iteration attacks, such as SDF, can enable faster and more reliable evaluation of the robustness of deep models.
Models
AA
AA++
Clcan ace.
Grads
Robust acc.
Grads
RI [45]
95.7%
82.3%
1259.2
82.1%
599.5
[51]
90.3%
76.1%
1469.1
76.1%
R3 [24)
80.4%
69.4%
1240-4
22.2%
431.5
R4 [46]
88.6%
67. 8%
933.T
68.4%
715.3
[46]
80.015
848.3
62.55 53
613.7
R6 [15]
88.0295
6%
721-4
63.0 63.4%
511.1
Natura
94.7%
0.00%%
208-6
0.00
5 Conclusion and Future Works
In this work, we have introduced a family of paremeter-free, fast, and parallelizable algorithms for crafting optimal adversarial perturbations. Our proposed algorithm, SDF, consistently finds smaller

---

norm perturbations on various networks and datasets with only a small additional computation cost compared DF (which is still significantly faster than all SOTA attacks). Furthermore, have shown that adversarial training using the examples generated by SDF builds more robust models. While our primary focus in this work has been on minimal & attacks, there exists potential for extending SDF families to other threat models, including general l fp-norms and targeted attacks. In the Appendix, we have demonstrated straightforward modifications that highlight the applicability of SDF to both targeted and 2cc attacks. However, more comprehensive evaluation remains direction for future work. Moreover, further limitations of our proposed method are elaborated upon in Appendix N. In the end, by revisiting the necessity of ép ---norm robustness and characterizing toy example on robustness- free phenomena, we underscore the pivotal role of minimum-non norm attacks in ensuring secure Al systems.
6 Acknowledgments
We want to thank Kosar Behnia and Mohammad Azizmalayeri for their helpful feedback. We are very grateful Fabio Brau and Jérôme Rony for providing code and models and answering questions on their papers.
10

---

References
[1] Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adver- sarial training, 2020. 9
[2] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In International conference on machine learning. pages 274 283. PMLR, 2018. 17
[3] Maximilian Augustin, Alexander Meinke, and Matthias Hein. Adversarial robustness on in-and out-distribution improves explainability. In European Conference on Computer Vision, pages 228 228-245. Springer, 2020. 16
[4] Yutong Bai, Jieru Mei, Alan Yuille, and Cihang Xie, Are transformers more robust than cnns?,
2021. 21
[5] Fabio Brau, Giulio Rossolini, Alessandro Biondi, and Giorgio Buttazzo. On the minimal adversarial perturbation for deep neural networks with provable estimation error arXiv preprint arXiv:2201.01235. 2022. 5, 15
[6] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium security and privacy (sp). pages 39-57. Icee, 2017. 2, 6, 23
[7] Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprini arXiv: 1902.0605, 2019. 23
[8] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C. Duchi. Unlabeled data improves adversarial robustness, 2022. 18
[9] Patrick Chao, Edoardo Debenedetti, Alexander Robey, Maksym Andriushchenko, Francesco Croce, Vikash Sehwag, Edgar Dobriban, Nicolas Flammarion, George J. Pappas, Florian Tramer, Hamed Hassani, and Eric Wong. Jailbreakbench: An open robustness benchmark for jailbreaking large language models, 2024. 3
[10] Jianbo Chen, Michael Jordan, and Martin Wainwright. Hopskipjumpattack: A query-efficient decision-based attack. In 2020 ieee symposium on security and privacy (sp), pages 1277-1294.
IEEE, 2020, 2
[11] Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack. In International Conference on Machine Learning, pages 2196-2205. PMLR, 2020. 2
[12] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference machine learning, pages 9206-2216 PMLR, 2020. 2,
[13] Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flammarion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: a standardized adversarial robustness benchmark. arXiv preprint arXiv:2010.09670, 2020. 16
[14] Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non- convex optimization. Advances in neural information processing systems, 27, 2014. 2
[15] Gavin Weiguang Ding, Yash Sharma, Kry Yik Chau Lui, and Ruitong Huang. Mma train- ing: Direct input space margin maximization through adversarial training. arXiv preprint 1812 026377, 2018.
[16] Junhao Dong Seyed-Mohsee -oosavi-Dezfooli, Jianhuang Lai, and Xiaohua Xie. The enemy of my enemy is my friend: Exploring inverse adversaries for improving adversarial training, 2022. 23

---

[17] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021. 16, 21
[18] Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robust- 16
ness (python library). 2019. URL
[19] Logan Engstrom, Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Brandon Tran, and Aleksander Madry. Adversarial robustness prior for learned representations, 2019. 3
[20] Christian Etmann, Sebastian Lunz, Peter Maass, and Carola-Bibiane Schönlieb. On the connec- tion between adversarial robustness and saliency map interpretability, 2019. 23
[21] Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. The robustness of deep networks: A geometrical perspective. IEEE Signal Processing Magazine, (4(6):50-62, 2017.
[22] Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli Pascal Frossard, and Stefano Soatto. Em- pirical study of the topology and geometry of deep networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3762-3770, 2018. 6
[23] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6572, 2014. 2, 18
[24] Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norn-bounded adversarial examples. arXiv preprint arXiv:2010.035993 2020. 9
[25] Jonathan Hayase, Ema Borevkovic, Nicholas Carlini, Florian Tramèr, and Milad Nasr. Query- based adversarial prompt generation, 2024. 3
[26] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016. 18
[27] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference computer vision, pages 630-645. Springer, 2016. 16
[28] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andrectto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 04861, 2017. 18
[29] Can Kanbak, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. Geometric robustness of deep networks: analysis and improvement, 2017. 2, 24
[30] Alex Krizhevsky, Ily Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6): 2017. 18
[31] Yann LeCun, Patrick Haffner, Léon Bottou, and Yoshua Bengio. Object recognition with gradient-based learning. In Shape, contour and grouping in computer vision, pages 319-345. Springer, 1999. 16
[32] Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for se- mantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431-3440, 2015.
[33] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint (xXiv:7706006033 2017. 2, 9, 18, 22, 23
[34] Natalie Maus, Patrick Chao, Eric Wong, and Jacob Gardner. Adversarial prompting for black box foundation models. arXiv preprint arXiv:2302.042.77 1(2), 2023.
12

---

[35] Tomáš Mikolov, Anoop Deoras, Daniel Povey, Lukáš Burget, and Jan Cernocký. Strategies for training large scale neural network language models. In 2011 IEEE Workshop on Automatic Speech Recognition & Understanding, pages 196-201. IEEE, 2011.
[36] Seyed-Mohsen Mlosavi-Dezfoolie Alhussein Fawzi, and Pascal Frossard. Deepfool: A simple and accurate method to fool deep neural networks. In Proceedingy of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), June 2016. 2, 22
[37] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9078-9086, 2019. 9, 19
[38] Guillermo Ortiz-Jimenez Apostolos Modas, Seyed-Mohsen Moosavi-Dezfoolii and Pascal Frossard. Optimism in the face of adversity: Understanding and improving deep learning through adversarial robustness, 2021. 2,3
[39] Guillermo Ortiz-limenez, Pau de Jorge, Amartya Sanyal, Adel Bibi, Puneet K. Dokania, Pascal Frossard, Grégory Rogez, and Philip Torr. Catastrophic overfitting can be induced with discriminative non-robust features. Transactions Muchine Learning Research, 2023, ISSN 2835-8856.
URL https: //opp//e////eeeeieeete
Expert Certification.
9
[40] Maura Pintor, Fabio Roli, Wieland Brendel, and Battista Biggio. Fast minimum- adversarial attacks through adaptive norm constraints. Advances in Neural Information Processing Systems, 00220052-20066 2021. 2, 22
[41] Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29, 2016.
[42] Chongli Qin, James Martens, Sven Gowal, Dilip Krishnan, Krishnamurthy Dvijotham, Alhus- sein Fawzi, Soham De, Robert Stanforth, and Pushmeet Kohli. Adversarial robustness through local linearization. Advances in Neural Information Processing Systems, 32, 2019. 9
[43] Rahul Rade and Seyed- Seyed-Mohsen Mohsen Moosavi-Dezfer Dezfooli. Helper- based adversarial training: Reducing excessive margin to achieve a better accuracy vs. robustness trade-off. In JCML (02L Workshop on Adversarial Machine Learning, 2021. 16, 17, 18, 23
[44] Ali Rahmati, Seyed-Mohsen Moosavi- -iosavi-Dezzoooli, Pascal Frossard, and Huaiyu Dai. Geoda: a geometric framework for blxck-box ad adversarial attacks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8446 8455, 2020. 5
[45] Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Timothy Mann. Fixing data augmentation to improve adversarial robustness. arXiv preprint arXiv:2103.01944 2021. 21
[46] Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pages 8093 -104. PMLR, 2020. 9
[47] Elias Abad Rocamora, Fanghui Liu, Grigorios G. Chrysos, Pablo M. Olmos, and Volkan Cevher. Efficient local linearity regularization to overcome catastrophic overfitting, 2024. 9
[48] Jerome Rony, Luiz G. Hafemann, Luiz S. Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. Decoupling direction and norm for efficient gradient-based 12 adversarial attacks and defenses. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019. 2, 6, 7, 8, 9, 16, 17, 22,
[49] Jérôme Rony, Eric Granger, Marco Pedersoli, and Ismail Ben Ayed. Augmented lagrangian adversarial attacks. In Proceedings of the IEEF/CVF International Conference on Computer
Vision, pages 7738-7747, 2021. 2,
[50] Kevin Roth, Yannic Kilcher, and Thomas Hofmann. Adversarial training is a form of data- dependent operator norm regularization, 2020. 23
13

---

[51] Vikash Sehwag, Saeed Mahloujifar, Tinashe Handina, Sihui Dai, Chong Xiang, Mung Chi- ang, and Prateek Mittal. Improving adversarial robustness using proxy distributions. CoRR. abs/2104.09425, 2021. 9
[52] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint prrxiv:1409. 1556, 2014.
[53] Suraj Srinivas, Kyle Matoba, Himabindu Lakkaraju, and François Fleuret. Efficient training of Low-curvature neural networks. In Advances in Neural Information Processing Systems. 9, 19
[54] Christian Szegedy, Wojeiech Zaremba. Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfel- low, and Rob Fergus. Intriguing properties of neural networks, arXiv preprint
2013. 1,2
[55] Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. adaptive attacks to adversarial example defenses. In Advances in Neural Information Processing Systems, 2020.
23
[56] Jonathan Uesato, Brendan O'donoghue, Pushmeet Kohli, and Aaron Oord. Adversarial risk and the dangers of evaluating against weak attacks. In International Conference Machine Learning, pages 5025-5034. PMLR, 2018. 18
[57] Dongxian Wu, Shu tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust generalization, 2020. 23
[58] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 1051v:1605.07146 2016. 16
[59] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing. Laurent El Ghaoui, and Michael I.
Jordan. Theoretically principled trade-off between robustness and accuracy, 2019, 23
[60] Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. arXiv preprint arXix:/906.068 16, 2019. 16
14

---

A Appendix
A.1 Proofs
Proof of Proposition 1.
Since VF(x)) is Lipschitz-continnuuss for æ, y E B( 2), we have:
[F() - + (F) (x y) - || 1---~v1 y1
(6)
DeepFool updates the new 2n in each according to the following equation:
VF(xn-1) F(xn-11
Da 1n + Va 21)12
(7)
Hence we substitute æ In and = In-1 in (6), we get:
[F(x,)) In In xn-1 11?
(8)
Now, let 8n = ||00 - In-ill. Using (8) and DeepFool's step, we get:
F((rn)
- 33 F(xr,))
8n+1
|VF(n)]]
25 1VIIFF(ann ( )11
(9)
F(xn)
g²
81+1
[[V[((x)] 8n
(10)
C²
Be
Using the assumptions of the theorem, we have
1, and hence 8, converges to when n oo.
X²
We conclude that {æn) is Cauchy sequence. Denote by Doo the limit point of {an.. Using the continuity of F and (8), we obtain
lim F(x,)l [F(xx)) [F(x") -=
(11)
Which concludes the proof of the theorem.
Proof of Proposition 2. Let us denote the acute angle between Vf(w, + r;) and r, by 0, (0 0, I T/2). Then from (4) we have |r41l |r, cos 0, Therefore, we get
rrt1l II cos 0 |rol-
(12)
Now there are cases, either 0,
not. Let us first consider the case where zero is the
limit of 0, Then there exists some eg >> 0 such that for any integer N there exists some > N for which we have 02, ép. Now for eo.
have series of integers ni where for all of them
have on, > Since we have 0 < cos 0| < 1, we have the following inequality:
cos 0,| S
cos 0ngl
II 1=0
cos col
(13)
The RHS of the above inequality goes to zero which proves that r; + This leaves us with the other case where 0: + 0. This means that cos 0 - 1 which is the maximum of Eq. (3), this completes the proof.
Proof of proposition 3 ([SI) We use assumptions discussed in proposition (the continuity of V D.. We derive that there exists a distance such that [[V[(x)] * in v (the smallest closed set containing ,,,, and so we derive that f is uniformly continuous in v, Hence, for each e, there V and ||æ el res the following inequality exists distance Ts such that, for each holds:
||ll|
Vx(x)
V f
<s,
(14)
[
15

---

Table Comparison of the effectiveness of line search on the CIFARIO data for SDF and DE. We regularly trained model (WRN-28-10) and three adversarially trained models (shown with RI [48], R2 [3] and R3 [43]). v and x indicate the presence and absence line search respectively.
DF
SDF
Model
X
X
S
0.16
0.19
0.09
0.10
R1
0.87
1.02
0.73
0.76
1.40
1.73
0.91
0.93
R3
1.13
1.36
1.04
1.09
Table 10: Comparison of the effectiveness of line search on the CIFAR-10 data for other attacks. Line search effects are a little for DDN and ALMA. For FMN and FAB because they use line search at the end of their algorithms (they remind this algorithm binary search and final search, respectively). line search does not become effective.
DDN
ALMA
FMN
FAB
MODEL
X
V
X
X
WRN-28-10
0.12
0.13
0.10
0.10
0.11
0.11
0.11
0.11
RI [48]
0.73
0.73
0.71
0.71
1.10
1.10
0.75
0.75
R2 [3]
0.96
0.97
0.93
0.94
0.95
0.95
1.03
1.03
R3 [43]
1.04
1.04
1.06
1.06
1.08
1.08
1.07
1.07
from triangle inequality for norms, we can derive:
v [ff
(15)
In conclusion, by taking = (a)( and by choosing & = /2 coss( we achieve upper bound for cos(f) where F(Ø) min( rz). Where Tnax is maximum distance such that for each in the V Yea. there exists Ps(x)) E 20 solves the minimum-norm optimization problem.
B Setup
We test our algorithms architectures trained on MNIST, CIFARIO, and ImageNet datasets. For MNIST, we use a robust model called IBP from [60] and naturally trained model called SmalICNN. For CIFARIO, regularly trained Wide ResNet 28- 10 (WRN-28-10 from [58] and LeNet [31]. These models are obtainable via the RobustBench library [13]. On ImageNet, test the attacks
three models: adversarially trained PreAAtRReNNtt-18 [27] from [43],
ResNet-50 (RN-
50) models: one regularly trained and one l adversarially trained, obtainable through the robustness library [18]. We additionally evaluate the robustness of Vision Transformers (ViT-B-16 [17]) and reevaluate the comparative analysis between ViTs and CNNs.
C On the benefits of line search
As we show in Figure 3, DF typically finds an overly perturbed point. SDF's gradients depend on DE, so overly perturbing DF is problematic. Line search mechanism that we add to the end of our algorithms to tackle this problem. For a fair comparison between adversarial attacks, we add this algorithm to the end of other algorithms to investigate the effectiveness line search. As shown in Table 9, we observe that line search can increase the performance of the DF significantly. However, this effectiveness for SDF little. We now measure the effectiveness line search for other attacks. As observed from Table 10, line search effectiveness for DDN and ALMA is small.
16

---

D Comparison on CIFARIO with the AT PRN-18
In this section, we compare SDF with other minimum norm attacks against an adversarially trained network [43]. In Table 11, SDF achieves smaller perturbation compared to other attacks, whereas costs only half much other attacks.
Table 11:
Comparison of SDF with other state-of-ther ofrt attacks for median & on CIFAR-10 dataset for adversarially trained network (PRN-18 [43]).
ATTACK
FR
MEDIAN- 82
GRADS
ALMA
100
0.68
100
DDN
100
0.73
100
FAB
100
0.77
210
FMN
99.7
0.81
100
SDF
100
0.65
46
E Performance comparison of adversarially trained models versus
Auto-Attack (AA)
Evaluating the adversarially trained models with attacks used in the training process is not standard evaluation in the robustness literature. For this reason, we evaluate robust models with AA. We perform this experiment with two modes; first, we measure the robustness of models with foo norm, and in a second mode, we evaluate them in terms of & norm. Tables 12 and 13 show that adversarial training with SDF samples is more robust against reliable AA than the model trained DDN samples [48].
Table 12: Robustness results of adversarially trained models on CIFAR-10 with AAA We perform this experiment on 1000 samples for each E.
MODEL
NATURAL
10
255
DDN
89.1
45
29.6
17.6
SDF (OURS)
90.8
47.5
38.1
25.4
Table 13: Robustness results of adversarially trained models on CIFAR-10 with 22-AA. We perform this experiment on 1000 samples for each E.
MODEL.
NATURAL
E
0.1
0.5
0.6
DDN
89.1
78.1
67.5
61.7
SDF (OuRS)
90.8
83.1
79.7
68.1
63.9
F Another variants of AA++
As mentioned, in alternative scenario, added the SDF to the beginning of the AA resulting in a version that is up to two times faster than the original AA. this scenario, we do not exchange the SDF with APGD. We add SDF the AA configuration. So in this configuration, AA has five attacks (SDF, APGD, APGD FAB, Square). By this design, we guarantee the performance of AA. An interesting phenomenon observed from these tables is that when the budget increases, the speed of the AA+ increases. We should note that we restrict the number of iterations for SDF to 10.
F.1 Why do we replace SDF with APGD
It is unaffected by gradient obfuscation [2]. The primary limitation of AA, however, its computational intensity. To thoroughly evaluate model, it must be subjected to four distinct attacks sequentially.
well established that AutoAttack (AA) is robust method for evaluating model robustness,
17

---

3.0
2.00
175-
160
410 415
(a) RI
(b)
Figure 6: In this figure, we show the time ratio of AA to AA++. For regularly trained model (WRN- 28-10) and adversarially trained model [43] (RI). We perform this experiment on 1000 samples from CIFARIO data.
Our empirical analysis identified the APGD attack as the main computational bottleneck in AA. For example, when attacking a standard WRN-28- 10 model trained on CIFAR-1O, APGD requires approximately 4310 backward passes achieve 100% fooling rate. Similarly, for adversarially trained WRN-28-10 [8] model on CIFAR-10, 10, APGD necessitates around 5660 backward passes to attain 100% fooling rate. To address this issue, rather than simply replacing SDF with another minimum-norn attack such as FAB in AA, we mitigate the bottleneck by employing a faster minimum- norm attack like SDF.
G Why do we need stronger minimum-norm attacks?
Bounded-none -orm attacks like FGSM [23], PGD [33], and momentum variants of PGD [56], by opti- mizing the difference between the logits of the true class and the best non-true class, try find an adversarial region with maximum confidence within a given, fixed perturbation size. Bounded-norn attacks only evaluate the robustness of deep neural networks; this means that they report a single scalar value as robust accuracy for a fixed budget. The superiority of minimum-norm attacks is to report distribution of perturbation norms, and they do not report a percentage of fooling rates (robust accuracy) by a single scalar value. This critical property of minimum-now norm attacks helps to accelerate to take an in-depth intuition about the geometrical behavior of deep neural networks.
We aim to address a phenomenon we observe by using the superiority of minimum- norm attacks. We observed that minor change within the design of deep neural networks affects the performance of adversarial attacks. To show the superiority of minimum-nome attacks, we show how minimum-nom attacks verify these minor changes rather than bounded-norm attacks.
Modeling with max-pooling was a fundamental aspect of convolutional neural networks when they were first introduced as the best image classifiers. Some Mfate-of-the-rr classifiers such [26, 30, 52] use this layer in network configuration. We use the pooling layers to show that using the max-pooling and Lp-pooling layer in the network design leads to finding perturbation with bigger fo-nm..
Assume that we have a classifier f. We train f in two modes until the training loss converges. In the first mode, f is trained in the presence of the pooling layer in its configuration, and in the second mode, does not have pooling layer. When we measure the robustness of these two networks with regular budgets used in bounded-norm attacks like PGD (e 8/255), we observe that the robust accuracy is equal to 0%. This is precisely where bounded-nome norm attacks such as PGD mislead robustness literature in its assumptions regarding deep neural network properties. However, a solution to solve the problem of bounded-nun norm attack scan be proposed: "Analyzing the quantity of changes in robust accuracy across different epsilons reveal these minor changes. "Is this case, the solution is costly. This is precisely where the distributive view perturbations from worst-case to best-case of minimum-nonm norm attacks detects this minor change.
To show these changes, we trained ResNet- 18 and Mobile-Net [28] in two settings. In the first setting, we trained them in the presence of pooling layer until the training loss converged, and in the second setting, we trained them in the absence of pooling layer until the training loss converged. We should note that we remove all pooling-layers in these two settings. For fair comparison, we train models until they achieve zero training loss using multi-step learning rate. We use max- max-pooling and Lp- Lp-pooling, for p 2, for this minor changes.
18

---

Table 14: This table shows the my-median for the minimum-norm attacks. For all networks, learning rate = 0.01 and weight decay 0.01. For training with Lp-pooling, we set p for all settings.
RN18
MOBILENET
ATTACK
NO POOL
MAX-POOL
LP-POOL
NO POOL
MAX-POOL
LP-POOL
DF
0.40
0.90
0.91
0.51
0.95
0.93
DDN
0.16
0.25
0.26
0.22
0.27
0.26
FMN
0.18
0.27
0.30
0.21
0.30
0.29
C&WW
0.18
0.25
0.27
0.22
0.26
0.24
ALMA 0.19
0.23
0.23
0.20
0.25
0.22
SDF
0.16
0.21
0.22
0.20
0.23
0.21
Table 15: This table shows the robust accuracy for all networks against to the AA and PGD. For training with Lp- -p-pooling, we set p for all settings.
RNI8
MOBILENET
ATTACK
NO POOL
MAX-POOL
LP-POOL
NO POOL
MAX-POOL
LP-POOT.
AA PGD
1.1%
17.2% 28%
16.3%
8.7%
21.3%
20.2%
9.3%
26.2%
16.8%
31.4%
28.7%
Table 14 shows that using a pooling layer in network configuration can increase robustness. DF has an entirely different behavior according to the presence or absence of the pooling layer; max-pooling affects up to 50% of performance. This effect is up to 9% for DDN and FMN. ALMA and SDF show 4% impact in their performance, which shows their consistency compared to other attacks.
As shown in Table 15, we observe that models with pooling-layers have more robust accuracy when facing ad advessarial attacks such as AA and PGD. It should be noted that using regular epsilon for AA and PGD will not demonstrate these modifications. For this reason, we choose an epsilon for AA and PGD lower (s 2/255) than the regular format (s 8/255).
Table 14 and 15 demonstrate that pooling- layerss affect adversarial robustness of deep networks. Powerful attacks such as SDF and ALMA show high consistency in these setups, highlighting the need for powerful attacks.
G.1 Max-pooling's effect on the decision boundary's curvature
Here, we take a step further and investigate why max-pon max-pooling impacts the robustness models. In order to perform this analysis, The curvature of a point is a mathematical quantity that indicates the degree of non-linearity. has been observed that robust models are characterized by their small curvature [37], implying smaller Hessian norms. In order to investigate robustness independent of non-linearity [53] propose normalized curvature, which normalizes the Hessian norm at given input ær by its corresponding gradient norm. They defined normalized curvature for a neural network classifier / as (a = [[V f(=))le/(() [x))(( + E). Where [[=]()) and || V f())ll are the fo-m the gradient and the spectral norm of the Hessian, respectively, where (x(x)) E Rdd. V f(x) E Raxd and small constant to ensure the proper behavior of the measure. In Table 16, we measure these quantities for two trained models, one with max-pooling the model incorporating max-pooling exhibits a smaller curvature. This finding corroborates the observation that models with greater robustness tend to have a smaller curvature value.
analyze gradient norms, Hessian norms, and the model's curvature.
one without. clearly shows that
Table 16: Model geometry of different ResNet-18 models. W (with pooling) and W/O (without pooling).
MODEL
E. VallVi(=))la
Eg +=I[Vf((=))))
Cy))
W
4.75 = 1.54
120.70 + 48.74
14.94 = 0.52
W/O
7.04 42.44
269.74 10.23
22.81 2.68
19

---

Table 17: Model geometry for regular and adversarially trained models.
MODEL
Eg
| (())ll2
[<r]l
(gC)(()
STANDARD
9.54 1.02
600.06
29.76
73.99 1: 6.62
DDN AT
0.91
4 0.34
2.86 4: 1.22
4.32 2.91
SDF AT
0.38 0.60
0.73 0.08
1.66 0.86
H Model geometry for AT models
In this section we provide curvature analysis of our adversarially trained networks, SDF AT, and DDN AT model. Table 17 shows that our AT model decreases the curvature of network more than DDN AT model.
I CNN architecture used in Table
Layer Type
CIFAR-10
Convolution + ReLU
3 3 64
Convolution + ReLU
x 3 64
max-pooling
2 x 2
Convolution + ReLU
3 x 128
Convolution + ReLU
3 x 128
max-pooling
2 x 2
Fully Connected ReIJU
256
Fully Connected ReLU
256
Fully Connected Softmax
10
The architecture used to compare SDF variants and DF (Table summarized in above Table.
20

---

J ViT-B-16 for CIFAR-10
Given our available computational resources, we conduct experiments on a ViT-B-16 [17] trained on
CIFAR-10, 10, achieving 98.55% accuracy. The results summarized in the following table:
Attack
FR (%)
Median-22
Grads
DF
98.2
0.29
19
ALMA
100
0.12
100
DDN
100
0.14
100
FAB
100
0.14
100
FMN
99.1
0.15
100
C&W
100
0.15
91,208
SDF
100
0.10
32
As seen, this transformer model does not exhibit significantly greater robustness compared to CNNs, with only negligible difference of 0.01 compared to a WRN-28 10 trained on CIFAR-10 10. These results support the notion that there might not be substantial disparity between the adversarial robustness of ViTs and CNNs. This aligns with the findings of [4]. They argue that earlier claims of transformers being more robust than CNNs stems from an unfair comparison and evaluation methods. We believe that thorough evaluations using minimum norm attacks could be helpful in resolving this debate.
K Natural (Regular) Trained MNIST Model
In Table 18 we show the results of evaluating adversarial attacks on naturally trained SmalICNN MNIST dataset. Our algorithm demonstrates higher rate of convergence compared to other algorithms, as the perturbations for all algorithms are generally similar.
Table We compare the performance of all algorithms on the natural SmalICNN model that was trained on the MNIST dataset.
Attacks
Median-Cz
Grads
ALMA
100
1.34
1000
DDN
100
1.36
1000
FAB
100
1.36
10000
FMN
97.10
1.37
1000
C&W
99.80
1.35
90000
SDF
100
1.34
67
L Runtime Comparison
We report the number of gradient computations main proxy for computional cost comparison. In Table 19, we have compared the runtime different attacks for fixed hardware. SDF is significantly faster.
Table 19:
Runtime comparison for adversarial attacks on WRN-28- architecture trained on CI- FAR10, for both naturally trained model and adversarially trained models.
Natural
RI [45]
Attacks
Time (S)
Median-
Time (S)
Median
ALMA
1.71
0.10
13.10
1.22
DDN
1.54
0.13
12.44
1.53
FAB
2.33
0.11
16.21
1.66
FMN
1.42
0.11
10.25
1.83
C&W
734.8
0.12
5402.
1.68
SDF
0.48
0.09
2.93
1.19
21

---

M
Query-Distortion Curves
Query-Distoriie Curve
1.4
SDF
1.3
1.2
1.1
1.0
20
40
60
80
100
120
Numbers of Forward Passes
Figure 7: As demonstrated in [40], query-distortion curves are utilised as a metric for evaluating computational complexity of white-box attacks. In this particular context, the term "query" refers the quantity of forward passes available to find adversarial perturbations.
refers to
Unlike FMN and ALMA, SDF (and DF) does not allow control over the number of forward and back- ward computations. They typically stop the process prematurely could prevent them from finding an adversarial example. Hence, we instead opted to plot the median norm of achievable perturbations for given maximum number of queries (Figure 7) Although this is not directly comparable to the query-distortion curves in [40], it provides more comprehensive view of the query distribution than the median alone.
successful adversarial example is found. Terminating
N Limitations
In this section, we discuss some limitations and potential extensions of SDF.
Extension to other é, -orms and targeted attacks. The proposed attack is primarily designed for l2-norm adversarial perturbations. Moreover, our method, similar to DeepFool (DF), is targeted Though there are potential approaches for adapting SDF to targeted and Ep attacks, these aspects remain largely unexplored in work.
Nevertheless, here demonstrate how one could possibly extend SDF other p-norms. A simple way is to replace the & projection (Line 5 of Algorithm 2) with projection operator minimizing ép norm similar to the derivations used in [36]. particular, for p = oo, the following projection would replace the line 5 of Algorithm 2:
2 T F0
sign w)
(16)
[w
In Table 20, we compare the performance of this modified version of SDE, named SDF,,, with FMN, FAB, and DF, two pretrained networks MI [33] and M2 [48] on CIFAR-10 dataset. Our findings indicate that SDF, also exhibits superior performance compared to other algorithms discovering smaller perturbations.
Table 20: Performance of SDF, on two robust networks trained on CIFAR-10 dataset.
M1
M2
ATTACKS
MEDIAN foo
FR
GRADS
MEDIAN &oo
GRADS
DF
0.031
96.7
24
0.043
97.4
31
FAB
0.025
99.1
100
0.038
99.6
100
FMN
0.024
100
100
0.035
100
100
SDF
0.019
100
33
0.027
100
46
22

---

Table 21: Performance of targeted SDF on a standard trained WRN-28- on CIFAR- 10, measured using 1000 random samples.
TARGETED
UNTARGETED
ATTACKS
FR
MEAN 2
MEDIAN &2
GRADS
FR
MEAN E
MEDIAN &
GRADS
DDN
100
0.24
0.25
100
100
0.13
0.14
100
FMN
96.2
0.22
0.24
100
97.3
0.11
0.13
100
SDF (TARGETED)
98.2
0.21
0.22
25
100
0.10
0.11
34
Furthermore, we can convert SDF to a targeted attack by replacing the line of Algorithm with the targeted version of DeepFool, and the line 4 with the following:
(T)
(ka..)) (i),
(17)
where t is the target label. We followed the procedure outlined in [6] to measure the performance in the targeted setting. The result is summarized in Table 21. While SDF is effective in quickly finding smaller perturbations, it does not achieve a 100% fooling rate. Further analysis required to understand the factors preventing SDF from converging in certain cases. This aspect remains for future work.
Convergence guarantees. A common challenge for all gradient-based optimization methods applied to non-convex problems is the lack of a guarantee in finding globally optimal perturbations for SotA neural networks. Obtaining even local guarantees is not trivial. Nevertheless, in Propositions I and 2 we worked towards this goal. We have established local guarantees showing the convergence of each individual operation, namely the DeepFool step and projection step. However, further analysis is needed to establish local guarantees for the overall algorithm.
Adaptive attacks. is known that gradient-basede attacks, ours included, are prone to gradient obfuscation/mmskingg [7]. To counter this challenge, adaptation, outlined in [55], is needed. It is also important to recognize that adapting geometric attacks such as SDF, does not follow a one-size- fits-all approach, as opposed to loss-based ones such as PGD. While this might be perceived as weakness, it actually underscores a broader trend the community. The predominant focus has been on loss- attacks. This emphasis has inadvertently led to less exploration and development in the realm of geometric attacks.
Vanila Adversarial Training
Vanila Adversarial Training without Additional Regularization. Our primary objective was to evaluate which adversarial attacks technique most effectively enhances robustness among PGD [33], DDN [48], and SDF. This focus differs from comparing various adversarial training strategics such TRADES [59], TTADES-AWE [57], HAT [43], and UIAT [16]. These strategies often include additional regularization techniques to enhance Madry's 's method using PGD adversarial examples. saate-of-the-all robust model. Instead, aim to demonstrate that vanilla AT, when combined with minimum-norm attacks like SDF, can potentially outperform PGD-based models. Accordingly, we selected vanilla adversarial training with -ggneraedd samples for our study and compared its effectiveness against a network trained with DDN samples. While TRADES similar AT strategies could also integrate SDF, exploring this combination will be addressed in future research endeavors.
Therefore, assertion is not aimed at developing
Why lp norm is Critical? The existing literature has explored variety of approaches under- standing adversarial examples. For example, training on f--norm adversarial examples has been identified as a form of spectral regularization [50], and adversarial perturbations, seen as counter- factual explanations, have been connected to saliency maps in image classifiers [20]. The rapid and accurate generation of these perturbations critical for the empirical investigation of such phenomena. Moreover, minimal l, adversarial perturbations are often considered "first order approximations of the decision boundary," illuminating the local geometric characteristies of models near data samples. This insight underscores the need for quick and precise methods for such explorations. Additionally, these
23

---

minimal perturbations provide data dependent, worst-case analysis of certain test-time corruptions, facilitating worst-case evaluations not only in the input space but also in the transformation space [29]. Within the context of Large Laaguuage Models (LL.Ms), these perturbations could potentially act as probing tools within their embedding space to examine their geometric properties. However, important to note that our interest in these topics was driven more by academic curiosity than by their practical applications in this specific study.
Multi-class algorithms for SDF (1,3) and SDF (1,1)
Algorithm (3,4) summarizes pseudo-codes for the multi-class versions of 1DF(11,) and SDF(1,3).
Algorithm 3: SDF (1,1)
Algorithm 4: SDF (1,3)
Input: image æ, classifier f.
Input: image æ, classifier
Output: perturbation r
Output: perturbation r
Initialize: Zo -- æ, i +
Initialize: 2g + x, i
while k(xx;) = k(x0) do
while k(x,) = k(xx)) do
for k + k(xo)) do
for k + k(wo) do
w + Van(z;)) - V ( (w:)
w/ - V (x(ii)
(k(ee)) (x)))
fk + fE((T;) fk(mm)) (x;)
fb. + (x;;;) - fk(20) (2:)
end
end
1K
1/
[ f- arg min, kxp((a))))
f arg min k
11 12
|
F |
W. 22
24
F
w
-2 + 34
u7;
fM( (2:))
V (2 (i:)
for steps do
x f- 30
[w 1
wi
wi
f ((.)) (2:)
fi(m0)) (3)))
- +
(a: w. w.
7 end
0; <- To +
1|
return 07; 250
end
10
<- i
11
end
12
return
x;
24

---

NeurIPS Paper Checklist
Claims
Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Guidelines: The code to reproduce our experiments can found at https://gitth com/ htt///arreaaabolllaaa ahpour //sppourr/Superepppoolll
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/ h/t::://neuuippeeee http:ippp..cppppp/eeeeeeee
Answer: [Yes]
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
25

---

Our paper deals with fundamental questions regarding our understanding of deep networks. In this sense, subject the same ethical concerns as the machine learning field whole, which makes it hard to identify potential direct risks or benefits associated to our empirical findings.
Justification:
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer:[NA]
26


Reviews:
[{"review_id": "t66nABRT2v", "reviewer": "Reviewer_UfKL", "summary": "The paper introduces a new family of adversarial attacks called SuperDeepFool (SDF) attack, extending the well-known DeepFool (DF) attack. This novel approach strikes an proper balance between effectiveness and efficiency, and consistently outperforms existing methods in terms of both. Additionally, the method can be adapted for robustness evaluation and adversarial training.", "questions": "1. Can the method be generalized to the $\\ell_p$-norm?\n2. Do we expect similar performance for smaller $\\varepsilon$, e.g. $8/255$?\n3. Is the case SDF(m,$\\infty$) also interesting?\n4. How do we determine the number of iterations in SDF beforehand?", "limitations": "The potential limitations are outlined in the weaknesses and questions sections.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The concept of integrating DF with minimal adversarial perturbations is both novel and intriguing.\n2. The theoretical analysis is sound: DF iterations converge to a point on the decision boundary, while SDF iterations converge to a point orthogonal to the decision boundary.\n3. Comprehensive experiments demonstrate SDF's remarkable performance compared to existing methods, in terms of both Fooling Rate (FR) and the number of gradient computations (Grads).\n4. The experiments consistently show improvements over DF and minimum-norm attacks, together with its potential for adaptation in adversarial training (AT).", "weaknesses": "1. The method is limited to the $\\ell_2$-norm.\n2. Most of the experiments are conducted with $\\varepsilon=0.5$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## $\\textbf{General comment}$:\nWe sincerely thank the reviewer for his/her positive assessment of our work, recognizing the novelty of our approach, the soundness of our theoretical analysis, and the strength of our empirical results. We are also pleased that the potential of SuperDeepFool for adversarial training is recognized.\n### $\\textbf{The method is limited to $\\ell_{2}$ norm}$.\nFirst, we revisit the role of $\\ell_{2}$ adversarial robustness in the robustness community. Then, we bring our results for the $\\ell_{\\infty}$ norm of SDF.\nAs we discussed in $\\texttt{lines 91 to 102}$ of the $\\texttt{main text}$ of the paper, the reasons for using $\\ell_{2}$ norm perturbations are **manifold**. We acknowledge that $\\ell_{2}$ threat model may not seem remarkably realistic in practical scenarios (at least for images); however, it can be perceived as a basic threat model amenable to both theoretical and empirical analyses, potentially leading insights in tackling adversarial robustness in more complex settings. The fact that, despite considerable advancements in AI/ML, we are yet to solve adversarial vulnerability motivates part of our community to return to the basics and work towards finding fundamental solutions to this issue $\\textcolor{blue}{[8, 24, 33]}$. In particular, thanks to their intuitive geometric interpretation, $\\ell_{2}$ perturbations provide valuable insights into the geometry of classifiers. They can serve as an effective tool in the \"interpretation/explanation\" toolbox, a versatile role of our method, to shed light on what/how these models learn.\nIt should be noted that the focus of our paper, as stated in the abstract, is on minimal $\\ell_{2}$ norm perturbations.\nNevertheless, we tried a $\\ell_{\\infty}$ version of SDF by replacing the $\\textit{orthogonal projection}$ with the $\\ell_{\\infty}$ projection (Holder's inequality). The table in $\\texttt{attached rebuttal pdf}$ shows our results for $\\ell_{\\infty}$ on M1 $\\textcolor{blue}{[32]}$ and M2 $\\textcolor{blue}{[47]}$. Our results show that this version of SDF also outperforms other algorithms in finding smaller $\\ell_{\\infty}$ perturbations (**the result is presented in the attached rebuttal pdf**). We will add this result to the Appendix.\n### $\\textbf{Do we expect similar performance for smaller $\\varepsilon$, e.g. 8/255?}$ (Most of the experiments are conducted with $\\varepsilon=0.5$).\nFirst, we should note the reason that we use $\\varepsilon = 0.5$ for comparison between $\\ell_{2}$ versions of AA and AA++ is that this budget ($\\varepsilon = 0.5$) is a **standard** case for comparison models in robustbench $\\textcolor{blue}{[12]}$ for CIFAR-10. Indeed, the primary models that robustbench $\\textcolor{blue}{[12]}$ want to evaluate primary adversarially trained with that specific budget ($\\varepsilon = 0.5$), so the **standard** way to evaluate their robustness is using that specific budget. \nFor instance, the standard budget for $\\ell_{\\infty}$ on CIFAR-10 is $8/255$, and for $\\ell_{2}$ on ImageNet, it is $\\varepsilon = 3.0$. But in any case, we are grateful for your suggestion and will present our results for other budgets.\n#### **$\\varepsilon = 0.3$ for $\\ell_{2}$ on CIFAR-10 result is presented in attached rebuttal pdf.**\n#### **Comparison between our AT model and $\\textcolor{blue}{[47]}$ beyond other $\\varepsilon$ :**\nWe presented these results in $\\texttt{line 363}$ of the main text and **Tables 12** and **13** of the $\\texttt{appendix}$ for both the $\\ell_{\\infty}$ and $\\ell_{2}$ versions of AA across a wide range of $\\varepsilon$ values.\n### $\\textbf{How do we determine the number of iterations in SDF beforehand?}$\nIt is important to note that SDF is a **parameter-free** attack. This implies that we do not set a fixed number of iterations for SDF; instead, the algorithm runs **until** it identifies the **adversarial point**. This factor significantly contributes to the exceptionally high speed of SDF. The results presented in the tables demonstrate that SDF computes a substantially **smaller** number of gradients compared to other algorithms to identify the adversarial point. To ensure a **fair** comparison between SDF and other fixed iteration attacks, we standardized the maximum number of iterations for the algorithm. Specifically, when comparing **fixed iteration** algorithms that operate with $100$ iterations, we set the maximum number of iterations for SDF to $100$ and vice versa.\nAlthough the **iteration-free** property of an algorithm can enhance its convergence speed, a **critical** question arises: $\\textit{“When the algorithm terminates upon finding the adversarial point, how can we \\textbf{ensure} that this adversarial point is optimal?”}$ This is one of the key **criticisms** that can be raised against **DeepFool**. As demonstrated in $\\texttt{Figure 3 (Left)}$ of the main paper, DeepFool's perturbations are **not** optimal and tend to be overly perturbed (extrapolated).\nTo address this issue, we can employ a **line search** at the end of the DeepFool algorithm to ensure that the perturbations are **not** excessively large and remain on the decision boundary. However, as shown in $\\texttt{Figure~3(Right)}$ of the main paper, line search $\\textit{alone}$ **cannot** resolve the issue of **orthogonality**.\n\n### $\\textbf{Is the case SDF(m, $\\infty$) also interesting?}$\nWe appreciate your insightful perspective. However, we must clarify that this cannot be considered an interesting case. Let us revisit the rationale behind the SDF$(m, n)$ and explain why, although SDF$(\\infty, 1)$ is a case of interest and controversy, SDF$(m, \\infty)$ **cannot** be considered interesting. The **orthogonal projection** step in SDF$(\\infty, 1)$ crucially **reduces** perturbation sizes, ensuring minimal adversarial perturbations. By iteratively using this projection, the optimal direction is **preserved**, leading to minimal perturbations that **cannot fool** the classifier, thereby maintaining classifier accuracy.", "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": "", "extra_scores": {}}, {"review_id": "D7ynWN2yGb", "reviewer": "Reviewer_e1KW", "summary": "The paper presents a novel, parameter-free and computationally efficient minimal-$L_2$ adversarial attack. Building on the DeepFool attack and incorporating a novel geometric perspective, the SuperDeepFool attack achieves state-of-the-art success rates on selected MNIST, CIFAR10, and ImageNet classifiers. The authors demonstrate that SuperDeepFool maintains computational efficiency while achieving higher success rates in fooling neural networks compared to similar attacks. Adversarial training experiments show that this approach improves the evaluation of neural network robustness against adversarial attacks.", "questions": "1. Optimality Measurements: I believe comparing DF with simple $\\gamma$ optimization against SuperDeepFool (SDF) is essential to start with, since it's much faster and is presented as a measure of optimality.\n2. Comparison Tables: In tables such as 2 and 3, it is not clear if both DF and SDF achieve 100% success rates. Could you clarify the success rates and explain how averages are computed?\nHow do you account for variations across different models when presenting average success rates?\n3. Adversarial Training (AT) Comparison: The comparison in the Adversarial Training section is quite brief. Could you elaborate on whether the evaluated network is state-of-the-art in terms of robustness and how it is optimized to defend against minimum-norm attacks?\nThe perturbation size of 2.6 chosen for SDF seems arbitrary. Could you explain the rationale behind this choice, especially given the convention of using 0.5-norm attacks (other AT networks don't claim to be robust to larger perturbations)?\n4. Auto Attack Comparison: The discussion on the comparison with auto attack is also brief. Why did you choose to switch from multitarget APGD to single target SDF without evaluating the multitarget approach?\nDoes multitarget SDF achieve better robust accuracy?", "limitations": "The authors discussed the limitations of their experimental work - the limited evaluation of the SDF methods on a big variance of robust and non-robust classifiers, and extensions to targeted attacks and different norms. (no justifications for limitations on the checklist)", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is clear, well-organized, and provides excellent geometric intuition and presentation. The illustrations are particularly effective in conveying complex concepts. The novel SuperDeepFool method demonstrates significant improvements over existing techniques by identifying the optimal adversarial point orthogonal to the decision boundary and employing an alternating optimization strategy. The paper's approach of combining the DeepFool attack with orthogonality optimization leads to higher success rates while maintaining computational efficiency. Additionally, the comprehensive comparisons and experiments highlight the effectiveness of SuperDeepFool across different models and datasets.", "weaknesses": "The paper has several areas that need further elaboration. The measurements to test optimality are simple and strightfoward, particularly regarding whether a $\\gamma$ < 1 factor makes the adversarial perturbation fail. Hence, it is not clear whether a simple gamma optimization with DF could outperform SuperDeepFool (SDF). Comparisons in tables (e.g., Tables 2 and 3) lack clarity on success rates and how averages are computed. The comparison with Adversarial Training (AT) is very interesting but too brief, raising questions about the chosen perturbation size and the network's optimization against minimum-norm attacks. Additionally, the discussion on the comparison with auto attack is also too brief, and the rationale for switching from multitarget APGD (or other attacks) to single target SDF without evaluating the multitarget approach is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## $\\textbf{General comment:}$\nWe really appreciate the reviewer’s enthusiasm and acknowledgment of the significance of our work. We address the reviewer's concerns below.\n### $\\textbf{Optimality Measurements:}$\nFirstly, it is important to note that while avoiding overly perturbed perturbation is a **critical** property of minimal adversarial perturbation, **orthogonality** is another equally crucial aspect. In Figure 3 (right) of the main paper, we measured orthogonality by **bringing all perturbations** to the decision boundary using a **line search** at the **end** of the DF algorithm (Indeed, we optimize $\\gamma$). This process is carried out **outside** the **main loop** of DF to ensure that the algorithm's **fooling rate** is **preserved**, as detailed in *lines 142 and 143 of the main paper*. \nFigure 3 (right) demonstrates that **even though** DF perturbations **lie on** the decision boundary and are **not** overly perturbed due to the line search, they still do **not** achieve optimal orthogonality. This raises a pertinent question: *How can we establish a connection between orthogonality and the minimality of perturbations?* We address this question in **two** ways:\nFirstly, by adding a line search to the end of DF, we optimize and compare the results of $\\texttt{DF+line search}$ and SDF (*Results are presented in the attached rebuttal pdf. While line search in DF reduces perturbation norm, it doesn't guarantee optimal results, even with over 20 iterations.*). Secondly, we show that the **goal** of achieving minimal adversarial perturbation **extends beyond** minimality in terms of *median, mean, and quantity*; it also encompasses the **direction** of minimal adversarial perturbation:\nAdversarial training for robust models requires finding adversarial perturbations with **optimal direction**, not just optimal size. CURE [36] shows that adversarial training primarily regularizes curvature, prioritizing curvature-reducing directions. Our analysis shows that our model trained with optimal direction perturbations has considerably lower curvature, confirming the importance of optimal direction for model robustness.\n### $\\textbf{Comparison Tables:}$\nTo compute Fooling Rates (FR), we follow the standard methodology in the literature by counting the number of samples that are *fooled* or *not fooled*. Specifically, a sample is considered fooled by adversarial perturbation if the model misclassifies it. Conversely, if the model correctly classifies a sample, the perturbation is deemed ineffective in fooling the classifier. It is important to note that before evaluating the algorithms, we **exclude** any samples that the model *initially* misclassifies.\nIt is important to note that in Table 2, we do **not** report the FR or ASR. Instead, we present the results of the *level of orthogonality* obtained by DF and SDF. These results are identical to those shown in Figure 3 (Right) and Figure 4.\n### $\\textbf{Elaborate on evaluated networks}$:\nIt is important to mention that the procedure of *\"Vanilla Adversarial Training\"* is explained in Appendix O of the main paper (lines 864 to 875).\n#### **Why is an adversarially trained (AT) model with strong minimum-norm attacks like SDF robust to others?**\nAT models with optimal perturbations can **potentially reduce** the model's curvature *concerning adversarial directions*. Specifically, when a model is made robust using optimal directions generated by **strong** minimum-norm attacks such as SDF, it is likely to exhibit robustness against perturbations produced by *sub-optimal* minimum-norm attacks, including DF, FMN, FAB, and others.\nThe results are displayed in Table (6) of the main paper.\n### $\\textbf{The perturbation size of 2.6}.$\nThe maximum perturbation budget ($\\varepsilon$) of 2.6 is based on the standard ℓ∞ epsilon of 8/255, which translates to an ℓ2 norm of approximately 1.75. This value was slightly increased to allow for a wider range of perturbations, but as Table 4 shows, the impact of this choice is minimal due to the low median perturbation size.\n### $\\textbf{AA Comparison:}$\nIt is important to note that APGD is not considered a minimum-norm attack but instead considered a norm-bounded attack.\nThe main procedure of AA involves utilizing strong bounded-norm attacks such as APGD to find adversarial perturbations. Subsequently, a minimum-norm attack like FAB is employed to minimize the discovered perturbations accordingly. When utilizing APGD in the context of a minimum-norm version, it is advisable to incorporate a binary search [48]. To ensure 100% ASR, a sufficient budget is allocated for the binary search. The budget size depends on the dataset being used. By allowing the attacks to achieve a 100% ASR and conducting multiple binary search steps, a precision of 0.01 for the ℓ₂-norm can be achieved, as previously demonstrated by [48]. This will significantly raise the cost of computations. One might wonder why we choose to replace SDF with APGD instead of FAB as a minimum-norm attack in a set of AA. While our paper primarily focuses on other aspects, we aim to improve the time efficiency of the AA. Undoubtedly, the primary limitation of AA is its computational time.\nIn general, combining a series of attacks and attempting to navigate through a sample can be accomplished using various different attacks (selecting the most powerful attack for each norm). However, a particularly intriguing scenario is one that can achieve this integration in the most efficient manner possible. So, we swap SDF for the critical point of a bottleneck for AA, known as APGD (line 733 of the appendix in the main paper). Nevertheless, this critique can still be directed towards our idea: How can we ensure the previous performance of AA with this modification? It is generally not possible to guarantee the performance of AA++ for all models. However, we can evaluate our notion through experimental evaluation, as we have done in our study.", "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": "", "extra_scores": {}}, {"review_id": "umhIBFW9U3", "reviewer": "Reviewer_ojpB", "summary": "The paper introduces SuperDeepFool (SDF), a new adversarial attack algorithm designed to evaluate the robustness of deep neural networks against L2-norm adversarial attacks. SDF generalizes the DeepFool (DF) attack by incorporating a projection step to find smaller perturbations while maintaining computational efficiency. The authors demonstrate that SDF outperforms many L2-norm attacks in terms of both effectiveness and computational cost on MNIST, CIFAR10 and ImageNet.", "questions": "N/A", "limitations": "A discussion of limitation is not found in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Strengths:\n\n1.\tEfficiency and theory justification: Based on the experimental results, SDF achieves a better trade-off between computational cost and attack efficiency compared to other baselines. Theoretical analysis is provided to support that such algorithm can converge to a point on the boundary.\n2.\tExperiments: The paper provides experimental results across three datasets, including a large one (ImageNet). It also shows that it can be combined with AutoAttack to further improve its strength.\n3.\tRobustness Improvement: The paper demonstrates that adversarial training using SDF-generated examples can better enhance the robustness image classifiers compared to DDN.", "weaknesses": "Weaknesses:\n\n1.\tClarity Issues: Generally speaking, it is well-organized, but there are some minor things make it not very clear. For example, on Line 123, the sentence “on about the geometrical…” misses the beginning part. In Section 3, $f$ represents a binary classifier when explaining the theory and algorithms in 3.1, but it was defined as a C-class classifier in Section 2. It is better to distinguish the two using different notations.\n2.\tNovelty: In fact, leveraging the geometry of decision boundary to improve the efficiency of adversarial attacks is not a new idea. This has been explored in many blackbox attacks, such as [1], [2]. A discussion of the relationship between the proposed idea and previous works would help improve the work.\n\n[1] Cheng, M., Singh, S., Chen, P., Chen, P. Y., Liu, S., & Hsieh, C. J. “Sign-opt: A query-efficient hard-label adversarial attack.” ICLR. 2020.\n\n[2] Chen, Jinghui, and Quanquan Gu. \"Rays: A ray searching method for hard-label adversarial attack.\" KDD. 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## $\\textbf{General comment:}$\nWe are grateful to the reviewer for recognizing SuperDeepFool's efficiency, theoretical justification, and strong empirical performance across various datasets and tasks. We also appreciate the acknowledgment of its potential to improve adversarial robustness through training.\n### $\\textbf{Clarity Issues $\\rightarrow$ notations}:$\nThank you for your valuable feedback. We will address the clarity issues you mentioned in the final version. Please note that the main paper already includes pseudo-code algorithms in the appendix for all versions.\n### $\\textbf{Novelty:}$\nThank you for your insightful suggestion. In $\\texttt{lines 210-215}$ of the $\\texttt{main manuscript}$, we have acknowledged that the method of iteratively approximating the decision boundary using a hyperplane, followed by the analytical determination of the minimal adversarial perturbation for a linear classifier, bears a resemblance to the approach employed by GeoDa $\\textcolor{blue}{[43]}$ in black-box settings.\n\nSuperDeepFool is indeed inspired by DeepFool's core principles to **iteratively approximate the decision boundary** with a *hyperplane* and then analytically calculate the minimal adversarial perturbation for a linear classifier for which this hyperplane is the decision boundary. It is crucial to recognize the substantial advancements it introduces. \nSuperDeepFool reimagines the approach to adversarial perturbations through several **key innovations**:\n\n**Balancing Geometry and Optimization**:  A key insight of SuperDeepFool is *striking* a balance between the **geometrical inspiration** of deep neural networks and **modern optimization techniques**. We avoid the *pitfalls* of relying **solely** on **hyperparameter tuning** or **excessive iterations**. Instead, we leverage **both** geometrical understanding and efficient optimization to achieve **near-optimal** solutions with **fewer iterations**, which is crucial for the development of robust LLMs, for instance, and large models. These innovations result in a qualitatively different attack, one that **not only** outperforms DeepFool **but** also the entire landscape of current state-of-the-art attacks, as evidenced by our extensive empirical results. We believe this shift towards a more balanced approach, emphasizing **simplicity** and **geometrical understanding**, is crucial for the future of adversarial robustness.\n\n#### $\\textbf{Key Insight:}$\nBroadly speaking, the approaches that employ **geometrical characterization** of deep neural networks can be categorized into white-box and black-box settings:\n1. White-box Settings: \n    - For $\\ell_{1}$ and $\\ell_{0}$ norms, SparseFool [1] iteratively approximates the decision boundary with a hyperplane while controlling the level of **sparsity**. It employs adaptive coordinate-wise control ($\\texttt{Qsolver}$). However, SparseFool encounters **issues** when dealing with **box constraints** in the range [0,1] (**clipping**) (𝜎-zero$\\textcolor{blue}{[3]}$, APGD-$\\ell_{1}$$\\textcolor{blue}{[4]}$).\n\n2. Black-box Settings: \n    - GeoDa [43] and qFool [2] aim to iteratively approximate the classifier's gradient with minimal query usage.\n\nThe most significant contribution of SuperDeepFool is its ability to strike a balance between two critical characterizations of optimal adversarial perturbations: lying on the decision boundary and maintaining orthogonality.\n\n### $\\textbf{A discussion of limitation is not found in the paper.}$\nOur limitations are clearly reported in the paper. In particular, we had a section in the Appendix (N). Following the reviewer’s suggestion, we will emphasize those points further in the revised version of our work.\n\n## References:\n[1]: Modas, A., Moosavi-Dezfooli, S., and Frossard, P. Sparsefool: a few pixels make a big difference. In CVPR, 2019.\n\n[2]: Liu, Y., Moosavi-Dezfooli, S. M., & Frossard, P. (2019). A geometry-inspired decision-based attack. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 4890-4898).\n\n[3]: Cinà, A. E., Villani, F., Pintor, M., Schönherr, L., Biggio, B., & Pelillo, M. (2024). 𝜎-zero: Gradient-based Optimization of ℓ0-norm Adversarial Examples. arXiv preprint arXiv:2402.01879.\n\n[4]: Croce, F., & Hein, M. (2021, July). Mind the box: ℓ1-APGD for sparse adversarial attacks on image classifiers. In International Conference on Machine Learning (pp. 2201-2211). PMLR.\n\n[43]: Ali Rahmati, Seyed-Mohsen Moosavi-Dezfooli, Pascal Frossard, and Huaiyu Dai. Geoda: a geometric framework for black-box adversarial attacks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8446–8455, 2020.", "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": "", "extra_scores": {}}, {"review_id": "WPZbDU3PSC", "reviewer": "Reviewer_Vkrz", "summary": "The paper introduces SuperDeepFool (SDF), a new family of adversarial attacks aimed at testing the robustness of deep neural networks against minimal L2 perturbations. The proposed attacks generalize the DeepFool (DF) attack, improving both computational efficiency and effectiveness. The authors show that SDF surpasses existing methods in both effectiveness and efficiency, making it ideal for evaluating large models and improving adversarial training to achieve state-of-the-art robustness.", "questions": "1. Can the insights gained from the proposed approach be extended to develop efficient black-box attacks?\n2. Are there realistic and practical scenarios where the proposed attack can effectively evaluate the robustness of neural networks?", "limitations": "1. The paper focuses on a white-box threat model, which is less practical and realistic than the more challenging black-box threat model.\n2. The paper focuses on L2 norm attacks, which may not adequately assess network robustness against realistic perturbations such as physical attacks.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper introduces a novel method that leverages the geometric properties of minimal L2 adversarial perturbations, offering an innovative perspective on adversarial attacks.\n2. The proposed method outperforms current state-of-the-art attacks by identifying smaller perturbations more efficiently, demonstrating superior effectiveness and computational efficiency.\n3. The authors conduct solid and comprehensive experimental validation, illustrating the superiority of SDF across various scenarios and benchmarks.\n4. The proposed method enhances the robustness of image classifiers through adversarial training, highlighting its practical applicability.", "weaknesses": "1. The paper focuses exclusively on L2 perturbations, which may not be the most practical or relevant threat model in real-world scenarios.\n2. The proposed method builds upon DeepFool, an existing state-of-the-art white-box attack, which may limit the perceived novelty and contribution of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## $\\textbf{General comment:}$\nWe sincerely thank the reviewer for their insightful and comprehensive assessment. We are particularly pleased that the reviewer recognized SuperDeepFool's core strengths: its computational efficiency, rigorous theoretical foundation, and robust empirical results demonstrated across a diverse range of datasets and tasks.\n### $\\textbf{Focus on $\\ell_{2}$ perturbations}.$\nGiven the 6,000-character constraint for this response and the substantial overlap between this section and the \"The method is limited to ℓ2\" section addressed for the $\\texttt{\"UfKL\" reviewer}$, we kindly refer you to our response in that section. Should you require further clarification or elaboration, please do not hesitate to inform us.\n### $\\textbf{The proposed method builds upon DeepFool,  Novelty}$.\nGiven the 6,000-character constraint for this response and the substantial overlap between this section and the **\"Novelty\"** section addressed for the $\\texttt{\"ojpB\" reviewer}$, we kindly refer you to our response in that section. Should you require further clarification or elaboration, please do not hesitate to inform us.\n### $\\textbf{Develop efficient black-box attacks.}$\nWe appreciate the reviewer's insightful question regarding black-box attacks. While SDF is primarily designed as a white-box attack, we believe the insights gained from our approach hold promise for developing efficient black-box techniques.\nAs mentioned in our paper, the strategy employed by SDF approximating the decision boundary and finding minimal perturbations \n shares similarities with the approach used in GeoDA [43], a black-box attack. This connection suggests that the **geometrical insights** underpinning SDF could potentially be adapted to the black-box setting.\n**However**, extending our method to black-box scenarios would **require** further research and modifications. Specifically, challenges such as estimating the decision boundary and its curvature **without** direct access to the model's gradients need to be addressed. We consider exploring these extensions as an exciting direction for future work and will investigate the feasibility of transferring our geometrically-inspired approach to black-box attacks.\nIn the meantime, we believe the current contributions of SDF as a white-box attack are significant. By establishing a new benchmark for minimal-norm perturbations and demonstrating superior performance on robust models, SDF provides valuable insights into adversarial robustness that can inform the development of future defenses, regardless of the attack scenario.\n\n### $\\textbf{Realistic and practical scenarios}.$\nWe appreciate the reviewer's emphasis on the importance of evaluating network robustness against realistic perturbations. While SuperDeepFool focuses on $\\ell_{2}$ norm attacks, we believe it has significant practical relevance for evaluating and improving the robustness of neural networks in several scenarios:\n\n**Benchmarking and Comparing Defenses:** The $\\ell_{2}$ norm provides a standardized and widely used metric for quantifying the magnitude of adversarial perturbations. SDF's ability to find minimal $\\ell_{2}$ norm perturbations makes it a valuable tool for benchmarking different defenses and comparing their effectiveness in mitigating adversarial attacks.\n\n**Understanding Model Vulnerabilities:** Even though $\\ell_{2}$ perturbations might not always directly translate to physical attacks, they can reveal underlying vulnerabilities in the model's decision boundaries. The **geometric insights** gained from SDF can help researchers identify regions of the input space where the model is particularly sensitive, guiding the development of more robust architectures.\n\n**Improving Adversarial Training:** Adversarial training is a common technique for enhancing robustness. By generating strong $\\ell_{2}$ adversarial examples, SDF can be used to augment training data and make models more robust to a broader range of perturbations, including those that might not strictly adhere to the $\\ell_{2}$ norm.\n\n**Bridging the Gap to Realistic Perturbations:** Research has shown that models robust to $\\ell_{2}$ attacks often exhibit improved robustness to other types of perturbations as well, including some physical attacks. While the transferability is not perfect, the $\\ell_{2}$ norm serves as a useful starting point for evaluating and improving robustness, as it **captures** the **general** concept of limiting the magnitude of perturbations [A, B].\n\n**Jailbreaking LLMs:**\nJailbreaking Leading Safety-Aligned LLMs with Simple Adaptive Attacks [C]: This paper shows that even safety-aligned LLMs are vulnerable to simple adaptive attacks that exploit the model's internal representations. The attacks involve perturbing the prompts to induce undesirable behavior, which can be seen as a form of attack in the embedding space by utilizing ℓ2 distance.\n\nFurthermore, our work on SuperDeepFool contributes to the ongoing research effort to bridge the gap between theoretical ℓ2 attacks and realistic perturbations. The insights gained from understanding and mitigating ℓ2 attacks are valuable stepping stones toward developing defenses against more complex and diverse threat models.\nWe acknowledge that ℓ2 norm attacks are not a comprehensive solution for evaluating robustness against all possible real-world scenarios. However, we believe that SuperDeepFool's contributions to the field, particularly its ability to find minimal ℓ2 perturbations and its superior performance on robust models, make it a valuable tool for both researchers and practitioners working on improving the security and reliability of neural networks.\n\n[A]: Tramèr,  The space of transferable adversarial examples. arXiv preprint.\n\n[B]: Moosavi-Dezfooli, Universal adversarial perturbations. CVPR 2017\n\n[C]: Andriushchenko, M., Jailbreaking leading safety-aligned llms with simple adaptive attacks. ICML 2024 Workshop on the Next Generation of AI Safety", "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": "", "extra_scores": {}}]

Author rebuttal:
We attached a pdf file containing the desired results.

Meta-review: **Summary of the paper**

This paper proposes improving a well-known adversarial example generation attack, DeepFool. Specifically, the authors observe that DeepFool does not generate an adversarial perturbation that is orthogonal to the decision boundary, suggesting that DeepFool is generating suboptimal adversarial examples. To address this issue, the authors propose a new method that projects the adversarial perturbation toward the optimal perturbation direction. The authors provide a few theoretical results and extensive experiments to support the improvement. 

**Summary of the discussion**

* All the reviewers mentioned that this paper's strengths are in the novelty of the idea, the quality of the theoretical analysis, and the comprehensive experiments, which showed impressive performances.
* Reviewer UfKL points out two weaknesses.
  * First, the paper only focused on $L_2$ perturbations. The authors claim that the $L_2$ perturbation can be perceived as a basic threat model amenable to theoretical and empirical analyses. They also added the results for the $ L_\infty$ version of SuperDeepFool. 
  * Second, most experiments are conducted on a fixed attack radius. Regarding the second weakness, the author pointed out that it is the standard setup used to evaluate robustness. The author also presented results for a different parameter setting in their revision.
  * After the discussion, the reviewer maintained the initial rating of 7.
* Reviewer e1KW points out three weaknesses.
  * First, the optimality measurement for the DeepFool is too simple, and the DeepFool algorithm might provide better perturbations than the proposed method. Regarding the optimality measurement, the authors emphasized that orthogonality is another crucial aspect that should be considered in the optimality definition, so adjusting the $\gamma$ parameter would not make the DeepFool perturbations stronger than the proposed method.
  * Second, the comparisons in some experimental results seem unclear. The authors clarified the tables that the reviewer found confusing.
  * Third, the comparisons to adversarial training and auto-attacks are too brief. The authors justified why their comparisons to adversarial training and auto-attacks are sufficient.
* Reviewer ojpB points out two weaknesses.
  * First, the reviewer points out some minor writing issues that should be improved. The authors accepted the writing improvements.
  * Second, the proposed idea used an idea explored by many existing methods. Regarding the originality of their work, the authors admitted that their idea is mostly based on DeepFool’s core principle. but they also clarified their key innovations in improving DeepFool’s idea.
  * After the discussion, the reviewer maintained the initial rating of 6.
* Reviewer Vkrz points out two weaknesses.
  * First, the paper only focused on $L_2$ perturbations.
  * Second, the proposed method merely improves DeepFool rather than an original attack algorithm.
  * Because Reviewer Vkrz mentioned the same weaknesses as Reviewer UfKL and Reviewer ojpB, the authors simply referred to their rebuttal arguments against those reviewers.
  * After the discussion, the reviewer maintained the initial rating of 6.

**Justification of my evaluation**

* My rating is 7.
* In general, the contribution seems enough for paper acceptance. This is a well-written paper.
* The authors communicated effectively during the discussion. However, the arguments were not enough to change any reviewer’s rating. In my opinion, the reviewer’s initial ratings were accurate, and I don’t think it would be possible to increase the rating further.
* I also agree with the reviewers that the proposed method is an improvement of a well-known method rather than a new invention of a new algorithm. Considering this lack of novelty, I’d not recommend this paper for the spotlight.

I’m confident about my evaluation and recommend accepting this work (poster).
Decision: Accept (poster)