PaperlayerView exact revision on arXiv

Source-linked AI summary

Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks

Jinyuan Jia, Xiaoyu Cao, Neil Zhenqiang Gong

arXiv:2008.04495v7cs.CRcs.LG

TL;DR

Data poisoning threatens machine-learning models, while existing certified defenses have limited applicability or loose guarantees. This paper derives intrinsic certified robustness for bagging with arbitrary base learning algorithms and develops practical computation methods. It proves unchanged predictions under bounded poisoning, establishes tightness without base-learner assumptions, and reports 91.1% certified accuracy on MNIST under 100 poisoned training examples.

  • Problem

    Data poisoning can corrupt machine-learning models, while existing certified defenses are limited in scope and can provide loose robustness guarantees.

  • Method

    The paper analyzes bagging, derives a certified poisoning size, and develops algorithms to compute it in practice.

  • Results

    The method proves unchanged predictions under bounded poisoning, proves tightness without assumptions on the base learning algorithm, and achieves 91.1% certified accuracy on MNIST with 100 arbitrarily poisoned training examples.

  • Takeaways & Limitations

    Bagging provides certified robustness against modifying, deleting, and inserting training examples, with empirical evaluations on MNIST and CIFAR10.

  • Takeaways & Limitations

    The tightness claim applies when no assumptions on the base learning algorithm are made, and existing comparisons include defenses with restricted attack or algorithm settings.

Abstract

from arXiv · show

