Revisiting DeepFool: generalization and improvement

SDF appears to consequently require more gradient steps than DF.

Our claim is that, in comparison to other algorithms, SDF offers the best tradeoff between computational cost and accuracy. As illustrated in Figure 1, compared to DF, SDF incurs a slightly higher computational cost but significantly gains in accuracy.

By design, both SDF and DF do not allow control over the number of gradient computations. They typically stop once a successful adversarial example is found. Terminating the process prematurely could prevent them from finding an adversarial example. One naive way would be the following: limiting SDF to a single iteration would equate its computational cost to DF, but this would essentially make SDF identical to DF, hence not a useful comparison.

As the goal is to improve DF, comparisons to DF are missing in Tab. 5/19/20.

DF, developed nearly eight years ago, has been demonstrated in various instances [1], [2], and [4] to be fast but no longer the SotA in identifying minimal adversarial perturbations. Therefore, we primarily conducted our experiments using SotA $\ell_2$ attacks. Table 1 is the exception, where we included a comparison with DF, as it was pertinent to compare SDF to DF – given that SDF is a modified version of DF.

But for the sake of completeness, we will include DF in the tables as suggested by the reviewer. Here are the corresponding results for DF:

• In Table 5: the median $\ell_2$ norm: 6.1, fooling rate: 96.2%.
• In Table 19: the median $\ell_2$ norm: 1.51, fooling rate: 100%.
• In Table 20: Naturally trained model: the median $\ell_2$ norm: 0.17, per-sample time: 0.21s. Adversarially trained models (R1): the median $\ell_2$ norm: 2.1, per-sample time: 1.32s.

The comparison in Sec. 4.3 against DDN is not fair…

Thank you for the suggestion. We reran our experiments using three different random seeds for training, and we set the number of epochs used in the DDN paper. Despite these adjustments, our findings remain consistent: SDF AT continues to outperform DDN AT.

"SDF adversarially trained model does not overfit to SDF attack”…

We hope that the experiment done above has addressed this issue, too.

The research field has largely moved on from minimum-norm…

We respectfully disagree with the reviewer. The reasons for using $\ell_2$ norm perturbations are manifold:

• We acknowledge that $\ell_2$ 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 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.

• 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 to shed light on what/how these models learn.

• Moreover, it has been demonstrated that (see, for example,[4] and [9]), $\ell_2$ robustness has several applications beyond security.

• While not the most compelling reason, the continued interest of the community in $\ell_2$ perturbations is evidenced by publications in top venues, including FMN [7] in NeurIPS 2021, DDN [5] in CVPR 2019, ALMA [10] in ICCV 2021, FAB [8] in ICML 2021, among many others.

How are perturbations "renormalized" for AutoAttack++?

For a given $\epsilon$ for AA++, if the norm of perturbation generated by SDF is greater than $\epsilon$, we apply a scalar multiplication to bring its $\ell_2$-norm down to $\epsilon$. Hence, we ensure that all the norms of all SDF perturbations are at most $\epsilon$.

Why does AA++ perform worse for R4?

For this particular model, we identified a few samples that SDF could not successfully fool, whereas APGD$^\top$ did. Therefore, we explored an alternative version of AA++ where we included SDF alongside the set of attacks, rather than replacing APGD$^\top$ with it, ensuring the preservation of AA’s original performance.

[1]: Rony, Jerome et al. "Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.

[2] Carlini, Nicholas and David A. Wagner. “Towards Evaluating the Robustness of Neural Networks.” 2017 IEEE Symposium on Security and Privacy (SP) (2016)

[3] Madry, Aleksander et al. “Towards Deep Learning Models Resistant to Adversarial Attacks.” ArXiv abs/1706.06083 (2017)

[4]: Pintor, Maura et al. "Fast minimum-norm adversarial attacks through adaptive norm constraints." Advances in Neural Information Processing Systems, vol. 34, pp. 20052-20062, 2021.

[5]: Croce, Francesco and Hein, Matthias. "Minimally distorted adversarial examples with a fast adaptive boundary attack." International Conference on Machine Learning, pp. 2196-2205, 2020, PMLR.

We thank the reviewer for revising their score. To better address your remaining concerns, particularly regarding the contributions of our work, we would greatly appreciate more specific feedback.

We would like to bring to your attention that in Appendix F of our paper, we have dedicated a section to discussing how SDF has led us to an interesting observation regarding the effect of pooling layers on the adversarial robustness. It further highlights the importance of developing minimum-norm adversarial attacks.

The other attacks are tested with default hyperparameters…

