Square Attack: A Query-Efficient Black-Box Adversarial Attack via Random Search

1. 01What problem does this paper attempt to solve?

   The authors propose Square Attack, a score-based black-box attack that does not rely on gradients, addressing the problems of high query counts and low success rates in black-box attacks.

   Core problem: existing score-based black-box adversarial attacks have low query efficiency and sometimes markedly lower success rates than white-box attacks, while gradient-based attacks are susceptible to gradient masking.

   • Problem setting: adversarial examples pose a threat to safety-critical machine learning applications; many defenses have been broken by stronger attacks, among which gradient obfuscation or masking often makes models that appear robust actually non-robust (according to the authors).
   • Shortcomings of existing methods: the authors state that black-box attacks based on finite-difference gradient estimation are affected by gradient masking and require many queries to the classifier to find adversarial examples, with success rates sometimes significantly lower than white-box attacks.
   • Core observation: successful l∞ perturbations usually lie at the corners of the intersection of the l∞ ball and the image space; convolutional networks are sensitive to local square perturbations with the same sign per channel, so random search with square updates can be used.
   • Paper proposes: Square Attack, a score-based black-box l2 and l∞ attack based on random search, with specific initialization and square updates; the authors state that it outperforms existing methods in both query efficiency and success rate in the untargeted setting.
   • Threat model:
     • Attacker goal: generate adversarial examples under lp norm constraints, in both untargeted (change the predicted class) and targeted (specify a class) settings.
     • Knowledge: score-based, i.e., can query the classifier's output probability distribution over classes but cannot access the model internals.
     • Capability: a query budget per point (e.g., 10,000 for ImageNet experiments), without relying on additional information such as substitute models.
     • Victim system: image classifiers (standard models and adversarially trained/defended models on ImageNet, MNIST, CIFAR-10).

   Collapse this answer

2. 02What related research exists?

   Related work is divided into four groups: gradient estimation, random search/evolution, corner search, and other threat models; baselines are Bandits, SignHunter, etc.

   Gradient-estimation-based score-based attacks

   • [6,30,56] — approximate the gradient by sampling noise around the input point; the authors state that such methods require many queries on high-dimensional inputs (e.g., image classification).
   • Dimensionality-reduction improvements: [6] uses data principal components, [55] searches in the latent space of an autoencoder, [31] uses a low-dimensional noise distribution (Bandits).

   Random search and evolution strategy methods

   • [3] (GenAttack) — generates adversarial examples with a genetic algorithm and can reduce the robust accuracy of randomization and discretization defenses.
   • [28] (SimBA) — can be viewed as a random search variant that selects search directions on an orthogonal basis and tries at most two candidate updates per step; the authors point out that it makes only small l2 modifications per step and orthogonal updates cannot be undone, so query efficiency may be suboptimal.

   Attacks based on searching the corners of the l∞ ball

   • [49] (Parsimonious) and [2] (SignHunter) — perform local search on a coarse grid with components restricted to ±ε, then refine the grid; [2] interprets this as gradient sign estimation.
   • [39] (DFO) — uses an evolutionary algorithm for discrete and continuous optimization, borrowing the "tiling trick" of [31] to partition the perturbation into squares; the authors point out that the size and position of its squares are fixed at the start and not optimized, and that such discrete optimization methods are not easily adapted directly to the l2 norm.
   • [50] (BayesAttack) — based on Bayesian optimization; the authors state it is competitive only in the low-query regime.

   Other threat and knowledge models

   • Decision-based attacks [9,16,27,11,13] — can only query the classifier's decision, a more restricted setting.
   • Substitute-model/transfer methods [44,57,17,23,52] and methods exploiting the target data distribution [35] — the authors point out that the query-efficiency gains from such additional knowledge do not account for the computational cost of training the substitute model, which is especially high at ImageNet scale.

   Baselines and benchmarks: the paper compares Bandits [31], Parsimonious [49], DFOc/DFOd [39], SignHunter [2], SimBA-DCT [28] (l2) and BayesAttack [50] (low-query regime) on ImageNet; on MNIST/CIFAR-10 defended models it compares PGD (1/10/100/10000 restarts), Bandits, SignHunter and SimBA.

   The authors position the paper as: a score-based attack that does not rely on gradient information and does not use a substitute model, differing from fixed-grid methods in that it jointly optimizes the position and color of the squares, and the same framework covers both the l∞ and l2 norms.

   Collapse this answer

