# Certified Robustness to Data Poisoning in Gradient-Based Training

Philip Sosnin  Department of Computing, Imperial College London, London,
United Kingdom  Mark N. Müller  Department of Computer Science, ETH Zurich,
Zurich, Switzerland  LogicStar.ai, Zurich, Switzerland  Maximilian Baader
Department of Computer Science, ETH Zurich, Zurich, Switzerland  Calvin Tsay
Equal contribution, corresponding authors<EMAIL_ADDRESS>and
<EMAIL_ADDRESS>Department of Computing, Imperial College London,
London, United Kingdom  Matthew Wicker∗ Department of Computing, Imperial
College London, London, United Kingdom  The Alan Turing Institute, London,
United Kingdom

###### Abstract

Modern machine learning pipelines leverage large amounts of public data,
making it infeasible to guarantee data quality and leaving models open to
poisoning and backdoor attacks. However, provably bounding model behavior
under such attacks remains an open problem. In this work, we address this
challenge and develop the first framework providing provable guarantees on the
behavior of models trained with potentially manipulated data. In particular,
our framework certifies robustness against untargeted and targeted poisoning
as well as backdoor attacks for both input and label manipulations. Our method
leverages convex relaxations to over-approximate the set of all possible
parameter updates for a given poisoning threat model, allowing us to bound the
set of all reachable parameters for any gradient-based learning algorithm.
Given this set of parameters, we provide bounds on worst-case behavior,
including model performance and backdoor success rate. We demonstrate our
approach on multiple real-world datasets from applications including energy
consumption, medical imaging, and autonomous driving.

##  1 Introduction

To achieve state-of-the-art performance, modern machine learning pipelines
involve pre-training on massive, uncurated datasets; subsequently, models are
fine-tuned with task-specific data to maximize downstream performance (Han et
al., 2021). Unfortunately, the datasets used in both steps are potentially
untrustworthy and of such scale that conducting rigorous quality checks
becomes impractical.

##### Data Poisoning.

Yet, adversarial manipulation, i.e., poisoning attacks, affecting even a small
proportion of data used for either pre-training or fine-tuning can lead to
catastrophic model failures (Carlini et al., 2023). 0For instance, Yang et al.
(2017) show how popular recommender systems on sites such as YouTube, Ebay,
and Yelp can be easily manipulated by poisoning. Likewise, Zhu et al. (2019)
show that poisoning even 1% of training data can lead models to misclassify
targeted examples, and Han et al. (2022) use poisoning to selectively trigger
backdoor vulnerabilities in lane detection systems to force critical errors.

##### Poisoning Defenses.

Despite the gravity of the failure modes induced by poisoning attacks,
counter-measures are generally attack-specific and only defend against known
attack methods (Tian et al., 2022). The result of attack-specific defenses is
an effective “arms race” between attackers trying to circumvent the latest
defenses and counter-measures being developed for the new attacks.
Subsequently, even best practices, i.e., using the latest defenses, provide no
guarantees of protection against poisoning attacks. To date, relatively few
approaches have sought provable guarantees against poisoning attacks
(Rosenfeld et al., 2020; Steinhardt et al., 2017; Xie et al., 2022). These
methods are often limited in scope, e.g., applying only to linear models
(Rosenfeld et al., 2020; Steinhardt et al., 2017) or only providing
approximate guarantees for a limited set of poisoning settings Rosenfeld et
al. (2020); Xie et al. (2022).

##### This Work: General Certificates of Poisoning Robustness.

In this work, we present an approach for computing sound and general
certificates of robustness to poisoning attacks for any model trained with
first-order optimization methods (e.g., stochastic gradient descent or Adam
(Kingma & Ba, 2014)). The proposed strategy begins by treating various
poisoning attacks as constraints over an adversary’s perturbation ‘budget’ in
input and label spaces. Following the comprehensive taxonomy in Tian et al.
(2022), we view the objective of each poisoning attack as an optimization
problem. We consider three objectives: (i) untargeted attacks: reducing the
model test performance to cause denial-of-service, (ii) targeted attacks:
compromising the model performance only on certain types of inputs, and (iii)
backdoor attacks: leaving the model performance stable, but introducing a
trigger pattern that causes errors at deployment time. Our approach then
leverages convex relaxations of both the training problem and the constraint
sets defining the threat model to compute a sound (but incomplete) certificate
that bounds the impact of the poisoning attack.

##### Paper Outline.

The paper is organized as follows. We first review related works and provide a
general framework for poisoning attacks, describing how our formulation
captures the settings studied in prior works. We then present abstract
gradient training (AGT), our technique for over-approximating the effect of a
given poisoning attack and discuss implementation details, including a novel,
explicit formulation of CROWN-like bounds (Zhang et al., 2018) on the weight
gradients. We conclude with extensive ablation experiments on datasets from
household energy consumption, medical image classification, and autonomous
vehicle driving.

##### Key Contributions.

In summary, this paper makes the following key contributions:

  * •

A generic threat model for capturing the capabilities and goals of a poisoning
attack.

  * •

A framework, including a novel bound propagation strategy, for computing sound
bounds on the influence of a poisoning adversary on any model trained with
gradient-based methods.

  * •

Based on the above, a series of formal proofs that allow us to bound the
effect of poisoning attacks that seek to corrupt the system with targeted,
untargeted, or backdoor attacks.

  * •

An extensive empirical evaluation demonstrating the effectiveness of our
approach.

##  2 Related Works

##### Data Poisoning.

Poisoning attacks have existed for nearly two decades and are a serious
security concern (Biggio & Roli, 2018; Biggio et al., 2014; Newsome et al.,
2006). In Muñoz-González et al. (2017) the authors formulate a general
gradient-based attack that generates poisoned samples that corrupt model
performance when introduced into the dataset (now termed, untargeted attack).
Backdoor attacks manipulate a small proportion of the data such that, when a
specific pattern is seen at test-time, the model returns a specific, erroneous
prediction Chen et al. (2017); Gu et al. (2017); Han et al. (2022); Zhu et al.
(2019). Popular defenses are attack specific, e.g., generating datasets using
known attack strategies to classify and reject potentially poisoned inputs (Li
et al., 2020). Alternative strategies apply noise or clipping to mitigate
certain attacks (Hong et al., 2020).

##### Poisoning Defenses.

General defenses to poisoning attacks seek to provide upper-bounds on the
effectiveness of any attack strategy. In this area, Steinhardt et al. (2017)
provide such upper-bounds for linear models trained with gradient descent.
Rosenfeld et al. (2020) present a statistical upper-bound on the effectiveness
of $\ell_{2}$ perturbations on training labels for linear models using
randomized smoothing. Xie et al. (2022) observe that differential privacy,
which usually covers addition or removal of data points, can also provide
statistical guarantees in some limited poisoning settings.

##### Certified Adversarial Robustness.

Sound algorithms (i.e., no false positives) for upper-bounding the
effectiveness of inference-time adversaries are well-studied for trained
models (Gehr et al., 2018) and training models for robustness (Gowal et al.,
2018; Müller et al., 2022). These approaches typically utilize ideas from
formal methods (Katz et al., 2017; Wicker et al., 2018) or optimization
(Botoeva et al., 2020; Bunel et al., 2018; Huchette et al., 2023). Most
related to this work are strategies that consider intervals over both model
inputs and parameters (Wicker et al., 2020), as well as some preliminary work
on robust explanations that bound the input gradients of a model Wicker et al.
(2022). Despite these methodological relationships, none of these methods
directly apply to the general training setting studied here.

##  3 Preliminaries: Poisoning Attacks

We denote a machine learning model as a parametric function $f$ with
parameters $\theta$, feature space $x\in\mathbb{R}^{n}$, and label space
$y\in\mathbb{R}^{m}$. We operate in the supervised learning setting with a
dataset $\mathcal{D}=\\{(x^{(i)},y^{(i)})\\}_{i=1}^{N}$ where we index the
dataset such that $\mathcal{D}_{x}^{(i)}$ is the $i^{th}$ feature vector and
$\mathcal{D}_{y}^{(i)}$ is the $i^{th}$ label. We denote the parameter
initialization $\theta^{\prime}$ and a training algorithm $M$ as
$\theta=M(f,\theta^{\prime},\mathcal{D})$, i.e., given a model,
initialization, and data, the training function $M$ returns a “trained”
parameterization $\theta$. Finally, we assume the loss function is computed
element-wise from the dataset, denoted as $\mathcal{L}(f(x^{(i)}),y^{(i)})$.

Given this abstraction of model training, we now turn to developing an
abstraction of the data poisoning attacks, defining their capabilities to
adversarially manipulate the training input. To complete the threat model, we
formulate adversary goals, i.e., what the adversaries seek to accomplish with
their manipulation as optimization problems. Typical threat models
additionally specify the adversary’s system knowledge, however, as we aim to
upper bound a worst-case adversary, we assume unrestricted access to all
training information including model architecture and initialization, data,
data ordering, batch size, etc.

###  3.1 Poisoning Attack Capabilities

We consider adversaries who are in general able to modify both features and
labels simultaneously. In a paired modification setting, adversaries must
choose a set of inputs and modify both their features and labels. In the
standard setting, however, adversaries may modify features and labels of
different inputs.

