GSBA$^K$: $top$-$K$ Geometric Score-based Black-box Attack
Authors: Md Farhamdur Reza
Richeng Jin
Tianfu Wu
Huaiyu Dai
Venue: ICLR 2025 Poster (2025)
Keywords: Adversarial Attack
Black-box Attack
Score-based Attack
Top-K Attack
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We proposed a generalized top-K score-based black-box adversarial attack to alter the top-K predictions of the source image.

Abstract: Existing score-based adversarial attacks mainly focus on crafting $top$-1 adversarial examples against classifiers with single-label classification. Their attack success rate and query efficiency are often less than satisfactory, particularly under small perturbation requirements; moreover, the vulnerability of classifiers with multi-label learning is yet to be studied. In this paper, we propose a comprehensive surrogate free score-based attack, named \b geometric \b score-based \b black-box \b attack (GSBA$^K$), to craft adversarial examples in an aggressive $top$-$K$ setting for both untargeted and targeted attacks, where the goal is to change the $top$-$K$ predictions of the target classifier. We introduce novel gradient-based methods to find a good initial boundary point to attack. Our iterative method employs novel gradient estimation techniques, particularly effective in $top$-$K$ setting, on the decision boundary to effectively exploit the geometry of the decision boundary. Additionally, GSBA$^K$ can be used to attack against classifiers with $top$-$K$ multi-label learning. Extensive experiential results on ImageNet and PASCAL VOC datasets validate the effectiveness of GSBA$^K$ in crafting $top$-$K$ adversarial examples.

Published as a conference paper at ICLR 2025
GSBA top-K GEOMETRIC SCORE-BASED BLACK- BOX ATTACK
Md Farhamdur Rezal; Richeng Jin Tianfu Wu' &
Huaiyu Dai
NC State University "Zhejiang University [mreza2, tianfu-wu, hdai addai)eccsu.. edu richengjin@zuu.educco
ABSTRACT
Existing score-based adversarial attacks mainly focus crafting top-/ adversarial examples against classifiers with single-label classification. Their attack success and query efficiency are often less than satisfactory, partieularly under small perturbation requirements; moreover, the vulnerability of classifiers with multi- label learning is yet to be studied. In this paper, we propose comprehensive surrogate free score-based attack, named geometric score-based black-box attack (GSBAK), craft adversarial examples in aggressive top-K setting for both untargeted and targeted attacks, where the goal is to change the top-K predictions of the target classifier. We introduce novel gradient-based methods to find a good initial boundary point to attack. Our iterative method employs novel gradient esti- mation techniques, particularly effective in top-K setting, on the decision bound- ary to effectively exploit the geometry of the decision boundary. Additionally. GSBAK can be used to attack against classifiers with top-K multi-label learning. Extensive experimental results on ImageNet and PASCAL VOC datasets validate the effectiveness GSBA K in crafting top-K adversarial examples.
INTRODUCTION
Deep neural networks (DNNs) are vulnerable to adversarial examples (Goodfellow et al. 2014
Moosavi-Dezfooli et al. 2016 Jia et al. 2022). In white-box attacks (Szegedy et al. 20133 | & Carlini
Wagner 2017: Moosavi- Deztooi et al. 2016 Madry et al. (017). 7. an adversary possesses complete access to the internal structure and parameters of the target DNN, whereas in black-box attacks, this information is not available, making them more practical in real-world scenarios. Black-box attacks be of two types: transfer-based (Dong et al.) 2018 Wang & He 202T Wang al. 2024] Li et al. 2020c Wei et al., 2023) and query based, where the former crafts adversarial examples exploiting a surrogate model, and the latter makes queries for the outputs from the target classifier to craft adversarial examples intended to deceive it. Within musey-based black-box attacks, two
subcategories exist: decision-base -aaed (Chen et al. 2020) Ma et al. 2021 Reza et al.) (023) and score- based (Guo et al.) 2019a Ilas et al.) 201 8b a Andriushchenko et al., (020) attacks. In the former, the adversary has access to the top-/ predicted label from the target model, while in the latter, the adversary can retrieve the full set of prediction probabilities for all classes.
Numerous endeavors have been undertaken towards effective score-basee based black-bor attacks (Chen et al. 2017 Bhagojj et al. 2018 [lyas et al. 2018a Guo et al. 2019a) against classifiers with single- label multi-class classification, where the classifiers goal is to predict the top-1 classification label corresponding to input. Score-based adversarial attacks be either gradient-based (Ilyas al., 2018a by Chen et al. (hagoji et al. 2018), or gradient-free (Andriushchenko et al.) [2000] al. 2019at Li et al.] (2020b). Gradient-based methods rely on small perturbations in the gradient direction to steer the input towards the adversarial region, while gradient-free methods use some predefined random directions for the same purpose. While Square Attack (Andriushchenko 2020), in score-based setting, offers state-of-ther performance, it suffers from low success rates and query inefficiency, particularly when constrained by small perturbation thresholds.
al.,
In recent years, leveraging the geometry of the decision boundary has proven to enhance the effi ciency and effectiveness of decision- based black-box attacks (Liu et al., 20199 Rahmati al. 2020 Reza et al. 2023). Geometric decision becision-based attacks, starting from a random point on the decision boundary, iteratively refine the adversarial example exploring this boundary. However, such efforts
"Corresponding authors

---

Published as a conference paper at ICLR 2025
largely lacking for score-based attacks. A simple comparison between the usual approach of existing score-basee attacks and the ofate-of-the-ar art decision- based attack CGBA (Reza et al. 2023) in finding adversarial examples considering linear boundary in 2D space is shown in Fig. Con- sidering imperfect gradient estimation, the geometric-based attack CGBA finds a better adversarial example along semicircular path, starting from random boundary point Thg- by exploring the decision boundary. This raises an important open question: can the geometric properties of high- dimensional image space boundaries be harnessed to advance the field of score-based attacks?
Traditionally, adversarial attacks have predom- inantly focused on generating top-1 adversarial examples against single-label multi-class clas- sifiers for untargeted and/or targeted attacks, wherein a well-crafted adversarial example re- places the single true label of the input image with an arbitrary label for untargeted attacks and a spe- cific target label for targeted attacks. However, in numerous real-world applications such as web search engines, image annotation, recommen- dation systems, and computer vision APIs like Google Cloud Vision, Microsoft Azure Computer Vision, Amazon Rekognition, and IBM Watson Visual Recognition, the top-K predictions pro- vide valuable information about the input. Thus, recently, a couple of white-box attacks (Zhang & Wu [2220] Hu et al. 202T]
Adversarial region
enversarialrggionn
9 Xbu
V0
Xadv
X udvv
8.
X
Xg
X Non-adversarial region
Non-adversarial region
(a)
(b)
Figure I: (a) Traditional score-based attack approach: adversarial example Tade is gener- ated by iteratively adding perturbations in the direction of the estimated gradient or random directions with source T. Perturbations are weighted based on the increase in confidence toward the adversarial region. (b) Geometric- based approach CGBA (Reza et al., (023) in finding a better adversarial example exploring the decision boundary.
( Tursynbek et al. [022] Paniagua et al. (023) have been proposed in an aggressive top-K setting where the top-K predic- tion labels of an input replaced by arbitrary set of mutually exclusive wrong labels for untar- geted attacks (Tursynbek given set of target labels for targeted attacks (Zhang & Wu 2020 Paniagua et al. 2023). Among these attacks, T ML--A (Hu et al., 2021) targets classifiers with multi-label learning, where the classifiers' goal is to learn multiple meaningful true labels from an image. These white-box attacks, having full access the target classifier, can calculate the true gradient to navigate towards the ad- versarial region and craft top-K adversarial examples with high attack success rate (ASR), demon- strating the underlying vulnerability of DNNs. However, this task becomes much more challenging in the more practical black-box setting with only predicted probabilities of all classes are available, as we lack accurate intermediate gradients for navigation the high-dimensional continuous space. In this case, identifying initial boundary point satisfying the top-K target-label constraints may be akin to finding a needle in an ocean. On top of that, we need to further refine the obtained adversarial example to meet the perturbation threshold constraint across the highly irregular adversarial region.
al. 2022), and by a
To address the aforementioned challenges, introduce com- prehensive query-efficient geo- metric score-based top-K black- box attack, GSBAK, that employs distinct approaches to approxi- mate gradients by querying the tar- get classifier, aiming efficiently identify good initial boundary points for both untargeted and tar- geted attacks rather than starting from random boundary point done by geometric decision- based attacks. However, the ob- tained initial boundary points, uti- lizing the estimated gradient di- rection, often significantly deviate from the optimal. Thus, we further
Benign
10*Perturbotion
Adv. Example (best)
Top-2 predictiony: cow, potted plant
Top predictions:
10*Perturbation
Exompll (worst)
person, dog
Tap-2 2 predictions: aeropione
+
Figure 2: Crafted top-2 adversarial examples against Inception- V3 (Szegedy et al. 2016) with top-2 multi-label learning the PASCAL VOC 2012 dataset (Everingham et al. 2015) by considering the best and worst larget-label sets (Sec. 5.2). The prediction order based on confidence scores of the benign in- put is: [person, dog, cow, polied plant, horse, chair, car, dining table. bottle, sofa, cat, ty/monitor, bicycle, sheep, boat, motor- bike, bird, bus, train, aeroplane).
2

---

Published as a conference paper at ICLR 2025
introduce more accurate gradient estimation techniques at boundary points by leveraging the pre- diction probabilities. Guided by the estimated gradient on the decision boundary. GSBA conducts boundary point search along semicircular trajectory, motivated by the state-of-the-arr (SOTA) decision-based attack CGBA (Reza et al. 2023), to explore the decision boundary and further op- timize the perturbation. GSBA is designed to perform attacks not only on traditional single-label multi-class classification problems but also on classifiers with top-K multi-label learning capabili- ties; see Fig. 2 for crafted top-2 adversarial examples. The contributions of this paper are summa- rized as follows:
We propose GSBAK, comprehensive and query-efficient geometric score-based attack in an aggressive top-K setting. GSBA incorporates novel gradient estimation techniques to locate a better initial boundary point and leverages the geometric properties of decision boundaries to enhance both query efficiency and attack versatility.
the difficult top-K targeted attack, our gradient estimators assess the impact of each query on the individual target classes and assign adaptive weights based on their significance.
We adapt the SOTA score-based Square Attack (SA) (Andriuscchenoo et al.) 2020) to the top-K setting to serve baseline. Comprehensive experiments on ImageNet (Deng et al. 2009) and PASCAL VOC 2012 (Everingham et al.) (015) datasets against popular classifiers underscore the efficacy of GSBAK in handling both top-7 and complicated top-K, including multi-label learning scenario, across untargeted and targeted settings.
2 RELATED WORK
Black-box adversarial attacks. The top-1 classification label is the sole piece of information
available to an adversary in decision- based attacks. These attacks can be either gradient-fre (Bren-
del al. 2018: Brunner et al.] 2019: Li et al., 2022| Dong et al. 2019 Maho et al. 2021 or they
can involve ve estimating the gradient on the decision boundary (Chen et al., [020 Li et al. 2020a
Rahmati et al. 2020, Reza et al. 2023). Based on the use of the geometrie properties of the decision
boundary, decision-based adversarial attacks can also be categorized as geometric socision-based
adversarial attacks (Rahmati et al. 2020: Maho et al. [02T]] Ma et al.] 2021 Wang et al. 2022]
Reza et al.) 2023). While Tangent Attack (Ma et al. 2021) considers the decision boundary
virtual hemisphere to refine the boundary point, Triangle Attack (Wang et al. 2022) used the trian-
gle inequality refine it. GeoDA (Rahmati al. 2020) and SurFrre (Maho et al. 2021) focus on the hyperplane boundary, with GeoDA using estimated gradient information to execute the attack, while SurFree is gradient-free. In contrast, CGBA (Reza et al., (2023) demonstrates the difference in curvature of the decision boundaries for untargeted and targeted attacks, based on which algorithms are proposed that go beyond the simplified hyperplane boundary model and exploit the distinct cur- vatures of the decision boundary for improved attack performance.
In score-based attacks, an adversary avails itself of the information of prediction probabilities of all the classes when querying the target classifier. Although most bcore-based attacks operate without surrogate models, some approaches (Guo et al. [201bb] Cheng et al.) 2019 Yang et al. 2020) incor- porate surrogate models to improve efficiency. Among the surrogate free attacks, 700 (Chen et al.) 2017) employs the finite difference method with dimension -iie estimation to approximate the gra- dient, requiring 2d queries per iteration, where d is the dimension of the image. To improve the query efficiency of gradient estimation, (Bhagoji et al. 2018) reduces the search space using PCA of the input data, while AutoZOOM (Tu et al. (019) samples noise from the oiw-dinensional latent space of a trained auto-encoder. NES (Ilyas et al. (018a) uses finite differences through natural evolution strategies for gradient estimation. In the quest for further improved query efficiency, Bandits (Ilyas) et al. 2018b) incorporates two priors: a time-dependent prior and data-dependent prior. All the aforementioned gradient-based attacks iteratively add noise toward the estimated gradient direction to craft adversarial examples. SimBA (Guo et al. 2019a). however, queries along a set of orthonor- mal directions to obtain adversarial perturbations. Despite its simplicity, SimBA outperforms the un-
gradient- based methods. PPBA (Li et al. 2020b) introduces a projection and probability- targeted attack, focusing on reducing the solution space by employing low-frequency constrained sensing matrix to enhance query efficiency. Conversely, SA (Andriushchenko et al. (2200) samples a small block of noise at some random locations of the image and add the noise with the image if it increases the confidence towards the adversarial region. There is another line of research that crafts sparse adversarial examples (Croce & Hein, 2019; Croce et al. (022). focusing on attacks that limit the number of perturbed pixels minimize detection. Nevertheless, SA offers SOTA performance
3

---

Published as a conference paper at ICLR 2025
in crafting untargeted and targeted top-/ adversarial examples satisfying norm constraint among the existing surrogate-fre reggate-freeaaeee score-basee attacks (Li et al. 2024).
Top-K white-box attacks. Up to date, the vast majority of adversarial attacks in literature have been focused on the top-1 setting, except for some pioneering white-box attacks, An ordered top-K white-box attack is proposed in (Zhang & Wu. 2020), which uses adversarial distillation frame- work in crafting adversarial examples by minimizing the Kullback-Leible divergence between the prediction probability distribution and the adversarial distribution. ML (Hu et al. (022)) proposes a white-box method to create top-K untargeted and targeted adversarial perturbation for the multi- label learning problem. The DeepFool attack Aloosavi-Dezfood et al. 2016) that was proposed for top-1 adversarial examples is extended in (Tursynbek et al. (022) to compute top- K untargeted ad- versarial examples. Moreover, (Paniagua al.]|202) introduces a quadratic programming method to learn ordered top-K adversarial examples that addresses attack constraints within the feature em- bedding space. (Mahmood & Elhamifar 2024) proposes a framework for crafting semantically consistent adversarial attacks multi-label models using consistent target set.
THREAT MODEL
Consider a classifier P(x) [0. 1 + [0, where Cr, W, H are the channel, width, height of arbitrary input æ. and C denotes the number of output classes. The classifier outputs prediction probabilities for all classes in response to a query. To be more precise, Pa(x) represents the probability that belongs to class with the constraint that > Pc(x) = 1. For given input ar the set of top-K predicted labels by the classifier can be expressed as follows:
8x (ax) =
[arg sort Pa(x)));) cE[C]
(1)
where arg ce(C] returns indices of sorted elements in decreasing order of probability, and [C] = {1, 2.., C} denotes the label set. For instance, [arg sortseree Pa (z)))]; contains the label index of the class with the 2th highest prediction probability.
An adversary's 's objective is to generate an imperceptible adversarial example, without using surro- gate models, from benign input image æ, which is correctly classified by the classifier. While the true label set of x, for the classic single-label multi-class classification problem is expressed as C. = ) (x.)), for top-K multi-label learning it is expressed as C, = (x.). In score-based attack, having the information of the prediction probabilities by querying the target classifier, the adversary aims to identify a unit direction ④ in which æ, moved into the adversarial region with minimal perturbation. A query F, = x. + r(ê) in the direction Ô considered the adversarial region if 1 (ax,)) = 1, where r r(θ) = ||0.-- x: 2 represents the perturbation added in the direction Ô. The indicator function 1 (Ir,) informs whether the query D. falls within the adversaris region or not. For an untargeted attack, aiming to move the true label set outside the top-K K predicted classes, the query success indicator function takes the following form:
1, if C. & (x())))
1 (xx,) = 1-1, otherwise.
In contrast, targeted attack seeks to replace the top-K predictions of the input x, with predefined set of K target classes, yi! [C] \ C.. Thus, the query success indicator function for targeted attack is:
1, if (x,(),)) =:0()
1(xx))
(3)
-1, otherwise.
If é' represents the optimal direction to obtain the desired adversarial image Bady = x. + r(6)), the optimization problem can be formulated as:
arg min [|r(@)] s.t. 1(x, + +r())) =
(4)
4 OUR PROPOSED GSBAK
The proposed GSBAK, guided by the approximated gradient direction in crafting adversarial exam- ples, involves three key steps, as depicted in Fig. 3 (a) Estimating the gradient in the non-adversarial region to approach the decision boundary iteratively to find better initial boundary point; (b) Esti-
4

