Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks

Jinyuan Jia |  | Xiaoyu Cao |  | Neil Zhenqiang Gong
---|---|---|---|---
Duke University |  | Duke University |  | Duke University
<EMAIL_ADDRESS>|  |<EMAIL_ADDRESS>|  |<EMAIL_ADDRESS>

###### Abstract

In a _data poisoning attack_ , an attacker modifies, deletes, and/or inserts
some training examples to corrupt the learnt machine learning model.
_Bootstrap Aggregating (bagging)_ is a well-known ensemble learning method,
which trains multiple base models on random subsamples of a training dataset
using a base learning algorithm and uses majority vote to predict labels of
testing examples. We prove the intrinsic certified robustness of bagging
against data poisoning attacks. Specifically, we show that bagging with an
arbitrary base learning algorithm provably predicts the same label for a
testing example when the number of modified, deleted, and/or inserted training
examples is bounded by a threshold. Moreover, we show that our derived
threshold is tight if no assumptions on the base learning algorithm are made.
We evaluate our method on MNIST and CIFAR10. For instance, our method achieves
a certified accuracy of $91.1\%$ on MNIST when arbitrarily modifying,
deleting, and/or inserting 100 training examples. Code is available at:
https://github.com/jjy1994/BaggingCertifyDataPoisoning.

##  1 Introduction

Machine learning models trained on user-provided data are vulnerable to _data
poisoning attacks_ (Nelson et al., 2008, Biggio et al., 2012, Xiao et al.,
2015, Li et al., 2016, Steinhardt et al., 2017, Shafahi et al., 2018), in
which malicious users carefully poison (i.e., modify, delete, and/or insert)
some training examples such that the learnt model is corrupted and makes
predictions for testing examples as an attacker desires. In particular, the
corrupted model predicts incorrect labels for a large fraction of testing
examples indiscriminately (i.e., a large testing error rate) or for some
attacker-chosen testing examples. Unlike adversarial examples (Szegedy et al.,
2014, Carlini and Wagner, 2017), which carefully perturb each testing example
such that a model predicts an incorrect label for the perturbed testing
example, data poisoning attacks corrupt the model such that it predicts
incorrect labels for many clean testing examples. Like adversarial examples,
data poisoning attacks pose severe security threats to machine learning
systems.

To mitigate data poisoning attacks, various defenses (Cretu et al., 2008,
Barreno et al., 2010, Suciu et al., 2018, Tran et al., 2018, Feng et al.,
2014, Jagielski et al., 2018, Ma et al., 2019, Wang et al., 2020, Rosenfeld et
al., 2020) have been proposed in the literature. Most of these defenses (Cretu
et al., 2008, Barreno et al., 2010, Suciu et al., 2018, Tran et al., 2018,
Feng et al., 2014, Jagielski et al., 2018) achieve _empirical_ robustness
against certain data poisoning attacks and are often broken by strong adaptive
attacks. To end the cat-and-mouse game between attackers and defenders,
_certified defenses_ (Ma et al., 2019, Wang et al., 2020, Rosenfeld et al.,
2020) were proposed. We say a learning algorithm is certifiably robust against
data poisoning attacks if it can learn a classifier that provably predicts the
same label for a testing example when the number of poisoned training examples
is bounded. For instance, Ma et al. (2019) showed that a classifier trained
with differential privacy certifies robustness against data poisoning attacks.
Wang et al. (2020) and Rosenfeld et al. (2020) leveraged _randomized
smoothing_ (Cao and Gong, 2017, Cohen et al., 2019), which was originally
designed to certify robustness against adversarial examples, to certify
robustness against data poisoning attacks that modify labels and/or features
of existing training examples.

However, these certified defenses suffer from two major limitations. First,
they are only applicable to limited scenarios, i.e., Ma et al. (2019) is
limited to learning algorithms that can be differentially private, while Wang
et al. (2020) and Rosenfeld et al. (2020) are limited to data poisoning
attacks that only modify existing training examples. Second, their certified
robustness guarantees are loose, meaning that a learning algorithm is
certifiably more robust than their guarantees indicate. We note that
Steinhardt et al. (2017) derives an approximate upper bound of the loss
function for data poisoning attacks. However, their method cannot certify that
the learnt model predicts the same label for a testing example.

We aim to address these limitations in this work. Our approach is based on a
well-known ensemble learning method called _Bootstrap Aggregating (bagging)_
(Breiman, 1996). Given a training dataset, we create a random _subsample_ with
$k$ training examples sampled from the training dataset uniformly at random
with replacement. Moreover, we use a deterministic or randomized base learning
algorithm to learn a base classifier on the subsample. Due to the randomness
in sampling the subsample and the (randomized) base learning algorithm, the
label predicted for a testing example $\mathbf{x}$ by the learnt base
classifier is random. Therefore, we define $p_{j}$ as the probability that the
learnt base classifier predicts label $j$ for $\mathbf{x}$, where
$j=1,2,\cdots,c$. We call $p_{j}$ _label probability_. In bagging, the
_ensemble classifier_ essentially predicts the label with the largest label
probability for $\mathbf{x}$.

Our first major theoretical result is that we prove the ensemble classifier in
bagging predicts the same label for a testing example when the number of
poisoned training examples is no larger than a threshold. We call the
threshold _certified poisoning size_. Our second major theoretical result is
that we prove our derived certified poisoning size is tight (i.e., it is
impossible to derive a certified poisoning size larger than ours) if no
assumptions on the base learning algorithm are made. Note that the certified
poisoning sizes may be different for different testing examples.

Our certified poisoning size for a testing example is the optimal solution to
an optimization problem, which involves the testing example’s largest and
second largest label probabilities predicted by the bagging’s ensemble
classifier. However, it is computationally challenging to compute the exact
largest and second largest label probabilities, as there are an exponential
number of subsamples with $k$ training examples. To address the challenge, we
propose a Monto Carlo algorithm to simultaneously estimate a lower bound of
the largest label probability and an upper bound of the second largest label
probability for multiple testing examples via training $N$ base classifiers on
$N$ random subsamples. Moreover, we design an efficient algorithm to solve the
optimization problem with the estimated largest and second largest label
probabilities to compute certified poisoning size.

We empirically evaluate our method on MNIST and CIFAR10. For instance, our
method can achieve a certified accuracy of $91.1\%$ on MNIST when 100 training
examples are arbitrarily poisoned, where $k=100$ and $N=1,000$. Under the same
attack setting, Ma et al. (2019), Wang et al. (2020), and Rosenfeld et al.
(2020) achieve $0$ certified accuracy on a simpler MNIST 1/7 dataset.
Moreover, we show that training the base classifiers using transfer learning
can significantly improve the certified accuracy.

Our contributions are summarized as follows:

  * •

We derive the first intrinsic certified robustness of bagging against data
poisoning attacks and prove the tightness of our robustness guarantee.

  * •

We develop algorithms to compute the certified poisoning size in practice.

  * •

We evaluate our method on MNIST and CIFAR10.

All our proofs are shown in the Supplemental Material.

##  2 Certified Robustness of Bagging

Assuming we have a training dataset
$\mathcal{D}=\\{(\mathbf{x}_{1},y_{1}),(\mathbf{x}_{2},y_{2}),\cdots,(\mathbf{x}_{n},y_{n})\\}$
with $n$ examples, where $\mathbf{x}_{i}$ and $y_{i}$ are the feature vector
and label of the $i$th training example, respectively. Moreover, we are given
an arbitrary deterministic or randomized base learning algorithm
$\mathcal{A}$, which takes a training dataset $\mathcal{D}$ as input and
outputs a classifier $f$, i.e., $f=\mathcal{A}(\mathcal{D})$. $f(x)$ is the
predicted label for a testing example $\mathbf{x}$. For convenience, we
jointly represent the training and testing processes as
$\mathcal{A}(\mathcal{D},\mathbf{x})$, which is $\mathbf{x}$’s label predicted
by a classifier that is trained using algorithm $\mathcal{A}$ and training
dataset $\mathcal{D}$.

Data poisoning attacks: In a data poisoning attack, an attacker poisons the
training dataset $\mathcal{D}$ such that the learnt classifier makes
predictions for testing examples as the attacker desires. In particular, the
attacker can carefully _modify_ , _delete_ , and/or _insert_ some training
examples in $\mathcal{D}$ such that
$\mathcal{A}(\mathcal{D},\mathbf{x})\neq\mathcal{A}(\mathcal{D}^{\prime},\mathbf{x})$
for many testing examples $\mathbf{x}$ or some attacker-chosen $\mathbf{x}$,
where $\mathcal{D}^{\prime}$ is the poisoned training dataset. We note that
modifying a training example means modifying its feature vector and/or label.
We denote the set of poisoned training datasets with at most $r$ poisoned
training examples as follows:

$\displaystyle{B}(\mathcal{D},r)=\\{\mathcal{D}^{\prime}|\max\\{|\mathcal{D}|,|\mathcal{D}^{\prime}|\\}-|\mathcal{D}\cap\mathcal{D}^{\prime}|\leq
r\\}.$ (1)

Intuitively,
$\max\\{|\mathcal{D}|,|\mathcal{D}^{\prime}|\\}-|\mathcal{D}\cap\mathcal{D}^{\prime}|$
is the minimum number of modified/deleted/inserted training examples that can
change $\mathcal{D}$ to $\mathcal{D}^{\prime}$.

Bootstrap aggregating (Bagging) (Breiman, 1996): Bagging is a well-known
ensemble learning method. Roughly speaking, bagging creates many subsamples of
a training dataset with replacement and trains a base classifier on each
subsample. For a testing example, bagging uses each base classifier to predict
its label and takes majority vote among the predicted labels as the label of
the testing example. Figure 1 shows a toy example to illustrate why bagging
certifies robustness against data poisoning attacks. When the poisoned
training examples are minority in the training dataset, a majority of the
subsamples do not include any poisoned training examples. Therefore, a
majority of the base classifiers and the bagging’s predicted labels for
testing examples are not influenced by the poisoned training examples.

Figure 1: An example to illustrate why bagging is robust against data
poisoning attacks, where ($\mathbf{x}_{5}$,$y_{5}$) is the poisoned training
example. Base classifiers $f_{1}$ and $f_{2}$ are trained using clean training
examples and bagging predicts the correct label for a testing example after
majority vote among the three base classifiers.

