Title: BAYESOPT ADVERSARIAL ATTACK

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 1 can achieve comparable success rates with 2-5 times fewer queries compared to previous stateof-the-art black-box attacks.

1. INTRODUCTION:

Deep learning algorithms are widely deployed in many real-world systems and are increasingly being used for tasks, ranging from identity verification (Liu et al., 2018) , to financial services (Heaton et al., 2017) to autonomous driving (Bojarski et al., 2016) . However, even the most accurate deep learning models can be easily deceived by perturbations which are visually imperceptible to the human eye (Szegedy et al., 2013; Carlini et 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 are whitebox approaches that assume full access to the target model architecture and the ability of performing back-propagation to get gradient information (Moosavi-Dezfooli et al., 2016; Kurakin et al., 2016; Gu & Rigazio, 2014; Goodfellow et al., 2014; Chen et al., 2018; Carlini & Wagner, 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 a 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 estimate the gradient of the target model by repeatedly querying it (Chen et al., 2017; Ilyas 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 an excessively large query budget to achieve a successful attack (Alzantot et al., 2018) . Another line of work removes the need for gradient estimation and uses decision-based techniques (Brendel et al., 2017) or genetic algorithms (Alzantot et al., 2018) to generate adversarial examples. One popular technique that is adopted by many black-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-dimensional 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 a query efficient black-box attack that iteratively optimises over both the adversarial perturbation and the effective dimensionality of the latent search space. Our main contributions are summarised as follows:

• We introduce a novel gradient-free black-box attack method, BayesOpt attack, which uses Bayesian optimisation with Gaussian process surrogate models to find the effective adversarial example and is capable of dealing with high-dimensional image inputs.

• We proposes a Bayesian technique which learns the optimal degree of search dimensionality reduction by harnessing 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 L ∞ constraint, our proposed attack method can achieve comparable success rate with about 2 to 5 times fewer model queries in comparison to current state-of-the-art query-efficient black box attack methods.

2. RELATED WORK ON BLACK-BOX ATTACKS:

Most of the existing adversarial attacks (Moosavi-Dezfooli et al., 2016; Kurakin et al., 2016; Gu & Rigazio, 2014; Goodfellow et al., 2014; Chen et al., 2018; Carlini & Wagner, 2017) (Papernot et al., 2017) , which mimics the classification behaviour 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 to 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 classification performance on the same data (Szegedy et al., 2013) . Moreover, to provide training data for the substitute model, the adversary either requires information on the target model's training set, which is highly unrealistic in real-world applications, or needs to build a synthetic training set by querying the target model (Papernot et al., 2017) , which implies a large number of model evaluations and becomes hardly feasible for large models or 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-wise gradient estimation requires excessive queries to the target model (2 queries per coordinate per descent/attack step) and thus is not feasible for attacking models with high dimensional inputs (e.g. classifiers on ImageNet). Chen et al. (2017) overcome this limitation by using stochastic coordinate gradient descent and selecting the batch of coordinates via importance sampling, introducing the state-of-the-art zeroth-order attack, ZOO, which achieves comparable attack success rate and perturbation costs as many white-box attacks. Although ZOO makes it computationally tractable to perform black-box attack on high-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 perturbation cost. More importantly, AutoZOOM shows the benefits of employing dimension reduction techniques in accelerating attacks (i.e. searching for adversarial perturbation in a low-dimensional latent space and decoding it back to the high-dimensional input space). Parallel work by Ilyas et al. (2018) estimate the gradient through a modified version of natural evolution strategy which can be viewed as a finite-difference method over a 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 an excessive number of queries to achieve successful attack. Moreover, their dependence on the gradient information makes them less robust to 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-art query efficiency, is GenAttack (Alzantot et al., 2018) . GenAttack uses genetic algorithms to iteratively evolve a population of candidate adversarial examples. Besides having an annealing scheme for mutation rate and range, GenAttack also adopts dimensional reduction techniques, similar to AutoZOOM, to improve the query efficiency. In parallel to GenAttack, Brendel et al. (2017) introduce a decision-based attack, 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 et 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 optimisation 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.

3. 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 on all C classes (i.e. f : R d -→ [0, 1] C ) (Tu et al., 2018; Alzantot et al., 2018) . Moreover, we aim to perform targeted attacks, which is more challenging than untargeted attacks, subject to a constraint on the maximum change to any of the coordinates (i.e., a L ∞ constraint) (Warde-Farley & Goodfellow, 2016; Alzantot et al., 2018) . Specifically, targeted attacks refer to the case where given a valid input x origin of class t origin (i.e. arg max i∈{1,...,C} f (x origin ) i = t origin ) and a target t = t origin , we aim to find an adversarial input x, which is close to x origin according to the L ∞ -norm, such that arg max i∈{1,...,C} f (x) i = t.

Untargeted adversarial attacks refer to the case that instead of classifying x origin as t origin , we try to find an input x so that arg max i∈{1,...,C} f (x) i = t origin .

In our approach, we follow the convention to optimise over the perturbation δ instead of the adversarial example x directly (Chen et al., 2017; Alzantot et al., 2018; Tu et al., 2018) . Therefore, our problem can be formulated as:

arg max i∈{1,...,C} f (x origin + δ) i = t s.t. δ ∞ ≤ δ max (1)

3.2. BAYESIAN OPTIMISATION:

Bayesian optimisation (BayesOpt) is a query-efficient approach to tackle global optimisation problems (Brochu et al., 2010) . It is particularly useful when the objective function is a 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 acquisition function α(•) which is maximised to recommend the next query location by trading off exploitation and exploration (see Algorithm 3 in Appendix A for standard BayesOpt).

4. BAYESOPT ATTACK:



4.1. BAYESOPT ATTACK OBJECTIVE:

It has been shown that reducing the dimensionality of the search space in Equation ( 1) 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 our surrogate model needs to be trained with a very small number of observation data, we adopt the previously suggested dimensionality reduction technique, bilinear resizing, to reduce the challenging problem of optimising over high-dimensional input space of x ∈ R d to one over a relatively low-dimensional input space, setting x = x origin + g(δ) where δ ∈ R d r with d r < d and g : R d r -→ R d being the bilinear resizing decoder2 .

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 et al., 2018) . Together with the dimensionality reduction, this leads to the following blackbox objective problem for our Bayesian optimisation:

δ * = arg max δ y(δ) s.t. δ ∈ [-δ max , δ max ] d r (2)

where

y(δ) =   log f (x origin + g(δ)) t -log C j =t f (x origin + g(δ)) j   4.2 GP-BASED BAYESOPT ATTACK

We first use BayesOpt with a standard GP as the surrogate to solve for the black-box attack objective in the reduced input dimension in Equation ( 2). The GP encodes our prior belief on the objective y :

EQUATION

which is specified by a mean function µ and a kernel/covariance function k (we use the Matern-5/2 kernel in our work). In our work, we normalise the objective function value and thus use a zeromean prior µ(•) = 0. The predictive posterior distribution for y t at a test point δ t conditioned on the observation data D t-1 = {δ i , y i } t-1 i=1 = {δ 1:t-1 , y 1:t-1 } then has the form:

EQUATION

where

EQUATION

EQUATION

)

where

K 1:t-1 = K(δ 1:t-1 , δ 1:t-1 ) is the t -1 × t -1 matrix with pairwise covariances k(δ l , δ m ), l, m ≤ t -1 as entries.

The optimal GP hyper-parameters θ * such as the length scales and variance of the kernel function k can be learnt by maximising the marginal likelihood p(D t-1 |θ) which has analytic form as presented in Appendix F. Please refer to (Rasmussen, 2003) for GPs.

Based on the predictive posterior distribution, we construct the acquisition function α(δ|D t-1 ) to help select the next query point δ t . The acquisition function can be considered as a utility measure which balances the exploration and exploitation by giving higher utility to input regions where the functional value is high (high µ y ) and where the model is very uncertain (high k y ). The approach of using BayesOpt with a GP surrogate to attack the target model is described in Algorithm 1. Select δ t = arg max α t (δ|D t-1 )

5:

y t = y(δ t ) and D t ← D t-1 ∪ (δ t , y t ) 6:

Update the surrogate model with D t 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 original image size (e.g. d = 3072 for CIFAR10 image) to a much lower dimension (e.g. d = 192), the reduced search space for the adversarial attack is still considered very high dimensional for GP-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 is highdimensional, estimating it with non-parametric regression becomes very difficult because it is impossible to densely fill the input space with finite number of sample points, even if the sample size is very large (Györfi et al., 2006) . The second challenge is the computational difficulty in optimising the acquisition function. The computation cost needed for optimising the acquisition function to within a 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:

y(δ) = M j=1 y (j) (δ (Aj ) ) (7)

where δ (Aj ) denotes disjoint low-dimensional subspaces, δ = ∪ M j=1 δ (Aj ) and δ (Aj ) ∩ δ (Ai) = ∅ for all j = i. If we impose a GP prior for each y (j) , the prior for the overall objective y is also a GP:

y ∼ GP(µ(δ), k(δ, δ )) where µ(δ) = Algorithm 2 Bayesian selection of d r 1: Input: A decoder g(•), observation data D d t-1 = {g(δ i ), y i } t-1 i=1

where g(δ i ) ∈ R d and a set of possible d r : {d r j } N j=1 2: Output: The optimal reduced dimension d r * and the corresponding GP model 3: for j = 1, . . . , N do 4:

D d r j t-1 = {g -1 (g(δ i )) , y i } t-1 i=1 where g -1 (g(δ i )) ∈ R d r j 5:

Fit a GP model to D ) and its correspond GP model as perturbation costs while finding a good d r by trial and error or progressive increasing is computationally expensive and highly inefficient because the optimal d r varies with different attack input x origin . An effective way of learning d r is thus very important for adversarial attacks. In this section, we propose a rigorous method, which is neatly compatible with our attack technique, to learn the optimal d r from the query information.

