Title: BLACK-BOX ADVERSARIAL ATTACK WITH TRANS-FERABLE MODEL-BASED EMBEDDING

Abstract: We present a new method for black-box adversarial attack. Unlike previous methods that combined transfer-based and scored-based methods by using the gradient or initialization of a surrogate white-box model, this new method tries to learn a low-dimensional embedding using a pretrained model, and then performs efficient search within the embedding space to attack an unknown target network. The method produces adversarial perturbations with high level semantic patterns that are easily transferable. We show that this approach can greatly improve the query efficiency of black-box adversarial attack across different target network architectures. We evaluate our approach on MNIST, ImageNet and Google Cloud Vision API, resulting in a significant reduction on the number of queries. We also attack adversarially defended networks on CIFAR10 and ImageNet, where our method not only reduces the number of queries, but also improves the attack success rate.

1. INTRODUCTION:

The wide adoption of neural network models in modern applications has caused major security concerns, as such models are known to be vulnerable to adversarial examples that can fool neural networks to make wrong predictions (Szegedy et al., 2014) . Methods to attack neural networks can be divided into two categories based on whether the parameters of the neural network are assumed to be known to the attacker: white-box attack and black-box attack. There are several approaches to find adversarial examples for black-box neural networks. The transfer-based attack methods first pretrain a source model and then generate adversarial examples using a standard white-box attack method on the source model to attack an unknown target network (Goodfellow et al., 2015; Madry et al., 2018; Carlini & Wagner, 2017; Papernot et al., 2016a) . The score-based attack requires a loss-oracle, which enables the attacker to query the target network at multiple points to approximate its gradient. The attacker can then apply the white-box attack techniques with the approximated gradient (Chen et al., 2017; Ilyas et al., 2018a; Tu et al., 2018) .

A major problem of the transfer-based attack is that it can not achieve very high success rate. And transfer-based attack is weak in targeted attack. On the contrary, the success rate of score-based attack has only small gap to the white-box attack but it requires many queries. Thus, it is natural to combine the two black-box attack approaches, so that we can take advantage of a pretrained white-box source neural network to perform more efficient search to attack an unknown target black-box model.

In fact, in the recent NeurIPS 2018 Adversarial Vision Challenge (Brendel et al., 2018) , many teams transferred adversarial examples from a source network as the starting point to carry out black-box boundary attack (Brendel et al., 2017) . N Attack also used a regression network as initialization in the score-based attack (Li et al., 2019a ). The transferred adversarial example could be a good starting point that lies close to the decision boundary for the target network and accelerate further optimization. P-RGF (Cheng et al., 2019) used the gradient information from the source model to accelerate searching process. However, gradient information is localized and sometimes it is misleading. In this paper, we push the idea of using a pretrained white-box source network to guide black-box attack significantly further, by proposing a method called TRansferable EMbedding based Black-box Attack (TREMBA). TREMBA contains two stages: (1) train an encoder-decoder that can effectively generate adversarial perturbations for the source network with a low-dimensional embedding space; (2) apply NES (Natural Evolution Strategy) of (Wierstra et al., 2014) to the low-dimensional embedding space of the pretrained generator to search adversarial examples for the target network. TREMBA uses global information of the source model, capturing high level semantic adversarial features that are insensitive to different models. Unlike noise-like perturbations, such perturbations would have much higher transferablity across different models. Therefore we could gain query efficiency by performing queries in the embedding space.

We note that there have been a number of earlier works on using generators to produce adversarial perturbations in the white-box setting (Baluja & Fischer, 2018; Xiao et al., 2018; Wang & Yu, 2019) . While black-box attacks were also considered there, they focused on training generators with dynamic distillation. These early approaches required many queries to fine-tune the classifier for different target networks, which may not be practical for real applications. While our approach also relies on a generator, we train it as an encoder-decoder that produces a low-dimensional embedding space. By applying a standard black-box attack method such as NES on the embedding space, adversarial perturbations can be found efficiently for a target model.

It is worth noting that the embedding approach has also been used in AutoZOOM (Tu et al., 2018) . However, it only trained the autoencoder to reconstruct the input, and it did not take advantage of the information of a pretrained network. Although it also produces structural perturbations, these perturbations are usually not suitable for attacking regular networks and sometimes its performance is even worse than directly applying NES to the images (Cheng et al., 2019; Guo et al., 2019) . TREMBA, on the other hand, tries to learn an embedding space that can efficiently generate adversarial perturbations for a pretrained source network. Compared to AutoZOOM, our new method produces adversarial perturbation with high level semantic features that could hugely affect arbitrary target networks, resulting in significantly lower number of queries.

We summarize our contributions as follows:

1. We propose TREMBA, an attack method that explores a novel way to utilize the information of a pretrained source network to improve the query efficiency of black-box attack on a target network.

2. We show that TREMBA can produce adversarial perturbations with high level semantic patterns, which are effective across different networks, resulting in much lower queries on MNIST and ImageNet especially for the targeted attack that has low transferablity.

3. We demonstrate that TREMBA can be applied to SOTA defended models (Madry et al., 2018; Xie et al., 2018) . Compared with other black-box attacks, TREMBA increases success rate by approximately 10% while reduces the number of queries by more than 50%.

2. RELATED WORKS:

There have been a vast literature on adversarial examples. We will cover the most relevant topics including white-box attack, black-box attack and defense methods.

White-Box Attack White-box attack requires the full knowledge of the target model. It was first discovered by (Szegedy et al., 2014) that adversarial examples could be found by solving an optimization problem with L-BFGS (Nocedal, 1980) . Later on, other methods were proposed to find adversarial examples with improved success rate and efficiency (Goodfellow et al., 2015; Kurakin et al., 2016; Papernot et al., 2016b; Moosavi-Dezfooli et al., 2016) . More recently, it was shown that generators can also construct adversarial noises with high success rate (Xiao et al., 2018; Baluja & Fischer, 2018) .

