Finding Optimal Tangent Points for Reducing Distortions of Hard-label Attacks
Year: 2022

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 `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 CIFAR10 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 at https://github.com/machanic/TangentAttack.

heading: 1 Introduction
text: 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 [6, 29, 32] have been proposed, and they can compute the gradients w.r.t. the target model’s input images to 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 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, 38] 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 of the target model for crafting adversarial examples. In the score-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 (NeurIPS 2021).
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 a high-dimensional combinatorial optimization problem, which is often challenging.
To reformulate the attack as a real-valued continuous optimization problem, OPT [10], Sign-OPT [11], and RayS [8] focus on minimizing an objective function g(θ), which is defined as the distance from the original image to the nearest adversarial example along the direction θ. However, when attacking complex models, it may be difficult to find a suitable direction θ along which adversarial examples exist.
Boundary Attack (BA) [4], HopSkipJumpAttack (HSJA) [7], QEBA [24], qFool [26], and Policy Driven Attack (PDA) [40] eliminate the search of 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 to 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 a reinforcement learning framework to train a 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 a geometrically critical issue, i.e., u is not the optimal direction to be followed (Fig. 1). We could explore better search directions at each attack iteration.
To find the optimal search direction for minimizing the distortions of attack, we propose a new geometric-based approach whose motivation is illustrated in Fig. 1. We construct a virtual semicircle B centered at xt−1 to indicate all possible locations that xt−1 can reach along different directions, and the radius ofB limits the range of updates for successful attacks. It is easy to observe that moving along the tangent line can reach the nearest location of the decision boundary to the original image x, thereby producing the adversarial example with the minimum distortion. In real attack scenarios, the image data reside in a high-dimensional space, and the semicircle becomes a 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 be obtained by searching the optimal tangent point of a 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 a formal proof of its correctness.
3. To improve robustness, we further propose a generalized method that replaces the hemisphere with a semi-ellipsoid to adapt to the target models with curved decision boundaries.
4. Extensive experiments conducted on the CIFAR-10 [23] and ImageNet [14] datasets demonstrate the effectiveness of our approach.

heading: 2 Related Work
text: 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–3, 9, 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 x0 and attempts to find a optimal direction θ to reach the adversarial example. OPT [10] searches an optimal θ to minimize the distance from x0 to the nearest adversarial example. Sign-OPT [11] 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 θ. However, RayS is only applicable to the untargeted attack under the `∞ norm because it is difficult to find a 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 a large perturbation or an 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 [5] reinterprets BA as a biased sampling framework and incorporates different biases to improve the query efficiency. HSJA [7] 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 [30] 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 [40] uses a reinforcement learning framework to train a policy network to predict promising directions. However, PDA requires a 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 is that they only support untargeted attacks. Because moving the original image far enough in any direction can always make it escape the non-adversarial region in untargeted attacks. However, in targeted attacks, it is difficult to find a suitable direction along which the target class’s region exists. In contrast, our approach supports all types of attacks, and we exploit the geometric characteristics of the decision boundaries of DNNs to boost the attack.

heading: 3 The Proposed Approach

heading: 3.1 The Goal of Hard-label Attacks
text: Given a target model f : Rd → Rk and a benign image x ∈ [0, 1]d that is correctly classified using f , the goal of the adversary is to slightly perturb x into xadv, such that f(xadv) outputs incorrect prediction. In the hard-label attack, the adversary can only observe the top-1 predicted label of f , denoted as ŷ = arg maxi f(xadv)i. We define an indicator function φ(·) of a successful attack:
φ(xadv) :=  1 if ŷ = yadv in the targeted attack,
or ŷ 6= y in the untargeted attack, 0 otherwise,
(1)
where y ∈ R is the true label of x and yadv ∈ R is a predefined target class label. In this study, we focus on generating an adversarial example xadv that satisfies φ(xadv) = 1, such that the distortion d(xadv,x) := ‖xadv − x‖p is minimized. This goal can be formulated as the optimization problem:
min xadv d(xadv,x) s.t. φ(xadv) = 1. (2)

