1 Introduction↩︎

Machine learning models, especially current large-scale models, require large amounts of labeled training data, which are often collected from untrusted third parties [1]. Training models on these potentially malicious data poses security risks. A typical application is in spam filtering, where the spam detector is trained using data (i.e., emails) that are generated by users with labels provided often implicitly by user actions. In this setting, spammers can generate spam messages that inject benign words likely to occur in spam emails such that models trained on these spam messages will incur significant drops in filtering accuracy as benign and malicious messages become indistinguishable [2], [3]. These kinds of attacks are known as poisoning attacks. In a poisoning attack, the attacker injects a relatively small number of crafted examples into the original training set such that the resulting trained model (known as the poisoned model) performs in a way that satisfies certain attacker goals.

One commonly studied poisoning attacks in the literature are indiscriminate poisoning attacks [4]–[12], in which the attackers aim to let induced models incur larger test errors compared to the model trained on a clean dataset. Other poisoning goals, including targeted [13]–[17] and subpopulation [9], [18] attacks, are also worth studying and may correspond to more realistic attack goals. We focus on indiscriminate poisoning attacks as these attacks interfere with the fundamental statistical properties of the learning algorithm [7], [10], but include a summary of prior work on understanding limits of poisoning attacks in other settings in the related work section.

Indiscriminate poisoning attack methods have been developed that achieve empirically strong poisoning attacks in many settings [7], [9]–[11], but these works do not explain why the proposed attacks are sometimes ineffective. In addition, the evaluations of these attacks can be deficient in some aspects [4], [7], [8], [10], [11], [19] (see 3) and hence, may not be able to provide an accurate picture on the current progress of indiscriminate poisoning attacks on linear models. The goal of our work is to understand the properties of the learning tasks that prevent effective attacks under linear models. An attack is considered effective if the increased error (or risk in the distributional sense) from poisoning exceeds the injected poisoning ratio [10], [11].

In this paper, we consider indiscriminate data poisoning attacks for linear models, the commonly studied victim models in the literature [4], [7], [12], [15], [19]. Attacks on linear models are also studied very recently [8]–[10], [20] and we limit our scope to linear models because attacks on the simplest linear models are still not well understood, despite extensive prior empirical work in this setting. Linear models continue to garner significant interest due to their simplicity and high interpretability in explaining predictions [21], [22]. Linear models also achieve competitive performance in many security-critical applications for which poisoning is relevant, including training with differential privacy [23], recommendation systems [24] and malware detection [25]–[30]. From a practical perspective, linear models continue to be relevant—for example, Amazon SageMaker [31], a scalable framework to train ML models intended for developers and business analysts, provides linear models for tabular data, and trains linear models (on top of pretrained feature extractors) for images.

We show that state-of-the-art poisoning strategies for linear models all have similar attack effectiveness of each dataset, whereas their performance varies significantly across different datasets (3). All tested attacks are very effective on benchmark datasets such as Dogfish and Enron, while none of them are effective on other datasets, such as selected MNIST digit pairs (e.g., 6–9) and Adult, even when the victim does not employ any defenses (1). To understand whether this observation means such datasets are inherently robust to poisoning attacks or just that state-of-the-art attacks are suboptimal, we first introduce general definitions of optimal poisoning attacks for both finite-sample and distributional settings (Definitions 1 and 2). Then, we prove that under certain regularity conditions, the performance achieved by an optimal poisoning adversary with finite-samples converges asymptotically to the actual optimum with respect to the underlying distribution (Theorem 1), and the best poisoning performance is always achieved at the maximum allowable poisoning ratio under mild conditions (Theorem 3).

Building upon these definitions, we rigorously characterize the behavior of optimal poisoning attacks under a theoretical Gaussian mixture model (Theorem 5), and derive upper bounds on their effectiveness for general data distributions (Theorem 7). In particular, we discover that a larger projected constraint size (Definition 5) is associated with a higher inherent vulnerability, whereas projected data distributions with a larger separability and smaller standard deviation (Definition 6) are fundamentally less vulnerable to poisoning attacks (5.2). Empirically, we find the discovered learning task properties and the gained theoretical insights largely explain the drastic difference in attack performance observed for state-of-the-art indiscriminate poisoning attacks on linear models across benchmark datasets (6). Finally, we discuss the potential implications of our work by showing how one might improve robustness to poisoning via better feature transformations and defenses (e.g., data sanitization defenses) to limit the impact of poisoning points (7).

Several prior works developed indiscriminate poisoning attacks by injecting a small fraction of poisoning points. One line of research adopts iterative gradient-based methods to directly maximize the surrogate loss chosen by the victim [6], [15], [19], [32], leveraging the idea of influence functions [33]. Another approach bases attacks on convex optimization methods [7], [9], [10], which provide a more efficient way to generate poisoned data, often with an additional input of a target model. Most of these works focus on studying linear models, but recently there has been some progress on designing more effective attacks against neural networks with insights learned from attacks evaluated on linear models [11], [34]. All the aforementioned works focus on developing different indiscriminate poisoning algorithms and some also characterize the hardness of poisoning in the model-targeted setting [9], [34], but did not explain why certain datasets are seemingly harder to poison than others. Our work leverages these attacks to empirically estimate the inherent vulnerabilities of benchmark datasets to poisoning, but focuses on providing explanations for the disparate poisoning vulnerability across the datasets. Besides injection, some other works consider different poisoning settings from ours by modifying up to the whole training data, also known as unlearnable examples [35]–[37] and some of them, similar to us, first rigorously analyze poisoning on theoretical distributions and then generalize the insights to general distributions [38], [39].

Although much research focuses on indiscriminate poisoning, many realistic attack goals are better captured as targeted attacks [13]–[17], where the adversary’s goal is to induce a model that misclassifies a particular known instance, or subpopulation attacks [9], [18], where the adversary’s goal is to produce misclassifications for a defined subset of the distribution. A recent work that studies the inherent vulnerabilities of datasets to targeted data poisoning attacks proposed the Lethal Dose Conjecture (LDC) [40]: given a dataset of size \(N\), the tolerable amount of poisoning points from any targeted poisoning attack generated through insertion, deletion or modifications is \(\Theta(N/n)\), where \(n\) is the sample complexity of the most data-efficient learner trained on the clean data to correctly predict a known test sample. Compared to our work, LDC is more general and applies to any dataset, any learning algorithm, and even different poisoning settings (e.g., deletion, insertion). In contrast, our work focuses on insertion-only indiscriminate attacks for linear models. However, the general setting for LDC can result in overly pessimistic estimates of the power of insertion-only indiscriminate poisoning attacks. In addition, the key factor of the sample complexity \(n\) in LDC is usually unknown and difficult to determine. Our work complements LDC by making an initial step towards finding factors (which could be related to \(n\)) under a particular attack scenario to better understand the power of indiscriminate data poisoning attacks. Appendix 13 provides more details.

2 Preliminaries↩︎

We consider binary classification tasks. Let \(\mathcal{X}\subseteq\mathbb{R}^n\) be the input space and \(\mathcal{Y}=\{-1, +1\}\) be the label space. Let \(\mu_c\) be the joint distribution of clean inputs and labels. For standard classification tasks, the goal is to learn a hypothesis \(h:\mathcal{X}\rightarrow\mathcal{Y}\) that minimizes \(\mathrm{Risk}(h; \mu_c) = \mathbb{P}_{(\boldsymbol{x},y)\sim \mu_c} \big[h(\boldsymbol{x}) \neq y \big]\). Instead of directly minimizing risk, typical machine learning methods find an approximately good hypothesis \(h\) by restricting the search space to a specific hypothesis class \(\mathcal{H}\), then optimizing \(h\) by minimizing some convex surrogate loss: \(\min_{h\in\mathcal{H}}\: L(h;\mu_c)\). In practical applications with only a finite number of samples, model training replaces the population measure \(\mu_c\) with its empirical counterpart. The surrogate loss for \(h\) is defined as \(L(h;\mu) = \mathbb{E}_{(\boldsymbol{x},y)\sim \mu} \big[\ell(h; \boldsymbol{x}, y)\big]\), where \(\ell(h;\boldsymbol{x},y)\) denotes the non-negative individual loss of \(h\) incurred at \((\boldsymbol{x},y)\).

We focus on the linear hypothesis class and study the commonly considered hinge loss in prior poisoning literature [4], [7], [9], [10], [19] when deriving the optimal attacks for 1-D Gaussian distributions in 5.1. Our results can be extended to other linear methods such as logistic regression (LR). A linear hypothesis parameterized by a weight parameter \(\boldsymbol{w}\in\mathbb{R}^n\) and a bias parameter \(b\in\mathbb{R}\) is defined as: \(h_{\boldsymbol{w},b}(\boldsymbol{x}) = \mathrm{sgn}(\boldsymbol{w}^\top\boldsymbol{x}+ b) \text{ for any } \boldsymbol{x}\in\mathbb{R}^n\), where \(\mathrm{sgn}(\cdot)\) denotes the sign function. For any \(\boldsymbol{x}\in\mathcal{X}\) and \(y\in\mathcal{Y}\), the hinge loss of a linear classifier \(h_{\boldsymbol{w}, b}\) is defined as: \[\begin{align} \label{eq:hinge32loss} \ell(h_{\boldsymbol{w},b}; \boldsymbol{x}, y) = \max\{0, 1 - y(\boldsymbol{w}^\top\boldsymbol{x}+b)\} + \frac{\lambda}{2}\|\boldsymbol{w}\|_2^2, \end{align}\tag{1}\] where \(\lambda \geq 0\) is the tuning parameter which penalizes the \(\ell_2\)-norm of the weight parameter \(\boldsymbol{w}\).

