# Post-Training Detection of Backdoor Attacks for Two-Class and Multi-Attack
Scenarios

Zhen Xiang, David J. Miller & George Kesidis
School of EECS
Pennsylvania State University
{zux49, djm25<EMAIL_ADDRESS>
###### Abstract

Backdoor attacks (BAs) are an emerging threat to deep neural network
classifiers. A victim classifier will predict to an attacker-desired target
class whenever a test sample is embedded with the same backdoor pattern (BP)
that was used to poison the classifier’s training set. Detecting whether a
classifier is backdoor attacked is not easy in practice, especially when the
defender is, e.g., a downstream user without access to the classifier’s
training set. This challenge is addressed here by a reverse-engineering
defense (RED), which has been shown to yield state-of-the-art performance in
several domains. However, existing REDs are not applicable when there are only
two classes or when multiple attacks are present. These scenarios are first
studied in the current paper, under the practical constraints that the
defender neither has access to the classifier’s training set nor to
supervision from clean reference classifiers trained for the same domain. We
propose a detection framework based on BP reverse-engineering and a novel
expected transferability (ET) statistic. We show that our ET statistic is
effective using the same detection threshold, irrespective of the
classification domain, the attack configuration, and the BP reverse-
engineering algorithm that is used. The excellent performance of our method is
demonstrated on six benchmark datasets. Notably, our detection framework is
also applicable to multi-class scenarios with multiple attacks. Code is
available at https://github.com/zhenxianglance/2ClassBADetection.

##  1 Introduction

Despite the success of deep neural network (DNN) classifiers in many research
areas, their vulnerabilities have been recently exposed Xu et al. (2020);
Miller et al. (2020). One emerging threat to DNN classifiers is a backdoor
attack (BA) Li et al. (2020). Here, a classifier will predict to the
attacker’s target class when a test sample is embedded with the same backdoor
pattern (BP) that was used to poison the classifier’s training set. On the
other hand, the classifier’s clean test set accuracy (i.e., on samples without
an embedded BP) is largely uncompromised Gu et al. (2019); Chen et al. (2017);
Liu et al. (2018b), which makes the attack difficult to detect.

Early BA defenses aim to cleanse the possibly poisoned training set of the
victim classifier Tran et al. (2018); Chen et al. (2018). But deployment of
these defenses is not feasible when the defender is the user/consumer of the
classifier, without access to its training set or to any prior knowledge of
the backdoor pattern Wang et al. (2020). A major defense approach suitable for
this scenario is a reverse-engineering defense (RED). In general, a RED treats
each class as a putative BA target class and trial-reverse-engineers a BP.
Then, detection statistics are derived from the estimated pattern for each
putative target class. If there is a BA, the pattern estimated for the true BA
target class will likely be correlated with the true BP used by the attacker,
such that the associated statistics will likely be anomalous referenced
against the statistics for the other (non-BA) classes Wang et al. (2019);
Xiang et al. (2020). Notably, RED-based anomaly detection does not require
supervision from clean classifiers trained for the same domain like, e.g.,
Kolouri et al. (2020).

Although existing REDs have achieved leading performance in many practical
detection tasks, a fundamental limitation still remains. RED-based anomaly
detection typically requires estimating a null distribution used to assess
anomalies, with the number of detection statistics (samples) used to estimate
this null a function of the number of classes $K$. Wang et al. (2019) uses
$O(K)$ statistics, and Xiang et al. (2020) uses even more statistics –
$O(K^{2})$. These methods are not applicable for domains with $K=2$, e.g.
sentiment classification Gao et al. (2019b), disease diagnosis Li et al.
(2014), etc., because there are insufficient statistics for estimating the
null. More generally, their accuracy is affected when the number of classes is
small ($K>2$, but small).

In this paper, we focus on BA detection for the two-class (and possibly multi-
attack) scenario, under two practical constraints: a) the defender has no
access to the training set of the victim classifier (or to any BP used by the
attacker); b) supervision from clean classifiers trained for the same domain
is not available. This scenario is clearly more challenging than the one
considered by existing REDs, for which there is at most one BA target class
and a sufficient number of non-target classes to learn an accurate null. As
the first to address this difficult problem, our main contributions are as
follows:

  * •

We propose a detection framework that involves BP reverse-engineering in order
to address constraint a) above. However, instead of performing anomaly
detection as existing REDs do, we process each class independently using a
novel detection statistic dubbed expected transferability (ET). This allows
our method to be applicable to the two-class, multi-attack scenario (as well
as to the multi-class and (possibly) multi-attack scenario).

  * •

We show that for ET there is a large range of effective choices for the
detection threshold, which commonly contains a particular threshold value
effective for detecting BAs irrespective of the classification domain or
particulars of BA. This common threshold is mathematically derived and is
based on properties for general classification tasks that have been verified
empirically by many existing works; thus, constraint b) that no domain-
specific supervision is needed is well-addressed.

  * •

Our ET statistic is obtained by BP reverse-engineering and does not strongly
depend on the type of BP, or the particular RED objective function and
optimization technique used to reverse-engineer putative BPs. Thus, our
detection framework can incorporate existing reverse-engineering techniques
and potentially their future advances.

  * •

We show the effectiveness of our detection framework on six popular benchmark
image datasets.

##  2 Related Work

Backdoor Attack (BA). For a classification task with sample space
${\mathcal{X}}$ and label space ${\mathcal{C}}$, a BA aims to have the victim
classifier $f:{\mathcal{X}}\rightarrow{\mathcal{C}}$ predict to the target
class $t\in{\mathcal{C}}$ whenever a test sample ${\bf x}\in{\mathcal{X}}$ is
embedded with the backdoor pattern (BP) Gu et al. (2019). BAs were initially
proposed for image classification, but have also been proposed for other
domains and tasks Xiang et al. (2021a); Zhai et al. (2021); Li et al. (2022).
While we focus on images experimentally, our detector is also applicable to
other domains. Major image BPs include: 1) an additive perturbation ${\bf v}$
embedded by

$\tilde{\bf x}=[{\bf x}+{\bf v}]_{\rm c}\vspace{-0.05in}$ (1)

where $||{\bf v}||_{2}$ is small (for imperceptibility) and $[\cdot]_{\rm c}$
is a clipping function Chen et al. (2017); Zhong et al. (2020); Xiang et al.
(2020); or 2) a patch ${\bf u}$ inserted using an image-wide binary mask ${\bf
m}$ via

$\tilde{\bf x}=(1-{\bf m})\odot{\bf x}+{\bf m}\odot{\bf u},\vspace{-0.05in}$
(2)

where $||{\bf m}||_{1}$ is small for imperceptibility) and $\odot$ represents
element-wise multiplication Gu et al. (2019); Wang et al. (2019); Xiang et al.
(2021c). Typically111A clean-label BA with a different strategy Turner et al.
(2019) is also detectable by our method (Apdx. E)., BAs are launched by
inserting into the training set a small set of samples labeled to the target
class and embedded with the same BP that will be used during testing. Such
data poisoning can be achieved e.g. when DNN training is outsourced to parties
that are possibly malicious Gu et al. (2019). BAs are also stealthy since they
do not degrade the classifier’s accuracy on clean test samples; hence they are
not detectable based on validation set accuracy.

Backdoor Defense. Some BA defenses aim to separate backdoor training samples
from clean ones during the training process Tran et al. (2018); Chen et al.
(2018); Du et al. (2020); Xiang et al. (2019); Huang et al. (2022). However,
their deployment is not feasible in many practical scenarios where the
defender is a downstream user who has no access to the training process. A
family of pruning-based method “removes” the backdoor mapping by inspecting
neuron activations (and removing some neurons) Liu et al. (2018a); Li et al.
(2021). These methods cause non-negligible degradation to classification
accuracy, they may remove neurons even when there is no backdoor, and moreover
they do not make explicit detection inferences. Kolouri et al. (2020) and Xu
et al. (2021) train a binary classifier to classify models as “with” and
“without” BAs; but such training requires clean classifiers from the same
domain or a significant number of labeled samples and heavy computation to
train these clean classifiers. Chou et al. (2018) and Gao et al. (2019a) can
detect triggering of a backdoor by an observed test sample. Unlike these
methods, the existing RED-based detector (introduced next) reliably detects
backdoors without the need to observe any test samples.

Reverse-Engineering Defense (RED). RED is a family of BA defenses that do not
need access to the classifier’s training set, nor to any prior knowledge of
the BP that may be used in an attack. Without knowing whether the classifier
has been backdoor-attacked, a RED trial-reverse-engineers a BP for each
putative BA target class (or possibly for each (source, target) BA class pair)
using a small, clean dataset independently collected by the defender. Then,
for each class, a detection statistic is derived from the estimated pattern
and used to infer if the class is a BA target class or not. For example, to
detect BAs with an additive perturbation BP (Eq. (1)), Xiang et al. (2020)
finds, for each putative target class, the perturbation with the minimum
$l_{2}$ norm that induces a large misclassification fraction to this class
when added to images from another class (the source class). Since BPs embedded
by Eq. (1) usually have a very small $l_{2}$ norm for imperceptibility, the
pattern estimated for the true BA target class (if a BA exists) will likely
have a much smaller $l_{2}$ norm than for non-target classes. Thus,
unsupervised anomaly detection based on these perturbation sizes is performed
– when there is one BA target class and a sufficient number of non-target
classes, the statistic for the BA target class will likely be detected as an
anomaly compared with the others.

Except the RED above proposed by Xiang et al. (2020), existing REDs also
include Neural Cleanse (NC) proposed by Wang et al. (2019), which reverse-
engineers BPs embedded by Eq. (2) and uses the $l_{1}$ norm of the estimated
mask as the detection statistic. Guo et al. (2019) adds constraints to NC’s BP
reverse-engineering problem by considering various properties of BPs. Liu et
al. (2019) proposed a novel objective function for BP reverse-engineering
leveraging the abnormal internal neuron activations caused by the backdoor
mapping. Chen et al. (2019) constructs clean images for detection using model
inversion. Dong et al. (2021) queries the classifier for BP reverse-
engineering to address the “black-box” scenario. Wang et al. (2020) proposes a
detection statistic based on the similarity between universal and sample-wise
BP estimation.

Limitation of Existing REDs The anomaly detection of REDs heavily relies on
the assumption that there is a relatively large number of non-target classes,
thus providing a sufficient number of statistics to inform estimation of a
null distribution. But this assumption does not hold for domains with only two
classes. For example, Xiang et al. (2020) and Wang et al. (2019) exploit
$O(K^{2})$ and $O(K)$ statistics in estimating a null respectively, where $K$
is the number of classes. Both of these methods are unsuitable for 2-class
problems ($K=2$).

##  3 Method

Our main goals are detecting whether a given classifier is backdoor attacked
or not and, if so, finding out all the BA target classes. We focus on a
practical “post-training” scenario: S1) The defender has no access to the
classifier’s training set, nor any prior knowledge of the true BP used by an
attacker. S2) There are no clean classifiers trained for the same domain for
reference; and the defender is not capable of training such clean classifiers.
S3) The classification domain has two classes that can both be BA targets.
While we focus on two-class scenarios in this section, our method is more
generally applicable to multi-class scenarios, with arbitrary number of
attacks (see experiments in Sec. 4.4).

To address S1, our detection framework involves BP reverse-engineering using a
small, clean dataset independently collected by the defender, like existing
REDs. To address S3, unlike existing REDs that perform anomaly detection
involving statistics from all classes, we inspect each class independently
using a novel detection statistic called expected transferability (ET), which
can be empirically estimated for each class independently. To address S2, we
show that ET possesses a theoretically-grounded detection threshold value for
distinguishing BA target classes from non-target classes, one which depends
neither on the domain nor on the attack configuration. This is very different
from existing REDs, for which a suitable detection threshold for their
proposed statistics may be both domain and attack-dependent. For example, the
range of the $l_{1}$ norm of the estimated mask used by Wang et al. (2019)
depends on the image size. The practical import here is that the detection
threshold is a hyperparameter, but setting this threshold in a supervised
fashion (e.g. to achieve a specified false positive rate on a group of clean
classifiers) is generally infeasible due to S2. Use of ET thus obviates the
need for such hyperparameter setting.

In the following, we define ET in Sec. 3.1, and then, the constant threshold
on ET for BA detection is derived in Sec. 3.2. Finally, our detection
procedure, which consists of ET estimation and an inference step, is in Sec.
3.3. Note that our detection framework is effective for various types of BPs
(as will be shown experimentally). Solely for clarity, in this section, we
focus on BAs with additive perturbation BPs (Eq. (1)). Similar derivation for
BPs embedded by Eq. (2) is deferred to Apdx. C.

###  3.1 Expected Transferability (ET)

Consider a classifier $f:{\mathcal{X}}\rightarrow{\mathcal{C}}$ to be
inspected with category space ${\mathcal{C}}=\\{0,1\\}$ and continuous sample
distribution $P_{i}$ on ${\mathcal{X}}$ for class $i\in{\mathcal{C}}$. For any
${\bf x}\in{\mathcal{X}}$ from any class, the optimal solution to

$\underset{{\bf v}}{\text{minimize}}\,||{\bf v}||_{2}\quad\quad\text{subject
to}\,f({\bf x}+{\bf v})\neq f({\bf x})\vspace{-0.05in}$ (3)

is defined as ${\bf v}^{\ast}({\bf x})$. In practice, (3) can be viewed as a
typical BP reverse-engineering problem and solved using methods in existing
REDs like Xiang et al. (2020). It can also be practically solved by creating
an adversarial example for ${\bf x}$ using methods in, e.g., M.-Dezfooli et
al. (2016); Carlini & Wagner (2017). We present the following definition for
the set of practical solutions to (3).

######  Definition 3.1.

($\bm{\epsilon}$-solution set) For any sample ${\bf x}$ from any class,
regardless of the method being used, the $\epsilon$-solution set to problem
(3), is defined by

${\mathcal{V}}_{\epsilon}({\bf x})\triangleq\\{{\bf
v}\in{\mathcal{X}}\big{|}||{\bf v}||_{2}-||{\bf v}^{\ast}({\bf
x})||_{2}\leq\epsilon,f({\bf x}+{\bf v})\neq f({\bf x})\\},\vspace{-0.05in}$
(4)

where $\epsilon>0$ is the “quality gap” of practical solutions, which is
usually small for existing methods.

A practical solution to (3) for sample ${\bf x}$ may or may not cause a
misclassification when embedded in another sample ${\bf y}$ from the same
class. In the following, we first present the definition regarding such a
“transferability” property. Then, we define the ET statistic for any class
$i\in{\mathcal{C}}$.

######  Definition 3.2.

(Transferable set) The transferable set for any sample ${\bf x}$ and
$\epsilon>0$ is defined by

${\mathcal{T}}_{\epsilon}({\bf x})\triangleq\\{{\bf
y}\in{\mathcal{X}}\big{|}f({\bf y})=f({\bf x}),\exists{\bf
v}\in{\mathcal{V}}_{\epsilon}({\bf x})\,{\rm s.t.}\,f({\bf y}+{\bf v})\neq
f({\bf y})\\}.\vspace{-0.05in}$ (5)

######  Definition 3.3.

(ET statistic) For any class $i\in{\mathcal{C}}=\\{0,1\\}$ and $\epsilon>0$,
considering i.i.d. random samples ${\bf X},{\bf Y}\sim P_{i}$, the ET
statistic for class $i$ is defined by ${\rm
ET}_{i,\epsilon}\triangleq{\mathbb{E}}\big{[}{\rm P}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})|{\bf X})\big{]}$.

###  3.2 Using ET for BA Detection

Here, we show that for any $i\in{\mathcal{C}}=\\{0,1\\}$ and small $\epsilon$,
we will likely have ${\rm ET}_{i,\epsilon}>\frac{1}{2}$ when class $(1-i)$ is
a BA target class; and ${\rm ET}_{i,\epsilon}\leq\frac{1}{2}$ otherwise. Note
that this constant threshold does not rely on any specific data domain,
classifier architecture, or attack configuration; even for BPs embedded by Eq.
(2), the same threshold can be obtained following a similar derivation (see
Apdx. C).

We first present the following theorem showing the connection between ET and
the threshold $\frac{1}{2}$ regardless of the presence of any BA. Then, we
discuss the attack and non-attack cases, respectively.

######  Theorem 3.1.

For any class $i\in{\mathcal{C}}$ and $\epsilon>0$:

${\rm ET}_{i,\epsilon}=\frac{1}{2}+\frac{1}{2}({\rm P}_{{\rm MT,}i}-{\rm
P}_{{\rm NT,}i}),\vspace{-0.025in}$ (6)

with ${\rm P}_{{\rm MT,}i}$ a “mutual-transfer probability” and ${\rm P}_{{\rm
NT,}i}$ a “non-transfer probability”, defined by

${\rm P}_{{\rm MT,}i}\triangleq{\rm P}({\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf
X}),{\bf X}\in{\mathcal{T}}_{\epsilon}({\bf Y}))\quad{\rm and}\quad{\rm
P}_{{\rm NT,}i}\triangleq{\rm P}({\bf Y}\notin{\mathcal{T}}_{\epsilon}({\bf
X}),{\bf X}\notin{\mathcal{T}}_{\epsilon}({\bf Y}))\vspace{-0.05in}$ (7)

