Certified Robustness to Data Poisoning in Gradient-Based Training

## Abstract

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. Provably bounding model behavior under such attacks remains an open problem. In this work, we address this challenge by developing the first framework providing provable guarantees on the behavior of models trained with potentially manipulated data without modifying the model or learning algorithm. In particular, our framework certifies robustness against untargeted and targeted poisoning, as well as backdoor attacks, for bounded and unbounded manipulations of the training inputs and labels.
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., ).
Unfortunately, the datasets used in both steps are potentially untrustworthy and of such scale that rigorous quality checks become 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., ).
For instance, Yang et al. () show how popular recommender systems on sites such as YouTube, Ebay, and Yelp can be easily manipulated by poisoning. Likewise, Zhu et al. () show that poisoning even 1% of training data can lead models to misclassify targeted examples, and Han et al. () 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., ). 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. In effect, 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.
These methods are often limited in scope, e.g., applying only to linear models (Rosenfeld et al., ; Steinhardt et al., ) or only providing approximate guarantees for a limited set of poisoning settings (Rosenfeld et al., ; Xie et al., ). Other approaches partition datasets into hundreds or thousands of disjoint shards and then aggregate predictions such that the effects of poisoning is provably limited (Levine & Feizi, ; Wang et al., ). In contrast, our goal in this work is not to produce a robust learning algorithm, but to efficiently analyze the sensitivity of (un-modified) algorithms.
Further discussion of related works is provided in Appendix A.

This Work: General Certificates of Poisoning Robustness.
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, ). 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 by Tian et al. (), we view the objective of each poisoning attack as an optimization problem. We consider three objectives: (i) untargeted attacks: reducing model test performance to cause denial-of-service, (ii) targeted attacks: compromising model performance 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 provide a general framework for poisoning attacks, describing how our formulation captures the settings studied in prior works (related works are reviewed in Appendix A). 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., ) on the weight gradients. We conclude with extensive ablation experiments on datasets from household energy consumption, medical image classification, and autonomous vehicle driving.

In summary, this paper makes the following key contributions:

- •
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 Preliminaries: Poisoning Attacks

We denote a machine learning model as a parametric function $f$ with parameters $\theta$, feature space $x\in\mathbb{R}^{n_{\text{in}}}$, and label space $y\in\mathcal{Y}$.
The label space $\mathcal{Y}$ may be discrete (e.g. classification) or continuous (e.g. regression).
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, hyper-parameters, etc.

### 2.1 Poisoning Attack Capabilities

This section defines the capabilities of the poisoning attack adversaries that we seek to certify against.
We consider two distinct threat models: (1) $\ell_{p}$-norm bounded adversaries, which are commonly assumed in backdoor attack models (Saha et al., ; Weber et al., ); (2) unbounded adversaries, which are more general and have the capability to inject arbitrary data into the training set.
In both cases, we consider adversaries able to modify both features and labels simultaneously.

Bounded Attacks. Under a bounded attack setting, we allow an adversary to perturb a subset of the training data in both the feature and label space, where the magnitude of the perturbation is bounded in a given norm.
In feature space, we allow for an adversary to modify at most $n$ datapoints by a distance of up to $\epsilon$ in the $\ell_{p}$-norm.
Similarly, we define the label-space poisoning capability as modifying at most $m$ labels by magnitude at most $\nu$ in an $\ell_{q}$-norm.
Note that label-space poisoning encompasses both classification and (multivariate) regression settings.
Common label-flipping attacks can be considered under this attack model by setting $q=0$.
Formally, given a dataset $\mathcal{D}$ and an adversary $\langle n,\epsilon,p,m,\nu,q\rangle$, the set of potentially poisoned datasets is defined as

$$ $\mathcal{T}^{n,\epsilon,p}_{m,\nu,q}(\mathcal{D}):=\left\{\widetilde{\mathcal{ D}}\ \middle|\begin{array}[]{l}\|\mathcal{D}^{(i)}_{x}-\widetilde{\mathcal{D}} ^{(i)}_{x}\|_{p}\leq\epsilon\ \forall i\in I,\quad\mathcal{D}^{(i^{\prime})}_{ x}=\widetilde{\mathcal{D}}^{(i^{\prime})}_{x}\ \forall i^{\prime}\notin I, \quad\forall I\in\mathcal{S}_{n}\\ \|\mathcal{D}^{(j)}_{y}-\widetilde{\mathcal{D}}^{(j)}_{y}\|_{q}\leq\nu\ \forall j\in J,\quad\mathcal{D}^{(j^{\prime})}_{y}=\widetilde{\mathcal{D}}^{(j ^{\prime})}_{y}\ \forall j^{\prime}\notin J,\quad\forall J\in\mathcal{S}_{m} \end{array}\right\}$ (1) $$

where $\mathcal{S}_{n}$ is the set of all subsets of integers less than $N$ with cardinality at most $n$.
The index sets $I$ and $J$ refer to the data-points that have been poisoned in the feature and label spaces, respectively.
Note that in a paired modification setting, adversaries must choose a set of inputs and modify both their features and labels, which corresponds to setting $I=J$ in the above.
Our more general setting allows for adversaries to modify features and labels of different inputs.

Unbounded Attacks. It may not always be realistic to assume that the effect of a poisoning adversary is bounded.
A more powerful adversary may be able to inject arbitrary data points into the training data set, for example by exploiting the collection of user data.
In this unbounded attack setting, we consider only a ‘paired’ modification setting, where an adversary can substitute both the features and labels of any $n$ data-points.
Specifically, for a dataset $\mathcal{D}$, the set of potentially poisoned datasets is

$$ $\mathcal{T}^{n}(\mathcal{D}):=\left\{\widetilde{\mathcal{D}}=(\mathcal{D} \setminus\mathcal{D}^{r})\cup\mathcal{D}^{a}\ \mid\ |\mathcal{D}^{a}|\leq n,| \mathcal{D}^{r}|\leq n,\mathcal{D}^{a}\subset\mathcal{D}\right\}$ (2) $$

where $|\cdot|$ is the cardinality operator, $\mathcal{D}^{a}$ is a set of arbitrary added data-points, and $\mathcal{D}^{r}$ is the set of corresponding data-points removed from the original dataset.
To simplify the exposition below, we interchangeably refer to $\mathcal{T}^{n}$ as either the poisoning adversary or the set of poisoned datasets.
We use $\mathcal{T}$ to refer to cases where either the bounded or unbounded adversaries may be applied.

### 2.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 attacks aim to prevent training convergence, leading to an unusable model and denial of service (Tian et al., ).
Given a test dataset of $k$ examples, the adversary’s objective is thus:

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

We can certify robustness to this kind of attack using a sound upper bound on the solution of (3).

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.
The adversary’s objective is thus:

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

As before, a sound upper bound on (4) 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. ().
This setting also covers ‘unlearnable examples’, such as the attacks considered by Huang et al. ().

Backdoor Poisoning. Backdoor attacks deviate from the above attacks by assuming that test-time data can be altered, via a so-called trigger manipulation.
However, backdoor attacks typically aim to leave the model performance on ‘clean’ data unchanged.
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\mathcal{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{)}$ (5) $$

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

## 3 Methodology

This section develops a novel approach for certifying robustness to poisoning attacks starting by assuming we have access to the set of all reachable trained models in the form of intervals over model parameters. We first show how these intervals can be used to certify robustness to the above attacks.
We then formulate a general algorithm for bounding the effect of adversaries on model parameters, producing an interval containing all reachable training parameters.
We then instantiate it using a novel formulation of CROWN-style bounds which can soundly compute the quantities required within.

### 3.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 $\mathcal{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}\leq\theta^{U}_{i}$ is a valid parameter-space bound on a poisoning adversary, $\mathcal{T}(\mathcal{D})$, if $\forall i$:

