PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Andrew Ilyas, Logan Engstrom, Aleksander Madry

arXiv:1807.07978v3stat.MLcs.CRcs.LG

TL;DR

The paper studies black-box adversarial attacks when only loss-oracle access is available, focusing on how to estimate useful gradients without direct gradient access. It unifies existing methods, identifies time-dependent and data-dependent gradient priors, and integrates them through bandit optimization. The resulting attacks achieve factor-of-two-to-six improvements in success rate and query efficiency, with ImageNet experiments showing lower failure rates and query use than NES.

  • Problem

    Black-box attacks must generate adversarial examples without direct access to the model’s loss gradient, while useful but imperfect gradient estimation remains difficult to obtain efficiently.

  • Method

    The paper formulates black-box attacks as gradient estimation and develops a bandit optimization framework that integrates time-dependent and data-dependent gradient priors.

  • Results

    Factor-of-two-to-six improvements in success rate and query efficiency are achieved over state-of-the-art methods.

  • Takeaways & Limitations

    Gradient priors provide a supported route to more efficient black-box adversarial attacks beyond the basic optimality of least-squares estimation.

  • Takeaways & Limitations

    The paper restricts its main presentation to untargeted attacks and perturbations bounded by a fixed ℓp-norm constraint.

Abstract

from arXiv · show

We study the problem of generating adversarial examples in a black-box setting in which only loss-oracle access to a model is available. We introduce a framework that conceptually unifies much of the existing work on black-box attacks, and we demonstrate that the current state-of-the-art methods are optimal in a natural sense. Despite this optimality, we show how to improve black-box attacks by bringing a new element into the problem: gradient priors. We give a bandit optimization-based algorithm that allows us to seamlessly integrate any such priors, and we explicitly identify and incorporate two examples. The resulting methods use two to four times fewer queries and fail two to five times less often than the current state-of-the-art.

1 Introduction

Black-box attacks address settings where attackers can query a model but cannot access its gradients. The paper unifies these attacks as gradient estimation, identifies exploitable gradient priors, and develops a bandit framework that improves query efficiency and failure rates.

  • Black-box attacks are needed when attackers can issue queries but cannot directly access the attacked network’s classification-loss gradient.
  • The paper formalizes gradient estimation as the central problem and uses it to unify previous black-box attack methods.
  • Least squares is shown to be optimal for the basic gradient-estimation setting and essentially equivalent to current-best black-box attacks.
  • The paper improves on this basic optimum by exploiting time-dependent and data-dependent priors about gradient structure.
  • A bandit optimization framework integrates gradient priors into black-box attacks, producing methods that are 2-4 times more query efficient and fail 2-5 times less often than the state of the art.

2 Black-box attacks and the gradient estimation problem

Black-box attacks replace direct gradient access with loss queries, motivating query-efficient gradient estimation for projected attacks. The paper frames this estimation problem, establishes least-squares optimality for standard methods, and motivates exploiting gradient priors despite that optimality.

  • First-order attacks: PGD iteratively increases loss while projecting each iterate into the allowed ℓp ball, using the gradient’s unit-ℓp steepest-ascent direction.For ℓ∞ attacks, this direction is the gradient sign vector.
  • Black-box threat model: Black-box attacks access only loss values, whereas white-box attacks require the classification-loss gradient.This motivates estimating gradients from oracle queries rather than using direct model access.
  • Finite-difference estimation: Finite differences estimate directional derivatives from loss queries, but coordinate-wise recovery requires dimension-proportional queries.For ImageNet Inception v3 with d=268,203, the basic method requires 268,204 queries.
  • Accuracy requirements: A single-step PGD attack can fool more than 60% of ImageNet images when only 20% of gradient-sign coordinates are correctly estimated.The experiment uses random coordinate selection and random signs for the remaining coordinates under an ℓ∞ attack.
  • Gradient estimation problem: The gradient-recovery task is underdetermined when fewer than d inner-product queries are available, so successful attacks need imperfect but sufficiently aligned estimators.The relevant criterion is a sufficiently large inner product with the true gradient.
  • Optimality and priors: Least squares is optimal under stated regression assumptions and essentially equivalent to NES in the underdetermined regime, yet gradient priors can still improve estimation.The paper identifies priors as additional information about gradient distributions and proposes integrating them through bandit optimization.

3 Black-box adversarial attacks with priors

