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

Q2: The paper does not adequately address the scalability of the proposed method, particularly in scenarios involving larger models or more complex datasets.

A2: To evaluate the scalability of our proposed method, we conduct experiments of attacking a large CLIP with the backbone of ViT-B/32, and the surrogate models include ImageNet pretrained ResNet-50, ConViT, CrossViT, MaxViT, and ViT. It is worth noting that these surrogate models are pretrained on ImageNet and their training paradigms are entirely different from the CLIP model. The CLIP model with ViT-B/32 backbone was trained on 400 million image-text pairs from the internet by using contrastive learning, enabling it to generalize well via natural language supervision. The CLIP model can serve as a zero-shot image classifier by leveraging its ability to align images and text in a shared embedding space. We encapsulate it as a 1000-class image classifier by constructing a set of text prompts representing the classes (e.g., "a photo of a cat," "a photo of a dog") and embedding them into the same space as the image. During inference, the image is embedded, and the class with the highest similarity score between the image embedding and the text embeddings is selected as the predicted label.

The tested images consist of 6 randomly selected pictures downloaded from the Internet, making the data and target model both unseen. The results under a maximum query budget of 10,000 are summarized in the following tables.

Table 1: Attack Success Rate (ASR), average queries across all samples (with a query count of 10,000 assigned to unsuccessful samples), and the $\ell_2$ distortion of the final samples for untargeted attacks against CLIP on 6 randomly downloaded images. The surrogate models include ImageNet pretrained ResNet-50, ConViT, CrossViT, MaxViT, and ViT.

As demonstrated in the table, incorporating more surrogate models (priors) significantly enhances attack performance, highlighting the robustness and generalization of our method. Notably, even though the surrogate models are ImageNet-pretrained and their training methods differ entirely from those of the CLIP model, they still contribute to improved performance. Let us now conduct an analysis of the robustness of our method in real-world applications.

Generalization to Real-World Scenarios:

Adversarial example generation fundamentally relies on gradient vectors, which increase classification loss to induce misclassification. Our method and theoretical framework focus on the cosine similarity between two vectors: the estimated gradient and the true gradient. This ensures the universality of our approach across various image classifiers.

In real-world scenarios, a common challenge is the gradient discrepancy between surrogate and target models, which leads to differing gradient directions. Our approach addresses this issue through the $\alpha$ variable, defined in Eq. (11), Eq. (12), Eq. (15), Eq. (16), and Eq. (17). $\alpha$ represents the cosine similarity between the $i$-th prior and the true gradient and is a key component of our theoretical analysis, ensuring robustness in diverse environments.

Applicability to Modern Architectures and Datasets:

Modern state-of-the-art image classification networks, primarily based on CNNs and ViTs, dominate the field, with benchmarks such as ImageNet and CIFAR-10 serving as standard datasets. The leading models on the ImageNet leaderboard consistently rely on these architectures. This supports the relevance and applicability of our approach to prevailing real-world scenarios.

Q3: The reliance on transfer-based priors from surrogate models raises concerns about overfitting and the applicability of the method to unseen models or datasets.

A3: See A2.

We would like to thank the reviewer for the positive comments, and we shall carefully revise the paper following your suggestions.

Q1: The following work [1] (Policy Driven Attack, PDA) 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.

A1: Policy Driven Attack (PDA) is a method derived from HSJA with added pretraining modifications and relies on two types of surrogate models prior to performing the attack. The first is a traditional classifier, which is used to generate image-gradient pairs as training data. The second is a policy network, pre-trained on the generated data, which is subsequently utilized to predict the gradient during the attack. While effective in certain scenarios, PDA has two significant limitations when compared to our approach.

First, PDA requires a pretraining process, and its performance heavily depends on the surrogate model being highly similar or identical to the target model. If the surrogate model differs substantially from the target model, the policy network may struggle to predict accurate gradients, leading to degraded attack performance. This is a fundamental limitation, as hard-label attacks are designed to operate in a black-box setting. If gradients from the target model are accessible for pretraining, the attack essentially transitions into a white-box setting, undermining the essence of a black-box attack and rendering the claimed novelty less meaningful.

