CorrAttack: Black-box Adversarial Attack with Structured Search

Although deep learning has many applications, it is known that neural networks are vulnerable to adversarial examples, which are small perturbations of inputs that can fool neural networks into making wrong predictions (Szegedy et al., 2014). While adversarial noise can easily be found when the neural models are known (referred to as white-box attack) (Kurakin et al., 2016). However, in real world scenarios models are often unknown, this situation is referred to as black-box attack.

Some methods (Liu et al., 2016; Papernot et al., 2016) use the transfer-based attack, which generates adversarial examples on a substitute model and transfer the adversarial noise to the target model. However, the transferability is limited and its effectiveness relies highly on the similarity between the networks (Huang & Zhang, 2020). If two networks are very different, transfer-based methods will have low success rates.

In practice, most computer vision API such as the Google Cloud Vision API allow users to access the scores or probabilities of the classification results. Therefore, the attacker may query the black-box model and perform zeroth order optimization to find an adversarial example without the knowledge of the target model. Due to the availability of scores, this scenario is called score-based attack.

There have been a line of studies on black-box attack which directly estimate the gradient direction of the underlying model, and apply (stochastic) gradient descent to the input image (Ilyas et al., 2018; 2019; Chen et al., 2017; Huang & Zhang, 2020; Tu et al., 2018; Li et al., 2019). In this paper, we take another approach and formulate score-based attack as a time-varying contextual bandits problem. At each state, the attacker may change the adversarial perturbation and get the reward as the reduction of the loss. And the attacker would receive some features about the arms before making the decision. By limiting the action space to image blocks, the associated bandits problem exhibits local correlation structures and the slow varying property suitable for learning. Therefore, we may use the location and other features of the blocks to estimate the reward for the future selection of the actions.

Using the above insights, we propose a new method called CorrAttack, which utilizes the local correlation structure and the slow varying property of the underlying bandits problem. CorrAttack uses Bayesian optimization with Gaussian process regression (Rasmussen, 2003) to model the correlation and select optimal actions. A forgetting strategy is added to the algorithm so that the Gaussian process regression can handle the time-varying changes. CorrAttack can effectively find blocks with the largest rewards. The resulting method achieves much lower numbers of average queries and higher success rates than prior methods with a similar action space (Moon et al., 2019).

It is worth noting that BayesOpt (Ru et al., 2020) and Bayes-Attack (Shukla et al., 2019) also employ Bayesian optimization for score-based attack. However, their Gaussian process regression directly models the loss as a function of the image, whose dimension can be more than one thousand. Therefore, the speed of BayesOpt is extremely slow. CorrAttack, on the other hand, searches over a much limited action space models the reward as a function of the low dimensional feature. Therefore, the optimization of CorrAttack is more efficient, and the method is significantly faster than BayesOpt.

We summarize the contributions of this work as follows:

1. 1.

   We formulate the score-based adversarial attack as a time-varying contextual bandits, and show that the reward function has slow varying properties. In our new formulation, the attacker could take advantage of the features to model the reward of the arms with learning techniques. Compared to the traditional approach, the use of learning in the proposed framework greatly improves the efficiency of searching over optimal actions.

2. 2.

   We propose a new method, CorrAttack, which uses Bayesian optimization with Gaussian process regression to learn the reward of each action, by using the feature of the arms.

3. 3.

   The experiments show that CorrAttack achieves the state of the art performance on ImageNet and Google Cloud Vision API for both defended and undefended models.

There have been a line of works focusing on black-box adversarial attack. Here, we give a brief review of various existing methods.

Transfer-Based Attack Transfer-based attack assumes the transferability of adversarial examples across different neural networks. It starts with a substitute model that is in the same domain as the target model. The adversaries can be easily generated on the white-box substitute model, and be transferred to attack the target model (Papernot et al., 2016). The approach, however, depends highly on the similarity of the networks. If two networks are distinct, the success rate of transferred attack would rapidly decrease (Huang & Zhang, 2020). Besides, the substitute model requires a lot of training data, which may not be realistic in practical applications. It may require querying the target model to build a synthetic dataset (Papernot et al., 2016).