$$ $\theta^{L}_{i}\leq\min_{\mathcal{D}^{\prime}\in\mathcal{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\mathcal{T}(\mathcal{D})}M(f,\theta^{ \prime},\mathcal{D}^{\prime})_{i}\leq\theta^{U}_{i}$ (6) $$

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

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

$$ $\max_{\mathcal{D}^{\prime}\in\mathcal{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 (3)–(5).
Full expressions are provided in Appendix G.1.

The advantage of Theorem 3.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., ; Wicker et al., , ).

###### Definition 1 .

###### Theorem 3.1 .

### 3.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$ $\displaystyle\leftarrow\theta-\alpha\dfrac{1}{|\mathcal{B}|}\sum_{(x,y)\in \mathcal{B}}\nabla_{\theta}\mathcal{L}\big{(}f^{\theta}(x),y\big{)}$ (7) $$

where $\mathcal{B}\subseteq\mathcal{D}$ is the sampled batch at the current iteration.
The function $M(f,\theta^{\prime},\mathcal{D})$, in the simplest case, iteratively applies the update (7) 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 (7).
In Algorithm 1, we present a general framework for computing parameter-space bounds on the output of SGD given a poisoning adversary $\mathcal{T}$.
In particular, we highlight that Algorithm 1 first computes the standard stochastic gradient descent update (lines 4-5), and then computes a bound on the set of all possible descent directions that could be taken at this iteration.
Note that the gradient clipping operation, highlighted in purple, is optional for a bounded adversary, and is only required for the unbounded adversary to limit the maximum contribution of any added data-points.
This bound on the descent direction is then soundly combined with the existing parameter space bound to obtain an updated reachable parameter interval $[\theta^{L},\theta^{U}]$.
Since the reachable parameter interval is maintained over every iteration of the algorithm, we have the following theorem (which we prove in Appendix I):

###### Theorem 3.2 .

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

Figure: Algorithm 1 Abstract Gradient Training for Poisoning Certification

Bounding the Descent Direction.
The main complexity in Algorithm 1 is in bounding the set $\Delta\Theta$, which is the set of all possible descent directions at the given iteration under $\mathcal{T}$.
In particular, $\widetilde{\mathcal{B}}\in\mathcal{T}\left(\mathcal{B}\right)$ represents the effect of the adversary’s perturbations on the current batch, while the reachable parameter interval $\theta^{\prime}\in\left[\theta^{L},\theta^{U}\right]$ represents the worst-case effect of adversarial manipulations to all previously seen batches.
Exactly computing the set $\Delta\Theta$ is not computationally tractable, so we instead seek over-approximate element-wise bounds that can be computed efficiently within the training loop.
We present a procedure for computing bounds for the bounded poisoning adversary in the following theorem.
The analogous theorem for the unbounded adversary can be found in Appendix B.

###### Theorem 3.3 (Bounding the descent direction for a bounded adversary) .

Given a nominal batch $\mathcal{B}=\left\{\left({x}^{(i)},{y}^{(i)}\right)\right\}_{i=1}^{b}$ of size $b$, a parameter set $\left[\theta^{L},\theta^{U}\right]$, and a bounded adversary $\langle n,\epsilon,p,m,\nu,q\rangle$,
the SGD parameter update
$\Delta\theta=\frac{1}{b}\sum\limits_{\widetilde{\mathcal{B}}}\nabla_{\theta}
\mathcal{L}\left(f^{\theta}\left(\tilde{x}^{(i)}\right),\tilde{y}^{(i)}\right)$
is bounded element-wise by

$$ $\displaystyle\Delta\theta^{L}=\frac{1}{b}\left(\underset{\max(m,n)}{ \operatorname{SEMin}}\left\{\tilde{\delta}^{(i)}_{L}-{{\delta}^{(i)}_{L}} \right\}_{i=1}^{b}+\sum\limits_{i=1}^{b}{{\delta}^{(i)}_{L}}\right),\quad \Delta\theta^{U}=\frac{1}{b}\left(\underset{\max(m,n)}{\operatorname{SEMax}} \left\{\tilde{\delta}^{(i)}_{U}-{{\delta}^{(i)}_{U}}\right\}_{i=1}^{b}+\sum \limits_{i=1}^{b}{{\delta}^{(i)}_{U}}\right)$ $$

for any $\widetilde{\mathcal{B}}\in T^{n,\epsilon,p}_{m,\nu,q}(\mathcal{B})$ and $\theta\in[\theta^{L},\theta^{U}]$.
The terms ${\delta}^{(i)}_{L},{\delta}^{(i)}_{U}$ are sound bounds that account for the effect of previous adversarial manipulations.
Likewise, the terms $\tilde{\delta}^{(i)}_{L},\tilde{\delta}^{(i)}_{U}$ are bounds on the worst-case adversarial manipulations of the $i$-th data-point in the current batch, i.e.

$$ $\displaystyle{\delta}^{(i)}_{L}\preceq{\delta}\preceq{\delta}^{(i)}_{U}\quad\forall$ $\displaystyle{\delta}\in\left\{\nabla_{\theta^{\prime}}\mathcal{L}\left(f^{ \theta^{\prime}}(x^{(i)}),y^{(i)}\right)\mid\theta^{\prime}\in[\theta^{L}, \theta^{U}]\right\},$ (8) $\displaystyle\tilde{\delta}^{(i)}_{L}\preceq\tilde{\delta}\preceq\tilde{\delta }^{(i)}_{U}\quad\forall$ $\displaystyle\tilde{\delta}\in\left\{\nabla_{\theta^{\prime}}\mathcal{L}\left( f^{\theta^{\prime}}\left(\tilde{x}\right),\tilde{y}\right)\mid\theta^{\prime} \in[\theta^{L},\theta^{U}],\|x^{(i)}-\tilde{x}\|_{p}\leq\epsilon,\|y^{(i)}- \tilde{y}\|_{q}\leq\nu\right\}.$ (9) $$

The operations $\operatorname{SEMax}_{a}$ and $\operatorname{SEMin}_{a}$ correspond to taking the sum of the element-wise top/bottom-$a$ elements over each index of the input vectors.
The update rule in Theorem 3.3 accounts for the effect of poisoning in previous batches by taking the lower and upper bounds on the gradient ($\delta_{L}^{(i)},\delta_{U}^{(i)}$) for all $\theta$ reachable at the current iteration.
Then, we bound the effect of adversarial manipulation in the current batch by taking the $\max(n,m)$ points that have the worst-case gradient bounds $\tilde{\delta}_{L}^{(i)},\tilde{\delta}_{U}^{(i)}$ under poisoning.
Since we wish to soundly over-approximate this operation for all parameters, we perform this bounding operation independently over each index of the parameter vector.
This is certainly a loose approximation, as the $\max(n,m)$ points that maximize the gradient at a particular index will likely not maximize the gradient of other indices.
However, this relaxation allows us to efficiently compute and propagate interval enclosures between successive iterations of AGT.
A further relaxation is taken when computing gradient bounds $\delta^{(i)}_{L},\delta^{(i)}_{U}$, since they are computed independently for each sample $i$ and the min/max for different samples may be attained for different $\theta^{\prime}\in\left[\theta^{L},\theta^{U}\right]$.
Performing this computation independently for each $i$, however, allows for efficient bound-propagation that we describe in more detail in subsequent sections.

For the bounded adversary, gradient clipping is not a requirement and we can directly bound the un-modified SGD training procedure.
However, it can still be desirable to add gradient clipping even in the bounded adversary case, as it can improve the tightness of our descent direction bounds and subsequently improve the guarantees afforded by AGT with little cost to training performance.

###### Theorem 3.2 .

###### Theorem 3.3 (Bounding the descent direction for a bounded adversary) .

### 3.3 Computation of Sound Gradient Bounds

This section presents a novel algorithm for computing bounds on the following optimization problem

$$ $\displaystyle\min\limits_{x^{\star},y^{\star},\theta^{\star}}\left\{\nabla_{ \theta^{\prime}}\mathcal{L}\left(f^{\theta^{\prime}}\left(\tilde{x}\right), \tilde{y}\right)\mid\theta^{\prime}\in[\theta^{L},\theta^{U}],\|x^{(i)}-\tilde {x}\|_{p}\leq\epsilon,\|y^{(i)}-\tilde{y}\|_{q}\leq\nu\right\}.$ (10) $$

Computing the exact solution to this problem is, in general, a non-convex and NP-hard optimization problem.
However, we require only over-approximate solutions; while these can introduce (significant) over-approximation of the reachable parameter set, they will always maintain soundness.
Future work could investigate exact solutions, e.g., via mixed-integer programming (Huchette et al., ; Tsay et al., ).
Owing to their tractability, our discussion focuses on the novel linear bound propagation techniques we develop for abstract gradient training.
Noting that problems of the form (8) can be recovered by setting $\nu=\epsilon=0$, we focus solely on this more general case in this section.

Neural networks. While the algorithm presented in Section 3.2 is general to any machine learning model trained via stochastic gradient descent, we focus our discussion on neural network models for the remained of the paper.
We first define a neural network model $f^{\theta}:\mathbb{R}^{n_{\text{in}}}\rightarrow\mathbb{R}^{n_{\text{out}}}$ 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.

Solving problems of the form $\min\left\{\cdot\mid{\|x-{x}^{\star}\|_{p}\leq\epsilon}\right\}$ for neural networks has been well-studied in the context of adversarial robustness certification.
However, optimizing over inputs, labels and parameters, e.g.,
$\min\left\{\cdot\mid\theta^{\star}\in[\theta^{L},\theta^{U}],\|x-{x}^{\star}\|
_{p}\leq\epsilon,\|y-{y}^{\star}\|_{q}\leq\nu\right\}$
is much less well-studied, and to-date similar problems have appeared primarily in the certification of probabilistic neural networks (Wicker et al., ).

Interval Arithmetic.
For ease of exposition, we will represent interval matrices with bold symbols i.e., $\boldsymbol{A}:=\left[{A_{L}},{A_{U}}\;\right]\subset\mathbb{R}^{n_{1}\times n
_{2}}$ and interval matrix multiplication 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}$ (where $\circ$ is the element-wise product) 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[{a}_{L},{a}_{U}\right]$ with analogous operations.
More details of interval arithmetic operations over matrices and vectors can be found in Appendix C.

Forward Pass Bounds Mirroring developments in robustness certification of neural networks, we provide a novel, explicit extension of the CROWN algorithm (Zhang et al., ) 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., ).
In the interest of space, we present only the upper bound of our extended CROWN algorithm here, with the full version presented in Appendix D.

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

