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

Experiments on L0-Robust Models. As requested, we expand our experiments to include the $\ell_0$ robust models sTRADES (denoted C11) and sAT (denoted with C12). Within the given time constraints, we decided to compare $\sigma$-zero with the most competitive attacks: FMN and BBadv for minimum-norm attacks, and Sparse-RS and Sparse-PGD for fixed-budget attacks. The camera-ready version will include results for the remaining (weaker) attacks, which we do not expect to significantly affect the following conclusions. Furthermore, for $\sigma$-zero we consider its default hyperparameters and a configuration using $\sigma=1$ (denoted with $\sigma$-zero*). We report our results in Table 6 (for minimum-norm attacks) and Table 10 (for fixed-budget attacks) in the revised manuscript. Overall, our findings indicate that $\ell_0$ gradient-based attacks (BB, Sparse-PGD, and $\sigma$-zero) require larger perturbations to break the model, demonstrating the model’s resistance to these attacks (as evidenced by poor ASR for fixed-budget attacks and large median $\tilde{\ell}_0$ values for minimum-norm attacks). Conversely, we observe that Sparse-RS and FMN perform better against these models. In particular, Sparse-RS, as a black-box attack, does not explicitly follow the gradient for minimizing $\ell_0$, while FMN optimizes adversarial examples in an $\ell_2$ direction (without using sparse projections on the gradient direction). These observations suggest that relying on the $\ell_0$ gradient direction (i.e. a sparsified gradient projection) when attacking these models can hinder the optimization of the attack, thus lowering its performance and leading to a false sense of security, while following a non-sparsified, dense gradient direction does not lead to the same problem. This observation is confirmed by the results obtained by $\sigma$-zero*, as using a larger value of the smoothing parameter $\sigma$ reduces sparsification of the gradient descent direction, overcoming the aforementioned issue. This adjustment effectively improves attack success rates against $\ell_0$ defenses (as shown in Tables 6 and 10, models C11 and C12). This flexibility highlights an advantage of $\sigma$-zero and suggests future strategies in which its smoothing parameter can be dynamically adjusted to overcome issues when attacking robust models against L0-norm attacks. We will add this discussion in the paper, and would like to thank the reviewer for requesting these additional experiments which unveiled a relevant aspect to further improve our strategy in this setting.

Experiments with N=10000 As requested, we include additional comparisons with fixed-budget attacks using 10,000 iterations. These experiments are performed on robust models from CIFAR-10 and ImageNet, with further results on the remaining models that will be included during camera-ready. The results, presented in Table 15 of the appendix in the revised manuscript, demonstrate that $\sigma$-zero continues to deliver outstanding performance, surpassing the state of the art. The updated results are thus consistent with our earlier findings, further supporting the robustness and reliability of our conclusions.

Minor Issues We thank the reviewer for the suggestion, we corrected the typo.

We appreciate that you found our contributions both interesting and easy to follow. We hope that the additional results and responses we have provided will prompt the reviewer to consider increasing their score. We are working to complete the additional requested experiments in the coming days to further demonstrate the robustness and quality of our work.

We thank the reviewer for their positive feedback on our work. We’re pleased that they found our contributions interesting and valuable. We hope the following changes will further strengthen our paper and encourage your support. Furthermore, we wish to inform the reviewer that we have extended our evaluation by integrating additional models to test $\sigma$-zero, further demonstrating its contributions to the state of the art. We now have a total of 22 models (originally they were 18) investigated in our experiments (i.e., 2 for MNIST, 12 for CIFAR-10, and 8 for ImageNet).

Move ablation study to the main paper. In accordance with the reviewer, we have revised the manuscript to include and discuss the ablation study in the main paper. We would like to clarify that the "Adaptive $\tau$” column refers to the capacity of $\sigma$-zero to make the projection adaptive with respect to the thresholding value $\tau$. As such, it is not possible to have the "Adaptive \tau” setting without the “Projection” column, or it would have the same effect as simply using normalization. Additionally, the role of the "Approximation" column (now renamed as $\hat{\ell_0}$) is to emphasize that relying solely on this approximation leads to suboptimal results in terms of the number of perturbed features. This helps highlight the importance of the full approach and contributions of this paper for achieving better performance.

Normalization coefficient. The scaling factor 1/d in Eq. 4 is used to keep the loss function within a 0 to 1 range, L0 can range from 0 to d, with d being the number of input features. From a design standpoint, it makes the loss function of our attack clearer to interpret by avoiding the usage of arbitrary soft-constraint weight terms.

Adversarial initialization. Interesting question. During the development of $\sigma$-zero, we experimented with initializing the attack similarly to BBadv. However, we did not observe significant improvements in performance. This is likely because, as demonstrated in our experiments, $\sigma$-zero can reach adversarial examples within a few iterations and then use the remaining iterations to minimize the number of manipulated features. ​​However, Initial investigations suggest that a promising research direction would be to create a synergy between attacks at different stages of their optimization process. Some attacks perform better in certain phases, such as exploration versus exploitation. For instance, FMN is even faster at initializing adversarial examples to good local solutions. This opens the possibility of developing an ensemble approach where methods like FMN quickly produce locally good adversarial examples, which could then be further refined using $\sigma$-zero to further reduce their number of manipulations. We will discuss this as a potential future extension of this work.

Minor Issues. We thank the reviewer for the helpful suggestions. We have corrected the typos in the paper and revised Table 4. The models are now listed in ascending order by their names in the Model column (e.g., from C1, C2, … to C10 for CIFAR-10).

I thank authors for their response to my questions. I do not have any outstanding concerns. I retain my positive rating and recommend acceptance.

We thank the reviewer for recognizing the value and contributions of our work.