heading: 3.2 Motivation
text: Most recent attacks belong to the second category (Section 2) follow a common procedure: it starts from an adversarial image yet not close enough to the benign one, then it iteratively searches for a
closer adversarial image. Let us take a typical attack HSJA [7] for example (Fig. 1). First, the attack initializes the adversarial example by using an image of the target class (in a 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 boundaryH , denoted as xt−1. Then, the algorithm iteratively performs three steps to update xt−1: estimating gradient u at H by sampling many probes around xt−1; jumping to the point g along the direction u with the step size determined by the geometric progression; and mapping g onto H 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 we can find a better boundary point xt by connecting x to a certain point on the semicircle B and then taking the intersection point on H . Fig. 1 shows that the tangent point k is the optimum update because it leads to the minimum distortion of the attack.
3.3 Definition of Optimal Tangent Points
There is some experimental evidence that the decision boundaries of DNNs are smooth surfaces with the low curvature [17, 33]. Based on this observation, we approximate the local decision boundary with a hyperplane H . Fig. 3 illustrates our problem in three-dimensional space. We will derive our algorithm from R3 and show that it can be directly extended to higher-dimensional spaces. Lastly, we address the case of curved decision boundaries.
As described in Section 3.2, xt−1 denotes the boundary sample that already lies on the decision boundary. We create a virtual hemisphere B centered at xt−1 with a radius R, which is an estimation of the safe region where we can search for adversarial examples. In the targeted attack, B represents the current estimation of the target class region around xt−1. Ideally, B is small enough to be fully contained in the target class’s region, i.e., φ(x′) = 1 for ∀x′ ∈ B.
Then, we need to find a point on B 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 ≥ 3, there are infinitely many tangent lines of B passing through x which create infinitely many tangent points on B, shown as the red points in Figs. 2 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.
Formally, let k be any point on the surface of B, u be the approximate gradient of H estimated at xt−1, and xt be the intersection of H and the line passing through x and k, we have the following theorem.
Theorem 1 Let H , u, k, x, and xt−1 be defined above, then the distance ‖x− xt‖ is minimized if k is the optimal solution of the following constrained optimization problem:
arg max k
〈k− xt−1,u〉 (3)
s.t. 〈k− xt−1,x− k〉 = 0, (4) ‖k− xt−1‖ = R, (5) 〈k− xt−1,u〉 ≥ 0. (6)

heading: In particular, the optimal k is in the plane spanned by u and x− xt−1.
text: The objective function of Eq. (3) is to maximize the projection of the vector k− xt−1 onto u, which is equivalent to finding k that is farthest away from H . The first constraint ensures that k is a tangent point. The second constraint indicates k is on the surface ofB. The last constraint states that k cannot appear on the same side of H as x, which is always satisfied if ‖ΠH(x − xt−1)‖ ≥ R, where the notation ΠH : Rn 7→ H denotes the orthogonal projection from Rn onto the hyperplane H . If there is no feasible solution, then our algorithm (Algorithm 1) reduces the radius R to guarantee that the last constraint is always satisfied. The formal proof of Theorem 1 is presented in the appendix. Here,
we refer the readers to Fig. 2 for an intuitive geometrical explanation. Eq. (3) is computationally expensive to solve in the high-dimensional space. Fortunately, we show there actually exists a closed-form solution.

heading: 3.4 Closed-Form Solution of the Optimal Tangent Point
text: The main intuition of the derivation is illustrated in Fig. 3, which shows an example in R3. For ease of presentation, we move xt−1 to 0. The known variables are x, xt−1, the unit normal vector u of hyperplane H , and the radius R. We need to solve for the unknown k. Let V = span({x,u}) be the plane spanned by x and u. According to Theorem 1, we know k ∈ V . Let us denote the angle between x and H as α, the angle between x and k as β, and the angle between k and H as γ. Then, β = α + γ because all three points x, k, and xt−1 are on the same plane V . Because the angle between x and u is π / 2 + α, we have
〈x,u〉 = ‖x‖ · ‖u‖ · cos(π 2 + α) = ‖x‖ · ‖u‖ · (− sinα) . (7)
Then we have sinα = − 〈x,u〉‖x‖·‖u‖ and cosα = √ 1− sin2 α = √ ‖x‖2·‖u‖2−〈x,u〉2 ‖x‖·‖u‖ . By the con-
straint (4), x− k is orthogonal to k. Thus, we have cosβ = R / ‖x‖ and sinβ = √
1− cos2 β =√ ‖x‖2 −R2 / ‖x‖. Then sin γ and cos γ can be derived as functions of α and β from basic facts of trigonometric functions: sin γ = sin(β − α) = sinβ cosα− cosβ sinα, cos γ = cos(β − α) = cosβ cosα+ sinβ sinα. (8)
Now, let k′ ∈ H be the orthogonal projection of k onto the plane H . The distance between k and k′ is denoted as h (Fig. 3). Then h = R · sin γ = R · (sinβ cosα− cosβ sinα). To derive k′, let us denote x′ as the orthogonal projection of x onto z axis. So we have x′ = 〈x,−u〉 · (−u) / ‖u‖2 = 〈x,u〉 · u / ‖u‖2. Then, because k′ and x− x′ are on the same direction, we have
k′
‖k′‖ =
x− x′
‖x− x′‖ . (9)
Now, ‖k′‖ = R · cos γ and x′ = 〈x,u〉 · u / ‖u‖2 are plugged into Eq. (9), and k′ is obtained as
k′ = x− x′ ‖x− x′‖ · ‖k′‖ = x− 〈x,u〉 · u / ‖u‖ 2 ‖x− 〈x,u〉 · u / ‖u‖2‖ ·R · cos γ. (10)
Therefore, k can be derived as
k = k′ + h · u = x− 〈x,u〉 · u / ‖u‖ 2
‖x− 〈x,u〉 · u / ‖u‖2‖ ·R · cos γ + h · u. (11)
Finally, because xt−1 has been moved to the origin, we need to move k back by adding xt−1.
We remark that although the above derivation is illustrated in R3, it can be directly applied to higher dimensions. The reason is Theorem 1, which essentially reduces any dimension space to R2: to find the optimal k, we only need to focus on the plane V spanned by u and x− xt−1.

heading: 3.5 Generalized Tangent Attack
text: 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 R of the hemisphere: as long as R 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 xt and xt−1 is proportional to 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 in a high-dimensional space, the important thing for our algorithm is only the situation in the two-dimensional plane spanned by x and u. In particular, if the decision boundary is “downward” curved (as opposed to the example in Fig. 4a), then searching along the tangent line is still a 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 a 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, u and v := (x − 〈x,u〉 · u / ‖u‖2) / ‖x − 〈x,u〉 · u / ‖u‖2‖ form an orthogonal basis of the plane V , then x can be identified with coordinates (x0, z0), i.e., x = x0v + z0u. Let θ denote the angle between the vector x and the vector −u, i.e., θ = arccos ( 〈x,−u〉 ‖x‖·‖u‖ ) . Then (x0, z0) = (‖x‖ · sin θ,−‖x‖ · cos θ). Consider the projection of the ellipsoid on V (which is an ellipse), we denote L as its radius along the direction of u, and S as its radius along the direction of v. Because the optimal tangent point k lies in the plane V , k can also be identified as k = xkv + zku, and we only need to solve for the unknown (xk, zk).
The ellipse is characterized by the equation x2 / S2 + z2 / L2 = 1, thus the tangent point k satisfies x2k / S 2 + z2k / L 2 = 1. Now we view z as a function of x, and take the derivative w.r.t. x at both sides of the equation to get the following formula: 2xk S2 + 2zk L2 · dz dx ∣∣∣∣ x=xk = 0. (12)
Thus, we have the slope of tangent line at k be dzdx ∣∣ x=xk = −xkL 2 zkS2 . Therefore, the tangent line can be written as z − zk = −xkL 2
zkS2 (x − xk). Since the tangent line passes through x, we know
z0 − zk = −xkL 2
zkS2 (x0 − xk). In summary, we can obtain the following system of equations: L2x2k + S 2z2k − xkx0L2 − z0zkS2 = 0,
x2k S2 + z2k L2 = 1. (13)
In Eq. (13), the known variables are L, S, x0 and z0, and the unknown variables that we need to solve for are xk and zk. In general, there are two solutions for Eq. (13), i.e., k and k′ depicted in Fig. 4b. Apparently, the solution of the optimal tangent point should satisfy zk > 0, so the one of two solutions in which zk > 0 should be picked: xk = S2 ( L2 − z0 · L2S2z0+L 2x0 √ −L2S2+L2x20+S2z20 L2x20+S 2z20 ) L2 · x0 , zk = L2S2z0 + L 2x0 √ −L2S2 + L2x20 + S2z20
L2x20 + S 2z20
.
(14)
Finally, the optimal tangent point k is obtained via k = |xk| · x−〈x,u〉·u/‖u‖ 2
‖x−〈x,u〉·u/‖u‖2‖ + zk · u. In the implementation, the value of L is determined in the same way as the radius R in TA (the hemisphere version). So we fix L = R, and use a hyperparameter r = L/S to control the value of S. Imagine that in the case of R3, the semi-ellipsoid becomes “slender” by setting r > 1, thereby adapting to the decision boundary of curved surface while preserving a relatively large step size.

heading: 3.6 The Complete Algorithm
text: TA (the hemisphere version) and G-TA (the semi-ellipsoid version) can be combined into one algorithm process, which is shown in Algorithm 1. It first performs a binary search to map the initial sample x̃0 to the decision boundary. Note that the binary search step always maps any xadv to the adversarial side of H that satisfies φ(xadv) = 1, hence the attack success rate is always 100%. Then, it performs a for loop of T iterations to find the adversarial example that is close to x. In the first iteration, we sample B0 probes around the boundary sample to estimate the gradient, which is increased to B0 √ t at the t-th iteration. This is because the error of gradient estimation in the later iterations has a greater impact on the attack performance, so using more samples can reduce the estimation error. Then, a 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 1 uses the binary search method to map k back to the classification decision boundary to end this iteration.
Algorithm 1 Tangent Attack Input: benign image x, attack success indicator function φ(·) defined in Eq. (1), initial batch size B0, iteration T , mode m ∈ {semi-ellipsoid, hemisphere}, radius ratio r. Initialize x̃0 that satisfies φ(x̃0) = 1; x0 ← BinarySearch(x̃0,x, φ); . boundary search d0 = ‖x0 − x‖; for t in 1, . . . , T do
Sample Bt ← B0 √ t random vectors to estimate the gradient u;
Initialize R← dt−1/ √ t; . the initial radius while true do Compute the optimal tangent point k based on Eq. (11) if m = hemisphere else Eq. (14); R← R2 ; . search the radius, and we set L = R,S = L r if m = semi-ellipsoid
if φ(k) = 1 then break;
end if end while k← Clip(k, 0, 1); xt ← BinarySearch(k,x, φ); . boundary search dt = ‖xt − x‖;
end for

heading: 4 Experiment

heading: 4.1 Experimental Setting
text: Datasets. TA and G-TA are evaluated on two datasets, namely CIFAR-10 and ImageNet with the image resolutions of 32×32×3 and 299×299×3, respectively. We randomly select 1,000 correctly classified images from their validation sets for experiments.
Method Setting. The initial batch size B0 is set to 100, which means the algorithm samples 100 probes for estimating a gradient at the first iteration. The threshold γ that controls the termination of the binary search is set to 1.0 in the CIFAR-10 dataset and 1,000 in the ImageNet dataset. The radius 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 y 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 `2 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-art performance, including Boundary Attack (BA) [4], Sign-OPT [11], SVM-OPT [11], and HopSkipJumpAttack (HSJA) [7]. HSJA is adopted as the baseline, whose hyperparameters are set to be the same with ours (e.g, the same initial batch size B0 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 HSJA, BA, TA and G-TA. For fair comparison, we set the initial direction θ0 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 PyTorch framework2: (1) a 272-layer PyramidNet+ShakeDrop network (PyramidNet-272) [19, 39] trained using AutoAugment [13] ; (2) a model obtained through a neural architecture search called GDAS [15]; (3) a wide residual network with 28 layers and 10 times width expansion (WRN-28) [41]; and (4) a wide residual network with 40 layers (WRN-40) [41]. In the ImageNet dataset, we select four target models from an off-the-shelf library containing pre-trained weights3: (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 `2 distortions as 1 |X| ∑ x∈X(‖xadv − x‖) under different query budgets, where X is the test set.

heading: 4.2 Comparisons with State-of-the-Art Methods
text: Results of Attacks against Undefended Models. Tables 1 and 2 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 1 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 HSJA-based approaches (e.g., QEBA-S). Specifically, the method is to 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 3.
2Pre-trained weights: https://github.com/machanic/SimulatorAttack 3Pre-trained weights: https://github.com/Cadene/pretrained-models.pytorch
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-10 dataset. We select 4 defense models: (1) a model obtained through adversarial training, abbreviated as AT [29]; (2) an
improved AT that optimizes a regularized surrogate loss, named as TRADES [42]; (3) an imagetransformation-based defense called JPEG [18]; and (4) a DNN-oriented 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 a significant increase in the curvature of the classification decision boundary. Figs. 5a and 5b show that G-TA outperforms TA when attacking AT and TRADES. This advantage is also demonstrated in attacking other defenses (e.g., Figs. 5d and 5c), proving the effectiveness of G-TA in attacking defense models.

heading: 4.3 Comprehensive Understanding of Tangent Attack
text: In the ablation studies, we conduct the experiments of the targeted attacks on the ImageNet dataset to understand our approach in depth, and the target model is ResNet-50. The results are shown in Fig. 6.
Initialization. Our algorithm starts with an image x̃0 selected from the target class, and we study three selection strategies: (1) a 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. 6c shows the effects of different jump directions. RandomHSJA is a variant of HSJA which adopts a random vector r that satisfies 〈r,u〉 > 0 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 a smaller B0 performs better since it saves queries. But B0 = 5 performs worse than B0 = 30 because it uses too few samples for gradient estimation.

heading: 5 Conclusion
text: In this paper, we propose a new geometric-based method for query-efficient hard-label black-box attacks. Our method relies on the observation that the minimum `2 distortion can be obtained by searching a boundary point along a tangent line of a virtual hemisphere. We offer a closed-form solution for computing the optimal tangent point and provide a formal proof of its correctness. We further propose a generalized method that replaces the hemisphere with a 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.

heading: Acknowledgments
text: This research is partially supported by the National Key R&D Program of China (2019YFB1405703) and TC190A4DA/3, the National Natural Science Foundation of China (Grant Nos. 62021002, 61972221). Yisen Wang is partially supported by the National Natural Science Foundation of China under Grant 62006153, and Project 2020BD006 supported by PKU-Baidu Fund.

Review summaries:
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.         

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.

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. 

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.