1 Introduction

Despite the unprecedented progress of Deep Neural Networks (DNNs) [24, 25, 27], the vulnerability to adversarial examples [46] poses serious threats to security-sensitive applications, e.g., face recognition [15, 20, 30, 37, 42, 47, 49, 55, 62], autonomous driving [4, 7, 19, 40, 61], etc. To securely deploy DNNs in various real-world applications, it is necessary to conduct an in-depth analysis on the intrinsic properties of adversarial examples, which has inspired numerous researches on adversarial attacks [3, 5, 6, 8, 11, 17, 36, 51] and defenses [23, 34, 52, 56, 57, 64]. Existing attacks can be split into two categories: white-box attack has full knowledge of the target model (often leveraging the gradient) [6, 17, 21, 34] while black-box attack can only access the model output, which is more applicable in real-world scenarios. The black-box attack can be implemented in different ways. Transfer-based attack [17, 32, 54, 59] adopts the adversaries generated on the substitute model to fool the target model. Score-based attack [2, 9, 26, 31] assumes that the attacker can access the output logits while decision-based (a.k.a. hard label) attack [5, 10, 11, 29, 35] only has access to the prediction (top-1) label.

Among the black-box attacks, decision-based attack is more challenging and practical due to the minimum information requirement for attack. The number of queries on target model often plays a significant role in decision-based attack, since the access to a victim model is usually restricted in practice. Though recent works manage to reduce the total number of queries from millions to thousands of requests [5, 29, 38], it is still insufficient for most practical applications [35].

Fig. 1.
figure 1

Illustration of the candidate triangle at an arbitrary iteration of TA. At the t-th iteration, TA constructs a triangle with the learned angle \(\alpha _t\) which satisfies \(\beta _t + 2\alpha _t > \pi \) in the sampled subspace to find a new adversarial example \(x_{t+1}^{adv}\) and update \(\alpha _t\) accordingly. Note that different from existing decision-based attacks [5, 35, 38], TA does not restrict \(x_t^{adv}\) on the decision boundary but minimizes the perturbation in the low frequency space using the geometric property; making TA itself query-efficient

Full size image

Existing decision-based attacks [5, 29, 35, 38] first generate a large adversarial perturbation and then minimize the perturbation while keeping adversarial property by various optimization methods. As shown in Fig. 1, we find that at the t-th iteration, the benign sample x, current adversarial example \(x_t^{adv}\), and next adversarial example \(x_{t+1}^{adv}\) can naturally construct a triangle for any iterative attacks. According to the law of sines, the adversarial example \(x_{t+1}^{adv}\) at the \((t\,+\,1)\)-th iteration should satisfy \(\beta _t + 2\alpha _t > \pi \) to guarantee that the perturbation decreases, i.e., \(\delta _{t+1}=\Vert x_{t+1}^{adv}-x\Vert _p<\delta _t=\Vert x_t^{adv}-x\Vert _p\) (when \(\beta _t + 2\cdot \alpha _t = \pi \), it would be an isosceles triangle, i.e., \(\delta _{t+1}=\delta _{t}\)).

Based on the above geometric property, we propose a novel and query-efficient decision-based attack, called Triangle Attack (TA). Specifically, at t-th iteration, we randomly select a directional line across the benign sample x to determine a 2-D subspace, in which we iteratively construct the triangle based on the current adversarial example \(x_t^{adv}\), benign sample x, learned angle \(\alpha _t\), and searched angle \(\beta _t\) until the third vertex of the constructed triangle is adversarial. Using the geometric information, we can conduct TA in the low frequency space generated by Discrete Cosine Transform (DCT) [1] for effective dimensionality reduction to improve the efficiency. And we further update \(\alpha _t\) to adapt to the perturbation optimization for each constructed triangle. Different from most existing decision-based attacks, there is no need to restrict \(x_t^{adv}\) on the decision boundary or estimate the gradient at each iteration, making TA query-efficient.

Our main contributions are summarized as follows:

  • To our knowledge, it is the first work that directly optimizes the perturbation in frequency space via geometric information without restricting the adversary on decision boundary, leading to high query efficiency.

  • Extensive evaluations on ImageNet dataset show that TA exhibits a much higher attack success rate within 1,000 queries and needs a much less number of queries to achieve the same attack success rate with the same perturbation budget on five models than existing SOTA attacks [8, 11, 12, 29, 35, 38].

  • TA generates more adversarial examples with imperceptible perturbations on Tencent Cloud API, showing its industrial-grade applicability.

