acceptodds
Under review as a conference paper at ICLR 2027

A Certified Robustness Framework for Backdoor Poisoning Attacks using -Divergences

Abstract

Machine learning systems trained on untrusted data are vulnerable to data and backdoor poisoning attacks, in which an adversary corrupts training and test samples to manipulate predictions at inference time. Randomized smoothing yields provable defenses against such attacks, but existing applications to train-time robustness are limited to specific threat models and smoothing mechanisms. We propose a general framework that allows expressing complex adversary constraints on the number of corrupted training examples, feature and label perturbation magnitudes, and test-time corruptions. Our framework randomizes inputs by combining data subsampling with feature, label and test-sample noising. We propose a composable certification procedure based on -divergences that handles arbitrary combinations of threat models and noising strategies, and recovers several prior certification regimes exactly as special cases. We demonstrate our framework experimentally by certifying, for the first time, general -constraint poisoning adversaries under bagging with additive Laplace, Gaussian, and Uniform noises.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
certified robustness, poisoning attacks

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_pwGHOpenReview ↗
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 mpm_p 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 ℓ1\ell_1, ℓ2\ell_2 and ℓ∞\ell_\infty poisoning adversaries under these noise types, and report clear gains over RAB against backdoor attacks.

Critical strengths
  1. 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.

  2. 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.

  3. The theoretical proofs and analysis are extensive. While I did not verify every theoretical result in detail, the core results I examined appear sound.

  4. 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
  1. 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.
  2. 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.
  3. RAB is evaluated via a loose outer approximation, an aggregate ℓ2\ell_2 bound of εfmp\varepsilon_f\sqrt{m_p}. Its models are also trained for 20/10 epochs versus 200 for the base learners. The author should justify such settings.
  4. 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

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.

Q1: clearly state what is novel relative to the existing literatures

We would like to clarify our contributions. Our work builds on the ff-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:

  • a reduction of the combinatorial subsampling mixture to a small number of terms (Theorem 4.1)
  • an exact characterization of the resulting slack (Appendix E)
  • new closed-form hockey-stick profiles for flipping and Gaussian–flip noise (Theorems G.4, G.5)
  • worst-case perturbation results for Laplace and Uniform noise under ℓp\ell_p constraints (Theorems G.6–G.9)

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\ell_p magnitude of corrupted examples.

Q2: empirically estimate the actual mixture divergence on small instances

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 ff is sufficiently nice (both ff and its perspective are Lipschitz), then Df(μ∥ν)D_f(\mu \| \nu) 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.

Q3: Justify RAB training

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\ell_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).

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 N=n/kN = n / k partitions, where kk is the bag size used in the corresponding experiment from the paper, so that each partition contains roughly kk 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 ii to partition i mod Ni \bmod N, 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 1/(2k)1 / (2k) 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 RR (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 (k=100k = 100), RR (%)0.20.40.611.6
DPA, hash61.40.00.00.00.0
DPA, index84.156.90.00.00.0
Ours83.674.160.028.28.8
MNIST-17, clean labels (k=100k = 100), RR (%)0.20.40.61.22.2
DPA, hash98.80.00.00.00.0
DPA, index99.298.80.00.00.0
Ours99.298.998.896.988.5
MNIST, dirty labels (k=30k = 30), RR (%)0.20.40.81.21.6
DPA, hash65.838.60.00.00.0
DPA, index77.866.340.115.10.0
Ours, σa\sigma_a69.656.533.114.71.4
Ours, σb\sigma_b65.851.827.710.81.0
MNIST-17, dirty labels (k=30k = 30), RR (%)0.81.62.43.24
DPA, hash90.20.00.00.00.0
DPA, index98.291.60.00.00.0
Ours, σa\sigma_a97.191.562.91.20.0
Ours, σb\sigma_b95.283.543.310.70.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).

Reviewer_hhTrOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a unified certification framework for defending against data poisoning and backdoor attacks, considering perturbations to training features, labels, and test inputs. The framework combines randomized smoothing mechanisms, including bagging and feature/label noise, and derives ff-divergence bounds to certify prediction robustness through convex optimization. Experiments on MNIST and CIFAR-10 datasets demonstrate the applicability of the framework and report improvements in certified accuracy over existing defenses under selected attack settings.

Critical strengths
  1. The paper addresses an important problem in certified robustness against data poisoning and backdoor attacks, with a flexible threat model covering different types of perturbations.

  2. The proposed ff-divergence framework provides a unified approach to certifying different randomized smoothing mechanisms. The theoretical analysis is well developed, combining bagging, feature noise, and label noise within a common certification procedure. It also recovers the certificates of several existing methods as special cases, demonstrating the generality of the framework.

  3. The experiments consider multiple noise distributions and attack settings on MNIST and CIFAR-10, showing improvements in certified accuracy over existing baselines under certain configurations.

