AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks

Introduction

In recent years, “machine learning as a service” has offered the world an effortless access to powerful machine learning tools for a wide variety of tasks. For example, commercially available services such as Google Cloud Vision API and Clarifai.com provide well-trained image classifiers to the public. One is able to upload and obtain the class prediction results for images at hand at a low price. However, the existing and emerging machine learning platforms and their low model-access costs raise ever-increasing security concerns, as they also offer an ideal environment for testing malicious attempts. Even worse, the risks can be amplified when these services are used to build derived products such that the inherent security vulnerability could be leveraged by attackers.

In many computer vision tasks, DNN models achieve the state-of-the-art prediction accuracy and hence are widely deployed in modern machine learning services. Nonetheless, recent studies have highlighted DNNs’ vulnerability to adversarial perturbations. In the white-box setting in which the target model is entirely transparent to an attacker, visually imperceptible adversarial images can be easily crafted to fool a target DNN model towards misclassification by leveraging the input gradient information [\citeauthoryearSzegedy et al.2014, \citeauthoryearGoodfellow, Shlens, and Szegedy2015]. However, in the black-box setting in which the parameters of the deployed model are hidden and one can only observe the input-output correspondences of a queried example, crafting adversarial examples requires a gradient-free (zeroth order) optimization approach to gather necessary attack information. Figure 1 displays a prediction-evasive adversarial example crafted via iterative model queries from a black-box DNN (the Inception-v3 model [\citeauthoryearSzegedy et al.2016]) trained on ImageNet.

Albeit achieving remarkable attack effectiveness by the use of gradient estimation, current black-box attack methods, such as [\citeauthoryearChen et al.2017, \citeauthoryearNitin Bhagoji et al.2018], are not query-efficient since they exploit coordinate-wise gradient estimation and value update, which inevitably incurs an excessive number of model queries and may give a false sense of model robustness due to inefficient query designs. In this paper, we propose to tackle the preceding problem by using AutoZOOM, an Autoencoder-based Zeroth Order Optimization Method. AutoZOOM has two novel building blocks: (i) a new and adaptive random gradient estimation strategy to balance the query counts and distortion when crafting adversarial examples, and (ii) an autoencoder that is either trained offline on other unlabeled data, or based on a simple bilinear resizing operation, in order to accelerate black-box attacks. As illustrated in Figure 2, AutoZOOM utilizes a “decoder” to craft a high-dimensional adversarial perturbation from the (learned) low-dimensional latent-space representation, and its query efficiency can be well explained by the dimension-dependent convergence rate in gradient-free optimization.

Contributions. We summarize our main contributions and new insights on adversarial robustness as follows:

We propose AutoZOOM, a novel query-efficient black-box attack framework for generating adversarial examples. AutoZOOM features an adaptive random gradient estimation strategy and dimension reduction techniques (either an offline trained autoencoder or a bilinear resizer) to reduce attack query counts while maintaining attack effectiveness and visual similarity. To the best of our knowledge, AutoZOOM is the first black-box attack using random full gradient estimation and data-driven acceleration.

We use the convergence rate of zeroth-order optimization to motivate the query efficiency of AutoZOOM and provide an error analysis of the new gradient estimator in AutoZOOM to the true gradient for characterizing the trade-offs between estimation error and query counts.

When applied to a state-of-the-art black-box attack proposed in [\citeauthoryearChen et al.2017], AutoZOOM attains a similar attack success rate while achieving a significant reduction (at least 93%) in the mean query counts required to attack the DNN image classifiers for MNIST, CIFAR-10 and ImageNet. It can also fine-tune the distortion in the post-success stage by performing finer gradient estimation.

In the experiments, we also find that AutoZOOM with a simple bilinear resizer as the decoder (AutoZOOM-BiLIN) can attain noticeable query efficiency, despite that it is still worse than AutoZOOM with an offline trained autoencoder (AutoZOOM-AE). However, AutoZOOM-BiLIN is easier to be mounted as no additional training is required. The results also suggest an interesting finding that while learning effective low-dimensional representations of legitimate images is still a challenging task, black-box attacks using significantly less degree of freedoms (i.e., reduced dimensions) are certainly plausible.

Related Work

