Model-Targeted Poisoning Attacks with Provable Convergence
Authors: Fnu Suya
Saeed Mahloujifar
David Evans
Yuan Tian
Venue:  (2021)
Keywords: adversarial machine learning
data poisoning attack
convergence

Abstract: In a poisoning attack, an adversary with control over a small fraction of the training data attempts to select that data in a way that induces a model that misbehaves in a particular way desired by the adversary, such as misclassifying certain inputs. We propose an efficient poisoning attack that can target a desired model based on online convex optimization. Unlike previous model-targeted poisoning attacks, our attack comes with provable convergence to any achievable target classifier. The distance from the induced classifier to the target classifier is inversely proportional to the square root of the number of poisoning points. We also provide a lower bound on the minimum number of poisoning points needed to achieve a given target classifier. Our attack is the first model-targeted poisoning attack that provides provable convergence, and in our experiments it either exceeds or matches the best state-of-the-art attacks in terms of attack success rate and distance to the target model. In addition, as an online attack our attack can incrementally determine nearly optimal poisoning points. 

Under review as a conference paper at ICLR 2021
POISONING ATTACKS
WITH PROVABLE CONVERGENCE
Anonymous authors Paper under double-blind review
ABSTRACT
In a poisoning attack, an adversary with control over small fraction of the training data attempts to select that data in way that induces model that misbehaves in a particular way desired by the adversary, such as misclassifying certain inputs. We propose an efficient poisoning attack that can target a desired model based on online convex optimization. Unlike previous ttrel-targeted poisoning attacks, our attack comes with provable convergence to any achievable target classifier. The distance from the induced classifier to the target classifier is inversely proportional to the square root of the number of poisoning points. We also provide lower bound on the minimum number of poisoning points needed to achieve a given target classifier. Our attack is the first model-targeted poisoning attack that provides provable convergence, and in our experiments it either exceeds or matches the best state-of-the-ae attacks in terms of attack success rate and distance to the target model. In addition, as an online attack our attack can incrementally determine nearly optimal poisoning points.
INTRODUCTION
State-of- of-the-art machine learning models require a large amount of labeled training data, which often depends collecting data and labels from untrusted sources. A typical application is email spam filtering, where a spam detector filters out spam messages based on features (e.g., presence of certain words) and periodically updates the model based on newly received emails labeled by users. In such a setting, spammers can generate "non-spam" messages by injecting non-related words or benign words, and when models are trained on these "non-spam" messages, the filtering accuracy will drop significantly (Lowd & Meek, (2055). Such attacks are known as poisoning attacks, and training process that collects labels or data from untrusted sources potentially vulnerable them.
Poisoning attacks can be categorized into objective-driven alfucks and model-targeter allacks de- pending on whether a target model considered in the attack process. Objective-driven attacks have specific attacker objective and aim to achieve the attack objective by generating the poisoning points; model-ted ttrre-taeeeeed attacks have a specific target classifier in mind and aim to induce that target classifier by generating minimal number of poisoning points. Objective-driven attacks are most commonly studied in the existing literature. The attacker objective is typically one of two extremes: indiscriminate attacks, where the adversary's goal is simply to decrease the overall accuracy of the
model (Biggio et al.] 2012 Xiao et al.) 2012: Mei & Zhu 2015b) Steinhardt et al. 2017 Koh et al..
2018); and instance-targeted attacks, where the goal is produce classifier that misclassifies
a particular known input (Shafahi et al. 2018 Zhu et al. 2019; Koh & Liang 2017). Recently, Jagielski al. (2019) introduced more realistic attacker objective known as a subpopulation attack.
where the goal is to increase the eтror rate or obtain a particular output for defined subpopulation of the data distribution. Attacker objectives for realistic attacks are diverse and designing unified and effective attack strategy for different attacker objectives is hard. Gradient-based local optimization is most commonly used to construct poisoning points for a particular attacker objective (Biggio et al. 2012 Xiao et al. 2012 Mei & Zhu 2015b; Koh & Liang 2017 Shafahi et al., 20188 Zhu et al. 2019). Although these attacks can be modified to fit other attacker objectives, since they are based on local optimization techniques they easily get stuck into bad local optima and fail to find effective sets of poisoning points (Steinhardt et al.) 2017 Koh et al.] (2018). To circumvent the issue of local optima, Steinhardt et al. (207)) formulate indiscriminate attack min-max optimization problem and

---