##### Feature Poisoning.

We denote adversarial feature poisoning capabilities with three parameters:
$n$, the number of inputs they may modify at most, $\epsilon$, the maximum
magnitude by which they can modify the feature vector, and $p$ the parameter
of the $\ell_{p}$ norm under which the modifications are measured.

##### Label Poisoning.

Similarly to the above, we model the label poisoning capabilities of an
adversary as modifying at most $m$ labels by magnitude at most $\gamma$ in an
$\ell_{q}$ norm.

Finally, given a dataset $\mathcal{D}$ we define the set of potentially
poisoned datasets as:

$T_{n,\epsilon,p}^{m,\gamma,q}(\mathcal{D}):=\bigcup_{I\in\mathcal{S}_{n}}\bigcup_{J\in\mathcal{S}_{m}}\\{\mathcal{D}^{\prime}\
s.t.\ \forall i\in
I,||\mathcal{D}^{\prime(i)}_{x}-\mathcal{D}^{(i)}_{x}||_{p}\leq\epsilon\wedge\forall
j\in J,||\mathcal{D}^{\prime(j)}_{y}-\mathcal{D}^{(j)}_{y}||_{q}\leq\gamma\\}$

Where $\mathcal{S}_{n}$ is the set of all subsets of the integers less than
$N$ with cardinally at most $n$. In our exposition below, we will often
shorten the above notation to simply $T(\mathcal{D})$, highlighting that the
methods work for any selection of the six parameters governing the adversary’s
capabilities (provided they are valid i.e., all non-negative).

###  3.2 Poisoning Attack Goals

Here, we cover the different goals poisoning adversaries may pursue and
briefly outline what it means to certify that a training algorithm is robust
against such an adversary.

##### Untargeted Poisoning.

Untargeted poisoning aims to prevent training convergence, leading to an
unusable model and therefore denial of service (Tian et al., 2022). Given a
test dataset of $k$ examples, the adversary’s objective is thus:

$\max_{\mathcal{D}^{\prime}\in
T}\dfrac{1}{k}\sum_{i=1}^{k}\mathcal{L}\big{(}f^{M(f,\theta^{\prime},\mathcal{D}^{\prime})}(x^{(i)}),y^{(i)}\big{)}$
(1)

We can certify robustness to this attack by providing a sound upper bound to
the solution of this optimization problem.

##### Targeted Poisoning.

Targeted poisoning is more task-specific. Rather than simply attempting to
increase the loss, the adversary seeks to make model predictions fall outside
a ‘safe’ set of outputs $S$ (e.g., the set of predictions matching the ground
truth). The safe set can be more specific however, i.e., mistaking a lane
marking for a person is safe, but not vice versa. As before, we formulate this
as an optimization problem:

$\max_{\mathcal{D}^{\prime}\in
T}\dfrac{1}{k}\sum_{i=1}^{k}\mathbbm{1}\big{(}f^{M(f,\theta^{\prime},\mathcal{D}^{\prime})}(x^{(i)})\notin
S\big{)}$ (2)

As before, a sound upper bound on (2) bounds the success rate of any targeted
poisoning attacker. Note that with $k=1$ we recover the pointwise certificate
setting studied by Rosenfeld et al. (2020).

##### Backdoor Poisoning.

Backdoor attacks deviate from the above attacks by assuming that test-time
data can be altered, via a so-called trigger manipulation. By assuming that
the trigger manipulation(s) are bounded to a set $V(x)$ (e.g., an
$\ell_{\infty}$ ball around the input), one can formulate the backdoor
attack’s goal as producing predictions outside a safe set $S$ (defined as
before) for manipulated inputs:

$\max_{\mathcal{D}^{\prime}\in
T}\dfrac{1}{k}\sum_{i=1}^{k}\mathbbm{1}\big{(}\exists x^{\star}\in V(x^{(i)})\
s.t.\ f^{M(f,\theta^{\prime},\mathcal{D}^{\prime})}(x^{\star})\notin S\big{)}$
(3)

Any sound upper bound to the above is a sound bound on the success rate of any
backdoor attacker.

##  4 Methodology

This section develops a novel approach for certifying the robustness of a set
of trained models described by intervals over their parameters to the above
attacks. We first formulate general algorithm before instantiating it using a
novel formulation of CROWN-style bounds which can soundly compute all of the
quantities required by our algorithm.

###  4.1 Parameter-Space Certificates of Poisoning Robustness

The key concept behind our framework is to bound the parameters obtained via
the training function $M(f,\theta^{\prime},\mathcal{D})$ given
$T(\mathcal{D})$. Before detailing the method, we first formalize our
definition of parameter-space bounds and how they can be translated into
formal, provable guarantees on poisoning robustness.

######  Definition 1.

(Valid parameter-space bounds) An interval over parameters
$[\theta^{L},\theta^{U}]$ such that $\forall i,\
\theta^{L}_{i}<\theta^{U}_{i}$ is a valid parameter-space bound on a poisoning
adversary, $T_{n,\epsilon,p}^{m,\gamma,q}(\mathcal{D})$, if $\forall i$:

$\theta^{L}_{i}\leq\min_{\mathcal{D}^{\prime}\in
T(\mathcal{D})}M(f,\theta^{\prime},\mathcal{D}^{\prime})_{i}\leq
M(f,\theta^{\prime},\mathcal{D})_{i}\leq\max_{\mathcal{D}^{\prime}\in
T(\mathcal{D})}M(f,\theta^{\prime},\mathcal{D}^{\prime})_{i}\leq\theta^{U}_{i}$
(4)

Intuitively, Definition 1 allows us to measure the poisoning adversary’s
influence in parameter space. From such bounds, we can then derive guarantees
on the poisoning robustness against any of the aforementioned attack vectors.

######  Theorem 4.1.

Given valid parameter bounds $[\theta^{L},\theta^{U}]$ for an adversary
$T_{n,\epsilon,p}^{m,\gamma,q}(\mathcal{D})$, one can compute a sound upper
bound (i.e., certificate) on any poisoning objectives by optimization the
parameter rather than dataset space space:

$\max_{\mathcal{D}^{\prime}\in
T}J\big{(}f^{M(f,\theta^{\prime},\mathcal{D}^{\prime})}(x)\big{)}\leq\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}J\big{(}f^{\theta^{\star}}(x)\big{)}$

where $J$ is one of the objective functions from (1)–(3). Full expressions are
provided in Appendix C.1.

The advantage of Theorem 4.1 is that each of these upper-bounds can be
computed directly using bounds from works studying certification of
adversarial robustness of probabilistic models (Adams et al., 2023; Wicker et
al., 2020, 2023).

###  4.2 Abstract Gradient Training for Valid Parameter Space Bounds

In this section, we provide an intuition and high-level framework for
computing parameter bounds that respect Definition 1. We call this framework
abstract gradient training (AGT). Our framework is applicable to any training
function $M$ based on first-order optimization, e.g., stochastic gradient
descent or Adam. To keep our exposition intuitive, we choose to focus on SGD,
written as:

$\displaystyle\theta^{(j+1)}$
$\displaystyle=\theta^{(j)}-\alpha\nabla_{\theta}\dfrac{1}{|\mathcal{B}^{(j)}|}\sum_{\mathcal{B}^{(j)}}\mathcal{L}\big{(}f^{\theta^{(j)}}(x^{(i)}),y^{(i)}\big{)}$
(5)

where $\mathcal{B}^{(j)}\subseteq\mathcal{D}$ is the sampled batch at
iteration $j$. The function $M(f,\theta^{\prime},\mathcal{D})$, in the
simplest case, iteratively applies the update (5) for a fixed, finite number
of iterations starting from $\theta^{(0)}=\theta^{\prime}$. Therefore, to
bound the effect of a poisoning attack, we can iteratively apply bounds on
update (5).

In Algorithm 1, we present a general framework for computing parameter-space
bounds on the output of SGD given a poisoning adversary. In particular, we
highlight that Algorithm 1 first computes the standard forward and backward
passes, and then defines optimization problems that bound their quantities
given the poisoning adversary. We will discuss solutions to these optimization
problems in detail in Section 4.3. The only non-standard operations in
Algorithm 1 are on lines 16-17, which sum the top $k$ element-wise maxima and
minima over the parameter gradient. These operations are described in detail
in our proof of the following theorem in Appendix C.2.

######  Theorem 4.2.

Algorithm 1 returns valid parameter-space bounds on a
$T_{n,\epsilon,p}^{m,\gamma,q}(\mathcal{D})$ poisoning adversary for a
stochastic gradient descent training procedure
$M(f,\theta^{\prime},\mathcal{D})$.

Algorithm 1 Abstract Gradient Training (Poisoning Certification)

Input: $f$ \- model, $\theta^{\prime}$ \- init. param., $E$ \- epochs, $b$ \-
batch-size, $\alpha$ \- learn. rate, and poisoning adv:
$n,\epsilon,p,m,\gamma,q$.
Output: Valid parameter space bounds on poisoning adversary for stochastic
gradient descent.

