Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks
Authors: Chen Ma
Xiangyu Guo
Li Chen
Jun-Hai Yong
Yisen Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: black-box adversarial attack
hard-label attack
geometric-based attack
tangent point
tangent line
HopSkipJumpAttack

Abstract: One major problem in black-box adversarial attacks is the high query complexity in the hard-label attack setting, where only the top-1 predicted label is available. In this paper, we propose a novel geometric-based approach called Tangent Attack (TA), which identifies an optimal tangent point of a virtual hemisphere located on the decision boundary to reduce the distortion of the attack. Assuming the decision boundary is locally flat, we theoretically prove that the minimum $\ell_2$ distortion can be obtained by reaching the decision boundary along the tangent line passing through such tangent point in each iteration. To improve the robustness of our method, we further propose a generalized method which replaces the hemisphere with a semi-ellipsoid to adapt to curved decision boundaries. Our approach is free of pre-training. Extensive experiments conducted on the ImageNet and CIFAR-10 datasets demonstrate that our approach can consume only a small number of queries to achieve the low-magnitude distortion. The implementation source code is released online.

Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks
Chen Ma Xiangyu Guo Li Chen 1,+ Jun-Hai Yong Yisen Wang 3,4
School of Software, BNRist, Tsinghua University, Beijing, China Department of Computer Science and Engineering, University at Buffalo, Buffalo NY, USA
3 Key Lab. of Machine Perception, School Artificial Intelligence, Peking University, Beijing, China Institute for Artificial Intelligence, Peking University, Beijing, China machenstare tare163. com, xiangyugdbuffalo. edu edu. edu.
Schenlee,yonge @tsinghua. edu. en, yisen. wwngapwu.nuuu.mmm wang@pku.edu.co
Abstract
One major problem in black-box adversarial attacks is the high query complexity in the hard-label attack setting, where only the top-1 predicted label is available. In this paper, we propose a novel geometric-basee approach called Tangent Attack (TA), which identifies an optimal tangent point of a virtual hemisphere located on the decision boundary to reduce the distortion of the attack. Assuming the decision boundary is locally flat, we theoretically prove that the minimum & distortion can be obtained by reaching the decision boundary along the tangent line passing through such tangent point in each iteration. To improve the robustness of our method, we further propose generalized method which replaces the hemisphere with a semi-ellipsodd to adapt to curved decision boundaries. Our approach is free of pre-training. Extensive experiments conducted on the ImageNet and CIFAR- 10 datasets demonstrate that our approach consume only small number of queries to achieve the low-magnitude distortion. The implementation source code is released online at hettttt//// /ttp:////ttutt./t/ http://///ccccaaiiaaaageeetttete
1 Introduction
Adversarial attacks cause deep neural networks (DNNs) to make incorrect predictions by slightly perturbing benign images during the test time. They can be divided into two main categories on the basis of the amount of information exposed by the target model, namely white-box and black-box attacks. Many white-box attacks 66 29 32 have been proposed, and they can compute the gradients w.r.t. the target model's input images generate adversarial examples with the first-order optimization techniques. In contrast, black- box attacks are more practical because they craft adversarial examples without requiring the target model's 's gradients.
Over the past years, the community has made considerable efforts in developing black-box attacks, and the proposed methods can be divided into transfer- and query-based attacks. Transfer- based attacks 25 37 generate adversarial examples by using a white-box attack method against a surrogate model to fool the target model. Although there is no need to query the target model in these attacks, the attack success rate can not be guaranteed, especially in the case of targeted attacks. To achieve satisfactory attack success rates, the query-based attacks use elaborate queries to obtain the feedback the target model for crafting adversarial examples. the score-basse based setting, the query-based attacks 2 [12 22 28) estimate approximate gradients by querying the predicted scores of the target model at multiple points. However, in most real-world scenarios, the score-based setting
"Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

