Paper deep dive
Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion
Ali Javeri, Javad Hezareh, Radin Shahdaei, AmirMahdi Sadeghzadeh
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Score-based black-box adversarial attacks pose a serious threat to deployed machine learning systems by exploiting repeated model queries to craft adversarial examples, requiring neither access to model parameters nor architecture. Existing defenses predominantly rely on stochastic output perturbations, which fail to prevent determined attackers from recovering stable gradient estimates by increasing query budgets or averaging over randomness. In this work, we propose the Gradient Confusion Defense (GCD), a retraining-free, deterministic test-time wrapper that actively shapes the probability vector returned to querying adversaries. By solving a constrained optimization problem grounded in the model's Jacobian, GCD aligns the exposed logit-gradient with a target confusion direction that is maximally misaligned with the true adversarial loss gradient---increasing the query complexity of attacks without sacrificing predictive utility or top-1 accuracy. We provide rigorous theoretical analysis demonstrating that GCD provably slows gradient-estimation-based attacks and induces systematic accept/reject errors in random search-based attacks, with the confusion effect amplifying as the fraction of defended queries increases. Extensive experiments on CIFAR-10 and ImageNet across multiple architectures (ResNet-18, ResNet-50, ViT-B/16) and four state-of-the-art attacks confirm these predictions: GCD achieves state-of-the-art robustness, while incurring zero clean accuracy degradation. %Crucially, unlike randomization-based defenses, GCD's deterministic structure provides resilience against adaptive attacks that exploit stochasticity, making it well-suited for security-critical deployment settings.
Tags
Links
- Source: https://arxiv.org/abs/2610.17382v1
- Canonical: https://arxiv.org/abs/2610.17382v1
Trouble viewing inline? Open PDF directly →
Full Text
97,119 characters extracted from source content.
Expand or collapse full text
Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion Ali Javeri Javad Hezareh Radin Shahdaei AmirMahdi Sadeghzadeh †thanks: Corresponding author Affiliation: Department of Computer Engineering, Sharif University of Technology Affiliation: Tehran, Iran Email: ali.javeri78@sharif.edu javad.hezareh@sharif.edu Email: radin.shahdaei01@sharif.edu sadeghzadeh@sharif.edu Abstract Score-based black-box adversarial attacks pose a serious threat to deployed machine learning systems by exploiting repeated model queries to craft adversarial examples, requiring neither access to model parameters nor architecture. Existing defenses predominantly rely on stochastic output perturbations, which fail to prevent determined attackers from recovering stable gradient estimates by increasing query budgets or averaging over randomness. In this work, we propose the Gradient Confusion Defense (GCD), a retraining-free, deterministic test-time wrapper that actively shapes the probability vector returned to querying adversaries. By solving a constrained optimization problem grounded in the model’s Jacobian, GCD aligns the exposed logit-gradient with a target confusion direction that is maximally misaligned with the true adversarial loss gradient—increasing the query complexity of attacks without sacrificing predictive utility or top-1 accuracy. We provide rigorous theoretical analysis demonstrating that GCD provably slows gradient-estimation-based attacks and induces systematic accept/reject errors in random search-based attacks, with the confusion effect amplifying as the fraction of defended queries increases. Extensive experiments on CIFAR-10 and ImageNet across multiple architectures (ResNet-18, ResNet-50, ViT-B/16) and four state-of-the-art attacks confirm these predictions: GCD achieves state-of-the-art robustness, while incurring zero clean accuracy degradation. Our code is available at: https://github.com/awlliom/GradientConfusion. Keywords Machine Learning, Adversarial Defense, Robustness, Adversarial Learning 1 Introduction Modern machine learning systems are often deployed via remote interfaces (e.g., cloud APIs and online services), where users interact with models only through query access. In this setting, standard white-box threat assumptions (Szegedy et al., 2014; Goodfellow et al., 2015; Moosavi-Dezfooli et al., 2016; Carlini and Wagner, 2017; Athalye et al., 2018a; Madry et al., 2018) are frequently unrealistic, yet query-based black-box attacks remain highly effective even without access to model parameters, gradients, or training data (Ilyas et al., 2018; Al-Dujaili and O’Reilly, 2020; Andriushchenko et al., 2020; Cheng et al., 2020; Guo et al., 2019; Ilyas et al., 2019; Vo et al., 2024; Reza et al., 2025; Chen and Gu, 2020; Chen et al., 2020; Reza et al., 2023). By adaptively probing the model and observing outputs, adversaries can craft adversarial examples under practical query budgets, making black-box robustness a core requirement for secure and trustworthy deployment. Query-based black-box attacks are commonly divided into decision-based attacks (Cheng et al., 2020; Chen and Gu, 2020; Chen et al., 2020; Reza et al., 2023), which rely only on predicted labels and search for the decision boundary, and score-based attacks (Andriushchenko et al., 2020; Al-Dujaili and O’Reilly, 2020; Guo et al., 2019; Ilyas et al., 2019; Vo et al., 2024), which use logits or class probabilities to estimate gradients via finite-difference or search-based strategies. In practice, score-based attacks are typically more query-efficient and achieve higher success rates, posing a serious risk to deployed classifiers that must return confidence scores. As a result, a large body of work (Qin et al., 2021; Xie et al., 2018; He et al., 2019; Chen et al., 2022; Aithal and Li, 2022; Dashtbani et al., 2026; Hung-Quang et al., 2024; Wang et al., 2021) has proposed defenses, most of which introduce randomness into model responses (Qin et al., 2021; Aithal and Li, 2022; Dashtbani et al., 2026; Hung-Quang et al., 2024). While such methods can increase variance or slow optimization, they do not explicitly control the gradient signal exposed through outputs, allowing attackers to average over randomness (Athalye et al., 2018b) or increase the query budget to recover stable estimates when meaningful scores must be preserved. In this work, we revisit black-box defense from a different perspective and ask: What gradient signal should a model expose to an adversary? Instead of relying on stochastic perturbations, we propose to actively manipulate the gradient information inferred from model outputs. Our goal is not merely to add noise, but to deliberately bias the gradient estimates or search directions that score-based attacks attempt to recover, steering them away from directions that reduce the classification margin. We study the problem of defending a fixed, pretrained target classifier against query-based black-box adversaries while preserving correct predictions and usable score outputs. We introduce a deterministic test-time response wrapper that modifies the returned probability vector without altering the classifier itself or its training procedure. The core idea is gradient confusion: we deliberately shape the output scores so that the induced adversarial loss gradient’s direction deviates from the true adversarial loss gradient that score-based attacks seek to estimate. Using the loss gradients and Jacobian of the model’s logits, we derive an analytic target direction that misaligns the attacker’s search direction or estimated gradient, thereby increasing the number of queries required for successful adversarial example generation. Building on a target confusion direction, we introduce the Gradient Confusion Defense (GCD), which formulates a constrained optimization problem over output probabilities to explicitly control the gradient signal exposed to score-based black-box attackers. GCD enforces three principled constraints at test time: exact preservation of the top-1 prediction to maintain clean accuracy, a bounded ℓ1 _1 distortion on the returned probability vector to preserve the utility of confidence scores, and alignment of the exposed logit-gradient with a target confusion direction rather than the true gradient. The main contributions of this work are threefold. • We propose the Gradient Confusion Defense (GCD), a practical, retraining-free test-time defense that explicitly controls the gradient signal exposed through model outputs in the score-based black-box threat model. • We theoretically analyze how GCD forces the adversary to issue more queries to generate a successful adversarial example using gradient estimation-based and search-based attacks. • Extensive experiments show that GCD substantially reduces attack success rates while preserving clean accuracy, and further validate our theoretical analysis and demonstrate the effectiveness of our defense against several state-of-the-art query-based and adaptive attacks. 2 Related Works Score-based query attacks. Query-based black-box adversarial attacks craft adversarial examples using only repeated queries to a deployed model, without access to parameters or gradients. These attacks are typically divided into score-based methods (Andriushchenko et al., 2020; Al-Dujaili and O’Reilly, 2020; Guo et al., 2019; Ilyas et al., 2019; Vo et al., 2024; Reza et al., 2025; Ilyas et al., 2018; Chen et al., 2017), which leverage logits or class probabilities, and decision-based methods (Cheng et al., 2020; Chen and Gu, 2020; Chen et al., 2020; Reza et al., 2023), which use only predicted labels and are often less query-efficient. Early score-based attacks estimated gradients via zero-order optimization and finite-difference style approximations (Chen et al., 2017; Ilyas et al., 2018; Ilyas et al., 2019), while later work emphasized search-based strategies that can be highly query-efficient (Andriushchenko et al., 2020; Al-Dujaili and O’Reilly, 2020). Bandit-TD (Ilyas et al., 2019) frames gradient estimation as a bandit optimization problem and exploits temporal correlation of successive gradients and spatial structure in images. SquareAttack (Andriushchenko et al., 2020) performs randomized search using localized square-shaped perturbations, accepting only loss-decreasing proposals, yielding strong practical query efficiency. BruSLeAttack (Vo et al., 2024) targets sparse (ℓ0 _0) perturbations by searching over a reduced set of pixel locations to replace with values from a fixed synthetic image, and uses a Bayesian strategy guided by historical pixel-manipulation outcomes to improve query efficiency. Black-box defenses. A foundational line of defense is adversarial training (AT) (Tramèr et al., 2018; Salman et al., 2019; Rice et al., 2020), which empirically improves robustness by training on adversarially perturbed samples. Extensions incorporate data augmentation (Rebuffi et al., 2021), denoising (Salman et al., 2020), and ensembling (Liu et al., 2018), but AT often remains costly and can reduce clean accuracy; moreover, many such defenses primarily target white-box threats and can be brittle under obfuscated-gradient effects (Athalye et al., 2018a). For query-based threats, defenses commonly aim to disrupt the attacker’s ability to recover stable gradients from outputs, typically via randomization or output/logit manipulation. A (Chen et al., 2022) explicitly optimizes returned logits to confound the attacker by wrapping the original loss with a surrogate that preserves similar degradation behavior while inducing opposite gradient slopes, thereby steering optimization toward incorrect directions. RLS (Dashtbani et al., 2026) randomizes the effective scale of logits by multiplying them with a random coefficient, which empirically degrades gradient estimation and slows attacks. Boundary defense (Aithal and Li, 2022) injects noise into the model’s output to hinder convergence, and RND (Qin et al., 2021) injects noise at the input level, both aiming to increase the query complexity required for successful attacks. 3 Preliminaries Let ⊆[0,1]dX [0,1]^d be the input space, and let [K]=1,…,K[K]=\1,…,K\ denote the label set. A classifier ℳ:→ΔKM:X→ ^K outputs a probability vector ℳ()=σ(())M(x)=σ(z(x)), where ()z(x) denotes the logits and σ is the softmax function. Here, ΔK=∈ℝK∣∑i=1 ^K=\p ^K _ip_i=1\ denotes the probability simplex. Let k∈[K]k∈[K] denote the true label of input x. For simplicity, we denote ^:=ℳ() y:=M(x). Attacks and perturbations. An adversarial example advx_adv for a sample x with corresponding label k is generated by adding a perturbation δ to x. Typically, the norm of the perturbation δ is bounded so as not to change the ground-truth label of x. Formally, an adversarial example is defined as adv=+x_adv=x+ δ, such that ∥adv−∥p≤R _adv-x _p≤ R, where R is the perturbation budget, and the classifier ℳM misclassifies advx_adv (untargeted attack: argmaxiℳ(adv)i≠k _iM(x_adv)_i≠ k) or predicts a target class t (targeted attack: argmaxiℳ(adv)i=t _iM(x_adv)_i=t). There are two strategies for generating adversarial examples in the black-box setting: transfer-based (Papernot et al., 2017) and query-based (Chen et al., 2017). In the query-based setting (our focus), the adversary can adaptively query the model up to a budget Q that bounds the number of query the adversary can perform. Each query returns either (i) a score or probability vector (score-based setting) or (i) only the predicted label (decision-based setting). We focus on score-based black-box attacks, as they are generally stronger than decision-based attacks and harder to defend (Ilyas et al., 2018). Query-based black-box attacks typically optimize an adversarial loss using only the model’s outputs. Adversarial Loss. To attack the black-box target classifier ℳ()M(x), the following adversarial loss function has been widely used in score-based attacks (Chen et al., 2017; Ilyas et al., 2018; Qin et al., 2021): f():=ℳ()i−ℳ()j,f(x):=M(x)_i-M(x)_j, (1) where i and j denote the indices of the largest and second-largest components of the probability vector ℳ()M(x), respectively. Decreasing f()f(x) encourages the top prediction (typically the correct label) to lose confidence relative to its strongest competitor. There are two common approaches for minimizing f()f(x): gradient estimation (Zero-Order Optimization) and random search. Gradient estimation (Zero-Order Optimization) The most prominent approach for generating adversarial examples is to update the input in the opposite direction of the gradient of the adversarial loss function with respect to the input, ∇f() _xf(x), so as to decrease the adversarial loss. Since the attacker cannot directly access the model’s parameters or the gradient ∇f() _xf(x), it instead estimates the gradient using only the model’s outputs. A gradient estimator that is widely used in score-based attacks (Ilyas et al., 2018; Nesterov and Spokoiny, 2017; Qin et al., 2021) is given by ∇^fμ():=1m∑i=1mf(+μi)−f()μi, ∇_xf_μ(x):= 1m _i=1^m f(x+ _i)-f(x)μ\,u_i, (2) where i∼(,)u_i (0,I) and μ>0μ>0 is a small smoothing parameter. In this setup, the adversary queries the model at points in a neighborhood around the input x. As a result, they effectively observe a Gaussian-smoothed version of the loss function, denoted by fμ()f_μ(x). The attacker then performs Projected Gradient Descent (PGD) steps based on ∇^fμ() ∇_xf_μ(x) while respecting the input perturbation constraint: t+1=ΠR(t−ηt∇^fμ(t)),x_t+1= _R\! (x_t- _t ∇_xf_μ(x_t) ), (3) where ηt _t is step size at iteration t, and Πξ _ξ denotes projection onto the ℓp _p-ball of radius R, i.e., ‖′−‖p≤R\|x -x\|_p≤ R. Each step of PGD requires one query to the target model. Increasing the number of steps required for PGD to converge increases the query complexity of the attack. Random-search. Random search is an iterative method for minimizing the adversarial loss function. Let μ>0μ>0 denote the step size (i.e., the perturbation magnitude used by the search rule). At iteration t, given the current iterate tx_t, the attacker samples a search direction t∼u_t from a predefined distribution (e.g., Gaussian directions or structured perturbations), and evaluates the candidate t+μtx_t+ _t. If this perturbation decreases the adversarial loss f(⋅)f(·) in (1), the attacker updates t+1←t+μtx_t+1 _t+ _t; otherwise, t+1←tx_t+1 _t. This type of random-search (hill-climbing) rule is commonly used in query-based black-box attacks (Guo et al., 2019; Andriushchenko et al., 2020; Ilyas et al., 2019). Using the adversarial loss f()f(x), the one-step improvement signal is defined as ht:=f(t+μt)−f(t).h_t:=f(x_t+ _t)-f(x_t). (4) If ht<0h_t<0, then moving along tu_t decreases the loss and is therefore considered a useful attack direction. Accordingly, the accepted update is given by t+1=Πξ(t+(ht<0)⋅μt),x_t+1= _ξ\! (x_t+I\! (h_t<0 )· _t ), (5) where (⋅)I(·) denotes the indicator function. 4 Gradient Confusion Defense (GCD) In score-based black-box attacks, the adversary minimizes the loss f()f(x) in (1) using only the model output ^∈ΔK y∈ ^K. Gradient Confusion Defense (GCD) disrupts this process by returning a modified output ~∈ΔK y∈ ^K instead of y, increasing the number of queries needed to succeed (potentially exceeding the budget Q). GCD constructs ~ y from ℳM and y while preserving utility by keeping ‖^−~‖1\| y- y\|_1 small and ensuring argmaxk(^k)=argmaxk(~k)argmax_k( y_k)=argmax_k( y_k). For analysis, we introduce a hypothetical model ℳ~ M with ~=ℳ~()=σ(~()) y= M(x)=σ( z(x)), and drop the dependence on x in notation. Since the adversary only sees the output of the defended target model by the gradient confusion method, their adversarial loss function transforms to: f~():=ℳ~()i−ℳ~()j, f(x):= M(x)_i- M(x)_j, (6) where i and j denote the indices of the largest and second-largest components of the probability vector ℳ~() M(x), respectively. The gradient confusion solves the following minimization problem to compute ~ y: argminy~⟨∇f(),∇f~()⟩, y \>\>\; _xf(x), _x f(x) , (7) s.t∥ .t \| ℳ()−ℳ~()∥1≤ξand~∈ΔK (x)- M(x)\|_1≤ξ y∈ ^K where ξ is the distortion budget. The GCD minimization problem addresses two objectives. (i) Confusion: Minimizing ⟨∇f(),∇f~()⟩ _xf(x), _x f(x) misaligns the adversary’s estimated gradient ∇f~() _x f(x) from the true gradient ∇f() _xf(x). This increases the query cost of gradient-estimation attacks and can mislead random-search attacks by flipping the sign of hth_t. Theorems 4.3 and 4.4 in Section 4.1 provide theoretical support, and Section 5 validates GCD empirically. (i) Utility: The constraint ‖ℳ()−ℳ~()‖1≤ξ||M(x)- M(x)||_1≤ξ (equivalently OPEN‖^−~‖1≤ξ)\| y- y\|_1≤ξ) keeps ~=ℳ~() y= M(x) close to ^=ℳ() y=M(x), preserving predictive performance. Section 4.2 details how we solve (7). 4.1 Theoretical Analysis In this section, we theoretically show that solving the optimization problem in (7) increases the model’s resistance to score-based black-box attacks. To incorporate the crafted loss function f~ f, we define a randomized defended objective: fdef():=λf()+(1−λ)f~(),λ∼Bernoulli(p),f_def(x):=λ f(x)+(1-λ) f(x), λ (p), (8) where λ is drawn independently for each query. This theoretical model allows us to formalize the effect of f~ f on the optimization problem faced by the adversary. Under mild assumptions, we show that using fdeff_def increases the number of steps required by gradient-estimation-based attacks and misleads search-based attacks. Consequently, it confuses the adversary and increases the number of queries required to craft an adversarial input. Moreover, we argue that setting p→0p→ 0 maximizes this confusion effect. Assumption 4.1. The loss functions f and f~ f are Lipschitz continuous with constants L0(f)L_0(f) and L0(f~)L_0( f), respectively. Assumption 4.2. The loss functions f and f~ f are smooth, meaning their gradients are Lipschitz continuous with constants L1(f)L_1(f) and L1(f~)L_1( f), respectively. 4.1.1 Gradient Estimation-Based Attacks Gradient estimation-based attacks approximate gradients using function evaluations (e.g., (2)) and update the input via projected gradient descent (e.g., (3)). Thus, the adversary applies (projected) gradient descent to minimize the adversarial loss. The number of queries performed by the adversary is denoted by T, which corresponds to the number of optimization steps. In theory, the adversary is considered to have succeeded in optimizing the adversarial loss function if the norm of its gradient is sufficiently small at the final iterate. Thus, to analyze the adversary’s optimization procedure, we need to bound the gradient norm. In our framework, using (8), the gradient estimator is driven by fdeff_def rather than f. Theorem 4.3. Suppose Assumption 4.1 holds. Consider zero-order optimization using the gradient estimator driven by fdeff_def, with smoothing parameter μ≤μ∗μ≤μ , for T iterations and constant step size ηt=η∗ _t=η . If, for all ∈ℝdx ^d, it holds that |f()−f~()|≤ϵ|f(x)- f(x)|≤ε, where ϵ>0ε>0 is a small constant, then the following bound holds: pT∑t=0T−1[‖∇fμ(t)‖2]+1−pT∑t=0T−1[⟨∇fμ(t),∇f~μ(t)⟩] pT _t=0^T-1E\! [\|∇ f_μ(x_t)\|^2 ]+ 1-pT _t=0^T-1E\! [ ∇ f_μ(x_t),∇ f_μ(x_t) ] (9) ≤4d3L0(f)5Rϵ′T(p+(1−p)L0(f~)2L0(f)2+2p(1−p)ϵ2ϵ′2). ≤ 4d^3L_0(f)^5Rε T (p+(1-p) L_0( f)^2L_0(f)^2+2p(1-p) ε^2ε 2 ). Here, R denotes the perturbation budget, ϵ′>0ε >0 is a small constant ensuring that fμf_μ is close to f, and the expectation is taken over the randomness of the optimization process up to iteration t. The detailed proof of Theorem 4.3 is provided in Appendix B. This theorem shows that incorporating the function f~ f into the optimization process can effectively perturb the optimization landscape and mislead the gradient estimates. In particular, by optimizing the confusion term ⟨∇fμ(t),∇f~μ(t)⟩ ∇ f_μ(x_t),∇ f_μ(x_t) , we can increase the overall bound and thereby improve robustness against gradient estimation attacks. Implications of Theorem 4.3. Let C(p)=4d3L0(f)5Rϵ′(p+(1−p)L0(f~)2L0(f)2+2p(1−p)ϵ2ϵ′2),C(p)= 4d^3L_0(f)^5Rε (p+(1-p) L_0( f)^2L_0(f)^2+2p(1-p) ε^2ε 2 ), be a constant depending on p and C(0)≠0C(0)≠ 0. Rearranging the bound in (9) as: 1T∑t=0T−1[‖∇fμ(t)‖2]≤C(p)pT 1T _t=0^T-1E\! [\|∇ f_μ(x_t)\|^2 ]≤ C(p)p T (10) −(1−p)p1T∑t=0T−1[⟨∇fμ(t),∇f~μ(t)⟩] - (1-p)p\, 1T _t=0^T-1E\! [ ∇ f_μ(x_t),∇ f_μ(x_t) ] For adversary to succeed in optimization, they need to minimize the right hand side of the inequality below a certain threshold by increasing T which is the number of optimization steps. Thus the defender can increase the second term in the right hand side by optimizing the confusion term ⟨∇fμ(t),∇f~μ(t)⟩ ∇ f_μ(x_t),∇ f_μ(x_t) to be negative and large in magnitude. In other words, the defender needs to make the gradients of the two functions to be misaligned. This would force the attacker to use a larger number of optimization steps (queries) T to achieve the desired threshold, thus increasing the attack cost. Choosing p→0p→ 0. We can further increase the bound in (10) by choosing p close to 00. When p→0p→ 0, the factor (1−p)/p(1-p)/p amplifies the contribution of the confusion term. Therefore, if the defender enforces ⟨∇fμ(t),∇f~μ(t)⟩ ∇ f_μ(x_t),∇ f_μ(x_t) to be negative and large in magnitude, the right-hand side of (10) can become arbitrarily large, effectively preventing the attacker from driving the average gradient norm below a fixed threshold within a limited number of iterations. This motivates choosing p=0p=0, i.e., relying entirely on f~ f in the optimization process. 4.1.2 Search-Based Attacks Random-search score-based attacks propose a direction tu_t and accept or reject it based on the sign of the one-step improvement signal (cf. (4) and (5)). Under our switching defense, each query is answered using the randomized objective fdeff_def, which independently returns either f or f~ f; thus the two evaluations used to form the improvement from tx_t to t+μtx_t+ _t may come from different objectives. Let hdef,th_def,t denote the improvement signal computed from the defender’s returned values. Because hdef,th_def,t can mix f and f~ f across the two points, sign(hdef,t) (h_def,t) can disagree with sign(ht) (h_t), causing the attacker to accept harmful steps or reject helpful ones. The next result lower bounds the probability of such one-step sign errors via (i) a geometric term depending on the angle between ∇f()∇ f(x) and ∇f~()∇ f(x), and (i) a smoothness correction scaling with μ (vanishing as μ→0μ→ 0 under Assumption 4.2). Theorem 4.4. Let Assumption 4.2 hold. Let d≥2d≥ 2 and ∼(,)u (0,I). Fix ∈ℝdx ^d and μ>0μ>0. Define the true and defended one-step signals h:=f(+μ)−f(),hdef:=fdef(+μ)−fdef().h:=f(x+ )-f(x), h_def:=f_def(x+ )-f_def(x). Then ℙ (sign(h)≠sign(hdef))≥ ( (h)≠ (h_ def) )≥ (11) (1−p)2[1πarccos(⟨∇f(),∇f~()⟩‖∇f()‖‖∇f~()‖) (1-p)^2 [ 1π ( ∇ f(x),∇ f(x) \|∇ f(x)\|\,\|∇ f(x)\| ) −μd2π(L1(f)‖∇f()‖+L1(f~)‖∇f~()‖)] - μ d 2π ( L_1(f)\|∇ f(x)\|+ L_1( f)\|∇ f(x)\| ) ] The proof of Theorem 4.4 is deferred to Appendix C. The event sign(h)≠sign(hdef) (h)≠ (h_def) is exactly a one-step decision error: relative to the true objective f, the attacker either rejects a truly improving direction or accepts a non-improving direction. Theorem 4.4 shows that this error probability is lower bounded by a misalignment term, proportional to the angle between ∇f()∇ f(x) and ∇f~()∇ f(x), up to a smoothness correction that decreases with the step size μ. Consequently, designing f~ f so that ∇f~()∇ f(x) is strongly misaligned with ∇f()∇ f(x) forces random search to waste queries, degrading progress under a fixed budget. A discussion of the Gaussian direction model (and its relationship to isotropic samplers used in practice) is provided in Appendix C.3 Conclusion. In summary, this subsection provides theoretical support that GCD increases the query cost of score-based black-box attacks. Theorem 4.3 shows that inducing a negative confusion term slows gradient-estimation-based optimization, while Theorem 4.4 shows that gradient misalignment causes accept/reject errors in search-based attacks. Together, these results justify designing f~ f to remain close to f in value while being misaligned in gradient. 4.2 Solving the GCD Minimization Problem GCD is a test-time output wrapper defense. It leaves the underlying target classifier unchanged, but modifies the probability vector returned to users. Concretely, for an input x, the target model produces logits ()∈ℝKz(x) ^K and probability vector ^=σ(())∈ΔK y=σ(z(x))∈ ^K. We suppose that GCD returns a perturbed distribution ~=σ(~())∈ΔK y=σ( z(x))∈ ^K. We first focus on minimizing ⟨∇f(),∇f~()⟩ _xf(x), _x f(x) , and then incorporate the constraints ‖ℳ()−ℳ~()‖1≤ξ\|M(x)- M(x)\|_1≤ξ and ~∈ΔK y∈ ^K. Based on the chain rule, we can write the inner product as follows: argmin~ y ⟨∇f(),∇f~()⟩ _xf(x), _x f(x) (12) =argmin~ = y ⟨∇()∇f(()),∇~()∇~f~(~())⟩. _xz(x)\, _zf(z(x)),\; _x z(x)\, _ z f( z(x)) . Solving (12) exactly is difficult because ~=σ(~()) y=σ( z(x)) appears inside the objective through f~ f and ∇f~ _x f, so the optimal ~ z determines the gradient terms needed to optimize for ~ z (a circular chicken-and-egg dependency). Therefore, due to the constraint ‖ℳ()−ℳ~()‖1≤ξ\|M(x)- M(x)\|_1≤ξ, we use a local approximation of ~() z(x) by ()z(x) (i.e., ()≈~()z(x)≈ z(x)), which yields ∇()≈∇~() _xz(x)≈ _x z(x). Letting J()=∇()J(x)= _xz(x), our objective then approximately becomes: argmin~ y ⟨∇f(),∇f~()⟩ _xf(x), _x f(x) (13) ≈argmin~ ≈\; y ⟨J()∇f(()),J()∇f~(())⟩. J(x)\, _zf(z(x)),\;J(x)\, _z f(z(x)) . Our experiments show this surrogate delivers consistent improvements against query-based black-box attacks. The only derivative that is a function of ~ y is ∇f~(()) _z f(z(x)). Let k()z_k(x) denote the k-th component of the perturbed logits vector ()z(x). For the k-th component of ∇f~(()) _z f(z(x)), we have ∂f~(())∂k()=~i(1−~i)−(−~j~i),if k=i,−~i~j−~j(1−~j),if k=j,−~i~k−(−~j~k),if k≠i,k≠j. ∂ f(z(x)) _k(x)= cases y_i(1- y_i)-(- y_j y_i),&if k=i,\\ - y_i y_j- y_j(1- y_j),&if k=j,\\ - y_i y_k-(- y_j y_k),&if k≠ i,k≠ j. cases (14) where i=argmaxk~ki= _k y_k (index of predicted class after defense), and j=argmaxk≠i~kj= _k≠ i y_k (index of runner-up class after defense). Since we do not know the index of the predicted class and the runner-up class of ~ y before minimization, we use the index of the predicted class and the runner-up class of y to construct ∇f~(()) _z f(z(x)). Hence, i=argmaxk^ki= _k y_k and j=argmaxk≠i^kj= _k≠ i y_k. The optimal solution for the minimization problem (13) with respect to ∇∗f~(()) _z^* f(z(x)) is as follows: ∇∗f~(())=−αJ()⊤J()∇f(()). _z^* f(z(x))=-α\,J(x) J(x)\, _zf(z(x)). (15) where α→∞α→∞. In our experiments, we found that the norm of ∇∗f~(()) _z^* f(z(x)) is not important for the success of GCD. Thus, we choose α=1α=1. Since we have J()J(x) and ∇f(()) _zf(z(x)), we can compute ∇∗f~(()) _z^* f(z(x)). Because the equation ∇f~(())=∇∗f~(()) _z f(z(x))= _z^* f(z(x)) with respect to ~ y is a nonlinear system, we cannot solve it directly to obtain ~=ℳ~() y= M(x). Moreover, the constraints ‖ℳ()−ℳ~()‖1≤ξ\|M(x)- M(x)\|_1≤ξ and ~∈ΔK y∈ ^K must also be considered. To find ~ y, GCD employs a solution that (i) returns a valid probability vector ~∈ΔK y∈ ^K, (i) keeps ~=ℳ~() y= M(x) close to ^=ℳ() y=M(x) to satisfy the utility constraint, and (i) preserves the predicted label of the target model (argmaxk^k=argmaxk~k _k y_k= _k y_k). GCD solves the following minimization problem to obtain ~ y: argmin~ y −⟨∇f~(()),∇∗f~(())⟩ - _z f(z(x)), _z^* f(z(x)) (16) s.t. .t. ‖ℳ()−ℳ~()‖1≤ξ. \|M(x)- M(x)\|_1≤ξ. The inner product in (16) encourages ∇f~(()) _z f(z(x)) to align with ∇∗f~(()) _z^* f(z(x)) as much as possible, subject to the constraint ‖ℳ()−ℳ~()‖1≤ξ\|M(x)- M(x)\|_1≤ξ. After solving the minimization problem in (16), the resulting ~ y is normalized by dividing by its sum to ensure that ~∈ΔK y∈ ^K. GCD solves the minimization problem in (16) using a trust-region interior-point method (Conn et al., 2000), as implemented in the scipy package (Virtanen et al., 2019). In rare cases, the index of the largest component of the resulting ~ y differs from that of y, which reduces the accuracy of the target model. To address this issue, GCD manually adjusts ~ y. Let i=argmaxk^ki= _k y_k and j=argmaxk~kj= _k y_k. If i≠ji≠ j, GCD adds ~j−~i y_j- y_i to ~i y_i and subtracts it from ~j y_j. This guarantees that argmaxk^k=argmaxk~k _k y_k= _k y_k, thereby preserving the accuracy of the target model. 5 Experiments 5.1 Experimental Setup Datasets and Models. We evaluate our proposed method, Gradient Confusion Defense across two standard benchmark datasets: CIFAR-10 and ImageNet. To ensure comprehensive assessment, we test on multiple model architectures. For CIFAR-10, we utilize pretrained ResNet-18 models. For ImageNet, we employ Torchvision pretrained ResNet-50 and Vision Transformer (ViT-B/16). All evaluations are performed on N=1000N=1000 randomly sampled test images per dataset, ensuring statistical significance while maintaining computational efficiency. Baseline Defenses. We compare GCD against five established defense methods implemented in our experimental framework: input Random Noise Defense (iRND) (Qin et al., 2021) applies Gaussian noise with σ=0.01σ=0.01 to input images. Boundary Defense (oRND) (Aithal and Li, 2022) adds Gaussian noise with σ=1.0σ=1.0 to output logits. Randomized Feature Defense (RFD) (Hung-Quang et al., 2024) injects noise into intermediate features. Random Logit Scaling (RLS) (Dashtbani et al., 2026) multiplies logits by a uniformly sampled scale in [0.5,10][0.5,10]. For Adaptive Attack on Attackers (A), we implement A-sine (Chen et al., 2022) with temperature 11, deviation 0.50.5, attractor interval 44, calibration weight 55, learning rate 0.10.1, and 100100 inner iterations. We only test A-sine, following Chen et al. (2022) which showed A-linear is vulnerable to adaptive attacks. All hyperparameters were selected based on established literature or thorough validation to ensure a fair comparison. Our defense replaces the model output with the optimized probability vector obtained from Equation (16), using an output distortion budget of ξ=0.5ξ=0.5. Since the dimension of ~ y is large for ImageNet and the trust-region interior-point method is a second-order optimizer, minimizing Equation (16) incurs a moderate computational cost. Therefore, for ImageNet we select a subset S of 20 indices of ~ y and optimize Equation (16) only over these components, while fixing the remaining components of ~ y to their corresponding values in y. To construct S, we use ∇∗f~(()) _z^* f(z(x)) and select the top-10 and bottom-10 components, which we found to have the largest effect on the objective in Equation (16). As a result, for ImageNet the optimized ~ y differs from y in only 20 components (before normalization). Attacks Configuration. We evaluate defenses against four state-of-the-art score-based black-box attacks in untargeted settings: BanditAttack (Ilyas et al., 2019) (ℓ2 _2 and ℓ∞ _∞ variants), BrusleAttack (Vo et al., 2024) (ℓ0 _0 variant), SignAttack (Al-Dujaili and O’Reilly, 2020) (ℓ∞ _∞ variant), and SquareAttack (Andriushchenko et al., 2020) (ℓ2 _2 and ℓ∞ _∞ variants). For CIFAR-10, inputs are scaled to [0,255][0,255] with ℓ∞ _∞ budget ϵ=12.75ε=12.75 (0.050.05 normalized) and ℓ2 _2 budget ϵ=255ε=255 (1.01.0 normalized). For ImageNet, inputs are in [0,1][0,1] with ℓ∞ _∞ budget ϵ=0.05ε=0.05, and ℓ2 _2 budgets follow the original implementations (Bandit: ϵ=1275ε=1275, Square: ϵ=5ε=5). All attacks are constrained by a maximum query budget of Q=1000Q=1000 queries per sample. Metrics. We report three metrics for each (dataset, model, defense, attack) configuration: Attack Success Rate, the fraction of samples successfully attacked within the query budget; Average Queries, the mean queries per successful attack; and Clean Accuracy Drop for each defended model. Together, they capture robustness and utility, enabling evaluation of the defense–utility trade-off. Table 1: Black-box attack results on CIFAR-10. ASR and average number of queries are reported. Model Defense Acc. Drop Attacks (Success % / Avg. Queries) Bandit-ℓ2 _2 Bandit-ℓ∞ _∞ Square-ℓ2 _2 Square-ℓ∞ _∞ Sign-ℓ∞ _∞ BrusLe-ℓ0 _0 ResNet-18 None - 82.68% / 545.68 98.03% / 186.16 87.76% / 466.29 99.38% / 112.46 98.97% / 230.05 79.78% / 234.82 iRND 1% 11.63% / 333.97 41.47% / 186.49 24.92% / 290.21 80.52% / 178.96 66.49% / 233.48 82.9% / 220.76 oRND 0.6% 12.53% / 354.43 47.70% / 158.43 20.98% / 188.31 64.09% / 113.92 38.83% / 170.05 68.6% / 201.10 RLS 0% 04.15% / 345.9 25.11% / 23.96 12.76% / 268.69 47.31% / 90.88 21.06% / 111.41 51.77% / 316.57 A 0.1% 03.33% / 318 38.08% / 132.26 9.77% / 174.91 43.41% / 82.04 32.09% / 177.10 66.78% / 290.17 GCD 0% 0.94% / 131.66 28.12% / 99.37 4.15% / 20.95 30.71% / 11.10 14.53% / 72.14 38.59% / 269.82 Table 2: Black-box attack results on ImageNet. ASR and average number of queries are reported. Model Defense Acc. Drop Attacks (Success % / Avg. Queries) Bandit-ℓ2 _2 Bandit-ℓ∞ _∞ Square-ℓ2 _2 Square-ℓ∞ _∞ Sign-ℓ∞ _∞ ResNet-50 None - 46.73% / 761.22 87.05% / 251.79 81.45% / 483.65 99.47% / 133.90 91.33% / 328.71 iRND 0.2% 11.02% / 440.30 45.56% / 141.79 26.66% / 214.17 83.49% / 126.10 60.78% / 229.78 oRND 1.7% 51.47% / 229.94 75.95% / 103.83 59.84% / 208.49 83.52% / 96.91 69.47% / 182.20 RLS 0% 6.68% / 618.42 47.80% / 143.72 16.29% / 143.03 59.82% / 104.07 21.37% / 109.13 A 0.3% 11.80% / 356.96 37.94% / 85.10 15.69% / 32.05 47.06% / 33.59 23.6% / 109.37 GCD 0% 3.34% / 528.6 35.65% / 103.29 13.22% / 64.05 47.94% / 32.17 20.17% / 90.15 ViT-B/16 None - 38.17% / 801.41 76.46% / 319.75 70.64% / 566.65 97.90% / 351.15 80.05% / 597.98 iRND 0.2% 7.78% / 471.24 25.13% / 169.19 21.77% / 287.48 61.70% / 252.02 38% / 255.65 oRND 1.8% 46.71% / 266.73 69.17% / 191.07 58.88% / 291.56 97.32% / 84.39 81.44% / 313.67 RLS 0% 4.47% / 589.5 28.51% / 224.63 10.29% / 148.42 30.36% / 144.31 13.39% / 184.20 A 0% 8.17% / 300.13 22.28% / 102.86 10.9% / 43.72 26.74% / 92.46 15.1% / 236.60 GCD 0% 3.35% / 609 21.94% / 140.03 12.38% / 455.74 33.83% / 257.21 21.44% / 315.70 5.2 Results and Analysis Overall Performance. Tables 1 and 2 summarize results on CIFAR-10 (ResNet-18) and ImageNet (ResNet-50, ViT-B/16). Across settings, GCD achieves a strong robustness–utility trade-off, preserving clean accuracy while reducing attack success rates. On CIFAR-10, GCD lowers Square-ℓ2 _2 ASR from 87.76% (undefended) to 4.15%, and Sign-ℓ∞ _∞ from 98.97% to 14.53%. This effectiveness transfers to ImageNet: for ResNet-50, GCD incurs no clean accuracy drop while maintaining strong robustness. Results on ViT-B/16 further confirm robustness; for example, Square-ℓ∞ _∞ ASR decreases from 97.90% to 33.83%. Comparison with Other Defenses. Tables 1 and 2 also show that on non-transformer models, GCD outperforms nearly all baselines. While randomized defenses (iRND, oRND, RLS) can reduce attack success, they often incur accuracy drops or weaker protection; iRND and oRND trade accuracy for limited robustness. A and RLS preserve accuracy and can be competitive, but are more vulnerable to adaptive attacks (Section 5.3). Table 3 reports ℓ1 _1 deviations over 1000 ImageNet samples: GCD exhibits a larger shift, consistent with shaping scores to misalign the induced adversarial loss gradient rather than merely injecting noise. Table 3: ℓ1 _1 distance between the original output of the model y y and defense output y~ y for 1000 ImageNet samples. Defense Min ℓ1 _1 Avg ℓ1 _1 Max ℓ1 _1 iRND 0.00 0.11 1.03 oRND 0.00 0.26 1.77 RLS 0.00 0.33 1.74 A 0.00 0.28 1.60 GCD 0.07 0.58 1.25 (a) GCD (b) A (c) RLS Figure 1: Polar histograms of gradient direction misalignment. For 10 randomly selected samples from the ImageNet test set, we plot the angular deviation θ=∠(∇f(),∇f~())θ= ( _xf(x), _x f(x)) between the direction ∇f~() _x f(x) induced by the defended score responses (i.e., the direction the attacker would follow) and the true loss gradient ∇f() _xf(x). Each color corresponds to 200 square-ℓ∞ _∞ attack iterations (200 queries used to generate adversarial example for a sample). Dashed rays and numeric labels indicate the mean deviation for each sample. Gradient Misalignment Evidence. Figure 1 shows θ=∠(∇f(),∇f~())θ= ( _xf(x), _x f(x)), the deviation between the true loss gradient ∇f() _xf(x) and the gradient ∇f~() _x f(x) implied by the defended score responses (i.e., the direction the attacker follows). GCD induces a systematic bias in this recovered direction, increasing the query cost of score-based attacks. In particular, GCD yields large deviations across queries (e.g., 24.5∘24.5 –84.4∘84.4 , many near ∼50∘ 50 ), whereas A concentrates at θ≈0∘θ≈ 0 (nearly revealing the true direction). RLS shows mixed behavior, including near-zero angles that still provide a reliable descent direction and angles near 90∘90 . We hypothesize this occurs because the RLS transform maps some target-model output probability vectors to one-hot vectors, making ∇f~()≈0 _x f(x)≈ 0. As a result, GCD’s persistent misalignment compounds over iterations, increasing query complexity and reducing attack success, while defenses that often yield θ≈0∘θ≈ 0 preserve a low-query path. These observations support our theoretical analysis. Figure 2 demonstrates trajectory-level analysis for 10 random CIFAR-10 samples over 100 Square Attack iterations: for each query iteration t along the attack trajectory, we measure the angle θt _t between the direction exposed under the defense and the corresponding undefended direction. This is the operational quantity that matters to an iterative score-based attacker. Based on these results, A does exhibit occasional local reversals, but they are not persistent: after a brief transient, its mean angle quickly settles to a small range (about 8∘8 –10∘10 in our trace plot), and many sample traces remain near low angles. In contrast, GCD maintains substantially larger misalignment throughout the trajectory, with the mean staying around 25∘25 –28∘28 , and many samples remaining in the 30∘30 –45∘45 range over tens of queries. So the practical difference is not whether a defense can reverse a local slope at isolated points, but whether it sustains input-space misalignment along the whole optimization path. GCD does; A usually does not. This also explains the mechanism. A heuristically flips local slopes in output space, but it does not optimize the induced input-space direction after composition with the model Jacobian. GCD is Jacobian-aware: Eqs. (7), (15), and (16) explicitly optimize the exposed direction in input space. That is precisely the quantity that matters for score-based attacks. This interpretation is also consistent with our theory: Theorem 4.4 shows that larger angular misalignment increases the probability of accept/reject errors in search-based attacks, and when that larger angle is maintained across many iterations, those errors compound over the trajectory. Figure 2: Angular deviation between defense-exposed and undefended gradient directions over 100 Square Attack iterations on 10 CIFAR-10 samples. Table 4: Adaptive Attacks on GCD, RLS, and A. We incorporate two adaptive techniques—Expectation over Transformation (EOT) and Pendulum—into the Square Attack framework. For both adaptive variants, we set k=10k=10 and evaluate performance on 10001000 ImageNet samples using ViT-B/16. Defense EOT Pen-Square Max(EOT,Pen) A 21.94% / 85.44 40.53% / 306.08 40.53% RLS 36.19% / 215.83 23.55% / 85.44 36.19% GCD 24.04% / 159.69 30.12% / 209.33 30.12% 5.3 Adaptive Attack Evaluation To assess defense resilience against adaptive adversaries, we evaluate GCD alongside A and RLS against two adaptive attacks: Expectation over Transformation (EOT) (Athalye et al., 2018b) and PendulumAttack (Dashtbani et al., 2026). For sample x, EOT counteracts random-based defenses by averaging over k independently randomized defense outputs (1k∑ki=0ℳ~(i))( 1kΣ^i=0_k M^(i)) to obtain an unbiased estimatimation of the ^=ℳ() y=M(x). PendulumAttack employs iterative estimation and exploitation of defense patterns. Table 4 reveals that GCD maintains performance even under adaptive settings. The primary result is reported in the Max column, which corresponds to a worst-case adaptive threat model in which the attacker uses the more successful of the two evaluated adaptive variants. Under this setting, GCD exhibits stronger robustness than both A and RLS. Figure 2 provides a mechanism-level interpretation of this result. GCD introduces a deterministic bias into the exposed objective, whereas randomization-based defenses primarily introduce variance and A primarily creates local slope perturbations. Adaptive averaging is designed to reduce variance; it does not remove a deterministic directional bias. For a deterministic defense, the relevant question is therefore whether the exposed direction remains persistently displaced along the attack trajectory. Figure 2 shows that GCD maintains this displacement, while A realigns much more quickly. This evidence helps explain the observed adaptive comparison, although it does not by itself establish causality. Adaptive attacks may smooth local irregularities or exploit predictable patterns, but they still optimize the systematically altered objective exposed by GCD. By contrast, A transforms the loss into a structured oscillatory surface. Pendulum-style attacks can exploit such structure by reversing the optimization direction when progress stalls, thereby escaping local minima and maxima. The trajectory plot therefore complements Table 4, it indicates that GCD’s effect is sustained across successive queries rather than being limited to isolated local slope changes. 6 Discussion and Conclusion Our comprehensive evaluation across two datasets, multiple model architectures, four attack methods, and two threat models demonstrates that Gradient Confusion represents an effective new paradigm for black-box defense. By explicitly shaping the gradient information revealed to attackers, GCD Consistently lower attack success rates across all evaluated configurations. Besides, we do not degrade the clean accuracy. Also, GCD Maintains protection even against sophisticated adaptive attacks. These results establish GCD as a state-of-the-art defense against score-based black-box attacks, offering a principled alternative to randomization-based approaches. The method’s model-agnostic implementation and deterministic operation make it particularly suitable for deployment in security-critical applications where both robustness and reliable performance are paramount. However, one limitation warrants discussion. GCD requires Jacobian computations, adding computational overhead (approximately 15% inference time increase). Future work could explore alternative optimization methods and workarounds to address this obstacle. References Aithal and Li (2022) M. B. Aithal and X. Li Boundary defense against black-box adversarial attacks. In 26th International Conference on Pattern Recognition, ICPR 2022, Montreal, QC, Canada, August 21-25, 2022, p. 2349–2356. Cited by: §1, §2, §5.1. Al-Dujaili and O’Reilly (2020) A. Al-Dujaili and U. O’Reilly Sign bits are all you need for black-box attacks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, Cited by: §1, §1, §2, §5.1. Andriushchenko et al. (2020) M. Andriushchenko, F. Croce, N. Flammarion, and M. Hein Square attack: A query-efficient black-box adversarial attack via random search. In Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIII, A. Vedaldi, H. Bischof, T. Brox, and J. Frahm (Eds.), Lecture Notes in Computer Science, Vol. 12368, p. 484–501. Cited by: §1, §1, §2, §3, §5.1. Athalye et al. (2018a) A. Athalye, N. Carlini, and D. A. Wagner Obfuscated gradients give a false sense of security: circumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, J. G. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 274–283. Cited by: §1, §2. Athalye et al. (2018b) A. Athalye, L. Engstrom, A. Ilyas, and K. Kwok Synthesizing robust adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, J. G. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 284–293. Cited by: §1, §5.3. Carlini and Wagner (2017) N. Carlini and D. A. Wagner Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, p. 39–57. Cited by: §1. Chen et al. (2020) J. Chen, M. I. Jordan, and M. J. Wainwright HopSkipJumpAttack: A query-efficient decision-based attack. In 2020 IEEE Symposium on Security and Privacy, SP 2020, San Francisco, CA, USA, May 18-21, 2020, p. 1277–1294. Cited by: §1, §1, §2. Chen and Gu (2020) J. Chen and Q. Gu RayS: A ray searching method for hard-label adversarial attack. In KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, R. Gupta, Y. Liu, J. Tang, and B. A. Prakash (Eds.), p. 1739–1747. Cited by: §1, §1, §2. Chen et al. (2017) P. Chen, H. Zhang, Y. Sharma, J. Yi, and C. Hsieh ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec@CCS 2017, Dallas, TX, USA, November 3, 2017, B. Thuraisingham, B. Biggio, D. M. Freeman, B. Miller, and A. Sinha (Eds.), p. 15–26. Cited by: §2, §3, §3. Chen et al. (2022) S. Chen, Z. Huang, Q. Tao, Y. Wu, C. Xie, and X. Huang Adversarial attack on attackers: post-process to mitigate black-box score-based query attacks. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Cited by: §1, §2, §5.1. Cheng et al. (2020) M. Cheng, S. Singh, P. H. Chen, P. Chen, S. Liu, and C. Hsieh Sign-opt: A query-efficient hard-label adversarial attack. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, Cited by: §1, §1, §2. Conn et al. (2000) A. R. Conn, N. I. M. Gould, and P. L. Toint Trust region methods. MOS-SIAM Series on Optimization, SIAM. Cited by: §4.2. Dashtbani et al. (2026) H. Dashtbani, M. D. Gandomani, and A. Sadeghzadeh Random logit scaling: defending deep neural networks against black-box score-based adversarial example attacks. Transactions on Machine Learning Research 2026. Cited by: §1, §2, §5.1, §5.3. Goodfellow et al. (2015) I. J. Goodfellow, J. Shlens, and C. Szegedy Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, Y. Bengio and Y. LeCun (Eds.), Cited by: §1. Guo et al. (2019) C. Guo, J. R. Gardner, Y. You, A. G. Wilson, and K. Q. Weinberger Simple black-box adversarial attacks. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 2484–2493. Cited by: §1, §1, §2, §3. He et al. (2019) Z. He, A. S. Rakin, and D. Fan Parametric noise injection: trainable randomness to improve deep neural network robustness against adversarial attack. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, p. 588–597. Cited by: §1. Hung-Quang et al. (2024) N. Hung-Quang, Y. Lao, T. Pham, K. Wong, and K. D. Doan Understanding the robustness of randomized feature defense against query-based adversarial attacks. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, Cited by: §1, §5.1. Ilyas et al. (2018) A. Ilyas, L. Engstrom, A. Athalye, and J. Lin Black-box adversarial attacks with limited queries and information. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, J. G. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 2142–2151. Cited by: §1, §2, §3, §3, §3. Ilyas et al. (2019) A. Ilyas, L. Engstrom, and A. Madry Prior convictions: black-box adversarial attacks with bandits and priors. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, Cited by: §1, §1, §2, §3, §5.1. Liu et al. (2018) X. Liu, M. Cheng, H. Zhang, and C. Hsieh Towards robust neural networks via random self-ensemble. In Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part VII, V. Ferrari, M. Hebert, C. Sminchisescu, and Y. Weiss (Eds.), Lecture Notes in Computer Science, Vol. 11211, p. 381–397. Cited by: §2. Madry et al. (2018) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, Cited by: §1. Meckes (2012) E. Meckes Approximation of projections of random vectors. Journal of Theoretical Probability 25 (2), p. 333–352. External Links: Document Cited by: §C.3. Moosavi-Dezfooli et al. (2016) S. Moosavi-Dezfooli, A. Fawzi, and P. Frossard DeepFool: A simple and accurate method to fool deep neural networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, p. 2574–2582. Cited by: §1. Nesterov and Spokoiny (2017) Y. E. Nesterov and V. G. Spokoiny Random gradient-free minimization of convex functions. Found. Comput. Math. 17 (2), p. 527–566. External Links: Link, Document Cited by: §B.1, §B.3, §3. Papernot et al. (2017) N. Papernot, P. D. McDaniel, I. J. Goodfellow, S. Jha, Z. B. Celik, and A. Swami Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS 2017, Abu Dhabi, United Arab Emirates, April 2-6, 2017, R. Karri, O. Sinanoglu, A. Sadeghi, and X. Yi (Eds.), p. 506–519. Cited by: §3. Qin et al. (2021) Z. Qin, Y. Fan, H. Zha, and B. Wu Random noise defense against query-based black-box attacks. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan (Eds.), p. 7650–7663. Cited by: §1, §2, §3, §3, §5.1. Rebuffi et al. (2021) S. Rebuffi, S. Gowal, D. A. Calian, F. Stimberg, O. Wiles, and T. A. Mann Data augmentation can improve robustness. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan (Eds.), p. 29935–29948. Cited by: §2. Reza et al. (2025) M. F. Reza, R. Jin, T. Wu, and H. Dai GSBAK: top-k geometric score-based black-box attack. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025, Cited by: §1, §2. Reza et al. (2023) M. F. Reza, A. Rahmati, T. Wu, and H. Dai CGBA: curvature-aware geometric black-box attack. In IEEE/CVF International Conference on Computer Vision, ICCV 2023, Paris, France, October 1-6, 2023, p. 124–133. Cited by: §1, §1, §2. Rice et al. (2020) L. Rice, E. Wong, and J. Z. Kolter Overfitting in adversarially robust deep learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, Vol. 119, p. 8093–8104. Cited by: §2. Salman et al. (2019) H. Salman, J. Li, I. P. Razenshteyn, P. Zhang, H. Zhang, S. Bubeck, and G. Yang Provably robust deep learning via adversarially trained smoothed classifiers. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, and R. Garnett (Eds.), p. 11289–11300. Cited by: §2. Salman et al. (2020) H. Salman, M. Sun, G. Yang, A. Kapoor, and J. Z. Kolter Denoised smoothing: A provable defense for pretrained classifiers. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (Eds.), Cited by: §2. Szegedy et al. (2014) C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, Y. Bengio and Y. LeCun (Eds.), Cited by: §1. Tramèr et al. (2018) F. Tramèr, A. Kurakin, N. Papernot, I. J. Goodfellow, D. Boneh, and P. D. McDaniel Ensemble adversarial training: attacks and defenses. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, Cited by: §2. Virtanen et al. (2019) P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. Carey, I. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy SciPy 1.0-fundamental algorithms for scientific computing in python. CoRR abs/1907.10121. External Links: 1907.10121 Cited by: §4.2. Vo et al. (2024) V. Q. Vo, E. Abbasnejad, and D. Ranasinghe Brusleattack: a query-efficient score- based black-box sparse adversarial attack. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, Cited by: §1, §1, §2, §5.1. Wang et al. (2021) D. Wang, A. Ju, E. Shelhamer, D. A. Wagner, and T. Darrell Fighting gradients with gradients: dynamic defenses against adversarial attacks. CoRR abs/2105.08714. External Links: 2105.08714 Cited by: §1. Xie et al. (2018) C. Xie, J. Wang, Z. Zhang, Z. Ren, and A. L. Yuille Mitigating adversarial effects through randomization. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, Cited by: §1. Appendix A Notations Here one can find all notations and symbols used in the paper. Table 5: Summary of Notations and Symbols used in the Gradient Confusion Defense (GCD) paper. Symbol Description General Model and Inputs X Input space, ⊆[0,1]dX [0,1]^d d Dimension of the input space [K][K] Label set 1,…,K\1,…,K\ ℳM Classifier mapping →ΔKX→ ^K ()z(x) Logits vector output by the model for input x σ(⋅)σ(·) Softmax function ΔK ^K Probability simplex ∈ℝK∣∑i=1\p ^K _ip_i=1\ ^,ℳ() y,M(x) Original probability vector output by the target model k True label of input x J()J(x) Jacobian of the model’s logits with respect to the input, ∇() _xz(x) Attacks and Optimization advx_adv Adversarial example (adv=+x_adv=x+ δ) R Perturbation budget (radius of the allowed perturbation ball) Q Maximum query budget f()f(x) Adversarial loss function based on the original model output i,ji,j Indices of the largest and second-largest probability components ∇^fμ() ∇_xf_μ(x) Estimated gradient of the smoothed function ,tu,u_t Random search direction vector, ∼(,)u (0,I) μ Smoothing parameter (step size for finite differences) fμ()f_μ(x) Gaussian-smoothed version of the loss function ηt _t Step size (learning rate) at iteration t Πξ _ξ Projection operator onto the lpl_p-ball of radius ξ hth_t One-step improvement signal in random search Gradient Confusion Defense (GCD) ~,ℳ~() y, M(x) Modified/Defended probability vector returned to the user ~() z(x) Perturbed logits corresponding to ~ y f~() f(x) Adversarial loss function based on the modified output ~ y ξ Distortion budget (constraint on l1l_1 distance between y and ~ y) fdef()f_def(x) Randomized defended objective function (theoretical model) λ Bernoulli random variable used in the theoretical switching defense p Probability parameter for the Bernoulli distribution (λ∼Bernoulli(p)λ (p)) Theoretical Analysis L0(f)L_0(f) Lipschitz continuity constant of function f L1(f)L_1(f) Lipschitz constant of the gradient (smoothness constant) of f T Total number of optimization steps/queries ϵε Small constants bounding the difference between functions (|f−f~||f- f|) ϵ′ε Small constants bounding the difference between functions (|fμ−f||f_μ-f|) hdefh_def Improvement signal computed from the defender’s returned values Appendix B Theoretical Analysis of Gradient Confusion for Gradient Estimation-Based Attacks In this appendix, we provide the theoretical analysis of Theorem 4.3. We show that by incorporating a second function f~ f, which is close to the original function f but has misaligned gradients, we can increase the convergence bound of gradient-estimation-based attacks. This analysis provides insights into how optimizing a confusion term can enhance the robustness of models against such attacks. We first state preliminaries and lemmas used in the proof, and then present the detailed proof of Theorem 4.3. B.1 Preliminaries Definition B.1 (μ-Gaussian Smoothing). For a function f:ℝd→ℝf:R^d , we define its μ-Gaussian smoothed version as: fμ()=∼(,)[f(+μ)]f_μ(x)=E_u (0,I_d)[f(x+ )] (17) Now, we define the gradient estimator as gμ()=f(+μ)−f()μ,g_μ(x)= f(x+ )-f(x)μ\,u, (18) where ∼(,d)u (0,I_d). Using the change of variables :=+μy:=x+ , we can show that the gradient of the smoothed function can be written as ∇fμ() ∇ f_μ(x) =∇(1(2π)d/2∫f(+μ)e−12‖2d) =∇ ( 1(2π)^d/2 f(x+ )e^- 12\|u\|^2du ) (19) =∇(1μd+1(2π)d/2∫f()e−12μ2‖−‖2d) =∇ ( 1μ^d+1(2π)^d/2 f(y)e^- 12μ^2\|y-x\|^2dy ) (Change of variables) (Change of variables) =1μd+1(2π)d/2∫f()(−μ2)e−12μ2‖−‖2 = 1μ^d+1(2π)^d/2 f(y) (- y-xμ^2 )e^- 12μ^2\|y-x\|^2dy =1μd+1(2π)d/2∫f(+μ)(−μμ2)e−12‖2μd = 1μ^d+1(2π)^d/2 f(x+ ) (- μ^2 )e^- 12\|u\|^2μ^ddu (Change of variables) (Change of variables) =1(2π)d/2∫f(+μ)(−μ)e−12‖2 = 1(2π)^d/2 f(x+ ) (- uμ )e^- 12\|u\|^2du =∼(,)[f(+μ)μ] =E_u (0,I_d) [ f(x+ )μu ] (∼(,)[f()μ]=0) (E_u (0,I_d) [ f(x)μu ]=0 ) =∼(,)[f(+μ)−f()μ] =E_u (0,I_d) [ f(x+ )-f(x)μu ] =∼(,)[gμ()] =E_u (0,I_d)[g_μ(x)] Thus, we have the following lemma: Lemma B.2. The gradient estimator gμ()g_μ(x) is an unbiased estimator of the gradient of the smoothed function fμ()f_μ(x), i.e., [gμ()]=∇fμ()E_u\! [g_μ(x) ]=∇ f_μ(x). We also use the following lemma on the smoothness of the Gaussian-smoothed function from Nesterov and Spokoiny (2017): Lemma B.3. If f is L0(f)L_0(f)-Lipschitz continuous, then its smoothed version fμf_μ is differentiable and has a Lipschitz continuous gradient with constant L1(fμ)=2dμL0(f).L_1(f_μ)= 2 dμL_0(f). We also use the following lemma on the moments of Gaussian random variables, which follows from standard concentration properties of Gaussian distributions: Lemma B.4. For ∼(,d)u (0,I_d), we have [‖2]≤d,E\! [\|u\|^2 ]≤ d, (20) and [‖4]≤(d+4)2.E\! [\|u\|^4 ]≤(d+4)^2. (21) B.2 Bias and variance of gradient estimator Let f:ℝd→ℝf:R^d and f~:ℝd→ℝ f:R^d be two functions such that, for all ∈ℝdx ^d, |f()−f~()|≤ϵ|f(x)- f(x)|≤ε. We define a randomized objective h as h()=λf()+(1−λ)f~(),h(x)=λ f(x)+(1-λ) f(x), (22) where λ∼Bernoulli(p)λ (p). Thus, the corresponding gradient estimator is given by gμ() g_μ(x) =(λ1f(+μ)+(1−λ1)f~(+μ))−(λ2f()+(1−λ2)f~())μ = ( _1f(x+ )+(1- _1) f(x+ ) )- ( _2f(x)+(1- _2) f(x) )μu (23) =[λ1f(+μ)−f()μ+(1−λ1)f~(+μ)−f~()μ+(λ1−λ2)(f()−f~())μ] = [ _1 f(x+ )-f(x)μ+(1- _1) f(x+ )- f(x)μ+ ( _1- _2)(f(x)- f(x))μ ]u Thus, for the expectation of the gradient estimator, we have: λ1,λ2[gμ()] _ _1, _2[g_μ(x)] =p(f(+μ)−f()μ)+(1−p)(f~(+μ)−f~()μ) =p ( f(x+ )-f(x)μu )+(1-p) ( f(x+ )- f(x)μu ) (24) From lemma B.2 we have: ,λ1,λ2[gμ()]=p∇fμ()+(1−p)∇f~μ()E_u, _1, _2[g_μ(x)]=p∇ f_μ(x)+(1-p)∇ f_μ(x) (25) Now we need to compute the variance of the gradient estimator: ‖gμ()‖2=[λ1f(+μ)−f()μ+(1−λ1)f~(+μ)−f~()μ+(λ1−λ2)(f()−f~())μ]2⏟A‖2 gathered\|g_μ(x)\|^2= [ _1 f(x+ )-f(x)μ+(1- _1) f(x+ )- f(x)μ+ ( _1- _2)(f(x)- f(x))μ ]^2_A\|u\|^2\\ gathered (26) Now set α=f(+μ)−f()μα= f(x+ )-f(x)μ, α~=f~(+μ)−f~()μ α= f(x+ )- f(x)μ, and δ=f()−f~()μδ= f(x)- f(x)μ. Thus for A we have: A=λ12α2+(1−λ1)2α~2+(λ1−λ2)2δ2+2λ1(1−λ1)αα~+2λ1(λ1−λ2)αδ+2(1−λ1)(λ1−λ2)α~δ⟹λ1,λ2[A]=pα2+(1−p)α~2+2p(1−p)(α−α~)δ+2p(1−p)δ2=pα2+(1−p)α~2+2p(1−p)(α−α~+δ)δλ1,λ2[A]=p(f(+μ)−f()μ)2+(1−p)(f~(+μ)−f~()μ)2+2p(1−p)μ2(f(+μ)−f~(+μ))(f()−f~()) gatheredA= _1^2α^2+(1- _1)^2 α^2+( _1- _2)^2δ^2+2 _1(1- _1)α α+2 _1( _1- _2)αδ+2(1- _1)( _1- _2) αδ\\ _ _1, _2[A]=pα^2+(1-p) α^2+2p(1-p)(α- α)δ+2p(1-p)δ^2\\ =pα^2+(1-p) α^2+2p(1-p)(α- α+δ)δ\\[10.00002pt] E_ _1, _2[A]=p ( f(x+ )-f(x)μ )^2+(1-p) ( f(x+ )- f(x)μ )^2\\ + 2p(1-p)μ^2 (f(x+ )- f(x+ ) ) (f(x)- f(x) )\\ gathered (27) Now using the bound |f()−f~()|≤ϵ|f(x)- f(x)|≤ε, and Lipschitz continuity of f and f~ f, we have: λ1,λ2[A]≤pL02(f)‖2+(1−p)L02(f~)‖2+2p(1−p)ϵ2μ2 gatheredE_ _1, _2[A]≤ pL^2_0(f)\|u\|^2+(1-p)L^2_0( f)\|u\|^2+ 2p(1-p)ε^2μ^2\\ gathered (28) Putting this into equation 26, we have: λ1,λ2[‖gμ()‖2]≤pL02(f)‖4+(1−p)L02(f~)‖4+2p(1−p)ϵ2μ2‖2E_ _1, _2[\|g_μ(x)\|^2]≤ pL^2_0(f)\|u\|^4+(1-p)L^2_0( f)\|u\|^4+ 2p(1-p)ε^2μ^2\|u\|^2 (29) Now taking expectation over u, using lemma B.4 we have: ,λ1,λ2[‖gμ()‖2]≤pL02(f)(d+4)2+(1−p)L02(f~)(d+4)2+2p(1−p)ϵ2μ2dE_u, _1, _2[\|g_μ(x)\|^2]≤ pL^2_0(f)(d+4)^2+(1-p)L^2_0( f)(d+4)^2+ 2p(1-p)ε^2μ^2d (30) B.3 Descent Lemma We now define the optimization process. Starting from 0x_0, at each iteration t we sample λ1(t),λ2(t)∼Bernoulli(p) _1^(t), _2^(t) (p) and (t)∼(,d)u^(t) (0,I_d), and compute the gradient estimator gμ(t)g_μ(x_t). We then update the iterate as t+1=t−ηtgμ(t),x_t+1=x_t- _tg_μ(x_t), where ηt _t denotes the step size at iteration t. Consequently, each iterate tx_t is a random variable that depends on all previous samples λ1(i),λ2(i),(i)i<t\ _1^(i), _2^(i),u^(i)\_i<t. We define the history up to iteration t as t=λ1(i),λ2(i),(i)i<t.Z_t= \ _1^(i), _2^(i),u^(i) \_i<t. Our goal is to analyze the convergence of this process in expectation over all sources of randomness. We assume the process is run for T iterations. Having access to the variance and bias of the gradient estimator, we can now use the standard descent lemma for zero order optimization. fμ(t+1)≤fμ(t)−ηt⟨∇fμ(t),gμ(t)⟩+L1(fμ)2ηt2‖gμ(t)‖2f_μ(x_t+1)≤ f_μ(x_t)- _t ∇ f_μ(x_t),g_μ(x_t) + L_1(f_μ)2 _t^2\|g_μ(x_t)\|^2 (31) Using equations 25 and 30, and taking expectation over λ1(t),λ2(t) _1^(t), _2^(t) and (t)u^(t) we have: (t),λ1(t),λ2(t)[fμ(t+1)]≤fμ(t)−ηtp‖∇fμ(t)‖2−ηt(1−p)⟨∇fμ(t),∇f~μ(t)⟩+L1(fμ)2ηt2(pL02(f)(d+4)2+(1−p)L02(f~)(d+4)2+2p(1−p)ϵ2μ2d) gatheredE_u^(t), _1^(t), _2^(t)[f_μ(x_t+1)]≤ f_μ(x_t)- _tp\|∇ f_μ(x_t)\|^2- _t(1-p) ∇ f_μ(x_t),∇ f_μ(x_t) \\[6.00006pt] + L_1(f_μ)2 _t^2 (pL^2_0(f)(d+4)^2+(1-p)L^2_0( f)(d+4)^2+ 2p(1-p)ε^2μ^2d ) gathered (32) Now taking expectation over the history tZ_t, we have: t,(t),λ1(t),λ2(t)[fμ(t+1)]=t+1[fμ(t+1)]≤t[fμ(t)]−ηtpt[‖∇fμ(t)‖2]−ηt(1−p)t[⟨∇fμ(t),∇f~μ(t)⟩]+L1(fμ)2ηt2(pL02(f)(d+4)2+(1−p)L02(f~)(d+4)2+2p(1−p)ϵ2μ2d) gatheredE_Z_t,u^(t), _1^(t), _2^(t)[f_μ(x_t+1)]=E_Z_t+1[f_μ(x_t+1)]\\ _Z_t[f_μ(x_t)]- _tpE_Z_t[\|∇ f_μ(x_t)\|^2]- _t(1-p)E_Z_t[ ∇ f_μ(x_t),∇ f_μ(x_t) ]\\[6.00006pt] + L_1(f_μ)2 _t^2 (pL^2_0(f)(d+4)^2+(1-p)L^2_0( f)(d+4)^2+ 2p(1-p)ε^2μ^2d ) gathered (33) Let’s define new notations for simplicity: At=t[fμ(t)]Bt=t[‖∇fμ(t)‖2]Ct=t[⟨∇fμ(t),∇f~μ(t)⟩]D=pL02(f)(d+4)2+(1−p)L02(f~)(d+4)2+2p(1−p)ϵ2μ2d casesA_t=E_Z_t[f_μ(x_t)]\\ B_t=E_Z_t[\|∇ f_μ(x_t)\|^2]\\ C_t=E_Z_t[ ∇ f_μ(x_t),∇ f_μ(x_t) ]\\ D=pL^2_0(f)(d+4)^2+(1-p)L^2_0( f)(d+4)^2+ 2p(1-p)ε^2μ^2d\\ cases (34) Rewrite the inequality with new notations: At+1≤At−ηtpBt−ηt(1−p)Ct+L1(fμ)2ηt2DA_t+1≤ A_t- _tpB_t- _t(1-p)C_t+ L_1(f_μ)2 _t^2D (35) Rearranging the terms, we have: At+1−At≤−ηtpBt−ηt(1−p)Ct+L1(fμ)2ηt2DA_t+1-A_t≤- _tpB_t- _t(1-p)C_t+ L_1(f_μ)2 _t^2D (36) Thus for different iterations t=0,…,T−1t=0,…,T-1, we have: A1−A0≤−η0pB0−η0(1−p)C0+L1(fμ)2η02DA2−A1≤−η1pB1−η1(1−p)C1+L1(fμ)2η12DAT−AT−1≤−ηT−1pBT−1−ηT−1(1−p)CT−1+L1(fμ)2ηT−12D gatheredA_1-A_0≤- _0pB_0- _0(1-p)C_0+ L_1(f_μ)2 _0^2D\\ A_2-A_1≤- _1pB_1- _1(1-p)C_1+ L_1(f_μ)2 _1^2D\\ \\ A_T-A_T-1≤- _T-1pB_T-1- _T-1(1-p)C_T-1+ L_1(f_μ)2 _T-1^2D\\ gathered (37) Summing all these inequalities, we have: AT−A0≤−p∑t=0T−1ηtBt−(1−p)∑t=0T−1ηtCt+L1(fμ)2D∑t=0T−1ηt2A_T-A_0≤-p _t=0^T-1 _tB_t-(1-p) _t=0^T-1 _tC_t+ L_1(f_μ)2D _t=0^T-1 _t^2 (38) Here A0=fμ(0)A_0=f_μ(x_0) and AT=T[fμ(T)]A_T=E_Z_T[f_μ(x_T)] is the expectation of the function value at the end of the optimization process. Let’s assume we use constant step size ηt=η _t=η for all t. Thus we have: AT−A0≤−ηp∑t=0T−1Bt−η(1−p)∑t=0T−1Ct+L1(fμ)2η2DTA_T-A_0≤-η p _t=0^T-1B_t-η(1-p) _t=0^T-1C_t+ L_1(f_μ)2η^2DT (39) Taking average over T iterations, we have: 1ηT(AT−A0)≤−p1T∑t=0T−1Bt−(1−p)1T∑t=0T−1Ct+L1(fμ)2ηD 1η T(A_T-A_0)≤-p 1T _t=0^T-1B_t-(1-p) 1T _t=0^T-1C_t+ L_1(f_μ)2η D (40) Rearranging the terms, we have: p1T∑t=0T−1Bt+(1−p)1T∑t=0T−1Ct≤A0−ATηT+L1(fμ)2ηDp 1T _t=0^T-1B_t+(1-p) 1T _t=0^T-1C_t≤ A_0-A_Tη T+ L_1(f_μ)2η D (41) Now minimize the right hand side with respect to η: η∗=2(A0−AT)L1(fμ)DTη = 2(A_0-A_T)L_1(f_μ)DT (42) Thus we have: p1T∑t=0T−1Bt+(1−p)1T∑t=0T−1Ct≤2L1(fμ)D(A0−ATT)p 1T _t=0^T-1B_t+(1-p) 1T _t=0^T-1C_t≤ 2L_1(f_μ)D ( A_0-A_TT ) (43) From Lipschitz continuity of f and f~ f, we know that fμf_μ and f~μ f_μ are also Lipschitz continuous with the same constants. Thus we can bound A0−ATA_0-A_T as: |A0−AT|≤L0(f)‖0−∗‖≤L0(f)R|A_0-A_T|≤ L_0(f)\|x_0-x \|≤ L_0(f)R (44) Where R is the radius of the ball for optimization budget. Thus we have the final convergence bound as: p1T∑t=0T−1Bt+(1−p)1T∑t=0T−1Ct≤2L1(fμ)D(L0(f)RT)p 1T _t=0^T-1B_t+(1-p) 1T _t=0^T-1C_t≤ 2L_1(f_μ)D ( L_0(f)RT ) (45) From the definition of fμf_μ and lemma B.3 we have L1(fμ)=2d1/2μL0(f)L_1(f_μ)= 2d^1/2μL_0(f), therefore we have: p1T∑t=0T−1Bt+(1−p)1T∑t=0T−1Ct≤4d1/2L0(f)2RμTDp 1T _t=0^T-1B_t+(1-p) 1T _t=0^T-1C_t≤ 4d^1/2L_0(f)^2Rμ TD (46) We also need to choose μ small enough to have |fμ()−f()|≤ϵ′|f_μ(x)-f(x)|≤ε . To have this bound, we choose μ≤ϵ′d1/2L0(f)μ≤ ε d^1/2L_0(f) as in Nesterov and Spokoiny (2017). Thus we can still simplify the bound as: p1T∑t=0T−1Bt+(1−p)1T∑t=0T−1Ct≤4dL0(f)3Rϵ′TDp 1T _t=0^T-1B_t+(1-p) 1T _t=0^T-1C_t≤ 4dL_0(f)^3Rε TD (47) Let’s also plug this value in D and rewrite that: D=pL02(f)(d+4)2+(1−p)L02(f~)(d+4)2+2p(1−p)ϵ2d2L0(f)2ϵ′2D=pL^2_0(f)(d+4)^2+(1-p)L^2_0( f)(d+4)^2+ 2p(1-p)ε^2d^2L_0(f)^2ε 2 (48) The input dimension d usually dominates the constant 44 in (d+4)(d+4), thus we can simplify the final bound as: D D ≈pL02(f)d2+(1−p)L02(f~)d2+2p(1−p)ϵ2d2L0(f)2ϵ′2 ≈ pL^2_0(f)d^2+(1-p)L^2_0( f)d^2+ 2p(1-p)ε^2d^2L_0(f)^2ε 2 (49) =pd2L0(f)2(1+(1−p)pL02(f~)L02(f)+2(1−p)ϵ2ϵ′2) =pd^2L_0(f)^2 (1+ (1-p)p L^2_0( f)L^2_0(f)+2(1-p) ε^2ε 2 ) Plugging this into the final bound, we have: pT∑t=0T−1t[∥∇fμ(t)∥2]+1−pT∑t=0T−1t[⟨∇fμ(t),∇f~μ(t)]≤4d3L0(f)5Rϵ′T(p+(1−p)L02(f~)L02(f)+2p(1−p)ϵ2ϵ′2) pT _t=0^T-1E_Z_t[\|∇ f_μ(x_t)\|^2]+ 1-pT _t=0^T-1E_Z_t[ ∇ f_μ(x_t),∇ f_μ(x_t)]≤ 4d^3L_0(f)^5Rε T (p+(1-p) L^2_0( f)L^2_0(f)+2p(1-p) ε^2ε 2 ) (50) This bound shows that optimizing the confusion term ⟨∇fμ(),∇f~μ()⟩ ∇ f_μ(x),∇ f_μ(x) increases the bound and, consequently, increases the number of steps required by gradient estimation-based attacks. Appendix C Theoretical Analysis of Gradient Confusion for Search-Based Attacks In this part, we provide the detailed proof of Theorem 4.4, which theoretically shows that GC can be effective against search-based attacks by misleading the acceptance/rejection signal hth_t. As a result, the adversary requires more steps (and thus more queries) to craft an adversarial example. We first present auxiliary lemmas used in the proof, and then provide the detailed proof of the theorem. C.1 Auxiliary Lemmas Lemma C.1. Let f:ℝd→ℝf:R^d be L-smooth, i.e., ‖∇f(u)−∇f(v)‖≤L‖u−v‖∀u,v∈ℝd.\|∇ f(u)-∇ f(v)\|≤ L\|u-v\| ∀ u,v ^d. Then for any x,ϵ∈ℝdx,ε ^d, f(x+ϵ)=f(x)+⟨∇f(x),ϵ⟩+rf,f(x+ε)=f(x)+ ∇ f(x),ε +r_f, where the remainder term satisfies |rf|≤L2‖ϵ‖2. |r_f|≤ L2\|ε\|^2. Equivalently, |f(x+ϵ)−f(x)−⟨∇f(x),ϵ⟩|≤L2‖ϵ‖2. |f(x+ε)-f(x)- ∇ f(x),ε |≤ L2\|ε\|^2. Proof. Define ϕ(t)=f(x+tϵ)φ(t)=f(x+tε) for t∈[0,1]t∈[0,1]. By the fundamental theorem of calculus, f(x+ϵ)−f(x)=∫01⟨∇f(x+tϵ),ϵ⟩t.f(x+ε)-f(x)= _0^1 ∇ f(x+tε),ε \,dt. Subtracting the first-order term yields f(x+ϵ)−f(x)=⟨∇f(x),ϵ⟩+∫01⟨∇f(x+tϵ)−∇f(x),ϵ⟩t.f(x+ε)-f(x)= ∇ f(x),ε + _0^1 ∇ f(x+tε)-∇ f(x),ε \,dt. Thus the remainder term is rf=∫01⟨∇f(x+tϵ)−∇f(x),ϵ⟩t.r_f= _0^1 ∇ f(x+tε)-∇ f(x),ε \,dt. Applying Cauchy–Schwarz and L-smoothness, |rf|≤∫01‖∇f(x+tϵ)−∇f(x)‖‖ϵ‖t≤∫01Lt‖ϵ‖2t=L2‖ϵ‖2.|r_f|≤ _0^1\|∇ f(x+tε)-∇ f(x)\|\,\|ε\|\,dt≤ _0^1Lt\|ε\|^2\,dt= L2\|ε\|^2. ∎ Lemma C.2. Let u∼(0,Id)u (0,I_d) in ℝdR^d with d≥2d≥ 2, and let g∈ℝdg ^d be fixed with g≠0g≠ 0. Then for any c≥0c≥ 0, ℙ(|g⊤u|<c‖u‖2)≤2πcd‖g‖.P\! (\,|g u|<c\,\|u\|^2\, )\;≤\; 2π\, c\,d\|g\|. Proof. Write u=rsu=rs where r=‖u‖≥0r=\|u\|≥ 0 and s=u/‖u‖∈Sd−1s=u/\|u\|∈ S^d-1. By rotational invariance of the standard Gaussian, r and s are independent, s is uniform on the unit sphere, and r2∼χd2r^2 χ^2_d. Let a=‖g‖>0a=\|g\|>0. Then g⊤u=rg⊤s.g u=r\,g s. By rotation symmetry, g⊤s=daTg s d=aT, where T is the first coordinate of a uniform random point on Sd−1S^d-1. Hence ℙ(|g⊤u|<c‖u‖2|r)=ℙ(|arT|<cr2|r)=ℙ(|T|<car).P\! (|g u|<c\|u\|^2\, |\,r )=P\! (|arT|<cr^2\, |\,r )=P\! (|T|< ca\,r ). For d≥2d≥ 2, T has density on [−1,1][-1,1] fT(t)=Cd(1−t2)d−32,Cd=Γ(d/2)πΓ((d−1)/2).f_T(t)=C_d(1-t^2) d-32, C_d= (d/2) π\, ((d-1)/2). Since supt∈[−1,1]fT(t)=fT(0)=Cd _t∈[-1,1]f_T(t)=f_T(0)=C_d, for any t≥0t≥ 0 we have ℙ(|T|<t)=∫−ttfT(x)x≤2tCd.P(|T|<t)= _-t^tf_T(x)\,dx≤ 2t\,C_d. Therefore, ℙ(|T|<car)≤2Cdcar.P\! (|T|< ca\,r )≤ 2C_d ca\,r. Taking expectation over r gives ℙ(|g⊤u|<c‖u‖2)≤2Cdca[r].P\! (|g u|<c\|u\|^2 )≤ 2C_d ca\,E[r]. By Cauchy–Schwarz, [r]≤‖u‖2=dE[r]≤ E\|u\|^2= d. Finally, using Γ(x+12)/Γ(x)≤x (x+ 12)/ (x)≤ x for all x≥12x≥ 12 with x=d−12x= d-12, Cd=Γ(d/2)πΓ((d−1)/2)=1πΓ(x+12)Γ(x)≤d2π.C_d= (d/2) π\, ((d-1)/2)= 1 π (x+ 12) (x)≤ d2π. Combining gives ℙ(|g⊤u|<c‖u‖2)≤2(d2π)c‖g‖(d)=2πcd‖g‖.P\! (|g u|<c\|u\|^2 )≤ 2 ( d2π ) c\|g\| ( d )= 2π\, c\,d\|g\|. ∎ Lemma C.3. Let u∼(0,Id)u (0,I_d) and let g,g~∈ℝdg, g ^d be nonzero vectors. Define θ∈[0,π]θ∈[0,π] to be the angle between g and g~ g, i.e. cosθ=⟨g,g~⟩‖g‖‖g~‖. θ\;=\; g, g \|g\|\,\| g\|. Then ℙ(sign(⟨g,u⟩)≠sign(⟨g~,u⟩))=θπ=1πarccos(⟨g,g~⟩‖g‖‖g~‖).P ( ( g,u )≠ ( g,u ) )\;=\; θπ= 1π \! ( g, g \|g\|\,\| g\| ). Proof. Set X=⟨g,u⟩X= g,u and Y=⟨g~,u⟩Y= g,u . Then (X,Y)(X,Y) is a centered bivariate Gaussian with Var(X)=‖g‖2,Var(Y)=‖g~‖2,Cov(X,Y)=⟨g,g~⟩,Var(X)=\|g\|^2, (Y)=\| g\|^2, (X,Y)= g, g , so the correlation is ρ=⟨g,g~⟩/(‖g‖‖g~‖)=cosθρ= g, g /(\|g\|\| g\|)= θ. A standard orthant probability identity gives ℙ(X>0,Y>0)=14+12πarcsin(ρ).P(X>0,Y>0)= 14+ 12π (ρ). By symmetry, ℙ(XY<0)=1−2ℙ(X>0,Y>0)=12−1πarcsin(ρ)=1πarccos(ρ)=θπ.P(XY<0)=1-2P(X>0,Y>0)= 12- 1π (ρ)= 1π (ρ)= θπ. ∎ C.2 Proof of Theorem 4.4 With the above lemmas in place, we now state the theorem and present a detailed proof. Theorem C.4 (Theorem 4.4 (restated)). Under Assumption 4.2, for d≥2d≥ 2, ∼(0,Id)u (0,I_d), fixed ∈ℝdx ^d, μ>0μ>0, and with per-query switching defense fdeff_def, the signals h:=f(+μ)−f(),hdef:=fdef(+μ)−fdef()h:=f(x+ )-f(x), h_def:=f_def(x+ )-f_def(x) satisfy the bound in (11). Proof. Let Δf:=f(x+μu)−f(x),Δf~:=f~(x+μu)−f~(x). _f:=f(x+μ u)-f(x), _ f:= f(x+μ u)- f(x). By definition, h=Δfh= _f. Let λ1,λ2∼i.i.d.Bernoulli(p) _1, _2 .i.d. Bernoulli(p) be independent of u, and write fdef(x+μu)=λ1f(x+μu)+(1−λ1)f~(x+μu),fdef(x)=λ2f(x)+(1−λ2)f~(x).f_def(x+μ u)= _1f(x+μ u)+(1- _1) f(x+μ u), f_def(x)= _2f(x)+(1- _2) f(x). Define E:=sign(h)≠sign(hdef)E:=\ (h)≠ (h_def)\. Conditioning on (λ1,λ2)( _1, _2) and keeping only the case (0,0)(0,0) gives ℙ(E) (E) ≥ℙ(E∩λ1=0,λ2=0) (E∩\ _1=0, _2=0\ ) =ℙ(λ1=0,λ2=0)ℙ(sign(Δf)≠sign(Δf~)) =P( _1=0, _2=0)\;P\! ( ( _f)≠ ( _ f) ) =(1−p)2ℙ(sign(Δf)≠sign(Δf~)). =(1-p)^2\;P\! ( ( _f)≠ ( _ f) ). It remains to lower bound ℙ(sign(Δf)≠sign(Δf~))P( ( _f)≠ ( _ f)). Define the linear parts A:=⟨∇f(x),u⟩,A~:=⟨∇f~(x),u⟩.A:= ∇ f(x),u , A:= ∇ f(x),u . By Lemma C.1 applied to f with L=L1(f)L=L_1(f) and ϵ=μuε=μ u, Δf=μA+rf,|rf|≤L1(f)2μ2‖u‖2. _f=μ A+r_f, |r_f|≤ L_1(f)2μ^2\|u\|^2. Similarly, applying Lemma C.1 to f~ f with L=L1(f~)L=L_1( f), Δf~=μA~+rf~,|rf~|≤L1(f~)2μ2‖u‖2. _ f=μ A+r_ f, |r_ f|≤ L_1( f)2μ^2\|u\|^2. Step 1: sign-stability events. If |δ|<|a||δ|<|a|, then sign(a+δ)=sign(a) (a+δ)= (a). Define Gf:=L1(f)2μ∥u∥2<|A|,Gf~:=L1(f~)2μ∥u∥2<|A~|.G_f:= \ L_1(f)2μ\|u\|^2<|A| \, G_ f:= \ L_1( f)2μ\|u\|^2<| A| \. On GfG_f, we have |rf|<μ|A||r_f|<μ|A|, hence sign(Δf)=sign(A) ( _f)= (A); similarly on Gf~G_ f, sign(Δf~)=sign(A~) ( _ f)= ( A). Therefore, ℙ(sign(Δf)≠sign(Δf~))≥ℙ(sign(A)≠sign(A~))−ℙ(Gfc)−ℙ(Gf~c).P\! ( ( _f)≠ ( _ f) ) \! ( (A)≠ ( A) )-P(G_f^c)-P(G_ f^c). Step 2: linear sign disagreement. By Lemma C.3 with g=∇f(x)g=∇ f(x) and g~=∇f~(x) g=∇ f(x), ℙ(sign(A)≠sign(A~))=1πarccos(⟨∇f(x),∇f~(x)⟩‖∇f(x)‖‖∇f~(x)‖).P\! ( (A)≠ ( A) )= 1π \! ( ∇ f(x),∇ f(x) \|∇ f(x)\|\,\|∇ f(x)\| ). Step 3: bound Taylor-failure probabilities. Using Lemma C.2 with g=∇f(x)g=∇ f(x) and c=L1(f)2μc= L_1(f)2μ, ℙ(Gfc)=ℙ(|A|<L1(f)2μ‖u‖2)≤2π(L1(f)2μ)d‖∇f(x)‖=μd2πL1(f)‖∇f(x)‖.P(G_f^c)=P\! (|A|< L_1(f)2μ\|u\|^2 )≤ 2π ( L_1(f)2μ)d\|∇ f(x)\|= μ d 2π L_1(f)\|∇ f(x)\|. Similarly, ℙ(Gf~c)≤μd2πL1(f~)‖∇f~(x)‖.P(G_ f^c)≤ μ d 2π L_1( f)\|∇ f(x)\|. Step 4: combine and multiply by (1−p)2(1-p)^2. Combining Steps 1–3 yields ℙ(sign(Δf)≠sign(Δf~))≥1πarccos(⟨∇f(x),∇f~(x)⟩‖∇f(x)‖‖∇f~(x)‖)−μd2π(L1(f)‖∇f(x)‖+L1(f~)‖∇f~(x)‖).P\! ( ( _f)≠ ( _ f) )≥ 1π \! ( ∇ f(x),∇ f(x) \|∇ f(x)\|\,\|∇ f(x)\| )- μ d 2π ( L_1(f)\|∇ f(x)\|+ L_1( f)\|∇ f(x)\| ). Multiplying by (1−p)2(1-p)^2 gives (11). ∎ C.3 Why Gaussian Directions? We model the search direction as Gaussian because it is rotationally invariant and makes the analysis depend only on geometry. This is also a good approximation for many isotropic samplers used in practice: in high dimensions, one-dimensional projections (i.e., inner products with a random direction) of a broad class of high-dimensional random vectors are close to Gaussian under mild conditions, so Gaussian modeling captures the sign behavior of these projections well (Meckes, 2012). In the proof, the key quantity is the probability that the two linearized one-step signals induced by ∇f()∇ f(x) and ∇f~()∇ f(x) disagree in sign, and rotational invariance implies this probability depends only on their relative orientation. This is exactly where the arccosine term in (11) comes from.