# RAB: Provable Robustness Against Backdoor Attacks

Maurice Weber† ∗ Xiaojun Xu‡ 111The first two authors contribute equally to
this work. Bojan Karlaš† Ce Zhang† Bo Li‡
† ETH Zurich, Switzerland {maurice.weber, bojan.karlas<EMAIL_ADDRESS>
‡ University of Illinois at Urbana-Champaign, USA {xiaojun3<EMAIL_ADDRESS>
###### Abstract

Recent studies have shown that deep neural networks (DNNs) are highly
vulnerable to adversarial attacks, including evasion and backdoor (poisoning)
attacks. On the defense side, there have been intensive interests in both
empirical and provable robustness against evasion attacks; however, provable
robustness against backdoor attacks remains largely unexplored. In this paper,
we focus on certifying robustness against backdoor attacks. To this end, we
first provide a unified framework for robustness certification and show that
it leads to a tight robustness condition for backdoor attacks. We then propose
the first robust training process, RAB, to smooth the trained model and
certify its robustness against backdoor attacks. Moreover, we evaluate the
certified robustness of a family of “smoothed” models which are trained in a
differentially private fashion, and show that they achieve better certified
robustness bounds. In addition, we theoretically show that it is possible to
train the robust smoothed models efficiently for simple models such as
K-nearest neighbor classifiers, and we propose an exact smooth-training
algorithm which eliminates the need to sample from a noise distribution.
Empirically, we conduct comprehensive experiments for different machine
learning (ML) models such as DNNs, differentially private DNNs, and K-NN
models on MNIST, CIFAR-10 and ImageNet datasets (focusing on binary
classifiers), and provide the first benchmark for certified robustness against
backdoor attacks. In addition, we evaluate K-NN models on a spambase tabular
dataset to demonstrate the advantages of the proposed exact algorithm. Both
the theoretical analysis and the comprehensive benchmark on diverse ML models
and datasets shed lights on further robust learning strategies against
training time attacks or other general adversarial attacks.

##  1 Introduction

Building machine learning algorithms that are robust to adversarial attacks
has been an emerging topic over the last decade. There are mainly two
different types of adversarial attacks: (1) evasion attacks, in which the
attackers manipulate the test examples against a trained machine learning (ML)
model, and (2) data poisoning attacks, in which the attackers are allowed to
perturb the training set. Both types of attacks have attracted intensive
interests from academia as well as industry [14, 35, 23, 37].

In response, several empirical solutions have been proposed as defenses
against evasion attacks [5, 36, 25, 39]. For instance, adversarial training
has been proposed to retrain the ML models with generated adversarial examples
[27]; quantization has been applied to either inputs or neural network weights
to defend against potential adversarial instances [36]. However, recent
studies have shown that these defenses are not resilient against intelligent
adversaries responding dynamically to the deployed defenses [5, 2].

As a result, one recent, exciting line of research aims to develop provably
robust algorithms against evasion attacks, including both deterministic and
probabilistic certification approaches [22]. In particular, among these
certified robustness approaches, only randomized smoothing and its variations
are able to provide certified robustness against evasion attacks on large
scale datasets such as ImageNet [20, 10, 38]. Intuitively, the randomized
smoothing based approaches are able to certify the robustness of a smoothed
classifier, by outputting a consistent prediction for an adversarial input as
long as the perturbation is within a certain radius. The smoothed classifier
is obtained by taking the expectation over the possible outputs given a set of
randomly smoothed inputs, which are generated by adding noise drawn from a
certain distribution to an input.

Figure 1: In this paper, we define a robust training process RAB for
classifiers. Given a backdoor’ed dataset $\mathcal{D}^{\prime}$ — produced by
adding backdoor patterns $\Delta$ by the attacker to some instances in the
dataset $\mathcal{D}$ with clean features — this robust training process
guarantees that, for all test examples $x$,
$\mathcal{A}_{\mathcal{D}^{\prime}}(x)=\mathcal{A}_{\mathcal{D}}(x)$, with
high probability when the magnitude of $\Delta$ is within the certification
radius.

Despite these recent developments on provable robustness against evasion
attacks, only empirical studies have been conducted to defend against backdoor
attacks [33, 13, 16, 21], and the question of how to improve and certify the
robustness of given machine learning models against backdoor attacks remains
largely unanswered. To our best knowledge, there is no provably robust
strategy to deal with backdoor attacks yet. Naturally, we ask: Can we develop
provably robust ML models against backdoor attacks?

Backdoor attacks have been studied extensively recently. For these type of
attacks, an attacker adds small backdoor patterns to a subset of training
instances such that the trained model is biased towards test images with the
same patterns [15, 8]. Such attacks can be applied to various real-world
scenarios such as online face recognition systems [21, 8]. In this paper, we
present the first verification process RAB to provide provable robustness for
ML models against backdoor attacks. Specifically, as shown in Figure 1, our
certification goal is to guarantee that the prediction of a classifier will
stay the same, no matter what patterns an attacker adds to the training set as
long as these patterns are within an $L_{p}$-ball of radius $R$.

Note that one can certify against a label flipping attack by setting a limit
to how many labels in the training set may be flipped such that it does not
affect the final prediction. This kind of guarantee has been analyzed in
concurrent work [30] by adapting randomized smoothing, while it focuses on a
different certification goal.

Our technique to achieve this is mainly inspired by the randomized smoothing
technique against evasion attacks [10] but goes significantly beyond it due to
the different settings (e.g. evasion and backdoor attacks). Our first
step/contribution is to develop a general theoretic framework to generalize
randomized smoothing to a much larger family of functions and smoothing
distributions. This allows us to support cases in which a classifier is a
function that takes as input a test instance _and_ a training set. With our
framework, we can _(1) provide robustness certificates against both evasion
and dataset poisoning attacks;_ _(2) certify any classifier which takes as
input a tuple of test instance and training dataset_ and _(3) prove that the
derived robustness bound is tight_.

However, a general theoretical framework alone cannot provide reasonable
certified radius for backdoor attacks. Our second step/contribution is to
instantiate our theoretical framework with a practical training pipeline RAB
which provides provable robustness against backdoor attacks. At a high level,
as shown in Figure 2, given a training set $\mathcal{D}$, RAB generates $N$
additional “smoothed” training data $\mathcal{D}+\epsilon_{i}$ by adding noise
$\epsilon_{i}$ ($i\in\\{1,\ldots,N\\}$) drawn from a certain smoothing
distribution and train a set of classifiers. These models are then aggregated
to generate a “smoothed classifier” for which we prove that its output will be
consistent regardless of whether there are backdoors added during training, as
long as the backdoor patterns satisfy certain conditions. Concretely, our
optimization goal can be classified into two categories: (1) Certification
Radius and (2) Certification Efficiency. To improve the certification radius,
we certify DNN classifiers with a data augmentation scheme and in the
meantime, explore the impact of a differentially private training process and
show that such inherently “smoothed” models enjoy higher certified robustness.
This provides additional guidance of improving the certified robustness
against backdoor attacks and we hope that it can inspire other researches in
the future. To improve the certification efficiency, we observed that for
certain families of classifiers, namely $K$-nearest neighbor classifiers, we
can develop an efficient algorithm to compute the smoothing result exactly,
eliminating the need to resort to Monte Carlo algorithms as for generic
classifiers.

Our third contribution is an extensive benchmark, evaluating our framework RAB
on multiple machine learning models and provide the first collection of
certified robustness bounds on a diverse range of datasets such as MNIST,
CIFAR-10, ImageNet, and a spambase tabular data with a focus on binary
classifiers. We hope that these experiments and benchmarks can provide future
directions for improving the robustness of machine learning models.

Being the first result on provable robustness against backdoor attacks, we are
convinced that these results will be improved by follow-up work in the near
future. We make the code and evaluation protocol publicly available with the
hope to facilitate future research by the community.

We summarize the contributions of our work as follows:

  * •

We propose a unified framework to certify model robustness against both
evasion and poisoning attacks and prove that our robustness bound is tight.

  * •

We provide the first certifiable robustness bound for general machine learning
models against backdoor attacks with different smoothing noise distributions.

  * •

We propose an exact efficient smoothing algorithm for $K$-NN models without
needing to sample random noise during training.

  * •

We also show that naturally smoothed models (e.g. differentially private
models) can potentially achieve higher certified robustness bound under the
RAB framework.

  * •

We conduct extensive reproducible large-scale experiments and provide a
benchmark on certified robustness against three representative backdoor
attacks for multiple types of models (e.g. DNNs, differentially private DNNs,
and $K$-NN) on diverse datasets with a focus on binary classifiers. 222Our
models and code are publicly available at https://github.com/AI-
secure/Robustness-Against-Backdoor-Attacks.

The remainder of this paper is organized as follows. Section 2 provides
background on backdoor attacks and related verifiable robustness techniques,
followed by the threat model and method overview in Section 3. Section 4
presents the proposed general theoretical framework for certifying robustness
against evasion and poisoning attacks, the tightness of the derived robustness
bound, and sheds light on a connection between statistical hypothesis testing
and certifiable robustness. Section 5 explains in detail the proposed approach
RAB to certifying robustness against backdoor attacks under the general
framework with Gaussian and Uniform noise distributions. Section 6 analyzes
robustness properties of DNNs, differentially private DNNs and $K$-NN
classifiers and presents algorithms to certify robustness for such models
(mainly on binary classifiers). Experimental results are presented in section
7. Finally, Section 8 puts our results in context with existing work and
Section 9 concludes.

##  2 Background

In this section, we provide an overview of different backdoor attacks and
randomized smoothing for certifying model robustness against evasion attacks.

###  2.1 Backdoor attacks

A backdoor attack against an ML model aims to inject certain “backdoor”
patterns during training and associate such patterns with a specific
adversarial target (label). As a result, during testing time, any test
instance with such a pattern will be misclassified as the pre-selected
adversarial target [16, 8]. ML models with injected backdoors are called
_backdoored models_ and they are typically able to achieve performance similar
to clean models on benign data, making it very challenging to detect whether
the model has been attacked.

There are several ways to categorize backdoor attacks. First, based on the
_adversarial target design_ , the attacks can be characterized as _single
target attack_ and _all-to-all attack_. In a _single target attack_ , the
backdoor pattern will cause the poisoned classifier to always return a
designed target label. An _all-to-all_ attack leverages the backdoor pattern
to permute the classifier results.

A second categorization is based on _different types of backdoor patterns_.
There are _region based_ and _blending_ backdoor attacks. In the _region
based_ attack, a specific region of the training instance is manipulated in a
subtle way that will not cause human notification [16, 23]. In particular, it
has been shown that such backdoor patterns can be as small as only one or four
pixels [31]. On the other hand, Chen at al. [8] show that by blending the
whole instance with a certain pattern such as a fixed random noise pattern, it
is possible to generate effective backdoors to poison the ML models.

In this work, we focus on certifying the robustness against general backdoor
attacks, where the attacker is able to add any specific or uncontrollable
random backdoor patterns for arbitrary adversarial targets.

###  2.2 Improving ML robustness via randomized smoothing

Randomized smoothing has been studied by several works to improve model
robustness against evasion attacks. Some provide heuristic approaches to
defend against adversarial examples [24, 4], and some provide theoretic
guarantees against $L_{p}$ bounded adversarial perturbations. In particular,
Cohen et al. [10] have proposed a tight robustness guarantee in $L_{2}$ norm
with Gaussian noise smoothing.

On a high level, the randomized smoothing strategy [10] provides a way to
certify the robustness of a _smoothed_ classifier against adversarial examples
during test time. First, a given classifier is smoothed by adding Gaussian
noise $\varepsilon\sim\mathcal{N}(0,\sigma^{2}\mathds{1}_{d})$ around each
test instance. Then, the classification gap between a lower bound of the
confidence on the top-1 class $p_{A}$ and an upper bound of the confidence on
the top-2 class $p_{B}$ are obtained. The smoothed classifier will be
guaranteed to provide consistent predictions within the perturbation radius,
which is a function of the smoothing noise variance $\sigma$, $p_{A}$ and
$p_{B}$, for each test instance.

However, all these approaches focus on the robustness against evasion attacks
only, and in this work we aim to first provide a function smoothing framework
to certify the robustness against both evasion and poisoning attacks. In
particular, the current randomized smoothing strategy focuses on adding noise
to induce smoothness on the level of test instance, while our unified
framework generalizes it to smoothing on the level of classifiers. We then
specifically describe the additional challenges of certifying robustness
against backdoor attacks, and provide theoretic robustness guarantees for
different machine learning models, randomized smoothing noise distributions,
as well as the tightness of the robustness bounds.

Figure 2: An illustration of the RAB robust training process. Given a poisoned
training set $\mathcal{D}+\Delta$ and a training process $\mathcal{A}$
vulnerable to backdoor attacks, RAB generates $N$ smoothed training sets
$\\{\mathcal{D}_{i}\\}_{i\in[N]}$ and trains $N$ different classifiers
$\mathcal{A}_{i}$.

##  3 Threat Model and Method Overview

In this section, we first define the threat model including concise
definitions of a backdoor attack, and then introduce the method overview,
where we define the robustness guarantee that our method provides.

###  3.1 Notation

We write random variables as uppercase letters $X$ and use the notation
$\mathbb{P}_{X}$ to denote the probability measure induced by $X$ and write
$f_{X}$ to denote the probability density function. Realizations of random
variables are written in lowercase letters. For discrete random variables, we
use lowercase letters to denote their probability mass function, e.g. $p(y)$
for a distribution over labels. Feature vectors are taken to be
$d$-dimensional real vectors $x\in\mathbb{R}^{d}$ and the set of labels $y$
for a $C$-multiclass classification problem is given by
$\mathcal{C}=\\{1,\,\ldots,\,C\\}$. A training set $\mathcal{D}$ consists of
$n$ (feature, label)-pairs
$\mathcal{D}=\\{(x_{1},\,y_{1}),\,\ldots,\,(x_{n},\,y_{n})\\}$. For a dataset
$\mathcal{D}$ and a collection of $n$ feature vectors
$d=\\{d_{1},\,\ldots,\,d_{n}\\}$, we write $\mathcal{D}+d$ to denote the set
$\\{(x_{1}+d_{1},\,y_{1}),\,\ldots,\,(x_{n}+d_{n},\,y_{n})\\}$. We view a
classifier as a deterministic function that takes as input a tuple with a test
instance $x$ and a training set $\mathcal{D}$ and returns a class label
$y\in\mathcal{C}$. Formally, given a dataset $\mathcal{D}$ and a test instance
$x$, a classifier $h$ learns a conditional probability distribution
$p(y\lvert\,x,\,\mathcal{D})$ over class labels and outputs the label which is
deemed most likely under the learned distribution $p$:

$h(x,\,\mathcal{D})=\arg\max_{y}p(y\lvert\,x,\,\mathcal{D}).$ (1)

We omit the dependence on model parameters throughout this paper and tacitly
assume that the learned model is based on parameters obtained from training on
the dataset $\mathcal{D}$ via some optimization schemes such as stochastic
gradient descent.

###  3.2 Threat Model and The Goal of Defense

First, we define our threat model: an adversary carries out a backdoor attack
against a classifier $h$ and a clean dataset
$\mathcal{D}=\\{(x_{i},y_{i})\\}$. The attacker has in mind a target backdoor
pattern $\Omega_{x}$ and a target class $\tilde{y}$ and the adversarial goal
is to alter the dataset such that, given a clean test example $x$, adding the
backdoor pattern to $x$ (i.e., $x+\Omega_{x}$) will alter the classifier
output $\tilde{y}$ with high probability. In general, the attack can replace
$r$ training instances $(x_{i},\,y_{i})$ by backdoored instances
$(x_{i}+\Omega_{x},\,\tilde{y}_{i})$. We remark that the attacker could embed
distinct patterns to each instance and our result naturally extends to this
case. Thus, summarizing the backdoor patterns as the collection
$\Delta(\Omega_{x}):=\\{\delta_{1},\,\ldots,\,\delta_{r},\,0,\ldots,0\\}$, we
formalize a backdoor attack as the transformation
$(\mathcal{D},\Omega_{x},\tilde{y})\to\mathcal{D}_{BD}(\Omega_{x},\tilde{y})$:

$\displaystyle\mathcal{D}_{BD}(\Omega_{x},\tilde{y})=\\{(x_{i}+\delta_{i},\tilde{y}_{i})\\}_{i=1}^{r}\cup\\{(x_{i},y_{i})\\}_{i=r+1}^{n}$
(2)

We often write $\mathcal{D}_{BD}(\Omega_{x})$ instead of
$\mathcal{D}_{BD}(\Omega_{x},\tilde{y})$ when our focus is on the backdoor
pattern $\Omega_{x}$ instead of the target class $\tilde{y}$. We define the
backdoor attack succeeds on test example $x$ when

$h(x+\Omega_{x},\mathcal{D}_{BD}(\Omega_{x}))=\tilde{y}$ (3)

Goal of Defense. One natural goal to defend against the above backdoor attack
is to ensure the prediction of $h(x+\Omega_{x},\mathcal{D}_{BD}(\Omega_{x}))$
to be independent of the pattern $\Omega_{x}$, i.e.,

$h(x+\Omega_{x},\mathcal{D}_{BD}(\Omega_{x}))=h(x+\Omega_{x},\mathcal{D}_{BD}(\emptyset))$
(4)

where $\mathcal{D}_{BD}(\emptyset)$ is the dataset without any embedded
backdoor patterns ($\delta_{i}=0$). When this is true, the attacker obtained
no additional information by knowing the pattern $\Omega_{x}$ embedded in the
training set.

###  3.3 Method Overview

Certified Robustness against Backdoors. We aim to obtain a robustness bound
$R$ such that, whenever the sum of the magnitude of backdoors is below $R$,
the prediction of the backdoored classifier is the same as when the classifier
is trained on benign data. Formally, if $\mathcal{D}_{BD}(\Omega_{x})$ denotes
the backdoored training set, and $\mathcal{D}$ the training set containing
clean features, we say that a classifier is provably robust whenever

$\sqrt{\sum_{i=1}^{r}\left\|\delta_{i}\right\|_{2}^{2}}<R$ (5)

implies that
$h(x+\delta,\,\mathcal{D}_{BD}(\Omega_{x}))=h(x+\delta,\,\mathcal{D}_{BD}(\emptyset))$.

Our approach to obtaining the aforementioned robustness guarantee is based on
randomized smoothing, which leads to a robust training pipeline, termed RAB,
as illustrated in Figure 2. Given a clean dataset $\mathcal{D}$ and backdoored
dataset $\mathcal{D}_{BD}(\Omega_{x})$, the goal of the defender is to make
sure that the prediction on test instances embedded with pattern $\Omega_{x}$
is the same over models trained with $\mathcal{D}_{BD}(\emptyset)$.

Different from randomized smoothing based certification against evasion
attacks, here it is not enough to only smooth the test instances. Instead, in
RAB, we will first add noise vectors, sampled from a smoothing distribution,
to the given training instances, so as to obtain a collection of “smoothed”
training sets. We subsequently train a model on each training set, and
aggregate their final outputs together as the final “smoothed” prediction.
After this process, we show that it is possible to leverage the Neyman Pearson
lemma in order to derive a robustness condition for this smoothed training
process RAB. Additionally, the connection to the Neyman Pearson lemma also
allows us to prove that the obtained robustness bound is tight. Note that in
the RAB framework, it requires the training instances to be “smoothed” by a
set of independent noise drawn from certain distribution. Thus, some natural
approaches for achieving model stability such as the differential privacy
based approaches are not directly applicable here. We will evaluate the
differentially private models under our framework in the experimental section
and show that it is possible to combine these different model stabilization
approaches to improve and certify the model robustness against backdoors.

In the following, we illustrate the RAB pipeline in three steps. In Section 4,
we introduce our theoretical foundation on a unified framework for certifying
robustness against both evasion and backdoor attacks. In Section 5, we
introduce how to apply our unified framework to defend against backdoor
attacks. In Section 6, we present the RAB pipeline on three types of models —
DNNs, differentially private DNNs and $K$-NN models.

We remark that, within this RAB training and certification process, there are
several additional challenges. First, after adding noise to the training data,
the clean accuracy of the trained classifier typically drops due to the
distribution shift in the training data. In order to mitigate this problem, we
add a deterministic value, based on the hash of the trained model, to test
instances (Section 6), which minimizes the distribution shift and leads to
improved accuracy scores. Second, considering different smoothing
distributions for the training data, we provide a rigorous analysis and a
robustness bound for both Gaussian and Uniform smoothing distributions
(Section 5). Third, we note the proposed training process requires to sample a
large number of randomly perturbed training sets. Since this is
computationally expensive, we propose an efficient algorithm for $K$-NN
classifiers (Section 6).

##  4 Unified Framework for Certified Robustness

In this section, we propose a unified theoretical framework for certified
robustness against evasion and poisoning attacks for classification models.
Our framework is based on the intuition that randomizing the prediction or
training process would “smoothen” the final prediction and therefore reduce
the vulnerability. This principle has been successfully applied to certifying
robustness against evasion attacks on classification models [10]. We will
first formally define the notion of a smoothed classifier where we extend upon
previous work by randomizing _both_ the test instance and the training set. We
then introduce some basic terminology from hypothesis testing, from where we
leverage the Neyman Pearson lemma to derive a generic robustness condition in
Theorem 1. Finally, we show that this robustness condition is tight.

###  4.1 Preliminaries

#### Smoothed Classifiers

On a high-level, a smoothed classifier $g$ is derived from a base classifier
$h$ by introducing additive noise to the input consisting of test and training
instances. In a nutshell, the intuition behind randomized smoothing
classifiers is that noise reduces the occurrence of regions with high
curvature in the decision boundaries, resulting in reduced vulnerability to
adversarial attacks. Recall that a classifier $h$, here serving as a base
classifier, is defined as
$h(x,\,\mathcal{D})=\arg\max_{y}p(y\lvert\,x,\,\mathcal{D})$ where $p$ is
learned from a dataset $\mathcal{D}$ and is interpreted as a conditional
probability distribution over labels $y$. A smoothed classifier is then
defined by

$q(y\lvert\,x,\,\mathcal{D})=\mathbb{E}_{X,D}\left(p(y\lvert\,x+X,\,\mathcal{D}+D)\right)$
(6)

where we have introduced random variables $X\sim\mathbb{P}_{X}$ and
$D\sim\mathbb{P}_{D}$ which serve as smoothing distributions and are assumed
to be independent. We emphasize that $D$ is a collection of $n$ independent
and identically distributed random variables $D^{(i)}$, each of which is added
to a training instance in $\mathcal{D}$. The final, smoothed classifier then
assigns the most likely class to an instance $x$ under this new, “smoothed”
model $q$, so that

$g(x,\,\mathcal{D})=\arg\max_{y}q(y\lvert\,x,\,\mathcal{D}).$ (7)

We notice that, with this formulation of a smoothed classifier, we can also
model randomized smoothing for defending against evasion attacks by setting
the trainings set noise to be zero, i.e. $D\equiv 0$. We emphasize at this
point that the smoothed classifier $g$ implicitly depends on the choice of
noise distributions $\mathbb{P}_{X}$ and $\mathbb{P}_{D}$. In section 5 we
instantiate this classifier with Gaussian noise and with Uniform noise and
show how this leads to different robustness bounds.

#### Statistical Hypothesis Testing

Hypothesis testing is a statistical problem that is concerned with the
question whether or not some hypothesis that has been formulated is correct. A
decision procedure for such a problem is called a statistical hypothesis test.
Formally, the decision is based on the value of a realization $x$ for a random
variable $X$ whose distribution is known to be either $\mathbb{P}_{0}$ (the
null hypothesis) or $\mathbb{P}_{1}$ (the alternative hypothesis). Given a
sample $x\in\mathcal{X}$, a randomized test $\phi$ can be modeled as a
function $\phi\colon\mathcal{X}\to[0,\,1]$ which rejects the null hypothesis
with probability $\phi(x)$ and accepts it with probability $1-\phi(x)$. The
two central quantities of interest are the probabilities of making a type I
error, denoted by $\alpha(\phi)$ and the probability of making a type II
error, denoted by $\beta(\phi)$. The former corresponds to the situation where
the test $\phi$ decides for the alternative when the null is true, while the
latter occurs when the alternative is true but the test decides for the null.
Formally, $\alpha$ and $\beta$ are defined as

$\alpha(\phi)=\mathbb{E}_{0}(\phi(X)),\hskip
10.00002pt\beta(\phi)=\mathbb{E}_{1}(1-\phi(X))$ (8)

where $\mathbb{E}_{\\{0,1\\}}$ denotes the expectation w.r.t
$\mathbb{P}_{\\{0,1\\}}$. The problem is then to select the test $\phi$ which
minimizes the probability of making a type II error, subject to the constraint
that the probability of making a type-I error is below a threshold
$\alpha_{0}$. The Neyman Pearson lemma [29] states that a likelihood ratio
test $\phi_{NP}$ is optimal, i.e. that $\alpha(\phi_{NP})=\alpha_{0}$ and
$\beta(\phi_{NP})=\beta^{*}(\alpha_{0})$ where

$\beta^{*}(\alpha_{0})=\inf_{\phi\colon\alpha(\phi)\leq\alpha_{0}}\beta(\phi).$
(9)

In Theorem 1, we leverage this formalism in order to obtain a robustness
guarantee for smoothed classifiers. Additionally, stemming from the optimality
of the likelihood ratio test, we will show in Theorem 2 that this condition is
tight.

###  4.2 A General Condition for Provable Robustness

In this section, we derive a tight robustness condition by drawing a
connection between statistical hypothesis testing and robustness of
classification models subject to adversarial attacks. We allow adversaries to
conduct an attack on either _(i) the test instance $x$_, _(ii) the training
features in $\mathcal{D}$_ or _(iii) a combined attack on test and training
set_. The resulting robustness condition is of a general nature and is
expressed in terms of the optimal type II errors for likelihood ratio tests.
We remark that this theorem is a more general version of the result presented
in [10], by extending it to general smoothing distributions and smoothing on
the training set. In Section 5 we will show how this result can be used to
obtain a robustness bound in terms of $L_{p}$-norm bounded backdoor attacks.
We show that smoothing on the training set makes it possible for certifying
the robustness against backdoors; and the general smoothing distribution
allows us to explore the robustness bound certified by different smoothing
distributions.

######  Theorem 1.

Let $q$ be the smoothed classifier as in (6) with smoothing distribution
$Z:=(X,\,D)$ with $X$ taking values in $\mathbb{R}^{d}$ and $D$ being a
collection $n$ independent $\mathbb{R}^{d}$-valued random variables,
$D=(D^{(1)},\,\ldots,\,D^{(n)})$. Let $\delta\in\mathbb{R}^{d}$ and let
$\Delta:=(\delta_{1},\,\ldots,\,\delta_{n})$ for backdoor patterns
$\delta_{i}\in\mathbb{R}^{d}$. Let $y_{A}\in\mathcal{C}$ and let
$p_{A},\,p_{B}\in[0,\,1]$ such that $y_{A}=g(x,\,\mathcal{D})$ and

$q(y_{A}\lvert\,x,\,\mathcal{D})\geq p_{A}>p_{B}\geq\max_{y\neq
y_{A}}q(y\lvert\,x,\,\mathcal{D}).$ (10)

If the optimal type II error probabilities, for testing the null
$Z\sim\mathbb{P}_{0}$ against the alternative
$Z+(\delta,\,\Delta)\sim\mathbb{P}_{1}$, satisfy

$\beta^{*}(1-p_{A})+\beta^{*}(p_{B})>1,$ (11)

then it is guaranteed that
$y_{A}=\arg\max_{y}q(y\lvert\,x+\delta,\,\mathcal{D}+\Delta)$.

The following is a short sketch of the proof for this theorem. We refer the
reader to Appendix A for a detailed proof.

###### Proof (Sketch).

We first explicitly construct likelihood ratio tests $\phi_{A}$ and $\phi_{B}$
for testing the null hypothesis $Z$ against the alternative
$Z+(\delta,\,\Delta)$ with type I errors $\alpha(\phi_{A})=1-p_{A}$ and
$\alpha(\phi_{B})=p_{B}$ respectively. An argument similar to the Neyman-
Pearson Lemma [29] then shows that the class probability for $y_{A}$ given by
$q$ on the perturbed input is lower bounded by
$\beta(\phi_{A})=\beta^{*}(1-p_{A})$. A similar reasoning leads to the fact
that an upper bound on the prediction score for $y\neq y_{A}$ on the perturbed
input is given by $1-\beta(\phi_{B})=1-\beta^{*}(p_{B})$. Combining this leads
to condition (11). ∎

We now make some observations about Theorem 1 in order to get intuition on the
robustness condition (11):

  * •

Different smoothing distributions lead to robustness bounds in terms of
different norms. For example, Gaussian noise yields a robustness bound in
$L_{2}$ norm while Uniform noise leads to other $L_{p}$ norms.

  * •

The robustness condition (11) does not make any assumption on the underlying
classifier other than on the class probabilities predicted by its smoothed
version.

  * •

The random variable $Z+(\delta,\,\Delta)$ models general adversarial attack
including both evasion and backdoor attacks.

  * •

If no attack is present, i.e. if $(\delta,\,\Delta)=(0,\,0)$, then
$Z=Z+(\delta,\,\Delta)$ and we get the trivial condition $p_{A}>p_{B}$.

  * •

As $p_{A}$ increases, the optimal type II error increases for given backdoor
$(\delta,\,\Delta)$. Thus, in the simplified setup where $p_{A}+p_{B}=1$ and
the robustness condition reads $\beta^{*}(1-p_{A})>1/2$, the distribution
shift caused by $(\delta,\,\Delta)$ can increase. Thus, as the smoothed
classifier becomes more confident, the robust region becomes larger.

While the generality of Theorem 1 allows to model a multitude of threat
models, it bears the challenge of how one should instantiate this theorem such
that it is applicable to defend against a specific adversarial attack. In
addition to the flexibility with regards to the underlying threat model, we
are also provided with flexibility with regards to the smoothing
distributions, resulting in different robustness guarantees. This again comes
with the question, which smoothing distributions result in useful robustness
bounds. In Section 5, we will show how this theorem can be applied to obtain
the robustness guarantee against backdoor attacks.

The next proposition shows that $Z$ and $Z+(\delta,\Delta)$ having non-
disjoint support is a necessary condition on the adversarial perturbations
$(\delta,\,\Delta)$ such that (11) can be satisfied. This sheds light on the
dynamics governing the robustness condition (11): if the smoothing
distribution $Z$ has compact support, then it is impossible to certify
perturbations $(\delta,\,\Delta)$, which induce a shift beyond the support of
$Z$ . This result then provides us with an idea on the maximal possible
robustness bound.

######  Proposition 1.

If $Z$ and $Z^{\prime}:=(\delta,\Delta)+Z$ have disjoint support, then
condition (11) cannot be satisfied.

###### Proof.

If $Z$ and $Z^{\prime}$ have disjoint supports, then the null hypothesis $Z$
can be distinguished from the alternative $Z^{\prime}$ by a single observation
and with zero probability of error, since $f_{Z}(z)=0\iff
f_{Z^{\prime}}(z)\neq 0$ for any
$z\in\mathrm{supp}(Z)\,\cup\,\mathrm{supp}(Z^{\prime})$. The hypotheses can
thus be distinguished in a deterministic way and hence any likelihood ratio
test type II error $\beta(\phi)=1-\mathbb{E}(\phi(Z^{\prime}))=0$. In
particular, this leads to the condition

$0=\beta^{*}(1-p_{A})+\beta^{*}(p_{B})>1$ (12)

which can never be satisfied. ∎

For example, suppose $Z=(X,\,0)$ with $X\sim\mathcal{U}[0,1]$. As a
consequence of Proposition 1 we immediately see that it is not possible to
certify input perturbations $\delta$ with absolute value larger than $1$,
because otherwise $Z$ and $\delta+Z$ would have disjoint supports.

Next we will show that our robustness condition is tight in the following
sense: If (10) is all that is known about the smoothed classifier $g$, then
there is no perturbation $(\delta,\Delta)$ that violates (11). On the other
hand, if (11) is violated, then we can always construct a smoothed classifier
$g^{*}$ such that it satisfies the class probabilities (10) but is not robust
for this perturbation.

######  Theorem 2.

Suppose that $1\geq p_{A}+p_{B}\geq 1-(C-2)\cdot p_{B}$. If the adversarial
perturbations $(\delta,\,\Delta)$ violate (11), then there exists a base
classifier $h^{*}$ such that the smoothed classifer $g^{*}$ is consistent with
the class probabilities (10) and for which
$g^{*}(x+\delta,\,\mathcal{D}+\Delta)\neq y_{A}$.

###### Proof.

We show tightness by constructing a base classifier $h^{*}$, such that the
smoothed classifier is consistent with the class probabilities (10) for a
given (fixed) input $(x_{0},\,\mathcal{D}_{0})$ but whose smoothed version is
not robust for adversarial perturbations $(\delta,\,\Delta)$ that violate
(11). Let $\phi_{A}$ and $\phi_{B}$ be two likelihood ratio tests for testing
the null $Z\sim\mathbb{P}_{0}$ against the alternative
$Z+(\delta,\,\Delta)\sim\mathbb{P}_{1}$ and let $\phi_{A}$ be such that
$\alpha(\phi_{A})=1-p_{A}$ and $\phi_{B}$ such that $\alpha(\phi_{B})=p_{B}$.
Since $(\delta,\,\Delta)$ violates (11), we have that
$\beta(\phi_{A})+\beta(\phi_{B})\leq 1$. Let $p^{*}$ be given by

$\displaystyle
p^{*}(y\lvert\,x,\,\mathcal{D})=\begin{cases}1-\phi_{A}(x-x_{0},\,\mathcal{D}-\mathcal{D}_{0})&\,y=y_{A}\\\
\phi_{B}(x-x_{0},\,\mathcal{D}-\mathcal{D}_{0})&\,y=y_{B}\\\
\frac{1-p^{*}(y_{A}\lvert\,x,\,\mathcal{D})-p(y_{B}\lvert\,x,\,\mathcal{D})}{C-2}&\,\mathrm{o.w.}\end{cases}$
(13)

where the notation $\mathcal{D}-\mathcal{D}_{0}$ denotes subtraction on the
features but not on the labels. Note that for binary classification, $C=2$ we
have that $\phi_{A}=\phi_{B}$ and hence $p^{*}$ is well defined since in this
case, by assumption $p_{A}+p_{B}=1$. If $C>2$, note that it follows
immediately from the definition of $p^{*}$ that
$\sum_{k}p^{*}(y\lvert\,x,\,\mathcal{D})=1$. Note that, from the construction
of $\phi_{A}$ and $\phi_{B}$ in the proof of Theorem 1 (Appendix A) that
(pointwise) $\phi_{A}\geq\phi_{B}$ provided $p_{A}+p_{B}\leq 1$. It follows
that for $y\neq y_{A},\,y_{B}$ we have
$p^{*}(y\lvert\,x,\,\mathcal{D})\propto\phi_{A}-\phi_{B}\geq 0$. Thus, $p^{*}$
is a well defined (conditional) probability distribution over labels and
$h^{*}(x,\,\mathcal{D}):=\arg\max_{y}p^{*}(y\lvert\,x,\,\mathcal{D})$ is a
base classifier. Furthermore, to see that the corresponding smoothed
classifier $q^{*}$ is consistent with the class probabilities (10), consider

$\displaystyle q^{*}(y_{A}\lvert\,x_{0},\,\mathcal{D}_{0})$
$\displaystyle=\mathbb{E}(p^{*}(y_{A}\lvert\,x_{0}+X,\,\mathcal{D}_{0}+D))$
(14) $\displaystyle=\mathbb{E}(1-\phi_{A}(X,\,D))=1-\alpha(\phi_{A})=p_{A}$
(15)

and

$\displaystyle q^{*}(y_{B}\lvert\,x_{0},\,\mathcal{D}_{0})$
$\displaystyle=\mathbb{E}(p^{*}(y_{B}\lvert\,x_{0}+X,\,D_{0}+D))$ (16)
$\displaystyle=\mathbb{E}(\phi_{B}(X,\,D))=\alpha(\phi_{B})=p_{B}.$ (17)

In addition, for any $y\neq y_{A},\,y_{B}$, we have
$q^{*}(y\lvert\,x_{0},\,\mathcal{D}_{0})=(1-p_{A}-p_{B})/(C-2)\leq p_{B}$
since by assumption $p_{A}+p_{B}\geq 1-(C-2)\cdot p_{B}$. Thus, $q^{*}$ is
consistent with the class probabilities (10) In addition, note that
$q^{*}(y_{A}\lvert\,x_{0}+\delta,\,\mathcal{D}_{0}+\Delta)=1-\beta(\phi_{A})$
and
$\beta(\phi_{B})=q^{*}(y_{B}\lvert\,x_{0}+\delta,\,\mathcal{D}_{0}+\Delta)$.
Since by assumption $1-\beta(\phi_{A})<\beta(\phi_{B})$ we see that indeed
$y_{A}\neq g^{*}(x_{0}+\delta,\,\mathcal{D}_{0}+\Delta)$. ∎

##  5 Provable Robustness Against Backdoors

It is not straightforward to use the result from Theorem 1 to get a robustness
certificate against backdoor attacks in terms of $L_{p}$-norm bounded backdoor
patterns. In this section, we aim to answer the question: _how can we
instantiate this result to obtain robustness guarantees against backdoor
attacks?_ In particular, we show that by leveraging Theorem 1, we obtain the
robustness guarantee defined in Section 3. To that end, we derive robustness
bounds for smoothing with isotropic Gaussian noise and we also illustrate how
to derive certification bounds using other smoothing distributions. We will
use isotropic Gaussian noise in our experiments as demonstration and it leads
to a better radius. Intuition. Suppose that we are given a base classifier
which was trained on a _backdoored_ dataset that contains $r$ training samples
infected with backdoor pattern $\delta$. Suppose we know that the smoothed
(backdoored) classifier is confident in predicting a malicious input
$x+\delta$ to be a given class $y_{A}$. Our goal is to derive a condition on
the pattern $\delta$ such that the prediction for $x+\delta$ is the same as
the prediction that a smoothed classifier would have made, had it been trained
on a clean dataset. In other words, we obtain the guarantee that _an attacker
can not achieve their goal of systematically leading the test instance with
the backdoor pattern to the adversarial target_ , meaning they will always
obtain the same prediction as long as the added pattern $\delta$ satisfies
certain conditions (bounded magnitude).

Method Outline. We obtain this certificate by instantiating Theorem 1 in the
following way. Suppose an attacker injects backdoor patterns
$\delta_{i}\in\mathbb{R}^{d}$ to $r\leq n$ training instances of the training
set $\mathcal{D}$. We then train the base classifier on this poisoned dataset
augmented with additional noise on the feature vectors $\mathcal{D}+\Delta+D$,
where $\Delta$ contains all backdoor patterns and $D$ is the smoothing noise
added to training features. We obtain a prediction of the smoothed classifier
$g$ by taking the expectation with respect to the distribution of the
smoothing noise $D$. Suppose that the smoothed classifier obtained in this way
predicts a malicious test instance $x+\delta$ to be of a certain class with
probability at least $p_{A}$ and the runner-up class with probability at most
$p_{B}$. Our result then tells us that, as long as the introduced patterns
satisfy condition (11), we get the guarantee that the malicious test instance
would have been classified equally had the classifier been trained on the
dataset with clean features. In the case where the noise variables are
isotropic Gaussians with standard deviation $\sigma$, the condition (11)
yields a robustness bound in terms of the sum of $L_{2}$-norms of the backdoor
patterns
$\sqrt{\sum_{i}\left\|\delta_{i}\right\|_{2}^{2}}<\frac{\sigma}{2}(\Phi^{-1}(p_{A})-\Phi^{-1}(p_{B}))$
where $\Phi^{-1}$ is the inverse of the standard Gaussian CDF.

######  Corollary 1 (Gaussian Smoothing).

Let $\Delta=(\delta_{1},\,\ldots,\,\delta_{n})$ and $\delta$ be
$\mathbb{R}^{d}$-valued backdoor patterns and let $\mathcal{D}$ be a training
set. Suppose that for each $i$, the smoothing noise on the training features
is iid Gaussian, i.e.
$D^{(i)}\overset{iid}{\sim}\mathcal{N}(0,\,\sigma^{2}\mathds{1}_{d})$. Let
$y_{A}\in\mathcal{C}$ such that $y_{A}=g(x+\delta,\,\mathcal{D}+\Delta)$ with
class probabilities satisfying

$\begin{split}q(y_{A}\lvert\,x+\delta,\,\mathcal{D}+\Delta)&\geq p_{A}\\\
&>p_{B}\geq\max_{y\neq
y_{A}}q(y\lvert\,x+\delta,\,\mathcal{D}+\Delta).\end{split}$ (18)

Then, if the backdoor patterns are bounded by

$\sqrt{\sum_{i=1}^{n}\left\|\delta_{i}\right\|_{2}^{2}}<\frac{\sigma}{2}\left(\Phi^{-1}(p_{A})-\Phi^{-1}(p_{B})\right),$
(19)

it is guaranteed that

$q(y_{A}\lvert\,x+\delta,\,\mathcal{D})>\max_{y\neq
y_{A}}q(y\lvert\,x+\delta,\,\mathcal{D}).$ (20)

This result shows that, whenever the norms of the backdoor patterns is below a
certain value, we obtain the guarantee that the classifier makes the same
prediction on the test data with backdoors as it does when trained without
embeded patterns in the training set.

We can further simplify the robustness bound in (19) if we can assume that an
attacker poisons at most $r\leq n$ training instances with one single pattern
$\delta$. In this case, the bound (19) is given by

$\left\|\delta\right\|_{2}<\frac{\sigma}{2\sqrt{r}}\left(\Phi^{-1}(p_{A})-\Phi^{-1}(p_{B})\right).$
(21)

We thus see that, as we know more about the capabilities of an attacker and
the nature of the backdoor patterns, we are able to certify a larger
robustness radius, proportional to the reciprocal of $\sqrt{r}$.

Discussion: Other Smoothing Distributions. Given the generality of our
framework, it is possible to derive certification bounds using other smoothing
distributions. However, different smoothing distributions have vastly
different performance and a comparative study among different smoothing
distributions are interesting future work. In this paper, we will just
illustrate one example of smoothing using uniform distribution.

######  Corollary 2 (Uniform Smoothing).

Let $\Delta=(\delta_{1},\,\ldots,\,\delta_{n})$ and $\delta$ be
$\mathbb{R}^{d}$ valued backdoor patterns and let $\mathcal{D}$ be a training
set. Suppose that for each $i$, the smoothing noise on the training features
is Uniform, i.e. $D^{(i)}\sim\mathcal{U}([a,\,b])$. Let $y_{A}\in\mathcal{C}$
such that $y_{A}=g(x+\delta,\,\mathcal{D}+\Delta)$ with class probabilities
satisfying

$\begin{split}q(y_{A}\lvert\,x+\delta,\,\mathcal{D}+\Delta)&\geq p_{A}\\\
&>p_{B}\geq\max_{y\neq
y_{A}}q(y\lvert\,x+\delta,\,\mathcal{D}+\Delta).\end{split}$ (22)

Then, if the backdoor patterns are bounded by

$1-\left(\dfrac{p_{A}-p_{B}}{2}\right)<\prod_{i=1}^{n}\left(\prod_{j=1}^{d}\left(1-\dfrac{|\delta_{i,j}|}{b-a}\right)_{+}\right)$
(23)

where $(x)_{+}=\max\\{x,0\\}$, it is guaranteed that

$q(y_{A}\lvert\,x+\delta,\,\mathcal{D})>\max_{y\neq
y_{A}}q(y\lvert\,x+\delta,\,\mathcal{D}).$ (24)

Similar to the Gaussian case, we can simplify the robustness bound in (23), if
we assume that an attacker poisons at most $r\leq n$ training instances with
one single pattern $\delta$. In this case the bound (23) is given by

$1-\left(\dfrac{p_{A}-p_{B}}{2}\right)<\left(\prod_{j=1}^{d}\left(1-\frac{\left|\delta_{j}\right|}{b-a}\right)_{+}\right)^{r}.$
(25)

We see again that, as the number of infected training samples $r$ gets
smaller, this corresponds to a larger bound since the RHS of (25) gets larger.
In other words if we know that the attacker injects fewer backdoors, then we
can certify a backdoor pattern with larger magnitude.

Note that in this paper, we focus on protecting the system against attackers
who hope to trigger a targeted error with a specific backdoor pattern. The
system can still be vulnerable to other types of poisoning attacks. One such
example is the label flipping attack, in which one flips the labels of a
subset of examples while keeping the features untouched. Interestingly, one
concurrent work explored the possibility of using randomized smoothing to
defend against label flipping attack [30]. Developing a single framework to be
robust against both backdoor and label flipping attacks is an exciting future
direction, and we expect it to require non-trivial extensions of both papers
to achieve non-trivial certified accuracy.

##  6 Instantiating the General Framework with Specific ML Models

In previous sections, we presented our provable robustness against backdoor
attacks. Here, we will analyze and provide detailed algorithms for RAB on
three types of machine learning models: deep neural networks, differentially
private deep neural networks and $K$-nearest neighbor classifiers.

The success of backdoor poisoning attacks against DNNs has caused a lot of
attention. Thus, we first aim to evaluate and certify the robustness of DNNs
against backdoor attacks.

Secondly, we aim to understand the properties of models such as “model
smoothness” that could potentially lead to learning robustness. Naturally, the
intuition is that differentially private neural networks are already
“smoothed” on the given training data with the intention of minimizing the
sensitivity of learned models. Our hypothesis is that such smoothed models
will achieve higher certified robustness against backdoor attacks based on our
certifiable process.

Thirdly, given the fact that $K$-NN models have been widely applied in
different applications, either based on raw data or on trained embeddings, it
is of great interest to know about the robustness of this type of ML models.
Specifically, we are inspired by a recent result [17] and develop an exact
efficient smoothing algorithm for $K$-NN models, such that we do not need to
draw a large number of random samples from the smoothing distribution for
these models.

###  6.1 Deep Neural Networks

In this section, we consider smoothed models which use DNNs as base
classifiers. The goal is to calculate the prediction of $g$ on
$(x+\delta,\mathcal{D}+\Delta)$ as in Corollary 1 and the corresponding
certified bound given in the right hand side of (19). In order to evaluate
smoothed DNN classifiers, we proceed in the following way. First, we draw $N$
samples $d_{1},\,\ldots,\,d_{N}$ from the distribution of
$D\sim\prod_{i=1}^{n}\mathcal{N}(0,\,\sigma^{2}\mathds{1}_{d}))$. Given the
$N$ samples of training noise (each consisting of $n$ noise vectors), we train
$N$ DNN models on the datasets $\mathcal{D}+d_{k}$ and obtain classifiers
$h_{1},\,\ldots,\,h_{N}$. The prediction of the smoothed classifier on
$x_{test}$ is then computed by using the empirical mean as an unbiased
estimate:

$\hat{q}(y\lvert\,x,\,\mathcal{D})=\frac{1}{N}\sum_{k=1}^{N}p(y\lvert\,x_{test},\,\mathcal{D}+d_{k}).$
(26)

This is then used to estimate the class probabilities $\hat{p}_{A}$ and
$\hat{p}_{B}$. Finally, for a given error tolerance $\alpha$, we use
Hoeffding’s inequality to compute $p_{A}$ and $p_{B}$ according to

$\displaystyle
p_{A}=\hat{p}_{A}-\sqrt{\frac{\log\nicefrac{{1}}{{\alpha}}}{2\cdot N}}\hskip
10.00002pt\text{and}\hskip
10.00002ptp_{B}=\hat{p}_{B}+\sqrt{\frac{\log\nicefrac{{1}}{{\alpha}}}{2\cdot
N}}$ (27)

However, empirically, we observed that this leads to poor prediction
performance since the ensemble of models $h_{k}$ have to classify an input
that has not been perturbed by Gaussian noise, while $h_{k}$ have only “seen“
noisy samples. In the following, we show a novel way to address this
challenge.

Model-deterministic Test-time Augmentation. One caveat in directly applying
Equation (26) is the mismatch of the training and test distribution — during
training, all examples are perturbed with sampled noise whereas the test
example is without noise. In practice, we see that this mismatch significantly
decreases the test accuracy (see Appendix D). One natural idea is to also add
noise to the test examples, however, this requires careful design (e.g.,
simply drawing $k$ independent noise vectors and apply them to Equation (26)
will cause problems in theory and leads to a loose bound).

We modify the inference function given a learned model $h_{k}$ in the
following way. Instead of directly classifying an unperturbed input
$x_{test}$, we use the hash value of the trained $h_{k}$ model parameters as
the random seed and sample
$u_{k}\sim\mathcal{N}_{hash(h_{k})}(0,\sigma^{2}{\mathds{1}_{d}})$. In
practice, we use SHA256 hashing[34] of the trained model file. In this way,
the noise we add is a deterministic function of the trained model, which is
equivalent of altering the inference function in a deterministic way:
$\tilde{h}_{k}(x_{test})=h_{k}(x_{test}+u_{k})$. We show in the experiments
that this leads to significantly better prediction performance in practice.
Pseudocode for our proposed DNN-RAB training procedure is shown in Algorithm
1.

0: (Backdoored) Training dataset $\mathcal{D}=\\{(x_{i},y_{i})_{i=1}^{n}\\}$,
test data $x_{test}$, noise scale $\sigma$, model number $N$, error rate
$\alpha$. /* Train models using smoothed dataset. */

1: for $k=1,\ldots,N$ do

2: Sample
$d_{k,1},\ldots,d_{k,n}\overset{\mathrm{iid}}{\sim}\mathcal{N}(0,\sigma^{2}\mathds{1}_{d})$.

3: $\mathcal{D}_{k}=\\{(x_{i}+d_{k,i},y_{i})_{i=1}^{n}\\}$.

4: $h_{k}=\texttt{train\\_model}(\mathcal{D}_{k})$.

5: $u_{k}=\mathcal{N}_{hash(h_{k})}(0,\sigma^{2}{\mathds{1}_{d}})$.

6: end for/* Calculate the empirical estimation of $p_{A}$ and $p_{B}$. */

7: $\hat{g}=\frac{1}{N}\sum_{k=1}^{N}h_{k}(x_{test}+u_{k})$.

8: $\hat{p}_{A},y_{A}=\max_{y}\hat{g}(y),\arg\max_{y}\hat{g}(y)$.

9: $\hat{p}_{B}=\max_{y\neq y_{A}}\hat{g}(y)$. /* Calculate lower bound of
$p_{A}$, upper bound of $p_{B}$. */

10:
$p_{A},p_{B}=\texttt{calculate\\_bound}(\hat{p}_{A},\hat{p}_{B},N,\alpha)$.

11: if $p_{A}>p_{B}$ then

12: $R=\frac{\sigma}{2}\left(\Phi^{-1}(p_{A})-\Phi^{-1}(p_{B})\right)$

13: return prediction $y_{A}$, robust radius $R$.

14: else

15: return ABSTAIN

16: end if

Algorithm 1 DNN-RAB algorithm for estimating the prediction and robust radius
of smoothed DNN classifiers.

###  6.2 Differentially Private DNN Models

Based on the intuition that a “smoothed” model is expected to be more robust
against attacks, in this section we provide a way to explore this assumption
and further provide guidance on how to improve the certified robustness of
machine learning models against backdoor attacks.

In the proposed RAB training procedure, we directly smooth the training
process by adding smoothing noise $d_{k}=(d_{k}^{1},\,\ldots,\,d_{k}^{(n)})$
sampled from $D=(D^{(1)},\,\ldots,\,D^{(n)})$ at each time and then train a
corresponding model as shown in Figure 2. The _k_ -th trained model can be
represented as

$\theta_{k}=\arg\min_{\theta}\sum_{i=1}^{n}\ell(h_{\theta}(x_{i}+d_{k}^{(i)}),\,y_{i}).$
(28)

To assess the effects of the model smoothness on the certified robustness
bound, we improve the model training process with differentially private
stochastic gradient descent (DP-SGD) [1]. During each iteration of training
the model $h_{k}$, we add noise to the gradient to reduce its dependency on
specific training data and then clip the gradient to a predefined range.
Intuitively, this process will add another level of “smoothness” to the model
training which is encoded in the model parameters $\theta_{k}$. The hypothesis
is that this procedure will lead to a larger gap between $p_{A}$ and $p_{B}$
and therefore provide a higher certified robustness. Note that DP-SGD is just
one way to provide a smoothed model training process we explore here. We
remark that our approach is flexible in that it enables plugging in any other
smoothing strategy to the proposed RAB framework with the goal of enhancing
the learning robustness against backdoor attacks.

###  6.3 K-Nearest Neighbors

If the base classifier $h$ is given by a $K$-nearest neighbor classifier, we
can evaluate the corresponding smoothed classifier analytically and thus
compute the confidence levels $p_{A}$ and $p_{B}$ exactly, opposed to the
approximation needed in the case for other types of base classifiers. In what
follows, we show that this computation can be performed with time complexity
polynomial in the number of training instances, where the smoothing
distribution is given by isotropic Gaussian.

A $K$-NN classifier works in the following way: Given a training set
$\mathcal{D}=\\{(x_{i},\,y_{i})_{i=1}^{n}\\}$ and a test example $x$, we first
calculate the similarity between $x$ and each $x_{i}$,
$s_{i}:=\kappa(x_{i},\,x)$ where $\kappa$ is a similarity function. Given all
these similarity scores $\\{s_{i}\\}_{i}$, we choose the $K$ most similar
training examples with the largest similarity score
$\\{x_{\sigma_{i}}\\}_{i=1}^{K}$ along with corresponding labels
$\\{y_{\sigma_{i}}\\}_{i=1}^{K}$. The prediction is then made according to a
majority vote among the top-$K$ labels.

Similar to DNNs, we obtain a smoothed $K$-NN classifier by adding Gaussian
noise to training points and evaluate the expectation with respect to this
noise distribution

$q(y\lvert\,x,\,\mathcal{D})=\mathbb{P}\left(\text{$K$-NN}(x,\,\mathcal{D}+D)=y\right)$
(29)

where
$D=(D^{(1)},\,\ldots,\,D^{(n)})\sim\prod_{i=1}^{n}\mathcal{N}(0,\,\sigma^{2}\mathds{1}_{d})$.
The next theorem shows that (29) can be computed exactly and efficiently when
we measure similarity with respect to euclidean distance quantized into finite
similarity levels.

######  Theorem 3.

Given $n$ training instances, a $C$-multiclass $K$-NN classifier based on
quantized euclidean distance with $L$ similarity levels, smoothed with
isotropic Gaussian noise can be evaluated exactly with time complexity
$\mathcal{O}(K^{2+C}\cdot n^{2}\cdot L\cdot C)$.

###### Proof (sketch).

The first step to computing (29) is to notice that we can summarize all
possible arrangements $\\{x_{\sigma_{i}}+D^{(\sigma_{i})}\\}_{i=1}^{K}$ of
top-$K$ instances leading to a prediction by using tally vectors
$\gamma\in[K]^{C}$. A tally vector has as its $k$-th element the number of
instances in the top-$K$ with label $k$,
$\gamma_{k}=\\#\\{y_{\sigma_{i}}=k\\}$. In the second step, we partition the
event that a tally vector $\gamma$ occurs into events where an instance $i$
with similarity $\beta$ is in the top-$K$ but would not be in the top-$(K-1)$.
These first two steps result in a summation over $\mathcal{O}(K^{C}\cdot
n\cdot L\cdot C)$ many terms. In the last step, we compute the probabilities
of the events
$\\{\mathrm{tally}\,\gamma\,\land\,\kappa(x_{i}+D^{(i)},\,x)=\beta\\}$ with
dynamic programming in $\mathcal{O}(n\cdot K^{2})$ steps, resulting in a final
time complexity of $\mathcal{O}(K^{2+C}\cdot n^{2}\cdot L\cdot C)$. ∎

If $K=1$, an efficient algorithm can even achieve time complexity linear in
the number of training samples $n$. We refer the reader to Appendix C for a
detailed proof of Theorem 3 and the algorithm details.

Table 1: Evaluation metrics for test set of size $m$ Prediction Acc | Certified Rate at radius $R$ | Certified Acc at radius $R$
---|---|---
$\frac{1}{m}\sum_{i=1}^{m}\mathds{1}\\{\hat{y}_{i}=y_{i}\\}$ | $\frac{1}{m}\sum_{i=1}^{m}\mathds{1}\\{R_{i}>R\\}$ | $\frac{1}{m}\sum_{i=1}^{m}\mathds{1}\\{\hat{y}_{i}=y_{i}\text{ and }R_{i}>R\\}$
Table 2: Experiment results with DNNs on different datasets. For each dataset,
different attack settings (i.e. patterns with bounded $L_{2}$ norm and
different backdoor ratios) and smoothing strategies (i.e. different noise
variance $\sigma$) have been employed.

MNIST | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.2/0.5/1.0/2.0$ | Certified Rate at $R=0.2/0.5/1.0/2.0$
---|---|---|---|---|---|---
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 1.000 | 0.996 / 0.796 / 0.000 / 0.000 | 0.996 / 0.796 / 0.000 / 0.000
2.0 | 0.995 | 0.995 / 0.991 / 0.744 / 0.000 | 0.995 / 0.991 / 0.744 / 0.000
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 1.000 | 1.000 / 1.000 / 0.986 / 0.000 | 1.000 / 1.000 / 0.986 / 0.000
2.0 | 1.000 | 0.999 / 0.998 / 0.993 / 0.708 | 0.999 / 0.998 / 0.993 / 0.708
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 1.000 | 0.997 / 0.530 / 0.000 / 0.000 | 0.997 / 0.530 / 0.000 / 0.000
2.0 | 0.996 | 0.994 / 0.987 / 0.640 / 0.000 | 0.994 / 0.987 / 0.640 / 0.000
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 1.000 | 1.000 / 1.000 / 0.990 / 0.000 | 1.000 / 1.000 / 0.990 / 0.000
2.0 | 1.000 | 0.999 / 0.998 / 0.993 / 0.725 | 0.999 / 0.998 / 0.993 / 0.725
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 1.000 | 1.000 / 0.985 / 0.000 / 0.000 | 1.000 / 0.985 / 0.000 / 0.000
2.0 | 0.997 | 0.995 / 0.991 / 0.744 / 0.000 | 0.995 / 0.991 / 0.744 / 0.000
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 1.000 | 1.000 / 1.000 / 0.992 / 0.000 | 1.000 / 1.000 / 0.992 / 0.000
2.0 | 1.000 | 0.999 / 0.997 / 0.993 / 0.728 | 0.999 / 0.997 / 0.993 / 0.728
CIFAR | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.733 | 0.683 / 0.615 / 0.389 / 0.000 | 0.811 / 0.717 / 0.455 / 0.005
1.0 | 0.656 | 0.624 / 0.588 / 0.487 / 0.085 | 0.789 / 0.741 / 0.604 / 0.137
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.833 | 0.805 / 0.770 / 0.687 / 0.295 | 0.892 / 0.846 / 0.735 / 0.298
1.0 | 0.790 | 0.768 / 0.749 / 0.714 / 0.555 | 0.880 / 0.847 / 0.796 / 0.593
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.737 | 0.685 / 0.618 / 0.423 / 0.000 | 0.805 / 0.710 / 0.485 / 0.005
1.0 | 0.656 | 0.617 / 0.585 / 0.490 / 0.090 | 0.790 / 0.735 / 0.612 / 0.145
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.838 | 0.808 / 0.775 / 0.696 / 0.284 | 0.892 / 0.847 / 0.741 / 0.287
1.0 | 0.794 | 0.768 / 0.746 / 0.702 / 0.546 | 0.883 / 0.848 / 0.785 / 0.585
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.736 | 0.669 / 0.599 / 0.376 / 0.000 | 0.797 / 0.702 / 0.444 / 0.006
1.0 | 0.662 | 0.622 / 0.595 / 0.498 / 0.133 | 0.792 / 0.748 / 0.617 / 0.193
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.834 | 0.809 / 0.774 / 0.699 / 0.284 | 0.889 / 0.842 / 0.741 / 0.288
1.0 | 0.798 | 0.770 / 0.754 / 0.712 / 0.550 | 0.885 / 0.858 / 0.793 / 0.588
ImageNet | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.781 | 0.718 / 0.656 / 0.424 / 0.000 | 0.758 / 0.688 / 0.439 / 0.000
1.0 | 0.604 | 0.562 / 0.519 / 0.424 / 0.104 | 0.635 / 0.578 / 0.463 / 0.120
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.907 | 0.887 / 0.864 / 0.810 / 0.230 | 0.905 / 0.880 / 0.818 / 0.230
1.0 | 0.816 | 0.796 / 0.775 / 0.740 / 0.580 | 0.828 / 0.804 / 0.761 / 0.588
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.791 | 0.742 / 0.664 / 0.407 / 0.000 | 0.779 / 0.691 / 0.424 / 0.000
1.0 | 0.630 | 0.596 / 0.560 / 0.466 / 0.120 | 0.656 / 0.612 / 0.502 / 0.132
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.910 | 0.894 / 0.869 / 0.808 / 0.200 | 0.914 / 0.886 / 0.818 / 0.200
1.0 | 0.808 | 0.792 / 0.768 / 0.724 / 0.574 | 0.829 / 0.799 / 0.747 / 0.580
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.774 | 0.716 / 0.639 / 0.386 / 0.000 | 0.755 / 0.666 / 0.403 / 0.000
1.0 | 0.600 | 0.564 / 0.523 / 0.440 / 0.114 | 0.632 / 0.583 / 0.484 / 0.129
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.906 | 0.888 / 0.865 / 0.810 / 0.272 | 0.907 / 0.878 / 0.819 / 0.272
1.0 | 0.811 | 0.792 / 0.776 / 0.732 / 0.571 | 0.826 / 0.808 / 0.755 / 0.577

Table 3: Experiment results for smoothed DNN models trained with DP-SGD.

MNIST | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.2/0.5/1.0/2.0$ | Certified Rate at $R=0.2/0.5/1.0/2.0$
---|---|---|---|---|---|---
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.997 | 0.995 / 0.991 / 0.904 / 0.000 | 0.997 / 0.991 / 0.904 / 0.000
2.0 | 0.996 | 0.995 / 0.992 / 0.948 / 0.265 | 0.996 / 0.992 / 0.948 / 0.265
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.998 | 0.998 / 0.997 / 0.981 / 0.000 | 0.998 / 0.997 / 0.981 / 0.000
2.0 | 0.998 | 0.998 / 0.997 / 0.994 / 0.833 | 0.998 / 0.997 / 0.994 / 0.833
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.997 | 0.994 / 0.985 / 0.848 / 0.000 | 0.996 / 0.985 / 0.848 / 0.000
2.0 | 0.995 | 0.994 / 0.988 / 0.936 / 0.176 | 0.996 / 0.988 / 0.936 / 0.176
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.998 | 0.998 / 0.997 / 0.982 / 0.000 | 0.998 / 0.997 / 0.982 / 0.000
2.0 | 0.998 | 0.998 / 0.997 / 0.993 / 0.793 | 0.998 / 0.997 / 0.993 / 0.793
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.998 | 0.997 / 0.994 / 0.925 / 0.000 | 0.997 / 0.994 / 0.925 / 0.000
2.0 | 0.997 | 0.995 / 0.993 / 0.957 / 0.317 | 0.995 / 0.993 / 0.957 / 0.317
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.998 | 0.998 / 0.997 / 0.979 / 0.000 | 0.998 / 0.997 / 0.979 / 0.000
2.0 | 0.998 | 0.998 / 0.997 / 0.994 / 0.820 | 0.998 / 0.997 / 0.994 / 0.820
CIFAR | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.479 | 0.365 / 0.251 / 0.082 / 0.000 | 0.578 / 0.410 / 0.174 / 0.005
1.0 | 0.305 | 0.239 / 0.192 / 0.105 / 0.004 | 0.512 / 0.432 / 0.267 / 0.044
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.728 | 0.675 / 0.612 / 0.440 / 0.003 | 0.799 / 0.719 / 0.497 / 0.004
1.0 | 0.649 | 0.609 / 0.575 / 0.484 / 0.204 | 0.754 / 0.700 / 0.580 / 0.228
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.466 | 0.344 / 0.222 / 0.057 / 0.000 | 0.555 / 0.375 / 0.141 / 0.003
1.0 | 0.292 | 0.225 / 0.170 / 0.088 / 0.002 | 0.491 / 0.405 / 0.244 / 0.037
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.725 | 0.673 / 0.612 / 0.457 / 0.006 | 0.795 / 0.719 / 0.514 / 0.007
1.0 | 0.643 | 0.602 / 0.570 / 0.471 / 0.189 | 0.753 / 0.698 / 0.569 / 0.213
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.471 | 0.361 / 0.239 / 0.072 / 0.000 | 0.580 / 0.400 / 0.163 / 0.005
1.0 | 0.321 | 0.262 / 0.210 / 0.129 / 0.007 | 0.536 / 0.452 / 0.297 / 0.055
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.724 | 0.673 / 0.613 / 0.444 / 0.002 | 0.795 / 0.718 / 0.501 / 0.003
1.0 | 0.647 | 0.607 / 0.570 / 0.475 / 0.188 | 0.750 / 0.693 / 0.569 / 0.209
ImageNet | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.405 | 0.317 / 0.237 / 0.116 / 0.000 | 0.403 / 0.292 / 0.134 / 0.000
1.0 | 0.101 | 0.072 / 0.054 / 0.022 / 0.000 | 0.218 / 0.156 / 0.073 / 0.002
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.698 | 0.641 / 0.580 / 0.445 / 0.028 | 0.685 / 0.609 / 0.459 / 0.028
1.0 | 0.376 | 0.333 / 0.276 / 0.195 / 0.037 | 0.392 / 0.319 / 0.218 / 0.038
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.408 | 0.318 / 0.246 / 0.115 / 0.000 | 0.402 / 0.300 / 0.133 / 0.000
1.0 | 0.103 | 0.071 / 0.053 / 0.020 / 0.000 | 0.211 / 0.157 / 0.068 / 0.002
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.697 | 0.638 / 0.579 / 0.444 / 0.028 | 0.680 / 0.608 / 0.458 / 0.028
1.0 | 0.377 | 0.324 / 0.280 / 0.197 / 0.041 | 0.384 / 0.325 / 0.220 / 0.042
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.397 | 0.318 / 0.232 / 0.113 / 0.000 | 0.403 / 0.286 / 0.131 / 0.000
1.0 | 0.097 | 0.070 / 0.052 / 0.021 / 0.000 | 0.215 / 0.160 / 0.071 / 0.002
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.701 | 0.644 / 0.580 / 0.444 / 0.029 | 0.687 / 0.609 / 0.457 / 0.029
1.0 | 0.379 | 0.332 / 0.281 / 0.197 / 0.042 | 0.392 / 0.324 / 0.220 / 0.042

Table 4: Experiment results for KNN ($K=5$).

MNIST | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.2/0.5/1.0/2.0$ | Certified Rate at $R=0.2/0.5/1.0/2.0$
---|---|---|---|---|---|---
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 1.000 | 1.000 / 1.000 / 1.000 / 0.000 | 1.000 / 1.000 / 1.000 / 0.000
1.0 | 1.000 | 1.000 / 0.999 / 0.995 / 0.552 | 1.000 / 0.999 / 0.995 / 0.552
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 1.000 | 1.000 / 1.000 / 1.000 / 1.000 | 1.000 / 1.000 / 1.000 / 1.000
1.0 | 1.000 | 1.000 / 1.000 / 1.000 / 0.995 | 1.000 / 1.000 / 1.000 / 0.995
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 1.000 | 1.000 / 1.000 / 1.000 / 0.000 | 1.000 / 1.000 / 1.000 / 0.000
1.0 | 1.000 | 1.000 / 0.999 / 0.995 / 0.483 | 1.000 / 0.999 / 0.995 / 0.483
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 1.000 | 1.000 / 1.000 / 1.000 / 1.000 | 1.000 / 1.000 / 1.000 / 1.000
1.0 | 1.000 | 1.000 / 1.000 / 1.000 / 0.995 | 1.000 / 1.000 / 1.000 / 0.995
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 1.000 | 1.000 / 1.000 / 1.000 / 0.000 | 1.000 / 1.000 / 1.000 / 0.000
1.0 | 1.000 | 1.000 / 1.000 / 0.995 / 0.690 | 1.000 / 1.000 / 0.995 / 0.690
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 1.000 | 1.000 / 1.000 / 1.000 / 1.000 | 1.000 / 1.000 / 1.000 / 1.000
1.0 | 1.000 | 1.000 / 1.000 / 1.000 / 0.995 | 1.000 / 1.000 / 1.000 / 0.995
CIFAR | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.659 | 0.621 / 0.581 / 0.498 / 0.229 | 0.930 / 0.858 / 0.740 / 0.380
1.0 | 0.554 | 0.537 / 0.518 / 0.467 / 0.283 | 0.962 / 0.918 / 0.822 / 0.535
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.764 | 0.747 / 0.736 / 0.694 / 0.535 | 0.964 / 0.931 / 0.866 / 0.645
1.0 | 0.723 | 0.711 / 0.698 / 0.670 / 0.552 | 0.976 / 0.947 / 0.905 / 0.724
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.653 | 0.620 / 0.594 / 0.502 / 0.240 | 0.931 / 0.877 / 0.751 / 0.388
1.0 | 0.560 | 0.540 / 0.510 / 0.465 / 0.268 | 0.953 / 0.906 / 0.813 / 0.511
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.771 | 0.750 / 0.737 / 0.701 / 0.534 | 0.963 / 0.938 / 0.870 / 0.641
1.0 | 0.718 | 0.708 / 0.696 / 0.664 / 0.549 | 0.973 / 0.947 / 0.899 / 0.725
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.646 | 0.606 / 0.551 / 0.461 / 0.231 | 0.927 / 0.845 / 0.720 / 0.386
1.0 | 0.567 | 0.548 / 0.519 / 0.477 / 0.289 | 0.967 / 0.918 / 0.831 / 0.538
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.772 | 0.746 / 0.736 / 0.704 / 0.539 | 0.958 / 0.935 / 0.878 / 0.648
1.0 | 0.714 | 0.702 / 0.691 / 0.654 / 0.544 | 0.976 / 0.952 / 0.892 / 0.723
Spam | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5/1.0$ | Certified Rate at $R=0.05/0.1/0.2/0.5/1.0$
One-dimension | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.709 | 0.686 / 0.668 / 0.603 / 0.400 | 0.962 / 0.928 / 0.838 / 0.554
2.0 | 0.512 | 0.478 / 0.434 / 0.323 / 0.120 | 0.932 / 0.861 / 0.676 / 0.340
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.856 | 0.842 / 0.834 / 0.806 / 0.744 | 0.977 / 0.956 / 0.907 / 0.800
2.0 | 0.913 | 0.905 / 0.895 / 0.862 / 0.757 | 0.985 / 0.966 / 0.905 / 0.761
Four-dimension | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.691 | 0.668 / 0.642 / 0.587 / 0.429 | 0.953 / 0.920 / 0.831 / 0.598
2.0 | 0.485 | 0.456 / 0.409 / 0.296 / 0.118 | 0.940 / 0.858 / 0.695 / 0.364
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.852 | 0.839 / 0.832 / 0.805 / 0.744 | 0.975 / 0.955 / 0.907 / 0.802
2.0 | 0.913 | 0.905 / 0.895 / 0.864 / 0.758 | 0.985 / 0.964 / 0.902 / 0.762
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.710 | 0.694 / 0.663 / 0.596 / 0.437 | 0.966 / 0.917 / 0.829 / 0.574
2.0 | 0.550 | 0.516 / 0.483 / 0.414 / 0.167 | 0.937 / 0.881 / 0.749 / 0.381
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.857 | 0.843 / 0.834 / 0.809 / 0.747 | 0.971 / 0.955 / 0.910 / 0.802
2.0 | 0.914 | 0.905 / 0.897 / 0.868 / 0.760 | 0.980 / 0.964 / 0.906 / 0.763

##  7 Experimental Results

In this section, we present extensive experiments to provide a benchmark for
the certified robustness bound of different types of machine learning models
on diverse datasets. In particular, we evaluate DNNs, differentially private
DNNs, and $K$-NN on MNIST, CIFAR-10, and ImageNet. We consider three different
types of backdoor patterns, namely one pixel, four pixel, and blending
attacks. We also evaluate a $K$-NN model on a tabular data spambase dataset to
assess the advantages of our efficient algorithm for $K$-NN classifiers.

###  7.1 Experiment Setup

We evaluate RAB for certifying robustness against backdoor attacks on
different ML models on MNIST [19], CIFAR-10 [18] and ImageNet [11] datasets,
with a focus on binary classifiers. Following the backdoor attack setting as
in [31, 8], we train a DNN model to classify between the (source, target)
label pairs on each task. The goal of the attacker is to inject a backdoor
pattern during training such that a source input infected with the pattern
will be classified as the adversarial target. We randomly choose two pairs for
each task, and report the results for pair (0,1) on MNIST, (airplane, bird) on
CIFAR, and (cat, dog) on ImageNet in the paper. We include the results of
other pairs in Appendix D. The training set sizes for the three tasks are
12,665, 10,000 and 20,000 for MNIST, CIFAR and ImageNet respectively. We use
the CNN architecture in [15] on MNIST and the ResNet used in [10] on CIFAR-10.
For ImageNet, we use the standard ResNet-20.

We evaluate three representative backdoor patterns: a one-pixel pattern in the
middle of the image, a four-pixel pattern, and blending a random noise pattern
to the entire image (the noise pattern is fixed and visualized in Appendix D).
We change the L2-norm of the backdoor patterns to control their magnitude. We
visualize all backdoor patterns together with the certified results in Table
2-4. For each attack, we add $r_{p}$ backdoor training instances whose ground
truth is the source class aiming to mislead the prediction of test instances
with the pattern to the adversarial target. We show the accuracy of regular
models (without randomized smoothing) trained on these datasets in the
Appendix in Table D.6.

In order to estimate $p_{A}$ and $p_{B}$ for DNN base classifiers, we train
$N=1,000$ smoothed models on MNIST and CIFAR, and $N=200$ smoothed models on
ImageNet according to the pseudocode in Figure 1. We then use Hoeffding’s
inequality to approximate the bounds with an error rate of $\alpha=0.001$. We
use the smoothing parameters $\sigma=1.0,2.0$ on MNIST and $\sigma=0.5,1.0$ on
CIFAR and ImageNet.

Besides the vanilla DNNs, we also use the differentially private training
algorithm (DP-SGD) proposed in [1] with the goal of further smoothing a
trained model on the instance level. We set the gradient clip norm to be
$C=5.0,100.0,1000.0$ and add Gaussian noise with scale
$\sigma_{DP}=4.0,0.1,0.01$ in the gradient calculation for MNIST, CIFAR and
ImageNet, respectively. In the $K$-NN approach, we use $L=200$ buckets.

As for the $K$-NN models, besides the image datasets we evaluate it with an
additional spambase tabular dataset in order to demonstrate its effectiveness.
In particular, we use the UCI Spambase dataset [12] which gives bag-of-word
feature vectors on e-mails and determines whether the message is spam or not.
The dataset contains 4,601 data cases with a 57-dimensional input. We use 80%
of the data as training set to fit the $K$-NN model and the remaining 20% for
evaluation.

We report our results with three metrics: prediction accuracy, certified rate
and certified accuracy. Given the $i$-th test case with ground truth label
$y_{i}$, the output prediction is either $\hat{y}_{i}$ within radius $R_{i}$
or $\hat{y}_{i}=\text{ABSTAIN}$. Given a test set of size $m$, the three
evaluation metrics are calculated according to the evaluation metrics defined
in Table 1. The prediction accuracy indicates how well the smoothed
(backdoored) classifier performs in classifying new, possibly backdoored,
instances without taking into account their robustness radius. The certified
rate at radius $R$ is given by the fraction of instances in the test set that
can be certified with radius $R_{i}>R$, indicating how consistent the attacked
classifier is with a clean one. Finally, the certified accuracy at $R$
combines the first two metrics: it reports the fraction of the test set which
is classified consistently correct (without abstaining) with a radius
$R_{i}>R$.

###  7.2 Certified robustness of DNNs against backdoor attacks

We evaluate the certified robustness bound on DNNs against different backdoor
patterns, and we present the results for three evaluation metrics. Table 2
lists the benchmark results on MNIST, CIFAR-10 and ImageNet, respectively.
From the results, we can see that on MNIST, it is possible to obtain certified
accuracy around 99.6% as long as the $L_{2}$ norm of the backdoor patterns is
within 0.5, and drops to around 70% as the radius increases (e.g.
$\left\|\delta\right\|_{2}=2)$. It can also be seen that larger smoothing
noise during RAB training helps to achieve higher certified accuracy and
certified rate. Similar observations can be drawn for CIFAR-10 and ImageNet,
while the certified robustness is lower than on MNIST.

###  7.3 Certified robustness of differentially private DNNs

In addition to vanilla DNNs, we provide the certified robustness benchmarks on
differentially private trained DNNs. Table 3 shows the results on MNIST,
CIFAR-10 and ImageNet. We can see that on MNIST, the certified robustness on
such smoothly trained models is much higher than that of vanilla DNNs. This
provides further guidance on improving the robustness of ML models against
backdoor attacks. On ImageNet and CIFAR-10, however, we do not observe
significantly improved certified robustness compared to vanilla DNNs. We
expect further improvements on DP-SGD will help to improve the certified
robustness since it is known that DP-SGD is challenging to be applied on these
datasets.

###  7.4 Certified robustness of K-NN models

In this section, we present the benchmarks based on our proposed efficient
algorithm for $K$-NN models without requiring to sample from the smoothing
noise distribution. We perform experiments on the MNIST, CIFAR-10 and UCI
spambase datasets and show the results for $K=5$ in Table 4. We can see that
the $K$-NN models on MNIST and CIFAR-10 achieve better certified rate and
accuracy and we can certify a large radius. In addition, the $K$-NN model
achieves high certified accuracy and certified rate on tabular data, which
indicates its advantages for specific domains. In terms of the efficiency
evaluation, we record the runtime of the proposed efficient _exact_ algorithm
for K-NN. We observe that for certifying one input from CIFAR-10 on $K$-NN
($K=5$), using the exact algorithm takes only 60 seconds, which is around 6-7
times faster than the vanilla RAB. It would be interesting future work to
design similar efficient algorithms for DNNs.

###  7.5 Ablation Studies

Here, we investigate additional properties of the RAB training process, namely
the effect of the training set size, the certified accuracy as a function of
the robust radius and certifying the robustness for 10-way classification.
Fig. 3 shows the certified accuracy on different datasets when different
portions of the original training data is used by RAB. It is clear that more
training data helps to improve the certified accuracy. We observe that this
effect is less pronounced when the radius of the backdoor patterns is small.
In Fig. 4, the certified accuracy is shown as a function of the certified
radius for varying smoothing noise variance. We can see that increasing the
variance leads to higher certifiable robust radii. Furthermore, the figure
shows that ImageNet is more sensitive to this backdoor attack than MNIST. In
addition to the binary classifiers, we also evaluate the certified robustness
for 10-way classifiers with the same source-target pairs used for the backdoor
attack, shown in Table 5. We can see that the certified accuracy is slightly
lower than in the binary case since the 10-way classification is a more
challenging task. We also note that a smaller $\sigma$ helps to improve the
robustness.

Figure 3: Certified accuracy for the four-pixel attack with
$||\delta||_{2}=0.1$ and $r_{p}=0.02$ when we train the model using only a
proportion of the dataset. Figure 4: Certified accuracy at different radii for
the four-pixel attack with $||\delta||_{2}=0.1$ and $r_{p}=0.02$. Table 5:
Experiment results on 10-way Classification with DNN.

MNIST | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.2/0.5/1.0/2.0$ | Certified Rate at $R=0.2/0.5/1.0/2.0$
---|---|---|---|---|---|---
Four-pixel | $\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.990 | 0.977 / 0.918 / 0.000 / 0.000 | 0.979 / 0.918 / 0.000 / 0.000
1.0 | 0.961 | 0.931 / 0.843 / 0.504 / 0.000 | 0.937 / 0.844 / 0.504 / 0.000
2.0 | 0.701 | 0.568 / 0.383 / 0.144 / 0.000 | 0.575 / 0.384 / 0.144 / 0.000
CIFAR | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
Four-pixel | $\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.25 | 0.675 | 0.578/ 0.471 / 0.274 / 0.000 | 0.636 / 0.497 / 0.278 / 0.000
0.5 | 0.534 | 0.465 / 0.403 / 0.287 / 0.063 | 0.568 / 0.462 / 0.309 / 0.064
1.0 | 0.343 | 0.302 / 0.267 / 0.202 / 0.068 | 0.410 / 0.346 / 0.246 / 0.074

##  8 Related Work

In this section, we discuss current backdoor (poisoning) attacks on machine
learning models and existing defenses.

Backdoor attacks. There have been several works developing optimal poisoning
attacks against machine learning models such as SVM and logistic regression
[3, 21]. Furthermore, [28] proposes a similar optimization based poisoning
attack against neural networks, that can only be applied to shallow MLP
models. In addition to these optimization based poisoning attacks, the
backdoor attacks are shown to be very effective against deep neural networks
[8, 15]. The backdoor patterns can be either static or generated dynamically
[37]. Static backdoor patterns can be as small as one pixel, or as large as an
entire image [8].

Potential defenses against backdoor attacks. Given the potential severe
consequences caused by backdoor attacks, multiple defense approaches have been
proposed. Cleanse [33] proposes to detect the backdoored models based on the
observation that there exists a “short path” to make an instance to be
predicted as a malicious one. [7] improves upon the approach by using model
inversion to obtain training data, and then apply GANs to generate the “short
path” and apply anomaly detection algorithm as in Neural Cleanse. Activation
Clustering [6] leverages the activation vectors from the backdoored model as
features to detect backdoor instances. Spectral Signature [31] identifies the
“spectral signature” in the activation vector for backdoored instances. STRIP
[13] proposes to identify the backdoor instances by checking whether the model
will still provide a confident answer when it sees the backdoor pattern.
SentiNet [9] leverages computer vision techniques to search for the parts in
the image that contribute the most to the model output, which are very likely
to be the backdoor pattern. In [26], differential privacy has been leveraged
as a defense against poisoning attacks. Note that RAB would not guarantee the
trained models are differentially private, though they both aim to decrease
the model sensitivity intuitively. Finally, another interesting application of
randomized smoothing is presented in [30] to certify robustness against label-
flipping attacks and randomize over the entire training procedure of the
classifier by randomly flipping labels in the training set. This work is
orthogonal to ours in that we investigate the robustness with respect to
perturbations on the training inputs rather than labels. In addition to these
works aiming to certify the robustness for a single model, [40] provides a new
way to certify the robustness of an end to end sensing-reasoning pipeline.

Recently, a technical report also proposes to directly apply the randomized
smoothing technique to certify robustness against backdoor attacks without any
evaluation or analysis [32]. In addition, as we have shown, directly applying
randomized smoothing will not provide high certified robustness bounds.
Contrary to that, in this paper, we first provide the unified framework with
smoothing functional, and then propose the RAB robust training process to
provide certified robustness against backdoor attacks based on the framework.
We provide the tightness analysis for the robustness bound, analyze different
smoothing distributions, and propose the hash function based model
deterministic test-time augmentation approach to achieve good certified
robustness. In addition, we analyze different machine learning models with
corresponding properties such as model smoothness to provide guidance to
further improve the certified model robustness.

##  9 Conclusion and Discussion

In this paper, we aim to propose a unified smoothing framework to certify
model robustness against different attacks. In particular, towards the popular
backdoor poisoning attack, we propose the first robust smoothing pipeline RAB
as well as a _model deterministic test-time augmentation_ mechanism to certify
the prediction robustness against diverse backdoor attacks. In particular, we
evaluate our certified robustness against backdoors on vanilla DNNs,
differentially private smoothed DNNs, and $K$-NN models. In addition, we
propose an exact algorithm for $K$-NN models without requiring to sample from
the smoothing noise distributions. We provide comprehensive benchmarks of
certified model robustness against backdoors on diverse datasets with a focus
on binary classifiers, which we believe will provide the _first set_ of model
robustness against backdoor attacks for future work to compare with.

Our approach is in general computationally expensive, since it requires the
training of a large number of models on the smoothed datasets. In particular,
training DNNs from scratch on large scale datasets with hundreds of classes
and millions of training instances quickly becomes prohibitively expensive.
One way to mitigate this issue is to make use of pretrained classifiers which
are assumed to be clean. One could then use RAB training to finetune on a
smaller dataset and obtain a robustness guarantee. In addition, as we have
shown for $K$-NN classifiers, it is possible to efficiently evaluate the
smoothed classifier by exploiting the structure of the underlying model.

## References

  * [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016.
  * [2] Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  arXiv preprint arXiv:1802.00420, 2018.
  * [3] Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning attacks against support vector machines.  arXiv preprint arXiv:1206.6389, 2012.
  * [4] 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.
  * [5] Nicholas Carlini and David Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3–14. ACM, 2017.
  * [6] Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava.  Detecting backdoor attacks on deep neural networks by activation clustering.  arXiv preprint arXiv:1811.03728, 2018.
  * [7] Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar.  Deepinspect: a black-box trojan detection and mitigation framework for deep neural networks.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 4658–4664. AAAI Press, 2019.
  * [8] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song.  Targeted backdoor attacks on deep learning systems using data poisoning.  arXiv preprint arXiv:1712.05526, 2017.
  * [9] Edward Chou, Florian Tramèr, Giancarlo Pellegrino, and Dan Boneh.  Sentinet: Detecting physical attacks against deep learning systems.  arXiv preprint arXiv:1812.00292, 2018.
  * [10] Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter.  Certified adversarial robustness via randomized smoothing.  arXiv preprint arXiv:1902.02918, 2019.
  * [11] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [12] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * [13] Yansong Gao, Chang Xu, Derui Wang, Shiping Chen, Damith C Ranasinghe, and Surya Nepal.  Strip: A defence against trojan attacks on deep neural networks.  arXiv preprint arXiv:1902.06531, 2019.
  * [14] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.
  * [15] T. Gu, K. Liu, B. Dolan-Gavitt, and S. Garg.  Badnets: Evaluating backdooring attacks on deep neural networks.  IEEE Access, 7:47230–47244, 2019.
  * [16] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  arXiv preprint arXiv:1708.06733, 2017.
  * [17] Bojan Karlas, Peng Li, Renzhi Wu, Merve Gurel, Xu Chu, Wentao Wu, and Ce Zhang.  Nearest neighbor classifiers over incomplete information: From certain answers to certain predictions.  arXiv preprint arXiv:2005.05117, 2020.
  * [18] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * [19] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [20] M. Lecuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana.  Certified robustness to adversarial examples with differential privacy.  In 2019 IEEE Symposium on Security and Privacy (SP), pages 656–672, 2019.
  * [21] 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.
  * [22] Linyi Li, Xiangyu Qi, Tao Xie, and Bo Li.  Sok: Certified robustness for deep neural networks.  arXiv preprint arXiv:2009.04131, 2020.
  * [23] Cong Liao, Haoti Zhong, Anna Squicciarini, Sencun Zhu, and David Miller.  Backdoor embedding in convolutional neural network models via invisible perturbation.  arXiv preprint arXiv:1808.10307, 2018.
  * [24] Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsieh.  Towards robust neural networks via random self-ensemble.  In Proceedings of the European Conference on Computer Vision (ECCV), pages 369–385, 2018.
  * [25] Xingjun Ma, Bo Li, Yisen Wang, Sarah M Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Dawn Song, Michael E Houle, and James Bailey.  Characterizing adversarial subspaces using local intrinsic dimensionality.  arXiv preprint arXiv:1801.02613, 2018.
  * [26] Yuzhe Ma, Xiaojin Zhu, and Justin Hsu.  Data poisoning against differentially-private learners: Attacks and defenses.  In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 4732–4738. International Joint Conferences on Artificial Intelligence Organization, 7 2019\.
  * [27] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  arXiv preprint arXiv:1706.06083, 2017.
  * [28] 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 Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 27–38. ACM, 2017.
  * [29] J Neyman and E Pearson.  On the problem of the most efficient tests of statistical hypotheses. 231\.  Phil. Trans. Roy. Statistical Soc. A, 289, 1933.
  * [30] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter.  Certified robustness to label-flipping attacks via randomized smoothing.  arXiv preprint arXiv:2002.03018, 2020.
  * [31] Brandon Tran, Jerry Li, and Aleksander Madry.  Spectral signatures in backdoor attacks.  In Advances in Neural Information Processing Systems, pages 8000–8010, 2018.
  * [32] Binghui Wang, Xiaoyu Cao, Neil Zhenqiang Gong, et al.  On certifying robustness against backdoor attacks via randomized smoothing.  arXiv preprint arXiv:2002.11750, 2020.
  * [33] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao.  Neural cleanse: Identifying and mitigating backdoor attacks in neural networks.  In Neural Cleanse: Identifying and Mitigating Backdoor Attacks in Neural Networks, page 0. IEEE, 2019.
  * [34] Wikipedia contributors.  Sha-2 — Wikipedia, the free encyclopedia, 2020.  [Online; accessed 18-March-2020].
  * [35] Chaowei Xiao, Bo Li, Jun-Yan Zhu, Warren He, Mingyan Liu, and Dawn Song.  Generating adversarial examples with adversarial networks.  arXiv preprint arXiv:1801.02610, 2018.
  * [36] Weilin Xu, David Evans, and Yanjun Qi.  Feature squeezing: Detecting adversarial examples in deep neural networks.  arXiv preprint arXiv:1704.01155, 2017.
  * [37] Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen.  Generative poisoning attack method against neural networks.  arXiv preprint arXiv:1703.01340, 2017.
  * [38] Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li.  Randomized smoothing of all shapes and sizes, 2020.
  * [39] Zhuolin Yang, Bo Li, Pin-Yu Chen, and Dawn Song.  Characterizing audio adversarial examples using temporal dependency.  arXiv preprint arXiv:1809.10875, 2018.
  * [40] Zhuolin Yang, Zhikuan Zhao, Hengzhi Pei, Boxin Wang, Bojan Karlas, Ji Liu, Heng Guo, Bo Li, and Ce Zhang.  End-to-end robustness for sensing-reasoning machine learning pipelines.  arXiv preprint arXiv:2003.00120, 2020.

##  Appendix A Proof of Theorem 1

###  A.1 Preliminaries and Auxiliary Lemmas

Central to our theoretical results are likelihood ratio tests which are
statistical hypothesis tests for testing whether a sample $x$ originates from
a distribution $X_{0}$ or $X_{1}$. These tests are defined as

$\displaystyle\phi(x)=\begin{cases}1&\mathrm{if}\,\Lambda(x)>t,\\\
q&\mathrm{if}\,\Lambda(x)=t,\\\ 0&\mathrm{if}\,\Lambda(x)<t.\\\
\end{cases}\hskip 6.00006pt\text{with}\hskip
6.00006pt\Lambda(x)=\frac{f_{X_{1}}(x)}{f_{X_{0}}(x)},$ (30)

where $q$ and $t$ are chosen such that $\phi$ has significance $\alpha_{0}$,
i.e.
$\alpha(\phi)=\mathbb{P}_{0}\left(\Lambda(X)>t\right)+q\cdot\mathbb{P}_{0}(\Lambda(X)=t)=\alpha_{0}.$

######  Lemma A.1.

Let $X_{0}$ and $X_{1}$ be two random variables with densities $f_{0}$ and
$f_{1}$ with respect to a measure $\mu$ and denote by $\Lambda$ the likelihood
ratio $\Lambda(x)=f_{1}(x)/f_{0}(x)$. For $p\in[0,\,1]$ let
$t_{p}:=\inf\\{t\geq 0\colon\,\mathbb{P}(\Lambda(X_{0})\leq t)\geq p\\}$. Then
it holds that

$\mathbb{P}\left(\Lambda(X_{0})<t_{p}\right)\leq
p\leq\mathbb{P}(\Lambda(X_{0})\leq t_{p}).$ (31)

###### Proof.

We first show the RHS of inequality (31). This follows directly from the
definition of $t_{p}$ if we show that the function
$t\mapsto\mathbb{P}(\Lambda(X_{0})\leq t)$ is right-continuous. Let $t\geq 0$
and let $\\{t_{n}\\}_{n}$ be a sequence in $\mathbb{R}_{\geq 0}$ such that
$t_{n}\downarrow t$. Define the sets $A_{n}:=\\{x\colon\Lambda(x)\leq
t_{n}\\}$ and note that $\mathbb{P}(\Lambda(X_{0})\leq
t_{n})=\mathbb{P}(X_{0}\in A_{n})$. Clearly, if $x\in\\{x\colon\Lambda(x)\leq
t\\}$ then $\forall n\colon\Lambda(x)\leq t\leq t_{n}$ and thus
$x\in\cap_{n}\,A_{n}$. If on the other hand $x\in\cap_{n}\,A_{n}$ then
$\forall n\colon\Lambda(x)\leq t_{n}\to t$ as $n\to\infty$. Hence, we have
that $\cap_{n}\,A_{n}=\\{x\colon\Lambda(x)\leq t\\}$ and thus
$\lim_{n\to\infty}\mathbb{P}\left(\Lambda(X_{0})\leq
t_{n}\right)=\mathbb{P}\left(\Lambda(X_{0})\leq t\right)$ since
$\lim_{n\to\infty}\mathbb{P}\left(X_{0}\in
A_{n}\right)=\mathbb{P}(X_{0}\in\cap_{n}A_{n})$ for $A_{n+1}\subseteq A_{n}$.
We conclude that $t\mapsto\mathbb{P}\left(\Lambda(X_{0})\leq t\right)$ is
right-continuous and in particular $\mathbb{P}\left(\Lambda(X_{0})\leq
t_{p}\right)\geq p$. We now show the LHS of inequality (31). For that purpose,
consider the sets $B_{n}:=\\{x\colon\Lambda(x)<t_{p}-\nicefrac{{1}}{{n}}\\}$
and let $B:=\\{x\colon\Lambda(x)<t_{p}\\}$. Clearly, if $x\in\cup_{n}B_{n}$,
then $\exists n$ such that $\Lambda(x)<t_{p}-\nicefrac{{1}}{{n}}<t_{p}$ and
hence $x\in B$. If on the other hand $x\in B$, then we can choose $n$ large
enough such that $\Lambda(x)<t_{p}-\nicefrac{{1}}{{n}}$ and thus
$x\in\cup_{n}B_{n}$. It follows that $B=\cup_{n}B_{n}$. Furthermore, by the
definition of $t_{p}$ and since for any $n\in\mathbb{N}$ we have that
$\mathbb{P}\left(X_{0}\in
B_{n}\right)=\mathbb{P}\left(\Lambda(X_{0})<t_{p}-\nicefrac{{1}}{{n}}\right)<p$
it follows that
$\mathbb{P}\left(\Lambda(X_{0})<t_{p}\right)=\lim_{n\to\infty}\mathbb{P}\left(X_{0}\in
B_{n}\right)\leq p$ since $B_{n}\subseteq B_{n+1}$. This concludes the proof.
∎

######  Lemma A.2.

Let $X_{0}$ and $X_{1}$ be random variables taking values in $\mathcal{Z}$ and
with probability density functions $f_{0}$ and $f_{1}$ with respect to a
measure $\mu$. Let $\phi^{*}$ be a likelihood ratio test for testing the null
$X_{0}$ against the alternative $X_{1}$. Then for any deterministic function
$\phi\colon\mathcal{Z}\to[0,1]$ the following implications hold:

  1. i)

$\alpha(\phi)\geq 1-\alpha(\phi^{*})\Rightarrow
1-\beta(\phi)\geq\beta(\phi^{*})$

  2. ii)

