Sparse-PGD: An Effective and Efficient Attack for $l_0$ Bounded Adversarial Perturbation

Dear reviewer RqW9,

We thank reviewer RqW9 for the helpful review! We are glad that you agree that our proposed contribution is significant. In response to your questions, we offer the following point-to-point answers:

1. Experimental evaluation should be improved. The authors claim the approach is explained with image classification as an example, but the approach should be applicable to any kind of data. This is inconsistent with how the method is evaluated.

   Reply: To help illustrate the formulation, we used image classification as an example and evaluated the proposed attack on CIFAR-10, CIFAR-100 and ImagNet-100. Similar to previous attacks [1 - 3], we don't have any constraint on the input. As a result, the method can be applicable to any data. Besides, all these datasets are intensively used and benchmarked in the existing literature [1 - 4] to evaluate the model's robustness. Lastly, since it is a novel attack method, rather than empirically proving it is applicable to some specific application in some specific data domain (although we agree that it will be a good potential future work), our main contribution is general: that is, our attack method empirically outperforms the state-of-the-art sparse attack (including both white-box and black-box attacks) and those models adversarially trained by the attack show the strongest robustness against various sparse attacks.

2. It would be interesting to see the results of this method without this additional constraint. The approach can be still developed, simply by creating a mask for every channel.

   Reply: Thanks for pointing this out, we will consider your comments and try to improve our work in future work.

3. Unclear difference with SAIF

   Reply: For the attack process, though we adopt a similar decomposition method to the perturbation to SAIF=, our attack design is significantly different from the previous work in two perspectives:

   1. Instead of using an $\ell_1$ convex surrogate for the $l_0$ norm constraint of the sparsity mask as done in SAIF, we introduce a continuous mask $\widetilde{m}$ and project it back to the feasible set. To prevent the magnitude of $\widetilde{m}$ from being too big, we add a sigmoid function before projecting $\widetilde{m}$ to the binary mask $m$. This new but simple strategy has proven to be effective as shown in the ablation studies (Table 2, Sec 5.3) where we observed a huge robust accuracy drop from 49.5% to 22.2%. Moreover, we further improve the exploration capability for the mask $m$ by a random reinitialization mechanism, which is shown to improve the performance in the ablation study. This design alleviates the problem of local convergence, which is reported in SAIF.
   2. The ablation studies (Table 2, Sec 5.3) also indicated naively decomposing the perturbation by $\delta = p \odot m$ can deteriorate the performance, which further corroborates the effectiveness of our attack designs.

7. There are many terms that are co-dependent with other terms throughout 4.1--it is challenging to understand precisely what are the main ingredients of Sparse-PGD, why they matter, and what decisions influenced their design.

   Reply: The main idea of our method is to decompose a $l_0$ bounded perturbation $\delta$ into a magnitude tensor $p$ and a sparsity mask $m$.

   • Since $p$ is only constrained in the image box $[0, 1]^{h\times w\times c}$ which is similar to the $l_\infty$ constraint, we update it using $l_\infty$-PGD.
   • Updating a sparse and discrete $m$ is challenging in optimization, we update its continuous alternative $\widetilde{m}$ and then projecting $\widetilde{m}$ to obtain $m$.
   • Due to the binary projection onto $S_{m}$, the update of $p$ is equivalent to $k$-coordinate descent, which leads to slow convergence and suboptimal performance. Inspired by training pruned neural networks and lottery ticket hypothesis [3-6], we discard the projection $S_{m}$ when calculating the gradient of $p$ to ensure every element of $p$ can be updated. However, in the experiments, we found the unprojected and projected gradients are complementary in terms of performance.
   • Random reinitialization is proposed to prevent $m$ from getting trapped into local maxima, because $m$ changes only when the relative magnitude ordering of the continuous alternative $\widetilde{m}$ changes. In other words, slight changes in $\widetilde{m}$ usually mean no change in $m$.

8. A distortion vs accuracy curve should be plotted, so that we can understand the performance curves of sAA against baselines. Reporting the final results at a fixed norm boundary is not readily indicative of attack performance, given that are are many values of k a defender would consider to be "adversarial"

   Reply: Thank you for pointing this out, we added the curves of sAA in Figure 1 (b).

