ADDA: An Adversarial Direction-Guided Decision-Based Attack via Multiple Surrogate Models

Abstract

Over the past decade, Convolutional Neural Networks (CNNs) have been extensively deployed in security-critical areas; however, the security of CNN models is threatened by adversarial attacks. Decision-based adversarial attacks, wherein an attacker relies solely on the final output label of the target model to craft adversarial examples, are the most challenging yet practical adversarial attacks. However, existing decision-based adversarial attacks generally suffer from poor query efficiency or low attack success rate, especially for targeted attacks. To address these issues, we propose a query-efficient Adversarial Direction-guided Decision-based Attack (ADDA), which exploits the advantages of transfer-based priors and the benefits of a single query. The transfer-based priors provided by the gradients of multiple different surrogate models can be utilized to suggest the most promising search directions for generating adversarial examples. The query consumption during the ADDA attack is mainly derived from a single query evaluation of the candidate adversarial samples, which significantly saves the number of queries. Experimental results on several ImageNet classifiers, including $l_{\infty }$ and $l_2$ threat models, demonstrate that our proposed approach overwhelmingly outperforms existing state-of-the-art decision-based attacks in terms of both query efficiency and attack success rate. We show case studies of ADDA against a real-world API in which it is successfully able to fool the Google Cloud Vision API after only a few queries.

1. Introduction

Convolutional Neural Networks (CNN) have been increasingly deployed and achieved remarkable success on many real-world critical tasks, such as computer-aided diagnosis [1], face recognition systems [2], and autonomous driving [3]. However, CNN models are challenged by their inherent vulnerability to adversarial examples [4,5], which are crafted by adding minor human-imperceptible perturbations to legitimate inputs and can maliciously mislead even state-of-the-art CNN models into making incorrect predictions. Such adversarial attacks cause CNN models to fail to capture the task-relevant intrinsic properties of images, and render them unable to judge the visual concept correctly; this may pose serious security threats, especially in high-stakes areas. Thus, the study of adversarial examples to identify the weaknesses and blind spots of deep learning algorithms is crucial [4,6], allowing potential security risks to be investigated [7] and the robustness of models to be evaluated [8].

In terms of the adversary’s goal, adversarial attacks can be classified into untargeted and targeted attacks. In an untargeted attack, the classification model is misled into predicting any incorrect class, whereas in a targeted attack the threat model is misguided by producing a chosen (target) class. Based on the knowledge that an attacker has about the target model, adversarial attacks can be generally divided into two primary types, namely, white-box attacks and black-box attacks. In the white-box setting, an adversary has complete access to the victim model, including its structure and parameters, and can easily exploit various gradient-based methods to craft adversarial samples [8,9,10,11]. However, white-box attacks are not practical in real-world applications, as model-specific information may not be exposed to users. As such, the focus is shifting towards black-box adversarial attacks, where the adversary is restricted to only acquiring the input–output correspondences of the target model and has no access to the threat model. Current existing black-box attacks can be categorized into transfer-based and query-based methods according to whether the attacker needs to query the target model. Transfer-based methods [12,13] can launch a black-box attack without model queries, which leverages the transferability of adversarial examples, i.e., an adversarial example generated by one visual model may fool other neural networks with different architectures trained on the same task. In consequence, the consistency between the victim model and the surrogate model is crucial, and greatly influences the attack success rate. Based on the information received from queries, the query-based approaches can be broadly divided into score-based attacks (known as soft-label attacks) and decision-based attacks (known as hard-label attacks), as shown in Figure 1. As far as score-based attacks are concerned, the adversary has access to the prediction probabilities (e.g., soft-label output) of the target model, and can estimate the gradients by adopting zeroth-order optimization techniques to craft adversarial examples [14,15,16,17]. On the other hand, the decision-based setting only provides prediction labels (e.g., hard-label output) of the model, and does not even provide any prediction probabilities [18,19]. Due to less information being exposed from the query feedback, gradient estimation in decision-based attacks is very inefficient and impractical.

In this paper, we focus on the most challenging yet practical decision-based black-box setting, where only the final decision (e.g., the top-1 label) is available from each query. In a real-world scenario this decision-based attack is more feasible, although it usually requires a large number of queries, as the information returned from a single model query is very little. Boundary attacks [18], as the initial attempt for decision-based attacks, may take millions of queries to converge. Although varied approaches [19,20,21] have been introduced to improve the query efficiency of boundary attack, the most effective and advanced attacks typically require more than tens of thousands of queries. Generally, in addition to the potentially high query costs in terms of time and money, online machine learning services restrict the number of queries allowed per unit of time. For example, the Google Cloud Vision API presently permits 1800 requests per minute, and a tremendous number of queries in a short time may be identified as fraud by the system. Therefore, decision-based attacks with low query efficiency may be inapplicable in the real world. Recently, Shukla et al. [22] presented a hard-label black-box attack in low query budget regimes through Bayesian optimization. Although the requisite number of queries is greatly reduced, the attack success rate remains unsatisfactory. To date, how to develop a query-efficient decision-based black-box attack that achieves a higher success rate with smaller distortions in a limited query setting remains an open question.