$\alpha(\phi)\leq\alpha(\phi^{*})\Rightarrow\beta(\phi)\geq\beta(\phi^{*})$

###### Proof.

We first show $(i)$. Let $\phi^{*}$ be a likelihood ratio test as defined in
(30). Then, for any other test $\phi$ we have

$\displaystyle 1-\beta(\phi^{*})-\beta(\phi)=$ (32)
$\displaystyle=\int_{\Lambda>t}\phi f_{1}d\mu+\int_{\Lambda\leq
t}\left(\phi-1\right)f_{1}d\mu+q\int_{\Lambda=t}f_{1}d\mu$ (33)
$\displaystyle=\int\displaylimits_{\Lambda>t}\phi\Lambda
f_{0}d\mu+\int\displaylimits_{\Lambda\leq
t}\underbrace{\left(\phi-1\right)}_{\leq 0}\Lambda
f_{0}d\mu+q\int\displaylimits_{\Lambda=t}\Lambda f_{0}d\mu$ (34)
$\displaystyle\geq t\cdot\left[\int\displaylimits_{\Lambda>t}\phi
f_{0}d\mu+\int\displaylimits_{\Lambda\leq
t}\left(\phi-1\right)f_{0}d\mu+q\int\displaylimits_{\Lambda=t}f_{0}d\mu\right]$
(35) $\displaystyle=t\cdot\left[\alpha(\phi)-(1-\alpha(\phi^{*}))\right]\geq
0$ (36)