The optimal d r should be the one that both takes into consideration our prior knowledge on the discrete d r choices and at the same time best explain the observed query data. Given that our BayesOpt attack uses a statistical surrogate (i.e. GP in our case) to model the unknown relation between the attack objective score y and the adversarial perturbation δ, this naturally translates to the criterion of maximising the posterior for d r :

EQUATION

where p(D t-1 |d r j ) is the marginal likelihood (evidence) of adopting a specific d r j , p(d r j ) is our prior over the possible d r values and p(D t-1 ) = i p(D t-1 |d r j )p(d r j ) is a normalising constant. If we match different d r j to different model choice, the problem of choosing d r then becomes the classic Bayesian model selection task (Rasmussen, 2003) . In most cases, our prior assumption is that we do not prefer one d r over another (i.e. flat prior p(d r j ) = p(d r i ) for j = i) and thus we can select d r by comparing their evidence (MacKay & Mac Kay, 2003) :

EQUATION

)

The exact computation of the evidence term requires marginalisation over model hyper-parameters, which is intractable. We approximate the integral with point estimates (i.e. marginal likelihood of our GP model):

p(D t-1 |d r j ) = p(D t-1 |θ, d r j )p(θ|d r j )dθ ≈ p(D t-1 |θ * , d r j ) where θ * = arg max θ p(D t-1 |θ, d r j ).

