Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

arXiv:2610.17382v1 [cs.LG] 12 Oct 2026

M ITIGATING B LACK -B OX S CORE -BASED Q UERY ATTACKS VIA G RADIENT C ONFUSION

Ali Javeri Javad Hezareh Radin Shahdaei AmirMahdi Sadeghzadeh∗ Department of Computer Engineering, Sharif University of Technology Tehran, Iran ali.javeri78@sharif.edu javad.hezareh@sharif.edu radin.shahdaei01@sharif.edu sadeghzadeh@sharif.edu

A BSTRACT 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., ∗

Corresponding author

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

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 scorebased 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 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, 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 ) 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 2

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

threats, defenses commonly aim to disrupt the attacker’s ability to recover stable gradients from outputs, typically via randomization or output/logit manipulation. AAA (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]𝑑 be the input space, and let [𝐾] = {1, … , 𝐾} denote the label set. A classifier  ∶  → Δ𝐾 outputs a probability ∑ vector (𝐱) = 𝜎(𝐳(𝐱)), where 𝐳(𝐱) denotes the logits and 𝜎 is the softmax function. Here, Δ𝐾 = {𝐩 ∈ ℝ𝐾 ∣ 𝑖 𝐩𝑖 = 1} denotes the probability simplex. Let 𝑘 ∈ [𝐾] denote the true label of input 𝐱. For simplicity, we denote 𝐲̂ ∶= (𝐱). Attacks and perturbations. An adversarial example 𝐱adv for a sample 𝐱 with corresponding label 𝑘 is generated by adding a perturbation 𝜹 to 𝐱. Typically, the norm of the perturbation 𝜹 is bounded so as not to change the ground-truth label of 𝐱. Formally, an adversarial example is defined as 𝐱adv = 𝐱 + 𝜹, such that ‖𝐱adv − 𝐱‖𝑝 ≤ 𝑅, where 𝑅 is the perturbation budget, and the classifier  misclassifies 𝐱adv (untargeted attack: arg max𝑖 (𝐱adv )𝑖 ≠ 𝑘) or predicts a target class 𝑡 (targeted attack: arg max𝑖 (𝐱adv )𝑖 = 𝑡). 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 𝑄 that bounds the number of query the adversary can perform. Each query returns either (i) a score or probability vector (score-based setting) or (ii) 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 (𝐱), 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): 𝑓 (𝐱) ∶= (𝐱)𝑖 − (𝐱)𝑗 ,

(1)

where 𝑖 and 𝑗 denote the indices of the largest and second-largest components of the probability vector (𝐱), respectively. Decreasing 𝑓 (𝐱) encourages the top prediction (typically the correct label) to lose confidence relative to its strongest competitor. There are two common approaches for minimizing 𝑓 (𝐱): 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, ∇𝐱 𝑓 (𝐱), so as to decrease the adversarial loss. Since the attacker cannot directly access the model’s parameters or the gradient ∇𝐱 𝑓 (𝐱), 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 𝑚 ∑ 𝑓 (𝐱 + 𝜇𝐮𝑖 ) − 𝑓 (𝐱) ̂ 𝐱 𝑓𝜇 (𝐱) ∶= 1 ∇ 𝐮𝑖 , 𝑚 𝑖=1 𝜇

(2)

where 𝐮𝑖 ∼  (𝟎, 𝐈) and 𝜇 > 0 is a small smoothing parameter. In this setup, the adversary queries the model at points in a neighborhood around the input 𝐱. As a result, they effectively observe a Gaussian-smoothed version of the loss ̂ 𝐱 𝑓𝜇 (𝐱) function, denoted by 𝑓𝜇 (𝐱). The attacker then performs Projected Gradient Descent (PGD) steps based on ∇ while respecting the input perturbation constraint: ( ) ̂ 𝐱 𝑓𝜇 (𝐱𝑡 ) , 𝐱𝑡+1 = Π𝑅 𝐱𝑡 − 𝜂𝑡 ∇ (3) where 𝜂𝑡 is step size at iteration t, and Π𝜉 denotes projection onto the 𝓁𝑝 -ball of radius 𝑅, i.e., ‖𝐱′ − 𝐱‖𝑝 ≤ 𝑅. 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. 3

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

Random-search. Random search is an iterative method for minimizing the adversarial loss function. Let 𝜇 > 0 denote the step size (i.e., the perturbation magnitude used by the search rule). At iteration 𝑡, given the current iterate 𝐱𝑡 , the attacker samples a search direction 𝐮𝑡 ∼  from a predefined distribution (e.g., Gaussian directions or structured perturbations), and evaluates the candidate 𝐱𝑡 + 𝜇𝐮𝑡 . If this perturbation decreases the adversarial loss 𝑓 (⋅) in (1), the attacker updates 𝐱𝑡+1 ← 𝐱𝑡 + 𝜇𝐮𝑡 ; otherwise, 𝐱𝑡+1 ← 𝐱𝑡 . 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 𝑓 (𝐱), the one-step improvement signal is defined as ℎ𝑡 ∶= 𝑓 (𝐱𝑡 + 𝜇𝐮𝑡 ) − 𝑓 (𝐱𝑡 ).

(4)

If ℎ𝑡 < 0, then moving along 𝐮𝑡 decreases the loss and is therefore considered a useful attack direction. Accordingly, the accepted update is given by ( ( ) ) 𝐱𝑡+1 = Π𝜉 𝐱𝑡 + 𝕀 ℎ𝑡 < 0 ⋅ 𝜇𝐮𝑡 , (5) where 𝕀(⋅) denotes the indicator function.

4

Gradient Confusion Defense (GCD)

In score-based black-box attacks, the adversary minimizes the loss 𝑓 (𝐱) in (1) using only the model output 𝐲̂ ∈ Δ𝐾 . ̂ increasing Gradient Confusion Defense (GCD) disrupts this process by returning a modified output 𝐲̃ ∈ Δ𝐾 instead of 𝐲, the number of queries needed to succeed (potentially exceeding the budget 𝑄). GCD constructs 𝐲̃ from  and 𝐲̂ while ̃ 1 small and ensuring argmax𝑘 (𝐲̂ 𝑘 ) = argmax𝑘 (𝐲̃ 𝑘 ). For analysis, we introduce a preserving utility by keeping ‖𝐲̂ − 𝐲‖ ̃ ̃ ̃ hypothetical model  with 𝐲 = (𝐱) = 𝜎(̃𝐳(𝐱)), and drop the dependence on 𝐱 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: ̃ 𝑖 − (𝐱) ̃ 𝑗, 𝑓̃(𝐱) ∶= (𝐱) (6) ̃ where 𝑖 and 𝑗 denote the indices of the largest and second-largest components of the probability vector (𝐱), respectively. The gradient confusion solves the following minimization problem to compute 𝐲̃ : arg min ⟨∇𝐱 𝑓 (𝐱), ∇𝐱 𝑓̃(𝐱)⟩, 𝑦̃

s.t

̃ ‖(𝐱) − (𝐱)‖ 1 ≤𝜉

(7)

and 𝐲̃ ∈ Δ𝐾

where 𝜉 is the distortion budget. The GCD minimization problem addresses two objectives. (i) Confusion: Minimizing ⟨∇𝐱 𝑓 (𝐱), ∇𝐱 𝑓̃(𝐱)⟩ misaligns the adversary’s estimated gradient ∇𝐱 𝑓̃(𝐱) from the true gradient ∇𝐱 𝑓 (𝐱). This increases the query cost of gradient-estimation attacks and can mislead random-search attacks by flipping the sign of ℎ𝑡 . Theorems 4.3 and 4.4 in Section 4.1 provide theoretical support, and Section 5 validates GCD empirically. (ii) Utility: The ̃ ̃ ̂ − 𝐲‖ ̃ 1 ≤ 𝜉) keeps 𝐲̃ = (𝐱) constraint ||(𝐱) − (𝐱)|| close to 𝐲̂ = (𝐱), preserving 1 ≤ 𝜉 (equivalently ‖𝐲 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 𝑓̃, we define a randomized defended objective: 𝑓def (𝐱) ∶= 𝜆𝑓 (𝐱) + (1 − 𝜆)𝑓̃(𝐱),

𝜆 ∼ Bernoulli(𝑝),

(8)

where 𝜆 is drawn independently for each query. This theoretical model allows us to formalize the effect of 𝑓̃ on the optimization problem faced by the adversary. Under mild assumptions, we show that using 𝑓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 𝑝 → 0 maximizes this confusion effect. Assumption 4.1. The loss functions 𝑓 and 𝑓̃ are Lipschitz continuous with constants 𝐿0 (𝑓 ) and 𝐿0 (𝑓̃), respectively. Assumption 4.2. The loss functions 𝑓 and 𝑓̃ are smooth, meaning their gradients are Lipschitz continuous with constants 𝐿1 (𝑓 ) and 𝐿1 (𝑓̃), respectively. 4

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

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 𝑇 , 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 𝑓def rather than 𝑓 . Theorem 4.3. Suppose Assumption 4.1 holds. Consider zero-order optimization using the gradient estimator driven by 𝑓def , with smoothing parameter 𝜇 ≤ 𝜇 ∗ , for 𝑇 iterations and constant step size 𝜂𝑡 = 𝜂 ∗ . If, for all 𝐱 ∈ ℝ𝑑 , it holds that |𝑓 (𝐱) − 𝑓̃(𝐱)| ≤ 𝜖, where 𝜖 > 0 is a small constant, then the following bound holds: 𝑇 −1 −1 ] 1 − 𝑝 𝑇∑ [⟨ ⟩] 𝑝 ∑ [ 𝔼 ‖∇𝑓𝜇 (𝐱𝑡 )‖2 + 𝔼 ∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 ) 𝑇 𝑡=0 𝑇 𝑡=0 √ ( ) 𝐿0 (𝑓̃)2 4𝑑 3 𝐿0 (𝑓 )5 𝑅 𝜖2 ≤ 𝑝 + (1 − 𝑝) + 2𝑝(1 − 𝑝) . 𝜖′𝑇 𝐿0 (𝑓 )2 𝜖 ′2