with the last inequality following from the assumption and $t\geq 0$. Thus,
$(i)$ follows; $(ii)$ can be proved analogously. ∎

###  A.2 Main Proof

###### Proof.

We first show the existence of a likelihood ratio test $\phi_{A}$ with
significance level $1-p_{A}$. Let $Z^{\prime}:=(\delta,\Delta)+Z$ and recall
that the likelihood ratio $\Lambda$ between the densities of $Z$ and
$Z^{\prime}$ is given by $\Lambda(z)=\frac{f_{Z^{\prime}}(z)}{f_{Z}(z)}$ and
let $X^{\prime}:=\delta+X$ and $D^{\prime}=\Delta+D$. Furthermore, for any
$p\in[0,\,1]$, let $t_{p}:=\inf\\{t\geq 0\colon\mathbb{P}(\Lambda(Z)\leq
t)\geq p\\}$ and

$q_{p}=\begin{cases}0&\text{ if }\mathbb{P}\left(\Lambda(Z)=t_{p}\right)=0,\\\
\frac{\mathbb{P}(\Lambda(Z)\leq t_{p})-p}{\mathbb{P}(\Lambda(Z)=t_{p})}&\text{
otherwise}.\end{cases}$ (37)

Note that by Lemma A.1 we have that $\mathbb{P}(\Lambda(Z)\leq t_{p})\geq p$
and