Black-Box Attack Black-box attack can be divided into three categories: transfer-based, score-based and decision-based. It is well known that adversaries have high transferablity across different networks (Papernot et al., 2016a) . Transfer-based methods generate adversarial noises on a source model and then transfer it to an unknown target network. It is known that targeted attack is harder than untargeted attack for transfer-based methods, and using an ensemble of source models can improve the success rate (Liu et al., 2016) . Score-based attack assumes that the attacker can query the output scores of the target network. The attacker usually uses sampling methods to approximate the true gradient (Chen et al., 2017; Ilyas et al., 2018a; Li et al., 2019a; Chen et al., 2018) . AutoZOOM tried to improve the query efficiency by reducing the sampling space with a bilinear transformation or an autoencoder (Tu et al., 2018) . (Ilyas et al., 2018b) incorporated data and time prior to accelerate attacking. In contrast to the gradient based method, (Moon et al., 2019) used combinatorial optimization to achieve good efficiency. In decision-based attack, the attacker only knows the output label of the classifier. Boundary attack and its variants are very powerful in this setting (Brendel et al., 2017; Dong et al., 2019) . In NeutIPS 2018 Adversarial Vision Challenge (Brendel et al., 2018) , some teams combined transfer-based attack and decision-based attack in their attacking methods (Brunner et al., 2018) . And in a similar spirit, N Attack also used a regression network as initialization in score-based attack (Li et al., 2019a) . Gradient information from the surrogate model could also be used to accelerate the scored-based attack (Cheng et al., 2019) .

Defense Methods Several methods have been proposed to overcome the vulnerability of neural networks. Gradient masking based methods add non-differential operations in the model, interrupting the backward pass of gradients. However, they are vulnerable to adversarial attacks with the approximated gradient (Athalye et al., 2018; Li et al., 2019a) . Adversarial training is the SOTA method that can be used to improve the robustness of neural networks. Adversarial training is a minimax game. The outside minimizer performs regular training of the neural network, and the inner maximizer finds a perturbation of the input to attack the network. The inner maximization process can be approximated with FGSM (Goodfellow et al., 2015) , PGD (Madry et al., 2018) , adversarial generator (Wang & Yu, 2019) etc. Moreover, feature denoising can improve the robustness of neural networks on ImageNet (Xie et al., 2018) .

3. BLACK-BOX ADVERSARIAL ATTACK WITH GENERATOR:

Consider a DNN classifier F (x). Let x ∈ [0, 1] dim(x) be an input, and let F (x) be the output vector obtained before the softmax layer. We denote F (x) i as the i-th component for the output vector and y as the label for the input. For un-targeted attack, our goal is to find a small perturbation δ such that the classifier predicts the wrong label, i.e. arg max F (x + δ) = y. And for targeted attack, we want the classifier to predicts the target label t, i.e. arg max F (x + δ) = t. The perturbation δ is usually bounded by p norm: δ p ≤ ε, with a small ε > 0.

Adversarial perturbations often have high transferablity across different DNNs. Given a white-box source DNN F s with known architecture and parameters, we can transfer its white-box adversarial perturbation δ s to a black-box target DNN F t with reasonably good success rate. It is known that even if x + δ s fails to be an adversarial example, δ s can still act as a good starting point for searching adversarial examples using a score-based attack method. This paper shows that the information of F s can be further utilized to train a generator, and performing search on its embedding space leads to more efficient black-box attacks of an unknown target network F t .

3.1. GENERATING ADVERSARIAL PERTURBATIONS WITH GENERATOR:

Adversarial perturbations can be generated by a generator network G. We explicitly divide the generator into two parts: an encoder E and a decoder D. The encoder takes the origin input x and output a latent vector z = E(x), where dim(z) dim(x). The decoder takes z as the input and outputs an adversarial perturbation δ = ε tanh(D(z)) with dim(δ) = dim(x). In our new method, we will train the generator G so that δ = ε tanh(G(x)) can fool the source network F s .

Suppose we have a training set {(x 1 , y 1 ) , . . . , (x n , y n )}, where x i denotes the input and y i denotes its label. For un-targeted attack, we train the desired generator by minimizing the hinge loss used in the C&W attack (Carlini & Wagner, 2017) :

L untarget (x i , y i ) = max F s (ε tanh(G(x i )) + x i ) yi -max j =yi F s (ε tanh(G(x i )) + x i ) j , -κ , (1)

And for targeted, we use

EQUATION

where t denotes the targeted class and κ is the margin parameter that can be used to adjust transferability of the generator. A higher value of κ leads to higher transferability to other models (Carlini & Wagner, 2017) . We focus on ∞ norm in this work. By adding point-wise tanh function to an unnormalized output D(z), and scaling it with ε, δ = ε tanh(D(z)) is already bounded as δ ∞ < ε.

Therefore we employ this transformation, so that we do not need to impose the infinity norm constraint explicitly. While hinge loss is employed in this paper, we believe other loss functions such the cross entropy loss will also work.

3.2. SEARCH OVER LATENT SPACE WITH NES:

Given a new black-box DNN classifier F t (x), for which we can only query its output at any given point x. As in (Ilyas et al., 2018a; Wierstra et al., 2014) , we can employ NES to approximate the gradient of a properly defined surrogate loss in order to find an adversarial example. Denote the surrogate loss by L, rather than calculating ∇ δ L(x+δ, y) directly, NES update δ by using

∇ δ E ω∼N (δ,σ 2 ) [L(x+ω, y)],

which can be transformed into

E ω∼N (δ,σ 2 ) [L(x + ω, y)∇ ω log(N (ω|δ, σ 2 ))].

The expectation can be approximated by taking finite samples. And we could use the following equation to iteratively update δ:

EQUATION