---

Published as a conference paper at ICLR 2025
1 (xp 1(x,))
8
(xy 1=(x,)=11
[x(x,))
4b.
xb.
(xg 11(xz) = -11
x, (xg 1xxx,)
8x
(xg (xxx))
(a) Step
(b) Step 2
(c) Step
Figure 3: (a) Estimated gradient 9w, on source image R, using Eq. for targeted and Eq. 10 for un- targeted attacks in the non-adversarial region; (b) Approximated gradient In.., at a decision bound- ary point Tb, using Eq. 12 for targeted and Eq. 13 untargeted attacks; and (c) Subsequent bound- ary point 2b...1 search in the 2D plane spanned by (9e.., 1b,), where 1h., denotes direction of æbb, from 2.. While the light green and the light orange regions indicate non-adversarial and adversarial regions, respectively, the dark green (dark orange) arrows indicate directions to increase (decrease) confidence toward the adversarial region.
mating the gradient at the boundary point by leveraging the prediction scores; (c) Finding the next boundary point with reduced perturbation along a semicircular trajectory under the guidance by the estimated gradient on decision boundary. The key novelty of GSBA K is its ability to more accu- rately estimate gradients both within the adversarial region and at the decision boundary in the aggressive top-K setting, enabling efficient boundary exploration to enhance ASR.
To estimate the gradient around a point æ in image space, we generate In number of noise samples {zi)/= from the low-frequency Discrete Cosine Transformation (DCT) subspace and exploit the prediction probabilities of + 25; Vz, {z from the target classifier. The DCT subspace encapsulates critical information of an image, including the gradient information (Guo et al. 2018 Li di al. 2020a) (for more, please refer Appendix [F).
For a top-K largeted attack with the constraint of a target-label set y to indicate the impact of an added z; to x specific target class E ) we exploit the following information:
(5) where a positive (or negative) value of Wæ,c,,, indicates the increase (or decrease) in confi- dence towards the target class due to the added z; to æ. For any query Ty. let eg [arg secy,,, (3xg)) denote the index of the class other than C, with the K-th largest pre- diction probability. Additionally, let e, arg max (a(a)) denote the source class with the highest prediction probability. For a top-K untargeted attack, where adversarial queries can take any set of top-K classes from [C]] \ C,, the adversarial region becomes significantly broader. Thus, we exploit the following information for an untargeted attack:
Wm.c,z; := Pa(( 2,) Pr(a),
Fz, :- Pex (xg) - (xxg),
(6)
where {a Fe > 0} indicates the adversarial region. With this higher positive value of Fe,, implies a more confident By in the adversarial region than the non-adversarial counterpart.
4.1 GRADIENT ESTIMATION IN NON-ADVERSARIAL REGION
Finding a good initial boundary point 2b, is crucial for the success of a geometric attack. Unlike geometric decision-based attacks (Chen al. 2020 Reza al. 2023), which locate The employing a random direction for the untargeted attack, and a binary search between the source image and a random target image for the targeted attack, our approach utilizes estimated gradient directions to find a better Tbg We estimate the gradient 9x, at æ, by querying around it and iteratively shift the query sample in the gradient direction 9r, := 9z./ /l.//1g1..l ll using fixed step size to locate Tby
In targeted attacks, estimating the gradient inside the non-adversarial region at point æ%,, is chal- lenging as it involves finding the direction towards the narrow adversarial region constraint by the target-label set ()(() Querying within the non-adversarial region around a',, will result in all queries being non-adversarial, in Fig. Bal Since the adversarial objective is to continuously increase the confidence of the target classes, to estimate gradient at ah/y. the adversary may target the region {a/, zi| min (y(()) Pa + 2.) min CE>/EE (a(x)),) > 0} that ensures gradient direction to enhance the minimum confidence among the target classes. Thus, we define the following indicator function to check whether query around ane,, satisfies the adversary's goal:
5

---

Published as a conference paper at ICLR 2025
2x (z:) 1, if min cey Po(er + zi) - min minceyfe Pa(arhn) 0
cEvi''
otherwise.
However, all the queries that satisfy Qui,, (zi) = are not equally effective. For instance, for a top-3 targeted attack, consider the prediction probabilities with the target classes from the target classifier for T/ as {0.12, 0.13, 0.1). Assume, 21 changes these probabilities to [0.13, 0.14, 0.11), while 22 modifies these to f0.11, 0.1.0.122.. 0.11}. While both 21 and 22 enhance the minimum confidence among the target classes (i.e., Dar (z:) = 1 for both), ž1 has greater impact as it improves confidence across all target classes. To indicate the impact of the added 2; to T on a particular target class e E y we introduce the following indicator function
Xa G. = (
1, if dah,, (zi) S.:;; otherwise,
[0,
(8)
where Way,, c..e, is defined in Eq. 5 Note that Xah, e. = includes the query that satisfies dwi -1 with a decreased confidence on i.e,, Wayy, ,0:2 < O, which will be included in gradient estimate, experimentally it is observed that, with very high probability, Xat, ...s, X# e,=x, satisfies. Thus, the gradient in the non-adversarial region for the top-K targeted attack can be estimated as:
Ia
Xmin Xmrg m.z.)
(E Woin na xax n.z.) 2i.
gobp
2=1
where Ecergo Xat, e.z. counts the number of target classes with increased (or decreased) confi- dence when Oai,, (z,) = 1 (or Dwi, (z,) = -), and Eeergo (.r, c.,, captures the change in confidence of these classes. Eq. 9 provides gradient direction that effectively increases the con- fidence of the minimum prediction probability among 2i(() and iteratively finds a boundary point Tbn It is effective in finding Pt, it considers the impact of 2; each of the target classes in K and assigns weight to z; accordingly. Additional analysis, showing the impact of each component in Eq. and the rationale behind it, provided in Appendix A.I
Turning to untargeted attacks, querying around 2hh result in Far,, +2, 0; Vz, E { due to the reason discussed above. Thus, having a wider adversarial region, to estimate the gradient at Tho, we consider the impact of on the enhancement of confidence towards the adversarial region relative to the non-adversarial counterpart. This gradient can be approximated as:
To
gwhn
Σ
(Fei,_
(
Fasi,)) 2i:
(10)
i=1
where +2,,,22- +2, - Fai, L > O signifies increased confidence towards the adversarial region in relative the non-adversarial region, due to perturbed 2// + z, compared a/yy and vice versa. This strategy leverages the available prediction probabilities, enhancing the possibility of finding good Tbo for the untargeted attack such that 5'x (ar))) E [C] C..
4.2 GRADIENT ESTIMATION ON DECISION BOUNDARY
Gradient estimation on the decision boundary plays a pivotal role in our proposed approach. For a targeted attack, the gradient is estimated at boundary point Tb, by querying around it in each iteration to find the next boundary point Tb,., with reduced perturbation. However, estimating the gradient for top-K targeted attacks with a narrow adversarial region still complicated. Not all adversarial queries contribute equally to this goal. Some queries may behave anomalously, leading to reduction in confidence across all target classes, while others may improve confidence for only subset of the target classes. Idcally, the most effective queries across all the target classes. For instance, consider that the prediction probabilities the target classes yo()) for top-3 attack, at Lb,, are (P.( ) ceyg" = (0.10, 0.08, 0.12). After applying three random perturbations. the resulting prediction probabilities are (P.,(x.. + 21) 2))) [0.009 0.07, 0.11), (0.09, 0.07, 0.15), {0.11, 0.09, 0.13)|: 1 1(x), + 2,) = 1, E [3]. In this exam- ple, the first perturbation is anomalous, it reduces the overall confidence in the target classes. The second perturbation biases the result towards a particular class, while the third perturbation increases confidence in all target classes, making it the most effective for achieving the adversarial goal. Thus,
those that increase confidence

---

Published as a conference paper at ICLR 2025
Algorithm 1: GSBAK
Input: benign image query budget Q, base query number To, step size tolerance
Output: adversarial image Wade-
The = Da. Q' 1.
while (4/h)) -1 do
Aw = / /19
|/2 based on Eq. 9 and Eq.
10 for targeted and untargeted attacks, respectively,
using lu queries.
a/o = 2ing + - Q Q' Iu+1
Zdny Quin BinarySearch(e,, Tho 1(),T).
Q' = Q²= Quin: n= O.
while Q' < Q do
10
estimate Jms.. = gms. /lggs, |la based on Eq. 12 targeted and Eq. 13 for untargeted attacks using
LLvv + queries.
11
direction of the boundary point from the source image: vp.,
= lll as shown in Fig. 3c
2ba+1 Qha f- next boundary point along semi-circular path guided by grs, and si.. and corresponding query cost, as discussed in CGBA (Reza et al. 2023).
12
13
Q' Q' + Lovv+ + + Qha; n 1.
14
return: Bade Db,
also propose effective gradient estimation technique decision boundary point by leverag- ing the available information for the challenging top-K K setting that filters out anomalous queries and assigns greater weight to perturbations that have higher impact achieving the adversarial goal.
Now, we introduce an indicator function that assesses whether the query Fb. 2; is adversarial and leads to increased confidence to the class >)(()
1, if 1(xs. + z, 2,)wa,, 1. > 0
(11)
0, otherwise.
Similar to Eq. 8 also includes the aon-rvreraaa queries (1 (3%6. + z;) = -1) while Was, ,f,;; O, which will be incorporated in the gradient estimate by flipping the sign of z;. The gradient for the intricate top-K targeted attack is thus estimated as:
ge
Seaa ci
(E Wws, cass Sera,, c.
Zi.
(12)
DEV
Here, Eneyth Sai, C,2, and Σ E War, C, S,,, are weights assigned to z, to estimate the gradient. The former counts the number of target classes for which 1 (2%e, + 2; );)Was, ..z; > 0, while the latter captures the strength of increased (or decreased) confidence towards the adversarial region the query is adversarial (or aon-adversarial.. Additionally, Leergh (ao,, ... = 0 indicates the query is anomalous. The proposed method offers improved gradient estimation by emphasizing the impact of the added noise z; on each of the target classes comparing the prediction probabilities of the boundary point æb,, and the perturbed T5,, 2;. It assigns more weight to z; in estimating the
gradient, if 2; impacts more target classes in ) while filtering out anomalous queries that do not correctly contribute to the adversarial goal. For more detailed discussion of the rationale behind Eq. [2] including the impact of each component in it on gradient estimation and comparisons with other possible choices of gradient estimation, please refer Appendix A.2
In an untargeted attack, since the attack transitions from a small set of source classes to any top-K classes in [C]\C, C. the likelihood of anomalous queries is greatly reduced. In this scenario, it suffices to evaluate the impact of the added noise z; based on how effectively it enhances confidence toward the adversarial region compared its aon-adversarial counterpart. Under this setting, the gradient can be can be straightforwardly approximated as:
In
F a
(13)
The larger the positive value of Fes, + the greater the confidence shift towards the adversarial region relative to the aon-adveraliial one, and more weight is assigned to z; if the change is higher. Note, Eq. 13 also incorporates 2,, which results in non-adversarial queries (Fa,, +z: < 0) and

---

Published as a conference paper at ICLR 2025
Shrbh 5036
A38000
Smik OCT
5ma4
1920
1803)
2000 4693 46033
Qsery budget
Queyy badget
Query bedget
Query budget
(a) Te = 2, Untargeted Figure 4: ASR(%) vs. queries in crafting top-/ adv. examples against ResNet-50 on ImageNet.
(b) Fah = 4, Untargeted
(c) Tshh = 4, Targeted
(d) Teh = 6. Targeted
weights them accordingly, it is highly probable that Fæ.,, < impact of non-adversarial queries on attack performance is discussed in Appendix A.3
F
0. The
The steps of GSBA are outlined in Algorithm [] Line Line O are used iteratively shift æ, into the adversarial region with a step size Then, a binary search between the obtained point inside the adversarial region and æ, conducted to locate the initial boundary point Th within a certain tolerance From Line Line perturbation using the similar semicircular boundary as CGBA (Reza et al.] (023) guided by the proposed estimated gradient 9æs,, on the decision boundary for both untargeted and targeted attacks. The code our attack is available at atttps:: /ttepp://qithubee com www.aaaaaauuuuu////aaaaooaaaa GSBBAK
9 13 GSBAK iteratively finds boundary point with reduced
5 EXPERIMENTS
In this section, we first outline the baselines, evaluation metrics, and hyperparameters employed for both the baselines and GSBAK Subsequently, we present the experimental results on ImageNet, which contains 1,000 classes, and the PASCAL VOC 2012 dataset, which includes 20 classes, il- lustrating the efficacy of GSBA in executing lop-K attacks. The limitations and potential negative impacts of GSBA K are addressed in the supplementary material.
Baselines, evaluation metries and hyperparameters. To evaluate the performance of GSBA we choose score- score-based attacks SimBA-DCT (Guo et al. 2019a). PPBA (Li et al., 2020b) and SA (Andriushchenko al. 2020) as baselines. To the best of our knowledge, SA offers SOTA performance in score-based setting. The baselines are only designed to craft top-/ adversarial exam- ples against classifiers with single-label multi-class classification. While SA and SimBA-DCT can generate both untargeted and targeted adversarial examples, PPBA is restricted to untargeted attacks. Nonetheless, the proposed GSBAK is versatile in crafting top-K adversarial examples for both untar- geted and targeted attacks, and both single-label and multi-label learning. To have strong baseline the top-K setting, we adapt the loss function of SA (Andriushchenko al. 2020) for both untar- geted and targeted attacks, enabling its application in crafting top-K adversarial examples, coined as SAK For untargeted attacks, we modify the loss function in (Andriushchenko et al. (020) to L(f(x)), c.) fe, (zq)= fex (zz). where e, and Uk are defined in Sec. Likewise, for targeted at- tacks, the loss function is modified to (f( 22 = min Jevl?' fz (x,)) + mmxx Je (z,))
for K > 1. This adaptation enables the effective crafting of top-K adversarial examples using SAK
We evaluate our method primarily using the metric Attack Success Rate (ASR). An attack is deemed successful if it crafts an adversarial example below a specified mo-m perturbation threshold, ruk- using queries within the allocated budget, Q. The lower the Tth. the more queries are required to make an attack successful, and vice versa. We also assess the effectiveness of an attack using the median fn-norm of the perturbation. A lower median perturbation value across all crafted adversarial examples within the allocated query budget indicates greater attack effectiveness.
Baseline implementations leverage the codes provided by the respective authors, with some suitable parameter adjustments. While SA accounts for constraints both in Q and rıh in defining attack success, SimBA-DCT and PPBA only consider the constraint in Q. potentially giving a false sense of success. Empirically, it is observed that the crafted perturbations in the default setting of SimBA- DCT and PPBA are often large and suffer from low ASR for a small 7th- To address this, we set = 0.1 for SimBA-DCT and 0.001 for PPBA, where and p control the magnitude of noises added at each query step for the respective methods, while retaining other parameters at their default settings. For SOTA SA, dimensional frequency subspace with a dimension reduction factor f = 4 to sample low- cow-frequency noise (z:). We set the base query number To 30, step size 6, and tolerance 7 0.0001.
the default parameters. In the case of GSBAK, we use reduced-
8

---

Published as a conference paper at ICLR 2025
Table I: ASR(%) () for different perturbation thresholds (rts) and query budgets (Q) against ResNet- 50 on ImageNet.
Amack Type
Untargeted Attack
Tarstel Amack 20000
CSBA
SA
Fxuml
26.5
29.2
61.4
50.2
58.1
76.88
$4.5
71.2
76.1
$7.9
71
9,4
3.2
23.4
5.1
47.5
16.2
62.4
22.0
20.6
69.9
App-1
50.7
75.6
85.6
96.3
19.3
55.5
CSBA
50.4
85.3
94.6
36.3
71.6
92.2
97.3
CSBA
Pax.6
74.9
75.2
98.0
95.6
98.8
99.6
100.0
18001
63.2
37.4
98.5
60.1
84.5
99.2
91.3
99.9
108.0
SAe GSBAA
12.8
10.3
25.9
40.5
55.
41.2
48.7
69.7
55.4
7et.
0.9
3.1
9.8
26.8
6.6
39.1
12.9
16.11
A5p-2
OSBA
25.6
68.7
83.7
97.3
16.
75.6
87.6
SA'
55.4
84.1
9531
96.0
58.9
19.5
30.6
57.5
67.4
7311
GSBAA
30.5
89.3
91.2
99.5
1000
36.7
71.6
92.4
97.1
98.2
SA'
17.9
2.4
OSBA'
50
30.5
47.1
63.4
4.8
14.
26.5
GSBA'
SA
7
1988
17.3
62.6
45.9
77.3
56.3
08.3
90.2
90.9
72.3
Tet.m
8.2
3.7
27.3
9:3
65.8
19:3
71.2
27.0
78.8
31.8
SA'
46.8
71.1
$8.5
04.8
91.4
10.1
22.3
33.2
44.6
51.1
GSBA
84.8
95.11
99.1
21,9
49.2
77.8
SA'
2.5
12.6
18.6
26.9
30.0
0.5
0.8
1.2
1.6
2.5
GSBA'
36
24.7
40.5
56.8
61.3
0.4
1.5
9.9
15.7
22.0
App-
GSBA
SA''
Feum2
143
12.4
37.4
72.3
50.5
62.9
66.3
4.3
1.4
3.1
39.2
11.5
55.7
16.6
19.7
12.1
22.3
OSBA'
34.2
78.6
93.7
10.1
35.0
61.5
5.1 RESULTS AGAINST SINGLE- MULTI-CLASS CLASSIFICATION
We assess GSBAK by conducting attacks against three widely used pre-trained classifiers ResNet- 50 (He et al. 2016). ResNet-101 (He et al. 2016), and VGG-16 (Simonyan & Zisserman (2014) trained for multi-class classification on the ImageNet (Deng et al. 2009) dataset. The pre-trained ResNet-50, ResNet-101 and VGG-16 models are sourced from Py Torch. In the case of untargeted attacks against classifier on ImageNet, we randomly select 1000 images that are correctly classified by the respective classifier. For targeted attacks, we create 1000 sets of images, each comprising a benign image F, and a target image Ft. The top-K target labels are extracted from the target image O (xx.. The input image size for all classifiers on the ImageNet dataset is set as 3 x 224 x 224.
Comparison with top-1 baselines. We compare the performance of the proposed GSBA' with SimBA-DCT (Guo et al. 2019a), PPBA (Li et al. 2020b) and SA (Andriushchenko et al. 2020 in crafting top-/ adversarial examples against classifiers with multi-class classification. Fig. depicts the variation of ASR against ResNet-50 on ImageNet with differing query budgets across various 7th values. From Fig. 4 for untargeted attacks, the ASR of SA is comparable with GSBA' for rth = 4 and reaches around 100% ASR. However, GSBA offers better ASR than SA with reduced rih- Experimentally, it is observed that with a higher value of rts, than 4, both SA and GSBA converge faster towards the 100% ASR. Conversely, for targeted attacks, GSBA outperforms the baseline by a considerable margin in ASR. Additional results for other classifiers are provided in Appendix B
Results on crafting top-K adversarial exam- ples. The ASR in crafting up to top-4 adver- sarial examples for both untargeted and targeted attacks against the ResNet-50 classifier on the ImageNet dataset is presented in Table T con- sidering different query budgets and perturba- tion threshold ris- The corresponding curves for ResNet-50, with rus = 2 for untargeted at- for targeted attacks, are de- picted in Fig. 5 The obtained ASR for differ- ent TıΛ and query budgets against other regular classifiers are given in Appendix C Additional evaluations against number of robust classifiers are provided in Appendix D We choose SAK K for the performance comparison, as it offers SOTA performance in the top-/ setting.
GEEA"
Quay todget
Quiry Imdgg:
(a) Untargeted
(b) Targeted
tacks and Tzh
Figure 5: ASR(%) versus queries for the attack against ResNet-50 on ImageNet.
In the context of untargeted attacks, it is noteworthy that while the ASR is comparable to SAK K when the query budget is relatively low, the proposed GSBAK method notably outperforms SAK as the query budget increases. Furthermore, for a given query budget and fixed K, the relative ASR of GSBAK K compared to SAK K increases rıh. decreases. Additionally, with fixed query budget and Tek. the relative ASR of GSBA compared to SAK K improves as K increases. For the targeted attack, by contrast, GSBAK demonstrates significantly higher ASR compared to SAK across the board,

---

Published as a conference paper at ICLR 2025
Source
Targe
(b) Targeted: Query budget 20000. Figure 6: Different top-K adversarial examples against ResNet50 for a benign input. Table 2: ASR(%) against Inception-V V3 with top-2 multi-label learning on the PASCAL VOC 2012 dataset.
(a) Untargeted: Query budget 2000.
Targs type
Kunckm
TuL
20000
30000
45000
10000
40000
10300
20000
50000
-0000
$0.0
73.0
98.0
100.0
196.0
52.0
39.0
51.0
59.0
OSBA!
99.0
50.0
62.0
68.0
75,0
$0.0
SAa
12.0
51.0
58.0
06.0
6.0
9.0
13.0
15.0
0100
0.8
1.0
3.0
GSBA
40.0
65.0
78.0
83.0
9.0
25.0
45.9
$3.0
5.0
36,0
46.0
53.0
6
GSBA
SA
$3.0
$1.0
800
7500
$3.0
71.0
80.0
K2.0
34.0
11.0
44.0
2311
$3,8
23.0
32.0
62.8
17.8
2.0
50.0
5.0
57.01
100
67.0
11.0
SA*
67.0
5011
$1.0
67.0
15.0
2511
41.0
16.0
7.0
14.1
196
31.0
CSBA
66.0
K2D0
39.0
90.0
31.0
55.0
61.8
00.0
24.0
54.
65.0
75.0
specifically in crafting adversarial examples with reduced perturbation. Moreover, GSBAK achieves substantially higher ASR than SAK in crafting top-K targeted adversarial examples with higher K. The crafted adversarial examples and their corresponding perturbation with different K for a benign input are depicted in Fig. For additional top-K adversarial examples and detailed insights, please refer to Appendix
5.2 ATTACK AGAINST MULTI-LABEL LEARNING
We employ the proposed GSBA K to attack against top-K multi-label learning, a task aimed at identi- fying the top K prediction labels for a given input. To execute an attack against a target model with top-K multi-label learning, we use Inception-V. V3 (Szegedy et al., (016), obtained from the GitHub repository of (Hu et al. 202T). This model pre-trained on ImageNet (Deng et al., 2209) and fine- tuned on the PASCAL VOC 2012 dataset (Everingham et al.] 2015). We focus on targeted top-K attacks, and categorize the possible target sets into three types: best, random, and worst. For be- nign input, the best target labels refer to set of K labels, excluding true labels, with the highest prediction scores; conversely, the worst target labels denote those with the lowest prediction scores, and Random target labels represent set of K randomly selected mutually exclusive labels, exclud- ing true labels. To perform the top-K attacks, we use 100 benign samples with true labels from the PASCAL VOC 2012 validation and perform attacks considering the aforementioned three categories of target sets. The input images are resized to 3 x 300 x 300 dimensions before being fed into the target model.
Table demonstrates the ASR in crafting top-/ and top-2 adversarial examples for different query budgets and perturbation thresholds, considering the best, random and the worst target label sets. As seen from these results, GSBAK outperforms SAK across the board. Specifically, with the con- sideration of random and worst target labels, GSBAK K notably outperforms SAK Importantly, while SA² fails to converge the desired perturbation for the worst target labels within the given query budgets, GSBA² maintains significantly higher ASR. From Table and Table ASR decreases as K increases. The impact of higher K on ASR is detailed in Appendix E. while the effect of varying reduced- dimensooaa frequency subspaces for sampling z; explored in Appendix F
6 CONCLUSION
In this work, we propose geometric score-based attack, GSBAK, to effectively generate strong top- K untargeted and targeted adversarial examples against classifiers with both single-label multi-class classification and multi-label learning tasks. It introduces novel gradient estimation techniques for the challenging top-K K setting, efficiently finding the initial boundary point and effectively exploit- ing the decision boundary iteratively refine the adversarial example by leveraging the estimated gradient direction. Experiments on large-scale benchmark datasets demonstrate that GSBAK offers state-of-the-ee -ot performance and would be strong baseline in crafting top-K adversarial examples.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work was supported in part by the US National Science Foundation under grants CNS-1824518 and
T. Wu partly supported by ARO Grant W91 INF1810295, NSF I1S-1909644,
ARO Grant W91 1 10010, NSF IIS- 1822477, NSF CMMI-2024688 and NSF IUSE-2013451.
R. Jin supported by the National Key R&D Program of China under Grant No. 2024YFE0200004.
The views and conclusions expressed in this work are those of the authors and do not necessarily reflect the official policies or endorsements, either expressed or implied, of ARO, NSF, or the U.S.
Government. The U.S. Government is authorized to reproduce and distribute reprints for Govern- mental purposes not withstanding any copyright annotation thereon. The authors sincerely appreci- ate the constructive feedback provided by the anonymous reviewers and area chairs.
REFERENCES
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square at- tack: a query-efficient black-box adversarial attack via random search. In European conference on computer vision, pp. 484-501 Springer, 2020.
Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box attacks deep neural networks using efficient query mechanisms. In Proceedings of the European conference on computer vision (ECCV), pp. 154-169, 2018.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. In International Conference on Learning Representations, 2018
Thomas Brunner, Frederik Diehl, Michael Truong Le, and Alois Knoll. Guessing smart: Biased sampling for efficient black-box adversarial attacks. In Proceedings of the IEEE/CVF Interna- tional Conference on Computer Vision, pp. 1958,4966, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium security and privacy (sp), pp. 39-57. lece, 2017.
Jianbo Chen, Michael I Jordan, and Martin J Wainwright. Hopskipjumpattack: A query-efficient decision-basee attack. In 2020 ieee symposium on security and privacy (sp), pp. 1277-1294.
IEEE, 2020.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop artificial intelligence and security, pp. 15-26, 2017.
Shuyu Cheng, Yinpeng Dong, Tianyu Pang, Hang Su, and Jun Zhu. Improving black-box adversarial attacks with a transfer-based prior. Advances in neural information processing systems, 32, 2019.
Francesco Croce and Matthias Hein. Sparse and imperceivable adversarial attacks. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 4724-4732, 2019.
Francesco Croce, Maksym Andriushchenko, Naman D Singh, Nicolas Flammarion, and Matthias Hein. Sparse-rs: versatile framework for query-efficient sparse black-box adversarial attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6437-6445, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, 2009.
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boost- ing adversarial attacks with momentum. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 9185-9193, 2018
Yinpeng Dong, Hang Su, Baoyuan WI, Zhifeng Li, Wei Liu, Tong Zhang, and Jun Zhu. Effi- cient decision- based black- box adversarial attacks on face recognition. In Proceedings of the IEFF/CVF Conference Computer Vision and Pattern Recognition, pp. 7714-7722, 2019.
11

---

Published as a conference paper at ICLR 2025
Mark Everingham, SM Ali Eslami, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes challenge: A retrospective. International journal of computer vision, 111:98-11111 136, 2015.
Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A Wichmann, and Wieland Brendel. Imagenet-trained cans are biased towards texture; increasing shape bias im- proves accuracy and robustness. arXiv preprint arXiv:/811.12233 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Chuan Guo, Jared S Frank, and Kilian Q Weinberger. Low frequency adversarial perturbation. arXiv preprint / 08778,, 2018
Chuan Guo, Jacob Gardner, Yurong You, Andrew Gordon Wilson, and Kilian Weinberger. Simple black-box adversarial attacks. In International Conference on Machine Learning, pp. 2484-2492 PMLR, 2019a.
Yiwen Guo, Ziang Yan, and Changshui Zhang. Subspace attack: Exploiting promising subspaces for query-efficient black-box attacks. Advances in Neural Information Processing Systems, 32, 2019b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Dan Hendrycks, Norman Mu, Ekin D Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshmi- narayanan. Augmix: A simple data processing method to improve robustness and uncertainty. arXiv preprint arXiv: 1et.::2112..811111 2019.
Shu Hu, Lipeng Ke, Xin Wang, and Siwei Lyu. Tyml-ap: Adversarial attacks to top-k multi-label learning. Proceedings of the IEEE/CVF International Conference on Computer Vision, pp- 7649-7657, 2022.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International conference on machine learning, pp. 2137- 2146. PMLR, 2018a.
Andrew lyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. arXiv preprint arXiv:1807.07978, 2018b.
Jinyuan Jia, Wenjie Qu, and Neil Gong. Multiguard: Provably robust multi-label classification against adversarial examples. Advances in Neural Information Processing Systems, 35:10150- 10163, 2022.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint 1xXiv:661.00125: 2016.
Huichen Li. Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query-efficient boundary- based blackbox attack. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1221-1230, 2020a.
Jie Li, Rongrong Ji, Hong Liu, Jianzhuang Liu, Bineng Zhong, Cheng Deng, and Qi Tian. Projection & cibaability-driver black-box attack. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pp. 362-371, 2020b.
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 decision- based black-box models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 16168-16177, 2021.
Maosen Li, Cheng Deng, Tengjiao Li, Junchi Yan, Xinbo Gao, and Heng Huang. Towards transfer- able targeted attack. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 641-649, 2020c.
12

---

Published as a conference paper at ICLR 2025
Yanjie Li, Bin Xie, Songtao Guo, Yuanyuan Yang, and Bin Xiao. A survey of robustness and safety of 2d and 3d deep learning models against adversarial attacks. ACM Computing Surveys, 56(6): 1-37, 2024.
Yujia Liu, Seyed-Mohser Moosavi- Deosavi-Dezfooli, and Pascal Frossard. A -iinerr--nnspiee decision- based attack. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp- 4890-4898, 2019.
Chen Ma. Xiangyu Guo, Li Chen, Jun-Hai Yong, and Yisen Wang. Finding optimal tangent points for reducing distortions of hard-label attacks. Advances in Neural Information Processing Sys- fems, 34:19288-193000 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:170.00600 2017.
Hassan Mahmood and Ehsan Elhamifar. Semantic- multi-label adversarial attacks. In Pro- ceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 24251- 24262, 2024.
Thibault Maho, Teddy Furon, and Erwan Le Merrer. Surfree: a fast surrogate-fre free black-box attack. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 10430-10439, 2021.
Scyed-Mohsen Doosavi-Dezfooliy Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 2574-2582, 2016.
Thomas Paniagua, Ryan Grainger, and Tianfu Wu. Quadattack: A quadratic programming approach to learning ordered top-k adversarial attacks. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Ali Rahmati, Seyed-Mohsen Moosavi-Dezfooli Pascal Frossard, and Huaiyu Dai. Geoda: a geo- metric framework for black-box adversarial attacks. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 8446-844 0466-8855,11 2020.
Md Farhamdur Reza, Ali Rahmati, Tianfu Wu, and Huaiyu Dai. Cgba: Curvature-awan geometric black-box attack. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 124-133, 2023.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 14X.v 2014.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-288882 28262 2016.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint 2017.
Chun-Chen Tu, Paishun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder- based zeroth order optimization method for attack- ing black- neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 742-749, 2019.
Nurislam Tursynbek, Aleksandr Petiushko, and Ivan Oseledets. Geometry-inspired top-k adversarial perturbations. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 3398-3407, 2022.
13

---

Published as a conference paper at ICLR 2025
Kunyu Wang, Xuanran He, Wenxuan Wang, and Xiaosen Wang. Boosting adversarial transferability by block shuffle and rotation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 24336-24333 2024.
Xiaosen Wang and Kun He. Enhancing the transferability of adversarial attacks through variance tuning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1924-1933, 2021.
Xiaosen Wang. Zeliang Zhang, Kangheng Tong, Dihong Gong, Kun He, Zhifeng Li, and Wei Liu. Triangle attack: A query-efficieet decision-based adversarial attack. In European Conference Computer Vision, pp. 156-174. Springer, 2022.
Zhipeng Wei, Jingjing Chen, Zuxuan Wu, and Yu-Gang Jiang. Enhancing the self-universality for transferable targeted attacks. In Proceedings of the IEEE/CVF conference on computer vision and paltern recognition, pp. 12281-12290, 2023.
Jiancheng Yang, Yangzhou Jiang, Xiaoyang Huang, Bingbing Ni, and Chenglong Zhao. Learning black-box attackers with transferable priors and query feedback. Advances Neural Information Processing Systems, 13:11228-12299 2020.
Zekun Zhang and Tianfu Wu. Learning ordered top-k adversarial attacks via adversarial distilla- tion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 776-777, 2020.
14

---

Published as a conference paper at ICLR 2025
Appendix
In this supplementary material, we provide the rationale for the design of proposed gradient esti- mation techniques for complicated top-K scenarios in Appendix A Additionally, we conduct an ablation study to assess the impact of non-adversarial queries on gradient estimation, and the influ- ence of gradient-based initialization performance, which are also discussed in Appendix [ The additional results showing the comparison of the proposed GSBA* 2 with top-/ baselines are given in Appendix B while the performance comparison between GSBA and SA against ResNet- (He et al.. 2016) and VGG-16 (Simonyan & Zisserman 2014), and several robust single-label multi-class classifiers can be found in Appendix [ and Appendix D respectively. The impact of larger K on the performance of GSBAK K is reported in Appendix E A brief discussion of the noise sampling pro- cess from fow-dimensional frequency space presented in Appendix [ while potential negative impacts and limitations of GSBA are covered in Appendix G Finally, number of crafted adver- sarial examples against single-label multi-class classification and multi-label learning are depicted in Appendix H
A ABLATION STUDY
In this section, present ablation study analyze the design of the proposed gradient estimation techniques presented in Eq. 9 and Eq. 12 which estimate gradients within the adversarial regions and on the decision boundary, respectively, for the top-K targeted attack. We also examine the influence of non-adversarial queries on gradient estimation at the decision boundary and how this influences the performance of the proposed attack. Furthermore, demonstrate that our gradient- based initial boundary- -onndiin--inding method significantly improves attack performance when compared to random boundary point initialization.
A.1 DETAILED BREAKDOWN OF EQ.
Finding good initial boundary point Tby for the targeted attack is difficult task it requires satisfying the constraint DK (2%)) ) = ()(() In this section, we analyze how each component Eq, contributes gradient estimation at point æho, inside the -oversaeraarall region to locate Tb, for the targeted attack. To evaluate the effectiveness it with alternative possible methods for estimating the gradient whoy providing justification for the selection of our proposed approach.
the proposed gradient estimation, we also compare
Method-1:
The gradient at oie can be estimated by comparing the prediction probabilities for z/ with those of the perturbed queries around it. The gradient estimation is give by:
Ja
9a
min Py(ar, =;) min Py((b))) Z;- JEVR
(14)
jEyK
In this method, estimate 9ai, by comparing the minimum prediction probabilities of the tar- get classes at at,, with the minimum of those due to the added noise. The positive difference of mey (ar, + 2;)= - min jey? ()(,)) ensures the increased confidence of the target class with minimum confidence.
Inspired by the CW (Carlini & Wagner 2017) adversarial objective, another possible approach could as follows:
Method-2:
Io
Jw
[Lah/ +2,) I(xrhn)) 2i-
(15)
where L(x(,,) min c (m( -mmx maxxgy((! Po(axh)). This formulation leverages the difference between the minimum probability among the target classes and the maximum probability of non-
max
target classes calculate the gradient.
This method is solely based on only considering the impact of the first weight factor, Exergo Xee, e,,,, in Eq. 9 which counts the number of target classes with increased confidence
Method-3:
when Pai, (z.) 1, or the number of target classes with decreased confidence when daat, (z:) =
15

---

Published as a conference paper at ICLR 2025
Table Caparison of different gradient estimations with the proposed gradient in Eq. initial boundary for top-K K targeted attacks.
to locate the
Grad Estimator
&2 (median)
Q (mediian)
Eq (meun))
Q (mean)
Method-1
9.82
1802.50
10.01
2131.12
Method-3
2439.00
top
Method-4
9.82
1802.50
10.01
2131.12
Pruposed
9.82
1802.50
10.01
2131.12
Mothod-1
12.17
2950.50
12.64
3439.31
Method-3
12.74
3074.50
top
Method
11.98
2733.50
12.59
3429.07
Proposed
12.12
2750.50
12.57
3352.49
Method-1
14.06
4258.00 3.800
14.83
4920.10
Method-3
14.12
4159.50
14.76
4899.33
top-3
Mothod-4
14,01
4175.00 50.00
14.71
4753,59
Proposed
13.70
3896.00
Method-1
17.20
5818.00
26.99
6862.56
Method-3
16.10
5151
16.77
$995,36 36
top-4
Method-4
16.60
5322.00 202000
17.28
6505.00 02
Proposed
15.24
4640,00
5666.69
Method-1
19.68
20.27
9153.95
Method-3
17.39
6057,00
18.77
7305.30
top-5
Method
18.06
6779.00 90000
19.12
8364.68
Proposed
17.14
5709.50
18.03
7042.50
-1. Using only this factor, the gradient is estimated as:
9who oE)if
Xx cize)) Peci (zi)
Z2:
(16)
where the indicator function Qmh, (z:) is defined in Eq.
Method-4: This method focuses on the second weight factor Eeeyg W ,c,,; Xar o, Eq. estimate the gradient at a/1.. It computes the weight associated with 2; by summing the changes in
prediction probabilities of the classes e yitt) either with increased confidence when Pai, (2,)
or with decreased in confidence when Dai, (2,) 11 The gradient estimation using Method-4 is given follows:
Io
g0%
Wayy e.z. Xx o.2. zi.
(17)
CE
Comparative analysis. We compare the performance of the aforementioned gradient estima- tion methods with our proposed gradient estimation to show its effectiveness in finding the initial boundary Tbg- To conduct the comparison, we randomly selected 100 test samples from the Im- ageNet (Deng et al. 2009) dataset and measured the median and mean query counts required to locate Th, as well as the median and mean l--distance of obtained boundary points from the cor- responding source images by performing attacks against ResNet50 (He et al. 2016). The results are demonstrated in Table 3 We exclude Method-2 which is based on CW adversarial objective, as experimentally it is observed that it often fails find Th, in aggressive top-K setting. This is because L(x',, + 2;) - L(x'))) > 0 doesn't mean that it increases the confidence towards the adver- sarial reason, and vice versa. One possible reason among numerous reasons of failure of Method-2 could be, because of the added z, with 2b,,> while min cE>!!) Po(x', + 2;) s min cEy(! Pa(2%,)) egyto (a(,,)) along with an enhanced confidence among classes max og>(() Pa( + ++) max
[C] (2 that doesn't 't meet the goal to find the direction to enhance the confidence towards the adversarial region.
In the top-/ setting, Method-1, Method-4 and the proposed gradient estimation offer the same strong performance locating the initial boundary, as these methods converge to the same ex- pression this setting. However, from Table 3 the efficiency of Method-1 diminishes as K in- creases. The performance deterioration is because Method-1 compares min ceiio Pa(ao, + z,)
16

---

Published as a conference paper at ICLR 2025
and min cey() p.( but fails account for the influence of z; all target classes ) In contrast, Method-3 and Method-4 incorporate the impact of z; on each of the target classes. While Method-3 counts the number of target classes with increased (or decreased) confidence when Pai, (2,) = 1 (or Pmi (z,) = -1), Method-4 considers the strength of these classes. As demonstrate in Table B] the query efficiency of Method-3 increases with higher K, and the Method-4 is query efficient than Method-1 in locating Tho for K > 1. Nevertheless, the proposed gradient estimation method, which takes account of both Method-3 and Method-4, demonstrates superior performance in locating the initial boundary Zbo-
A.2 DETAILED BREAKDOWN OF EQ. 12
The proposed gradient estimation for the top-K targeted attack decision boundary point, Lb... involves two key components: the count of target classes with increased (or decreased) confidence Eeerge Sar,, and the sum of the increased (or decreased) prediction probability of these classes presented as ΣeEv(!) Wmy, ,0,;; Sm,,, ..z, if the query is adversarial (or non-adversarial) Before delv- ing into the impact these components on attack performance, we explore alternative possible gradient estimation approaches.
Approach 1: In this scenario, we consider more challenging setting for the gradient estimation, where an adversary only knows whether query is within the adversarial region without obtaining prediction probabilities from the classifier as employed by CGBA (Reza al. 2023). The estimated gradient on Us in this challenging setting is expressed as:
9 JabE
( 2 24-
(18)
Approach 2:
In this approach, the adversary has access to prediction probabilities of all the classes, and the gradient estimation is done by summing the changes in predictions of all the target classes in K- The gradient estimation using this approach is given
In
gw... i=1
Wenn, C.2. 2s:
(19)
where War,, ..:;; the aggregated change across 10(() is higher.
Pa(o,. + 2;) - Pa(oo...) ) is defined Eq. More weight assigned to 2,,
Approach 3:
To estimate the gradient at the boundary point Wh,,, we may compare the minimum
confidence among the target classes in ):(() at Db. with that of the queries around it by adding noise 2; Ct.,, and it can be represented as:
In
min Po(xo, + 22) - min Pa(2xo.)) zi.
(20)
cEvie
cE>t
This gradient estimator estimates the direction to enhance the minimum confidence among y)())
Approach 4: Having the access to the prediction probabilities of all the classes, the misclassifi- cation objective of the popular Carlini-Wagner (CW) (Carlini & Wagner 2017) can be adapted to estimate the gradient at Lte for the top-K attack, and is given as follows:
min Pa +2)) max Pe + zi)) 21- CE
Jan.
(21)
cg
The CW adversarial objective in optimizing the 2--morm of perturbation is originally given in-terms of logits L of the classifier that is related with the prediction probabilities for a given input æ as: P(x)= softmax([(z)) With the access of logits, Eq. [1] be rewritten as:
Approach 5:
min Lab + 22) cEy1)
max Le(2o, + 21)) zi- cE>
(22)
17