Gradient-based adversarial attacks on DNNs fall within the white-box setting, since acquiring the gradient with respect to the input requires knowing the weights of the target DNN. As a first attempt towards black-box attacks, the authors in [\citeauthoryearPapernot et al.2017] proposed to train a substitute model using iterative model queries, performing white-box attacks on the substitute model, and implementing transfer attacks to the target model [\citeauthoryearPapernot, McDaniel, and Goodfellow2016, \citeauthoryearLiu et al.2017]. However, its attack performance can be severely degraded due to poor attack transferability [\citeauthoryearSu et al.2018]. Although ZOO achieves a similar attack success rate and comparable visual quality as many white-box attack methods [\citeauthoryearChen et al.2017], its coordinate-wise gradient estimation requires excessive target model evaluations and is hence not query-efficient. The same gradient estimation technique is also used in [\citeauthoryearNitin Bhagoji et al.2018].

Beyond optimization-based approaches, the authors in [\citeauthoryearIlyas et al.2018] proposed to use a natural evolution strategy (NES) to enhance query efficiency. Although there is a vector-wise gradient estimation step in the NES attack, we treat it as a parallel work since its natural evolutionary step is out of the scope of black-box attacks using zeroth-order gradient descent. We also note that different from NES, our AutoZOOM framework uses a theory-driven query-efficient random-vector based gradient estimation strategy. In addition, AutoZOOM could be applied to further improve the query efficiency of NES, since NES does not take into account the factor of attack dimension reduction, which is the novelty in AutoZOOM as well as the main focus of this paper.

Under a more restricted attack setting, where only the decision (top-1 prediction class) is known to an attacker, the authors in [\citeauthoryearBrendel, Rauber, and Bethge2018] proposed a random-walk based attack around the decision boundary. Such a black-box attack dispenses class prediction scores and hence requires additional model queries. Due to space limitation, we provide more background and a table comparing existing black-box attacks in the supplementary material.

AutoZOOM: Background and Methods

Here we formulate black-box targeted attacks. The formulation can be easily adapted to untargeted attacks. Let $(\mathbf{x}_{0},t_{0})$ denote a natural image $\mathbf{x}_{0}$ and its ground-truth class label $t_{0}$, and let ($\mathbf{x},t$) denote the adversarial example of $\mathbf{x}_{0}$ and the target attack class label $t\neq t_{0}$. The problem of finding an adversarial example can be formulated as an optimization problem taking the generic form of

where $\textnormal{Dist}(\mathbf{x},\mathbf{x}_{0})$ measures the distortion between $\mathbf{x}$ and $\mathbf{x}_{0}$, $\textnormal{Loss}(\cdot)$ is an attack objective reflecting the likelihood of predicting $t=\arg\max_{k\in\{1,\ldots,K\}}[M(F(\mathbf{x}))]_{k}$, $\lambda$ is a regularization coefficient, and the constraint $\mathbf{x}\in^{d}$ confines the adversarial image $\mathbf{x}$ to the valid image space. The distortion $\textnormal{Dist}(\mathbf{x},\mathbf{x}_{0})$ is often evaluated by the $L_{p}$ norm defined as $\textnormal{Dist}(\mathbf{x},\mathbf{x}_{0})=\|\mathbf{x}-\mathbf{x}_{0}\|_{p}=\|\boldsymbol{\delta}\|_{p}=\sum_{i=1}^{d}|\boldsymbol{\delta}_{i}|^{1/p}$ for $p\geq 1$, where $\boldsymbol{\delta}=\mathbf{x}-\mathbf{x}_{0}$ is the adversarial perturbation to $\mathbf{x}_{0}$. The attack objective $\textnormal{Loss}(\cdot)$ can be the training loss of DNNs [\citeauthoryearGoodfellow, Shlens, and Szegedy2015] or some designed loss based on model predictions [\citeauthoryearCarlini and Wagner2017b].

In the white-box setting, an adversarial example is generated by using downstream optimizers such as ADAM [\citeauthoryearKingma and Ba2015] to solve (1); this requires the gradient $\nabla f(\mathbf{x})$ of the objective function $f(\mathbf{x})=\textnormal{Dist}(\mathbf{x},\mathbf{x}_{0})+\lambda\cdot\textnormal{Loss}(\mathbf{x},M(F(x)),t)$ relative to the input of $F$ via back-propagation in DNNs. However, in the black-box setting, acquiring $\nabla f(\cdot)$ is implausible, and one can only obtain the function evaluation $F(\cdot)$, which renders solving (1) a zeroth order optimization problem. Recently, zeroth order optimization approaches [\citeauthoryearGhadimi and Lan2013, \citeauthoryearNesterov and Spokoiny2017, \citeauthoryearLiu et al.2018] circumvent the preceding challenge by approximating the true gradient via function evaluations. Specifically, in black-box attacks, the gradient estimate is applied to both gradient computation and descent in the optimization process for solving (1).