where η is the learning rate, b is the minibatch sample size, ω k is the sample from the gaussian distribution and [-ε,ε] represents a clipping operation, which projects δ onto the ∞ ball. The sign function provides an approximation of the gradient, which has been widely used in adversarial attack (Ilyas et al., 2018a; Madry et al., 2018) . However, it is observed that more effective attacks can be obtained by removing the sign function (Li et al., 2019b) . Therefore in this work, we remove the sign function from Eqn (3) and directly use the estimated gradient.

Instead of performing search on the input space, TREMBA performs search on the embedding space z. The generator G explores the weakness of the source DNN F s so that D produces perturbations that can effective attack F s . For a different unknown target network F t , we show that our method can still generate perturbations leading to more effective attack of F t . Given an input x and its label y, we choose a starting point z 0 = E(x). The gradient of z t given by NES can be estimated as:

∇ z t L(x + ε tanh(D(z t )), y) ≈ ∇ z t E ν∼N (z t ,σ 2 ) [L(x + ε tanh(D(ν)), y)] (4) ≈ 1 b b k=1 L(x + ε tanh(D(ν k )), y)∇ z t log N (ν k |z t , σ 2 ).

where ν k is the sample from the gaussian distribution N (z t , σ 2 ). Moreover, z t is updated with stochastic gradient descent. The detailed procedure is presented in Algorithm 1. We do not need to do projection explicitly since δ already satisfies δ ∞ < ε.

Next we shall briefly explain why applying NES on the embedding space z can accelerate the search process. Adversarial examples can be viewed as a distribution lying around a given input. Usually this distribution is concentrated on some small regions, making the search process relatively slow.

After training on the source network, the adversarial perturbations of TREMBA would have high level semantic patterns that are likely to be adversarial patterns of the target network. Therefore searching over z is like searching adversarial examples in a lower dimensional space containing likely adversarial patterns. The distribution of adversarial perturbations in this space is much less concentrated. It is thus much easier to find effective adversarial patterns in the embedding space.

4. EXPERIMENTS:

We evaluated the number of queries versus success rate of TREMBA on undefended network in two datasets: MNIST (LeCun et al., 1998) and ImageNet (Russakovsky et al., 2015) . Moreover, we evaluated the efficiency of our method on adversarially defended networks in CIFAR10 (Krizhevsky & Hinton, 2009) and ImageNet. We also attacked Google Cloud Vision API to show TREMBA can generalize to truly black-box model. 1 We used the hinge loss from Eqn 1 and 2 as the surrogate loss for un-targeted and targeted attack respectively.

We compared TREMBA to four methods: (1) NES: Method introduced by (Ilyas et al., 2018a) , but without the sign function for reasons explained earlier.

(2) Trans-NES: Take an adversarial 

z 0 = E(x) 2: for t = 1 to T do 3: Sample Gaussian noise ν 1 , ν 2 , • • • , ν b ∼ N (z t-1 , σ 2 ) 4: Calculate L i = L untarget (x, y) or L target (x, t) 5: Update z t = z t-1 -η b b i=1 L i ∇ zt-1 log N (ν i |z t-1 , σ 2 ) 6: end for 7: return δ = ε tanh(D(z T ))

perturbation generated by PGD or FGSM on the source model to initialize NES. (3) AutoZOOM: Attack target network with an unsupervised autoencoder described in (Tu et al., 2018) . For fair comparisons with other methods, the strategy of choosing sample size was removed. (4) P-RGF: Prior-guided random gradient-free method proposed in (Cheng et al., 2019) . The P-RGF D (λ * ) version was compared. We also combined P-RGF with initialization from Trans-NES PGD to form a more efficient method for comparison, denoted by Trans-P-RGF.

Since different methods achieve different success rates, we need to compare their efficiency at different levels of success rate. For method i with success rate s i , the average number of queries is q i for all success examples. Let q * denote the upper limit of queries, we modified the average number of queries to be q * i = [(max j s j -s i ) • q * + s i • q i ]/ max j s j , which unified the level of success rate and treated queries of failure examples as the upper limit on the number of queries. Average queries sometimes could be misleading due to the the heavy tail distribution of queries. Therefore we plot the curve of success rate at different query levels to show the detailed behavior of different attacks.

The upper limit on the number of queries was set to 50000 for all datasets, which already gave very high success rate for nearly all the methods. Only correctly classified images were counted towards success rate and average queries. And to fairly compare these methods, we chose the sample size to be the same for all methods. We also added momentum and learning decay for optimization. And we counted the queries as one if its starting point successfully attacks the target classifier. The learning rate was fine-tuned for all algorithms. We listed the hyperparameters and architectures of generators and classifiers in Appendix B and C.

4.1. BLACK-BOX ATTACK ON MNIST:

We trained four neural networks on MNIST, denoted by ConvNet1, ConvNet1*, ConvNet2 and FCNet. ConvNet1* and ConvNet1 have the same architecture but different parameters. All the network achieved about 99% accuracy. The generator G was trained on ConvNet1* using all images from the training set. Each attack was tested on images from the MNIST test set. The limit of ∞ was ε = 0.2.

We performed un-targeted attack on MNIST. Table 1 lists the success rate and the average queries. Although the success rate of TREMBA is slightly lower than Trans-NES in ConvNet1 and FCNet, their success rate are already close to 100% and TREMBA achieves about 50% reduction of queries compared with other attacks. In contrast to efficient attack on ImageNet, P-RGF and Trans-P-RGF behaves very bad on MNIST. Figure 4 .1 shows that TREMBA consistently achieves higher success rate at nearly all query levels.

4.2. BLACK-BOX ATTACK ON IMAGENET:

