Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors

Introduction

Recent research has shown that neural networks exhibit significant vulnerability to adversarial examples, or slightly perturbed inputs designed to fool the network prediction. This vulnerability is present in a wide range of settings, from situations in which inputs are fed directly to classifiers (SZS+, 14; CMV+, 16) to highly variable real-world environments (KGB, 16; AEIK, 18). Researchers have developed a host of methods to construct such attacks (GSS, 15; MFF, ; CW, 17; MMS+, 18), most of which correspond to first order (i.e., gradient based) methods. These attacks turn out to be highly effective: in many cases, only a few gradient steps suffice to construct an adversarial perturbation.

A significant shortcoming of many of these attacks, however, is that they fundamentally rely on the white-box threat model. That is, they crucially require direct access to the gradient of the classification loss of the attacked network. In many real-world situations, expecting this kind of complete access is not realistic. In such settings, an attacker can only issue classification queries to the targeted network, which corresponds to a more restrictive black box threat model.

Recent work (CZS+, 17; BHLS, 17; IEA+, 18) provides a number of attacks for this threat model. Chen et. al CZS+ (17) show how to use a basic primitive of zeroth order optimization, the finite difference method, to estimate the gradient from classification queries and then use it (in addition to a number of optimizations) to mount a gradient based attack. The method indeed successfully constructs adversarial perturbations. It comes, however, at the cost of introducing a significant overhead in terms of the number of queries needed. For instance, attacking an ImageNet (RDS+, 15) classifier requires hundreds of thousands of queries. Subsequent work (IEA+, 18) improves this dependence significantly, but still falls short of fully mitigating this issue (see Section 4.1 for a more detailed analysis).

We revisit zeroth-order optimization in the context of adversarial example generation, both from an empirical and theoretical perspective. We propose a new approach for generating black-box adversarial examples, using bandit optimization in order to exploit prior information about the gradient, which we show is necessary to break through the optimality of current methods. We evaluate our approach on the task of generating black-box adversarial examples, where the methods obtained from integrating two example priors significantly outperform state-of-the-art approaches.

We formalize the gradient estimation problem as the central problem in the context of query-efficient black-box attacks. We then show how the resulting framework unifies the previous attack methodology. We prove that the least squares method, a classic primitive in signal processing, not only constitutes an optimal solution to the general gradient estimation problem but also is essentially equivalent to the current-best black-box attack methods.

We demonstrate that, despite this seeming optimality of these methods, we can still improve upon them by exploiting an aspect of the problem that has been not considered previously: the priors we have on the distribution of the gradient. We identify two example classes of such priors, and show that they indeed lead to better predictors of the gradient.

Finally, we develop a bandit optimization framework for generating black-box adversarial examples which allows for the seamless integration of priors. To demonstrate its effectiveness, we show that leveraging the two aforementioned priors yields black-box attacks that are 2-5 times more query efficient and less failure-prone than the state of the art.

Black-box attacks and the gradient estimation problem

Suppose that we have some classifier $C(x)$ with a corresponding classification loss function $L(x,y)$, where $x$ is some input and $y$ its corresponding label. In order to generate a misclassified input from some input-label pair $(x,y)$, we want to find an adversarial example $x^{\prime}$ which maximizes $L(x^{\prime},y)$ but still remains $\epsilon_{p}$-close to the original input. We can thus formulate our adversarial attack problem as the following constrained optimization task:

So, intuitively, the PGD update perturbs the input in the direction that (locally) increases the loss the most. Observe that due to the projection in (1), $x_{k}$ is always a valid perturbation of $x$, as desired.

2 Black-box adversarial attacks

The projected gradient descent (PGD) method described above is designed to be used in the context of so-called white-box attacks. That is, in the setting where the adversary has full access to the gradient $\nabla_{x}L(x,y)$ of the loss function of the attacked model. In many practical scenarios, however, this kind of access is not available—in the corresponding, more realistic black-box setting, the adversary has only access to an oracle that returns for a given input $(x,y)$, only the value of the loss $L(x,y)$.

