PaperlayerView exact revision on arXiv

Source-linked AI summary

Square Attack: a query-efficient black-box adversarial attack via random search

Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, Matthias Hein

arXiv:1912.00049v3cs.LGcs.CRcs.CVstat.ML

TL;DR

Adversarial attacks can fail when gradient information is masked, motivating a score-based black-box alternative. Square Attack uses randomized localized square updates near the feasible-set boundary and reports higher efficiency and success than prior methods across broad benchmarks.

  • Problem

    The problem is to construct effective adversarial examples when gradient-based attacks can be undermined by gradient masking.

  • Method

    Square Attack uses score-based random search with localized square-shaped updates and no access to the underlying model.

  • Results

    Square Attack outperforms state-of-the-art black-box methods in query efficiency and success rate across l2- and l∞-threat models, datasets, and model types.

  • Takeaways & Limitations

    The method is useful for evaluating robustness, including models exhibiting gradient masking, and can outperform white-box attacks in the reported comparisons.

  • Takeaways & Limitations

    The convergence guarantee applies to a related l∞ sampling distribution rather than directly to the paper's exact l∞ distribution.

Abstract

from arXiv · show

We propose the Square Attack, a score-based black-box $l_2$- and $l_\infty$-adversarial attack that does not rely on local gradient information and thus is not affected by gradient masking. Square Attack is based on a randomized search scheme which selects localized square-shaped updates at random positions so that at each iteration the perturbation is situated approximately at the boundary of the feasible set. Our method is significantly more query efficient and achieves a higher success rate compared to the state-of-the-art methods, especially in the untargeted setting. In particular, on ImageNet we improve the average query efficiency in the untargeted setting for various deep networks by a factor of at least $1.8$ and up to $3$ compared to the recent state-of-the-art $l_\infty$-attack of Al-Dujaili & O'Reilly. Moreover, although our attack is black-box, it can also outperform gradient-based white-box attacks on the standard benchmarks achieving a new state-of-the-art in terms of the success rate. The code of our attack is available at https://github.com/max-andr/square-attack.

1 Introduction

Square Attack addresses the need for black-box adversarial attacks that remain effective when gradient information is unreliable. It uses score-based random search and reports stronger query efficiency, success rate, and broad benchmark performance than existing methods.

  • Gradient masking can make seemingly robust models non-robust, while gradient-based attacks may be affected by this phenomenon.
  • Square Attack queries class probabilities without accessing the classifier's underlying model.
  • The method combines random search, a specialized initialization, and square-shaped updates to reduce queries and improve success rate.
  • Across untargeted and targeted attacks on MNIST, CIFAR-10, and ImageNet, Square Attack outperforms state-of-the-art methods under l2- and l∞-norm threat models.

2 Related Work

The related work distinguishes score-based attacks from decision-based and transfer-based settings, and motivates Square Attack as an alternative to gradient estimation. Prior approaches improve efficiency through structured searches, but differ in perturbation geometry and threat-model assumptions.

  • The paper focuses on norm-bounded l2- and l∞-perturbations rather than other norms or minimal-norm attacks.
  • Score-based attacks access classifier scores, while decision-based attacks access only decisions and transfer-based methods use substitute models.
  • Finite-difference gradient estimation can require many queries, especially in high-dimensional image spaces.
  • Random search is iterative rather than random sampling inside the feasible region.
  • Corner searches over the l∞-ball can improve efficiency by applying discrete optimization in a coarse lower-dimensional grid.

3 Square Attack

Square Attack uses random, localized square updates for l∞- and l2-constrained adversarial optimization. Its design keeps perturbations near the feasible-set boundary while adapting update placement, shape, and initialization to each norm.

  • 3 Square Attack: The algorithm samples an update, adds it to the current point, projects onto the norm ball and image domain, and repeats until success or the iteration limit.
  • 3.2 General Algorithmic Scheme of the Square Attack: Random search avoids gradient information by accepting updates that improve the objective.
  • 3.2 General Algorithmic Scheme of the Square Attack: Each update uses localized contiguous square regions and keeps the perturbation approximately on the l∞- or l2-ball boundary before image-domain projection.
  • 3.2 General Algorithmic Scheme of the Square Attack: Unlike prior fixed-grid square methods, Square Attack also optimizes square positions and colors.
  • 3.3 The l∞-Square Attack: For l∞ attacks, square size follows a scheduled percentage of image elements, while vertical-stripe initialization uses random ±ϵ channel values.
  • 3.3 The l∞-Square Attack: The l∞ sampling distribution creates square updates with channelwise constant signs, producing perturbations near l∞-ball corners after projection.
  • 3.4 The l2-Square Attack: For l2 attacks, localized two-center updates move perturbation mass between squared windows while preserving the l2 norm before clipping.

