BayesOpt Adversarial Attack
Authors: Binxin Ru
Adam Cobb
Arno Blaas
Yarin Gal
Venue:  (2020)
Keywords: Black-box Adversarial Attack
Bayesian Optimisation
Gaussian Process

Abstract: Black-box adversarial attacks require a large number of attempts before finding successful adversarial examples that are visually indistinguishable from the original input. Current approaches relying on substitute model training, gradient estimation or genetic algorithms often require an excessive number of queries. Therefore, they are not suitable for real-world systems where the maximum query number is limited due to cost. We propose a query-efficient black-box attack which uses Bayesian optimisation in combination with Bayesian model selection to optimise over the adversarial perturbation and the optimal degree of search space dimension reduction. We demonstrate empirically that our method can achieve comparable success rates with 2-5 times fewer queries compared to previous state-of-the-art black-box attacks.

Published as a conference paper at ICLR 2020
BAYESOPT ADVERSARIAL ATTACK
Binxin Ru, Adam D. Cobb, Arno Blaas
Yarin Gal
Machine Learning Research Group, Department of Engineering Science, University of Oxford frobin, acobb, arno Brobots. ox. ox.ac.u.
OATMI Research Group, Department of Computer Science,
University of Oxford yarin. ga (cs. ox ac uk
ABSTRACT
Black-box adversarial attacks require a large number of attempts hefore finding successful adversarial examples that are visually indistinguishable from the orig- inal input. Current approaches relying on substitute model training, gradient esti- mation or genetic algorithms often require an excessive number of queries. There- fore, they are not suitable for real-world systems where the maximum query num- ber is limited due cost. We propose a query-efficient black-box attack which uses Bayesian optimisation in combination with Bayesian model selection to op- timise over the adversarial perturbation and the optimal degree of search space dimension reduction. We demonstrate empirically that our method comparable success rates with 2-5 times fewer queries compared to previous state- of of-the-art black-box attacks.
[ can achieve
INTRODUCTION
Deep learning algorithms are widely deployed in many real-world systems and are increasingly be- ing used for tasks, ranging from identity verification (Liu et al. 2018), to financial services (Heaton cet al., (017) to autonomous driving (Bojarski al. 2016). However, even the most accurate deep learning models can be easily deceived by perturbations which are visually imperceptible to the hu- man eye (Szegedy et al. 2013; Carlini al. 2016). The growing costs and risks associated with the potential model failures has led to the importance of studying adversarial attacks, both in assessing their robustness and their ability to detect such attacks. In this paper we focus on highly practical adversarial attacks that fulfill the following two criteria. First, the attack is designed for a black-box setting because in real- world examples, the attacker would normally have no knowledge of the target deep learning model and can only interact with the model by querying it. Second, query efficiency is highly prioritised because in practical cases where the damage caused by the attack is high, the query budget available to the attacker will be highly limited due to the risk of being detected by the defence system or other high inherent costs (monetary or computational) of model evaluations.
Despite of the large array of adversarial attacks proposed in the literature, many of them white- box approaches that assume full access to the target model architecture and the ability of performing back-propagation to get gradient information MMosavi-Deztoro
al. 2016)] Kurakin et al., 2016) Gu & Rigazio 2014; Goodfellow et al. 2014: Chen et al. [0118] Carlini & Wagner (017)). 2017) On the other hand, for black-box attacks, there are various techniques that have been used which do not require access to the model architecture. One class of methods trains white-box substitute model
and attacks the target model with adversarial examples that successfully fool the substitute (Papernot et al. 2017). However, this type of method requires the availability of the original training data or large query data to train the substitute network and the performance is often limited by the mismatch between the substitute and the target models (Su et al. 2018). The second class of black-box attacks, which show better empirical performance than the substitute model approaches, numerically esti- mate the gradient of the target model by repeatedly querying it (Chen al.) 2017 [lyas et al. [2018] Tu et al. 2018) and attack with the estimated gradient. Although various techniques are employed to increase the query efficiency for the gradient estimation, they need excessively large query bud- get to achieve a successful attack (Alzantot et al. 20118). Another line of work removes the need for gradient estimation and uses decision-based techniques (Brendel et al. 2017) or genetic algorithms
Our code is available at htt.hh/hh..rr//.t.t......././//m

---

