Stronger Data Poisoning Attacks Break Data Sanitization Defenses

Introduction

In high-stakes settings like autonomous driving (Gu et al., 2017), biometrics (Chen et al., 2017), and cybersecurity (Rubinstein et al., 2009; Suciu et al., 2018), machine learning (ML) systems need to be secure against attacks by malicious actors. Securing ML systems is complicated by the fact that they are often trained on data obtained from the outside world, which makes them especially vulnerable. By attacking this data collection process, which could be as easy as creating a new user account, adversaries can inject malicious data into the system and cause it to fail.

These data poisoning attacks are the focus of the present work. We consider attacks against classifiers where an attacker adds a small fraction of new training points to degrade the performance of the trained classifier on a test set. Figure 1 illustrates this setting: a model that might otherwise correctly classify most of the data (Figure 1-Left) can be made to learn a significantly different decision boundary by an attacker who injects just a small amount of poisoned data (Figure 1-Middle).

A common and often effective defense against data poisoning attacks is data sanitization, which uses anomaly detectors to filter out suspicious training points (Hodge and Austin, 2004; Cretu et al., 2008; Paudice et al., 2018). Figure 1-Right illustrates a hypothetical defense: by removing the anomalous poisoned data, the defender can learn the correct decision boundary. In our experiments, data sanitization defenses were able to defeat all of the existing data poisoning attacks we tested.

However, those attacks were naive in that they did not explicitly try to evade the data sanitization defenses. This is typical in the literature: attackers might be optimized to act within an attack budget (Mei and Zhu, 2015b) and to only add points that belong to the input domain (e.g., word counts in a document should be integer-valued (Nelson et al., 2008; Newell et al., 2014), but not to evade defenses. Previous work has suggested that attacks optimized for evading data sanitization can in fact evade some types of defenses (Steinhardt et al., 2017), whereas attacks that are not optimized can be easily detected as anomalies (Frederickson et al., 2018). This leads to the question of whether data sanitization defenses are vulnerable to attackers who explicitly try to evade anomaly detection.

In this paper, we answer this question in the affirmative. We develop three data poisoning attacks that can simultaneously evade a broad range of common data sanitization defenses, including anomaly detectors based on nearest neighbors, training loss, singular-value decomposition, and the distance to class centroids. Our attacks are also able to deal with integer constraints on the input, which naturally arise in domains like natural language. For example, our attacks on a linear support vector machine increase test error on the Enron spam detection dataset from $3\%$ to $24\%$ and on the IMDB sentiment classification dataset from $12\%$ to $29\%$ by adding just $3\%$ poisoned data, even in the presence of these data sanitization defenses.

We adopt two strategies to evade data sanitization defenses. The first strategy is targeted at defenses which use anomaly detectors that are highly sensitive to the presence of just a few points: e.g., an anomaly detector that filters out points which are far from their nearest neighbors will not recognize a point as anomalous if it is surrounded by a few other points, even if those points is far from the rest of the data. Intuitively, such detectors tend to ‘overfit’ the training data. To evade these defenses, our attacks concentrate poisoned points in just a few distinct locations (Section 3). For example, poisoned data placed in a tight cluster will evade the nearest-neighbor-based anomaly detector that throws out points far away from other points. We show theoretically that we can concentrate all of the attack mass on just a few distinct points (e.g., only 2 points for 2-class support vector machines (SVMs) and logistic regression models) without any loss in attack effectiveness.

The second strategy is targeted at defenses which use anomaly detectors that are less sensitive and highly parametric: e.g., an anomaly detector that throws out points beyond some distance from the data centroid will not depend too much on the addition or removal of a few points from the data, as long as the data centroid does not change significantly. These defenses are more resistant to concentrated attacks, since they are less sensitive to small changes in the data (in this paper, we consider only attacks that inject a small fraction—3% or less—of poisoned data). To evade them, we formulate the attack as a constrained optimization problem, where the objective is to maximize the test loss of the model that the defender learns on the union of the clean and poisoned data; the optimization variables are the locations of the poisoned points; and the constraints are imposed by the defenses (such that a point that satisfies the constraints will be guaranteed to evade the defenses).

Formulating a data poisoning attack as an optimization problem is a common technique, first introduced in the context of support vector machines in Biggio et al. (2012b) and subsequently refined by Mei and Zhu (2015b) and later work. The central difficulty is that the bilevel problem—the attacker needs to reason about what model the defender would learn, which in turn requires solving an inner optimization problem—is non-convex and intractable to solve exactly (Bard, 1991), and even local methods like gradient ascent can be slow (Koh and Liang, 2017). This is made even more challenging in our setting, compared to prior work, because we have additional constraints that encode the defenses that the attacker wishes to evade. To overcome this computational hurdle, we use two ideas:

We concentrate the attacks on a small number of distinct points. Beyond allowing us to evade some data sanitization defenses, as discussed above, it also significantly improves computational efficiency as we only need to optimize for the locations of a few distinct points. We use this to speed up gradient ascent on the bilevel optimization problem, leading to what we call the influence attack (Section 4.1).

The bilevel problem is expensive to solve because the effect of the optimization variables (poisoned points) on the objective (test loss) depends on the model parameters that the defender learns on the poisoned data, an intermediate quantity that is expensive to compute. We break this dependency by first finding decoy parameters—model parameters that have high test error but low training error. Given fixed decoy parameters, we can then efficiently find poisoned points that yield the decoy parameters when trained on. We call this the KKT attack (Section 4.2), after the Karush-Kuhn-Tucker optimality conditions that used to derive this attack. Furthermore, we use these decoy parameters to adapt the attack introduced by Steinhardt et al. (2017), which in its original form is efficient but cannot evade loss-based defenses; this leads to our min-max attack (Section 4.3). These attacks mitigate some of the drawbacks of the influence attack, which is still too computationally intensive to scale to large datasets and sometimes gets stuck in local minima.

Finally, our study reveals several surprising facts about data poisoning:

Poisoned data does not have to look anomalous; if the poisoned points are carefully coordinated, each poisoned point can appear normal, as in the above example of the nearest-neighbor based anomaly detector.

Poisoned points need not have high loss under the poisoned model, so the defender cannot simply throw out points that have high loss. For example, given fixed decoy parameters, we can constrain our poisoned data to have low loss under those parameters.

Regularization reduces the effect that any single data point can have on the model and is therefore tempting to use as a defense against data poisoning. However, increasing regularization can actually make the defender more susceptible to attacks, because the defender becomes less able to fit the small fraction of poisoned points.

The success of our data poisoning attacks against common anomaly-based data sanitization defenses suggest that more work needs to be done on defending against data poisoning attacks. In particular, while anomaly detectors are well-suited to detect independently-generated anomalous points (e.g., due to some noise process in nature), a robust defense against data poisoning attacks will have to account for the ability of the attacker to place all of their poisoned data points in a coordinated fashion.

Beyond the merits of our specific attacks, our results underscore a broader point: data poisoning attacks need to account for defenses, and defenses correspondingly need to account for attacks that are specifically targeted against them. Attacks that do not consider defenses might work against a naive defender but be easily defeated by other defenses. Similarly, defenses that are only tested against basic attacks might give a false sense of security, as they might be broken by more determined and coordinated attackers.

Problem Setting and Defenses

In the setting we consider, the defender aims to pick a $\hat{\theta}$ with low test error $L_{\text{0-1}}(\hat{\theta};\mathcal{D}_{\text{test}})$, while the attacker aims to mislead the defender into picking a $\hat{\theta}$ with high $L_{\text{0-1}}(\hat{\theta};\mathcal{D}_{\text{test}})$. The attacker observes the test set $\mathcal{D}_{\text{test}}$ as well as a clean training set $\mathcal{D}_{\text{c}}=\{(x_{i},y_{i})\}_{i=1}^{n}$, and chooses $\epsilon n$ poisoned points $\mathcal{D}_{\text{p}}$ to add to $\mathcal{D}_{\text{c}}$. The defender observes the combined training set $\mathcal{D}=\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}}$ consisting of the original $n$ clean points and the $\epsilon n$ additional poisoned points; uses a data sanitization defense to remove anomalous points; and then learns $\hat{\theta}$ from the remaining data.

The attacker has several advantages: it knows the test set in advance (whereas the defender does not); it knows the defender’s training procedure; and it also gets to observe the clean training set $\mathcal{D}_{\text{c}}$. In reality, the attacker might not have access to all of this information. However, as defenders, we want to be robust even to attackers that might have the above information (this is the principle of security by design; see, e.g., Biggio et al. (2014)). For example, an attacker whose goal is to make the defender get a particular set of predictions wrong (e.g., the attacker might want to cause a “fake news” classifier to classify all websites from a certain domain as “real news”) would accordingly choose, and therefore get to observe, $\mathcal{D}_{\text{test}}$. In contrast, the defender might not know the attacker’s goal in advance, and therefore would not have access to $\mathcal{D}_{\text{test}}$.