2 Random Vector based Gradient Estimation

As a first attempt to enable gradient-free black-box attacks on DNNs, the authors in [\citeauthoryearChen et al.2017] use the symmetric difference quotient method [\citeauthoryearLax and Terrell2014] to evaluate the gradient $\frac{\partial f(\mathbf{x})}{\partial\mathbf{x}_{i}}$ of the $i$-th component by

using a small $h$. Here $\mathbf{e}_{i}$ denotes the $i$-th elementary basis. Albeit contributing to powerful black-box attacks and applicable to large networks like ImageNet, the nature of coordinate-wise gradient estimation step in (2) must incur an enormous amount of model queries and is hence not query-efficient. For example, the ImageNet dataset has $d=299\times 299\times 3\approx 270,000$ input dimensions, rendering coordinate-wise zeroth order optimization based on gradient estimation query-inefficient.

To improve query efficiency, we dispense with coordinate-wise estimation and instead propose a scaled random full gradient estimator of $\nabla f(\mathbf{x})$, defined as

where $\beta>0$ is a smoothing parameter, $\mathbf{u}$ is a unit-length vector that is uniformly drawn at random from a unit Euclidean sphere, and $b$ is a tunable scaling parameter that balances the bias and variance trade-off of the gradient estimation error. Note that with $b=1$, the gradient estimator in (3) becomes the one used in [\citeauthoryearDuchi et al.2015]. With $b=d$, this estimator becomes the one adopted in [\citeauthoryearGao, Jiang, and Zhang2014]. We will provide an optimal value $b^{*}$ for balancing query efficiency and estimation error in the following analysis.

Averaged random gradient estimation. To effectively control the error in gradient estimation, we consider a more general gradient estimator, in which the gradient estimate is averaged over $q$ random directions $\{\mathbf{u}_{j}\}_{j=1}^{q}$. That is,

where $\mathbf{g}_{j}$ is a gradient estimate defined in (3) with $\mathbf{u}=\mathbf{u}_{j}$. The use of multiple random directions can reduce the variance of $\overline{\mathbf{g}}$ in (4) for convex loss functions [\citeauthoryearDuchi et al.2015, \citeauthoryearLiu et al.2018].

Below we establish an error analysis of the averaged random gradient estimator in (4) for studying the influence of the parameters $b$ and $q$ on estimation error and query efficiency.

The proof is given in the supplementary file. ∎

Here we highlight the important implications based on Theorem 1: (i) The error analysis holds when $f$ is non-convex; (ii) In DNNs, the true gradient $\nabla f$ can be viewed as the numerical gradient obtained via back-propagation; (iii) For any fixed $b$, selecting a small $\beta$ (e.g., we set $\beta=1/d$ in AutoZOOM) can effectively reduce the last error term in (1), and we therefore focus on optimizing the first error term; (iv) The first error term in (1) exhibits the influence of $b$ and $q$ on the estimation error, and is independent of $\beta$. We further elaborate on (iv) as follows. Fixing $q$ and let $\eta(b)=\frac{b^{2}}{d^{2}}+\frac{b^{2}}{dq}+\frac{(b-d)^{2}}{d^{2}}$ to be the coefficient of the first error term in (1), then the optimal $b$ that minimizes $\eta(b)$ is $b^{*}=\frac{dq}{2q+d}$. For query efficiency, one would like to keep $q$ small, which then implies $b^{*}\approx q$ and $\eta(b^{*})\approx 1$ when the dimension $d$ is large. On the other hand, when $q\rightarrow\infty$, $b^{*}\approx d/2$ and $\eta(b^{*})\approx 1/2$, which yields a smaller error upper bound but is query-inefficient. We also note that by setting $b=q$, the coefficient $\eta(b)=\frac{b^{2}}{d^{2}}+\frac{b^{2}}{dq}+\frac{(b-d)^{2}}{d^{2}}\approx 1$ and thus is independent of the dimension $d$ and the parameter $q$.

Adaptive random gradient estimation. Based on Theorem 1 and our error analysis, in AutoZOOM we set $b=q$ in (3) and propose to use an adaptive strategy for selecting $q$. AutoZOOM uses $q=1$ (i.e., the fewest possible model evaluation) to first obtain rough gradient estimates for solving (1) until a successful adversarial image is found. After the initial attack success, it switches to use more accurate gradient estimates with $q>1$ to fine-tune the image quality. The trade-off between $q$ (which is proportional to query counts) and distortion reduction will be investigated in Section 4.

3 Attack Dimension Reduction via Autoencoder

