Designing Black-Box Adversarial Examples Using Gradient-Free Optimization and Operator Splitting Method

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

   To address the high query complexity of black-box adversarial attacks and the limited distortion metrics and feedback settings, the authors propose a general attack framework based on ADMM.

   Core question: how to generate adversarial examples in the black-box setting while supporting multiple distortion metrics and feedback types, and reducing query complexity.

   • Scenario and motivation: the authors note that DNNs perform well on average but can be misled by small perturbations in adversarial cases, involving high-reliability scenarios such as face recognition, autonomous driving, and malware detection; studying adversarial examples is the basis for developing defenses.
   • Shortcomings of existing methods (as stated in the paper): white-box attacks assume full access to the target model and are not applicable to real black-box systems; surrogate-based transfer attacks have low success rates when the surrogate is inaccurate (training a qualified surrogate is difficult in data-intensive domains such as ImageNet); the ZOO attack based on zeroth-order gradient estimation requires many queries per iteration and is uneconomical in query-limited scenarios.
   • Core approach: formulate the attack as an optimization problem with a distortion term, use the operator-splitting method ADMM to decouple the black-box loss from the distortion term, then respectively apply zeroth-order optimization (RGE) and Bayesian optimization (BO), yielding two gradient-free attacks, ZO-ADMM and BO-ADMM.
   • Threat model:
     • Goal: misclassify a correctly classified image x0, after perturbation, into the target class t (targeted; ImageNet also evaluates untargeted).
     • Knowledge: the target model's internal structure and configuration are unknown (black-box).
     • Capability: can only submit inputs and receive outputs; the score-based setting can obtain soft labels for all classes, while the decision-based setting can only obtain hard labels.
     • Victim system and constraints: image classification DNN; perturbation per pixel does not exceed ε (kδk∞ ≤ ε), with pixels normalized to [0,1].

   Collapse this answer

2. 02What related research exists?

   Related work falls into three categories: surrogate transfer attacks, gradient-estimation attacks, and other black-box attacks; the paper uses ZOO, boundary, query-limited, BanditsTD, etc. as baselines.

   Surrogate (transfer) attacks

   • Papernot et al. [33]: train a surrogate DNN on data labeled by the target model, then apply a white-box attack to it. The paper notes that such methods depend on surrogate quality and have low success rates in data-intensive domains such as ImageNet.

   Gradient-estimation-based attacks

   • ZOO [10]: uses zeroth-order optimization for coordinate-level gradient estimation, followed by a C&W attack; the paper notes that it requires many queries per iteration and is computationally expensive.
   • Narodytska & Kasiviswanathan [31]: uses greedy local search to estimate the gradient, perturbing only a few input components per step; the paper notes that it does not explicitly minimize distortion, so the noise is more easily noticed.
   • Ilyas et al. [20]: defines three settings—query-limited, partial-information, label-only—based on NES and Monte Carlo approximation; the paper notes that it only constrains l∞ and does not minimize some l_p norm.
   • BanditsTD (Ilyas et al. [21]): builds on [20] by using temporal priors and data priors to improve query efficiency.

   Other black-box attacks

   • Boundary attack [7]: decision-based, starting from a large adversarial perturbation and randomly walking along the boundary to reduce distortion; the paper notes that it requires many queries and has no convergence guarantee.
   • Cheng et al. [11]: formulates the hard-label black-box attack as a continuous real-valued optimization problem and solves it with a zeroth-order algorithm; Hogan & Kailkhura [18]: universal (image-independent) perturbations in the hard-label setting.

   Baselines and benchmarks: experiments compare C&W white-box attack [8] (reference), transfer attack [33], ZOO [10], boundary attack [7], query-limited and label-only [20], BanditsTD [21], and additionally compare AutoZoom [42] in the appendix; datasets are MNIST, CIFAR-10, ImageNet.

   The authors position this paper as: using ADMM to uniformly support multiple l_p distortion metrics and both score-based/decision-based feedback settings, while reducing query complexity via RGE and BO.

   Collapse this answer