We formulate indiscriminate data poisoning attack as a game between an attacker and a victim in practice following the prior work [7]:

1. A clean training dataset \(\mathcal{S}_c\) is produced, where each data point is i.i.d. sampled from \(\mu_c\).

2. The attacker generates a poisoned dataset \(\mathcal{S}_p\) using some poisoning strategy \(\mathcal{A}\), which aims to reduce the performance of the victim model by injecting \(\mathcal{S}_p\) into the training dataset.

3. The victim minimizes empirical surrogate loss \(L(\cdot)\) on \(\mathcal{S}_c\cup \mathcal{S}_p\) and produces a model \(\hat{h}_p\).

The attacker’s goal is to find a poisoning strategy \(\mathcal{A}\) such that the risk of the final induced classifier \(\mathrm{Risk}(\hat{h}_p; \mu_c)\) is as high as possible, which is empirically estimated on a set of fresh testing data that are i.i.d. sampled from \(\mu_c\). We assume the attacker has full knowledge of the learning process, including the clean distribution \(\mu_c\) or the clean training dataset \(\mathcal{S}_c\), the hypothesis class \(\mathcal{H}\), the surrogate loss function \(\ell\) and the learning algorithm adopted by the victim.

We impose two restrictions to the poisoning attack: \(|\mathcal{S}_p| \leq \epsilon\cdot |\mathcal{S}_c|\) and \(\mathcal{S}_p\subseteq\mathcal{C}\), where \(\epsilon\in[0,1]\) is the poisoning budget and \(\mathcal{C}\subseteq\mathcal{X}\times\mathcal{Y}\) is a bounded subset that captures the feasibility constraints for poisoned data. We assume that \(\mathcal{C}\) is specified in advance with respect to different applications (e.g., normalized pixel values of images can only be in range \([0,1]\)) and possible defenses the victim may choose (e.g., points that have larger Euclidean distance from center will be removed) [7], [10]. Here, we focus on undefended victim models, i.e., \(\mathcal{C}\) is specified based on application constraints, so as to better assess the inherent dataset vulnerabilities without active protections. However, defense strategies such as data sanititation [7], [10], [41] may shrink the size of \(\mathcal{C}\) so that the poisoned data are less extreme and harmful. We provide preliminary experimental results on this in Section 7.

3 Disparate Poisoning Vulnerability of Benchmark Datasets↩︎

Prior evaluations of poisoning attacks on convex models are inadequate in some aspects, either being tested on very small datasets (e.g., significantly subsampled MNIST 1–7 dataset) without competing baselines [6], [12], [19], [32], generating invalid poisoning points [7], [10] or lacking diversity in the evaluated convex models/datasets [11], [34]. This motivates us to carefully evaluate representative attacks for linear models on various benchmark datasets without considering additional defenses.

We evaluate the state-of-the-art data poisoning attacks for linear models: Influence Attack [10], [15], KKT Attack [10], Min-Max Attack [7], [10], and Model-Targeted Attack (MTA) [9]. We consider both linear SVM and LR models and evaluate the models on benchmark datasets including different MNIST [42] digit pairs (MNIST 1–7, as used in prior evaluations [7], [9], [10], [19], in addition to MNIST 4–9 and MNIST 6–9 which were picked to represent datasets that are relatively easier/harder to poison), and other benchmark datasets used in prior evaluations including Dogfish [15], Enron [43] and Adult [9], [18]. Filtered Enron is obtained by filtering out 3% of near boundary points (with respect to the clean decision boundary of linear SVM) from Enron. The motivation of this dataset (along with Adult) is to show that, the initial error cannot be used to trivially infer the vulnerability to poisoning attacks (6). We choose \(3\%\) as the poisoning rate following previous works [7], [10], [11], [34]. 12.1 provides details on the experimental setup.

1 shows the highest error from the tested poisoning attacks (they perform similarly in most cases) on linear SVM. Similar observations are found on LR in 12.2.5. At \(3\%\) poisoning ratio, the (absolute) increased test errors of datasets such as MNIST 6–9 and MNIST 1–7 are less than 4% for SVM while for other datasets such as Dogfish, Enron and Filtered Enron, the increased error is much higher than the poisoning ratio, indicating that these datasets are more vulnerable to poisoning. Dogfish is moderately vulnerable (\(\approx\) 9% increased error) while Enron and Filtered Enron are highly vulnerable with over 30% of increased error. Consistent with prior work [7], [10], [34], throughout this paper, we measure the increased error to determine whether a dataset is vulnerable to poisoning attacks. However, in security-critical applications, the ratio between the increased error and the initial error might matter more but leave its exploration as future work. These results reveal a drastic difference in robustness of benchmark datasets to state-of-the-art indiscriminate poisoning attacks which was not explained in prior works. A natural question to ask from this observation is are datasets like MNIST digits inherently robust to poisoning attacks or just resilient to current attacks? Since estimating the performance of optimal poisoning attacks for benchmark datasets is very challenging, we first characterize optimal poisoning attacks for theoretical distributions and then study their partial characteristics for general distributions in Section 5.

4 Defining Optimal Poisoning Attacks↩︎

In this section, we lay out formal definitions of optimal poisoning attacks and study their general implications. First, we introduce a notion of finite-sample optimal poisoning to formally define the optimal poisoning attack in the practical finite-sample setting with respect to our threat model:

Definition 1 states that no poisoning strategy can achieve a better attack performance than that achieved by \(\small{\hat{\mathcal{A}}_\mathrm{opt}}\). If we denote by \(\small{\hat{h}_p^*}\) the hypothesis produced by minimizing the empirical loss on \(\mathcal{S}_c\cup\mathcal{S}_p^*\), then \(\small{\mathrm{Risk}(\hat{h}_p^*; \mu_c)}\) can be regarded as the maximum achievable attack performance.

Next, we introduce a more theoretical notion of distributional optimal poisoning, which generalizes Definition 1 from finte-sample datasets to data distributions.

Similar to the finite-sample case, Definition 2 implies that there is no feasible poisoned distribution \(\mu_p\) such that the risk of its induced hypothesis is higher than that attained by \(\mu_p^*\). Theorem 1, proven in Appendix 9.1, connects Definition 1 and Definition 2. The formal definitions of uniform convergence, strong convexity and Lipschitz continuity are given in Appendix 9.1.

Moreover, we note that \(\delta^*\) represents the ratio of injected poisoned data that achieves the optimal attack performance. In general, \(\delta^*\) can be any value in \([0, \epsilon]\), but we show in Theorem 3, proven in Appendix 9.2, that optimal poisoning can always be achieved with \(\epsilon\)-poisoning under mild conditions.

5 Characterizing Optimal Poisoning Attacks↩︎

This section characterizes the distributional optimal poisoning attacks with respect to linear hypothesis class. We first consider a theoretical 1-dimensional Gaussian mixture model and exactly characterize optimal poisoning attack and then discuss the implications on the underlying factors that potentially cause the inherent vulnerabilities to poisoning attacks for general high-dimensional distributions.

5.1 One-Dimensional Gaussian Mixtures↩︎

