PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Partition Aggregation: Provable Defense against General Poisoning Attacks

Alexander Levine, Soheil Feizi

arXiv:2006.14768v2cs.LGstat.ML

TL;DR

Poisoning attacks can corrupt test-time classifications by changing training data, motivating certificates for individual test samples. The paper introduces DPA for general insertions and deletions and SS-DPA for label flips, achieving stronger label-flip certificates and the first certified defense for broadly defined general poisoning attacks.

  • Problem

    Existing certified poisoning defenses are limited across threat models, while pointwise guarantees are needed for individual test samples.

  • Method

    DPA hashes training samples into partitions and aggregates classifiers trained separately on them; SS-DPA additionally uses all unlabeled data for label-flip attacks.

  • Results

    Over 600 MNIST label flips and over 300 CIFAR-10 label flips are certified for at least half of test images, while DPA certifies over 500 MNIST and nine CIFAR-10 insertions or deletions.

  • Takeaways & Limitations

    The methods provide deterministic, neural-network-compatible certificates and extend certified poisoning defenses to a broadly defined general attack model.

  • Takeaways & Limitations

    The general-poisoning analysis assumes the attack is bounded by training-set insertions or deletions, and the SS-DPA theorem assumes no repeated unlabeled samples with different labels.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper develops certified defenses that provide per-test-sample guarantees against poisoning, covering both general training-set insertions/deletions and label flips. DPA partitions data by deterministic hashing, while SS-DPA exploits trustworthy unlabeled data to improve label-flip certificates.

  • Threat models: Certified poisoning defenses lower-bound the training-set distortion required to change an individual test sample’s classification.The paper distinguishes these pointwise certificates from guarantees about average test accuracy.
  • Threat models: General poisoning permits bounded sample insertions or deletions and includes arbitrary image or label distortions through removal and insertion.A sample distortion or label flip increases symmetric-difference attack magnitude by two.
  • DPA: DPA hashes each training sample into one of k partitions, trains one classifier per partition, and aggregates their plurality predictions.Adding or removing a sample changes only one partition and therefore one base classifier, enabling certification.
  • SS-DPA: SS-DPA uses the entire unlabeled training set while restricting each base classifier to labels from its own partition.This modified technique applies when the adversary flips labels but unlabeled data remains trustworthy.
  • Results: Over 600 label flips are certified for at least half of MNIST test images with over 93% accuracy, compared with fewer than 200 flips for the prior method.On CIFAR-10, SS-DPA certifies over 300 label flips for at least half of test images versus 175 for Rosenfeld et al. (2020).
  • Results: Over 500 general poisoning insertions or deletions are certified for at least half of MNIST images, while CIFAR-10 supports nine.The paper presents this as the first certified defense against its broadly defined general poisoning threat model.

2 RELATED WORKS

The paper distinguishes DPA from prior ensemble, smoothing, and distributional approaches by providing deterministic, pointwise poisoning certificates with deep neural network implementations.

  • Ensemble defenses: Unlike bootstrap and subset aggregation, DPA assigns each sample to one partition, preventing the same poisoned point from affecting multiple base classifiers.This partition structure yields deterministic robustness certificates rather than only improving empirical generalization.
  • Randomized smoothing: Prior randomized-smoothing poisoning defenses certify only clean-label attacks under bounded L2 distortions of training data.DPA instead targets a more broadly defined poisoning threat model.
  • Distributional guarantees: Distributional poisoning analyses guarantee average accuracy under shared-data-distribution assumptions but do not guarantee robustness for specific test samples.The paper’s certificates are pointwise rather than distributional.

3 PROPOSED METHODS

DPA partitions training data deterministically and aggregates classifiers trained on disjoint partitions, yielding certificates against general poisoning. SS-DPA adapts this design for label flips by using unlabeled data and label-stable sorted partitions.

  • 3.2 DPA: DPA partitions the training set with a deterministic hash function and trains one base classifier on each partition.Partitions are formed by h(t) mod k, with roughly uniform hashing preferred.
  • 3.2 DPA: At inference, DPA counts each base classifier's predicted class and returns the ensemble consensus with deterministic tie-breaking.The class count n_c(x) determines the consensus output.
  • 3.2 DPA: DPA certifies that the prediction remains c whenever the poisoned and clean training sets differ by at most the sample-specific certified radius.The guarantee covers the symmetric-difference magnitude |T ⊖ U|.
  • 3.2 DPA: DPA is deterministic randomized ablation with disjoint partitions, enabling exact finite-sample certificates and invariance to training-data reordering.Each classifier retains only one partition, unlike randomized independent sampling.
  • 3.3 SS-DPA: SS-DPA trains semi-supervised base classifiers using the entire unlabeled dataset plus labels from a partition, with sorted-index partitioning stabilizing label flips.The inference procedure remains the same as standard DPA.
  • 3.3 SS-DPA: SS-DPA certifies prediction c when at most the sample-specific certified number of training labels are changed, assuming no repeated unlabeled samples with different labels.Without that assumption, the analysis is more complicated.