Dimension-dependent convergence rate using gradient estimation. Different from the first order convergence results, the convergence rate of zeroth order gradient descent methods has an additional multiplicative dimension-dependent factor $d$. In the convex loss setting the rate is $O(\sqrt{d/T})$, where $T$ is the number of iterations [\citeauthoryearNesterov and Spokoiny2017, \citeauthoryearLiu et al.2018, \citeauthoryearGao, Jiang, and Zhang2014, \citeauthoryearWang et al.2018]. The same convergence rate has also been found in the nonconvex setting [\citeauthoryearGhadimi and Lan2013]. The dimension-dependent convergence factor $d$ suggests that vanilla black-box attacks using gradient estimations can be query inefficient when the (vectorized) image dimension $d$ is large, due to the curse of dimensionality in convergence. This also motivates us to propose using an autoencoder to reduce the attack dimension and improve query efficiency in black-box attacks.

Why AE? Our proposal of AE is motivated by the insightful findings in [\citeauthoryearGoodfellow, Shlens, and Szegedy2015] that a successful adversarial perturbation is highly relevant to some human-imperceptible noise pattern resembling the shape of the target class, known as the “shadow”. Since a decoder in AE learns to reconstruct data from latent representations, it can also provide distributional guidance for mapping adversarial perturbations to generate these shadows.

We also note that for any reduced dimension $d^{\prime}$, the setting $b^{*}=q$ is optimal in terms of minimizing the corresponding estimation error from Theorem 1, despite the fact that the gradient estimation errors of different reduced dimensions cannot be directly compared. In Section 4 we will report the superior query efficiency in black-box attacks achieved with the use of AE or BiLIN as the decoder, and discuss the benefit of attack dimension reduction.

4 AutoZOOM Algorithm

Algorithm 1 summarizes the AutoZOOM framework towards query-efficient black-box attacks on DNNs. We also note that AutoZOOM is a general acceleration tool that is compatible with any gradient-estimation based black-box adversarial attack obeying the attack formulation in (1). It also has some theoretical estimation error guarantees and query-efficient parameter selection based on Theorem 1. The details on adjusting the regularization coefficient $\lambda$ and the query parameter $q$ based on run-time model evaluation results will be discussed in Section 4. Our source code is publicly available https://github.com/IBM/Autozoom-Attack.

Performance Evaluation

This section presents the experiments for assessing the performance of AutoZOOM in accelerating black-box attacks on DNNs in terms of the number of queries required for an initial attack success and for a specific distortion level.

As described in Section 3, AutoZOOM is a query-efficient gradient-free optimization framework for solving the black-box attack formulation in (1). In the following experiments, we demonstrate the utility of AutoZOOM by using the same attack formulation proposed in ZOO [\citeauthoryearChen et al.2017], which uses the squared $L_{2}$ norm as the distortion measure $\textnormal{Dist}(\cdot)$ and adopts the attack objective

where this hinge function is designed for targeted black-box attacks on the DNN model $F$, and the monotonic transformation $M(\cdot)=\log(\cdot)$ is applied to the model output.

2 Comparative Black-box Attack Methods

We compare AutoZOOM-AE ($D=\textnormal{AE}$) and AutoZOOM-BiLIN ($D=\textnormal{BiLIN}$) with two different baselines: (i) Standard ZOO implementation https://github.com/huanzhang12/ZOO-Attack with bilinear scaling (same as BiLIN) for dimension reduction; (ii) ZOO+AE, which is ZOO with AE. Note that all attacks indeed generate adversarial perturbations based on the same reduced attack dimension.

3 Experiment Setup, Evaluation, Datasets and AutoZOOM Implementation

We assess the performance of different attack methods on several representative benchmark datasets, including MNIST [\citeauthoryearLeCun et al.1998], CIFAR-10 [\citeauthoryearKrizhevsky2009] and ImageNet [\citeauthoryearRussakovsky et al.2015]. For MNIST and CIFAR-10, we use the same DNN image classification models https://github.com/carlini/nn_robust_attacks as in [\citeauthoryearCarlini and Wagner2017b]. For ImageNet, we use the Inception-v3 model [\citeauthoryearSzegedy et al.2016]. All experiments were conducted using TensorFlow Machine-Learning Library [\citeauthoryearAbadi et al.] on machines equipped with an Intel Xeon E5-2690v3 CPU and an Nvidia Tesla K80 GPU.

