CORRATTACK: BLACK-BOX ADVERSARIAL ATTACK
Year: 2020

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.

text: 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.

heading: 1 INTRODUCTION
text: 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, in real world scenarios models are often unknown, this situation is referred to as black-box attack.
Some methods (Liu et al., 2016; Papernot et al., 2016) use the transfer-based attack, which generates adversarial examples on a substitute model and transfer the adversarial noise to the target model. However, the transferability is limited and its effectiveness relies 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 as 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 score-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 al., 2017; Huang & Zhang, 2020; Tu et al., 2018; Li et al., 2019). In this paper, we take another approach and formulate score-based attack as a time-varying 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, we 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 a 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) to model the correlation and select optimal actions. A forgetting strategy is added to the algorithm so that the Gaussian process regression can handle the time-varying changes. CorrAttack can effectively find
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 as a 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 a 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 our 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 use 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.

heading: 2 RELATED WORK
text: There have been a line of works focusing on black-box adversarial attack. Here, we give a brief review of various existing methods.
Transfer-Based 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-wise search impossible as it requires millions of queries. ZOO (Chen et al., 2017) is 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 Ilyas 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 et al., 2018) uses bilinear transformation or autoencoder to reduce the sampling space and accelerate the optimization process. In the same spirit, data prior can be used to improve query efficiency (Ilyas et al., 2019). Besides, MetaAttack (Du et al., 2020) takes a 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. A different method, PARSI, poses the attack on `∞ norm as a discrete optimization problem over {−ε, ε}d (Moon et al., 2019). It uses a Lazy-Greedy algorithm to search over the space {−ε, ε}d to find an adversarial example. SimBA (Guo et al., 2018) also employs a discrete search space targeted at `2 norm.
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) are designed for the setting. However, the information received by the attacker is much smaller than score-based attack, and it would take many more queries than score-based attack to successfully attack an image.

heading: 3 PRELIMINARIES
text: A Gaussian process (Rasmussen, 2003) is a prior distribution defined on some bounded set Z , and is determined by a mean function µ : Z → R and a covariance kernel κ : Z × Z → R. Given n observations Dn = {(zi, f(zi))}ni=1, the prior distribution on f(z1:n) is
f(z1:n) ∼ Normal(µ0(z1:n), κ0(z1:n, z1:n)), (1) where we use compact notation for functions applied to collections of input points: z1:n indicates the sequence z1, · · · , zn, f(z1:n) = [f(z1), · · · , f(zn)], µ0(z1:n) = [µ0(z1), · · · , µ0(zn)], κ0(z1:n, z1:n) = [κ0(z1, z1), · · · , κ0(z1, zn); · · · ;κ0(zn, z1), · · · , κ0(zn, zn); ]. Now we wish to infer the value of f(z) at some new point z, the posterior process f(z)|Dn is also a Gaussian process (GP) with mean µn and covariance σ2n:
f(z)|Dn ∼ Normal(µn(z), σ2n(z)), (2) µn(z) = κ0(z, z1:n)κ0(z1:n, z1:n)
−1(f(z1:n)− µ0(z1:n)) + µ0(z), σ2n(z) = κ0(z, z)− κ0(z, z1:n)κ0(z1:n, z1:n)−1κ0(z1:n, z).
As a optimization method to maximize a function f , Bayesian optimization models the function to make decisions about where to evaluate the next point z. Assuming we already obtained observations Dt−1 = {(zi, f(zi))}t−1i=1 , to determine the next point zt for evaluation, we first use the posterior GP to define an acquisition function ϕt : Z → R, which models the utility of evaluating f(z) for any z ∈ Z . We then evaluate f(zt) with
zt = arg max Z ϕt(z). (3)
In this work, we use the expected improvement (EI) acquisition function (Mockus et al., 1978) ϕt(z) = √ σ2n(z)(γ(z)Φ(γ(z)) + φ(γ(z))) with γ(z) =
µn(z)− f(zbest)√ σ2n(z) , (4)
which measures the expected improvement over the current best value zbest = arg maxzi f(zi) according to the posterior GP. Here Φ(·) and φ(·) are the cdf and pdf of N (0, I) respectively.

