Black-box Adversarial Attacks with Bayesian Optimization
Authors: Satya Narayan Shukla
Anit Kumar Sahu
Devin Willmott
J. Zico Kolter
Venue:  (2020)
Keywords: black-box adversarial attacks
bayesian optimization

Abstract: We focus on the problem of black-box adversarial attacks, where the aim is to generate adversarial examples using information limited to loss function evaluations of input-output pairs. We use Bayesian optimization (BO) to specifically
cater to scenarios involving low query budgets to develop query efficient adversarial attacks. We alleviate the issues surrounding BO in regards to optimizing high dimensional deep learning models by effective dimension upsampling techniques. Our proposed approach achieves performance comparable to the state of the art black-box adversarial attacks albeit with a much lower average query count. In particular, in low query budget regimes, our proposed method reduces the query count up to 80% with respect to the state of the art methods.

Under review as a conference paper at ICLR 2020
BLACK-BOX ADVERSARIAL ATTACKS WITH BAYESIAN OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We focus on the problem of black-box box adversarial attacks, where the aim is to generate adversarial examples using information limited loss function evalu- ations of input-output pairs. We use Bayesian optimization (BO) to specifically cater to scenarios involving low query budgets to develop query efficient adversar- ial attacks. We alleviate the issues surrounding BO in regards to optimizing high dimensional deep learning models by effective dimension upsampling techniques. Our proposed approach achieves performance comparable the state of the art black-box adversarial attacks albeit with a much lower average query count. particular, in low query budget regimes, proposed method reduces the query count up to 80% with respect to the state of the art methods.
INTRODUCTION
Neural networks are now well-known to be vulnerable to adversarial examples: additive perturba- tions that, when applied to the input, change the network's 's output classification (Goodfellow et al, 2014). Work investigating this lack robustness to adversarial examples often takes the form of back-and-forth between newly proposed adversarial attacks, methods for quickly and efficiently crafting adversarial examples, and corresponding defenses that modify the classifier at either train- ing or test time improve robustness. The most successful adversarial attacks use gradient-based optimization methods (Goodfellow et al.) [014|Madry et al. 2017). which require complete knowl- edge of the architecture and parameters of the target network; this assumption is referred as the white-box attack setting. Conversely, the more realistic black-box setting requires an attacker to find an adversarial perturbation without such knowledge: information about the network can be obtained only through querying the target network, i.e., supplying an input to the network and receiving the corresponding output.
In real-world scenarios, it is extremely improbable for an attacker to have unlimited bandwidth to query a target classifier. evaluation of black box attacks, this constraint usually formalized via the introduction of query budget: maximum number of queries allowed to the model per input, after which an attack is considered to be unsuccessful. Several recent papers have proposed attacks specifically operate in this query-limited context (Ilyas al., 2019 2018 Chen al.) 2017] Tu et al.) 2019] Moon et al.) 2019); nevertheless, these papers typically consider query budgets on the order of 10,000 100,000. This leaves open questions as to whether black-box attacks can successfully attack a deep network based classifier in severely query limited settings, e.g., with a query budget of 100-200. In such query limited regime, it is natural for attacker use the entire query budget, so we ask the pertinent question: In a constrained query limited setting, can one design query efficient yet successful black box adversarial attacks?
This work proposes black-box attack method grounded in Bayesian optimization (Jones et al. 1998 FFazzerr 2018), which has recently emerged as a state of the black-box optimization tech- nique in settings where minimizing the number of queries is of paramount importance. Straight- forward application of Bayesian optimization to the problem of finding adversarial examples is not feasible: the input dimension of even small neural network-based image classifier is orders of magnitude larger than the standard use case for Bayesian optimization. Rather, we show that we can bridge this gap by performing Bayesian optimization in to obtain our final perturbation. We explore several upsampling techniques and find that a relatively simple nearest-neighhor upsampling method allows to sufficiently reduce the optimization prob-
setting and upsampling

---

