HARD-LABEL BLACK-BOX ADVERSARIAL EXAMPLES
Year: 2021

Abstract:
To craft black-box adversarial examples, adversaries need to query the victim model and take proper advantage of its feedback. Existing black-box attacks generally suffer from high query complexity, especially when only the top-1 decision (i.e., the hard-label prediction) of the victim model is available. In this paper, we propose a novel hard-label black-box attack named Policy-Driven Attack, to reduce the query complexity. Our core idea is to learn promising search directions of the adversarial examples using a well-designed policy network in a novel reinforcement learning formulation, in which the queries become more sensible. Experimental results demonstrate that our method can significantly reduce the query complexity in comparison with existing state-of-the-art hard-label black-box attacks on various image classification benchmark datasets. Code and models for reproducing our results are available at https://github.com/ZiangYan/ pda.pytorch.

heading: 1 INTRODUCTION
text: It is widely known that deep neural networks (DNNs) are vulnerable to adversarial examples, which are crafted via perturbing clean examples to cause the victim model to make incorrect predictions. In a white-box setting where the adversaries have full access to the architecture and parameters of the victim model, gradients w.r.t. network inputs can be easily calculated via back-propagation, and thus first-order optimization techniques can be directly applied to craft adversarial examples in this setting (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini & Wagner, 2017; Madry et al., 2018; Rony et al., 2019). However, in black-box settings, input gradients are no longer readily available since all model internals are kept secret.
Over the past few years, the community has made massive efforts in developing black-box attacks. In order to gain high attack success rates, delicate queries to the victim model are normally required. Recent methods can be roughly categorized into score-based attacks (Chen et al., 2017; Ilyas et al., 2018; Nitin Bhagoji et al., 2018; Ilyas et al., 2019; Yan et al., 2019; Li et al., 2020b; Tu et al., 2019; Du et al., 2019; Li et al., 2019; Bai et al., 2020) and hard-label attacks (a.k.a, decision-based attacks) (Brendel et al., 2018; Cheng et al., 2019; Dong et al., 2019; Shi et al., 2019; Brunner et al., 2019; Chen et al., 2020; Rahmati et al., 2020; Li et al., 2020a; Shi et al., 2020; Chen & Gu, 2020), based on the amount of information exposed to the adversaries from the output of victim model. When the prediction probabilities of the victim model are accessible, an intelligent adversary would generally prefer score-based attacks, while in a more practical scenario where only the top-1 class prediction is available, the adversaries will have to resort to hard-label attacks. Since less information is exposed from such feedback of the victim model, hard-label attacks often bare higher query complexity than that of score-based attacks, making their attack process costly and time intensive.
* The first two authors contributed equally to the work. Work was done when ZY was an intern at ByteDance AI Lab.
In this paper, we aim at reducing the query complexity of hard-label black-box attacks. We cast the problem of progressively refining the candidate adversarial example (by skillfully querying the victim model and analyzing its feedback) into a reinforcement learning formulation. At each iteration, we search along a set of chosen directions to see whether there exists any new candidate adversarial example that is perceptually more similar to its benign counterpart, i.e., in the sense of requiring less distortion. A reward is assigned to each of such search directions (treated as actions), based on the amount of distortion reduction yielded after updating the adversarial example along that direction. Such a reinforcement learning formulation enables us to learn the non-differentiable mapping from search directions to their potential of refining the current adversarial example, directly and precisely. The policy network is expected to be capable of providing the most promising search direction for updating candidate adversarial examples to reduce the required distortion of the adversarial examples from their benign counterparts. As we will show, the proposed policy network can learn from not only the queries that had been performed following the evolving policy but also peer experience from other black-box attacks. As such, it is possible to pre-train the policy network on a small number of query-reward pairs obtained from the performance log of prior attacks (with or without policy) to the same victim model. Experiments show that our policy-driven attack (PDA) can achieve significantly lower distortions than existing state-of-the-arts under the same query budgets.