non-adversarial region tangent point
HSJA point g
adyersarial region
original image =aaze
Xg
X
non-adversarial region
Figure I: Simplified two-dimensional illustration of our motivation. H is the decision boundary, and
X₁-1 is the current adversarial example mapped onto the decision boundary at the (t 1)-th iteration. HSJA updates x;-1 along the gradient direction to reach g and then maps to H at Xg along the line through x and g. However, the optimal update should be the tangent point k because it can be mapped onto at X that has the shortest distance to the original image x.
is not applicable because the public service returns only the top-1 predicted label (i.e., the hard label) rather than the predicted score. In this case, since the feedback information is limited and the objective function is discontinuous, the attack requires solving high-dimensional combinatorial optimization problem, which often challenging.
To reformulate the attack as real-valued continuous optimization problem, OPT [00, Sign-OPT and RayS [8] focus minimizing an objective function g(),, which is defined as the distance from the original image to the nearest adversarial example along the direction 6. However, when attacking complex models, it may be difficult find suitable direction 0 along which adversarial examples exist.
qFool [26]. and Policy Driven Attack (PDA) 40 climinate the search the direction Instead, they start from a large adversarial perturbation and then reduce its distortion while staying in the adversarial region. Because the output labels of the target model flip only near the decision boundary, these attacks restrict their explorations the regions near the decision boundary. However, they do not thoroughly investigate the geometric properties of the decision boundary to accelerate the attack. For example, PDA uses reinforeement learning framework train policy network to predict search directions, which are not geometrically optimal. In addition, the prediction accuracy of the policy network decreases significantly in the later stages of the iterations, resulting in worse performance of these iterations. HSJA and qFool simply use the gradient u estimated at the decision boundary as the direction of each update, while ignoring geometrically critical issue, i.e., u not the optimal direction be followed (Fig. I. We could explore better search directions at each attack iteration.
Boundary Attack (BA) HopSkkipluppAtrak (HSJA) 17). QEBA 24
To find the optimal search direction for minimizing the distortions of attack, we propose new scometric-basee approach whose motivation is illustrated in Fig. [ We construct a virtual semicircle B centered at X;-1 indicate all possible locations that X;-1 can reach along different directions, and the radius of limits the range of updates for successful attacks. It is easy to observe that moving along the tangent line reach the nearest location of the decision boundary the original image x, thereby producing the adversarial example with the minimum distortion. In real attack scenarios, the image data reside in high-dimensional space, and the semicircle becomes hemisphere. In this case, the benefit of using tangent points still exists, and we provide the detailed description and the formal proof in Section 3 and appendix.
To summarize, the main contributions of this study are as follows.
1. We cast the problem of minimizing the distortion in hard-label attacks into a geometric problem. We discover that the minimum distortion can obtained by searching the optimal tangent point of virtual hemisphere around the adversarial example at each iteration.
2. We propose a novel geometric- based method to obtain a closed-form solution of the optimal tangent point. We provide an intuitive explanation of our approach, as well as formal proof of its correctness.
3. To improve robustness, we further propose generalized method that replaces the hemisphere with a remi-ellipsoid to adapt to the target models with curved decision boundaries.
4. Extensive experiments conducted on the CIFAR-10 23 and ImageNet [4] datasets demonstrate the effecctiveness of our approach.

---

2 Related Work
Query-based black-box attacks can be divided into score- and decision-based attack (a.k.a. the hard-label attack). Score-based attacks [1 12
22 28 31 use the predicted probability score to craft adversarial examples, which is not always available in most real-world systems. Hard-label attacks are more useful, but obviously more challenging, because only the top-1 predicted label can be obtained. The hard-label attacks usually fall into three categories.
The first category starts from the original image Xo and attempts to find a optimal direction to reach the adversarial example. OPT [10] searches optimal & to minimize the distance from Xo to the nearest adversarial example. Sign-OPT [T] improves the query efficiency of OPT by using a single query to estimate the sign of the directional derivative. RayS [8] eliminates the gradient estimation and proposes a fast check step to efficiently find the direction t. However, RayS is only applicable to the untargeted attack under the fo norm because it is difficult to find suitable direction to reach the region of the target class in a targeted attack, especially in the case of a large number of classes.
The second category starts from large perturbation or image of the target class, and then reduces its distortion while staying in adversarial region, thereby gradually making it closer to the original image. BA 4 and NES [1] are two representative methods, but they have high query complexity. Biased BA reinterprets BA as a biased sampling framework and incorporates different biases to improve the query efficiency. HSJA 77] utilizes the gradient estimation and the binary search to outperform BA. HSJA can be used as the baseline of hard-label attacks. QEBA (24) improves HSJA by using dimension reduction techniques. SurFree 33] and GeoDA 33) improve the performance of HSJA by exploiting geometric properties of DNNs. However, the geometric features of DNNs have not been fully explored, and they do not support the targeted attack. PDA 440 uses reinforcement learning framework to train a policy network to predict promising directions. However, PDA requires high-cost pre-training, which is not always available in all tasks.
The third category uses a random sampling technique to improve query efficiency. Customized Adversarial Boundary (CAB) attack (34) uses the current noise to select the sensitive area of images and customize sampling distribution. Evolutionary [16] improves the query efficiency by reducing the dimension of the search space with the stochastic coordinate selection.
The issue of RayS and GeoDA that they only support untargeted attacks. Because moving the original image far enough in any direction can always make it escape the aon-adversarial region in untargeted attacks. However, in targeted attacks, is difficult to find suitable direction along which the target class's 's region exists. In contrast, our approach supports all types of attacks, and we exploit the geometric characteristics the decision boundaries of DNNs to boost the attack.
3
The Proposed Approach
3.1 The Goal of Hard-label Attacks
Given target model f RRd RR and benign image 1] that is correctly classified using f. the goal of the adversary is to slightly perturb x into Xadv, such that f(xuvv outputs incorrect prediction. In the hard-label attack, the adversary can only observe the top-1 predicted label of f. denoted as ÿ = arg max; fXaav) We define an indicator function o--) of a successful attack:
{
if ÿ Badv in the targeted attack, or 9 # y in the untargeted attack, otherwise,
d( ((Xavv)
(I)
where y E R is the true label of and Yady E R. is a predefined target class label. In this study, focus on generating an adversarial example Xadv that satisfies o(Xu.v) = 1, such that the distortion d(xatv, x) = X x|lp is minimized. This goal can be formulated as the optimization problem:
min d( d(Xndv, x) s.t. ((xavv) = 1.
(2)
3.2 Motivation
Most recent attacks belong to the second category (Section follow common procedure: from an adversarial image yet not close enough to the benign one, then it iteratively searches for
it starts
3

---

closer adversarial image. Let us take a typical attack HSJA 77 for example (Fig. D. First, the attack initializes the adversarial example by using an image of the target class (in targeted attack) or a noisy version of the original image (in an untargeted attack). Next, it performs the binary search to map the initial sample onto the decision boundary H, denoted as Xt-1- Then, the algorithm iteratively performs three steps to update x;- estimating gradient 11 at H by sampling many probes around x;-1; jumping to the point g along the direction u with the step size determined by the geometric progression; and mapping g onto Il at Xg by performing the binary search along the line passing through g and the original image x. However, geometrically speaking, the estimated gradient u is not the optimal search direction, and certain point on the semicircle B and then taking the intersection point on H. Fig. shows that the tangent point k is the optimum update because it leads to the minimum distortion of the attack.
find better boundary point X, by connecting to
3.3 Definition of Optimal Tangent Points
There is some experimental evidence that the deci- sion boundaries of DNNs are smooth surfaces with the low curvature 17 33 Based on this observa- tion, we approximate the local decision boundary with a hyperplane H. Fig. 3 illustrates our prob- lem in three-dimensional space. We will derive our algorithm from TR.3 and show that it can be directly extended to higher-dimensional spaces. Lastly, we address the case of curved decision boundaries.
B
U
y
As described in Section X denotes the bound- ary sample that already lies on the decision boundary. We create a virtual hemisphere B centered at X,-1 with a radius R, which an estimation of the safe region where we can search for adversarial exam- ples. In the targeted attack, B represents the current estimation of the target class region around X,-1- Ideally, B is small enough to be fully contained in the target class's 's region, i.e., o(x') Then, we need to find a point on which would produce the minimum distortion when mapped to H. In two-dimensional case, this point is the tangent point. However, in n-dimensional space where n 2 3, there are infinitely many tangent lines of B passing through x which create infinitely many tangent points B, shown as the red points in Figs. [ and 3] Still, we will show that exactly one tangent point can lead to the minimum distortion when mapping it onto H along the tangent line.
Figure 2: Geometrical explanation of Theo- rem D All points on H that are closer to x than x₁ are within a red disk, which is the in- tersection of H and the red cone whose vertex is x. Clearly k is the only intersection point of the cone and the hemisphere B. Thus, of all the lines intersecting B, only the intersection of the tangent line and H is closest to x.
for Vx' E B.
Formally, let k be any point on the surface of B, u be the approximate gradient of H estimated at X,-1, and x₃ be the intersection of H and the line passing through x and k, we have the following theorem.
Theorem Let H. u, k, x, and x;-1 be defined above, then the distance ||x - xxll is minimized if is the optimal solution of the following constrained optimization problem:
arg max k
(k X1 u)
(3)
s.t.
(k x, x - k) = 0,
(4)
kk x1-1|| || = R.
(5)
(k (k-x:t X1- u) 2 O.
In particular, the optimal k is in the plane spanned by u and x X(-1-
The objective function of Eq. (3) is to maximize the projection of the vector k X;-1 onto which equivalent to finding k that farthest away from H. The first constraint ensures that k is tangent point. The second constraint indicates k is on the surface of B. The last constraint states that k cannot appear on the same side of H as x, which always satisfied if | x.-1)ll > R, where the notation 1 R + H denotes the orthogonal projection from IR" onto the hyperplane H. If there no feasible solution, then our algorithm (Algorithm I reduces the radius R to guarantee that the last constraint is always satisfied. The formal proof of Theorem I is presented in the appendix. Here,

---

V
B
k
R
X
4
X
Figure 3: The illustration of the optimal tangent point k for the flat decision boundary. The tangent point k is the surface of virtual hemisphere B with radius R centered the adversarial example X,-1. x is the original image, x is the intersection point of the tangent line and the decision hyperplane H, k' and x' are the orthogonal projections of k and onto H and axis, respectively.
refer the readers to Fig. for intuitive geometrical explanation. Eq. is computationally expensive to solve the digh-damensional space. Fortunately, we show there actually exists a closed-form solution.
3.4 Closed-Form Solution of the Optimal Tangent Point
The main intuition of presentation, we move X to O. The known variables are x, Xr-1, the unit normal vector u of hyperplane H, and the radius R. We need to solve for the unknown k. Let = span( (x, u}) be the plane spanned by and According to Theorem[] we know k V. Let denote the angle between x and as a, the angle between x and k as B, and the angle between and H as ry Then, = because all three points x, k, and x,-1 on the same plane V. Because the angle between x and u is π 2 + a, we have
derivation is illustrated Fig. which shows an example in R For ease
(x, u) = |x|| ||u|| cos(
" π + a.) = ||x|| ||u||
(- sin o:).
2
(x.u) and cos = V1 sin 2 /|x |2 ||u 2 (x.u)² |||||||||||
Then we have sin
By the con-
|
straint x k is orthogonal to k. Thus. we have cos 3 = R / | and sin B = VI cos? B
x R² xx| Then sin ry and cos y be derived as functions of and ,3 from basie facts of
trigonometric functions:
sin 7 sin(B a) sin cos cos sin a, cos = co A a)) = cos B cos a + sin 8 sin a.
(8)
Now, let k' E H be the orthogonal projection of k onto the plane Н. The distance between k and k' R sin 7 = (sin 3 cos a cos 3 sin a).
denoted as h (Fig. 3). Then
To derive k,, let us denote x' as the orthogonal projection of x onto axis. So we have x' (x. -u) (-u) | (x, u) u/ ||u|| Then, because k' and x' are on the same direction, we have
k'
x
|
x x'I
Now, ||'|| = R cos y and x' = (x, u)
u
||u|| are plugged into Eq. (9. and is obtained as
x x'
|k'l = x (x. u)
k'
R cos
(10)
x xl|
|x
(x.
1
Therefore, k can be derived as
x (x, u) 11
k k'
R. cos + u.
(11)
xx
(x, u)
21
5

---

k(0k, 2h)
L
S
x( 20)
X
k (m 2x2)
(a) 3D view Generalized Tangent Attack
(b) 2D plane spanned by x and u.
Figure 4: Illustration of the derivation of Generalized Tangent Attack, which replaces the hemisphere B with a semi-ellipsoid to increase the height of k to adapt to curved decision boundaries.
Finally, because x has been moved to the origin, we need to move back by adding X;-1-
We remark that although the above derivation is illustrated in R3, it can be directly applied to higher dimensions. The reason is Theorem | which essentially reduces any dimension space to RR: to find the optimal k, we only need to focus on the plane V spanned by and x Xt-1-
3.5 Generalized Tangent Attack
When the local decision boundary is not flat enough, the boundary point obtained via the tangent line may not be the optimal, as shown in Fig. 4a A simple solution is to simply continue halving the radius I of the hemisphere: long as becomes small enough, the local flatness can always be obtained. However, too small a radius will reduce the convergence rate of our algorithm, because the distance between X, and x;-1 is proportional R. Therefore, when the classification decision boundary is a curved surface, the attack algorithm should change the shape of hemisphere rather than simply reducing R. Based on this idea, we propose the Generalized Tangent Attack (G-TA).
First, although the shape of the decision boundary can be very complex a high-dimensional space, the important thing for algorithm is only the situation in the two-dimensional plane spanned by and u. In particular, the decision boundary is "downward" curved (as opposed to the example in Fig. (a)) then searching along the tangent line is still better approach than HSJA's solution. Thus, the only "bad case" we have to deal with is when the decision boundary is "upward" curved and has large curvature, as shown in Fig. 4a
According to Theorem 1 we only need to focus on the plane V spanned by x and u, as shown in Fig. 4b Now, and == (x (x, u) u [u]l)/ / ||x (x, u) uu/ |u| (2] form orthogonal basis of the plane V. then x can be identified with coordinates ( 20), i.e., X 2o + ug Let arccos (x.-u) Then (No, =0) ([|x|| sin 0, -||x|| cos 0). Consider the projection of the ellipsoid on V (which is ellipse), we denote L as its radius along the direction of and S as its radius along the direction of v. Because the optimal tangent point k lies in the plane V, k can also identified as k T&V + u and we only need to solve for the unknown (IR, 2+).
denote the angle between the vector x and the vector -u, i.e.,
|
The ellipse is characterized by the equation x² / 52 + 23 L = 1, thus the tangent point k satisfies oh / 5 + 2f L 1. Now we view & as a function of x. and take the derivative w.r.. x at both sides of the equation to get the following formula:
2xk
2zh
dz
0.
(12)
22
1
dr
r=
Thus, we have the slope of tangent line at be
de
2s
Therefore, the tangent line ST
de
lame
can be written 2h
1.
(x
Th). Since the tangent line passes through x, know

---

20
2/
=:,2² 24."
(20 rk). In summary, we can obtain the following system of equations:
L' + -
=0
+
z 2 52 52+ L2
(13)
In Eq. (3), the known variables are L,, S, zo and 2n. and the unknown variables that we need to solve for are 2y and 2g. In general, there are two solutions for Eq. (13), i.e., and k' depicted in
Fig. 4b Apparently, the solution of the optimal tangent point should satisfy 2 >> O, so the one of two solutions in which 2/ > 0 should be picked:
L22 55
22
L2
20
1
1
L 30
(14)
L + LLroOV -2
L2 8
2k
1,20 + 52z
Finally, the optimal tangent point k is obtained via k = | implementation, the value of L is determined in the same way the radius R in TA (the hemisphere version). So we fix = R, and use a hyperparameter r = L/S S to control the value S. Imagine that in the case of R3, the semi-ellipsoid becomes "slender" by setting r 1, thereby adapting the decision boundary of curved surface while preserving a relatively large step size.
x (x.u) wu/ |||l]| + 23
x (x.u) u/ ul|
In the
3.6 The Complete Algorithm
TA (the hemisphere version) and G-TA (the semi-ellipsoid version) can be combined into one algorithm process, which is shown in Algorithm [ first performs binary search to map the initial sample &o to the decision boundary. Note that the binary search step always maps any Xadv to the adversarial side of H that satisfies ((xxdv) 1, hence the attack success rate is always 100%. Then, it performs for loop of I iterations to find the adversarial example that is close to In the first iteration, we sample Bo probes around the boundary sample to estimate the gradient, which is increased to Bo / at the t-th iteration. This because the error of gradient estimation in the later iterations has a greater impact on the attack performance, using more samples can reduce the estimation error. Then, while loop is performed to determine a reasonable radius R by repeatedly halving the radius until the tangent point k is in the adversarial region. Finally, Algorithm uses the binary search method to map back to the classification decision boundary to end this iteration.
Algorithm Tangent Attack
Input:
benign image attack success indicator function o(-) defined in Eq. ① initial batch size Bn, iteration T, mode m e { (semi-ellin Isemi-ellipsoid, hemisphere), ), radius ratio r.
Initialize Xn that satisfies d(Xx)) 1;
Xo f BinarySSarchh &2, x, Φ);
boundary search
dg = ||x, -x|:
for / in 1....,T' T do
Sample B, <- Bovl random vectors to estimate the gradient u;
Initialize R - d/t//vt:
the initial radius
while true do
Compute the optimal tangent point k based Eq. (11) if hemisphere else Eq. 14 D search the radius, and we set T,= R, S = L m semi-ellipsoid
R < n.
2'
if (K) then
break; end if
end while
t Clip(k, 0, 1);
X, < BinarySearch(k,, Φ);
boundary search
d, |x,-||
end for
7

---

Experiment
4.1 Experimental Setting
Datasets. TA and G-TA are evaluated on two datasets, namely CIFAR-I0 and ImageNet with the image resolutions of x 32 3 and 299 x 299 x 3, respectively. We randomly select 1,000 correctly classified images from their validation sets for experiments.
Method Setting. The initial batch size Bo is set to 100, which means the algorithm samples 100 probes for estimating a gradient at the first iteration. The threshold 7 that controls the termination of 1.0 in the CIFAR-10 10 dataset and 1,000 in the ImageNet dataset. The radius
the binary search is ratio r is set to 1.5 in the CIFAR-10 dataset and 1.1 in the ImageNet dataset. Besides, we also set r to 1.5 when attacking defense models. In targeted attacks, the target class label is set to yadv = (y + 1) mod C. where is the true label, and C' is the number of classes.
Compared Methods. The advantage of our method is that it supports all types of attacks, including both untargeted and targeted attacks under lg norm and & norm constraints. Therefore, for complete and fair comparisons, we select the compared methods that support both untargeted and targeted attacks with state-of-the-- ahe performance, including Boundary Attack (BA) [4], Sign-OPT ( SVM-OPT [II. and HopSkip/umpAAtac (HSJA) 77. HSJA is adopted as the baseline, whose hyperparameters are set to be the same with ours (e.g, the same initial batch size Bn and threshold ?). In addition, QEBA 24 is a HSJA-based method which has three variants: QEBA-I, QEBA-S and QEBA-F. We select QEBA-S in the additional experiment to verify whether the proposed method can improve attack performance of other HSJA-based method. For the consistency of experiments, we translate the implementations of Sign-OPT, SVM-OPT and HSJA from the official NumPy version into the PyTorch version by replacing each NumPy function with the corresponding PyTorch function. Thus, the two versions behave exactly the same. In the targeted attack, we randomly select an image from the target class of the validation set to be the initial sample of HSIA, BA, TA and G-TA. For fair comparison, we set the initial direction 9g of Sign-OPT and SVM-OPT to the direction of a randomly selected image of the target class. The detailed settings are presented in the appendix.
Target Models. In the CIFAR-10 dataset, we select four target models implemented using the (1) 272-layer SrramidNet+ShakelD
PyTorch framework
network (2yramidNet-2722) [19 39
trained using AutoAugment [13 (2) model obtained through a neural architecture search called GDAS [15: (3) wide residual network with 28 layers and 10 times width expansion (WRN-28) [I]];
and (4) a wide residual network with 40 layers (WRN-40) ET. In the ImageNet dataset, we select four target models from an off thel library containing tranned weights (1) Inception-v3 36. (2) Inception-v4 [35], (3) ResNet- 101 [20], and (4) SENet-154 (21).
Evaluation Metric. Following previous studies [40]. we report the mean & distortions as X Σxex ([|xat xll) under different query budgets, where X is the test set.
4.2
Comparisons with State-of-the-Art Methods
Results of Attacks against Undefended Models. Tables and show the experimental results on the ImageNet and CIFAR- 10 datasets. We derive two conclusions based on the results:
(1) We found that the experiments of CIFAR-10 requires a larger radius ratio r than that of ImageNet to achieve the satisfactory performance of G-TA. We speculate that the reason is that the target models of ImageNet have relatively flat decision boundaries.
(2) TA is more effective in targeted attacks, while the G-TA performs better in untargeted ones. This is because the adversarial region of the target class is narrower and more scattered, making the local classification decision boundary smoother, so that Theorem I holds and TA performs better.
In addition, one unique benefit of our approach is that it can be used as a performance enhanced plug-in when combining it with other ASSJA-baedd approaches (e.g., QEBA-S), Specifically. the method is change the jump directions of boundary samples of QEBA-S to the directions of the optimal tangent points. We present that "QEBA-S + TA" can further improve the performance of QEBA-S, as shown in Table
2 Pre-ttrained weights: http:://gtthhbccc//aaaaaa////slt
"Pre-trained httpss//ggttalecccmm///eeeepppep
pytorch

---

Table 1: Mean Eg distortions of different query budgets on the ImageNet dataset, where r' 1.1.
Target Model
Method
Targeted @2K
Allack @5K
Untargeted e2K
Atlack @5K
@:000
IK
@8K
@ @10K
@:300
@1K
@8K
@ e10K
A
111.798
108. 044
106.283
102.715
86.931
78.326
107,558
102.309
95,776
78.66
60,296
Sign-OPT IT
103.939
87.706
71.291
36.744
34.64 640
29.414
121.085
79.158
43.642
16.625
10.557
8.680
Inception-x3
SVM-OPT
101.630
82.950
67.965
46,275
306
121.135
66.027
36.763
15,736
10.501
8.789
HSTA 7
111.562
95. 295
82. 111
52.544
37 395
30.425
103.60
57.295
37.185
15.484
9.989
7:967
TA
103.781
80.327
42.121
30.866
25.566
94,752
52.523
15.040
9.748
7.793
G-TA
103.724
81.089
67. 168
42.434
31.011
25.587
94.972
$2.278
34.734
14,850
9.673
7.757
106.616
100.321
84.058
757
116.075
104.451
86.572
Sign-OPT 11
101.60
K5.731
69.719
46.416
34.957
30.004
132. 991
86.431
48.292
18.678
11.567
9.262
Inception-s4
SVM
99.856
81.342
66.
45.667
31.152
227
72.920
41.095
17.611
11,418
HSJA 7
109.670
93.916
80.937
52.358
37.773
30.958
100.727
63.731
42.290
17.936
11.367
8.911
TA
101.666
78.683
65.304
41.629
30.995
25. 25.958
101.207
58.616
40.314
17.639
11.304
8.907
G-TA
101.495
79.2.0
65. 888
42,002
30.963
25.847
101.324 324
58.718
40.106
17.296
11,032
8.691
81,090
77.723
76. 122
71,967
55,953
47.652
75.998
71.671
66,983
53.917
40.725
Sign-OPT IT
75.722
62.876
49. 191
30.155
21 333
17.672
70.035
47.705
17.314
10.890
6.643
5.245
SENet-154
SVM OPT LT
75,680
58.932
47.073
30.348
22.553
19.312
69.854
40.291
23,692
10.494
6,666
5,409
HSJA Z
77.035
63.488
51. 802
30. 38
19 680
16.261
71.248
38.035
34.895
10.218
5.855
4.842
TA 70,739
55.256
43.694
24.961
16.756
138876
65.589
35.689
24.037
10.039
5.774
4.766
G-TA
70.591
55.224
44.047
25.041
16.854
14.047
65.846
35.601
23.730
9.902
5.720
4.738
BA 4
81.565
77.9003
76.356
72.392
58.
51.679
64.1017
60.383
56.344
44,175
31.37T
Sign-OPT 11
76.732
63.939
51.231
32.439
23.160
19.248
56.244
38.282
21.985 21.985
10.048
7,050
6.050
ResNet-101
SVM-OPT
[1
77.031
61.417
49.842
32,806
24.553
20.964
55,894
32,638
19:409
9.830
7.185
6,281
HSJA 7
76.121
63.991
52.301
31,018
20.472
16.911
56.264
27.443
17.717
7.649
4.723
4.019
TA
72.434
57.969
47.142
27.699
18.788
15.414
53.197
26.777
17.651
7.730
4.822
4.107
G-TA
72.459
58.320
47.297
27.905
19.04
15.633
53.142
26.597
17.345
7.568
4.712
4.021
Table 2: Mean &g distortions with different query budgets on the CIFAR-10 dataset, where 1.5.
Target Model
Method
Targeted
Attack
Untargeted
Allack @5K
@ 300
@ IK
@2KK
85K
@8K
@ 10K
@ 300
@ 1K
@2K
@8K
10K
BA
8.651
8.073
8.013
6.387
4.189
3,333
5.636
4.725
4.414
2.750
1.696
Sign-OPT 11
8.279
6.331
4.250
1.718
0.960
0.718
4,387
2.334
1.178
0.403
0.267
0.226
PyramidNet.272
SVM OPT
9.207
6.801
4.530
2.010
1.207
0.947
4.481
2.318
1.093
0.414
0.276
0.236
HSJA
7.917
4.329
2.523
0.793
0.489
0.397
4.505
1.279
0.713
0.333
0.255
0.227
TA
7.943
4.267
2,488
0.809
0.503
0.406
4.256
1.275
0.710
0.329
0.253
0.226
G-TA
7,816
4.277
2.469
0.803
0.505
0.412
0.702
0.329
0.252
BA [4
8,487
7,885
7.821
6.034
3.632
2.703
2,717
2,514
2.373
1.642
1.106
Sign-OPT 11
8.372
6.514
4.351
1.827
0.987
0,711
4.917
4.159
3,260
1.352
0.452
0.250
GDAS
SVM-OPT 11
9.529
7.243
5.092
2.347
1.317
0.958
4.909
3,950
2.736
1.082
0.371
0.234
HSJA ?
7.714
3.566
1.966
0.591
0.365
0.301
2.188
0.756
0.483
0.261
0.208
0.189
7.674
3.529
1.946
0.585
0.366
0.302
0.774
0,485
0.206
G TA
7.697
3.558
1.959
0.583
0.361
0.298
2.161
0.745
0.476
0.255
0.204
0.185
BA A
8.688
8,046
7.984
5,786
2.486
1.355
4,425
3,648
3.455
1.543
0.832
Sign-OPT JT
8.258
5.576
3,260
1.087
0.593
0.459
3.093
1.494
0.828
0.319
0.239
0.213
WRN-28
SVM-OPT
9.516
5.968
3.744
1.367
0.728
0.553
2.977
1.466
0.723
0.325
0.245
0.221
IISJA
6.810
2.603
1.326
0.518
0.389
0.347
3.052
0.797
0.508
0.299
0.250
0.232
TA
6.802
2.556
1.311
0.519
0.394
0.353
2.974
0.785
0.496
0.293
0.249
0.233
G-TA
6.755
2.543
0.513
0.387
0.345
0.782
0,502
0.298
HA
8,658
8.014
7.953
5.738
2,484
1,566
4,377
3,586
3.367
1.487
0.821
Sign-OPT II
8.156
5.579
3,300
1.186
0.646
0.50]
4.754
3.239
1,885
0.311
0.226
0.201
WRN-10
SVM-OPT I
9.339
6,061
3.840
1.445
0.800
0.605
4.457
2.756
0.739
0.310
0.229
0,206
HSJA Z
6.909
2.648
1.330
0.528
0.400
0.357
2.992
0.777
0.498
0.290
0.242
0.225
TA
6.944
2.579
1.295
0.523
0.398
0.358
2.926
0.770
0.490
0.288
0.243
0.227
G-TA
6.783
2.605
1.320
0.535
0.403
0.361
2.952
0.772
0.492
0.288
0.241
0.223
Table 3: Experimental results of the combined method of QEBA-S and TA.
Target Model
Method
Targeted @22K
Attack @5KK
@ @0000
@ IK
@8K
@ 10K
Inception-43
QEBA-S 24
100.295
79.604
63.621
35.194
22.773
18.414
QEBA-S + TA
104.490
75.622
59.836
33.112
22.329
17.799
Inception-v4
QEBA 24
97.773
77.347
62.451
35.275
23.204
19.002
QEBA-S TA
101 848
73.838
58.554
33.288
23.160
18.736
154
QEBA [24
72831
55.367
42.674
21.988
13,888
11,210
QEBA-S
76.547
52.269
39.740
20.608
13,873
11,016
ResNet-101
QEBA-S [24]
75.567
57.929
44,983
23,209
14,402
11.467
QEBA-S + TA
78.709
53.917
41.245
21.198
13.856
10.773
Results of Attacks against Defense Models. We conduct the experiments of untargeted attacks
on defense models. Fig- 5 shows the experimental results on the CIFAR-I0 dataset. We select defense models: (1) model obtained through adversarial training, abbreviated as AT [29 : (2) an

---

GITA
G TA
G-TA TA
Mean & Distortion
MBJA
Mean Distortion
HBJA
Mean Distontion
Meuun 5 Distortion
BAg
SVACPPT Sign-OPT
SUR-OPT Sign-OPt
SUN-OPT Sigh-OPP
IX 2< 14 or BK
10C
15
26 16
26 12 dr Number Queries
E< aK w Ie
26 1E 18 2c we
Queries
Queries
(a) AT (c 8/255)
(b) TRADES (f 8/255)
JPEG
(d) Feature Distillation
Figure 5: Experimental results of the attacks against defense models with the backbone of ResNet-55.
improved AT that optimizes a regularized surrogate loss, named as TRADES :2: (3) an image- transformation-asse based defense called JPEG [88; and (4) DNN -oientree compression defense called Feature Distillation [27]. All defense models adopt ResNet-50 as the backbone. Previous studies [43 have shown that AT and TRADES have the issue of robust overfitting, which leads to significant increase in the curvature of the classification decision boundary. Figs. [aland 55 show that G-TA outperforms TA when attacking AT and TRADES. This advantage also demonstrated in attacking other defenses (e.g., Figs. and and 5c), proving the effectiveness G-TA in attacking defense models.
4.3 Comprehensive Understanding of Tangent Attack
In the ablation studies, we conduct the experiments of the targeted attacks on the ImageNet dataset to understand our approach depth, and the target model is ResNet-50. The results are shown Fig. 6
Initialization. Our algorithm starts with an image Xn selected from the target class, and we study three selection strategies: (1) randomly selected image, (2) the image with the shortest distance to the original image, and (3) the image with the longest distance to the original image. Fig. 6a shows that the strategy of (2) achieves the best performance.
Radius Ratio. Fig. 6b shows that the performance of G-TA is not sensitive to the radius ratio r.
Jump Direction. Fig. 60 shows the effects of different jump directions. RandomHSIA is variant of HSJA which adopts a random vector that satisfies (r, u) > as the jump direction. Fig. 6c verifies the benefit of jumping to the optimal tangent point.
Initial Batch Size. In general, Fig. 6d shows that smaller Bo performs better since it saves queries.
But By = 5 performs worse than Bg = 30 because it uses too few samples for gradient estimation.
Mean Distortion
Image
maximum distortion
HSJA
RendsmilSjA
radius r2t r-17
8. 70
radius ratur 2.0
dg 100
2030
Mean
150
200
CRC Number of Queries
DORCICCROOOO Number Queries
Number of Querees
Number of Quenes
(a) initial X selection
(b) radius ratio Figure Experimental results of ablation studies.
(c) jump directions
(d) initial batch size Bo
Conclusion
In this paper, we propose new geometric-basee method for query-efficient hard-label black-box attacks. Our method relies on the observation that the minimum & distortion can be obtained by searching a boundary point along tangent line of a virtual hemisphere. We offer a closed-form solution for computing the optimal tangent point and provide formal proof of its correctness. We further propose generalized method that replaces the hemisphere with semi-ellipsoid to adapt to the target models with curved decision boundaries. Lastly, we evaluate our approach through extensive experiments and show its superior performance compared with baseline methods.
10

---

Acknowledgments
This research is partially supported by the National Key R&D Program of China 2219YFB1405500 and TC190A4DA/3, the National Natural Science Foundation of China (Grant Nos. 62021002, 61972221). Yisen Wang partially supported by the National Natural Science Foundation of China under Grant 62006153, and Project 2020BD006 supported by PKU-Baidu Fund.
References
[1] Ilyas Andrew, Engstrom Logan, Athalye Anish, Lin Jessy. Black-box adversarial attacks with limited queries and information. In International Conference on Machine Learning, pages 2142-2151, 2018.
[2] Yang Bai, Yuyuan Zeng, Yong Jiang, Yisen Wang, Shu-Tao Xia, and Weiwei Guo. Improving query efficiency of black-box adversarial attack. European Conference on Computer Vision. pages 101-116. 2020.
[3] Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box attacks on deep neural networks using efficient query mechanisms. In European Conference on Computer Vision, pages 2018.
[4] Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: reliable attacks against black-box machine learning models. International Conference on Learning Representations, pages 1- 12, 2018.
[5] T. Brunner, E. Diehl, M. T. Le, and A. Knoll. Guessing smart: biased sampling for efficient black-box adversarial attacks. In JEEE/CVF International Conference on Computer Vision, pages 4957-4965, 2019.
[6] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy, pages 39-57, 2017.
[7] Jianbo Chen, Jordan Michael I., and Wainwright Martin J. HopSkiplumpAttack: a query-efficient decision- based adversarial attack. In IEEF Symposium on Security and Privacy, pages 1277-1294, 2020.
[8] Jinghui Chen and Quanquan Gu. RayS: a ray searching method for hard-label adversarial attack. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, page 1739-1747, 2020.
[9] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In ACM Workshop on Artificial Intelligence and Security, pages 15-26, 2017.
[10] Minhao Cheng, Thong Le, Pin-Yu Chen, Huan Zhang, JinFeng Yi, and Cho-Jui Hsich. Query-efficient hard-label black-box attack: an optimization-bast based approach. International Conference on Learning Representations, pages 1-14, 2019.
[11] Minhao Cheng, Simranjit Singh, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsich. Sign-OPT: a query-efficient hard-label adversarial attack. In International Conference on Learning Representations, pages 1-16, 2020.
[12] Shuyu Cheng. Yinpeng Dong. Tianyu Pang. Hang Su, and Jun Zhu. Improving black-box adversarial attacks with transfer-hased prior. In Advances Neural Information Processing Systems, pages 10934-10944, 2019.
[13] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. AutoAugment: learning augmentation strategies from data. IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 113-123, 2019.
[14] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: large-scale hicrarchical image database. IEEE Conference on Computer Vision and Pattern Recognition, pages 148-255, 2009.
[15] Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four GPU hours. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1761-1770, 2019.
[16] Yinpeng Dong. Hang Su, Baoyuan Wu, Zhifeng Li, Wei Liu, Tong Zhang, and Jun Zhu. Efficient decision- based black-box adversarial attacks on face recognition. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7714-7722, 2019.
[17] Alhussein Fawzi, Seyed- Wryed-Mohsen Moosavi-Dezfooli,, and Pascal Frossard. Robustness of classifiers: from adversarial to random noise. In Advances in Neural Information Processing Systems, page 1632-1640) 2016.
11

---

[18] Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using input transformations. In International Conference Learning Representations, pages 1-12, 2018.
[19] Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In IEEE Conference on Computer Vision and Pattern Recognition, pages 5927-5935, 2017.
[20] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Patter Recognition, pages 770-778, 2016.
[21] Jie Hu, Li Shen, and Gang Sun. Squeeze-and-excittion networks. In IEEE/CVF Conference Computer Vision and Pottern Recognition, pages
2018.
[22] Andrew Tlyas, Logan Engstrom, and Aleksander Madry. Prior convictions: black-box adversarial attacks with bandits and priors. International Conference on Learning Representations, pages 1-25, 2019.
[23] Alex Krizhevsky, Learning multiple layers of features from tiny images. pages 1-60, 2009.
[24] Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. QEBA: Query-efficient boundary-based blackbox attack. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1221-1230 2020.
[25] Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. In International Conference on Learning Reprexentations, pages 1-24, 2017.
[26] Yujia Liu, Seyed- Mohsen Moosavi-Dezfooli, and Pascal Frossard. A geometry-inspired decision-based attack. In IEÉE/CVF International Conference on Computer Vision, pages 4889-4897, 2019.
[27] Zihao Liu, Qi Liu,, Tao Liu, Nuo Xu. Xue Lin, Yanzhi Wang, and Wujie Wen. Feature distillation: DNN- oriented jpeg compression against adversarial examples. In IEEE/CVF Conference Computer Vision and Pottern Recognition, pages 860-868, 2019.
[28] Chen Ma, Chen, and Jun-Hai Yong. Simulating unknown target models for query-efficient black-box attacks. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11835- 11835-11844, 2021.
[29] Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, pages 1-28, 2018.
[30] Thibault Maho, Teddy Furon, and Erwan Le Merrer. SurFree: a fast surrogate-free black-box attack. In IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 10430-10439, 2021.
[31] Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. In International Conference Machine Learning, pages 4636-4645, 2019.
[32] Seyed-Mohsen Moosavi-Dezfoo Dezzooli,, Alhussein Fawzi, and Pascal Frossard. DeepFool: simple and accurate method fool deep neural networks. IEEE Conference on Computer Vision and Pattern Recognition, pages 2574 258222522222 2016.
[33] Ali Rahmati, Seyed- Mohsen Moosavi-Dezfoolii Pascal Frossard, and Huaiyu Dai. GeoDA: a geometric framework for black- box adversarial attacks. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2020.
[34] Yucheng Shi, Yahong Han, and Qi Tian. Polishing decision-basel adversarial noise with customized sampling. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1030-1038, 2020.
[35] Christian Szegedy, Sergey Toffe, Vincent Vanhoucke, and Alexander Alemi. Inception-v4, inception-resnet and the impact of residual connections on learning. In AAAI Conference on Artificial Intelligence, page 4278-4284, 2017.
[36] Christian Szegedy, Vincent Vanhoucke, Sergey Toffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In IEEE Conference on Computer Vision and Pattern Recognition, pages 222188226622222 2016.
[37] Xin Wang. Jie Ren, Shuyun Lin, Xiangming Zhu, Yisen Wang, and Quanshi Zhang A unitied ap- proach to interpreting and boosting adversarial transferability. In International Conference on Learning Representations, pages 1-35, 2021.
12

---

[38] Dongxian Wu, Yisen Wang. Shu-Tao Xia, James Bailey, and Xingjun Ma. Skip connections matter: the transferability of adversarial examples generated with ResNets. In International Conference Learning Representations, pages 1-15, 2020.
[39] Yoshihiro Yamada, Masakazu Iwamura, Takuya Akiba, and Koichi Kise. Shakedrop regularization for deep residual learning. IEEE Access, 7: 1188666-18666666 2019.
[40] Ziang Yan, Yiwen Guo, Jian Liang, and Changshui Zhang. Policy-driven attack: learning query for hard-label black-box adversarial examples. International Conference on Learning Representations, pages 1-15, 2021.
[41] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference, pages 87.1-87.12, 2016.
[42] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent Ghaoui, and Michael Jordan. Theo- retically principled trade-off between robustness and accuracy. In International Conference on Machine Learning, pages 1472-7485 2019.
[43] Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry- aware
adversarial training. In International Conference on Learning Representations, pages 1-29, 2021.
13


Reviews:
[{"review_id": "nrvRmZN8Fi", "reviewer": "Reviewer_geDq", "summary": "This work proposes a new type of hard-label attacking method. Hard-label attacking methods only allow access of the top-1 predicted labels. This method is based on geometric properties, i.e., tangent points to reduce the l2 distortion after attacks. The method is shown to be superior compared with the existing hard-label attacking methods. The authors also studied the performance under four different defense frameworks, all of which prove the superiority of the proposed method. \n\n\n   \n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Main concerns:\n\n1. There is something wrong with the fonts and the styles. The authors should have a look and made corrections. \n\n2.  Although the author claims it is hyperparameter-free, $r$ is still one of the hyper-parameter (although empirically set in the article). If one wants to use the method on other datasets, should the value of $r$ change?\n\n\n----\n## Post-Rebuttal Update\n----\nI thank the authors for responding to my questions. I will go through others' comments and make discussions but currently, I will keep my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No analysis has been made. \n\n----\n## Post-Rebuttal Update\n----\n\nLimitation and Societal Impact are addressed in Appendiex. ", "review_text": "", "extra_scores": {"ethical_concerns": " ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "mw7vJ_p4KbS", "reviewer": "Reviewer_qsse", "summary": "The paper proposes Tangent Attack, a decision based adversarial attack which can be seen as an improvement of HopSkipJumpAttack [6]: it progressively reduces the norm of the adversarial perturbations according to a method inspired by the geometry of the decision boundary in the input space. This allows to achieve adversarial points with lower distortion than HSJA with the same amount of queries of the classifiers, i.e. better query efficiency.", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths\n- The motivation of the method and the geometric approach are simple and reasonable.\n\n- The improvement upon HSJA is consistent across models and datasets.\n\nWeaknesses\n- The main concern is about the experimental evaluation: the authors cite many related works (QEBA, SurFree, GeoDA) which are improvements of HSJA, as acknowledged, but do not include them in the experimental comparison. Since all those methods outperform HSJA, Tangent Attack needs to be compared to them, especially given that its improvement over HSJA is often not large.\n\n- Similarly, for the $\\ell_\\infty$-threat model RayS should be included.\n\nOther comments\n- The template, especially the font, seems to be not the original one.\n\n- The target classes for targeted attacks are usually sampled randomly, not as the next one.\n\nOverall, the method is quite reasonable and well presented, but the experimental evaluation not sufficient.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think both are sufficiently discussed.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "dnnFYKQnJeW", "reviewer": "Reviewer_ZX4s", "summary": "This paper discovers that searching the optimal tangent point of a virtual hemisphere could help find minimal adversarial distortion; therefore, this paper proposes an effective method of hard-label attack", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Pros. \n\n1 The paper is well-written and well-organized. In particular, I like the related work part, which is well-organized. \n\n2 The experiments on standard models and defensive models exhibit the efficacy of the proposal. \n\nComments. \n\nI have a question about the assumption of the low-curvature smooth surface. \nIt is well known that traditional adversarial training techniques such as AT and TRADES have the undesirable issue of robust overfitting. \nWhen robust overfitting occurs, the decision boundary becomes more and more curved [1]. Would the overfitted model severely violate the assumption that will weaken the efficacy of the proposal? \nAuthors may try the friendly adversarial training [2], where it used curriculum training techniques to elude the issue of robust overfitting. \n\n[1] Geometry-aware instance-reweighed adversarial training, in ICLR 2021. \n\n[2] Attacks which do not kill training make adversarial learning stronger, in ICML 2020.\n\n######################## post rebuttal ######################\nI have read the author(s)' response and other reviewers' comments. I maintain my scores. Thanks. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "LJoOgos6Sj", "reviewer": "Reviewer_c1JB", "summary": "In this paper, the authors proposed a new geometric-based method for query-efficient hard-label black-box attacks. The proposed method relies on the observation that the minimum l2 distortion can be obtained by searching a boundary point along a tangent line of a virtual hemisphere. The authors offered a closed-form solution for computing the optimal tangent point and provided a formal proof of its correctness. Lastly, the authors evaluated the proposed approach through extensive experiments.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "1. This paper proposed a geometric-based method to compute the optimal perturbation direction. However, it seems that the authors assume the decision boundary is a hyperplane H and the gradient direction u is known. This raises my two concerns. First, H can be seen as a hyperplane only when we are considering a very small local region. Yet it is not clear whether the actual radius used in the algorithm is small enough such that this assumption holds. Second, the algorithm can only obtain an estimated gradient and using that could lead to very wrong results in computing the optimal tangent direction (as this gradient estimation is well-known to be not precise even using large B). As a motivation for the proposed method, these two assumptions sound ok but the authors might want to further verify the actual conditions in the experiments to make them more convincing.\n\n2. Another downside is that the proposed method will need to tune extra parameters like r compared to other baselines. The authors might also want to show an ablation study on r.\n\n3. In the experiments part, the authors only consider the L2 norm threat model. I think there is no obstacle here to also apply the proposed method in Linf norm settings? (correct me if I miss something here). It would be more comprehensive to also see the Linf norm experiments and compare them with SOTA methods like HSJA/RayS. Especially for the defended models, as they are not trained in the L2 threat model, which makes the results less representative.\n\n4.  Also in the experiments (especially CIFAR10), the advantages of the proposed method are marginal or even non-exist compared with other baselines when the number of queries is sufficient. Here the author only considered 10K as the maximum query number. It is better to show whether the proposed method still holds up the position with maximum of 20k or 50k queries. It would also be nice to have some plots instead of tables to show this one.\n\n=====after rebuttal=========\nI thank the authors for their detailed responses. And I appreciate all the extra experiments conducted by the authors. Yet I feel that the proposed method is not better than RayS or QEBA-S on different settings (in R2's comments). And comparing to HSJA, the advantages get vanished when the maximum query number is large or dealing with defended Linf norm models. Therefore, I will keep my score unchanged.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "see above, societal impact not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0tzCajyvXjb", "reviewer": "Reviewer_qy3F", "summary": "This paper proposes a new method for performing hard-label black-box attacks, similar to the HopSkipJump Attack but modified with the observation that the gradient direction is not always the best direction to move in when trying to minimize mean attack distortion. Instead, under some assumptions about the decision boundary, the paper derives an update direction based on an optimal tangent point on the semi-circle around the current attack iterate. The paper then implements the corresponding algorithm and shows that it indeed lowers mean distortion on the CIFAR-10 and ImageNet datasets at a variety of query budgets. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The proposed method seems reasonable and to my knowledge the given proofs are correct. I am not an expert in geometry, however, so I can't judge the technical depth or novelty of the theoretical contributions. On the empirical side, the evaluation seems solid (modulo some concerns listed below) and the method does improve on competing hard-label attack algorithms, which lends some credence to the approach. My main comments and questions are below:\n\nPresentation/Clarity:\n\n- L48: The paper claims that \"although Rahmati et al. claimed that GeoDA is grounded on the geometric properties of DNNs, it assumes that the decision boundary of DNNs is flat in the vicinity of data samples\"---however, isn't this flatness assumption also made by the proposed hemisphere attack as well? I think the authors should either better distinguish their method from GeoDA or just remove the corresponding claim from the paper.\n- Fig. 1: What is the motivation for the oddly-shaped decision boundary? In particular, what purpose does the upper decision boundary line serve? In my opinion this figure should be as simple as possible since it is the reader's first introduction to the main idea, so any lines that can be removed should be removed.\n- Proof of Theorem 1: Any assumptions made in the proof of Theorem 1 (in particular, Assumption B.1 in the appendix) should be stated in the main text (and explained in intuitive terms if possible) rather than in the proof itself.\n- I thought the layout of the paper was good, but local readability is hindered a bit by some grammatical/spelling/phrasing issues (e.g., missing articles, missing pluralizations, tense agreement, etc). These did not affect my score but I think the clarity of the paper could be improved with some proofreading.\n- The legend of Figure 5 is too small/hard to read\n- Again minor and did not affect my score, but the entire paper is typeset in an incorrect font (you probably have a stray \\usepackage in the LaTeX source). \n\n\nExperimental:\n- Rather than just the average l2 distortion, I think the paper should also show the distribution of l2 distortions across test images---i.e., is it the case that the l2 distortions found by the semi-circle attack are uniformly better, or is it just the other attacks \"fail\" on some images leading to very high mean distortions?\n- The paper mentions that HSJA was re-implemented in PyTorch for consistency which is reasonable, but as a sanity check the appendix should include a comparison of the re-implemented HSJA and the original HSJA codebase on the same models (since it's a black-box attack, it should be easy to use a PyTorch model [or any arbitrary function] in fact) in conjunction with the original code.\n- I like the ablation studies that the authors performed in Figure 5! In Figure 5c it seems like decreasing the batch size monotonically improves the performance of the attack, up to the smallest shown batch size. Did the authors try lowering the batch size even further, e.g., to 15 or 10? It would be interesting to see at what point the stability from batching outweighs the redundant queries.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors dedicate an entire appendix section to discussing social impact, and also have a detailed limitations section (in the Appendix). If space permits it would be nice to see some of these discussed in the main paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a slightly novel approach for black-box adversarial attacks, with extensive sets of experiments that seem to confirm some performance benefits compared to the related work. This one should be better positioned (e.g., targeted vs non-targeted attack settings), and the active discussion with the reviewers should help in clarifying the true benefits of the proposal in the revision of the manuscript towards any eventual publication. 
Decision: Accept (Poster)