(9)

Here, 𝑅 denotes the perturbation budget, 𝜖 ′ > 0 is a small constant ensuring that 𝑓𝜇 is close to 𝑓 , and the expectation is taken over the randomness of the optimization process up to iteration 𝑡. The detailed proof of Theorem 4.3 is provided in Appendix B. This theorem shows that incorporating the function 𝑓̃ into the optimization process can effectively perturb the optimization landscape and mislead the gradient estimates. In particular, by optimizing the confusion term ⟨∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 )⟩, we can increase the overall bound and thereby improve robustness against gradient estimation attacks. Implications of Theorem 4.3.

Let √ 𝐶(𝑝) =

4𝑑 3 𝐿0 (𝑓 )5 𝑅 𝜖′

) ( 𝐿 (𝑓̃)2 𝜖2 𝑝 + (1 − 𝑝) 0 2 + 2𝑝(1 − 𝑝) ′2 , 𝐿0 (𝑓 ) 𝜖

be a constant depending on 𝑝 and 𝐶(0) ≠ 0. Rearranging the bound in (9) as: 𝑇 −1 ] 𝐶(𝑝) 1 ∑ [ 𝔼 ‖∇𝑓𝜇 (𝐱𝑡 )‖2 ≤ √ 𝑇 𝑡=0 𝑝 𝑇 𝑇 −1 ] (1 − 𝑝) 1 ∑ [ − 𝔼 ⟨∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 )⟩ 𝑝 𝑇 𝑡=0

(10)

For adversary to succeed in optimization, they need to minimize the right hand side of the inequality below a certain threshold by increasing 𝑇 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 ⟨∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 )⟩ 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) 𝑇 to achieve the desired threshold, thus increasing the attack cost. Choosing 𝑝 → 0. We can further increase the bound in (10) by choosing 𝑝 close to 0. When 𝑝 → 0, the factor (1 − 𝑝)∕𝑝 amplifies the contribution of the confusion term. Therefore, if the defender enforces ⟨∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 )⟩ 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 𝑝 = 0, i.e., relying entirely on 𝑓̃ in the optimization process. 4.1.2

Search-Based Attacks

Random-search score-based attacks propose a direction 𝐮𝑡 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 𝑓def , which independently returns either 𝑓 or 𝑓̃; thus the two evaluations used to form the improvement from 𝐱𝑡 to 𝐱𝑡 + 𝜇𝐮𝑡 may come from different objectives. Let ℎdef ,𝑡 denote the improvement signal computed from the defender’s returned values. Because ℎdef,𝑡 can mix 𝑓 and 𝑓̃ across the two points, sign(ℎdef ,𝑡 ) can disagree with 5

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

sign(ℎ𝑡 ), 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 ∇𝑓 (𝐱) and ∇𝑓̃(𝐱), and (ii) a smoothness correction scaling with 𝜇 (vanishing as 𝜇 → 0 under Assumption 4.2). Theorem 4.4. Let Assumption 4.2 hold. Let 𝑑 ≥ 2 and 𝐮 ∼  (𝟎, 𝐈). Fix 𝐱 ∈ ℝ𝑑 and 𝜇 > 0. Define the true and defended one-step signals ℎ ∶= 𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱), Then

ℎdef ∶= 𝑓def (𝐱 + 𝜇𝐮) − 𝑓def (𝐱).

( ) ℙ sign(ℎ) ≠ sign(ℎdef ) ≥ ( ) [ ̃(𝐱)⟩ ⟨∇𝑓 (𝐱), ∇ 𝑓 1 arccos (1 − 𝑝)2 𝜋 ‖∇𝑓 (𝐱)‖ ‖∇𝑓̃(𝐱)‖ )] ( 𝐿1 (𝑓̃) 𝐿1 (𝑓 ) 𝜇𝑑 −√ + 2𝜋 ‖∇𝑓 (𝐱)‖ ‖∇𝑓̃(𝐱)‖

(11)

The proof of Theorem 4.4 is deferred to Appendix C. The event sign(ℎ) ≠ sign(ℎdef ) is exactly a one-step decision error: relative to the true objective 𝑓 , 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 ∇𝑓 (𝐱) and ∇𝑓̃(𝐱), up to a smoothness correction that decreases with the step size 𝜇. Consequently, designing 𝑓̃ so that ∇𝑓̃(𝐱) is strongly misaligned with ∇𝑓 (𝐱) 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 scorebased 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 𝑓̃ to remain close to 𝑓 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 𝐱, the target model produces logits 𝐳(𝐱) ∈ ℝ𝐾 and probability vector 𝐲̂ = 𝜎(𝐳(𝐱)) ∈ Δ𝐾 . We suppose that GCD returns a perturbed distribution 𝐲̃ = 𝜎(̃𝐳(𝐱)) ∈ Δ𝐾 . We ̃ ̃ ∈ Δ𝐾 . first focus on minimizing ⟨∇𝐱 𝑓 (𝐱), ∇𝐱 𝑓̃(𝐱)⟩, and then incorporate the constraints ‖(𝐱) − (𝐱)‖ 1 ≤ 𝜉 and 𝐲 Based on the chain rule, we can write the inner product as follows: ⟨ ⟩ arg min ∇𝐱 𝑓 (𝐱), ∇𝐱 𝑓̃(𝐱) 𝐲̃

= arg min 𝐲̃

⟨ ⟩ ∇𝐱 𝐳(𝐱) ∇𝐳 𝑓 (𝐳(𝐱)), ∇𝐱 𝐳̃ (𝐱) ∇𝐳̃ 𝑓̃(̃𝐳(𝐱)) .

(12)

Solving (12) exactly is difficult because 𝐲̃ = 𝜎(̃𝐳(𝐱)) appears inside the objective through 𝑓̃ and ∇𝐱 𝑓̃, so the optimal 𝐳̃ determines the gradient terms needed to optimize for 𝐳̃ (a circular chicken-and-egg dependency). Therefore, due to ̃ ̃ (𝐱) by 𝐳(𝐱) (i.e., 𝐳(𝐱) ≈ 𝐳̃ (𝐱)), which yields the constraint ‖(𝐱) − (𝐱)‖ 1 ≤ 𝜉, we use a local approximation of 𝐳 ∇𝐱 𝐳(𝐱) ≈ ∇𝐱 𝐳̃ (𝐱). Letting 𝐽 (𝐱) = ∇𝐱 𝐳(𝐱), our objective then approximately becomes: ⟨ ⟩ arg min ∇𝐱 𝑓 (𝐱), ∇𝐱 𝑓̃(𝐱) 𝐲̃

⟨ ⟩ ≈ arg min 𝐽 (𝐱) ∇𝐳 𝑓 (𝐳(𝐱)), 𝐽 (𝐱) ∇𝐳 𝑓̃(𝐳(𝐱)) .

(13)

𝐲̃

Our experiments show this surrogate delivers consistent improvements against query-based black-box attacks. The only derivative that is a function of 𝐲̃ is ∇𝐳 𝑓̃(𝐳(𝐱)). Let 𝐳𝑘 (𝐱) denote the 𝑘-th component of the perturbed logits vector 𝐳(𝐱). For the 𝑘-th component of ∇𝐳 𝑓̃(𝐳(𝐱)), we have ⎧𝐲̃ (1 − 𝐲̃ ) − (−𝐲̃ 𝐲̃ ), if 𝑘 = 𝑖, 𝑖 𝑗 𝑖 𝜕 𝑓̃(𝐳(𝐱)) ⎪ 𝑖 = ⎨−̃𝐲𝑖 𝐲̃ 𝑗 − 𝐲̃ 𝑗 (1 − 𝐲̃ 𝑗 ), if 𝑘 = 𝑗, 𝜕𝐳𝑘 (𝐱) ⎪−𝐲̃ 𝑖 𝐲̃ 𝑘 − (−𝐲̃ 𝑗 𝐲̃ 𝑘 ), if 𝑘 ≠ 𝑖, 𝑘 ≠ 𝑗. ⎩ 6

(14)

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

where 𝑖 = arg max𝑘 𝐲̃ 𝑘 (index of predicted class after defense), and 𝑗 = arg max𝑘≠𝑖 𝐲̃ 𝑘 (index of runner-up class after defense). Since we do not know the index of the predicted class and the runner-up class of 𝐲̃ before minimization, we use the index of the predicted class and the runner-up class of 𝐲̂ to construct ∇𝐳 𝑓̃(𝐳(𝐱)). Hence, 𝑖 = arg max𝑘 𝐲̂ 𝑘 and 𝑗 = arg max𝑘≠𝑖 𝐲̂ 𝑘 . The optimal solution for the minimization problem (13) with respect to ∇∗𝐳 𝑓̃(𝐳(𝐱)) is as follows: ∇∗𝐳 𝑓̃(𝐳(𝐱)) = −𝛼 𝐽 (𝐱)⊤ 𝐽 (𝐱) ∇𝐳 𝑓 (𝐳(𝐱)).

(15)

where 𝛼 → ∞. In our experiments, we found that the norm of ∇∗𝐳 𝑓̃(𝐳(𝐱)) is not important for the success of GCD. Thus, we choose 𝛼 = 1. Since we have 𝐽 (𝐱) and ∇𝐳 𝑓 (𝐳(𝐱)), we can compute ∇∗𝐳 𝑓̃(𝐳(𝐱)). Because the equation ̃ ∇𝐳 𝑓̃(𝐳(𝐱)) = ∇∗𝐳 𝑓̃(𝐳(𝐱)) with respect to 𝐲̃ is a nonlinear system, we cannot solve it directly to obtain 𝐲̃ = (𝐱). 𝐾 ̃ Moreover, the constraints ‖(𝐱) − (𝐱)‖1 ≤ 𝜉 and 𝐲̃ ∈ Δ must also be considered. ̃ To find 𝐲̃ , GCD employs a solution that (i) returns a valid probability vector 𝐲̃ ∈ Δ𝐾 , (ii) keeps 𝐲̃ = (𝐱) close to 𝐲̂ = (𝐱) to satisfy the utility constraint, and (iii) preserves the predicted label of the target model (arg max𝑘 𝐲̂ 𝑘 = arg max𝑘 𝐲̃ 𝑘 ). GCD solves the following minimization problem to obtain 𝐲̃ : ⟨ ⟩ arg min − ∇𝐳 𝑓̃(𝐳(𝐱)), ∇∗𝐳 𝑓̃(𝐳(𝐱)) 𝐲̃ (16) ̃ s.t. ‖(𝐱) − (𝐱)‖ 1 ≤ 𝜉. The inner product in (16) encourages ∇𝐳 𝑓̃(𝐳(𝐱)) to align with ∇∗𝐳 𝑓̃(𝐳(𝐱)) as much as possible, subject to the constraint ̃ ̃ is normalized by dividing by its ‖(𝐱) − (𝐱)‖ 1 ≤ 𝜉. After solving the minimization problem in (16), the resulting 𝐲 sum to ensure that 𝐲̃ ∈ Δ𝐾 . 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 ̂ which reduces the accuracy of the target model. To address this component of the resulting 𝐲̃ differs from that of 𝐲, issue, GCD manually adjusts 𝐲̃ . Let 𝑖 = arg max𝑘 𝐲̂ 𝑘 and 𝑗 = arg max𝑘 𝐲̃ 𝑘 . If 𝑖 ≠ 𝑗, GCD adds 𝐲̃ 𝑗 − 𝐲̃ 𝑖 to 𝐲̃ 𝑖 and subtracts it from 𝐲̃ 𝑗 . This guarantees that arg max𝑘 𝐲̂ 𝑘 = arg max𝑘 𝐲̃ 𝑘 , 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 𝑁 = 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 to input images. Boundary Defense (oRND) (Aithal and Li, 2022) adds Gaussian noise with 𝜎 = 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]. For Adaptive Attack on Attackers (AAA), we implement AAA-sine (Chen et al., 2022) with temperature 1, deviation 0.5, attractor interval 4, calibration weight 5, learning rate 0.1, and 100 inner iterations. We only test AAA-sine, following Chen et al. (2022) which showed AAA-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. Since the dimension of 𝐲̃ 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  of 20 indices of 𝐲̃ and optimize Equation (16) only over these components, while fixing ̂ To construct , we use ∇∗𝐳 𝑓̃(𝐳(𝐱)) and select the the remaining components of 𝐲̃ to their corresponding values in 𝐲. 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 𝐲̃ differs from 𝐲̂ 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 and 𝓁∞ variants), BrusleAttack (Vo et al., 2024) (𝓁0 variant), 7

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

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

