$\sigma$-zero: Gradient-based Optimization of \\$\ell_0$-norm Adversarial Examples

We thank the reviewer for acknowledging the value of our contribution and its benefit to the community.

Writing style. We acknowledge the constructive criticism of the reviewer, and will improve our writing style by better highlighting the contributions and novelty of our work, as well as the reasons behind why the attack works well. Our purpose was genuinely to make our work reproducible, as also encouraged by the conference policy. This is why we reported too many results and technical details in the paper. However, we are committed to enhancing the paper's accessibility and will relocate the more technical details and results to the appendix.

sigma-zero results. We will improve the paper emphasizing the main contributions and condensing their descriptions in a well-identifiable paragraph in the paper. In particular, we posit that several factors contribute to the effectiveness of $\sigma$-zero, including the type of approximation used for the L0 norm, the novel loss formulation presented in Eq. 7, and the incorporation of gradient normalization in our optimization process. To elaborate further, we will clarify how the L0-norm approximation can enhance the effectiveness of our approach, offering a numerically stable method for minimizing L0 in adversarial perturbations. Additionally, we will detail the characteristics of the loss formulation introduced in Equation 7, explaining that it is carefully designed such that its solution corresponds to a minimum L0-norm perturbation. Finally, we will delve into the role of gradient normalization towards ensuring convergence during our optimization process.  

VRAM. We will also revise the paper to make clear that VRAM refers to Video Random Access Memory, and its role. Specifically, VRAM is a type of memory designed explicitly for use in graphics processing units (GPUs). In machine learning, GPUs have become increasingly important due to their parallel processing capabilities, making them well-suited for tasks involving large-scale mathematical computations, such as those found in machine learning algorithms.

We will add these considerations to the paper and would be happy to know if the reviewer has any other requests. We would appreciate a score increase from the reviewer if he/she finds our clarifications satisfactory. We remain available for further clarification.

We thank the reviewer for acknowledging the significant results sigma-zero offers over all the experimental settings we provide.