The paper challenges the apparent query-efficiency limit of black-box attacks by exploiting gradient priors arising from iterative trajectories and image structure. It develops a bandit framework that integrates these priors into gradient estimation and adversarial-example generation.

  • Motivation: Least-squares optimality applies only when the target gradient is arbitrary and completely unknown, whereas attack gradients contain exploitable prior information.The paper identifies local input structure and correlations between successive iterative-attack gradients as two such sources of prior information.
  • Time-dependent priors: Time-dependent priors use correlations between successive gradients along the optimization trajectory.The multi-step prior carries the previous gradient into the next estimation step.
  • Time-dependent priors: Cosine similarity between successive gradients is typically about 0.9 for the reported NES PGD step size.The correlation continues at higher step sizes, including step size 4.0 in Appendix B.
  • Data-dependent priors: Data-dependent priors exploit spatial local similarity in images, which extends to similarity among nearby gradient coordinates.The paper evaluates this using average-pooled, or tiled, gradients and cosine similarity with the original gradient.
  • Bandit framework: The bandit formulation represents each action as a gradient estimate based on a latent vector and uses the loss as the negative inner product with the actual gradient.The latent vector carries time-dependent information and can be constrained to encode data-dependent structure.
  • Bandit framework: The algorithm updates the latent vector with an estimated gradient and interleaves gradient estimation with image updates using the boundary projection of the estimate.The resulting method applies to perturbations constrained by any convex set, including ℓ2 and ℓ∞ constraints.

4 Experiments and evaluation

The evaluation compares the bandit methods with NES on ImageNet black-box attacks under ℓ2 and ℓ∞ constraints. Across success, query efficiency, loss, and gradient estimation, the bandit methods outperform NES, with the strongest method substantially reducing failures and queries.

  • ImageNet results: 6 and 3 times fewer failures than NES are achieved by BanditsT D under ℓ∞ and ℓ2 constraints, respectively.Despite its higher success rate, BanditsT D uses around half as many queries as NES.
  • ImageNet results: 2.5 and 5 times greater query efficiency than NES are achieved by the bandit attacks on inputs where NES succeeds, under ℓ∞ and ℓ2 constraints, respectively.The comparison uses only inputs on which NES successfully generates adversarial examples.
  • Additional analyses: At any fixed success rate, the bandit methods use fewer queries per successful image than NES, with the gap suggesting amplification at higher success rates.Figure 4 also tracks average loss over time and correlation between the latent vector and the true gradient.
  • Additional analyses: On every reported metric in both threat models, the bandit methods strictly dominate NES.The metrics include query efficiency, classifier loss, and gradient-estimation performance.

5 Related work

Black-box adversarial attacks have followed iterative query-based optimization or substitute-network transferability. Substitute networks can transfer attacks, but their overall query efficiency is generally worse than gradient-estimation methods, while becoming more favorable across many inputs.

  • Existing black-box approaches: Black-box attacks have primarily used iterative optimization or substitute networks with transferability.Iterative methods gradually perturb inputs using queries, whereas substitute-network methods first mimic the target’s decision boundaries.
  • Substitute networks: Substitute-network attacks train a model on target-labeled synthetic data, generate adversarial examples on it, and transfer them to the target model.Their reported attacks tend to transfer to target MNIST classifiers.
  • Substitute networks: Overall query efficiency is generally worse for substitute-network methods than for gradient-estimation methods.Their performance becomes more favorable when attacking more inputs because the substitute network is trained only once.

6 Conclusion

The paper reframes black-box adversarial attacks as gradient estimation and proves that least squares captures and optimally characterizes existing state-of-the-art approaches. It then uses bandit optimization to integrate gradient priors, yielding substantially more efficient attacks.

  • Conclusion: The framework casts black-box adversarial attack construction as a gradient-estimation problem and unifies existing attack approaches.A standard least-squares estimator is shown to capture existing state-of-the-art methods and be optimal in a natural sense.
  • Conclusion: Two gradient priors are identified: time-dependent similarity across nearby optimization inputs and data-dependent latent structure in the input space.These priors provide additional information beyond the optimality of the existing estimator.
  • Conclusion: A bandit optimization approach integrates such priors and produces methods with a factor of two to six improvement in success rate and query efficiency.The conclusion presents this framework as a route toward more efficient black-box adversarial attacks.

A Proofs