One might expect that PGD is thus not useful in such black-box setting. It turns out, however, that this intuition is incorrect. Specifically, one can still estimate the gradient using only such value queries. (In fact, this kind of estimator is the backbone of so-called zeroth-order optimization frameworks (Spa, 05).) The most canonical primitive in this context is the finite difference method. This method estimates the directional derivative $D_{v}f(x)=\langle\nabla_{x}f(x),v\rangle$ of some function $f$ at a point $x$ in the direction of a vector $v$ as

Here, the step size $\delta>0$ governs the quality of the gradient estimate. Smaller $\delta$ gives more accurate estimates but also decreases reliability, due to precision and noise issues. Consequently, in practice, $\delta$ is a tunable parameter. Now, we can just use finite differences to construct an estimate of the gradient. To this end, one can find the $d$ components of the gradient by estimating the inner products of the gradient with all the standard basis vectors $e_{1},\ldots,e_{d}$:

We can then easily implement the PGD attack (c.f. (1)) using this estimator:

Indeed, CZS+ (17) were the first to use finite differences methods in this basic form to power PGD–based adversarial attack in the black-box setting. This basic attack was shown to be successful but, since its query complexity is proportional to the dimension, its resulting query complexity was prohibitively large. For example, the Inception v3 (SVI+, ) classifier on the ImageNet dataset has dimensionality d=268,203 and thus this method would require 268,204 queries. (It is worth noting, however, that CZS+ (17) developed additional methods to, at least partially, reduce this query complexity.)

3 Black-box attacks with imperfect gradient estimators

In the light of the above discussion, one can wonder if the algorithm (4) can be made more query-efficient. A natural idea here would be to avoid fully estimating the gradient and rely instead only on its imperfect estimators. This gives rise to the following question: How accurate of an gradient estimate is necessary to execute a successful PGD attack?

4 The gradient estimation problem

The above discussion makes it clear that successful attacks do not require a perfect gradient estimation, provided this estimate is suitably constructed. It is still unclear, however, how to efficiently find this kind of imperfect but helpful estimator. Continuous optimization methodology suggests that the key characteristic needed from our estimator is for it to have a sufficiently large inner product with the actual gradient. We thus capture this challenge as the following gradient estimation problem:

For an input/label pair $(x,y)$ and a loss function $L$, let $g^{*}=\nabla_{x}L(x,y)$ be the gradient of $L$ at $(x,y)$. Then the goal of the gradient estimation problem is to find a unit vector $\widehat{g}$ maximizing the inner product

from a limited number of (possibly adaptive) function value queries $L(x^{\prime},y^{\prime})$. (The expectation here is taken over the randomness of the estimation algorithm.)

One useful perspective on the above gradient estimation problem stems from casting the recovery of $g^{*}$ in (5) as an underdetermined vector estimation task. That is, one can view each execution of the finite difference method (see (2)) as computing an inner product query in which we obtain the value of the inner product of $g^{*}$ and some chosen direction vector $A_{i}$. Now, if we execute $k$ such queries, and $k<d$ (which is the regime we are interested in), the information acquired in this process can be expressed as the following (underdetermined) linear regression problem $Ag^{*}=y$, where the rows of the matrix $A$ correspond to the queries $A_{1},\ldots,A_{k}$ and the entries of the vector $y$ gives us the corresponding inner product values.

The view of the gradient estimation problem we developed bears striking similarity to the compressive sensing setting (FR, 13). Thus one might wonder if the toolkit of that area could be applied here. Compressive sensing crucially requires, however, certain sparsity structure in the estimated signal (here, in the gradient $g^{*}$) and, to our knowledge, the loss gradients do not exhibit such a structure. (We discuss this further in Appendix B.)

The least squares method