All attacks used ADAM [\citeauthoryearKingma and Ba2015] for solving (1) with their estimated gradients and the same initial learning rate $2\times 10^{-3}$. On MNIST and CIFAR-10, all methods adopt 1,000 ADAM iterations. On ImageNet, ZOO and ZOO+AE adopt 20,000 iterations, whereas AutoZOOM-BiLIN and AutoZOOM-AE adopt 100,000 iterations. Note that due to different gradient estimation methods, the query counts (i.e., the number of model evaluations) per iteration of a black-box attack may vary. ZOO and ZOO+AE use the parallel gradient update of (2) with a batch of $128$ pixels, yielding 256 query counts per iteration. AutoZOOM-BiLIN and AutoZOOM-AE use the averaged random full gradient estimator in (4), resulting in $q+1$ query counts per iteration. For a fair comparison, the query counts are used for performance assessment.

Query reduction ratio. We use the mean query counts of ZOO with the smallest $\lambda_{\textnormal{ini}}$ as the baseline for computing the query reduction ratio of other methods and configurations.

Post-success fine-tuning. When implementing AutoZOOM in Algorithm 1, on MNIST and CIFAR-10 we find that AutoZOOM without fine-tuning (i.e., $q=1$) already yields similar distortion as ZOO. We note that ZOO can be viewed as coordinate-wise fine-tuning and is thus query-inefficient. On ImageNet, we will investigate the effect of post-success fine-tuning on reducing distortion.

Autoencoder Training. In AutoZOOM-AE, we use convolutional autoencoders for attack dimension reduction, which are trained on unlabeled datasets that are different from the training dataset and the attacked natural examples. The implementation details are given in the supplementary material.

Dynamic Switching on $\lambda$. To adjust the regularization coefficient $\lambda$ in (1), in all methods we set its initial value $\lambda_{\textnormal{ini}}\in\{0.1,1,10\}$ on MNIST and CIFAR-10, and set $\lambda_{\textnormal{ini}}=10$ on ImageNet. Furthermore, for balancing the distortion Dist and the attack objective Loss in (1), we use a dynamic switching strategy to update $\lambda$ during the optimization process. Per every $S$ iterations, $\lambda$ is multiplied by 10 times of the current value if the attack has never been successful. Otherwise, it divides its current value by 2. On MNIST and CIFAR-10, we set $S=100$. On ImageNet, we set $S=1,000$. At the instance of initial success, we also reset $\lambda=\lambda_{\textnormal{ini}}$ and the ADAM parameters to the default values, as doing so can empirically reduce the distortion for all attack methods.

4 Black-box Attacks on MNIST and CIFAR-10

For both MNIST and CIFAR-10, we randomly select 50 correctly classified images from their test sets, and perform targeted attacks on these images. Since both datasets have 10 classes, each selected image is attacked 9 times, targeting at all but its true class. For all attacks, the ratio of reduced attack-space dimension to the original one (i.e., $d^{\prime}/d$) is 25% for MNIST and 6.25% for CIFAR-10.

Table 1 shows the performance evaluation on MNIST with various values of $\lambda_{\textnormal{ini}}$, the initial value of the regularization coefficient $\lambda$ in (1). We use the performance of ZOO with $\lambda_{\textnormal{ini}}=0.1$ as a baseline for comparison. For example, with $\lambda_{\textnormal{ini}}=$ $0.1$ and $10$, the mean query counts required by AutoZOOM-AE to attain an initial success is reduced by 93.21% and 98.57%, respectively. One can also observe that allowing larger $\lambda_{\textnormal{ini}}$ generally leads to fewer mean query counts at the price of slightly increased distortion for the initial attack. The noticeable huge difference in the required attack query counts between AutoZOOM and ZOO/ZOO+AE validates the effectiveness of our proposed random full gradient estimator in (3), which dispenses with the coordinate-wise gradient estimation in ZOO but still remains comparable true positive rates, thereby greatly improving query efficiency.

For CIFAR-10, we report similar query efficiency improvements as displayed in Table 2. In particular, comparing the two query-efficient black-box attack methods (AutoZOOM-BiLIN and AutoZOOM-AE), we find that AutoZOOM-AE is more query-efficient than AutoZOOM-BiLIN, but at the cost of an additional AE training step. AutoZOOM-AE achieves the highest attack success rates (ASRs) and mean query reduction ratios for different values of $\lambda_{\textnormal{ini}}$. In addition, their true positive rates (TPRs) are similar but AutoZOOM-AE usually takes fewer query counts to reach the same $L_{2}$ distortion. We note that when $\lambda_{\textnormal{ini}}=10$, AutoZOOM-AE has a higher TPR but also needs slightly more mean query counts than AutoZOOM-BiLIN to reach the same $L_{2}$ distortion. This suggests that there are some adversarial examples that are difficult for a bilinear resizer to reduce their post-success distortions but can be handled by an AE.