Critical weaknesses
  1. The tightness of the proposed certificates is not sufficiently characterized for the newly supported smoothing mechanisms. Although Appendix E analyzes the sources of slack and shows that the framework recovers the certificates of several prior methods, it remains unclear how tight the divergence bounds are for new combinations of bagging with Gaussian, Laplace, and Uniform noise. In particular, Theorem 4.1 relies on joint convexity to bound mixture divergences, while the component-wise worst-case relaxation may introduce additional looseness. Without a more detailed theoretical or empirical analysis of these gaps, it is difficult to assess how much the proposed framework improves certification beyond providing valid but potentially conservative bounds.

  2. The experiments do not fully evaluate the general threat model proposed in the paper. While the framework supports simultaneous training feature, label, and test-time corruptions, the experiments only consider these attacks in separate combinations. It remains unclear whether the method can maintain meaningful certified robustness when all three types of corruption occur simultaneously.

  3. The certified robustness remains limited on more challenging datasets, and its relevance to realistic backdoor attacks is not sufficiently demonstrated. In Table 3, the method achieves only 5.3% certified accuracy on CIFAR-10 at a poisoning rate of 0.1%, even with the better noise configuration. Moreover, the backdoor experiments use relatively small ℓ2\ell_2 perturbation budgets (ϵf=ϵte=0.5\epsilon_f=\epsilon_{\mathrm{te}}=0.5 for CIFAR-10), which may not cover typical patch-based backdoor triggers. The paper should better examine whether its certification guarantees remain meaningful under more realistic trigger sizes and attack settings.

  4. The computational cost of the proposed framework is substantial. The experiments require training 10,000 base models for MNIST and 1,000 for CIFAR-10. Although the paper discusses efficient certification computations, it provides limited comparisons of end-to-end training and inference costs with existing defenses. This raises concerns about the scalability of the method to larger datasets and more complex models.

Questions for authors
  1. Appendix E analyzes the sources of slack and demonstrates that the framework recovers several existing certificates. However, how tight are the divergence bounds for the newly supported combinations of bagging with Gaussian, Laplace, and Uniform noise? Could the authors provide theoretical analysis or numerical comparisons with exact mixture divergences on tractable settings to quantify the looseness introduced by Theorem 4.1 and the component-wise relaxations?

  2. The proposed framework supports simultaneous training feature, label, and test-time corruptions, but the experiments evaluate only separate combinations. Could the authors provide results under the full joint threat model to demonstrate whether meaningful certified accuracy can still be achieved?

  3. Table 3 reports only 5.3% certified accuracy on CIFAR-10 at a 0.1% poisoning rate. How representative are the chosen ℓ2\ell_2 perturbation budgets of realistic backdoor attacks, particularly patch-based triggers? Could the authors clarify how the certified accuracy changes under larger perturbation budgets that better reflect these attacks?

  4. The proposed method requires training thousands of base models. Could the authors report the end-to-end training, inference, and certification costs, and compare the certified accuracy with existing defenses under comparable computational budgets?

4 comments

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.

Q1: How tight are the divergence bounds?

We agree that the tightness of the divergence bounds is an interesting direction to study further. Our divergence accounting has two possible sources of slack: the joint convexity bound (Theorem 4.1) and the component-level analysis (Appendix G). We do not believe either is loose for the Gaussian noise of our main results (Tables 2 and 3). There the component-level analysis is exact, and we expect the joint convexity bound to be nearly tight, for the following reason.

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 ff is sufficiently nice (both ff and its perspective are Lipschitz), then Df(μ∥ν)D_f(\mu \| \nu) 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.

As for the individual noises, the only non-exact cases for us are those noises involving Uniform or Laplace noise under ℓp\ell_p feature constraints with 1<p<∞1 < p < \infty. Note we do provide the exact characterization for p∈{1,∞}p \in \{1, \infty\}, and we consider this a valuable contribution of our work. For Uniform noise we provide two-sided bounds on this quantity and so can measure the slack. For Laplace noise we have a less complete understanding.

Q2: Could the authors provide results under the full joint threat model?

We certify the ensembles trained with label noise and test-time noise. The threat model is our backdoor setting (Table 3) but now with a dirty-label attacker. The prior baselines cannot certify this threat model: plain bagging does not noise the test input, and RAB does not apply label noise. These results are included in the updated draft in Section 5.2, Table 4.