respectively, where ${\bf X}$ and ${\bf Y}$ are i.i.d. random samples
following distribution $P_{i}$ for class $i$.

1) Non-attack case: class $(1-i)$ is not a BA target class. We first focus on
${\rm P}_{{\rm NT,}i}$.

######  Property 3.1.

For general two-class domains in practice and small $\epsilon$, if class
$(1-i)$ is not a BA target class, ${\rm P}_{{\rm NT,}i}$ for class $i$ will
likely be larger than $\frac{1}{2}$ (see Sec. 4.3 for empirical support).

For any $i\in{\mathcal{C}}$, ${\rm P}_{{\rm NT,}i}$ is the probability that
two independent samples from class $i$ are mutually “not transferable”. For
such a pair of samples, the event associated with ${\rm P}_{{\rm NT,}i}$ is
that the pattern estimated for one (by solving (3)) does not induce the other
to be misclassified and vice versa. Accordingly, if we solve a problem similar
to (3) but requiring a common ${\bf v}$ that induces both samples to be
misclassified, the solution should have a larger norm than the solution to (3)
for each of them. Property 3.1 has been verified by many existing works for
general classification tasks commonly using highly non-linear classifiers. For
example, the universal adversarial perturbation studied by Moosavi-Dezfooli et
al. (2017) can be viewed as the solution to problem (3) (in absence of BA) for
a group of samples instead of one. Compared with the minimum sample-wise
perturbation required for each individual to be misclassified, the minimum
universal perturbation required for high group misclassification typically has
a much larger norm. Similar empirical results have also been shown by Xiang et
al. (2020) and inspired their proposed RED. Despite the evidence in existing
works, we also verify this property experimentally in Sec 4.3.

Next, we focus on ${\rm P}_{{\rm MT,}i}$. Note that ${\rm P}_{{\rm MT,}i}$ is
upper bounded by $1-{\rm P}_{{\rm NT,}i}$; thus it will likely be smaller than
$\frac{1}{2}$ (and even possibly close to 0) for the non-attack case based on
Property 3.1. The asymptotic behavior of ${\rm P}_{{\rm MT,}i}$ for small
$\epsilon$ can also be approached by the following theorem. Note that in
practice, a small $\epsilon$ is not difficult to achieve, since a solution to
problem (3) using, e.g., algorithms for generating adversarial samples Szegedy
et al. (2014) usually have a small norm.

######  Theorem 3.2.

For any class $i\in{\mathcal{C}}$ with continuous sample distribution $P_{i}$,
${\rm P}_{{\rm MT,}i}\rightarrow 0$ as $\epsilon\rightarrow 0$.

In summary, for the non-attack case with small $\epsilon$, we will likely have
${\rm P}_{{\rm NT,}i}\geq\frac{1}{2}\geq{\rm P}_{{\rm MT,}i}$; and thus, ${\rm
ET}_{i,\epsilon}\leq\frac{1}{2}$ (based on Thm. 3.1) – this will be shown by
our experiments. Moreover, in Apdx. B, for a simplified (yet still relatively
general) domain and a linear prototype classifier, we show that $\frac{1}{2}$
is a strict upper bound of the ET statistic when there is no BA.

2) Attack case: class $(1-i)$ is the target class of a successful BA. Suppose
${\bf v}_{0}$ is the BP for this attack, such that for any ${\bf X}\sim
P_{i}$, $f({\bf X})=i$, while $f({\bf X}+{\bf v}_{0})\neq f({\bf X})$.
Intuitively, ${\rm P}_{{\rm MT,}i}$ will be large and possibly close to 1
because, different from the non-attack case, there is a special pattern – the
BP ${\bf v}_{0}$ – that could likely be an element of
${\mathcal{V}}_{\epsilon}({\bf X})$ and ${\mathcal{V}}_{\epsilon}({\bf Y})$
simultaneously, for ${\bf X}$ and ${\bf Y}$ i.i.d. following $P_{i}$. In this
case, ${\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf X})$ and ${\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y})$ jointly hold (i.e. mutually
transferable) by Definition 3.2. Accordingly, ${\rm P}_{{\rm NT,}i}$ which is
upper bounded by $1-{\rm P}_{{\rm MT,}i}$ will likely be small and possibly
close to 0; then, we will have ${\rm P}_{{\rm MT,}i}>{\rm P}_{{\rm NT,}i}$ and
consequently, ${\rm ET}_{i,\epsilon}>\frac{1}{2}$ by Thm. 3.1.

Algorithm 1 BA detection using ET statistics.

1:Input: Classifier $f:{\mathcal{X}}\rightarrow{\mathcal{C}}$ for inspection;
clean dataset ${\mathcal{D}}_{i}=\\{{\bf x}_{1}^{(i)},\cdots,{\bf
x}_{N_{i}}^{(i)}\\}$ for each $i\in{\mathcal{C}}$.

2:Initialization: ${\rm attacked}=False$; ${\rm BA\\_targets}=\emptyset$.

3:for each putative target class $t\in{\mathcal{C}}=\\{0,1\\}$ do

4: Step 1: Obtain empirical estimation $\widehat{{\rm ET}}_{i,\epsilon}$ using
${\mathcal{D}}_{i}$ for $i=1-t$.

5: for $n=1:N_{i}$ do

6: $\widehat{{\mathcal{T}}}_{\epsilon}({\bf x}_{n}^{(i)})=\emptyset$; ${\rm
converge}=False$

7: while not converge do

8: Obtain an empirical solution $\hat{\bf v}({\bf x}_{n}^{(i)})$ to problem
(3) using random initialization.

9: $\widehat{{\mathcal{T}}}_{\epsilon}({\bf
x}_{n}^{(i)})\leftarrow\widehat{{\mathcal{T}}}_{\epsilon}({\bf
x}_{n}^{(i)})\cup\\{{\bf x}_{m}^{(i)}|m\in\\{1,\cdots,N_{i}\\}\setminus
n,f({\bf x}_{m}^{(i)}+\hat{\bf v}({\bf x}_{n}^{(i)}))\neq f({\bf
x}_{m}^{(i)})\\}$

10: if $\widehat{{\mathcal{T}}}_{\epsilon}({\bf x}_{n}^{(i)})$ unchanged for
$\tau$ iterations then

11: converge $\leftarrow$ $True$

12: $p_{n}^{(i)}=|\widehat{{\mathcal{T}}}_{\epsilon}({\bf
x}_{n}^{(i)})|/(N_{i}-1)$

13: $\widehat{{\rm
ET}}_{i,\epsilon}=\frac{1}{N_{i}}\sum_{n=1}^{N_{i}}p_{n}^{(i)}$

14: Step 2: Determine if class $t$ is a BA target class or not.

15: if $\widehat{{\rm ET}}_{i,\epsilon}>\frac{1}{2}$ then

16: ${\rm attacked}=True$; ${\rm BA\\_targets}\leftarrow{\rm
BA\\_targets}\cup\\{t\\}$

17:Output: ${\rm attacked}$; ${\rm BA\\_targets}$

Beyond the intuitive analysis above, the following theorem gives a guaranteed
large ET statistic (being exactly 1) in the attack case when the backdoor
pattern has a (sufficiently) small norm (which is in fact desired in order to
have imperceptibility of the attack).

######  Theorem 3.3.

If class $(1-i)$ is the target class of a successful BA with BP ${\bf v}_{0}$
such that $f({\bf X}+{\bf v}_{0})\neq f({\bf X})$ for all ${\bf X}\sim P_{i}$,
and if $||{\bf v}_{0}||_{2}\leq\epsilon$, we will have
$P({\mathcal{V}}_{\epsilon}({\bf X})\cap{\mathcal{V}}_{\epsilon}({\bf
Y})\neq\emptyset)=1$ for ${\bf X}$ and ${\bf Y}$ i.i.d. following $P_{i}$; and
furthermore, ${\rm ET}_{i,\epsilon}=1$.

###  3.3 Detection Procedure

Our detection procedure is summarized in Alg. 1. Basically, for each putative
target class $t\in{\mathcal{C}}=\\{0,1\\}$, we estimate the ET statistic
$\widehat{{\rm ET}}_{i,\epsilon}$ (with a “hat” representing empirical
estimation) for class $i=1-t$, and claim a detection if $\widehat{{\rm
ET}}_{i,\epsilon}>\frac{1}{2}$. In particular, the core to estimating
$\widehat{{\rm ET}}_{i,\epsilon}$ is to estimate ${\rm P}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})|{\bf X}={\bf x}_{n}^{(i)})$ for each
clean sample ${\bf x}_{n}^{(i)}\in{\mathcal{D}}_{i}$ used for detection (line
6-12, Alg. 1). To do so, we propose to find, for each ${\bf
x}_{n}^{(i)}\in{\mathcal{D}}_{i}$, the subset
$\widehat{\mathcal{T}}_{\epsilon}({\bf x}_{n}^{(i)})$ which contains all
samples in ${\mathcal{D}}_{i}\setminus{\bf x}_{n}^{(i)}$ belonging to the
transferable set ${\mathcal{T}}_{\epsilon}({\bf x}_{n}^{(i)})$ of sample ${\bf
x}_{n}^{(i)}$. Then, ${\rm P}({\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf X})|{\bf
X}={\bf x}_{n}^{(i)})$ can be estimated by
$p_{n}^{(i)}=|\widehat{{\mathcal{T}}}_{\epsilon}({\bf
x}_{n}^{(i)})|/(|{\mathcal{D}}_{i}|-1)$ (line 12, Alg. 1). However, by Def.
3.2, a sample ${\bf y}$ is in the transferable set
${\mathcal{T}}_{\epsilon}({\bf x})$ of a sample ${\bf x}$ as long as there
exists a practical solution to problem (3) (with some intrinsic quality gap
$\epsilon$) that induces ${\bf y}$ to be misclassified as well. Thus, it is
insufficient to decide whether or not a sample is in the transferable set of
another sample according to merely one solution realization to problem (3). To
address this, for each ${\bf x}_{n}^{(i)}$, we solve problem (3) repeatedly
with random initialization. For each practical solution, we embed it to all
elements in ${\mathcal{D}}_{i}\setminus{\bf x}_{n}^{(i)}$ and find those that
are misclassified – these samples are included into the subset
$\widehat{\mathcal{T}}_{\epsilon}({\bf x}_{n}^{(i)})$ (line 9, Alg. 1). Such
repetition stops when $\widehat{\mathcal{T}}_{\epsilon}({\bf x}_{n}^{(i)})$
stays unchanged for some $\tau$ iterations. This procedure is summarized as
the “while” loop in Alg. 1, which is guaranteed to converge in
$(N_{i}-1)\times\tau$ iterations. Finally, we obtain the estimated ET by
averaging $p_{n}^{(i)}$ – the empirical estimation of ${\rm P}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})|{\bf X}={\bf x}_{n}^{(i)})$ – over all
samples in ${\mathcal{D}}_{i}$.

Our detection framework has the following generalization capabilities. 1) BP
embedding mechanism. As mentioned before, our detection rule can be adapted to
BPs embedded by Eq. (2), with the same constant threshold $\frac{1}{2}$ on ET
and only little modification to the while loop in Alg. 1 (see Apdx. C.3). 2)
BP reverse-engineering algorithm. We do not limit our detector to any specific
algorithm when solving problem (3) (line 8 in Alg. 1) – existing algorithms
proposed by, e.g., Xiang et al. (2020); Carlini & Wagner (2017), and even
future BP reverse-engineering algorithms can be used. 3) Adoption for multi-
class scenario. When there are multiple classes, where each can possibly be a
BA target, Alg. 1 can still be used for detection by, for each putative target
class $t\in{\mathcal{C}}$, treating all the classes other than $t$ as a super-
class and estimating ET on $\cup_{i\in{\mathcal{C}}\setminus
t}{\mathcal{D}}_{i}$. In our experiments (next), we will evaluate our
detection framework considering a variety of these extensions.

##  4 Experiments

Our experiments involve six common benchmark image datasets with a variety of
image size and color scale: CIFAR-10, CIFAR-100 Krizhevsky (2012), STL-10
Coates et al. (2011), TinyImageNet, FMNIST Xiao et al. (2017), MNIST Lecun et
al. (1998). Details of these datasets are in Apdx. D.1.

###  4.1 Main Experiment: 2-Class, Multi-Attack BA Detection Using ET
Statistic

Generating 2-class domains. From CIFAR-10, we generate 45 different 2-class
domains (for all 45 unordered class pairs of CIFAR-10). From each of the other
five datasets, we generate 20 different random 2-class domains. More details
are provided in Apdx. D.2.

Attack configuration. Like most related works, we mainly focus on classical
BAs launched by poisoning the classifier’s training set with a small set of
samples embedded with a BP and labeled to some target class Gu et al. (2019).
Effectiveness of our detector against another type of clean-label BA is shown
in Apdx. E. For each 2-class domain generated from CIFAR-10, CIFAR-100,
STL-10, and TinyImageNet, we create two attack instances, one for BA with
additive perturbation BP embedded by Eq. (1), and the other for BA with patch
replacement BP embedded by Eq. (2). For each 2-class domain generated from
FMNIST and MNIST, we create one attack instance with additive perturbation
BP222Images from these two datasets commonly have a large area of “black”
background. Positively perturbing a few background pixels, which is a common
practice to achieve a successful BA Chen et al. (2018), is equivalent to
replacing these pixels with a gray patch using Eq. (2).. For convenience, the
six ensembles of attack instances with additive perturbation BP and for
2-class domains generated from CIFAR-10, CIFAR-100, STL-10, TinyImageNet,
FMNIST, and MNIST are denoted as A1-A6 respectively. The four ensembles of
attack instances with patch replacement BP and for 2-class domains generated
from CIFAR-10, CIFAR-100, STL-10, and TinyImageNet are denoted as A7-A10
respectively. The BPs used in our experiments include many popular ones in the
BA literature – examples of some BPs and images embedded with them are shown
in Fig. 1 (details for generating these BPs are deferred to Apdx. D.3).

(a) chessboard

(b) “L”

(c) “X”

(d) a pixel

(e) unicolor patch

(f) noisy patch

Figure 1: Part of the BPs used in our experiments (others in Apdx. D.3) and
images with these BPs embedded. (a)-(d) are additive perturbation BPs and
(e)-(f) are patch replacement BPs. BP in (a) is amplified for visualization.
Spatial locations for BPs in (b)-(f) are randomly selected for each attack.

We consider 2-class scenarios where both classes can possibly be a BA target
class. For each attack instance in ensembles A1, A2, A3, A7, A8, and A10, we
create two attacks each with one of the two classes being the BA target class.
For each instance in ensembles A4, A5, A6, and A9, we create one attack with
the second class being the BA target class. For each of these attacks, the BP
is randomly selected from the candidate BPs (part of which are shown in Fig.
1), with the specified BP type for the ensemble which the attack is associated
with. However, to avoid confusion for learning the backdoor mapping during
training, for all 2-attack instances with additive perturbation BPs, we ensure
that the BPs for the two attacks have different shapes (e.g., two “X” BPs are
not allowed). Similarly, for all 2-attack instances where the two attacks both
choose to use the unicolor patch BP (Fig. 1), we ensure that the colors for
the two BPs are significantly different. Other attack configurations,
including e.g., the poisoning rate for each attack are detailed in Apdx. D.4.

Training configurations. We train one classifier for each attack instance
using the poisoned training set. For each 2-class domain, we also train a
clean classifier to evaluate false detections. We denote the six ensembles of
clean instances for datasets CIFAR-10, CIFAR-100, STL-10, TinyImageNet,
FMNIST, and MNIST as C1-C6 respectively. For classifier training, we consider
a variety of DNN architectures (with two output neurons, one for each of the
two classes). For 2-class domains associated with CIFAR-10, CIFAR-100, and
STL-10, we use ResNet-18 He et al. (2016); for FMNIST, we use VGG-11 Simonyan
& Zisserman (2015); for TinyImageNet, we use ResNet-34; and for MNIST, we use
LeNet-5 Lecun et al. (1998). Other training configurations including the
learning rate, the batch size, and the optimizer choice for each 2-class
domain are detailed in Apdx. D.5. Moreover, all attacks for all the instances
are successful with high attack success rate and negligible degradation in
clean test accuracy – these two metrics are commonly used to evaluate the BA
effectiveness Wang et al. (2020). As a defense paper, we defer these attack
details to Apdx. D.5.

Table 1: Detection accuracy for RE-AP and RE-PR on attack ensembles A1-A10,
and on clean ensembles C1-C6, using the common threshold 1/2 on ET statistic.
“n/a” represents “not applicable”.

| A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10 | C1 | C2 | C3 | C4 | C5 | C6
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
RE-AP | 45/45 | 18/20 | 16/20 | 17/20 | 20/20 | 20/20 | n/a | n/a | n/a | n/a | 45/45 | 20/20 | 20/20 | 20/20 | 20/20 | 20/20
RE-PR | n/a | n/a | n/a | n/a | n/a | n/a | 45/45 | 20/20 | 19/20 | 19/20 | 39/45 | 19/20 | 20/20 | 16/20 | 18/20 | 19/20