4 RESULTS

Experiments evaluate DPA and SS-DPA on MNIST, CIFAR-10, and GTSRB using certified accuracy and median certified robustness. SS-DPA improves label-flip certificates over the existing certificate, while DPA certifies substantial general-poisoning budgets; increasing ensemble size trades accuracy for robustness.

  • Label-flipping results: 392 label flips on CIFAR-10 versus 175, and 645 on MNIST versus < 200, are the median certificates achieved by SS-DPA over the existing certificate.These comparisons use the existing certificate of Rosenfeld et al. (2020).
  • General-poisoning results: Over 500 poisoning insertions or deletions on MNIST, and 9 on CIFAR-10, are certified for at least half of the test images with DPA.These are general-poisoning certificates measured by symmetric difference.
  • GTSRB results: 20 poisoning insertions or deletions, or 176 label flips, are certified for over half of GTSRB images.The paper notes that this represents a larger fraction of each class than the CIFAR-10 certificates because GTSRB classes have fewer training images on average.
  • Robustness–accuracy trade-off: Larger ensemble size k tends to increase robustness certificates but decrease base and final ensemble accuracy, creating a robustness–accuracy trade-off.With k classifiers, the largest possible certified robustness is k/2.
  • Binary MNIST: 95.5% clean accuracy and certified robustness to 5952 label flips are achieved for every correctly classified image in specialized binary-MNIST SS-DPA.The comparison baseline reports 94.5% clean accuracy and best certified accuracy below 70%.

5 CONCLUSION

The paper introduces provable defenses against poisoning attacks that provide exact, deterministic certificates and work with deep neural networks. These defenses outperform prior certified label-flip defenses and extend certification to broadly defined general poisoning attacks.

  • The method provides exact, deterministic certificates for poisoning robustness and can be implemented with deep neural networks.

A PROOFS

The proofs establish robustness certificates for DPA and SS-DPA under their respective poisoning models. DPA preserves the prediction when the poisoned set differs by at most the certified magnitude, while SS-DPA does so under bounded label changes.

  • DPA: DPA certifies the prediction for any poisoned training set U satisfying |T ⊖ U| ≤ ¯ρ(x).
  • DPA: The DPA proof bounds the number of affected partitions by the symmetric-difference attack magnitude.The hash-based partition mapping limits the number of changed ensemble classifiers to at most ¯ρ(x).
  • SS-DPA: SS-DPA certifies the prediction when at most ¯ρ samples in T have their labels changed.At most ¯ρ ensemble classifiers are affected because each changed label belongs to one partition.
  • SS-DPA: The SS-DPA proof relies on identical sorted samples and invariant partition assignments under label-flipping attacks.

B BINARY MNIST EXPERIMENTS

A binary MNIST experiment applies SS-DPA with one labeled sample per partition and cluster-based semi-supervised classifiers. The resulting classifier achieves high clean accuracy while certifying robustness to thousands of label flips.

  • The SS-DPA experiment sets k = m, so each partition contains one label, and uses 2-means clustering on unlabeled MNIST data.
  • Each base classifier assigns labels by comparing whether the test image and its partition’s labeled image belong to the same cluster.
  • 95.5% clean accuracy is achieved, with every correctly classified image certified robust to 5952 label flips.The certified accuracy is also 95.5% at 5952 label flips, corresponding to 45.8% of the training data.
  • Rosenfeld et al. report 94.5% clean accuracy and less than 70% best certified accuracy for up to 2000 label flips.

C RELATIONSHIP TO RANDOMIZED ABLATION