Limited Innovation. We respectfully disagree with the reviewer. The main value of our proposal lies in the combination of all the components considered, which are listed below and acknowledged by other reviewers. Specifically, contributions are:

• Objective. The objective function in Eq. 6 is designed to induce an alternate optimization process between the logit loss and the L0-norm penalty, without introducing any hyperparameters. This is a novel contribution and avoids re-running the attack several times to tune the tradeoff hyperparameter, as done by EAD.
• L0-norm. The approximation has never been used to implement sparse attacks, which normally use the L1 norm to deal with convex projections, yielding suboptimal solutions (see, e.g., EAD). Our L0 approximation is non-convex, but it enables $\sigma$-zero to find sparser perturbations.
• Adaptive projection. Our non-naive adaptive projection operator is designed to promote sparsity in the solution, zeroing negligible components iteratively, and reducing the dependency on the choice of the initial step size. State-of-the-art performance. $\sigma$-zero significantly advances the state of the art for sparse attacks, as demonstrated in multiple experiments in the paper and the additional ones we provide in this rebuttal. As a consequence of that, $\sigma$-zero can work as a reliable tool for improving the robustness assessment of a target model against sparse attacks.

Lack of Theoretical Understanding and Analysis. We agree with the reviewer that adding theoretical insights may improve our work, and will point out this limitation in the paper, even if the same issue affects many other attacks (if not all) published in top-tier venues (e.g., Carlini and Wagner, 2017b; Brendel et al., 2019b; Croce et al., 2021; Pintor et al., 2021; Zhong et al., 2024). A theoretical study of all these algorithms, investigating consistency, convergence rates, etc. would certainly help the community gaining a better understanding of their inner workings, but considering the effort and skills required, we believe it should be investigated as additional follow-up work. Nevertheless, we firmly believe that our paper still provides significant contributions that advance the state of the art. Our attack establishes new state-of-the-art performances for sparse attacks, as shown by our extensive experiments, both in terms of efficacy and efficiency. The other attacks are either fast but suboptimal (e.g., FMN, EAD) or accurate but extremely slow (e.g., BB, BBadv). $\sigma$-zero is the only L0-norm attack that is both fast and accurate, thereby enabling a scalable and effective robustness evaluation against sparse attacks. This makes it a worthy contribution for a venue such as ICLR.

Limited Application Scope. We wish to clarify that our primary objective, as outlined in Section 2, is to present a minimum-norm attack for assessing model robustness in a white-box setting, a standard approach in the field (e.g., [Carlini and Wagner, 2017b; Brendel et al., 2019b; Croce et al., 2021; Pintor et al., 2021; Zhong et al., 2024]). We agree with the reviewer’s recommendation that analyzing transferability would be a valuable additional contribution to our work. However, we think that providing a detailed and fair transferability analysis of $\sigma$-zero will again require a large number of comparisons with the competing approaches, thereby requiring efforts that go beyond the scope of this work (i.e. the proposal of a novel L0 minimum-norm attack outperforming state-of-the-art, existing approaches). We will nevertheless acknowledge this as an interesting extension for future work, and will plan to study the transferability of sparse white-box gradient-based attacks more systematically, following e.g. the transferability analysis performed in [A].

[A] Demontis et al. Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks. USENIX security 2019.

We thank the reviewer for recognizing the value and contributions of our work.

Clarifications on memory usage and runtime. We revised the paper to include memory usage and mean runtime results for the fixed-budget attacks. We also changed the column names to specify that the number of queries shown in Tables 10-15 corresponds to the smallest budget k, as this setting typically results in the highest average query consumption.

Clearer comparisons with fixed-budget attacks. To address the reviewer's request, we provide additional robustness evaluation curves in Figure 5 (in the new Appendix) for fixed-budget attacks across 8 different values of k on robust model C3. In this evaluation, we run fixed-budget attacks with $N=1000$ (and $N=5000$) iterations for each $k$, and the results consistently demonstrate that $\sigma$-zero outperforms existing fixed-budget attacks at every perturbation size $k$. We will provide the robustness evaluation curves related to the other models for the camera ready. We hope this addition offers a clearer understanding of the performance of $\sigma$-zero against fixed-budget attacks, confirming that our algorithm significantly outperforms them both in efficacy and efficiency.

Transferability to other architectures We agree with the reviewer’s recommendation that analyzing transferability would be a valuable additional contribution to our work. However, we think that providing a detailed and fair transferability analysis of $\sigma$-zero will again require a large number of comparisons with the competing approaches, thereby requiring efforts that go beyond the scope of this work (i.e. the proposal of a novel L0 minimum-norm attack outperforming state-of-the-art, existing approaches). We will nevertheless acknowledge this as an interesting extension for future work, and will plan to study the transferability of sparse white-box gradient-based attacks more systematically, following e.g. the transferability analysis performed in [A].

[A] Demontis et al. Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks. USENIX security 2019.

Budget Inconsistencies Thank you for pointing this out. The difference in the reported budgets stems from the fact that ImageNet has significantly more features than the other two datasets, thus making the optimization problem more challenging to solve as the adversarial perturbations must navigate a higher-dimensional input space while maintaining effectiveness. Therefore, considering the perturbation levels used in previous work (e.g., Croce et al.), we set higher perturbation budgets for ImageNet to account for the increased complexity. In the final camera-ready version, we plan to include additional values of k for ImageNet, similar to the approach used for CIFAR-10, to provide a more consistent comparison across datasets.

Minor Writing Issues Lastly, we have also corrected the minor writing issues as suggested.

We will incorporate these updates in the final version of the manuscript, and hope that the reviewer will reconsider their evaluation.