PaperlayerView exact revision on arXiv

Source-linked AI summary

HopSkipJumpAttack: A Query-Efficient Decision-Based Attack

Jianbo Chen, Michael I. Jordan, Martin J. Wainwright

arXiv:1904.02144v5cs.LGcs.CRmath.OCstat.ML

TL;DR

Decision-based attacks must craft adversarial examples from output labels alone, but existing approaches can be query-intensive. HopSkipJumpAttack uses a boundary-based gradient-direction estimate to support targeted and untargeted ℓ2 and ℓ∞ attacks, with theory guiding the algorithm. Experiments report substantially greater query efficiency than Boundary Attack and competitive performance against several defenses.

  • Problem

    Decision-based adversarial attacks operate from predicted labels alone, creating a need for effective attacks under limited model-query access.

  • Method

    HopSkipJumpAttack estimates gradient direction from binary decision information at the boundary and iteratively combines gradient estimation, step-size search, and binary boundary search.

  • Results

    HopSkipJumpAttack achieves superior query efficiency over decision-based attacks while supporting targeted and untargeted optimization for ℓ2 and ℓ∞ distances.

  • Takeaways & Limitations

    The attack can evaluate several defense mechanisms using only decision access and remains applicable to nondifferentiable models.

  • Takeaways & Limitations

    Decision-based algorithms require model evaluations near the boundary, and imperceptible targeted examples on ImageNet can still require tens of thousands of queries.

Abstract

from arXiv · show

The goal of a decision-based adversarial attack on a trained model is to generate adversarial examples based solely on observing output labels returned by the targeted model. We develop HopSkipJumpAttack, a family of algorithms based on a novel estimate of the gradient direction using binary information at the decision boundary. The proposed family includes both untargeted and targeted attacks optimized for $\ell_2$ and $\ell_\infty$ similarity metrics respectively. Theoretical analysis is provided for the proposed algorithms and the gradient direction estimate. Experiments show HopSkipJumpAttack requires significantly fewer model queries than Boundary Attack. It also achieves competitive performance in attacking several widely-used defense mechanisms. (HopSkipJumpAttack was named Boundary Attack++ in a previous version of the preprint.)

I. INTRODUCTION

Decision-based attacks generate adversarial examples using only predicted labels, making them practical but query-constrained. HopSkipJumpAttack addresses these constraints with boundary-based gradient estimation and query-efficient algorithms supporting targeted and untargeted ℓ2 and ℓ∞ attacks.

  • Threat model: Decision-based attacks assume access only to the target model’s predicted label, unlike white-box and score-based threat models.This label-only setting is especially practical because it does not require model details or output probabilities.
  • Prior work: Boundary Attack avoids training-data and transferability assumptions but is limited to ℓ2 distance and requires many model queries.Its rejection-sampling procedure discards perturbations that leave the target class, contributing to query inefficiency.
  • Motivation: Limited query budgets matter because online platforms impose request limits, making query inefficiency a practical clock-time and scalability problem.The paper gives Google’s cloud vision API limit as 1,800 requests per minute.
  • Proposed approach: The algorithm family generates targeted and untargeted adversarial examples optimized for minimum ℓ2 or ℓ∞ distance.Each iteration estimates a gradient direction, searches the step size by geometric progression, and returns to the boundary through binary search.
  • Proposed approach: HopSkipJumpAttack estimates gradient direction from binary decision information at the boundary and controls deviation from that boundary.The proposed estimate is designed to be unbiased at the boundary, while the analysis motivates perturbation and step-size choices.
  • Evaluation: Extensive experiments report superior efficiency over state-of-the-art decision-based attacks and evaluate several defense mechanisms.The evaluation includes defensive distillation, region-based classification, adversarial training, and input binarization.

A. An iterative algorithm for ℓ2 distance

The paper first develops a gradient-access iterative procedure for minimizing ℓ2 distance, then extends the projection perspective to ℓ∞ distance. Under smoothness and nonvanishing-gradient assumptions, the ℓ2 updates converge to a stationary point.

  • A. An iterative algorithm for ℓ2 distance: The ℓ2 procedure updates an adversarial iterate along the gradient and chooses a line-search parameter so the next iterate lies on the decision boundary.The boundary constraint motivates the update because the later gradient-direction estimate is valid near the boundary.
  • A. An iterative algorithm for ℓ2 distance: Under twice differentiability, locally Lipschitz gradients, and a gradient bounded away from zero on the boundary, the analysis guarantees convergence to a stationary point.The angular measure reaches its stationary-point condition as the iterations proceed.
  • A. An iterative algorithm for ℓ2 distance: Theorem 1 bounds the angular error by 1 − r(x_t, x⋆) ≤ c t^(q−1) for the prescribed step-size schedule.The theorem uses step sizes of the form ξ_t = ∥x_t − x⋆∥_2 t^−q.
  • B. Extension to ℓ∞ distance: The projection formulation extends the update from ℓ2 to other ℓp norms, including an ℓ∞ operator that clips each coordinate within a neighborhood of x⋆.The ℓ∞ update uses the element-wise sign of the gradient.