Score-based Attack Many approaches estimate the gradient with the output scores of the target network. However, the high dimensionality of input images makes naive coordinate-wise search impossible as it requires millions of queries. ZOO (Chen et al., 2017) is an early work of gradient estimation, which estimates the gradient of an image block and perform block-wise gradient descent. NES (Wierstra et al., 2008) and CMA-ES (Meunier et al., 2019) are query efficient methods based on evolution strategy. Instead of the gradient itself, SignHunter (Al-Dujaili & O’Reilly, 2020) just estimates the sign of gradient to reduce the complexity. AutoZOOM uses bilinear transformation or autoencoder to reduce the sampling space and accelerate the optimization process. In the same spirit, data prior can be used to improve query efficiency (Ilyas et al., 2019). Besides, MetaAttack (Du et al., 2020) takes a meta learning approach to learn gradient patterns from prior information, which reduces queries for attacking targeted model.

Many zeroth order optimization methods for black-box attacks rely on gradient estimation. However, there are some research works using gradient free methods to perform black-box attack. BayesOpt and Bayes-Attack (Ru et al., 2020; Shukla et al., 2019) employ Bayesian optimization to find the adversarial examples. They use Gaussian process regression on the embedding and apply bilinear transformation to resize the embedding to the size of image. Although the bilinear transformation could alleviate the high dimensionality of images, the dimension of the embedding space is still in the thousands, which makes Bayesian optimization very ineffective and computationally expensive. A different method, PARSI, poses the attack on $\ell_{\infty}$ norm as a discrete optimization problem over $\{-\varepsilon,\varepsilon\}^{d}$ (Moon et al., 2019). It uses a Lazy-Greedy algorithm to search over the space $\{-\varepsilon,\varepsilon\}^{d}$ to find an adversarial example. SimBA (Guo et al., 2018) also employs a discrete search space targeted at $\ell_{2}$ norm.

Decision-based Attack Decision-based attack assumes the attacker could only get the output label of the model. Boundary Attack and its variants (Brendel et al., 2017; Chen et al., 2020; Li et al., 2020) are designed for the setting. However, the information received by the attacker is much smaller than score-based attack, and it would take many more queries than score-based attack to successfully attack an image.

A Gaussian process (Rasmussen, 2003) is a prior distribution defined on some bounded set $\mathcal{Z}$, and is determined by a mean function $\mu:\mathcal{Z}\rightarrow\mathbb{R}$ and a covariance kernel $\kappa:\mathcal{Z}\times\mathcal{Z}\rightarrow\mathbb{R}$. Given $n$ observations $\mathcal{D}_{n}=\{(z_{i},f(z_{i}))\}_{i=1}^{n}$, the prior distribution on $f(z_{1:n})$ is

where we use compact notation for functions applied to collections of input points: $z_{1:n}$ indicates the sequence $z_{1},\cdots,z_{n}$, $f(z_{1:n})=[f(z_{1}),\cdots,f(z_{n})]$, $\mu_{0}(z_{1:n})=[\mu_{0}(z_{1}),\cdots,\mu_{0}(z_{n})]$, $\kappa_{0}(z_{1:n},z_{1:n})=[\kappa_{0}(z_{1},z_{1}),\cdots,\kappa_{0}(z_{1},z_{n});\cdots;\kappa_{0}(z_{n},z_{1}),\cdots,\kappa_{0}(z_{n},z_{n});]$.

Now we wish to infer the value of $f(z)$ at some new point $z$, the posterior process $f(z)|\mathcal{D}_{n}$ is also a Gaussian process (GP) with mean $\mu_{n}$ and covariance $\sigma_{n}^{2}$:

As a optimization method to maximize a function $f$, Bayesian optimization models the function to make decisions about where to evaluate the next point $z$. Assuming we already obtained observations $\mathcal{D}_{t-1}=\{(z_{i},f(z_{i}))\}_{i=1}^{t-1}$, to determine the next point $z_{t}$ for evaluation, we first use the posterior GP to define an acquisition function $\varphi_{t}:\mathcal{Z}\rightarrow\mathbb{R}$, which models the utility of evaluating $f(z)$ for any $z\in\mathcal{Z}$. We then evaluate $f(z_{t})$ with

In this work, we use the expected improvement (EI) acquisition function  (Mockus et al., 1978)

which measures the expected improvement over the current best value $z_{best}=\operatorname*{arg\,max}_{z_{i}}f(z_{i})$ according to the posterior GP. Here $\Phi(\cdot)$ and $\phi(\cdot)$ are the cdf and pdf of $\mathcal{N}(0,I)$ respectively.

Suppose a classifier $F(x)$ has input $x$ and label $y$. An un-targeted adversarial example $x_{adv}$ satisfies:

where $C$ is the number of classes. While an adversarial example for targeted attack means the maximum position of $F(x)$ should be the targeted class $q$: $\operatorname*{arg\,max}_{j\in\{1,\cdots C\}}F(x_{adv})_{j}=q$. In order to find $x_{adv}$, we may optimize a surrogate loss function $\ell(x,y)$ (e.g hinge loss).

In this work, we consider adversarial attack as a time-varying contextual bandits problem. At each time $t$, we observe a state $x_{t}$ which is a modification of the original input $x_{0}$. Before taking arm $a_{t}\in\mathcal{A}\subset\mathbb{R}^{d}$, we could observe the feature $z$ of arms. And $a_{t}$ would modify state $x_{t}$ to $x_{t+1}$ according to

with reward function $r(x_{t},a_{t})=\ell(x_{t+1},y)-\ell(x_{t},y)$ and the checking step tries to remove negative reward. In this frame, we would like to estimate the reward $r(x_{t},a_{t})$ with feature $z_{t}$ using learning, and then pick $a_{t}$ to maximize the reward. Observe that

where the gradient $\nabla_{x_{t}}\ell(x_{t},y)$ is unknown. It follows from the formulation that we may rewrite $r(x_{t},a_{t})$ as a function

Since in general, we make small steps from one iteration to the next iteration, $\delta_{t}(a_{t})=x_{t+1}-x_{t}$ is small. We may approximate the reward with fixed gradient locally with

We may consider the learning of reward as a time-varying contextual bandits problem with reward function $\tilde{f}_{t}(a_{t})$ for arm $a_{t}$ at time $t$. Since $x_{t+1}-x_{t}$ is small, this time-varying bandits has slow-varying property: the function $\tilde{f}_{t}$ changes slowly from time $t$ to time $t+1$.

In the proposed framework, our goal is to learn the time-varying bandits reward $\tilde{f}_{t}(a_{t})$ with feature $z_{t}$. We use Gaussian process regression to model the reward function using recent historic data since the reward function is slow-varying, and describe the details in the subsequent sections.

We note that the most general action space contains all $a_{t}\in\mathbb{R}^{d}$, where $d$ is the image pixels. However, it is impossible to explore the arms in such a large space. In this work, we choose a specific class of actions $\mathcal{A}=\{a_{i}\}_{i=1}^{n}$, $n$ is the image blocks of different sizes. It covers the space of the adversarial perturbations while maintaining good complexity. We also find that the location and the PCA of the blocks a good component of the feature $z$ associated with the arm. Besides, modifying a block only affects the state locally. Therefore the reward function remains similar after state changes.

We evaluated the number of queries versus the success rates of CorrAttack on both undefended and defended network on ImageNet (Russakovsky et al., 2015). Moreover, we attacked Google Cloud Vision API to show that CorrAttack can generalize to a true black-box model.

We used the common hinge loss proposed in the CW attack (Carlini & Wagner, 2017). We compared two versions of CorrAttack : CorrAttack${}_{\text{Diff}}$ and CorrAttack${}_{\text{Flip}}$, to ZOO (Chen et al., 2017), NES (Ilyas et al., 2018), NAttack (Li et al., 2019), Bandits (Ilyas et al., 2019), PARSI (Moon et al., 2019), BayesOpt (Ru et al., 2020) and Bayes-Attack (Shukla et al., 2019). We only test adversarial attack on $\ell_{\infty}$ norm. The details of the Gaussian processes regression and the hyperparameters of CorrAttack are given in the Appendix B. We shall mention that CorrAttack is not sensitive to the hyperparameters. The hyperparameters of other methods follow those suggested by the original papers.

We formulate the score-based adversarial attack as a time-varying contextual bandits and propose a new method CorrAttack. By performing structured search on the blocks of the image, the bandits has the slow varying property. CorrAttack takes advantage of the the features of the arm, and uses Bayesian optimization with Gaussian process regression to learn the reward function. The experiment shows that CorrAttack can quickly find the action the large reward and CorrAttack achieves superior query efficiency and success rate on ImageNet and Google Cloud Vision API.

We only include basic features for learning the bandits. Other features like embedding from the transfer-based attack may be taken into account in the future work. While our work only focuses on adversarial attack on $\ell_{\infty}$ norm, the same contextual bandits formulation could be generalized to other $\ell_{p}$ norm to improve query efficiency. Besides, defense against CorrAttack may be achieved with adversarial training on CorrAttack , but it may not be able to defend other attacks in the meantime.