Published as a conference paper at ICLR 2020
(Alzantot et al. 2018) to generate adversarial examples. One popular technique that is adopted by many black-box box attacks (Chen et al. 2017: Alzantot et al., 2018 Tu et al., 2018 to significantly improve the query efficiency is to search for adversarial perturbations in a low-dimensions latent space (search dimensionality reduction). However, learning the effective dimensionality of the latent search space can be challenging by itself, and has not been investigated by the prior works to the best of our knowledge.
In light of the above limitations, we propose query efficient black-box attack that iteratively op- timises over both the adversarial perturbation and the effective dimensionality of the latent search space. Our main contributions are summarised follows:
We introduce novel gradient-free black-box attack method, BayesOpt attack. which uses Bayesian optimisation with Gaussian process surrogate models to find the effective adver- sarial example and is capable of dealing with high-dimensional image inputs.
We proposes Bayesian technique which learns the optimal degree of search dimension- ality reduction by harnsssing our statistical surrogate and information from query data. This technique can be incorporated naturally into our attack procedure, leading to efficient optimisation over both adversarial perturbation and the latent search space dimension.
We empirically demonstrate that under the Los constraint, our proposed attack method can achieve comparable success rate with about 2 to times fewer model queries in comparison to current ffate-of-the-as query- eeey-eefficient black box attack methods.
2 RELATED WORK ON BLACK-BOL -BO ATTACKS
Most of the existing adversarial attacks (Moosaii Dezfool al. 2016 Kurakin et al. 2016; Gu & Rigazio 2014] Goodfellow et al. 2014 Chen et al. [0188] Carlini & Wagner 2017) focus on white- box settings, where the attacker can get full access the target model and has complete knowledge of the architecture, weights and gradients to generate successful adversarial examples. However, real-world systems are usually attacked in black-box setting, where one has knowledge about the model and can only observe the input-output correspondences by querying the model. Here we give brief overview of various existing black-box attacks.
Substitute model One class of black-box attacks uses data acquired from querying the target black- box model train substitute model (Papernot al., 2017). which mimies the classification be- haviour of the target model. The adversary can then employ any white-box method to attack the fully observable substitute model and apply the successful adversarial example the target model. Such approaches rely on the transferability assumption that adversarial examples which are effective to the substitute model are also very likely to conceive the target model given their similar classifica- tion performance on the same data (Szegedy et al. 20.3). Moreover, provide training data for the substitute model, the adversary either requires information on the target model's s training set, which is highly unrealistic in real-world applications, needs to build a synthetic training set by querying the target model (Papernot et al. 2017). which implics a large number of model evaluations and becomes hardly feasible for large models complex datasets (Brendel et al. 2017).
Gradient estimation An alternative to training a substitute model is to estimate the gradient via finite differences and use the estimated gradient information to produce attacks. However, the naive coordinate-wee wist gradient estimation requires excessive queries to the target model (2 queries per co- ordinate per descent/attack step) and thus is not feasible for attacking models with high dimensional inputs (e.g. classifiers on ImageNet). Chen et al. (017)) overcome this limitation by using stochastic coordinate gradient descent and selecting the batch of coordinates via importance sampling, intro- ducing the state-of thethe-rrt zeroth -odder attack, ZOO, which achieves comparable attack success rate and perturbation costs as many white-box attacks. Although ZOO makes computationally tractable to perform black-box attack on high-diment sigh-dimensional image data, it still requires millions of queries to generate a successful adversarial example, making it impracticable for attacking real-world systems where model query can be expensive and the budget limited. Improving on ZOO, AutoZOOM (Tu et al. 2018) significantly enhances the query efficiency by using random vectors to estimate the full gradient and adjusting the estimation parameter adaptively to trade off query efficiency vs. input per- turbation cost. More importantly, AutoZOOM shows the benefits of employing dimension reduction techniques in accelerating attacks (i.e. searching for adversarial perturbation in low-dimensional
2

---

Published as a conference paper at ICLR 2020
latent space and decoding it back to the digendimensional input space). Parallel work by Ilyas et al. (2118) estimate the gradient through a modified version of natural evolution strategy which can be viewed as a finite-difference method over random Gaussian basis. The estimated gradient is then used with projected gradient descent, a white-box attack method, to generate adversarial examples.
Gradient-free optimisation As discussed, gradient-estimation approaches in general need cessive number of queries to achieve successful attack. Moreover, their dependence on the gradient information makes them less robust defences which manipulate the gradients (Athalye et al. 2018 Brendel et al. 2017 Guo et al. 2017). Thus, truly gradient-free methods are more likely to bypass such defences. One recent example, which has demonstrated state-of-the-ane query efficiency, is GenAttack (Alzantot et al. 2018). GenAttack uses genetic algorithms to iteratively evolve popu- lation of candidate adversarial examples. Besides having an annealing scheme for mutation rate and range, GenAttack also adopts dimensional reduction techniques, similar to AutoZOOO, to improve the query efficiency. parallel to GenAttack, [Brendel et al.) (2017) introduce decision-based at- tack, Boundary Attack, which only requires access to the final model decision. Boundary Attack starts from a huge adversarial perturbation and then iteratively reduces the perturbation through a random walk along the decision boundary. However, Boundary Attack takes about 72 times more queries than GenAttack to fool an undefended ImageNet model (Alzantot et al.] 2018). Another recent approach introduced in Moon al. (2019) reduces the search space to a discrete domain and subsequently uses combinatorial optimisation to find successful attacks, mostly focusing on the less challenging setting of untargeted attacks. Finally, the prior works that use Bayesian optimisation for adversarial attacks (Suya et al. 2017 Zhao et al. 2019) only investigate the use of simple Gaussian process as the surrogate model and are limited in their performance. The method proposed in (Suya et al., 2017) deals with the untargetted attack setting and only demonstrates the effectiveness of Bayesian optimisation in comparison to random search on a low-dimensional (d 57) email attack task. BO-ADMM proposed in (Zhao et al.] 2019) works on image data but it applies Bayesian op- timisation directly on the search space of image dimension to minimise the joint objective of attack loss and distortion loss. Despite its query efficiency, BO-ADMM leads to poor-quality adversarial examples of large distortion loss.
PRELIMINARIES
3.1 PROBLEM DEFINITION
We focus on the black-box attack setting, where the adversary has no knowledge about the network architecture, weights, gradient or training data of the target model f, and can only query the target model with an input x to observe its prediction scores all C' classes (i.c. f: R - [0, 1] (Tu et al. 2018 Alzantot et al., 2018). Moreover, we aim to perform targeted attacks, which is more challenging than untargeted attacks, subject to constraint on the maximum change to any of the coordinates (i.e., a Lxx constraint) (Warde-Farley & Goodfellow 2016: Alzantot et al.) 2018). Specifically, targeted attacks refer to the case where given valid input Eorigin of class forigin (l.e. arg max,e((....CC) J (Barigin); = lorigin) and a target 1 * lorigins we aim to find an adversarial in-
put æ. which is close to Lorigin according to the Los- norm, such that arg max (1....C) f(x); = t.
Untargeted adversarial attacks refer to the case that instead of classifying Torigin as forigins we try to find an input x so that arg max f(x): A Lorigin.
In our approach, follow the convention optimise over the perturbation 5 instead of the adver-
sarial example æ directly (Chen et al. 2017 Alzantot et al. 2018 Tu et al. 2018). Therefore, our problem can be formulated as:
arg max fXooiggn + +6) =t s.t. ||0|| o0 S 8maz ig (1,....))
3.2 BAYESIAN OPTIMISATION
Bayesian optimisation (BayesOpt) is a query-effccient approach to tackle global optimisation prob- lems (Brochu et al., 2010). It is particularly useful when the objective function is black-box and is costly to evaluate. There are 2 key components in BO: a statistical surrogate, such as a Gaussian process (GP) or a Bayesian neural network (BNN) which models the unknown objective, and an
3

---