2 Related Work

Since Szegedy et al.  [46] identified adversarial examples, massive adversarial attacks have been proposed to fool DNNs. White-box attacks, e.g., single-step gradient-based attack [21], iterative gradient-based attack [14, 28, 34, 36], and optimization-based attack [3, 6, 46], often utilize the gradient and exhibit good attack performance. They have been widely adopted for evaluating the model robustness of defenses [13, 16, 34, 41, 64], but are hard to be applied in real-world with limited information. To make adversarial attacks applicable in practice, various black-box attacks, including transfer-based attack [17, 50, 51, 58,59,60], score-based attack [2, 9, 18, 26, 48, 63, 65], and decision-based attack [5, 8, 12, 35, 38], have gained increasing interest. Among them, decision-based attack is most challenging since it can only access the prediction label. In this work, we aim to boost the query efficiency of decision-based attack by utilizing the geometric information and provide a brief overview of existing decision-based attacks.

BoundaryAttack [5] is the first decision-based attack that initializes a large perturbation and performs random walks on the decision boundary while keeping adversarial. Such a paradigm has been widely adopted in the subsequent decision-based attacks. OPT [11] formulates the decision-based attack as a real-valued optimization problem with zero-order optimization. And SignOPT [12] further computes the sign of the directional derivative instead of the magnitude for fast convergence. HopSkipJumpAttack (HSJA) [8] boosts BoundaryAttack by estimating the gradient direction via binary information at the decision boundary. QEBA [29] enhances HSJA for better gradient estimation using the perturbation sampled from various subspaces, including spatial, frequency, and intrinsic components. To further improve the query efficiency, qFool [33] assumes that the curvature of the boundary is small around adversarial examples and adopts several perturbation vectors for efficient gradient estimation. BO [43] uses Bayesian optimization for finding adversarial perturbations in low dimension subspace and maps it back to the original input space to obtain the final perturbation. GeoDA [38] approximates the local decision boundary by a hyperplane and searches the closest point to the benign sample on the hyperplane as the adversary. Surfree [35] iteratively constructs a circle on the decision boundary and adopts binary search to find the intersection of the constructed circle and decision boundary as the adversary without any gradient estimation.

Most existing decision-based attacks restrict the adversarial example at each iteration on the decision boundary and usually adopt different gradient estimation approaches for attack. In this work, we propose Triangle Attack to minimize the adversarial perturbation in the low frequency space directly by utilizing the law of sines without gradient estimation or restricting the adversarial example on the decision boundary for efficient decision-based attack.

3 Methodology

In this section, we first provide the preliminaries. Then we introduce our motivation and the proposed Triangle Attack (TA).

3.1 Preliminaries

Given a classifier f with parameters \(\theta \) and a benign sample \(x \in \mathcal {X}\) with ground-truth label \(y\in \mathcal {Y}\), where \(\mathcal {X}\) denotes all the images and \(\mathcal {Y}\) is the output space. The adversarial attack finds an adversary \(x^{adv} \in \mathcal {X}\) to mislead the target model:

$$\begin{aligned} f(x^{adv};\theta )\ne f(x;\theta )=y \quad \mathrm {s.t.}\quad \Vert x^{adv}-x\Vert _p <\epsilon , \end{aligned}$$

where \(\epsilon \) is the perturbation budget. Decision-based attacks usually first generate a large adversarial perturbation \(\delta \) and then minimize the perturbation as follows:

$$\begin{aligned} \min \Vert \delta \Vert _p \quad \mathrm {s.t.} \quad f(x+\delta ;\theta )\ne f(x;\theta )=y. \end{aligned}$$
(1)

Existing decision-based attacks [11, 12, 29] often estimate the gradient to minimize perturbation, which is time-consuming. Recently, some works adopt the geometric property to estimate the gradient or directly optimize the perturbation. Here we introduce two geometry-inspired decision-based attacks in details.

GeoDA [38] argues that the decision boundary at the vicinity of a data point x can be locally approximated by a hyperplane passing through a boundary point \(x_B\) close to x with a normal vector w. Thus, Eq. (1) can be locally linearized:

$$\begin{aligned} \min \Vert \delta \Vert _p \quad \mathrm {s.t.} \quad w^\top (x+\delta ) - w^\top x_B = 0. \end{aligned}$$