Second, PDA employs reinforcement learning during the attack phase for fine-tuning, which is computationally expensive and time-consuming. This significantly impacts the practicality and efficiency of PDA, especially in scenarios requiring a large number of attacks or real-time constraints.

In contrast, our approach, Prior-OPT, does not require pretraining of a policy network or any fine-tuning steps. This makes it simpler, more efficient, and easier to deploy. Unlike PDA, Prior-OPT avoids the use of reinforcement learning, making it less computationally intensive. Furthermore, when there is a significant discrepancy between the surrogate model and the target model, our gradient estimation mechanism adaptively assigns a lower weight to the surrogate gradient, mitigating the impact of model mismatch.

Therefore, PDA and Prior-OPT are fundamentally different methods. Theoretical analysis further supports that our approach guarantees a lower bound on the expected cosine similarity of the estimated gradient, ensuring its reliability and effectiveness in diverse settings.

We would like to thank the reviewer for the positive comments, and we shall carefully revise the paper following your suggestions.

Q1: The paper benefit from showing the time complexity.

A1: The primary additional computational cost of Prior-OPT compared to Sign-OPT arises from the binary search procedure performed on the priors during gradient estimation. Let $d$ represent the dimension of the input image, $q$ the number of vectors used in gradient estimation, and $f(d)$ the inference time of the target model for an input of dimension $d$. The time complexity of gradient estimation in Sign-OPT is $O(q \cdot f(d))$. In Prior-OPT, $s$ priors are introduced. Each prior requires a binary search procedure, which involves approximately $k$ inference steps. While $k$ may vary slightly depending on the specific prior or the input configuration, its value generally remains bounded and logarithmic in scale, given the nature of binary search. Consequently, the time complexity of the gradient estimation step of Prior-OPT can be expressed as:

$O((q-s+(s+1)\cdot k)\cdot f(d) + s \cdot \hat{f}(d)).$

When $q$ is large, $s$ and $k$ is relatively small (i.e., the number of priors is small, and $k$ typically ranges in the tens), $s \cdot \hat{f}(d)$ denotes the time of taking $s$ priors, the additional overhead introduced by Prior-OPT is limited compared to Sign-OPT. While Prior-OPT introduces extra computation due to the binary search procedure on the priors, the increase in time complexity is relatively modest, especially when $s$ remains much smaller than $q$. This demonstrates that Prior-OPT achieves a balance between computational efficiency and improved gradient estimation. We add this analysis in Appendix F.1.

Table 12 in Appendix F.1 of our paper presented the time required to attack a single image using 10,000 queries, measured in seconds on a NVIDIA Tesla V100 GPU. For further details, please refer to Appendix F.1. Below, we paste the summary of time overhead results from Appendix F.1.

Table 1: The time consumptions of attacking one image with 10000 queries, which are measured by seconds on a NVIDIA Tesla V100 GPU.

Q2: This paper conducts a comprehensive study on transfer and query attacks. I suggest comparing your results with those from "Blackbox Attacks via Surrogate Ensemble Search (BASES)" (NeurIPS 2022).

A2: Thank you for your suggestion. While BASES primarily employs a score-based attack method, and it is not a typical hard-label attack. It leverages a set of surrogate models to generate adversarial examples, which are then transferred to hard-label models.

We perform untargeted and targeted attack experiments with BASES on 100 images from the ImageNet dataset. The attack success rates (ASR) are summarized in the following tables, where the surrogate model set includes ResNet-50, SENet-154, ResNeXt-101 (64 × 4d), VGG-13, SqueezeNet v1.1 for attacking against ResNet-101, and ResNet-50, ConViT, CrossViT, MaxViT, ViT for attacking against GC ViT and Swin Transformer. The victim surrogate model is VGG-19 in BASES.

Table 2: The attack success rate of untargeted attack of 100 images on the ImageNet dataset.

Interestingly, our approach can integrate BASES as an initial sample during initialization, denoted as $\text{{Prior-Sign-OPT}}_\text{{5 priors}}$ + BASES, as shown the following table, further enhancing performance.

