$\sigma$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples
Authors: Antonio Emanuele Cinà
Francesco Villani
Maura Pintor
Lea Schönherr
Battista Biggio
Marcello Pelillo
Venue: ICLR 2025 Poster (2025)
Keywords: adversarial examples
sparse attacks
gradient-based attack
machine learning security
evasion attacks
sparse optimization
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: The $\sigma$-zero attack uses a differentiable approximation of the $\ell_0$ norm for gradient-based optimization, with an adaptive projection operator that balances loss minimization and perturbation sparsity.

Abstract: Evaluating the adversarial robustness of deep networks to gradient-based attacks is challenging.
While most attacks consider $\ell_2$- and $\ell_\infty$-norm constraints to craft input perturbations, only a few investigate sparse $\ell_1$- and $\ell_0$-norm attacks.
In particular, $\ell_0$-norm attacks remain the least studied due to the inherent complexity of optimizing over a non-convex and non-differentiable constraint.
However, evaluating adversarial robustness under these attacks could reveal weaknesses otherwise left untested with more conventional $\ell_2$- and $\ell_\infty$-norm attacks.
In this work, we propose a novel $\ell_0$-norm attack, called $\sigma$-zero, which leverages a differentiable approximation of the $\ell_0$ norm to facilitate gradient-based optimization, and an adaptive projection operator to dynamically adjust the trade-off between loss minimization and perturbation sparsity.
Extensive evaluations using MNIST, CIFAR10, and ImageNet datasets, involving robust and non-robust models, show that $\sigma$-zero finds minimum $\ell_0$-norm adversarial examples without requiring any time-consuming hyperparameter tuning, and that it outperforms all competing sparse attacks in terms of success rate, perturbation size, and efficiency.