Here \(x_B\) is a data point on the boundary, which can be found by binary search with several queries, and GeoDA randomly samples several data points for estimating w to optimize the perturbation at each iteration.

Surfree [35] assumes the boundary can be locally approximated by a hyperplane around a boundary point \(x+\delta \). At each iteration, it represents the adversary using polar coordinates and searches optimal \(\theta \) to update the perturbation:

$$\begin{aligned} \delta _{t+1} = \delta _t \cos {\theta } (\boldsymbol{u}\cos {\theta }+\boldsymbol{v}\sin {\theta }), \end{aligned}$$

where \(\boldsymbol{u}\) is the unit vector from x to \(x_t^{adv}\) and \(\boldsymbol{v}\) is the orthogonal vector of \(\boldsymbol{u}\).

3.2 Motivation

Different from most decision-based attacks with gradient estimation [11, 12, 29, 38] or random walk on the decision boundary [5, 35], we aim to optimize the perturbation using the geometric property without any queries for gradient estimation. After generating a large adversarial perturbation, the decision-based attacks move the adversarial example close to the benign sample, i.e., decrease the adversarial perturbation \(\delta _t\), while keeping the adversarial property at each iteration. In this work, as shown in Fig. 1, we find that at the t-th iteration, the benign sample x, current adversarial example \(x_t^{adv}\) and next adversarial example \(x_{t+1}^{adv}\) can naturally construct a triangle in a subspace for any iterative attacks. Thus, searching for the next adversarial example \(x_{t+1}^{adv}\) with smaller perturbation is equivalent to searching for a triangle based on x and \(x_t^{adv}\), in which the third data point \(x'\) is adversarial and satisfies \(\Vert x'-x\Vert _p < \Vert x_t^{adv}-x\Vert _p\). This inspires us to utilize the relationship between the angle and side length in the triangle to search an appropriate triangle to minimize the perturbation at each iteration. As shown in Sect. 4.4, however, directly applying such a geometric property on the input image leads to poor performance. Thanks to the generality of such a geometric property, we optimize the perturbation in the low frequency space generated by DCT [1] for effective dimensionality reduction, which exhibits great attack efficiency as shown in Sect. 4.4.

Moreover, since Brendel et al.  [5] proposed BoundaryAttack, most decision-based attacks [8, 11, 12, 35, 38] follow the setting in which the adversarial example at each iteration should be on the decision boundary. We argue that such a restriction is not necessary in decision-based attacks but introduces too many queries on the target model to approach the boundary. Thus, we do not adopt this constraint in this work and validate this argument in Sect. 4.4.

3.3 Triangle Attack

In this work, we have the following assumption that the adversarial examples exist for any deep neural classifier f:

Assumption 1

Given a benign sample x and a perturbation budget \(\epsilon \), there exists an adversarial perturbation \(\Vert \delta \Vert _p \le \epsilon \) towards the decision boundary which can mislead the target classifier f.

This is a general assumption that we can find the adversarial example \(x^{adv}\) for the input sample x, which has been validated by numerous works [3, 5, 6, 21, 53]. If this assumption does not hold, the target model is ideally robust so that we cannot find any adversarial example within the perturbation budget, which is beyond our discussion. Thus, we follow the framework of existing decision-based attacks by first randomly crafting a large adversarial perturbation and then minimizing the perturbation. To align with previous works, we generate a random perturbation close to the decision boundary with binary search [29, 35, 38] and mainly focus on the perturbation optimization.

In two arbitrary consecutive iterations of the perturbation optimization process for any adversarial attacks, namely the t-th and \((t\,+\,1)\)-th iterations without loss of generalization, the input sample x, current adversarial example \(x_t^{adv}\) and next adversarial example \(x_{t+1}^{adv}\) can naturally construct a triangle in a subspace of the input space \(\mathcal {X}\). Thus, as shown in Fig. 1, decreasing the perturbation to generate \(x_{t+1}^{adv}\) is equivalent to searching for an appropriate triangle in which the three vertices are x, \(x_t^{adv}\) and \(x_{t+1}^{adv}\), respectively.

Theorem 1 (The law of sines)

Suppose a, b and c are the side lengths of a triangle, and \(\alpha \), \(\beta \) and \(\gamma \) are the opposite angles, we have \(\frac{a}{\sin {\alpha }}=\frac{b}{\sin {\beta }}=\frac{c}{\sin {\gamma }}\).