1:$\theta^{L}=\theta^{\prime};\theta^{U}=\theta^{\prime}$;
$\theta=\theta^{\prime}$ 2:for $E$-many epochs do 3: for Each mini-batch,
$\mathcal{B}^{(j)}$ do 4:
$d^{L}\leftarrow[\emptyset];d^{U}\leftarrow[\emptyset]$ 5: for Input-label
pair $(x^{(i)},y^{(i)})\in\mathcal{B}^{(j)}$ do 6:
$\hat{y}^{(i)}=f^{\theta}(x^{(i)})$;
$l^{(i)}=\mathcal{L}(\hat{y}^{(i)},{y}^{(i)})$; $\delta=\partial
l/\partial\theta$ $\triangleright$ Normal forward and backwards pass 7: #
Bounds to account for worst-case poisoning adversary effects 8:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\check{y}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\check{y}^{(i)}_{U}}=\min\&\max\left\\{f^{\theta^{\star}}(x^{\star})\mid{\theta^{\star}\in\left[\theta^{L},\theta^{U}\right],\|x^{(i)}-x^{\star}\|_{p}\leq\epsilon}\right\\}$
$\triangleright$ §4.3.1 9:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\partial\check{l}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\partial\check{l}^{(i)}_{U}}=\min\&\max\left\\{\partial\mathcal{L}(y^{\star},y^{\prime})/\partial
y^{\star}\mid{y^{\star}\in\left[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\check{y}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\check{y}^{(i)}_{U}}\right],\|y^{(i)}-y^{\prime}\|_{q}\leq\gamma}\right\\}$
$\triangleright$ §A 10:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\check{\delta}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\check{\delta}^{(i)}_{U}}=\min\&\max\left\\{\partial
l/\partial\theta^{\star}\mid{\partial l/\partial
y^{\star}\in\left[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\partial\check{l}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\partial\check{l}^{(i)}_{U}}\right],\theta^{\star}\in\left[\theta^{L},\theta^{U}\right]}\right\\}$$\triangleright$
§4.3.2 11: # Bounds to account for the effect of previous adversarial
manipulations 12:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\tilde{y}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\tilde{y}^{(i)}_{U}}=\min\&\max\left\\{f^{\theta^{\star}}(x)\mid{\theta^{\star}\in\left[\theta^{L},\theta^{U}\right]}\right\\}$
13:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\partial\tilde{l}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\partial\tilde{l}^{(i)}_{U}}=\min\&\max\left\\{\partial\mathcal{L}(y^{\star},y^{(i)})/\partial
y^{\star}\mid{y^{\star}\in\left[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\tilde{y}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\tilde{y}^{(i)}_{U}}\right]}\right\\}$
14:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\tilde{\delta}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\tilde{\delta}^{(i)}_{U}}=\min\&\max\left\\{\partial
l/\partial\theta^{\star}\mid{\partial l/\partial
y^{\star}\in\left[{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\partial\tilde{l}^{(i)}_{L}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\partial\tilde{l}^{(i)}_{U}}\right],\theta^{\star}\in\left[\theta^{L},\theta^{U}\right]}\right\\}$
15: $d=1/b\sum_{i=1}^{b}\delta^{(i)}$ 16:
$d^{U}=1/b\left(\sum\limits_{i=1}^{b}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\tilde{\delta}^{(i)}_{U}}+\text{SEMax}_{\max(m,n)}\left({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\check{\delta}^{(\star)}_{U}}-{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\tilde{\delta}^{(\star)}_{U}}\right)\right)$
$\triangleright$ Sum Top-k EW max.  17:
$d^{L}=1/b\left(\sum\limits_{i=1}^{b}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\tilde{\delta}^{(i)}_{L}}+\text{SEMin}_{\max(m,n)}\left({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\check{\delta}^{(\star)}_{L}}-{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\tilde{\delta}^{(\star)}_{L}}\right)\right)$
$\triangleright$ Sum Top-k EW min.  18: $\theta=\theta-\alpha d$;
$\quad\theta^{L}=\theta^{L}-\alpha d^{U}$;
$\quad\theta^{U}\leftarrow\theta^{U}-\alpha d^{L}$ 19:return
$[\theta^{L},\theta^{U}],\theta$

###  4.3 Sound Computation of Abstract Gradients

While solving the non-convex optimization problems in Algorithm 1 (lines 8–14)
exactly is NP-hard, we can compute bounds that can introduce (significant)
over-approximation of the reachable set, but will always maintain soundness.
Future work could investigate exact solutions, e.g., via mixed-integer
programming (Huchette et al., 2023; Tsay et al., 2021). Owing to their
tractability, our discussion focuses on the novel, explicit bound propagation
techniques we develop for abstract gradient training. We first define a neural
network model $f^{\theta}:\mathbb{R}^{n_{0}}\rightarrow\mathbb{R}^{n_{K}}$
with $K$ layers and parameters
$\theta=\left\\{(W^{(i)},b^{(i)})\right\\}_{i=1}^{K}$ as:

$\displaystyle\hat{z}^{(k)}=W^{(k)}z^{(k-1)}+b^{(k)},\quad
z^{(k)}=\sigma\left(\hat{z}^{(k)}\right)$

where $z^{(0)}=x$, $f^{\theta}(x)=\hat{z}^{(K)}$, and $\sigma$ is the
activation function, which we take to be ReLU.

####  4.3.1 Forward Pass Bounds

Solving problems of the form:
$\min\left\\{\cdot\mid{x^{\star}\in[x-\epsilon,x+\epsilon]}\right\\}$ has been
well-studied in the context of adversarial robustness certification. However,
optimizing over both inputs and parameters, i.e., $\min\left\\{\cdot\mid
x^{\star}\in[x-\epsilon,x+\epsilon],\theta^{\star}\in[\theta^{L},\theta^{U}]\right\\}$
is much less well-studied, and to-date has appeared primarily in the
certification of probabilistic neural networks. Existing solutions typically
leverage double interval matrix multiplication to bound the output of each
layer of the neural network.

######  Theorem 4.3 (Double Interval Matrix Multiplication).

Given element-wise intervals over matrices $[A_{L},A_{U}]$ where
$A_{L},A_{U}\in\mathbb{R}^{n\times m}$ and $[B_{L},B_{U}]$ where
$B_{L},B_{U}\in\mathbb{R}^{m\times k}$, define the matrices
$A_{\mu}=(A_{U}+A_{L})/2$ and $A_{r}=(A_{U}-A_{L})/2$. Allow $B_{\mu}$ and
$B_{r}$ to be defined analogously, then computing using Rump’s algorithm
(Rump, 1999),

$\displaystyle C_{L}=A_{\mu}B_{\mu}-|A_{\mu}|B_{r}-A_{r}|B_{\mu}|-A_{r}B_{r}$
$\displaystyle C_{U}=A_{\mu}B_{\mu}+|A_{\mu}|B_{r}+A_{r}|B_{\mu}|+A_{r}B_{r},$

we have that $C_{Li,j}\leq\left[A^{\prime}B^{\prime}\right]_{i,j}\leq
C_{Ui,j}\ \forall A^{\prime}\in[A_{L},A_{U}],\ B^{\prime}\in[B_{L},B_{U}]$.
Nguyen (2012) showed that the above bounds have a worst-case overestimation
factor of 1.5.

For ease of exposition, we will now represent interval matrices with bold
symbols i.e., $\boldsymbol{A}:=\left[\underline{A},\overline{A}\;\right]$ and
interval matrix multiplication per Theorem 4.3 as $\otimes$, meaning
$AB\in\boldsymbol{A}\otimes\boldsymbol{B}$ for all $A\in\boldsymbol{A}$ and
$B\in\boldsymbol{B}$. Additionally, we define $\odot$ and $\oplus$ as element-
wise interval matrix multiplication and addition, respectively. This implies
$A\circ B\in\boldsymbol{A}\odot\boldsymbol{B}$ and
$A+B\in\boldsymbol{A}\oplus\boldsymbol{B}$ for all $A\in\boldsymbol{A}$ and
$B\in\boldsymbol{B}$, which can be computed using standard interval arithmetic
techniques. We denote interval vectors as
$\boldsymbol{a}:=\left[\underline{a},\overline{a}\right]$ with analogous
operations.

Mirroring developments in robustness certification of neural networks, we
provide a novel, explicit extension of the CROWN algorithm (Zhang et al.,
2018) to account for interval-bounded weights. The standard CROWN algorithm
bounds the outputs of the $m$-th layer of a neural network by back-propagating
linear bounds over each intermediate activation function to the input layer.
We extend this framework to interval parameters, where the weights and biases
involved in these linear relaxations are themselves intervals. We note that
linear bound propagation with interval parameters has been studied previously
in the context of floating-point sound certification (Singh et al., 2019).
Here, we present an explicit instantiation of the CROWN algorithm for interval
parameters:

######  Proposition 1 (Explicit output bounds of neural network $f$ with
interval parameters).

Given an $m$-layer neural network function
$f:\mathbb{R}^{n_{0}}\rightarrow\mathbb{R}^{n_{m}}$ whose unknown parameters
lie in the intervals ${b}^{(k)}\in\boldsymbol{b}^{(k)}$ and
$W^{(k)}\in\boldsymbol{W}^{(k)}$ for $k=1,\dots,m$, there exist two explicit
functions