heading: 2 RELATED WORK
text: In this paper, we focus on the hard-label black-box setting where only the top-1 decision of the victim model is available. Since less information (of the victim model) is exposed after each query, attacks in this category are generally required to query the victim model more times than those in the white-box or score-based settings. For example, an initial attempt named boundary attack (Brendel et al., 2018) could require ∼million queries before convergence. It proposed to start from an image that is already adversarial, and tried to reduce the distortion by walking towards the benign image along the decision boundary. Recent methods in this category focused more on gradient estimation which could provide more promising search directions, while relying only on top-1 class predictions. Ilyas et al. (2018) advocated to use NES (Wierstra et al., 2014; Salimans et al., 2017) to estimate the gradients over proxy scores, and then mounted a variant of PGD attack (Madry et al., 2018) with the estimated gradients. Towards improving the efficiency of gradient estimation, Cheng et al. (2019) and Chen et al. (2020) further introduced a continuous optimization formulation and an unbiased gradient estimation with careful error control, respectively. The gradients were estimated via issuing probe queries from a standard Gaussian distribution. To generate probes from some more powerful distributions, Dong et al. (2019) proposed to use the covariance matrix adaptation evolution strategy, while Shi et al. (2020) suggested to use customized distribution to model the sensitivity of each pixel. In contrast to these methods, our PDA proposes to use a policy network which is learned from prior intentions to advocate promising search directions to reduce the query complexity.
We note that some works also proposed to exploit DNN models to generate black-box attacks. For example, Naseer et al. (2019) used DNNs to promote the transferability of black-box attacks, while several score-based black-box attacks proposed to train DNN models for assisting the generation of queries (Li et al., 2019; Du et al., 2019; Bai et al., 2020). Our method is naturally different from them in problem settings (score-based vs hard-label) and problem formulations. In the autonomous field, Hamdi et al. (2020) proposed to formulate the generation of semantic attacks as a reinforcement learning problem to find parameters of environment (e.g., camera viewpoint) that can fool the recognition system. To the best of our knowledge, our work is the first to incorporate reinforcement learning into the black-box attacking scenario for estimating perturbation directions, and we advocate the community to consider more about this principled formulation in the future. In addition to the novel reinforcement learning formulation, we also introduce a specific architecture for the policy network which enjoys superior generalization performance, while these methods adopted off-the-shelf auto-encoding architectures.

heading: 3 OUR POLICY-DRIVEN ATTACK
text: We study the problem of attacking an image classifier in the hard-label setting. The goal of the adversaries is to perturb an benign image x ∈ Rn to fool a k-way victim classifier f : Rn → Rk into making an incorrect decision: arg maxi f(x
′)i 6= y, where x′ is the adversarial example generated by perturbing the benign image and y is the true label of x. The adversaries would generally prefer
adversarial examples x′ with smaller distortions ‖x− x′‖2 achieved using less queries, since these properties make the attack less suspicious and also save the cost. In this section, we first briefly review some background information that motivate our method (in Section 3.1), and then detail our reinforcement learning formulation (in Section 3.2 and Section 3.3) and the architecture of our policy network (in Section 3.4).

heading: 3.1 MOTIVATIONS
text: Most recent hard-label attacks followed a common pipeline of searching from a starting point which was already an adversarial image1 yet not close enough to the benign one. Unlike the white-box and score-based black-box setting in which the input gradients can be calculated and used as the most effective perturbation direction, in the concerned hard-label setting, outputs of the victim model only flip on the decision boundary while keeping constant away from the boundary, making it difficult to evaluate different directions almost everywhere. In this context, the search of promising perturbation directions was restricted into the regions near the decision boundary, since these regions are arguably more informative, and binary search was used to reach the decision boundary efficiently.
Let us take a very recent attack named HopSkipJumpAttack (Chen et al., 2020) as an example. Given the current estimation x′s of the adversarial example at each iteration, HopSkipJumpAttack first performed binary search to project it onto the decision boundary of the victim model. Denote x′ as the updated example that was on the decision boundary already, HopSkipJumpAttack then sampled many probes around x′ from an isotropic Gaussian distribution, and issued these probes to the victim model as queries. The feedback of the victim model was utilized to estimate the gradient direction at x′, and it was updated along this direction to obtain a new estimation of the adversarial example. This process was repeated many times until the query budget was exhausted.
In comparison with boundary attack (Brendel et al., 2018), HopSkipJumpAttack was in general far more query-efficient, though a large number of queries had to be consumed for probing the local geometrics of the decision boundary of the victim model. Its superiority came from using the estimated gradient directions as the search directions, which motivated us to explore even better search directions at each iteration of the attack. As will be shown in the appendices, drawing on some geometric insights, we found that the gradient directions are in fact not the optimal search directions in the framework of HopSkipJumpAttack. We also found that the task of performing hardlabel black-box attack could be naturally cast into a reinforcement learning task, thus we attempt to explore the possibility of developing a model-based method for predicting the most promising search directions for attacks. Feedbacks from the victim can provide supervision and thus the policy models in our reinforcement learning framework can be trained/fine-tuned on the fly during each attack process, such that little query is required once the model has been well-trained.