Under review as a conference paper at ICLR 2021
solve it efficiently using online convex optimization techniques. However, the strong min-max attack only applies to the indiscriminate setting.
In contrast, model-targeter attacks incorporate the attacker objective into target model and hence, the target model can reflect any attacker objective. Thus, the same model-targeted attack methods can be directly applied
range of indiscriminate and subpopulation attacks just by finding suitable target model. Mei & Zhu (2015b) first introduced a target model into a poisoning attack, but their attack is still based on gradient-basee local optimization techniques and suffers from bad local optima (Steinhardi et al. 2017: Koh el al. 2018). Koh et al. (2018) proposed the KKT attack, which converts the complicated bi-level optimization into simple convex optimization problem utilizing the KKT condition, avoiding the local optima issues. However, their attack only works for margin based losses and does not provide any guarantee on the number of poisoning points required to converge to the target classifier.
In this work, we focus on model- targett attacks and aim to understand the feasibility of poisoning adversary to induce any target model. In particular, we find both theoretical and empirical bounds on the sufficient (and necessary) number of poisoning points to get close to a specific target classier.
Contributions. Our main contributions involve developing a principled and general model-targeted poisoning attack strategy, along with a proof that the model it induces converges to the target model. Our poisoning method takes as input a target model, and produces a set of poisoning points. We prove that the model induced by training on the original training data with these points added, converges to the target classifier as the number of poison points increases, given that the loss function is convex and proper regularization is adopted in training (Theorem 4.1, l. Previous model-targeter attacks lack of such convergence guarantees. We then prove lower bound on the minimum number of poisoning points needed to reach the target model (Theorem 4.2), given that the loss function for empirical risk minimization is convex. Such lower bound can be used estimate the optimality of model-targeteer poisoning attacks and also indicate the intrinsic hardness of attacking different targets. Our attack also efficient in incremental poisoning scenario incrementally find poisoning points that are nearly optimal. Previous model-targeted attacks work with fixed number of poisoning points and need to know the poisoning budget in advance. We run experiments to compare our attack to the state-of-the-eee We first evaluate the convergence our attack to the target model and find that, under same number of poisoning points, classifiers induced by our attack are closer to the target models than the best known attack, for all the target classifiers we tried. Then, we evaluate the success rate of our attack, and find that it has superior performance than the state-of-the-atr in the more realistic subpopulation attack scenario, and comparable performance in the conventional indiscriminate attack scenario (Section 5)
works in an online fashion and can
model-targete
attack (Koh et al. (018).
2 PROBLEM SETUP
The poisoning attack proposed in this paper applies multi-class prediction tasks regression problems (by treating the response variable as an additional data feature), but for simplicity of presentation we consider binary prediction task, h X + where X C Rd and y = (+1,-1); The prediction model h is characterized by parameters 0 E θ C Rdd We define the non-negative convex loss on an individual point, (a, y), as 1(0; x, y) (c.g.. hinge loss for SVM model). We also define the empirical loss over a set of points A as L(0; A) = (o.ije [(0; 2,)
We adopt the game-theoretic formalization of the poisoning attack process from Steinhardt et al. (2117) to describe our morel-targeted attack scenario:
1. N data points are drawn uniformly at random from the true data distribution over X' x y and form the clean training set, D...
2. The adversary, with knowledge of De. the model training process and the model space O generates a target classifier fp E ④ that satisfies the attack goal.
3. The adversary produces a set of poisoning points, D,, with the knowledge of D... model training process, θ and Op-
4. Model builder trains the model on D. D.P and produces classifier, Patk-
Similar to previous works, in this paper, focus on designing model-targeted attack that works for any achievable target model and leave the exploration of finding hetter target classifiers the future work.
2

---

Under review as a conference paper at ICLR 2021
The adversary's 's goal is that the induced classifier, aakk is close to the desired target classifier, 0p (Section [42 discusses how this distance is measured). Step 2 corresponds to the target classifier generation process. Our attack works for any target classifier, and in the paper we do not focus on the question of how to find the best target classifier to achieve a particular adversarial goal but simply adopt the heuristic target classifier generation process from Koh al. (2018). Step 3 corresponds to our model-targeted poisoning attack, and is also the main contribution of the paper.
We assume the model builder trains a model through empirical risk minimization (ERM) and the training process details are known to the attacker:
1 [De]
0₂ = arg min Age
[(0;Da) + Cn R(0)
where R(0) is the regularization function (e.g.. 21101 for SVM model).
Threat Model. We assume an adversary with full knowledge of training data, model space and training process. Although this may be unrealistic for many scenarios, this setting allows us to focus on a particular aspect of poisoning attacks, and is the setting used in many prior works (Biggio & Zhu 2015b; Steinhardt et al.] 2017; Koh et al. 2018 Shafahi et al. 2018). We assume an addition-only attack where the attacker only adds poisoning points into the clean training set. A stronger attacker may be able to modify remove existing points, but this typically requires administrative access to the system. The added points are unconstrained, other than being value elements of the input space. They can have arbitrary features and labels, which enables to perform the worst case analysis on the robustness of models against addition-only poisoning attacks, Although some previous works also allow arbitrary selection of the poisoning points (Biggio et al. 201 1 Mei
et al.
Zhu 2015b Steinhardt et al.) 2017 Koh et al. 2018), others put different restrictions on the poisoning
appoints. clean-label attack assumes adversaries can only perturb the features of the data, but the
label is given by an oracle labeler (Koh & Liang 2017 (Shatahi et al., [2018] Zhuu et al.) [2019] Huang ct al. 2020). In label-flippigg attacks, adversaries are only allowed to change the labels (Biggio et al.
2011 Xiao et al. [2012] 2015: Jagielski et al.] (019). These restricted attacks are weaker than the
poisoning attacks without restrictions (Koh et al. 2018: Hong et al. 2020).
3 RELATED WORK
The most commonly used poisoming strategy is gradient-based attack. Gradient- based attacks iteratively modify a candidate poisoning point (ø, ÿ) in the set DD, based on the test loss defined on (keeping fixed). This kind of attack was first studied on SVM models (Biggio et al.) 2012). and later extended to linear and logistic regression (Mei & Zhu 20155), and recently to larger neural network models (Koh & Liang 2017 Yang et al. Munoz- et al. 2017 Shafahi et al. 2018 Zhu et al. Huang et al. 2020). Jagielski et (2018) also studied gradient attacks and principled defenses on linear regression tasks. Their work studies linear regression while in this paper, we mainly focus on binary classification, although our attack can also be extended to regression tasks. More importantly, our attack aims to induce target model by generating poisoning points while (Jggeeskk et al. (2018)'s 's attack tries to increase the Mean Squared Error of the linear regression task with fixed poisoning budget. In addition classification and regression tasks, gradient-based poisoning attacks are also applied to topic modeling (Mei & Zhu 2015a), collaborative filtering (Li al. 2016) and algorithmic fairness (Solans et al. 2020).
Besides the gradient-based attacks, researchers also utilize generative adversarial networks to craft poisoning points efficiently for larger neural networks, however, the effectiveness of the attack is limited (Yang et al.] 2017, (7777
et al.] 2019). The strongest attacks so far are the KKT attack (Koh et al.) (018)) and the min-max attack (Steinhardt et af., 2017: Koh et al. 2018). However, the KKT attack cannot scale well for multi-class classification and is limited to margin based losses (Koh et al.) 2018). The min-max attack only works for indiscriminate attack setting, but additionally provides a certificate on worst case test loss for fixed number of poisoning points. We are also inspired by Steeinhartt et al. (2017) to adopt online convex optimization to instantiate our model-targete attack, but now deals more general attack scenario. We also distinguish ourselves from the poisoning attack against online learning (Wang & Chaudhuri 2018). The attack against online learning considers a setting where training data arrives in streaming manner while
3

---

Under review as a conference paper at ICLR 2021
consider the offline setting with training data being fixed. Another line of work studies "targeted" poisoning attacks where an adversary guarantees to increase the probability of an arbitrary "bad" property (Mahloujifar et al. 2019a; 2017 2019b), long that property has some non-negligible chance of naturally happening. These attacks cannot be applied in the model-targeted setting as the probability of naturally producing specific target model is often negligible. Related to Theorem 4.2 Ma et (2019) also derived a lower bound on number of poisoning points (to induce a target model), but their lower bound only applies when differential privacy is deployed during the model training process (and hence hurts model utility), which is different from our problem setting.
4 POISONING ATTACK WITH A TARGET MODEL
Our new poisoning attack determines target model and selects poisoning points to achieve that target model. The target model generation is not our focus and we adopt the heuristic approach proposed by KKhh et al. (2018). For the new poisoning attack, first, we show the algorithm that generates the poisoning points Section[4.] and and then prove that the generated poisoning points, once added to the clean data, can produce classifier that asymptotically converges to the target classifier in Section 4.2
4.1 MADEEETARRGETED POISONING WITH ONLINE LEARNING
The main idea of our model-targeted poisoning attack, as outlined in Algorithm [ is to sequentially add point into the training set that have maximum loss difference between the intermediate model obtained so far and the target model, and by training models on the updated training set, we actually minimize the gap in the loss of the intermediate classifier and the target classifier. Repeating the process then eventually generates classifiers that have similar loss distribution as the target classifier. We show in Section why similar loss distribution implies convergence.
Algorithm 1 Model MoodelTTrgetedPoisoningg
Input: D.,, the loss functions (L and l), 0p
Output: D,
1: D.
2: while stop criteria not met do
3: 0, = arg min [0; De U (D,)
4: (x",v")= = arg x
xxy ((11,,))) 1(0p:
5: D, = Dr ((x' y²)}
6: end while
7: return Dr
Algorithm I requires the input of clean training set De, the Loss function (L for set of points and I for individual point) and the target model 0z. The output from Algorithm will be the set of poisoning points Dp. The algorithm is simple: first, adversaries train the intermediate model 6, on the mixture of clean and poisoning points D. DD with Dp an empty set in first iteration (Line 3). The adversary then searches for the point that maximizes the loss difference between 0, and 0, (Line 4). After the point of maximum loss difference is found, it is added to the poisoning set Dr (Line 5). The whole process repeats until the stop condition is satisfied in Line 2. The stop condition is flexible and it can take various forms: 1) adversary has budget T' on number of poisoning points, and the algorithm halts when the algorithm runs for T iterations; 2) the intermediate classifier O, is closer to the target classifier (than a preset threshold e) in terms of the maximum loss difference, and more details regarding this distance metric will be introduced in Section 4.2) 3) adversary has some requirement on the accuracy and the algorithm terminates when O, satisfies the accuracy requirement. Since we focus on producing a classifier close to the target model, we adopt the second stop criterion that measures the distance with respect to the maximum loss difference, and report results based on this criterion in Section 5
A nice property of A is that the classifier Oatk trained on D.UD, is close to the target model 8, and asymptotically converges to 9p. Details of the convergence will be shown in the next section. The algorithm may appear to be slow, particularly for larger models due to requirement of repeatedly training a model in line 3. However, this is not an issue. First, as will be shown in next section, the algorithm is an online optimization process and line 3 corresponds to solving the online optimization
4

---

Under review as a conference paper at ICLR 2021
problem exactly. However, people often use the very efficient online gradient descent method to approximately solve the problem and its asymptotic performance is the same Second, if we solve the optimization problem exactly, we can add multiple copies of (a", y into Dp each time. This reduces the overall iteration number, and hence reduces the number of times retraining models. The proof of convergence will be similar. For simplicity in interpreting the results, we do not use this in our experiments and add only one copy of (z", each iteration. However, we also tested the performance by adding two copies of (x" yy" and find that the attack results are nearly the same while the efficiency is improved significantly. For example, for the experiments we tried on MNIST 1-7 dataset, by adding 2 copies of points, with same number of poisoning points, the attack success rate decreases at most by 0.7% while the execution time is reduced approximately by half.
2012).
4.2 CONVERGENCE OF OUR POISONING ATTACK
Before proving the convergence of Algorithm|] I trained on De Dp to the target model Pp. First, we define general closeness measure based on their prediction performance which we will use to state our convergence theorem:
we need to measure the distance of the model aatk
Definition (Loss-based distance and e-close). For two models 0₁ and 02, space x y and a loss function (0;; y), we define loss-based distance Dix,y: θ x θ + Ras max 1(01;,,1) v) I(02;r,y), (x.))Xxy
Dixxy((1,, 02)
and we say model 0, e-close to model 0g when the loss-based distance from O2 to 0g is upper bounded by e.
Why is loss-based distance a meaningful notion of closeness? We argue that this notion captures the "behavorial" distance between two models. Namely, if 0, is e-close (as measured by loss- based distance) to 02 and vice versa, then 0 and 0g would have almost equal loss on all the points, meaning that they have almost the same behavior across all the space. Note that general definition of loss- based distance does not have the symmetry property of metrics and hence is not a metric. However, it has some other properties of metrics in the space of attainable models. For example, if some model attainable using ERM. no model could have negative distance to it. To further show the value of this distance notion, in Appendix B we demonstrate an (E)) upper bound on the é - of difference between two models that are e-close with respect to loss-based distance for the special case of Hinge loss. For Hinge loss, also satisfies the bi-directional closeness, that is if 01 is e-close 62, then 8g is Occ)-close to 9 (details can be found in Corollary B.2.1). and the proof details can be found in Appendix B In the rest of the paper, we will use terms c c-close or e-closeness to denote that a model is e away from another model based on the loss-based distance.
Our convergence theorem uses the loss-based distance to establish that the attack of Algorithm converges to the target classifier:
Theorem 4.1. After at most T steps, Algorithm [ will produce the poisoning set D, and the classifier trained on De U p,,tt is e-close to 0p. with respect to loss-based distance, Di.x..y.
aTT) L(0p: D.) L(Oc:D)
T T
where, 7 is a constant for given 8p and classification task, and (T) is the regret of the online algorithm when the loss function used for training is convex.
Remark 1. Online learning algorithms with sublinear regret bound can be applied show the convergence. Here, we adopt results from McMahan (2017). Specifically, ((T)) is in the order of Ollog T)) and we have S ( ((logT) T when the loss function is additionally Lipschitz continuous and the regularizer R(A) strongly convex, and c > O when T +oo. (<T) is also in the order of Olog T) when the loss function used for training is strongly convex and the regularizer is convex.
Proof idea. The full proof of Theorem 4.1 is in Appendix A Here, we only summarize the high level proof idea. The key idea is to frame the poisoning problem online learning problem. In this formulation, each step of the online learning problem corresponds to the ith poison point (æ,, 9:). In particular, the loss function at iteration i of the online learning problem is set to 2(:; 22, y:). Then,
5

---

Under review as a conference paper at ICLR 2021
show that by defining the parameters of the online learning problem in careful way, the output of the vollow-the-leade (FTL) algorithm to training model on dataset consisting of the clean points and the first - 11 poisoning points. On the other hand, the way the poisoning points are selected, we can show that at the ith iteration the maximum loss difference between the target model and the best induced model so far would be smaller than the regret of the FTL algorithm divided by the number of poisoning points. The convergence bound of Theorem 4.1 boils down to regret analysis of the algorithm based on the loss function. Since we are assuming the loss function is convex with a strongly convex regularizer (or strongly convex loss function with a convex regularizer), we can show that the regret bounded by Oloog 7') and hence the loss distance between the induced model and the target model converges to 0.
Shwarrz 2012) at iteration i is a model that is identical
Implications of Theorem 4.1 The theorem says that the loss-based distance of the model trained on De U Dr to the target model correlates the loss difference between the target model and the clean model 6g (trained on Dz) on De. and correlates inversely with the number of poisoning points. Therefore, it implies 1) if the target classifier f, has lower loss on D,, then it is easier to achieve the target model, and 2) with more poisoning points, we get closer to the target classifier and our attack will be more effective. The theorem also justifies the motivation behind the heuristic method in Koh itt al. (2018) to select target classifier with lower loss on clean data. For the indiscriminate attack scenario, we also improve the heuristic approach by adaptively updating the model and producing target classifiers with much lower loss on the clean set. This helps to empirically validate our theorem. Details of the original and improved heuristic approach, and relevant experiments are in Appendix D.I
4.3 LOWER BOUND ON THE NUMBER OF POISONING POINTS
We first provide the lower bound on number of poisoning points required for producing the target classifier in addition only setting (Theorem 4.2p and then explain how the lower bound estimation can be incorporated into Algorithm | The intuition behind the theorem below is, when the number of poisoning points added to the clean training is smaller than the lower bound, there always exists classifier with lower loss compared to 9p and hence the target classifier cannot be attained.
Theorem 4.2 (Lower Bound). Given a target classifier 0p, to reproduce 8, by adding the poisoning set D, into D the number of poisoning points [D,l cannot be lower than
L(Op; De) Da) (CR((((0p) R())) supx,y (1(0;z,y) - 1[0p) x, x.,)) v)) + CR(B(O) R(O,))
sup z(0)
Corollary 4.2.1. If we furteer assume bi bi-directional closeness in the loss-based distance, we can also derive the lower bound on number of poisoning points needed to induce models that are e-close the target model. More precisely, i being c-close to 02 implies that 0₂ is also k close to 01. then we have,
L(O;; - - L(O:D.) NCR R NNe
sup 2 0
supz.y (1(0; 2, y) 1(0p: v)) + CC R' + KE
where Rt is an upper bound on the nonnegative regularizer R(0)-
The formula for the lower bound in Theorem 4.2 (and also the lower bound in Corollary 4.2.T) can be easily incorporated into Algorithm T to obtain tighter theoretical lower bound. We simply need to check all of the intermediate classifier 0: produced during the attack process and replace 0 with O., and the lower bound can be computed for the pair of 0g and 0p. Algorithm [ then additionally returns the lower bound, which is the highest lower bound computed from our poisoning procedure.
5 EXPERIMENTS
We first describe our experimental setup regarding the datasets, models, attacks and target classifiers. Next, we present the experimental results by showing the convergence of Algorithm [] the comparison of attack success rates to state-of-the -ftte-of-the-att poisoning attack, and the theoretical lower bound for inducing given target classifier and its gap to the number of poisoning points used by our attack.

---

Under review as a conference paper at ICLR 2021
We are most interested in subpopulation attacks, since they correspond to the more realistic attacker goal of impacting the classifier outputs for a targeted subpopulation. Therefore, in the main body, we introduce the results of SVM model on the Adult dataset (Dua & Graff 2017) in the subpopulation poisoning scenario. For completeness, we also evaluate our attack on SVM model on MNIST 1-7 dataset in the indiscriminate poisoning scenario but defer details those experiments to Appendix [ Our findings for the indiscriminate attacks are that the attack gradually and consistently converges to the target model in terms of the maximum loss difference and the Euclidean distance the target, with attack success rates that are comparable to the state-of-the-an art attack (unlike the subpopulation attacks, where our attack produces superior results). To further verify the universal effectiveness of our attack, we also evaluate our attack on additional dataset (Dogfish) and model (logistic regression), and more details can be found in Appendix F
Dataset, Model and Attacks. For the subpopulation attack experiments, we use the Adult dataset (Dua & Graff 2017). This dataset was used for evaluation by the first subpopulation attack paper (Jagielski et al. 2019). We downsampled the Adult dataset to ensure it is class-balanced and we ended up having 15,682 training and 7,692 test examples. We conduct experiments on linear SVM model and compare our model-targeted poisoning attack in Algorithm [ to the state-of-the-an KKT attack (Koh et al. 2018). We do not include the model- targettd attack from Mei & Zhu (2015b) because it underperforms the KKT attack (Koh et al. 2018). We also do not include objective- -diiven attacks because our main goal here is to evaluate how well our attack approaches a given target model, across a range of target models. Madel-targeted attacks can be compared to objective-driven attacks with regards to given attacker objective by choosing the target model in a careful way. We show some heuristies of choosing such target models and comparison to some objective-driven attacks in Appendix B
Both our attack and the KKT attack take as input a target classifier and the original training data, and output a set of poisoning points selected with the goal that the induced classifier is as close as possible to the target classifier. We compare the effectiveness of the attacks in selecting poisoning points that converge to given target classifier by testing the attacks using the same target model.
The KKT attack requires a target number of poisoning points as an input while our attack is more flexible and can either take target number of poisoning points or a threshold for c-close distance to the target model. Since we do not know the number of poisoning points needed to reach some attacker goal in advance for the KKT attack, we first run our attack and produce a classifier that satisfies the selected e-close distance threshold. The loss function is set as the hinge loss since we target an SVM model in experiments and we set 0.01 for all these experiments. Then, we use the size of the poisoning set returned from our attack (denoted by np)) as the input to the KKT attack for the target number of poisons needed. We also compare the two attacks with varying numbers of poisoning points up to nn- For the KKT attack, its entire optimization process must be rerun whenever the target number of poisoning points changes. Hence, it is infeasible to evaluate the KKT attack on many different poisoning set sizes. In our experiments, we run the KKT attack five poisoning set sizes: 0.2 np. 0.4 np. 0.6 Rep 0.8 Ny. and np. In contrast, we simply run our attack for iterations up to the maximum number of poisoning points, collecting a data point for iteration up to ny.
Subpopulations. We identify the subpopulations for the Adult dataset using k-means clustering techniques (ClusterMatch (Jagielski et al. (019)) to obtain different clusters (k- = 20 in our case). For each cluster, we select instances with label "<=50K" to form the subpopulation (indicating all instances in the subpopulation are in low income group). This way of defining subpopulation is rather arbitrary (in constrast to a more likely attack goal which would select subpopulations based on demographic characteristics), but enables us to simplify the analysis. From the 20 subpopulations obtained, we select three subpopulations with the highest test accuracy on the clean model and they all have 100% test accuracy, indicating all instances in these subpopulations are correctly classified as low income. This enables us to use "attack success rate" and "accuracy" without any ambiguity on the subpopulation- for each of our subpopulations, all instances are originally classified low income, and the simulated attacker's s goal is to have them classified as high income.
For each subpopulation, we use the heuristic approach from Koh et al. (018) to generate target classifier that has 0% accuracy (100% attacker success) on the subpopulation, indicating that all subpopulation instances are now classified as high income.
7

---

Under review as a conference paper at ICLR 2021
2.0
Eaclidean Didanes
0.8
1.5
0.6
Moa
1.0
0.2
Our Allack
KKT Attack
KKT Attakk
0.0
1500
Num of Possons
Num Puiscas
(a) Max Loss Difference to Target
(b) Euclidean Distance to Target
Figure 1: Attack convergence (results shown are for the first subpopulation, Cluster 0). The maximum number of poisons is set using the 0.01 -cloe threshold to target classifier.
Test Aoc Sahgoo
0.3
KKT Attock
Test Agc on Suhgagp
0.2
KKT Attock
Agc on Suhpoop
0.8
KKT Attaok
0..
0.4
0.2
0.2
0.3
Num of Poisons
Num
Poisons
Num Poisons
(a) Cluster 0
(b) Cluster 1
(c) Cluster 2
Figure 2: Test accuracy for each subpopulation with classifiers induced by poisoning points obtained from our attack and the KKT attack.
Cluster
Cluster
Cluster 2
Poisoning Points
1866
2097
2163.3 2.5
Lower Bound
1666.7 = 2.4 1831.4 + 5.0 1863.0 + 9.2
Table Poisoning points needed to achieve target classifiers induced from our attack. Top row means number of poisoning points used by attack. Bottom means the lower bound computed from Theorem 4.2 for the induced classifiers. All results are averaged over 4 runs, integer value in the cell means we get exactly same value for 4 runs and others are shown with the average and standard error.
Convergence. Figure shows the convergence of Algorithm [ [uusing both maximum loss difference and Euclidean distance the target. The maximum number of poisons (n,) for the experiments is obtained when the classifier from Algorithm| T 0.01-close to the target classifier, Our attack steadily reduces the maximum loss difference and Euclidean distance to the target model, in contrast the KKT attack which does not seem to converge towards the target model reliably. Concretely, at the maximum number of poisons in Figure [] both the maximum loss difference and Euclidean distance of our attack (to the target) is less than 2% of the corresponding distances of the KKT attack.
Attack Success. Next, we compare the classifiers induced by the two attacks in terms of the attacker's goal of reducing the test accuracy on the subpopulation. Figure Souure@shoee shows the accuracy results for the three subpopulations. For each test, the maximum number of poisoning points is obtained by running our attack with target of 0.01-closeness (in loss-based distance). For the three subpopulations, at the maximum number of poisons, our attack much more successful than the KKT attack the induced classifiers have 0.5% accuracy compared to 15.4% accuracy for KKT subpopulation 1, 0.0% compared to 6.9% on subpoulation 2, and 0.3% compared to 20. 1% on subpoplation
Near Optimality of Our Attack. In order to show the optimality of our attack, calculate lower bound on the number of poisoning points needed to induce the model that is induced by the poisoning points that are found by attack. We calculate this lower bound on the number of poisons using Theorem 4.2 (details in Section 4.3). Note that Theorem 4.2 provides a valid lower bound based any intermediate model. In order get lower bound the number of poisoning points,
8

---

Under review as a conference paper at ICLR 2021
only need to Theorem 4.2 the encountered intermediate models and report the best one. We do this by running Algorithm| using the induced model (and not the previous target model) as the target model, terminating when the induced classifier is 0.01-close the given target model. We then consider all the intermediate classifiers that the algorithm induced across the iterations. Our
calculated lower bound in Table shows that the gap between the lower bound and the number of used poison points is relatively small. This means our attack is nearly optimal in terms of minimizing the number of poisoning points needed induce the target classifier.
CONCLUSION AND DISCUSSION
We propose a general poisoning framework with provable guarantees reach any achievable target classifier, along with a lower bound on the number of poisoning points needed. Our attack is generic tool that first captures the goal adversary as a target model, and then focuses on the power of attacks to induce that model. This separation enables future work to explore the effectiveness of poisoning attacks corresponding to different adversarial goals. Our framework also applies in scenarios where adversaries first remove points and then add new points into the training set. We have not considered defenses in this work, and is important to study the effectiveness of our attack against data poisoning defenses. Defenses may be designed the limit the search space of the points with maximum loss difference and increasing the number of poisoning points needed.
One limitation of our framework is the requirement in the concavity of the difference of loss functions to efficiently search for its maximum value. However, our approach might still be effective in these cases by using local optimization techniques to search for poisoning points with (approximate) maximum loss difference and we have demonstrated this in the case of logistic loss. More formally, if the approximate maximum loss difference found from local optimization techniques is within constant factor from the globally optimal value 1 (i.e., 1 2 al", 0 < < 1), then we still enjoy similar convergence guarantees. It is important to note that the convergence property of our attack holds (with strongly convex regularizer) for any Lipschitz and convex loss function, and does not require the loss difference to be concave. The theoretical guarantees in the paper do not apply to non-convex models, although it might be possible to empirically apply our attack to these models. Incorporating online learning for non-convex functions might be one possible path to extend our theoretical analysis into non-convex settings.
REFERENCES
Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. In Asian Conference on Machine Learning. 2011.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. arXiv preprint 1206. 2012.
Steven Diamond and Stephen Boyd. Cvxpy: A python-embedded modeling language for convex optimization. The Journal of Machine Learning Research, 17(1):2909 2913, 2016.
Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017. URL http:: ics. www...d.mmmmmm..
Sanghyun Hong, Varun Chandrasekaran, Yigitcan Kaya, Tudor Dumitraş, and Nicolas Papernot. On the effectiveness of mitigating data poisoning attacks with gradient shaping. arXiv preprint arXiv:2002. /497, 2020.
W Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. Mctapoison: Practical general-purpose clean-label data poisoning. arXiv preprint arX1v:2004.00225,, 2020.
Gurobi Optimization Inc. Gurobi optimizer reference manual, 2020. URL
com/ htmm//dommenntt... wttpeeeeetttittt/.tt/. on prrefaan/ai wwwp/.indxx..mmm html
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium Security and Privacy (SP), pp. 19-35. IEEF, 2018.

---

Under review as a conference paper at ICLR 2021
Matthew Jagielski, Paul Hand, and Alina Oprea. Subpopulation data poisoning attacks. In NeurIPS 2019 Workshop on Robust Al in Financial Services, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1411.6980, 2014.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, 2017.
Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. arXiv preprint 1..0041111.00711, 2018.
Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. Data poisoning attacks on factorization- based collaborative filtering. In NeurIPS, 2016.
Daniel Lowd and Christopher Meek. Adversarial learning. In ACM SIGKDD Conference on Knowledge Discovery in Data Mining, 2005.
Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentiallly-riivaai learners:
Attacks and defenses. arXiv preprint arXiv: (903009000000 2019.
Saeed Mahloujifar, Dimitrios Diochnos, and Mohammad Mahmoody. Learning under p-tampering attacks. arXiv preprint arXXv:1711.03700 2017.
Saeed Mahloujifar, Dimitrios
Diochnos, and Mohammad Mahmoody. The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. In AAAI Conference on Artificial Intelligence, 2019a.
Saced Mahloujifar, Mohammad Mahmoody, and Ameer Mohammed. Universal multi-party poisoning attacks. In International Conference on Machine Learning. 2019b.
H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning, The Journal of Machine Learning Research, 18(1):31173116, 2017.
Shike Mei and Xiaojin Zhu. The security of Latent Dirichlet Allocation, In Artificial Intelligence and Statistics, pp. 681-689, 2015a.
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. In AAAI Conference Artificial Intelligence, 2015b.
Luis Munioz-Gonzáler Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back-gradient optimization. In ACM Workshop on Artificial Intelligence and Security, 2017.
Luis Gonzlllo Bjarne Pfitzner, Matteo Russo, Javier Carnerero-Cano, and Emil C Lupu. Poisoning attacks with generative adversarial nets. arXiv preprint arXiv:1906.07773. 2019.
Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer. Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In NeurlPS, 2018
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
David Solans, Battista Biggio, and Carlos Castillo. Poisoning attacks algorithmic fairness. arXiv preprint arXivv2004.07401, 2020.
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In NewrlPS, 2017.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
10

---

Under review as a conference paper at ICLR 2021
Yizhen Wang and Kamalika Chaudhuri. Data poisoning attacks against online learning. arXiv preprint IrXiv:1806 08994, 2018.
Han Xiao, Huang Xiao, and Claudia Eckert. Adversarial label flips attack on support vector machines. In European Conference Artificial Intelligence, 2012.
Huang Xiao, Battista Biggio, Blaine Nelson, Han Xiao, Claudia Eckert, and Fabio Roli. Support vector machines under adversarial label contamination. Neurocomputing, 160:53-65 2015.
Chaofei Yang, Qing Wu, Hai Li, and Yiran Chen. Generative poisoning attack method against neural networks. arXiv preprint 1oXiv:703.01:: 2017.
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 preprini arXiv:1905.05897, 2019.

---

Under review as a conference paper at ICLR 2021
A PROOFS
In this section, we provide the proofs of the main theorems shown in this paper. For convenience, we restate all the theorems below while also referencing the main paper.
Before proving the main theorem, we introduce two new definitions and several lemmas to assist with the proof.
Definition 2 (Attainable models). We say A is CR-attainable with respect to loss function I and regularization function R if there exists training set DD such that
0 = arg min BEB
L(0; D) + CR R(0)
[D]
Lemma A.I. Let 0i and O2 be two CR-attainable parameters for some CR > 0 such that R(O,)) R(02). Then,
sup (1(02; y) (01:: -R(02) > CR- 2.9
Proof. Consider any attainable pairs of (0), f2) such that R(O,) > R(02) and let D, to be training set that the training algorithm produces the unique minimizer 0₁. Namely,
1 Di
0 arg min
L(0; Di) + CC R(0)
0
Since 0 minimizes the total loss on D uniquely, we have
[ L(02; Di) + On R(02) > | [(01; Di) + Cn R(01)
By rearranging the above inequality and by an averaging argument, we have
1
sup (1(02; x. y) 1(01: x),x) 2 |Di| L(02; x.y
[D1 L((1; CR (R(6,) R(02)).
Now since R(0,)= > R(02) we have
sup (1(0);,,)) [(0:: R((2)) CR-
z
Lemma A.2. Let F be the family of all Cn-attainable models. For any 01 E F, there is constant where for all 02 E F we have
sup (1(02; x. x. 1(01;2,y)) + Cn(R((2) R((:))))))))))) sup (1002;z,)) 1(01; x. v)) 23
2.31
where is positive constant related to, 0,. OR and other model parameters (fixed for given classification task).
Proof. We prove the lemma for = 1- - CR/CRRCCC for
sup(((f2;x.u) - 1(0122, (R) - R(02))
inf ByEF (st. B(0))> R(02)
a.
First, note that by Lemma A.1 have
C> CR 2 0.
(2)
which implies y is positive. Now consider subcases based the sign of R(02) R(O,) ):
12

---

Under review as a conference paper at ICLR 2021
Case 1: R(02) R(01) 0. In this case the inequality is straightforward:
sup (1(0g;4,)) v) 1(01;,,))) CR (R(02) R((1)) sup (1(02; 9) 1[01; y)) 2.9
(1 CR/C)
sup (1(02: 2, y) 1(01011 x));
2.9
where the last inequality is based on equation
Case 2: R((2) R((1)) O. From the definition of C/ we have
supa.y (I(02; xr v) 1(01;ar,))
R(O)) R(02) -
C
Equivalently, we can say
R(O2) R(01) suPa,y (1002; 2r, v) 1(01;0,,1
C
Replacing R(O2) R(O,) with the lower bound above completes the proof, namely
sup (((02;;; x 3) - (10 x. v)) CR((((())))))))))))))))))))))))) - R(OO)) 2 (1 CR/C) sup -10;) 2.9
2.8
With Definition 2 and the lemmas, we are ready to prove Theorem 4.1 (restating Theorem 4.1 from
Section 4.2
Theorem After at most steps, Algorithm 7 will produce the poisoning set D, and the classifier Irained on De U Dp is e-close to Op with respect to loss-based distance, Di.x.yy.fr
(TT) + L(Op: D.) I[6e; Dc)
T T
where, " is a constant for given 6p and classification task, and (TT) is the regret of the online algorithm when the loss function used for training is convex.
The goal of the adversary is to get c-close to 8p (in terms of the (potentially few) number of poisoned training data. The algorithm in essence an online learning problem and we transform AggorthhmTinne the form of standard online learning problem. Specifically, we adopt the follow the leader (FTL) framework to describe Algorithm in the language standard online learning problem. We first describe the online learning setting considered in this paper and the notion of the regret.
distance) by injecting
Definition 3. Let be a class of loss functions, θ set of possible models, A: (0x L)* - θ an online learner and S: (9 C)* x x + L strategy for picking loss functions in different rounds of online learning (adversarial environment in the context of online convex optimization). We use Regret(A, A, S,T) denote the regret of against S, in T rounds. Namely,
T
T
Regret = Σ 440,) min Σ (()
OEE
1=0
j=0
where
0, =
and 1, =
With the online learning problem set up, we proceed to the main proof which first describes Algo- rithm in the FTL framework.
Proof of Theorem 4.7 The FTL framework proceeds by solving all the functions incurred during the
previous online optimization steps, namely, AFTL ((0,((())))) (0,,4)) arg mingge 4()
13

