TtBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
Authors: Feiyang Wang
Xingquan Zuo
Hai Huang
Gang Chen
Venue: ICML 2025 poster (2025)
Keywords: Adversarial Attacks
Black Box Adversarial Attacks
Hard Label Attacks
Decision-Based Attacks
Machine Learning Security
Artificial Intelligence Security
Robustness
Primary area: deep_learning->robustness
TL;DR: We propose a novel Two-third Bridge Attack (TtBA) for decision-based black-box attack.

Abstract: A key challenge in black-box adversarial attacks is the high query complexity in hard-label settings, where only the top-1 predicted label from the target deep model is accessible. In this paper, we propose a novel normal-vector-based method called Two-third Bridge Attack (TtBA). A innovative bridge direction is introduced which is a weighted combination of the current unit perturbation direction and its unit normal vector, controlled by a weight parameter $k$. We further use binary search to identify $k=k_\text{bridge}$, which has identical decision boundary as the current direction. Notably, we observe that $k=2/3 k_\text{bridge}$ yields a near-optimal perturbation direction, ensuring the stealthiness of the attack. In addition, we investigate the critical importance of local optima during the perturbation direction optimization process and propose a simple and effective approach to detect and escape such local optima. Experimental results on MNIST, FASHION-MNIST, CIFAR10, CIFAR100, and ImageNet datasets demonstrate the strong performance and scalability of our approach. Compared to state-of-the-art non-targeted and targeted attack methods, TtBA consistently delivers superior performance across most experimented datasets and deep learning models. Code is available at https://anonymous.4open.science/r/TtBA-6ECF.

TtBA: Two-third Bridge Approach for Decision- Adversarial Attack
Feiyang Wang" 12
Xingquan Zuo
Hai Huang 12 Gang Chen 3
Abstract
across wide range of real-world applications, they remain significantly vulnerable to adversarial attacks (Biggio et al., 2013; Brendel et al., 2018; Park et al., 2024). Research on these attacks is pivotal in advancing the development of attack-resistant DNNs in the future (Bai et al., 2023).
A key challenge in black-box adversarial attacks is the high query complexity hard-label set- tings, where only the top-1 predicted label from the target deep model is accessible. In this paper, we propose novel normal-vector-based method called Two-third Bridge Attack (TiBA). A inno- vative bridge direction is introduced which is a weighted combination of the current unit pertur- bation direction and its unit normal vector, con- trolled by a weight parameter k. We further use binary search to identify & khridge which has identical decision boundary the current direc- tion. Notably, we observe that &o 2/3kurdde yields a near-optimal perturbation direction, en- suring the stealthiness of the attack. In addi- tion, we investigate the critical importance of lo- cal optima during the perturbation direction op- timization process and propose simple and ef- fective approach detect and escape such lo- cal optima. Experimental results on MNIST, FASHION-MNIST CIFAR 10, CIFAR106 and ImageNet datasets demonstrate the strong perfor- mance and scalability of our approach. Compared to state-of-theearr art non- non-targeted and targeted at- tack methods, TtBA consistently delivers superior performance across most experimented datasets and deep learning models. Code is available at https: //ggggtthh//////
Adversarial attack approaches are generally classified into three categories: white-box attacks (Goodfellow et al., 2015; Madry et al., 2018), gray-box attacks (soft-label attacks, score-based attacks) (Chen et al., 2017; Liu et al., 2019a), and black-box attacks (Brendel et al., 2018; Chen & Gu, 2020). White-box and gray-box attacks rely on complete or partial knowledge of the target model, such as its architec- ture, trainable parameters, or output probabilities, which often impractical in real-world settings (Long et al., 2022). As a more practical alternative, black-box attacks are typi- cally divided into transfer- based attacks and decision-bait -based attacks. Transfer-based attacks (Feng et al., 2022; Ghosh et al., 2022; Fan et al., 2024; Wang et al., 2024; Sun et al., 2024; Park et al., 2024) train a surrogate model using the tar- get model's 's training data. Adversarial examples are crafted using white-box attack methods on this surrogate model. However, the success of this approach is not guaranteed, due to unreliable transferability of adversarial examples (Reza et al., 2023).
Significance of decision- based attacks. Decision-based attacks (Brendel et al., 2018; Li et al., 2021; Shi et al., 2022; Chen et al., 2020; Chen & Gu, 2020; Reza et al., 2023) do not rely on specific details of the target DNN, such as training data, network structure, or output probabilities. In- stead, adversarial examples crafted using only feedback from the DNN's top-1 predicted label, which is the class with the highest confidence score assigned by the model. This makes decision-haseee attacks the most popular strategy in practice (Dong et al., 2019; Brunner et al., 2019) and the key focus of this paper. Decision- deceive the target DNN (c.g., an image classifier) with min- imal perturbation strength while adhering to a predefined query budget (Brendel et al., 2018), To improve efficiency, these attacks focus on optimizing adversarial examples by exploring perturbation directions and their corresponding decision boundaries (see Appendix A for more details).
BA.
1. Introduction
Background and motivation. Although deep neural net- works (DNNs) have demonstrated remarkable performance
attacks aim to
School of Computer Science, Beijing, University Posts and Tedecommunications, Beijing, China ? Key Laboratory of Trustworthy Distributed Computing and Services, Ministry of Edu- cation, Beijing, China 'School of Engineering and Computer Sci- ence, Victoria University of Wellington, Wellington, New Zealand. Correspondence to: Xingquan Zuo <zuoxq @ bupt.edu.cn>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Normal bastor attacks. Many decision based adver- sarial attacks, such as HSJA (Chen al., 2020), Tangent

---

TIBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
Adversarial region
Adversarial region
Non-adversarial region
Non-adversarial region
d
d
de
dridgg
Gridge
X
X
(a) Calculation of karigg and chriatg:
(b) Calculation of d and
Figure 1. geometric illustration of iteration TIBA. In (a), the i-th iteration, represents the original image, d' is the unit vector of the current perturbation direction, &' is the boundary point along d', N is the unit normal vector at .' and Khecal denotes the local best adversarial example. We define direction de k No + (1 k) d' where k (0, is weight parameter. Using binary search, we can identify k kindge such that the direction dhingge kaidge N' + (1 kenage) df has identical decision boundary as d', i.e. g(dhnitg)) = g(d"). We then use k = 2/ 2/3kindge to generate the next direction directly: d = 2/ 2/3kivitg= N + (1 (1-2/3kmna) 2233kmaag)) d' as shown in (b). The boundary point +
((d 1. di+l produces the next adversarial example.
Attack (TA) (Ma et al., 2021), GeoDA (Rahmati et al., 2020), QEBA (Li et al., 2020), and CGBA (Reza al., 2023), ex- ploit the normal vector of the decision boundary improve attack efficiency and effectiveness. They introduce Gaus- sian noises to perturb a boundary point (2' in Figure 1) and query the model to identify which perturbations fall within the adversarial region, enabling accurate estimation of the normal vector (N' in Figure 1) (see Appendix for details). In recent studies (Chen al., 2020), researchers show that the locally optimal adversarial example Hosat typically lies on the 2D hypersurface spanned by d' and No, where the normal vector N points directly toward Ftoca,, as illustrated in Figure 1. Leveraging this geometric property, new bound- ary points closer to Rleaal can be discovered as weighted combination of A and the current boundary point z (Chen al., 2020; Reza et al., 2023).
ial regions with high decision boundary curvatures. While improving query efficiency, they overlooked local optima caused by the varying geometries of decision boundaries and target models, compromising their performance across diverse DNNs (see experiment results in Section 5). Our research reveals that narrow adversarial regions, whether in targeted or non-targe non-targeted attacks, can trap perturbation optimization local optima. To address this, we propose simple yet effective method detect narrow adversarial regions. An effective mechanism is further developed es- cape the associated local optima and enhance performance.
Proposed method. We propose novel Two-third Bridge Attack (TtBA) method. this method, a new bridge met- ric, Airidgee is introduced to guide perturbation optimization based on the decision boundary curvature.
For efficiency and simplicity, TuBA generates new perturba- tion directions at the i-th iteration (i > 1) by combining the current unit perturbation direction d' with its unit normal vector Ñ through & + (1 - k)dd, where & E (0, 1] is a weight parameter. geometric illustration of TtBA is shown Figure 1-(a). TtBA, the decision based attack becomes simply the problem of optimizing the weight pa- rameter k. We aim find suitable k to properly control the influence of the normal vector No on the updated direction
The curvatures of decision boundaries have strong impact on perturbation optimization (Ma et al., 2021; Reza et al., 2023). In particular, targeted attacks often create narrower adversarial regions with higher decision boundary curva- tures than non-targeted attacks, making perturbation opti- mization more challenging than non-targeted attacks (Reza al., 2023) (see Appendix A for more details). G-TA (Ma al., 2021) and CGBA-H (Reza et al., 2023) have been recently developed for targeted attacks narrow adversar-
2

---

TIBA: Two-third Bridge Approach for Decision-Basse Adversarial Attack
de. If k is too large, dy moves away from the best ad- versarial example (Proaal in Figure 1), making optimization ineffective. To identify the upper bound of k, we introduce threshold k = Aoridge such that the decision boundary along dy equals that of the current direction d'. is then opti- mized within the range (0, M Geometrically, the range of perturbation directions generated by TiBA resembles an arch bridge over the local best adversarial example Mocal, spanning from i' to 7 bridge shown in Figure 1.
Dedia bouubkayy
DesisionDonebeer
Hustg
Harsty:
k
0.5
0.3
0.
(a) Low curvoture
(b) Balanosd curvabure
(c) High curvature
Figure 2. Example decision boundaries with different curvatures.
Our introduction of the new metric kendge reveals the follow- ing interesting properties. First, the decision boundary's 's cur- vature can be directly estimated through kindgee illustrated in Figure 2 and analyzed theoretically in Appendix B.3. For narrow adversarial regions with high decision boundary curvatures as shown in Figure 2-(c), Mindgge is small. In con- trast, for wide adversarial regions in Figures 2-(a) and 2-(b), Koridge is large. Second, we discover that the perturbation direction generated by k = 2/3kénddee is very close to the optimal weight in the i-th iteration, as shown in Figure 1- (b) and detailed in Section 4. This finding eliminates the need for searching the optimal weight extensively, thereby significantly improving query efficiency. Third, a narrow adversarial region can potentially trap the optimization pro- cess in local optima. Therefore, when Miragge is very small (e.g., less than 0.1), we increase &s (e.g.. from 2/ 2/3dir to (nggen allowing d'+1 to deviate significantly from Mocal and hence escape local optima.
et al., 2021; Wang et al., 2022), and normal-vector based attacks (Chen al., 2020; Liu et al., 2019a; Li et al., 2020; Rahmati et al., 2020; Ma et al., 2021; Reza et al., 2023).
Random search attacks. Random search attacks create candidate perturbations by sampling randomly, followed by optimization through binary search along the decision boundary during each iteration. For example, Boundary At- tack(Brendel et al., 2018), 8), Biased Boundary Attack (Brun- ner et al., 2019) and AHA (Li et al., 2021) perform random walks along the decision boundary to refine perturbation directions. SurFree (Maho et al., 2021) explores multiple directions without using normal vectors. Triangle Attack (Wang et al., 2022) utilizes a triangle-shaped perturbation structure and low-frequency spaces for efficient optimiza- tion. OPT (Cheng et al., 2019) and Sign-OPT (Cheng et al., 2020) reformulate hard-label attacks as continuous optimiza- tion problems solved through zeroth-order methods. RayS in (Chen & Gu, 2020) employs a progressive direction sub- division strategy, iteratively refining blocks of perturbation directions to enhance search efficiency.
In summary, our main contributions are as follows: (1) We introduce novel metric hendge to detect varied curvatures of decision boundaries, providing valuable insights into the geometrical characteristies of adversarial attacks. (2) We un- cover a previously unidentified linear relationship between Abridge and the near-optimal perturbation direction. This in- sight paves the way for developing an efficient approach (TIBA) for bacision-based attacks. (3) We identify and ad- dress the critical challenge of local optima in perturbation optimization, particularly in narrow adversarial regions with high decision boundary curvatures, proposing an efficient detection and escape mechanism that significantly improves attack performance. (4) Extensive experiments on 9 widely used deep models, spanning MNIST, FASHION-MNIST, CIFAR10, CIFAR100, and ImageNet, show that TtBA con- sistently outperforms four ofte--ofthhearr decision-based attacks in both targeted and non-targeted settings.
Normal vector-based attacks. Normal vector-based at- tacks utilize normal vectors at the boundary points to guide perturbation optimization. For instance, HSJA (Chen et al., 2020) estimates normal vectors at boundary points for effi- cient adversarial example generation. TA (Ma et al., 2021) extends this idea by leveraging virtual hemisphere tangents to minimize perturbations. Efficient gradient estimation is achieved in qFool (Liu et al., 2019h) and GeoDA (Rah- mati al., 2020) by exploiting the observation that decision boundaries typically have low curvatures near adversarial examples. QEBA (Li et al., 2020) reduces query complex- ity through subspace optimization across spatial, frequency, and intrinsic dimensions. CGBA (Reza et al., 2023) intro- duces a novel semicircular search strategy on a 2D plane to efficiently handle geometric complexities. BounceAt- tack (Wan et al., 2024) improves upon HSJA by leveraging orthogonal gradient components and introducing smooth search mechanisms.
2. Related Work
Decision-based attacks represent one of the most challeng- ing settings for generating adversarial examples. Existing decision-basee based attacks can be divided into random search attacks (Brendel et al., 2018 8; Brunner et al., 2019; Cheng et al., 2019; 2020; Chen & Gu, 2020; Li et al., 2021; Maho
Although existing methods employ various geometric ap- proaches for perturbation optimization, they fall short in thoroughly analyzing how boundary curvatures vary across
3

---

TIBA: Two-third Bridge Approach for Decision-Basse Adversarial Attack
different models and datasets. This paper addresses these limitations by introducing novel techniques identify nar- row adversarial regions with high-curvature decision bound- aries and effectively escape associated local optima, signifi- cantly enhancing attack effectiveness and efficiency.
21.0
Kool
Dassioon g(d )
2
Ieration 10
20.0
195
18.12
013
K19
Ieration 11
19:0
1 Ma
0.11
levation
3. Problem Definition
0.15
180
1261
0.10
Iteraton 13 Iteration
Let (PI.I,.--- PC.wH) where Po,wh [0, 1), repre-
17
0.08
0.13
sent source image with shape C' x W x H, where C, W. and H correspond to the image's channels, width, and height, respectively. Let v(x) denote the true label of z, and f - f1...., ...,,K) } represent a K-class image classifica- tion model. Given a source image xi which is correctly clas- sified by the model (i.e., [())= = y(z))). decision-bar -based black-box attacker can only query the top-1 classification la- bel f(z) and have access the internal structures and pa- rameters of the classifier f. The goal is to find an adversarial example â =
17.0
a.17
Iteratinn 15
16.5
160
LASU
0
0.26
Iteration 16
15.5
15.0
0.15
14.5
k
0.05
011
0.15
02
0255
0.3
Figure 3. The g(dx) curve decision boundary g(de)
Pe.w. [0, 1], such that (()) + u(z) for non-targeted attacks, or [()) I (Ftarge) for targeted attacks where Taaget is a given target image and f (Zaugg * y(z), while minimizing the perturbation strength || x=le.- The stands for the norm used to mea- sure the perturbation strength, such as la or lx (Zhou et al., 2025). We adopt the lg norm, following many existing stud- ies (Chen et al., 2020; Reza et al., 2023). The problem for optimizing the adversarial example ã can be formulated as:
g(k Ñ + (1 - k) d multiple iterations of TiBA.
its decision boundary is defined as g(d) = min(r > 0 T(x + r- d) =1}. with the corresponding boundary point 3 = +g(g(()))))))))))))))())) -d. Correspondingly, the optimization problem in Equation (1) can be re-defined (Reza et al., 2023) as:
arg min g(d) s.t. I(x + g(d) d) = d
(4)
arg min | 2||2 s.t. 7(x) = 1,
(1)
where I(-) is an indicator function that determines whether the adversarial example z is in the adversarial regions. For non-targeted attack:
The decision boundary g(d) for direction d can be estimated using binary search (Reza et al., 2023), as outlined in Algo- rithm in Appendix D.
= L -1, otherwise.
if f()) vl)),
((3)
Probabiility Denety
Probubiiity Dersity
12%
20%
10%
15%
For targeted attack with a targeted image Fraget
30%
8%4
1, - -1, otherwise.
if f()) (Iurge));
((ū) =
(3)
a1
61
Reeal/
Beridg
Beral Harsty
(a) CIFAR100VVIT Non-targeted (b) ImageNet-VGG Non-targeted
To ease understanding, prior works (Brendel et al., 2018 Cheng et al., 2019; Reza et al., 2023) approximate the op- timization space of Equation (1) through a 2D-plane, as shown in Figure 1. They also exploit the perturbation direc-
Probsabiitt Daveity
Prebobilityy Dereity
20%
%6.
a%
6%
tion (denoted by d) and its corresponding decision boundary (denoted by g(d)) generate adversarial examples.
Let d = (UI.LI...,, (C....).. Vewwh [-1, 1]. represents perturbation direction. An adversarial example à can
0%
01 02
04
OS
06
65 02
01 82
02 04 05 os 03
Boral Keetgg
Rocal Henige
(c) CIFAR10O-VIT Targeted
(d) ImageNet-VGG Targeted
be defined as ã = clip(r + (ī +)) = clip(x + d) = clip(z + ||d]|2 d), where clip(-) constrains each pixel to the range [0, 1), and d = - is the unit vector obtained by normalizing using the & norm. For any direction d,
Figure 4. Distribution of the local best weight parameter kisea for generating the local best adversarial example Ziocat.

---

TIBA: Two-third Bridge Approach for Decision-Basse Adversarial Attack
Algorithm 1 Two-third Bridge Attack
iteratively increment k with a step size of 0.01, and esti- mate g(dk) using Algorithm 2 in Appendix D. The resulting g(dx) curve when attacking an VGG model using TIBA is plotted in Figure 3. In this figure, k = hleaa corresponds to the local minimum of g(dx), while k: = Kiddge gives the upper bound of the weight parameter k. Alucal is hence de- fined as the weight that determines the local minimum of the decision boundary on the 2D plane spanned by d' and Ñ' at the current iteration of TtBA. Note that when k > 1 midge g(dz) is greater than the decision boundary of the current direction, i.e., g(d+) g(d"),
1: Input: Original image z, indicator I()), budget Q;
2: Output: Adversarial example 5:;
3: Initialization: Iteration number f- 1, d' + Algo- rithm 4(xr, I, Q), 5² < x + g(d"). d', kwridge search tol- erance 8 + 0.001, local optimum threshold k + 0.1,
k < 0.2, bridge coefficient +- 0.9, b < 2/3:
4: repeat
5: No +- Algorithm Max 1,",,,33330
6: kiett, Kright t 0,1
). resulting in large perturbation demonstrated in Figure 1. So we first perform binary search to determine the threshold kindgg and the direction Sridgge such that ((hridgg)) - g(d"), ) and then optimize the weight parameter & within the range (0, Koridge] to find Kiwaat
7: repeat
kmid s hen hiige
8:
2
dmidd t kmid -o + (1 kmid) .d
9:
10:
Tmidd f + g(d")) ) dmid
11:
if I (2mia) = 1 then
12:
kjjt f kmid
To understand the statistical relationship between Rsocal and bridde we analyze the g(4))) A curves across 100 images based on both a ViT (Dosovitskiy, 2020) and a VGG (Si- monyan & Zisserman, 2015) model, with the distribution of ALoaa shown in Figure 4. This figure reveals strong linear relationship between Aeecal and the threshold Missgge (see theoretical analysis in Appendix B.5). It enables us to directly identify near-optimal kneaa using karidee For example, as shown in Figure 3, in the 10-th iteration of TtBA, when k2 bridge = 0.22, the local optimum occurs at Aoaaa 0.13, yielding ratio of Aasa 0.591 2/3. By Snige
13:
else
14:
Kiright f kimid
15:
end if
16:
until kright kieft 5
17:
Krritge & kien
18:
if Khridgee 2 h then
19:
11 <- b. bridge
20:
else if brridge S l then
21:
h1 t b. kriigge
22:
else
23:
kit1 t (.kkbbb))) (Moridge - +b)+b..
analyzing the distribution of Atuual across 100 images from different datasets, as shown in Figure 4, we find that Ance Montge is concentrated in the range (0.5..77) Based on this ob- servation, TiBA uses k++1 = b -.--- brriigge to determine kraca for each iteration, thereby eliminating the need to further search for Auuat- In this paper, we use K' = 2/3/ to efficiently generate the next perturbation (see Appendix G for more details). Driven by this idea, we propose TiBA with its pseudocode shown in Algorithm 1.
24:
end if
25:
d'+11 + kitl Ari + (1 - -ktt) di
gi+1 c- + g(d+t)) di+1
26:
27:
i+i+1
28:
until Number of queries Q Return z²
29:
4. Proposed Approach
In line 3 of Algorithm 1, we first follow the perturbation generation method in HSJA (Chen et al., 2020) and CGBA (Reza et al., 2023) to generate the initial perturbation direc- tion (see Algorithm 4 in Appendix F). In line 5, in each iter- ation of Algorithm 1, we follow the method in HSJA (Chen et al., 2020) and CGBA (Reza al., 2023) to generate a normal vector No at the current boundary point 5 (see Al- gorithm 3 in Appendix E). Lines 6-17 perform binary search to find Kindge in [0, 1] at an accuracy level of 5. Bi- nary search for kbesdge incurs minimal queries for high attack efficiency, as detailed in Appendix C. Empirically, we found that TIBA runs for 57 iterations on average under a 10,000- query budget. Each iteration uses approximately 10 queries for the binary search achieve krridge with accuracy level of 5 = 0.001. The total cost of 570 queries (57 x 10) consti- tutes only 5.7% of the query budget, significantly improving attack performance.
TIBA determines the perturbation direction dy at the i-th iteration as weighted combination of the unit current di- rection d' and its unit normal vector Nri;
de = k- No + (1 di, A EE (0,
(5)
where the weight parameter i interpolates between the direc- tions ' and d'. By identifying a critical bridge threshold hivridge (defined below), we can effectively exploit the decision boundary curvature to optimize the perturbation direction efficiently.
Numerous recent studies (Brendel et al., 2018; Cheng et al., 2019; Chen & Gu, 2020; Li et al., 2021; Chen et al., 2020; Reza et al., 2023) have shown that the decision boundary is smooth and locally concave. To further understand the geometric properties of the decision boundary g(dz), we
5

---

TIBA: Two-third Bridge Approach for Decision-Basse Adversarial Attack
Kbridge 2 k 0.2 indicates that the decision boundary has low curvature and the algorithm is not trapped in any local optimum. In this case, the weight parameter 2/ erdge In lines 20-21, Kiridge I k = 0.1, indicating that the decision boundary has high curvature and the algorithm is trapped in a local optimum. To escape this local optimum, we increase the weight according to k++1= = 6- Andge origge foreing d'+t1 to deviate from the perturbation direction of Hocal- The effectiveness of this method for escaping local optima is analyzed in Appendix G. As illustrated in Figures 2 and 3, narrow adversarial regions with high decision boundary curvatures tend to have shallow depths (see Appendix B.4 for more details), limiting the optimization the perturbation magnitude. Increasing 1 may cause d1+1 deviate from the local best Toocal without significantly increasing the E2-norm compared to Tocal-
In lines 18-19, k
performance in non-targeted and targeted settings separately, with the smallest &2 perturbation. Therefore, select these methods for comparison.
k++1 = =b-
Hy Hyprpaaraeeter settings. We adopt the recommended hyperparameter settings in (Reza et al., 2023) for searching decision boundaries and normal vectors. Specifically, for all four comparative algorithms and TtBA, the decision boundary search tolerance T = 0.0001. The dimension reduction factor is set to 4 for the ImageNet dataset, and for all other datasets. In TiBA, search tolerance 0 = 0.001 for determining Karidge. According to the parameter sensitive analysis in Appendix G, the thresholds i 0.1 and k 0.2, and the bridge coefficients b = 0.9 and 6 = 2/3.
Benchmark datasets and models. To assess the effective- ness and scalability of TIBA, we chose five datasets and 9 typical models listed below:
In lines 23, if kandge falls within the range [k- 0.1, k 0.2). the decision boundary is considered to have moderate curvature, potentially causing the optimization process to stuck in a local optimum. To address this, + 1 is chosen as a weighted interpolation between b- Mrddge and b- Mindgge properly balancing stability and exploration. Specifically, by assigning greater weight the normal vector, TiBA promotes broader exploration of the perturbation direction, reducing the risk of premature convergence to local optima. In line 25, the new direction d'+1 is computed as a weighted combination of the unit current direction d' and the unit normal vector N using the updated weight k*+1, In line 26, a binary search is performed along d'+1 (see Algorithm 2 in Appendix D) to identify the boundary point g++1 as the adversarial example of the current iteration.
MNIST-CNN: The MNIST dataset (LeCun et al., 1998), and benchmark 7-layer MNIST-CNN (Cheng al., 2020; Chen & Gu, 2020) that achieved 99.4% accuracy after training;
2. WASHION-MNIST-CNMT The FASHION MNIST dataset (Xiao et al., 2017), and a benchmark 7-1ayer FASHION-MNIST-CNN (Cheng et al., 2020; Chen & Gu, 2020) that achieved 91.0% accuracy after training.
CIFARIO-CNN. The CIFARIO dataset (Krizhevsky al., 2009), and benehmark 7-1ayer CIFARIO-CNN (Cheng et al., 2020; Chen & Gu, 2020) that achieved 82.5% accuracy after training;
5. Experiments
4. 1IFAR1O-VVT: The CIFAR100 dataset (Krizhevsky et al., 2009), and a well-known ViT model (Dosovit- skiy, 2020) that achieved 89.9% accuracy after train- ing:
In this section, we evaluate TiBA's effectiveness through a set of experiments, comparing its performance against state- of-the-art decision-base black-box attacks for both targeted and non-targeted scenarios.
5. The ImageNet dataset (Deng et al., 2009), and five prominent machine learning models: ImageNet- VGG19 (Simonyan & Zisserman, 2015), ImageNet- ResNet50 (He et al., 2016), ViT (Dosovit- skiy, 2020), LimageNetEffficenttee (Tan & Le. 2019), and ImageNee-Inneptton (Szegedy et al., 2016).
5.1. Experiment Settings
Experiment hardware configuration. Experiments are conducted using an Intel Xeon Gold 6330 CPU and NVIDIA GeForce RTX 4090 GPU, running PyTorch 2.3.0, Torchvi- sion 0.18.0, and Python 3.11.5.
5.2. Main Results
Competing approaches. We compare the performance of TIBA with four state-of-the-art decision-based attacks, including HSJA (Chen et al., 2020), TA (Ma et al., 2021), CGBA, and its variant CGBA-H (Reza et al., 2023), for both non-targeted and targeted scenarios. These methods are commonly used as baselines for decision-based attacks (Ma et al., 2021; Reza et al., 2023). Among them, CGBA and its variant CGBA-H have demonstrated the best attack
Performance metrics. Following state-of-the-an black-box attacks (Brendel et al., 2018; Li et al., 2021; Reza al., 2023), we adopt the l norn to measure the perturbation strength. For each model, we randomly select 1000 images from the test dataset. Table I presents the average and median & norms achieved by all competing approaches under query budgets of 2,000, 5,000, and 10,000, for both non-targeted and targeted attacks.
6

---

TIBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
Attacks
Non-targeted attacks
Targeted attacks
Datasets
2,000 QUE
5,000 QUE
10,000 QUE
2,000 QUE
5,000 QUE
10,000 QUE
MNIST
HSJA
2.921(1.785) 1.609(1.443)
1.366(1.307)
2.956(2.712)
2.275(2.079)
1.980(1.869
CNN
TA
2.983(1.799) 1.588(1.417)
1.345(1.281)
2.819(2.634)
2.169(2.001)
1.901(1.831)
CGBA
2.689(1.825) 1.978(1.538)
1.436(1.410)
3.247(2.904)
2.465(2.223)
2.095(2.021)
CGBA-H
2.741(1.864) 1.631
1.373(1.317)
2.977(2.846)
2.343(2.102)
2.059(1.862)
TIBA
2.667(1.754) (.505().362)
1.288(1.213)
2.841(2.659)
2.156(2.017)
1888((1786)
FASHION
HSJA
1.127(0.954) 0.778(0.748)
0.683(0.665)
1.741(L.689)
1.256(1.294)
1.097(1.13))
-MNIST
TA
1.191(0.998) 0.779(0.730)
0.665(0.646)
1.729(1.691)
1.017(1.100 1.239(1.222)
CNN
CGBA
1.059(0.008) 0.8)
0.781(0.640)
1.729(1.704)
1.263(1.291)
1.110(1156)
CGBA-H
1.02((0.984) 0.783(0.756)
0.690(0.665))
1.68((L.63))
1.261 (1.29)
1.101(1.115)
TiBA
0.896(0.873)
0.674(0.672)
0.603(0.601)
1.642(1.605)
1.19((1.208)
L.00((1084)
CIFARIO
HSJA
0.541(0.450)
0.300(0.251)
0.226(0.196)
1.634(1.88))
0.622(00 4688)
0,410(03332)
CNN
TA
0.552(0.449) 0.289(0.245)
0.208(0.190)
1.514(0.823)
0.554(0.401)
0.348(0.30))
CGBA
0.350(0.279) 0.233(0.189
0.181(0.152)
1.121(0.794)
0.440(0.393)
0.317(0.298)
CGBA-H
0.383(0.309) 0.235(0.19)) 190)
0.188(0.153)
0.872(0.602)
0.452(0.353)
0.338(0.284)
TtBA
0.371(0.294) 0.227(0.188)
0.180(0.55))
0.817(0.595)
0.415(0.343)
0.308(0.263)
CIFAR
HSJA
6.322(4.691) 2.627(2.015)
1.750(1.257)
42.66(40.43)
19.78(17.18)
10.88(8.074)
-100
TA
5.825(4.376) 2.327(1.925)
1.350(1.18))
40.38(38.42)
18.04(16.53)
9.761(7.217)
VIT
CGBA
2.086(1.430) 1.097(0.47))
0.744(0.613)
45.15(44.12)
11.96(7.399)
4,480(2.397)
CGBA-H
2.165(1.500) 1.130(0.862)
0.792(0.678)
20.66(18.41)
8.228(4.571)
4.327(2.17)
TtBA
2.114(1.521) 1.079(.8455)
0.734(0.603)
20.15(15.18)
8.154(4.330)
4.464(2.160)
ImageNet ResNe150
HSJA
27.33(16.95)
13.39(7.018)
7.840(4.023)
72.01(61.64)
55.80(48.15)
46.25(41.91)
TA
23.38(14.99)
12.04(6.302)
7.251(3.539)
68.95(59.52)
52.91(46.12)
44.34(39.93)
CGBA
18.58(12.79)
10. 10.10(5.099)
5.838(2.499)
76.38(70.77)
69.25(64.89)
58.33(52.44)
CGBA-H
17.79(9.628)
10.63(4.530)
6.203(2.542)
59.25(55.30)
45.99(42.75)
34.35(30.35)
TIBA
12.33(7.462)
6.32(2.804)
3.448(1.700)
57.21(53.19)
42.38(37.83)
27.83(24.54)
ImageNet
HSJA
8.117(5.409) 4.397(2.513)
3.256(1.997)
71.28(67.48)
50.92(36.57)
32.77(19.81)
VGG19
TA
6.592(4.433) 3.737(2.028)
2.651(1.539)
63.59(61.12)
40.18(32.17)
26.91(17.22)
CGBA
38810(2.184) 1.912(1119)
1.174(0.750)
80.00(77.99)
62.89(60.84)
40.72(33.1I)
CGBA-H
3.783(2.162) 1.841(1.179)
1.253(0.740)
54.09(46.12)
29.05(21.44)
14.32(10.59)
TtBA
3.650(2.150) 1.834(1.105)
1.166(0.737)
46.89(40.99)
25.85(20.14)
12.26(8.420)
ImageNet
HSJA
12.24(9.222)
6.513(4.233)
4.071(2.761)
33.73(29.98)
15.91(15.01)
7,899(7.844 8488)
ViT
TA
8.926(6.115) 1.792(3.101)
2.872(2.002)
28.13(24.34)
13.38(10.12)
5.647(4.649)
CGBA
4.515(3.086) 2.338(1.571)
1.588(1.058)
35.72(30.62)
13.96(10.19)
5.829(4.757)
CGBA-H
4.554(3.078) 2.311(1.651)
1.582(1.131)
23.23(20.75)
9.614(7.794)
4.862(3.944)
TtBA
4.508(3.052) 2.294(1.558)
1.512(1.044)
22.20(19.64)
9.205(7.611)
4.841(3.817)
ImtgeNet
HSJA
16.25(11.18) 9.288(4.980)
5.816(3.021)
77.46(74.88)
66.38(63.01)
51.29(47.72)
Efficient
TA
13.11(8.728) 6.986(4.034)
4.112(2.429)
73.00(68.15)
62.77(58.26)
49.28(44.36)
CGBA
9.956(5.719) 5.696(2.522)
3.161(1.456)
79.44(75.73)
68.52(61.24)
52.82(44.16)
CGBA-H
9.542(6.373)
4.836(2.958)
2.688(1.979)
61.98(56.37)
42.34(38.71)
28.83(25.39)
TtBA
6.451(4.400) 3.359(.136)
2.008(1.224)
54.85(50.73)
36.15(30.59)
21.68(15.81)
ImageNet
HSJA
14.50(9.801) 7.823(4.565)
4.935(2.820)
75.51(72.86)
64.54(61.28)
50.37(46.89)
Inception
TA
13.23(8.012) 6.907(3.854)
3.839(2.233)
71.26(67.54)
60.83(57.36)
48.21(43.52)
CGBA
11.54(4.402) 5.950(1.935)
3.185(1.072)
80.47(77.25)
53.69(48.67) 67.99(65.07)
CGBA-H
10.88(4.882)
5.095(1.960)
2.474(1.092)
56.46(51.08
42.22(36.61)
27 27.96(22.60)
TtBA
8.599(4.297)
3.771(1.765)
1.961(0.953)
55.16(53.13)
38.24(34.55)
24.19(18.18)
Table I. Average (median) & norm of perturbation for targeted and non-targeted black-box attacks under different query budgets (QUE).

---

TIBA: Two-third Bridge Approach for Decision-Bann Based Adversarial Attack
fectiveness state-of-the-art adversarially trained models developed in (Wang et al., 2023). These models serve as highly relevant benchmark due to their focus adversar- ial robustness, making them ideal for assessing the perfor- mance of TtBA. In our experiments, we test specifically the WideResNet models (Wang et al., 2023), which were trained using techniques in (Zagoruyko, 2016) to achieve strong robustness. We compare TiBA against other leading attack methods, including HSJA, TA, CGBA, and CGBA-H, the CIFAR-100 and -iag-eeteeNet datasets. For each dataset, we randomly select 500 images to conduct targeted and non- targeted attack experiments, adhering to a query budget limit of 10,000 queries. Specifically, we adopt the WideResNet WRN-70- 16 model from (Wang et al., 2023) for CIFAR-100 100 and the WRN-28-10 model for -imy-ImageNet. Past studies show that these models have strong defensive performance the respective datasets (Wang et al., 2023).
FEJJ
Markané, perturruuaaa
TA
OGBA
CGBA
OGBA-I
OGIA-HI
Markiné
0000
030
000
(00
030
0
0.00
1332
100
100
090
030
Queries
Queries
(a) Non-targeted attack
(b) Targeted attack on
C10A datasot
CIFAR100 dataset.
11
Median Merkam,ppetuui perturttiio
80
HSJA
HSBA
OGBAA
21
CGRA
CGBA-H
CGBA-H
TIBA
Mediaan
0001
OFE
OTE
000
000
000
O00E
000
OKE
000
0000
To assess the general applicability of TiBA, we follow iden- tical hyper-parameter settings introduced in Section 5.1.
Queries
Queries
(c) Non-targeted attack on
(d) Targeted attack on
Tiny- Imageeet dataset
Tiny-mmgeNee dataset
The median lg curve with respect to different numbers of queries is presented in Figure 5. The results in Figure 5-(a) and (b) demonstrate that, on the CIFAR 100 dataset, TIBA outperforms all competing methods for both targeted and targttd attacks. For the tiny-ImageNee dataset, Fig- ure 5-(c) shows that TtBA achieves the best performance in non-targeted attacks. However, for targeted attacks, as depicted in Figure 5-(d), CGBA-H performs the best within the query budget range of 1,000 to 4,000. Beyond 4,000 queries, TtBA surpasses CGBA-H.
Figure 5. Median & perturbation against adversarialll-trained WideResNet models.
Results. For non-targeted attacks in Table 1, our proposed TIBA achieves the best performance on out of 9 models, ranging from 2000 to 10,000 queries. On the ImageNet dataset, TtBA reduces the &2 perturbation by over 20% com- pared to other methods for the ResNet50 and Efficient mod- els. On the CIFAR 10-CNN and CIFAR100-ViT models, CGBA outperforms TIBA in terms of both average and me- dian & norm at 2,000 queries. However, TtBA surpasses CGBA at 5,000 and 10,000 queries for both models. In targeted attacks, TIBA surpasses other methods in nearly all tested scenarios, covering models and various query budgets. The only exception occurs with the CIFAR 100- ViT model at 10,000 queries, where CGBA-H achieves marginally lower average l2 norm (4.327 versus 4.464). This result shows that TtBA outperforms other methods, especially for targeted attack settings.
6. Conclusion and Future Work
In this paper, we proposed Two-third Bridge Artack (TtBA), a novel and efficient decision-based black-box adversar- ial attack method. Our method introduces the concept of bridge direction, which effectively combines the current perturbation direction with its normal vector, guided by the weight parameter herdge- We identified and successfully addressed the challenge of local optima in regions with high decision boundary curvatures, significantly enhancing the attack's 's effectiveness. Further, through theoretical analysis and extensive experimentation, we demonstrated that using 2/ /33hhrige consistently yields near-optimal results in mini- mizing the Eg distance of adversarial examples. Extensive evaluation across multiple datasets (MNIST, FASHION- MNIST, CIFAR1O, CIFAR100, and ImageNet) and 9 deep learning models demonstrated that TtBA can consistently outperform state-of-the-art methods in both targeted and non-targeted attack scenarios. Our work not only advances the field of adversarial machine learning but also provides valuable insights into the geometric properties of decision boundaries through the novel khridge metric.
The perturbed images generated by TIBA for different query budgets (QUE) are shown in Figure 6. In this figure, per- turbation directions
normalized to the [0, range to illustrate how they diminish as the query budget increases, starting from random noise in non-targeted attacks and a target image in targeted one.
5.3. Results on Adversarially Trained Models
Defense methods based on adversarial training play a cru- cial role in enhancing model robustness by significantly lowering the success rates of hard-label attacks (Chen & Gu, 2020; Chakraborty et al., 2021). We assess TtBA's ef-
Future research directions for TIBA are promising in sev-
8

---

TIBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
5UE=500
QUE=2000
QUE=5000 t2 nom=1.11
QUE=500 t2 norm=5.98
QUE=2000 22 nomm=2.2
QUE 5000
Input x
t2 nom=2.42
t2 nom=1.37
Input
f2 nom==141
Perturiation Non-targeee Enample
(a) Class 'I' misclassified arbitrary class '4'
(c) Class 'Ibizan' misclassified as arbitrary class 'Whippet'
QUE=500
QUE=2000
QUE=5000
QUE=1000
QUE=5000
QUE=20000
Inputxx
E2 nom=2.43
nom=1.71
C2 nom=1.43
Input
t2 norm 10.2
E2 norm 29.2
t2 norm 13.9
Targetd Enargals
Perturbakkn
2
Class misclassified target class
(d) Class 'hizzan' misclassified as target class 'Model-T'
Figure 6. Adversarial examples and corresponding perturbation directions generated by TtBA for differont query budgets.
eral avenues. First, adapting TiBA to score-based attack scenarios could leverage probability outputs to significantly reduce query complexity. Second, incorporating TtBA into multi-objective optimization frameworks could enhance real-world deployability by jointly optimizing perturbation imperceptibility, cross-model transferability, and query effi- ciency. The geometric insights developed from the decision boundary analysis in this paper could extend beyond tra- ditional attack scenarios, potentially benefiting adversarial machine learning tasks in areas such as speech recognition, text classification, and object detection.
Acknowledgments
This work was partially supported by BUPT Excellent Ph.D. Students Foundation, foundation number is CX20241003. The authors express their gratitude to the anonymous re- viewers for their insightful and constructive feedback on the initial version of this paper.
References
Bai, Y., Wang, Y., and Zeng, Query efficient black- box adversarial attack on deep neural networks. Pattern Recognition, 133:109037, 2023.
Impact Statement
Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šmdić, N., Laskov, P., Giacinto, G., and Roli, Evasion attacks against machine learning at test time. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Repub- lic, September 23-27, 2013, Proceedings, Part III 13, pp. 387-402, 2013.
This paper presents work that aims to advance the field of AI security, specifically in understanding and improving black- box adversarial attacks against image classification models. While our research could potentially be used to enhance the robustness of AI systems through better understanding of their vulnerabilities, we acknowledge that adversarial attack techniques might have dual-use implications. Our proposed method can potentially be extended beyond image classification to other domains including speech recognition, text classification, and object detection models. We believe this research contributes to the broader goal of developing more reliable and secure Al systems across various Al ap- plications, which is crucial as these technologies become increasingly integrated into society.
Brendel, W., Rauber, J.. and Bethge, M. Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models, 2018. arXiv:1712.04248 [cs, stat].
Brunner, T., Dichl, F., Le, M. T., and Knoll, A. Guessing smart: Biased sampling for efficient black-box adversarial attacks. Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4958 4966, 2019.

---

TIBA: Two-third Bridge Approach for Decision-Bans Adversarial Attack
Chakraborty, A., Alam, M., Dey, V., Chattopadhyay, A., and Mukhopadhyay, D. A survey on adversarial attacks and defences. CAAI Transactions on Intelligence Technology, ((1):25-45, 2021.
with adjustable sparsity and generalizability for deep im- age classifiers. Pattern Recognition, 122: 122:108279, 2022.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Chen, and Gu, Q. Rays: A ray searching method for hard-label adversarial attack. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1739-17477 2020.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Chen, J., Jordan, M. I., and Wainwright, M. Hop- skipjumpattack: A query-efficient decision-baid baaod attack. In 2020 IEEE Symposium Security and Privacy, pp. 1277-1294, 2020.
Krizhevsky, A., Hinton, at. Learning multiple layers of features from tiny images. Technical Report, University of Toronto, 2009.
Chen, P.- Zhang, H., Sharma, Y., Yi, J., and Hsieh, C.- Zoo: Zeroth order optimization based black-box at- tacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop artificial intelligence and security, pp. 15-26, 2017.
LeCun, Y., Bottou, I.., Bengio, Y., and Haffner, Gradient- based learning applied document recognition. Proceed- ings of the IEEE, 86(1 1):2278 23224, 1998.
Li, H., Xu, X., Zhang, X., Yang, S., and Li, B. Qeba: Query- efficient boundary-based blackbox attack. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1221-1230, 2020.
Cheng, M. Zhang, H., Hsieh, C. J., Le, I., Chen, Y., and Yi, J. Query-efficient hard-label black-box attack: An optimization-basee approach. In 7th International Conference on Learning Representations, 2019.
Li, J., Ji, R., Chen, P., Zhang, B., Hong, X., Zhang, R., Li, S., Li, J., Huang, F,, and Wu, Y. Aha! adaptive history- driven attack for decision-based black-box models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 16168-16177, 2021.
Cheng, M., Singh, S., Chen, P., Chen, P.-Y., Liu, S., and Hsieh, C.-.. Sign-OPT: A Query-Efficient Hard-label 10773 [cs, stat].
Adversarial Attack, 2020.
Deng, J., Dong, W., Socher, R., Li, L.-J,, ,, Li, K., and Fei-Fei, L. Imagenet: A scage-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248 255, 2009.
Liu, Y., Moosavi-Dezfoolli S.-M., and Frossard, P. A geometry-inspired decision-based attack. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4890 4898, 2019a.
Dong, Y., Su, H., Wu, B., Li, Z., Liu, W., Zhang, T., and Zhu, Efficient decision-baasee black-box adversarial attacks face recognition. In Proceedings of the JEEF/CVF Conference Computer Vision and Pattern Recognition, pp. 7714-7722, 2019.
Liu, Y., Moosavi-Dezfooli S.-M., and Frossard, P. A ecometry-inspiree decision basciioo-bbaedd attack. In Proceedings of the IEFE//CV International Conference on Computer Vision, pp. 4890-4898, 2019b.
Dosovitskiy, An image is worth 16x16 words: Trans- formers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
Long, T., Gao, Q., Xu, L., and Zhou, Z. A survey adversarial attacks in computer vision: Taxonomy, visual- ization and future directions. Computers & Security, 121: 102847, 2022.
Fan, X., Li, M., Zhou, J., Jing, Q., Lin, Lu, Y., and Bi, scheme toward black-box adversarial attacks. JEEE Transactions Consumer Electronics, 70(1):2038-2488 2024.
Gesa: new adversarial
Ma, C., Guo, X., Chen, L., Yong. J.-H., and Wang, Y. Find- ing optimal tangent points for redueing distortions of hard-label attacks. Advances in Neural Information Pro- cessing Systems, 34:19288-19300 2021.
Feng, Y., Wu, B., Fan, Y., Liu, L., Li, Z., and Xia, S.- T. Boosting black-box attack with partially transferred conditional adversarial distribution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pallern Recognition, pp. 15095-15104, 2022.
Madry, A., Makelov, A., Schmidt, I.., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. In International Conference Learn- ing Representations, 2018.
Ghosh, A., Mullick, S., Datta, S., Das, S., Das, A. K., and Mallipeddi, R. black-box adversarial attack strategy
Maho, T. Furon, T., and Le Merrer, E. Surfree: a fast surrogate-free black-box attack. In Proceedings of the
10

---

TIBA: Two-third Bridge Approach for Decision-Bans Based Adversarial Attack
IEEE/CVF Conference on Computer Vision and Pallern Recognition, pp. 10430-10439, 2021.
Wang, Z., Pang, T., Du, C., Lin, M., Liu, W., and Yan, S. Better diffusion models further improve adversarial train- ing. In International Conference Machine Learning, 2023.
Park, J., Miller, P., and McLaughlin, N. Hard-label based small query black-box adversarial attack. In Proceedings of the IEEE/CVF Winter Conference Applications of Computer Vision (WACV), pp. 3986-3995, 2024.
pp.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: aeai::000000444480 2017.
Rahmati, A., Moosavi-Dezfoolli S.-M., Frossard, P., and Dai, H. Geoda: a geometric framework for black-box adversarial attacks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 8446-8455, 2020.
Zagoruyko, Wide residual networks. arXiv preprint 1605 2016.
Zhou, C., Wang, Y-G.,, Wang, Z.-.,, and Kang, X. Lp-norm distortion adversarial attack. Signal Processing: Image Communication, 131:117241, 2025.
Reza, M. F., Rahmati, A., Wu, T., and Dai, H. CGBA: Curvature-aware geometric black-box attack. In Pro- ceedings of the IEEE/CVF International Conference on 2023.
Computer Vision, pp. 124-133, 2023.
Shi, Y., Han, Y., Tan, Y.aa,, and Kuang. X. Decision- based black-box attack against vision transformers via patch- wise adversarial removal. Advances in Neural Informa- tion Processing Systems, 15:12911-1293,, 2022.
Simonyan, K. and Zisserman, A. Very deep convolutional networks for large-scale image recognition. 3rd Interna- tional Conference on Learning Representations, 2015.
Sun, X., Cheng, G., Li, H., Lang, C., and Han, J. Stdatav2: Accessing efficient black-box stealing for adversarial at- tacks. IEEE Transactions on Pattern Analysis and Ma- chine Intelligence, pp. 1-17, 2024.
Szegedy, C., Vanhoucke, V., loffe, S., Shlens, J., and Wojna, Z. Rethinking the inception architecture for computer vi- sion. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818 2826, 2016.
Tan, M. and Le, Q. Efficientnet: Rethinking model seal- ing for convolutional neural networks. International conference on machine learning, pp. 6114, 2019.
Wan, J., Fu, J., Wang, L., and Yang. Z. Bounceattack: A query-efficient decision-based adversarial attack by bouncing into the wild. In 2024 IEEE Symposium Security and Privacy (SP), pp. 1270-1286. IEEE, 2024.
Wang, F., Shao, M. Meng, L., and Liu, F. Dual stage black-box adversarial attack against vision transformer. International Journal of Machine Learning and Cyber- netics, pp. 1-12, 2024.
Wang. X., Zhang, Z., Tong, K., Gong, D., He, K., Li, Z., and Liu, W. Triangle attack: A query-efficient decesion-based adversarial attack. European conference on computer vision, pp. 156-18 174, 2022.

---

TIBA: Two-third Bridge Approach for Decision-Basse Adversarial Attack
A. Appendix Introduction
In real-world applications, lower perturbation strength makes adversarial examples less noticeable to human observers. Therefore, decision-basee attacks aim to deceive the target DNN (i.e., image classifier) with the minimal perturbation strength, subject pre-determined query budget (Brendel et al., 2018). To enhance attack efficiency, fecision-based attacks have focused on exploring perturbation directions and the corresponding decision boundary optimize adversarial examples (Brendel et al., 201 8; Chen & Gu, 2020; Reza et al., 2023). A perturbation direction is a pixel-wise vector guiding adversarial modifications. Its decision boundary defines the minimal perturbation magnitude required to mislead the model along the perturbation direction. Thus the direction with low decision boundary is highly desirable. As illustrated in Figure 1, x is the original image, and the boundary of the orange region represents the decision boundary of a DNN in image classification. Points Ø and 24 bridge in Figure serve as boundary points along the perturbation directions d' and Briigge respectively.
The curvatures of decision boundaries have strong impact on perturbation optimization (Ma et al., 2021; Reza et al., 2023). In particular, targeted attacks often create narrower adversarial regions with higher decision boundary curvatures than non-targeted attacks, making perturbation optimization more challenging than non-targeted attacks (Reza et al., 2023). As shown in Figure 2-(c), the adversarial region contracts in targeted attacks, making it difficult to find effective adversarial examples, seriously hurting attack effectiveness and query-efficiency (Reza et al., 2023). Thus, efficiently optimizing perturbations within narrow adversarial regions is a crucial practical challenge (Reza al., 2023). Overcoming this obstacle key to advancing the effectiveness of decision-based attacks.
B. Geometric Analysis of Decision Boundary
B.1. Define the HyperSurface of Decision Boundary
The decision boundary of the target DNN model f can be characterized as a hyperSurface S associated with an input æ. Specifically, S is the set of all points ē that lie exactly on the boundary between the class of x and other classes. For any direction e Rx there exists a unique boundary point ă along d, determined by the minimal perturbation required to cross the decision boundary. Formally, can be defined as:
S { 1 = x + g(d)
d
PA 0. I(t) = 1
(6)
[d]a
where T(-) is the indicator function that determines whether è lies in the adversarial region, g(d) is the decision boundary d along direction d, श is the unit direction vector. HSJA (Chen et al., 2020) proves that there exists only one boundary point on S along any direction d. Furthermore, since the hyperSurface S is smooth with respect to d, the decision boundary g(d) is also smooth with respect to d.
B.2. Local Taylor Expansion of Decision Boundary
Since studying the properties of S in the high-dimensional input space C x W x H is challenging, existing research such as (Chen et al., 2020; Ma et al., 2021; Reza et al., 2023) focused on studying the curve at the intersection between the decision boundary and the 2D plane defined by the current perturbation vector d' and the normal vector Ñ This 2D reduction is effective because ' indicates the direction of locally optimal perturbation, making the search for new directions more efficient. For simplicity, we treat the decision boundary G(k) = g(k: Nr + (1 - k) dd) as a function of and analyze the properties of G(k) on this 2D plane. We express G(k) as Taylor expansion around the initial point k: 0:
1 bk2 + 2
1 _okk + O(K*),
G(k) = gdd" + ak +
aG
0 is the first-order derivative, representing the initial slope of the boundary along N
Bk k=
0 is the second-order derivative, dominating local curvature,
UR k=
G
is the third-order derivative, describing the curvature variation rate,
a k=
12

---

TIBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
Okkt) denotes higher-order terms.
To find k4 "hridge*
we set
1 1 bb2 goh -(kk)==gle g(d)) By omitting the third-order term } ck and higher-order terms, the equation simplifies
G(k) = g(d") + ak
G(k) - g(d)) + ak + 2
bbg² = g(dd).
Moving g(d") to the right-hand side yields
1
ak + 2
bi2² O.
This equation has two solutions:
1
== 0 and + bk 0,
2
which gives
2a
1:
b
Since d-f bridge
> 0, we obtain
2a
k- bridge
(8)
B.3. Relationship between Curvature and kbridge
At 1: the curvature x of the decision boundary in the 2DD plane is derived from the Taylor expansion coefficients as:
(f))
(1+ (3))))))3/2 (1 + a2)3/2
This revision simplifies the wording slightly, maintains the mathematical meaning, and improves the flow of the sentence.
When higher-order terms are negligible (i.e., |a| << 1 and |ck-1
<<
[bk D, the curvature can be approximated as:
2a
K R
with
(10)
hridge
bridge
This approximation is valid for small attack steps within the neighborhood of k. It implies that as the curvature of the decision boundary G(k) increases, kridge decreases. Thus, kridge serves an indicator of the decision boundary's 's curvature.
B.4. Minimum Points and Values of Decision Boundary
CRITICAL POINTS AND MINIMUM DECISION BOUNDARY
The first-order derivative of G(k) is:
G' G'(k)= + bl 2 ck2 + O(K3).
(11)
Setting Gk(k) ( to find critical points, we solve:
+ bk + ck 0 (neglecting (kk))).
(12)
Quadratic Approximation Case (c 0): When higher-order terms are negligible (c zs 0), the critical point simplifies to:
Kmin b
(13)
The second derivative (k) = b ck + Okk2) must satisfy (kmmi)) > for local minimum. Under 2s 0, this reduces > consistent with positive curvature.
13