None iRND oRND ResNet-18 RLS AAA GCD

1% 0.6% 0% 0.1% 0%

Bandit-𝓁∞

Square-𝓁2

Square-𝓁∞

Sign-𝓁∞

BrusLe-𝓁0

82.68% / 545.68 98.03% / 186.16 87.76% / 466.29 99.38% / 112.46 98.97% / 230.05 79.78% / 234.82 11.63% / 333.97 41.47% / 186.49 24.92% / 290.21 80.52% / 178.96 66.49% / 233.48 82.9% / 220.76 12.53% / 354.43 47.70% / 158.43 20.98% / 188.31 64.09% / 113.92 38.83% / 170.05 68.6% / 201.10 04.15% / 345.9 25.11% / 23.96 12.76% / 268.69 47.31% / 90.88 21.06% / 111.41 51.77% / 316.57 03.33% / 318 38.08% / 132.26 9.77% / 174.91 43.41% / 82.04 32.09% / 177.10 66.78% / 290.17 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

Bandit-𝓁∞

Square-𝓁2

Square-𝓁∞

Sign-𝓁∞

None iRND oRND ResNet-50 RLS AAA GCD

0.2% 1.7% 0% 0.3% 0%

46.73% / 761.22 87.05% / 251.79 81.45% / 483.65 99.47% / 133.90 91.33% / 328.71 11.02% / 440.30 45.56% / 141.79 26.66% / 214.17 83.49% / 126.10 60.78% / 229.78 51.47% / 229.94 75.95% / 103.83 59.84% / 208.49 83.52% / 96.91 69.47% / 182.20 6.68% / 618.42 47.80% / 143.72 16.29% / 143.03 59.82% / 104.07 21.37% / 109.13 11.80% / 356.96 37.94% / 85.10 15.69% / 32.05 47.06% / 33.59 23.6% / 109.37 3.34% / 528.6 35.65% / 103.29 13.22% / 64.05 47.94% / 32.17 20.17% / 90.15

None iRND oRND ViT-B/16 RLS AAA GCD

0.2% 1.8% 0% 0% 0%

38.17% / 801.41 76.46% / 319.75 70.64% / 566.65 97.90% / 351.15 80.05% / 597.98 7.78% / 471.24 25.13% / 169.19 21.77% / 287.48 61.70% / 252.02 38% / 255.65 46.71% / 266.73 69.17% / 191.07 58.88% / 291.56 97.32% / 84.39 81.44% / 313.67 4.47% / 589.5 28.51% / 224.63 10.29% / 148.42 30.36% / 144.31 13.39% / 184.20 8.17% / 300.13 22.28% / 102.86 10.9% / 43.72 26.74% / 92.46 15.1% / 236.60 3.35% / 609 21.94% / 140.03 12.38% / 455.74 33.83% / 257.21 21.44% / 315.70

SignAttack (Al-Dujaili and O’Reilly, 2020) (𝓁∞ variant), and SquareAttack (Andriushchenko et al., 2020) (𝓁2 and 𝓁∞ variants). For CIFAR-10, inputs are scaled to [0, 255] with 𝓁∞ budget 𝜖 = 12.75 (0.05 normalized) and 𝓁2 budget 𝜖 = 255 (1.0 normalized). For ImageNet, inputs are in [0, 1] with 𝓁∞ budget 𝜖 = 0.05, and 𝓁2 budgets follow the original implementations (Bandit: 𝜖 = 1275, Square: 𝜖 = 5). All attacks are constrained by a maximum query budget of 𝑄 = 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. 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 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. AAA and RLS preserve accuracy and can be competitive, but are more vulnerable to adaptive attacks (Section 5.3). Table 3 reports 𝓁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. 8

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

Table 3: 𝓁1 distance between the original output of the model 𝑦̂ and defense output 𝑦̃ for 1000 ImageNet samples. Defense

Min 𝓁1

Avg 𝓁1

Max 𝓁1

iRND oRND RLS AAA GCD

0.00 0.00 0.00 0.00 0.07

0.11 0.26 0.33 0.28 0.58

1.03 1.77 1.74 1.60 1.25

84.4° 68.9°

90° 120°

60°

150°

180°

0

30

60

90°

51.7° 49.0° 49.4° 47.4° 46.8° 36.0° 29.9° 30°24.5°

90 120 150

0°

60°

120°

150°

30°

180°

0

(a) GCD

40

80 120 160 200

60°

150°

30°

0.0° 0.0° 180°

0°

0

(b) AAA

0

1

2

3

66.5° 58.4° 55.4° 55.9°

90°

120°

Sample 4 5

40

80 120 160 200

0.5° 0.0° 0.0°

0°

(c) RLS

6

7

8

9

Figure 1: Polar histograms of gradient direction misalignment. For 10 randomly selected samples from the ImageNet test set, we plot the angular deviation 𝜃 = ∠(∇𝐱 𝑓 (𝐱), ∇𝐱 𝑓̃(𝐱)) between the direction ∇𝐱 𝑓̃(𝐱) induced by the defended score responses (i.e., the direction the attacker would follow) and the true loss gradient ∇𝐱 𝑓 (𝐱). 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 𝜃 = ∠(∇𝐱 𝑓 (𝐱), ∇𝐱 𝑓̃(𝐱)), the deviation between the true loss gradient ∇𝐱 𝑓 (𝐱) and the gradient ∇𝐱 𝑓̃(𝐱) 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◦ –84.4◦ , many near ∼ 50◦ ), whereas AAA concentrates at 𝜃 ≈ 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◦ . We hypothesize this occurs because the RLS transform maps some target-model output probability vectors to one-hot vectors, making ∇𝐱 𝑓̃(𝐱) ≈ 0. As a result, GCD’s persistent misalignment compounds over iterations, increasing query complexity and reducing attack success, while defenses that often yield 𝜃 ≈ 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 𝑡 along the attack trajectory, we measure the angle 𝜃𝑡 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, AAA 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◦ –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◦ –28◦ , and many samples remaining in the 30◦ –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; AAA usually does not. This also explains the mechanism. AAA 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. 9

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

60

