PaperlayerView exact revision on arXiv

Source-linked AI summary

Sign-OPT: A Query-Efficient Hard-label Adversarial Attack

Minhao Cheng, Simranjit Singh, Patrick Chen, Pin-Yu Chen, Sijia Liu, Cho-Jui Hsieh

arXiv:1909.10773v3cs.LGstat.ML

TL;DR

Hard-label black-box attacks must generate adversarial examples when the model is hidden and only hard-label decisions are available, but existing methods can require more than 20,000 queries per example. Sign-OPT keeps Cheng et al.’s smooth optimization formulation and uses a single-query directional-derivative sign oracle, achieving 5–10 times fewer queries and usually smaller perturbations while providing convergence analysis.

  • Problem

    Hard-label black-box attacks expose only model decisions, and existing approaches can require more than 20,000 queries to attack one example.

  • Method

    Sign-OPT retains Cheng et al.’s optimization formulation and estimates the sign of a directional derivative with a single hard-label query.

  • Results

    5–10 times fewer queries are reported across models and datasets, and adversarial examples with smaller distortion are usually found.

  • Takeaways & Limitations

    Sign-OPT is presented as a practical, query-efficient tool for hard-label black-box robustness evaluation.

  • Takeaways & Limitations

    The convergence analysis assumes that the objective is L-smooth with bounded gradients and unimodal, symmetric gradient noise.

Abstract

from arXiv · show

We study the most practical problem setup for evaluating adversarial robustness of a machine learning system with limited access: the hard-label black-box attack setting for generating adversarial examples, where limited model queries are allowed and only the decision is provided to a queried data input. Several algorithms have been proposed for this problem but they typically require huge amount (>20,000) of queries for attacking one example. Among them, one of the state-of-the-art approaches (Cheng et al., 2019) showed that hard-label attack can be modeled as an optimization problem where the objective function can be evaluated by binary search with additional model queries, thereby a zeroth order optimization algorithm can be applied. In this paper, we adopt the same optimization formulation but propose to directly estimate the sign of gradient at any direction instead of the gradient itself, which enjoys the benefit of single query. Using this single query oracle for retrieving sign of directional derivative, we develop a novel query-efficient Sign-OPT approach for hard-label black-box attack. We provide a convergence analysis of the new algorithm and conduct experiments on several models on MNIST, CIFAR-10 and ImageNet. We find that Sign-OPT attack consistently requires 5X to 10X fewer queries when compared to the current state-of-the-art approaches, and usually converges to an adversarial example with smaller perturbation.

1 INTRODUCTION

The paper targets hard-label black-box attacks, where only model decisions are available, and introduces Sign-OPT to reduce the query burden of optimization-based attacks.

  • 1 INTRODUCTION: Hard-label black-box attacks expose only queried input decisions while hiding the victim model.This setting is presented as a practical and challenging setup for generating adversarial examples.
  • 1 INTRODUCTION: Cheng’s formulation enables zeroth-order optimization because its objective is computable through hard-label queries and has a smooth boundary in most tasks.However, each objective evaluation requires binary search with tens of queries.
  • 1 INTRODUCTION: 20,000 queries can still be required to attack a single image with Cheng et al.’s approach.The high cost arises because every function evaluation uses additional binary-search queries.
  • 1 INTRODUCTION: Sign-OPT evaluates the sign of a directional derivative with one query instead of estimating its magnitude through finite differences.The method retains Cheng et al.’s smooth optimization formulation while introducing a single-query sign oracle.
  • 1 INTRODUCTION: 5–10 times fewer queries are reported across different models and datasets, with smaller distortion on most datasets than previous approaches.The paper presents these experiments as evidence of a practical, query-efficient robustness evaluation tool.

2 RELATED WORK

