SPECTRE: Defending Against Backdoor Attacks Using Robust Statistics

Introduction

Large scale machine learning, such as federated learning (Kairouz et al. 2019), requires training data collected from multiple sources. As not all sources can be trusted and sanity checking the data is expensive, this opens an opportunity for an adversary to inject poisoned data into the training set. A particularly concerning scenario is the backdoor attack; the attacker attempts to embed a hidden backdoor to the trained model such that its prediction is maliciously changed when activated by samples with an attacker-defined trigger. As the model behavior on clean data is unchanged, such backdoored models may be deployed unnoticed.

Recently, Tran et al. 2018 proposed, what we call, the PCA defense using the representations at the intermediate layers of such neural networks trained on a corrupted dataset. It is based on the observation that poisoned examples have special spectral signatures that can be used to filter them out. Concretely, given the intermediate representations $\{\bm{h}_{i}\}_{i=1}^{n}$ of all the training data, each sample is assigned an outlier score $\tau_{i}=|\langle\bm{h}_{i},\bm{v}_{h}\rangle|$, which is its magnitude in the top PCA direction $\bm{v}_{h}$ of the representations. Those with high scores are removed from the training data, and a fresh model is trained on the filtered data.

Contributions. We introduce SPECTRE (Spectral Poison ExCision Through Robust Estimation), a novel defense for general backdoor attacks. The key insight, illustrated in Fig. 2, is that we can significantly amplify the spectral signature of the poisoned data by (i) estimating the mean and the covariance of the clean data using robust statistical estimators and (ii) whitening the combined data with the estimated statistics. The resulting top PCA directions are well-aligned with the subspace that separates the poisoned samples from the clean ones (illustrated in Fig. 2). However, detecting those poisoned examples can still be challenging as the distribution of the (whitened) representations can vary widely depending on the types and strengths of the attacks. To adapt to such profile of the representations, we propose a variation of recently introduced QUantum Entropy (QUE) outlier scoring. We show in Section 4 that SPECTRE is able to eliminating the backdoor (e.g., shown in green squares in Fig. 1) under a broad range of attacks, significantly improving upon the state-of-the-art baselines. We show that every component of SPECTRE is crucial in achieving this performance gain with ablation study in Section 5.

We focus on training-time attacks and refer readers to (Madry et al. 2017; Ilyas et al. 2019) for survey on inference-time attacks.

Data poisoning attacks and defenses. Data poisoning refers to attacks that insert poisoned examples into the training data. There are two types depending on the goal: reducing model quality or creating a backdoor. Model quality attacks have been studied in feature selection (Xiao et al. 2015), PCA (Rubinstein et al. 2009), neural networks (Yang et al. 2017), general models (Mozaffari-Kermani et al. 2014), and general function classes (Kearns & Li 1993). These attacks have been successfully launched in deployed systems, as shown in (Newsome et al. 2006; Laskov 2014; Biggio et al. 2014; Wang et al. 2020b).

Defenses against backdoor attacks. As the defender is not assumed to have clean validation data, several approaches do not apply to our setting. Defenses using outlier detection require clean validation data (Liang et al. 2017; Lee et al. 2018; Steinhardt et al. 2017; Turner et al. 2019). (Liu et al. 2018) requires clean data to retrain a poisoned model to make it forget the backdoor. (Kolouri et al. 2020) requires a model trained on clean data to design a litmus test that detects poisoned models.

Some other defenses (Wang et al. 2019; Awasthi et al. 2020; Wang et al. 2020a; Weber et al. 2020; Chou et al. 2018) rely on triggers having a small norm, and are known to fail on attacks with large perturbations. Neural Cleanse (Wang et al. 2019) finds perturbations that change the label of a training sample. The smallest such perturbation is declared as the trigger. Randomized smoothing proposed in (Wang et al. 2020a; Weber et al. 2020) ensures that all bounded perturbations are consistently labelled, forcing clean image and its poisoned version to have the same label.