To ensure a fair comparison, for each dataset, we selected hyperparameters for each attack based on those recommended in their respective papers. The assumption was that the authors of these papers have either fine-tuned these parameters or claimed that their methods are not highly sensitive to them.

Given that comprehensive hyperparameter tuning for each attack across every model and dataset would be infeasible for us, we experimented with different variations of the attacks by varying their number of iterations (as detailed in Table 3). We consistently aimed to select this parameter so that it would work in favor of their performance. However, we acknowledge the possibility that there may still be hyperparameter settings for each (attack, model, dataset) combination that could equalize the performance of all attack algorithms. Similar scenarios have been observed previously in the context of training algorithms and GANs, (Lucic et al. “Are GANs Created Equal? A Large-Scale Study”, NeurIPS 2018.)

This further highlights the importance of designing algorithms with fewer number of hyperparamters such as SDF.

additionally, it would be interesting to see the query-distortion curves...

Many thanks for this suggestion.

Note that, SDF (and DF) do not allow control over the number of gradient computations. They typically stop once a successful adversarial example is found. Terminating the process prematurely could prevent them from finding an adversarial example. Hence, we opted to plot the median norm of achievable perturbations for a given maximum number of queries. Although this is not directly comparable to the query-distortion curves in FMN, it provides a more comprehensive view of the query distribution than the median alone. The figures are placed in the Appendix K.

the attack should also be tested and compared in the targeted version…

Thanks for this suggestion. If time allows, we will include this experiment; otherwise, we will mention it as a future direction.

to claim that the attack finds perturbations “quickly”…

It may be helpful to differentiate between two distinct objectives: A) With a fixed “computational budget”, which algorithm finds the smallest perturbation. B) For a given a level of distortion, which algorithm requires less computation.

While there is not a straightforward method to directly address points A and B for SDF (as mentioned above), our results suggest that SDF is the fastest for “very small” distortions. Also, with a “very small” number of queries, it tends to find the smallest perturbation. It was the message we aimed to convey in Figure 1.

We also measured the number of forward and backward passes separately for a robust WRN-28-10 model. The median values for the forward and backward passes of SDF are 50 and 32 per sample, respectively. The time spent on other operations was less than 1% of the total time. It achieves a median norm of 0.77. While FMN-100 achieves a median norm of 1.43 using 100 forward and 100 backward passes per sample, FMN-1000 reaches a median norm of 0.87 with 1000 forward and 1000 backward passes.

The attack algorithm should enforce this constraint "by default"...

We report all our results with clipping as the final step in the algorithm. We acknowledge the reviewer's point that this might not be enough IF our focus is on the "real-world" security implications of these attacks. However, if the purpose is to use them for data augmentation, for example, then such a requirement might not be needed anymore.

Anyway, we played with the in-loop clipping as well, yet observed no noticeable difference between the two methods in our experiments.

Clarifications

The authors should clarify this aspect to make the paper…

We will clarify this sentence in the text, and will include a figure in the Appendix XX to visualize the concept.

The authors should state that the bounded-norm attacks solve a different problem than (1).

Thanks for the suggestion. Indeed. We modify the text to clarify this distinction.

As it is a scalar multiplied by the gradient, is the first part of eq. 4 an estimation of the step size?

Yes, indeed. We will make it clear in the text.

The authors should discuss why the other attacks are not parallelizable, as they state that attacks for AT should be and CW, for example, is not.

Other algorithms usually use perform one backward pass per iteration, resulting in these backward passes being non-parallelizable as they need to be performed sequentially. However, in the case of SDF, some of the backward passes can be executed in parallel, especially the backward passes that are carried out in each iteration of the inner loop in the multi-class case.

We appreciate the reviewer's constructive feedback and positive view of our work. We address the questions raised in the following:

Limitations

We are going to add a new section in the paper to discuss the limitations of our work (Appendix L). However, let us first elaborate on them here.

The attack is not adaptive per-se…

We acknowledge that, generally, extending geometric attacks to such cases is not immediately apparent. However, we do not view this as an inherent limitation of geometric attacks like DF and SDF. Instead, we believe the community's focus to obtain adaptive attacks has primarily been on loss-based attacks such as PGD, which allow for easy modification of the loss. Investigating ways to adapt geometric attacks could be of interest, particularly due to their computational benefits

The attack is still an empirical attack…

This indeed can be said about almost any gradient-based optimization technique applied to non-convex problems. As such, we thought it is evident from the context that there is no guarantee for finding the globally optimal perturbations for state-of-the-art neural networks—neither for us nor for any other attacks we are aware of. We apologize if our wording caused such confusion. If there is any specific sentence in the text implying otherwise, we would be grateful if the reviewers could point them out to us.