AAA sample traces (dashed) GCD sample traces (continuous) AAA vs Undefended (mean) GCD vs Undefended (mean)

Angular Deviation

50 40 30 20 10 0

20

40 60 Query Iterations

80

100

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 AAA. We incorporate two adaptive techniques—Expectation over Transformation (EOT) and Pendulum—into the Square Attack framework. For both adaptive variants, we set 𝑘 = 10 and evaluate performance on 1000 ImageNet samples using ViT-B/16. D EFENSE AAA RLS GCD

5.3

EOT

P EN -S QUARE

M AX (EOT,P EN )

21.94% / 85.44 36.19% / 215.83 24.04% / 159.69

40.53% / 306.08 23.55% / 85.44 30.12% / 209.33

40.53% 36.19% 30.12%

Adaptive Attack Evaluation

To assess defense resilience against adaptive adversaries, we evaluate GCD alongside AAA and RLS against two adaptive attacks: Expectation over Transformation (EOT) (Athalye et al., 2018b) and PendulumAttack (Dashtbani et al., 2026). For sample 𝐱, EOT counteracts random-based defenses by averaging over 𝑘 independently randomized defense ∑ ̃ (𝑖) ̂ outputs ( 𝑘1 𝑖=0 𝑘  ) to obtain an unbiased estimatimation of the 𝐲 = (𝐱). 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 AAA 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 AAA 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 AAA 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, AAA 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 10

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

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, M.B., Li, X., 2022. Boundary defense against black-box adversarial attacks, in: 26th International Conference on Pattern Recognition, ICPR 2022, Montreal, QC, Canada, August 21-25, 2022, IEEE. pp. 2349–2356. Al-Dujaili, A., O’Reilly, U., 2020. 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, OpenReview.net. Andriushchenko, M., Croce, F., Flammarion, N., Hein, M., 2020. Square attack: A query-efficient black-box adversarial attack via random search, in: Vedaldi, A., Bischof, H., Brox, T., Frahm, J. (Eds.), Computer Vision - ECCV 2020 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIII, Springer. pp. 484–501. Athalye, A., Carlini, N., Wagner, D.A., 2018a. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples, in: Dy, J.G., Krause, A. (Eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, PMLR. pp. 274–283. Athalye, A., Engstrom, L., Ilyas, A., Kwok, K., 2018b. Synthesizing robust adversarial examples, in: Dy, J.G., Krause, A. (Eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, PMLR. pp. 284–293. Carlini, N., Wagner, D.A., 2017. 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, IEEE Computer Society. pp. 39–57. Chen, J., Gu, Q., 2020. Rays: A ray searching method for hard-label adversarial attack, in: Gupta, R., Liu, Y., Tang, J., Prakash, B.A. (Eds.), KDD ’20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, ACM. pp. 1739–1747. Chen, J., Jordan, M.I., Wainwright, M.J., 2020. 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, IEEE. pp. 1277–1294. Chen, P., Zhang, H., Sharma, Y., Yi, J., Hsieh, C., 2017. ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models, in: Thuraisingham, B., Biggio, B., Freeman, D.M., Miller, B., Sinha, A. (Eds.), Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec@CCS 2017, Dallas, TX, USA, November 3, 2017, ACM. pp. 15–26. Chen, S., Huang, Z., Tao, Q., Wu, Y., Xie, C., Huang, X., 2022. Adversarial attack on attackers: Post-process to mitigate black-box score-based query attacks, in: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (Eds.), 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. Cheng, M., Singh, S., Chen, P.H., Chen, P., Liu, S., Hsieh, C., 2020. 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, OpenReview.net. Conn, A.R., Gould, N.I.M., Toint, P.L., 2000. Trust Region Methods. MOS-SIAM Series on Optimization, SIAM. Dashtbani, H., Gandomani, M.D., Sadeghzadeh, A., 2026. Random logit scaling: Defending deep neural networks against black-box score-based adversarial example attacks. Transactions on Machine Learning Research 2026. Goodfellow, I.J., Shlens, J., Szegedy, C., 2015. Explaining and harnessing adversarial examples, in: Bengio, Y., LeCun, Y. (Eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. Guo, C., Gardner, J.R., You, Y., Wilson, A.G., Weinberger, K.Q., 2019. Simple black-box adversarial attacks, in: Chaudhuri, K., Salakhutdinov, R. (Eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, PMLR. pp. 2484–2493. 11

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

He, Z., Rakin, A.S., Fan, D., 2019. 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, Computer Vision Foundation / IEEE. pp. 588–597. Hung-Quang, N., Lao, Y., Pham, T., Wong, K., Doan, K.D., 2024. 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, OpenReview.net. Ilyas, A., Engstrom, L., Athalye, A., Lin, J., 2018. Black-box adversarial attacks with limited queries and information, in: Dy, J.G., Krause, A. (Eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, PMLR. pp. 2142–2151. Ilyas, A., Engstrom, L., Madry, A., 2019. 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, OpenReview.net. Liu, X., Cheng, M., Zhang, H., Hsieh, C., 2018. Towards robust neural networks via random self-ensemble, in: Ferrari, V., Hebert, M., Sminchisescu, C., Weiss, Y. (Eds.), Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part VII, Springer. pp. 381–397. Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A., 2018. 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. Meckes, E., 2012. Approximation of projections of random vectors. Journal of Theoretical Probability 25, 333–352. doi:10.1007/s10959-010-0299-2. Moosavi-Dezfooli, S., Fawzi, A., Frossard, P., 2016. 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, IEEE Computer Society. pp. 2574–2582. Nesterov, Y.E., Spokoiny, V.G., 2017. Random gradient-free minimization of convex functions. Found. Comput. Math. 17, 527–566. URL: https://doi.org/10.1007/s10208-015-9296-2, doi:10.1007/S10208-015-9296-2. Papernot, N., McDaniel, P.D., Goodfellow, I.J., Jha, S., Celik, Z.B., Swami, A., 2017. Practical black-box attacks against machine learning, in: Karri, R., Sinanoglu, O., Sadeghi, A., Yi, X. (Eds.), Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS 2017, Abu Dhabi, United Arab Emirates, April 2-6, 2017, ACM. pp. 506–519. Qin, Z., Fan, Y., Zha, H., Wu, B., 2021. Random noise defense against query-based black-box attacks, in: Ranzato, M., Beygelzimer, A., Dauphin, Y.N., Liang, P., Vaughan, J.W. (Eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 7650–7663. Rebuffi, S., Gowal, S., Calian, D.A., Stimberg, F., Wiles, O., Mann, T.A., 2021. Data augmentation can improve robustness, in: Ranzato, M., Beygelzimer, A., Dauphin, Y.N., Liang, P., Vaughan, J.W. (Eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 29935–29948. Reza, M.F., Jin, R., Wu, T., Dai, H., 2025. GSBAK: top-k geometric score-based black-box attack, in: The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025, OpenReview.net. Reza, M.F., Rahmati, A., Wu, T., Dai, H., 2023. CGBA: curvature-aware geometric black-box attack, in: IEEE/CVF International Conference on Computer Vision, ICCV 2023, Paris, France, October 1-6, 2023, IEEE. pp. 124–133. Rice, L., Wong, E., Kolter, J.Z., 2020. Overfitting in adversarially robust deep learning, in: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, PMLR. pp. 8093–8104. Salman, H., Li, J., Razenshteyn, I.P., Zhang, P., Zhang, H., Bubeck, S., Yang, G., 2019. Provably robust deep learning via adversarially trained smoothed classifiers, in: Wallach, H.M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E.B., Garnett, R. (Eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 11289–11300. Salman, H., Sun, M., Yang, G., Kapoor, A., Kolter, J.Z., 2020. Denoised smoothing: A provable defense for pretrained classifiers, in: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (Eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual. 12

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I.J., Fergus, R., 2014. Intriguing properties of neural networks, in: Bengio, Y., LeCun, Y. (Eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings. Tramèr, F., Kurakin, A., Papernot, N., Goodfellow, I.J., Boneh, D., McDaniel, P.D., 2018. 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, OpenReview.net. Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A.R.J., Jones, E., Kern, R., Larson, E., Carey, C., Polat, I., Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P., SciPy, 2019. Scipy 1.0-fundamental algorithms for scientific computing in python. CoRR abs/1907.10121. arXiv:1907.10121. Vo, V.Q., Abbasnejad, E., Ranasinghe, D., 2024. 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, OpenReview.net. Wang, D., Ju, A., Shelhamer, E., Wagner, D.A., Darrell, T., 2021. Fighting gradients with gradients: Dynamic defenses against adversarial attacks. CoRR abs/2105.08714. arXiv:2105.08714. Xie, C., Wang, J., Zhang, Z., Ren, Z., Yuille, A.L., 2018. 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, OpenReview.net.

13

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

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

 𝑑 [𝐾]  𝐳(𝐱) 𝜎(⋅) Δ𝐾 ̂ (𝐱) 𝐲, 𝑘 𝐽 (𝐱)

Input space,  ⊆ [0, 1]𝑑 Dimension of the input space Label set {1, … , 𝐾} Classifier mapping  → Δ𝐾 Logits vector output by the model for input 𝐱 Softmax function ∑ Probability simplex {𝐩 ∈ ℝ𝐾 ∣ 𝑖 𝐩𝑖 = 1} Original probability vector output by the target model True label of input 𝐱 Jacobian of the model’s logits with respect to the input, ∇𝐱 𝐳(𝐱) Attacks and Optimization

𝐱𝑎𝑑𝑣 𝑅 𝑄 𝑓 (𝐱) 𝑖, 𝑗 ̂ 𝐱 𝑓𝜇 (𝐱) ∇ 𝐮, 𝐮𝑡 𝜇 𝑓𝜇 (𝐱) 𝜂𝑡 Π𝜉 ℎ𝑡

Adversarial example (𝐱𝑎𝑑𝑣 = 𝐱 + 𝜹) Perturbation budget (radius of the allowed perturbation ball) Maximum query budget Adversarial loss function based on the original model output Indices of the largest and second-largest probability components Estimated gradient of the smoothed function Random search direction vector, 𝐮 ∼  (𝟎, 𝐈) Smoothing parameter (step size for finite differences) Gaussian-smoothed version of the loss function Step size (learning rate) at iteration 𝑡 Projection operator onto the 𝑙𝑝 -ball of radius 𝜉 One-step improvement signal in random search Gradient Confusion Defense (GCD)

̃ ̃ (𝐱) 𝐲, 𝐳̃ (𝐱) 𝑓̃(𝐱) 𝜉 𝑓def (𝐱) 𝜆 𝑝

Modified/Defended probability vector returned to the user Perturbed logits corresponding to 𝐲̃ Adversarial loss function based on the modified output 𝐲̃ Distortion budget (constraint on 𝑙1 distance between 𝐲̂ and 𝐲̃ ) Randomized defended objective function (theoretical model) Bernoulli random variable used in the theoretical switching defense Probability parameter for the Bernoulli distribution (𝜆 ∼ Bernoulli(𝑝)) Theoretical Analysis

𝐿0 (𝑓 ) 𝐿1 (𝑓 ) 𝑇 𝜖 𝜖′ ℎdef

Lipschitz continuity constant of function 𝑓 Lipschitz constant of the gradient (smoothness constant) of 𝑓 Total number of optimization steps/queries Small constants bounding the difference between functions (|𝑓 − 𝑓̃|) Small constants bounding the difference between functions (|𝑓𝜇 − 𝑓 |) Improvement signal computed from the defender’s returned values

14

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

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 𝑓̃, which is close to the original function 𝑓 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 𝑓 ∶ ℝ𝑑 → ℝ, we define its 𝜇-Gaussian smoothed version as: 𝑓𝜇 (𝐱) = 𝔼𝐮∼ (𝟎,𝐈𝐝 ) [𝑓 (𝐱 + 𝜇𝐮)]

(17)

𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱) 𝐮, 𝜇

(18)

Now, we define the gradient estimator as 𝑔𝜇 (𝐱) =

where 𝐮 ∼  (𝟎, 𝐈𝑑 ). Using the change of variables 𝐲 ∶= 𝐱 + 𝜇𝐮, we can show that the gradient of the smoothed function can be written as ( ) 1 2 1 ∇𝑓𝜇 (𝐱) = ∇ 𝑓 (𝐱 + 𝜇𝐮)𝑒− 2 ‖𝐮‖ 𝑑𝐮 (2𝜋)𝑑∕2 ∫ ( ) − 1 ‖𝐲−𝐱‖2 1 =∇ 𝑓 (𝐲)𝑒 2𝜇2 𝑑𝐲 (Change of variables) 𝜇 𝑑+1 (2𝜋)𝑑∕2 ∫ ( ) − 1 ‖𝐲−𝐱‖2 𝐲−𝐱 1 𝑑𝐲 = 𝑓 (𝐲) − 𝑒 2𝜇2 𝜇2 𝜇 𝑑+1 (2𝜋)𝑑∕2 ∫ ) ( 𝜇𝐮 − 1 ‖𝐮‖2 𝑑 1 = 𝜇 𝑑𝐮 (Change of variables) 𝑒 2 𝑓 (𝐱 + 𝜇𝐮) − 𝜇2 𝜇 𝑑+1 (2𝜋)𝑑∕2 ∫ (19) ( ) 1 2 1 𝐮 = 𝑓 (𝐱 + 𝜇𝐮) − 𝑒− 2 ‖𝐮‖ 𝑑𝐮 𝑑∕2 ∫ 𝜇 (2𝜋) [ ] ( [ ] ) 𝑓 (𝐱 + 𝜇𝐮) 𝑓 (𝐱) = 𝔼𝐮∼ (𝟎,𝐈𝐝 ) 𝐮 𝔼𝐮∼ (𝟎,𝐈𝐝 ) 𝐮 =0 𝜇 𝜇 [ ] 𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱) = 𝔼𝐮∼ (𝟎,𝐈𝐝 ) 𝐮 𝜇 = 𝔼𝐮∼ (𝟎,𝐈𝐝 ) [𝑔𝜇 (𝐱)] Thus, we have the following lemma: Lemma B.2. The gradient estimator 𝑔𝜇 (𝐱) is an unbiased estimator of the gradient of the smoothed function 𝑓𝜇 (𝐱), i.e., [ ] 𝔼𝐮 𝑔𝜇 (𝐱) = ∇𝑓𝜇 (𝐱). We also use the following lemma on the smoothness of the Gaussian-smoothed function from Nesterov and Spokoiny (2017): Lemma B.3. If 𝑓 is 𝐿0 (𝑓 )-Lipschitz continuous, then its smoothed version 𝑓𝜇 is differentiable and has a Lipschitz continuous gradient with constant √ 2 𝑑 𝐿1 (𝑓𝜇 ) = 𝐿0 (𝑓 ). 𝜇 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 𝐮 ∼  (𝟎, 𝐈𝑑 ), we have [ ] 𝔼 ‖𝐮‖2 ≤ 𝑑, (20) and [ ] 𝔼 ‖𝐮‖4 ≤ (𝑑 + 4)2 . (21) 15

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

B.2

Bias and variance of gradient estimator

Let 𝑓 ∶ ℝ𝑑 → ℝ and 𝑓̃ ∶ ℝ𝑑 → ℝ be two functions such that, for all 𝐱 ∈ ℝ𝑑 , |𝑓 (𝐱) − 𝑓̃(𝐱)| ≤ 𝜖. We define a randomized objective ℎ as ℎ(𝐱) = 𝜆𝑓 (𝐱) + (1 − 𝜆)𝑓̃(𝐱), (22) where 𝜆 ∼ Bernoulli(𝑝). Thus, the corresponding gradient estimator is given by ( ) ( ) 𝜆1 𝑓 (𝐱 + 𝜇𝐮) + (1 − 𝜆1 )𝑓̃(𝐱 + 𝜇𝐮) − 𝜆2 𝑓 (𝐱) + (1 − 𝜆2 )𝑓̃(𝐱) 𝑔𝜇 (𝐱) = 𝐮 𝜇 (23) [ ] 𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱) 𝑓̃(𝐱 + 𝜇𝐮) − 𝑓̃(𝐱) (𝜆1 − 𝜆2 )(𝑓 (𝐱) − 𝑓̃(𝐱)) = 𝜆1 + (1 − 𝜆1 ) + 𝐮 𝜇 𝜇 𝜇 Thus, for the expectation of the gradient estimator, we have: ( ) ( ) 𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱) 𝑓̃(𝐱 + 𝜇𝐮) − 𝑓̃(𝐱) 𝔼𝜆1 ,𝜆2 [𝑔𝜇 (𝐱)] = 𝑝 𝐮 + (1 − 𝑝) 𝐮 𝜇 𝜇 From lemma B.2 we have:

𝔼𝐮,𝜆1 ,𝜆2 [𝑔𝜇 (𝐱)] = 𝑝∇𝑓𝜇 (𝐱) + (1 − 𝑝)∇𝑓̃𝜇 (𝐱)

(24)

(25)

Now we need to compute the variance of the gradient estimator: [ ]2 𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱) 𝑓̃(𝐱 + 𝜇𝐮) − 𝑓̃(𝐱) (𝜆1 − 𝜆2 )(𝑓 (𝐱) − 𝑓̃(𝐱)) 2 ‖𝑔𝜇 (𝐱)‖ = 𝜆1 + (1 − 𝜆1 ) + ‖𝐮‖2 𝜇 𝜇 𝜇 ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟

(26)

𝐴 ̃ ̃ (𝐱) 𝑓̃(𝐱) Now set 𝛼 = 𝑓 (𝐱+𝜇𝐮)−𝑓 , 𝛼̃ = 𝑓 (𝐱+𝜇𝐮)− , and 𝛿 = 𝑓 (𝐱)−𝜇 𝑓 (𝐱) . Thus for 𝐴 we have: 𝜇 𝜇

𝐴 = 𝜆21 𝛼 2 + (1 − 𝜆1 )2 𝛼̃ 2 + (𝜆1 − 𝜆2 )2 𝛿 2 + 2𝜆1 (1 − 𝜆1 )𝛼 𝛼̃ + 2𝜆1 (𝜆1 − 𝜆2 )𝛼𝛿 + 2(1 − 𝜆1 )(𝜆1 − 𝜆2 )𝛼𝛿 ̃ ⟹ 𝔼𝜆1 ,𝜆2 [𝐴] = 𝑝𝛼 2 + (1 − 𝑝)𝛼̃ 2 + 2𝑝(1 − 𝑝)(𝛼 − 𝛼)𝛿 ̃ + 2𝑝(1 − 𝑝)𝛿 2 = 𝑝𝛼 2 + (1 − 𝑝)𝛼̃ 2 + 2𝑝(1 − 𝑝)(𝛼 − 𝛼̃ + 𝛿)𝛿 (27)

(

)2 ( )2 𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱) 𝑓̃(𝐱 + 𝜇𝐮) − 𝑓̃(𝐱) 𝔼𝜆1 ,𝜆2 [𝐴] = 𝑝 + (1 − 𝑝) 𝜇 𝜇 )( ) 2𝑝(1 − 𝑝) ( 𝑓 (𝐱 + 𝜇𝐮) − 𝑓̃(𝐱 + 𝜇𝐮) 𝑓 (𝐱) − 𝑓̃(𝐱) + 𝜇2 Now using the bound |𝑓 (𝐱) − 𝑓̃(𝐱)| ≤ 𝜖, and Lipschitz continuity of 𝑓 and 𝑓̃, we have: 𝔼𝜆1 ,𝜆2 [𝐴] ≤ 𝑝𝐿20 (𝑓 )‖𝐮‖2 + (1 − 𝑝)𝐿20 (𝑓̃)‖𝐮‖2 +

2𝑝(1 − 𝑝)𝜖 2 𝜇2

(28)

Putting this into equation 26, we have: 2

2𝑝(1 − 𝑝)𝜖 𝔼𝜆1 ,𝜆2 [‖𝑔𝜇 (𝐱)‖2 ] ≤ 𝑝𝐿20 (𝑓 )‖𝐮‖4 + (1 − 𝑝)𝐿20 (𝑓̃)‖𝐮‖4 + ‖𝐮‖2 𝜇2

(29)

Now taking expectation over 𝐮, using lemma B.4 we have: 2

2𝑝(1 − 𝑝)𝜖 𝔼𝐮,𝜆1 ,𝜆2 [‖𝑔𝜇 (𝐱)‖2 ] ≤ 𝑝𝐿20 (𝑓 )(𝑑 + 4)2 + (1 − 𝑝)𝐿20 (𝑓̃)(𝑑 + 4)2 + 𝑑 𝜇2 B.3

(30)

Descent Lemma

We now define the optimization process. Starting from 𝐱0 , at each iteration 𝑡 we sample 𝜆(𝑡) , 𝜆(𝑡) ∼ Bernoulli(𝑝) and 1 2 𝐮(𝑡) ∼  (𝟎, 𝐈𝑑 ), and compute the gradient estimator 𝑔𝜇 (𝐱𝑡 ). We then update the iterate as 𝐱𝑡+1 = 𝐱𝑡 − 𝜂𝑡 𝑔𝜇 (𝐱𝑡 ), 16

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

where 𝜂𝑡 denotes the step size at iteration 𝑡. Consequently, each iterate 𝐱𝑡 is a random variable that depends on all previous samples {𝜆(𝑖) , 𝜆(𝑖) , 𝐮(𝑖) }𝑖<𝑡 . We define the history up to iteration 𝑡 as 1 2 { } (𝑖) (𝑖) 𝑡 = 𝜆(𝑖) , 𝜆 , 𝐮 . 1 2 𝑖<𝑡

Our goal is to analyze the convergence of this process in expectation over all sources of randomness. We assume the process is run for 𝑇 iterations. Having access to the variance and bias of the gradient estimator, we can now use the standard descent lemma for zero order optimization. 𝐿1 (𝑓𝜇 ) 2 𝑓𝜇 (𝐱𝑡+1 ) ≤ 𝑓𝜇 (𝐱𝑡 ) − 𝜂𝑡 ⟨∇𝑓𝜇 (𝐱𝑡 ), 𝑔𝜇 (𝐱𝑡 )⟩ + 𝜂𝑡 ‖𝑔𝜇 (𝐱𝑡 )‖2 (31) 2 Using equations 25 and 30, and taking expectation over 𝜆(𝑡) , 𝜆(𝑡) and 𝐮(𝑡) we have: 1 2 𝔼𝐮(𝑡) ,𝜆(𝑡) ,𝜆(𝑡) [𝑓𝜇 (𝐱𝑡+1 )] ≤ 𝑓𝜇 (𝐱𝑡 ) − 𝜂𝑡 𝑝‖∇𝑓𝜇 (𝐱𝑡 )‖2 − 𝜂𝑡 (1 − 𝑝)⟨∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 )⟩ 1

