PaperlayerView exact revision on arXiv

Source-linked AI summary

Stateful Detection of Black-Box Adversarial Attacks

Steven Chen, Nicholas Carlini, David Wagner

arXiv:1907.05587v1cs.CRcs.LG

TL;DR

Adversarial examples remain difficult to defend against, especially when attackers query remote black-box classifiers. The paper proposes stateful query-history defenses that detect adversarial-example generation and introduces query blinding as an adaptive attack. The defense detects existing attacks and remains secure against query blinding, while its scope excludes model-extraction and arbitrary-error attacks.

  • Problem

    Existing adversarial-example defenses are difficult to make robust, motivating alternatives to stateless detection in black-box settings.

  • Method

    The paper monitors query histories with a similarity detector and develops query blinding to evaluate adaptive evasion of stateful defenses.

  • Results

    Stateful detection reliably detects existing black-box attacks, with at least 200 detections on average, and remains secure against query blinding.

  • Takeaways & Limitations

    Stateful defenses expand black-box defense options and can combine with defenses against zero-query attacks to support broader protection.

  • Takeaways & Limitations

    The defense assumes secret model parameters and only prevents attacks seeking an adversarial example near a specific image.

Abstract

from arXiv · show

The problem of adversarial examples, evasion attacks on machine learning classifiers, has proven extremely difficult to solve. This is true even when, as is the case in many practical settings, the classifier is hosted as a remote service and so the adversary does not have direct access to the model parameters. This paper argues that in such settings, defenders have a much larger space of actions than have been previously explored. Specifically, we deviate from the implicit assumption made by prior work that a defense must be a stateless function that operates on individual examples, and explore the possibility for stateful defenses. To begin, we develop a defense designed to detect the process of adversarial example generation. By keeping a history of the past queries, a defender can try to identify when a sequence of queries appears to be for the purpose of generating an adversarial example. We then introduce query blinding, a new class of attacks designed to bypass defenses that rely on such a defense approach. We believe that expanding the study of adversarial examples from stateless classifiers to stateful systems is not only more realistic for many black-box settings, but also gives the defender a much-needed advantage in responding to the adversary.

1 INTRODUCTION

The paper reframes black-box adversarial-example defense as a stateful problem: monitoring query histories can detect attack generation rather than classifying individual inputs. It proposes a similarity-based detector, adaptive query blinding, and defenses that remain effective against both existing and adaptive attacks.

  • 1 INTRODUCTION: Black-box defenses matter because remote classifiers expose outputs without model parameters, while adversarial examples remain difficult to defend against reliably.The paper motivates this setting through safety-critical deployments and the shortcomings of prior defenses.
  • 1 INTRODUCTION: Stateful detection monitors query sequences to identify adversarial-example generation, rather than statelessly classifying individual inputs.The central hypothesis is that attack-query sequences differ detectably from benign-use sequences.
  • 1 INTRODUCTION: A similarity-detector neural network identifies highly self-similar query patterns used by existing black-box attacks.The strategy can compose with existing defenses for defense-in-depth.
  • 1 INTRODUCTION: Query blinding preprocesses inputs to resemble benign data while preserving enough information to deduce classifier outputs, targeting defenses that monitor query sequences.The paper introduces query blinding as a general adaptive attack strategy.
  • 1 INTRODUCTION: The proposed defense detects existing attacks and remains secure against query blinding when attackers adapt to the detection strategy.This evaluates both direct attack detection and resistance to an adaptive evasion strategy.

2 BACKGROUND & PROBLEM STATEMENT

