Defending Against Backdoor Attacks Using Ensembles of Weak Learners 
Authors: Charles Jin
Melinda Sun
Martin Rinard
Venue: ICLR 2022 Submitted (2022)
Keywords: data poisoning

Abstract: A recent line of work has shown that deep networks are susceptible to backdoor data poisoning attacks. Specifically, by injecting a small amount of malicious data into the training distribution, an adversary gains the ability to control the behavior of the model during inference. We propose an iterative training procedure for removing poisoned data from the training set. Our approach consists of two steps. We first train an ensemble of weak learners to automatically discover distinct subpopulations in the training set. We then leverage a boosting framework to exclude the poisoned data and recover the clean data. Our algorithm is based on a novel bootstrapped measure of generalization, which provably separates the clean from the dirty data under mild assumptions. Empirically, our method successfully defends against a state-of-the-art dirty label backdoor attack. We find that our approach significantly outperforms previous defenses.

Under review as a conference paper at ICLR 2022
DEFENDING AGAINST BACKDOOR ATTACKS USING ENSEMBLES OF WEAK LEARNERS
Anonymous authors Paper under double-blind review
ABSTRACT
A recent line of work has shown that deep networks are susceptible to backdoor data poisoning attacks. Specifically, by injecting small amount of malicious data into the training distribution, an adversary gains the ability to control the behavior of the model during inference. We propose iterative training procedure for removing poisoned data from the training set. Our approach consists of two steps. We first train ensemble of weak learners automatically discover distinet subpopulations in the training set. We then leverage boosting framework to exclude the poisoned data and recover the clean data. Our algorithm is based on a novel bootstrapped measure of generalization, which provably separates the clean from the dirty data under mild assumptions. Empirically, our method successfully defends against state-of-ther -fete-rrr-e- dirty label backdoor attack. We find that our approach significantly outperforms previous defenses.
OVERVIEW
The past few years has seen the rapid adoption of deep learning in real world applications, from digital personal assistants autonomous vehieles. This trend shows no sign of abating, given the remarkable (super)human performance of deep neural networks on tasks such as computer vision (He
al. 2016a). speed recognition (Graves al. 2013). and game playing (Silver et al. 2016).
However, this widespread integration of deep networks presents a potential security risk, particularly in performance- and safety-critical applications. In this work, we focus on defending against backdoor attacks (Chen et al. 2017]] Adi et al. 2018). Specifically, it has been demonstrated that deep networks can be attacked by injecting small amounts of poisoned (i.e., maliciously perturbed) data during training to create backdoor in the model; once installed, an adversary can exploit the backdoor to change the network's predictions at inference time. For instance, Gu et al. (2019) demonstrate a backdoor that causes model to misclassify stop signs speed signs by applying a (physical) sticker. These attacks are particularly pernicious in that the accuracy of the model on unperturbed data is generally not affected by the backdoor, thus making it difficult to identify compromised models during standard operation.
Techniques We first introduce the notion of self-expanding sets, which based on a bootstrapped measure of how well a set generalizes to itself. Under certain compatibility properties, we show that the process of identifying self-expanding sets naturally separates dataset into collection of homogeneous components (i.c., completely clean or completely poisoned subsets of the training data). Given such collection, we then provide a method to identify the clean distribution by boosting an ensemble of weak learners over the components.
To separate the training set into homogeneous components, we present the Inverse Self-Paced Learning algorithm. This algorithm uses quantile statistics to repeatedly identify and exclude samples with high loss. Recursively applying the technique to sets of excluded samples produces the collection of homogeneous components. We prove sufficient conditions for the convergence of the algorithm.
Experimental Evaluation We implement the proposed Inverse Self-Paced Learning algorithm within our boosting framework and evaluate its performance on two different backdoor attacks on CIFAR-10 (?). Our method completely defends against the attacks in almost every setting and

---

Under review as a conference paper at ICLR 2022
substantially reduces the success rate of the attack in the remaining cases, while reducing the accuracy on clean data by only 2-3%. Our results also show that previous approaches (Tran et al. 2018 Chen et al. 2018 Shen and Sanghavi, 2019) are substantial weaker at identifying poisoned samples. These previous approaches also either require an explicit upper bound on expected amount of poison or suffer from high levels of false positives. Our approach thus presents novel, empirically verified method for defending against backdoor attacks.
2 RELATED WORK
Our separation results can be viewed as solutions to a clustering problem, where we exploit weak supervision in the form of class labels, related via our notions of self-expansion and compatibility. Many previous works analyze similar properties for weak or semi-supervised learning based on clustering (Seeger) 2000 Rigollet, 2007; (Sighh et al. 2008) or expansion (Wei et al., 2020). In general, these works define expansion as an intrinsic property of the input data, rather than with respect to (weak) learner we do. [Baccan al. (2005) show that under similar expansion property, learners fit independently to two different "views" of the data can supervise each other to improve their joint performance. However, a major departure from these prior works is that do not use an expansion property to leverage small set of trusted or confident labels for minimizing a global classification error, but rather use self-expansion to identify homogeneous components by fitting weak learners to certain local minima.
We also introduce the Inverse Self Paced Learning algorithm for efficiently finding eeff-expanding sets. Self paced learning (SPL) was introduced by Kumar et al. (2010) as an type of curriculum learning (Bengio et al., 2009). SPL is a heuristic that dynamically creates a curriculum based on the losses of the model after each epoch, so as to incorporate the easier samples first. SPI. and its variants have been observed to be resilient to noise both in theory (Meng et al. (016)) and practice (Jiang al. 2018 Zhang et al. 2020), though prior works focus mostly on clean accuracy under unrealizeable label noise. In contrast, we measure targeted misclassification accuracy under more challenging noise distributions that are adversarially selected to be realizeable.
Finally, several prior works propose methods for defending against backdoor attacks on neural networks. In general, it has been observed that standard techniques from robust statistics applied directly to the data do not successfully identify the poisoned data (Tran et al., 2018). The standard approach is therefore to first fit deep network to the poisoned distribution, then apply techniques to the learned representations in the network layers. The Activation Clustering defense (Chen et al., 2018)) uses dimensionality reduction followed by k-means clustering (k=2) on the activation patterns, and discards the smallest cluster. Tran el al. 2018) propose Spectral Signature defense that removes the data with the top c eigenvalues, where e is set to 1.5 times the amount of expected poison. TRIM (Jagielski et al., (02T) (for linear regression) and Iterative Trimmed Loss Minimization (Shen and Sanghavi 2019) (for generalized linear models and deep neural networks) iteratively train on a subset of the data after removing constant fraction of the samples with the highest loss. However, the majority of works do not evaluate their defenses on CIFAR- 10, opting instead for simpler datasets, such traffic signs or MNIST. Furthermore the triggers skew large and obvious (such as 3x3 patches QQao et al. 2019) or legible text overlays (Gao et al. 2019a)) ) and are often constrained to lie the center of the image; our evaluation shows that existing defenses fail when evaluated on the more subtle triggers we use.
BACKGROUND AND SETTING
We first establish some basic notation and the scope of our classification setting. Let X be the input space, Y be the label space, and L(.,,) be a loss function over Y x Y. We assume a bounded loss func- tion, which includes many commonly used loss functions such as the zero-one or cross entropy loss. Given a target distribution DD supported on X x Y and a parametric family of functions fo, the goal to find the parameters 0 that minimize the population risk R(0)= == Jxxx T.(fo()), y) v)d (a. y)-
The learning problem (fe. D) is realizable if (1) for every label y. the marginals D(-lg) have disjoint support; and (2) there exist ground truth parameters 0* with R(8*) O. For simplicity, we assume (possibly stochastic) learning algorithm A that performs empirical risk minimization, i.c., given a set of samples T. A tries to return minimizing Remp T) Σier [(fo(x)), vi). Clearly, given
2

---

Under review as a conference paper at ICLR 2022
enough training samples S = (111, v1 y1)..., (En, Mn)) } iid from D, the empirical risk gets arbitrarily close to the population risk. We will identify the training set S with its indices [n]]
3.1 DATA AND THREAT MODEL
We consider mixture of distributions {(ag, D:) such that D = U;(D;} and Σ, a, 1. We observe N inputs according to the following two-step procedure:
d ~ Cat(ar..... .... an)
(1)
2, y- Da
(2)
where Cat(-) a categorical random variable that returns i with probability a; If S is a set of samples produced by this process, for any subset S" S. we will denote the samples drawn from the 7th distribution as Sy, so that = U.
Our evaluation focuses the backdoor data poisoning model. It has been observed empirically that injecting a small amount of malicious data into the training distribution effectively installs a backdoor in the model, whereby the behavior clean data is otherwise unaffected, but attacker can cause targeted misclassification during inference by overlaying a small trigger. In this case sampling from the training distribution modeled follows:
Cat(ar, ... Onn)
(3)
3, y ~ Dj p~ Bern(p)
(4)
(5)
I + ( - (y), i
(6)
where T(-) is the function which applies a small trigger, x(-) is a permutation on classes, and controls the probability of observing a poisoned sample. Note that this procedure can easily be replicated within the original data model. We will also assume the attack is non-trivial in the sense that the perturbed source distributions T r(D:) and target distributions D Pi()) are disjoint for all
Given model fo(-), we measure the success of the attack using the targeted misclassification rate:
Aemp T) Eife(z)) y fe(T(z:)) T(4))
iET
In other words, the attack succeeds if, during inference, it can flip the label of correctly-classifee instance by applying the trigger T(-).
3.2 LEARNING OBJECTIVE
We formulate our learning objective in the general data model of Equations [ Without loss of generality, assume the first distributions are primary distributions, and the remaining n p noise distributions. Given a training set S, we write Sp = Si U U... U S, for the samples from primary distributions, and Sx = Sp+1 U... U U,S for the samples from the noise distributions.
Our goal is learn parameters which correspond to training only the primary distributions: i = A(Sr). Note this objective differs significantly from simply minimizing the risk over the primary distributions when the mixed distribution D is realizable, i.e., we are also interested in avoiding effects that occur on portions of the input space that have low density in the primary distributions. More explicitly, in terms of the data poisoning threat model (Equation 7 we note that training on Sp SN would yield low risk over the unperturbed distributions, but also high targeted misclassification risk. Conversely, for sufficiently separated distributions r r(D)) and (r),), we expect that the hypothesis class fo enjoys low targeted misclassification risk when trained only on clean data.
4 SEPARATION OF MIXED DISTRIBUTIONS
We next introduce the main theoretical propertics that allow us to separate the primary and noise distributions. Our main tool is a property of "self-expanding" sets; intuitively, given a set,
3