Additional comparison with BB. We have run additional experiments considering BB with adversarial initialization (BBadv), whose results are reported in our response to all reviewers (https://openreview.net/forum?id=dXRWP4n15q&noteId=JKLyN3Qnl9). These experiments further confirm the effectiveness of sigma-zero against competing attacks, in terms of ASR, perturbation size, and execution time. We also remark that, over five additional experimental configurations, only once BBadv finds slightly better results (i.e., 3 features less in median perturbation size). However, this improvement comes at the cost of a 12-fold increase in execution time, raising the computational complexity from 0.42 seconds per sample to 5.28 seconds. Furthermore, BBadv exploits an unfair initialization strategy compared to the other attacks, given that all the other ones start from the same source sample, and not from an adversarial region. We will add these experiments and considerations to the paper.

Comparison with Sparse-RS. We agree with the reviewer that SparseRS was tested in an unfair setting. We have thus re-run it using a sample-wise binary search on the perturbation budget, to efficiently find minimum-norm adversarial examples, as suggested in [S0], and as also detailed in the response to reviewer g7Nu (see Unfair comparison with Sparse-RS, https://openreview.net/forum?id=dXRWP4n15q&noteId=9oqEGzhkh4 ). Even under this configuration, $\sigma$-zero shows better results and computational efficiency. We’d finally like to remark also that SparseRS should not be seen as a direct competitor of gradient-based (white-box) attacks, including $\sigma$-zero, given its gradient-free (black-box) nature. We report it in our experiments as an additional, interesting baseline, and will clarify this aspect in the paper too. Note finally that the number of network passes (i.e. forwards and backwards) is already set to be the same between white-box and black-box attacks. This means that SparseRS is already performing twice the number of forward passes w.r.t. gradient-based attacks. We'll clarify this aspect in the paper.

[S0] Rony, Jérôme et al. “Augmented Lagrangian Adversarial Attacks.” 2021 IEEE/CVF International Conference on Computer Vision (ICCV).

Hyperparameter optimization. We agree in principle with the reviewer that optimizing the attack hyperparameters may be beneficial for some attacks. However, this is normally too costly and not considered in the majority of papers dealing with attack and defense evaluations (see, e.g., [S0, S1, S2, S3, S4, S5]). This is also why AutoPGD (and AutoAttack) algorithms are so popular, namely, they are parameter-free and work well with their default hyperparameter values. For this reason, we also consider here the same setting of using the default hyperparameter values reported in the original papers/implementations of each attack, and show that without any specific hyperparameter tuning, $\sigma$-zero turns out to be more effective. In this sense, we do believe that our comparison remains fair (namely, all attacks use default hyperparameters, and no computational overhead is spent in hyperparameter tuning).

[S1] Croce, Francesco and Matthias Hein. “Mind the box: l1-APGD for sparse adversarial attacks on image classifiers.” ICML.

[S2] Hajri, Hatem et al. “Stochastic sparse adversarial attacks. 2021 IEEE 33rd ICTAI.

[S3] Rony, Jérôme et al. “Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses.” 2019 IEEE CVPR.

[S4] Modas, Apostolos et al. “SparseFool: A Few Pixels Make a Big Difference.” 2019 IEEE/CVF CVPR.

[S5] Croce, Francesco and Matthias Hein. “Sparse and Imperceivable Adversarial Attacks.” 2019 IEEE/CVF ICCV.

Paper’s contributions. Finally, we apologize to the reviewer for not having highlighted our contributions well within the paper. Specifically, the loss term in Eq. 7 represents a novel contribution as it enables us to simultaneously search for an adversarial example while also minimizing the L0 norm of the perturbation (i.e., a non-trivial task given the non-convexity of this norm). Despite its simplicity, the approximation function used in Cinà et al. enables the implementation of a simple yet very fast and surprisingly effective attack, as witnessed by our extensive experimental analysis and acknowledged by the other reviewers. We thus firmly believe that the idea of leveraging such an approximation to develop a very effective L0-norm adversarial attack is not trivial.

We would appreciate a score increase from the reviewer if he/she finds our clarifications satisfactory. We remain available for further clarification.

Recall that PGD-L0 has 100 iterations by default, and that increasing the iterations of PGD-L0 and Sparse-RS for each k would then be unfair to minimum-norm attacks. However, if this is important, we can also include results with more iterations for these attacks too, or even better, compare ASR at fixed k, using the same number of iterations for sigma-zero, Sparse-RS, and PGD-L0. Despite this scenario being slightly unfair to sigma-zero, we are confident that sigma-zero will outperform the other attacks also in that configuration. Finally, we express again our sincere gratitude for your insights and feedback. We hope that we have provided convincing evidence that our attack works very well, especially post rebuttal, and that it can thus provide an additional, sound algorithm to help improve adversarial robustness evaluations in the L0 case.

We'll detail that aspect better in the paper, but we essentially followed the same mechanisms explained in [S0]. We imposed 400 and 100 number of steps respectively for Sparse-RS and PGD-$\ell_0$.

As depicted in Table 1 (column q), with these configurations, the two attacks execute approximately 2000 queries or more each. Consequently, they exploit, on average, the same number of queries compared to the other attacks, ensuring a fair comparison.

[S0] Rony, Jérôme et al. “Augmented Lagrangian Adversarial Attacks.” 2021 IEEE/CVF International Conference on Computer Vision (ICCV).

We appreciate the reviewer for their response.

Thresholding scheme. The main modification of the thresholding scheme aims to provide a sample-wise threshold tuning which drastically improved the performance with respect to having a fixed threshold equal for all samples.

Ablation study. The reported ablation study, as detailed in the appendix (refer to Figure 5), is not outdated. It has been updated to incorporate the updated version of our attack including the new thresholding scheme. We demonstrate that the initial value selection for the thresholding parameter, denoted as $\tau$, has negligible influence on the outcome, given that the parameter dynamically adapts throughout the optimization process.

Binary Search. Regarding binary search, yes, the iteration budget is split across different perturbation sizes.

We thank the reviewer for acknowledging the simplicity and effectiveness of our proposed attack, and reply to their concerns below.  

Visually-imperceptible Adversarial Examples. We aim to clarify with the reviewer that visual imperceptibility of adversarial examples is considered now a known misconception [S0,S1]. In fact, as highlighted by the examples reported in [S0,S1], including image spam and visibly-modified traffic signs, the perturbations are clearly visible to the human eye (even though the main content is still preserved), as their sole purpose is to evade automatic detection. In addition, quoting Justin Gilmer et al. [S0]: “at the time of writing, we were unable to find a compelling example that required indistinguishability.” Recall indeed that indistinguishability is a much stricter requirement than just preserving the main content (e.g., the ability of humans to still recognize the correct object in the image). This is also consistent with the definition of adversarial example given by Ian Goodfellow, which does not even mention the requirement of visual indistinguishability: “Adversarial examples are inputs to machine learning models that an attacker has intentionally designed to cause the model to make a mistake”. Accordingly, we can say that the goal of an adversarial example is simply to fool the machine-learning model, and not necessarily be imperceptible to the human eye. This is especially true for sparse (L0 and L1) attacks, as they are constrained to only manipulate a few input values, but it is also an issue that affects all previous work related to sparse attacks, not just ours [S2, S3, S4, S5]. In fact, by inspecting the attacks proposed in previous work, it is not difficult to see that L0 and L1 adversarial perturbations are always clearly visually distinguishable (see, e.g., Figure 3 in our paper). Their goal, indeed, is not to be indistinguishable to the human eye, but rather show whether and to which extent models can be fooled by just changing a few input values -- i.e., to evaluate their adversarial robustness against sparse perturbations. We hope that the reviewer agrees with this perspective and, if necessary, we will take this opportunity to clarify this aspect in the paper too.

[S0] J. Gilmer, R. P. Adams, I. J. Goodfellow, D. Andersen, and G. E. Dahl. Motivating the rules of the game for adversarial example research. CoRR, abs/1807.06732, 2018.

[S1] Biggio, Battista and Fabio Roli. “Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning.” Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (2017).

[S2] Croce, Francesco and Matthias Hein. “Mind the box: l1-APGD for sparse adversarial attacks on image classifiers.” International Conference on Machine Learning.

[S3] Modas, Apostolos et al. “SparseFool: A Few Pixels Make a Big Difference.” 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).

[S4] Croce, Francesco et al. “Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks.” AAAI Conference on Artificial Intelligence (2020).

[S5] Su, Jiawei et al. “One Pixel Attack for Fooling Deep Neural Networks.” IEEE Transactions on Evolutionary Computation 23 (2017).

Robust Models. As suggested by reviewer g7Nu, we now have integrated two more models trained to be robust against sparse attacks [S6, S7]. The results have been reported above in our response to all reviewers (https://openreview.net/forum?id=dXRWP4n15q&noteId=JKLyN3Qnl9). Even against such robust models, $\sigma$-zero continues to outperform existing attacks, exhibiting higher attack success rates, lower distances, and faster execution. We will add these experiments and considerations to the paper and would be happy to know if the reviewer has any other requests.

[S6] Croce, Francesco, and Matthias Hein. "Mind the box: -APGD for sparse adversarial attacks on image classifiers." International Conference on Machine Learning. PMLR, 2021.

[S7] Jiang, Yulun, et al. "Towards Stable and Efficient Adversarial Training against Bounded Adversarial Attacks." International Conference on Machine Learning. PMLR, 2023.  

We would appreciate a score increase from the reviewer if he/she finds our clarifications satisfactory. We remain available for further clarification.

Thanks the authors for your feedback. I do not agree with your point of the unnecessity of maintaining visual imperceptibility of adversarial examples. If it happens, why you need to minimize the $\ell_0$ of the perturbation. If we relieve such constraints, we can easily find the adversarial examples with attack successful rate 100%. It would be more convincing to me if the authors can give a practical scenario of using the easily human-recognized adversarial examples. Moreover, it would be better if the paper reports some other metrics such as SSIM, PSNR, and LPIPS. I am leaning to keep my current score.

We have been able to run some more additional experiments, reported in the supplementary material (see comparison_SSIM_PSNR.pdf), where we computed SSIM and PSNR measures for different examples. Note that only EAD exhibits marginally superior values w.r.t. the other attacks, given that it works using a slightly different perturbation model.

The proposed $\sigma$-zero attack instead achieves very high SSIM and PSNR, outperforming or remaining comparable to the other $\ell_0$-norm attacks.

Let us finally thank again the reviewer for giving us the opportunity to improve our work. We hope that this last evaluation will convince the reviewer that our attack is valuable and that it can improve our current understanding of adversarial robustness against sparse, $\ell_0$-norm attacks.

We thank the reviewer for acknowledging credit for our contribution and its clarity, and reply to their concerns below.

Additional attacks and robust models. We have run additional experiments considering the additional attacks PGD-L0 [A] and Sparsefool [B], and the L1-norm robust models [C] and [D], as suggested by the reviewer. We report the results in our response to all reviewers (https://openreview.net/forum?id=dXRWP4n15q&noteId=JKLyN3Qnl9), showing that $\sigma$-zero outperforms such attacks on the suggested robust models as well as on the other CIFAR10 models from our paper. We will add these results to the revised paper, as well as the comparisons on the remaining models we used in the paper (which will take some more time to execute). With these additional results, our work will include more than 320 diverse dataset-model-attack configurations, which we believe should provide sufficient convincing empirical evidence that our attack achieves state-of-the-art performance.

Unfair comparison with Sparse-RS. We agree with the reviewer that comparing minimum-norm attacks against maximum-confidence attacks (i.e., attacks that optimize the loss within a maximum perturbation budget, like PGD-L0 and Sparse-RS) may be tricky. In particular, minimum-norm attacks are typically more complicated as they require not only finding an adversarial example, but also the minimum perturbation budget required to do that (i.e., they optimize both the loss and the perturbation size, not only the loss). To compare these two types of attack in a fair manner, we have re-run our experiments by performing a binary search on the perturbation budget of each sample when using maximum-confidence attacks (rather than doing that per batch), as also suggested in [S1]. In addition, we do not only report the median distance (i.e., the distance that corresponds to an ASR of 50%), but also the ASR at a fixed budget with eps=10 and eps=50, as typically done when evaluating maximum-confidence attacks. Given that we re-evaluated Sparse-RS within this setting, we decided to remove the two redundant SparseRS versions achieving different ASRs (85% and 100%, respectively).

Loss gradient. Regarding Eq 7, we agree with the reviewer that using a sigmoid-like function instead of a step function may be more appropriate. We have however seen in practice that this never induces numerical instabilities on the gradient even on the 18 models we consider in our experimental analysis. We will clarify this point within the paper, after Eq. 7.

Superscripts in Sparse-RS. First, let us point out that comparing against Sparse-RS is only meant to provide an additional baseline, but it should not be considered a direct competitor of gradient-based (white-box) attacks, given that Sparse-RS is a gradient-free (black-box) attack (working under stricter assumptions). As explained before, the superscripts in Sparse-RS were not referred to the perturbation budget, but to the ASR. This means that the perturbation budget of Sparse-RS^85 and Sparse-RS^100 was tuned to respectively achieve an ASR of 85% and 100%. However, given that we now tune the perturbation budget in a sample-wise manner to find minimum-norm adversarial examples also for SparseRS, we decided to remove these two (confusing) versions of SparseRS from our evaluation.

We would appreciate a score increase from the reviewer if he/she finds our clarifications satisfactory. We remain available for further clarification.