For query efficiency, we project the same perturbation query data in the original image dimension

D d t-1 = {g(δ i ), y i } t-1

i=1 to different latent spaces to get corresponding low-dimensional training data sets for separate GP models. The GP model that corresponds to d r j is trained on

D d r j t-1 = {g -1 (g(δ i )) , y i } t-1 i=1 where g -1 (g(δ i )) ∈ R d r j .

Then we select the optimal d r by comparing the marginal likelihood p(D

d r j t-1 |θ * , d r j )

of each GP surrogate. The overall procedure for d r selection is described in Algorithm 2. We would like to highlight that the use of the statistical surrogate in our BayesOpt attack approach enables us to naturally use the Bayesian model selection technique to learn the optimal d r that automatically enjoy the trade-off between data-fit quality and model complexity. And we also show empirically in Section 5.3 that by automating and incorporating the learning of d r into our BayesOpt attack, we can gain higher success rate and query efficiency. Other adversarial attacks methods can also use our proposed approach to decide d r but it would require the additional efforts of constructing statistical models to provide p(D t-1 |d r j ).

5. EXPERIMENTS:

We empirically compare the performance of our BayesOpt attacks against the state-of-the-art blackbox methods such as ZOO (Chen et al., 2017) , AutoZOOM (Tu et al., 2018) and GenAttack (Alzantot et al., 2018) . We denote the BayesOpt attack with standard GP surrogate as GP-BO, its variant that learns the d r automatically is GP-BO-auto-d r as well as the attack with additive GP surrogate as ADDGP-BO. For all the BayesOpt methods, we use GP-UCB as the acquisition function3 and update the GP hyperperameters every 5 BayesOpt iterations. We relearn the optimal d r for GP-BOauto-d r 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 CIFAR10 (a CNN with 80% test accuracy). Following the experiment design in (Tu et al., 2018) , we randomly select 50 correctly classified images from CIFAR10 test data and MNIST test data. We then perform targeted attacks on these images. Each selected image is attacked 9 times, targeting at all but its true class and this gives a total of 450 attack instances for both CIFAR10 and MNIST. For ImageNet, we also select 50 correctly classified images from the test set but perform one random targeted attack for each image. We set δ max = 0.3 for attacking MNIST and δ max = 0.05 for CIFAR10 and ImageNet, which are used in (Alzantot et al., 2018) . We use the recommended parameter setting and their open sourced implementations for performing all competing attack methods (Chen et al., 2017; Tu et al., 2018; Alzantot et al., 2018) .