3. 03How does the paper address this problem?

   ADMM is used to split the attack problem into a distortion-term z-step (closed-form solution) and an attack-loss δ-step (gradient-free solving), yielding ZO-ADMM and BO-ADMM.

   Overall approach: formulate adversarial example generation as min_δ f(x₀+δ,t)+γ D(δ), s.t. (x₀+δ)∈[0,1]^d, |δ|_∞≤ϵ (f is the misclassification loss, D is the distortion function), introduce an auxiliary variable z and solve by ADMM splitting, with the δ-step handled by gradient-free methods for the black-box loss.

   Problem Formulation and Loss Functions

   • General form: D(δ) defaults to kδk22 (the authors state this is inspired by the C&W l2 attack), but other l_p norms can also be used; only targeted attacks are focused on, and the authors state untargeted can be implemented similarly.
   • score-based loss: a C&W-style loss based on log probabilities (Eq. 2), with κ usually set to 0; log is used to weaken the influence of the dominant class.
   • decision-based loss: f ∈ {−1, 1}, with f = −1 meaning attack success (Eq. 3); this loss is non-smooth with discrete outputs, and the authors state that combinatorial optimization methods are almost ineffective.

   ADMM Splitting and z-step

   • Splitting scheme: introduce z and add an indicator function I(z) to handle the [0,1] and l∞ constraints, construct the augmented Lagrangian, and alternately update z, δ and the multiplier u (Eq. 8–10).
   • z-step closed-form solution: when D(z) = kzk22, it decomposes element-wise and has a closed-form solution (Eq. 13).
   • Multi-norm generalization: when D(z) is kzk0, kzk1, or kzk1 + β/2·kzk22, the z-step requires only minor modifications (proximal operator, full derivation in Appendix A); the authors state this is difficult for other black-box attacks that are usually customized for a single norm.

   Gradient-free Solving of the δ-step

   • ZO-ADMM (RGE): uses forward-difference stochastic gradient estimation (Eq. 15), with Q random directions and smoothing parameter ν; query complexity O(Q) (O(dQ) for coordinate-level estimation), and forward differences require Q+1 queries, fewer than NES central differences' 2Q. Further, linearized ADMM is used: f is replaced by a first-order Taylor expansion plus Bregman regularization, yielding a closed-form solution (Eq. 17) requiring only one gradient estimation step each time; the authors cite [27] as showing that linearized ADMM has a convergence proof for non-convex problems.
   • BO-ADMM: models the δ-step objective as a Gaussian process (ARD Matérn 5/2 kernel), selects points with the expected improvement (EI) acquisition function, then uses projected gradient descent to ensure feasibility (Eq. 24–25).

   Smoothing and Initialization for decision-based

   • Smoothed loss: random smoothing is applied to the discrete loss (Eq. 26), and in practice a Monte Carlo approximation is used with N uniform samples within the unit ball (Eq. 27).
   • Initialization: δ is initialized so that the perturbed image belongs to the target class, which the authors state saves queries compared with arbitrary image initialization.

   Key Hyperparameters (Section 6.1)

   • Q = 20 (RGE), N = 10 (smoothed loss); ν = 0.5 (all three datasets).
   • ρ = 10, γ = 1 (MNIST); ρ = 2000, γ = 10 (CIFAR-10); ρ = 1000, γ = 1 (ImageNet).
   • ε = 1 (MNIST/CIFAR-10, which the authors state is for a fair comparison with the pure l2 framework ZOO), ε = 0.05 (ImageNet); µ = 1 / 0.1 / 0.01 (MNIST/CIFAR-10/ImageNet).

   Collapse this answer