Consider binary classification tasks using hinge loss with one-dimensional inputs, where \(\mathcal{X}= \mathbb{R}\) and \(\mathcal{Y}=\{-1, +1\}\). Let \(\mu_c\) be the underlying clean data distribution, where each example \((x,y)\) is assumed to be i.i.d. sampled according to the following Gaussian mixture model: \[\label{eq:GMM32generating32process} \left\{ \begin{array} {ll} y=-1, x\sim\mathcal{N}(\gamma_1, \sigma_1^2) & \text{with probability p,}\\ y=+1, x\sim\mathcal{N}(\gamma_2, \sigma_2^2) & \text{with probability 1-p}, \end{array} \right.\tag{2}\] where \(\sigma_1, \sigma_2 > 0\) and \(p\in(0,1)\). Without loss of generality, we assume \(\gamma_1\leq\gamma_2\). Following our threat model, we let \(\epsilon\geq 0\) be the maximum poisoning ratio and \(\mathcal{C}:=[-u, u]\times \mathcal{Y}\) for some \(u>0\) be the constraint set. Let \(\mathcal{H}_{\mathrm{L}} = \{h_{w,b}: w\in\{-1, 1\}, b\in\mathbb{R}\}\) be the linear hypothesis class with normalized weights. Note that we consider a simplified setting where the weight parameter \(w\in\{-1, 1\}\).¹ Since \(\|w\|_2\) is fixed, we also set \(\lambda=0\) in the hinge loss function 1 .

For clarify in presentation, we outline the connection between the definitions and the main theorem below, which will also show the high-level proof sketch of 5. We first prove that in order to understand the optimal poisoning attacks, it is sufficient to study the family of two-point distributions (Definition 3), instead of any possible distributions, as the poisoned data distribution. Based on this reduction and a specification of weight flipping condition (Definition 4), we then rigorously characterize the optimal attack performance with respect to different configurations of task-related parameters (5). Similar conclusions may also be made with logistic loss.

Now we are ready to present our main theoretical results. The following theorem rigorously characterizes the behavior of the distributional optimal poisoning adversary \(\mathcal{A}_{\mathrm{opt}}\) under the Gaussian mixture model 2 and the corresponding optimal attack performance:

5.2 General Distributions↩︎

Recall that we have identified several key factors (i.e., \(u\), \(|\gamma_1 - \gamma_2|\) and \(\sigma\)) for 1-D Gaussian distributions in Section 5.1 which are highly related to the performance of an optimal distributional poisoning adversary \(\mathcal{A}_\mathrm{opt}\). In this section, we demonstrate how to generalize the definition of these factors to high-dimensional datasets and illustrate how they affect an inherent robustness upper bound to indiscriminate poisoning attacks for linear learners. In particular, we project the clean distribution \(\mu_c\) and the constraint set \(\mathcal{C}\) onto some vector \(\boldsymbol{w}\), then compute those factors based on the projections.

According to Definition 5, \(\mathrm{Size}_{\boldsymbol{w}}(\mathcal{C})\) characterizes the size of the constraint set \(\mathcal{C}\) when projected onto the (normalized) projection vector \(\boldsymbol{w}/\|\boldsymbol{w}\|_2\) then scaled by \(\|\boldsymbol{w}\|_2\), the \(\ell_2\)-norm of \(\boldsymbol{w}\). In theory, the constraint sets conditioned on \(y=-1\) and \(y=+1\) can be different, but for simplicity and practical considerations, we simply assume they are the same in the following discussions.

For finite-sample settings, we simply replace the input distributions with their empirical counterparts to compute the sample statistics of \(\mathrm{Sep}_{\boldsymbol{w}}(\mu_c)\) and \(\mathrm{SD}_{\boldsymbol{w}}(\mu_c)\). Note that the above definitions are specifically for linear models, but out of curiosity, we also provide initial thoughts on how to extend these metrics to neural networks (see Appendix 14 for preliminary results). Below, we provide justifications on how the three factors are related to the optimal poisoning attacks. Theorem 7 and the techniques used in its proof in Appendix 10.2 are inspired by the design of Min-Max Attack [7].

6 Experiments↩︎

Recall from Theorem 1 and Remark 2 that the finite-sample optimal poisoning attack is a consistent estimator of the distributional one for linear learners. In this section, we demonstrate the theoretical insights gained from Section 5, despite proven only for the distributional optimal attacks, still appear to largely explain the empirical performance of best attacks across benchmark datasets.

Given a clean training data \(\mathcal{S}_c\), we empirically estimate the three distributional metrics defined in Section 5.2 on the clean test data with respect to the weight \(\boldsymbol{w}_c\). Since \(\|\boldsymbol{w}_c\|_2\) may vary across different datasets while the predictions of linear models (i.e., the classification error) are invariant to the scaling of \(\|\boldsymbol{w}_c\|_2\), we use ratios to make their metrics comparable: \(\mathrm{Sep}_{\boldsymbol{w}_c}(\mu_c)/\mathrm{SD}_{\boldsymbol{w}_c}(\mu_c)\) (denoted as Sep/SD in 1) and \(\mathrm{Sep}_{\boldsymbol{w}_c}(\mu_c)/\mathrm{Size}_{\boldsymbol{w_c}}(\mathcal{C})\) (Sep/Size). According to our theoretical results, we expect datasets that are less vulnerable to poisoning have higher values for both metrics.

Table 1 summarizes the results where Error Increase is produced by the best attacks from the state-of-the-art attacks mentioned in 3. The Sep/SD and Sep/Size metrics are highly correlated to the poisoning effectiveness (as measured by error increase). Datasets such as MNIST 1–7 and MNIST 6–9 are harder to poison than others, which correlates with their increased separability and reduced impact from the poisoning points. In contrast, datasets such as Enron and Filtered Enron are highly vulnerable and this is strongly correlated to their small separability and the large impact from the admissible poisoning points. The results of Filtered Enron (low base error, high increased error) and Adult (high base error, low increased error) demonstrate that poisoning vulnerability, measured by the error increase, cannot be trivially inferred from the initial base error.

When the base error is small, which is the case for all tested benchmark datasets except Adult, the empirical metrics are highly correlated to the error increase and also the final poisoned error. However, when the base error becomes high as it is for Adult, the empirical metrics are highly correlated to the final poisoned error, but not the error increase, if the metrics are computed on the entire (clean) test data. For the error increase, computing the metrics on the clean and correctly classified (by \(\boldsymbol{w}_c\)) test points is more informative as it (roughly) accounts for the (newly) induced misclassification from poisoning. Therefore, we report metrics based on correctly-classified test points in 1 and defer results of the whole test data to Appendix 12.2. For datasets except Adult, both ways of computing the metrics produce similar results. The Adult dataset is very interesting in that it is robust to poisoning (i.e., small error increase) despite having a very high base error. As a preliminary experiment, we also extended our analysis to neural networks (14) and find the identified factors are correlated to the varied poisoning effectiveness when different datasets are compared under similar learners.

Our current results only show the correlation of the identified factors to the varied (empirical) poisoning effectiveness, not causality. However, we also speculate that these factors may cause different poisoning effectiveness because: 1) results in 5 characterize the relationship of these factors to the performance of optimal attacks exactly for 1-D Gaussian distributions and partially for the general distributions, and 2) preliminary results on MNIST 1–7 shows that gradual changes in one factor (with the other fixed) also causes gradual changes in the vulnerability to poisoning (12.2.6). We leave the detailed exploration on their causal relationship as future work.

7 Discussion on Future Implications↩︎

Our results imply future defenses by explaining why candidate defenses work and motivating defenses to improve separability and reduce projected constraint size. We present two ideas—using data filtering might reduce projected constraint size and using better features might improve separability.

The popular data sanitization defense works by filtering out bad points. We speculate it works because the defense may be effectively limiting the projected constraint size of \(\mathcal{C}\). To test this, we picked the combination of Sphere and Slab defenses considered in prior works [7], [10] to protect the vulnerable Enron dataset. We find that with the defense, the test error is increased from 3.2% to 28.8% while without the defense the error can be increased from 2.9% to 34.8%. Although limited in effectiveness, the reduced Error Increase with the defense is highly correlated to the significantly reduced projected constraint size \(\mathrm{Size}_{\boldsymbol{w}_c}(\mathcal{C})\) (and hence a significantly higher Sep/Size)—the Sep/Size metric jumps from 0.01 without defense to 0.11 with defense while Sep/SD remains almost the same at 1.18 with and without defense. Similar conclusions can also be drawn for MNIST 1-7 and Dogfish (detailed experimental results are in Appendix 12.2.3).

We consider a transfer learning scenario where the victim trains a linear model on a clean pretrained model. As a preliminary experiment, we train LeNet and ResNet18

models on the CIFAR10 dataset till convergence, but record the intermediate models of ResNet18 to produce models with different feature extractors (R-\(X\) denotes ResNet18 trained for \(X\) epochs). We then use the feature extraction layers of these models (including LeNet) as the pretrained models and obtain features of CIFAR10 images with labels “Truck” and “Ship”, and train linear models on them.

We evaluate the robustness of this dataset against poisoning attacks and set \(\mathcal{C}\) as dimension-wise box-constraints, whose values are the minimum and maximum values of the clean data points for each dimension when fed to the feature extractors. This way of configuring \(\mathcal{C}\) corresponds to the practical scenario where the victim has access to some small number of clean samples so that they can deploy a simple defense of filtering out inputs that do not fall into a dimension-wise box constraint that is computed from the available clean samples of the victim. 2 shows that as the feature extractor becomes better (using deeper models and training for more epochs), both the Sep/SD and Sep/Size metrics increase, leading to reduced error increase.

Quantitatively, the Pearson correlation coefficient between the error increase and each of the two factors is \(-0.98\) (a strong negative correlation). This result demonstrates the possibility that better feature representations free from poisoning might be leveraged to improve downstream resilience against indiscriminate poisoning attacks. We also simulated a more practical scenario where the training of the pretrained models never sees any data (i.e., data from classes of “Truck" and”Ship") used in the downstream analysis and the conclusions are similar (12.2.7).

8 Limitations↩︎

Our work also has several limitations. We only characterize the optimal poisoning attacks for theoretical distributions under linear models. Even for the linear models, the identified metrics cannot quantify the actual error increase from optimal poisoning attacks, which is an interesting future work, and one possible approach might be to tighten the upper bound in 7 using better optimization methods. The metrics identified in this paper are learner dependent, depending on the properties of the learning algorithm, dataset and domain constraints (mainly reflected through \(\mathcal{C}\)). In certain applications, one might be interested in understanding the impact of learner agnostic dataset properties on poisoning effectiveness—a desired dataset has such properties that any reasonable learners trained on the dataset can be robust to poisoning attacks. One likely application scenario is when the released data will be used by many different learners in various applications, each of which may be prone to poisoning. We also did not systematically investigate how to compare the vulnerabilities of different datasets under different learning algorithms. Identifying properties specific to the underlying learner that affect the performance of (optimal) data poisoning attacks is challenging but interesting future work.

Although we focus on indiscriminate data poisoning attacks in this paper, we are optimistic that our results will generalize to subpopulation or targeted poisoning settings. In particular, the specific learning task properties identified in this paper may still be highly correlated, but now additional factors related to the relative positions of the subpopulations/individual test samples to the rest of the population under the clean decision boundary will also play important roles.

Acknowledgements↩︎