In our experiments, we assume that $f_{\theta}$ is a linear classifier, i.e., $f_{\theta}(x)=\operatorname*{sign}(\theta^{\top}x)$ for binary tasks. We consider both binary and multi-class classification. We also focus on indiscriminate attacks (Barreno et al., 2010), where the test data $\mathcal{D}_{\text{test}}$ is drawn from the same distribution as the clean training data $\mathcal{D}_{\text{c}}$, and the attacker tries to increase the average test error of the defender’s model under this underlying data distribution. In Section 6.1, we show that the attacker can still construct strong indiscriminate attacks even when they do not know the test data $\mathcal{D}_{\text{test}}$. Most of our methods are also applicable to more general choices of $\mathcal{D}_{\text{test}}$; we discuss this further in Section 7.

2 Data sanitization defenses

To thwart the attacker, we assume the defender employs a data sanitization defense (Cretu et al., 2008), which first removes anomalous-looking points from $\mathcal{D}=\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}}$ and then trains on the remaining points. The motivation is that intuitively, poisoned data that looks similar to the clean data will not be effective in changing the learned model; therefore, the attacker would want to place poisoned points that are somehow different from the clean data. By discarding points that look too different (anomalous), the defender can thus protect itself against attack. Ideally—as in the hypothetical Figure 1—a defense would discard the poisoned data $\mathcal{D}_{\text{p}}$ and leave the clean data $\mathcal{D}_{\text{c}}$, so that the defender learns model parameters $\hat{\theta}$ that have low test error.

Fits the anomaly detector parameters $\beta=B(\mathcal{D})$, where $B$ is a function that takes in a dataset and returns a vector.

Constructs the feasible set $\mathcal{F}_{\beta}=\{(x,y):(x,y)\in\mathcal{X}\times\mathcal{Y}\text{ with }s_{\beta}(x,y)<\tau_{y}\}$. The threshold $\tau_{y}$ is chosen such that a desired fraction of points from each class are discarded.

Forms the sanitized training dataset $\mathcal{D}_{\text{san}}=\mathcal{D}\cap\mathcal{F}_{\beta}$ by discarding all points that fall outside the feasible set.

Finds the $\hat{\theta}$ that minimizes the regularized training loss on $\mathcal{D}_{\text{san}}$:

We consider 5 different defenses that span existing approaches to data sanitization and anomaly detection:

The L2 defense removes points far from their class centroids in $L_{2}$ distance:

The slab defense (Steinhardt et al., 2017) projects points onto the line between the class centroids, then removes points too far from the centroids:

The idea is to use only the relevant dimensions in feature space to find outliers. The L2 defense treats all dimensions equally, whereas the slab defense treats the vector between the class centroids as the only relevant dimension.

The loss defense discards points that are not well fit by a model trained (without any data sanitization) on the full dataset $\mathcal{D}$:

It is similar to the trimmed loss defense proposed in the context of regression in Jagielski et al. (2018). For a linear model, it is similar to the slab defense, except that the relevant dimension is learned using the loss function instead of being fixed as the direction between the class centroids.

The SVD defense assumes that the clean data lies in some low-rank subspace, and that poisoned data therefore will have a large component out of this subspace (Rubinstein et al., 2009). Let $X$ be the data matrix, with the $i$-th row containing $x_{i}$, the features of the $i$-th training point. Then:

In our experiments, we choose the smallest $k$ such that the normalized Frobenius approximation error (i.e., the normalized sum of the squared singular values) is <0.05.

The k-NN defense removes points that are far from their $k$ nearest neighbors (e.g., Frederickson et al. (2018)).

Note that $\beta$ is sometimes a simple set of summary statistics of the dataset (e.g., in the L2 and slab defenses), while at other times $\beta$ can be the entire dataset (e.g., in the k-NN defense). We will handle these two types of defenses separately, as we discuss in Section 3.

The feasible set $\mathcal{F}_{\beta}$ encodes both the defenses and the input constraints of the dataset, since $\mathcal{F}_{\beta}\subseteq\mathcal{X}\times\mathcal{Y}$ and the input domain $\mathcal{X}$ only includes valid points. Thus, the defender will eliminate all input points that do not obey the input constraints of the dataset.

Attack Framework

In this paper, we take on the role of the attacker. Recall that we are given a set of $n$ clean training points $\mathcal{D}_{\text{c}}$ and a test set $\mathcal{D}_{\text{test}}$, and our goal is to come up with a set of $\epsilon n$ poisoned training points $\mathcal{D}_{\text{p}}$ such that a defender following the procedure in Section 2.2 will choose model parameters $\hat{\theta}$ that incur high test error $\mathcal{L}(\hat{\theta})$. The difficulty lies in choosing poisoned points $\mathcal{D}_{\text{p}}$ that will both lead to high test error and also avoid being flagged as anomalous.

In this section, we describe our general approach to crafting attacks that can evade anomaly detectors. As mentioned in Section 1, we can roughly group anomaly detectors into two categories: those that are more sensitive to the data and tend to ‘overfit’ (like the k-NN defense), and those that are less sensitive to the data and tend to ‘underfit’ because they make strong parametric assumptions (like the L2 defense). In Section 3.1, we discuss how we can use concentrated attacks to evade defenses in the first group. In Section 3.2, we formulate the constrained optimization problem that we use to evade defenses in the second group. Finally, in Section 3.3, we introduce a randomized rounding procedure to handle problem settings where the input features are constrained to be integers.

To bypass anomaly detectors that are sensitive to small changes in the data, we rely on the simple observation that poisoned data that is concentrated on a few locations tends to appear normal to anomaly detectors. For example:

For the k-NN defense and other similar nonparametric detectors, this is trivially true: if several poisoned points are placed very near each other, then by definition, the distances to their nearest neighbors will be small.

For the SVD defense, it is more likely that the low-rank representation of $\mathcal{D}$ will include the poisoned points, reducing their out-of-projection components.

For the loss defense, if the poisoned points are concentrated in a similar location, the model will have more incentive to fit those points (because fitting one of them would imply fitting all of them, which would reduce the training loss more than fitting a single isolated point).

A potential issue for the attacker is that being constrained to place points in concentrated groups might make the attack less effective, in the sense of requiring more poisoned points to make the defender learn some target parameters. For example, it might be the case that a more efficient attack would involve spreading out each poisoned point throughout the feasible set.

Fortunately for the attacker, we show that if the feasible sets for each class are convex, and if the defender is using a 2-class SVM or logistic regression model, then the above scenario will not occur. Instead, we would only need two distinct points (one per class) to realize any attack:

We defer the full proof to Appendix A. As a short proof sketch, the proof consists of two parts. We first relate the number of distinct points necessary to achieve an attack to the geometry of the set of gradients of points within the feasible set, using the notion of Carathéodory numbers from convex geometry. We then show, for the specific losses considered above (the hinge and logistic loss), that this set of feasible gradients has the necessary geometry. Our method is general and can be extended to different loss functions and feasible sets; we provide one such extension, to a multi-class SVM setting, in Appendix A.

One objection to attacks with only two distinct poisoned points is that they can be easily defeated by a defender that throws out repeated points. However, the attacker can add a small amount of random noise to fuzz up poisoned points without sacrificing the concentrated nature of the attack. Randomized rounding, which we use to handle datasets with integer input constraints in Section 3.3, is a version of this procedure.

2 Constrained optimization

Anomaly detectors that are more robust to small changes in the training data, such as those that rely on simple sufficient statistics of the data, tend to be less vulnerable to concentrated attacks. In our setting, the L2 and slab defenses in particular are not fooled by concentrated attacks: the class centroid, which is used in both defenses, cannot be moved too much by an $\epsilon$ fraction of poisoned points if $\epsilon$ is small and the clean training data $\mathcal{D}_{\text{c}}$ is well-clustered, since poisoned points that are too far away would be filtered out by the L2 defense.

To handle these defenses, we formulate the attacker’s goal as a constrained optimization problem:

The first constraint corresponds to the attacker only being able to add in an $\epsilon$ fraction of poisoned points; the second constraint corresponds to the defender fitting the anomaly detector on the entire training set $\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}}$; and the final equality corresponds to the defender learning model parameters $\hat{\theta}$ that minimize training loss.

To make this problem more tractable, we make three approximations:

We assume that the defender does not discard any clean points. Thus, if all poisoned points are constrained to lie within the feasible set $\mathcal{F}_{\beta}$ and therefore evade sanitization, then the defender trains on the entirety of $\mathcal{D}=\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}}$.This favors the defender, since we do not consider the case in which a savvy attacker might place poisoned points in such a way as to cause the defender to throw out particularly good points in $\mathcal{D}_{\text{c}}$ and therefore learn a bad model.

We break the dependence of the feasible set $\mathcal{F}_{\beta}$ on the poisoned data $\mathcal{D}_{\text{p}}$ by fixing the anomaly detector $\beta=B(\mathcal{D}_{\text{c}})$ on the clean data. This is a reasonable approximation for the L2 and slab defenses, as their feasible sets depend only on the class centroids, which are very stable with respect to small amounts of poisoned data $\mathcal{D}_{\text{p}}$.

These approximations let us rewrite the attacker’s goal as the following optimization problem:

This constrained optimization formulation has been used in prior work (e.g., Steinhardt et al. (2017)), and despite the approximations, it is still a bilevel problem that is non-convex and intractable to solve exactly (Bard, 1991, 1999). Our contribution in this regard is developing more effective and computationally efficient ways of solving it, which will be the focus of Section 4.