MNISTMNIST-17CIFAR10CIFAR10-02
RR (%)00.050.10.1500.250.40.7500.010.020.0300.20.30.5
Ours, σa\sigma_a42.632.722.512.683.059.241.019.85.43.41.90.824.110.24.30.2
Ours, σb\sigma_b37.525.313.65.782.048.228.814.77.65.13.21.645.833.124.78.0

Q3: How representative are the chosen perturbation budgets of realistic backdoor attacks?

There exist realistic backdoor attacks that exhibit the small corruption sizes we consider in this work. For example, Sleeper Agent [1] considers backdoor poisoning with ℓ∞\ell_\infty perturbations as low as 8/255, and Narcissus [2] demonstrates successful backdoors against CIFAR10 with an ℓ∞\ell_\infty budget of 2/2552/255 and poisoning rates as low as 0.05% (25 images).

Larger patch sizes are difficult to certify. It is useful to appreciate the difficulty of the certification task, which is a very strong claim over the stability of the learner encompassing both train-time and test-time uncertainty. We know of no certified defense that is effective against full-size patch triggers. RAB [3] certifies only small triggers: its experiments use triggers of ℓ2\ell_2 norm 0.1, against 1 (MNIST) and 0.5 (CIFAR10) in our Table 3, and it reports 0% certified accuracy for a 4×44 \times 4 patch. BagFlip [4] certifies 0% for backdoor attacks on CIFAR10, even with no poisoned examples. Our CIFAR10 numbers are low, but the only available baseline, RAB, has 0% certified accuracy on CIFAR10 at every R>0R > 0, so we consider our nontrivial certificate in that setting a substantial contribution nonetheless.

Q4: report the end-to-end training, inference, and certification costs, and compare the certified accuracy with existing defenses under comparable computational budgets?

We report a typical runtime on the MNIST dataset after training N=10,000N = 10{,}000 base learners with Gaussian noise. We train on a small Ray cluster comprising two nodes each equipped with two RTX 4090 GPUs and 160 CPU cores total. Training takes about 170s, inference takes about 60s, and certification takes about 4s. This procedure produces the maximum certified poisoning rate for each test example in the test set at a fixed εf,εl,εte\varepsilon_f, \varepsilon_l, \varepsilon_{\mathrm{te}}. The results are included in the updated draft in Section 5.4.

Plain bagging with the same bag size has essentially the same training cost as our method, so Figure 1 and Table 2 compare the two at equal computational budgets. Like other randomized smoothing defenses (Bagging, BagFlip, RAB), the main cost of our method is training the ensemble.

We thank the reviewer again for the detailed questions. We hope the new results on the full threat model and the computational cost address the reviewer's concerns, and we would be glad to provide any further details or results that would help in evaluating our paper.

References

[1] Souri, Hossein, et al. "Sleeper agent: Scalable hidden trigger backdoors for neural networks trained from scratch." Advances in Neural Information Processing Systems 35 (2022): 19165-19178.

[2] Zeng, Yi, et al. "Narcissus: A practical clean-label backdoor attack with limited information." Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. 2023.

[3] Weber, Maurice, et al. "Rab: Provable robustness against backdoor attacks." 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023.

[4] 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.

Thank you for the clarifications and additional results. The new dirty-label backdoor experiments address my concern about evaluating simultaneous feature, label, and test-time corruptions, and the runtime measurements improve the assessment of computational cost. Although the tightness of the mixture divergence bounds remains unquantified and the CIFAR-10 results and scalability remain limited, I consider the unified framework and its broader certification scope a useful contribution. I therefore raise my rating from 2 to 3.

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).

Reviewer_N4rKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a unified framework for certifying robustness against data poisoning and backdoor attacks. Building on an existing ff-divergence-based certification framework for randomized smoothing, it addresses the challenges of subsampling-induced mixture distributions and joint certification through a composable analysis, thereby extending certification methods to continuous noise distributions, multiple perturbation norms, and combinations of feature and label noise.

Critical strengths
  1. Compared with prior work, the paper considers richer threat models and successfully addresses the resulting technical challenges, broadening the range of attacks that can be certified and opening up further research directions.

  2. In my view, the theoretical development is coherent and reasonably comprehensive.

  3. The experiments demonstrate promising results in several settings, with some improvements over bagging or RAB.