heading: 4 SCORE-BASED BLACK-BOX ATTACK
text: Suppose a classifier F (x) has input x and label y. An un-targeted adversarial example xadv satisfies:
arg max j∈{1,···C}
F (xadv)j 6= y and ‖xadv − x‖p ≤ ε, (5)
where C is the number of classes. While an adversarial example for targeted attack means the maximum position of F (x) should be the targeted class q: arg maxj∈{1,···C} F (xadv)j = q. In order to find xadv , we may optimize a surrogate loss function `(x, y) (e.g hinge loss).
In this work, we consider adversarial attack as a time-varying contextual bandits problem. At each time t, we observe a state xt which is a modification of the original input x0. Before taking arm at ∈ A ⊂ Rd, we could observe the feature z of arms. And at would modify state xt to xt+1 according to
xt+1 = arg min s∈{xt+at,xt} `(ΠBp(x,ε) (s) , y) (6)
with reward function r(xt, at) = `(xt+1, y)− `(xt, y) and the checking step tries to remove negative reward. In this frame, we would like to estimate the reward r(xt, at) with feature zt using learning, and then pick at to maximize the reward. Observe that
r(xt, at) ≈ ∇x`(xt, y)>(xt+1 − xt), (7)
where the gradient ∇xt`(xt, y) is unknown. It follows from the formulation that we may rewrite r(xt, at) as a function r(xt, at) ≈ f(xt, xt+1 − xt). Since in general, we make small steps from one iteration to the next iteration, δt(at) = xt+1 − xt is small. We may approximate the reward with fixed gradient locally with
f(xt, δt) = f̃t(at),
We may consider the learning of reward as a time-varying contextual bandits problem with reward function f̃t(at) for arm at at time t. Since xt+1 − xt is small, this time-varying bandits has slowvarying property: the function f̃t changes slowly from time t to time t+ 1.
In the proposed framework, our goal is to learn the time-varying bandits reward f̃t(at) with feature zt. We use Gaussian process regression to model the reward function using recent historic data since the reward function is slow-varying, and describe the details in the subsequent sections.
We note that the most general action space contains all at ∈ Rd, where d is the number of image pixels. However, it is impossible to explore the arms in such a large space. In this work, we choose a specific class of actions A = {ai}ni=1, n 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 a good component of the feature z associated with the arm. Besides, modifying a block only affects the state locally. Therefore the reward function remains similar after state changes.

