A Separation Result Between Data-oblivious and Data-aware Poisoning Attacks
Authors: Samuel Deng
Sanjam Garg
Somesh Jha
Saeed Mahloujifar
Mohammad Mahmoody
Abhradeep Guha Thakurta
Venue: NeurIPS 2021 Poster (2021)
Keywords: Poisoning Attacks
Separation Theorem
Data Oblivious

Abstract: Poisoning attacks have emerged as a significant security threat to machine learning algorithms. It has been demonstrated that adversaries who make small changes to the training set, such as adding specially crafted data points, can hurt the performance of the output model. Most of these attacks require the full knowledge of training data. This leaves open the possibility of achieving the same attack results using poisoning attacks that do not have the full knowledge of the clean training set.
In this work, we initiate a theoretical study of the problem above. Specifically, for the case of feature selection with LASSO, we show that \emph{full information} adversaries (that craft poisoning examples based on the rest of the training data) are provably much more devastating compared to the optimal attacker that is \emph{oblivious} to the training set yet has access to the distribution of the data.  Our separation result shows that the two settings of data-aware and data-oblivious are fundamentally different and we cannot hope to achieve the same attack or defense results in these scenarios. 

A Separation Result Between Data-oblivious and Data-aware Poisoning Attacks
Samuel Deng Columbia University
Sanjam Garg UC Berkeley and NTT Research sanjang@berkeley. edu edu
Somesh Jha University of Wisconsin jha@cs. wisc
samdeng@es.com co..oummiaa.
Saeed Mahloujifar
Mohammad Mahmoody University of Virginia mohammad@virginie edu
Abhradeep Thakurta Google Research Brain Team athakurta@google. com
Princeton efar@princeton.com edu
Abstract
Poisoning attacks have emerged significant security threat machine learning algorithms. It has been demonstrated that adversaries who make small changes to the training set, such adding specially crafted data points, can hurt the perfor- mance of the output model. Some of the stronger poisoning attacks require the full knowledge of the training data. This leaves open the possibility of achieving the same attack results using poisoning attacks that do not have the full knowledge of the clean training set. this work, we initiate theoretical study of the problem above. Specifically, for the case of feature selection with LASSO, we show that full information adversaries (that craft poisoning examples based on the rest of the training data) are provably stronger than the optimal attacker that is oblivious the training set yet has access to the distribution of the data. Our separation result shows that the two setting of data-av aware and data-oblivious are fundamentally dif- ferent and we cannot hope to always achieve the same attack or defense results these scenarios.
Introduction
Traditional approaches supervised machine learning focus a benign setting where honestly sampled training data is given to learner. However, the broad use of these learning algorithms in safety-critical applications makes them targets for sophisticated attackers. Consequently, chine learning has gone through a revolution of studying the same problem, but this time under so-called adversarial settings. Researchers have investigated several types of attacks, including test- time ka. evasion attacks to find adversarial examples) (62 7 32 555, training-time attacks (a.k.a.,
poisoning causative attacks) 3. 51]] backdoor attacks [67 331, membership inference attacks
(57], etc. In response, other works have put forth several defenses [52, 43, 9 followed by adaptive attacks [15 2 65] that circumvent some of the proposed defenses. Thus, developing approaches that are based on solid theoretical foundations (that prevent further adaptive attacks) has stood out as an important of investigation.
Poisoning Attacks. a poisoning attack, an adversary changes a training set of examples into a "close" training set S' (The difference is usually measured by Hamming distance; i.c., the number of examples injected and/or removed.). Through these changes, the goal of the adversary, generally speaking, is to degrade the "quality" of the learned model, where quality here could be interpreted in different ways. In a recent industrial survey (39]) poisoning attacks were identified as the most important threat model against applications of machine learning. The main reason behind the im- portance of poisoning attacks are the feasibility of performing the attack for adversary. As the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

data is usually gathered from multiple sources, the adversary can perform the poisoning attacks by corrupting one of the sources. Hence, it is extremely important fundamentally understand this threat model. In particular, we need to investigate the role of design choices that are made in both poisoning attacks and defenses.
Does the attacker know the training data? The role of knowledge of the clean training set is one of the less investigated aspects of poisoning attacks. Many previous work on theoretical analysis of poisoning attacks implicitly, or explicitly, assume that the adversary has full knowledge of the
training data S before choosing what examples to add or delete from S [38. 58 44 61]]. In several natural scenarios, an adversary might not have access to the training data before deciding on how to
tamper with it. This has led researchers to study poisoning attacks that do not use the knowledge of the training set to craft the poison points. In this work, we explore the following question:
What is the role of the knowledge of training set in the success of poisoning adver- saries? Can the knowledge of training set help the attacks? Or alternatively, can hiding the training set from adversaries help the defenses? |
In this work, as first step to understand this question, we show a separation result between data- oblivious and data-aware poisoning adversaries. In particular, we show that there exist a learning setting (Feature selection with LASSO on Gaussian data) where poisoning adversaries that know the distribution of data but are oblivious to specific training samples that are used to train the model are provably weaker than the adversaries with the knowledge of both training set and the distribution. To the best of our knowledge, this is the first separation result for poisoning attacks.
Implications of our separation result: Here, we mention some implications of our separation result.
Separation of threat models: The first implication of our result is the separation of data- oblivious and data-aware poisoning threat models. Our result shows that data-oblivious attacks are strictly weaker than data-aware attacks. other words, shows that we cannot expect the defenses to have the same effectiveness in both scenarios. This makes the knowl- edge of data a very important design choice that should be clearly stated when designing defenses or attacks.
Possibility of designing new defenses: Although data-oblivious poisoning is a weaker at- tack model, it might still be the right threat model for many applications. For instance, if data providers use cryptographically secure multi-party protocols to train the model 168), then each participant can only observe their own data. Note that each party might still have access to some data pool from the true distribution of training set and that still fits in our data-oblivious threat model. In these scenarios, it is natural use defenses that are only se- cure against data-oblivious attacks. Our results shows the possibility of designing defense mechanisms that leverage the secrecy of training data and can provide much stronger secu- rity guarantees in this threat mode. In particular, our result shows the provable robustness of LASSO algorithm in defending against data-oblivious attacks.
Note that this approach is distinct from the demoted notion of "security through obscurity" as the attacker knows every detail of the algorithm as well as the data distribution. The only unknown to the adversary is the randomness involved in the process of sampling training examples from the training distribution. This is exactly similar to how secret randomness helps security in cryptography.
privacy is often viewed as a utility for data owners in the ma- chine learning pipeline. Due to the trade-offs between privacy and the efficiency/utiiity, data-users often ignore the privacy of data owners while doing their analysis, especially when there is no incentive to enforce the privacy of the learning protocol. The possi- bility of improving the security against poisoning attacks by enforcing the (partial) data- obliviousness of the adversary could create new incentive for keeping training datasets secret. Specifically, the users of data would now have more motivation to try to keep train- ing dataset private, with the goal of securing their models against poisoning and increasing their utility in scenarios where part of data is coming from potentially malicious sources.
A new motive for privacy:
This question independently asked as an open question in the survey of Goldblum al. 31

---