---

TIBA: Two-third Bridge Approach for Decision-Basse Adversarial Attack
IMPACT OF DECISION BOUNDARY CURVATURE
From the curvature formula
(1+a4)377 (Eq, (9)), two regimes emerge:
1. Small Slope (la) < 1): Here, K = 6, and Eq. (13) becomes:
mmin
(14)
Ki
For fixed a, increasing (i.e., sharper eurvature) drives minn O. The minimum value is:
a²
G(kmmin) R g(
(15)
2x
Larger reduces the subtraction term, resulting in larger Gkimin))
2. Non-Negligible Slope (lal ~ 1): The full curvature formula & (1+02)a77 implies = x<11 + a2)38/2 Substituting into
kmin:
Kmin
(16)
x(1 + a2)3/2
Even with moderate a, increasing still forces kmin - O, and (kmmn)) grows G (imma)) g(dd)
a²
2N(1+a233/a
GEOMETRIC INTERPRETATION
High Curvature (ı: 1): The decision boundary sharply curved near input x. To reach the boundary, adversarial perturbations require smaller steps (Kmin J) but larger magnitudes (Gi(mmn)) 1), as the boundary "retreats" rapidly from the original class.
Low Curvature (k .): The boundary is flat, allowing larger steps (kmin 1) with smaller perturbations (G 4)-
HIGHI-ORDER CORRECTIONS
Including the cubic term (c & 0), Eq. (12) becomes quadratic:
= ck2 + bk + a O.
(17)
2
The solution is:
-b + V62 -acc
kinn
(18)
For small a Taylor expansion in e/b² gives:
d²c
Amin
(c²)
(19)
b 21
The cubic term introduces an offset proportional c, but the dominant term -a/b still ensures kimin 1/1 when
B.5. Linear Relationship Between kmiin and kirridge
Building on the analysis of the decision boundary's curvature к and the minimum point kmin- we now investigate the relationship between kmin and the parameter biidgge We demonstrate that under the quadratic approximation, kinin and kef exhibit approximately linear relationship, governed by the curvature k.
beddge
DEFINITIONS RECAP
Minimum Point kiii: From Eq. (13), under quadratic approximation (c = 0):
Kmin b'
where a aG/Okkkkoo and 82G/Ok2 Ik=o RS K. when |a|
1.
Bridge weight parameter kividge from Eq. (8):
2a
orrige =
b
14