Next, we describe a probabilistic view of bagging, which makes it possible to
theoretically analyze its certified robustness against data poisoning attacks.
Specifically, we denote by $g(\mathcal{D})$ a random subsample, which is a
list of $k$ examples that are sampled from $\mathcal{D}$ with replacement
uniformly at random. We use the base learning algorithm $\mathcal{A}$ to learn
a base classifier on $g(\mathcal{D})$. Due to the randomness in sampling the
subsample $g(\mathcal{D})$ and the (randomized) base learning algorithm
$\mathcal{A}$, the label $\mathcal{A}(g(\mathcal{D}),\mathbf{x})$ predicted by
the base classifier learnt on $g(\mathcal{D})$ for $\mathbf{x}$ is random. We
denote by $p_{j}=\text{Pr}(\mathcal{A}(g(\mathcal{D}),\mathbf{x})=j)$ the
probability that the learnt base classifier predicts label $j$ for
$\mathbf{x}$, where $j=1,2,\cdots,c$. We call $p_{j}$ _label probability_. The
_ensemble classifier_ $h$ in bagging essentially predicts the label with the
largest label probability for $\mathbf{x}$, i.e., we have:

$\displaystyle
h(\mathcal{D},\mathbf{x})=\operatorname*{arg\,max}_{j\in\\{1,2,\cdots,c\\}}p_{j},$
(2)

where $h(\mathcal{D},\mathbf{x})$ is the predicted label for $\mathbf{x}$ when
the ensemble classifier $h$ is trained on $\mathcal{D}$.

Certified robustness of bagging: We prove the certified robustness of bagging
against data poisoning attacks. In particular, we show that the ensemble
classifier in bagging predicts the same label for a testing example when the
number of poisoned training examples is no larger than some threshold (called
_certified poisoning size_). Formally, we aim to show
$h(\mathcal{D}^{\prime},\mathbf{x})=h(\mathcal{D},\mathbf{x})$ for
$\forall\mathcal{D}^{\prime}\in{B}(\mathcal{D},r^{*})$, where $r^{*}$ is the
certified poisoning size. For convenience, we define the following two random
variables:

$\displaystyle X=g(\mathcal{D}),Y=g(\mathcal{D}^{\prime}),$ (3)

where $X$ and $Y$ are two random subsamples with $k$ examples sampled from
$\mathcal{D}$ and $\mathcal{D}^{\prime}$ with replacement uniformly at random,
respectively. $p_{j}=\text{Pr}(\mathcal{A}(X,\mathbf{x})=j)$ and
$p_{j}^{\prime}=\text{Pr}(\mathcal{A}(Y,\mathbf{x})=j)$ are the label
probabilities of label $j$ for testing example $\mathbf{x}$ when the training
dataset is $\mathcal{D}$ and its poisoned version $\mathcal{D}^{\prime}$,
respectively. For simplicity, we use $\Omega$ to denote the joint space of $X$
and $Y$, i.e., each element in $\Omega$ is a subsample of $k$ examples sampled
from $\mathcal{D}$ or $\mathcal{D}^{\prime}$ uniformly at random with
replacement.

Suppose the ensemble classifier predicts label $l$ for $\mathbf{x}$ when
trained on the clean training dataset, i.e., $h(\mathcal{D},\mathbf{x})=l$.
Our goal is to find the maximal poisoning size $r$ such that the ensemble
classifier still predicts label $l$ for $\mathbf{x}$ when trained on the
poisoned training dataset with at most $r$ poisoned training examples.
Formally, our goal is to find the maximal poisoning size $r$ such that the
following inequality is satisfied for
$\forall\mathcal{D}^{\prime}\in{B}(\mathcal{D},r)$:

$\displaystyle h(\mathcal{D}^{\prime},\mathbf{x})=l\Longleftrightarrow
p_{l}^{\prime}>\max_{j\neq l}p_{j}^{\prime}.$ (4)

However, it is challenging to compute $p_{l}^{\prime}$ and $\max_{j\neq
l}p_{j}^{\prime}$ due to the complicated base learning algorithm
$\mathcal{A}$. To address the challenge, we aim to derive a lower bound of
$p_{l}^{\prime}$ and an upper bound of $\max_{j\neq l}p_{j}^{\prime}$, where
the lower bound and upper bound are independent from the base learning
algorithm $\mathcal{A}$ and can be easily computed for a given $r$. In
particular, we derive the lower bound and upper bound as the probabilities
that the random variable $Y$ is in certain regions of the space $\Omega$ via
the Neyman-Pearson Lemma (Neyman and Pearson, 1933). Then, we can find the
maximal $r$ such that the lower bound is larger than the upper bound for any
$\mathcal{D}^{\prime}\in B(\mathcal{D},r)$, and such maximal $r$ is our
certified poisoning size $r^{*}$.

Next, we show the high-level idea of our approach to derive the lower and
upper bounds (details are in Supplemental Material). Our key idea is to
construct regions in the space $\Omega$ such that the random variables $X$ and
$Y$ satisfy the conditions of the Neyman-Pearson Lemma (Neyman and Pearson,
1933), which enables us to derive the lower and upper bounds using the
probabilities that $Y$ is in these regions. Next, we discuss how to construct
the regions. Suppose we have a lower bound $\underline{p_{l}}$ of the largest
label probability ${p_{l}}$ and an upper bound $\overline{p}_{s}$ of the
second largest label probability $p_{s}$ when the ensemble classifier is
trained on the clean training dataset. Formally, $\underline{p_{l}}$ and
$\overline{p}_{s}$ satisfy:

$\displaystyle{\small p_{l}\geq\underline{p_{l}}\geq\overline{p}_{s}\geq
p_{s}=\max_{j\neq l}p_{j}.}$ (5)

We use the probability bounds instead of the exact label probabilities
${p_{l}}$ and ${p}_{s}$, because it is challenging to compute them exactly. We
first divide the space $\Omega$ into three regions $\mathcal{B}$,
$\mathcal{C}$, and $\mathcal{E}$, which include subsamples with $k$ examples
sampled from $\mathcal{D}$, $\mathcal{D}^{\prime}$, and
$\mathcal{D}\cap\mathcal{D}^{\prime}$, respectively. Then, we can find a
region $\mathcal{B}^{\prime}\subseteq\mathcal{E}$ such that we have
$\text{Pr}(X\in\mathcal{B}\cup\mathcal{B}^{\prime})=\underline{p_{l}}-\delta_{l}$,
where $\delta_{l}=\underline{p_{l}}-(\lfloor\underline{p_{l}}\cdot
n^{k}\rfloor)/n^{k}$ is a small residual. We have the residual $\delta_{l}$
because $\text{Pr}(X\in\mathcal{B}\cup\mathcal{B}^{\prime})$ is an integer
multiple of $\frac{1}{n^{k}}$. The reason we assume we can find such region
$\mathcal{B}^{\prime}$ is that we aim to derive a sufficient condition.
Similarly, we can find $\mathcal{C}_{s}\subseteq\mathcal{E}$ such that we have
$\text{Pr}(X\in\mathcal{C}_{s})=\overline{p}_{s}+\delta_{s}$, where
$\delta_{s}=(\lceil\overline{p}_{s}\cdot n^{k}\rceil)/n^{k}-\overline{p}_{s}$
is a small residual. Given these regions, we leverage the Neyman-Pearson Lemma
(Neyman and Pearson, 1933) to derive a lower bound of $p_{l}^{\prime}$ and an
upper bound of $\max_{j\neq l}p_{j}^{\prime}$ as follows:

$\displaystyle p_{l}^{\prime}$
$\displaystyle\geq\text{Pr}(Y\in\mathcal{B}\cup\mathcal{B}^{\prime}),$ (6)
$\displaystyle\max_{j\neq l}p_{j}^{\prime}$
$\displaystyle\leq\text{Pr}(Y\in\mathcal{C}\cup\mathcal{C}_{s}),$ (7)

where the lower bound $\text{Pr}(Y\in\mathcal{B}\cup\mathcal{B}^{\prime})$ and
upper bound $\text{Pr}(Y\in\mathcal{C}\cup\mathcal{C}_{s})$ can be easily
computed for a given $r$. Finally, we find the maximal $r$ such that the lower
bound is still larger than the upper bound, which is our certified poisoning
size $r^{*}$. The following Theorem 1 formally summarizes our certified
robustness guarantee of bagging.

######  Theorem 1 (Certified Poisoning Size of Bagging).

Given a training dataset $\mathcal{D}$, a deterministic or randomized base
learning algorithm $\mathcal{A}$, and a testing example $\mathbf{x}$. The
ensemble classifier $h$ in bagging is defined in Equation (2). Suppose $l$ and
$s$ respectively are the labels with the largest and second largest label
probabilities predicted by $h$ for $\mathbf{x}$. Moreover, the probability
bounds $\underline{p_{l}}$ and $\overline{p}_{s}$ satisfy (5). Then, $h$ still
predicts label $l$ for $\mathbf{x}$ when the number of poisoned training
examples is bounded by $r^{*}$, i.e., we have:

$\displaystyle
h(\mathcal{D}^{\prime},\mathbf{x})=l,\forall\mathcal{D}^{\prime}\in{B}(\mathcal{D},r^{*}),$
(8)

where $r^{*}$ is the solution to the following optimization problem:

$\displaystyle r^{*}$ $\displaystyle=\operatorname*{arg\,max}_{r}r$
$\displaystyle\text{s.t.}\max_{n-r\leq n^{\prime}\leq
n+r}(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{\max(n,n^{\prime})-r}{n})^{k}$
$\displaystyle+1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s})<0,$
(9)

where $n=|\mathcal{D}|$, $n^{\prime}=|\mathcal{D}^{\prime}|$,
$\delta_{l}=\underline{p_{l}}-(\lfloor\underline{p_{l}}\cdot
n^{k}\rfloor)/n^{k}$, and $\delta_{s}=(\lceil\overline{p}_{s}\cdot
n^{k}\rceil)/n^{k}-\overline{p}_{s}$.

Given Theorem 1, we have the following corollaries.

######  Corollary 1.

Suppose a data poisoning attack only modifies existing training examples.
Then, we have $n^{\prime}=n$ and the solution to optimization problem (9) is
$r^{*}=\lceil
n\cdot(1-\sqrt[k]{1-\frac{\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s}}{2}})-1\rceil$.

######  Corollary 2.

Suppose a data poisoning attack only deletes existing training examples. Then,
we have $n^{\prime}=n-r$ and $r^{*}=\lceil
n\cdot(1-\sqrt[k]{1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s})})-1\rceil$.

######  Corollary 3.

Suppose a data poisoning attack only inserts new training examples. Then, we
have $n^{\prime}=n+r$ and $r^{*}=\lceil
n\cdot(\sqrt[k]{1+(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s})}-1)-1\rceil$.

The next theorem shows that our derived certified poisoning size is tight.

######  Theorem 2 (Tightness of the Certified Poisoning Size).

