Sign-OPT: A query-efficient hard-label adversarial attack

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

   Reducing the query cost of hard-label black-box adversarial attacks: existing methods typically require more than 20,000 queries to attack a single sample.

   Core problem: under a black-box setting where only model prediction labels (hard-label) are available, how to generate adversarial examples with fewer queries.

   • Scenario and importance: The authors consider this the most practical restricted-access setting for evaluating the robustness of machine learning systems—the model is hidden from the attacker, who can only query it and obtain decision results. Existing hard-label attack algorithms typically require more than 20,000 queries to attack a single sample.
   • Shortcomings of existing methods: The Boundary attack is based on a random walk on the decision surface, and the authors point out that it has no convergence guarantee; Cheng et al. (2019) rewrite the hard-label attack as an optimization problem that can be solved with zeroth-order optimization, but each function evaluation relies on a binary search and consumes dozens of queries, so attacking a single image still requires about 20,000 queries.
   • Core observation: The authors believe that (i) algorithm convergence does not require very precise directional derivative values; (ii) there exists an imperfect but informative estimate of the directional derivative whose sign can be computed with only one query.
   • Method proposed in the paper: Based on a single query oracle, it designs a new zeroth-order optimization algorithm, Sign-OPT, as well as a variant, SVM-OPT, that recovers the gradient using an SVM, and provides a convergence analysis.
   • Threat model:
     • Attacker's goal: For a given sample, generate a small perturbation that makes the model misclassify it (untargeted) or predict a specified target class (targeted), measured by L2 perturbation.
     • Attacker's knowledge: hard-label black-box—does not know the model structure or weights.
     • Attacker's capability: Can query the model and obtain the corresponding hard-label decision (top-1 predicted class), with a limited number of queries.
     • Victim system: Image classification models (CNN on MNIST/CIFAR-10, ResNet-50 on ImageNet).

   Collapse this answer