4 Theoretical and Empirical Justification of the Method

The paper justifies Square Attack’s localized square updates through convolutional geometry and evaluates its randomized search design empirically. The analysis also establishes a convergence result under stated assumptions while identifying a mismatch for the main l∞ sampling distribution.

  • Convergence Analysis of Random Search: The convergence analysis shows that, for sufficiently large T, random search can make the gradient arbitrarily small and converge to a critical point of g.This result assumes an L-smooth objective and the update-distribution conditions stated in Eq. (3).
  • Convergence Analysis of Random Search: The second convergence assumption does not directly hold for the l∞ sampling distribution used by the attack, although it holds for a related distribution P_multiple.The related distribution performs worse than the main Algorithm 2 distribution but still reaches state-of-the-art results.
  • Why Squares?: Square-shaped supports maximize the number of s × s convolutional filters that can overlap the perturbation when the modified area is fixed.When k = l^2, the optimal update is an exact l × l square.
  • Ablation Study: In the ablation study, square updates reduce average queries from 339 to 73 versus random selection with constant per-channel signs, and from 401 to 153 with independent signs.The comparison uses 1,000 ImageNet test points, a normally trained ResNet-50, ε = 0.05, and a 10,000-query limit.
  • Ablation Study: Vertical-stripe initialization improves average queries by approximately 25% over uniform initialization and more than halves the median queries.The comparison is for the final “square-c” method.
  • Ablation Study: On ImageNet, Square Attack outperforms other methods in success rate and query efficiency for both l∞ and l2 untargeted attacks.Table 2 uses a 10,000-query limit, ε = 0.05 for l∞ attacks, and ε = 5 for l2 attacks.

5 Experiments

Experiments show that Square Attack achieves high success rates and strong query efficiency across untargeted ImageNet attacks, while also handling robust and gradient-masked models effectively.

  • Evaluation on ImageNet: The evaluation compares score-based black-box attacks on three ImageNet models for untargeted l∞- and l2-threat models.The experiments use 1,000 ImageNet validation images and a 10,000-query budget unless stated otherwise.
  • Evaluation on ImageNet: Square Attack has the lowest failure rate in nearly all ImageNet model-and-norm cases and almost always needs fewer queries than competitors.Its failure rate is below 1% everywhere except for the l2-attack on Inception v3.
  • Evaluation on ImageNet: For l∞ attacks with ϵ = 0.05, Square Attack achieves the lowest failure rate and query consumption across the compared models.Its closest competitor, SignHunter, requires on average 1.8–3 times more queries and has a higher failure rate.
  • Evaluation on ImageNet: For l2 attacks with ϵ = 5, Square Attack attains the lowest median queries on all models and the lowest average queries on VGG-16-BN.On points where all attacks succeed, it improves average queries by at least 1.5× and median queries by at least 2×.
  • Comparison with white-box attacks: Square Attack can outperform white-box PGD and other black-box attacks when evaluating robust models and defenses affected by gradient masking.The reported comparisons include MNIST robust models, l2 attacks against l∞-adversarially trained models, and Clean Logit Pairing or Logit Squeezing defenses.
  • Comparison with white-box attacks: The l2-version of SignHunter can fail to accurately assess robustness because it optimizes only extreme points of an embedded l∞-ball.This limitation is reported in the comparison involving l∞-adversarially trained MNIST models under an l2 threat model.

6 Conclusion

The paper presents Square Attack as a simple black-box attack that substantially improves query efficiency and success rate. The authors argue that it can also help assess models exhibiting gradient masking, including relative to white-box attacks.

  • Square Attack outperforms state-of-the-art methods by a large margin in both query efficiency and success rate.
  • The results suggest that Square Attack can improve robustness estimation for models exhibiting gradient masking, even compared with white-box attacks.

Organization of the Supplementary Material

The supplementary material contains proofs, implementation details, ablations, random-seed variance analyses, and additional experimental material.

  • Section A supplies omitted proofs and deeper theoretical analysis of the l∞-attack’s efficiency.
  • Sections B–D cover implementation details, algorithmic ablations, and variance of reported metrics across random seeds.

A Proofs Omitted from Section 3 and Section 4