Given an $m$-layer neural network function $f:\mathbb{R}^{n_{\text{in}}}\rightarrow\mathbb{R}^{n_{\text{out}}}$ 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 an explicit function

$$ $\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)$ (11) $$

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

$$ $\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\}$ (12) $$

where $\boldsymbol{x}$ is a closed input domain and ${\Lambda}^{(0:m)},{\Delta}^{(1:m)}$ are the equivalent weights and biases of the linear upper bounds, respectively.
The bias term ${\Delta}^{(1:m)}$ is explicitly computed based on the linear bounds on the activation functions.
The weight ${\Lambda}^{(0:m)}$ lies in an interval $\mathbf{\Lambda}^{(0:m)}$ which is computed in an analogous way to standard, non-interval CROWN (see Appendix D for further details).

Given the upper bound function
$f_{j}^{U}(\cdot)$ defined above and intervals over all the relevant variables, we can compute the following closed-form global upper bound:

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

where $\max$ is performed element-wise and returns the upper bound of the interval enclosure.
Then, we have $f_{j}({x})\leq\gamma^{U}_{j}$ for all ${x}\in\boldsymbol{x}$, ${b}^{(k)}\in\boldsymbol{b}^{{(k)}}$ and ${W}^{(k)}\in{\boldsymbol{W}}^{{(k)}}$.
The equivalent procedure for computing the global lower bound $f_{j}({x})\geq\gamma^{L}_{j}$ can be found in Appendix D.

Backward Pass Bounds. Given bounds on the forward pass of the neural network, we can bound the backward pass (the gradients) of the model. We do this by extending the interval arithmetic based approach of Wicker et al. () (which bounds derivatives of the form ${\partial\mathcal{L}}/{\partial z^{(k)}}$) to additionally bound the derivatives w.r.t. the parameters.
Details of this computation can be found in Appendix F.

Figure: Figure 1: Bounds on a classification threshold trained on the halfmoons dataset for a bounded adversary that can perturb up to $n$ data-points by up to $\epsilon$ in the $p=\infty$ norm; in label space, the adversary may flip up to $m$ labels (corresponding to $\gamma=1,q=0$). The white line shows the decision boundary of the nominal classification model. The coloured regions show the areas for which we cannot certify robustness for the given adversary strength.
Refer to caption: x1.png

###### Proposition 1 (Explicit upper bounds of neural network f 𝑓 f italic_f with interval parameters) .

### 3.4 Algorithm Analysis and Discussion

Figure 1 visualizes the resulting worst-case decision boundaries for a simple binary classifier consisting of a neural network with a hidden layer of 128 neurons.
In this classification setting, label poisoning results in looser bounds than feature space poisoning, with $m=5$ 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.
We also emphasise that Algorithm 1 assumes at most $m,n$ poisoned points per batch, rather than per dataset.
In regression settings, label poisoning is relatively weaker than feature poisoning for a given strength $\epsilon=\nu$, 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., ; Sosnin & Tsay, ).

Comparison to Interval Bound Propagation.
The CROWN algorithm in § 3.3 is not strictly tighter than interval bound propagation (IBP).
Specifically, the non-associativity of double-interval matrix multiplication leads to significantly different interval sizes 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 and Backward Pass 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., ).
As a result, we found that the tightest bounds were obtained using IBP/CROWN on the forward pass and IBP on the backward pass.

Computational Complexity.
The computational complexity of Algorithm 1 depends on the method used to bound on the gradients.
In the simplest case, IBP can be used to compute bounds on the gradients in 4$\times$ the cost of a standard forward and backward pass (see Appendix C).
Likewise, our CROWN bounds admit a cost of at most 4 times the cost of the original CROWN algorithm.
For an $m$ layer network with $n$ neurons per layer and $n$ outputs, the time complexity of the original CROWN algorithm is $\mathcal{O}(m^{2}n^{3})$ (Zhang et al., ).
We further note that the $\operatorname{SEMin}/\operatorname{SEMax}$ operations required by Theorems B.1 and 3.3 can be computed in $\mathcal{O}(b)$ for each index and in practice can be efficiently parallelized using GPU-based implementations.
In summary, Abstract Gradient Training using IBP has time complexity equivalent to standard neural network training ($\mathcal{O}(bmn^{2})$ for each batch of size $b$), but with our tighter, CROWN-based, bounds the complexity is $\mathcal{O}(bm^{2}n^{3})$ per batch.

Limitations. While Algorithm 1 is able to obtain valid-parameter space bounds for any gradient-based training algorithm, the tightness of these bounds depends on the exact architecture, hyperparameters and training procedure used.
In particular, bound-propagation between successive iterations of the algorithm assumes the worst-case poisoning at each parameter index, which may not be achievable by realistic poisoning attacks.
Therefore, obtaining non-vacuous guarantees with our algorithm often requires training with larger batch-sizes and/or for fewer epochs than is typical.
Additionally, certain loss functions, such as multi-class cross entropy, have particularly loose interval relaxations.
Therefore, AGT obtains relatively weaker guarantees for multi-class problems when compared to regression or binary classification settings.
We hope that tighter bound-propagation approaches, such as those based on more expressive abstract domains, may overcome this limitation in future works.