A reasonable choice for $A$ (via JL (84) and related results) is the distance-preserving random Gaussian projection matrix, i.e. $A_{ij}$ normally distributed.

The resulting algorithm turns out to yield solutions that are approximately those given by Natural Evolution Strategies (NES), which (IEA+, 18) previously applied to black-box attacks. In particular, in Appendix A, we prove the following theorem.

Let $\hat{x}_{NES}$ be the Gaussian $k$-query NES estimator of a $d$-dimensional gradient $\bm{g}$ and let $\hat{x}_{LSQ}$ be the minimal-norm $k$-query least-squares estimator of $\bm{g}$. For any $p>0$, with probability at least $1-p$ we have that

Note that when we work in the underdetermined setting, i.e., when $k\ll d$ (which is the setting we are interested in), the right hand side bound becomes vanishingly small. Thus, the equivalence indeed holds. In fact, using the precise statement (given and proved in Appendix A), we can show that Theorem 1 provides us with a non-vacuous equivalence bound. Further, it turns out that one can exploit this equivalence to prove that the algorithm proposed in IEA+ (18) is not only natural but optimal, as the least-squares estimate is an information-theoretically optimal gradient estimate in the regime where $k=d$, and an error-minimizing estimator in the regime where $k<<d$.

For a linear regression problem $y=A\bm{g}$ with known $A$ and $y$, unknown $\bm{g}$, and isotropic Gaussian errors, the least-squares estimator is finite-sample efficient, i.e. the minimum-variance unbiased (MVU) estimator of the latent vector $\bm{g}$.

In the underdetermined setting, i.e. when $k<<d$, the minimum-norm least squares estimate ($\hat{x}_{LSQ}$ in Theorem 1) is the minimum-variance (and thus minimum-error, since bias is fixed) estimator with no empirical loss.

Black-box adversarial attacks with priors

The optimality of least squares strongly suggests that we have reached the limit of query-efficiency of black-box adversarial attacks. But is this really the case? Surprisingly, we show that an improvement is still possible. The key observation is that the optimality we established of least-squares (and by Theorem 1, the NES approach in (IEA+, 18)) holds only for the most basic setting of the gradient estimation problem, a setting where we assume that the target gradient is a truly arbitrary and completely unknown vector.

However, in the context we care about this assumption does not hold – there is actually plenty of prior knowledge about the gradient available. Firstly, the input with respect to which we compute the gradient is not arbitrary and exhibits locally predictable structure which is consequently reflected in the gradient. Secondly, when performing iterative gradient attacks (e.g. PGD), the gradients used in successive iterations are likely to be heavily correlated.

The above observations motivate our focus on prior information as an integral element of the gradient estimation problem. Specifically, we enhance Definition 1 by making its objective

This change in perspective gives rise to two important questions: does there exist prior information that can be useful to us?, and does there exist an algorithmic way to exploit this information? We show that the answer to both of these questions is affirmative.

Consider a gradient $\nabla_{x}L(x,y)$ of the loss function corresponding to some input $(x,y)$. Does there exist some kind of prior that can be extracted from the dataset $\{x_{i}\}$, in general, and the input $(x,y)$ in particular, that can be used as a predictor of the gradient? We demonstrate that it is indeed the case, and give two example classes of such priors.

The first class of priors we consider are time-dependent priors, a standard example of which is what we refer to as the “multi-step prior.” We find that along the trajectory taken by estimated gradients, successive gradients are in fact heavily correlated. We show this empirically by taking steps along the optimization path generated by running the NES estimator at each point, and plotting the normalized inner product (cosine similarity) between successive gradients, given by