Assuming we have $\underline{p_{l}}+\overline{p}_{s}\leq 1$,
$\underline{p_{l}}+(c-1)\cdot\overline{p}_{s}\geq 1$, and
$\delta_{l}=\delta_{s}=0$. Then, for any $r>r^{*}$, there exist a base
learning algorithm $\mathcal{A}^{*}$ consistent with (5) and a poisoned
training dataset $\mathcal{D}^{\prime}$ with $r$ poisoned training examples
such that $h(\mathcal{D}^{\prime},\mathbf{x})\neq l$ or there exist ties.

We have several remarks about our theorems.

Remark 1: Our Theorem 1 is applicable for any base learning algorithm
$\mathcal{A}$, i.e., bagging with any base learning algorithm is provably
robust against data poisoning attacks.

Remark 2: For any lower bound $\underline{p_{l}}$ of the largest label
probability and upper bound $\overline{p}_{s}$ of the second largest label
probability, Theorem 1 derives a certified poisoning size. Moreover, our
certified poisoning size is related to the gap between the two probability
bounds. If we can estimate tighter probability bounds, then the certified
poisoning size may be larger.

Remark 3: Theorem 2 shows that when no assumptions on the base learning
algorithm are made, it is impossible to certify a poisoning size that is
larger than ours.

##  3 Computing the Certified Poisoning Size

Given a base learning algorithm $\mathcal{A}$, a training dataset
$\mathcal{D}$, subsampling size $k$, and $e$ testing examples in
$\mathcal{D}_{e}$, we aim to compute the label ${l}_{i}$ predicted by the
ensemble classifier and the corresponding certified poisoning size
${r}_{i}^{*}$ for each testing example $\mathbf{x}_{i}$. For a testing example
$\mathbf{x}_{i}$, our certified poisoning size relies on a lower bound
$\underline{p_{{l}_{i}}}$ of the largest label probability and an upper bound
$\overline{p}_{{s}_{i}}$ of the second largest label probability. We design a
Monte-Carlo algorithm to estimate the probability bounds for the $e$ testing
examples simultaneously via training $N$ base classifiers. Next, we first
describe estimating the probability bounds. Then, we describe our efficient
algorithm to solve the optimization problem in (9) with the estimated
probability bounds to compute the certified poisoning sizes.

Computing the predicted label and probability bounds for one testing example:
We first discuss estimating the predicted label ${l}_{i}$ and probability
bounds $\underline{p_{{l}_{i}}}$ and $\overline{p}_{{s}_{i}}$ for one testing
example $\mathbf{x}_{i}$. We first randomly sample $N$ subsamples
$\mathcal{L}_{1},\mathcal{L}_{2},\cdots,\mathcal{L}_{N}$ from $\mathcal{D}$
with replacement, each of which has $k$ training examples. Then, we train a
base classifier $f_{o}$ for each subsample $\mathcal{L}_{o}$ using the base
learning algorithm $\mathcal{A}$, where $o=1,2,\cdots,N$. We use the base
classifiers to predict labels for $\mathbf{x}_{i}$, and we denote by $N_{j}$
the frequency of label $j$, i.e., $N_{j}$ is the number of base classifiers
that predict label $j$ for $\mathbf{x}_{i}$. We estimate the label with the
largest frequency as the label $l_{i}$ predicted by the ensemble classifier
$h$ for $\mathbf{x}_{i}$. Moreover, based on the definition of label
probability, the frequency $N_{j}$ of the label $j$ among the $N$ base
classifiers follows a binomial distribution with parameters $N$ and $p_{j}$.
Therefore, given the label frequencies, we can use the Clopper-Pearson
(Clopper and Pearson, 1934) based method called SimuEM (Jia et al., 2020a) to
estimate the following probability bounds simultaneously:

$\displaystyle\underline{p_{l_{i}}}$
$\displaystyle=\text{Beta}(\frac{\alpha}{c};N_{l_{i}},N-N_{l_{i}}+1)$ (10)
$\displaystyle\overline{p}_{j}$
$\displaystyle=\text{Beta}(1-\frac{\alpha}{c};N_{j},N-N_{j}+1),\forall j\neq
l_{i},$ (11)

where $1-\alpha$ is the confidence level and
$\text{Beta}(\beta;\lambda,\theta)$ is the $\beta$th quantile of the Beta
distribution with shape parameters $\lambda$ and $\theta$. One natural method
to estimate $\overline{p}_{s_{i}}$ is that $\overline{p}_{s_{i}}=\max_{j\neq
l_{i}}\overline{p}_{j}$. However, this bound may be loose. For example,
$\underline{p_{l_{i}}}+\overline{p}_{s_{i}}$ may be larger than 1. Therefore,
we estimate $\overline{p}_{s_{i}}$ as $\overline{p}_{s_{i}}=\min(\max_{j\neq
l_{i}}\overline{p}_{j},1-\underline{p_{l_{i}}})$.

Computing the predicted labels and probability bounds for $e$ testing
examples: One way of estimating the predicted labels and probability bounds
for $e$ testing examples is to apply the above process for each testing
example separately. However, such process requires training $N$ base
classifiers for each testing example, which is computationally intractable. To
address the challenge, we propose a method to estimate them for $e$ testing
examples simultaneously via training $N$ base classifiers in total. Our key
idea is to divide the confidence level among the $e$ testing examples such
that we can estimate their predicted labels and probability bounds using the
same $N$ base classifiers with a simultaneous confidence level at least
$1-\alpha$. Specifically, we still use the $N$ base classifiers to predict the
label for each testing example as we described above. Then, we follow the
above process to estimate the probability bounds $\underline{p_{{l}_{i}}}$ and
$\overline{p}_{{s}_{i}}$ for a testing example $\mathbf{x}_{i}$ via replacing
$\alpha$ as $\alpha/e$ in Equation (10) and (11). Based on the _Bonferroni
correction_ , the simultaneous confidence level of estimating the probability
bounds for the $e$ testing examples is at least $1-\alpha$.

Computing the certified poisoning sizes: Given the estimated probability
bounds $\underline{p_{{l}_{i}}}$ and $\overline{p}_{{s}_{i}}$ for a testing
example $\mathbf{x}_{i}$, we solve the optimization problem in (9) to obtain
its certified poisoning size $r_{i}^{*}$. We design an efficient binary search
based method to solve $r_{i}^{*}$. Specifically, we use binary search to find
the largest $r$ such that the constraint in (9) is satisfied. We denote the
left-hand side of the constraint as $\max_{n-r\leq n^{\prime}\leq n+r}L(n)$.
For a given $r$, a naive way to check whether the constraint $\max_{n-r\leq
n^{\prime}\leq n+r}L(n^{\prime})<0$ holds is to check whether
$L(n^{\prime})<0$ holds for each $n^{\prime}$ in the range $[n-r,n+r]$, which
could be inefficient when $r$ is large. To reduce the computation cost, we
derive an analytical form of $n^{\prime}$ at which $L(n^{\prime})$ reaches its
maximum value. Our analytical form enables us to only check whether
$L(n^{\prime})<0$ holds for at most two different $n^{\prime}$ for a given
$r$. The details of deriving the analytical form are shown in Supplemental
Material.

Algorithm 1 Certify

Input: $\mathcal{A}$, $\mathcal{D}$, $k$, $N$, $\mathcal{D}_{e}$, $\alpha$.

Output: Predicted label and certified poisoning size for each testing example.
$f_{1},f_{2},\cdots,f_{N}\leftarrow\textsc{TrainUnderSample}(\mathcal{A},\mathcal{D},k,N)$

for $\mathbf{x}_{i}$ in $\mathcal{D}_{e}$ do

counts$[j]\leftarrow\sum_{o=1}^{N}\mathbb{I}(f_{o}(\mathbf{x}_{i})=j),j\in\\{1,2,\cdots,c\\}$

$l_{i},s_{i}\leftarrow$ top two indices in counts (ties are broken uniformly
at random).

$\underline{p_{l_{i}}},\overline{p}_{s_{i}}\leftarrow\textsc{SimuEM}(\text{counts},\frac{\alpha}{e})$

if $\underline{p_{l_{i}}}>\overline{p}_{s_{i}}$ then

$r_{i}^{*}\leftarrow\textsc{BinarySearch}(\underline{p_{l_{i}}},\overline{p}_{s_{i}},k,|\mathcal{D}|)$

else

$l_{i},r_{i}^{*}\leftarrow\text{ABSTAIN},\text{ABSTAIN}$

end if

end for

return $l_{1},l_{2},\cdots,l_{e}$ and $r_{1}^{*},r_{2}^{*},\cdots,r_{e}^{*}$

Complete certification algorithm: Algorithm 1 shows our certification process
to estimate the predicted labels and certified poisoning sizes for $e$ testing
examples in $\mathcal{D}_{e}$. The function TrainUnderSample randomly samples
$N$ subsamples and trains $N$ base classifiers. The function SimuEM estimates
the probability bounds $\underline{p_{l_{i}}}$ and $\overline{p}_{s_{i}}$ with
confidence level $1-\frac{\alpha}{e}$. The function BinarySearch solves the
optimization problem in (9) using the estimated probability bounds
$\underline{p_{l_{i}}}$ and $\overline{p}_{s_{i}}$ to obtain the certified
poisoning size $r_{i}^{*}$ for testing example $\mathbf{x}_{i}$.

Since the probability bounds are estimated using a Monte Carlo algorithm, they
may be estimated incorrectly, i.e., $\underline{p_{l_{i}}}>p_{l_{i}}$ or
$\overline{p}_{s_{i}}<{p}_{s_{i}}$. When they are estimated incorrectly, our
algorithm Certify may output an incorrect certified poisoning size. However,
the following theorem shows that the probability that Certify returns an
incorrect certified poisoning size for at least one testing example is at most
$\alpha$.

######  Theorem 3.

The probability that Certify returns an incorrect certified poisoning size for
at least one testing example in $\mathcal{D}_{e}$ is at most $\alpha$, i.e.,
we have:

$\displaystyle\text{Pr}(\cap_{\mathbf{x}_{i}\in\mathcal{D}_{e}}((\forall\mathcal{D}^{\prime}\in
B(\mathcal{D},r_{i}^{*}),h(\mathcal{D}^{\prime},\mathbf{x}_{i})=l_{i})|l_{i}\neq\text{ABSTAIN}))\geq
1-\alpha.$ (12)

##  4 Experiments

###  4.1 Experimental Setup

Datasets and classifiers: We use MNIST and CIFAR10 datasets. The base learning
algorithm is neural network, and we use the example convolutional neural
network architecture and ResNet20 (He et al., 2016) in Keras for MNIST and
CIFAR10, respectively. The number of training examples in the two datasets are
$60,000$ and $50,000$, respectively, which are the training datasets that we
aim to certify. Both datasets have 10,000 testing examples, which are the
$\mathcal{D}_{e}$ in our algorithm. When we train a base classifier, we adopt
the example data augmentation in Keras for both datasets.

