Stateful defenses for machine learning models cannot yet withstand black-box attacks
Stateful Defenses for Machine Learning Models Are Not Yet Secure Against Black-box Attacks
The authors propose the adaptive black-box attack strategy OARS, and state that its enhanced attacks raise ASR against four stateful defenses including Blacklight from near 0% to near 100%.
Black-box threat model: the attacker can only query the model through the public API of an MLaaS platform, obtaining labels (hard-label) or class probabilities (score-based), and cannot access the model or training data; the attack is model agnostic and does not know whether an SDM is deployed or which one; the victim system is a query interface with a stateful defense (SDM) deployed, and the SDM runs throughout and can reject queries or ban accounts.
- Stateful defenses (SDM) defend against black-box attacks by tracking query history and rejecting similar queries, and Blacklight et al. reported 0% ASR against existing attacks. The authors aim to answer: following the lesson from the white-box field, can SDM be broken by stronger adaptive black-box attacks.
- Proposes OARS (Oracle-guided Adaptive Rejection Sampling): treats the SDM's rejection/banning behavior as an oracle, first fine-tunes the parameters of the attack's sampling distribution via binary search (adapt), then performs rejection sampling from the fine-tuned distribution to avoid collisions (resample), modifying the three stages of the attack: gradient estimation, step size, and boundary location.
- OARS was applied to six attacks—NES, Square, HSJA, QEBA, SurFree, and Boundary—and four SDMs were evaluated on CIFAR10, ImageNet, CelebaHQ, and IIoT Malware. The authors report that for every dataset×defense combination, at least one OARS attack achieved an ASR above 99%, while the standard and query-blinding baselines were mostly below 5%.
- In the Limitations section, the authors state that transfer attacks were not considered, nor were other black-box attack detection methods such as AAA and AdvMind evaluated. The experiments cover four SDMs, six attacks, and four main datasets, with 100 samples per configuration (an additional 1000 samples for CIFAR10); the text domain has only preliminary experiments.
- Evaluated models
- BlacklightPIHAIIoT-SDAOSDResNet-20 (CIFAR10)ResNet-152 (ImageNet)ResNet-152 (CelebaHQ)5 Conv + FC (IIoT Malware)BERT
- Benchmarks
- CIFAR10ImageNetCelebaHQIIoT MalwareIMDB
- Metrics
- ASRquery countfalse positive rate
Researchers from the University of Wisconsin-Madison and the University of Michigan proposed the OARS adaptive black-box attack strategy in a CCS 2023 paper, showing that four stateful defenses—Blacklight, PIHA, OSD, and IIoT-SDA—are highly vulnerable to such attacks. OARS (Oracle-guided Adaptive Rejection Sampling) first uses initial queries to infer the defense's similarity detection mechanism, then designs subsequent queries accordingly, continuing to construct adversarial examples while avoiding collision detection. The researchers applied it to six black-box attacks—NES, HSJA, QEBA, SurFree, Square, and Boundary—and on datasets including CIFAR10 and ImageNet with a 100k query budget, the best enhanced attack raised the success rate against the four defenses from near 0% to near 100%, with an additional query cost of only $1-18 for online APIs. Against defense reconfigurations such as raising the collision threshold, the attack still maintained a high success rate; the authors state that OARS-enhanced attacks can serve as a new benchmark for testing future stateful defenses.
Why it was selectedThe OARS adaptive attack proposed in the paper raises the success rate of the best-performing black-box attacks against four stateful defenses from near 0% to near 100%, providing a new benchmark for testing stateful defenses.
Paper analysis
What problem does this paper attempt to solve?
The authors propose the adaptive black-box attack OARS, which they claim can break existing stateful defenses (SDMs), raising ASR from near 0% to near 100%.
Core question: whether stateful defenses (SDM) against black-box query attacks can be broken by adaptive black-box attacks.
- Problem setting: MLaaS platforms (such as Clarifai, Amazon Rekognition) expose only a query API, and black-box attacks need to repeatedly query similar samples to estimate gradients or walk along the boundary. SDM (such as Blacklight, PIHA) tracks query history and rejects queries that are "too similar" (i.e., collisions); the authors state that Blacklight achieves 0% ASR against multiple attacks.
- Shortcomings of existing methods: The authors state that the existing adaptive approach query-blinding evades detection by applying random transformations to queries, but it is difficult to balance attack utility and detection evasion: stronger transformations make evasion easier but destroy the optimization process more; Blacklight et al. claim to defeat query-blinding.
- Core observation: The authors' key insight is that the action module of SDM "leaks" information about its similarity detection process and parameters—attackers can use rejection/blocking behavior as an oracle to adjust subsequent queries so that they both avoid collisions and continue to advance the attack.
- Proposed in the paper: An adaptive black-box attack strategy OARS (Oracle-guided Adaptive Rejection Sampling), in two stages: first use an initial query pattern to infer key properties of the SDM defense, then use these properties to design subsequent queries. The authors apply it to six black-box attacks and report that ASR against four SDMs rises from near 0% to near 100%.
- Threat model:
- Goal: construct adversarial examples within a perturbation budget (NES, HSJA, QEBA are targeted; Square, SurFree, Boundary are untargeted).
- Knowledge: black-box, can only query the model to obtain labels (hard-label) or class probabilities (score-based); the attack is model agnostic and does not know whether an SDM is deployed or which one.
- Capability: interact with the public API by registering accounts; do not disable or pause the SDM, and the SDM can reject queries or ban accounts throughout.
- Victim system: an MLaaS classifier with an SDM deployed.
What related research exists?
Related work is divided into four groups: black-box attacks, stateful defense mechanisms (SDM), query-blinding adaptive attacks, and other black-box attack detection methods.
Black-box query attacks (the six attacks modified by OARS)
- NES (Ilyas et al., 2018)—a score-based attack that estimates the loss gradient using finite differences of Gaussian samples, then performs projected gradient descent.
- Square (Andriushchenko et al., 2020)—a score-based attack that applies ℓp-bounded random perturbations within progressively shrinking squares.
- HSJA (Chen et al., 2020), QEBA (Li et al., 2020), SurFree (Maho et al., 2021), Boundary (Brendel et al., 2017)—four hard-label attacks: HSJA binary-searches to locate the boundary and estimates the gradient; QEBA samples in a low-dimensional subspace; SurFree does not estimate gradients and randomly searches along polar coordinate directions; Boundary starts from a randomly initialized adversarial example and performs a boundary walk.
Stateful defense models (SDM, the attack targets of this paper)
- OSD (Chen et al., 2020)—uses a neural similarity encoder trained with contrastive loss to extract features, a per-account query store, detects using the average ℓ2 distance to the 50 nearest neighbors, and the action is banning the account; the paper notes that Sybil accounts can trivially break it.
- Blacklight (Li et al., 2022)—uses Pixel-SHA probabilistic hashing for feature extraction, a global hash table query store, approximate nearest neighbor search on normalized Hamming distance, and the action is rejecting the query; the authors relay that it reports 0% ASR against all black-box attacks, and that with the query store reset once per day, the fastest successful attack would take about 3 years.
- PIHA (Choi et al., 2023)—similar to Blacklight but proposes a new perceptual hashing algorithm (low-pass filtering, HSV/YCbCr color spaces, Local Binary Patterns).
- IIoT-SDA (Esmaeili et al., 2022)—for industrial IoT malware classification, uses a neural encoder trained with Mahalanobis contrastive loss, a per-account query store, 11 nearest neighbors, and rejects queries; the paper describes it as a combination of OSD and Blacklight.
query-blinding (existing adaptive approach, baseline of this paper)
- Query-blinding (Chen et al., 2020)—applies random image transformations (rotation, translation, scaling, Gaussian noise) to queries to evade detection, then uses a revealing function to recover the original output estimate. The paper notes that it is difficult to balance attack utility and detection evasion, and that Blacklight et al. claim to defeat it.
Other black-box attack detection methods (not evaluated in the paper)
- AAA (Chen et al., 2022)—a post-processing method that periodically modifies the logits loss curve to mislead score-based attacks; AdvMind (Pang et al., 2020)—a detection model that infers attacker intent. The paper states that both are orthogonal to SDM and were not included in the evaluation.
Baselines and benchmarks: The baseline attack configurations are standard and query-blinding (both include a resample-only variant); the defense baselines are the default configurations of the four SDMs above; the datasets are CIFAR10, ImageNet, CelebaHQ, IIoT Malware.
The authors position this paper as: following the lesson in the white-box field that "the lack of adaptive attack evaluation leads to overestimated robustness" (Athalye et al., 2018), providing an adaptive attack benchmark for SDM to test future stateful defenses.
How does the paper address this problem?
OARS treats the SDM's rejection behavior as an oracle: first binary-search to fine-tune the sampling distribution parameters (adapt), then use rejection sampling to avoid collisions (resample), modifying three components of the attack.
Overall idea: SDMs block attacks by rejecting "similar" queries, and their accept/reject behavior itself leaks information about similarity detection. OARS (Oracle-guided Adaptive Rejection Sampling) treats the SDM as an oracle and adopts a two-stage adapt + resample strategy: first fine-tune the parameters of the parametric proposal distribution so that the collision rate of sampled queries falls below a threshold, then perform rejection sampling from that distribution, discarding colliding queries and resampling replacement queries.
Problem setting and SDM abstraction
- The paper formalizes an SDM as six components (Figure 1): a classifier F, a feature extractor h, a query library Q, a similarity process s, an action function action, and collision determination; actions fall into two categories: rejecting queries (Blacklight, PIHA, IIoT-SDA) and banning accounts (OSD).
- Attack goal: for a victim sample xvic, find xadv such that f(xadv) ≠ y and ||xadv − xvic|| ≤ ϵ; CIFAR10/ImageNet/CelebaHQ use ε=0.05 for ℓ∞ and normalized ℓ2, IIoT uses ε=0.2, and the query budget is 100k.
Adaptive modifications to the three attack stages
- Estimating the gradient: the original attack samples from a fixed distribution (e.g., NES's N(0, σ²I)); OARS keeps the distribution form and treats parameters (e.g., σ) as tunable, using the oracle-guided binary search of Algorithm 1 within [σ_lo, σ_hi] to find the optimal parameter that makes the collision rate below cr, then performs rejection sampling per Algorithm 2 to obtain n valid samples (retrying at most getries times, continuing as long as there is at least 1 valid sample).
- Step size: the original attack uses a fixed step size (e.g., NES's λ·sgn(∇L)); OARS constructs a proposal distribution for the step size (λ-scaled Rademacher for NES, uniform on a sphere of radius λ for HSJA), likewise fine-tunes λ via binary search and then samples.
- Locating the boundary: the original attack performs binary interpolation between the current point and the victim sample; OARS defines a binary search φ(r) with a termination distance r, fine-tunes the upper bound a using a uniform proposal distribution U(0,a), and on failure reuses the second-to-last query from the previous search for resampling.
Diagnostic test for defense types
- For account-banning defenses such as OSD, the paper designs a two-step diagnostic: account A repeatedly queries input x until it is detected; then account B queries the same x, and if it is detected, the defense is judged to be a global query library, otherwise per-account. The cost is the number of queries needed for detection on A, one extra query on B, and one extra account.
Specific application to the six attacks
- OARS-NES: modifies gradient estimation and step size (Table 2 summarizes which stages are modified for each attack; Square has no gradient estimation stage).
- OARS-Square: fine-tunes the proposal distribution of the "minimum number of squares needed to avoid collision" for each square size.
- OARS-HSJA / OARS-QEBA: modifies gradient estimation, step size, and boundary location; QEBA is modified the same way as HSJA.
- OARS-SurFree: modifies the polar-coordinate step size and final boundary location; OARS-Boundary: modifies the tuning of two hyperparameters, η_δ (random-direction step size) and η_ε (backtracking distance).
- Key parameters (Table 8, Appendix B): the binary search stps is mostly 5–10 steps, the per-point sampling sam is mostly 20, and the target collision rate cr is mostly 0 or 0.05; hyperparameters are set per dataset and do not change with the SDM, and the authors state that selecting hyperparameters for each dataset requires a one-time cost of about 1000 queries.
What experiments did the paper conduct?
Evaluated on 4 datasets, 4 SDMs, and 6 attacks: the authors report that for every dataset×defense combination, some OARS attack achieves an ASR above 99%.
Experimental setup
- Defenses and models tested: Blacklight and PIHA are evaluated on CIFAR10 (ResNet-20, 91.73%), ImageNet (ResNet-152, 78.31%), CelebaHQ (ResNet-152, 89.55%); OSD only on CIFAR10; IIoT-SDA on IIoT Malware (5 Conv + FC, 97.46%) (Table 3).
- Attacks: NES, Square (ℓ∞ score-based), HSJA, QEBA, SurFree, Boundary (ℓ2 hard-label); NES, HSJA, QEBA are targeted, the rest untargeted.
- Attack configurations: two baselines, standard and query-blinding, and three configurations of this paper, standard+resample, query-blinding+resample, adapt+resample (full OARS), five in total.
- Defense configurations: default configurations—Blacklight window 20 (CIFAR10) or 50, quantization step 50, threshold 0.5; PIHA block 7x7, threshold 0.05; OSD 50 nearest neighbors, threshold 1.44; IIoT-SDA 11 nearest neighbors, threshold 0.21.
- Metrics and samples: ASR and average number of queries (averaged only over successful attacks); 100 samples per configuration, targeted attack target classes uniformly random; CIFAR10 additionally has extended results with 1000 samples (Table 9). Query budget 100k.
Main results
Table 4 (ASR / number of queries, listing only adapt+resample, i.e., full OARS, and the standard baseline; "—" means the baseline had no successful samples due to collisions):
Swipe horizontally to read the table
Dataset Defense Attack Standard OARS CIFAR10 Blacklight NES 0% / — 99% / 1540 CIFAR10 Blacklight Square 0% / — 93% / 218 CIFAR10 Blacklight HSJA 0% / — 82% / 1615 CIFAR10 Blacklight QEBA 0% / — 98% / 1294 CIFAR10 Blacklight SurFree 0% / — 81% / 145 CIFAR10 Blacklight Boundary 0% / — 98% / 3302 ImageNet Blacklight NES 0% / — 100% / 10551 CelebaHQ PIHA QEBA 0% / — 100% / 6984 (Table 4 has 4 datasets × 2 defenses × 6 attacks in total; the remaining rows are omitted here; in the full table, the lowest OARS cell is OARS-Boundary against IIoT-SDA on IIoT Malware at 30% / 398.)
- The authors state that the standard and query-blinding baselines have ASR below 5% except in a few cases such as Square, and Blacklight is 0% against all standard attacks.
- The authors state that under the full OARS configuration, most attacks exceed 80% ASR and many exceed 90%, and every dataset×defense combination has at least one attack reaching over 99%.
- The resample-only configuration improves substantially on Square and SurFree (e.g., SurFree against PIHA on ImageNet and CelebaHQ reaches 100%), but shows no clear improvement on NES, HSJA, QEBA; the authors therefore consider both the adapt and resample mechanisms important.
Attacks on OSD (account-banning type)
- After using a diagnostic test to determine that OSD is per-account, standard attacks are run directly (Table 5): the six attacks all achieve 98%–100% ASR, with Square averaging 2 accounts and SurFree 3, while NES uses 18 and HSJA 21; the diagnostic cost of about 50 additional queries and 1 additional account is already included.
Defense reconfiguration and integration
- Raising the threshold: When the Blacklight threshold is raised from 0.5 to 0.7, the authors report that the false positive rate rises from 0.2% to 0.9% (about 1 million tiny images), and all attacks still have ASR above 63%; Figure 3 shows that the pairwise distances of attack queries shift right as the threshold increases, and the authors state that the attack automatically increases query spacing.
- Changing feature extractor hyperparameters (Table 6, CIFAR10, 5 (w,q) configurations of Blacklight): under each configuration some attack reaches 99% ASR, and all attacks have ASR no lower than 80%.
- Replacing the feature extractor and integration: Replacing Blacklight's feature extractor with PHash or PDQ, OARS-NES still reaches 99% and 96% ASR; under the Blacklight+PIHA integration (Table 7, CIFAR10), OARS-Square 95%, OARS-QEBA 91%, OARS-Boundary 89%, and standard attacks are all 0%.
Attack cost and preliminary text-domain experiments
- The authors report that most OARS attacks complete within 10,000 queries; at MLaaS pricing of $1–1.5 per thousand queries, the additional cost is at least under $1 and at most about $18 (HSJA attacking ImageNet, hard-label targeted setting).
- Text domain (§5.2): The authors first verify that Blacklight reduces TextFooler's ASR against a BERT classifier from 100% to 0% (100 samples); then they transfer the OARS idea to text (parameterizing the proposal distribution by edit distance λ), reporting 78% ASR and an average perturbation of 20% of words, and state that improving ASR and reducing the perturbation proportion are left for future work.
Other ablations and analyses
- CIFAR10 1000-sample extension (Table 9, against Blacklight): OARS-NES 96%, Square 93%, HSJA 86%, QEBA 97%, SurFree 83%, Boundary 99%, standard all 0%.
- Query overhead factors (§5.5): The authors state that more classes and higher input dimensions increase overhead; overhead may also depend on the specific SDM, but the number of existing SDMs is insufficient to draw a conclusion.
- Exception: OARS-Boundary on IIoT Malware achieves only 30% ASR, lower than the other OARS attacks in the same table; the paper gives no explanation.
What are some points that can be further explored?
In Limitations, the authors state that transfer attacks and detection methods such as AAA and AdvMind were not considered; the text domain and defense countermeasures have only preliminary results.
Limitations and future directions noted by the authors
- Transfer attacks were not considered (§5.6 Limitations): the authors consider transfer attacks an orthogonal problem, and existing dedicated defenses can be combined with stateful systems.
- Other black-box attack detection methods such as AAA and AdvMind were not evaluated (§5.6): the authors state that they are orthogonal to SDM, which detects similar queries.
- Choosing an ideal feature extractor for SDM remains difficult (§5.1): PHash and PDQ did not bring robustness improvements, and the authors leave this for future work.
- Action functions with randomized responses and SDM integration require deeper research before being practical (§5.1): the authors note that randomized responses may produce anomalous behavior, and integration raises the false positive rate.
- OARS in the text domain is only preliminarily validated (§5.2): the authors leave improving ASR and reducing the proportion of perturbed words for future work.
- The authors hope OARS becomes a benchmark for testing future SDM (§6 Conclusion).
Scope of experimental coverage
- The defenses tested are four in total: Blacklight, PIHA, IIoT-SDA, OSD; the classification models tested are ResNet-20, ResNet-152, 5 Conv + FC (Table 3), and the text experiments additionally use a BERT classifier.
- The attacks cover five configurations of six black-box attacks; the datasets are CIFAR10, ImageNet, CelebaHQ, IIoT Malware, and the text domain is a preliminary experiment on IMDB.
- Each configuration evaluates 100 samples, and CIFAR10 additionally has 1000 samples (Table 9); the paper does not report the number of repeated experiments.
- Defense reconfiguration experiments are done only on CIFAR10 against Blacklight (threshold, window/quantization step, switching to PHash/PDQ, integration with PIHA).
- The relationship between query overhead and SDM type: the authors state that more SDMs are needed to draw a conclusion (§5.5).
Summarize the main content of the paper
OARS uses the rejection signals leaked by SDMs to perform adaptive rejection sampling; the authors report that under its enhanced attacks, the ASR of four SDMs rose from near 0% to near 100%.
A paper on adaptive black-box attacks against stateful defenses (SDM). SDM defends against black-box attacks by tracking query history and rejecting similar queries; Blacklight et al. previously reported 0% ASR against existing attacks.
- Problem: The authors draw an analogy to the lesson in the white-box field that "the lack of adaptive evaluation leads to overestimated robustness," and propose that the action module of SDM leaks information about similarity detection that attackers can exploit.
- Method: OARS has two stages—the adapt stage uses the SDM as an oracle to binary-search and fine-tune the parameters of the attack sampling distribution (such as Gaussian variance σ and step size λ), and the resample stage performs rejection sampling from the fine-tuned distribution and discards colliding queries; based on this, it modifies three components of the attack—gradient estimation, step size, and boundary localization—and applies it to six attacks: NES, Square, HSJA, QEBA, SurFree, Boundary.
- Main results: On CIFAR10, ImageNet, CelebaHQ, IIoT Malware against Blacklight, PIHA, IIoT-SDA, the authors report that every dataset×defense combination has at least one OARS attack reaching over 99% ASR (Table 4), while the standard and query-blinding baselines are mostly below 5%; for OSD, which bans accounts, after a diagnostic test they run standard attacks, and the six attacks achieve 98%–100% ASR, requiring as few as 2 accounts (Table 5).
- Defense-side evaluation: Raising the Blacklight threshold increases the false positive rate from 0.2% to 0.9% while ASR remains above 63%; changing feature extractor hyperparameters, switching to PHash/PDQ, and integrating with PIHA all fail to stop OARS (e.g., OARS-Square 95% under integration).
- Cost: The authors report that most attacks complete within 10,000 queries, with additional cost of about $1–18 at MLaaS pricing.
- Authors' conclusion: Existing SDM is not as robust as previously thought, and OARS can serve as a benchmark for testing future stateful defenses; transfer attacks and other detection methods were not included in the evaluation, and the text domain has only preliminary results (78% ASR).
Related papers
- No Free Efficiency: Revisiting the Trade-off Between Training Efficiency and Model VulnerabilityAnalysis / interpretabilityarXiv
Show 3 more papers
- Theoretically Principled Trade-off for Stateful Defenses against Query-Based Black-Box AttacksAnalysis / interpretabilityarXiv