Boosting Ray Search Procedure of Hard-label Attacks with Transfer-based Priors

Authors: Chen Ma, Xinjie Xu, Shuyu Cheng, Qi Xuan
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: adversarial attack, hard-label attack, decision-based attack, black-box attack, gradient estimation, surrogate model, transfer-based priors

Abstract:
One of the most practical and challenging types of black-box adversarial attacks is the hard-label attack, where only top-1 predicted labels are available. One effective approach is to search for the optimal ray direction from the benign image that minimizes the $\ell_p$ norm distance to the adversarial region. The unique advantage of this approach is that it transforms the hard-label attack into a continuous optimization problem. The objective function value is the ray's radius and can be obtained through a binary search with high query cost. Existing methods use a "sign trick" in gradient estimation to reduce queries. In this paper, we theoretically analyze the quality of this gradient estimation, proposing a novel prior-guided approach to improve ray search efficiency, based on theoretical and experimental analysis. Specifically, we utilize the transfer-based priors from surrogate models, and our gradient estimators appropriately integrate them by approximating the projection of the true gradient onto the subspace spanned by these priors and some random directions, in a query-efficient way. We theoretically derive the expected cosine similarity between the obtained gradient estimators and the true gradient, and demonstrate the improvement brought by using priors. Extensive experiments on the ImageNet and CIFAR-10 datasets show that our approach significantly outperforms 11 state-of-the-art methods in terms of query efficiency.

Decision: accept (spotlight)
Reviewer scores: 8, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1730648019873

thread_type:
official_review

<thread_object>
creator: reviewer_cas8

<content>
summary:
The paper addresses the challenge of hard-label adversarial attacks and enhances the efficiency of searching for the optimal ray direction by introducing a prior-guided approach that leverages transfer-based priors from surrogate models. Theoretical analysis is provided to validate the effectiveness of their gradient estimation technique, and extensive experiments on ImageNet and CIFAR-10 demonstrate significant improvements in query efficiency compared to 11 state-of-the-art methods.

strengths:
1. The paper provides a solid theoretical foundation for the proposed gradient estimation technique.
2. Extensive experiments on multiple datasets demonstrate the practical effectiveness of the proposed method.
3. The focus on improving query efficiency is critical, as it addresses one of the major challenges in hard-label attacks, making the method more applicable in real-world scenarios.

weaknesses:
1. The following work [1] also proposes to use a pre-trained model to reduce the query complexity of hard-label adversarial attacks. Please clarify the novelty based on this work.
2. The paper does not adequately address the scalability of the proposed method, particularly in scenarios involving larger models or more complex datasets.
3. The reliance on transfer-based priors from surrogate models raises concerns about overfitting and the applicability of the method to unseen models or datasets.

[1] Yan, Z., Guo, Y., Liang, J., & Zhang, C. (2021). Policy-driven attack: Learning to query for hard-label black-box adversarial examples. In International Conference on Learning Representations.

questions:
See the weaknesses for details
</content>
</thread_object>

</thread>
<thread>
creation date:
1730686450316

thread_type:
official_review

<thread_object>
creator: reviewer_hzgv

<content>
summary:
This paper proposes a new method for hard-label attacks which uses transfer-based priors to estimate the gradient of the loss in hard-label attacks, which is quite query efficient.

strengths:
1. This paper proposes a surrogate function to estimate compute the transfer-based priors, which can avoid the non-differentiable issue of using binary search to learn the prior.

2. The gradient of the loss in Eq. (3) can be estimated by the projection of the true gradient onto the subspace spanned by these transfer-based priors and some random directions.

weaknesses:
An efficiency experiment is required to show how the proposed method improves the ray search efficiency.

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1730731207088

thread_type:
official_review

<thread_object>
creator: reviewer_z4ag

<content>
summary:
This paper introduces two novel hard-label attack methods, Prior-Sign-OPT and Prior-OPT, which leverage transfer-based priors and random sampling vectors to enhance the query efficiency and success rate of black-box adversarial attacks. Theoretical analysis and experiments on ImageNet and CIFAR-10 datasets demonstrate that these methods significantly outperform 11 state-of-the-art techniques while reducing the number of queries needed.

strengths:
1. This paper proposes a gradient estimation method to conduct hard-label attack and provides proof for it.

2. The paper is well-written.

weaknesses:
1. The paper benefit from showing the time complexity.
2. This paper is a comprehensive study based on transfer and query, hence, I hope you could compare it with the results from the paper "Blackbox Attacks via Surrogate Ensemble Search. Neurips 2022."

questions:
Please see the weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730785032703

thread_type:
official_review

<thread_object>
creator: reviewer_dspd

<content>
summary:
The paper addresses the problem of hard-label black-box adversarial attacks. The paper builds on an existing approach that seeks the optimal ray direction from a benign image to minimize the distance to the adversarial region. While this method has shown promise, its high query cost remains a major drawback. A variation of this method that uses ‘signed gradient’ suffers from gradient accuracy limitation. To address these issues, the authors propose incorporating a transfer-based prior to reduce the query burden and improve performance. Additionally, they provide theoretical analysis of the gradient estimation quality achieved through this transfer-based prior and provide insight into its effectiveness.

strengths:
**Originality**: The concept of using transfer priors is not entirely new, as it was demonstrated in other works e.g., Dong et al. (2022). However, this paper's novelty lies in applying them to the more practical hard-label setting, where information is limited.

**Quality**: The methodology demonstrates technical soundness, particularly the idea of using transfer-based priors and then the approach to gradient approximation through closest projection on the subspace.  