---

Published as a conference paper at ICLR 2025
Auraaa Agaroes3 feroraa
100
300
Moard Weaddomaatr
10 COCO
faamati
pider
28
0000
1000
400 BAQ
260
40.0
10xc Qaattc
10.02
2000
10.0
Quatia
Querio
(a) top-1
(b) top-2
(c) top-3
(d) top-4
Figure 7: Comparing the variation of f2-norm of perturbations with queries of different gradient estimation approaches on the decision boundary with our proposed gradient estimation in Eq. 12 in crafting diverse top-K targeted adversarial examples.
Approach 6:
Considering only the first component of the weight to z; in Eq. 12 the estimated
gradient can be expressed as:
Jæhn Σ
Σ C.......)) 12bb, z1) Z/
(23)
OEVI
where Eeerg Sans, ..zz counts the number of target classes with increased (or decreased) confi- dence towards the adversarial region if the query æs.,, + z; is adversarial (or non-adversarial).
Approach 7:
In this case, we consider the second component of the weight to z; in Eq. which
aggregates the changes in confidence of the classes D such that ,,,, 1, to estimate the gradient at Ts,,, Thus,
9 Jah.
Wann c,z. Sen,,,,,,
(24)
CE
Comparative analysis. We present a comparative analysis of the aforementioned gradient esti- mation approaches with our proposed gradient estimation, as expressed in Eq. [2] on the decision boundary for targeted attacks. To facilitate the comparison, the ImageNet (Deng et al., (2009) dataset and perform attacks against the popular pre-trained ResNet- 50 (He et al.] 2016) classifier. For a particular top-K and a source image, all the attacks using different estimation techniques start from same randomly chosen initial boundary point.
randomly choose 100 images from
In Fig. 7a it evident that all attacks utilizing prediction probabilities for gradient estimation out- perform Approach-1, which solely relies on the classifier's 's decision to estimate the gradient for craft- ing top-/ adversarial examples.
this top-/ setting, the gradient estimation with Approach-6 closely resembles that of the decision-based (Approach-1) 1). The weight associated with using Approach-6 reduces to (Smy, 1 (x + 2:)) E (-1, O, 1), where y/ is the target label. The key advantage of gradient estimation using Approach-6 is that it excludes anomalous queries those non- adversarial but increase the confidence toward the target class, and vice versa. In multi-class classifi- cation problems, there might be scenarios, for target class yı, though Py, (ars,, +22;) -Pp))pPp (ars..) O, the query as, + z; is still aon-adversaria (Pa (Pr(ar,, + z;) > Py, (æa., + +2;) for a E [C] {ve }). Since the decision-based approach (Approach-I) treats all queries equally by assigning unit absolute value weights of either -1 or to z; based on whether a query is adversarial, irrespective of considering the discussed phenomenon, the inclusion of anomalous queries negatively impacts the performance of the attack using it.
In the top-1 setting, attacks with Approach-2, Approach-3, Approach-7, and the proposed gradi- ent estimation offer quite strong performance. Approach-2 and Approach-3, essentially reduce to the same expression in top-1 setting, account for all queries by evaluating the increase or de- crease in confidence toward the target class from the decision boundary, using this change in confidence as a weight for z,. Both Approach-7 and the proposed method (essentially both re- duce to the same expression under top-1 setting) also assign weights based on the change in confidence, similar to Approach-2 and Approach-3, but they exclude anomalous queries. How- ever, Approach-2 and Approach-3 still perform comparably to the proposed gradient estimation method, as the weights associated with the anomalous queries are relatively small. Now, turn- ing to 4pproach-4 and Approach-5, which are based on CW adversarial objective, gradient esti-
18

---

Published as a conference paper at ICLR 2025
mation using these approaches is not optimal. With these approaches, on the decision boundary, min cErg Pe + =2i max cg (o. + z;) > 0
( + z;]), and vice versa. Thus, there no difficulties with anomalous queries. The possible reasons behind this sub-optimal performance by these approaches because the weights that are calculated based on the difference between the minimum prediction score among the target classes and the maximum prediction score among the other classes. This weighting does not accurately reflect the increase in confidence toward the target class from the decision boundary, leading to less effective gradient estimations.
Turning to Figs. 7b 7c and 7
we observed that when K > 1, Approach-2, which sums the changes in prediction probability across all target classes in K performs well for top-/ attacks but suffers a significant performance drop, even bellow Approach-1, when K increases. The degradation in performance for Approach-2 is attributed to the fact that the likelihood of Eceyie Wæs.o, >
when the query Ib,, + 2, is adversarial decreases with the increase of K, while the expectation with an adversarial query. the weight assigned to 2, should be positive. Consequently, as K grows, gradient estimation with Approach-2 becomes less accurate and struggles to converge. Like- wise, Approach-3 also suffers from a similar performance drop with K. This is because, on the decision boundary, the difference between min c (T + z,) and min minogy (T does
not carry too much information of whether the query 2b,, + x; is adversarial. The probability of min ce>y() (x x4) min CE>T Pe(x),.) > 0 when a query is adversarial reduces as well with higher K using this approach that enhances the likelihood of the anomalous queries. Approaches based the CW adversarial objective, such as Approach-4 and Approach-5, continue to exhibit sub-optimal performance for higher K due to the issues previously discussed.
For Approach-6 and Approach-7- where Approach-6 counts the number of target classes with in- creased (or decreased) confidence if the query is adversarial (or non-adversarial), and Approach-7 sums the confidence increases (or decreases) for these classes while Approach-6 consistently out- performs all other aforementioned approaches for higher K, Approach-7 outperforms those when K is smaller. For a query at Tb, with added z; on the decision boundary, these approaches focus on the impact of z; on each of the target classes rather than looking at whole. For example, they do not consider the impact of z; on the class arg min CE
Po (ar + z:). but all classes in y>((). They
assign more weight to 2, in estimating gradient, if it impacts more target classes. By incorporating the indicator function (,,,, they exclude queries that are adversarial but do not positively impact any )x(e) Notably, our proposed gradient estimation method, which integrates the strengths of both Approach-6 and Approach-7, outperforms all other approaches when K > 1.
A.3 IMPACT OF NON-ADVERSARIAL QUERIES
The proposed GSBAK calculates gradients by incorporating both adversarial and aon-adversarial queries. When estimating gradients at a boundary point Tb,,, if query Byg = Es., + 2; is non- adversarial due to added noise 2; GSBA incorporates this noise by inverting it and scaling it with the absolute value of the weights assigned z; in Eq. 12 for targeted attacks and Eq. B3 for untargeted attacks. Eq. 13 can be rewritten as follows:
9 Ja
Fan, +2 1(66, + 2:)2.
(25)
Likewise, Eq. 12 can be rewritten as:
ga....
G 1.))
Warn a. Say, c, (Drb. + 2:)2..
(26)
Fig. |cooparess the performance of the proposed attack in crafting top-/ adversarial examples when estimating gradients using both adversarial and aon-adversarial queries versus considering only ad- versarial queries for both untargeted and targeted attacks. These experiments are conducted against
the 5e (He et al. (0116) classifier using 100 correctly classified images from ImageNet (Deng et al. 2009). While Fig. Sa and Fig. Se/depict the obtained median fn-norm of perturbation for differ- ent query budget for untargeted and targeted attacks, respectively, Fig. [b and Fig. [dd] demonstrate the corresponding attack success rate (ASR) with perturbation threshold rus 2 and Tth.
19

---

Published as a conference paper at ICLR 2025
Wiltorr ranell surl
ASR050
Anthor serodh
Withor nor
Query halgs
Quary budge.
(a) Untargeted (b) Untargeted, PrA = (c) Targeted
(d) Targeted, Pth -4
Figure 8: Impact of non-adversarial queries in estimating the gradients at decision boundary on crafting top-/ untargeted and targeted adversarial examples against ResNet-50.
for untargeted and targeted attacks, respectively. The results clearly demonstrate that incorporating both adversarial and aoverrverlll queries in gradient estimation results in improved performance compared to not considering non-adversarial queries in gradient estimation.
A.4 IMPACT OF GRADIENT-BASED SEARCH FOR INITIAL BOUNDARY POINT
Geometric attacks start by finding an ini- tial boundary point and then iteratively duce the perturbation by utilizing the decision boundary's 's geometry. In literature, untargeted decision-based attacks find the initial bound- ary point in a random direction, while targeted attacks find it by using BinarySearch be- tween the source and an image with the target class. Instead of employing random direction or binary search to locate the initial boundary point, the proposed GSBAK employs the es- timated gradient direction for both untargeted and targeted attacks. Fig. [9] demonstrates the significant improvement in the median mo-m
Binory Search Gradiem: based
Mediun fa pertutnation
40
Mediun perturatton
80-
30
600
20
26
2500
10000 Mudiinuurries
Modian queries
(a) Untargeted
(b) Targeted
Figure 9: Impact of gradient-baa based initialization against ResNet-50.
of perturbation in crafting 100 top-/ adversarial examples against the ResNet-50 classifier using the gradient-base based initial boundary finding approach for both untargeted and targeted attacks.
FFEA
P98A
058A
OZEA!
0006
2006
1000 1083 2003
1000 1203 2008
1000 2000 2003 RO0CE
10000
2009
(a) 2, Untargeted
(b) Pia = 4. Untargeted
(c) 4, Targeted
(d) Pza. = 6, Targeted
Reahee3333
Realves-00
058A
053A)
053A
C5RA
(e) Tea 2, Untargeted
(i) rsh 4, Untargeted
(g) Teh = 4, Targeted
(h) Teh = 6, Targeted
Figure 10: ASR(%) versus queries in generating top-/ adversarial examples for different pertur- bation thresholds utilizing GSBAL and baseline attacks against single-label multi-class classifiers 1GG-16 and ResNet- on ImageNet. GSBA' outperforms the baselines for both the untargeted and targeted attacks.
20

---

Published as a conference paper at ICLR 2025
Table 4: ASR(%) for different perturbation thresholds (rth) and query budgets against VGG-16.
Attack Type
Untargeted Attack
Targeted Attack
Queries
1000
5000
10000
20000
30038
5000
T00000
20000
30000
40000
SA'
2488
49.8
62.4
72.5
77.8
1.8
7.0
15.1
24.4
29.8
Tza=1
Tra=2
GSBA
31.1
64.0
83.0
90.1
91.0
11.2
28.0
52.0
63.4
71.0
SA
Fea=2
49.6
77.7
89.9
94.0
96.3
17.9
36.4
58.2
69.1
74.5
GSBA
50.1
91.0
98.0
99.1
99.1
76.6
94.4
97.1
99.0
SA
79.2
95.9
98.1
99.3
99.8
38.9
62.5
78.6
84.7
88.8
GSBA
85.9
97.9
99.0
99.2
100.0
T1A-6
74.7
93,9
99.5
100.0
100.0
GSBA
rox-1
14.0
9.8
27.9
42.1
40.3
61.1
72.1
54.0
79.0
59.7
TrA-2
11.7
1.8
29.3
5.4
40.8
10.9
47.3
14.1
SA"
rua=2
29.1
59.4
74.1
83.9
87.9
7.5
18.3
35.2
44.6
49.7
GSBA-
37.0
79.9
94.0
97.1
99.0
25.7
50.6
75.0
85.6
89.8
VGG-16
SA
62.0
89.7
95.3
97.3
96.3
21.6
37.3
55.7
63.4
67.0
GSDA*
Tea
63.0
97.0
97.1
99.0
100.0
47.7
74.6
93.0
95.1
96.0
4.9
15.5
26.5
40.5
45.6
0.8
2.4
GSBA
Tokml
7.9
33,1
49.9
69.0
72.1
TrA=2
1,5
5.8
17.5
24.7
33,2
SA
17.8
46.7
62.6
74.8
81.0
4.2
11.9
22.4
29.2
32.4
==a=2
87.1
95.1
97.1
32.7
59.2
70.2
76.0
SA
50.4
82.8
91.9
96.0
97.3
12.9
24.8
36.0
42.1
47.0
GSBA'
rea 4
52.1
93.0
97.0
98.0
99.0
Yea
26.8
57.1
74.9
83.2
86.3
SA*
2.3
12.7
20.4
33.3
38.5
0..3
1.6
3.9
5.1
GSBA'
roa=1
4.0
23,0
41.9
57.1
62,0
M/A=2
3,6
11.4
16.2
20.6
SA'
ru-=2
13.0
41.8
53.9
69.4
75.9
2.3
5.9
13.4
19.1
21.3
GSBA*
15.1
58.0
79.0
92.9
93.9
18.1
40.2
53.2
60.8
SA*
45.4
78.0
88.7
95.2
96.3
15.7
23.6
31.0
32.8
GSDA!
42.0
89.1
95.9
97.9
98.1
15.0
37,8
60.9
69.7
75.4
Table 5: ASR(%) for different perturbation thresholds (rta) and query budgets against ResNet-100)
Attack Type Queries
Untargeted Attack
Targeted Attack
1000
5000
10000
200000
30088
5000
T0X000
20000
30000
40000
SA'
27.3
44.7
52.6
61.8
65.5
3.8
6.8
14.1
21.4
25.7
GSBAA
=1a=1
28.2
59.6
72.8
83.4
85.4
rta==
23.0
44.9
59.7
67.9
SA
Feam2
47.3
71.2
81.1
88.9
91.2
17.4
34.3
54.4
64.7
69.4
GSBA
49.1
83.5
93.0
97.5
98.8
32.7
65.7
90.0
96.4
98.0
SA'
73.0
99.2
35.2
55,9
78.8
86.1
90.8
GSBA
70.9
95.7
99.4
99.8
100.0
F(A
58.5
88.6
97.7
99.6
99.7
GSBA
Tox-1
11.4
11.3
24.5
38.6
52.9
32.6
43.0
67.9
73.3
44.0
TrA-2
1,2
8.9
2.6
24.1
5.8
34.8
8.7
11.1
42.0
1np-2
SA"
27.7
53.1
63.4
73.4
77.7
7.2
14.3
28.2
39.2
46.5
=2a=2
RosNer- 101
GSBA
27.8
66.2
82.5
94.0
96.0
14.8
38.5
67.9
79.4
87.7
GSDA
SA²
Tea
54.9
48.3
82.6
87.7
91.2
95.8
99.4
96.7
99.6
97.7
T6-=6
29.8
14.5
61.7
30.9
52.7
88.6
62.1
95.0
68.1
96.9
SA'
6.4
17.3
26.3
35.6
40.5
0.9
1.4
2.7
4.1
4.8
Toaml
r(Am2
GSBA
6.6
28.7
42.4
58.8
66.6
4.6
12.5
21.1
28.7
SA"
19.8
41.5
52.8
63.3
68.1
3.3
7.2
15.2
20.3
22.9
=2a=2
GSBA
16.6
55.3
74.9
88.2
92.1
23.7
47.6
61.2
72.2
SA*
43,0
74.0
92.2
94.4
16.7
29.7
38.9
43.7
GSBA
rax-4
38.2
81.8
94.1
98.3
99.5
T(A-6
16.7
41.4
72.7
83.6
89.6
SA
3.8
12.0
17.0
23.1
36.2
0.8
1.3
2.1
2.9
GSBA*
Tea=1
3.4
20.9
35.6
50.2
$8.4
1.4
6.7
12,2
16.9
SA
Faa=2
13.6
35.6
46.3
58.4
62.6
1.5
5.0
8.1
11.8
14.8
GSBA*
11.9
47.4
69.3
83.4
88.5
12.5
30.5
44.8
53.5
SA
38.3
68.3
79.5
87.9
92.5
9.3
17.3
22.7
28.3
GSDA'
T4am4
31.8
74.6
90.4
97.2
98.5
8.0
25.3
53.2
70.1
78.7
B COMPARISON WITH top-1 BASELINES
Fig. T0 depicts the variation of ASR with differing query budgets across various Y'g, values, com- paring the performance of GSBA' with the basclines SimBA-DCT (Guo al., 2019a)). PPBA (Li et al. 2020b) and SA (Andrushchenkoo et al.) 2020) in generating top-7 untargeted and targeted ad- versarial examples against the VGG-16 (Simonyan Zisserman, 2014) and ResNet- 101 (He al.) 2016) single-label multi-class classifiers on the ImageNet dataset (Deng et al.) 2009). The depicted curves are derived from 1000 randomly selected samples correctly classified by the respective clas- sifier. From this figure, GSBA shows significantly better ASR in crafting adversarial examples with small perturbation thresholds for untargeted attacks. For targeted attacks, on the other hand, the proposed GSBA' outperforms the baselines by considerable margin in ASR performance. The obtained ASR against VGG- 16 and ResNet- 101 quite similar to the one obtained for ResNet-50, as demonstrated in the main paper.
21