From Theorem 1, we can obtain the relationship between the side length and opposite angle for the triangle in Fig. 1:

$$\begin{aligned} \frac{\delta _t}{\sin {\alpha _t}} = \frac{\delta _{t+1}}{\sin {(\pi - (\alpha _t + \beta _t))}}. \end{aligned}$$
(2)

To greedily decrease the perturbation \(\delta _t\), the t-th triangle should satisfy that \(\frac{\delta _{t+1}}{\delta _t}=\frac{\sin {(\pi - (\alpha _t + \beta _t))}}{\sin {\alpha _t}}<1\), i.e., \(\pi - (\alpha _t + \beta _t) < \alpha _t\). Thus, decreasing the perturbation at the t-th iteration can be achieved by finding a triangle constructed by the input sample x, current adversarial example \(x_t^{adv}\) and the angles \(\beta _t\) and \(\alpha _t\), which satisfy \(\beta _t \,+\, 2\alpha _t > \pi \) and the third vertex should be adversarial. We denote such a triangle as candidate triangle and \(\mathcal {T}(x, x_{t}^{adv}, \alpha _t, \beta _t, \mathcal {S}_t)\) as the third vertex, where \(\mathcal {S}_t\) is a sampled subspace. Based on this observation, we propose a novel decision-based attack, called Triangle Attack (TA), that searches the candidate triangle at each iteration and adjusts angle \(\alpha _t\) accordingly.

Fig. 2.
figure 2

Illustration of the entire procedure of TA attack at the t-th iteration. We construct the triangle in the frequency space to efficiently craft adversarial examples. Note that here we adopt DCT for illustration but we do not need it for x at each iteration. We still adopt x and \(x_t^{adv}\) in the frequency space without ambiguity due to the one-to-one mapping of DCT

Full size image

Sampling the 2-D Subspace \(\mathcal {S}\) of Frequency Space. The input image often lies in a high-dimensional space, such as \(224\,\times \,224\,\times \,3\) for ImageNet [27], which is too large for the attack to explore the neighborhood for minimizing the adversarial perturbation efficiently. Previous works [22, 29, 35] have shown that utilizing the information in various subspaces can improve the efficiency of decision-based attacks. For instance, QEBA [29] samples the random noise for gradient estimation in the spatial transformed space or low frequency space but minimizes the perturbation in the input space with estimated gradient. Surfree [35] optimizes the perturbation in the subspace of the input space determined by a unit vector randomly sampled in the low frequency space. In general, the low frequency space contains the most critical information for images. With the poor performance of TA in the input space as shown in Sect. 4.4 and the generality of the geometric property shown in Fig. 2, we directly optimize the perturbation in the frequency space at each iteration for effective dimensionality reduction. And we randomly sample a d-dimensional line across the benign sample in the low frequency space (top 10%). The sampled line, directional line from benign sample x and current adversary \(x_t^{adv}\) can determine a unique 2-D subspace \(\mathcal {S}\) of the frequency space, in which we can construct the candidate triangle to minimize the perturbation. The final adversary can be converted into the input space by Inverse DCT (IDCT).

Fig. 3.
figure 3

Illustration of a symmetric candidate triangle (x, \(x_t^{adv}\) and \(x_{t+1,2}^{adv}\)). When the angle \(\beta \) cannot result in adversarial example (\(x_{t+1,1}^{adv}\)), we would further construct the symmetric triangle based on line \(\langle x, x_t^{adv} \rangle \) to check data point \(x_{t+1,2}^{adv}\)

Full size image
Fig. 4.
figure 4

The effect of magnitude on \(\alpha \) for the candidate triangle used in TA. For the same sampled angle \(\beta \), the larger angle \(\alpha \) leads to smaller perturbation but is also more likely to cross over the decision boundary

Full size image