IV. A DECISION-BASED ALGORITHM BASED ON A NOVEL

The decision-based algorithm replaces unavailable discriminant-function gradients with a boundary gradient-direction estimate derived solely from Boolean model decisions. It repeatedly approaches the boundary, estimates direction, updates, and returns to the boundary through binary search.

  • IV. A DECISION-BASED ALGORITHM BASED ON A NOVEL: In the decision-based setting, the attacker observes only the Boolean decision function and cannot access the classifier’s underlying discriminant function or gradient.The gradient-direction estimate is therefore constructed from binary information at a boundary point.
  • GRADIENT ESTIMATE: At a boundary iterate, the method approximates the gradient direction with a Monte Carlo average of perturbation directions sampled uniformly on the d-dimensional sphere.The perturbation parameter δ controls the size of the random probes.
  • GRADIENT ESTIMATE: The proposed estimator is asymptotically unbiased as δ approaches zero, with its directional accuracy analyzed under locally Lipschitz gradients.Theorem 2 bounds the cosine of the angle between the expected estimate and the true boundary gradient direction.
  • B. Approaching the boundary: Because the estimator is valid at the boundary, each iteration first approaches the boundary by binary search before estimating the gradient direction.Finite binary search produces an iterate close to, rather than exactly on, the boundary.
  • B. Approaching the boundary: After estimating direction, the algorithm uses norm-dependent updates and geometric step-size reduction, then performs another binary search to return near the boundary.For ℓ2 it normalizes the direction; for ℓ∞ it uses its element-wise sign.

C. Controlling errors of deviations from the boundary

The paper analyzes errors caused by finite binary-search accuracy and off-boundary perturbations, then controls them through dimension-aware perturbation and threshold choices plus variance reduction.

  • C. Controlling errors of deviations from the boundary: Finite binary search never places the iterate exactly on the boundary, so the gradient-direction estimate must tolerate deviation from that boundary.The analysis explicitly separates boundary approximation error from estimator variance.
  • C. Controlling errors of deviations from the boundary: The method chooses δ_t as a function of dimension d and threshold θ, setting θ at scale d^(−q−1) so δ_t is proportional to d^−1.This choice makes approximation error independent of dimension and yields logarithmic dependence on dimension for model queries.
  • C. Controlling errors of deviations from the boundary: At the boundary, gradient-approximation error scales as O(δ_t^2), while finite-step search leaves the iterate only close to the boundary.This makes perturbation-size selection important when the boundary is approached numerically.
  • C. Controlling errors of deviations from the boundary: A baseline is introduced to reduce variance when perturbed samples are unevenly distributed across the two sides of the boundary.The paper states that variance decreases whenever the expected baseline signal is sufficiently large.
  • C. Controlling errors of deviations from the boundary: The complete algorithm combines boundary search, sampled gradient-direction estimation, geometric step-size search, and a final update toward the boundary.The implementation initializes a target-side sample and repeats these operations for T iterations.

D. HopSkipJumpAttack

HopSkipJumpAttack combines boundary initialization, gradient-direction estimation, geometric step-size search, and projection into an iterative decision-based attack. Its evaluation compares median distance against Boundary Attack across model-query budgets.

  • D. HopSkipJumpAttack: HopSkipJumpAttack is initialized with a target-side sample and iteratively performs boundary search, gradient estimation, geometric progression, and projection.Untargeted attacks start from a target-class sample, while targeted attacks use a misclassified sample blended with uniform noise.
  • D. HopSkipJumpAttack: Table I reports median distance at various model-query counts, with smaller distances bold-faced and BA denoting Boundary Attack versus HSJA denoting HopSkipJumpAttack.The table is designed to compare attack distance at matched query budgets.
  • D. HopSkipJumpAttack: The algorithm clips iterates when the input domain is bounded, preserving feasibility during the iterative updates.Clipping is performed at each step by default in bounded input domains.

V. EXPERIMENTS