---

Published as a conference paper at ICLR 2025
VGG-16
2
VG 16-4
100
100
30
30
30
ASR(%))
ASR110
ASR(15
40
561
GS384
-0
5.4
GS38
-0-
561
GS88
GSSK"
544
GSSK'
GS
6584
GSBX
GSSK'
SM
GSBA'
GSBA'
0-
10009
20000
15000
10503
20000
Query budggt
Query budges
Query budget
(a) Untargeted
(b) Untargeted
(c) Untargeted
VGG-16
VGG-16 /m
VGG-16 1 06=6
100
S4
80
80-
50-
SA
ASR1%)
3A1
ASR
ASR0P9
GSBA
GSBA
658A'
54'
65BA
SA
6536
S4
6SBA!
10000
20000
30000
40000
10000
20000
30000
40300
10000
20000
30000
40000
Query budget
Quay budget
Query budget
(d) Targeted
(c) Targeted
(f) Targeted
Figure 11: ASR(%) (%) versus queries in crafting up to top-4 adversarial examples for different pertur-
bation thresholds utilizing GSBA and SA against single-label multi-class classifier VGG-16 16 on ImageNet. GSBA consistently outperforms the state-of-the-art baseline SAK in crafting untargeted adversarial examples, with larger gains when the perturbation threshold is smaller and/or the query budget is larger. Moreover, the relative gain in ASR of GSBA over SA increases with K. For the targeted attack, GSBAK K offers significantly better ASR than SAK across the board.
RseNet-101 Fi 1
RsoNett-11 6
RseNet-101 | Fa
80
30
80
ASR(%)
40
ASKON)
60
ASR
GSBA!
40
65BA
GSBA'
56
GSBA7
GSBA'
20
SM
65341
20
SM
20
5A
GSMA
56
GS3M*
56'
GS3
56
GSM
5000
10000
15200 20000
25003 30000
5000
10000
35200
20000
25003 30000
5000
10000
15-203 20000
25003 30000
Query budget
Query budget
Query budget
(a) Untargeted
(b) Untargeted
(c) Untargeted
RsoNet-101 r
RseNet-101 -4
RsoMet-101 101
100
100
S64
658
SA
6SBA?
ASR(%)
40
SA
65BA!
ASR(%)
60
AS30%
20
542
5.2
658A2
20
20
562
20-
542
GSBA
10000
20000
30000
40000
10000
20000
30000
40002
10000
20000
30000
42000
Query budgot
Quary budget
Query budget
(d) Targeted
(e) Targeted
(f) Targeted
Figure 12: ASR(%) versus queries in crafting up to top-4 adversarial examples for different pertur-
bation thresholds utilizing GSBAK and SA* against single-label multi-class classifier ResNet- 101 on ImageNet. GSBAK consistently outperforms the state-of-the-an baseline SAK in crafting untar- geted adversarial examples, with larger gains when the perturbation threshold is smaller and/or the query budget is larger. Moreover, the relative gain in ASR of GSBAK K over SAK increases with K. For the targeted attack, GSBAK offers significantly better ASR than SAK across the board.
22

