TtBA: Two-third Bridge Approach for Decision-Based Adversarial Attack

We sincerely appreciate the reviewer's meticulous evaluation and valuable comments, which have greatly helped improve our manuscript.

1. The problem formulation is reasonable for two key reasons. First, in hard-label black-box attacks (e.g., HSJA, TA, CGBA), where only the model’s output label is available and gradient information is inaccessible, generating an initial adversarial example for a target label in targeted attacks is nearly impossible. As a result, these methods require a target image $y_{\text{target}}$ as the initial adversarial example. We will explicitly highlight this methodological distinction in our revision to prevent potential confusion for readers. Second, HSJA, TA, and CGBA all evaluate attack efficiency under this targeted setting in their experiments. To ensure a fair comparison, we adopt the same setting in our experiments.

2. We agree that the adversarial example definition should explicitly include clipping to [0,1]. This was properly implemented in our code but inadvertently omitted from the text. We will add this clarification in the revision. We sincerely thank the reviewer for carefully checking our code.

3. Following your valuable advice, we will carefully simplify Figure 1 in the revised paper.

4. Agreeing with the reviewer, in Figure 2 and 3, we observe that models without defense (i.e., undefended models) usually have decision boundaries with low curvature and large $k_{\text{bridge}}$, while robust models normally have high curvature and small $k_{\text{bridge}}$. The table below shows the relationship between average $k_{\text{bridge}}$ and average $\ell_2$ distortion for successful attacks on CIFAR100 and CIFAR10 datasets across undefended ViT, CNN, and defended WRN models. It demonstrates that robust WRN models generally have higher average $\ell_2$ distortion and lower $k_{\text{bridge}}$, suggesting that adversarially trained models are associated with high decision boundary curvature.

5. The sensitivity analysis in Tables 2 and 3 does not include adversarially robust models. Here we add a sensitivity analysis on robust models. By adjusting the hyperparameters of TtBA, it can certainly yield better performance for robust models, as demonstrated in the following table. Specifically, we modify the setting of $k = \check{b} \cdot k_\text{bridge}$ by varying the default value of $\check{b} = 2/3$ across {0.55, 0.575, 0.60, 0.625, 0.65, 2/3, 0.70}, and evaluate the AUC of two WRN models on the CIFAR-100 and TinyImageNet datasets. The results demonstrate that, for robust models, the setting $\check{b} = 0.625$ achieves the best performance in 3 out of 4 experiments, clearly surpassing the $\check{b} = 2/3$ setting. This difference likely arises because robust models can effectively conceal gradient information, causing normal vector estimation to become less reliable. Consequently, assigning a smaller weight to the normal vector can enhance the effectiveness of perturbation optimization.

Thank you for your comments.