5 Black-box Attacks on ImageNet

We selected 50 correctly classified images from the ImageNet test set to perform random targeted attacks and set $\lambda_{\textnormal{ini}}=10$ and the attack dimension reduction ratio to 1.15%. The results are summarized in Table 3. Note that comparing to ZOO, AutoZOOM-AE can significantly reduce the query count required to achieve an initial success by 99.39% (or 99.35% to reach the same $L_{2}$ distortion), which is a remarkable improvement since this means reducing more than 2.2 million model queries given the fact that the dimension of ImageNet ($\approx$ 270K) is much larger than that of MNIST and CIFAR-10.

Post-success distortion refinement. As described in Algorithm 1, adaptive random gradient estimation is integrated in AutoZOOM, offering a quick initial success in attack generation followed by a fine-tuning process to effectively reduce the distortion. This is achieved by adjusting the gradient estimate averaging parameter $q$ in (4) in the post-success stage. In general, averaging over more random directions (i.e., setting larger $q$) tends to better reduce the variance of gradient estimation error, but at the cost of increased model queries. Figure 3 (a) shows the mean distortion against query counts for various choices of $q$ in the post-success stage. The results suggest that setting some small $q$ but $q>1$ can further decrease the distortion at the converged phase when compared with the case of $q=1$. Moreover, the refinement effect on distortion empirically saturates at $q=4$, implying a marginal gain beyond this value. These findings also demonstrate that our proposed AutoZOOM indeed strikes a balance between distortion and query efficiency in black-box attacks.

6 Dimension Reduction and Query Efficiency

In addition to the motivation from the $O(\sqrt{d/T})$ convergence rate in zeroth-order optimization (Sec. 3.3), as a sanity check, we corroborate the benefit of attack dimension reduction to query efficiency in black-box attacks by comparing AutoZOOM (here we use $D=\textnormal{AE}$) with its alternative operated on the original (non-reduced) dimension (i.e., $\delta^{\prime}=D(\delta^{\prime})=\delta$). Tested on all three datasets and aforementioned settings, Figure 3 (b) shows the corresponding mean query count to initial success and the mean query reduction ratio when $\lambda_{\textnormal{ini}}=10$ in all three datasets. When compared to the attack results of the original dimension, attack dimension reduction through AutoZOOM reduces roughly 35-40% query counts on MNIST and CIFAR-10 and at least 95% on ImageNet. This result highlights the importance of dimension reduction towards query-efficient black-box attacks. For example, without dimension reduction, the attack on the original ImageNet dimension cannot even be successful within the query budge ($Q=200K$ queries).

7 Additional Remarks and Discussion

$\bullet$ In addition to benchmarking on initial attack success, the query reduction ratio when reaching the same $L_{2}$ distortion can be directly computed from the last column in each table. $\bullet$ The attack gain in AutoZOOM-AE versus AutoZOOM-BiLIN could sometimes be marginal, while we also note that there is room for improving AutoZOOM-AE by exploring different AE models. However, we advocate AutoZOOM-BiLIN as a practically ideal candidate for query-efficient black-box attacks when testing model robustness, due to its easy-to-mount nature and it has no additional training cost. $\bullet$ While learning effective low-dimensional representations of legitimate images is still a challenging task, black-box attacks using significantly less degree of freedoms (i.e., reduced dimensions), as demonstrated in this paper, are certainly plausible, leading to new implications on model robustness.

Conclusion

AutoZOOM is a generic attack acceleration framework that is compatible with any gradient-estimation based black-box attack having the general formulation in (1). It adopts a new and adaptive random full gradient estimation strategy to strike a balance between query counts and estimation errors, and features a decoder (AE or BiLIN) for attack dimension reduction and algorithmic convergence acceleration. Compared to a state-of-the-art attack (ZOO), AutoZOOM consistently reduces the mean query counts when attacking black-box DNN image classifiers for MNIST, CIFAT-10 and ImageNet, attaining at least $93\%$ query reduction in finding initial successful adversarial examples (or reaching the same distortion) while maintaining a similar attack success rate. It can also efficiently fine-tune the image distortion to maintain high visual similarity to the original image. Consequently, AutoZOOM provides novel and efficient means for assessing the robustness of deployed machine learning models.

Acknowledgements