We appreciate the comments from the anonymous reviewers. This work was partially funded by awards from the National Science Foundation (NSF) SaTC program (Center for Trustworthy Machine Learning, #1804603), the AI Institute for Agent-based Cyber Threat Intelligence and Operation (ACTION) (#2229876), NSF #2323105, and NSF #2325369. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. Fnu Suya also acknowledges the financial support from the Maryland Cybersecurity Center (MC2) at the University of Maryland to attend the conference.

9 Proofs of Main Results in Section 4↩︎

9.1 Proof of Theorem 1↩︎

We first introduce the formal definitions of strong convexity and Lipschitz continuity conditions with respect to a function, and the uniform convergence property respect to a hypothesis class. These definitions are necessary for the proof of Theorem 1.

Such a uniform convergence property, which can be achieved using the VC dimension or the Rademacher complexity of \(\mathcal{H}\), guarantees that the learning rule specified by empirical risk minimization always returns a good hypothesis with high probability [44]. Similar to PAC learning, the function \(m_\mathcal{H}\) measures the minimal sample complexity requirement that ensures uniform convergence.

Now, we are ready to prove Theorem 1

9.2 Proof of Theorem 3↩︎

9.3 Proofs of the Statement about Linear Models in Remark 4↩︎

10 Proofs of Main Results in Section 5↩︎

10.1 Proof of Theorem 5↩︎

To prove Theorem 5, we need to make use of the following three auxiliary lemmas, which are related to the maximum population hinge loss with \(\boldsymbol{w}=1\) (Lemma 1), the weight-flipping condition (Lemma 2) and the risk behaviour of any linear hypothesis under 2 (Lemma 3). For the sake of completeness, we present the full statements of Lemma 1 and Lemma 2 as follows. In particular, Lemma 1, proven in Appendix 11.1, characterizes the maximum achievable hinge loss with respect to the underlying clean distribution \(\mu_c\) and some poisoned distribution \(\mu_p\) conditioned on \(w=1\).

Lemma 1 suggests that it is sufficient to study the extreme two-point distributions \(\nu_\alpha\) with \(\alpha\in[0,1]\) to understand the maximum achievable population hinge loss conditioned on \(w=1\). Lemma 2, proven in Appendix [sec:proof32thm32condition32exist32w61-1], characterizes the sufficient and necessary conditions in terms of \(\epsilon\), \(u\) and \(\mu_c\), under which there exists a linear hypothesis with \(w=-1\) that achieves the minimal value of population hinge loss with respect to \(\mu_c\) and some \(\mu_p\).

Lemma 2 identifies sufficient and necessary conditions when a linear hypothesis with flipped weight parameter is possible. Note that we assume \(\gamma_1\leq \gamma_2\), thus flipping the weight parameter of the induced model from \(w=1\) to \(w=-1\) is always favorable from an attacker’s perspective. In particular, if the population hinge loss with respect to \(\mu_c\) and some \(\mu_p\) achieved by the loss minimizer conditioned on \(w=1\) is higher than that achieved by the loss minimizer with \(w=-1\), then we immediately know that flipping the weight parameter is possible, which further suggests the optimal poisoning attack performance must be achieved by some poisoned victim model with \(w=-1\).

Finally, we introduce Lemma 3, proven in Appendix 11.3, which characterizes the risk behavior of any linear hypothesis with respect to the assumed Gaussian mixture model 2 .

Now we are ready to prove Theorem 5 using Lemmas 1, 2 and 3.

10.2 Proof of Theorem 7↩︎

11 Proofs of Technical Lemmas used in Appendix 10.1↩︎

11.1 Proof of Lemma 1↩︎

To prove Lemma 1, we need to make use of the following general lemma which characterizes the population hinge loss and its derivative with respect to clean data distribution \(\mu_c\). For the sake of completeness, we provide the proof of Lemma 4 in Appendix 11.4.

Next, let us summarize several key observations based on Lemma 4 (specifically for the setting considered in Lemma 1). For any \(w\in\{-1, 1\}\), \(\frac{\partial}{\partial b}L(h_{w,b};\mu_c)\) is a monotonically increasing with \(b\), which achieves minimum \(-\frac{1}{2}\) when \(b\) goes to \(-\infty\) and achieves maximum \(\frac{1}{2}\) when \(b\) goes to \(\infty\). If \(w=+1\), then \(L(h_{w,b}; \mu_c)\) is monotonically decreasing when \(b\in(-\infty, -\frac{\gamma_1+\gamma_2}{2})\) and monotonically increasing when \(b\in(-\frac{\gamma_1+\gamma_2}{2}, \infty)\), reaching the minimum at \(b = b^{*}_{c}(1):=-\frac{\gamma_1+\gamma_2}{2}\). On the other hand, if \(w=-1\), then \(L(h_{w,b}; \mu_c)\) is monotonically decreasing when \(b\in(-\infty, \frac{\gamma_1+\gamma_2}{2})\) and monotonically increasing when \(b\in(\frac{\gamma_1+\gamma_2}{2}, \infty)\), reaching the minimum at \(b = b^{*}_{c}(-1) :=\frac{\gamma_1+\gamma_2}{2}\).

As for the clean loss minimizer conditioned on \(w=1\), we have \[\begin{align} L(h_{1,b_c^*(1)};\mu_c) &= \frac{1}{2}\int_{\frac{\gamma_2-\gamma_1-2}{2\sigma}}^{\infty} \bigg(\frac{\gamma_1-\gamma_2}{2}+1+\sigma z\bigg)\cdot\varphi(z) dz \\ &\qquad + \frac{1}{2}\int^{\frac{\gamma_1-\gamma_2+2}{2\sigma}}_{-\infty} \bigg(\frac{\gamma_1-\gamma_2}{2}+1-\sigma z\bigg)\cdot\varphi(z) dz \\ &= \frac{(\gamma_1-\gamma_2+2)}{2}\cdot \Phi\bigg(\frac{\gamma_1-\gamma_2+2}{2\sigma}\bigg) + \frac{\sigma}{\sqrt{2\pi}}\cdot\exp\bigg(-\frac{(\gamma_1-\gamma_2+2)^2}{8\sigma^2}\bigg), \end{align}\] whereas as for the clean loss minimizer conditioned on \(w=-1\), we have \[\begin{align} L(h_{-1,b_c^*(-1)};\mu_c) &= \frac{1}{2}\int_{\frac{\gamma_1-\gamma_2-2}{2\sigma}}^{\infty} \bigg(\frac{\gamma_2-\gamma_1}{2}+1+\sigma z\bigg)\cdot\varphi(z) dz\\ &\qquad + \frac{1}{2}\int^{\frac{\gamma_2-\gamma_1+2}{2\sigma}}_{-\infty} \bigg(\frac{\gamma_2-\gamma_1}{2}+1-\sigma z\bigg)\cdot\varphi(z) dz \\ &= \frac{(\gamma_2-\gamma_1+2)}{2}\cdot \Phi\bigg(\frac{\gamma_2-\gamma_1+2}{2\sigma}\bigg) + \frac{\sigma}{\sqrt{2\pi}}\cdot\exp\bigg(-\frac{(\gamma_2-\gamma_1+2)^2}{8\sigma^2}\bigg). \end{align}\] Let \(f(t) = t\cdot\Phi(\frac{t}{\sigma}) + \frac{\sigma}{\sqrt{2\pi}}\cdot \exp(-\frac{t^2}{2\sigma^2})\), we know \(L(h_{1,b_c^*(1)};\mu_c) = f(\frac{\gamma_1-\gamma_2+2}{2})\) and \(L(h_{-1,b_c^*(-1)};\mu_c) = f(\frac{\gamma_2-\gamma_1+2}{2})\). We can compute the derivative of \(f(t)\): \(f'(t) = \Phi(\frac{t}{\sigma}) \geq 0\), which suggests that \(L(h_{1,b_c^*(1)};\mu_c) \leq L(h_{-1,b_c^*(-1)};\mu_c)\).

Now we are ready to prove Lemma 1.

11.2 Proof of Lemma 2↩︎

11.3 Proof of Lemma 3↩︎

11.4 Proof of Lemma 4↩︎

12 Additional Experimental Results and Details↩︎

In this section, we provide details on our experimental setup (12.1) and then provide additional results (12.2).

12.1 Details on Experimental Setup in Section 3↩︎

In the main paper, we used different public benchmark datasets including MNIST [48] digit pairs (i.e., 1–7. 6–9, 4–9) and also the Enron dataset, which is created by Metsis et al. [43], Dogfish [15] and Adult [49], which are all used in the evaluations of prior works except MNIST 6–9 and MNIST 4–9. In the appendix, we additionally present the results of the IMDB dataset [50], which has also been used in prior evaluations [10], [15]. We did not include the IMDB results in the main paper because we could not run the existing state-of-the-art poisoning attacks on IMDB because the computation time is extremely slow. Instead, we directly quote the poisoned error of SVM from Koh et al. [10] and then present the computed metrics. For the Dogfish and Enron dataset, we construct the constraint set \(\mathcal{C}\) in the no defense setting by finding the minimum (\(u^i_{\min}\)) and maximum (\(u^i_{\max}\)) values occurred in each feature dimension \(i\) for both the training and test data, which then forms a box constraint \([u^i_{\min},u^i_{\max}]\) for each dimension. This way of construction is also used in the prior work [10]. Because we consider linear models, the training [51] of linear models and the attacks on them are stable (i.e., less randomness involved in the process) and so, we get almost identical results when feeding different random seeds. Therefore, we did not report error bars in the results. The regularization parameter \(\lambda\) for training the linear models (SVM and LR) are configured as follows: \(\lambda=0.09\) for MNIST digit pairs, Adult, Dogfish, SVM for Enron; \(\lambda=0.01\) for IMDB, LR for Enron. Overall, the results and conclusions in this paper are insensitive to the choice of \(\lambda\). The computation of the metrics in this paper are extremely fast and can be done on any laptop. The poisoning attacks can also be done on a laptop, except the Influence Attack [10], whose computation can be accelerated using GPUs.

The KKT, MTA and Min-Max attacks evaluated in 3 require a target model as input. This target model is typically generated using some label-flipping heuristics [9], [10]. In practice, these attacks are first run on a set of carefully-chosen target models, then the best attack performance achieved by these target models is reported. We generate target models using the improved procedure described in Suya et al. [9] because their method is able to generate better target models that induce victim models with a higher test error compared with the method proposed in Koh et al. [10]. We generate target models with different error rates, ranging from \(5\%\) to \(70\%\) using the label-flipping heuristics, and then pick the best performing attack induced by these target models.

Following the prior practice [10], we consider adversaries that have access to both the clean training and test data, and therefore, adversaries can design attacks that can perform better on the test data. This generally holds true for the Enron and MNIST 1–7 datasets, but for Dogfish, we find in our experiments that the attack “overfits” to the test data heavily due to the small number of training and test data and also the high dimensionality. More specifically, we find that the poisoned model tends to incur significantly higher error rates on the clean test data compared to the clean training data. Since this high error cannot fully reflect the distributional risk, when we report the results in 3 we report the errors on both the training and the testing data to give a better empirical sense of what the distributional risk may look like. This also emphasizes the need to be cautious on the potential for “overfitting” behavior when designing poisoning attacks. 2 shows the drastic differences between the errors of the clean training and test data after poisoning.

12.2 Supplemental Results↩︎

In this section, we provide additional results results that did not fit into the main paper, but further support the observations and claims made in the main paper. We first show the results of IMDB and the metrics computed on the whole clean test data in 12.2.2 to complement Table 1 in the main paper, then include the complete results of the impact of data sanitization defenses in 12.2.3 to complement the last paragraph in 7. Next, we provide the metrics computed on selective benchmark datasets using a different projection vector from the clean model weight in 12.2.4 to support the results in 1 in the main paper. Lastly, we show the performance of different poisoning attacks at various poisoning ratios in 12.2.5, complementing 1 in the main paper.

12.2.1 IMDB results↩︎

Table 1 in the main paper presents the metrics that are computed on the correctly classified test samples by the clean model \(\boldsymbol{w}_c\). In Table 3, we additionally include the IMDB results to the Table 1 in the main paper. From the table, we can see that IMDB is still highly vulnerable to poisoning because its separability is low compared to datasets that are moderately vulnerable or robust, and impacted the most by the poisoning points compared to all other benchmark datasets. Note that, the increased error from IMDB is directly quoted from Koh et al. [10], which considers data sanitization defenses. Therefore, we expect the attack effectiveness might be further improved when we do not consider any defenses, as in our paper.

12.2.2 Metrics computed using all test data↩︎

Table 4 shows the results when the metrics are computed on the full test data set (including misclassified ones), rather than just on examples that were classified correctly by the clean model. The metrics are mostly similar to Table 3 when the initial errors are not high. For datasets with high initial error such as Adult, the computed metrics are more aligned with the final poisoned error, not the error increase.

12.2.3 Explaining the impact of data sanitization defenses↩︎

We then provide additional results for explaining the effectiveness of the data sanitization defenses in improving dataset robustness, which is discussed in 7. On top of the Enron result shown in the paper, which is attacked at 3% poisoning ratio, we also provide attack results of MNIST 1-7 dataset. We report the attack results when \(\epsilon=10\%\) and we considered a significantly higher poisoning ratio because at the original 3% poisoning, the dataset can well resist existing attacks and hence there is no point in protecting the dataset with sanitization defenses. This attack setting is just for illustration purpose and attackers in practice may be able to manipulate such a high number of poisoning points. Following the main result in the paper, we still compute the metrics based on the correctly classified samples in the clean test set, so as to better depict the relationship between the increased errors and the computed metrics. The results are summarized in Table 5 and we can see that existing data sanitization defenses improve the robustness to poisoning by majorly limiting \(\mathrm{Size}_{\boldsymbol{w}_c}(\mathcal{C})\). For MNIST 1-7, equipping with data sanitization defense will make the dataset even more robust (robust even at the high 10% poisoning rate), which is consistent with the findings in prior work [7].

12.2.4 Using different projection vectors↩︎

In the main paper, we used the weight of the clean model as the projection vector and found that the computed metrics are highly correlated with the empirical attack effectiveness observed for different benchmark datasets. However, there can also be other projection vectors that can be used for explaining the different vulnerabilities, as mentioned in 8.

We conducted experiments that use the projection vector that minimizes the upper bound on optimal poisoning attacks, given in Equation 5 . The upper-bound minimization corresponds to a min-max optimization problem. We solve it using the online gradient descent algorithm (alternatively updating the poisoning points and model weight), adopting an approach similar to the one used by Koh et al.for the i-Min-Max attack [10]. We run the min-max optimization for 30,000 iterations with learning rate of 0.03 for the weight vector update, and pick the weight vector that results in the lowest upper bound in Equation 5 .

The results on two of the benchmark datasets, MNIST 1–7 and Dogfish, are summarized in Table 6. From the table, we can see that, compared to the clean model, the new projection vector reduces the projected constraint size (increases Sep/Size), which probably indicates the weight vector obtained from minimizing the upper bound focuses more on minimizing the term \(\ell_{\mathrm{M}}(\mathrm{Size}_{\boldsymbol{w_c}}(\mathcal{C}))\) in Equation 5 . Nevertheless, projecting onto the new weight vector can still well explain the difference between the benchmark datasets.

Using the obtained vector \(\boldsymbol{w}_U\) (denote the corresponding hypothesis as \(h_U\)) above, we can also compute an (approximate) upper bound on the test error of the optimal indiscriminate poisoning attack, which is proposed by Steinhardt et al. [7] and is shown in 17 . The upper bound is an approximate upper bound to the test error because \(\max_{\mathcal{S}_p \subseteq \mathcal{C}}\; L(\hat{h}_p; \mathcal{S}_c)\) only upper bounds the maximum training error (of poisoned model \(\hat{h}_p\)) on \(\mathcal{S}_c\) from poisoning and it is assumed that, with proper regularization, the training and test errors are roughly the same. We can view \(h_U\) as the numerical approximation of the hypothesis that leads to the smallest upper bound on the (approximate) test error. Next, in 7, we compare the computed (approximate) upper bound and the lower bound on poisoning effectiveness achieved by best known attacks, and we can easily observe that, although the gap between the lower and upper bounds are relatively large (all datasets are vulnerable at 3% poisoning ratio when we directly check the upper bounds), the upper bounds still vary between datasets. We also speculate that the actual performance of the best attacks may not be as high as indicated by the upper bound, because when computing the upper bound, we used the surrogate loss to upper bound the 0-1 loss (exists some non-negligible gap) and maximized the surrogate loss in the poisoning setting, which potentially introduces an even larger gap between the surrogate loss and the 0-1 loss. Hence, we motivate future research to shrink the possibly large gap.

\[\begin{align} \label{eq:min-max32upper32bound32on32opt32poison} \nonumber \underset{\mathcal{S}_p \subseteq \mathcal{C}}{\max}\; L(\hat{h}_p; \mathcal{S}_c) & \leq \underset{h}{\min} \bigg( L(h;\mathcal{S}_c)+\epsilon\underset{(\boldsymbol{x}_p,y_p) \in \mathcal{C}}{\max}\;\ell(h;\boldsymbol{x}_p,y_p)+\frac{(1+\epsilon)\lambda}{2} \|\boldsymbol{w}\|_2^2 \bigg)\\ & \leq L(h_U;\mathcal{S}_c)+\epsilon\underset{(\boldsymbol{x}_p,y_p) \in \mathcal{C}}{\max}\;\ell(h_U;\boldsymbol{x}_p,y_p)+\frac{(1+\epsilon)\lambda}{2} \|\boldsymbol{w}_U\|_2^2 \end{align}\tag{17}\]

12.2.5 Performance of different attacks are similar↩︎

In this section, we first present the best attack results on different benchmark datasets on the LR model in 3. Similar to the case of linear SVM as shown in 1, the performance of best known attacks vary drastically across the benchmark datasets. Although we only report the performance of the best known attack from the candidate state-of-the-art poisoning attacks, the difference among these canndidate attacks do not vary much in many settings. In 4 we show the attack performance of different attacks on the selected benchmark datasets of MNIST 1–7, Dogfish, and Enron and the main observation is that different attacks perform mostly similarly for a given dataset (but their performance varies a lot across datasets). Also, from the attack results on Enron (4 (c)), we can see that several of the attacks perform worse at higher poisoning ratios. Although there is a chance that the attack performance can be improved by careful hyperparameter tuning, it also suggests that these attacks are suboptimal. Optimal poisoning attacks should never get less effective as the poisoning ratio increases, according to 3.

12.2.6 Possible causal relationship of identified factors to poisoning vulnerability↩︎

In this section, we describe our preliminary experiment on showing the possible causal relationship from the identified two factors (i.e., Sep/SD and Sep/Size) to the empirically observed vulnerability against poisoning attacks. Given a dataset, we aim to modify it such that we can gradually change one factor of the dataset while (ideally) keeping the other one fixed, and then measure the changes in its empirical poisoning vulnerability. To cause changes to the factor of “Sep/SD", we need to modify the original data points in the dataset. This modification may make it hard to keep the factor of”Sep/Size" (or “Size") fixed, as the computation of”Size" depends on the clean boundary \(\boldsymbol{w}_c\), which is again dependent on the (modified) clean distribution. Therefore, even if we use the same constraint set \(\mathcal{C}\) for different modified datasets, the “Size" or”Sep/Size" can be different. We conducted preliminary experiments on MNIST 1–7 and the details are given below.

, In order to measure the impact of Sep/Size without impacting Sep/SD, we can choose \(\mathcal{C}\) that covers even larger space so that the resulting constraint set will not filter out any clean points from the original training data, which then implies both the \(\boldsymbol{w}_c\) and the corresponding metric of Sep/SD will not change. We performed a hypothetical experiment on MNIST 1–7 where we scale the original box-constraint from \([0,1]\) to \([0,c], c>=1\), where \(c\) is the scale factor and \(c=1\) denotes the original setting for MNIST 1–7 experiment. The experiments are hypothetical because, in practice, a box-constraint of \([0,c]\) with \(c>1\) will result in invalid images. We experimented with \(c=2,3,5,7,10\) and the results are summarized in Table 8. From the table, we see that as \(c\) becomes larger, the Size increases and correspondingly the Sep/Size decreases. These changes are associated with a gradual increase in the “Error Increase" from poisoning.

As mentioned above, in order to change Sep/SD, we need to modify the original data points, and this modification makes it hard for us to keep Sep/Size fixed for MNIST 1–7 even when using the same \(\mathcal{C}\). We leave the exploration of better ways to change data distributions with the Sep/Size fixed as future work. To modify the original data points, we first train a linear SVM on the original MNIST 1-7 dataset. Then, we pick 3% of all (training + test data) correctly classified points that are closest to the clean boundary. These points, once repeated \(x\) times, replace \(x\times 3\%\) of correctly classified training and testing data points that are furthest from the boundary. This process can be viewed as oversampling in the near-boundary region and undersampling in the region far from the boundary, and aim to create a dataset with a low separability ratio. We tested with \(x=1,2,4,6,8,10\). We only deal with correctly classified points because we want to ensure the modified dataset still has high clean accuracy. The results are summarized in Table 9 and we can see that as we increase \(x\), the Sep/SD gradually decreases, and the attack effectiveness (measured by the error increase) increases. Interestingly, the Sep/Size also decreases even though it is computed with the same \(\mathcal{C}\). Although the preliminary results above are not sufficient to prove a causation claim, they still show the possibility with the empirical evidence on the MNIST 1–7 dataset.

12.2.7 Evaluating feature extractors with downstream data removed↩︎

The experiments in 2 uses the entire CIFAR10 training data to train the pretrained feature extractor, which also includes the data of class “Truck" and”Ship" that are used in the downstream training and analysis. Although our original experiment aims to show how the victim can gain improved resistance to poisoning by using better feature extractors, for the particular experiment in 2, a more realistic setting is to exclude the downstream training data used to train the (upstream) pretrained feature extractors. Therefore, we repeated the same experiment, but now removed the data points from the classes of "Ship" and "Truck" from the upstream training data and then train the (pretrained) models. The results are summarized in 5 and the overall finding is similar to the one in 2 that when we adopt a deep architecture and train it for more epochs, the quality of the obtained feature extractor increases and so, it appears to improve the resistance of downstream classifiers to poisoning attacks. The increased quality of the feature extractor is in general correlated to the increased Sep/SD and Sep/Size. To quantitatively measure the correlation of the error increase and each of the two factors, we show the Pearson correlation coefficient of the relevant metrics and the results are summarized in 10. From the table, we can see that when we directly measure the Pearson correlation with each individual factor, the correlation between the two factors and error increase is still very strong as the lowest (absolute) correlation coefficient of -0.66 still indicates a strong negative correlation. And if we further restrict ourselves to the ResNet-18 models only, then the (absolute) correlation coefficient is even higher, which again confirms the two factors are strongly (and negatively) correlated with the error increase.

In 10, we also compare the new experiment with the original experiment in 2 and observe that the (absolute) Pearson correlation is reduced slightly, which is due to the fact that when the pretrained model does not involve any downstream data, the two factors may not consistently change in the same direction and undermines the Pearson correlation of each individual factor with the error increase. However, if we compute the Pearson correlation between the number of epochs for training the ResNet-18 model (roughly incorporates the combined effects of both factors) and the error increase from poisoning, we observe an even stronger negative correlation (-0.99) compared to the original experiment (-0.95), which again supports the claim that training the deep architecture for more epochs seems to be one possible approach to improve resistance to poisoning. The slight increase in correlation in the new experiment results from the slightly higher covariance between the error increase and the number of epochs, but this difference is not significant since we only consider a limited number of samples when computing the correlation.

Developing general methods for learning meaningful feature extractors such that the two factors can be improved simultaneously in a controlled way would be an interesting research direction, which we plan to pursue in the future. However, we also note that this is a challenging task from the practical perspective since the goal is to extract useful feature representations for downstream applications, so the base error should also be considered in addition to the error increase from poisoning, especially when no downstream data are used in the upstream training. Our initial thought is to consider an intermediate few-shot learning setup [52], where a small number of (clean) downstream training data are allowed to be incorporated in training the feature extractor. This few-shot learning setup might correspond to an intermediate setting between the original experiment with full knowledge of the (clean) downstream training data and the new experiment with almost zero knowledge but still reflects certain real-world application scenarios. To conclude, all results in both the original and new experiments support our main claim that it is possible for the victim to choose better feature extractors to improve the resistance of downstream classifiers to indiscriminate poisoning attacks.

13 Comparison to LDC and Aggregation Defenses↩︎

We first provide a more thorough discussion on the differences between our work and the Lethal Dose Conjecture (LDC) [40] from NeurIPS 2022, which had similar goals in understanding the inherent vulnerabilities of datasets but focused on targeted poisoning attacks (13.1). Then, we discuss how our results can also be related to aggregation based defenses whose asymptotic optimality on robustness against targeted poisoning attacks is implied by the LDC conjecture (13.2).

13.1 Relation to LDC↩︎

As discussed in 1, LDC is a more general result and covers broader poisoning attack goals (including indiscriminate poisoning) and is agnostic to the learning algorithm, dataset and also the poisoning generation setup. However, this general result may give overly pessimistic estimates on the power of optimal injection-only poisoning attacks in the indiscriminate setting we consider. We first briefly mention the main conjecture in LDC and then explain why the LDC conjecture overestimated the power of indiscriminate poisoning attacks, followed by a discussion on the relations of the identified vulnerability factors in this paper and the key quantity in LDC.

LDC conjectures that, given a (potentially poisoned) dataset of size \(N\), the tolerable sample size for targeted poisoning attacks (through insertion and/or deletion) by any defenses and learners, while still predicting a known test sample correctly, is an asymptotic guarantee of \(\Theta(N/n)\), where \(n<N\) is the sample complexity of the most data-efficient learner (i.e., a learner that uses smallest number of clean training samples to make correct prediction). Although it is a conjecture on the asymptotic robustness guarantee, it is rigorously proven for cases of bijection uncovering and instance memorization, and the general implication of LDC is leveraged to improve existing aggregation based certified defenses against targeted poisoning attacks.

LDC conjectures the robustness against targeted poisoning attacks, but the same conjecture can also be used in indiscriminate setting straightforwardly by taking the expectation over the tolerable samples for each of the test samples to get the expected tolerable poisoning size for the entire distribution (as mentioned in the original LDC paper) or by choosing the lowest value to give a worst case certified robustness for the entire distribution. The underlying assumption in the reasoning above is that individual samples are independently impacted by their corresponding poisoning points while in the indiscriminate setting, the entire distribution is impacted simultaneously by the same poisoning set. The assumption on the independence of the poisoning sets corresponding to different test samples might overestimate the power of indiscriminate poisoning attacks as it might be impossible to simultaneously impact different test samples (e.g., test samples with disjoint poisoning sets) using the same poisoning set. In addition, the poisoning generation setup also greatly impacts the attack effectiveness—injection only attacks can be much weaker than attacks that modify existing points, but LDC provides guarantees against this worst case poisoning generation of modifying points. These general and worst-case assumptions mean that LDC might overestimate the power of injection-only indiscriminate poisoning attacks considered in this paper.

In practice, insights from LDC can be used to enhance existing aggregation based defenses. If we treat the fraction of (independently) certifiable test samples by the enhanced DPA [53] in Figure 2(d) (using \(k=500\) partitions) in the LDC paper as the certified accuracy (CA) for the entire test set in the indiscriminate setting, the CA against indiscriminate poisoning attack is 0% at the poisoning ratio of \(\epsilon = 0.5\%\) \((250/50000)\). In contrast, the best indiscriminate poisoning attacks [34] on CIFAR10 dataset reduces the model accuracy from 95% to 81% at the much higher \(\epsilon=3\%\) poisoning ratio using standard training (i.e., using \(k=1\) partition). Note that using \(k=1\) partition is a far less optimal choice than \(k=500\) as \(k=1\) will always result in \(0\%\) CA for aggregation based defenses. Our work explicitly considers injection only indiscriminate poisoning attacks so as to better understand its effectiveness.

While it is possible that current indiscriminate attacks for neural networks are far from optimal and there may exist a very strong (but currently unknown) poisoning attack that can reduce the neural network accuracy on CIFAR10 to 0% at a 0.5% poisoning ratio, we speculate such likelihood might be low. This is because, neural networks are found to be harder to poison than linear models [11], [34] while our empirical findings in the most extensively studied linear models in 3 indicate some datasets might be inherently more robust to poisoning attacks.

As mentioned above, LDC might overestimate the power of indiscriminate poisoning attacks. In addition, the key quantity \(n\) is usually unknown and hard to estimate accurately in practice and the robustness guarantee is asymptotic while the constants in asymptotic guarantees can make a big difference in practice. However, the generic metric \(n\) still offers critical insights in understanding the robustness against indiscriminate poisoning attacks. In particular, our findings on projected separability and standard deviation can be interpreted as the first step towards understanding the dataset properties that can be related to the (more general) metric \(n\) (and maybe also the constant in \(\Theta(1/n)\)) in LDC for linear learners. Indeed, it is an interesting future work to identify the learning task properties that impact \(n\) at the finer-granularity.

As for the projected constraint size (Definition 5), we believe there can be situations where it may be independent from \(n\). The main idea is that in cases where changing \(\mathcal{C}\) arbitrarily will not impact the clean distribution (e.g., when the support set of the clean distribution is a strict subset of \(\mathcal{C}\), arbitrarily enlarging \(\mathcal{C}\) will still not impact the clean distribution), the outcomes of learners trained on clean samples from the distribution will not change (including the most data-efficient learner) and hence \(n\) will remain the same for different permissible choices of \(\mathcal{C}\), indicating that the vulnerability of the same dataset remains the same even when \(\mathcal{C}\) changes drastically without impacting the clean distribution. However, changes in \(\mathcal{C}\) (and subsequently changes in the projected constraint size) will directly impact the attack effectiveness, as a larger \(\mathcal{C}\) is likely to admit stronger poisoning attacks. To illustrate how much the attack power can change as \(\mathcal{C}\) changes, we conduct experiments on MNIST 1–7 and show that scaling up the original dimension-wise box-constraint from \([0, 1]\) to \([0, c]\) (where \(c>1\) is the scale factor) can significantly boost attack effectiveness. 11 summarizes the results and we can observe that, as the scale factor \(c\) increases (enlarged \(\mathcal{C}\), increased projected constraint size and reduced Sep/Size), the attack effectiveness also increases significantly. Note that this experiment is an existence proof and MNIST 1–7 is used as a hypothetical example. In practice, for normalized images, the box constraint cannot be scaled beyond [0,1] as it will result in invalid images.

13.2 Relation to Aggregation-based Defenses↩︎

Aggregation-based (provable) defenses, whose asymptotic optimality is implied by the LDC, work by partitioning the potentially poisoned data into \(k\) partitions, training a base learner on each partition and using majority voting to obtain the final predictions. These defenses provide certified robustness to poisoning attacks by giving the maximum number of poisoning points that can be tolerated to correctly predict a known test point, which can also be straightforwardly applied to indiscriminate setting by treating different test samples independently, as mentioned in the discussion of LDC.

Because no data filtering is used for each partition of the defenses, at the partition level, our results (i.e., the computed metrics) obtained in each poisoned partition may still be similar to the results obtained on the whole data without partition (i.e., standard training, as in this paper), as the clean data and \(\mathcal{C}\) (reflected through the poisoning points assigned in each partition) may be more or less the same. At the aggregation level, similar to the discussion on LDC, these aggregation defenses may still result in overly pessimistic estimates on the effectiveness of injection only indiscriminate poisoning attacks as the certified accuracy at a particular poisoning ratio can be very loose, and the two possible reasons are: 1) straightforwardly applying results in targeted poisoning to indiscriminate poisoning might lead to overestimation and 2) considering the worst case adversary of modifying points might overestimate the power of injection only attacks in each poisoned partition. Therefore, our work can be related to aggregation defenses via reason 2), as it might be interpreted as the first step towards identifying factors that impact the attack effectiveness of injection only indiscriminate attacks in each poisoned partition, which may not always be highly detrimental depending on the learning task properties in each partition, while these aggregation defenses assume the existence of a single poisoning point in a partition can make the model in that partition successfully poisoned.