1.1 Our Contributions
In this work, provide theoretical evidence that obliviousness of attackers to the training data can indeed help robustness against poisoning attacks. In particular, we provide a provable difference between: (i) adversary that is aware of the training data as well as the distribution of training data, before launching the attack (data-aware adversary) and (ii) an adversary that only knows the distribution of training data and does not know the specific clean examples in the training set (data- oblivious adversary).
We start by formalizing what it means mathematically for the poisoning adversary to be data- oblivious or data-aware.
Separations for feature selection with Lasso. We then prove a separation theorem between the data-aware and data-oblivious poisoning threat models in the context of feature selection. We study data-aware and data-oblivious attackers against the Lasso estimator and show that if certain natural properties holds for the distribution of dataset, the power of optimal data-aware and data-oblivious poisoning adversaries differ significantly.
We emphasize that in our data-oblivious setting, the adversary fully knows the data distribution, and hence it implicitly has access to a lot of auxiliary information about the data set, yet the very fact that it does not know the actual sampled dataset makes it harder for adversary to achieve its goal.
Experiments. To further investigate the power of data-oblivious and data-aware attacks in the con- text of feature selection, experiment synthetic datasets sampled from Gaussian distributions, as suggested in our theoretical results. Our experiments confirm our theoretical findings by showing that the power of data-oblivious and poisoning attacks differ significantly. Furthermore, we exper- imentally evaluate the power of partially-aware attackers who only know part of the data. These experiments show the gradual improvement of the attack the knowledge of data grows.
In our experimental studies we go beyond Gaussian setting and show that the the power of data- oblivious attacks could be significantly lower real world distributions well. In our experiments, sometimes (depending on the noise nature of the dataset), even an attacker that knows 20% of the dataset cannot have much of improvement over oblivious attacker.
Separation for classification. In addition to our main results in the context of feature selection, in this work, we also take initial steps to study the role of adversary's 's knowledge (about the data set) when the goal of the attacker is to increase the risk of the produced model in the context of classification. These results are presented supplemental material ASection(A
1.2 Related Work
Here, provide short version of related prior work. A more comprehensive description of pre- vious work has been provided in Appendix B where we also categorize the existing attacks into data-aware and data-oblivious categories.
Beatson et al. [4] study "Blind" attackers against machine learning models that do not even know the distribution of the data. They show that poisoning attacks could be successful in such a restricted setting by studying the minimax risk of learners. They also introduced "informed" attacks that see the data distribution, but not the actual training samples and leave the study of these attacks to future work. Interestingly. the "informed" setting of [4] is equivalent to the "oblivious" setting in our work.
Xiao et al. [71] empirically examine the robustness of feature selection in the context of poisoning attacks, but their measure of stability is across sets of features. We are distinct in that our paper studies the effect of data-oblivious attacks on individual features and with provable guarantees.
We distinguish our work with another line of work that studies the computational complexity of the attacker [46, (2)]. Here, we study the "information complexity" of the attack; namely, what information the attacker needs succeed in poisoning attack, while those works study the compu- tational resources that a poisoning attacker needs to successfully degrade the quality of the learned model. Another recent exciting line of work that studies the computational aspect of robust learn- ing in poisoning contexts, focuses on the computational complexity of the leurning process itself 18. 40. 16. 20. 21. 19. 53 22). and other works have studied the same question about the com- plexity of the learning process for evasion attacks
[7]. Furthermore, our work deals with
3

---