Instead of fixing the feasible set based on only the clean data, $\beta=B(\mathcal{D}_{\text{c}})$, we can also adopt an iterative optimization approach, where we alternate between optimizing over $\mathcal{D}_{\text{p}}$ for a fixed $\beta$, and then updating $\beta$ to reflect the new $\mathcal{D}_{\text{p}}$ (Algorithm 1). This iterative optimization procedure is guaranteed to make progress so long as the poisoned points $\mathcal{D}_{\text{p}}$ remain valid even after re-fitting $\beta$. In Section 5.4, we show that this slightly improves the attacks obtained, though it is not necessary to obtain effective attacks.

3 Handling integer input constraints with randomized rounding

Each of the three data poisoning attacks that we will develop use some form of gradient descent on the poisoned points to solve the attacker’s optimization problem (4). However, gradient descent cannot be directly applied in settings where the input features are constrained to be non-negative integers (e.g., with bag-of-word models in natural language tasks).

To handle this, Steinhardt et al. (2017) relaxed the integrality constraint to allow non-negative real-valued points, and then performed randomized rounding on these real-valued points to obtain integer-valued points:

Solve the optimization problem (4) while allowing all poisoned points $(x,y)\in\mathcal{D}_{\text{p}}$ to have real-valued $x$.

However, this approach can produce poisoned points that get detected by data sanitization defenses. We adopt their approach but introduce two techniques to avoid detection:

While the function $f(x)\stackrel{{\scriptstyle\rm def}}{{=}}x(\lceil x\rceil+\lfloor x\rfloor)-\lceil x\rceil\lfloor x\rfloor$ looks complicated, intuitively, we expect $f(x)$ to be close to $x^{2}$. Indeed, as Figure 2 shows, it is a piecewise-linear function where the $k$-th piece linearly interpolates between $k^{2}$ and $(k+1)^{2}$, and we can write it as the maximum over a set of linear equations:

Thus, when solving the attacker optimization (equation (4)) for datasets with non-negative integer constraints, we replace the standard L2 feasible set $\mathcal{F}_{\beta}=\{(x,y):\|x-\mu_{y}\|_{2}\leq\tau_{2}\text{ and }x\in\mathbf{R}_{\geq 0}\}$ with the modified constraint set

Randomized rounding has some negative impact: it makes attacks less concentrated, as discussed above, and can also result in a few unlucky poisoned points getting filtered by other defenses (e.g., by the loss defense if the rounding happens to increase the loss on the point). Another advantage of the above LP relaxation is that in practice, the linear constraints tend to lead to nearly-integer $x$, which further reduces the negative impact of having to do randomized rounding.

Specific Attacks

In this section, we introduce three different methods for efficiently solving the attacker’s optimization problem (Equation (4)) and generating an attack. As discussed in Section 3, these methods all generate concentrated attacks within our constrained optimization framework and use the randomized rounding procedure when necessary. We start with the influence attack in Section 4.1, which is direct but computationally slower, and then introduce the KKT and min-max attacks in Sections 4.2 and 4.3, which both use the idea of decoy parameters to speed up the attack.

Recall that solving Equation (4) involves finding poisoned data $\mathcal{D}_{\text{p}}$ that maximizes the defender’s test loss $L(\hat{\theta};\mathcal{D}_{\text{test}})$ for a fixed feasible set $\mathcal{F}_{\beta}$. The influence attack tackles this problem via projected gradient ascent.

At a high level, we can find a local maximum of Equation (4) by iteratively taking gradient steps on the features of each poisoned point in $\mathcal{D}_{\text{p}}$, projecting each point onto the feasible set $\mathcal{F}_{\beta}$ after each iteration. This type of gradient-based data poisoning attack was first studied in the context of SVMs by Biggio et al. (2012b), and has subsequently been extended to linear and logistic regression (Mei and Zhu, 2015b), topic modeling (Mei and Zhu, 2015a), collaborative filtering (Li et al., 2016), and neural networks (Koh and Liang, 2017; Yang et al., 2017; Muñoz-González et al., 2017). We call this projected gradient ascent method the influence attack after Koh and Liang (2017), who use influence functions to compute this gradient. Our method builds upon previous work by incorporating the techniques mentioned in Section 3—concentrating the attack and using randomized rounding with the LP relaxation.

The quantity $\frac{\partial L}{\partial\hat{\theta}}$ is the average gradient of the test loss, which we denote as $g_{\hat{\theta},\mathcal{D}_{\text{test}}}$ for convenience, and it can be computed straightforwardly as

where $H_{\hat{\theta}}$ is the Hessian of the training loss at $\hat{\theta}$:

1.2 Improvements to the basic algorithm

However, even after these improvements, the influence attack is slow especially in high dimensions: each iteration of gradient descent requires computing an expensive inverse Hessian-vector product (10) and a projection onto the feasible set. Moreover, the influence attack relies on local optimization and can sometimes get stuck in poor local minima, even when the underlying model loss is convex. To mitigate these shortcomings, we propose the KKT attack, which we discuss next.

2 The KKT attack

The KKT attack is based on the observation that the attacker’s optimization problem (4) is difficult to solve because the optimization variable $\mathcal{D}_{\text{p}}$ only affects the objective (test loss $L(\hat{\theta};\mathcal{D}_{\text{test}})$) through the model parameters $\hat{\theta}$, which are themselves a complicated function of $\mathcal{D}_{\text{p}}$. In general, we do not know what $\hat{\theta}$ would lead to an attack that is both effective and realizable; but if we did know which $\hat{\theta}$ we were after, then the attacker’s optimization problem simplifies to finding $\mathcal{D}_{\text{p}}$ such that $\hat{\theta}=\operatorname*{argmin}_{\theta}L(\theta;\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$. As we will show in this section, this simplified problem can be solved much more efficiently than the original bilevel problem.

Using fast heuristics to find decoy parameters $\theta_{\text{decoy}}$ that we want the defender to learn, and then

Finding poisoned data $\mathcal{D}_{\text{p}}$ that tricks the defender into learning those decoy parameters $\theta_{\text{decoy}}$.

The name of this attack comes from the use of the Karush-Kuhn-Tucker (KKT) first-order necessary conditions for optimality in the second step.

Good decoy parameters, from the perspective of the attacker, should have high test error while still being achievable by some poisoned data $\mathcal{D}_{\text{p}}$. Decoy parameters that have a high loss on the clean data $\mathcal{D}_{\text{c}}$ are unlikely to be achievable by an $\epsilon$ fraction of poisoned data $\mathcal{D}_{\text{p}}$, since it is likely that there exist other parameters that would have a lower training loss on the combined data $\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}}$ and would therefore be learned instead by the defender.

Our heuristic is to augment the clean data $\mathcal{D}_{\text{c}}$ with a dataset $\mathcal{D}_{\text{flip}}$ comprising label-flipped examples from $\mathcal{D}_{\text{test}}$, and then find the parameters $\theta_{\text{decoy}}$ that minimize the training loss on this modified training set $\mathcal{D}_{\text{decoy}}=\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{flip}}$ (Algorithm 3). The idea is that since the decoy parameters $\theta_{\text{decoy}}$ were trained on $\mathcal{D}_{\text{decoy}}$, which incorporates flipped points from $\mathcal{D}_{\text{test}}$, it might achieve high test loss. At the same time, the following informal argument suggests that on the clean data $\mathcal{D}_{\text{c}}$, the decoy parameters $\theta_{\text{decoy}}$ are likely to be not much worse than the optimal parameters for the clean data, $\theta_{c}$. By construction,

where the last inequality comes from the non-negativity of the loss $L$. The second term on the right-hand side, $L(\theta_{c};\mathcal{D}_{\text{flip}})$, is likely to be small: $\mathcal{D}_{\text{flip}}$ comprises of points that originally had a high loss under $\theta_{c}$ before their labels were flipped (which implies that their label-flipped versions are likely to have a lower loss), and we can choose $|\mathcal{D}_{\text{flip}}|$ to be small compared to $|\mathcal{D}_{\text{c}}|$. Thus, the average loss $L(\theta_{\text{decoy}};\mathcal{D}_{\text{c}})$ of the decoy parameters $\theta_{\text{decoy}}$ on the clean data $\mathcal{D}_{\text{c}}$ is not likely to be too much higher than $L(\theta_{c};\mathcal{D}_{\text{c}})$, which is the best possible average loss on $\mathcal{D}_{\text{c}}$ within the model family.

By varying the loss threshold $\gamma$ and number of repeats $r$ used in Algorithm 3, we obtain different candidates for $\theta_{\text{decoy}}$. As we will discuss next, finding an attack $\mathcal{D}_{\text{p}}$ for each candidate $\theta_{\text{decoy}}$ is fast, so we simply generate a set of candidate decoy parameters and try all of them, picking the $\theta_{\text{decoy}}$ that achieves the highest test loss.

For given decoy parameters $\theta_{\text{decoy}}$, the next step for the attacker is to find poisoned data $\mathcal{D}_{\text{p}}$ such that $\mathcal{D}_{\text{p}}$ evades data sanitization and $\theta_{\text{decoy}}$ minimizes the overall training loss over both $\mathcal{D}_{\text{p}}$ and the clean data $\mathcal{D}_{\text{c}}$. We can formulate this task as the following optimization problem:

as the equivalent KKT optimality condition