SentiNet (Chou et al. 2018) uses saliency maps to detect triggers corresponding to small connected regions of high salience over multiple images. Other types of defenses protect against model quality attacks, including outlier detection without clean data (Sun et al. 2019; Steinhardt et al. 2017; Blanchard et al. 2017; Pillutla et al. 2019) and Byzantine-tolerant distributed learning approaches (Blanchard et al. 2017; Alistarh et al. 2018; Chen et al. 2018b).

Threat model and diversifying the attacks

We assume the threat model of (Tran et al. 2018). The adversary has the training data and knows the user’s neural architecture and training method. However, the adversary does not train the model herself. The user trains the model on training data that might be corrupted by the adversary, whose goal is to create a backdoor in the user’s trained model. The purpose of a backdoor is twofold. First, in order to avoid suspicion, the classification accuracy on the clean training data and clean test data should not decrease due to the presence of poisoned data (hence the name backdoor). Second, when a clean test data (whose label is not the target label) is corrupted by an attacker-defined trigger, the backdoor should be activated and the example should be classified as the attacker-defined target label.

To create a backdoor, the adversary injects poisoned data in the training set. We test our defense against the pixel attack, periodic attack, and clean label attack. We vary the fraction of injected poisoned examples denoted by

2 Pixel attacks and mm-way pixel attacks

Algorithm

The pipeline of our approach is to train a model and extract a representation from a middle layer, then identify the target label with Algorithm 4, detect and remove the poisoned examples with Algorithm 1, and retrain (see Fig. 4). In this section, we assume that the representations have been extracted and the target label has been correctly identified and focus on the robust poison detector. We refer to Section 4.5 for the details on identifying the target label.

We propose the following three steps in SPECTRE (Algorithm 1). We first project the given representation data down to a $k$-dimensional space using its top left singular vectors. We next apply robust estimation to get the approximate mean and covariance of the clean data. After whitening the data with the estimated mean and covariance, the spectral signature of the poisoned data is amplified such that it can be detected more effectively. Finally, we use QUantum Entropy (QUE) scores to find those with strong spectral signatures. Note that the sensitivity of the algorithm is tuned by the choice of removing $1.5\varepsilon n$ suspicious samples, following the same choice from (Tran et al. 2018). We show that the performance is not sensitive to this choice in Appendix H.

2 Step 2: Robust estimation

The PCA defense fails when the direction the algorithm checks (which is the top PCA direction of the combined data) is not aligned with the spectral signature of the poisoned examples (which is the direction that separates poisoned from clean data). This happens when the covariance of the clean data has a large condition number such that the variance along the spectral signature direction is much smaller than the variance along the top PCA direction, as shown in Figs. 5 and 2. In real data, the spectral signature commonly hides in such low-variance directions, causing PCA Defense to fail under most of the attacks we tested.

If we know the true mean and covariance of the clean data, we can whiten the combined data to ensure that the clean data has the same variance along the spectral signature direction as any other directions, thus amplifying the hidden spectral signature. We propose using the recently introduced robust mean and covariance estimator, which is guaranteed to accurately estimate the true mean and covariance when we have enough samples from a Gaussian distribution.

Let $G\sim\mathcal{N}\lparen\bm{\mu},\Sigma\rparen$ be a Gaussian in $d$ dimensions, and let $\varepsilon>0$. Let $S$ be an $\varepsilon$-corrupted set of samples from $G$ of size $\Omega\lparen\lparen d^{2}/\varepsilon^{2}\rparen\operatorname{poly~log}\lparen d/\varepsilon\rparen\rparen$. RobustEst($S$, $\varepsilon$), returns $\widehat{\Sigma}$ and $\widehat{\bm{\mu}}$, so that with probability at least $9/10$, it holds that $\|{\bm{I}}-\Sigma^{-1/2}\widehat{\Sigma}\Sigma^{-1/2}\|_{F}=O\lparen\varepsilon\log\lparen 1/\varepsilon\rparen\rparen$ and $\|\bm{\mu}^{\prime}-\bm{\mu}\|_{2}=O\lparen\varepsilon\sqrt{\log\lparen 1/\varepsilon\rparen}\rparen$.