Published as a conference paper at ICLR 2020
acquisition function ax.)) which is maximised recommend the next query location by trading off exploitation and exploration (see Algorithm in Appendix A for standard BayesOpt).
BAYESOPT ATTACK
4.1 BAYESOPT ATTACK OBJECTIVE
It has been shown that reducing the dimensionality of the search space in Equation increases query efficiency significantly (Chen et al.] 2017; [Tu et al. 2018 Alzantot et al. 2018 Due to our focus on the small query regime where number of observation data, we adopt the previously suggested dimensionality reduction technique, bilinear resizing, to reduce the challenging problem of optimising over nigh-dimensional input space of x E IRd to one over a relatively low-dimensional input space, setting æ = Corigin + g(0) where 8 E Rd with d' < d and IRd _ Rd being the bilinear resizing decoder
surrogate model needs be trained with very small
Furthermore, we follow the approach of smoothing the discontinuous objective function in Equation (1). which has been found to be beneficial in previous work (Chen et al. 2017] Tu et al. 2018 Alzantot al. (018). Together with the dimensionality reduction, this leads the following black- box objective problem for our Bayesian optimisation:
8 arg max y())
s.t.
E [- 1-8max Smax) ]d
(2)
where y(δ) log (Worigin + +((0)), log
Σ j#l
(Worigin + g())),
4.2 GP-BASED BAYESOPT ATTACK
We first use BayesOpt with standard GP as the surrogate to solve for the black-box attack objective the reduced input dimension in Equation The GP encodes our prior belief on the objective y
y (((
(3)
which is specified by a mean function μ and a kernel/covariance function & (we use the Matern-5/2 kernel in our work). In our work, we normalise the objective function value and thus use a zero- mean prior ua(-) = 0. The predictive posterior distribution for y at a test point & conditioned on the observation data D.-1 = {ō,, yi | I- = 1812-1. then has the form:
p(ur D.-1) =
(4)
where
My((8) = k(ō,, 81:1 K 1:t 11:1-191t-11
(5)
ky (5, 8%) = k: 5%) k(,, 8 -
K 1:t- k(d 8%).
(6)
where K K ((01.-11, 012-1) is the t x matrix with pairwise covariances k 6(5,, 5 ) 1, m < t- as entries. The optimal GP hyper-parameters 0* such as the length scales and variance of the kernel function k can be learnt by maximising the marginal likelihood p(D,_1 which has analytic form as presented Appendix Please refer to (Rasmussen) 2003) for GPs.
Based on the predictive posterior distribution, we construct the acquisition function a(8 ((,)) to help select the next query point d,. The acquisition function can be considered as utility measure which balances the exploration and exploitation by giving higher utility to input regions where the functional value is high (high (ly) and where the model is very uncertain (high kwy) The approach of using BayesOpt with GP surrogate attack the target model is described in Algorithm
Note that our method is not dependent a particular choice of decoder, i.c. it could also be used together with autoencoder- PCA-hasea dimensionality reduction technique.
4

---

Published as a conference paper at ICLR 2020
Algorithm BayesOpt Attack
1: Input: A black-box function y. observation data Du, iteration budget T, decoder g(-)
2: Output: The best recommended advensarial example xt = Borigin + g(6*)
3: for /. 1,- ..... do
4: Select 8 = arg max 0rg (=(6))
5: Vt = y(,)) and D; D (ōr, 3/2)
6: Update the surrogate model with D;
7: end for
4.3 ADDITIVE GP-BASED BAYESOPT ATTACK
Although techniques such as bilinear resizing are able to reduce the input dimension from the orig- inal image size (e.g. d 3072 for CIFARIO image) much lower dimension (e.g. d' 192), the reduced search space for the adversarial attack is still considered very high dimensional for Ga-based BayesOpt (which is usually applied on problems with d' 20).
There are two challenges in using BayesOpt for high dimensional problems. The first is the curse of dimensionality in modelling the objective function. When the unknown function high- dimensional, estimating it with non-parametric regression becomes very difficult because it is im- possible to densely fill the input space with finite number of sample points, even the sample size very large (Györfi et al., 2006). The second challenge is the computational difficulty in optimising acquisition function. The computation cost needed for optimising the acquisition function to within desired accuracy grows exponentially with dimension (Kandasamy et al. 2015).
We adopt the additive-GP model (Duvenaud et al. 2011 Kandasamy et al. 2015) to deal with the above-mentioned challenges associated with searching for adversarial perturbation in the high dimensional space. The key assumption we make is that the objective can be decomposed into a sum of low-dimensional composite functions:
v(6) Σ (0(()))))
where 5(4,) denotes disjoint low-dimensional subspaces, ö = 1 and 8(A,) ((())))) 0 for all j # i. If we impose a GP prior for each y) the prior for the overall objective y is also a GP: y ~ GP(u(6)) k(6, 8')) where µτ6) Σド أام (8(4))) and k(5, 8') = ES kG) (5(4)),88 8)(A)).
The predictive posterior distribution for each subspace p(siie (Aa) D.) is:
(o) (6(4)) s(As) K K k( (o((A)) o(((s)) 100(
(A)) 8f s((A))) (6) ((A))
K 1 S((A))
In our case, the exact decomposition (i.e. which input dimension belongs to which low-dimensional subspace) is unknown but we can learn it together with other GP hyperparameters by maximising marginal likelihood (Kandasamy et al., 2015). We demonstrate the effectiveness of our decompo- sition learning in Appendix E Note that in this case, the acquisition function is formulated based
on p(ye 15 (5( DD.) for each subspace and is also optimised the low-dimensional subspace, thus leading to much more efficient optimisation task. The optimal perturbations in all the subspaces {8(A,) ) =-=1 are then combined to give the next query point 8,
4.4 LEARNING THE OPTIMAL d'
Generating the successful adversarial example x E IR by searching perturbation in a reduced di- mension 8 E R has become popular practice that leads to significant improvement in query efficiency (Chen et al., 2017 Tu et al. 2018 Alzantot et al. 2018). However, what the optimal is and how to decide efficienlly have not been investigated in previous work (Chen et al.) 2017: Tu et al. 2018 Alzznnoo et al. 2018). As we shown empirically in Section setting d' arbitrarily can lead suboptimal attack performance in terms of query efficiency, attack success rate well
5

---

Published as a conference paper at ICLR 2020
Algorithm 2 Bayesian selection of d'
1: Input: A decoder g(-), observation data D- = {g( y M where g( E R and a set of
possible d' {d]) [
2: Output: The optimal reduced dimension d²* and the corresponding GP model
3: for ,,....NV do
4: D = (g(6))) , Mil where g (g(6.) e R
5: Fit a GP model to D and computes its maximum marginal likelihood (DD-110", :d).
6: end for
7: Select d² = arg max max meiny, P(D ,d))))))) and its correspond GP model
,d))
as perturbation costs while finding good d' by trial and error or progressive increasing compu- tationally expensive and highly inefficient because the optimal d" varies with different attack input Forigin- An effective way of learning d' is thus very important for adversarial attacks. In this sec- tion, we propose rigorous method, which is neatly compatible with our attack technique, to learn the optimal d' from the query information.
The optimal d' should be the one that both takes into consideration our prior knowledge on the discrete d' choices and at the same time best explain the observed query data. Given that our BayesOpt attack uses statistical surrogate (i.e. GP in our case) to model the unknown relation between the attack objective score y and the adversarial perturbation d, this naturally translates to the criterion of maximising the posterior for d":
p(d] = ((D--1l()pp(7))
(8)
p(D:-1)
where pdD) is the marginal likelihood (evidence) of adopting a specific dj. p(d")) ) is our prior over the possible d' values and p(D;-1) = Σ, p (DD:nlld))p((
normalising constant. we match different dł to different model choice, the problem of choosing d" then becomes the classic Bayesian model selection task (Rasmussen) (200)). In most cases, our prior assumption is that we do not prefer one d' over another (i.e. flat prior p(d") p(d))) for + i) and thus we can select d' by
comparing their Maackay & Mac Kay 2003):
p(dgID. p(D, | (d)) p(D,-1ld7)
p( P(d))D--1) P(Dr-11()p(()) p(D,-1ldz)
The exact computation of the evidence term requires marginalisation over model ppperrparameters, which is intractable. We approximate the integral with point estimates (i.e. marginal likeli- hood of our GP model): p(D)) = f PDD 0, d dd)p((dd)dd s p(D,-1 ,d)) where 0- = arg max, P(D._1 dj)). For query efficiency, we project the same perturbation query data in the original image dimension DI_ = {9(d.), y to different latent spaces to get corresponding low-dimensional training data sets for separate GP models. The GP model that corresponds to d'
is trained on D = tg (o(6.)). Wil where g (9(6))) E Rd, Then we select the optimal
d" by comparing the marginal likelihood p(D,"" 0 dd)) of each GP surrogate. The overall proce- dure for d' selection is described in Algorithm 2] We would like to highlight that the use of the statistical surrogate in BayesOpt attack approach enables to naturally selection technique to learn the optimal d' that automatically enjoy the trade-off between data-fit quality and model complexity. And also show empirically in Section 5.3 that by automating and incorporating the learning of d' into our BayesOpt attack, we can gain higher success rate and query efficiency. Other adversarial attacks methods can also use our proposed approach decide d' but would require the additional efforts of constructing statistical models to provide p(D)-1ld3).
the Bayesian model
EXPERIMENTS
We empirically compare the performance of our BayesOpt attacks against the state-of- of-tth---atttt black- box methods such as ZOO (Chen et al. 2017), AutoZOOM et al. (018)) and GenAttack (Alzantot) al. 2018). We denote the BayesOpt attack with standard GP surrogate GP-BO, its variant that