The paper studies query-based adversarial-example attacks against remotely hosted, hard-label image classifiers, where defenders can retain query history but not observe offline computation. Its approach exploits the local similarity of iterative attack queries, while complementing defenses for zero-query transfer attacks.

  • 2 BACKGROUND & PROBLEM STATEMENT: An adversarial example is a minimally modified input that changes the neural network’s classification relative to the original input.The paper formalizes this using a distance constraint and differing model outputs.
  • 2 BACKGROUND & PROBLEM STATEMENT: Query-based black-box attacks use gradient-free optimization, iteratively querying nearby perturbations because gradients are unavailable and labels alone must guide the attack.NES and BoundaryAttack are presented as examples of this sequential strategy.
  • 2 BACKGROUND & PROBLEM STATEMENT: In the black-box threat model, attackers query a remote classifier and receive labels, while model weights and parameters remain secret.The setting assumes account creation has a practical cost and measures defense effectiveness by detections before successful attack generation.
  • 2 BACKGROUND & PROBLEM STATEMENT: Tracking query history can detect attacks through anomalously close successive queries, unlike defenses that classify individual inputs.The approach is feasible when the defender observes online queries but not an attacker’s offline computation.
  • 2 BACKGROUND & PROBLEM STATEMENT: Zero-query transfer attacks operate offline, so the paper’s query-monitoring defense cannot protect against them and must be complemented by defenses such as Ensemble Adversarial Training.The paper positions query-based and zero-query defenses as complementary components.

3 OUR SCHEME

The scheme monitors each user's query history and flags sequences whose queries are unusually close in a learned perceptual embedding space. It combines stateful detection, low false-positive thresholding, and compact query representations to detect attacks while limiting storage costs.

  • 3.1 The Query Detection Defense: The detector stores each user's recent query encodings, computes each new query's mean distance to its k nearest prior queries, and flags unusually close sequences.The monitor can respond by clearing the buffer or blocking the user's account after detection.
  • 3.2 Similarity Encoder: A learned similarity encoder maps perceptually similar images nearby, making encoded-space distance more suitable than raw pixel ℓ2 distance for adversarial-query detection.The encoder is trained with contrastive loss so positive pairs are close and negative pairs are separated by a margin.
  • 3.2 Similarity Encoder: The encoded representation addresses raw-pixel distance's sensitivity to small transformations and reduces storage because it is lower-dimensional than the original image.The paper notes that storing complete queried images can impose storage costs and privacy risks.
  • 3.4 Encoder Training and Threshold Selection: For CIFAR-10, the authors select k = 50 because the threshold rises sharply up to about 50 and then largely plateaus, while larger k increases computation and delays possible detection.CIFAR-10 is used because it is common in adversarial-example research and enables less expensive experimentation than ImageNet.

4 NON-ADAPTIVE EVALUATION

The evaluation tests the defense against representative gradient-estimation and boundary-following black-box attacks under a targeted ℓ∞ distortion constraint. Unmodified attacks eventually succeed, but the scheme detects them frequently enough to impose substantial account costs.

  • 4.1 Attack Setup: The evaluation covers one representative gradient-estimation attack and one representative boundary-following attack, using default unmodified implementations.NES estimates gradients through repeated queries, whereas Boundary Attack follows the classifier's decision boundary.
  • 4.1 Attack Setup: Both attacks are targeted and count as successful when they reach the target class within ℓ∞ distortion ε = 0.05 of the original image.Each attack is terminated as soon as it finds an example satisfying this condition.
  • 4.2 Results: At least 200 detections occur on average before each unmodified attack produces a successful adversarial example, despite attacks eventually succeeding at high rates.Under the account-oriented setting, this means an attacker would need at least 200 accounts to generate one adversarial example with these attacks.

5 QUERY BLINDING

The paper develops query blinding to hide adversarial-query sequences from stateful detectors while preserving access to classifier outputs. It combines randomized transformations, learned auto-encoders, and diversity-based filtering to reduce detection.

  • Query Blinding: Query blinding hides the query sequence from the defender while allowing the attacker to infer the classifier output for a target input.The strategy pre-processes inputs so they resemble benign data patterns while retaining enough information to deduce the classifier’s output.
  • Query Blinding: Randomized image transformations such as noise, translation, and rotation serve as blinding functions because distorted images retain primary content and produce similar outputs.For image transformations, the revealing function can directly use the classifier output on a transformed image.
  • Auto-Encoder Attack: A randomized auto-encoder is trained to make transformed examples far apart while keeping their classifier outputs close to the original.Its loss combines output-distribution similarity with a distance-promoting term, using cross-entropy, a relative-weight constant, and a target distance.
  • Auto-Encoder Attack: The auto-encoder is trained for 10 epochs on CIFAR-10 using a separate classifier trained on 10% of the data, with c = 1 and d = 10 selected in practice.The threshold d = 10 balances fooling the detector against preserving the original classifier output.
  • Improving Query Blinding: Generating many blinded images can create near-duplicates through the birthday paradox, so the attack filters or resamples candidates to promote diversity.Candidate queries can be represented as graph nodes, with edges connecting pairs whose distance would trigger detection; the resulting selection avoids problematic pairs.
  • Improving Query Blinding: Although the defense uses an encoder rather than direct ℓ2 distance, diversity-based filtering still reduces detections by promoting attack-sample diversity.