Defense configurations. As mentioned in Sec. 3.3, our detection framework can
be easily generalized to incorporate a variety of algorithms for BP reverse-
engineering to detect various types of BP with different embedding mechanisms.
Here, we consider the algorithm proposed by Xiang et al. (2020) for estimating
Additive Perturbation BPs (by solving (3)), and the algorithm proposed by Wang
et al. (2019) for estimating Patch Replacement BPs (by solving (46) in Apdx.
C.1). For convenience, we denote detection configurations with these two
algorithms as RE-AP and RE-PR, respectively. Details for these two algorithms
are both introduced in the original papers and reviewed in Apdx. D.6.
Irrespective of the BP reverse-engineering algorithm, we use only 20 clean
images per class (similar to most existing REDs) for detection. Finally, we
set the “patience” parameter for determination of convergence in Alg. 1 to
$\tau$=4 – this choice is independent of the presence of BA; a larger $\tau$
will not change the resulting ET much, but only increase the execution time.

Detection performance (using the common ET threshold 1/2). In practice, our
detector with RE-AP and with RE-PR can be deployed in parallel to cover both
additive perturbation BPs and patch replacement BPs. Here, for simplicity, we
apply our detector with RE-AP to classifiers (with BAs using additive
perturbation BP) in ensemble A1-A6, and apply our detector with RE-PR to
classifiers (with BAs using patch replacement BP) in ensemble A7-A10. For each
classifier in clean ensembles C1-C6, we apply our detector with both
configurations. In Tab. 1, for each ensemble of attack instances, we report
the fraction of classifiers such that the attack and all BA target classes are
both successfully detected; for each ensemble of clean instances, we report
the fraction of classifiers that are inferred to be not attacked. Given the
large variety of classification domains, attack configurations, DNN
architectures, and defense generalizations mentioned above, using the common
ET threshold 1/2, we successfully detect most attacks with only very few false
detections (see Tab. 1). More discussions regarding the detection performance
are deferred to Apdx. K.

###  4.2 Compare ET with Other Statistics

The results for existing REDs applying to the attacks we created are neglected
for brevity, since these REDs cannot detect BAs for 2-class domains by their
design. However, we compare our ET statistic with some popular types of
statistic used by existing REDs in terms of their potential for being used to
distinguish BA target classes from non-target classes. The types of statistic
for comparison include: 1) the $l_{2}$ norm of the estimated additive
perturbation used by Xiang et al. (2020) (denoted by L2); 2) the $l_{1}$ norm
of the estimated mask used by Wang et al. (2019) (denoted by L1); and 3) the
(cosine) similarity between the BP estimated group-wise and the BP estimated
for each sample in terms of classifier’s internal layer representation Wang et
al. (2020) (denoted by CS).

Figure 2: Comparison between our ET statistic (for both RE-AP and RE-PR
configurations) and statistic types used by existing REDs (L1, L2, and CS).
Only for ET, there is a common range for all 2-class domains for choosing a
threshold to distinguish BA target classes (blue) from non-target classes
(orange). Such common range also contains the constant threshold 1/2 (red
dashed line).

For each type of statistic mentioned above and each benchmark dataset, we
consider all classifiers (with and without BA) trained for all 2-class domains
generated from the dataset, and plot a double histogram for statistics
obtained for all BA target classes and all non-target classes across these
classifiers respectively. For example, in the 1st column of Fig. 2, for our
detector with RE-AP, we plot a double histogram for ET statistics obtained for
all BA target classes and all non-target classes from all classifiers in each
of A1&C1, A2&C2, A3&C3, A4&C4, A5&C5, and A6&C6. Note that all classifiers in,
e.g., A1&C1 are trained for 2-class domains generated from CIFAR-10. Here, for
simplicity, for ET (with RE-AP) and L2 (both designated for additive
perturbation BP), we do not consider BA target classes with patch replacement
BP (e.g. associated with classifiers in A7-A10); for ET (with RE-PR), L1 and
CS (designated for patch replacement BP), we do not consider BA target classes
with additive perturbation BP (e.g. associated with classifiers in A1-A6).

Based on Fig. 2, for all types of statistics including our ET, statistics
obtained for BA target classes are generally separable from statistics
obtained for non-target classes for classifiers (with and without BA) trained
for 2-class domains generated from the same benchmark dataset (using same
training configurations including DNN architecture). But only for our ET
(obtained by both RE-AP and RE-PR), there is a common range (irrespective of
the classification domain, attack configurations, and training configurations)
for choosing a detection threshold to effectively distinguish BA target
classes from non-target classes for all instances; and such common range
clearly includes the constant threshold 1/2 (marked by red dashed lines in
Fig. 2) derived mathematically in Sec. 3. By contrast, for both L1 and L2, a
proper choice of detection threshold for distinguishing BA target classes from
non-target classes is domain dependent. For example, in the 4th column of Fig.
2, the $l_{1}$ norm of masks estimated for both BA target classes and non-
target classes for domains with larger image size (e.g. $96\times 96$ for
domains in A9&C3 generated from STL-10) is commonly larger than for domains
with smaller image size (e.g. $32\times 32$ for domains in A7&C1 generated
from CIFAR-10). The CS statistic, on the other hand, not only relies on the
domain, but also depends on the DNN architecture. More details regarding CS
are deferred to Apdx. D.7.

In summary, all the above mentioned types of statistics are suitable for BA
detection if there is supervision from the same domain for choosing the best
proper detection threshold. However, in most practical scenarios where such
supervision is not available, only our ET statistic with the common detection
threshold 1/2 can still be used to achieve a good detection performance.
Finally, in Fig. 3, we show the receiver operating characteristic (ROC) curves
associated with Fig. 2 for each of ET, L1, L2, and SC – our ET statistic has
clearly larger area under the ROC curve (very close to 1) than the other types
of statistics.

###  4.3 Experimental Verification of Property 3.1

We verify Property 3.1 by showing that, if a class is not a BA target class,
for any two clean images from the other class (considering 2-class domains),
the minimum additive perturbation required to induce both images to be
misclassified has a larger norm than the minimum perturbation required for
each of these two images to be misclassified. Here, we randomly choose one
clean classifier from each of C1-C6. For each classifier, we randomly choose
50 pairs of clean images from a random class of the associated 2-class domain
– these images are also used for detection in Sec. 4.1. For each pair of
images, we apply the same RE-AP algorithm (i.e. the BP reverse-engineering
algorithm proposed by Xiang et al. (2020) for additive perturbation BPs) on
the two images both jointly (to get a pair-wise common perturbation) and
separately (to get two sample-wise perturbationsfor the two images
respectively). Then, we divide the $l_{2}$ norm of the pair-wise perturbation
by the maximum $l_{2}$ norm of the two sample-wise perturbations to get a
ratio (which is more scale-insensitive than taking absolute difference). In
Fig. 5, we plot the histogram of such ratio for all image pairs for all six
classifiers – the ratio for most of the image pairs is greater than 1 (marked
by the red dashed line in Fig. 5). For these pairs, very likely that the
perturbation estimated for one sample cannot induce the other sample to be
misclassified and vise versa (otherwise their expected ratio will likely be
1).

(a) ET

(b) L2

(c) L1

(d) CS

Figure 3: ROC curves for ET, L1, L2, and SC in distinguishing BA target
classes from non-target classes for the large variety of classification
domains and attack configurations considered in Fig. 2.

Figure 4: Histogram of $l_{2}$ norm ratio between pair-wise additive
perturbation and maximum of the two sample-wise perturbations for each random
image pair for clean classifiers.

Figure 5: Maximum ET statistic over all classes for classifiers with one, two,
and three attacks respectively, and a clean classifier, for CIFAR-10,
CIFAR-100, and STL-10.

| 1 attack | 2 attacks | 3 attacks | clean
---|---|---|---|---
CIFAR-10 | 0.91 | 0.92 | 0.87 | 0
CIFAR-100 | 0.95 | 0.99 | 0.99 | 0.27
STL-10 | 0.65 | 0.83 | 0.77 | 4.3e-3

###  4.4 Multi-Class, Multi-Attack BA Detection Using ET Statistic

Since our detector inspects each class independently, it can also be used for
BA detection for more general scenarios with more than two classes and
arbitrary number of attacks (and BA target classes). For demonstration, for
each of CIFAR-10, CIFAR-100, and STL-10, we create three attack instances with
one, two, and three attacks, respectively (on the original domain). Additional
experiments with aggregated results are deferred to Apdx. L due to space
limitations. Here, we consider BAs with additive perturbation BPs for
simplicity. The target class and the shape of BP for each attack are randomly
selected. We train one classifier for each attack instance (thus, nine
classifiers being attacked in total). More details for these attacks and
training configurations are in Apdx. D.8. For each domain, we also train a
clean classifier (without BA) for evaluating false detections.

Following the description at the end of Sec. 3, we apply the generalized Alg.
1 with RE-AP to these classifiers. For CIFAR-10 and STL-10, we use three clean
images per class for detection; for CIFAR-100, we use only one clean image per
class for detection. Other detection configurations including the detection
threshold 1/2 are the same as in Sec. 4.1. Since a classifier is deemed to be
attacked if ET obtained for any class is greater than the threshold 1/2, for
each classifier, we show the maximum ET over all the classes in Tab. 5.
Clearly, the maximum ET is greater than 1/2 for all classifiers being attacked
and less than 1/2 for all clean classifiers. Thus, our detection framework
(with the same constant threshold on ET) is also applicable to multi-class,
multi-attack scenarios.

##  5 Conclusions

We proposed the first BA detector for two-class, multi-attack scenarios
without access to the classifier’s training set or any supervision from clean
reference classifiers trained for the same domain. Our detection framework is
based on BP reverse-engineering and a novel ET statistic. Our ET statistic can
be used to effectively distinguish BA target classes from non-target classes,
with a particular, theoretical-grounded threshold value 1/2, irrespective of
the classification domain, the DNN architecture, and the attack
configurations. Our detection framework can also be generalized to incorporate
a variety of BP reverse-engineering algorithms to address different BP types,
and be applied to multi-class scenarios with arbitrary number of attacks.

## Ethics Statement

The main purpose of this research is to understand the behavior of deep
learning systems facing malicious activities, and enhance their safety level
by unsupervised means. The backdoor attack considered this paper is well-
known, with open-sourced implementation code. Thus, publication of this paper
(with code released at https://github.com/zhenxianglance/2ClassBADetection)
will be beneficial to the community in defending backdoor attacks.

## References

  * A. Saha (2020) H. Pirsiavash A. Saha, A. Subramanya.  Hidden trigger backdoor attacks.  In _AAAI_ , 2020.
  * Carlini & Wagner (2017) N. Carlini and D. Wagner.  Towards evaluating the robustness of neural networks.  In _2017 IEEE Symposium on Security and Privacy (SP)_ , pp. 39–57, May 2017.
  * Chen et al. (2018) B. Chen, W. Carvalho, N. Baracaldo, H. Ludwig, B. Edwards, T. Lee, I. Molloy, and B. Srivastava.  Detecting backdoor attacks on deep neural networks by activation clustering.  http://arxiv.org/abs/1811.03728, Nov 2018.
  * Chen et al. (2019) H. Chen, C. Fu, J. Zhao, and F. Koushanfar.  Deepinspect: A black-box trojan detection and mitigation framework for deep neural networks.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_ , pp. 4658–4664, 7 2019.
  * Chen et al. (2017) X. Chen, C. Liu, B. Li, K. Lu, and D. Song.  Targeted backdoor attacks on deep learning systems using data poisoning.  https://arxiv.org/abs/1712.05526v1, 2017.
  * Chou et al. (2018) E. Chou, F. Tramèr, G. Pellegrino, and D. Boneh.  Sentinet: Detecting physical attacks against deep learning systems, 2018\.  URL http://arxiv.org/abs/1812.00292.
  * Coates et al. (2011) A. Coates, H. Lee, and A. Y. Ng.  An analysis of single layer networks in unsupervised feature learning.  In _AISTATS_ , 2011.
  * D. P. Kingma (2015) J. Ba D. P. Kingma.  Adam: A method for stochastic optimization.  In _ICLR_ , 2015.
  * Dong et al. (2021) Y. Dong, X. Yang, Z. Deng, T. Pang, Z. Xiao, H. Su, and J. Zhu.  Black-box detection of backdoor attacks with limited information and data.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * Du et al. (2020) M. Du, R. Jia, and D. Song.  Robust anomaly detection and backdoor attack detection via differential privacy.  In _Proc. ICLR_ , 2020.
  * Fredrikson et al. (2015) M. Fredrikson, S. Jha, and T. Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  CCS, 2015.
  * Gao et al. (2019a) Y. Gao, C. Xu, D. Wang, S. Chen, D. C. Ranasinghe, and S. Nepal.  STRIP: A defence against trojan attacks on deep neural networks.  In _Proc. ACSAC_ , 2019a.
  * Gao et al. (2019b) Z. Gao, A. Feng, X. Song, and X. Wu.  Target-dependent sentiment classification with bert.  _IEEE Access_ , 7:154290–154299, 2019b.
  * Gu et al. (2019) T. Gu, K. Liu, B. Dolan-Gavitt, and S. Garg.  Badnets: Evaluating backdooring attacks on deep neural networks.  _IEEE Access_ , 7:47230–47244, 2019.
  * Guo et al. (2019) W. Guo, L. Wang, X. Xing, M. Du, and D. Song.  TABOR: A highly accurate approach to inspecting and restoring Trojan backdoors in AI systems.  https://arxiv.org/abs/1908.01763, 2019.
  * He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proc. CVPR_ , 2016.
  * Huang et al. (2022) K. Huang, Y. Li, B. Wu, Z. Qin, and K. Ren.  Backdoor defense via decoupling the training process.  In _ICLR_ , 2022.
  * Kolouri et al. (2020) S. Kolouri, A. Saha, H. Pirsiavash, and H. Hoffmann.  Universal litmus patterns: Revealing backdoor attacks in cnns.  In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 298–307, 2020.
  * Krizhevsky (2012) A. Krizhevsky.  Learning multiple layers of features from tiny images.  _University of Toronto_ , 05 2012.
  * Lecun et al. (1998) Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Li et al. (2014) R. Li, W. Zhang, H.-I. Suk, L. Wang, J. Li, D. Shen, and S. Ji.  Deep learning based imaging data completion for improved brain disease diagnosis.  In _Medical Image Computing and Computer-Assisted Intervention – MICCAI 2014_ , pp. 305–312, 2014.
  * Li et al. (2020) Y. Li, B. Wu, Y. Jiang, Z. Li, and S.-T. Xia.  Backdoor learning: A survey, 2020.  URL https://arxiv.org/pdf/2004.04692.pdf.
  * Li et al. (2021) Y. Li, X. Lyu, N. Koren, L. Lyu, B. Li, and X. Ma.  Neural Attention Distillation: Erasing Backdoor Triggers from Deep Neural Networks.  In _Proc. ICLR_ , 2021.
  * Li et al. (2022) Y. Li, H. Zhong, X. Ma, Y. Jiang, and S.-T. Xia.  Few-shot backdoor attacks on visual object tracking.  In _ICLR_ , 2022.
  * Liu et al. (2018a) K. Liu, B. Doan-Gavitt, and S. Garg.  Fine-pruning: Defending against backdoor attacks on deep neural networks.  In _Proc. RAID_ , 2018a.
  * Liu et al. (2018b) Y. Liu, S. Ma, Y. Aafer, W.-C. Lee, and J Zhai.  Trojaning attack on neural networks.  In _Proc. NDSS_ , San Diego, CA, 2018b.
  * Liu et al. (2019) Y. Liu, W.-C. Lee, G. Tao, S. Ma, Y. Aafer, and X. Zhang.  Abs: Scanning neural networks for back-doors by artificial brain stimulation.  In _CCS_ , 2019.
  * M.-Dezfooli et al. (2016) S.-M. M.-Dezfooli, A. Fawzi, and P. Frossard.  DeepFool: a simple and accurate method to fool deep neural networks.  In _Proc. CVPR_ , 2016.
  * Madry et al. (2018) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  In _Proc. ICLR_ , 2018.
  * Miller et al. (2020) D. J. Miller, Z. Xiang, and G. Kesidis.  Adversarial learning in statistical classification: A comprehensive review of defenses against attacks.  _Proceedings of the IEEE_ , 108:402–433, 2020.
  * Moosavi-Dezfooli et al. (2017) S.-M. Moosavi-Dezfooli, A. Fawzi, and P. Frossard.  Universal adversarial perturbations.  In _Proc. CVPR_ , 2017.
  * Simonyan & Zisserman (2015) K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  In _ICLR_ , 2015.
  * Szegedy et al. (2014) C. Szegedy, W. Zaremba, I Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus.  Intriguing properties of neural networks.  In _Proc. ICLR_ , 2014.
  * Tran et al. (2018) B. Tran, J. Li, and A. Madry.  Spectral signatures in backdoor attacks.  In _Proc. NIPS_ , 2018.
  * Turner et al. (2019) A. Turner, D. Tsipras, and A. Madry.  Clean-label backdoor attacks.  https://people.csail.mit.edu/madry/lab/cleanlabel.pdf, 2019.
  * Wang et al. (2019) B. Wang, Y. Yao, S. Shan, H. Li, B. Viswanath, H. Zheng, and B.Y. Zhao.  Neural cleanse: Identifying and mitigating backdoor attacks in neural networks.  In _Proc. IEEE Symposium on Security and Privacy_ , 2019.
  * Wang et al. (2020) R. Wang, G. Zhang, S. Liu, P.-Y. Chen, J. Xiong, and M. Wang.  Practical detection of trojan neural networks: Data-limited and data-free cases.  In _Proc. ECCV_ , 2020.
  * Xiang et al. (2019) Z. Xiang, D.J. Miller, and G. Kesidis.  A benchmark study of backdoor data poisoning defenses for deep neural network classifiers and a novel defense.  In _Proc. IEEE MLSP_ , Pittsburgh, 2019.
  * Xiang et al. (2020) Z. Xiang, D. J. Miller, and G. Kesidis.  Detection of backdoors in trained classifiers without access to the training set.  _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–15, 2020.
  * Xiang et al. (2021a) Z. Xiang, D. J. Miller, S. Chen, X. Li, and G. Kesidis.  A backdoor attack against 3d point cloud classifiers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pp. 7597–7607, October 2021a.
  * Xiang et al. (2021b) Z. Xiang, D. J. Miller, and G. Kesidis.  Reverse engineering imperceptible backdoor attacks on deep neural networks for detection and training set cleansing.  _Computers and Security_ , 106, 2021b.
  * Xiang et al. (2021c) Z. Xiang, D. J. Miller, H. Wang, and G. Kesidis.  Detecting Scene-Plausible Perceptible Backdoors in Trained DNNs Without Access to the Training Set.  _Neural Computation_ , 33(5):1329–1371, 2021c.
  * Xiao et al. (2017) H. Xiao, K. Rasul, and R. Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.  URL http://arxiv.org/abs/1708.07747.
  * Xu et al. (2020) H. Xu, Y. Ma, H.-C. Liu, D. Deb, H. Liu, J.-L. Tang, and A. K. Jain.  Adversarial attacks and defenses in images, graphs and text: A review.  _International Journal of Automation and Computing_ , 17:151–178, 2020.
  * Xu et al. (2021) X. Xu, Q. Wang, H. Li, N. Borisov, C. A. Gunter, and B. Li.  Detecting AI Trojans Using Meta Neural Analysis.  In _Proc. IEEE Symposium on Security and Privacy_ , 2021.
  * Zhai et al. (2021) T. Zhai, Y. Li, Z. Zhang, B. Wu, Y. Jiang, and S.-T. Xia.  Backdoor attack against speaker verification.  In _ICASSP_ , 2021.
  * Zhong et al. (2020) H. Zhong, C. Liao, A. Squicciarini, S. Zhu, and D.J. Miller.  Backdoor embedding in convolutional neural network models via invisible perturbation.  In _Proc. CODASPY_ , 2020.

##  Appendix A Proof of Theorems in the Main Paper

###  A.1 Proof of Theorem 3.1

For random variables ${\bf X}$ and ${\bf Y}$ i.i.d. following distribution
$P_{i}$, for any realization ${\bf x}$ of ${\bf X}$, we have

${\rm P}({\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf x}))={\rm P}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})|{\bf X}={\bf
x})={\mathbb{E}}\big{[}\mathds{1}({\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf
X}))\big{|}{\bf X}={\bf x}\big{]}$ (8)