$\displaystyle
f_{j}^{L}\left({x},{\Omega}^{(0:m)},{\Theta}^{(1:m)},{b}^{(1:m)}\right)={\Omega}_{j,:}^{(0)}{x}+\sum_{k=1}^{m}{\Omega}_{j,:}^{(k)}\left({b}^{(k)}+{\Theta}_{:,j}^{(k)}\right)$
(6) $\displaystyle
f_{j}^{U}\left({x},{\Lambda}^{(0:m)},{\Delta}^{(1:m)},{b}^{(1:m)}\right)={\Lambda}_{j,:}^{(0)}{x}+\sum_{k=1}^{m}{\Lambda}_{j,:}^{(k)}\left({b}^{(k)}+{\Delta}_{:,j}^{(k)}\right)$
(7)

such that $\forall x\in\boldsymbol{x}$

$\displaystyle
f_{j}(x)\geq\min\left\\{f_{j}^{L}\left({x},{\Omega}^{(0:m)},{\Theta}^{(1:m)},{b}^{(1:m)}\right)\mid{\Omega}^{(k)}\in\mathbf{\Omega}^{(k)},{b}^{k}\in{\boldsymbol{b}}^{(k)}\right\\}$
$\displaystyle
f_{j}({x})\leq\max\left\\{f_{j}^{U}\left({x},{\Lambda}^{(0:m)},{\Delta}^{(1:m)},{b}^{(1:m)}\right)\mid{\Lambda}^{(k)}\in{\mathbf{\Lambda}}^{(k)},{b}^{k}\in{\boldsymbol{b}}^{(k)}\right\\}$

where $\boldsymbol{x}$ is a closed input domain and
${\Lambda}^{(0:m)},{\Delta}^{(1:m)},{\Omega}^{(0:m)},{\Theta}^{(1:m)}$ are the
equivalent weights and biases of the upper and lower linear bounds,
respectively. The bias terms ${\Delta}^{(1:m)},{\Theta}^{(1:m)}$ are
explicitly computed based on the linear bounds on the activation functions.
The weights ${\Lambda}^{(0:m)},{\Omega}^{(0:m)}$ lie in intervals
$\mathbf{\Lambda}^{(0:m)},\mathbf{\Omega}^{(0:m)}$ which are computed in an
analogous way to standard (non-interval) CROWN. Full details of this
computation can be found in Appendix B.

##### Closed-form Global Bounds.

Given the two functions $f_{j}^{L}(\cdot)$, $f_{j}^{U}(\cdot)$ as defined
above and intervals over all the relevant variables, we can compute the
following interval enclosures:

$\displaystyle\left[\underline{\gamma}^{L}_{j},\overline{\gamma}^{L}_{j}\right]={\mathbf{\Omega}}^{(0)}_{{j,:}}\otimes\boldsymbol{x}\oplus\sum_{k=1}^{m}{\boldsymbol{\Omega}}^{(k)}_{j,:}\otimes\left[{\boldsymbol{b}}^{(k)}\oplus{{\Theta}}^{(k)}_{:,j}\right]$
$\displaystyle\left[\underline{\gamma}^{U}_{j},\overline{\gamma}^{U}_{j}\right]={\mathbf{\Omega}}^{(0)}_{{j,:}}\otimes\boldsymbol{x}\oplus\sum_{k=1}^{m}{\boldsymbol{\Lambda}}^{(k)}_{j,:}\otimes\left[{\boldsymbol{b}}^{(k)}\oplus{{\Delta}}^{(k)}_{:,j}\right]$

Then, we have $\underline{\gamma}^{L}_{j}\leq
f_{j}({x})\leq\overline{\gamma}^{U}_{j}$ for all ${x}\in\boldsymbol{x}$,
${b}^{(k)}\in\boldsymbol{b}^{{(k)}}$ and
${W}^{(k)}\in{\boldsymbol{W}}^{{(k)}}$, which suffices to bound the
optimization problems on lines 8 and 12 of Algorithm 1.

####  4.3.2 Backwards Pass Bounds

We now turn to bound the optimization problems on lines 9 and 13 of Algorithm
1:

${{\delta}_{L}},{{\delta}_{U}}=\min\&\max\left\\{\partial
l/\partial\theta^{\star}\mid{\partial l/\partial
y^{\star}\in\left[{\partial{l}_{L}},{\partial{l}_{U}}\right],\theta^{\star}\in\left[\theta^{L},\theta^{U}\right]},\hat{z}^{(k)}\in\left[\hat{z}^{(k)}_{L},\hat{z}^{(k)}_{U}\right]\right\\}$

The bounds on the intermediate ReLU activations ($\hat{z}^{(k)}_{L}$ and
$\hat{z}^{(k)}_{U}$) are obtained using CROWN, and the bounds on the partial
derivative $\left[{\partial{l}_{L}},{\partial{l}_{U}}\right]$ are derived from
the loss function (Appendix A discusses several common choices).

We extend the interval arithmetic based approach of Wicker et al. (2022) to
bound derivatives of the form ${\partial\mathcal{L}}/{\partial z^{(k)}}$ to
additionally compute bounds on the derivatives w.r.t. the parameters. We use
the double matrix interval arithmetic defined in § 4.3.1 to propagate
intervals (bolded as before) through the backwards pass. Specifically, we can
back-propagate
$\boldsymbol{{\partial\mathcal{L}}/{\partial\hat{z}^{(K)}}}=\left[{\partial{l}_{L}},{\partial{l}_{U}}\right]$
to obtain

$\displaystyle\boldsymbol{\frac{\partial\mathcal{L}}{\partial z^{(k-1)}}}$
$\displaystyle=\left(\boldsymbol{W^{(k)}}\right)^{\top}\otimes\boldsymbol{\frac{\partial\mathcal{L}}{\partial\hat{z}^{(k)}}},\quad\boldsymbol{\frac{\partial\mathcal{L}}{\partial\hat{z}^{(k)}}}=\left[H\left(\hat{z}^{(k)}_{L}\right),H\left(\hat{z}^{(k)}_{U}\right)\right]\odot\boldsymbol{\frac{\partial\mathcal{L}}{\partial
z^{(k)}}}$ $\displaystyle\boldsymbol{\frac{\partial\mathcal{L}}{\partial
W^{(k)}}}$
$\displaystyle=\boldsymbol{\frac{\partial\mathcal{L}}{\partial\hat{z}^{(k)}}}\otimes\left[\left(\hat{z}^{(k)}_{L}\right)^{\top},\left(\hat{z}^{(k)}_{U}\right)^{\top}\right],\quad\boldsymbol{\frac{\partial\mathcal{L}}{\partial
b^{(k)}}}=\boldsymbol{\frac{\partial\mathcal{L}}{\partial\hat{z}^{(k)}}}$

where $H(\cdot)$ is the Heaviside function, and $\circ$ is the Hadamard
product. The resulting intervals are valid bounds for each partial derivative,
that is ${{\partial\mathcal{L}}/{\partial
W^{(k)}}}\in\boldsymbol{{\partial\mathcal{L}}/{\partial W^{(k)}}}$ for all
$W^{(k)}\in\boldsymbol{W^{(k)}}$, $\partial l/\partial
y^{\star}\in\left[{\partial{l}_{L}},{\partial{l}_{U}}\right]$ and
$\hat{z}^{(k)}\in\left[\hat{z}^{(k)}_{L},\hat{z}^{(k)}_{U}\right]$.

###  4.4 Algorithm Analysis and Discussion

Figure 1 visualizes the resulting worst-case decision boundaries for a simple
binary classifier. We chose adversary parameters that produce similar bounds
across the four plots to demonstrate how the bounds scale with each parameter.
In this classification setting, label poisoning results in looser bounds than
feature space poisoning, with $m=1$ producing bounds of approximately the same
width as $n=50$. This is due to the relatively large interval introduced by a
label flipping attack $y^{(i)}\in\\{0,1\\}$, compared to an interval of width
$\epsilon$ introduced in a feature-space attack.

In regression settings, label poisoning is relatively weaker than feature
poisoning for a given strength $\epsilon=\gamma$, since the feature-space
interval propagates through both the forward and backward training passes,
while the label only participates in the backward pass. This effect is
particularly pronounced in deep networks, since interval/CROWN bounds tend to
weaken exponentially with depth (Mao et al., 2023; Sosnin & Tsay, 2024).

Figure 1: Bounds on a classification threshold trained on the halfmoons
dataset for various poisoning attack parameter values (max samples and
strengths of feature/label poisoning).

##### Comparison to Interval Bound Propagation.

The CROWN algorithm in § 4.3.1 is not strictly tighter than interval bound
propagation (IBP). Specifically, the non-associativity of double-interval
matrix multiplication leads to significantly different intervals depending on
the order in which the multiplications are performed: IBP performs interval
matrix multiplications in a ‘forwards’ ordering, while CROWN uses a
‘backwards’ ordering. Empirically, we observe that CROWN tends to be tighter
for deeper networks, while IBP may outperform CROWN for smaller networks. In
our numerical experiments, we compute both CROWN and IBP bounds and take the
element-wise tightest bound.

##### Combined Forward-Backwards Bounds.