6 ADAPTIVE ATTACK EVALUATION

Adaptive query blinding can reduce detection effectiveness, but the defense continues to detect all evaluated attack families and cannot be completely defeated.

  • Adaptive attack evaluation: The defense remained effective against adaptive gradient, boundary-following, and hybrid attacks, although attackers could degrade its effectiveness.The evaluation covers NES variants, Boundary Attack variants, and a surrogate-model hybrid attack.
  • 6.1.2 Query Blinding: At least 100 detections occurred for every NES query-blinding transformation, while brightness and pixel-scale transformations sometimes improved attack success and uniform or Gaussian noise failed completely.The results indicate that transformation choice affects gradient-estimation quality, but does not eliminate detection.
  • 6.1.2 Query Blinding: Higher-distortion transformations produced 6–8× more detections with the similarity encoder than with image ℓ2 distance, increasing attacker cost.Higher distortion also required more queries because gradient estimates became less precise.
  • 6.1.2 Query Blinding: The auto-encoder attack was more effective than simple transformations and defeated image-ℓ2 detection more readily, but the full similarity-encoder defense still detected it.The auto-encoder was trained to produce same-label images with large ℓ2 distortion.
  • 6.2 The Boundary Attack: Boundary-attack variants were less effective than the original because preprocessing could cause premature convergence, while the defense required 200 accounts for one adversarial example.Brightness preprocessing reduced attack success without reducing detections.
  • 6.3 Hybrid Query Based Surrogate Attack: The hybrid surrogate attack achieved a modest non-trivial success rate with 3–8× fewer detections, but no evaluated attack completely defeated the defense.Its targeted version failed, so evaluation focused on untargeted attacks targeting the next-most-likely class.

7 ECONOMICS OF PERFORMING AN ATTACK

The paper estimates that avoiding detection can impose substantial time, query, and account costs on attackers, while buffer storage remains relatively inexpensive for providers.

  • Case 1: time-bounded buffer: With a 100-hour time-bounded buffer, the strongest evaluated attack would take over a year to generate one adversarial example without detection.The NES auto-encoder attack triggered 97 detections, and each detection adds the buffer duration when the attacker avoids detection.
  • Case 1: time-bounded buffer: Provider storage for a 100-hour buffer would cost at most $0.14 per user per month under the stated Cloud Vision rate-limit example.Storing 10.8M 256-dimensional vectors in 16-bit precision requires 5.5GB.
  • Case 2: query-bounded buffer: For a query-bounded buffer, an attacker can flush the last N queries with N random queries before an expected detection, making total effort about dN queries for d detections.This strategy assumes the attacker knows which queries would trigger detection.
  • Case 2: query-bounded buffer: A query-bounded buffer of N = 10^4 would raise the strongest attack’s cost to about $1500 per adversarial image, versus about $20 without the defense.The estimate assumes Google Cloud Vision pricing of $1.50 per 1000 queries and approximately 97 × 10^4 queries.

8 ZERO QUERY DEFENSE

The stateful query-detection defense complements zero-query defenses rather than replacing them, and remains effective when combined with ensemble adversarial training.

  • Zero-query defense: The defense cannot detect zero-query attacks because those attacks operate entirely offline, so the paper combines it with ensemble adversarial training.The combined design targets both query-based and transfer-based zero-query threats.
  • Zero-query defense: Ensemble adversarial training made the defended model noticeably more robust to all three evaluated transfer attacks, with a clean-accuracy decrease.The reported robustness was obtained at ϵ = 0.05.
  • Zero-query defense: On the EAT-defended model, the stateful scheme still frequently detected query-based attacks, and EAT appeared to reduce their success rate.The paper reran its best query-based attack variants on the EAT-defended model.