Thus, ET, the left hand side of Eq. (6), can be written as

${\mathbb{E}}\big{[}{\rm P}({\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf X})|{\bf
X})\big{]}={\mathbb{E}}\big{[}\mathds{1}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X}))\big{]}={\rm P}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X}))$ (9)

Based on the inclusion-exclusion rule

${\rm P}({\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf X}))+{\rm P}({\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y}))=1+{\rm P}_{{\rm MT,}i}-{\rm P}_{{\rm
NT,}i}$ (10)

Since, ${\bf X}$ and ${\bf Y}$ are i.i.d. random variables, ${\rm P}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X}))={\rm P}({\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y}))$; thus, we get Eq. (6).

###  A.2 Proof of Theorem 3.2

Step 1: We show that for any $i\in{\mathcal{C}}$ and ${\bf X}$, ${\bf Y}$
i.i.d. following distribution $P_{i}$, ${\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y})$ and ${\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})$ if and only if
${\mathcal{V}}_{\epsilon}({\bf X})\cap{\mathcal{V}}_{\epsilon}({\bf
Y})\neq\emptyset$.

(a) If ${\mathcal{V}}_{\epsilon}({\bf X})\cap{\mathcal{V}}_{\epsilon}({\bf
Y})\neq\emptyset$, there exists ${\bf v}$ such that ${\bf
v}\in{\mathcal{V}}_{\epsilon}({\bf X})$ and ${\bf
v}\in{\mathcal{V}}_{\epsilon}({\bf Y})$. By Definition 3.1,

$\displaystyle{\bf v}\in{\mathcal{V}}_{\epsilon}({\bf X})\Rightarrow f({\bf
X}+{\bf v})\neq f({\bf X})$ (11) $\displaystyle{\bf
v}\in{\mathcal{V}}_{\epsilon}({\bf Y})\Rightarrow f({\bf Y}+{\bf v})\neq
f({\bf Y})$ (12)

Then, by Definition 3.2, the existence of such ${\bf v}$ yields ${\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y})$ and ${\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})$.

(b) We prove the “only if” part by contradiction. Given ${\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y})$ and ${\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})$, suppose
${\mathcal{V}}_{\epsilon}({\bf X})\cap{\mathcal{V}}_{\epsilon}({\bf
Y})=\emptyset$. By Definition 3.2, if ${\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf
X})$, there exists ${\bf v}\in{\mathcal{V}}_{\epsilon}({\bf X})$ such that
$f({\bf Y}+{\bf v})\neq f({\bf Y})$. Since ${\mathcal{V}}_{\epsilon}({\bf
X})\cap{\mathcal{V}}_{\epsilon}({\bf Y})=\emptyset$, ${\bf
v}\notin{\mathcal{V}}_{\epsilon}({\bf Y})$; hence, by Definition 3.1

$||{\bf v}||_{2}-||{\bf v}^{\ast}({\bf Y})||_{2}>\epsilon.$ (13)

Similarly, there exists ${\bf v}^{\prime}\in{\mathcal{V}}_{\epsilon}({\bf Y})$
such that $f({\bf X}+{\bf v}^{\prime})\neq f({\bf X})$ and ${\bf
v}^{\prime}\notin{\mathcal{V}}_{\epsilon}({\bf X})$; hence

$||{\bf v}^{\prime}||_{2}-||{\bf v}^{\ast}({\bf X})||_{2}>\epsilon.$ (14)

By Definition 3.1, for all ${\bf u}\in{\mathcal{V}}_{\epsilon}({\bf Y})$,
$||{\bf u}||_{2}-||{\bf v}^{\ast}({\bf Y})||_{2}<\epsilon$. Thus, we have

$||{\bf v}||_{2}-||{\bf v}^{\ast}({\bf Y})||_{2}>||{\bf u}||_{2}-||{\bf
v}^{\ast}({\bf Y})||_{2}$ (15)

and accordingly $||{\bf v}||_{2}>||{\bf u}||_{2}$ for all ${\bf
u}\in{\mathcal{V}}_{\epsilon}({\bf Y})$. Similarly, for all ${\bf
u}^{\prime}\in{\mathcal{V}}_{\epsilon}({\bf X})$, we have

$||{\bf v}^{\prime}||_{2}-||{\bf v}^{\ast}({\bf X})||_{2}>||{\bf
u}^{\prime}||_{2}-||{\bf v}^{\ast}({\bf X})||_{2}$ (16)

and thus, $||{\bf v}^{\prime}||_{2}>||{\bf u}^{\prime}||_{2}$ for all ${\bf
u}^{\prime}\in{\mathcal{V}}_{\epsilon}({\bf X})$. Clearly, there is a
contradiction since there cannot exist an element in one set having a larger
norm than all elements in another set while vise versa; and therefore,
${\mathcal{V}}_{\epsilon}({\bf X})\cap{\mathcal{V}}_{\epsilon}({\bf
Y})\neq\emptyset$.

Step 2: We show that the upper bound for ${\rm P}_{{\rm MT,}i}$ goes to 0 when
$\epsilon\rightarrow 0$. Note that $\epsilon$ is the “quality gap” between the
practical solution and the optimal solution.

Note that by Definition 3.1, ${\mathcal{V}}_{\epsilon}({\bf
X})\cap{\mathcal{V}}_{\epsilon}({\bf Y})\neq\emptyset$ only if $\big{|}||{\bf
v}^{\ast}({\bf X})||_{2}-||{\bf v}^{\ast}({\bf Y})||_{2}\big{|}\leq\epsilon$;
also based on Step 1:

${\rm P}_{{\rm MT,}i}={\rm P}({\mathcal{V}}_{\epsilon}({\bf
X})\cap{\mathcal{V}}_{\epsilon}({\bf Y})\neq\emptyset)\leq{\rm
P}(\big{|}||{\bf v}^{\ast}({\bf X})||_{2}-||{\bf v}^{\ast}({\bf
Y})||_{2}\big{|}\leq\epsilon).$ (17)

For ${\bf X}$ following continuous distribution $P_{i}$, $||{\bf
v}^{\ast}({\bf X})||_{2}$ also follows some continuous distribution333One can
construct very extreme cases such that ${\rm P}(||{\bf v}^{\ast}({\bf
X})||_{2}=d)>0$ for some constant $d>0$. In other words, there is a set of
samples from class $i$ with non-negligible probability that are equal distant
to the decision boundary. However, the probability for these cases is zero for
practical domains and highly non-linear classifiers. on $(0,+\infty)$. Since
${\bf X}$ and ${\bf Y}$ are i.i.d., the right hand side of Eq. (17) goes to 0
as $\epsilon\rightarrow 0$.

###  A.3 Proof of Theorem 3.3

For any ${\bf X}\sim P_{i}$, since ${\bf v}_{0}$ satisfies $f({\bf X}+{\bf
v}_{0})\neq f({\bf X})$ and

$||{\bf v}_{0}||_{2}-||{\bf v}^{\ast}({\bf X})||_{2}<||{\bf
v}_{0}||_{2}\leq\epsilon,$ (18)

${\bf v}_{0}\in{\mathcal{V}}_{\epsilon}({\bf X})$ by Definition 3.1. Thus,
${\bf v}_{0}\in{\mathcal{V}}_{\epsilon}({\bf
X})\cap{\mathcal{V}}_{\epsilon}({\bf Y})$ for ${\bf X}$ and ${\bf Y}$ i.i.d.
following $P_{i}$; and

$P({\mathcal{V}}_{\epsilon}({\bf X})\cap{\mathcal{V}}_{\epsilon}({\bf
Y})\neq\emptyset)=1.$ (19)

Thus, based on Step 1 (and Eq. (17)) in Apdx A.2, we have ${\rm P_{MT}}=1$.
Since ${\rm P_{MT}}+{\rm P_{NT}}\leq 1$, Eq. (6) can be written as

${\rm ET}_{i,\epsilon}\geq\frac{1}{2}+\frac{1}{2}({\rm P_{MT}}-1+{\rm
P_{MT}})={\rm P_{MT}}$ (20)

Then we have

${\rm ET}_{i,\epsilon}=1.$ (21)

##  Appendix B Analysis on a Simplified Classification Problem

In this section, we consider a simplified analogue to practical 2-class
classification problems. Although assumptions are imposed for simplicity, we
still keep the problem relatively general by allowing freedom on, e.g., the
sample distribution in their latent space. With the simplification, we are
able to analytically derive the condition for a sample belonging to the
transferable set of another sample from the same class. Based on this, we show
that $\frac{1}{2}$ is the supremum of the ET statistic for this problem when
there is no attack. Note that we will abuse some notations that appeared in
the main paper; the notations in this section are all self-contained.

###  B.1 Problem Settings

We consider sample space ${\mathbb{R}}^{n}$ with an orthonormal basis
$\\{\bm{\alpha}_{1},\cdots,\bm{\alpha}_{d},\bm{\beta}_{1},\cdots,\bm{\beta}_{n-d}\\}$.
We assume that samples from the two classes are distributed on sub-spaces
$V_{0}=\\{{\bf Ac}|{\bf c}\in{\mathbb{R}}^{d}\\}$ and $V_{1}=\\{{\bf Be}|{\bf
e}\in{\mathbb{R}}^{n-d}\\}$ respectively, with ${\bf
A}=[\bm{\alpha}_{1},\cdots,\bm{\alpha}_{d}]$ and ${\bf
B}=[\bm{\beta}_{1},\cdots,\bm{\beta}_{n-d}]$. By the definition of $V_{0}$ and
$V_{1}$, we have also defined the latent spaces, i.e. ${\mathbb{R}}^{d}$ and
${\mathbb{R}}^{n-d}$, for the two classes. Here, we do not constrain the form
or parameters of the distributions for the two classes in both the sample
space ${\mathbb{R}}^{n}$ and latent spaces, as long as the distributions are
continuous. Such an analogue may be corresponding to some simple
classification domains in practice. Moreover, the latent space may be
corresponding to an internal layer space of some deep neural network (DNN)
classifier. For example, for a typical ReLU DNN classifier, it is possible
that a subset of nodes in the penultimate layer are mainly activated for one
class, while another subset of nodes are mainly activated for the other class.

For this simplified domain, we consider a nearest prototype classifier that is
capable of classifying the two classes perfectly for any continuous sample
distributions. To achieve this, any point ${\bf x}\in{\mathbb{R}}^{n}$ on the
decision boundary of the classifier should have equal distance to $V_{0}$ and
$V_{1}$, i.e.:

$||{\bf A}{\bf A}^{T}{\bf x}-{\bf x}||_{2}=||{\bf B}{\bf B}^{T}{\bf x}-{\bf
x}||_{2}$ (22)

By expanding both sides of Eq. (22) and rearranging terms (using the fact that
${\bf A}^{T}{\bf A}={\bf I}$ and ${\bf B}^{T}{\bf B}={\bf I}$), we obtain the
decision boundary of the classifier, which is $\\{{\bf
x}\in{\mathbb{R}}^{n}|{\bf x}({\bf A}{\bf A}^{T}-{\bf B}{\bf B}^{T}){\bf
x}=0\\}$. In other words, the classifier
$f:{\mathbb{R}}^{n}\rightarrow\\{0,1\\}$ is defined by

$f({\bf x})=\begin{cases}0&{\bf x}({\bf A}{\bf A}^{T}-{\bf B}{\bf B}^{T}){\bf
x}>0\\\ 1&{\bf x}({\bf A}{\bf A}^{T}-{\bf B}{\bf B}^{T}){\bf x}\leq 0\\\
\end{cases}$ (23)

Note that this classifier is not necessarily linear; and the region for each
class may not be convex.

###  B.2 Derivation of Transfer Condition

We derive the condition that one sample belongs to the transferable set of
another sample from the same class. Since the two classes are symmetric, we
focus on class 0 for brevity. Moreover, in this section, we refer to samples
by their latent space representation; i.e., instead of “a sample ${\bf
x}\in{\mathbb{R}}^{n}$ from class 0”, we use “a sample ${\bf
c}\in{\mathbb{R}}^{d}$”.

First, we present the following modified definition of the transferable set
(compared with Def. 3.2 in the main paper) using latent space representation.

######  Definition B.1.

(Transferable set in latent space) The transferable set for any sample ${\bf
c}\in{\mathbb{R}}^{d}$ from class 0 is defined by

${\mathcal{T}}({\bf c})=\\{{\bf c}^{\prime}\in{\mathbb{R}}^{d}\big{|}f({\bf
Ac}^{\prime})=f({\bf Ac}),f({\bf Ac^{\prime}}+{\bf v}^{\ast}({\bf c}))\neq
f({\bf Ac}^{\prime})\\},$ (24)

where ${\bf v}^{\ast}({\bf c})$ is the optimal solution to

$\underset{{\bf v}\in{\mathbb{R}}^{n}}{\text{minimize}}\,||{\bf
v}||_{2}\quad\quad\text{subject to}\,f({\bf Ac}+{\bf v})\neq f({\bf Ac}).$
(25)

Note that the above definition is in similar form to Def. 3.2 in the main
paper, though here, the quality to the solution to problem (25) is no longer
considered. This is because, different with problem (3) in the main paper
(which is the prerequisite of Def. 3.2), problem (25) here can be solved
analytically, yielding a close form solution instead of a solution set with
some intrinsic quality bound $\epsilon$. Accordingly, we present the following
theorem, which gives the condition for one sample belonging to the
transferable set of another sample from the same class.

######  Theorem B.1.