Given a poisoning budget \(\epsilon\), aggregation based defenses give a certified accuracy against indiscriminate poisoning attacks by first computing the tolerable fraction of poisoning points for each test sample and all the test samples with tolerable fraction smaller than or equal to \(\epsilon\) are certifiably robust. Then, the fraction of those test samples to the total test samples gives the certified accuracy for the test set. Similar to the result of CIFAR10 shown in LDC, here, we provide an additional result of certified accuracy for neural networks trained on the MNIST dataset: the state-of-the-art finite aggregation (FA) method [54] gives a certified accuracy of 0% at 1% poisoning ratio (600/60,000) using \(k=1200\) partitions while at the much higher 3% poisoning ratio, the current state-of-the-art indiscriminate poisoning attack [34] can only reduce the accuracy of the neural network trained on MNIST without partitioning (i.e., \(k=1\), a far less optimal choice from the perspective of aggregation defenses) from over 99% to only around 90%.

14 Extension to Multi-class Settings and Non-linear Learners↩︎

In this section, we first provide the high-level idea of extending the metric computation from binary setting to multi-class setting and then provide empirical results on multi-class linear models and show that these metrics can still well-explain the observations in multi-class linear classifiers (14.1). Then, we provide the idea of extending the metrics from linear models to neural networks (NNs) and also the accompanying experimental results (14.2). In particular, we find that, for the same learner (e.g., same or similar NN architecture), our metrics may still be able to explain the different dataset vulnerabilities. However, the extended metrics cannot explain the vulnerabilities of datasets that are under different learners (e.g., NN with significantly different architectures), whose investigation is a very interesting future work, but is out of the scope of this paper.