The CROWN algorithm can be applied to any composition of functions that can be
upper- and lower-bounded by linear equations. Therefore, it is possible to
consider both the forwards and backwards passes in a single combined CROWN
pass for many loss functions. However, linear bounds on the gradient of the
loss function tend to be relatively loose, e.g., linear bounds on the softmax
function may be orders-of-magnitude looser than constant $[0,1]$ bounds (Wei
et al., 2023). As a result, we found that the tightest bounds were obtained
using IBP/CROWN on the forward pass and IBP on the backward pass.

##  5 Experiments

Computational experiments were performed using a Python implementation of
Algorithm 1. Bounds on accuracy/error are computed by bounding the respective
optimization problem from Theorem 4.1 using IBP/CROWN. The experimental set-up
and datasets are described in Appendix D. Code repository to reproduce our
experiments can be found at:
https://github.com/psosnin/AbstractGradientTraining.

Regression of Household Power Consumption. We first consider a relatively
simple regression model for the household electric power consumption
(‘houseelectric’) dataset from the UCI repository (Hebrail & Berard, 2012)
with fully connected neural networks and MSE as loss function. Figure 2 shows
the progression of the nominal and worst/best-case MSE (computed for the test
set) for a 1$\times$50 neural network and various parameterizations of
poisoning attacks. As expected, we observe that increasing each of $n$, $m$,
$\epsilon$, and $\gamma$ results in looser performance bounds.

Figure 2: MSE bounds during training of a 1x50 neural network on
‘houseelectric’ ($b=10000$) with the red line in each figure representing the
unpoisoned MSE. Figure 3: Effect of model/training hyperparameters on MSE for
‘houseelectric’ for a fixed adversary $(n=100,\epsilon=0.01)$. Hyperparameters
$d=1,w=50,b=10000$, and $\alpha=0.02$ where not stated.

Figure 3 shows the progression of bounds on the MSE (computed for the test
set) over the training procedure for a fixed poisoning attack
($n=100,\epsilon=0.01$) and various hyperparameters of the regression model.
In general, we observe that increasing model size (width or depth) results in
looser performance guarantees. As expected, increasing the batch size improves
our bounds, as the number of potentially poisoned samples $n$ remains fixed
and their worst-case effect is ‘diluted’. Finally, increasing the learning
rate accelerates both the model training and the deterioration of the bounds.

MedMNIST Image Classification. Next, we consider fine-tuning a classifier
trained on the retinal OCT dataset (OCTMNIST) (Yang et al., 2021), which
contains four classes – one normal and three abnormal. The dataset is
unbalanced, and we consider the simpler normal vs abnormal binary
classification setting. We consider the ‘small’ architecture from Gowal et al.
(2018), comprising two convolutional layers of width 16 and 32 and a dense
layer of 100 nodes, and the following fine-tuning scenario: the model is first
pre-trained without the smallest class (Drusen). We employ the robust training
procedure from (Wicker et al., 2022) for the pre-training step so that the
resulting model is robust to feature perturbations during fine-tuning. We then
assume Drusen samples may be poisoned and add them as a new abnormal class to
fine-tune the dense layer, with a mix of 30% Drusen samples per batch. Figure
4 shows bounds on the test prediction accuracy for Drusen samples.

In general, this fine-tuning step improves accuracy on the new class (Drusen)
from approximately 0.5 to over 0.8. Nevertheless, we observe how increasing
the amount of potential poisoning worsens the bound on prediction accuracy.
With feature-only poisoning, a poisoning attack greater than $\epsilon=0.02$
over $n\approx 90$ samples produces bounds worse than the prediction accuracy
of the original pre-trained model. With label and feature poisoning, the
bounds are weaker for similar $\epsilon$, as expected. With label-only
poisoning, the training procedure requires approximately $m\approx 120$
poisoned samples for the prediction accuracy bound to reach the original pre-
trained model’s accuracy.

Figure 4: Certificates for a binary classifier fine-tuned on the Drusen class
of OCTMNIST. Left: Certified bounds on prediction accuracy. Right: Certified
bounds on prediction accuracy under a backdoor attack.

Fine-Tuning PilotNet. Finally, we fine-tune a model that predicts steering
angles for autonomous driving given an input image (Bojarski et al., 2016).
The model contains convolutional layers of 24, 36, 48, and 64 filters,
followed by fully connected layers of 100, 50, and 10 nodes. The fine-tuning
setting is similar to above. First, we pre-train the model on videos 2–6 of
the Udacity self-driving car dataset111github.com/udacity/self-driving-
car/tree/master. We then fine-tune the dense layers on video 1, which has
challenging lighting conditions, assuming the samples may contain label
poisoning.

Figure 5 shows the bounds on mean squared error for the video 1 data and
visualizes how the bounds translate to the predicted steering angle. We again
see that fine-tuning improves accuracy on the new data, but also that the MSE
bounds deteriorate as the number of potentially poisoned samples increases
(Figure 5, left). The rate of deterioration depends strongly on poisoning
strength $\gamma$.

Figure 5: Left: Certified MSE after finetuning PilotNet on unseen driving
conditions. Right: Steering angle prediction bounds after finetuning,
$\gamma=0.01,m=300$.

##  6 Conclusions

We proposed a mathematical framework for computing sound parameter-space
bounds on the influence of a poisoning attack for gradient-based training. Our
framework defines generic constraint sets to represent general poisoning
attacks and propagates them through the forward and backward passes of model
training. Based on the resulting parameter-space bounds, we provided rigorous
bounds on the effects of various poisoning attacks. Finally, we demonstrated
our proposed approach to be effective on tasks including autonomous driving
and the classification of medical images.