For any ${\bf c},{\bf c}^{\prime}\in{\mathbb{R}}^{d}$, ${\bf
c}^{\prime}\in{\mathcal{T}}({\bf c})$ if and only if $||{\bf c}^{\prime}-{\bf
c}/2||_{2}\leq||{\bf c}/2||_{2}$.

###### Proof.

First, we derive the solution to problem (25). Note that ${\bf
v}\in{\mathbb{R}}^{n}$ can be decomposed (using the orthonormal basis
specified by ${\bf A}$ and ${\bf B}$) as ${\bf v}={\bf A}{\bf v}_{a}+{\bf
B}{\bf v}_{b}$ with ${\bf v}_{a}\in{\mathbb{R}}^{d}$ and ${\bf
v}_{b}\in{\mathbb{R}}^{n-d}$. We substitute this decomposition into the
constraint of problem (25). In words, the constraint means that ${\bf v}$
induces ${\bf Ac}$ to be (mis)classified to class 1; thus, according to the
expression of the classifier in Eq. (23), the constraint can be written as

$({\bf Ac}+{\bf A}{\bf v}_{a}+{\bf B}{\bf v}_{b})^{T}({\bf A}{\bf A}^{T}-{\bf
B}{\bf B}^{T})({\bf Ac}+{\bf A}{\bf v}_{a}+{\bf B}{\bf v}_{b})\leq 0.$ (26)

Expanding the left hand side of the above inequality and using the fact that
${\bf A}^{T}{\bf B}=0$ for simplification, we get a much simpler expression of
the constraint:

$||{\bf v}_{a}+{\bf c}||_{2}\leq||{\bf v}_{b}||_{2}.$ (27)

Thus, a lower bound of the (square of the) objective to be minimized in
problem (25) can be derived as

$||{\bf v}||_{2}^{2}=||{\bf A}{\bf v}_{a}+{\bf B}{\bf v}_{b}||_{2}^{2}=||{\bf
v}_{a}||_{2}^{2}+||{\bf v}_{b}||_{2}^{2}\geq||{\bf v}_{a}||_{2}^{2}+||{\bf
v}_{a}+{\bf c}||_{2}^{2},$ (28)

with equality holds if and only if $||{\bf v}_{b}||_{2}=||{\bf v}_{a}+{\bf
c}||$, i.e. ${\bf Ac}+{\bf v}$ on the decision boundary of the classifier.
Note that the right hand side of the inequality above is minimized when ${\bf
v}_{a}=-\frac{\bf c}{2}$. Then, the optimal solution ${\bf v}^{\ast}({\bf
c})={\bf A}{\bf v}_{a}^{\ast}(\bf c)+{\bf B}{\bf v}_{b}^{\ast}(\bf c)$ to
problem (25) satisfies:

$\displaystyle\begin{cases}{\bf v}_{a}^{\ast}(\bf c)=-\frac{\bf c}{2},\\\
||{\bf v}_{b}^{\ast}({\bf c})||_{2}=\frac{||{\bf c}||_{2}}{2}.\end{cases}$
(29)

Next, for any ${\bf c},{\bf c}^{\prime}\in{\mathbb{R}}^{d}$, we derive the
condition for ${\bf c}^{\prime}\in{\mathcal{T}}({\bf c})$. Since $f({\bf
Ac}^{\prime})=f({\bf Ac})$ is already satisfied, by Def. B.1, ${\bf
c}^{\prime}\in{\mathcal{T}}({\bf c})$ if and only if $f({\bf Ac^{\prime}}+{\bf
v}^{\ast}({\bf c}))\neq f({\bf Ac}^{\prime})$, which is equivalent to (by Eq.
(23))

$({\bf Ac^{\prime}}+{\bf v}^{\ast}({\bf c}))^{T}({\bf A}{\bf A}^{T}-{\bf
B}{\bf B}^{T})({\bf Ac^{\prime}}+{\bf v}^{\ast}({\bf c}))\leq 0.$ (30)

Using the decomposition of ${\bf v}^{\ast}({\bf c})$, expanding and
rearranging terms on the left hand side of the above, we obtain

${\bf c}^{\prime T}{\bf c}^{\prime}+{\bf v}_{a}^{\ast}({\bf c})^{T}{\bf
v}_{a}^{\ast}({\bf c})-{\bf v}_{b}^{\ast}({\bf c})^{T}{\bf v}_{b}^{\ast}({\bf
c})+2{\bf c}^{\prime T}{\bf v}_{a}^{\ast}({\bf c})\leq 0.$ (31)

With the optimal solution in Eq. (29) substituted in, we get

${\bf c}^{\prime T}({\bf c}^{\prime}-{\bf c})\leq 0,$ (32)

or, equivalently

$||{\bf c}^{\prime}-{\bf c}/2||_{2}\leq||{\bf c}/2||_{2}.$ (33)

∎

###  B.3 Upper Bound on ET Statistic

In this section, we show that $\frac{1}{2}$ is the minimum upper bound on the
ET statistic for this problem when there is no BA. To do so, we first present
a definition of ET statistic modified from Def 3.3 in the main paper, merely
in adaption to the latent space representation used here (see Def. B.2). Then,
we show the tightness of the bound by giving a concrete example where ET
equals $\frac{1}{2}$ in Lem. B.1. Finally, we prove that the ET statistic
cannot be greater than $\frac{1}{2}$.

######  Definition B.2.

For i.i.d. random samples ${\bf C}$ and ${\bf C}^{\prime}$ following some
continuous distribution $G$ on ${\mathbb{R}}^{d}$, the ET statistic is defined
by

${\rm ET}={\mathbb{E}}_{{\bf C}\sim G}\big{[}{\rm P}({\bf
C}^{\prime}\in{\mathcal{T}}({\bf C})|{\bf C})\big{]}$ (34)

######  Lemma B.1.

For latent space ${\mathbb{R}}^{d}$ with dimension $d=1$ and distribution $G$
continuous on ${\mathbb{R}}$, the ET statistic satisfies

$\frac{1}{4}\leq{\rm ET}\leq\frac{1}{2},$ (35)

where ${\rm ET}=\frac{1}{2}$ if and only if $G(0)=0$ or $G(0)=1$.

###### Proof.

Based on Thm. B.1, for latent space dimension $d=1$ and two scalar444We do not
use bold ${\bf C}$ but $C$ instead, since it is given as a scalar random
variable. i.i.d. random samples $C$ and $C^{\prime}$ with continuous
distribution $G$, $C^{\prime}\in{\mathcal{T}}(C)$ if and only if
$|C^{\prime}-C/2|\leq|C/2|$. Thus, by Def. B.2, we have

$\displaystyle{\rm ET}_{(d=1)}=$ $\displaystyle{\mathbb{E}}_{C\sim
G}[G(\frac{C}{2}+\frac{|C|}{2})-G(\frac{C}{2}-\frac{|C|}{2})]$ (36)
$\displaystyle=$
$\displaystyle\int_{-\infty}^{\infty}[G(\frac{c}{2}+\frac{|c|}{2})-G(\frac{c}{2}-\frac{|c|}{2})]g(c)dc$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{0}[G(0)-G(c)]g(c)dc+\int_{0}^{\infty}[G(c)-G(0)]g(c)dc$
$\displaystyle=$
$\displaystyle\int_{0}^{G(0)}[G(0)-G(c)]dG(c)+\int_{G(0)}^{1}[G(c)-G(0)]dG(c)$
$\displaystyle=$ $\displaystyle
G(0)^{2}-\frac{1}{2}G(0)^{2}+\frac{1}{2}[1-G(0)^{2}]-G(0)[1-G(0)]$
$\displaystyle=$ $\displaystyle\frac{1}{2}-G(0)+G(0)^{2},$

where $g(\cdot)$ is the density function of distribution $G$. Note that the
last line of Eq. (36) is strictly in the interval $[\frac{1}{4},\frac{1}{2}]$
for $G(\cdot)$ in range $[0,1]$. The upper bound of ET when $d=1$ is
$\frac{1}{2}$, which is achieved if and only if $G(0)=0$ or $G(0)=1$. ∎

######  Theorem B.2.

For arbitrary $d\in{\mathbb{Z}}_{+}$ and continuous distribution $G$ on
${\mathbb{R}}^{d}$

$\underset{d,G}{\text{sup}}\quad{\rm ET}=\frac{1}{2}.$ (37)

###### Proof.

By Lem. B.1, there exists $d=1$ and $G(0)=0$ or $G(0)=1$, such that ${\rm
ET}=\frac{1}{2}$. Here, we only need to show that ${\rm ET}\leq\frac{1}{2}$
for any $d$ and $G$. Again, by the definition of ET (Def. B.2) and Thm. B.1,
we can write ET as

${\rm ET}={\mathbb{E}}_{{\bf C}\sim G}\Big{[}{\rm P}(||{\bf
C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf C}}{2}||_{2})|{\bf
C}\Big{]},$ (38)

for ${\bf C}$ and ${\bf C}^{\prime}$ i.i.d. following distribution $G$.
Similar to our proof of Thm. 3.1 in Sec. A.1

${\rm P}(||{\bf C}^{\prime}-\frac{\bf c}{2}||_{2}\leq||\frac{{\bf
c}}{2}||_{2})={\mathbb{E}}_{{\bf C^{\prime}}\sim G}\Big{[}\mathds{1}\\{||{\bf
C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf C}}{2}||_{2}\\}\Big{|}{\bf
C}={\bf c}\Big{]}.$ (39)

Thus, based on Eq. (38) and (39), ET can be written as

${\rm ET}={\mathbb{E}}_{{\bf C,C^{\prime}}\sim G}\Big{[}\mathds{1}\\{||{\bf
C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf C}}{2}||_{2})\\}\Big{]}={\rm
P}(||{\bf C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf C}}{2}||_{2})$
(40)

Since ${\bf C}$ and ${\bf C}^{\prime}$ are i.i.d,

${\rm P}(||{\bf C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf
C}}{2}||_{2})={\rm P}(||{\bf C}-\frac{\bf C^{\prime}}{2}||_{2}\leq||\frac{{\bf
C^{\prime}}}{2}||_{2})$ (41)

Also note that for continuous distribution

$\displaystyle{\rm P}(||{\bf C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf
C}}{2}||_{2},||{\bf C}-\frac{\bf C^{\prime}}{2}||_{2}\leq||\frac{{\bf
C^{\prime}}}{2}||_{2})$ (42) $\displaystyle\leq$ $\displaystyle{\rm P}(||{\bf
C}^{\prime}-\frac{\bf C}{2}||_{2}^{2}+||{\bf C}-\frac{\bf
C^{\prime}}{2}||_{2}^{2}\leq||\frac{{\bf C}}{2}||_{2}^{2}+||\frac{{\bf
C^{\prime}}}{2}||_{2}^{2})$ $\displaystyle=$ $\displaystyle{\rm P}(||{\bf
C}-{\bf C}^{\prime}||_{2}^{2}\leq 0)$ $\displaystyle=$ $\displaystyle 0$

Then, by the inclusion-exclusion rule

$\displaystyle{\rm P}(||{\bf C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf
C}}{2}||_{2})+{\rm P}(||{\bf C}-\frac{\bf C^{\prime}}{2}||_{2}\leq||\frac{{\bf
C^{\prime}}}{2}||_{2})$ (43) $\displaystyle-{\rm P}(||{\bf
C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf C}}{2}||_{2},||{\bf
C}-\frac{\bf C^{\prime}}{2}||_{2}\leq||\frac{{\bf
C^{\prime}}}{2}||_{2})\leq\,1,$

Substituting Eq. (41) and (42) into Eq. (43), we have

${\rm P}(||{\bf C}^{\prime}-\frac{\bf C}{2}||_{2}\leq||\frac{{\bf
C}}{2}||_{2})\leq\frac{1}{2},$ (44)

thus, by Eq. (40)

${\rm ET}\leq\frac{1}{2}$ (45)

which finishes the proof. ∎

##  Appendix C Using ET to Detect BA with Patch Replacement BP

In the main paper, we have described our detection framework in details
considering additive perturbation BPs embedded by Eq. (1). In fact, our
detection framework is not specific to any particular backdoor embedding
mechanism. In this section, we repeat our derivation and analysis in Sec. 3 by
considering patch replacement BPs embedded by Eq. (2). Basically, the
definitions, theorems and algorithms presented in this section are matched
with those in the main paper – they are under the same framework which is
generally independent of the backdoor pattern embedding mechanism.

Like the organization of Sec. 3, in this section, we first introduce several
definitions related to ET but for patch replacement BPs – these definitions
are similar to those in the main paper and are customized to patch replacement
BPs. Especially, the ET statistic is defined in the same fashion as in Def.
3.3 of the main paper. Then, we show that the same constant detection
threshold $\frac{1}{2}$ on the ET statistic for detecting BAs with with
additive perturbation BPs can be used for detecting BAs with patch replacement
BPs as well. Finally, we present the detailed procedure of our detection for
patch replacement BPs (as the counterpart of Alg. 1 of the main paper). Again,
this section can be viewed as an independent section, where the notations are
self-contained.

###  C.1 Definition of ET for Patch Replacement BP

Consider the same classifier $f:{\mathcal{X}}\rightarrow{\mathcal{C}}$ to be
inspected (as in the main paper) with the same label space
${\mathcal{C}}=\\{0,1\\}$ and continuous sample distribution $P_{i}$ on
${\mathcal{X}}$ for class $i\in{\mathcal{C}}$. For any sample ${\bf x}$ from
any class, the optimal solution to

$\underset{{\bf s}=\\{{\bf m},{\bf u}\\}}{\text{minimize}}\,||{\bf
m}||_{1}\quad\quad\text{subject to}\,f(\bm{\Delta}({\bf x};{\bf m},{\bf
u}))\neq f({\bf x})$ (46)

is defined as ${\bf s}^{\ast}({\bf x})=\\{{\bf m}^{\ast}(\bf x),{\bf
u}^{\ast}({\bf x})\\}$, where $\bm{\Delta}({\bf x};{\bf m},{\bf u})=(1-{\bf
m})\odot{\bf x}+{\bf m}\odot{\bf u}$ is an alternative expression to the patch
replacement embedding formula in Eq. (2) (for notational convenience only).
Again, ${\bm{m}}\in{\mathcal{M}}$ is the binary mask and ${\bf
u}\in{\mathcal{X}}$ is the patch for replacement.

Existing methods for solving problem (46) including the one proposed by Wang
et al. (2019), where, again, the practical solutions are usually sub-optimal.
Thus, similar to Def. 3.1 in the main paper, we present the following
definition in adaption to patch replacement BPs.

######  Definition C.1.

($\bm{\epsilon}$-solution set for patch replacement BPs) For any sample ${\bf
x}$ from any class, regardless of the method being used, the
$\epsilon$-solution set to problem (46), is defined by

${\mathcal{S}}_{\epsilon}({\bf x})\triangleq\\{\\{{\bf m},{\bf
u}\\}\big{|}||{\bf m}||_{1}-||{\bf m}^{\ast}({\bf
x})||_{1}\leq\epsilon,f(\bm{\Delta}({\bf x};{\bf m},{\bf u}))\neq f({\bf
x})\\},$ (47)

where $\epsilon>0$ is the “quality” bound of the solutions, which is usually
small for existing methods.

Similar to Def. 3.2 in the main paper, we present the following definition
(with abused notation) for the transferable set for patch replacement BPs.

######  Definition C.2.

(Transferable set for patch replacement BPs) The transferable set for any
sample ${\bf x}$ and $\epsilon>0$ is defined by

${\mathcal{T}}_{\epsilon}({\bf x})\triangleq\\{{\bf
y}\in{\mathcal{X}}\big{|}f({\bf y})=f({\bf x}),\exists\\{{\bf m},{\bf
u}\\}\in{\mathcal{S}}_{\epsilon}({\bf x})\,{\rm s.t.}\,f(\bm{\Delta}({\bf
y};{\bf m},{\bf u}))\neq f({\bf y})\\}.$ (48)

Finally, we present the following definition of the ET statistic for patch
replacement BPs, which looks exactly the same as Def. 3.3 in the main paper.
However, here, the definition of the transferable set has been customized for
patch replacement BPs. Even though, the similarity between these definitions
and their counterparts in the main paper has already highlighted the
generalization capability of our detection framework.

######  Definition C.3.

(ET statistic for patch replacement BPs) For any class
$i\in{\mathcal{C}}=\\{0,1\\}$ and $\epsilon>0$, considering i.i.d. random
samples ${\bf X},{\bf Y}\sim P_{i}$, the ET statistic for class $i$ is defined
by ${\rm ET}_{i,\epsilon}\triangleq{\mathbb{E}}\big{[}{\rm P}({\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})|{\bf X})\big{]}$.

###  C.2 Detecting BA with Patch Replacement BP Using ET

For the ET statistic for patch replacement BPs defined above, the same
constant detection threshold $\frac{1}{2}$ can be used for distinguish BA
target classes from non-target classes. The connection between the ET
statistic for patch replacement BPs and the constant threshold $\frac{1}{2}$
is established by the same Thm. 3.1 in Sec. 3.2 of the main paper with the
same proof in Apdx. A.1. Thus, these details are not included here for
brevity. Note that ${\rm P}_{{\rm MT,}i}$ and ${\rm P}_{{\rm NT,}i}$ for class
$i$ are defined in the same way as in Thm. 3.1, though the transferable set
${\mathcal{T}}_{\epsilon}({\bf x})$ is customized for patch replacement BPs in
the current section – this is the main reason why we abuse the notation for
the transferable set for patch replacement BPs in Def. C.2.

