Policy-Driven Attack: Learning to Query for Hard-label Black-box Adversarial Examples
Authors: Ziang Yan
Yiwen Guo
Jian Liang
Changshui Zhang
Venue: ICLR 2021 Poster (2021)
Keywords: hard-label attack
black-box attack
adversarial attack
reinforcement learning

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

Published as a conference paper at ICLR 2021
POLICY-DRIVEN ATTACK: LEARNING TO QUERY FOR HARD-LABEL BLACK-BOX ADVERSARIAL EXAMPLES
Ziang Yan 1.2 Yiwen Guo Jian Liang', Changshui Zhang'
Institute for Artificial Intelligence, Tsinghua University (THUAI), Beijing National Research Center for Information Science and Technology (BNRist), Department of Automation, Trrtiion,,Tinghuuu University, Beijing, P.R.China
2 ByteDance AI Lab
3 Alibaba Group
yzal 8emailmmllll.mm.ma ts tsinghua. edu. en, guoyiwen wwwpywwwwaai@yyydddeeeea xuelang.o 1 aiealliaaalii alibaba--a-e inc. com, 2cs
edu. cn
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 gen- erally suffer from high query complexity, especially when only the top-1 decision (i.e., the hard-label prediction) of the vietim model is available. In this paper, we propose a novel hard-label black-box attack named Policy-Driven Attack, to re- duce the query complexity. Our core idea is learn promising search directions of the adversarial examples using well-designed policy network in novel rein- forcement learning formulation, which the queries become more sensible. Ex- perimental results demonstrate that our method can significantly reduce the query complexity comparison with existing state-of-the-arr hard-label Maxk-box at- tacks on various image classification benchmark datasets. Code and models for reproducing our results are available at http:::: / //gituub. com/ ZiangYan/ pda pytorch
INTRODUCTION
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 proppproppggtion, and thus first-order optimization techniques can be directly applied to craft adversarial examples in this setting (Szegedy al. 2014| Goodfellow et al. 2015 Carlini & Wagner 2017 Madry al. [0188] 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-bor attacks. In order to gain high attack success rates, delicate queries the victim model are normally required.
Recent methods can be roughly categorized into crose- attacks (Chen et al. 2017] 2017:110 IIyas et al.
2018 Nitin Bhagoji et 2018 llaas et al.]
[2019] Yan et al., (2019) Li al.) 2020b]
al. 2019
Du et al. |019 Li et al. 2019 Bai et al.
2020) and hard-label attacks (a.k.a, reciisionbbsed at-
tacks) (Brendel et al. 2018 Cheng et al. 2019 Dong et al. 2019 Shi et al. (209): Brunner et al.
2019 Chen al. 2020 Rahmati al. 2020 Li al. 2020al Shi al. [2200] Chen & Gul 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-basee attacks, while in a more practical scenario where only the top-1 class prediction available, the adversaries will have resort hard-label attacks. Since less informa- tion is exposed from such feedback of the victim model, hard-label attacks often bare higher query complexity than that of acore-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 intern ByteDance AT Lab.

---

Published as a conference paper at ICLR 2021
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 vic- tim model and analyzing its feedback) into 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 reinforcement learning formulation enables us to learn the non 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 exam- ples 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 small number of query-reward pairs obtained from the performance log of prior attacks (with or with- out policy) to the same victim model. Experiments show that our policy-driven attack (PDA) can achieve significantly lower distortions than existing -tate-of-the-arts under the same query budgets.
2 RELATED WORK
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 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. (018) 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 al.] [014]] [allmann et al., 2017) to estimate the gradients over proxy scores, and then mounted variant of PGD attack (Madry et al. 2018) with the estimated gradients. Towards improving the efficiency of gradient estimation, [heng et al. (2019) and Chen et al. (2020) further introduced continuous optimization formulation and unbiased gradient estimation with careful error control, respectively. The gradients were estimated via issuing probe queries from 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 (Sileehheeee 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 al. 2019 Bai et al. 2020). Our method naturally different from them in problem settings iscore-based vs labell and problem formulations. In the autonomous field, |Handi et al. (2020) proposed to formulate the generation of semantic attacks as a reinforce- ment 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 reinforce- ment 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 addi- tion 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.
OUR POLICY-DRIVEN ATTACK
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
R to fool a k-way victim classifier f R. - IR* into making an incorrect decision: arg max, f(x'); ) # y. where a' is the adversarial example generated by perturbing the benign image and y is the true label of æt. The adversaries would generally prefer
2

---

Published as a conference paper at ICLR 2021
adversarial examples x' with smaller distortions | 2212 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 method (in Section [.T 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..
3.1 MOTIVATIONS
Most recent hard-label attacks followed a common pipeline of searching from a starting point which was already an adversarial image' 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 reach the decision boundary efficiently.
Let us take a very recent attack named HopSkiplumpAAtack (Chen et al., 2020) as an example. Given the current estimation x of the adversarial example at each iteration, HopSkip/umpAAtaee first performed binary search to project it onto the decision boundary of the victim model. Denote a' as the updated example that was on the decision boundary already, HopSkip/umpAttar 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 æ', 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.
then
In comparison with boundary attack (Brendel et al. 2018), HopSkippumpAAtaakk 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 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 HopSkiplumpAtttak. We also found that the task of performing hard- label 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- tunee on the fly during each attack process, such that little query is required once the model has been well-trained.
3.2 ATTACK AS REINFORCEMENT LEARNING PROBLEM
In this paper, we consider both targeted attacks and untargeted attacks. Given 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 a; on the decision boundary of the victim model (or called the candidate adversarial example) represents the state at each timestamp t. The agent uses 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 required to fool the vietim model. The action here incorporates searching along promising direction a /|alll where a, E R" is sampled from an isotropic Gaussian distribution whose mean vector is given by the policy network μr, = g( V, v²) I where y' is the target label, and its covariance matrix is given by Σ = al E R=*x, in which the value of a E IR is set to be gradually increased as the attack on each sample progresses, and I E Rx indicates the n x n identity matrix. With a, the agent searches along its direction az/ /|all lI 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, æ; 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 reward Tr E IR
In practice, 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 benign sample from the adversarial class.
3

---

Published as a conference paper at ICLR 2021
Algorithm Policy-Driven Attack Algorithm
1: Input: the environment ( y. f); the target label y', initial adversarial image a' R which lies on the decision boundary; the policy network g-
2: Output:
adversarial example.
3: Initialize the step index 4-1 1.
4: while the query count limit not reached do
5: // Determine the baseline l to evaluate the potential of different actions
6: Pt f g( y. y'), 2= t- BS 8 ie: |1ill2 æ, f). where BS(....) performs binary search
7: Set the distortion reduction of x as baseline: le < max || -a = || x xl12. {min
8:
9:
I/ Collect actions and rewards, and update the policy network
Sample M actions: ae,i ~ Ni otf), E (1.2...... .M} Assign rewards Tt, to each actions with our mechanism introduced in Section 3.3 Update the policy network using one-step REINFORCE on M pairs: (ar,,, Tt.a
11:
12:
13:
14:
Update adversarial image using predicted direction pe g (<x,, y.y. y/) if
15:
| æ|12 S ||o| x||2, otherwise μt t ar,5", 1- arg Trç
16:
2/41 < BS + 6 1e 2.
Mr
17:
18:
Update other variables Double if all M rewards are zeros: 0.41 f- 2 oy; else keep it: 0141 f- Oz
19:
20:
1 6-1+1
21:
end while
return final adversarial image x/
based on the performance of each action and the corresponding a; is given to the agent for updating the parameter of the policy network. All details of our PDA are summarized in Algorithm
Powered by the reinforcement learning framework, we can use policy gradient algorithms to train the policy network g to generate promising search directions in direct way. For simplicity, use the one-step REINFORCE (Williams 1992) the sequel of this paper and leave the exploration of more advanced policy gradient algorithms to future work.
3.3 REWARD AND ACTION
o + 8 a/l|a|12
V2
B
E
Figure 1: The reward assignment mechanism of our method. Ares with color magenta, yellow, and green corresponded to actions with reward 0, 1, and 2, respectively.
Figure SoaureTillann illlsttratss how we assign the scalar reward r given current candidate adversarial example o/ and an action aę- The decision boundary is illustrated by a horizontal straight line (denoted by B) in the figure, the benign counterpart æ is assumed to be below B, and the circle C' centered at at with small radius 8 shows all possible locations after jumping along the directions of some actions by 8 from 2/-- As described earlier, the reward should be assigned based on the amount of potential distortion reduction brought by a, A direct evaluation can be achieved by jumping along the direction of a; first and then projecting the updated example back onto the decision boundary via binary search, to see how much improvement obtained. However, since we evaluate actions a; simultaneously at an iteration (see Algorithm T and binary search needs to be performed for each of them, and the overall process would be prohibitively (query- sexeensvxee On this point, to efficiently assess the performance of an action, instead evaluate whether the reduction of distortion by taking
4

---

Published as a conference paper at ICLR 2021
particular action can exceed particular baselines. Concretely, we first evaluate μ4 g( y, y/) as an action directly by using binary search in a way as just described. Suppose that it can reduce the required adversarial distortion? by 4, then we setup two levels of baselines || ll 31 4 and ||æ== 32 l, to see whether other actions can lead to adversarial examples with closer distance (than these baselines) from the benign example at, in which 81 = 0 and 82 0.25. As shown in Figure[] for an action a E {ar,sh. we first obtain 2 + 8 a/ a/||aa|2 and then move it towards x to see how much reward it can obtain. The two ares V1 and 1/2 indicates where the same progress as the two baselines can be achieved, thus we can further project æ + 8 a....all [a/la||z onto the ares to see if the projections (i.e, V and x²!²) are still adversarial. It can be seen that / is still adversarial yet a. is not. We assign a reward to such an action a. If both the projections are still adversarial we shall assign a reward of 2, and neither of them is adversarial, zero reward is assigned. Since x V not adversarial could imply that 2 is also not adversarial, such way reduces the number of queries for assessing each action to at most Vi and 2/22 ) and makes our PDA more query-efficient
3.4 ARCHITECTURE OF THE POLICY NETWORK
As described in Section 3.2 the goal of our policy network is to predict direction based on which the optimal adversarial example/candidate can be casily found. Its input is the current example on the decision boundary of the vietim 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. Naive architecture designs of the policy network include the conventional auto-encoders and U-Net (Ronneberger et al. (015).. However, our experimental results suggest that such off-the-sheff 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 (c.g.. predicting 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 new architecture for the policy network for our PDA. First, we know from HopSkipJumpAttack that the gradient direction at x/, 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 æi,, the ground- truth label y of the benign example, and the target label y' as input, and mapped them to a search direction in R". In this spirit, the policy network is designed own an internal classifier h : R" + R* which performs a k-way classification. The number & 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 as descent search direction. Following the logit-diff loss developed for the white-box setting in Carlini & Wagner (2017)'s 's work, we propose to use:
g(2/s v, v/) V at h(xr)y - V h(rr)) + b,,
(1)
as the output of the policy network, where a Icarnable bias vector b E IR" 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, can also learn to explore even better search directions other than the gradient directions.
3.5 (OPTIONAL) PRE- TEEENRRINING OF THE POLICY NETWORK.
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
IIf f4, is unable reduce the distortion, or < 0.05 6, we clip le to 0.05 8 for numerical stability.
5

---

Published as a conference paper at ICLR 2021
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 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 & 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 policy network, i.e., using an input-independent policy for it. Concretely, we can instead sample each direction a. from the distribution N (b, o, the timestamp t, where b here is still learnable, just like in Eq. ( 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 - {(a", 2, a"") {1, mz
(2)
where my is the total number of iterations, and x²'. y/", a" 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- pre-training, we suggest a simple post-processing strategy to discard the tuples in TT with less informative candi- date adversarial examples: for i 2 2, we discard the i-th tuple in T n if ||œ2" æ112 >> 0.99||a² - -a1 1/22. 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 T and the final pre-training set S is constructed using this sort of set gathered from all attack trajectories using the simplified policy, i.c..
$
T
(3)
(z.
Then it is how to pre-train the policy network given 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 somehow align with the considered effective search directions (i.e., a.") found by the aforementioned simplified policy. On this point, we introduce the cosine similarity S together with regularizer V/ which incorporates the classification loss to achieve these two goals, making the pre-training loss L as:
L
-S (g(a", .U. a") + A
".
(4)
(ce" J...."""" y
where .(s,)) calculates the cosine similarity between its two input vectors, is the coefficient for regularization, and Vi serves as regularizer which is given by:
(h(xx), h(="),))))))))))"")))) y. v²) CE(h(x), + CE(((=")) (
" CE(((=")) v"",
(5)
where CE(,,) -) calculates the cross-entropy loss given logits and labels. Since x" is on the decision boundary of the victim model f. must assign 0.5 probability to both the benign class y and the adversarial class y" at x", which interprets the terms CCC(((())) v) and CEE((()")
EXPERIMENTS
In this section, we evaluate the effectiveness of our method on three datasets: MNIST (LeCun al.
2010), CIFAR-10 (Krizhevsky & Hinton 2009), and ImageNet (Russakovsky et al. 2015). We compare our method with Boundary Attack (Brendel al. 2018) and HopSkipJumpAttann
CChn
ct al. 2020) in both untargeted and targeted settings, and the required b 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 comprehensive comparison, we report the distortions at 1000, 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 [ 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 only show results MNIST and CIFAR-10 which are faster to be evaluated. All experiments are conducted on NVIDIA GTX 2080 Ti GPUs with PoTorch (Paszke al. 2017).

---

Published as a conference paper at ICLR 2021
Table 1: Mean & distortions for performing untargeted attacks with different query budgets.
Datasct
Victim Model
Mothod
@ 100
@500
@ @IK
@5KK
10K
@25K
Boundary Attack
10.179
9.970
9.692
8.960
3,670
1.850
MNIST
CNN
HopSkiplump-Atrekk
7.267
3.576
2.709
1.843
1.721
1.641
2,204
2,053
1,994
1.674
1663
1.639
Boundary Attack
9.625
8.649
8.463
5,442
1.408
0.395
CNN
HopSkip/umpAttack
4.567
1.520
0.911
0.378
0.304
0.261
Ours
0.640
0.546
0.507
0.358
0.298
0.263
Boundary Atiack
9.268
8.095
7.972
3.639
0.664
0.287
CIFAR-10
WRN
HopSkiplunpAAtickk
3.041
1.052
0.649
0.268
0.213
0.179
Ours
0,700
0,515
0.453
0.273
0,217
0.174
Boundary Attack
10.672
10.273
10.217
9.064
4,998
2.378
ResNet50 Adv.
HogSkiphump-AAtack
7:980
5.453
4.353
2.521
2,097
1.793
2.365
1.926
1.733
Boundary Attack
65. 8.0
60. 868
60.618
39,359
13 8,888
4,877
ImageNet
18
HopSkiphumpAAAtckk Ours
36.594
4,846
2,883
11,998
8.200
6.751
4.093
2,921
1.481
Table 2: Mean &g distortions for performing targeted attacks with different query budgets.
Dataset
Victim Model
Method
@ 1100
@:500
@IK
@5K
10K
25K
Boundary Attack
5.559
5.486
5,480
5.417
4.087
2,638
MNIST
CNN
HopSkiplampAAtack
5.291
4,480
3,786
2.644
2.423
2.268
Ours
3.072
2.772
2.712
2.423
2.355
2.314
Boundary Atlack
11.194
10.075
9.381
7,933
2.778
0.750
CNN
HopSkipJump
8,864
3.763
2.118
0.724
0.549
0.448
Ours
1.426
1.207
0.930
0.691
0.589
0.481
CIFAR-I0
WRN
HopSkipJampAtrack
Boundary Attack
10.021
7.770
3.191
8.269
7.903
1.573
5.368
0.398
0.295
1.223
0.467
0.240
Ours
2.759
1,518
1.203
0.680
0.494
0.321
Boundary Atlack
11,268
11.086
11,002
10.677
7.386
3.702
ResNer50 Adv.
HopSkiplumpAtrac
10.316
8.592
7.021
3,766
3.030
2.524
Ours
4.327
3.843
3.704
3.119
2.789
2.419
4.1 EXPERIMENTAL SETUP
Victim models and ht 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 test er- ror rate of 0.59%, since it is widely adopted as a victim model in many related works. For CIFAR-IO, consider three victim models: (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 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 &g PGD attacks (c = 1.0). On ImageNet, we adopt a ResNet- (He et al., 2016) from the PyTorch official model zoo as the victim model, which shows top-1 eтror rate of 30.24% 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 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 m = 500 actions at each iteration t (see Eq. 2 When constructing S with the simplified policy for pre- training without momentum, and we use a learning rate 0.003 in our PDA. Another 500 images are also collected form the validation set for tuning all hyper-parameters for each of the three datasets (i.e., MNIST, CIFAR-10, 10, and ImageNet).
described in Section
we choose the SGD optimizer
'Pre-trained weights: http://///gaauuoo/////////tootoa 'Pre-trained https::/qi http::/ww.t///agaaaoooaa///a/aaa Pree-triined wttp://...pp/./o.ooo.c./////r/r. facaticciinn

---

Published as a conference paper at ICLR 2021
After a pre-trained policy network is obtained, the final performance of our PDA is evaluated based set described in the above
on a set of 1,000 clean images disjoint from the training/validateo not used in training the policy network and tuning hyper-
paragraph (i.e., these 1,000 images parameters). At this stage, we sample only mz = 25 actions at each iteration for faster convergence in all experiments. We use the Adam optimizer (Kingma & Ba 2014) with learning rate of 0.0001 and the cross entropy regularization in Eq. [ with coefficient À 0.003 is applied. To achieve better trade-off' between exploration and exploitation, we initialize in the sampling Gaussian dis- tribution 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.41|a: - - 22|12, 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 HopSkiiluumAAtack; which yields better performance than its default setting which used 100 probs. Other hyper-parameters for performing boundary attack and HopSkiplumpAAtack 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]" 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 find input from a particular class via random sampling. Once generated, the starting points are shared among all the compared attack methods.
4.2 COMPARISON WITH THE STATE-OF-THE-ANE
Table I compares our PDA with the state-of-the-ar thet---rtt methods for performing hard-label black-box untargeted attacks. We consider a threat model where a large number of benign examples are re- quired to be attacked in 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 HopSkiplumpAtttck which is the second best. With a larger query budget of 500, SooSkipJJupptttre
still leads to 1.5 to 3.0 times larger distortion than our method. More interest- ingly, 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 signifi- cant. Such an observation is considered consistent with a phenomenon discovered in prior work (Yu let 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- 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.
4.3 ABLATION STUDY
Table 3: Comparison of choosing different architectures for the policy network. Mean Eg distortions for performing untargeted attacks are evaluated.
Architecture
100
@500
@ IK
@5K
@ 10K
@25K
U-Net (small)
1.023
0.791
0.613
0.374
0.300
0.276
U-Net (medium)
0.871
0.772
0.587
0.362
0.288
0.273
U-Net (large)
0.882
0.741
0.589
0.365
0.308
0.262
Ours
0.640
0.546
0.507
0.358
0.298
0.263
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 & 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 ht 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 httts:: // //qithub. com/ ham/milee wwweessaalyytoorreee the cross-entropy regularization is not applied, since they do not perform classification and there
UNet Note that, for U-Net models,
8

---

Published as a conference paper at ICLR 2021
logit for computing such loss. The performance of different policy networks in terms of the mean l2 distortion is reported in 3 Obviously, we can see that the proposed architecture outperforms U-Net significantly in the framework of our PDA.
CONCLUSION
Existing hard-label black-box attacks often suffer from very high query complexity. In this paper, 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 suggest promising search directions for the adversarial examples. Moreover, it has been demonstrated that pre- treiiiiiingg of such a policy network, which is crucial for the attack performance, can 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 Im- ageNet) suggest that the proposed PDA significantly outperforms existing state-of-the-arts in terms of query efficiency.
ACKNOWLEDGMENTS
This work is funded by the National Key Research and Development Program of China (No. 201 2018AAA0100701) and the NSFC 61 61876095.
REFERENCES
Yang Bai, Yuyuan Zeng, Yong Jiang, Yisen Wang, Shu-Tao Tao Xia, and Weiwei Guo. Improving query efficiency of black-box adversarial attack. In ECCV, 2020.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision- based adversarial attacks: Reliable attacks against black-box machine learning models. In ICLR, 2018.
Thomas Brunner, Frederik Dichl, Michael Truong Le, and Alois Knoll. Guessing smart: Biased sampling for efficient black-box adversarial attacks. In ICCV, pp. 4958-4966, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In JEEE Symposium Security and Privacy (SP), 2017.
Jianbo Chen, Michael I Jordan, and Martin J Wainwright. Hopskipjumpattack: A query-efficient decision-based attack. In 2020 IEEE Symposium on Security and Privacy (SP), 2020.
Jinghui Chen and Quanquan Gu. Rays: A ray searching method for hard-label adversarial attack. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1739-1747, 2020.
Pin-Yo Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An optimization-based approach. In ICLR, 2019.
Minhao Cheng, Simranjit Singh, Patrick Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Sign-opt: A query-efficient hard-label adversarial attack. In ICLR, 2020.
Yinpeng Dong, Hang Su, Baoyuan Wu, Zhifeng Li, Wei Liu, Tong Zhang, and Jun Zhu. Efficient box adversarial attacks on face recognition. In CVPR, pp. 7714-7722, 2019.
Jiawei Du Hu Zhang. Jocy Tianyi Zhou, Yi Yang, and Jiashi Feng, Query-efficient meta attack to deep neural networks. arXiv preprint arXiv: /906.02.90002.99 2019.
Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019. URL http///cppee/gggtttooo..//////aa

---

Published as a conference paper at ICLR 2021
Ian J Goodffllow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Abdullah Hamdi, Mauthias Müller, and Bernard Ghanem. Sada: Semantic adversarial diagnostic attacks for autonomous applications. In AAAI, pp. 10901-10908, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, 2016.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In ICML, 2018.
Andrew lyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. In ICLR, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412.6944 2014.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, Citeseer, 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online). Available: http://yann. www.n. cocem..com//xdb/miiss, 2, 2010.
Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang. and Bo Li. Qeba: Query-efficient boundary- based blackbox attack. In CVPR, pp. 1221-1230 2020a.
Qizhang Li, Yiwen Guo, and Hao Chen. Yet another intermediate-level attack. In ECCV, 2020b.
Yandong Li, Lijun Li, Liqiang Wang, Tong Zhang, and Boqing Gong. Nattack: Learning the dis- tributions of adversarial examples for an improved black-box attack on deep neural networks. In ICMI., pp. 3866-3876, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Muhammad Muzammal Naseer, Salman H Khan, Muhammad Haris Khan, Fahad Shahbaz Khan, and Fatih Porikli. Cross-domain transferability of adversarial perturbations. In NeurLPS, pp- 12905-129155 2019.
Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box attacks deep neural networks using efficient query mechanisms. In ECCV, 2018.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vito,o, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NeurlPS Workshop, 2017.
Ali Rahmati, Seyed-Mohsen Dezeooii,,,,ooii, Pascal Frossard, and Huaiyu Dai. Geoda: geo- metric framework for black-box adversarial attacks. In CVPR, pp. 4446-8455, 2020.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedi- cal image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234 241. Springer, 2015.
Jérôme Rony, Luiz G Hafemann. Luiz S Oliveira, Ismail Ben Ayed, Robert Sabourin, and Eric Granger. Decoupling direction and norm for efficient gradient-based adversarial attacks and 2019.
defenses. In CVPR, pp.
Olga Russakovsky, Jia Deng. Hao Su. Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. Imagenet large scale visual recognition challenge. IJCV, 2015.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as a scalable alternative reinforcement learning, arXiv preprint arXiv:/703.0m 173.00003.,3864, 2017.
10

---

Published as a conference paper at ICLR 2021
Yucheng Shi, Siyu Wang, and Yahong Han. Curls & whey: Boosting black-box adversarial attacks. In CVPR, pp. 6519 6519-6527, 2019.
Yucheng Shi, Yahong Han, and Qi Tian. Polishing decision-based adversarial noise with a cus- tomized sampling. In CVPR, pp. 1030-1038, 2020.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game go with deep neural networks and tree search. nature, 529(7587):484-455 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2015.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Chun-Chen Tu, Paishun Ting, Pin-Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks. In AAAI, 2019.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. JMLR, 15(1):949-980, 2014.
Ronald J Williams. Simple statistical gradient- algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-255 256, 1992.
Ziang Yan, Yiwen Guo, and Changshui Zhang. Subspace attack: Exploiting promising subspaces for query-efficiees black-box attacks. In NeurlPS, pp. 3820 0920-3829, 2019.
Fuxun Yu, Zhuwei Qin, Chenchen Liu, Liang Zhao, Yanzhi Wang, and Xiang Chen. Interpreting and evaluating neural network robustness. In IJCAI, pp. 4199-4205. AAAI Press, 2019.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
Haichao Zhang and Jianyu Wang. Defense against adversarial attacks using feature scattering-based adversarial training. In NeurlPS, pp. 1831-1841, 2019.
A OPTIMAL SEARCH DIRECTION FOR HOPSKIPJUMPATTACK
We illustrate the optimal search direction for HopSkipJumpAAtack in a two-dimensional input space in Figure 2 The decision boundary is illustrated by horizontal straight line (denoted by B), the benign counterpart æ of the adversarial example is assumed to be below B, and the circle C' centered the candidate adversarial example xy with a small radius 8 shows all possible locations after jumping along some directions by distance from σ/ The gradient direction Ug shall be vertical under locally linear assumption, and after updating at along that direction (by 5) and projecting the updated image back onto the decision boundary B (path marked in blue), we obtain xz. Let the straight line T be the tangent line of which goes through æ, and u, is the direction which perpendicular to T'. If update x along u, and then project the result back B (path marked in green), xf is obtained. Clearly, xę would have a smaller distortion than x: | - x < ||x] - indicating u. is better direction than the gradient ug in the sense of cutting distortion. It is also easy to verify u. is the optimal updating direction in this two-dimensional case.
U
g
B
T
C
Figure The optimal search direction for HopSkijpJmppAttakk
11

---

Published as a conference paper at ICLR 2021
B MEDIAN DISTORTIONS
We report the median la distortions over perturbing test images at different query count budgets for performing untargeted attacks in T 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.
Table 4: Median l distortions for performing targeted attacks with different query budgets.
Dataset
Victim Model
Mothod
@ 100
@5500
@ IIK
@.5K
10K
@ @25
Boundary Attack
10.108
9.946
9.602
9.098
3,604
1.825
MNIST
CNN
HogSkippuumpAAttckk
7.114
3.505
2.664
1.813
1,693
1.616
Ours
2.165
2,014
1,955
1.631
1,602
1,595
Boundary Attack
8.825
7.985
7.970
5,000
1.189
0.332
CNN
HoysSkipluppAAttck
3.629
1.188
0.739
0.321
0,262
0.227
Ours
0.543
0.463
0.429
0.298
0.249
0.218
Boundaay Atlack
8.740
7.778
7.765
3,456
0.607
0.263
CIFAR-10
WRN
HopSkip/unpAArrck
2,638
0.927
0.589
0.248
0.199
0.168
Ours
0.578
0,448
0.400
0.244
0.195
0.158
Roundary Attack
9.303
8.881
8.869
8.647
5.071
2.296
ResNet50 Adv.
HoppkiiplumpAAttck
7.569
5.439
4.362
2.424
1.972
1.672
2.301
1,806
1.624
Boundary Atlack
64.303
58..447
58.888
37.352
11.123
3.299
ImageNet
1esNet-18
HopSkiplumpAttack
34.955
17.309
11,057
3,309
1.993
Ours
10.751
7.522
5.554
2.997
1.877
0.998
C EFFECTS OF PRE-TRAINING
In this section, we study the effects of pre-training in our PDA. We only show results 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 VGG-13 its internal classifier in the main paper, and it is pre-trained on data sets with smaller sizes. To achieve the goal, we first sample a subset ID' with size [V| E {0, 50, 500, 5000} from D which has 5,000 benign images in total and used create S in the main paper, and then we collect tuples from DV to form a possibly smaller pre-training set.
Table 5: Comparison of different pre-training configurations for the policy network. Mean & dis- tortions for performing untargeted attacks are evaluated.
Method
DJ
Has h?
@ 100
@500
1K
@5K
10K
@25K
Boundary Attack
10.179
9,970
9.692
8.960
3.670
1.850
HopSkiplumpAttack
7.267
3.576
2,709
1,843
1.721
1.641
Ours
No
7.314
3.489
2,981
1.809
1.772
1.648
Ours
Yes
9.052
6.438
4,994
2.130
1.720
1.665
Ours
Yes
3.028
2.571
2.320
1.696
1.636
1.632
Ours
500
Yes
2.287
2.104
2.024
1,668
1.629
1.625
Ours
5,000
Yes
2.204
2.053
1,994
1.674
1.643
1.639
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'] O means no pre-training is applied, and the third column indicates whether or not the policy network owns an internal classifier. We see when pre- training not applied, with simplified policy (i.e., without h) our PDA can achieve comparable performance to HopSkip/umpAttaan sifier 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 didate 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 "3". The first column of the
yet directly incorporating randomly initialized internal clas-
12

---

Published as a conference paper at ICLR 2021
figure shows the common initial adversarial example for all configurations, which is generated via sampling from the uniform distribution in [0, 1]"h as described in the main paper. It can be seen that method could provide adversarial images with higher qualities, especially in the early stage.
7
Boundary Attack
AopSkiplumpAttac
7
7
7
7
7
b only
7
7
7
7
7
7
TV| 0, VGG-13
7
7
7
7
7
DDI = 50, VGG-13
7
7
7
7
7
7
7
7
7
7
7
7
D 500, VGG-13
7
7
7
7
7
7
D 5, 000, VGG-13
init
@ 100
500
@1K
@55K
10K
@25K
Figure 3: Visualization of generated adversarial images using different pre-training configurations. All shown images are classified as "3" by the victim model.
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 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 81 and B: 0.25 are selected. These values are tuned under constraint of B1 < 32. We try different combinations of values in {0, 0.25, 0.5, 1.0) for 31 and B2 on MNIST and found that $1 =0 ,32 = 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 /2 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 31 and 32, and smaller values usually have better performance on the late stage of attacks.
Table Comparison of choosing different 31 and B2. Mean bg distortions for performing untargeted attacks on MNIST are evaluated, and the victim model is CNN.
(3),32)
@ 100
@ 500
@
IK
@.SK
@ 1OK
@255
(0, 0.25)
2.204
2.053
1.994
1.674
1.643
1.639
(0, 0.5)
2.202
2.035
1.973
1.673
1.648
1.641
(0. 1.0)
2.204
2.049
1.993
1.688
1.650
1.642
(0.25, 0.5)
2.202
2.032
1.977
1.782
1.767
1.748
(0.25, 1.0)
2.203
2.038
1.982
1.781
1.766
1,748
(0.5, 1.0)
2.199
2.028
1.986
1.902
1.885
1.859
13

---

Published as a conference paper at ICLR 2021
E TRANSFERABILITY OF THE PRE-TRAINED POLICY NETWORK
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 } to attack all these three victim models. Table summarizze 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 different victim model to attack, the attacking performance 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 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 pre-train the policy network on some local models, thus the queries consumed in collecting the pre-training dataset can be practically saved.
different
Table 7: Transferability of pre-trained policy networks on CIFAR-10. Last six columns are median l2 distortions for performing untargeted attacks with different query budgets.
Victim Model for Evaluation
Victim Model for Pre- Pre-Trainin
@100
@ @500
@1K
6:5K
10K
@125K
CNN
0.640
0.546
0.507
0.358
0.298
0.263
CNN
WRN
2.719
1.683
1.322
0.565
0.399
0.278
ResNet50 Adv.
1.405
1.087
0.895
0.422
0.315
0.249
1.035
WRN
WRN
0,700
0.515
0.483
0.273
0.217
0.174
ResNet50 Adv.
2,028
1,474
1,173
0.482
0.309
0.197
CNN
6,324
5,257
4,790
3.146
2.449
18277
ResNet50 Adv.
WRN
6.737
5.697
5,203
3.524
2,807
2.020
ResNet50 Adv.
2,638
2.454
2.365
1.926
1,733
1.570
F ATTACK PERFORMANCE ON THE PRE-TRAINING DATASET
The untargeted attack performance on the pre-training dataset S is reported in Table g 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.
Table 8: Mean & distortions for performing untargeted attacks with different query budgets on the pre-training dataset S.
Dataset
Victim Model
Method
@15K
@225
Boundary Attack
10.252
10.067
9.774
9.059
3,700
1.871
MNIST
CNN
3.607
2.728
1.855
1.732
Ours
2.229
2.075
2.015
1.692
1.660
1.654
Boundary Attack umpStkipunpAAAtckk
8.385
5.462
1.403
CNN
4.396
1.448
0.874
0.371
0.300
0.258
0.464
0.343
0.290
0.257
Boundary Attack
9,318
8.047
7.928
3.567
0.663
0.293
CIFAR-
WRN
HoySkiplumpAAtnck
3,020
1.050
0.655
0.273
0,218
0. 184
Ours
0.660
0.506
0.448
0.274
0.221
0.177
Boundary Attack
10.481
10.091
10.039
8.990
5.020
2.422
ResNe150 Adv.
HopSkiplumpAAtrck
7.938
5.473
4.390
2.575
2.137
1.817
Ours
2,531
2.377
2.327
1,981
1.791
1.616
Boundary Atlack
66.007
61.033
60.767
39.710
13.548
4.566
ImageNet
ResNot-18
HopSkiplumpAtnek
36.812
20.701
14.146
4.779
2.815
1.440
Ours
8.132
6.900
5.027
3.761
2.148
1.361
G COMPUTATION AND MEMORY COMPLEXITY
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 single GPU (excluding the inference time of the victim model) to fine-tune the policy
14

---

Published as a conference paper at ICLR 2021
network, while HopSkip/umpAAttack requires 354ms. Although it seems that method is compu- tational 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 GPUs. As for GPÚ memory consumption, when attacking the ResNet-18 victim using hatch size 25, method needs additional ~5GB GPU memory compared with HopSkipJumpAAtae 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.
be reduced by using multiple
H COMPARISON TO SIGN-OPT
In this section, we compare our method to recent hard-label black-box attack named Sign- OPT (Ceng 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 in our method to make a fair comparison. The untargeted attack performance of Sign-OPT on MNIST and CIFAR-10 is reported in Table g We see, in general, our method outperforms Sign-OPT, espe- cially the earlier stage of attack.
Table 9: Mean & distortions for performing untargeted attacks with different query budgets.
Dataset
Victim Model
Method
@:100
@:500
@1K
10K
Boundary Atlack
10.179
9.970
9.692
8.960
3.670
1,850
MNIST
CNN
HopSkiplumpAAtack
Sign-OPT
10.009
7.267
5.398
3,576
2,709
3.381
2.019
1.843
1.721
1.698
1.641
1.669
Ours
2.204
2.053
1.994
1.674
1.643
1.639
Boundary Attack
9.625
8.649
8.463
5.442
1,408
0.395
CNN
HopSkiplump-Atra
4.567
1.520
0.911
0.378
0.304
0.261
Sign OPT
6.018
3.221
1.498
0.404
0.287
0.250
Ours
0.640
0.546
0.507
0.358
0.298
0.263
Boundary Atrack
9. 9.268
7,972
3.639
0.664
0.287
CIFAR- 10
HopSkiplumpAAtrckk
3.041
1.052
0.649
0.268
0.213
0.179
WRN
Sign-OPT
5.113
2.099
0.757
0.341
0.226
0,193
Ours
0,700
0.515
0.453
0.273
0.217
0.174
Boundary
9.064
2.378
HopSkiplumpAAtack
7,980
5.453
4,353
2.521
2.097
1.793
ResNet50 Adv.
Sign-OPT
1.784
Ours
2.638
2.454
2.365
1.926
1.733
1.570
15


Reviews:
[{"review_id": "iCjCYRo9xeI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThere is almost no intersection between reinforcement learning and adversarial attacks for three main reasons. First of all, the action space of optimizing adversarial noises is too large for the reinforcement learning algorithm to converge. Secondly, the optimal attack strategies of different images are quite different, so it is difficult to learning a unified policy network to attack the whole image classification dataset. In addition, it is difficult to design the value function to guide the attack process. This paper innovatively applies reinforcement learning in the neighborhood of the decision boundary and solves the above problem, realizing the adaptive adjustment of the noise-searching direction. \n\nI have three questions about the practicality of the proposed attack. First, according to algorithm 1, the single action in the policy-driven attack is a direction sampled from Gaussian distribution, so the dimensionality of the action space is still high. Will this affect the convergence of the policy network? Secondly, if the policy network is optimized after each query, will the attack speed be severely lagged? In addition, section 3.5 of this paper discussed the pre-training of the policy network. I wonder whether the policy and the target model are coupled. If the target model changes, is it necessary to retrain the policy network? This may affect the practicability of the attack.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "P7IEjW0Ribr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary** :\nThis 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.\n\n**Strengths** :\n- The quarry efficiency is demonstrated compared to the two baselines (Boundary Attack, HopSkipJumpAttack) with less distortion on standard datasets and models.\n- The paper is well written and well presented. The mathematical notations are clear and informative. \n- The use of policy networks to produce black-box adversarial attacks is a novel idea. It might open a direction for other fields interested in security besides the usefulness in the adversarial ML community. \n\n**Weaknesses**:\n- The work has a limited ablation study. While the authors did provide an ablation on the policy network architecture and pretraining, some essential components of the reward setup and the algorithm are given without proper justification nor ablation study, e.g., the 0.5 and 0 of $\\beta$ values in the reward limits in Algorithm 1. It would also be appreciated to show the attack's transferability between different models on the same datasets. \n- The proposed pipeline is complicated compared to the baselines. Pre-Training a policy network, then training the network adds to the computing complexity of the problem. While the sampling efficiency has increased, the compute and memory efficiency of the attacks have decreased. The baselines NATTACK: ( Li et. al , ICML 2019) and AutoZoom (Tu et. al, AAAI 2019 ) could have been adapted and compared against in the paper to see how useful are the policy networks.   \n- Missing some references[a,b]. [a] uses a deep U-net network to produce adversarial attacks that are black box-transferable to unseen models. It bears similarity to the proposed network architecture in which the goal is to produce differences rather than predict the perturbation directly. The work in [b] formulates the problem of attacking black-box models as the perturbation to the victim's environment and tries to learn actions by the adversary that minimizes the victim model's reward.      \n\n\n\n[a] Nasser at. al , \"Cross-Domain Transferability of Adversarial Perturbations\", ( NeurIPS 2019 )  \n[b] Hamdi et. al, \"SADA: Semantic Adversarial Diagnostic Attacks for Autonomous Applications\" (AAAI 2020)\n\n\n\nMinor issues :\nThe tables could have been illustrated as plots for easier following and comparisons \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JRIYqHEf43P", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new black-box attack method in the hard-label setting. By using a well-designed policy network in a novel reinforcement learning formulation, the new method learns promising search directions of the adversarial examples and showed that query complexity is significantly reduced in experiments.\n\nA couple questions I have:\n\nHow are \\beta_1 and \\beta_2 chosen?\n\nIs there any convergence analysis? How do we guarantee the proposed attacking method will converge?\n\nThe proposed method is introduced as an attack that minimize L_2 distance.  Is it possible to extend this attacking method to L_inf?\n\nI am curious, have you tried evaluate the attacking methods on DenseNet as the victim model?\n\nOverall, I think this paper is very readable and is clearly written with a very good background and context. I found the idea of the paper original and interesting. And the authors have conducted experiments that show their new method has the best query efficiency, which is reasonable and aligns with their idea. For cons, this paper does not have a convergence analysis. And if the experiments could be conducted on more data sets and more victim models, then it would be more convincing. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5JS_UEcm2f", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis 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.\n\nStrengths:\n1. This paper is the first to incorporate reinforcement learning into black-box attacking. The proposed reinforcement learning formulation and the architecture of policy network are interesting and novel.\n2. A significant amount of experiments are done to show the effectiveness and efficiency of the proposed policy-driven attack compared with baselines. Moreover, the ablation experiment in the main paper and appendix provide useful insights of how every component of PDA works.\n3. The paper is in general well-written and easy to follow. Implementation details are clearly described. \n\n\nWeakness:\n1. My main concern is that there is a mismatch between the claim and the experiment. In the experiments, the paper mainly shows the results with pre-trained policy networks. However, the pertaining dataset S requires a lot of queries to the victim, which is conflictive with the purpose to reduce the number of queries. Although the authors mention that they consider the case where a large number of adversarial examples are required so that the pre-training samples can be omitted, the experiment setting does not match this assumption (500 queries * 5000 images in the pretraining dataset, versus 25 queries * 1000 images in the testing dataset which is used to evaluate the performance). It is not clear whether the performance of PDA is still the best when the number of adversarial examples keeps increasing, as it is a deep RL network, not guaranteed to be stable. ———— The authors may consider the following ways to make the experiment more convincing: (1) using much more images in the testing phase than in the pertaining phase; (2) sampling the pre-training dataset from another classifier on the same dataset, rather than from the real victim (in this way the queries to the victim can be really saved); (3) incorporating both the pre-training dataset and the testing dataset in the final performance evaluation. \n2. As also pointed out by the authors, reinforcement learning is itself sample-consuming. Applying RL to a complicated task could be difficult and non-stable. This paper proposes a few methods to facilitate learning, e.g.,  domain knowledge, pre-training, which are nice. But according to table 5, without pre-training, PDA performs similarly to HopSkipJumpAttack (even worse when internal classifier h is used), while the latter is easier to implement. This is a little concerning, suggesting the necessarily of pre-training for PDA if one wants to benefit from using PDA. I might be wrong, but if this is the case, it will be better for the authors to emphasize the importance of pre-training, and show the reasonability of using pre-training samples as stated in point 1 above.\n\nMinor comments:\n- Although the authors formulate the attacking process as a decision making problem and use a policy network to generate actions / search directions, I do not see the necessity of using RL techniques. The main reason is, there is no “horizon”, as the agent does not consider future rewards. (I am not sure whether the authors consider the future rewards in the implementation, but the description seems to only consider the current state.) Thus it might be enough to formalize this problem as a contextual bandit. This point does not influence my rating though.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an RL-based approach for decision-based attack. All the reviewers like the paper after the rebuttal phase, and we would like to encourage the authors to incorporate the new experiments in the camera-ready version. Furthermore, some recent decision-based attacks should also be included in the comparisons, such as

Li et al., QEBA: Query-Efficient Boundary-Based Blackbox Attack. (CVPR 2020) 

Cheng et al., Sign-OPT: A Query-Efficient Hard-label Adversarial Attack. (ICLR 2020)
Decision: Accept (Poster)