5.1. EFFECT OF d r:

We first empirically investigate the effect of the reduced dimensionality d r 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 r = {6 × 6 × 3, 8 × 8 × 3, 10 × 10 × 3, 12 × 12 × 3, 14 × 14 × 3, 16 × 16 × 3, 18 × 18 × 3} and perform targeted attacks on 5 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 r 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 1 to 5, are shown in the left subplot of Figure 1 . It's evident that the d r which leads to highest attack success rate varies for different original images x origin .

We then examines how the d r affects the query efficiency and attack quality (average L 2 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 r . We present the results on 4 attack instances of a airplane image in the middle and right subplots of Figure 1 . We can see that even for the same original image and attack instances, varying d r can impact query efficiency and L 2 norm of the successful adversarial perturbation significantly. For example, d r = 8 × 8 × 3 is most query efficient for attack instance 1 and 4 but is outperformed by other dimensions in attack instance 2 and 3. Therefore, the importance of d r and the difficulty of finding the optimal d r for a specific target/image motivates us to derive our method for learning it automatically from the data. As shown in the following sections, our d r learner does lead to more superior attack performance.

5.2. PERFORMANCE UNDER A 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 CIFAR10 (Alzantot et al., 2018) and 2000 for ImageNet. We adopt the reduced search dimension recommended by AutoZOOM, d r = 14 × 14 × 3 for CIFAR10 and d r = 14 × 14 × 1 for MNIST and allow GP-BOauto-d r to automatically learn the reduced dimension d r in a range between 6×6×1 and 28×28×1 for MNIST, and between 6 × 6 × 3 and 32 × 32 × 3 for CIFAR10.

For ImageNet, due to the high dimensionality of its images, we adopt a hierarchical decoding process: 1) first performance BayesOpt attacks(ADDGP-BO and GP-BO) on a reduced dimension of d r 1 = 48 × 48 × 3 and then 2) decode the adversarial perturbation found in d r 1 to d r 2 = 96 × 96 × 3 via bilinear upsampling. 3) This is followed by another bilinear decoder projecting the adversarial perturbation in d r 2 back to image dimension of d = 299 × 299 × 3. As for the GP-BO-auto-d r , we allow the algorithm to automatically learn the reduced dimension d r 1 in the phase 1) in the range between 6 × 6 × 3 to 60 × 60 × 3. GenAttack is performed with the same upsampling as our methods. As for AutoZOOM and ZOO, we uses the optimal d r settings recommended in (Tu et al., 2018; Chen et al., 2017) for ImageNet.

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 is 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 finetuning stage to reduce the perturbation cost (e.g. L 2 norm) of the successful attack. We report its performance on the attack success rate and L 2 norm of adversarial perturbations after a budget of 1000 queries, which allows it to fine-tune the successful adversarial perturbations found. Moreover, AutoZOOM uses L 2 norm to measure the perturbation costs but our method and GenAttack limit the search space via L ∞ norm. We observe that the successful attacks found by AutoZOOM incur The results on MNIST in Table 1 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 GP-BO-auto-d r is 49% less than GenAttack and 67% less than AutoZOOM.