heading: 3.2 ATTACK AS REINFORCEMENT LEARNING PROBLEM
text: In this paper, we consider both targeted attacks and untargeted attacks. Given a benign example x, its label y, and the victim model f , an environment E(x, y, f) is naturally formed. The adversaries shall play the role of agent, trying to interact with the environment by issuing queries and collecting feedbacks, under a certain policy. The current example x′t on the decision boundary of the victim model (or called the candidate adversarial example) represents the state at each timestamp t. The agent uses a learnable policy network g which will be carefully introduced in Section 3.4 to guide its actions, and the action is to update the candidate adversarial example such that less distortions are required to fool the victim model. The action here incorporates searching along a promising direction at/‖at‖ where at ∈ Rn is sampled from an isotropic Gaussian distribution whose mean vector is given by the policy network µt = g(x′t, y, y
′) ∈ Rn where y′ is the target label, and its covariance matrix is given by Σ = σI ∈ Rn×n, in which the value of σ ∈ R is set to be gradually increased as the attack on each sample progresses, and I ∈ Rn×n indicates the n × n identity matrix. With at, the agent searches along its direction at/‖at‖ to see whether any better candidate adversarial example can be found. For targeted attacks, the target label y′ is chosen by the agent from the beginning and kept unchanged during the attack process. For untargeted attacks, x′t should be on the decision boundary where one side is the ground-truth label y and the other side could be regarded as the “target label” y′. As will be carefully introduced in Section 3.3, a reward rt ∈ R
1In practice, it is performed by randomly sampling until the adversarial constraint is satisfied, i.e., it is not classified as y by the victim model, or by directly choosing a benign sample from the adversarial class.
Algorithm 1 Policy-Driven Attack Algorithm 1: Input: the environment E(x, y, f); the target label y′, initial adversarial image x′1 ∈ Rn which
lies on the decision boundary; the policy network g. 2: Output: an adversarial example. 3: Initialize the step index t← 1. 4: while the query count limit not reached do 5: // Determine the baseline lt to evaluate the potential of different actions 6: µt ← g(x′t, y, y′), z ← BS(x′t + δ · µt‖µt‖2 ,x, f), where BS(·, ·, ·) performs binary search 7: Set the distortion reduction of z as baseline: lt ← max{‖x′t − x‖2 − ‖z − x‖2, lmin} 8: 9: // Collect actions and rewards, and update the policy network
10: Sample M actions: at,i ∼ N (µt, σtI), i ∈ {1, 2, . . . ,M} 11: Assign rewards rt,i to each actions with our mechanism introduced in Section 3.3 12: Update the policy network using one-step REINFORCE on M pairs: (at,i, rt,i) 13: 14: // Update adversarial image using predicted direction 15: µt ← g(x′t, y, y′) if ‖z − x‖2 ≤ ‖x′t − x‖2, otherwise µt ← at,i∗ , i∗ = arg maxi rt,i 16: x′t+1 ← BS(x′t + · µt‖µt‖2 ,x, f) 17: 18: // Update other variables 19: Double σt if all M rewards are zeros: σt+1 ← 2 · σt; else keep it: σt+1 ← σt 20: t← t+ 1 21: end while 22: return final adversarial image x′t
based on the performance of each action and the corresponding at is given to the agent for updating the parameter of the policy network. All details of our PDA are summarized in Algorithm 1.
Powered by the reinforcement learning framework, we can use policy gradient algorithms to train the policy network g to generate promising search directions in a direct way. For simplicity, we use the one-step REINFORCE (Williams, 1992) in the sequel of this paper and leave the exploration of more advanced policy gradient algorithms to future work.
3.3 REWARD AND ACTION
Figure 1 illustrates how we assign the scalar reward rt given current candidate adversarial example x′t and an action at. The decision boundary is illustrated by a horizontal straight line (denoted by B) in the figure, the benign counterpart x is assumed to be below B, and the circle C centered at x′t with a small radius δ shows all possible locations after jumping along the directions of some actions by δ from x′t. As described earlier, the reward rt should be assigned based on the amount of potential distortion reduction brought by at. A direct evaluation can be achieved by jumping along the direction of at first and then projecting the updated example back onto the decision boundary via binary search, to see how much improvement is obtained. However, since we evaluateM actions at,i simultaneously at an iteration (see Algorithm 1) and binary search needs to be performed for each of them, and the overall process would be prohibitively (query-)expensive. On this point, to efficiently assess the performance of an action, we instead evaluate whether the reduction of distortion by taking
a particular action can exceed particular baselines. Concretely, we first evaluate µt = g(x′t, y, y ′) as an action directly by using binary search in a way as just described. Suppose that it can reduce the required adversarial distortion2 by lt, then we setup two levels of baselines ‖x− x′t‖2 − β1 · lt and ‖x−x′t‖2−β2 · lt to see whether other actions can lead to adversarial examples with closer distance (than these baselines) from the benign example x, in which β1 = 0 and β2 = 0.25. As shown in Figure 1, for an action a ∈ {at,i}, we first obtain x′t + δ ·a/‖a‖2 and then move it towards x to see how much reward it can obtain. The two arcs V1 and V2 indicates where the same progress as the two baselines can be achieved, thus we can further project x′t + δ ·a/‖a‖2 onto the arcs to see if the projections (i.e, xV1s and x V2 s ) are still adversarial. It can be seen that x V1 s is still adversarial yet x V2 s is not. We assign a reward 1 to such an action a. If both the projections are still adversarial we shall assign a reward of 2, and if neither of them is adversarial, zero reward is assigned. Since xV1s is not adversarial could imply that xV2s is also not adversarial, such a way reduces the number of queries for assessing each action to at most 2 (xV1s and x V2 s ) and makes our PDA more query-efficient.