Critical weaknesses
  1. The experimental results are insufficient.
    • Tables 2 and 3 use different poisoning fractions across datasets and even for the same dataset across tables, suggesting possible over-tuning to obtain favorable results.
    • The datasets are too small, possibly because of the high computational cost. This undermines one of the original motivations for randomized smoothing: its scalability.
    • Table 2 presents a major set of results, yet the method clearly underperforms the simpler bagging baseline.
  2. The certification algorithm lacks improvement. Although Dvijotham’s framework is broadly applicable, it involves substantial relaxations, potentially producing loose certificates and limiting empirical performance.
  3. The paper focuses on newly constructed settings rather than a central challenge in randomized smoothing, leaving few comparable baselines. Although the gains over RAB appear substantial, they may reflect RAB’s poor suitability for these settings. More appropriate baselines would strengthen the evaluation.
  4. The novelty is limited. The Hockey-stick profile, the ff-divergence-based convex optimization framework, and the experimental approach are inherited from prior work. I see little novel exploration in either the algorithms or the mathematics.
Questions for authors

See S&W

5 comments

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.

Q1: The experimental results are insufficient…

We first clarify the experimental protocol. The ensembles are trained on clean data, following standard practice for certified defenses. The poisoning fraction is the adversary budget at which we evaluate the certificate. The certificate is a provable guarantee: it holds against every adversary within the budget, so it can be computed directly on the clean input. For each test point, we compute the largest number of poisoned examples for which the prediction is provably unchanged. The reported poisoning rates are selected for each dataset to show the relevant accuracy-robustness tradeoff region. The rates differ between settings because the certified region depends strongly on the task and threat model.

Second, regarding dataset size: the absolute size of the dataset does not affect the cost of our method. Each base learner is trained on a bag of fixed size k, so the cost is determined by properties of the base learner, such as its sample complexity and model size, not the number of training examples. We selected the datasets in this work for consistency with prior literature on certified poisoning defenses [1-3].

Third, regarding Table 2: it is true that plain bagging certifies more than our method in most of Table 2. However, Table 2 is not intended to show that label noise strictly improves on bagging, or vice versa. Its purpose is to determine when different smoothing mechanisms help, a question that prior work cannot address. Plain bagging is itself a special case of our framework (Theorem E.1), so Table 2 compares mechanisms within it. We have updated the discussion to make its role clearer. We should expect plain bagging to outperform noising mechanisms at low poisoning rates. In this regime, few bags retain any corrupted data, so there is little benefit to adding noise. At higher poisoning rates, most bags retain some corrupted data, and it becomes increasingly important for the learner to tolerate it. This is the regime where additional noising, such as label flipping, should help. On MNIST-17, we observe a substantial improvement over bagging. At R = 2.5%, bagging certifies 0.0% while our method certifies 48.6%, and we certify some predictions up to 3.5% poisoning rate. We would like to stress that no prior work can certify general combinations of subsampling, feature noise, and label noise, and our framework is what enables this comparison between smoothing mechanisms.

Q2: The certification algorithm lacks improvement. Dvijotham’s framework…involves substantial relaxations.

When the worst-case hockey stick envelope is known, the relaxation is tight for the standard conception of certification with randomized smoothing (what [4] call “information-limited” certification). We recover the complete hockey stick envelope for label-released mixtures under Gaussian noise and any ℓp\ell_p constraint, as well as for Uniform and Laplace noise under ℓ1,ℓ∞\ell_1, \ell_\infty constraints. This also remains true if we add label flipping components into the noising scheme. Thus, there is no substantial relaxation in these cases. We do show a few settings where relaxation in the divergence accounting is nontrivial, such as for Uniform and Laplace noises for ℓp\ell_p with 1<p<∞1 < p < \infty.

Q3: The paper focuses on newly constructed settings…

We agree that RAB is poorly suited to these settings, and in fact this is a central motivation for our work. These settings reflect practical attacks: clean-label and backdoor attacks typically corrupt a small fraction of training examples, each by a bounded perturbation. Constraining both the number of corrupted examples and the per-example budget is therefore the natural threat model, but no prior certificate uses both axes. RAB certifies only a global ℓ2\ell_2 perturbation of the full dataset and is blind to how many examples are corrupted. To certify comparable poisoning rates, RAB must add noise that grows with the total number of corrupted examples, which destroys predictive performance. In contrast, each bag in our method retains only a few corrupted examples with high probability, so the required noise is much smaller (Section 5.2). In our comparison, RAB is given the same noise scales as our method (Table 3). We would also like to clarify that our evaluation is not limited to new settings. Under the original threat models of Jia et al. (2021) and BagFlip, our framework recovers their certificates exactly (Section 5.3, Appendices C.1 and E).

Q4: The novelty is limited…