Since the first term in (13) is fixed and does not depend on the optimization variable $\mathcal{D}_{\text{p}}$, we can treat it as a constant:

If this optimization problem (14) has a solution, we can find it by solving the equivalent norm-minimization problem

which moves the KKT constraint into the objective, relying on the fact that the norm of a vector is minimized when the vector is 0.

Defenses like the loss defense have feasible sets that depend on the model parameters $\hat{\theta}$ that the defender learns, which in turn depend on the poisoned points. This dependence makes it difficult for the attacker to explicitly constrain their poisoned points to lie within such feasible sets. In the influence attack, we relied on concentrated attacks (Section 3.1) to evade the loss defense. This approach is empirically effective, but it relies to some extent on luck, as the attacker cannot guarantee that its poisoned points will have low loss.

3 Improved Min-Max Attack

Our third and final attack is the min-max attack, which improves on what we call the min-max-basic attack from prior work (Steinhardt et al., 2017). The min-max attack relies on the same decoy parameters introduced in Section 4.2, but unlike the influence and KKT attacks, it naturally handles multi-class problems without a grid search, and it does not require convexity of the feasible set. Its drawback is assuming that the clean data $\mathcal{D}_{\text{c}}$ and the test data $\mathcal{D}_{\text{test}}$ are drawn from the same distribution (i.e., that the attacker is performing an indiscriminate attack; see Sections 2 and 7).

We start by reviewing the min-max-basic attack, as it was introduced in Steinhardt et al. (2017). Recall that the attacker’s goal is to find poisoned points $\mathcal{D}_{\text{p}}$ that maximize the test loss $L(\hat{\theta};\mathcal{D}_{\text{test}})$ that the defender incurs, where the parameters $\hat{\theta}$ are chosen to minimize the training loss $L(\hat{\theta};\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$ (equation (4)). As we discussed in Sections 3.2, 4.1, and 4.2, the bilevel nature of this optimization problem—maximizing the loss involves an inner minimization to find the parameters $\hat{\theta}$—makes it difficult to solve.

The key insight in Steinhardt et al. (2017) was that we can make this problem tractable by replacing the test loss $L(\hat{\theta};\mathcal{D}_{\text{test}})$ with the training loss $L(\hat{\theta};\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$. This substitution changes the bilevel problem into a saddle-point problem—i.e., one that can be expressed in the form $\min_{u}\max_{v}f(u,v)$— that can be solved efficiently via gradient descent.

To do so, we first approximate the average test loss with the average clean training loss:

This approximation only works in the setting where the test data $\mathcal{D}_{\text{test}}$ is drawn from the same distribution as the (clean) training data $\mathcal{D}_{\text{c}}$, and relies on the training set being sufficiently big and the model being appropriately regularized, such that test loss is similar to training loss. Next, we make use of the non-negativity of the loss to upper bound the average clean training loss with the average combined loss on the clean and poisoned data:

where, as usual, $\epsilon$ is the relative ratio of poisoned points $\epsilon=\frac{|\mathcal{D}_{\text{p}}|}{|\mathcal{D}_{\text{c}}|}$.

By combining (18) and (19), we can approximately upper-bound the average test loss $L(\theta;\mathcal{D}_{\text{test}})$ by $(1+\epsilon)$ times the average loss on the combined training data $L(\theta;\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$. Instead of directly optimizing for $L(\theta;\mathcal{D}_{\text{test}})$ as the attacker (equation (4)), we can therefore optimize for $L(\theta;\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$, which gives us

The advantage of this formulation is that the outer maximization and inner minimization are over the same function $L(\theta;\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$, which lets us rewrite it as the saddle-point problem

This algorithm automatically handles class balance, since at each iteration it chooses to add either a positive or negative point; it can thus handle multi-class attacks without additional difficulty, unlike the KKT or influence attacks. Moreover, unlike the influence attack, it avoids solving the expensive bilevel optimization problem.

3.2 Improvements to the basic algorithm

We improve the min-max-basic attack by incorporating the decoy parameters introduced in Section 4.2 (Algorithm 3). The problem with the min-max-basic attack, which repeatedly adds the highest-loss point that lies in the feasible set $\mathcal{F}_{\beta}$, is that at low $\epsilon$, the attack might end up picking poisoned points $\mathcal{D}_{\text{p}}$ that are not fit well by the model, i.e., with high $L(\hat{\theta};\mathcal{D}_{\text{p}})$. These points could still lead to a high combined loss $L(\hat{\theta};\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$, but such an attack would be ineffective for two reasons:

If the poisoned points have high loss compared to the clean points, they are likely to be filtered by the loss defense.

Even if the poisoned points are not filtered out, the loss on the clean data $L(\hat{\theta};\mathcal{D}_{\text{c}})$ might still be low, implying that the test loss would also be low. Such a scenario could happen if there is no model that fits both the poisoned points $\mathcal{D}_{\text{p}}$ and the clean points $\mathcal{D}_{\text{c}}$ well; since $\epsilon$ is small, overall training loss could then be minimized by fitting $\mathcal{D}_{\text{c}}$ well at the expense of $\mathcal{D}_{\text{p}}$.

We therefore want to keep the loss on the poisoned points, $L(\hat{\theta};\mathcal{D}_{\text{p}})$, small. To do so, we use the decoy parameters $\theta_{\text{decoy}}$ from Section 4.2 (Algorithm 3), augmenting the feasible set $\mathcal{F}_{\beta}$ with the constraint

If the learned parameters are driven towards $\theta_{\text{decoy}}$, the poisoned points in $\mathcal{D}_{\text{p}}$ will have low loss due to the constraint (22), and hence will not get filtered by the loss defense.

Adding poisoned points with high loss under the current parameters but low loss under the decoy parameters $\theta_{\text{decoy}}$ is likely to drive the learned parameters towards $\theta_{\text{decoy}}$. In turn, this will increase the test loss, since $\theta_{\text{decoy}}$ is chosen to have high test loss Section 4.2.1.

We find that empirically, the min-max-basic attack naturally yields attacks that are quite concentrated. For datasets with integer input constraints, we additionally use the linear programming relaxation and repeated points heuristic (Section 3.3). Altogether, these changes to the min-max-basic attack yield what we call the min-max attack.

Experiments: Attackers with complete information

Our experiments focus on two binary classification datasets. Summaries of each dataset are given in Table 1, including the number of training points $n$, the dimension of each point $d$, and the base accuracy of an SVM trained only on the clean data.

The Enron spam classification text dataset (Metsis et al., 2006), which requires input to be non-negative and integer valued, as each feature represents word frequency. The Enron dataset has $n\approx d$ and a relatively low base error of 3.0%.

The IMDB sentiment classification text dataset (Maas et al., 2011), which similarly requires input to be non-negative and integer valued. Compared to the other datasets, the IMDB dataset has significantly larger $n$ and $d$, presenting computational challenges. It also has $n\ll d$ and is not as linearly separable, with a high base error of 11.9%.

In addition, we use the standard 10-class MNIST dataset (LeCun et al., 1998) as an illustration of a multi-class setting.

These datasets are considered in Steinhardt et al. (2017), which also studied data poisoning. In Appendix C, we also consider experiments on the other two datasets studied in that work: MNIST-1-7, a binary version of MNIST (LeCun et al., 1998), and Dogfish (Koh and Liang, 2017). These datasets were shown by Steinhardt et al. (2017) to have some certificates of defensibility using the L2 and slab defenses, and indeed, our attacks were not as effective on them as they were for the other datasets above.

2 Setup

We used the non-iterative version of Algorithm 1 to carry out the data poisoning attacks. We assumed that the attacker has limited control over the training data: in our experiments, we allowed the attacker to only add up to $\epsilon=3\%$ poisoned data, and we set the data sanitization threshold $\tau$ such that the defender removes $p=5\%$ of the training data from each class after training its anomaly detector on the combined clean and poisoned dataset $\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}}$.

As the attacker’s goal is to increase test error regardless of which defense is deployed against it, we evaluated an attack $\mathcal{D}_{\text{p}}$ by running each of the 5 defenses in Section 2.2 separately against it, and measuring the minimum increase in test error it achieves over all of the defenses.

We optimized each attack against all of the defenses. Specifically, for the influence attack, we took the feasible set $\mathcal{F}_{\beta}$ to be the intersection of the feasible sets under the L2 and slab defenses, plus any additional input constraints that each dataset imposed. For the KKT and min-max attacks, we used the decoy parameters to expand the feasible set $\mathcal{F}_{\beta}$ to incorporate the loss defense as well. We relied on concentrated attacks to evade the remaining defenses.

3 Comparing attacks on Enron and IMDB

We tested all three attacks on the Enron spam classification dataset, and the KKT and min-max attack on the IMDB sentiment classification dataset (which was too large to run the influence attack on). All of the attacks were successful, with the KKT and min-max attack achieving slightly higher test error than the influence attack on the Enron dataset (Figure 3-Left). As each defense is evaluated separately against the attack, we plot a bar for each defense. However, our attacks are constructed to avoid all of the defenses; this simulates the fact that the attacker might not know which defense will be deployed ahead of time, and therefore strives to evade all of them.

For the KKT and min-max attacks, successful attacks did not need to exactly reach the decoy parameters; in fact, trying to get to ambitious (i.e., high test error but unattainable) decoy parameters could sometimes outperform exactly reaching unambitious decoy parameters. (Of course, the ideal choice of decoy parameters would have high test error but also be attainable.)

We measured the speed of each attack against the Enron dataset by running them each on 2 cores of an Intel Xeon E5 processor. Additionally, the influence attack used a GeForce GTX Titan X for GPU-based calculations. Despite not using a GPU, the KKT and min-max attacks were significantly faster: while the influence attack took 286 minutes to reach 17% error, the KKT attack only took 27 seconds (Figure 4). The min-max attack took 28 minutes to process its first decoy parameter, which gave 23.0% error. The main computational bottleneck for the influence attack is the inverse Hessian-vector product calculation in Equation (10). In contrast, the other two attacks solve convex subproblems (as opposed to the non-convex problem that the influence attack is doing gradient descent on) and admit more efficient general-purpose convex optimization solvers.

4 Iterative optimization

The above experiments simply fix the feasible set $\mathcal{F}_{\beta}$ based on the clean training data, as described in Section 3.2. To study the effect of refining the attacks by iteratively $\mathcal{F}_{\beta}$ (Algorithm 1), we ran an iterative version of the influence attack against the Enron dataset. Figure 5 shows that iterative optimization does only slightly better: at the low levels of $\epsilon$ that we chose, the attack does not shift the centroids of the data that much, and therefore the feasible set $\mathcal{F}_{\beta}$ for both the L2 and slab defenses stay somewhat constant.

One perspective on iterative optimization in our setting is that it is targeting the slab defense by trying to rotate the vector between the two class centroids; as Steinhardt et al. (2017) show, at large $\epsilon$ (e.g., $\epsilon=0.3$, which is 10 times larger than what we consider), this vector can be significantly changed by the poisoned points, whereas the ${L2}{}$ feasible set is harder to perturb. Note that our influence attacks on MNIST-1-7 at high $\epsilon$ are considerably weaker than the attacks in Steinhardt et al. (2017), which uses a specialized semi-definite program that relies on poisoning the anomaly detector (i.e., placing poisoned points to move the class centroids in a way that renders the slab defense ineffective). They achieve an increase in test error of 39% for $\epsilon=0.3$. The high-$\epsilon$ setting is not our focus in this paper, since it is less realistic; this performance gap could be a result of poor step size tuning or initialization on our part, or it could signify a weakness in the applicability of iterative optimization and/or gradient descent to the high-$\epsilon$ setting. On the Enron dataset and at the low $\epsilon$ settings that we consider, the slab defense only decreases test error by a few percentage points, so iterative optimization only increases test loss by a few percentage points. To illustrate this point, we ran an attack with $\epsilon=0.3$ on the MNIST-1-7 dataset: the influence attack without iterative optimization achieved an increase in test error of only 1.1%, while the influence attack with iterative optimization achieved a larger increase in test error of 7.5%.

5 Ablations for the influence attack

We studied the effect of the two improvements made to the influence-basic attack—the linear programming (LP) relaxation and the concentration of the attack—on the Enron dataset. Removing the linear programming (LP) relaxation decreased the achieved test error by a few percentage points (Figure 6-Left versus Mid). Further removing the concentrated attack decreased test error substantially (Figure 6-Right). The influence-basic attack is still optimized to evade the L2 and slab defenses, but because its poisoned points are not concentrated, many of them get filtered out by the loss and SVD defenses. Consequently, it does not manage to increase test error beyond 11% under those defenses.

6 Ablations for the min-max attack

To measure the effect of using decoy parameters in the min-max attack, we ran the min-max-basic attack from Steinhardt et al. (2017), augmented with the linear programming relaxation and repeated points heuristic. (The unaugmented version of the min-max-basic attack from Steinhardt et al. (2017) performs worse.) In contrast to the min-max attack, the min-max-basic attack gets defeated by the loss defense (test error 10.0%, Figure 7). As discussed in Section 4.3.2, without the constraints imposed by the decoy parameters, the poisoned points found by the min-max-basic attack have high loss and consequently get filtered out by the loss defense.

7 Attacks on multi-class tasks with the min-max attack on MNIST

We illustrate a multi-class attack by running the min-max attack on the 10-class MNIST dataset (LeCun et al., 1998). Using $\epsilon=3\%$ poisoned data, the min-max attack obtains 15.2% test error against the L2 defense and 13.7% test error against the loss defense, demonstrating a high-leverage attack in a multi-class setting.

Experiments: Attackers with incomplete information

In Section 5, we saw that the influence, KKT, and min-max attacks are effective if the attacker has complete information about the model and defenses. In this section, we study transferability—are these attacks still effective when the attacker does not have complete information about the defender? Specifically, we use the Enron dataset to explore what happens when the attacker does not have knowledge of 1) the test set (i.e., they only see the train set); 2) the amount of regularization that the defender uses; 3) their optimization algorithm; and 4) their loss function.