9. When attacking against adversarially trained models, perturbations must stay within the threat model. That is, it should be made clear that, when attacking an l-infinity-based model, the l0 perturbations also do not exceed, e.g., 8/255. Otherwise, it is not clear to me what insights are to be drawn from attacking a model whose threat model is violated

   Reply: In the previous work [7], when evaluating the robustness of an $l_\infty$-robust model against $l_2$ attacks, they do not constrain the $l_\infty$ norm of the $l_2$ perturbations to be $8/255$ or something else. The results in [7] also indicate that a model that is robust to a specific attack is usually not robust to another attack at all. In addition, when we validate whether a model is robust to a white-box attack, we should follow the principle that the attacker knows model architecture and model weights; training algorithm and training data; test time randomness (either the values chosen or the distribution) of the defender [8]. In the evaluation, we should not compromise the defender, so what we do is just to generate $l_0$ bounded perturbations without any other restrictions.

10. Mixing threat models does not seem sound. It is not clear why black-box attacks are compared to white-box attacks, etc. White-box threat models should only be compared to white-box attacks, and likewise for black-box attacks.

    Reply: As shown in AutoAttack [9], they also combine white-box and black-box attacks to obtain a reliable and comprehensive evaluation of adversarial robustness, since white-box attacks sometimes have suboptimal performance due to gradient masking, but black-box attacks are immune from it because they do not rely on the gradient information. Empirically, among current adversarial attacks generating $l_0$ bounded perturbations, black-box attacks usually outperform white-box ones. For example, we see black-box sparse-RS outperforms white-box PGD$_0$ in many cases, depending on the evaluated models. In summary, we need to combine both white-box and black-box attacks to reliably and comprehensively evaluate the robustness, because they are complimentary.

11. Attack configuration does not seem fair - It is not clear to me why Sparse-RS is included within sAA when it is used verbatim from prior work. So that readers can understand the core contributions of this work, comparisons against baselines should only be evaluated against the introduced attacks. Moreover, the JSMA (Papernot, 2016) is one of the first l0-based attacks to be introduced in the literature. It is unclear to me why this not compared against in this work.

    Reply: Thanks for pointing this out, we have cited it in the paper. Although JSMA is one of the first $l_0$ attacks, its code is not publicly available, making it difficult for reproduction. In addition, JSMA is not included in the existing works we use as baselines either. Considering these two points, we do not include it in the comparison.

Dear reviewer DCtb,

Thanks for your insightful and constructive comments. In response to your questions, we offer the following point-to-point answers:

1. For updating the magnitude tensor, are p and delta the same variable?

   Reply: In our work, we decompose the sparse perturbation $\delta$ into a magnitude tensor $p\in\mathbb{R}^{h\times w\times c}$ and a sparsity mask $m\in\{0,1\}^{h\times w\times 1}$, i.e., $\delta =p \odot m$. We update $p$ and $m$ separately, and then obtain $\delta$ with the updated $p$ and $m$.

2. Why is the l2-norm of the loss taken in (5)?

   Reply: According to the first-order Taylor expansion of loss function, $L(x+v)\approx L(x)+\nabla L(x)^T v$. Finding the steepest ascent direction of the loss function is equivalent to finding the $v$ which maximizes the directional derivative. In Euclidean space, if we want to find the steepest ascent direction within the step size of the unit norm, i.e., ||v||2=1 , the direction is $v=\nabla L(x)/||\nabla L(x)||_2$ [1].
   In our scenarios, we want to update $\widetilde{m}$ with the step size $\beta$, so the updating can be written as $\widetilde{m} = \widetilde{m} + \beta \cdot \nabla_{\widetilde{m}} L / (||\nabla_{\widetilde{m}} L||_2 + \gamma)$, where $\gamma$ is a small constant to prevent the denominator from being zero.