In the following, like in Sec. 3.2 of the main paper, we discuss the non-
attack case and the attack case respectively. Readers should notice that the
theorems (and the associated proofs) and discussions are similar to those in
the main paper. Such similarity further highlight the generalization
capability of our detection framework.

Non-attack case. Property 3.1 from the main paper is also applicable here.
That is, if class $(1-i)$ where $i\in{\mathcal{C}}=\\{0,1\\}$ is not a BA
target class, ${\rm P}_{{\rm NT,}i}$ for class $i$ will likely be larger than
$\frac{1}{2}$.

Similar to our verification of Property 3.1 for additive perturbation BPs in
Sec. 4.3 of the main paper, we verify Property 3.1 for patch replacement BPs
in Apdx. F. Using similar protocol as in Sec. 4.3 of the main paper, we show
that the common mask with the minimum-norm required for two sample to be
misclassified usually has a larger norm than mask with the mimimum-norm
required for each of them.

As for ${\rm P}_{{\rm MT,}i}$, again, Thm. 3.2 from the main paper is also
applicable here, but with a slightly different proof (shown below) in adaption
to the modifications to the definitions for the patch replacement BPs in Apdx.
C.1.

###### Proof.

Step 1: Similar to the proof in Apdx. A.2, We show that for any
$i\in{\mathcal{C}}$ and ${\bf X}$, ${\bf Y}$ i.i.d. following distribution
$P_{i}$, ${\bf X}\in{\mathcal{T}}_{\epsilon}({\bf Y})$ and ${\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})$ if and only if
${\mathcal{S}}_{\epsilon}({\bf X})\cap{\mathcal{S}}_{\epsilon}({\bf
Y})\neq\emptyset$.

(a) If ${\mathcal{S}}_{\epsilon}({\bf X})\cap{\mathcal{S}}_{\epsilon}({\bf
Y})\neq\emptyset$, there exists ${\bf s}$ such that ${\bf
s}\in{\mathcal{S}}_{\epsilon}({\bf X})$ and ${\bf
s}\in{\mathcal{S}}_{\epsilon}({\bf Y})$. By Def. C.1,

$\displaystyle{\bf s}\in{\mathcal{S}}_{\epsilon}({\bf X})\Rightarrow
f(\bm{\Delta}({\bf X};{\bf m},{\bf u}))\neq f({\bf X})$ (49)
$\displaystyle{\bf s}\in{\mathcal{S}}_{\epsilon}({\bf Y})\Rightarrow
f(\bm{\Delta}({\bf Y};{\bf m},{\bf u}))\neq f({\bf Y})$ (50)

Then, by Definition C.2, the existence of such ${\bf s}$ yields ${\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y})$ and ${\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})$.

(b) We prove the “only if” part also by contradiction. Given ${\bf
X}\in{\mathcal{T}}_{\epsilon}({\bf Y})$ and ${\bf
Y}\in{\mathcal{T}}_{\epsilon}({\bf X})$, suppose
${\mathcal{S}}_{\epsilon}({\bf X})\cap{\mathcal{S}}_{\epsilon}({\bf
Y})=\emptyset$. By Definition C.2, if ${\bf Y}\in{\mathcal{T}}_{\epsilon}({\bf
X})$, there exists ${\bf s}=\\{{\bf m},{\bf
u}\\}\in{\mathcal{S}}_{\epsilon}({\bf X})$ such that $f(\bm{\Delta}({\bf
Y};{\bf m},{\bf u}))\neq f({\bf Y})$. Since ${\mathcal{S}}_{\epsilon}({\bf
X})\cap{\mathcal{S}}_{\epsilon}({\bf Y})=\emptyset$, such ${\bf
s}\notin{\mathcal{S}}_{\epsilon}({\bf Y})$; hence, by Definition C.1

$||{\bf m}||_{1}-||{\bf m}^{\ast}({\bf Y})||_{1}>\epsilon.$ (51)

Similarly, there exists ${\bf s}^{\prime}=\\{{\bf m}^{\prime},{\bf
u}^{\prime}\\}\in{\mathcal{S}}_{\epsilon}({\bf Y})$ such that
$f(\bm{\Delta}({\bf X};{\bf m}^{\prime},{\bf u}^{\prime}))\neq f({\bf X})$ and
${\bf s}^{\prime}\notin{\mathcal{S}}_{\epsilon}({\bf X})$ (since it is assumed
that ${\mathcal{S}}_{\epsilon}({\bf X})\cap{\mathcal{S}}_{\epsilon}({\bf
Y})=\emptyset$); hence

$||{\bf m}^{\prime}||_{1}-||{\bf m}^{\ast}({\bf X})||_{1}>\epsilon.$ (52)

By Definition C.1, for all $\tilde{{\bf s}}=\\{\tilde{{\bf m}},\tilde{{\bf
u}}\\}\in{\mathcal{S}}_{\epsilon}({\bf Y})$, $||\tilde{\bf m}||_{1}-||{\bf
m}^{\ast}({\bf Y})||_{1}<\epsilon$. Thus, we have

$||{\bf m}||_{1}-||{\bf m}^{\ast}({\bf Y})||_{1}>||\tilde{\bf m}||_{1}-||{\bf
m}^{\ast}({\bf Y})||_{1}$ (53)

and accordingly $||{\bf m}||_{1}>||\tilde{\bf m}||_{1}$ for all $\tilde{\bf
s}\in{\mathcal{S}}_{\epsilon}({\bf Y})$. Similarly, for all $\tilde{\bf
s}^{\prime}=\\{\tilde{\bf m}^{\prime},\tilde{\bf
u}^{\prime}\\}\in{\mathcal{S}}_{\epsilon}({\bf X})$, we have

$||{\bf m}^{\prime}||_{1}-||{\bf m}^{\ast}({\bf X})||_{1}>||\tilde{\bf
m}^{\prime}||_{1}-||{\bf m}^{\ast}({\bf X})||_{1}$ (54)

and thus, $||{\bf m}^{\prime}||_{1}>||\tilde{\bf m}^{\prime}||_{1}$ for all
$\tilde{\bf s}^{\prime}\in{\mathcal{S}}_{\epsilon}({\bf X})$. Clearly, there
is a contradiction since there cannot exist an element in one set having a
larger norm than all elements in another set while vise versa; and therefore,
${\mathcal{S}}_{\epsilon}({\bf X})\cap{\mathcal{S}}_{\epsilon}({\bf
Y})\neq\emptyset$.

Step 2: We show that the upper bound for ${\rm P}_{{\rm MT,}i}$ goes to 0 when
$\epsilon\rightarrow 0$.

Note that by Definition C.1, ${\mathcal{S}}_{\epsilon}({\bf
X})\cap{\mathcal{S}}_{\epsilon}({\bf Y})\neq\emptyset$ only if $\big{|}||{\bf
m}^{\ast}({\bf X})||_{1}-||{\bf m}^{\ast}({\bf Y})||_{1}\big{|}\leq\epsilon$;
also based on Step 1:

${\rm P}_{{\rm MT,}i}={\rm P}({\mathcal{S}}_{\epsilon}({\bf
X})\cap{\mathcal{S}}_{\epsilon}({\bf Y})\neq\emptyset)\leq{\rm
P}(\big{|}||{\bf m}^{\ast}({\bf X})||_{1}-||{\bf m}^{\ast}({\bf
Y})||_{1}\big{|}\leq\epsilon).$ (55)

For ${\bf X}$ following continuous distribution $P_{i}$, ${\bf m}^{\ast}({\bf
X})$ also follows some continuous distribution on $(0,+\infty)$. Since ${\bf
X}$ and ${\bf Y}$ are i.i.d., the right hand side of Eq. (55) goes to 0 as
$\epsilon\rightarrow 0$. ∎

Based on the above, we have reached the same conclusions for patch replacement
BPs as in the main paper. That is, for the non-attack case, we will likely
have ${\rm P}_{{\rm NT,}i}\geq{\rm P}_{{\rm MT,}i}$, and consequently, ${\rm
ET}_{i,\epsilon}\leq\frac{1}{2}$ based on Thm. 3.1.

Attack case. For class $i\in{\mathcal{C}}=\\{0,1\\}$, we consider a successful
BA with target class $(1-i)$. The BP used by the attacker is specified by
${\bf s}_{0}=\\{{\bf m}_{0},{\bf u}_{0}\\}$ with mask ${\bf m}_{0}$ and patch
${\bf u}_{0}$. Thus, for any ${\bf X}\sim P_{i}$, due to the success of the
BA, $f({\bf X})=i$ and $f(\bm{\Delta}({\bf X};{\bf m}_{0},{\bf u}_{0}))\neq
f({\bf X})$. Similar to our discussion in the main paper, ${\bf s}_{0}$ will
likely be a common element in both ${\mathcal{S}}_{\epsilon}({\bf X})$ and
${\mathcal{S}}_{\epsilon}({\bf Y})$ for ${\bf X}$, ${\bf Y}$ i.i.d. following
$P_{i}$. For the same reason, in this case, the ET statistic will likely be
greater than $\frac{1}{2}$.

Similar to additive perturbation BPs, for patch replacement BPs, we also have
a guarantee for a large ET statistic (${\rm ET}_{i,\epsilon}=1$) when the mask
size of the BP used by the attacker is sufficiently small. Such property is
summarized in the theorem below.

######  Theorem C.1.

If class $(1-i)$ it the target class of a BA with patch replacement BP ${\bf
s}_{0}=\\{{\bf m}_{0},{\bf u}_{0}\\}$ such that $||{\bf
m}_{0}||_{1}\leq\epsilon$, we will have $P({\mathcal{S}}_{\epsilon}({\bf
X})\cap{\mathcal{S}}_{\epsilon}({\bf Y})\neq\emptyset)=1$ for ${\bf X}$ and
${\bf Y}$ i.i.d. following $P_{i}$; and furthermore, ${\rm
ET}_{i,\epsilon}=1$.

###### Proof.

For any ${\bf X}\sim P_{i}$, since ${\bf s}_{0}=\\{{\bf m}_{0},{\bf u}_{0}\\}$
satisfies $f(\bm{\Delta}({\bf X};{\bf m}_{0},{\bf u}_{0}))\neq f({\bf X})$,
and also because

$||{\bf m}_{0}||_{1}-||{\bf m}^{\ast}({\bf X})||_{1}<||{\bf
m}_{0}||_{1}\leq\epsilon,$ (56)

by Definition C.1, we have ${\bf s}_{0}\in{\mathcal{S}}_{\epsilon}({\bf X})$.
Thus, ${\bf s}_{0}\in{\mathcal{S}}_{\epsilon}({\bf
X})\cap{\mathcal{S}}_{\epsilon}({\bf Y})$ for ${\bf X}$ and ${\bf Y}$ i.i.d.
following $P_{i}$; and

$P({\mathcal{S}}_{\epsilon}({\bf X})\cap{\mathcal{S}}_{\epsilon}({\bf
Y})\neq\emptyset)=1.$ (57)

The rest of the proof (showing that ${\rm ET}_{i,\epsilon}=1$ for this attack
scenario) is exactly the same as the proof of Thm. 3.3 shown in Apdx. A.3,
thus is neglected here. ∎

###  C.3 Detection Procedure for Patch Replacement BP

The same procedure, i.e. Alg. 1 in the main paper, can be used for detecting
BAs with patch replacement BP, with only the following two modifications. We
only need to first replace line 8 of Alg. 1 by:
“Obtain an empirical solution $\hat{\bf s}({\bf x}_{n}^{(i)})=\\{\hat{\bf
m}({\bf x}_{n}^{(i)}),\hat{\bf u}({\bf x}_{n}^{(i)})\\}$ to problem (46) using
random initialization.”
and then change line 9 of Alg. 1 to:
“$\widehat{{\mathcal{T}}}_{\epsilon}({\bf
x}_{n}^{(i)})\leftarrow\widehat{{\mathcal{T}}}_{\epsilon}({\bf
x}_{n}^{(i)})\cup\\{{\bf x}_{k}^{(i)}|k\in\\{1,\cdots,N_{i}\\}\setminus
n,f(\bm{\Delta}({\bf x}_{k}^{(i)};\hat{\bf m}({\bf x}_{n}^{(i)}),\hat{\bf
u}({\bf x}_{n}^{(i)})))\neq f({\bf x}_{k}^{(i)})\\}$”.
Such a simple “module-based” modification allows our detection framework to be
applicable to a variety of BP embedding mechanisms, which again, shows the
generalization capability of our detection framework.

##  Appendix D Details of Experiment Settings

###  D.1 Details of Datasets

Our experiments are conducted on six popular benchmark image datasets. They
are CIFAR-10, CIFAR-100 Krizhevsky (2012), STL-10 Coates et al. (2011),
TinyImageNet, FMNIST Xiao et al. (2017) and MNIST Lecun et al. (1998). All the
datasets are associated with the torchvision package, except for that STL-10
is downloaded from the official website
https://cs.stanford.edu/~acoates/stl10/. Though the details of these datasets
can be easily found online, we summarize them in Tab. 2.

Table 2: Details of CIFAR-10, CIFAR-100, STL-10, TinyImageNet, FMNIST, MNIST datasets. | Color | Image size | # Classes | # Images/class | # Training images/class
---|---|---|---|---|---
CIFAR-10 | ✓ | $32\times 32$ | 10 | 6000 | 5000
CIFAR-100 | ✓ | $32\times 32$ | 100 | 600 | 500
STL-10 | ✓ | $96\times 96$ | 10 | 1300 | 500
TinyImageNet | ✓ | $64\times 64$ | 200 | 600 | 500
FMNIST | ✗ | $28\times 28$ | 10 | 7000 | 6000
MNIST | ✗ | $28\times 28$ | 10 | 7000 | 6000

###  D.2 Details for Generating the 2-Class Domains

In Sec. 4.1, we generate 45 2-class domains from CIFAR-10, and 20 2-class
domains from each of CIFAR-100, STL-10, TinyImageNet, FMNIST, and MNIST. Here
we provide more details about how these 2-class domains are generated.

As mentioned in Sec. 4.1, for CIFAR-10, the 45 2-class domains are
corresponding to the 45 unordered class pairs of CIFAR-10 respectively. For
each of CIFAR-100, FMNIST, and MNIST, we randomly sample 20 unordered class
pairs, each forming a 2-class domain. For TinyImageNet, due to high image
resolution and data scarcity, we generate 20 “super class” pairs – for each
pair, we randomly sample 20 classes from the original category space and then
evenly assign them to the two super classes (each getting 10 classes from the
original category space). Similarly, for STL-10 with 10 classes, we generate
20 super class pairs by randomly and evenly dividing the 10 classes into two
groups (of 5 classes from the original category space) for each pair. For each
generated 2-class domain, we use the subset of data associated with these two
(super) classes from the original dataset, with the original train-test split.

###  D.3 Details of BPs

In this paper, we consider both additive perturbation BPs embedded by Eq. (1)
and patch replacement BPs embedded by Eq. (2) that are frequently used in
existing backdoor papers. Despite the BPs (with images embedded with them)
illustrated in Fig. 1 in the main paper, here, in Fig. 6, we show the BPs used
in our experiments that are not included in the main paper due to space
limitations. In the following, we also provide details for each of these BPs
(in both Fig. 1 and Fig. 6).

(a) “static” pattern

(b) chessboard patch

(c) cross

(d) square

Figure 6: BPs used in our experiments that are not shown in Fig. 1 of the main
paper due to space limitations; and images with these BPs embedded. BPs in (a)
and (b) are amplified for visualization.

First, we provide the details for all the additive perturbation BPs. The
“chessboard” pattern in Fig. 1 is a “global” pattern that has been used by
Xiang et al. (2020). Here, one and only one of two adjacent pixels are
perturbed positively by 3/255 in all color channels. Another global pattern is
the “static” pattern in Fig. 6 considered by both Zhong et al. (2020); Xiang
et al. (2021b). For pixel indices starting from 0, a pixel $(i,j)$ is
perturbed positively if and only if $i$ and $j$ are both even numbers. Again,
the perturbation size is 3/255 for all pixels being perturbed.

Other additive perturbation BPs are all “localized” patterns. The “L” pattern
in Fig. 1 and the “X” pattern in Fig. 1 have been used by both Tran et al.
(2018) and Wang et al. (2020). For the “L” pattern, we perturb all the color
channels by 50/255. For the “X” pattern, for each attack, we randomly choose a
channel (for all images to be embedded in for this particular attack) and
perturb the associated pixels positively by 50/255. The “pixel” BP in Fig. 1
has been used by Tran et al. (2018); Chen et al. (2018), where a single pixel
is perturbed in all channels by 50/255 for color images and 70/255 for gray-
scale images. The “chessboard patch” pattern in Fig. 6, the “cross” in Fig. 6,
and the “square” in Fig. 6 have all been previously considered. For the cross
and the chessboard patch, the perturbation sizes for each pixel being
perturbed are 50/255 and 5/255, respectively; and perturbation is applied to
all channels. For the square pattern, one channel is randomly selected for
each attack and the perturbation size is 50/255. The spatial location of all
these localized patterns are randomly selected over the entire image (and
fixed for all images to be embedded in) for each attack. Only for gray-scale
images, the pixels being perturbed are restricted to one of the four corners,
such that these pixels will likely be black (with pixel value close to 0)
originally.

