- Rating
- 4(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proposes a randomized smoothing based framework for certifying classifiers against data poisoning and backdoor attacks. The adversary can replace up to training examples, with separate budgets on the feature change, the label change and the test-time trigger. The defence combines bagging with noise on training features, labels and the test input. Certificates come from the f-divergence convex method of Dvijotham et al. (2020), which reduces the problem to bounding the divergence between the clean and poisoned smoothing distributions. They show that the framework exactly recovers the bagging certificate of Jia et al. (2021) and the BagFlip certificate. They also characterize when the joint-convexity bound is tight. Experiments on MNIST, CIFAR10 and binary subsets of each certify , and poisoning adversaries under these noise types, and report clear gains over RAB against backdoor attacks.
Critical strengths
-
This paper introduce a single joint certificate rather than separate per-axis guarantees. All four budgets act on one perturbation set, and their effects compound inside one divergence bound. Consider such a compounding threat model adds more practicality to this field, and also initialise more interesting challenges and theorems in certified robustness.
-
The paper propose a composable certification pipeline. The procedure splits into three parts: mixture reduction, worst-case pairs ordered by hockey-stick dominance, and composition across product factors. New noise or threat-model combinations then need only per-component analysis rather than a fresh Neyman–Pearson derivation.
-
The theoretical proofs and analysis are extensive. While I did not verify every theoretical result in detail, the core results I examined appear sound.
-
The experiments are transparent and reproducible. The paper fully specifies its training configurations, releases code, and openly acknowledges its computational cost and the poorly understood trade-off between subsampling and noise.
Critical weaknesses
- Given the core theorem is based on the existing f-divergence and DP-amplification in this field. The theoretical contribution / novelty might be limited as the whole theory seems to be a carefully assembly and instantiation of known tools. It would be much more clear if the author could clearly state what is novel relative to the existing literatures.
- The tightness is not guaranteed in the new regimes, and the slack is not quantified. Exactness is shown only when mixture components are identifiable in pure bagging and BagFlip's label-released mixture. For bagging combined with continuous feature noise, which is the novel regime the paper presents, the slack is shown to be non-trivial but not quantified. It would be much appreciated if the author could empirically estimate the actual mixture divergence on small instances, so readers can tell whether weak results in experiments come from the mechanism or from the analysis.
- RAB is evaluated via a loose outer approximation, an aggregate bound of . Its models are also trained for 20/10 epochs versus 200 for the base learners. The author should justify such settings.
- DPA and Finite Aggregation are cited but not compared against, and Table 3 has no bagging-only row. It would be much appreciated if the author has the capability to extend the experiments.
Questions for authors
As in Weaknesses.
4 comments
Q4: Compare to prior work such as DPA and Finite Aggregation.
We evaluated DPA [3] as a baseline on all four datasets under clean- and dirty-label poisoning attacks (no backdoor trigger). We use partitions, where is the bag size used in the corresponding experiment from the paper, so that each partition contains roughly examples, matching our bagging settings. We consider two partition strategies: hash-based and index-based. The hash rule is the original strategy and uses the hash of the feature values to assign examples to partitions. The index rule assigns example to partition , and is valid due to our replacement adversary who cannot add or remove examples. The two methods differ in their certificate under modification adversary: for the hash rule, a single corrupted example can impact two partitions, while under the index rule only a single partition is affected.
DPA is essentially a deterministic alternative to bagging. Like bagging, it treats poisoned examples as worst-case. Due to this model, DPA can certify against at most a fraction of of the training set. Adding feature and label noise can certify beyond this by making use of partially corrupted bags. The qualitative comparison is similar to our findings using bagging. Full results can be found in the updated manuscript (Appendix H.1).
We observe from their paper that FA [4] yields only incremental improvements over DPA (below 5%), so we do not expect adding FA as a baseline would qualitatively affect our findings.
A bagging-only row in Table 3 would be 0% at every (even 0), because plain bagging does not noise the test input and therefore cannot certify a test-time trigger. The same is true for DPA on its own.
| MNIST, clean labels (), (%) | 0.2 | 0.4 | 0.6 | 1 | 1.6 |
|---|---|---|---|---|---|
| DPA, hash | 61.4 | 0.0 | 0.0 | 0.0 | 0.0 |
| DPA, index | 84.1 | 56.9 | 0.0 | 0.0 | 0.0 |
| Ours | 83.6 | 74.1 | 60.0 | 28.2 | 8.8 |
| MNIST-17, clean labels (), (%) | 0.2 | 0.4 | 0.6 | 1.2 | 2.2 |
|---|---|---|---|---|---|
| DPA, hash | 98.8 | 0.0 | 0.0 | 0.0 | 0.0 |
| DPA, index | 99.2 | 98.8 | 0.0 | 0.0 | 0.0 |
| Ours | 99.2 | 98.9 | 98.8 | 96.9 | 88.5 |
| MNIST, dirty labels (), (%) | 0.2 | 0.4 | 0.8 | 1.2 | 1.6 |
|---|---|---|---|---|---|
| DPA, hash | 65.8 | 38.6 | 0.0 | 0.0 | 0.0 |
| DPA, index | 77.8 | 66.3 | 40.1 | 15.1 | 0.0 |
| Ours, | 69.6 | 56.5 | 33.1 | 14.7 | 1.4 |
| Ours, | 65.8 | 51.8 | 27.7 | 10.8 | 1.0 |
| MNIST-17, dirty labels (), (%) | 0.8 | 1.6 | 2.4 | 3.2 | 4 |
|---|---|---|---|---|---|
| DPA, hash | 90.2 | 0.0 | 0.0 | 0.0 | 0.0 |
| DPA, index | 98.2 | 91.6 | 0.0 | 0.0 | 0.0 |
| Ours, | 97.1 | 91.5 | 62.9 | 1.2 | 0.0 |
| Ours, | 95.2 | 83.5 | 43.3 | 10.7 | 0.8 |
We thank the reviewer for the careful review and for the suggestions to improve the paper. We hope these clarifications and the new comparison address the reviewer’s concerns, and would be glad to provide any further details or discussion.
References
[1] Jia, Jinyuan, Xiaoyu Cao, and Neil Zhenqiang Gong. "Intrinsic certified robustness of bagging against data poisoning attacks." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 9. 2021.
[2] Zhang, Yuhao, Aws Albarghouthi, and Loris D'Antoni. "Bagflip: A certified defense against data poisoning." Advances in Neural Information Processing Systems 35 (2022): 31474-31483.
[3] Levine, Alexander, and Soheil Feizi. "Deep partition aggregation: Provable defense against general poisoning attacks." International Conference on Learning Representations. 2021.
[4] Wang, Wenxiao, Alexander J. Levine, and Soheil Feizi. "Improved certified defenses against data poisoning with (deterministic) finite aggregation." International Conference on Machine Learning. PMLR, 2022.
I really appreciate the authors detailed explaination for my concerns. I am happy to raise my score for this paper.
We thank the reviewer again for their helpful comments and support of our work.
We would like to briefly mention that we have since quantified the slack arising from the joint convexity bound more carefully, and as a demonstration we were able to measure experimentally that the certificates computed from our method are essentially tight in the clean label poisoning setting with Gaussian noise (see our comment at the top of the page).
We thank the reviewer for their thoughtful review. We hope the following discussion will clarify the strengths of our paper. We have uploaded an updated draft of our manuscript, to which we refer in the following discussion.
We would like to clarify our contributions. Our work builds on the f-divergence framework of Dvijotham et al. (2020), which was developed for evasion attacks with simple noise distributions. We extend it to a general framework for data poisoning and backdoor attacks. Prior certified poisoning defenses each derive a certificate by hand for one fixed smoothing scheme and threat model. Our framework instead supports rich threat models spanning feature, label, and test-time corruptions, combines subsampling with arbitrary feature and label noise, and produces certificates automatically from per-component divergence bounds. Making this tractable requires new mathematical tools, including:
With these tools, our framework recovers the certificates of Bagging [1] and BagFlip [2] exactly as special cases (Theorems E.1, E.2). It also provides the first certificates in settings no prior work can handle, including adversaries constrained jointly in the number and ℓp magnitude of corrupted examples.
We agree that quantifying the slack of the joint convexity bound under continuous feature noise is an interesting question, and we are working on a more detailed characterization of the tightness of our divergence accounting. Here we will discuss when the bound is exact and our reasons for expecting it to be effectively tight in the non-exact case for the datasets we evaluate in this work (MNIST, MNIST-17, CIFAR10, CIFAR10-02).
The joint convexity bound is exact when the component label is released or is determined by the observation (Lemma E.1, Corollary E.1). Intuitively, if the generator f is sufficiently nice (both f and its perspective are Lipschitz), then Df(μ∥ν) should be continuous in both its arguments (say, with respect to TV distance). On high-dimensional datasets like MNIST, we expect that noised samples are still easily distinguished from each other on average, so that the (clean) label-released and unlabeled mixtures are close. A similar property should hold for the corrupted mixtures, based on the attacker constraints. It should follow that the divergence is close to our bound. This is currently intuition and we have not yet formalized it.
The certificate we compute for RAB is not loose. RAB adds Gaussian noise to the full training set and its (tight) certificate only depends on the global aggregate ℓ2 perturbation. The perturbation at which we evaluate RAB’s certificate is attained by an attacker who maximally perturbs all their corrupted points.
The smaller number of epochs for RAB is somewhat deceptive due to the substantial difference in dataset sizes. Since our method trains on small bags of data, more epochs are needed to reach a comparable number of training steps. RAB trains on the full dataset and so needs fewer epochs. In fact, RAB was the most expensive method for us to train: training a single 10,000-classifier ensemble took about 2h in our environment, many times longer than our ensembles (see our response to hhTR, Q4).