---

Published as a conference paper at ICLR 2020
drr-12x12x3
d-x-16x16x3
drr=18x1813
100
400
350
Mean per-pixel pixel (0.0001))
6.0
300
Query counts
ASA (%)
60
250
200
5.0
150
4.5
100
20
50
3.5
Image ID
Attack Instances
Attack Instances
Figure 1: Performance of BayesOpt attack with GP surrogate in different reduced dimension d". Each color represents a particular d'. The left subplot shows the attack success rates(ASR) for attacking all the other 9 classes on each of the 5 original images. The d' that leads to the highest ASR varies with the original images. The middle subplot shows the number of queries needed to attack the same attack instances (i.e. the same original image and the same attack target) by using different d", For the same attack instances, the right subplot show the effect of the choice of d' on the L2 distances between the resultant adversarial examples and the original image.
learns the d' automatically is GP-BO-auto-d" as well as the attack with additive GP surrogate as ADDGP-BO For all the BayesOpt methods, we use GP-UCB as the acquisition function 3 and update the GP hyperperameters every BayesOpt iterations. We relearn the optimal d' for GP-BO- auto-d" and the search space decomposition for ADDGP-BO every 40 iterations. For ADDGP-BO, we decompose the search spaces into M 12 sub-spaces of equal dimensions for MNIST and CIFAR10 and into M = 27 sub-spaces for ImageNet.
The target models that we attack follow the same architectures as that used in AutOZOOM and GenAttack; These are image classifiers for MNIST (a CNN with 99.5% test accuracy) and CIFARIO (a CNN with 80% test accuracy). Following the experiment design (Tu et al.) 2018), we randomly select 50 correctly classified images from CIFARIO 10 test data and MNIST test data. We then perform targeted attacks on these images. Each selected image is attacked times, targeting at all but its true class and this gives total of 450 attack instances for both CIFAR10 10 and MNIST. For ImageNet, also select 50 correctly classified images from the test set but perform one random targeted attack for each image. We Omar 0.3 for attacking MNIST and 8mac 0.05 for CIFARI 10 and ImageNet, which are used in (Alzantot et al. (018)). We use the recommended parameter setting and their open
sourced implementations for performing all competing attack methods (Chen et 2017 2018
Tu al.
Alzantot et al. 2018).
5.1 EFFECT OF d'
We first empirically investigate the effect of the reduced dimensionality d' of the latent space in which we search for the adversarial perturbation. We experiment with the GP-based BayesOpt attacks for the CIFAR10 classifier using reduced dimension of d, {6 x 6 x 3, 8 x 8 x 3, 10 x 10 3, 12 x 12 x 3, 14 x 14 x 3, 16 16 x 3, 18 x 18 x 3) and perform targeted attacks on target images with each image being attacked 9 times, leading to 45 attack instances. We first investigate the attack success rate (ASR) achieved at different d' for all the 5 images. The results on ASR out of the 9 targeted attacks for each of the 5 images, which are indicated by Image ID I to 5, are shown in the left subplot of Figure [ It's evident that the d' which leads to highest attack success rate varies for different original images Torigin-
We then examines how the d' affects the query efficiency and attack quality (average Ly distance of the adversarial image from the original image) for the attack instances (e.g. make the classifier to mis-classify a airplane image as a cat) that GP-based BayesOpt can attack successfully at all d". We present the results 4 attack instances of a airplane image in the middle and right subplots of Figure I We can see that even for the same original image and attack instances, varying d' can
"The parameter that trades off exploration and exploitation is to 2.
7

---

Published as a conference paper at ICLR 2020
Table 1: Attack results on 50 random MNIST images by using d' 14 x 14 Q denotes the query count. ASR denotes attack success rate. The standard errors are in parentheses.
Attack method
ASR
@ (Max, Median, Mean)
Average L2 perturbation (per pixel)
ADDGP-BO
97%
829, 46, (5
6.81 x 10-3 x 10
Pr-BO-autood"
98%
833, 75, 121 (=
6.89 x 10-5 x 10-6)
GP-BO 82%
899,42 (7
7.15 x 10 10-5)
GenAttack
92%
986, 146, 217(#9)
6.66 x 10 10
AutoZOOM
99%
998, 229, (-5())))
5.05 x 10-9 x 10-6)
ZO0
1%
256, 128, 128(= (44)
2.78 x 10-3 x 10-9)
Table Attack results on 50 randomly selected CIFARIO images with d' 14 14x Q denotes the query count. ASR denotes attack success rate. The standard errors are in parentheses.
Attack method
ASR
Q (Max, Median, Mean)
Average L2 perturbation (per pixel)
ADDGP-BO
87%
885, 154, 222(+10)
5.87 x 10- x 10-6)
GP-BO-auto-d"
87%
891, 159, 234
5.96 x 10-*(=5.00 x 10-6)
GP-BO
72%
141, 190(=
5.78 x 10=*(=4.67 x 10-6)
GenAttack
68%
991, (29()14)
7.38 x 10-1(+4.14 10-6)
AutoZOOM
38%
896, 102, 154(+11)
9.97 x 10-1(+1.53 x 10-5)
ZOO
4%
768, 256, (577)
1.77 x 10-1 x 10-6)
impact query efficiency and L2 norm of the successful adversarial perturbation significantly. For example, d" = x 8 x is most query efficient for attack instance and 4 but is outperformed by other dimensions in attack instance 2 and 3. Therefore, the importance of d" and the difficulty of finding the optimal d" for specific target/image motivates us to derive our method for learning automatically from the data. As shown in the following sections, our d' learner does lead more superior attack performance.
5.2 PERFORMANCE UNDER FIXED QUERY BUDGET
In this experiment, we limit the total query number to be 1000, which is slightly above the median query counts needed for GenAttack to make a successful attack on MNIST and CIFARIO (Alzantot et al.; 2018) and 2000 for ImageNet. We adopt the reduced search dimension recommended by AutoZOOM, d' = 14 14 3 for CIFAR 10 and auto-d" to automatically learn the reduced dimension d' in range between 6 6 and 28 x 28 x 1 for MNIST, and between 6 x 6 3 and 32 x 32 x for CIFAR1O.
14 x 14 for MNIST and allow GP-BO-
For ImageNet. due to the high dimensionality of its images, adopt hierarchical decoding pro- cess: 1) first performance BayesOpt (tDacks(ADDDP....... BO and GP-BO) on reduced dimension of dj 48 x 48 x and then 2) decode the adversarial perturbation found in d' to d' 96 96 3 via bilinear upsampling. 3) This is followed by another bilinear decoder projecting the adversarial per- turbation in d5 back to image dimension of d 299 299 3. As for the GP-BO-auto-d", we allow the algorithm to automatically learn the reduced dimension di in the phase 1) in the range between 6 x 6 x 60 x 60 for AutoZOOM and ZOO, we uses the optimal d" settings recommended in (Tu et al. 2018 Chen al. 2017) for ImageNet.
GenAttack is performed with the same upsampling as our methods. As
For BayesOpt attack, each iteration requires 1 query to the objective function so we limit its iteration to 1000 and early terminate the BayesOpt attack algorithm when successful adversarial example found. AutoZOOM comprises 2 stages in their attack algorithm. The first exploration stage aims to find the successful adversarial example. Once a successful attack is found, it switches to the fine- tuning stage reduce the perturbation cost (e.g. La norm) of the successful attack. We report its performance on the attack success rate and Lg norm of adversarial perturbations after a budget of 1000 queries, which allows it to fine-tune the successful adversarial perturbations found. Moreover, AutoZOOM uses L2 norm to measure the perturbation costs but our method and GenAttack limit the search space via Ta norm. We observe that the successful attacks found by AutoZOOM ineur
8

