Skip to content

Query-efficient hard-label black-box attacks: an optimization-based approach

Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach

arXiv· arXiv:1807.04457· Minhao Cheng, Thong Le, Pin-Yu Chen, Jinfeng Yi, Huan Zhang, Cho-Jui HsiehDepartment of Computer Science, University of California, Davis; IBM Research; JD AI ResearchIndexed by this site · 23 days ago· Originally publishedAttacks

Quick read

Attacks

Based on the paper PDF (AI-generated); refer to the original

The authors propose Opt-attack, which rewrites the hard-label black-box attack as a continuous optimization problem of the distance along a direction to the decision boundary, and the authors state that on MNIST it uses 3–4 times fewer queries than Decision-attack.

Threat modelhard-label black-box: the attacker does not know the model's internal information and can only obtain the hard-label decision (top-1 predicted class) corresponding to an input through queries, with no probability output; the goal is to find an adversarial example near the original sample that is misclassified (or classified as the target class). The victim systems are CNN image classification models and GBDT.

Questions
A hard-label black-box model returns only the top-1 class and no probabilities, so the white-box attack objective function becomes a discontinuous step function and cannot be directly optimized with gradients; the only prior method, Decision-attack, requires a large number of queries and has no convergence guarantee.
Methods
The attack is rewritten as a real-valued optimization problem over the distance g(θ) along direction θ to the decision boundary; g is evaluated through hard-label queries using fine-grained search plus binary search, then solved with Randomized Gradient-Free (RGF) zeroth-order optimization, and a convergence analysis is given.
Experiments and results
On CNNs for MNIST, CIFAR-10, and ImageNet, Opt-attack achieves smaller or similar L2 perturbations with fewer queries (the authors state that on MNIST the number of queries is reduced by 3–4 times); on GBDT for HIGGS and MNIST, it finds small-perturbation adversarial examples within about 30K queries.
Limitations and future work
The authors state that on ImageNet, because the number of queries was limited, the perturbations of the black-box attack are noticeably larger than those of the C&W white-box attack; in the CIFAR targeted attack, Opt-attack converges to a solution slightly worse than Decision-attack. The models tested are three CNNs and LightGBM GBDT, with N=100 images sampled per setting.
Experimental setupCNN (MNIST)、CNN (CIFAR-10) et al. · MNIST、CIFAR-10 et al. · Avg L2 distortion、average number of queries et al.
Evaluated models
CNN (MNIST)CNN (CIFAR-10)ResNet-50GBDT (HIGGS)GBDT (MNIST)
Benchmarks
MNISTCIFAR-10ImageNet-1000HIGGS
Metrics
Avg L2 distortionaverage number of queriesattack success rate
AI summaryThe researchers propose a hard-label black-box adversarial attack method against machine learning models, which turns the attack into a usually continuous real-valued optimization problem that can be solved with any zeroth-order optimization algorithm. In this setting the attacker can only query the model's hard-label decisions; directly applying white-box attacks such as CW and PGD requires minimizing a discontinuous step function, which cannot be solved with gradient-based optimizers; the only prior method was random walk along the decision boundary, which requires many queries and lacks convergence guarantees. When using the Randomized Gradient-Free method, the new algorithm can give an upper bound on the number of iterations needed to reach a stationary point; on MNIST, CIFAR and ImageNet it outperforms the random walk method in attacking convolutional neural networks, and it can also be used to attack discrete, non-continuous machine learning models such as GBDT.

The researchers propose a hard-label black-box adversarial attack method against machine learning models, which turns the attack into a usually continuous real-valued optimization problem that can be solved with any zeroth-order optimization algorithm. In this setting the attacker can only query the model's hard-label decisions; directly applying white-box attacks such as CW and PGD requires minimizing a discontinuous step function, which cannot be solved with gradient-based optimizers; the only prior method was random walk along the decision boundary, which requires many queries and lacks convergence guarantees. When using the Randomized Gradient-Free method, the new algorithm can give an upper bound on the number of iterations needed to reach a stationary point; on MNIST, CIFAR and ImageNet it outperforms the random walk method in attacking convolutional neural networks, and it can also be used to attack discrete, non-continuous machine learning models such as GBDT.

