What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?
Authors: Fnu Suya
Xiao Zhang
Yuan Tian
David Evans
Venue: NeurIPS 2023 poster (2023)
Keywords: poisoning attacks; adversarial machine learning; machine learning security
TL;DR: we explain why linear learners show drastic vulnerabilities to best poisoning attacks across benchmark datasets.

Abstract: We study indiscriminate poisoning for linear learners where an adversary injects a few  crafted examples into the training data with the goal of forcing the induced model to incur higher test error. Inspired by the observation that linear learners on some datasets are able to resist the best known attacks even without any defenses, we further investigate whether datasets can be inherently robust to indiscriminate poisoning attacks for linear learners. For theoretical Gaussian distributions, we rigorously characterize the behavior of an optimal poisoning attack, defined as the poisoning strategy that attains the maximum risk of the induced model at a given poisoning budget. Our results prove that linear learners can indeed be robust to indiscriminate poisoning if the class-wise data distributions are well-separated with low variance and the size of the constraint set containing all permissible poisoning points is also small. These findings largely explain the drastic variation in empirical attack performance of the state-of-the-art poisoning attacks on linear learners across benchmark datasets, making an important initial step towards understanding the underlying reasons some learning tasks are vulnerable to data poisoning attacks.

What Distributions are Robust to Indiscriminate Poisoning Attacks for Linear Learners?
Fnu Suya' Xiao Zhang? Yuan Tian
David Evans!
University of Virginia
*CISPA Helmholtz Center for Information Security
University California Los Angeles
suya@virginia edu, xiao. wwwngacispa..eee...oooooo.a @ua conntuuclaa edu, evans@virginia..dd
Abstract
We study indiscriminate poisoning for linear learners where adversary injects few crafted examples into the training data with the goal of forcing the induced model to incur higher test error. Inspired by the observation that linear learners on some datasets are able to resist the best known attacks even without any defenses, we further investigate whether datasets be inherently robust to indiscriminate poisoning attacks for linear learners. For theoretical Gaussian distributions, we rigorously characterize the behavior of optimal poisoning attack, defined the poisoning strategy that attains the maximum risk of the induced model at a given poisoning budget. Our results prove that linear learners indiscriminate poisoning if the class-wise data distributions are well-separated with low variance and the size of the constraint set containing all permissible poisoning points is also small. These findings largely explain the drastic variation in empirical attack performance of the state-of-the-an poisoning attacks on linear learners across benchmark datasets, making an important initial step towards understanding the underlying reasons some learning tasks are vulnerable to data poisoning attacks.
indeed be robust
Introduction
Machine learning models, especially current large-scale models, require large amounts of labeled training data, which are often collected from untrusted third parties [6]. 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. this setting, spammers can generate spam messages that inject benign words likely to occur in spam emails such that models trained these spam messages will incur significant drops in filtering accuracy as benign and malicious messages become indistinguishable [37, 20]. These kinds of attacks are known poisoning attacks. In 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 way that satisfies certain attacker goals.
One commonly studied poisoning attacks in the literature are indiscriminate poisoning attacks [4, 54, 35, 45, 5, 46, 25, 31, 10]. 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 [42, 56, 24, 21, 18] and subpopulation [22, 46) 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 [45, 25], but include 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 poi- soning attacks in many settings [45, 46, 25, 31], but these works do not explain why the proposed attacks are sometimes ineffective. In addition, the evaluations of these attacks can be deficient in
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