Related work spans white-box gradient attacks and query-based black-box attacks, including hard-label methods based on boundary exploration and zeroth-order optimization.

  • 2 RELATED WORK: White-box attacks assume the classifier, network structure, and weights are exposed, enabling back-propagation and gradient-based methods.The cited examples include attacks by Goodfellow et al., Kurakin et al., Carlini and Wagner, Chen et al., and Madry et al.
  • 2 RELATED WORK: Black-box attacks allow model queries without direct access to internal information, and are categorized by whether feedback is soft-label or hard-label.Soft-label feedback provides probability scores, whereas hard-label feedback provides only the final decision.
  • 2 RELATED WORK: Hard-label attacks observe only the top-1 predicted class and include Boundary attack, which explores random directions near the decision boundary.Other query-based work attempts to estimate output probability scores from limited feedback.
  • 2 RELATED WORK: The paper distinguishes its method from prior zeroth-order sign-oracle work by introducing a new optimizer, proving convergence, and targeting Cheng’s attack formulation’s query complexity.It also reports comparisons with the recent method in an appendix.

3 PROPOSED METHOD

Sign-OPT reformulates hard-label attacks as finding a direction with minimal distance to the decision boundary, then uses single-query directional-derivative signs to reduce zeroth-order optimization cost. The paper also introduces SVM-OPT, which recovers a gradient estimate from these signs through a hard-constraint optimization problem.

  • Optimization formulation: The attack minimizes g(θ), the distance from x0 to the decision boundary along direction θ, using only hard-label queries.Locally, g(θ) is evaluated by binary search over λ, querying whether x0 + λθ/∥θ∥ remains correctly classified.
  • Optimization formulation: Finite-difference directional-derivative estimates require many queries because each g evaluation uses binary search.This query cost motivates replacing derivative magnitudes with a cheaper sign estimate.
  • A single-query oracle: A single query determines whether g(θ + ϵu) is smaller or larger than g(θ) by testing the point at distance g(θ) along the perturbed direction.If that point is misclassified, the perturbed direction reaches the boundary at a smaller distance and u is a descent direction.
  • Sign-OPT attack: Sign-OPT samples Q random directions and averages sign(g(θ + ϵu_q) − g(θ))u_q to form an imperfect gradient estimate.The estimate requires Q queries, after which θ is updated by θ ← θ − ηĝ and g(θ) is recomputed using the existing search procedure.
  • Convergence analysis: The method’s convergence analysis assumes smoothness, bounded gradients, and unimodal symmetric gradient noise, while accounting for random-direction magnitudes.This differs from signSGD-style analysis that uses only elementwise signs.
  • Other gradient estimations: SVM-OPT treats directional signs as hard-constraint labels and estimates the gradient by solving a quadratic program, with each sign obtained from one query.The resulting estimate updates θ in the same optimization framework as Sign-OPT.

4 EXPERIMENTAL RESULTS

Experiments evaluate Sign-OPT against hard-label and white-box baselines across MNIST, CIFAR-10, and ImageNet, using query efficiency, distortion, and success rate. Sign-OPT generally reduces queries while achieving competitive or lower distortion, with Q=200 selected as a practical balance.

  • Experimental setup: Experiments compare Sign-OPT with Opt-based, Boundary, Guessing Smart, and C&W attacks on MNIST, CIFAR-10, and ImageNet.The evaluation samples 100 validation examples per attack and uses the same examples across methods.
  • Evaluation metrics: Median distortion is measured at query budgets, while success rate records the fraction reaching a dataset-specific distortion threshold.Median distortion is computed over examples attacked with fewer than the specified number of queries.
  • Comparison between Sign-OPT and SVM-OPT: Sign-OPT and SVM-OPT achieve nearly identical query efficiency across settings and datasets, including both targeted and untargeted attacks.For MNIST and CIFAR-10, their median distortions at a given query count are reported as being roughly on par.
  • Comparison between Sign-OPT and SVM-OPT: Q=200 provides a practical balance between noisy estimates from small Q and the higher time cost of large Q.The experiments report little impact of Q on the final convergence point, but delayed convergence for small Q.
  • Untargeted attack: Sign-OPT consistently outperforms prior hard-label approaches in untargeted attacks and usually converges to lower distortion.Its distortion is comparable with C&W on ImageNet, better on CIFAR-10, and worse on MNIST.
  • Targeted attack: For one targeted example, Sign-OPT achieves L2 distortion 0.94 in approximately 6k queries, whereas the Opt-based attack needs approximately 35k queries for the same example.For MNIST at C&W’s average distortion of 1.51, Sign-OPT requires approximately 12k queries while other methods require more than 120k.
  • The power of single query oracle: The single-query oracle is evaluated against a straightforward hard-label adaptation of ZO-SignSGD, which is observed to be inefficient.The comparison tests methods with and without the single-query oracle.

