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:
- 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.
- Ensemble Training: A separate "base" classifier (like a deep neural network) is trained exclusively on each partition.
- 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.
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.
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