DEFENDING AGAINST BACKDOOR ATTACKS USING ENSEMBLES OF WEAK LEARNERS
Year: 2021

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.

heading: 1 OVERVIEW
text: The past few years has seen the rapid adoption of deep learning in real world applications, from digital personal assistants to autonomous vehicles. This trend shows no sign of abating, given the remarkable (super)human performance of deep neural networks on tasks such as computer vision (He et al., 2016a), speed recognition (Graves et 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 a 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 a model to misclassify stop signs as 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 a dataset into a collection of homogeneous components (i.e., completely clean or completely poisoned subsets of the training data). Given such a 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
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 a novel, empirically verified method for defending against backdoor attacks.

heading: 2 RELATED WORK
text: 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; Singh 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 a (weak) learner as we do. Balcan et al. (2005) show that under a 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 we do not use an expansion property to leverage a 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 self-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. SPL and its variants have been observed to be resilient to noise both in theory (Meng et al., 2016) and practice (Jiang et 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 a 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 et al. (2018) propose a Spectral Signature defense that removes the data with the top eigenvalues, where is set to 1.5 times the amount of expected poison. TRIM (Jagielski et al., 2021) (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 a 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 as traffic signs or MNIST. Furthermore the triggers skew large and obvious (such as 3x3 patches (Qiao et al., 2019) or legible text overlays (Gao et al., 2019a)), and are often constrained to lie in the center of the image; our evaluation shows that existing defenses fail when evaluated on the more subtle triggers we use.

heading: 3 BACKGROUND AND SETTING
text: 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 ×Y . We assume a bounded loss function, which includes many commonly used loss functions such as the zero-one or cross entropy loss. Given a target distribution D supported on X × Y and a parametric family of functions fθ, the goal is to find the parameters θ that minimize the population risk R(θ) := ∫ X×Y L(fθ(x), y)dPD(x, y).
The learning problem (fθ,D) is realizable if (1) for every label y, the marginals D(·|y) have disjoint support; and (2) there exist ground truth parameters θ∗ with R(θ∗) = 0. For simplicity, we assume a (possibly stochastic) learning algorithm A that performs empirical risk minimization, i.e., given a set of samples T , A tries to return θ minimizing Remp(θ;T ) := ∑ i∈T L(fθ(xi), yi). Clearly, given
enough training samples S = {(x1, y1)..., (xn, yn)} iid from D, the empirical risk gets arbitrarily close to the population risk. We will identify the training set S with its indices [n].

heading: 3.1 DATA AND THREAT MODEL
text: We consider a mixture of n distributions {(αi,Di)}ni=1 such that D = ∪i{Di} and ∑ i αi = 1. We observe N inputs according to the following two-step procedure:
d ∼ Cat(α1, ..., αn) (1) x, y ∼ Dd (2)
where Cat(·) is a categorical random variable that returns i with probability αi. If S is a set of samples produced by this process, for any subset S′ ⊆ S, we will denote the samples drawn from the ith distribution as S′i, so that S
′ = ∪iS′i. Our evaluation focuses on 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 on clean data is otherwise unaffected, but an attacker can cause targeted misclassification during inference by overlaying a small trigger. In this case sampling from the training distribution is modeled as follows:
d ∼ Cat(α1, ..., αn) (3) x, y ∼ Dd (4)
p ∼ Bern(ρ) (5) x← τ(x), y ← π(y), if p (6)
where τ(·) is the function which applies a small trigger, π(·) 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 τ(Di) and target distributions Dπ(i) are disjoint for all i.
Given a model fθ(·), we measure the success of the attack using the targeted misclassification rate: Aemp(θ;T ) := ∑ i∈T [fθ(xi) = yi ∧ fθ(τ(xi)) = π(yi)] (7)
In other words, the attack succeeds if, during inference, it can flip the label of a correctly-classified instance by applying the trigger τ(·).

heading: 3.2 LEARNING OBJECTIVE
text: We formulate our learning objective in the general data model of Equations 1-2. Without loss of generality, we assume the first p distributions are primary distributions, and the remaining n− p are noise distributions. Given a training set S, we write SP = S1 ∪ ... ∪ Sp for the samples from the primary distributions, and SN = Sp+1 ∪ ... ∪ Sn for the samples from the noise distributions.
Our goal is to learn parameters θ̃ which correspond to training only on the primary distributions: θ̃ := A(SP ). 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 τ(Di) and Dπ(i), we expect that the hypothesis class fθ enjoys low targeted misclassification risk when trained only on clean data.

heading: 4 SEPARATION OF MIXED DISTRIBUTIONS
text: We next introduce the main theoretical properties that allow us to separate the primary and noise distributions. Our main tool is a property of “self-expanding” sets; intuitively, given a set, we
resample at a 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.e., drawn entirely from either the primary or noise components. Finally, we fit weak learners to the recovered (homogeneous) sets in a simplified boosting framework to identify the primary component.

heading: 4.1 SELF-EXPANSION AND COMPATIBILITY
text: We begin by stating a formal characterization of the self-expanding property of sets: Definition 4.1 (Self-expansion of sets.). Let S and T be sets. We define the α-expansion error of S given T for all 0 ≤ α ≤ 1 such that α|S| is integral as
(S|T ;α) := |S|−1E[Remp(A(S′ ∪ T );S)] (8) where the expectation is over both the randomness in A and S′, a random variable of α|S| samples drawn from S with replacement.
This self-expansion 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, a 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 (S;α) instead of (S|∅;α). α is also referred to as the subsampling rate. Finally, we will extend (S|T ;α) to all 0 ≤ α ≤ 1 by linearly interpolating between the value at integral sample sizes.
We now use self-expansion to define a notion of compatibility between sets: Definition 4.2 (Compatibility of sets.). A (nonempty) set T is α-compatible with set S with margin δ ≥ 0 if
(S|T ;α) + δ ≤ (S;α) (9) where the expectation is over the same random variables as in the definition of self-expansion. Furthermore, T is completely α-compatible with S if all (nonempty) subsets T ′ ⊆ T are α-compatible with S. Conversely, T is α-incompatible with S if the opposite holds, i.e.,
(S;α) + δ ≤ (S|T ;α) (10) (and similarly for complete incompatibility). We also say that strict compatibility (incompatibility) holds when δ > 0.
In other words, T is compatible with S if the self-expansion error of S 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 ;α) is a convex function of α ∈ [0, 1] such that (S|T ; 1) = 0 for all S, T (2) if T is α-incompatible with S, then T is β-incompatible with S for all β ≥ α.
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 T 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 on a noise distribution should not improve performance on a 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 D1 ∪ ... ∪Dp and Dp+1 ∪ ... ∪Dn, respectively, are strictly and completely α-incompatible.
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 are homogeneous.). Let S = S1 ∪ ... ∪ Sn be a set of samples drawn from a mixture of distributions {(αi,Di}ni=1. Define
S∗ := arg min S′⊆S (S′;α) (11)
for some expansion factor α. Then if Property 4.4 holds for α, we have either that S∗ ⊆ SP or S∗ ⊆ SN , where SP = S1 ∪ ... ∪ Sp and SN = Sp+1 ∪ ... ∪ Sn.
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 S1 ∪ ... ∪ Sp and the noise distribution Sp+1 ∪ ... ∪ Sn derive the homogeneity of S∗, a 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, a 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 a 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.
Remark 2 In general, the larger α is in Property 4.4, the easier it is to estimate the value of (S;α); the most convenient case would be for incompatibility to hold even when α = 1, in which case (S;α) can be evaluated exactly with one call to A. Unfortunately, for overparameterized models trained using empirical risk minimization, we have that (S; 1) = 0 for all S (since we assume the problem is realizable in the limit). One method to circumvent this problem is to prevent A from converging, e.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 our experiments, we find that combining early stopping with our self-expansion property leads to further improvements in performance.

heading: 4.2 IDENTIFICATION USING WEAK LEARNERS
text: The development of the previous section suggests an iterative approach to separating the primary and noise distributions. In particular, if we fix the expansion factor α, 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 to identify which components belong to the primary distribution.
We next propose a 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 to fit a weak learner to each component, then use each learner to vote on the other components.
Algorithm 1 presents our approach for boosting from homogeneous sets. The subroutine Loss0,1 takes a set of parameters and a 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 1 follows from an analogous compatibility property (cf. Property 4.4): Property 4.6 (Compatibility of primary distribution). Let α be given. Then any pair of (nonempty) sets Si and Sj drawn from Di and Dj , respectively, such that i, j ≤ n, are strictly and completely α-compatible.
Finally, we also require unbiased priors for weak learners:
Algorithm 1 Boosting Homogeneous Sets Input: Homogeneous sets S1, ..., SN , total number of samples n, number of estimates B, weak
learner A Output: Votes V1, ..., VN
1: C1, ..., CN ← 0 2: for i = 1 to N do 3: Vi1, ..., ViN ← 0 4: for j = 1 to B do 5: θij ← A(Si) 6: for k = 1 to N do 7: Vik ← Vik + Loss0,1(θij ;Sk)/B 8: end for 9: end for
10: for k = 1 to N do 11: if Vik > |Sk|/2 then 12: Ck ← Ck + |Si| 13: end if 14: end for 15: end for 16: for i = 1 to N do 17: Vi ← Ci > n/2 18: end for
Property 4.7 (Weak learners are unbiased.). Let Si be any sets. Then for any untrained weak learner, we have also that E[Remp(A(∅);Si)] = |Si|/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 of this section, whose proof is deferred to Appendix A. Theorem 4.8 (Identification of primary samples). Let S be a set of samples drawn from a mixture of distributions {(αi,Di}ni=1 such that Properties 4.4, 4.6, and 4.7 hold, and assume that the ratio of primary samples p = |SP |/|S| > 1/2. Let S1, ..., SN be a partition of S produced by iteratively applying Theorem 4.5. Then if A is deterministic, Algorithm 1 returns 1 with B = 1 for all components containing samples from the primary distribution, and 0 otherwise.

heading: If A is stochastic, the same result holds with probability
text: [1− 2 exp(−2δ2B)]MN (12)
where M is the number of primary components, and B is the number of independent weak learners used to fit each primary component.
Remark 3 At a high level, the approach to identifying the primary distribution presented in Theorems 4.5 and 4.8 follows a simplified boosting framework: at each step, we fit a weak learner to a 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 we 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 as using the empirical loss of the ensemble thus far, e.g., AdaBoost (Freund et al., 1996); in contrast, in 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 in our algorithm, we use each learner to vote over components of the training set to filter out the noise distributions. Finally, note that we can succeed with arbitrary probability by taking the number of samples B to infinity.

heading: 5 INVERSE SELF-PACED LEARNING
text: A major question raised by Theorem 4.5 is how to identify the set S∗ in its statement. In this section, we propose an algorithm called Inverse Self-Paced Learning (ISPL) to solve this problem. Rather
Algorithm 2 Inverse Self-Paced Learning Input: training set S, total iterations N , annealing schedule 1 ≥ β0 ≥ ... ≥ βN = βmin > 0,
expansion α ≤ 1, momentum η, incremental learning procedure A, initial parameters θ0 Output: SN ⊆ S such that |SN | = βN |S|
1: S0 ← S 2: L← 0 3: for t = 1 to N do 4: S′ ← Sample(St−1, α) 5: θt ← A(S′, θt−1) 6: L← ηL+ (1− η)Remp(θt;S) 7: St ← Trim(L, βt) 8: end for
than optimizing over all possible subsets of the training data, our objective will instead be to minimize the expansion error over subsets of fixed size β|S|. The optimization objective is defined as:
S∗β := arg min S′⊆S:|S′|=β|S| (S′;α) (13)
We attempt to solve for S∗β by alternating between optimizing parameters θt and the training subset St. More explicitly, given S′ we update θ using a single subset from S′ of size α−1|S′|. Then we use θ to compute the loss for each element in S, and set S′ to be the β fraction of the samples with the lowest losses. To encourage stability of the learning algorithm, the losses are smoothed with an optional momentum term η. We also anneal the parameter β from an initial value β0 down to the target value βmin 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 β|L| samples with the lowest loss. Finally, we show for certain parameters that Algorithm 2 converges on the following objective over the training set S:
F (θt, vt;βt) := ∑ i∈S vt[i]L(fθt(xi), yi) + cmax(0, βt|S| − |vt|) (14)
where vt is a 0-1 vector, βt is decreasing, and L(·, ·) ≤ c. Proposition 5.1. Let α = 1 and η = 0 in the setting of Algorithm 2, and assume that A returns the empirical risk minimizer. Then we have that for each round of the algorithm, F (θt, vt;βt) is decreasing in t and furthermore, |F (θt, vt;βt)− F (θt+1, vt+1;βt+1)| t→∞−−−→ 0.
We defer the proof of Proposition 5.1 to Appendix A.
Remark 4 When α = 1 and η = 0, we recover vanilla self-paced learning (SPL) with two major differences. First, we start on the full set of samples and train on incrementally smaller sets, while SPL starts with a small set of samples and trains on larger sets. This discrepancy is due to the differing objectives; whereas SPL is a heuristic for converging faster to a global minimizer of the population loss by training first on easy samples, ISPL attempts to converge to a local minimum over a 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 the 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 a smaller impact on the final performance.

heading: 6 EXPERIMENTAL EVALUATION
text: We evaluate our defense against the standard patch-based backdoor attack with dirty labels, where the adversary inserts a small patch into a training image from the source class, then changes the label
of the image to the target class. The goal is to induce the learner to misclassify images from the source class as the target class upon application of the patch. Results in this section use a standard PreActResNet18 architecture (He et al., 2016b) that achieves 94% accuracy on CIFAR-10 when trained on a clean dataset. The appendix provides full experimental details and additional results.

heading: 6.1 RESULTS
text: Our implementation of the dirty label backdoor adversary follows the threat model described in Gu et al. (2017). The perturbation function τ simply overlays a 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 1.
Table 1 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 in the form (X,Y) where X,Y is the position of the single pixel trigger. The third column, , presents the percentage of the source class in the training set that is poisoned by the adversary.
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) (Chen et al., 2018), and 4) Iterative Trimmed Loss Minimization (ITLM) (Shen and Sanghavi, 2019). 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 misclassification rate (Equation 7) over patched images of the target class in the test set (column A, lower is better, minimum is 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 A ranges from 0.0% to 1.3%) at the cost of 2) a 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).