$\displaystyle\mathbb{P}(\Lambda(Z)\leq t_{p})$
$\displaystyle=\mathbb{P}(\Lambda(Z)<t_{p})+\mathbb{P}(\Lambda(Z)=t_{p})$ (38)
$\displaystyle\leq p+\mathbb{P}(\Lambda(Z)=t_{p})$

and hence $q_{p}\in[0,\,1]$. For $p\in[0,\,1]$, let $\phi_{p}$ be the
likelihood ratio test defined in (30) with $q\equiv q_{p}$ and $t\equiv
t_{p}$. Note that $\phi_{p}$ has type I error probability
$\alpha(\phi_{p})=1-p$. Thus, the test $\phi_{A}\equiv\phi_{p_{A}}$ satisfies
$\alpha(\phi_{A})=1-p_{A}$. It follows from assumption (10) that
$\mathbb{E}(p(y_{A}\lvert\,x+X,\,\mathcal{D}+D))=q(y_{A}\lvert\,x,\,\mathcal{D})\geq
1-\alpha(\phi_{A})$ and thus, by applying the first part of Lemma A.2 to the
functions $\phi\equiv p(y_{A}\lvert\,x+X,\,\mathcal{D}+D)$ and
$\phi^{*}\equiv\phi_{A}$, it follows that