heading: 3.4 ARCHITECTURE OF THE POLICY NETWORK
text: As described in Section 3.2, the goal of our policy network is to predict a direction based on which the optimal adversarial example/candidate can be easily found. Its input is the current example on the decision boundary of the victim model (together with other useful information that is available to the agent if needed) and its output is expected to be a promising search direction that shares the same dimension with its input. Naı̈ve architecture designs of the policy network include the conventional auto-encoders and U-Net (Ronneberger et al., 2015). However, our experimental results suggest that such off-the-shelf auto-encoding architectures often offer degraded performance (see Section 4.3 for more details). We note that predicting a promising search direction is discrepant from the computer vision tasks for which these architectures are widely applied (e.g., predicting a segmentation map). Specifically, a segmentation map often aligns with the visual contents of the input image, while the promising search directions might be less correlated with the semantics of the input examples. We reckon it can be more beneficial to incorporate domain knowledge about adversarial attacks into the architecture of the policy network g.
On this point, we propose a new architecture for the policy network for our PDA. First, we know from HopSkipJumpAttack that the gradient direction at x′t, although not theoretically optimal, can provide strong empirical performance when serving as the search direction. Therefore, designing an architecture which could output the gradient vector at the point of its input seems to be an appropriate option for the policy network g. Formally, it takes the candidate adversarial example x′t, the groundtruth label y of the benign example, and the target label y′ as input, and mapped them to a search direction in Rn. In this spirit, the policy network is designed to own an internal classifier h : Rn → Rk, which performs a k-way classification. The number k can be the same as the number of prediction classes of the black-box victim model if the adversaries has such information. We hope the internal classifier h can learn to distill knowledge from the victim model if possible, as such we can use the input gradient of h as a descent search direction. Following the logit-diff loss developed for the white-box setting in Carlini & Wagner (2017)’s work, we propose to use:
g(x′t, y, y ′) = ∇x′th(x ′ t)y′ −∇x′th(x ′ t)y + b, (1)
as the output of the policy network, where a learnable bias vector b ∈ Rn is introduced to improved the capacity and flexibility of the network. The forward process of such a policy network is basically a back-propagation process of the internal classifier h, and if the decision boundary of the internal classifier h is aligned with that of the victim model, the output of the policy network should be the gradient direction of the victim model. Since the model is parameterized and has sufficient capacity, it can also learn to explore even better search directions other than the gradient directions.

