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

May 20, 2026

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

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.

Aman Saxena, Jan Schuchardt, Yan Scholten +1

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

Randomized Smoothing Adversarial Robustness Backdoor Defense Certified Robustness

Ask PDF

Feb 18, 2026

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

This work introduces a verification framework that provides both sound and complete guarantees for data poisoning attacks during neural network training. We formulate adversarial data manipulation, model training, and test-time evaluation in a single mixed-integer quadratic programming (MIQCP) problem. Finding the global optimum of the proposed formulation provably yields worst-case poisoning attacks, while simultaneously bounding the effectiveness of all possible attacks on the given training pipeline. Our framework encodes both the gradient-based training dynamics and model evaluation at test time, enabling the first exact certification of training-time robustness. Experimental evaluation on small models confirms that our approach delivers a complete characterization of robustness against data poisoning.

Philip Sosnin, Jodie Knapp, Fraser Kennedy +2

Department of Computing, Imperial College London, United Kingdom · The Alan Turing Institute, United Kingdom

Data Poisoning Attacks Certified Robustness Neural Network Verification

Ask PDF

Sep 10, 2026

Empirical Evaluation of Data Poisoning Attacks in Supervised Learning

Data poisoning corrupts training data to degrade a model or to plant attacker-controlled behavior. This study evaluates two representative training-time attacks, label flipping and backdoor poisoning, on MNIST and Fashion-MNIST with three baseline classifiers: Logistic Regression, Linear SVM, and Random Forest. Clean training is compared with poisoning rates of 5%, 10%, and 20% using clean-test accuracy, macro-precision, macro-recall, macro-F1, and, for backdoors, attack success rate. Label flipping caused clear degradation, largest for Logistic Regression and Linear SVM, while Random Forest stayed comparatively stable. Backdoor poisoning reached attack success rates from 0.9667 to 1.0000 on both datasets and all three models while often keeping clean-test performance near baseline. The results separate indiscriminate poisoning, which shows up in standard metrics, from targeted backdoor poisoning, which stays comparatively stealthy while embedding highly effective malicious behavior, and they support security-oriented evaluation beyond conventional clean-test metrics.

Toshif Khan, Muhammad Abusaqer

Minot State University

Adversarial Attacks Backdoor Attacks Data Poisoning Attacks

Ask PDF

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