Query complexity of adversarial attacks
arXiv:2010.01039
Abstract
There are two main attack models considered in the adversarial robustness literature: black-box and white-box. We consider these threat models as two ends of a fine-grained spectrum, indexed by the number of queries the adversary can ask. Using this point of view we investigate how many queries the adversary needs to make to design an attack that is comparable to the best possible attack in the white-box model. We give a lower bound on that number of queries in terms of entropy of decision boundaries of the classifier. Using this result we analyze two classical learning algorithms on two synthetic tasks for which we prove meaningful security guarantees. The obtained bounds suggest that some learning algorithms are inherently more robust against query-bounded adversaries than others.
arXiv comment32 pages, 2 figures Generalized the results. Adversarial examples no longer need to be in the support of the data distribution
References in corpus (16)
- Feature Squeezing: Detecting Adversarial Examples in Deep Neural Networks
- ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
- Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples
- Delving into Transferable Adversarial Examples and Black-box Attacks
- Adversarially Robust Generalization Requires More Data
- Adversarial Attacks and Defences: A Survey
- Adversarial Risk and the Dangers of Evaluating Against Weak Attacks
- Black-box Adversarial Attacks with Limited Queries and Information
- Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
- Adversarial examples from computational constraints
- Rademacher Complexity for Adversarially Robust Generalization
- Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability
- VC Classes are Adversarially Robustly Learnable, but Only Improperly
- Adversarial Spheres
- Adversarial Examples from Cryptographic Pseudo-Random Generators
- Black-box Certification and Learning under Adversarial Perturbations