9 RELATED WORK

The paper positions stateful query-history detection as a complement to difficult stateless defenses and existing defenses for white-box and zero-query attacks.

  • Detection approaches: PRADA also uses query history, but its image-ℓ2 distance test is vulnerable to query blinding, motivating the paper’s similarity-encoder approach.The comparison highlights why the defense uses learned similarity rather than only raw image distances.
  • Detection approaches: Prior stateless defenses inspect individual inputs, whereas this paper monitors query history to detect sequences associated with black-box attack generation.The paper identifies limited prior work on defenses against query-based attacks.
  • Complementary defenses: The proposed detector is complementary to white-box defenses such as adversarial training and can be applied on top of an existing model.The paper studies the defense on a non-robust model to isolate the value of stateful detection.
  • Black-box attack families: Query-based attacks commonly use gradient estimation or boundary following, so related attacks such as SPSA and Boundary++ share the core patterns targeted by the defense.These attacks differ in implementation and efficiency but retain the same high-level query strategies.
  • Complementary defenses: Transfer attacks address the zero-query setting, and the paper combines its query-history defense with ensemble adversarial training to cover both threat types.The two defenses address distinct attack mechanisms.

10 LIMITATIONS AND FUTURE WORK

The defense has important scope boundaries: it assumes secret model weights, was evaluated on image recognition and hard-label queries, and targets attacks near a specific image. Future work includes broader domains, stronger query-blinding robustness, and defenses for model extraction.

  • The defense is ineffective if an attacker learns the model weights, leaving model-extraction attacks as an open detection problem.
  • Its evaluation covers image recognition, motivating tests in other application domains with domain-specific similarity encoders.
  • The defense targets adversarial examples near a specific image; random search can instead find arbitrary misclassified inputs, requiring about 13 trials for a 92%-accurate CIFAR-10 classifier.
  • The constructed auto-encoder attack specifically targets this defense, so future defenses may detect that transformation even though query blinding remains a broader research direction.
  • The defense was evaluated only in the hard-label setting, while soft-label outputs expose difficulties that the current scheme does not address.
  • Adversarial training of the similarity encoder and query-blinding auto-encoder may improve robustness, but this remains future work.

11 CONCLUSION

The paper argues that black-box defenses should move beyond stateless input screening toward stateful detection of adversarial-example generation. It presents stateful detection as a potential unified source of black-box robustness when combined with defenses against transferability attacks.

  • The paper argues that stateful defenses give black-box defenders a new advantage beyond the stateless defenses previously studied.
  • The proposed scheme detects the process of adversarial-example generation and can combine with transferability defenses to form a unified black-box defense.

A CNN ARCHITECTURE

This appendix section supplies implementation and query-budget details for the CNN-based similarity encoder and the comparison of low- and high-sample query-blinding settings.

  • Table 6 specifies the three-layer CNN architecture used for the similarity encoder and hybrid attack.
  • The transformation tables distinguish low-distortion settings with expected ℓ2 = 2.32 from high-distortion settings with expected ℓ2 = 5.10.
  • Reducing samples per confidence-score estimate from s = 50 to s = 2 lowers expected detections but may reduce score accuracy, while increasing s raises both success chances and query-based detections.

C ENSEMBLE ADVERSARIAL TRAINING

The soft-label case uses query blinding to disguise classifier queries while recovering outputs through local behavior, exposing a setting where the hard-label detector can be bypassed.

  • The soft-label attack blinds an input with paired random-direction perturbations and uses a revealing procedure to recover the classifier output.
  • The attack relies on neural networks behaving locally like linear functions despite global nonlinearity.
  • Averaging estimates across multiple random directions improves accuracy, and the resulting soft-label NES variant succeeds against the query-based detector.
  • Figure 5 compares attack success and detection rates as the samples-per-estimate parameter varies from s = 2 to s = 50.
Loading 1907.05587v1…