**Clarity**: The writing could be further improved. Since the paper is based on previous work - Sign-OPT, it can be confusing for someone who is not well familiar with those works. The figures also make it hard to understand the key idea of the paper. In particular, the first figure is confusing as it has a lot of information which is unnecessary and does not motivate the problem or explain the idea well. 

**Significance**: The paper makes substantial contributions to adversarial machine learning by introducing a novel attack that leverages transfer-based priors in hard-label black-box setting. The paper demonstrates how this additional information from surrogate models can be effectively used.

weaknesses:
1. The main contribution of the paper seems to have limited novelty. It essentially boils down to employing Eq (7), which is similar to the Sign-OPT method but with the addition of using gradients from surrogate classifiers.
2. It seems that the results don't clearly favor one approach over another. In some cases, Prior-Sign-OPT performs well, while in others, Prior-OPT outperforms it. Lines 319-321 mention that Prior-OPT outperforms Sign-OPT under certain conditions, but these conditions are not clearly explained, so the reasoning is unclear.
3. Another concern is the inconsistent performance in targeted attacks. For instance, in Figures 10(g) and 10(h), the proposed methods are not among the top three, throughout the plots. In other cases, other methods perform equally well (especially for smaller number of queries), yet no explanation is provided for these discrepancies.
4. The method underperforms when the number of queries is small. For example, in Table 1, for the ViT experiments, other methods achieve lower mean L2 norm distortions with fewer queries. Specifically, for targeted attacks up to 5k queries, other methods generate adversarial examples with smaller perturbations as compared to the proposed methods.

questions:
1. **Lines 196-197**: The notation for qi (used for the transfer-based prior) and q (representing the total number of vectors) is confusing. It would help to revise the notation to make the distinction clearer and avoid confusion.

2. **Figure 1**: The figure is unclear and lacks proper labeling. Please add clear labels to define the regions and ensure the equations are more readable and understandable

3. **Figures 9 & 10, and Table 1**: These results highlight that using PGD (Projected Gradient Descent) significantly boosts performance. The question arises: How would the other methods perform if PGD were applied to them as well? Were there any experiments done to investigate that?

4. The results indicate that even adding a single transfer-based prior improves performance. However, it would be valuable to test an alternative where, instead of using random vectors, only prior vectors are used. Are there any experiments that investigate this scenario?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732527460911

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response to All the Reviewers

comment:
We appreciate the reviewers for dedicating their time and effort to provide insightful and constructive feedback on our paper. In response, we have carefully addressed each comment in detail. Additionally, we would like to: (1) summarize the primary contributions acknowledged by reviewers, and (2) outline the improvements made in the revised manuscript.

**Key Contributions Acknowledged by Reviewers:**

- **Novelty and Originality:**  Hard-label attacks are among the most challenging tasks, as they rely solely on the top-1 predicted label, making the limited information a significant obstacle. The proposed approach is grounded in a solid theoretical foundation, effectively addressing the non-differentiable issue associated with using binary search to obtain the priors. It further enables the application of transfer priors in a more practical hard-label setting through subspace projection approximation. To the best of our knowledge, this is the first work to derive the expected cosine similarity between the estimators of the OPT family (i.e., Sign-OPT, Prior-Sign-OPT, Prior-OPT) and the true gradient, offering a theoretical guarantee for improved performance. [cAs8,hzgv,DsPD,z4Ag]

- **Significance**: The paper makes substantial contributions to adversarial machine learning by introducing a novel attack that leverages transfer-based priors in hard-label black-box setting. The paper demonstrates how this additional information from surrogate models can be effectively used. [DsDP]

- **Clarity**: The paper is well-written, with geometrical intuitions effectively illustrated through detailed figures. [DsPD,z4Ag]

- **Quality**: The methodology demonstrates technical soundness, particularly the idea of using transfer-based priors and then the approach to gradient approximation through closest projection on the subspace.  [DsPD]


**Major Updates in the Revised Version**: Based on the reviewers’ suggestions, we made the following major revisions in the updated version of our paper:

- **Revised Figure**: We have updated Fig. 1, Fig. 2(c), and Fig. 2(d) by refining the adversarial region and adding clearer labels to enhance readability and comprehension.

- **Add Theoretical Condition under which Prior-OPT outperforms Sign-OPT**: We added the theoretical condition under which Prior-OPT outperforms Sign-OPT, along with the detailed derivation steps to support this condition. Specifically, we add a new section (Appendix D) to include the detailed steps of the derivation of this condition. This revision is highlighted in blue text in the revised manuscript (line 318-322, and Appendix D).

- **Add Time Complexity Analysis**: We have included a theoretical analysis of the time complexity for gradient estimation in Appendix F.1, with the revisions highlighted in blue text.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies black-box adversarial attacks in the hard-label setting, where only information on the top predicted class is available to the attacker. Devising successful attacks in this setting is difficult, as very little information is available to the adversary. Existing methods set up the problem via optimizing a problem that seeks the shortest path towards a region of a different label, but the resulting problem is discontinuous, incurs hard querying costs, and the resulting attacks might be limited. This work incorporates transfer-based priors to aid this optimization problem, in the form of the gradient of a surrogate model, using a subspace projection. The work theoretically analyzes these attacks, deriving the expected cosine similarity between the resulting estimations of the attacks and the true gradient. The paper also incorporates extensive numerical experiments, demonstrating state-of-the-art results.

All reviewers recognize that the strengths of this paper (the novelty in the transfer-prior formulation, theoretical analysis, and numerical results) are significant. Weaknesses noted include the lack of clarity in some figures and further clarification of details in the presentation. 

Overall, reviewers are supportive of this paper, and I concur.