1. SOTA studies, including HSJA, TA, CGBA, strongly support the hypothesis that the decision boundary of DNNs remains smooth and locally concave even for many robustly trained models. This is because the robust training process does not interfere with normal vector estimation. We conduct additional experiments using the Towards Robust Vision Transformer (RVT) defense from [1], which enhances ViT robustness with position-aware attention scaling and patch-wise augmentation. The corresponding decision boundary is plotted in a figure at [decision boundary of robustly trained models](https://anonymous.4open.science/r/TtBA-6ECF/ DecisionBoundaryofRobustViT.pdf). In the figure, the decision boundary remains smooth and locally concave.

   However, for input transformation-based defenses such as RandResizePad in [2], the normal vector estimation process can be disrupted. This causes the decision boundary to lose its smoothness, which is shown at abnormal decision boundary of RandResizePad. It is important to note that this issue is not specific to our approach. All normal vector-based attacks, including HSJA, TA, and CGBA, encounter similar challenges and currently lack effective solutions. Since addressing these specific challenges is beyond the primary scope of our study, we did not include experiments on transformation-based defenses in our evaluation.

   To strengthen our revised paper, we will expand the literature review to discuss attack methods specifically designed for input transformation-based defenses and highlight their differences from normal vector-based attacks. Additionally, we will update our future work section to explore potential extensions of our method to handle such defenses effectively.

2. We thank the reviewer for pointing out important attack methods such as BounceAttack and SQBA, which we have now incorporated in the literature review section.

• While BounceAttack improves upon HSJA by using orthogonal gradient components and introduces momentum/smooth search mechanisms, it does not address the local optima problem caused by high-curvature decision boundaries, which is the core focus of our work. We would gladly compare with BounceAttack, but the official code is currently inaccessible, preventing us from presenting detailed results.

• SQBA uses pre-trained surrogate models for gradient estimation and relies on access to the target model's training dataset. In contrast, our decision-based attacks assume no access to the training dataset. Therefore, a direct experimental comparison with SQBA will not be included. Thank you for your understanding!

3. The reduction in query complexity under the same perturbation budget is shown below. Following the setup of CGBA, we set the query budget to 10,000 and the maximum $\ell_2$ perturbation strength to $\epsilon = 2.5$. We then randomly choose 500 images from ImageNet and compare the Attack Success Rate (ASR) and the average (median) queries.

• The results show that TtBA achieves the highest ASR across all models. HSJA has the lowest average (median) number of queries, but this is due to its much lower ASR. As is well-known, some images contain robust features that require more queries to attack. TtBA, with significantly higher ASR, is able to successfully attack these robust images, thus requiring more queries on average. Meanwhile, with a similar ASR, TtBA outperforms CGBA in terms of average (median) queries. On ResNet-50, TtBA also achieves significantly higher ASR (61.8%) compared to CGBA (52.0%). We will include these results in our revised paper.

We believe we have satisfactorily addressed all the concerns raised in our rebuttal. If the reviewer agrees, would you please kindly consider adjusting your rating?

[1] Mao, Xiaofeng, et al. "Towards robust vision transformer." In Proceedings of the IEEE/CVF conference on Computer Vision and Pattern Recognition. 2022.

[2] Xie, C., Wang, J., et al. "Mitigating adversarial effects through randomization." In arXiv preprint arXiv:1711.01991.

1. Thank you for raising concerns regarding the strength of our contributions. We introduce a fundamentally new and practically valuable metric, $k_\text{bridge}$, specifically designed to quantify decision boundary curvature, a critical but previously unexplored factor in adversarial attacks. This metric reveals vital insights into how geometric properties of decision boundaries directly affect the effectiveness of decision-based attacks. Existing SOTA decision based attack methods such as HSJA, TA, qFool, GeoDA, QEBA, and CGBA overlook the critical issue of local optima caused by high-curvature boundaries, significantly reducing their attack effectiveness. Addressing this gap, we make three substantial contributions:

   (1) We propose $k_\text{bridge}$, the first quantitative metric in literature, to rigorously measure boundary curvature, enabling systematic analysis and deeper understanding of adversarial optimization.

   (2) Using insights from $k_\text{bridge}$, we uncover a previously unidentified linear relationship between boundary curvature and optimal perturbation directions. Leveraging this discovery, we develop the TtBA method for highly effective decision-based black-box attack.

   (3) We identify a low attack efficiency problem caused by high boundary curvature and propose a robust mechanism to detect and escape them, significantly enhancing optimization efficiency and attack success rates.

   Our extensive experiments across multiple widely-used datasets and models clearly demonstrate the substantial practical impact of our contributions, representing a significant advancement in adversarial machine learning. We will further clarify the above discussion in the revised paper.

2. While the setting $k=2/3k_\text{bridge}^{i}$ is empirically motivated, it is also supported by an extensive sensitivity analysis in Appendix G. Specifically, we analyze the sensitivity of our method to different settings of $k$ by varying the default value of $2/3$ across {0.55, 0.60, 0.65, 0.70, 0.75} in Table 2, and similarly adjusting other parameters in Table 3. Our results reveal two key findings: first, the current configuration achieves the best performance in 10 out of 16 experimental scenarios; second, alternative parameter values maintain comparable effectiveness. These results demonstrate that, while $k=2/3$ represents the most effective choice, TtBA's performance remains robust to parameter variations, ensuring methodological reliability across different configurations.

We believe we have satisfactorily addressed all the concerns raised in our rebuttal. If the reviewer agrees, would you please kindly consider adjusting your rating?

Thank you for your valuable comments.

1. We perform a binary search of $k = k_\text{bridge}^{i} \in (0,1]$ to identify $d_k = d_\text{bridge}^{i}$ which have identical decision boundary as $\hat{d}^{i}$.

• According to Figure 1, when $k$ is very small, direction $d_k$ approaches $\hat{d}^{i}$ and its decision boundary of $d_k$ is smaller than $\hat{d}^{i}$.

• When $k=1$, $d_k = \hat{N}^i$, its decision boundary is significantly larger than $\hat{d}^{i}$. By the intermediate value theorem, there must exist $k \in (0,1]$ such that $d_k$ yields the same decision boundary as $\hat{d}^{i}$. We will clarify the above in the revised paper.

2. Thank you for raising concern regarding the "brand-new insight". Our primary innovation lies in identifying and rigorously analyzing the previously unknown relationship between decision boundary curvature and the optimization of adversarial perturbations. Existing SOTA decision based methods (HSJA, TA, QEBA, and CGBA) have largely overlooked how boundary curvature influences the occurrence of local optima that seriously impacts optimization efficiency and effectiveness.

   In contrast, our work introduces a novel and practical curvature metric, $k_\text{bridge}$, which provides the first systematic means to quantify and interpret decision boundary geometry. This new understanding allows us to pinpoint precisely why and how adversarial attacks fail under certain geometric conditions, delivering useful insights previously missing from the literature.

   Leveraging this discovery, we developed TtBA, a significantly more effective and efficient decision-based attack method. Further, we introduced a robust mechanism specifically designed to detect and escape local optima induced by boundary curvature, directly addressing an important limitation unexplored by previous studies. In summary, rather than merely improving upon prior methods, our research introduces brand-new conceptual understanding and practical tools with significant contributions to the AI security field. We will further clarify the above discussion in the revised paper.

3. We acknowledge that the proposed techniques may appear conceptually simple at first glance. However, identifying critical yet overlooked issues, including the presence of local optima due to high-curvature decision boundaries, is far from trivial. Developing practical, intuitive, and effective solutions to address such issues further highlights the strength and novelty of our contributions. Hence, the simplicity of our solution does not diminish its novelty or importance; rather, it underscores the clarity and practical value of our research.

   The novelty of our technical contributions lies precisely in uncovering significant issues that have not received sufficient attention in existing literature. Despite extensive research, prior SOTA decision based methods have largely ignored how boundary curvature leads to local optimization traps that severely hinder adversarial attacks. Our research uniquely identifies this critical gap and proposes robust, intuitive, and demonstrably effective methods to address it.

   Therefore, while the proposed solutions might seem intuitive after being introduced, we argue that recognizing and formulating these specific problems and subsequently developing simple yet powerful techniques constitute substantial and novel contributions to the AI security community. We will further clarify the above discussion in the revised paper.

4. Our evaluation is rigorous, covering extensive experiments across five datasets and seven distinct model architectures, representing a comprehensive and highly challenging benchmark. It is noteworthy that consistently surpassing SOTA performance across all tests is exceptionally difficult, which is a challenge similarly faced by recent leading methods such as HSJA, TA, and CGBA. Despite this inherent difficulty, our method achieves substantial performance improvements. Specifically in Table 1, TtBA clearly outperforms existing SOTA methods in 103 out of 108 experimented scenarios, with few remaining cases closely matching the best performance.

   Furthermore, for robust models evaluated in Figure 5, we intentionally refrained from fine-tuning parameters to rigorously test our method's robustness and generalization capability. Even under this conservative setting, we demonstrated superior performance in 37 out of 40 cases. Additional targeted parameter tuning can further enhance the effectiveness of TtBA. However, we deliberately emphasized our method's strong general performance and broad applicability across diverse settings, thereby reinforcing the substantial practical value and robustness of our contributions.

We believe we have satisfactorily addressed all the concerns raised in our rebuttal. If the reviewer agrees, would you please kindly consider adjusting your rating?