$\displaystyle\begin{split}q(y_{A}\lvert\,x+\delta,\,\mathcal{D}+\Delta)&=1-\beta(\phi)\geq\beta(\phi_{A}).\end{split}$
(39)

Similarly, the likelihood ratio test $\phi_{B}\equiv\phi_{1-p_{B}}$ satisfies
$\alpha(\phi_{B})=p_{B}$ and, for $y\neq y_{A}$, it follows from the
assumption (10) that
$\mathbb{E}(p(y\lvert\,x+X,\,\mathcal{D}+D))=q(y\lvert\,x,\,\mathcal{D})\leq
p_{B}=\alpha(\phi_{B}).$ Thus, applying the second part of Lemma A.2 to the
functions $\phi\equiv p(y\lvert\,x+X,\,\mathcal{D}+D)$ and
$\phi^{*}\equiv\phi_{B}$ yields

$\displaystyle\begin{split}q(y\lvert\,x+\delta,\,\mathcal{D}+\Delta)&=1-\beta(\phi)\leq
1-\beta(\phi_{B}).\end{split}$ (40)

Combining (39) and (40) we see that, if $\beta(\phi_{A})+\beta(\phi_{B})>1$,
then it is guaranteed that

$q(y_{A}\lvert\,x+\delta,\,\mathcal{D}+\Delta)>\max_{y\neq
y_{A}}q(y\lvert\,x+\delta,\,\mathcal{D}+\Delta)$ (41)

