Randomization matters. How to defend against strong adversarial attacks

2020/02/26 by Rafaël Pinot, Raphael Ettedgui, Pinot, Rafael +7 · 2 citations
Computer Science · #Advanced Malware Detection Techniques #Adversarial Robustness in Machine Learning #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Physical Unclonable Functions (PUFs) and Hardware Security

paper · pdf · doi:10.48550/arxiv.2002.11565

openalex publication_date 2020/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Is there a classifier that ensures optimal robustness against all adversarial attacks? This paper answers this question by adopting a game-theoretic point of view. We show that adversarial attacks and defenses form an infinite zero-sum game where classical results (e.g. Sion theorem) do not apply. We demonstrate the non-existence of a Nash equilibrium in our game when the classifier and the Adversary are both deterministic, hence giving a negative answer to the above question in the deterministic regime. Nonetheless, the question remains open in the randomized regime. We tackle this problem by showing that, undermild conditions on the dataset distribution, any deterministic classifier can be outperformed by a randomized one. This gives arguments for using randomization, and leads us to a new algorithm for building randomized classifiers that are robust to strong adversarial attacks. Empirical results validate our theoretical analysis, and show that our defense method considerably outperforms Adversarial Training against state-of-the-art attacks.

Citations

• Feature Squeezing Mitigates and Detects Carlini/Wagner Adversarial Examples
• Minimax Statistical Learning with Wasserstein Distances
• On Evaluating Adversarial Robustness
• On the Hardness of Robust Classification
• Lower Bounds on Adversarial Robustness from Optimal Transport
• On Adaptive Attacks to Adversarial Example Defenses
• EMPIR: Ensembles of Mixed Precision Deep Networks for Increased Robustness against Adversarial Attacks
• Learning Multiple Layers of Features from Tiny Images

Cited by

• Lattice Climber Attack: Adversarial attacks for randomized mixtures of classifiers
• Towards provable probabilistic safety for scalable embodied AI systems

Related

• Robust Attacks against Multiple Classifiers
• On the robustness of randomized classifiers to adversarial examples
• Theoretical evidence for adversarial robustness through randomization
• Game Theory for Adversarial Attacks and Defenses
• Unveiling the Role of Randomization in Multiclass Adversarial Classification: Insights from Graph Theory