In general, our attacks are still effective under these changes, with the min-max attack generally being the most robust and the influence attack being the least. However, the loss defense poses problems for all three attacks when the optimization algorithm or the loss function are changed, suggesting that attackers should set conservative thresholds against the loss defense.

An attacker might not have specific test examples in mind; for example, they might aim to make the defender incur high expected loss on test points from the same distribution as the training set. For such an attacker, optimizing for some test data $\mathcal{D}_{\text{test}}$ might not translate into an effective attack on a different sample of test data. We tested if our attacks would still be effective if the attacker only knew the clean training data $\mathcal{D}_{\text{c}}$ but not the test data $\mathcal{D}_{\text{test}}$. A different setting is if the attacker knows the test data $\mathcal{D}_{\text{test}}$ but not the clean training data $\mathcal{D}_{\text{c}}$. For example, the attacker might only have access to a similarly distributed but distinct dataset $\mathcal{D}_{\text{c}}^{\prime}$. As our attacks depend on the clean training data primarily through the average gradient of the loss computed over $\mathcal{D}_{\text{c}}$, we expect that swapping $\mathcal{D}_{\text{c}}$ with $\mathcal{D}_{\text{c}}^{\prime}$ should not matter for sufficiently large training sets. Specifically, we generated attacks by simply using $\mathcal{D}_{\text{c}}$ in place of $\mathcal{D}_{\text{test}}$ (i.e., we optimized for high error on the training data $\mathcal{D}_{\text{c}}$).

Figure 9 shows the test error that the resulting attacks incurred on $\mathcal{D}_{\text{test}}$, compared with attacks that assume knowledge of $\mathcal{D}_{\text{test}}$, as used in the rest of the paper. Overall, the attacks still significantly increase test error even without knowing $\mathcal{D}_{\text{test}}$. However, the influence attack is comparatively less effective when the test dataset is not known (reaching 10.9% test error instead of 18.3% test error). In contrast, the KKT (16.5% vs. 22.6% test error) and min-max attacks (19.0% vs 23.7% test error) are more robust to using the training data in place of the test data. These results suggest that the influence attack, which explicitly optimizes for loss on the test set, overfits more strongly to the test set compared to the KKT and min-max attacks, which rely on the test set mainly through the construction of decoy parameters.

A variant of the above setting is when the attacker does not know the exact test data $\mathcal{D}_{\text{test}}$ but nonetheless has access to some validation data $\mathcal{D}_{\text{val}}$ from the same distribution, as well as the training data $\mathcal{D}_{\text{c}}$. In this setting, the attacker could optimize an attack against $\mathcal{D}_{\text{val}}$; we expect that doing so will result in an attack that is more effective than optimizing against the training data $\mathcal{D}_{\text{c}}$, as we do above, though still slightly less effective than optimizing against $\mathcal{D}_{\text{test}}$ itself.

2 Regularization

Do attacks that are optimized for one level of regularization still work well at other levels of regularization? Recall that the defender uses $L_{2}$ regularization with the hyperparameter $\lambda$ controlling the amount of regularization (Equation (2)); in particular, we use $\lambda=0.09$ for the Enron dataset (Table 1). To test the effect of the defender’s choice of $\lambda$, we varied it from $0.009$ to $0.9$ while keeping the attacker’s $\lambda$ constant at $0.09$. Figure 10 shows the results:

Against the L2 defense, test error generally increased with $L_{2}$ regularization strength (Figure 10-Left). The L2 feasible set depends only on the location of the poisoned points and not on the model parameters that the defender learns. Thus, the test error changes because the defender learns a different set of parameters given exactly the same set of poisoned points, and not because a different set of poisoned points get filtered out by the defenses.

The amount of regularization had different effects on each attack’s effectiveness against the L2 defense. The influence attack became less effective as we reduced defender regularization ($<10\%$ test error against the L2 defense at $\lambda=0.009$), while the min-max attack was robust to changes in defender regularization ($22\%$ test error at $\lambda=0.009$).

Increasing regularization can make the loss defense more effective (Figure 10-Right). The loss feasible set is sensitive to changes in the model parameters that the defender learns, so some poisoned points that evaded this defense under the original model (with $\lambda=0.09$) are now detected under the changed model.

Unlike the other attacks, the min-max attack initially gets more effective against the loss defense as defender regularization is increased from $\lambda=0.09$. We suspect that this is due to the min-max attack using a fixed loss threshold $\tau$ (see equation (22) in Section 4.3.2) that is more conservative than the KKT attack (which uses an adaptive threshold based on the quantiles of the loss under the decoy parameters) and the influence attack (which solely relies on concentrated attacks to overcome the loss defense).