14.1 Extension to Multi-class Linear Learners↩︎

Multi-class classifications are very common in practice and therefore, it is important to extend the computation of the metrics from binary classification to multi-class classification. For linear models, \(k\)-class classification (\(k>2\)) is handled by treating it as binary classifications in the "one vs one" mode that results \(k(k-1)/2\) binary problems by enumerating over every pair of classes or in the "one vs rest" mode that results in \(k\) binary problems by picking one class as the positive class and the rest as the negative class. In practice, the "one vs rest" mode is preferred because it requires training smaller number of classifiers. In addition, the last classification layer of neural networks may also be roughly viewed as performing multi-class classification in “one vs rest" mode. Therefore, we only discuss and experiment with multi-class linear models trained in”one vs rest" mode in this section, consistent with the models in prior poisoning attacks [10], [34], but classifiers trained in “one vs one" mode can also be handled similarly.

Although we consider linear models in “one vs rest" mode, when computing the metrics, we handle it in a way similar to the”one vs one" mode – when computing the metrics, given a positive class, we do not treat all the remaining k-1 classes (constitute the negative class) as a whole, instead, for each class in the remaining classes, we treat it as a “fake" negative class and compute the metrics as in the binary classification setting. Then from the \(k-1\) metrics computed, we pick the positive and”fake" negative pair with smallest separability metric and use it as the metric for the current positive and negative class (includes all remaining \(k-1\) classes)². Once we compute the metrics for all the \(k\) binary pairs, we report the lowest metrics obtained. The reasoning behind computing the metrics in (similar to) “one vs one" mode is, for a given positive class, adversaries may target the most vulnerable pair from the total \(k-1\) (positive, negative) pairs to cause more damage using the poisoning budget. Therefore, treating the remaining \(k-1\) pairs as a whole when computing the metrics will obfuscate this observation and may not fully reflect the poisoning vulnerabilities of a dataset.