heading: 4.1 STRUCTURED SEARCH WITH GAUSSIAN PROCESS REGRESSION AND BAYESIAN OPTIMIZATION
text: Define the block size as b, we divide the image into several blocks E = {e000, e001, · · · , ehwc}, where the block is b× b square of pixels and (h,w, c) = (height/b,width/b, channel). Each block eijk is associated with the feature zeijk such as the location of the block.
Suppose we have time-varying bandits with state xt and unknown reward function f̃t at time t. By taking the action aeijk , we change the individual block eijk of xt and get xt+1 with reward f̃t(aeijk). We consider two ways of taking action aeijk on block eijk : CorrAttackDiff and CorrAttackFlip.
Finite Difference CorrAttackDiff: For action aeijk , the attacker will query `(xt + ηeijk, y) and `(xt − ηeijk, y), and choose
aeijk = arg min s∈{ηeijk,−ηeijk} `(xt + s, y). (8)
The action space A = {aeijk |eijk ∈ E}. In our framework, the bandits problem can also be regarded as learning the conditional gradient over actions. That is, when η is small, we try to choose action at with
at = arg min eijk∈E
e>ijk∇xt`(xt, y) (9)
which is the conditional gradient over the set of blocks.
Discrete Approximation CorrAttackFlip: In general, adversarial attack with `∞ budget can be formulated as constrained optimization with ‖xadv − x‖∞ ≤ . However, PARSI (Moon et al., 2019) limits the space to {−ε,+ε}d, which leads to better performance for black-box attack (Moon et al., 2019). The continuous optimization problem becomes a discrete optimization problems as follows:
maximize `(xadv, y) =⇒ maximize `(xadv, y) (10)
subject to ‖xadv − x‖∞ ≤ subject to xadv − x ∈ { ,− }d.
Following PARSI, we consider two stages to perform structured search. When flipping ε to −ε, aeijk changes the block to −ε and A = {−2εeijk|eijk ∈ E}. When changing −ε to ε, A = {2εeijk|eijk ∈ E} instead. Gaussian Process (GP) Regression: We model the difference function
gt(at) = `(ΠBp(x,ε) (xt + at) , y)− `(xt, y) (11)
instead of the reward function f̃t(at) ≥ 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 difference {zk, gk(ak))}tk=1 and learn the difference to make choices at a later stage. At each time t, we use the Gaussian process regression to model the correlation between the features zeijk and use Bayesian optimization to select the next action. More specifically, the same as eq. (2), we let
gt(aeijk)|Dt ∼ Normal(µt(zeijk), σ2t (zeijk)), (12) where Dt = {zk, gk(ak))}tk=t−τ is the difference of evaluated blocks et−τ :t with feature zet−τ:t and τ is a parameter to forget old samples. Then we use EI acquisition function to pick up the next action at+1 in A. More specifically, the same as eq. (4), we let
at+1 = arg max A
( √ σ2t (zeijk)(γ(zeijk)Φ(γ(zeijk)) + φ(γ(zeijk)))) (13)
As the difference function gt 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 Dt. 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 to remove samples near the last block eitjtkt in Dt. 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 shown in Algorithm 1, which mainly follows standard procedure of Bayesian optimization.
Algorithm 1 CorrAttack Require: Loss function `(·, ·), Input x0 and its label y, Action space A = {aeijk |eijk ∈ E}, Parameter c, τ ,
α 1: Build set D0 = {(zeipjpkp , g0(aeipjpkp ))} m p=1 using latin hypercube sampling from A 2: repeat 3: Fit the parameter of Normal(µt(zeijk ), σ 2 t (zeijk )) on Dt according to Equation (12) 4: Calculate acquisition function ϕt(zeijk ) and according to Equation (13) 5: Select aeitjtkt = arg maxA ϕt(zeijk ) according to Equation (13) 6: xt+1 = arg mins∈{xt+aeitjtkt ,xt} `(ΠBp(x,ε) (s) , y) 7: Update sample set Dt with Algorithm 2 Dt+1 = UPDATESAMPLES(Dt, xt, xt+1, eitjtkt , gt+1(aeitjtkt ), τ, α) 8: until maxA ϕt(zeijk ) < c 9: return xT ;
Algorithm 2 Update Samples Require: Sample set Dt, State xt, xt+1, Block eitjtkt , Difference gt+1(aeitjtkt ), Paramter τ , α 1: if xt+1 6= xt then 2: Dt+1 = Dt \ {(zeijk , g) ∈ Dt||i− it|+ |j − jt| ≤ α} 3: else 4: Dt+1 = Dt ∪ {(zeitjtkt , gt+1(aeitjtkt ))} 5: end if 6: Remove the earliest sample from D if the cardinality |D| > τ 7: return Dt+1

heading: 4.2 FEATURES AND SLOW VARYING PROPERTY
text: Features of Contextual Bandits: We use a four dimensional vector as the feature zeijk : zeijk = (i, j, k, pca) (14)
where i, j, k is the location of the block. And pca is the first component of PCA decomposition of [x0(e000), x0(e001), · · ·x0(ehwc)]. x0(eijk) means the block of natural image at the given position. The reward function depends on the gradient in Equation (7). It has been shown that the gradient ∇x`(x, y) has local dependencies (Ilyas et al., 2019). Suppose two coordinates eijk and elpq are close, then∇x`(x, y)ijk ≈ ∇x`(x, y)lpq. We consider the finite difference of the block eijk
∆t(eijk) = ` (xt + ηeijk, y)− ` (xt − ηeijk, y) ≈ 2ηe>ijk∇xt` (xt, y) (15)
where η is a 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 1 shows one example of the finite difference ∆t(eijk) obtained on ImageNet dataset with ResNet50. This shows blocks with closer locations are more likely to have similar reward. Therefore, we add the location of the block as the feature so that it uses historic data to find the arm with the largest reward.
In addition to the location of the difference, we 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, we use PCA to 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 a small region of xt. Let xt+1 = xt− ηeitjtkt , Figure 2 shows the difference of ∆t(eijk) and ∆t+1(eijk), which is centralized in a small region near eitjtkt . Reward function is based on the finite difference, which also has the slow varying property. It could be explained by the local property of convolution. When η is small, the finite difference can be approximated with gradient and the local Hessian:
∆t+1(eijk)−∆t(eijk) ≈ η2e>ijk∇2xt`(xt, y)eitjtkt (16) The difference is much smaller than ∆t(eijk). Today’s neural networks are built with stacks of convolutions and non-linear operations. Since these operations are localized in a small region, the Hessian of a neural network is also localized and the reward function only changes near eitjtkt .