---

Published as a conference paper at ICLR 2025
Table 6: ASR(%) by SA and GSBA against different robust classifiers.
Attack
Inc-vAg
IR-12
R
RN50
RN50
4-:5000 rw==
63.0
GSHAI
75.0
SA'
63.0
38.0
50.0
52.0
57.0
GSDA
72.0
54,0
66.0
65.0
54,0
Untorgeted
GSBA'
64.0
44.0
55.0
58.0
44.0
SA'
41.0
26.0
35.0
36,0
20.0
GSBA
55.0
35.0
46.0
33,0
Q=30000 7wa=2
GSBA!
94,0
93.0
97.0
100.0
97.0
SA-
79.0
63.0
78.0
79.0
63.0
GSBAA
91.0
85.0
97.0
73.0
GSBA"
87.0
83.0
9:.00
95.0
86.0
SA'
67.0
49.0
58.0
62.0
44.0
GSBA*
85,0
4=10000 TaES
27.0
15.0
75.0
55.0
GSBA!
62.0
39.0
95.0
93.0
86.0
SA
8.0
8.0
39.0
48.0
24,0
GSBA*
SAP
2,0
4.0
26.0
30.0
15.0
Targeted
GSBA
20.0
13.0
60.0
65.0
42.0
SA"
0.0
5.0
16.0
19.0
10.0
27.0
Q= 7wn
44.0
22.0
94,0
97.0
$7.0
GSBA!
96.0
74,0
100.0
100.0
99.0
SA-
15.0
12.0
79.0
78.0
59.0
SAP
7.0
7.0
61.0
59.0
34.0
GSDA"
46.0
39.0
94.0
95.0
89.0
SA"
4.0
46.0
26.0
GSBA
32.0
25.0
89.0
93.0
80.0
C ADDITIONAL RESULTS FOR top-K ON IMAGENET
Table and Table compares the obtained ASR of SOTA baseline SAK and proposed GSBAK against single-laber multi-class classifiers VGG-16 (Simonyan & Zisserman 2014) and ResNet- 101 (He et al.] 2016), respectively, for both the untargeted and targeted attacks for different query budgets and perturbation thresholds nth in crafting up to top-4 adversarial examples on Ima- geNet (Deng et al., 2009). The corresponding curves demonstrating ASR versus query budgets against VGG-16 and ResNet-101 are depicted Fig. and Fig. 12 respectively.
As can be seen from the results for untargeted attacks, the ASR against VGG-16 and ResNet- 101 closely mirrors our findings against ResNet-50. The performance of the proposed GSBA consis- tently outperforms the state-of-the larger gains when the perturbation threshold smaller and/or the query budget is larger. When the query budget is small, all black-box attack methods are limited, so no significant gain can be expected; on the other hand, when the allowed perturbation threshold is large, the state-of-the-an method already achieves satisfactory performance, Moreover, the relative gain in ASR of GSBAK over SAK increases with K. For the targeted attack, GSBA offers significantly better ASR than SA across the board against VGG-16 and ResNet-101 classifiers, as we have seen for ResNet-50.
score-based attack SA in crafting adversarial examples, with
no significant gain can be expected either.
D PERFORMANCE AGAINST ROBUST CLASSIFIERS
We compare the performance of the proposed GSBA and SAK against several robust classifiers. These include adversarially-traie Inception V3 (Kurakin et al. 2016), ensemble-ad adversarially- Pained-ResSNe--nneetii
V2 (Tramer et al., 2017). and three robustly trained ResNet-50 (RN50): RN50IN (Geirhos al., 2018), RN50 (Geirhos et al. 2018) and RNSO (Hendrycks al. 2019). RN50IN is trained combination of stylized and natural ImageNet, RN50 fine-tuned with an auxiliary dataset and RN50Aux is trained with advanced data augmentation techniques. We assess the performance of these robust models using 100 randomly selected samples from ImageNet for both untargeted and targeted attacks.
Table 6 demonstrates the obtained ASR(%) for query budgets of 5000 and 30000 at a perturbation threshold Fth. = 2 for the untargeted attack, and for query budget of 10000 and 40000 considering the perturbation threshold rza. 8 for the targeted attack. These results show that GSBAK K in the top-
23