Searching the Candidate Triangle. Given a subspace \(\mathcal {S}_t\), the candidate triangle only depends on angle \(\beta \) since \(\alpha \) is updated during the optimization. As shown in Fig. 3, if we search an angle \(\beta \) without leading to an adversarial example (\(x_{t+1,1}^{adv}\)), we can further construct a symmetric triangle with the same angle in the opposite direction to check data point \(x_{t+1,2}^{adv}\), which has the same magnitude of perturbation as \(x_{t+1,1}^{adv}\) but in different direction. We denote the angle as \(-\beta \) for the symmetric triangle without ambiguity. Note that with the same angle \(\alpha \), a larger angle \(\beta \) would make the third vertex closer to the input sample x, i.e., smaller perturbation. After determining the subspace \(\mathcal {S}_t\), we first check angle \(\beta _{t,0}=\max (\pi -2\alpha , \underline{\beta })\), where \(\underline{\beta }=\pi /16\) is a pre-defined small angle. If neither \(\mathcal {T}(x,x_t^{adv},\alpha _t, \beta _{t,0},\mathcal {S}_t)\) nor \(\mathcal {T}(x,x_t^{adv},\alpha _t, -\beta _{t,0},\mathcal {S}_t)\) is adversarial, we give up this subspace because it brings no benefit. Otherwise, we adopt binary search to find an optimal angle \(\beta ^*\in [\max (\pi -2\alpha , \underline{\beta }), \min (\pi -\alpha , \pi /2)]\) which is as large as possible to minimize the perturbation. Here we restrict the upper bound of \(\beta \) because \(\mathcal {T}(x,x_t^{adv},\alpha _t, \beta ,\mathcal {S}_t)\) would be at the opposite direction w.r.t. x for \(\beta > \pi /2\) and \(\pi -\alpha \) guarantees a valid triangle.

Adjusting Angle \(\alpha \). Intuitively, angle \(\alpha \) balances the magnitude of perturbation and the difficulty to find an adversarial example.

figure a

Proposition 1

With the same angle \(\beta \), a smaller angle \(\alpha \) makes it easier to find an adversarial example while a larger angle \(\alpha \) leads to smaller perturbation.

Intuitively, as shown in Fig. 4, a smaller angle \(\alpha \) results in larger perturbation but is more likely to cross over the decision boundary, making it easier to search an adversarial example, and vice versa. It is hard to consistently find an optimal \(\alpha \) for each iteration, letting alone various input images and target models. Thus, we adaptively adjust angle \(\alpha \) based on the crafted adversarial example:

$$\begin{aligned} \alpha _{t,i+1} = \left\{ \begin{array}{cc} \min (\alpha _{t,i}+\gamma , \pi /2+\tau ) &{} \textrm{if} \ f(x_{t,i+1}^{adv};\theta )\ne y\\ \max (\alpha _{t,i}-\lambda \gamma , \pi /2-\tau ) &{} \textrm{Otherwise} \end{array} \right. \end{aligned}$$
(3)

where \(x_{t,i+1}^{adv}=\mathcal {T}(x,x_t^{adv},\alpha _{t,i},\beta _{t,i},\mathcal {S}_t)\) is the adversarial example generated by \(\alpha _{t,i}\), \(\gamma \) is the change rate, \(\lambda \) is a constant, and \(\tau \) restricts the upper and lower bounds of \(\alpha \). We adopt \(\lambda < 1\) to prevent decreasing the angle too fast considering much more failures than successes during the perturbation optimization. Note that a larger angle \(\alpha \) makes it harder to find an adversarial example. However, a too small angle \(\alpha \) results in a much lower bound for \(\beta \), which also makes \(\mathcal {T}(x,x_t^{adv}, \alpha _t, \beta _t, \mathcal {S}_t)\) far away from the current adversarial example \(x_t^{adv}\), decreasing the probability to find an adversarial example. Thus, we add bounds for \(\alpha \) to restrict it in an appropriate range.

TA iteratively searches the candidate triangle in subspace \(\mathcal {S}_t\) sampled from the low frequency space to find the adversarial example and update angle \(\alpha \) accordingly. The overall algorithm of TA is summarized in Algorithm 1.

4 Experiments

We conduct extensive evaluations on the standard ImageNet dataset using five models and Tencent Cloud API to evaluate the effectiveness of TA. Code is available at https://github.com/xiaosen-wang/TA.

Table 1. Attack success rate (%) on five models under different RMSE thresholds. The maximum number of queries is set to 1,000. We highlight the highest attack success rate in bold
Full size table

4.1 Experimental Setup

Dataset. To validate the effectiveness of the proposed TA, following the setting of Surfree [39], we randomly sample 200 correctly classified images from the ILSVRC 2012 validation set for evaluation on the corresponding models.

Models. We consider five widely adopted models, i.e., VGG-16 [44], Inception-v3 [45], ResNet-18 [24], ResNet-101 [24] and DenseNet-121 [25]. To validate the applicability in the real world, we evaluate TA on Tencent Cloud APIFootnote 1.

Baselines. We take various decision-based attacks as our baselines, including four gradient estimation based attacks, i.e., OPT [11], SignOPT [12], HSJA [8], QEBA [29], one optimization based attack, i.e., BO [43], and two geometry-inspired attacks, i.e., GeoDA [38], Surfree [35].

Evaluation metrics. Following the standard setting in QEBA [29], we adopt the root mean squared error (RMSE) between benign sample x and adversarial example \(x^{adv}\) to measure the magnitude of perturbation:

$$\begin{aligned} d(x, x^{adv})=\sqrt{\frac{1}{w\cdot h\cdot c}\sum _{i=1}^w \sum _{j=1}^h \sum _{k=1}^c (x[i,j,k]-x^{adv}[i,j,k])^2}, \end{aligned}$$
(4)

where w, h, c are the width, height and number of channels of the input image, respectively. We also adopt the attack success rate, the percentage of adversarial examples which reach a certain distance threshold.

Hyper-parameters. For fair comparison, all the attacks adopt the same adversarial perturbation initialization approach as in [35] and the hyper-parameters for baselines are exactly the same as in the original papers. For our TA, we adopt the maximum number of iterations in each subspace \(N=2\), the dimension of directional line \(d=3\) and \(\gamma =0.01\), \(\lambda =0.05\) and \(\tau =0.1\) for updating angle \(\alpha \).

4.2 Evaluation on Standard Models

To evaluate the effectiveness of TA, we first compare the attack performance on five popular models with different decision-based attacks and report the attack success rate under various RMSE thresholds, namely 0.1, 0.05 and 0.001.

Fig. 5.
figure 5

Number of queries to achieve the given attack success rate on ResNet-18 for the attack baselines and the proposed TA under various perturbation budgets. The maximum number of queries is 10,000

Full size image

We first evaluate the attack within 1,000 queries, which is widely adopted in recent works [8, 35, 38]. The attack success rate is summarized in Table 1, which means the attack would fail to generate adversarial example for the input image if it takes 1,000 queries without reaching the given threshold. We can observe that TA consistently achieves much higher attack success rate than existing decision-based attacks under various perturbation budgets on five models with different architectures. For instance, TA outperforms the runner-up attack with a clear margin of 1.0%, 7.5% and 13.0% under the RMSE threshold of 0.1, 0.05, 0.01 on ResNet-101, which is widely adopted for evaluating the decision-based attacks. In particular, the proposed TA significantly outperforms the two geometry-inspired attacks, i.e., GeoDA [38] and Surfree [35], which exhibit the best attack performance among the baselines. This convincingly validates the high effectiveness of the proposed TA. Besides, among the five models, Inception-v3 [45], which is rarely investigated in decision-based attacks, exhibits better robustness than other models under various perturbation budgets against both baselines and TA. Thus, it is necessary to thoroughly evaluate the decision-based attacks on various architectures instead of only ResNet models.

To further verify the high efficiency of TA, we investigate the number of queries to achieve various attack success rates under the RMSE threshold of 0.1, 0.05 and 0.01, respectively. The maximum number of queries is set to 10,000 and the results on ResNet-18 are summarized in Fig. 5. As shown in Fig. 5a and 5b, TA needs much less number of queries to achieve various attack success rates with RMSE threshold of 0.1 and 0.05, showing the high query efficiency of our method. For the smaller threshold of 0.01, as shown in Fig. 5c, our TA still needs less number of queries when achieving the attack success rate smaller than 50% but fails to achieve the attack success rate higher than 60%. Note that as shown in Fig. 6 and Table 1, RMSE threshold of 0.01 is very rigorous so that the perturbation is imperceptible but is also hard to generate the adversarial examples for decision-based attacks. Since we mainly focus on the query efficiency of attack only based on geometric information, the attack performance under the RMSE threshold of 0.01 is acceptable because it is impractical for such high number of queries when attacking real-world applications.

Table 2. The number of adversarial examples successfully generated by various attack baselines and the proposed TA on Tencent Cloud API within 200/500/1,000 queries. The results are evaluated on 20 randomly sampled images from the correctly classified images in ImageNet due to the high cost of online APIs
Full size table

Besides, since TA aims to improve the query efficiency by utilizing the triangle geometry, the global optima might be worse than existing gradient estimation based attacks when more queries are allowed. Other geometry-inspired methods also perform poorer than QEBA [29] in this case without gradient estimation. However, it is not the goal of TA and can be easily solved using gradient estimation. With the high efficiency of TA, we can achieve higher attack performance with lower number of queries by taking the TA as warm-up for the precise gradient estimation attacks, such as QEBA [29], if the high number of queries is acceptable. We integrate the gradient estimation used in QEBA [29] into TA after 2,000 queries, dubbed TAG. For the perturbation budget of 0.01, TAG achieves the attack success rate of 95% using 7,000 queries, which is better than the best baseline with the attack success rate of 92% using 9,000 queries.

4.3 Evaluation on Real-world Applications

With the superior performance and unprecedented progress of DNNs, numerous companies have deployed DNNs for a variety of tasks and also provide commercial APIs (Application Programming Interfaces) for different tasks. Developers can pay for these services to integrate the APIs into their applications. However, the vulnerability of DNNs to adversarial examples, especially the prosperity of decision-based attack which does not need any information of target models, poses severe threats to these real-world applications. With the high efficiency of TA, we also validate its practical attack applicability using Tencent Cloud API. Due to the high cost of commercial APIs, we randomly sample 20 images from ImageNet validation set and the maximum number of queries is 1,000.

Fig. 6.
figure 6

The adversarial examples crafted by TA against Tencent Cloud API. #Q. denotes the number of queries for attack and RMSE denotes the RMSE distance between the benign sample and adversarial example. We report the correct label and the predicted label on the leftmost and rightmost columns, respectively (Zoom in for details.)

Full size image

The numbers of successfully attacked images are summarized in Table 2. We can observe that TA successfully generates more adversarial examples than the attack baselines within 200, 500 and 1,000 queries under various RMSE thresholds. In particular, TA can generate even more adversarial examples within 500 queries than the best attack baselines within 1,000 queries, showing the superiority of TA. We also visualize some adversarial examples generated by TA in Fig. 6. As we can see, TA can successfully generate high quality adversarial examples for various classes with few queries (\({\le }200\)), validating the high applicability of TA in real-world. Especially when the number of queries is 200, the adversarial examples generated by TA are almost visually imperceptible for humans, highlighting the vulnerability of current commercial applications.

4.4 Ablation Study

In this section, we conduct a series of ablation studies on ResNet-18, namely the subspace chosen by TA, the ratio for low frequency subspace and the change rate \(\gamma \) and \(\lambda \) for updating angle \(\alpha \). The parameter studies on the dimension of sampled line d and the bound \(\tau \) for \(\alpha \) are summarized in Appendix B.

Table 3. Ablation study on ResNet-18 for different spaces, i.e. input space (TA\(_\textrm{I}\)), frequency space for line sampling but input space for perturbation optimization (TA\(_\textrm{FI}\)), and full frequency space without mask (TA\(_\textrm{F}\))
Full size table

On the Subspace Chosen by TA. Different from existing decision-based attacks, the generality of geometric property used by TA makes it possible to directly optimize the perturbation in the frequency space. To investigate the effectiveness of frequency space, we implement TA in various spaces, namely input space (TA\(_\textrm{I}\)), sampling the directional line in the frequency space but optimizing the perturbation in the input space (TA\(_\textrm{FI}\)) used by Surfree [35] and full frequency space (TA\(_\textrm{F}\)). As shown in Table 3, due to the high-dimensional input space, TA\(_\textrm{I}\) cannot effectively explore the neighborhood of the input sample to find good perturbation and shows very poor performance. With the information from frequency space to sample the subspace, TA\(_\textrm{FI}\) exhibits much better results than TA\(_\textrm{I}\). When optimizing the perturbation in the full frequency space, TA\(_\textrm{F}\) can achieve higher attack success rate than TA\(_\textrm{FI}\), showing the benefit of frequency space. When sampling the subspace using the low frequency information, TA achieves much better performance than all the other attacks, supporting the necessity and rationality of the subspace chosen by TA.

Fig. 7.
figure 7

Attack success rate (%) of TA on ResNet-18 within 1,000 queries with various ratios for the low frequency subspace under three RMSE thresholds

Full size image
Fig. 8.
figure 8

Attack success rate (%) of TA on ResNet-18 within 1,000 queries with various \(\gamma \) and \(\lambda \) used for updating \(\alpha \) under \(RMSE = 0.01\)

Full size image

On the Ratio for Low Frequency Subspace. The low frequency domain plays key role in improving the efficiency of TA. However, there is no criterion to identify the low frequency since it corresponds to high frequency, which is usually determined by the lower part of the frequency domain with a given ratio. Here we investigate the effect of this ratio on the attack performance of TA. As shown in Fig. 7, the ratio has more significant influence on the attack success rate under the smaller RMSE threshold. In general, increasing the ratio roughly decreases the attack performance because it makes TA focus more on the high frequency domain, containing less critical information of the image. Thus, we adopt the lower 10% parts as the low frequency subspace for high efficiency, which also helps TA effectively reduce the dimension, making it easier for attack.

On the Change Rate \(\gamma \) and \(\lambda \) for Updating Angle \(\alpha \). As stated in Sect. 3.3, the angle \(\alpha \) plays a key role in choosing a better candidate triangle but it is hard to find a uniformly optimal \(\alpha \) for different iterations and input images. We assume that the larger angle \(\alpha \) makes it harder to find a candidate triangle but leads to smaller perturbation. As in Eq. (3), if we successfully find a triangle, we would increase \(\alpha \) with \(\gamma \). Otherwise, we would decrease \(\alpha \) with \(\lambda \gamma \). We investigate the impact of various \(\gamma \) and \(\lambda \) in Fig. 8. Here we only report the results for \(RMSE = 0.01\) for clarity and the results for \(RMSE = 0.1/0.05\) exhibit the same trend. In general, \(\gamma = 0.01\) leads to better attack performance than \(\gamma = 0.05/0.005\). When we increase \(\lambda \) with \(\gamma = 0.01\), the attack success rate increases until \(\lambda = 0.05\) and then decreases. We also investigate the impact of \(\tau \) which controls the bound for \(\alpha \) in Eq. (3), which shows stable performance within 1,000 queries but takes effect for 10,000 queries and we simply adopt \(\tau = 0.1\). In our experiments, we adopt \(\gamma = 0.01\), \(\lambda = 0.05\) and \(\tau = 0.1\).

Fig. 9.
figure 9

Attack success rate (%) of TA using various number of iterations for binary search (\(N_{bs}\)) to restrict the adversary on the decision boundary at each iteration

Full size image

4.5 Further Discussion

BoundaryAttack [5] adopts random walk on the decision boundary to minimize the perturbation for decision-based attack and the subsequent works often follow this setting to restrict the adversarial example on the decision boundary. We argue that such a restriction is not necessary and do not adopt it in our TA. To validate this argument, we also conduct binary search to move the adversarial example towards the decision boundary at each iteration after we find the candidate triangle to investigate the benefit of this restriction. As illustrated in Fig. 9, when the number of iterations for binary search (\(N_{bs}\)) is 0, it is vanilla TA that exhibits the best attack success rate. When we increase \(N_{bs}\), the binary search takes more queries in each iteration which degrades the total number of iterations under the given total number of queries. In general, the attack success rate stably decreases when increasing \(N_{bs}\) especially for \(RMSE = 0.01\), which means the cost (i.e., queries) for binary search to restrict the adversarial example on the decision boundary is not worthy. Such restriction might not be reliable and rational either for most decision-based attacks, especially for geometry-inspired attacks. We hope this would inspire more attention to discuss the necessity of restricting the adversarial examples on the decision boundary and shed new light on the design of more powerful decision-based attacks.

5 Conclusion

In this work, we found that the benign sample, the current and next adversarial examples can naturally construct a triangle in a subspace at each iteration for any iterative attacks. Based on this observation, we proposed a novel decision-based attack, called Triangle Attack (TA), which utilizes the geometric information that the longer side is opposite the larger angle in any triangle. Specifically, at each iteration, TA randomly samples a directional line across the benign sample to determine a subspace, in which TA iteratively searches a candidate triangle to minimize the adversarial perturbation. With the generality of geometric property, TA directly optimizes the adversarial perturbation in the low frequency space generated by DCT with much lower dimensions than the input space, and significantly improves the query efficiency. Extensive experiments demonstrate that TA achieves a much higher attack success rate within 1,000 queries and needs much less queries to achieve the same attack success rate. The practical applicability on Tencent Cloud API also validates the superiority of TA .