Next, we provide the details for the two patch replacement BPs considered in
our experiments. The BP in Fig. 1 is a small, monochromatic patch located near
the margin of the images to be embedded in. Similar BPs have been considered
by Gu et al. (2019) and Wang et al. (2019). The color is randomly chosen and
fixed for each attack. The BP in Fig. 1 is a small noisy patch located near
the margin of the images to be embedded in. Similar BPs have been considered
by Turner et al. (2019) and A. Saha (2020). For both BPs, once the location is
selected, the same location will be applied to all images to be embedded in
for the same attack. Also, for both BPs, the size of the patch is $3\times 3$
for the 2-class domains generated from CIFAR-10 and CIFAR-100; $4\times 4$ for
the 2-class domains generated from TinyImageNet; and $10\times 10$ for the
2-class domains generated from STL-10.

Table 3: Short hand “code” for each ensemble of attack instances based on both the BP being used and the dataset where the associated 2-class domains are generated from. “n/a” represents “not applicable”. | Additive perturbation BP | Patch replacement BP
---|---|---
CIFAR-10 | A1 | A7
CIFAR-100 | A2 | A8
STL-10 | A3 | A9
TinyImageNet | A4 | A10
FMNIST | A5 | n/a
MNIST | A6 | n/a
Table 4: Summary of attack configurations for instances in each of ensembles
A1-A10. For each ensemble, we show the number of attacks for each instance in
this ensemble. We also show, for each ensemble, the number of samples
(embedded with BP and labeled to the target class) used for poison the
training set for each attack associated with this ensemble, as well as the
corresponding poisoning rate. Poisoning rate is defined as the number of
samples inserted into the training set by the attacker divided by the total
number of training samples from the target class after poisoning.

| A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10
---|---|---|---|---|---|---|---|---|---|---
# Attacks | 2 | 2 | 2 | 1 | 1 | 1 | 2 | 2 | 1 | 2
# Poison samples | 500 | 150 | 1000 | 1500 | 1000 | 1000 | 500 | 50 | 750 | 500
Poisoning rate | 9.1% | 23.0% | 28.6% | 23.0% | 14.3% | 14.3% | 9.1% | 9.1% | 23.1% | 9.1%

###  D.4 Other Attack Configurations

In the main paper, we defined a “code” for each ensemble of attack instances
based on both the type of BP being used and the dataset from which the
associated 2-class domains are generated. Here, we summarize these codes in
Tab. 3 for reference. Also in the main paper, we have described most of the
attack configurations for the attacks instances in each ensemble. For some
ensembles, each attack instance is associated with two attacks, each with one
of the two class being the target class. Also, the BPs used by the two
attacks, though of the same type, are guaranteed to be sufficiently different
in shapes (for additive perturbation BP) or colors (for patch replacement BP).
For other ensembles, there is only one attack for each attack instance. Here,
we provide a summary for these configurations in Tab. 4. Also, in Tab 4, for
attack instances in each ensemble, we summarize the number of training samples
embedded with the BP and labeled to the target class that are used for
poisoning the classifier’s training set for the associated attacks.

Table 5: Training details, including learning rate, batch size, number of epochs, whether or not using training data augmentation, choice of optimizer (Adam D. P. Kingma (2015) or stochastic gradient descent (SGD)), for 2-class domains generated from CIFAR-10, CIFAR-100, STL-10, TinyImageNet, FMNIST, and MNIST, respectively. | Learning rate | Batch size | # Epochs | Data augmentation | Optimizer
---|---|---|---|---|---
CIFAR-10 | 0.001 | 32 | 150 | ✗ | Adam
CIFAR-100 | 0.001 | 32 | 150 | ✗ | Adam
STL-10 | 0.001 | 128 | 150 | ✗ | Adam
TinyImageNet | 0.001 | 128 | 150 | ✓ | Adam
FMNIST | 0.01 | 256 | 100 | ✗ | SGD
MNIST | 0.01 | 256 | 100 | ✗ | SGD

###  D.5 Training Details

Here we provide the training details that are not included in the main paper
due to space limitations. For each generated 2-class domain, we use the same
training configuration irrespective of the existence of BA. In Tab. 5, we show
the training details including learning rate, batch size, number of epochs,
whether or not using training data augmentation, choice of optimizer (Adam D.
P. Kingma (2015) or stochastic gradient descent (SGD)) for 2-class domains
generated from CIFAR-10, CIFAR-100, STL-10, TinyImageNet, FMNIST, and MNIST,
respectively. Training data augmentations for 2-class domains generated from
TinyImageNet include random cropping and random horizontal flipping – these
augmentations are helpful for the backdoor mapping to be learned without
compromising the classifier’s accuracy on clean test samples. Otherwise, we
may not easily produce an effective attack to evaluate the performance of our
defense.

Table 6: Average clean test accuracy (ACC, in percentage) over all classifiers
being attacked, average and minimum attack success rate (ASR, in percentage)
over all attacks, for each of ensemble A1-A10 of attack instances.

| A1 | A2 | A3 | A4 | A5 | A6 | A7 | A8 | A9 | A10
---|---|---|---|---|---|---|---|---|---|---
ASR (average) | 95.7$\pm$3.6 | 91.6$\pm$4.5 | 98.8$\pm$1.0 | 93.9$\pm$2.8 | 96.8$\pm$3.3 | 99.8$\pm$0.4 | 99.2$\pm$1.1 | 96.4$\pm$4.0 | 97.9$\pm$1.4 | 94.5$\pm$4.6
ASR (minimum) | 82.3 | 80.0 | 95.9 | 88.0 | 87.6 | 98.4 | 92.5 | 82.0 | 95.1 | 83.2
ACC (average) | 94.6$\pm$4.2 | 90.7$\pm$4.5 | 79.6$\pm$2.9 | 77.0$\pm$3.2 | 99.0$\pm$1.1 | 99.8$\pm$0.1 | 96.7$\pm$2.5 | 93.2$\pm$4.1 | 78.7$\pm$3.4 | 77.2$\pm$3.5

Table 7: Average clean test accuracy (ACC, in percentage) over the classifiers for the clean instances in each of ensemble C1-C6. | C1 | C2 | C3 | C4 | C5 | C6
---|---|---|---|---|---|---
ACC (average) | 95.4$\pm$3.6 | 93.3$\pm$3.3 | 80.5$\pm$3.2 | 78.2$\pm$3.0 | 99.3$\pm$1.0 | 99.8$\pm$0.1

We also show the effectiveness of the attacks we created for evaluating our
defense. Commonly, the effectiveness of a BA is evaluated by attack success
rate (ASR) and clean test accuracy (ACC) Xiang et al. (2020); Wang et al.
(2020). ASR is defined (for each attack) as the probability that a test image
from the source class is (mis)classified to the target class of BA when the BP
is embedded. ACC is defined (for each classifier being attack regardless of
the number of attacks) as the classification accuracy on test samples with no
BP. In our experiments, we evaluate ASR and ACC using images from the test set
associated with each 2-class domain – these images are not used during
training. For each attack instance, we evaluate ASR for each attack (since
there can be either one attack or two attacks with different BA target class)
separately. In Tab. 6, for each of ensembles A1-A10, we show the average ACC
for the classifier being attacked over all instances in the ensemble; we also
show the mean and minimum ASR over all attacks of all instances in the
ensemble. As a reference, in Tab. 7 for each of ensemble C1-C6 of clean
instances, we show the average ACC over all the clean classifiers for the
ensemble. Based on the results in both Tab. 6 and Tab. 7, all the attacks we
created are successful with high ASR and almost no degradation in ACC.

###  D.6 BP Reverse-Engineering Algorithms

In the main paper, we evaluate our detection framework with two BP reverse-
engineering algorithms, which are denoted as RE-AP and RE-PR, respectively.
RE-AP is proposed by Xiang et al. (2020) for reverse-engineering additive
perturbation BPs. The general form of RE-AP estimates a common perturbation
that induces a group of images to be misclassified to a common target class.
When there is a single image in such a group, and when there are only two
classes, the optimization problem solved by RE-AP is reduced to (3). To solve
this problem for some target class $i\in{\mathcal{C}}$ and image ${\bf
x}\in{\mathcal{X}}$ from the class other than $i$, RE-AP minimizes the
following surrogate objective function:

$L_{\rm AP}({\bf v})=-\log p(i|{\bf x}+{\bf v}),$ (58)

using gradient descent with ${\bf v}$ initialized from ${\mathbf{0}}$, until
the constraint of (3) is satisfied. Here, $p(i|{\bf x})$ denotes the
classifier’s posterior of class $i$ give any input sample ${\bf
x}\in{\mathcal{X}}$. The step size for minimization is set small to ensure a
good “quality” for the solution; otherwise, the resulting perturbation may
have a much larger norm than the minimum norm perturbation required for
inducing a misclassification. Moreover, for each domain and each classifier to
be inspected, choosing a proper step size can be done based on the norm of the
solution and without any knowledge of the presence of BA.

Another BP reverse-engineering algorithm, RE-PR is proposed by Wang et al.
(2019) for patch replacement BPs. Similarly, RE-PR solves problem (46) in
Apdx. C.1, which is the counterpart of problem (3) for patch replacement BPs.
Formally, for some target class $i\in{\mathcal{C}}$ and image ${\bf
x}\in{\mathcal{X}}$ from the class other than $i$, RE-PR minimizes the
following surrogate objective function:

$L_{\rm PR}({\bf m},{\bf u})=-\log p(i|\bm{\Delta}({\bf x};{\bf m},{\bf
u}))+\lambda||{\bf m}||_{1},$ (59)

using gradient descent, where $\lambda$ is the Lagrange multiplier and
$\bm{\Delta}({\bf x};{\bf m},{\bf u})$ is the alternative expression to Eq. 2
(see the description below Eq. (46)) for patch replacement BP embedding.

###  D.7 Limitations of the Cosine Similarity Statistic in BA Detection

In the main paper, we compared our ET statistic with other three types of
detection statistics including a cosine similarity (CS) statistic proposed by
Wang et al. (2020). As an important work addressing unsupervised backdoor
detection without access to the training set, this method can effectively
detect backdoor attacks when their are multiple classes with only few of them
are backdoor target classes.

For general classification domains with arbitrary number of classes, the CS
statistic is obtained for each putative target class $t\in{\mathcal{C}}$ as
following. First, a common (patch replacement) BP is estimated to: a) induces
a group of images from classes other than $t$ to be misclassified in an
untargeted fashion (i.e., to any class other than their originally labeled
classes); b) not induce any class $t$ images to be misclassified; and c) have
as small mask size (measured by $l_{1}$ norm) as possible. Accordingly, Wang
et al. (2020) proposed to minimize the following loss:

$\displaystyle L_{\rm CSC}({\bf m},{\bf u})$
$\displaystyle=\sum_{i\in{\mathcal{C}}\setminus t}\sum_{{\bf
x}\in{\mathcal{D}}_{i}}\max\\{h_{i}(\bm{\Delta}({\bf x};{\bf m},{\bf
u}))-\max_{j\neq i}h_{j}(\bm{\Delta}({\bf x};{\bf m},{\bf u})),-\kappa\\}$
(60) $\displaystyle+\sum_{{\bf x}\in{\mathcal{D}}_{t}}\max\\{\max_{j\neq
t}h_{j}(\bm{\Delta}({\bf x};{\bf m},{\bf u}))-h_{t}(\bm{\Delta}({\bf x};{\bf
m},{\bf u})),-\kappa\\}+\lambda||{\bf m}||_{1},$

where $h_{i}(\cdot):{\mathcal{X}}\rightarrow{\mathbb{R}}$ is the logit (right
before softmax) of class $i\in{\mathcal{C}}$ Carlini & Wagner (2017). We
denote the estimated (common) BP for class $t$ as ${\bf s}^{\ast}_{t}=\\{{\bf
m}^{\ast}_{t},{\bf u}^{\ast}_{t}\\}$.

Then, for each image not from class $t$, a sample-wise BP is estimated to: a)
induce the image to be misclassified to class $t$; and b) have as small mask
size (measured by $l_{1}$ norm) as possible. Thus, the following loss is
minimized for each ${\bf x}\in\cup_{i\in{\mathcal{C}}\setminus
t}{\mathcal{D}}_{i}$:

$L_{\rm CSS}({\bf m},{\bf u})=\max\\{\max_{j\neq t}h_{j}(\bm{\Delta}({\bf
x};{\bf m},{\bf u}))-h_{t}(\bm{\Delta}({\bf x};{\bf m},{\bf
u})),-\kappa\\}+\lambda||{\bf m}||_{1}.$ (61)

We denote the sample-wise BP estimated for class $t$ and sample ${\bf x}$ as
$\tilde{\bf s}^{\ast}_{t}({\bf x})=\\{\tilde{\bf m}^{\ast}_{t}({\bf
x}),\tilde{\bf u}^{\ast}_{t}({\bf x})\\}$.

Finally, the cosine similarity statistic for class $t$ is computed by:

${\rm CS}_{\rm t}=\frac{1}{|\cup_{i\in{\mathcal{C}}\setminus
t}{\mathcal{D}}_{i}|}\sum_{{\bf x}\in\cup_{i\in{\mathcal{C}}\setminus
t}{\mathcal{D}}_{i}}{\rm cos}({\bf z}(\bm{\Delta}({\bf x};{\bf
m}^{\ast}_{t},{\bf u}^{\ast}_{t})),{\bf z}(\bm{\Delta}({\bf x};\tilde{\bf
m}^{\ast}_{t}({\bf x}),\tilde{\bf u}^{\ast}_{t}({\bf x})))),$ (62)