These results imply that attackers should optimize for lower levels of regularization, in case the defender uses a lower level (and conversely, it suggests that defenders might want to use lower levels of regularization than they might otherwise). Attackers using decoy parameters might also decide to set their loss thresholds more conservatively.

These results also suggest that the data poisoning attacks are not exploiting overfitting. If that were the case, we would expect increasing regularization to decrease overfitting and thus reduce attack effectiveness. Instead, we observe the opposite: the defender generally suffers when increasing regularizatio, as it is harder for the defender’s model to fit both the poisoned training points and clean training points well, and if the clean training points are not fit well, the test error will consequently increase.

We note that Demontis et al. (2019) studied the transferability of gradient-based data poisoning attacks for image recognition and found that attacks were more effective when the defender used less regularization. The differences from our work is that they assumed that there are no defenses (i.e., the only constraint on the attacker is to generate a valid image) and that there are a small number of training points relative to dimension (e.g., $n=500$ for a binary MNIST classification problem).

3 Optimization and loss function

In our previous experiments, we assumed that the defender would learn the model parameters $\hat{\theta}$ that globally minimized training loss. In practice, defenders might use stochastic optimization and/or early stopping, leading to parameters $\hat{\theta}$ that are close to but not exactly at the optimum.

Figure 11-Left shows the results of our attacks on a defender that learned a model by doing a single pass of stochastic gradient descent over the dataset (i.e., each sample is looked at exactly once). We also tested how an attacker using the hinge loss would fare against a defender who uses the logistic loss (Figure 11-Right). All three attacks stayed effective against all of the defenses except the loss defense, which managed to significantly reduce the damage inflicted by the attacker.

As in Section 6.2, these results suggest that attackers should use a conservative loss threshold to harden their attacks against loss-based defenses. It also suggests that the attacker’s ability to evade loss-based defenses is especially sensitive (relative to other defenses) to getting the defender’s model correct.

Related Work

In this section, we discuss other attack settings and defense strategies that have been studied in the literature. For broad surveys on this topic, see e.g., Barreno et al. (2010), Biggio et al. (2014), Gardiner and Nagaraja (2016), Papernot et al. (2016b), and Vorobeychik and Kantarcioglu (2018).

In our experiments, the attacker sought to increase error on a test set $\mathcal{D}_{\text{test}}$ that was drawn from the same distribution as the clean training data $\mathcal{D}_{\text{c}}$. This type of attack is known as an indiscriminate attack (Barreno et al., 2010) and is akin to a denial-of-service attack.

Indiscriminate attacks seek to change the predictions of the learned model on a good fraction of the entire data distribution and therefore require substantial changes to the model. This makes indiscriminate attacks statistically interesting, as they get at fundamental properties of the model: how might an attacker that only controls 1% of the training data bring about a 10% increase in test error?

A different type of attack is a targeted attack, in which the attacker seeks to cause errors on specific test examples or small sub-populations of test examples (Gu et al., 2017; Chen et al., 2017; Burkard and Lagesse, 2017; Koh and Liang, 2017; Shafahi et al., 2018; Suciu et al., 2018). For example, an attacker might seek to have all of the emails that they send marked as non-spam while leaving other emails unaffected; or an attacker might seek to cause a face recognition system to recognize their face as that of a particular victim’s (as in Biggio et al. (2012a) and Biggio et al. (2013), which build off the attacks in Kloft and Laskov (2012)). Targeted attackers only seek to change the predictions of the model on a small number of instances, and therefore might be able to add in 50 poisoned training points to cause an error on a single test point (Shafahi et al., 2018). Targeted attacks are well-motivated from a security perspective: attackers might only care about a subset of the model’s prediction, and targeted attacks require less control over the training set and are therefore easier to carry out.

The influence and KKT attacks in Sections 4.1 and 4.2 do not make any assumptions on the nature of the test set $\mathcal{D}_{\text{test}}$, and can therefore handle the targeted attack setting without modification. In contrast, the min-max attack in Section 4.3 assumes that the training error is a good approximation to the test error, and is thus only appropriate in the indiscriminate attack setting.

A backdoor attack is a targeted attack that seeks to cause examples that contain a specific backdoor pattern, e.g., a bright sticker (Gu et al., 2017) or a particular type of sunglasses (Chen et al., 2017), to be misclassified. Backdoor attacks work by superimposing the chosen backdoor pattern onto particular training examples from a given class, which causes the model to associate the backdoor pattern with that class (and therefore misclassify, at test time, examples of a different class that also contain the backdoor pattern). The attackers in Gu et al. (2017) and Chen et al. (2017) do not need to know the model that the defender is using; in fact, the attacker in Chen et al. (2017) does not even need any knowledge of the training set, instead adding examples from a external dataset. These weaker assumptions on attacker capabilities are common in targeted attacks. In contrast, the indiscriminate attacks that we develop in this paper make use of knowledge of the model and the training set in order to have high leverage.

Clean-label attacks are attacks that “do not require control over the labeling function; the poisoned training data appear to be labeled correctly according to an expert observer” (Shafahi et al., 2018). Not requiring control over labeling makes it easier for the attacker to practically conduct such an attack, as the attacker only needs to introduce the unlabeled poisoned data into the general pool of data (e.g., uploading poisoned images or sending poisoned emails, as Shafahi et al. (2018) discusses) and wait for the defender to label and ingest the poisoned data.

Our attacks are not clean-label attacks, in that the poisoned points will not necessarily be labeled as the correct class by a human expert. On the other hand, our poisoned points are designed to evade detection by automatic outlier detectors; note that “clean-label” points can fool human experts but still look like statistical outliers.

The bulk of recent research in machine learning security has focused on test-time attacks, where the attacker perturbs the test example to obtain a desired classification, leaving the training data and the model unchanged. This line of research was sparked by the striking discovery that test images could be perturbed in a visually-imperceptible way and yet fool state-of-the-art neural network image classifiers (Szegedy et al., 2014; Goodfellow et al., 2015; Carlini et al., 2016; Kurakin et al., 2016; Papernot et al., 2016a, 2017; Moosavi-Dezfooli et al., 2016). Designing models that are robust to such attacks, as well as coming up with more effective attacks, is an active area of research (Papernot et al., 2016c; Madry et al., 2017; Tramèr et al., 2017; Wong and Kolter, 2018; Raghunathan et al., 2018; Sinha et al., 2018; Athalye et al., 2018; Papernot and McDaniel, 2018).

In contrast to these test-time attacks, data poisoning attacks are train-time attacks: the attacker leaves the test example unchanged, and instead perturbs the training data so as to affect the learned model. Data poisoning is less well-studied, and compared to test-time attacks, it is harder to both attack and defend in the data poisoning setting: data poisoning attacks have to depend on the entire training set, whereas test-time attacks only depend on the learned parameters; and common defense techniques against test-time attacks, such as ’adversarial training’ (Goodfellow et al., 2015), do not have analogues in the data poisoning setting.

2 Defenses

In the literature, effective defenses typically require additional information than the defenders we consider in this paper, e.g., having a labeled set of outliers or having a trusted dataset.

If the defender has access to data that has been labeled as ‘normal’ vs. ‘outlier’, then outlier detection can be treated as a standard supervised classification problem (Hodge and Austin, 2004). For example, an online retailer might have a set of transactions that had been previously labeled as fraudulent, and could train a separate outlier detection model to detect and throw out other fraudulent-looking transactions from the dataset. One drawback is that in an adversarial setting there is no assumption that future poisoned points might look like previous poisoned points. Such methods are therefore more suited for detecting outliers caused by natural noise processes rather than adversaries.

Instead of directly using ‘normal’ vs. ‘outlier’ labels, defenders can instead rely on other types of training metadata. For example, Cretu et al. (2008)—which introduced the term ‘data sanitization’ in the context of machine learning—uses information on the time at which each training point was added to the training set. The intuition is that “in a training set spanning a sufficiently large time interval, an attack or an abnormality will appear only in small and relatively confined time intervals” (Cretu et al., 2008).

Other defense methods rely on having a trusted subset $\mathcal{T}$ of the training data that only contains clean data (obtained for example by human curation). One example is the Reject on Negative Impact (RONI) defense proposed by Nelson et al. (2008), which was one of the first papers studying data poisoning attacks and defenses. The RONI defense iterates over training points $(x,y)$ and rejects points if the model learned on just the trusted data $\mathcal{T}$ is significantly different from the model learned on $\mathcal{T}\cup\{(x,y)\}$. Another example is the outlier detector introduced in Paudice et al. (2018), which operates similarly to our k-NN defense except that it measures distances only to the points in the trusted subset.

Having a trusted dataset makes it easier for the defender, though such a dataset might be expensive or even impossible to collect; if the defender has enough resources to collect a large amount of trusted data, then they can train a model on only the trusted data, solving the problem of data poisoning. The question of whether a small amount of trusted data is sufficient for defeating attackers while maintaining high overall performance (i.e., not rejecting clean training points that are not similar to the trusted data) is an open one. Finally, defenses that rely on trusted data are particularly vulnerable to attackers that manage to compromise the trusted data (e.g., through clean-label attacks that escape human notice).