---

Under review as a conference paper at ICLR 2022
resample at given rate and measure how well the learning algorithm generalizes to the rest of the set. Given primary and noise components satisfying certain compatibility properties, we show that the set with the optimal expansion must be homogeneous, i.c. drawn entirely from either the primary or noise components. Finally, we fit weak learners to the recovered (homogeneous) sets in a simplified boosting framework identify the primary component.
4.1 SELF-EXPANSION AND COMPATIRILITY
We begin by stating formal characterization of the self-expanding property of sets: Definition 4.1 (Self-expansion of sets.). Let and T be seis. We define the a-expansion error of given T for all 0 S or S 1 such that a [S| is integral as
<(S)T; ax) == [|emp UT)
(8)
where the expectation is over both the randomness in A and S', a random variable of a|SS samples drawn from S with replacement.
This self- eeffexxaasiion property measures the ability of the learning algorithm A to generalize to the empirical distribution of a set S with the help of additional training samples T'; intuitively, smaller expansion error means that the set S is both "easier" and "more homogeneous" with respect to the learning algorithm and T. When T = we will also write c(S: a) instead of c(S)@0; a)). a is also referred to the subsampling rate. Finally, interpolating between the value at integral sample sizes.
will extend e(S)T; a)) to all
S by linearly
We now self-expansion define notion of compatibility between sets: Definition 4.2 (Compatibility of sets.). A (nonempty) set T is a-compatible with set S with margin 8 2 if
<(ST: a) + S <((;a)
where the expectation is over the same random variables as in the definition of self-expansion. Furthermore, T is completely a-compatible with S if all (nonempty) subsets T" T are a-compatible with S. Conversely, T is a-incompatible with S if the opposite holds, i.e.,
<(S:a) + 8 a)
(10)
(and similarly for complete incompatibilityy. We also say that strict compatibility (incompatibilitty holds when 5 >> 0.
In other words, is compatible with S if the self-expansion error of given T is not worse than the self-expansion error of S by itself.
In what follows, we make use of the following assumptions about expansion:
Assumption 4.3 (Properties of expansion). The learning procedure satisfies the following:
(1) <(S)T: a)) is a convex function of a E [0, 1] such that e(S)T;; 1) = for all S,T
(2) T is a-incompatible with S. then T is B-incompatible with S for all B 2
The first assumption rules out the existence of pathological sets where increasing the number of samples degrades performance and also says that memorization of the training set always occurs. Convexity holds when the expected marginal information gained from additional samples decreases as the number of samples increases. The second assumption says that increase the amount of data from S in the training set (which always improves performance, regardless of the compatibility of T) should not flip an incompatible into a compatible set.
The following key property enables us to separate the primary and noise distributions. Intuitively, we want the primary and noise mixture components to be negatively correlated (or at least independent) in the sense that training a noise distribution should not improve performance on primary distribution, and vice versa:
Property 4.4 (Incompatibility of primary and noise distributions). Let be given. Then any pair of (nonempty) sets Sp and SN drawn from D; U ...UD, and D Dp+1 U ... U Dz,, respectively, are strictly and completely a-incompatible.
4

---