---

TIBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
LINEAR RELATIONSHIP DERIVATION
From Eq. (13) and Eq. (8), obtain:
Kminn = 2 Mbridgee
This reveals linear proportionality between Kmin and Miridgee
kimin OK Korigge
(20)
C. Complexity of Binary Search for kbridge
In lines 6-17 of Algorithm 1, we perform binary search to identify the bridge parameter kindg that aligns the intermediate direction dmid (Line 9) with the current direction ds decision boundary. While this process requires query budget, its computational cost is minimal compared to its strategic benefits. Under the standard 10,000-query setting (Chen & Gu, 2020), TtBA completes 57 iterations average, with query allocation distributed across four components:
1. Initial perturbation (Algorithm 4): about queries for baseline direction generation.
2. Normal vector estimation (Line 5): [30vi] queries per iteration for boundary geometry analysis, where i represent the i-th optimization iteration in Algorithml.
3. Bridge parameter binary search (Lines 6-17): approximately 10 queries/iteration precision 5 0.001 (x= 2-10)
4. Decision boundary binary search (Line 26): approximately 14 queries/iteration for = 0.0001 (= 2-14) tolerance.
The resulting queries for each iteration is:
= 24 + [30
(21)
Consequently, the total number queries across iterations of binary search bounded by:
J. (24 (24+ 30vz) dr 10 + 24x + 20x 24n + 20n 34.
Qn 10
Σ qi 10
(22)
10a yields n 57 iterations. The total cost of 570 queries (57 x 10) for lirrigee binary search constitutes only 5.7% of the query budget.
Solving 24n + 20n
D. Binary Search of Decision Boundary
In Algorithm 2, the binary search process begins by initializing the low boundary point Htow + x in the non-adversarial region and the high boundary point Hnggh + x + d in the adversarial region. In lines 4-11, 1, the algorithm iteratively checks whether the midpoint Fmid < (Tlow + Thigh lies the adversarial region and updates Tlow or Thigh accordingly until the search tolerance is met. Finally, in line 12, it returns the decision boundary value ||amigh 22/22-
E. Normal Vector Generation
We follow the CGBA (Reza et al., 2023) normal vector estimation method (Algorithm 3) for decision boundary characteriza- tion. Given a boundary point in line 1, we initialize a normal vector N + 0C* W xH in line 3. For each query E [1, QN]:
1) Generate low-dimensional Gaussian noise chemp ~/00,) 7) in reduced space C W. x (Line 5); 2) Upsample to image space via 2D inverse discrete cosine transform dGaussian + IDCT, (DCep() (Line 6), where IDCT, refers to the 2D Inverse Discrete Cosine Transform, which reconstructs spatial-domain data from its Trequency-domall representation; 3) Test adversarial direction by perturbing ă with TN dGassian (Line 7); 4) Accumulate direction using + dGaussin based on the indicator T(ă + daussii)) (Lines 8- 8-10). The final normalized normal vector Ñ is returned after QN queries (Line 12).
15