The theoretical computer science community has studied robust estimators in high dimensions, which seek to work well even in the presence of outliers (Kearns and Li, 1993). A key issue is that many traditional robust estimators incur a $\sqrt{d}$ increase in error in $d$ dimensions. This theoretical insight aligns with the empirical results in this paper showing that it is often possible to attack classifiers with only a small fraction of poisoned data.

Motivated by these issues, Klivans et al. (2009) and later Awasthi et al. (2014) and Diakonikolas et al. (2017b) design robust classification algorithms that avoid the poor dimension-dependence of traditional estimators, although only under strong distributional assumptions such as log-concavity. Separately, Lai et al. (2016) and Diakonikolas et al. (2016) designed robust procedures for mean estimation, which again required strong distributional assumptions. Later work (Charikar et al., 2017; Diakonikolas et al., 2017a; Steinhardt et al., 2018) showed how to perform mean estimation under much more mild assumptions, and Diakonikolas et al. (2017a) showed that their procedure could yield robust estimates in practice. In recent concurrent work, Diakonikolas et al. (2018) showed that robust estimation techniques can be adapted to classification and used this to design a practical algorithm that appears more robust than many traditional alternatives. It would be interesting future work to attack this latter algorithm in order to better vet its robustness.

Steinhardt et al. (2017) explore the task of provably certifying defenses, i.e., computing a dataset-dependent upper bound on the maximum test loss that an attacker can cause the defender to incur. Their method—from which we adopt the min-max-basic attack—shows that the L2 and slab defenses are sufficient for defending models trained on the MNIST-1-7 and Dogfish datasets but cannot certifiably protect models trained on the Enron and IMDB datasets, which matches with our experimental results. Open questions are whether our improvements to the min-max-basic (e.g., decoy parameters) can be used in their framework to derive tighter upper bounds on attack effectiveness, and whether the other defenses (e.g., the loss defense) can be incorporated into their framework.

Discussion

In this paper, we developed three distinct attacks that could evade data sanitization defenses while significantly increasing test error on the Enron and IMDB datasets. The influence attack directly optimizes for increasing the test loss through gradient ascent on the poisoned points; the KKT attack chooses poisoned points to achieve pre-determined decoy parameters; and the min-max attack efficiently solves for the poisoned points that maximize train loss, as a proxy for test loss.

We summarize the relative merits of these attacks in Table 2. The influence attack is direct but slow, less effective against model-based defenses (such as the loss defense), and less robust. The KKT attack is much faster, at least in our setting where it can heavily exploit convexity; however, its reliance on decoy parameters is also a limitation, as our heuristic for generating decoy parameters might fail under more sophisticated defenses. The min-max attack shares the same reliance on decoy parameters and is slower than the KKT attack, and it only works in the indiscriminate setting, but it is more robust and can handle multi-class settings more efficiently.

We expect that more sophisticated data sanitization defenses could defeat the attacks developed in this paper, which did not account for them. However, these defenses might in turn be broken by attacks that are specifically geared for those defenses. The results in this paper show that data poisoning defenses need to be tested against attackers that are designed to evade them. We end by discussing some directions for future work.

The effectiveness of our attacks vary significantly from dataset to dataset (e.g., linear models trained on the Enron and IMDB datasets are more vulnerable than linear models trained on the MNIST-1-7 and Dogfish datasets). What conditions make certain models on certain datasets attackable, but not others? This is an open question; we speculate that linear models on the Enron and IMDB datasets are easier to attack because they have higher dimensionality and are less linearly separable, but this question deserves more study.

One limitation of our attacks is that they rely on the attacker and defender being able to find the model parameters $\theta$ that globally minimize the training loss. This is a reasonable assumption if the loss is convex, but most models in practice today are non-convex. Analysis of attack algorithms in the non-convex setting is substantially more difficult, e.g., a poisoning attack that works against a neural net trained with a given random seed might fail when the random seed is changed, or a single poisoned point might cause the defender to get stuck at a very bad local minimum. The attacks that we present in this paper can, at least empirically, be applied in some form to non-convex models. For example, in the influence attack, we can still move poisoned data points along the gradient of the test loss. It is an open question whether our attacks remain effective in the non-convex setting.

How might we build stronger defenses that are robust against determined attackers? We outline several approaches, as well as potential difficulties.

One strategy would be to try to design better outlier detectors—perhaps the L2 and slab defenses provide too crude a measure of whether a point is realistic, and sophisticated generative models such as generative adversarial nets (Goodfellow et al., 2014) could better rule out poisoned data. We are skeptical of this approach, as there are many natural distributions (such as multivariate Gaussians) where even a perfect generative model cannot prevent an adversary from substantially skewing empirical statistics of the data (see Steinhardt (2018), Section 1.3). The existence of adversarial test examples for image classifiers (Szegedy et al., 2014; Goodfellow et al., 2015) also weights against this approach, since such examples are generated using a method for inducing high loss under a target model. This method could likely be adapted for use in the min-max attack, as the the main sub-routine in that attack involves generating examples that induce high loss under a target model.

A different strategy is to learn multiple models on different (random or otherwise) subsets of data, in the hopes that the data will be relatively clean at least on some subsets (Fischler and Bolles, 1981; Kearns and Li, 1993; Cretu et al., 2008). In general, these methods are variants of loss-based defenses, in that they assume that poisoned points tend to be poorly fit by the model, and could therefore still be vulnerable to attacks that specifically target loss-based defenses. Especially with larger models and datasets, these methods also incur the additional computational cost from needing to fit multiple models.

Another strategy rests on the observation that if we could directly minimize the $0-1$ test error (rather than using a convex proxy), then an adversary controlling an $\epsilon$-fraction of the data could always induce at most additional $\frac{\epsilon}{1-\epsilon}$ error, at least on the training set.To see this, note that the $0/1$-loss of $\theta^{*}$ averaged across $\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}}$ is at most at most $\epsilon$ larger than across $\mathcal{D}_{\text{c}}$, so any $\hat{\theta}$ outperforming $\theta^{*}$ can only have slightly higher loss than $\hat{\theta}$ across $\mathcal{D}_{\text{c}}$. The key issue with convex proxies for the $0/1$-loss is that they are unbounded and so an adversary can cause the loss on $\mathcal{D}_{\text{p}}$ to be very large. One could perhaps do better by using non-convex but bounded proxies for the $0/1$-loss, which would make optimization of the training loss more difficult, but might pay off with higher robustness. However, it also opens up a new avenue for attack—the attacker could try to push the learner towards a bad local minimum. There are also known hardness results for even approximately minimizing the $0/1$-loss (Feldman et al., 2009; Guruswami and Raghavendra, 2009), but it is possible that they do not apply in practice.

Finally, as noted in Section 7, there is recent work seeking to design estimators that are provably robust to adversarial training data under suitable distributional assumptions. Diakonikolas et al. (2018) recently presented a practical implementation of these methods for classification and regression tasks and showed promising initial results. Their method iteratively removes points with outlying gradients and refits the model, and can be viewed as a more sophisticated version of an iterative loss-based defense; Liu et al. (2017) and Jagielski et al. (2018) also present similar iterative algorithms for the regression setting. We view provable security under a well-defined threat model as the gold standard, and encourage further work along this direction (see Li (2018) or Steinhardt (2018) for two recent overviews). There appears to be plenty of room both to improve the practical implementation of this family of defenses and to devise new theoretically-grounded procedures.

Reproducibility

Code and data for replicating our experiments are available at https://github.com/kohpangwei/data-poisoning-journal-release.

Acknowledgements

We are grateful to Steve Mussmann, Zhenghao Chen, Marc Rasi, Robin Jia, and our anonymous reviewers for helpful comments and discussion. This work was partially funded by an Open Philanthropy Project Award. PWK was supported by the Facebook Fellowship Program. JS was supported by the Fannie and John Hertz Foundation Fellowship.

References

A How many distinct points are needed for data poisoning attacks?

Consider some attack $\mathcal{D}_{\text{p}}$ which makes a defender learn model parameters $\hat{\theta}$. Under what conditions does there exist some other attack $\mathcal{D}_{\text{p}}^{\prime}$ that contains at most as many points ($|\mathcal{D}_{\text{p}}|\geq|\mathcal{D}_{\text{p}}^{\prime}|$), but with fewer distinct points (i.e., $\mathcal{D}_{\text{p}}^{\prime}$ contains repeated copies of points)?

If the attacker could place poisoned points at arbitrary locations, and if the model’s loss function is unbounded (as is the case in most models, e.g., SVMs or logistic regression), then very few poisoned points (distinct or otherwise) are generally needed since the attacker can get high leverage over the model by placing a poisoned point far away. However, in our setting, the attacker is constrained to play poisoned points that are in the feasible set $\mathcal{F}$.

In this section, we provide a general method for finding the minimum number of distinct points necessary for achieving any attack, given a model with a strictly convex loss function and some feasible set $\mathcal{F}$. We show that for binary SVMs and logistic regression, if $\mathcal{F}$ is convex for each class—as is the case for the L2, slab, loss, and SVD—then only 2 distinct points are necessary.

As a high-level sketch, our proof proceeds as follows:

(Proposition 7) We check that for SVMs, $\mathcal{G}_{\hat{\theta}}$ is convex for each class if the original feasible set $\mathcal{F}$ is convex for each class.

(Proposition 8) More generally, we establish conditions under which differentiable margin-based losses have $\mathcal{G}_{\hat{\theta}}$ convex for each class, and we show that logistic regression satisfies these conditions.

For convenience, in the sequel we will assume that these models are trained by finding

We start by establishing the equivalence between the number of distinct points needed to poison a given model and the geometry of the set of feasible gradients of that model.

The defender learns parameters $\hat{\theta}$ that minimize the training loss

Since $\hat{\theta}$ is a minimum of the loss, we have that

Proposition 4 tells us that to find the number of distinct points required for data poisoning attacks on a given model and feasible set, it suffices to find the Carathéodory number of the set of feasible gradients of that model. Finding the Carathéodory number of a set is a well-studied problem (see, e.g., Bárány and Karasev (2012), or Mirrokni et al. (2015) for an approximate version of the problem). In our setting, each feasible set can be written as the union of a small number of convex sets, which simplifies the analysis of its Carathéodory number. We start by establishing the following lemma:

If a set $\mathcal{G}$ is the union of $k$ convex sets, $\mathcal{G}=\mathcal{G}_{1}\cup\mathcal{G}_{2}\cup\ldots\mathcal{G}_{k}$ where each $\mathcal{G}_{i}$ is convex, then the Carathéodory number of $\mathcal{G}$ is at most $k$.

We use this lemma to establish the Carathéodory number of the set of scaled gradients for a binary SVM.

Proof Recall that in a binary SVM, the loss on an individual point is given by

For convenience, we have folded the regularization term into the loss on each point.

Plugging this into the expression for $\mathcal{G}_{\hat{\theta}}$, we get that

which we can rewrite as the union of two convex sets, one for each class:

By Lemma 6, the Carathéodory number of $\mathcal{G}_{\hat{\theta}}$ is at most 2, regardless of what $\hat{\theta}$ is.

More generally, we can bound the Carathéodory number of the set of scaled gradients for a particular class of convex, differentiable, margin-based losses.

where $c^{\prime}$ is the derivative of $c$. Substituting this into (29) and cancelling out the $-y$ terms on both sides gives us the equivalent condition

To satisfy the above condition, we will take

First, note that $\log c^{\prime}(\cdot)$ is a concave function, as its derivative $c^{\prime\prime}/c^{\prime}$ is monotone non-increasing by assumption. For notational convenience, let $s_{1}\stackrel{{\scriptstyle\rm def}}{{=}}-y\theta^{\top}x_{1}$ and $s_{2}\stackrel{{\scriptstyle\rm def}}{{=}}-y\theta^{\top}x_{2}$, and let $T\stackrel{{\scriptstyle\rm def}}{{=}}\gamma c^{\prime}(s_{1})+(1-\gamma)c^{\prime}(s_{2})$. We then have that

Exponentiating both sides and rearranging gives us

The above argument shows that $\mathcal{G}_{\hat{\theta},y}$ is a convex set. Since we picked $\hat{\theta}$ and $y$ arbitrarily, we can apply Lemma 6 to conclude that $\mathcal{G}_{\hat{\theta}}=\mathcal{G}_{\hat{\theta},+1}\cup\mathcal{G}_{\hat{\theta},-1}$ has Carathéodory number at most 2 regardless of $\hat{\theta}$.

Proof In logistic regression, we have that $c(v)=\log(1+\exp(v))$; $c^{\prime}(v)=\sigma(v)$ where $\sigma$ is the sigmoid function, $\sigma(v)\stackrel{{\scriptstyle\rm def}}{{=}}\frac{1}{1+\exp(-v)}$; and $c^{\prime\prime}(v)=\sigma(v)(1-\sigma(v))$. Thus, $\frac{c^{\prime\prime}}{c^{\prime}}$ is a monotone decreasing function, and $c$ is convex, monotone increasing, and twice-differentiable, so Proposition 8 applies.

We can collect all of the above results into the following theorem, which appears in the main text.

Proof From Proposition 7 (SVMs), Proposition 8 (margin-based losses), and Corollary 9 (logistic regression), we have that the Carathéodory number of $\mathcal{G}_{\hat{\theta}}$ (the set of scaled possible gradients) for each of these models is at most 2, regardless of $\hat{\theta}$. By Proposition 4, we conclude that only 2 distinct points are necessary. In particular, since $\mathcal{G}_{\hat{\theta}}$ can be represented in each of these cases as the union of two convex sets, one for each class, we need 1 distinct point from each class to realize any data poisoning attack.

The general approach of finding the Carathéodory number of the set of scaled possible gradient can be applied to other models beyond those that we consider in this paper. As one example, we can extend the above approach to the setting of a multi-class SVM:

This reduces to the above formulation for a binary (2-class) SVM by setting $\theta_{-1}=-\theta_{+1}$.

Define $\mathcal{G}_{i,j}=\{-\alpha x^{(i)}+\alpha x^{(j)}:0\leq\alpha\leq 1,(x,i)\in\mathcal{F}\}$. We have that $\mathcal{G}_{\hat{\theta}}=\bigcup_{i=1}^{k}\bigcup^{k}_{j\neq i}\mathcal{G}_{i,j}$, and since each $\mathcal{G}_{i,j}$ is a convex set, by Lemma 6, the Carathéodory number of $\mathcal{G}$ is at most $k(k-1)$.

B Attack implementation details

The following details apply to both the influence-basic and influence attacks.

B.2 The KKT attack

Generating decoy parameters. For each dataset, we first generated candidate decoy parameters as in Section 4.2.1—adding $r$ copies of each test point whose flipped label has loss greater than $\gamma$. For Enron, we swept over $r\in\{1,2,3,5,8,12,18,25,33\}$ and $\gamma$ set to the $q$th quantile of the loss (over the flipped test set), for $q\in\{0.05,0.10,\ldots,0.55\}$. This yielded $99$ candidates $\theta_{\text{decoy}}$; for efficiency we removed all parameters that had lower test error and higher training loss than some other candidate $\theta_{\text{decoy}}^{\prime}$. This left us with $48$ parameters total. For IMDB, we applied a similar procedure but took $r\in\{1,2,3,4,5\}$ and $q\in\{0.1,0.2,\ldots,0.6\}$; this yielded $18$ candidates after pruning (we sought fewer candidates for IMDB because it is bigger and slower to attack).

Choosing the labels of poisoned points. Given the fraction of poisoned data $\epsilon=3\%$, for each set of decoy parameters, we grid searched over 7 different ratios of positive vs. negative poisoned points, ranging from $\epsilon_{+}=3\%,\epsilon_{-}=0\%$ to $\epsilon_{+}=0\%,\epsilon_{-}=3\%$.

B.3 The min-max attack

Loss defense threshold. To evade the loss defense, we used the threshold $\tau=0.25$ across all experiments. The results were fairly robust to this choice of threshold.

Multi-class training. For the MNIST dataset, we trained the multi-class SVM with AdaGrad (Duchi et al., 2010), with a batch size of 20, step size $\eta=0.02$, and 3 passes over the training data.

C Experiments on MNIST-1-7 and Dogfish

In this section, we study the effectiveness of the influence attack on the following two datasets:

The MNIST-1-7 image dataset (LeCun et al., 1998), which requires each input feature to lie within the interval (representing normalized pixels). It is derived from the standard 10-class MNIST dataset by taking just the images labeled ‘1’ or ‘7’. It is easily linearly separable: an SVM achieves 0.7% error on the clean data.

As discussed in Section 5, Steinhardt et al. (2017) showed that the L2 and slab defenses are certifiably effective at defending the MNIST-1-7 dataset, and to a lesser extent the Dogfish dataset, for low values of $\epsilon$. The results in Figure 12 are consistent with this: with $\epsilon=3\%$, the influence attack increases Dogfish test error from 1% to 8% and does not appreciably affect MNIST-1-7 test error. In contrast, it drives test error on the Enron dataset from 3% to 23%.

D Label Flip Attacks

Many ways of choosing which points to flip have been proposed (see Xiao et al. (2015) for a review). Here, we consider the alfa attack from Xiao et al. (2012). alfa seeks to add points that have a high loss under the original (clean) model $\theta^{*}\stackrel{{\scriptstyle\rm def}}{{=}}\operatorname*{argmin}_{\theta}L(\theta;\mathcal{D}_{\text{c}})$ but a low loss under the final (poisoned) model $\hat{\theta}\stackrel{{\scriptstyle\rm def}}{{=}}\operatorname*{argmin}_{\theta}L(\theta;\mathcal{D}_{\text{c}}\cup\mathcal{D}_{\text{p}})$. Concretely, it solves:

We adapt the original alfa attack to our setting in the following two ways:

We constrain all poisoned points in $\mathcal{D}_{\text{p}}$ to lie in the feasible set $\mathcal{F}_{\beta}$.

We set $\mathcal{D}_{\text{pool}}=\mathcal{D}_{\text{test}}$; that is, the attacker gets to add points from the flipped test set. Intuitively, adding flipped versions of test points to the training set should cause the model to wrongly classify those test points, in line with the attacker’s goal of increasing the model’s loss on the test set.