2

( ) 𝐿1 (𝑓𝜇 ) 2 2𝑝(1 − 𝑝)𝜖 2 2 2 2 ̃ 2 + 𝜂𝑡 𝑝𝐿0 (𝑓 )(𝑑 + 4) + (1 − 𝑝)𝐿0 (𝑓 )(𝑑 + 4) + 𝑑 2 𝜇2

(32)

Now taking expectation over the history 𝑡 , we have: 𝔼 ,𝐮(𝑡) ,𝜆(𝑡) ,𝜆(𝑡) [𝑓𝜇 (𝐱𝑡+1 )] = 𝔼𝑡+1 [𝑓𝜇 (𝐱𝑡+1 )] 𝑡

1

2

≤ 𝔼𝑡 [𝑓𝜇 (𝐱𝑡 )] − 𝜂𝑡 𝑝𝔼𝑡 [‖∇𝑓𝜇 (𝐱𝑡 )‖2 ] − 𝜂𝑡 (1 − 𝑝)𝔼𝑡 [⟨∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 )⟩] (

+

𝐿1 (𝑓𝜇 ) 2 𝜂𝑡 𝑝𝐿20 (𝑓 )(𝑑 + 4)2 + (1 − 𝑝)𝐿20 (𝑓̃)(𝑑 + 4)2 + 2

2𝑝(1 − 𝑝)𝜖 2 𝜇2

)