some aspects [3, 4, 45, 25,31] (see Section 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 the increased error (or risk in the distributional sense) from poisoning exceeds the injected poisoning ratio 25].
In this paper, we consider indiscriminate data poisoning attacks for linear models, the commonly studied victim models in the literature [3, 4, 24, 45, 10J. Attacks on linear models are also studied very recently [46, 25, 5, 9] 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 [30, 39]. Linear models also achieve competitive performance in many security-critice applications for which poisoning is relevant, including training with differential privacy [49], recommendation systems [15] and malware detection [7, 8, 41, 11, 44, 2]. From a practical perspective, linear models continue to be relevant-forr for example, Amazon SageMaker [1], 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.
Contributions. 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 (Section 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 (Figure 1). To understand whether this observation means such datasets are inherently robust to poisoning attacks or just that state-of-thh oh-the-art attacks are suboptimal, we first introduce general definitions of optimal poisoning attacks for both finite-sampl and distributional settings (Definitions 4.1 and 4.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 4.3), and the best poisoning performance is always achieved at the maximum allowable poisoning ratio under mild conditions (Theorem 4.5).
Building upon these definitions, we rigorously characterize the behavior of optimal poisoning attacks under theoretical Gaussian mixture model (Theorem 5.3), and derive upper bounds on their effec- tiveness for general data distributions (Theorem 5.7). In particular, we discover that a larger projected constraint size (Definition 5.5) is associated with a higher inherent vulnerability, whereas projected data distributions with a larger separability and smaller standard deviation (Definition 5.6) are fun- damentally less vulnerable to poisoning attacks (Section 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 (Section 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 (c.g., data sanitization defenses) to limit the impact of poisoning points (Section 7).
Related Work. Several prior works developed indiscriminate poisoning attacks by injecting a small fraction of poisoning points. One line of research adopts iterative gradient- methods to directly maximize the surrogate loss chosen by the victim [3, 35, 34, 24), leveraging the idea of influence functions [40]. Another approach bases attacks on convex optimization methods [45, 46, 25]. which provide 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 [31, 32]. All the aforementioned works focus on developing different indiscriminate poisoning algorithms and some also characterize the hardness of poisoning in the model-targeted setting [46, 32), 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 [19, 55, 16] and some of them, similar to us, first rigorously analyze poisoning on thcoretical distributions and then generalize the insights to general distributions [48, 47).
2

---

Although much research focuses on indiscriminate poisoning, many realistic attack goals are better captured as targeted attacks [42. 56, 24, 21, 18], where the adversary's goal is induce model that misclassifies particular known instance, or subpopulation attacks [22, 46], where the adversary's goal is to produce misclassifications for a defined subset of the distribution. recent work that studies the inherent vulnerabilittis of datasets to targeted data poisoning attacks proposed the Lethal Dose Conjecture (LDC) [50]: given a dataset of size N, the tolerable amount of poisoning points from any targeted poisoning attack generated through insertion, deletion or modifications is (N//n). where n is the sample complexity of the most data-efficient learner trained on the clean data to correctly predict 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 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 particular attack scenario to better understand the power of indiscriminate data poisoning attacks. Appendix E provides more details.
2 Preliminaries
We consider binary classification tasks. Let C R be the input space and - ( [-1,+1] be the label space. Let Me be the joint distribution of clean inputs and labels. For standard classification tasks, the goal is to learn a hypothesis h X² y that minimizes Risk(h; j4e P (m..)))) [h(z)) * v] Instead of directly minimizing risk, typical machine learning methods find an approximately good hypothesis by restricting the search space to a specifie hypothesis class H. then optimizing by minimizing some convex surrogate loss: minnEH L(h; Me). In practical applications with only a finite number of samples, model training replaces the population mcasure He with its empirical counterpart. The surrogate loss for h is defined as (hh; μ4) (/) [e(h; x. v)]. where ((h; æ v) denotes the non-negative individual loss of h incurred at (z.
We focus on the linear hypothesis class and study the commonly considered hinge loss in prior poisoning literature [3. 4, 45, 25, 46) when deriving the optimal attacks for I-D Gaussian distributions in Section 5. Our results can be extended to other linear methods such logistic regression (LR). A linear hypothesis parameterized by weight parameter w E R" and bias parameter b E R is defined as: f (ln,((()) (z) = sgn(w" x + b) for any æ RT, where sgn(-) denotes the sign function. For any x E X' and y E y. the hinge loss of a linear classifier hw b is defined as:
E(hmm, 2t, y) = max (0, 1 - y(w T x + b)) + 2
1 12
where A 2 0 is the tuning parameter which penalizes the f--norm of the weight parameter w.
Threat Model. We formulate indiscriminate data poisoning attack as a game between an attacker and a victim in practice following the prior work [45]:
1. A clean training dataset S, is produced, where each data point is i.i.d. sampled from pe-
2. The attacker generates a poisoned dataset S, using some poisoning strategy A, which aims to reduce the performance of the victim model by injecting Sp into the training dataset.
3. The victim minimizes empirical surrogate loss L(-) S. U.S. and produces model hn-
The attacker's ' goal is to find a poisoning strategy A such that the risk of the final induced classifier Risk(hp; (e) is as high as possible, which is empirically estimated on a set of fresh testing data that are i.i.d. sampled from Me- We assume the attacker has full knowledge of the learning process, including the clean distribution Me or the clean training dataset S., the hypothesis class H. the surrogate loss function E and the learning algorithm adopted by the vietim.
We impose two restrictions to the poisoning attack: |Spl S [S.l and Sp C, where c E [0. 1] is the poisoning budget and C C X' x y is a bounded subset that captures the feasibility constraints for poisoned data. We assume that C is specified 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 Fuclidean distance from center will be removed) [45, 25). Here, we focus on undefended victim models, i..., C is specified based on application constraints, so
3

---

Test Error (%)
Trained on S: Trained on S; u Sp
20
Filtered Enron MNIST6-9
Dogfish
MNISTI-7
Enron
MNIST4-9
Adult
Figure 1: Performance of best current indiscriminate poisoning attacks with c 3% across different benchmark datasets on linear SVM. Datasets are sorted from lowest to highest base error rate.
as to better assess the inherent dataset vulnerabilities without active protections. However, defense strategies such as data sanititation [12, 45, 25] may shrink the size of C so that the poisoned data are less extreme and harmful. We provide preliminary experimental results on this Section 7.
3 Disparate Poisoning Vulnerability of Benchmark Datasets
Prior evaluations of poisoning attacks 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 [3, 10, 34, 35], generating invalid poisoning points [45, 25] lacking diversity in the evaluated convex models/datasets [31, 32). This motivates us to carefully evaluate representative attacks for linear models various benchmark datasets without considering additional defenses.
Experimental Setup. We evaluate the state-of-the-ard data poisoning attacks for linear models: Influence Attack [24, 25], KKT Attack [25], Min-Max Attack [45, 25], and Model-Targetes Attack (MTA) [46]. We consider both linear SVM and LR models and evaluate the models on benchmark datasets including different MNIST [28] digit pairs (MNIST 1-7, as used in prior evaluations [45, 25, 3, 46), 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 [24), Enron [36] and Adult [22, 46). 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 (Section 6). We choose 3% as the poisoning rate following previous works [45, 25, 31, 32). Appendix D.1 provides details on the experimental setup.
Results. Figure 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 Appendix D.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 (R: 9% increased error) while Enron and Filtered Enron are highly vulnerable with over 30% of increased error. Consistent with prior work [45, 25, 32], throughout this paper, we measure the increased error to determine whether 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 drastic difference in robustness of benchmark datasets state-of-the-a 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, first characterize optimal poisoning attacks for theoretical distributions and then study their partial characteristics for general distributions in Section
4 Defining Optimal Poisoning Attacks
In this section, we lay formal definitions of optimal poisoning attacks and study their general implications. First, we introduce a notion of finite fimite-sample optimal poisoning to formally define the optimal poisoning attack in the practical finite-sample setting with respect our threat model:

---

Definition 4.1 Saniiee--eeleeeeee Optimal Poisoning). Consider input space X' and label space y. Let Me be the underlying data distribution of clean inputs and labels. Let S. be a set of examples sampled i...d. from Me- Suppose H is the hypothesis class and l is the surrogate loss function that are used for learning. For any 0 and C S X x V. finite-sample optimal poisoning adversary Aopt is defined to be able to generate some poisoned dataset Sp such that:
Sp - arginx Risk(hpi s.t. Sp C C and |S s (Sa),
Sy
where hp argminge E(a,)ssuss, ((1; x,, x,, y) denotes the empirical loss minimizer.
Definition 4.1 states that poisoning strategy can achieve better attack performance than that achieved by Aope. If we denote by hū the hypothesis produced by minimizing the empirical loss S, U. then Risk(h); po) can be regarded as the maximum achievable attack performance.
Next, we introduce more theoretical notion of distributional optimal poisoning, which generalizes Definition 4.1 from sinte-sample datasets to data distributions.
Definition 4.2 (Distributional Optimal Poisoning). Consider the same setting as in Definition 1. distributional optimal poisoning adversary Aopt is defined to be able to generate some poisoned data distribution s such that:
(n 5") = argmax Risk(hpipee) s.t. supp(pp) S C and 0 S 5556 (Kp,5)
where hp = argmin pc) + Lhh; [p)} denotes the population loss minimizer.
Similar to the finite-saple case, Definition 4.2 implies that there is feasible poisoned distribution Hp such that the risk of its induced hypothesis is higher than that attained by M.- Theorem 4.3, proven in Appendix A.I, connects Definition 4.1 and Definition 4.2. The formal definitions of uniform convergence, strong convexity and Lipschitz continuity are given in Appendix A.I.
Theorem 4.3. Consider the same settings as in Definitions 4.1 and 4.2. Suppose H. satisfies the uniform convergence property with function m Assume is b-strongly convex and Risk(h; He) is p- p-Lipschitz continuous with respect to model parameters for some b, > 0. Let (L:
hū = argminkeи E(E.))sssss; E(h; xr v) and hū = argminnent [[h; + I[hh; (g)). For any é', 8' E (0, if Sel 2 mm(e', 8"), then with probability at least 1- 8',
Risk(h);:p.) Risk(hi; pa)1 S 201 /
Remark 4.4. Theorem 4.3 assumes three regularity conditions to ensure the finite-sample optimal poisoning attack is consistent estimator of the distributional optimal one (i.e., insights poisoning from distributional settings can transfer to finite-sample settings): the uniform convergence property of H that guarantees empirical minimization of surrogate loss returns good hypothesis, the strong convexity condition that ensures a unique loss minimizer, and the Lipschitz condition that translates the closeness of model parameters the closeness of risk. These conditions hold for most (properly regularized) convex problems and input distributions with bounded densities. The asymptotic convergence rate is determined by the function mz, which depends on the complexity of the hypothesis class H and the surrogate loss f. For instance, if we choose À carefully, sample complexity of the linear hypothesis class for bounded hinge loss is (2)1(cc))), where é' is the error bound parameter for specifying the uniform convergence property (see Definition A.3) and other problem- dependent parameters are hidden in the big-S2 notation (see Section 15 of [43] for details). We note the generalization of optimal poisoning attack for linear case is related to agnostic learning of halfspaces [23), which also imposes assumptions on the underlying distribution such as anti-coneentration assumption [13, 17] similar to the Lipschitz continuity condition assumed in Theorem 4.3. The theorem applies to any loss function that strongly convex (e.g.. general convex losses with the 6 or elastic net regularizers), not just the hinge loss.
Moreover, we note that 8* represents the ratio of injected poisoned data that achieves the optimal attack performance. In general, 8 can be any value [0, <), but we show in Theorem 4.5, proven in Appendix A.2, that optimal poisoning can always be achieved with e-poisoning under mild conditions.
5

---

Theorem 4.5. The optimal poisoning attack performance defined in Definition 4.2 can always be achieved by choosing as the poisoning ratio, if either of the following conditions is satisfied:
1. The support of the clean distribution supp(pe) C C.
2. H is convex hypothesis class, and for any hg H. there always exists distribution j such that supp(p) _ C and 8 L(he: (1) = 0.
Bp
Remark 4.6. Theorem 4.5 characterizes the conditions under which the optimal performance is guar- anteed to be achieved with the maximum poisoning ratio e. Note that the first condition supp(ue) S C mild because typically holds for poisoning attacks against undefended classifiers. When attacking classifiers that employ some defenses such as data sanitization, the condition supp(ue) S C might not hold, due to the fact that the proposed defense may falsely reject some clean data points as outliers (i.e., related to false positive rates). The second condition complements the first one in that it does not require the victim model to be undefended, however, it requires to be convex. We prove in Appendix A.3 that for linear hypothesis with hinge loss, such μ can be easily constructed. The theorem enables us to conveniently characterize the optimal poisoning attacks in Section 5.1 by directly using When the required conditions are satisfied, this theorem also provides simple sanity check on whether a poisoning attack is optimal. In particular, if a candidate attack is optimal, the risk of the induced model is monotonically non-decreasing with respect to the poisoning ratio. Note that the theorem above applies to any strongly convex loss function.
5 Characterizing Optimal Poisoning Attacks
This section characterizes the distributional optimal poisoning attacks with respect to linear hypothesis class. We first consider a theoretical I-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-Dimeniional Gaussian Mixtures
Consider binary classification tasks using hinge loss with one-dimensional inputs, where X' = R
and y = (-1,+1) Let He be the underlying clean data distribution, where each example (xx y) is assumed to be i..d. sampled according to the following Gaussian mixture model:
{
with probability y = +1,x ((22, o2) with probability 1-P.
= - 1,, ~ N(n, of)
(2)
where 01,02 > O and p (0, 1). Without loss of generality, we assume ?1 7/2- Following
our threat model, we let c 2 0 be the maximum poisoning ratio and C : [-u, u| x y for some
[J be the linear hypothesis class be the constraint set. Let Hr. (kwwb w E {-1,1),
with normalized weights. Note that we consider a simplified setting where the weight parameter ||w||2 is fixed, we also set > 0 in the hinge loss function (1).
E 1), Since
For clarify in presentation, we outline the connection between the defimitions and the main theorem below, which will also show the high-level proof sketch of Theorem 5.3. We first prove that in order to understand the optimal poisoning attacks, it is sufficient to study the family two-point distributions (Definition 5.1), instead of any possible distributions, as the poisoned data distribution. Based on this reduction and a specification of weight flipping condition (Definition 5.2), we then rigorously characterize the optimal attack performance with respect to different configurations of task-related parameters (Theorem 5.3). Similar conclusions may also be made with logistic loss.
Definition 5.1 (Two-point Distribution). For any E [0. 1]. Po is defined as a two-point distribution, if for any (z, 3) sampled from Va.
(-u, +1) (u, -1)
with probability a, with probability 1 1 a.
(x,, v) =
'Characterizing the optimal poisoning attack under the general setting of w E IR is more challenging, since we need to consider the effect of any possible choice of w and its interplay with the dataset and constraint set factors. We leave the theoretical analyses of w E R. to future work.

---

Definition 5.2 the linear hypothesis class H.,.- Let g be an auxiliary function such that for any E I,
Condition). Consider the assumed Gaussian mixture model (2) and
1 7 Φb
m
1 2
(
g (b)
where & is the cumulative distribution function (CDF) of standard Gaussian WNO, 1). Let e 0 be the poisoning budget and g be the inverse of 9, then the weight-flipping condition is defined as:
max(A(-<)) A(o())), (()) 2 0,
where (s)) = [(h1.0-(0)))11 - mingeR L(h-1,6:: 14) + c.
(s).
Now we are ready to present our main theoretical results. The following theorem rigorously char- acterizes the behavior of the distributional optimal poisoning adversary Aopt under the Gaussian mixture model (2) and the corresponding optimal attack performance:
Theorem 5.3. Suppose the clean distribution pr. follows the Gaussian mixture model (2) with p = 1/2.
71 S. 7/2, and 01 02 = a. Assume u 2 1 and Iy1 + +2 < 2(u - There always exists some a E [0, 1] such that the optimal attack performance defined in Definition 4.2 is achieved with 6 e and
My = Vo, where Va is defined by (3). More specifically, if hf; = argmin {L(h; te-
denotes the induced hypothesis with optimal poisoning, then
4b (22-71)
if condition (4) is satisfied. otherwise,
Risk(h ue) { 1
20
91
12
+ 1 20 (06)))
2x
where s = max
(c) (c) Remark 5.4. The proof of Theorem 5.3 is given in Appendix B.I. We considered same variance of T1 = 02 = a simply for the convenience in proof without involving minor but tedious calculations, and the same conclusion can be made using different variances. Theorem 5.3 characterizes the exact behavior of Aopt for typical combinations of hyperparameters under the considered model, including distribution related parameters such as 7/1 72. 0 and poisoning related parameters such as E, u. We use directly because the poisoning setup in the 1-D Gaussian distribution satisfies the second condition in Theorem 4.5. Hence, the best performance can be achieved with the maximum poisoning ratio e. For u, a larger of it suggests the weight-flipping condition (4) is more likely to be satisfied, as attacker can generate poisoned data with larger hinge loss to flip the weight parameter w. Class separability in - ?2l and within-class variance a also play an important role in affecting the optimal attack performance. If the ratio 1 - 72l/0 / is large, then we know the initial risk Risk(hei me) (22 (2) will be small. Consider the case where condition (4) is satisfied. Note that ( ((>==))
(0), (0((0)0))) - g-'((e)) and g(-) is defined in Definition 5.2.
@ (2 implies an improved performance of optimal poisoning attack thus an higher inherent vulnerabilities to data poisoning attacks. However, it is worth noting that there is an implicit assumption in condition (4) that the weight parameter can be flipped from w = 1 to = -1. A large value of h7 y2l/or also implies that flipping the weight parameter becomes more difficult, since the gap between the hinge loss with respect to He for a hypothesis with w = - and that with w becomes larger. Moreover, if condition (4) cannot be satisfied, then larger ratio of /n1 - 722//a suggests that it is more difficult to move the decision boundary to incur an increase in test error, because of the number of correctly classified boundary points will increase at faster rate. In summary, Theorem 5.3 suggests that a smaller value of u and a larger ratio of hi - r2l/a increases the inherent robustness to indiscriminate poisoning for typical configurations under model (2). Empirical verification of the above theoretical results is given in Appendix G.
=1 )===))=1--1
5.2 General Distributions
Recall that we have identified several key factors (i.c., 1/1 7/o and σT) for 1-D Gaussian distribu- tions Section 5.1 which are highly related to the performance of an optimal distributional poisoning adversary Aopt- In this section, we demonstrate how to generalize the definition of these factors to digh-dimensiooal 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 Me and the constraint set onto some vector w. then compute those factors based on the projections. Definition 5.5 (Projected Constraint Size). Let C C X x y be the constraint set for poisoning, For any u E TR.", the projected constraint size of C with respect to un is defined as:
Size (C)
max w x min w" x (a, CC
7

---

According to Definition 5.5, Size characterizes the size of the constraint set C when projected onto the (normalized) projection vector w/ w/||w|| then scaled by |//] the norm of w. In theory. the constraint sets conditioned on y = -1 and y 11 can be different, but for simplicity and practical considerations, we simply assume they are the same in the following discussions.
Definition 5.6 (Projected Separability and Standard Deviation). Let X C IR", ) = {-1, +1). and He be the underlying distribution. Let μr- and 44+ be the input distributions with labels of - and +1 respectively. For any w E IR,,, the projected separability of pe with respect w is defined as:
Sep (pe) = /Eve-a- [w x) Euway
[w [u]]]] æ=|
In addition, the projected standard deviation of tec with respect to w is defined as:
wD (Me) = (arw((e)) Varw (Me) = p- Varzwu [w Twoaa x] + p+ Var [w 2z].
where p- = Pr(a..))~uul ly = -1], p+ Pr(ma))~ue yy +1] denote the sampling probabilities.
For finite-sample settings, we simply replace the input distributions with their empirical counterparts to compute the sample statistics of Sep (Me) and SD (Do)..). 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 F for preliminary results). Below, we provide justifications on how the three factors are related to the optimal poisoning attacks. Theorem 5.7 and the techniques used in its proof in Appendix B.2 are inspired by the design of Min-Max Attack [45].
Theorem 5.7. Consider input space X C IR", label space y clean distribution Pe and linear hypothesis class H. For any hgg H. x E X and y E y, let bi I, y) = y x x+bb) be a margin-based based loss adopted by the victim, where f is convex and non non-decreasing. Let C C X x y be the constraint set and > be the poisoning budget. Suppose he argmin T.(h;; (c) has weight w. and b is the poisoned model induced by optimal adversary Aupt, then we have
Risk(h Mc) I min (e)) e [(x S L(hei e (Siiew NEH
(5)
Remark 5.8. Theorem 5.7 proves an upper bound on the inherent vulnerability to indiscriminate poisoning for linear learners, which can be regarded a necessary condition for the optimal poisoning attack. A smaller upper bound likely suggests a higher inherent robustness to poisoning attacks. In particular, the right hand side of (5) consists of two terms: the clean population loss of h2 and a term related to the projected constraint size. Intuitively, the projected separability and standard deviation metrics highly affect the first term, since data distribution with higher Sepw. (Me) and lower (1t) implies a larger averaged margin with respect to ht, which further suggests a smaller L The second term determined by the poisoning budget e and the projected constraint size, or more precisely, a larger e and larger Size (C) indicate higher upper bound on Risk pe). In addition, we set h hhe and the projection vector as w. for the last inequality of (5), because he achieves the smallest population surrogate loss with respect to the clean data distribution Mec However, choosing h = he may not always produce a tighter upper bound on Risk(h;;; me) since there is no guarantee that the projected constraint size Size (C) is small. An interesting future direction is to select more appropriate projection vector that returns a tight, if not the tightest, upper bound on Risk (hū; (te for any clean distribution Me (see Appendix D.2 for preliminary experiments). We also note that the results above apply to any (non-decreasing and strongly-conven margin-based losses.
6 Experiments
Recall from Theorem 4.3 and Remark 4.4 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 S., we empirically estimate the three distributional metrics defined in Section 5.2 on the clean test data with respect to the weight w.. Since ||wellz may vary across different datasets while the predictions of linear models (i.e., the classification error) are invariant to the scaling of ||w..||2 22, we use ratios to make their metrics comparable: Sep... (Me)/SD m. (Je)) (denoted as Sep/SD in Table 1) and Sep.. w. (Pe) (uee/Sizee /Sizee, (C) (Sep/Size). According to our theoretical results, expect datasets that are less vulnerable to poisoning have higher values for both metries.
8

---

Robust MNIST 1-7
Moderately Vulnerable MNIST 4-9
Highly Vulnerable F. Enron
Metric
MNIST 6-9
Adult
Dogfish
Enron
Error Increase
2.7
2.4
3.2
7.9
6.6
33.1
31.9
SVM Base Error
0.3
1.2
21.5
0.8
4.3
0.2
2.9
Sep/SD
6.92
6.25
9.65
5.14
4.44
1.18
1.18
Sep/Size
0.24
0.23
0.33
0,05
0.14
0.01
0.01
Error Increase
2.3
2.5
6.8
5.8
33.0
33.1
Base Error
0.6
20.1
5.1
0.3
2.5
LR
Sep/SD
6.28
6.13
4.62
5.03
4.31
1.11
1.10
Sep/Size
0.27
0.27
0.27
0.09
0.16
0.01
0.01
Explaining disparate poisoning vulnerability under linear models. The top row for each model gives the increase in error rate due to the poisoning. over the base error rate in the second row. The explanatory metrics are the scaled (projected) separability, standard deviation and constraint size.
Table 1:
Table 1 summarizes the results where Error Increase is produced by the best attacks from the state- of-the-art attacks mentioned in Section 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 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 it is for Adult, the empirical metries 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 w. test from test points in Table I and defer
points is more informative as (roughly) accounts for the (newly) induced misclassificatiio poisoning. Therefore, we report metrics based on correctly results of the whole test data to Appendix D.2. For datasets except Adult, both ways of computing the metries produce similar results. The Adult dataset very interesting that it is robust poisoning (i.e., small error increase) despite having a very high base error. As preliminary experiment, we also extended our analysis neural networks (Appendix F) 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 Section 5 characterize the relationship of these factors to the performance of optimal attacks exactly for I-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 (Appendix D.2.6). We leave the detailed exploration on their causal relationship 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 seeas--using data filtering might reduce projected constraint size and using better features might improve separability.
Reduced projected constraint size. 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 C. To test this, we picked the combination of Sphere and Slab defenses considered in prior works [25, 45] to protect the vulnerable Enron dataset. We find that with the defense, the test error 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 Size (C) (and hence a significantly higher Sep/Size) the Sep/Size metric jumps from 0.01 without defense to 0. 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 D.2.3).
Better feature representation. We consider a transfer learning scenario where the victim trains a linear model on clean pretrained model. As preliminary experiment, we train LeNet and R models on the CIFAR1O dataset till con- vergence, but record the intermediate mod- els of R8 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 CIFARIO im- ages with labels "Truck" and "Ship", and train linear models on them.
Error Increase (%)
R-100
6
0.35
R-120
5
SepiSize
R-90
4
0.25
0.20-
2
We evaluate the robustness of this dataset against poisoning attacks and set C as dimension-wise box-constraints, whose values are the minimum and maximum val- ues of the clean data points for each di- mension when fed to the feature extractors. This way of configuring C' corresponds to the practical scenario where the victim has access to some small number of clean samples so that they can deploy simple defense of filtering out inputs that do not fall into a dimension-wil samples of the victim. Figure 2 shows that as the feature extractor becomes better (using deeper mod- els 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 the downstream analysis and the conclusions are similar (Appendix D.2.7).
0.15
LeNet R-
1
0
Sep/SD
Figure Improving downstream robustness to poison- ing through better feature extractors.
box constraint that is computed from the available clean
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 eгтor increase from optimal poisoning attacks, which is an interesting future work, and one possible approach might be to tighten the upper bound Theorem 5.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 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, cach of which may be prone to poisoning. We also did not systematically investigate how to compare the vulnerabilities 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 the relative positions of the subpopplations//ndivide population under the clean decision boundary will also play important roles.
test samples to the rest of the
10

---

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, # +1846633,, the AI Institute for Agent- 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.
References
[1] Amazon, Inc. Amazon SageMaker. attps://awes amazon. cow/ wommsaagmaaer//... Accessed: 2023-05-01.
[2] Daniel Arp. Michael Spreitzenbarth, Malte Hubner, Hugo Gascon, Konrad Rieck, and CERT Siemens. Drebin: Effective and explainable detection of android malware in your pocket. In Network and Distributed System Security, 2014.
[3] Battista Biggio, Blaine Nelson, and Pavel Laskov. Support Vector Machines Under Adversarial Label Noise. In Asian Conference on Machine Learning, 2011.
[4] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning Attacks against Support Vector Machines, In International Conference Machine Learning. 2012.
[5] Mustain Billah, Adnan Anwar, Ziaur Rahman, and Syed Md Galib. Bi-level poisoning at- tack model and countermeasure for appliance consumption data of smart homes. Energies, 14(13):3887, 2021.
[6] Nicholas Carlini, Matthew Jagielski, Christopher A Choquuete-Choo Daniel Paleka, Will Pearce, Hyrum Anderson, Andreas Terzis, Kurt Thomas, and Florian Tramèr. Poisoning web-scale training datasets is practical. arXiv preprint 2rX1v:2302.101499 2023.
[7] Yizheng Chen, Zhoujie Ding, and David Wagner. Continuous learning for Android malware detection. arXiv preprint arXiv:2302.04333 04332, 2023.
[8] Yizheng Chen, Shiqi Wang, Yue Qin, Xiaojing Liao, Suman Jana, and David Wagner. Learning security classifiers with verified global robustness properties. In ACM Conference Computer and Communications Security, 2021.
[9] Antonio Emanuele Cinà, Sebastiano Vascon, Ambra Demontis, Battista Biggio, Fabio Roli, and Marcello Pelillo. The hammer and the nut: Is bilevel optimization really needed to poison linear classifiers? In International Joint Conference Neural Networks, 2021.
[10) Ambra Demontis, Marco Melis, Maura Pintor, Matthew Jagielski, Battista Biggio, Alina Oprea, Cristina Rita-Rotaru, and Fabio Roli. Why Do adversarial attacks transfer? Explaining transferability of evasion and poisoning attacks. In USENIX Security Symposium, 2019.
[11] Ambra Demontis, Paolo Russu, Battista Biggio, Giorgio Fumera, and Fabio Roli. On security and sparsity of linear classifiers for adversarial settings. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop. Springer, 2016.
[12] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stew- art. Sever: robust alga-algo for stochastic optimization. International Conference on Machine Learning, 2019.
[13] Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. Near-optimal SQ lower bounds for agnosti- cally learning halfspaces and ReLUS under Gaussian marginals. Advances in Neural Information Processing Systems, 2020.
[14] Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017.

---

[15] Maurizio Ferrari Dacrema, Paolo Cremonesi, and Dietmar Jannach. Are we really making much progress? worrying analysis of recent neural recommendation approaches. In ACM Conference Recommender Systems, 2019.
[16] Liam Fowl, Micah Goldblum, Ping-yed yeh Chiang, Jonas Geiping, Wojeiech Czaja, and Tom Goldstein. Adversarial examples make strong poisons. Advances in Neural Information Processing Systems, 001300339-33335 2021.
[17] Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of halfspaces with gradient descent via soft margins. In International Conference on Machine Learning, 2021.
[18] Jonas Geiping, Liam Fowl, W Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching. In International Conference on Learning Representations, 2021.
[19] Hanxun Huang, Xingjun Ma, Sarah Monazam Erfani, James Bailey, and Yisen Wang. Un- learnable examples: Making personal data unexploitable. arXiv preprint arXiv:2101.0444 04898, 2021.
[20] Ling Huang, Anthony Joseph, Blaine Nelson, Benjamin IP Rubinstein, and J Doug Tygar. Adversarial Machine Learning. In ACM Workshop on Security and Artificial Intelligence, 2011.
[21] W Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. MetaPoison: Practical general-purpose clean-label data poisoning. In Advances in Neural Information Processing Systems, 2020.
[22] Matthew Jagielski, data poisoning attacks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. pages 3 3104-3122, 2021.
Giorgio Severi, Niklas Pousette Harger. and Alina Oprea. Subpopulation
[23] Adam Tauman Kalai, Adam Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal Computing, 1776) 2008.
[24] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, 2017.
[25] Pang Wei Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. Machine Learning. 111(1):1 47, 2022.
[26] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers features from tiny images. 2009.
[27] Yann LeCun. The MNIST database of handwritten digits, 1998.
[28] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228-2324 1998.
[29] Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks. arXiv preprint arXiv:2006. 14768, 2020.
[30] Yue Liu, Chakkrit Tantithamthavorn, Li Li, and Yepang Liu. Explainable AI for Android malware detection: Towards understanding why the models perform so well? In International Symposium on Software Reliability Engineering, 2022.
[31] Yiwei Lu, Gautam Kamath, and Yaoliang Yu. Indiscriminate data poisoning attacks on Neural Networks. arXiv preprint arXiv:2204.09092. 2022.
[32] Yiwei Lu, Gautam Kamth, and Yaoliang Yu. Exploring the limits of indiscriminate data poisoning attacks. arXiv preprint arXiv:2303.03592, 2023.
[33] Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the asxociation for computational linguistics: Human language technologies, pages 142-150.
2011.
12

---

[34] Shike Mei and Xiaojin Zhu. The Security of Latent Dirichlet Allocation. In Artificcia Intelligence and Statistics, 2015.
[35] Shike Mei and Xiaojin Zhu. Using Machine Teaching to Identify Optimal Training-Set Attacks on Machine Learerr. In AAAI Conference on Artificial Intelligence, 2015.
[36] Vangelis Metsis, Ion Androutsopoulos, and Georgios Paliouras. Spam filtering with Naive Bayes-Which Naive Bayes? In Third Conference on Email and Anti-Spum, 2006.
[37] Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles A Sutton, J Doug Tygar, and Kai Xia. Exploiting machine learning to subvert your spam filter. In USENIX Workshop on Large Scale Exploits and Emergent Threats, 2008.
[38] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2830, 2011.
[39] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?" Explaining the predictions of any classifier. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
[40] Peter J Rousseeuw, Frank R Hampel, Elvezio M Ronchetti, and Werner A Stahel. Robust stutistics: the approuch bused influence functions. John Wiley & Sonn, 2011.
[41] Ahmad Salah, Eman Shalabi, and Walid Khedr. A lightweight Android malware classifier using novel feature selection methods. Symmetry, 12(5):858, 2020.
[42] Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Du- mitras, and Tom Goldstein. Poison Frogs! Targeted clean-label poisoning attacks on Neural Networks. In Advances in Neural Information Processing Systems, 2018.
[43] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
[44] Nedim Šmdic and Pavel Laskov. Detection of malicious PDF files based on hierarchical document structure. In Network and Distributed System Security, 2013.
[45] Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. Advances in Neural Information Processing Systems, 2017.
[46] Fnu Suya, Saeed Mahloujifar, Anshuman Suri, David Evans, and Yuan Tian. Model-targeted poisoning attacks with provable convergence. In International Conference on Machine Learning, 2021.
[47] Lue Tao, Lei Feng, Hongxin Wei, Jinfeng Yi, Sheng-Jun Huang, and Songcan Chen. Can adversarial training be manipulated by non-robust features? Advances in Neural Information Processing Systems, 35:26504-266 26518, 2022.
[48] Lue Tao, Lei Feng, Jinfeng Yi, Sheng-Jun Huang, and Songcan Chen. Better safe than sorry: Preventing delusive adversaries with adversarial training. Advances in Neural Information Processing Systems, 34:16209-16225, 2021.
[49] Florian Tramèr and Dan Boneh. Differentially private learning needs better features (or much more data). International Conference on Learning Representations, 2021.
[50] Wenxiao Wang, Alexander Levine, and Soheil Feizi. Lethal Dose Conjecture on data poisoning. In 36th Conference on Neural Information Processing Systems, 2022.
[51] Wenxiao Wang, Alexander J Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In International Conference on Machine Learning, pages 22769222783 PMLR, 2022.
13

---

[52] Yaqing Wang, Quanming Yao, James T Kwok, and Lionel M Ni. Generalizing from a few examples: survey on few-shot learning. ACM computing surveys (csur), 53(3):1-34, 2020.
[53] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, 2018.
[54] Han Xiao, Huang Xiao, and Claudia Eckert. Adversarial Label Flips Attack Support Vector Machines. In European Conference on Artificial Intelligence, 2012.
[55] Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie-Yan Liu. Indiscriminate poisoning attacks shortcuts. 2021.
[56] Chen Zhu, W Ronny Huang, Ali Shafahi. Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks on Deep Neural Nets. In International Conference on Machine Learning, 2019.
14

---

A Proofs of Main Results in Section 4
A.1 Proof of Theorem 4.3
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 hypothesis class. These definitions are necessary for the proof of Theorem 4.3.
Definition A.1 (Strong Convexity). A function / IR" + R is b-strongly convex for some b > 0, if f(x1) 2 (x2) + f22) (x1 Definition A.2 (Lipschitz Continuity). A function f R" + R is p-Lipschitz for some > 0, if [f(a) (22)) S p| æ 22 l22 for any 21, 22 E R
- x2) + 2 |||1 - æ2l22 22 for any #1, 22 E R".
Definition A.3 (Uniform Convergence). Let be hypothesis class. We say that H satisfies the
uniform convergence property with loss function f, if there exists function my (0, 1)2 + N such that for every é', 8 E (0, 1) and for every probability distribution μ. if S is set of examples with m 2 mx((',8) samples drawn i.idd from μs, then
sup [(h:As) - L(h:)a) S 2 8'. bEH
Such a uniform convergence property, which can be achieved using the VC dimension or the Rademacher complexity of H. guarantees that the learning rule specified by empirical risk minimiza- tion always returns good hypothesis with high probability [43]. Similar to PAC learning, the function my measures the minimal sample complexity requirement that ensures uniform convergence.
Now, we are ready to prove Theorem 4.3
Proof of Theorem 4.3. First, we introduce the following notations to simplify the proof. For any Sp. Up and 8 2 0, let
Sc) = -rrgmin
Σ
E(h;
hER
(s,
g(6, Pp. He) argmmnn hem
(I(h; (e) + L IL; Up)7
According to the definitions of h; and h7, we know h; - 0( S.) and h = g(6", :.. Mc).
Now we are ready to prove Theorem 4.3. For any S. sampled from Pe: consider the empirical loss minimizer hg 0(Sp, and the population loss minimizer g(ōs; üs; Mc), where ōs; |851/\8cl- Then S S. can be regarded as the i.i.d. sample set from (pe + ōs; (os;)/(1 + 6s;). According Definition A.3, since H satisfies the uniform convergence property with respect to É, we immediately know that the empirical loss minimization is close to the population loss minimization if the sample size is large enough (see Lemma 4.2 in [43]). To be more specifie, for any e', 8 E (0, 1). if |S.| 2 myx('', (E', 8'), then with probability at least - 8', we have
L L( + òs;;" LØ0( (s) < argmin (L(h; + ōs; LLhh po;) }} 2 NEW
= =L(g(6s; As; Mc): pe) + ós; Lgg(55; As; Me): ps;;) + 2é'
In addition, since the surrogate loss is b-strongly convex and the population risk p-Lipschitz we further know the clean risk of "(S,,S, and g(ōs;, üs; Me) is guaranteed to be close. Namely, with probability at least 1 - 8', we have Risk( Se); Risk(g(ōs; psp Mc); Pc) S p |10(5, S.) g(6s; po)l2
/e' S <2pV b.
Note that ds; E [0, e| and supp(ūs;) S C. Thus, according to the definition of h1 = g(0", pp Mc). we further have
Risk Mc) 2 Risk (as00ssssss,s. Mc): pc) 2 Risk Sc); -20
Risk(h - 201 /e T
(6)
15

---

So far, we have proven one direction of the asymptotic for results Theorem 4.3.
On the other hand, we can always construct a subset Sp with size | = 8" |Sa by i.idd. sampling from Py. Consider the empirical risk minimizer O(Sp. Se) and the population risk minimizer h; g(ō" plp Mc). Similarly, since H. satisfies the uniform convergence property, if [Sd 2 mx(é', then with probability at least 1 - 8'we have
(.) 8* L( S.): S argmin (L(h; me) + + L(h;; 12))) + 2e'
NEH
= Lgg("" Mbp pe); Ho) + + Llgg00 Hyp poli (i)) + 2é'.
According to the strong convexity of and the Lipschitz continuity of the population risk, we further have
[Risk(j(S,, S.): - Risk Risk(a(0" M6p mo); Mo); S p- [l0(Sp, S.) - "000"
PSp Mo) ll2
e'
- 2P
Note that Sp and |Sp1 8 -Soel S e -Sel Thus according to the definition of h; 9(5 Se). we have
(hps Risk Sc): z Risk(g(0", 1bp Mc): Me) -20 c
Risk (1))s 20v /e'
Combining (6) and (7), we complete the proof of Theorem 4.3.
A.2 Proof of Theorem 4.5
Proof of Theorem 4.5. We prove Theorem 4.5 by construction.
We start with the first condition supp(ue) C C. Suppose 8* <, e, since the theorem trivially holds 8* To simplify notations, define (6. Up] argmingec {L(h; me) + 8 L(h; up)) for any and Mpp To prove the statement in Theorem 4.5, it is sufficient to show that there exists some up based on the first condition such that
Risk (hp(ee
2 me)) = Risk (h, (1)):: Pe), and supp(u C.
The above equality means we can always achieve the same maximum risk after poisoning with the full poisoning budget To proceed with the proof, we construct ui (6) based on flc and μe follows:
8
6 6-
E(l 8(1 (Mo + 8 (G)
<(1 8+) Pe + (1(1+e)
E e 8
<(1 (1) 14.
We easily check that 4/) is valid probability distribution and supp(u!)) (0)) C C. In addition, can show that
hple, (1)) = argmin (I(h; + T(hh;1()))
keH
argmin (E(an)) ((h; E e(;; NEW
1+c (E l(; x. v) + 8" E(n.))p3 2 e(h; v))
argmin
11+8*
NEH
-pp6"" (
where the third equality holds because of the construction of u Therefore, we have proven (8). which further implies the optimal attack performance can always be achieved with e-poisoning as long the first condition is satisfied.
16

---

Next, we turn to the second condition of Theorem 4.5. Similarly, it is sufficient to construct some (e) Up for the setting where d" such that
Risk (c, (4 ); = Risk (h,(" (1)))
(:p):P)) Pe), and supp( CC.
We construct Up based on up and the assumed data distribution More specifically, we construct
8"
8
11
μ.
By construction, we know Up is a valid probability distribution. addition, according to the assumption of supp(u) E C, we have supp(up)) S C. According to the assumption that for any 0, there exists a such that 0 [(ho: = O, we know for any possible weight parameter 0 of & hp(6", .G)), there also exists corresponding such that the gradient is 0 and therefore, we have
(L(hp(6' (2)))))) + L(hp(6" (())))))
da; (L(hp6"" + L(hpl0" (p))(())))
0
where the last equality is based on the first-order optimality condition of hpp6" .11)) for convex losses. For simplicity, we also assumed (6" .1()) is obtained by minimizing the loss on pee + 0 "i while in the case of supp(μe) g C, the victim usually minimizes the loss on Aee + +8 Heg where Me is the "truncated" version of such that supp(ãe) S C. To conclude, we know he,e, Hp (e) ) = hp(8' .1)) holds for any possible hpp8", (15) and we complete the proof of Theorem 4.5.
A.3 Proofs of the Statement about Linear Models in Remark 4.6
Proof. We provide the construction μ with respect to the second condition Theorem 4.5 for linear models and hinge loss. Since for any h E Hr, and any (at, y) E X' V, we have
f(hw bi v, = max 0, 1 y(w b)} 2 1
Let (wv b), then the gradient with respect w be written as:
① e(b xt y) {{
-y x + Aw
if f x + b) $ 1,
Aw
otherwise.
Similarly, the gradient with respect can be written as:
0 (hwwwi x,
if y T x + 6) S 1,
0
otherwise.
Therefore, for large input space X' y, we can simply construct μ by constructing two-point distribution (with equal probabilities of label +1 and -1) that cancels out each other's gradient (for both and b), that y(w?
< 1 and -y
Aw 0.
We may also generalize the construction of μ from linear models with hinge loss to general convex models if the victim minimizes the loss frc + 8" 15 to obtain (6', (C)). which is common in practice. In this case, we can simply set μ = The + 8* Mbg which guarantees
8 (0, (O,,("",1))'p p) = 0.
Do;
17

---

B Proofs of Main Results in Section
B.1 Proof of Theorem 5.3
To prove Theorem 5.3, need make use of the following three auxiliary lemmas, which are related condition
to the maximum population hinge loss with w = 1 (Lemma B.1), the (Lemma B.2) and the risk behaviour of any linear hypothesis under (2) (Lemma B.3). For the sake of completeness, we present the full statements of Lemma B.1 1 and Lemma B.2 as follows. In particular, Lemma I, proven in Appendix C.I, characterizes the maximum achievable hinge loss with respect to the underlying clean distribution Me and some poisoned distribution Up conditioned on 1.
Lemma B.1. Suppose the underlying clean distribution Pee follows the Gaussian mixture model (2)
with p = 1/2 and 01 = 02 = a. Assume 1 + 72l S 2u. For any e 2 O, consider the following maximization problem:
max (PE((u)
[L(hi,briPd) Me) + L(hLs,;
(10)
where by argmingeRl (Th 6 T(h1,bi Up)). There exists some E [0, such that the optimal value of (10) is achieved with pp Vor where Va a two-point distribution with some parameter E [0, 1] defined according to (3).
Lemma B. suggests that it is sufficient to study the extreme two-point distributions Vo. with a E [0. to understand the maximum achievable population hinge loss conditioned on w 1. Lemma B.2. proven in Appendix C.2, characterizes the sufficient and necessary conditions in terms of c, u and Me. under which there exists a linear hypothesis with w 1 that achieves the minimal value of population hinge loss with respect to μre and some Mtp-
Lemma B.2. Suppose the underlying clean distribution Pa. follows the Gaussian mixture model (2) with p = 1/2 and 01 = 02 = a. Assume 171 + +721 S 2(u - 1) for some u 1. Let g be an auxiliary function such that for any b R,
b 71 +1
--b
72 -)
((b) +
2 $
where & is the CDF of standard Gaussian. For any > 0, there exists some Mp (uu) such that argmin (L Pe) + C. L(hr, bi ppp] outputs a hypothesis with w -1, if and only if
(()))(())))((())))((()) 2 0,
where A(s) (())i--) minser I L(h Mc) c(1 u) g (s), and g-1 denotes the inverse of g.
Lemma B.2 identifies sufficient and necessary conditions when a linear hypothesis with flipped weight parameter is possible. Note that we assume 71 S 72. thus flipping the weight parameter of the induced model from w = 1 to w = -1 is always favorable from an attacker's s perspective. In particular, if the population hinge loss with respect to Me and some μ4 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 B.3, proven in Appendix C.3, which characterizes the risk behavior of any linear hypothesis with respect to the assumed Gaussian mixture model (2).
Lemma B.3. Let ue be the clean data distribution, where each example is sampled ii.d. according to the data generating process specified in (2). For any linear hypothesis hw. HI. we have
b 11 + + (1-p) (bb w 72
Risk He) =
σ1
where T denotes the CDF of standard Gaussian distribution. (((piittiiooOOO N(00
Now are ready to prove Theorem 5.3 using Lemmas B.I, B.2 and B.3.
18

---

Proof of Theorem 5.3. According to Theorem 4.5 and Remark 4.6, we note that the optimal poisoning performance Definition 4.2 is always achieved with 8 e. Therefore, we will only consider 6 in the following discussions.
Since the optimal poisoning performance is defined with respect clean risk, it will be useful to understand the properties of Risk(hw.bi Re) such as monotonicity and range. According to Lemma B.3, for any hi. HI. we have
1 $
(b+w) w. 71
b w 72
Risk(hoo,b Me))
+
To understand the monotonicity of risk, we compute its derivative with respect to b:
0 Ob Risk(hw,
(b + w. .1)²
exp (-
(b + w 72)
exp
20 2m
20
20²
If w = L, then Risk Pe) is monotonically decreasing when b E ---00-22-0 and monotoni- cally increasing when b E (- x)), suggesting that minimum is achieved at b 21 t and maximum is achieved when b goes to infinity. To be more specific, Risk(h110;:44 e [ n1 ?=))) ), 21 On the other hand, if w = -1, then Risk(h Me) is monotonically increasing 2x
when b E (-xc, 2)) and monotonically decreasing when b E (2 oo), suggesting that maximum is achieved at = n and minimum is achieved when b goes infinity. Thus, Me) E [ $ )(
2
Based on the monotonicity analysis of Risk(hee pe), we have the following two observations:
1. If there exists some feasible Mp such that h-1.b, argmin (Lhh; Mo) + eL(h; (p)) can be achieved, then the optimal poisoning performance is achieved with w = -1 and close to 21 as much as possible. 2
2. If there does not exist any feasible Up that induces h- by minimizing the population hinge loss, then the optimal poisoning performance is achieved with w and far from . much as possible (conditioned that the variance the same for the two classes).
Recall that we prove in Lemma B.2 specifies a sufficient and necessary condition for the existence of such 1.b, which is equivalent the condition (4) presented in Lemma B.2. Note that according to Lemma C.I, b -ut= also yields the population loss minimizer with respect to Pc. conditioned on w = -1. Thus, if condition (4) is satisfied, then we know there exists some a E [0, 1] such that the optimal poisoning performance can be achieved with U4 Va- This follows from the assumption
In + 72 < 2(u - 1), which suggests that for any (z. v) ~ Va. the individual hinge loss at (æ, v) will be zero. In addition, we know that the poisoned hypothesis induced by Aopt is h 21 which maximizes risk with respect to Pe-
On the other hand, if condition (4) is not satisfied, we know that the poisoned hypothesis induced by any feasible H has weight parameter w = 1. Based on our second observation, this further suggests that the optimal poisoning performance will always be achieved with either up = vo or up vi- According to the first-order optimality condition and Lemma C.I, we can compute the closed-form solution regarding the optimal poisoning performance. Thus, we complete the proof.
B.2 Proof of Theorem 5.7
Proof of Theorem 5.7. Consider linear hypothesis class H. and the poisoned distribution 14, generated by the optimal poisoning adversary Aupt in Definition 4.1. Given clean distribution /ee. poisoning ratio e and constraint set C, the inherent vulnerability to indiscriminate poisoning is captured by the optimal attack performance Risk(h,; Hc), where hü denotes the poisoned linear model induced by Me. For any h E H. we have
Rh;k(h & L(C): S L(h;;
+ -- < L(h He) e (5:
(11)
where the first inequality holds because the surrogate loss is defined to be not smaller than the 0-1 loss, the second inequality holds because the surrogate loss is always non-negative, and the third incquality holds because h minimizes the population loss with respect to both clean distribution
19

---

and optimally generated poisoned distribution ue. Consider he argmin Lh;; pc) (with weight parameter w, and bias parameter bz), which is the linear model learned from the clean data. Therefore, plugging h = he into the right hand side of (11), we further obtain
Risk(hi Mc) & (ehes
L(hei (2)) S L(hei Pc) + E ( (C)),
(12)
where the last inequality holds because for any poisoned data point (x, y) ~ ug. the surrogate loss at (z: y) with respect to he is (y (w)) x + be)). and y (w. x + bz) I max(x.y) | x + bel- Under the condition that mi)(a, w- x S bb I maX(x.y)eC w x which means the decision boundary of he falls into the constraint set C. when projected on to the direction of wes we further have (a)(e [wa æ + bel S Sizcw, (C), which implies the validity of (12). We remark that the condition min(a,,) W x bb I ma)(a. w typically holds for margin- based loss in practice, since the support of the clean training data belongs to the constraint set for poisoning inputs (for either undefended victim models models that employ some unsupervised data sanitization defense). Therefore, we leave this condition out in the statement of Theorem 5.7 for simplicity. L.
C Proofs of Technical Lemmas used in Appendix B.1
C.1 Proof of Lemma B.1
To prove Lemma B.I, 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 Pe- For the sake of completeness, we provide the proof of Lemma C.I in Appendix C.4.
Lemma C.1. Let pe be data distribution generated according to (2). For any too E HL, the population hinge loss is:
L(ew,bi Mc) = b-
(b+ w 71 + + 1 012) -01)++02))))))))
-h-
22
+ (1 p)
(-b-w-72
w 72 + 022) (2()ddz
and its gradient with respect to b is:
① L( He) = p.
b (bb +1 (b -
p). p1- - ()-p))--bu
72 +
bb
σ1
where ip and & denote the PDF and CDF of standard Gaussian distribution NN0,, 1), respectively.
Next, let us summarize several key observations based Lemma C.1 (specifically for the setting considered in Lemma B. For any w E [-1,1], ab I(h Me) is monotonically increasing with b. which achieves minimum - when b goes to -oo and achieves maximum 1 when b goes to xx. If = +1, then L(h 65 no) is monotonically decreasing when E (-xc 2 and monotonically increasing when b E (- oo), reaching the minimum at b = (1) := - >2 On the other hand, if w 11, then L(h (MW.,iie)) He) is monotonically decreasing when E (-o0, 20 and monotonically increasing when b E (2 oo), reaching the minimum at 65(-1) 22
à
As for the clean loss minimizer conditioned on w = 1, we have
((h =
00
11 - 7/
+ +1+ oz x(())dz
2
20
22222
711 - 72
1 02
:p(2)dz
2
000
(71
+ 2)
71 72 +2
(_(11
(71 - 72 + 2)3
T
+
exp
2
20
2
802
20

---

whereas as for the clean loss minimizer conditioned on w =1, we have
12 -
7
+ +1+ 02) :((2)dz
2
20
Y2 71
+ 0z
00
(72
71
+ 2)
12 71 +
(-122-
(7/ 1 92 +222 +2)²
+
exp
2
20
2
8
Let [(1) = 1 .
+
a
exp( 26
12 )
we know L(b1,g(1): Mc) = 1(22 1(21-22t2) and
22x
[(h-1.0(-13: = / (2221 +2
We can compute the derivative of f(1): ('(1) = + 2 0,
which suggests that L( L(hi S L(h 1()
Now we are ready to prove Lemma B.1.
Proof of Lemma B. I. First, we prove the following claim: for any possible by, linear hypothesis h1,5 always be achieved by minimizing the population hinge loss with respect /ee and Mp Va with some carefully-chosen a E [0, 1] based on bp-
For any Mp @u)). according to the first-order optimality condition with respect to 6p. we have
① 0b T.(h1,,;)e)) - ab
[(h1 M(b1b,i14p)) = ab B (a [[th1,, /tp]] E [-,,
(13)
where the last inequality follows from (h x, 8) E [-1,1] for any (x. y). Let B, be the set of any possible bias parameters bp. According (13), have
25
B, DER:
0 2 L( Ho) El -e.d.. 06
Let (1( = argmingeR L(hi,6i Mc) be the clean loss minimizer conditioned on w = 1. According to Lemma and the assumption Iy1 + 72l I 2u, we know 61(1) = 21 E [-u, u]. For any Bp Bp, can always choose
1
1
0
+
[ Mc) E [0,1],
(14)
2
2E
06
such that
h1,8, = argminn (11,, + L(hi,ii
bER
where Vaa is defined according to (3). This follows from the first-order optimality condition for convex function and the closed- dosed-form solution for the derivative of hinge loss with respect to Va:
2 0b (ha
2 ((++1,)) u, +1) (1 (1-a)
2 Zb ( u, 1) 2a.
Thus, have proven the claimed presented the beginning of the proof of Lemma B.
Next, we show that for any bp E Bp. among all the possible choices of poisoned distribution Up that induces bp. choosing Mp with defined according to (14) is the optimal choice in terms of the maximization objective (10). Let Plp E Q(u) be any poisoned distribution that satisfies the following condition:
bp = argmin(LL(h..t pc) + L(hi,i beR
According to the aforementioned analysis, we know that by setting a according to (14), v. also yields by- Namely,
bp argmin|L((b1oi t L(hi,si bER
Since the population losses with respect to pa are the same at the induced bias b = by. it remains to prove v. achieves larger population loss with respect to the poisoned distribution than that ppp i..., L(h1,0, Pa) 2 L(h1,5pi
21

---

Consider the following two probabilities with respect to by and Myi
a (h1,siii, P1 P (2.0)~<pp
= -1]. p2 ((
a
[hi,b,, y) - =
ab
Note that the derivative of hinge loss with respect to the bias parameter is 2e (hhm,iii 21,1) {-1,0,1) thus we have
(h1, x, = =0 = =1 (p1 + P2).
(x Ob
Moreover, according to the first-order optimality of by with respect to Mps we have
Tb ((haa,g)te) - L(hn L(hi,,i = (pi p2),
Øb
If we measure the sum of the probability of input having negative gradient and half of the probability of having zero gradient, we have:
P1 + 1
(pr + P2)
P1
0 2c Øb
L(h1,,55te) L = a.
2
2
2
2
Therefore, we can construct mapping 9 that maps Pp vs: by moving any (zr,y) Up that contributes pi (negative derivative) and any (x. Ap that contributes (positive derivative) to extreme locations (-u, +1) and (u, -1), respectively, and move the remaining (x, y) that has zero derivative to (-u, +1) and (u, -1) with equal probabilities (i.e.. 1-p-pp ), and we can easily verify that the gradient of 6, with respect to UP is the same as Va-
In addition, note that hinge loss is monotonically increasing with respect to the l distance of misclassified examples to the decision hyperplane, and the initial clean loss minimizer (1) E [-u, ud), we can verify that the constructed mapping g will not reduce the individual hinge loss. Namely, ((11,12 x. y) S E(h1,65 g(,, u)) holds for any (x, y) ~ Mp- Therefore, we have proven Lemma B.1.
C.2 Proof of Lemma B.2
Proof of Lemma B.2. First, we introduce the following notations. For any Up E Q(u) and any W E 11, let
(w) argmin L(hw,pi Pe), (p: Hp))
argmin argmin(L((w..at (Lho Po) + c L(hi di Pp)).
bER
bEr
According to Lemma B.1, we know that the maximum population hinge loss conditioned on 1 is achieved when Hp = Va for some a E [o, 1]. To prove the sufficient and necessary condition specified in Lemma B.2, we also need to consider to specify the minimum loss that can be achieved with some (Ap for w = -1. For any Ho E Q(u), we have
-1 Note that different from 1, we want
((0-1006-1pp0354 + -Lhh-1,00- Mp) min L(h pe) L(b (-1 (15)
BER
According to Lemma C.I, we know (-1- _ which achieves the minimum clean loss conditioned on w = 11 Since we assume 11 E [-u 1, - 1). according to the first-order optimality condition, the equality in (15) can be attained as long as ut only consists of correctly classified data that also incurs zero hinge loss with respect to 6-(-1) (not all correctly classified instances incur zero hinge loss). can be easily checked that choosing H,, Vo based (3) with any a E [0, 1] satisfies this condition, which suggests that as long as the poisoned distribution Me is given in the form of Pa and if the w will be discussed shortly), then the bias term that minimizes the distributional loss is equal to b (-1),
2
1 is achievable (conditions on when this can be achieved
and is the minimum compared to other choices of 6, (pp-1;; 1: H4)). According to Lemma B. I, it further implies the following statement: there exists some a E [0, 1] such that
Va argmax PpE)(u)
[L(h,,, Mc) + e. [(h,,,,((w.,33..))))
- [L 11 + I. (( [el)
22

---

For simplicity, let us denote by AL (p (e) the maximization objective regarding the population loss difference between = 1 and -1 Thus, necessary and sufficient condition such that there exists (1=1,, as the loss minimizer is that [0x1 [T[(V;; Me.) 2 0. This requires us to characterize the maximal value of loss difference for any possible configurations of 6, and Pe. According to Lemma C.1 and the definition of va for any E loss difference as
[0, 11, we denote the above
,, M.) (lsaii(( +e [(h1),((w..). -_
12
The second term 1z is fixed (and the loss on is zero conditioned on w -)), thus it remains characterize the maximum value of Ii with respect a for different configurations. Consider auxiliary function
b + +
1 !
(0---2- -
g(b) 2
We know g(b) -
2. is a monotonically increasing function by checking with derivative to b. Let g-1 be the inverse function of g. Note that according to Lemma C.I and the first-order optimality condition of (1; we have
① 0b 1h Mo)
((b((+1;)a)) - (a) = e (2a 1), (16) ab
where the first equality follows from Lemma C.I, the second equality follows from the first-order optimality condition and the last equality is based on the definition of Va- This suggests that (1; --- (2a - 1)) for any E [0, 1].
(e) and 0 E Consider the following two configurations for the term 1; O & (-- (g- (e)]. Consider the first configuration, which also equivalent to g & [-e,e] We can prove that if 7/1 + < 0 meaning that (1) > 0, choosing a = 0 achieves the maximal value of [1: whereas 71 + 72 > O, choosing a achieves the maximum. Note that it is not possible for 71 + 7/2 = 0 under this scenario. The proof is straightforward, since we have
11 = 12h1 (j)))) + L(bbsgg' Va)
L(hig- Mo) +
u - (1-2a) (2Ea c)]
= L(h1,1 (e) c (1 +u) t. g(t),
where t = g (2ea- - c) E 1 (c), (c)). In addition, we can compute the derivative of I with respect
a ot /1 = --) gt)(
-t
which suggests that 1 is concave function with respect
If E [g
we achieve
the global maximum of 4 at t by carefully picking ag = - + के g()) If not (i.c., g (-c) > or 9 (c) < 0), then we pick t that is closer to O, which is either c) or g(c) by setting a = a respectively. Therefore, we can specify the sufficient and necessary conditions when the weight vector w can be flipped from to -1:
1. When (0) & {_,, the condition is
max ( (AL(u: c, u, pe), ALVI;, 2 0.
2. When (0) E [-e,e], e), the condition is
AL(Po u, He) 2 0, where og
9(0).
2 2e
Plugging in the definition of g and AL, we complete the proof of Lemma B.2.
C33 Proof of Lemma B.3
Proof of Lemma B.3. Let fn, u1 be the probability measures of the positive and negative examples assumed in (2), respectively. sp(277,a) be the PDF of Gaussian distribution A (17, o²). For simplicity, simply write (p()) =p(2; 0, 1) for standard Gaussian. For any hw,b 5 E HL. we know
23

---

can be either 1 or -1. First, let's consider the case where w = 1. According to the definition of risk and the data generating process of Hes we have
Risk(howbb Mc) = p- Risk (hw 11) + (1 - p) Risk (hank(h
= p.
((2;71, jdz + +1 (1-p)
((z 72, 02)dz
-2-22
x p.
p(z)dz + +(1 (1-p))
(02)dz
-b-r1
00
b b+ 11
-b -b- 1/2
ob
+ (1 pp) ①b
01
02
Similarly, when 11, we have
(1-)))) Risk(heo Mc) p f (1) + (1-1)) p). I (221
4(z)dz + +(1
p(z)dz
p. xc
- 71 + (1 - p) +b
-b +b+ 7/2
Combining the two cases, complete the proof.
C.4 Proof of Lemma C.1
Proof of Lemma C.I. We use similar notations such as fı. P2 and o as Lemma B.3. For any hmgh E Hr, with 1, then according to the definition of population hinge loss, have
L(h Pc)
B(
[max(0,11 y(u + b)}]
b+1
(1+b+
+ - p)
(1 - 2)p(2; 72, 02)dz
b-1
-b41-12
12
+ (1-p)
(1- -0==)))((2())
1
-20
b b+++1
1
(b+ + 71 + 1)2
-p(b + + 1)
+ p
exp
σ1
/ 2t
20²
-b- +1
1
(-b b
72 1)²
+ (1 - (2b 1)
+ (1 p)oz
exp
02
/2T
20
Taking the derivative with respect to parameter and using simple algebra, we have
ab [(hm,bitee) p. p b +1 - (1 p) +
(-b b 72 +
02
24

---

Similarly, for any hw,b E H.. with w = -1, we have
T.h Pc)
B Blay)ap
max 100,1-3100 v(-x +
p.
b+1
(1 (1+b-
+ (1- (1-p). p).
b+ [ -
(1 (2,
000
(1
bb-
1+1-11
= p
(1 b - - 01 -1) + (1-
(1-b+ 72 + 02=)))(2)))))))
1-1--2 12
b b- +1
1
(b - 71 + +1
p(b - -n + 1)
+ +po1
exp
01
/2T
20
72 +
1
(-b + 72 + 1)²) 203
+11- (-b 72 + 1)
+ (1 p)oz
exp
02
2
Taking the derivative, we have
Tb ((hmmbi - p- b ( -
- (bb+
-1) Φb
02
Combining the two scenarios, we complete the proof.
D Additional Experimental Results and Details
In this section, we provide details on our experimental setup (Appendix D.I) and then provide additional results (Appendix D.2).
D.1 Details on Experimental Setup in Section 3
Details on datasets and training configurations. In the main paper, we used different public benchmark datasets including MNIST [27] digit pairs (i.e., 1-7. 6-9, 4-) and also the Enron dataset, which is created by Metsis et al. [36], Dogfish [24] and Adult [14], 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 [33], which has also been used prior evaluations [24, 25]. We did not include the IMDB results in the main paper because we could not run the existing state-of-the-ar poisoning attacks on IMDB because the computation time is extremely slow. Instead, we directly quote the poisoned error of SVM from Koh et al. [25] and then present the computed metrics. For the Dogfish and Enron dataset, we construct the constraint set C in the no defense setting by finding the minimum (uiii)) and maximum (uinax) values occurred in each feature dimension for both the training and test data, which then forms a box constraint [wiinn "(nax] for each dimension. This way of construction is also used in the prior work [25]. Because we consider linear models, the training [38] 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 À for training the linear models (SVM and LR) are configured as follows: X 0.09 for MNIST digit pairs, Adult, Dogfish, SVM for Enron; = 0.01 for IMDB, LR for Enron. Overall, the results and conclusions in this paper are insensitive to the choice of X. The computation of the metrics in this paper extremely fast and can be done on any laptop. The poisoning attacks can also be done on laptop, except the Influence Attack [25], whose computation can be accelerated using GPUs.
Attack details. The KKT, MTA and Min-Max attacks evaluated in Section require a target model as input. This target model is typically generated using some label-flipping heuristics [25, 46). In practice, these attacks are first run on a set of carefully-choser target models, then the best attack performance achieved by these target models is reported. We generate target models using the improved procedure described Suya et al. [46] because their method is able to generate better target models that induce victim models with higher test error compared with the method proposed in Koh et al. [25]. 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.
25

---

Poison Ratio (%)
0.0
0.1
0.2
0.3
0.5
0.7
0.9
1.0
2.0
3.0
Train Error (%)
0.1
0.8
1.2
1.8
2.6
3.1
3.3
3.6
5.3
6.5
Test Error (%)
0.8
9.5
12.8
13.8
17.8
20.5
21.0
20.5
27.3
31.8
Table Comparisons of training and test errors of existing data poisoning attacks on Dogfish. The poisoned training and test errors reported from the current best attacks.
Robust
Moderately Vulnerable Dogfish
Highly Vulnerable
Metric
MNIST 6-9
MNIST 1-7
Adult
MNIST 4-9
Enron
Enron
IMDB
Error Increase
2.7
2.4
3.2
7.9
6.6
33.1
31.9
19.1
Base Eiror
0.3
1.2
21.5
0.8
4.3
0.2
2.9
11.9
SVM
Sep/SD
6,92
6.25
9.65
5.14
4.44
1.18
1.18
2.57
Sep/Size
0.24
0,23
0.33
0.05
0.14
0.01
0.01
0.002
Firor Increase
2.3
1.8
2.5
6.8
5.8
33.0
33.1
Base Error
0.6
2.2
20.1
1.7
5.1
0.3
2.5
LR
Sep/SD 6.28
6.13
4.62
5.03
4.31
1.11
1.10
2.52
Sep/Size
0.27
0.27
0.27
0.09
0.16
0.01
0.01
Table Explaining disparate poisoning vulnerability under linear models by computing the metrics on the correctly classified clean test points. The top row for each model gives the increase in error rate due to the poisoning, over the hase error rate in the second row. The error increase of IMDB (marked with 1) is directly quoted from Koh al. (25] as running the existing poisoning attacks IMDB is extremely slow. LR results are missing as they are not contained in the original paper. The explanatory metries are the scaled (projected) separability, standard deviation and constraint size.
Following the prior practice [25], we consider adversaries that have access 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 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 eπror 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 Section 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 be cautious on the potential for "overfitting" behavior when designing poisoning attacks. Table 2 shows the drastic differences between the errors the clean training and test data after poisoning.
D.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 Appendix D.2.2 to complement Table in the main paper, then include the complete results the impact of data sanitization defenses in Appendix D.2.3 to complement the last paragraph in Section 7. Next, we provide the metrics computed on selective benchmark datasets using a different projection vector from the clean model weight Appendix D.2.4 to support the results in Table in the main paper. Lastly, we show the performance of different poisoning attacks various poisoning ratios Appendix D.2.5, complementing Figure the main paper.
D.2.1 IMDB results
Table in the main paper presents the metrics that are computed on the correctly classified test samples by the clean model w. 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 robust, and impacted the most by the poisoning points compared all other benchmark datasets. Note that, the increased error from IMDB is directly quoted from Koh al. [25], which considers data sanitization
26

---

Robust
Moderately Vulnerable
Highly Vulnerable
Models
Metrics
MNIST 6-9
MNIST 1-7
Adult
Doglish
MNIST 4-9
F. Enron
Enron
IMDB
Error Increase
2.7
2.4
3.2
7.9
6.6
33.1
31.9
19.1
Base Firor
0.3
1.2
21.5
0.8
4.3
0.2
2.9
11.9
SVM
Scp/SD
6,70
5.58
1.45
4.94
3,71
1.18
1.15
1.95
Scp/Size
0.23
0.23
0.18
0.05
0.13
0.01
0.01
0.001
Error Increase
2.3
1.8
2.5
6.8
5.8
33.0
33.1
Base Error
0.6
2.2
20.1
1.7
5.1
0.3
2.5
LR
Sep/SD
5.97
5.17
1.64
4.67
3,51
1.06
1.01
1.88
Sep/Size
0.26
0.26
0.16
0.08
0.15
0.01
0.01
0.002
Table 4: Explaining the different vulnerabilities benchmark datasets under linear models by computing metrics the whole data. The error increase of IMDB (marked with 1) directly quoted from Koh et al. [25].
Dataset
Error Increase
Base Error
Sep/SD w/o
Sep/Size w/o
w/o
w/
w/o
w/
MNIST 1-7 (10%)
7.7
1.0
1.2
2.4
6.25
6,25
0.23
0.43
Dogfish (3%)
8.7
4.3
0.8
1.2
5.14
5.14
0.05
0.12
Enron (3%)
31.9
25.6
2.9
3,2
1.18
1.18
0.01
0.11
Table 5: Understanding impact of data sanitization defenses poisoning attacks, w/o and w/ denote without defense and with defense respectively. MNIST 1-7 evaluated at 10% poisoning ratio due to its strong robustness at 3% and Enron is still evaluated at = 3% because it is highly vulnerable.
defenses. Therefore, we expect the attack effectiveness might be further improved when we do not consider any defenses, in our paper.
D.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 misclassi- fied ones), rather than just on examples that were classified correctly by the clean model. The metries are mostly similar to Table 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.
D.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 section 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 10% and considered significantly higher poisoning ratio because at the original 3% poisoning the dataset can well resist existing attacks and hence there 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, still compute the metries 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 sanitization defenses improve the robustness to poisoning by majorly limiting Sizew, (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 [45].
summarized in Table 5 and we can that existing data
D.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 other projection vectors that can be used for explaining the different vulnerabilities, mentioned in Remark 5.8.
27

---

Sep/SD
Sep/Size
Base Error (%)
Error Increase (%)
We
WU
We
WU
MNIST 1-7 Dogfish
1.2
2.4
6.25
6.51
0.23
0.52
0.8
7.9
5.14
4.43
0.05
0.19
Table 6: Using the projection vector that minimizes the upper bound on the risk of optimal poisoning attacks for general distributions. w, denotes the clean weight vector and wy denotes weight vector obtained from minimizing the upper bound.
Metric
MNIST 1-7
Doglish
Upper Bound (%)
20.1
34.9
Lower Bound (%)
3.6
8.7
Base Error (%)
1.2
0.8
Table Non-trivial upper bounds on the limits of poisoning attacks across benchmark datasets on linear SVM. The Upper Bound on the limits of poisoning attacks is obtained by minimizing the upper bound Equation (17). The Lower Bound on the limit of poisoning attacks obtained by reporting the highest poisoned error from the best empirical attacks. The datasets are sorted based on the lowest and highest empirical base error.
We conducted experiments that the projection vector that minimizes the upper bound 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 [25]. 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 Equation 5.
The results on two of the benchmark datasets, MNIST 1-7 and Dogfish, are summarized Table From the table, projected constraint size (increases Sep/Size), which probably indicates the weight vector obtained from minimizing the upper bound focuses more minimizing the term lm (Size,,, (C)) in Equation 5. Nevertheless, projecting onto the new weight vector can still well explain the difference between the benchmark datasets.
that, compared the clean model, the new projection vector reduces the
Using the obtained vector wy (denote the corresponding hypothesis as hy) above, we can also compute (approximate) upper bound the test error of the optimal indiscriminate poisoning attack, which is proposed by Steinhardt et al. [45] and shown in (17). The upper bound is an approximate upper bound to the test error because maxs, I.hhg S.) only upper bounds the maximum training error (of poisoned model h,)) S. from poisoning and is assumed that, with proper regularization, the training and test errors are roughly the same. We can view by as the numerical approximation of the hypothesis that leads the smallest upper bound on the (approximate) test error. Next, in Table 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 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.
28

---

Test Error (%)
Trained on S:
Trained on S; u Sp
10
Filtered Enron MNIST6-9
Dogfish
MNIST1-7
Enron
MNIST4-9
Aduit
Figure 3: Performance best current indiscriminate poisoning attacks with e e= 3% across different
benchmark datasets on LR. Datasets are sorted from lowest to highest base error rate.
50
Influence Attack
Test Error (%)
40
i-Min-Max
MTP
30
30
KKT
20
20
10
0.1 0.2 0.3 0.5 0.7 0.9 1.0 2.0
1.0
0.5 2.0
Poison Ratio (96)
MNIST 1-7
(b) Dogfish
(c) Enron
Figure 4: Comparisons of the attack performance of existing data poisoning attacks on different benchmark datasets. Poisoning ratios are 0. 9,, 0.2%, 0.3%, 0.5%, 0.7%, 0.9%, 1%, 2%. 3%.
max Lhhp: Sc) s min Sc) te max (h: Up) + + c)> s,Sc
|w0l3
(xp.Nn)EC
2
(1 e)
$ I(hu: + max (dp.8nleC
((hu: Fp pp. Up) +
2 /wo
(17)
D.2.5 Performance of different attacks are similar
In this section, first present the best attack results different benchmark datasets the LR model in Figure 3. Similar to the case of linear SVM as shown Figure 1, the performance of best known attacks vary drastically across the benchmark datasets. Although we only report the performance the best known attack from the candidate state-of-the-arr poisoning attacks, the difference among these canndidate attacks do not vary much in many settings. In Figure 4 show the attack performance of different attacks on the selected benchmark datasets of MNIST 1-7, Dogfish, and Enron and the main observation that different attacks perform mostly similarly for given dataset (but their performance varies a lot across datasets). Also, from the attack results on Enron (Figure 4c), we can see that several of the attacks perform worse at higher poisoning ratios. Although there is chance that the attack performance can be improved by careful hyperparameter tuning, it also suggests that these attacks are suboptinal. Optimal poisoning attacks should never get less effective as the poisoning ratio increases, according to Theorem 4.5.
D.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.c., Sep/SD and Sep/Size) to the empirically observed vulnerability against poisoning attacks. Given a dataset, 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 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 w., which again dependent on the (modified) clean distribution. Therefore, even if we use the same constraint set C for different modified datasets, the "Size" or "Sep/Size" can different. We conducted preliminary experiments MNIST 1-7 and the details given below.
aim modify such that we can gradually change one
29

---

Scale Factor e
Error Increase (%)
Sep/Size
1.0
2.4
0.23
2.0
3.6
0.12
3.0
4.9
0.08
5.0
7.8
0.05
7.0
9.8
0.03
10.0
15.6
0.02
Table 8: Impact of scale factor с on poisoning effectiveness for C in the form of dimension wiie box-constraint [0, c] (c 1) for the MNIST 1-7 dataset. Originally, the dimension-win -iise box constraint is in [0. 1]. The Base Error is 1.2% and the Sep/SD factor is 6.25 and these two values will be the same for all settings of because the support of the clean distribution is the strict subset of C. Higher value of e implies poisoning points can be more harmful.
Number of Repetitions x
Base Error (%)
Error Increase (%)
Sep/SD
Sep/Size
0
1.2
2.4
6.25
0.23
1
1.0
4.4
5.78
0.21
2
1.0
5.7
5.48
0.19
4
1.0
6.2
5.02
0.17
6
1.2
6.8
4.75
0.15
8
1.4
8.0
4.62
0.13
10
1.1
8.1
4.55
0.12
Table 9: Changing the distribution of the MNIST 1-7 dataset by replacing x -33% of correctly classified points farthest from the clean boundary with 3% of correctly classified points (repeated times) closest to the boundary. Higher value of æ denotes that more near boundary points will be present in the modified training data.
Change Sep/Size., In order measure the impact of Sep/Size without impacting Sep/SD, we can choose 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 w. and the corresponding metric of Sep/SD will not change. We performed hypothetical experiment on MNIST 1-7 where we scale the original box-constraint from (0, 1] to [0, c), >= 1, where is the scale factor and e = denotes the original setting for MNIST 1-7 experiment. The experiments are hypothetical because, in practice, a box-constraint of [0, c) with e will result in invalid images. We experimented with = 2,3,5 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 gradual increase in the "Error Increase" from poisoning.
Change Sep/SD. As mentioned above, in order 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 MNİST 1-7 even when using the same C. We leave the exploration 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 times, replace x 3% of correctly classified training and testing data points that are furthest from the boundary. This process can be viewed as oversampling in the cear-boundary region and undersampling in the region far from the boundary, and aim to create dataset with a low separability ratio. We tested with = 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 and we can see that increase the Scp/SD gradually decreases, and the attack effectiveness (measured by the
better ways to change data distributions with
30

---

Error Increase (%)
22.5
0.20
R-90
R-120
20.0
0.18
R-100
17.5
0.16
R-50
15.0
Sep/Size
0.14
R-25
12.5
0.12
10.0
0.10
R-1
7.5
0.08
5.0
0.06
2.5
LeNet
0.0
3.2
3.4
3.6
3.8
Sep/SD
Figure 5: Impact of feature representations the poisoning effectiveness. The training data of the pretrained model excludes the downstream data of classes "Truck" and "Ship".
Experiments
Sep/SD vs Error Increase
Sep/Size vs Error Increase
New Original
-0.66 (-0.90)
-0.90 (-0.99)
-0.98 (-0.97)
-0.98 (-0.97)
Table 10: Pearson correlation between Error Increase and each of Sep/SD and Sep/Size. The value in the parentheses denotes the Pearson correlation coefficient when we exclude the LeNet structure and only consider ResNet- 18 models.
error increase) increases. Interestingly, the Sep/Size also decreases even though is computed with the same C. Although the preliminary results above not sufficient prove causation claim, they still show the possibility with the empirical evidence on the MNIST 1-7 dataset.
D.2.7 Evaluating feature extractors with downstream data removed
The experiments in Figure 2 uses the entire CIFARIO 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 Figure 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 Figure 5 and the overall finding similar to the one in Figure 2 that when we adopt deep architecture and train it for more epochs, the quality of the obtained feature extractor increases and so, appears 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 Table 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 -0.66 still indicates 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 Table 10, we also compare the new experiment with the original experiment in Figure and observe that the (absolute) Pearson correlation is reduced slightly, which is due 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 cach individual factor with
31

---

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 ervor 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.
E
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) [50] from NeurIPS 2022, which had similar goals in understanding the inherent vulnerabilities of datasets but focused on targeted poisoning attacks (Appendix E.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 (Appendix E.2).
E.1 Relation to LDC
As discussed in Section 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 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 discussion on the relations of the identified vulnerability factors in this paper and the key quantity in LDC.
The main conjecture in LDC. LDC conjectures that, given (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 ((N/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 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.
Overestimating the power of indiscriminate poisoning. LDC conjectures the robustness against targeted poisoning attacks, but the same conjecture can also be used in indiscriminate setting straight- forwardly 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 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 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
32

---

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 injeecttoosnnnectiionn 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 [29] 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 E = 0.5% (250/50000). In contrast, the best indiscriminate poisoning attacks [32] on CIFAR1O 10 dataset reduces the model accuracy from 95% to 31% at the much higher = 3% poisoning ratio using standard training (i.e., using k 1 partition). Note that using k partition is far less optimal choice than k 500 as l = 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 CIFARIO to 0% 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 [31, 32] while our empirical findings in the most extensively studied linear models in Section 3 indicate some datasets might be inherently more robust to poisoning attacks.
Providing finer analysis the vulnerability factors. 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 @ /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- aneer-ranularity.
As for the projected constraint size (Definition 5.5), we believe there can be situations where it may be independent from The main idea that in cases where changing C arbitrarily will not impact the clean distribution (e.g.. when the support set of the clean distribution is a strict subset of C, arbitrarily enlarging 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 C, indicating that the vulnerability of the same dataset remains the same even when C changes drastically without impacting the clean distribution. However, changes in C (and subsequently changes in the projected constraint size) will directly impact the attack effectiveness, as larger C is likely to admit stronger poisoning attacks.
To illustrate how much the attack power can change C changes, conduct experiments MNIST 1-7 and show that scaling up the original dimension-wise box-constraint from [0, 1] to [0, c] (where >>> 1 is the scale factor) can significantly boost attack effectiveness. Table 11 summarizes the results and we can observe that, as the scale factor e increases (enlarged 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 hypothetical example. In practice, for normalized images, the box constraint cannot be scaled beyond [0.1] as it will result in invalid images.
E.2 Relation to Aggregation-based Defenses
Aggregation- (provable) defenses, whose asymptotic optimality implied by the LDC, work by partitioning the potentially poisoned data into & partitions, training 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
33

---

Scale Factor e Error Increase (%)
Sep/Size
1.0
2.2
0.27
2.0
3.1
0.15
3.0
4.4
0.10
Table 11: Impact of scale factor с on poisoning effectiveness for C' in the form of dimension-we wwie box-constraint as [0, cl. Base Error is 1.2%. Base Error and Sep/SD will be the same for all settings because support set of the clean distribution is the strict subset of C.
correctly predict known test point, which can also be straighuforwardly applied indiscriminate setting by treating different test samples independently, as mentioned in the discussion of LDC.
Because data filtering is used for each partition of the defenses, the partition level, our results (i.c., the computed metrics) obtained in each poisoned partition may still be similar to the results obtained the whole data without partition (i.e., standard training, in this paper), the clean data and 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 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 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 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.
Loose certified accuracy in indiscriminate setting. Given a poisoning budget 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 equal total test samples gives the certified accuracy for the test set. Similar to the result of CIFAR10 10 shown in LDC, here, we provide an additional result of certified accuracy for neural networks trained on the MNIST dataset: the state-of-the-ar finite aggregation (FA) method [51] gives a certified accuracy of 0% 1% poisoning ratio (600/60,000 0000) using & = 1200 partitions while at the much higher 3% the-art art indiscriminate poisoning attack [32] can only reduce the accuracy of the neural network trained on MNIST without partitioning (i.e.. k 1. far less optimal choice from the perspective of aggregation defenses) from over 99% to only around 90%.
certifiably robust. Then, the fraction of those test samples the
poisoning ratio, the current state-of- sate--of-hhaaaee
F 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 (Appendix F.I). Then, we provide the idea of extending the metrics from linear models to neural networks (NNs) and also the accompanying experimental results (Appendix F.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 very interesting future work, but is out of the scope of this paper.
F.1 Extension 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"
34

---

Datasets
Base Error (%)
Poisoned Error (%) Increased Error (%)
Sep/SD
Sep/Size
SVM 7.4%
15.4%
8.0%
2.23/2.73
0.06/0.03
LR 7.7%
30.6%
22.9%
1.15
0.02
Table 12: Results of Linear Models on MNIST using 3% poisoning ratio. The "Poisoned Error" is directly quoted from Lu al. [31] and SVM one is quoted from Koh et al. [25]. SVM contains two values for Sep/SD and Sep/Size because there are two binary pairs with the lowest value for each of the two metrics (lowest value is made bold).
mode that results k(k - 1 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 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 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 [25, 32), but classifiers trained in "one one" mode can also be handled similarly.
Computation of the metries. Although we consider linear models in "one vs rest" mode, when computing the metrics, we handle it in way similar to the "one vs one" mode when computing the metrics, given 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 as "fake" negative class and compute the metrics as in the binary classification setting. Then from the A 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 c 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 given positive class, adversaries may target the most vulnerable pair from the total 1 (positive, negative) pairs to cause more damage using the poisoning budget. Therefore, treating the remaining Is - 1 pairs as a whole when computing the metrics will obfuscate this observation and may not fully reflect the poisoning vulnerabilities of dataset.
We provide a concrete example on how treating the remaining classes as a whole can lead to wrong estimates the dataset separability: we first train simple CNN models on the full CIFAR-1O [26] and MNIST datasets and achieve models with test accuracies of x 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 CIFAR-10 has much lower test accuracy compared to MNIST. However, when 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 h 1 classes separately and pick the smallest value, we will again see the expected result that CIFAR-I0 is far less separable than MNIST. Therefore, for the following experiments, we will compute the metries 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 10 and MNIST in Appendix F.2.
Results on multi-class linear learners. 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 directly quoted from the prior works- works-LR error is from Lu et al. [31] and the SVM error is from Koh et al. [25]. 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
We still use the same projected constraint size for the k - positive and "fake" negative pairs because, the projected constraint size measures how much the decision boundary can be moved in presence of clean data points, which do not distinguish the points in the "fake" netgative class and the remaining k 1 classes.
35

---

Datasets
Base Error (%)
Poisoned Error (%)
Increased Error (%)
Sep/SD
Sep/Size
MNIST
0.8%
1.9%
1.1%
4.58
0.10
CIFAR-10 10
31.0%
35.3%
4.3%
0.24
0.01
Table 13: Results on Simple CNN Models for MNIST and CIFAR-10 datasets using 3% poisoning ratio. The "Poisoned Error" of both datasets are directly quoted from Lu al. [31]
Datasets
Base Error (%)
Increased Error (%)
Sep/SD
Sep/Size
MNIST
0.8%
9.6%
4.58
0.10
CIFAR-10
4.8%
13.7%
6.36
0.24
Table 14: Results on Simple CNN Model for MNIST and ResNer1 8 model for CIFAR-10 datasets
using 3% poisoning ratio. The "Poisoned Error" both datasets are directly quoted from Lu et al. [32].
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.
F.2 Extension to Multi-class Neural Networks
We first note that the insights regarding the separability and constraints set 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 metries 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) an example.
High level idea. 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 neural network into metric computations (on feature space) for linear models. To be more concrete, we propose to use 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 's training. Below, we consider the from-scratch training case as it is more challenging.
convert the metric computations for non-linear
Computation of the metrics. 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 C after transforming through the feature extractor can be non-convex and sometimes, for complicated C, computing such transformation can be very challenging (can be a case even for linear models), but a very interesting direction to explore. For the simple forms of C such as the dimension- wise box constraints considered in this paper, we may leverage the convex outer polytope method [53] bound the activation in each layer till the final feature layer so that we can obtain final transformed convex set C' using the feature extractor, which is a set that contains the original C. However, due to time limitation, when computing the projected constraint size the following experiments, we simply set 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 Section? 7.
36

---

0.4
OPT Risk
Empirical OPT Test Error
Best Heuristic Test Error
0.3
Risks
0.2
0.1
0.0
20
40
60
80
100
1
Y2//o
Figure Measuring the performance of optimal poisoning attacks with different values of separability ratio In 722//o. Best Heuristic denotes the best performing attack in the literature.
Results under similar learners. For the experiments, we use the simple CNN models presented Lu et al. [31] for MNIST and CIFAR-10 datasets (similar architecture). We directly quote the attack results of TGDA attack by Lu et al. [31] for both the CIFAR-10 and MNIST datasets. Note that, very recently, a stronger GC attack also proposed by Lu et al. [32] and outperforms the TGDA attack. However, evaluation in the original paper also did not include the simple CNN for CIFAR- dataset. The results shown in Table 13. From the table, we 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 10 may also suggest that the poisoned error for CIFAR-10 10 with simple CNN maybe increased further (e.g., using the stronger attack in Lu et al. [32]).
could not include the newer result because the code is not published and the
that CIFAR-10 tends to be more vulnerable
Results under different learners. Above, we only showed results when the MNIST and CIFAR-10 10 datasets are compared under similar learners. However, in practical applications, one might use deeper architecture for CIFAR-10 and so, we computed the metries CIFAR- using ResNet18 model. Then we compare the metrics of MNIST under simple CNN and the metrics of CIFAR-10 under ResNet18 Table 14, where the poisoned errors are quoted from the more recent GC attack [32] because the attack results are all available in the original paper. However, from the table 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 metrics. If the current attacks are already performing well and the empirical poisoned errors are indeed good approximations to the inherent vulnerabilities, then might have systematically investigate the comparison of vulnerabilities of different datasets under different learners.
G Evaluation on Synthetic Datasets
In this section, we empirically test our theory on synthetic datasets that are sampled from the considered theoretical distributions in Section 5.1.
G.1 Synthetic Datasets
According to Remark 5.4, there are two important factors be considered: (1) the ratio between class separability and within-class variance |y) 72l/a, denoted by 3 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.
37

---

Poisoned Error
0.5
0.4
0.3
0.2
0.0
25
50
75
100
125
150
175
Value of
V2l/o: 10.00
Iy1 Y2/la: 2.50
Iy: V2//o: 1.25
I/: V2l/o: 5.00
ly1 Y2l/a: 1.67
1y1 Y2l/o: 1.00
Figure 7: Impact of the (projected) constraint size u on poisoning effectiveness. u 0 means the test error without poisoning.
More specifically, we generate 10,000 training and 10,000 testing data points according to the Gaussian mixture model (2) with negative center yn -10 and positive center 72 0. Throughout our experiments, and 7/2 are kept fixed, whereas we vary the variance parameter a and the value of The default value of is set as 20 if not specified. Evaluations of empirical poisoning attacks require training linear SVM models, where we choose À = 0.01. The poisoning ratio is still set as 3%, consistent with evaluations the benchmark datasets.
Impact 3. First, we show how the optimal attack performance changes as we increase the value of B. We report the risk achieved by the OPT attack based on Theorem 5.3. Note that obtain approximations
only the inverse function g using numerical methods, which may induce small approximation eπrо for evaluating the optimal attack performance. For the samele 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 Section 3, where the latter is termed Best Heuristic for simplicity. Since the poisoned models induced by these empirical attacks do not restrict E {-1, 1}, normalize w make the empirical results comparable with our theoretical results.
Figure summarizes the attack performance when we vary B. 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 3 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 the small numerical error induced by approximating the inverse function g-
Impact of u. Our theoretical results assume the setting where w E (-1,1). However, this restriction makes the impact of the constraint set size less significant, as it is only helpful judging whether flipping the sign of w is feasible and becomes irrelevant to the maximum risk after poisoning when flipping infeasible. 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 Appendix G.2).
contrast, if ur is not restricted, the impact of u will be more significant as
To illustrate the impact of in continuous way, we allow w 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.3. Instead, we use the poisoning attack inspired by our theory to get an empirical lower bound on the maximum risk. Since ?1 + 72 < 0, Theorem 5.3 suggests that optimal poisoning should place poisoning points on u with label We simply use this approach even when can now take arbitrary values. We vary the value of gradually and record the test error the induced hypothesis, We repeat this procedure for different dataset configurations (i.c., fixing 71, 72 and varying σ)).
when w 11)-
38

---

Poisoned Weight W
0.2
0.1
0.0
25
50
75
100
125
150
175
Value of
V2l/o: 10.00
Iy1 Y2lla: 2.50
Iy: V2//o: 1.25
I/: V2l/o: 5.00
ly1 Y2/la: 1.67
1y1 Va//o: 1.00
Figure 8: Impact of the (projected) constraint size u on the value of after poisoning in 1-D Gaussian distribution.
The results are summarized in Figure 7. There are two key observations: (1) once w is no longer constrained, if is large enough, the vulnerability of all the considered distributions gradually increases as we increase the value of u, and (2) datasets with smaller 3 are more vulnerable with the increased value of compared to ones with larger 3. which has larger increased same class separability and box constraint (choosing other values of 5 also reveals a similar trend). Although not backed by our theory, it makes sense as smaller 33 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.
error under the
G.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, for mee-imensioonll case, while in practical machine learning applications, convex models are trained by optimizing the hinge loss with respect to both parameters w and 6, which can result in 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:)) in the norm so as to minimize the large loss introduced by the extreme points. Figure 8 plots the relationship between and of poisoned model, and supports the statement above. When the norm w becomes smaller, the original clean data that are well-separated also becomes less separable 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.
39


Reviews:
[{"review_id": "F8rHdpCx0R", "reviewer": "Reviewer_5jje", "summary": "This paper explores the issue of data poisoning attacks on machine learning models, focusing on linear models. The authors find that the effectiveness of state-of-the-art poisoning strategies varies across different datasets. They introduce definitions of optimal poisoning attacks for finite-sample and distributional settings and prove performance convergence under certain conditions. They also characterize optimal poisoning attacks under a theoretical Gaussian mixture model and find that a larger projected constraint size is linked with higher vulnerability, while larger separability and smaller standard deviation provide less vulnerability. These findings explain the performance differences of indiscriminate poisoning attacks on linear models across various datasets and suggest ways to improve robustness against poisoning.", "questions": "- Is the resistance of some linear learners to attacks, even without defenses, a new finding or reported in previous studies?\n\n- How applicable are these findings to non-linear classifiers like neural networks? Do they imply greater inherent robustness of linear classifiers against attacks?", "limitations": "In summary, this paper makes a substantial contribution to the field. Although its primary limitation is its exclusive focus on linear classifiers, it effectively elucidates the observed phenomena within this scope.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The observation that the performance of state-of-the-art poisoning strategies significantly varies across different datasets is indeed insightful. It not only challenges the common understanding of indiscriminate poisoning attacks but also opens up new lines of inquiry into why these differences occur.\n- The theoretical analysis under specific data distributions is a major strength of this paper. It's robust, reliable, and underpins a comprehensive understanding of how and why different datasets might be more or less vulnerable to poisoning attacks. By tying the theoretical analysis back to empirical attack performance, the authors effectively bridge the gap between theory and practice, enhancing the practical relevance of their findings.", "weaknesses": "- It's not explicitly clear from the paper whether the observation that \"linear learners on some datasets are able to resist the best-known attacks even without any defenses\" is novel or previously reported. The authors could benefit from addressing this explicitly. \n\n- The authors' focus on linear classifiers is indeed a limitation. While the paper provides valuable insights into data poisoning attacks on linear models, these findings cannot be directly extrapolated to non-linear classifiers such as neural networks. Moreover, the paper does not provide enough information to definitively conclude whether linear classifiers are more robust than non-linear classifiers without additional defense strategies.\n\n-  The paper doesn't sufficiently distinguish its analysis from existing works on data poisoning that also provided theoretical analysis on Gaussian mixture distributions and linear classifiers, such as [1]. Could you elaborate on this?\n\n\n\n[1] Tao, Lue, et al. \"Can Adversarial Training Be Manipulated By Non-Robust Features?.\" Advances in Neural Information Processing Systems 35 (2022): 26504-26518.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Is the observation of \"linear learners being robust to poisoning on some datasets\" a novel observation or previously reported?**\n\nYes, we are the first to explicitly report the results that linear models can resist the current state-of-the-art poisoning attacks on some datasets by running the state-of-the-art attacks on various benchmark datasets without considering additional defenses. In contrast, previous literature did not clearly show the robustness of linear models to poisoning without defenses.\n\nHowever, we note that the disparate effectiveness of current indiscriminate poisoning attacks across different datasets (in settings different from ours) is reported in prior work. For example, Steinhardt et al. [1] observed that datasets such as MNIST 1-7, when equipped with an oracle defense, can be highly robust to state-of-the-art poisoning attacks while the Enron dataset is highly vulnerable even with defenses. Recently, Lu et al. also observed that attack effectiveness might vary across datasets for neural networks in two recent works [2], [3]. However, these works either consider additional defenses and obfuscate the impact of original distributional properties on poisoning effectiveness [1], or the empirical observations are for neural networks, which are also found to be harder to poison than the linear models [3].\n\n2. **How applicable are these findings to non-linear classifiers such as neural networks? Do they imply greater or lesser inherent robustness to attacks compared to linear models?**\n\nWe merged the related questions mentioned in the \"Weakness\" and \"Questions\" sections to provide a more focused response. \n\nWe provide the initial thoughts on extending the analysis on linear models to neural networks and some preliminary experiments in Appendix F (with a pointer to the appendix in page 7 in the main paper, right below Definition 5.6). Although our results show that the insights on linear models may also be relevant when the victim uses similar network architectures for different datasets (e.g., MNIST, CIFAR10), this conclusion still requires more in-depth investigation, which is beyond the scope of this paper. \n\nAs for the robustness comparison between linear and non-linear models such as neural networks, we first clarify that our paper is not to make a claim that linear models are more robust than non-linear models such as neural networks without defenses. We only study the impact of distributional properties on poisoning effectiveness for linear models. In fact, prior literature actually shows the opposite that non-linear models such as neural networks are (currently) harder to poison than linear models. This is backed up by the fact that, indiscriminate attacks on neural networks are not very successful and some good progress is made only very recently [2], [3]. However, even with the state-of-the-art attack on neural networks, for the same dataset, neural networks are still harder to poison than the linear models. For details, please see the attack results on LR and NN that are trained on the full MNIST dataset at 3% poisoning ratio in Table 2 in Lu et al. [3], where the increased error of LR is around 23\\% while the error increase of NN is only around 6\\%. We will add a clarifying sentence in the revised version to avoid confusion. \n\n\n3. **The distinction to the work by Tao et al.** \n\nWe appreciate the reviewer for bringing this paper to our attention. We also discover another work on poisoning attacks that conducts rigorous analysis on Gaussian mixture models and then empirically validates the idea on benchmark datasets [4]. \n\nCompared to the paper pointed out by the reviewer, the major distinction is, our work considers a threat model where the attacker generates poisoning points to impact the clean accuracy of the poisoned model that is obtained from natural (or standard) training, while the mentioned work considers the generation of poisoning points to compromise the robust accuracy of the model obtained through adversarial training, and the attack did not focus on reducing the model accuracy on clean test samples. Different from us, the work by Tao et al. [4] focuses on demonstrating how adversarial training can help defend against data poisoning attacks.\n\nAnother distinction of our work from the two reference papers is, the reference papers consider the poisoning setup where the feature perturbations have bounded norms and the labels are still correct (i.e., the poisoned data points are still semantically meaningful), and the entire dataset can be modified by the attackers. However, our poisoning setup only allows attackers to inject a small fraction of poisoning points and the generated poisoning points do not have to be obtained by adding bounded perturbations to existing data points and their labels can also be freely assigned, as long as the generated poisoning points fall into the constraint set $\\mathcal{C}$ defined in the paper. We will properly discuss the mentioned papers in our revised version. \n\n4. **Focus on linear models is indeed a limitation**\n\nWe think studying linear models is still valuable (as argued in the introduction) and much can still be learned from analyzing these simple models. For example, attacks on the convex (e.g., linear) models [5] can also inspire the design of attacks on non-convex models given some proper adaptation and invention [3].\n\n[1] Steinhardt et al., \"Certified defenses against poisoning attacks\", N(eur)IPS 2017. \n\n[2] Lu et al., \"Indiscriminate Data Poisoning Attacks on Neural Networks\", TMLR 2022.\n\n[3] Lu et al., \"Exploring the Limits of Model-Targeted Indiscriminate Data Poisoning Attacks\", ICML 2023.\n\n[4] Tao et al., \"Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training\", NeurIPS 2021.\n\n[5] Koh et al., \"Stronger Data Poisoning Attacks Break Data Sanitization Defenses\", Machine Learning 2022. "}, {"review_id": "x8OnclZj8T", "reviewer": "Reviewer_J4a4", "summary": "Inspired by the variant performance of indiscriminate data poisoning attacks against different datasets, this paper studies the inherent robustness of datasets against them. Using an optimal attack designed for a binary Gaussian dataset, the authors discover three properties, namely class separability, variation, and constraint size are important factors to determine the robustness of a dataset. Experiments further validate the theory on several datasets. ", "questions": "Questions are listed above.", "limitations": "Limitations are well addressed.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1) This paper studies an important problem, namely the dataset robustness against indiscriminate data poisoning attacks.\n\n(2) The authors provide initial but valuable evidence on understanding the vulnerability of datasets by explicating the three properties. Although these characteristics match our intuitive understanding of the problem, they have not been systematically analyzed or studied.\n\n(3) The empirical findings, especially the results in Section D, are nicely presented and very comprehensive. Moreover, I can find answers to most of my initial questions when reading the main paper in the appendix.", "weaknesses": "(1) I don't find the title a nice summarization of the entire paper as it is probably too general. I would suggest mentioning the dataset robustness in the title.\n\n(2) I don't think comparing with LDC is necessary as I clearly see the drastic difference. I suggest the authors move this part to the appendix and present some more valuable content in the main paper, e.g., some experiments in Appendix D.\n\n(3) Although it has been mentioned in the appendix, I think it is important to mention what attacks you use to generate Table 1. The authors should at least provide a pointer to the appendix.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for acknowledging our work for providing the initial but valuable step towards understanding the impact of distributional properties on robustness of linear learners against poisoning attacks. Please see our individual responses below.\n\n1. **Set title to be more focused** \n\nThanks for the suggestion and we are considering to change the title as *When can Linear Learners be Robust to Indiscriminate Poisoning: A Distributional Perspective*. We are inclined towards discussing the robustness with respect to distributions, instead of datasets, as distributional properties perhaps denote the underlying reasons that contribute to the dataset robustness in practice.\n\n2. **Shrink the content on LDC and discuss more on experimental results**\n\nWe will move part of our results in Section D of the appendix to the main paper in the revised version.\n\n3. **What attacks are used to generate table 1**\n\nThe poisoned error in Table 1 denotes the highest poisoned error returned from the four empirical attacks mentioned in the experimental setup in Section 3. We will clarify this part and add a pointer to the appendix in the main paper. "}, {"review_id": "K6hedMiXBy", "reviewer": "Reviewer_Ya9d", "summary": "This paper delves into the impact and effectiveness of indiscriminate data poisoning attacks on machine learning models, particularly linear ones. It highlights significant variations in attack effectiveness across different datasets and seeks to understand whether this is due to inherent dataset robustness or shortcomings in current attack strategies. The paper presents optimal poisoning definitions, characterizes these attacks under a theoretical Gaussian mixture model, and identifies learning task properties that affect attack performance. It concludes with suggestions for designing better defenses against such attacks.", "questions": "- The format of figure out is confusing. \n  - Are the bars stacked? \n  - Caption mentions “Datasets are sorted from lowest to highest base error rate”. Does this mean the error rate of the SVM trained on $S_c$? \n  - Please change the color palette to more distinguishable colors. \n\n- The paper analysis is restricted to linear models. Would any of these insights hold for more complex models? Did the authors do any (empirical) investigation there? In particular, it would be interesting if the authors find that high Sep/SD and Sep/Size metrics are indicative of lower vulnerability to poisoning in more general neural networks and on datasets such as CIFAR-10 and ImageNet.\n\n- Are the percentage changes in the results paragraph in Line 157 absolute or relative? I believe it is absolute, but would be helpful to clarify that.\n\n### Minor\n\n- Line 123: What is a “theoretic game”?\n- Line 278: an higher-> a higher\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The question the paper is trying to answer, of whether some datasets are inherently robust to poisoning attacks or just resilient to state-of-the-art attacks, is original and interesting.\n- The paper flows smoothly and is decently written, but contains some grammatical mistakes and typos (some of which I mention below). A careful proofread can increase the quality of writing quite a bit.\n- The paper is sound, and the claims are proved on 1D toy Gaussian mixture model then extended to more complex data distributions. \n- The empirical results support the theoretical results. Specifically, on various datasets, the results show that the datasets that are less vulnerable to poisoning have higher values for metrics defined by the paper (Sep/SD and Sep/Size).\n", "weaknesses": "- The contributions of the paper is not very significant as there is no clear practical implication of the findings of the paper. However, the paper investigates an interesting phenomenon of \"inherent robustness\" of some datasets which might inspire further investigations of this sort.\n- The paper analysis is restricted to linear models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **No clear practical implications from this paper**\n\nWe appreciate that the reviewer agrees that our work might inspire the future investigation on the inherent robustness of datasets. As for the possible practical future implications, we present some preliminary results in the discussion section (Section 7) with a hope that our results may provide additional insights on building robust systems against poisoning attacks in the future. \n\n2. **Analysis is only limited to linear models. Are there any empirical investigations on neural networks?**\n\nWe do provide the preliminary results on neural networks (trained on the full MNIST and CIFAR10) in Appendix F and put a pointer to the appendix in the text right below Definition 5.6 in page 7. Our analysis show that, when the victim uses similar architectures for different datasets, the insights on linear models might also generalize, but more in-depth investigation is needed to make some definitive claims. However, this investigation is out of the scope of this paper and is an interesting next step. \n\nWe also note that, although our analysis is limited to linear models, we think it is valuable to investigate linear models (as stated in the introduction) and much can still be learned from analyzing the simpler models. For example, attacks on linear models [1] can inspire the design of attacks on deep neural networks given proper adaptation and invention [2]. \n\n[1] Koh et al., \"Stronger Data Poisoning Attacks Break Data Sanitization Defenses\", Machine Learning 2022. \n\n[2] Lu et al., \"Exploring the Limits of Model-Targeted Indiscriminate Data Poisoning Attacks\", ICML 2023.\n\n3. **Other issues such as format of Figure 1 and absolute error increase** \n\nFor Figure 1, yes, the bars were originally stacked with a hope to concisely represent all the information in one figure. Even though stacked, the height of each bar should be interpreted as the absolute value of the final errors (corresponding to absolute errors trained on $\\mathcal{S}_c$ or $\\mathcal{S}_c\\cup\\mathcal{S}_p$), not increased errors. The datasets are sorted based on the base error trained on $\\mathcal{S}_c$ and because the base errors of LR and SVM have the same orders for the tested datasets, the potential ambiguity between two models is eliminated. We will clarify this in the figure caption. Further, we will divide Figure 1 into two figures that individually show the results of SVM and LR, and use two bars to show the errors of the models trained on $\\mathcal{S}_c$ and $\\mathcal{S}_c\\cup \\mathcal{S}_p$ respectively, and will choose the colors more wisely to make the bars more distinguishable. \n\n\"Theoretic game\" was intended to mean \"game theoretic formulation\", and we will simply name it as \"game\". The percentage changes in line 157 is the absolute change and we will add clarification to it. "}, {"review_id": "fFrKl8pHnL", "reviewer": "Reviewer_oRg1", "summary": "This paper explores poisoning attacks on linear classifiers.  Specifically, the authors explore why poisoning attacks may have high efficacy on one dataset but low efficacy on another.  The authors relate this phenomenon to two potential factors: (1) (projected) constraint set size and separability. The authors theoretically characterize an optimal poisoning attack w.r.t. Gaussian mixture data.", "questions": "* Eq. (2) allows the two Gaussian distributions to have distinct variances (e.g., $\\sigma_1$ and $\\sigma_2$). In Theorem 5.3, you specify the two variances as equivalent. Is Theorem 5.3's equivariance specification for convenience in the proof or a necessity?\n\n* On Line 155, you wrote, \"*We chose 3% as the maximum poisoning rate.\" I found this confusing wording. I understanding \"maximum poisoning rate\" is terminology you use in the theoretical discussion.  When discussing experiments you perform, defining your poisoning rate w.r.t. a *maximum* implies to me you tested multiple poisoning rates. However, I do not get that indication elsewhere in the paragraph.  Please be precise concerning your experimental setup.\n\n* Figure 1 uses the \"Filtered Enron\" dataset.  I am not familiar with the filtered version of the Enron dataset. Is this filtering procedure something you performed or an existing dataset? How do the results change if you use the vanilla Enron dataset?  If you filtered the dataset yourself, I believe the paper should explain why that filtering was done, not just how it was performed.\n\n* Your preliminaries section specifies a few design choices. For example, you restrict consideration to primarily hinge loss. Moreover, you specify an L2 regularizer (Eq. (1)). As a reader, I am somewhat left to guess why these specific choices are made. For example, I assume you chose hinge loss because you want max margin.  Concerning regularizer, I was unsure if L2 was for convenience and whether a different convex regularizer (e.g., L1) could be used. If you are focusing on specific design choices, I believe it is better to explain why.\n    * I do not recall any of the theorems requiring specifically the hinge loss as opposed to alternate convex losses.\n\n* Lines 183-184 state, \"Definition 4.1 *suggests* that no poisoning strategy can achieve a better attack performance than that achieved by $\\mathcal{A}_{opt}$\" When reading this, I was confused by the choice of the word \"suggests,\" as given $\\epsilon$, I found Def. 4.1 clearly stated no alternate strategy achieves better attack performance.\n\n* One criterion for Theorem 4.5 to hold is that the support of $\\mu_c$ should be a (proper) subset of $\\mathcal{C}$.  I believe this criterion does not hold in the optimal Gaussian case given the definition of $\\mathcal{Q}(u)$.  If so, please explain how that affects your results (including the proof). Ideally, this should be more explicit in the paper.\n   * Searching through the paper, I did not see where $\\mathcal{Q}(u)$ was used beyond line 246. Perhaps I missed it. If it is just for that one point, I think it is worth removing.", "limitations": "Better understanding what causes attacks to fail could lead to enable better attacks.  At the same time, it can lead to better defenses.  I see no serious ethical or societal risks for this work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Previous work has repeatedly shown that poisoning attacks represent a real and serious threat to machine learning models.  Most work in the field focuses on how to design better attacks or better defenses.  An improved theoretical understanding of what mechanisms allow an attack to work could accelerate research for both attacks and defenses.  In my view, this represents a challenging, under-explored research topic. This paper makes an incremental step into improving understanding in this area.", "weaknesses": "I rate the paper as borderline reject and explain my rationale below. I want to make clear that with a thoughtful rebuttal and changes to different aspects, I could definitely see my score increasing.\n\nWhile the paper has many things I like, it is my view that the paper still needs work.  Perhaps the biggest problem is that the writing tends to overclaim results or draw conclusions that, as written, are not well supported.  I discuss a couple of cases below under \"Experimental Results.\" I also ask multiple questions about points I had concerns with in the \"Questions\" section below.\n\n* A more harmless example of what I perceived as overclaiming is on lines 42-43, which state, \"we consider indiscriminate poisoning attacks for linear models, *the most commonly studied victim models in the literature* (emphasis added). It is not my assessment that linear models are the most commonly studied victim model, particularly recently. Reading this sentence, it felt to me that the authors were stretching to over-justify the paper's restriction to linear models. This is despite the subsequent sentences being more than adequate to justify the choice, e.g., \"linear models are still not well understood\" and \"high interpretability.\"\n\n* A second example is on lines 35-36, which state \"the reasons why attacks are sometimes ineffective have not been previously studied.\"  I do not know this statement to be true and expect given other work (e.g., the lethal dose conjecture) that this is not true.\n\n**Experimental Results**\n\nMy biggest concerns are around the experimental results and the conclusions drawn from them. \n\n* Lines 343-344 state, \"Table 1 summarizes the results show that Sep/SD and Sep/Size can *largely* explain why datasets...are harder to poison than others.\" In my view, this statement is making primarily a causation claim. However, the results in the table provide primarily correlation results.  To make a causation claim (which I think is the appropriate type of claim for this paper to try to make), the experiments should externally vary the separability and measure how the performance changes.  I realize that is non-trivial, but I believe it is the right type of experiment here.  \n\n* Lines 390-392 state, \"Although limited in effectiveness, the defense still mitigates the poisoning to some degree *mostly by shrinking the projected constraint size*\" I do not see how the empirical results as presented can support such a strong claim.  As written, the text may barely support the claim that smaller projected constraint size *partially* helps (a weak, not that meaningful claim). To justify *mostly* a lot more is needed.\n\n* Section 7 Better Feature Representation: Lines 363-364 state, \"We train LeNet and ResNet18 on the CIFAR10 dataset...\" From this sentence, it is my understanding that your pretraining was done on all 10 classes.  If so, your feature encoder goes beyond the transfer learning setting, and I believe this approach does *not* correspond with \"the practical scenario where the victim has access to some *small number* of clean samples...\"\n\n* On lines 360-361, we present two ideas -- using better features might improve separability and using data filtering might reduce the projected constraint size.\" I would expect data filtering would both improve separability and reduce the constraint size.  The paper should explain how you are ensuring filtering is only affecting one criteria and not the other.  \n\n* I understand why the authors chose to lay out Figure 1 as they did.  However, I did not find the overlapping bars were the best format.  I was initially confused by the formatting, and it took me some time to figure out exactly what was being visualized since I expected multiple attacks, but only saw two bars.\n\n**Miscellaneous Comments**\n\n* Overall, I found section 5.1 notationally cumbersome and lacking a clear structure and flow. I had to re-read it twice to extract all the main points.  One possible fix is to provide more intuition about why each is being proposed and how the pieces relate.  It felt as though you gave a lot of disparate pieces of information to the reader without walking them through how they fit together as you went alone\n\n* Lines 40-41 state, \"An attack is considered ineffective if the increased risk from poisoning is roughly equal to or smaller than the injected poisoning rate.\"  This perspective makes sense, but it took me a minute to understand the definition as stated. I think this sentence could be written more intuitively.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first respond to concerns about the experiments and conclusions we draw. To utilize space, we also respond to the last comment from the **Questions**. For other unaddressed comments, we will reflect them in the revised version. \n\n1. **Statement on results in Table 1 is trying to make a causation claim, but results are correlation results**\n\nWe should have been more careful in our writing, but did not mean to claim a causation result from Table 1, as it only shows the correlation between the factors and the empirical vulnerabilities to poisoning. We will revise our statement to make it explicit that we are showing the correlation, not causation. We will revise the writing to avoid any unfounded implications of causation, and to ensure we explicitly mention where needed that we found factors that are correlated to the disparate attack effectiveness across datasets. \n\nWe also speculate our factors might cause vulnerability to poisoning due to the following reasons, but these are just some partial evidence and may not be sufficient to provide a definitive answer. We also clarify that we are not claiming our factors are the only factors that might cause the vulnerability. First, for the 1-D Gaussian example, we exactly characterized the optimal poisoning attacks and then provided an upper bound on the performance of optimal attacks for general distributions. And indeed, when the separability ratio (Sep/SD) is high and the projected constraint size (Size) is small, the distributions will be less prone to poisoning. \n\nSecond, limited empirical results (due to computing constraints, running all the attacks on large number of datasets is infeasible) might also provide partial evidence for the possible causation from the two factors (Sep/SD and Sep/Size) to the poisoning vulnerability. In particular, as suggested by the reviewer, we vary one factor (ideally with another one fixed) externally and then measure the performance changes in the tested attacks.\n\nWe conducted new experiments on MNIST 1-7. We changed the distributions of MNIST 1-7 such that the Sep/SD could change gradually while, ideally, the Sep/Size could remain the same. However, in practice, keeping Sep/Size (or Size) fixed is hard because the computation of Size depends on the clean boundary, which is again dependent on the (modified) clean distribution. Therefore, even if we use the same constraint set $\\mathcal{C}$ for different modified datasets of MNIST 1-7, the Size or Sep/Size can be different. Below is the detail of our modification. \n\nWe first train a linear SVM on the original MNIST 1-7 dataset. Then, we pick 3% of correctly classified points that are closest to the clean boundary. These points, once repeated $x$ times, replace $x \\cdot$3% of correctly classified 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$ and applies to both the training and test data. 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 1 in the attached PDF file in the global response. As mentioned above, even using the same $\\mathcal{C}$ for all modified datasets, we still failed to keep the Sep/Size unchanged. We leave the exploration of better ways to change data distributions with the Sep/Size fixed as future work. From the table, we 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 with the same $\\mathcal{C}$. \n\nFor Size (or Sep/Size), its impact can be measured more easily as we can change $\\mathcal{C}$ without impacting the clean distribution, which means Sep/SD can be fixed. We performed a hypothetical experiment where we scale the original box-constraint from $[0,1]$ to $[0,c]$, where $c\\geq 1$ is the scale factor and $c=1$ denotes the original setting for MNIST 1-7. 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 2 in the attached PDF file. From the table, we see 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. \n\nAlthough the preliminary results above are not sufficient to prove a causation claim, they still show the possibility with partial evidence. \n\n\n**(Questions) The first criterion of Thm 4.5 does not hold for 1-D Gaussian**\n\nThis is a great point and we should have made it clear in the paper. For the 1-D Gaussian example in Sec 5.1, it holds based on the second criterion in Theorem 4.5 and will not impact the results and proofs. In particular, to satisfy the criterion, since $\\boldsymbol{\\theta}=(w,b)$ and $w\\in$ { +1,-1}, given a $(w,b)$, we only need to concern with the gradient of $b$ w.r.t the hinge loss. If there is a valid point $(x,y)$ with zero gradient, then $\\mu$ only contains that $(x,y)$. If no such point exists, then we pick any two valid points with different labels and $\\mu$ has equal 50\\% probability on each point. \n\nThe remaining comments on the experimental results are related to the experiments in the discussion section (Section 7). We note that, the purpose of Section 7 is to identify possible implications from our work and support the claim through some preliminary results. This is not the major contribution of this work but rather provides partial evidence on leveraging the insights in this paper to build better defenses in the future. Therefore, we will revise the wording carefully to avoid making strong claims. **The remaining (detailed) responses are in the global response above.**"}]

Author rebuttal:
We continue to respond to reviewer oRg1 in the global response due to space constraints and also attach the new result tables as a single PDF. Comments from other reviewers are addressed in the individual rebuttals. 

2. **For results on data sanitization defenses, to justify "mostly by ...", a lot more is needed. Also, Why does filtering only affect the projected constraint size?**

In the original submission, we meant to use "mostly" to indicate that the projected constraint size (Size or Sep/Size) is impacted more significantly compared to the separability ratio Sep/SD, but realized that this wording is misleading and may even give an impression of causation-like claims. We included detailed results in Table 3 in the attached PDF file (can also be found in Table 4 of Appendix D in the original submission), we can see that after filtering, the Sep/SD does not change much while the Sep/Size (or Size) is changed significantly. This also answers whether data filtering is going to impact both factors. At least for the tested datasets, the Sep/SD is minimally impacted while there is a significant impact on the Sep/Size. 

We will revise our statement to indicate that the reduction in attack effectiveness is correlated with the significant reduction in the Size, and this high correlation provides possible explanations on why data sanitization defenses work, to avoid the issue of (strong) causation-like claims. 

3. **Experiments on better feature representation do not correspond to the practical scenario of ...**

We are not absolutely sure if we get the reviewer's comment correctly. We will clarify based on our current understanding, so please correct us if we misunderstood your comment. 

First, we clarify that we provide this transfer learning experiment mainly for the purpose of showing a potential implication of our work: it is possible for the victim to select a better feature extractor (assuming it is free from poisoning) to improve the resilience of the downstream classifiers to indiscriminate attacks. 

The reviewer is correct that the whole CIFAR-10 dataset is used to train different feature encoders in this experiment as an illustration. In practice, the victim can go beyond this experimental setup to leverage any pretrained feature extractor (free from poisoning), which we believe is one typical transfer learning setting. We only use the CIFAR-10 dataset in this experiment instead of higher-resolution image datasets (e.g., ImageNet), just for the convenience in obtaining different feature extractors by training from scratch. In addition, we assume the victim has access to a small number of clean samples to set the box-constraints for the feature representation space. These clean samples are neither related to the pretrained feature extractor nor used to train the downstream classifier. While assuming a pretrained encoder free from poisoning may be strong for many practical applications, there are situations where there can be a one-time centralized effort to clean a large benchmark dataset to train some high-quality feature extractors free from poisoning and enable diverse downstream applications. Again, we want to emphasize that the presented results serve to point out potential implications of our work on building better defenses. It is an interesting future work to relax these assumptions to build more practical defenses for real-world scenarios.

4. **About Figure 1**

Please see the response to reviewer Ya9d for the revision plans. The poisoned error is the highest poisoned error among the errors from the four tested attacks. We did not include the results of multiple attacks because we are only concerned about the best-performing attack. The performances of individual attacks are given in Figure 4 in Appendix D, where they are similar in many cases. 

Below are the remaining major concerns in the **Questions** section. 

**Why same variance in Theorem 5.3?** 

The same variance is assumed simply for convenience in the proof without involving minor but tedious calculations. Similar conclusions can be obtained using different variances.

**How is Filtered Enron obtained? Comparison to the Enron dataset?**

The Filtered Enron is obtained by first training a linear SVM on the original Enron dataset and then removing 3\% of points (in both the training and test data) that are closest to the boundary. As mentioned in Section 6, the purpose of this dataset (together with Adult) is to show one cannot trivially infer the vulnerability of a dataset to poisoning by checking its base error without poisoning. As shown in Figure 1 and Table 1 in the paper, both the Filtered Enron and the Enron are highly vulnerable, but the Filtered Enron has the lowest base error among all the tested datasets. 

**Is hinge loss specifically required?**

Thanks for raising this question. Indeed, some of our statements are not very clear, so we provide clarifications below and will revise accordingly.

For all the theoretical results, we require the loss function for model training to be strongly convex, since we make use of the fact that the minimizer of a strongly convex loss function is unique to prove Theorems 4.3 and 4.5. Such a strong convexity condition is also used in Section 5, because we use Theorem 4.5 to justify the choice of the maximum poisoning budget. So, our results can be applied to any regularizer that can ensure the strong convexity of the loss function, including the typical $\ell_2$-regularization studied in this work and more broadly, the elastic net regularization. 

The results in Section 4 apply to general convex loss (with the regularizer, the whole loss is strongly convex). In Section 5.1, we study hinge loss in particular for the convenience of mathematical derivations but believe similar results can be proven for other margin-based convex losses such as logistic loss (but maybe more tedious). In Section 5.2, we study any margin-based convex losses, not just the hinge loss. 

Meta-review: Most reviewers were generally happy with this paper from the start, only Reviewer oRg1 was unconvinced. Through a significant back and forth, the reviewer and the authors settled their disagreements. The reviewer was pleased with the engagement from the authors, and trusts them to make the changes that they promised to all the reviewers. In my own evaluation, I tend to agree -- that trying to understand which datasets are or aren't poisonable is a very interesting direction, and the authors take a promising step in this direction. Thus, I recommend the paper for acceptance.
Decision: Accept (poster)