4. 04What experiments did the paper conduct?

   Comparing multiple black-box attacks on MNIST, CIFAR-10, and ImageNet, the authors state that ZO-ADMM reduces query counts by about 94%–99% relative to ZOO while achieving similar ASR.

   Experimental Setup

   • Models tested: one self-trained CNN each for MNIST and CIFAR-10 (4 conv layers, 2 max pooling, 2 fully connected, softmax), with test accuracy 99.5% and 80% respectively; ImageNet uses pretrained Inception v3 (top-5 accuracy 96%).
   • Datasets and sample sizes: 200 correctly classified images each for MNIST/CIFAR-10, each attacked toward the other 9 classes (targeted), 1800 attacks per method; 100 correctly classified images for ImageNet, with 9/1000 target classes randomly selected per image for targeted attacks, plus untargeted attacks.
   • Baselines: C&W white-box attack (reference), transfer attack (via C&W, κ = 20), ZOO (ZOO-Adam default parameters), boundary attack, query-limited and label-only (ImageNet), BanditsTD (ImageNet); the appendix compares AutoZoom and boundary.
   • Metrics: ASR, l1/l2/l∞ distortion, query count on initial success, and the query reduction ratio relative to ZOO; decision-based attacks start from a target-class image and thus succeed initially, and their "query count on initial success" refers to the query count at which the reported l2 distortion is reached (Table 1 footnote a).
   • Success criterion: the perturbed image is classified into the target class (targeted) or a non-original class (untargeted); the paper does not report the number of repetitions or statistical significance tests.
   • Hardware: NVIDIA GTX 1080 TI.

   Main Results

   According to Table 1 (MNIST/CIFAR-10, score-based targeted attacks):

   Swipe horizontally to read the table

   Dataset	Method	ASR	l2 distortion	Query count on initial success	Query reduction ratio
   MNIST	C&W (white-box reference)	100%	1.962	-	-
   MNIST	Transfer (via C&W)	30.6%	4.545	-	-
   MNIST	ZOO	98.8%	1.977	12,161	0.0%
   MNIST	score-based ZO-ADMM	98.3%	1.975	493.6	95.9%
   MNIST	score-based BO-ADMM	87%	7.7	52.1	99.6%
   CIFAR-10	ZOO	97.6%	0.361	9982	0.0%
   CIFAR-10	score-based ZO-ADMM	98.7%	0.417	421	95.7%
   CIFAR-10	score-based BO-ADMM	84.1%	5.29	46.3	99.6%

   • The authors state that ZO-ADMM's ASR and l2 distortion are close to ZOO and the C&W white-box attack, and that the query reduction comes from Eq. 17 requiring only one gradient estimation step.
   • The authors state that BO-ADMM uses fewer queries but controls the perturbation imprecisely, with larger l_p distortion; Appendix C states that BO-ZO-ADMM (BO initialization + ZO refinement) requires 380 queries on MNIST and 320 queries on CIFAR-10 to reach the same l2 distortion as ZO-ADMM.
   • decision-based (Table 1): ZO-ADMM achieves 100% ASR on both MNIST/CIFAR-10, with query counts of 7,603 / 6,213 to reach the reported l2 distortion, about 60% fewer than boundary attack (25,328 / 16,720); the authors state that decision-based's slightly larger l2 distortion than score-based is expected.

   ImageNet Experiments (Table 2)

   • score-based untargeted: ZO-ADMM ASR 98%, query count on initial success 891 (94.3% reduction relative to ZOO); ZOO 90% / 15,631; query-limited 100% / 4785; BanditsTD 94% / 1259.
   • score-based targeted: ZO-ADMM ASR 97%, queries 16,058 (99.2% reduction); ZOO 78% / 2.11×10^6; query-limited 98% / 34,128; BanditsTD does not report targeted results (Table 2 footnote a: it mainly explores untargeted attacks).
   • decision-based: ZO-ADMM untargeted ASR 100%, targeted 94%; label-only targeted ASR 92%, queries 1.89×10^6, ZO-ADMM targeted 1.52×10^6 (footnote c: decision-based's "query count on initial success" refers to the query count at which the same l2 distortion as ZOO's initial success is reached).

   Convergence and Multiple Norms

   • Convergence (Figure 2): the authors state that score-based ZO-ADMM rises from zero distortion to success and then lowers l2, and decision-based starts from a target-class image with l2 decreasing as queries increase; the authors state that success is reached within a few hundred queries on MNIST/CIFAR-10 and tens of thousands of queries on ImageNet. The figure shows 5 curves (three score-based, two decision-based), with the horizontal axis up to 3×10^4 queries and the vertical axis l2 distortion 0–15, all showing a downward trend.
   • Multiple l_p norms (Table 3, MNIST score-based): when ZO-ADMM minimizes l0/l1/l2 respectively, ASR is 100% in all cases; the l0 version has l0 distortion 18.5 and l2 9.72; the l1 version has l1 10.5 and l2 2.71; the l2 version has l1 22.09 and l2 1.93. The authors state that the method can adapt to different l_p norms.

   Other Ablations and Analyses

   • AutoZoom comparison (Appendix D, Table A1, 500 images, equal l2 distortion): ZO-ADMM query counts are 562 / 492 / 16,390 (MNIST/CIFAR-10/ImageNet), AutoZoom 1821 / 1639 / 43,547; ASR is 100% / 99% / 99% and 100% / 99.2% / 98.3% respectively. The authors note that AutoZoom generates perturbations in a low-dimensional latent space, with lower computational cost.
   • ImageNet supplementary comparison (Table A2): score-based ZO-ADMM queries 1.6×10^5 (query-limited 3.4×10^5); decision-based ZO-ADMM ASR 93%, queries 1.5×10^6 (boundary 85%, 2.2×10^6).
   • Appendix E (Figure A1/A2): gives convergence curves of l2 distortion versus query count and ADMM iteration count, and compares convergence with the boundary method; specific values are not annotated on the figures.

   Collapse this answer

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

   The paper has no dedicated subsection discussing limitations; the experiments cover three image classification datasets and three classification models, and some settings are not reported in the paper.

   Limitations and Future Directions Noted by the Authors

   • The paper does not specifically discuss limitations (no Limitations/Discussion/Future Work section).
   • Section 6.1: the authors state that BO-ADMM controls the perturbation imprecisely and requires a larger perturbation to mislead the model, hence larger l_p distortion.
   • Section 6.1: the authors state that BO-ADMM has limitations, and that combining BO with ZO-ADMM (BO-ZO-ADMM, Appendix C) yields a more query-efficient attack.
   • Section 2.1 (commentary on transfer attacks, not a limitation of this paper): the authors state that transfer attacks have low success rates when the surrogate is inaccurate, and that training a qualified surrogate is difficult in data-intensive domains such as ImageNet.

   Scope of Experimental Coverage

   • 3 models tested in total: MNIST self-trained CNN, CIFAR-10 self-trained CNN, ImageNet pretrained Inception v3 (Section 6).
   • Datasets are MNIST, CIFAR-10, ImageNet; 1800 targeted attacks per method on MNIST/CIFAR-10, 100 images on ImageNet (9 target classes per image for targeted, plus untargeted) (Section 6.1/6.2).
   • Feedback settings cover both score-based and decision-based; distortion metrics cover l0, l1, l2 and the l∞ constraint (Table 3, Appendix A).
   • Comparison methods cover transfer, ZOO, boundary, query-limited, label-only, BanditsTD, with AutoZoom additionally compared in the appendix (Table 1, 2, A1, A2).
   • The paper does not report runtime per attack, number of repeated experiments, or statistical significance tests; transfer attack is not done on ImageNet (Section 6.2: the authors state that it is difficult to scale to ImageNet due to surrogate training).

   Collapse this answer