heading: 4.3 HIERARCHICAL BAYESIAN OPTIMIZATION SEARCH
text: Recent black-box approaches (Chen et al., 2017; Moon et al., 2019) exploit the hierarchical image structure for query efficiency. Following these approaches, we take a hierarchical approach and perform the accelerated local search in Algorithm 1 from a coarse grid (large blocks) to a fine grid (smaller blocks). The algorithm for hierarchical attack iteratively performs Algorithm 1 at one block size, and then divides the blocks into smaller sizes. At each block size, we build a Gaussian process to model the difference function, and perform structured search with the blocks until maxA ϕt(zeijk) < c. When dividing the blocks into smaller sizes, we will build a new block set E with action aeijk and new feature zeijk , but keep the xt in last block size as x0 in new block size. Define the stage as S = {0, 1, · · · , s} and initial block size as b. The block at stage s is b2s × b 2s square of pixels and (h,w, c) = (2s ∗ height/b, 2s ∗ width/b, channel). The overall hierarchical accelerated local search algorithm is shown in Appendix A. It is important to note that most of the attacks terminate in the early stages and rarely need to run on fine scales.

heading: 5 EXPERIMENTS
text: We evaluated the number of queries versus the success rates of CorrAttack on both undefended and defended network on ImageNet (Russakovsky et al., 2015). Moreover, we attacked Google Cloud Vision API to show that CorrAttack can generalize to a true black-box model.
We used the common hinge loss proposed in the CW attack (Carlini & Wagner, 2017). We compared two versions of CorrAttack : CorrAttackDiff and CorrAttackFlip, to ZOO (Chen et al., 2017), NES (Ilyas et al., 2018), NAttack (Li et al., 2019), Bandits (Ilyas et al., 2019), PARSI (Moon et al., 2019), Square Attack (Andriushchenko et al., 2020), SignHunter(Al-Dujaili & O’Reilly, 2020b), BayesOpt (Ru et al., 2020) and Bayes-Attack (Shukla et al., 2019). We only test adversarial attack on `∞ 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 to the hyperparameters. The hyperparameters of other methods follow those suggested by the original papers.

heading: 5.1 UNDEFENDED NETWORK
text: 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 Densenet121 (Huang et al., 2017), which are the most commonly used network structures. We set ε = 0.05 and the query limit to be 10000 except for BayesOpt and Bayes-Attack. For targeted attacks, we 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 1 and 2. CorrAttackFlip outperforms other methods by a large margin.
As BayesOpt and Bayes-Attack takes tens of thousands of hours to attack 1000 images, we compare them with CorrAttackFlip only on 20 images and un-targeted attack. The query limit is also reduced to 1000 as 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 at different budget of adversarial perturbations at ε = 0.04 and ε = 0.06 on Resnet50. As it is shown in Appendix C.2, CorrAttack shows a consistently better performance at different ε.
Ablation study on random choices Appendix C.3 shows the ablation study of random version of CorrAttackDiff and CorrAttackFlip. 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.

heading: 5.2 DEFENDED NETWORK
text: To evaluate the effectiveness of CorrAttack on adversarially defended networks, we tested our method on one of the SOTA robust model (Xie et al., 2018) on ImageNet. The weight is downloaded from Github1. "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. CorrAttackFlip still outperforms other methods.

heading: 5.3 GOOGLE CLOUD VISION API
text: We also attacked Google Cloud Vision API, a 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 CorrAttackFlip with NAttack, BayesOpt and PARSI. The result is shown in Table 4. We also show one example of the classification output in Appendix C.9
1https://github.com/facebookresearch/ImageNet-Adversarial-Training

heading: 6 CONCLUSION AND FUTURE WORK
text: We formulate the score-based adversarial attack as a time-varying contextual bandits and propose a 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 CorrAttack 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 on `∞ norm, the same contextual bandits formulation could be generalized to other `p norm to improve query efficiency. Besides, defense against CorrAttack may be achieved with adversarial training on CorrAttack , but it may not be able to defend other attacks in the meantime.

heading: A ALGORITHM
text: Algorithm 3 Split Block Require: Set of blocks E, Block size b, E′ = ∅ 1: for each block e ∈ E do 2: Split the block e into 4 blocks {e1, e2, e3, e4} with size b/2 3: E′ ← E′ ∪ {e1, e2, e3, e4} 4: end for 5: return E′;
Algorithm 4 Hierarchical CorrAttackDiff Require: Loss function `(·, ·), Input image x and its label y, Initial Block size b, Set of blocks E containing all
blocks of the image, Threshold c, τ , α, Step size η, Adversarial budget ε 1: x0 = x 2: repeat 3: Choose A = {aeijk |eijk ∈ E} with Equation (8) 4: Run CorrAttack on current block size x = CORRATTACK (`(·, ·), x, y, A, c, τ, α) 5: if b > 1 then 6: Split the blocks into finer blocks using Algorithm 3 E = SPLITBLOCK(E, b) 7: b← b/2 8: end if 9: until ` converges
10: return xK ;
Algorithm 5 Hierarchical CorrAttackFlip Require: Loss function `(·, ·), Input image x and its label y, Block size b, Set of blocks E containing all blocks
of the image, Threshold c, τ , α, Adversarial budget ε 1: x0 = x 2: for eijk ∈ E do 3: Randomly draw v from {−ε, ε} 4: x0[eijk] = v + x0[eijk] 5: end for 6: repeat 7: An = {2εeijk ∈ E|e>ijk(xk − x) < 0} 8: Run CorrAttack flipping −ε to ε x̃k = CORRATTACK (`(·, ·), xk, y, An, c, τ, α) 9: Ap = {−2εeijk ∈ E|e>ijk(x̃k − x) > 0} 10: Run CorrAttack flipping ε to −ε xk+1 = CORRATTACK (`(·, ·), x̃k, y, Ap, c, τ, α) 11: if b > 1 then 12: Split the blocks into finer blocks using Algorithm 3 E = SPLITBLOCK(E, b) 13: b← b/2 14: end if 15: until ` converges 16: return xK ;

heading: B DETAILS OF EXPERIMENT SETTING
text: We use the hinge loss for all the experiments. For un-targeted attacks,
`untarget(x, y) = max { F (x)y −max
j 6=y F (x)j ,−ω
} (17)
and for targeted attacks,
`target(x, y) = max { max j F (x)j − F (x)t,−ω } . (18)
Here F represents the logits of the network outputs, t is the target class, and ω denotes the margin. The image will be projected into the ε-ball. Besides, the value of the image will be clipped to range [0, 1].

heading: B.1 GAUSSIAN PROCESS REGRESSION AND BYAESIAN OPTIMIZATION
text: We further provide details on both the computational scaling and modeling setup for the GP regression.
To address computational issues, we use GPyTorch (Gardner et 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-determinant via the Lanczos process. Without GPyTorch, running BO with a GP regression for more than a few thousand evaluations would be infeasible as classical approaches to GP regression scale cubically in the number of data points.
On the modeling side, the GP is parameterized using a Matérn-5/2 kernel with ARD and a 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 to [0, 1]d 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) λi ∈ [0.005, 2.0 ], (output scale) λ′i ∈ [0.05, 20.0], (noise variance) σ2 ∈ [0.0005, 0.1].

heading: B.2 HYPERPARAMETERS
text: For CorrAttack in Algorithm 4 and Algorithm 5, we set the initial block size b to be 32 and the step size η for CorrAttackDiff is 0.03. In Algorithm 1, we use the initial sampling ratio m = 0.03n at the start point for Gaussian process regression, the threshold c = 10−4 to decide when to stop the search of current block size. In Algorithm 2, the threshold is different for different block size. For CorrAttackFlip, α = 1, 1, 2, 2, 3 for block size 32, 16, 8, 4, 2 and for CorrAttackDiff, α = 0, 0, 1, 1, 2 for block size 32, 16, 8, 4, 2. We set τ = 3m = 0.09n to remove the earliest samples from D once |D| > α. The Adam optimizer is used to optimize the mean µ and covariance κ of Gaussian process, where the iteration is 1 and the learning rate is 0.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 as the original paper.
We optimize the hyperparameters for ZOO, NES. For un-targeted attack on NES, we set the sample size to be 50, learning rate to be 0.1. For targeted attack on NES, the sample size is also 50 and the learning rate is 0.05. The learning is decay by 50% if the loss doesn’t decrease for 20 iterations.
For NAttack, we set the hyperparameters the same as NES and add momentum and learning rate decay, which are not mentioned in the original paper.
For ZOO, we set the learning rate to 1.0 and sample size to be 50. Other setting follows the original paper.

heading: C ADDITIONAL EXPERIMENTS

heading: C.1 OPTIMALITY OF BAYESIAN OPTIMIZATION
text: 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 a few queries. It shows that the Gaussian process regression could model the correlation of the reward function and the Bayesian optimization could use it to optimize the time-varying contextual bandits.
C.2 VARYING THE ADVERSARIAL BUDGET
We test CorrAttack on different adversarial budget on ImageNet for both un-targeted attack and targeted attack. Table 5 and Table 6 show the success rate and average queries for ε = 0.04, 0.05, 0.06. CorrAttackFlip achieves the best performance among all methods.

heading: C.3 ABLATION STUDY ON RANDOM CHOICES
text: Table 7 and Table 8 show the ablation study on the strategy to choose action xt+1 in the line 6 of Algorithm 1. The process of Bayesian optimization helps to accelerate the optimization. As targeted attack is more complicated and requires larger number of queries, CorrAttack has more advantage in this scenario.

heading: C.4 ABLATION STUDY ON HIERARCHICAL ATTACK
text: We perform un-targeted attack on Resnet50 as shown in Table 10. 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 10, block size for non-hierarchical is essential for the performance.

heading: C.5 ABLATION STUDY ON FEATURES
text: Table 11 shows the success rate and average queries for CorrAttackwith different features. We perform ablation study on the features of the contextual bandits. One contains just the location of the
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 of queries. PCA feature achieves significant improvement on CorrAttackFlip. We may find more useful features in the future.

heading: C.6 COMPARISON BETWEEN CORRATTACKFLIP , BAYESOPT AND BAYES-ATTACK
text: 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 a group when comparing with our model CorrAttack.
Difference between CorrAttack, BayesOpt and Bayes-Attack: For l∞ attacks, assume there are no hierarchical structure, we have blocksE = {e000, e001, · · · , ehwc}, where the block is b×b square of pixels and (h,w, c) = (height/b,width/b, channel). CorrAttack, BayesOpt (Ru et al., 2020) and Bayes-Attack (Shukla et al., 2019) all try to search the adversarial noise on E with perturbation δ ∈ [− , ]d where d = h× w × c, the perturbation of block eijk at time t is δteijk .
BayesOpt and Bayes-Attack use a GP regression directly on δ ∈ [− , ]d (all blocks),
f(δ)|Dn ∼ Normal(µn(δ), σ2n(δ)). (19)
CorrAttack define an action spaceA and use a standard GP regression on features zeijk = (i, j, k, pca) (single block),
gt(aeijk)|Dt ∼ Normal(µt(zeijk), σ2t (zeijk)). (20)
At each iteration, in BayesOpt and Bayes-Attack, the changes of overall perturbation is
δt − δt−1 = {δte000 ∪ δ t e001 ∪ · · · ∪ δ t ehwc } − {δt−1e000 ∪ δ t−1 e001 ∪ · · · ∪ δ t−1 ehwc }. (21)
However, in CorrAttack,
δt − δt−1 = δteijk − δ t−1 eijk . (22)
In conclusion, BayesOpt and Bayes-Attack view each block as a dimension, try to search the overall perturbation directly. CorrAttack defines a low dimension feature space, keep an overall perturbation and try to search an action on single block.
Time complexity and running time: The time complexity of fitting GP regression is O(dn2) where d is the dimension of input and n is the number of samples. And the dimension for CorrAttack (d = 4 for zeijk = (i, j, k, pca)) is much smaller than BayesOpt and Bayes-Attack (d = 6912 if h = w = 48, c = 3). Moreover, we can convert the continuous search space of BayesOpt and Bayes-Attack from [− , ]6912 to discrete search space E = {e000, e001, · · · , ehwc}, whose number is only 6912, smaller search space could save the computation time of acquisition function.
We compare the running time for CorrAttackFlip with BayesOpt and Bayes-Attack on 20 images from ImageNet. Table 12 shows the running time for the un-targeted attack. We use PyTorch2 to develop these two models. All experiments were conducted on a personal workstation with 28 Intel(R) Xeon(R) Gold 5120 2.20GHz CPUs, an NVIDIA GeForce RTX2080Ti 11GB GPU and 252G memory.
BayesOpt models the loss function with a very high dimensional Gaussian process. The decomposition 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 as 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/query. CorrAttack solves this problem with Time=0.1s/query even when query reaches 10000. Since we forget the previous samples before t − τ , our input sample n 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.

heading: C.7 GROWING CURVE OF SUCCESS RATE
text: The number of average queries is sometimes misleading due to the the heavy tail distribution of queries. Therefore in Figure 4, we plot the success rates at different query levels to show the detailed behaviors of different attacks. It shows that CorrAttack is much more efficient than other methods at all query levels.
2https://pytorch.org/
C.8 VISUALIZATION OF LOCAL PROPERTY AND SLOW VARYING PROPERTY
Figure 5 shows more examples of finite difference for different network architectures and different dataset. They all have local correlation structure as shown in Figure 1. And Figure 6 shows more examples like Figure 2, the slow varying properties exist for different architectures and different datasets.

heading: C.9 GOOGLE CLOUD VISION API
text: Figure 7 shows the example of attacking the Google Cloud Vision API. CorrAttackFlip and PARSI successfully change the classification result. BeyesOpt, however, can not remove the top 1 classification result out of the output.
C.10 VISUALIZATION OF ADVERSARIAL EXAMPLES

Review summaries:
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.