what completes the proof. ∎

##  Appendix B Proof of Corollaries 1 and 2

###### Proof of Corollary 1.

We prove this statement by direct application of Theorem 1. Let $Z=(X,\,D)$ be
the smoothing distribution for $q$ and let $\tilde{Z}:=(\delta,\,\Delta)+Z$
and $\tilde{Z}^{\prime}:=(0,\,-\Delta)+\tilde{Z}$. Correspondingly, let
$\tilde{q}(y\lvert\,x,\,\mathcal{D})=q(y\lvert\,x+\delta,\,\mathcal{D}+\Delta)$.
By assumption, we have that $\tilde{q}(y_{A}\lvert\,x,\,\mathcal{D})\geq
p_{A}$ and $\max_{y\neq y_{A}}\tilde{q}(y\lvert\,x,\,\mathcal{D})\leq p_{B}$.
We will now apply Theorem 1 to the smoothed classifier $\tilde{q}$. By Theorem
1, there exist likelihood ratio tests $\phi_{A}$ and $\phi_{B}$ for testing
$\tilde{Z}$ against $\tilde{Z}^{\prime}$ such that, if

$\beta(\phi_{A})+\beta(\phi_{B})>1$ (42)

then it follows that
$y_{A}=\arg\max_{y}\tilde{q}(y\lvert\,x,\,\mathcal{D}-\Delta)$ The statement
then follows, since
$\tilde{q}(y\lvert\,x,\,\mathcal{D}-\Delta)=\arg\max_{y}\tilde{q}(y\lvert\,x+\delta,\,\mathcal{D}\Delta)$.
We will now construct the corresponding likelihood ratio tests and show that
(42) has the form (19). Note that the likelihood ratio between $\tilde{Z}$ and
$\tilde{Z}^{\prime}$ at $z=(x,\,d)$ is given by

