# Theoretically Principled Trade-off for Stateful Defenses against Query-Based Black-Box Attacks

arXiv: https://arxiv.org/abs/2307.16331 · HTML: https://mlsanity.com/paper/2307.16331/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 23 references that are in the map.
- First posted on arXiv 30 Jul 2023.

## Builds on (most cited first, 15 of 15)

- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Practical Black-Box Attacks against Machine Learning](https://mlsanity.com/paper/1602.02697/) (2016)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Square Attack: a query-efficient black-box adversarial attack via random search](https://mlsanity.com/paper/1912.00049/) (2019)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [Understanding and Mitigating the Tradeoff Between Robustness and Accuracy](https://mlsanity.com/paper/2002.10716/) (2020)
- [QEBA: Query-Efficient Boundary-Based Blackbox Attack](https://mlsanity.com/paper/2005.14137/) (2020)
- [SurFree: a fast surrogate-free black-box attack](https://mlsanity.com/paper/2011.12807/) (2020)
- [Stateful Detection of Black-Box Adversarial Attacks](https://mlsanity.com/paper/1907.05587/) (2019)
- [Invisible Perturbations: Physical Adversarial Examples Exploiting the Rolling Shutter Effect](https://mlsanity.com/paper/2011.13375/) (2020)
- [Blacklight: Scalable Defense for Neural Networks against Query-Based Black-Box Attacks](https://mlsanity.com/paper/2006.14042/) (2020)
- [GRAPHITE: Generating Automatic Physical Examples for Machine-Learning Attacks on Computer Vision Systems](https://mlsanity.com/paper/2002.07088/) (2020)

## Built on by (most cited first, 2 of 2)

- [AdvQDet: Detecting Query-Based Adversarial Attacks with Adversarial Contrastive Prompt Tuning](https://mlsanity.com/paper/2408.01978/) (2024)
- [Adversarial Observations in Weather Forecasting](https://mlsanity.com/paper/2504.15942/) (2025)

## Abstract (arXiv)

Adversarial examples threaten the integrity of machine learning systems with alarming success rates even under constrained black-box conditions. Stateful defenses have emerged as an effective countermeasure, detecting potential attacks by maintaining a buffer of recent queries and detecting new queries that are too similar. However, these defenses fundamentally pose a trade-off between attack detection and false positive rates, and this trade-off is typically optimized by hand-picking feature extractors and similarity thresholds that empirically work well. There is little current understanding as to the formal limits of this trade-off and the exact properties of the feature extractors/underlying problem domain that influence it. This work aims to address this gap by offering a theoretical characterization of the trade-off between detection and false positive rates for stateful defenses. We provide upper bounds for detection rates of a general class of feature extractors and analyze the impact of this trade-off on the convergence of black-box attacks. We then support our theoretical findings with empirical evaluations across multiple datasets and stateful defenses.