where ${\bf z}(\cdot):{\mathcal{X}}\rightarrow{\mathbb{R}}^{d}$ is the mapping
from input layer to the penultimate layer with some dimension $d$. ${\rm
cos}(\cdot):{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\rightarrow[-1,1]$ is the
cosine similarity between two real vectors.

Based on our results in Fig. 2, CS for BA target classes and non-target
classes are separable for most domains. This is not surprising because when
class $t\in{\mathcal{C}}$ is a BA target class, the estimated common BP will
likely be highly correlated with the sample-wise BPs estimated for images from
classes other than $t$; thus, the resulting CS will be large and possibly
close to 1. If class $t\in{\mathcal{C}}$ is not a BA target class, the
estimated common BP may induce images from classes other than $t$ to be
misclassified to some arbitrary classes (possibly the “semantically” closest
class for each individual image). Thus, the common BP may be very different
from sample-wise BP estimated to only induce misclassifications to class $t$.
Consequently, the CS statistic will likely be small.

However, considering our 2-class problem with no sufficient number of
statistics to inform estimation of a null distribution, and also our
assumption that there is no domain-specific supervision (e.g. using clean
classifiers trained for the same domain) for setting a proper detection
threshold, CS statistic may not be effective since it is sensitive to domains
and DNN architectures.

First, when there is no BA, for ReLU networks, the penultimate layer features
are always non-negative, such that the cosine similarity is guaranteed to be
non-negative. However, for DNN with sigmoid or leaky ReLU activation
functions, the penultimate layer features can be negative. Thus, the CS
statistic may be distributed in the entire interval of $[-1,1]$. Such large
difference in the null distribution of CS statistic makes the choice of a
detection threshold very difficult without domain-specific knowledge.

Second, CS is also sensitive to the classification domain, especially the
number of classes. Considering some putative target class $t\in{\mathcal{C}}$,
when there are a large number of classes in the domain, the common BP
estimated for a group of images from classes other than $t$ will likely be
very different with the sample-wise BP estimated for each individual in the
group. In particular, most images will likely be misclassified to some class
other than $t$ when the common BP is embedded; but the sample-wise BP is
estimated for each of these images to induce them to be misclassified to class
$t$. Thus, the penultimate layer feature associated with the common BP and the
sample-wise BP will likely be different for most images. However, when there
are only two classes, i.e. ${\mathcal{C}}=\\{0,1\\}$ in our case, the images
used for BP estimation for class $t$ are all from class $(1-t)$. Moreover,
both common BP and samples-wise BP estimated for these images will induce them
to be misclassified to class $t$. Thus, CS obtained for this case will likely
be larger than for the cases where there are a large number of classes when
there is no BA. We demonstrate this phenomenon in the following.

Figure 7: Average CS statistic versus the number of classes in the domain.

We construct five domains from CIFAR-10. The first four domains contain 2, 4,
6, 8 classes randomly selected from the 10 classes of CIFAR-10 respectively,
and the the fifth domain is the original CIFAR-10 with 10 classes. We train a
classifier without BA for each domain using the same configurations as in Sec.
4.1. For each classifier, we obtain CS statistics for all classes. In Fig. 7,
we show the average CS statistic over all classes for the five classifiers. In
general, CS statistic decreases as the number of classes grows; thus, it is
highly domain-dependent.

###  D.8 Details for Multi-Class Experiments

In Sec. 4.4, we evaluate the performance of our detection framework for multi-
class scenarios with arbitrary number of attacks. In other words, the
classifier has more than two classes, and each class can possibly be a BA
target class.

For each of CIFAR-10, CIFAR-100, and STL-10, we create three attack instances
with one, two, and three attacks, respectively. Like the attacks we created
for the 2-class domains, the attacks here are created following the same data
poisoning protocol that has been widely considered in existing works. That is,
we create backdoor training images by embedding a BP into a small set of
images from classes other than the target class. These backdoor training
images are labeled to a target class and inserted into the training set of the
classifier Gu et al. (2019). In our experiment here, for each attack of each
instance, we randomly select a target class. For simplicity, we consider only
additive perturbation BP here. We randomly select a shape (and location for
localized BP) for the BP to be used from our pool of candidate BPs. Note that
for any two attacks of the same attack instance, the target classes and the
BPs should both be different from each other. For attacks on CIAFR-10,
CIFAR-100, and STL-10, the backdoor training images are created using 60, 10,
and 100 clean images per class (not including the target class), respectively.

For each domain, the three attack instances and the clean classifier use the
same training configuration. For CIFAR-10 and STL-10, we use ResNet-18 as the
DNN architecture; for CIFAR-100, we use ResNet-34 architecture. For all three
domains, training data augmentations including random cropping and random
horizontal flipping are adopted. Other configurations for classifier training
for these domains are the same as for the 2-class domains generated from these
original domains (shown in Tab. 5). Using these training configurations, the
resulting nine classifiers being attacked (three classifiers for the three
attack instances respectively for each domain) all have high attack success
rate (ASR). Compared with the three clean classifiers (without BA) trained for
the three domains respectively, there is also no significant degradation in
clean test accuracy (ACC) for the classifiers being attacked. ASR and ACC for
these classifiers are shown in Tab. 8.

Table 8: Attack success rate (ASR) and clean test accuracy (ACC) for the classifiers being attacked (with one, two, and three attacks/target classes) for CIAFR-10, CIFAR-100, and STL-10, respectively; and ACC for the clean classifiers trained for the three domains respectively. | CIFAR-10 | CIFAR-100 | STL-10
---|---|---|---
one attack |  ASR: 97.0 ACC: 93.7 |  ASR: 97.7 ACC: 71.5 |  ASR: 95.1 ACC: 79.7
two attacks |  ASR=96.0, 93.7 ACC: 92.5 |  ASR=89.6, 95.3 ACC: 71.9 |  ASR=99.6, 96.0 ACC: 80.8
three attacks |  ASR: 94.5, 80.2, 97.9 ACC: 92.8 |  ASR: 95.7, 74.7, 97.4 ACC: 70.5 |  ASR: 78.1, 99.0, 95.1 ACC: 79.1
no attack | ACC: 92.5 | ACC: 70.4 | ACC: 78.8

##  Appendix E Using ET to Detect Clean-Label BAs

In this section, we demonstrate the effectiveness of our detection framework
against a recent clean-label BA proposed by Turner et al. (2019). Clean-label
BAs are motivated by the possible human/machine inspection of the training
set. For example, backdoor training samples labeled to some target class
inserted by a typical backdoor attacker are originally from classes other than
the target class. Such “mislabeling” may be noticed by a human expert who
inspects the training set manually, or may be detected by a shallow neural
network trained on a small held-out validation set that is guaranteed to be
clean. Thus, Turner et al. (2019) proposed to create backdoor training samples
(that will be inserted into the classifier’s training set) by embedding the BP
only to target class samples. However, for target class samples embedded with
the BP, there is no guarantee that it is the BP but not the features
associated with the target class that will be learned by the classifier. Thus,
Turner et al. (2019) proposed to “destroy” these target class features before
embedding the BP when creating backdoor training samples. Then, the classifier
will learn the BP and classify any test sample embedded with the BP to the
target class.

(a) bird

(b) deer

(c) frog

(d) horse

(e) ship

(f) truck

Figure 8: Examples for backdoor training images for clean-label BAs. These
images are originally from the BA target class, perturbed (in human-
imperceptible fashion) to be misclassified by a surrogate classifier, embedded
with the BP, and are still labeled to the target class.

Figure 9: Effectiveness of our defense, with the constant ET threshold 1/2,
against the clean-label BA proposed by Turner et al. (2019). Classifiers being
attacked have a maximum ET (over the two classes) greater than 1/2; clean
classifiers have a maximum ET (over the two classes) less than 1/2.

One simple yet effective approach proposed by Turner et al. (2019) to destroy
the features in the backdoor training samples associated with the target class
is inspired by a method for creating adversarial examples. The backdoor
attacker needs to first train a surrogate classifier using an independently
collected clean dataset. Then, for each of a small set of samples from the
target class used for creating backdoor training samples, the attacker
independently launches a projected gradient descent (PGD) attack (Madry et al.
(2018)) to have the sample be predicted to any class other than its original
class (i.e. the target class) by the surrogate classifier. These samples with
the target class features destroyed are then embedded with the BP, are still
labeled to the target class, and are inserted into the classifier’s training
set.

In our experiment here, we randomly generate ten 2-class domains from CIFAR-10
following its original train-test split. For each 2-class domain, we first
train a surrogate classifier using a subset of the training set (2000 training
images per class). The remaining samples (3000 per class) are assumed to be
possessed by the trainer for training the victim classifier. For each 2-class
domain, we create one attack instance with one BA targeting on the second
class and using an additive perturbation BP. The candidate BPs to be used are
the same as in our experiments in the main paper. Here, for each BA, we use
1500 images from the target class (i.e. the second class of the associated
2-class domain) to create backdoor training images. These images are randomly
sampled from the images used for training the surrogate classifier. For each
of these 1500 images, we independently generate an adversarial perturbation
using the surrogate classifier following the standard protocol of PGD Madry et
al. (2018). In particular, we set the maximum perturbation size as 8/255, the
number of perturbation steps as 10, and the step size as 1/255. Most of the
perturbed images are misclassified by the surrogate classifier. Then we embed
the BP randomly selected from the candidates for each attack into these images
with the adversarial perturbation and still label them to the target class,
where they are originally from. The created backdoor training images are
inserted into the training set of the victim classifier. They will be barely
noticeable to human inspectors since they visually look like standard target
class images and the embedded BP is almost imperceptible by humans. Some
examples of backdoor training images are shown in Fig. 8.

For each attack instance, we use the same training configurations as in Sec.
4.1 of the main paper to train the victim classifier. We also train a clean
classifier for each instance to evaluate false detections. Moreover, we apply
our detection framework with the BP reverse-engineering algorithm RE-AP and
the same defense configurations as in the main paper to both the classifiers
being attacked and the clean classifiers. In Fig. 9, we show the maximum ET
(over the two classes) for all these classifiers. Using ET and the constant
detection threshold 1/2, we perfectly detect all clean-label BAs with no false
detections.

##  Appendix F Experimental Verification of Property 3.1 for Patch Replacement
BPs

We verify Property 3.1 for patch replacement BPs embedded by Eq. (2). Similar
to Sec. 4.3 of the main paper, here, we show that when class $(1-i)$ for
$i\in{\mathcal{C}}=\\{0,1\\}$ is not a BA target class, for any two samples
from class $i$, the minimum $l_{1}$ norm for any common mask that induces both
samples to be misclassified will likely be larger than the minimum $l_{1}$
norm for the masks inducing each individual sample to be misclassified. The
masks are obtained by solving problem (3).

Figure 10: Histogram of $l_{1}$ norm ratio between pair-wise common mask and
maximum of the two sample-wise masks for each random image pair for clean
classifiers.

We randomly choose one clean classifier from each of C1-C4. For each
classifier, we randomly choose 10 pairs of clean images from a random class of
the associated 2-class domain. For each pair of images, we apply the RE-PR
algorithm (for reverse-engineering patch replacement BPs) on the two images
jointly (to get a pair-wise common mask) as well as separately (to get two
sample-wise masks for the two images respectively). Again, we divide the
$l_{1}$ norm of the pair-wise (common) mask by the maximum $l_{1}$ norm of the
two sample-wise masks to get a ratio. In Fig. 10, we plot the histogram of
such ratio for all image pairs for all four classifiers – the ratio for most
of the image pairs is greater than 1 (marked by the red dashed line in Fig.
10). For these pairs, it is very likely that the BP (in particular, the mask)
estimated for one sample cannot induce the other sample to be misclassified
and vise versa. Note that if for any image pair, the mask (and some associated
pattern) estimated for one sample can induce the other to be misclassified,
such mask (and the associated pattern) will be a common mask (and pattern)
that induces both images to be misclassified. Then, we would expect the ratio
computed above to be very close to 1 for such an image pair.

##  Appendix G Influence of the Number of Clean Images for Detection

The core of our detector is to estimate the ET statistic for each class. Note
that the ET statistic is in fact an expectation. In principle, with fewer
clean images per class for ET estimation, the variance of the estimated ET
will be larger, though the execution time for ET estimation may be smaller.
Thus, we would expect that, sometimes, the ET estimated using only a few clean
images may be smaller than $\frac{1}{2}$ for the attack case; or larger than
$\frac{1}{2}$ for the clean case.

(a) attack instances (A1)

(b) clean instances (C1)

Figure 11: Accuracy of detection inference on the ensemble of attack instances
A1 and the ensemble of clean instances C1, when the number of images used for
detection varies in [2, 5, 10, 15].

In Sec. 4.1, we used 20 images per class (40 images in total) for backdoor
detection for all attack instances and all clean instances, and achieved good
detection accuracy. Here, we show the influence of the number of clean images
per class on detection accuracy. In particular, for all 45 attack instances
and all 45 clean instances of two-class domains generated from CIFAR-10 (i.e.
A1 and C1), we apply the same detector in Sec. 4.1 with detection threshold
$\frac{1}{2}$, but varying the number of clean images per class (in [2, 5, 10,
15]) used for detection (i.e. ET estimation). As shown in Fig. 11, with 5
clean images per class (10 images in total), our method achieves relatively
good detection accuracy. Even with only 2 clean images per class (which is the
minimum sample size for empirical ET estimation), our detector catches $\sim
80\%$ of attacks with less than 10% false detection rate555Here, we claim a
failure in detection if ET is exactly $\frac{1}{2}$ for both clean instances
and attack instances. Thus, the actual detection accuracy should be higher
than those in Fig. 11 if we either do or do not trigger an alarm when ET is
exactly $\frac{1}{2}$..

##  Appendix H Choice of the Patience Parameter $\tau$

In all experiments in the main paper, we set the patience parameter in Alg. 1
to $\tau=4$ and claim that larger $\tau$ will not induce much change to the
estimated ET. Here, we provide some empirical evidence to support this claim.

(a) an attack instance in A1 (RE-AP)

(b) an attack instance in A7 (RE-PR)

(c) a clean instance in C1 (RE-AP)

(d) a clean instance in C1 (RE-PR)

(e) an attack instance in A2 (RE-AP)

(f) an attack instance in A8 (RE-PR)

(g) a clean instance in C2 (RE-AP)

(h) a clean instance in C2 (RE-PR)

Figure 12: Example growing curves of $p_{n}^{(i)}$ (with patience $\tau=8$).
In each figure, there are 20 curves, each corresponding to a clean sample used
for detection. ET is the average final $p_{n}^{(i)}$ over these 20 samples.

We apply Alg. 1 with RE-AP to a classifier being attacked in A1 and a
classifier being attacked in A2. We also apply Alg. 1 with RE-PR to a
classifier being attacked in A7 and a classifier being attacked in A8.
Moreover, Alg. 1 with both RE-AP and RE-PR are applied to a clean classifier
in C1 and a clean classifier in C2. Note that classification domains
associated with A1, A7, and C1 are generated from CIFAR-10; while
classification domains associated with A2, A8, and C2 are generated from
CIFAR-100.

For all experiments in this section, we set the patience parameter to $\tau=8$
instead of $\tau=4$ used in the main paper. The purpose is to get a better
observation of the asymptotic behavior of
$p_{n}^{(i)}=|\widehat{{\mathcal{T}}}_{\epsilon}({\bf
x}_{n}^{(i)})|/(N_{i}-1)$ during ET estimation for each clean sample ${\bf
x}_{n}^{(i)}$ used for detection (see line 7-12 of Alg. 1 for the definition
of related quantities). The number of clean samples used for detection is 20.

As shown in Fig. 12, when applying our method to classifiers being attacked,
$p_{n}^{(i)}$ (for some class $i$) quickly grows to 1 (in very few iterations)
for most clean samples used for detection (see (a)(b)(e)(f) of Fig. 12). For a
few clean samples, $p_{n}^{(i)}$ quickly grows to a large value close to 1 and
then slowly reaches 1 (see (e)(f) of Fig. 12). Only for very few samples,
$p_{n}^{(i)}$ stays at some value in between 0 and 1 (see (b)(e) of Fig. 12).
Based on these observations, which are generally true for other domains we
investigated, $\tau=4$ is not a critical choices to our detection performance.
The estimated ET, which is the average $p_{n}^{(i)}$ for all clean samples
used for detection, will likely be greater than $\frac{1}{2}$, as determined
by the majority of clean samples used for detection.

On the other hand, when applying our method to clean classifiers, with RE-AP,
$p_{n}^{(i)}$ stays at 0 (or some small values close to 0) for all clean
samples used for detection (see (c)(g) of Fig. 12). When applying our method
with RE-PR to the same classifiers, $p_{n}^{(i)}$ stays at 0 or some small
values close to 0 for most samples and shows a trend of convergence (see
(d)(h) of Fig. 12). Again, reducing $\tau$ from 8 to 4 or further increasing
$\tau$ will not change the estimated ET much – the estimated ET for these
clean instances will still be clearly less than $\frac{1}{2}$.

##  Appendix I Using Synthesized Images for Backdoor Detection

For most REDs, the defender is assumed to possess a small, clean dataset
(collected independently) for detection Wang et al. (2019); Xiang et al.
(2020); Guo et al. (2019); Wang et al. (2020). Although this assumption is
relatively mild and feasible in most practical scenarios, it may be
unnecessary if the defender is able to synthesize the images used for
detection.

The first trial was made by Chen et al. (2019), where on simple datasets like
MNIST Lecun et al. (1998), images for backdoor pattern reverse-engineering are
synthesized by model inversion Fredrikson et al. (2015). However, images
generated in such a way are not guaranteed to be visually typical to their
designated classes, especially for complicated domains like ImageNet. Thus we
ask the following question:
Can our ET framework be generalized to involve backdoor pattern reverse-
engineering using synthesized images?

(a) “1”

(b) “3”

(c) “4”

(d) “5”

Figure 13: Images synthesized using a simpler version of the model inversion
method used by Chen et al. (2019).

Figure 14: Histogram of ET statistics for classifiers in A6 and C6, when the
images for backdoor pattern reverse-engineering are synthesized.

Here, we consider the 20 two-class domains generated from MNIST due to this
domain’s simplicity. We apply RE-AP to the 20 classifiers being attacked in A6
and the 20 clean classifiers in C6, respectively. The clean images used for
detection are generated using a simpler version of the model inversion method
used by Chen et al. (2019). To synthesize an image for detection, we first
initialize an all-zero image added with some small random positive noise.
Then, we maximize (over the image values) the posterior of the designated
class of the image using the classifier to be inspected, until the posterior
is greater than 0.9. Examples for our synthesized images are shown in Fig. 13.
Note that without the “auxiliary constraints” on images during their
generation process (Chen et al. (2019)), the generated images are usually
atypical to their designated classes.

In Fig. 14, we show the ET statistic for the 80 classes associated with the 40
binary classifiers (20 classifiers being attacked and 20 clean classifiers).
Among these 80 classes, there are 60 backdoor target classes and 20 non-target
classes (please see the settings in Sec. 4.1). Despite one backdoor target
class evading our detection and one ET for a backdoor target class lying close
to the threshold $\frac{1}{2}$, the separation of ET for backdoor target
classes and non-target classes is even better than that in the bottom left
figure in Fig. 2 (where backdoor pattern reverse-engineering is performed on
typical MNIST images). The possible reasons maybe:

  * •

For non-attack cases, two independently synthesized samples predicted to the
same class will likely be both atypical to their predicted class. They will
likely share fewer features associated with their predicted class than two
independent typical samples from this class. They can also be located anywhere
in the input space. Thus, they will be more likely to be “mutually not
transferable”.

  * •

The synthesized samples are also far from the data manifold of classes other
than the class they are predicted to. So the minimum perturbation size
required to induce them to be misclassified will have a large norm – possibly
larger than the norm of the backdoor pattern when there is an attack. If this
is the case, the ET statistic will be exactly 1 based on Thm. 3.3.

Future works along this research line include further investigation of the
phenomenon we observed, and also improvement to the model inversion
techniques, such that more complicated domains can be handled.