Evaluation metric: We use _certified accuracy_ as our evaluation metric. In
particular, we define the certified accuracy at $r$ poisoned training examples
of a classifier as the fraction of testing examples whose labels are correctly
predicted by the classifier and whose certified poisoning sizes are at least
$r$. Formally, we have the certified accuracy $CA_{r}$ at $r$ poisoned
training examples as follows:

$\displaystyle
CA_{r}=\frac{\sum_{\mathbf{x}_{i}\in\mathcal{D}_{e}}\mathbb{I}(l_{i}=y_{i})\cdot\mathbb{I}(r_{i}^{*}\geq
r)}{|\mathcal{D}_{e}|},$ (13)

where $y_{i}$ is the ground truth label for testing example $\mathbf{x}_{i}$,
and $l_{i}$ and $r_{i}^{*}$ respectively are the label predicted by the
classifier and the corresponding certified poisoning size for
$\mathbf{x}_{i}$. Intuitively, $CA_{r}$ of a classifier means that, when the
number of poisoned training examples is $r$, the classifier’s testing accuracy
for $\mathcal{D}_{e}$ is at least $CA_{r}$ no matter how the attacker
manipulates the $r$ poisoned training examples. Based on Theorem 3, the
$CA_{r}$ computed using the predicted labels and certified poisoning sizes
outputted by our Certify algorithm has a confidence level $1-\alpha$.

Parameter setting: Our method has three parameters, i.e., $k$, $\alpha$, and
$N$. Unless otherwise mentioned, we adopt the following default settings for
them: $\alpha=0.001$, $N=1,000$, $k=30$ for MNIST, and $k=500$ for CIFAR10. We
will study the impact of each parameter while setting the remaining parameters
to their default values. Note that training the $N$ base classifiers can be
easily parallelized. We performed experiments on a server with 80<EMAIL_ADDRESS>8 GPUs (RTX 6,000), and 385 GB main memory.

((a)) Different attacks

((b)) Impact of $k$

((c)) Impact of $\alpha$

((d)) Impact of $N$

Figure 2: (a) Comparing different data poisoning attacks. (b)-(d) Impact of
$k$, $\alpha$, and $N$ on the certified accuracy of our method. The first row
is the result on MNIST and the second row is the result on CIFAR10.

((a)) Transfer learning

((b)) Comparing certified accuracy

((c)) Comparing running time

Figure 3: (a) Transfer learning improves our certified accuracy on CIFAR10.
Comparing our method with existing methods with respect to (b) certified
accuracy and (c) running time on the MNIST 1/7 dataset.

###  4.2 Experimental Results

Comparing different data poisoning attacks: An attacker can modify, delete,
and/or insert training examples in data poisoning attacks. We compare the
certified accuracy of our method when an attacker only modifies, deletes, or
inserts training examples. Our Corollary 1-3 show the certified poisoning
sizes for such attacks. Figure 2(a) shows the comparison results, where “All”
corresponds to the attacks that can use modification, deletion, and insertion.
Our method achieves the best certified accuracy for attacks that only delete
training examples. This is because deletion simply reduces the size of the
clean training dataset. The curves corresponding to Modification and All
overlap and have the lowest certified accuracy. This is because modifying a
training example is equivalent to deleting an existing training example and
inserting a new one. In the following experiments, we use the All attacks
unless otherwise mentioned.

Impact of $k$, $\alpha$, and $N$: Figure 2 shows the impact of $k$, $\alpha$,
and $N$ on the certified accuracy of our method. As the results show, $k$
controls a tradeoff between accuracy under no poisoning and robustness.
Specifically, when $k$ is larger, our method has a higher accuracy when there
are no data poisoning attacks (i.e., $r=0$) but the certified accuracy drops
more quickly as the number of poisoned training examples increases. The reason
is that a larger $k$ makes it more likely to sample poisoned training examples
when creating the subsamples in bagging. The certified accuracy increases as
$\alpha$ or $N$ increases. The reason is that a larger $\alpha$ or $N$
produces tighter estimated probability bounds, which make the certified
poisoning sizes larger. We also observe that the certified accuracy is
relatively insensitive to $\alpha$.

Transfer learning improves certified accuracy: Our method trains multiple base
classifiers and each base classifier is trained using $k$ training examples.
Improving the accuracy of each base classifier can improve the certified
accuracy. We explore using transfer learning to train more accurate base
classifiers. Specifically, we use the Inception-v3 classifier pretrained on
ImageNet to extract features and we use a public
implementation111https://github.com/alexisbcook/keras_transfer_cifar10 to
train our base classifiers on CIFAR10. Figure 3(a) shows that transfer
learning can significantly increase our certified accuracy, where $k=100$,
$\alpha=0.001$, and $N=1,000$. Note that we assume the pretrained classifier
is not poisoned in this experiment.

Comparing with Ma et al. (2019), Wang et al. (2020), and Rosenfeld et al.
(2020): Since these methods are not scalable because they train $N$
classifiers on the entire training dataset, we perform comparisons on the
MNIST 1/7 dataset that just includes digits 1 and 7. This subset includes
13,007 training examples and 2,163 testing examples. Note that our above
experiments used the entire MNIST dataset.

  * •

Ma et al. (2019). Ma et al. showed that a classifier trained with differential
privacy achieves certified robustness against data poisoning attacks. Suppose
$ACC_{r}$ is the testing accuracy for $\mathcal{D}_{e}$ of a differentially
private classifier trained on a poisoned training dataset with $r$ poisoned
training examples. Based on the Theorem 3 in (Ma et al., 2019), we have the
expected testing accuracy $E(ACC_{r})$ is lower bounded by a certain function
of $E(ACC)$, $r$, and $(\epsilon,\delta)$ (the function can be found in their
Theorem 3), where $E(ACC)$ is the expected testing accuracy of a
differentially private classifier that is trained using the clean training
dataset and $(\epsilon,\delta)$ are the differential privacy parameters. The
randomness in $E(ACC_{r})$ and $E(ACC)$ are from differential privacy. This
lower bound is the certified accuracy that the method achieves. A lower bound
of $E(ACC)$ can be further estimated with confidence level $1-\alpha$ via
training $N$ differentially private classifiers on the entire clean training
dataset. For simplicity, we estimate $E(ACC)$ as the average testing
accuracies of the $N$ differentially private classifiers, which gives
advantages for this method. We use DP-SGD (Abadi et al., 2016) implemented in
TensorFlow to train differentially private classifiers. Moreover, we set
$\epsilon=0.3$ and $\delta=10^{-5}$ such that this method and our method
achieve comparable certified accuracies when $r=0$.

  * •

Wang et al. (2020) and Rosenfeld et al. (2020). Wang et al. proposed a
randomized smoothing based method to certify robustness against backdoor
attacks via randomly flipping features and labels of training examples as well
as features of testing examples. Rosenfeld et al. leveraged randomized
smoothing to certify robustness against label flipping attacks. Both methods
can be generalized to certify robustness against data poisoning attacks that
modify both features and labels of existing training examples via randomly
flipping features and labels of training examples. Moreover, the two methods
become the same after such generalization. Therefore, we only show results for
Wang et al. (2020). In particular, we binarize the features to apply this
method. We train $N$ classifiers to estimate the certified accuracy with a
confidence level $1-\alpha$. Unlike our method, when training a classifier,
they flip each feature/label value in the training dataset with probability
$\beta$ and use the entire noisy training dataset. When predicting the label
of a testing example, this method takes a majority vote among the $N$
classifiers. We set $\beta=0.3$ such that this method and our method achieve
comparable certified accuracies when $r=0$. We note that this method certifies
the number of poisoned features/labels in the training dataset. We transform
this certificate to the number of poisoned training examples as
$\lfloor\frac{F}{d+1}\rfloor$, where $F$ is the certified number of
features/labels and $d+1$ is the number of features/label of a training
example ($d$ features + one label). We have $d=784$ for MNIST.

Figure 3(b) shows the comparison results, where $k=50$, $\alpha=0.001$, and
$N=1,000$. To be consistent with previous work, we did not use data
augmentation when training the base classifiers for all three methods in these
experiments. Our method significantly outperforms existing methods. For
example, our method can achieve $96.95\%$ certified accuracy when the number
of poisoned training examples is $r=50$, while the certified accuracy is $0$
under the same setting for existing methods. Figure 3(c) shows that our method
is also more efficient than existing methods. This is because our method
trains base classifiers on a small number of training examples while existing
methods train classifiers on the entire training dataset. Ma et al.
outperforms Wang et al. and Rosenfeld et al. because differential privacy
directly certifies robustness against modification/deletion/insertion of
training examples while randomized smoothing was designed to certify
robustness against modifications of features/labels.

##  5 Related Work

Data poisoning attacks carefully modify, delete, and/or insert some training
examples in the training dataset such that a learnt model makes incorrect
predictions for many testing examples indiscriminately (i.e., the learnt model
has a large testing error rate) or for some attacker-chosen testing examples.
For instance, data poisoning attacks have been shown to be effective for Bayes
classifiers (Nelson et al., 2008), SVMs (Biggio et al., 2012), neural networks
(Yang et al., 2017a, Muñoz-González et al., 2017, Suciu et al., 2018, Shafahi
et al., 2018), linear regression models (Mei and Zhu, 2015b, Jagielski et al.,
2018), PCA (Rubinstein et al., 2009), LASSO (Xiao et al., 2015), collaborative
filtering (Li et al., 2016, Yang et al., 2017b, Fang et al., 2018, 2020b),
clustering (Biggio et al., 2013, 2014), graph-based methods (Zügner et al.,
2018, Wang and Gong, 2019, Jia et al., 2020b, Zhang et al., 2020), federated
learning (Fang et al., 2020a, Bhagoji et al., 2019, Bagdasaryan et al., 2020),
and others (Mozaffari-Kermani et al., 2014, Mei and Zhu, 2015a, Koh et al.,
2018, Zhu et al., 2019). We note that backdoor attacks (Gu et al., 2017, Liu
et al., 2017) also poison the training dataset. However, unlike data poisoning
attacks, backdoor attacks also inject perturbation (i.e., a trigger) to
testing examples.

One category of defenses (Cretu et al., 2008, Barreno et al., 2010, Suciu et
al., 2018, Tran et al., 2018) aim to detect the poisoned training examples
based on their negative impact on the error rate of the learnt model. Another
category of defenses (Feng et al., 2014, Jagielski et al., 2018) aim to design
new loss functions, solving which detects the poisoned training examples and
learns a model simultaneously. For instance, Jagielski et al. (2018) proposed
to jointly optimize the selection of a subset of training examples with a
given size and a model that minimizes the loss function; and the unselected
training examples are treated as poisoned ones. Steinhardt et al. (2017)
assumes that a model is trained only using examples in a feasible set and
derives an approximate upper bound of the loss function for any data poisoning
attacks under these assumptions. However, all of these defenses cannot certify
that the learnt model predicts the same label for a testing example under data
poisoning attacks.