3. 03How does the paper address this problem?

   Square Attack uses random search, sampling a local square update at each step so that the perturbation lies approximately on the boundary of the feasible set, with dedicated sampling distributions for l∞ and l2.

   Overall idea: formulate finding adversarial examples as a constrained optimization problem and solve it with random search; each step samples a local square update at a random position so that, before projection, the perturbation lies on the boundary of the lp ball, thereby using almost the full perturbation budget.

   Problem setup

   • Classifier f : [0,1]^d → R^K; an untargeted attack requires arg max_k f_k(x̂) ≠ y and ‖x̂−x‖_p ≤ ε, x̂ ∈ [0,1]^d.
   • Written as constrained optimization: min_{x̂∈[0,1]^d} L(f(x̂), y), s.t. |x̂−x|_p ≤ ϵ; experiments use the margin loss L(f(x̂), y) = f_y(x̂) − max_{k≠y} f_k(x̂).

   General algorithm framework (Algorithm 1)

   • Each step: take the square side length h(i) according to a predetermined decreasing schedule, sample an update δ, project x̂+δ onto the lp ball and [0,1]^d, and accept if the loss decreases.
   • Stop as soon as an adversarial example is found; time complexity is dominated by the number of evaluations of f, at most N.
   • Difference from classical random search: at each step the perturbation x̂−x lies on the ball boundary before projection, and the modification is concentrated in a square region; difference from [31,49,39] is that both the position and color of the square are optimized rather than fixed on a grid.
   • Square side length: h is the positive integer closest to √(p·w²) (h ≥ 3 for the l2 version); the initial p is the only free parameter; for N = 10000, p is halved at iterations {10, 50, 200, 1000, 2000, 4000, 6000, 8000}.

   l∞ version design

   • Initialization: vertical stripes of width 1, each stripe's color sampled uniformly from {−ε, ε}^c; the authors state they found convolutional networks sensitive to such perturbations.
   • Sampling distribution (Algorithm 2): randomly select a position, take an h×h square window, sample one value independently from {−2ε, 2ε} for each color channel with the same sign within the window; after projection (clipping), all components far from the boundary take x_i ± ε, i.e., the perturbation lies at a corner of the l∞ ball.

   l2 version design

   • Initialization: a 5×5 grid-like tiling, each block using the η shape described below, scaled overall to l2 norm ε and clipped.
   • Update shape: η has two "centers" with large absolute values and opposite signs; the farther from the center, the smaller the absolute value, but not zero (Fig. 2 gives an example for h = 8); the authors state that this local high-contrast update improves query efficiency.
   • Sampling distribution (Algorithm 3): randomly select two square windows W1, W2, set the perturbation in W2 to zero and transfer its l2 budget to W1, so that the new perturbation remains on the sphere of radius ε (Proposition 1 guarantees ‖x̂+δ−x‖₂ = ε).

   Theoretical basis

   • Proposition 2: under the assumptions E[δ_t]=0 and Eq. (3), random search with step size γ_t = γ/√T converges to a critical point of an L-smooth objective; the authors note that this assumption does not directly hold for the actual sampling distribution P (Sup. A.3 gives a counterexample), but does hold for P_multiple, which samples each pixel independently (Sup. A.4).
   • Proposition 3: when only k elements can be modified, an (approximate) square maximizes the number of s×s convolutional filters fully covered, providing intuition for why squares are better than rectangles.
   • Targeted attack (Sup. E.1): uses the target-class cross-entropy loss instead; the authors state that the margin loss is suboptimal in query efficiency in the targeted setting.

   Collapse this answer

