A Theoretical Trade-off for Stateful Defenses Against Query-Based Black-Box Attacks
Theoretically Principled Trade-off for Stateful Defenses against Query-Based Black-Box Attacks
The authors theoretically characterize the trade-off between detection rate and false positive rate in stateful defenses, give an upper bound on the detection rate, and empirically validate on Blacklight and PIHA using TinyImages and ImageNet.
- Stateful defenses resist black-box adversarial attacks by detecting similar queries, but there is a trade-off between detection rate and false positive rate; existing defenses rely on manually tuning the threshold and lack a formal understanding of this trade-off.
- The authors first derive an upper bound on the detection rate under a toy model with a quantized feature extractor plus a Gaussian query distribution (Theorem 3.1), then generalize to Lipschitz continuous feature extractors (Theorem 3.2), and empirically validate with Blacklight and PIHA on TinyImages and ImageNet.
- Figure 2 shows that under each setting there is a trade-off between detection rate and false positive rate, and that the trade-off worsens as β increases; Figure 3 shows that PIHA's distance ratio distribution is more spread out and its detection rate is higher; Figure 4 shows that although increasing β lowers the detection rate, the estimated gradient direction is also worse.
- The paper does not specifically discuss limitations. The experiments cover only two feature extractors, Blacklight and PIHA, and two datasets, TinyImages and ImageNet; αdet is computed on 100 images, and αf p for PIHA on ImageNet is extrapolated using 100k images; the paper does not report the classification model used in the attack convergence experiments.
- Threat model
- In the black-box setting, the attacker has only query access to the model and constructs adversarial examples by submitting a large number of highly similar queries (e.g., Gaussian perturbation sampling for finite-difference gradient estimation); the victim system is an image classifier deployed with a stateful defense (maintaining a query buffer and detecting by a feature similarity threshold).
- Evaluated models
- BlacklightPIHA
- Benchmarks
- TinyImagesImageNet
- Metrics
- detection rate αdetfalse positive rate αf ploss change ratio
This work provides a theoretical characterization of the trade-off between detection rate and false positive rate when stateful defenses detect query-based black-box attacks. Stateful defenses detect attacks by caching recent queries and flagging new queries that are too similar to history; the authors derive an upper bound on the detection rate for a class of general feature extractors and analyze the impact of this trade-off on the convergence of black-box attacks. The theoretical results are experimentally verified on multiple datasets and multiple stateful defenses.
Paper analysis
What problem does this paper attempt to solve?
Stateful defenses have a trade-off between detection rate and false positive rate, but it lacks a formal characterization; the authors provide a theoretical characterization and empirical validation.
The trade-off between detection rate and false positive rate in stateful defenses lacks formal understanding; its formal limits and influencing factors remain unclear.
- Problem setting: Adversarial examples can threaten machine learning systems with high success rates even under black-box conditions (per the authors). Stateful defenses identify attacks by maintaining a buffer of recent queries and detecting new queries that are too similar; the authors describe this as a promising class of countermeasures.
- Shortcomings of existing methods: The authors point out that existing defenses typically adjust this trade-off by hand-picking feature extractors and empirically effective similarity thresholds, provide only empirical control of the false positive rate, and cannot provide any guarantee on the detection rate; little is known about which properties of the feature space and problem domain affect this trade-off.
- Core observation: Black-box attackers often submit large numbers of highly similar queries during optimization (e.g., querying neighboring points to estimate gradients), and stateful defenses exploit exactly this for detection; thus detecting attack queries and avoiding false positives are inherently in tension.
- Contributions of the paper: The authors give upper bounds on the detection rate for a general class of feature extractors (Theorem 3.1, 3.2), characterize how the trade-off depends on the attack query distribution, the natural query distribution, and the properties of the feature extractor, and analyze the effect of this trade-off on the convergence of black-box attacks (Theorem 4.1), then empirically validate on multiple datasets and defenses.
- Threat model:
- Attacker goal: construct an adversarial example xadv that causes the classifier to misclassify, with the perturbation constrained by an ℓp norm budget ϵ (Equation 1).
- Knowledge: black-box setting, where the attacker has only query access to the model.
- Capability: submit similar queries to collect information about model behavior, e.g., sampling neighboring points from a Gaussian distribution for finite-difference gradient estimation.
- Victim system: an image classifier deployed with a stateful defense, where the defense consists of the classifier f, the feature extractor H, the query store q, and the threshold τ.
What related research exists?
Related work falls into three groups: black-box attacks, stateful defenses against adversarial attacks, and stateful defenses against model stealing.
Black-box adversarial attacks
- NES (Ilyas et al., 2018), HSJA (Chen et al., 2020a), QEBA (Li et al., 2020) — sample neighboring points from a Gaussian (or similar) distribution and compute finite differences to estimate the gradient.
- SurFree (Maho et al., 2021), Square (Andriushchenko et al., 2020) — sample neighboring points to estimate a "random search" direction (rather than a gradient).
- The paper points out that what these attacks have in common is that they use similar queries to collect information about model behavior, which is exactly the feature exploited by stateful defenses.
Stateful defenses against adversarial attacks
- Blacklight (Li et al., 2022) — uses the Hamming distance of SHA-256 hashes of quantized pixels as similarity; the authors claim it reduces the ASR of several black-box attacks to as low as 0%.
- PIHA (Choi et al., 2023) — a detection method based on perceptual image hashing.
- SD (Chen et al., 2020b) — uses real-valued metrics such as the ℓ2 distance between embeddings from a neural similarity encoder.
- The paper points out that these defenses mainly control the trade-off by adjusting the similarity threshold, provide only empirical control of the false positive rate, and offer no guarantee on the detection rate; this paper evaluates Blacklight and PIHA because they are available on both CIFAR-10 and ImageNet.
Stateful defenses against model stealing
- SEAT (Zhang et al., 2021) — a defense that detects model-stealing queries; the authors claim it can force an attacker to create as many as 65 accounts to steal a single model; the authors argue that its success can likewise be explained by the submission of highly similar queries, and illustrate this with the query construction of the JBA attack (Papernot et al., 2017).
A similar trade-off in white-box defenses
- Tsipras et al. (2018), Yang et al. (2020), Raghunathan et al. (2020) — study the trade-off between robustness and accuracy in white-box defenses; the authors analogize the detection–false-positive trade-off of stateful defenses to this known trade-off.
The authors position this paper as: providing a formal characterization of the trade-off for the above empirical stateful defenses, explaining why some defenses work better against black-box attacks, and offering guidance for future defense design.
How does the paper address this problem?
First derive an upper bound on the detection rate under a toy model, then generalize to Lipschitz continuous feature extractors, and finally analyze the effect of the trade-off on attack convergence.
The overall approach is: use a toy model that can be explicitly characterized to give an upper bound on the relationship between detection rate and false positive rate, then relax the assumptions to obtain a general bound, and finally use empirical experiments to validate the theoretical corollaries. The object of analysis is the feature extractor H of stateful defenses and the query distribution, rather than a specific defense algorithm.
Problem setup
- Defense composition: classifier f, feature extractor H (with a distance metric), query store q, threshold τ; when the similarity between a new query and any query in q exceeds τ, a defensive measure is triggered (rejecting the query or banning the account).
- Attack query model: to estimate the gradient at input x, the attacker samples perturbations δ ∼ N (0, Id β²), i.e., Gaussian-based finite differences (following NES).
- Natural query model: natural images come from one of several Gaussian distributions uniformly spread over the input space, with each natural image drawn from a different distribution N (p, Id σ²); the authors state this is the "best case" for the defense.
Toy model (Theorem 3.1)
- Feature extractor: quantizer H(x) = ⌊x + 0.5⌋, outputting discrete features; a query is regarded as an attack query if and only if it produces exactly the same features as a previous query.
- Core conclusion: given a false positive rate αf p, the detection rate upper bound is αdet ≤ 1 − (2 − 2Φ(0.5β−1))d (1 − αfp), where Φ is the cumulative distribution function of the standard normal; the meaning is that lowering αf p also lowers the upper bound on αdet, and the larger β is, the lower the detection rate upper bound.
- Proof sketch: placing x at the center of a quantization bin minimizes the escape probability after adding δ; this decomposes the detection rate into the product of the probability that the perturbation leaves the bin and the uniqueness of the natural query's features.
Generalized analysis (Theorem 3.2)
- Relaxed assumptions: H is changed to a general perceptual feature extractor H : Rd → Ry, assumed to be Lipschitz continuous with constants KL and KU; detection becomes threshold-based, i.e., a query is judged an attack query when ||H(x) − H(xh)|| ≤ τ.
- Core conclusion: αdet ≤ 1/(Γ(d/2))γ(d/2, 1/2((KU MD)/(KL β))2 1/(1−αfp)), where MD = E[||x1 − x2||] is the expected spread of natural queries, and γ and Γ are the lower incomplete and complete Gamma functions respectively; the meaning is that the trade-off also depends on β, MD, and the Lipschitz constant ratio KU /KL.
- Proof sketch: use the Lipschitz lower bound to relate the detection event to ||δ|| ≤ τ/KL, use the Lipschitz upper bound and Markov's inequality to relate the false positive rate to ||x1 − x2|| ≤ τ/KU, and then combine them using the chi distribution CDF of the Gaussian norm.
Effect on attack convergence (Theorem 4.1)
- Form of the conclusion: the norm of the estimated gradient G·∇x falls within the (1±ϵ) interval of the true gradient norm with probability at least 1 − 2·exp(−k − (1+ϵ)/(2β²)), where k is the number of sampled rows and ϵ is the estimation error.
- Meaning: as β increases, this probability lower bound decreases, i.e., the estimated gradient is less likely to produce the same loss increase as the true gradient; the proof is in Appendix A.0.1.
Empirical validation design
- Feature extractors: Blacklight (pixels quantized into bins of size 50, sliding-window hashing, taking the top 50 hashes, with window size 20 for TinyImages and 50 for ImageNet) and PIHA (3x3 Gaussian low-pass filtering, conversion to HSV discarding S and V, 7x7 block sum-pooling, local binary patterns).
- Data: TinyImages (32x32, a superset of about 80 million images) and ImageNet (256x256, over 1 million images), each randomly sampling 1 million images.
- Three questions: Q1 the relationship between the trade-off and β; Q2 the relationship between the trade-off and KU /KL; Q3 the effect of the trade-off on attack convergence.
What experiments did the paper conduct?
Validate the relationship of the trade-off with β and the Lipschitz ratio on TinyImages and ImageNet, and analyze the effect of β on gradient estimation quality.
Experimental setup
- Subjects under test: the feature extractors of two stateful defenses, Blacklight and PIHA; the paper does not report the use of a specific classification model.
- Datasets: TinyImages and ImageNet, with 1 million images randomly sampled from each.
- Metrics: detection rate αdet, false positive rate αf p, Delta Loss Ratio.
- Computation: αf p is computed on 1 million images, but for PIHA on ImageNet, due to computational complexity, only 100,000 are used and extrapolated; αdet is computed on 100 images from Gaussian-sampled perturbations with different standard deviations β; each curve is obtained by varying the threshold τ.
- Lipschitz estimation: 10000 image pairs (x, x+δ) are constructed with β = 0.01, and the ratio of the feature-space ℓ2 distance to the input-space distance is computed.
- Number of repetitions: not reported in the paper.
Main results
The main results are presented as figures (Figure 2), with four subfigures: Blacklight-TinyImages, PIHA-TinyImages, Blacklight-ImageNet, and PIHA-ImageNet; each subfigure gives four curves such as β ∈ {0.001, 0.01, 0.02, 0.03} (Blacklight-TinyImages); the axes are αdet (horizontal axis) and αf p (vertical axis), ranging from 0 to 1. The converted text does not give specific data points on the curves and can only describe trends:
Setting Curves (β values) Trend (according to Figure 2) Blacklight + TinyImages 0.001, 0.01, 0.02, 0.03 Under each β, an increase in αdet is accompanied by an increase in αf p PIHA + TinyImages 0.001, 0.01, 0.02, 0.03 Same as above; the authors state that PIHA can achieve a higher αdet than Blacklight on low-dimensional TinyImages Blacklight + ImageNet 0.001, 0.005, 0.01, 0.02 Same as above PIHA + ImageNet 0.001, 0.01, 0.05, 0.1 Same as above - The authors state that for any β, obtaining a larger αdet requires increasing αf p, which is consistent with the corollaries of Theorem 3.1 and 3.2.
- The authors state that the αf p required to achieve the same αdet increases as β increases, i.e., the trade-off has an inverse relationship with β.
- The authors state that on ImageNet, when β exceeds 0.01, the performance of both extractors degrades.
Lipschitz constant ratio and trade-off (Q2)
- What was measured: the distribution of the feature-space/input-space distance ratio for Blacklight and PIHA on ImageNet, and the corresponding (αdet, αf p) trade-off curves (Figure 3, β = 0.01).
- Results: in Figure 3(a), PIHA's histogram distribution is more spread out than Blacklight's; in Figure 3(b), the PIHA-ImageNet trade-off curve lies above the BlackLight-ImageNet curve (the converted text shows only axes and legends, with no specific values).
- Authors' interpretation: a more spread-out distribution means a larger KU /KL, which according to Theorem 3.2 should yield a higher detection rate; the authors state this corroborates the empirical result of PIHA's higher detection rate.
Trade-off and attack convergence (Q3)
- What was measured: on the four defense × dataset combinations, the loss change induced by gradients estimated with different β (Figure 4, Delta Loss Ratio shown as color bands, with red indicating a large loss increase and blue indicating a small increase).
- Results: the range of each color band in Figure 4 varies by setting (e.g., Blacklight-TinyImages approximately 0.02–0.20, PIHA-ImageNet approximately 0.00–0.08); the authors state that for any given αf p, a larger β, while lowering the detection rate, also makes the estimated gradient worse for the attacker, i.e., the loss increase is smaller.
- Authors' interpretation: the worse trade-off caused by increasing β is not without cost to the attacker.
Other ablations and analyses
- PIHA's αf p on ImageNet is computed on only 100,000 images and extrapolated due to computational complexity, while all other settings use 1 million (Section 4.2).
- The Lipschitz constant ratio estimate uses β = 0.01 and 10000 image pairs (Section 4.3).
- The paper does not report other hyperparameter ablations or statistical significance tests.
What are some points that can be further explored?
The paper does not specifically discuss limitations; the experiments cover only two feature extractors and two image datasets, and some metrics are computed under small samples or extrapolation.
Limitations and future directions noted by the authors
- The paper does not include a Limitations or Future Work section and does not explicitly list limitations.
- In the Conclusion, the authors state that they hope their analysis can "help improve current strategies and potentially guide the design of future defenses," which is an outlook rather than a specific future direction.
- In Section 3.2, the authors point out that Theorem 3.2 assumes the feature extractor is continuous, whereas the feature extractors of Blacklight and PIHA are not continuous and are only designed to approximate perceptual similarity; therefore Section 4.3 can only resort to empirical estimates of KU and KL.
Scope of experiments
- The feature extractors evaluated are two, Blacklight and PIHA; the paper states they were chosen because both are available on CIFAR-10 and ImageNet (Section 4.1).
- The datasets are TinyImages and ImageNet, with 1 million images randomly sampled from each (Section 4.1).
- αdet is computed on 100 images; PIHA's αf p on ImageNet is computed on 100,000 images and extrapolated, while the remaining settings use 1 million (Section 4.2).
- The Lipschitz constant ratio is estimated with 10000 image pairs and β = 0.01 (Section 4.3).
- The paper does not report the classification model used in the attack convergence experiments, the complete attack algorithms (such as end-to-end runs of NES and HSJA), the number of repetitions, or statistical significance tests.
Summarize the main content of the paper
The authors give a theoretical upper bound for the detection–false positive trade-off of stateful defenses, and empirically validate it with Blacklight and PIHA on two image datasets.
This is a paper analyzing the theoretical properties of stateful defenses, supplemented by empirical validation, in the defense setting against query-based black-box adversarial attacks.
- Problem: stateful defenses identify attacks by detecting similar queries, but there is a trade-off between the detection rate αdet and the false positive rate αf p; existing defenses tune thresholds by hand and only control the false positive rate empirically, and the authors note that the formal limits of this trade-off and the factors affecting it remain unclear.
- Method: first give an upper bound on the detection rate under a toy model with a quantized feature extractor plus a Gaussian query distribution (Theorem 3.1), then generalize to Lipschitz-continuous feature extractors (Theorem 3.2), with the bound depending on the perturbation standard deviation β, the expected spread of natural queries MD, and the Lipschitz constant ratio KU /KL; Theorem 4.1 further shows that increasing β degrades gradient estimation quality.
- Result one: Figure 2 shows that across the four combinations Blacklight, PIHA × TinyImages, ImageNet, a trade-off between αdet and αf p exists at every β value, and the trade-off worsens as β increases; the authors state that PIHA can achieve a higher αdet than Blacklight on low-dimensional TinyImages, while when β exceeds 0.01 both worsen on ImageNet.
- Result two: Figure 3 shows that PIHA's distance-ratio distribution is more spread out than Blacklight's (implying a larger KU /KL), and PIHA's trade-off curve is higher, which the authors say is consistent with the prediction of Theorem 3.2.
- Result three: Figure 4 shows that for any given αf p, a larger β lowers the detection rate but also yields a smaller loss increase from the estimated gradient, which the authors say means the worsened trade-off is not without cost to the attacker.
- Authors' conclusion: the analysis can explain why some defenses work better against black-box attacks, helps improve existing strategies and may guide future defense design.