Co-Designing Smoothing Noise and Query Tracking Against Adaptive Black-Box Attackers

Many deployed classifiers sit behind an interface that returns only a label, and attackers probe them with thousands of queries until they find an input that flips the answer. Two defenses exist for this setting, and each fails on its own. Randomized smoothing adds random noise to every input and returns the majority vote. It comes with a mathematical guarantee for each individual input, but an attacker who can repeat queries can average the noise away. Stateful defenses keep a log of past queries and flag clusters of near-duplicate ones. They need no retraining, but they are heuristic, and attackers have learned to read their rejections as a signal and route around them.

This note argues that the two defenses should be designed together. Smoothing makes each answer near a decision boundary a coin flip. The only way to read a coin's bias is to flip it many times at nearly the same place, and "many queries at nearly the same place" is exactly the pattern a query log detects. If the smoothing noise level is set relative to the detector's similarity radius, the attacker faces a forced choice: get caught, or accept a boundary estimate too coarse to be useful. We propose to state that choice as a query-complexity certificate, build a model-agnostic wrapper that achieves it around frozen classifiers, and test it against the strongest adaptive attackers we can construct.

Core Claim

Let $p(x)$ be the probability that the base classifier, applied to $x$ plus Gaussian noise of scale $\sigma$, returns the top class. A standard property of Gaussian smoothing is that the transformed score $\Phi^{-1}(p(x))$, where $\Phi$ is the standard normal CDF, changes by at most $\|x - x'\|_2 / \sigma$ between any two inputs. This is the same Lipschitz fact that underlies the certified radius in Certified Adversarial Robustness with Additive Noise. A hard-label attacker who wants to know which side of the boundary a point lies on, to a resolution of $\delta$ in these probit units, needs roughly $1/\delta^2$ noisy answers, which is ordinary Bernoulli estimation. All of those answers must come from inside a ball of radius about $\delta\sigma$; outside it, the quantity being averaged has itself moved by more than $\delta$.

Suppose a query-tracking detector flags any group of $k$ queries that fall within distance $\rho$ of one another. The claim is the coupling condition

$$ \delta\,\sigma \le \rho \quad\text{and}\quad k \ll 1/\delta^2 . $$

When it holds, an attacker who needs boundary resolution $\delta$ must either place many queries inside a detectable cluster or work with resolution worse than $\delta$. Read the other way, the defender gets a lower bound on how coarse an undetected attacker's boundary estimate must be, and that bound holds even if the attacker knows $\sigma$, $\rho$, and $k$.

This guarantee is about the attacker's query process, not about a single input. It sits alongside the usual per-input certified radius rather than replacing it. The condition also exposes a three-way trade-off:

  • A larger $\sigma$ costs clean and per-class accuracy, through the shrinking effect proved in Hidden Cost of Randomized Smoothing.
  • A larger $\rho$ costs benign false positives.
  • A smaller required $\delta$ costs the attacker queries.

The novelty lies in this coupling. The closest work, Randomized Smoothing under Attack, found empirically that using few Monte Carlo samples creates boundary jitter that disrupts attacks such as HSJA, SurFree and RayS. It fixed its parameters, never considered an attacker who averages the jitter away, and had no detector to stop that averaging. Theoretically Principled Trade-off for Stateful Defenses proved an "attacker's dilemma": evading similarity tracking forces the attacker to spread queries out, which corrupts its gradient estimates. That analysis assumes the classifier's own answers are deterministic, so the attacker's only noise is self-inflicted. We supply the method that analysis lacks, defender-controlled answer noise with a known Lipschitz structure, which turns the dilemma into an explicit inequality. We reuse that paper's feature-extractor Lipschitz ratios to translate $\rho$ between input space and the detector's feature space.

Research Program

The work has three parts.

The wrapper. Around a frozen classifier, we place an off-the-shelf diffusion denoiser and Gaussian smoothing, the zero-shot composition of Carlini et al. building on Denoised Smoothing. This keeps the defense model-agnostic. Each query receives a fresh noise draw. The answer is a majority over $n_t$ draws, where the defender sets $n_t$ per account and per region.

A single global query log runs alongside, with similarity radius $\rho$ and cluster threshold $k$. The log is global because Investigating Stateful Defenses showed that per-account logs fail when attackers spread queries across accounts.

The dynamic element is a simple policy. Accounts whose recent queries concentrate near low-margin regions get smaller $n_t$, so each answer carries less information; benign accounts get large $n_t$ and stable answers. We treat this as a repeated game in which the defender learns about the attacker over rounds. The certificate must not depend on keeping the policy secret. Secrecy, which Comparing Strategic Secrecy and Stackelberg Commitment shows can beat public commitment in zero-sum settings, is measured only as an added benefit.

The theory. We will prove the coupling bound for hard-label attackers. The bound counts how many undetected queries are possible as a function of $\sigma$, $\rho$, $k$ and $n_t$. It covers an attacker who mixes exact repeats with queries spread just beyond $\rho$. It also covers an attacker who distributes queries across many accounts, under the assumption that the log is global.

