PAC-learning in the presence of evasion adversaries

Abstract

The existence of evasion attacks during the test phase of machine learning algorithms represents a significant challenge to both their deployment and understanding. These attacks can be carried out by adding imperceptible perturbations to inputs to generate adversarial examples and finding effective defenses and detectors has proven to be difficult. In this paper, we step away from the attack-defense arms race and seek to understand the limits of what can be learned in the presence of an evasion adversary. In particular, we extend the Probably Approximately Correct (PAC)-learning framework to account for the presence of an adversary. We first define corrupted hypothesis classes which arise from standard binary hypothesis classes in the presence of an evasion adversary and derive the Vapnik-Chervonenkis (VC)-dimension for these, denoted as the adversarial VC-dimension. We then show that sample complexity upper bounds from the Fundamental Theorem of Statistical learning can be extended to the case of evasion adversaries, where the sample complexity is controlled by the adversarial VC-dimension. We then explicitly derive the adversarial VC-dimension for halfspace classifiers in the presence of a sample-wise norm-constrained adversary of the type commonly studied for evasion attacks and show that it is the same as the standard VC-dimension, closing an open question. Finally, we prove that the adversarial VC-dimension can be either larger or smaller than the standard VC-dimension depending on the hypothesis class and adversary, making it an interesting object of study in its own right.

arXiv comment14 pages, 2 figures (minor changes to biblatex output)

References in corpus (27)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Ensemble Adversarial Training: Attacks and Defenses
• 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
• Poisoning Attacks against Support Vector Machines
• Provable defenses against adversarial examples via the convex outer adversarial polytope
• Adversarially Robust Generalization Requires More Data
• On the (Statistical) Detection of Adversarial Examples
• Adversarial Examples Are Not Easily Detected: Bypassing Ten Detection Methods
• A study of the effect of JPG compression on adversarial images
• Defensive Distillation is Not Robust to Adversarial Examples
• MagNet: a Two-Pronged Defense against Adversarial Examples
• Houdini: Fooling Deep Structured Prediction Models
• Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach
• MagNet and "Efficient Defenses Against Adversarial Attacks" are Not Robust to Adversarial Examples
• Delving into adversarial attacks on deep policies
• Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning
• Adversarial Examples that Fool Detectors
• Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
• Adversarial Examples for Semantic Image Segmentation
• Shield: Fast, Practical Defense and Vaccination for Deep Learning using JPEG Compression
• Defending against Adversarial Images using Basis Functions Transformations
• Adversarial Spheres
• Adversarial examples for generative models
• Training Ensembles to Detect Adversarial Examples

Cited by in corpus (13)

• Rademacher Complexity for Adversarially Robust Generalization
• Adversarially Robust Generalization Just Requires More Unlabeled Data
• The Limitations of Adversarial Training and the Blind-Spot Attack
• Adversarial Examples - A Complete Characterisation of the Phenomenon
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Recent Advances in Adversarial Training for Adversarial Robustness
• Probabilistic Margins for Instance Reweighting in Adversarial Training
• Adversarial Examples on Object Recognition: A Comprehensive Survey
• Lower Bounds for Adversarially Robust PAC Learning
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Calibration and Consistency of Adversarial Surrogate Losses
• Adversarially Robust Low Dimensional Representations
• Towards Deep Learning Models Resistant to Large Perturbations