Boosting Ray Search Procedure of Hard-label Attacks with Transfer-based Priors
Authors: Chen Ma
Xinjie Xu
Shuyu Cheng
Qi Xuan
Venue: ICLR 2025 Spotlight (2025)
Keywords: adversarial attack
hard-label attack
decision-based attack
black-box attack
gradient estimation
surrogate model
transfer-based priors
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose a novel prior-guided hard-label attack approach by using subspace projection approximation.

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

Published as a conference paper at ICLR 2025
BOOSTING RAY SEARCH PROCEDURE OF HARD-LABEL ATTACKS WITH TRANSFER-BASED PRIORS
Chen Ma Xinjie Xu
Shuyu Cheng
Xuan
1 Institute of Cyberspace Security, Zhejiang University of Technology, Hangzhou 310023, China
2 Binjiang Institute of Artificial Intelligence, ZJUT, Hangzhou 310056, China
3 JQ Investments, Shanghai 200122, China
(machen, xuanqi J0 jut stuttt....... edu. acu.cn. cn, xxj xx11018@ foxmaiooooilllommmm comm com, csy530216812e com
ABSTRACT
One of the most practical and challenging types of black-box adversarial attacks is the hard-label attack, where only the top-1 predicted label is available. One effective approach is to search for the optimal ray direction from the benign image that minimizes the lp norm distance to the adversarial region. The unique advan- tage of this approach is that it transforms the hard-label attack into a continuous optimization problem. The objective function value the ray's radius, which can be obtained via binary search trick" in gradient estimation to reduce the number of queries. In this paper, we theoretically analyze the quality of this gradient estimation and propose novel prior-guide approach to improve ray search efficiency both theoretically and em- pirically. Specifically, we utilize the crasfer-based priors from surrogate models, and our gradient estimators appropriately integrate them by approximating the projection of the true gradient onto the subspace spanned by these priors and ran- dom directions, in a query -ffereeffiicien manner. We theoretically derive the expected cosine similarities between the obtained gradient estimators and the true gradient, and demonstrate the improvement achieved by incorporating priors. Extensive experiments on the ImageNet and CIFAR- 10 datasets show that our approach significantly outperforms 11 state-of-the-an methods in terms of query efficiency.
"sign high query cost. Existing methods
INTRODUCTION
Adversarial attacks represent a major security threat to deep neural networks (DNNs), where subtle, imperceptible perturbations are crafted to cause misclassifications To assess DNN robustness and uncover vulnerabilities, the research community has developed various adversarial attack strategies. As result, adversarial attacks and defenses have become a focal point in AI security research.
Based on the available information about the target model, adversarial attacks can be broadly classified into white-box and black-box attacks. White-box attacks, such those proposed by Madry al. (2088: Moosavi-Dezfooll et al. (2066), rely on the target model's 's gradients with respect to the input, making them less practical real-world applications. Black-box attacks, by contrast, are often more feasible, as they do not require knowledge of model parameters or gradients. As subset of black-box attacks, transfer-based attacks generate adversarial examples using white-box models with the aim of generalizing to other models. While transfer-based attacks do not involve querying the target model, their success rate inconsistent. Alternatively, query- black-box box attacks iteratively interact with the target model to achieve higher success rates. These attacks can be categorized into two subtypes: score-based and decision-based (also known as hard-label) attacks. Score-based attacks (Ma et al.. 2021a) utilize the model's 's output logits guide the attack, whereas hard-label attacks rely solely on top-1 predicted labels, making them particularly practical when only label information is accessible. In this work, focus the problem of reducing query complexity in hard-label attacks.
The difficulty hard-label attacks that the labels can only be flipped near the classification decision boundary, and thus the objective function is discontinuous. As result. the attack requires solving high-dimensional combinatorial optimization problem, which is challenging. Common approaches
(Chen et al. 2020 Brendel al. 2018) start with sample containing large adversarial perturbations

---

Published as a conference paper at ICLR 2025
and iteratively reduce the distortion by moving along the decision boundary towards benign image. However, these methods lack convergence guarantees. To reformulate the problem as a continuous optimization task, ray- eay-search methods have been introduced. Typical approaches such OPT (Cheng et al. 2019), Sign-OPT (Cheng et al. 2020), and RayS (Chen & Gul 2020) aim to minimize an objective function g(),, which is defined as the shortest Ep norm distance along the ray direction O from the benign image to the adversarial region. This function value can be evaluated using a binary search method. Leveraging the smooth and continuous nature of decision boundaries, g(0) is locally continuous, making it amenable to zeroth-orde (ZO) optimization with gradient estimator. OPT employs random gradient- frree (RGF) estimator, but it incurs high query cost due to the binary search in finite differences. Sign-OPT reduces the query complexity by using the sign of the directional derivative in gradient estimation, but significantly sacrifices gradient accuracy.
To solve this problem and improve query efficiency, we employ the same objective function g(0) and propose incorporating the transfer-based priors into gradient estimation. An ideal prior the gradient of g()) from surrogate model, but it cannot be easily obtained since g(0) is non-differentiable due to the binary search. Instead, we propose a surrogate loss, whose gradient is proportional to that of g(0), to obtain the prior. Once the transfer- manserr-based priors are obtained, we must design better gradient estimators that effectively integrate these priors. This is particularly challenging under the hard-label restriction, as accurately determining the value of g(0) is costly. As result, previous prior-guided methods for score-based attacks such as PRGF (Cheng et al.) 2021] Dong et al. 2022] are not suitable in this context. Thus, we need explore how improve the gradient estimator with additional priors while minimizing queries. To achieve this, we propose two algorithms: Prior-Sign-OPT and Prior-OPT. They estimate the gradient
query-efficieet manner by approximating the projection of the true gradient onto subspace spanned by priors and randomly sampled vectors. We provide a thorough theoretical analysis to validate their effectiveness and offer theoretical comparisons between Sign-OPT and our approach. In particular, Prior-OPT achieves better approximation of the subspace projection with only slightly more queries, and can adaptively adjust the weight of each prior based on its quality, striking balance between gradient accuracy and query efficiency. While several methods (Brunner et al.] 2219); Shi et al., 2023) attempt to combine transfer- and decision based attacks, they lack theoretical guarantees and often perform poorly. Crucially, in the hard-label setting, these approaches fail to effectively address the challenge of appropriately weighing the prior when it deviates significantly from the true gradient. Our approach resolves this issue and naturally scales to priors from multiple surrogate models, demonstrating further improvement in attack performance.
To summarize, our main contributions are follows.
1. Novelty in hard-label attacks. We address the problem of introducing the transfer-based priors into hard-label attacks by employing the subspace projection approximation, which significantly improves the accuracy of gradient estimation with slightly more queries. Our approach not only strikes a balance between gradient estimation and query efficiency, but also elegantly integrates priors from multiple surrogate models to further improve performance.
2.
Novelty in theoretical analysis. We analyze the quality of our gradient estimators and that of the orthogonal variant of Sign-OPT, enabling theoretical comparisons. To our knowledge, this is the first work to derive the expected cosine similarities between estimators the Sign- OPT family and the true gradient, theoretically guaranteeing performance improvement.
3. Extensive experiments. Extensive experiments conducted on the ImageNet and CIFAR-10 datasets show that our approach outperforms 11 sfute-of-the-a methods significantly.
2 RELATED WORK
Hard-label attacks can be categorized into boundary-search and ray-search approaches.
The boundary-search approaches start from large perturbation or an image of the target class and then reduce distortions by iteratively moving along the decision boundary towards the original image. Boundary Attack (BA) (Brendel et al. 2018) is early representative method, and its query efficiency is relatively low. SeppSkkpJumpAtttce (HSJA) (Chen et al., (0220) estimates the gradient at the decision boundary to update the sample and then finds the next boundary point by moving it towards the benign image. Tangent Attack (TA) and Generalized Tangent Attack (G-TA) (Ma et al.) 2021b) find optimal tangent point virtual hemisphere or semi-ellipsoid to efficiently generate
2

---