Under review as a conference paper at ICLR 2020
lem dimension such that Bayesian optimization can find adversarial perturbations with more success than existing black-box attacks in constrccod settings.
We compare the efficacy of our adversarial attack with set of experiments attacking three of the most commonly used pretrained ImageNet (Deng et al. 2009) classifiers: ResNet50 (He et al. 2013). Inception-v3 (Szegedy al. 2 and VGGI6-bn (Simonyan & Zisserman 2014). Results from these experiments show that with very small query budgets (under 200 queries), the proposed method BAYES-
achieves success rates comparable to or exceeding existing methods, and does so with far smaller average and median query counts. Further experiments are performed on the MNIST dataset to compare how various upsampling techniques affect the attack accuracy of our method. Given these results we argue that, despite being a simple approach (indeed, largely because it is such a simple and standard approach for black-bor optimization), Bayesian Optimization should be a standard baseline for any black-box adversarial attack task in the future, especially in the small query budget regime.
2 RELATED WORK
Within the black-box setting, adversarial attacks can be further categorized by the exact nature of the information received from a query. The most closely related work to our approach are score-basse based attacks, where queries to the network return the entire output layer of the network, either as logits or probabilities. Within this category, existing approaches draw from a variety of optimization fields and techniques. One popular approach in this area is to attack with zeroth-order methods via some method of derivative-free gradient estimation, as in methods proposed in llyas et al. (2019), which uses time- deeeddeenddntt and data- data-dependent priors to improve the estimate, as well as llyas et al. (2018), which replaces the gradient direction found using natural evolution strategies (NES). Other methods search for the best perturbation outside of this paradigm: [Moon et al.] (2019) cast the problem of finding an adversarial perturbation as discrete optimization problem and use local search methods to solve. These works all search for adversarial perturbations within a search space with a hard constraint on perturbation size; other work (Chen al.) 2017 Tu al., 2019) incorporates a soft version of this constraint and performs coordinate descent to decrease the perturbation size while keeping the perturbed image misclassified. The latter of these methods incorporates an autoencoder-
based upsampling method with which we compare in Section 5.3.1
One may instead assume that only part of the information from the network's 's output layer is received as the result of query. This can take the form of only receiving the output of the top A: predicted classes (Ilyas et al., 2018), but more often the restrictive decision-bused setting is considered. Here, queries yield only the predicted class, with no probability information. The most successful work in this area is in Cheng et al. (2018), which reformulates the problem as a search for the direction of the nearest decision boundary and solves using random gradient-free method, and in [Brendel et al. (0017) and/Chen et al. (2019), both of which use random walks along the decision boundary to perform attack. The latter work significantly improves over the former with respect to query effi- ciency, but the number of queries required to produce adversarial examples with small perturbations in this setting remains in the tens of thousands.
A separate class of transfer-based attacks train a second, fully-observable substitute network, attack this network with white-box methods, and transfer these attacks the original target network. These may fall into one of the preceding categories or exist outside of the distinction: in Papernot et al. 2016). the substitute model is built with score-based queries the target network, Lhe al. 2016) trains an ensemble of models without directly querying the network at all. These methods come with their own drawbacks: they require training a substitute model, which may be costly or time-consuming. and overall attack success tends to be lower than that of gradient-based methods.
Finally, there has been some recent interest in leveraging Bayesian optimization for constructing adversarial perturbations. Bayesian optimization (BO) has played a supporting role in several meth- ods. For example, Zhho et al. (2019) use BO to solve the 6-step of an alternating direction of method multipliers (ADMM) approach, Co et al. (2018) search within a set of procedural noise perturba- tions using BO and Gopakumar et al. 2018) use BO to find maximal distortion error by optimizing perturbations defined using 3 parameters. On the other hand, prior work in which Bayesian op- timization plays a central role performs experiments only in relatively low-dimensional problems, highlighting the main challenge of its application: Suya al. (017) examines attack on a spam
2

---