Experiments evaluate HopSkipJumpAttack across datasets, models, attack goals, distance metrics, and query budgets, comparing it with decision-based baselines. Across these settings, it generally produces smaller perturbations with fewer queries, while targeted attacks and larger datasets require more queries.

  • Experimental setup: Experiments compare HopSkipJumpAttack with Boundary Attack, Limited Attack, and Opt Attack across varied datasets and models.Limited Attack is included only for targeted ℓ∞ experiments.
  • Metrics: The evaluation measures median ℓp distance and success rate under fixed query budgets and distance thresholds.Figures report median distance versus queries and success rate versus distance threshold.
  • Efficiency results: HopSkipJumpAttack crafts significantly smaller-distance adversarial examples than Boundary Attack and Opt Attack with limited queries across all evaluated datasets.The reported ordering is HopSkipJumpAttack, followed by Boundary Attack, then Opt Attack.
  • Efficiency results: 0.559 is the untargeted ℓ2 median distance for HopSkipJumpAttack on CIFAR-10 ResNet at 1,000 queries, versus 2.78 for Boundary Attack and 2.07 for Opt Attack.The HopSkipJumpAttack perturbation corresponds to below 3/255 per pixel on average.
  • Efficiency results: 70% of untargeted ℓ∞ HopSkipJumpAttack examples on CIFAR-10 stay within an 8/255 neighborhood at 1,000 queries, a Boundary Attack rate reached only after 20,000 queries.This comparison is reported for the success-rate evaluation.
  • Targeted versus untargeted attacks: Targeted attacks require more queries than untargeted attacks for comparable distances, especially on CIFAR-100 and ImageNet.On CIFAR-10, targeted HopSkipJumpAttack takes about 2,000–5,000 queries for a performance level reached by untargeted attacks within 1,000 queries on 70%–90% of images; ImageNet targeted attacks take 10,000–20,000 queries.

B. Defense mechanisms under decision-based attacks

The paper evaluates HopSkipJumpAttack against defensive distillation, region-based classification, and adversarial training under decision-based query budgets. It achieves acceptable low-budget performance and comparable or superior performance to white-box attacks with sufficient queries, while Boundary Attack is limited under restricted budgets and for ℓ∞ optimization.

  • Experimental setup: Three defense mechanisms—defensive distillation, region-based classification, and adversarial training—are evaluated under decision-based attacks.The experiments compare HopSkipJumpAttack with gradient-based and defense-specific white-box baselines, plus Boundary Attack.
  • Overall results: On all three defenses, HopSkipJumpAttack shows similar or superior performance to state-of-the-art white-box attacks with sufficient model queries.With only 1K–2K queries, performance remains acceptable but is worse than the best white-box attacks.
  • Defensive distillation: 86% and 99% success rates are achieved on distilled models at ℓ∞ distance 0.3 with 1K and 50K queries, respectively.At ℓ2 distance 3.0, the attack reaches 91% success with 2K queries and remains comparable to C&W with 10K–50K queries.
  • Region-based classification: 82% and 93% success rates are achieved on region-based classification at ℓ∞ and ℓ2 thresholds, respectively, with 2K queries.Convergence is slightly slower because stochasticity near the boundary can prevent accurate binary boundary search; performance becomes comparable to BPDA with 10K–50K queries.
  • Adversarial training: 11.0% success is achieved against adversarial training at ℓ∞ distance 0.3 with 50K queries, compared with 7.4% for BIM.The resulting adversarially perturbed-data accuracy is 87.58%, and 1K-query performance is comparable to BIM and C&W.

APPENDIX A PROOFS

The appendix analyzes convergence of the iterative update under conditions on step sizes, distances, and gradient regularity. The proof separates cases according to the relative boundary distance and derives asymptotic convergence behavior.

  • Convergence analysis: The proofs rewrite the update using τ_t := ξ_t/∥∇S(x_t)∥_2 and analyze the resulting squared-distance ratio.This introduces normalized step-size quantities for the convergence argument.
  • Convergence analysis: A second-order Taylor expansion with Hessian H_t is used to characterize the update and derive a quadratic equation in α.The proof defines v_t and d_t to simplify the update analysis.
  • Case analysis: The proof separates the cases r_t < η_t and r_t ≥ η_t when bounding the distance ratio.The first case can occur only finitely often under the stated asymptotic conditions.
  • Case analysis: As η_t tends to zero, θ_t is eventually bounded above by 1 − c_2 for a positive constant c_2, enabling a contraction argument.The argument uses fixed constants and positivity of the product of θ_t over iterations.
  • Asymptotic rate: For 2 < q < 1, the proof obtains 1 − r_t = o(t^(q−1)) under the step-size choice ξ_t = η_t∥x_t − x⋆∥ with η_t := t^(−q).The appendix also states τ_t = η_t for this choice.

B. Proof of Theorem 2