$\Lambda(z)=\exp\left(\sum_{i=1}^{n}\langle
d_{i},\,-\delta_{i}\rangle_{\Sigma}+\frac{1}{2}\langle\delta_{i},\,\delta_{i}\rangle_{\Sigma}\right)$
(43)

where $\Sigma=\sigma^{2}\mathds{1}_{d}$ and $\langle
a,\,b\rangle_{\Sigma}:=\sum_{i=1}^{n}a_{i}b_{i}/\sigma^{2}$. Thus, since
singletons have probability $0$ under the Gaussian distribution, any
likelihood ratio test for testing $\tilde{Z}$ against $\tilde{Z}^{\prime}$ has
the form

$\displaystyle\phi_{t}(z)=\begin{cases}1,&\,\Lambda(z)\geq t.\\\
0,&\,\Lambda(z)<t.\end{cases}$ (44)

For $p\in[0,\,1]$, let

$\displaystyle
t_{p}:=\exp\left(\Phi^{-1}(p)\sqrt{\sum_{i=1}^{n}\langle\delta_{i},\,\delta_{i}\rangle_{\Sigma}}-\frac{1}{2}\sum_{i=1}^{n}\langle\delta_{i},\,\delta_{i}\rangle_{\Sigma}\right)$
(45)

and note that $\alpha(\phi_{t_{p}})=1-p$ since

$\displaystyle\alpha(\phi_{t_{p}})=1-\Phi\left(\frac{\log(t_{p})+\frac{1}{2}\sum_{i=1}^{n}\langle\delta_{i},\,\delta_{i}\rangle_{\Sigma}}{\sqrt{\sum_{i=1}^{n}\langle\delta_{i},\,\delta_{i}\rangle_{\Sigma}}}\right)$
(46)

where $\Phi$ is the CDF of the standard normal distribution. Thus, the test
$\phi_{A}\equiv\phi_{t_{A}}$ with $t_{A}\equiv t_{p_{A}}$ satisfies
$\alpha(\phi_{A})=1-p_{A}$ and the test $\phi_{B}\equiv\phi_{t_{B}}$ with
$t_{B}\equiv t_{1-p_{B}}$ satisfies $\alpha(\phi_{B})=p_{B}$. Computing the
type II error probability of $\phi_{A}$ yields
$\beta(\phi_{A})=\Phi\left(\Phi^{-1}(p_{A})-\sqrt{\sum_{i=1}^{n}\langle\delta_{i},\,\delta_{i}\rangle_{\Sigma}}\right)$.
and, similarly, the type II error probability of $\phi_{B}$ is given by
$\beta(\phi_{B})=\Phi\left(\Phi^{-1}(1-p_{B})-\sqrt{\sum_{i=1}^{n}\langle\delta_{i},\,\delta_{i}\rangle_{\Sigma}}\right)$.
Finally, we see that $\beta(\phi_{A})+\beta(\phi_{B})>1$ is satisfied iff
$\sqrt{\sum_{i=1}^{n}\left\|\delta_{i}\right\|_{2}^{2}}<\frac{\sigma}{2}\left(\Phi^{-1}(p_{A})-\Phi^{-1}(p_{B})\right)$
what concludes the proof. ∎

###### Proof of Corollary 2.

We proceed analogously to the proof of Corollary 1 but with a Uniform
distribution, on the feature vectors $D\sim\mathcal{U}([a,\,b])$ and construct
the likelihood ratio tests in the uniform case. Denote by
$S:=\prod_{i=1}^{n}S_{i},\,S_{i}:=\prod_{j=1}^{d}[a+\delta_{ij},\,b+\delta_{ij}]$
the support of $\tilde{D}:=\Delta+D$ and by
$S^{\prime}:=\prod_{i=1}^{n}[a,\,b]^{d}$ the support of
$\tilde{D}^{\prime}:=D$. Note the likelihood ratio between $\tilde{Z}$ against
$\tilde{Z}^{\prime}$ at $z=(x,\,w,\,v)$ for any $w\in S\cup S^{\prime}$ is
given by

$\displaystyle\Lambda(z)=\frac{f_{\tilde{Z}^{\prime}}(z)}{f_{\tilde{Z}}(z)}=\frac{f_{\tilde{W}^{\prime}}(w)}{f_{\tilde{W}}(w)}=\begin{cases}0&\,w\in
S\setminus S^{\prime},\\\ 1&\,w\in S\cap S^{\prime},\\\ \infty&\,w\in
S^{\prime}\setminus S.\end{cases}$ (47)

and that any likelihood ratio test for testing $\tilde{Z}$ against
$\tilde{Z}^{\prime}$ has the form (30) We now construct such likelihood ratio
tests $\phi_{A},\,\phi_{B}$ with $\alpha(\phi_{A})=1-p_{A}$ and
$\alpha(\phi_{B})=p_{B}$ by following the construction in the proof of Theorem
1. Specifically, we compute $q_{A},\,t_{A}$ such that the these type I error
probabilities are satisfied. Notice that

$\displaystyle p_{0}:=\mathbb{P}\left(\tilde{W}\in S\setminus
S^{\prime}\right)=1-\prod_{i=1}^{n}\left(\prod_{j=1}^{d}\left(1-\frac{\lvert\delta_{ij}\rvert}{b-a}\right)_{+}\right)$
(48)

where $(x)_{+}=\max\\{x,\,0\\}$. For $t\geq 0$ we have

$\displaystyle\mathbb{P}\left(\Lambda(\tilde{Z})\leq t\right)$
$\displaystyle=\begin{cases}p_{0}&\,t<1\\\ 1&\,t\geq 1\end{cases}$ (49)

and thus $t_{p}:=\inf\\{t\geq 0\colon\mathbb{P}(\Lambda(Z)\leq t)\geq p\\}$ is
given by $t_{p}=0$ if $p\leq p_{0}$ and $t_{p}=1$ if $p>p_{0}$. We notice
that, if $p_{A}\leq p_{0}$, then $t_{A}\equiv t_{p_{A}}=0$. This implies that
the type II error probability of the corresponding test $\phi_{A}$ is $0$
since in this case

$\displaystyle\beta(\phi_{A})$
$\displaystyle=1-\mathbb{P}\left(\Lambda(\tilde{Z}^{\prime})>0\right)-q_{A}\cdot\mathbb{P}\left(\Lambda(\tilde{Z}^{\prime})=0\right)$
(50) $\displaystyle=1-\mathbb{P}\left(\tilde{D}^{\prime}\in
S^{\prime}\right)-q_{A}\cdot\mathbb{P}\left(\tilde{D}^{\prime}\in S\setminus
S^{\prime}\right)=0.$ (51)

Similarly, if $1-p_{B}\leq p_{0}$ then $t_{B}\equiv t_{p_{B}}=0$ and we obtain
that the corresponding test $\phi_{B}$ satisfies $\beta(\phi_{B})=0$. In both
cases $\beta(\phi_{A})+\beta(\phi_{B})>1$ can never be satisfied and we find
that $p_{A}>p_{0}$ and $1-p_{B}>p_{0}$ is a necessary condition. In this case,
we have that $t_{A}=t_{B}=1$. Let $q_{A}$ and $q_{B}$ be defined as in the
proof of Theorem 1

$\displaystyle q_{A}$ $\displaystyle:=\frac{\mathbb{P}(\Lambda(\tilde{Z})\leq
1)-p_{A}}{\mathbb{P}(\Lambda(\tilde{Z})=1)}=\frac{1-p_{A}}{1-p_{0}},$ (52)
$\displaystyle q_{B}$ $\displaystyle:=\frac{\mathbb{P}(\Lambda(\tilde{Z})\leq
1)-(1-p_{B})}{\mathbb{P}(\Lambda(\tilde{Z})=1)}=\frac{1-(1-p_{B})}{1-p_{0}}.$
(53)

Clearly, the corresponding likelihood ratio tests $\phi_{A}$ and $\phi_{B}$
have significance $1-p_{A}$ and $p_{B}$ respectively. Furthermore, notice that

$\displaystyle\mathbb{P}\left(\tilde{D}^{\prime}\in S^{\prime}\setminus
S\right)$ $\displaystyle=\mathbb{P}\left(\tilde{D}\in S\setminus
S^{\prime}\right)=p_{0}$ (54)
$\displaystyle\mathbb{P}\left(\tilde{D}^{\prime}\in S^{\prime}\cap S\right)$
$\displaystyle=\mathbb{P}\left(\tilde{D}\in S^{\prime}\cap S\right)=1-p_{0}$
(55)

and hence $\beta(\phi_{A})$ is given by

$\displaystyle\beta(\phi_{A})$
$\displaystyle=1-\mathbb{P}\left(\Lambda(\tilde{Z}^{\prime})>1\right)-q_{A}\cdot\mathbb{P}\left(\Lambda(\tilde{Z}^{\prime})=1\right)$
(56) $\displaystyle=1-\mathbb{P}\left(\tilde{D}^{\prime}\in
S^{\prime}\setminus S\right)-q_{A}\cdot\mathbb{P}\left(\tilde{D}^{\prime}\in
S^{\prime}\cap S\right)$ (57)
$\displaystyle=1-p_{0}-q_{A}\cdot(1-p_{0})=p_{A}-p_{0}.$ (58)

and similarly

$\displaystyle\beta(\phi_{B})$
$\displaystyle=1-\mathbb{P}\left(\Lambda(\tilde{Z}^{\prime})>1\right)-q_{B}\cdot\mathbb{P}\left(\Lambda(\tilde{Z}^{\prime})=1\right)$
(59) $\displaystyle=1-\mathbb{P}\left(\tilde{D}^{\prime}\in
S^{\prime}\setminus S\right)-q_{B}\cdot\mathbb{P}\left(\tilde{D}^{\prime}\in
S^{\prime}\cap S\right)$ (60)
$\displaystyle=1-p_{0}-q_{B}\cdot(1-p_{0})=1-p_{B}-p_{0}.$ (61)

Finally, the statement follows, since $\beta(\phi_{A})+\beta(\phi_{B})>1$ if
and only if

$1-\left(\frac{p_{A}-p_{B}}{2}\right)<\prod_{i=1}^{n}\left(\prod_{j=1}^{d}\left(1-\frac{\lvert\delta_{ij}\rvert}{b-a}\right)_{+}\right)$
(62)

∎

##  Appendix C Smoothed K-NN Classifiers

We first formalize $K$-NN classifiers which use quantizeed euclidean distance
as a notion of similarity. Specifically, let
$B_{1}=[0,\,b_{1}),\,\ldots,B_{L}:=[b_{L-1},\infty)$ be similarity buckets
with increasing $b_{1}<b_{2}<\ldots,b_{L-1}$ and associated similarity levels
$\beta_{1}>\beta_{2}>\ldots>\beta_{L}$. Then for
$x,\,x^{\prime}\in\mathbb{R}^{d}$ we define their similarity as
$\kappa(x,x^{\prime}):=\sum_{l=1}^{L}\beta_{l}\mathds{1}_{B_{l}}(\left\|x-x^{\prime}\right\|_{2}^{2})$
where $\mathds{1}_{B_{l}}$ is the indicator function of $B_{l}$. Given a
dataset $D=(x_{i},\,y_{i})_{i=1}^{n}$ and a test instance $x$, we define the
relation

$\displaystyle x_{i}$ $\displaystyle\succeq
x_{j}\iff\begin{cases}\kappa(x_{i},\,x)>\kappa(x_{j},\,x)&\text{ if }i>j\\\
\kappa(x_{i},\,x)\geq\kappa(x_{j},\,x)&\text{ if }i\leq j\end{cases}$ (63)

which says that the instance $x_{i}$ is more similar to $x$, if either it has
strictly larger similarity or, if it has the same similarity as $x_{j}$, then
$x_{i}$ is more similar if $i<j$. With this binary relation, we define the set
of $K$ nearest neighbours of $x$ as

$I_{K}(x,\,\mathcal{D}):=\\{i\colon\,\left|\\{j\neq i\colon\,x_{j}\succeq
x_{i}\\}\right|\leq K-1\\}\subseteq[n]$ (64)

and summarize the per class votes in $I_{K}$ as a label tally vector

$\gamma_{k}(x,\,\mathcal{D}):=\\#\\{i\in
I_{K}(x,\,\mathcal{D})\colon\,y_{i}=k\\}.$ (65)

The prediction of a $K$-NN classifier is then given by
$\text{$K$-NN}(x,\,\mathcal{D})=\arg\max_{k}\gamma_{k}(x,\,\mathcal{D}).$

###  C.1 Proof of Theorem 3

###### Proof.

Our goal is to show that we can compute the smoothed classifier $q$ with
$Z=(0,\,D)$, and
$D\sim\prod_{i=1}^{n}\mathcal{N}(0,\,\sigma^{2}\mathds{1}_{d})$ and defined by
the probability

$q(y\lvert\,x,\,\mathcal{D})=\mathbb{P}_{D}\left(\text{$K$-NN}(x,\,\mathcal{D}+D)=y\right)$
(66)