Published as a conference paper at ICLR 2025
O-ZERO: GRADIENT-BASED OPTIMIZATION OF lo-NORM ADVERSARIAL EXAMPLES
Antonio Emanuele Cinà
Francesco Villani!
Maura Pintor
Lea Schönherr
Battista Biggio?
Marcello Pelillo*
"Department of Computer Science, Bioengineering, Robotics and Systems, University of Genoa, Italy Deparrment of Electrical and Electronic Engineering, University of Cagliari, Italy
ACISPA Helmholtz Center for Information Security, Germany
*Department of Environmental Sciences, Informatics and Statistics, Ca' Foscari University Venice, Italy
antenic. cina@unige. it francesco, vi 1anni @edu unige. it maura, caura.pintor pintor wenoorrunnc.... Schoenherr@ciee rea.ee.dde
battista. sertiistabiiggiie www.giiuiiiii.....ooooo pelillo@unive.25
ABSTRACT
Evaluating the adversarial robustness of deep networks to gradient- crasee attacks is challenging. While most attacks consider é2- and & nnrm constraints to craft input perturbations, only a few investigate sparse f and fo-norm attacks. In particular, fo-norm attacks remain the least studied due to the inherent complex- ity of optimizing over a non-convex and non-differemtiable constraint. However, evaluating adversarial robustness under these attacks could reveal weaknesses otherwise left untested with more conventional fz- and -nom attacks. In this work, we propose novel tg fn-norm attack, called a-zero, which leverages a dif- ferentiable approximation of the lg norm facilitate gradient- maseent-based optimization, and an adaptive projection operator to dynamically adjust the trade-off between loss minimization and perturbation sparsity. Extensive evaluations using MNIST, CIFARIO, and ImageNet datasets. involving robust and non-robust models, show that a oo-eer zero finds minimum εg-norm adversarial examples without requiring any time-consuming hyperparameter tuning, and that it outperforms all competing sparse attacks in terms of success rate, perturbation size, and efficiency.
INTRODUCTION
Early research has revealed that machine learning models are fooled by adversarial examples, i... slightly-perturbed inputs optimized to cause misclassifications (Biggio et al.] 2013); Szegedy et al.
2014). The discovery of this phenomenon has, in turn, demanded
careful evaluation of
the robustness of such models, especially when deployed in security-sensitive and safety-critical applications. Most of the gradient-based attacks proposed evaluate the adversarial robustness of Deep Neural Networks (DNNs) optimize adversarial examples under different L, -ooor constraints. In particular, while convex ε,, l2, and fo norms have been widely studied (Chen et al., 2018 Croce & Hein (021), only few fo-norm attacks have been considered to date. The main reason is that finding minimum fn-norm solutions is known to an NP-hard problem (Davis et al., 1997). and thus ad-hoe approximations must be adopted to overcome issues related to the non-convexity and non-diffcreniiabiiiyy of such (pseudo) norm. Although this a challenging task, attacks based on the to norm have the potential to uncover issues in DNNs that may not be evident when considering other attacks (Carlini & Wagner 2017b) Croce & Hein 2021). In particular, fn-norm attacks, known to perturb minimal fraction of input values, can be used determine the most sensitive characteristies that influence the model's 's decision- making process, offering a different and relevant threat model to benchmark existing defenses and different understanding of the model's inner workings.
Unfortunately, current fn-ormm attacks exhibit a largely suboptimal trade-off between their success rate and efficiency, i.e., they either accurate but slow or fast but inaccurate. In particular, the accurate ones use complex projections and advanced initialization strategies (e.g., adversarial
Code available https::///tt wtw.ggittuu..ee hww.hh.o.oooo..ccoooooooc.ooh.oo gma0-aávx giga- gma zero.

---

Published as a conference paper at ICLR 2025
Frog Frog 2o:2813
Fog - Chameleon fo:1381
Frog. Chameleon 4g:52
Figure I: The leftmost plot shows the exccution of a- z-zero two-dimensional problem. The initial point x (red dot) is updated via gradient descent to find the adversarial example x* (green star) while minimizing the number of perturbed features (i.e., the to norm of the perturbation). The gray lines surrounding x demarcate regions where the lo norm is minimized. The rightmost plot shows the adversarial images (top row) and the corresponding perturbations (bottom row) found by ø-zero during the three steps highlighted in the leftmost plot, along with their prediction and lo norm.
initialization) to find smaller input perturbations but suffer from time or memory limitations, hindering their scalability to larger networks or high-dimensional data (Brendel et al. 2019a Césaire al.
2021). Other attacks execute faster, but their returned solution is typically less accurate and largely suboptimal (Matyasko & Chau 2021 Pintor al. 202T This results in overestimating adversarial robustness and, in turn, contributes to spreading a false sense of security, hindering the development of effective defense mechanisms (Carlimi et al. 2019; Pintor al. 2022). Developing reliable, scalable, and compelling method to assess the robustness of DNN models against sparse perturbations
with minimum to norm remains thus relevant and challenging open problem.
In this work, we propose a novel fo-norm attack, named d-zero, which iteratively promotes the sparsity of the adversarial perturbation by minimizing its norm (see Figure I and Secc.. 2p. To over- come the limitations of previous approaches, our attack leverages two main technical contributions: (i) a smooth, differentiable approximation of the tu norm enable the minimization of the attack loss via gradient descent; and (ii) an adaptive projection operator that dynamically increases sparsity further reduce the perturbation size while keeping the perturbed sample in the adversarial region.
Our experiments (Sect. 3) provide compelling evidence of the remarkable performance of o a-zero. We evaluate on well- benchmark datasets (i.e., MNIST, CIFARIO, IO, and ImageNet), using 22 different models from Robustbench (Croce et al. 2021) and the corresponding official repositories. We compare the performance of a zero against more than 10 competing attacks, totaling almost 450 different comparisons. Our analysis shows that a zero outperforms wate-of-the-art attacks in terms of both attack success rate and perturbation size (lower tu norm), while being also significantly faster (i.e., requiring fewer queries and lower runtime). Our attack also provides some additional advantages: (i) it does not require any sophisticated, time-consuming hyperparameter tuning: (ii) it does not require being initialized from adversarial input; (iii) it is less likely to fail, i.e., consistently achieves an attack success rate of 100% for sufficiently-largy thereby enabling more reliable robustness evaluations (Carlimi al. 2019). We thus believe that a -ezero will foster significant advancements in the development of better robustness evaluation tools and more robust models against sparse attacks. We conclude the paper by discussing related work (Sect. 4), along with the main contributions and future research directions SSect. 5)
perturbation budgets,
O-ZERO: MINIMUM 40 NORM ATTACKS
We present here a- zero, a pradient-based attack that finds minimum fn-norm adversarial examples.
Threat Model. We assume that the attacker has complete access to the target model, including its architecture and trained parameters, and exploits its gradient for staging white-box untargeted attacks (Carlini & Wagner 20176; Biggio & Roli 2018). This setting is useful for worst-case evaluation of the adversarial robustness of DNNs, providing an empirical assessment of the perfor- mance degradation that may be incurred under attack. Note that this is the standard setting adopted
2

---

Published as a conference paper at ICLR 2025
in previous work for gradient- based adversarial robustness evaluations (Carlini & Wagner 2017b Brendel et al. 2019b Croce et al. 2021: Pintor et al. 2021
Problem Formulation. In this work, we seek untargeted minimum fo-norm adversarial perturbations that steer the model's decision towards misclassification (Carlini & Wagner 2017b). To this end, let X [0, 1] be ddddimensional input sample, y E)' [I....,4] ] its associated true label, and f x e + y the target model, parameterized by 0 E Q. While f outputs the predicted label, we will also use fs. to denote the continuous-valle valued output (logit) for class k V The goal of our attack is to find the minimum fo-norm adversarial perturbation 8 such that the corresponding adversarial example =x+ 8" is misclassified by f. This can be formalized as:
8" E arg min ||0|0:
s.t. f(x 5,0)
(2)
x [0.1]
where ||. Ilo denotes the to norm, which counts the number of non-zero components. The hard constraint in Eq. 2 ensures that the perturbation 8 is valid only the target model ff misclassifies the perturbed sample x + 8, while the box constraint in Eq. (3) ensures that the perturbed sample lies in [0, 1] Since the problem in Eqs.
can not be solved directly, we reformulate it as:
8 E arg min
C(x + 5,
d ()(
(4)
s.t. x x+ E [0, 1j.
(5)
where use differentiable approximation (5) instead of ||0| |0l and normalize it with respect to the number of features d to ensure that its value is within the interval [0, 1]. The loss L is defined as:
[(x, y, 0) max [x((x)) max fa 0).0) - [([((x,)) = y) kEy
The first term in L represents the logit difference, which is positive when the sample is correctly assigned to the true class y. and clipped to zero when it is misclassified (Carlimi & Wagner, 20176). The second term merely adds 1 to the loss if the sample is correctly classified D This ensures that == 0 only when an adversarial example is found and L 2 1 otherwise. In practice, when minimizing the objective in Eq. (4). this loss term induces an alternate optimization process between minimizing the loss function itself (to find an adversarial example) and minimizing the éy-norm of the adversarial perturbation (when an adversarial example is found). It is also worth remarking that, conversely to the objective function proposed by Carlini & Wagner (017b), our objective does not require tuning any trade-off hyperparameters to balance between minimizing the loss and reducing the perturbation size, thereby avoiding computationally expensive line search for each input sample.
fo-norm Approximation. Besides the formalization of the attack objective, one the main technical advantages of a zero is the smooth, differentiable approximation of the to norm, thereby enabling the use of gradient- based optimization. To this end, we first note that the 4n-nrmm of a vector can be rewritten as ||x||o Ein sign(z.)²² and then approximate the sign function as sign(z.) s I./ Vaz ao, where > 0 is smoothing hyperparameter that makes the approximation sharper as a + This, in turn, yields the following smooth approximation of the En norm:
(o(x, 0) = + > 0, (o(x, E [0.]]
Adaptive Projection IT.. The considered fo-nrrm approximation allows optimizing Eq. via gradient descent. However, using such a smooth approximation tends to promote solutions that are not fully sparse, i.c., with many components that are very close zero but not exactly equal zero, thereby yielding inflated fo-norm values. To overcome this issue, we introduce an adaptive projection operator II, that sets to zero the components with a perturbation intensity lower than a given sparsity
Note that, when the source point x already misclassified by f. the solution is simply 5* 0.
"While sigmoid approximation may be adopted to overcome the non conddiferentiabilityy of the term at the decision boundary, we simply its gradient zero everywhere, without any impact the experimental results.
3

---

Published as a conference paper at ICLR 2025
Algorithm 1 o zero Attack Algorithm.
Input: x E [0, the input sample; y. the true class label; 0, the target model; N, the number of
iterations; 77 = 1.0, the initial step size: 10-3 33 the fo-norm smoothing hyperparameter,
= 0.3, the initial sparsity threshold: t = 0.01, the sparsity threshold adjustment factor.
Output: x", the minimum fo-norm adversarial example.
8 <- 0: 8* <- oc;
- 7o
2 for in ......NN do
3
Vg t Vo[C(x 6, y, 8) [)((6,0)]
Gradient Descent for Eq. 0 P Gradient Normalization. > Box Constraints.
4
Vg f Vg/ Vg
ô < clip(x 17 Vgl)
Adaptive Projection Operator.
7= crosine_annealine
i)
> Learning Rate Decay. b Adaptive Adjustment for т.
if i + 0,
< 0: = ----- else -- =1
if 8,
I 0
A
16%
< 8 0: 8" t
10 end
L(x 8" ,y,
0: 8
return 6x+0
threshold in each iteration. The sparsity threshold is initialized with a starting value To and then dynamically adjusted for each sample during each iteration; in particular, it is increased to find sparser perturbations when the current sample is already adversarial, while it is decreased otherwise. The updates to are proportional to the step size and follow its annealing strategy, as detailed below.
Solution A Algorithm. Our attack, given as Algorithm solves the problem in Eqs. and memory-efficient gradient-based optimization. After initializing the adversarial perturbation = 0 Line I). it computes the gradient of the objective in Eq. (4) with respect to glnn 3). The gradient is then normalized such that its largest components (in absolute value) equal =1 [ine 4).
via a fast
This stabilizes the optimization by making the update independent from the gradient size, and also makes the selection of the step size independent from the input dimensionality (Rony al. 2018
Pintor et al. 2021). We then update to minimize the objective via gradient descent while also enforcing the box constraints in Eq. 55) through the usage of the cl ip operator dline 5). We increase sparsity in by zeroing all components lower than the current sparsity threshold <line 6). as discussed the previous paragraph. We then decrease the step size 7) via cosine annealing (line 7) as suggested by Rony et al. (218);; Pintor et al. (222I) and adjust the sparsity threshold т accordingly (Tine 8). In particular, if the current sample is adversarial, we increase by 1 to promote sparser perturbations; otherwise, we decrease by the same amount to promote the minimization of L. The above process is repeated for N iterations while keeping track of the best solution found, i.e., the adversarial perturbation 8* with the lowest to norm (lie 9). If no adversarial example is found, the algorithm sets 8* = xo (line 11). It terminates by returning x = x + 8
(line 12).
Remarks. To summarize, the main contributions behind r-zero are: (i) the use of a smooth fo-nomm approximation, along with the definition of an appropriate objective (Eq. 4. to enable optimizing fo formorm adversarial examples via gradient descent; and (ii) the introduction of adaptive projection operator to further improve sparsity during the optimization. Our algorithm leverages also common strategies like gradient normalization and step size annealing to speed up convergence. As reported by our experiments, a zero provides a more effective and efficient fo-norm attack that (i) is robust different hyperparameter choices; (ii) does not require any adversarial initialization: and (iii) enables more reliable robustness evaluations, being able to find adversarial examples also when the competing attacks may fail (Carlini al. 2019
Pintor et al. 2022
EXPERIMENTS
We report here extensive experimental evaluation comparing z-zero against 11 state-of-the of-ee----hrerr sparse attacks, including both bo- and é nnom attacks. We test all attacks using different settings on 18 distinct models and 3 different datasets, yielding almost 450 different comparisons in total.
4

---

Published as a conference paper at ICLR 2025
3.1 EXPERIMENTAL SETUP
Datasets. We consider the three most popular datasets used for benchmarking adversarial robustness: MNIST (eCunn & Cortes, 2005), CIFAR-10 (Krizhevsky 2009) and ImageNet (Krizhevsky et al. 2012). To evaluate the attack performance, we use the entire test set for MNIST and CIFAR-10 (with batch size of 32), and subset of 1000 test samples for ImageNet (with batch size of 16).
Models. We use a selection of both baseline and robust models to evaluate the attacks under different conditions. We evaluate o-zers ro vast of models ensure its broad effectiveness and expose vulnerabilities that may not be revealed by other attacks (Croce & Hein (02T). For the MNIST dataset, we consider two adversarially trained convolutional neural network (CNN) models by Rony jet al. (2021), i.e., CNN-DDN and CNN-Trades. These models have been trained to be robust to both lg and Loo adversarial attacks. We denote them MI and M2, respectively. For the CIFAR- 10 and ImageNet datasets, we employ state-of-the of--te--rrr--- art robust models from RobustBench (Croce et al. 202T) and the paper's official repositories. For CIFAR-10. 10, we adopt ten models, denoted as CI-C12. CI (Carmon et al. 2019) and C2 (Augustin et al. 2020) combine training data augmentation with adversarial training to improve robustness to fo and & attacks. C3 (Croce & Hein| 2021) and
C4 TTaag et al. 2023) are & robust models. C5 (Croce et al. 2021 is non-robust NedeResNet-
28-10 model. C6 (Gowal et al. 202I) uses generative models to artificially augment the original training set and improve adversarial robustness generic ly-norm attacks. C7 (Engstrom et al. 2019) is an adversarially trained model that is robust against fg-norm attacks. C8 (Chen et al. 20200 is
robust ensemble model. C9 (Xu et al., 2023) is recently proposed adversarial training defense robust to & attacks. C1O (Addepalli et al. (022) enforces diversity during data augmentation and
combines with adversarial training. Lastly, CIT Zhong al. 2024 and C12 (Zhong al.) 2024
are two adversarially trained models robust against tu no-norm adversarial perturbations. For ImageNet, we consider a pretrained ResNet-11 denoted with 11 (He et al.) 2015). and five robust models to lo -attacckss denoted with 12 (Engstrom et al. 2019). 13 (Hendrycks et al. 2021), 14 (Debenedetti
et al. 2023), [Wong et al. (020), and 16 Salman et al.
2020). Lastly, the appendix, we present two 6- robrotstt models, C11 (Zhngg et al. 2024) and C12 ZZong et al. (024)) for CIFAR-10, along
with two large robust models, 17 (Peng et al. 2023) and 18 (Mo et al. 2022), for ImageNet.
Attacks. We compare o o-zero against the following state-of-the-art minimum-norm attacks, in their f--nrrm variants: the Voting Folded Gaussian Attack (VFGA) attack (Césaire et al., [202]) the Primal-Dual Proximal Gradient Descent (PDPGD) attack (Matyasko & Chau (2021). the Brendel & Bethge (BB) attack (Brendel et al. 2019a). including also its variant with ad adversarial initialization and the Fast Minimum Norm (FMN) attack (Pintor et al. 2021). We also consider two state-of-the-art & nnoom attacks as additional baselines, i.e., the Elastic-Net (EAD) attack (Chen et al. 2018) and SparseFool (SF) by Modas et al. 2019). All attacks are set to manipulate the input values independently; e.g., for CIFAR-10, the number of modifiable inputs is 3 x 32 x 32 3072.
(BBadv) and
Hyperparameters. We run our experiments using the default hyperparameters from the original implementations provided in the authors' repositories. AdversarialLib (Rony & Ben Ayed) and Foolbox (Rauber al.) 2017). We set the maximum number of iterations to N 1000 ensure that all attacks reach convergence (Pintor et al. 2022 For a-zero, we set 7o and Ø = 10-3 3 and keep the same configuration for all models and datasets
1, To = 0.3, = 0.01,
Evaluation Metrics. For each attack, we report the Attack Success Rate (ASR) at different values of k. denoted with ASR,, i.e., the fraction of successful attacks for which ||0* llo S k. and the median value of || 8 loo over the test samples, denoted with Eo We compare the computational effort cach attack considering the mean runtime (s) (per sample), the mean number of queries (q) (i.e., the total number of forwards and backwards required to perform the attack, divided by the number of samples), and the Video Random Access Memory (VRAM) consumed by the Graphics Processing Unit (GPU). We measure the runtime on workstation with an NVIDIA A 100 Tensor Core GPU (40 GB memory) and two o X Gold 6238R processors. We evaluate memory consumption as the maximum VRAM used among all batches, representing the minimum requirement to run without failure.
'We utilize the Foolbox DatasetAttack Foolbox 2017 for adversarial initialization.
AAdittiona results using only N- 100 steps are reported in Appendix B.1
"To show that no specific hyperparameter tuning is required, additional results are reported in Appendix A.2 'If no adversarial example is found for given x, we set | = oc, done by Brendel al. 2019a).
5

---

Published as a conference paper at ICLR 2025
Table I: Minimum-norm comparison results on MNIST, CIFARIO and ImageNet with N For each attack and model (M), we report ASR runtime 8 (in seconds), mean number of queries (in thousands), and maximum VRAM usage (in
1000.
24, 50, co, median perturbation size lq. mean
GB). When VFGA exceeds the VRAM limit, we re-run it using a smaller batch size, increasing its
runtime L. We denote those cases with the symbol 'x'. Remaining models in Appendix B Table 6
Attack M 2 ASR50 A
to
s
q
VRAM ASR ASR ^
E
q
VRAM
MNIST
SF
6.66
6,76
96.98
469
1.07
0.18
0.06
1.03
1.21
91.68
463
2.87
0.86
0.07
EAD
3.83
53.66
100.0
49
0.47
6.28
0.05
2.13
55.57
100.0
48
0.50
6.73
0.05
PDPGD
26.77
74.08
100.0
38
0.23
2.00
0.04
16.91
66.30
100.0
2.00
0.04
VFGA
43.58
82.42
99.98
27
0.05
0.77
0.21
5.00
39.33
99.95
0.05
1.33
0.21
M7
M2
FMN
35.90
93.74
100.0
29
0.21
2.00
0.04
50.74
91.84
99.41
24
0.22
2.00
0.04
BB
71.23
97.86
100.0
18
0.90
2.99
0.05
56.53
91.62
100.0
18
0.74
3.71
0.05
BBadv
67.06
91.23
100.0
19
0.77
2.01
0.07
29.17
40.88
100.0
89
0.71
2.01
0,07
0- zero
83.79
99.98
100.0
16
0.31
2.00
0.04
98.03
100.0
100.0
9
0.31
2.00
0.04
CIFAR-10
SF
18.71
18.77
56.39
3072
11.31
1.40
1.62
20.46
24.36
58.29
3072
T.63
0.48
0.66
EAD
16.32
30.38
100.0
90
1.92
5.70
1.47
13.01
13.23
100.0
800
0.94
4.89
0.65
PDPGD
26.84
42.50
100.0
63
0.64
2.00
1.32
22.30
35.13
100.0
75
0.41
2.00
0.59
VFGA
51.06
75.37
99.92
24
0.59
0.78
11.71
28.47
49.98
99.72
51
0.32
1.25
4.44
C1
C3
FMN
48.89
74.70
100.0
26
0.59
2.00
1.31
27.45
48.87
100.0
52
0.24
2.00
0.60
13.27
14.24
14.70
0O
0.63
2.05
1.47
16.88
22.91
27.64
00
1.04
2.25
0.65
BBadv
65.96
90.57
100.0
16
4.68
2.01
1.64
36.47
72.43
100.0
2.01
0.64
0-zero
76.53
95.38
100.0
11
0.73
2.00
1.53
38.60
73.02
100.0
0.43
2.00
0.71
SF
19.66
21.22
98.74
3070
3.62
0.46
1.90
31.76
43.07
91.14
69
4.32
1.49
0.66
EAD
9.73
11.42
100.0
360
2.53
5.62
1.89
24.21
24.78
100.0
768
1.04
4.99
0.65
PDPGD
28.02
45.15
100.0
55
1.12
2.00
1.8
26.89
42.38
100.0
66
0.40
2.00
0.60
VFGA
39.58
66.50
99.62
34
0.48
0.94
16.53
46.71
69.47
99.83
28
0.25
0.82
4.22
FMN
39.30
71.70
100.0
33
1.08
2.00
1.8
43.06
62.96
100.0
34
0.35
2.00
0.59
BB
38.73
56.78
58.64
33
2.31
2.89
1.89
25.95
27.98
29.50
00
0.54
2.09
0.65
BBadv
70.07
96.31
100.0
17
3.92
2.01
1.99
53.17
82.46
100.0
22
3.03
2.01
0.65
o-zero
74.63
97.55
100.0
15
1.41
2.00
1.92
55.42
82.92
100.0
20
0.42
2.00
0.72
ImageNet
EAD
35.4
36.3
100.0
460
4.13
2.69
0.46
27.0
28.4
100.0
981
19.25
5.49
1.41
VPGA
57.9
72.5
99.9
14
1.22
1.08
>
46.7
59.5
97.9
31
6.93
1.98
40
FMN
1/
62.6
81.0
100.0
12
0.73
2.00
0.66
67.7
100.0
25
1.98
2.00
2.30
BBadv
77.5
93.2
100.0
231.67
2.01
0.72
64.7
85.5
100.0
205.11
2.01
2.41
82.6
95.9
100.0
5
1.18
2.00
0.84
66.7
86.9
100.0
13
2.76
2.00
2.52
RAD
46.8
51.0
100.0
42
18.10
5.45
1.42
32.8
33.5
100.0
572
11.43
5.34
1.68
VFGA
54.7
63.4
96.7
12
8.21
2.35
> 40
40.0
46.5
95.5
66
33.88'
3.97
>00
FMN
12
57.8
67.0
100.0
9
1.97
2.00
2.30
14
40.3
47.2
100.0
58
4.28
2.00
2.97
BBadv
71.0
82.3
100
4
182.65
2.01
2.40
46.8
59..8
100.0
31
178.06
2.01
3.07
0 zero
76.9
87.4
100.0
3
2.75
2.00
2.52
50.7
65.1
100.0
23
5.72
2.00
3.20
3.2
EXPERIMENTAL RESULTS
We report the success rate and computational effort metrics of a-zero against minimum-norm attacks in Table annd fixed-budget attacks in Table 4 In these tables, consider the most robust models for each dataset, and we provide the remaining results in Appendix [B] Finally, for ImageNet, we narrow our analysis EAD, FMN, BBady, and VFGA minimum- attacks, as they surpass competing attacks on MNIST and CIFAR-10 in terms of ASR, perturbation size, or execution time.
The median values of 1 denoted as &g and the ASRs are reported in Table for all models and datasets. To facilitate comparison, the attacks are sorted from the least to the most effective, on average. In all modes configurations, a zero significantly outperforms all the considered attacks. Taking the persorerfor attack among the fastest competitors as a reference (i.e., FMN), 0- d-zero is able to find smaller perturbations and higher ASRs in all configurations. In particular, on CIFAR-I0, a zero reduces the median number of manipulated features from 52 to 32 against the most robust model (C3), with average reduction of 49% across all models. On ImageNet, this improvement is even more pronounced, with a reduction of up to 58%. In the best case (I4), the median ||0* (8*(], llo is reduced from 58 to 23, and in the worst case (I2), from 9 to 3. Alternatively, the most competitive attack in finding small perturbations is BBady, which is significantly slower and requires starting from arreay-adversarial input. The ASR of BB
Effectiveness.

---

Published as a conference paper at ICLR 2025
SpeendPod
PDRGD
+
VPGA
BB
-A-
FMN
B3ady 100
100
100
ASK.
ASR
ASR
07 107
117
102
102
Figure 2: Robustness evaluation curves (ASR vs. perturbation budget k) for M2 on MNIST (leff), C1 on CIFAR-10 (middle), and 11 on ImageNet (right).
(i.e., without adversarial initialization) indeed decreases with increasing input dimensionality (e.g.. CIFAR-10). This occurs because BB often stops unexpectedly before reaching the specified number of steps due to initialization failures; in particular, TTble Tsoww that the median perturbation size found by BB is sometimes oo, as its AS lower than 50%. Although BBadv does not suffer from the same issue, as it leverages adversarial initialization, it is still outperformed by a -zero. Specifically, ø-zero reduces the lo norm of the adversarial examples from 16 to 11 in the best case (CI), while achieving an average improvement of 24% across all mataset-mode configurations.
Efficiency. We evaluate the computational effort required to run each attack by reporting in Table I] the mean runtime (in seconds), the mean number of queries q issued to the model (in thousands), and the maximum VRAM used. Note that, while the runtime s and the consumed VRAM may depend on the attack implementation, the number of queries q counts the total number of forward and backward passes performed by the attack, thus providing a fairer evaluation of the attack complexity. In fact, some attacks perform more than 2000 queries even if N 1000, i.e., they perform more than one forward and one backward pass per iteration (see, e.g., EAD and BB). Other attacks, instead, might use less than 2000 queries they implement early stopping strategies. The results indicate that zezer exhibits similar runtime performance when compared to the fastest algorithms FMN, PDPGD, and VFGA, while preserving higher effectiveness. In contrast, when compared against the BBady attack, which competes in terms of Eg. our attack is much faster across all the dataset- model configurations, especially for Imagenet. For example, a-zero is 10 times faster than BBady on C4 and 100 times faster on B on ImageNet. This confirms that ø-zero establishes a better effectiveness-efficiee trade-off than that provided by state-of-the- norm attacks.
Reliability, Complementary to Table we present the robustness evaluation curves in Figure 2 for each attack on M2, C1, and 11. In Appendix B.3 we include similar curves for all other configurations. These curves go beyond the only median statistic and ASR;, providing further evidence that a-zero achieves higher ASRs with smaller to no-norm perturbations compared to the competing attacks. More importantly, the ASR of a- zero reaches almost always 100% as the perturbation budget grows, meaning that its optimization only rarely fails to find an adversarial example. In Appendix B. we further demonstrate that even when the number of iterations is reduced to N = 100, o-zero consistently achieves an ASR, of 100% across all models. This is not observed with other attacks, which often fail when using fewer iterations, thereby increasing the risk of overestimating adversarial robustness. These results reinforce our previous findings, confirming that azzero can help mitigate the issue of overestimating adversarial robustness a crucial aspect to foster scientific progress in defense developments and evaluations (Carlini et al. 2019 Pintor et al. 2022).
we present an ablation study to evaluate the relevance of a a-zero's components. Our findings indicate that all the non-tric non-trivial components in ø-zero are essential for ensuring the effectiveness of the attack. Specifically, we observe that the 4y-morm approximation to (Eq. line 3) leads the optimization algorithm to perturb all input features, albeit with small contributions. The projection operator qline 6) plays a crucial role by significantly decreasing the number of perturbed features, effeectivly removing the least significant contributions. Furthermore, gradient normalization (Tine 4) accelerates convergence, enhancing efficiency. Lastly, the adaptive projection operator (line 8) fine-tunes the results, reduces the number of perturbed features, and mitigates the dependency on hyperparameter choices. These results underline the importance of each component in a-zero, re, highlighting their contributions to the overall performance of the attack.
Ablation Study. In Table 2
7

---

Published as a conference paper at ICLR 2025
Table 2: Ablation study the d- components integrated in Algorithm Columns describe
respectively: Gradient normalization factor (line 4) dynamic projection adjustment line 8 projection operator II, (line 6); and the &g norm approximation lo (ine 3).
Model Normalization
Adaptive
Projection
to ASR10
ASRs0
ASR
21.68
73.02
100.0
32
21.89
71.66
100.0
32
16.81
39.76
100.0
65
C10
12.95
13.23
100.0
505
12.95
12.95
100.0
3004
12.95
12.95
100.0
3070
37.27
82.92
100.0
20
37.01
79.83
100.0
21
29.56
52.83
100.0
46
C5
25.46
32.84
100.0
144
23.78
23.78
100.0
3064
23.78
23.78
100.0
3068
Table 3: Fixed-budge comparison results with N 1000 (N 2000 for Sparse-RS) MNIST and CIFAR-IO at budgets 24, 50, 100. Columns 421 and $21 show the average number of queries (in thousands) and the average execution time per sample (in seconds)
24.
Attack ASR21 ASR ASR 100
824
VRAM M ASR21 ASR50 ASR 100 924
824
VRAM
MNIST
PGD-L
73.99
99.90
100.0
2.00
0.09
0.04
61.87
94.
98.50
2.00 0.09
0.04
Sparse-RS
79.54
96.35
99.79
0.83 0.21
0.04
98.92
99.96
100.0
0.24 0.07
0.04
sPGD, MI
65.55
97.97
99.99
0.46 0.09
0.05
M2
67.92
98.57
99.97
0.92 0.08
0.05
sPGD,,
82.79
99.65
100.0
0.09 0.08
0.05
62.25
98.11
99.99
1.00 0.09
0.05
o-zero
83.71
99.98
100.0
0.43 0.02
0.06
98.11
100.0
100.0
0.01
0.06
CIFAR-IO
PGD-&
38.18
59.67
87.19
2.00 0.78
1.90
22.99
36.20
67.54
0.35
0.69
Sparse-RS RS
72.51
86.59
94.28
0.77 0.36
1.95
30.87
45.65
63.26
1.47 0.28
0.68
sPGD, C1
66.37
89.21
99.36
0.74 0.41
2.06
C3
31.82
58.62
93.19
1.39 0.17
0.73
sPGD
66.33
91.07
99.75
0.72 0.41
2.06
36.16
70.06
98.07
1.30 0.16
0.73
77.08
95.33
99.95
0.65 0.29
2.07
38.67
73.00
98.53
1.33 0.15
0.75
PGD-2
32.41
39.19
89.22
2.30
2.46
34.35
44.99
68.61
0.35
0.70
Sp
59.24
79.81
92.43
1.04 0.35
2.46
49.35
63.01
76.51
1.11 0.37
0.68
sPGD,
C2
58.91
88.15
99.42
0.89 0.39
2.57
C4
50.41
75.86
97.52
1.02 0.18
0.73
sPGD,,
64.8
93.15
99.92
0.76 0.48
2.56
55.89
84.64
99.56
0.91 0.19
0.73
0-2cro
75.09
97.67
100.0
0.65 0.17
2.68
55.69
82.72
99.07
0.11
0.75
Comparison with Fixed-budget Attacks. We complement our analysis by comparing g-zero with three fixed-budget fo-norm attacks, i.c., the fo-norm Projected Gradient Descent (PGD-Ln) attack (Croce & Hein, 2019). the Sparse Random Search (Sparse-RS) attack (Croce et al. 2022 and the Sparse- PGDse--PGDD PGD attack (Zhong et al. 2024). For Sparse-PGD, we consider the implementation with sparse (sPGD,,) and with unprojected (sPGD,, gradient. In contrast to minimum norm attacks, fixed-budget attacks optimize adversarial examples within a given maximum perturbation budget For fairer comparison,as done in fixed-budget approaches, early stop the process as soon as an adversarial example with an fn-norm perturbation smaller than is found. In these evaluations, N = 2000 for Sparse-RS. Therefore, when using N = 1000 steps for zezo (which amounts to performing 1000 forward and 1000 backward calls), set N 2000 steps for Sparse-RS (which
optimization
set N 1000 for r-zero, PGD-Lu, sPGD,, and sPGD... ... while using
"Sparse-R8 RS is a gradient-free (black-box) attack. which only requires query access to the target model. We consider it an additional baseline in our experiments, but it should not be considered direct competitor of cradient-based attacks, works under much stricter assumptions (i.e.,
input gradients).
8

---

Published as a conference paper at ICLR 2025
Table 4: Fixed-budget comparison results with N 1000 (N 2000 for Sparse-RS) ImageNet
at budgets & 100, 150. See the caption of Table 3 for further details.
Attack ASR 100
1SR
$100
VRAM M 1SR
ASR 150
4100
$100
VRAM
ImageNet
Sparse-RS
89.3
91.5
0.39
0.32
1.29
81.1
84.1
0.53
0.5
4.39
sPGD,
95.4
98.5
0.31
0.16
1.40
85.6
91.2
0.33
0.64
4.48
II
sPGD.
93.6
97.8
0.33
0.12
1.40
82.6
88.7
0.39 0.37
4.49
zzzero
99.7
100.0
0.19 0.06
1.79
94.7
97.1
0.15
0.17
4.90
Sparse-Re RS
69.1
72.2
0.81
0.62
4.39
45.9
47.4
1.17
1.12
5.72
sPGD, p
85.4
93.4
0.32 0.55
4.49
66.3
74.9
0.73
1.39
5.84
13
14
sPGD,.
83.9
92.1
0.35
0.39
4.49
66.0
76.0
0.72
1.01
5.84
a-zero
97.7
99.6
0.34
0.37
4.90
78.8
85.8
0.49
0.70
6.29
amounts to performing 2000 forward calls) Furthermore, to compute the ASR at different (ASR+), we separately execute fixed-budget attacks for k = 24, 50, 100 features on MNIST and CIFAR-10 10, and with k = 100, 150 features on ImageNet (excluding PGD-& due to computational demands), reporting only the maximum number of queries and execution time across all distinct runs. We report the average query usage at io (q&) and the average execution time per sample at l (sx). We report the execution time of S for the smaller k, it requires, average, more iterations due the more challenging problem. The results, shown in Tables confirm that d-zero outperforms competing approaches in 17 out of 18 configurations (see Appendix B.2 for additional results). Only against C4 the fixed- beed-budget attack sPGD,, slightly increases the ASR. The advantages of a zero become even more evident when looking at the results on ImageNet, where, on average, it improves the 1S of 9.6% across all models in Table 4 The results also indicate that early stopping enables a zero to save a significant number of queries and runtime while preserving a high ASR. In Appendix B.2, we also report additional comparisons with N 2500 and N 5000, i.e. more favorable scenario for the competing attacks, confirming that zezero remains competitive even at higher budgets.
Summary. Our experiments show that a~ zero: (i) outperforms minimum-norm attacks by im- proving the success rate and decreasing the Eo norm of the generated adversarial examples (see Table and Appendix B. : (ii) is significantly faster and scales easily to large datasets (see la ble and Appendix B. :): (iii) is robust hyperparameter selection, not requiring sophisticated and time-consuming tuning (see Appendix A.2 : (iv) does not require any adversarial initialization
(see Table T: (v) provides
reliable adversarial robustness evaluations, consistently achieving
100% ASRs (see Table 1
Figure 2) Appendix B.3); (.3);; and (vi) remains competitive against fixed fixed-budget
attacks even when given the same query budget (Table" 4
RELATED WORK
Optimizing to fo-oorm adversarial examples with gradient-based based algorithms is challenging due to non- convex and non-differentiable constraints. We categorize them into two main groups: (i) multiple- norm attacks extended to fo. and (ii) attacks specifically designed to optimize the to norm.
Multiple-norm Attacks Extended to &. These attacks have been developed to work with multiple Ep norms, including extensions for the lg norm. While they can find sparse perturbations, they often rely heavily heuristies in this setting. [Brendel et (2019a) initialize the attack from adversarial example far away from the clean sample and optimizes the perturbation by following the decision boundary to get closer the source sample. In general, the algorithm can be used for any 4p norm, including fo. but the individual optimization steps are very costly, Pintor et al. (202I) propose the FMN attack that does not require an initialization step and converges efficiently with lightweight pradient-descent steps. However, their approach was developed to generalize over L, norms, but does not make special adaptations minimize the l, norm specifically. Matyasko Chau 2021 use
N 2000 is suggested as lower hound number of iterations to ensure the convergence of Sparse-RS by Croce al. 2022 Additional results with N 5000/11000 for Sparse-RS can be found in Appendix B.2

---

Published as a conference paper at ICLR 2025
relaxations of the lo norm (e.g., 112 to promote sparsity. However, this scheme does not strictly minimize the lo norm, as the relaxation does not set the lowest components exactly to zero.
fo-specific Attacks. Croce et al. (2022) introduced Sparse-RS, random search-based attack that, unlike minimum-nori norm attacks, aims to find adversarial examples that are misclassified with high confidence within fixed perturbation budget. On the same track find Sparse-PGD (Zhong et al., 2024) and PGD-& (Croce & Hein 2019). white-box Exed-budget alternatives to Sparse-RS. Lastly, Césaire et al. (222)) induces folded Gaussian noise to selected input components. iteratively finding the set that achieves misclassification with minimal perturbation. However, it requires considerable memory to explore possible combinations and find an optimal solution, limiting its scalability.
Overall, current implementations of fo-norm attacks present crucial suboptimal trade-off between their success rate and efficiency, i.c., they are either accurate but slow (e.g., BB) or fast but inaccurate (e.g., FMN). This is also confirmed by recent work that has benchmarked more than 100 gradient- based attacks (Cima al. 2025) on additional robust models. In that open-source benchmark, r-zero consistently and significantly outperformed all the existing implementations of competing fo-norm attacks, establishing a performance very close to that of the empirical oracle (obtained by ensembling all the attacks tested). In summary, our attack combines the benefits of the two families of attack detailed above, i.c., effectiveness and efficiency, providing the state-of-the-ar solution for adversarial robustness evaluations of DNNs when considering oo-norm attacks.
CONCLUSIONS AND FUTURE WORK
In this work, we propose zero, novel attack aimed to find minimum fo-norm adversarial examples, based on the following main technical contributions: (i) a differentiable approximation of the lu norm define novel, smooth objective that can be minimized via gradient descent; and (ii) an adaptive projection operator to enforce sparsity in the adversarial perturbation, by zeroing the least relevant features in each iteration. o z-zero also leverages specific optimization tricks to stabilize and speed up the optimization. Our extensive experiments demonstrate that a zero consistently discovers more effective and reliable fo-norm adversarial perturbations across all models and datasets while maintaining computational efficiency and robustness to hyperparameters choice. In conclusion, ø-zero emerges as highly promising candidate to evaluate robustness against fo-norm perturbations and promote the development of novel robust models against sparse attacks.
Based on our comprehensive analysis, we assert that there are no identifiable ethical considerations or foreseeable negative societal consequences that warrant specific attention within the limits of this study. This study will rather help improve the understanding of adversarial robustness of DNNs and identify potential ways to improve it.
Ethics Statement.
Reproducibility, To ensure the reproducibility of our work, we have detailed the experimental setup in Section 3.1 where describe the datasets, models, and attacks used, along with their respective sources. Additionally, we have provided our source code as part of the supplementary material, which will be made publicly available open source upon acceptance.
ACKNOWLEDGMENT
This work has been partially supported by the project Sec4A14Sec, under the EU's Horizon Europe Research and Innovation Programme (grant agreement no. 101 120393); the project ELSA, under the EU's Horizon Europe Research and Innovation Programme (grant agreement no. 101070617); the EU-NGEU National Sustainable Mobility Center (CN00000023), Italian Ministry of University and Research (MUR) Decree 1033 17/06/2022 (Spoke 10); projects SERICS (PE00000014) and FAIR (PE0000013) under the MUR NRRP funded by the EU-NGEU; and by the German Federal Ministry of Education and Research under the grant AlgenCY (16KIS2012).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Sravanti Addepalli, Samyak Jain, and Venkatesh Babu R. Efficient and effective augmentation strategy for adversarial training. In NeurlPS, 2022.
Maximilian Augustin, Alexander Meinke, and Matthias Hein. Adversarial robustness in- and out-distribution improves explainability. In Computer Vision ECCV 2020 16th European Springer, 2020.
Conference, volume 12371 of Lecture Notes in Computer Science, pp.
Battista Biggio and Fabio Roli, Wild patterns: Ten years after the rise of adversarial machine learning. Pattern Recognition, 84:317-331, 2018
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Sindic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD, volume 8190 of Lecture Notes in Computer Science, pp. 387-402 Springer, 2013.
Wieland Brendel, Jonas Rauber, Matthias Kümmerer, Ivan Ustyuzhaninov, and Matthias Bethge. Accurate, reliable and fast robustness evaluation. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems, NeurlPS, 2019a.
Wieland Brendel, Jonas Rauber, Matthias Kümmerer, Ivan Ustyuzhaninov, and Matthias Bethge. Accurate, reliable and fast robustness evaluation. In Conference on Neural Information Processing Systems (NeurIPS)), 2019b.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium Security and Privacy (S&P), 2017a.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy SP. pp. 39-57. IEEE Computer Society, 2017b.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian J. Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. CoRR, abs/1902.06605, 2019.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. In Conference on Neural Information Processing Systems (NeurIPS)), 2019.
Manon Césaire, Lucas Schott, Hatem Hajri, Sylvain Lamprier, and Patrick Gallinari. Stochastic sparse adversarial attacks. In 33rd IEEE International Conference on Tools with Artificial Intelligence, ICTAL, pp. 1247-1254. IEEE, 2021.
Pin-W Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. EAD: elastic-net attacks to deep neural networks via adversarial examples. In Proceedings of the Thirty-Secone AAAI Conference Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Iniel- ligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances Artificial Intelligence (EAAI-18), pp. 10-17. AAAI Press, 2018.
Tianlong Chen, Sijia Liu, Shiyu Chang, Yu Cheng, Lisa Amini, and Zhangyang Wang. Adversarial robustness: From self supersupe pre-training to fine-tuning. In /EEE/CVF Conference on Com- puter Vision and Puttern Recognition, CVPR, pp. 696-705. Computer Vision Foundation/ / IEEE, 2020.
A. E. Cinà, J. Rony, M. Pintor, Demetrio, A. Demontis, B. Biggio, I. B. Ayed, and F. Roli. Attackbench: Evaluating gradient-based attacks for adversarial examples. In AAAI Conference on Artificial Intelligence, 2025.
Francesco Croce and Matthiss Hein. Sparse and imperceivable adversarial attacks. 2019 IEFF/CVF International Conference on Computer Vision (ICCV), pp. 4723-4731, 2019.
Francesco Croce and Matthias Hein. Mind the box: 1 li-apgd for sparse adversarial attacks on image classifiers. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML, volume 139 of Proceedings of Machine Learning Research, pp. 2201-2211, PMLR, 2021.
11

---

Published as a conference paper at ICLR 2025
Francesco Croce, Maksym Andriushchenko, Vikash Sehwag, Edoardo Debenedetti, Nicolas Flam- marion, Mung Chiang, Prateek Mittal, and Matthias Hein. Robustbench: standardized adversarial robustness benchmark. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks I, NewrlPS Datasets and Benchmarks, 2021.
Francesco Croce, Maksym Andriushchenko, Naman D. Singh, Nicolas Flammarion, and Matthias Hein. Sparse-rs: versatile framework for query-efficient sparse black-box adversarial attacks. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI, pp. 6437-6445. AAAI Press, 2022.
Geoff Davis, Stephane Mallat, and Marco Avellaneda. Adaptive greedy approximations, Constructive approximation, 13:57-98, 1997.
Edoardo Debenedetti, Vikash Sehwag, and Prateck Mittal. A light recipe to train robust vision transformers. In First IEEE Conference on Secure and Trustworthy Machine Learning. 2023. URL
https:://openreveew..eeo. net.
Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019. URL httpp://gggginaoooooo/aaaaaaaaaa
Foolbox. Datasetattack, 2017. URL U_L_ateee/oooooo..eaataooo......
modu les hess/attack...on htm fooo hwwp:aaattackk...aaaasttttttttt
Justin Gilmer, Ryan P. Adams, Ian J. Goodfellow, David Andersen, and George E. Dahl. Motivating the rules of the game for adversarial example research. CoRR, abs/1807.06732,, 2018.
Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A. Mann. Improving robustness using generated data. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS, pp. 4218-4233, 2021.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2015.
Dan Hendryeks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song. Jacob Steinhardt, and Justin Gilmer. The many faces of robustness: A critical analysis of out-of-distribttion generalization. In 2021 IEEE/CVF International Conference on Computer Vision ICCV, pp. 8320-8329. IEEE, 2021.
Yulun Jiang, Chen Liu, Zhichao Huang, Mathieu Salzmann, and Sabine Süsstrunk. Towards stable and efficient adversarial training against I1 bounded adversarial attacks. In International Conference on Machine Learning, 2023.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60:84 90, 2012.
Yann LeCun and Corinna Cortes. The mnist database handwritten digits. 2005.
Alexander Matyasko and Lap-Pui Chau. PDPGD: primal-dual proximal gradient descent adversarial 01538)
attack. CoRR, fttp//210.011338. 2021. wtt.lttts...//x....rrggg///////
Yichuan Mo, Dongxian Wu, Yifei Wang, Yiwen Guo, and Yisen Wang. When adversarial training meets vision transformers: Recipes from training to architecture. Advances in Neural Information Processing Systems, 15:18599-1861, 2022.
Apostolos Modas, SoyyedMMossen -ezzovll,,,,,, and Pascal Frossard. Sparsefool: few pixels make a big difference. In Conference on compuler vision and pattern recognition (CVPR), 2019.
Shengyun Peng, Weilin Xu, Cory Cornelius, Matthew Hull, Kevin Li, Rahul Duggal, Mansi Phute, Jason Martin, and Duen Horng Chau. Robust principles: Architectural design principles for adversarially robust cnns. In 34th British Machine Vision Conference 2023. BMVC 2023, Aberdeen. UK, November 20-24, 2023, pp. 749-740. BMVA Press, 2023, URL http://procedddggs lomvc2023.org/11
12

---

Published as a conference paper at ICLR 2025
Maura Pintor, Fabio Roli, Wieland Brendel, and Battista Biggio. Fast minimum-nomm adversarial attacks through adaptive norm constraints. In Advances in Neural Information Processing Systems 34: Anmual Conference Neural Information Processing Systems, NeurIPS, pp. 20052-20062, 2021.
Maura Pintor, Luca Demetrio, Angelo Sotgiu, Ambra Demontis, Nicholas Carlini, Battista Biggio, and Fabio Roli. Indicators of attack failure: Debugging and improving optimization of adversarial examples. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 23063-23076. Curran Associates, Inc.,
2022.
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: A python toolbox benchmark the robustness of machine learning models, 2017. URL htttt:::///tttaaee com/ wtt.ccttt//.eeeeeeeeeeeeeeeeeeee bethgelab
fool box
Jérome Rony, Luiz G. Hafemann, Luiz Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. Decoupling direction and norm for efficient gradient-based 12 adversarial attacks and defenses. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4317-4325, 2018.
Jérôme Rony, Eric Granger, Marco Pedersoli, and Ismail Ben Ayed. Augmented lagrangian adversarial attacks. In 2021 IEEE/CVF International Conference on Computer Vision, ICCV, pp. 7718-7727. IEEE, 2021.
Jérôme Rony and Ismail Ben Ayed. Adversarial Library. Tercomerony/dddeesaaiaal libbary
URL https://github.com
Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adver- sarially robust imagenet models transfer better? Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS, 2020.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations (ICLR), 2014.
Eric Wong, Leslie Rice, and Zico Kolter. Fast is better than free: Revisiting adversarial training. In 8th International Conference on Learning Representations, ICLR. OpenReview.net, 2020.
Yuancheng Xu, Yanchao Sun, Micah Goldblum, Tom Goldstein, and Furong Huang. Exploring and exploiting decision boundary dynamics for adversarial robustness. In International Conference on Learning Representationss (ICLR), 2023.
Xuyang Zhong, Yixiao Huang, and Chen Liu. Towards efficient training and evaluation of robust models against lo bounded adversarial perturbations. In International Conference on Machine Learning ICML.. PMLR, 2024.
13


Reviews:
[{"review_id": "8qr886u5mS", "reviewer": "Reviewer_fo9d", "summary": "The paper proposes a novel $\\ell_0$-norm attack by leveraging a differentiable approximation of the $\\ell_0$-norm constraint. The approach can be applied to finding both minimum $\\ell_0$-norm and fixed budget adversarial examples. The authors conduct extensive evaluations on diverse datasets (e.g. CIFAR-10, ImageNet) and models. The results show that the proposed attack is effective and efficient in reducing the number of queries and memory usage.", "questions": "- To enable a clearer comparison between different attacks, could the authors provide ASR under varying iterations and perturbation budgets for fixed-budget attacks, similar to Figure 2? Showing results on one model would suffice and help better understand the performance under different conditions.\n- The transferability of the proposed attack across different model and architectures is unclear. Would it be possible to evaluate the method on a different model/architecture than the one used for generating adversarial examples? Such an evaluation would strengthen the applicability of the attack across varied settings.\n- In the minimum-norm attacks, ASR of the three datasets are reported on the same budgets: $k = 24, 50,\\infty$. However, in the fixed-budget comparisons, the results of ImageNet are reported at budgets $k = 100, 150$ while the other two datasets are evaluated at $24, 50, 100$. Could the authors clarify the reasoning behind this difference?\n- Minor writing issues\n  - The bounded-norm attacks are not cited at the first appearance in Section 3.1\n  - In Table 2’s caption, $q_{100}$ and $s_{100}$ are mentioned, but it seems these should be $q_{24}$ and $s_{24}$, based on the table’s content.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem is well-motivated as $\\ell_0$-norm attacks are less studied due to the non-convexity nature.\n- The paper is easy to follow and well-organized\n- The evaluations are comprehensive and indeed show that the proposed algorithm is more effective and efficient.", "weaknesses": "- I appreciate the authors' efforts in evaluating the method. However, I was a bit confused by the inconsistency in some parts of the evaluations. For example, the memory usage is shown for minimum-norm attacks while it's missing in the bounded-norm attack results; The mean runtime for bounded attacks is shown in Tables 2 and 3 while it's missing in Tables 10 - 12; In Tables 10 - 12, the budget level that the number of queries corresponds to is also missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "HTtyipkKZ3", "reviewer": "Reviewer_L1s2", "summary": "The paper introduces σ-zero, a novel attack aimed at creating sparse adversarial examples under the ℓ0 norm constraint. By using a differentiable ℓ0 norm approximation and adaptive projection operator, the attack achieves high success rates across multiple benchmarks (MNIST, CIFAR-10, and ImageNet) and models. It outperforms existing sparse attacks in both efficiency and effectiveness.", "questions": "**Q1**: In the introduction, you mention that “evaluating adversarial robustness under these attacks could reveal weaknesses otherwise left untested with more conventional ℓ2- and ℓ∞-norm attacks.” Could you specify what types of model weaknesses can be exposed by ℓ0 attacks that may remain undetected under conventional ℓ2 and ℓ∞ attacks? Examples or specific scenarios would be helpful for understanding.\n\n**Q2:** Have you considered any step size decay methods other than cosine annealing in your algorithm? Exploring more direct approaches might further reduce computational complexity.\n\n\n**Q3:** Does your method enhance the improvement or understanding of attacks using other norms? Based on your assertion that 'ℓ0-norm attacks, which perturb only a minimal fraction of input values, can identify the most sensitive features affecting the model's decision-making,' could your method be integrated into attacks with other norms to avoid targeting these sensitive features, thereby reducing the visual damage of adversarial examples?\n\n\n**Q4:** I appreciate your clarification that 'the goal of ℓ0-norm attacks is not to be indistinguishable to the human eye—a common misconception regarding adversarial examples—but rather to demonstrate whether and to what extent models can be deceived by altering only a few input values.' However, in the visualizations of adversarial examples provided in your appendix, the perturbations lack semantic information comprehensible to humans. How can we understand and apply the adversarial perturbations generated by your method in this context?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. **Innovative Approach**: σ-zero combines a unique differentiable approximation of the ℓ0 norm with adaptive projections, addressing challenges in sparse adversarial attack optimization with a gradient-based method.\n2. **Robust Evaluation**: The experimental setup is thorough, involving extensive model types and datasets, and a range of comparison attacks. Evaluation metrics like success rate, median perturbation size, runtime, and query count provide a clear assessment of σ-zero's performance relative to existing methods.\n3. **Efficiency and Robustness**: σ-zero demonstrates effective performance without the need for adversarial initialization or hyperparameter tuning, potentially broadening its applicability.", "weaknesses": "1. **Limited Innovation**  \n   The approach presented shows minimal originality and bears a strong resemblance to existing methods, with only slight modifications. These adjustments lack ingenuity, as they do not introduce new insights or significant advancements over prior work. The lack of a novel perspective limits the contribution of this study to the field.\n\n2. **Lack of Theoretical Understanding and Analysis**  \n   A major shortcoming of this work is the absence of a robust theoretical foundation. The paper lacks in-depth analysis to demonstrate the underlying principles or broader significance of the method. Without a theoretical understanding, the impact of the work remains superficial, leaving readers without a clear sense of the method’s potential applicability or contribution to the advancement of adversarial robustness.\n\n3. **Limited Application Scope**  \n   All experiments focus exclusively on white-box attacks, which limits the generalizability of the findings. While white-box evaluations are useful for testing model robustness, the absence of analysis in other contexts raises concerns about the method’s broader applicability. Expanding to include black-box or transfer-based attacks, for instance, could improve the study’s relevance and highlight potential real-world applications.\n\n4. **Simplistic Model Choices in Experiments**  \n   Although the experiments involve several models, these are relatively simple in structure. The paper does not consider more complex architectures, such as ResNet-101 or models of similar or higher complexity, which are frequently used in evaluating ImageNet-related tasks. Given that larger and more sophisticated models are common in real-world applications, the study’s reliance on simpler architectures limits the robustness and scalability of its findings.\n\n\n**Miner Comments:** \n1. There is an indexing error in Table 2 that needs to be addressed.\n2. Footnote 1 states, 'when the source point $x$ is already misclassified by $f $, the solution is simply $\\delta^* = 0$. This is quite puzzling, as attacks are typically conducted on samples that can be correctly classified. If the attack is performed on samples that are already misclassified, I question the persuasiveness of the higher ASR observed in the experimental results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "rPZ9lVC9jh", "reviewer": "Reviewer_xveC", "summary": "This paper proposes a $\\ell_0$-norm adversarial attack that efficiently breaks various models trained on MNIST, CIFAR10, and ImageNet with 100% success rate. The proposed method is significantly faster than prior attacks at a high success rate. The proposed attack is composed of three main components:\n1) A differentiable relaxation of the $\\ell_0$ loss (Eq. 7).\n2) An adaptive projection to project near-zero components to zero. The threshold for projection, $\\tau$, is adapted dynamically such it is increased when the sample is adversarial and decreased otherwise.\n3) Cosine annealing of the learning rate.", "questions": "- Eq. 4 defines the regularized objective with a fixed regularization coefficient of $1/d$. How important is this normalization? Do you have any theories or ablations?\n- BBadv is said to be slow, particularly it relies on adversarial initialization. Would $\\sigma$-zero benefit in any way if it is also initialized the same way if we ignore the extra runtime?\n\nMinor:\n- Line 321: The sentence starts with “Despite BBadv does not suffer …” needs grammar correction, e.g., substituting “Despite” with “Although”.\n- Consider annotating Figure 2 with subfigure captions.\n- How is table 4 ordered? It seems to be random.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The proposed method is highly effective against a diverse set of models on multiple datasets and all attack budgets (Table 1-3, Figure 2). Particularly, on ImageNet $\\sigma$-zero improves the attack success rate at 100 by nearly 10% across all models (Table 3).\n- Compared with BBadv that often achieves similar ASRk values, the proposed method is 10-200x faster.", "weaknesses": "- I recommend moving the ablations on the components of the proposed method (Table 5) to the main body of the paper. For completeness, consider adding the missing row with normalization/adaptive $\\tau$ but without projection and dropping the column approximation as all rows rely on it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "IIXmMLlvQH", "reviewer": "Reviewer_xCu7", "summary": "The authors propose a $\\ell_0$-norm attack, called sigma-zero, which leverages a differentiable approximation of the $\\ell_0$ norm to facilitate gradient-based optimization. The attack can find minimum $\\ell_0$-norm adversarial examples. The experiments show that sigma-zero exhibits good performance in different settings.", "questions": "1. Typo on the title of Table 2: \"Columns $q_{100}$ and $s_{100}$ ... at $k=100$\", but $k$ is 24 in the below.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is easy-to-follow\n\n2. The method is simple but effective\n\n3. The experiments are relatively comprehensive", "weaknesses": "1. Despite the effectiveness of sigma-zero on different models, the evaluation on $\\ell_0$-robust models is missing. Please consider including the results of sAT / sTRADES [1], e.g., those trained on CIFAR-10, $k_{train}=6\\times20$ in pixel space.\n\n2. Due to the early-stopping mechanism widely adopted in various attacks, when the batch size is large, white-box attacks could run even faster than black-box attacks with the same iteration budget. Thus, I am still curious about the results of sigma-zero, sPGD and Sparse-RS with the same budget, e.g., N=10000. You can report the same metrics on a subset of representative models as in Table 13.\n\nI will adjust my score if the authors can address my concerns.\n\n[1]  Xuyang Zhong, Yixiao Huang, and Chen Liu. Towards efficient training and evaluation of robust models against l0 bounded adversarial perturbations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)