---

Published as a conference paper at ICLR 2025
Table ASR against ResNer50 on 100 ImageNet images for different top-K targeted attacks with a
perturbation threshold Lth = 20.
K
10
15
20
ASR(%) %)
100.00 100.00 98.00
69.00
36.00
11.00
Table ASR against ResNet50 on 100 ImageNet images for different top-K untargeted attacks with
perturbation threshold Fth. 20.
20
50
ASR(%) %
100.00 99.00 84.00
71.00
54.00
43.00
30.00
Table 9: ASR against Inception- V3 on 100 PASCAL VOC images for different top-K targeted
attacks considering best target classes with a perturbation threshold rth = 20.
Top-K
3
5
7
ASR(%)
100.00
82.00
61.00
21.00
2.00
setting follows a similar pattern to its performance against standard classifiers. Additionally, from this table, adversarially trained classifiers demonstrate greater robustness than the robustly trained classifiers like RN50TN, RN50mme and RN50
E IMPACT OF LARGER K ON ASR
We conduct attacks with higher values of K to evaluate its impact on ASR. As shown in Table 7 we report the ASR against ResNet50 for targeted attacks, where the top-K predicted labels are replaced by the target classes. Table [ presents the ASR for untargeted attacks on 100 ImageNet images, where the top-K predicted labels of source images are replaced by any K labels other than the top-K source labels. Furthermore, Table 9 illlstrates the ASR variation for top-K targeted attacks on Inception-Ve V3 using 100 images from the multi-label PASCAL VOC2012 dataset. From these results, observe that ASR decreases K increases, with sharper decline for targeted attacks. This trend suggests that the proposed black-box attack, which lacks knowledge of the target model, becomes ineffective K approaches the extreme of K C/2 under the perturbation constraint, where C' is the total number of classification labels.
Table 10: Median fn-m of perturbations (lower is better) for different query budgets and different dimension reduction factors for top-2 targeted attacks on 100 ImageNet images against ResNet50.
4
6
40400
15.82
12.55
11.74
9.29
11.72
10.22
Q=8000
10.30
8.47
7.05
5.72
6.40
6.92
Table 11: ASR(%) with r'n 20 for different query budgets and different dimension reduction
factors for top-2 targeted attacks on 100 ImageNet images against ResNet50.
2
3
4
6
8
Q=4000
47.00
59.00
64.00
72.00
66.00
68.00
Q=8000
89.00
94.00
95.00
99.00
97.00
96.00
F SAMPLING NOISE FROM LOW-FREQUENNC SUBSPACE
The low-frequency subspace obtained through Discrete Cosine Transformation (DCT) is crucial because it captures essential image information, including the gradient information (Guo et al. Li et al. 2020a), which are vital for our approach. To sample a noise z; E [0, 1,, from low-frequency subspace, the coefficients of the low-frequency components with dimension C₁ C2 W. // are drawn from normal distribution with zero mean and 0.0002 standard deviation x x
2018
while setting the remaining frequency components to zero, and then revert this representation back to the original image space using the Inverse DCT, as discussed in (Guo et al. 2018). This process effectively allows us to generate perturbations that influence the more critical, low- frequency aspects of the image. minimizing disruption to the less important high-frequenn details. The parameter f serves dimension reduction factor, controlling how much of the frequency space is retained in
24

---

Published as a conference paper at ICLR 2025
the noise sample. For instance, if the dimension of an image is 3 224 224, the dimension of the www-freuency space with dimension reduction factor f 4 would be 9408. This corresponds to selecting 6.25% of the frequency components. We choose the dimension reduction factor as f = 4 for all our experiments following (Reza et al. 2023 [i et al. 2020a). The median fn-nrrm of perturbations and ASR for different query budgets and different dimension reduction factors for targeted top-2 attack on 100 images are reported in Table [10 and Table II respectively, which
conforms with the finding in (Reza al. 2023) even for top-2 attacks.
G LIMITATIONS AND POTENTIAL NEGATIVE IMPACTS
Limitations: The proposed GSBA based querying the target classifier craft adversarial examples, and it offers query-efficient performance as compared to the baseline attacks. However, crafting top-K adversarial examples, particularly for targeted attacks with larger values K, still demands significant number of queries, leaving ample room for further improvement. Moreover, the designs of our untargeted and targeted attacks are based on the assumption of low curvature and high curvature decision boundaries, respectively. However, while the curvature is high when the boundary point is far from the source image, it tends to become flatter as the boundary point comes closer to the source image from the viewpoint of the source image. Additionally, attack proceeds with optimizing boundary points on the decision boundary, poor transferability is incurred due the variation of decision boundaries across classifiers. Thus, more accurate gradient estimation technique along with adaptive boundary point search can be a future endeavor to improve the performance further. Additionally, efforts can be made to improve the transferability of the geometric adversarial attacks.
the proposed
Potential societal negative impacts: Adversarial attacks pose significant security risks in real- world machine learning systems due to the potential misuse of adversarial perturbations for mali- cious purposes. Our proposed black-box GSBAK method aims to generate lop-K adversarial exam- ples, which can be leveraged for various real-world scenarios, as outlined in the introduction section. While our experiments primarily focus on deceiving image classifiers, the versatility of our approach extends to other domains, such as image annotation, object detection, and recommendation systems, broadening the scope of potential misuse by malicious users. However, it's important to emphasize that objective is to highlight the vulnerabilities of machine learning systems in aggressive top-K settings, ultimately advocating for the implementation of defense mechanisms to enhance their secu- rity against adversarial attacks. One potential defense strategy against our proposed attack involves restricting queries around the decision boundaries.
H CRAFTED ADVERSARIAL EXAMPLES
In this section, we demonstrate number of generated top-K adversarial examples and their corre- sponding perturbation, along with detailed information, for different benign inputs against different classifiers. While Fig. [3] Fig. 14 and Fig. 15 demonstrate crafted untargeted adversarial examples against ResNet-50, VGG 16 and ResNet- single-label multi-class classifiers, Fig. 16] Fig. 17 and Fig. 18 display the crafted targeted adversarial examples against these classifiers. Fig. 19 depicts the generated top-2 adversarial examples against a classifier with multi-label learning. The value of & at the title of each adversarial example demonstrates the f--nomm of the crafted perturbation obtained after spending a given query budget.
25

---

Published as a conference paper at ICLR 2025
Source
top-1 0.99
top-2 ( :1:13
| 11:25
top-4 4:137
perpetturbation
10*perturbation
10*perturbation
10*perturbation
[cicada, leafhopper, lacewing, fly, graxshopper]. Top-5 predictions of the top- K adversarial examples are as follows: top- I: [dragonfly, cicada, fly, damselfty, lacewing). top-2: Vfy, dragonfty, cicada, damselfly, lacewing), tep-3: [dragonfly, lacewing, damselfly, cicada, fly]. and top-4: [dragonfly, damselfly, lacewing, fly, cicada).
(a) Top-5 predictions source image on ResNet-50 are:
Source
top-1 1 4:8.11
tap :0.99
top 3 & :1.03 top 4 4 ::41
10*perturbation
10*perturbetion
10*perturbation
10*perturbation
(b) Top-5 predictions of source image on VGG-16 are: [cicada, leafhopper, grasshopper, lacewing, man- ris]. Top-5 predictions of the top-K adversarial examples are as follows: top-1: [leafhopper, cicada, mantis, lacewing, grasshopper), top-2: [leafhopper, mantis, cicada, grasshopper, cricker), top-3: [mantis, leafhopper, grasshopper, cicada, cricket), and top-4: (grasshopper, mantis, leafhopper lacewing, cicada].
Source
top-1 14:115
top-2 4 1.57
top-3 1::88
top-4 42.38
10*perturbation
10*perturbation
10*perturbation
10*perturbation
(c) Top-5 predictions of a source image on ResNet- 101 are: per]. Top-5 predictions the top-K adversarial examples are as follows: top- [leafhopper, cicada, grasshop- per, cricket, laceving), top-2: [leafhopper, grasshopper, cicada, cricket, mantis), top-3: Igrasshopper, leafhop- per, cricket, cicada, cockroach), and top-4: [cricket, grasshopper, leafhopper, mantis, cicada].
[cicada, leafhopper, lacewing, cricket, grasshop-
Figure 13: Crafted Kop-K untargeted adversarial examples of source image with ground truth label cicada, utilizing query budget of 5000, against different single-label multi-clan classifiers
26

---

Published as a conference paper at ICLR 2025
Source
top-1 12:22
top-2 1::112
6
top-4 42:6.27
perperturbation
10*perturbation
10*perturbation
10*perturbation
(a) Top-5 predictions source image on ResNet-50 are: [redshank, ruddy turnstone, dowitcher, oystercatcher, limpkin]. Top-5 predictions of the top-K adversarial examples are as follows: top-1: [dowitcher, redshank, limpkin, water ouzel, ruddy turnstone), top-2: [dowitcher, limpkin, redshank, black stork, bittern], top-3: (dow- itcher, limpkin, red-backed sandpiper, redshank, cicada), and top-4: [dowitcher limpkin, spoonbill, red-backer sandpiper, redshank].
top-1
top-2
top-4
po*peruurbation
10*perturbation
10+perturbation
p0*petturbation
(b) Top-5 predictions of source image on VGG-16 are: [redshank, oystercatcher, dowitcher, ruddy turnstone, red- breasreea merganser). Top-5 predictions of the top-K adversarial examples follows: top-1: [ruddy turnstone, redshank, dowitcher, shank, red-backed sandpiper. water ouzel), top-3: [cicada, water ouzel, ruddy turnstone, redshank, leashopper), and top-4: [cicada, leafhopper, weevil, water ouzel, redshank).
ouzel, red-backed sandpiper), top-2: [ruddy turnstone, dowitcher, red-
Source
top-1 16:1
top-2 :3.447
top-3 b 44.88
top-4 55.334
pertuurraaionn
pertttruraation
10*perturbation
porpttuuraation
(c) Top-5 predictions of source image ResNet-101 are: [redshank, oystercatcher, ruddy turnstone, dow- itcher, red-breasted merganser]. Top-5 predictions of the top-K adversarial examples follows: top-1: Idowitcher, redshank, ruddy turnstone, limpkin, robin), top-2: [dowitcher, limpkin, redshank, ruddy turnstone, black stor), top-3: Limpkin, dowitcher, bittern, redshank, black stork]. and top-4: [dowitcher, partridge, ruffed grouse, brambling, redshank).
Figure 14: Crafted top- K untargeted adversarial examples of source image with ground truth label redshank, utilizing a query budget 5000, against different single-labe label multi-class classifiers.
27