Under the assumption that the clean data is drawn from a Gaussian distribution, this provides the best known guarantee for joint mean and covariance estimation and also matches the known fundamental limit on the achievable accuracy up to a logarithmic factor. However, in practice, we do not have enough samples to do robust estimation of the $d=$4true096$$dimensional covariance in real data with CIFAR-10, where each label has$5true000$samples. It is critical to use an appropriate choice of$k$in reducing the dimensionality of the samples down to$k$in the pre-processing. In fact, a moderate choice of$k=60$can completely fail as we illustrate in Fig. 8. To this end, we propose Algorithm 3 to identify the dimensionality$k$. For completeness we also provide RobustEst from (Diakonikolas et al. 2017a) in Algorithm 13 in Appendix D.

3 Step 3: Quantum entropy score poison detection

The name quantum entropy scoring comes from the fact that the matrix exponential $Q_{\alpha}/\trace\lparen Q_{\alpha}\rparen$ is a solution of a particular linear maximization with a quantum entropy regularization. This matrix weighs the top and bottom principal directions differently, and the choice of $\alpha$ controls how aggressively we want to emphasize the top principal directions. This allows the QUE score to naturally adapt to the effective dimensionality of the spectral signature in poisoned samples. The squared norm $\tau_{i}^{(0)}$ fails when this effective dimension is small, which happens when the signature is weak, i.e. large $m$ and small $\varepsilon$. The squared projected norm $\tau_{i}^{(\infty)}$ fails when the effective dimension is large, which happens when the signature is strong, i.e., small $m$ and large $\varepsilon$. The experiments support this intuition and we provide details in Appendix G. The performance of the score is not sensitive to the choice of $\alpha$ and we set it to $4$ for all our experiments. QUE score plays critical roles also in identifying the target label (Algorithm 4) and also in selecting the dimensionality $k$ (Algorithm 3).

4 Possible extensions to SPECTRE

In the dimensionality reduction step, we could have used robust principal component analysis (Kong et al. 2020; Jambulapati et al. 2020) to replace $U$ with the estimated principal subspace of the clean data. Further, theoretically, we should partition the data into two groups $S_{1}\cup S_{2}=S$, and project the data from one group onto the subspace learned from the SVD of the other group. This ensures that the learned subspace does not overfit the data. In practice, these two variations did not give any improvement in performance.

Experiments

In our pipeline (Fig. 4) for removing poison and retraining, we replace our proposed SPECTRE with two competing state-of-the-art approaches and compare the resulting performances. Following (Tran et al. 2018), in all experiments, we set the sensitivity so that $1.5\varepsilon n$ data points are removed in total, we use “deer” as the target label, and use images of trucks to create poisoned samples (unless otherwise stated). In all experiments shown in this section, we use Algorithm 3 (explained in Section 4.4) to find the effective dimension $k$ adaptively and automatically, and use Algorithm 4 (explained in Section 4.5) to identify the target label. Due to space constraints, we only report the attack accuracy on the backdoored test examples on the final re-trained model. The accuracy on the clean test examples is always between $92.5\%$ and $93.5\%$ unless otherwise stated, and is omitted from the results. Complete statistics of the poison removal process are provided in Appendix B.

We compare three defenses: the proposed Algorithm 1, the PCA defense of (Tran et al. 2018) and the Clustering defense of (Chen et al. 2018a). The Clustering defense uses standard $2$-means on the representations and we allow access to the oracle to determine one cluster and randomly select $1.5\varepsilon n$ data points to remove from that cluster. Detailed descriptions are provided in Appendix A. We evaluate them on three popular families of backdoor attacks.

We test the defenses on the $m$-way pixel attacks described in Section 2.2 with examples shown in Fig. 3. Following the experiments of (Tran et al. 2018), we use a poisoned CIFAR-10 dataset to train a 32-layer ResNet We modified the implementation at https://github.com/akamaster/pytorch_resnet_cifar10 to match that used in (Tran et al. 2018). model composed of three groups of residual blocks with 16, 32, and 64 filters respectively and 5 residual blocks per group. Details of the training are provided in Appendix E. A complete table of all the results including the number of poisoned training examples detected by each defense is provided in Table 7.