We randomly divided the ImageNet validation set into two parts, containing 49000 and 1000 images respectively. The first part was used as the training data for the generator G, and the second part was used for evaluating the attacks. We evaluated the efficiency of all adversarial attacks on VGG19 (Simonyan & Zisserman, 2014) , Resnet34 (He et al., 2016) , DenseNet121 (Huang et al., 2017) and MobilenetV2 (Sandler et al., 2018) . All networks were downloaded using torchvision package. We set ε = 0.03125. Following (Liu et al., 2016) , we used an ensemble (VGG16, Resnet18, Squeezenet (Iandola et al., 2016) and Googlenet (Szegedy et al., 2015) ) as the source model to improve transferablity (Liu et al., 2016) for both targeted and un-targeted attack. TREMBA, Trans-NES, P-RGF and Trans-P-RGF all used the same source model for fair comparison. We chose several target class. Here, we show the result of attacking class 0 (tench) in Table 2 and Figure 2 . And we leave the result of attacking other classes in Appendix A.1. The average queries for TREMBA is about 1000 while nearly all the average queries for other methods are more than 6000. TREMBA also achieves much lower queries for un-targeted attack on ImageNet. The result is shown in Appendix A.2 due to space limitation. And we also compared TREMBA with CombOpt (Moon et al., 2019) in the Appendix A.9.

Figure 3 shows the adversarial perturbations of different methods. Unlike adversarial perturbations produced by PGD, the perturbations of TREMBA reflect some high level semantic patterns of the targeted class such as the fish scale. As neural networks usually capture such patterns for classification, the adversarial perturbation of TREMBA would be more easy to transfer than the noise-like perturbation produced by PGD. Therefore TREMBA can search very effectively for the target network. More examples of perturbations of TREMBA are shown in Appendix A.3.

Choice of ensemble::

We performed attack on different ensembles of source model, which is shown in Appendix A.4. TREMBA outperforms the other methods in different ensemble model. And more source networks lead to better transferability for TREMBA, Trans-NES and Trans-P-RGF.

Varying ε: We also changed ε and performed attack on ε = 0.02 and ε = 0.04. As shown in Appendix A.5, TREMBA still outperforms the other methods despite using the G trained on ε = 0.03125. We also show the result of TREMBA for commonly used ε = 0.05.

Sample size and dimension the embedding space::

To justify the choice of sample size, we performed a hyperparameter sweep over b and the result is shown in Appendix A.6. And we also changed the dimension of the embedding space for AutoZOOM and Trans-P-RGF. As shown in Appendix A.7, the performance gain of TREMBA does not purely come from the diminishing of dimension of the embedding space.

4.3. BLACK-BOX ATTACK ON DEFENDED MODELS:

This section presents the results for attacking defended networks. We performed un-targeted attack on two SOTA defense methods on CIFAR10 and ImageNet. MNIST is not studied since it is already (Madry et al., 2018) . We directly used their model as the source network2 , denoted by WResnet. To test whether these methods can transfer to a defended network with a different architecture, we trained a defended ResNeXt (Xie et al., 2017) using the same method. For ImageNet, we used the SOTA model3 from (Xie et al., 2018) . We used "ResNet152 Denoise" as the source model and transfered adversarial perturbations to the most robust "ResNeXt101 DenoiseAll". Following the previous settings, we set ε = 0.03125 for both CIFAR10 and ImageNet.

As shown in Table 3 , TREMBA achieves higher success rates with lower number of queries. TREMBA achieves about 10% improvement of success rate while the average queries are reduced by more than 50% on ImageNet and by 80% on CIFAR10. The curves in Figure 4 (a) and 4(b) show detailed behaviors. The performance of AutoZOOM surpasses Trans-NES on defended models. We suspect that low-frequency adversarial perturbations produced by AutoZOOM will be more suitable to fool the defended models than the regular networks. However, the patterns learned by AutoZOOM are still worse than adversarial patterns learned by TREMBA from the source network. An optimized starting point for TREMBA: z 0 = E(x) is already a good starting point for attacking undefended networks. However, the capability of generator is limited for defended networks (Wang & Yu, 2019) . Therefore, z 0 may not be the best starting point we can get from the defended source network. To enhance the usefulness of the starting point, we optimized z on the source network by gradient descent and found

EQUATION

)

The method is denoted by TREMBA OSP (TREMBA with optimized starting point). Figure 4 shows TREMBA OSP has higher success rate at small query levels, which means its starting point is better than TREMBA.

4.4. ATTACK GOOGLE CLOUD VISION API:

We also attacked the Google Cloud Vision API, which was much harder to attack than the single neural network. Therefore we set ε = 0.05 and perform un-targeted attack on the API, changing the top1 label to whatever is not on top1 before. We chose 10 images for the ImageNet dataset and set query limit to be 500 due to high cost to use the API. As shown Table 4 , TREMBA achieves much higher accuracy success rate and lower number of queries. We show the example of successfully attacked image in Appendix A.8.

5. CONCLUSION:

We propose a novel method, TREMBA, to generate likely adversarial patterns for an unknown network. The method contains two stages: (1) training an encoder-decoder to generate adversarial perturbations for the source network; (2) search adversarial perturbations on the low-dimensional embedding space of the generator for any unknown target network. Compared with SOTA methods, TREMBA learns an embedding space that is more transferable across different network architectures. It achieves two to six times improvements in black-box adversarial attacks on MNIST and ImageNet and it is especially efficient in performing targeted attack. Furthermore, TREMBA demonstrates great capability in attacking defended networks, resulting in a nearly 10% improvement on the attack success rate, with two to six times of reductions in the number of queries. TREMBA opens up new ways to combine transfer-based and score-based attack methods to achieve higher efficiency in searching adversarial examples.

For targeted attack, TREMBA requires different generators to attack different classes. We believe methods from conditional image generation (Mirza & Osindero, 2014 ) may be combined with TREMBA to form a single generator that could attack multiple targeted classes. We leave it as a future work.

A EXPERIMENT RESULT:

A.1 TARGETED ATTACK ON IMAGENET Figure 9 shows result of the targeted attack on dipper, American chameleon, night snake, ruffed grouse and black swan. TREMBA achieves much higher success rate than other methods at almost all queries level.

A.2 UN-TARGETED ATTACK ON IMAGENET We used the same source model from targeted attack as the source model for un-targeted attack. We report our evaluation results in Table 5 and Figure 5 . Compared with Trans-P-RGF, TREMBA reduces the number of queries by more than a half in ResNet34, DenseNet121 and MobilenetV2.

Searching in the embedding space of generator remains very effective even when the target network architecture differs significantly from the networks in the source model. 

A.4 EXPERIMENTS ON DIFFERENT ENSEMBLES:

We chose two more source ensemble models for evaluation. The first ensemble contains VGG16 and Squeezenet. And the second ensemble is consist of VGG16, Squeezenet and Googlenet. Figure 6 shows our result for targeted attack for ImageNet. We only compared Trans-NES PGD and Trans-P-RGF since they are the best variants from Trans-NES and P-RGF. We chose ε = 0.02 and ε = 0.04 and performed targeted attack on ImageNet. Although TREMBA used the same model that is trained on ε = 0.03125, it still outperformed other methods, which shows that TREMBA can also generalize to different strength of adversarial attack with different ε.

For the commonly used ε = 0.05, TREMBA also performs well. The results are shown in Table 6 , Table 7 , and Figure 8 .

A.6 VARYING SAMPLE SIZE:

We performed a hyperparameter sweep over b on Densenet121 on un-targeted attack on ImageNet. b = 20 may not be the best choice Trans-NES, but it is not the best for TREMBA, either. Generally, the performance is not very sensitive to b, and TREMBA will also outperform other methods even if we fine-tune the sample size for all the methods.

A.7 DIMENSION OF THE EMBEDDING SPACE:

We slightly changed the architecture of the autoencoder by adding max pooling layers and changing the number of filters and perform un-targeted attack on ImageNet. More specifically, we added additional max pooling layers after the first and the fourth convolution layers and changed the number of filters of the last layer in the encoder to be 8. Thus, the dimension of the embedding space would be 8 × 8 × 8. And we also changed the factor of bilinear sampling in the decoder. The remaining 9 , this autoencoder is even worse than the original autoencoder despite small dimension of the embedding space. In addition, we also changed to dimension of the data-dependent prior of Trans-P-RGF to match the dimension of TREMBA, whose performance is also not better than before. They show that simply diminishing the size of the embedding space may not lead to better performance. The performance gain of TREMBA comes beyond the effect of diminishing the dimension of the embedding space. 

:

Our code is available at https://github.com/TransEmbedBA/TREMBA

https://github.com/MadryLab/cifar10_challenge

https://github.com/facebookresearch/ImageNet-Adversarial-Training

Figures and Tables:

Figure 1: Success rate of un-targeted attack at different query levels for undefended MNIST models.

Figure 2: The success rate of black-box adversarial targeted attack at different query levels for ImageNet models. The targeted class is tench

Figure 4: The success rate at different query levels for defended CIFAR10 and ImageNet models. (a)CIFAR10; (b)ImageNet.

Figure 5: The success rate of un-targeted black-box adversarial attack at different query levels for undefended ImageNet models.

Figure 6: We show the success rate at different query levels for targeted attack for different ensemble source networks. V represents VGG16; S represents Squeezenet; G represents Googlenet; R represents Resnet18

Figure 7: We show the success rate at different query levels for attack at different ε for ImageNet.

Figure11shows one example of attacking Google Cloud Vision API. TREMBA successfully make the shark to be classified as green. Compared with Trans-NES PGD , TREMBA hugely changes the

Figure 10: Visualization of adversarial perturbations for targeted attack on ImageNet. The first column shows one example of the target class. Other columns show the adversarial perturbations.

Algorithm 1 Black-Box adversarial attack on the embedding space Input: Target Network F t ; Input x and its label y or the target class t; Encoder E; Decoder D; Standard deviation σ; Learning rate η; Sample size b; Iterations T ; Bound for adversarial perturbation ε Output: Adversarial perturbation δ 1:

Table content: <table/>

Success rate and average queries of un-targeted attack on MNIST. ε = 0.2

Table content: <table><tr><td colspan="2">Attack</td><td/><td/><td colspan="2">ConvNet1</td><td/><td/><td colspan="2">ConvNet2</td><td/><td/><td>FCNet</td></tr><tr><td/><td/><td/><td colspan="2">Success</td><td colspan="2">Queries</td><td/><td>Success</td><td colspan="3">Queries</td><td>Success</td><td>Queries</td></tr><tr><td colspan="2">NES</td><td/><td colspan="2">97.88%</td><td>4380</td><td/><td/><td>90.32%</td><td colspan="2">5428</td><td/><td>99.98%</td><td>1183</td></tr><tr><td colspan="2">Trans-NES PGD</td><td/><td colspan="2">98.65%</td><td>2113</td><td/><td/><td>90.22%</td><td colspan="2">4691</td><td/><td>99.99%</td><td>818</td></tr><tr><td colspan="2">Trans-NES FGSM</td><td/><td colspan="2">98.34%</td><td>3592</td><td/><td/><td>91.32%</td><td colspan="2">4218</td><td/><td>99.99%</td><td>1540</td></tr><tr><td colspan="2">AutoZOOM</td><td/><td colspan="2">93.39%</td><td>5874</td><td/><td/><td>91.21%</td><td colspan="2">2645</td><td/><td>99.69%</td><td>823</td></tr><tr><td colspan="2">P-RGF</td><td/><td colspan="2">68.53%</td><td>16135</td><td/><td/><td>39.85%</td><td colspan="3">29692</td><td>90.42%</td><td>8289</td></tr><tr><td colspan="2">Trans-P-RGF</td><td/><td colspan="2">66.34%</td><td>16428</td><td/><td/><td>27.57%</td><td colspan="3">35576</td><td>68.39%</td><td>18818</td></tr><tr><td colspan="2">TREMBA</td><td/><td colspan="2">98.00%</td><td>1064</td><td/><td/><td>92.63%</td><td colspan="2">1359</td><td/><td>99.75%</td><td>470</td></tr><tr><td/><td>100%</td><td colspan="2">ConvNet1</td><td/><td/><td colspan="2">ConvNet2</td><td/><td>100%</td><td/><td>FCNet</td></tr><tr><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/></tr><tr><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>NES Trans-NESPGD Trans-NESFGSM AutoZOOM P-RGF Trans-P-RGF TREMBA</td></tr><tr><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/></tr><tr><td/><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td></tr></table>