information complexity and is distinct from works that study the impact of the training set (e.g..
using clean labels) on the success of poisoning [55. 73 67]
Our work's motivation for data secrecy might seem similar to other works that leverage privacy- preserving learning (and in particular differential privacy (23. 25 to limit the power of poisoning attacks by making the learning process less sensitive to poison data [42]. However, despite seeming similarity, what we pursue here is fundamentally different. In this work, we try to understand the effect of keeping the data secret from adversaries. Whereas the robustness guarantees that come from differential privacy has nothing to do with secrecy and hold even if the adversary gets to see the full training set (or even select the whole training set in an adversarial way.).
We also point out some separation results in the context of adversarial examples. The work of Bubeck et al. [12] studies the separation in the power of computationally bounded v.s. computa- tionally unbounded learning algorithms in learning robust model. Tsipras et al. [66] studies the separation between benign accuracy and robust accuracy of classifiers showing that they can be even odds with each other. Schmidt et al. [54]] show the separation between sample complexity of learning algorithms in training an adversarially robust model versus a model with high benign accuracy. Garg et al. [29] separate the notions of computationally bounded v.s. computationally unbounded attacks in successfully generating adversarial examples. Although all these results are only proven for few (perhaps unrealistic) settings, they still significantly helped the understanding of adversarial examples.
As opposed to the data poisoning setting, the question of adversary's 's (adaptive) knowledge was indeed previously studied in the line of work on adversarial examples [41. 49, 62 In a test time
evasion attack the adversary's goal is find an adversarial example, the adversary knows the input a entirely before trying to find a close input x' that is misclassified. So, this adaptivity aspect already differentiates adversarial examples from random noise.
2 Defining Threat Models: Data-oblivious and Data-aware Poisoning
In this section, we formally define the security games of learning systems under data-oblivious poisoning attacks. It common in cryptography to define security model based on a game between an adversary and a challenger [36]. Here, we use the same approach and introduce game based definitions for data-oblivious and data-aware adversaries.
Feature selection. The focus of this work is mostly on the feature selection which is a significant task in machine learning. In feature selection problem, the learning algorithm wants to discover the relevant features that determine the ground truth function. For example, imagine a dataset of patients with many features, who suffer from a specific disease with different levels of severity. One can try to find the most important features contributing to the severity of the disease in the context of feature selection. Specifically, the learners' goal is to recover a vector 0" E Idd whose non-zero coordinates determine the relevant features contributing to the disease. In this scenario, the goal of the adversary is to deceit the learning process and make it output model Ø' E Ed with different set of non-zero coordinates. As motivation for studying feature selection under adversarial perturbations, note that the non-zero coordinates of the learned model could be related to a sensitive subject. For example, in the patient data example described in the introduction, the adversary might be a pharmaceutical institute who tries to imply that non-relevant feature is contributing to the disease, in order to advertise for a specific medicine.
We start by separating the goal of a poisoning attack from how the adversary achieves the goal. The setting of an data-oblivious attack deals with the latter, namely it is about how the attack is done, and this aspect is orthogonal to the goal of the attack. In nutshell, many previous works data poisoning deal with increasing the population risk of the produced model (see Definition Definition/A..bbloor and Section C for more details and variants of such attacks). In a different line of work, when the goal of the learning process is to recover a set of features (a.k.a,, model recovery) the goal of an attacker would be defined to counter the goal of the feature selection, namely to add or remove features from the correct model.
In what follows, we describe the security games for feature selection task. We give this definition for a basic reference setting in which the data-oblivious attacker injects data into the data set, and its goal is to change the selected features. (See Section C for more variants of the attack.) Later, in

---

Section 3 we will see how to construct problem instances (by defining their data distributions) that provably separate the power of data-oblivious attacks from data- aware ones.
Notation. We first define some useful notation. For an arbitrary vector 0 E TRd we use Supp(0) = {i: 0g # 0), denote the of (indices of) its non-zero coordinates. We use capital letters (e.g X) to denote sets and calligraphic letters (c.g. X') to denote distributions. (2) denotes the joint distribution X' and y and X X2 denotes the equivalence of two distributions X1 and X2 We use ||0||2 and ||O|| to denote the l and & norms of / respectively. For two matrices X E R and Y E Rax1, we use X Y] E R (d-1) to denote a set of regression observations on feature vectors Xig[M] such that Y; is the real-valued observation for X,, For two matrices X1 E R and
X1 X2
X2 E Raaxd, we use
E R((1+ta)xd to denote the concatenation of X1 and X2. Similarly,
[1 Y1
for two set of observations [Xi Yi] E Rnxx(d+1) and [X2 Y2] E [=xx(d+1), we use
LX2
Y2J
denote the concatenation of [X| Yi] and [X2 Y2). For security game and an adversary A we use Adv(A,C G) (advantage of adversary in game G) to denote probability of adversary A winning the security game G. where the probability taken over the randomness of the game and adversary.
Since the security games for data-aware and data-oblivious games close, below for both, while we specify their exact differences.
Definition 2.
Definition 2.1 (Data-oblivious and data-aware data injection poisoning for feature selection).
first describe the data-oblivious security game between challenger C' and an adversary A. The game parameterized by the adversary's budget k and the training data = [[ Y] which is a matrix X and set of labels Y, and the feature selection algorithm FtrSelector.
OblFtrSel(k; D, FtrSelector, n))
1. Knowing the algorithm FtrSelector and distribution 'D supported on IR++1, and given k as
input, the adversary A generates poisoning dataset [X' Y'1 E [-1, 1]1,1]kx((+)) of size such that each row has & norm most and sends it C.
2. C samples a dataset [X Y] + D
3. C recovers models Ó = FtrSelector([X YY) using the clean data and O'
(IX Y
FtrSelector
using the poisoned data.
4. Adversary wins if (upp(() (0) Supp(0'), and the following notation denote the winning:
ObIFtrScl(A,k; D, FtrSelector,n) n)) =.
In the security game for data-aware attackers, all the steps are the same as above, except that the order of steps 1 and 2 are different. Namely, challenger first samples and sends the dataset to adversary.
A (wrFtrSel(k; D. FtrSelector,
1. C samples [X [Y] + D" --" and sends A.
2. Knowing the algorithm FtrSelector and distribution D supported Rd+1, the dataset
[X Y), and given l as input, the adversary A generates a poisoning dataset [X' I e
- 1, 1 (x--11 of size l such that each row [V') has &a norm at most I and sends it to
C.
3. C recovers models Ó = FtrSelector([x [Y]) using the clean data and 0 = Y
(1x Yr
1) using the poisoned data.
FtrSelector
4. Adversary wins if Supp(0) + Supp(O'), and use the following notation to denote the winning:
AwrFtrSel(A.kr FtrSelector, n)
Variations of security games for Definition 2.1 Definition 2 is written only for the case of
flipping attacks by only injecting poison data. One can, however, envision variants by chang- ing the adversary's 's goal and how it is doing the poisoning attack. In particular, one can define more
5

---

specific goals for the attacker to violate the feature selection, by aiming to add or remove non-zero coordinates the recovered model compared to the ground truth In addition, it also possible to change the method of the adversary to employ data elimination or substitution attacks.
One can also imagine partial-informatio attackers who are exposed fraction of the data S (e.g.. by being offered the knowledge of a randomly selected fraction of the rows of [X] Our experiments deal with this very setting.
Why bounding the norm of the poison points? When bounding the number of poison points, is important to bound the norm of the poisoning points according to some threshold (e.g. through a clipping operation) otherwise a single poison point can have infinitely large effect on the trained model. By bounding the ε norm of the poison data, we make sure that single poison point has a bounded effect on the objective function and cannot play the role of a large dataset. We could remove this constraint from the security game and enforce it in the algorithm through a clipping operation but we keep it as a part of definition to emphasize on this aspect of the security game. Note that in this work we always assume that the data is centered around zero. That is why we only use a constraint on the norm of the poison data points. However, the security game could be generalized by replacing the l norm constraint with an arbitrary filter IF for different scenarios.
Why using i instead of O. Note that in security games of Definition 2.1 do not use the real model 0 (or more accurately its of features Supp(O)), but rather we work with Supp(0). That is because, we will work with promised data sets for which FtrSelector provably recovers the true set of features Supp(0) (O). This could be guaranteed, e.g., by putting conditions on the data.
Why injecting the poison data to the end? Note that in security games of Definition 2.1 simply injecting the poison examples to the end of the training sequence defined by X.Y. instead of asking the adversary to pick their locations. That is only for simplicity, and the definition is implicitly assuming that the feature selection algorithm is symmetric with respect to the order of the elements int the data set (e.g., this is for Lasso estimator). However, one can generalize the definition directly to allow the adversary to pick the specific location of the added elements.
3 Separating Data-oblivious and Data-aware Poisoning for Feature Selection
In this section, we provably demonstrate that the power of data-oblivious and data-aware adversaries could significantly differ. Specifically, we study the power of poisoning attacks on feature selection.
Feature selection by the Lasso estimator. We work in the feature selection setting, and the exact format of our problem as follows. There a target parameter vector 0" E (0, 1)d. We have a x matrix X (n vectors, each of d features) and we have Y = X x 0" + W where W itself is small noise, and Y is the vector of noisy observations about 8*, where the number of non-zero elements (denoting the actual relevant features) in 0* is bounded by namely, |Supp(O*) S s. The goal of the feature selection is find a model Ó, given [x] y). such that Supp(0) = Supp(O").
The Lasso Estimator tries to learn 6 by optimizing the regularized loss with regularization parame- ter and obtain the solution A as
0 argmin
||Y X 012 0E(0,1)a n
2A
10
n
We use L[ Y] A) to denote 02, learned by the Lasso optimization described above. When
we A is clear from the context, use Lasso[[X YY) and Ā.
We also use Risk(O, [x] X) (and Risk [x] X) when À is clear from the context) to denote the "scaled up" value of the Lasso's 's objective function
Risk 0, [X Y)) = Y x
x
0
2 + +
|0],-
2
is known by a work of Wainwright (69 that under proper conditions Lasso estimator can recover the correct feature vector (See Theorems D.2 and and D.4 Appendix [ for more details.) The robust
'In fact, one can even define targeted variants in which the adversary even picks the feature that it wants to add/remove or flip.

---

version of this result, where part of the training data is chosen by an adversary, is also studied in Thakurta et al. [63]. (See Theorems D.5 and [D3 in Appendix [ for more details.) However, the robust version considers robustness against data-aware adversaries that can see the dataset and select the poisoning points based on the rest of training data. In the following theorem, we show that the robustness against data-oblivious adversaries could be much higher than robustness against data-aware adversaries.
Separation for feature selection. We prove the existence of a feature selection problem such that, with high probability, it stays secure the data-oblivious attack model of Definition 2.1 while the same problem's 's setting is highly vulnerable to poisoning adversaries as defined in the data- aware threat model of Definition [.1 We use Lasso estimator for proving our separation result.
Theorem 3.1. For any l E N and E1 E2 E (0,1), there exist an n, N, a E R and R such that the distribution 'D (X,)) for X' (0, o odynxd and y = X 0" + (0, is recoverable using Lasso estimator, meaning that with high probability over the randomness of sampling dataset [X] [X| <- DD" we have
Supp(Lasso((x [Y) = Supp((")
while the advantage of any data-oblivious adversary in changing the support is most e Namely for any data- data-oblivious adversary A we have
ObIFtrSel(AA k, Lasso, n) E1 S
E
On the other hand, there is an adversary that can win the data-aware security game with probability at least Eg. Namely, there is an data-aware adversary such that
IE StD
AwrFFrSee(AA (A, Lasso, m) 2 62
The main idea behind the proof. To prove the separation, we use the fact that data-oblivious adversaries cannot discriminate between the coordinates that are not the support set of 0*, Imagine the distribution of data has property that with high probability there exists a unique feature that not in the support set, but it is possible to add that feature to the support set with a few number of poisoning examples. We call such feature "unstable" feature. Suppose the distribution also has an additional property that each coordinate has the same probability feature. Then, the only way that adversary can find the unstable feature is by looking into the dataset. Otherwise, if the adversary is data-oblivious, it does not have any information about the unstable feature and should attack blindly and pick one of the coordinates random. On the other hand, the data-aware adversary can investigate the dataset and find the unstable feature. In the rest of this section formalize this idea by constructing distribution D that has the properties mentioned above.
being the unstable
Below we first define the notion of stable and unstable features and then formally define two proper- ties for a distribution D that if satisficd, we derive Thcorem it.
Definition 3.2 (Stable and unstable coordinates). Consider a dataset [x [ E R=x(d+1) with
unique solution 0g for the Lasso minimization. [x] Y] is k-unstable on coordinate E [d]
the 2th coordinate of the feature vector obtained by running Lasso on [X] YY] 0. namely Lasso (Ix [Y)) = 0, and there exist data set [X' YY) with size k and Ego norm at most 1 on Y
(
X Y D) On the other hand, [X Y] is k-stable on
each row such that i E Supp coordinate i, for all datasets [x' Y"I with rows and loc norm at most on each row we have
Lasso
(()))
X Y
SignoLasso ([x (T),) Sign
(Lasso
The following definitions capture two properties of a distribution D. The first property states that with high probability over the randomness of D, a dataset sampled from D has least one unstable feature.
7

---

Definition 3.3 ((k, 8) unstable distributions). A distribution D is unsttale if it is on at least one coordinate with probability least (E2). Namely
k k-unstable
Pr Bi Pr E [d]
The 8thh feature is k-unstable on S] E2.
The following notion defines the resilience of a distribution against a single poison dataset. In nutshell, distribution is resilient if there does not exist universal poisoning set that can be effective against all the datasets coming from that distribution.
Definition 3.4. [(k, E) ressiliinnce distribution D over (xx((++) is (k, ()rsssiiil if for any poi- soning dataset S' of size k and to norm bounded by 1 we have
((s)
(s)
Pr (Supp
Lasso
* Supp(Lasso(S)) S.
8')
Remark 3.5. Note that Deftmitions dataset sampled from the distribution that we omit from the notation for simplicity.
3.3 and 3.4 have an implicit dependence on the size of the
Before constructing a distribution we first prove the following Proposition about (k, -u-nttaeee and (R:, ressiiient distributions. The proof can be found in Appendix
Proposition 3.6 (Separation for unstable yet resilient distributions). If data distribution is (k, E1)- resilient and (k. -unsttbbel then there is an adversary that wins the data-aware game of definition 2. with probability Ez. while no adversary can win the data-oblivious game with probability more than E1.
3.1
(In)Stabilityy and Resilience of Gaussian
The only thing that remains to prove Theorem 3.1 is to show that Gaussian distributions with proper parameters are (k,,2))unstaa) and ( --rresiiient at the same time. Here we sketch the two steps we take to prove this.
Gaussian is Unstable. We first show that each feature in the Gaussian sampling process has probability of being k-unstable that is proportional to eA Note that the unstability of i-th feature is independent from all other features and also note that the probability is independent of d. This shows that, if d chosen large enough, with high probability, there will be least one coordinate that is k-unstable. However, note that the probability of particular feature being unstable is still low and we are only leveraging the large dimensionality to increase the chance having an unstable feature. Roughly, if we select d = (E2//()), we can make sure that the ratio of the success rate between data-aware and data-oblivious adversary what we need. The only thing that remains is to select À and in way that the data oblivious adversary has success rate of most E and at least (2(E1).
This result actually shows the tightness of the robustness theorem in 63 (See Theorem D.3 for the full description of this result). The authors in (63) show that running Lasso on Gaussian distribution can recover the correct support set, and is even robust to certain number of adversarial entries. Our result complements theirs and shows that their theorem is indeed tight. Note that the robustness result of [63] is against dataset-aware attacks. In the next step, we show stronger robustness guarantee for data-oblivious attacks in order to prove our separation result. See Appendix E for formalization of this argument.
Gaussian is Resilient. We show the LASSO is resilient when applied on Gaussian of any dimension. In particular, we show that if the adversary aims at adding a feature to the support set of the model, should "invest" in that feature meaning that the la weight on that feature should be high across all the poison entries. The bound on the la norm of each entry will prevent the adversary to invest on all features and therefore, the adversary has to predict which features will be unstable and invest in them. On the other hand, since Gaussian is symmetric, each feature has the same probability of being unstable and the adversary will have a small chance of succeeding.
nutshell, by selecting = (kk + a + k)) In(1/e1) we can make sure that the success probability of the oblivious adversary is bounded by #1. This argument is formalized in Appendix
8

---

3.2 Experiments
In this section, we highlight our experimental findings on both synthetic and real data to compare the power of data-oblivious and data-aware poisoning attacks the context of feature selection. Our experiments empirically support our separation result in TheoremB.1
Our partial-knowledge attack: The attack first explores through the part of data that it has access to and identifies which feature is the most unstable feature. The key here is that the data-aware adversary search for the most vulnerable feature in the available data. Then, the attack will use that feature to craft poison points that create maximum correlation between that feature and the response variable. See Appendix [2.2 for more details.
Experiments with Gaussian distribution. For the synthetic experiment, we demonstrate the sep- aration result occurs for large dataset sampled from Gaussian distribution. For 300 rows and d 5 x 10 features, we demonstrate that unstable features occur for a dataset drawn from (O, 1)mxd, For the LASSO algorithm, the "knowledge" the adversary has of the dataset from p 0, 5, 10.... 95, 100% by only showing the adversary random sample of p% (for p O, the adversary is completely oblivious and so must choose a feature uniformly at random). The adversary then chooses the most unstable feature out of their p% of the data and perform the attack on that feature to add it to the Supp(0), (0) We observe a clear separation between data-oblivious, data-aware, and partially-awar adversaries in Figure []
the hyperparameter of A 20 2n
We vary
Partall Information Adversary vs. Percentage of Data (synthelic)
100
30
8
number
Percentage
Figure I: Synthetic experiment. The y-axis is the average (over 30 random p% splits of the dataset given to the adversary) number of poison points needed to add the feature to Í.The leftmost point shows the power of an oblivious adversary while the rightmost point shows the power of full- information adversary. The oblivious adversary needs significantly more poison points, average, to add their uniformly chosen feature to Supp(O).
Experiments with real data. We also consider MNIST and four other datasets used widely in the feature selection literature to explore this separation in real world data: Boston, TOX, Protate GE, and SMK.F
We first preprocess the data by standardizing to zero mean and unit variance. Then, we chose À such that the resulting parameter vector has reasonable support size (at least 10 features in the support); this done by searching over the space of X/n [0, 1.0]. and resulted in À 50.1 for Boston, A = 9.35 for SMK, À = 17 for TOX, A 5.1 for Prostate, and À = 1000 for MNIST. Just as in the synthetic experiments, we allow the adversary to have the knowledge of p 0, 5, 10...., 95, 100% fraction of the data. Denote the features not in Supp(f) as G. We attack each feature E g with the same attack as synthetic experiment, where X' Rxd and Y' E R4x1, We plot the average best value of k needed by the adversary to add a feature Supp(() against how much knowledge (p%) of the dataset they have. We show the results for SMK and TOX in Figure and the result for MNIST in Figure
TTO., SMK, and Prostate GE can be found here: http:://featuursseeeettet asu. www.datasttss.sooooeee
Boston can be found with scikit learn's built-in datasets: https://scikit-t learn. wtt.raoooerrrroorrttteeeeeeeeeee http:///aalllaaaaoeo/////eeeeeaa datasets. siid__ostoo..tte

---

Power Parta infomation Percerlage (5M6))
Power Partal irhumaaion Perceriage Known, (TOX)
Arg narier
Arg number
100
22
40
65 123
Percerlogg
Pereosagge
Figure 2: SMK and TOX Experiments. The behavior of attack on these two datasets is very similar synthetic experiments. We believe this is because the noisy nature of these feature selection datasets which causes them to be similar to the Gaussian distribution. Since the noise is large, even given the half of the dataset, the attacker cannot identify the most unstable feature.
100
193
Percurlage ol Known
Figure 3: MNIST experiments. Compared to other experiments, the number of poison points drops faster as the percentage of data-awareness grows. This can be explained by separability (less noisy nature) of MNIST dataset.
Conclusion
In this paper we initiated a formal study of the power of data-oblivious adversaries who do not have the knowledge of the training set in comparison with data-aware adversaries who know the training data completely before adding poison points to it. Our main result proved a separation between the two threat models by constructing sparse linear regression problem. We show that in this natural problem, Lasso estimator is robust against data-oblivious ad adversaries that aim to add a non-relevant features the model with certain poisoning budget. On the other hand, for the same problem, we prove that data-aware ad adversaries, with the same budget, can find specific poisoning examples based on the rest of the training data in such a way that they can successfully add non-relevant features to the model. We also experimentally explored the partial- inttialinformmation adversaries who only observe fraction of the training set and showed that even in this setting, the adversary could be much weaker than full-information adversary. As result, our work sheds light on important and yet subtle aspect of modeling the threat posed by poisoning adversaries. We, leave open the question of separating different aspects of poisoning threat model including computational power of adversaries, computational power of learners, clean-label nature of adversaries and etc.
Acknowledgments. Mohammad Mahmoody was supported by NSF grants CCF-191066 and CNS- 1936799, Sanjam Garg supported in part by DARPA under Agreement No. HR001 12020026. AFOSR Award Foundation, and Visa Inc. The work is partially supported by Air Force Grant FA9550-18-1148 18-1-0166. the National Science Foundation (NSF) Grants CCF-FMitF. 1836978, IIS-2008559, SaTC-Frontier 1804648 and CCF-1652140 140, and ARO grant number W91 INF17-1-0400 Somesh Jha partially supported by the DARPA GARD problem under agreement number 885000. Any opinions, findings and conclusions or recommendations expressed this material are those of the author(s) and do necessarily reflect the views of the United States Government or DARPA.
NSF CNS Award 1936826, and research grants by the Sloan
10

---

References
[1] Hojjat Aghakhani, Dongyu Meng, Yu-Xiang Wang, Christopher Kruegel, and Giovanni Vigna. Bullseye polytope: A scalable clean-label poisoning attack with improved transferability. arXiv preprint 20X1v:2005.00191, 2020.
[2] Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense of security: Circumventing defenses to adversarial examples. In International Conference on Machine Learning. 2018
[3] Marco Barreno, Blaine Nelson, Russell Sears, Anthony D Joseph, and J Doug Tygar. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pages 16-25. ACM, 2006.
[4] Alex Beatson, Zhaoran Wang, and Han Liu. Blind attacks on machine learners. In Advances In Neural Information Processing Systems, pages 2397-2405, 2016.
[5] Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing fed- erated learning through an adversarial lens. In International Conference on Machine Learning, pages 634 643, 2019.
[6] Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Smdic, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion Attacks against Machine Learning at Test Time. In ECML/PKDD, pages 387-402, 2013.
[7] Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. Asian conference on machine learning, pages 97-112, 2011.
[8] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1467-1474. Omnipress, 2012.
[9] Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Pattern Recognition, 84:317-331, 2018.
[10] Sébastien Bubeck, Yin Tat Lee, Eric Price, and llya Razenshteyn. Adversarial examples from cryptographic pseudo-random generators. arXiv preprint arXiv: (0V::/8/1.06111 1,06418, 2018 8.
[11] Sébastien Bubeck, Eric Price, and llya Razenshteyn. Adversarial examples from computational constraints. arXiv preprint arXiv: 1oXiv:1805..1m 11.805500044 2018
[12] Sébastien Bubeck, Eric Price, and llya Razenshteyn. Adversarial examples from computational constraints. arXiv preprint arXiv: 1805. 10204, 2018.
[13] Cody Burkard and Brent Lagesse. Analysis of causative attacks against svms learning from data streams. In Proceedings of the 3rd ACM on International Workshop on Security And Privacy Analytics, pages 31 31-36, 2017.
[14] Di Cao, Shan Chang. Zhijian Lin, Guohua Liu, and Donghong Sun. Understanding distributed poisoning attack in federated learning. In 2019 JEEE 25th International Conference on Parallel and Distributed Systems (ICPADS), pages 233 239...9.922 IEEE, 2019.
[15) Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IFEE Symposium on Security and Privacy, pages 39-57. IEEF, 2017.
[16] Moses Charikar, Jacob Steinhardt, and Gregory Valiant. Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47-60. ACM, 2017.
[17] Akshay Degwekar and Vinod Vaikuntanathan. Computational limitations in robust classifica- tion and win-win results. arXiv preprint 10XX:v/9022.0086 2019.
[18] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 655- 664, IEEE, 2016.

---

[19] Ilass Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Jacob Steinhardt, and Alis- tair Stewart. Sever: A robust meta-algorithm for stochastic optimization. arXiv preprint arXiv: I8N::02032255 2018.
[20] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Statistical query lower bounds for robust estimation of high -ighddimensiona Gaussians and Gaussian mixtures. In Foundations of Compuler Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 73-84. IEEE, 2017.
[21] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. List-decodable robust mean estima- tion and learning mixtures of spherical Gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1047-1060. ACM, 2018.
[22] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. arXiv preprint arXiv: 00040, 2018.
[23] Irit Dinur and Kobbi Nissim, Revealing information while preserving privacy. In Proceedings of the twenty-second ACM SIGMOD-SIGACTTSSIAARR symposium Principles of databuse systems, pages 202-210, 2003.
[24] Dimitrios Diochnos, Saeed Mahloujifar, and Mohammad Mahmoody. Lower bounds for adversarially robust pac learning. arXiv preprint arXiv:190..0533 1906.0586,,, 2019.
[25] Cynthia Dwork. Differential privacy: A survey of results. In International conference on theory and applications of models of computation, pages 1-19. Springer, 2008.
(26) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensi- tivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[27] Minghong Fang, Neil Zhenqiang Gong, and Jia Liu. Influence function based data poisoning attacks to top-n recommender systems. In Proceedings of The Web Conference 2020, pages 3019-3025, 2020.
[28] Clement Fung, Chris JM Yoon, and Ivan Beschastnikh. Mitigating sybils in federated learning poisoning. arXiv preprint arXiv: 848,0666, 2018
[29] Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mohammad Mahmoody. Adversarially ro- bust learning could leverage computational hardness. arXiv preprint arXiv: 1554, 2019.
[30] Jonas Geiping, Liam Fowl, Ronny Huang, Wojeiech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. arXiv preprint arXiv:2009.0222
2020.
[31] Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li, and Tom Goldstein. Data security for machine learning: Data poisoning, backdoor attacks, and defenses. arXiv preprint arXiv:2012. 2004444 2020.
[32] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adver- sarial Examples. In ICLR, 2015.
[33] Tianyu Gu, Brendan Dolan-Gavitt and Siddharth Garg. Badnets: Identifying vulnerabilitiis in the machine learning model supply chain. arXiv preprint arXiv:1708.06733 2017.
[34] Junfeng Guo and Cong Liu. Practical poisoning attacks on neural networks. Proceedings of the European Conference Computer Vision, 2020.
[35] Rui Hu, Yuanxiong Guo, Miao Pan, and Yanmin Gong. Targeted poisoning attacks social recommender systems. In 2019 IEEE Global Communications Conference (GLOBECOM), pages 1-6. IEEE, 2019.
[36] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chapman & Hall/CRC, 2007.
[37] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pages 1885-1894, 2017.
12

---

[38] Pang Wei Koh, Jacob Steinhardt, and Percy Liang, Stronger data poisoning attacks break data sanitization defenses. arXiv preprint 1rXiv:1811.07700 2018.
[39] Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comissoneru, Matt Swann, and Sharon Xia. Adversarial machine learning-industry per- spectives. In 2020 IEEE Security and Privacy Workshops (SPW), pages 69-75. IEEE, 2020.
[40] Kevin A Lai, Anup B Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Anmual Symposium on, pages 665-674. IEEE, 2016.
[41] Daniel Lowd and Christopher Meek. Adversarial learning. In KDD, pages 641 641-647, 2005.
[42] Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially-priias learners: attacks and defenses. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 4732-473 4738. AAAI Press, 2019.
[43] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards Deep Learning Models Resistant to Adversarial Attacks. In ICLR, 2018.
[44] Saeed Mahloujifar, Dimitrios I Diochnos, and Mohammad Mahmoody. The curse of concen- tration in robust learning: Evasion and poisoning attacks from concentration of measure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4536-4543, 2019.
[45] Saeed Mahloujifar and Mohammad Mahmoody. Blockwise p- T-Tampering Attacks on Crypto- graphic Primitives, Extractors, and Learners. In Theory of Cryptography Conference, pages 245-279, Springer, 2017.
[46] Saeed Mahloujifar and Mohammad Mahmoody. Can adversarially robust learning leverage computational hardness? arXiv preprint 1rXiv:1810.01407 2018.
[47] Saeed Mahloujifar and Mohammad Mahmoody. Can adversarially robust learning leverage computational hardness? In Algorithmic Learning Theory, pages 581-609, 2019.
[48] Saeed Mahloujifar, Mohammad Mahmoody, and Ameer Mohammed. Universal multi-party poisoning attacks. In International Conference on Machine Learning, pages 0274-4283 2019.
[49] Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, and J. D. Tygar. Classifier Evasion: Models and Open Problems. In PSDM, pages 92-98, 2010.
[50] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Anan- thram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pages 506-519. ACM, 2017.
[51] Nicolas Papernot, Patrick McDaniel, Arunesh Sinha, and Michael Wellman. Towards the sci- ence of security and privacy in machine learning. arXiv preprint
2016.
[52] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distilla- tion as a defense to adversarial perturbations against deep neural networks. In 2016 IEEE Symposium on Security and Privacy (SP), pages 582-597. IEEE, 2016.
[53] Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.06485, 2018
[54] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially Robust Generalization Requires More Data. arXiv preprint 18X1v:180..11285. 2018.
[55] 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, pages 6103-6113, 2018.
13

---

[56] Shiqi Shen, Shruti Tople, and Prateck Saxena. A uror: defending against poisoning attacks in collaborative deep learning systems. In Proceedings of the 32nd Annual Conference on Computer Security Applications, pages 508-519. ACM, 2016.
[57] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pages 3-18. IEEE, 2017.
[58] Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In Advances in neural information processing systems, pages 3517-3529, 2017.
[59] Octavian Suciu, Radu Marginean, Yigitcan Kaya, Hal Daume III, and Tudor Dumitras. When does machine learning (FAIL)? generalized transferability for evasion and poisoning attacks. In 27th {USENIX} Security Symposium (!USENIX) Security 18), pages 1299 1316, 2018.
[60] Lichao Sun. Natural backdoor attack on text data. arXiv preprint arXiv:220000 /6/76, 2020.
[61] Fnu Suya, Saeed Mahloujifar, David Evans, and Yuan Tian. Model-targeted poisoning attacks: Provable convergence and certified bounds. arXiv preprint arXiv:2006.16466 2020.
[62] Christian Szegedy. Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Good- fellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[63] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via sta- bility arguments, and the robustness of the lasso. In Conference on Learning Theory, pages 819-850, 850, 2013.
[64] Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against federated learning systems. In European Symposium on Research in Computer Security, pages 480-501. Springer, 2020.
[65] Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive at- tacks to adversarial example defenses. arXiv preprint arXiv:2002.08347, 2020.
[66] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. arXiv preprint 1805. 2018.
[67] Alexander Tumner Dimitris Tsipras, and Aleksander Madry. Label-consistent backdoor attacks. arXiv preprint arXiv: (rXiv::912.027711 2019
[68] Sameer Wagh, Divya Gupta, and Nishanth Chandran. Securenn: 3-party secure computation for neural network training. Proceedings Privacy Enhancing Technologies, 2019(3):26-9,, 2019.
[69] Martin J Wainwright. Sharp thresholds for nigh-dimensional and noisy sparsity recovery us- ing ficonstraineed quadratic programming (lasso). IEEE transactions on information theory, 55(5):2183-2D) 2009.
[70] Yizhen Wang and Kamalika Chaudhuri. Data poisoning attacks against online learning. arXiv preprint arXiv: 1808. 08994, 2018
[71] Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is feature selection secure against training data poisoning? In ICML, pages 1689-1698, 2015.
[72] Mengchen Zhao, Bo An, Wei Gao, and Teng Zhang. Efficient label contamination attacks against black-box learning models. In IJCAI, pages 3945-3951, 2017.
[73] 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. arXiv preprint 1xxin=1905.05897, 2019.
14


Reviews:
[{"review_id": "Pv67y4WNl1l", "reviewer": "Reviewer_wYCe", "summary": "The paper studies the difference between data-oblivious and data-aware adversaries in ML. In particular, the authors present a result about the effectiveness of such adversaries against feature selection with LASSO and show that the data-aware adversary is provably stronger in such a scenario. Experiments on synthetic and real data suggest that such a separation is also of practical importance.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "$\\textbf{Originality}$\n\nThe presented results are, to my awareness, novel. The proof technique appears interesting and potentially transferable to other learning setups. The related work is covered very well.\n\nA suggestion regarding the related work is to include a discussion on different adversaries in the context of mean estimation and PAC learning. For mean estimation, the relation between the classic Huber contamination model [1] to the adversarial model of [2] is somewhat similar to the relation between the adversaries discussed in the paper. For PAC learning, [3] and [4] give formal definitions of two data-aware adversaries.\n\n$\\textbf{Quality}$\n\nThe work appears technically sound and the main results are presented in full rigor within the main body of the paper. A good amount of intuition about the proofs is presented, with full proofs included in the supplementary material.\n\n$\\textbf{Clarity}$\n\nOverall, the paper is well-written and easy to follow, with various discussions helping the readers to gain more understanding. Some suggestions for improvement are as follows:\n\n- Abstract: \"devastating\" is a strange word to use here, perhaps \"harmful\" or \"effective\"?\n- I found the third paragraph of section 2 a bit hard to follow: perhaps it's helpful to make a difference between the goal of a poisoning attack from how it is done a bit earlier in the paper.\n- Definitions 3.3 and 3.4 have an implicit dependence on $n$, the size of the clean dataset. Perhaps you should talk about $(n,k, \\delta)$-resilient distributions.\n- Figure 1(a), caption: average number of *points*, not *features*? \n- Page 8, last paragraph: the results are shown in Figure 2, not 3. Also, why are the results for MNIST in the synthetic data plot, rather than with TOX and SMK? If it's for space reasons, it would be good to fix this for a potential camera-ready version.\n \n\n$\\textbf{Significance}$\n\nStudying the robustness of various ML algorithms to different adversaries is certainly of great current interest. The results presented in the paper only focus on the robustness of a fixed algorithm, LASSO. Nevertheless, the authors show a provable separation between two adversarial models, which I find interesting. Furthermore, the technique could be applicable to other learning setups, so the paper could be a first step towards more general separation results.\n\n$\\textbf{Summary}$\n\nThe paper is well-motivated, well-written and well-executed. While the results only hold for one fixed learning algorithm, I find this an interesting first steps towards more general results and therefore I think that the paper will be relevant for the NeurIPS community.\n\n\n$\\textbf{References}$\n\n[1] P. J. Huber. Robust Estimation of a Location Parameter. In: The Annals of Mathematical Statistics, 1964.\n\n[2] I. Diakonikolas et al. Robust estimators in high-dimensions without the computational intractability. In: SIAM Journal on Computing, 2019.\n\n[3] M. Kearns and M. Li. Learning in the presence of malicious errors. In: SIAM Journal on Computing, 1993.\n\n[4] N. H. Bshouty, N. Eiron, E. Kushilevitz. PAC learning with nasty noise. In: Theoretical Computer Science, 2002.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I find no serious issues in this regard.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "HF6M52aUdpa", "reviewer": "Reviewer_Rx3R", "summary": "This paper studies the (information-theoretic) power of an adversary in poisoning attacks. The authors exhibit a learning model (feature selection with Lasso) in which an adversary that has knowledge of the training set is provably stronger than an adversary that has no knowledge of the training set. (In both cases the adversary also has access to the distribution of the data.) The authors complement their theoretical findings with experiments on both synthetic and real data.\n\nTo show their theoretical result, the authors define the notion of unstable and resilient distributions under addition of poisoned data to the original dataset. They show that Gaussian distributions with suitable parameters are both resilient and unstable. This means (acc. to Prop 3.5) that data-aware adversaries can profit from the instability of the distribution to create poisoned data that cause Lasso to incorrectly select certain features with high probability, while the distribution's resiliency ensures that data-oblivious adversaries have to create attacks at random.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Review\n\nThis works seems to be a solid contribution to learning theory, as it provides a novel result, is well-motivated, and is presented in a neat and organized way. The paper is very well written and clearly organized. The discussion on the relation to prior work is thorough and very clear. \n\nI believe this paper would open up the avenue for future work on information-theoretic separation results for poisoning attack in other learning settings (e.g. classification), with more general assumptions in the feature selection setting (e.g. no restriction on the learning algorithm, compared to the explicit Lasso algorithm in this work) or to further the theoretical understanding of experimental results (i.e. how the partial access to the training dataset changes the guarantees). \n\nI think lines 97-99 highlight the compelling nature of the result: even given full knowledge of the data distribution, having access to the training data give vastly different robustness guarantees.\n\n\n## Questions\n\nThe claims and method seem correct to me, though I have a couple of questions:\n\n1. Instability is characterized by the existence of a coordinate i that is not picked up on by Lasso on the clean data, but that is selected on the poisoned data -- this omits the case where i is selected on the clean data but not on the poisoned data. Is there a reason for this?\n\n2. Distribution of the data (l.223-227): what happens if the data is nowhere near the region [-1,1]^d? Referring to the experimental setup, the real-world data was centred and normalized -- is the training data assumed to be centred and normalized in the theoretical results as well? If the data is very far away from the origin, it seems that adding points in the region [-1,1]^d could have the same effect that poisoning the dataset with points far from [-1,1]^d would do in case the data is indeed centred and normalized (i.e. \"playing the role of a large dataset\" as the authors mention on line 227).\n\n## Suggestions and comments\n\nMath typos/suggestions:\n* l. 245: should be the size |.| of Supp()\n* l. 246: introduce the lambda parameter formally, and perhaps index theta with lambda (as done in definition 3.2)\n* Theorem 3.1: It would be good if the dependence of n,d and sigma on k and the epsilons were stated explicitly to give an idea of how large the dataset and input dimensions need to be to have the result.\n\nSuggestions:\n- l.31-32: It would be good to highlight the main reasons why poisoning attacks have been identified as \"the most important threat model\" in the survey (instead of basing the claim on the survey's \"authority\")\n- l.148: the parameter theta hasn't been introduced at this point -- please use words instead or define it\n- l.213: I think it would be better to write out the steps explicitly \n\nEnglish style/grammar comments & suggestions:\n- l.28: \"difference usually measured\" -> \"the difference is usually measured\" (full sentence)\n- l.90-91: \"Doing so... models\" -> I think this sentence is unnecessary \n- l.147: \"the question of whether adversary\" -> \"the question of whether the adversary\"\n- l.148: \"adds another dimension of adaptivity to the story\" -> weird formulation? maybe change to \"\"\n- l.155-156: \"The focus of this work is mostly on the feature selection as one of the important tasks in machine learning.\" unclear formulation, and I think ranking machine learning tasks is a bit unnecessary. Perhaps something like \"This work focuses on feature selection, which is a significant task in machine learning.\" would be better?\n- l.181 \"...}, we denote the set of (indices of) its non-zero coordinates of $\\theta\\in R^d.\" -> \"...} to denote the set of (indices of) its non-zero coordinates.\"\n- l.196 \"data data-oblivious\" -> \"data-oblivious\"; probably better to break the sentence in two after \"an adversary A\"\n- l.197 \"by adversary's budget\" -> \"by the adversary's budget\"\n- l.202 \"such that each row and\" -> incomplete sentence\n- l.214 \"feature flipping attack\" -> \"feature-flipping attack\"\n- l.244 \"theta* where number\" -> \"theta*, where the number\"\n- l.245 \"are bounded\" -> \"is bounded\"\n- l.246 remove hat from theta^*; add a period; \"by optimizing the a\" -> \"by optimizing the\"\n- l.251 \"the robust version, considers\" -> \"the robust version considers\"\n- l.272 \"Bellow\" -> \"Below\" \n- Defn 3.2: It took me a while to parse the sentence \"if its i-th coordinate of model learn on it is 0\", perhaps something like \"the i-th coordinate of the feature vector obtained by running Lasso on [X | Y] is 0\" would be better.\n- l.287 \"Gaussian distribution\" -> \"Gaussian distributions\"\n- l.290-291 \"We first show that each feature in the Gaussian sampling process the probability of the i-th feature being k-unstable is proportional to $e^{\\lambda - k}$\" -> \"We first show that each feature in the Gaussian sampling process has a probability of being k-unstable that is proportional to $e^{\\lambda - k}$\"\n- l.317 incomplete sentence: \"... identifies which feature The key here ...\"\n- l.323 \"an feature\" -> \"a feature\"\n- l.358 \"We also explored\" -> \"We also experimentally explored\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the assumptions needed to show the result are perhaps a limitation worth mentioning (or mentioning again outside of the introduction).\n\n1. Lasso estimator: the results would be stronger if the adversary was competing against an arbitrary learner (though the Lasso analysis is interesting in its own right). \n\n2. There is no limitation on the knowledge and computational power of the adversary as indicated in the proof of Prop 3.5: \"After getting the dataset [X | Y] the adversary inspects the dataset to find out which coordinate is unstable and find a poisoning dataset that would add that unstable coordinate to the support set of the model.\" (l. 768-770) -> the instability is characterized by the existence of a poisoned dataset that causes the supports of the feature vectors gotten by Lasso on clean and poisoned data to differ. I believe this assumes that the adversary has a way of finding such a dataset -- it would perhaps be worth highlighting this again, even if it was touched on in the introduction (l.118-120).\n\n3. Distributional knowledge: the fact that the adversary knows the distribution of the data seems like quite a strong assumption -- though the separation result remains interesting (the authors adequately address this limitation on lines 97-99; it would be perhaps worth adding whether this is a common assumption for poisoning attacks in the literature). \n", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "5n5w4wIV1qS", "reviewer": "Reviewer_xT4q", "summary": "This paper studies the \"data-oblivious poisoning attack,\" which presumes an adversary without the knowledge of the victim's training set. Once the authors define the threat model of an oblivious attack, they formulate the security game where an adversary crafts poison samples and a victim trains classifiers on the contaminated training set. Under this formulation, the authors compare the power of a full-knowledge attacker with that of the \"oblivious attack.\" In there, the authors show that oblivious attackers are weaker than full-knowledge attackers. In evaluation, the authors demonstrated that the number of poison samples requires to cause the same deviation of a specific feature becomes larger in \"oblivious\" attacks.\n", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**I reviewed this paper in NeurIPS 2020. I compare the two submissions (this one and the previous one) and found that the major concerns that I raised in the review have not been resolved yet. Therefore, I am leaning toward rejecting this paper. I also shared the detailed comments below.**\n\n----\n**[Major concerns]**\n\n\nAs this paper presents a new attack, \"data-oblivious adversary,\" I look at this paper as offensive research. On the offensive side, I evaluate the paper with two criteria:\n\n(1) Does this paper help us to understand the unknown worst-case attacker?\n(2) Does it provide fundamental insights in building defenses against an attack?\n\nUnfortunately, I don't think this paper still serves any of those purposes. The conclusions are:\n\n(1) The paper studied a weaker poisoning attack and found that the attack is weak.\n(2) The authors argue that, since the attack is weak, we are safe as long as the data is not shared with the adversary.\n\nWe already know (1), I am not sure whether (2) is true, and the claim is only provable in LASSO (Line 66).\n\nSo, there is no addition to the knowledge that prior work found.\n\n\n--------\n**[My lasting concerns]**\n\nIn the previous review, I examined this paper with the following three dimensions:\n\n\n**(1) Is the research question well-motivated?**\n\nI am still super-confused about why we need to consider the \"data-oblivious poisoning\" attack.\n\nFirstly, I am not sure it has research value. Recall that there has been a vast literature on the full-knowledge poisoning attacks, and we know what would be the worst-case consequences of data poisoning attacks and the defenses on that (e.g., in [1,2]). Then, I couldn't find the reason we should consider any sub-optimal poisoning attacks. If a defense can defeat the strong attacks, it can, of course, work for the \"oblivious attackers\". Even the experimental results in this paper also reached the same conclusion --- an oblivious attacker is weaker than the full-knowledge attacker.\n\nSecondly, the assumption---an adversary may not know the training samples---itself is under-specified and could be incorrect as there are millions of easy ways an adversary approximates the statistics of a victim's training set. The fundamental assumption in ML is that the training and the testing samples are drawn from an underlying data distribution (using i.i.d sampling mechanism); thus, an attacker can exploit this. For example, one can train a surrogate model on samples crawled from public sources to estimate the impact of an attack on the actual victim model, which has been shown as \"transferable poisoning attacks\" in vast literature.\n\n**[New]** For the second point, the authors provide some motivating scenarios, e.g., when multiple parties compute a neural network. However, I am not sure those scenarios guarantee \"data-obliviousness.\" As long as the attacker has access to a model, they can extract the training samples and conduct much stronger poisoning attacks.\n\n\n**(2) Does this paper have clear, novel contributions?**\n\nI am still sure that the contribution is not clear and weak.\n\n**[New]** This paper claims that \"we provide theoretical evidence that obliviousness of attackers to the training data can indeed help robustness against poisoning attacks.\" I do not think that this is a contribution. In the paper, I cannot find any content that proves robustness against poisoning attacks. For example, I cannot find any metric that I can formally measure the robustness.\n\nSecondly, it's the same question that I asked in (1). Why do we need to know how much stronger full-information attackers are? Based on the poisoning literature, I assume the purpose is to know the limit of a poisoning attacker so that we can come up with accountable defense mechanisms against those strong attacks. But, as the authors already show the oblivious poisoning is already weaker, I can't see the benefits of knowing oblivious poisoning attacks.\n\n**[New]** The paper still contains a lot of under-specified terms such as \"close training set\" (how do you measure this similarity) or \"information complexity\" (how do you formally define this complexity?). The authors should clearly define them before developing further theoretical claims. Currently, the paper shoots vague terms in the introduction and related work and develops a theory in the following sections.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I could not find this in the manuscript.", "review_text": "", "extra_scores": {"ethical_concerns": "Nope.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "0ls_D-UsQfn", "reviewer": "Reviewer_pjvz", "summary": "This paper raises the need for separating the notions of data-oblivious poisoning attacks from data-aware poisoning attacks. Theoretical analysis on feature selection with LASSO show that data-aware adversaries are provably more devastating compared to data-oblivious adversaries. Empirical results on synthetic and real-world datasets also verify the arguments.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### **Originality**\n\nThe paper deals with the impact of keeping the training data secret from adversaries, while letting the attackers fully know the data distribution. This scenario is relatively realistic and has rarely been studied before.\n\n### **Quality**\n\nMain claims are theoretically supported for the case of feature selection with LASSO under the Gaussian setting. Experimental results validate the theoretical implications both on synthetic datasets sampled from Gaussian distributions and several real-world datasets.\n\n### **Clarity**\n\nThe paper is clearly written and well organized. Line 317: \"feature\" -> \"feature.\"\n\n### **Significance**\n\nThe separation result provided by the paper has several implications, including the possibility of designing new defenses for data-oblivious poisoning and the new motive for privacy, which I personally appreciate. \n\nHowever, the theoretical results only work for the case of feature selection with LASSO. It's still unclear whether the situation holds for the general classification and regression problems. Deriving theoretical or experimental results on these problems would further broaden the impact of this paper.\n\nNevertheless, the paper gives a solid theoretical case for the separation result, and brings implications for designing defense mechanisms that leverage the secrecy of training data. I think it's meaningful for many applications such as the scenario of cryptographically secure multi-party protocols for neural network training.\n\nOverall, I’m on the border for this paper. I would be happy to adjust my rating based on the discussion and revision.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors may need to discuss how the results for the case of feature selection with LASSO generalize to more general machine learning problems such as classification and regression.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper got a score of 3786, while all 4 reviewers have concerns about the narrow field of the paper, i.e., only focused on LASSO and did not provide analysis on the widely used neural networks. In the authors' rebuttal, the authors evaded the question and said their result is just the first step. After discussing with SAC, the thoughts that having access to the actual data is more important than we might have otherwise thought is indeed interesting, i.e., the attack can be still weaker than data-aware one even we can estimate the distribution from publicly available data. Although the newly designed problem has some strong assumptions and may not be so practical, it provides some new insights on the poisoning attack research. Thus, the paper can be accepted if having slots. 
Decision: Accept (Poster)