(33)

𝑑

Let’s define new notations for simplicity: ⎧𝐴 = 𝔼 [𝑓 (𝐱 )] 𝑡 𝜇 𝑡 ⎪ 𝑡 2 ⎪𝐵𝑡 = 𝔼𝑡 [‖∇𝑓𝜇 (𝐱𝑡 )‖ ] ⎨𝐶 = 𝔼 [⟨∇𝑓 (𝐱 ), ∇𝑓̃ (𝐱 )⟩] 𝑡 𝜇 𝑡 𝜇 𝑡 ⎪ 𝑡 2 ⎪𝐷 = 𝑝𝐿20 (𝑓 )(𝑑 + 4)2 + (1 − 𝑝)𝐿20 (𝑓̃)(𝑑 + 4)2 + 2𝑝(1−𝑝)𝜖 𝑑 2 𝜇 ⎩

(34)

Rewrite the inequality with new notations: 𝐴𝑡+1 ≤ 𝐴𝑡 − 𝜂𝑡 𝑝𝐵𝑡 − 𝜂𝑡 (1 − 𝑝)𝐶𝑡 +

𝐿1 (𝑓𝜇 ) 2 𝜂𝑡 𝐷 2

(35)

𝐿1 (𝑓𝜇 ) 2 𝜂𝑡 𝐷 2

(36)

Rearranging the terms, we have: 𝐴𝑡+1 − 𝐴𝑡 ≤ −𝜂𝑡 𝑝𝐵𝑡 − 𝜂𝑡 (1 − 𝑝)𝐶𝑡 + Thus for different iterations 𝑡 = 0, … , 𝑇 − 1, we have: 𝐿1 (𝑓𝜇 ) 2 𝜂0 𝐷 2 𝐿1 (𝑓𝜇 ) 2 𝐴2 − 𝐴1 ≤ −𝜂1 𝑝𝐵1 − 𝜂1 (1 − 𝑝)𝐶1 + 𝜂1 𝐷 2 ⋮ 𝐿1 (𝑓𝜇 ) 2 𝐴𝑇 − 𝐴𝑇 −1 ≤ −𝜂𝑇 −1 𝑝𝐵𝑇 −1 − 𝜂𝑇 −1 (1 − 𝑝)𝐶𝑇 −1 + 𝜂𝑇 −1 𝐷 2 Summing all these inequalities, we have: 𝐴1 − 𝐴0 ≤ −𝜂0 𝑝𝐵0 − 𝜂0 (1 − 𝑝)𝐶0 +

𝐴𝑇 − 𝐴0 ≤ −𝑝

𝑇∑ −1

𝜂𝑡 𝐵𝑡 − (1 − 𝑝)

𝑡=0

𝑇∑ −1 𝑡=0

17

𝜂𝑡 𝐶𝑡 +

𝐿1 (𝑓𝜇 ) 2

𝐷

𝑇∑ −1 𝑡=0

𝜂𝑡2

(37)

(38)

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

Here 𝐴0 = 𝑓𝜇 (𝐱0 ) and 𝐴𝑇 = 𝔼𝑇 [𝑓𝜇 (𝐱𝑇 )] is the expectation of the function value at the end of the optimization process. Let’s assume we use constant step size 𝜂𝑡 = 𝜂 for all 𝑡. Thus we have: 𝐴𝑇 − 𝐴0 ≤ −𝜂𝑝

𝑇∑ −1

𝐵𝑡 − 𝜂(1 − 𝑝)

𝑡=0

𝑇∑ −1

𝐶𝑡 +

𝑡=0

𝐿1 (𝑓𝜇 ) 2 𝜂 𝐷𝑇 2

(39)

Taking average over 𝑇 iterations, we have: 𝑇 −1 𝑇 −1 𝐿1 (𝑓𝜇 ) 1 1 ∑ 1 ∑ (𝐴𝑇 − 𝐴0 ) ≤ −𝑝 𝐵𝑡 − (1 − 𝑝) 𝐶𝑡 + 𝜂𝐷 𝜂𝑇 𝑇 𝑡=0 𝑇 𝑡=0 2

(40)

Rearranging the terms, we have: 𝑇 −1 𝑇 −1 𝐿1 (𝑓𝜇 ) 𝐴 − 𝐴𝑇 1 ∑ 1 ∑ 𝐵𝑡 + (1 − 𝑝) 𝐶𝑡 ≤ 0 + 𝜂𝐷 𝑝 𝑇 𝑡=0 𝑇 𝑡=0 𝜂𝑇 2

