Deep Partition Aggregation: Provable Defenses against General Poisoning Attacks

Alexander Levine, Soheil FeiziICLR 2021 · OpenReview

Most machine learning models are vulnerable to poisoning attacks, where an adversary injects malicious data into the training set to manipulate the model's behavior at test time. While many empirical defenses exist, they often fail against new, adaptive attacks.

To counter this, researchers focus on certified defenses. Unlike a standard defense that "usually works," a certified defense provides a mathematical guarantee—a "certificate"—for a specific test input. This certificate acts as a lower bound on how many training samples an attacker would have to change to successfully flip the model's prediction. Before this paper, certified defenses were largely limited to simple linear models or specific, narrow attack types (like only changing labels).

This paper introduces Deep Partition Aggregation (DPA), providing robust, provable protection for deep neural networks against general data corruption, achieving state-of-the-art certified robustness against both general poisoning (adding/deleting samples) and label-flipping attacks.

The Core Mechanism: Deep Partition Aggregation (DPA)

The foundation of the authors' approach is an ensemble strategy designed to isolate the impact of poisoned data:

  1. Deterministic Partitioning: The training set is split into $k$ disjoint partitions. To ensure this split is "stable" (meaning the addition of a new sample doesn't reshuffle the entire dataset), the authors use a deterministic hash function or a sorting mechanism based on the data values themselves. This ensures a poisoned sample only "infects" its own designated partition.
  2. Ensemble Training: A separate "base" classifier (like a deep neural network) is trained exclusively on each partition.
  3. Plurality Voting: At inference time, all $k$ models predict the class of a test image. The final output is the class with the most votes.

The "Aha!" Moment: Because the partitions are disjoint, a single poisoned sample can only ever affect one base model in the ensemble. If the top-voted class has a lead of 10 votes over the runner-up, an attacker would need to poison at least 5 different partitions (requiring at least 5 malicious samples) to potentially flip the result. Unlike previous "randomized smoothing" techniques that rely on probabilistic guarantees, DPA is deterministic, allowing for exact certificates without statistical sampling.

Semi-Supervised DPA (SS-DPA) for Label-Flipping

The authors also introduce Semi-Supervised DPA (SS-DPA) specifically for label-flipping attacks. In this scenario, the images themselves are "trustworthy," even if the labels aren't. Base models are trained using semi-supervised learning: they see the entire unlabeled training set but only have access to the labels within their specific partition. This allows the models to learn better features from the clean, unlabeled data while maintaining the partition-based safety margin.

Key Results and Performance

The authors evaluated their methods on three standard computer vision benchmarks: MNIST, CIFAR-10, and GTSRB (German Traffic Sign Recognition Benchmark). The proposed methods significantly outperformed previous state-of-the-art (SOTA) certified defenses.

Defending Against Label-Flipping Attacks

SS-DPA demonstrated massive improvements in certified robustness against label-flipping. On the MNIST dataset, SS-DPA certified that 50% of test images would remain correct even if over 600 labels were flipped. The previous SOTA could only certify fewer than 200 flips.

Certified accuracy of SS-DPA against label-flipping attacks on MNIST.

Similarly, on CIFAR-10, SS-DPA certified over 300 label flips for half the test set, nearly doubling the previous SOTA of 175.

Defending Against General Poisoning

Crucially, DPA provided the first-ever certificates for general attacks (inserting or deleting images entirely). On MNIST, it successfully certified 50% of images against 500+ insertions.

Certified accuracy of DPA against general poisoning attacks (insertions/deletions) on MNIST.

On the more complex CIFAR-10 dataset, it could certify 50% of images against 9 insertions. For GTSRB, the model certified 50% of images against 176 label flips or 20 general poisoning insertions.

Limitations and Future Directions

While DPA and SS-DPA establish new benchmarks for certified robustness, they come with a fundamental robustness-accuracy trade-off. Increasing the number of partitions ($k$) makes the model more robust (yielding larger certificates), but it also means each base model is trained on less data, which can hurt individual model accuracy.

Additionally, training an ensemble of $k$ models (where $k$ can be 1000+) is computationally expensive. While these can be trained in parallel, it remains a high barrier for very large datasets or massive models. For highly complex tasks like ImageNet, the base models might become too weak to provide a useful plurality vote when the data is partitioned so heavily.

Future work may explore more sophisticated semi-supervised techniques to further bridge the gap between clean accuracy and certified robustness, as well as optimizing the partitioning logic to better handle high-dimensional data.

Summary updated

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 (inference) attacks. Our defense against label-flipping poison 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 (Rosenfeld et al., 2020) 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 $\geq$ 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 general and label-flipping poison attacks. Code is available at https://github.com/alevine0/DPA
BibTeX
@inproceedings{levine2021deep,
  author = {Alexander Levine and Soheil Feizi},
  title = {{Deep Partition Aggregation: Provable Defenses against General Poisoning Attacks}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=Rp_qdaUYzZ-},
}
Figure