Ma et al. (2019) shows that differentially private models certify robustness
against data poisoning attacks. Wang et al. (2020) proposes to use randomized
smoothing to certify robustness against backdoor attacks, which is also
applicable to certify robustness against data poisoning attacks. Rosenfeld et
al. (2020) leverages randomized smoothing to certify robustness against label
flipping attacks. However, these defenses achieve loose certified robustness
guarantees. Moreover, Ma et al. (2019) is only applicable to learning
algorithms that can be differentially private, while Wang et al. (2020) and
Rosenfeld et al. (2020) are only applicable to data poisoning attacks that
modify existing training examples. Biggio et al. (2011) proposed bagging as an
empirical defense against data poisoning attacks. However, they did not derive
the certified robustness of bagging. We note that a concurrent work (Levine
and Feizi, 2020) proposed to certify robustness against data poisoning attacks
via partitioning the training dataset using a hash function. However, their
results are only applicable to deterministic learning algorithms.

##  6 Conclusion

Data poisoning attacks pose severe security threats to machine learning
systems. In this work, we show the intrinsic certified robustness of bagging
against data poisoning attacks. Specifically, we show that bagging predicts
the same label for a testing example when the number of poisoned training
examples is bounded. Moreover, we show that our derived bound is tight if no
assumptions on the base learning algorithm are made. We also empirically
demonstrate the effectiveness of our method using MNIST and CIFAR10. Our
results show that our method achieves much better certified robustness and is
more efficient than existing certified defenses. Interesting future work
includes: 1) generalizing our method to other types of data, e.g., graphs, and
2) improving our method by leveraging meta-learning.

##  7  Acknowledgments

We thank the anonymous reviewers for insightful reviews. This work was
supported by NSF grant No. 1937786.

## References

  * Abadi et al. (2016) Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In _CCS_ , 2016.
  * Bagdasaryan et al. (2020) Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov.  How to backdoor federated learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2938–2948, 2020.
  * Barreno et al. (2010) Marco Barreno, Blaine Nelson, Anthony D Joseph, and JD Tygar.  The security of machine learning.  _Machine Learning_ , 2010.
  * Bhagoji et al. (2019) Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo.  Analyzing federated learning through an adversarial lens.  In _International Conference on Machine Learning_ , pages 634–643, 2019.
  * Biggio et al. (2011) Battista Biggio, Igino Corona, Giorgio Fumera, Giorgio Giacinto, and Fabio Roli.  Bagging classifiers for fighting poisoning attacks in adversarial classification tasks.  In _International workshop on multiple classifier systems_ , pages 350–359. Springer, 2011.
  * Biggio et al. (2012) Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning attacks against support vector machines.  In _ICML_ , 2012.
  * Biggio et al. (2013) Battista Biggio, Ignazio Pillai, Samuel Rota Bulò, Davide Ariu, Marcello Pelillo, and Fabio Roli.  Is data clustering in adversarial settings secure?  In _AISec_ , 2013.
  * Biggio et al. (2014) Battista Biggio, Konrad Rieck, Davide Ariu, Christian Wressnegger, Igino Corona, Giorgio Giacinto, and Fabio Roli.  Poisoning behavioral malware clustering.  In _AISec_ , 2014.
  * Breiman (1996) Leo Breiman.  Bagging predictors.  _Machine learning_ , 24(2):123–140, 1996.
  * Cao and Gong (2017) Xiaoyu Cao and Neil Zhenqiang Gong.  Mitigating evasion attacks to deep neural networks via region-based classification.  In _Proceedings of the 33rd Annual Computer Security Applications Conference_ , pages 278–287, 2017.
  * Carlini and Wagner (2017) Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In _2017 ieee symposium on security and privacy (sp)_ , pages 39–57. IEEE, 2017.
  * Clopper and Pearson (1934) Charles J Clopper and Egon S Pearson.  The use of confidence or fiducial limits illustrated in the case of the binomial.  _Biometrika_ , 26(4):404–413, 1934.
  * Cohen et al. (2019) Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter.  Certified adversarial robustness via randomized smoothing.  _arXiv preprint arXiv:1902.02918_ , 2019.
  * Cretu et al. (2008) Gabriela F. Cretu, Angelos Stavrou, Michael E. Locasto, Salvatore J. Stolfo, and Angelos D. Keromytis.  Casting out demons: Sanitizing training data for anomaly sensors.  In _IEEE S & P_, 2008.
  * Fang et al. (2018) Minghong Fang, Guolei Yang, Neil Zhenqiang Gong, and Jia Liu.  Poisoning attacks to graph-based recommender systems.  In _Proceedings of the 34th Annual Computer Security Applications Conference_ , pages 381–392, 2018.
  * Fang et al. (2020a) Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong.  Local model poisoning attacks to byzantine-robust federated learning.  In _Usenix Security Symposium_ , 2020a.
  * Fang et al. (2020b) Minghong Fang, Neil Zhenqiang Gong, and Jia Liu.  Influence function based data poisoning attacks to top-n recommender systems.  In _Proceedings of The Web Conference 2020_ , pages 3019–3025, 2020b.
  * Feng et al. (2014) Jiashi Feng, Huan Xu, Shie Mannor, and Shuicheng Yan.  Robust logistic regression and classification.  In _NIPS_ , 2014.
  * Gu et al. (2017) Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  _arXiv preprint arXiv:1708.06733_ , 2017.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , pages 770–778, 2016.
  * Jagielski et al. (2018) Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li.  Manipulating machine learning: Poisoning attacks and countermeasures for regression learning.  In _IEEE S & P_, 2018.
  * Jia et al. (2020a) Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong.  Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing.  In _International Conference on Learning Representations_ , 2020a.
  * Jia et al. (2020b) Jinyuan Jia, Binghui Wang, Xiaoyu Cao, and Neil Zhenqiang Gong.  Certified robustness of community detection against adversarial structural perturbation via randomized smoothing.  In _Proceedings of The Web Conference 2020_ , pages 2718–2724, 2020b.
  * Koh et al. (2018) Pang Wei Koh, Jacob Steinhardt, and Percy Liang.  Stronger data poisoning attacks break data sanitization defenses.  _arXiv preprint arXiv:1811.00741_ , 2018.
  * Levine and Feizi (2020) Alexander Levine and Soheil Feizi.  Deep partition aggregation: Provable defense against general poisoning attacks.  _arXiv preprint arXiv:2006.14768_ , 2020.
  * Li et al. (2016) Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik.  Data poisoning attacks on factorization-based collaborative filtering.  In _Advances in neural information processing systems_ , pages 1885–1893, 2016.
  * Liu et al. (2017) Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang.  Trojaning attack on neural networks.  In _ISOC Network and Distributed System Security Symposium_ , 2017\.
  * Ma et al. (2019) Yuzhe Ma, Xiaojin Zhu, and Justin Hsu.  Data poisoning against differentially-private learners: Attacks and defenses.  In _International Joint Conference on Artificial Intelligence_ , 2019\.
  * Mei and Zhu (2015a) Shike Mei and Xiaojin Zhu.  The security of latent dirichlet allocation.  In _Artificial Intelligence and Statistics_ , pages 681–689, 2015a.
  * Mei and Zhu (2015b) Shike Mei and Xiaojin Zhu.  Using machine teaching to identify optimal training-set attacks on machine learners.  In _Twenty-Ninth AAAI Conference on Artificial Intelligence_ , 2015b.
  * Mozaffari-Kermani et al. (2014) Mehran Mozaffari-Kermani, Susmita Sur-Kolay, Anand Raghunathan, and Niraj K Jha.  Systematic poisoning attacks on and defenses for machine learning in healthcare.  _IEEE journal of biomedical and health informatics_ , 19(6):1893–1905, 2014.
  * Muñoz-González et al. (2017) Luis Muñoz-González, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli.  Towards poisoning of deep learning algorithms with back-gradient optimization.  In _AISec_ , 2017.
  * Nelson et al. (2008) Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles A Sutton, J Doug Tygar, and Kai Xia.  Exploiting machine learning to subvert your spam filter.  _LEET_ , 8:1–9, 2008.
  * Neyman and Pearson (1933) Jerzy Neyman and Egon Sharpe Pearson.  On the problem of the most efficient tests of statistical hypotheses.  _Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character_ , 231(694-706):289–337, 1933.
  * Rosenfeld et al. (2020) Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J Zico Kolter.  Certified robustness to label-flipping attacks via randomized smoothing.  In _ICML_ , 2020.
  * Rubinstein et al. (2009) Benjamin IP Rubinstein, Blaine Nelson, Ling Huang, Anthony D Joseph, Shing-hon Lau, Satish Rao, Nina Taft, and JD Tygar.  Antidote: understanding and defending against poisoning of anomaly detectors.  In _ACM IMC_ , 2009.
  * Shafahi et al. (2018) Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein.  Poison frogs! targeted clean-label poisoning attacks on neural networks.  In _NIPS_ , 2018.
  * Steinhardt et al. (2017) Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang.  Certified defenses for data poisoning attacks.  In _Advances in neural information processing systems_ , pages 3517–3529, 2017.
  * Suciu et al. (2018) Octavian Suciu, Radu Marginean, Yigitcan Kaya, Hal Daume III, and Tudor Dumitras.  When does machine learning fail? generalized transferability for evasion and poisoning attacks.  In _Usenix Security Symposium_ , 2018.
  * Szegedy et al. (2014) Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  _ICLR_ , 2014.
  * Tran et al. (2018) Brandon Tran, Jerry Li, and Aleksander Madry.  Spectral signatures in backdoor attacks.  In _NIPS_ , 2018.
  * Wang and Gong (2019) Binghui Wang and Neil Zhenqiang Gong.  Attacking graph-based classification via manipulating the graph structure.  In _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , pages 2023–2040, 2019.
  * Wang et al. (2020) Binghui Wang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong.  On certifying robustness against backdoor attacks via randomized smoothing.  In _CVPR 2020 Workshop on Adversarial Machine Learning in Computer Vision_ , 2020.
  * Xiao et al. (2015) Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli.  Is feature selection secure against training data poisoning?  In _ICML_ , 2015.
  * Yang et al. (2017a) Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen.  Generative poisoning attack method against neural networks.  _arXiv preprint arXiv:1703.01340_ , 2017a.
  * Yang et al. (2017b) Guolei Yang, Neil Zhenqiang Gong, and Ying Cai.  Fake co-visitation injection attacks to recommender systems.  In _NDSS_ , 2017b.
  * Zhang et al. (2020) Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong.  Backdoor attacks to graph neural networks.  _arXiv preprint arXiv:2006.11165_ , 2020.
  * Zhu et al. (2019) Chen Zhu, W Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein.  Transferable clean-label poisoning attacks on deep neural nets.  In _International Conference on Machine Learning_ , pages 7614–7623, 2019.
  * Zügner et al. (2018) Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann.  Adversarial attacks on neural networks for graph data.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2847–2856, 2018.