heading: 3.5 (OPTIONAL) PRE-TRAINING OF THE POLICY NETWORK.
text: Note that the learning of the policy network can bare from large sampling complexity and may even fail to converge if its initial outputs are completely unable to cut the distortion. Just like for playing the game of go (Silver et al., 2016), we can optionally (pre-)train the policy network in a supervised manner to make the initial actions more reasonable in the reinforcement learning process, such that the samples collected in the follow-up steps are more informative and the issue can be relieved. In
2If µt is unable to reduce the distortion, or lt < 0.05 · δ, we clip lt to 0.05 · δ for numerical stability.
this section, we introduce how such pre-training can be performed for the concerned task. Recall that the goal of the policy network is to predict promising search directions for the candidate adversarial examples, thus we can construct the pre-training set S by collecting the intermediate results of any prior attacks to the same victim model, or we can also use a simplified policy and collect its suggested actions for constructing S for pre-training.
Given a small dataset D = {(x, y)}which consists of benign examples and their ground-truth labels, it is easier to first run our PDA without learning a policy network, i.e., using an input-independent policy for it. Concretely, we can instead sample each direction a′′t from the distribution N (b, σtI) at the timestamp t, where b here is still learnable, just like in Eq. (1). We found that such a simplified policy tends to learn a search direction that is very similar to the gradient direction. This simplified reinforcement learning problem where the policy network g is now absent shows more stable training performance and each of its attack trajectories can be effectively used to pre-train the policy network, which is formulated as: Tx , {(x′′t ,x, y, y′′t ,a′′t ) | t ∈ {1, 2, . . . ,mx}} , (2) where mx is the total number of iterations, and x′′t , y ′′ t , a ′′ t are the candidate adversarial example, the target label, and the suggested search direction by the simplified policy at each iteration, with a common timestamp t, respectively. To improve the compactness of the sample set for pre-training, we suggest a simple post-processing strategy to discard the tuples in Tx with less informative candidate adversarial examples: for i ≥ 2, we discard the i-th tuple in Tx if ‖x′′i −x‖2 > 0.99‖x′′j −x‖2, where j indicates the index of any previous tuple that is decided not to be discarded. The set that contains the remaining tuples is denoted by Trx, and the final pre-training set S is constructed using this sort of set gathered from all attack trajectories using the simplified policy, i.e.,
S = ⋃
(x,y)∈D Trx. (3)
Then it is how to pre-train the policy network given S for better initialization. First, according to the design of g as introduced in Section 3.4, it is natural to encourage the internal classifier h to perform as a classifier, and then, probably more importantly, the outputs of the policy network are encouraged to somehow align with the considered effective search directions (i.e., a′′t ) found by the aforementioned simplified policy. On this point, we introduce the cosine similarity S together with a regularizer Ψ which incorporates the classification loss to achieve these two goals, making the pre-training loss L as:
L = 1 |S| ∑
(x′′,x,y,y′′,a′′)∼S −S (g(x′′, y, y′′),a′′) + λ ·Ψ(h(x), h(x′′), y, y′′), (4)
where S(·, ·) calculates the cosine similarity between its two input vectors, λ is the coefficient for regularization, and Ψ serves as a regularizer which is given by:
Ψ(h(x), h(x′′), y, y′′) = CE(h(x), y) + 1 2 CE(h(x′′), y) + 1 2 CE(h(x′′), y′′), (5)
where CE(·, ·) calculates the cross-entropy loss given logits and labels. Since x′′ is on the decision boundary of the victim model f , f must assign 0.5 probability to both the benign class y and the adversarial class y′′ at x′′, which interprets the terms 12CE(h(x ′′), y) and 12CE(h(x ′′), y′′).