The gradient of the surrogate model, known as the prior gradient, contains plentiful prior information of the true gradient [23,24]. Several recent works [23,24,25] have adopted both transfer-based prior queries and model queries, reducing the query amount of score-based attacks from the initial millions of calls [14,15] to less than a thousand. However, this impressive drop is unreachable in the decision-based setting at present. Brunner et al. [20] utilized the gradient of a reference model to improve the efficiency of decision-based attacks, and gained benefit from surrogates as well. Surrogate models are widely used for black-box attacks, and cannot be ignored whenever they are available.

In this paper, we propose an Adversarial Direction-guided Decision-based Attack (ADDA) using several pretrained white-box surrogate models. We aim to greatly improve the success rate of non-targeted and targeted attacks within a low query budget (a thousand queries) as well as small constraint perturbations. We turn this adversarial process into a constrained optimization problem and then develop an iterative random search framework to craft adversarial examples. At each iteration, we search along the adversarial direction generated by the surrogate model, which is randomly chosen from the pretrained model set, to produce a candidate seed. Then, we use the predefined query function to judge whether the candidate seed is an adversarial example. The failed seed contains location information of decision boundaries [26], which can be used as the starting point of the next iteration. The iterative process stops if an adversarial example is successfully found or if the query budget is exhausted. Figure 2 illustrates the framework of ADDA. The superiority of our method is due to three main aspects: (1) under the guidance of adversarial direction, the candidate adversarial example has the most promising updating direction; (2) random search along adversarial directions generated by different surrogate models may mutually revise previous inaccurate directions; (3) the whole process of crafting an adversarial example does not increase the number of queries, and only a single query is used to evaluate the adversarial example at each iteration, which saves a significant number of queries.

Our main contributions can be summarized as follows:

• We design a simple yet novel algorithm called ADDA based on the random search mechanism via exploiting multiple pretrained white-box surrogate models, drastically reducing the query amount while achieving a high fooling rate.
• We explore the geometric properties of three large classification models trained on the ImageNet dataset along adversarial directions generated through different reference models. The results reveal several interesting findings, such as that the adversarial directions always outperform the random directions in both targeted and untargeted settings.
• We demonstrate the superior efficiency and effectiveness of our algorithm over several state-of-the-art decision-based attacks through comprehensive experiments. Our source code is publicly available at (https://github.com/whitevictory9/ADDA, accessed on 1 July 2023).
• Our approach is able to successfully fool Google Cloud Vision, a black-box machine learning commercial system, while using an unprecedentedly low number of queries.

2. Related Work

Decision-Based Attacks. We focus on the restrictive hard-label or decision-based black-box settings where only the final decision, i.e., the top-1 predicted label, is returned by the victim model. Brendel et al. [18] first studied this problem and proposed the Boundary Attack (BA). It starts from a large adversarial perturbation and iteratively reduces the distortion by random walks along the decision boundary. Although the performance of BA is comparable to that of state-of-the-art white-box attacks, it demands millions of model queries before convergence. Subsequently, several other works have extended this work and improved its query efficiency. HopSkipJumpAttack (HSJA) [21] achieves this through the utilization of discarded information in the gradient-direction estimation, while Biased Boundary Attack [20] incorporates low-frequency perturbations, regional masks, and surrogate gradients. In both cases, tens of thousands of queries are needed to generate adversarial examples with small perturbations. Cheng et al. [19] proposed Opt Attack, which reformulates the original adversarial optimization problem as a search for the optimal direction which leads to the shortest distance to the decision boundary. Sign-Opt Attack [27] refines this method by estimating the sign of gradient at any direction instead of the true gradient. Recent approaches have studied decision-based black-box scenarios with severely limited queries. Bayes attacks [22] exploit Bayesian optimization for finding adversarial examples in a structured low-dimensional subspace. SurFree [28] searches along precise indications of geometrical properties of the classifier decision boundaries to find the largest distortion decrease. Although the former leverages Fast Fourier Transform (FFT) to alleviate the high dimensionality of the image, the structured subspace is still in thousands of dimensions, which makes Bayesian optimization computationally expensive and ineffective. The latter, however, performs outstandingly in terms of adversarial distortion under low query budgets, and can be assumed as the state-of-the-art method in the decision-based black-box setting.

Transfer-Based Attacks. It is well known that adversarial examples often transfer across different models, i.e., an adversarial example generated by one visual model could probably deceive another [4,29]. Several works on black-box attacks combine both transfer-based attacks and query-based attacks. Papernot et al. [7,12] trained a substitute model to mimic the victim model with a synthetic dataset labeled by the target model through queries and then mount black-box attacks based on the transferability of adversarial examples. However, these methods rely solely on transferability, and tend to suffer from high failure rates. Several score-based black-box attacks have introduced reference models as transferable priors to conduct gradient estimation, which greatly improves their performance [20,23,25]. Thereafter, Yang et al. [30] further improved the attack success rate and query efficiency by updating the surrogate model with query feedback. Suya et al. [31] proposed a hybrid attack strategy that exploits the local surrogate model to generate the starting points for optimization-based attacks and then tune the local surrogate model using labels learned from optimization attacks. Ma et al. [32] proposed Simulator Attack to reduce the query complexity, which leverages a meta-learning-based framework to train a generalized surrogate model to precisely mimic any unknown victim model. Unlike previous approaches, we do not optimize the surrogate model, and instead focus on utilizing the adversarial directions generated by multiple reference models as directional guidelines for the random search framework.

3. Problem Formulation

Let $f:{[0,1]}^D\to {\mathbb{R}}^{{}^K}$ denote a K-class image classification model. Starting with an input image $\mathbf{x}\in {[0,1]}^D$, the model produces an output $f\left(\mathbf{x}\right)\in \{y\in {[0,1]}^K|{\sum }_{k=1}^K{y}_k=1\}$. The output vector $f\left(\mathbf{x}\right)=(f_1\left(\mathbf{x}\right),\dots ,f_K\left(\mathbf{x}\right))$ can be considered as a probability distribution over the set of labels $\left[K\right]=\{1,\dots K\}$. The final output label of image $\mathbf{x}$ is the class with maximum probability $arg{max}_{k\in \left[K\right]}{f}_k\left(\mathbf{x}\right)$. We consider adversaries of both the untargeted and targeted types. For an original well-classified image ${\mathbf{x}}_0$ and its ground-truth label y, the goal of the non-targeted attacker is to find an adversarial image ${\mathbf{x}}^{\prime }$ such that $arg{max}_{k\in \left[K\right]}{f}_k\left({\mathbf{x}}^{\prime }\right)\ne y$ while ${\mathbf{x}}^{\prime }$ is visually indistinguishable from the original image ${\mathbf{x}}_0$. The similarity between ${\mathbf{x}}^{\prime }$ and ${\mathbf{x}}_0$ can be quantified by the perceptibility metric $d({\mathbf{x}}^{\prime },\mathbf{x})$. Standard choices of d are usually $l_p$-norms; we focus on $l_2$-norm and $l_{\infty }$-norm distance in this paper. To constrain adversarial perturbations, we adopt the common approach of requiring $\left|\right|{\mathbf{x}}^{\prime }-\mathbf{x}|{|}_p$ less than a given threshold $\epsilon$.

In the decision-based black-box setting, we assume that the function f is not accessible, and that only the final decision (top-1 prediction) can be obtained by querying the classification model. Because each query to the target network may incur time or monetary costs, we are interested in query-efficient black-box attack algorithms. Specifically, an attack is considered successful only if an adversarial example is constructed within a given query budget Q. Hence, the process of finding adversarial examples can be expressed as solving the following constrained optimization problem:

$$\begin{array}{cc}\hfill & arg\underset{k\in \left[K\right]}{max}{f}_k\left({\mathbf{x}}^{\prime }\right)\ne y,\hfill \\ \hfill & s.t.\left|\right|{\mathbf{x}}^{\prime }-{\mathbf{x}}_0|{|}_p\le \epsilon andqueries\le Q.\hfill \end{array}$$

(1)

The targeted attack instead replaces the object function in Equation (1) with

$$arg\underset{k\in \left[K\right]}{max}{f}_k\left({\mathbf{x}}^{\prime }\right)=y_t,$$

(2)

where $y_t\in \left[K\right]/\left\{y\right\}$ is a target class provided by the attacker.

4. Our Approach

4.1. Basic Idea

The study of transfer-based attacks reveals that different classification models tend to have similar decision boundaries for the same classification tasks [13]. In this paper, we assume that the attacker can access pretrained local models, which is a common assumption used in transfer-based attacks. Inspired by [13], for a non-targeted attack, if a point within the perturbation constraint is far from the decision boundary of the clean image which is found in the local surrogate model, it may be an adversarial example for the target model or it may accelerate the adversarial attack. Based on this idea, we roughly regard the process of searching for adversarial examples as a problem of minimizing the true class probability along the correct classification direction of the surrogate model. Specifically, for a given clean image ${\mathbf{x}}_0$ and its true label y, ${\mathbf{1}}_y$ can be seen as the direction of the correct classification. Given substitute model $\tilde{f}$, we denote the true class probability for this model as ${\tilde{f}}_y\left(x^{\prime }\right)=1_y^T\tilde{f}\left({\mathbf{x}}^{\prime }\right)$; thus, the optimization problem in Equation (1) can be converted into the problem of minimizing the true class probability for the surrogate model, as follows:

$${\mathbf{x}}^{*}\leftarrow \underset{\left|\right|x^{\prime }-x\left|\right|\le \epsilon }{\mathrm{argmin}}{\tilde{f}}_y\left({\mathbf{x}}^{\prime }\right),s.t.queries\le Q.$$

(3)

In the iterative approach to solving Equation (3), the number of iterations is constrained by the query budget Q. Therefore, a query-efficient attack is an attack algorithm that quickly converges to a solution. As an indicator of a successful black-box attack, we introduce the query function $\varphi \left({\mathbf{x}}^{*}\right):{[0,1]}^d\to \{1,0\}$ via

$$\varphi \left({\mathbf{x}}^{*}\right):=\left\{\begin{array}{c}1\underset{k\in \left[K\right]}{argmax}{V}_k\left({\mathbf{x}}^{*}\right)\ne y,\\ 0\underset{k\in \left[K\right]}{argmax}{V}_k\left({\mathbf{x}}^{*}\right)=y,\end{array}\right.$$

(4)

where V is the victim model. Generally, the input ${\mathbf{x}}^{*}$ is an adversarial example for V if and only if $\varphi \left({\mathbf{x}}^{*}\right)=1$. The query function $\varphi \left({\mathbf{x}}^{*}\right)$ is accessible in the decision-based black-box setting, as it can be obtained by querying the victim model V alone. Therefore, within a given query budget Q, Equation (1) can be reformulated as the following optimization problem:

$$\underset{\left|\right|x^{\prime }-x\left|\right|\le \epsilon }{\mathrm{argmin}}{\tilde{f}}_y\left({\mathbf{x}}^{\prime }\right),s.t.\varphi \left({\mathbf{x}}^{\prime }\right)=1.$$

(5)

Projected gradient descent (PGD) [8], as the backbone of some of the most powerful white-box adversarial attacks, can be used to generate adversarial samples iteratively:

$${{\mathbf{x}}^{\prime }}^{(k+1)}={\mathbb{P}}_{S_p({\mathbf{x}}_0,\epsilon )}({{\mathbf{x}}^{\prime }}^{\left(k\right)}-\eta {\mathbf{g}}_p^{\left(k\right)}),$$

(6)

with

$${\mathbf{g}}_p^{\left(k\right)}=\left\{\begin{array}{c}\hfill {\nabla }_{{{\mathbf{x}}^{\prime }}^{\left(k\right)}}{\tilde{f}}_y\left({{\mathbf{x}}^{\prime }}^{\left(k\right)}\right)/||{\nabla }_{{{\mathbf{x}}^{\prime }}^{\left(k\right)}}{\tilde{f}}_y\left({{\mathbf{x}}^{\prime }}^{\left(k\right)}\right){||}_2(p=2),\\ \hfill sign\left({\nabla }_{\left({{\mathbf{x}}^{\prime }}^{\left(k\right)}\right)}{\tilde{f}}_y\left({\mathbf{x}}^{\prime }\right)\right)(p=\infty ).\end{array}\right.$$

(7)

Here, ${\mathbb{P}}_{S_p}$ denotes the projection onto $S_p(·)$, $S_p({\mathbf{x}}_0,\epsilon )$ is an $l_p$ ball of radius $\epsilon$ centered on ${\mathbf{x}}_0$, and $\eta$ is the step size. In fact, under the $l_{\infty }$ norm, ${\mathbf{g}}_{\infty }$ is the sign vector of the gradient, while in the case of the $l_2$ norm ${\mathbf{g}}_2$ represents the normalized gradient. Because the adversarial example is crafted iteratively along ${\mathbf{g}}_p$, we can intuitively define ${\mathbf{g}}_p$ as the adversarial direction.

Similarly, the goal of the targeted attack can be approximated as maximizing the probability of the target class on the surrogate model, namely, $arg{max}_{\left|\right|{\mathbf{x}}^{\prime }-\mathbf{x}|{|}_p\le \epsilon }{\tilde{f}}_{y_t}\left({\mathbf{x}}^{\prime }\right)$, and then searching for the adversarial example by querying the target model. We define the query function of the targeted attack as

$$\varphi \left({\mathbf{x}}^{*}\right):=\left\{\begin{array}{c}1\underset{k\in \left[K\right]}{argmax}{V}_k\left({\mathbf{x}}^{*}\right)=y_t,\\ 0\underset{k\in \left[K\right]}{argmax}{V}_k\left({\mathbf{x}}^{*}\right)\ne y_t.\end{array}\right.$$

(8)

The process of generating targeted adversarial examples is similar to that of the non-target attack.

Unfortunately, the proposed attack method above may fail to find an adversarial sample if only a single surrogate model is used. This is because the success rate of the adversarial attack depends on the similarity between the substitute model and the victim model. Therefore, it is necessary to further develop an algorithm to successfully and quickly find adversarial examples.

4.2. Exploration of Different Adversarial Directions

In this section, we explore the geometric properties of the classification model along the adversarial directions from different reference models. Specifically, we study the decision boundary of three victim models, DenseNet121 [33], ResNet50 [34], and VGG16_bn [35], in the planes spanned by the adversarial directions from ResNet152 [36], ResNeXt101 [37], Wide ResNet101 [38], and VGG13 [35], respectively. These seven models are all state-of-the-art models that were pretrained on the ImageNet [39] dataset, with the three victim models commonly chosen by prior works [22,24] and the other four victim models selected randomly from the torchvision package. For brevity, we denote the four surrogate models as ${\tilde{f}}^{\left(n\right)},\mathrm{n}=1,\dots 4$, respectively. We randomly select an image $\tilde{\mathbf{x}}$ from the ILSVRC2012 verification set, originally classified as ‘brambling’, and use it as an example to study the decision boundary.

Decision Boundaries of the Untargeted Method using Different Reference Models. We set the gradient direction of the substitute model in Equation (6) as

$$\mathbf{u}=\nabla {\tilde{f}}_y^{\left(n\right)}\left(\tilde{\mathbf{x}}\right)/||\nabla {\tilde{f}}_y^{\left(n\right)}\left(\tilde{\mathbf{x}}\right){||}_2,\mathrm{n}=1,\dots 4,$$

(9)

with the negative direction being the non-targeted adversarial direction. We choose $\mathbf{u}$ and its random normalized orthogonal directions $\mathbf{v}$ as the horizontal and vertical axes of a 2D plane Cartesian coordinate system. The unit value for both axes is one pixel. For any point $(i,j)$ in the 2D plane corresponding to an image perturbed by i and j along each direction,

$$clip(\tilde{\mathbf{x}}+i\mathbf{u}+j\mathbf{v},0,1),$$

(10)

where $\tilde{\mathbf{x}}$ is the pixel value vector of the original image. The decision boundaries of all victim models in different planes are plotted in the first row of Figure 3.

From Figure 3, it can be observed that:

• For all victim models, the area where each model can correctly predict the image is limited to the middle region. In addition, the decision boundary of each model is within a small closed curve. The models are quickly misled along the untargeted adversarial direction (e.g., negative gradient direction). This partially explains the feasibility of the non-targeted attack approach presented in Section 4.1.
• The distance to the boundary along the non-targeted adversarial direction is less than along other directions. Note that this conclusion holds for different planes; that is, even if the reference model provides a direction that is not optimal for searching for adversarial samples, it is still better than a random direction. For example, for the ResNet50 model, using the ResNeXt101 surrogate model as the direction guide is slower to reach the boundary than following the directions provided by other substitute models, but is faster than the random directions. Therefore, it can be concluded that the reference model can provide useful guidance in searching for adversarial examples even when it is not optimal.
• Using different surrogate models, the distance to the boundary along the non-targeted adversarial direction is unequal. For an attacker, the ideal situation is to reach the boundary in the shortest distance. This means that only a very small perturbation is needed in order for the victim model to be misclassified. Specifically, among the four substitute models, when the reference model ResNeXt101 is used as the direction guidance the number of steps to move out of the ground-truth region of the DenseNet121 model is the least. Thus, intuitively, if we can take advantage of this optimal situation it will greatly improve the efficiency of the adversarial attack.

Decision Boundaries of the Targeted Method using Different Reference Models. We randomly choose ‘Ptarmigan’ as the target label. Setting

$$\mathbf{u}=\nabla {\tilde{f}}_{y_t}^{\left(n\right)}\left(\tilde{\mathbf{x}}\right)/||\nabla {\tilde{f}}_{y_t}^{\left(n\right)}\left(\tilde{\mathbf{x}}\right){||}_2,\mathrm{n}=1,\dots 4,$$

(11)

as the respective targeted adversarial directions, we then plot the decision boundaries of the three victim models on the planes crossed by $\mathbf{u}$ and its random orthogonal direction, as shown in Figure 4. In addition to findings in the non-targeted case, the following can be observed:

• With the guidance of the targeted adversarial direction, each victim model finds the target area within which all points are predicted as the target class. However, certain targeted regions are very small, and each of the centers deviates from the x-axis (i.e., the targeted adversarial direction). This may be due to the inaccurate targeted adversarial direction provided by the surrogate model, such as the other three cases when the victim model is ResNet50, excluding Wide ResNet101 used as the reference model. Obviously, compared with the other three surrogate models, the success probability of the targeted adversarial attack is higher along the adversarial direction generated by Wide ResNet101. In contrast, for the DenseNet121 model, it is possible to reach the targeted regions faster along the other three adversarial directions. Therefore, the optimal adversarial direction is different for different victim models.
• Another interesting finding is that certain victim models appear to have multiple target regions in the plane. This may be attributed to the nonlinearity of the function ${\tilde{f}}_{y_t}\left({\mathbf{x}}^{\prime }\right)$, i.e., the gradient direction may change significantly when the distortion is large [37]. In this situation, moving along the direction of the original adversarial gradient no longer increases the probability of being classified as the target label.

4.3. Adversarial Direction-Guided Decision-Based Attack (ADDA)

Based on the above analysis, it might be wondered whether there is an algorithm that can exploit all of these adversarial directions such that each victim model can quickly move out of/reach the ground truth region/targeted region. A natural idea is to regard the adversarial directions provided by the surrogate models as a candidate direction set, then randomly select an adversarial direction from the set to generate the candidate seed. This means that multiple adversarial directions are used for random wandering within the perturbation limits. Because the adversarial directions are purposeful and abundant, it becomes easy to find adversarial samples through candidate seeds.

We now develop the above ideas into a query-efficient iterative attack algorithm, which we name ADDA. One iteration of the algorithm consists of three components. For brevity, we denote a set of candidate models as $\mathcal{M}$. First, a candidate model is randomly chosen from $\mathcal{M}$ as a substitute model. Second, an adversarial direction is obtained by Equation (7) using the candidate model. Following this adversarial direction can generate a candidate seed via Equation (6). Third, the query function (Equation (4) for an untargeted attack and Equation (8) for a targeted attack) is used to judge whether the candidate seed is an adversarial example. If the value of the query function is equal to 1, the candidate seed is considered as an adversarial example and the adversarial attack is successful. Otherwise, the candidate seed is used as the starting point for the next iteration. The termination condition of the whole iterative process is when the adversarial example is successfully found or the query budget runs out. The complete procedure is shown in Algorithm 1. In addition, Figure 5 intuitively shows the process of targeted ADDA for the $l_2$ norm. From the picture, it can be observed that even when using different random seeds, the ADDA algorithm can find the adversarial examples successfully after five iterations.

Algorithm 1 ADDA Algorithm

Input: Original image $\mathbf{x}$ and its label y, target label $y_t$, surrogate model set $\mathcal{M}$, query function $\varphi (·)$, query budget Q, step size $\eta$, $l_p$ threshold $\epsilon$. Output: Adversarial example ${\mathbf{x}}^{(k+1)}$. 1: $k\leftarrow 0$; 2: while  $k<Q$  do 3:     Pick a surrogate model f randomly from $\mathcal{M}$; 4:     if untargeted then 5:       ${\mathbf{g}}^{\left(k\right)}\leftarrow {\nabla }_{{\mathbf{x}}^{\left(k\right)}}{f}_y\left({\mathbf{x}}^{\left(k\right)}\right)$; 6:       ${\mathbf{x}}^{(k+1)}\leftarrow {\mathbb{P}}_{S_p(\mathbf{x},\epsilon )}({\mathbf{x}}^{\left(k\right)}-\eta {\mathbf{g}}_p^{\left(k\right)})$; 7:     else 8:       ${\mathbf{g}}^{\left(k\right)}\leftarrow {\nabla }_{{\mathbf{x}}^{\left(k\right)}}{f}_{y_t}\left({\mathbf{x}}^{\left(k\right)}\right)$; 9:       ${\mathbf{x}}^{(k+1)}\leftarrow {\mathbb{P}}_{S_p(\mathbf{x},\epsilon )}({\mathbf{x}}^{\left(k\right)}+\eta {\mathbf{g}}_p^{\left(k\right)})$; 10:    end if 11:    $k\leftarrow k+1$; 12:    if $\varphi \left({\mathbf{x}}^{(k+1)}\right)=1$ then 13:       break 14:    end if 15: end while 16: return  ${\mathbf{x}}^{(k+1)}$

5. Experiments

In this section, we first compare ADDA with several state-of-the-art decision-based attacks on the ImageNet dataset and then apply it to the popular commercial system Google Cloud Vision API to demonstrate the realistic threat of ADDA.

5.1. Experimental Setup

Dataset. We randomly sampled 1000 images from the validation set of ILSVRC2012 as the test images, which were evenly distributed across 1000 classes. All images were resized to $D=224\times 224\times 3$ and normalized to $[0,1]$. To ensure that the perturbed images were valid, we clipped them back to $[0,1]$ for all algorithms. In all experiments, we only considered images that were initially correctly predicted by the target network.

Models. We considered three commonly used models, DenseNet121, ResNet50, and VGG16_bn, as the victim classifiers, and used four models, ResNet152, ResNeXt101, Wide ResNet101, and VGG13, as surrogate models. All models were derived from the respective PyTorch [40] pretrained models.

Baselines. In untargeted settings, we compared our proposed algorithm with four state-of-the-art decision-based attacks: Sign-opt [27], HSJA [21], Bayes attack [22], and SurFree [28]. We used the publicly available implementations by these four authors and the same hyperparameter settings as in the original papers. In the targeted setting, we only report the performance of our method and do not compare it with these four methods, which is due to the following reasons: (a) SurFree currently only supports $l_2$ untargeted attacks; (b) for targeted attacks, Bayes attack only supports the low-dimension image, not larger image sizes such as ImageNet; (c) Sign-opt and HSJA cannot achieve any success under the dual constraints of a low query budget and small perturbation, requiring larger perturbations or more model queries to achieve a non-zero success rate.

Evaluation Metrics. The two core evaluation metrics were the attack success rate (ASR) and the average number of queries (Avg. Q). We defined the success rate as the percentage of the number of images that were successfully perturbed below a given distance threshold $\epsilon$ within a query budget Q. For both untargeted and targeted attacks, we restricted the query budget Q to 1000, which is consistent with that in Bayes attack.

5.2. Untargeted Attacks on ImageNet

First, we compared our proposed ADDA with Sign-opt, HSJA, and Bayes attack, which are the current state-of-the-art decision-based attacks for the $l_{\infty }$ threat model. We set the $l_{\infty }$ perturbation bound to $\epsilon =0.05$ and the step size of ADDA in PGD to $\eta =0.01$.

Table 1. Performance evaluation of $l_{\infty }$ untargeted attacks on ImageNet; $\epsilon =0.05$ and query limit = 1000.

Attack	DenseNet121		ResNet50		VGG16_bn
	ASR (%)	Avg. Q	ASR (%)	Avg. Q	ASR (%)	Avg. Q
Sign-opt	6.29	475.08	5.59	455.76	10.40	478.87
HJSA	9.65	165.37	11.09	144.14	16.14	159.76
Bayes attack	61.53	52.33	61.10	64.18	74.50	56.30
ADDA	99.58	7.70	99.89	5.50	98.21	7.37

presents the performance comparison of $l_{\infty }$ untargeted attacks on ImageNet. It can be observed that ADDA enjoys significantly higher efficiency in terms of the average number of queries and attack success rate than Sign-opt, HSJA, and Bayes attack. Specifically, ADDA consistently achieves an attack success rate close to $100\%$ while requiring $7\times$ to $20\times$ fewer queries compared to the competitors across the three different victim models.

For untargeted $l_2$ settings, we compared the performance of ADDA with four advanced decision-based adversarial attacks. To ensure fair comparisons, we considered three different $l_2$ perturbation bounds: $\epsilon =\{5.0,10.0,20.0\}$. We used a fixed step size for ADDA in PGD of $\eta =2.0$.

Table 2. Performance evaluation of untargeted $l_2$ attacks on ImageNet with a maximum query number of 1000.

		$\mathit{\epsilon }=5.0$		$\mathit{\epsilon }=10.0$		$\mathit{\epsilon }=20.0$
Threat Model	Attack	ASR (%)	Avg. Q	ASR (%)	Avg. Q	ASR (%)	Avg. Q
DenseNet121	Sign-opt	7.45	698.18	18.47	703.06	39.65	702.37
	HJSA	11.75	466.29	24.24	441.48	47.53	416.91
	Bayes attack	17.73	110.59	35.46	86.20	67.05	50.43
	SurFree	28.54	413.30	49.21	348.18	75.13	270.41
	ADDA	96.96	16.65	99.16	8.83	99.90	8.85
ResNet50	Sign-opt	7.04	673.78	18.43	688.97	42.44	700.10
	HJSA	10.66	451.74	24.43	444.04	49.38	405.17
	Bayes attack	15.94	109.01	33.99	91.56	67.25	63.20
	SurFree	26.09	406.97	48.24	359.46	75.57	264.85
	ADDA	98.86	11.65	99.69	7.16	99.90	6.55
VGG16_bn	Sign-opt	11.24	654.14	26.58	671.87	58.36	680.88
	HJSA	14.48	479.80	29.34	440.92	64.98	386.72
	Bayes attack	17.82	90.23	39.85	89.72	74.40	45.70
	SurFree	43.84	401.77	67.19	315.18	90.64	210.01
	ADDA	95.38	17.65	98.53	10.07	99.68	9.06

summarizes the evaluation results of the success rate and average query amount. It can be seen that ADDA consistently outperforms its competitors across all classifiers and different $\epsilon$. Furthermore, the results show that the attack success rate gap between the baseline approaches and ADDA increases to $88\%$ as $\epsilon$ decreases while maintaining leading query efficiency. Figure 6 displays the attack success rate versus the number of queries required to generate an adversarial example on the DenseNet121 classifier under $l_2$ perturbation constraints. Compared to the baseline methods, ADDA gains a dramatically faster increase in success rate. With a small query budget, ADDA achieves a success rate of almost $100\%$, which dominates the current basic methods in all settings.

5.3. Targeted Attacks on ImageNet

For each example in the targeted attacks, a random class other than the true one was chosen as the target class out of 1000 classes. Notably, we set the maximum $l_2$ perturbation size as $\epsilon =\sqrt{0.001·D}\approx 12.27$ in the targeted case, which has been used in several previous papers [23,30]. The step size $\eta$ in PGD and the perturbation bound $\epsilon$ under the $l_{\infty }$ perturbation constraint were the same as those in the untargeted setting. Due to the relatively larger dimensions of the images in ImageNet, previous methods have encountered difficulty when exploring them in targeted attacks, whereas our approach overcomes such problems. The experimental results are reported in

Table 3. Performance evaluation of ADDA under targeted settings on ImageNet with a maximum query number of 1000.

	${\mathit{l}}_{\mathit{\infty }}$		${\mathit{l}}_2$
Treat Model	ASR (%)	Avg. Q	ASR (%)	Avg. Q
DenseNet121	85.83	90.40	90.10	61.26
ResNet50	95.24	54.95	97.62	44.67
VGG16_bn	72.58	110.67	84.24	94.87

and Figure 7. The results in Table 3 show that ADDA achieves a high attack success rate while maintaining low query consumption. Regardless of the $l_{\infty }$ or $l_2$ setting, the performance of our approach on the DenseNet121 and ResNet50 classifiers is better than that of VGG16_bn in targeted attacks. In Figure 7, we plot the histogram of the number of model queries required for a successful targeted attack made by ADDA over three different victim models. Note that the query distributions are highly left-skewed, indicating that only a few images demanded a large number of queries, while most images required only about 100 or fewer model queries to construct adversarial examples.

5.4. Attacks on Google Cloud Vision

To demonstrate the effectiveness and applicability of ADDA to real-world applications, we applied it to the cloud-based computer vision API by Google Cloud Vision. For a given picture, the API returns a series of top labels and corresponding confidence scores, although these scores are neither probabilities nor logits. Because the returned labels are a list of unspecified length that varies based on the image, attacking Google Cloud Vision is significantly more challenging than attacking ImageNet. The adversarial criterion can be formulated as removing the top-3 concepts from the classification output. To meet this adversarial criterion, it is possible to slightly modify the query function in Equation (4) to make it suitable for attacking commercial classifiers.

We conducted both $l_{\infty }$ and $l_2$ untargeted attacks against the Google Cloud Vision API. Figure 8 and Figure 9 show the classification results in a comparison of clean images and adversarial examples generated by 2 and 29 queries, respectively. In Figure 8, the original image contains concepts related to primates. After only two queries, the perturbed image is forced to be classified as ‘Felidae’. Note that ADDA successfully replaced the top-3 concepts with Felidae-related objects through an imperceptible change to the original image. Figure 9 shows that our attack produces a perturbation that is human-indistinguishable after only 29 queries, causing the model to ignore the existence of the player-related object and classify the image as the dancer-relevant object.

6. Discussion and Conclusions

In this paper, we have proposed a query-efficient algorithm for decision-based black-box attack based on a random search scheme. We explored the decision boundary of three different victim models, observing that the adversarial directions provided by the pretrained models are optimal for searching for adversarial samples. Based on this finding, we developed a novel mechanism for random search designed to suggest the most promising search directions for adversarial examples. Along a random adversarial direction, this attempt obtains the best distortion decrease, contributing to a fast convergence to qualitative adversarial perturbations within an order of only tens of queries. Experimental results on the ImageNet dataset show that our ADDA proposal overwhelmingly outperforms existing state-of-the-art decision-based attacks in terms of query efficiency and attack success rate.

Unlike the performance in untargeted attacks, ADDA’s targeted attack success rate varies greatly across different models, which may be related to the selection of surrogate models. Because ADDA is sufficiently strong compared to the baseline methods in the current setting, we do not further discuss the impact on the attack strength of changes in the selection of reference models.

Considering the fact that ADDA is capable of crafting an imperceptible adversarial perturbation within a small query budget and can successfully fool real-world systems after only two queries, it is important to consider the impact of decision-based attacks on real-world systems. We hope that ADDA will inspire future work on adversarial defenses.