##  Appendix A Proof of Theorem 1

We first define some notations that will be used in our proof. Given a
training dataset $\mathcal{D}$ and its poisoned version
$\mathcal{D}^{\prime}$, we define the following two random variables:

$\displaystyle X=g(\mathcal{D})$ (14) $\displaystyle
Y=g(\mathcal{D}^{\prime}),$ (15)

where $X$ and $Y$ respectively are two random lists with $k$ examples sampled
from $\mathcal{D}$ and $\mathcal{D}^{\prime}$ with replacement uniformly at
random. We denote by $\mathcal{I}=\mathcal{D}\cap\mathcal{D}^{\prime}$ the set
of training examples that are in both $\mathcal{D}$ and
$\mathcal{D}^{\prime}$. We denote $n=|\mathcal{D}|$,
$n^{\prime}=|\mathcal{D}^{\prime}|$, and $m=|\mathcal{I}|$, which are the
number of training examples in $\mathcal{D}$, $\mathcal{D}^{\prime}$, and
$\mathcal{D}\cap\mathcal{D}^{\prime}$, respectively. We use $\Omega$ to denote
the joint space of random variables $X$ and $Y$, i.e., each element in
$\Omega$ is a list with $k$ examples sampled from $\mathcal{D}$ or
$\mathcal{D}^{\prime}$ with replacement uniformly at random. For convenience,
we define operators $\sqsubseteq,\not\sqsubseteq$ as follows:

######  Definition 1 ($\sqsubseteq,\not\sqsubseteq$).

Assuming $\omega\in\Omega$ is a list of $k$ examples and $\mathcal{S}$ is a
set of examples, we say $\omega\sqsubseteq\mathcal{S}$ if $\text{
}\forall\mathbf{w}\in\omega,\mathbf{w}\in\mathcal{S}$. We say
$\omega\not\sqsubseteq\mathcal{S}$ if $\text{
}\exists\mathbf{w}\in\omega,\mathbf{w}\not\in\mathcal{S}$.

For instance, we have $X\sqsubseteq\mathcal{D}$ and
$Y\sqsubseteq\mathcal{D}^{\prime}$. Before proving our theorem, we show a
variant of the Neyman-Pearson Lemma (Neyman and Pearson, 1933) that will be
used in our proof.

######  Lemma 1 (Neyman-Pearson Lemma).

Suppose $X$ and $Y$ are two random variables in the space $\Omega$ with
probability distributions $\mu_{x}$ and $\mu_{y}$, respectively. Let
$M:\Omega\xrightarrow{}\\{0,1\\}$ be a random or deterministic function. Then,
we have the following:

  * •

If $S_{1}=\\{\omega\in\Omega:\mu_{x}(\omega)>t\cdot\mu_{y}(\omega)\\}$ and
$S_{2}=\\{\omega\in\Omega:\mu_{x}(\omega)=t\cdot\mu_{y}(\omega)\\}$ for some
$t>0$. Let $S=S_{1}\cup S_{3}$, where $S_{3}\subseteq S_{2}$. If we have
$\text{Pr}(M(X)=1)\geq\text{Pr}(X\in S)$, then
$\text{Pr}(M(Y)=1)\geq\text{Pr}(Y\in S)$.

  * •

If $S_{1}=\\{\omega\in\Omega:\mu_{x}(\omega)<t\cdot\mu_{y}(\omega)\\}$ and
$S_{2}=\\{\omega\in\Omega:\mu_{x}(\omega)=t\cdot\mu_{y}(\omega)\\}$ for some
$t>0$. Let $S=S_{1}\cup S_{3}$, where $S_{3}\subseteq S_{2}$. If we have
$\text{Pr}(M(X)=1)\leq\text{Pr}(X\in S)$, then
$\text{Pr}(M(Y)=1)\leq\text{Pr}(Y\in S)$.

###### Proof.

We show the proof of the first part, and the second part can be proved
similarly. For simplicity, we use $M(1|\omega)$ and $M(0|\omega)$ to denote
the probabilities that $M(\omega)=0$ and $M(\omega)=1$, respectively. We use
$S^{c}$ to denote the complement of $S$, i.e., $S^{c}=\Omega\setminus S$. We
have the following:

$\displaystyle\text{Pr}(M(Y)=1)-\text{Pr}(Y\in S)$ (16) $\displaystyle=$
$\displaystyle\sum_{\omega\in\Omega}M(1|\omega)\cdot\mu_{y}(\omega)-\sum_{\omega\in
S}\mu_{y}(\omega)$ (17) $\displaystyle=$ $\displaystyle\sum_{\omega\in
S^{c}}M(1|\omega)\cdot\mu_{y}(\omega)+\sum_{\omega\in
S}M(1|\omega)\cdot\mu_{y}(\omega)-\sum_{\omega\in
S}M(1|\omega)\cdot\mu_{y}(\omega)-\sum_{\omega\in
S}M(0|\omega)\cdot\mu_{y}(\omega)$ (18) $\displaystyle=$
$\displaystyle\sum_{\omega\in
S^{c}}M(1|\omega)\cdot\mu_{y}(\omega)-\sum_{\omega\in
S}M(0|\omega)\cdot\mu_{y}(\omega)$ (19) $\displaystyle\geq$
$\displaystyle\frac{1}{t}\cdot(\sum_{\omega\in
S^{c}}M(1|\omega)\cdot\mu_{x}(\omega)-\sum_{\omega\in
S}M(0|\omega)\cdot\mu_{x}(\omega))$ (20) $\displaystyle=$
$\displaystyle\frac{1}{t}\cdot(\sum_{\omega\in
S^{c}}M(1|\omega)\cdot\mu_{x}(\omega)+\sum_{\omega\in
S}M(1|\omega)\cdot\mu_{x}(\omega)-\sum_{\omega\in
S}M(1|\omega)\cdot\mu_{x}(\omega)-\sum_{\omega\in
S}M(0|\omega)\cdot\mu_{x}(\omega))$ (21) $\displaystyle=$
$\displaystyle\frac{1}{t}\cdot(\sum_{\omega\in\Omega}M(1|\omega)\cdot\mu_{x}(\omega)-\sum_{\omega\in
S}\mu_{x}(\omega))$ (22) $\displaystyle=$
$\displaystyle\frac{1}{t}\cdot(\text{Pr}(M(X)=1)-\text{Pr}(X\in S))$ (23)
$\displaystyle\geq$ $\displaystyle 0.$ (24)

We obtain (21) from (19) because $\mu_{x}(\omega)\geq
t\cdot\mu_{y}(\omega),\forall\omega\in S$ and $\mu_{x}(\omega)\leq
t\cdot\mu_{y}(\omega),\forall\omega\in S^{c}$. We have the last inequality
because $\text{Pr}(M(X)=1)\geq\text{Pr}(X\in S)$. ∎

Next, we prove our Theorem 1. Our goal is to show that
$h(\mathcal{D}^{\prime},\mathbf{x})=l$, i.e.,
$\text{Pr}(\mathcal{A}(Y,\mathbf{x})=l)>\max_{j\neq
l}\text{Pr}(\mathcal{A}(Y,\mathbf{x})=j)$. Our key idea is to derive a lower
bound of $\text{Pr}(\mathcal{A}(Y,\mathbf{x})=l)$ and an upper bound of
$\max_{j\neq l}\text{Pr}(\mathcal{A}(Y,\mathbf{x})=j)$, where the lower bound
and upper bound can be easily computed. We derive the lower bound and upper
bound using the Neyman-Pearson Lemma. Then, we derive the certified poisoning
size by requiring the lower bound to be larger than the upper bound. Next, we
derive the lower bound, the upper bound, and the certified poisoning size.

Deriving a lower bound of $\text{Pr}(\mathcal{A}(Y,\mathbf{x})=l)$: We first
define the following residual:

$\displaystyle\delta_{l}=\underline{p_{l}}-(\lfloor\underline{p_{l}}\cdot
n^{k}\rfloor)/n^{k}.$ (25)

We define a binary function
$M(\omega)=\mathbb{I}(\mathcal{A}(\omega,\mathbf{x})=l)$ over the space
$\Omega$, where $\omega\in\Omega$ and $\mathbb{I}$ is the indicator function.
Then, we have $\text{Pr}(\mathcal{A}(Y,\mathbf{x})=l)=\text{Pr}(M(Y)=1)$. Our
idea is to construct a subspace for which we can apply the first part of Lemma
1 to derive a lower bound of $\text{Pr}(M(Y)=1)$. We first divide the space
$\Omega$ into three subspaces as follows:

$\displaystyle\mathcal{B}=\\{\omega\in\Omega|\omega\sqsubseteq\mathcal{D},\omega\not\sqsubseteq\mathcal{I}\\},$
(26)
$\displaystyle\mathcal{C}=\\{\omega\in\Omega|\omega\sqsubseteq\mathcal{D}^{\prime},\omega\not\sqsubseteq\mathcal{I}\\},$
(27)
$\displaystyle\mathcal{E}=\\{\omega\in\Omega|\omega\sqsubseteq\mathcal{I}\\}.$
(28)

Since we sample $k$ training examples with replacement uniformly at random, we
have the following:

$\displaystyle\text{Pr}(X=\omega)=\begin{cases}\frac{1}{{n^{k}}},&\text{ if
}\omega\in\mathcal{B}\cup\mathcal{E}\\\ 0,&\text{ otherwise}\end{cases}$ (29)
$\displaystyle\text{Pr}(Y=\omega)=\begin{cases}\frac{1}{{(n^{\prime})^{k}}},&\text{
if }\omega\in\mathcal{C}\cup\mathcal{E}\\\ 0,&\text{ otherwise}\end{cases}$
(30)

Recall that the size of $\mathcal{I}$ is $m$, i.e., $m=|\mathcal{I}|$. Then,
we have the following:

$\displaystyle\text{Pr}(X\in\mathcal{E})=(\frac{m}{n})^{k},\text{Pr}(X\in\mathcal{B})=1-(\frac{m}{n})^{k},\text{
and }\text{Pr}(X\in\mathcal{C})=0.$ (31)
$\displaystyle\text{Pr}(Y\in\mathcal{E})=(\frac{m}{n^{\prime}})^{k},\text{Pr}(Y\in\mathcal{C})=1-(\frac{m}{n^{\prime}})^{k},\text{
and }\text{Pr}(Y\in\mathcal{B})=0.$ (32)