The PCA defense succeeds when the spectral signature is strong ($m=1,\varepsilon=500$) but fails when we diversify the attack, keeping the same number of poisons or reducing the number of poisons, because the spectral signature is weaker. Robust covariance estimation consistently amplifies these signatures, eliminating the backdoor in all cases. The clustering defense fails to separate poisons from clean ones.

2 mm-way periodic attacks

Proposed in (Barni et al. 2019), the periodic attack adds a periodic signal to the image as a trigger, as shown in Fig. 6. We chose signals with amplitude 6 and frequency of 8. We design an $m$-way periodic attack by choosing $m$ different (frequency, direction) pairs. Table 8 in the appendix provides all the experimental results. The same experimental setting was used as in Section 4.1. Algorithm 1 consistently removes the backdoors completely, whereas competing defenses fail.

3 Label consistent attacks

The obvious discrepancy between the image and the target label (e.g., a truck labelled as a deer) in previously presented attacks makes it trivial for a human to detect the poison. The label consistent attack, which was proposed in (Turner et al. 2019), designs images that are consistent with the target label, but can still create backdoors.

We used the same experimental setup as (Turner et al. 2019). For our experiments, we ran the provided implementation. https://github.com/MadryLab/label-consistent-backdoor-code Accuracy on clean data was between 91% and 92.5% in all experiments and are omitted in the table. More results are provided in Table 9 in the appendix.

Algorithm 1 removed all poisoned examples in every instance, guaranteeing that the backdoor was eliminated. However, in a wide regime, the PCA and Clustering defenses removed a small fraction of the poison or none at all.

4 Finding the effective dimension kk

Algorithm 1 takes a parameter $k$, which is the number of dimensions to use for covariance estimation. Comparing Figs. 8 and 9, note that no fixed value of $k$ works well for all experiments. A small choice of $k$ fails when the spectral signature is not in the top $k$ PCA directions, which happens when the attack is weak (Fig. 9). A large choice of $k$ fails when the clean data is not well-behaved (resilience property fails) in the lower PCA subspaces causing robust covariance estimation to fail (Fig. 8).

A major challenge in selecting the appropriate $k$ is that we do not have oracle access to the performance of our SPECTRE (in red), as in practice we do not know which samples are poisoned. We therefore propose selecting $k$ that maximizes the mean QUE score (in blue). Concretely, for each $k$ we run SPECTRE to remove $1.5\varepsilon n$ data points. We use the covariance of the remaining cleaned examples (in the representation space) to whiten all the data, and compute the mean QUE score of all the data points after whitening. The idea is that if poisons were correctly identified, then the mean QUE score will be large as poisons have strong spectral signature. We write the algorithm explicitly in Algorithm 3. Table 5 shows that Algorithm 3 selects nearly optimal values of $k$.

5 Identifying the target label

Ablation study

SPECTRE combines several steps to effectively detect poisoned examples.

Adaptive dimension reduction using Algorithm 3.

The covariance of the clean samples is estimated using Algorithm 10.

The samples are whitened using the estimated covariance.

We compute QUE scores using Algorithm 2 to determine which samples to discard.

Here we perform an ablation study to demonstrate that none of this steps can be omitted. We show that Step 1 is necessary in Section 4.4, where we show that no constant choice of $k$ is sufficient to detect the majority of the poison across multiple experiments. Note that choosing $k=d$ is equivalent to performing no dimension reduction. In our experiments, we found that checking values of $k$ which are substantially smaller than $d$ sufficed. This also gave us a substantial computational speedup since the runtime of Algorithm 1 scales with $k$. We show that Step 4 is important in Section 3.3. In particular, in Table 1 we show that two other natural choices for outlier scoring can fail under certain conditions. For Steps 2 and 3, we provide Table 6, which shows the performance of Algorithm 1 on a variety of experiments where Step 3 has been omitted (removing the need for Step 2) and where Step 2 is omitted, and the whitening is done using the sample covariance. The results in Table 6 justify the use of Steps 2 and 3.

Conclusion