Under review as a conference paper at ICLR 2022
Our technique is designed for separating primary and noise distributions that satisfy this property.
We are now ready to state the main result of this section. Given Property 4.4 we show that any subset of S which achieves the minimum expansion error consists entirely of data drawn from either the primary or noise distributions:
Theorem 4.5 (Sets minimizing expansion error homogeneous.). Let S S1 U Sn be set of samples drawn from mixture of distributions {(as, D: Define
5* == arg min aa) S'CS
(11)
for some expansion factor a. Then if Property 4.4 holds for a, we have either that S C Sp or S C Sx, where Sp S1 U...U.ppp and SN Sp-1 U...
We defer the proof to Appendix A Intuitively, if two distributions are incompatible, then adding data from one distribution to a homogeneous set of the other should only increase the self-expansion error.
Remark 1 Theorem 4.5 relies crucially on the incompatibility between the samples from the
primary distribution S U... U... Sp and the noise distribution Sp+1 U U Sn, derive the homogeneity of SS* condition which depends on the interaction between the data S and the learning algorithm A. We note that the requirement is empirically satisfied in many data poisoning settings. For example, common adversary for backdoor attacks against deep neural networks inserts a small synthetic patch in the corner of the image, which, by design, is a location on which the classification does not depend. In this case, the labels for the primary and noise distributions depend on disjoint dimensions of the input, which gives very clean example of incompatible distributions; given the number of shared (spurious) features, empirical results suggest that the two distributions are, in fact, strictly incompatible for moderately large sets as well.
In general, the larger a is in Property 4.4 the easier it estimate the value of <(S; a)); the most convenient case would be for incompatibility to hold even when = 1, in which case c(S: a) can be evaluated exactly with one call to A. Unfortunately. for overparameterized models trained using empirical risk minimization, we have that 1); 0 for all S (since we assume the problem realizable the limit). One method to circumvent this problem to prevent A from converging, c.g., by using early stopping. In fact, it is well known that regularizing deep neural networks trained with Stochastic Gradient Descent using early stopping is resilient to noise (Li et al.) 2020 In experiments, we find that combining early stopping with our self-expansion property leads to further improvements in performance.
Remark 2
4.2 IDENTIFICATION USING WEAK LEARNERS
The development of the previous section suggests iterative approach separating the primary and noise distributions. In particular, if we fix the expansion factor a, at each step, we can identify the set S* which achieves the lowest expansion error and remove it from the training set. Repeating this procedure partitions the training set into groups of compatible sets. While this suffices to separate the primary and noise distributions, it remains identify which components belong to the primary distribution.
We next propose simplified boosting framework for identification of the primary distribution. We assume the setting of binary classification and use the 0-1 loss, so that the empirical risk simply counts the number of elements which are misclassified. Our approach is fit weak learner each component, then use each learner vote the other components.
Algorithm I presents our approach for boosting from homogeneous sets. The subroutine Losso, takes set of parameters and set of samples, and returns the empirical zero-one loss over the entire set. Note that votes are weighted by size.
The correctness of Algorithm [gorithmmfolloww follows from an analogous compatibility property (cf. Property 4.4h: Property 4.6 (Compatibility of primary distribution). Let a be given. Then any pair of (nonempty) sets St and Sj drawn from D; and D,, respectively, such that i, S n, are strictly and completely a-compatible.
Finally, we also require unbiased priors for weak learners:
5

---

Under review as a conference paper at ICLR 2022
Algorithm I Boosting Homogeneous Sets
Input: Homogeneous sets S Sv, total number of samples number of estimates B, weak
learner A
Output: Votes 11, 11,... VNN
1: Ci.... C2 f-
2: for = 1 to N do
3: Va...., ViN t- 0
4: for j j=
B do Oi + A(S:)
5:
6:
for k 1 to N do
7:
V + V + Lossu,1 So)
8:
end for end for
9:
for k = to N do
11:
if Vik S then
12:
C < Ck + [
13: end if
14: end for
15: end for
16: for = 1 to do
17: Vi f- C n12
18: end for
Property 4.7 (Weak learners are unbiased.). Let St be any sets. Then for any untrained weak learner, have also that [[ (A))); S;)] 1S.1/2.
This condition is necessary in that the weak learners should not be biased toward learning the noise distributions. Finally, we state the main result this section, whose proof is deferred Appendix A Theorem 4.8 (Identification of primary samples). Let S be a set of samples drawn from mixture 4.44
such that Properties 4.4 4.6 and 4.7 hold, and assume that the ratio of primary samples p Spl/[S] > 1/2. Let S1, SN n be partition of S produced by iteratively applying Theorem 4.5 Then if A is deterministic, Algorithm | returns with B = for all
of distributions (a,, Dj D.), 1-
components containing samples from the primary distribution, and 0 otherwise.
If A is stochastic, the same result holds with probability
2 MN
(12)
where M is the number of primary components, and B is the number of independent weak learners used each primary component.
Remark 3 At a high level, the approach to identifying the primary distribution presented in folloows
Theorems 4.5 and follows simplified boosting framework: at each step. we weak learner to subset of the distribution, then reweight the remaining training samples by removing the identified component; the ensemble of weak learners is then aggregated using a majority vote. However, our setting is somewhat unique so for clarity mention several key differences. First, in general the objective of standard boosting is to achieve low population risk, thus the reweighting is performed via more sophisticated methods such using the empirical loss of the ensemble thus far, e.g., AdaBoost (Freund et al. [996); in contrast, our setting there are subpopulations over which we would actually like to maximize the risk. Another difference is that in standard boosting, the ensemble is used during inference to vote on new observations to perform classification, whereas our algorithm, we use each learner vote over components of the training
a.5]and|4..
filter the noise distributions. Finally, note that we can succeed with arbitrary probability by taking the number of samples B to infinity.
5 INVERSE SELF-PACED LEARNING
major question raised by Theorem 4.5 is how to identify the set S in its statement. this section, propose algorithm called Inverse Self-Paced Learning (ISPL.) solve this problem. Rather

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Inverse Self-Paced Learning
Input: training set S, total iterations N, annealing schedule 1 > 30 2 ... NN Bmi 0,
expansion a S I, momentum 7, incremental learning procedure A, initial parameters 0g Output: SS - such that [Sx] [y|
1: So 5
2: L 4-0
3: for = 1 to do
4:
5" Sample(S;-1, (1
5:
0: f A(S", 02-1)
6:
L f nL+ + (1 -1) Remp (0,s S)
7: St < Trim L, 31)
8: end for
than optimizing over all possible subsets of the training data, our objective will instead be to minimize the expansion enror over subsets of fixed size B|S). The optimization objective is defined as:
S% == arg
min S' = a(S::a)
(13)
We attempt to solve for S3 by alternating between optimizing parameters 9, and the training subset St. More explicitly, given S' we update using a single subset from S' size a "|5' Then we to compute the loss for each element in S, and set S' to be the 3 fraction of the samples with the lowest losses. To encourage stability of the learning algorithm, the losses are smoothed with an optional momentum term 7/. We also anneal the parameter / from initial value 30 down to the target value Buin in order encourage more global exploration in the initial stages.
Algorithm| 2 presents the full algorithm. In addition to the incremental learning procedure A (e-g., standard SGD), the subroutine Sample takes a training set S and returns S| elements uniformly at random; while Trim takes losses L and returns the 3|4] samples with the lowest loss.
2 converges on the following objective over Finally, we show for certain parameters that Algorithm the training set S:
F(O,, B:) = Σ (f u)) + cmax(0,, - (vel)
(14)
iES
where is 0-1 vector, 3r is decreasing, and T(.,)) S.
Proposition 5.1. Let a and n in the setting of Algorithm and assume that A returns the empirical risk minimizer. Then we have that for each round of the algorithm, F(Or, 06 Bi) is decreasing and furthermore, [( 04; B,) F(0.+1 U1413 Be+1)l 1-220 0.
We defer the proof of Proposition 5.1 to Appendix A
When 1 and 17 0, recover vanilla self self-paced learning (SPL) with two major differences. First, we start on the full set of samples and train on incrementally smaller sets, while SPI. starts with small set of samples and trains on larger sets. This discrepancy is due to the differing objectives; whereas SPL is heuristic for converging faster to global minimizer of the population loss by training first on easy samples, ISPL attempts to converge subpopulation. Second, our annealing schedule is defined using the quantile statistics, while SPL uses an absolute loss threshold that generally scales by a multiplicative factor in each iteration. We chose this to counteract the propensity of deep neural networks to suddenly and rapidly interpolate training data; in our experiments, we found this behavior made the performance of ISPL very sensitive to the specific annealing schedule when using absolute losses. Conversely, in SPL the final threshold is generally set high enough that most (or all) the samples are incorporated by the end, and so the specific schedule may have smaller impact the final performance.
Remark 4
local minimum over
6 EXPERIMENTAL EVALUATION
We evaluate our defense against the standard patch- patch-based backdoor attack with dirty labels, where the adversary inserts small patch into training image from the source class, then changes the label
7

---

Under review as a conference paper at ICLR 2022
Figure I: CIFAR-I0 images with triggers applied (top), selected maximize trigger visibility.
Table I: Results against dirty label backdoor adversary for select pairs of CIFAR-10 classes using single pixel trigger. The numbers in column refer the standard CIFAR-10 labels (e.g.. 0 airplane, = automobile, etc.). Column gives the (x. coordinates of the trigger. S = source class, T target class, C = clean accuracy (higher is better), targeted misclassification rate (lower better). Results for our method are in the last two columns under TW (this work).
No defense
SS
AC
ITLM
TW
S/T
pos
C
A
C
A
C
A
C
A
C
A
5
94.5
75.6
94.3
74.7
92.4
53.9
94.7
79.4
92.5
0.1
2/5
(27, 9)
94.6
95.2
94.4
0.0
92.9
81.8
94.7
92.4
93.0
0.0
20
94.7
98.1
94.2
0.0
92.6
89.4
94.6
96.3
92.8
0.0
5
94.8
99.3
94.6
50.0
92.2
39.2
94.6
57.2
92.0
0.1
1/3
(15, 4)
10
94.5
99.2
94.2
10.4
92.0
47.9
94.5
75.0
92.9
0.3
20
94.5
98.8
94.3
1.5
91.9
60.5
94.2
92.3
92.3
1.3
94.7
84.1
94.8
80.5
92.8
73.3
94.4
76.3
93.1
0.0
8 8/6
(4, 1)
10
94.6
96.4
94.2
96.0
92.2
97.0
94.5
94.2
93.0
0.0
20
94.1
98.1
94.3
0.0
92.5
96.4
94.1
96.4
92.9
0.0
5
94.9
98.0
94.4
65.7
92.8
79.7
94.7
97.6
93.0
0.0
9/2
(4, 27)
10
94.9
99.1
94.6
0.0
92.6
80.8
94.4
99.3
92.9
0.0
20
94.7
99.1
94.3
0.0
93.1
98.9
94.1
99.1
93.1
0.0
of the image the target class. The goal is induce the learner to miselassify images from the source class as the target class upon application of the patch. Results in this section use standard PreActResNet18 architecture (He et al. 20166) that achieves 94% accuracy on CIFAR-10 when trained on a clean dataset. The appendix provides full experimental details and additional results.
6.1 RESULTS
Our implementation of the dirty label backdoor adversary follows the threat model described in Gu al. (2017). The perturbation function 7 simply overlays small pattern on the image. For evaluation, we use the same dataset (CIFAR-10 (?)) and setup for our experiments as Tran et al.
(2018). Example pairs of clean and poisoned data are shown in Figure D
Table presents results for the single-pixel backdoor attack, in which the adversary randomly selects a position and color for the backdoor and applies the trigger by replacing the pixel at that position with the selected color. The first column, S T, presents numbers in the form S T, where S is the source class and T is the target class in CIFAR-10. The goal of the attacker is to induce the network to misclassify poisoned images from the S class to the T class. The second column, pos, presents numbers the form (X, Y) where X, the position the single pixel trigger. The third column, e, presents the percentage of the source class in the training that is poisoned by the adversary.
8

---

Under review as a conference paper at ICLR 2022
We report results for our defense, This Work (TW), in the last column, in addition to four baseline defenses: 1) No defense, 2) Spectral Signatures (SS) (Tran et al., 2018). 3) Activation Clustering
(AC) CChen al. 2018), and 4) Iterative Trimmed Loss Minimization (TTLM) (Shen and Sanghavi 2019). J. For each defense we report the percent accuracy over the clean images in the test set (column C, higher is better, maximum is 100% when all clean images are classified correctly) and the targeted misclassificction rate (Equation 7 over patched images of the target class in the test set (column A, lower is better, minimum 0% when none of the poisoned images are misclassified). The results show that the technique we present in this paper 1) almost completely defends against this attack (column ranges from 0.0% to 1.3%) at the cost of 2) small (roughly 2%) decrease in the clean accuracy (column C, clean accuracies around 92-93%). All other defenses exhibit significant vulnerability to this attack (column A, No defense, SS, AC, and ITLM).
6.2 DISCUSSION
Many data poisoning defenses in the literature are evaluated on simpler datasets than those considered in this paper, such as traffic signs (GTSRB (Houben et al., (013) or LISA (Mogelmose et al.) 2012) and MNIST (?). Furthermore, these datasets are tested in conjunction with larger otherwise more obvious triggers. For instance, the Neural Cleanse (Wang ct al. 2019) defense uses a 4x4 white box as the trigger on the MNIST and GTSRB datasets; MESA (Qiao et al. 2019) uses 3x3 image as the trigger on CIFAR-11 10 and test only at = 1%; TABOR (Guo et al. 2019) uses a 6x6 square as the trigger for GTSRB for images that are 32x32 (they additionally test on ImageNet but do not report good results until the trigger is over 25% of each dimension); and STRIP (Gao et al. (019b) uses an 8x8 box on CIFAR-IO. Our hypothesis is that the combination of a smaller trigger and more complex classes breaks defenses that demonstrate good performance in simpler contexts. Table [T] reports results using a single pixel trigger, which is often placed at the border of the image, within the region cropped by the standard random cropping data augmentation during training.
For comparison, we implemented the AC defense, which is included in the Adversarial Robustness Toolbox (Nicolae al. 2019), an open-source collection of tools for security in machine learning. The authors report that AC achieves nearly perfect performance on two popular settings, namely, MNIST and traffic signs. We also implemented ITLM, which was tested on CIFAR-10 at E 5% using larger L- and X-shaped triggers. Our results in Table [ iindicate that both AC and ITLM fail to completely defend against the poison in every setting, with the best targeted misclassification rate achieved by AC at 39.2% (compared to nearly 0% in every case with our defense).
To the best of our knowledge, SS is the only other defense in the literature which evaluated using the same dataset (CIFAR-10) and class of triggers. The defense uses the eigenvectors of the feature matrix to separate clean and poisoned data. However, the authors do not appear to use triggers that can be cropped out during training by data augmentation. They also limit evaluation to "successfully" attacked networks, which they define as over 90% targeted misclassification rate the undefended network (Column A, No defense). While our experiments suggest that SS is the strongest baseline after ours, successfully defending against the poison in 6 of the 12 scenarios considered in Table [ its performance is poor particularly at lower Our results suggest that SS may fail to defend against harder to learn triggers requiring more complex feature representations.
7 CONCLUSION
Backdoor data poisoning attacks on deep neural networks are an emerging class of threats in the growing landscape of deployed machine learning applications. Though defenses exist, our experi- ments suggest that they only work against narrowly defined adversaries and fail dramatically when evaluated using more subtle threat models.
We introduce a new approach to defending against backdoor attacks based on an analysis of a novel self-expansion property in the training data. For a poisoned dataset satisfying mild compatibility properties, we show that an ensemble of weak learners fit to self-cxpanding sets successfully removes the poisoned data. Empirically, our method is resilient attack introduced by Gu et al. (2017), which successfully evades all the baseline defenses. We believe our analysis and techniques present valuable addition to the toolbox for secure deep learning.
strong version of the dirty label backdoor

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yossi Adi, Carsten Baum, Moustapha Cisse, Benny Pinkas, and Joseph Keshet. Turning your weakness into a strength: Watermarking deep neural networks by backdooring. In 27th {USENIX) Security Symposium (!USENIX) Security 18), pages 1615-1631, 2018.
Maria-Florina Balcan, Avrim Blum, and Ke Yang. Co-training and expansion: Towards bridging theory and practice. Advances in neural information processing systems, 17:89-96, 2005.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston, Curriculum learning. In Proceedings of the 26th anmual international conference on machine learning, pages 41-48, 2009.
Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by actívation clustering. arXiv preprint uriiv:/81.00322 2018.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv:/712.05526, 2017.
Yoav Freund, Robert Schapire, et al. Experiments with a new boosting algorithm. In ICML, volume 96, pages 148-156. Citeseer, 1996.
Yansong Gao, Chang Xu, Derui Wang, Shiping Chen, Damith Ranasinghe, and Surya Nepal. Strip: A defence against trojan attacks on deep neural networks. In 35th Annual Computer Security Applications Conference (ACSAC), 2019a.
Yansong Gao, Change Xu, Derui Wang, Shiping Chen, Damith C. Ranasinghe, and Surya Nepal. Strip: A defence against trojan attacks on deep neural networks. In Proceedings of the 35th Annual Computer Security Applications Conference, ACSAC '19, page 113-125, New York, NY, USA, 2019b. Association for Computing Machinery. ISBN 978 47834600. doi: 10.1 10.1145/3359789 3359790. URL
3359790
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks, 2013 IEEE international conference on acoustics, speech and signal processing. pages 6645-6649. Ieee, 2013.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint
2017.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv:1708.0677 2019.
Wenbo Guo, Lun Wang, Xinyu Xing, Min Du, and Dawn Song. Tabor: A highly accurate approach to inspecting and restoring trojan backdoors in ai systems. arXiv preprint arxiv:1908.0/765: 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. arXiv preprint 10xiv:1502.008522 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016a. 6a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. arXiv preprini arXiv: 1603:06603. 2016b..
Sebastian Houben, Johannes Stallkamp, Jan Salmen, Mare Schlipsing, and Christian Igel. Detection of traffic signs in real-world images: The German Traffic Sign Detection Benchmark. In International Joint Conference on Neural Networks, number 1288, 2013.
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. arXiv preprint arXiv: 0880000000 2021.
and Bo Li.
10

---

Under review as a conference paper at ICLR 2022
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentomet: Learning data- driven curriculum for very deep neural networks on corrupted labels. In International Conference Machine Learning, pages 2304-2313 PMLR, 2018.
M Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. Advances in neural information processing systems, 23:1 189-1197, 2010.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust label noise for overparameterized neural networks. In International Conference on Artificial Intelligence and Statistics, pages 4313-4324. PMLR, 2020.
Deyu Meng, Qian Zhao, and Lu Jiang. What objective does self-paced learning indeed optimize? arXiv preprint arviv: / 1.6049, 2016.
Andreas Mogelmose, Mohan Manubhai Trivedi, and Thomas B. Moeslund. Vision-based traffic sign detection and analysis for intelligent driver assistance systems: Perspectives and survey. IEEE Transactions on Intelligent Transportation Systems, (544):44441497 2012. doi: 10.1109/TITS
2012.2209421.
Maria-Irina Nicolae, Mathieu Sinn, Minh Ngoc Tran, Beat Buesser, Ambrish Rawat, Martin Wistuba, Valentina Zantedeschi, Nathalie Baracaldo, Bryant Chen, Heiko Ludwig, Ian M. Molloy, and Ben Edwards. Adversarial robustness toolbox v1..00. arXiv preprint (rxXiv:887.00066 2019.
Ximing Qiao, Yukun Yang, and Hai Li. Defending neural backdoors via generative distribution modeling. arXiv preprint arXiv: 1xXiv:/910.00 1910.04799 2019.
Philippe Rigollet. Generalization error bounds in cumi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(7), 2007.
Matthias Seeger. Learning with labeled and unlabeled data. 2000.
Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. arXiv preprint 18000 /1874, 2019.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Panncershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):4844889 2016.
Aarti Singh, Robert Nowak, and Jerry Zhu. Unlabeled data: Now it helps, now it doesn't. Advances in neural information processing systems, 21:1513-1520, 2008
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. arXiv preprint arXiv:1811.00633 2018
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium on Security and Privacy (SP), pages 707-723. IEEE, 2019.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622. 2020.
Xuchao Zhang, Xian Wu, Fanglan Chen, Liang Zhao, and Chang-Tien Lu. Self-paced robust learning for leveraging clean labels in noisy data. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6853-6860. 2020.
11

---

Under review as a conference paper at ICLR 2022
A DEFERRED PROOFS
Lemma A.1. Let SN and Sy be two sets satisfying Property 4.4 and let S and T be drawn from SN and Sp, respectively. Then for all 0 < << < a, S and T mutually strictly 7--nncompatbbe.
Proof. We will show that T is 7-incompatible with S for all S a: mutual incompatibility follows by symmetric argument. First, is a-incompatible with S by consequence of Property 4.4 Fix a. Our main approach will be to subsample S twice: first, we sample S at a rate of 7/ax to create S' such that [S|| ~ 7/a[S]. Then S' a-incompatible with T, ((5')T, a) 2 cS'', a). However we need take some care to ensure 7/a|S| is an integer.
Define
S|
a' ST|S|/a]
(15)
Then a' 2 a and
Thus, we will subsample at a rate of r/ to create S" by Assumption 4.3 T a' o'-incompatible with S'. Note that the resulting training sets produced by this
double subsampling procedure have size 7|5| as desired.
Next, we will show that there exists constant such that
<(SIT, cl7////)))
(16)
<(S, = <(>/a' ( "){{"")
(17)
where the expectations are taken over the subset S' c |8) 7/a//S]. Then since T is strictly a a'-incompatible with all such S' by Property 4.4
<(SIT,7) = c|s' "E'ssss
(18)
> c|S" "Be("""""(S"))))
(19)
(20)
which is what we wanted to prove.
Fix a training set S" |S"| >|S]. and let T be arbitrary. By Assumption 4.3 we have that Remp(Af UT); for all T". Then conditioning on the training set S", we have that
('(Ss = ElRemp (A(S" S')
(21)
= -E| UT): -S")s""
(22)
where the expectation is over S' such that S" Now S' - S" is random variable consisting of [S"| - ||5" independent draws from S with replacement; thus Equation 22 is just equal to |SS - SS times the empirical risk of random element in S. On the other hand, (emp(A((") UT; is the empirical risk over all elements in S, or equivalently, [S] times the empirical risk of a random element.
Since was arbitrary, summing over all possible training sets S" yields the desired identities with
S
(23)
1
S"
Proof of Theorem 4.5 We first prove slightly more general result. Assume by way of contradic- tion that there exists a partition of S* into two nonempty sets and Q that are mutually strictly incompatible.
Let c" be the expansion error of S*, Recall that this means
S = S ae) = (A(S") S*)]
(24)
where the expectation is taken over samples S' of size |S drawn from S' with replacement. Since the empirical risk is linear function of S*, we can decompose this last term as
E Remm (A(S"): St)] E. Reemp (A(S") P)] + (ERemmp (A(S":: Q)]
(25)
12

---

Under review as a conference paper at ICLR 2022
Given set of training samples S", will denote the elements drawn from P and Q P' S' n and Q' = S" i Q, respectively. Now consider the term
E ([ = E[ U P))
(26)
If we fix Q', then Pf is drawn uniformly at random from P with replacement, where |P'| a.S - 1Q'). Define
aq' | 1Q"
(27)
PP]
which is the subsampling rate of P given Q'. Note that if 2 a, then Q' is a' oiicoompaaiible with p' by Assumption 4.3 and otherwise a' < and Q' is strictly a' a'-incompatible with / by Lemma
A.1 Thus,
E
Pr[Q (APP(((PPPP))))) P)
(28)
Q'
= IPI
Pr(Q')=(PQ'''a'))
(29)
P
PP(Q))((P:aq))
(30)
On the other hand, B[aq.] a, and since e(P:a) is convex in by Assumption Jensen's inequality to conclude
4.3
can apply
pr(0) (P:a),
(31)
i...
ElRemp (APP)
(32)
Similarly,
E[ (1
(33)
Combining these two results yields
| +
(34)
Since |P| [Q] |. we have that at least of E E(P; a) e(Q;a) must be less than e", which contradicts the optimality of St. Thus one of P or Q must be empty.
Finally, note that by Property 4.4 the partition P S* n Sp and S n Sy gives incompatible partition, which yields the result.
Proof of Theorem 4.8 We begin with the simple observation that if Properties 4.4 and 4.6 hold for S, they also hold for 5 S' for any set S", Thus we are able to apply Theorem 4.5 at each step and so in fact Si.... SN are all homogeneous. Additionally, since p > 1/2 and component's vote is weighted by its size, sufficient condition for success is when all the primary components vote correctly.
We start with the case when A deterministic. Let St and Sy be a primary component and noise component, respectively. By strict incompatibility. we have that Remp(A(S)) Remp(A(0): S,) |S,1/2. Thus S, votes on Sy. Conversely, then Remp (,) < Remp (A(0) using the fact that p > 1/2, we find that the noise components have weighted vote strictly less than [8|/2, while the primary components have weighted vote strictly greater than |S| /2, as required.
> S, is a primary component, |S,1/2. so S; votes I on Sj. Putting these together and
For the case when A is stochastic, we apply standard concentration bounds to our estimates of the empirical risk of each component (over the randomness in A). Let S, and S be primary and noise component, respectively. Again, strict incompatibility gives Bemp(A((5) S,) 2 Remp (A(0); S,) + S)S,1 (1/2 Sy Define the sample average empirical risk
1
VB =
Remp (Ao(S)):
(35)
B|S
13

---

Under review as a conference paper at ICLR 2022
computed from B samples the randomness in A. Then E[ 2 (1/2+ and by Hoeffding's inequality
Pr[VB < - Pr[[VB - (1/2 + 6) 8]
(36)
< 2 exxx(--26 B3)
(37)
Thus with probability at least 1 - exp(-202 primary component S; votes 0 when Sj is a noise component. By the same argument and using strict compatibility, the bound also holds for S, voting 1 when S; and Sj are both from primary components. Putting this together, we recall that sufficient condition for success of the algorithm occurs when all the primary components vote correctly on all components (both primary and noise), which happens with probability at least
[I 2 eex(( 2 B)
(38)
as claimed.
Proof of Proposition 5.1 The statement more or less a direct consequence of the alternating convex minimization strategy. Recall first that since and rj 0, Lines 4 and 6 in Algorithm 2 have no effect.
We prove the statement in two steps. First we claim that
F(0 vas Bc) S F(O,, U23 8c)
(39)
Note that i in the optimization objective F plays the role of S, in Algorithm 2 The inequality follows from the optimization on Line 5 in Algorithm [ which sets 0.+1 to the empirical risk minimizer of the set Uz.
Next, we claim that
F(O++1, u441 BB41) S F(04+1, B:)
(40)
Since 0 S I(..)) :) < the optimal size of the set St is |eel B.|S). Since 3r is decreasing, we have that |0++1| I |0.]. Thus the number of elements in the trimmed empirical loss is non-increasing (Line 7).
Combining the two inequalities shows that the objective function is decreasing in l. Since F(O,, ne B:) is a decreasing sequence bounded from below by zero, the monotone convergence theorem gives the second result.
14

---

Under review as a conference paper at ICLR 2022
B EXPERIMENTAL DETAILS
B.1 DEFENSE SET UP AND HYPERPARAMETERS
ISPL + Boosting (this work). For our defense, we use the same set of hyperparameters across all experiments. We run 8 rounds of ISPL, each of which returns component consisting of roughly 12% of the total samples. Let be the target percentage of samples over the remaining samples (i.e., p = 1/(88-111 i+ 1) in the 7th iteration). Then the number of iterations N is set to 2 + min(3, 1/p). / starts at 3 in the first iteration, then drops linearly to its final value of p over the next 2 iterations. When trimming the training set, we also additionally include the top p/8 samples per class to prevent the network from collapsing to a trivial solution. For the learning procedure A, we use standard SGD, trained for 4 epochs per iteration, with a warm-up in the first iteration of 8 epochs. The expansion factor is set to 1/4, and the momentum factor is set to 0.9.
We run ISPL times to generate 24 weak learners, Each weak learner is trained for 40 epochs on its respective subset. For the boosting framework, each component votes a per-sample basis. The sample is preserved if the modal vote equals the given label, with ties broken randomly.
We also include final self-training step by training a fresh model for 100 epochs the recovered samples. The main idea is that a model fit to the full "clean" training data can be used to test the excluded training data, thereby recovering additional consistent data which may have been originally excluded because the weak learners were fit to small subset of data for fewer epochs. However, may take several repetitions of training model from scratch before this self-training process no longer identifies new samples to recover. Therefore, we use a simple self-paced learning algorithm to single iteration. More
dynamically adjust the samples during training to limit the self self-traiming explicitly, we start with the "clean" samples as returned by the boosting framework. Every 5 epochs, we update the training set to be the samples whose labels agree with the model's current predictions. Due to the relative frequency with which we resample the training set, we smooth the predictions by a momentum factor of 0.8 so that the training process is less noisy. The samples used for training in the last epoch are returned as the defended dataset. In our experiments, this process decreases the false positive rate (and thus increases the clean accuracy) but does not materially affect the false negative rate (nor the targeted misclassification rate).
Spectral Signatures. We the official implementation of the Spectral Signatures defense (Tran) et al. 2018) by the authors, available on Github, except that we replace the training procedure with PyTorch (instead of Tensorflow 1.x as in the authors' original implementation). The authors suggest removing 1.5 times the maximum expected amount of poison from each class for the defense. We remove 20% of each class for c = 5, 10% and 30% of each class for c = 20%. In selecting the layer for the activations, for the ResNet32 architecture, we use the input to the third block of the third layer (which matches the authors' implementation), and for the PreActResNNt18 architecture, we use the input to the first block of the four layer (which was found empirically to remove the most poison on the first set of scenarios). We note that the authors indicate the defense should be fairly successful at any of the later layers of the network.
Iterative Trimmed Loss Minimization. The Iterative Trimmed Loss Minimization defense (Shen and Sanghavi (209)) consists of an iterative procedure. Given a setting 0 < a S 1, one first trains a model for a number of epochs. Then the a fraction of samples with the lowest loss are retained for the next iteration. This process is repeated several times, with a fresh model beginning each iteration. The defended dataset the a fraction of samples with the lowest loss after the last iteration. For the backdoor data poisoning experiments on CIFAR-10, 10, the authors use 80 epochs for the first round of training, then 40 epochs thereafter; they also set a = 98% for e = 5%, and do not test at other values of c. We use the same settings, and scale a linearly with i.e., a = 96% for = 10% and 92% for e = 20%.
Activation Clustering. The Activation Clustering defense (Chen et al., 2018) has an actively maintained official implementation in the Adversarial Robustness Toolbox (ART) (Nicolac et al. 2019). an open-source collection of tools for security in machine learning. We use the official implementation with the default parameters values in ART v1.6.2, the most current version at the
15

---

Under review as a conference paper at ICLR 2022
time of writing. In selecting the layer for the activations, used the same layer for Spectral Signatures.
Models. The &reActResNetl He al. (2016b) model is optimized using vanilla SGD with learning rate 0.02, momentum 0.9, and weight decay Sc-4. For the final dataset, we train for 200 epochs and drop the learning rate by 10 at epochs 100, 150, and 180. Using these parameters, we achieve 94.7% accuracy on CIFAR- 10 when trained and tested with clean data.
The ResNet32 He et al. (2016a) model is optimized using vanilla SGD with learning rate 0.1, momentum 0.9, and weight decay le-4. For the final dataset, we train for 200 epochs and drop the learning rate by 10 at epochs 100 and 150. Using these parameters, we achieve 91.8% accuracy on CIFAR-10 when trained and tested with clean data.
B.2 BACKDOOR POISON DATASET CONSTRUCTION
Each scenario has a single source and target class. We use the same (source, target) pairs as in Tran al. (2018:: (airplane, bird), (automobile, cat), (bird, dog), (cat, dog), (cat, horse), (horse, deer), (ship, frog), (truck, bird).
To generate perturbation, we choose shape (L-shape, X-shape, or pixel) uniformly at random. The (X,Y) coordinates of the perturbation are randomly selected to guarantee that the entire shape is visible before data augmentation (e.g.. the pixel-based perturbation can be placed anywhere within the 32x32 image, but the X-shape is larger and so must be centered in a 30x30 region, one pixel away from the border). The color of the perturbation also selected uniformly at random, with each of the (R,G.B) coordinates ranging from 0 to 255. Finally, we randomly select percentage of the source class, apply the perturbation by replacing the pixels in the corresponding locations with the selected shape and color, then relabel the poisoned images the target class.
5, 10, 20%
Table Sibleedisplay the generated triggers used in our experiments with examples of poisoned images. Within the row for each (source, target) pair, the first subrow gives the parameters for poison 1, the second subrow gives the parameters for poison 2, and the third subrow gives the paramcters for poison 3. We also provide example of the corresponding clean image for poison in column clean Note that the results presented in Table I of the main paper use the first scenario each (source, target) pair (poison 1).
16

---

Under review as a conference paper at ICLR 2022
Table 2: CIFAR-10 dirty label backdoor scenarios.
source
target
color
position
method
clean
poison
poison
poison 3
(103, 87, 79)
(24, 3)
pixel
/ Plane
2/ /ird
(92, 1, 189)
(27, 30)
pixel
(47, 21)
(21,
pixel
(180, 98, 53)
(10, 30)
pixel
Car
3// Cat
(40, 105, 92)
(25, 13)
pixel
(145, 70, 200)
(9)
pixel
(93, 86, 130)
(27, 9)
pixel
2/ Bird
5 D/
(156, 158, 244)
(18, 30)
pixel
(74, 162, 26)
(11, 9)
pixel
(34, 241, 240)
14)
Cat
D/
(239, 42, 58)
(28, 13)
pixel
(39, 221, 162)
(7,
(61, 14, 183)
(16,2)
Cat
7/ Horse
(180, 50, 21)
(11,0) 0)
pixel
(4, 221, 78)
(24, 22)
(107, 60, 58)
(15,4) 4)
pixel
7 / Horse
4/ Deer
(242, 30, 233)
(4,
(76, 14, 15)
(11, 19)
[141,245 211)
(4.
pixel
8/ Ship
6/ Frog
(213, 221, 138)
(19, 29)
(121, 158,
(3, pixel
(187, 67, 135)
(4, (7)
pixel
9 Truck
2/ Bird
(69, 204, 11)
(14, 29)
(239, 186, 219)
(1, 29)
17

---

Under review as a conference paper at ICLR 2022
Table 3: Performance on CIFAR-IO, dirty label backdoor scenario, using the PreActResNet188 architecture. The $ / column lists the CIFAR-10 source and target classes. refers to the percentage of the source class which is poisoned. For the remainder of the columns, the top level column headers give the defense type: L (clean), ND (no defense), SS (spectral signatures), AC (activation clustering), ITLM (iterative trimmed loss minimization, and TW (this work); the second level column headers give the metric type: M (misclassification rate), C (clean accuracy, higher is better), A (targeted misclassification rate, lower is better), FP (false positives, lower better), FN (false negatives, lower better). Please refer to the text for more detailed explanation of the table.
SS
AC
ITLM
TW
S/T
M
C
A
C
A
FP
FN
C
A
FP
FN
C
A
FP
FN
C
A
FP
FN
94.5
91.3
94.5
79.9
7381
130
91.9
58.3
18926
94.6
84.9
994
244
92.8
0.0
3640
23
0/2
1.3
94.1
90.6
94.5
66.0
7383
383
92.3
85.9
19790
94.2
92.8
1961
461
92.8
0.0
3479
20
1.1
80.2 94.6
94.2
64.2
14335
335
92.4
73.9
19127
601
93.8
93.8
3897
897
91.6
22.9
3711
237
94.4
92.9
94.7
5.5
7319
68
90.9
19.5
19791
155
94.8
96.5
986
236
92.8
3434
1/3
10
0.0
94.6
98.4
94.5
0.0
7035
35
92.5
68.7
19033
333
94.6
98.0
1981
481
93.0
0.0
3348
3
20
0.0
94.4
99.6
94.6
0.0
14007
7
92.2
91.8
18317
622
94.4
99.4
3914
914
93.0
0.0
3253
2
5
1.1
94.4
80.4
94.6
76.4
7494
243
92.4
53.9
19937
172
94.7
79.4
985
235
92.6
0.2
3704
5
2/5
10
0.9
94.4
97.2
94.4
0.1
7053
53
92.9
81.8
18657
313
94.7
92.4
990
490
92.9
0.2
3200
16
20
1.2
94.4
94.0
94.5
87.7
14263
263
92.6
89.4
20531
406
94.6
95.4
966
966
92.8
0.3
3540
38
5
7.6
94.7
91.0
94.7
88.5
7281
30
92.6
90.8
19172
172
94.5
91.4
993
243
92.8
81.1
3693
167
3/5
5.9
94.8
94.0
94.4
8.6
7014
14
92.3
91.6
20293
296
94.6
92.3
488
92.6
90.2
3355
496
20
7.6
94.7
90.8
94.3
90.6
14092
92
92.6
92.6 18236
652
94.7
91.7
974
974
92.6
87.4
3210
995
94.3
33.8
94.6
98.3
7500
249
97.2
21289
94.7
98.4
92.7
3692
3/7
10
0.7
94.4
98.5
94.6
96.6
7135
135
92.2
98.2
20630
484
94.5
98.6
1979
479
92.7
2.4
3427
22
20
0.7
94.4
98.5
93.7
78.5
14675
675
92.3
98.2
20470
987
94.4
98.9
980
980
92.9
10.5
3259
43
1.5
94.7
92.0
94.6
0.6
7280
29
92.3
39.2
19353
150
94.8
91.6
992
242
92.8
0.5
3258
30
7/4
10
1.5
94.6
94.7
94.4
0.0
7023
23
92.0
47.9
19631
285
94.4
94.5
1979
479
93.0
0.3
3627
293
20
1.5
94.6
96.5
0.1 94.3
14000
0
92.1
78.6
21292
22
94.4
96.5
3910
910
92.8
84.5
3203
867
5
0.2
94.7
97.0
94.8
80.5
7470
219
92.8
73.3
19293
152
94.5
98.3
993
243
92.8
0.0
3494
2
8/6
10
0.2
94.4
99.5
94.7
0.0
7008
8
92.6
97.6
19544
288
94.4
99.4
1981
481
92.9
0.0
3571
0.2
94.7
99.5
0.0 94.4
14000
0
92.5
96.4
18946
597
94.2
99.5
3908
908
92.6
0.2
3492
8
0.1
95.0
92.0
94.4
93.3
7501
250
91.7
85.0
23573
151
94.6
97.3
988
238
93.0
0.0
3291
2
9/2
94.5
93.9
94.3
93.1
7500
500
92.1
95.1
22896
251
94.4
98.6
1970
93.1
0.0
3133
20
0.1
94.4
96.1
94.7
0.0
14010
10
93.1
98.9
18651
575
94.1
99.0
3906
906
93.1
0.0
3223
2
C ADDITIONAL EXPERIMENTAL RESULTS
Tables and summarizes our main results for all the (source, target) pairs using two standard architectures for image classification: 8 He et al. (2016b) network and ResNet32 He et al. (2016a) network, respectively.
For each (source, target) pair, we generated three scenarios. For each (source, target) pair and setting of epsilon, we report results for the scenario in which the defense's targeted misclassification rate (column A) was the median all three scenarios. For the clean and no defense columns, we report results for the same scenario as TW (This Work).
The set of defenses consists of
1. (L) Clean, training the entire clean training set. We report only the misclassification rate (M), which is the number of poisoned samples from the test set of the source class that are misclassified as the target class.
2. (ND) No Defense, training entire poisoned training set. We report only the clean accuracy
(C) and targeted misclassification rate (A) in this case.
3. (SS) Spectral Signatures (Tran et al. 2018
4. (AC) Activation Clustering (Chen al. 2018
18

---

Under review as a conference paper at ICLR 2022
Table 4: Performance CIFAR-10, dirty label backdoor scenario, using the ResNet32 architecture. The / column lists the CIFAR-10 10 source and target classes. c refers to the percentage of the source class which is poisoned. For the remainder of the columns, the top level column headers give the defense type: L. (clean), ND (no defense), SS (spectral signatures), AC (activation clustering). ITLM (iterative trimmed loss minimization, and TW (this work); the second level column headers give the metric type: M (misclassificattion accuracy), C (clean accuracy, higher is better), A (targeted misclassification rate, lower better), FP (false positives, lower better), FN (false negatives, lower is better). Please refer to the text for more detailed explanation of the table.
ND
SS
AC
ITLM
TW
S/T
C
C
A
FP
FN
FP
FP
FP
FN
5
1.1
92.6
85.0
91.8
57.3
7499
248
88.8
0.6
24211
133
91.8
83.3
988
238
89.8
0.0
5752
31
0/2
92.4
92.6
91.7
91.5
7422
422
88.8
78.6
24031
250
91.7
92.3
1969
469
89.5
0.0
5445
92.5
94.9
90.4
64.2
14590
590
88.6
62.7
23686
455
91.9
94.2
3890
88.0
0.0
6992
92.7
98.5
91.7
5.7
7479
23903
91.9
12.7
89.8
5776
1/3
91.6
35.0
91.1
3.3
7436
436
88.3
24.9
23891
92.0
69.2
89.8
5736
20
0.0
92.1
98.1
91.5
0.0
14004
4
89.1
0.4
21145
70
91.9
97.3
3900
900
89.4
0.0
5833
1.7
92.2
62.7
91.2
43.2
7493
242
88.0
1.4
24001
128
92.2
75.7
994
244
88.8
0.1
6358
2/5
10
1.6
92.5
92.4
91.9
89.8
7476
476
89.3
81.5
23827
275
91.6
93.2
1975
475
89.2
0.0
5985
26
20
1.6
91.7
95.8
89.9
3.5
14349
349
88.5
87.2
21086
711
91.9
95.1
3905
905
89.8
0.2
5684
40
5
6.3
91.3
88.9
91.7
87.9
7466
215
88.9
80.0
23817
131
92.2
90.8
996
246
89.2
27.5
5974
59
3/5
10
6.2
91.8
90.8
91.6
86.4
7348
348
88.7
73.1
21299
136
92.2
89.5
990
490
89.1
82.1
5681
344
6.3
92.3
90.8
90.5
71.9
14090
90
89.3
78.5
20694
156
90.9
88.8
3918
918
89.8
86.7
5093
994
1.1
92.6
98.4
91.0
97.1
7452
201
86.2
72.8
23823
189
92.1
97.1 994
244
89.4
0.2
5498
13
3/7
92.4
98.6
91.8
96.7
7315
315
88.6
96.2
23648
482
92.3
98.0
89.8
5126
16
20
92.9
98.6
90.9
97.0
14167
167
89.1
95.4
20600
551
92.4
98.1 3924
924
88.6
0.2
6642
26
92.1
88.5
91.6
87.5
7486
235
72.2
23928
92.4
92.2
6643
7/4
1.7
92.7
93.9
91.9
94.2
7371
371
88.3
59.2
23753
193
92.1
96.2
1973
473
88.9
0.8
6478
32
20
1.7
92.6
96.9
91.1
94.1
14397
397
88.2
47.6
23737
423
91.7
95.8
3904
904
88.6
46.9
6322
209
0.2
92.7
98.0
91.3
97.8
7441
190
89.1
88.7
23658
164
92.5
96.9
988
238
89.6
0.0
5991
8 8/6
10
0.2
92.1
97.7
91.8
97.2
7089
89
90.2
95.1
19585
280
92.3
98.7
973
473
89.3
0.0
6007
20
0.2
92.8
98.8
91.3
96.0
14297
297
87.2
64.2
23347
646
92.3
98.6
975
975
89.4
0.0
5691
0.1
92.9
93.2
91.2
93.2
7478
225
88.7
1.2
23518
136
92.1
94.0
991
241
90.3
0.0
5444
2
9/2
10
0.1
92.6
98.6
91.4
94.7
7497
497
88.5
91.5
24034
242
92.5
97.8
986
486
88.1
0.0
7220
92.6
97.4
90.5
0.0
14011
90.6
97.7
18658
91.9
99.2
3881
5742
19

---

Under review as a conference paper at ICLR 2022
5. (ITLM) Iterative Trimmed Loss Minimization (Shen and Sanghavi 2019)
6. (TW) This Work
For each defense, we report
1. (C) clean accuracy, which is the accuracy of the defended network on the entire clean test set (higher is better).
2. (A) targeted misclassification rate as defined in Equation 7 which is measured over the entire source class of the test set (lower is better).
3. (FP) false positives, which counts the number of clean samples excluded from the defended training set (lower is better).
4. (FN) false negatives, which counts the number of poisoned samples included in the defended training set (lower better).
C.I DISCUSSION
Our approach consistently outperforms all other defenses by targeted misclassification rate (column A) across both architectures, If we define a "successful" run as achieving less than 1% targeted misclassification rate, then for the PreActResNet18 architecture, our defense succeeds in 17/24 scenarios, SS succeeds 9/24 scenarios, and both AC and ITLM do not succeed single time; for the ResNet32 architecture, our defense succeeds in 20/24 scenarios, SS succeeds in 2/24 scenarios, AC succeeds in 1/24 scenarios, and ITLM again fails all 24 scenarios.
In general, our defense results in 2-3% drop in clean accuracy for both architectures, when compared to model trained and tested using clean data. AC achieves clean accuracy which is on par with (or slightly below) ours. Surprisingly, this clean accuracy is despite AC having false positives (FP) of approximate 6x and 4x ours for the PreActResNet18 and ResNet32 models, respectively. Similarly, compared to our defense, SS has a slightly higher FP rate (which is roughly constant, as the defense always removes fixed amount of data), but suffers negligible drop in clean accuracy. We attribute this behavior to the existence of small, difficult to learn subpopulations (that may be removed by the weak learners as incompatible after training for only 40 epochs) but are responsible for the last 2-3% of performance. However, we note that our defense is designed to remove incompatible data, rather than poisoned data specifically, and therefore some such behavior is expected. Conversely. we hypothesize that SS and AC are removing "easy" data according to statistical properties of the activation patterns of trained network, which may constitute redundant data in terms of the training distribution. ITLM achieves good clean accuracy and the lowest number of false positives (though its performance is negligible in terms of defending against poison).
The only scenario which consistently evades our defense is the / (at, 5 Dog) scenario. This scenario is also the only one for which the poison misclassification rate of a clean network is noticeable large at around 6-8% (primary column L, secondary column M). which is consistent with the results in Tran et al. 2018). These results suggest that the scenario violates Property 4.4 i.c., the poison and clean distributions are not incompatible- performance on poisoned cats when mislabeled as dogs. Because the poisoned data is compatible with the clean data, our theoretical analysis suggests that our defense will struggle separate the clean and poisoned data, as is reflected in our results. Despite this, we note that the performance of our defense still exceeds that of the SS, AC, and ITLM defenses in several cases for this scenario.
on clean dataset yields neglneglee
Finally, to reconcile our results with the results presented in the Spectral Signatures paper, we note that the training code in official implementation of the SS defenses uses some non-standard methodologics, including a random crop with only 2x2 padding (instead of the 4x4 commonly used for CIFAR- 10); no normalization of the input data according to the mean and standard deviation; and custom initialization of all the layers (such as using a normal distribution to initialize the convolutional layers, rather than the default Kaiming initialization (He et al., 2015) in PoTrcch) The authors also only report results for cases where the network was "successfully poisoned"' which they defined as "approximately 90% or higher accuracy on the poisoned set" (corresponding to primary column ND, the first scenario of the first
secondary column A, in Tables 3 and 4). To verify results, (source, target) pair (i.e., the first row of Table through the authors' own implementation and found that at e 5%
20

---

Under review as a conference paper at ICLR 2022
undefended network had 71.9% poison misclassification rate;
the defense left 205 false negatives (out of 250 poisoned images);
trained on the defended dataset, the network had a 52.9% poison misclassification rate,
and at 10%
undefended network had 74.1 % poison misclassification rate;
the defense left 193 false negatives (out of 500 poisoned images);
trained on the defended dataset, the network had a 23.3% poison misclassification rate.
These results are not within the scope of the results considered in the original paper (due to not being over 90% poisoned pre-defense). In contrast, in our experiments, the pre-defense poison misclassification rate is much higher, which we attribute to more modern training methodologies.
21

---

Under review as a conference paper at ICLR 2022
Table 5: Ablation studies on CIFAR-IO, dirty label backdoor scenario, using the PreActResNet18 architecture, with various settings of a and 3. The S / column lists the CIFAR-10 source and target classes. c refers to the percentage of the souree class which is poisoned. The second level headings are C (clean accuracy, higher is better), A (targeted misclassification rate, lower is better). Please refer the text for more detailed explanation of table.
8 1/16
1/8 A
B
1/4
S/T
C
A
A
5
92.7
79.8
92.8
81.1
92.9
71.8
93.0
55.7
3/5
10
92.6
87.3
92.6
90.2
93.1
89.9
93.5
91.9
20
92.3
76.1
92.6
87.4
92.8
88.4
93.3
92.3
5
92.9
2.4
92.8
0.5
93.3
0.2
93.3
48.2
7/4
10
92.6
9.3
92.9
0.3
93.2
27.6
93.2
76.7
20
92.7
83.5
92.8
84.5
92.8
84.7
93.2
43.0
a 1/4
5
92.8
0.0
93.1
0.0
93.3
0.0
93.4
0.0
8/6
10
92.7
0.0
93.0
0.0
93.3
0.0
93.5
0.1
20
92.8
0.1
92.6
0.2
93.1
0.0
93.1
95.5
5
92.9
0.0
93.0
0.0
93.3
0.0
93.2
0.0
9/2
10
92.8
0.0
92.9
0.0
92.9
0.0
92.8
0.0
20
92.7
0.0
93.1
0.0
93.0
0.0
93.3
0.0
5
92.8
80.6
92.8
74.7
93.0
73.6
92.7
87.1
3/5
10
92.4
86.8
92.3
86.1
92.8
91.4
93.0
90.1
20
91.5
79.8
92.6
85.3
93.0
87.6
93.1
90.4
5
92.6
0.9
93.4
0.9
92.9
5.7
93.5
0.2
7/4
10
92.9
2.3
92.8
72.1
93.1
0.5
93.5
72.1
20
92.7
91.7
92.6
83.4
92.9
88.4
93.0
86.6
5
92.8
0.0
92.2
0.0
92.8
0.0
93.3
0.0
8/6
10
92.8
0.1
93.1
0.0
93.2
0.0
93.5
0.0
20
92.3
0.0
92.7
0.0
93.5
0.0
93.2
0.0
5
92.6
0.0
92.9
0.0
93.1
0.0
93.1
0.0
9
10
92.8
0.0
93.0
0.0
93.1
0.0
93.0
0.0
20
92.8
0.5
92.8
0.0
92.6
0.0
93.2
0.0
C.2 ABLATION STUDIES
We conduct some additional ablation studies to better understand the effects of the two main hyper- parameters in Algorithm 2 the expansion factor a and the subset size f3. Computationally. larger 3 means fewer components and fewer outer iterations of ISPL (and is thus more efficient); in our main experiments, we use 3 1/8 and run ISPL 8 times in sequence to generate components. Additionally, as discussed in Remark 2, smaller is more stringer requirement, since mixing distributions increases the expansion factor. Therefore we would expect that increasing a leads to worse identification of homogeneous components average.
Tables 5 presents the full results the ablation studies. Our main finding is that our method is quite robust to both the expansion factor and subset size B. There is also slight trend that smaller and are better at identifying poison, with a small drop in clean accuracy.
22


Reviews:
[{"review_id": "m_M8cibgg4G", "reviewer": "Reviewer_gSj9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n- The authors tackle a very relevant problem\n- The proposed solution is creative \n- There are strong theoretical motivations and modeling\n\nWeaknesses: \n- The empirical evaluation is only on one dataset (CIFAR-10) - I wonder whether this overall approach may include an unwanted smoothing of decision boundaries \n- Missing defenses (e.g., MNTD [2])\n- No adaptive adversary is considered [1]\n- Intuitions are not always clear before diving into the details; it would be useful also to draw a high-level pipeline of the proposed method for clarity\n\nComments:\n\nThe paper proposes an idea which is strongly formalized and thoroughly theoretically thought. \n\nI do have some concerns regarding the general efficacy of the approach:\n- **Missing adaptive adversary**: When proposing a new defense to adversarial attacks, it is fundamental to consider an attacker that knows which defense you are employing [1]. In the empirical evaluation, you only consider other proposed defenses, but do not consider a backdoor attack variant which knows you are looking for these homogeneous sets and then using the ensemble of weak learners. I feel you may be hence overestimating the effectiveness of your defense.\n- **Missing relevant defense**: At S&P21 it was recently proposed a new backdoor detection mechanism called MNTD [2], which has shown to be extremely effective in detecting backdoored models. I think the authors should also consider and compare against this other defense. But, more importantly, I feel their defense should be evaluated against an adaptive attacker as mentioned in the previous point.\n- **One dataset**. The empirical evaluation is conducted only on CIFAR-10. So I wonder if there is any bias in this. For example, does your approach involve a smoothing of the boundaries? What would happen if you use FMNIST or EMNIST? Would the clean model accuracy still hold? I have the suspicion that your approach may be implicitly increase the smoothing of the decision boundaries to improve generalization, and I wonder what effects this may have on a larger ecosystem. \n- **Intuitions and pipeline**. Although I strongly appreciate the heavy formalism of the paper, I also felt that having an overall bird-eye view of the pipeline would have helped in assessing its overall robustness. Hence, I feel that a diagram of two summarizing the intuitions behind the main phases of the proposed defense would greatly help the reader.\n- **Minor comments**. Some other minor comments\n\t- some citations are missing and are marked with \"(?)\", such as MNIST and CIFAR-10.\n\t- Possible typo right before equation 11: extra or missing parenthesis\n\n\nReferences:\n- [1] Carlini, Nicholas, et al. \"On evaluating adversarial robustness.\" arXiv preprint arXiv:1902.06705 (2019).\n- [2] Xu, Xiaojun, et al. \"Detecting AI trojans using meta neural analysis.\" 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021.", "summary_of_the_paper": "This paper proposes a new defense to backdoor attacks. In practice, it is an iterative training procedure which aims to remove poisoned data from the training set. This happens in two phases: an ensemble of weak learners identifies distinct homogeneous sub-populations in the training se, and a boosting framework aims to exclude poisoned data and recover clean data. They compare their approach with a few other defenses on CIFAR-10 and on dirty-label backdoor attacks.", "summary_of_the_review": "I feel the major shortcoming is the lack of an adaptive adversary, possibly overestimating the efficacy of the overall defense and giving a false sense of security. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "epNwpXOU1-A", "reviewer": "Reviewer_cvHA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n1. The idea of data partitioning, assessing then reassembling is generally new for adversarial defense.\n\n2. The proposed method seems more effective than prior work the Iterative Trimmed Loss Minimization (ITLM) of Shen and Sanghavi, 2019.\n\n3. Theoretical analyses are provided to justify the proposed approach.\n\n\nWeak points:\n\n1. The threat model adopted in this work needs more justifications. Backdoor attacks are no longer purely data poisoning anymore, there are quite a number of them are “model poisoning” attacks that follow a different setting. They follow different threat models in terms of who controls the training process. I understand this paper follows the more traditional data poisoning threat model, but it needs to be made very clear and contrasted to other backdoor defense threat models. \n\n\n2. Where the authors place their defense in the current literature is not clear. It appears to me that the proposed method is a robust training method, not a detection or backdoor removal method. The defense scope should also be discussed explicitly. The proposed method can only defense dirty-label backdoors with simple trigger patterns.\n\n3. Some of the assumptions are too strong, and their implications to backdoor attack/defense should also be explained. Property 4.4 (Incompatibility of primary and noise distributions), this assumption e most excludes most advanced backdoor attacks (trojan [1], dynamic input-aware [2], sample-wise [3], clean-label [4], feature-space attack, invisible attack, blending attack, reflection attack, and many others), and limits it to only simple attacks like BadNets. The authors can find many other examples in this GitHub repo: https://github.com/THUYimingLi/backdoor-learning-resources. Backdoor examples are *by design* compatible to clean data distribution, iconic characteristic of backdoor attacks to traditional data poisoning attacks. The tested BadNets is a classific dirty-label backdoor attack, which is very close to the traditional poisoning attacks but can no longer represent all backdoor attacks. \n\n4. Theorem 4.5 (Sets minimizing expansion error are homogeneous) is based on the strong assumption of incompatibility. I doubt it will hold for backdoor attacks, not just because of the incompatibility assumption, but also in general without knowing the poisoning rate.  The authors can prove me wrong with 40% poisoning but keeping the same number of samples. How to calculate the number of remaining/removed samples anyway?\n\n5. How does Algorithm 1 help is not well explained. The input has homogenous sets S_1-S_N, the return is their votes (based on their mean empirical error), is this to choose low-loss samples like in ITLM, Shen and Sanghavi, 2019. How does this differ from their strategy except using the ensemble (but in the full set case)? How the votes contribute to Algorithm 2?\n\n6. In Proof of Theorem 4.5, $S^{‘}=P^{‘} \\cup Q^{‘}$, why?\n\n7. What is the overall training procedure? How time-consuming it is compared to standard training. The training details given in the appendix show that the proposed method is complex, ad hoc, and hard to tune for other datasets, attacks, or poisoning rates.\n\n8. Confusing notations: $\\alpha-$expansion/compatibility, $\\beta$-compatibility, and the purposes of the samples determined by $\\alpha$ and $\\beta$ in Algorithm 2.\n\n9. The biggest concern about the experiment, except for missing many different types of attacks and datasets, is the cherry-picking results in the main text, Table 1. The complete results in appendix Table 3-5 indicate many failure cases on some of the source-target classes, for example, 3/5, 7/4, while the results in Table 1 only show the successful ones. So, based on the more complete results, the proposed defense does work at least on some source-traget class pairs. I doubt it will work on high poisoning rate or other types of advanced attacks like input-aware, sample-wise, clean labels attacks. \n\n10. Missing discussion of other defense methods: detection methods and backdoor removal methods. Can detection methods be directly applied to detect and remove the backdoor examples, if one can retrain the model on the purified data? Can backdoor trigger removal methods like Model be used or compared? What's wrong with the assumption of having a small set of clean samples, if the authors assume the defender has access to the full dataset and the dataset is less than 50% poisoned?\n\n11. The authors kept arguing that many existing defense works are not tested on CIFAR-10, why the authors didn’t test other datasets since many of them did? What makes the CIFAR-10 dataset so special? Transferability of the developed defense to large datasets? CIFAR-10 is not a good backdoor dataset is simply because its resolution is low, which is not an ideal place to design and test different types of trigger patterns, and even they work on CIFAR-10, they may not transfer to real-world scenarios which are surely not low resolution. \n\n---\n[1] Trojaning attack on neural networks, Liu et al.\n\n[2] Input-Aware Dynamic Backdoor Attack, NeurIPS, 2020.\n\n[3] Invisible Backdoor Attack with Sample-Specific Triggers, ICCV 2021. (maybe concurrent work)\n\n[4] Clean-Label Backdoor Attacks, Turner, Tsipras and Madry.\n\n[5] Bridging Mode Connectivity in Loss Landscapes and Adversarial Robustness, ICLR 2020.\n\n[6] Neural Attention Distillation: Erasing Backdoor Triggers from Deep Neural Networks, ICLR 2021.\n", "summary_of_the_paper": "This paper proposes an iterative data filtering/expanding approach with a set of weak learners for backdoor defense. The core idea is that clean distribution and backdoor distribution is incompatible and thus making them seperable based on the expanding error of the training set with many smaller subsets. The weak learners refer to the snapshots of the classifier trained on different subsets and expanded sets.  It is an iterative approach with multiple (8) rounds of  ISPL (Inverse Self-Paced Learnin) and 24 weak learners (each trained for 40 epochs). The entire process is also repeated for 3 times. Theoretical formulation and jusstificaiton have been given along with some empirical verfifiction.", "summary_of_the_review": "Good attempt, but the assumptions are too strong, making the entire theoretical analysis less convincing, problematic in several places, cherry-picked results,  missing many details about the overall training procedure, strategy for hyper-parameter choosing, missing experiments on many other attacks and datasets (only experiment with the simplest BadNets attack and CIFAR-10 datasets is given). Overall, I don't believe the proposed defense approach is good or simple enough to be useful in practice. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ShTigcNdPHH", "reviewer": "Reviewer_ey67", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. I like the description of self-expansion and compatibility in Section 4.1. It is very clear and properly motivates the idea of homogeneous set. The math proof of Theorem 4.5 makes sense to me (did not check every detail).\n2. A more challenging attack case (1 pixel trigger for CIFAR-10) is used in the experiments to validate the effectiveness of proposed defense. It significantly outperforms existing work without hurting clean accuracy too much.\n\nCons:\nI did not see obvious weakness of this paper. I am interested to see a running complexity comparison between previous proposed work. How does the number of ISPL runs affect the defense performance?\n\nTypos:\n1. Overview last paragraph: CIFAR-10 (?)\n2. Background and setting first paragraph: a loss function over Y X Y -> a loss function over X X Y", "summary_of_the_paper": "This paper tackles backdoor attacks where an adversary performs targeted attack against neural networks by injecting some poisoned data into the training data without sacrificing prediction accuracy on clean data. The defense works by recovering the clean data from poisoned training data. The authors proposed an Inverse Self-Paced Learning (ISPL) algorithm to first find a set of homogeneous sets (pure clear or poisoned data) and use an ensemble of weaker learners to exclude poisoned data from training set. ", "summary_of_the_review": "I will vote for accepting this paper. The idea of separating training set into self-expanding (homogeneous) sets is novel and interesting. The use of a set of weak learners and proposed boosting algorithm are technically sound. The experimental part demonstrates the performance of proposed defense over other existing work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "-LsqjqQClz2", "reviewer": "Reviewer_21eY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The goal of the paper is to provide a defense against backdoor attacks. They define backdoor attacks in a very specific way: We have a distribution $D$, and a \"backdoored\" version $D'$ that is, equal to $(1-p)\\cdot D+ p\\cdot backdoor(D)$ for some poisoning ratio $p$. And the $backdoor()$ function is a function that takes a labeled example $(x,y)$ and outputs $(x',y')$ where both $x'$ and $y'$ are deterministic functions of $x$ and $y$. The backdoor function should be chosen by adversary a priori. Then the success of the attack is measured by the accuracy of the resulting model on distribution $backdoor(D)$.\n\nAfter defining this threat model, they try to provide an outlier detection technique that when given a set $S$ sampled from $D'$ can separate the backdoored samples from benign samples. If I understand correctly, in the rest of paper, they try to find a way to solve this problem.\n\nThey define a notion of self-expansion of a set $S$ with respect to another set $T$, and with a ratio alpha. This notion is intuitively the expected empirical risk of a classifier trained on a dataset that is the union random subset of S with size $\\alpha|S|$ and $T$. And the empirical risk is calculated on the set $S$. This notion captures how well a random subset of S generalizes to the rest of the set, when combined with $T$.\n\nThen define the notion of $\\alpha$-compatibility of two sets $S$ and $T$ that is defined based on whether the self-expansion of set $S$ with respect to $T$ is smaller than without $S$ (compatible) or not (not compatible).\n\nFrom here on, they start making assumption that helps them to identify the outliers. The first assumption is that the self-expansion is a convex function of alpha, for both inliers and outliers. This assumption is extremely strong. The second assumption is about monotonicity of compatibility. That is, if $S$ and $T$ are $\\alpha$-compatible, then they should be $\\beta$-compatible too, for all $\\beta>\\alpha$. This assumption is again an strong assumption. \n\nThey also need some other assumptions that any subset of the outliers is incompatible with the incliners. This assumption is actually something that I think cannot hold in any setting and I mention that below in my comment to authors.\n\nThen using all these strong assumptions, the authors show that they can separate outliers from inliers using some tests for compatibility.  \n \n\n\nQuestions to Authors: \n\n1- To me, this paper is mostly about outlier detection. It is not clear to me why authors focus on backdoor poisoning attacks in the introduction as rest of the paper does not have anything to do with backdoor attacks. \n\n2- I have strong concerns about property 4.4. How can we strict and complete incompatibility? If you consider the empty set as a subset of T, then strict and complete incompatibility is not possible. \n\n3- What is the role of alpha of property 4.4 in the theorem 4.8?\n\n4-In general, there is a need for more discussion about why the assumptions are realistic and \"mild\" (as stated in the paper). In my opinion, these assumption are really strong. Also, the adversary can easily circumvent these assumptions. Why should we only consider adversaries that adhere to these assumptions?\n\n5-Why do you need to define multiple primary and multiple noise distributions? In my opinion this only makes the paper harder to understand. \n\n\n\nOther comments:\n\n-\"Clearly, given enough training samples S = {(x1, y1)...,(xn, yn)} iid from D, the empirical risk gets arbitrarily close to the population risk.\" This sentence is clearly wrong unless you assume something about your function class.\n\n-Theorem 4.5: \\{(\\alpha_i,\\mathcal{D}_i\\}-> \\{(\\alpha_i,\\mathcal{D}_i)\\}\n\n-Page 1 and 8: citation for CIFAR is missing\n\n-Page 3, eq 6: Why should \\pi be a  permutation? Could it be any mapping? Or does it even need to be a mapping between labels? Can't the adversary sometimes label a cat as a dog and sometimes label a cat as a frog?\n\n-Theorem 4.8: What is delta?\n\n-It's not clear how the learning objective is related to the threat mode.\n\n", "summary_of_the_paper": "This paper studies a defense against poisoning attacks using an outlier detection technique they develop using a notion of \"self-expanding\" sets. They assume a number of properties for inliers and outliers and can classify them so long as those properties are satisfied. They run experiments based on an existing backdoor attack and they show that their technique could be successful.  \n\n", "summary_of_the_review": "This paper try to provide a defense against backdoor attacks through outlier detection. I find the direction of providing provable guarantees for outlier detection is interesting. However, the assumptions in the paper are very strong which makes the threat model of the paper narrow. These assumptions are not just about the data distribution, rather, they are about the properties of the distribution generated by adversary that can be easily violated by adversary.\n\nI find the presentation of paper a bit confusing. The introduction talks about backdoor attacks but the technical parts of the paper has nothing to do with backdoor attacks.\n\nI also have concerns about some of technical steps of the proof that I mentioned in my comments. I also have a hard time understanding the main theorem that there seems to be an undefined term (delta). Also, I don't see any connection to alpha in alpha-compatibility, which is one of the assumptions of the theorem.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new defense against backdoor attacks based on the discovery of homogeneous populations in the training data and subsequent filtering of poisoned data due to its difference from the said populations. The method has a solid theoretical foundation which, however, requires strong assumptions on attacks and benign data. Due to these assumptions the theoretical guarantees alone cannot ensure that the defense is robust against adaptive attacks. The experimental validation of the proposed method is limited to one benchmark datasets (CIFAR), additional results are briefly presented in the response but not elaborated on.
Decision: Reject