---

Under review as a conference paper at ICLR 2021
Next, describe how design the ith loss function I, in each round of the online optimization. For the first choice, AFTL chooses a random model 8g E @ In the first round (round 0), Sø, uses the clean training set Dr and the loss is set
SØ, (0o) lo(0) L(, D.) + N CR R(O).
According to the FTL framework, AFTL returns model that minimizes the loss on the clean training set DD using the structural empirical risk minimization. For the subsequent iterations (i 2 1), the loss functions is defined as, given the latest model 0,, Sa, first finds (27, M() that maximizes the loss difference between 0, and target model 0g. Namely,
(x) v() = arg max 1(0;; 2) 1[0p: x. v)
(a.9)
and then chooses the ith loss function as follows:
So, ((6v. lo).................. (6 (61-1.4-1)) 0.) = ((0) = (0;22,00) + CR R(0).
Now will how FTL framework behaves when working these loss functions at different iterations. We use D to denote the set (Ir,,"))... (27, v()) We have
8;- -AFTL((OU, (0), lo)..... (0.1,,1)))))) arg min
Σ (0)
Bce
j=0
arg min L(): + N. CR R(O)
(0;=7,11) + Cn R(0)
arg min L(0; D. U D 1) + (N + 1) Cn R(0)
dEG
arg min
D(0:D.UD Cn R(0)
DD. DDDDD
AEe
This means that AFTL algorithm, at each step, trains new model over the combination of clean data and poison data so far (i - 1 number of poisons). Now we want to see what is the transla- tion of the Regret( AFTL, So T). If we can prove an upper bound on regret, namely if we show Regret(AFTL. So T) I (TT) for some function then we have
T Σ 40,) 1=0
T Σ (0ep) $ 1=0
T
T min > ((0) S a()) 8EB j=0
~E400
1=0
which implies
T
T Σ LO: L(0,; D.) + +N CR (B(0) - R(0,))
Σ ((0,))
L(0:;
1=0
1=0
4(00) Σ 1(00))
L(O.D.) L(0,; De) + N Cn (R(0.) - R(O,))
max (1(0,iz,)) v) 1(0p; v)) + CR (R(0,) -R(0,))
1=1
<T(
14

---

Under review as a conference paper at ICLR 2021
Therefore have
Σ
max (1(0)iz,)) ((0p:z,8)) + CR (R(0,) R(O,))) S <T( L(pp: D.) L()c:D.)
a.y
+N CR (R((p) R(Oe))
Based on Lemma
A.2
we further have
T
max (0,;;, 1(0p; S aT)) + L(,; D.) Do),
+ Cn (R(O,) R((O))
Above inequality states that average of the maximum loss difference in all previous rounds is bounded from above. Therefore, we know that among the 7 iterations, there exist an iteration jr E [T]] (with lowest maximum loss difference) such that the maximum loss difference of fg. is c-close to 6p with respect to the loss-based distance where
a(T) + L(0 D.) L(Gci D2) + Cn (R(0,) R(O,))
T
Theorem characterizes the dependencies of on (T)) and the constant term L(,p D.) L(o:: De) N Cn (R(0p) - R(O+)). To show the convergence of Algorithm | ensure 0 when T - +oc, which implies need to show a(T) O(VT). Following remark (restating Remark [ in Section 4.2) and its proof shows the desired convergence.
we need to
Remark 1 Online learning algorithmms with sublinear regret bound can be applied show the convergence. Here, we adopt the regret analysis from McMahan (2017). Specifically, a(T) is in the order of Ollog T)) and we have S O log
T when the loss function is Lipschitz continuous and the regularizer R(0) strongly convex, and e 0 when T +oo. (TT) is also in the order of O(log 7') when the loss function used for training is strongly convex and the regularizer is convex.
Our FTL framework formulation can utilize the existing logarithmic regret bound of adaptive FTL algorithm when the objective functions are strongly convex with respect to some norm ||. as illustrated in Section 3.6 McMahan (2017). For clarity in presentation, we first restate their related results below.
Setting (Setting in McMahan (2017). Given a sequence of objective loss functions f1, .... f: and a sequence of incremental regularization functions To, Tly Ti we consider an algorithm that selects the response point based on
0 arg min (f) BERd
0 1+1 arg min
Σ (0)++ + ro(O), for 2,... j=1
BER
We simplify the summation notation with (0) (0). Assume that T4 is a convex and satisfy rz(0) 2 0 for E 20,1,2,...} against sequence of convex loss functions f; Rdd + R U {oo}. Further, letting hoss russ + fi. we assume dom has is non-empty. Recalling 0: arg ming (f)) we further assume (..) is non-empty. We denote the dual norm of a norm as ||.-
Theorem A.3 (Restatement of Theorem in McMahan (017)). Consider Setting 7 and suppose
the Tı are chosen such that ros + f is I-strongly-conver w.r.l. some norm ll)) we define the regret of the algorithm with respect to selected point 0* as
T
T
Regret, (f) = Σ f((O.) Σ f((0)).
15

---

Under review as a conference paper at ICLR 2021
Then, for any 0 Rd and for any T >> O, with 9s Of((0.). we have
Regret, (0', .1) S SO.T-1
Corollary A.3.1 (Formalization of FTL result in Section 3.6 in McMahan (2017). In the FTL frumework (no individual regularizer is used in the optimization procedure), suppose each loss function fo is 1 I-strongly convex w.r.t a norm
then we have
1 T
G² - 2
Regret, (f) -
(1 logT)
2
with 1gill- S G.
Proof. The following proof is a restatement of the proof in Section 3.6 in McMahan (017)) The proof follows from Theorem A.3 Since we considering the FTL framework, let r;(() 0 for all
i and define [0]|)) 0 Observe that how (i.e., fi:)) is I-strongly convex with respect to | a
(Lemma 3 in McMahan 2017) and we have ||0) (s), J [10||. Then by applying Theorem A.3
we have
Regret, (0" fi) S
19 i
Σ
1
Based on the inequality of 2i=1 ET= 1/i < + log T and if we further assume l|g: S G, then can have
G (1+ + To
|9:1 13
2
Proof of Remark] [ We will prove the logarithmic regret bound in Remark [utiliiiii Corollary A.3.1
First of all, our online learning process fits into Setting I Specifically, we set (0) = 0 for all z.
For (0), when 1 < iss N, we set f:( \ (0: D.) + Cr R(0) (evenly distributing the term L(O; D.) + N CR R(0) across N iterations) and when 2 +1 we set (0) = 4,- (o)) Details l, can be referred from the proof Theorem 4.] Therefore, St is I-strongly convex with respect to norm (the norm is determined by the regularizer R(0) and Cr)). Further, (0.(0)
fi.
In addition, the assumption that dom ho: is non-empty in Setting [ meaans when we train a classifier on the poisoned data set, assumption of the existence of subgradient 0f,(0, in Setting is also satisfied by the poisoning attack scenario.
always return model and hence the assumption is satisfied. The
The logarithmic regret of Regret St, T) of our algorithm then follows from the result of Regret, f.) in Corollary A.3.I Specifically, (f) (f) is 1-strongly convex norm || || VN + ēll and since assume the loss function is G-Lipschitz, have [|gi||- S G. Therefore, we have the logarithmic regret bound as:
G² |1: S (1+log 7) S Olog T).
Regret(AFTL, T) 5 aT)
9:
i
2
We next provide the proof of the certified lower bound (restating Theorem 4.2 from Section 4.3
16

---

Under review as a conference paper at ICLR 2021
Theorem 4.2
Given target classifier 8g. reproduce By by adding the poisoning set Dp into De.
the number of poisoning points (Dpl cannot be lower than
sup 2(0) L(0p; D.) L(0; NC R(O))
suPx,y (1(0;z,)) x, - 1[0p; x, v)) + (R() R(0,))
The main intuition behind the theorem is, when the the number of poisoning points added to the clean training set is lower than the certified lower bound, for structural empirical risk minimization problem (shown equation in in the main paper), then target classifier will always have higher loss than another classifier and hence cannot be achieved.
Proof. We first show that for all models 0, we can derive a lower bound on the number of poison points required to get dg. Then since these lower bounds all hold, take the maximum all of them and get valid lower bound. We first show that for any model 6, the minimum number of poisoning points cannot be lower than
D.) L() NC -(())
(0) SuPr.y (1(0; x. 100p; 2), Cn R(Op))
Let us denote the point corresponding to the supremum of the loss difference between 0 and fp as (a" .yy)) Namely, ((0; x0, y²) 1(0p;=", ",; y²) = supz.y (1(0; x, y) I(pp; p; 3)). Now suppose we can obtain Op with lower number of poisoning points < =00). Assume there is a poisoning set Dp
with size such that when added to De would result 8p. We have
1
sup (1(0; x, v) 1(0ps x)) 2 DD. 2.y
L(0:D.U,))
D. DDD
CR (R(0p) R(0)).
0. Based the assumption that 1 x0), and the fact that sup,., (1(0; x, v) 1(0p;,,))) + Cr (R((0) - R(0,)) > O, we have
implying suP (1(0; x, y) 1(0g; Cn CR. (R(0) - R(O,)) (((,))
2 (1(0;2', "100;"",'>> 3²) - =0"
- R((,)))
< =0) = [Opp; D.) - L(O, + (C((( - R(()).
where the equality is based on the definition of =0)). On the other hand, by definition of (x", (x","") for any Dp of size 2, we have
L(0; D,) L(Op) Dp) Dp) + + (CR R(0) - Cr R(O,)) 2 (I(0) x² .y") 1(0p: x"; ,3²) ) Cn(R(O) R(O,))).
The above two inequalities imply that for any set Dp with size we have
1
D.UD, L( + OR R(0) D. D, L L0p:: D. DD, CR R(0p).
which indicates that adding D, poisoning points into the training set De., the model 0 has lower loss compared to 6p. which is contradiction to the assumption that 0p has lowest loss on D. U DD and can be achieved. Now, since Op needs to have lower loss D. J D, compared to any classifier E θ, the best lower bound is the supremum over all models the model space θ
Corollary 4.2.1 If we further assume bi-directional closeness in the loss-based distance, we can also derive the lower bound on number of poisoning points needed to induce models that are e-close the target model. More precisely, if 0r being c-close to 02 implies that 02 is also k close to 01. then we have,
- R - NKe
sup z' 2')
supa.y ((0:: 3) + +CR R + Ke
where R' is an upper bound the nonnegative regularizer R(0).
II practice, the data space X' is closed convex set and hence, can find (a. "n",v") using convex optimization. In other words, as in experiments, calculating the lower bound possible in practical scenarios.
17

---

Under review as a conference paper at ICLR 2021
Proof of Corollary 4.2.1. The lower bound for all e-close models to the target classifier is given
exactly as follows:
sup x(0,0) = L(d';D.) L() supa.y -0) =1.0==,,)))))) + Cn(R(0) - R(0))
R(0))
inf
10' -
where jnf -ypl'-
denotes 0' is 6-close to 0g in the loss-based distance. However, the formulation above is a min-max optimization problem and hard to analytically compute the lower bound (by plugging the lower bound formula into Algorithm[[] Therefore, we need make several relaxations such that the lower bound is computable. For any model 6' that is c-close pp. based on the bi-directional assumption, then Op is ke-close to 0', Therefore we have,
T.(0'; D.) (.,)-L((0;D.)) = T.(0"; - P.) D.) -Nke -()::
and
22, sup (1(0:z,)) - 1(0" I. v)) sup (1(O: z, y) 1(0p, 2,1)) + sup (1(0p) x. x, v) 1(0';)
a.y
S sup (1(0: x. v) 1(0p, v, y) + ke
and the inequalities are all based on the definition 0p being ke-close to 8'.
Plugging the above inequalities into the formula of supo, or for model 8', and with the assumption that 0 & R(0)= & R", v0 E O, we immediately have
L(Op: L(; - c (C(((((6) R(0))
sup 2(0, 0' 2 sup & supz,, x, (1(0) 20, 1(0p; ((0,: he CR (R(() R(A'))
L(0p; - L(0
Nke NCR R²
2' (0)
sup
suPx,y ((00;,,,)) -
- Ke + Cr R-
Since the inequality holds for any 0', we have
inf
sup (0, 2 sup (0)
6 9 D se
and hence z' 2'(0) is valid lower bound.
Remark 2 (Improving Results in Corollary 4.2.11. Assuming 0 S R(0) I R' is not a strong assumption and actually can be satisfied by many common convex models. For example, for SVM model with Ez-regularizer (in fact, applies to any regularizer R((0) with R(0) = 0), we have R(0) S Ca and hence R < Cn. Moreover, we can further tighten the lower bound by better bounding the term R(8') ((()). Specifically, R(8') R(Ø) R(8') R(0,) (((0p) R(0) and we only need to have tighter upper and lower bounds on R(6') R(Op) utilizing some special properties of the loss functions. For the constant in the bi-directional closeness, we can also compute its value for some specific loss functions. For example, for Hinge loss, we can compute the value based on Corollary B.2. in Appendix B
B RELATING CLOSENESS OF LOSS-BASED DISTANCE TO CLOSENESS OF PARAMETERS
In theorem below, show how relate the notion of e-closeness in Definition in the main paper to closeness of parameters in the specific setting of hinge loss. We use this just as an example to show that our notion of e-closeness can be tightly related to the closeness of the models.
18

---

Under review as a conference paper at ICLR 2021
Theorem B.1. Consider the hinge loss function I(0; x.y) max(1 -y y. (I, 0) r 0 E R and I E R and y E [-1,+1]. For 8, 8' E R such that ||0||1 S r and 1 $ r. if 0 is c-close to A in the loss-based distance, then, ||0 8111 r.
Remark 3. In Theorem B. above with Ez-regularizer, an upper bound on the &-norm of 0 and O' is vd/Cn. however, the models that we care about in practice usually have smaller norms.
Remark can be obtained by plugging O E IR and compare the resulting (regularized) optimization loss the model 0* that minimizes the model loss.
Proof of Theorem
B.7
We construct a point x: as follows:
0; > 0 E [d]
x
if 0, S 8, i E [d]
Then have
( 2²) = 110 11
(3)
Since ||0]] Σ r we have
(x 2 -1
(4)
and similarly since |10'|1 & r we have
00'0'' 2 1.
(5)
Therefore by Inequalities equation 4 and equation 5 we have
I(0: x -1 1(6'; x -) max(1 + (z) 0) max(1 + (0",6")00 0) (0- f ,0'x,))
which by equation 3 implies
10; 1) 1000; = 110 110- 0'
Now since know that, Vr Rd, the loss difference between @ and 0' is bounded by the bound should also hold for the point -1). meaning that
1 110 0'111 Se
which completes the proof.
Theorem B.2. Consider the hinge loss function 1(0; xr y) = max(1 - y (I. (),00) for 0 E Rd and I2d and y E {[1, +1}. For X {0 Rd: || 1 S 9} and y = [11, For any two models 0, 0 0 0' 1| e, then q e-close to 0' in the loss-based distance. Namely,
Di 8¹) S ..
Proof. For any given 0 and 0', by triangle inequality for maximum, we have
1(0;x, y) - 1(6' v) = max(1 y 0).0) max(1 y (z,0'),0) s max(0, (yz, 0 - -0))
Therefore, we have
1(0: x, y) - 1(0 1z. 1(0':(.v)) xx)
max max(O, (yr, o' - -A)). (xx))xxx)
max
Our goal is then to obtain an upper bound of O(e) for (xy,, 0' - 0) when 110-0' 00 || Se. e.
To maximize (yz, o' - 0) by choosing and y, only need ensure that sign ye, sigu 0,, i [d] Therefore, based on the assumption that + || < 1 (f.e..)(a)) lay < 1, E [d] we have
(yr, 0 0)
0/1 S
Σ
10:
011
1
o 0115
(x.))EXY)) q
which concludes the proof.
Corollary B.2.1. For Hinge loss, with Theorem B.1 and Theorem r. q e-close to 0.
B.2 if c-close to 9', then o' is
19

---

Under review as a conference paper at ICLR 2021
C INSTANTIATING THEOREM 4.1 FOR THE CASE OF SVM
Here we show how to instantiate Theorem 4.1 for SVM with exact constants instead of the asymptotic notations. We need to calculate the constant ?y to get the exact constant. Imagine the feature domain is IR Now we calculate the constant C' as follows. Let 1 = arg min [0 and Og [ /0pp/t Let s. Rd be point where is equal to 0 everywhere and is equal to 1/0 on the i" coordinate. We have,
1(0, zg. +1) 1(0p 2g. 1(0, xg. +1) 2 (1 aa).
Now we can calculate C' as follows
C=
inf dEF
sup(((0;a, -((p)))))((0;))))))1)1)) ([0piz,,)) R(OO)
st. ((0,)>R(0))
a.y
inf REF s1 R(0,)>
(1(0, zgg +1) (0):: - R(O))
- 0pg
(By Inequality 7
IV IV
inf AEF
sup
2.l R(Op) R(0)
a1. R(0,)>=(())
00
(By definition of og)
inf BEF R(B
R(Op) ag)
009 R(0,)) a
inf OEP st. R()))>R(0))
2R(0p)
Therefore 1 1 form given in the proof of Theorem
2- Cr R(Op)). On the other hand, we also calculate ((T) based the exact
D INDISCRIMINATE SETTING EXPERIMENTS
In this section, we evaluate the attacks the conventional indiscriminate attack setting, where the attacker's goal is just reduce the overall accuracy of the model.
Datasets and Models. For the indiscriminate attack, we use the MNIST 1-7 dataset, which consists of the digits and and is commonly used for evaluating indiscriminate poisoning attacks against binary classification (Steinhardt et al.] [017]] [Bigiio et al., 2012 Xiao et al. 2012). MNIST 1-7 contains 13,007 training and 2,163 test samples. The dataset contains 784 features and all the features are normalized into range [o, 1]. For completeness, the Adult dataset used for subpopulation attack is downsampled form blasneal dataset and contains 15682 training data and 7692 test data. The dataset contains 57 features and the features are also normalized into range [0, 1] (except for the binary features). All of the processed datasets are included in the supplementary material. We still adopt linear SVM model in the indiscriminate attack scenario. All of the models for both datasets set the regularization parameter CR = 0.09. The clean accuracy of SVM model on MNIST 1-7 is 98.9% and the accuracy Adult dataset is 78.5%.
Target Classifiers. Accuracy of the clean MNIST 1-7 model has around 1% error rate on the test set. For our experiment, we aim to generate three target classifiers with overall test errors around 5%, 10% and 15%. To generate target classifiers with desired error rates, we follow the heuristic strategy proposed by Koh et al. (2018) to generate multiple candidate target classifiers, and then among all the valid candidate models that satisfy the error rate requirement we choose the one with lowest loss on the clean training set. Using this approach, the final target classifiers induced have overall test accuracy of 94.0%, 88.8% and 83.3% respectively. (We describe better way of finding the target classifiers in Appendix D.I but for comparison purposes do not use those in the results here.)
20

---

Under review as a conference paper at ICLR 2021
Our Allack KKT Attack
1.75
Our Attack
Max Lods D:d
10
Euclidean Distance
1.50
KKT Attack
0.25
1.00
6
0.5
0.50
2
0.25
4000
1000
2000
(a) Max Loss Difference to Target
(b) Euclidean Distance Target
Figure 3: Attack convergence (results shown are for the target classifier of error rate 10%). The maximum number of poisons is set using the 0.1-close threshold target classifier
1.0
Teel Agc
0.0
Our Allack
02
Our Alback
022
KKT Allack
KKT Allack
KKT Allack
2000
Poisons
Num Poisons
Paisons
(a) 5% Error Rate
(b) 10% Error Rate
(c) 15% Error Rate
Figure 4: Test accuracy for each target model of given error rate with classifiers induced by poisoning points obtained from attack and the KKT attack.
Convergence. We show the convergence of Algorithm by reporting the maximum loss difference and Euclidean distance between the classifier induced by the attack and the target classifier. Figures Ba and 3bb summarize the results for the target classifier with 10% error rate. The maximum number of poisoning points in the figure is obtained when the classifier from Algorithm iis 0.1-close to the target classifier the loss loss-based based distance. In Figure 3 the classifier induced by our algorithm steadily converges to the target classifier both in the maximum loss difference and Euclidean distance, while the classifier induced by the KKT attack diverges initially and then starts to converge to the target model. At the maximum number of points, the maximum loss difference of KKT-innuced classifier the target is 0.46, compared to 0.1 for the classifier induced by our attack. For the Euclidean distance, the KKT-induced classifier is 0.16 away, compared to 0.07 for the classifier induced by our attack.
Attack Success. We next compare the classifier induced from our attack to the classifier induced by the KKT attack in terms of their overall test accuracy. Similarly, the maximum number of poisoning points in Figure 4 obtained by rumning our attack with 0.1-closeness (in loss-based distance) to the target as the input. In terms of the test accuracy, our attack has comparable attack success rate compared to the KKT attack. Specifically, for target models of 5% and 10% error rates, both methods have almost identical performance, as shown in Figures 4a and 4b For the target model of 15% error rate (test accuracy is 83.3%), the KKT attack is more successful than our attack, inducing models with 82.7% accuracy (17.3% attack success rate) compared to 85.9% accuracy (14. 14.1% 1% attack success rate) for our attack. Interestingly, in this case, the performance of models induced by the two attacks with fewer poisoning points our attack results models with lower test accuracy (higher attacker success) than the KKT attack. To summarize, for the indiscriminate scenario. attack produces classifiers that have much closer distance to the target models than the KKT attack, and has comparable attack success rates with the KKT attack.
Lower Bound on Number of Poisons. We next check the optimality our attack in the indiscrimi- nate attack scenario. Similar the subpopulation attack setting, still use Theorem to compute the lower bound of the induced classifier from our attack by using it as the input to Algorithm and terminating when the induced classifier is 0. 1.1-olose the given target model. In Table
21

---

Under review as a conference paper at ICLR 2021
5% Error
10% Error
15% Error
# of Poisons 1737
5458
6192
Lower Bound
874
3850.4 + 0.8
4904
Table 2: Poisoning points needed to achieve target classifiers induced from our attack. Top row means number of poisoning points used by our attack. Bottom row means the lower bound computed from Theorem 4.2 for the target classífiers. All results are averaged over four runs. integral value in cell means we get exactly that same value for all four runs; for the one cell where we observe variation, we report the average and standard error.
Computent Lewerr
Computen
8
Computeri
Num of Poisons
1007
183
Num
200
2017 Num Poisons
1000
(a) 5% Error Ratc
5% Error Rate
(c) 15% Error Rate
Figure 5: Lower bound computed in each iteration of running algorithm I when the target classifier of the algorithm the classifier induced from our Attack (classifier in Table 2 The maximum number of poisons is set using the 0. 1-lloe threshold to classifier induced from attack.
5% Error
10% Error
15% Error
of Poisons
1737
5458 4058.4+1.4
6192
Lower Bound
856
5031.4+4.8
Table 3: Poisoning points needed to achieve target classifiers induced from the KKT attack. Top row means number of poisoning points used by the KKT attack. Bottom row means the lower bound computed from Theorem 4.2 for the target classifiers. All results averaged over runs, integer value in the cell means we get exactly same value for 4 runs and others are shown with the average and standard error.
Dount
20xc
x
Conputed 1
Computed
Computed
100
Num of Poisons
Num of Poisons
Num Potsons
(a) 5% Error Rate
(b) 5% Error Rate
(c) 15% Error Rate
Figure 6: Lower bound computed in each iteration of running algorithm | when the target classifier of the algorithm is the classifier induced from the KKT Attack (classifier in Table The maximum number of poisons is set using the 0. 1-clol threshold to KKT induced classifier.
calculated lower bound shows that there exists relatively large gap between the number of poisoning points, especially for the induced classifier from our attack for the target model of 5% error rate, where the lower bound is only 50% of the actual number of poisoning points used. For the induced classifier for the target model of 15% emror rate, the gap between the number of poisoning points and the lower bound is smallest, with the lower bound taking 79% of the number of poisoning points.
22

---

Under review as a conference paper at ICLR 2021
Test Acc (%)
Loss on Clean Set Improved
# of Poisons
Target Models
Original
Improved
Original
Original
Improved
5% Error
94.0
94.9
2254.6
1767.1
2170
1340
10% Error
88.8
88.9
4941.0
3233.1
5810
2432
15% Error
83.3
84.5
5428.4
4641.6
6762
3206
Table Comparison two target generation methods on number of poisoning points used to reach 0. 1.l--loseeess to the target. Original indicates the original target generation process from Koh et al. (2018). Improved denotes our improved target generation process with adaptive model updating.
1.0
1.0
0.4
0.
0.4
Test
Test
Our Attack KKT Attack
Our Attack
82
Our Attack
KKT Attack
KKT Attack
1500
1000 2000
to00
5000
0.0
1000
2000
3000 4000 5000 6000
(a) 5% Error Rate
(b) 10% Error Rate
15% Error Rate
Figure 7: Test accuracy with classifiers obtained from our attack and KKT attack. Target model for KKT attack is generated from the original generation process and target model for attack is generated from the improved generation process. Maximum number of poisoning points is obtained by running our attack with target model generated from the original process and resultant classifier is 0. 0-1-cl to the target.
The relatively large gap indicates that either the estimated lower bound is not tight or the attack itself not close to optimal. To gain more insights into this problem, we further show the computed lower bound at each iteration when running Algorithm and Figure summarrzzss the results. From the Figure, we see that, the peak value the curve (i.c., highest lower bound) always appears before the termination of the algorithm, indicating that the computed lower bound is likely to be tight and may need to further improve the attack algorithm.
For completeness, also repeat the lower bound computation process for classifiers induced from the KKT attack. The KKT induced classifiers are obtained by running the KKT attack with target classifiers of different is given by the size of poisoning set returned from our attack when our algorithm terminates when the induced classifier 0.1-close the target model of different error rates. Then the lower bound computation process is identical to the above we simply send the KKT induced classifier as target input Algorithm] [ and terminate when the induced classifier from our algorithm 0. 0-1-elose to the given target model (i.e., KKT induced classifier). The results are summarized in Table 3 and we observe that there also exists a relatively large gap between the lower bound and the number of poisoning points used by the attack. Similarly, we also plot the lower bound computed at different iterations of Algorithm| inn Figure 0 and find that the peak value also appears before the termination of the algorithm, indicating that the lower bound might be tight and need stronger attack strategy to close the gap.
target input. The target number of poisoning points of KKT attack
D.1 IMPROVED TARGET GENERATION PROCESS
The original heuristic approach works by finding different quantiles of training points that have higher loss on the clean model, flipping their labels, repeating those points for multiple copies, and adding them to the clean training set. We find that, in the process of trying different quantiles and copies of high loss points, if we also adaptively update the model where the high loss points are found (instead of just always fixing it to be the clean model). loss on the clean training. Such an improved generation process can significantly reduce the number of poisoning points needed to reach the same e-closeness (with respect the loss-based distance)
can generate valid target classifier with even lower
23

---

Under review as a conference paper at ICLR 2021
to the target classifier, consistent with the claims in Theorem 4.1 in the main paper. In addition, find that, if we compare our attack with improved generation process to the KKT attack with the original generation process (Koh et al., 2018), we can also reach the desired target error rate much faster using our attack.
Implication of Theorem 4.1 We first empirically validate the implication of Theorem 4.1 in the main paper: to obtain the same c-closeness in coss-based distance, a target classifier with lower loss on the clean training set D, requires fewer poisoning points. Therefore, when adversaries have multiple target classifiers that satisfy the attack goal, the one with lower loss on clean training set is preferred.
For both the original and improved target generation methods, we generate three target classifiers with error rates of 5%, 10% and 15%. The original target classifier generation method returns classifiers with test accuracy of 94.0%, 88.8% and 82.3% respectively (also used in the previous experiments of indiscriminate attack). The improved target generation process returns target classifiers with approximately the same test accuracy (94.9%, 88.9% and 84.5%). However, for classifiers returned from the two generation methods of same eπror rate, the improved generation method produces classifiers with significantly lower loss compared to the original generation approach.
Table 4 compares the two target generation approaches by showing the number of poisoning points needed to get 0. 1-lllo to the corresponding target model of same error rate. For example, for target models of 15% error rate, the model from the original approach has total clean loss of 5428.4 while our improved method reduces it to 4641.6. With the reduced clean loss, getting 0.1-close to the target model generated from our improved process only requires 3206 poisoning points, while reaching the same distance from the target model produced by the original method would require 6762 poisoning points, more than 50% reduction.
End-to-End Comparison. Figure compares the two attacks in an end-to-end manner in terms of their test accuracy. With the improved target generation process, our attack can achieve the desired error rate much faster than the KKT attack with the original process. For the KKT attack with target model generated from the original process, we determine the target number of poisoning points using the size of poisoning set returned from running Algorithm | with 0.1-closeness and target model from original process inputs. To run our attack with improved generation process, we terminate the algorithm when the size of the poisoning points is same as the number of poisoning points used by the KKT attack with original process. Such a termination criteria helps us to ensure that both attacks use same number of poisoning points and can be compared easily. We also evaluate the KKT attack on fractions of the maximum target number of poisoning points (0.2, 0.4, 0.6, and 0.8), as in the previous experiments. The accuracy plot shows that our attack (with improved target model) can achieve the desired error rate (e.g.. 10%) much faster than the KKT attack (with original target model), especially for the target classifiers of error rates of 10% and 15%.
E COMPARISON OF MODEL-TARGETTE AND OBJECTIVE- -DRIVEN ATTACKS
Although model-targeted attacks work to induce the given target classifiers by generating poisoning points, the end goal is still to achieve the attacker objectives encoded in the target models. In terms of attacks
the comparison to the objective-driven attacks, we first demonstrate that, objective-drive can be used to generate a target model, which can then be used as the target for a model-targeted attack, resulting in an attack that achieves the desired attacker objective with fewer poisoning points. Then, we show that in order to have competitive performance against state-of- the-hhh-rtt objective-driven attacks (e.g.. the min-max attack (Steinhardt et al., 2017)), the target classifiers should be generated carefully, such that the attacker objectives of the target classifiers can be achieved efficiently with model-targeted attacks using fewer poisoning points. Although the investigation of a systematic approach to generate such "desired" classifiers is out of the scope of this paper, in the indiscriminate setting, we have some empirical evidence. Specifically, we find that target classifiers with lower loss on clean training set and higher error rates (higher than what are desired in the attacker objectives) often require fewer poisoning points to achieve the attacker objectives. The following experiments are conducted on the MNIST 1-7 dataset.
Target Models Generated from Objective-drieen Label-Flipping Attacks. In our experiments, the target classifiers are generated from the label flipping based objective driven attacks that
24

---

Under review as a conference paper at ICLR 2021
effective but need too many poisoning points achieve their objective. Then, our attacks are deployed to achieve the same objective with fewer poisoning points. Table the number of poisoning points used by the label-flipping attack and model-targeted attack, to achieve desired attack objectives of increasing the test error to certain amount. We can see that, using our attack, the number of poisoning points used by lahel-flipping attacks can be saved up to 73%.
Comparison to the Min-Max Attack. Still using target classifiers generated from flipping attacks, we show that attack can outperform the state-of-ther arr min-max attack (Steinhardt et al., 2017) at reducing the overall test accuracy, under same amount of poisoning points. Since we aim to produce target classifiers with lower loss on clean training set and higher error rates, we adopt the improved target model generation process described in Section D.I (helps to reduce the loss on clean training set) and generate classifier of 15% error rate. With the target model, we terminate our attack when the induced model is 0.1-close to the target model in terms of the loss-based distance. However, to we compare our attack to the min-max attack conveniently, we compare their accuracy reduction at different poisoning ratios (i.e., 5%, 15% and 30%), which is the common evaluation strategy of objective-driven attacks in the indiscriminate setting (Biggio et al., 2011] Steinhardt et al. 2017 Koh et al. 2018). Table Jummmrrze the results. From the table, we observe that, compared to the min-max attack, our attack reduces more on the test accuracy under the same poisoning budget and the gap becomes larger when the poisoning ratio increases.
Comparison to the Label-Flipping Subpopulation Attack. We also compare our attack to the label-flippigg subpopulation attack from Jagielski et al. 2019). This attack works by randomly sampling fixed number (constrained by the poisoning budget) of instances from the training data of the subpopulation, flipping their labels and then injecting them into to the original training set. Although this attack is very simple, it shows relatively high attack success when the goal is to cause misclassification the selected subpopulation (Jagielski et al. 2019).
To be consistent with our experiments in Section 5 we assume the attacker objectives are still to induce model that has 0% accuracy on selected subpopulation. For each of the SVM and logistic regression models, we selected the three subpopulations with highest test accuracy (all end up having have 100% accuracy). In indiscriminate setting, we already observed that models with lower loss on clean training set and larger overall eтror rates can achieve attacker objectives of smaller error rates faster. However, to leverage this observation into our subpopulation experiments, one challenge is the attacker objective is to have 100% test error on the subpopulation, but no classifiers can have test errors larger than 100%. To tackle this, we select models with larger loss on training samples from the subpopulation, with a hope that this process is "equivalent" to selecting target models with larger error rates (on subpopulation) than 100%. To this end, we heuristically select targeted models that satisfy the attacker objective, have larger loss on the training data from the subpopulation, and have relatively low loss on the entire clean training set. Empirically, this selection strategy works better than the original target generation process (as done in Section (5) in achieving the attacker objectives. A more detailed and systematic investigation of the target model search process is left as the future work.
To check the effectiveness of achieving the attacker objectives, we first run our attack and terminate when our attack achieves the attacker objective to have 0% accuracy on the selected subpopulation, and record the number of poisoning points used. Then, we run the random label-flipping attack with the same number of poisoning points. For both attacks, we report the final test accuracies of the resulting models on the subpopulations.
Attacker Objectives
5% Error
10% Error
15% Error
Label-fliping Attack
6,510
8,648
10,825
Our Attack
1,737
5,458
6,192
Table 5: Generate target classifiers using objective-driven label-flipingg attacks and achieve similar attacker objectives using attack with fewer poisoning points. The attacker objectives are to increase the test error to certain amounts (i.c., 5%, 10% and 15%) and the target classifiers to our attack are generated by running the label-ftippigg attacks with given attacker objectives.
25

---

Under review as a conference paper at ICLR 2021
Poisoning Ratio
5%
15%
30%
Min-max Attack
97.0%
93.9%
92.9%
Our Attack
96.2%
88.6%
85.0%*
Table 6: Comparison of our attack to the min-max attack with different poisoning ratios. The target model of our attack is of 15% error rate. The poisoning ratio is with respect the full training set size of 3,,07. Each cell in the table denotes the test accuracy of the classifier after poisoning. The clean test accuracy is 98.9% Our attack at 30% poisoning ratio is marked with "*" because the attack terminates when the induced model is 0.1-close to the target model, which only uses 2,894 poisoning points and less than the 30% ratio.
SVM
Logistic Regression
Cluster 0 Cluster
Cluster 2
Cluster Cluster 1
Cluster 2
Our Attack 0%
0%
0%
0%
0%
0%
Label-Fipping
31.4%
2.8%
15.5%
15.9%
14.0%
19.1% %
Table 7: Comparison of our attack to the label-flippngg based subpopulation attack. The table com-
pares the test accuracy on subpoplation of Adult dataset under same number of poisning points. The number of poisons are determined when attack achieves 0% test accuracy the subpopulation. Cluster 0-3 in the logistic regression and SVM models denote different clusters. For logistic regres- sion, number of poisoning points for Cluster 0-3 are 1,575, 1,336 and 1,649 respectively. For SVM, number of poisoning points for Cluster 0-3 are 1 1,252, 1,268 and 1,179 respectively.
The attack comparisons on different subpopulation clusters and models are given in Table 7 Results in the table compare our attack and the -iipppiip attack over the three distinct subpopulation clusters for the SVM and logistic regression models. Across all settings, our attack is considerably more successful. The number of poisoning points needed to reach the 0% accuracy goal is small compared to the entire training set size (e.g., the maximum poisoning ratio is only 10.5%) The gap between our attack and the label-flipping attack is fairly small. For example, for Cluster 1 in the SVM experiment, the label-flipping attack is also quite successful and reduces the test accuracy to 2.8% (our attack achieves 0% accuracy). We believe the success of sabel-flippin attack due to the following two reasons. First, label-flipingg in the subpopulation setting be successful because smaller subpopulations show some degree of locality and hence, injecting points (from the subpopulation) with flipped labels can have strong impact the selected subpopulation. This is confirmed by empirical evidence that increasing the subpopulation size (i.e., reducing its locality) gradually reduces the label-fiiping effectiveness and the attack becomes much less effective in the indiscriminate setting (i.e., subpopulation is the entire population). Second, the Adult dataset only contains 57 features, where of them are binary features with additional constraints. Therefore, the benefit from optimizing the feature values is less significant as the optimization search space of our attack is fairly limited.
F ADDITIONAL EXPERIMENTS
In this section, we provide the results of evaluating our attack and the KKT attack on SVM models for an additional dataset (Section F.T) and on logistic regression models for three datasets (Section F22)
The results here are consistent with our findings in on the datasets and models in Section but provide further evidence of the general effectiveness of our attack.
F.1 ATTACKS ON SVM TRAINED ON DOGFISH
In this section, we introduce the results of SVM model evaluated on the Dogfish dataset.
Dataset. The Dogfish dataset contains dog and fish images of dimensions 298 x 298 3. This dataset has been used as a binary classification task by by previous works in evaluating poisoning attacks in the indiscriminate setting (Koh & Liang 2017 Steinhardt et al. 2017 Koh et al. 2018).
26

---

Under review as a conference paper at ICLR 2021
0.36
17.5
Our Atlack KKT Attack
Our Allack
Euchidean Distance
0.30
KKT Attack
Loos Din
0.25
12.5
7,5
9.15
5.0
0.10
0.05
Num
Polisns
(a) Max Loss Difference Target
(b) Euclidean Distance Target
Figure 8: SVM on Dogfish dataset: attack convergence (results shown are for the target classifier of error rate 10%). The maximum number of poisons using the 2.0-close threshold to target classifier
0.8
Test A00
0.0
Teek Adc
0.
Test Apc
0.8
Our Allack
Our Allack
02
Allack
KKT Attack
KKT Attack
KKT Altack
Num of Poisons
Num Poisons
Num Poisons
(a) 10% Error Rate
(b) 20% Error Rate
(c) 30% Error Rate
Figure 9: SVM on Dogfish dataset: test accuracy of each target model of given error rate with classifiers induced by poisoning points obtained from attack and the KKT attack.
10% Error
20% Error
30% Error
Poisoning Points
32
89
169
Lower Bound
13
36
Table 8: SVM on Dogfish dataset: poisoning points needed to achieve target classifiers induced from our attack. Top row means number of poisoning points used by our attack. Bottom row means the lower bound computed from Theorem 4.2 for the induced classifiers.
To make classification easy for linear models, both Steinhardt et al. (211)) and Koh et al. (2018) use the extracted features (of the original images) from the ImageNet Inception model (Szegedy et 2016) and then apply linear models to complete the classification task. We also adopt the extracted features for classification, so each instance has 2,048 features. The Dogfish dataset has 1,800 training samples and 600 test samples. As in the previous work, we conduct conventional indiscriminate attack on it, where the adversary's goal is to reduce the overall test accuracy.
Target Classifiers. The clean accuracy of the SVM model on the Dogfish dataset is 98.5%. We generate target classifiers of overall test error rates around 10%, 20% and 30% using similar (heuristic) target generation process (Koh et al. 2018) as in the case of MNIST 1-7 dataset. The final test accuracies of the obtained target classifiers are 89.3%, 78.3% and 67.2% respectively.
Attack Results. The convergence of our attack is demonstrated in Figure both in the loss-based distance and the actual model distance f2-norm. The maximum number poisons for the experiments is obtained when the classifier from Algorithm is 2.0-close to the target classifier. Our attack steadily converges to the target model for both metrics, and has a faster convergence rate than found in other attack settings, as summarized in Figure 9
the KKT attack. Similar observations Our attack is slightly more successful than the KKT attack in all three target classifiers we tested. For the models induced from our attack, in Table we also show the gap between the number of
27

---

Under review as a conference paper at ICLR 2021
poisoning points of our attack and the theoretical lower bound. Although our attack can induce the target models using very few poisoning points (recall that the entire training set size is 1,800), there is still some gap to the theoretical lower bound. We also repeated the same process on the model induced from the KKT attack and again observe gaps between the number of poisoning points and the corresponding lower bound. These suggest that there is still potentially room for improvement in finding more efficient model-targeted poisoning attacks.
F.2 ATTACKS ON LOGISTIC REGRESSION
In this section, we evaluate our attack on the logistic regression models for the Adult, MNIST 1-7 and Dogfish datasets.
The convergence guarantee in the paper also holds for logistic regression model (more generally, holds for any Lipschitz and convex function with strongly convex regularizer). However, for logistic regression, may not be able efficiently search for the globally optimal point with maximum loss difference (Line iin Algorithm I because the difference of two logistic losses is not concave. Therefore, we adopt gradient descent strategy, using the Adam optimizer (Kingma & Ba 2014) to search for the point that (approximately) maximizes the loss difference. This is in contrast to the SVM model, where the difference of Hinge loss is piece-wise linear and we can deploy general (convex) solvers to search for the globally optimal point in each linear segment (Diamond & Boyd 2016 Inc 2020). However, as will be demonstrated next. poisoning points with approximate maximum loss difference can still be very effective. More formally, if the approximate maximum loss difference I found from local optimization techniques is within a constant factor from the globally optimal value I' (i.e., I 2 at", 0 < < 1), then still enjoy similar convergence guarantees. A similar issue of global optimality also applies to the KKT attack (Koh et 2018)) where the attack objective function longer convex for logistic regression models, and therefore, we also utilize gradient based technique to (approximately) solve the optimization problem. Since the maximum loss difference found for logistic regression models may not be the globally optimal value, in these experiments we did not compute the lower bound (Theorem 4.2) on number of poisoning points to induce the poisoned model from our attack, which requires obtaining the actual maximum loss difference
Target Classifiers. The clean accuracies of logistic regression models on the three datasets are 79.9% on Adult, 98.1% on MNIST 1-7 and 98.5% on Dogfish. Target classifiers for logistic regression models are generated similarly to their SVM counterpart on each dataset. For Adult dataset, the subpopulations are generated exactly the same as the SVM case and form total of 20 subpopulations, where instances in each subpopulation all belong to the "low-income" group. Among all the subpopulations, we select three with the highest test accuracy on the subpopulations and they all have 100% accuracy. The target classifiers are then generated to have 0% accuracy on the subpopulations using the target generation method described in Section 5 On the MNIST 1-7 dataset, target models generated to have around 5%, 10% and 15% overall test errors and final test accuracies of the obtained target models are 94.7%, 89.0% and 84.5%. For Dogfish, target models generated to have around 10%, 20% and 20% overall test errors and the final test accuracies of the resulting models are 89.0%, 79.5% and 67.3%.
Results on Adult. Figure T0 shows the effectiveness of our attack on logistic regression models trained on the Adult dataset, using the loss-based distance and the actual model distance in fo-norm. The maximum number of poisons for the experiments is obtained when the classifier from Algorithm 1 is 0.05-close to the target classifier. Our attack steadily converges to the target model while the KKT attack fails to have reliable convergence. Similar observations are also found in other attack settings, as shown in Figure II Our attack is much more successful than the KKT attack, especially for the attack on Cluster 1.
Results on MNIST 1-7. Figure 12 shows the convergance of our attack on LR models trained on the MNIST 1-7, The maximum number of poisons for the experiments is obtained when the classifier from Algorithm is 0.1-close to the target classifier. Our attack converges to the target model while
'I the lower bound computation, when the loss difference is not concave, we can use a concave upper bound for it to obtain valid lower bound and as long as the upper hound is relatively tight, the lower bound is still mcaningful.
28

---

Under review as a conference paper at ICLR 2021
Euclsdesa Distence
o.
1.0
0.
KKT Attack
Max
Our Attack Attock
0.0
250
500
750
1000 1250 1500 1750 2000
250
500
1030 1250 1500 1750 2000 Num of Possons
750
Num of Poisons
(a) Max Loss Difference to Target
(b) Euclidean Distance to Target
Figure 10: Logistic regression model on Adult dataset: attack convergence (results shown are for the first subpopulation, Cluster 0). The maximum number of poisons is set using the 0.05-close threshold target classifier.
1.0
Our Attack KKT Attock
Test Acc Suhpop
0.2
Test Agc on Subpoop
0.2
Ace on Suhpoop
0.8
0.4
0.4
Our Attack
Our Attack
KKY Atlack
550
1900 Nur of Poisons
1500
2000
1950
Maon
1000
1100
2500
Nom of Poisons
Num Poisons
(a) Cluster 0
(b) Cluster
(c) Cluster
Figure 11: Logistic regression model on Adult dataset: test accuracy for each subpopulation with classifiers induced by poisoning points obtained from our attack and the KKT attack.
Our A Allack
Max Lasz DRt
8
Euclsteen Distence
1.2
1.0
Our Attack
KKT Attack
560
Num of Poisons
Num of Poisons
(a) Max Loss Difference to Target
(b) Euclidean Distance to Target
Figure 12: Logistic regression model on MNIST 1-7 dataset: attack convergence (results shown are for the target classifier of error rate 10%). The maximum number of poisons set using the 0.1 0.1-close threshold to target classifier.
0.0
0.8
0.8
Toat Agc
0/1
0.2
0.2
022
KKT Altack
KKT Attack
KKT Allack
2000 Num of Poisons
Num of Poisons
Num of Poisons
(a) 5% Error Rate
(b) 10% Error Rate
(c) 15% Error Rate
Figure 13: Logistic regression model on MNIST 1-7 dataset: test accuracy each target model of given error rate with classifiers induced by poisoning points obtained from our attack and the KKT attack.
29

---

Under review as a conference paper at ICLR 2021
20
Euclideen Distance
0.
Max Loos Did
15
Our Attack Attack
Our Attack KKT Attack
02
Num
Pooisons
(a) Max Loss Difference to Target
Euclidean Distance Target
Figure 14: Logistic regression model on Dogfish dataset: attack convergence (results shown are for the target classifier of error rate 10%). The maximum number of poisons set using the 1.0-close threshold to target classifier
0.0
Test A00
0.8
Teat Ad6
0.2
Test Agc
0.8
Our Atlack
Our Allack
02
Our Allack
XKT Attack
KKT Attack
KKT Attack
Poisons
Num Poisons
Num Poisons
(a) 10% Error Rate
(b) 20% Error Rate
(c) 30% Error Rate
Figure 15: Logistic regression model on Dogfish dataset: test accuracy each target model of given error rate with classifiers induced by poisoning points obtained from our attack and the KKT attack.
the KKT attack diverges. Similar observations are also found for other attack settings, shown in these settings, our attack is much more successful than the KKT attack. fact, the KKT attack seems not find useful set of poisoning points as its induced models did not show significant drop from the clean accuracy of 98.1%. We suspect this is due to the highly non-convex nature of the attacker objective") when attacking logistic regression models. In contrast, attack only deals with maximizing the difference of two logistic losses, which is simpler than the KKT attacker objective, and results in successful attack.
Figure 13
Results on Dogfish. Figure 14 shows attack results of logistic regression models on the Dogfish dataset. The maximum number of poisons for the experiments is obtained when the classifier from Algorithm 1 is 1.0-close to the target classifier. Our attack converges to the target model while the KKT attack fails to converge. Attack success comparisons
given in Figure 15 As with MNIST 1-7, our attack succeeds in settings where the KKT attack does not lead to significant accuracy drops from the clean accuracy of 98.5%. We believe this also because of the highly non-convex nature of the KKT attack objective.
"The attacker objective is related to minimizing norm of the gradient, and becomes complicated for logistic regression models. Details of the attack formulation in Koh et (218).
30


Reviews:
[{"review_id": "ktj6jzDFs32", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents an improvement on an interesting problem: poison a dataset to induce a machine learning process to a misleading model. This field of study has been trending in recent years, and this paper presents a neat increment over previous works. The basic idea is that the attacker iteratively generates new data points so as to minimize the difference between the poisoned model and the target model. This approach requires retraining the model in each iteration, which is a costly procedure. This work then propose to use an online learning approach to update the model with a small cost to accelerate the entire process, and thus provide an efficient data poisoning approach.\n\nThere are several issues with both the work itself and the presentation. The main issue is about the evaluation. The approach is only evaluated on one dataset (Adult dataset), considers only one model (SVM) and compared against one approach (KKT attack). This is not enough to justify the universal effectiveness of the approach applying to other machine learning algorithms. In particular, modern deep learning algorithms typically suffer catastrophic forgetting issues when applying online learning algorithms, and these models are of more interests in the context of poisoning attacks. So this work does not provide enough evidence to justify that the proposed approach is effective in dealing with them.\n\nMaybe I neglect them, but I do not find the description of the adult dataset's stats, i.e., how large is the dataset? The paper studies poisoning more 1500 data points, what percentage is these data to the entire dataset? It looks like, from the description, that these dataset might be 100% of the entire dataset. Isn't this too large to be feasible in the real setup?\n\nIn addition, it might be important to compare against Jagielski's 2018 paper [1], which is not cited, as well in the non-subpopulation setup, in addition to KKT, which should provide a better baseline. This work also presents a set of commonly used dataset and machine learning models, which can be experimented with in the context of this work.\n\nPart of the above is presentation issues, and there are more issues in the presentation of the theoretical part. For example, the presentation of Thm 4.1 uses the term of epsilon-close, but I don't find its formal definition above (like in Sec 2). Thm 4.2 uses a notion of c(theta) without a definition of what it is. It seems c indicates a clean dataset (when in subscription), but I find it difficult to read it when there is an argument theta associated with it. These issues make me hard to understand what the main theorems of this work want to tell us.\n\nI think the paper should be revised to fix the presentation issues first so that we can evaluate more accurately whether the theoretical results have enough merit to upgrade my rating; also it may be helpful if more experiments can be conducted to demonstrate that the approach is effective on more datasets and more machine learning models.\n\n[1] Matthew Jagielski, et al. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning, SP 2018\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EmcgivRCQR4", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies model-targeted poisoning attacks during training time. The victim learner is assumed to be a convex learner that performs regularized empirical risk minimization. Instead of formulating the problem as a bi-level optimization as standard, the paper proposes reducing the attack to an online learning problem, where the adversary decides on a poisoning data point in a sequential manner. The data point that leads to the largest difference of loss between the current model and the target model is selected as the next point to inject into the training data. In doing so, the learned model will converge to the target model in the long run. The paper provided a theoretical analysis on how many data points are needed to achieve a pre-specified small distance to the target model. Experiments demonstrated the effectiveness of the proposed attack.\n\nThe main advantage of the paper lies in that it draws the first connection between the data poisoning attack and online learning. The techniques used in the paper very novel. While the proposed attack algorithm looks simple, it actually has a deeper theoretical reason for why the attack can be effective. The authors also give a rigorous theoretical result on how many poisoning points are needed in order to drive the learner’s model toward a target model. This result is elegant!\n\nAnother strength of the paper is that the proposed online learning-based attack can even outperform the traditional KKT attacks. This is surprising to me because the KKT formulation is in fact an optimal-attack formulation. The only place that could incur sub-optimality in the KKT approach is the nonlinearity of the attack optimization, which may not solve to the global-optima solution. I am wondering if the authors could provide some intuition about why the proposed attack results in superior attack performance as compared to traditional data poisoning attacks?\n\nI am also curious if the attack in this paper extends to the deep learning setting, where the victim learners are no longer convex. Empirically it would be nice to show some results on that, although the theoretical results definitely do not easily extend. Currently, the paper only experiments on simple tasks where the dataset is kind of small. It would be more convincing to study larger datasets and verify whether the proposed attack can outperform existing baselines across a variety of tasks.\n\nOverall, I enjoy reading the paper, and I think it makes significant contributions that push forward the frontier of data poisoning attack. In particular, the online learning approach is very appealing and gives a very nice formulation of the model-targeted attack.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8MkMIM-28PQ", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Most existing data poisoning attacks are objective driven, e.g., the poisoned model is inaccurate for certain inputs (called subpopulation). The authors define model-targeting attack, in which the attacker aims to poison training data such that the learnt model is a given target model. The authors define distance between the poisoned model and the target model using their loss difference (this reduces to objective driven poisoning attack). Evaluation on linear SVM is performed and comparison with one existing attack is conducted. \n\n1. The model-targeted poisoning attack is an ill-defined problem. When measuring the model-targeted poisoning attack, one should use some distance between the poisoned model and the target model, e.g., L2 distance (it's good that the evaluation considers this). The loss based metric reduces the model-targeted poisoning attack to be similar to objective-drive attack. However, when measuring success using distance between the poisoned model and the target model, the attack is obviously unsuccessful when the loss function is non-convex. Many ML loss functions are non-convex. In such non-convex cases, you cannot get the same model parameters in multiple runs of the same algorithm and training data, even if there are no poisoned data points. So the attack could only be successful for strongly convex loss functions, which have a global optimal solution. I would suggest the authors to explicitly mention that the attack is limited to such setting. Moreover, redefine the success metric to measure the attack. However, once limited to such setting, the paper's contribution is also limited. \n\n2. Insufficient evaluation. The evaluation does not compare with subpopulation attacks. I understand you study model-targeted attacks. Since the evaluation is for subpopulation attacks. It is still interesting to know the comparison results. \n\n3. Only linear SVM is evaluated. I suggest evaluating other models and datasets. \n\n4. Why is model-targeted poisoning attack relevant? Objective-driven attacks are more relevant. In fact, the evaluation is on subpopulation attack, which is an objective-driven attack. \n\n\nTypos\n\nis the setting use in many prior works -- used\n\nalso allow arbitrary selectiong of the poisoning points -- selection\n\nclassifier that that has 0% accuracy -- that", "extra_scores": {}, "extra_text": {}}, {"review_id": "6syN9kB7Xyi", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Paper summary**\nThe paper proposes an algorithm, that works in an online fashion, for targeted poisoning attacks. If the loss function is convex, then the algorithm is guaranteed to converge to the target as the number of poisoned samples increases. The paper claims that this is the first model-targeted attack which has theoretical guarantees. The lower bound provided is interesting in the sense that it can give a lower bound on the number of samples needed to reach the target model from the current model.\n\n**Strengths**\n1. The paper proposes a new algorithm that works by progressively adding poisoned points to the dataset. Theoretical guarantee (Theorem 4.1) is also provided for the algorithm. The proof idea is well explained and I liked the connection with online learning and how the algorithm is reduced to follow-the-leader algorithm. \n2. The algorithm works by progressively adding more points and hence it can stop as soon as it is close to the target. This means that it does not need a predecided budget and if it is indeed optimal, then it would use the minimum number of poisoned points to reach the target.\n3. On SVMs, the experiments show that the attack is almost optimal in the sense that it matches the theoretical lower bound.\n\n**Concerns**\n1. Theorem 4.2 is a lower bound for the minimum number of samples needed to reach the target model exactly. Can we say something about reaching the target model approximately (say up to distance $\\epsilon$)? I think this can be achieved by the following optimization in Theorem 4.2: $$\\inf_{\\theta':\\|\\theta'-\\theta_p\\|\\leq\\epsilon} \\sup_\\theta c(\\theta,\\theta')=\\frac{L(\\theta';\\mathcal{D}_c)-L(\\theta;\\mathcal{D}_c)+NC_R(R(\\theta_p)-R(\\theta))}{\\sup(l(\\theta;x,y)-l(\\theta';x,y))+C_R(R(\\theta)-R(\\theta')))}.$$\n\nFurther, how much would the lower bound decrease (as a function of $\\epsilon$) if we are indeed interested in only reaching the target model approximately?\n\n2. In the experiments, the lower bound is computed for the number of samples needed to reach the model induced after poisoning. This can be different from the target model. Hence, shouldn't the lower bound be computed for the number of samples needed to reach the target model? I think that would be the true lower bound for poisoning. However, I believe that the two numbers should be close.\n\n3. The experiments are performed only for linear SVMs. It would be more interesting to see if the attack also works well on deep neural networks. This is also important because the paper claims that the existing algorithms get stuck in bad local minima. Thus, it should be checked if this algorithm also gets stuck in bad local minima.\n\n**Score justification**\n\nModel poisoning is a very real threat in modern machine learning. Strong attacks provide good insights for developing strong defenses. I believe the attack proposed in this paper is strong and theoretically backed. Further, the paper also provides lower bound on the minimum amount of poisoning needed to reach the target model. However, I have some concerns regarding the attack's success on deep neural networks. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper establishes an interesting relationship between poisoning and online learning. Instead of framing the poisoning problem as a bi-level optimization problem as what is done conventionally, the paper proposes reducing the poisoning attack design to an online learning problem in which the adversary decides on a poisoning data point in a sequential manner.  The data point that leads to the largest difference of loss between the current model and the target model is selected as the next point to inject into the training data.

Pros
+ If the loss function is convex, the proposed algorithm is guaranteed to converge to the target, and the paper provides a lower bound on the number of samples needed to reach the target model from the current model. 

+ Experiments on SVMs show the advantageous performance of the proposed attack algorithm. 


Cons
- The reason why the proposed online learning method could outperform the KKT-based attack is not well justified theoretically. Experimentally, the paper would be stronger if evaluations are done on more diverse settings and data.  

- Reviewers have expressed concerns on how practical the proposed algorithm is, since the guarantees are established on convex loss functions. The paper would be stronger if  the authors can further compare the attack with deep-learning poisoning algorithms on larger datasets.


I truly believe that the paper’s exploration of convex models is an important step towards understanding the poisoning attacks and is a step towards understanding attacks for non-convex models. However, I do think that the paper could make a more profound contribution and impact with stronger experimental evaluations. 

Therefore, I would classify this paper as borderline, toward weak reject compared with other papers. 

Decision: Reject