Success rate and average queries of black-box targeted attack on ImageNet. Targeted class is class 0 (tench). ε = 0.03125

Table content: <table><tr><td/><td/><td colspan="2">Attack</td><td/><td colspan="2">VGG19</td><td/><td colspan="2">Resnet34</td><td/><td/><td colspan="2">DenseNet121</td><td/><td colspan="2">MobilenetV2</td></tr><tr><td/><td/><td/><td/><td colspan="13">Success Queries Success Queries Success Queries Success Queries</td></tr><tr><td/><td/><td>NES</td><td/><td colspan="13">94.86% 12283 93.89% 14418 95.65% 12538 97.76% 10276</td></tr><tr><td/><td colspan="16">Trans-NES PGD 96.26% 6854 95.97% 8737 96.59% 8627 98.04% 9375</td></tr><tr><td colspan="17">Trans-NES FGSM 90.85% 12885 91.81% 14090 93.61% 12859 97.48% 9983</td></tr><tr><td/><td colspan="3">AutoZOOM</td><td colspan="13">25.80% 40195 26.25% 39681 31.98% 37628 27.03% 39689</td></tr><tr><td/><td/><td colspan="2">P-RGF</td><td colspan="13">96.12% 6951 90.28% 10221 91.84% 11563 88.94% 14596</td></tr><tr><td/><td colspan="16">Trans-P-RGF 98.06% 2262 93.61% 6309 94.69% 7263 91.60% 10048</td></tr><tr><td/><td colspan="3">TREMBA</td><td colspan="2">98.47%</td><td colspan="2">853</td><td colspan="9">96.38% 1206 98.50% 1124 99.16% 1210</td></tr><tr><td/><td>100%</td><td/><td>VGG19</td><td/><td>100%</td><td colspan="2">Resnet34</td><td/><td>100%</td><td colspan="2">DenseNet121</td><td/><td>100%</td><td colspan="2">MobilenetV2</td></tr><tr><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/></tr><tr><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>NES Trans-NESPGD Trans-NESFGSM AutoZOOM P-RGF Trans-P-RGF TREMBA</td></tr><tr><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/></tr><tr><td/><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td></tr></table>

Success rate of average queries of black-box un-targeted attack on defended CIFAR10 and ImageNet model. Source network is WResNet and ResNet152 Denoise.

Table content: <table><tr><td>Attack</td><td/><td/><td colspan="3">CIFAR10 ResneXt</td><td/><td/><td>ImageNet RexneXt101 DenoiseAll</td></tr><tr><td/><td/><td colspan="3">Success</td><td colspan="3">Queries</td><td>Success</td><td>Queries</td></tr><tr><td>NES</td><td/><td colspan="3">32.17%</td><td colspan="3">24521</td><td>29.72%</td><td>26526</td></tr><tr><td colspan="2">Trans-NES PGD</td><td colspan="3">32.92%</td><td colspan="3">20735</td><td>32.84%</td><td>20446</td></tr><tr><td colspan="2">Trans-NES FGSM</td><td colspan="3">33.17%</td><td colspan="3">20873</td><td>33.66%</td><td>18547</td></tr><tr><td colspan="2">AutoZOOM</td><td colspan="3">33.70%</td><td colspan="3">14870</td><td>38.75%</td><td>14605</td></tr><tr><td>P-RGF</td><td/><td colspan="3">22.37%</td><td colspan="3">25818</td><td>32.51%</td><td>17926</td></tr><tr><td colspan="2">Trans-P-RGF</td><td colspan="3">20.88%</td><td colspan="3">27222</td><td>31.03%</td><td>19262</td></tr><tr><td colspan="2">TREMBA</td><td colspan="3">42.73%</td><td colspan="2">2528</td><td/><td>49.59%</td><td>5985</td></tr><tr><td colspan="2">TREMBA OSP</td><td colspan="3">41.56%</td><td colspan="2">4994</td><td/><td>50.41%</td><td>4771</td></tr><tr><td/><td/><td colspan="2">ResNeXt</td><td/><td/><td/><td/><td>ResNetXt101 DenoiseAll</td></tr><tr><td/><td>40%</td><td/><td/><td/><td/><td/><td>50%</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>40%</td></tr><tr><td>Success Rate</td><td>10% 20% 30%</td><td/><td/><td/><td>NES Trans-NESPGD Trans-NESFGSM AutoZOOM P-RGF Trans-P-RGF TREMBA TREMBAOSP</td><td>Success Rate</td><td>10% 20% 30%</td><td>NES Trans-NESPGD Trans-NESFGSM AutoZOOM P-RGF Trans-P-RGF TREMBA TREMBAOSP</td></tr><tr><td/><td>0%</td><td/><td/><td/><td/><td/><td>0%</td></tr><tr><td/><td>102</td><td>103</td><td>Queries</td><td>104</td><td/><td/><td>102</td><td>103</td><td>Queries</td><td>104</td></tr><tr><td/><td/><td colspan="3">(a) CIFAR10</td><td/><td/><td/><td>(b) ImageNet</td></tr></table>