In a \emph{data poisoning attack}, an attacker modifies, deletes, and/or inserts some training examples to corrupt the learnt machine learning model. \emph{Bootstrap Aggregating (bagging)} is a well-known ensemble learning method, which trains multiple base models on random subsamples of a training dataset using a base learning algorithm and uses majority vote to predict labels of testing examples. We prove the intrinsic certified robustness of bagging against data poisoning attacks. Specifically, we show that bagging with an arbitrary base learning algorithm provably predicts the same label for a testing example when the number of modified, deleted, and/or inserted training examples is bounded by a threshold. Moreover, we show that our derived threshold is tight if no assumptions on the base learning algorithm are made. We evaluate our method on MNIST and CIFAR10. For instance, our method achieves a certified accuracy of $91.1\%$ on MNIST when arbitrarily modifying, deleting, and/or inserting 100 training examples. Code is available at: \url{https://github.com/jjy1994/BaggingCertifyDataPoisoning}.

1 Introduction

Data poisoning can corrupt models by modifying, deleting, or inserting training examples, while existing certified defenses have limited applicability or loose guarantees. This work uses bagging to certify unchanged predictions against bounded poisoning and evaluates the resulting method on MNIST and CIFAR10.

  • Data poisoning modifies, deletes, and/or inserts training examples to induce incorrect predictions for many or attacker-chosen testing examples.
  • Existing certified defenses are limited to differentially private algorithms or attacks modifying existing examples, and their robustness guarantees can be loose.
  • Bagging samples k training examples with replacement, trains a base classifier, and predicts the label with the largest label probability.
  • The certified poisoning size guarantees the same prediction when poisoned examples do not exceed a threshold, and the threshold is tight without assumptions on the base learner.
  • 91.1% certified accuracy is achieved on MNIST when 100 training examples are arbitrarily poisoned, with k = 100 and N = 1,000.
  • The method includes algorithms for computing certified poisoning size in practice and is evaluated on MNIST and CIFAR10.

2 Certified Robustness of Bagging

Bagging samples training data with replacement, trains base classifiers, and aggregates their predictions by majority vote. The paper proves that this ensemble preserves a testing example’s label under bounded poisoning, derives computable certificates, and establishes tightness without assumptions on the base learner.

  • Bagging setup: Bagging samples k training examples with replacement, trains a base classifier on each subsample, and predicts the testing label with the largest label probability.The base learning algorithm may be deterministic or randomized.
  • Bagging setup: When poisoned examples are a minority, most subsamples exclude them, so majority vote can remain unaffected by poisoning.A toy example illustrates this mechanism using three base classifiers, two trained on clean examples.
  • Certified robustness: The certified poisoning size is the largest poisoning budget for which the ensemble predicts the same label for every permitted poisoned dataset.The poisoning metric counts the minimum modifications, deletions, and insertions needed to transform one dataset into another.
  • Certified robustness: The certificate uses bounds on the largest and second-largest clean label probabilities to compare poisoned-label probabilities without directly evaluating every poisoned dataset.The bounds are derived from regions of the subsample space using the Neyman–Pearson Lemma.
  • Certified robustness: The guarantee applies to any deterministic or randomized base learning algorithm and is tight when no assumptions on that algorithm are imposed.For any larger poisoning budget, an admissible learner and poisoned dataset can change the prediction or create ties under the theorem’s stated conditions.

3 Computing the Certified Poisoning Size

The certification procedure estimates ensemble label probabilities for each test example, then solves for the largest certified poisoning size using these bounds. It uses Monte Carlo estimation, simultaneous processing, and binary search to make certification computationally feasible.

  • Estimating labels and probabilities: SimuEM estimates lower and upper bounds for the largest and second-largest label probabilities at confidence level 1 − α.The second-largest probability bound is tightened using min(maxj≠li pj, 1 − pli).
  • Estimating labels and probabilities: The algorithm samples N subsamples, trains one base classifier per subsample, and estimates each testing example’s ensemble label from prediction frequencies.The label frequencies follow binomial distributions, enabling simultaneous probability-bound estimation with SimuEM.
  • Estimating multiple examples: Training one shared set of N base classifiers estimates predicted labels and probability bounds for e testing examples simultaneously.Estimating each testing example separately would require N classifiers per example and is computationally intractable.
  • Computing certification sizes: The certified poisoning size for each testing example is obtained by solving an optimization problem over the estimated probability bounds.The implementation uses binary search to find the largest r satisfying the certification constraint.
  • Confidence guarantee: The probability-estimation procedure may produce incorrect certified poisoning sizes, but the probability of any error across the testing examples is at most α.This guarantee is stated in Theorem 3 for Certify’s output.

4 Experiments

Experiments evaluate certified accuracy on MNIST and CIFAR10 and compare attack types, parameter effects, transfer learning, and existing certified defenses. The reported results show tradeoffs among subsampling size, estimation parameters, classifier accuracy, robustness, and efficiency.

  • Experimental Setup: The experiments use MNIST and CIFAR10 with neural-network base learners, 60,000 and 50,000 training examples, and 10,000 testing examples respectively.MNIST uses an example convolutional neural network, while CIFAR10 uses ResNet20.
  • Experimental Setup: Certified accuracy is the fraction of correctly classified testing examples whose certified poisoning sizes are at least r.Its confidence level is 1 − α when computed from Certify’s outputs.
  • Attack Comparisons: Deletion-only attacks achieve the best certified accuracy, while modification and All attacks overlap and have the lowest certified accuracy.The paper attributes the overlap to modification being equivalent to deleting an example and inserting a new one.
  • Parameter Effects: Larger k improves accuracy at r = 0 but makes certified accuracy decline faster as poisoned examples increase.Larger k increases the likelihood that subsamples contain poisoned training examples.
  • Parameter Effects: Certified accuracy increases as α or N increases, while remaining relatively insensitive to α.Larger α or N produces tighter estimated probability bounds and larger certified poisoning sizes.
  • Transfer Learning: Transfer learning can significantly increase certified accuracy on CIFAR10 when the pretrained classifier is assumed unpoisoned.The experiment uses Inception-v3 features pretrained on ImageNet.
  • Comparison with Existing Methods: 96.95% certified accuracy is achieved at r = 50, compared with 0 for existing methods under the same MNIST 1/7 setting.The comparison uses k = 50, α = 0.001, and N = 1,000 without data augmentation.

5 Related Work

Related work covers attacks that poison training data and defenses that detect poisoned examples, alter loss functions, or provide certified robustness. Existing certified defenses are described as having limited applicability and loose guarantees.

  • Data Poisoning Attacks: Data poisoning attacks modify, delete, and/or insert training examples to induce incorrect predictions for many or attacker-chosen testing examples.Such attacks have been demonstrated against Bayes classifiers, SVMs, neural networks, and other models.
  • Poisoning Defenses: Some defenses detect poisoned examples through their impact on error rates, while others jointly design loss functions and identify poisoned data during training.These approaches target detection and model learning together.
  • Certified Defenses: Differential privacy and randomized smoothing provide certified robustness against selected poisoning or backdoor settings, but their guarantees are described as loose.The cited randomized-smoothing methods focus on feature, label, or backdoor perturbations.

6 Conclusion

The paper establishes certified robustness for bagging against bounded data poisoning and shows that the bound is tight without assumptions on the base learner. Experiments on MNIST and CIFAR10 support the method’s effectiveness and efficiency relative to existing certified defenses.

  • Conclusion: Bagging predicts the same label for a testing example when the number of poisoned training examples is bounded.The result applies without assumptions on the base learning algorithm for the tightness claim.
  • Conclusion: The derived certified poisoning bound is tight when no assumptions on the base learning algorithm are made.The paper also reports empirical evaluations on MNIST and CIFAR10.
  • Future Work: The authors identify generalizing to other data types and leveraging meta-learning as future work.Graphs are given as an example of another data type.

A Proof of Theorem 1

The proof compares sampling distributions from the original and poisoned datasets using a Neyman–Pearson lemma variant. Certified robustness follows when a lower bound for the predicted label exceeds upper bounds for all alternatives, with the certified size defined as the largest poisoning budget satisfying this condition.

  • Setup: The proof models subsamples from D and D′ as random lists X and Y, sharing m examples across datasets of sizes n and n′.Each list contains k examples sampled uniformly with replacement, and the joint sample space is denoted Ω.
  • Probability comparison: The Neyman–Pearson lemma transfers probability bounds between X and Y for indicator functions over carefully selected regions of Ω.Its two parts provide lower and upper bounds under likelihood-ratio-defined subsets.
  • Label bounds: The proof lower-bounds the probability of label l by constructing a region R and upper-bounds each competing label with regions Qj.The resulting quantities incorporate residual discretization terms δl and δj arising from probabilities on the 1/n^k grid.
  • Certification condition: The bagging predictor is certified to retain label l when its lower bound exceeds the maximum competing-label upper bound for all admissible poisoned datasets.This requires the sufficient condition to hold across dataset sizes n−r ≤ n′ ≤ n+r.
  • Certified size: The certified poisoning size r* is the maximum r satisfying the sufficient condition, expressed as an optimization problem.This definition turns the probability comparison into the paper’s certified robustness threshold.

B Proof of Theorem 2

The proof establishes tightness by constructing a base learning algorithm that agrees with the original bagging prediction yet loses that prediction or creates ties after sufficiently large poisoning. This shows that the certified threshold cannot generally be improved without assumptions on the base learner.

  • Construction: For r > r*, the proof constructs a poisoned dataset D′ satisfying conditions under which the original label l is no longer guaranteed.The construction uses residual-adjusted probabilities for l and a competing label s.
  • Adversarial base learner: The remaining sample space is partitioned among competing labels so that a deliberately constructed algorithm A* remains consistent with the original probability constraints.For labels other than l and s, the construction enforces Pr(A*(X, x) = j) ≤ ps.
  • Tightness result: Under D′, label l is not predicted for x or ties occur, demonstrating failure of the original certified prediction beyond r*.The result is obtained from the constructed learning algorithm and poisoned sampling distribution.

C Proof of Theorem 3

The proof bounds the probability that certification returns an incorrect poisoning size by using the SimuEM guarantee and a union-bound argument. The resulting error probability is controlled by α.

  • Certification event: The SimuEM-based event guarantees that the true label probability is lower-bounded by pli while every competing label probability is upper-bounded by pj with probability at least 1−α.These bounds support the certification calculation for each testing example.
  • Error bound: The probability that Certify returns an incorrect certified poisoning size for a testing example is at most α.This is the theorem’s stated per-example certification error guarantee.
  • Proof step: The proof extends the bound across events using Boole’s inequality.The argument applies the inequality to combine the relevant error events.

D Derivation of the Analytical Form of n′

The derivation analyzes how L(n′) changes across the admissible range of poisoned dataset sizes and identifies where it is maximized. The maximizing n′ is characterized analytically through endpoint and interior cases.

  • Function analysis: The proof defines L(n′) and studies its monotonicity over intervals determined by n, r, and the admissible poisoned dataset-size range.The analysis separates n−r ≤ n′ ≤ n from n ≤ n′ ≤ n+r.
  • Lower-size interval: When n−r ≤ n′ ≤ n, L(n′) increases as n′ increases, so its maximum occurs at n.This identifies the relevant endpoint on the lower side of the original dataset size.
  • Interior behavior: In other ranges, L(n′) can increase and then decrease, so an interior root or an endpoint determines the maximum.The analysis identifies a single root no smaller than r and divides the behavior into three cases.
  • Analytical maximizer: The maximum occurs at n, n+r, or a nearby floor or ceiling of the analytical root, depending on the case.The stated endpoint cases include n′ = n and n′ = n+r; otherwise the maximizing value is an integer neighbor of the root.
Loading 2008.04495v7…