Under review as a conference paper at ICLR 2020
email classifier with 57 imput features, and in Co (2017) image classifiers are attacked but notably do not scale beyond MNIST classifiers. In contrast to these past works, the main contribution of this paper is to show that Bayesian Optimization presents scalable, querr- -heer-efficient approach for large-scale black-box adversarial attacks, when combined with upsampling procedures.
3 PROBLEM FORMULATION
The following notation and definitions will be used throughout the remainder the paper. Let be the target neural network. We assume that F: _ + [0. K is K-class image classifier that takes normalized inputs: each dimension of an input E _ represents a single pixel and is bounded between 0 and 1, y E f1. [1....]] K} denotes the original label, and the corresponding output F(x) is K K-dimensional vector representing probability distribution over classes.
Rigorous evaluation of an adversarial attack requires careful definition of threat model: set of formal assumptions about the goals, knowledge, and capabilities of an attacker (Carlini & Wagner 2017 We assume that, given correctly classified input image x, the goal of the attacker is find perturbation 5 such that x + 5 is misclassified, i.e., arg max, F(x + 6) * arg max, F(x). We operate in the score-based black-box setting, where we have no knowledge of the internal workings of the network, and query to the network I' yields the entire corresponding K -ddimensional out- put. To enforce the notion that the adversarial perturbation should be small, we take the common approach of requiring that |00lp be smaller than given threshold in some lp norm, where varies depending on the classifier. This work considers the to norm, but our attack can easily be adapted to other norms. Finally, denote the query budget with 6; if adversarial example is not found after t queries to the target network, the attack fails.
As in most work, we pose the attack as a constrained optimization problem. We an objective function suggested by Carlini & Wagner 2017) and used in Tu et al. (2019) Chen et al. (017)):
max f(x. y, 0) subject to ||ő||p S and (x + 5) E [0, 1], 8
(1)
where f(x, y. 8)
max log F(x + 8)] log [( 5)
kzy
Most importantly, the input + to f an adversarial example for F if and only if f(x, y; 6) 0.
We briefly note that the above threat model and objective function were chosen for simplicity and for ease of directly comparing with other black box attacks, but the attack method we propose is compatible with many other threat models. For example, we may change the goals of the attacker or measure 5 in & or & norms instead of foo with appropriate modifications to the objective function and constraints in equation
4 MODEL FRAMEWORK
In this section, we present the proposed black-box attack method. We begin with brief descrip- tion of Bayesian optimization (Jones et al. 1998) followed by its application to generate black-box adversarial examples. Finally, describe our method for attacking a classifier trained with high- dimensional inputs (e.g. ImageNet) in a query-efficient manner.
4.1 BAYESIAN OPTIMIZATION
Bayesian Optimization (BO) is a method for black box optimization particularly suited problems with low dimension and expensive queries. Bayesian Optimization consists of two main compo- nents: a Bayesian statistical model and acquisition function. The Bayesian statistical model, also referred to as the surrogate model, is used for approximating the objective function: it provides Bayesian posterior probability distribution that describes potential values for the objective function at any candidate point. This posterior distribution is updated each time we query the objective func- tion at a new point. The most common surrogate model for Bayesian optimization are Gaussian processes (GPs) (Rasmussen & Williams 2005), which define prior over functions that are cheap to evaluate and are updated as and when new information from queries becomes available. We model the objective function h using GP with prior distribution N (Po, En) with constant mean
3

---

Under review as a conference paper at ICLR 2020
function My and Matern kernel (Shahriari et al. 2016 Snoek et al. 2012) the covariance function Eo. which defined as:
Eo(x,x') = 0g exp(- (xp)- 1 var + 5 r²
d' (x, - x2/²²
y2
0g
where d' the dimension of input and {0.) J and μi are hyperparameters. We select hyperparam- eters that maximize the posterior of the observations under a prior (Shahriari et al. 2016 Frazier 2018).
The second component, the acquisition function A, assigns a value to each point that represents the utility of querying the model at this point given the surrogate model. We sample the objective function h at X, arg maxx so far. Although this itself may hard (non-convex) optimization problem solve, in practice use standard approach and approximately optimize this objective using the LBFGS algorithm. There are several popular choices acquisition function; we use expected improvement (EI) (Jones al. 1998), which is defined
where Di:n-1 comprises of n - samples drawn from
EI, (x) = E, [max (h(x) h 0)],
(2)
where En!:] P1-1Pim--1] denotes the expectation taken over the posterior distribution given eval- uations of h at X1, 1n and h is the best value observed so far.
Bayesian optimization framework as shown Algorithm 2 runs these two steps iteratively for the given budget of function evaluations. It updates the posterior probability distribution on the ob- jective function using all the available data. Then, it finds the next sampling point by optimizing the acquisition function over the current posterior distribution of GP. The objective function h is evaluated this chosen point and the whole process repeats.
In theory, we may apply Bayesian optimization directly to the optimization problem in equation [ to obtain an adversarial example, stopping once we find a point where the the objective function rises above O. In practice, Bayesian optimization's speed and overall performance fall dramatically as the input dimension of the problem increases. This makes running Bayesian optimization over high dimensional inputs such ImageNet (input dimension 3 x 299 x 299 268203) practically infeasible; we therefore require a method for reducing the dimension of this optimization problem.
4.2 BAYES-A GENERATING ADVERSARIAL EXAMPLES USING BAYESIAN OPTIMIZATION
Images tend to exhibit spatial local similarity i.c. pixels that are close to each other tend to be similar. [īlys et al. (2019) showed that this similarity also extends to gradients and used this to reduce query complexity. Our method uses this data dependent prior to reduce the search dimension of the perturbation. We show that the adversarial perturbations also exhibit spatial local similarity and we do not need to learn the adversarial perturbation conforming to the actual dimensions of the image. Instead, we learn the perturbation in a much lower dimension. We obtain our final adversarial perturbation by interpolating the learned, low-dimension perturbation to the original input dimension.
We define the objective function for running the Bayesian optimization in low dimension in Algo- rithm [] We let IT B(o..) be the projection onto the lx ball of radius centered at origin. Our method finds low dimension perturbation and upsamples to obtain the adversarial perturbation. Since this upsampled image may not lie inside the ball of radius e centered the origin, we project back to ensure ||o]| remains bounded by With the perturbation 8 in hand, we compute the objective function of the original optimization problem defined in equation [
We describe the complete algorithm our complete framework in Algorithm 2 where E Rd and No E {1, .., K} denote the original input image and label respectively. The goal is to learn an adversarial perturbation ò E Rdd much lower dimension, i.c., d' << d. We begin with a small dataset D ((01, U1); .n),.... (ōng Ung)) ) where each 5,, is a d' dimensional vector sampled from
4

---

Under review as a conference paper at ICLR 2020
Algorithm Objective Function
1: procedure OBI-FUNC(Xo,) No. d)
2: e the given perturbation
3: 8' < Upsample(d)
Upsampling low dimension perturbation imput dimension
4: 8' < (o,c)) 8')
Projecting perturbation on ly b--ball around zo Quering the model
5: 4- f(xo, No. 8')
6: return v
Algorithm 2 Adversarial Attack using Bayesian Optimization
1: procedure BAYES-ATTACKIS
yo) D (=((61, {()1,1)), v1),.... ...., (. [no}}
2:
Quering randomly chosen no points. Updating posterior distribution using available points
3: Update the GP on
4:
f rip
> Updating number of queries till now
5:
while S T do
6:
5; f- arg max, A(6 D) 1; f OBI-FUNC(XO,... 1/o
b. Optimizing the acquisition function over the GP P Querying the model
7:
8:
[ f ++1
9:
if 1/ < 0 then
10:
D DU (ōz, vx) and update the GP
> Updating posterior distribution
else
12:
return 5
Adversarial attack successful
13:
return d;
Adversarial attack unsuccessful
given distribution and e. is the function evaluation at 6n i.e on OBJ-FUBC(XX (Xp, yo. 6n). We itera- tively update the posterior distribution of the GP using all available data and query new perturbations obtained by maximizing the acquisition function over the current posterior distribution of GP until of query budget. The Bayesian optimization iterations run in low dimension d' but for querying the model we upsample, project and then add the pertur- bation the original image as shown Algorithm [ to get the perturbed image to conform the input space of the model. To generate a successful adversarial perturbation, it is necessary and suf- ficient have 1/ > 0, as deseribed in Section 3 We call our attack successful with queries to the model if the Bayesian optimization loop exits after t iterations (line 12 in Algorithm 2 otherwise it unsuccessful. Finally, we note that the final adversarial image can be obtained by upsampling the learned perturbation and adding the original image as shown in Figure]]
find an adversarial perturbation
In this work, we focus on lo -nrm perturbations, where projection is defined as:
P(xo. (x) min (max - x,x),x0 +
where e is the given perturbation bound. The upsampling method can be linear or non-linear. In this work, conduct experiments using nearest neighbor upsampling. A variational autoencoder (Kingma & Welling 2014) or vanilla autoencoder could also be trained to map the low dimension perturbation the original input space. We compare these different upsampling schemes in Sec- tion 5.3.1 The initial choice of the dataset D to form a prior can be done using standard normal distribution, uniform distribution or even in a deterministic manner (e.g. with Sobol sequences).
EXPERIMENTS
Our experiments focus on the untargeted attack setting where the goal perturb the original image originally classified correctly by the classification model to cause misclassification. We primarily consider performance of BAYES-ATTAS other black-box attacks in terms of success rate studies on the MNIST dataset (Lecun et al., 1998) by examining different upsampling techniques and varying the latent dimension d' of the optimization problem.
on ImageNet classifiers and compare its performance to given query budget. We also perform ablation
We define success rate as the ratio of the number of images successfully perturbed for a given query budget to the total number of input images. In all experiments, images that already misclassified
5

---

Under review as a conference paper at ICLR 2020
Upeampling
X 0.1
12
10
Low-dimension perturbation
Adversurial perturbation
Original Image white
Final adversarial image Label: curtain
Figure An illustration of black-box adversarial attack performed by the proposed method DAYES-ATTACE on RESNET50 trained on ImageNet. Images from the left: first figure shows the learnt perturbation low dimension d' (72
18); second figure is the final adversarial perturbation (3 x 224 x 224) obtained by using nearest neighbor upsampling; third figure is the original image (note that the input size for REsNET50 is 224 224) which is initially classified as white/arctic wolf; last image is the final adversarial image obtained by adding the adversarial per- turbation to the original image. RESNET50 classifies the final adversarial image as shower curtain with high probability.
by the target network are excluded from the test set; only images that are initially classified with the correct label are attacked. For each method of attack and each target network, we compute the average and median number of queries used to attack among images that were successfully perturbed.
5.1 EMPIRICAL PROTOCOLS
We treat the latent dimension d' used for running the Bayesian optimization loop hyperparam- eter. For MNIST, we tune the latent dimension d' over {16, 64, 100, 256, 784]. Note that 784 is the original input dimension for MNIST. While for ImageNet, we search for latent dimension d' and shape over the range (48(3 x x 4), 49(1 x 7 x 7). 100(1 x 10 x 10), 108(3 x 6 x 6), 400(1 x 20 x 20), 432(3 12x x 12), 576(1 24 x 24), 588(3 x 14 14), 961(1 x 31 31). 972 ImageNet, the latent shapes with first dimension all three channels while the ones with 3 indicate that perturbation across channels are different. found that for ResNet50 and VGG16-bn different perturbation across chan-
18)]. For indicate that the same perturbation is added to
In case of ImageNet, nels work much better than adding the same perturbation across channels. While for Inception-v3, both seem work equally well.
We initialize the GP with no = 5 samples sampled from a standard normal distribution. For all the experiments in next section, examined other acquisition functions (posterior mean, probability of improvement, upper confidence bound) and observed that method works equally well with other acquisition functions. We independently tune the hyper-parameters on a small validation set and exclude from our final test We used @oTTore""acckae for implementation.
expected improvement the acquisition function. We also
5.2 EXPERIMENTS ON IMAGENET
We compare the performance of the proposed method BAYES-ATTACE against NES (Ilyas al. 2018), BANDITS-TD (Ilyas et al. 2019) and PARSIMONIOUS (Moon et al. 2019). which is the current state of the among based black-box attacks within the E threat model. On Ima- geNet, we attack the R (He et al. 2015), Inception-v3 (Szegedy et al. 2015 and VGG16-bn (Simonyan & Zisserman 2014). We use 10,000 randomly selected images (normalized to [0, 1]) from the ImageNet validation set that were initially correctly classified.
We the too perturbation bound to 0.05 and evaluate the performance of all the methods for low query budgets. We use the implementation and hyperparameters provided by llyas et al. (209 for
https: stttps://botorch.oo org/
PPeetrained available at httplcaatttttsttttot htt.://awwttaa//////o//o//////aa

---

Under review as a conference paper at ICLR 2020
PayessAttace
Parsimonious
Bandits_TP TD
NES
80
80
30
Success rate
60
Success
20
20
20
100
200
300
400
500
300
200
300
400
500
300
200
300
400
500
Query Budget
Query Budget
Query Budget
(a) RESNET50
(b) INCEPTION-V3
(c) VGGI6-BN
Figure 2: Performance comparison for foo untargeted attacks on ImageNet classifiers. BAYES- ATTACK consistently performs better for low query budgets (< 200). Note that for NES, model queries performed in batches of 100 specified in [lyas al. (2018).
Table I: Results for too untargeted attacks on ImageNet classifiers with query budget of 200
SUCCESS RATE
AVERAGE QUERY
MEDIAN QUERY
CLASSIFIER
METHOD
NES
15.20%
152
200
BANDITS-TD
56.59%
44
20
RESNET50
PARSIMONIOUS
72.26%
79
73
BAYES-ATTAGE
74.16%
17
6
NES 20.27%
152
200
BANDITS-TD. 66.44%
40
16
INCEPTION-V3
PARSIMONIOUS
70.75%
80
73
MAYES-ATTACK
81.60%
13
NES
16.41%
152
200
BANDITS-TD 62.10%
45
20
VGG16-BN
PARSIMONIOUS 60.16%
84
74
BAYES- ATTACK
62.95%
22
NES and BANDITS-TD. Similarly for PARSIMONIOUS, we use the implementatior and hyperpa- rameters given by MMon et al. (2019).
Figure compares the performance of the proposed method BAYES-ATTACK against the set of base- line methods terms of success rate at different query budgets. We can see that LAYRS-ATTACK consistently performs better than bascline methods for query budgets 200. Even for query bud- achieves better success rates than BANDITS-TU and NES on ResNet50 and 1-GG16-b.. Finally, note that for higher query budgets (> 1000), both PARSIMONIOUS and BANDITS-TD method perform better than BAYES-ATTACK.
gets 200,
To compare the success rate and average/median query, select point the plots shown in Figure 2 Table Table|[ommprce the performance all the methods in terms of success rate, average and median query for query budget of 200. We
that BAYES-ATTACE achieves higher success rate with 80% less average queries as compared to the next best PARSIMONIOUS method. Thus, argue that although the Bayesian Optimization adversarial attack approach to some extent a "standard" application of traditional Bayesian Optimization methods, the performance over the existing state of the makes it compelling approach particularly for the very low query setting. We also compare the average & distortion of the generated ad adversarial perturbations in Appendix B
https://github. watp:/ummmaaaaaaaaaaaaaaam ous-b1 accbbxckkxxaao attack

---

Under review as a conference paper at ICLR 2020
70
70-
Success rate
50
Success rate
40
VAS, dim-16
40
VAE, dim-32
MR.
VAE,
MN.
AE, dim-32
MN. dim-64 64
MN, dim=11 16
MR, dim= 100
10
BIC,
10
dim-233
Bil, dm-16 16
MN, dim- 784
0
100
200
300
400
500
100
200
300
400
500
Query Budget
Budget
(a) Performance comparison with different upsam- (b) Performance comparison with different latent di- pling schemes.
mension.
Figure 3: Lo untargeted attacks on MNIST. dim: latent dimension used to run the Bayesian opti- mization, NN: Nearest neighbor interpolation, BiC: Bicubic interpolation, BiL: Bilinear interpola- tion, AE: autoencoder- based decoder, VAE: VAE-based generator (or decoder)
5.3 EXPERIMENTS ON MNIST
For MNIST, we use the pretrained network (used in Carlini & Wagner 2017 with 4 convolu- tional layers, 2 max-pooling layers and 2 fully-connected layers which achieves 99.5% accuracy on MNIST set. We conduct foo untargeted adversarial attacks with perturbation bound 0.2 on randomly sampled 1000 images from the test set. All the experiments performed on MNIST follow the same protocols.
5.3.1 UPSAMPLING METHODS
The proposed method requires an upsampling technique for mapping the perturbation learnt in the latent dimension the original input dimension. this section, examine different linear and non-linear upsampling schemes and compare their performance on MNIST. The approaches we con- sider here can divided into two broad groups: Secoder-Decodde based methods and Interpolation methods. For interpolation-bust based methods, we consider wearest-neighbor bilinear and bicubic in- terpolation.
For encoder-decoder based approaches, we train a variational autoencoder (Kingma & Welling 2014 Rezende al., 20144) by maximizing a variational lower bound on the log marginal likelihood. We also consider simple autoencoder trained by minimizing the mean squared loss between the generated image and the original image. For both approaches, we run the Bayesian optimization loop in latent space and use the pretrained decoder (or generator) for mapping the latent vector into image space. For these approaches, rather than searching for adversarial perturbation the latent space, we learn the adversarial image + ô directly using the Bayesian optimization.
Figure 3a compares the performance of different upsampling methods. We can see that Nearest Neighbor (NN) interpolation and VAE-based decoder perform better than rest of the upsampling schemes. However, the NN interpolation achieves similar performance to the VAE-based method but without the need of large training dataset which is required for accurately training VAB- based decoder.
5.3.2 LATENT DIMENSION SENSITIVITY ANALYSIS
We perform a sensitivity analysis on the latent dimension hyperparameter d' used for running the Bayesian optimization. We vary the latent dimension over the range E (9, 16, 64, 100, 256, 784). Figure 3b shows the performance of nearest neighbor interpolation method for different latent di- mension. We observe that lower latent dimensions achieve better success rates than the original input dimension d' 784 for MNIST. This could be because with increase in search dimension, Bayesian optimization needs more queries to find successful perturbation. We also note that for the case of latent dimension d' 9, BAYES-ATTACK achieves lower success rates which could mean
8

---

Under review as a conference paper at ICLR 2020
that it is hard to find adversarial perturbations in such low dimension. We show the convergence plots of AATACK on ImageNet and MNIST in Appendix A
CONCLUSIONS
We considered the problem of black-box adversarial attacks settings involving constrained query budgets. We employed Bayesian optimization based method to construct query efficient attack strategy. The proposed method searches for an adversarial perturbation in low dimensional latent space using Bayesian optimization and then maps the perturbation to the original input space using the nearest neighbor upsampling scheme. We successfully demonstrated the efficacy our method in attacking multiple deep learning architectures for high dimensional inputs. Our work opens enues regarding applying BO for adversarial attacks in high dimensional settings.
REFERENCES
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-basee adversarial attacks: Reliable attacks against black-box machine learning models. arXiv preprint arXiv:1712.04244 2017.
N. Carlini and D. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57, May 2017. doi: 10.1109/SP.2017.49.
Jianbo Chen, Michael I. Jordan, and Martin J. Wainwright. Hopskipjumpattack: A query-efficient decision-based attack. arXiv preprint arXiv: 02144, 2019.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth der optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, AISec '17, pp. 15-26, New York, NY. USA, 2017. ACM. ISBN 978-1-4503-5202-4, doi: 10.11455/128552.34444444
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, and Cho-Jui Hsieh. Query- efficient hard-label black-box attack: An optimization-baase approach. arXiv preprint
arXiv:1807.04457. 2018.
Kenneth Co. Bayesian Optimization for Black-Bo Box Evasion of Machine Learning Systems. PhD thesis, Imperial College London, 2017.
Kenneth T Co, Luis Muñoz-Gonzále and Emil C Lupu. Procedural noise adversarial examples for black-box attacks on deep neural networks. arXiv preprint arXiv: 2018.
Deng, Dong, R. Socher, L.-J. Li. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
Peter I. Frazier. A tutorial on bayesian optimization. ArXiv,
2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint urXiv:1412.6575 2014.
Shivapratap Gopakumar, Sunil Gupta, Santu Rana, Vu Nguyen, and Svetha Venkatesh. Algorithmic assurance: An active approach algorithmic testing using bayesian optimisation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31. pp. 5465-5473. Curran Associates, Inc., 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. 2016 IEEE Conference on Computer Vision and Patlern Recognition (CVPR), pp. 770- 778. 2015.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In Jennifer Dy and Andreas Krause reds.). Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2137-2146, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018 PMLR.

---

Under review as a conference paper at ICLR 2020
Andrew Ilyas, Logan Engstrom, and Aleksander Madry. Prior convictions: Black-box adversarial attacks with bandits and priors. In International Conference on Learning Representations, 2019.
Donald R. Jones, Matthias Schonlau, and William J. Welch. Efficient global optimization of ex- pensive black-box functions. J. of Global Optimization, 13(4):455 442, December 1998. ISSN 0925-5001. doi: 10.1023/A11008836441144
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Yann Lecun, Lon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, pp. 2278-2322 1998.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial exam- ples and black-box attacks. arXiv preprint arXiv: 2016.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0660 2017.
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 4636-4645, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Nicolas Papernot, Patrick D. McDaniel, Ian J. Goodfellow, Somesh Jha, Z. Berkay Celik, and Anan- thram Swami. Practical black-box attacks against machine learning. CoRR, abs/1602.02297,
2016.
Carl Edward Rasmussen and Christopher Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005. ISBN 086218253X.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. arXiv preprint arXiv: arXiv:1401.44 4082, 2014.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan Adams, and Nando Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104:148- 175, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition, 2014. cite arxiv: Mxxiv:1409.1555
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 2951-2959 Curran Associates, Inc., 2012.
Fnu Suya, Yuan Tian, David Evans, and Paolo Papotti. Query-limited black-box attacks to classifiers arXiv preprint arXiv: 171.v:1112.08/1111 2017.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2818-2826, 2015.
Chun-Chen Tu, Pai-Shun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang. Jinfeng Yi, Cho-Jui Hsich, and Shin-Ming Cheng. Autozoom: Autoencoder-based zeroth order optimization method for attack- ing black-box neural networks. In The Thirty-Thire AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February I, 2019., pp. 742-749, 2019.
Pu Zhao, Sijia Liu, Pin-Yu Chen, Nghia Nguyên Hoång, Kaidi Xu, Bhavya Kailkhura, and X Cai Lin. On the design of black-box adversarial examples by leveraging gradient-free optimization and operator splitting method. ArXiv, abs/1907. 2019.
10

---

Under review as a conference paper at ICLR 2020
A CONVERGENCE OF BAYESIAN OPTIMIZATION
In this section, we show the convergence of Bayesian Optimization (BO) in terms of objective value versus the number of queries. Note that we have framed our objective of finding adversarial perturbation to be maximization problem and we stop the iteration loop of BO once the objective value reaches a positive value. positive objective value corresponds successful adversarial perturbation as described in Section 3.
Figure f shows the convergence objective function the BAYES-ATTACK on RESNET50 trained on ImageNet as described in Section 5.2. We run the BO in 972 dimensions (3 x 18 x 18) and upsample the perturbation to the original input dimension 150, 528(3 x24 224). The plot shows ten randomly chosen images from the validation set, with different colors representing different
images.
2
Objective Function
-2
-4
25
50
75
100
125
150
Number of Queries
Figure 4: Convergence graphs on RESNET50 trained on ImageNet
We also show the convergence of the BO on MNIST by varying the latent dimension. Specifically, compare the convergence with latent dimension 16(4 4) and the original input dimension 784(28 x 28). The plot is shown in Figure 5 Each color represents test image, while dashed lines and solid lines represent runs of BO using 16 and 784 dimensions, respectively. As we can see from the graph, BO in 784 dimensions does not converge to successful attack (i.e., objective value 0) 500 iterations on either of the images, while BO with 16 dimensions on the same images finds the adversarial perturbation in less than 200 iterations. This aligns with our observation that with increase in latent dimension, it becomes harder for BO to find successful perturbation and indeed would require much more queries than rumning BO in lower dimensions.
Objective Function
Example dimm16
Example dim- 784
500
Number of Queries
Figure 5: Convergence graphs MNIST
B DISTORTION EFFICIENCY
We compare the average & distortion per image of the proposed method BAYES-ATTACK with the current state-of-the-an methods including gradient-based approaches RESNET50 trained
11

---

Under review as a conference paper at ICLR 2020
ImageNet. We fix the query budget at 200 similar to the experiments described in Section 5.2 and compute the distortion using only the successful adversarial perturbations. As we can see from Table the & distortion of adversarial examples generated using BAYES-ATTAN is almost similar to the current state-of-the-art methods but achieves better attack success rate in low query budget regimes. Having said that, in BANDITS-TD (llyas al. 2019) and PARSIMONIOUS (Moon al., 2019), our approach focuses on finding successful adversarial perturbations subject to a pre-defined maximum distortion specified in terms of Lo distance.
Table 2: Average l distortion of adversarial examples generated for lo untargeted attacks on RESNET50 trianed on ImageNet.
SUCCESS RATE
AVERAGE l DISTORTION
METHOD
BANDITS-TD
18.65 56.59%
PARSIMONIOUS
72.26%
19.40
74.16%
19.14
12


Reviews:
[{"review_id": "rylgel1fYr", "reviewer": "AnonReviewer2", "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": "The paper presents an idea on making adversarial attack on deep learning model. Since the space of input-output for the adversarial attach is huge, the paper proposes to use Bayesian optimization (BO) to sequentially select an attack.\n\nAlthough the potential application of adversarial attack on deep learning model is interesting, the paper contribution and the novelty are limited giving the fact that there is another related paper published [1].\n\nThe authors in [1] consider using Bayesian optimization to make adversarial attack for model testing. In particular, they have considered the deep learning model. Then, they extend to multi-task settings. There is a big overlapping between the idea in [1] and the current paper.\n\nThe paper presentation and writing is high quality although the paper is a bit over-length.\n\n[1] Gopakumar, Shivapratap, et al. \"Algorithmic assurance: an active approach to algorithmic testing using Bayesian optimisation.\" Advances in Neural Information Processing Systems. 2018.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "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."}, "extra_text": {}}, {"review_id": "rkgOQMOAtS", "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 proposed a BO-based black-box attack generation method. In general, it is very well written and easy to follow. The main contribution is to combine BO with dimension reduction, which leads to the effectiveness in generating black-box adversarial examples in the regime of limited queries.  However, I still have some concerns about this paper. \n\n1) The benefits of BO? It seems that the step of dimension reduction is crucial to make BO scablable to high-dimensional problems. I wonder if the gradient estimation-based attack methods can apply the similar trick and yield the similar performance. That is, one can solve problem min_{\\delta} attack_loss( x, y, g(\\delta) ) by estimating gradients via finite-difference of function values, where g(\\cdot) is the dimension-reduction operator, and \\delta is the low-dimensional perturbation. Such a baseline is not clear in the paper, and the comparison with (Tu et al., 2019) is not provided in the paper. \n\n2) Moreover, in experiments, it seems that only query-efficiency was reported. What about distortion-efficiency for BO-based attack? For $\\ell_\\infty$-attacks, the other $\\ell_p$ norms can be used as distortion metrics. I wonder what perturbation does the BO method converge to. It was shown in (https://arxiv.org/pdf/1907.11684.pdf, Table 1) that BO usually leads to larger \\ell_1 and \\ell_2 distortion. \n\n3) It might be useful to show the convergence of BO in terms of objective value versus iterations/queries. This may give a clearer picture on how BO works in the attack generation setting. \n\n4) Minor comment: In related work \"Bayesian optimization has played a supporting role in several methods,\nincluding Tu et al. (2019), where ....\" However,  Tu et al. (2019) does not seem using BO and ADMM. \n\n############ Post-feedback ##########\nThanks for the clarification and the additional experiments. I am satisfied with the response, and have increased my score to 6.\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": "HyljiA_RFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 applies Bayesian optimisation (BO), a sample efficient global optimisation technique, to the problem of finding adversarial perturbation. First, the application is starightforward application of BO to the well-known problem of adversarial perturbation. Nothing innovative. Second, the paper addresses the high dimensional optimisation with simple upsampling technique like nearest-neighbour, without even trying their hands dirty by using one of many many high-dimensional Bayesian optimisation algorithm (a quick Google search will reveal them), The work  thus fail in thoroughness also. Third, adversarial perturbation are known to exist even around the image such that even a simple gradient descet optimisation starting from the target image would be able to provide perceptually small perturbation (it does not have to the smallest to be perceptually small). Hence, the impact is also missing. Thus accroding to me this paper is not good enough for acceptance. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a Bayesian optimization approach to creating adversarial examples. The general idea has been in the air for some years, and over the last year especially there have been a number of approaches using BayesOpt for this purpose. Reviewers raised concerns about differences between this approach and related work, and practical challenges in general for using BayesOpt in this domain (regarding dimensionality, etc.). The authors provided thoughtful responses, although some of these concerns still remain. The authors are encouraged to address all comments carefully in future revisions, which a sufficiently substantial that the paper would benefit from additional review.



Decision: Reject