Randomness in ML Defenses Helps Persistent Attackers and Hinders Evaluators

Keane Lucas, Matthew Jagielski, Florian Tramèr, Lujo Bauer, Nicholas CarliniarXiv 2023 · DOI · arXiv

Introduction

In the adversarial machine learning landscape, randomness is often deployed as a defensive shield. The intuition is straightforward: by introducing stochasticity into model transformations, defenders hope to prevent "white-box" attackers from calculating precise adversarial perturbations. However, this paper challenges that intuition, arguing that randomness frequently serves as a "security through obscurity" crutch. Far from strengthening a model, randomness can introduce new vulnerabilities while complicating the task of honest evaluation.

The Nag Factor Threat Model

The authors introduce a critical vulnerability called the Nag Factor. In this threat model, a persistent attacker is allowed to query a randomized defense multiple times with the same input. While a randomized model might correctly classify an adversarial image 99% of the time, the attacker only needs a single failure to succeed.

Conceptual illustration of the Nag Factor vulnerability in randomized defenses.

As shown in the figure above, a deterministic defense (bottom) provides a consistent response, forcing the attacker to find a truly robust failure point. In contrast, a randomized defense (top) might eventually yield a misclassification through sheer repetition, even if the input remains unchanged.

Methods: Isolating the Effect of Randomness

To determine if randomness itself provides robustness, the researchers developed deterministic versions of three prominent defenses: Randomized Smoothing, Energy-Based Model Defense (EBM-Def), and Diffusion Models (DiffPure). By fixing the random seed for every prediction, they ensured that the transformations (like noise addition) were identical for every query, effectively removing stochasticity while preserving the underlying mechanism.

Additionally, they introduced a Subspace Grid-sweep tool. This evaluation method performs brute-force searches for adversarial examples within low-dimensional subspaces (1–6 dimensions). This approach is designed to bypass "obfuscated gradients"—messy loss surfaces created by some defenses that hinder standard gradient-based optimization without actually removing adversarial holes.

Key Insights: The Self-Ensembling Secret

A core finding of the study is that the robustness of defenses like Randomized Smoothing does not stem from randomness. Instead, it arises from self-ensembling: the aggregation of multiple transformed versions of an image. The researchers demonstrated that this effect persists even when the noise patterns are fixed and deterministic.

Furthermore, deterministic defenses are inherently more "honest." By removing the noise in the gradients caused by randomness, researchers can use more reliable tools to verify if a defense is truly robust or merely masking its weaknesses.

Empirical Results

The experiments, primarily conducted on the CIFAR-10 dataset, yielded several striking results:

  • Randomized Smoothing: The robust accuracy of deterministic and randomized versions converged rapidly. With as few as five fixed corruptions, the deterministic version matched the performance of the original randomized defense.
  • DiffPure: A version using only two alternating fixed seeds achieved 83% robust accuracy, nearly matching the 88% of the fully randomized original. This suggests that high-entropy randomness is largely unnecessary.
  • Nag Factor Evidence: Empirical testing confirmed that the robust accuracy of randomized defenses declines as the number of attack repeats increases, whereas deterministic defenses maintain a constant level of robustness.
Robust accuracy comparison showing the self-ensembling effect (left) and the Nag Factor vulnerability (right).

The figure above illustrates these two key points: the left plot shows how robustness improves with more corruptions (self-ensembling), while the right plot shows the steady decline of randomized defense accuracy under repeated attacks (the Nag Factor).

Limitations and Future Work

While the empirical evidence favors deterministic defenses, there is a theoretical trade-off. Randomized Smoothing provides "provable robustness certificates" based on stochasticity. Making the defense deterministic removes these mathematical guarantees, even if empirical robustness remains high.

Future research directions include:

  • Analyzing how an attacker's knowledge of specific fixed seeds impacts success rates.
  • Evaluating the benefits of randomness against black-box attacks, where the attacker lacks internal model access.
  • Encouraging the community to provide deterministic versions of all new randomized defenses to ensure they can be properly stress-tested.

Summary updated

Abstract

It is becoming increasingly imperative to design robust ML defenses. However, recent work has found that many defenses that initially resist state-of-the-art attacks can be broken by an adaptive adversary. In this work we take steps to simplify the design of defenses and argue that white-box defenses should eschew randomness when possible. We begin by illustrating a new issue with the deployment of randomized defenses that reduces their security compared to their deterministic counterparts. We then provide evidence that making defenses deterministic simplifies robustness evaluation, without reducing the effectiveness of a truly robust defense. Finally, we introduce a new defense evaluation framework that leverages a defense's deterministic nature to better evaluate its adversarial robustness.
BibTeX
@misc{lucas2023randomness,
  author = {Keane Lucas and Matthew Jagielski and Florian Tramèr and Lujo Bauer and Nicholas Carlini},
  title = {{Randomness in ML Defenses Helps Persistent Attackers and Hinders Evaluators}},
  year = {2023},
  eprint = {2302.13464},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.13464},
}
Figure