6. 06Summarize the main content of the paper

   The authors propose an ADMM black-box adversarial attack framework (ZO-ADMM/BO-ADMM), claiming that on three image classification datasets it reduces query counts by about 94%–99% with ASR close to ZOO.

   A paper on black-box adversarial attack methods: addressing the problems of existing black-box attacks having a single distortion metric, restricted feedback settings, and high query complexity, it formulates the attack as an optimization problem with a distortion term and solves it using ADMM splitting.

   • Method: the z-step handles distortion and box constraints; l2 has a closed-form solution, and l0/l1/l1+l2 require only minor modifications via proximal operators; the δ-step uses stochastic gradient estimation (ZO-ADMM, solved with one step of linearized ADMM) or Bayesian optimization (BO-ADMM); the decision-based setting uses a Monte Carlo smoothed loss and initializes from target-class images.
   • MNIST/CIFAR-10 (Table 1): the ASR of score-based ZO-ADMM is 98.3% / 98.7% (ZOO is 98.8% / 97.6%), and the number of queries to first success decreases by 95.9% / 95.7% relative to ZOO; decision-based ZO-ADMM achieves an ASR of 100% on both, with about 60% fewer queries than boundary attack.
   • ImageNet (Table 2): score-based ZO-ADMM achieves 98% untargeted ASR and 97% targeted ASR, with query counts decreasing by 94.3% and 99.2% relative to ZOO, respectively; decision-based targeted ASR is 94%, with fewer queries than label-only.
   • BO-ADMM: fewer queries (MNIST 52.1, CIFAR-10 46.3) but lower ASR (87% / 84.1%) and greater distortion; Appendix C states that BO-ZO-ADMM, when combined, requires only 380 / 320 queries to reach the same l2 distortion as ZO-ADMM.
   • Authors' conclusion: the framework uniformly supports multiple l_p distortion metrics and score-based/decision-based settings, and the authors state that it is more query-efficient than existing black-box attacks without sacrificing ASR or distortion.

   Collapse this answer

Related papers