The attack formulation only works for the $\ell_2$ norm.

We had reasons to limit the scope of the paper to $\ell_2$ perturbations. We believed this approach would more clearly convey our meta-message, as summarized by Reviewer 34Xw: ”the importance that fundamentally 'classic' approaches, if done right, might still serve as a strong baseline". Anyway, we tried a simple idea to see the potential of our approach in finding $\ell_\infty$ perturbations, and it worked. We replaced the orthogonal projection with the $\ell_\infty$ projection.

We present our findings about the $\ell_\infty$ norm for two robust models M1 and M2 in the following table.

Improvements

Analysis of complementarity with AA, do the two attacks find smaller perturbations for different points? This could suggest whether the best strategy is to add it to the ensemble or to remove directly some of the sub-optimal attacks of AA (e.g., FAB that seems sub-optimal w.r.t. the proposed method). Additionally, in AA the attacks are used in a cascade manner, i.e., if the first attack finds an adversarial perturbation within the eps bound, the other attacks are not launched. Would SDF be launched before or after, e.g., APGD?

Our decision to replace APGD$^{\top}$ with SDF was primarily motivated by the former being a computational bottleneck in AA. As it is shown in Table 8, AA and AA++ achieve similar fooling rates, with AA++ being notably faster. Following your suggestion, we compared the sets of points that were fooled or not fooled by SDF/APGD$^{\top}$ across 1000 samples ($\epsilon=0.5$). The results indicate that both algorithms fool approximately the same set of points, differing only in a handful of samples for this epsilon value. Therefore, the primary benefit of using SDF is the reduction in computation time.

We are currently conducting experiments to provide a comprehensive analysis, which includes substituting SDF with various attacks, integrating SDF into the mix, etc. Given that they are time-consuming, it may not be feasible to complete them all by Nov 22. Anyway, we intend to include the full set of results in the final version of our work.

We are glad that the reviewer has liked several aspects of our work. We have done our best to address the questions and comments. Please let us know if there is anything more we can do to positively influence your opinion and strengthen the paper.

