CorrAttack: Black-box Adversarial Attack with Structured Search
Authors: Zhichao Huang
Yaowei Huang
Tong Zhang
Venue:  (2021)
Keywords: adversarial examples
black-box attack
bandits

Abstract: We present a new method for score-based adversarial attack, where the attacker queries the loss-oracle of the target model.
Our method employs a parameterized search space with a structure that captures the relationship of the gradient of the loss function. We show that searching over the structured space can be approximated by a time-varying contextual bandits problem, where the attacker takes feature of the associated arm to make modifications of the input, and receives an immediate reward as the reduction of the loss function. The time-varying contextual bandits problem can then be solved by a Bayesian optimization procedure, which can take advantage of the features of the structured action space. The experiments on ImageNet and the Google Cloud Vision API demonstrate that the proposed method achieves the state of the art success rates and query efficiencies for both undefended and defended models.

Under review as a conference paper at ICLR 2021
CORRATTACK: BLACK-BOX ADVERSARIAL ATTACK WITH STRUCTURED SEARCH
Anonymous authors Paper under double-bling review
ABSTRACT
We present a new method for score-based adversarial attack, where the attacker queries the loss-oracle of the target model. Our method employs a parameterized search space with structure that captures the relationship of the gradient of the loss function. We show that searching over the structured space can be approximated by a time-varying contextual bandits problem, where the attacker takes feature of the associated reward as the reduction of the loss function. The time-varying contextual bandits problem can then be solved by Bayesian optimization procedure, which can take ad advantage of the features of the structured action space. The experiments on ImageNet and the Google Cloud Vision API demonstrate that the proposed method achieves the state of the art success rates and query efficiencies for both undefended and defended models.
to make modifications of the input, and receives an immediate
INTRODUCTION
Although deep learning has many applications, it is known that neural networks are vulnerable to adversarial examples, which are small perturbations of inputs that can fool neural networks into making wrong predictions (Szegedy et al., 2014). While adversarial noise can easily be found when the neural models are known (referred to as white-box attack) (Kurakin et al. 2016). However, real world scenarios models are often unknown, this situation is referred to as black-box atlack.
Some methods (Liu et al. 2016 Papernot et al., 2016) use the transfer-based attack, which generates adversarial examples a substitute model and transfer the adversarial noise the target model. However, the transfcrability is limited and its effectiveness relics highly on the similarity between the networks (Huang & Zhang 2020 If two networks are very different, transfer-based methods will have low success rates.
In practice, most computer vision API such the Google Cloud Vision API allow users to access the scores or probabilities of the classification results. Therefore, the attacker may query the black-box model and perform zeroth order optimization to find an adversarial example without the knowledge of the target model. Due to the availability of scores, this scenario is called -core-based attack.
There have been a line of studies on black-box attack which directly estimate the gradient direction of the underlying model, and apply (stochastic) gradient descent to the input image (Ilyas et al.) 2018 2019 Chen et 2017 Huang & Zhang 2020 Tu al. 2018 Li et al. 2019). In this paper, we take another approach and formulate score-bar score-based attack as a ime-varyiig contextual bandits problem. At each state, the attacker may change the adversarial perturbation and get the reward as the reduction of the loss. And the attacker would receive some features about the arms before making the decision. By limiting the action space to image blocks, the associated bandits problem exhibits local correlation structures and the slow varying property suitable for learning. Therefore, may use the location and other features of the blocks to estimate the reward for the future selection of the actions.
Using the above insights, we propose new method called CorrAttack, which utilizes the local correlation structure and the slow varying property of the underlying bandits problem. CorrAttack uses Bayesian optimization with Gaussian process regression (Rasmussen) 2003) model the correlation and select optimal actions. A forgetting strategy is added to the algorithm so that the Gaussian process regression handle the time-varying changes. CorrAttack effectively find

---