Figure 3 demonstrates that there indeed is a non-trivial correlation between successive gradients—typically, the gradients of successive steps (using step size from IEA+ (18)) have a cosine similarity of about 0.9. Successive gradients continue to correlate at higher step sizes: Appendix B shows that the trend continues even at step size 4.0 (a typical value for the total perturbation bound $\varepsilon$). This indicates that there indeed is a potential gain from incorporating this correlation into our iterative optimization. To utilize this gain, we intend to use the gradients at time $t-1$ as a prior for the gradient at time $t$, where both the prior and the gradient estimate itself evolve over iterations.

Data-dependent priors

We find that the time-dependent prior discussed above is not the only type of prior one can exploit here. Namely, we can also use the structure of the inputs themselves to reduce query complexity (in fact, the existence of such data-dependent priors is what makes machine learning successful in the first place).

In the case of image classification, a simple and heavily exploited example of such a prior stems from the fact that images tend to exhibit a spatially local similarity (i.e. pixels that are close together tend to be similar). We find that this similarity also extends to the gradients: specifically, whenever two coordinates $(i,j)$ and $(k,l)$ of $\nabla_{x}L(x,y)$ are close, we expect $\nabla_{x}L(x,y)_{ij}\approx\nabla_{x}L(x,y)_{kl}$ too. To corroborate and quantify this phenomenon, we compare $\nabla_{x}L(x,y)$ with an average-pooled, or “tiled”, version (with “tile length” $k$) of the same signal. An example of such an average-blurred gradient can be seen in Appendix B. More concretely, we apply to the gradient the mean pooling operation with kernel size $(k,k,1)$ and stride $(k,k,1)$, then upscale the spatial dimensions by $k$. We then measure the cosine similarity between the average-blurred gradient and the gradient itself. Our results, shown in Figure 3, demonstrate that the gradients of images are locally similar enough to allow for average-blurred gradients to maintain relatively high cosine similarity with the actual gradients, even when the tiles are large. Our results suggest that we can reduce the dimensionality of our problem by a factor of $k^{2}$ (for reasonably large $k$) and still estimate a vector pointing close to the same direction as the original gradient. This factor, as we show later, leads to significantly improved black-box adversarial attack performance.

2 A framework for gradient estimation with priors

3 Implementing gradient estimation in the bandit framework

for a given gradient estimate $g$, where we access this inner product via finite differences. Here, $L(x,y)$ is the classification loss on an image $x$ with true class $y$.

where $\bm{u}$ is a Gaussian vector sampled from $\mathcal{N}(0,\frac{1}{d}I)$. The resulting algorithm for calculating the gradient estimate given the current latent vector $v$, input $x$ and the initial label $y$ is Algorithm 2.

A crucial point here is that the above gradient estimator $\Delta_{t}$ parameterizing the bandit reduction has no direct relation to the “gradient estimation problem” as defined in Section 2.4. It is simply a general mechanism by which we can update the latent vector $v_{t}$ in bandit optimization. It is the actions $g_{t}$ (equal to $v_{t}$) which provide proposed solutions to the gradient estimation problem from Section 2.4.

Experiments and evaluation

In evaluating our approach, we test both the bandit approach with time prior (BanditsT), and our bandit approach with the given examples of both the data and time priors (BanditsTD). We use 10,000 randomly selected images (scaled to $$) to evaluate all approaches. For NES, BanditsT, and BanditsTD we found hyperparameters (given in Appendix C, along with the experimental parameters) via grid search.

Related work

All known techniques for generating adversarial examples in the black-box setting so far rely on either iterative optimization schemes (our focus) or so-called substitute networks and transferability.

In the first line of work, algorithms use queries to gradually perturb a given input to maximize a corresponding loss, causing misclassification. Nelson et. al NRH+ (12) presented the first such iterative attack on a special class of binary classifiers. Later, Xu et. al XQE (16) gave an algorithm for fooling a real-world system with black-box attacks. Specifically, they fool PDF document malware classifier by using a genetic algorithms-based attack. Soon after, Narodytska et. al NK (17) described the first black-box attack on deep neural networks; the algorithm uses a greedy search algorithm that selectively changes individual pixel values. Chen et. al CZS+ (17) were the first to design black-box attack based on finite-differences and gradient based optimization. The method uses coordinate descent to attack black-box neural networks, and introduces various optimizations to decrease sample complexity. Building on the work of CZS+ (17), Ilyas et. al IEA+ (18) designed a black-box attack strategy that also uses finite differences but via natural evolution strategies (NES) to estimate the gradients. They then used their algorithm as a primitive in attacks on more restricted threat models.