heading: 4 EXPERIMENTS
text: In this section, we evaluate the effectiveness of our method on three datasets: MNIST (LeCun et al., 2010), CIFAR-10 (Krizhevsky & Hinton, 2009), and ImageNet (Russakovsky et al., 2015). We compare our method with Boundary Attack (Brendel et al., 2018) and HopSkipJumpAttack (Chen et al., 2020) in both untargeted and targeted settings, and the required `2 distortions given a specific query budget are evaluated, as in recent related work (Brendel et al., 2018; Chen et al., 2020; Li et al., 2020a). For a comprehensive comparison, we report the distortions at {100, 500, 1K, 5K, 10K, 25K} query budgets in all experiments in the paper. The required mean distortions for untargeted and targeted attacks are reported in Table 1 and Table 2, respectively, and the median distortions are reported in the appendices. For targeted attack, we set the target label to y′ = y + 1 mod 10 where y is the true label for the clean image, and we only show results on MNIST and CIFAR-10 which are faster to be evaluated. All experiments are conducted on NVIDIA GTX 2080 Ti GPUs with PyTorch (Paszke et al., 2017).

heading: 4.1 EXPERIMENTAL SETUP
text: Victim models and h. For MNIST, we use the same architecture as in Carlini & Wagner (2017)’s work 3, which contains four convolutional layers and three fully connected layers and shows a test error rate of 0.59%, since it is widely adopted as a victim model in many related works. For CIFAR-10, we consider three victim models: (a) a CNN whose architecture is similar to the one considered on MNIST, which achieves a test error rate of 22.03% 4; (b) a WRN-28-10 (Zagoruyko & Komodakis, 2016) with a test error rate of 4.03% 5; (c) a ResNet-50 with a test error rate of 18.38% collected from the robustness package (Engstrom et al., 2019), which was adversarially trained under `2 PGD attacks ( = 1.0). On ImageNet, we adopt a ResNet-18 (He et al., 2016) from the PyTorch official model zoo as the victim model, which shows a top-1 error rate of 30.24% on the ImageNet official validation set. As for the policy network g, we adopt a VGG-13 (Simonyan & Zisserman, 2015) architecture as its internal classifier h for attacking all these victim models, i.e., the architecture of g and h is by no means similar to that of any of the victim models.
Implementation details. We mostly test our PDA with pre-training of the policy network g, and its performance without pre-training will be presented in the appendices. When pre-training is to be performed, we should construct a training dataset S for it. On MNIST and CIFAR-10, we randomly sample 5,000 images which are confirmed to be correctly classified by the victim model from their official test set to construct S. On ImageNet, we similarly gather 50,000 images from an auxiliary dataset called ImageNetV2 and the official ImageNet validation set to construct S. For each gathered image x, we sample mx = 500 actions at each iteration t (see Eq. (2)). When constructing S with the simplified policy for pre-training as described in Section 3.5, we choose the SGD optimizer without momentum, and we use a learning rate 0.003 in our PDA. Another 500 images are also collected to form the validation set for tuning all hyper-parameters for each of the three datasets (i.e., MNIST, CIFAR-10, and ImageNet).
3Pre-trained weights: https://github.com/IBM/Autozoom-Attack 4Pre-trained weights: https://github.com/IBM/Autozoom-Attack 5Pre-trained weights: https://github.com/bearpaw/pytorch-classification
After a pre-trained policy network is obtained, the final performance of our PDA is evaluated based on a set of 1,000 clean images disjoint from the training/validation set described in the above paragraph (i.e., these 1,000 images are not used in training the policy network and tuning hyperparameters). At this stage, we sample only mx = 25 actions at each iteration for faster convergence in all experiments. We use the Adam optimizer (Kingma & Ba, 2014) with a learning rate of 0.0001 and the cross entropy regularization in Eq. 5 with a coefficient λ = 0.003 is applied. To achieve better trade-offs between exploration and exploitation, we initialize σ in the sampling Gaussian distribution to be 0.003, and scale it at each iteration if necessary, to make sure that the ratio of the average output of the policy network and σ lies in the range of [0.01, 0.5]. The value of σ is doubled if all sampled actions at an iteration receive zero reward. The step size during attack is set as 0.4‖x−x′t‖2, and the geometric regression strategy suggested by Chen et al. (2020) is also applied. To make a fair comparison, we also sample 25 probs around each example on the decision boundary for HopSkipJumpAttack, which yields better performance than its default setting which used 100 probs. Other hyper-parameters for performing boundary attack and HopSkipJumpAttack are kept as in their original papers. The starting adversarial examples for untargeted attacks are obtained by sampling from a uniform distribution in the input space [0, 1]n until the adversarial criterion is met, and for targeted attacks we directly select a benign image from the target class as the starting point since for some victim models it is often hard to find an input from a particular class via random sampling. Once generated, the starting points are shared among all the compared attack methods.

heading: 4.2 COMPARISON WITH THE STATE-OF-THE-ARTS
text: Table 1 compares our PDA with the state-of-the-art methods for performing hard-label black-box untargeted attacks. We consider a threat model where a large number of benign examples are required to be attacked in a hard-label black-box manner, such that the queries for pre-training could be omitted. It can be easily seen that in general our method outperforms its competitors, especially in the earlier stage of attacks, which is of importance when lower query budgets are permitted. In particular, with only 100 queries, our method leads to only one-sixth to one-third distortions when compared with HopSkipJumpAttack which is the second best. With a larger query budget of 500, HopSkipJumpAttack still leads to 1.5 to 3.0 times larger distortion than our method. More interestingly, on CIFAR-10, when attacking the ResNet-50 model guarded with adversarial training, which is proved to be one of the most powerful defenses, the superiority of our PDA is in fact more significant. Such an observation is considered consistent with a phenomenon discovered in prior work (Yu et al., 2019; Zhang & Wang, 2019) which shows that adversarially trained models often have less sharp peaks and cliffs on the decision boundary, making it easier for our policy network to capture. Table 2 shows the results for targeted attacks and our PDA again outperforms others in general. Performance of our PDA under different pre-training configurations is given in the appendices. In practice, pre-training is recommended since it is crucial for the superior performance of our method.

heading: 4.3 ABLATION STUDY
text: We perform an ablation study on how the architecture design of the policy network would affect the performance of our PDA. More specifically, we train policy networks with several different architectures on the same set S and then attempt to attack the CNN victim model on CIFAR-10 using these policy networks. In addition to our design (as introduced in Section 3.4) which leverages the gradient of an internal classifier h, we mostly consider the U-Net (Ronneberger et al., 2015) which is a popular option for the learning models for assisting adversarial attacks. We compare our proposed architecture with several U-Nets with different configurations. Details of their architectures can be found at https://github.com/milesial/Pytorch-UNet. Note that, for U-Net models, the cross-entropy regularization is not applied, since they do not perform classification and there
is no logit for computing such a loss. The performance of different policy networks in terms of the mean l2 distortion is reported in Table 3. Obviously, we can see that the proposed architecture outperforms U-Net significantly in the framework of our PDA.