in time $\mathcal{O}(K^{2+C}\cdot n^{2}\cdot L\cdot C)$. For ease of notation,
let $X_{i}:=x_{i}+D^{(i)}$ and $S_{i}:=\kappa(X_{i},\,x)$ and note that
$p_{i}^{l}:=\mathbb{P}\left(S_{i}=\beta_{l}\right)=F_{d,\lambda_{i}}\left(\frac{b_{l}}{\sigma^{2}}\right)-F_{d,\lambda_{i}}\left(\frac{b_{l-1}}{\sigma^{2}}\right)$
where $F_{d,\lambda_{i}}$ is the CDF of the non-central
$\chi^{2}$-distribution with $d$ degrees of freedom and non-locality parameter
$\lambda_{i}=\left\|x_{i}+\delta_{i}-x\right\|_{2}^{2}/\sigma^{2}$. Note that
we can write (66) equivalently as
$\mathbb{P}_{D}\left(\arg\max_{k^{\prime}}\gamma_{k^{\prime}}(x,\,\mathcal{D}+D))=y\right)$
and thus
$q(y\lvert\,x,\,\mathcal{D})=\sum_{\gamma\in\Gamma_{k}}\mathbb{P}_{D}\left(\gamma(x,\,\mathcal{D}+D)=\gamma\right)$
with
$\Gamma_{k}:=\\{\gamma\in[K]^{C}\colon\,\arg\max_{k^{\prime}}\gamma_{k^{\prime}}=k\\}$.
Next, we notice that the event that a tally vector $\gamma$ occurs, can be
partitioned into the events that lead to the given $\gamma$ and for which
instance $i$ has similarity $\beta_{l}$ and is in the top-$K$ but not in the
top-$(K-1)$. We define these to be the boundary events

$\mathcal{B}_{i}^{l}(\gamma):=\\{\forall c\colon\,\\#\\{j\in I_{c}\colon
X_{j}\succeq X_{i}\\}=\gamma_{c},\,S_{i}=\beta_{l}\\}$ (67)

where $I_{c}=\\{i\colon y_{i}=c\\}$. The probability that a given tally vector
$\gamma$ occurs is thus given by

$\mathbb{P}_{D}\left(\gamma(x,\,\mathcal{D}+D)=\gamma\right)=\sum_{i=1}^{n}\sum_{l=1}^{L}\mathbb{P}\left(\mathcal{B}_{i}^{l}(\gamma)\right).$
(68)

For fixed $i$ we notice that the for different classes, the events
$\\{\\#\\{j\in I_{c}\colon X_{j}\succeq X_{i}\\}=\gamma_{c}\\}$ are pairwise
independent, conditioned on $\\{S_{i}=\beta_{l}\\}$. Let
$P_{c}^{l}(i,\,\gamma)=\mathbb{P}\left(\\#\\{i\in I_{c}\colon
y_{i}=c\\}=\gamma_{c}\lvert\,S_{i}=\beta_{l}\right)$ and note that
$\mathbb{P}\left(\mathcal{B}_{i}^{l}(\gamma)\right)=p_{i}^{l}\cdot\prod_{c=1}^{C}\,P_{c}^{l}(i,\,\gamma)$
and hence

$\displaystyle
q(y\lvert\,x,\,\mathcal{D})=\sum_{\gamma\in\Gamma_{k}}\sum_{i=1}^{n}\sum_{l=1}^{L}p_{i}^{l}\cdot\prod_{c=1}^{C}\,P_{c}^{l}(i,\,\gamma)$
(69)

which requires $\mathcal{O}(K^{C}\cdot n\cdot L\cdot C)$ evaluations of
$P_{c}^{l}$. The next step is to compute the probabilities $P_{c}^{l}$. For
that purpose we need to open up the binary relation $\succeq$. Suppose first,
that $y_{i}\neq c$. Then the event that exactly $\gamma_{c}$ instances of
class $c$ satisfy $X_{j}\succeq X_{i}$ is the same as the event that for some
$r\leq\gamma_{c}$ exactly $r$ instances with index larger than $i$ have
similarity strictly larger than $X_{i}$ and exactly $\gamma_{c}-r$ instances
with index smaller than $i$ have similarity larger or equal than $X_{i}$. Now
suppose that $y_{i}=c$. Then, the event that exactly $\gamma_{c}$ instances of
the same class $c$ satisfy $X_{j}\succeq X_{i}$ is the same as the event that
for some $r\leq\gamma_{c}$ exactly $r$ instances with index larger than $i$
have similarity strictly larger than $X_{i}$ and exactly $\gamma_{c}-r-1$
instances with index smaller than $i$ have similarity larger or equal than
$X_{i}$. This reasoning allows us to write $P_{c}^{l}$ in terms of functions

$\displaystyle R_{c}^{l}(i,\,r)$ $\displaystyle:=\mathbb{P}\left(|\\{j\in
I_{c}\colon\,S_{j}>\beta_{l},\,j>i\\}|=r\right)$ (70) $\displaystyle
Q_{c}^{l}(i,\,r)$ $\displaystyle:=\mathbb{P}\left(|\\{j\in
I_{c}\colon\,S_{j}\geq\beta_{l},\,j<i\\}|=r\right)$ (71)

as

$\displaystyle
P_{c}^{l}(i,\,\gamma)=\begin{cases}\sum_{r=0}^{\gamma_{c}}R_{c}^{l}(i,r)\cdot
Q_{c}^{l}(i,\gamma_{c}-r)&y_{i}\neq c\\\
\sum_{r=0}^{\gamma_{c}-1}R_{c}^{l}(i,r)\cdot
Q_{c}^{l}(i,\gamma_{c}-r-1)&y_{i}=c.\end{cases}$

The functions $R_{l}^{c}$ and $Q_{l}^{c}$ exhibit recursive structure that we
wish to exploit in order to get an efficient algorithm. Specifically, we write
$\alpha_{i}^{l}:=\mathbb{P}(S_{i}\leq\beta_{l})=\sum_{s=l}^{L}p_{i}^{l}$, and
$\bar{\alpha}_{i}^{l}:=1-\alpha_{i}^{l}$ and use the following recursion

$\displaystyle R_{l}^{c}(i-1,\,r)=\begin{cases}R_{c}^{l}(i,r)&y_{i}\neq c\\\
\bar{\alpha}_{i}^{l}\cdot R_{c}^{l}(i,r-1)+\alpha_{i}^{l}\cdot
R_{c}^{l}(i,r)&y_{i}=c\end{cases}$

starting at $i=n$ and $r=0$ and with initial values $R_{c}^{l}(i,\,-1)=0$,
$R_{l}^{c}(n,\,0)=1$ and $R_{l}^{c}(n,\,r)=0$ for $r\geq 1$. Similarly,

$\displaystyle Q_{c}^{l}(i+1,\,r)=\begin{cases}Q_{c}^{l}(i,\,r)&y_{i}\neq c\\\
\\!\begin{aligned} &\bar{\alpha}_{i}^{l+1}\cdot Q_{c}^{l}(i,\,r-1)\\\ &\hskip
20.00003pt+\alpha_{i}^{l+1}\cdot
Q_{c}^{l}(i,\,r)\end{aligned}&y_{i}=c\end{cases}$ (72)

starting the recursion at $i=1$ and $r=0$ and with initial values
$Q_{c}^{l}(i,\,-1)=0$, $Q_{c}^{l}(1,\,0)=1$ and $Q_{c}^{l}(1,\,r)=0$ for
$r\geq 1$. Evaluating $P_{c}^{l}$ requires $\mathcal{O}(K)$ calls to
$R_{c}^{l}$ and $Q_{c}^{l}$ each. The computation of $R_{c}^{l}$ and
$Q_{c}^{l}$ can be achieved in $\mathcal{O}(n\cdot K)$ if the values
$\alpha_{i}^{l}$ are computed beforehand and stored separately (requiring
$\mathcal{O}(n\cdot L)$ computations). Finally, the entire computation has a
time complexity of $\mathcal{O}(K^{C+2}\cdot n^{2}\cdot L\cdot C)$ what
concludes the proof. ∎

##  Appendix D Additional Experiment Results

Results on Other (Source, Target) Pairs. We show the performance of our
pipeline on other randomly chosen pair of (source, target) data in different
tasks in Table D.7. In particular, we use (6,8) for MNIST, (automobile, dog)
for CIFAR and (dog, fish) for ImageNet. We observe that the certification
performance is similar with before. This shows that our pipeline works well in
general.

Effect of deterministic noise for test data. In Figure 5, we show the
comparison when we add or do not add deterministic noise to test data as
proposed in Section 6. The dashed lines show the performance when we do not
use test-time data augmentation, while the solid lines show when we use it. We
can observe that the proposed test-time deterministic noise augmentation
technique significantly improves the certified robustness against the same
backdoors.

Figure 5: Comparison of certification performance of four-pixel attack with
$||\delta||_{2}=0.1$ and $r_{p}=0.02$ with and without test-time augmentation.
Dashed line is the performance without test-time augmentation and solid line
is the performance with test-time augmentation. On the ImageNet dataset, the
certification completely fails without test-time augmentation when
$\sigma=1.0$, so there is no red dashed line.

Example of trigger patterns. We show the trigger pattern we used in the MNIST
experiment for one-pixel attack, four-pixel attack and blending attack
respectively in Figure 6.

Figure 6: The backdoor pattern in the MNIST experiments for one-pixel attack
(left) four-pixel attack (middle) blending attack (right).

Benign Accuracy of Regular and Smoothed Models. We show the benign accuracy
(i.e. the accuracy on benign test data without backdoor patterns) of a regular
model and smoothed models in Table D.6 (the models are trained on benign
($r_{p}=0$) and backdoored data respectively). For models trained with
backdoors, we consider the backdoors as four-pixel pattern with
$||\delta||_{2}=0.1$ and $r_{p}=0.02$. We observe that the benign accuracy of
a smoothed model decreases by a small margin compared to the regular model in
both cases (i.e. $r_{p}=0$ and $r_{p}=0.02$), indicating that the cost of the
smoothing process is small.

Table D.6: Benign accuracy of the regular ($\sigma=0$) and smoothed model ($\sigma>0$) trained on the backdoored dataset using four-pixel attack with $||\delta||_{2}=0.1$ and $r_{p}=0.02$. Dataset | Poisoning Ratio | $\sigma$ | Benign Accuracy
---|---|---|---
MNIST | $r_{p}=0$ | 0 | 1.000
1.0 | 1.000
2.0 | 1.000
$r_{p}=0.02$ | 0 | 1.000
1.0 | 1.000
2.0 | 1.000
CIFAR | $r_{p}=0$ | 0 | 0.881
0.5 | 0.859
1.0 | 0.847
$r_{p}=0.02$ | 0 | 0.866
0.5 | 0.839
1.0 | 0.823
ImageNet | $r_{p}=0$ | 0 | 0.985
0.5 | 0.955
1.0 | 0.916
$r_{p}=0.02$ | 0 | 0.981
0.5 | 0.956
1.0 | 0.911
Table D.7: Experiment results with DNN on different datasets for another
randomly chosen binary pair, in particular, (6,8) for MNIST, (automobile,dog)
for CIFAR and (dog,fish) for ImageNet.

MNIST | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.2/0.5/1.0/2.0$ | Certified Rate at $R=0.2/0.5/1.0/2.0$
---|---|---|---|---|---|---
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.982 | 0.956 / 0.710 / 0.000 / 0.000 | 0.957 / 0.710 / 0.000 / 0.000
2.0 | 0.876 | 0.775 / 0.533 / 0.073 / 0.000 | 0.783 / 0.534 / 0.073 / 0.000
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.993 | 0.984 / 0.965 / 0.826 / 0.000 | 0.984 / 0.965 / 0.826 / 0.000
2.0 | 0.964 | 0.932 / 0.882 / 0.670 / 0.052 | 0.934 / 0.883 / 0.670 / 0.052
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.981 | 0.959 / 0.691 / 0.000 / 0.000 | 0.960 / 0.691 / 0.000 / 0.000
2.0 | 0.859 | 0.740 / 0.485 / 0.032 / 0.000 | 0.748 / 0.489 / 0.032 / 0.000
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.993 | 0.985 / 0.968 / 0.814 / 0.000 | 0.985 / 0.968 / 0.814 / 0.000
2.0 | 0.967 | 0.937 / 0.895 / 0.700 / 0.081 | 0.938 / 0.896 / 0.700 / 0.081
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 1.0 | 0.977 | 0.953 / 0.719 / 0.000 / 0.000 | 0.955 / 0.719 / 0.000 / 0.000
2.0 | 0.861 | 0.753 / 0.518 / 0.077 / 0.000 | 0.763 / 0.521 / 0.077 / 0.000
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 1.0 | 0.993 | 0.987 / 0.971 / 0.839 / 0.000 | 0.987 / 0.971 / 0.839 / 0.000
2.0 | 0.965 | 0.940 / 0.896 / 0.700 / 0.063 | 0.941 / 0.897 / 0.700 / 0.063
CIFAR | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.900 | 0.872 / 0.840 / 0.717 / 0.000 | 0.914 / 0.875 / 0.732 / 0.001
1.0 | 0.814 | 0.783 / 0.748 / 0.678 / 0.305 | 0.863 / 0.818 / 0.729 / 0.325
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.935 | 0.924 / 0.910 / 0.875 / 0.627 | 0.949 / 0.931 / 0.887 / 0.627
1.0 | 0.904 | 0.891 / 0.882 / 0.849 / 0.733 | 0.938 / 0.923 / 0.879 / 0.743
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.886 | 0.863 / 0.822 / 0.683 / 0.000 | 0.911 / 0.856 / 0.706 / 0.001
1.0 | 0.823 | 0.796 / 0.767 / 0.698 / 0.308 | 0.870 / 0.833 / 0.749 / 0.324
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.939 | 0.927 / 0.914 / 0.878 / 0.622 | 0.954 / 0.932 / 0.889 / 0.623
1.0 | 0.905 | 0.897 / 0.887 / 0.857 / 0.737 | 0.944 / 0.924 / 0.885 / 0.748
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.885 | 0.862 / 0.829 / 0.709 / 0.000 | 0.907 / 0.862 / 0.723 / 0.000
1.0 | 0.822 | 0.791 / 0.764 / 0.687 / 0.308 | 0.872 / 0.840 / 0.739 / 0.323
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.940 | 0.926 / 0.915 / 0.881 / 0.621 | 0.951 / 0.933 / 0.893 / 0.621
1.0 | 0.904 | 0.894 / 0.884 / 0.858 / 0.736 | 0.942 / 0.924 / 0.887 / 0.747
ImageNet | Attack Approach | Attack Setting | $\sigma$ | Prediction Acc | Certified Acc at $R=0.05/0.1/0.2/0.5$ | Certified Rate at $R=0.05/0.1/0.2/0.5$
One-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.870 | 0.817 / 0.730 / 0.438 / 0.000 | 0.830 / 0.739 / 0.441 / 0.001
1.0 | 0.724 | 0.694 / 0.655 / 0.558 / 0.123 | 0.737 / 0.690 / 0.581 / 0.130
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.953 | 0.943 / 0.938 / 0.901 / 0.327 | 0.948 / 0.943 / 0.904 / 0.328
1.0 | 0.894 | 0.883 / 0.877 / 0.854 / 0.696 | 0.895 / 0.887 / 0.862 / 0.700
Four-pixel | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.888 | 0.852 / 0.778 / 0.471 / 0.000 | 0.862 / 0.783 / 0.474 / 0.001
1.0 | 0.759 | 0.723 / 0.678 / 0.587 / 0.106 | 0.764 / 0.712 / 0.610 / 0.114
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.958 | 0.944 / 0.929 / 0.903 / 0.272 | 0.949 / 0.933 / 0.907 / 0.273
1.0 | 0.901 | 0.893 / 0.878 / 0.847 / 0.701 | 0.907 / 0.889 / 0.855 / 0.706
Blending | $\left\|\delta_{i}\right\|_{2}=1.0,r_{p}=0.1$ | 0.5 | 0.893 | 0.827 / 0.745 / 0.468 / 0.002 | 0.836 / 0.753 / 0.473 / 0.003
1.0 | 0.769 | 0.734 / 0.689 / 0.589 / 0.101 | 0.766 / 0.713 / 0.605 / 0.106
$\left\|\delta_{i}\right\|_{2}=0.1,r_{p}=0.02$ | 0.5 | 0.951 | 0.943 / 0.934 / 0.895 / 0.282 | 0.947 / 0.938 / 0.897 / 0.284
1.0 | 0.913 | 0.900 / 0.887 / 0.853 / 0.734 | 0.910 / 0.895 / 0.859 / 0.739