Shin-Ming Cheng was supported in part by the Ministry of Science and Technology, Taiwan, under Grants MOST 107-2218-E-001-005 and MOST 107-2218-E-011-012. Cho-Jui Hsieh and Huan Zhang acknowledge the support by NSF IIS-1719097, Intel faculty award, Google Cloud and NVIDIA.

References

Supplementary Material

Appendix A More Background on Adversarial Attacks and Defenses

The research in generating adversarial examples to deceive machine-learning models, known as adversarial attacks, tends to evolve with the advance of machine-learning techniques and new publicly available datasets. In [\citeauthoryearLowd and Meek2005], the authors studied adversarial attacks to linear classifiers with continuous or Boolean features. In [\citeauthoryearBiggio et al.2013], the authors proposed a gradient-based adversarial attack on kernel support vector machines (SVMs). More recently, gradient-based approaches are also used in adversarial attacks on image classifiers trained by DNNs [\citeauthoryearSzegedy et al.2014, \citeauthoryearGoodfellow, Shlens, and Szegedy2015]. Due to space limitation, we focus on related work in adversarial attacks on DNNs. Interested readers may refer to the survey paper [\citeauthoryearBiggio and Roli2018] for more details.

Gradient-based adversarial attacks on DNNs fall within the white-box setting, since acquiring the gradient with respect to the input requires knowing the weights of the target DNN. In principle, adversarial attacks can be formulated as an optimization problem of minimizing the adversarial perturbation while ensuring attack objectives. In image classification, given a natural image, an untargeted attack aims to find a visually similar adversarial image resulting in a different class prediction, while a targeted attack aims to find an adversarial image leading to a specific class prediction. The visual similarity between a pair of adversarial and natural images is often measured by the $L_{p}$ norm of their difference, where $p\geq 1$. Existing powerful white-box adversarial attacks using $L_{\infty}$, $L_{2}$ or $L_{1}$ norms include iterative fast gradient sign methods [\citeauthoryearKurakin, Goodfellow, and Bengio2017], Carlini and Wagner’s (C&W) attack [\citeauthoryearCarlini and Wagner2017b], elastic-net attacks to DNNs (EAD) [\citeauthoryearChen et al.2018], etc.

Black-box adversarial attacks are practical threats to the deployed machine-learning services. Attackers can observe the input-output correspondences of any queried input, but the target model parameters are completely hidden. Therefore, gradient-based adversarial attacks are inapplicable to a black-box setting. As a first attempt, the authors in [\citeauthoryearPapernot et al.2017] proposed to train a substitute model using iterative model queries, perform white-box attacks on the substitute model, and leverage the transferability of adversarial examples [\citeauthoryearPapernot, McDaniel, and Goodfellow2016, \citeauthoryearLiu et al.2017] to attack the target model. However, training a representative surrogate for a DNN is challenging due to the complicated and nonlinear classification rules of DNNs and high dimensionality of the underlying dataset. The performance of black-box attacks can be severely degraded if the adversarial examples for the substitute model transfer poorly to the target model. To bridge this gap, the authors in [\citeauthoryearChen et al.2017] proposed a black-box attack called ZOO that directly estimates the gradient of the attack objective by iteratively querying the target model. Although ZOO achieves a similar attack success rate and comparable visual quality as many white-box attack methods, it exploits the symmetric difference quotient method [\citeauthoryearLax and Terrell2014] for coordinate-wise gradient estimation and value update, which requires excessive target model evaluations and is hence not query-efficient. The same gradient estimation technique is also used in the later work in [\citeauthoryearNitin Bhagoji et al.2018]. Although acceleration techniques such as importance sampling, bilinear scaling and random feature grouping have been used in [\citeauthoryearChen et al.2017, \citeauthoryearNitin Bhagoji et al.2018], the coordinate-wise gradient estimation approach still forms a bottleneck for query efficiency.

Beyond optimization-based approaches, the authors in [\citeauthoryearIlyas et al.2018] proposed to use a natural evolution strategy (NES) to enhance query efficiency. Although there is also a vector-wise gradient estimation step in the NES attack, we treat it as an independent and parallel work since its natural evolutionary step is out of the scope of black-box attacks using zeroth-order gradient descent. We also note that different from NES, our AutoZOOM framework uses a query-efficient random gradient estimation strategy. In addition, AutoZOOM could be applied to further improve the query efficiency of NES, since NES does not take into account the factor of attack dimension reduction, which is the main focus of this paper. Under a more restricted setting, where only the decision (top-1 prediction class) is known to an attacker, the authors in [\citeauthoryearBrendel, Rauber, and Bethge2018] proposed a random-walk based attack around the decision boundary. Such a black-box attack dispenses class prediction scores and hence requires additional model queries.