## References

  * Adams et al. (2023) Adams, S., Patane, A., Lahijanian, M., and Laurenti, L.  Bnn-dp: robustness certification of bayesian neural networks via dynamic programming.  In _International Conference on Machine Learning_ , pp. 133–151. PMLR, 2023.
  * Biggio & Roli (2018) Biggio, B. and Roli, F.  Wild patterns: Ten years after the rise of adversarial machine learning.  In _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , pp. 2154–2156, 2018.
  * Biggio et al. (2014) Biggio, B., Rieck, K., Ariu, D., Wressnegger, C., Corona, I., Giacinto, G., and Roli, F.  Poisoning behavioral malware clustering.  In _Proceedings of the 2014 workshop on artificial intelligent and security workshop_ , pp. 27–36, 2014.
  * Bojarski et al. (2016) Bojarski, M., Del Testa, D., Dworakowski, D., Firner, B., Flepp, B., Goyal, P., Jackel, L. D., Monfort, M., Muller, U., Zhang, J., et al.  End to end learning for self-driving cars.  _arXiv preprint arXiv:1604.07316_ , 2016.
  * Botoeva et al. (2020) Botoeva, E., Kouvaros, P., Kronqvist, J., Lomuscio, A., and Misener, R.  Efficient verification of relu-based neural networks via dependency analysis.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 3291–3299, 2020.
  * Bunel et al. (2018) Bunel, R. R., Turkaslan, I., Torr, P., Kohli, P., and Mudigonda, P. K.  A unified view of piecewise linear neural network verification.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Carlini et al. (2023) Carlini, N., Jagielski, M., Choquette-Choo, C. A., Paleka, D., Pearce, W., Anderson, H., Terzis, A., Thomas, K., and Tramèr, F.  Poisoning web-scale training datasets is practical.  _arXiv preprint arXiv:2302.10149_ , 2023.
  * Chen et al. (2017) Chen, X., Liu, C., Li, B., Lu, K., and Song, D.  Targeted backdoor attacks on deep learning systems using data poisoning.  _arXiv preprint arXiv:1712.05526_ , 2017.
  * Gehr et al. (2018) Gehr, T., Mirman, M., Drachsler-Cohen, D., Tsankov, P., Chaudhuri, S., and Vechev, M.  Ai2: Safety and robustness certification of neural networks with abstract interpretation.  In _2018 IEEE symposium on security and privacy (SP)_ , pp. 3–18. IEEE, 2018.
  * Gowal et al. (2018) Gowal, S., Dvijotham, K., Stanforth, R., Bunel, R., Qin, C., Uesato, J., Arandjelovic, R., Mann, T., and Kohli, P.  On the effectiveness of interval bound propagation for training verifiably robust models.  _arXiv preprint arXiv:1810.12715_ , 2018.
  * Gu et al. (2017) Gu, T., Dolan-Gavitt, B., and Garg, S.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  _arXiv preprint arXiv:1708.06733_ , 2017.
  * Han et al. (2021) Han, X., Zhang, Z., Ding, N., Gu, Y., Liu, X., Huo, Y., Qiu, J., Yao, Y., Zhang, A., Zhang, L., et al.  Pre-trained models: Past, present and future.  _AI Open_ , 2:225–250, 2021.
  * Han et al. (2022) Han, X., Xu, G., Zhou, Y., Yang, X., Li, J., and Zhang, T.  Physical backdoor attacks to lane detection systems in autonomous driving.  In _Proceedings of the 30th ACM International Conference on Multimedia_ , pp. 2957–2968, 2022.
  * Hebrail & Berard (2012) Hebrail, G. and Berard, A.  Individual Household Electric Power Consumption.  UCI Machine Learning Repository, 2012.  DOI: https://doi.org/10.24432/C58K54.
  * Hong et al. (2020) Hong, S., Chandrasekaran, V., Kaya, Y., Dumitraş, T., and Papernot, N.  On the effectiveness of mitigating data poisoning attacks with gradient shaping.  _arXiv preprint arXiv:2002.11497_ , 2020.
  * Huchette et al. (2023) Huchette, J., Muñoz, G., Serra, T., and Tsay, C.  When deep learning meets polyhedral theory: A survey.  _arXiv preprint arXiv:2305.00241_ , 2023.
  * Katz et al. (2017) Katz, G., Barrett, C., Dill, D. L., Julian, K., and Kochenderfer, M. J.  Reluplex: An efficient smt solver for verifying deep neural networks.  In _Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part I 30_ , pp. 97–117. Springer, 2017.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Li et al. (2020) Li, S., Cheng, Y., Wang, W., Liu, Y., and Chen, T.  Learning to detect malicious clients for robust federated learning.  _arXiv preprint arXiv:2002.00211_ , 2020.
  * Mao et al. (2023) Mao, Y., Müller, M. N., Fischer, M., and Vechev, M. T.  Understanding certified training with interval bound propagation.  _CoRR_ , abs/2306.10426, 2023.  doi: 10.48550/ARXIV.2306.10426.  URL https://doi.org/10.48550/arXiv.2306.10426.
  * Müller et al. (2022) Müller, M. N., Eckert, F., Fischer, M., and Vechev, M.  Certified training: Small boxes are all you need.  _arXiv preprint arXiv:2210.04871_ , 2022.
  * Muñoz-González et al. (2017) Muñoz-González, L., Biggio, B., Demontis, A., Paudice, A., Wongrassamee, V., Lupu, E. C., and Roli, F.  Towards poisoning of deep learning algorithms with back-gradient optimization.  In _Proceedings of the 10th ACM workshop on artificial intelligence and security_ , pp. 27–38, 2017.
  * Newsome et al. (2006) Newsome, J., Karp, B., and Song, D.  Paragraph: Thwarting signature learning by training maliciously.  In _Recent Advances in Intrusion Detection: 9th International Symposium, RAID 2006 Hamburg, Germany, September 20-22, 2006 Proceedings 9_ , pp. 81–105. Springer, 2006.
  * Nguyen (2012) Nguyen, H. D.  Efficient implementation of interval matrix multiplication.  In _Applied Parallel and Scientific Computing: 10th International Conference, PARA 2010, Reykjavík, Iceland, June 6-9, 2010, Revised Selected Papers, Part II 10_ , pp. 179–188. Springer, 2012.
  * Rosenfeld et al. (2020) Rosenfeld, E., Winston, E., Ravikumar, P., and Kolter, Z.  Certified robustness to label-flipping attacks via randomized smoothing.  In _International Conference on Machine Learning_ , pp. 8230–8241. PMLR, 2020.
  * Rump (1999) Rump, S. M.  Fast and parallel interval arithmetic.  _BIT Numerical Mathematics_ , 39:534–554, 1999.
  * Singh et al. (2019) Singh, G., Gehr, T., Püschel, M., and Vechev, M.  An abstract domain for certifying neural networks.  _Proc. ACM Program. Lang._ , 3(POPL), jan 2019.  doi: 10.1145/3290354.
  * Sosnin & Tsay (2024) Sosnin, P. and Tsay, C.  Scaling mixed-integer programming for certification of neural network controllers using bounds tightening.  _arXiv preprint arXiv:2403.17874_ , 2024.
  * Steinhardt et al. (2017) Steinhardt, J., Koh, P. W. W., and Liang, P. S.  Certified defenses for data poisoning attacks.  _Advances in neural information processing systems_ , 30, 2017.
  * Tian et al. (2022) Tian, Z., Cui, L., Liang, J., and Yu, S.  A comprehensive survey on poisoning attacks and countermeasures in machine learning.  _ACM Computing Surveys_ , 55(8):1–35, 2022.
  * Tsay et al. (2021) Tsay, C., Kronqvist, J., Thebelt, A., and Misener, R.  Partition-based formulations for mixed-integer optimization of trained relu neural networks.  _Advances in neural information processing systems_ , 34:3068–3080, 2021.
  * Wei et al. (2023) Wei, D., Wu, H., Wu, M., Chen, P.-Y., Barrett, C., and Farchi, E.  Convex bounds on the softmax function with applications to robustness verification, 2023.
  * Wicker et al. (2018) Wicker, M., Huang, X., and Kwiatkowska, M.  Feature-guided black-box safety testing of deep neural networks.  In _Tools and Algorithms for the Construction and Analysis of Systems: 24th International Conference, TACAS 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14-20, 2018, Proceedings, Part I 24_ , pp. 408–426. Springer, 2018.
  * Wicker et al. (2020) Wicker, M., Laurenti, L., Patane, A., and Kwiatkowska, M.  Probabilistic safety for bayesian neural networks.  In _Conference on uncertainty in artificial intelligence_ , pp. 1198–1207. PMLR, 2020.
  * Wicker et al. (2022) Wicker, M., Heo, J., Costabello, L., and Weller, A.  Robust explanation constraints for neural networks.  _arXiv preprint arXiv:2212.08507_ , 2022.
  * Wicker et al. (2023) Wicker, M., Patane, A., Laurenti, L., and Kwiatkowska, M.  Adversarial robustness certification for bayesian neural networks.  _arXiv preprint arXiv:2306.13614_ , 2023.
  * Xie et al. (2022) Xie, C., Long, Y., Chen, P.-Y., and Li, B.  Uncovering the connection between differential privacy and certified robustness of federated learning against poisoning attacks.  _arXiv preprint arXiv:2209.04030_ , 2022.
  * Yang et al. (2017) Yang, G., Gong, N. Z., and Cai, Y.  Fake co-visitation injection attacks to recommender systems.  In _NDSS_ , 2017.
  * Yang et al. (2021) Yang, J., Shi, R., and Ni, B.  MedMNIST classification decathlon: A lightweight AutoML benchmark for medical image analysis.  In _IEEE 18th International Symposium on Biomedical Imaging (ISBI)_ , pp. 191–195, 2021.
  * Zhang et al. (2018) Zhang, H., Weng, T.-W., Chen, P.-Y., Hsieh, C.-J., and Daniel, L.  Efficient Neural Network Robustness Certification with General Activation Functions.  November 2018.  doi: 10.48550/arXiv.1811.00866.  URL http://arxiv.org/abs/1811.00866.  arXiv:1811.00866 [cs, stat].
  * Zhu et al. (2019) Zhu, C., Huang, W. R., Li, H., Taylor, G., Studer, C., and Goldstein, T.  Transferable clean-label poisoning attacks on deep neural nets.  In _International conference on machine learning_ , pp. 7614–7623. PMLR, 2019.

##  Appendix A Bounds on Loss Function Gradients

In this section we present the computation of bounds on the first partial
derivative of the loss function required for Algorithm 1. In particular, we
consider the optimization problem

${\partial{l}^{L}},{\partial{l}^{U}}=\min\&\max\left\\{\partial\mathcal{L}\left(y^{\star},y^{\prime}\right)/\partial
y^{\star}\mid{y^{\star}\in\left[{{y}^{L}},{{y}^{U}}\right],\|y^{\prime}-y^{t}\|_{q}\leq\gamma}\right\\}$

for some loss function $\mathcal{L}$ where $[{{y}^{L}},{{y}^{U}}]$ are bounds
on the logits of the model and $y^{t}$ is the true label.

##### Mean Squared Error Loss

Taking
$\mathcal{L}\left(y^{\star},y^{\prime}\right)=\|y^{\star}-y^{\prime}\|^{2}_{2}$
to be the squared error and considering the $q=\infty$ norm, the required
bounds are given by:

$\displaystyle{\partial{l}^{L}}=2\left(y^{L}-y^{t}-\gamma\right)$
$\displaystyle{\partial{l}^{U}}=2\left(y^{U}-y^{t}+\gamma\right)$

##### Cross Entropy Loss

To bound the cross entropy loss, we first bound the output probabilities
$p_{i}={[\sum_{j}\exp{\left(y^{\star}_{j}-y^{\star}_{i}\right)}]^{-1}}$
obtained by passing the logits through the softmax function:

$\displaystyle
p^{L}_{i}=\left[{\sum_{j}\exp{\left(y^{U}_{j}-y^{L}_{i}\right)}}\right]^{-1},\quad
p^{U}_{i}=\left[{\sum_{j}\exp{\left(y^{L}_{j}-y^{U}_{i}\right)}}\right]^{-1}$

The categorical cross entropy loss and its first partial derivative are given
by

$\displaystyle\mathcal{L}\left(y^{\star},y^{\prime}\right)=-\sum_{i}y^{t}_{i}\log
p_{i},\quad\frac{\partial\mathcal{L}\left(y^{\star},y^{\prime}\right)}{\partial
y^{\star}}=p-y^{t}$

where $y^{t}$ is a one-hot encoding of the true label. Considering label
flipping attacks ($q=0$), we can bound the partial derivative by

$\displaystyle\left[{\partial{l}^{L}}\right]_{i}=p_{i}^{L}-1,\quad\left[\partial
l^{U}\right]_{i}=p_{i}^{U}-0$