Computing Certificates of Poisoning Robustness. Algorithm 1 returns valid parameter-space bounds $[\theta_{L},\theta_{U}]$ for a given poisoning adversary.
To provide certificates of poisoning robustness for a specific query at a point $x$, we first bound the model output $f^{\theta}(x)\forall\theta\in[\theta_{L},\theta_{U}]$ using the bound-propagation procedure described above.
In classification settings, the robustness of the prediction can then be certified by checking if the lower bound on the output logit for the target class is greater than the upper bounds of all other classes (i.e. $[f_{j}^{\theta}(x)]_{L}\geq[f_{i}^{\theta}(x)]_{U}\forall i\neq j$).
If this condition is satisfied, then the model always predicts class $j$ at the point $x$ for all parameters within our parameter-space bounds, and thus this prediction is certifiably robust to poisoning.
Details on computing bounds on other poisoning adversary objectives (3), (4), and (5) can be found in Appendix G.

## 4 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.
To investigate the tightness of AGT, we also compare our bounds with heuristic poisoning attacks in Appendix H.
The experimental set-up and datasets are described in Appendix J.
Code repository to reproduce our experiments can be found at: [https://github.com/psosnin/AbstractGradientTraining](https://github.com/psosnin/AbstractGradientTraining).

Figure: Figure 2: Mean squared error bounds on the UCI-houseelectric dataset. Top: Effect of adversary strength on certified bounds for a fixed model. Bottom: Effect of model/training hyperparameters on certified bounds for a fixed feature poisoning adversary $(n=100,\epsilon=0.01,p=\infty)$. Hyperparameters $d=1,w=50,b=10000$, and $\alpha=0.02$ where not stated.
Refer to caption: x2.png

UCI Regression (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, ) with fully connected neural networks and MSE as loss function.
Figure 2 (top) 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 $\nu$ results in looser performance bounds.
We note that the settings of $m=10000$ and $n=10000$ correspond $100\%$ of the data (batchsize $b=10000$) being poisoned.

Figure 2 (bottom) 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’.
Increasing the learning rate accelerates both the model training and the deterioration of the bounds.

Figure: Figure 3: Certified accuracy on the MNIST dataset under a label-flipping attack.
Refer to caption: x4.png

MNIST Digit Recognition.
We consider a label-flipping attack ($q=0,\nu=1$) on the MNIST dataset.
In label-only poisoning settings, it is common to use unsupervised learning approaches on the (assumed clean) features prior to training a classification model (e.g. SS-DPA (Levine & Feizi, )).
Therefore, we first project the data into a 32-dimensional feature space using PCA and then train a linear classifier using AGT to obtain a certified classification model.
Figure 3 illustrates the certifiable accuracy using this methodology.
Compared to regression or binary classification settings, AGT provides limited guarantees for multi-class problems; we hope that tighter bound propagation techniques will overcome this limitation in the future.
Stronger guarantees can be obtained by increasing the gradient clipping parameter $\kappa$, at the cost of decreased model utility.

Figure: Figure 4: Certified accuracy (left) and backdoor accuracy (right) for a binary classifier fine-tuned on the Drusen class of OCTMNIST for an attack size up to 10% poisoned data per batch ($b=6000,p=\infty,q=0,\nu=1$). Dashed lines show the nominal accuracy of each fine-tuned model.
Refer to caption: x5.png

MedMNIST Image Classification.
Next, we consider fine-tuning a classifier trained on the retinal OCT dataset (OCTMNIST) (Yang et al., ), 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. (), 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 rarest class (Drusen) using the robust training procedure from Wicker et al. (), 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 50% Drusen samples ($b=6000$ with 3000 Drusen) per batch.

In general, this fine-tuning step improves accuracy on the new class (Drusen) from approximately 0.5 to over 0.8. Nevertheless, Figure 4 shows 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 500$ samples produces bounds worse than the prediction accuracy of the original pre-trained model.
With an unbounded label and feature poisoning adversary, the bounds are weaker, as expected.
Higher certified accuracy can be obtained by increasing the clipping parameter $\kappa$, at the cost of nominal model accuracy (Figure 4, center right).
With label-only poisoning, the certificates are relatively stronger, as the training procedure requires approximately $m\geq 600$ poisoned samples for the prediction accuracy bound to reach the original pre-trained model’s accuracy.
The setting of $m=600$ corresponds to $20\%$ of the Drusen data per batch being mis-labeled as healthy.

Finally, we consider a backdoor attack setting where the $\epsilon$ used at training and inference times is the same.
The model is highly susceptible to adversarial perturbations at inference time even without data poisoning, requiring only $\epsilon=0.009$ to reduce the certified backdoor accuracy to $<50\%$.
As the strength of the (bounded) adversary increases, the accuracy that we are able to certify decreases.
We note that tighter verification algorithms
can be applied at inference time to obtain stronger guarantees.

Figure: Figure 5: Left: Fine-tuning PilotNet on unseen data with a bounded label poisoning attack ($q=\infty$). Right: Steering angle prediction bounds after fine-tuning ($m=300,q=\infty,\nu=0.01$).
Refer to caption: x6.png

Fine-Tuning PilotNet.
Finally, we fine-tune a model that predicts steering angles for autonomous driving given an input image (Bojarski et al., ).
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 dataset ([github.com/udacity/self-driving-car/tree/master](github.com/udacity/self-driving-car/tree/master)).
We then fine-tune the dense layers on video 1 (challenging lighting conditions) assuming potential 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 $\nu$.

## 5 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.

## Appendix A Related Works

#### Data Poisoning.

Poisoning attacks have existed for nearly two decades and are a serious security concern (Biggio & Roli, ; Biggio et al., ; Newsome et al., ).
In Muñoz-González et al. () 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. (); Gu et al. (); Han et al. (); Zhu et al. ().
Popular defenses are attack specific, e.g., generating datasets using known attack strategies to classify and reject potentially poisoned inputs (Li et al., ). Alternative strategies apply noise or clipping to mitigate certain attacks (Hong et al., ).

#### 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. () provide such upper-bounds for linear models trained with gradient descent.
Rosenfeld et al. () present a statistical upper-bound on the effectiveness of $\ell_{2}$ perturbations on training labels for linear models using randomized smoothing. Xie et al. () observe that differential privacy, which usually covers addition or removal of data points, can also provide statistical guarantees in some limited poisoning settings.

#### Certified Poisoning Robustness

Relative to inference-time adversarial robustness (also referred to as evasion attacks), less attention has been devoted to provable guarantees against data poisoning adversaries. Existing methods for deterministic certification of robustness to poisoning adversaries involve design of a learning process with careful partitioning and ensembling such that the resulting model has poisoning robustness guarantees (Levine & Feizi, ; Wang et al., ; Rezaei et al., ). We refer to these methods as "aggregation" methods. In contrast, our approach is a method for analysis and certification of standard, unmodified machine learning algorithms. Aggregation approaches have been shown to offer strong guarantees against poisoning adversaries albeit at a substantial computational cost including: storing and training thousands of models on (potentially disjoint) subsets of the dataset and the requirement to evaluate each of the potentially thousands of models for each prediction; additionally, these methods require that one have potentially thousands of times more data than is necessary for training a single classifier. By designing algorithms to be robust to poisoning adversaries aggregation based approaches are able to scale to larger models than are considered in this work (Levine & Feizi, ; Wang et al., ; Rezaei et al., ). Yet, the computational cost of our approach, in the simplest case, is only four times that of standard training and inference and we do not require that one has access to enough data to train multiple well-performing models. Furthermore, our approach enables reasoning about backdoor attacks, where these partitioning approaches cannot. We finally highlight that the method presented in this paper is orthogonal/complementary to the partitioning approach, and thus future works may be able to combine the two effectively.

#### 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., ) and training models for robustness (Gowal et al., ; Müller et al., ). These approaches typically utilize ideas from formal methods (Katz et al., ; Wicker et al., ) or optimization (Botoeva et al., ; Bunel et al., ; Huchette et al., ).
Most related to this work are strategies that consider intervals over both model inputs and parameters (Wicker et al., ), as well as some preliminary work on robust explanations that bound the input gradients of a model Wicker et al. (). Despite these methodological relationships, none of these methods directly apply to the general training setting studied here.

## Appendix B Bounding the Descent Direction for an Unbounded Adversary

###### Theorem B.1 (Bounding the descent direction for an unbounded adversary) .

Given a nominal batch $\mathcal{B}=\left\{\left({x}^{(i)},{y}^{(i)}\right)\right\}_{i=1}^{b}$ with batchsize $b$, a parameter set $\left[\theta^{L},\theta^{U}\right]$, and a clipping level $\kappa$, the clipped SGD parameter update $\Delta\theta=\frac{1}{b}\sum\limits_{\widetilde{\mathcal{B}}}\operatorname{
Clip}_{\kappa}\left[\nabla_{\theta}\mathcal{L}\left(f^{\theta}\left(\tilde{x}^
{(i)}\right),\tilde{y}^{(i)}\right)\right]$
is bounded element-wise by

$$ $\displaystyle\Delta\theta^{L}$ $\displaystyle=\frac{1}{b}\left(\underset{b-n}{\operatorname{SEMin}}\left\{{ \delta^{(i)}_{L}}\right\}_{i=1}^{b}-n\kappa\mathbf{1}_{d}\right),\quad\Delta \theta^{U}=\frac{1}{b}\left(\underset{b-n}{\operatorname{SEMax}}\left\{{\delta ^{(i)}_{U}}\right\}_{i=1}^{b}+n\kappa\mathbf{1}_{d}\right)$ (13) $$

for any poisoned batch $\widetilde{\mathcal{B}}$ derived from $\mathcal{B}$ by substituting up to $n$ data-points with poisoned data and any $\theta\in[\theta^{L},\theta^{U}]$.
The terms $\delta^{(i)}_{L},\delta^{(i)}_{U}$ are sound bounds that account for the worst-case effect of additions/removals in any previous iterations.
That is, they bound the gradient given any parameter $\theta^{\star}\in[\theta^{L},\theta^{U}]$ in the reachable set, i.e. for all $i=1,\dots,b$, we have $\delta^{(i)}_{L}\preceq\delta^{(i)}\preceq\delta^{(i)}_{U}$ for any

$$ $\displaystyle\delta^{(i)}\in\left\{\operatorname{Clip}_{\kappa}\left[\nabla_{ \theta^{\prime}}\mathcal{L}\left(f^{\theta^{\prime}}(x^{(i)}),y^{(i)}\right) \right]\mid\theta^{\prime}\in\left[\theta^{L},\theta^{U}\right]\right\}.$ (14) $$

The operations $\operatorname{SEMax}_{a}$ and $\operatorname{SEMin}_{a}$ correspond to taking the sum of the element-wise top/bottom-$a$ elements over each index of the input vectors.
Therefore, the update step in (13) corresponds to substituting the $n$ elements with the largest / smallest gradients (by taking the sum of only the min / max $b-n$ gradients) with the minimum / maximum possible gradient updates ($-\kappa,\kappa$, respectively, due to the clipping operation).
Since we wish to soundly over-approximate this operation for all parameters, we perform this bounding operation independently over each index of the parameter vector.
This is certainly a loose approximation, as the $n$ points that maximize the gradient at a particular index will likely not maximize the gradient of other indices.
Note that without clipping, the min / max effect of adding arbitrary data points into the training data is unbounded and we cannot compute any guarantees.

###### Theorem B.1 (Bounding the descent direction for an unbounded adversary) .

## Appendix C Interval Matrix Arithmetic

In this appendix, we provide a basic introduction to interval matrix arithmetic, which forms the basic building block of our CROWN-style bounds.
We denote intervals over matrices as $\boldsymbol{A}:=[A_{L},A_{U}]\subseteq\mathbb{R}^{n\times m}$ such that for all $A\in\boldsymbol{A},A_{L}\leq A\leq A_{U}$.

###### Definition 2 (Interval Matrix Arithmetic) .

Let $\boldsymbol{A}=[A_{L},A_{U}]$ and $\boldsymbol{B}=[B_{L},B_{U}]$ be intervals over matrices.
Let $\oplus$, $\otimes$, $\odot$ represent interval matrix addition, matrix multiplication and elementwise multiplication, such that

$$ $\displaystyle A+B\in[\boldsymbol{A}\oplus\boldsymbol{B}]\quad\forall A\in \boldsymbol{A},B\in\boldsymbol{B},$ $\displaystyle A\times B\in[\boldsymbol{A}\otimes\boldsymbol{B}]\quad\forall A \in\boldsymbol{A},B\in\boldsymbol{B},$ $\displaystyle A\circ B\in[\boldsymbol{A}\odot\boldsymbol{B}]\quad\ \forall A \in\boldsymbol{A},B\in\boldsymbol{B}.$ $$

These operations can be computed using standard interval arithmetic techniques in at most 4$\times$ the cost of a standard matrix operation. For example, interval matrix multiplication can be computed using the following procedure.

###### Definition 3 (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, ),

$$ $\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 () showed that the above bounds have a worst-case overestimation factor of 1.5.

Interval arithmetic is commonly applied as a basic verification or adversarial training technique by propagating intervals through the intermediate layers of a neural network (Gowal et al., ).

###### Definition 2 (Interval Matrix Arithmetic) .

###### Definition 3 (Interval Matrix Multiplication) .

## Appendix D CROWN with Interval Parameters

In this section, we present our full extension of the CROWN algorithm (Zhang et al., ) for neural networks with interval parameters.
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., ).
Here, we present an explicit instantiation of the CROWN algorithm for interval parameters:

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