Under review as a conference paper at ICLR 2021
blocks with the largest rewards. The resulting method achieves much lower numbers of average queries and higher success rates than prior methods with a similar action space (Moon et al. 2019).
It is worth noting that BayesOpt (Ru et al., 2020) and Bayes-Attack (Shukla et al. 2019) also employ Bayesian optimization for score-based attack. However, their Gaussian process regression directly models the loss function of the image, whose dimension can be more than one thousand. Therefore, their speed is slow especially for BayesOpt, which uses slow additive kernel. CorrAttack, on the other hand, searches over much limited action space and models the reward as a function of the low dimensional feature. Therefore, the optimization of CorrAttack is more efficient, and the method is significantly faster than BayesOpt.
We summarize the contributions of this work as follows:
1. We formulate the score-based adversarial attack as a time-varying contextual bandits, and show that the reward function has slow varying properties. In new formulation, the attacker could take advantage of the features to model the reward of the arms with learning techniques. Compared to the traditional approach, the of learning in the proposed framework greatly improves the efficiency of searching over optimal actions.
2. We propose a new method, CorrAttack, which uses Bayesian optimization with Gaussian process regression to learn the reward of each action, by using the feature of the arms.
3. The experiments show that CorrAttack achieves the state of the art performance on ImageNet and Google Cloud Vision API for both defended and undefended models.
2 RELATED WORK
There have been a line of works focusing on black-box adversarial attack. Here, we give a brief review of various existing methods.
Baanser-BBased Attack Transfer-based attack assumes the transferability of adversarial examples across different neural networks. It starts with a substitute model that is in the same domain as the target model. The adversaries can be easily generated on the white-box substitute model, and be transferred to attack the target model (Papernot et al. 2016). The approach, however, depends highly on the similarity of the networks. If two networks are distinct, the success rate of transferred attack would rapidly decrease (Huang & Zhang 2020). Besides, we may not access the data for training the substitute model in practice.
Score-based Attack Many approaches estimate the gradient with the output scores of the target network. However, the high dimensionality of input images makes naive coordinate- wiiee search impossible as it requires millions of queries. ZOO (Chen et al.) [017]] an early work of gradient estimation, which estimates the gradient of an image block and perform block-wise gradient descent. NES (Wierstra et al. 2008) and CMA-ES (Hansen 2016) are two evolution strategies that can perform query efficient score- based attack Myas et al. (2018); Meunier et al. (2019). Instead of the gradient itself, SignHunter (Al-Dujaili & O Reilly 2020a) just estimates the sign of gradient to reduce the complexity. AutoZOOM (Tu al. 2018 uses bilinear transformation
autoencoder reduce the sampling space and accelerate the optimization process. the same spirit, data prior can be used improve query efficiency (Ilyas et al., 2019). Besides, MetaAttack (Du al. (220)) takes meta learning approach to learn gradient patterns from prior information, which reduces queries for attacking targeted model.
Many zeroth order optimization methods for black-box attacks rely on gradient estimation. However, there are some research works using gradient free methods to perform black-box attack. BayesOpt and Bayes-Attack (Ru et al., 2020; /Shukla et al., 2019) employ Bayesian optimization to find the adversarial examples. They use Gaussian process regression on the embedding and apply bilinear transformation to resize the embedding to the size of image. Although the bilinear transformation could alleviate the high dimensionality of images, the dimension of their embeddings are still in the thousands, which makes Bayesian optimization very ineffective and computationally expensive. different method, PARSI. poses the attack on Eoo norm as a discrete optimization problem over {-r,e)" (Moon et al. 2019 It uses Lazy-Greedy algorithm to search over the space {- to find an adversarial example. SimBA (Guo et al. 2018) also employs a discrete search space targeted lg norm.
2

---

Under review as a conference paper at ICLR 2021
Decision-based Attack Decision- based attack assumes the attacker could only get the output label of the model. Boundary Attack and its variants (Brendel et al. 2017 Chen et al. 2020: Li et al.) 2020) designed for the setting. However, the information received by the attacker much smaller than score-hased attack, and it would take many more queries than score-based attack to successfully attack image.
3 PRELIMINARIES
A Gaussian process Rassusssen 2003) is prior distribution defined on some bounded set Z, and determined by a mean function μ : 2 - and a covariance kernel & : 2 RR. Given n observations D, = {(2), f(+)) | 1==1 the prior distribution on
o f(11n) is
f(z1n) Normal
Ko (2(2i: 21:n)),
(1)
where we use compact notation for functions applied to collections of input points: 2im indi- cates the sequence 21,- . Zn. (Z1m) [f(z)..... f(zn),, po(zim) [uo(z1)," "0 (zx)l. ko(21mm Z1 = [x0(21,
Ko(Z1, =n); -....... (o 21), ko(Zn, an)i].
Now wish to infer the value of (() some new point z, the posterior process [z)) is also Gaussian process (GP) with mean pn and covariance o:
[2) (ormal((),()),
[nn (n) Ko(z, 2i:a )00 (21:: =1:a) (J(1mm)) (
po (=((1)))) 1 (2),
(2) ko(z, 2) ko 21m )mo (3:m 21m) ( (o((2mm))) (2)
As optimization method to maximize function f. Bayesian optimization models the function to make decisions about where to evaluate the next point 2. Assuming we already obtained observations Di-1 ((2 f+))) determine the next point 2; for evaluation, we first the posterior GP
to define an acquisition function yp: Z + IR, which models the utility of evaluating f(z) for any Z. We then evaluate fzz) with
24 arg max (z().
In this work, use the expected improvement (EI) acquisition function Mockus et al. 1978)
7(2) (n( - ((bestt
px(2) ( +
with
(4)
Va((z)
which measures the expected improvement over the current best value 2beat = arg max s,
f(+
according the posterior GP. Here ((-) and Φ(-) are the edf and pdf of /V respectively.
4 SCORE-BASER BLACK-BOX ATTACK
Suppose classifier F(z) has input z and label An un un-targeted adversarial example Tade satisfies:
arg max F(F F(Fadv) + y and jE(1,--C)
|Radv - x 11p E,
(5)
where C' is the number of classes. While an adversarial example for targeted attack means the maximum position of Fzz) should be the targeted class arg max.e(1,...c) F(Zadv)j = q. In order to find Kadv. we may optimize a surrogate loss function f(x, y) (e.g hinge loss).
In this work, we consider adversarial attack as a time-varying contextual bandits problem. At each time I, we observe a state Ha which is a modification of the original input xn- Before taking arm a, E c. Rdd we could observe the feature of arms. And a would modify state Ie to I++1 according to
T1+1 = arg min E(TI (T..e) (s).y)
(6)
sE sE(z+ta.=))
with reward function r(z,, ax) ((x++1.)) E(x,, y) and the checking step tries to remove negative reward. this frame, we would like estimate the reward r(x,, 0z) with feature 2, using learning. and then pick or to maximize the reward. Observe that
r(Ze, (t) Val(Fe.)) (#e41 x2),
3

---

Under review as a conference paper at ICLR 2021
where the gradient V., ( y) is unknown. It follows from the formulation that may rewrite r(z,, 0z) as a function
((I),0g) Re faz, 2+++1 xx)-
Since in general, we make small steps from one iteration to the next iteration, 6((a,) = 2141 Iy is small. We may approximate the reward with fixed gradient locally with
f(zz, 5τ) = f((a)),
We may consider the learning of reward time-varying contextual bandits problem with reward function fi(as) for arm de at time Since 2++1 2; is small, this time-varying bandits has slow- varying property: the function ft changes slowly from time / to time f 4+11. 1.
In the proposed framework, our goal is to learn the time-varying bandits reward fa)) with feature 2t. We use Gaussian process regression to model the reward function using recent historic data since the reward function slow-varying, and describe the details in the subsequent sections.
We note that the most general action space contains all a E IRd, where d is the number of image pixels. However, is impossible to explore the arms in such large space. In this work, we choose specific class of actions A = {== n2 is the image blocks of different sizes. It covers the space of the adversarial perturbations while maintaining good complexity. We also find the location and the PCA of the blocks good component of the feature 2 associated with the arm. Besides, modifying block only affects the state locally. Therefore the reward function remains similar after state changes.
4.1 STRUCTURED SEARCH WITH GAUSSIAN PROCESS REGRESSION AND BAYESIAN OPTIMIZATION
Define the block size as we divide the image into several blocks E = {E000s E001; Chwe where the block is 5 b square of pixels and (h, w. c) (height/b b, width/ /b, channel). Each block Eijk is associated with the feature Zeyy such as the location of the block.
Suppose we have time-varying bandits with state and unknown reward function ft at time L. By taking the action Geaz we change the individual block eijk of 24 and get 2++1 with reward (a We consider two ways of taking action de,s on block Eijk CorrAttackpirt and CorrAttackFipp
Finite Difference CorrA :tackpu:::: For action Gegge the attacker will query ((x, + netyks v) and l(x, n/igk: y), and choose
Geigh
arg min seluesee.-eepp
((x+ + 8,
The action space A [deigu leas E F.).
In our framework, the bandits problem also be regarded learning the conditional gradient over actions. That is, when is small, we try to choose action de with
Oj arg min eTjx V (
E
which is the conditional gradient over the set of blocks.
Discrete Approximation CorrAttackynp: In general, adversarial attack with lx budget can be formulated as constrained optimization with ||= x||00 < e. However, PARSI (Moon et al. 2019) limits the space to {-c, +e}", which leads to better performance for black-box attack (Moon et al. 2019). The continuous optimization problem becomes a discrete optimization problems follows:
maximize ((zadv;)) v)
maximize ((Fadvy
(10)
subject ||Tado x01.00 Se
subject to Tade {e, -e]d.
Following PARSI, consider two stages to perform structured search. When flipping to -E, Gesy. changes the block to - and A {-2eesuleesk E E). When changing - to e, A = (2ee:ja Eijk E} instead.
Gaussian Process (GP) Regression: We model the difference function
ge(a;) E(IT (x,ss) (xe az),,) v) {(x,,)) v)
(11)
4

---

Under review as a conference paper at ICLR 2021
instead of the reward function f((())) 2 0, as the difference function could be negative, providing more information about the negative arms in A. We would collect historic actions with feature and (ax) )) and learn the difference to make choices at later stage. At each time t, we use the Gaussian process regression to model the correlation between the features Zegg and use Bayesian optimization select the next action. More specifically, the same eq. (2). we let
difference (
gr (Begs [D; Normal( (Fesga) o (Fegg)))
(12)
where D, [ gl (ax))))) H- the difference of evaluated blocks ct-rit with feature Zet-r:t and T is parameter to forget old samples. Then we use EI acquisition function to pick up the next action a+41 in A. More specifically, the same eq. 44). let
0++1 arg max (oaxxVa((eee))) (f( (( ((((E)))))))))) + ((7 ((7((2:3))))
(13)
As the difference function is varying, we take two strategies in Algorithm 2 to update the previous samples to make sure GP regression learns the current difference function well. The first strategy is to remove old samples in Dr, Even if the bandits are slowly varying, the difference function will change significantly after a significant number of rounds. Therefore, we need to forget samples before t т. The second strategy is remove samples near the last block Ct,jk, in Dr. As we discuss later, the difference function may change significantly in a local region near the last selected block. Therefore previous samples in this local region will be inaccurate. The resulting algorithm for CorrAttack is which mainly follows standard procedure of Bayesian optimization.
shown in Algorithm !
Algorithm 1 CorrAttack
Require: Loss function (,,,),, Input To and its label y. Action space {Geiy (4yj E E}, Parameter c,
a
1: Build set Do = ((Reeysy go (ae yo t
1) }1 using latin hypercube sampling from A
repeat
3: Fit the parameter of Normal (pr (Zeage e of (Zeige)) on D, according to Equation
12
4: Calculate acquisition function (e((Zeije) and according Equation 13
5: Select dei = max (e (P((ge)))) according to Equation
13
Je+1 = arg min (me-tae ,zx) E(TT (8).
7: Update sample set D, with Algorithm? 2
De+1 = UPDATESAMPLES((D Te, Tt+1, Cteceh Dt+1 (Reipshh, ),
8: until max (Feign) <
9: return ZT;
Algorithm 2 Update Samples
Require: Sample set D., State 2141, Block Basicke Difference gi+1 (deiesikk
Paramter
I: if 1e+1 # Iı then
2: Di+1 = D. (( E Dilli [ili- del + lj jel S a}
3: else
D.+1
U {Zeenssk gt+1 (Res.so (iniess...))))) }}}
6: Remove the earliest sample from if the cardinality [D] >
7: return Dr+1
4.2 FEATURES AND SLOW VARYING PROPERTY
Features of Contextual Bandits: We four dimensional vector the feature Zerya'
Zeszu (i. J. k. pea)
(14)
where i, j, k is the location of the block. And pca is the first component of PCA decomposition of (Co0)) Po (Cow1), ... Zo (Chwe)). (e((ejk)) means the block of natural image the given position.
The reward function depends on the gradient in Equation 7 It has been shown that the gradient VzE(x, y) has local dependencies (Ilyas al. 2211)). Suppose two coordinates Eijk and Glpy are close, then VaL(a, 1)ig & Vzl(x, 4)1pg We consider the finite difference of the block eija
A((eig) = (xt neigh. v) l (x+ neigk: y) 2ne Vz, (x+, v)
(15)
5

---

Under review as a conference paper at ICLR 2021
where 1) is small step size. When is small, the reward can be approximated by the average of the gradients around a small region, which also has local dependencies. In fact, the local structure of the reward will also be persevered when the block size and is large. Figure shows the finite difference (eijk) obtained on ImageNet dataset with ResNet50. This shows blocks with closer locations more likely to have similar reward. Therefore, add the location of the block as the feature so that it uses historic data to find the arm with the largest reward.
example of
Figure I: Finite difference of the perturbation for three channels on one image from ImageNet with ResNet50. h = 28, b = 8 and r 0.05. Lighter block means larger finite difference.
In addition the location of the difference, may add other features. The block of the image itself forms a strong feature for the regression, but the dimension of the block is too high for GP regression. Therefore,
PCA lower the dimension and add the first component into the feature vector.
Slow Varying Property In addition to the local dependencies of finite difference, the difference would also be slow varying if we just change small region of r4. Let It+1 2t jj Figure _ shows the difference of A (eiga) and A++1 (eijk), which is centralized in small region near ji,j, Reward function based the finite difference, which also has the slow varying property. could be explained by the local property of convolution. When is small, the finite difference can be approximated with gradient and the local Hessian:
(ejzk Ax(eij)) = e V2 (( B)
(16)
The difference is much smaller than Ae(eigR). Today's neural networks are built with stacks of convolutions and non-linear operations. Since these operations are localized in a small region, the Hcssian of a neural network also localized and the reward function only changes near Gi.jkke
Difference of finite difference on each block after changing block 615,18,1 of Figure 1, which is the lightest pixel in the picture. Darker blocks imply smaller difference in finite difference, which is almost zero in the majority of the image except the part near the changed block.
Figure 2:
4.3 HIERARCHICAL BAYESIAN OPTIMIZATION SEARCH
Recent black-boo approaches (Chen et al. 2017 Moon et al, 2019) exploit the hicrarchical image structure for query efficiency. Following these approaches, we take hierarchical approach and perform the accelerated local search Algorithm from a coarse grid (large blocks) to fine grid (smaller blocks). The algorithm for hierarchical attack iteratively performs Algorithm [ at one block size, and then divides the blocks into smaller sizes. At each block size, we build Gaussian process model the difference function, and perform structured search with the blocks until max (pa( (Z < When dividing the blocks into smaller sizes, we will build new block E with action Geyy and new feature Ze,zz but keep the 2; in last block size as To in new block size. Define the stage as = {0, 1, 1.... s} and initial block size as b. The block at stage s is 2 x 2" square of pixels and (h, w, (2 height/b. bb, 2" width channel).
The overall hierarchical accelerated local search algorithm is shown in Appendix A is important to note that most of the attacks terminate in the early stages and rarely need on fine scales.

---

Under review as a conference paper at ICLR 2021
Table 1: Success rate and average queries of un-targeted attack 1000 samples of ImageNet.
E = 0.05. Since BayesOpt and Bayes-Attack needs thousands of hours to run all samples, we only
test 20 samples, which marked as *, the complexity and running time could be referred to C.6
VGG16
Resnet50
Densenet121
Attack
Success
Queries
Success
Queries
Success
Queries
ZOO
81.93%
2003
63.68%
1795
76.73%
1864
NES
99.72%
700
99.19%
1178
99.72%
1074
NAttack
100% %
293
99.73%
401
100% %
375
Bandits
94.75%
389
96.92%
433
98.09%
635
PARSI
100%
365
99.73%
432
100%
387
Square Attack
100%
79
100 %
112
100 %
86
SignHunter
100%
104
100 %
145
100 %
118
CorrAttackpint
100%
389
99.86%
419
99.86%
334
CorrAttackFiip
100%
130
100 %
150
100% %
113
BayesOpt* 100%
182
100 %
214
100%
223
Bayes-Attack= 100%
244
100 %
254
100 %
213
CorrAttackpip" 100%
110
100%
96
100%
87
Table 2: Success rate and average queries of targeted attack ImageNet. = 0.05 and query limit is 10000. As BayesOpt and Bayes-Attact rum very slow, we do not include them for the targeted attack.
VGGI6
Resnet50
Densenet121
Attack
Success
Queries
Success
Queries
Success
Queries
ZOO NES
1.1%
2884
0.8%
3018
1.1%
3309
80.82%
4582
52.73%
5762
64.21%
5427
NAttack
91.86%
4045
89.05%
3799
91.97%
4389
Bandits
50.62%
5379
40.18%
5672
43.53%
5434
PARSI
76.28%
3229
64.88%
3403
75.09%
3246
Square Attack
96.69%
2060
89.52%
2807
95.38%
2280
SignHunter
93.52%
2999
83.71%
3905
90.75%
3632
At
88.41%
3826
81.84%
4064
91.29%
3513
Attrkktackiip 98.07%
2191
96.39%
2531
99.41%
2019
5
EXPERIMENTS
We evaluated the number of queries versus the success rates of CorrAttack on both undefended and defended network ImageNet (Russakovsky et al. 2015). Moreover, attacked Google Cloud Vision API to show that CorrAttack can generalize to true black-box model.
We used the common hinge loss proposed in the CW attack (Carlini & Wagner 2017). We compared two versions of CorrAttack Attrcktaakppar and CorrAttack to 700 (Chen et al. 2017). NES
(Ilyas al. 2018), NAttack (Li et al. 2019). Bandits (Ilyas et al.) (209)), PARSI (Moon et al. 2019). Square Attack (Anrriuhchhenko et al. 2020),
MaruutterAl--ujaaaa & O' O'Reilly 2020b). BayesOpt 2019). We only adversarial attack on foo norm. The details of the Gaussian processes regression and the hyperparameters of CorrAttack are given in the Appendix B We shall mention that CorrAttack is not sensitive the hyperparameters. The
(Ru et al., 2020) and Bayes-Attack (Shukla
hyperparameters of other methods follow those suggested by the original papers.
5.1 UNDEFENDED NETWORK
We randomly select 1000 images from the validation set of ImageNet and only attack correctly classified images. The query efficiency of CorrAttack is tested on VGG16 (Simonyan Zisserman 2014). Resnet50 (He et al. 2016) and Densenet 121 (Huang et al. 2017). which are the most commonly used network structures. We set E = 0.05 and the query limit to be 10000 except for BayesOpt and Bayes-Attack. For targeted attacks,
randomly choose the target class for each image and the target classes are maintained the same for the evaluation of different algorithms. The results are shown in
Table and 2 CorrAttackrip outperforms other methods by a large margin.
7

---

Under review as a conference paper at ICLR 2021
Table 3: Success rate and average queries of un-targeted attack on defended model. Since BayesOpt and Bayes-Attack Attack take thousands of hours to run, we only tested on 10 samples from ImageNet with e 0.05 and 1000 query limit, which are marked
Method
700
NES
NAttakk
Bandits
PARSI
Success
28.57%
24.13%
74.38%
55.82%
73,40%
Queries
1954
3740
1078
1873
1529
Method
SignHunter
Square Attack
CorrAttackpir
CorrAltackrin
Success
68.97%
73.89%
64. 86%
79.15%
Queries
1392
1086
1599
1036
Method
BayesAttack
BayesOpt*
CorrAttackrigg" *
Success
50.00%
50.00%
60.00%
Queries
129
406
206
Table 4: Success rate and average queries of un un-targeted attack on Google Cloud Vision API. 0.05
Method
NAttack
BayesOpt
PARSI
CorrAttackruip
Success 70.00%
30.00%
70.00%
80.00%
Queries 142
129
235
155
As BayesOpt and Bayes-Attack takes tens of thousands of hours attack 1000 images, we compare them with CorrAttackrup only on 20 images and un in-targeted attack. The query limit is also reduced to 1000 the time for BayesOpt and Bayes-Attack quickly increases as more samples add into the Gaussian distribution. The time comparison between three models is shown in Appendix C.6
Optimality of Bayesian optimization Appendix C.1 shows the rank the actions found by CorrAttack. The attacker could find the action with large reward quickly.
Varying & We also test the algorithms different budget of adversarial perturbations and & = 0.06 on Resnet50. As it is shown in Appendix C.2 CorrAttack shows a consistently better performance different
0.04
Ablation study on random choices Appendix C.3 shows the ablation study of random version of ConrAttacpiif and CorrAttackFipp In both cases, Bayesian optimization helps to gain better query efficiency.
Ablation study on hierarchical attack We perform ablation study on the hierarchical attack and the result is shown in Appendix [C.4] Hierarchical structure accelerates the CorrAttack and eliminates the sensitivity of choosing initial block size.
Ablation study on features Appendix C.5 demonstrates how the feature of the contextual bandits affects the performance of attack. PCA would help to improve the efficiency of attack.
5.2 DEFENDED NETWORK
To evaluate the effectiveness of CorrAttack on adversarially defended networks, we tested our method on one of the SOTA robust model (Xie et al., (2188) on ImageNet. The weight downloaded from Githut|] "ResneXt DenoiseAll" is chosen as the target model as it achieves the best performance. We set 0.05 and the maximum number of queries is 10000. As BayesOpt runs very slowly, the attack is also performed on 10 images and the query limit is 1000. The result is shown in Table 3 AttrAttackpip still outperforms other methods.
5.3 GOOGLE CLOUD VISION API
We also attacked Google Cloud Vision API, real world black-box model for classification. The target is to remove the top-1 label out of the classification output. We choose 10 images for the ImageNet dataset and set the query limit to be 500 due to high cost to use the API. We compare AttrAttackıip with NAttack, BayesOpt and PARSI. The result is shown in Table We also show one example of the classification output in Appendix C.9
8

---

Under review as a conference paper at ICLR 2021
6 CONCLUSION AND FUTURE WORK
We formulate the score-based adversarial attack as a time-varying contextual bandits and propose new method CorrAttack. By performing structured search on the blocks of the image, the bandits has the slow varying property. CorrAttack takes advantage of the the features of the arm, and uses Bayesian optimization with Gaussian process regression to learn the reward function. The experiment shows that CorrAttack can quickly find the action with large reward and AttrAttack achieves superior query efficiency and success rate on ImageNet and Google Cloud Vision API.
We only include basic features for learning the bandits. Other features like embedding from the transfer-based attack Huang & Zhang 2020) may be taken into account in the future work. While our work only focuses on adversarial attack &o norm, the same contextual bandits formulation could be generalized to other lp norm to improve query efficiency. Besides, defense against CorrAttack may be achieved with adversarial training CorrAttack, but it may not be able defend other attacks in the meantime.
REFERENCES
Abdullah AL- Al-Dujaili and Una-May O'Reilly. Sign bits are all you need for black-box attacks. In International Conference on Learning Representations, 2020a. URL /tttpps://ppeeeeieerr
Abdullah Al-Dujaili and Una-May O' D'Reilly. Sign bits are all you need for black-hox attacks. In International Conference Learning Representations, 2020b. URL htttttts////peereerr
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficient black-box adversarial attack via random search. 2020.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv: 2017.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017
IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE, 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), pp. 1277-1294. IEEE, 2020.
Pin-Yu, Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order optimization based black-box attacks deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15 26. ACM, 2017.
Kun Dong, David Eriksson, Hannes Nickisch, David Bindel, and Andrew G Wilson. Scalable log determinants for gaussian process kernel learning. In Advances Neural Information Processing Systems, pp. 6327-6337, 2017.
Jiawei Du, Hu Zhang, Joey Tianyi Zhou, Yi Yang, and Jiashi Feng. Query-efficient meta attack to deep neural networks. In International Conference Learning Representations, 2020. URL
httts::/cpenzxviiee net/ hhett//ooommiddStxde.e....
Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson. Gpytorch: Blackbox matrix-matrix gaussian process inference with gpu acceleration. In Advances Neural Information Processing Systems, pp. 7576-7586, 2018.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using input transformations. In International Conference Learning Representations, 2018. httptppps//ppenreveeeeeetteee//e
Nikolaus Hansen. The ema evolution strategy: A tutorial, arXiv preprint arXiv:1604.00777. 2016.

---

Under review as a conference paper at ICLR 2021
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-470000 2017.
Zhichao Huang and Tong Zhang. Black-box adversarial attack with transferable model-based embedding. In International Conference on Learning Representations, 2020. URL https //openreview wwt. wttee//formmmi=SxxxtTTTT
Andrew Ilass Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Jennifer Dy and Andreas Krause (eds.), Proceedings the the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2137-2146, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Andrew Ilyas, Logan Engstrom, and Aleksander Madry, Prior convictions: Black-box adversarial attacks with bandits and priors. In International Conference on Learning Representations, 2019. URL heattps://ppeereeeee
net foremm/ ii=
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint arXiv: 1.01236, 2016.
Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query- boundary- based blackbox attack. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1221-1230. 2020.
Yandong Li, Lijun Li, Liqiang Wang, Tong Zhang, and Boqing Gong, Nattack: Learning the distributions of adversarial examples for an improved black-box attack on deep neural networks. arXiv preprint arXiv: arXiiv1905.000 1et.. 2019.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples and black-box attacks. arXiv preprint arXiv: 161:: 1.02770, 2016.
Laurent Meunier, Jamal Atif, and Olivier Teytaud. Yet another but more efficient black-box adversarial attack: tiling and evolution strategies. arXiv preprint 1910:02900.02244: 2019.
Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The application of bayesian methods for seeking the extremum. Towards global optimization, 2(117-129):2, 1978.
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black- box adversarial attacks via efficient combinatorial optimization. arXiv preprint arXiv:1905.066 2019.
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint arXiv: urXiv:1605.000 1605.07277 2016.
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School Machine Learning, pp. 63-71. Springer, 2003.
Binxin Ru, Adam Cobb, Arno Blaas, and Yarin Gal. Bayesopt adversarial attack. In International Conference on Learning Representations, 2020. URL
id Hld=kkem-- IrtvH
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-255) 2015.
Satya Narayan Shukla, Anit Kumar Sahu, Devin Willmott, and J Zico Kolter. Black-box adversarial attacks with bayesian optimization. arXiv preprint arXiv:1909.13857 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
10

---

Under review as a conference paper at ICLR 2021
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014. |ttp:t::
org/ ab////as//11...//.///aa//aaaaaaa 6199
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. arXiv preprint arXiv: 2018.
Daan Wierstra, Tom Schaul, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. 2008 IEEE Congress Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 3381-3387, 2008
Cihang Xie, Yuxin Wu, Laurens van der Maaten, Alan Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. arXiv preprint arXiv: 2018.

---

Under review as a conference paper at ICLR 2021
A ALGORITHM
Algorithm 3
Split Block
Require: Set of blocks E, Block size b, E"
for each black E
2: Split the block e into 4 blacks ca, c4) with size b/2
3: E' t E" U {er, e2, 6a
4: end for
return E":
Algorithm Hierarchical CorrAttackpar
Require: Loss function ((:,-), Input image and its label Initial Block size b, Set of blocks E containing all blocks of the image, Threshold G, 7, a, Step size 7, Adversarial budget
1: æo æ
2: repeat
3: Choose A = (argg Gijk E bb} with Equation 8
4:
Run ComrAttack current block size
CORRATTACK (E(:, -), 2r y, A, C, a)
5:
i > 1 then
6:
Split the blocks into finer blocks using Algorithm E SPL.IBLLOCK
7:
b/2
end if
9: until converges
10:
return
Algorithm 5 Hierarchical CorrAttackrip
Require: Loss function E(., Input image z and its label y, Block size b, Set of blocks E containing all blocks of the image, Threshold e, 7, o, Adversarial budget
1: иe x
2: for esyl E E do
3:
Randomly draw from [-8,e] zu(e
4: To Iole:ya]
end for
repeat
7:
An [2Eexsk E EE (2x x) < <0)
8:
Run CorrAttack flipping to
ft CORRATTACK (f(,,),, Ik, V, Au, T,
9:
Ap (-2ee Ele (ix x) > 0}
10:
Run CorrAttack flipping to -
JR-1 CORRATTACK (,(,,)), V, Ag, C, a.
b then
12:
Split the blocks into finer blocks using Algorithm
E' SPLITBLOCK(E)
13:
6 1+-b) b/2
14:
end if until converges
15:
16:
return zK:
B DETAILS OF EXPERIMENT SETTING
We the hinge loss for all the experiments. For un-targeted attacks,
Lumtarged (x, y) max [((x), - max F(z)5, -w
(17)
jzy
and for targeted attacks,
Farger (x, y) max max F(x), F F(x) -w
(18)
12

---

Under review as a conference paper at ICLR 2021
Here F represents the logits of the network outputs, is the target class, and denotes the margin. The image will be projected into the E-ball. Besides, the value the image will be clipped to range [0, 1|.
B. GAUSSIAN PROCESS REGRESSION AND BYAESIAN OPTIMIZATION
We further provide details on both the computational scaling and modeling setup for the GP regression.
To address computational issues, we use GPyTorch (Gardner ct al. 2018) for scalable GP regression. GPyTorch follows (Dong et al. 2017) to solve linear systems using the conjugate gradient (CG) method and approximates the log- deg-deterninant via the Lanczos process. Without GPyTorch, running BO with GP regression for more than few thousand evaluations would be infeasible classical approaches to GP regression scale cubically in the number of data points.
On the modeling side, the GP is parameterized using Matérn-5/2 kernel with ARD and constant mean function for all experiments. The GP hyperparameters are fitted before proposing a new batch by optimizing the log- marginal likelihood. The domain is rescaled [0, 1] and the function values are standardized before fitting the GP regression. We use a Matérn-5/ 2 kernel with ARD for CorrAttack and use the following bounds for the hyperparameters: (length scale) X E [0.005, 2.0). (output scale) X E [0.05, 20.0], (noise variance) o² E [0.0005, 0.1].
B.2 HYPERPARAMETERS
For CorrAttack in Algorithm 4 and Algorithm we set the initial block size b to be 32 and the step size n for AttrAutackiir 0.03. In Algorithm I we use the initial sampling ratio m = 0.03n at the start point for Gaussian process regression, the threshold = 10 to decide when to stop the search of current block size. Algorithm 2 the threshold different for different block size. For CotrAttackFijp
1, 2, 2,3 for block size 32, 16, 8, 4, 2 and for CorrAttackiar, for block size 32, 16, 8, 4, We set r = 3m = 0.09v to remove the earliest samples from D once |D| > The Adam optimizer is used to optimize the mean μ and covariance k of Gaussian process, where the iteration is and the learning rate is 0.1.
0, 0, 1, 1,
For PARSI, the block size is set to 32 as CorrAttack, other hyperparameters are the same as the original paper.
For Bandits, Bayes-Attack and BayesOpt, the hyperparameters are the same the original paper.
We optimize the hyperparameters for ZOO, NES. For un-targeted attack on NES, we set the sample size be 50, learning rate to be 0. For targeted attack on NES, the sample size is also 50 and the learning rate 0.05. The learning is decay by 50% if the loss doesn't 't decrease for 20 iterations.
For NAttack, set the hyperparameters the same NES and add momentum and learning rate decay, which are not mentioned in the original paper.
For ZOO, set the learning rate to 1.0 and sample size to be 50. Other setting follows the original paper.
C ADDITIONAL EXPERIMENTS
C.1 OPTIMALITY OF BAYESIAN OPTIMIZATION
Figure 3 shows the reward function that the Bayesian optimization could find in the action set. CorrAttack could find the action with high reward within just few queries. It shows that the Gaussian process regression could model the correlation of the reward function and the Bayesian optimization could use optimize the time-varying contextual bandits.
C.2
VARYING THE ADVERSARIAL BUDGET
We test CorrAttack different adversarial budget ImageNet for both un-targeted attack and targeted attack. Table and Table Table the success rate and average queries for e = 0.04, 0.05, 0.06. Corr Attrkktakk achieves the best performance among all methods.
13

---

Under review as a conference paper at ICLR 2021
Targetod
Untargeted
0.22
6.10
0.08
0.08
Mooee Blace Block
0.04
0.04
0.00
0.00
0.525 0.850 0.ors 0.100 0.125 0150 0.175 0250
0.025 0.050 0.075
0,100 0.15 0.175 0200
Querias
Queries
Figure 3: The rank of the reward function that the Bayesian optimization could find the action set for different block size. The rank and query normalized by the cardinality of the action set.
Table 5: Success rate and average queries of un-targeted attack on different E. Query limit is 10000
0.04
0.05
0.06
Attack
Success
Queries
Success
Queries
Success
Queries
ZOO
63.28%
1915
63.68%
1794
64.88%
1507
NES
99.06%
1230
99.19%
1178
99.19%
1160
NAttack
99.73%
529
99.73%
401
99.73%
369
Bandits
95.86%
898
96.92%
694
97.06%
567
PARSI
99.73%
508
99.73%
432
100%
387
CorrAttackpiff
99.86%
479
99.86%
419
99.78%
373
Attrkktackyip
100%
203
100%
150
100%
107
Table 6: Success rate and average queries targeted attack on different &. Query limit is 10000
0.04
0.05
0.06
Attack
Success
Queries
Success
Queries
Success
Queries
ZOO
0,80%
3514
0.80%
3018
0.93%
1938
NES
49.13%
5901
52.73%
5762
56.48%
5884
NAttack
78.24%
5019
89.05%
3799
90.25%
4321
Bandits
31.78%
5721
40.19%
5672
43.39%
5609
PARSI
57.00%
3599
64.88%
3403
68.75%
3250
CorrAttackpir
78.70%
4472
81.84%
4064
85.31%
3837
CorrAttackeu 93.44%
2689
96.39%
2531
97.50%
2194
C.3 ABLATION STUDY ON RANDOM CHOICES
Table 7 and Table show the ablation study on the strategy to choose action #++1 in the line 6 of Algorithm [ The process of Bayesian optimization helps accelerate the optimization. As targeted attack is more complicated and requires larger number of queries, CorrAttack has more advantage in this scenario.
C.4 ABLATION STUDY ON HIERARCHICAL ATTACK
We perform un-targeted attack Resnet50 shown in Table 1O Hierarchical attack lowers the average queries and improves the query efficiency. Besides, hierarchical attack avoids the problem of choosing block size. As shown in Table 1O block size for non-hierarchical is essential for the performance.
C.5 ABLATION STUDY ON FEATURES
Table II shows the success rate and average queries for CorrAttackwith different features. We perform ablation study the features of the contextual bandits. One contains just the location of the
14

---

Under review as a conference paper at ICLR 2021
Table 7: Ablation study random choices with success rate and average queries of un-targeted attack on ImageNet, E = 0.05 and query limit is 10000
VGG16
Resnet50
Densenet121
Attack
Success
Queries
Success
Queries
Success
Queries
CorrAttackpin Random
100 %
456
99.86%
491
100 %
375
Corr Diff Bayes
100 %
389
99.86%
419
100 %
334
CorrAttackpipp Random
100 %
143
100%
176
100 %
132
CorrAttack Bages 100 %
130
100%
150
100 %
113
Table 8: Ablation study random choices with success rate and average queries of targeted attack on ImageNet. = 0.05 and query limit is 10000
VGG16
Resnet50
Densenet12)
Attack
Success
Queries
Success
Queries
Success
Queries
CorrAttackpint Randon Random
83.72%
4388
74.76%
4644
85.30%
4113
Attakktak Bages
88.41 %
3826
81.84%
4064
91.29%
3513
CorrAttackyis Random
96.42%
2545
92.92%
3066
96.87%
2556
CorrAttackpiip Bayes
98.07%
2191
96.39%
2531
99.41
2019
Table 9: Ablation study on random choices with success rate and average queries of un-targeted attack on defended model ImageNet. 0.05 and query limit is 10000
Method Co Random CorrAttackpi CorrAttacknia Random
Corr CorrAttackrip Bayes
Success
57.47%
64.86 %
71.42%
79.15% %
Queries 1645
1599
1159
1036
Table 10: Success and average queries of un-targeted attack Resnet50 for Hierarchical
Strategy.
Method
Fixed Size 4
Fixed Size 8
Fixed Size 16
Fixed Size 32
Hierarchical
Success 100%
100.0%
99.47%
89.32%
100%
Queries
763
351
168
96
150
block and the other contains both the location and the PCA feature. PCA helps the learning process of the reward and achieve higher success rate and lower number queries. PCA feature achieves significant improvement CorrAttackrii- We may find more useful features in the future.
C.6 COMPARISON BETWEEN CORRATTACKEUN BAYESOPT AND BAYES-ATTACK
The main difference between BayesOpt and Bayes-Attack is using different types of GP regression (Standard GP for Bayes-Attack and Additive GP for BayesOpt), so we will consider these two models as group when comparing with our model CorrAttack.
Difference between CorrA Atack, BayesOpt and Bayes-Attack: For I.c attacks, assume there are no hierarchical structure, we have blocks F = (E000, (oo0,, ........... Chwe). where the block is bx b square of pixels and (h, w, c) = (height/l 6b, width/b b, channel). CorrAttack, BayesOpt (Ru et al. 2020) and Bayes-Attack (Shukla et al., 2019) all try to search the adversarial noise E with perturbation x w X c, the perturbation of block Cijk at time 6t 8'.ya.
E [-c, cd where
BayesOpt and Bayes-Attack use GP regression directly on e]e (all blocks),
f( ~ (0)
(19)
CorrAttack define action space and use standard GP regression features Zesju (single block),
(1. pea)
gt (Begs [[D, (or (Zessu)))
(20)
15

---

Under review as a conference paper at ICLR 2021
Table 11:
Ablation study features with success rate and average queries of targeted attack on ImageNet. E = 0.05 and query limit is 10000. We use feature Zeue = {i. k. pca) for
CorrAttackpilf pea and Attrkktakk peas use Zeisa (i.j, k) for CorrAttackpatw/oo pea. and
ConrAttacKrinnr/o peu.
VGGI6
Resnet50
Densenet121
Attack
Success
Queries
Success
Queries
Success
Queries
CorrAttackpifuu/o
88.69%
3892
81.71%
4066
90.88%
3540
CorrAttackpiltu pea
88.41 %
3826
81.84
4064
91.29% %
3513
CorrAttackriipu// /o
98.11 %
2233
95.86%
2682
98. 10%
2195
AtarA pon
98.07%
2191
96.39 %
2531
99.41 %
2019
At each iteration, in BayesOpt and Atyes-Attack, the changes of overall perturbation is
6, 6 15000 U Uo
U... L 02
182000
U
52-1 epon U... ..... U 81-1 Chwel J-
(21)
Clawe
However, in CorrAttack,
6, - 6 =
86-1 Cayé
(22)
Esse
In conclusion, BayesOpt and Bayes-Attack view each block as a dimension, try to search the overall perturbation directly. CorrAttack defines low dimension feature space, keep an overall perturbation and try search an action on single block.
Time complexity and running time: the dimension of input and n the number of samples. And the dimension for CorrAttack (d dd=4 4 for Zeask = (i,j, k pca)) is much smaller than BayesOpt and Bayes-Attack (d 6912 if = w = 48, c = 3). Moreover, we can convert the continuous search space of BayesOpt and Baycs-Attack from |-e, e] 6692 discrete search space E = { c001. Chwe J. whose number is only 6912, smaller search space could save the computation time of acquisition function.
The time complexity of fitting GP regression is O(dn²) where
We compare the running time for CorrAttackpup with BayesOpt and Bayes-Attack 20 images from ImageNet. Table 12 shows the running time for the un-targeted attack. We use PyToret"" to develop these two models. All experiments were conducted on a personal workstation with 28 Intel(R) Xeon(R) Gold 5120 2.20GHz CPUs, NVIDIA GeForce RTX2080TI 1 11GB GPU and 252G memory.
BayesOpt models the loss function with very high dimensional Gaussian process. The decomposi- tion of additive kernel also needs to be restarted several times. Even though we try to optimize the speed of BayesOpt with GPU acceleration, it is still very slow and takes hundreds of times more computational resources than CorrAttack.
Bayes-Attack could be regarded a simpler version of BayesOpt, which does not add additive kernel. We do not evaluate it on targeted task (when query>1000) since GP inference time grows fast as evaluated query increases, e.g. For Bayes-Attack, when 150 <query< 200, Time=1.6s/ /query; 800 <query< 1000, Time = 10.5s/f /uuery... CorrAttack solves this problem with Time=0.1s/ huu.uurr/uuuyuu query even when query reaches 10000. Since we forget the previous samples before т, our input sample will be smaller than The forgetting technique can not be applied into the Bayes-Attack and BayesOpt since they are searching the perturbation of all blocks so each sample needs to be remembered.
C.7 GROWING CURVE SUCCESS RATE
The number of average queries is sometimes misleading due the the heavy tail distribution of queries. Therefore in Figure[] we plot the success rates at different query levels to show the detailed behaviors of different attacks. shows that CorrAttack much more efficient than other methods at all query levels.
https://pytorcch.org/
16

---

Under review as a conference paper at ICLR 2021
Table 12: Comparsion of running time between Atrrkttakkn BayesOpt un-targeted attack.
"Per Query" means the average time needed to perform one query to the loss-oracle and "Per Image" denotes the average time successfully attack image. Since BayesOpt needs thousands of hours to run all samples, we only tested on 20 samples from ImageNet, which will be marked as *
VGG16
Resnet50
Densenet121
Time
Per Query
Per Image
Per Query
Per Image
Per Query
Per Image
BayesOpt* Mayes-Attack?
28.94s
5268s
40.53s
86738
39.57s
8825s
3.03s
739s
3.42s
869s
2.96s
630s
CorrAttackFipp
0.12s
19s
0.11s
15s
0.15s
20s
V6616
Resnee50
Densenet121
Success Rate
Success Rake
Successs Ralee
kwm
60%
NES
NAttack
Bandits
PARSI
290
SignHunter
Square Allack
ComAttackar
17
10-
30
ConrÄttackev
Queries
Queries
Queries
(a) Un-targeted Attack
Dansenet121
1806
67%
Success fatte
Success Rate
Success Rate
60%
ZOO
NES
NAltack
60%
6%%
60%
Bandits
SignHunter
Square
ConrAttackar
ComAllackee
Queries
Quertes
Quertes
(b) Targeted Attack
Figure 4: Success rate of black-box attack at different query levels for undefended ImageNet models.
C.8 VISUALIZATION LOCAL PROPERTY AND SLOW VARYING PROPERTY
Figure shows more examples of finite difference for different network architectures and different dataset. They all have local correlation structure as shown in Figure [ And Figure showws more examples like Figure 2 the slow varying properties exist for different architectures and different datasets.
C.9 GOOGLE CLOUD VISION API
7 the example of attacking the Google Cloud Vision API. Corr and PARSI suc- cessfully change the classification result. BeyesOpt, however, can not remove the top 1 classification result out of the output.
C.10 VISUALIZATION OF ADVERSARIAL EXAMPLES
17

---

Under review as a conference paper at ICLR 2021
(a) VGGI6 Imagenet
(b) Resnet50 Imagenet
(c) Densenet121 on Imagenet
(d) LeNet on MNIST
Figure 5: Finite difference of perturbation like Figure
h w = 28. For Imagenet, and
? 0.05. For MNIST, b 1 and 7 0.2
18

---

Under review as a conference paper at ICLR 2021
(a) VGGI6 Imagenet
(b) Resnet50 Imagenet
(c) Densenet121 on Imagenet
(d) LeNet on MNIST
Figure 6: Difference finite difference of perturbation like Figure 2 = w 28. For Imagenet,
b = 8 and n 0.05. For MNIST, b and
0.2
19

---

Under review as a conference paper at ICLR 2021
Snake
Conegon cooreetua
Garp
Rony-fish
Milfiihh
Cyprinidbe
Natural Image
(b) CorrAttackripp
Flsh
Groen
91%
Fish
Purple
85%
Corogonus Lavarotus
765
Finger
70%
Carp
59%
Hand
106
Tench
58c
Nail
67
Cyp inidan
52%
(c) BayesOpt
(d) PARSI
Mouth
75%
Reptle
NAttack
Figure 7: Example result of attacking Google Cloud Vision API
20

---

Under review as a conference paper at ICLR 2021
Figure 8: Visualization of adversarial examples for targeted attack on Densenet 0.05
21


Reviews:
[{"review_id": "wAF4ZAJJzWh", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 work considers an important problem of generating adversarial examples to attack a black-box model. The paper proposes a new approach to consider an adversarial example as a result of a sequence of pixel changes from a benign instance. Therefore, the adversarial generation problem can be considered as a bandit problem, and thus we can leverage Bayesian optimization to search for an instance that maximize the changes on the loss function through a sequence of pixel changes. The evaluation is comprehensive, and demonstrates that fewer number of black-box queries are needed to achieve a higher attack success rate.\n\nI pretty much enjoy this work. The only concern is that I'm not so sure why the speed of CorrAttack is much faster than BayesOpt and Bayes-Attack. It seems that the main reason is because the work defines a block structure (as in Sec 4.1), so that the number of blocks is much smaller than the number of raw pixels. Such a hierarchical structure can naturally lead to a hierarchical search procedure as discussed in Sec 4.3. Is this the main reason why speed is fast? Such an idea doesn't seem to be unique to the bandit setup, is a similar idea also applicable to previous work such as BayesOpt and Bayes-Attack? I hope such an issue can be discussed more in the revision.", "extra_scores": {}, "extra_text": {}}, {"review_id": "vIBzSgcOEyH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "\n\n\n\n\nThis paper proposes a new black-box attack that assumes access to loss-oracle of the target model. The attack exploits temporal and spatial correlation of block-wise pixel perturbations in a Bayesian optimization framework to achieve query efficiency.\n\nPros:\n- Overall, I enjoyed reading this paper. It is one of the few papers that employ scalable GP regression in black-box attacks. It also provides a novel formulation of how the action space of perturbation should be searched by optimizing a surrogate reward function over a low-dimensional space comprising image block location and a PCA-based feature.\n- The proposition combines several aspects of different attacks from the literature in one framework: sign flips, Bayesian optimization, hierarchical blocking, and exploitation of temporal- and spatial-correlation in natural images.\n\nCons:\n- I have highlighted my remarks below and hope the authors address them.\n\n\n\nComments/Questions:\n- Fig 1: I appreciate the authors' attempt to motivate contextual bandits and slow varying property, but making this conclusion based on one image of one dataset (ImageNet) and one architecture (ResNet50) is not sufficient. Is this observation consistent over *multiple* images of *multiple* datasets and across *multiple* architectures?\n- Table 1: NAttack achieves 100% on VGG16 and DenseNet. It is not highlighted in bold.\n- Table 3: query limit \"1000\" -> \"10,000\"?\n- Page 2, Paragraph 2: What is the distinction between BayesOpt and Bayes-Attack. Most of the discussion is around BayesOpt.\n- Page 2, Sec 2, Paragraph 2: Reference of AutoZOOM is missing.\n- Page 2, Sec 2: The context in which NES and CMA-ES are presented gives the impression that they are adversarial attacks, please rephrase to indicate they are gradient-free optimization techniques.\n- Eq. 9 : the notation is not clear. Is $e_{ijk}$ of the same dimensionality as $\\nabla_{x_t}l(x_t,y)$?. The definition of $e_{ijk}$ does not imply that.\n- It seems that most of the computational gains that CorrAttack has over BayeOpt and BayesAttack is due to the use of **scalable** GP regression (GPytorch) - not to mention the low-dimensionality of its GP. To highlight the benefits of the other aspects of CorrAttack, I think all (BayesOpt, BayesAttack, and CorrAttack) should employ the same GP tool\n- Fig 3: Are the rewards across different block sizes comparable? If so, the plot suggests that using smaller blocks yields **faster** convergence to **better** rewards which in turn does not justify the hierarchical bayesian optimization search of Sec 4.3.  \n- PCA formulation: please elaborate on how PCA is employed to compute a single feature per block. In particular, is PCA performed for each block (pixel-level PCA) or over all the pixels of the image?\n- Just as the authors compared the Bayesian aspect of the attack to Bayesian attacks (BayesOpt, Bayes-Attack), it would have been great if the authors could contrast the \"flip\" aspect of the attack with flip-based attacks---e.g., SignHunter & SIMBA ---that the authors mention in Sec 2.\n- Ablation Studies: I appreciate the study but I think it lacks supporting evidence of \"hierarchical vs non-hierarchical attack\" and \"small (one-pixel) block vs 32-pixel block\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "qPkGNaRHWmW", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "The paper proposes to use time-varying contextual bandits in order to improve the query efficiency of score-based adversarial black-box attacks.The effectiveness is demonstrated on various classifiers for ImageNet and compared against several baseline methods.\n\nThe improvements over the baseline methods seem significant, although I have one question: in Algorithm 1, what is the actual value for m used in the experiments? The appendix indicates that m=0.03n, however, the value for n isn’t given as far as I can see. This is an important detail because it determines the number of queries that CorrAttack needs to perform upfront. Is it correct that, depending the actual value of m, some of the baseline methods may actually be more efficient than CorrAttack if the attacker only wants to compute a single adversarial example?\n\nAnother question: the original ZOO paper (Chen et al., 2017) reports more than 90% attack success rate with a maximum of 1,500 queries per sample against Inception-v3, which is higher success rate and lower number of queries than reported in this paper. Did you use the same hyper parameters as in the original work?\n\nMinor observations:\np.2: “searches over a much limited action space models the reward” -> something is missing here\np.2: “the substitute model requires a lot of training data” -> this is a bit casual\np.2: “the dimension of the embedding space is still in the thousands” -> this depends on the particular model under consideration; suggest to generalise this statement\np.3.: “score-based attack” -> “score-based attacks”\np.4.: last paragraph before Section 4.1: the specific context of images ia introduced a bit abruptly; it will be good to make more clear which parts of the paper apply to classifiers in general, and which ones only to the image domain.\np.4: “d is the image pixels” -> “d is the number of image pixels”\np.4.: “we also find that the” -> “that” should be omitted \np.5: what is “EI”?\np.8: “find the action the large award” -> something’s missing in this sentence\np.8: last paragraph: what is meant by the “embedding from the transfer-based attack”? The very last sentence about adversarial training doesn’t make much sense to me; in particular, defending against white-box attacks should also work against CorrAttack; on the other hand, the objective of adversarial training usually isn’t to defend just against one specific attack, but to make the model robust against worst-case examples within e.g. an l-p-ball, regardless of what attack algorithm may be used to construct such examples.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MZduXl4sgZm", "reviewer": "AnonReviewer2", "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:**\nThe paper proposes a new approach for generating black-box adversarial attacks based on slowly-varying contextual bandits. The proposed approach achieved query efficiency and success rate which are not too far away from the current state of the art.\n\n**Pros:**\n- High query efficiency and success rate (although not state-of-the-art, see Cons below).\n- Better runtime than other Bayesian optimization methods (but it’s unclear to me how effective the Bayesian optimization approach is in the first place, see Cons below).\n- The paper is clearly written.\n\n**Cons:**\n- My main concern is the list of competitors in Table 1 which does not include [SignHunter (ICLR’20)](https://openreview.net/pdf?id=SygW0TEFwH) or [Square Attack (ECCV’20)](https://arxiv.org/pdf/1912.00049.pdf). In particular, they obtain the following average number of queries for untargeted attacks on ImageNet for eps=0.05 (taken from Table 2 from the [Square Attack paper](https://arxiv.org/pdf/1912.00049.pdf)):\n| Method |  VGG | ResNet-50 |\n| ------------- |-----------------------:| -----:|\n| SignHunter | 95 | 129 |\n| Square Attack | **31** | **73** |\n| CorrAttack-Flip | 130 | 150 |\n- Another related concern that I have is whether the proposed Bayesian optimization approach really helps. CorrAttack-Flip resembles a lot the SignHunter approach which doesn’t rely on taking the optimal action and instead selects actions in some predefined (but to some extent, arbitrary) order. Moreover, updates of SignHunter are similar in spirit: they also suggest to flip eps to -eps and vice versa, although they rely not on squares but on horizontal stripes (due to flattening of the image tensor). Thus, I would be very interested to see an ablation study for the success rate and query efficiency of (1) CorrAttack-Flip vs (2) CorrAttack-Flip with a **random selection of actions**. In other words, does the proposed Bayesian optimization framework really help, and if so, what is the margin? Related to this, there is an ablation study in Table 7 about the importance of PCA features, but the shown improvement is very minor and I am not sure if it’s statistically significant.\n\n\n**Minor suggestions**\n- It would be good to include at least a short discussion why you selected the expected improvement acquisition function and not other alternatives.\n- Page 4: “where d is the image pixels” -> “where d is the **number** of image pixels”\n- Implementation of the time-varying property: for completeness, it would be also good to provide an ablation study that would justify the choice out of the two alternatives you mentioned.\n- All entries in Table 4 are based only on 10 samples. I’m not sure what kind of conclusion we can draw from an comparison which is made only based on 10 samples.\n\n**Score:**\nMy current score is 4/10 but I would be willing to raise it if my second concern (mentioned in **Cons**) is resolved.\n\n-----\n\n**Update:**\nAfter the rebuttal, I update my score to 6/10 (see the justifications below).\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new Bayesian optimization method based on the Gaussian process bandits framework for black-box adversarial attacks. The method achieves good performance in the experiments, which was appreciated by all the reviewers.

At the same time, the presentation of the method is quite confusing, which currently precludes acceptance of the paper. In particular, during the discussion phase the reviewers were not able to decipher the algorithm based on the description presented in the paper. It is not clear how the problem is modeled as a bandit problem, what the loss function $\ell$ is minimized and why minimizing it makes sense (assuming, e.g., that $\ell$ it the hinge loss as suggested and the initial prediction is good with a large margin, that is, the loss is zero, equation 6 never changes $x_t$ when the procedure is started from $x$). This connection, since it is the fundamental contribution of the paper, should be much better explained. Once the problem is set up to estimate (maximize?) the reward, it is changed to calculating the difference in the minimization (cf. equation 11), which is again unmotivated. (Other standard aspects of the algorithm should also be explained properly, e.g., the stopping condition of Algorithm 1)

Unfortunately, the paper is written in a mathematically very imprecise manner. As an example, consider equation (6), where $B_p$ and the projection operator are not defined, and while these can be guessed, a projection of the argmin seems to be missing as well in the end (otherwise nothing guarantees that $x_T$, which is the final outcome of the algorithm, remains in the $L_p$ ball). Another example is the $Discrete\ Approximate\ CorrAttack_{Flip}$ paragraph which requires that every coordinate of $x$ should be changed by  $\pm\epsilon$. It is also not clear what "dividing the image into several blocks" means in Section 4.1 (e.g., are these overlapping, do they cover the whole image, etc., not to mention that previously $x$ was a general input, not necessarily an image). It is also unlikely that the stopping condition in Algorithm 1 would use the exact same $\epsilon$ for the acquisition function as the perturbation radius for adversarial examples, etc. While some of these inaccuracies and unclear definitions are also mentioned in the reviews, unfortunately there are more in the paper.

The authors are encouraged to resubmit the paper to the next venue after significantly improving and cleaning up the presentation.


Decision: Reject