heading: 5 CONCLUSION
text: Existing hard-label black-box attacks often suffer from very high query complexity. In this paper, we have introduced a model-based method (i.e., PDA) for learning from past queries and model feedbacks, based on a reinforcement learning formulation of the attack. We have developed a novel architecture for the policy network that is designed to suggest promising search directions for the adversarial examples. Moreover, it has been demonstrated that pre-training of such a policy network, which is crucial for the attack performance, can be effectively performed using prior attacking logs on the same victim model. Experimental results on various victim models (including both naturally and adversarially trained ones) trained on different datasets (including MNIST, CIFAR-10, and ImageNet) suggest that the proposed PDA significantly outperforms existing state-of-the-arts in terms of query efficiency.

heading: ACKNOWLEDGMENTS
text: This work is funded by the National Key Research and Development Program of China (No. 2018AAA0100701) and the NSFC 61876095.

heading: A OPTIMAL SEARCH DIRECTION FOR HOPSKIPJUMPATTACK
text: We illustrate the optimal search direction for HopSkipJumpAttack in a two-dimensional input space in Figure 2. The decision boundary is illustrated by a horizontal straight line (denoted by B), the benign counterpart x of the adversarial example is assumed to be belowB, and the circleC centered at the candidate adversarial example x′t with a small radius δ shows all possible locations after jumping along some directions by distance δ from x′t. The gradient direction ug shall be vertical under the locally linear assumption, and after updating x′t along that direction (by δ) and projecting the updated image back onto the decision boundary B (path marked in blue), we obtain xgt . Let the straight line T be the tangent line of C which goes through x, and uo is the direction which is perpendicular to T . If we update x′t along uo and then project the result back to B (path marked in green), xot is obtained. Clearly, x o t would have a smaller distortion than x g t : ‖xot−x‖2 < ‖xgt−x‖2, indicating uo is a better direction than the gradient ug in the sense of cutting distortion. It is also easy to verify uo is the optimal updating direction in this two-dimensional case.

heading: B MEDIAN DISTORTIONS
text: We report the median l2 distortions over perturbing test images at different query count budgets for performing untargeted attacks in Table 4. It can be easily seen that our method outperforms existing state-of-the-arts on all test cases, especially in the earlier stages of the attacks.

heading: C EFFECTS OF PRE-TRAINING
text: In this section, we study the effects of pre-training in our PDA. We only show results on MNIST with CNN as the victim model which is faster to be evaluated. We test our PDA under several different pre-training configurations: (a): the policy network does not own the internal classifier h, i.e., its output is input-agnostic and thus pre-training is meaningless in this case; (b): the policy network has a VGG-13 as its internal classifier as in the main paper, and it is pre-trained on data sets with smaller sizes. To achieve the goal, we first sample a subset D′ with size |D′| ∈ {0, 50, 500, 5000} from D which has 5,000 benign images in total and is used to create S in the main paper, and then we collect tuples from D′ to form a possibly smaller pre-training set.
Table 5 summarizes our results, in which the second column indicates the size of D′ which reflects the cost for pre-training, in particular, |D′| = 0 means no pre-training is applied, and the third column indicates whether or not the policy network owns an internal classifier. We see when pretraining is not applied, with a simplified policy (i.e., without h) our PDA can achieve comparable performance to HopSkipJumpAttack, yet directly incorporating a randomly initialized internal classifier into the policy network would lead to much worse result since, in this case, the initial search directions for adversarial example suggested by the policy network are nearly random and often completely failed to reduce the required distortions. Moreover, it can also be seen that, with the size of the pre-training set increased, the performance of our PDA is also gradually improved. Figure 3 provides visualizations of generated adversarial examples on a randomly selected benign image. Each row in the figure represents a pre-training configuration, and images in each column are candidate adversarial examples under a certain query count budget. The benign example is classified as “7” by the victim model, and all images in the figure are classified as “3”. The first column of the
figure shows the common initial adversarial example for all configurations, which is generated via sampling from the uniform distribution in [0, 1]n as described in the main paper. It can be seen that our method could provide adversarial images with higher qualities, especially in the early stage.
Since favorable results can be obtained with light or even no pre-training of the policy network, our PDA is also applicable to scenarios where only a few adversarial examples are to be generated. This paper introduces a novel perspective of viewing hard-label black-box attacks (as a reinforcement learning problem), thus more advanced policy gradient methods an also be tested for improving the performance of our PDA, with or without pre-training.
D VALUES OF BASELINE LEVELS
In this section, we explain how the values of β1 = 0 and β2 = 0.25 are selected. These values are tuned under a constraint of β1 < β2. We try different combinations of values in {0, 0.25, 0.5, 1.0} for β1 and β2 on MNIST and found that β1 = 0, β2 = 0.25 provide the best result on the validation set (containing 500 images as described in Section 4.1), and these values are then applied to all other experiments. In Table 6 we report the mean l2 distortions when attacking a CNN victim on MNIST test images (1,000 images as described in Section 4.1) at different query count budgets. We see that the performance of our method is fairly robust to tested values of β1 and β2, and smaller values usually have better performance on the late stage of attacks.