Given an $m$-layer neural network function $f:\mathbb{R}^{n_{\text{in}}}\rightarrow\mathbb{R}^{n_{\text{out}}}$ 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)$ (15) $\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)$ (16) $$

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.

Computing Equivalent Weights and Biases.
Our instantiation of the CROWN algorithm in Proposition 2 relies on the computation of the equivalent bias terms ${\Delta}^{(1:m)},{\Theta}^{(1:m)}$ and interval enclosures over the equivalent 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.
All interval operations are as described in Appendix C.

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

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

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 closed-form global bounds:

$$ $\displaystyle\gamma^{L}_{j}=\min\left\{{\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]\right\}$ $\displaystyle\gamma^{U}_{j}=\max\left\{{\mathbf{\Lambda}}^{(0)}_{{j,:}}\otimes \boldsymbol{x}\oplus\sum_{k=1}^{m}{\boldsymbol{\Lambda}}^{(k)}_{j,:}\otimes \left[{\boldsymbol{b}}^{(k)}\oplus{{\Delta}}^{(k)}_{:,j}\right]\right\}$ $$

where $\min/\max$ are performed element-wise and return the lower / upper bounds of each interval enclosure.
Then, we have $\gamma^{L}_{j}\leq f_{j}({x})\leq\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 output of the neural network as required to further bound the gradient of the network.

###### Proposition 2 (Explicit output bounds of neural network f 𝑓 f italic_f with interval parameters) .

## Appendix E 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 bounding the following optimization problem via interval arithmetic:

$$ $\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\nu}\right\}$ $$

for some loss function $\mathcal{L}$ where $[{{y}^{L}},{{y}^{U}}]$ are bounds on the logits of the model (obtained via the bound-propagation procedure), $y^{t}$ is the true label and $y^{\prime}$ is the poisoned 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}-\nu\right)$ $\displaystyle{\partial{l}^{U}}=2\left(y^{U}-y^{t}+\nu\right)$ $$