The supplementary proofs analyze the sampling distributions underlying Square Attack, including their norm behavior, convergence assumptions, and geometric construction strategy.

  • Proofs for the l2 construction: The proof establishes that Algorithm 3 outputs a perturbation exactly on the l2 boundary, with ∥x̂ + δ − x∥2 = ϵ.
  • Convergence analysis: The convergence analysis uses L-smoothness and bounds involving expected gradient-update alignment and update norms.
  • Limitations of P: The original sampling distribution P does not satisfy the assumptions required by the convergence analysis because some directions have zero expected absolute inner product with updates.
  • Modified sampling distribution: The modified distribution P_multiple restores the assumptions through independent Rademacher values across pixels in the update window.The construction is formalized in Algorithm 4 and supported by moment and variance calculations.
  • Why equal-sign updates help: The analysis explains that equal-sign square updates produce larger expected inner products with approximately piecewise-constant gradient directions than pixelwise-independent updates.The proposed directions are therefore more correlated with gradient direction and are reported to help convergence faster empirically.
  • Geometric construction: The geometric proof constructs a near-square shape by repeatedly adding unit squares along the longer side to maximize the number of contained s × s squares.

B.1 Experiments on ImageNet

The ImageNet experiments use specified attack parameters and compare implementations under model- and norm-specific settings. The evaluation also corrects a preprocessing issue in the Bandits baseline.

  • The ImageNet experiments use p = 0.05 for the l∞-Square Attack and p = 0.1 for the l2 version.
  • Bandits uses its suggested hyperparameters for both l∞ and l2 attacks.
  • SignHunter is evaluated with its original code and no hyperparameters, assuming the finite-difference probe δ equals ϵ.
  • The l∞-Square Attack uses p = 0.3 on MNIST and CIFAR-10 across models.
  • For an l∞-adversarially trained model, the l2-Square Attack uses p = 0.1, while Bandits and SimBA parameters are selected through tuning.
  • The ablation experiments are performed on ImageNet with a standardly trained PyTorch ResNet-50.

C.1 l∞-Square Attack

The attack remains effective across a broad range of initial pixel fractions, while square-shaped updates and the chosen initialization outperform several alternatives. The l2 variant is similarly robust except with very small initial squares.

  • Sensitivity to the hyperparameter p: 0.0% failure rate is achieved for every tested p from 0.0125 to 0.4, with average queries below 140 and median queries below 20.
  • Algorithmic choices: Changing random subsets of pixels requires 339 average queries, compared with 93 for rectangles and 73 for squares.
  • Algorithmic choices: Horizontal-stripe and randomly placed-square initialization achieve 83 and 90 average queries, respectively, but both are worse than the selected vertical-stripe initialization.
  • Sensitivity to the hyperparameter p: The l2-Square Attack has approximately the same failure rate and query efficiency for p between 0.05 and 0.4.
  • Sensitivity to the hyperparameter p: Performance degrades slightly for very small initial squares, p ∈ {0.0125, 0.025}.
  • Algorithmic choices: Using independently sampled random signs in the l2 update and initialization degrades performance by a factor of 1.5.
  • Algorithmic choices: Different initialization schemes do not strongly influence l2-attack results, unlike for the l∞-attack.

D Stability of the Attack under Different Random Seeds

The attack is stable across random seeds on ImageNet and adversarially trained MNIST. Variability is small relative to gaps over competing methods, although robust models can make initialization more influential on query efficiency.

  • On ImageNet, the l∞ and l2 performance metrics are highly concentrated across random seeds, with standard deviations smaller than gaps to competing methods.
  • On adversarially trained MNIST, robust accuracy varies by only 0.1% for l∞ and 1.4% for l2 across runs.
  • Attacking robust models is more challenging, so favorable random initialization or updates can have greater influence on query efficiency.

E.2 Success Rate on ImageNet for Different Number of Queries

Across query budgets, the Square Attack achieves strong ImageNet success rates, including in low-query settings, and extends to dilated architectures and imperceptible perturbations. It also breaks a reported randomized defense.

  • l∞-results: Over 10% success-rate improvement is observed on the challenging Inception-v3 model in the 100–1000-query range.
  • l∞-results: Approximately 20% higher success rate than BayesAttack is achieved below 200 queries on every evaluated model.
  • l2-results: The l2-Square Attack outperforms Bandits and SimBA, with a particularly large gap in the low-query regime.
  • 100% success rate is achieved on DRN-A-50, DRN-C-42, and DRN-D-38, with average and median queries comparable to VGG and ResNet-50.
  • At ϵ∞ = 4/255, the attack achieves almost perfect success with limited queries, producing imperceptible adversarial examples.
  • Robust accuracy falls from 88.4% to 15.8% on CIFAR-10 and from 76.1% to 0.4% on ImageNet under the l∞-Square Attack.
Loading 1912.00049v3…