---

Published as a conference paper at ICLR 2025
Source
top-1 6::12 1.21
top-2 6.99
top-3 11:04
top-1 16:13
pereeruurbation
perperturbbatin
10*perturbation
10*perturbation
(a) Top-5 predictions of a source image on ResNet-50 are: [loggerhead, leatherback turtle, hippopotamus, terrapin, mud turtle). Top-5 predictions of the top-K K adversarial examples are as follows: top-I: I: Vleatherback urile, loggerhead, amphibian, speedboat, conch), top-2: lamphibian, hippopotamus, loggerhead, leatherback turtle, speedboat), top-3: [amphibian, hippopotamuss speedboat, loggerhead, leatherback turtle), and top-4: lamphibian, conch, hippopotamus, speedboat, loggerhead].
0.555
top-2
top-3 11:00
top-4
10*peruurbation
10*perturbation
10*perturbation
10*perturbation
(b) Top-5 predictions of a source image on VGG-16 are: [loggerhead, leatherback turtle, conch, hermit crab, terrapin]. Top-5 predictions of the top-K adversarial examples follows: top-1: [conch, loggerhead, hermit crub, leatherback turtle, hippopotamus]. top-2: [conch, hermit crub, loggerhead, leatherbuck turtle, fiddler crab], top-3: [conch, hippopotamus, hermit crab, loggerhead, bathing cap). top-4: [conch, hermit crab, buthing cap, hippopotamus, loggerhead].
Source
tap-1 0.000
top-2 6:0.37
top-3 003399
top-4 0:0.5
peretturraaionn
10*petturbation
10*perturbation
10*perturbation
(c) Top-5 predictions of source image on ResNet-101 are: [loggerhead, hippopotamus, leatherback turtle, conch, hermit crab]. Top-5 predictions of the top-K adversarial examples follows: top-1: Uhippopotamus, loggerhead, leatherback urrtle conch, hermit crab], top-2: [hippopotamus, bikini, loggerhead, bathing cap, conch), top-3: Phipoopotamus, bikini, bating cap, loggerhead, swimming trunks), and top-4: Vhippopotamus, conch, hermit crab, bikini, loggerhead).
Figure 15: Crafted top- K untargeted adversarial examples of source image with ground truth label loggerhead, utilizing query budget of 5000, against different single-label multi-class classifiers.
28

---

Published as a conference paper at ICLR 2025
Source
top-1 4 2:22
top-2 4 3328
top-3 :3:226
top-4 3:112
Target
10*perturbation
10*perturbation
pt*perturbation
10*perturbation
(a) Top-5 predictions of source image and target image ResNet-50 are [Staffordshire bullterrier, American Staffordshire terrier, Boston bull, French bulldog, basenji] and [cicada, leashopper, lacewing, fly. grasshopper), respectively. Top-5 predictions the top-K adversarial examples are as follows: top-1: (cicada, Staffordshire bullterrier, American Staffordshire terrier, miniature pinscher, muzzle), top-2: [cicada, leafhopper, American Staffordshire terrier, Staffordshire bullterrier, cricket), top-3: [cicada, lacewing, leafhopper, American Stafford- shire terrier, Staffordshire bullterrier], and top-4: [cicada, fly, lacewing, leafhopper, dragonfly).
Source
top-1 2.18
top-2 22248
top-3 15.91
top-4 1::324
Target
10*perturbation
10*perturbation
10*perturbation
10*perturbation
(b) Top-S predictions of source image and target image VGG-16 [Staffordshire bullterrier, American Staffordshire terrier, soccer bull, whippet, tennis bull] and [cicuda, leashopper, grasshopper, lacewing, man- tis]. respectively. Top-5 predictions of the top-K adversarial examples are as follows: top-1: [cicada, muzzle, Staffordshire bullterrier, miniature pinscher, rhinoceros beetle), top-2: [cicada, leafhopper, rhinoceros bee- tle, leaf beetle, muzzle), top-3: Igrasshopper, leafhopper, cicada, muzzle, cricket), and top-4: [grasshopper, leafhopper, cicada, lacewing, muzzle].
Source
top-1 2.88
top-2 4:1119
top-3 4:3311
top-4 4:5522
Target
10*perturbation
10*perturbation
10*perturbation
10*perturbation
(c) Top-5 predictions of source image target image on ResNet-101 [Staffordshire bullterrier, Ameri- can Staffordshire terrier. French bulldog. bull mastiff. Boston bull] and [cicada. leashopper, lacewing, cricket, grasshopper), respectively. Top-5 predictions of the top-K adversarial examples are as follows: top-1: [ci- cada, Staffordshire bullterrien American Staffordshire terrier, miniature pinscher, Chihuahua), top-2: [ci- cada, leafhopper, Staffordshire bullterrier, cricket, American Staffordshire terrier), top-3: (cicada, leafhopper lacewing, cricket, Staffordshire bullterrier), and top-4: [cricket, cicada, leafhopper, lacewing, grasshopper).
Figure 16: Crafted top-K targeted adversarial examples of a source image with ground truth label Staffordshire bullterrier and target image with top-/ classification label cicada, utilizing query budget of 30000, against different single-label multi-class classifiers.
29

---

Published as a conference paper at ICLR 2025
Source
top-1 2.94
top-2 3333
top-3 4 3.6
top-4 & 7.91
Target
10*perturbation
10*perturbation
10*perturbation
10"petturbation
(a) Top-5 predictions of source image and target image on ResNet-50 are [Staffordshire bullterrier, Amer- ican Staffordshire lerrier, Boston bull, French bulldog, baxenji] and [redshank, ruddy turnstone. dowitcher, oystercatcher, limpkin], respectively. Top-S predictions
top-K adversarial examples are as follows: top- I: (redshank, Italian greyhound, American Staffordshire terrier, Weimaraner, Staffordshire bullterrier). top-2: Iruddy turnstone, redshank, Italian greyhound, American Staffordshire terrier, Staffordshire bullterrier), top- 3: truddy nurnstone, dowitcher, redshank, American Staffordshire terrier, red- red-backed sandpiper), and top-4: [ruddy tursttone redshank, oystercatcher, dowitcher, magpie].
Source
top-1 2:34
top-2 22242
top-3 13.09
top-4 4 44.95
Target
10*perturbation
10*perturbation
10hperturbation
10*perturbation
(b) Top-S predictions of image and target image VGG-16 [Staffordshire bullterrier, American Staffordshire terrier, soccer ball, whippet, tennis bull) and [redshank, oystercatcher, dowitcher, ruddy turnstone, red- bre-breatted merganser]. respectively. Top-5 predictions of the top-K adversarial examples are as follows: top- I: (redshank, whippet, Scottish deerhound, American Staffordshire terrier, magpie), top-2: [oystercatcher, redshank, whippet, magpie, European gallinule), top-3: [redshank, oystercatcher, dowitcher, whippet, goose), top-4: (ruddy turnstone, redshank, oystercatcher, dowitcher, whippet).
Source
top-1 2.922
top-2 4:3.37
top-3 1:3448
top-4 4:3.71
Target
10*perturbation
10*perturbation
10*perturbation
10*perturbation
(c) Top-5 predictions of source image and target image ResNet-101 [Staffordshire bullterrier, Amer- ican Staffordshire terrier. French bulldog, bull mastiff. Boston bull] and [redshank, oystereatcher, ruddy turn- stone, dowitcher, red--beasted merganser), respectively. Top-5 predictions of the top- K adversarial examples are as follows: top-1: [redshank, American Staffordshire terrier. Stuffordshire bullterrier, reel, kelpie). top-2: loystercatcher, redshank, Staffordshire bullterrier. American Staffordshire terrier, kelpie), top-3: [ruddy turn- stone, redshank, oystercatcher, Staffordshire bullterrier, American Staffordshire terrier), and top-4: [redshank, ruddy tursstone, oystereatcher, dowitcher, American Staffordshire terrier).
Figure 17: Crafted top-K targeted adversarial examples of source image with ground truth label Staffordshire bullterrier and target image with top-1 classification label redshank, utilizing query budget of 30000, against different single-label multi-class classifiers.
30

---

Published as a conference paper at ICLR 2025
Source
top-1 14:22200 2:65
top-2 & 2:82
top-3 14:33 :.33
top-4 & 5.53
Target
10*perturbation
10*perturbation
10*perturbation
10*perturbation
(a) Top-5 predictions of source image and larget image ResNet-50 are [Staffordshire bullterrier, Ameri- Staffordshire terrier, Boston bull, French bulldog, busenji] and [loggerheud, leatherback turtle, hippopota- mus, terrupin, mud urtte), respectively. Top-5 predictions
top-K adversarial examples are as follows: top-1: (loggerhead, Staffordshire bullterrier, American Staffordshire terrier, terrapin, leatherback turtle), top- 2: [leatherback turtle, loggerhead, Staffordshire bullterrier, American Staffordshrre terrier, terrapin), top- lleatheback turtle, hippopotamus, loggerhead, Staffordshire bullterrier terrapin), and top-4: (terrapin, leatherback turtle, hippopotamus, loggerhead, mud turtle).
Source
top-1 3.16
top-2 3.001
top-3 14 5.7
top-4 6:699
Target
10*perturbation
10*perturbation
10*perturbation
10*perturbatio
(b) Top-S predictions of image and target image VGG-16 [Staffordshire bullterrier, American Staffordshire terrier, soccer ball, whippet, tennis bull] [loggerhead, leatherback turtle, conch, hermit crab, terrapin], respectively. Top-5 predictions of the top-K adversarial examples are as follows: top-1: [loggerhead, black-and-Rn tan coonhound, terrapin, Staffordshire bullterrier, mud turtle), top-2: [leatherback turtle, logger- head, terrapin, mud turtle, Staffordshire bullterrier), top-3: [loggerhead, leatherback turtle, conch, terrapin, mud turtle), and top-4: [hermit crab, leatherback turtle, conch, loggerhead, terrapin).
Source
top-1 2.622
top-2 4:449
top-3 1:33776
top 8.009
Target
10*perturbation
10*perturbation
10*perturbation
10*perturbation
(c) Top-5 predictions of source image and target image ResNet- 101 are [Staffordshire bullterrier, Ameri- can Staffordshire terrien, French bulldog, bull mustiff. Boston bull] and [loggerheud, hippopotamus, leatherback turile, conch, hermit crab), respectively. Top-5 predictions of the top-K adversarial examples are as follows: top-1: [loggerheud, Staffordshire bullterrien, American Staffordshire terrier, mud turtle, terrapin), top-2: [hip- popotamus, loggerhead, Staffordshire bullterrier, American Staffordshire terrier, Mexican hairless), top-3: [log- gerhead, leatherback turtle, hippopotamus, Staffordshire bullterrier, American Staffordshire terrier), ), and top-4: lloggerhead, hippopotamus, leatherback turtle, conch, triceratops).
Figure 18: Crafted top-K targeted adversarial examples of source image with ground truth label Staffordshire bullterrier and a target image with top-1 classification label loggerhead, utilizing query budget of 30000, against different single-label multi-class classifiers.
31