DPA replaces randomized, independently sampled training subsets with deterministic, disjoint partitions. This enables exact finite-ensemble certificates while retaining comparable poisoning bounds when the number of attacks is small relative to the partition count.

  • Deterministic disjoint partitions avoid the estimation error and failure probability associated with randomized finite ensembles.
  • Randomized Ablation requires a large randomized ensemble to estimate class probabilities with high confidence.
  • For label flipping, SS-DPA bounds the poisoned-classifier proportion using a union bound over disjoint partitions.The bound assumes each flipped label can affect a different partition in the worst case.
  • When the number of flips is small relative to the number of partitions, the deterministic union-bound estimate is close to an independence-based estimate.
  • Unlike arbitrary partitioning for training-time poisoning, prior patch-attack derandomization exploits geometric constraints on the attacked image.

D RELATIONSHIP TO EXISTING ENSEMBLE METHODS

DPA and SS-DPA relate to classical ensemble methods but differ in partition structure and robustness objectives. SS-DPA’s sorting-based partitioning improves base accuracy and does not reduce median certified robustness relative to hashing.

  • Classical ensemble methods: Subagging independently samples subsets, whereas DPA uses disjoint partitions rather than allowing multiple classifiers to share samples.Subagging typically uses large subsets for accuracy, while DPA uses many small partitions to support certification.
  • Classical ensemble methods: Bagging may repeat samples across classifiers and has been proposed empirically for poisoning defense, but not for certified robustness.
  • Related distributed learning: Federated Averaging also trains models on disjoint partitions, but averages and redistributes weights without theoretical robustness guarantees.
  • SS-DPA partitioning: Sorting partitions SS-DPA more evenly and consistently yields higher base classifier accuracy while increasing or preserving median certified robustness.These effects are larger on MNIST than on CIFAR-10.
  • SS-DPA partitioning: Hashing on MNIST mainly decreases certified robustness without significantly changing clean smoothed accuracy.The sorting method may produce more correlated but more accurate base classifiers.

F EFFECT OF RANDOM SEED SELECTION

The experiments compare shared and distinct training seeds across DPA and SS-DPA. Distinct seeds usually improve smoothed clean accuracy, with the clearest gain for SS-DPA on MNIST.

  • Robustness effects: Seed choice has no large, consistent effect on base accuracy or median certified robustness across experiments.
  • Accuracy effects: Distinct random seeds usually produce higher smoothed classifier accuracy than using the same seed, and always do so for DPA.
  • Accuracy effects: On MNIST, distinct seeds increase SS-DPA smoothed accuracy by at least 1% for every tested partition count k.
  • Correlation mechanism: Shared seeds can make base classifiers more correlated, increasing the chance that they misclassify the same sample.The proposed explanation involves identical random cropping patterns across small training sets.
  • Dataset dependence: The seed effect is least significant for SS-DPA on CIFAR-10 and GTSRB with SimCLR.The authors suggest this may relate to using linear final supervised classifiers rather than deep networks.

G SS-DPA WITH REPEATED UNLABELED DATA

SS-DPA’s formal data model addresses repeated samples with differing labels, but its implementation assumes repeated sample values do not occur. The experiments use histogram equalization as a dataset-specific preprocessing variant for GTSRB.

  • Repeated samples: The formal training-set definition permits repeated samples with differing labels, which complicates the definition of label-flipping attacks.The issue does not arise in the datasets used for the experiments.
  • Implementation boundary: SS-DPA’s implementation does not handle repeated sample values and verifies their absence before sorting the training set.
  • Formal data model: The formalism can merge repeated samples into one sample with a set of associated labels, thereby disallowing repeated sample values in T.
  • Partition invariance: Partition assignment depends only on sample values, so label flips leave an unlabeled sample and its associated labels in the same partition.
  • GTSRB preprocessing: On GTSRB, histogram equalization substantially improves performance at k = 100 but has a modest effect at k = 50.At k = 50, it increases clean accuracy by 2.64% and certified robustness by 3.

I SIMCLR EXPERIMENTAL DETAILS

The SimCLR experiments use deterministic training with dataset-specific batch sizes and a ResNet18 embedding model. Linear ensemble classifiers are then trained separately with their own optimization settings, while GTSRB images are resized for training and testing.

  • Embedding training: SimCLR embeddings use ResNet18, batch size 512 for CIFAR-10 and 256 for GTSRB, learning rate 0.5, cosine annealing, temperature 0.5, and 1000 epochs.
  • Classifier training: The linear ensemble classifiers use batch size 512, learning rate 1.0, and 100 training epochs.
  • Image preprocessing: GTSRB images are resized to 48 × 48 with bilinear interpolation for training and testing.Sorting for SS-DPA uses original-image pixel values with black padding for smaller images.
Loading 2006.14768v2…