A Certified Robustness Framework for Backdoor Poisoning Attacks using $f$-Divergences

Evan Rose; Alina Oprea

cs.LGOct 26, 2026

A Certified Robustness Framework for Backdoor Poisoning Attacks using $f$ -Divergences

Authors: Evan Rose, Alina Oprea

Organizations: Northeastern University

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 develop a composable certification procedure based on $f$ -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, robustness under general $\ell_p$ -constrained poisoning adversaries under bagging with additive Laplace, Gaussian, and Uniform noises.

Figures & tables

Noise	Adjacency $\theta$	$D_{\mathrm{R},\alpha}(\mu\\|\nu)$	$D_{\mathrm{HS},\beta}(\mu\\|\nu)$
$\Unif(\gamma)$	$1-\prod_{i}\bigl(1-\tfrac{\lvert\Delta_{i}\rvert}{2\gamma}\bigr)_{\!+}$	$\tfrac{1}{\alpha-1}\log(1-\theta)$	$\min(1,\beta)\,\theta$
$\mathcal{N}(\cdot,\sigma^{2}I)$	$r=\lVert\Delta\rVert_{2}/\sigma$	$\alpha r^{2}/2$	$\Phi\bigl(\tfrac{r}{2}-\tfrac{\log\beta}{r}\bigr)-\beta\Phi\bigl(-\tfrac{r}{2}-\tfrac{\log\beta}{r}\bigr)-(1-\beta)_{+}$
$\Lap(\cdot,b)$	$\mathbf{t}=\lvert\Delta\rvert/b$	$\sum_{j}\kappa_{\alpha}(\mathbf{t}_{j})$	$\bigl[(1-\sqrt{\beta}e^{-t/2})_{+}-(1-\beta)_{+}\bigr]_{+}$
$\phi^{\textrm{flip}}_{\gamma,C}$	$s=\lVert\Delta\rVert_{0}$	$\tfrac{s}{\alpha-1}\log\bigl(p_{+}^{\alpha}p_{-}^{1-\alpha}+p_{+}^{1-\alpha}p_{-}^{\alpha}+p_{0}\bigr)$	$\sum_{d\geq d_{\beta}}\bigl(1-\beta(p_{+}/p_{-})^{-d}\bigr)P_{d}$

Table 1: Divergence bounds derived in Appendix G . Here

\theta

is the adjacency parameter of Definition G.1 and

\Delta\coloneqq x-x^{\prime}

. Notation

p_{+}

p_{0}

p_{-}

\kappa_{\alpha}(t)

d_{\beta}

, and

P_{d}

are defined in Appendix G .

Panel of Figure 1 — Figure 1: Certified accuracies on MNIST for clean-label triggerless attacks under different $\ell_{p}$ adversaries. The budget in each case is calibrated to correspond to the same $\ell_{2}$ budget, which has the effect that Gaussian noise certifies the same radius across all curves.

	MNIST				MNIST-17				CIFAR10				CIFAR10-02
$R$ (%)	$0$	$0.5$	$1$	$1.5$	$0$	$1$	$2.5$	$3.5$	$0$	$0.05$	$0.1$	$0.15$	$0$	$0.8$	$1.6$	$2.4$
Bagging	82.3	56.8	31.9	12.0	99.1	98.0	0.0	0.0	32.5	14.7	5.3	1.1	78.3	64.4	40.2	2.4
Ours, $\sigma_{a}$	81.2	50.0	23.5	5.1	98.7	96.6	48.6	0.0	22.3	9.8	3.3	0.6	66.9	48.5	26.6	0.6
Ours, $\sigma_{b}$	78.7	44.8	17.9	3.7	98.8	93.0	35.3	5.3	16.7	6.4	1.7	0.1	64.2	45.4	27.5	3.4

Table 2: Robustness tradeoff for joint feature & label adversaries at poisoned fractions

R

, with

\varepsilon_{\mathrm{l}}=1

and

\ell_{2}

budget

\varepsilon_{\mathrm{f}}=1

(MNIST, MNIST-17) or

0.5

(CIFAR10, CIFAR10-02). Bag sizes

k

and noise scales

\sigma_{a}<\sigma_{b}

are fixed per dataset ( Table 7 ). Label noise retains the true label with

p=0.9

	MNIST				MNIST-17				CIFAR10				CIFAR10-02