Now minimize the right hand side with respect to 𝜂:

√

∗

𝜂 =

(41)

2(𝐴0 − 𝐴𝑇 ) 𝐿1 (𝑓𝜇 )𝐷𝑇

Thus we have:

(42)

√

( ) 𝐴0 − 𝐴𝑇 1 1 (43) 𝐵𝑡 + (1 − 𝑝) 𝐶𝑡 ≤ 2𝐿1 (𝑓𝜇 )𝐷 𝑇 𝑡=0 𝑇 𝑡=0 𝑇 From Lipschitz continuity of 𝑓 and 𝑓̃, we know that 𝑓𝜇 and 𝑓̃𝜇 are also Lipschitz continuous with the same constants. Thus we can bound 𝐴0 − 𝐴𝑇 as: |𝐴0 − 𝐴𝑇 | ≤ 𝐿0 (𝑓 )‖𝐱0 − 𝐱∗ ‖ ≤ 𝐿0 (𝑓 )𝑅 (44) Where 𝑅 is the radius of the ball for optimization budget. Thus we have the final convergence bound as: √ ( ) 𝑇 −1 𝑇 −1 𝐿0 (𝑓 )𝑅 1 ∑ 1 ∑ 𝑝 𝐵𝑡 + (1 − 𝑝) 𝐶𝑡 ≤ 2𝐿1 (𝑓𝜇 )𝐷 (45) 𝑇 𝑡=0 𝑇 𝑡=0 𝑇 𝑝

𝑇∑ −1

𝑇∑ −1

1∕2

From the definition of 𝑓𝜇 and lemma B.3 we have 𝐿1 (𝑓𝜇 ) = 2𝑑𝜇 𝐿0 (𝑓 ), therefore we have: √ 𝑇 −1 𝑇 −1 4𝑑 1∕2 𝐿0 (𝑓 )2 𝑅 1 ∑ 1 ∑ 𝐵𝑡 + (1 − 𝑝) 𝐶𝑡 ≤ 𝑝 𝐷 𝑇 𝑡=0 𝑇 𝑡=0 𝜇𝑇

(46) ′

We also need to choose 𝜇 small enough to have |𝑓𝜇 (𝐱) − 𝑓 (𝐱)| ≤ 𝜖 ′ . To have this bound, we choose 𝜇 ≤ 𝑑 1∕2𝜖𝐿 (𝑓 ) as in 0 Nesterov and Spokoiny (2017). Thus we can still simplify the bound as: √ 𝑇 −1 𝑇 −1 4𝑑𝐿0 (𝑓 )3 𝑅 1 ∑ 1 ∑ 𝑝 𝐷 (47) 𝐵𝑡 + (1 − 𝑝) 𝐶𝑡 ≤ 𝑇 𝑡=0 𝑇 𝑡=0 𝜖′𝑇 Let’s also plug this value in 𝐷 and rewrite that: 𝐷 = 𝑝𝐿20 (𝑓 )(𝑑 + 4)2 + (1 − 𝑝)𝐿20 (𝑓̃)(𝑑 + 4)2 +

2𝑝(1 − 𝑝)𝜖 2 𝑑 2 𝐿0 (𝑓 )2