In the case of targeted label flipping attacks (e.g. only applying label
flipping attacks to / from specific classes), stronger bounds can be obtained
by considering the $0-1$ bounds only on the indices $y^{t}_{i}$ affected by
the attack.

##  Appendix B Computation of Equivalent Weights and Biases in CROWN

Our instantiation of the CROWN algorithm in 1 relies on the computation of the
bias terms ${\Delta}^{(1:m)},{\Theta}^{(1:m)}$ and interval enclosures over
the weights ${\Omega}^{(0:m)},{\Lambda}^{(0:m)}$. This proceeds similarly to
the standard CROWN algorithm but now accounting for intervals over the
parameters $b^{(1:m)},W^{(1:m)}$ of the network.

The standard CROWN algorithm bounds the outputs of the $m$-th layer of a
neural network by back-propagating linear bounds over each intermediate
activation function to the input layer. In the case of interval parameters,
the sign of a particular weight may be ambiguous (when the interval spans
zero), making it impossible to determine which linear bound to back-propagate.
In such cases, we propagate a concrete bound for that neuron instead of its
linear bounds.

When bounding the $m$-th layer of a neural network, we assume that we have
pre-activation bounds $\hat{z}^{(k)}\in\left[{l}^{(k)},{u}^{(k)}\right]$ on
all previous layers on the network. Given such bounds, it is possible to form
linear bounds on any non-linear activation function in the network. For the
$r$-th neuron in $k$-th layer with activation function $\sigma(z)$, we define
two linear functions

$h_{L,r}^{(k)}(z)=\alpha_{L,r}^{(k)}\left(z+\beta_{L,r}^{(k)}\right),\quad
h_{U,r}^{(k)}(z)=\alpha_{U,r}^{(k)}\left(z+\beta_{U,r}^{(k)}\right)$

such that $h_{L,r}^{(k)}(z)\leq\sigma(z)\leq h_{U,r}^{(k)}(z)\ \forall
z\in\left[{l}_{r}^{(k)},{u}_{r}^{(k)}\right]$. The coefficients
$\alpha_{U,r}^{(k)},\alpha_{L,r}^{(k)},\beta_{U,r}^{(k)},\beta_{L,r}^{(k)}\in\mathbb{R}$
are readily computed for many common activation functions (Zhang et al.,
2018).

Given the pre-activation and activation function bounds, the interval
enclosures over the weights ${\Omega}^{(0:m)},{\Lambda}^{(0:m)}$ are computed
via a back-propagation procedure. The back-propagation is initialised with
$\boldsymbol{\Omega}^{(m)}=\boldsymbol{\Lambda}^{(m)}=\left[{I}^{n_{m}},{I}^{n_{m}}\right]$
and proceeds as follows:

$\displaystyle{\boldsymbol{\Lambda}}^{(k-1)}=\left({\boldsymbol{\Lambda}}^{(k)}\otimes{\mathbf{W}}^{(k)}\right)\odot{\lambda}^{(k-1)},\quad{\lambda}^{(k)}_{{j,i}}=$
$\displaystyle\begin{cases}\alpha_{U,i}^{(k)}&\text{ if }k\neq 0,\
0\leq{\left[\boldsymbol{\Lambda}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
\alpha_{L,i}^{(k)}&\text{ if }k\neq 0,\
0\geq{\left[\boldsymbol{\Lambda}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
0&\text{ if }k\neq 0,\
0\in{\left[\boldsymbol{\Lambda}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
1&\text{ if }k=0.\end{cases}$
$\displaystyle{\boldsymbol{\Omega}}^{(k-1)}=\left({\boldsymbol{\Omega}}^{(k)}\otimes{\mathbf{W}}^{(k)}\right)\odot{{\omega}}^{(k-1)},\quad{\omega}^{(k)}_{{j,i}}=$
$\displaystyle\begin{cases}\alpha_{L,i}^{(k)}&\text{ if }k\neq 0,\
0\leq{\left[\boldsymbol{\Omega}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
\alpha_{U,i}^{(k)}&\text{ if }k\neq 0,\
0\geq{\left[\boldsymbol{\Omega}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
0&\text{ if }k\neq 0,\
0\in{\left[\boldsymbol{\Omega}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
1&\text{ if }k=0.\end{cases}$

where we use $0\leq[\cdot]$ and $0\geq[\cdot]$ to denote that an interval is
strictly positive or negative, respectively.

Finally, the bias terms ${\Delta}^{(k)},{\Theta}^{(k)}$ for all $k<m$ can be
computed as

${{\Delta}}^{(k)}_{{i,j}}=\begin{cases}\beta_{U,i}^{(k)}&\text{ if
}0\leq{\left[\boldsymbol{\Lambda}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
\beta_{L,i}^{(k)}&\text{ if
}0\geq{\left[\boldsymbol{\Lambda}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
u^{(k)}&\text{ if
}0\in{\left[\boldsymbol{\Lambda}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
\end{cases},\hfill{{\Theta}}^{(k)}_{{i,j}}=\begin{cases}\beta_{L,i}^{(k)}&\text{
if
}0\leq{\left[\boldsymbol{\Omega}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
\beta_{U,i}^{(k)}&\text{ if
}0\geq{\left[\boldsymbol{\Omega}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
l^{(k)}&\text{ if
}0\in{\left[\boldsymbol{\Omega}^{(k+1)}\otimes\mathbf{W}^{(k+1)}\right]}_{{j,i}}\\\
\end{cases}$

with the $m$-th bias terms given by
${{\Theta}}^{(m)}_{{i,j}}={{\Delta}}^{(m)}_{{i,j}}=0$.

##  Appendix C Proofs

In this section we provide formal proofs of the theorems stated in the main
text.

###  C.1 Proof of Theorem 4.1

We begin the proof by writing out the form of the function we wish to
optimize, $J$, for each attack setting considered. Below the right hand side
of the inequality is taken to be the function $J$, and each inequality is the
statement we would like to prove.

For denial of service our bound becomes:

$\max_{\mathcal{D}^{\prime}\in
T}\dfrac{1}{k}\sum_{i=1}^{k}\mathcal{L}\big{(}f^{M(f,\theta^{\prime},\mathcal{D}^{\prime})}(x^{(i)}),y^{(i)}\big{)}\leq\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\dfrac{1}{k}\sum_{i=1}^{k}\mathcal{L}\big{(}f^{\theta^{\star}}(x^{(i)}),y^{(i)}\big{)}$

For certified prediction poisoning robustness our bound becomes:

$\max_{\mathcal{D}^{\prime}\in
T}\dfrac{1}{k}\sum_{i=1}^{k}\mathbbm{1}\big{(}f^{M(f,\theta^{\prime},\mathcal{D}^{\prime})}(x^{(i)})\notin
S\big{)}\leq\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\dfrac{1}{k}\sum_{i=1}^{k}\mathbbm{1}\big{(}f^{\theta^{\star}}(x^{(i)})\notin
S\big{)}$

And for backdoor attacks our bound becomes:

$\displaystyle\max_{\mathcal{D}^{\prime}\in T}$
$\displaystyle\dfrac{1}{k}\sum_{i=1}^{k}\mathbbm{1}\big{(}\exists x^{\star}\in
V(x^{(i)})\ s.t.\
f^{M(f,\theta^{\prime},\mathcal{D}^{\prime})}(x^{\star})\notin S\big{)}$
$\displaystyle\leq\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\dfrac{1}{k}\sum_{i=1}^{k}\mathbbm{1}\big{(}\exists
x^{\star}\in V(x^{(i)})\ s.t.\ f^{\theta^{\star}}(x^{\star})\notin S\big{)}$

##### Proof:

Without loss of generality, take the function we wish to optimize to be
denoted simply by $J$. By definition, there exists a parameter,
$\theta^{\circ}=M(f,\theta^{\prime},\mathcal{D}^{\prime})$ resulting from a
particular dataset $\mathcal{D}^{\prime}\in T(\mathcal{D})$ such that
$\theta^{\circ}$ provides a (potentially non-unique) optimal solution to the
optimization problem we wish to bound, i.e., the left hand side of the
inequalities above. Given a valid parameter space bound
$[\theta^{L},\theta^{U}]$ satisfying Equation 4, we have that necessarily,
$\theta^{\circ}\in[\theta^{L},\theta^{U}]$. Therefore, the result of
optimizing over $[\theta^{L},\theta^{U}]$ can provide at a minimum the bound
realized by $\theta^{\circ}$; however, due to approximation, this bound might
not be tight, so optimizing over $[\theta^{L},\theta^{U}]$ provides an upper-
bound, thus proving the inequalities above. ∎

###  C.2 Algorithm Correctness Proof (Theorem 4.2)

Here we provide a proof of correctness for our algorithm (i.e., proof of
Theorem 4.2) as well as a detailed discussion of the operations therein.

First, we recall the definition of valid parameter space bounds (Equation 4 in
the main text):

$\theta^{L}_{i}\leq\min_{\mathcal{D}^{\prime}\in
T(\mathcal{D})}M(f,\theta^{\prime},\mathcal{D}^{\prime})_{i}\leq
M(f,\theta^{\prime},\mathcal{D})_{i}\leq\max_{\mathcal{D}^{\prime}\in
T(\mathcal{D})}M(f,\theta^{\prime},\mathcal{D}^{\prime})_{i}\leq\theta^{U}_{i}$

As well as the iterative equations for stochastic gradient descent:

$\displaystyle\theta^{(0)}$ $\displaystyle=\theta^{\prime}$
$\displaystyle\theta^{(i+1)}$
$\displaystyle=\theta^{(i)}-\alpha\dfrac{1}{b}\sum_{j=1}^{b}\nabla_{\theta}\mathcal{L}(f^{\theta^{(i)}}(x^{(j)}),y^{(j)})$

For ease of notation, we assume a fixed data ordering (one may always take the
element-wise maximums/minimums over the entire dataset rather than each batch
to relax this assumption), and we denote $\theta^{(1)}_{\mathcal{D}}$ as the
value of the parameters at the $i$-th iteration given the dataset
$\mathcal{D}$ with fixed ordering.

Now, we proceed to prove by induction that Algorithm 1 maintains valid
parameter space bounds on each step of gradient descent. We start with the
base case where $\theta^{L}=\theta^{U}=\theta^{\prime}$ according to line 1,
and now we prove that the result of the first batch (lines 5–18) produces a
new $\theta^{L}$ and $\theta^{U}$ that satisfy Definition 1. First, we observe
that lines 12–14 simply compute the normal forward pass, due to the fact that
$\theta^{L}=\theta^{U}$. Lines 8–10 can be combined and written (using the
indexing from the above iterative SGD equations) as the following optimization
problems:

$\displaystyle{\delta}^{(j)}_{L}=\min_{y^{\prime}\in\|y^{(i)}-y^{\prime}\|_{q}<\gamma,x^{\prime}\in\|x^{(i)}-x^{\prime}\|_{q}<\epsilon}\nabla_{\theta}\mathcal{L}(f^{\theta}(x^{\prime}),y^{\prime})$
(8)
$\displaystyle{\delta}^{(j)}_{U}=\max_{y^{\prime}\in\|y^{(i)}-y^{\prime}\|_{q}<\gamma,x^{\prime}\in\|x^{(i)}-x^{\prime}\|_{q}<\epsilon}\nabla_{\theta}\mathcal{L}(f^{\theta}(x^{\prime}),y^{\prime})$
(9)

From the soundness of bound propagation for automatic differentiation (see
Wicker et al. (2022)), we have that
$\check{\delta}^{(j)}_{L}<{\delta}^{(j)}_{L}$ and that
$\check{\delta}^{(j)}_{U}>{\delta}^{(j)}_{U}$, thus $\forall j\in[b]$ we have
sound bounds on the gradient computation. Assume that the adversary can only
manipulate a single feature and label (though not necessarily from the same
index), and further that these manipulations are present in every sampled
batch (a source of over-approximation). Then we have that $m=n=1$, and we know
that the largest increase that an adversary can make for any term in the
expression
$\dfrac{1}{b}\sum_{j=1}^{b}\nabla_{\theta}\mathcal{L}(f^{\theta^{(i)}}(x^{(j)}),y^{(j)})$
is given by the element-wise maximum over the all possible increases
$\\{\check{\delta}_{U}^{(j)}-\delta^{(j)}\\}$.

Assuming $m=n=2$, we have that the largest increase to an adversary could make
to
$\dfrac{1}{b}\sum_{j=1}^{b}\nabla_{\theta}\mathcal{L}(f^{\theta^{(i)}}(x^{(j)}),y^{(j)})$
would be to first make the largest change (element-wise maximum) above, and
then to make the largest remaining change after that corresponding to the
maximum of the remaining possible changes (the summation structure implies no
interactions between samples). From this, we can generalize to the case that
if $m>n>1$, then we take the sum of the top-$m$ possible changes (top-$m$
element-wise maximum) as the largest possible adversarial effect on the batch.
Combining this largest possible change with the iterative SGD equation we have
that:

$\forall\mathcal{D}^{\prime}\in
T_{n,\epsilon,p}^{m,\gamma,q}(\mathcal{D}),\theta^{(1)}_{\mathcal{D}^{\prime}}\leq\theta^{\prime}-\alpha/b\left(\sum\limits_{j=1}^{b}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\delta}^{(j)}_{U}}+\text{SEMax}_{\max(m,n)}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\check{\delta}^{(\star)}_{U}}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\delta}}\right)\right).$
(10)

A corresponding argument holds for the maximum and thus we have that
$\forall\mathcal{D}^{\prime}\in T_{n,\epsilon,p}^{m,\gamma,q}(\mathcal{D})$:

$\displaystyle\theta^{\prime}-\alpha/b\left(\sum\limits_{j=1}^{b}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\delta}^{(j)}_{L}}+\text{SEMin}_{\max(m,n)}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\check{\delta}^{(\star)}_{L}}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\delta}^{(\star)}_{L}}\right)\right)$
$\displaystyle\geq$ $\displaystyle\theta^{(1)}_{\mathcal{D}}$
$\displaystyle\geq$
$\displaystyle\theta^{\prime}-\alpha/b\left(\sum\limits_{j=1}^{b}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\delta}^{(j)}_{U}}+\text{SEMax}_{\max(m,n)}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\check{\delta}^{(\star)}_{U}}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}{\delta}}\right)\right)$

Which proves the base case that the first iteration of Algorithm 1 provides
valid parameter-space bounds.

Our inductive hypothesis is that, given that the previous iteration of the
algorithm provides valid parameter-space bounds, denoted
$[\theta^{L},\theta^{U}]$, we would like to prove that the algorithm computes
valid bounds on $\theta^{(i+1)}$ for any poisoning adversary. We begin by
observing that the effect of the adversary on the current batch can be
accounted for by considering the exact optimization problem above with the
added optimization over all possible parameters, i.e.,
$\theta^{\star}\in[\theta^{L},\theta^{U}]$, which gives us:

$\max_{\theta^{\star}\in[\theta^{L},\theta^{U}],y^{\prime}\in\|y^{(j)}-y^{\prime}\|_{q}<\gamma,x^{\prime}\in\|x^{(j)}-x^{\prime}\|_{q}<\epsilon}\nabla_{\theta}\mathcal{L}(f^{\theta^{\star}}(x^{\prime}),y^{\prime})$

and the corresponding problem for the $\min$. However, the bounds in (10) no
longer hold exactly, as we now must additionally consider all possible values
$\delta$ can take, given the effect of the adversary on our previous parameter
updates. This can be accounted for by computing the following $\forall j$:

$\displaystyle\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\nabla_{\theta}\mathcal{L}(f^{\theta^{\star}}(x^{(j)}),y^{(j)})$
$\displaystyle\min_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\nabla_{\theta}\mathcal{L}(f^{\theta^{\star}}(x^{(j)}),y^{(j)})$

Using the soundness of bound propagation we have that the above optimization
problems can be bounded by $\tilde{\delta}_{L}^{(j)}$ and
$\tilde{\delta}_{U}^{(j)}$, respectively. Then, combining this largest and
smallest possible update from the clean data with the largest and smallest
updates from the adversarial data, we have that the largest and smallest total
adversarial update yields the following bounds:

$\displaystyle\theta^{U}-\alpha/b\left(\sum\limits_{j=1}^{b}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\tilde{\delta}^{(j)}_{L}}+\text{SEMin}_{\max(m,n)}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\check{\delta}^{(\star)}_{L}}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\tilde{\delta}^{(\star)}_{L}}\right)\right)$
$\displaystyle\geq$ $\displaystyle\theta^{(i+1)}_{\mathcal{D}}$
$\displaystyle\geq$
$\displaystyle\theta^{L}-\alpha/b\left(\sum\limits_{j=1}^{b}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\tilde{\delta}^{(j)}_{U}}+\text{SEMax}_{\max(m,n)}\left({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\check{\delta}^{(\star)}_{U}}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\tilde{\delta}}\right)\right)$

By definition, the above bounds constitute valid parameter-space bounds and,
given that these bounds are exactly those in Algorithm 1, we have that
Algorithm 1 provides valid parameter space bounds as desired. ∎

##  Appendix D Experimental Set-up

This section details the datasets and hyper-parameters used for the
experiments detailed in Section 5. All experiments were run on a server
equipped with 2x AMD EPYC 9334 CPUs and 2x NVIDIA L40 GPUs using an
implementation of Algorithm 1 written in Python using Pytorch.

Table 1 details the datasets along with the number of epochs, learning rate
($\alpha$), decay rate ($\eta$) and batch size ($b$) used for each. We note
that a standard learning rate decay of the form ($\alpha_{n}=\alpha/(1+\eta
n)$ was applied during training. In the case of fine-tuning both OCT-MNIST and
PilotNet, each batch consisted of a mix 70% ‘clean’ data previously seen
during pre-training and 30% new, potentially poisoned, fine-tuning data.

Dataset | #Samples | #Features | #Epochs | $\alpha$ | $\eta$ | $b$
---|---|---|---|---|---|---
UCI House-electric | 2049280 | 11 | 1 | 0.02 | 0.2 | 10000
OCT-MNIST | 97477 | 784 | 2 | 0.005 | 10.0 | 10000
Udacity Self-Driving | 31573 | 39600 | 2 | 0.25 | 10.0 | 10000
Table 1: Datasets and Hyperparameter Settings