$R$ (%)	$0$	$0.1$	$0.5$	$1$	$0$	$0.5$	$1$	$2$	$0$	$0.02$	$0.06$	$0.1$	$0$	$0.2$	$0.4$	$0.6$
RAB, $\sigma_{a}$	74.1	0.0	0.0	0.0	95.9	0.0	0.0	0.0	18.4	0.0	0.0	0.0	63.5	0.0	0.0	0.0
RAB, $\sigma_{b}$	66.5	0.0	0.0	0.0	94.7	0.0	0.0	0.0	19.3	0.0	0.0	0.0	67.5	0.0	0.0	0.0
Ours, $\sigma_{a}$	48.6	42.2	20.5	5.0	92.9	88.0	76.6	41.8	6.8	5.6	3.8	2.5	40.9	34.4	27.5	20.2
Ours, $\sigma_{b}$	41.9	36.6	17.8	6.2	91.3	86.1	76.1	45.4	8.7	7.9	6.5	5.3	54.0	51.4	48.7	45.8

Table 3: Robustness tradeoff for clean label backdoor adversaries on MNIST, MNIST-17, CIFAR10, and CIFAR10-02 at different poisoned fractions

R

. The

\ell_{2}

constraint is

\varepsilon_{\mathrm{f}}=\varepsilon_{\mathrm{te}}=1

on MNIST and MNIST-17 and

\varepsilon_{\mathrm{f}}=\varepsilon_{\mathrm{te}}=0.5

on CIFAR10 and CIFAR10-02.

\sigma_{a},\sigma_{b}

are as in Table 7 . RAB trains on the full training set.

Panel of Figure 2 — Figure 2: Certified accuracy versus poisoning fraction $R$ at each per-example budget $\varepsilon_{\mathrm{f}}$ , under an $\ell_{2}$ adversary with Gaussian feature noise. $\sigma=0.5$ for MNIST and $\sigma=0.35$ for CIFAR10.

Figure 3: Tightness of our certificate with BagFlip’s.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

$f$ -Divergence	Regime	Generator $f(u)$	Integral form
Total variation $D_{\mathrm{TV}}(\mu\\|\nu)$		$\tfrac{1}{2}\lvert u-1\rvert$	$\frac{1}{2}\int\lvert p-q\rvert\,d\lambda$
Hockey-stick $D_{\mathrm{HS},\beta}(\mu\\|\nu)$	$\beta\geq 0$	$(u-\beta)_{+}-(1-\beta)_{+}$	$\int(p-\beta q)_{+}\,d\lambda-(1-\beta)_{+}$
Kullback–Leibler $D_{\mathrm{KL}}(\mu\\|\nu)$		$u\log u$	$\int p\log\frac{p}{q}\,d\lambda$
Squared Hellinger $D_{\mathrm{H}^{2}}(\mu\\|\nu)$		$\tfrac{1}{2}(\sqrt{u}-1)^{2}$	$1-\int\sqrt{pq}\,d\lambda$
Hellinger $D_{\mathrm{H},\alpha}(\mu\\|\nu)$	$\alpha\in(0,1)\cup(1,\infty)$	$\frac{u^{\alpha}-1}{\alpha-1}$	$\frac{1}{\alpha-1}(\int p^{\alpha}q^{1-\alpha}\,d\lambda-1)$
Pearson $D_{\chi^{2}_{\mathrm{P}}}(\mu\\|\nu)$		$(u-1)^{2}$	$\int\frac{(p-q)^{2}}{q}\,d\lambda$

Appendix

Table 4:

f

-divergences and associated generators and integral form, with

p\coloneqq\tfrac{d\mu}{d\lambda}

and

q\coloneqq\tfrac{d\nu}{d\lambda}

Divergence		Tensorization	Notes
Hellinger integral	$Z_{\alpha}(\mu\\|\nu)$	$=\prod_{i=1}^{n}Z_{\alpha}(\mu_{i}\\|\nu_{i})$	$\alpha\in(0,1)\cup(1,\infty)$
Rényi	$D_{\mathrm{R},\alpha}(\mu\\|\nu)$	$=\sum_{i=1}^{n}D_{\mathrm{R},\alpha}(\mu_{i}\\|\nu_{i})$	$\alpha\in[0,\infty]$
Kullback–Leibler	$D_{\mathrm{KL}}(\mu\\|\nu)$	$=\sum_{i=1}^{n}D_{\mathrm{KL}}(\mu_{i}\\|\nu_{i})$	case $\alpha=1$ above
Squared Hellinger	$D_{\mathrm{H}^{2}}(\mu\\|\nu)$	$=1-\prod_{i=1}^{n}\bigl(1-D_{\mathrm{H}^{2}}(\mu_{i}\\|\nu_{i})\bigr)$	case $\alpha=1/2$ above
Pearson $\chi^{2}$	$D_{\chi^{2}_{\mathrm{P}}}(\mu\\|\nu)$	$=\prod_{i=1}^{n}\bigl(1+D_{\chi^{2}_{\mathrm{P}}}(\mu_{i}\\|\nu_{i})\bigr)-1$	case $\alpha=2$ above
Neyman $\chi^{2}$	$D_{\chi^{2}_{\mathrm{N}}}(\mu\\|\nu)$	$=\prod_{i=1}^{n}\bigl(1+D_{\chi^{2}_{\mathrm{N}}}(\mu_{i}\\|\nu_{i})\bigr)-1$	Item B.2(ii) w/ $D_{\chi^{2}_{\mathrm{P}}}$