The proofs establish two theoretical properties of Gaussian-query gradient estimation: NES and least squares are closely related, while least squares is finite-sample efficient under isotropic Gaussian noise. The analysis bounds the estimator comparison using concentration and random-direction arguments.

  • NES and least-squares equivalence: Theorem 1 states a high-probability equivalence between the Gaussian k-query NES estimator and the minimal-norm k-query least-squares estimator.The theorem concerns estimating a d-dimensional gradient g from Gaussian query directions.
  • Estimation setup: The query vectors δ_i are independent Gaussian directions, and y contains their inner products with the gradient.The matrix A is defined as the k × d matrix whose rows are the query vectors.
  • Proof strategy: The proof controls the difference between NES and least-squares estimates by bounding the spectrum of A A^T − I and inner products among normalized directions.It uses E[A A^T] = I, covariance concentration, and union bounds.
  • Least-squares optimality: Theorem 2 states that x̂_LSQ = A^T(A A^T)^−1y is a finite-sample efficient, minimum-variance unbiased estimator under y = Ag + ε with isotropic Gaussian noise.The proof applies the Cramér–Rao lower bound and verifies the required Fisher-information condition.
  • Least-squares optimality: The Fisher-information argument establishes finite-sample efficiency by showing that the least-squares estimator satisfies the sufficient condition derived from the Cramér–Rao bound.The proof computes the Fisher matrix from the distribution of y and concludes the required condition.
  • Numerical implication: Claim 1 applies Theorem 1’s bound to an ImageNet-sized dimension d = 300000 with k = 100 queries in the ℓ∞ setting.The supplied passage introduces this numerical application without including its completed bound.

B.1 Compressive Sensing

The paper examines whether compressed sensing can improve gradient estimation by exploiting sparsity in image-gradient representations. Across standard, wavelet, and PCA bases, the examined gradients show no significant sparsity, weakening this route for improving over least squares.

  • B.1 Compressive Sensing: Lack of sparsity in standard and wavelet bases suggests no fundamental structural sparsity in convolutional-network gradients.This observation does not strictly rule out the existence of another basis in which gradients are sparse.
  • B.1 Compressive Sensing: Compressed sensing can solve the relevant optimization problem in some cases, but it requires sparsity to improve over least squares.
  • B.1 Compressive Sensing: The examined standard, wavelet, and PCA bases do not induce significant sparsity in gradients from a standardly trained Inception v3 network.The analysis uses gradients from 5,000 randomly selected ImageNet validation images.

B.2 Tiling

The tiling procedure constructs an average-blurred version of a gradient using spatial mean pooling and upscaling. Figure 6 illustrates the original and tiled gradients for tile length 5.

  • B.2 Tiling: Figure 6 compares an original gradient with its tiled, or average-blurred, version using tile length 5.

B.3 Time-dependent Priors at Higher Step Sizes

The paper tests whether successive gradients remain correlated at larger optimization steps. The results show that this correlation persists up to an ℓ2 step size of 4.0, motivating a time-dependent prior.

  • B.3 Time-dependent Priors at Higher Step Sizes: Successive gradients remain correlated at step sizes up to an ℓ2 norm of 4.0.The paper identifies 4.0 as a typical value for the total perturbation bound ε and an absolute step-size bound.
  • B.3 Time-dependent Priors at Higher Step Sizes: The persistent correlation provides motivation for using a time-dependent prior in iterative optimization.
  • B.3 Time-dependent Priors at Higher Step Sizes: Figure 7 repeats the successive-gradient correlation analysis across several step sizes and shows that the correlation continues at higher steps.

D Full Results

The full results compare optimization trajectories and query requirements for NES, BanditsT, and BanditsT D in ℓ2 and ℓ∞ threat models. The bandit methods dominate NES in queries per successful image, while success may remain incomplete within the 10,000-query budget.

  • D Full Results: Figure 8 plots average loss and cosine distance against query count over optimization trajectories in the two threat models.The trajectories are averaged over 100 images.
  • D Full Results: The CDFs compare query requirements for NES, BanditsT, and BanditsT D in both ℓ2 and ℓ∞ settings.
  • D Full Results: The approaches sometimes fail to find an adversarial example within 10,000 queries, so their CDFs do not converge to one.
  • D Full Results: BanditsT and BanditsT D use strictly fewer queries per successful image than NES at every specified success rate.BanditsT uses a time prior, while BanditsT D uses both data and time priors.

E Results for other Classifiers

On ImageNet, BanditsTD consistently outperforms NES across Inception-v3, VGG16, and ResNet50 classifiers, even without retuning hyperparameters for the new classifiers.

  • BanditsTD consistently outperforms NES on black-box attacks across Inception-v3, VGG16, and ResNet50 classifiers.
  • The experiments reuse hyperparameters found for Inception-v3 rather than fine-tuning them to VGG16 and ResNet50.
  • Table 4 summarizes ℓ∞ and ℓ2 ImageNet attacks using NES and BanditsTD with time- and data-dependent priors.
  • The evaluation enforces a query limit of 10,000 queries, while average queries in the first column count only successful attacks.
Loading 1807.07978v3…