In a concurrent line of work, Papernot et. al PMG+ (17) introduced a method for attacking models with so-called substitute networks. Here, the attacker first trains a model – called a substitute network – to mimic the target network’s decision boundaries. The attacker then generates adversarial examples on the substitute network, and uses them to attack the original target mode. Increasing the rate at which adversarial examples generated from substitute networks fool the target model is a key aim of substitute networks work. In PMG+ (17), the attacker generates a synthetic dataset of examples labeled by the target classifier using black-box queries. The attacker then trains a substitute network on the dataset. Adversarial examples generated with methods developed with recent methods PMG+ (17); LCLS (17) tend to transfer to a target MNIST classifier. We note, however, that the overall query efficiency of this type of methods tends to be worse than that of the gradient estimation based ones. (Their performance becomes more favorable as one becomes interested in attacking more and more inputs, as the substitute network has to be trained only once.)

Conclusion

We develop a new, unifying perspective on black-box adversarial attacks. This perspective casts the construction of such attacks as a gradient estimation problem. We prove that a standard least-squares estimator both captures the existing state-of-the-art approaches to black-box adversarial attacks, and actually is, in a certain natural sense, an optimal solution to the problem.

We then break the barrier posed by this optimality by considering a previously unexplored aspect of the problem: the fact that there exists plenty of extra prior information about the gradient that one can exploit to mount a successful adversarial attack. We identify two examples of such priors: a “time-dependent” prior that corresponds to similarity of the gradients evaluated at similar inputs, and a “data-dependent” prior derived from the latent structure present in the input space.

Finally, we develop a bandit optimization approach to black-box adversarial attacks that allows for a seamless integration of such priors. The resulting framework significantly outperforms the state-of-the-art methods, achieving a factor of two to six improvement in terms of success rate and query efficiency. Our results thus open a new avenue towards finding priors for construction of even more efficient black-box adversarial attacks.

Acknowledgments

We thank Ludwig Schmidt for suggesting the connection between the least squares method and the natural estimation strategies.

AI was supported by an Analog Devices Graduate Fellowship. LE was supported in part by an MIT-IBM Watson AI Lab research grant, the Siebel Scholars Foundation, and NSF Frontier grant CNS-10413920. AM was supported in part by a Google Research Award, and the NSF grants CCF-1553428 and CNS-1815221.

References

Appendix A Proofs

Let $\hat{x}_{NES}$ be the Gaussian $k$-query NES estimator of a $d$-dimensional gradient $\bm{g}$ and let $\hat{x}_{LSQ}$ be the minimal-norm $k$-query least-squares estimator of $\bm{g}$. For any $p>0$, with probability at least $1-p$ we have that

for each $1\leq i\leq k$. We define the matrix $A$ to be a $k\times d$ matrix with the $\delta_{i}$s being its rows. That is, we have

Now, recall that the closed forms of the two estimators we are interested in are given by

We can bound the difference between these two inner products as

Now, to bound the first term in (12), observe that

(Note that the first term in the above sum has been canceled out.) This gives us that

as long as $\left|\left|{AA^{T}-I}\right|\right|\leq\frac{1}{2}$ (which, as we will see, is indeed the case with high probability).