We provide a concrete example on how treating the remaining classes as a whole can lead to wrong estimates on the dataset separability: we first train simple CNN models on the full CIFAR-10 [55] and MNIST datasets and achieve models with test accuracies of \(\approx 70\%\) and \(>99\%\) respectively. When we feed the MNIST and CIFAR-10 test data through the model and inspect the feature representations, the t-SNE graph indicate that the CIFAR-10 dataset is far less separable than the MNIST, which is expected as CIFAR-10 has much lower test accuracy compared to MNIST. However, when we compute the separability metrics in our paper by considering all \(k-1\) classes in the negative class, the separability of CIFAR-10 is similar to the separability of MNIST, which is inconsistent with drastic differences in the test accuracies of the respective CNN models. In contrast, if we treat each class in the remaining \(k-1\) classes separately and pick the smallest value, we will again see the expected result that CIFAR-10 is far less separable than MNIST. Therefore, for the following experiments, we will compute the metrics by treating the remaining \(k-1\) classes individually. We first provide the results of multi-class linear models for MNIST dataset below and then discuss our initial findings on the neural networks for CIFAR-10 and MNIST in 14.2.

As explained above, when checking the \(k\)-binary pairs for a \(k\)-class problem, we report the lowest values for the Sep/SD and Sep/Size metrics. However, in some cases, the lowest values for the two metrics might be in two different pairs and in this case, we will report the results of both pairs. Table 12 summarizes the results, where the poisoned errors are directly quoted from the prior works—LR error is from Lu et al. [11] and the SVM error is from Koh et al. [10]. We can see that MNIST dataset is indeed more vulnerable than the selected MNIST 1–7 and MNIST 6–9 pairs because it is less separable and also impacted more by the poisoning points. We also note that the poisoned error of SVM is obtained in the presence of data sanitization defenses and hence, the poisoned error may be further increased when there are no additional defenses. We also see that, for SVM, although the lowest values for Sep/SD and Sep/Size are in two different pairs, their results do not differ much, indicating that either of them can be used to represent the overall vulnerability of MNIST.

