Abstract
Defending machine-learning (ML) models against white-box adversarial attacks has proven to be extremely difficult. Instead, recent work has proposed stateful defenses in an attempt to defend against a more restricted black-box attacker. These defenses operate by tracking a history of incoming model queries, and rejecting those that are suspiciously similar. The current state-of-the-art stateful defense Blacklight was proposed at USENIX Security '22 and claims to prevent nearly 100% of attacks on both the CIFAR10 and ImageNet datasets. In this paper, we observe that an attacker can significantly reduce the accuracy of a Blacklight-protected classifier (e.g., from 82.2% to 6.4% on CIFAR10) by simply adjusting the parameters of an existing black-box attack. Motivated by this surprising observation, since existing attacks were evaluated by the Blacklight authors, we provide a systematization of stateful defenses to understand why existing stateful defense models fail. Finally, we propose a stronger evaluation strategy for stateful defenses comprised of adaptive score and hard-label based black-box attacks. We use these attacks to successfully reduce even reconfigured versions of Blacklight to as low as 0% robust accuracy.
Introduction
In the realm of machine learning security, black-box adversarial attacks represent a significant threat. In these scenarios, an adversary lacks access to the model's internal weights and must rely on querying the model to find adversarial examples—inputs designed to fool the AI while appearing normal to humans. To counter this, researchers introduced Stateful Defense Models (SDMs). These defenses were initially viewed as a "silver bullet," designed to block sequences of similar queries that typically characterize a black-box attack. However, this paper introduces OARS (Oracle-guided Adaptive Rejection Sampling), a strategy that demonstrates how these defenses can be systematically evaded.
The Architecture of Stateful Defenses
Stateful defenses operate on the principle of query history tracking. By maintaining a record of past interactions, the system can identify and reject queries that are "too similar" to previous ones, effectively halting the iterative probing required for many black-box attacks.
As illustrated in the pipeline above, an image query is transformed into a feature representation. A similarity procedure then compares this representation against a query store. If a "collision" is detected—meaning the query is suspiciously similar to a previous one—an action function triggers a rejection or an account ban. If no collision occurs, the query is passed to the classifier.
OARS: Turning Rejections into Information
The core insight of this research is that a rejection from an SDM is not merely a failed query; it is a valuable data point. OARS treats the stateful defense as an "oracle," using its rejection signals to learn the internal similarity thresholds. The OARS strategy consists of two main phases:
- Adapt (Fine-tuning the Proposal Distribution): The attacker employs a binary search to identify the optimal parameters—such as noise standard deviation or step size—that allow queries to remain as close as possible to the target image without triggering a rejection.
- Resample (Rejection Sampling): Once the distribution is tuned, the attacker generates queries. If the SDM rejects a query, the attacker simply discards it and samples again until a query is accepted.
This principled approach allows OARS to be integrated into various black-box attacks, including score-based methods like NES and hard-label methods like HSJA.
Systematization and Evaluation
To evaluate the robustness of SDMs, the authors systematized the current defensive landscape. The defenses vary significantly in their implementation details, which influences how an attacker must adapt.
As shown in the table above, defenses like Blacklight and PIHA utilize global query stores and Hamming distance metrics, while others like OSD and IIoT-SDA use per-account stores and $\ell_2$ distance. Despite these variations, the OARS framework proved capable of adapting to each configuration.
Key Results and Economic Impact
The experimental results provide a stark contrast to previous claims of SDM robustness. Against Blacklight, which previously reported a 0% attack success rate (ASR), OARS-enhanced attacks achieved near-perfect success:
- OARS-NES reached 99-100% ASR across multiple datasets, including CIFAR10 and ImageNet.
- OARS-Boundary and OARS-QEBA also achieved near-perfect success rates.
- Efficiency: Most attacks were completed within 10,000 queries, well under the standard research budget of 100,000.
Furthermore, the research highlights the low economic barrier to these attacks. On commercial Machine-Learning-as-a-Service (MLaaS) platforms, a successful attack using OARS would cost an adversary between only $1 and $18.
Conclusion and Future Work
Stateful defenses are inherently "leaky" because they must provide a response—even if that response is a rejection. This leakage allows clever attackers to map the defense's internal metrics and bypass them. While SDMs increase the complexity of an attack, they do not provide the robust security once hoped for. Future research should explore more aggressive account-banning strategies and defensive randomization, as well as how these adaptive attacks scale to non-image domains like audio and video.
Summary updated