Table 3: The attack success rate of targeted attack of 100 images on the ImageNet dataset.

Thanks for your response. I have updated the score to 6.

Thank you for acknowledging the value of our hard-label attack and for increasing your score!

We have updated the latest experimental results for "Prior-Sign-OPT + BASES" in the table provided in our previous response. By integrating BASES as a plugin to generate an initial sample during attack initialization, our approach further enhances performance. Notably, Prior-Sign-OPT + BASES achieves the highest attack success rate among all methods. Please see the updated table for details.

Also, we report the attack success rate (ASR) under the specific query budget, which is defined as the percentage of samples with distortions below a threshold $\epsilon$. In $\ell_2$ norm attacks, we set the threshold $\epsilon = \sqrt{0.001 \times d}$ on the ImageNet dataset, where $d$ is the image dimension.

Table 5: Attack Success Rate (ASR) under different query budgets of untargeted attacks against Inception-V4 on the ImageNet dataset.

Table 6: Attack Success Rate (ASR) under different query budgets of untargeted attacks against ResNet-101 on the ImageNet dataset.

Table 7: Attack Success Rate (ASR) under different query budgets of untargeted attacks against GC ViT on the ImageNet dataset.

We would like to thank the reviewer for the positive comments, and we shall carefully revise the paper following your suggestions.

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

A1: In query-based attacks, the term efficiency refers to query efficiency, which evaluates the performance of the proposed method in two aspects:

(1) for a fixed number of queries, the reduction in distortion or the improvement in attack success rate;

(2) for a fixed number of iterations, the average number of queries required to successfully attack all samples. These metrics provide a comprehensive measure of the method's efficiency in enhancing the ray search process.

Throughout our paper, we have presented extensive experimental results (Tables 1, 2, 14, 15, 16, 17, and Figures 3, 4, 7, 8, 9, 10, 11, 12) to illustrate the query efficiency advantages of our approach.

Now, we present the additional experimental results as following tables, which will be added to the revised version of our paper.

Table 1: Attack Success Rate (ASR), average successful queries of all samples , and the $\ell_2$ distortion of final sample on the untargeted attacks against Swin Transformer on the ImageNet dataset.

Table 2: Attack Success Rate (ASR), average successful queries of all samples, and the $\ell_2$ distortion of final sample on the untargeted attacks against GC ViT on the ImageNet dataset.

Table 3: Attack Success Rate (ASR), average successful queries of all samples, and the $\ell_2$ distortion of final sample on the untargeted attacks against ResNet-101 on the ImageNet dataset.

We report the average queries of 1000 samples as the following table, where the query times of failed samples are recorded as 10,000.

Table 4: Average successful queries on the ImageNet dataset.

Q8: The results show that adding a single transfer-based prior improves performance. Would it be useful to test using only prior vectors instead of all random vectors?

A8: If all random vectors are eliminated in gradient estimation, the gradient estimator's performance lacks a lower bound, making it unable to guarantee accuracy in the worst-case scenario. However, when random vectors are included in the gradient estimation, the accuracy of the estimator is ensured to have a lower bound. This means that, regardless of how poor the priors are, the estimator maintains a guaranteed minimum level of performance in the worst case.

This can be verified through the formulas for $\mathbb{E}[\gamma]$ and $\mathbb{E}[\gamma^2]$ derived for Prior-Sign-OPT and Prior-OPT.

Specifically, in Prior-Sign-OPT, $\mathbb{E}[\gamma]$ is given by:

$\mathbb{E}[\gamma] = \frac{1}{\sqrt{q}}\left[\sum_{i=1}^s|\alpha_i|+(q-s)\sqrt{1-\sum_{i=1}^s \alpha_i^2} \cdot \frac{\Gamma(\frac{d-s}{2})}{\Gamma(\frac{d-s+1}{2})\sqrt{\pi}}\right]$, where $\alpha_i$ denotes the cosine similarity between the $i$-th prior and the true gradient, $s$ is the number of priors, and $q$ is the total number of vectors. When all random vectors are removed in Prior-Sign-OPT, we set $q = s$, and the formula reduces to:

$\mathbb{E}[\gamma] = \frac{1}{\sqrt{q}}\left[\sum_{i=1}^s|\alpha_i|\right].$

In this case, $\mathbb{E}[\gamma]$ depends solely on $\alpha_i$, which reflects the accuracy of the priors. If $\alpha_i$ is extremely low, the accuracy of the estimated gradient degrades significantly. Similarly, when we remove all random vectors in Prior-OPT and set $q=s$, the formula of $\mathbb{E}[\gamma]$ reduces to:

$\mathbb{E}[\gamma] \ge \sqrt{\sum _ {i=1}^s \alpha _ i^2}.$

This demonstrates that, without random vectors, the gradient estimation is entirely reliant on the quality of the priors (i.e., the $\alpha_i$ value), and poor priors can result in arbitrarily poor performance. Conversely, when random vectors are included, the formula involving random vectors ensures a lower bound for $\mathbb{E}[\gamma]$. This lower bound can be derived by setting $\alpha_i=0$ in the above formula. For Prior-Sign-OPT, the lower bounds of $\mathbb{E}[\gamma]$ and $\mathbb{E}[\gamma^2]$ are

$\mathbb{E}[\gamma] \ge \frac{q-s}{\sqrt{q}} \cdot \frac{\Gamma(\frac{d-s}{2})}{\Gamma(\frac{d-s+1}{2})\sqrt{\pi}},$

$\mathbb{E}[\gamma^2] \ge \frac{1}{q}\left(\frac{q-s}{d-s} \left( \frac{2}{\pi} (q-s-1)+1\right)\right).$

For Prior-OPT, the lower bounds of $\mathbb{E}[\gamma]$ and $\mathbb{E}[\gamma^2]$ are

$\mathbb{E}[\gamma] \ge \sqrt{\frac{q-s}{\pi}} \cdot \frac{\Gamma(\frac{d-s}{2})}{\Gamma(\frac{d-s+1}{2})},$

$\mathbb{E}[\gamma^2] \ge \frac{1}{d-s}\left(\frac{2}{\pi} (q-s+1)+1 \right),$

thereby providing robustness even when the priors are of low quality.

Furthermore, in Prior-OPT's gradient estimation, each prior requires a binary search, whereas random vectors do not. Random vectors need only a single query per vector, making them more efficient in this regard.

We present targeted attack results on 100 images using only priors with the Prior-Sign-OPT and Prior-OPT algorithms, referred to as "Pure-Prior-Sign-OPT" and "Pure-Prior-OPT", respectively, in the following tables.

Table 5: The results of targeted attacks against GC ViT on the ImageNet dataset.

Based on the above results, Pure-Prior-Sign-OPT and Pure-Prior-OPT fail to outperform Sign-OPT, which relies solely on random vectors without incorporating priors. Moreover, as the query budget increases, the distortion achieved by these methods decreases very slowly or remains nearly unchanged, highlighting their inefficiency in utilizing additional queries to improve attack effectiveness.

Q7: 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?

A7: We conduct additional experiments on 100 tested images to investigate the impact of using the PGD attack on a surrogate model to generate initial adversarial examples for enhancing the performance of SQBA and BBA attacks. The results of these experiments are presented below.

Table 1: The mean distortion across 100 images under different query budgets of attacking against GC ViT on the ImageNet dataset.

Table 2: The mean distortion across 100 images under different query budgets of attacking against ResNeXT-101(64x4d) on the ImageNet dataset.

Table 3: The mean distortion across 100 images under different query budgets of attacking against Inception-V3 on the ImageNet dataset.

Table 4: The mean distortion across 100 images under different query budgets of attacking against Inception-V4 on the ImageNet dataset.

From the results above, we conclude that while PGD initialization enhances all methods, our Prior-OPT and Prior-Sign-OPT achieve significantly lower distortions, thereby delivering the best performance among all attacks.

Q4: The method underperforms when the number of queries is small. For example, in Table 1, for the ViT experiments, other methods achieve lower mean $\ell_2$ 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.