14.2 Extension to Multi-class Neural Networks↩︎

We first note that the insights regarding the separability and constraints set \(\mathcal{C}\) can be general, as the the first metric measures the sensitivity of the dataset against misclassification when the decision boundary is perturbed slightly. The latter captures how much the decision boundary can be moved by the poisoning points once injected into the clean training data. The Sep/SD and Sep/Size metrics used in this paper are the concrete substantiations of the two metrics under linear models. Specific ways to compute the metrics in non-linear settings should still (approximately) reflect the high level idea above. Below, we use neural network (NN) as an example.

We may partition the neural network into two parts of feature extractor and linear classification module and we may view the feature representations of the input data as a "new" data in the corresponding feature space, and so that we can convert the metric computations for non-linear neural network into metric computations (on feature space) for linear models. To be more concrete, we propose to use a fixed feature extractor, which can be extractors inherited from pretrained models (e.g., in transfer learning setting) or trained from scratch on the clean data, to map the input data to the feature space. Here, if the victim also uses the same pretrained feature extractor (as in the transfer learning setting), then our metrics can have higher correlation with the poisoned errors from existing attacks because the non-linear feature extractor is now independent from the poisoned points used in the victim’s training. Below, we consider the from-scratch training case as it is more challenging.

Although the feature extractor will also be impacted by the poisoning points now, in our preliminary experiment, we will still use the extractor trained on the clean data and leave the exploration of other better feature extractors as future work. Using the transformation from the clean feature extractor, the projected separability and standard deviation can be easily computed. But the computation of the projected constraint size can be tricky, because the set \(\mathcal{C}\) after transforming through the feature extractor can be non-convex and sometimes, for complicated \(\mathcal{C}\), computing such transformation can be very challenging (can be a case even for linear models), but is a very interesting direction to explore. For the simple forms of \(\mathcal{C}\) such as the dimension-wise box constraints considered in this paper, we may leverage the convex outer polytope method [56] to bound the activation in each layer till the final feature layer so that we can obtain a final transformed convex set \(\mathcal{C}^{'}\) using the feature extractor, which is a set that contains the original \(\mathcal{C}\). However, due to time limitation, when computing the projected constraint size in the following experiments, we simply set \(\mathcal{C}\) as the dimension-wise box-constraints, whose minimum and maximum values are computed from the feature representations of the clean data points, similar to the transfer-learning experiment in 7.

For the experiments, we use the simple CNN models presented in Lu et al. [11] for MNIST and CIFAR-10 datasets (similar architecture). We directly quote the attack results of TGDA attack by Lu et al. [11] for both the CIFAR-10 and MNIST datasets. Note that, very recently, a stronger GC attack is also proposed by Lu et al. [34] and outperforms the TGDA attack. However, we could not include the newer result because the code is not published and the evaluation in the original paper also did not include the simple CNN for CIFAR-10 dataset. The results are shown in Table 13. From the table, we can see that CIFAR-10 tends to be more vulnerable than MNIST as the Sep/SD and Sep/Size metrics (in neural networks) are all much lower than those of MNIST. These significantly lower values of CIFAR-10 may also suggest that the poisoned error for CIFAR-10 with simple CNN maybe increased further (e.g., using the stronger attack in Lu et al. [34]).

Above, we only showed results when the MNIST and CIFAR-10 datasets are compared under similar learners. However, in practical applications, one might use deeper architecture for CIFAR-10 and so, we computed the metrics for CIFAR-10 using ResNet18 model. Then we compare the metrics of MNIST under simple CNN and the metrics of CIFAR-10 under ResNet18 in Table 14, where the poisoned errors are quoted from the more recent GC attack [34] because the attack results are all available in the original paper. However, from the table we can see that, although MNIST is less separable and impacted more by the poisoning points, the error increase is still slightly smaller than CIFAR-10, which is not consistent with our metrics. If the current attacks are already performing well and the empirical poisoned errors are indeed good approximations to the inherent vulnerabilities, then we might have to systematically investigate the comparison of vulnerabilities of different datasets under different learners.

15 Evaluation on Synthetic Datasets↩︎

In this section, we empirically test our theory on synthetic datasets that are sampled from the considered theoretical distributions in 5.1.

15.1 Synthetic Datasets↩︎

According to Remark 6, there are two important factors to be considered: (1) the ratio between class separability and within-class variance \(|\gamma_1-\gamma_2|/\sigma\), denoted by \(\beta\) for simplicity; (2) the size of constraint set \(u\). We conduct synthetic experiments in this section to study the effect of these factors on the performance of (optimal) data poisoning attacks.

More specifically, we generate 10,000 training and 10,000 testing data points according to the Gaussian mixture model 2 with negative center \(\gamma_1=-10\) and positive center \(\gamma_2=0\). Throughout our experiments, \(\gamma_1\) and \(\gamma_2\) are kept fixed, whereas we vary the variance parameter \(\sigma\) and the value of \(u\). The default value of \(u\) is set as \(20\) if not specified. Evaluations of empirical poisoning attacks require training linear SVM models, where we choose \(\lambda=0.01\). The poisoning ratio is still set as \(3\%\), consistent with evaluations on the benchmark datasets.

First, we show how the optimal attack performance changes as we increase the value of \(\beta\). We report the risk achieved by the OPT attack based on Theorem 5. Note that we can only obtain approximations of the inverse function \(g^{-1}\) using numerical methods, which may induce a small approximation error for evaluating the optimal attack performance. For the finite-sample setting, we also report the empirical test error of the poisoned models induced by the empirical OPT attack and the best current poisoning attack discussed in 3, where the latter is termed as Best Heuristic for simplicity. Since the poisoned models induced by these empirical attacks do not restrict \(w\in\{-1, 1\}\), we normalize \(w\) to make the empirical results comparable with our theoretical results.

6 summarizes the attack performance when we vary \(\beta\). As the ratio between class separability and within-class variance increases, the risk of the OPT attack and empirical test errors of empirical OPT and best heuristic attacks gradually decrease. This is consistent with our theoretical results discussed in Section 5.1. Note that there exists a minor difference between these attacks when the value of \(\beta\) is small, where the test error attained by the best current heuristic poisoning attack is slightly higher than that achieved by the empirical OPT attack. This is due to the small numerical error induced by approximating the inverse function \(g^{-1}\).

Our theoretical results assume the setting where \(w\in\{-1, 1\}\). However, this restriction makes the impact of the constraint set size \(u\) less significant, as it is only helpful in judging whether flipping the sign of \(w\) is feasible and becomes irrelevant to the maximum risk after poisoning when flipping is infeasible. In contrast, if \(w\) is not restricted, the impact of \(u\) will be more significant as larger \(u\) tends to reduce the value of \(w\), which in turn makes the original clean data even closer to each other and slight changes in the decision boundary can induce higher risks (further discussions on this are found in 15.2).

To illustrate the impact of \(u\) in a continuous way, we allow \(w\) to take real numbers. Since this relaxation violates the assumption of our theory, the maximum risk after poisoning can no longer be characterized based on Theorem 5. Instead, we use the poisoning attack inspired by our theory to get an empirical lower bound on the maximum risk. Since \(\gamma_1+\gamma_2<0\), Theorem 5 suggests that optimal poisoning should place all poisoning points on \(u\) with label \(-1\) when \(w\in\{1,-1\}\). We simply use this approach even when \(w\) can now take arbitrary values. We vary the value of \(u\) gradually and record the test error of the induced hypothesis, We repeat this procedure for different dataset configurations (i.e., fixing \(\gamma_1\), \(\gamma_2\) and varying \(\sigma\)).

The results are summarized in Figure 7. There are two key observations: (1) once \(w\) is no longer constrained, if \(u\) is large enough, the vulnerability of all the considered distributions gradually increases as we increase the value of \(u\), and (2) datasets with smaller \(\beta\) are more vulnerable with the increased value of \(u\) compared to ones with larger \(\beta\), which has larger increased test error under the same class separability and box constraint (choosing other values of \(\beta\) also reveals a similar trend). Although not backed by our theory, it makes sense as smaller \(\beta\) also means more points might be closer to the boundary (small margin) and hence small changes in the decision boundary can have significantly increased test errors.

15.2 Relationship Between Box Constraint Size and Model Weight↩︎

Our theory assumes that the weight vector of \(w\) can only take normalized value from \(\{-1, 1\}\) for one-dimensional case, while in practical machine learning applications, convex models are trained by optimizing the hinge loss with respect to both parameters \(w\) and \(b\), which can result in \(w\) as a real number. And when \(w\) takes real numbers, the impact of \(u\) becomes smoother: when poisoning with larger \(u\), the poisoning points generated can be very extreme and forces the poisoned model to have reduced \(w\) (compared to clean model \(w_c\)) in the norm so as to minimize the large loss introduced by the extreme points. Figure 8 plots the relationship between \(u\) and \(w\) of poisoned model, and supports the statement above. When the norm of \(w\) becomes smaller, the original clean data that are well-separated also becomes less separable so that slight movement in the decision boundary can cause significantly increased test errors. This makes the existence of datasets that have large risk gap before and after poisoning more likely, which is demonstrated in Figure 7.

References↩︎