4. 04What experiments did the paper conduct?

   Compares five black-box attacks on three ImageNet models, and compares with white-box PGD on MNIST/CIFAR-10 robust models.

   Experimental setup

   • Models under test: Inception v3, ResNet-50, and VGG-16-BN pretrained with PyTorch on ImageNet; the appendix additionally tests DRN-A-50, DRN-C-42, and DRN-D-38; on MNIST, the l∞ adversarially trained model of [37] and TRADES [61]; on CIFAR-10/MNIST, CLP, LSQ [33], and the post-averaging defense [36].
   • Data: 1,000 images from the ImageNet validation set; 200 points for the targeted l2 experiments; 100 points for the SignHunter targeted evaluation.
   • Baselines: Bandits [31], Parsimonious [49], DFOc/DFOd [39], SignHunter [2], SimBA-DCT [28], BayesAttack [50] (low query regime); unless noted, the original papers' code and suggested parameters are used, and some results are taken from the original papers.
   • Metrics: failure rate, mean/median number of queries for successful attacks (computed only over points that were originally correctly classified and successfully attacked), robust accuracy.
   • Budget and parameters: 10,000 queries per point for untargeted attacks; ε = 0.05 for l∞ and ε = 5 for l2; Square Attack's p is fixed at 0.05 (l∞) and 0.1 (l2) for all models.
   • Repetitions: the main experiments do not report repetitions; Appendix D measures stability with 10 random seeds.

   Main results

   ImageNet untargeted attacks, 10,000 query budget (per Table 2; Parsimonious reported only Inception v3):

   Swipe horizontally to read the table

   Norm	Attack	Failure rate I/R/V	Mean queries I/R/V	Median queries I/R/V
   l∞	Bandits	3.4/1.4/2.0%	957/727/394	218/136/36
   l∞	DFOc–CMA	0.8/0.0/0.1%	630/270/219	259/143/107
   l∞	DFOd–Diag. CMA	2.3/1.2/0.5%	424/417/211	20/20/2
   l∞	SignHunter	1.0/0.1/0.3%	471/129/95	95/39/43
   l∞	Square Attack	0.3/0.0/0.0%	197/73/31	24/11/1
   l2	Bandits	9.8/6.8/10.2%	1486/939/511	660/392/196
   l2	SimBA-DCT	35.5/12.7/7.9%	651/582/452	564/467/360
   l2	Square Attack	7.1/0.7/0.8%	1100/616/377	385/170/109

   • The authors state that Square Attack has the lowest failure rate across all models and norms (all < 1% except 7.1% for l2 on Inception v3), and almost always uses fewer queries.
   • The authors state that the closest competitor, SignHunter, still uses 1.8–3 times more mean queries and has a higher failure rate; DFOc–CMA's median queries are competitive, but its failure rate is higher and its mean queries are 2–7 times higher.
   • Because Square Attack's failure rate is low, its query statistics are biased toward "hard" samples; recomputed only on points where all three succeed (Table 3), the authors state an improvement of at least 1.5× in mean queries and at least 2× in median queries.

   Comparison with white-box attacks

   • Robust models (Table 4): MNIST l∞ ε = 0.3, p = 0.8, 20k queries, 50 random restarts; robust accuracy 88.25% on the Madry et al. [37] model (white-box SOTA 88.13%), and 92.58% on TRADES [61]; the authors state this surpasses the white-box attack of [20] and achieves a new SOTA.
   • Gradient masking (Table 5): the l∞ adversarially trained model of [37] under the l2 threat, at ε = 2.5, Square Attack's single-run robust accuracy is 2.4%, PGD100 is 36.0%, SignHunter 94.9%, Bandits 32.4%, SimBA 75.8%; the authors state that Square Attack is not affected by gradient masking.
   • CLP/LSQ defenses (Table 6): p = 0.3, 20k queries; on MNIST at ε = 0.3, CLP 6.1%, LSQ 2.6% (PGD with ten thousand restarts: 4.1% and 5.0% respectively); the authors state that in most cases a single run is close to PGDR and on average better than Bandits and SignHunter.

   Targeted attacks and other results

   • Targeted (Table 9, Inception-v3): l∞ (100k query budget) Square Attack failure rate 0.0%, mean 4584 queries, which the authors state is 1.5 times fewer than the closest competitor; l2 (60k budget, 200 points) failure rate 33.5%, higher than Bandits' 24.5% and SimBA-DCT's 25.5%, but with lower mean and median queries (19794/15946).
   • post-averaging defense (Table 12): ε = 8/255, Square Attack (p = 0.3) reduces robust accuracy from 88.4% as measured by PGD to 15.8% (CIFAR-10), and from 76.1% to 0.4% (ImageNet); the authors state that this defense is less robust than claimed.
   • Dilated convolution architectures (Table 10): on DRN-A-50/C-42/D-38, l∞ ε = 0.05 failure rates are all 0.0%, with mean queries 86/57/48; the authors state that the attack is not limited to standard convolutional networks.

   Other ablations and analyses

   • Design ablation (Table 1, ResNet-50, l∞ ε = 0.05): square + same sign per channel + vertical stripes gives 73 mean queries, random shape + per-pixel sign gives 401; the authors state that square is better than rectangular (93) and random shape.
   • Initialization: vertical stripes reduce mean queries by about 25% versus uniform initialization, and halve the median (Table 1).
   • Sensitivity to p (Fig. 5): for l∞, failure rate is 0.0% for p ∈ [0.0125, 0.4] with mean queries below 140; for l2, performance is similar for p ∈ [0.05, 0.4] and slightly worse for p ∈ {0.0125, 0.025}.
   • Random seed stability (Table 8, 10 seeds): ImageNet ResNet-50 l∞ failure rate 0.0% ± 0.0%, mean queries 72 ± 2; MNIST l2 robust accuracy 16.0% ± 1.4%.
   • Imperceptible perturbation (Table 11): at ε = 4/255, failure rates for VGG/ResNet-50/Inception v3 are 0.5/0.3/5.4%.
   • Low query regime (Fig. 4, Fig. 6): the authors state that Square Attack outperforms all methods including BayesAttack within 200 queries; the BayesAttack and DFO data in Fig. 6 come from personal communication with the authors and were evaluated on 500 and 10,000 sampled points respectively.

   Collapse this answer