heading: E TRANSFERABILITY OF THE PRE-TRAINED POLICY NETWORK
text: In this section, we study the transferability of the pre-trained policy network across different victim models on the same dataset. To do so, on CIFAR-10, we use policy networks pre-trained on {CNN, WRN, ResNet-50 Adv.} to attack all these three victim models. Table 7 summarizes our results, in which the first column is the victim model used to evaluate the attack performance, and the second column is the victim model used to collect dataset S for pre-training. We see from Table 7 that when using a policy network pre-trained on a different victim model to attack, the attacking performance is degraded on all test cases. However, in the early stage of attacking process, our PDA can still consistently provide smaller distortions even when the policy network is pre-trained on a different victim model, enabling attackers to benefit from our PDA by using it to provide high quality starting points for other attacks. More importantly, the transferability allows one to pre-train the policy network on some local models, thus the queries consumed in collecting the pre-training dataset can be practically saved.

heading: F ATTACK PERFORMANCE ON THE PRE-TRAINING DATASET
text: The untargeted attack performance on the pre-training dataset S is reported in Table 8. We see our method has the best performance on the pre-training images, just like in the test images. By comparing the performance of our method on the pre-training images and the test images, we see the “overfitting” of our method is moderate and acceptable in practice.

heading: G COMPUTATION AND MEMORY COMPLEXITY
text: As a policy network is involved in our proposed attack process, our PDA method naturally has higher computation and memory complexity than baseline methods. In our experiment for attacking a ResNet-18 model on ImageNet, for each 100 queries to the victim model, it costs our method extra 947ms on a single GPU (excluding the inference time of the victim model) to fine-tune the policy
network, while HopSkipJumpAttack requires 354ms. Although it seems that our method is computational more intensive, the extra overhead is acceptable considering that the inference of the victim model is also costly (672ms), also the run-time of our method can be reduced by using multiple GPUs. As for GPU memory consumption, when attacking the ResNet-18 victim using batch size 25, our method needs additional ∼5GB GPU memory compared with HopSkipJumpAttack which needs ∼2GB GPU memory. The computational and memory cost of our method can be reduced by compressing the policy network, which is to be explored in future work.

heading: H COMPARISON TO SIGN-OPT
text: In this section, we compare our method to a recent hard-label black-box attack named SignOPT (Cheng et al., 2020). We directly use their official implementation and hyper-parameters 6. When evaluating Sign-OPT, we use the same victim networks and initial adversarial images as in our method to make a fair comparison. The untargeted attack performance of Sign-OPT on MNIST and CIFAR-10 is reported in Table 9. We see, in general, our method outperforms Sign-OPT, especially in the earlier stage of attack.

Review summaries:
This paper proposes a new hard-label black-box adversarial attack method based on reinforcement learning. The authors formulate the black-box attacking problem as a reinforcement learning problem, and design a policy network to learn the appropriate attack directions, in order to achieve more efficient attacks. The proposed policy-driven attack (PDA) algorithm is able to craft adversarial examples with lower distortions under the same query budgets. Experiment results show that with a pre-trained policy model, PDA outperforms two baseline methods, Boundary Attack and HopSkipJumpAttack.

This work proposes to formulate the problem of black-box adversarial attacks as learning a policy network that predicts offsets to some initial guesses of adversarial examples. The proposed PDA method tackles the problematic situation of queries with only hard labels. A specific reward, architecture, and pretraining setups are designed for the policy network to learn useful directions in updating the adversarial examples. Experiments on MNIST, CIFAR10, and ImageNet show the proposed PDA produced less distorted adversarial examples with less sampling budget for the black box attacks than two recent baseline attacks.

This paper proposes a new hard-label black-box adversarial attack method based on reinforcement learning. The general idea is to improve the adversarial noise compressing efficiency taking advantage of past queries and the policy network. Experiments are conducted on MNIST, CIFAR-10 and ImageNet and achieved superior performance compared to other hard-label black-box attacks. In addition, ablation studies are conducted to verify the effectiveness of the proposed attack.