While existing backdoor attacks are powerful enough to corrupt the trained model with a small fraction of injected poisoned training data, existing defenses fail under a broad regime of backdoor attacks. The reason is that the spectral signatures that those methods build upon are challenging to detect for a wide range of the attacks. We therefore introduce a novel defense algorithm, that we call SPECTRE, by combining the ideas from robust covariance estimation and quantum entropy outlier detection. Whitening with the robust covariance amplifies the spectral signature of the poisoned samples. The quantum entropy score can robustly detect that signature, adapting to the spectral profile of the poisoned examples. We demonstrate the superiority of our defense in several popular backdoor attacks, which suggest that the proposed defense is successful in all regimes we tested on, including those where the state-of-the-art baseline approaches fail. The empirical success of SPECTRE opens several new research directions, two of which we discuss in the following.

SPECTRE requires the trainer to have access to the corrupted training dataset. In some scenarios we might not have a direct access to the training data, for example due to privacy constraints. Identifying the statistical signatures in such settings is an interesting direction to make SPECTRE more widely applicable. A concrete direction is to design a decentralized and differentially private version of SPECTRE under the setting of federated learning (Pillutla et al. 2019). Recent advances in differentially private and robust estimators in (Liu et al. 2021) provide promising directions.

(Gao et al. 2019) proposes a different paradigm for defending against backdoor attacks. The defense, called STRIP, mixes each training sample with multiple other samples and measure the entropy of the resulting prediction. This leverages an aspect of common backdoor attacks that is different from spectral signatures. Understanding how these different types of defenses perform against different types of attacks, such as the hidden backdoor attacks from (Saha et al. 2020), is an important research question.

Acknowledgement

Sewoong Oh is supported by Google faculty research award and NSF grants CNS-2002664, IIS-1929955, and CCF-2019844 as a part of Institute for Foundations of Machine Learning.

References

Appendix

Appendix A Previous approaches

For completeness, we write the algorithms we used for comparisons here.

The principal component defense was proposed in (Tran et al. 2018). They analyze the representations by projecting them onto the top eigenvector of their covariance and then removing points that are far from the mean. This algorithm is shown in Algorithm 5.

A.2 Clustering Defense

The clustering defense was proposed in (Chen et al. 2018a). They analyze the representations produced by the network by reducing the dimension using principal component analysis and running a clustering algorithm on the result. The exact algorithm is shown in Algorithm 6.

Chen et al. 2018a propose several methods to determine which clusters, if any, contain poisoned representations. To avoid these complexities, we equip the algorithm with an oracle, ClusterOracle, which given two clusters returns the cluster with the greatest fraction of poisoned examples. The algorithm which returns the best cluster out of $C_{1},C_{2}$ give by the oracle should perform at least as well as any heuristic to determine which clusters to return. There are two other concerns which make it difficult to compare this defense with Algorithm 1: first, there is no way to control how many examples are removed and second, the performance of the clustering varies with the initialization of $k$-means, which is random. Therefore, we use a second step which repeatedly runs Algorithm 6 and samples the cluster with the highest fraction of poison according to the oracle in order to build the set of samples to remove. The algorithm is shown in Algorithm 7.

Algorithm 7 should perform well whenever the clustering is able to effectively separate the poisoned examples from clean ones and its performance should have relatively low variance as $R$ is built using many independent clustering runs. Although this process is not guaranteed to terminate, we found that it did in all of our experiments.

Appendix B Complete experimental results

Complete experimental results for $m$-way pixel attacks, $m$-way periodic attacks, and label consistent attacks are shown in Tables 7, 8 and 9 respectively.

Appendix C Supplemental experimental results for different source-target label pairs

In our previous experiments, we chose “deer” as the source label and “truck” as the target label following (Tran et al. 2018). We also ran the $m$-way pixel attack experiments for $m\in\{1,3\}$ and $\varepsilon n\in\{500,125\}$ for ten combinations of source and target labels. The results are shown in Table 10. Overall the trend in performance is similar, although there are some cases where none of the defences work well. We suspect that this is because the representations of the clean and poisoned samples are merged at an earlier point in the network, making them difficult to distinguish once they reach the penultimate residual block. We believe exploring this phenomenon presents an interesting research direction.

Appendix D Robust estimation

There exists a practical robust mean estimation algorithm RobustMean which is given explicitly in Algorithm 8.