𝜖 ′2 The input dimension 𝑑 usually dominates the constant 4 in (𝑑 + 4), thus we can simplify the final bound as: 2𝑝(1 − 𝑝)𝜖 2 𝑑 2 𝐿0 (𝑓 )2 𝐷 ≈ 𝑝𝐿20 (𝑓 )𝑑 2 + (1 − 𝑝)𝐿20 (𝑓̃)𝑑 2 + 𝜖 ′2 ) ( 2 ̃ (1 − 𝑝) 𝐿0 (𝑓 ) 𝜖2 = 𝑝𝑑 2 𝐿0 (𝑓 )2 1 + + 2(1 − 𝑝) 2 𝑝 𝐿 (𝑓 ) 𝜖 ′2

(48)

(49)

0

Plugging this into the final bound, we have:

√ ( ) √ √ 4𝑑 3 𝐿 (𝑓 )5 𝑅 𝐿20 (𝑓̃) 2 𝑝 1−𝑝 𝜖 0 √ 2 𝔼 [‖∇𝑓𝜇 (𝐱𝑡 )‖ ]+ 𝔼 [⟨∇𝑓𝜇 (𝐱𝑡 ), ∇𝑓̃𝜇 (𝐱𝑡 )] ≤ 𝑝 + (1 − 𝑝) + 2𝑝(1 − 𝑝) 𝑇 𝑡=0 𝑡 𝑇 𝑡=0 𝑡 𝜖′𝑇 𝜖 ′2 𝐿20 (𝑓 ) (50) ̃ This bound shows that optimizing the confusion term ⟨∇𝑓𝜇 (𝐱), ∇𝑓𝜇 (𝐱)⟩ increases the bound and, consequently, increases the number of steps required by gradient estimation-based attacks. 𝑇∑ −1

𝑇∑ −1

18

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

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 ℎ𝑡 . 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 𝑓 ∶ ℝ𝑑 → ℝ be 𝐿-smooth, i.e., ‖∇𝑓 (𝑢) − ∇𝑓 (𝑣)‖ ≤ 𝐿‖𝑢 − 𝑣‖ Then for any 𝑥, 𝜖 ∈ ℝ𝑑 ,

∀𝑢, 𝑣 ∈ ℝ𝑑 .

𝑓 (𝑥 + 𝜖) = 𝑓 (𝑥) + ⟨∇𝑓 (𝑥), 𝜖⟩ + 𝑟𝑓 ,

where the remainder term satisfies

𝐿 | |𝑟𝑓 | ≤ ‖𝜖‖2 . | 2

Equivalently,

| | 𝐿 |𝑓 (𝑥 + 𝜖) − 𝑓 (𝑥) − ⟨∇𝑓 (𝑥), 𝜖⟩| ≤ ‖𝜖‖2 . | | 2

Proof. Define 𝜙(𝑡) = 𝑓 (𝑥 + 𝑡𝜖) for 𝑡 ∈ [0, 1]. By the fundamental theorem of calculus, 1

𝑓 (𝑥 + 𝜖) − 𝑓 (𝑥) =

∫0

⟨∇𝑓 (𝑥 + 𝑡𝜖), 𝜖⟩ 𝑑𝑡.

Subtracting the first-order term yields 1

𝑓 (𝑥 + 𝜖) − 𝑓 (𝑥) = ⟨∇𝑓 (𝑥), 𝜖⟩ + Thus the remainder term is

∫0

⟨∇𝑓 (𝑥 + 𝑡𝜖) − ∇𝑓 (𝑥), 𝜖⟩ 𝑑𝑡.

1

𝑟𝑓 =

∫0

⟨∇𝑓 (𝑥 + 𝑡𝜖) − ∇𝑓 (𝑥), 𝜖⟩ 𝑑𝑡.

Applying Cauchy–Schwarz and 𝐿-smoothness, 1

|𝑟𝑓 | ≤

∫0

1

‖∇𝑓 (𝑥 + 𝑡𝜖) − ∇𝑓 (𝑥)‖ ‖𝜖‖ 𝑑𝑡 ≤

∫0

𝐿𝑡‖𝜖‖2 𝑑𝑡 =

𝐿 ‖𝜖‖2 . 2

Lemma C.2. Let 𝑢 ∼  (0, 𝐼𝑑 ) in ℝ𝑑 with 𝑑 ≥ 2, and let 𝑔 ∈ ℝ𝑑 be fixed with 𝑔 ≠ 0. Then for any 𝑐 ≥ 0, √ ( ⊤ ) 2 𝑐𝑑 2 ℙ |𝑔 𝑢| < 𝑐 ‖𝑢‖ ≤ . 𝜋 ‖𝑔‖ Proof. Write 𝑢 = 𝑟𝑠 where 𝑟 = ‖𝑢‖ ≥ 0 and 𝑠 = 𝑢∕‖𝑢‖ ∈ 𝑆 𝑑−1 . By rotational invariance of the standard Gaussian, 𝑟 and 𝑠 are independent, 𝑠 is uniform on the unit sphere, and 𝑟2 ∼ 𝜒𝑑2 . Let 𝑎 = ‖𝑔‖ > 0. Then 𝑔 ⊤ 𝑢 = 𝑟 𝑔 ⊤ 𝑠. 𝑑

By rotation symmetry, 𝑔 ⊤ 𝑠 = 𝑎𝑇 , where 𝑇 is the first coordinate of a uniform random point on 𝑆 𝑑−1 . Hence ( ) ( ( 𝑐 | ) | ) ℙ |𝑔 ⊤ 𝑢| < 𝑐‖𝑢‖2 | 𝑟 = ℙ |𝑎𝑟𝑇 | < 𝑐𝑟2 | 𝑟 = ℙ |𝑇 | < 𝑟 . | | 𝑎 For 𝑑 ≥ 2, 𝑇 has density on [−1, 1] 𝑑−3

𝑓𝑇 (𝑡) = 𝐶𝑑 (1 − 𝑡2 ) 2 ,

𝐶𝑑 = √ 19

Γ(𝑑∕2) 𝜋 Γ((𝑑 − 1)∕2)

.

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

Since sup𝑡∈[−1,1] 𝑓𝑇 (𝑡) = 𝑓𝑇 (0) = 𝐶𝑑 , for any 𝑡 ≥ 0 we have 𝑡

ℙ(|𝑇 | < 𝑡) = Therefore,

∫−𝑡

𝑓𝑇 (𝑥) 𝑑𝑥 ≤ 2𝑡 𝐶𝑑 .

) ( 𝑐 𝑐 ℙ |𝑇 | < 𝑟 ≤ 2𝐶𝑑 𝑟. 𝑎 𝑎

Taking expectation over 𝑟 gives

( ) 𝑐 ℙ |𝑔 ⊤ 𝑢| < 𝑐‖𝑢‖2 ≤ 2𝐶𝑑 𝔼[𝑟]. 𝑎 √ √ √ By Cauchy–Schwarz, 𝔼[𝑟] ≤ 𝔼‖𝑢‖2 = 𝑑. Finally, using Γ(𝑥 + 12 )∕Γ(𝑥) ≤ 𝑥 for all 𝑥 ≥ 12 with 𝑥 = 𝑑−1 , 2 1

1 Γ(𝑥 + 2 ) =√ ≤ 𝐶𝑑 = √ 𝜋 Γ((𝑑 − 1)∕2) 𝜋 Γ(𝑥) Γ(𝑑∕2)

Combining gives ( ) ℙ |𝑔 ⊤ 𝑢| < 𝑐‖𝑢‖2 ≤ 2

(√

𝑑 2𝜋

)

√

𝑑 . 2𝜋

( ) √ 𝑐 √ 2 𝑐𝑑 𝑑 = . ‖𝑔‖ 𝜋 ‖𝑔‖

Lemma C.3. Let 𝑢 ∼  (0, 𝐼𝑑 ) and let 𝑔, 𝑔̃ ∈ ℝ𝑑 be nonzero vectors. Define 𝜃 ∈ [0, 𝜋] to be the angle between 𝑔 and 𝑔, ̃ i.e. ⟨𝑔, 𝑔⟩ ̃ cos 𝜃 = . ‖𝑔‖ ‖𝑔‖ ̃ Then ( ) ( ) ⟨𝑔, 𝑔⟩ ̃ 𝜃 1 ℙ sign(⟨𝑔, 𝑢⟩) ≠ sign(⟨𝑔, ̃ 𝑢⟩) = = arccos . 𝜋 𝜋 ‖𝑔‖ ‖𝑔‖ ̃ Proof. Set 𝑋 = ⟨𝑔, 𝑢⟩ and 𝑌 = ⟨𝑔, ̃ 𝑢⟩. Then (𝑋, 𝑌 ) is a centered bivariate Gaussian with Var(𝑋) = ‖𝑔‖2 ,

Var(𝑌 ) = ‖𝑔‖ ̃ 2,

Cov(𝑋, 𝑌 ) = ⟨𝑔, 𝑔⟩, ̃

so the correlation is 𝜌 = ⟨𝑔, 𝑔⟩∕(‖𝑔‖‖ ̃ 𝑔‖) ̃ = cos 𝜃. A standard orthant probability identity gives ℙ(𝑋 > 0, 𝑌 > 0) =

1 1 + arcsin(𝜌). 4 2𝜋

By symmetry, ℙ(𝑋𝑌 < 0) = 1 − 2ℙ(𝑋 > 0, 𝑌 > 0) =

C.2

1 1 1 𝜃 − arcsin(𝜌) = arccos(𝜌) = . 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 𝑑 ≥ 2, 𝐮 ∼  (0, 𝐼𝑑 ), fixed 𝐱 ∈ ℝ𝑑 , 𝜇 > 0, and with per-query switching defense 𝑓def , the signals ℎ ∶= 𝑓 (𝐱 + 𝜇𝐮) − 𝑓 (𝐱),

ℎdef ∶= 𝑓def (𝐱 + 𝜇𝐮) − 𝑓def (𝐱)

satisfy the bound in (11). Proof. Let Δ𝑓̃ ∶= 𝑓̃(𝑥 + 𝜇𝑢) − 𝑓̃(𝑥).

Δ𝑓 ∶= 𝑓 (𝑥 + 𝜇𝑢) − 𝑓 (𝑥), i.i.d.

By definition, ℎ = Δ𝑓 . Let 𝜆1 , 𝜆2 ∼ Bernoulli(𝑝) be independent of 𝑢, and write 𝑓def (𝑥 + 𝜇𝑢) = 𝜆1 𝑓 (𝑥 + 𝜇𝑢) + (1 − 𝜆1 )𝑓̃(𝑥 + 𝜇𝑢), 20

𝑓def (𝑥) = 𝜆2 𝑓 (𝑥) + (1 − 𝜆2 )𝑓̃(𝑥).

Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion

Define 𝐸 ∶= {sign(ℎ) ≠ sign(ℎdef )}. Conditioning on (𝜆1 , 𝜆2 ) and keeping only the case (0, 0) gives ( ) ℙ(𝐸) ≥ ℙ 𝐸 ∩ {𝜆1 = 0, 𝜆2 = 0} ( ) = ℙ(𝜆1 = 0, 𝜆2 = 0) ℙ sign(Δ𝑓 ) ≠ sign(Δ𝑓̃ ) ( ) = (1 − 𝑝)2 ℙ sign(Δ𝑓 ) ≠ sign(Δ𝑓̃ ) . It remains to lower bound ℙ(sign(Δ𝑓 ) ≠ sign(Δ𝑓̃ )). Define the linear parts

𝐴 ∶= ⟨∇𝑓 (𝑥), 𝑢⟩, By Lemma C.1 applied to 𝑓 with 𝐿 = 𝐿1 (𝑓 ) and 𝜖 = 𝜇𝑢, Δ𝑓 = 𝜇𝐴 + 𝑟𝑓 ,

𝐴̃ ∶= ⟨∇𝑓̃(𝑥), 𝑢⟩. |𝑟𝑓 | ≤

𝐿1 (𝑓 ) 2 𝜇 ‖𝑢‖2 . 2

|𝑟𝑓̃ | ≤

𝐿1 (𝑓̃) 2 𝜇 ‖𝑢‖2 . 2

Similarly, applying Lemma C.1 to 𝑓̃ with 𝐿 = 𝐿1 (𝑓̃), Δ𝑓̃ = 𝜇𝐴̃ + 𝑟𝑓̃ ,

If |𝛿| < |𝑎|, then sign(𝑎 + 𝛿) = sign(𝑎). Define { } { } 𝐿1 (𝑓 ) 𝐿1 (𝑓̃) ̃ . 𝐺𝑓 ∶= 𝜇‖𝑢‖2 < |𝐴| , 𝐺𝑓̃ ∶= 𝜇‖𝑢‖2 < |𝐴| 2 2

Step 1: sign-stability events.

̃ Therefore, On 𝐺𝑓 , we have |𝑟𝑓 | < 𝜇|𝐴|, hence sign(Δ𝑓 ) = sign(𝐴); similarly on 𝐺𝑓̃ , sign(Δ𝑓̃ ) = sign(𝐴). ( ) ( ) ̃ − ℙ(𝐺𝑐 ) − ℙ(𝐺𝑐 ). ℙ sign(Δ𝑓 ) ≠ sign(Δ𝑓̃ ) ≥ ℙ sign(𝐴) ≠ sign(𝐴) 𝑓 𝑓̃ By Lemma C.3 with 𝑔 = ∇𝑓 (𝑥) and 𝑔̃ = ∇𝑓̃(𝑥), ) ( ( ) 1 ⟨∇𝑓 (𝑥), ∇𝑓̃(𝑥)⟩ ̃ . ℙ sign(𝐴) ≠ sign(𝐴) = arccos 𝜋 ‖∇𝑓 (𝑥)‖ ‖∇𝑓̃(𝑥)‖

Step 2: linear sign disagreement.

Step 3: bound Taylor-failure probabilities. (

ℙ(𝐺𝑓𝑐 ) = ℙ

Using Lemma C.2 with 𝑔 = ∇𝑓 (𝑥) and 𝑐 =

𝐿 (𝑓 ) |𝐴| < 12 𝜇‖𝑢‖2

)

√ ≤

𝐿1 (𝑓 ) 𝜇, 2

𝐿 (𝑓 )

1 𝜇𝑑 𝐿1 (𝑓 ) 2 ( 2 𝜇)𝑑 =√ . 𝜋 ‖∇𝑓 (𝑥)‖ 2𝜋 ‖∇𝑓 (𝑥)‖

Similarly, 𝜇𝑑 𝐿1 (𝑓̃) ℙ(𝐺𝑓𝑐̃ ) ≤ √ . 2𝜋 ‖∇𝑓̃(𝑥)‖ Step 4: combine and multiply by (1 − 𝑝)2 .

Combining Steps 1–3 yields ( ) ( ) ( ) 1 𝐿1 (𝑓 ) 𝐿1 (𝑓̃) ⟨∇𝑓 (𝑥), ∇𝑓̃(𝑥)⟩ 𝜇𝑑 ℙ sign(Δ𝑓 ) ≠ sign(Δ𝑓̃ ) ≥ arccos −√ + . 𝜋 ‖∇𝑓 (𝑥)‖ ‖∇𝑓̃(𝑥)‖ 2𝜋 ‖∇𝑓 (𝑥)‖ ‖∇𝑓̃(𝑥)‖

Multiplying by (1 − 𝑝)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 ∇𝑓 (𝐱) and ∇𝑓̃(𝐱) 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. 21

Related documents

• Mitigating Black-Box Score-Based Query Attacks via Gradient Confusion#1342601
• Accelerating Targeted Hard-Label Adversarial Attacks in Low-Query Black-Box Settings#158718
• Machine Learning Security: Threats, Countermeasures, and Evaluations#133945
• AI Models Can Provably Hide Arbitrary Capabilities#1298424
• AI Models Can Provably Hide Arbitrary Capabilities#1291720