Our goal thus becomes bounding $\left|\left|{AA^{T}-I}\right|\right|=\lambda_{max}(AA^{T}-I)$, where $\lambda_{max}(\cdot)$ denotes the largest (in absolute value) eigenvalue. Observe that $AA^{T}$ and $-I$ commute and are simultaneously diagonalizable. As a result, for any $1\leq i\leq k$, we have that the $i$-th largest eigenvalue $\lambda_{i}(AA^{T}-I)$ of $AA^{T}-I$ can be written as

ensuring that $\varepsilon\leq\frac{1}{2}$, gives us

with probability at least $1-\frac{k}{k+1}p$.

To bound the second term in (12), we note that all the vectors $\delta_{i}$ are chosen independently of the vector $\bm{g}$ and each other. So, if we consider the set $\{\hat{{g}},\hat{\delta_{1}},\ldots,\hat{\delta_{k}}\}$ of $k+1$ corresponding normalized directions, we have (see, e.g., ) that the probability that any two of them have the (absolute value of) their inner product be larger than some $\varepsilon^{\prime}=\sqrt{\frac{2\log(2(k+1)/p)}{d}}$ is at most

On the other hand, we note that each $\delta_{i}$ is a random vector sampled from the distribution $\mathcal{N}(0,\frac{1}{d}\bm{I}_{d})$, so we have that (see, e.g., Lemma 1 in ), for any $1\leq i\leq k$ and any $\varepsilon^{\prime\prime}>0$,

Applying these two bounds (and, again, union bounding over all the relevant events), we get that

with probability at most $\frac{p}{k+1}$.

Finally, by plugging the above bound and the bound (13) into the bound (12), we obtain that

For a fixed projection matrix $A$ and under the following observation model of isotropic Gaussian noise: $\bm{y}=A\bm{g}+\vec{\varepsilon}\text{ where }\bm{\varepsilon}\sim\mathcal{N}(\bm{0},\varepsilon\bm{Id})$, the least-squares estimator as in Theorem 1, $\hat{x}_{LSQ}=A^{T}(AA^{T})^{-1}\bm{y}$ is a finite-sample efficient (minimum-variance unbiased) estimator of the parameter $\bm{g}$.

Proving the theorem requires an application of the Cramer-Rao Lower Bound theorem:

Given a parameter $\theta$, an observation distribution $p(x;\theta)$, and an unbiased estimator $\hat{\theta}$ that uses only samples from $p(x;\theta)$, then (subject to Fisher regularity conditions trivially satisfied by Gaussian distributions),

Now, note that the Cramer-Rao bound implies that if the variance of the estimator $\hat{\theta}$ is the inverse of the Fisher matrix, $\hat{\theta}$ must be the minimum-variance unbiased estimator. Recall the following form of the Fisher matrix:

Now, suppose we had the following equality, which we can then simplify using the preceding equation:

Multiplying the preceding by $\left[I(\theta)\right]^{-1}$ on both the left and right sides yields:

which tells us that (15) is a sufficient condition for finite-sample efficiency (minimal variance). We show that this condition is satisfied in our case, where we have $y\sim A\bm{g}+\varepsilon$, $\hat{\theta}=\hat{x}_{LSQ}$, and $\theta=\bm{g}$. We begin by computing the Fisher matrix directly, starting from the distribution of the samples $y$:

which concludes the proof, as we have shown that $\hat{x}_{LSQ}$ satisfies the condition (15), which in turn implies finite-sample efficiency. ∎

Appendix B Omitted Figures

B.2 Tiling

An example of the tiling procedure applied to a gradient can be seen in Figure 6.

B.3 Time-dependent Priors at Higher Step Sizes

Appendix C Hyperparameters

Appendix D Full Results

Appendix E Results for other Classifiers

Here, we give results for the ImageNet dataset, comparing our best method (BanditsTD) and NES for Inception-v3 (also shown in Table 1), VGG16, and ResNet50 classifiers. Note that we do not fine-tune the hyperparameters to the new classifiers, but simply use the hyperparameters found for Inception-v3. Nevertheless, our best method consistently outperforms NES on black-box attacks.