Success rate and average queries of un-targeted attack of 10 images on Google Vision API.

Table content: <table><tr><td>Method</td><td>NES</td><td colspan="2">AutoZOOM Trans-NES PGD</td><td>P-RGF</td><td colspan="2">Trans-P-RGF TREMBA</td></tr><tr><td colspan="2">Success 70.00%</td><td>20.00%</td><td>70.00%</td><td>50.00%</td><td>60.00%</td><td>90.00%</td></tr><tr><td>Queries</td><td>245</td><td>410</td><td>114</td><td>324</td><td>167</td><td>8</td></tr></table>

Success rate and average queries of un-targeted attack on ImageNet. ε = 0.03125

Table content: <table><tr><td/><td/><td colspan="2">Attack</td><td/><td colspan="2">VGG19</td><td/><td colspan="2">Resnet34</td><td/><td/><td colspan="2">DenseNet121</td><td/><td colspan="2">MobilenetV2</td></tr><tr><td/><td/><td/><td/><td colspan="13">Success Queries Success Queries Success Queries Success Queries</td></tr><tr><td/><td/><td>NES</td><td/><td colspan="2">100%</td><td colspan="2">924</td><td>100%</td><td colspan="2">1255</td><td colspan="2">100%</td><td colspan="4">1235 99.86%</td><td>872</td></tr><tr><td/><td colspan="5">Trans-NES PGD 100%</td><td colspan="2">441</td><td>100%</td><td>827</td><td/><td colspan="2">100%</td><td>838</td><td/><td colspan="2">100%</td><td>733</td></tr><tr><td colspan="6">Trans-NES FGSM 100%</td><td colspan="2">586</td><td>100%</td><td>982</td><td/><td colspan="2">100%</td><td>961</td><td/><td colspan="2">100%</td><td>648</td></tr><tr><td/><td colspan="3">AutoZOOM</td><td colspan="13">94.18% 5184 96.25% 3754 94.56% 4567 95.38% 4213</td></tr><tr><td/><td/><td colspan="2">P-RGF</td><td colspan="2">100%</td><td colspan="2">277</td><td>99.72%</td><td>635</td><td/><td colspan="2">100%</td><td>709</td><td colspan="3">99.72%</td><td>730</td></tr><tr><td/><td colspan="3">Trans-P-RGF</td><td colspan="2">100%</td><td colspan="2">130</td><td>99.86%</td><td>371</td><td/><td colspan="2">99.18%</td><td>806</td><td colspan="3">99.86%</td><td>522</td></tr><tr><td/><td colspan="3">TREMBA</td><td colspan="2">100%</td><td colspan="2">88</td><td>100%</td><td>183</td><td/><td colspan="2">100%</td><td>172</td><td/><td colspan="2">100%</td><td>61</td></tr><tr><td/><td/><td/><td>VGG19</td><td/><td/><td colspan="2">Resnet34</td><td/><td/><td colspan="2">DenseNet121</td><td/><td/><td colspan="2">MobilenetV2</td></tr><tr><td/><td>100%</td><td/><td/><td/><td>100%</td><td/><td/><td colspan="2">100%</td><td/><td/><td/><td>100%</td><td/><td/></tr><tr><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/><td/><td>80%</td><td/><td/></tr><tr><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>Success Rate</td><td>20% 40% 60%</td><td/><td/><td>NES Trans-NESPGD Trans-NESFGSM AutoZOOM P-RGF Trans-P-RGF TREMBA</td></tr><tr><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/><td/><td>0%</td><td/><td/></tr><tr><td/><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td><td>10 2</td><td>10 3</td><td>Queries</td><td>10 4</td></tr></table>

Success rate and average queries of un-targeted attack on ImageNet. ε = 0.05

Table content: <table><tr><td>Attack</td><td colspan="2">VGG19</td><td colspan="2">Resnet34</td><td colspan="2">DenseNet121</td><td colspan="2">MobilenetV2</td></tr><tr><td/><td colspan="8">Success Queries Success Queries Success Queries Success Queries</td></tr><tr><td>NES</td><td>100%</td><td>651</td><td>100%</td><td>850</td><td>100%</td><td>840</td><td>99.86%</td><td>640</td></tr><tr><td colspan="2">Trans-NES PGD 100%</td><td>74</td><td>100%</td><td>196</td><td>100%</td><td>235</td><td>100%</td><td>169</td></tr><tr><td colspan="2">Trans-NES FGSM 100%</td><td>232</td><td>100%</td><td>401</td><td>100%</td><td>361</td><td>100%</td><td>272</td></tr><tr><td>AutoZOOM</td><td colspan="8">99.72% 1743 99.58% 1481 99.32% 1730 99.29% 1672</td></tr><tr><td>P-RGF</td><td>100%</td><td>178</td><td>100%</td><td>328</td><td>100%</td><td>436</td><td>100%</td><td>402</td></tr><tr><td>Trans-P-RGF</td><td>100%</td><td>44</td><td>99.44%</td><td>418</td><td colspan="2">98.09% 1049</td><td>100%</td><td>157</td></tr><tr><td>TREMBA</td><td>100%</td><td>8</td><td>100%</td><td>27</td><td>100%</td><td>19</td><td>100%</td><td>8</td></tr></table>

Success rate and average queries of targeted attack on ImageNet. ε = 0.05