5. 05What are some points that can be further explored?

   The paper does not have a dedicated limitations section; the experiments cover three ImageNet models and several MNIST/CIFAR-10 defense models.

   Limitations and future directions noted by the authors

   • The paper does not specifically discuss limitations; there is no Limitations or Future Work section. The following are statements of method applicability explicitly written by the authors in the main text:
   • The convergence analysis does not directly apply to the actual l∞ sampling distribution P: Sec. 4.1 and Sup. A.3 give counterexamples showing that the assumptions of Eq. (3) do not hold for P, and hold only for P_multiple, which samples each pixel independently; the authors state that P_multiple performs worse than the distribution of Algorithm 2.
   • The l2 version is "significantly harder to analyze" (start of Sec. 4); the theoretical argument is mainly for the l∞ version.
   • The targeted l2 attack has a higher failure rate than competitors: Sup. E.1 reports a Square Attack failure rate of 33.5%, higher than Bandits' 24.5% and SimBA-DCT's 25.5% (lower query counts, but the statistics are based on different numbers of successful points).

   Experimental coverage

   • The untargeted main experiments cover three models on ImageNet, Inception v3, ResNet-50, and VGG-16-BN, with 1,000 validation set images each (Sec. 5.1).
   • Targeted experiments are done only on Inception-v3: l∞ uses 1,000 images and a 100k query budget, l2 uses 200 points and a 60k budget (Sup. E.1).
   • Robust models and defense evaluations include: [37] and TRADES [61] on MNIST (l∞ ε = 0.3), the [37] model under the l2 threat, CLP/LSQ [33] (MNIST and CIFAR-10), and post-averaging [36] (CIFAR-10 and ImageNet).
   • Appendix additions: dilated convolution architectures DRN-A-50/C-42/D-38 (Table 10), imperceptible perturbation ε = 4/255 (Table 11), stability over 10 random seeds (Table 8).
   • The paper does not report the number of repetitions for the main experiments; some comparison results are taken from the original papers, and the per-query success rates of BayesAttack and DFO in Fig. 4/Fig. 6 come from personal communication with the original authors and were evaluated on different numbers of points (500 and 10,000).

   Collapse this answer

6. 06Summarize the main content of the paper

   The authors propose Square Attack, a black-box attack based on random search, which the authors state has better query efficiency and success rate than existing methods and is not affected by gradient masking.

   Square Attack is a score-based black-box adversarial attack targeting image classifiers under l∞ and l2 norm constraints; the authors state that it does not require gradient information and is therefore not affected by gradient masking.

   • Problem addressed: the authors state that existing black-box attacks require many queries and sometimes have lower success rates than white-box attacks, while gradient masking distorts gradient-based evaluations.
   • Method highlights: within a random search framework, each step samples a local square update at a random position so that the perturbation lies approximately on the boundary of the lp ball; the l∞ version uses vertical stripe initialization and same-sign updates per channel, the l2 version uses a two-center update and transfers perturbation mass between the two windows; the only free parameter p controls the initial square size.
   • Main ImageNet results (Table 2): untargeted l∞ (ε = 0.05) failure rates on Inception v3/ResNet-50/VGG-16-BN are 0.3/0.0/0.0%, with average queries 197/73/31; l2 (ε = 5) failure rates are 7.1/0.7/0.8%, which the authors state are better than Bandits, SignHunter, DFO, SimBA-DCT, etc.
   • Comparison with white-box attacks: robust accuracy 92.58% on the MNIST TRADES model (Table 4), which the authors state surpasses white-box attacks to achieve a new SOTA; on models with gradient masking, the single-run robust accuracy at l2 ε = 2.5 is 2.4%, whereas PGD100 is 36.0% (Table 5).
   • Defense evaluation: the robust accuracy of post-averaging defenses on ImageNet drops from 76.1% as measured by PGD to 0.4% (Table 12); the authors state that directly applying white-box PGD leads to inaccurate robustness estimates.
   • Authors' conclusion: the authors believe the attack can be used for robustness evaluation even in settings where white-box attacks require many restarts and iterations; follow-up work [21] has incorporated it into AutoAttack.

   Collapse this answer

Related papers