Published as a conference paper at ICLR 2025
the adversarial example. CGBA (Reza al. 2023 conducts boundary search along semicireular path on a restricted 2D plane to find the boundary point. To avoid gradient estimation, SurFree (Maho et al., 202T) and Triangle Attack (Wang et al. (022) find the adversarial example in DCT subspace to improve query efficiency. Evolutionary (Dong et al., 2019) adopts the (1+1)-MMAEES simple yet effective variant of Covariance Matrix Adaptation Evolution Strategy, to efficiently generate adversarial examples. Adaptive History-driven Attack (AHA) (Li al., (021)) gathers data of previous queries as the prior for current sampling, which improves the random walk optimization.
The ray-search approaches aim to find an optimal direction that reaches the nearest adversarial region. As mentioned Section | it challenging address both the high query complexity issue of OPT and the low estimation accuracy issue of Sign-OPT. RayS (Chen & Gu (2000) avoids gradient estimation and employs hierarchical search step to efficiently find the optimal direction. However, RayS only supports untargeted f attacks. Since the query efficiency of previous ray-search approaches has not surpassed that of boundary-search methods, they have attracted less research interest and remain insufficiently studied. We note that the mechanisms of OPT and Sign-OPT remain poorly understood, and their inefficiency stems from the limited precision in gradient estimation.
Several methods attempt to combine transfer- and decision-based attacks, but the critical issue, namely how to weigh the prior when it deviates significantly from the true gradient, has not been well addressed. For example, Biased Boundary Attack (BBA) (Brunner al. 2019), Customized Iteration and Sampling Attack (CISA) (Shi et al. (023) and Small-Query Black- Attack (SQBA) (Park al., 2024) set the prior's 's coefficient empirically rather than through theoretical analysis. In contrast, our approach dynamically calculates optimal coefficients, improving gradient estimation accuracy.
THE PROPOSED APPROACH
3.1 THE GOAL OF HARD-LABEL. ATTACKS
Given a k-class classifier f Fd + R and a benign image x E [0, 1] which is correctly classified by f. the adversary aims to find an adversarial example Xadv with the minimum perturbation such that (Xav)) outputs an incorrect prediction. Formally, we formulate the attack goal as:
min d(xadv: x) s.t. (XXav) =1,
Xate
where d(xadv; x) = ||xadv - x1Ip is the Ep norm distortion, and $ (-)) is a success indicator function:
if ÿ = Madv in the targeted attack, ú A y in the untargeted attack,
(XXadr)
otherwise,
where ÿ arg max;e(1.....)) .) / (Xadr); is the top-1 predicted label of S. y IR is the true label of and Yadv E IR is target class label. In this study, we follow Cheng et al. (2019 2020) to reformulate
the problem ①1 the problem of finding the ray direction of the shortest distance from x to the adversarial region:
min (0)
g(0) where 9(0) :00)=inf(( > 0, (x
--11 1).
(3)
100
Note that (0) = too when the set is empty, since inf 0 too by convention. Finally, the adversarial example is x g(0*) T and 0* is the optimal solution of problem
3.2 THE OPTIMIZATION OF SEARCHING RAY DIRECTIONS
The previous works (Cheng al. 2019 2020 attempt optimize the problem (3)
by using ZO methods. However, the restriction of hard-label access results high query cost of the gradient estimation, because obtaining single value of g(0) requires performing binary search with multiple queries, and the gradient estimation with finite difference requires multiple computations of g()). Sign-OPT (Cheng al. 2020) replaces the finiteddifference term g(O + ou) g(0) with (g) + ou) g()),, which improves query efficiency by only using a single query (Eq. (8). However, significantly reduces the accuracy of the gradient estimation. We propose to incorporate transfer-basee priors to enhance accuracy without significantly increasing query complexity, thus achieving an optimal balance between query complexity and estimation accuracy.
3

---

Published as a conference paper at ICLR 2025
The first challenge is how to obtain
h(Gu. 97 (Do)) ) =0
a transfer-basee based prior Vgz (0) from a
h(00 A02. 97 (0o1)
surrogate model J, where gy (0) rep- resents the shortest distance along the direction 0 to the adversarial region of
max
1000 031.0)(00)) = =}, -maxit 83
22 87(00 A02) 33 (06) 0
100
A0:) gy(00) <0
f. This is challenging because 93 (0) is typically evaluated using binary search, making it non-differentiable. To address this, for any non-zero vec- tor 0g E Ra such that 97 (0o) < +oc, we define a surrogate function h(0, X) such that (g) = c. Vah(Oo. Ao). where A (0n) (0n) is treated as a con- stant during differentiation. Here, A non-zero con- stant. The surrogate function h68 X) defined as the negative Carlini &
With An = 2z (6o) fixed radius,
non-adversarial region with label y
h(0, Ag) defined spherical surface.
adversarial region
(1) When 07(0) + with 201, A(0, A) 4 well.
(2) When gy(0) 1 with 202, h(0, A) f as well.
Figure 1:
Geometrical explanation of Vgy(On)
scalar, and
Veh Ao) by taking an untargeted attack as an exam- ple. When gj 9)(0) reduces/increases with small A6, h(0, A) changes at similar rate. The formal proof is in Appendix A
Wagner (C&W) loss function of
[ max Joz h(0, A) = max J, B... if targeted attack.
if untntargeted attack,
(4)
[89 ); is an abbreviation for the i-th element of the output of j. and x is the where 7, = ix
0
original image. Any non-zero zero scalar can be used X, but the specific value Ào = 90 (f() yields gradient proportional to Vgg (fo). The value Ao is obtained through binary search, where h(Oo, Ao) represents the negative C&W loss the decision boundary of the surrogate model
j. The geometric explanation and formal proof of Vgy(0o) = c Vgh(fo, Xo) are presented in Fig. and Appendix A
In targeted attacks, determining an appropriate An value becomes a challenging task. This is because the spatial distribution of classification regions, along with the shape and extent of the decision boundaries, varies across different models. Although predefined target class Yadv along the 0 direction in the target model f. the same direction may not lead to the region of the class Yndv in a surrogate model f. Therefore, we must set new target class Vadv before determining An and computing Eq. (4). See Appendix B for detailed steps.
locate the region corresponding to the
Given s non-zero vectors ki,.... k2 representing transfer-hased priors from surrogate models and q 8 randomly sampled vectors r; ~ N/ I) for i = 1.....9 8, our objective is to estimate a gradient v* Re Vg(O) as accurately as possible using these 9 vectors. In the score-based attack setting, there is a subspace projection estimator theory (Meier et al. [019 Cheng al. 2021 that can solve this problem. Based on this theory, the optimal estimated gradient v that maximizes its similarity with the true gradient is given by Proposition 3.1 the score-based setting
Proposition 3.1. (Optimality of the subspace projection estimator) Let ki...., and ri...., -g-s be defined above; let S span (k1, k,, ri,..., ,Fg=s} denote the subspace spanned by these vectors. Then the optimal v" in S that maximizes Vg(O) subject ||v|| = 1 is the Ey-ormallized projection of (g( onto S, denoted as = Vg(()ss.
According to Proposition 3.1. finding the optimal approximate gradient is equivalent to finding a projection of the true gradient onto a oiw-dinensional subspace S spanned by all available vec- tors. The projection of vector onto a subspace can be calculated by summing its projections onto the orthonormal basis of S. To achieve this, construct an orthonormal basis of S via Gram-Schmidh orthonormalization which transforms kj...., k, ri,..., ,T-s into an orthonormal basis .I.-..: Ps, U1...., Ug- Note that .I....: : Ps correspond to kı,..., ... k,, and uı,... Ug correspond to ri, -g- Then, we can compute the projection of (g(()) onto S by Eq. (5)
Vg(0)) P D
Vg( u, u,
(5)
1=1
'Throughout this paper, for any vector x, we denote its normmallede version by x, where X == x/||x||.
4

---

Published as a conference paper at ICLR 2025
Given the queried function values, Vg(()" (((0))u u for the unit norm vector can be approximated by the mhite-iifferenc method, without requiring backpropagation:
Vg(0) T g(0 ou) g(0)
(6)
where a is small positive number. By plugging Eq. into Eq. (5) we can easily calculate v in the score-based setting as v = Ei= g((top.)
Dizi g(++ou.)-g(0) un However, the hard-label setting, the fiite-diffference requires large number of queries due to the binary search of g()). We propose two algorithms to reduce query cost by computing the approximate projection, i.e. Prior-Sign-OPT and PPior-OPT. With priors, Prior-Sign-OPT uses Eq. improve performance:
sg + op.) g(0)) P + sign(g + ou,) g(0)) u.
Eq. 7 similar the formula Sign-OPT, benefiting from using only single query to calculate the sign of the directional derivative (Cheng et al., 2020):
sign + tu,) (()) = +1, f (x+ g(0)
Stou: [0+ou.ll
=
(8)
-1, otherwise.
The accuracy of the estimated gradient is crucial in optimization. A natural way to assess accuracy is via the following metries: IE[y] and E[ where y the cosine similarity between the estimated and true gradients. We propose novel approach to compute E[>] and E ( for Sign-OPT, Prior-Sign- OPT, and Prior-OPT. Our baseline extends Sign-OPT (Cheng et al. 2020) by employing orthogonal random vectors, while retaining the original name to maintain consistency within the method family,
Theorem 3.2. For the Sign-OPT estimator approximated by Eq. (6 (defined as Eq. (44)) we let
7 = v Vg(0) be its cosine similarity to the true gradient, where TV then
T(
El7] = / r( d+1 V
(9)
B ( 1) (g
(10)
The proof of Theorem 3.2 is included in Appendix For Sign--iOn,,,, we have Theorem Theorem 3.3. For the Pitor-Sign-OPT estimator approximated by Eq. (6) (defined Eg. 82)
let y = v² Vg(() be cosine similarity to the true gradient, where || then
T( r( |VT
Bhi = /
oul (g -5))
1- Σ
(II)
E
acl|
+ q- -
2
1)+1)
1- (I-
9
[(
Σ
lail
(q
8)
1 Σ
(12)
where a; P Vg(0) the cosine similarity between the i-th prior and the true gradient.
The proof of Theorem 3.3 is presented in Appendix C.2 Now we can compare E[7]] of Sign-OPT (Eq. and Prior-Sign-OPT (Eq. (TT). Sign-OPT, applying Jensen's inequality yields the bound Ehi VEhT = (2(g - σ (md). When q < d, E[y] becomes very small, resulting in poor performance. In contrast, Prior Prior-Sign-On Sign-OPT with single prior improve performance. For instance, when attacking an image of size 32 x 32 x 3, and using parameters q = 200 and s = 1, 0.01422 < |1 s 0.611. E[y] of Prior-Sign-OP OPT surpasses that of Sign-OPT. However, Prior-Sign- OPT may underperform Sign-OPT in certain cases, such as when jay 2 0.612 the example above, because it applies sign-based multipliers both random vectors and priors. Intuitively, random
5

---

Published as a conference paper at ICLR 2025
F13
sign(u( + ou;) 200)2
9 ap
for i E {1.
2 ov
Fg
F5
one query for u.
hindry seurch
binary search
adviraarraaallll region
non adv-vvvvvaaaalll region
110
adversarial region
adversarial region
(a) Get prior 11 and sample rs.
(b) Orthomormal basis.
(c) Estimate a sign bused v (d) Estimate v with v and p
illustration of the gradient estimation of Prior-OPT with single transfer- based prior. In Fig. 2a we first sample random vectors r, NN I) for i 1..... and obtain a transfer-based prior k1 using Voh A), where 1(0,, A) is defined in Eq. 4 Then, as shown Fig. 26 we perform Gram-Schmidt orthonormalization on these vectors to obtain an orthonormal basis PI. P1.U1..... Mp-11 where P1 k1 Next, we estimate V1 based on Eq. (14) with
Figure 2: Simplified
ui..... u (Fig. 2 where each (ign(g(0 + ou,) g(0) requires only a single query (Eq. (8).
Finally, as shown Fig. 2d we estimate a gradient v based Eq. (3) with P1 and v1, where the values of g + op and g( [ are obtained via the binary search with multiple queries.
vectors Ui...... U1 have relatively consistent cosine similarities with the true gradient as they are identically distributed, allowing for efficient sign-based estimation. In contrast, the cosine similarities between the priors pl..... Ps and the true gradient differ, requiring more precise estimation. To address this, we propose Prior-OPt OPT that treats priors and random vectors differently. Fig. iillutrattss the process of gradient estimation in Prior-OPT, which is based on the following formula:
g(f + op:) g(0)
g(O + [vV g(
p,
VL.
(13)
1=1
where TT is the l normalization of VT, and T1 obtained by:
sign(g(0 + ou;) g(0) u.
(14)
Since random vectors Upy...y Ug poorly align with Vg(0), aggregate them into single vector
v using a less accurate estimator in Eq. (14) which is orthogonal to all priors. Compared with Eq.
Eq. (3) provides a more accurate projection approximation. We now present Theorem 3.4
Theorem 3.4. For the Prior-OPT estimator approximated by Eq. (6) (defined as Eq. 114 ), we let
= V (g( be its cosine similarity to the true gradient, where v
[i then
(q s)(1 [1 Ei af)
Ebl Z
2
(15)
I8 I(--att
Eb] <
Σ
0 d-s (g- 10---1144 11)+)
2
(1-
a?
(16)
i=1
1=1
Eb7
Σ
a
2 (2 (2 (1-
f--aa ai
(17)
d
1=1
where a; = P:
(g( the cosine similarity between the i-th prior and the true gradient.
The proof of Theorem 3.4 4 is included in Appendix C.3 E[ is the second-order moment, which reflects the magnitude y in a statistical sense. Under certain assumptions, E[["]] directly affects the convergence rate of optimization algorithms (Cheng al. 2021). Intuitively, a larger indicates more accurate gradient estimation, leading to faster optimization and improved query efficiency. Next, we compare E/>?] for Prior-OPT (Eq. (7) and Sign-OPT (Eq. (10). Under the reasonable assumption that q < d, Prior-OPT outperforms Sign-OPT >
1 af > gd (where 2s is an approximate value), nd
which is easily satisfied for large d. See Appendix D for details.
Algorithm I Ismmmarizes our attack procedure. The initialization of 6g has two options in untargeted atlacks: (1) HRND, select the best direction with the smallest distortion from 100 random directions

---

Published as a conference paper at ICLR 2025
Algorithm 1 Prior-Sign-OPT and Prior-OPT attack
Input: benign image x. objective function g(-), attack success indicator Φ(-) defined in Eq. 2 iteration T', method m E { Prior-OPT, Prior-Sie Siinor-- the initialization strategy of untargeted attacks init (0 ORND), ). the maximum gradient norm gmax, attack norm
p E (2) surrogate models 8 = {} I.....:.. f.).
Output: adversarial example x* that satisfies o(x*) =
Xo PGD(x, Ji) if init Dg otherwise random Xn that satisfies ((xx) = 1 is selected for the GRND strategy; b the targeted attack selects an image from the target class as Xo.
Oo + 1:00 Xn-x
do f | xlln:
x
for r in , do
for J, in S do
1 BinarySearch(x, 0-- 1, J.: $):
k; < Voh(0;-1, 11) on f; with d--1 treated as a constant in differentiation; & obtain transfer-based priors.
end for
r, IV(0..) for i
Pi..... Pa; ui..... un- < Schmidt orthonormalization ((aaaaliiiiiiiiikk....... kg Fi..... rg--))))
Estimate gradient v using Eq. 77 if Prior-
otherwise using Eq. (13)
v t- ClipGradNorm(y" gmax):
77" LineSearch(x, v", Lb d 0c-1); search step size.
0. < f--1 n²vv" Oe < 0,
|
de + (lg(0.) Ocllp:
end for
return x* t x + ((0r) |0rl12
as 0o: (2) OPOD; we apply PGD Madry et al. 2018) to attack surrogate model Л, to initialize Do which uses the transfer-based attack as initialization. In largeted attacks, we initialize Og with an image Ra selected from the target class in the training set. In each iteration, the algorithm first calculates the gradient of Eq. (4) on each surrogate model J, in 3 to obtain the priors kı,..., kg. Then, we combine these priors and the randomly sampled vectors ri,...,. Kg-s into list L, where the priors positioned ahead of the random vectors. After performing Gram-Schmidt orthonormalization on IL. the orthonormal vectors P1: Ps. u1..... ug-= are obtained, representing an orthonormal basis of the subspace. With these orthonormal vectors, we estimate the gradient v* using Eq. (7) for Prior-Sign-O OPT or Eq. (13) for Prior-OP respectively. Then, we employ the gradient clipping technique to address the large-norm gradient problem caused by finite difference. Finally, we use line search to find the optimal step size 1)" and perform a gradient descent step to minimize gf)).
4 EXPERIMENTS
4.1 EXPERIMENTAL SETTING
Datasets. All experiments are conducted on two datasets, i.e., CIFAR-10 (Krizhessky & Hinton 2009) and ImageNet (Deng al. 2009). The image sizes are 32 x 32 x for CIFAR-1Ó, and either 299 x 299 3 or 224 x 224 x 3 for ImageNet. We randomly select 1,000 images from the validation sets for experiments.
targeted attacks, for the same target class, we use the same image Xg as the initialization for all methods. We set the target label as Yadv (y + 1) mod C, where y is the true label and C' is the number of classes. Results of the CIFAR-10 dataset are presented in Appendix G.5
Method Setting. The hyperparameter settings of all methods experiments, surrogate models are denoted as subscripts in the method names. For instance, Prior- OPT RecNesuscaeei means using ResNet-50 and Con the surrogate models for Prior-OPT, and Prior-OPT pPGo RosNeco applies PGD attack on the surrogate model ResNet-50 to initialize 0g
listed in Appendix In the
Compared Methods, To provide a comprehensive comparison, we select 11 state-of taite-of-the-ae art hard- label attacks, including Sign-OPT, SVM-OPT (Cheng et al. 2020), HSJA (Chen al.) 2020).
7

---

Published as a conference paper at ICLR 2025
Triangle Attack WWann et al. 2022), TA, G-TA (a et al.) 2021b). SurFree (Maho et al. (021))
GeoDA (Rahmati et al. 2020), Evolutionary (Dong et al. 2019). BBA (Brunner et al. 2019); and
SQBA (Park et al. 2024). SQBA, Triangle Attack, GeoDA, and our f initialization strategy (e.g..
Prior-OPT 0g ResNes50 only support untargeted attacks. Both BBA and SQBA use a single surrogate
model, denoted as a subscript in the method name (e.g., SQBARESNCCO).
Target Models and Surrogate Models. In the ImageNet dataset, select 8 neural network architectures as the target models, including Convolutional Neural Networks (CNNs) and Vision Transformers (ViTss. The selected target models are Inception-v3 (Szegedy et al. 20T6), Inception-v4 (Szegedy et al. (017), ResNet- 101 (He et al., 2016), SENeet 1.54 (Hu et al. 2018). ResNeXt-101 (64 x 4d) (iie et al. (017). Vision Transformer (ViT) (Dosovitskiy et al. (2021) Swin Transformer (Liu et al. 2021) and Global Context Vision Transformer (GC ViT) (Hatamizadeh et al. (023)) The
Inception- and Inception- require a resolution of 299 x 299 for the input images, and we select Inception- nncepiio-RReNNet-Z. (IncRes and Xception as the surrogate models. ResNet-50 (He et al.) (016)) and Con ViT (D' Ascoli et al. 202T are selected as the surrogate models for the remaining target models. In the attacks on defense models, we use the adversarially trained (AT) surrogate models (e.g.. AT(ResNetl 10)), which are marked as subscripts in the method names, such as Prior-OPT ATTReNNet10)-
Evaluation Metric. All methods are evaluated using the mean distortion over 1,000 images as [ ExEx (I|xaa>> - x) under different query budgets, where X is the test set and p E {2, oo} is the attack norm, We also report the attack success rate (ASR) under the specific query budget, which is defined as the percentage of samples with distortions below a threshold e. In f--norm attacks, we set the threshold
v0.001 d on the ImageNet dataset, where d is the image dimension. Following we calculate the area under the curve (AUC) of le distortions versus queries.
Li et al.
2021
4.2
COMPARISON WITH ATR ATTACKS
Table 1: Mean l distortions of different query budgets on the ImageNet dataset.
Target Model
Method
Untaagettd Attack 65K
Targoted Attack
@ @1K
#2K
8K
@ 10K
1K
@ 2K
@5K
@SK @ 10K
15K
@2UK
HSJA (Chen et al. 2020
75.392
44.530
20.567
14.194
11.645
95.876
79.001
52.176
39.190
32.951
24.546
19.522
TA (Miret ai 20210
67.496
42.233
20.352
14.175
11.694
78,883
61 .90
40.069
31.506
27.111
21.079
17.319
G-TA Ma mil wucth
67,842
41.946
19.962
13.865
79.297
62.291
40.529
30,941
26.427
20.268
16.569
Sign-OPT Cheng of 2020
86,716
48.233
18.258
11.067
8.786
80.366
65,200
42,866
32.104
27.526
20.394
16,281
SVM-OPT (Chsig drate 20120
89,863
47.914
11.091
79.807
65.590
43,426
33.090
28.797
22.354
18.795
GeoDA Rahmalt el al. 2000
29.157
20.119
12.487
11.010
9.688
Exolationary Done
2019
61,966
42.6 666
13,382
81.761
65.060
43.021
120
27.385
19:942.
15.610
Surfree Mahb et Al 20zl
51.685
38 482
22 845
16.174
13,818
84,925
74,887
55.991
44.475
39.004
29.354
23.153
Inception-ve
Triangle Allas
Wang
27.217
25
23.743
22.581
SQBAnaaav
Park et al 20/44
26.134
19.035
11.189
8.432
7.417
SQBAsaziiee
23.672
8,036
7.115
BBA Bruiing et cll
2019
38.782
28.437
18.757
15.474
14.191
66.746
56.283
41.324
34.066
30.942
25 757
22.630
BBAxaqiia Brunner al 2019
43.317
31.519
20.504
16.712
63.069
39.740
36.166
25 23.438
22.561
Prior-Sign- Siign-PPTaresss
81.991
42,403
12.835
7.365
5.842
74,597
55.421
31.856
22.958
19.513
14.361
11,665
77.683
37.099
9.058
5.198
4.199
69.526
49.
26.882
19.324
16.697
12.821
10.769
Prior Sign OPT Lgp lackeaV
23.596
15.347
8.074
5.729
4.863
Prior Prior-OPTwoa OPTnRRess
49,279
18. 135
5.718
4.451
4.027
67.300
49,842
33.477
602
25.281
21.837
19,800
Prior OPPussevaeeiaii
42.541
13.418
3.919
3,321
60.211
42.631
27.547
23.011
21.441
19.193
17.983
Prior-OPT ag 12
22.852
12.194
6.568
5.114
4.548
HSJA (Chen et al, 2020
37.813
19.386
9.031
6,604
5.637
61.491
44,853
23.947
16.926
14.152
10.791
8.922
(Mirer nr. 1012
37,923
19.867
9.078
6.636
5.674
52.110
20.536
15.
12.885
10.158
8.609
G-TA M 202
b
37.425
19.347
8.948
6,496
5.643
52,550
36.720
20.857
15.436
13.255
10.490
8.933
Sig heng el
2020
51.120
25.290
8.559
5.482
4.572
55.941
86.
23.784
16.541
13.873
10.129
8.267
SVM OPT (Cheng ar
2012
55.802
26.580
9.242
5.988
5.070
56.002
41,899
23.909
17.273
14.848
11.739
10.320
GeoDA [Rahmali el (T3
18,880
12.904
8.039
7.153
6.313
Evolutionary Dong c ah 2019
40.382
25.709
11.925
7.974
6.719
$7.141
40.187
21.782
19.191
12.795
9.677
8.311
SurFiee Malh cl 2
28.228
19.016
10.194
7.321
70.337
53.129
30.054
20.595
16.908
11.794
9.204
VIT
Triangle Allac [Wang a 2022
12.789
12.144
11.064
10.411
10,0977
SQBAu
Paak 20
21.741
14.004
5.861
5.201
SQBAcwan
Park 2 di 2024
12,886
9.762
6.240
4.947
4.452
BRAgaNes0
29
29.755
20.053
12,580
10.375
9.567
43.231
33.365
21.889
17.635
16.046
13.726
12.463
BBAcavT
Brunner CE mi 2019
22.716
16.153
10.893
9.193
8.595
45.588
35.227
22.865
18.325
16.614
14.028
12.623
Prior-Sign- Tuctert
50.161
27.953
9.474
5.872
4.850
55.095
22.354
13.201
9.789
R.048
Prior Sign OPT TPT
46.196
23.869
7.327
4.694
3.967
53.925
38.418
20.673
14.422
12.153
9.090
7.544
Prior-Sign-OPP OPT,pm ym Rasheeii
29.912
18.425
7.848
5.175
4.331
Prior- Prior-OPTassuuss
42,838
22.704
6.024
54.348
24.408
18.
15.803
12.638
11.070
Prior-OPTee.ee TRNNN
26.495
11.287
4.929
3.937
3,609
53.369
40.002
24.706
19.148
17.116
14.114
12.650
Prior-OPT, gg BwNeet
29.099
17.754
8.208
5.782
5.009
8

---

Published as a conference paper at ICLR 2025
Table 2: Mean lg distortions of the different numbers of priors on the ImageNet dataset.
Method
Priors
Target Model: RosNott-1O1' @#2K
Target Model: Swin Transformer" 62K
Target @2K
Model:
GC VIT
@ IK
@5K
@8K
10K
IK
@5K
@88
10K
IK
@5K
@8K
@ 10K
Sign-OPT
prior 37.248
21.235
8.982
5,811
4.754
86,373
53,399
20.686
12,406
9.899
57,903
35.762
14.763
9.047
7.185
prior 350
18.733
6.111
3,718
3.019
84.124
52. 882
20.344
11,880
9:254
57.171
36,949
14,963
8,931
6.899
2 ptiors
32.848
17.548
5.121
3,136
2.593
77.459
43,062
13.614
7.903
6.331
54.896
32.418
11,012
6.651
5,342
Prioe-Sign-OP
priors 31.156
15,455
4,074
2.527
2.122
73.110
37.852
10.264
5.939
4.778
52.744
28.939
8.707
5.245
4.215
priors 29,984
14.707
3.698
2.335
1,989
70.246
34,470
8.526
5.066
4.169
50.256
26.027
6,435
3,804
3.212
priors
29.601
14.195
3,573
2.275
1,951
67.616
32.225
7,321
4,219
3.467
48.935
24.821
6,123
3.601
2,893
T prior 18:355
7.100
2,840
2:324
22138
09:432
39.447
16,336
"T1:241"""""""""""
50.467
29.091
11.537
".311
2 priors 17.373
6,465
2.454
2.096
1.979
41.152
17.977
7.289
5.453
4.896
36,055
16.176
6,094
4.413
3.747
OPT
3 priors
15.373
5.350
1.919
1.714
1.653
36.66
13.877
5,166
4.008
3,687
33.181
13.005
4.702
3.644
3,264
4 priors
15.422
5,220
1.849
1.654
1.596
38,343
12.650
3.784
3.027
2.850
34.396
10.994
3,047
2.356
2.171
5 priors
15.556
5.395
1.881
1.672
1,605
37.712
12,070
3,488
2.747
2.577
33,351
10.369
2.921
2.329
2.159
Five surrogate models: ResNet-50, SENct-154,
ResNeXt- 101 (64 x 4d), VGG-13, SqueezeNet v1.1
2 Five surrogate models: ReaNet-50, VIn CiossVIT MaxVIT VIT
G-TA
40
Alauk
26
Maen Detrtton
50
30
Garree
20
84
3K
4K
6K
7K
10K
2K
OK
BK
12K
14K
10K
1BK
2K
6K
10K 12K
10K 10K
Number Quaenes
Number Chasrtee
Number of Cuartees
(a) TRADES 3o =8/255 (CIFAR- 10)
(b) AT 3o #4/225 (ImageNet
(c) 00 =8/205 (ImageNet
Figure 3: Mean distortions of untargeted attacks on the defense models equipped with the ResNet-50.
100
100
100
PoPhagee
HAM SANOFF
Arook B10000 Rats
00
00
50
10
Aback
10
T4K
12K Nurther of Cuantine
15K
Numbbr of Queres
Nlmber of Guereos
(a) TRADES (CIFAR-1O)
(b) AT 44/25 (ImageNeet
(c) AT ege m 8/285 (ImageNet
Figure 4: Attack success rates of untargeted attacks with &z- mo-m constraint against defense models.
Results of Attacks against Undefended Models. Table I shows the results of attacks against undefended models on the ImageNet dataset. Additional results are in Appendix G.5 In summary:
(1) In untargeted attacks (Table and Fig. D the performance of Prior-OPT significantly surpasses that of all methods, and using multiple surrogate models yields better performance than using a single surrogate model. In addition, the PGD initialization (6PGD) proves effective in early iterations, because establishes high-quality initial attack direction Og through transfer-based attacks.
(2) In targeted attacks, Prior-OPT outperforms Prior-Sign-OPt when the query budget is below 5,000, while Prior-Sign-OPT performs better later iterations with more queries.
(3) Table 2 and Fig. 5c demonstrate that using more surrogate models (priors) can boost performance.
1 1st AT: AT(ResNet-50, ftz- = =8/255), 3rd AT: AT(ResNet-50, ct, = =3), double ATs: combination of both
2nd AT: AT(ResNct-50, 6Lo 4/255), 3rd AT: AT(ResNet-50, ct, = 3), double AT's: combination of both
9

---

Published as a conference paper at ICLR 2025
Results of Attacks against Defense Models. We conduct untargeted attack experiments against two types of defense models, i.c., adversarial training (AT) (Madry et al. 2018) and TRADES Zhang et al. 2019). Figs. B and show that Prior-OPT with two surrogate models (Prior-OPT. double AT& achieves the best performance on the ImageNet dataset and the CIFAR-10 dataset.
4.3 COMPREHENSIVE UNDERSTANDING OF PRIOR-OPT
In the ablation studies, conduct control experiments based on theoretical analysis results and attacks on real images (Fig. 5). In Figs. Sa 5b Sc] we set the image dimension to = 3,072 and E[>] (Eq. p for Sign-OPT, Eq. [1] for Prior-Sign-OPT, Eq. (15) and Eq. (66) for the lower and
upper bound of Prior-OPT) as the metric for gradient estimation accuracy, where V Vg(O). Figs. and 5c are based on g = 50. Fig. 5a uses one prior and shows that Prior-OPT and Prior- Oign-OPT outperform Sign-OPT with different values of a. Fig. 5a also shows that Prior- Por-Siin-OPP performs well when
close to This is because when we set = 1, [ = 1//v in Eq. (IT). Fig. 5b shows that [[y] monotonically increases with for each method, and Prior-Sign-OPP performs worse than Sign-OPT when g > 500. Fig. [5c validates that the performance can be improved when more priors are available, and prioritizing surrogate models with larger a values outperforms random selection. Fig. |c consistent with the conclusion of the experimental results in Table 2 Fig. 5d shows the untargeted attack results of Prior-OPT against Swin Transformer with varying q on ImageNet. A smaller q achieves better performance in the early iterations, but becomes less effective in the late stage of iterations with higher number of queries.
small and E[ decreases when
1.00
0.49
Sigr-OPT
Prio--SignOPT Prax-OPT
0.44
0.80
0.39
0.70
0.34
0.90
0.24
0.20
Sir-OPT
0.15
Sww.-ignnPP..... DPT
0.20
0.10
OFTy-OFTy-02 Pran-Sign-OPT...
0.05
0.00
0.1
02
033
0.8
088
1.0
0.00
200 300 400 500
300 1000
(a) Effect of prior's accuracy
(b) Effect of number of vectors
0.57
70
85
-0
120
80
40
4 1:40
0.45
55
0.40
q
-
65
q
0.28
35
30
0.20
Sign
Pricr-kignOPT.a. Pot--OPToaaaaao ae
20
0.11
Prin-OPT, -pa--aa
10
Prisn
Numbar
Number
(c) Effect of number of priors
(d) Prior-OPT with different
g
Figure 5: Results of ablation studies. Figs. 5a
5b
and
5c
based Eqs.
and 16
CONCLUSION
In this paper, we propose novel hard-label attacks (i.e., Prior-OPT and Prior-Sign-OPT) that incor- porate transfer-based priors into the gradient estimation of the ray direction and significantly boost the attack performance. Through theoretical analysis, prove the effectiveness of our approach: we derive expressions for the expected cosine similarities between the estimated and true gradients, enabling theoretical comparison against the baseline. Therefore, our analysis offers comprehensive understanding Prior-OPT and Sign-OPT. Lastly, we evaluate our approach through extensive experiments, demonstrating superior performance compared to state-ofthhe-e methods.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by Key R&D Program of Zhejiang under Grant No. 2024C01164, by Zhejiang Provincial Natural Science Foundation of China under Grant No. LMS25F020005, and by the National Natural Science Foundation of China under Grant No. U21B2001.
ETHICS STATEMENT
We affirm our commitment to the ICLR Code of Ethics to ensure that our research on adversarial examples and AI security adheres to the highest ethical standards. Our work aims to identify potential vulnerabilities in Al systems with the intention of enhancing their security and resilience. Specifically, our approach can be integrated into the evaluation process for a model's robustness, enabling the study and implementation of targeted defense strategies and providing effective support to strengthen the security specifications of artificial intelligence models. We acknowledge the dual-use nature of this research. We have taken steps to responsibly share our findings, encouraging their use in developing robust defense mechanisms. We remain open to discussions about any ethical concerns that may arise and dedicated to contributing positively to the field of Al security.
REPRODUCIBILITY STATEMENT
We have taken several steps ensure the reproducibility of our research. The appendix provides comprehensive details on the algorithm settings, computational resources, and theoretical proofs. To further support reproducibility, we provide the complete attack code for our approach and all baseline methods at htttt::://// //ithbb com/ www./a/caanc////.ccccccooooaaaae /hard label attacks] These resources intended enable others replicate our experiments.
REFERENCES
Wieland Brendel, Jonas Rauber, and Matthias Bethge. attacks against black-box machine learning models. In International Conference on Learning Representations, pp. 1-12, 2018.
adversarial attacks: reliable
Brunner, F. Diehl, M. T. Le, and A. Knoll. Guessing smart: biased sampling for efficient black-box adversarial attacks. In IEEE/CVF International Conference Computer Vision, pp. 4957-4965, 2019.
Jianbo Chen, Jordan Michael I., and Wainwright Martin J. HogSkiplumpAAttek: query-efficient decision-bar based adversarial attack. In IEEE Symposium on Security and Privacy, pp. 1277-1294, 2020.
Jinghui Chen and Quanquan Gu. RayS: a ray searching method for hard-label adversarial attack. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 7739-1747, 2020.
Minhao Cheng, Thong Le. Pin-Yu Chen, Huan Zhang, JinFeng Yi, and Cho-Jui Hsich. Query- efficient hard-label black-box attack: an optimization-basel approach. In International Confer- ence on Learning Representations, 2019. URL IJ1k6iRqKX
www.nnet/forrm forummiduu
Minhao Cheng, Simranjit Singh, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Sign-OPT: query- efficient hard-label adversarial attack. In International Conference on Learning Representations, 2020. URL https: /tttts://openne
http::/eee//eoeeeeee SK SkITOCNtvS
Shuyu Cheng, Guogiang Wu, and Jun Zhu. the convergence of prior-guided zeroth-order optimization algorithms. In Advances in Neural Information Processing Systems, volume 34, pp. 14620-14631, 2021.
Stéphane D' Ascoli, Hugo Touvron, Matthew L Leavitt, Ari S Morcos, Giulio Biroli, and Levent Sagun. ConViT: improving Vision Transformers with soft convolutional inductive biases. In
11

---

Published as a conference paper at ICLR 2025
International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp.
2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 248-254 2009. doi: 10. 1w.100//CVR..00.5500.....
Yinpeng Dong, Hang Su, Baoyuan Wu, Zhifeng Li, Wei Liu, Tong Zhang, and Jun Zhu. Efficient black-box adversarial attacks face recognition. In IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 7714-7722, 2019.
Yinpeng Dong, Shuyu Cheng, Tianyu Pang, Hang Su, and Jun Zhu. Query-efficient black-box adversarial attacks guided by a rransfer-based prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(12):9536 955)99948,88 2022. doi: 10.1 1100TPAMM22221.1227733..
Alexey Dosovitskiy. Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations, 2021. URL httpp::/openreet net/forum: id=Yi cwF.NTTY
Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 5927-5935, 2017.
Ali Hatamizadeh, Hongxu Yin, Greg Heinrich, Jan Kautz, and Pavlo Molchanov. Global Context Vi- sion Transformers. In International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp.
2023.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778. 2016.
Jie Hu, Li Shen, and Gang Sun. Squeezz-and-exxiine Computer Vision and Pattern Recognition, pp. 7132-7141, 2018.
networks. In IEEE/CVF Conference on
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In IEEE Conference Computer Vision and Pattern Recognition, pp. 4708, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report O, University of Toronto, 2009. URL dittps://wwet www.:wcs..roootocom
htiii//learninn-feeuueeeee
Jie Li, Rongrong Ji, Peixian Chen, Baochang Zhang. Xiaopeng Hong, Ruixin Zhang, Shaoxin Li, Jilin Li, Feiyue Huang, and Yongjian Wu. Aha! Adaptive history-driven attack for bacision-based black-box box models. In /EFE/CVF International Conference on Computer Vision, pp. 16168-16177, 2021.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin Transformer: hierarchical vision transformer using shifted windows. In IEEE/CVF International Conference on Computer Vision, pp. 10012-10022, 2021.
Chen Ma, Li Chen, and Jun-Hai Yong. Simulating unknown target models for query-efficiem black-box attacks. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11835-11844, 2021a.
Chen Ma, Xiangyu Guo, Li Chen, Jun-Hai Yong, and Yisen Wang. Finding optimal tangent points for reducing distortions of hard-label attacks. In Advances in Neural Information Processing Systems, volume 34, pp. 19288-19300, 2021b.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt. Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learn- ing Representations, 2018. URL htt.htpppa.//ppeeeeeeeeeee.e www.nnee//oormmm2.drrIzzzz
12

---

Published as a conference paper at ICLR 2025
Thibault Maho, Teddy Furon, and Erwan Le Merer. SurFree: fast surrogate-free prreegttt-feeeeeeeeeee black-box attack. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10430-104333 2021.
Florian Meier, Asier Mujika, Marcelo Matheus Gauy, and Angelika Steger. Improving gradient estimation in evolutionary strategies with past descent directions. arXiv preprint arXiv:/9/0.05266. 2019.
Scyed-Mohsen Doosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. DeepFool: simple and accurate method to fool deep neural networks. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 2574-2582 2016.
Jeonghwan Park, Paul Miller, and Niall McLaughlin. Hard-label based small query black-box adversarial attack. In IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 3986-3995, 2024.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 8748-8763, 2021.
Ali Rahmati, Seyed-Mohsen Moosavi-Dezfooli, Pascal Frossard, and Huaiyu Dai. GeoDA: geometric framework for black-box adversarial attacks. IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 8446 8455, 2020.
Md Farhamdur Reza, Ali Rahmati, Tianfu Wu, and Huaiyu Dai. CGBA: curvature-aware geometric black-box attack. In IEEE/CVF International Conference on Computer Vision, pp. 124-133, 2023.
Oswaldo Rio Branco de Oliveira. The implicit and the inverse function theorems: easy proofs. arXiv preprint arXiv: 1212.26,,,, 2012.
Yucheng Shi, Yahong Han, Qinghua Hu, Yi Yang, and Qi Tian. Query-efficient black-box adversarial attack with customized iteration and sampling. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(2):2226-222 2023. doi: 10. (09/TPAML.20223116999
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the Inception architecture for computer vision. In IEEE Conference Computer Vision and Pattern Recognition, pp. 2818-2826, 2016.
Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A. Alemi. Inception-v4, Inception- and the impact of residual connections on learning. In AAAI Conference on Artificial Intelligence, pp. 4278 4284, 2017.
Michail Tsagris, Christina Beneki, and Hossein Hassani. On the folded normal distribution. Mathe- matics, 2(1):12-28, 2014. ISSN 2227-7390. doi: 10.3390/math211000
Xiaosen Wang, Zeliang Zhang. Kangheng Tong, Dihong Gong, Kun Hc, Zhifeng Li, and Wei Liu. Triangle Attack: query- efficieen decision-basee adversarial attack. In European Conference Computer Vision, pp. 156-174, 2022.
Saining Xie, Ross Girshick, Piotr Dollar, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 1492-1500, 2017.
Yoshihiro Yamada, Masakazu Iwamura, Takuya Akiba, and Koichi Kise. Shakedrop regularization for deep residual learning. IEEE Access, 2960566.
2019. doi: 10.1109/ACCESS.201 20119,
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference, pp. 87.1-87.11 2016. doi: 10.5244/C.30.87.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7472-7482,
2019.
13

---

Published as a conference paper at ICLR 2025
APPENDIX
A PROOF FOR SURROGATE GRADIENT COMPUTATION
For surrogate model J, we define f as the negative C&W loss function as follows.
[x'), maxjøy (xx)). max f(x'); (xx)sa>> if targeted attack,
if untargeted attack,
f(x) =
(18)
where f(x'); denotes the i-th element of the output of f(x'). Note that 1(0,, >) defined in Eq. of the main text equals f (x X
Now we consider g(0), the distance from the benign image to the adversarial region along the ray direction 0, as defined in Eq. ( For any x'. 4 (xx') ) = 1 + f(x') S 0, so we have
( = inf {A:A> 0x +
101 0
(19)
where i-) denotes the infimum of a subset of R. We define g(f) = too when no valid À exists, since inf 0 +o by convention. Now can prove the following proposition.
Proposition A.1. If f is continuous, f(x) > 0, then given any 0 + s.I. g(0) < t00, we have g(0) > and x + s(0) 8 ToT O.
Proof. We first prove that g( > O. We begin by defining the function fo(A) f X 8
Toll
Note that fo is continuous (w.r.. A) because f is continuous. Since fo(0) = f(x) > 0, there
exists 5 > such that AO À < 6, fa(A) > 0. Since g(0) < +00 by the definition we have
g(0) ([) > 0, (o( & 0}) 8 0.
= O. i.e. fo(g(0)) = 0. To simplify notation in the proof, let us denote As- = {A: : 0, (A) $ 0}.
Next, we want to prove ʃ x + g T
If fe()(0)) 0, then since fe is continuous and g0)) 0, there exists > 0 such that fe(g(0)- -c) 0 and g()) - e > 0. Therefore, we have g(0) - E Ag. which implics that g(0) > inf(AA). This contradicts the definition g(0) = ino()
E) <
(g ()) > O, then there exists e > 0 such that (A) > O holds for all g < X S g + This means that [o()), g(0) <] n Ag O. Noting that ( is lower bound of Ag, this implies that g(0) + is also a lower bound of Ag. which contradicts the definition g()) = iAn))
Therefore (0) O.
Next, we show how to calculate Vg(() based on some weak assumptions.
Theorem A.2. Suppose f is continuously differentiable and f(x) > 0. Let h(0 = = ff x [ill) @h ox (fo, Ao) # O. then conclude
For any 0 s.t. g(0n) +oo, let An 9(0)), and assume that
that g is differentiable at 0g and
1
Vg(())= ah (Oo, No) ax
Vgh(Bo. Ao).
(20)
Remark A.3. The assumptions in the theorem are rather weak. f(x) > O (the unperturbed sample can be successfully classified) is standard assumption; g(Op) < +oo is common assumption, necessary for ray search procedure to work; ff is continuously differentiable almost everywhere under common network architectures. The only special condition required here is that ah (0o, Ao) # O, which is DA
generally satisfied unless a specific function f is explicitly constructed to violate it. Intuitively, as X increases, the function value decreases from a positive value non-positive value, and the derivative w.r.t. À is typically non-zero when the function value crosses zero.
AA function is said to be continuously differentiable if all partial derivatives of exist and continuous.
14

---

Published as a conference paper at ICLR 2025
8 is continuously differentiable { A) E R. 0} and f is continuously differentiable everywhere.
Proof. Since (8, + |io]|
continuously differentiable when 0 * by ØX (Oo, Au) + O, by the Implicit Function Theorem (see Theorem 1 in Rio Branco de Oliveira (0112)) there exists a neighborhood θ S R
the chain rule. By Proposition A.1 h(0,, Ao) = O. Since 2h
of dg and an open interval A = (Ao 77, Ao + 77) such that for each E θ, there is a unique À A satisfying h00, A) = 0. Since 0 uniquely determines X, we define g θ A satisfying
M(0 ū(0)) = 0 for all E O. Moreover, the Implicit Function Theorem tells us that ğ is continuously differentiable, and
1
(g(
V Vgh(00 Ag)-
(21)
ah
(0o, Ao) DX
Now it suffices to prove is differentiable at do and Vg((o) = Vg((b). We shall prove that there
exists a neighborhood of 0g in which y and 9 are equal. Since h(0, ((0) 0, from the definition of g. we have g(0) S ō(0) < +oo for all 0 E O. By Proposition
A.1 h(0, (()) = 0, so the uniqueness
Implicit Function Theorem tells us that AO E θ if Ag 7 < ( X + 17. then g(0) = g(0)
Since g(0) - g(0) λ + 7). it suffices prove that g00) > λo 77.
Now we prove that there exists a neighborhood O' Oo such that v0 E O', AA E [0, Ao
10, X) > 0 (this would imply that v0 E ((0) > Ag 77, since (()) = b Proposition A.1 To prove that, we first note that AA E [0, do n]. h(0.. A) > since g(0)) = Ào > X 77 Since h(Oo, A) is continuous w.r.. X, by the Extreme Value Theorem, h(0o. A) on À Ao A0] could attain the minimum (6., A*) which is positive, so there exists > such that E [0. Ag An.nn,,(00. A) 2 c. We pick bounded closed neighborhood of 0,. denoted by O" such that 0 & O" h continuous on the compact set {0,, A) 0 E O", A E [0, Àg - n/},. so by Heine-Cantor Theorem, f is uniformly continuous on the same set. This implies that there exists
couldd
such that for all 0 E O" satisfying
||e - 0ol < 8, we have (h, A) h(6. A) < c and hence h00. > 0 for all À E [0, Ào 7/-
Setting e' O" (0: |00 ful || < 8). we have 40 E O', AA E [0, A- 77. h(0, X) > 0, and thus the proposition at the beginning of this paragraph is proven, i.e., 40 E g') A
Therefore, we have proven that there exists a neighborhood of op. en in which g and 9 are equal. Since the différentiabilityy at On and the gradient only rely on the function value in a neighborhood of to. g differentiable Og and Vg(0,) Vg(Oo). By Eq. (2T). the proof is completed.
B ACQUISITION OF TRANSFER- PRIORS IN TARGETED ATTACKS
adversriial region of original target class
adversarial of original target class thal initial adv image Ry
initial ady image &a
Ainection 0
& dinection
direction R
intersects the region yatr
dieection 0
directionn 6
adversariall region the new largot class Gutte denoted as Rate
Xo
original imsage X
image
non-schersarial region
con-adversurill region
(a) The @ direction in the target model f.
(b) The @ direction in the surrogate model f.
Figure 6: Illustration of setting the new target class Paay and Ao before obtaining priors.
In targeted attacks, obtaining transfer- based priors is more challenging. Fig. 6 iillustrates that dg is initialized as the direction from the original image x to an initial adversarial image Ny. which is selected from the target class Yadv. The o direction used as the initial direction in both the surrogate model and the target model. If both models classify Xo correctly, the lg direction leads to the region of the target class Yadv in both models. During the optimization process, small perturbation AA is added to Oo. resulting in new direction 0. Although the 0 direction may successfully guide the attack towards the adversarial region of the target class Yadv in the target model f. it may not lead to the same region in the surrogate model f. This a result of the varying decision boundaries between the two models, which differ in both shape and extent. Therefore, gj (0) becomes infinitely large in
15

---

Published as a conference paper at ICLR 2025
this case, shown in Fig. 6b To address this issue, set new target class Dady and Ao before computing the cansfer-based priors. The procedure as follows:
(1) Starting at the original image x, we move along the direction in the surrogate model f. The region located distance of X along 0 is defined as the adversarial region Radv with label Vadv where o represents the shortest distance from x along 0 to the adversarial region of the original target class Yadv in the target model f. The shortest distance from x to Raáv along the 0 direction is denoted as λo as shown in Fig. 6b
(2) If adversarial region with the label Undv different from the label y found in the previous steps, we then search for the first adversarial region Radv along the 0 direction in the surrogate model f. within distance range of 0 to 200. The label of Rav is denoted as Vadv. and the shortest distance from Rady along the direction denoted as λo-
C THEORETICAL ANALYSIS OF SIGN-OPT, PRIOR-SIGN-OPT, AND PRIOR-OPT
Lemma C.1. Suppose u ((8-1)) where ((S-1)) denotes the uniform distribution on the unit hypersphere in RR. Suppose is a fixed vector in R with |g = 1. Let B = u g. Then
r
[
(22)
I V
E13a] = d'
(23)
where I is the gamma function.
Proof. Let (O, E Rd then we let u |a Hence / aJg Note that |all and ||a|| are
[|all
independent because the distribution ||a]|
a is always the uniform distribution on the unit hypersphere a and ||a|| also independent, [ la
given any restriction to the value of |||]]. Therefore, and ||||| are independent. Noting that | a|l la gl. we have
E a gll 3 [[[a]]]
(24)
Since a g is affine transformation of the multivariate Gaussian variable a. a gg also has Gaussian distribution with the mean 0 and the variance g Ig = 1, so a g a (0. 1). Therefore, |a gl follows the folded normal distribution (actually its special case: the half-normal distribution), and by the formula in Tsagris et al. (2014).
V2
a gl
(25)
Vx
||a|| follows the chi distribution with d degrees of freedom, so by the formula of its mean
E ||||a|] = V2
(26)
Substituting Eq. 25 and Eq. (66 into Fq.
24 have proved Eq. 22
Since 3 and ||a|| are independent, similarly to Eq. 24
we have
(a 1 B[8
(1.
(27)
Since I), ElaaT] T = I. Hence E[(a gg)
E gg
Tgi
g TEEa
T
aaa
||g/|
and E |||||||]]]] = (raa T] Tr(Elaa [Ea 'I) d. By Eq.
Eq. (3 has been proved.
Lemma C.2. Suppose g is a fixed vector in Rdd with ||gl| = Suppose is another fixed vector in Rd with ||||| and let B, g p. Let be random vector uniformly sampled from the unit
16

---

Published as a conference paper at ICLR 2025
hypersphere in the (d dimensiiol subspace orthogonal to p. Specifically, can be constructed as u
P P.p -p where & ld (1)- Let 31 g then
||| r -(
1
(28)
Proof.
To observe the property of 11, since u is orthogonal to p, we do the following decomposition
forg:
g= P P = 3pp + gL:
(29)
where g1 p denotes the projection of to the (d - dimensional subspace orthogonal
to p. By expanding the inner product, we have
lg 11 = 2/3p + 83 = - -8p
(30)
so 10|gg_l S.. Meanwhile,
(31)
Therefore, 11 is essentially the inner product between random vector uniformly sampled from the unit hypersphere in a (d - didiesssio subspace and a fixed vector with norm /1- 58 in this subspace. Taking the expectation of the absolute values on both sides of Eq. (3I), we have
|[ = [ llg ||E[|l. Tul].
(32)
Since both gi and reside in the (d 1)-dimensional subspace orthogonal to p. it follows that Elgg "ul] corresponds to E B[ in Eq. 22 with replaced by d 1. Therefore,
r(
B g g1
[|]
2
-8
(33)
I
and the proof is completed.
Lemma C.3. Let B be as defined in Lemma that -1 B 1)
C.1
then the probability funcitio of 3 is (note
d-3
32
p(B)
(34)
B
d-1
where B(..)) )) is the beta function.
Proof. We note that when -1 - 5 P(B x)) is equal to the ratio of the surface area of the hyperspherical cap of a hypersphere in TRd to the surface area of the hypersphere. For hyperspherical cap with height on unit hypersphere, its surface area is =Aglzh-n² ( 1)) where Aa is the surface area of the unit hypersphere in IRd and I(.,.) the regularized incomplete beta function. To
compute P( < x) for -1 < x S O, substituting h + and dividing the area by Aa, we have
P(3 < x) 1- d
(35)
where / is the regularized incomplete beta function, defined as (a. _0 10 -
(36)
B(a, b)
Hence the probability density function is
(=(x)= = P(3 < x)
(37)
dr
-2r
(1
x
1-1 -1 2
(1 - x²)) x2))
(38)
2
B
dd1 1
2 2
(V1 x
-r
(39)
|z||
B d-1
(VI x²
(40)
B d-1
17

---

Published as a conference paper at ICLR 2025
Note that the last equality holds because x S 0.
Therefore, we have proven Eq. (34) for I 0. When B > 0, the formula the same due to the symmetry. The proof is completed.
C.I ANALYSIS FOR SIGN-OPT
We can compute the projection of Vg(() onto S with = 0 by summing over all its projection onto the orthonormal basis:
g(0 ou,) - g
(41)
where {ui..... Un} is uniformly random orthonormal set of vectors in RR so ~ (d for any S q. However, in hard-label attacks the coefficients above for each basis vector are costly to estimate. In the Sign-OPT estimator, each coefficient is replaced by its sign which is much easier to obtain using hard-label queries:
Σ sign(g(0 + ou,) g(0)) u,
(42)
In the following analysis, we assume that g is differentiable 0 that have g(0 + g(0) a V + o(or) where lim a(a) = 0 for any unit vector u. We further assume that a is sufficiently small so that a small a is feasible until the numerical error dominates. Therefore, in the following analysis we assume that
omit o(or). In practice, if the target model is deterministic, picking
sign(0(0 + ou) .(0)) sign(V u),
(43)
where u is unit vector in Rd. Now we can write Sign-OPT in the following form:
sign (g( u.) u,
(44)
Now, we present the proof of Theorem 3.2 for the Sign-OPT estimator defined in Eq. 44
Proof. Since {u:}1_ are orthonormal, we have ||v|| e sign Vo( u;))
/q. We note
that sign (0) u.) sign (())) u;),
sign Vg(0) u:) u.
(45)
Hence
v Vg(O)
7
sign Vg(l) u.) (Vg(() u,)
(46)
(g(
u;
(47)
Since (g((f) is a fixed vector w.r.t. the randomness of (u;) and the marginal distribution of u, is U( for any i, by Eq. (22) we have
D(2) VT
r(2)
Eb7
V 1
V
(48)
r
VT
7
Computing Eb>"] is more complicated. First we have
1
(g(
m
(49)
9
g
2 +
1
Vg(O)
u.)
Vg(O)
u,
Vg(0)
(50)
1=1
18

---

Published as a conference paper at ICLR 2025
For the first part, by Eq. 233 we have
Vi, (Vg(() 3 = 1 d'
(51)
For the second part, let us denote 3, == (g( T and Bj = Vg(0) for + j:
uj. Then we need to compute
B| 13,11 E.,, [[[ | uill
(52)
= E., [| [B u:]].
(53)
Next, we aim to compute B|| u.]. Since and u are orthonormal, conditioned on u, the vector ny is uniformly distributed on the unit hypersphere in the (d -)ddiennsional subspace orthogonal
to u, When caleulating the conditional expectation, we consider u, be fixed and use Lemma Specifically, in Lemma C.2
we let g be Vg(0) and let p be u, Then we have
B [
BB
(54)
Substituting Eq. (54) into Eq. 53
we have
E| |3,1]
|3d
83
(55)
T(S)
Here the distribution of 3, is the same as that of 8 in Lemma C.I and we need to compute B[[B| - B3). By Eq. (2 and Eq. (34.. we have
I(
E| = [" p(3))
(56)
4+1 V
2
d-3
[" |8|
82
d3,
(57)
d-1
2 12
so
{ 131 (V1 - B2
d-3
I(2)
dd-1 1
d3
(58)
I(
4-1
2
Hence
[r 131v 1 (3p(3)dB
EE [/311- Bz
(59)
18 (VI- 82 d-2
db
(60)
B
d-1 [(d-1
:2)
d+1
d 1
B
(61)
( d-1
2'2
2 2
π
where the last equality is obtained by setting in Eq.
58
to d 1. Therefore, by Eq. 55 we have
B
I d(d=1) I(
E B|
. 18,11
(62)
B
[( I 442
(63)
TG (
T(
(64)
I d-2
2
(65)
d
19

---

Published as a conference paper at ICLR 2025
Here, the second equality is due to the identity B(a, identity Ia + 1) = al).
[(a)(() F(a+b) and the last equality is due the
Taking the expectation on both sides of Eq. (50) and using Eq. (51) and Eq. 665 we have
1
9 d 14
1)
(66)
2 1)
1
2
1) +
(67)
d
π
The proof is completed.
C.2 ANALYSIS FOR PRIOR-SIGN-OPT
The Ptor-SiinnOPP estimator is defined in Eq. 77. Note that there are priors {PI..... Pa P.) (we assume that they are normalized to have unit norm), and {ui, ug...., ] is uniformly random orthonormal set of 8 vectors in the (d - s)-dimensional subspace orthogonal to (Pi..... Ps). For convenience we first consider the case of and the analysis can easily be generalized the case of 8 >>> 1.
C.2.1 THE CASE OF $
When 1, we rewrite the Prior-Sign-OPT estimator in the following form:
v = sign( Vg(0) p) P
sign Vg(0) Tu) u.,
(68)
where is the prior vector with ||p|| = 1, and (u:)
9-1 is the random orthonormal basis of the ==1
(d diddieensional subspace orthogonal p. Note that the directional derivative approximation is also employed, as in Eq. (3
Theorem C.4. For the Prior-Sign-OPT estimator defined in Eq. (68 we let 7 = V' Vg(0) be its cosine similarity to the true gradient, where the notation v |' is defined to be the lz normalization of the corresponding vector, then
Eb1 =
|al + (q 1 (o--1Vi--o
(69)
T(2
- = a + d-1 T (9 (q- 2) (1- 111--1111--
9-1 ("
r(
(70)
r r())
where = Vf((t) is the cosine similarity between the prior and the true gradient.
Proof. Note that the property of sign function (e.g.. sign (g(()) (())))) sign( Vg(0) u)). Eq. we denote
68
sign (g(()
u; Σ sign Vg(() u,)) u;
(71)
then y sagn(a)p V.. Now
7 (v+) Vg(()
(72)
||v+||
(la) + Vg()))
(73)
The following argument is similar to that in the proof of Lemma C.2 Let g = Vg(0), and let
g g p denote the projection of g the (d d--dinensional subspace orthogonal
20

---

Published as a conference paper at ICLR 2025
to p. It follows that vig = vi Moreover, since {u:}=1 orthogonal p, have V1 = -. sign(g u, u, Since { are uniformly distributed on the unit hypersphere in the (d (d-11)-dmension be considered as the Sign-OPT estimator for g1 as in Eq. (44). with replaced by q and the effective dimension being d 1 rather than d. By Eq. ( we have
subspace orthogonal to and g.1 also resides in this subspace, V1 can
((
g
(( V
(74)
Noting that || vI a² by Eq.
30) and ||vl|| = / - I, we have
E[v]g] = E g = [R[v g g1/lv__ll |1lll
(75)
( 1) a²
(76)
Taking the expectation on both sides of Eq. 73 and substituting Eq. (6) Eq. (69) has been proved.
Next we derive 2 By Eq.
73 we have
(lal + Ig)²
(77)
q
1 (a + (vIg)² 2/a|vIg).
(78)
q
As discussed in the paragraph preceding Eq. 74 Vi be considered the Sign-OPT estimator
for g as in Eq. (44), with replaced by and the effective dimension being d rather than By Eq. 100 we have
2 (1 - 2) +1)
B[(vi
B1
(79)
d
Noting that ||g_|| = v1 a by Eq. 30 and |v 1q I, we have
( (<v]g)>]=B) [ T
g
= E (VI g1 2 |1
(80)
1-1
d- ( 2) +1 (1 (1-
(81)
Taking the expectation on both sides of Eq. (88) and substituting Eq. 76) and Eq. (81) Eq.
770 has
been proved.
C.2.2 THE CASE 1
In the case > we rewrite the Prior-Sign-OPT estimator in the following form:
sign (gg) p.) P:
Σ sign si (g) u.)- u,
(82)
Now, we present the proof of Theorem 3.3 for the Prioo-Sign-OPT estimator defined in Eq.
82
Proof. The following argument is similar to that in the proof of Theorem C.4 Now have
sign Vg(0) Tu.) u, Σ sign (g( u,) u.
u;)
(83)
then v* = Ei sign(a a p, + V1, and
7 (v*) Vg(0)
(84)
|
Σ
|as| + vI Vg(0)
(85)
/
21

---

Published as a conference paper at ICLR 2025
Vg(O). and let g1 g dimensional subspace orthogonal to {p. i== It follows that vlg vigi. Using the similar analysis to that in the case of s = 1, when $ > we have
Let g
Σ i=1 g Pi Ps denote the projection of g to the (d - s)-
(86)
π
Similar to the derivation of Eq.
30
derive that
gi
v v1-
Li- oz. Since ||v ||
vq - 8, we have
E g EBv
B
B
V
||||
(87)
r (())))
(q
8) 1 Σ
(88)
r(
++1 V
Taking the expectation on both sides of Eq. 88 and substituting Eq.
88
Eq.
11
has been proved.
Next derive El By Eq.
(85) have
1 + vig
72
aa
(89)
q
1
losl + (vIg) +
Σ 1=1
lo:1
vIIg
(90)
9
Similar to the case
1, when s > 1 we have
2 (q 5- 1)+
gI d 7
(91)
Noting that ||g_|| = /1 - Ei=1 af and ||v = /q - s. we have
E[[vIg)²]
B[(vI I g __g )²] [[ T (gg )21lv1 11 11 flgll11111
(92)
q 2 (4 1) (1----1)+1) +1)
(1- a
1 (1-
8
(93)
d π
Taking the expectation on both sides of Eq. (90) and substituting Eq.
88 and Eq. (93). Eq.
12 has
been proved.
C.3 ANALYSIS FOR PRIOR-OPT
The Prior-OPT estimator is defined in Eq. 13
Note that there priors {Pi,..., Ps} (we assume that they have been normalized so that they have unit norm), and {N,, u2,..., u is a uniformly random orthonormal set of q q- vectors in the (d - s)-dimensional subspace orthogonal to (pi...., P. For convenience, we first consider the case of 1, and the analysis can easily be generalized the case of 1.
C.3.1 THE CASE OF s =
When 1, we rewrite the Prior-OPT estimator in the following form:
v Vg(() p.p
Vg(0) VI
Tv VI.
(94)
where
11 sign (g(0) T n.) u,
(95)
Here is the prior vector with ||||| = 1. and {u, 1--1 is the random orthonormal basis of the (d - 1)- dimensional subspace orthogonal to p. Note that we employ the directional derivative approximation as in Eq. 44). Furthermore, should also be noted that v defined in Eq. (95) is consistent with that
in Eq. 77p. and thus the conclusions regarding v derived in Appendix C.2. remain valid this section (e.g., Eq. (76).
22

---

Published as a conference paper at ICLR 2025
Theorem C.5. For the Prior-OPT estimator defined in Eq. 1 similarity the true gradient, where the notation |V the corresponding vector, then
y = v V Vg(0)) be its cosine defined be the &g normalization of
1)(1 - a²) (q
[( d=11
Eb1 2
a
2
(96)
TT())
(2 2) + (1 (1-
Eh| -
a
(97)
d
π
1
2 22 2)
(1--))+1 +1 (1-a2) (1)=))+))(--2)
Bly = a²
(98)
d-1
where a = p T Vg( is the cosine similarity between the prior and the true gradient.
Proof. Let g = Vg( Then v =
p.p.ggpppppgg vI). We also note that V1 is a
linear combination of u, ug-1. all of which orthogonal to p. so V1 is also orthogonal to p.
Therefore, ||v*|| = [Vg())]l (p g) + ( T g)a. Hence
7 (v*) ) Vg(0)
(99)
|r
(p g)² + (VI g)²
(100)
(p g)) + (VI g) 2
V (p"g)² (vI g)
(101)
We define new estimator
Vg(()] p p V [g( VI
(102)
= |Vo(0)] (g T p p E gl v
(103)
Let 7 be the cosine similarity between v and (g) Then
(
(104)
(pl g) + V g VT g
(105)
V (p 22 Tg) + E VI g]
Therefore,
(p g 2 + E VI g gg g
BM E
(106)
(p T g) + E[vI gl
a² + F(v1 1 g
(107)
0 E g]
0² + V g)?.
(108)
Since E g] ||~]| B[v] g]. we substitute Eq. 76 and ||v1|| v into this expression.
-
yielding E g] / 1 I σ \+
1(2) Hence,
(r(=1) a² + (q 1)(1 a2)
BM
2
(109)
I(()
23

---

Published as a conference paper at ICLR 2025
The remaining part is to show the relationship between E[y] and E|7] Note that v is the projection of Vg(0) on the 2-dimensional subspace spanned by and V_. By Proposition in Meier et al. (2019), among all the vectors in the subspace spanned by p and VI. v has the largest cosine similantyy with always holds. Therefore, E(y] 2 BR.
Vg( Since v is linear combination of p and vL. which directly proves the lower bound given in Eq. (96
Next, derive E. By Eq. (99) have
Ehd - a² B[(vT'[[)]
(110)
Since ||vi||
/q I, using Eq.
have
BI[ g)
[[(vIg)
(111)
|| 1|
2 (4--2) (1-2)
+1) (1 (1-02). a²).
(112)
d
Plugging Eq. (112) into Eq. (110), we obtain Eq.
(98)
Finally, by applying Jensen's inequality (E(r))² < E h we derive the upper bound for E/y, which
leads to the following result:
a + d (1)-)) 2) +1+1 (1 a2).
1
/E/y2
(113)
This establishes Eq. 97
thereby completing the proof.
C.3.2 THE CASE OF $ >
In the case of > 1, we rewrite the Prior-OPT estimator in the following form:
Vg(0) P. V VI.
(114)
where
V1 = sign (g(0) u.) u,
(115)
Note that Eq. (15) approximates Eq. under the directional derivative approximation. Further- more, it should also be noted that _ defined in Eq. (115) is consistent with that in Eq. (83). and thus
the conclusions regarding V derived Appendix C.2.2 remain valid in this section (e.g.. Eq. (88)
Now, we present the proof of Theorem 3.4 for the Prior-OPT estimator defined in Eq. (11).
Proof. Let (g) Then
"
= [V)(0)) Σ D D
(116)
We also note that is a linear combination of u, to ug all of which are orthogonal to {p:)i_
V. is also orthogonal to {p:) Therefore, ||v*|| [V ().g)" (VI "g). Hence
(v*) (
? |+
(117)
Σ (p. g)2 + (VI T g)).
(118)
24

---

Published as a conference paper at ICLR 2025
We define new estimator
Vg(0) P: P P.+EEVE Vg(()] II
(119)
= Vg(())l
Σ g P: P g VI
(120)
Let 7 be the cosine similarity between V and Vg(O). Then
(v*)
Vg(0)
(121)
v+
(P. g)² + E V g
V g
(122)
Σ i= (P. g)² - E V g)²
Therefore,
Σ i= (P: g) E
g
Bhi E
(123)
i= [P: g)
E
V
gl 2
Σ ii 0f + V
(124)
Ei=1 aj + E V g]
af F T g)
(125)
Since E[
g] = [[v_] E[v g]. we substitute Eq. and ||v q 5 into this expression,
yielding B[v g /
Ei=r
Hence,
(g 8) (1 Ei= of
d= I
2
Σ
2
(126)
d- 2
The remaining part is show the relationship between E [/r] and [E(7]- We note that v is the projection of (g(0) on the (s + 1) -)ddimnnsional subspace spanned by (PI, P2........ P.. VIJ. By Proposition in Meier al. (2019), among all the vectors in the subspace spanned by {P1, {PI.P,..... P2,..., Ps, VIJ.
has the largest cosine similarity with (g( Since also lies this subspace, 7 2 7 always holds. Therefore, E(r) [6)) which directly proves the lower bound given in Eq. (15)
Next, we derive 2. By Eq.
we have
E(-21
Σ
0 + (VT g)
(127)
Since ||v = / 5, using Eq.
93 we have
[ g)
[ [v
(128)
[v
2 8 (1-
1 1 Σ o
+
(129)
d
Plugging Eq. 129 into Eq. 117). we obtain Eq.
17
Finally, by applying Jensen's inequality (E()))² < 2 we derive the upper bound for E[>] which leads to the following result:
Bly < / E
Σ 0f
1
2 -
(1-
Eaf
(130)
d
1=1
This establishes Eq. (6). thereby completing the proof.
25

---

Published as a conference paper at ICLR 2025
D DERIVATION OF THE CONDITION FOR PRIOR-OPT TO OUTPERFORM SIGN-OPT
With the formulas of E[>²] of Sign-OPT (Eq. (00) and Prior-OPT (Eq. (77). we now derive the exact value of a; for which Prior-OPT can outperform Sign-OPT on gradient estimation.
Now, we rewrite the formulas of E[ of Sign-OPT and Prior-OPT as follows:
1
(q (22
E Sign OPT
1) +1+
(131)
d
E Prior OPT Σ
0 d- (1 (1- +1)
2
(
Σ o
(132)
We need to find the value of a; such that "| Priee-OPr > Ely"" ISign-OP..
Let A Ei=1 af, and the inequality becomes:
g 8 - 1))
> d (q - (9-1)+11 1))+
1 1
A+ A)
(133)
d s
8
Now let us simplify the left side of Eq.
133 to E
Prior-OPT
+ (1 - AA)C,, where C2 =
- ( - - 1) 1)+1) 1).
Then, let us simplify the right side of Eq.
133
to E/1²] Sign-OPP
= C₁. where C₁ =
1 1)
The inequality of Eq. 133 becomes:
A A+ (1 A)C2 > Ct.
(134)
rearrange the above inequality as A(1 - C2) + C Ci, and then we solve for A:
C C2
>> > - C2
(135)
Substituting the formulas of A, C1 and C2 into Eq. 135 we have:
1(2 (q 1) +1)
1 (3 s 1) 11)
(136)
(2 1) +1)
This is the condition of Di=1 a for Prior-OPT to outperform Sign-OPT. But this inequality is complex, next we show how further simplify this inequality. Under the reasonable assumptions that 9 & d, which implies that the input dimension is much larger than the total number of vectors (and consequently & d since s < q). the above inequality can be simplified.
We first approximate denominator of Eq. (16),, note that when s < d, we have d - s = d. Therefore, the denominator simplifies to:
2 (q--s- -
1))+1 (1a-s-1)+1)
1 ( (g - s - 1a----1)+1 -1)+ d
D d -
(137)
Since 1 (2 - 5 -1)
11) + 1) is a small number because < d (denote it as e), the denominator becomes D x1 1. Next, simplify the numerator
26

---

Published as a conference paper at ICLR 2025
2
1
2
N
=
q 1) +1)
d - (q - -- 1)+1
(138)
2
11 1) +1
2
19- (9-
(139)
d 77
7
d (1 1) +
1 (2
(9- (1----1)++)
2
(140)
28
(141)
rd
Now, let substitute the simplified N and D into the right side of Eq. (136), have
N
2s
(142)
nd
This is the simplified condition of Ei= af for Prior-OPT to outperform Sign-OPT.
Dividing both sides by s, we get the condition for the average squared cosine similarity a² == -E= a > 2
xd Since 2 is typically very small value due to the large input dimension d, this
ad
threshold relatively easy to satisfy. Therefore, Prior-OPT generally outperforms Sign-OPT when the priors have even minimal level of informativeness (non-zero (x;).
E DISCUSSIONS
E.1 PRIOR ACCURACY 0z
a, = P. Vg(0) the cosine similarity between the i-th surrogate model's gradient (the i-th prior) and the true gradient. The value of a; is only used in the theoretical analysis and is not required for practical algorithm. Algorithm[[] does not require any a, or the true gradient to run. We assume that
o is known in the theoretical analysis so that we can analyze its impact on the expectation of the final estimated gradient's cosine similarity 7 to the true gradient, which derives the solutions of E(>) and E[ Figs. and 13 demonstrate the quantitative analysis for [E[7]] and [B[>"), respectively.
E.2 DIFFERENCES BETWEEN OPT AND PRIOR-OPT
Although the gradient estimation formulas OPT (Cheng et al. 2019) and Prior-OPT (Eq. (13) exhibit some similarities, they differ in two key aspects.
First, the formula Prior-OPT (Eq. 13 is not identical to that of OPT. In Eq. 13) the last term involves the f2 normalization of V.. where t_ = Σn + u1,.... u orthonormal random vectors. Consequently, Prior-OPT employs more precise finite difference estimation for the priors (the first term), while relying on sign-based estimation for the random vector components. This distinction arises because random vectors UI...., uy are identically distributed, leading to relatively consistent cosine similarity with the true gradient. This observation enables efficient sign-based estimation for random vectors. In contrast, the cosine similarities between the prior directions ....... P, and the true gradient Vg( are unknown and may differ significantly. Thus, the coefficients for priors require more precise estimation, necessitating separate binary search procedure. Therefore, Prior-OPT is not merely a simple extension of OPT that incorporates priors, as handles priors and random directions differently to address these challenges.
- g()) u, and
Second, OPT does not require its random directions to be orthogonality, while Prior-OPT explicitly does. Although small number of randomly sampled vectors are approximately orthogonal in the high-dimensional space, this is not always the case for multiple priors. Priors derived from potentially correlated models are less likely to be orthogonal to each other. If the orthonormalization is omitted, the estimated gradient obtained using Eq. 7 and Eq. (13 may become less accurate, potentially degrading performance. Furthermore, the formulas of E[y] and E[72] derived from our theoretical analysis would no longer hold in such scenarios.
27

---

Published as a conference paper at ICLR 2025
E.3 PRACTICALITY OF THEORY
No matter how complex real-world situation is, the generation of adversarial examples mainly relies on gradient vectors that increases the classification loss to cause misclassification. Our theory focuses on the similarity between the estimated gradient and the true gradient, and is applicable to all image classifiers. One of the most common challenges in real-world scenarios is the significant difference between models, leading to discrepancies in their gradients. We address this issue by introducing the variable in Eqs. (II). 12) (5), (6), and (17), where represents the cosine similarity between the i-th prior and the true gradient and is assumed be known in our theoretical analysis. In summary, our theory is universally applicable to real-world scenarios.
F EXPERIMENTAL SETTINGS
In this section, we provide the hyperparameter settings for our approach and the compared methods, which include HSIA, TA, G-TA, GcoDA, Evolutionary, Triangle Attack, SurFree, Sign-OPT, SVM- OPT, SQBA, and BBA.
Experimental Equipment. The experiments of all methods are conducted using PyTorch 1.7.1 framework on NVIDIA V100 and A100 GPUs. NVIDIA A100 GPU has TensorFloat 32 (TF32) tensor cores to improve computation speed, and enabling TF32 tensor cores causes large relative error compared to double precision, especially in attacks on ViTs. Therefore, in all experiments, we set torch. backends cuda matmul a lowt Fa se and wow.h.backeene. cudnn. allow.tf32 False to obtain higher precision.
CIFAR-10 dataset. In the CIFAR-I0 dataset, we select four networks as target models, including 272-l PyramidNet+-SakkeDroo network (PyramidNet-2722) (Han et al. 2017 Yamada et al.
2019), two wide residual networks with 28 and 40 layers (WRN-28 and WR N4)-400 (Zagoruyko & Komodakis 2016), and DenseNet-BC- Be-eeN-et-C-190 (k: 40) (Huang al. 2017). We use ResNeet1110 the surrogate model in the CIFAR-10 10 dataset.
Prior-OPT and Prior-Sign-OPT. Table 3 lists the hyperparameters of Prior-OPT and Prior-Sir Siinn OPT. Our implementation based on the PyToocc framework. In the targeted attack experiments on given target class, we initialize the direction & for both Prior-OPT and Prior-Sign-OPT toward the same reference image from that class, consistent with all baseline methods.
Table 3: The hyperparameters of Prior-OPT and Prior-Sign-OPT.
Dataset
Hyperparameter
Value
g. total number of vectors for estimating gradient, including priors and random vectors
200
the binary search's stopping threshold the number of iterations gmax the maximum gradient norm for the gradient clipping operation
10
500
1,000
0.1
total number of vectors for estimating gradient, including priors and random vectors
200
the binary search's stopping threshold
10
ImageNet
the number of iterations
1,000
gmx, the maximum gradient norm for the gradient clipping operation
1.0
Table 4: The hyperparameters of Sign-OPT and SVM-OPT.
Hyperparameter
Value
the number of queries for estimating an approximate gradient the number of iterations
200
1,000
the binary search's stopping threshold the CIFAR-10 dataset the binary search's 's stopping threshold of the ImageNet dataset
500
x 10
28

---

Published as a conference paper at ICLR 2025
Table 5: The hyperparameters of HSJA, TA and G-TA.
Hyperparameter
Value
".. threshold of the binary search
1.0
Bo, the initial batch size for gradient estimation Bmxx the maximum batch size for gradient estimation the search method for step size
100
10,000
geometric progression
the number iterations
64
radius ratio r for the ImageNet dataset in G-TA radius ratio r for the CIFAR-10 dataset in G-TA
1.1
1.5
Table 6: The hyperparameters of Evolutionary.
Hyperparameter
Value
Coous the hyperparameter of updating the diagonal covariance matrix C the deviation for bias il, critical hyperparameter controlling strength going towards the original image
0.001
0.03
maxien, the maximum length of successful attacks for calculating μ
30
Table The hyperparameters of GeoDA.
Datasct
Hyperparameter
Value
subspace dimension, the dimension of DCT basis's subspace 6, the step size searching the decision boundary
10
CIFAR-10
0.5
subspace dimension, dimension of DCT basis's subspace 6, the step size of searching the decision boundary
ImageNet
Table The hyperparameters of Triangle Attack.
Dataset
Hyperparameter
Value
d. number of picked dimensions
rat i ma mask, the ratio of the mask size for obtaining the low-frequency mask
0.3
CIFAR-10 Guk. the initial angle of the subspace equals Pma x x/32
the initial angle of alpha the maximum iteration number of attack algorithm in 2D subspace
7/2
d, the number of picked dimensions
3
ratio mask, the ratio of the mask size for obtaining the low-frequency mask
0.1
ImageNet Oai. the initial angle the subspace equals Oma x x/32
Osnis the initial angle of alpha
7/2
the maximum iteration number of attack algorithm in 2D subspace
2
Sign-OPT and SVM-OPT. Table lists the hyperparameters of Sign-OPT and SVM-OPT. For fair comparison, we set the hyperparameters Prior-OPT and Prior-Sign-OPT to be the same as those of Sign-OPT and SVM-OPT, e.g., using the same number of vectors for the gradient estimation.
HSJA, TA and G-TA. Taste the hyperparameters HSJA, TA and G-TA. TA has no additional hyperparameters. G-TA has additional hyperparameter, the radius ratio to control the shape of the virtual semi-ellipsoid. Specifically, r set to 1.1 for ImageNet and 1.5 for CIFAR-10.
Evolutionary. We follow the official source code of Evolutionary to set its hyperparameters, as shown in Table
GeoDA. GeoDA only supports untargeted attacks, and the convergence of & &-rmrrm attacks of GeoDA theoretically guaranteed. Thus, we conduct untargeted 2 no-m attack experiments using GeoDA, and the hyperparameters of GeoDA are shown in Table
29

---

Published as a conference paper at ICLR 2025
Table The hyperparameters of SurFree.
Hyperparameter
Value
BS-gaamm,, the stopping threshold in the binary search of
0.01
BS max.iterat on, the maximum itcrations in the binary search for p. the parameter for determining Omax
0.98
2, the parameter for determining the range of a and the best 0 m the parameter for determining the range of a n.ortho, parameter for finding the direction of the lowest e -e..g..canddiatees the binary search's ss stopping threshold of the ImageNet datasct frequence renge, the parameter used in constructing dct
3
30
100
x 10
0 ~ 0.5
teththiisst stance......... atttaneeinneseareeeeeee iiieeseeacce the parameter used _ggt_cannidatee..
False
withhinterpoll at on, the parameter used _gge_.candidatee. with with.alpha alpha linie nine search rrch, the parameter used in get best theta
False
Truc
Table 10: The hyperparameters of SQBA.
Hyperparameter
Value
threshold. d, the stopping threshold in the binary scarch min min-rand the value indirectly determines the number of queries in each gradient estimation
0.001
10
Table 11: The hyperparameters of BBA.
Hyperparameter
Value
use www.suroogatt.be..oo bias, whether to surrogate model the bias use_mask.bias whether to use regional masks as the bias
True
False
use.perlin.bias whether to use Perlin Noise as the bias pg.factor, the hyperparameter that controls the strength of the hias
False
0.3
Triangle Attack. We set the hyperparameter "ratio mask" to 0.1 for ImageNet and 0.3 for CIFAR-10. respectively. hyperparameters of Triangle Attack are shown in Table
SurFree. SurFree only supports the f2-norm attacks. We adapt the official version of SurFree's code to PyTorch for our experiments, and its hyperparameters are detailed in Table
SQBA. SQBA only supports the untargeted f--nrrm attacks, and its hyperparameters are shown in Table 10
BBA. BBA only supports the fz-norm attacks, and the hyperparameters of BBA are shown in Table II] We only use the bias of the surrogate model, and the hyperparameter pg-fact or controls the strength of this bias. When pg-factor 1, the orthogonal step is equivalent to one iteration of the PGD attack. Brunner et al. (2019) suggest that fg-tactor 0.3.
G ADDITIONAL EXPERIMENTAL RESULTS
In this section, we present the results of the computational overhead tests and additional experiments.
G.1 COMPUTATIONAL OVERHEAD
The primary additional computational cost of Prior-OPT over Sign-OPT stems from: (1) the binary search procedure during gradient estimation, and (2) the time required to obtain priors. Let d denote the dimension of the input image, denote the number of vectors used in gradient estimation, f(d) denote the inference time of the target model for input of dimension d, and id) denote the gradient computation time (i.e., the forward and backward pass time) the surrogate model on an input of dimension d. The time complexity of gradient estimation in Sign-OPT is Olg f(d). In
Prior-OPT, priors are introduced. Each prior requires a binary search procedure, which involves approximately & inference steps. While & may vary slightly depending the specific prior the
30

---

Published as a conference paper at ICLR 2025
imput configuration, its value remains bounded and logarithmic in scale, given the nature of binary search. Consequently, the time complexity of Prior-OPT's gradient estimation can be expressed as:
o (
k:) f(d) + A(d)).
(143)
where s [d) denotes the time to obtain priors. (q (q-s)) s)- ((d) indicates the time for computing 1 fdd represents the time of performing the binary search over s priors and Vi in Eq. (1)). When q is large, and k are relatively small (i.e., the number of priors is small, and k typically ranges in the tens), the additional overhead introduced by Prior-OPT is limited compared Sign-OPT. While Prior-OPT introduces extra computation due to the binary search, the increase in time complexity is relatively modest, especially when remains much smaller than This shows that Prior-OPT strikes balance between computational efficiency and gradient estimation quality.
in Eq. (14). and (s+1) -)-k -k
Table 12 demonstrates the time consumption of Sign-OPT, SVM-OPT, Fior-Sign-OPT. and Prior- OPT, measured by performing untargeted attacks on the ImageNet dataset. We use a ResNet-50 surrogate model and an NVIDIA Tesla V100 GPU. The additional time overhead of Prior-Sign-OP mainly the time of obtaining priors on surrogate models. Prior-OPT uses Eq. (33 to estimate the gradient, invoking binary search result additional time consumption compared to Prior-Sign-OPT. Note that for black-box attacks, the primary metrics are the number of queries and the attack success rate rather than runtime. In real-world scenarios, the number of queries is the main limitation, thus we need to use as few queries as possible achieve the highest success rate. Table 13 shows the GPU memory allocations of Sign-OPT, Prior-Sign-OPT, and Prior-OPT. Prior-OPT and Prior-Sign-OPY require the transfer- priors, and thus the additional memory allocation is mainly consumed in the forward and backward pass of the surrogate models. After obtaining a prior, GPU memory is promptly released, thus minimizing additional memory usage of our approach.
times, where is the number of surrogate models. This will
Table 12:
The time consumption of attacking one image with 10,000 queries, which are measured by seconds on NVIDIA Tesla V100 GPU,
Method
ResNet-101
SEN
ResNeXt-101
GC VIT
Swin Transformer
Sign-OPT Cheng et al.
2020
112
197
91
131
88
SVM-OPT Cheng et al. 2020
119
189
102
158
98
Shor-Sign-OPP ReNNee0
240
372
195
203
183
Prior-OPTe.e Rasen
342
476
321
357
203
Table 13: The GPU memory allocations of attacks against different target models, which are measured by Mi B on a NVIDIA Tesla V100 GPU.
Method
ResNet- 101
SENet- 154
ResNeXt-101
GC VIT
Swin Transformer
Sign-OPT Cheng et al. 2020
4,686
6,244
7.272
7,352
8,854
SVM-OPT [Cheng et al. 2020)
4,688
6,246
7,274
7,354
8,856
Prior-Sign-OP RenReee
5,222
6,750
7,828
7,856
9,410
PiiorOPPeeaNare
5,222
6,746
7,816
7,846
9,390
G.2 EXPERIMENTAL RESULTS OF LARGE VISION -SSINNLANGUAGE MODEL
To evaluate the scalability of the proposed approach, we conduct experiments of attacking a CLIP model (Radford et al., 2021) with the ViT-L/14 backbone (Dosovitskiy et al. [02T]. J. and the surrogate models include ImageNet pretrained ResNet-50, ConVil: Cross VIT. Max VIT, and VIT. Here, ViT- L/14 refers to a large variant of the Vision Transformer architecture with the patch size 14 14. is worth noting that these surrogate models are pretrained ImageNet and their training paradigms are entirely different from that of CLIP. The CLIP model, which stands for Contrastive Language- Image Pretraining, is trained on millions of image-tex pairs from the internet using contrastive learning approach, enabling it to generalize effectively through natural language supervision. By aligning images and text in shared embedding space, the CLIP model functions zero-shot image classifier.
31

---

Published as a conference paper at ICLR 2025
We encapsulate it as 1,000-class classifier by constructing set of text prompts that correspond to the class names. These prompts are then embedded into the same space as the images.
In the experiments, due to the differences between CLIP and standard classification models, the tested images used in previous experiments may not be correctly classified by CLIP. Therefore, we select new of 1,000 images that are correctly classified by both CLIP and five surrogate models (ResNet-50, VinV ViTssViT, MaxViT, and ViT) for evaluation. The results are shown in Table [4] which demonstrate that incorporating more surrogate models (priors) significantly enhances attack performance. Notably, despite being pretrained on ImageNet with fundamentally different training methods than those used by CLIP, the surrogate models still improve performance.
Table 14: The experimental results of attacking against CLIP with the backbone of ViT-L/14, and the surrogate models include ImageNet pretrained ResNet-50, VinV CiossViT, MaxViT, and VIT.
Method
Priors
Mcan &g distortion
Attack Success Rate' @5K
@
@2K
69.K
@8K
@0K
@IK
@2K
68K
10K
Sign. OPT (Cheng et al 2020
no prior
58.180
49.435
40,261
37,020
35.713
13.4%
15.2%
17.4%
19.1%
19.4%.
Proor Signn SP HoNces0
I prior
56.915
"3.191"33189
"309977"
295.517
13.3%
25.3%
27.3%%
Shor-Sign-OPeceee Oecevr
prior
55.036
43.327
31.387
27.577
26.250
14.3%
16.3%
24.0%
28.8%
31.5%
Prior Stor-Sign-Oe www---iinn-ntaaaeeee Patt-OPPateassseeeeer
prions
23,954
14.1%
37.4%
Siio-Sign-OPTTe Siga=OPPreNeetteeeeeeiii TcNNccRtCCaeeaaacoll
priors
50.875
36.428
23.410
19,589
18.414
15.3%
20.5%
37.2%
44.1%
46.7%
Pror-Sjgn--PPreeeaeaeeeee hww.eeeaaeeeeeeaaaaaaaaaaaaaaa
priors
49.438
33.941
17.466
16.296
15.7%
23.3%
44.3%
53.2%
57.1%
Sigr-SignOPPTT hht.:o/TTTeeceeeeeeeeeeaoooot
priors
48.214
32.298
19.114
15.790
14.726
15.0%
24.1%
48.0%
56.5%
59.3%
Prior-OPT RecKed
prior
38.934
27.384
20.184
18.520
18.153
23.4%
34.9%
47.3%
50 50.6%
51.4%
Prior-OPT QPaST
prior
31.822
21.261
15.568
14.623
14,362
29.25
43.3%
56.6%
58.8%
98.9%
Prior-OPT ReWT
priors
29.596
18.088
11,770
10,724
10.427
31.3%
1%
68.3%
72.2%
73.4%
Prior-QPT Be
prioes
26.355
15.251
9.953
8.834
8.625
35.0%
55.7%
75.2%
79.1%
79.5%
Prior-PPe aa
priors
26.433
14.261
7.899
6.807
6.562
35.6%
59.5%
82.0%
86.5%
87.3%
Prior-OPT VaNNaaraecaiiaaaaoNTTitttaa
prioos
25.170
13.327
6.745
5,931
5.737
39.2%
63.0%
85.9%
89.4%
89.8%
!
The distortion threshold the attack suceess rate 12.2689852881
11572 which calculated as /0.001 224 x 221 x 3.
G.3 PERFORMANCE OF PRIOR-ONLY GRADIENT ESTIMATORS
The experimental results in previous sections demonstrate that incorporating single transfer-ban based prior enhances performance. To explore this further, it is valuable to investigate an alternative approach where only prior vectors are used, rather than relying on random vectors. We can examine this approach from both theoretical and empirical perspectives.
If all random vectors are eliminated in gradient estimation, the gradient estimator's performance lacks a lower bound, making it unable to guarantee accuracy in the worst-case scenario. However, when random vectors included in the gradient estimation, the accuracy of the estimator is guaranteed to have a lower bound. This means that, regardless of how poor the priors are, the estimator maintains a guaranteed minimum level of performance in the worst case. This can be verified by examining the Ely] derived for Prior-Sign-OPT (Eq. (11) and Prior-OPT (Eq. (15)). Specifically, when all random vectors are removed in Prior-Sign-OPT and q set to s, Eq. reduces
Eli
asl
(144)
In this case, Ely] depends solely ag which reflects the accuracy of the priors. If a; is extremely small, the accuracy the estimated gradient degrades significantly. Similarly, when we remove all random vectors in Prior-OPT and q is set to Eq. [5 reduces to
Ely N
(145)
This demonstrates that, without random vectors, the gradient estimation is entirely reliant on the quality of the priors (i.e., the a, values), and poor priors result in arbitrarily poor performance. Conversely, when random vectors are included, the formula incorporating them guarantees a lower bound for [E[x]- This lower bound can be derived by setting aş 0 in Eqs. (11) and (15). For
32

---

Published as a conference paper at ICLR 2025
Table 15: Mean 22 distortions of targeted attacks on the ImageNet dataset against GC VIT, where Pure- Ture-Prior-SPi Prior-Sign-PPT and Pire-Prior-OPT use only priors in the gradient estimation.
Method
Priors
Targeted Attacks @ 10K
IK
@ @2K
@ 5K
@8K
@ 12K
@ @55K
@ @8K
@20K
Sign-OPT (Cheng et al.
2020 no prior 53.026
42.049
28.210
22.156
19.557
17.661
15.556
14.018
13.194
Pure-Prior- Prior-Sign-OP OPT---PaTee ReaNaso
I prior 52.337
31.255 51.024
51.017
51.017 51.017
51.017
31.01751011
priors 41.468
38.481
37.791
37.787
37.787
37.787
37.787
37.787
37.787
Pure-Prior-O0 Prior--rrToeeeee Peee-OPReeeeee
prior 53.673
53.416
53.385
53.385
53.385
53.385
53.385
53.385
53,385
Cane-Prior-OPI Prioo-OOTTeeaaaaaa NaSAACC
2 priors 41.631
38.687
38.256
38.250
38,250
38.250
38.250
38.250
38.250
Prior-Sign-OPPeeaNiie RoNaso (ours)
prior 52.491
"113333
26,857
20,829
18.427
16.6681
T4.771
13.337
12.333
Prior-Sign-OPTTe Srign-OPReeNeeeee Resve (ours)
priors 51.465
39.537
25.124
19.216
16.841
15.115
13.321
12.030
11.377
OPoee-OP (ours)
prior 50.323
39.615
25.876
20.309
18.120
16,488
14.750
13.535
12,918
Proo-OPPReNaauccoo (ours)
priors
47.739 36.129
23.177
18.528
16.764
15.467
14.121
13.193
12.699
Table 16: Attack success rates of targeted attacks on the ImageNet dataset against GC ViT, where Pure-Priot-Sinn-OPP and Pure-Prior-OPT use only priors in the gradient estimation.
Method
Priors
Targeted Altacks 10K
@1K
@2K
@5K
@8K
12K
@ 15K
@18K
@ 20K
Sign-OPT (Cheng ct al.
2020 no prior 1.0%
1.9%
8.5%
20.3%
30.2%
38.7%
48.8%
57.5%
61.2%
Purc-Prior-Sige Signr--in--PP ReeNertU
prior 2.3%
2.6%
2.7%
2.7%
2.7%
2.7%
2.7%
2.7%
2.7%
Pure-Prior-Sige SeennOPTReNeettukee
priors 8.6%
10.7%
11.6%
11.6%
11.6%
11.6%
11.6%
11.6%
11.6%
Pare-Prior-PPTResee
prior 2.1%
2.3%
2.3%
2.3%
2.3%
2.3%
2.3%
2.3%
2.3%
Purc-Prior-OP1
priors 9.7%
12.5%
12.7%
12.7%
12.7%
12.7%
12.7%
12.7%
12.7%
Prior- Sooo--iinnOPPTaeee (ours)
prior 0.9%
2.6%
12.0%
25.1%
34.4%
41.9%
49 99.6%
58.2%
62.9%
Beo--iignOOOTReeeecccco (ours)
priors 0.9%
3.3%
15.8%
32.2%
40.2%
47.9%
57.1%
62.5%
66.0%
Prior-OPT Neteoeto R (ours)
prior 1.5%
4.6%
14.2%
25.4%
32.8%
40.4%
50.5%
56.8%
60.5%
Prior-OP Prior-OPTResNesttee Resheetucciiv (ours)
priors 2.6%
9.2%
24.7%
36.2%
41.0%
46.8%
53.5%
58.0%
60.7%
Prior-Sign-OPT, the lower bound of E(7] is
r(
F
9
(146)
r r(d- s+1
For Prior-OPT, the lower bound of E/>] is
T( 2
E h
(147)
thereby providing robustness with random vectors when the priors of low quality. Furthermore, in Prior-OPT's gradient estimation, each prior requires a binary search, whereas random vectors do not. Random vectors require only single query per vector, making them more efficient in this regard.
We present experimental results of targeted attacks using variants of the Prior-Sign-OPi OPT and Prior- OPT algorithmss, in which random vectors are excluded from the gradient estimation and only priors (i.e., gradients from surrogate models) are used. These variants are referred to as OPT and PUT The experimental results of attacks against GC ViT (Hatamizadeh et al.) 2023) on the ImageNet dataset are presented in Tables 15 and 16 The results indicate that Pure-Prior- Sign-OPT and Paire-Prior-PPe fail to outperform Sign-OPT when the query budget exceeds 2,000, even though Sign-OPT relies solely on random vectors without incorporating priors. Furthermore, as the query budget increases, the distortions and attack success rates for Peiee--roo-SSin-OPPP and Pure-Prior-OPe remain relatively stable, revealing their inefficient use of additional queries.
G.4 EFFECT OF PGD INITIALIZATION ON THE PERFORMANCE OF SQBA AND BBA METHODS
Previous experiments have demonstrated that applying PGD (Projected Gradient Descent) initializa- tion, denoted as Prior-OPT gro and Prior-Sign-OPTT gx,, significantly enhances the performance of adversarial attacks. This raises the question: How would other baseline methods perform if PGD initialization were applied to them as well? To investigate this, we propose variants of the SQBA (Park al. 2024) and BBA (Brunner al. 2019) methods, labeled as SQBA,ge and BBA, in which PGD initialization is utilized surrogate model to generate the initial adversarial examples.
33

---

Published as a conference paper at ICLR 2025
Table 17: Mean lg distortions of untargeted attacks on the ImageNet dataset against Inception-v4.
Method
Untargeted Attacks @
@ IK
@2K
@:3
6:4K
@66K
67K
@8K
@ 10K
SQBA Park et al_ 2024
26.134
19:035
15,200
12.799
11.189
10.015
9.129
8.432
7.878
7.417
SQBAyain
20.... JuRek (Pakk al 2024
22.698
16.882
13.731
11.699
10.314
9.301
8.543
7,931
7.426
7,017
BBAnntaav Brunner el
2019
38.782
28.437
23.673
20.745
18.757
17.373
16.307
15:474
14.781
14.191
BBA, focRev [Sranner al
2019
26.297
20.370
17.460
15.647
14.404
13.484
12.754
12.177
11.700
11.295
Prior- SannnSiin-OPPTaaeee
81,991
42.403
25.355
17.163
12.835
10.191
8.508
7.365
6.508
5.842
Prior Sign-OPTTaa
20... Ladevv
23.596
15.347
11.565
9.458
8.074
7.085
6,330
5.729
5.249
4.863
Prior PriorOPTTaaee OPTineeent
49.279
1K.135
9:226
6,798
5.718
5.148
4.747
4,451
4,215
4.027
Prior-OPT
0 inetleeV
22.852
12.194
8,896
7.452
6.568
5.947
5.485
5.114
4.809
4.548
Table 18: Mean lz distortions of untargeted attacks the ImageNet dataset against VIT.
Method
Untargeted Attacks 666K
@ 1K
@2K
633K
@4KK
655K
6K7K
68K
#9K
@ 10K
SQBAcavar Park ct
2024
12.886
9.762
8.045
6.972
6,240
5.702
5,278
4.947
4.681
4.452
SQBA Park
2024
10.794
8.424
7.094
6.227
5.647
5.204
4,856
4.572
HR (Brunner
2019
133309
11.3%6
"K395"
BBA g DwesT Briinner ee
2019
11.163
9.431
8.535
7.958
7,534
7.227
6.982
6.783 6.615
6.477
Prior Phoor-SinnOOP Sign-OPToowtt
46.883
24:351
14,592
10,329
8.057
6.669
5.755
55142 4,688
4,313"
Prior- Sign-OPT N...... GinWi
9,011
6.935
5.752
5.025
4.504
4.108
3,803
3.549
3.345
3.17
Prior-OPT OPTeaST TowNT
26.649
11,706
7.632
6.025
3.228
4.728
4,380
4.117
3.909
3.754
Prior-OPT COVV
8.688
6.646
5.595
4.962
4.551
4.245
4.003
3.808
3.640
3.511
Table 19: Mcan & distortions of untargeted attacks on the ImageNet dataset against GC VIT.
Method
Untargeted @5K
Attacks @6K
@
IK
@ 2K
@ @3K
@4K
@7K
@8K
@9K
@ 10K
SQBAcaaii Paak et al.
2024
19.307
14.049
11.170
9.327
8.072
7.135
6.434
5.877
5,426
5.056
SQBA
Park
2024
15.652
11,520
9.197
7.752
6.754
6.033
5.479
5.034
4.673
4.370
"BBKGwW
[Brunner
2019
24:922
21:095
17:061
14:680"
T3.103
IT354
TT320
TO::00
BBA.
(uiVi7 (Brumer a. 2019
15.959
12.688
11.054
9.997
9.230
8.627
8.164
7.766
7.430
7,131
Prior VMior-Sign-OPT.oo
35,864
34,707
22.793
16.584
12.893
10.346
8.895
7.678
6.712
5,972
Sign OPT.ge
8.642
7,209
6.250
5,551
5.009
4.560
4.205
3.166
"99497
12.320
9.275
7:41
6.339
5.828
3.251
"X17""4351"
Prior-OPT, 100 ccaVTT
16.949
10.708
8.251
6.937
6.031
5.391
4.913
4,530
4.219
3.961
Table 20: Mean lg distortions of untargeted attacks on the ImageNet dataset against ResNet-101.
Method
Untargeted Attacks
@2K
@4K
655K
@6K
#7K
SQBAuesesi (Park
2024
8,873
7.229
6.172
5.449
4.934 4,531
4.215
3,957
3.745
3.563
SQBA,ta Reckere
Park ef al.
2024
6.882
5.675
4,894
4.364
3.985
3.689
3.456
3.264
3.101
2.961
BBA Brunner et al 2019
Y4335
11.764
9'444
9:44
"W70
BBA,,
BBrunner et
2019
6,281
5.488
5.051
4.779
4.577
4.425
4.302
4.196
4.109
4.029
Prior-Sign-OPT.e RanNart
34.150
18.733
11.452
7.977
6.111
4,922
4.247
3.718
3.323
3.019
Prior-Sign-OL Sinor-SinnOPP,.tr. .0g a Roodeet
5.423
4.303
3.632
3.182
2,859
2.615
2.414
2.267
2.142
2.045
OPior-OPTeeaee
18:353
"1100"
4.190
3:214
840
2.112
2,400
2.324
2:23
2.588"
Prior-OPT,
4.932
3.807
3.273
2.940
2.710
2.532
2.390
2.275
2.181
2.107
Table 21: Mean & distortions of untargeted attacks on the ImageNet dataset against SENet-
Method
Untargeted @5K
Attacks @6K
@IK
@2K
@
@4K
@7K
@8K
@9K
@00K
SQBAp (Par
2024
16.332
11.802
9.335
7.788
6.765
6.016
5,445
4.994
4.630
4.332
SQBA, got RuaNerto
Park ct al 2024
13.342
9,871
7.944
6.707
5.863
5.246
4.779
4,410
4.115
3.860
BBAauNee0 [Bunner ei 2019
24.402
17.863
14.923
13.134
11.915
11.009
10.330
9,796
9.348
8.976
BBA.m RoNNa50 [Stunnee
2019
13.074
10.435
9.080
8.221
7.626
7.187
6.843
6.559
6.112
Prior Prior-Sign-0 Silu--SinnOOPT.... koNNat
45.340
26.404
17:200
12:317
9,412
77.51
6.285
5,000
4.740
4.223
Prior-Sign Siin--ignPPP S0T pen Resaaro
12.375
8.859
6.900
5.684
4.865
4.272
3.817
3.461
3.184
2.958
"Fior: 3PTs5000
29.378
14:333
K355
W377
33342
4432
4,316
3347
3.630
"3300""""""""
Prior-OPT Mann-OPPyyt-_aaaa
60 RaNado
11.952
8.431
6.580
5.542
4.863
4.368
3,980
3,680
3,420
3.215
34

---

Published as a conference paper at ICLR 2025
Table 22: Success rates of untargeted attacks on ImageNet against Inception-v4,
Mothod
Untargeted Attacks @
@ 1K
@2K
0:3
6:4K
GR6K
697K
@
69K
@ 10K
RQBA Park et al_ 2024
41.95
55.8%
65. .%
74.7%
79.2%
85, 85.6%
87.7%
89.9%
91.4%
93.0%
SQBAyai
20.... JuRo (Pakk al 2024
51.5%
63.7%
71.3%
79.4%
82.
87.4%
90.2%
91.2%
92.6%
93.3%
BBAnnttav
Brunner el
2019
16.3%
29.0%
39.0%
46.9%
54.3%
57.5%
60.6%
63.9%
66.6%
68.8%
BBA focRev
[Sranner al.
2019
43.9%
53.4%
60.1%
65.6%
69.0%
71.7%
74.8%
77.0%
78.8%
79.6%
Prior- SanooSiin-OPPTaaeee
3.8%
16.6%
38.9%
60.4%
75.7%
85
89.4%
11.8%
94.2%
96.3%
Prior Sign-OPTTam
2.... LadeeV
62.6%
72.2%
77.8%
84.4%
88. 3%
90.7%
93.4%
94.5%
95.8%
96.9%
Prior PriorOPTTaata OPTinatent
17,8%
63.4%
86.%%
94.2%
96.4%
97,4
98.4%
98.8%
99.0%
99.1%%
Prior-OPT
64.7%
84.1
89.2%
92. 5%
95.1 1%
97.6%
98.19
Table 23: Success rates of untargeted attacks ImageNet against VIT.
Method
Untargeted
Attacks @66
@ 1K
622K
04KK
6R5KK
@ 07K
6KK
69K
@ 10K
SQBAc (Park et nl.
2024
55. 9%
71.7%
81.1%
88.4%
91.9%
94.4%
96.7%
97.4%
97.8%
98.3%
,QBA,KD
(Park
2024
67.1%
80.7%
87.8%
91.6%
94.6%
96.2%
96.9%
97.6%
98.2%
98.3%
BWA
(Brunner 2
"3300%"""
75.22%""""
""""""""""""""""""
""""""""""""""""""""""""""""""""
BBA Coavir (Brunner et al.
2019
69.9%
76.4%
80.3%
84. 8%
86.5%
87.5%
89.1%
89.5%
90.6%
91.3%
Sioo--Sin-OPPP...
8.44%"
23.8%
49.2%%
71.44
83.6%
90.4%
94.0%
96.0%
97.1%
98.1%
Prior- Prior-Sign-Or Sign-OPT.ger.
83.8%
89.7%
93.6%
95.2%
96.4%
97.5%
97.9%
98.3%
98.7%
99.2%
Prior- OPTeavvr
26.2%
65.7%
83.6%
91.3%
94.7%
96.2%
97.1%
97.7%
98.9%
99.2%
Prior-OPT, go COUNT
83.6%
89.7%
93.4%
94.9%
96.3%
97.3%
97.9%
98.1%
98.6%
98.9%
Table 24: Success rates of untargeted attacks on ImageNet against GC ViT.
Method
Untargeted @-5K
Attacks @6K
@ IK
@2K
@ 3K
@4K
@7K
@8K
@9K
@ 10K
SQBAcuNT (Par et 2024
38.1%
53.3%
64.4%
73.8%
79.6%
84.7%
87.7%
90.9%
93.1%
94.4%
SQBA,
See Gotvr Park 2024
50.2%
65.5%
74.6%
81.9%
86.8%
89.7%
92.1%
94.1%
95.4%
96.2%
BBBAcoo
(Bunner
10.7%
42.49%
"62.9%
"1.3%"
"7200%%%
BBAgr
Cushi BBunner et
2019
51.7%
60.3%
66.0%
69.4%
74.2%
78.1%
79.7%
82.7%
85.1%
86.5%
Sigu-Sign-PPPee
1.7%
9.2%
27.3%
48.2%
62.7%
72.0%
78.7%
82.7%
86.3%
89.0%
Prior Sign OPT CoMM
63.4%
73.6%
81.1%
85.4%
89.4%
91.2%
92.8%
94.3%
95.4%
96.4%
"Pror OPTeawr
87.9%
"''4""""""""""""""""""""""""""""
933.3%
"95.7%"""""""""
Prior-OPT ggD -reNNT
63.2%
74.1% 1
81.4%
86.4%
89.9%
92.0%
93.5%
94.4%
95.7%
96.7%
Table 25: Success rates of untargeted attacks on ImageNet against ResNet-
Method
Untargeted Attacks 0K
6:2K
3K
@6K
10K
SQBAuasaoo Park al. 2024
78.7%
85.3%
89.6%
92.6%
94.6%
96.2%
97.0%
98.1% 11)
98.3%
98.9%
SQBA Roderto
Park et nl.
2024
88.5%
93.2%
95.2%
96.0%
97.1
97.5%
98.1 1%
98.7%
98.9%
99.3%
BB
de (Brunner ni. 2019
come
47.8%%
62.3%
70.2%
75.2%%
7994%
84.8%
85.7%%
BBA
Brunner atal.
2019
89.8%
92.2%
93.9%
95.1%
95.9%
96.0%
96.4%
96.8%
97.1%
97.1%
Mhor-Sinn-PPTuoeeee
10.9%
35.4%
65.0%
83.0%
91.1%
94.0%
95.9%
97.3%
98.6%
99.4%
Prior- Sign-SignOPPT.rrt
S.... ReeNeet)
94.5%
96.1%
97.2%
97.9 9%
98.2%
98.7%
99 0%
99.3%
99.4%
99.78
Prio=-PTTRss Ruske50
42.0%
87.4%%
96.2%%
98.3%
99.2%
99.3%
99.7%
99.7%
99.8%
10000%
Prior-OPT g0 RooNedo
94.6%
95.9%
96.9%
97.8%
98.3%
98.7%
98.7%
99.0%
99.2%
99.5%
Table 26: Success rates of untargeted attacks on ImageNet against SENet-
Method
Untargeted Attacks @5K
@
@2K
@3K
@44K
@6K
@7K
@8K
@9K
@ 10K
SQBApaaato Park et
2024
45.1%
61.5%
72.9%
81.7%
85.7%
89.0%
91.7%
94.6%
96.4%
97.9%
SQBAgee Agp Rudieto Park ci al 2024
59.1%
72.3%
81.1%
86.7%
90.2%
92. 92.4%
94.4%
96.5%
97.5%
98.4%
BBAR [Bruncer et al 2019
16.6%
33.9%
45.6%
54.9%
61.2%
66.3%
69.7%
72.7%
74.2%
76.9%
BBA.D ReaNed0 Brunner
2019
60.8%
69.7%
75.4%
79.9%
83.2%
85.6%
87.0%
88.6%
89.9%
90.6%
Prior Sign
3.7%
16.2%
36.6%
58.3%
75.2%
83.1%%
88.3%
92.1%
95.0%
96.7%
Prior-Sign OPT KoNheo
71.9%
79.6%
87.25
91.3%
94.2%
96.3%
97.2%
97.6%
97.9%
98.3%
PHar:PPT
16.3%
55.9%
77:5%"
97.0%%
97.6%%
Prior-OPT,em.
6mhh RaNalo
72.5%
81.3%
88.5%
91.6%
94.3%
96.2%
97.1 %%
97.5%
98.0%
98.6%
35

---

Published as a conference paper at ICLR 2025
The mean lg distortions of the experimental results the ImageNet dataset presented in Tables 17
18
19
20
and 21 while the corresponding attack success rates are shown Tables 22
23 24
25
and 26 The distortion threshold for attack success rates is 16.3769 for attacks Inception-V v0.001 x d, where d is the dimension of the input image. As shown in these tables, the PGD initialization improves the performance of both SQBA and BBA, resulting in reduced mean & distortions and higher attack success rates. Furthermore, our approach with PGD initialization outperforms both SQBA and BBA.
and 2689 for attacks other networks, caleulated
G.5 COMPARISON WITH STATE-OF OF-THE-ARE METHODS
Table 27: Untargeted attack results of ViTs on the ImageNet dataset, where "Mean lg" denotes the
average & distortion of the final adversarial examples, "AUC" denotes the area under the curve of mean & distortions versus the number of queries (lower is better), and "ASR" denotes the attack success rate of the final adversarial examples.
GC
Swin Transformer
Mcthod
Moan E
AUCC
ASR
Mean d
AUC
ASR
Mean 02
AUC
ASR
HSIA (Chen
5.637
102956.7
163915.1
228806.0
70.3%
TA eM B
5.674
104023.3 3
96.6%
9.102
176063.88
76.7%
10.513
230351.0
68.4%:
G-TX
202th
5.643
102013.4
96.4%
8.671
170511.6
77.6%
9.929
219877.9
72.6%
GeoDA Rahmall et al
2020
6.313
83176.7
91.0%
12,998
172173.2
54.3%
19.120
245094.6
31.5%.
Evolutional
2019
6.719
128659.9
89.8%
8.615
174592.0
79.1%
15.738
266695.9
52.6%
SurFree
Maho C A034)
6,303
104053.9 9
91.6%
10.967
19340006
65.4%
13:059
200688 5
58.3%
Triangle
Aiaae Wais
2023
10.097
99746.4
69. 69.0%
30.119
298578.9
21.2%
29.005
288358.2 2
23.1%
BBAx.aae
9.567
125221.1
11,294
67.5%
185551.7
99.9%
BBAGwN
Brumner < m
2019
8.595
105826.6
79. 3%
9.188
128468.5
77.6%
12:375
156081.9 9
59. 55%
SQBApwlars
5.201
79423.0
95.7%
6,186
100435.8
89.2%
7.587
115845.7
83.2%
SQBAcaww
Park al.
A126
4.452
602995.8
98.3%
5,056
79670.8
94.4%
5.883
82141.3
91.0%%
Sign OPT Neny
2020
4.572
111439.9
98.3%
7,188
166001.9
85.9%
9.899
238907.0
74.7%
SVM.OPT heng
5,070
171869.8
249491.3
72.1
Prior-Sign-OPe TaoNlco0
4,850
119961.
97,
1%
234462.4
75.7%
Prior Sign- OPTo-PP
4.313
105379.9
98.1%
5,972
151725.9
89.0%
7.622
198431.3
84.2%:
Prior-Sign-OO Sign--innTPaaa OPT..NesMeCCNN
3.967
99940.6
98.6%
5,286
137011.9
92.9%
6.331
177589.1
89.2%
Prior-Sign-OPT, .r.. Resbier
4.331
88120.1
91.7%
5,243
98749.0
92.6%
8.112
128167.1
80.3%
5.195
106791.0
134255.9
190534.1
73.0%
Prior-PPeewNr OTTNT
3.754
62928.
99.2%
4,453
92662.3
95.7%
5.558
102428.7 7
91 8%
Prior-OPT: Pww.PPPaaneneccartt
3,609
60449.00
99.2%
3,700
76896.1
98.3%
4.896
91211.7
94.5%
Prior OPT guo
5,009
900005.1
96.4%
5,502
98555.8
92.8%
8.552
128766.0
76.4%
Table 28: Untargeted attack results of CNNs on the ImageNet dataset, where "Mean 6²" denotes the average & distortion of the final adversarial examples, "AUC" denotes the area under the curve of mean & distortions versus the number of queries (lower is better), and "ASR" denotes the attack success rate of the final adversarial examples.
ResNer--10 AUC
ResNeXt- 4d)
SENet- 154
Method
Mean E
ASR
Meun fg
AUC
ASR
Mean 2g
AUC
ASR
HSIA CChen
5.158
96234.2
5.484
9.385
177364.9
74.9%
TA (Maer 20410
5.239
96858.5
95.9%
5.565
110870.1 1
95. 05.0%
9,379
172600.0
73.8%
G-TX
202.
5.225
95901.
96.3%
5.524
109990.5
$.430
119281.1
92.9%
GeoDA [Khmall è ill 2020
6.364
82320.0
91.9%
5.898
88947.7
89.3%.
8.209
107267.4 4
80.95
Evelutionary Dong di
2u19
5.406
107841.6 6
93.2%
6.042
123706.5
91.3%
6.111
130032.0
90.15%
SurFree Maho G A
6.627
104285 4
88.1%
7,550
123394.0
83.7%
8.247
131295-4
79.5%
Triangle Xllack (Wing F1 2022
12.123
117731.5
61.3%
11.883
I 116639.5
63.7%
15.019
145508.7 7
48.9%
BBAxaaii Brunner
2019
7,295
86.9%
76.9%
SQBAnaNa Park 1 2074]
3.563
46450.8
98.9%
4,058
59316.7
97, 8%
4,332
67106.3
97.9%
Sign-OPT C hein
4.754
101907.7
5.108
120545.5
95.
124730.2
93.5%
SVM-OPT
bosg dl 2020
4.842
105778.8
95.8%
5.255
126799.4 4
95.0%
5.125
127568.9
93.7%
Prior-Sign- Taxdeoto
3.019
79126..4
3,518
100999.4 4
114089.3
Prior Sign- OPT Reslleco
2.045
27148.4
99.7%
2.450
35290.7
99.4%)
2,958
48708.7
98.3%
Prior-OPTawaach
2.158
37218.3
100.0%
2.692
53085.7
99.7%
3.394
68609.
98.9%
Prior OPion-OPT.pm
2.107
25627.6
99.5%
2.486
33291,5
99.7%
3.215
48444..6
98.6%
Tables 27 28 and 29 show the experimental results of untargeted attacks against ViTs and CNNs on the ImageNet dataset, where "AUC" indicates area under the curve of the mean & distortions versus the number of queries, "Mean 82" denotes the average ε2 distortion of the final adversarial examples, and "ASR" indicates the attack success rate of the final adversarial examples. Here, the final adversarial examples are generated with the query budget of 10,000. The ASR is defined the percentage of samples with distortions below threshold e, which is set v0.001 d in the
36

---

Published as a conference paper at ICLR 2025
Table 29: Untargeted attack results of Inception networks on the ImageNet dataset, where "Mean &g" denotes the average & distortion of the final adversarial examples, "AUC" denotes the area under the curve of mean & distortions versus the number of queries (lower better), and "ASR" denotes the attack success rate of the final adversarial examples.
Inception- V3 AUC
Inception- AUC
Method
Mean &
ASR
Mean
ASR
HSJA (Chen et al
2020
12.014
211938.7
81.1%
11.645
227700.5
82.1%
TA (Ma 202
12.378
208706.8
79.8%
11,694
219707.3
82.0%
G-TA (Ma al. b021b
12.076
205670.7
81.5%
11.448
216797.7
83.3%
GeoDA (Kahmali
2020
9.437
124150.7
87.8%
9.688
128665.4
87.7%
Evolutionary (Dnn al.
9.809
192654.1
86.4%
10.839
215405.4
81.6%
Surfiree (Maho 20
11.648
186094.3
79.1%
13.818
221197.5
69.7%
Triangle Attack (Wang a1.
2022
20.878
205534.2
46.5%
22.132
214723.3
42.5%
BBAuuRSV2 Brunner el a..
2019
13,952
169881.3
69.0%
14.191
182033.7
68.8%
BB Axcepioo Brunner e1 a1.
2019
14.657
185798.3
67.2%
15.282
199287.2
63.6%
SQBAneesss (Park ct al.
2024
7,020
98767.0
94.3%
7.417
110451.
93.0%
SxBaxna
Park cl al.
2022
6,933
97022.6
94,7%
7.115
102939.0
92.2%
Sign-OPT Cheng cf al.
2020
8.134
195118.7
91.9%
8.786
217576.3
89.8%
SVM-OPT (Cheng ct
20200
7,995
193289.7
92.3%
8.839
219673.6
89.0%
Prior-Sign-Oi TickeeV2
5.314
156261.6
97.8%
5.842
I 174243,9
96.3%
Ertor-SignOPPTseee Txeetionn
5.831
163715.5
96.8%
5,958
176950.5
95.7%
Prior-Sign-OP1 Siign-OPTo.Reeeeeee. Vo.eeiV22Xooo
4.225
130427.5
98.6%
4.199
142032.3
99.0%
Prior-Sign-OPTTer % InckeeV2
4.713
75088.7
97.1%
4.863
83066.8
96.9%
Prior-OPT: Instaw
4.067
79685,9
99.3%
4,027
85290.8
99.1%
Prior-OPT Xxeption
4.539
88915.0
99.3%
4,261
90492.0
99.3%
Prior-OPT, IncptitVXooottion
3.387
64461.8
99.7%
3.167
66110.1
99.8%
Prior-OPP gg luReeV2
4.496
65031.0
98.4%
4,548
20165.3
98.1 9%
ImageNet dataset and 1.0 in the CIFAR-10 dataset, where d is the image dimension. Tables 27 28 and 29 show that the Prior-OPT with two surrogate models performs the best in most cases, and the PGD initialization of 0 (e.g., Prior-OPT,pe 6p ResNeso)) can effectively reduce the AUC.
Table 30 demonstrates that Prior-OPP and Prior-Sign- Soor-Sinn-PPP OPT deliver competitive performance in foo- norm attacks on ImageNet, surpassing Sign-OPT in average too distortions, further validating our approach's is effectiveness across attack types.
Fig. shows the experimental results untargeted f2-norm attacks on the ImageNet dataset. The results demonstrate that Prior-OPT significantly outperforms all compared methods, including SQBA and BBA that also use surrogate models. The results also show that using multiple surrogate models further boost performance. In addition, the PGD initialization ensures the algorithm's 's initial attack direction 6g is already good, which enables it to achieve better untargeted attack performance even with small number of queries (e.g., the query budget of 1,000). Fig. 8 shows that on ImageNet, Prior-Sign-OPT outperforms Prior-OPT in targeted f2-norm attacks on CNN models, especially when single one.
using multiple surrogate models compared
Figs. 9 and 10 show the attack success rates of untargeted and targeted attacks on the ImageNet dataset. In untargeted fn-morm attacks (Fig. 9) Prior-OPT with two surrogate models achieves the highest success rate, and both Prior-OPT and Sigi--Si outperform the baseline Sign-OPT. For targeted attacks (Fig. [OP. Prior-Sign- -ign-Oinn-PP OP exhibits superior performance compared to Prior-OPT. One plausible explanation is that Prior-Sign-OP employs a more query- query-efficient strategy by leveraging the sign directional derivatives, which requires only single query per direction. When o; is small, Prior-OPT, which relies on binary search to fully exploit prior information, becomes less efficient due to its high query cost. Consequently. Prior- Prior-Sign-OPe Sign-OPT holds a relative advantage in such scenarios.
Figs. and and present the experimental results the CIFAR-10 10 dataset. The results demonstrate achieve the highest performance among all evaluated methods. In future work, we aim further improve the performance of our approach the CIFAR- -00 dataset.
that SQBA and Prior-Sign-On
13b and 13c present the ablation studies of E[ based on our theoretical results, Figs. 13a
with Eq. 10 for OPgn-OPT, Eq. (12 for Phior-Sign-OPP and Eq. (7) for Prior-OPT. Fig. 13d demonstrates the performance Prior-Sign-OP in untargeted & norm attacks against the Swin Transformer the ImageNet dataset, evaluated with different values of
37

---

Published as a conference paper at ICLR 2025
Table 30: Mean &o distortions of untargeted attacks across various query budgets on ImageNet.
Target Model
Method
Mcan @2K
to distortions @8K
@ IK
@5K
@ 10K
TA iMa et al. 102
0.399
0.379 0.359 0.348
0.342
Sign-OPT Cheng al. 2020
0.726 0.403 0.156 0.100
0.084
SVM-OPT (Ceng el al 2020
0.723 0.389 0.155
0.102
0.088
Inception-v3
Prior Sinn--iinn--ieeee IndRa
0.365
0.016
0.086
0.080
Prior- Proo-Sign-OPPnaeee OPTaneestAxooppii
0.640 0.318 0,102 0.083
0,080
Prior-OPT nn22
0.581 0.267 0.138
0.115
0.109
Prior-OPThnn Prior-OPhnaaaaaeee Vaceooa
0,502 0.208 0.119
0.111
0.109
TA MMa et al. 202
0.420 0.402 0.381
0.370
0.365
Sign-OPT Cheng al. 2020
0.794 0,450 0.175 0.111 0.093
SVM-OPT (Chnng el al. 2020
0.811 0,446 0.178 0.113 0.096
Inception-vd
Prior Siier-Sinn-----ie indRaW
0.756 0.408 0.13660.097 00089
Prior-Sign-Oe OPTnneeeVAxooooi
0,700 0.348 0.107 0.086 0.082
Prior-OPT Prir-OPPhneRaa2
0.645 0.302 0,757 0.131
0.123
Prior-OPT Tocessaaxaaaoo
0,558 0.218 0.117
0.108
0.106
TA Ma et al. 202
0.301 0.285 0.267
0.258
0.253
Sign-OPT (C Chnng al. 2020
0.437 0.247 0.101
0.066
0.057
ResNet-101
SVM-OPT (Chngg et 2020
0.461 0.254 1.1 0.075
0.066
Prior Sign-OPTReeMaan ResNatoo
0.404
0.218 0.074
0.053
0.049
Phior-OPTResvee
0.289 0.138 0.075
0.064
0.060
TA MM et al. 2021b
0.362 0.344 0.323
0.313
0.307
Sign-OPT Cheng al. 2020
0.611
0.326 0.131 0.090
0.078
ResNeXt-101 (64 4d) SVM-OPT (Chnn al. 2020
0.667 0.336 0.131 0.089
0.078
Prior-Sign-OPTe OPT
0.574
0.303 0.104 0.075
0.069
Prior-OPT ResNedo
0.428 0.196 0.097 0.080
0.075
TA iMa et 202
0.355 0.336 0.316 0,306 0,300
Sign-OPT Chong 2020
0.563 0.326 0.132 0.082 0.067
SENet-154
SVM-OPT Cheng 2020
0.570
0.325 0.132 0.082 0.068
Prior-Sign- SiggnOOPTeee ResNesd
0.536
0.314 0.113 0.074 0.065
Prior-OTT RosN
0.448 0.246 0.129 0.102
0.094
TA MMa et al. 2021b
0.399 0.379 0.358
0,348
0.342
Sign-OPTTChhe Cheng et 2020
0.602 0,302 0.105 0.072
0.064
SVM-OPT Cheng et al 2020
0.651 0,310 0.107 0,075
0.068
VIT
Prior-Sign-Oe Sooe-Sinn-OPr
Sign-OPTeen ResNe150
OPTReNNtti
0.597 0.334 0.118 0.084
0.077
Prior-Sign- Dhoo--Sin-OPPReeeeeee NaTCCNII
0.539 0.273 0.090 0.069
0.065
PPixe-OPTeeeedo ResNedo
0.591 0,352 0.178 0.136
0.123
Prior-OPT Non
0.429 0.217 0.124
0.110
0.106
TA MM et al.
202
0,380 0,365 0.348
0,339
0.335
Sign-OPTi Cheng et 2020
0.680 0.434 0.186 0.119 0.098
SVM-OPT (Chnng et al
2020
0.678
0.427 0.183 0,116 0.097
GC VIT
Prior-Sign www.--inn--PPPre Sann-OPTRrnaa TReNNe50
0.670 0.445 0.13 0.116 '0.097"
Prior-Sign-OO Proo-Sign-OPPaaaaee OPTRENPAAAACCTTT
0.642 0,389 0.141
0.092 0.079
Prior-OPT RedNedo
0.652 0.455 0.248
0.185
0.163
Prior-OPTReaussee Ron
0.538 0.305 0.160
0.131
0.122
TA Ma al. 202
0.536 0,515 0.491
0.479
0.472
Sign-OPTT Cheng et al.
2020
1.009 0.625 0.258 0.159
0.128
SVM-OPT (Cenng al 2020
1.036
0.622 0.251 0.157
0.131
Swin Transformer
Vrior-Sign-OPe OP ReoNa50
1.000 0.647 0.262 0.162
0.113"
Prior-Sign-OPTaaee TeM
0.909 0,513 0.169 0.105 0.088
Prior-OPT KesNedo
0.942 0.619 0.309 0.226 0.198
Prior-OPTRe.ke RaNuAM
0.662 0.321 0.159 0.129 0.120
Figs. 14 16 and 18 show examples of adversarial images generated using different numbers of
queries in targeted attacks with Sign-OPT, Prior-Sign-OPT. and Prior-OPT methods. Figs. 15 17 and 19 show the corresponding adversarial perturbations for the Sign-OPT, Prior-Sign-OP Prior-OPT methods. Initially, all methods start with an image from the target class and iteratively minimize the 12-norm distance to the original image, while maintaining the predicted label as the target class. Prior-Sign-OPT and Prior-OPt achieve a faster reduction in perturbation magnitude compared to Sign-OPT, as shown Figs. 15 and 19
and
38

---

Published as a conference paper at ICLR 2025
40
55
35
DV16-PF
GeoDA
Gre-G
48
Price Sig.-PPP---po
Mean f. Dietortion
30
Suffre
Pre-OFT
Mean fy Distortion
40
Pix Oriige
25
35
30
20
25
20
10
0
1K
2K
3K
4K
5K
8K
7K
8K
8K
10K
1K
2K
3K
4K
5K
6K
7K
8K
9K
10K
Number Queries
Number Queries
(a) 101
(b) ResNeXt-101 (64 4d)
50
HSLA
80
78
RSUA
Sign-din SUN OPT
45
G-TA
2V0 oir
40
CecBA
yo woaeed
65
Drok Bonaroonary
Mean f, Distortion
36
55
Batree
Trango Alaa
30
50
BDA caait
45
-55
40
35
20
30
15
20
10
5
10
0
1K
2K
3K
4K
SK
8K
7K
8K
9K
10K
0
1K
2K
3K
4K
5K
6K
7K
8K
9K
10K
Number Queries
Number Queries
(c) SENet- 154
(d) Inception-V3
RIL
CPT
85
80
Ex94-e
50
G-IA
75
45
GecDA
70
Cadurierayy
Mean E: Dietortin
65
Surtaw
Meen E Distortion
40
Trange Rlacs
Towert
55
35
Biloaoe
50
30
Prix
-5
40
25
30
25
15
20
15
10
5
1K
2K
3K
4K
5K
6K
7K
8K
9K
10K
%
1K
2K
3K
4K
5K
6K
7K
8K
9K
10K
Number of Queries
Number of Queries
(c) Inception-V4 V4
(f) VIT
60
90
HILA
CPT
C-TA
G-TA
Pron-
50
Bealhh
75
Mean à Dietortion
40
45
Suffree
Fusidtinary
Aand
PapstMi
Sage- CoTage
85
70
Trange
Prior
PRp-OPT
36
30
50BACHAY
P aninees
45
50
25
35
40
15
20
25
10
0
1K
2K 3K 4K
5K
8K
7K
8K
8K
10K
1K
2K
3K
4K
5K
6K 7K
8K
9K 10K
Number of Queries
Number Queries
(g) GC VIT
(h) Swin Transformer
Figure 7: Mean distortions of untargeted norm attack under different query budgets on the ImageNet dataset.
39

---

Published as a conference paper at ICLR 2025
100
96
90
85
80
D/A
HAI
SigyCPT
Prian
80
85
0.7%
Pop-CPPluaet2
Sge-CPT
EYNOOFT
75
65
Mean I Distorton
70
Distortion
80
85
80
45
40
30
25
20
2K
4K
8K
8K
10K
12K 14K 18K
18K 20K
2K
4K
8K
8K
10K
12K 14K 18K 18K 20K
Number
Number
(a) ResNet-101
(b) ResNeXt-101 (64 4d)
80
HSIA
BD
90
95
C-TA
5X5--PT
85
D-TA
Ecoiuborury
80
Enduarey
75
Mean 1, Distorion
45
f. Distortoon
65
70
40
60
35
55
30
25
15
10
5
0
2K
4K
6K
8K
10K 12K 14K 16K 1BK 20K
2K
4K
6K
10K 12K 14K 18K 18K 20K Number Queries
8K
Number Queries
(c) SENet- 154
(d) Inception-V3
65
80
GUTA Endiloayy
60
C-TA
Fenu Penutrrory
Supe-
75
55
battee
Mean 1, Distorion
65
60
70
Pay Cenppre
45
50
Prox-
355
30
25
00000
5
2K
4K
6K 8K
10K 12K 14K 16K 18K 20K
%
2K
4K
6K
8K 10K 12K 14K 16K 18K 20K
Number of Queries
Number of Queries
(c) Inception-Ve
(f)
SHRLFFT
70
65
65
60
9-th
Desiuterayy
Suthoo
85
BBACHAT
Statred
& Dietorion
Distortio
50
15
Sie-OFm
45
40
35
30
30
25
20
15
10
10
6K 8K 10K 12K 14K 16K Number of Queries
18K 20K
%
8K 10K 12K 14K 16K 18K 20K Number Queries
(g) GC VIT
(h) Swin Transforeer
Figure Mean distortions of targeted norm attacks under different query budgets on the ImageNet dataset.
40

---

Published as a conference paper at ICLR 2025
100
80
80
Atacc Success Rate
70
Attack Success Rale
70
80
60
50
50
40
40
HoLk
30
TX
30
C-TA
5VU-OFF
G-Dk
20
20
10
OFT
10
ArangeAtes
%
2K
3K
4K
SK
8K
7K
BK
9K
10K
%
2K
3K
4K
5K
6K 7K 8K 9K 10K
Number of Queries
Number of Queries
(a) ResNet-101
(h) ResNeXi. 101 (64 46)
100
100
90
90
80
80
Atock Success Rate
70
Attock Success Rate
70
60
60
40
grooft wher
30
30
Evtiikerryy
Surfinn
20
GeaDA
Die plbeary
20
Trangl
10
Qurriin
Prix-Off
PriccciP
10
%
1K
2K
3K
4K
5K
6K
7K
8K
5K
10K
9
1K
2K
3K
4K
5K
BK
7K
8K
9K 10K
Number of Queries
Number of Queries
(c) SENet- 154
(d) Inception-V3
100
90
80
80
Abbock Success Rate
70
Attack Sucoess Rate Rate
70
60
60
50
50
SVM CPT
40
-Paa--ggn-Om 207)
40
CecDA
30
Pea Sti---t--------mmm excdenc
30
Eriiubeary
Susfins
20
20
Tranja
Prio- Droe
10
SUSA uount
10
50BA
%
3K 4K
BK
10K
9
4K
8K 9K 10K
Number of Queries
Number of Queries (f) VIT
(e) Inception V4
100
100
90
90
80
80
Attack Surcess Rate
Attack Sucosss Rate
50
HSUe
40
40
Pran-Sign-Pe CPTaaannnscar
30
30
Sufffe
20
Thangle Atacc
20
Trangiatad
10
Pees CPT
10
Prio-
%
1K
2K
3K
4K
SK
8K
7K
BK
9K
10K
9
1K
2K
3K
4K
5K
6K
7K
8K
9K
10K
Number of Quarrios
Number of Queries
(g) GC VIT
(h) Swin Transformer
Figure 9: Attack success rates of untargeted fy-norm attacks under different query budgets on the ImageNet dataset.
41

---

Published as a conference paper at ICLR 2025
unbett
GITA
OPT
G-TA
Dicubrery
Fro- 9gg-077
Eood
Pricdd geonnddgFFTaaaaa
Pro Pra-OPhaati0
Success Rate
70
Attack Success Rale
70
60
60
50
50
40
40
30
30
20
20
10
10
%
4K
6K
10K 12K 14K
16K 18K 20K
%
4K
6K
8K 10K 12K 14K 16K 20K
Number Queries
Number of Queries
(a) ResNet-101 101
(h) ResNeXi- 10I (64 4d)
100
HALK
100
HSA
5V/S-FT
90
90
Proe-Sgo-O wholh
80
SurFiee
80
Surfiee
BBA seo
70
Attsck Success Rate
70
60
60
30
30
20
20
10
0
2K
4K
8K
8K
10K 12K 14K 16K 18K 20K
9
2K
4K
6K
10K 12K 14K 16K 18K 20K Number Queries
8K
Number Queries
(c) SENet- 154
(d) Inception-V3
Prin-ign Peo--ign-PP CP%,
DLTX
Fra--ign Swg-Sttf--eeeeom..
Priond Prinndgg OFT
Bucidooaay
FookEwary
Priedigs waaees
80
Prg-OPleceeet
80
Pate
70
Peo- CPTaninnnn
Attack Success Rate
70
Prov
SigcCTT
60
60
50
50
40
40
30
30
20
20
10
0
%
Number Querles
Number Queries
(e) Inception. V4
(f) VIT
100
HSSA
100
MSAA
SUISIPT
90
90
Divudorary
80
Satino
Pap Pay-OPTrane
BRA
Pro-CPTratiinneeii
Pes- PFl-aaaooo
Attack Sucoess Rate
BBA
Surcess
40
40
30
30
20
20
10
10
0
2K
4K
6K
8K 10K 12K 14K 16K 16K 20K
%
2K
4K
6K
10K 12K 14K 16K 18K 20K Number of Queries
8K
Number of Queries
(g) GC ViT
(h) Swin Transformer
Figure 10: Attack success rates of targeted fy-norm attacks under different query budgets on the ImageNet dataset.
42

---

Published as a conference paper at ICLR 2025
HBJA
OPT
Sig-
Q-TA
SUSNOPT
1.5
SUU-CET
2.0
GeoTA
Fanuttorwy
Proe-aga-OPTy todactts
BurFrce
Peze Teaseesss
Burice
Mean fa Distortion
OFage soberts
Mean f, Distortion
Tronj
1.5
1.0
1.0
0.5
0.5
0.0g
1K
2K
4K
5K
7K
8K
10K
0.9g
1K
3K
4K
6K 7K
9K
10K
Number of Querles
Number of Querles
(a) PyramidNet-272
(b) DenseNet-BC-Il (k 40)
HSA4
HSA
SCBA
Sign DPPT
Sign DPPT
1.5
G-TA
DooDA
SVW--PPT
Pese-Saga-DPP
3.0
G-TA
GooDA
Pris Pron-Sagn-CPPTT..m
Evo Excutionary
Prlor Siga-OFTT beskec11
Pric Pio--Bgn-OFTgge
SurFice
2.5
BurFice
Triangra Attck
Mean 1, Distortion
Trinng Attakk
ProxOPTTge (oamee)))))))
1.0
2.0
1.5
0.5
1.0
0.5
0.0g
10K
0.9g
10K
Number of Queries
Number of Queries
(c) WRN-28
(d) WRN-40
Figure 11: Mean distortions of untargeted f2-norm attack under different query budgets on the
CIFAR- 10 dataset.
43

---

Published as a conference paper at ICLR 2025
100
100
70
Altack Success Rate
70
60
HSUA
HBJA
BCBAuemerii
30
Tt
OPT
30
Sign-OF OPT
G-TA
SVALOPT
CITA
SVM OFF
20
Pvdl Soouryy
Price Sig--P 10
Pinne Sig--RRT -aae-tt
20
Porketooayy
Prize San--Pn--PPP somamaann
Guftie
Staties
Pios Peox-OPTesseeee
Trinnll Adtes
Trangls Adtds
1K
2K
3K 4K 5K 6K
7K
8K
9K
10K
%
2K
3K 4K 5K
6K
7K 8K
9K
10K
Number of Queries
Number of Queries
(a) PyramidNet-272
(b) DemseNet-BC-190
40)
100
100
80
80
Attakk Success Rale
Success
50
50
40
40
BCBfewauitte
Bigh
Pior-Stn-OPT -xamets
10
SuiFee
RRor-OPTTg deveett
10
BaFigs
Proo-OPT rewente
Rige OPT musecit
1K
2K
3K
4K
5K
6K
7K
8K
9K
10K
9
1K
2K
3K
4K
5K
6K
7K
8K
9K
10K
(c) WRN-28
(d) WRN-40
Figure 12: Attack success rates of untargeted mn-m attacks under different query budgets on the CIEAR- 10 dataset.
44

---

Published as a conference paper at ICLR 2025
1.00
0.24
Sign-OPT
Sign-OPT
0.90
Prior-Sign-OPr
0.22
Priar-Sin-OPTg-4..
Prior-OPT
0.19
Pria-OPT,-67
Prior-Sin-OPT
0.70
0.17
Prior-OPT,
0.60
0.14
0.50
0055
61
0.15
0.12
0.40
0.10
0.30
0.07
0.20
0.05
0.10
0.02
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
0.00
100
200
300
400
500 600 700 800 900 1000
9
(a) Effect of prior's 's accuracy a
(b) Effect number vectors g
0.23
Sign-OPT
85
=0
q= 120
0.21
Prior-Sign.OP. op
75
40
q= 140
Prior-OPTginng PaaurPTTallllooo Cipp:OPPTiuncoo........ mo0)
0.19
Prior-Sign-OP
65
160
0.16
Prigr-OPT, o,
5
55
100
9
180
0.14
45
0.12
2
0.09
36
0.07
25
0.05
15
10
0.00
3
5
11
13
15
19
1K
2K
3K 4K
5K
6K 7K
8K
9K 10K
Number of Priors
Number of Queries
(c) Effect of number of priors
(d) Prior-Sign-OPT with different g
Figure 13: Experimental results of ablation studies of [E[>]]. Figs.
13a 13b and 13c are based on
theoretical results (Eqs. (10), (12) and (17p) with d = 3072. Fig.
13d demonstrates the results of
attacking against Swin Transformer on the ImageNet dataset using Prior-Sign-OP with different q.
45

---

Published as a conference paper at ICLR 2025
(a) 0 query
(b) 1,110 queries
(c) 2,142 queries
(d) 3,017 queries
(e) 5,007 queries
(I) 8,039 queries
(g) 10,104 queries
(h) 12,184 queries
(i) 15,176 queries
(j) 18,477 queries
(k) 19,032 queries
(l) 20,470 queries
Figure 14: Adversarial images generated with different queries in Sign-OPT targeted attacks against ResNet-101.
(a) 0 query
(b) 1,110 queries
(c) 2,142 queries
(d) 3,017 queries
(c) 5,007 queries
(f) 8,039 queries
(g) 10,104 queries
(h) 12,184 queries
(i) 17,176 queries
(i) 18,477 queries
(k) 19,032 queries
(I) 20,470 queries
Figure 15: The corresponding adversarial perturbations generated with different queries Sign-OPT targeted attacks against 101N
46

---

Published as a conference paper at ICLR 2025
(a) 0 query
(b) 1,092 queries
(c) 2,124 queries
(d) 3,088 queries
(c) 5,368 queries
(I) 8,191 queries
(g) 10,331 queries
(h) 12,025 queries
(i) 15,192 queries
(j) 18,149 queries
(k) 19,138 queries
(l) 20,114 queries
Figure 16: Adversarial images generated with different queries Prior-Sign-OPT targeted attacks against ResNet-101.
(a) 0 query
(b) 1,092 queries
(c) 2,124 queries
(d) 3,088 queries
(c) 5,368 queries
(f) 8,191 queries
(g) 10,331 queries
(h) 12,025 queries
(i) 19,192 queries
(i) 18,149 queries
(k) 19,138 queries
(I) 20, 114 queries
Figure The corresponding adversarial perturbations generated with different queries in Prior-Sign- OPT targeted attacks against ResNet-101.
47

---

Published as a conference paper at ICLR 2025
(a) 0 query
(b) 1,142 queries
(c) 2,424 queries
(d) 3,336 queries
(e) 5,105 queries
(I) 8,047 queries
(g) 10,068 queries
(h) 12,239 queries
(i) 15,646 queries
(j) 18,179 queries
(k) 19,189 queries
(I) 20,233 queries
Figure 18: Adversarial images generated with different queries Prior-OPT targeted attacks against ResNet-101.
(a) 0 query
(b) 1,142 queries
(c) 2,424 queries
(d) 3,336 queries
(c) 5,105 queries
(f) 8,047 queries
(g) 10,068 queries
(h) 12,239 queries
(i) 15,646 queries
(i) 18,179 queries
(k) 19,189 queries
(I) 20,233 queries
Figure The corresponding adversarial perturbations generated with different queries in Prior-OPT
targeted attacks against 101Net-101.
48


Reviews:
[{"review_id": "nVh8mlKDH5", "reviewer": "Reviewer_DsPD", "summary": "The paper addresses the problem of hard-label black-box adversarial attacks. The paper builds on an existing approach that seeks the optimal ray direction from a benign image to minimize the distance to the adversarial region. While this method has shown promise, its high query cost remains a major drawback. A variation of this method that uses ‘signed gradient’ suffers from gradient accuracy limitation. To address these issues, the authors propose incorporating a transfer-based prior to reduce the query burden and improve performance. Additionally, they provide theoretical analysis of the gradient estimation quality achieved through this transfer-based prior and provide insight into its effectiveness.", "questions": "1. **Lines 196-197**: The notation for qi (used for the transfer-based prior) and q (representing the total number of vectors) is confusing. It would help to revise the notation to make the distinction clearer and avoid confusion.\n\n2. **Figure 1**: The figure is unclear and lacks proper labeling. Please add clear labels to define the regions and ensure the equations are more readable and understandable\n\n3. **Figures 9 & 10, and Table 1**: These results highlight that using PGD (Projected Gradient Descent) significantly boosts performance. The question arises: How would the other methods perform if PGD were applied to them as well? Were there any experiments done to investigate that?\n\n4. The results indicate that even adding a single transfer-based prior improves performance. However, it would be valuable to test an alternative where, instead of using random vectors, only prior vectors are used. Are there any experiments that investigate this scenario?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Originality**: The concept of using transfer priors is not entirely new, as it was demonstrated in other works e.g., Dong et al. (2022). However, this paper's novelty lies in applying them to the more practical hard-label setting, where information is limited.\n\n**Quality**: The methodology demonstrates technical soundness, particularly the idea of using transfer-based priors and then the approach to gradient approximation through closest projection on the subspace.  \n\n**Clarity**: The writing could be further improved. Since the paper is based on previous work - Sign-OPT, it can be confusing for someone who is not well familiar with those works. The figures also make it hard to understand the key idea of the paper. In particular, the first figure is confusing as it has a lot of information which is unnecessary and does not motivate the problem or explain the idea well. \n\n**Significance**: The paper makes substantial contributions to adversarial machine learning by introducing a novel attack that leverages transfer-based priors in hard-label black-box setting. The paper demonstrates how this additional information from surrogate models can be effectively used.", "weaknesses": "1. The main contribution of the paper seems to have limited novelty. It essentially boils down to employing Eq (7), which is similar to the Sign-OPT method but with the addition of using gradients from surrogate classifiers.\n2. It seems that the results don't clearly favor one approach over another. In some cases, Prior-Sign-OPT performs well, while in others, Prior-OPT outperforms it. Lines 319-321 mention that Prior-OPT outperforms Sign-OPT under certain conditions, but these conditions are not clearly explained, so the reasoning is unclear.\n3. Another concern is the inconsistent performance in targeted attacks. For instance, in Figures 10(g) and 10(h), the proposed methods are not among the top three, throughout the plots. In other cases, other methods perform equally well (especially for smaller number of queries), yet no explanation is provided for these discrepancies.\n4. The method underperforms when the number of queries is small. For example, in Table 1, for the ViT experiments, other methods achieve lower mean L2 norm distortions with fewer queries. Specifically, for targeted attacks up to 5k queries, other methods generate adversarial examples with smaller perturbations as compared to the proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "iRnuKWAZ3B", "reviewer": "Reviewer_z4Ag", "summary": "This paper introduces two novel hard-label attack methods, Prior-Sign-OPT and Prior-OPT, which leverage transfer-based priors and random sampling vectors to enhance the query efficiency and success rate of black-box adversarial attacks. Theoretical analysis and experiments on ImageNet and CIFAR-10 datasets demonstrate that these methods significantly outperform 11 state-of-the-art techniques while reducing the number of queries needed.", "questions": "Please see the weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a gradient estimation method to conduct hard-label attack and provides proof for it.\n\n2. The paper is well-written.", "weaknesses": "1. The paper benefit from showing the time complexity.\n2. This paper is a comprehensive study based on transfer and query, hence, I hope you could compare it with the results from the paper \"Blackbox Attacks via Surrogate Ensemble Search. Neurips 2022.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ajfazhP2SP", "reviewer": "Reviewer_hzgv", "summary": "This paper proposes a new method for hard-label attacks which uses transfer-based priors to estimate the gradient of the loss in hard-label attacks, which is quite query efficient.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a surrogate function to estimate compute the transfer-based priors, which can avoid the non-differentiable issue of using binary search to learn the prior.\n\n2. The gradient of the loss in Eq. (3) can be estimated by the projection of the true gradient onto the subspace spanned by these transfer-based priors and some random directions.", "weaknesses": "An efficiency experiment is required to show how the proposed method improves the ray search efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "tvTjboXsp6", "reviewer": "Reviewer_cAs8", "summary": "The paper addresses the challenge of hard-label adversarial attacks and enhances the efficiency of searching for the optimal ray direction by introducing a prior-guided approach that leverages transfer-based priors from surrogate models. Theoretical analysis is provided to validate the effectiveness of their gradient estimation technique, and extensive experiments on ImageNet and CIFAR-10 demonstrate significant improvements in query efficiency compared to 11 state-of-the-art methods.", "questions": "See the weaknesses for details", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a solid theoretical foundation for the proposed gradient estimation technique.\n2. Extensive experiments on multiple datasets demonstrate the practical effectiveness of the proposed method.\n3. The focus on improving query efficiency is critical, as it addresses one of the major challenges in hard-label attacks, making the method more applicable in real-world scenarios.", "weaknesses": "1. The following work [1] also proposes to use a pre-trained model to reduce the query complexity of hard-label adversarial attacks. Please clarify the novelty based on this work.\n2. The paper does not adequately address the scalability of the proposed method, particularly in scenarios involving larger models or more complex datasets.\n3. The reliance on transfer-based priors from surrogate models raises concerns about overfitting and the applicability of the method to unseen models or datasets.\n\n[1] Yan, Z., Guo, Y., Liang, J., & Zhang, C. (2021). Policy-driven attack: Learning to query for hard-label black-box adversarial examples. In International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Spotlight)