SuperDeepFool: a new fast and accurate minimal adversarial attack

$**General comment:**$

We 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.

$**Focus on$\ell_{2** perturbations}.

Given 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 $`"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.

$**The proposed method builds upon DeepFool, Novelty**$.

Given the 6,000-character constraint for this response and the substantial overlap between this section and the "Novelty" section addressed for the $`"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.

$**Develop efficient black-box attacks.**$

We 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. As mentioned in our paper, the strategy employed by SDF approximating the decision boundary and finding minimal perturbations 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. 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. In 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.

$**Realistic and practical scenarios**.$

We 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:

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.

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.

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.

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].

Jailbreaking LLMs: Jailbreaking 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.

Furthermore, 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. We 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.

[A]: Tramèr, The space of transferable adversarial examples. arXiv preprint.

[B]: Moosavi-Dezfooli, Universal adversarial perturbations. CVPR 2017

[C]: Andriushchenko, M., Jailbreaking leading safety-aligned llms with simple adaptive attacks. ICML 2024 Workshop on the Next Generation of AI Safety

$**General comment:**$

We 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.

$**Clarity Issues$\rightarrow$notations**:$

Thank 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.

$**Novelty:**$

Thank you for your insightful suggestion. In $`lines 210-215`$ of the $`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.

SuperDeepFool 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. SuperDeepFool reimagines the approach to adversarial perturbations through several key innovations:

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.

$**Key Insight:**$

Broadly speaking, the approaches that employ geometrical characterization of deep neural networks can be categorized into white-box and black-box settings:

1. White-box Settings:

   • 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 ($`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]}).

2. Black-box Settings:

   • GeoDa [43] and qFool [2] aim to iteratively approximate the classifier's gradient with minimal query usage.

The 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.

$**A discussion of limitation is not found in the paper.**$

Our 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.

References:

[1]: Modas, A., Moosavi-Dezfooli, S., and Frossard, P. Sparsefool: a few pixels make a big difference. In CVPR, 2019.

[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).

[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.

[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.

[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.

$**General comment**$:

We 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.

$**The method is limited to$\ell_{2** norm}.

First, 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. As we discussed in $`lines 91 to 102`$ of the $`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. It should be noted that the focus of our paper, as stated in the abstract, is on minimal $\ell_{2}$ norm perturbations. Nevertheless, we tried a $\ell_{\infty}$ version of SDF by replacing the $*orthogonal projection*$ with the $\ell_{\infty}$ projection (Holder's inequality). The table in $`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.

$**Do we expect similar performance for smaller$\varepsilon$, e.g. 8/255?**$ (Most of the experiments are conducted with $\varepsilon=0.5$).

First, 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. For 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.

$\varepsilon = 0.3$ for $\ell_{2}$ on CIFAR-10 result is presented in attached rebuttal pdf.

Comparison between our AT model and $\textcolor{blue}{[47]}$ beyond other $\varepsilon$ :

We presented these results in $`line 363`$ of the main text and Tables 12 and 13 of the $`appendix`$ for both the $\ell_{\infty}$ and $\ell_{2}$ versions of AA across a wide range of $\varepsilon$ values.

$**How do we determine the number of iterations in SDF beforehand?**$

It 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. Although the iteration-free property of an algorithm can enhance its convergence speed, a critical question arises: $*“When the algorithm terminates upon finding the adversarial point, how can we **ensure** that this adversarial point is optimal?”*$ This is one of the key criticisms that can be raised against DeepFool. As demonstrated in $`Figure 3 (Left)`$ of the main paper, DeepFool's perturbations are not optimal and tend to be overly perturbed (extrapolated). To 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 $`Figure~3(Right)`$ of the main paper, line search $*alone*$ cannot resolve the issue of orthogonality.

$**Is the case SDF(m,$\infty$) also interesting?**$

We 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.

$**General comment:**$

We really appreciate the reviewer’s enthusiasm and acknowledgment of the significance of our work. We address the reviewer's concerns below.

$**Optimality Measurements:**$

Firstly, 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. Figure 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: Firstly, by adding a line search to the end of DF, we optimize and compare the results of $`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: Adversarial 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.

$**Comparison Tables:**$

To 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. It 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.

$**Elaborate on evaluated networks**$:

It is important to mention that the procedure of "Vanilla Adversarial Training" is explained in Appendix O of the main paper (lines 864 to 875).

Why is an adversarially trained (AT) model with strong minimum-norm attacks like SDF robust to others?

AT 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. The results are displayed in Table (6) of the main paper.

$**The perturbation size of 2.6**.$

The 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.

$**AA Comparison:**$

It is important to note that APGD is not considered a minimum-norm attack but instead considered a norm-bounded attack. The 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. In 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.