A4: The observed underperformance of our method is highlighted in Table 1 for the ViT's targeted attack experiments under low query budgets. The limitation arises from a trade-off inherent in our approach. Specifically, our method prioritizes gradient estimation accuracy through a prior-based mechanism, which becomes increasingly effective as the number of queries grows. However, when the query budget is small, the priors require sufficient queries during the binary search phase to influence the attack's query efficiency. This limitation is particularly pronounced in targeted attacks, where the accuracy of priors is significantly reduced, resulting in performance closer to that of Sign-OPT (as discussed in A3). Another possible reason is the complexity of optimization, and we will investigate this reason in the future work.

To address this issue, we propose integrating a dimension reduction step during the sampling phase of gradient estimation, inspired by the QEBA approach. This modification is straightforward, requiring only minor changes in the sampling process. Specifically, the method involves initially sampling random vectors in a reduced-dimensional space, followed by resizing these vectors to match the original input dimension. Preliminary experimental results show that this technique can reduce the distortion by approximately half in both untargeted and targeted attacks.

Notably, dimension reduction techniques are also employed in other state-of-the-art methods, such as AHA, SurFree, and Triangle Attack, demonstrating their effectiveness in improving performance in low-query settings. We believe that incorporating this enhancement into our method will enable it to achieve competitive, if not superior, performance across all query budgets. We plan to explore this approach in greater detail as part of our future work.