heading: 6.2 DISCUSSION
text: 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., 2013) or LISA (Mogelmose et al., 2012)) and MNIST (?). Furthermore, these datasets are tested in conjunction with larger or otherwise more obvious triggers. For instance, the Neural Cleanse (Wang et al., 2019) defense uses a 4x4 white box as the trigger on the MNIST and GTSRB datasets; MESA (Qiao et al., 2019) uses a 3x3 image as the trigger on CIFAR-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., 2019b) uses an 8x8 box on CIFAR-10. Our hypothesis is that the combination of a smaller trigger and more complex classes breaks defenses that demonstrate good performance in simpler contexts. Table 1 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 et 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 = 5% using larger L- and X-shaped triggers. Our results in Table 1 indicate 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 is 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 of 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 1, 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.

heading: 7 CONCLUSION
text: 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 experiments 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-expanding sets successfully removes the poisoned data. Empirically, our method is resilient to a strong version of the dirty label backdoor attack introduced by Gu et al. (2017), which successfully evades all the baseline defenses. We believe our analysis and techniques present a valuable addition to the toolbox for secure deep learning.

heading: A DEFERRED PROOFS
text: Lemma A.1. Let SN and SP be two sets satisfying Property 4.4, and let S and T be drawn from SN and SP , respectively. Then for all 0 < γ ≤ α, S and T are mutually strictly γ-incompatible.
Proof. We will show that T is γ-incompatible with S for all γ ≤ α; mutual incompatibility follows by a symmetric argument. First, T is α-incompatible with S by consequence of Property 4.4. Fix γ < α. Our main approach will be to subsample S twice: first, we sample S at a rate of γ/α to create S′ such that |S′| ≈ γ/α|S|. Then S′ is α-incompatible with T , so (S′|T, α) ≥ (S′, α). However we need take some care to ensure γ/α|S| is an integer. Define
α′ := γ|S|
bγ|S|/αc (15)
Then α′ ≥ α and γ/α′|S| = bγ|S|/αc. Thus, we will subsample S at a rate of γ/α′ to create S′; by Assumption 4.3, T is α′-incompatible with S′. Note that the resulting training sets produced by this double subsampling procedure have size γ|S| as desired. Next, we will show that there exists some constant c such that
(S|T, γ) = c(γ/α′|S|)−1E[ (S′|T, α′)] (16) (S, γ) = c(γ/α′|S|)−1E[ (S′, α′)] (17)
where the expectations are taken over the subset S′ ⊂ S, |S′| = γ/α′|S|. Then since T is strictly α′-incompatible with all such S′ by Property 4.4,
(S|T, γ) = c|S′|−1E[ (S′|T, α′)] (18) > c|S′|−1E[ (S′, α′)] (19) = (S, γ) (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(A(S′′ ∪ T );S′′) = 0 for all T ′. Then conditioning on the training set S′′, we have that
E[ (S′|T, α′)|S′′] = E[Remp(A(S′′ ∪ T );S′)|S′′] (21) = E[Remp(A(S′′ ∪ T );S′ − S′′)|S′′] (22)
where the expectation is over S′ such that S′′ ⊂ S′. Now S′ − S′′ is a random variable consisting of |S′| − |S′′| independent draws from S with replacement; thus Equation 22 is just equal to |S′| − |S′′| times the empirical risk of a random element in S. On the other hand, Remp(A(S′′ ∪ T );S) is the empirical risk over all elements in S, or equivalently, |S| times the empirical risk of a random element.
Since T was arbitrary, summing over all possible training sets S′′ yields the desired identities with
c = |S|
|S′| − |S′′| . (23)
Proof of Theorem 4.5. We first prove a slightly more general result. Assume by way of contradiction that there exists a partition of S∗ into two nonempty sets P and Q that are mutually strictly incompatible.
Let ∗ be the expansion error of S∗. Recall that this means
|S∗| ∗ = |S∗| (S∗;α) = E[Remp(A(S′);S∗)] (24)
where the expectation is taken over samples S′ of size α−1|S∗| drawn from S∗ with replacement. Since the empirical risk is a linear function of S∗, we can decompose this last term as
E[Remp(A(S′);S∗)] = E[Remp(A(S′);P )] + E[Remp(A(S′);Q)] (25)
Given a set of training samples S′, we will denote the elements drawn from P and Q as P ′ = S′ ∩ P and Q′ = S′ ∩Q, respectively. Now consider the term
E[Remp(A(S′);P )] = E[Remp(A(P ′ ∪Q′);P )] (26) If we fix Q′, then P ′ is drawn uniformly at random from P with replacement, where |P ′| = α|S∗| − |Q′|. Define
αQ′ := α|S∗| − |Q′| |P |
(27)
which is the subsampling rate of P ′ given Q′. Note that if α′ ≥ α, then Q′ is α′-incompatible with P ′ by Assumption 4.3, and otherwise α′ < α and Q′ is strictly α′-incompatible with P ′ by Lemma A.1. Thus,
E[Remp(A(P ′ ∪Q′);P )] = ∑ Q′ Pr[Q′]E[Remp(A(P ′ ∪Q′);P )|Q′] (28)
= |P | ∑ Q′ Pr[Q′] (P |Q′;αQ′) (29)
> |P | ∑ Q′ Pr[Q′] (P ;αQ′) (30)
On the other hand, E[αQ′ ] = α, and since (P ;α) is convex in α by Assumption 4.3, we can apply Jensen’s inequality to conclude ∑
Q′
Pr[Q′] (P ;αQ′) ≥ (P ;α), (31)
i.e.,
E[Remp(A(P ′ ∪Q′);P )] > |P | (P ;α). (32) Similarly,
E[Remp(A(P ′ ∪Q′);Q)] > |Q| (Q;α). (33) Combining these two results yields
|S∗| ∗ > |P | (P ;α) + |Q| (Q;α). (34) Since |P |+ |Q| = |S∗|, we have that at least one of (P ;α) or (Q;α) must be less than ∗, which contradicts the optimality of S∗. Thus one of P or Q must be empty.
Finally, we note that by Property 4.4, the partition P = S∗ ∩ SP and Q = S∗ ∩ SN gives an 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 S \ S′ for any set S′. Thus we are able to apply Theorem 4.5 at each step and so in fact S1, ..., SN are all homogeneous. Additionally, since p > 1/2 and a component’s vote is weighted by its size, a sufficient condition for success is when all the primary components vote correctly.
We start with the case when A is deterministic. Let Si and Sj be a primary component and noise component, respectively. By strict incompatibility, we have that Remp(A(Si);Sj) > Remp(A(∅);Sj) = |Sj |/2. Thus Si votes 0 on Sj . Conversely, if Sj is a primary component, then Remp(A(Si);Sj) < Remp(A(∅);Sj) = |Sj |/2, so Si votes 1 on Sj . Putting these together and using the fact that p > 1/2, we find that the noise components have weighted vote strictly less than |S|/2, while the primary components have weighted vote strictly greater than |S|/2, as required. 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 Si and Sj be a primary and noise component, respectively. Again, strict incompatibility gives Remp(A(Si);Sj) ≥ Remp(A(∅);Sj) + δ|Sj | = (1/2 + δ)|Sj |. Define the sample average empirical risk
VB := 1
B|Sj | B∑ b=1 Remp(Ab(Si);Sj) (35)
computed fromB samples over the randomness inA. Then E[VB ] ≥ (1/2+δ) and so by Hoeffding’s inequality
Pr[|VB < 1/2] ≤ Pr[|VB − (1/2 + δ)| > δ] (36) < 2 exp(−2δ2B) (37)
Thus with probability at least 1− 2 exp(−2δ2B), primary component Si votes 0 when Sj is a noise component. By the same argument and using strict compatibility, the bound also holds for Si voting 1 when Si and Sj are both from primary components. Putting this together, we recall that a 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
[1− 2 exp(−2δ2B)]MN (38)
as claimed.
Proof of Proposition 5.1. The statement is more or less a direct consequence of the alternating convex minimization strategy. Recall first that since α = 1 and η = 0, Lines 4 and 6 in Algorithm 2 have no effect.
We prove the statement in two steps. First we claim that
F (θt+1, vt;βt) ≤ F (θt, vt;βt) (39)
Note that vt in the optimization objective F plays the role of St in Algorithm 2. The inequality follows from the optimization on Line 5 in Algorithm 2, which sets θt+1 to the empirical risk minimizer of the set vt.
Next, we claim that
F (θt+1, vt+1;βt+1) ≤ F (θt+1, vt;βt) (40)
Since 0 ≤ L(·, ·) < c, the optimal size of the set St is |vt| = βt|S|. Since βt is decreasing, we have that |vt+1| ≤ |vt|. 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 t. Since F (θt, vt;βt) is a decreasing sequence bounded from below by zero, the monotone convergence theorem gives the second result.

heading: B EXPERIMENTAL DETAILS
text: 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 a component consisting of roughly 12% of the total samples. Let p be the target percentage of samples over the remaining samples (i.e., p ≈ 1/(8− i+ 1) in the ith iteration). Then the number of iterations N is set to 2 +min(3, 1/p). β starts at 3 ∗ p 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 3 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 on a per-sample basis. The sample is preserved if the modal vote equals the given label, with ties broken randomly.
We also include a final self-training step by training a fresh model for 100 epochs on 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 a small subset of data for fewer epochs. However, it may take several repetitions of training a 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 dynamically adjust the samples during training to limit the self-training to a single iteration. More 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 use 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 = 5, 10% and 30% of each class for = 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 PreActResNet18 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, 2019) consists of an iterative procedure. Given a setting 0 < α ≤ 1, one first trains a model for a number of epochs. Then the α 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 is the α fraction of samples with the lowest loss after the last iteration. For the backdoor data poisoning experiments on CIFAR-10, the authors use 80 epochs for the first round of training, then 40 epochs thereafter; they also set α = 98% for = 5%, and do not test at other values of . We use the same settings, and scale α linearly with , i.e., α = 96% for = 10% and α = 92% for = 20%.
Activation Clustering. The Activation Clustering defense (Chen et al., 2018) has an actively maintained official implementation in the Adversarial Robustness Toolbox (ART) (Nicolae 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
time of writing. In selecting the layer for the activations, we used the same layer as for Spectral Signatures.
Models. The PreActResNet18 He et al. (2016b) model is optimized using vanilla SGD with learning rate 0.02, momentum 0.9, and weight decay 5e-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 1e-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 et al. (2018): (airplane, bird), (automobile, cat), (bird, dog), (cat, dog), (cat, horse), (horse, deer), (ship, frog), (truck, bird).
To generate a perturbation, we choose a 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 is also selected uniformly at random, with each of the (R,G,B) coordinates ranging from 0 to 255. Finally, we randomly select an = 5, 10, 20% 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 as the target class.
Table 2 displays 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 parameters for poison 3. We also provide an example of the corresponding clean image for poison 1 in column clean 1. Note that the results presented in Table 1 of the main paper use the first scenario of each (source, target) pair (poison 1).

heading: C ADDITIONAL EXPERIMENTAL RESULTS
text: Tables 3 and 4 summarizes our main results for all the (source, target) pairs using two standard architectures for image classification: a PreActResNet18 He et al. (2016b) network and a 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 of 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 on 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 on 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 et al., 2018)
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 is better).
C.1 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 a 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 a 2-3% drop in clean accuracy for both architectures, when compared to a model trained and tested using clean data. AC achieves a 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 a fixed amount of data), but suffers a 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 a 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 (3 / Cat, 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.e., the poison and clean distributions are not incompatible—training on a clean dataset yields non-negligible 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 to 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.
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 methodologies, 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 PyTorch). 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, secondary column A, in Tables 3 and 4). To verify our results, we ran the first scenario of the first (source, target) pair (i.e., the first row of Table 2) through the authors’ own implementation and found that at = 5%
– an undefended network had a 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%
– an undefended network had a 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.
C.2 ABLATION STUDIES
We conduct some additional ablation studies to better understand the effects of the two main hyperparameters in Algorithm 2: the expansion factor α and the subset size β. Computationally, larger β means fewer components and fewer outer iterations of ISPL (and is thus more efficient); in our main experiments, we use β = 1/8 and run ISPL 8 times in sequence to generate 8 components. Additionally, as discussed in Remark 2, smaller α is a more stringer requirement, since mixing distributions increases the expansion factor. Therefore we would expect that increasing α leads to worse identification of homogeneous components on average.
Tables 5 presents the full results of the ablation studies. Our main finding is that our method is quite robust to both the expansion factor α and subset size β. There is also a slight trend that smaller α and β are better at identifying poison, with a small drop in clean accuracy.

Review summaries:
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.    

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. 

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.

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.