Understanding Algorithm 10 requires the definition of an $\lparen\varepsilon,\tau\rparen$-good set with respect to a Gaussian, which is given in Definition D.1. The key feature of $\lparen\varepsilon,\tau\rparen$-goodness is that a set of independent samples from the Gaussian of sufficient size is $\lparen\varepsilon,\tau\rparen$-good with high probability as stated in Lemma D.2.

For all $\bm{x}\in S$ we have $\|\bm{x}-\bm{\mu}\lparen G\rparen\|_{2}\leq O\lparen\sqrt{d\log\lparen|S|/\tau\rparen}\rparen$.

We have that $\|\bm{\mu}\lparen S\rparen-\bm{\mu}\lparen G\rparen\|_{2}\leq\varepsilon$.

We have that $\|M_{s}-I\|_{2}\leq\varepsilon$.

(Diakonikolas et al. 2017a, Lemma A.6) Let $G$ be a sub-gaussian distribution with parameter $\nu=\Theta\lparen 1\rparen$ and identity covariance and let $\varepsilon,\tau>0$. If the multiset $S$ is obtained by taking $\Omega\lparen\lparen d/\varepsilon^{2}\rparen\operatorname{poly~log}\lparen d/\varepsilon\tau\rparen\rparen$ independent samples from $G$, it is $\varepsilon$-good with respect to $G$ with probability at least $1-\tau$.

Now we give the definition of the filter used in Algorithm 8 in Algorithm 9, which shows that the sets $S^{\prime}$ in Algorithm 8 approach the $\varepsilon$-good set $S$ with respect to the size of their symmetric difference.

D.2 Robust covariance estimation

The structure of this subsection mirrors that of Section D.1. 1 states the existence of a practical robust covariance estimation algorithm RobustCov which is given explicitly in Algorithm 10.

