Deep Partition Aggregation: Provable Defense against General Poisoning Attacks

Abstract

Adversarial poisoning attacks distort training data in order to corrupt the test-time behavior of a classifier. A provable defense provides a certificate for each test sample, which is a lower bound on the magnitude of any adversarial distortion of the training set that can corrupt the test sample's classification. We propose two novel provable defenses against poisoning attacks: (i) Deep Partition Aggregation (DPA), a certified defense against a general poisoning threat model, defined as the insertion or deletion of a bounded number of samples to the training set -- by implication, this threat model also includes arbitrary distortions to a bounded number of images and/or labels; and (ii) Semi-Supervised DPA (SS-DPA), a certified defense against label-flipping poisoning attacks. DPA is an ensemble method where base models are trained on partitions of the training set determined by a hash function. DPA is related to both subset aggregation, a well-studied ensemble method in classical machine learning, as well as to randomized smoothing, a popular provable defense against evasion attacks. Our defense against label-flipping attacks, SS-DPA, uses a semi-supervised learning algorithm as its base classifier model: each base classifier is trained using the entire unlabeled training set in addition to the labels for a partition. SS-DPA significantly outperforms the existing certified defense for label-flipping attacks on both MNIST and CIFAR-10: provably tolerating, for at least half of test images, over 600 label flips (vs. < 200 label flips) on MNIST and over 300 label flips (vs. 175 label flips) on CIFAR-10. Against general poisoning attacks, where no prior certified defenses exists, DPA can certify >= 50% of test images against over 500 poison image insertions on MNIST, and nine insertions on CIFAR-10. These results establish new state-of-the-art provable defenses against poisoning attacks.

ICLR 2021

References in corpus (13)

• A Simple Framework for Contrastive Learning of Visual Representations
• Semi-Supervised Learning with Deep Generative Models
• Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning
• Poisoning Attacks against Support Vector Machines
• Certified Adversarial Robustness via Randomized Smoothing
• Supervised Contrastive Learning
• (De)Randomized Smoothing for Certifiable Defense against Patch Attacks
• RAB: Provable Robustness Against Backdoor Attacks
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness
• Randomized Smoothing of All Shapes and Sizes
• Certified Robustness to Label-Flipping Attacks via Randomized Smoothing
• Random Smoothing Might be Unable to Certify ${\ell }_{\infty }$ Robustness for High-Dimensional Images
• Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks

Cited by in corpus (8)

• Adversarial Unlearning of Backdoors via Implicit Hypergradient
• Adversarial Neuron Pruning Purifies Backdoored Deep Models
• DP-InstaHide: Provably Defusing Poisoning and Backdoor Attacks with Differentially Private Data Augmentations
• Rethinking the Backdoor Attacks' Triggers: A Frequency Perspective
• SoK: Machine Learning Governance
• Robust learning under clean-label attack
• On Provable Backdoor Defense in Collaborative Learning
• Certifying Robustness to Programmable Data Bias in Decision Trees