---

TIBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
Algorithm 2 Decision Boundary Binary Search
Input: Original image z, direction d, indicator I(-):
2: Output: Decision boundary g(d) for direction d;
3: Initialization: Set low boundary point Tow z, high boundary point Thigh f- + d, search tolerance < 0.0001;
4: repeat
5: Tmid < Zum + Frigh
2
6: if (fmmaa) = then
7: Thigh f- Tmid
8: else
9:
Flow mid
10: end if
11: until [hhighh Flo 2| S T
12: Return [ 27 as g(d).
Algorithm 3 Get Normal Vector
1: Input: Original image indicator function (()), a boundary point ă, query budget for normal vector Q dimension
reduce factor and normal vector radius rN = 0.0003;
2: Output: A normal vector N at current boundary point ;;
3: Initialization: N + (),..,,)CxX)) OXXWXII
4: for query q = QN do
5: dremp t (21,1,1, ..., Fc # )), Zewch (0,
6: dGaussian < IDCT, (chemp)
7: if I" TNN dGassssan then
8:
N N + dGaussia
9: else
10: N +- N- dGaussinn
11: end if
12:
end for
13:
Return N
F. Initial Perturbation Generation
We adopt the CGBA framework (Reza et al., 2023) to compute the initial perturbation direction (Algorithm 4). For targeted attacks (Lines 3-4), the direction is derived as dinit = Ttarget - x. In non-targeted scenarios (Lines 6-19), Gaussian noise dosussiaa (0, I) is iteratively sampled (Line 7). scaled by 0.02q (Line 8, where q is the query index and 8 denotes normalization), with early termination if T(x dimit)
(Lines 9-11). If Q/10 queries fail (Line 13), perturbations 1 CC x (Line 14) or OC*W*H x (Line 16) are attempted. The direction then calibrated via dmai + g(dma) dma (Line 20), where g(-) implements boundary projection through binary search (Reza al., 2023).
G. Parameter Sensitivity Analysis
Our TtBA algorithm summarized in Algorithm 1 introduces several parameters, including the local optima thresholds = 0.1 and = 0.2, as well as the bridge coefficients i = 0.9 and i = 2/3. The corresponding parameter settings are determined based on preliminary experiments conducted on the MageNettVGGii model. this appendix, we show that the performance of TiBA is not sensitive to these parameter settings.
To evaluate the impact of different parameter settings, conduct sensitivity analysis. Specifically, we vary the bridge coefficients i and (Table 2) and the local optima thresholds & and & (Table 3) across range of values. For each setting, performance is assessed using the area under the median f2-query curve (AUC). AUC is calculated using the formula: ii | (Q;) where (2().) represents the median fn-mrm obtained after Q; queries, and 10, 000 is the total query budget. adversarial attacks, a lower AUC demonstrates a smaller perturbation and better attack effect.
AUC = Σ"
We conduct experiments on the MNIST-CNN, CIFARIO-CNN, CIFAR100-VES and ImageNet- VGG models for both
16

---

TIBA: Two-third Bridge Approach for Decision-Bass Adversarial Attack
Algorithm 4 Get Initial Perturbation Direction
Input: Original image z, indicator I(-), query budget Q, target image Naarget for targeted attack;
2: Output: An initial perturbation direction dimits
3: if Targeted attack then
4: dinit &- Fturget I
5: else if Non-targeted attack then
6: for query 9 = to 10 do
7: dGaasssaa 6- (21,1,1, (C,,,, Femuch ~ (0,
8: dini + 0.02 9- dGausisn
9: (z + dma) = 1 then
break
end if end for
12:
13:
if 2 Q then
10
14:
dinit f (I,..., 1)
15:
if (x + dinit) = -1 then
16:
dmm + (O, OXCXWxH
end if
end if
19: end if
20: dinit g(chnit) duni
21: Return dimit
Dataset Model
Parameter
b 0.9
b 0.9
b= 0.9
b 0.9
0.9
1 0.9
i 2/3
Parameter
0.55
b 0.60
b 0.65
b 2/3
b 0.70
b= 0.75
b= 2/3
MNIST
Non-targeted
17121
17481
17151
17016
17440
17447
17091
CNN
Targeted
24750
24032
23863
24106
24960
24389
24166
CIFARIO
ton-targeted
2908.0
2808.7
2786.1
2771.8
2833.1
2887.9
2791.0
CNN
Targeted
9954.0
9271.4
8827.8
9027.1
8804.8
9157.8
9046.2
CIFAR100
Non-targeted
11359
10860
9926.5
9607.3
10102
11970
9621.3
VIT
Targeted
90993
94329
85023
83471
100429
90909
87365
ImageNet
Non-targeted
16913
16037
17005
16072
15366
16250
16182
VGG19
Targeted
201410
198460
196677
193161
193700
198519
198932
Table 2. AUC of TIBA under different parameters (6, b).
non-targeted and targeted attacks. These models have been introduced in Subsection 5.1. The results are presented Table 2 and Table 3, with the best values highlighted in bold.
Our experiment results clearly indicate that the parameter settings (6 0.9, = 2/3) and (K 0.2, k= 0.1) achieve the best performance in five out of eight experiments. Even when they are not the top-performing configurations, their results remain very close to the best values.
Furthermore, the parameter setting i = 2/3 and i = 2/3, as shown Table 3, corresponds to TtBA without the local optima escape mechanism. Under this setting, TtBA updates the weight parameter as k = 2/33 in lines 18-24 of Algorithm 1, completely ignoring the curvature of the decision boundary. Our experiments show that this configuration achieved consistently lower performance compared to setting b 0.9 and b 2/3 Algorithm 1. This result highlights the importance of using our proposed mechanism escape local optima.
We also conduct additional sensitivity analysis on robust models. As demonstrated in Table 4, TtBA can effectively attack robust models after adjusting its hyperparameters. Specifically, we modify the setting of k = b kbridge by varying the default value of J = 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 100 and Tiny ImageNet datasets. The results demonstrate that, for robust models, the setting 0.625 achieves the best performance out of experiments, clearly surpassing the i = 2/3 setting. This difference likely
17

---

TIBA: Two-third Bridge Approach for Decision-Based Adversarial Attack
Dataset
Parameter k
k 0.15
A == 0.20
k 0.15
k 0.20
À 0.25
k 0.20
À 0.25
Model
Parameter k
k 0.05
k 0.05
k == 0.10
k 0.10
k = 0.10
k k= 0.15
À 0.15
MNIST
Non-targeted
16972
17005
16954
17016
16946
17051
17008
CNN
Targeted
23745
24262
23972
24106
24389
24272
24601
CIFARIO
Non-targeted
2777.0
2786.5
2781.2
2771.8
2787.2
2779.7
2774.0
CNN
Targeted
9340.9
9307.6
9126.3
9027.1
9221.4
9471.9
9350.8
CIFAR 100
Non-targeted
9711.4
9703.6
9698.2
9607.3
9614.4
9625.9
9688.1
VIT
Targeted
87940
88777
96075
83471
100613
106421
90233.9
ImageNet
Non-targeted
16199
16175
16120
16072
16167
16089
16168
VGG19
Targeted
198385
192804
216609
193161
191641
216601
192685
Table 3. AUC of TiBA under different parameters (k. k).
Dataset
Parameter b
b = 0.9
b 0.9
b 0.9
b 0.9
b = 0.9
b 0.9
b 0.9
Model
Parameter
b = 0.55
0 = 0.575
0.60
b = 0.625
i == 0.65
i =/3/3 2/3
b == 0.70
CIFARTO0
Non-targeted
8763.6
8790.2
8657.4
8605.4
8681.8
8784.6
8816.2
WRN
Targeted
22786
22288
21977
20799
22806
22973
23172
TinylmageNet
Non-targeted
31864
31230
30898
29437
29978
30026
30569
WRN
Targeted
121442
120874
115260
115681
116891
116976
117997
Table 4. AUC of TiBA under different parameters (6, b) against robust trained models.
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 perturbation
optimization.
H. Appendix Experiment on Attack Success Rate
The reduction in query complexity under the same perturbation budget is shown in Table 5. We evaluate the performance
of TtBA on the ImageNet dataset across four models: VGG-19, ResNet-50, Inception- V3, and ViT-B32. Following the
setup of CGBA, we set the query budget to 10,000 and the maximum & perturbation strength to = 2.5. We then randomly
choose 500 images from ImageNet and compare the Attack Success Rate (ASR) and the average (median) number queries required for successful attack. The results are presented below.
Model
VGG
ResNet -50
Inception -V3
VIT
Attack
-19
-B32
HSJA
Query
2051.1
1833.8(1209.5)
2851.1(2080.1)
1873.9(947.5)
ASR
61.0%
38.8%
57.2%
59.6%
CGBA
Query
2500.9(1528.5)
3450.7(2679.00
3169.3(2363.0)
2447.8(1797.0)
ASR
88.2%
52.0%
74.4%
79.6%
TBBA
Query
2350.8(148)
(550.((148..0)
3546.6(2754.0)
3098.8(2175.0)
2384.4(1781.5)
ASR
93.2%
61.8% %
80.0% %
80.4%
Table 5. Comparison of decision-based untargeted attacks on the ImageNet dataset with 10,000 query budgets and maximum &2 perturba- tion strengths 2.5.
The results show that TtBA achieves the highest attack success (ASR) across all four models. Regarding the number of queries, HSJA has the lowest average (median) number of queries, but this is due to its much lower ASR compared to CGBA and TıBA. As is well-known, some images contain robust features that require more queries for a successful attack. TiBA, with has significantly higher ASR, is able to successfully attack these robust images, thus requiring more queries on average. Meanwhile, with a similar ASR, TIBA outperforms CGBA terms of average (median) queries. ResNet-50, TtBA also achieves significantly higher ASR (61.8%) compared to CGBA (52.0%).
18


Reviews:
[{"review_id": "VxjZ5jywho", "reviewer": "Reviewer_UW3F", "summary": "The paper proposes the TtBA method for decision-based black-box adversarial attacks. \nIt introduces a new bridge direction, a weighted combination of the current direction and its normal vector, controlled by a weight parameter $k$.\nExperiments on multiple datasets and models show that TtBA outperforms state-of-the-art methods in both targeted and non-targeted attacks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n    (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.\n\n    (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.\n\n    (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.\n\n    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.\n\n2. 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.\n\n**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?**", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "## Strength\n\n- The proposed method improves the performance of decision-based adversarial attacks.\n\n- The paper is well written.\n\n## Weakness\n\n- The contribution of this paper is a little weak, from my perspective.\n\n- Some settings are somewhat empirical and without rational explanation. For example,  $k = 2/3k^i_{bridge}$.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "n/a", "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": "RWbWpJsvwV", "reviewer": "Reviewer_1Mse", "summary": "The manuscript introduces an innovative bridge direction to optimize the adversarial perturbation by linearly combining the current unit perturbation direction with its unit normal vector. Via experiment observation, k= 2/3 k_{bridge} can yield a near-optimal perturbation direction. Besides, the paper designs a simple and effective approach to detect and escape the local optima, making the proposed method better than the SOTA.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. \n\n1. 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}$. \n\n- 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}$. \n\n- 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.\n\n2. 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.\n\n    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. \n\n    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.\n\n3. 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.\n\n    **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.\n\n    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.\n\n4. **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.\n\n    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.\n\n**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?**", "claims_and_evidence": "The novelty claims and theoretical derivations are reasonable.", "methods_and_evaluation_criteria": "The proposed method and the used criteria, including evaluation datasets, are common and representative.", "theoretical_claims": "I check the theoretical claims and the corresponding proofs are correct.", "experimental_designs_or_analyses": "The experiments and results are convincing.", "relation_to_broader_scientific_literature": "The optimization strategy may be somewhat insightful to other fields.", "essential_references_not_discussed": "Not enough.", "other_strengths_and_weaknesses": "Strongs: For targeted attacks, narrow adversarial regions lead to being more easily trapped in local optima. \nWeakness: Why d_{bridge}^{i} can be ensured to have identical decision bourndary as \\hat{d}^{i}, as shown in Figure 1.", "other_comments_or_suggestions": "The paper includes certain novelty components, but seems to be not enough to get the bar of the ICML.", "questions_for_authors": "In total, the proposed method is only an improvement of existing techniques, mainly based on HSJA, TA, qFool, GeoDA, QEBA, and CGBA. No brand-new insight is found to contribute to AI security fields. Finding a k=2/3k_{bridge} by experiments matched with some theoretical verification, designing an escape scheme to skip the local optima, and so on are not too challenging and very innovative. The performance improvement is not very significant, some are even below the sota results.", "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": "Cegt3mEIfD", "reviewer": "Reviewer_i6yX", "summary": "This paper introduces a decision-based black-box adversarial attack, termed Two-third Bridge Approach---TtBA, that focuses on optimizing perturbation directions for attack queries by leveraging normal vectors and the *bridge* direction, to relieve query complexity. This *bridge* direction is a weighted combo of the current perturbation direction and its normal vector, where the weight parameter is k. Through empirical evaluations, the authors show $k=\\frac{2}{3}k_{\\text{bridge}}$ offers the optimal directional alignment. With validations on various datasets, TtBA shows improved performances over existing non-targeted and targeted attack methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. \n\n1. 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/\nDecisionBoundaryofRobustViT.pdf). In the figure, the decision boundary remains smooth and locally concave.\n\n    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](https://anonymous.4open.science/r/TtBA-6ECF/DecisionBoundaryofRandResizePad.pdf). 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.\n\n    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.\n\n2. 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**. \n\n- 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.\n\n- **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!\n\n3. **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. \n\n| Attack | Model  | VGG-19            | ResNet-50        | Inception-V3      | ViT-B32          |\n|--------|--------|-------------------|------------------|-------------------|------------------|\n| HSJA   | Query  | **2051.1(1071.8)** | **1833.8(1209.5)** | **2851.1(2080.1)** | **1873.9(947.5)** |\n|        | ASR    | 61.0%             | 38.8%            | 57.2%             | 59.6%            |\n| CGBA   | Query  | 2500.9(1528.5)     | 3450.7(2679.0)   | 3169.3(2363.0)     | 2447.8(1797.0)   |\n|        | ASR    | 88.2%             | 52.0%            | 74.4%             | 79.6%            |\n| TtBA   | Query  | 2350.8(1481.0)     | 3546.6(2754.0)   | 3098.8(2175.0)     | 2384.4(1781.5)   |\n|        | ASR    | **93.2%**         | **61.8%**        | **80.0%**         | **80.4%**        |\n\n- 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.\n\n**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?**\n\n[1] Mao, Xiaofeng, et al. \"Towards robust vision transformer.\" In Proceedings of the IEEE/CVF conference on Computer Vision and Pattern Recognition. 2022. \n\n[2] Xie, C., Wang, J., et al. \"Mitigating adversarial effects through randomization.\" In arXiv preprint arXiv:1711.01991.", "claims_and_evidence": "The claims made in the submission are partially supported by empirical evidence. The major concern of the reviewer is that, does the hypothesis that the decision boundary of DNNs is smooth and locally concave still hold for robust models? Only a robust WideResNet was studied in the experiments. The reviewer finds this to be slightly lacking. Are other adversarial defenses such as input transformation-based ones, and adversarial training techniques tailored for ViTs, etc., relevant under this context?", "methods_and_evaluation_criteria": "The evaluation setups are reasonable and supportive of this work.", "theoretical_claims": "The reviewer briefly went through the proofs in the Appendix and find that they are supportive of the claims made, but the reviewer did not check the correctness of the proofs.", "experimental_designs_or_analyses": "Experimental designs are valid and supportive of the effectiveness of this proposed method.", "relation_to_broader_scientific_literature": "The paper makes significant contributions to the broader scientific literature on black-box adversarial attacks, where research on decision-based hard label attacks is essential in theoretical and practical advancements.", "essential_references_not_discussed": "A few major decision-based attacks introduced in [1-2] are missing in the current experimental comparisons. The authors should discuss the relationship of TtBA to these works and/or explain why they were not included.\n\n[1] Wan, Jie, Jianhao Fu, Lijin Wang, and Ziqi Yang. “BounceAttack: A Query-Efficient Decision-Based Adversarial Attack by Bouncing into the Wild.” In 2024 IEEE Symposium on Security and Privacy (SP), 1270–86, 2024. https://doi.org/10.1109/SP54263.2024.00068.\n\n[2] Park, Jeonghwan, Paul Miller, and Niall McLaughlin. “Hard-Label Based Small Query Black-Box Adversarial Attack.” In 2024 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 3974–83. Waikoloa, HI, USA: IEEE, 2024. https://doi.org/10.1109/WACV57701.2024.00394.", "other_strengths_and_weaknesses": "**Strengths:**\n- The authors are to be congratulated with the extensive experiments on all 5 datasets with various common model architectures that include CNNs and ViTs.\n- One of the major concerns, i.e., why 2/3 is the optimal parameter, has been explained in detail and empirically validated (in Figure 4 and Appendix G).\n\n**Weaknesses**: \n- Apart from the concerns mentioned above, the reviewer find that the experiments are quite focused on comparing perturbation size ($\\ell_2$ distance) under the same query budget. The reviewer was kind of expecting that the work reports on the inverse, that is, the query complexity reduction under the same perturbation budget?", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "1y8XuUqMyH", "reviewer": "Reviewer_EhyV", "summary": "The paper proposes a novel decision-based black box attack against image classifiers. The attack is called TtBA and it is based upon exploiting the geometry of the decision boundary. It introduces a notion of the $k_{bridge}$ metric and discusses how it helps in constructing an efficient adversarial example. The attack is demonstrated to outperform the existing methods on a wide range of datasets and models (undefended and defended) in the untargeted and targeted attack settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's meticulous evaluation and valuable comments, which have greatly helped improve our manuscript. \n\n1. 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.\n\n2. 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.\n\n3. Following your valuable advice, we will carefully **simplify Figure 1** in the revised paper. \n\n4. 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.\n\n| Model (Dataset) | ViT (CIFAR100) | WRN (CIFAR100) | CNN (CIFAR10) | WRN (CIFAR10) |\n|----------------|----------------|----------------|---------------|---------------|\n| AVG ℓ₂         | 0.779          | 0.991          | 0.180         | 1.198         |\n| AVG K_bridge   | 0.370         | 0.350          | 0.362         | 0.341         |\n\n5. 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. \n\n| Dataset (model)      | Attack Type  | b̌=0.55 | b̌=0.575 | b̌=0.60 | b̌=0.625 | b̌=0.65 | b̌=2/3 | b̌=0.70 |\n|-------------|-------------|--------|---------|--------|---------|--------|-------|--------|\n| **CIFAR100** (WRN) | Non-targeted | 8763.6 | 8790.2 | 8657.4 | **8605.4** | 8681.8 | 8784.6 | 8816.2 |\n|              | Targeted    | 22786  | 22288   | 21977  | **20799** | 22806  | 22973 | 23172  |\n| **TinyImageNet** (WRN) | Non-targeted | 31864 | 31230 | 30898 | **29437** | 29978 | 30026 | 30569 |\n|              | Targeted    | 121442 | 120874 | **115260** | 115681 | 116891 | 116976 | 117997 |", "claims_and_evidence": "The claims made in the paper are supported by empirical observations, formal analysis (Appendix) and extensive experimental results (Section 5 and Appendix).", "methods_and_evaluation_criteria": "In the line 169 targeted attack is formulated via a target image $x_{target}$ with its corresponding label $f(x_{target})$ rather than a more typical formulation via a target label $y_{target}$ i. e. achieving $f(x)=y_target$. It is not clear whether evaluating attack efficiency in the targeted setting with this formulation is reasonable. \n\nOther than that the evaluation methods and criteria seem to make sense for this problem.", "theoretical_claims": "There appear to be no proofs in the main part. The derivation in the Appendix were not carefully checked.", "experimental_designs_or_analyses": "It is not entirely clear whether the formulation of a targeted attack is reasonable (see the Methods And Evaluation Criteria Section for details).\n\nOther than that there appear to be no issues. \n\nAdversarial example definition in the line 199 doesn't contain clipping the resulting image to [0, 1], probably to do saving some space in the text. But in the code provided along with the submission it was checked that the clamping is happening.", "relation_to_broader_scientific_literature": "The paper relates to the previous analysis of the decision boundary curvature and norm vector-based attacks.", "essential_references_not_discussed": "There appear to be no missing essential references.", "other_strengths_and_weaknesses": "Strengths\n\n1. A novel black-box attack outperforming state of the art, as demonstrated in extensive experiments.\n2. Studying decision-based attacks is important because they are more practical than other types of black box attacks and can pose a significant threat for safety-critical machine learning applications.\n\nWeaknesses\n\n1. Figure 1 is a bit overloaded with notation. It would be good to simplify it.", "other_comments_or_suggestions": "No further comments.", "questions_for_authors": "1. Have you observed any difference when analysing the curve of the decision boundary (e. g. Figure3) for undefended and adversarially trained models?\n\n2. Does sensitivity analysis in the Tables 2 and 3 include adversarially robust models? Would you expect some other hyperparameters to work better for them?", "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:

Meta-review: Reviewers identified some relatively minor issues regarding additional related work, clarification of the threat model and its access to data, and other clarifying questions. These were all addressed during the response period. Now, it is not entirely obvious why this adjusted threat model, which deviates from prior work, is of utmost importance to the broader ML community. Beyond being merely a methodological difference, the value of this work would be a lot more valuable if connected to more real-world challenges or considerations reflecting actual use-cases of the threat model. As a result, while the work is good and could be interesting, its general value is not totally clear even after reading the discussion, leading to my recommendation of weak accept.
Decision: Accept (poster)