Understanding Algorithm 10 requires the definition of an $(\varepsilon$-good set with respect to a Gaussian, which is given in Definition D.3. The key feature of $\varepsilon$-goodness is that a set of independent samples from the Gaussian of sufficient size is $\varepsilon$-good with high probability as stated in Proposition D.4.

For all $\bm{x}\in S$, $\bm{x}^{\top}\Sigma^{-1}\bm{x}<d+O\lparen\sqrt{d}\log\lparen d/\varepsilon\rparen\rparen$.

We have that $\|\Sigma^{-1/2}\cov\lparen S\rparen\Sigma^{-1/2}-I\|_{F}=O\lparen\varepsilon\rparen$.

For all even degree-$2$ polynomials $p$, we have that $\var\lparen p\lparen\bm{x}\rparen\rparen=\var\lparen p\lparen G\rparen\rparen\lparen 1+O\lparen\varepsilon\rparen\rparen$.

(Diakonikolas et al. 2017a, Proposition A.28) Let $N$ be a sufficiently large constant multiple of $\lparen d^{2}/\varepsilon^{2}\rparen\log^{5}\lparen d/\varepsilon\rparen$. Then a set $S$ of $N$ independent samples from $G$ is $\varepsilon$-good with respect to $G$ with high probability.

Now we give the definition of the filter used in Algorithm 10 in Algorithm 11, which shows that the sets $S^{\prime}$ in Algorithm 10 approach the $\lparen\varepsilon,\tau\rparen$-good set $S$ with respect to the size of their symmetric difference.

Note that a naive implementation of Algorithm 12 requires $\Omega\lparen nd^{2}\rparen$ space to store the $\bm{y}_{i}$ and $\Omega\lparen d^{4}\rparen$ space to store $T_{S^{\prime}}$. Additionally, the matrix multiplication performed by OpenBLAS to produce $T_{S^{\prime}}$ requires $\Omega\lparen nd^{4}\rparen$ time. By representing the linear operator $T_{S^{\prime}}$ implicitly, we can reduce these requirements substantially. First, the product $-I^{\flat}(I^{\flat\top}\bm{v})$ can be computed in $O\lparen d^{2}\rparen$ time and space. Next, if $Y$ and $Z$ are the matrices with columns $\bm{y}_{i}$ and $\bm{z}_{i}$ respectively, then $Z$ is the Khatri-Rao product $Y\odot Y$. This means we can use the vec tricks for the Khatri-Rao and transpose Khatri-Rao vector products of (Periša 2017) to calculate $ZZ^{\top}\bm{v}$ in $O\lparen nd^{2}\rparen$ time and $O\lparen nd+d^{2}\rparen$ space. We can then calculate the eigenvector $\bm{v}^{*}$ of the implicitly represented linear operator $T_{S^{\prime}}$ using Krylov methods, requiring the evaluation of a small number of products $T_{S^{\prime}}\bm{v}$. For our experiments, this provided a speedup of several orders of magnitude and a substantial reduction in the required amount of system memory versus the naive implementation.

D.3 Robust joint mean and covariance estimation

Note that Algorithm 8 requires the inputs to have identity covariance and Algorithm 10 requires the inputs to have zero mean. Here we show how to combine them to estimate both the mean and covariance of an arbitrary Gaussian, as described in (Diakonikolas et al. 2017a, Section 4.5). The key idea is to split the dataset into two halves, pair off samples from each half, and subtract them. The resulting vectors have zero mean and double the original covariance. This allows us to use Algorithm 10 to whiten the samples, which then allows us to use Algorithm 8. We reproduce the exact procedure in Algorithm 13.

Appendix E Experiment details

For pixel attacks, we reproduce the experimental setup of (Tran et al. 2018). For our ResNet-32, we used a leaky ReLU with a negative slope of 0.1 for the nonlinearity and trained it using stochastic gradient descent with momentum for 200 epochs, dividing the learning rate by 10 every 75 epochs. Both data standardization and augmentation were used.

Although a fixed pixel is used for watermarking, data augmentation may ensure that the network is sensitive to pixels of the chosen color at multiple locations in the image. Using the standard random horizontal flip and random crop with 4 pixels of padding used for CIFAR-10, the pixel may end up in as many as $9\times 9\times 2=162$ distinct pixels in the transformed image, representing about 16% of the image’s total area.

To implement an $m$-way pixel attack, $m$ pairs of locations and colors are chosen. Only one of the $m$ pixels is used for each poisoned training example, but all $m$ are used simultaneously at test time. We ran experiments for $m\in\{1,2,3\}$. We used the same backdoor pixel Tran et al. 2018 used for their experiments, along with two more arbitrarily chosen. The exact locations and colors are shown in Table 11.

E.2 mm-way periodic attacks

For periodic attacks, we used the same network architecture and training environment used for pixel attacks. Although the phase of the signal is fixed for watermarking, the signal will be shifted by a random amount at training time due to the random flip and random crop and pad, in a manner similar to the pixel attack. Because our signals have a period of 4 pixels, which equals the maximum translation produced by the data augmentation, the backdoored network should be sensitive to signals with any phase.

E.3 Label consistent attacks

For label consistent attacks we used the experimental setup of (Turner et al. 2019) which is provided at https://github.com/MadryLab/label-consistent-backdoor-code. The setup of (Turner et al. 2019) appears to be very similar to that of (Tran et al. 2018). The same ResNet-32 architecture is used, albeit with a normal (i.e. not leaky) ReLU. Data standardization was enabled by default. Data augmentation was disabled by default, but we enabled it to ensure greater consistency with our previous experiments. We also enabled patch placement on all four corners to ensure the watermark would not be cropped out. For this family of attacks, we did not make any changes to the training system of (Turner et al. 2019), which does not provide retraining.

Appendix F Analysis of poisoned representations

Here we include Figs. 12, 13, 14 and 15, which illustrate some relevant properties of the hidden layer activations of examples bearing the target layer under a successful backdoor poisoning attack.

Appendix G Analysis of QUE scores

Appendix H Sensitivity to number of removed examples

Following (Tran et al. 2018), we choose to remove the $1.5\varepsilon n$ samples with the highest QUE scores from the $\lparen 1+\varepsilon\rparen n$ total samples bearing the target label. We show in Fig. 19 that our defence performance is not overly sensitive to this choice. In particular, the fraction of poisoned samples removed does not vary substantially with the total number of removed samples after the first $\varepsilon n$ samples are removed.