Q5: Lines 196-197: The notation for $\mathbf{q}_i$ (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.

A5: Thank you for pointing this out. The fonts of $\mathbf{q}_i$ and $q$ are indeed different. Specifically, $\mathbf{q}_i$ is in bold font, typically representing a vector, and in our case, it is used to denote transfer-based priors. In contrast, $q$ is in normal font, representing a scalar. To improve clarity and avoid confusion in notation, we will revise our paper to replace $q$ with $n$.

Q6: 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.

A6: Thank you for your feedback. We have revised the paper to include clearer labels in Figure 1, making the regions and equations more readable and understandable. Please refer to the updated PDF file for the revised figure.

We would like to thank the reviewer for the positive comments, and we shall carefully revise the paper following your suggestions.

Q1: Is the main contribution of the paper a limited novelty, essentially applying Eq (7), similar to the Sign-OPT method, with the added use of gradients from surrogate classifiers?

A1: Compared to the original Sign-OPT, Prior-Sign-OPT is based on the orthogonal vectors constructed through Gram-Schmidt orthogonalization. It approximates the subspace projection to achieve a more accurate gradient estimation, which optimizes its query efficiency. Prior-Sign-OPT represents an initial step in the development of Prior-OPT, serving as a preliminary stage rather than the final algorithm. Notably, the gradient estimation formula of Prior-OPT (Eq. (13)) is fundamentally different from that of Sign-OPT (Eq. (8)).

Additionally, the effectiveness of Prior-OPT and Prior-Sign-OPT is rigorously demonstrated through extensive theoretical analysis and comprehensive experimental validation.

To the best of our knowledge, this is the first work to derive the expected cosine similarity between estimators of the OPT family (i.e., Sign-OPT, Prior-Sign-OPT, Prior-OPT) and the true gradient, providing a theoretical guarantee for performance improvement.

Q2: Lines 319-321 mention that Prior-OPT outperforms Sign-OPT under certain conditions, what are the conditions under which Prior-OPT surpasses Sign-OPT?

A2: The effectiveness of Prior-OPT is analyzed through the expected squared cosine similarity $\mathbb{E}[\gamma^2]$ between the estimated gradient and the true gradient.

For Sign-OPT, $\mathbb{E}[\gamma^2] = \frac{1}{d}\left(\frac{2}{\pi}(q-1)+1\right)$.

For Prior-OPT, $\mathbb{E}[\gamma^2] = \sum_{i=1}^{s} \alpha_i^2+\frac{1}{d-s}\left(\frac{2}{\pi}(q-s-1)+1\right)\left(1-\sum_{i=1}^{s} \alpha_i^2\right)$, where $\alpha_i$ is the cosine similarity between the $i$-th prior and the true gradient, $s$ is the number of priors, $q$ is the number of number of queries (also the number of sampled vectors), and $d$ is the dimension of the input image.

Conditions for Prior-OPT to Outperform Sign-OPT:

Prior-OPT surpasses Sign-OPT when the following inequality holds:

$\sum _ {i=1} ^ s \alpha _ i^2 > \frac{\frac{1}{d} \left(\frac{2}{\pi}(q-1)+1\right) - \frac{1}{d-s}\left(\frac{2}{\pi}(q-s-1)+1\right)}{1-\frac{1}{d-s}\left( \frac{2}{\pi} (q-s-1)+1\right)}$

To simplify this inequality, under the assumption that $s \ll q \ll d$, the right-hand side approximates to $\frac{2s}{\pi d}$. Thus, the condition simplifies to:

$\sum _ {i=1} ^ s \alpha _ i^2 > \frac{2s}{\pi d}$

Equivalently, the average squared cosine similarity must satisfy:

$\overline{\alpha^2}>\frac{2}{\pi d}$

Since $\frac{2}{\pi d}$ is typically a very small value due to the large input dimension $d$, this threshold is relatively easy to satisfy. Therefore, Prior-OPT generally outperforms Sign-OPT when the priors have even a minimal level of informativeness (non-zero $\alpha_i$).

The detailed derivation steps of above conclusion is in Appendix D of our paper.

Q3: Why is the performance inconsistent in targeted attacks? For example, in Figures 10(g) and 10(h), the proposed methods are not among the top three, and in some cases, other methods perform equally well with fewer queries.

A3: Our method is an improvement based on Sign-OPT, which still significantly outperforms Sign-OPT in Fig. 10(g) and Fig. 10(h). However, since Sign-OPT performs considerably worse than the best methods in targeted attacks against GC ViT and Swin Transformer, our method also falls short of surpassing the best methods in these specific cases. Nevertheless, our method demonstrates superior performance in most other scenarios, as shown in Fig. 10(a) to Fig. 10(f).

In targeted attacks, the gradient direction must specifically point toward a narrow adversarial region corresponding to the target class. This constraint tends to reduce the cosine similarity $\alpha_i$, often leading to $\alpha_i \approx 0$ for $i\in[1,s]$. In such cases, when $s\ll q$, the expected squared cosine similarity $\mathbb{E}[\gamma^2]$ for both Sign-OPT and Prior-OPT becomes approximately equal, reducing the advantage of using priors. Consequently, the performance of Prior-OPT converges to that of Sign-OPT in targeted attack scenarios.

Furthermore, in targeted attacks, Prior-Sign-OPT employs a more query-efficient approach by leveraging the sign of directional derivatives, requiring only a single query per sampled vector. In contrast, Prior-OPT involves multiple binary search steps (as described in Eq. (13)), which significantly increases query costs. This efficiency allows Prior-Sign-OPT to maintain higher performance under limited query budgets in targeted attacks.

Another possible explanation is the increased complexity of the optimization process in targeted attacks. This aspect warrants further investigation in future work.

Further Explanation Regarding the Concern in A1

A1+: Thank you for your thoughtful comments and for highlighting these points.
We would like to provide additional explanation of the differences between Prior-OPT and OPT to address your concerns.

First, the formulation of Prior-OPT (Eq. (13)) is not identical to OPT. In Eq. (13), the last term involves the $\ell_2$ normalization of $\mathbf{v} _ \perp$, where $\mathbf{v} _ \perp = \sum_{i=1}^{q-s} \text{sign}({g(\theta + \sigma \mathbf{u}_i) - g(\theta)}) \cdot \mathbf{u}_i$ and $\mathbf{u} _ {1},\cdots,\mathbf{u} _ {q-s}$ are orthogonal random vectors. As a result, Prior-OPT employs more precise finite difference estimations for the prior terms (the first term), while relying on sign-based estimation for the random vector components. This distinction arises because random vectors $(\mathbf{u} _ {1},\mathbf{u} _ {2},\cdots)$ have identical distributions in $d$-dimensional space, leading to relatively consistent cosine similarity with the true gradient. Given the approximation $\nabla g(\theta)^\mathsf{T} \mathbf{u} \approx \frac{g(\theta + \sigma \mathbf{u}) - g(\theta)}{\sigma}$, it is reasonable to replace $\nabla g(\theta)^\mathsf{T} \mathbf{u} _ i$ with $\text{sign}(\nabla g(\theta)^\mathsf{T} \mathbf{u} _ i)$ since magnitudes (absolute values) of these inner products do not vary significantly across random directions. As a result, the coefficients of random vectors can be set to uniform magnitudes ($+1$ or $-1$) to reduce the number of queries. In contrast, the cosine similarity between the prior direction $\mathbf{p}_i$ and the true gradient $\nabla g(\theta)$ is unknown and may differ significantly from that of the random directions. Thus, the coefficients for priors requires a more precise estimation, necessitating a separate binary search procedure. Therefore, Prior-OPT goes beyond a simple modification of OPT by directly adding priors, as it fundamentally handles priors and random directions differently to address these challenges.

Second, regarding the orthogonalization in high-dimensional spaces, while we agree that a small number of randomly sampled vectors ($\ll d$) are approximately orthogonal, this is not always the case for multiple priors. Priors derived from potentially correlated models are less likely to be orthogonal to each other. If the Gram-Schmidt orthogonalization is removed, the gradient estimate obtained using Eq. (7) and Eq. (13) may become less accurate, potentially degrading performance. Furthermore, the expected formulas ($\mathbb{E}[\gamma]$ and $\mathbb{E}[\gamma^2]$) derived from our theoretical analysis would no longer hold in such scenarios.

We appreciate your perspective that the main contribution lies in incorporating priors into the OPT or Sign-OPT framework, supported by theoretical proof. However, we believe these key differences in handling priors and random directions, along with the role of orthogonalization, contribute to the deeper understanding of our approach.

About A2:

The condition under which Prior-OPT surpasses Sign-OPT, along with its derivation, have been verified. Thank you for the clarification. I have reviewed the detailed proof in the appendix, and it is clear.

Response to Follow-Up Suggestion of A3

A3+: Thanks for your suggestion. Yes, we will include this explanation in Appendix in the final version.

Response to the Follow-Up Question of A4

Q4+: (1) Why does the proposed approach achieve high attack accuracy but require a large mean $\ell _ 2$​-norm for low query budgets? (2) For higher query budgets, why do other methods perform comparably?

A4+: (1) In targeted attacks on ViT, while priors become less effective for certain samples, they remain useful for a considerable proportion of samples. This contributes to the higher ASR of Prior-OPT in the early stages of attacks (low query budgets) (see Fig. 10(f)). However, for the remaining samples, the limited effectiveness of priors makes it more challenging for Prior-OPT to succeed. In contrast, Prior-Sign-OPT leverages a gradient estimation technique that requires fewer queries to achieve high ASR. This distinction explains why Prior-Sign-OPT outperforms Prior-OPT in the later stages of the attack (see Fig. 10(f)).

It should be noted that in the difference between the calculation methods of attack success rate (ASR) and mean $\ell _ 2$ distortion. ASR represents the proportion of successfully attacked samples, whereas mean $\ell _ 2$ distortion is the average distortion across all samples. Our approach achieves a high ASR under low query budgets because it successfully attacks a large number of samples. However, a small subset of samples exhibits relatively high $\ell _ 2$ distortion, which increases the overall mean distortion.

This is analogous to a group of students in a class where most students perform well and pass the exam (high ASR), but a few students with very low scores lower the class's average grade (high mean $\ell _ 2$ distortion).

In fact, in the targeted attack on ViT shown in Table 1, the mean $\ell _ 2$ distortion of our \text{Prior-Sign-OPT} _ \text{{ResNet50\\&ConViT}} is very close to that of the best-performing TA method: 53.925 vs 52.110 in 1K queries, 38.418 vs 36.455 in 2K queries, and 20.673 vs 20.536 in 5K queries. These differences are minimal.

(2) This is because other methods converge significantly slower than our approach. For example, in Fig. 9(a), Prior-OPT converges much faster than other methods. When the query budget reaches its maximum (10K), SQBA gradually converges to a similar minimum distortion, as shown in Fig. 9(a).

Thus, while some methods can eventually achieve a similar minimum distortion on certain models, their convergence rate remains considerably slower compared to our approach. Convergence rate is important because, in practice, query budgets are often limited, especially when only a very small number of queries is allowed.

Additionally, in Fig. 9(a), \text{{Prior-Sign-OPT}} _ \text{{ResNet50\\&ConViT}} is highly effective across both low and high query budgets, consistently achieving the lowest distortion due to its PGD-based initialization.

We will incorporate these explanations into the final version of our paper.

Response to the Additional Suggestion in A6

Q6+: The figure remains unclear. I would suggest to label points or areas with single letters and include a legend explaining each label. This will better convey the key idea of the method.

A6+: We will make a revision to our figure in the final version.

Response to the Follow-Up Question of A7

Q7+: The addition is valuable, but it does not convey the whole picture. It would be ideal to include attack success rates. Please consider adding these results in the appendix for the final version of the paper to make the paper more comprehensive.

A7+: Thank you for your valuable suggestion to improve our paper. We will include the attack success rates of SQBA (PGD) and BBA (PGD) in the final revised version. Due to time constraints, the experiments are still ongoing. We will provide the results in the final version once the programs are fully completed.

Response to the Follow-Up Question of A8

Q8+: How likely is it to encounter bad priors? I assume a bad prior would align with the gradient direction that increases the correct class confidence rather than decreasing it. This could have been clarified through experiments, but with only L2 norm information provided, it is difficult to draw conclusions.

A8+: As you mentioned, the likelihood of encountering bad priors needs to be validated through experiments. However, even if bad priors are encountered, their impact is negligible due to the properties of the method, as demonstrated below.

Let us consider the case where a "bad prior vector" is exactly the negative of the true gradient, which would increase the confidence of the correct class rather than decreasing it.

For Prior-Sign-OPT, the prior-related term in the gradient estimation formula (Eq. (7)) is:

$\sum _ {i=1}^{s} \text{sign}(g(\theta + \sigma \mathbf{p} _ i) - g(\theta))\cdot \mathbf{p} _ i,$

and for Prior-OPT, the prior-related term in the gradient estimation formula (Eq. (13)) is:

$\sum _ {i=1}^{s} \frac{g(\theta + \sigma \mathbf{p} _ i) - g(\theta)}{\sigma} \cdot \mathbf{p} _ i.$

In both formulas, under the assumption of $\nabla g(\theta)^\mathsf{T} \mathbf{p} _ i \approx \frac{g(\theta + \sigma \mathbf{p} _ i) - g(\theta)}{\sigma}$, if we replace $\mathbf{p}_i$ with $-\mathbf{p}_i$, the final output remains unchanged. This result can also be verified through our theoretical analysis. In Eqs. (11), (12), (15), (16), and (17), the expectations $\mathbb{E}[\gamma]$ and $\mathbb{E}[\gamma^2]$ depend only on $|\alpha _ i|$ or $\alpha _ i^2$. Therefore, even if $\alpha_i$ changes to $-\alpha_i$, the expectations remains the same.

Q9: In Appendix D, line 1420, $q$ is mentioned as the number of queries, while in the main paper, it is number of total vectors.

A9: In our paper, $q$ consistently represents the total number of vectors used in gradient estimation. The reference to $q$ as the number of queries in line 1420 of Appendix D is a typo, and we sincerely apologize for the oversight. This typo has been corrected in the updated version. As mentioned in A5, to help readers clearly distinguish between $\mathbf{q}_i$ and $q$, we will replace $q$ with $n$ in the final version of the paper.

Finally, we would like to sincerely thank the reviewer for your valuable and insightful comments, which have significantly contributed to enhancing the quality of our paper. We will carefully address and incorporate your suggestions into the final version.