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.
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.
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