The adaptive attacker. We will build the strongest attacker we can, because the claim is only as good as its evaluation. It is HSJA/RayS-style boundary search with explicit noise-aware averaging: it chooses the spread and repetition of each query cluster to sit just outside the detector's radius. We combine it with OARS-style threshold probing of the rejection signal, from Investigating Stateful Defenses.

Baselines

The naive reference point is the frozen classifier with no wrapper, attacked by HSJA, SurFree, RayS and OARS-NES. It anchors attack success rate (ASR) at a given query budget.

Static smoothing. The second baseline is standard randomized smoothing with fixed $\sigma$ and large $n$, as in Certified Adversarial Robustness with Additive Noise, with no query log. It is the strongest certified competitor, and it isolates what the log adds.

Low-sample smoothing. The third baseline is fixed low-$n$ smoothing, the "stochastic shield" of Randomized Smoothing under Attack, again without a log. That paper reports 97% clean accuracy at $\sigma = 0.05$. It reports its gap result as a ratio, about 30 times between the distortion needed to flip a label and the certified radius, rather than as an ASR we could match directly. We therefore rerun it.

Strongest heuristic stateful defense. This is Query Provenance Analysis, which links queries into a graph and classifies attack trajectories with a graph neural network. It reports an average OARS ASR of 4.08% and a benign false-positive rate of 0.04%. For context, Blacklight and PIHA reach 77.63% and 87.72% ASR under the same attack in that paper. Investigating Stateful Defenses separately reports Blacklight's CIFAR-10 robust accuracy falling from 82.2% to 6.4% under OARS.

Beating QPA means meeting all of the following:

  • matching or beating its 4.08% ASR under OARS at a benign false-positive rate no higher than 0.04%;
  • also holding against our noise-aware attacker, which QPA was not tested against;
  • doing both while providing a guarantee that QPA lacks.

We have found no reported certified-accuracy figure on Lacuna for diffusion-denoised smoothing combined with a query log, so the certified side is new measurement.

Fairness. All defenses wrap the same frozen classifiers and the same denoiser. All are attacked under the same query budgets: 10,000, the budget at which OARS reaches 99–100% ASR, and 100,000. Each attack gets an equal tuning budget per defense.

Ablation. The key ablation keeps the identical log and wrapper but sets $\rho$ well below $\delta\sigma$, so the coupling condition is deliberately violated. If performance does not drop sharply, the coupling is not doing the work.

Why not just…?

Why not just use low-sample smoothing alone? Its jitter is real, but it is unstructured averaging bait. Because the smoothed score is Lipschitz, an attacker can average nearby queries without exact repeats and recover the boundary. Our noise-aware attacker is built to do exactly this. The low-$n$ baseline is the experiment that settles whether averaging defeats it. We expect it to, because nothing in Randomized Smoothing under Attack limits repetition.

Why not just randomize the detector's rejection threshold, without smoothing the classifier? This is a real threat to the proposal, since it is cheaper and directly targets the oracle that OARS exploits. However, the classifier's own boundary stays deterministic. An attacker who stays below the detection threshold then still reads exact labels, and no Lipschitz structure ties the attacker's averaging radius to $\rho$, so there is no certificate. We will run it as an additional baseline. If it matches our ASR curves against the noise-aware attacker, the empirical half of our claim fails, and only the guarantee remains as a contribution.

Why not just use QPA's learned graph detector? It is the best empirical result in the file. It is also heuristic: an attacker who knows its features could shape query graphs to evade it, a limitation the file itself notes. Our design could plug QPA in as the detector. The question we answer is whether coupling it to smoothing yields a bound that QPA alone cannot give.

Why not just use adversarial training? It requires retraining the model, which is impossible for frozen API models. Improving the Accuracy-Robustness Trade-off documents its clean-accuracy cost, and DiffPure reports it trailing purification by 36% on unseen spatial attacks. It is also orthogonal: an adversarially trained model can sit inside our wrapper.

Proposed Experiments

Datasets and models. We will use CIFAR-10 and ImageNet with frozen WideResNet-28-10 and ResNet-50 classifiers, the settings used by DiffPure, DiffAttack and the stateful-defense papers, plus CelebA-HQ for a third domain.

Metrics. We measure ASR versus query count, the detection rate of attack clusters, the benign false-positive rate on held-out clean query streams, clean accuracy, per-class accuracy (to track the shrinking effect), certified accuracy at standard radii for benign answers, and latency.

Decisive check. We sweep the ratio $\rho/\sigma$ at fixed benign false-positive rate. The coupling claim predicts a sharp transition in the noise-aware attacker's success near $\rho \approx \delta\sigma$, where $\delta$ is the resolution the attack needs to make progress. The claim also predicts that the attacker's measured boundary-localization error scales as one over the square root of its undetected queries. If attacker success varies smoothly with no transition, or if the attacker reaches low error with few clustered queries, the claim is wrong.

Secondary check. We test whether the per-account $n_t$ policy improves benign stability over a fixed $n$ at equal attacker ASR. This determines whether the dynamic component earns its place or should be dropped.