3. For updating the sparsity mask, what is gradient ascent performed on?

   Reply: The $l_0$ bounded perturbation $\delta$ can be decomposed into magnitude tensor $p$ and a sparsity mask $m$, i.e., $\delta =p \odot m$. We aim to maximize the loss $L(\theta, x+p\odot m)$ through updating $p$ and $m$ with gradient ascent. Since $m$ is sparse and discrete, directly optimizing it is challenging. Instead, we introduce a continuous variable $\widetilde{m} \in \mathbb{R}^{h\times w\times 1}$ and project $\widetilde{m}$ to the feasible set $S_m$ before multiplying it with the magnitude tensor $p$ to calculate the sparse perturbation $\delta$. Since $\widetilde{m}$ is a continuous variable, we can optimize it using gradient ascent.

4. It is unclear what, "Since elements in m are 0 or 1, we use sigmoid to normalize elements in m-tilde to be 0 or 1" is trying to say; aren't elements in m in [0, 1] because of (6)?

   Reply: We are sorry about the confusion, we have modified the claim in the paper. In addition, we clarify that the sigmoid function used here is to prevent $\widetilde{m}$ from being too large in magnitude. When the magnitude of $\widetilde{m}$ is large, its gradient will vanish to zero by applying the sigmoid function, this mechanism will prevent $\widetilde{m}$ from being too large and ensure the numeric stability. In the same settings of Table 2 in section 5.3, if we discard the sigmoid function, the robust accuracy increases from 20.0 to 68.5, which further demonstrates the effectiveness of the sigmoid function.

5. The argument that projection on the binary set Sm is discarded because coordinate descent is suboptimal is unclear; why is such a projection introduced to be later argued as suboptimal and thus discarded? (In fact, this observation is stated twice)

   Reply: Due to $S_{m}$, the gradient of $p$ is sparse, so at most $k$ elements of $p$ are updated at one iteration, which is equivalent to $k$-coordinate descent. Previous work [2] already demonstrates that coordinate descent results in slow convergence and suboptimal performance. In addition, we want to emphasize that the projection operator is only discarded during the back-propagation, it still works in the forward propagation. Moreover, as we indicate in Table 3, the projected and unprojected gradients are complementary in terms of performance, none of them is always better than the other, so we run sPGD twice with different backward functions in sAA for comprehensive evaluation.

6. It is unclear where the projection onto the binary set Sm is used in gp and why it is used in tandem with gp-tilde if gp exhibits both non-convergence and gradient explosions

   Reply: This question is already addressed in the explanations above.

Dear reviewer DbyG,

Thanks for your insightful and constructive comments. In response to your questions, we offer the following point-to-point answers.

For problems mentioned in Weaknesses:

1. >>> While sAA seems effective (Table 1), there are some concerns in my opinion: first, according to Fig. 1a, the attacks notably benefit from more iterations. In particular, Sparse-RS shows significant improvements between 3k and 10k iterations for all models, which means that the results reported in Table 1 might be suboptimal. Second, in Tables 6, 7 and 8, CS alone appears to be better than sAA on the models robust to $l_0$-attacks: while CS is evaluated on a subset of points only, an improvement of more than 3% (Table 6) seems significant to hint to the fact that, even on the full test set, the results of sAA might be improved. Finally, in most cases the robust accuracy of the best individual attack (either RS or sPGD) is quite higher (2-3%) than their worst-case, i.e. sAA, which suggests that each attack is suboptimal.

   Response: First, Sparse-RS indeed has performance improvement between 3k and 10k iterations for all models. However, as illustrated in Figure 1 (a), in the cases where our method outperforms Sparse-RS at 3k iterations, it is still substantially better than Sparse-RS when we use more iterations. That is to say, setting the number of iterations to 3k does not affect the performance superiority of our method. However, we are happy to present the results of Sparse-RS with 10k iterations and compare them with our methods. Due to the time constraint, we only run the experiments on a subset of models as shown in Table 1. It is clear that sAA still performs the best in all models except in $\ell_{\infty}$-adv model and we acknowledge this as one weakness of our method and will try to improve it in future work. As for the second question, we would like to emphasize that our $l_0$-robust models are just baselines for future work. The major motivation of $l_0$-robust models is to demonstrate the efficiency of our method so that we can utilize it for adversarial training. Due to the challenges of optimization in an $l_0$ bounded space, we notice that the $l_0$-robust models are more vulnerable to black-box attacks, especially sparse-RS, although these models still obtain the best robustness when we consider all attack methods. In Tables 6, 7 and 8, the reason why CS is better than sAA on the models robust to $l_0$-attacks can be attributed to that Sparse-RS underperforms CS on $l_0$-robust models. Despite that, due to the very high complexity of CS (10x slower), we do not adopt it as the black-attack here. We believe this issue can be solved if we have a better adversarial training methods to mitigate the gradient masking problem of the models obtained, which we leave it as future work.

   Table 1: Robust accuracy of selected models on Sparse RS where the sparsity level $k=20$. We record the performance of RS in both 3k and 10k iterations and their changes.

   Model	Network	RS	sPGD$_{\mathrm{CE}}$	sPGD$_{\mathrm{CE+T}}$	sAA
   Vanilla	RN-18	0.0 $\to$ 0.0	0.0	0.0	0.0
   $l_\infty$-adv. trained, $\epsilon=8/255$
   PORT	RN-18	14.6 $\to$ 9.7	20.9	16.1	10.8
   DKL	WRN-28	11.0 $\to$ 7.0	22.5	16.6	9.6
   $l_2$-adv. trained, $\epsilon=0.5$
   HAT	PRN-18	20.5 $\to$ 13.9	13.2	10.0	9.3
   DM	WRN-28	23.4 $\to$ 16.1	20.9	15.5	14.1
   $l_1$-adv. trained, $\epsilon=12$
   $l_1$-APGD	PRN-18	33.1 $\to$ 25.8	24.0	20.0	19.5
   $l_0$-adv. trained, $k=20$
   sTRADES	PRN-18	52.1 $\to$ 41.8	79.5	77.9	52.0

2. >>> The budget of iterations of the attacks is not justified: looking at Fig. 1a it seems that more iterations would significantly improve the results, especially for RS. If I understand it correctly, sPGD is used for 20 runs ({1 CE, 9 targeted CE} x {projected, unprojected}) each of 300 iterations, for total 6k iterations (each consisting in one forward and one backward pass of the network). However, only 3k queries (forward pass only) are used for RS, which seems unbalanced given that RS provides better results for $l_0$- and (especially) $l_0$-adversarially trained models.

   Response: We need to clarify that the sPGD with 20 runs ({1 CE, 9 targeted CE} x {projected, unprojected}) is only adopted in sAA. We do not compare the performance of Sparse-RS with sPGD and its variants. By contrast, in Figure 1 (a), we evaluate sPGD with unprojected gradient with different numbers of iterations. The robust accuracies of Sparse-RS and sPGD at the same x-axis value are obtained with the same number of iterations. Therefore, we think the comparison is fair here.

References:

[1] Tooba Imtiaz, Morgan Kohler, Jared Miller, Zifeng Wang, Mario Sznaier, Octavia Camps, and Jennifer Dy. Saif: Sparse adversarial and interpretable attack framework. arXiv preprint arXiv:2212.07495, 2022.

[2] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning, pp. 2206–2216. PMLR, 2020.

[3] Francesco Croce and Matthias Hein. Mind the box: $l_1$-apgd for sparse adversarial attacks on image classifiers. In International Conference on Machine Learning, pp. 2201–2211. PMLR, 2021.

[4] Francesco Croce and Matthias Hein. Sparse and imperceivable adversarial attacks. In Proceedings of the IEEE/CVF international conference on computer vision. 2019.

[5] Croce, Francesco, and Matthias Hein. "Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks." International conference on machine learning. PMLR, 2020.

[6] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.

[7] Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari. What’s hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11893–11902, 2020.

[8] Yonggan Fu, Qixuan Yu, Yang Zhang, Shang Wu, Xu Ouyang, David Cox, and Yingyan Lin. Drawing robust scratch tickets: Subnetworks with inborn robustness are found within randomly initialized networks. Advances in Neural Information Processing Systems, 34:13059–13072, 2021.