---

Published as a conference paper at ICLR 2020
Table 3: Attack results on 50 randomly ImageNet images with random target label under query budget of 2000. Q denotes the query count. ASR denotes attack success rate. The standard errors are in parentheses. ZOO fails to make any successful attack within this budget.
Attack method
ASR
@ (Max, Median, Mean)
Average La perturbation (per pixel)
ADDGP-BO
60%
1985, 1247, (296
1.74 x 10 10 x 10
GP-BO-auto-d"
32%
1999, 922, (38())28)
1.96 10 10
GP-BO 16%
1947, 1113, 1232(+162)
1.62 x 10 10-4 x 10 10-6)
GenAttack 12%
1971, 1354, 1266(+259)
2.03 x 10 4(=9.8111 x 10 10-6)
AutoZOOM
2%
1451, 1451, (4.000
1.21 10 (=0.00)
much higher perturbation costs in terms of T. norm than GenAttack and our method. Therefore, we only consider the final adversarial examples whose Top distances from the original images lie within [-Omaz, 6maz] as the successful attacks
The results on MNIST in Table D show that all our BayesOpt attacks can achieve a comparable success rate but at a much lower query count in comparison to GenAttack (Alzantot et al. 2018 and AutoZOOM (Tu et al. 2018). Specifically, the median query count of ADDGP BO is 68% less than GenAttack and 80% less than AutoZOOM while that of HBP-BO-autodd" is 49% less than GenAttack and 67% less than AutoZOOM.
As for results on attacking on CIFARIO, Table 2 shows that all our BayesOpt attack can achieve significantly higher success rate but again at a remarkably lower query counts than the existing black-box approaches. For example, our ADDGP-BO can achieve 18% higher success rate while using 37.4% less queries in terms of the median as compared to GenAttack. In addition, our ap- proaches also lead to better quality adversarial examples (Figure in Appendix BD which are closer to the original image than the benchmark methods as reflected by the lower average L2 perturbation (20.5% less). More importantly, this set of experiments also demonstrate the effectiveness of our Bayesian method for learning d" as GP-BO-auto-l leads to 15% increase in attack success rate compared to GP-BO while maintaining the competitiveness in query efficiency and L2 distance.
Similarly, the results on ImageNet in Table shows that all our BayesOpt attacks can achieve higher attack success rate than the competing methods given a query budget of 2000. ADDGP-BO the clearly best performing method in this very high-dimensional setting, achieving 5 times higher suc- cess rate than the best competing method, GenAttack, while again obtaining successful adversarial perturbations with lower average L2 perturbation (14 % less) than GenAttack. This confirms our hypothesis that the additive-Gi GP surrogate together with decomposition learning is very effective for high-dimensional optimisation.
5.3 QUERY EFFICIENCY COMPARISON
We finish by comparing the query efficiency, measuring the change in the attack success rate over query counts for all the methods. We limit the query budget of our BayesOpt attacks 1000 but let the competing methods to continue running until they achieve the same best attack success rate as our best BayesOpt attacks or exceeds a much higher limit (2000 queries for MNIST and 5000 queries for CIFAR 10 and 14000 queries for ImageNet).
As shown in Figure 2. BayesOpt attacks converge much faster to the high attack success rates than the other methods. Specifically, GP-BO-auto-d" take less than 833 queries to achieve the success rate of 98% for MNIST, which is 24% of that by GenAttack (2500). As for CIFARIO 10, both ADDGP- BO and GP-BO-an BO--BOO-tttttt takes around 890 queries to achieve success rate of 87% which is 23% of the query count by AutoZOOM and 17% of that by GenAttack. One point to note is that AutoZOOM appears be slightly more query efficient than GenAttack in this set of experiments. However, need to bear in mind that although we limit the mean Lint norm of the adversarial perturbation found by AutoZOOM to 5 maaz AutoZOOM still have the advantage of exploring beyond the δmcc for many dimensions. In the case of ImtgeNet, all our BayesOpt attacks again enjoy faster convergence, with
'This still gives an advantage to ZOO and AutoZOOM because it allows them to inject perturbation whose magnitude is larger than dma certain pixels but our BayesOpt methods and Gen limit perturbation all the pixels to be less than 5 mmaz-

---

Published as a conference paper at ICLR 2020
1.00
0.75
ASR (%)
GP: GP-BO auto dr ADDGP-BO
ASR (%)
0.6
GP-BO auto
ADDGP-BO
GP-BO
0.25
GenAttack
GenAttack
AutoZOOM
AutoZooM
ZOO
ZOO
0.00
0.0
500
1,000
2,000
3,000
5001,000
2,000
3,000
4,000
5,200
Query counts
Query counts
(a) Attacks on MNIST
(b) Attacks on CIFARIO
0.6
ASR (96
GP-BO-auto-dr
ADDGP-80
GP-80
0.2
GenAttack
AutoZOoM
2,500
5,000
7,500
10,000
12,500
15,000
17,500
20,000
Query counts
(c) Attacks on ImageNet
Figure 2: Query efficiency of BayesOpt Attacks. The plots show the attack success rate (ASR) of different methods up to certain query counts. The best BayesOpt attacks (i.e. GP-BO-auto-d" (red) and ADDGP-BI BO (blue))
achieve an ASR of 98% MNIST(a) and 87% on CIFARIO (b) within a budget of 1000 queries. To achieve the same success rates, GenAttack (purple) takes 3500 for MNIST and 5141 for CIFARIO, and AutoZOOM (green) takes 800 for MNIST and 3880 for CIFAR 10. For ImageNet (c), the best BayesOpt attack is ADDGP-BO (blue), which achieves ASR of 60% with 1985 queries. To achieve the success rates, GenAttack (purple) takes
budget of 4711 queries and AutoZOOM (green) takes 19451 queries. ZOO fails to make any attack on ImageNet within the given budget.
ADDGP-BO taking only 1985 queries to achieve 60% ASR. Mcanwhile, GenAttack, takes a budget of 4711 queries, 2.4 times that of ADDGP-BO, to achieve the same ASR and AutoZOOM costs 19451 queries which is 9.8 times that of ADDGP-BO.
CONCLUSION
We introduce new black-box adversarial attack which leverages Bayesian optimisation find suc- cessful adversarial perturbations with high query efficiency. We also improve our attack by adopting an additive surrogate structure to ease the optimisation challenge over the typically high-dimensional task. Moreover, we take full advantage of our statistical surrogate model and the available query data learn the optimal degree of dimension reduction for the search space via Bayesian model selec- tion. In comparison to several existing black-box attack methods, our BayesOpt attacks can achieve high success rates with 2-5 times fewer queries while still producing adversarial examples that closer to the original image (in terms of average L22 distance). We believe our BayesOpt attacks can be a competitive alternative for accessing the model robustness.
One limitation of our attack methods is that due to the poor scalability of GPs, the attack algorithms are computationally more expensive than most existing alternatives especially as the query number increases. Thus, our BayesOpt attacks are optimal for the setting where the cost of evaluating the target model. being it the monetary costs, computational costs or the risk of being detected, is much higher than the computational cost of the attack algorithm itself and thus query efficiency is highly prioritised. On the other hand, replacing the GP surrogates with more scalable models such as sparse GPs or Bayesian neural networks can be interesting future research direction.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Moustafa Alzantot, Yash Sharma, Supriyo Chakraborty, and Mani Srivastava. Genattack: Practical black-box attacks with gradient- optimization. arXiv preprint arXiv: 1805. 1090, 2018.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Cireumventing defenses adversarial examples. arXiv preprint 2018.
00420,
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars, arXiv preprint
2016.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Recision-based adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv: 2017.
Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv: 1012.259, 2010.
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.
Nicholas Carlini, Pratyush Mishra, Tavish Vaidya, Yuankai Zhang, Micah Sherr, Clay Shields, David Wagner, and Wenchao Zhou. Hidden voice commands. In 25th {USENIX) Security Symposium (!USENIX) Security 16), pp. 513-530, 2016.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Pin-Yu Yu Chen, Yash Sharma, Huan Zhang, Jinfeng Yi, and Cho-Jui Hsieh. Ead: elastic-net attacks to deep neural networks via adversarial examples. In secooy AAAI conference on artificial intelligence, 2018.
David K Duvenaud, Hannes Nickisch, and Carl E Rasmussen. Additive gaussian processes. In Advances in neural information processing systems, pp. 226-234, 2011.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014.
Shixiang Gu and Luca Rigazio. Towards deep neural network architectures robust to adversarial examples. arXiv preprint arXiv:1412.5068, 2014.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens Van Der Maaten. Countering adversarial images using input transformations, arXiv preprint arXiv:1711.00117 2017.
László Györfi, Michael Kohler, Adam Kızyzak, and Harro Walk. distribution-free theory of nonparametric regression. Springer Science & Business Media, 2006.
JB Heaton, NG Polson, and Jan Hendrik Witte. Deep learning for finance: deep portfolios. Applied Stochastic Models in Business and Industry, 33(1) 122 2017.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. arXiv preprint arXiv:1804.08598 2018.
Kirthevasan Kandasamy, Jeff Schneider, and Barnabás Póezos. High dimensional Bayesian optimi- sation and bandits via additive models. In International Conference on Machine Learning, pp- 295-304, 2015.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv: 002533, 2016.

---

Published as a conference paper at ICLR 2020
Yi Liu, Jie Ling, Zhusong Liu, Jian Shen, and Chongzhi Gao. Finger vein secure biometric template generation based on deep learning. Soft Computing, 22(7):2257-2665, 2018.
David JC MacKay and David JC Mac Kay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. arXiv preprint UrXiv:/905.000 2019.
Scyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 2574-2582, 2016.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506-519, ACM, 2017.
CE Rasmussen and C K Williams. Gaussian processes for muchine learning. 2006.
Carl Edward Rasmussen. Gaussian processes machine learning. In Summer School on Machine Learning, pp. 63-71. Springer, 2003.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin- Yu Chen, and Yupeng Gao. Is robustness the cost of accuracy?-a comprehensive study on the robustness of 18 deep image classification models. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 631-648, 2018.
Fnu Suya, Yuan Tian, David Evans, and Paolo Papotti. Query-limited black-box attacks to classifiers.
NIPS Workshop, 2017.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: /3/2.6/99, 2013.
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:1805. 2018.
David Warde-Farley and Ian Goodfellow. 11 adversarial perturbations of deep neural networks. Perturbations, Optimizution, and Statistics, 311, 2016.
Pu Zhao, Sijia Liu, Pin- Yu Chen, Nghia Hoang, Kaidi Xu, Bhavya Kailkhura, and Xue Lin. On the design of blx adversarial examples by leveraging gradient-free free optimization and operator splitting method. In Proceedings of the IEEE International Conference Computer Vision, pp- 121-130, 2019.
12

---

Published as a conference paper at ICLR 2020
A BAYESIAN OPTIMISATION
Here we present a generic algorithm for Bayesian optimisation.
Algorithm 3 BayesOpt Algorithm
1: Input: A black-box function y. observation data Do, iteration budget T
2: Output: The best recommendation 5*
3: for t= 1, ................................ I do
4: Select 6 arg max ox (6)
5: V/ = y(62) and D2 <- D (6t, y/3)
6: Update the surrogate model with Dr
7: end for
B ADVERSARIAL EXAMPLES FOR CIFAR10
bird
deer
frog
horse
ship
truck
Cal. bird auto plame
deer
dog
truck ship hoose frog
Figure 3: CIFARIO adversarial examples generated by our BayesOpt attack. True labels and target labels correspond to the rows and columns.
C ADDITIONAL EXPERIMENTS ON MNIST AND CIFARIO
D OBJECTIVE VALUE OVER BAYESOPT ITERATIONS
We illustrate this via the case of attacking CIFARIO image of label 9class truck) on the other 9 target labels with original label 9We plot the value of objective function (Fquation 2 which is equal the negative of attack loss, against the BayesOpt iterations/query counts. We our additive GP surrogate (ADDGP-BO) as well as the Bayesian learning of optimal d" (GP-BO- auto-d") lead faster convergence and thus higher attack success rate for this instance.
that
E EFFECTIVENESS OF DECOMPOSITION LEARNING
To learn the decomposition for the additive- GP surrogate ADDGP-BO BO attack, we follow the approach proposed in (Kandasamy et al. 2015) to treat the decomposition as additional hy- perparameter and learn the optimal decomposition by maximising marginal likelihood. However, exhaustive search over all Mld! (d, MM possible decompositions is expensive. We adopt com- putationally cheap alternative by randomly selecting 20 decompositions and choosing the one with
M the number of subspaces and d, |4g is the dimension of each subspaces
13

---

Published as a conference paper at ICLR 2020
Table Summary of attack results 7 MNIST images. Q denotes the query count. ASR denotes attack success rate. The standard errors are in parentheses.
Attack method
d,
ASR
Q (Max, Median, Mean)
Average La perturbation (per pixel)
GP-BO
14 X 14 x 1
92%
899, 53, 119(+28)
7.01 X 10-3(#1.13 x 10
ADDGP-BO
14 x 14 x
98%
584, (3))
6.50 x 10-3(+8.39) x 10 10-5)
AutoZOOM
x
97%
892, 186, 247(
5.10 x 10 x 10 10-4)
GenAttack
14 14
97%
976, 184, 239
5.56 x 30 x 10 10-5)
GP-BO
16 x 16 X
97%
400, 50, 80(=12)
7.08 x 10- 10"4)
ADDGP-BO
16 X 16 x
100%
540, 42, 72(+12)
6.49 x 10-3(+99.4111 10-5)
AutoZOOM
16 x 16 X
98%
812, 251, 295(+:88)
5.98 x 10-3(+2..3 10-4)
GenAttack
x 16
97%
928, 202, 237
5.61 x 10-3 10-5)
GP-BO
28 x 28 X 1
98%
430, 201, 121
8.71 x.71x10--0 10- 10
ADDGP-BO
28 x 28 x
100%
666, 57, 100(+15)
9.71 x 10-3 10-4)
AutoZOOM
28 x 28 X
98%
860, 185, 244(+27)
1.01 x 10-2 10-4)
GenAttack
28 x 28 X
83%
976, 365, 399(+:33)
6.26 x 10 10-9)
Table Summary of attack results on 27 CIFAR10 images. Q denotes the query count, ASR denotes attack success rate. The standard errors are in parentheses.
Attack method
d,
ASR
@ (Max, Median, Mean)
Average Lg perturbation (per pixel)
GP-BO
8
x
8
3
52%
314, 48, 70(+133
5.78 x 10 10-5)
ADDGP-BO
8 x
x
3
75%
899, 140, 234(+33)
5.55 x 10-4 10-6)
AutoZOOM
8 8
3
56%
382, 126, (37
9.58 x 10-4 10-3)
GenAttack
8 x
x
3
67%
671, 236, 286(+32)
7.40 x 10 10-5)
GP-BO
14
14
3
81%
899, 142, 192(#11)
5.74 x 10-4(1..9 10-9)
ADDGP-BO -B
14 X
14
x
90%
885, 141, 213 11))
5.79 x 10 10-5(15.16x 10-6)
AutoZOOM
14
X
14
3
42%
376, 95, 133(+12)
9.82 x 10 10-5)
GenAttack
14 14
3
75%
971, 251, (21
7.35 1H.6(2. 10-6
GP-BO
x 16
x 3
83%
785, 280, 292(+22)
5.34 x 10 10 10-5)
ADDGP-BO
16 x 16
x
87%
878, 168, 229 (299)
5.76 10 10
10-6)
AutoZOOM
16 X 16
3
3%
298, 170, 170(
7.50 x 10 40.133 x1-11.5x0000 10
GenAttack
16 X 16
3
79%
986, 281, 151,300 333 (+36)
7.36 x 10- 10-9)
the largest marginal likelihood. The method decomposition learning procedure is repeated every 40 BO iterations and we use M 12 for CIFARIO. We denote the method ADDGP-BO-LD in this section but as ADDGP-BB BO in the rest of the paper.
We also experiment with another alternative way to learn the decomposition (ADDGP-BO-FDX which is similar to importance sampling in ZOO. We group the pixels/dimensions together if the magnitude of average change in their pixel values over the past 5 BO iterations are closer (i.e. pixels that are subject to the most large adversarial perturbations are grouped together). Again, we divide the dimensions into disjoint 12 groups as above to ensure fair comparison.
Table Summary of attack results on CIFAR10 for different decomposition learning method. d, 14 14 3 which is further decomposed into 12 subspaces of d, 49. Q denotes the query count. ASR denotes attack success rate. The standard errors are parentheses.
Attack method
ASR Q (Max, Median, Mean)
Average L2 perturbation (per pixel)
ADDGP-BOL BOO-DD
94%
885, 114,1134(((2 116
5.78 x 10 4(45.32 x 10 10-
ADDGP-BO-FT
87%
899, 143, 196( =14)
5.05 10 10-4(44.52 10 10-6)
14

---

Published as a conference paper at ICLR 2020
-10
-10
-10
-20
-20
-20
Attack 1035
Attock loss
Attock loss
GP-BO_9_10
GP-80 auto-dr
ADDGP -2. 19_0
-30
-30
GP-80-aute-dr_88
-30
ADDGP-BO_8M 8_t1
GP-80-auto-dr_P3
ADDGP-B0_PP
GP-BO-R ___3
eute
ADDGP 80 89_
GP-B0_PP
dr_
440
19,
GP-8O_88
Gute0-aute-dr
ADDGP-BR 100PP800PP
GP BP-80_00 18
GP GP8B0 auto- 19,6
ADDGP 80, 19,9
19_t7
ADDGP-BO,
GP 0P--0_99_t
GP80 auto dr 19
ADDGP 80 19_8
-60
-60
-60
250
500
750
1000
250
750
1000
80 iteration
iteration
60 Reration
(a) GP-BO
(b) GP-BO-anto-d"
(c) ADDGP-BO
Figure 4: Attack objective value against BayesOpt iterations(query count) for using various BayesOpt methods attack one CIFARIO image of class label (denoted by i). Curves of dif- ferent colours correspond to the 9 different target labels (denoted by t). Convergence to O objective value indicates successful attack. ADDGP-BO and GP-BO-auto-d" enjoy faster convergence and thus higher attack success rates than simple GP-BO.
We compare the both types of decomposition learning methods using 20 randomly selected CI- FARIO images, each of which attacked on other classes except its original class and a query budget of 1000. The results are shown in T It is evident that learning decomposition by max- imising marginal likelihood ADDGP-BO-LDD can achieve higher attack success rate than pixel- value-change- based decomposition learning (ADDGP-BO-FD) given the query budget.
F GAUSSIAN PROCESSES
Gaussian processes (GPs) are popular models for inference in regression problems, especially when a quantification of the uncertainty around predictions is of relevance and little prior information available to the inference problem. These qualities, together with their analytical tractability, make them the most commonly used surrogate model in Bayesian optimisation. A comprehensive overview on GPs can be found in Rasmussen & Williams (2006). Below we highlight the concepts of marginal likelihood and how to use it for hyperparameter optimisation and model selection based on the notation introduced in Section 4.2
Hyperparameter tuning. The key finding the right hyperparameters 0* in light of D,-1 in principled way given by the marginal likelihood in Equation TTP..
exp K 1 (0) exp (- 1
p(Dr-1 (2m)
(10)
where have introduced slightly augmented notation of K (0)-1(0) highlight the dependence on the kernel hyperparamaters 0. In truly Bayesian approach, one could shy away from fixing one set of hyperparameters and use Equation (IO) to derive posterior distribution of based on one's 's prior beliefs about 0 expressed through some distribution (O)) However, as such an approach generally requires sampling using methods like Markov chain Monte Carlo (MCMC) due to intractability of integrals, in practice it is often easier and computationally cheaper to replace the fully Bayesian approach by maximum likelihood approach and simply maximise the likelihood p(D.-il0) w.r.t. 0. We follow this approach and perform mix of grid- and gradient based search to maximise the logarithm the r.h.s. of Equation 10). After evaluating a grid of 5'000 points, start gradient ascent each of the most promising points using the following equation for the gradient (Rasmussen & Williams 2006) to find the hyperparameters 0* which maximise the marginal likelihood:
15

---

Published as a conference paper at ICLR 2020
0 00;
1 T
1k
0K
log (Pi-110 2 Vi
k
KT
111-1911111
7t
K [
(11)
00;
00,
(KT1-191:t-11/
K (it-1)
(12)
08,
Model selection. Once the optimal hyperparameters 0 are found described above, they can be plugged back into Equation (10) to choose amongst different models. In Section 4.4 this is described for the case of choosing between different values of the reduced dimensionality d".
16


Reviews:
[{"review_id": "rye_muURtr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studied the problem of black-box adversarial attack generation by leveraging Bayesian optimization (BO).\n\nMerits of this paper:\n1) The combination of BO and dimension reduction, which makes BO more efficient under a low-dimensional space. \n2) Good experiment results.\n\nComments/questions about this paper:\n\n1) Comment on \"Finally, to the best of our knowledge, the only prior work that uses Bayesian optimisation is a workshop paper by...\". BO was also used for generating black-box adversarial examples at https://arxiv.org/pdf/1907.11684.pdf\nThis is a missing related work, and please elaborate on the differences. \n\n2) The presentation of the proposed algorithm is not clear. Please explicitly state the acquisition function. And how to tune the hyperparameter in the acquisition function? What decoder is used in experiments? Have authors tested the sensitivity of the decoder (not reduced dimension)?  \n\n3) In experiments, the authors mentioned \"we randomly select 3 correctly classified images for each class from CIFAR10 test data which sums up to 27 CIFAR10 images, and randomly select 7 correctly classified images from MNIST test data.\"\nI feel that the number of tested images is not sufficient. How about conducting experiments on a large number of tested images for untargeted attack?\n\n4) In Table 1, what does 0,0,0, mean in ZOO? \n\n5) It is known that BO has itself parameter to tune, and is not computationally efficient. It might be good to show the computation efficiency of BO for different reduced dimensions together with the corresponding attack performance. \n\n6) The convergence of BO is usually not stable. However, Figure 3 shows that BO converges very smoothly in terms of ASR. Could authors also show the loss value of using BO-attacks against iteration numbers? \nMeanwhile, in Figure 3 is the best ASR  (up to the current query counts) reported or the ASR at the current query number?\n\n\nBased on the aforementioned questions, my initial rating is weak reject. \n\n\n############## Post-feedback ################\nThanks for the response. Most of my questions have been addressed. Thus, I increased my score to 6. \nI suggested to have a clearer presentation on the possible pros and cons of BO in attack generation, e.g., making a comparison between BO and other methods in both query efficiency and computation efficiency.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJx2OHC2tS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "In this paper, the authors propose to use Bayesian optimization with a GP surrogate for adversarial image generation. In addition to the standard BayesOpt algorithm, the authors use a variant that exploits additive structure, as well as a variant that uses Bayesian model selection to determine an optimal dimensionality reduction.\n\nFor the experimental results, I find it extremely surprising that vanilla GP-BO works at all, even downsampling e.g. to d=588 (Table 2). This is extraordinarily high dimensionality for vanilla BayesOpt, and conventional wisdom suggests that this should not work at all. I'd like to see a discussion of this, particularly as I've seen unsuccessful attempts at this in the past. What differentiating factors lead to it working here? The set of images considered is quite small, presumably because of the rather extreme wall clock expense of running hundreds of sequential BayesOpt iterations without GPU acceleration. This is particularly true for methods that require Bayesian model selection and therefore training multiple GPs in each iteration of BayesOpt.\n\nAlong the same lines of dimensionality concerns, I would view a lack of results on ImageNet images as a significant weakness, particularly as these are probably much harder for general purpose blackbox optimizers, as the initial dimensionality of those images is ~150000. A decent amount of missing related literature studies transformations of ImageNet images, including the QL Attack (Ilyas et al., 2018), Bandits-TD (Ilyas et al., 2019) and others. These papers also focus specifically on query budget, so it would be hard to claim that BayesOpt is SOTA if it can't scale to images this large.\n\nCan you provide additional details on the learning mechanism for the additive decomposition? Are you learning kernel outputscales for different predefined additive components as in Duvenaud et al., 2011? Note that this is a fairly different structure than considered in Kandasamy et al., 2015 (despite both being called \"additive GPs\") -- the type of additive structure in Kandasamy et al., 2015 usually needs to be learned through approximate model selection mechanisms (usually via Metropolis-Hastings or Gibbs sampling).", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkxnc7g79r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 a black-box attack method that optimises both the adversarial perturbation and the optimal dimensionaity reduction in a Bayesian Optimization framework. The formulation seem sound and the experiments show improvements wrt competitors in terms of performance and query efficiency with comparable attack success rates.\n\n* In section 4.3 the authors claim that the additive surrogate makes the GP-based BO able to deal with the problem of high dimensionality. Given that the typical dimensionality for BayesOpt is d <= 20, how are the experiments with dimensions up to 14x14x3 provided for GP-BO and GP-BO-auto-dT performed?\n\n* The image selection protocol seems arbitrary and it does not correspond to the Tu et al. protocol which selects 50 random images from  CIFAR-100 and MNIST.\n\n* I feel the experiments lack some details: which is the decoder used for dimensionality reduction?\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a query-efficient black-box attack that uses Bayesian optimization in combination with Bayesian model selection to optimize over the adversarial perturbation and the optimal degree of search space dimension reduction. The method can achieve comparable success rates with 2-5 times fewer queries compared to previous state-of-the-art black-box attacks. The paper should be further improved in the final version (e.g., including more results on ImageNet data).
Decision: Accept (Poster)