{'fraction_non_alphanumeric': 0.04425461559658308, 'fraction_numerical': 0.01424634885643428, 'mean_word_length': 4.007036423841059, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Investigation of Data Poisoning Defenses for Online Learning

We consider data poisoning attacks, where an adversary can modify a small fraction of training data, with the goal of forcing the trained classifier to have low accuracy. While a body of prior work has developed many attacks and defenses, there is not much general understanding on when various attacks and defenses are effective. In this work, we undertake a rigorous study of defenses against data poisoning in online learning. First, we theoretically analyze four standard defenses and show conditions under which they are effective. Second, motivated by our analysis, we introduce powerful attacks against data-dependent defenses when the adversary can attack the dataset used to initialize them. Finally, we carry out an experimental study which confirms our theoretical findings, shows that the Slab defense is relatively robust, and demonstrates that defenses of moderate strength result in the highest classification accuracy overall.


Introduction
Machine learning is increasingly used in safety-critical applications, and hence designing machine learning algorithms in the presence of an adversary has been a topic of active research [2,3,4,5,11,12,13]. A style of adversary that is commonly studied is data poisoning attacks [4,12,15,21] where the adversary can modify or corrupt a small fraction of training examples with the goal of forcing the trained classifier to have low classification accuracy. Such attacks have threatened many real-world applications including spam filters [23], malware detection [25], sentiment analysis [24] and collaborative filtering [15].
There has been a body of prior work on data poisoning with increasingly sophisticated attacks and defenses [4,12,15,21,22,27,29,30]. However, the literature largely suffers from two main limitations. First, most work is on the batch setting -all data is provided in advance and the adversary assumes that the learner's goal is to produce an empirical minimizer of a loss. This excludes many modern machine learning algorithms, such as, stochastic gradient descent, or learning from a data stream. The second drawback is that there is little analysis, and hence not much rigorous understanding of exactly how powerful the attacks are, and the conditions under which defenses are successful.
In this work, we address both limitations by providing a rigorous analysis of data poisoning for online learning against four popular defenses. In online learning, examples arrive sequentially, and at iteration t, the learner updates its parameters based on the newly-arrived example. We select as our learner perhaps the most basic yet widely-used algorithm -online gradient descent (OGD). Starting with an initial parameter value and a loss function, OGD updates its parameter value by taking a small step against the gradient of the loss at the current example. For data-poisoning, we assume the semi-online setting [32] -the adversary's goal is to attack the classifier produced at the end of online learning. Additionally, the learner has a defense in place that filters out input examples with certain properties that are determined by the precise defense.
To analyze the defenses, we consider three regimes of effectiveness. In the first easy regime, there exists a simplistic attack that can break the defense rapidly. In the second hard regime, there are no successful data poisoning attacks that succeed against a defense. In between lies an intermediate regime where effective attacks exist, but are not as simplistic or powerful. Specifically, our contributions are as follows: • We prove that the popular L 2 -norm defense, which filters out all examples outside an L 2 -ball is always in the easy regime and is hence mostly weak.
• We characterize conditions under which the labeling oracle defense [29,31], where the adversary only provides an unlabeled example to be labeled by an annotator, is in the easy regime or in the hard regime.
• We next analyze two data-dependent defenses -the L 2 -distance-to-centroid defense and the slab defense [12,30] -that are initialized based on clean data, and provide performance guarantees.
• Motivated by our analysis, we introduce a novel attack on the data-dependent defenses when the adversary is capable of corrupting a small fraction of the data used for initializing them.
Is our analysis confirmed by practice? And how do data poisoning defenses impact overall classification accuracy -given that they also act on clean examples? We next investigate these questions through an experimental study where we test classification accuracy under the L 2 -norm defense, the L 2 -distance-to-centroid defense and the slab defense for a variety of defense strengths and against a number of baseline attacks.
Our experiments corroborate that the L 2 -norm defense is mostly weak; in contrast, the L 2 -distanceto-centroid defense has three regimes of effectiveness, and the slab defense has either three regimes of effectiveness or is robust depending on the dataset. We also find that our data-dependent attacks are highly effective against the L 2 -distance-to-centroid defense, and moderate to highly effective against the slab defense for some datasets. This indicates that the slab defense may be a highly effective defense overall for online learning. Finally, we find that in most cases, classification accuracy is the highest when the defense strength is moderate -which ensures that not too many clean examples are filtered out by the defenses. This indicates that defense parameters need to be chosen suitably in real applications while taking classification accuracy into account.
Related Work. The work closest in spirit to ours is [12], which proposes and analyzes strong data poisoning attacks that break a number of data sanitization based defenses. Their work however differs from ours in two major ways. First, they are in the offline setting where all data is provided in advance and the learner is an offline empirical risk minimizer; second, their analysis focusses on the number of distinct poisoning examples needed while ours characterizes when defenses are effective against attacks. [19,20] provides upper bounds on the number of poisoning points required to poison online and offline learners; however, they do not consider specific defenses, and their results only hold for certain classes of distributions. [10] provides a convex optimization algorithm that is resistant to data poisoning attacks and has provable guarantees; however, their algorithm is also in the offline setting and requires advance knowledge of the data.
Data poisoning is a threat to a number of applications [15,23,24,25], and hence there is extensive prior work on it -mostly, in the offline setting. Efficient attacks have been developed against logistic regression, SVM and neural networks [4,12,21,22,29], and defenses have been in analyzed in [15,30].
Recent work has looked at data poisoning in the online setting against classification [14,32,34], contextual bandits [17] and autoregressive models [1]. Prior works on online attacks include [32], which finds an efficient gradient-ascent attack method for a number online objectives, and [14], which views the attack process as an optimal control problem to be solved by a nonlinear optimization solver or be approximated using reinforcement learning [34]. However, little is understood on the defense side, and our work is the first to provide theoretical performance guarantees of attacks and defenses for online data poisoning. Finally, there has also been prior work on outlier detection [7,8,9]; unlike ours, these are largely in the unsupervised learning setting.

The Setting
We consider online learning -examples (x t , y t ) arrive sequentially, and the learner uses (x t , y t ) to update its current model θ t , and releases the final model θ T at the conclusion of learning. Our learner of choice is the popular online gradient descent (OGD) algorithm. The OGD algorithm, parameterized by a learning rate η, takes as input an initializer θ 0 , and a sequence of examples S = {(x 0 , y 0 ), . . . , (x T −1 , y T −1 )}; at iteration t, it performs the update: where is an underlying loss function -such as square loss or logistic loss. We focus on logistic regression classifiers in this work, which uses logistic loss.
Attacker and Defense Model. We consider attackers that can add at most K examples to the data stream in any position. The attacker's goal is to modify the final model θ T output by the learner so that it satisfies certain objectives. For example, θ T could be equal to a specific θ * , or have high error on the data distribution.
We assume that the attacker works against a learner equipped with a defense mechanism that is characterized by a feasible set F. If the incoming example (x t , y t ) ∈ F, then it is used for updating θ t ; otherwise it is filtered out. For example, in the popular L 2 -norm defense, F is an L 2 -ball of radius R; data-dependent defenses such as the Slab and the L 2 -distance-to-centroid defense correspond to more sophisticated feasible sets.
We may now formalize the attacker as follows.
Definition 2.1 (Data Poisoner). A Data Poisoner DP η (θ 0 , S, K, F, θ * , ), parameterized by a learning rate η, takes as input an initializer θ 0 , a sequence of examples S, an integer K, a feasible set F ⊆ X × Y, a target model θ * , and a tolerance parameter and outputs a sequence of examples S. The attack is said to succeed ifS has three properties -first, an OGD that uses the learning rate η, initializer θ 0 and input streamS will output a model θ s.t. θ * − θ ≤ ; second,S is obtained by inserting at most K examples to S, and third, the inserted examples lie in the feasible set F.
For simplicity of presentation, we say that a data poisoner outputs a model θ if the OGD algorithm obtains a model θ over the data streamS.

Analysis
In this section, we analyze the effectiveness of common defenses against data poisoning. In order to test the strength of a defense, we propose a simple data poisoning algorithm -the SimplisticAttack. A defense is weak if this attack succeeds for small K, and hence is able to achieve the poisoning target rapidly. In contrast, a defense is strong if no attack can achieve the objective. We analyze the conditions under which these two regimes hold for an online learner using logistic loss.
Algorithm 1 SimplisticAttack(θ 0 , S, K, F, θ * , , R) Let θ 0 be the model learned over the clean stream S starting from θ 0 . λ = θ * ,S = S, t = 0, γ 0 = min R/ θ 0 − θ * , 1/η The SimplisticAttack algorithm is described in Algorithm 1. Suppose the online learner has an initial model θ 0 , and the poisoning target is θ * . SimplisticAttack appends at most K poisoning points to the clean stream S. Let θ 0 denote the output of OGD on S. The poisoning points all lie on the line θ * − θ 0 with magnitude at most R. The algorithm is inspired by the iterative teaching method in [16].

Bounded L 2 Norm Defense.
In many applications, the learner requires the input vector to be within a bounded domain, for example having bounded L p norm. We consider inputs with bounded L 2 norm, which corresponds to a defense mechanism with a feasible set F = {(x, y)| x 2 ≤ R} for some constant R. Notice that if the input domain is bounded by L ∞ or L 1 norms, we can still find an L 2 ball inscribed in the domain. We next show that SimplisticAttack is a very efficient data poisoner for this setting.
Theorem 3.1. Let θ 0 and θ * be the initial and the target model. Suppose the feasible set Remark. Theorem 3.1 suggests that SimplisticAttack outputs a θ close to θ * within logarithmic number of steps w.r.t. 1/ . Therefore, the defense is in the easy regime if C is not too large. The factor C increases with decreasing R, and is in the order of O(1/R) when R is small. However, in real applications, the learner cannot set R to be arbitrarily small because this also rejects clean points in the stream and slow down learning. We investigate this in more details in the experiment section.

The Labeling Oracle Defense
In many applications, the adversary can add unlabeled examples to a dataset, which are subsequently labeled by a human or an automated method. We call the induced labeling function a labeling oracle. Denoting the labeling oracle by g, we observe that this oracle, along with bounded L 2 norm constraint on the examples, induces the following feasible set: For simplicity, we analyse the oracle defense on a different feasible set F = {(yx, +1)|(x, y) ∈ F} derived from F. We call F the one-sided form of F because it flips all (x, −1) ∈ F into (−x, +1) and as a result only contains points with label +1. Lemma A.1 shows that an attacker that outputs θ using K points in F always corresponds to some attacker that outputs θ using K points in F and vice versa. Therefore, the defenses characterized by F and F have the same behavior.
We next show that for feasible sets F of this nature, three things can happen as illustrated in Figure 1. First, if F contains a line segment connecting the origin O and some point in the direction of θ * − θ 0 , then SimplisticAttack can output a θ close to θ * rapidly. Second, if F is within a convex region G that does not contain any point in the direction of θ * − θ 0 , then no poisoner can output θ * . Third, if F contains points in the direction of θ * − θ 0 but not the origin, then the attack can vary from impossible to rapid. Theorem 3.2 captures the first and the second scenarios, and Appendix A.4 shows various cases under the third.
Theorem 3.2. Let L(r, u) = {cu/ u |0 < c ≤ r} denote a line segment connecting the origin and ru/ u for some vector u. Also, let θ 0 , θ * be as defined in Theorem 3.1 and θ 0 be the online learner's model over the clean stream S. Suppose θ * = λ. Figure. 1: Schematic illustration of the one-sided feasible sets F corresponding to three defense regimes. Left to right: defense in the easy, hard and intermediate regime.
Remarks. The second statement implies that if G L(+∞, θ * − θ t ) = ∅ for θ t at time t, then no attack is possible from time t onwards.

Data-driven Defenses
A common data poisoning defense strategy is to find a subset of the training points that are anomalous or 'outliers', and then sanitize the data set by filtering them out before training. Following [6,12,26,30], we assume a defender who builds the filtering rule using clean data that the poisoner cannot corrupt. Thus the poisoner knows the defense mechanism and parameters, but has no way of altering the defense. We focus on two defenses, the L 2 -distance-to-centroid defense and the Slab defense [12,30], which differ in their outlier detection rules.
Defense Description. Both defenses assign a score to an input example, and discard it if its score is above some threshold τ . The L 2 norm constraint on the input vector still applies, i.e. x ≤ R. Let µ + denote the centroid of the positive class and µ − the centroid of the negative class computed from the clean initialization set.
L 2 -distance-to-centroid defense assigns to a point (x, y) a score x − µ y . This induces a feasible sets First, if τ is large such that either F c + or F c − contains the origin, then SimplisticAttack can approach the target rapidly. Second, if τ is small such that the one-sided form of F c does not contain any point on the positive side of the hyperplane with normal vector (θ * − θ 0 ), then no attack is possible. Lemma 3.3 shows the condition for these two cases.
, then no data poisoner can output θ * for any K.
Slab Defense. Each of F s + and F s − is a 'disc' between two hyperplanes with normal vector β. When τ is large such that either F s + or F s − contains the origin, SimplisticAttack can approach θ * rapidly. When τ is small and the projection of y(θ * − θ 0 ) on β is in the opposite direction to that of µ y for y = +1 and −1, then no attack is possible. Lemma 3.4 characterizes the condition for both cases.
then no data poisoner outputs θ * for any K.
We examine the effectiveness of both data-driven defenses with various defense parameters τ in the experiment section.

Attacking Data-driven Defenses
Analysis on data-driven defenses in Section 3 assumes that the attacker cannot influence the outlier detector. However in practice, the initialization set used to generate the outlier score is rarely absolutely clean, and hence the score is often based on a mixture of clean and poisoned data [12,30]. Motivated by our analysis in Section 3, we propose two attacks on data-driven defenses. These attacks inject m poisoning examples into the initialization set of size n so as to undermine defense.
Attack on L 2 -distance-to-centroid Defense. Lemma 3.3 shows that the defense breaks down if the norm of the centroid is small compared to the defense parameter. This motivates us to move the centroid closer to the origin. WLOG, we consider the centroid µ + for points with +1 labels. The attacker injects m copies of (x, +1), where x is found by solving the following optimization problem Attack on Slab Defense. Lemma 3.4 shows that the defense breaks down if τ is large compared to −yβ µ y where β = µ + − µ − . This motivates us to reduce the latter by altering the defense direction. In specific, the attacker can maximize the angular difference, or equivalently minimize the cosine value between the defense directions before and after contaminating the data set. Let n + and n − denote the number of points with +1 and −1 label in the initialization set. The attacker injects m + copies of (x + , +1) and m − copies of (x − , −1) obtained from solving the following problem We examine the effectiveness of these attacks in Section 5.

Experiments
Is our analysis confirmed by practice? And how do data poisoning defenses impact overall classification accuracy -given that they also act on clean examples? We now investigate these questions through an experimental study. In particular, we ask the following questions.
• Do practical data-poisoning defenses exhibit the different regimes of effectiveness that we see in theory?
• How is classification accuracy affected by the presence of data-poisoning defenses?
• How effective are our proposed data-driven attacks against the L 2 -distance-to-centroid and the Slab defense?
These questions are considered in the context of three defenses -L 2 -norm, L 2 -distance-to-centroid and Slab. The labeling oracle defense is not included because we lack appropriate labeling functions for the real-world tasks involved in the experiment.

Experimental Methodology
Baseline Attacks. To evaluate the effectiveness of the defenses, we consider four canonical baseline attacks. All attacks we use append the poisoning examples to the end of the clean data stream, as [32] shows that this works best for our setting.
The Straight attack uses the SimplisticAttack algorithm with one minor difference -when the generated (x t , y t ) lies outside the feasible set F, it is projected back onto F. The Greedy attack, motivated by [16], finds, at step t, the example (x t , y t ) ∈ F that minimizes θ t+1 − θ * , where θ t+1 is derived from the Online Gradient Descent update rule; this example is then added to the end of the stream. The Semi-Online attack [32] finds K poisoning examples together by maximizing the loss of the resulting model on a clean validation dataset. The optimization problem is solved using gradient descent. The poisoning points are again inserted at the end.
As a sanity-check, we also include an offline baseline -the Concentrated attack [12], which performs well against many offline defenses. The original attack generates a poisoning set instead of a sequence. To convert the poisoning set to a sequence, we need to impose an ordering on the points. We consider three orders -positive first, negative first and random -and report the best results of the three. This poisoning sequence is again added to the end of the stream.
Finally, we also implement our data-driven attacks in  For Straight, Greedy and Concentrated attacks,the target model θ * is the negation of the offline optimal model on the validation set scaled to unit L 2 norm. For L 2 -norm defense, the defense parameter τ is the maximum L 2 norm of the input; for L 2 -distance-to-centroid, τ is the maximum L 2 distance between an input to its class centroid, and for Slab, it is the maximum Slab score.

Results and Discussion
Results. We present three categories of results. First, to directly measure the speed of attacks, Figure 2 presents the test accuracy of the output model against the defense parameter τ when only poisoned examples are filtered by the defense. Second, to determine the effect of defenses on accuracy in practice, Figure 3 presents the test accuracy of θ against τ where both clean and the poisoned examples are filtered. Finally, to evaluate our proposed data-driven attacks, the test accuracy of θ against τ under the Straight attack is plotted in Figure 4 for different levels of contamination of the initialization set. Here, the defense filters out both clean and poisoned examples as in practice.   Overall Performance of Attacks. We see that Straight, Greedy and Semi-Online are effective online attacks, while Concentrated is mostly ineffective as it ignores the online nature of the problem. Straight and Greedy perform similarly. Semi-Online typically performs better than Straight, as it has more flexibility in selecting the poisoning examples; however it is also more prone to local minima.
Regimes of Effectiveness for Defenses. We find that the L 2 -norm defense is overall a weak defense. For small τ (corresponding to small R), attacks are not very effective, while a slight increase in τ results in rapid attacks. This is to be expected as the constant C in Theorem 3.1 depends inversely on R, and the results overall confirm the theory. The L 2 -distance-to-centroid defense shows three regimes of effectiveness, confirming our theory. The Slab defense also shows three regimes for IMDB, but appears to be strong for the other datasets. This indicates that Slab may be a highly effective defense in the online setting.
Classification Accuracy vs. Defense Strength. We find that overall classification accuracy goes through three stages as we increase the defense parameter τ (or, equivalently, decrease defense strength). When τ is small, accuracy is low as the defense also filters out most clean points. For moderate τ , more clean and poisoning points are used to update θ, and the accuracy depends on the relative 'strength' of the two sets. Finally, for large τ , the defense is weak enough to let in both clean and poisoning examples, again leading to low accuracy. Thus moderate values of τ are largely best for classification accuracy. The exception is the Slab defense, which appears to retain high accuracy for most datasets with increasing τ .
Data-Driven Attacks. We find that the data-driven attacks are highly effective for L 2 -distance-tocentroid defense. The test accuracy drops with increasing contamination, and at 20% contamination, the defense completely breaks down on MNIST, fashionMNIST and IMDB Review. The Slab defense, in contrast, is more robust even to data-driven attacks -the learner can still find a τ that gives high accuracy on each data set in spite of initial contamination. This suggests that the Slab defense may be a highly effective defense overall for online data poisoning.

Conclusion
In conclusion, we perform a thorough theoretical and experimental study of defenses against data poisoning in online learning. Our theoretical analysis shows that typical defenses are in three possible regimes and establishes conditions under which they hold, and motivates novel data-driven attacks. Our experiments validate our theoretical findings, show that classification accuracy is typically best for defenses of moderate stength, and demonstrate that the Slab defense is often highly effective in practice, even against data-driven attacks. There are many avenues for future investigationfor example, to more complex models such as neural networks and to other settings such as the fully-online setting of [32]. In particular, an important line of future work is to extend our analysis to more complex and realistic learning settings, such as reinforcement learning, and provide attacks and defenses with provable guarantees.

A Proofs to Theorems and Lemmas
A.1 Proof to Theorem 3.1 η . Suppose we set y t = 1 and x t = γ t (θ * − θ t ); this (x, y) lies in F from the way we choose γ t . Notice that θ t θ * − θ t 2 ≤ λ 2 . If γ t = γ * t , then the poisoner can output θ * in the next step. Otherwise if γ t = γ 0 , the norm of θ t − θ * shrinks geometrically because The first inequality holds because θ t θ * − θ t 2 ≤ λ 2 and the monotonicity of exponential function. The last equality holds because 1 − . Notice that if we let λ = 1, the Taylor expansion of C at γ 0 = 0 is approximately 2/(ηγ 0 ). If we treat R as a variable, then when R is small, γ 0 = R/ θ 0 − θ * , and therefore C is approximately 2 θ 0 − θ * /(ηR), which is in the order of O(1/R).
We first show that if a data poisoner can output θ using a sequenceS = {(x 0 , y 0 ), · · · , (x T −1 , y T −1 )} with each point (x i , y i ) ∈ F, then there must be a data poisoner that output θ using a sequencẽ S = {(x 0 , y 0 ), · · · , (x T −1 , y T −1 )} with each point (x i , y i ) ∈ F . Notice that for an OGD algorithm running on logistic regression model, (x, +1) and (−x, −1) will lead to the same gradient updates on the model parameter. We constructS as follows. For each (x i , y i ) ∈S, if (x i , y i ) ∈ F , then we let (x i , y i ) = (x i , y i ); otherwise, we let (x i , y i ) = (−x i , −y i ). Notice by the construction rule of F , at least one of (x i , y i ) and (−x i , −y i ) exists in F . Hence, we have obtained a data poisoner on F using a poisoning sequence of same length and outputing the same model as a poisoner on F.
The reverse direction is similar. We can use the same technique to show that whenever a poisoner can output θ using a sequence of length T with points on F , there is a sequence using points on F that achieves the same goal. Therefore, the statement is true.

A.3 Proof to Theorem 3.2
For the first part, we use the same poisoning sequence as in the proof of Theorem 3.1; what remains to be shown is that all (x t , y t ) in this sequence still lie in the feasible set F. To show this, we begin with showing that for any t, θ t − θ * = c( θ 0 − θ * ) for some scalar c ∈ [0, 1].
We prove this by induction. The base case is easyt = 0, and c = 1. In the inductive case, observe that: and that (1 − ηγ t /(1 + exp( θ t ( θ t − θ * )γ t ))) ∈ [0, 1] by construction. Thus, the inductive case follows. Now, observe that the proof of Theorem 3.1 still goes through, as y = 1 and is still a feasible point to add to the teaching sequence.
For the second part, observe that if the data poisoner outputs θ * , then θ * = θ 0 −η i (θ i−1 , x i , y i )y i x i for some (x i , y i )'s. For the augmented feasible set F , y i = +1 always. For logistic regression, > 0 always. Hence, there should exist some collection of x i 's, and some positive scalars α i such that: However, Lemma A.2 shows that such collection is impossible by letting u = θ * − θ and β = 1. Therefore, no data poisoner can output θ * .
Lemma A.2. Let G be a convex set, u be a vector and ru / ∈ G for all r ≥ 0. Then there is no set of points {x 1 , · · · , x n |x i ∈ G, ∀i ∈ [n]} such that i α i x i = βu for any α i , β ∈ R + and n ∈ Z + . Proof. We prove the statement by induction. The base case n = 1 is true because G does not contain any point in the direction of u. Suppose the statement is true for n = k. Assume there exists a set S = {x 1 , x 2 , · · · , x k+1 } such that Let x = α1 α1+α2 x 1 + α2 α1+α2 x 2 . Since both x 1 and x 2 are in G by our assumption, x is also in G by the definition of convex set. Multiplying both side of the equation above by 1 α1+α2 , we obtain The equation implies that a setS = {x } S\{x 1 , x 2 } is a set of k points in G such that a positive linear combination of them gives a vector in the direction of u. However, this contradicts our inductive assumption when n = k. Therefore, there cannot be a set of k + 1 points from G that satisfies Equation 5. The statement we want to prove is also true for n = k + 1.

A.4 Various Attack Rates in the Intermediate Regime
In Section 3, we conclude that the poisoning attack's rate can vary from impossible to rapid in the intermediate regime. We show three examples in which the attack is very rapid, slow and impossible.
The Rapid Case. SimplisticAttack is shown to be effective against L 2 -norm defense. LetS = {(x 0 , +1), · · · , (x T −1 , +1)} be the poisoning sequence generated by SimplisticAttack against L 2 -norm defense, which only uses points with +1 label. Let x min denote the point with the smallest L 2 norm among x 0 , · · · , x T −1 . A feasible set F = {(rx xmin , +1)|r ≥ 1} contains all points inS but not the origin. An attacker can useS as the poisoning sequence to approach its target as rapidly as against L 2 -norm defense, even though the feasible set F does not contain the origin.
The Slow Case. Notice that the poisoning points in SimplisticAttack normally have diminishing magnitudes towards the end. We now show that if the attacker is only allowed to use poisoning points with constant magnitude, then the attack can be very slow.
Suppose the feasible set only contains a single point (x, +1) where x = r θ * − θ0 . The attacker can only choose (x, +1) as the poisoning point. The gradient update will be for all t.
We consider a 1-D example with θ 0 = 0.5, θ * = 1, step size η = 1 and an L 2 -norm upperbound r = 10. If the attacker can choose any point (x, +1) such that x ≤ r = 10, the attacker can reach its objective with a single poisoning points by solving the following equation which gives x ≈ 1.629.
Now suppose the attacker is only allowed to choose (r, +1) as the poisoning point. Let ∆ t denote the difference between θ t+1 and θ t . We have (5) .
The inequality is because θ t ∈ [0.5, 1] as it starts from θ 0 = 0.5 and approaches θ * = 1. The attacker then needs at least 0.5(1+exp(5)) 10 = 8 poisoning points to achieve its goal. Notice that the exponential term grows much more rapidly then the denominator. If r = 20, the attacker will need at least 0.5(1+exp(10)) 20 = 551 points! In short, the attacker needs exponentially many points w.r.t. r in this case to achieve the same objective that can be done using a single point against L 2 -norm defense.
This example also naturally extends to high dimensional inputs as long as the attacker only wants to change one coordinate of the model parameter.
The Impossible Case. We consider the same θ 0 , θ * and η as in the slow case. Now the attacker can only choose (2.5, +1) as the poisoning point, i.e. r = 2.5. After one update step, the model θ becomes θ = θ + ηx Notice that the model parameter monotonically increases if the attacker adds more poisoning points of (2.5, +1) into the stream. Therefore, this θ after one poisoning point is the closest the attacker can ever get to the target θ * = 1. No data poisoner can output θ * exactly.

A.5 Proof to Lemma 3.3
For simplicity, we consider a feasible set F c = {(yx, +1)|(x, y) ∈ F c }, which is the one-sided form of F c . As a consequence of Lemma A.1, defenses characterized by F c and F c have the same behavior.
Also, let L(r, u) denote a line segment connecting the origin and a point r u u as in Theorem 3.2.
The Rapid Case. For the first part, we show that there exists an r > 0 such that L(r, θ * − θ 0 ) ⊆ F c + F c − . Suppose µ + < τ . Let α denote the angle between µ + and θ * − θ 0 , and let x = l(θ * − θ 0 )/ θ * − θ 0 be a point in the direction of θ * − θ 0 with norm l. A point (x, +1) is in F c + if and only if it satisfies the following inequality We want to find the range for l when the inequality holds. Notice that the determinant of this quadratic inequality, µ + 2 (cos α) 2 − µ + 2 + τ 2 , is always positive. Therefore, real solutions always exist for the lower and upper bound of l. Solving the inequality gives us It is also easy to verify that the lower bound is smaller than 0 and the upper bound is larger than 0.
We first look at F c + . The condition µ + , θ * − θ 0 < 0 implies that µ + ∈ G. The distance between µ + to the hyperplane (θ * − θ 0 ) x = 0 is u + . Since u + ≥ τ , none of the point in F c + can cross the hyperplane, and therefore F c + ⊆ G. The proof for showing F c − in G is analogous. Therefore G contains both F c + and F c − . In addition, G does not contain any point A.6 Proof to Lemma 3.4 For simplicity, we consider a feasible set F s = {(yx, +1)|(x, y) ∈ F s }, which is the one-sided form of F s . As a consequence of Lemma A.1, defenses characterized by F s and F s have the same behavior.
We first look at F s + when 0 > τ − b + > −τ − b + . We know that the Slab score |β x + b + | ≤ τ for all x ∈ F s + . Combining with the condition that τ − b + < 0, we have β x ≤ τ − b + < 0 for all x ∈ F s + .

B.1 Data Preparation
UCI Breast Cancer. Initialization, training, validation and test data sets have size 400, 100, 50, 100 respectively. The data set is divided in random. Since the data set is small in size, we split the data set in ten different ways, run experiments on all ten data sets and report the average test accuracy.

IMDB Review
We train a Doc2Vec feature extractor on the 50000 unlabeled reviews provided in the original data set using the method in [28]. Then we convert reviews in the original training and test set into feature vector of d = 100 using the extractor. Initialization, training, validation and test data sets have size 10000, 5000, 2000, 5000 respectively. The first three data sets are drawn from the original training set in vector representation without replacement. The test set is drawn from the original test set.
MNIST 1v7. We use a subset of the MNIST handwritten digit data set containing images of Digit 1 and 7. Initialization, training, validation and test data set have size 8000, 1000, 500, 1000 respectively. The first three data sets are drawn from the original MNIST training sets in random with no replacement. The test set is drawn from the original MNIST test set.
fashionMNIST Bag v.s. Sandal. We use a subset of the fashionMNIST data set containing images of bags and sandal. Initialization, training, validation and test data set have size 8000, 1000, 500, 1000 respectively. The first three data sets are drawn from the original fashion-MNIST training sets in random with no replacement. The test set is drawn from the original fashionMNIST test set.
Each data set is normalized by subtracting the mean of all data points and then scaled into [−1, 1] d .

B.2 Detailed Experiment Parameters.
The learning rate η is set to 0.05 for UCI Breast Cancer and 0.01 for the other three data sets. The model obtained after making one pass of the training set using OGD algorithm has high accuracy on all data sets.
For Concentrated attack, the attacker needs to divide its attack budget, i.e. number of poisoning points, to points with +1 and −1 labels. We try three different splits -all +1 points, half-half, all −1 points -and report the best in terms of poisoning effect.
As mentioned in Section 5, Concentrated attack also needs to impose an order to points in the poisoning set. In positive first order, the attacker appends all the points with +1 label to the data stream before appending points with −1 labels. In negative first order, the attacker appends all the points with −1 label to the data stream first instead. In random order, the points are shuffled and appended to the data stream. We try 100 different random orders, and report the best among the positive-first, negative-first and random orders in terms of poisoning effect.
For poisoning the initialization set used by slab defense, the attacker also needs to divide its attack budget to points with +1 and −1 labels. We divide the budget proportional to the fraction of +1 and −1 points in the clean initialization set.