We would like to clarify our contributions. Our work builds on the ff-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:

  • a reduction of the combinatorial subsampling mixture to a small number of terms (Theorem 4.1)
  • an exact characterization of the resulting slack (Appendix E)
  • new closed-form hockey-stick profiles for flipping and Gaussian–flip noise (Theorems G.4, G.5)
  • worst-case perturbation results for Laplace and Uniform noise under ℓp\ell_p constraints (Theorems G.6–G.9)

With these tools, our framework recovers the certificates of Jia et al. (2021) and BagFlip 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\ell_p magnitude of corrupted examples.

Thank you again for the constructive feedback. We hope these clarifications address the reviewer’s concerns, and we would be glad to provide any additional details or results that would help in evaluating our paper.

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] Weber, Maurice, et al. "Rab: Provable robustness against backdoor attacks." 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023.

[4] Dvijotham, Krishnamurthy Dj, et al. "A framework for robustness certification of smoothed classifiers using f-divergences." ICLR, 2020.

We thank the reviewer again for their constructive feedback.

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).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Concrete results on certificate tightness

Measurements of certificate tightness (new Appendix E.4)

In our replies to Reviewer hhTR (Q1) and Reviewer pwGH (Q2), we gave an informal argument for why we expect the joint convexity bound (Theorem 4.1) to be nearly tight for Gaussian noise. We have formalized this idea in a new Appendix E.4, and we use the result to measure the tightness of our certificates on all four datasets. In these experiments, our certificate is essentially exact.

Method. 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, even if the label is only recoverable with high probability, the divergence bound should still be approximately tight. Our strategy to make this rigorous is the following.

  1. We show that under certain regularity conditions on the generator ff, the divergence DfD_f is Lipschitz in both arguments with respect to the TV distance. These conditions hold for the entire family of hockey-stick divergences central to our certification analysis.
  2. It then remains to understand how well the component label can be recovered from the unlabeled observation, for both the clean and corrupted inputs. Any strategy for recovering the label yields a pair of TV distance bounds, given by its error probabilities, and hence a bound on the slack. We also argue that it is sufficient to restrict the recovery only to positions containing corrupted data. We then directly analyze the recovery strategy that assigns each noised training example to its most likely training index under the clean dataset.
  3. We apply this bound to a single corruption w0′w'_0 that attains our bound τβ\tau_\beta in every mixture component. This gives τ‾β≤DHS,β(M(w0′)∥M(w))≤τβ\underline{\tau}_\beta \le D_{\mathrm{HS},\beta}(\mathcal{M}(w'_0) \Vert \mathcal{M}(w)) \le \tau_\beta at every order β\beta. By Theorem A.3 (Dvijotham et al., 2020) applied to w0′w'_0, no information-limited certificate certifies more than the certificate computed from τ‾β\underline{\tau}_\beta.

This gives a certificate of tightness that we can compute from the dataset, in the information-limited sense of Dvijotham et al. (Theorem A.2).

Interestingly, our tightness analysis is intrinsically data-dependent, an unusual property for Randomized Smoothing methods. For Gaussian noise and bagging, we compute τ‾β\underline{\tau}_\beta from the ℓ2\ell_2 distances between training examples. As we show below, for high-dimensional datasets like MNIST this yields tight bounds. In general, for datasets with larger “overlap” between training examples (e.g., low-dimensional data), we expect the bound not to be tight, although we did not measure this.

Experiment. We compute an upper bound on the information-limited certified radius for clean-label poisoning with Gaussian noise and an ℓ2\ell_2 budget, using the ensembles of Section 5.1. The results are in the table below.

MNISTMNIST-17CIFAR10CIFAR10-02
RR (%)0.20.40.81.60.20.40.82.20.020.040.080.160.10.20.41
Our certificate83.674.142.98.899.298.998.688.528.620.79.81.271.163.046.011.4
Upper bound83.674.142.98.899.298.998.688.528.620.79.81.271.163.046.011.4

At the poisoning rates shown, the two certified accuracies are equal. The table below compares the certified radius of each test point with the upper bound on its radius. Across all four datasets, our radius is smaller for at most 5.04% of the test points, and by at most one poisoned example.

(%) Below boundMax radius gap
MNIST1.361
MNIST-175.041
CIFAR100.011
CIFAR10-020.000

Thus, our certificate is essentially exact in this setting. Further improvement would have to come from tighter bounds on the vote probabilities, a different smoothing mechanism, or more information about the base learner than its vote probabilities. These results are in Section 5.3 and Appendix E.4 of the updated draft.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.