[9] Chen Liu, Ziqi Zhao, Sabine Süsstrunk, and Mathieu Salzmann. Robust binary models by pruning randomly-initialized networks. Advances in Neural Information Processing Systems, 35:492–506, 2022

Dear reviewer Ngmx,

Thanks for your insightful and constructive comments. In response to your questions, we offer the following point-to-point answers:

1. >>> Following Sparse Adversarial and Interpretable Attack Framework (SAIF) [1], which adopts a magnitude tensor and sparsity mask same as this paper, the authors further discard the projection to the binary set when calculating the gradient and use the unprojected gradient to update the magnitude tensor p. Sparse-AutoAttack (sAA) part has extended the work of AutoAttack (AA) [2,3], and the reason for discarding the adaptive step size, momentum and difference of logits ratio (DLR) loss function should be further explained clearly. The paper appears to offer limited new perspectives on the attack process and lacks a notable degree of technical innovation.

   Response: For the attack process, though we adopt a similar decomposition method to the perturbation to SAIF [1], our attack design is significantly different from the previous work in two perspectives:

   1. Instead of using an $\ell_1$ convex surrogate for the $l_0$ norm constraint of the sparsity mask as done in SAIF, we introduce a continuous mask $\widetilde{m}$ and project it back to the feasible set. To prevent the magnitude of $\widetilde{m}$ from being too big, we add a sigmoid function before projecting $\widetilde{m}$ to the binary mask $m$. This new but simple strategy has proven to be effective as shown in the ablation studies (Table 2, Sec 5.3) where we observed a huge robust accuracy drop from 49.5% to 22.2%. Moreover, we further improve the exploration capability for the mask $m$ by a random reinitialization mechanism, which is shown to improve the performance in the ablation study. This design alleviates the problem of local convergence, which is reported in SAIF.
   2. The ablation studies (Table 2, Sec 5.3) also indicated naively decomposing the perturbation by $\delta = p \odot m$ can deteriorate the performance, which further corroborates the effectiveness of our attack designs.

   In terms of backward function for updating $p$, we argue that the original gradient $g_{p} = \nabla_{\delta} L(\theta, x + \delta) \odot m$ is sparse due to the sparsity of the mask $m$. The sparse update will result in sub-optimal performance similar to coordinate descent when there are limited iterations. To solve this problem, we adopt a novel unprojected gradient $g_{p} = \nabla_{\delta} L(\theta, x + \delta) \odot \sigma(\widetilde{m})$ inspired by network pruning and lottery ticket hypothesis [6 - 9] and combine it with the original sparse gradient to achieve a better trade-off on exploration and exploitation.

2. >>> The authors claim that “We are the first to conduct adversarial training against $l_{0}$ bounded perturbations.” However, related work had also conducted similar experiments [4].

   Response: Thank you for pointing this out. We will modify this claim in the paper and add the results of using PGD$_0$ as adversarial training. The results are reported in Table 1, Sec 1.2.1 of General Response, and we have also included them in the paper. We observe that the model trained with adversarial samples generated by PGD$_0$ can be easily beaten by our proposed attack sPGD, while the model trained with sPGD-generated adversarial samples is still robust against PGD$_0$, so we do not include it in other experiments.

3. >>> This paper has emphasized the contribution of computational complexity and efficiency but lacks corresponding analysis for computational complexity and query budgets for comparison.

   Response: In Section 5.2, we study the efficiency by comparing the performance of Sparse-RS with sPGD_CE (Figure 1(a)) and sPGD_CE+T (Figure 2) under different number of iterations. Both figures show that sPGD achieves significantly better performance than RS attack under limited iterations. That is to say, Sparse-RS requires a much larger query budget to achieve comparable performance.

4. >>> In Table 1 in experimental part, RS attack outperforms sPGD_CE+T for $l_{\infty}$ models while more analysis is required.

   Response: Thanks for pointing this out. For attacking $l_\infty$ models, we agree that sPGD is outperformed by RS when there are enough iterations, which means sPGD suffers from gradient masking to some degree in this case. This is also why we included the black-box RS attack in sAA to comprehensively evaluate the robustness. Further mitigating the gradient masking effect when sPGD is applied to some specific models will be our future work.