DeepFool was proposed and evaluated not only for $\ell_2$ adversarial robustness, but also had formulas (Holder's inequality) and evaluations for any $\ell_p$(including $\ell_0$, $\ell_1$, $\ell_\infty$) norm balls….

It should be noted that the focus of our paper, as stated in the abstract, is on minimal $\ell_2$-norm perturbations. If the reviewer has identified any sentences that suggest otherwise, please let us know. We would greatly appreciate your feedback. Whenever we mention DF, we refer to its $\ell_2$ variant. Moreover, up to our knowledge, DF was primarily introduced for $\ell_2$-norm, and its application to general $\ell_p$-norm perturbations was not extensively tested in the original paper.

Nevertheless, we tried an $\ell_\infty$ version of SDF by replacing the orthogonal projection with the $\ell_\infty$ projection (Holder's inequality). The table below shows our results for $\ell_\infty$ on M1 [1] and M2 [5]. Our results show that this version of SDF also outperforms other algorithms in finding smaller $\ell_\infty$ perturbations. We will add this result to the Appendix.

Only convolutional networks were used in the experiments…

Many thanks for the suggestion. Given our available computational resources, we conduct experiments on a ViT-B-16 [2] trained on CIFAR-10, achieving 98.5$\%$ accuracy. The results are summarized in the following table:

As seen, this transformer model does not exhibit significantly greater robustness compared to CNNs, with only a negligible difference of 0.01 compared to a WRN-28-10 trained on CIFAR-10 (0.09 in Table 3 of the paper). These results support the notion that there might not be a substantial disparity between the adversarial robustness of ViTs and CNNs. This aligns with the findings of [3]. 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.

Few additional hyperparameters $(n,m)$ are added and there is no methodology how to select them right.

We regard $(m,n)$ as a way to parameterize a class of algorithms, where each pair corresponds to an algorithm. As shown in Table 2 of the paper, all these variants yield comparable results. However, SDF($\infty$,1) empirically demonstrates a slightly superior performance (and hence is considered the default algorithm). For a new dataset, it is important to note that SDF($\infty$,1) might not be always the optimal algorithm. This is why we kept the class of algorithms general (it is needless to say that even to train a model on a new dataset, even the selection of architecture, optimization algorithm, etc. are not known apriori, and many methods used to determine those, can be equally applied here.)

Why does $\ell_2$ white-box adversarial robustness matter?

The reasons for using $\ell_2$ norm perturbations are manifold:

• We acknowledge that $\ell_2$ 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 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.

• 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 to shed light on what/how these models learn.

• Moreover, it has been demonstrated that (see, for example,[4] and [9]), $\ell_2$ robustness has several applications beyond security.

• While not the most compelling reason, the continued interest of the community in $\ell_2$ perturbations is evidenced by publications in top venues, including FMN [7] in NeurIPS 2021, DDN [5] in CVPR 2019, ALMA [10] in ICCV 2021, FAB [8] in ICML 2021, among many others.

A note on the spectral properties of $\ell_2$ perturbations: It is not entirely accurate to categorize $\ell_2$ perturbations as “high-frequency”. On the contrary, these perturbations tend to align more with "low-frequency" bands (see, e.g., [11]).

Why median and number of grads are used as the metric, while DeepFool used another one?

To ensure a fair comparison, we employed the metrics commonly used in recent literature on adversarial robustness. Specifically, we employed the two most prevalent metrics: the median/mean of perturbation norms (taken over dataset samples) to evalaute the method's accuracy, and the number of backward passes to measure the computational complexity.

Nevertheless, one could argue that DF's $\rho$ (which normalizes the perturbation norm by the input sample norm) is conceptually similar to the mean of norms of perturbations. This is especially true given that the norm of samples tend to be quite concentrated for high dimensional data like CIFAR-10 and ImageNet. Hence, it can be said that they are almost equivalent up to a scaling factor. We can compute this metric, though, if the reviewer insists on its importance.

Why does experiment with adversarial training with SuperDeepFool not have models trained with PGD adversarial examples?

We excluded PGD AT, as DDN already outperformed it. For completeness, here is a modified version of Table 6 that includes PGD AT results.

Lots of space could be saved by combining tables and figures in one row (for example Table 3 and Table 8)

Thank you for this comment. ٌe have attempted to improve the presentation by putting Tables 3 and 8 in-line with the text.

[1]: Madry, Aleksander, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. "Towards deep learning models resistant to adversarial attacks." arXiv preprint arXiv:1706.06083, 2017.

[2]: Dosovitskiy, Alexey et al. "An image is worth 16x16 words: Transformers for image recognition at scale." arXiv preprint arXiv:2010.11929, 2020.

[3]: Bai, Yutong et al. "Are transformers more robust than cnns?" Advances in neural information processing systems, vol. 34, pp. 26831-26843, 2021.

[4]: Ortiz-Jiménez, Guillermo, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, and Pascal Frossard. "Optimism in the face of adversity: Understanding and improving deep learning through adversarial robustness." Proceedings of the IEEE 109, no. 5 (2021): 635-659.

[5]: Rony, Jerome et al. "Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.

[6] Carlini, Nicholas and David A. Wagner. “Towards Evaluating the Robustness of Neural Networks.” 2017 IEEE Symposium on Security and Privacy (SP) (2016)

[7]: Pintor, Maura et al. "Fast minimum-norm adversarial attacks through adaptive norm constraints." Advances in Neural Information Processing Systems, vol. 34, pp. 20052-20062, 2021.

[8]: Croce, Francesco and Hein, Matthias. "Minimally distorted adversarial examples with a fast adaptive boundary attack." International Conference on Machine Learning, pp. 2196-2205, 2020, PMLR.

[9]: Engstrom, Logan, et al. "Adversarial robustness as a prior for learned representations." arXiv preprint arXiv:1906.00945 (2019).

[10]: Rony, Jerome, Luiz G. Hafemann, Luiz S. Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. "Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.

[11]: Ortiz-Jimenez et al. “Hold me tight! Influence of discriminative features on deep network boundaries”, Advances in Neural Information Processing Systems, 2020.

We are happy that we could address many of your concerns.

Why $\ell_p$?

Several possibilities have been explored in the existing literature. For instance, training on $\ell_p$-norm adversarial examples is shown to be a form of spectral regularization [A], while adversarial perturbations—viewed as counterfactual explanations—are linked to saliency maps in image classifiers [B]. The fast yet accurate generation of such perturbations is crucial for the empirical study of these phenomena. Additionally, minimal $\ell_p$ adversarial perturbations can be viewed as "first order approximations of the decision boundary", shedding light on the local geometric properties of models in the vicinity of data samples. It similarly demands fast yet accurate methods for exploration. Furthermore, these minimal adversarial perturbations offer a data-dependent, worst-case analysis for certain test-time corruptions and enable worst-case assessments in the transformation space, not just the input space [C]. In the context of Large Language Models (LLMs), we can speculate that such perturbations could serve as probing tools within their embedding space to explore their geometric properties. Nevertheless, we must acknowledge that, like many other researchers, we were primarily motivated by academic curiosity rather than their practical applications in this particular work.

[A] Roth et al., "Adversarial Training is a Form of Data-dependent Operator Norm Regularization", NeurIPS 2020.

[B] Etmann et al., "On the Connection Between Adversarial Robustness and Saliency Map Interpretability", ICML 2019.

[C] Kanbak et al., "Geometric robustness of deep networks: analysis and improvement", CVPR 2018.

Adversarial training

The natural accuracies are as follows; SDF AT: 90.8%, DDN AT: 89.0%, PGD AT: 87.3%.

The primary goal was to determine which adversarial generation technique improves robustness most effectively (PGD, DDN, or SDF), rather than comparing various adversarial training strategies (vanilla (Madry's) AT, TRADES, TRADES-AWP, HAT) Such approaches normally incorporate additional regularization techniques to improve Madry's method with PGD adversarial examples. Thus, our claim is not about developing a SotA robust model. Instead, our goal is to illustrate that vanilla AT, when coupled with minimum-norm attacks such as SDF, may yield better performance compared to PGD-based models. Therefore, we opted for vanilla adversarial training with SDF-generated samples and compared it to a network trained on DDN samples. Certainly, TRADES or similar AT strategies can be employed in conjunction with SDF. This is the subject of future work.

We are pleased that the reviewer appreciates the simplicity and efficiency of our proposed method. We have addressed their comments in detail below. If there are any further aspects we can clarify or improve to positively influence their view of our work, please let us know.

It is not clear why the attack is strongest...

Like any other gradient-based optimization method tackling a non-convex problem, providing a definitive explanation for why one algorithm outperforms others is not straightforward. We have the following speculation on why SDF($\infty$,1) consistently outperforms the other configurations: Note that each projection step reduces the perturbation, while each DF step moves the perturbation nearer to the boundary. So when projection is repeated multiple times ($n>1$), it might undo the progress made by DF, potentially slowing down the algorithm's convergence. On the other hand, by first reaching a 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 Figure 3).

The comparison is done primarily for the $\ell_2$ norm...

Many thanks for the suggestion. Although, SDF is primarily designed to find minimal $\ell_2$ perturbations, we tried a simple idea to extend it to $\ell_\infty$ norm by substituting the $\ell_2$-projection step (line 5 in Algortihm 2) with the $\ell_\infty$ projection:

$\boldsymbol{x}\gets \boldsymbol{x}_0 + \frac{(\widetilde{\boldsymbol{x}}-\boldsymbol{x}_0)^\top\boldsymbol{w}}{||\boldsymbol{w}||_1} \text{sign}(\boldsymbol{w})$

The table below displays the results obtained for the $\ell_\infty$ norm. We conducted multiple $\ell_\infty$ attacks, namely FMN, FAB, and DF, on M1 [3] and M2 [6] adversarially trained networks on the CIFAR10 dataset. Our findings indicate that this variant of SDF also exhibits superior performance compared to other algorithms in discovering smaller $\ell_\infty$ perturbations.

We will add this result to the Appendix.

Some parts of the paper seem a bit disjoint/not relevant.

Adversarial training is more effective when conducted with strong, yet computationally efficient adversaries. Our proposed method is both fast and more accurate than the SotA in identifying adversarial perturbations, making it a logical choice for evaluating its effectiveness in enhancing the robustness of models through adversarial training.

The primary goal was to determine which adversarial generation technique improves robustness most effectively (PGD, DDN, or SDF), rather than comparing various adversarial training strategies (vanilla (Madry's) AT, TRADES, TRADES-AWP, etc.) Such approaches normally incorporate additional regularization techniques to improve Madry's method with PGD adversarial examples. Thus, our claim is not about developing a SotA robust model. Instead, our goal is to illustrate that vanilla AT, when coupled with minimum-norm attacks such as SDF, may yield better performance compared to PGD-based models. Therefore, we opted for vanilla adversarial training with SDF-generated samples and compared it to a network trained on DDN samples. Certainly, TRADES or similar AT strategies can be employed in conjunction with SDF, but we believe that falls beyond the scope of this paper.

Despite DDN AT already outperforms PGD AT, we have added PGD results for the sake of completeness.

Authors should also include comparison with some strong adversarial attacks...

We appreciate if the reviewer could clarify their point. From our understanding, C&W is a minimum-norm attack, and we have indeed included a comparison with it in our work. Once we fully grasp the specific type of comparison the reviewer is requesting, we will promptly provide it.