As for results on attacking on CIFAR10, 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 approaches also lead to better quality adversarial examples (Figure 3 in Appendix B ) which are closer to the original image than the benchmark methods as reflected by the lower average L 2 perturbation (20.5% less). More importantly, this set of experiments also demonstrate the effectiveness of our Bayesian method for learning d r as GP-BO-auto-d r leads to 15% increase in attack success rate compared to GP-BO while maintaining the competitiveness in query efficiency and L 2 distance.

Similarly, the results on ImageNet in Table 3 shows that all our BayesOpt attacks can achieve higher attack success rate than the competing methods given a query budget of 2000. ADDGP-BO is the clearly best performing method in this very high-dimensional setting, achieving 5 times higher success rate than the best competing method, GenAttack, while again obtaining successful adversarial perturbations with lower average L 2 perturbation (14 % less) than GenAttack. This confirms our hypothesis that the additive-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 to 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 CIFAR10 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 r take less than 833 queries to achieve the success rate of 98% for MNIST, which is 24% of that by GenAttack (2500). As for CIFAR10, both ADDGP-BO and GP-BO-auto-d r takes around 890 queries to achieve a 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 to be slightly more query efficient than GenAttack in this set of experiments. However, we need to bear in mind that although we limit the mean L inf norm of the adversarial perturbation found by AutoZOOM to δ max , AutoZOOM still have the advantage of exploring beyond the δ max for many dimensions. In the case of ImageNet, all our BayesOpt attacks again enjoy faster convergence, with 

6. CONCLUSION:

We introduce a new black-box adversarial attack which leverages Bayesian optimisation to find successful 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 to learn the optimal degree of dimension reduction for the search space via Bayesian model selection. 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 are closer to the original image (in terms of average L 2 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 an interesting future research direction.

A BAYESIAN OPTIMISATION:

Here we present a generic algorithm for Bayesian optimisation.

Algorithm 3 BayesOpt Algorithm 

C ADDITIONAL EXPERIMENTS ON MNIST AND CIFAR10 D OBJECTIVE VALUE OVER BAYESOPT ITERATIONS:

We illustrate this via the case of attacking a CIFAR10 image of label 9(class truck) on the other 9 target labels with original label 9We plot the value of objective function (Equation 2), which is equal to the negative of attack loss, against the BayesOpt iterations/query counts. We can see that our additive GP surrogate (ADDGP-BO) as well as the Bayesian learning of optimal d r (GP-BOauto-d r ) lead to faster convergence and thus higher attack success rate for this instance.

E EFFECTIVENESS OF DECOMPOSITION LEARNING:

To learn the decomposition for the additive-GP surrogate in ADDGP-BO attack, we follow the approach proposed in (Kandasamy et al., 2015) to treat the decomposition as an additional hyperparameter and learn the optimal decomposition by maximising marginal likelihood. However, exhaustive search over all M !d!/(d s ! M )5 possible decompositions is expensive. We adopt a computationally cheap alternative by randomly selecting 20 decompositions and choosing the one with the largest marginal likelihood. The method decomposition learning procedure is repeated every 40 BO iterations and we use M = 12 for CIFAR10. We denote the method as ADDGP-BO-LD in this section but as ADDGP-BO in the rest of the paper.

We also experiment with another alternative way to learn the decomposition (ADDGP-BO-FD), 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. 

:

Our code is available at https://github.com/rubinxin/BayesOpt_Attack.git

Note that our method is not dependent on a particular choice of decoder, i.e. it could also be used together with an autoencoder-or PCA-based dimensionality reduction technique.

The parameter that trades off exploration and exploitation is set to 2.

This still gives an advantage to ZOO and AutoZOOM because it allows them to inject perturbation whose magnitude is larger than δmax at certain pixels but our BayesOpt methods and GenAttack limit perturbation at all the pixels to be less than δmax.

M is the number of subspaces and ds = |Aj| is the dimension of each subspaces

Figures and Tables:

and computes its maximum marginal likelihood p(D d t-1 |θ * , d r j ) 6: end for 7: Select d r * = arg max d r j ∈{d r j } N j=1 p(D d t-1 |θ * , d r j

Figure 1: Performance of BayesOpt attack with GP surrogate in different reduced dimension d r .Each color represents a particular d r . 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 r 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 r . For the same 4 attack instances, the right subplot show the effect of the choice of d r on the L 2 distances between the resultant adversarial examples and the original image.

Figure 3: CIFAR10 adversarial examples generated by our BayesOpt attack. True labels and target labels correspond to the rows and columns.

Attack results on 50 random MNIST images by using d r = 14 × 14 × 1. Q denotes the query count. ASR denotes attack success rate. The standard errors are in parentheses.

Table content: <table><tr><td>Attack method</td><td colspan="3">ASR Q (Max, Median, Mean) Average L 2 perturbation (per pixel)</td></tr><tr><td>ADDGP-BO</td><td>97%</td><td>829, 46, 95(±6)</td><td>6.81 × 10 -3 (±3.12 × 10 -5 )</td></tr><tr><td colspan="2">GP-BO-auto-d r 98%</td><td>833, 75, 121(±6)</td><td>6.89 × 10 -3 (±5.55 × 10 -5 )</td></tr><tr><td>GP-BO</td><td>82%</td><td>899, 42, 77(±5)</td><td>7.15 × 10 -3 (±4.17 × 10 -5 )</td></tr><tr><td>GenAttack</td><td>92%</td><td>986, 146, 217(±9)</td><td>6.66 × 10 -3 (±2.81 × 10 -5 )</td></tr><tr><td>AutoZOOM</td><td>99%</td><td>998, 229, 265(±9)</td><td>5.05 × 10 -3 (±7.71 × 10 -5 )</td></tr><tr><td>ZOO</td><td>1%</td><td>256, 128, 128(±64)</td><td>2.78 × 10 -3 (±3.53 × 10 -5 )</td></tr></table>

Attack results on 50 randomly selected CIFAR10 images with d r = 14 × 14 × 3. Q denotes the query count. ASR denotes attack success rate.The standard errors are in parentheses.

Table content: <table><tr><td>Attack method</td><td colspan="3">ASR Q (Max, Median, Mean) Average L 2 perturbation (per pixel)</td></tr><tr><td>ADDGP-BO</td><td>87%</td><td>885, 154, 222(±10)</td><td>5.87 × 10 -4 (±3.22 × 10 -6 )</td></tr><tr><td colspan="2">GP-BO-auto-d r 87%</td><td>891, 159, 234(±10)</td><td>5.96 × 10 -4 (±5.00 × 10 -6 )</td></tr><tr><td>GP-BO</td><td>72%</td><td>899, 141, 190(±8)</td><td>5.78 × 10 -4 (±4.67 × 10 -6 )</td></tr><tr><td>GenAttack</td><td>68%</td><td>991, 246, 329(±14)</td><td>7.38 × 10 -4 (±4.14 × 10 -6 )</td></tr><tr><td>AutoZOOM</td><td>38%</td><td>896, 102, 154(±11)</td><td>9.97 × 10 -4 (±1.53 × 10 -5 )</td></tr><tr><td>ZOO</td><td>4%</td><td>768, 256, 369(±57)</td><td>1.77 × 10 -4 (±1.16 × 10 -5 )</td></tr></table>

Attack results on 50 randomly ImageNet images with random target label under a 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. much higher perturbation costs in terms of L ∞ norm than GenAttack and our method. Therefore, we only consider the final adversarial examples whose L ∞ distances from the original images lie within [-δ max , δ max ] as the successful attacks 4 .

Table content: <table><tr><td>Attack method</td><td colspan="2">ASR Q (Max, Median, Mean)</td><td>Average L 2 perturbation (per pixel)</td></tr><tr><td>ADDGP-BO</td><td>60%</td><td>1985, 1247, 1206(±90)</td><td>1.74 × 10 -4 (±1.89 × 10 -6 )</td></tr><tr><td colspan="2">GP-BO-auto-d r 32%</td><td>1999, 922, 938(±128)</td><td>1.96 × 10 -4 (±8.07 × 10 -6 )</td></tr><tr><td>GP-BO</td><td colspan="2">16% 1947, 1113, 1232(±162)</td><td>1.62 × 10 -4 (±7.94 × 10 -6 )</td></tr><tr><td>GenAttack</td><td colspan="2">12% 1971, 1354, 1266(±259)</td><td>2.03 × 10 -4 (±9.81 × 10 -6 )</td></tr><tr><td>AutoZOOM</td><td colspan="2">2% 1451, 1451, 1451(±0.00)</td><td>1.21 × 10 -5 (±0.00)</td></tr></table>

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 r (red) and ADDGP-BO (blue)) can achieve an ASR of 98% on MNIST(a) and 87% on CIFAR10 (b) within a budget of 1000 queries. To achieve the same success rates, GenAttack (purple) takes 3500 for MNIST and 5141 for CIFAR10, and AutoZOOM (green) takes 800 for MNIST and 3880 for CIFAR10. For ImageNet (c), the best BayesOpt attack is ADDGP-BO (blue), which achieves an ASR of 60% with 1985 queries. To achieve the same success rates, GenAttack (purple) takes a 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. Meanwhile, 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.

Table content: <table><tr><td/><td>1.00</td><td/><td/><td/><td/><td/><td/><td/><td>0.9</td></tr><tr><td>ASR (%)</td><td>0.00 0.25 0.75</td><td>0</td><td/><td colspan="4">500 1,000 Query counts 2,000 GP-BO-auto-dr 3,000 ADDGP-BO GP-BO GenAttack AutoZOOM ZOO</td><td>ASR (%)</td><td>0.0 0.3 0.6</td><td>Query counts 0 5001,000 2,000 3,000 4,000 5,200 GP-BO-auto-dr ADDGP-BO GP-BO GenAttack AutoZOOM ZOO</td></tr><tr><td/><td/><td/><td/><td colspan="3">(a) Attacks on MNIST</td><td/><td/><td>(b) Attacks on CIFAR10</td></tr><tr><td/><td/><td/><td>0.6</td><td/><td/><td/><td/><td/></tr><tr><td/><td colspan="2">ASR (%)</td><td>0.0 0.2 0.4</td><td>0</td><td>2,500</td><td>5,000</td><td colspan="3">7,500 Query counts 10,000</td><td>12,500</td><td>15,000</td><td>17,500 GP-BO-auto-dr 20,000 ADDGP-BO GP-BO GenAttack AutoZOOM ZOO</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td colspan="3">(c) Attacks on ImageNet</td></tr><tr><td colspan="2">Figure 2:</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Summary of attack results on 7 MNIST images. Q denotes the query count. ASR denotes attack success rate. The standard errors are in parentheses.

Table content: <table><tr><td>Attack method</td><td>d r</td><td colspan="3">ASR Q (Max, Median, Mean) Average L 2 perturbation (per pixel)</td></tr><tr><td>GP-BO</td><td colspan="2">14 × 14 × 1 92%</td><td>899, 53, 119(±28)</td><td>7.01 × 10 -3 (±1.13 × 10 -4 )</td></tr><tr><td>ADDGP-BO</td><td colspan="2">14 × 14 × 1 98%</td><td>584, 34, 67(±13)</td><td>6.50 × 10 -3 (±8.39 × 10 -5 )</td></tr><tr><td>AutoZOOM</td><td colspan="2">14 × 14 × 1 97%</td><td>892, 186, 247(±27)</td><td>5.10 × 10 -3 (±1.92 × 10 -4 )</td></tr><tr><td>GenAttack</td><td colspan="2">14 × 14 × 1 97%</td><td>976, 184, 239(±22)</td><td>5.56 × 10 -3 (±9.25 × 10 -5 )</td></tr><tr><td>GP-BO</td><td colspan="2">16 × 16 × 1 97%</td><td>400, 50, 80(±12)</td><td>7.08 × 10 -3 (±1.09 × 10 -4 )</td></tr><tr><td>ADDGP-BO</td><td colspan="2">16 × 16 × 1 100%</td><td>540, 42, 72(±12)</td><td>6.49 × 10 -3 (±9.41 × 10 -5 )</td></tr><tr><td>AutoZOOM</td><td colspan="2">16 × 16 × 1 98%</td><td>812, 251, 295(±28)</td><td>5.98 × 10 -3 (±2.03 × 10 -4 )</td></tr><tr><td>GenAttack</td><td colspan="2">16 × 16 × 1 97%</td><td>928, 202, 237(±19)</td><td>5.61 × 10 -3 (±8.58 × 10 -5 )</td></tr><tr><td>GP-BO</td><td colspan="2">28 × 28 × 1 98%</td><td>430, 201, 225(±11)</td><td>8.71 × 10 -3 (±1.94 × 10 -4 )</td></tr><tr><td>ADDGP-BO</td><td colspan="2">28 × 28 × 1 100%</td><td>666, 57, 100(±15)</td><td>9.71 × 10 -3 (±1.12 × 10 -4 )</td></tr><tr><td>AutoZOOM</td><td colspan="2">28 × 28 × 1 98%</td><td>860, 185, 244(±27)</td><td>1.01 × 10 -2 (±1.63 × 10 -4 )</td></tr><tr><td>GenAttack</td><td colspan="2">28 × 28 × 1 83%</td><td>976, 365, 399(±33)</td><td>6.26 × 10 -3 (±6.69 × 10 -5 )</td></tr></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.

Table content: <table><tr><td>Attack method</td><td>d r</td><td colspan="3">ASR Q (Max, Median, Mean) Average L 2 perturbation (per pixel)</td></tr><tr><td>GP-BO</td><td>8 × 8 × 3</td><td>52%</td><td>314, 48, 70(±13)</td><td>5.78 × 10 -4 (±1.44 × 10 -5 )</td></tr><tr><td>ADDGP-BO</td><td>8 × 8 × 3</td><td>75%</td><td>899, 140, 234(±33)</td><td>5.55 × 10 -4 (±8.46 × 10 -6 )</td></tr><tr><td>AutoZOOM</td><td>8 × 8 × 3</td><td>56%</td><td>382, 126, 139(±17)</td><td>9.58 × 10 -4 (±2.66 × 10 -5 )</td></tr><tr><td>GenAttack</td><td>8 × 8 × 3</td><td>67%</td><td>671, 236, 286(±32)</td><td>7.40 × 10 -4 (±1.30 × 10 -5 )</td></tr><tr><td>GP-BO</td><td colspan="2">14 × 14 × 3 81%</td><td>899, 142, 192(±11)</td><td>5.74 × 10 -4 (±6.96 × 10 -6 )</td></tr><tr><td>ADDGP-BO</td><td colspan="2">14 × 14 × 3 90%</td><td>885, 141, 213(±15)</td><td>5.79 × 10 -4 (±5.16 × 10 -6 )</td></tr><tr><td>AutoZOOM</td><td colspan="2">14 × 14 × 3 42%</td><td>376, 95, 133(±12)</td><td>9.82 × 10 -4 (±1.95 × 10 -5 )</td></tr><tr><td>GenAttack</td><td colspan="2">14 × 14 × 3 75%</td><td>971, 251, 321(±21)</td><td>7.35 × 10 -4 (±6.92 × 10 -6 )</td></tr><tr><td>GP-BO</td><td colspan="2">16 × 16 × 3 83%</td><td>785, 280, 292(±22)</td><td>5.34 × 10 -4 (±1.43 × 10 -5 )</td></tr><tr><td>ADDGP-BO</td><td colspan="2">16 × 16 × 3 87%</td><td>878, 168, 229(±29)</td><td>5.76 × 10 -4 (±8.93 × 10 -6 )</td></tr><tr><td>AutoZOOM</td><td colspan="2">16 × 16 × 3 3%</td><td>298, 170, 170(±90)</td><td>7.50 × 10 -4 (±1.35 × 10 -5 )</td></tr><tr><td>GenAttack</td><td colspan="2">16 × 16 × 3 79%</td><td>986, 281, 339(±36)</td><td>7.36 × 10 -4 (±1.55 × 10 -5 )</td></tr></table>

Summary of attack results on CIFAR10 for different decomposition learning method. d r = 14 × 14 × 3 which is further decomposed into 12 subspaces of d s = 49. Q denotes the query count. ASR denotes attack success rate. The standard errors are in parentheses.

Table content: <table><tr><td>Attack method</td><td colspan="3">ASR Q (Max, Median, Mean) Average L 2 perturbation (per pixel)</td></tr><tr><td colspan="2">ADDGP-BO-LD 94%</td><td>885, 134, 212(±16)</td><td>5.78 × 10 -4 (±5.32 × 10 -6 )</td></tr><tr><td colspan="2">ADDGP-BO-FD 87%</td><td>899, 143, 196(±14)</td><td>5.05 × 10</td></tr></table>

Peer review (iclr2020):
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. For 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. Along 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. Can 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).