Source-linked AI summary
SurFree: a fast surrogate-free black-box attack
Thibault Maho, Teddy Furon, Erwan Le Merrer
TL;DR
Decision-based black-box attacks expose only labels, and the query reductions achieved in score-based attacks had not reached comparable levels in this harder setting. SurFree avoids surrogate and gradient estimation through geometrically guided trials, and the paper reports improved query efficiency at low budgets while remaining competitive at higher budgets.
Problem
Decision-based black-box attacks receive only labels, and the query reductions achieved by score-based attacks had not reached comparable levels in this more challenging setting.
Source: §1 · p. 2Method
SurFree is a geometrical decision-based attack that avoids surrogate models, score reconstruction, and gradient estimation while exploring directions to reduce distortion.
Source: §1 · p. 2, §5.2 · p. 5Results
At about a thousand queries, SurFree overcomes the state of the art on query amount while remaining competitive with unlimited queries.
Source: §1 · p. 2Takeaways & Limitations
SurFree shows that trials across directions and a geometric distortion-reduction mechanism can produce qualitative adversarials within hundreds of queries.
Source: §7 · p. 9The geometric analysis assumes a locally hyperplane-like boundary, and its 2D analysis assumes that ∂O ∩ P is a line through x_b.
Source: §3 · p. 3, §4.1 · p. 3
Abstract
from arXiv · showhide
Machine learning classifiers are critically prone to evasion attacks. Adversarial examples are slightly modified inputs that are then misclassified, while remaining perceptively close to their originals. Last couple of years have witnessed a striking decrease in the amount of queries a black box attack submits to the target classifier, in order to forge adversarials. This particularly concerns the black-box score-based setup, where the attacker has access to top predicted probabilites: the amount of queries went from to millions of to less than a thousand. This paper presents SurFree, a geometrical approach that achieves a similar drastic reduction in the amount of queries in the hardest setup: black box decision-based attacks (only the top-1 label is available). We first highlight that the most recent attacks in that setup, HSJA, QEBA and GeoDA all perform costly gradient surrogate estimations. SurFree proposes to bypass these, by instead focusing on careful trials along diverse directions, guided by precise indications of geometrical properties of the classifier decision boundaries. We motivate this geometric approach before performing a head-to-head comparison with previous attacks with the amount of queries as a first class citizen. We exhibit a faster distortion decay under low query amounts (few hundreds to a thousand), while remaining competitive at higher query budgets.
1. Introduction
SurFree targets the query cost of decision-based black-box attacks, where only labels are available, by avoiding surrogate estimation and using geometrically guided trials. The paper reports lower distortion under low query budgets and competitiveness at higher budgets.
1. Introduction
- Decision-based attacks are especially challenging because they provide only top-1 labels, while score-based attacks expose predicted probabilities.The cited motivation notes that score-based attacks reduced query counts to under a thousand, a reduction not yet matched in the hard-label setup.Source: §1 · pp. 1–2
- Recent black-box methods use surrogates or gradient estimates to compensate for missing information, spending queries while distortion can stall.The authors identify these query-consuming estimation steps as a motivation for SurFree.Source: §1 · pp. 1–2
- SurFree is a decision-based attack that uses no target-model surrogate, score reconstruction, or gradient estimation.It is inspired by early works [1].Source: §1 · p. 2
- Its geometrical mechanism seeks the greatest distortion decrease along each explored direction under a hyperplane-boundary assumption.The paper also highlights trials along diverse directions as its alternative to gradient-surrogate estimation.Source: §1 · p. 2
- The paper compares recent attacks head-to-head by distortion as a function of query number.This makes query amount central to the comparison rather than treating it as a secondary measure.Source: §1 · p. 2
- At about a thousand queries, SurFree overcomes the state of the art on query amount while remaining competitive with unlimited queries.The paper treats query amount as a central criterion and defines speed by distortion performance under low query budgets.Source: §1 · p. 2
2. Related Works
The related work connects decision-based adversarial attacks to earlier watermarking attacks and contrasts query trends across black-box settings. It also reviews gradient estimation and dimension reduction as design choices in recent attacks.
2.1. Watermarking
- Watermarking attacks already used boundary surjection, boundary-gradient estimation, and dimension reduction; later work [3] resembles the Blind Newton Sensitivity Attack.The watermarking literature also includes random-direction attacks, including and the first decision-based attack [1].Source: §2.1 · p. 2
2.2. Black box adversarial examples
- The paper studies black-box attacks and places white-box attacks [2] [26] [17] outside its scope.Source: §2.2 · p. 2
- On ImageNet, score-based attacks progressed from hundreds of thousands of queries to fewer than one thousand, while decision-based work reached only thousands and had no reported results below one thousand.The cited decision-based sequence goes from about one million queries [1] to tens of thousands [3, 14] and then some thousands [23].Source: §2.2 · p. 2
- Recent decision-based attacks commonly estimate a boundary normal by probing around a boundary point, trading query count against gradient accuracy and convergence.This paper instead spends no queries on gradient estimation.Source: §2.2 · p. 2
- Dimension reduction restricts perturbations to a low-dimensional subspace, increasing distortion at convergence in principle but easing projected-gradient estimation; the paper reports better results with block DCT.Prior methods typically use a low-frequency band of the full DCT transform [23] [14].Source: §2.2 · p. 3
3. Problem statement
The section formulates untargeted black-box evasion as finding a nearby image with a different top-1 label. Its approach assumes that a boundary point can be found and that the boundary is locally approximated by a hyperplane.
3. Problem statement
- The classifier f maps images in [0, 1]^D to class scores, and cl(x) is the class with the highest predicted probability.Source: §3 · p. 3
- Given a well-classified original image x_o, the untargeted objective is to find a nearby x_a whose top-1 label differs; the paper frames the task as finding an approximate solution.The outside region O consists of points whose predicted label differs from that of x_o.Source: §3 · p. 3
- The setup assumes a boundary point can be found along the segment from x_o to an outside point, and that the boundary is locally approximated by a hyperplane.The authors cite experimental evidence for a smooth, low-curvature boundary in deep neural networks.Source: §3 · p. 3
4. Our Approach
SurFree replaces costly gradient estimation with searches along multiple directions, guided by decision-boundary geometry. Under a hyperplane model, the approach yields a minimal-distortion point; for smooth convex boundaries, repeated coordinate descent is described as converging to a local minimum.
4. Our Approach
- Gradient-estimation plateaus motivate setting that query budget to zero and spending queries on more directions to seek faster distortion decrease.The paper frames query amount as central and notes that gradient-estimation queries leave the adversarial example unchanged.Source: §4 · p. 3
4.1. Basic idea
- In a 2D plane through the original image and a boundary point, a coupled angle-distance search uses boundary geometry to seek a closer adversarial point despite the unknown optimal angle.Under a locally linear boundary, the optimal point is the projection of the original image onto the boundary line; its angle is unknown to the attacker.Source: §4.1 · pp. 3–4
4.2. Iterations over orthonormal directions
- Under an affine-hyperplane boundary, iterating over orthonormal directions converges to the adversarial point with minimal distortion, whose displacement from the original image is colinear with the normal.The paper notes that ordering directions by decreasing angle could yield the biggest decreases first, but is out of reach without estimating the normal.Source: §4.2 · p. 4
4.3. Convex boundary
- For a smooth convex boundary, cycling through the coordinate directions multiple times ensures convergence to a local minimum.The paper describes this as random coordinate descent and notes that its convergence rate and query cost relative to gradient estimation merit investigation.Source: §4.3 · p. 4
5. The SurFree attack
SurFree iteratively searches for closer boundary points using sign tests and binary refinement, without estimating gradients. Its directions are randomized, reduced in frequency space, and shaped by image content; an optional interpolation step addresses curved boundaries.
5.1. The algorithm
- Each iteration builds a direction orthogonal to the current displacement and recent directions, tests signed angles until finding an adversarial point, then uses binary search to refine the boundary point.If sign search fails, the algorithm decreases the angle range and generates another direction.Source: §5.1 · pp. 4–5
5.2. Distribution of the directions
- Random directions serve both dimension reduction and adaptation to image content, using selected low-frequency transform coefficients whose amplitudes are shaped by the original image.The paper links content-shaped perturbations to a masking effect that can make them less perceptible.Source: §5.2 · p. 5
5.3. Interpolation
- Optional interpolation, inspired by watermarking attacks, targets smooth convex boundaries by fitting angle-to-distance behavior from three boundary points and searching near the fitted minimum.A binary search then finds the new boundary point between the original image and the candidate at the fitted angle.Source: §5.3 · p. 5
6. Experimental Work
The experiments evaluate SurFree on MNIST and ImageNet through component ablations and head-to-head query-budget benchmarks. They report a low-query advantage while probing how direction-generation choices and iteration costs affect distortion.
6.1. Datasets and Experimental Setup
- Tests use 100 MNIST images and 350 ImageNet validation images; distortion is measured by ℓ2 norm, and success rate is reaching target distortion within a query budget.MNIST uses a 99.14%-accurate CNN; ImageNet uses a pre-trained ResNet18.Source: §6.1 · p. 6
6.2. Ablation Studies
- The ablation averages distortion over 100 images and measures run-to-run standard deviation over 20 attacks on one MNIST image.Direction generation is random and can produce unstable distortion across adversarial images.Source: §6.2 · p. 6, Figure 4 · p. 7, Figure 5 · p. 7
- SurFree balances averaged distortion and standard deviation; unlike SignSearch, it exhausts each explored direction under the hyperplane assumption.SignSearch is competitive only at the beginning, while interpolation can improve distortion but costs two additional binary searches.Source: §6.2 · p. 6
- κ has no significant impact when κ > 0, and increasing T brings no benefit because line 12 already performs a finer search.Source: §6.2 · p. 6
- ImageNet ablations favor constrained DCT directions early and 50% over 25%; block DCT with tanh shaping gives early drops and long-run levels similar to constant shaping.The chosen configuration uses tanh shaping on 50% of DCT8×8 coefficients.Source: Table 1 · p. 7, §6.2 · p. 7
6.3. Benchmarking
- SurFree lowers distortion significantly faster than all attacks from 1 to 750 queries, while QEBA prevails around 3,750.Figure 6 plots mean distortion against query count on ImageNet.Source: Figure 6 · p. 7, §6.3 · p. 8
- SurFree remains the best attack for every target distortion up to a 2,000-query budget.Success rate is evaluated across target distortions and query budgets on ImageNet.Source: Figure 7 · p. 8, Table 2 · p. 8, §6.3 · p. 8
- At 10,000 queries, ℓ2 distortion was 2.09 (QEBA) < 2.72 (SurFree) < 3.48 (HSJA 10) < 4.63 (GeoDA).Source: §6.3 · p. 8
7. Conclusion
Decision-based attacks have important query-efficiency gaps, and SurFree addresses them with a geometrical attack that reaches qualitative adversarials within hundreds of queries.
7. Conclusion
- Black-box decision-based attacks have important gaps in the number of queries they require.Source: §7 · p. 8
- SurFree’s multiple-direction trials and best-distortion-decrease mechanism converge to qualitative adversarials within hundreds of queries.The conclusion contrasts this with costly gradient estimation in the three state-of-the-art approaches considered.Source: §7 · p. 9
- The three state-of-the-art approaches considered rely on gradient estimation, which is particularly costly compared with SurFree’s geometrical attack.Source: §7 · p. 9