---

Published as a conference paper at ICLR 2025
Adv. ex. f2:17
Adv. ex. f2:411 frandom targets)
Adv. ex. f2:5.3 (worst targets)
Benign
(best targets)
1 Perturaaaiioo
10*Perturbation
10*Pttuurbttton
(a) Prediction order of source image with true lahel {person, horse) is: [person, horse, boat, car, dog. bicycle, cow, motorbike, bus, chair, potted plant, bird, bottle, tvmonitor, sheep, cat, train, sofa, dining table, aeroplane). The best, random and worst target sets are {boat, car). {tv/monitor sofa) and [dining table, aeroplane).
Adv. ex. | f2:27 (best targets)
Adv. ex. 12:4.4 frandom targets)
Adv. ex. f2:8.6 (worst targets)
Benign
1
P
Porttrurrbttion
(b) Prediction order of source image with true label (person, dog} is: [person, dog, sheep, car, horse, bottle, cow, car, bicycle, potted plant, boat, sofa, chair, rymonitor, motorbike, bird, train, dining table, bus, aeroplane). The best, random and worst target sets are (sheep, car). {polied plant, motorbike) and (bus, aeroplane).
Adv. ex. | 6:3.1 (best targets)
Adv. ex. 6:6.3 frandom targets)
Adv. ex. 12:6.0 (werst targets)
Benign
10*Petturbation
10*Perturbation
10*Perturbation
(c) Prediction order of source image with true label {person, bicycle) is: [person, bicycle, bottle, car, chair, potted plant, bus, motorbike, cow; dog, horse, dining table, sofa, cat, train, tv/monitor, boat, sheep, bird, aeroplane). The best, random and worst target sets are {bottle, car), (tvmmonioor, sofa) and (bird, aeroplane): }
Figure 19: Crafted top-2 adversarial examples for benign inputs with two true labels against Inception-V3 (Szegedy et al. 2016) on PASCAL VOC 2012 dataset (Everingham et al. 2015) with best, random and worst target label sets utilizing query budget of 30000.
32


Reviews:
[{"review_id": "b3Yrcun7y3", "reviewer": "Reviewer_8mHS", "summary": "This paper presents a score-based and query-efficient blackbox adversarial attack method. The proposed method is designed based on GSBA, which searches for the adversarial samples close to the classification boundary along a semi-circular path. The merit of the proposed method is more accurate gradient estimation to update incrementally the adversarial sample in the adversarial region and along the classification boundary. This study applies the method to a challenging top-k adversarial attack scenario and demonstrate its superior performance compared to the baselines in an empirical comparison.", "questions": "1/ Regarding the second bullet point in the comments of weakness, please provide further discussion if the reweighing technique may require to increase the number of queries, since the reweighing step can exclude some sampled points from estimating the gradients. \n\n2/ Please justify the third bullet point with further discussions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This study offers a query-efficient solution to a challenging top-K adversarial attack problem and organise a comprehensive study in both targeted and untargeted attack scenarios for single-label and multi-label learning tasks. The core idea is to boost the blackbox gradient estimator by reweighing different sample points around the current estimate, instead of treating them equally. The weight assigned to each sampled point is defined by measuring the decision confidence variation. The sampled points are considered, only if they cause the decision confidence scores all decrease with respect to the targeted top-K classes towards the adversarial region. This weighing technique better tunes the gradient estimator to be aligned to the goal of adversarial attacks. This design improves the efficiency of attacks, rather than initialising the attack with a random or less attack-optimised gradient estimates.", "weaknesses": "I have the following suggestion and comments over the limitation of this study. \n\n(1) This paper needs significant improvement to get a clear logic structure. The attack according to Figure.3 is initialised by locating an adversarial sample along the classification boundary, then followed by searching for more closer adversarial samples in the adversarial region along a semi-circular path. Therefore, Section 4.2 should be presented before 4.1. \n\n(2) Reweighing the sampled point to form a more accurate gradient estimator also reduces the number of sampled points $\\{z_{i}\\}$ that are useful and have non-zero weights in gradient estimation. As a result, it may produce a better gradient estimation, yet require more sampled points especially at the beginning iterations of the attack. \n\n(3) Why do you set the number of the queried points as $\\lfloor{I_{0}\\sqrt{n+1}}\\rfloor$ ?", "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": "ojo5xr7wTr", "reviewer": "Reviewer_LM2j", "summary": "This paper addresses a novel setting in black-box adversarial attacks, specifically focusing on generating top-k adversarial examples with access to the target classifier's class prediction probabilities. While traditional decision-based black-box attacks rely solely on class labels, this work leverages additional information in the form of prediction probabilities to enhance attack effectiveness.\nThe authors propose a geometry-based framework that generates both targeted and untargeted attacks without requiring a surrogate model. The method operates iteratively: given an input data point and query access to a black-box model, it systematically updates the data point to approach the decision boundary through repeated classifier queries. At the initial boundary point, by exploiting the geometry of the decision boundary, the framework identifies boundary points with reduced perturbation norms.\nComprehensive experiments presented in both the main paper and appendix demonstrate that the additional information provided by prediction probabilities significantly enhances attack effectiveness. While existing methods fail to adequately leverage this information and perform poorly in this novel setting, the proposed approach consistently achieves superior results compared to current alternatives.", "questions": "1. From Table 1, I do see that the performance on targeted attacks drops quickly as the K increases. For example, the best top-2 accuracy of 98.2% to top-4 accuracy of 81.4%. Which makes me question that how well the method would scale for larger multi-label datasets and for larger K e.g., K = 20 for OpenImages dataset? Please provide comments or any analysis.\n2. It is not clear how the target labels are selected for targeted attack setting for ImageNet experiments. For PASCAL-VOC, how many experiments are performed for random target class setting in Table 2 and how much do the results vary? Did you observe any influence of choosing specific target classes on the performance?\n3. For DCT, what percentage of low frequency components were selected? Have you performed any experiments to show the impact of choosing different number of components?\n4. Since you are considering the setting where the sum of probabilities is 1, maximizing the probability of a set of target classes would reduce the probabilities of other classes. In multi-label learning, the labels are correlated and it is difficult to maximize a set of target class probabilities while decreasing the other highly correlated classes. This was observed in one of the recent works [1]. Did you observe something similar? Any comments?\n\n--\n\n1. Mahmood, Hassan, and Ehsan Elhamifar. \"Semantic-Aware Multi-Label Adversarial Attacks.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: This work presents the first systematic investigation of black-box adversarial attacks in the top-k setting with access to prediction probabilities, addressing a previously unexplored practical scenario.\n\n**Quality**: The methodology demonstrates technical soundness, particularly in its approach to gradient approximation. The rationale of approximating gradients in adversarial and non-adversarial regions in different ways for top-k setting makes sense. \n\n**Clarity**: The paper is mostly clear and well-written. However, there are some missing details which I have asked in the question section. In terms of logical flow, I personally think that the section about estimating the gradients in non-adversarial region should be discussed before boundary region since that is the first step in the attack generation.\n\n**Significance**: The paper makes substantial contributions to adversarial machine learning by introducing a novel attack setting that leverages prediction probability information in top-k predictions. The paper demonstrates how this additional information can be effectively used.", "weaknesses": "There are a few key weaknesses:\n1. Lines 270 - 271: experimentally, it is observed that $\\zeta\\_{\\boldsymbol{x}\\_{b_n}, c, \\boldsymbol{z}\\_i}=\\zeta\\_{\\boldsymbol{x}\\_{b_n}, -c, \\boldsymbol{z}\\_i}$. This might be true for some directions, but this cannot be guaranteed. The trained models can have flat surface across a direction. The formula (7) is based on that. I understand that this works in practice, but this does not have a strong/concrete evidence. \n2. One drawback of (5) is that the formulation does not consider relative change i.e., the change in a class prediction from 0.5 → 0.52 is considered the same as 0.02 → 0.04 where one might argue that the latter is better than the former.\n3. Similarly, Eq(12) can weigh two directions/vectors equally even if one would overall hurt the performance of majority of classes as compared to the other. For example, consider two vectors z1 and z2. Assume we are considering top-3 attack. Consider the model predicts initially with the target class probabilities shown {….., 0.03,0.04,0.02} (assume the other class probabilities are fixed). Assume \n\n    z1 changes the predictions to {…., 0.023,0.021,0.32}: reduces the confidence of two classes and increases one.\n\n    z2 changes the predictions to {….., 0.13, 0.14, 0.12}: equally increases the confidence of all classes.\n\n4. Another issue is that the method might be too dependent on the initial boundary point because once it finds a point on the boundary, to find the next boundary point, it requires that the change in the probability should be larger as in Eq(5). It is actually very likely that the confidence would decrease for the top-k predictions and correspondingly might increase for the the rest but still the top k predictions remain top k. For example, {0.3,0.3,0.3,0.1} → {0.28,0.28,0.28,0.16}. This might explain why the method doesn’t perform that well for small norms. \n5. The experiments do not provide confidence intervals. For example, in table 2, it is important to know how much of deviation there is across different target classes (through standard deviation). I would highly encourage the authors to add that in the paper, if possible. \n6. Although there are extensive experiments, the missing experiments are for larger K and for multi-label datasets with larger number of labels e.g., MS-COCO, OpenImages. It would be great to see the performance for larger data sizes in multi-label settings. \n7. Lines 177 - 178: Should be $P(\\boldsymbol{x}):[0,1]^{C\\_h \\times W \\times H} \\rightarrow [0,1]^C$ since the paper considers probabilities. \n8. Since the work is relevant to multi-label learning in general, it is good to cite and mention recent multi-label attacks e.g., [1,2].\n\n--\n1. Mahmood, Hassan, and Ehsan Elhamifar. \"Semantic-Aware Multi-Label Adversarial Attacks.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.\n2. Jia, Jinyuan, Wenjie Qu, and Neil Gong. \"Multiguard: Provably robust multi-label classification against adversarial examples.\" Advances in Neural Information Processing Systems 35 (2022): 10150-10163.", "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": "jVIdHb8Xir", "reviewer": "Reviewer_hY9G", "summary": "The paper addresses the problem of score-based adversarial attacks on top-K predictions. They propose a novel GSBA^K attack that uses gradient estimation in the non-adversarial region and on the decision boundary to craft adversarial perturbations. The authors discuss both targeted and untargeted settings. The approach is extensively evaluated on multiple datasets and compared to existing methods in the top-K setting.", "questions": "1) line 271: “experimentally it is observed that …” - do you have an explanation for this observation? It seems a bit counterintuitive to me. \n\n2) In the line 396, could you please also state the number of classes in each dataset, especially Pascal VOC? It could be useful to compare the number of target classes K that you use in your attacks with the total number of classes N. Have you investigated extreme cases e. g. when K ~ N/2 i. e. we need to completely shift the prediction scores?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality: the paper proposes a novel and efficient black-box attack that relies on existing approaches to some extent but contains original elements such as novel gradient estimation methods.\n\nQuality: proposed attack is extensively evaluated and compared to existing work. The asttack is tested on both vanilla and robust models (Table 6). Limitations and Social Impact are discussed in the Appendix F.\n\nReproducibility: the code is provided in the supplementary materials, not carefully checked. \n\nClarity: the paper is well structured, the geometrical intuition is illustrated in numerous Figures. \n\nSignificance: the paper seems to introduce valuable improvement into the black-box robustness evaluation field and addresses a challenging and insufficiently investigated field of top-K predictions.", "weaknesses": "Some minor points:\n\n1) Avoid duplication of very long expressions in Equations (7), (9), (12), (13) to improve readability. Consider denoting the nominator as h and use g = h / ||h||_2\n\n3) typo in line 024: experiental", "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": "g6FgEgUbM8", "reviewer": "Reviewer_uZC7", "summary": "The paper introduces GSBA$^K$, a comprehensive and query-efficient geometric score-based attack specifically designed for the challenging top-K setting. GSBA$^K$ incorporates innovative gradient estimation techniques to identify a better initial boundary point and exploits the geometric properties of decision boundaries to improve both query efficiency and attack adaptability. The top-K setting presents significant difficulties in adversarial attacks, particularly for targeted attacks. The proposed method combines a novel gradient technique with the existing CGBA approach to address the complexities of score-based black-box attacks in the top-K scenario. While the proposed approach is promising, the clarity of the paper’s writing limits the accessibility of the method. For instance, it is unclear what the notation $\\zeta _ {\\mathbf{x} _ {b_n}, c, z _ i}$ in Eq. (6) represents or why $\\mathbf{x} _ {b_n}, c, z _ i$ appear in the subscript. The distinction between the two versions of gradient estimation—one on the decision boundary and the other in the non-adversarial region—warrants clarification. An overview would help provide a broader perspective on why both approaches are necessary and how they contribute differently to the attack method. Most importantly, the paper lacks a theoretical analysis of the accuracy of the gradient estimation (e.g., examining the expected cosine similarity between the estimated gradient and the true gradient).", "questions": "1. Targeted attacks in the top-K setting for black-box scenarios are highly challenging. A key question is how to ensure that the estimated gradient consistently points toward the narrow adversarial region corresponding to the $K$ target classes. Additionally, how is a high attack success rate (ASR) maintained in such targeted attacks?\n\n2. Could you provide a simplified overview explaining why there are two versions of gradient estimation (one on the decision boundary and the other in the non-adversarial region)? This would help make the rationale for this choice more accessible and easier to understand.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The top-K setting poses substantial challenges for adversarial attacks, especially in targeted scenarios. The proposed method integrates a novel gradient technique with the existing CGBA approach to tackle the complexities of score-based black-box attacks within the top-K framework. Experimental results demonstrate promising performance.", "weaknesses": "1. Although the ablation study and experiments in the Appendix provide valuable insights, the paper *lacks a theoretical analysis of the gradient estimation accuracy* (e.g., evaluating the expected cosine similarity between the estimated and true gradients). Without this analysis, the quality of the estimated gradient remains uncertain from a theoretical perspective. \n\n3. Some baseline comparisons appear to be missing. For instance, the QuadAttacK method [1] is not included in the experiments. How does the ASR of GSBA$^K$ compare to QuadAttacK?\n\n3. The writing in Sections 4.1 and 4.2 makes it difficult to understand the proposed approach. For example, the notation $\\zeta _ {\\mathbf{x} _ {b_n}, c, z _ i}$ in Eq. (6) is unclear, and the reason for including $\\mathbf{x} _ {b_n}, c, z _ i$ in the subscript is not well-explained. The symbols used in the formulas are overly complex and lack brevity.\n\n[1] Paniagua, T., Grainger, R., & Wu, T. (2023). QuadAttacK: A Quadratic Programming Approach to Learning Ordered Top-K Adversarial Attacks. In *Advances in Neural Information Processing Systems 36 (NeurIPS 2023)*.", "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 (Poster)