Table content: <table><tr><td>Attack</td><td colspan="2">VGG19</td><td colspan="2">Resnet34</td><td colspan="2">DenseNet121</td><td colspan="2">MobilenetV2</td></tr><tr><td/><td colspan="8">Success Queries Success Queries Success Queries Success Queries</td></tr><tr><td>NES</td><td colspan="6">99.03% 6364 98.89% 8003 99.32% 7525</td><td>99.72$</td><td>5610</td></tr><tr><td colspan="9">Trans-NES PGD 99.31% 1968 99.31% 3549 99.46% 3731 99.86% 3223</td></tr><tr><td colspan="9">Trans-NES FGSM 99.03% 4997 98.33% 7298 98.23% 6874 99.16% 5034</td></tr><tr><td>AutoZOOM</td><td colspan="8">51.04% 30032 52.36% 28547 60.00% 25836 53.78% 28356</td></tr><tr><td>P-RGF</td><td colspan="8">99.17% 3704 98.05% 5498 97.96% 5769 98.17% 6896</td></tr><tr><td colspan="2">Trans-P-RGF 99.58%</td><td>662</td><td colspan="6">99.31% 1896 99.05% 2267 99.16% 3192</td></tr><tr><td>TREMBA</td><td>99.72%</td><td>285</td><td>99.44%</td><td>443</td><td>99.72%</td><td>224</td><td>99.72%</td><td>422</td></tr><tr><td colspan="5">settings are the same in Appendix A.2. As shown in Table</td><td/><td/><td/><td/></tr></table>

Hyperparameter sweep over b on Densenet121 for un-targeted attack on ImageNet

Table content: <table><tr><td>Sweep over b</td><td colspan="2">b = 10</td><td colspan="2">b = 30</td><td colspan="2">b = 40</td><td colspan="2">b = 50</td></tr><tr><td/><td colspan="8">Success Queries Success Queries Success Queries Success Queries</td></tr><tr><td>NES</td><td>100%</td><td>1323</td><td>100%</td><td>1284</td><td>100%</td><td>1433</td><td>100%</td><td>1639</td></tr><tr><td>Trans-NES PGD</td><td>100%</td><td>915</td><td>100%</td><td>791</td><td>100%</td><td>707</td><td>100%</td><td>639</td></tr><tr><td colspan="2">Trans-NES FGSM 100%</td><td>1037</td><td>100%</td><td>916</td><td>100%</td><td>879</td><td>100%</td><td>886</td></tr><tr><td>AutoZOOM</td><td>90.9%</td><td>6052</td><td>96.2%</td><td>4148</td><td>97.1%</td><td>4066</td><td>97.3%</td><td>4366</td></tr><tr><td>P-RGF</td><td>99.73%</td><td>717</td><td>99.86%</td><td>860</td><td>99.86%</td><td>949</td><td colspan="2">99.86% 1095</td></tr><tr><td colspan="4">Trans-P-RGF 98.50% 1139 99.86%</td><td>479</td><td>99.86%</td><td>487</td><td>100%</td><td>427</td></tr><tr><td>TREMBA</td><td>100%</td><td>150</td><td>100%</td><td>205</td><td>100%</td><td>274</td><td>100%</td><td>299</td></tr></table>

Change of dimension of the embedding space of AutoZOOM. The task is un-targeted attack on ImageNet. It is hard to say the overall classification of Trans-NES PGD is wrong. However, the labels of TREMBA are definitely not correct.

Table content: <table><tr><td>Attack</td><td colspan="2">VGG19</td><td colspan="2">Resnet34</td><td colspan="2">DenseNet121</td><td colspan="2">MobilenetV2</td></tr><tr><td colspan="9">Success Queries Success Queries Success Queries Success Queries</td></tr><tr><td colspan="9">AutoZOOM 64.35% 19684 71.94% 16931 68.44% 17871 71.15% 16134</td></tr><tr><td colspan="2">Trans-P-RGF 99.86%</td><td>194</td><td>99.58%</td><td>508</td><td>99.59%</td><td>610</td><td>99.58%</td><td>705</td></tr><tr><td>labels of the image.</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper proposed a new method for black-box adversarial attacks which tries to learn a low-dimensional embedding using a pretrained model and then performs efficient search within the embedding space to attack the target network. The proposed method can produce perturbation with semantic patterns are easily transferable. It can be used to improve the query efficiency in black-box attacks. - The main idea of this paper is quite simple, i.e., using a autoencoder model to capture encoding in the embedding space and then searching over the embedding space for possible attacks. While searching for adversarial examples in the embedding space is not something new, such as manifold attack or GAN-based attack, the authors claimed that by doing so, it can help reduce the query complexity of black-box attacks. However, it is not immediately clear to me why this can help reduce the query complexity, as intuitively, restricting the attack image space to an embedding space (or a manifold) will naturally increase the difficulty for finding adversarial examples. The authors’ explanation is not quite convincing to me since many adversarial examples are not necessarily on the embedding space. - Algorithm 1 is not clearly written and I do not understand the update rule in Algorithm 1. What is Li exactly? If Li means eq(1) or eq(2), it seems totally independent of sampled Guassian noise? Also, the update rule in Line 5 of Algorithm 1 is different from what is described in eq(4) or other black-box attack algorithms. Can the author explain the algorithm design with details? - In experiments section, the authors miss a few important black-box attack baselines. I would suggest the authors to further comment and compare with the following black-box attacks to better demonstrate the performance of the proposed algorithm. Ilyas, Andrew, Logan Engstrom, and Aleksander Madry. *Prior convictions: Black-box adversarial attacks with bandits and priors.* ICLR 2019. Moon, Seungyong, Gaon An, and Hyun Oh Song. *Parsimonious Black-Box Adversarial Attacks via Efficient Combinatorial Optimization.* ICML 2019. Chen, Jinghui, Jinfeng Yi, and Quanquan Gu. *A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks.* arXiv preprint arXiv:1811.10828 (2018). - Also can the authors further conduct experiments using more common choice of epsilon to help the reader get better understandings. For example, add ImageNet experiments with epsilon = 0.05. Detailed comments: - In section 3.2, the author suggests that by removing the sign function, the attacks can be more effective in (Li et al., 2019). I didn’t find the corresponding argument in (Li et al., 2019). Can the authors be more specific on this argument? ------------------------- I have read the response and it addressed my concerns. I will increase my score