The loss itself can be upper-bounded by $l^{U}=\max\{(y^{L}-y^{t})^{2},(y^{U}-y^{t})^{2}\}$ and lower bounded by

$$ $\displaystyle l^{L}=\begin{cases}0&\text{if }y^{t}\in[y^{L},y^{U}]\\ \min\{(y^{L}-y^{t})^{2},(y^{U}-y^{t})^{2}\}&\text{ otherwise}\end{cases}$ (17) $$

#### Cross Entropy Loss

To bound the gradient of 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,\nu=1$), 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.
The cross entropy loss itself is bounded by $l^{L}=-\sum_{i}y^{t}_{i}\log p_{i}^{U},l^{U}=-\sum_{i}y^{t}_{i}\log p_{i}^{L}$.

## Appendix F Backwards Pass Bounds

Given bounds on the forward pass of the neural network, we now turn to bounding the objective of our original problem (10), replacing the forward pass constraints with their bounds computed using our CROWN algorithm,

$$ $\displaystyle\min\&\max\left\{\frac{\partial}{\partial\theta^{\star}}\left( \mathcal{L}\left(\hat{z}^{(K)},y^{\star}\right)\right)\mid\theta^{\star}\in \left[\theta^{L},\theta^{U}\right],\hat{z}^{(k)}\in\left[\hat{z}^{(k)}_{L}, \hat{z}^{(k)}_{U}\right],\|y-{y}^{\star}\|_{q}\leq\nu\right\}.$ (18) $$

We extend the interval arithmetic based approach of Wicker et al. (), which bounds derivatives of the form ${\partial\mathcal{L}}/{\partial z^{(k)}}$, to additionally compute bounds on the derivatives w.r.t. the parameters.
First, we back-propagate intervals over $y^{\star}$ (the label) and $\hat{z}^{(K)}$ (the logits) to compute an interval over $\boldsymbol{{\partial\mathcal{L}}/{\partial\hat{z}^{(K)}}}$, the gradient of the loss w.r.t. the logits of the network.
The procedure for computing this interval is described in Appendix E for a selection of loss functions.
We then use interval bound propagation to back-propagate this interval through the network to compute intervals over all gradients:

$$ $\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({z}^{(k-1)}_{L}\right)^{\top},\left({z}^{(k-1)}_{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 element-wise product.
The resulting intervals are valid bounds the objective of our original problem (10) and its relaxation (18).
That is, the gradients of the network lie within these intervals for all $W^{(k)}\in\boldsymbol{W^{(k)}}$, $b^{(k)}\in\boldsymbol{b^{(k)}}$, $\|x-{x}^{\star}\|_{p}\leq\epsilon$, and $\|y-{y}^{\star}\|_{q}\leq\nu$.

## Appendix G Computing Bounds on Poisoning Objectives

In this section, we first present a proof of Theorem 3.1, and then describe a procedure for computing bounds on each of the poisoning adversary’s objectives.

### G.1 Proof of Theorem 3.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:

$$ $\displaystyle\max_{\mathcal{D}^{\prime}\in\mathcal{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{)}$ (19) $$

For certified prediction poisoning robustness our bound becomes:

$$ $\displaystyle\max_{\mathcal{D}^{\prime}\in\mathcal{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{)}$ (20) $$

And for backdoor attacks our bound becomes:

$$ $\displaystyle\max_{\mathcal{D}^{\prime}\in\mathcal{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{)}$ (21) $\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{)}$ (22) $$

#### 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\mathcal{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 6, 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.
∎

### G.2 Bounding the Objectives

Given any objective $J$ and a test set $\{(x^{(i)},y^{(i)})\}_{i=1}^{k}$, the poisoning adversary’s objective can be relaxed by taking each test sample independently, i.e.

$$ $\displaystyle\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\dfrac{1}{k}\sum_{ i=1}^{k}J\big{(}\theta^{\star},x^{(i)},y^{(i)}\big{)}\leq\dfrac{1}{k}\sum_{i=1 }^{k}\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}J\big{(}\theta^{\star},x^{ (i)},y^{(i)}\big{)}.$ (23) $$

Thus to bound the original poisoning objectives (3), (4), and (5), it suffices to compute bounds on the required quantity for each test sample independently.

Denial of Service. Computing bounds on the optimization problem

$$ $\displaystyle\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\mathcal{L}\big{(} f^{\theta^{\star}}(x^{(i)}),y^{(i)}\big{)}$ (24) $$

for the cross-entropy and mean-squared-error losses is described in Section E.

Certified Prediction and Backdoor Robustness. Computing an bounds on

$$ $\displaystyle\max_{\theta^{\star}\in[\theta^{L},\theta^{U}]}\mathbbm{1}\big{(} f^{\theta^{\star}}(x^{(i)})\notin S\big{)}$ (25) $$

corresponds to checking if $f^{\theta^{\star}}(x^{(i)})$ lies within the safe set $S$ for all $\theta^{\star}\in[\theta^{L},\theta^{U}]$.
As before, we first compute bounds $f^{L},f^{U}$ on $f^{\theta^{\star}}(x^{(i)})$ using our CROWN-based bounds.
Given these bounds and assuming a multi-class classification setting, the predictions not reachable by any model within $[\theta^{L},\theta^{U}]$ are those whose logit upper bounds lie below the logit lower bound of any other class.
That is, the set of possible predictions $S^{\prime}$ is given by

$$ $\displaystyle S^{\prime}=\left\{i\text{ s.t. }\nexists j:f^{U}_{i}\leq f^{L}_{ j}\right\}.$ (26) $$

If $S^{\prime}\subseteq S$, then $\max_{\theta^{\star}}\mathbbm{1}\big{(}f^{\theta^{\star}}(x^{(i)})\notin S\big
{)}=0$.

Backdoor attack robustness is computed in an analagous way, with the only difference being the logit bounds $f^{L},f^{U}$ being computed over all $x\in V(x)$ and $\theta^{\star}\in[\theta^{L},\theta^{U}]$. This case is also computed via our CROWN-based bound propagation.

## Appendix H Comparison with Empirical Attacks

In this section, we compare the tightness of our bounds with simple heuristic poisoning attacks for both the UCI-houseelectric and OCT-MNIST datasets.

### H.1 Visualising Attacks in Parameter Space (UCI-houseelectric)

Figure: Figure 6: Training trajectory for selected parameters under parameter-targeted feature poisoning with an adversary of $\epsilon=0.02,n=2000,p=\infty$. The coloured boxes show the bounds $[\theta_{L},\theta_{U}]$ obtained at each training iteration using AGT.
Refer to caption: x8.png

First, we investigate the tightness of our bounds in parameter space via a feature poisoning attack.
The attack’s objective is to maximize a given
scalar function of the parameters, which we label $f^{\text{targ}}(\theta)$.
We then take the following poisoning procedure at each training iteration:

- 1.
Randomly sample a subset of $n$ samples from the current training batch.
- 2.
For each selected sample $x^{(i)}$, compute a poison $v^{(i)}$ such that $x^{(i)}+v^{(i)}$ maximizes the gradient $\partial f^{\text{targ}}/\partial x$ subject to $\|v^{(i)}\|_{p}\leq\epsilon$.
- 3.
Add the noise to each of the $n$ sampled points to produce the poisoned dataset.

The noise in step 2 is obtained via projected gradient descent (PGD).
To visualise the effect of our attack in parameter space, we plot the trajectory taken by two randomly selected parameters $\theta_{i},\theta_{j}$ from the network.
We then run our poisoning attack on a collection of poisoning objectives $f^{\text{targ}}$, such as $\theta_{i}+\theta_{j},\theta_{i},-\theta_{j}$, etc.
The effect of our poisoning attack is to perturb the training trajectory in the direction to maximize the given objective.

Figure 6 shows the result of this poisoning procedure for a random selection of parameter training trajectories.
We can see that the poisoned trajectories (in black) lie close the clean poisoned trajectory, while our bounds represent an over-approximation of all the possible training trajectories.

### H.2 Feature-Space Collision Attack (UCI-houseelectric)

Figure: Figure 7: Mean squared error on the target point $(x^{\text{target}},y^{\text{target}})$ in the UCI-houseelectric dataset. Black lines show loss trajectories under the randomized feature-collision poisoning attack.
Refer to caption: x9.png

We now consider an unbounded attack setting where the adversary’s goal is to prevent the model from learning a particular training example $(x^{\text{target}},y^{\text{target}})$.
We again consider a simple randomized attack setting, where the adversary first selects a subset of $n$ samples from each training batch.
The adversary then replaces the features of each of the $n$ samples with $x^{\text{target}}$, and assigns each one a randomly generated label.
In this way, the adversary aims to obscure the true target label and prevent the model from learning the pair $(x^{\text{target}},y^{\text{target}})$.

Figure 7 shows the loss of the model on the target point at each training iteration.
To investigate the tightness of our loss lower bound, we also consider the case where the adversary replaces all of the $n$ sampled instances from the batch with the true $(x^{\text{target}},y^{\text{target}})$, thus over-representing the sample within the batch and causing the model to fit the target point faster.
The bounds (in red) are obtained from AGT with an unbounded adversary ($\kappa=0.05$).
We can see that although our bounds are not tight to any of the attacks considered, they remain sound for all the poisoned training trajectories.

### H.3 Randomized Label Flipping Attack (OCT-MNIST)

Figure: Figure 8: Accuracy on the OCT-MNIST dataset under a random label flipping attack on the Drusen class.
Refer to caption: x10.png

Here, we present the results of a label-flipping attack conducted on the OCT-MNIST dataset.
Following the approach described in Section 4, we begin by pre-training a binary classification model to distinguish between two diseased classes and a healthy class. Next, we fine-tune the model’s final dense layers on the ‘Drusen’ class, which we assume to be potentially compromised, using a training set composed of 50% clean data and 50% Drusen data, with 3000 samples from each category in each batch. Given that the Drusen class is a minority, we simulate a scenario where a random subset of the Drusen data is incorrectly labeled as the ‘healthy’ class.
Figure 8 displays the model’s accuracy when trained on the poisoned dataset.
We can see that training on the mis-labelled data results in a significant decrease in model accuracy, though the poisoned accuracy remains within the bounds of certified by AGT.

## Appendix I Algorithm Correctness Proof (Theorem 3.2 )

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

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

$$ $\theta^{L}_{i}\leq\min_{\mathcal{D}^{\prime}\in\mathcal{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\mathcal{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 6–8) produces a new $\theta^{L}$ and $\theta^{U}$ that satisfy Definition 1. First, we observe that lines 4-5 simply compute the normal forward pass, due to the fact that $\theta^{L}=\theta^{U}$. The gradient bounds required by lines 6-8 (from Theorem 3.3) can be 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}< \nu,x^{\prime}\in\|x^{(i)}-x^{\prime}\|_{q}<\epsilon}\nabla_{\theta}\mathcal{L }(f^{\theta}(x^{\prime}),y^{\prime})$ (27) $\displaystyle{\delta}^{(j)}_{U}=\max_{y^{\prime}\in\|y^{(i)}-y^{\prime}\|_{q}< \nu,x^{\prime}\in\|x^{(i)}-x^{\prime}\|_{q}<\epsilon}\nabla_{\theta}\mathcal{L }(f^{\theta}(x^{\prime}),y^{\prime})$ (28) $$

From the soundness of bound propagation for automatic differentiation (see Wicker et al. ()), we have that $\tilde{\delta}^{(j)}_{L}<{\delta}^{(j)}_{L}$ and that $\tilde{\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 $\{\tilde{\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,\nu,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}\tilde{\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).$ (29) $$

A corresponding argument holds for the maximum and thus we have that $\forall\mathcal{D}^{\prime}\in T_{n,\epsilon,p}^{m,\nu,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}\tilde{\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}\tilde{\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}^{(\star)}_{U}} \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}<\nu,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 (29) 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}{\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}\tilde{\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^{(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}{\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}\tilde{\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_{U}}^{(\star)}} \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 J Experimental Set-up and Additional Results

### J.1 Experimental Set-up

This section details the datasets and hyper-parameters used for the experiments detailed in Section 4. 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.

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

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: My main question would be on how this approach compares (in terms of computing the exact influence of a poisoned dataset) to the finer analysis in the references provided above.
soundness: 2
strengths: The paper proposes a framework, with a (claimed to be novel) bound propagation strategy, for computing bounds on the
influence of a poisoning adversary on any model trained with gradient-based methods,  from the above, a series of proofs are suggested to bound the effect of poisoning attacks, finally, empirical evaluation are proposed to illustrate the approach.
summary: This paper attempts to provide provable guarantees on the behaviour of models trained with potentially manipulated data without modifying the model or learning algorithm. The method uses convex relaxations to over-approximate the set of all possible parameter updates for a given poisoning attack, and provide bounds on worst-case behaviour.
weaknesses: While I might have missed the rationale for computing the set of all reachable trained models given how loose such (worst-case) bounds can be, the approach seems to claim novelty while overlooking important previous contributions, in particular, the use of influence functions in robust statistics, and their revival in modern machine learning.

Cook, R. D. Detection of influential observation in linear regression. Technometrics, 19:15–18, 1977.

Cook, R. D. Assessment of local influence. Journal of the Royal Statistical Society. Series B (Methodological), pp. 133–169, 1986.

Cook, R. D. and Weisberg, S. Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics, 22:495–508, 1980.

Cook, R. D. and Weisberg, S. Residuals and influence in regression. New York: Chapman and Hall, 1982.

Koh, P.W. and Liang, P., 2017, July. Understanding black-box predictions via influence functions. In International conference on machine learning (pp. 1885-1894). PMLR.

---

confidence: 4
contribution: 4
initial_rating: 6
presentation: 3
questions: * Shouldn't we use $\mathrm{SEMin}_{m+n}$ in Theorem 3.3, since the $m$ feature vectors and $n$ labels that are perturbed can belong to disjoint sets of samples (see see ll.117-118)?
* Aside from increased computational cost, are there any reasons why you decided to extend CROWN instead of more recent methods like ($\alpha,\beta$)-CROWN, MN-BAB etc.?
soundness: 3
strengths: * This submission proposes a novel solution to an extensively studied problem (susceptibility to training-time attack), which has received renewed attention due to the current excitement around language models.
* The problem is well-motivated via references to prior work on poisoning attacks.
* The method is clearly distinguished from prior aggregation-based approaches.
* The idea of applying iterative reachability analysis to SGD is very natural. It is somewhat surprising that no one has tried this ansatz before, i.e., the work closes a very obvious gap in existing literature.
* Rather than proposing a completely new relaxation approach, the work expands the well-established CROWN method (soundness appears to be good).
* The method is applicable to a very general perturbation model.
* The in-depth discussion of the method and its limitations in Section 3.4 is commendable.
* The work opens various obvious avenues for future work that could be of interest for the wider robust ML community (refining single- and multi-neuron bounds, generalizing beyond feed-forward networks, enforcing consistency of perturbations between gradient steps etc.)
* The manuscript is well-structured, beginning with a high-level approach (Paramaeter-space certification) and a specific instantiation of this approach (Abstract gradient training), before discussing the technical details of its individual components.
summary: This submission considers the problem of providing provable robustness guarantees to training-time adversarial attacks. Specifically, the considered perturbation models admits changes to a constrained number of $n$ feature vectors and $m$ labels, with optional constraints on their norm. The adversary's objective is to perform a succesful targeted or untargeted poisoning attack, or a backdoor attack.  
Unlike prior work, the authors propose to generalize existing convex relaxation based methods for neural network verification to (1) determine a reachable set of model parameters at training time and (2) at inference time determine a reachable set of model outputs given this parameter sets.  
The reachable set of model parameters is iteratively expanded with each gradient step.
Given the perturbation model and bounds from the previous iteration, lower and upper bounds for the gradients are determined via convex relaxation while (1) considering worst-case choices of inputs and parameteers for $max(m,n)$ inputs and (2) worst-case choices of parameters for the remaining inputs.  
The strength of the resultant bounds for different perturbation model parameters are evaluated by training a model from scratch on a simple regression dataset and dimensionality-reduced MNIST, as well as fine-tuning on two other vision datasets.
weaknesses: * I agree with the authors' argument that the approach taken by this method is orthogonal to prior work. Nevertheless, the experiments would be significantly more informative if one were to use prior work as baselines. Instead of demonstrating "the method for verifying robustness does in fact verify robustness for sufficiently small perturbations", one could demonstrate "the verification method fills a useful niche in the certified-accuracy/runtime space for certain dataset / model sizes".
* The authors claim that their procedure was applicable to any first-order optimizer like Adam (see ll.198-199). This claim appears to be incorrect, since it would require a reachability analysis of the optimizer's internal state (moments etc.). Instead, the method appears to be limited to vanilla SGD.
* The submission does not include an implementation. Since the proposed method is rather involved, and implementing verifiers requires significant care, this significantly hinders reproducibility. I would strongly encourage the authors to provide code.
* Even if one were to try and reimplement the method, the description of hyperparameters and other aspects of the experimental setup is hardly sufficient to reproduce any of the results (see Appendix J). I would strongly encourage the authors to upload experiment configurations with their code.
* The discussion of related work is mostly relegated to Appendix A. This is an integral part of the paper and should (maybe with slightly more concise writing) be moved to the main text.

**Minor weaknesses**:
* While the authors provide asymptotic bounds on runtime complexity, they do not specify the wall-clock time needed for veryifing the different models in the experiment section. This would make it easier to gauge the practical feasibility of the proposed method.
* Based on the asymptotic runtime complexity, the use of small-scale models, and fine-tuning instead of training from scratch, the method appears to be hardly scalable to real-world settings -- except for some  special cases. I do, however, not consider this a major weakness, as this work represents a first step in a novel research direction.
* The definition of targeted attacks (Eq. 4) assumes the existence of a single, data-independent set of safe outputs $S$. However, what constitutes a safe output may often be data-dependent (e.g., whether steering left/right is safe depends on whether the ground truth direction is left/right in the PilotNet dataset from Fig. 5). It should be easy to generalize the proposed method to this use case, since one just has to evaluate the model output bounds differently.
* The definition of backdoor attacks (Eq. 5) does not enforce that the model should have high accuracy on unperturbed samples. As such, the guarenteees are likely to be very loose upper bounds on unnoticable backdoor attacks. It would probably be better to solve a constrained optimization problem over the set of reachable model parameters.
* Prior work on parameter-level verification for Bayesian NNs is mentioned, but it is not explained why these methods are not applicable to the considered problem. For instance, Wicker et al. (2020) [1] appear to determine a "safe" set of weights such that only some desired set of outputs is reachable, which is essentially inverse to Theorem 3.1.

---

[1] Wicker et al. Probabilistic Safety for Bayesian Neural Networks. UAI 2020.

---

Overall, I believe that this submission is a meaningful, well-motivated contribution to the field of robust machine learning. It proposes a very natural approach to robustness certification under training-time attacks that closes an obvious gap in existing literature.  
The submission is primarily held back by poor reproducibility and somewhat uninformative experiments, which do not provide any insights about when parameter-space certification is preferable to existing aggregation-based approaches.  
I thus recommend borderline/weak acceptance. Should the authors address either of these weaknesses (e.g. by sharing a link to anonymized code or comparing to some aggregation / randomized smoothing method on MNIST), I will further increase my score (even if the experimental results are negative).

**EDIT**: Following the rebuttal, which addresses both of my primary concerns, **I have decided to increase my score to 8 (accept)**.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Please see the Weakness section above.
soundness: 3
strengths: 1. The paper is well-organized and easy to follow.
2. This paper provides an alternative perspective to certify the model performance through the robustness of model parameters.
3. The topic of AI security and robustness regarding malicious model attacks attracts a signficant amount of attention in recent years.
summary: This paper proposes to certify the robustness of a model trained on possibly poisoned dataset through the robustness of its parameters. Specifically, the model performance is bounded by the worst-case performance over all possible parameters that can be trained over all possible poisoned datasets under a capability constraint on the attacker. The authors therefore propose to certify a parameter-space bounds, and provide a practical algorithm when the model is a fully-connected neural network. The authors demonstrate their certified accuracy through the proposed method on various datasets.
weaknesses: **Major Concerns:**

1. While it is intuitive that the variation of model parameters can serve as a tool to evaluate its robustness, the guarantee it could provide is extremely loose, at least as presented in this work. In particular, the authors consider the worst-case parameter interval against all possible poisoning dataset as in Eq. (6), and relax it further to Eqs. (8) and (9). It is questionable how useful such a valid but loose bound will be. This concern is to some extent confirmed by the experimental results. Examples include (i) in Fig 1, either a small perturbation level or a small number of poisoning data points is considered to avoid meaningless result. In Fig 1(c), flipping only 4 labels causes an almost void certified bound. (ii) in Appendix H, the authors acknowledge that their bound is extremely loose compared to real-world attacks and corresponding model performance. 

2. The practical evaluation of Eq. (6). As acknowledged by the authors in Section 3, obtaining an parameter interval by Algorithm 1 is intractable in general. The authors provide an approach to solve Eq. (10) for fully-connected neural networks only.  It seems too ambitious to derive the reachable parameter interval against all potential attacks. Even if we can somehow approximate it, as mentioned in the first point, this interval may turn out to be vacuous. 

3. Attack goals formulated in Section 2.2. While authors claim the goal of the attacker is to maximize the training loss such as Eqs. (3), (4) and (5), it makes more sense to consider controlling the generalization error or the test loss, because people are generally more interested in the test performance. To this end, the experiments should also report the certified and true performance on test datasets. Moreover, Eq. (5) is more similar to adversarial attacks instead of backdoor poisoning. A backdoor poisoning attack has dual goals of preserving the performance of clean data and ensuring the accuracy of the backdoored data in terms of the target label.

**Minor Concerns:**
1. It is unclear to me what is the close-form solution to Eq. (10) for neural networks in terms of $\epsilon, \nu, n, m$. An algorithm explaining these details will help readers better understand it.

2. Some results are neither proved or properly referred, such as Theorem 3.3 and B.1, and Proposition 1 and 2.

Meta-review: This paper explores the problem of providing provable robustness guarantees to training-time adversarial attacks. The proposed framework certifies robustness against poisoning and backdoor attacks by bounding the set of all reachable parameters, with worst-case guarantees on model performance and attack success rate.

Reviewers were interested in the approach and found the ideas fairly novel. However, there were major concerns that the bounds given by the proposed method were extremely loose and hence may not be meaningful in practice. This point was not resolved through the rebuttals. Also, the experiments were not well grounded in prior research since the authors did not use baseline methods from the literature. While this was partially added during rebuttals, the experiments have yet to be presented with sufficient rigor.

The work is promising, and the authors have worked to improve it during this review process, but the changes required are not quite complete, and are too major to be accepted as is. I am recommending rejection, but want to encourage the authors to resubmit to a comparable conference after taking the reviewer’s feedback into consideration.

Decision: Reject