2. 02What related research exists?

   Related work is divided into three groups: white-box attacks, soft-label black-box attacks, and hard-label black-box attacks; this paper belongs to the third group.

   White-box attacks

   • Goodfellow et al. (2015), Carlini & Wagner (2017), Madry et al. (2017), etc. — construct gradient-based attacks under the setting where the model is fully exposed to the attacker; representative methods include C&W and PGD.
   • Athalye et al. (2018) — proposed the BPDA attack, bypassing defenses that use obfuscated gradients.

   Soft-label (probability output) black-box attacks

   • Chen et al. (2017) — used coordinate-wise finite differences to estimate changes in output probabilities and performed coordinate descent; Ilyas et al. (2018a) used NES to directly estimate gradients; subsequent variants (Ilyas et al., 2018b; Tu et al., 2019) used side information to accelerate.
   • Al-Dujaili & O'Reilly (2019) — proposed SignHunter based on signSGD, using sign estimation to accelerate convergence in the soft-label setting.
   • Liu et al. (2019) — designed ZO-SignSGD for soft-label black-box attacks; the paper points out that its estimator takes the sign of the entire vector and ignores the direction of the random direction uq, converging more slowly in practice (see Section 4.4 and Figure 5(b)).

   Hard-label black-box attacks

   • Brendel et al. (2017) — first studied this problem, proposing the Boundary attack based on random walks near the decision boundary; the paper points out that it has no convergence guarantee.
   • Ilyas et al. (2018a)'s Query-Limited attack — used queries to estimate probability scores, converting the hard-label problem into a soft-label problem.
   • Cheng et al. (2019) — reformulated the hard-label attack as an optimization problem of "finding the shortest direction to the decision boundary" (the paper calls this Cheng's formulation); this paper follows this formulation.
   • Chen et al. (2019) (HopSkipJumpAttack) — used a zeroth-order sign oracle to improve the Boundary attack; the paper points out that the difference is that this paper proposes a new zeroth-order gradient descent algorithm, provides a convergence guarantee, reduces query complexity for Cheng's formulation, and that the other uses single-point gradient estimation with larger variance (comparison in Appendix A.1).

   Baselines and benchmarks: The comparison baselines are the Boundary attack, the OPT-based attack (Cheng et al., 2019), the Guessing Smart Attack (Brunner et al., 2018; the prior relying on similar models is removed in the experiments) and the white-box C&W L2 attack; the datasets are MNIST, CIFAR-10 and ImageNet-1000.

   The authors position this paper as: following the smoothness advantage of Cheng's formulation, but replacing finite differences with single-query sign estimation, thereby reducing the query complexity of hard-label attacks by 5–10 times.

   Collapse this answer

3. 03How does the paper address this problem?

   Following Cheng's formulation, it estimates the sign of the directional derivative with a single query and constructs a new zeroth-order gradient descent algorithm, Sign-OPT.

   Overall approach: It follows Cheng et al. (2019) in formulating the hard-label attack as an optimization problem of "finding the direction with the shortest distance to the decision boundary," but does not estimate the magnitude of the directional derivative; instead, it estimates its sign with a single query, and on this basis designs the Sign-OPT algorithm.

   Problem formulation

   • Given a sample x0, the true label y0, and a hard-label black-box function f, the goal of the untargeted attack is min_θ g(θ), where g(θ) = argmin_λ>0 f(x0 + λθ/|θ|) ≠ y0, i.e., the shortest distance to the decision boundary along direction θ.
   • The authors state that this objective function is usually smooth and that the value of g can be obtained by binary search using hard-label queries; however, Cheng et al. (2019) require a binary search for each evaluation, consuming dozens of queries.

   Single-query sign oracle

   • Key design: For a new direction θ+εu, query the model once at a distance g(θ) from x0; if the prediction is not equal to y0, take +1, otherwise take −1, i.e., obtain sign(g(θ+εu) − g(θ)).
   • Meaning: If the point falls outside the boundary, the new direction has a smaller distance to the boundary, and u is a descent direction that decreases g; each sign requires only 1 query.

   Sign-OPT algorithm

   • At each iteration, sample Q random vectors uq (Gaussian or uniform distribution), estimate the gradient with ĝ = 1/Q∑_q sign(g(θ+ϵ u_q)−g(θ)) · u_q, requiring only Q queries, then update θ ← θ − ηĝ with step size η.
   • Difference from ZO-SignSGD (Liu et al., 2019): The latter takes the sign of the entire vector, whereas Sign-OPT retains the magnitude information of the random direction uq; the authors state that this makes it a new zeroth-order optimization algorithm to which existing convergence analyses do not apply.
   • Convergence result: Under the assumptions that g is L-smooth, the gradient is bounded, and the gradient noise is unimodal and symmetric, taking ηt = O(1/√(QdT)) and ε = O(1/(dT)) gives E[‖∇g(θ)‖²] = O(√d/√T + d/√Q) (Theorem 3.1, proof in Appendix A.2).

   SVM-OPT variant

   • Treat each sign yq = sign(⟨∇g(θ), uq⟩) as the label of sample uq, solve a hard-margin SVM quadratic program to recover a more accurate gradient estimate z, then update θ (Algorithm 2).

   Implementation details

   • The step size η is estimated using the same line search as Cheng et al. (2019); g(θ) is approximated by binary search; the initial θ0 is obtained by taking the best of g(θ) over 100 random directions (for targeted attacks, 100 training samples of the target class are used).
   • Success criterion: median distortion (the median of the adversarial perturbations of all samples within x queries) is the main metric, supplemented by the success rate at a given threshold ε.

   Collapse this answer

4. 04What experiments did the paper conduct?

   Comparing 4 attacks on MNIST, CIFAR-10 and ImageNet, the authors claim Sign-OPT uses 5–10 times fewer queries and has smaller perturbations.

   Experimental setup

   • Models tested: For MNIST and CIFAR-10, the CNN (nine layers) provided by Carlini & Wagner (2017), with accuracies of 99.5% and 82.5% respectively; for ImageNet-1000, the torchvision pretrained ResNet-50, with Top-1 accuracy of 76.15%.
   • Datasets: MNIST, CIFAR-10, ImageNet-1000; each attack randomly samples 100 examples from the validation set (for untargeted, only correctly classified examples are taken).
   • Baselines: Boundary attack, OPT-based attack (Cheng et al., 2019), Guessing Smart Attack (with the prior relying on similar models removed), white-box C&W L2 attack.
   • Metrics: median distortion (the median adversarial perturbation reached within x queries) as the primary metric; success rate (the proportion of examples whose perturbation is below threshold ε within x queries), with the threshold depending on the dataset (MNIST ε=1.5, CIFAR-10 ε=0.5, ImageNet ε=3.0).
   • Hyperparameters: Q = 200 (tuned on a small number of examples, used for all experiments in this section); the paper does not report the number of repetitions.

   Main results

   Table 1: untargeted L2 attacks, average L2 perturbation and SR at a given number of queries.

   Swipe horizontally to read the table

   Method	MNIST 14k queries Avg L2 / SR(ε=1.5)	CIFAR-10 12k queries Avg L2 / SR(ε=0.5)	ImageNet 160k queries Avg L2 / SR(ε=3.0)
   Boundary	2.13 / 16.3%	0.78 / 29.2%	4.62 / 41.6%
   OPT	1.76 / 36.0%	0.33 / 61.0%	4.27 / 34.0%
   Guessing Smart	1.68 / 43.0%	0.24 / 80.0%	12.88 / 12.0%
   Sign-OPT	1.09 / 94.0%	0.13 / 95.0%	1.21 / 90.0%
   C&W (white-box)	0.88 / 99.0%	0.25 / 85.0%	1.51 / 80.0%

   • The authors claim Sign-OPT consistently outperforms existing hard-label methods in query efficiency and in most cases converges to smaller perturbations.
   • The authors claim Sign-OPT's solutions are comparable to white-box C&W: better on CIFAR-10, worse on MNIST, comparable on ImageNet (according to the last row of Table 1 and Figure 4).
   • ImageNet exception: at 4,000 and 30,000 queries, Guessing Smart's average perturbation (16.69, 13.27) is smaller than Sign-OPT's (early points before 23.19, 2.99); by 30,000 queries Sign-OPT reaches 2.99 with SR 50.0%, and the authors claim other attacks need more than 200k queries to reach a median perturbation of 3.0.

   Targeted attacks

   • What was tested: targeted L2 attacks on MNIST and CIFAR-10 (Figure 5(a)). Results: the authors claim the C&W white-box attack has an average perturbation of 1.51 on MNIST, and Sign-OPT takes about 12k queries to reach that level, while other methods need more than 120k.
   • Single-example example (Figure 2): on one MNIST example, Sign-OPT obtains an L2 perturbation of 0.94 in about 6k queries, while the OPT-based attack takes about 35k queries to reach the same level.
   • CIFAR-10 success rate (Figure 6): for untargeted and targeted at thresholds ε=0.6 and ε=0.3, the Sign-OPT curve is overall above the other methods (only the relative positions of the curves are readable in the figure).

   Effectiveness of the single-query oracle

   • What was tested: extending ZO-SignSGD to the hard-label setting, comparing "directly combining with Cheng et al. (2019)'s binary search estimation" and "adding the single-query sign oracle" (Figure 5(b), CIFAR-10).
   • Results: the authors claim that simply combining ZO-SignSGD with Cheng et al. (2019) is not efficient, and that adding the single-query oracle reduces the number of queries; Sign-OPT still outperforms ZO-SignSGD with the single-query oracle, which the authors explain as its gradient preserving the magnitude of u.

   Other ablations and analyses

   • Sign-OPT vs SVM-OPT (first two panels of Figure 3, MNIST/CIFAR-10, L2, targeted and untargeted): the two have comparable query efficiency, so the paper reports only Sign-OPT in the main experiments.
   • Effect of Q (third panel of Figure 3, CIFAR-10, Q=10 to 1000): the authors claim Q does not affect the final convergence point; a small Q means noisier gradient estimates and delayed convergence, while a large Q means each estimation takes longer, and Q=200 is a reasonable balance.
   • Comparison with HopSkipJumpAttack (Appendix A.1, Figure 7, MNIST/CIFAR-10, L2): the authors claim the two consume comparable queries, and in some cases Sign-OPT converges to a better solution; the authors believe the other's single-point estimation has larger variance, being slightly faster initially but ending with slightly larger perturbation.

   Collapse this answer

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

   The paper does not specifically discuss limitations; the experiments are limited to 3 image datasets, 2 models, and 100 samples per attack.

   Limitations and future directions noted by the authors

   • The paper does not specifically discuss limitations (no Limitations or Future Work section).
   • Section 4.1 mentions: a small Q introduces noise into the gradient estimate and delays convergence, while a large Q makes each gradient estimate more time-consuming—this is a hyperparameter trade-off stated by the authors, not a separate discussion of limitations.

   Experimental coverage

   • Models tested: 2—a CNN on MNIST/CIFAR-10 (the nine-layer network provided by Carlini & Wagner) and ResNet-50 on ImageNet (Section 4).
   • Datasets: three image classification datasets, MNIST, CIFAR-10, and ImageNet-1000; 100 validation samples are randomly drawn for each attack (Section 4).
   • Attack settings cover untargeted and targeted, with the L2 norm; the Boundary attack is compared only under the L2 setting (Section 4).
   • Compared methods: Boundary, OPT-based, Guessing Smart, white-box C&W, as well as HopSkipJumpAttack in Appendix A.1 and the ZO-SignSGD variant in Section 4.4.
   • The paper does not report the number of repetitions per setting, statistical significance tests, or the actual runtime of the attacks (it only mentions that each estimate is time-consuming when Q is large).

   Collapse this answer

6. 06Summarize the main content of the paper

   Sign-OPT reduces the number of queries for hard-label black-box attacks by 5–10 times using single-query sign estimation (as stated by the authors), and it has a convergence guarantee.

   An ICLR 2020 adversarial attack paper that targets the hard-label black-box setting—where the attacker can only query the model and obtain the top-1 predicted label—to generate L2 adversarial examples.

   • Problem: Existing hard-label attacks (such as Boundary and the OPT-based method of Cheng et al. 2019) typically require more than 20,000 queries to attack a single sample, because each function evaluation requires a binary search.
   • Method: It follows Cheng's formulation (finding the direction with the shortest distance to the decision boundary), but estimates only the sign of the directional derivative rather than its magnitude: querying once at distance g(θ) along a new direction yields one sign, and Q queries form a gradient estimate, combined with a new zeroth-order gradient descent update (retaining the magnitude of the random direction, unlike ZO-SignSGD). The authors provide a convergence analysis: E[‖∇g(θ)‖²] = O(√d/√T + d/√Q).
   • Main results (untargeted L2, Table 1): On MNIST at 14,000 queries, average perturbation 1.09, SR(ε=1.5) 94.0% (OPT: 1.76 / 36.0%); on CIFAR-10 at 12,000 queries, 0.13, SR(ε=0.5) 95.0%; on ImageNet ResNet-50, median perturbation below 3.0 within 30,000 queries, and the authors state that other attacks require more than 200,000.
   • Authors' conclusions: Sign-OPT uses 5–10 times fewer queries than existing methods, yields smaller perturbations in most cases, and its solutions are comparable to white-box C&W; the authors believe the single-query sign oracle can generally improve various optimization methods under the hard-label setting and can serve as a practical query-efficient robustness evaluation tool.

   Collapse this answer

Related papers