Source-linked AI summary
Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach
Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, Cho-Jui Hsieh
TL;DR
Hard-label black-box attacks must operate with only queried final decisions, making conventional gradient-based optimization ineffective because the resulting objective is discontinuous and combinatorial. The paper reformulates the attack as a usually continuous real-valued problem solvable by zeroth-order methods, with convergence guarantees under a smooth-boundary condition. It reports fewer queries than the prior state-of-the-art attack on CNNs and extends the approach to GBDTs.
Problem
Hard-label black-box attacks provide only final decisions, causing discontinuous objectives that are difficult for gradient-based optimization, while prior boundary random walks require many queries and lack convergence guarantees.
Method
The paper reformulates hard-label black-box attacks as real-valued optimization problems evaluated through queries and solved with zeroth-order optimization.
Results
The method achieves smaller or similar distortion using 3-4 times fewer queries than the state-of-the-art algorithm and successfully attacks CNNs and GBDTs.
Takeaways & Limitations
The framework supports query-efficient hard-label attacks across neural and non-differentiable models, including GBDTs that gradient-based methods cannot attack.
Takeaways & Limitations
The convergence guarantee holds when the decision boundary is smooth, and the paper’s problem setting considers K-way multi-class classification.
Abstract
from arXiv · showhide
We study the problem of attacking a machine learning model in the hard-label black-box setting, where no model information is revealed except that the attacker can make queries to probe the corresponding hard-label decisions. This is a very challenging problem since the direct extension of state-of-the-art white-box attacks (e.g., CW or PGD) to the hard-label black-box setting will require minimizing a non-continuous step function, which is combinatorial and cannot be solved by a gradient-based optimizer. The only current approach is based on random walk on the boundary, which requires lots of queries and lacks convergence guarantees. We propose a novel way to formulate the hard-label black-box attack as a real-valued optimization problem which is usually continuous and can be solved by any zeroth order optimization algorithm. For example, using the Randomized Gradient-Free method, we are able to bound the number of iterations needed for our algorithm to achieve stationary points. We demonstrate that our proposed method outperforms the previous random walk approach to attacking convolutional neural networks on MNIST, CIFAR, and ImageNet datasets. More interestingly, we show that the proposed algorithm can also be used to attack other discrete and non-continuous machine learning models, such as Gradient Boosting Decision Trees (GBDT).
1 Introduction
The paper addresses hard-label black-box attacks, where only final decisions are observable and conventional gradient-based methods cannot handle the resulting discontinuous objectives. It introduces a continuous real-valued reformulation solvable with zeroth-order optimization, achieving query-efficient attacks across neural networks and GBDTs.
- Motivation: Hard-label black-box attacks expose only final decisions, unlike score-based attacks that provide probability outputs.This setting is motivated by real-world models that do not provide probability outputs.
- Motivation: Gradient-based attacks fail because hard-label outputs resist finite differences and produce discontinuous, combinatorial objectives.The lack of model gradients and discontinuity makes direct optimization difficult.
- Approach: The proposed framework reformulates the attack as a usually continuous real-valued optimization problem evaluable through model queries.Any zeroth-order optimizer can then be applied despite the reformulation lacking an analytical expression.
- Approach: With controlled function-evaluation accuracy, Random Gradient-Free optimization is proven to converge to stationary points when the decision boundary is smooth.The paper presents this as the first hard-label black-box attack with a guaranteed convergence rate.
- Results: Experiments show successful attacks on CNNs across MNIST, CIFAR, and ImageNet using far fewer queries than the state-of-the-art algorithm.The method also finds imperceptibly perturbed adversarial examples for GBDTs within 30,000 queries.
2 Background and Related work
The background contrasts white-box optimization, where gradients are available, with hard-label black-box attacks, where only discrete decisions expose a discontinuous objective. Existing boundary random walks require many queries and lack convergence guarantees, motivating the paper’s reformulation.
- White-box attacks: White-box attacks assume the classifier is exposed, allowing back-propagation and gradient-based optimization such as SGD, Adam, or PGD.C&W and EAD formulate attacks using a distance term, attack loss, and balancing parameter.
- Black-box setting: Hard-label black-box attacks reveal only the top-1 predicted label rather than probability outputs.The attacker can query the model but receives limited prediction results.
- Hard-label difficulty: Substituting one-hot hard-label outputs into the loss makes it discrete and discontinuous, unlike the continuous logit-based loss used in white-box attacks.Figure 1 contrasts the continuous C&W loss with its discontinuous hard-label version and the proposed objective.
- Hard-label difficulty: Optimizing the hard-label objective requires combinatorial search that is nearly impossible in high dimensions.This explains why few methods successfully attack hard-label black-box models.
- Prior approach: The prior boundary-based decision attack suffers from exponential search time, many queries, and no convergence guarantees.The paper positions its optimization-based method as reducing queries while guaranteeing convergence in iterations.
3 Algorithms
The paper reformulates hard-label black-box attacks as minimizing the real-valued distance to a decision boundary, then solves the resulting problem with zeroth-order optimization and analyzes convergence under approximate evaluations.
- 3.1 A Boundary-based Re-formulation: The reformulation defines g(θ) as the distance from x0 to the nearest adversarial example along search direction θ.The adversarial example is recovered as x*=x0+g(θ*)θ*/∥θ*∥.
- 3.1 A Boundary-based Re-formulation: Unlike hard-label CW or PGD objectives, g(θ) maps directions to real-valued distances and is usually continuous.This continuity makes zeroth-order optimization applicable even when the classifier itself is non-continuous.
- 3.1 A Boundary-based Re-formulation: Because the method does not require classifier gradients, it also applies to non-differentiable models such as GBDTs.The paper reports finding imperceptible-perturbation adversarial examples for a GBDT within 30,000 queries.
- 3.1 A Boundary-based Re-formulation: The algorithm evaluates g(θ) from hard-label queries by locating a boundary interval and refining it with binary search.Initialization uses fine-grained search followed by binary search; later evaluations first expand or contract a local interval around the previous value.
- 3.2 Zeroth Order Optimization: RGF estimates the gradient with random Gaussian directions and updates θ using a step size η; high-dimensional settings average q estimators and use backtracking line search.The experiments use β=0.005 and q=20.
- 3.3 Theoretical Analysis: The convergence analysis extends RGF to approximate function evaluations, requiring controlled evaluation error and relating the precision to β, δ, d, and L1(g).Binary search obtains the desired function-value precision in O(log δ) steps, and the analysis provides an iteration bound for convergence to stationary points.
4 Experimental results
Experiments on CNNs show that Opt-attack generally achieves lower distortion with fewer queries than Decision-attack, across untargeted and targeted settings. The method also finds small-distortion adversarial examples for GBDTs using about 30K queries.
- Experimental Setup: The evaluation compares Opt-attack, Decision-attack, and C&W on 100 randomly sampled validation images using average L2 distortion and, for black-box methods, query counts.MNIST, CIFAR-10, and ImageNet-1000 CNN models are included.
- Untargeted Attack: Increasing queries reduces the distortion gap between black-box attacks and C&W on ImageNet.The constrained query budget makes black-box distortion much worse than C&W, but Figure 4 shows the gap can be reduced with more queries.
- Targeted Attack: Opt-attack is more than 4 times faster than Decision-attack for targeted MNIST attacks and converges to a better solution.On CIFAR, it has similar efficiency through 60,000 queries but converges to a slightly worse solution.
- Attack Gradient Boosting Decision Tree (GBDT): Opt-attack obtains small distortion on GBDT models from HIGGS and MNIST using around 30K queries.The result identifies vulnerability in tree-based models despite their interpretability and comparable prediction accuracy with CNNs.
5 Conclusion
The paper presents a generic optimization-based hard-label black-box attack for neural and discrete non-continuous models. It combines query efficiency with a theoretical convergence guarantee and achieves smaller or similar distortion using fewer queries than the state-of-the-art method.
- Conclusion: The proposed attack applies to discrete and non-continuous models such as gradient boosting decision trees.It is presented as a generic optimization-based hard-label black-box algorithm.
- Conclusion: The method has a theoretical convergence guarantee and achieves smaller or similar distortion using 3–4 times fewer queries than the state-of-the-art algorithm.The comparison concerns attack performance in the hard-label black-box setting.
6 Appendix
The appendix extends convergence analysis to approximate function evaluations and Gaussian-smoothed gradient estimation, then derives conditions for reaching stationary points. The analysis assumes smoothness and lower-bounded objective values while relating estimator errors to dimension, smoothing, and evaluation precision.
- Approximate evaluation: The algorithm evaluates g(θ) only approximately, with g(θ) − ϵ ≤ ˜g(θ) ≤ g(θ) + ϵ, and defines a finite-difference estimator from these values.The approximation error is controlled by the algorithm’s stopping criterion.
- Gradient estimation: Gaussian smoothing and randomized directional estimates provide the zeroth-order quantities used to analyze the algorithm.The estimator uses a perturbed evaluation ˜g(θ+βu)−˜g(θ), with β controlling the perturbation scale.
- Convergence analysis: Under a Lipschitz-continuous gradient assumption, the analysis bounds estimator moments and approximation terms using L1(g), dimension d, β, and ϵ.The bounds include terms involving (d + 6)^3, (d + 4)||∇g(θ)||2, and the evaluation-error contribution.
- Stationarity guarantee: Assuming g(x) ≥ g*, averaging the descent analysis over iterations relates the expected smoothed-gradient norm to a stationary-point condition.The analysis introduces φk as the conditional expectation of g(θk) and selects β ≤ O(δ d/L1(g)) to target δ^2-level stationarity.