Paper analysis

6 questions; open one to read the full answer

  1. What problem does this paper attempt to solve?

    The authors study hard-label black-box attacks: when only the top-1 class can be obtained by querying, how to generate adversarial examples with a small number of queries.

    Core problem: how to efficiently generate adversarial examples in a black-box setting where only hard-label decisions (top-1 class) can be obtained through queries.

    • Problem scenario: the authors believe that many real systems expose neither model parameters nor probability outputs, giving only the final predicted class; white-box attacks and score-based black-box attacks that rely on softmax outputs are both inapplicable.
    • Shortcomings of existing methods: the authors state that directly transferring white-box attacks such as C&W and PGD requires minimizing a discontinuous step function, which is essentially combinatorial optimization and cannot be solved with gradient methods; the only prior method, Decision-attack (Boundary Attack), is based on random walks along the boundary, requires a large number of queries, and lacks a convergence guarantee.
    • Core observation: the distance g(θ) along some direction θ to the decision boundary is a real-valued and usually continuous function; even if the classifier itself is discontinuous (e.g., GBDT), g(θ) remains continuous (Figure 1, Figure 3), so zeroth-order optimization can be used.
    • Proposed in the paper: Opt-attack—rewriting the attack as a real-valued optimization problem of minimizing g(θ), evaluating the function value with binary search through queries, then solving with RGF zeroth-order optimization, with a convergence rate guarantee; the authors state that this is the first attack with a convergence rate guarantee in the hard-label black-box setting.
    • Threat model:
      • Attacker's goal: generate adversarial examples that are close to the original sample x0 but are misclassified by the model (untargeted) or classified as a specified class t (targeted).
      • Attacker's knowledge: hard-label black-box—the model is not exposed, and the attacker can only obtain the corresponding hard-label decision through queries, with no probability output.
      • Attacker's capability: query the model to probe the predicted class corresponding to an input.
      • Victim systems: CNN image classification models (MNIST, CIFAR-10, ImageNet) and GBDT (HIGGS, MNIST).
  2. What related research exists?

    Related work is divided into three groups: white-box attacks, score-based black-box attacks, and the only hard-label method, Decision-attack.

    White-box attacks

    • C&W attack (Carlini & Wagner, 2017) and EAD (Chen et al., 2018): formulate the attack as the optimization problem argmin Dis(x,x0) + c·L(Z(x)) and solve it with gradient methods; this paper follows their loss function form and uses C&W as a white-box reference.
    • PGD (Madry et al., 2018) and FGSM (Goodfellow et al., 2014): formulate the attack as constrained optimization solved by projected gradient descent, with FGSM being a special case of single-step PGD; DeepFool (Moosavi-Dezfooli et al., 2016) solves a similar optimization problem.

    Score-based black-box attacks

    • ZOO (Chen et al., 2017): under the setting where softmax outputs can be queried, reconstructs the loss function and directly minimizes it with zeroth-order optimization; the paper notes that the score-based setting can obtain probability outputs, which is more information than the hard-label setting in this paper.
    • AutoZoom (Tu et al., 2018): uses adaptive stochastic gradient estimation and an autoencoder for acceleration, reducing the query complexity of ZOO.
    • Ilyas et al. (2017): uses an evolutionary algorithm to solve score-based attacks, and states that their method can also be used in the hard-label setting.

    Transfer attacks

    • Papernot et al. (2017), Bhagoji et al. (2017): train substitute models to imitate the target model and then perform white-box attacks; the paper cites others' conclusions that attacking substitute models usually brings larger perturbations and lower success rates.

    Hard-label black-box attacks and baselines

    • Decision-based attack (Brendel et al., 2017): based on boundary random walks; the paper states that it is the only prior hard-label black-box attack, and that it can find adversarial examples with perturbations comparable to white-box attacks, but its search time is exponential, it requires a large number of queries, and it has no convergence guarantee. This paper's experiments use it as a baseline (using the authors' implementation in Foolbox and default parameters), with benchmarks on MNIST, CIFAR-10, and ImageNet-1000, and additionally uses the C&W white-box attack as a reference.

    The authors position this paper as: rewriting the hard-label attack as a continuous real-valued optimization problem, thereby using fewer queries than Decision-attack, and being what the authors call the first attack under this setting with a convergence rate guarantee.

  3. How does the paper address this problem?

    Rewrite the attack as continuous optimization of the distance to the boundary along a direction, g(θ), evaluate g with binary search, and then solve with RGF zeroth-order optimization.

    Overall idea: instead of directly searching for adversarial examples, search for a direction θ and minimize the distance g(θ) along that direction to the decision boundary, turning the combinatorial problem into a usually continuous real-valued optimization problem, Opt-attack.

    Problem setup and rewriting

    • Goal: given a classification model f and a sample x0, find x such that x is close to x0 and f(x) ≠ f(x0) (untargeted) or f(x) = t (targeted).
    • Core definition: for untargeted attacks, g(θ) = argminλ>0 { f(x0 + λ θ/(|θ|)) ≠ y0 }, i.e., the distance along direction θ from x0 to the nearest adversarial example (decision boundary); for targeted attacks the condition is changed to the prediction equaling the target class t. When image inputs are bounded, upper and lower bounds are added.
    • Optimization problem: min_θ g(θ), and the final adversarial example is x* = x0 + g(θ)·θ/‖θ*‖. The authors state that g(θ) maps a direction to a real-valued distance and is usually continuous—even if f itself is discontinuous (e.g., GBDT, neural networks), g(θ) remains continuous (Figure 1d, Figure 3c/3d), so zeroth-order methods can be used for optimization.

    Evaluating g(θ) with queries (Algorithm 1)

    • Initialization: perform a fine-grained search over normalized θ, querying x0 + αθ, x0 + 2αθ, … point by point until the prediction changes, then use binary search within that interval to locate the boundary; when taking the direction of a sample from another class, the first stage has an upper bound.
    • Local evaluation: when the known solution is close to the previous value v, first increase or decrease v by a ratio α = 0.01 to find an interval containing the boundary, then binary search to within the stopping tolerance ε, and return an approximation of g.

    Zeroth-order optimization (Algorithm 2)

    • Gradient estimation: use the Randomized Gradient-Free (RGF) method, ĝ = (g(θ + β u) − g(θ))/β · u, where u is a zero-mean Gaussian random vector and β is the smoothing parameter (β = 0.005 in all experiments).
    • Implementation details: in high-dimensional problems the estimation noise is large, so q = 20 Gaussian vectors are sampled each time and averaged; the step size is not the fixed value suggested by theory but uses backtracking line-search, which the authors state increases the number of queries but is more stable and avoids tuning the step size. The authors state that in practice RGF outperforms zeroth-order coordinate descent.

    Theoretical analysis

    • Convergence guarantee (Theorem 1): if g has a Lipschitz continuous gradient, the function value evaluation error is controlled at ε ~ O(βδ²) and β ≤ O(δ/(d·L1(g))), then the number of iterations required to reach an average squared gradient norm of at most δ² is at most O(d/δ²); binary search can reach the required precision within O(log δ) steps.
    • Non-smooth case: the authors state that with the same idea, when g(θ) is non-smooth but Lipschitz continuous, a complexity of O(d²/δ³) can be achieved. Proof details are in the appendix.
  4. What experiments did the paper conduct?

    Compared with Decision-attack on CNNs for three datasets and GBDT for two datasets, Opt-attack uses fewer queries and has smaller or similar perturbations.

    Experimental setup

    • Models evaluated: MNIST and CIFAR-10 use the same CNN (4 convolutional layers, 2 max-pooling, 2 fully connected layers, parameters from the C&W paper, accuracy 99.5% and 82.5% respectively); ImageNet-1000 uses a torchvision pretrained ResNet-50 (top-1 accuracy 76.15%); GBDT is trained with LightGBM (HIGGS AUC 0.8457, MNIST accuracy 98.09%).
    • Datasets: MNIST, CIFAR-10, ImageNet-1000 (CNN attacks); HIGGS (binary classification) and MNIST (GBDT attacks).
    • Baselines: Decision-based attack (using the authors' implementation in Foolbox with default parameters); C&W white-box attack is for reference only (binary search over parameter c per image).
    • Metrics: average L2 perturbation and average number of queries for black-box attacks; the success rate of all three attacks is 100%.
    • Sample size: for each setting, N = 100 images are randomly sampled from the validation set; for targeted attacks, the target class is t = (i+1) mod 10 following the setting of Brendel et al.
    • Number of repetitions: not reported in the paper.

    Main results

    Untargeted attacks (according to Table 1, three rows per method correspond to different stopping conditions):

    Swipe horizontally to read the table

    MethodMNIST Avg L2 / queriesCIFAR-10 Avg L2 / queriesImageNet Avg L2 / queries
    Decision-attack1.1222 / 60,293; 1.1087 / 143,3570.1575 / 123,879; 0.1501 / 220,1445.9791 / 123,407; 3.7725 / 260,797
    Opt-attack1.188 / 22,940; 1.049 / 51,683; 1.011 / 126,4860.2050 / 40,941; 0.1625 / 77,327; 0.1451 / 133,6626.9796 / 71,100; 4.7100 / 127,086; 3.1120 / 237,342
    C&W (white-box reference)0.9921 / -0.1012 / -1.9365 / -
    • Authors' interpretation: Opt-attack consistently achieves smaller perturbations with fewer queries; the authors state that on MNIST the number of queries is reduced by 3–4 times, and that Decision-attack converges to worse solutions on all three datasets.
    • Gap to white-box: on MNIST and CIFAR the black-box attack perturbations are slightly larger than C&W, which the authors consider reasonable; on ImageNet, because the number of queries is limited, the black-box attack perturbations are noticeably larger than C&W, and the authors state that increasing the number of queries can narrow the gap (Figure 4 gives log perturbation versus number of queries curves for 6 images, solid lines for Decision-attack and dashed lines for Opt-attack).

    Targeted attacks

    • Results (Table 2): on MNIST, the three settings for Opt-attack are 1.8522 / 46,248, 1.7744 / 57,741, 1.7114 / 73,293, and for Decision-attack 2.3158 / 30,103, 2.0052 / 58,508, 1.8668 / 192,018; C&W is 1.4178. On CIFAR-10, Opt-attack is 0.2758 / 61,869, 0.2369 / 141,437, 0.2300 / 186,753, and Decision-attack is 0.2850 / 55,552, 0.2213 / 140,572, 0.2122 / 316,791; C&W is 0.1901.
    • Authors' interpretation: on MNIST the authors state that Opt-attack uses more than 4 times fewer queries than Decision-attack and converges to better solutions; on CIFAR, in the first 60,000 queries the two are similar in efficiency, but Opt-attack converges to a slightly worse solution.
    • Example quality: Figure 5 gives a comparison of targeted attack examples from the same starting point, and the authors state that Opt-attack achieves better results with fewer queries.

    Attacking GBDT

    • Setup: untargeted attacks on GBDT trained with LightGBM, on the HIGGS and MNIST datasets.
    • Results (Table 3): on HIGGS the three settings are 0.3458 / 4,229, 0.2179 / 11,139, 0.1704 / 29,598; on MNIST they are 0.6113 / 5,125, 0.5576 / 11,858, 0.5505 / 32,230.
    • Authors' interpretation: about 30K queries suffice to obtain small perturbations on both datasets, and the authors state that this is the first to reveal the vulnerability of GBDT models—even with good interpretability and accuracy similar to CNN, GBDT remains vulnerable under Opt-attack, and they propose tree model robustness as a future direction.

    Other ablations and analyses

    • Stopping conditions: changing the stopping condition yields different trade-offs between number of queries and perturbation (multiple rows in Table 1–3).
    • Smoothing parameter: β = 0.005 fixed in all experiments (Section 3.2).
    • Number of samples for gradient estimation: q = 20 Gaussian vectors averaged, fixed in all experiments (Section 3.2).
    • Solver choice: the authors state that in practice RGF outperforms zeroth-order coordinate descent, without giving numbers.
  5. What are some points that can be further explored?

    The authors propose tree model robustness as a future direction; the experiments cover three CNNs and two GBDTs, with N=100 per setting.

    Limitations and future directions noted by the authors

    • Perturbations on ImageNet are relatively large: The authors state that because the number of queries was limited, the perturbations of the black-box attack on ImageNet are much worse than those of the C&W white-box attack, and increasing the number of queries can narrow the gap (Section 4.1.1).
    • Targeted attack on CIFAR converges slightly worse: The authors state that on CIFAR, Opt-attack and Decision-attack have similar efficiency in the first 60,000 queries, but Opt-attack converges to a slightly worse solution (Section 4.1.2).
    • Tree model robustness: The authors propose that the robustness of tree models is an interesting future direction (Section 4.1.3).
    • The paper has no dedicated Limitations section; the above are the shortcomings and directions written by the authors in the experimental discussion and conclusion.

    Scope of experiments

    • Models tested: one CNN with the same architecture each for MNIST/CIFAR, one ResNet-50 for ImageNet, three CNNs in total; GBDT is one LightGBM model each on HIGGS and MNIST.
    • Attack types: untargeted and targeted attacks were done on CNNs, and only untargeted attacks were done on GBDT.
    • Sample size: N = 100 validation set images were randomly sampled for each setting, and the success rate of all three attacks was 100%.
    • Baselines: the only black-box baseline is Decision-attack; the C&W white-box attack is used only as a reference.
    • Information not reported: the paper does not report the number of repetitions or running time; query counts are reported only as averages, without variance or distribution.
  6. Summarize the main content of the paper

    Opt-attack turns the hard-label black-box attack into a continuous optimization problem, and the authors state that it uses 3–4 times fewer queries than Decision-attack and has a convergence guarantee.

    A paper on hard-label black-box adversarial attacks: the attacker can only obtain the model's top-1 predicted class through queries, with no probability outputs and no model internal information.

    • Problem to solve: Under this setting, the white-box attack objective becomes a discontinuous step function and cannot be optimized by gradients; the only prior method, Decision-attack, requires a large number of queries and has no convergence guarantee.
    • Method highlights: Define g(θ) as the distance to the decision boundary along direction θ, and rewrite the attack as the real-valued optimization min_θ g(θ)—even if the classifier is discontinuous (e.g., GBDT), g(θ) is usually still continuous; use fine-grained search plus binary search to evaluate g via hard-label queries, then solve with RGF zeroth-order optimization (β = 0.005, q = 20, backtracking line-search); Theorem 1 gives an iteration complexity of O(d/δ²), which the authors state is the first attack under this setting with a convergence rate guarantee.
    • Main results: For untargeted attacks on MNIST, Opt-attack reaches Avg L2 1.188 with 22,940 queries, and Decision-attack reaches 1.1222 with 60,293 queries (Table 1); the authors state that on MNIST the number of queries is reduced by 3–4 times, and that on all three datasets Decision-attack converges to worse solutions; on ImageNet, due to the query limit, the perturbations are noticeably larger than the C&W white-box reference; on CIFAR, the targeted attack converges slightly worse than Decision-attack.
    • GBDT results: On LightGBM models for HIGGS and MNIST, small-perturbation adversarial examples are found within about 30K queries (e.g., HIGGS 0.1704 / 29,598 queries), which the authors state reveals the vulnerability of GBDT for the first time.
    • Authors' conclusion: The optimization framework is general, query-efficient, has theoretical convergence guarantees, and can be used for discrete discontinuous models beyond neural networks; the authors propose tree model robustness as a future direction.

Related papers

Show 3 more papers
Read originalarxiv.org