5 CONCLUSION

The paper presents Sign-OPT as an ultra query-efficient hard-label black-box attack, combining a single-query sign oracle with a new optimization algorithm and convergence analysis.

  • 5 CONCLUSION: Sign-OPT computes the sign of the attack objective’s directional derivative using a single hard-label query.It uses Cheng et al.’s smooth reformulation while replacing magnitude estimation with sign estimation.
  • 5 CONCLUSION: The authors design a new zeroth-order optimization algorithm around this single-query oracle.The method targets the hard-label black-box attack setting.
  • 5 CONCLUSION: The paper proves convergence and reports that Sign-OPT dramatically reduces query counts compared with Cheng et al. (2019).The conclusion also states that it is overwhelmingly better than current hard-label black-box attacks.

A.1 COMPARISON WITH HOPSKIPJUMPATTACK

The comparison evaluates Sign-OPT against HopSkipJumpAttack on CIFAR-10 and MNIST using L2 attack distortion versus query count. Their query performance is comparable, while Sign-OPT sometimes reaches a better solution.

  • A.1 COMPARISON WITH HOPSKIPJUMPATTACK: HopSkipJumpAttack uses a one-point gradient estimate, whereas Sign-OPT uses a two-point gradient estimate.The one-point estimate is unbiased but has larger variance, while Sign-OPT produces smaller distortion in the cited comparison.
  • A.1 COMPARISON WITH HOPSKIPJUMPATTACK: Sign-OPT and HopSkipJumpAttack are compared on CIFAR-10 and MNIST for L2 norm-based attacks.Figure 7 reports median distortion versus queries for untargeted and targeted attacks.
  • A.1 COMPARISON WITH HOPSKIPJUMPATTACK: Their performance is comparable in terms of queries consumed.This comparison concerns both datasets shown in Figure 7.
  • A.1 COMPARISON WITH HOPSKIPJUMPATTACK: In some cases, Sign-OPT converges to a better solution than HopSkipJumpAttack.The passage does not specify which individual dataset or attack mode produces this outcome.

A.2 PROOF

The proof develops bounds for zeroth-order gradient-sign estimation and establishes convergence under smoothness, bounded-gradient, and symmetric unimodal noise assumptions.

  • A.2 PROOF: The zeroth-order gradient estimate is biased for g but unbiased for the randomized smoothing function gϵ(θ) = Eu[g(θ + ϵu)].The proof therefore analyzes the smoothed objective rather than directly treating the estimate as unbiased for g.
  • A.2 PROOF: The analysis assumes that g is L-smooth with finite L and that ∥∇g(θt)∥2 is bounded by σ.These assumptions provide the regularity and gradient bound used in the convergence argument.
  • A.2 PROOF: The proof bounds the variance of the zeroth-order gradient estimate and the probability that its estimated coordinate sign is incorrect.The sign-error bound scales with the coordinate gradient magnitude and √Q.
  • A.2 PROOF: The coordinatewise sign analysis interprets the aggregate estimator through weighted Bernoulli trials over Q random directions.The weighting uses the absolute coordinate magnitudes of the sampled directions.
  • A.2 PROOF: Theorem 1 gives a convergence rate for Sign-OPT under the stated assumptions and a learning rate ηt = O(1/Q).The supplied theorem passage states the learning-rate order and convergence result, while the surrounding proof derives it from smoothness and estimator bounds.

DISCLAIMER

The document includes a government-work disclaimer concerning sponsorship, warranties, liability, and intellectual-property rights.

  • DISCLAIMER: The report was prepared as an account of work sponsored by a United States Government agency.The disclaimer identifies sponsorship context without describing the research findings.
  • DISCLAIMER: The United States Government and its agencies disclaim warranties about the accuracy, completeness, or usefulness of the disclosed work.The disclaimer also denies responsibility for implied warranties.
  • DISCLAIMER: The disclaimer states that the government assumes no legal liability and does not warrant freedom from infringement of privately owned rights.This is a legal scope statement attached to the report.
Loading 1909.10773v3…