Theorem 2 is proved by analyzing random sphere directions near the decision boundary. Taylor bounds partition directions into upper-cap, annulus, and lower-cap events, yielding the expected gradient-direction estimate and its error bound.

  • Boundary analysis: A random vector u is sampled uniformly on the sphere, and Taylor’s theorem bounds the model behavior after perturbation by δu.The second-order term is bounded using Lipschitz gradients and eigenvalue-based bounds.
  • Estimator expectation: The gradient is expanded in an orthogonal basis whose first vector is the normalized gradient direction, allowing the estimator’s expected value to be computed.The random direction is represented through spherical coordinates in this basis.
  • Geometric partition: Directions are partitioned into upper-cap, annulus, and lower-cap events according to the value of ∇S(x_t)^T u.The annulus probability is denoted p, while the two cap probabilities are equal by symmetry.
  • Estimator error: The derivation bounds the difference between the expected estimator and a scaled true gradient-direction vector.This connects the binary boundary observations to the direction used by the attack.
  • Probability bound: The relevant projection squared follows a Beta distribution B(1/2, (d−1)/2) scaled by ∥∇S(x_t)∥_2^2.This distribution is used to bound the probability of the annulus event.

C. Proof of Theorem 3

Theorem 3 analyzes the variance of the gradient-direction estimator, including the effect of a baseline. The proof expands the estimator variance using independent samples and concludes that the baseline estimator has lower variance.

  • Variance decomposition: The proof introduces ξ_b and its average over B samples, using independent copies of ξ and u to expand the variance.The notation separates individual binary observations from their batch mean.
  • Variance decomposition: Independence of sampled directions and their associated observations is used to express the estimator variance.The expansion isolates cross terms and the contribution of the batch average.
  • Variance calculation: The middle term is algebraically expanded in terms of B and the moments of ξ.This produces the correction needed for the baseline variance calculation.
  • Conclusion: The baseline estimator satisfies Var(d∇S(x_t, δ)) < Var(g∇S(x_t, δ)).Thus, under the proof’s assumptions, incorporating the baseline reduces estimator variance.

APPENDIX B SENSITIVITY ANALYSIS

The sensitivity analysis evaluates theoretically motivated choices for step size, perturbation size, and baseline in HopSkipJumpAttack. The theorem-based step-size and perturbation choices perform best, while the baseline improves gradient-direction estimation under uneven perturbations.

  • Experimental setup: The experiments evaluate these hyper-parameters using an ℓ2-optimized HopSkipJumpAttack on randomly sampled CIFAR-10 images classified by a 20-layer ResNet.The setup is designed to assess choices suggested by the theoretical analysis.
  • Choice of step size: The evaluated step-size schemes include square-root decay, linear decay, no decay, grid search, and constant step size.The square-root-decay scheme scales with the current distance according to the theoretical prescription.
  • Choice of step size: The theorem-suggested step-size scheme achieves the best performance in median distance versus model queries.Grid search incurs extra queries initially but later converges comparably; inappropriate decay slows convergence, while a constant step size performs poorly.
  • Choice of perturbation size and baseline: The proposed perturbation size yields the highest average cosine between the estimated and true gradient directions.The cosine of the angle is used to evaluate gradient-direction estimates across iterations and perturbation sizes.
  • Choice of perturbation size and baseline: Adding the baseline further improves gradient-direction estimation, especially when the perturbation size creates severe unevenness among perturbed images.The analysis studies perturbation sizes and baseline use when the sample deviates from the decision boundary.

APPENDIX C MODEL WITHOUT GRADIENTS

The appendix tests HopSkipJumpAttack on a non-differentiable binarization-plus-random-forest model under a decision-only interface. The attack is highly effective at threshold 0.1 and outperforms Boundary Attack on several query-efficiency measures at threshold 0.5.

  • Evaluation setting: HopSkipJumpAttack is evaluated on a model without gradients to test attacks against non-differentiable models and discontinuous input transforms.The model applies input binarization before classification by a random forest.
  • Evaluation setting: The experiment uses MNIST random forests with binarization thresholds of 0.1 and 0.5, achieving 96% and 94.5% natural-test accuracy respectively.The 0.1 threshold gives the highest natural accuracy, while 0.5 gives the more robust adversarial performance.
  • Evaluation protocol: Both attacks use the same initialization and hyper-parameters, query real-valued images, and are evaluated only for untargeted ℓ2 attacks.The model internally binarizes each queried image before passing it to the random forest.
  • Reported metrics: The figures report median ℓ2 distance and success rate as functions of model queries and distance thresholds, respectively.The distance plot uses a logarithmic scale with first- and third-quartile error bars.
  • Threshold 0.1: At threshold 0.1, about 96% of HopSkipJumpAttack adversarial examples lie within the size-3 ℓ2-neighborhood after 1K model queries.The passage attributes this vulnerability to activating pixels by increasing their strength by 0.1.
  • Threshold 0.5: At threshold 0.5, HopSkipJumpAttack reaches median ℓ2 distance 3 in 3K queries and 99% success at distance 3 in 25K queries, while Boundary Attack reaches median distance 5 after 25K queries.The comparison is consistent with query inefficiency from Boundary Attack’s random-walk sampling relative to HopSkipJumpAttack’s gradient-direction estimation.
Loading 1904.02144v5…