Appendix

Table 5: Tensorization of

f

-divergences under product measures. Throughout,

\mu=\bigotimes_{1}^{n}\mu_{i}

and

\nu=\bigotimes_{i=1}^{n}\nu_{i}

are product measures on a common product space.

Work	Threat vector $\rho$	Mechanism $(\Pi,\phi_{\mathcal{X}},\phi_{\mathcal{Y}})$	Certificate
Jia et al. [2021]	$(m_{\mathrm{p}},\infty,1,0)$	bagging, none, none	identical ( Theorem E.1 )
Rosenfeld et al. [2020]	$(m_{\mathrm{p}},0,1,0)$	full set, none, flipping	tight a
Zhang et al. [2022]	$(m_{\mathrm{p}},s,\varepsilon_{\mathrm{l}},\varepsilon_{\mathrm{te}})$	bagging, flipping, flipping	identical ( Theorem E.2 )
Weber et al. [2023]	aggregate $\ell_{2}$ on $S$	full set, Gaussian, none	identical b

Appendix

Table 6: Threat models and smoothing mechanisms of prior randomized smoothing works expressed in the notation of Sections 3 and 4

Dataset	$k$	$\sigma_{a}$	$\sigma_{b}$	$k$	$\sigma_{a}$	$\sigma_{b}$
	Joint feature & label			Backdoor
MNIST	30	0.25	0.5	300	0.75	1.0
MNIST-17	30	0.5	1.0	100	0.75	1.0
CIFAR10	200	0.2	0.35	1000	0.5	0.75
CIFAR10-02	25	0.35	0.5	100	0.35	0.5

Appendix

Table 7: Bag sizes and noise scales of Table 2 and Table 3 .

Certified Robustness

Certified robustness develops formal guarantees that model predictions remain reliable under specified input or system perturbations.

See all 86 papers

Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy
May 20, 2026Aman Saxena, Jan Schuchardt, Yan Scholten +1Randomized Smoothing Adversarial Robustness
Department of Computer Science, Technical University of Munich · Munich Data Science Institute · MCML +1
Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programming
Feb 18, 2026Philip Sosnin, Jodie Knapp, Fraser Kennedy +2Data Poisoning Attacks Certified Robustness
Department of Computing, Imperial College London, United Kingdom · The Alan Turing Institute, United Kingdom
Empirical Evaluation of Data Poisoning Attacks in Supervised Learning
Sep 10, 2026Toshif Khan, Muhammad AbusaqerAdversarial Attacks Backdoor Attacks
Minot State University

May 20, 2026J/K move · Enter open · S save

Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy

Aman Saxena, Jan Schuchardt, Yan Scholten, Stephan Günnemann

Department of Computer Science, Technical University of Munich · Munich Data Science Institute · MCML+1

Randomized Smoothing Adversarial Robustness Backdoor Defense Certified Robustness

Open paper AskPDF arXiv

Randomized smoothing is a powerful tool for certifying robustness to adversarial perturbations, including poisoning attacks via randomized training and evasion attacks via randomized inference. Extending these guarantees to backdoor attacks, where training and test data are jointly perturbed, remains challenging because training- and test-time randomized mechanisms must be analyzed within a single robustness certificate. We address this by connecting randomized smoothing to the dual view of differential privacy through privacy profiles, which provide a numerical procedure for composing heterogeneous mechanisms. The resulting framework enables tight, modular, end-to-end certification of complex, composed mechanisms while leveraging existing analyses of differentially private mechanisms. We instantiate the framework for DP-SGD and Deep Partition Aggregation with inference-time smoothing, deriving joint robustness guarantees against both training-time and inference-time attacks. Experiments on MNIST and CIFAR-10 demonstrate the effectiveness of our framework. Overall, we provide a principled and general framework for using composite mechanisms to certify robustness under complex threat models that better capture the capabilities of real-world adversaries.

Abstract

Certified Robustness

Explore similar work

Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy

Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programming

Empirical Evaluation of Data Poisoning Attacks in Supervised Learning