In this paper, we focus on improving the query efficiency of gradient-estimation and gradient-descent based black-box attacks and consider the threat model when the class prediction scores are known to an attacker. For reader’s reference, we compare existing black-box attacks on DNNs with AutoZOOM in Table S1. One unique feature of AutoZOOM is the use of reduced attack dimension when mounting black-box attacks, which is an unlabeled data-driven technique (autoencoder) for attack acceleration, and has not been studied thoroughly in existing attacks. While white-box attacks such as [\citeauthoryearBaluja and Fischer2018] have utilized autoencoders trained on the training data and the transparent logit representations of DNNs, we propose in this work to use autoencoders trained on unlabeled natural data to improve query efficiency for black-box attacks.

There has been many methods proposed for defending adversarial attacks to DNNs. However, new defenses are continuously weakened by follow-up attacks [\citeauthoryearCarlini and Wagner2017a, \citeauthoryearAthalye, Carlini, and Wagner2018]. For instance, model ensembles [\citeauthoryearTramèr et al.2018] were shown to be effective against some black-box attacks, while they are recently circumvented by advanced attack techniques [\citeauthoryearIlyas2018]. In this paper, we focus on improving query efficiency in attacking black-box undefended DNNs.

Appendix B Proof of Theorem 1

Recall that the data dimension is $d$ and we assume $f$ to be differentiable and its gradient $\nabla f$ to be $L$-Lipschitz. Fixing $\beta$ and consider a smoothed version of $f$:

Based on [\citeauthoryearGao, Jiang, and Zhang2014, Lemma 4.1-a], we have the relation

where we recall that $\mathbf{g}$ has been defined in (3). Moreover, based on [\citeauthoryearGao, Jiang, and Zhang2014, Lemma 4.1-b], we have

where $\|\boldsymbol{\epsilon}\|_{2}\leq\frac{b\beta L}{2}.$

Once again, by applying [\citeauthoryearGao, Jiang, and Zhang2014, Lemma 4.1-b], we can easily obtain that

Now, let us consider the averaged random gradient estimator in (4),

Due to the properties of i.i.d. samples $\{\mathbf{u}_{i}\}$ and (S5), we define

From (S6), we also obtain that for any $i$,

Substituting (S11) and (S12) into (S10), we obtain

Finally, we bound the mean squared estimation error as

Appendix C Architectures of Convolutional Autoencoders in AutoZOOM

On MNIST, the convolutional autoencoder (CAE) is trained on 50,000 randomly selected hand-written digits from the MNIST8M dataset http://leon.bottou.org/projects/infimnist. On CIFAR-10, the CAE is trained on 9,900 images selected from its test dataset. The remaining images are used in black-box attacks. On ImageNet, all the attacked natural images are from 10 randomly selected image labels, and these labels are also used as the candidate attack targets. The CAE is trained on about 9000 images from these classes.

Table S2 shows the architectures for all the autoencoders used in this work. Note that the autoencoders designed for ImageNet uses bilinear scaling to transform data size from $299\times 299\times Dep$ to $128\times 128\times Dep$, and also back from $128\times 128\times Dep$ to $299\times 299\times Dep$. This is to allow easy processing and handling for the autoencoder’s internal convolutional layers.

The normalized mean squared error of our autoencoder trained on MNIST, CIFAR-10 and 25 Imagenet is 0.0027, 0.0049 and 0.0151, respectively, which lies within a reasonable range of compression loss.

Appendix D More Adversarial Examples of Attacking Inception-v3 in the Black-box Setting

Figure S1 shows other adversarial examples of the Inception-v3 model in the black-box targeted attack setting.

Appendix E Performance Evaluation of Black-box Untargeted Attacks

Table S3 shows the attacking performance of black-box untargeted attacks on MNIST, CIFAR-10 and ImageNet using ZOO and AutoZOOM-BiLIN attacks on the same set of images in Section 4.5. The Loss function is defined as

where $t_{0}$ is the top-1 prediction label of a natural image $\mathbf{x}_{0}$. We set $\lambda_{\textnormal{ini}}=10$ and use $q=5$ on MNIST and CIFAR-10 and $q=4$ on ImageNet for distortion fine-tuning in the post-attack phase. Comparing to Table 3, the number of model queries can be further reduced since untargeted attacks only require the adversarial images to be classified as any class other than $t_{0}$ rather than classified as a specific class $t\neq t_{0}$.