We have $\text{Pr}(X\in\mathcal{E})=(\frac{m}{n})^{k}$ because each of the $k$
examples is sampled independently from $\mathcal{I}$ with probability
$\frac{m}{n}$. Furthermore, since
$\text{Pr}(X\in\mathcal{B})+\text{Pr}(X\in\mathcal{E})=1$, we obtain
$\text{Pr}(X\in\mathcal{B})=1-(\frac{m}{n})^{k}$. Since
$X\not\sqsubseteq\mathcal{D}^{\prime}$, we have
$\text{Pr}(X\in\mathcal{C})=0$. Similarly, we can compute the probabilities in
(32).

We assume $\underline{p_{l}}-\delta_{l}-(1-(\frac{m}{n})^{k})\geq 0$. We can
make this assumption because we only need to find a sufficient condition for
$h(\mathcal{D}^{\prime},\mathbf{x})=l$. We define
$\mathcal{B}^{\prime}\subseteq\mathcal{E}$, i.e., $\mathcal{B}^{\prime}$ is a
subset of $\mathcal{E}$, such that we have the following:

$\displaystyle\text{Pr}(X\in\mathcal{B}^{\prime})=\underline{p_{l}}-\delta_{l}-\text{Pr}(X\in\mathcal{B})=\underline{p_{l}}-\delta_{l}-(1-(\frac{m}{n})^{k}).$
(33)

We can find such subset because $\underline{p_{l}}-\delta_{l}$ is an integer
multiple of $\frac{1}{n^{k}}$. Moreover, we define $\mathcal{R}$ as follows:

$\displaystyle\mathcal{R}=\mathcal{B}\cup\mathcal{B}^{\prime}.$ (34)

Then, based on (5), we have:

$\displaystyle\text{Pr}(\mathcal{A}(X,\mathbf{x})=l)\geq\underline{p_{l}}-\delta_{l}=\text{Pr}(X\in\mathcal{R}).$
(35)

Therefore, we have the following:

$\displaystyle\text{Pr}(M(X)=1)=\text{Pr}(\mathcal{A}(X,\mathbf{x})=l)\geq\text{Pr}(X\in\mathcal{R}).$
(36)

Furthermore, we have $\text{Pr}(X=\omega)>\gamma\cdot\text{Pr}(Y=\omega)$ if
and only if $\omega\in\mathcal{B}$ and
$\text{Pr}(X=\omega)=\gamma\cdot\text{Pr}(Y=\omega)$ if
$\omega\in\mathcal{B}^{\prime}$, where $\gamma=(\frac{n^{\prime}}{n})^{k}$.
Therefore, based on the definition of $\mathcal{R}$ in (34) and the condition
(36), we can apply Lemma 1 to obtain the following:

$\displaystyle\text{Pr}(M(Y)=1)=\text{Pr}(\mathcal{A}(Y,\mathbf{x})=l)\geq\text{Pr}(Y\in\mathcal{R}).$
(37)

$\text{Pr}(Y\in\mathcal{R})$ is a lower bound of
$\text{Pr}(\mathcal{A}(Y,\mathbf{x})=l)$ and can be computed as follows:

$\displaystyle\text{Pr}(Y\in\mathcal{R})$ (38) $\displaystyle=$
$\displaystyle\text{Pr}(Y\in\mathcal{B})+\text{Pr}(Y\in\mathcal{B}^{\prime})$
(39) $\displaystyle=$ $\displaystyle\text{Pr}(Y\in\mathcal{B}^{\prime})$ (40)
$\displaystyle=$ $\displaystyle\text{Pr}(X\in\mathcal{B}^{\prime})/\gamma$
(41) $\displaystyle=$
$\displaystyle\frac{1}{\gamma}\cdot(\underline{p_{l}}-\delta_{l}-(1-(\frac{m}{n})^{k})),$
(42)

where we have (40) from (39) because $\text{Pr}(Y\in\mathcal{B})=0$, (41) from
(40) because $\text{Pr}(X=\omega)=\gamma\cdot\text{Pr}(Y=\omega)$ for
$\omega\in\mathcal{B}^{\prime}$, and the last equation from (33).

Deriving an upper bound of $\max_{j\neq
l}\text{Pr}(\mathcal{A}(Y,\mathbf{x})=j)$: We define the following residual:

$\displaystyle\delta_{j}=(\lceil\overline{p}_{j}\cdot
n^{k}\rceil)/n^{k}-\overline{p}_{j},\forall
j\in\\{1,2,\cdots,c\\}\setminus\\{l\\}.$ (43)

We leverage the second part of Lemma 1 to derive such an upper bound. We
assume $\text{Pr}(X\in\mathcal{E})\geq\overline{p}_{j}+\delta_{j}$, $\forall
j\in\\{1,2,\cdots,c\\}\setminus\\{l\\}$. We can make the assumption because we
derive a sufficient condition for $h(\mathcal{D}^{\prime},\mathbf{x})=l$. For
$\forall j\in\\{1,2,\cdots,c\\}\setminus\\{l\\}$, we define
$\mathcal{C}_{j}\subseteq\mathcal{E}$ such that we have the following:

$\displaystyle\text{Pr}(X\in\mathcal{C}_{j})=\overline{p}_{j}+\delta_{j}.$
(44)

We can find such $\mathcal{C}_{j}$ because $\overline{p}_{j}+\delta_{j}$ is an
integer multiple of $\frac{1}{n^{k}}$. Moreover, we define the following
space:

$\displaystyle\mathcal{Q}_{j}=\mathcal{C}\cup\mathcal{C}_{j}.$ (45)

Therefore, based on (5), we have:

$\displaystyle\text{Pr}(\mathcal{A}(X,\mathbf{x})=j)\leq\overline{p}_{j}+\delta_{j}=\text{Pr}(X\in\mathcal{Q}_{j}).$
(46)

We define a function
$M_{j}(\omega)=\mathbb{I}(\mathcal{A}(\omega,\mathbf{x})=j)$, where
$\omega\in\Omega$. Based on Lemma 1, we have the following:

$\displaystyle\text{Pr}(M(Y)=1)=\text{Pr}(\mathcal{A}(Y,\mathbf{x})=j)\leq\text{Pr}(Y\in\mathcal{Q}_{j}),$
(47)

where $\text{Pr}(Y\in\mathcal{Q}_{j})$ can be computed as follows:

$\displaystyle\text{Pr}(Y\in\mathcal{Q}_{j})$ (48) $\displaystyle=$
$\displaystyle\text{Pr}(Y\in\mathcal{C})+\text{Pr}(Y\in\mathcal{C}_{j})$ (49)
$\displaystyle=$ $\displaystyle
1-(\frac{m}{n^{\prime}})^{k}+\text{Pr}(Y\in\mathcal{C}_{j})$ (50)
$\displaystyle=$ $\displaystyle
1-(\frac{m}{n^{\prime}})^{k}+\text{Pr}(X\in\mathcal{C}_{j})/\gamma$ (51)
$\displaystyle=$ $\displaystyle
1-(\frac{m}{n^{\prime}})^{k}+\frac{1}{\gamma}\cdot(\overline{p}_{j}+\delta_{j}).$
(52)

Therefore, we have:

$\displaystyle\max_{j\neq l}\text{Pr}(\mathcal{A}(Y,\mathbf{x})=j)$ (53)
$\displaystyle\leq$ $\displaystyle\max_{j\neq
l}\text{Pr}(Y\in\mathcal{Q}_{j})$ (54) $\displaystyle=$ $\displaystyle
1-(\frac{m}{n^{\prime}})^{k}+\frac{1}{\gamma}\cdot\max_{j\neq
l}(\overline{p}_{j}+\delta_{j})$ (55) $\displaystyle\leq$ $\displaystyle
1-(\frac{m}{n^{\prime}})^{k}+\frac{1}{\gamma}\cdot(\overline{p}_{s}+\delta_{s}),$
(56)

where $\overline{p}_{s}+\delta_{s}\geq\max\limits_{j\neq
l}(\overline{p}_{j}+\delta_{j})$.

Deriving the certified poisoning size: To reach the goal
$\text{Pr}(\mathcal{A}(Y,\mathbf{x})=l)>\max\limits_{j\neq
l}\text{Pr}(\mathcal{A}(Y,\mathbf{x})=j)$, it is sufficient to have the
following:

$\displaystyle\frac{1}{\gamma}\cdot(\underline{p_{l}}-\delta_{l}-(1-(\frac{m}{n})^{k}))>1-(\frac{m}{n^{\prime}})^{k}+\frac{1}{\gamma}\cdot(\overline{p}_{s}+\delta_{s})$
(57) $\displaystyle\Longleftrightarrow$
$\displaystyle(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{m}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s})<0.$
(58)

Taking all poisoned training datasets $\mathcal{D}^{\prime}$ (i.e., $n-r\leq
n^{\prime}\leq n+r$) into consideration, we have the following sufficient
condition:

$\displaystyle\max_{n-r\leq n^{\prime}\leq
n+r}(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{m}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s})<0.$
(59)

Note that $m=\max(n,n^{\prime})-r$. Furthermore, when the above condition (59)
is satisfied, we have $\underline{p_{l}}-\delta_{l}-(1-(\frac{m}{n})^{k})\geq
0$ and
$\text{Pr}(X\in\mathcal{E})=(\frac{m}{n})^{k}\geq\overline{p}_{j}+\delta_{j},\forall
j\in\\{1,2,\cdots,c\\}\setminus\\{l\\}$, which are the conditions when we can
construct the spaces $\mathcal{B}^{\prime}$ and $\mathcal{C}_{j}$. The
certified poisoning size $r^{*}$ is the maximum $r$ that satisfies the above
sufficient condition. In other words, our certified poisoning size $r^{*}$ is
the solution to the following optimization problem:

$\displaystyle r^{*}$ $\displaystyle=\operatorname*{arg\,max}_{r}r$
$\displaystyle\text{s.t.}\max_{n-r\leq n^{\prime}\leq
n+r}(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{\max(n,n^{\prime})-r}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s})<0.$
(60)

##  Appendix B Proof of Theorem 2

Our idea is to construct a learning algorithm $\mathcal{A}^{*}$ such that the
label $l$ is not predicted by the bagging predictor or there exist ties. When
$r>r^{*}$ and $\delta_{l}=\delta_{s}=0$, there exists a poisoned training
dataset $\mathcal{D}^{\prime}$ with a certain $n^{\prime}\in[n-r,n+r]$ such
that we have:

$\displaystyle(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{\max(n,n^{\prime})-r}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s})\geq
0$ (61) $\displaystyle\Longleftrightarrow$
$\displaystyle(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{m}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s})\geq
0$ (62) $\displaystyle\Longleftrightarrow$ $\displaystyle
1+(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{m}{n})^{k}\geq\underline{p_{l}}-\overline{p}_{s}$
(63) $\displaystyle\Longleftrightarrow$
$\displaystyle\frac{1}{\gamma}\cdot(\underline{p_{l}}-(1-(\frac{m}{n})^{k})\leq
1-(\frac{m}{n^{\prime}})^{k}+\frac{1}{\gamma}\cdot\overline{p}_{s},$ (64)

where $m=\max(n,n^{\prime})-r$ and $\gamma=(\frac{n^{\prime}}{n})^{k}$. We let
$\mathcal{Q}_{s}=\mathcal{C}\cup\mathcal{C}^{\prime}_{s}$, where
$\mathcal{C}^{\prime}_{s}$ satisfies the following:

$\displaystyle\mathcal{C}^{\prime}_{s}\subseteq\mathcal{E},\mathcal{C}^{\prime}_{s}\cap\mathcal{B}^{\prime}=\emptyset,\text{
and }\text{Pr}(X\in\mathcal{C}^{\prime}_{s})=\overline{p}_{s}.$ (65)

Note that we can construct such $\mathcal{C}^{\prime}_{s}$ because
$\underline{p_{l}}+\overline{p}_{s}\leq 1$. Then, we divide the remaining
space $\Omega\setminus(\mathcal{R}\cup\mathcal{Q}_{s})$ into $c-2$ subspaces
such that $\text{Pr}(X\in\mathcal{Q}_{j})\leq\overline{p}_{s}$, where
$j\in\\{1,2,\cdots,c\\}\setminus\\{l,s\\}$. We can construct such subspaces
because $\underline{p_{l}}+(c-1)\cdot\overline{p}_{s}\geq 1$. Then, based on
these subspaces, we construct the following learning algorithm:

$\displaystyle\mathcal{A}^{*}(\omega,\mathbf{x})=\begin{cases}&l,\text{ if
}\omega\in\mathcal{R}\\\ &j,\text{ if }\omega\in\mathcal{Q}_{j}\end{cases}$
(66)

Then, we have the following based on the above definition of the learning
algorithm $\mathcal{A}^{*}$:

$\displaystyle\text{Pr}(\mathcal{A}^{*}(X,\mathbf{x})=l)=\text{Pr}(X\in\mathcal{R})=\underline{p_{l}}$
(67)
$\displaystyle\text{Pr}(\mathcal{A}^{*}(X,\mathbf{x})=s)=\text{Pr}(X\in\mathcal{Q}_{s})=\overline{p}_{s}$
(68)
$\displaystyle\text{Pr}(\mathcal{A}^{*}(X,\mathbf{x})=j)=\text{Pr}(X\in\mathcal{Q}_{j})\leq\overline{p}_{s},j\in\\{1,2,\cdots,c\\}\setminus\\{l,s\\}.$
(69)

Therefore, the learning algorithm $\mathcal{A}^{*}$ is consistent with (5).
Next, we show that $l$ is not predicted by the bagging predictor or there
exist ties when the training dataset is $\mathcal{D}^{\prime}$. In particular,
we have the following:

$\displaystyle\text{Pr}(\mathcal{A}^{*}(Y,\mathbf{x})=l)$ (70)
$\displaystyle=$ $\displaystyle\text{Pr}(Y\in\mathcal{R})$ (71)
$\displaystyle=$
$\displaystyle\frac{1}{\gamma}\cdot(\underline{p_{l}}-(1-(\frac{m}{n})^{k}))$
(72) $\displaystyle\leq$ $\displaystyle
1-(\frac{m}{n^{\prime}})^{k}+\frac{1}{\gamma}\cdot\overline{p}_{s}$ (73)
$\displaystyle=$ $\displaystyle\text{Pr}(Y\in\mathcal{Q}_{s})$ (74)
$\displaystyle=$ $\displaystyle\text{Pr}(\mathcal{A}^{*}(Y,\mathbf{x})=s),$
(75)

where $\gamma=(\frac{n^{\prime}}{n})^{k}$ and we have (73) from (72) because
of (64). Therefore, label $l$ is not predicted for $\mathbf{x}$ or there exist
ties when the training dataset is $\mathcal{D}^{\prime}$.

##  Appendix C Proof of Theorem 3

Based on the definition of SimuEM in (Jia et al., 2020a), we have:

$\displaystyle\text{Pr}(\underline{p_{l_{i}}}\leq\text{Pr}(\mathcal{A}(g(\mathcal{D}),\mathbf{x}_{i})=l_{i})\land\overline{p}_{j}\geq\text{Pr}(\mathcal{A}(g(\mathcal{D}),\mathbf{x}_{i})=j),\forall
j\neq l_{i})\geq 1-\frac{\alpha}{e}.$ (76)

Therefore, the probability that Certify returns an incorrect certified
poisoning size for a testing example $\mathbf{x}_{i}$ is at most
$\frac{\alpha}{e}$, i.e., we have:

$\displaystyle\text{Pr}((\exists\mathcal{D}^{\prime}\in
B(\mathcal{D},r_{i}^{*}),h(\mathcal{D}^{\prime},\mathbf{x}_{i})\neq
l_{i})|l_{i}\neq\text{ABSTAIN})\leq\frac{\alpha}{e}.$ (77)

Then, we have the following:

$\displaystyle\text{Pr}(\cap_{\mathbf{x}_{i}\in\mathcal{D}_{e}}((\forall\mathcal{D}^{\prime}\in
B(\mathcal{D},r_{i}^{*}),h(\mathcal{D}^{\prime},\mathbf{x}_{i})=l_{i})|l_{i}\neq\text{ABSTAIN}))$
(78)
$\displaystyle=1-\text{Pr}(\cup_{\mathbf{x}_{i}\in\mathcal{D}_{e}}((\exists\mathcal{D}^{\prime}\in
B(\mathcal{D},r_{i}^{*}),h(\mathcal{D}^{\prime},\mathbf{x}_{i})\neq
l_{i})|l_{i}\neq\text{ABSTAIN}))$ (79) $\displaystyle\geq
1-\sum_{\mathbf{x}_{i}\in\mathcal{D}_{e}}\text{Pr}((\exists\mathcal{D}^{\prime}\in
B(\mathcal{D},r_{i}^{*}),h(\mathcal{D}^{\prime},\mathbf{x}_{i})\neq
l_{i})|l_{i}\neq\text{ABSTAIN})$ (80) $\displaystyle\geq
1-e\cdot\frac{\alpha}{e}$ (81) $\displaystyle=1-\alpha$ (82)

We have (80) from (79) according to the Boole’s inequality.

##  Appendix D Derivation of the Analytical Form of $n^{\prime}$

We define $L(n^{\prime})$ as follows:

$\displaystyle
L(n^{\prime})=(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{\max(n,n^{\prime})-r}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s}).$
(83)

We have the following analytical form of $n^{\prime}$ at which $L(n^{\prime})$
reaches its maximum:

$\displaystyle\operatorname*{arg\,max}_{n-r\leq n^{\prime}\leq
n+r}L(n^{\prime})=\begin{cases}n,&\text{ if }r\leq
n\cdot(1-\sqrt[k-1]{\frac{1}{2}})\\\ n+r,&\text{ if }r\geq
n\cdot(\sqrt[k-1]{2}-1)\\\
\lceil\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}\rceil\text{ or
}\lfloor\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}\rfloor,&\text{ otherwise.
}\end{cases}$ (84)

Next, we show details on how to derive such analytical form of $n^{\prime}$.
When $n-r\leq n^{\prime}\leq n$, we have the following:

$\displaystyle
L(n^{\prime})=(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{n-r}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s}).$
(85)

Therefore, when $n-r\leq n^{\prime}\leq n$, $L(n^{\prime})$ increases as
$n^{\prime}$ increases. Thus, $L(n^{\prime})$ reaches its maximum value when
$n\leq n^{\prime}\leq n+r$. When $n\leq n^{\prime}\leq n+r$, we have the
following:

$\displaystyle
L(n^{\prime})=(\frac{n^{\prime}}{n})^{k}-2\cdot(\frac{n^{\prime}-r}{n})^{k}+1-(\underline{p_{l}}-\overline{p}_{s}-\delta_{l}-\delta_{s}).$
(86)

Moreover, we have:

$\displaystyle\frac{\partial L(x)}{\partial x}$ (87) $\displaystyle=$
$\displaystyle\frac{1}{n^{k}}\cdot(k\cdot x^{k-1}-2\cdot k\cdot(x-r)^{k-1})$
(88) $\displaystyle=$ $\displaystyle\frac{k\cdot
x^{k-1}}{n^{k}}\cdot(1-2\cdot(1-\frac{r}{x})^{k-1}).$ (89)

$\frac{k\cdot x^{k-1}}{n^{k}}$ is larger than $0$. Moreover,
$1-2\cdot(1-\frac{r}{x})^{k-1}$ decreases as $x$ increases when $x\geq r$ and
it only has one root that is no smaller than $r$ which is as follows:

$\displaystyle x_{root}=\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}.$ (90)

Therefore, we have $\frac{\partial L(x)}{\partial x}>0$ when $r\leq
x<\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}$ and $\frac{\partial L(x)}{\partial
x}<0$ when $x>\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}$. $L(x)$ increases as $x$
increases in the range $[r,\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}})$ and decreases
as $x$ increases in the range $(\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}},+\infty)$.
Therefore, we have the following three cases:

Case I: When $r\leq n\cdot(1-\sqrt[k-1]{\frac{1}{2}})$, $L(n^{\prime})$
reaches its maximum value at $n^{\prime}=n$ since $L(n^{\prime})$ decreases as
$n^{\prime}$ increases in the range $[n,n+r]$.

Case II: When $n\cdot(1-\sqrt[k-1]{\frac{1}{2}})<r<n\cdot(\sqrt[k-1]{2}-1)$,
$L(n^{\prime})$ reaches its maximum value at
$n^{\prime}=\lceil\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}\rceil\text{ or
}\lfloor\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}\rfloor$ since $L(n^{\prime})$
increases as $n^{\prime}$ increases in the range
$[n,\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}}]$ and decreases as $n^{\prime}$
increases in the range $[\frac{r}{1-\sqrt[k-1]{\frac{1}{2}}},n+r]$.

Case III: When $r\geq n\cdot(\sqrt[k-1]{2}-1)$, $L(n^{\prime})$ reaches its
maximum value at $n^{\prime}=n+r$ since $L(n^{\prime})$ increases as
$n^{\prime}$ increases in the range $[n,n+r]$.