Indiscriminate Data Poisoning Attacks on Neural Networks
Authors: Yiwei Lu
Gautam Kamath
Yaoliang Yu
Venue: Accepted by TMLR ()

Abstract: Data poisoning attacks, in which a malicious adversary aims to influence a model by injecting ``poisoned'' data into the training process, have attracted significant recent attention. In this work, we take a closer look at existing poisoning attacks and connect them with old and new algorithms for solving sequential Stackelberg games. By choosing an appropriate loss function for the attacker and optimizing with algorithms that exploit second-order information, we design poisoning attacks that are effective on neural networks. We present efficient implementations by parameterizing the attacker and allowing simultaneous and coordinated generation of tens of thousands of poisoned points, in contrast to most existing methods that generate poisoned points one by one. We further perform extensive experiments that empirically explore the effect of data poisoning attacks on deep neural networks. Our paper sets a new benchmark on the possibility of performing indiscriminate data poisoning attacks on modern neural networks.

Published in Transactions on Machine Learning Research (12/2022)
Indiscriminate Data Poisoning Attacks on Neural Networks* *
Yiwci Lu University of Waterloo
giwei, Thwei.ku@uwaaeeroo..co
Gautam Kamath University of Waterloo
g mit edu
Yaoliang Yu! University of Waterloo
yaoliang. you @wwaterrooo.co
Reviewed on OpenReview:
Abstract
Data poisoning attacks, in which a malicious adversary aims influence a model by inject- ing "poisoned" data into the training process, have altracted significant. recent attention. In this work, we take closer look at existing poisoning attacks and connect them with old and new algorithms for solving sequential Stackelberg games. By choosing an appropriate loss function for the attacker and optimizing with algorithms that exploit second-order informa- tion, we design poisoning attacks that are effective on neural networks. We present efficient implementations by parameterizing the attacker and allowing simultaneous and coordinated generation of lens of thousands of poisoned points, contrast to most existing methods that generate poisoned points one by one. We further perform extensive experiments that empirically explore the effect of data poisoning attacks deep neural networks. Our paper sets new benchmark the possibility of performing indiscriminate data poisoning attacks on modern neural networks.
1 Introduction
Adversarial attacks have repeatedly exposed critical vulnerabilitics in modern machinc lcarning (ML) mod- els (Nelson et al., 2008; Szegedy et al., 2013; Kumar et al., 2020). As ML systems are deployed in increasingly important settings, significant effort has been levied understanding attacks and defenses towards robust machine learning.
In this paper, focus on data poisoning attacks. ML models require a large amount of data to achieve good performance, and thus practitioners frequently gather data by scraping content. from the web (Gao et al., 2020; Wakefield, 2016). This gives rise to an attack vector, in which an adversary may manipulate part of the training data by injecting poisoned samples. For example, an attacker can actively manipulate datasets by sending corrupted samples directly to a dataset aggregator such as chatbot, a spam filter, or user profile databascs; the attacker can also passively manipulate datascts by placing poisoned data, on the web and waiting for collection. Moreover, in federaled learning, adversaries can also inject malicious data into diffuse network (Shejwalkar et al., 2021; Lyu al., 2020).
A spectrum of such data poisoning attacks cxists in the literature, including targeted, indiscriminate and backdoor atfacks. We focus on indiscriminate allacks for image classification, where the allacker aims at decreasing the overall test accuracy a model by adding a small portion of poisoned points. Current indiscriminate attacks are most effective against convex models (Biggio et al., 2011; Koh & Liang, 2017;
*CK and YY are listed in alphabetical order.
TSupported NSERC Discovery Grant, unrestricted gift from Google, and University of Waterloo startup grant. #Supported an NSERC Discovery Grant, Canada CIFAR AT chair program and WHJII..

---

Published in Transactions on Machine Learning Research (12/2022)
Koh et al., 2018; Shumailov et al., 2021), and several defenses have also been proposed (Steinhardt et al., 2017; Diakonikolas et al., 2019). However, existing poisoning attacks are less adequate against more complex non-convex models, especially deep neural networks, either due to their formulation being inherently tied to convexity or computational limitations. For example, many prior attacks generate poisoned points sequen- tially. Thus, when applied to deep models or large dalasets, these altacks quickly become compulationall infeasible. To our knowledge, a systematic analysis of indiscriminate data poisoning attacks on deep neural works is still largely missing gap we aim to fill in this work.
To address this difficult problem, we design more versatile data poisoning attacks by formulating the problem as a non-zcro-sum Stackelberg game, in which the attacker crafts some poisoned points with the aim of decreasing the test accuracy, while the defender optimizes its model on the poisoned training set. We exploit sedond-order information and apply the Total Gradient Descent Ascent (TGDA) algorithm to address the attacker's objective, even on non-convex models.
We also examine the elfectiveness of alternative formulations, including the simpler zero-sum setting as well when the defender leads the optimization. Moreover, address computational challenges by proposing efficient architecture for poisoning attacks, where parameterize the attacker than optimizing the poisoned points directly. By applying TGDA to update the attacker model directly, we are able to generate lens of thousands of poisoned points simultaneously in one pass, potentially even in a coordinated way.
separate network rather
In this work, we make the following contributions:
We construct new data poisoning attack based on TGDA that incorporates second-order optimiza- tion. In comparison to prior data poisoning attacks, ours is significantly more effective and runs least order of magnitude faster.
We summarize and classify existing data poisoning attacks (specifically, indiscriminate attacks) in both thcoretical formulations and experimental settings.
We propose an efficient allack architecture, which enables a more efficient clean-label al attack. We conduct experiments to demonstrate the effectiveness of our attack on neural networks and its advantages over previous methods.
Notation. Throughout this paper, we denote training data Drr, validation data as De, test data Dreat: and poisoned data as Dp- We use L to denote the leader in Stackelberg game, for its loss function, x for its action, and A for its model parameters (if they exist). Similarly, we use F to denote the follower, f for its loss function, and w for its model parameters. Finally, we use é as the poison budget, namely that 'Dpl = =/rrl
2 Background
In this section, we categorize existing data poisoning attacks according to the attacker's power and objectives, and specify the type of attack we study in this paper.
2.1 Power of an attacker
Injecting poisoned samples. Normally, without breaching the defender's database (i.e., changing the existing training data Dor), an attacker can only inject poisoned data, actively or passively to the defender's database, such that its objective can be achieved when the model is retrained after collection. Such a situation may be realistic when the defender gathers data from several sources, some of which may be untrusted (e.g., when scraping data from the public Internet). The goal of the attacker can be presented as:
w. = (D,)) E arg min L(Drr U D w),
(1)
where w. is the attacker's desired model parameter, which realizes the attacker's objectives, L(-) is the loss function. We focus on such attacks and further categorize them in the next subsection.
2

---

Published in Transactions on Machine Learning Research (12/2022)
Perturbing training data. Some work makes the assumption that the attacker can directly change the training data Dtr- This is perhaps less realistic, as it assumes the attacker has compromised the defender's database. We note that this threat model may be more applicable in an alternate setting, where the defender wishes to prevent the data from being used downstream to train a machine learning model. This research direction locuses on so called unlearnable eramples (Huang et al., 2021; Yu et al., 2021; Fowl al., 2021b;a), and has faced some criticism that it provides "a false sense of security" (Radiya-Dixit et al., 2022). We provide more details of this line of research in Appendix B.
In this paper, we focus on injecting poisoned samples it is more realistic attack.
2.2 Objective of an attacker
Data poisoning attacks can be further classifidd into three categories according to the adversary's objective (Cinà et al., 2022; Goldblum et al., 2022).
Targeted attack. The attacker adds poisoned data Dp resulting in a w such that a particular target example from the test set is misclassified as the base class (Shafahi et al., 2018; Aghakhani et al., 2020; Guo & Liu, 2020; Zhu et al., 2019). This topic is well studied the litcrature, and we refer the reader Schwarzschild al. (2021) for an excellent summary of existing methods.
Backdoor attack. This attack aims at misclassifying any test input with a particular trigger pattern (Gu et al., 2017; Tran et al., 2018; Chen et al., 2018; Saha et al., 2020). Note that backdoor attacks require access to both the training data as well as the input at inference time to plant the trigger.
Indiscriminate attack. This attack aims to induce a parameter vector w that broadly decreases the model utility. We consider image classification tasks where the attacker aims to roduce the overall classification accuracy. Existing methods make different assumptions on the attacker's knowledge:
Perfect knowledge attack:
the attacker has access to both training and test data (Dtr and Drest),
the target model, and the training procedure (c.g., the min-max attack of Koh et al. 2018). Training-only attack: the attacker has access to training data Der, the target model, and the training procedure (e.g.,
et al. 2017; Biggio et al. 2012).
Training-data-only attack: the attacker only has access to the training data Drr (e.g., the label flip attack of Biggio et al. 2011).
In Appendix A we give more detailed summary of the existing indiscriminate data poisoning attacks.
In this work, we focus on training-only atlacks because perfect knowledge attacks are not always feasible due to the proprietary nature of the test data, while existing training-data-one data-only attacks are weak and often fail for deep ncural networks, as we show in Section 5.
3 Total Gradient Descent Ascent Attack
In this section, we formulate the indiscriminate attack and introduce our attack algorithm. We first briefly introduce the Stackelberg game and then link it to data poisoning.
3.1 Preliminaries on Stackelberg Game
The Stackelberg competition is strategic game in Economics in which two parties move soquentially (von Stackelberg, 1934). Specifically, we consider two players, leader L and follower F in Stackelberg game, where the follower F chooses w to best respond to the action x of the leader L, through minimizing its loss function f:
Vx E CC, wx(x) E arg min f(x, w),
(2)
weW
and the leader L chooses to maximize its loss function t:
X, E arg max f(x, w, wx()), XEX
(3)
3

---

Published in Transactions on Machine Learning Research (12/2022)
where (x., w. (xx)) is known Stackelberg equilibrium. We note that early work of Liu & Chawla (2009) already applied the Stackelberg game formulation to learning linear discriminant function, where an adversary perturbs the whole training set first. In contrast, we consider the poisoning problem where the adversary can only add a small amount of poisoned data to the unperturbed training set. Morcover, instead of the genetic algorithm in Liu & Chawla (2009), we solve the resulting Stackelberg game using gradient algorithms that are more appropriate for neural network models. The follow-up work of Liu & Chawla (2010) further considered a constant-sun simplification, effectively crafting unlearnable examples (see more discussion in Appendix B) for support vector machines and logistic regression. Finally, mention the early work of Dalvi et al. (2004), who essentially considered a game-theoretic formulation of adversarial training. However, the formulation of Dalvi et al. (2004) relied on the notion of Nash equilibrium where both players move simultaneously while in their implementation the allacker perturbs the whole training set w.r.t fixed surrogate model (naive Bayes).
When f l we recover the zero-sum setting where the problem can be written compactly as:
max min {(x, w);
(4)
xeX weW
see, e.g., Zhang et al. (2021) and the references therein.
For simplicily, we assume W R2 and the functions ʃ and l are smooth, hence the follower problem an instance of unconstrained smooth minimization.
3.2 On Data Poisoning Attacks
There are two possible ways to formulate data poisoning as a Stackelberg game, according to the acting order. Here we assume the attacker the leader and acts first, and the defender the follower. This assumption can be easily reversed such that the defender acts first. Both of these settings are realistic depending on the defender's awareness of data poisoning attacks. We will show in Section that the ordering of the parties affects the results significantly.
Non-zero-sum formulation. case is analogous. Here recall that the follower F (i.e., the defender) aims at minimizing its loss function f = L(Drr U Dp, w) under data poisoning:
In this section, we only consider the attacker as the leader as the other
w. = (Dp) E arg arg min L(Drr U Dp. w):
w
while the leader L (i.e., the attacker) aims at maximizing a different loss function E = L(D,, w.) the validation set D.:
Dp_ arg max L(D.,, w.),
(6)
D,
where the loss function C(.) can be any task-dependent target criterion, e,g., the cross-entropy loss. Thus we have arrived at the following non-zero-sum Stackelberg formulation of data poisoning attacks (a.k.a,, a bilevel optimization problem, see e.g. Munoz-González et al. 2017; Huang et al. 2020: Koh et al. 2018):
max L(Do, w.), s.t. w. arg min L(D,r Dp, w). W) D2
Note that we assume that the attacker can inject eN poisoned points, where N | and E is the power of the attacker, measured as fraction of the training set size.
We identify that Equation (7) is closely related to the formulation of unlearnable examples (Liu & Chawla, 2010: Huang et al., 2021; Yu et al., 2021; Fowl et al., 2021b;a; Landoval-Segure et al., 2022; Fu et al., 2021):
max L(D,, w.), s.t. w. arg min L(Dp, w)- D,
4

---

Published in Transactions on Machine Learning Research (12/2022)
where D3 ((x, + oz V.) of is the bounded sample-wise or class-wise perturbation (lo,1lp Eo). The main differences lie in the direct modification of the training set Drr (often all of it). In comparison, adding poisoned points to a clean training set would never results in 100 % modification in the augmented training set. This seemingly minor difference can cause a significant difference in algorithm design and performance. We direct interested readers to Appendix B for details.
Previous approaches. Next, we mention three previous approaches for solving Equation (7).
(1) A direct approach: While the inner minimization can be solved via gradient descent, the outer maxi- mization problem is non-trivial as the dependence of L(D,, w.) on Dp is indirectly through the parameter w of the poisoned model. Thus, applying simple algorithms (e.g., Gradient Descent Ascent) directly would result in zero gradients in practice. Nevertheless, we can rewrite the desired derivative using the chain rule:
aC(D,, w..) aC(De, w dw. dw. OD,
(9)
aD, p
The difficulty lies in computing dw. to the poisoned points Dz- Biggio et al. (2011) and Koh & Liang (2017) compute 8D, exactly via KKT conditions while the Back-gradient attack in descent ascent (UGDA) algorithm in Metz et al. (2017):
aD, i.e., measuring how much the model parameter w changes with respect aw.
et al. (2017) approximate it using gradient ascent. We characterize that et al. (2017) can be understood as the k-step unrolled gradient
X(+1 + m/ Vx Vxell((x,, W:), W++1 = W. 7t W (x,,
(10)
(11)
where (xx w) is the k-time composition, i.e. we perform k steps of gradient descent for the leader. Furthermore, Huang et al. (2020) propose to use meta-learning algorithm for solving a similar bilevel optimization problem in targeted attack, and can be understood as running UGDA for M models and taking the average.
(2) Zero-sum reduction: Koh et al. (2018) also proposed a reduced problem of Equation (7), where the leader and follower share the same loss function (i.e. - (():
max min L(D,r U Dp. w). D,
(12)
This relaxation enables attack algorithms to optimize the outer problem directly. However, this formulation may be problematic its training objective does not necessarily reflect its true influence on test data. However, for unlearnable examples, the zero-sum reduction is feasible, and might be the only viable approach. See Appendix B for more details.
This problem is addressed by Koh et al. (2018) with an assumption that the attacker can acquire a target model parameter, usually using a label flip attack which considers a much larger poisoning fraction E. By adding a constraint involving the larget parameter Wtar, the allacker can search for poisoned points that maximize the loss l while keeping a low loss on whar. However, such target parameters are hard obtain since, as will demonstrate, non-convex models appear to be robust to label flip attacks and there guarantees that w!ar is the solution of Equation (7).
(3) Fixed follower (model): Geiping et al. (2020) propose gradient matching algorithm for crafting targeted poisoning attacks, which can also be casily adapted to unlearnable ezamples (Fowl et al., 2021a). This mothod fixes the follower and supposes it acquires clean parameter w on clean data Drr. We define a reversed function J', where f' can be the reversed cross entropy loss for classification problems (Fowl et al., 2021a). As f' discourages the network from classifying clean samples, one can mimic its gradient V fww D..) by adding poisoned data such that:
Vw Der) 2o V Der Dp).
(13)
To accomplish this goal, Geiping et al. (2020) define a similarity function S for gradient matching, leading to the attack objective:
L = S( Dor), Vwf(w: Dar UD))),
(14)
5

---

Published in Transactions on Machine Learning Research (12/2022)
where we minimize L w.r. Dp. This method is not studied yet in the indiscriminate attack literature, but would serve an interesting future work.
TGDA attack. In this paper, we solve Equation (7) and avoid the calculation of Ow. using the Total gradient descent ascent (TGDA) algorithm (Evtushenko, 1974; Fiez et al., 2020) 1. TGDA takes a total gradient ascent step for the leader and a gradient descent step for the follower:
JDp
X + (>Dxx( we).
(15)
W++1 = W. 777 V [xt, we)
(16)
where Dx = vx - V wxx/ Vww/ Vw is the total derivative of with respect to x, which implicitly measures the change of w with respect to Pp. As optimizing l does not involve the attacker parameter 0, we can rewrite D == wxxf Vwwff Ww.. Here, the product (V -w can be efficiently computed using conjugate gradient (CG) equipped with Hessian-vector products computed by autodiff. As CG essentially Hession inverse-free approach (Martens, 2010), each step requires only linear time. Note that TGDA also be treated as letting k + in UGDA.
We thus apply the total gradient descent ascent algorithm and call this the TGDA attack. Avoiding computing dw. enables us to parameterize Dp and generate points indirectly by treating L as a separate aD, model. Namely that D, Lo(D)r); where 0 is the model parameter and D' is part of the training set to be poisoned. Therefore, can rewrite Equation (15) as:
0.11 = -, + TnDo((,
(17)
Thus, we have arrived at a poisoning attack that generates D, in a batch rather than individually, which greatly improves the attack efficiency in Algorithm Note that the TGA update does not depend on the choice of e. This signíficant advantage over previous methods as the running time does not increase as the attacker is allowed larger budget of introduced poisoned points, thus enabling data poisoning attacks larger training sets.
Algorithm 1: TGDA Attack
Input: Training set Der (2t, Ve J validation set De, training steps T, attacker step size a, allacker number of steps m, defender step size B, defender number of steps n, poisoning fraction E, with Opee and é = L(D,,, w.). , with Wore and f = L(Der UD,, w). Initialize poisoned data set DR - {(1 vi). (I'N. veN)
for t t= I...., T do for i = 1,... m do 4
L +- 0 + aDoE(0, wt)
// TGA on
for j = 1,..., n do
6
w f w - BV f(0,
// GD on
return model Lo and poisoned set Dp=Lon Lo
Necessity of Stackelberg game. Although Equation (7) is equivalent to the bilevel optimization problem et al. (2017); Huang et al. (2020); Koh et al. (2018), our sequential Stackelberg formula- tion more suggestive of the data poisoning problem as it reveals the subtlety in the order of the attacker and the defender.
in
4 Implementation
In this section, we (1) discuss the limitations of existing data poisoning attacks and how to address them, (2) set an efficient attack architecture for the TGDA attack.
There other possible solvers for Equation (7), and have listed them Appendix

---

Published in Transactions on Machine Learning Research (12/2022)
Table 1: Summary of existing poisoning attack algorithms, evaluations, and their respective code. While some papers may include experiments on other datascts, we only cover vision datasets as our main focus is image classification. The attacks: Random label flip and Adversarial label flip attacks (Biggio et al,, 2011); P-SVM: PoisonSVM attack (Biggio et al., 2011), Min-max attack (Steinhardt et al., 2017), KKT attack (Koh et al., 2018), i-Min-max: improved Min-max attack (Koh et al., 2018), MT: Model Targeted attack (Suya et al., 2021), BG: Back-gradienn attack (Muñoz- González et al., 2017).
Attack
Datasct
Model
Pa-l
Decot
Code
Multiclass
Batch
Random label flip
toy
SVM
0-40%
c e/Prr
Adversarial label flip
toy
SVM
0-40%
c| 1r
P-SVM
MNIST-17
SVM
100
500
0-9%
x
Min-max
MNIST-17/Dogthn
SVM
60000
10000
0-30%
v
KKT
MNIST-17/Dogfiel
SVM, LR
13007/1800
2103/600
3%
L-Min-max
MNIST
SVM
60000
10000
3%
MT
MNIST-17/Dogfshh
SVM, LR
13007/1800
2163/660
BG
MNIST
SVM, NN
1000
8000
0-6%
4.1 Current Limitations
We observe two limitations of existing data poisoning attacks.
Inconsistent assumptions. We first summarize existing indiscriminate data poisoning attacks Table 1, where we identify that such attacks work under subtly different assumptions, on, for example, the attacker's knowledge, the attack formulation, and the training set size. These inconsistencies result in somewhat unfair comparisons between methods.
Limitation 1:
Solution: We set experimental protocol for generalizing existing attacks and benchmarking data poisoning attacks for systematic analysis in the future. Here we fix three key variants:
(1) the attacker's knowledge: as discussed in Section 2, we consider training-only attacks;
(2) the attack formulation: in Section 3, we introduce three possible formulations, namely non-zero-sum, zero-sum, and zero-sum with target parameters. We will show in the experiment section that the latter two are ineffective against neural networks.
(3) the dataset size: existing works measure altack elficacy with respect to the size of the poisoned dataset, where size is measured as
MNIST-17
Test accuracy drop (%))
PolsonSVM
a fraction E of the training dataset. However, some works subsample
Back-gradient
30
and thus reduce the size of the training dataset. As we show
Figure 1, attack efficacy not invariant to the size of the training set: larger training sets appear to be harder to poison. Furthermore, keeping e fixed, smaller training set reduces the number of poisoned data points and thus the time required for methods that generate points sequentially, potentially concealing a prohibitive runtime for poisoning the full training set. Thus we consider not only a fixed e, but also the complete training set for attacks.
20
10
0
1000 2000 3000 4000 5000
Training set size
Limitation 2: Running time. As discussed in Scction 3, many ex- isting attacks approach the problem by optimizing individual points directly, thus having to generate poisoned points one by one. Such implementation takes enormous running time (see Section 5) and does not scale to bigger models or datasets.
Figure 1: Comparing the efficacy of poisoning MNIST-17 with the Poi- SonSVM and Back-gradient attacks. The training set size is varied, while the ratio of the number of poisoned points to the training set size is fixed at 3%. These attacks become less of- fective as training set sizes increase.
We design a new poisoning scheme that allows simultane- ous and coordinated generation of D, in batches requiring only one pass. Thanks to the TGDA attack in Section 3, we can treat as a separate model (typically neural network such an autoencoder)
Solution:
7

---

Published in Transactions on Machine Learning Research (12/2022)
that takes part of the Drr as input and generates Dp correspondingly only the parameters of L.
Thus fix the input and optimize
4.2 A more efficient attack architecture
Once we have fixed the attack assumptions and poisoned data generation process, we are ready to specify the complete three-stage attack architecture, which enables compare poisoning attacks fairly. One can easily apply this unified Iramework for more advanced attacks in the future.
(1) Pretrain: The goals of the attacker L are to: (a) Reduce the test accuracy (i.e., successfully attack). (b) Generate Dp that is close to Drr (i.e., thwart potential defenses).
The attacker achieves the first objective during the attack by optimizing f. However, l does not enforce that the distribution of the poisoned points will resemble those of the training set. To this end, we pretrain reconstruct Drr producing parameter vector Opre. This process is identical training an autoencoder.
For the defender, assume that F is fully trained convergence. Thus perform standard training Dir to acquire F with Wpre. Here record the performance of F on Drest (denoted as accı for image classification tasks) as the benchmark we are poisoning.
(2) Attack: We generate poisoned points using the TGDA attack. We assume that the attacker can inject eN poisoned points, where N |Derl and the power of the attacker, measured as a. fraction of the training set size. We summarize the attack procodure in Figure
Initialization: We take the pretrained model with parameter 0pre and F with pretrained parameter Wpre initialization of the two networks; the complete training set Dz, validation set D, and part of the training set as initialization of the poisoned points DØ = Dr eN].
TGDA attack: this paper, we run the TGDA
attack to generate poisoned data. But it can be changed any suitable attack for comparison.
Attacker
Specifically, follow Algorithm and perform m steps of TGA updates for the attacker, and n steps of GD updates for the defender in one pass. We discuss the role of m and n in Section 5.
Dre
Pyre
atlack
Note that previous works (e.g., Koh et al. 2018; Muüoz-González et al. 2017) choose n 1 by de- fault. However, we argue that this is not necessarily appropriate. When system is deployed, the model is generally trained until convergence rather than for only a single step. Thus we recommend choosing much larger n (e.g., n 20 in our experiments) to better resemble the testing scenario.
D2
pretrain
WAre
Der
Label Information: We specify that DO {I,, ys y. Prior works (c.g., Koh et al. 2018: Muñoz-Gonzad González al. 2017) optimize x produce Tp. and perform label flip on y to produce 3p (more details in Appendix A). This approach neglects label information during optimization.
Defender
Figure 2: Our experimental protocol benchmarks data poisoning attacks. (1) Pretrain: the attacker and the defender are first trained on Drr to yield good au- toencoder/ tack, the attacker generates the optimal 0" (thus Dp) w.r.t D, and the the optimal w*; the defender gener- ates optimal w" w.r.t D', Drr DD, and the optimal 0* (which mimics testing).
/eencoder/caassifier classifier respectively. (2) During the at-
In contrast, we fix yp y, and concatenate x and to D = {ux; yı JeM as input to L. Thus we gen- erate poisoned points by considering the label infor- mation. We emphasize that we do not optimize or change the label during the attack, but merely use to aid the construction of the poisoned Zp. Thus, our attack can be categorized clean label.
8

---

Published in Transactions on Machine Learning Research (12/2022)
(3) Testing: Finally, we discuss how measure the effectiveness of attack. In realistic setting, the lesting procedure should be identical to the pretrain procedure, such that we can measure the effectiveness of Dp fairly. The consistency between pretrain and testing is crucial as the model F is likely to underfit with fewer training steps.
Given the final 0, we produce the poisoned points D, = Lo(p)) and train from scratch on Pu,U.pp. Finally, we acquire the performance of F on Prest (denoted as acc2 for image classification tasks). By comparing the discrepancy between pretrain and testing acc1 ace2 we can evaluate the efficacy of an indiscriminate data poisoning attack.
5 Experiments
We evaluate our TGDA attack on various models for image classification tasks and show the efficacy of our method for poisoning neural networks. In comparison to existing indiscriminate data poisoning attacks, we show that our attack is superior in terms of both effectiveness and efficiency.
Specifically, our results confirm the following: (1) By applying the Stackelberg game formulation and in- corporating second-order information, we can attack neural networks with improved efficiency and efficacy using the TGDA attack. (2) The efficient attack architecture further enables the TGDA attack to generate Dp in batches. (3) The poisoned points are visually similar to clean data, making the attack intuitively resistant to defenses.
5.1 Experimental Settings
Hardware and package: Exporiments were run on cluster with T4 and P100 GPUs. The platform we use is PyTorch (Paszke et al., 2019). Specifically, autodiff can be easily implemented using torch. autograd. As for the total gradient calculation, we follow Zhang et al. (2021) and apply conjugate gradient for caleu- lating Hessian-vector products.
Dataset: We consider image classification on MNIST (Deng, 2012) (60,000 training and 10,000 test images). and CIFAR-10 (Krizhevsky, 2009) (50,000 training and 10,000 test images) datasets. We are not aware of prior work that performs indiscriminate data poisoning on dataset more complex than MNIST or CIFAR- 10, and, as we will see, even these settings give rise to significant challenges in designing efficient and effective attacks. Indeed, some prior works consider only a simplified subset of MNIST (e.g., binary classification I's and 7's, or subsampling the training set to 1,000 points) or CIFAR-10 (e.g., binary classification on dogs and fish). In contrast, we set benchmark by using the full datasets for multiclass classification.
Training and validation set: During the attack, we need to split the clean training data into the training set Der and validation set D,.. Here we split the data to 70% training and 30% validation, respectively. Thus, for the MNTST dataset, we have [Der = 42000 and |Dx| = 18000. For the CIFAR-10 dataset, we have [Drr - 35000 and [P,| 15000.
Attacker models and Defender models: (1) For the attacker model, for MNIST dataset: use three- layer neural network, with three fully connected layers and leaky ReI.U activations; for CIFAR-10 dataset, we use an autoencoder with three convoluational layers and three conv transpose layers. The attacker takes the concatenation of the image and the label as the input, and generates the poisoned points. (2) For the defender, we examine three target models for MNIST: Logistic Regression, a neural network (NN) with three layers and a convolutional neural network (CNN) with two convolutional layers, maxpooling and one fully connected layer; and only the CNN model and ResNet-18 (He et al., 2016) for CIFAR-10 (as CIFAR-10 contains RBG images).
Hyperparametors: (1) Pretrain: we use a batch size of 1,000 for MNIST and 256 for CIFAR-10, and optimize the net worw using our own implementation of gradient descent with torch. aarchaad We choose the learning rate as 0.1 and train for 100 epochs. (2) Attack: for the attacker, we choose a = 0.01, m = 1 by default; for the defender, we choose 3 = 0.1, n = 20 by default. We set the batch size to be 1,000 for MNIST; 256 for CIFAR10 and train for 200 epochs, where the attacker updated using total gradient ascent and the defender is updated using gradient descent. We follow Zhang et al. (2021) and implement TGA using
9

---

Published in Transactions on Machine Learning Research (12/2022)
The attack accuracy /acuuacy/cccuracy drop (%) and attack running time (hours) on the MNIST dataset. We only record the attack running time since pretrain and testing time are fixed across different methods. As the label flip attack does not involve optimization, its running time is always O. We take three different runs for TGDA to get the mcan and the standard derivation. Our attack outperforms the Min-max, i-Min-max and boak-gradient attacks in terms of both effectiveness and efficiency across neural networks.
Table 2:
Clean
Label Flip
Min-max
--Min-max
BG
(ours)
Model
Aoc
Acx/Drop
Time
Ace/Drop
Time
Aoz/Drop
Time
Ace/Drop
Time
Acc/Drop
Time
LR
92.35
90.83/ / 1.52
0 hrs
80.80/2.55
0.7 hrs
80.56/2.79
19 hrs
89.82 / 2.53
27 hrs
89.56 / 2.7920.07 1.1 hrs
NN
98.04
97.99
0.05
hre
98.07/-0.03
13 hrs
97. 97.82/0.22
73 hrs
97.67 0.37
239 hrs
96.54 / 1.50
15 hrs
CNN
99.13
99.12
0.01
99.55/-0.42
63hes
99.05/0.06
246 99.02 0.09
2153 hes
98.02 / 10.m
conjugate gradient. We choose the poisoning fraction 3% by default. Note that choosing a bigger & will not increase our running time, but we choose small e resemble the realistic setting in which the attacker is limited in their access to the training data. (3) Testing: we choose the exact same setting as pretrain to keep the defender's training scheme consistent.
There is a spectrum of data poisoning attacks in the literature. However, due to their attack formulations, only a few atlacks can be directly compared with our method. See Table in Appendix A for a complete summary, For instance, the Poison SVM (Biggio et al., 2011) and KKT (Koh et al., 2018) attacks can only be applicd to convex models for binary classification; the Min-max (Steinhardt et al., 2017) and the Model largeted (Suya et al., 2021) attacks can be only applied to convex models. However, it is possible to modify Min-max (Steinhardt et al., 2017) and i-Min-max (Koh al., 2018) attacks to attack neural networks. Moreover, compare with two baseline methods that can originally attack neural networks: the Back grek-gradeent attack González et al., 2017) and the Label flip attack (Biggio et al., 2011). It is also possible to apply certain largeted atlack methods (e.g., MetaPoison, Huang et al. 2020) in the context of indiscriminate attacks. Thus we compare with MetaPoison on CIFAR-10 under our unified architecture. We follow Huang et al. (2020) and choose K = 2 unrolled inner steps, 60 outer steps, and an ensemble of 24 inner models.
Basclines:
5.2 Comparison with Benchmarks
MNIST. We compare our attack with the Min-max, i-Min-max, Back- greddgradient and the Label flip attacks with 5 3% MNIST in Table 2. Since the Min-max, i-Min-max, and Back-gradient attack relies on generating poisoned points sequentially, we cannot adapt it into our unified architecture and run their code directly for comparison. For the label flip allack, we flip the label according to the rule y + 10 y, there are 10 classes in MNIST.
We observe that label flip attack, though very efficient, is not effective against neural networks. Min-max allack, due to its zero-sum formulation, does not work on neural worksrks. i-Min-max allack is effective against LR, but performs poorly on neural networks where the assumption of convexity fails. Although Munoz-González et al. (2017) show empirically that the Back-gradicnt attack is effective when attacking subsets of MNIST (1,000 training samples, 5,000 testing samples), we show that the attack is much less effective on the full dataset. We also observe that the complexity of the target model affects the attack effectiveness significantly. Specifically, we find that neural networks are generally more robust against in- discriminate data poisoning attacks, among which, the CNN architecture is even more robust. Overall, our method perforrs the baseline methods across the three target models. Moreover, with our unified architecture, we significantly reduce the running time of poisoning attacks.
CIFAR-10. We compare our attack with the Label flip attack and the MetaPoison attack with E 3% CIFAR-10 in Table 3. We omit comparison with the fack-gradient attack as it is too computationally expensive to run on CIFAR-10. We observe that running the TGDA attack following Algorithm 1 directly is computationally expensive on large models (e.g., ResNet, He el al. 2016). However, it is possible to run TGDA on such models by slightly changing Algorithm 1: we split the dataset into partitions and run TGDA separately on different GPUs. This simple trick enables us to poison deeper models and we find it works well in practice. We observe that the TGDA attack very effective at poisoning the CNN and the ResNet-18 18 architectures, Also, MetaPoison is a more efficient attack (meta-learning with two unrolled steps is
10

---

Published in Transactions on Machine Learning Research (12/2022)
Table 3: The attack vecuracy/accuraat drop (%) and attack running time (hours) on CIEAR-10. Note that TGDA experiments are performed on GPUs for parallel training. We take three different runs for TGDA and MetaPoison to get the mean and the standard derivation.
Clean
Label Flip
Peisoo
TGDA(ours)
Model
Acc
Acc/Drop
Time
Ace/Drop
Time
Acc/Drop
Time
CNN
69.44
68.99 68.99/0.45
hrs 68. 18.1141.132..1
35 hrs
65.15/4.29
42 hrs
ResNet-18
94.95
94.79 74/79/0.16
0 hrs 02.00/22.052..
108 hrs 89.41/5..420.3
162 hrs
Table 4: Comparing the TGDA attack with different orders: attacker as the leader and defender as the leader in terms of Lest accuracy bacnccy/yccuuee Jacuurayy drop(%). Atlacks are more effective when the allacker is the leader.
Target Model
Clean
Attacker as leader Defender as leader
L.R
92.35
89.56
2.79
89.79 / 2.56
NN
98.04
96.54
1.50
96.98 / 1.06
CNN 99.13
98.02
1.11
98.66 / 0.47
much quicker than calculating total gradient), but since its original objective to perform targetod attacks, its application to indiscriminate attacks not effective. Moreover, the difference between the efficacy of the TGDA attack MNIST and CIFAR-10 suggests that indiscriminate attacks may be dataset dependent, with MNIST being harder to poison than CIFAR-10.
5.3 Ablation Studies
To better understand our TGDA attack, we perform ablation studies on the order in the Stackelberg game, the attack formulation, roles in our unified attack framework, and the choice of hyperparameters. For putational considerations, we run all ablation studies the MNIST dataset unless specified. Furthermore, we include empirically comparison with unlearnable ezamples in Appendix B.
Who acts first. In Section 3, we assume that the attacker is the leader and the defender is the follower, iee, that the attacker acts first. Here, we examine the outcome of reversing the order, where the defender acts first. Table 4 shows the comparison. We observe that across all models, reversing the order would result in less effective attack. This result shows that even without any defense strategy, the target model would be more robust if the defender acts one step ahead of the attacker.
Figure 3: We visualize the poi- soned data generated by the TGDA attack with pre- training the leader L the MNIST dataset.
Attack formulation. In Section 3, we discuss a relaxed attack formula- tion, where = f and the game zero-sum. We perform experiments on this setting and show results in Table 5. We observe that the non-zero- sum formulation is significantly more effective, and in some cases, the zero-sum setting actually increases the accuracy after poisoning. We also find that using target parameters would not work for neural networks as they are robust to label flip attacks even when e is large. We ran a label flip attack with e = 100% and observed only 0.1% and 0.07% accuracy drop on NN and CNN architectures, respectively. This provides further evidence that neural networks are robust to massive label noise, as previously observed by Rolnick et al. (2017).
Role of pretraining. In Section 4, we propose two desired properties of L, among which should generate D, that is visually similar to Dtr. Thus requires the pretraining of L for reconstructing images. We perform experiments without pretraining L to examine its role in effecting the attacker. Figure 3 confirms that without pretraining, the attacker will generate images that are visually different from the Drr distribution, thus fragile to possible defenses. Moreover, Table indicates that without pretraining L, the attack will also be ineffective. Thus we have demonstrated the necessity of the visual similarity between Dp and Drr-
Different E. We have set & = 3% in previous experiments. However, unlike prior methods which generate points one at time, the running time of our attack does not scale with E, and thus we can consider significantly larger and compare with other feasible methods. Figure 4 shows that attkck efficacy increases
11

---

Published in Transactions on Machine Learning Research (12/2022)
Table 5: Comparing the TGDA attack with different formulations: non-zero-sum and zero-sum in terms of test accuracy/ aaauracy/accurayy accuracy drop (%). Non-zero-sum is more effective at gencrating poisoning attacks.
Target Model
Clean
Non Zero-sum
Zero-sum
LR
92.35
89.56 / 2.79
92.33
0.02
NN
98.04
96.54 / 1.50
98.07 / -0.03
CNN
99.13
98.02
1.11
99.55 -0.42
Table 6: Comparing the TGDA attack with/ without pretraining the attacker L in terms of lest accu- racy pacy/accuracy drop (%). Pretraining strongly improves attack efficacy.
Targel Model
Clean
With Pretrain
Without Pretrain
LR
92.35
89.56
2.79
92.09 / 0.26
NN
98.04
96.54
1.50
97.47 / 0.57
CNN
99.13
98.02
1.11
98.72 / 0.41
with E, but the accuracy drop is significantly less than e when e very large. Moreover, TGDA outperforms baseline methods across any choice of E.
Number of steps and We discuss the choice of m and n, the mumber of steps of L and F, respectively. We perform three choices of m and in Table 7. We observe that 20 steps of TGA and 1 step of GD results in the most effective attack. This indicates that when m > the outer maximization problem is better solved with more TGA updates. However, setting 4 (m = 20, = 1) takes 10 times more computation than setting 3 (m = 1, n = 20), due to the fact that the TGA update is expensive. When m = n = 1, the attack is less effective as the defender might not be fully trained respond the attack. When n = 0, the attack is hardly effective at all as the target model not retrained. We conclude that different choices of and n would result. trade-off between elfectiveness and elficiency.
Cold-Start. The methods compare in this work all belong to the partial warm-start category for bilevel optimization (Vicol et al., 2022). It is also possible to formulate the cold-start Stackelberg game for data poisoning. Specifically, we follow Vicol et al. (2022) such that in Algorithm 1, the follower update is modified to w 4- Wpre - f(0, in indiscriminate data poisoning, partial warm-start a better approach than cold-start overall, and our outer problem (antoencoder for generating poisoned points) does not appear be highly wer-parameterized.
(0, w). We report the results in Table 8 on MNIST dataset. We observe that
5.4 Visualization of attacks
Finally, we visualize some poisoned points D, generated by the TGDA attack in Figure 5.
The poisoning samples against NN and CNN are visually very similar with Der as our attack is clean label attack (see Section 4). Moreover, we evaluate the magnitude of perturbation by calculating the maximum of pixel-level difference. Both visual similarity and magnitude of perturbation provide heuristic evidence that the TGDA attack may be robust against data sanitization algorithms. Note that Dp against LR is visually distinguishable, and the reason behind this discrepancy between the convex model and the neural works
LR on NNIST
NN MNST
CN UWEST
Chilt on CITAR-10
Redkat-18 CIPAp-1
15.0
accuracy drop (%)
TODD
Label
12.5
-
TODA
MituPoson
35
10
5.0
02
0.4
0.6
0.8
1.0
0.2
0.6
0.6
0.8
1.0
0.6
3.0
Figure 4: Accuracy drop induced by our TGDA poisoning attack and baseline methods versus e (left three figures: MNIST; right two figures: CIFAR-10). Attack efficacy increases modestly with e. Note that when 1, only 50% of the training is filled with poisoned data.
12

---

Published in Transactions on Machine Learning Research (12/2022)
Table 7: Comparing different numbers of steps of the attacker (m) and defender (n) in terms of test accu- racy /accuracy drop (%). Many attacker steps and single defender step produces the most effective attacks.
Model Clean 1,
1,
1,
20
20,
20
LR 92.35
92.30 / 0.05
89.97
2.38
89.56 / 2.79
89.29 / 3.06 89.77 / 2.57
NN 98.04 98.02 / 0.02 97.03 1.01
96.54 / 1.50
96.33
1.71 96.85 / 1.19
Table Comparing the TGDA atlack with partial warm-start (our original setting) and cold-start terms of test accuracy/accuna accuracy drop (%). Cold-start training less effective overall.
Model
Clean
Partial Warm-start
Cold-start
LR
92.35
89.56
2.79
89.84
2.41
NN
98.04
96.54
1.50
96.77
1.27
CNN
99.13
98.02
1.11
98.33 0.80
may be that the attacker L is not expressive enough to generate extremely strong poisoning allacks against neural networks.
5.5 Transferability of the TGDA attack
Even for training-oni only attacks, the assumption on the attacker's knowledge can be too strong. Thus we study the scenario when the attacker has limited knowledge regarding the defender's 's model F and training process, where the attacker has to use a surrogate model to simulate the defender. We report the transferability of the TGDA attack on different surrggtte models in Table We observe that poisoned points generated against LR and NN have much lower impact against other models, while applying CNNs as the surrogate model is effective all models.
5.6 Against Defenses:
To further evaluate the robustness of the TGDA attack against data sanitization algorithms:
(a) We perform the loss defense (Koh et al., 2018) by removing 3% of training points with the largest loss. We compare with pGAN (Munoz-González et al., 2019), which includes a constraint on the similarity between the clean and poisoned samples, and is thus inherently robust against defensos. In Table 10, we obscrve that although we do not add an explicit constraint on delectability our loss function, our method still reaches comparable robustness against such defenses with pGAN.
Clean
LA
CNN
Clean
3
3
3
10
Poisoned
Attack
Change
Change
20
80
100
120
1.25
1.22
0.88
Figure 5: We visualize the poisoned data generated by the TGDA attack and report the magnitude of perturbation (left: CIFAR- 10; right: MNIST).
13

---

Published in Transactions on Machine Learning Research (12/2022)
Table 9: Transferability expeirments on MNIST.
Surrogate
LR
NN
CNN
Target
LR
CNN
LR
NN
CNN
LR
NN
CNN
Accuracy (rop(%)
2.79
0.12
0.27
0.13
1.50
0.62
3.22
1.47 1.11
Table 10: Comparison with pGAN on MNIST with loss defense.
Method
TGDA (wo// defense)
PGAN(wo/ w defense)
Target Model
LR
NN
CNN
LR
NN
CNN
Accuracy Drop (%) 2.79/2.56
1.50/149
L11/1104
2.52/2.49 109/1.07 0.74/0.73
Table 11: TGDA attack on MNIST with Influence/Sevel Max defense.
Influence
Sever
MaxUp
Model
wo defense w defense
wo defense
w defense
wo defense
w defense
LR
2.79
2.45
2.79
2.13
2.79
2.77
NN
1.50
1.48
1.50
1.32
1.50
1.50
CNN
1.11
1.10
1.11
0.98
1.11
1.11
(b) Other defenses remove suspicious points according to their effect on the learned parameters, e.g., through influence functions (influence defense in Koh & Liang 2017) or gradients (Sever in Diakonikolas et al. 2016). Specifically, influence defense removes 3% of training points with the highest influence, defined using their gradients and Hessian-vector products (Koh & Liang, 2017); Sever removes 3% of training points with the highest outlier scores, defined using the top singular value in the matrix of gradients. Here we examine the robustness of TGDA against these two strong defenses. We observe in Table 11 that TGDA is robust against. Influence defense, but its effectiveness is significantly reduced by Sever. Thus, we conclude Sever is potentially a good defense against the TGDA attack, and it might require special design (e.g., an explicit constraint on the singular value) to break Sever sanitation.
(c) We examine the robustness of our TGDA altack against strong data augnentations, e.g,, the MaxUp defense2 of Gong et al. (2020). In a nutshell, MaxUp generates a set of augmented data with random perturbations and then aims at minimizing the worst case loss over the augmented data. This training technique addresses overfitting and serves as possible defense against adversarial examples. However, it is not clear if MaxUp is a good defense against indiscriminate data poisoning attacks. Thus, we implement MaxUp under our testing protocol, where we add random perturbations to the training and the poisoned data, i.e., (D,, JP): and then minimize the worst case loss over the augmented set. We report the results in Table 11, where we observe that even though MaxUp is a good defense against adversarial examples, it is not readily an effective defense against indiscriminate data poisoning attacks. Part of the reason we believe is that in our formulation the allacker anticipates the retraining done by the defender, in contrast. to the adversarial example setting.
6 Conclusions
While indiscriminate data poisoning attacks have been well studicd under various formulations and settings convex models, non-convex models remain significantly underexplored. Our work serves a first explo- ration into poisoning neural networks under unified architecture. While prior state-of-thhears attacks failed at this task due to either the attack formulation or a computationally prohibitive algorithm, we propose a novel Total Gradient Descent Ascent (TGDA) attack by exploiting second-order information, which enables generating thousands of poisoned points in only one pass. We perform experiments on (convolutional) neu- ral networks and empirically demonstrate the feasibility of poisoning them. Moreover, the TGDA attack
We fallow the implementation https: http://ttthhhhoooe com/ Yunodo hanoodo/mxxug /maxup
14

---

Published in Transactions on Machine Learning Research (12/2022)
produces poisoned samples that are visually indistinguishable from unpoisoned data (i.e., it is clean-label attack), which is desired in the presence of a curator who may attempt to sanitize the dataset.
Our work has some limitations. While our algorithm is significantly faster than prior methods, it remains computationally expensive to poison deeper models such as ResNet, or larger datasets such as ImageNet. Similarly, while our attacks are significantly more effective than prior methods, we would ideally like a poison fraction of ε to induce an accuracy drop far larger than e, as appears be possible for simpler settings (Lai et al., 2016; Diakonikolas et al., 2016; 2019). We believe our work will set an effective benchmark for future work poisoning neural networks.
Acknowledgement
We thank the action editor and reviewers for the constructive comments and additional references, which have greatly improved our presentation and discussion.
References
Hojjat Aghakhani, Dongyu Meng, Yu-Xiang Wang, Christopher Kruegel, and Giovanni Vigna. Bulls- eye polytope: A scalable clean-label poisoning attack with improved transferability. arXiv preprint arXiv:2005.00191, 2020.
Samyadoep Basu, Philip Pope, and Soheil Feizi. Influence functions in deep learning are fragile. In Interna- tional Conference on Learning Representations (ICLR), 2021.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Support vector machines under adversarial label noise. In Proceedings of the Asian Conference on Machine Learning (ACML), pp. 97-112, 2011.
Baltista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In Proceedings of the 29th International Conference on Machine Learning (ICML), pp. 1467-1474, 2012.
Mengjie Chen, Chao Gao, and Zhao Ren. Robust covariance and scatter matrix estimation under Huber's contamination model. The Annals of Statistics, 46(5):1932-1960) 1960, 2018. URL https://doi /ttp://///oo..///.../.
1214/17-A0s161
Antonio Emanuele Cinà, Kathrin Grosse, Ambra Demontís, Sebastiano Vascon Werner Zellinger, Bern- hard A Moser, Alina Oprea, Battista Biggio, Marcello Pelillo, and Fabio Roli. Wild patterns reloaded: A survey of machine learning security against training data poisoning. arXiv preprint S.w:2225500192 2022.
Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, and Deepak Verma. Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 99 19-108, 2004. URL https: /dl,.,....// acm acm. org. /tt.o////////// /10 1144/11114052 1014066.
Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Mogazine, 29(6):141 142, 2012.
Thas Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium Foundations of Computer Science, pp. 655-664, 2016.
Tías Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart. Sever: A robust mela-algorithm for stochastic optimization. In Proceedings of the 36th International Conference Machine Learning, pp. 1596-1606, 2019.
Urün Dogan, Tobias Glasmachers, and Christian Igel. A unified view on multi-class support vector classifi- cation. Journal of Machine Learning Research, 17(45):1-38 12:11132,4000 2016.
Yu. G. Evtushenko. Iterative methods for solving minimax problems. USSR Computational Mathematics and Mathematical Physics, 14(5):52 63, 1974.
15

---

Published in Transactions on Machine Learning Research (12/2022)
Tanner Fiez, Benjamin Chasnov, and Lillian J Ratliff. Implicit learning dynamics in Stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Liam Fowl, Ping-ych Chiang, Micah Goldblum, Jonas Geiping, Arpit Bansal, Wojtck Czaja, and Tom Goldstein. Preventing unauthorized use of proprietary data: Poisouing for secure dataset release. arXiv preprint WiXiv:2033002683, 2021a.
Liam Fowl, Micah Goldblum, Ping-yeh Chiang, Jonas Geiping, Wojtek Czaja, and Tom Goldstein. Adver- sarial examples make strong poisons. arXiv preprint arXiv:2106. 10807, 2021b.
Shaopeng Fu, Fengxiang He, Yang Liu, Li Shen, and Dacheng Tao. Robust unlcarnable examples: Protecting data privacy against adversarial learning. In International Conference on Learning Representations, 2021.
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.0000 000007,0007 2020.
Jonas Geiping, Liam Fowl, W Ronny Huang, Wojeiech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches' brew: Industrial scale data poisoning via gradient matching. arXiv preprint arXiv:2009.0220 02276. 2020.
Micah Goldblun, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li, and Tom Goldstein. Datasct security for machine learning: Data poisoning, backdoor altacks, and defenses. TEEE Transactions on Patlern Analysis and Machine Intelligence, 2022. URL https:/ /ooi
2022. 3123977.
Chengyue Gong, Tongzheng Ren, Mao Ye, and Qiang Liu. Maxup: A simple way to improve generalization of neural network training. arXiv preprint arXiv:200.09002, 2020.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv:1708.0673. 066333 2017.
Junfeng Guo and Cong Liu. Practical poisoning attacks on neural networks. European Conference on Computer Vision, 2020.
Frank R Hampel. The influence curve and its role in robust estimation. Journal of the American Statistical Association, 69(346):383 393, 1974.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the 2016 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR '16 pp. 770 778, Washington, DC, USA, 2016. IEEE Computer Society.
Hanxun Huang, Xingjun Ma, Sarah Monazam Erfani, James Bailey, and Yisen Wang. Unlearnable examples: Making personal data unexploitable. arXiv preprint arXiv:2101 104898, 2021.
W Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. Metapoison: Practical ceneral-purpose clcan-label data poisoning. In Advances in Neural Information Processing Systems, vol- ume 33, pp. 120001 2020.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 1885-1894, 2017.
Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. arXiv:1811.00741, 2018
Alex Krizhevsky. Learning multiple layers of features from tiny images. tech. report, 2009. URL https: / w/wwww www.ttoooooooooooooo www.tooo.oooo...kr.ttt... wttti///elaanneeeeee fettrrrere/ennnnneeeeeeteee-eeee 2e0tture-2200--T.. pdf.
16

---

Published in Transactions on Machine Learning Research (12/2022)
Ram Shankar Siva. Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comis- soneru, Matt Swann, and Sharon Xia. Adversarial machine learning-industry perspectives. In IREE Security and Privacy Workshops (SPW), pp. 69-75, 2020.
Kevin A. Lai, Amup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Proceedings of the 57th Annual IEEE Symposium on Foundalions of Computer Science, pp. 665 674, 2016.
Wei Liu and Sanjay Chawla. A game thcoretical model for adversarial learning. In IEEE International Conference on Data Mining Workshops, pp. 25 30, 2009. URL https://ieeexplorst ieee. org/
pettzract/dccumet//eet /5360532.
Wei Liu and Sanjay Chawla. Mining adversarial patterns via regularized loss minimization. Ma- chine learning, 81()):69 83, 2010. URL http:://innk.sppingerr http://gwr...o//rrr/////........
110994-010-5199-
Lingjuan Lyu, Han Yu, and Qiang Yang. Threats federated learning: A survey. arXiv preprint
MrXiv:2003.02133. 2020.
James Martens. Deep learning via hessian-free optimization. In ICML, pp. 735 742, 2010.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. In International Conference on Learning Representation (ICLR), 2017.
Luis Mluizz-Gonzáler Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C.
Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back-gradient optimization. In Proceedings of the 10th ACM Workshop on Arlificial Intelligence and Securily (ATSec), pp. 27 27-38, 38, 2017.
Luis Muñoz-Gonzále González, Bjarne Pfitzner, Matteo Russo, Javier Carnerero-Cano, and Emil C Lupu. Poisoning attacks with generative adversarial nets. arXiv preprint KKKv:1906.007733 2019.
Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles Sutton, Doug Tygar, and Kai Xia. Exploiting machine learning to subvert your spam filter. LEET, 8:1-9, 2008.
Adamn Paszke, Sam Gross, Francisco Massa, Adamn Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorcch: An imperative style, perfo-performance deep learning library. In Advances in Newral Information Processing Systems 32, NeurIPS '19, pp. 8026-8037. Curran Associates, Inc., 2019.
Evani Madiya-Dixit Sanghyun Hong, Nicholas Carlini, and Florian Tramer. Data poisoning won't save you from facial recognition. In Proceedings of the 10th International Conference on Learning Representations, ICLR '22, 2022.
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv preprint arXiv:1705.10694 2017.
Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hiddon trigger backdoor attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Pedro Sandoval-Segura, Vasu Singla, Jonas Geiping, Micah Goldblum, Tom Goldstein, and David W Jacobs. Autoregressive perturbations for data poisoning. arXiv preprint arXiv:2206.0366 036693 2022.
Avi Schwarzschild, Micah Goldblum, Arjun Gupta, John Dickerson, and Tom Goldstein. Just how toxic is data poisoning? A unified benchmark for backdoor and data poisoning attacks, In Proceedings of the 38th International Conference Machine Learning (TCML), 2021.
17

---

Published in Transactions on Machine Learning Research (12/2022)
Ali Shafahi, W. Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! Targeted clean-label poisoning attacks on neural networks. In Advonces in Newral Information Processing Systems (NeurlPS), pp. 6103 6113, 2018.
Virat Shejwalkar, Amir Houmansadr, Peter Kairouz, and Daniel Ramage. Back to the drawing board: A critical evaluation of poisoning attacks on federated learning. arXiv:2108.10241, 2021.
Ilia Shumailov, Zakhar Shumaylov, Dmitry Kazhdan, Yiren Zhao, Nicolas Papernot, Murat A Erdogdu, and Ross Anderson. Manipulating SGD with data ordering attacks. arXiv:2104009667, 2021.
Jacob Steinhardt, Pang Wei Koh, and Percy Liang. Certified defenses for data poisoning attacks. In Advances in Neural Information Processing Systems (NewrIPS), pp. 3532, 2017.
Fnu Suya, Saced Mahloujifar, Anshuman Suri, David Evans, and Yuan Tian. Model-targeted poisoning at- tacks with provable convergence. In Proceedlings of the 38th International Conference Machine Learning (ICML), pp. 10000- 1000010010, 2021.
Christian Szegedy, Wojeiech Zaremba, 1lya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Paul Vicol, Jonathan P Lorraine, Fabian Podregosa, David Duvenaud, and Roger B Grosse. On implicit bias in overparameeterized bilevel oplimization. In International Conference on Machine Learning, pp- 22234 22259, 2022.
Heinrich von Stackelberg. Market structure and equilibrium. Springer, 1934.
Jane Wakefield. Microsoft chatbot laught swear on twitter. BBC News, 2016.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-
ridge approach. In The 8th International Conference on Learning Representations (ICLR), 2020.
Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie- Liu. Indiscriminate poisoning attacks short- cuts. arXiv preprint arXiv:211L.0088: 2021.
Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for minimax optimiza- tion. In ICML workshop on Beyond First- Order Methods in ML Systems, 2021.
Chen Zhu, W Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning attacks on deep neural nets. In International Conference on Machine Learning, 2019.
18

---

Published in Transactions on Machine Learning Research (12/2022)
A Indiscriminte data poisoning attacks
We first show that perfect knowledge attacks and training-only attacks can be executed by solving non- zero-sum bi-level optimization problem.
A.1 Non-zero-sum setting
For perfect knowledge and training-only attacks, recall that we aim at the following bi-level optimization problem:
max L(Du, w.), s.t. W. E arg min L(Drr U Up, w): D2
(18)
wEW
where we constrain [Dp] = t/r to limit the amount of poisoned data the attacker can inject. The attacker can solve (18) in the training only attack setting. With a stronger assumption where Dzeet is available, we substitute D with Deest and arrive at the perfect knowledge attack setting.
Existing attakks generate poisoned points one by one by considering the problem:
max L(D.. w.), s.t. arg min L(Der U {Ep, Bpl.w) UP
(19)
weW
While the inner minimization problem can be solved via gradient descent, the outer maximization problem is non-trivial as the dependency of [(D,, w.) on Ep is indirectly encoded through the parameter w of the poisoned model. As result, we rewrite the desired derivative using the chain rule:
@D(D,, w.) OD(D,, w.) Ow. dw. Oxp
(20)
Orp
where the difficulty lies in computing dw., ie., measuring how much the model parameter w changes with do,
8w. by solving this problem exactly, using respect to the poisoning point Tp. Various approaches compute Bxg either influence functions (Koh & Liang, 2017) (Influence attack) KKT conditions (Biggio et al., 2011) (PoisonSVM attack²). Another solution is to approximate the problem using gradient descent (Muñoz- González et al., 2017). We discuss each of these approaches below.
Influence attack. The influence function (Hampel, 1974) tells us how the model parameters change as we modify training point by an infinitesimal amount. Borrowing the presentation from Koh & Liang (2017), we compute the desired derivative as:
8w. Ox,
82 (xr. Upp.w..) w.) H H=1
(21)
Ow, O.Kp
where Hw. is the Hessian of the training loss at w.:
0 LL w.. O(w.)2
Hw. = AI + Drr UD (D.
Σ
(22)
Influence functions are well-defined for convex models like SVMs and are generally accurate for our settings. However, they have been showed to be inaccurate for neural networks (Basu et al., 2021).
PoisonS VM attack. Biggio et al. (2012) replaces the inner problem with its stationary (KKT) conditions. According to the KKT condition, we write the implicit function:
OC(Drr U (2p: yoh, w.) 0,
(23)
Ow.
While this might naturally suggest. the name "KKT attack," 7 this reserved for different attack covered in Sec- tion A.3.
19

---

Published in Transactions on Machine Learning Research (12/2022)
which yields the linear system:
0 (Dr U (Tp, Up). w.) 0 LD U (xp:
Upl, w.) dw. 0, Oxp
(24)
Ow,0xp
0(w.)²
and thus we can solve the desired derivative as:
dw. 8 L(Drr U (Tp: MpJ, w.)
( d(w.)²
8 LDDr U Bp), w.)
(25)
drp
dw,0xp
Note that despite their differences in approaching the derivative, both the influence attack and PoisonSVMI attack involve the inverse Hessian.
Back-gradient attack. Muñoz-Gonzáine et al. (2017) avoid solving the outer maximization problem ex- actly by replacing it with a set of iterations performed by an optimization method such as gradient descent. This incomplete optimization of the inner problem allows the algorithm run faster than the two above methods, and poisoning neural networks.
A.2 Zero-sum Setting
Steinhardt al. (2017) reduce Equation (18) to a zero-sum game by replacing L(D,, w.) with C(D U D,, w.), and the original problem can be written as:
max L(D,r Dp, w.). s.t. W. E min [(Der Upp w). weW
(26)
D,
which is identical the saddle-point or zero-sum problem:
max min [(Der UDp w)
(27)
D, w
For an SVM model, given that the loss function convex, we can solve (27) by swapping the min and max and expand the problem to:
min Σ [([x,y).w) + max C((xps Mp), w), {...8p}
(28)
(R.y)ED..
However, we emphasize that this relaxed gradient- attack is problematic and could be ineffective since the loss on the clean data Dir could still be low. In other words, the inner maximization does not address the true objective where we want to change the model parameter to cause wrong predictions on clean data. This can be addressed by keeping the loss on the poisoned data small, but this contradicts the problem formulation. One solution to this is to use target parameters in Section A.3.
A.3 Zero-sum Setting with Target parameters
Gradient-based attacks solve a difficult optimization problem in which the poisoned data D, affects the objective through the model parameter w.. As result, evaluating the gradient usually involves computing Hessian, computationally expensive operation which can not be done in many realistic settings. Koh et al. (2018) propose that if we have a target parameter wter which maximizes the loss on the test data C(Desst, w.), then the problem simplifies to:
find Dp, s.t. w!ar = arg min L(D UD, w),
(29)
wEW
KKT attack. Since the target parameter waar is pre-specified, the condition can be rewritten
tar arg min L(Der UDp, w)
(30)
wEW
arg min
Σ f(1x,y). w)
Σ
[((xp) yph, w):
(31)
WEW (D.y)ED..
20

---

Published in Transactions on Machine Learning Research (12/2022)
Again we use the KKT optimality condition to solve the argmin problem for convex losses:
Σ
((ar))).wtr)) +
Σ
Up(
Up) (
(32)
(D
(ED.BpJED
Thus we can rewrite the problem
find Dps s.1.
Σ
((aa,y).w
Σ
Up),
Uph
(33)
(ep.Be)ED
If this problem has solution, we find it by solving the equivalent norm norm-mininne minimization problem:
min P2
Σ
C((x,y),w
E
C(txp, w(rr)
(34)
(Dtr
(sp:Bo]EDp
where the problem only be minimized if the KKT condition is satisfied. This attack is called the KKT allack.
Of course, the success of this attack relies on the target parameter w Koh et al. (2018) propose to use the label flip attack for such purpose where we use the trained parameter as the target. This attack achieves comparable results to other atlccks while being much faster since il can be solved efficiently using grid search for binary classification. Note that for multi-class classification, this algorithm quickly become infeasible.
Improved min-max. Koh et al. (2018) applies the target parameters to address the issue for the relaxed gradient- cradient-based attack, where we add the following constraint during training:
C(1x, y), w ST
(35)
where t is a fixed threshold. Thus the attacker can search for poisoned points that maximize loss under the current parameter w while keeping low loss on the target parameter wear..
Model Targeted Poisoning. Suya et al. (2021) propose another algorithm for generating poisoned points using target parameters. This attack considers a different attack strategy from the others, where the attacker adopts an online learning procedure. In this case, the attacker does not have a poison fraction to generate specific amount of poisoned data. Instead, the attacker aims reaching stopping criteria (can be either desired accuracy drop desired distance to the target parameter). However, such altacking procedure may cause the poison fraction to be large and it is hard to measure the success of the attack. Thus, we use the same setting as others for fair comparison.
A.4 Training Training-data-onfe data-only attack
In the training-data-one attack setting, since the attacker does not have access to the training procedure, the bi-level optimization methods are not applicable. The remaining strategies focus either on modifying the labels only (i.e., label flip attacks).
Random label flip attack. Random label flipping is a very simple attack, which constructs a set of poisoned points by randomly selecting training points and flipping their labels:
Dp ((x,. (xi, vk) E Drr s.t. [Dpl e
(36)
where for each class 1, I,...,c,
C, we set
T = with probability Pj-
(37)
Note that the weights {p,} may depend on the true label ys- For instance, for binary classification (i.e., 2), we may set Pet1-us ys in which case it simply flips the true label ys-
21

---

Published in Transactions on Machine Learning Research (12/2022)
Adversarial label flip attack. Biggio et al. (2011) consider an adversarial variant of the label flip attack, where the choice of the poisoned points is not random. This attack requires access to the model and training procedure, and thus is not a training-data-one
attack. Biggio et al. (2011) design an attack focused on SVMs. They choose to poison non-support vectors, as these are likely to become support vectors when an SVM is trained on the dataset including these points with flipped labels.
Label flip for multi-class classification For binary classification, label flip is trivial. Koh et al. (2018) provides solution for multi-class classification problem. For marginal based models (for example, SVM), we can write the multi-class hinge loss, where we have (Dogan et al., 2016):
L( w. (mi, v:)) max (0, 1 max W Wy.
(38)
where the choice of is obvious: we choose the index with the highest function score except the target class Naturally, we can use this index j as the optimal label flip. As for non-convex models, the choice of optimal label flip is not clear. In this case, one can use a heuristic by choosing the class with the biggest. training loss.
B Unlearnable Examples
B.1 Stackelberg Game on Unlearnable Examples
We recall the general Stackelberg game in Section 3, where the follower chooses to best respond to the action of the leader L, through minimizing its loss function f:
X R2, w.(x) E arg min f(x, w);
(39)
wEW
and the leader L chooses to maximize its loss function &
X, E arg max E(xx (x)),
(40)
xEX
where (x., (x.)) is Stackelberg equilibrium.
We then formulate unlearnable examples as a non-zero-sum Stackelberg formulation (Liu & Chawla, 2010; Huang et al., 2021; Yu et al., 2021; Fowl et al., 2021b;a; Sandoval-Segura et al., 2022; Fu et al., 2021):
max L(D,, w.), s.t. w. E arg arg min L(D,, w).
(41)
w
where Dp {xx oz, v:)1 oR is the bounded sample-wise perturbation (lo,l S <E), which can be generalized to class-wise perturbation (Huang al., 2021). Similar to indiscriminate data poisoning attacks, this primal formulation is difficult, as for the outer maximization problem, the dependence of L(D,, w.) on D, or a is indireclly through the parameter w of the poisoned model.
However, in practice, we can perform a similar zero-sum reduction in Section 3 (Liu Chawla, 2010):
max min L(Pp, w). D
(42)
We recall that in indiscriminate data poisoning attacks, such formulation is problematic as the attacker may simply perform well on poisoned points D, but poorly on clean points. However, we would not encounter such a problem here as the perturbations are applied across the entire training set Der-
Now we are ready to categorize existing algorithms on unlearnable examples:
Enror-Minimizing Noise (EMN) (Huang et al., 2021): By slightly modifying Equation (42) to min min L(D,, w), D,
(43)
Intuitively, Huang et al. (2021) construct the perturbation to fool the model into learning strong correlation between and the labels.
22

---

Published in Transactions on Machine Learning Research (12/2022)
Table 12: Indiscriminate data poisoning attacks: the attack accuracy/aceuracy drop (%) and attack running
time (hours) on CIFAR-10.
Clean
Label Flip
EMN
TGDA(ours)
Model
Acc/Drop
Time
Acc/Drog
Time
Acc/Drop
Time
CNN
69.44
68.99/0 08.99/0.45 /0.45
hrs 69 69.00/0.44 2.2 hrs
65. 65.15/4.22 4.2
42 hrs
ResNet-18
94.95
94.79/0.16
hrs
94.76/0.19
8.4 hrs
89. 39.41/5.54 5.54
162 hrs
Table 13: Unlearnable examples: model accuracy (%)
under different unlearnable percentages on CIFAR-10
with ResNet-18 model. Percentage of unlearnable examples is defined P..+2p1
[Pal
Method 0%
20%
40%
60%
80%
100%
EMN 94.95
94.38
93.10
91.90
86.85
19.93
TGDA
94.95
93.22
92.80
91.85
85.77
16.65
Robust Unlearnable Examples (Fu et al., 2021): Fu et al. (2021) further propose a min-min-max formulation following Equation (43):
min min max C(D) p. w),
(44)
where I|,; S &u is the defensive perturbation, which is forced to be imperceptible; ||o S Ea the adversarial perturbation, which controls the robustness against adversarial training; D = {(z; + +oj + oof, (:)) Fu et al. (2021) find this formulation generates robust unlcarnable examples against adversarial training.
Adversarial poisoning (Error maximizing) (Fowl et al., 2021b): By freezing the follower entirely in Equation (42), Fowl et al. (2021b) propose to solve the maximization problem:
max L(Dp, p. w),
(45)
D,
such that it is similar to an adversarial example problem. Gradient Matching (Fowl et al., 2021a): Fowl et al. (2021a) solve the same maximization problem Equation (45) and apply the gradient matching algorithm in Geiping al. (2020) (see more details in Section 3).
B.2 Comparison with Indiscriminate Data Poisoning Attacks
Despite their differences in problem formulation, it is possible to compare algorithms for unlearnable examples (we take EMN as an example here) with our TGDA attack. We identify two possible scenarios where we may fairly compare TGDA and EMN empirically:
Indiscriminate Data Poisoning Attacks: for EMN, we first craft perturbations using the original algorithm. After the attack, we take Dp = {(x; + 6:), ye J:M, recall e is the attack budget (or poison ratc). Then, we follow our experimental protocol to perform the attack.
Unlearnable Examples: for TGDA, we follow Equation (12) and perform the zero-sum reduction of TGDA to perturb the entire training set. Note that only consider sample-wis perturbation across all experiments. Similar to our test protocol, we retrain the perturbed model and test the performance of the attack on the test set.
We report the experimental results Table 12 and Table 13, where we observe that:
For indiscriminate data poisoning attacks: In Table 12, although EMN is efficient, its attack efficacy poor. Such poor performance is expected the objective of EMN does not reflect the true influence of an attack clean test data.
For unlearnable examples: In Table 13, we observe that TGDA (after simplification) can be directly comparable with EMN, and the zero-sum simplification allows it to scale up to large models (i.e., ResNet) casily (training time for 100% unlcarnable examples 1.8 hours). However, the perturbation introduced by TGDA is not explicitly bounded.
23

---

Published in Transactions on Machine Learning Research (12/2022)
C Other solvers than TGDA
We recall that in Section 3, we solve Equation (7) and approximate the calculation of aw. aD,
using the total
gradient descent ascent (TGDA) algorithm (Eytushenko, 1974; Fiez et al., 2020):
X++1 = X + <x,,, we). W++1 W. - 77 fx,,, we)
(46)
(47)
where Dx Vxl Vwxf www Vw the total derivative of & with respoct to x.
Furthermore, is possible apply two other algorithms to solve Equation (7):
Follow the ridge (FR) (Evtushenko, 1974; Wang et al., 2020):
X/+1 + (>D we), W++1 W. 17c V f we) + 17 Www.f Vxwf Dxf(xi, we).
(48)
(49)
Gradient descent Newton (GDN) (Evtushenko, 1974; Zhang al., 2021):
X X, DxD(xx We), Wi+1 = -: w V [wf(x,, wt).
(50)
(51)
Zhang et al. (2021) showed that both TGDA and FR are first-order approximations of GDN, despite having similar computational complexity all three.
In our preliminary experiments, TGDA appears be most effective which why we chose it our main algorithm.
24


Reviews:
[{"review_id": "gVgCXiP2Xj", "reviewer": "Reviewer_TZgv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In broad strokes I do think that this work engages an important topic. Model availability attacks with small budgets (which I will refer to as indiscriminate attacks following the author's notation from here on) against neural networks are a hard problem, where it is currently unclear if strong attacks are even possible, and I think it makes sense to approach this work with this framing in mind. I like the derivation of a new attack from bilevel literature via TGDA which I find well motivated.\n\nYet, to me at least, the current version of this submission falls short on delivering on the overall goal of providing a great attack. To put it briefly, I have concerns clustered around two main areas. \n\nFirst, the submission promises a systematic analysis on poisoning deep neural networks, but reviews mostly Cinà et al. \"Wild patterns reloaded: A survey of machine learning security against training data poisoning\" and other surveys with fewer new insights than I would have hoped. Then, existing analysis based on Stackelberg games in the context of data poisoning is reviewed. Here, the submission opens several interesting questions that could go beyond previous treatments of Stackelberg games in poisoning (especially in terms of sequential Stackelberg games), but does not really act on this. \nSecond, the submission promises indiscriminate data poisoning attacks on modern neural networks, and deep neural networks, but the experimental results are not convincing enough to verify this, showing minimal performance degradations on 3-layer models at the cost of astronomical compute effort.\n\nI'll provide a bullet-point list of more details below:\n\n* The submission dismisses comparisons to attacks that perturb training data, but this seems an oversimplification to me. There is a decent number of works that investigate these \"unlearnable examples\", but these are also poisoning availability attacks. The only difference is that perturbations are constrained in input space, but not in number of poisoned examples.\nIt is straightforward to apply these attacks in scenarios where subsets of the training set are poisoned (or poisoned data is added) as analzyed in this work. This task of mixing clean and poisoned data is evaluated in several works on untrainable data, for example, in Sandoval-Segura \"Autoregressive Perturbations for Data Poisoning\" in Table 5. Methods tuned for untrainable data attacks might underperform in the 3% scenario investigated in this work, but the burden of proof there is on the submission to show this. A large range of attacks from this angle of work, especially error-minimizing and error-maximizing perturbations might still have a measurable impact when used in the scenario investigated in this work, especially when epsilon bounds are increased (or liffted entirely). \n* More broadly, when setting out to categorize poison availability attacks, it seems surprising to dismiss these attacks, especially as many attacks can be cast as min-max optimization problems in line with the analysis based on zero-sum Stackelberg games, and works such as Fu et al. \"Robust Unlearnable Examples: Protecting Data Privacy Against Adversarial Learning\" can actually be understood as sequential Stackelberg games. I think it would be an insightful addition to include these works in the categorization.\n* The authors discuss the use of TGDA as algorithm to approximate Eq.(5). It would be great to characterize previous attacks in relationship to TGDA. For example, gradient descent steps on the follower are also prominently discussed in related work. Huang et al., 2020, include a single descent step after evaluating K gradient steps on the leader [and average over many followers]. Muñoz-González et al.,2017, alternate single steps on both leader and follower (same as Koh 2017) and Geiping et al. 2021 \"Witches' Brew: Industrial Scale Data Poisoning via Gradient Matching\" approximate the leader dynamics via gradient matching and freeze the pretrained follower entirely. The update on the leader in Huang and Muñoz-González is actually not so different from the leader step arising from TGDA, as truncated backpropagation can converge to the same objective (see discussion in Shaban 2019, \"Truncated back-propagation for bilevel optimization\") and I think it would be interesting to conceptualize these works and others as instances of TGDA to strengthen the desired overview over poison attacks against neural networks, aside from only minor remarks in Sec. 4.2\n\n* A central problem in previous work on data poisoning with formulations like TGDA is warm-starting, best summarized in Vicol 2022, \"On Implicit Bias in Overparameterized Bilevel Optimization\". It would be great if the submission could include a discussion of the problems discussed in Vicol 2022 for overparametrized models, in the context of this work.\n\n* It is unclear to me why this attack is so expensive for these tiny machine learning models, especially on CIFAR-10. It would be great to at least include a breakdown of costs, but maybe even better would be to address this problem and provide a feasible algorithm that can be evaluated on modern neural networks. For example, have the authors considered the suggestions in Koh and Liang 2017 (Sec. 3), such as fast Pearlmutter approximations for the Hessian vector product? How many CG iterations are required?  In it's current state it feels hard to find this algorithm an \"attack with improved efficiency\" for neural networks.\n\n* If I understand correctly, the attack of Muñoz-González is slow in Table 3 as poisons are created sequentially? While this arguably follows Muñoz-González to the letter, a more modern implementation could just compute poisoned data points in batches (or a single batch) by the same algorithm. I think this somewhat clouds the runtime comparison with the proposed approach.\n\n* The submission claims that the proposed attack is very effective, but over all experiments (which really should include standard deviations), the effective drop is arguably small. The submission attempts to attack with a budget of 3% which really is a hard ask.  I think it would be much more convincing if aside from the 3% scenario, attacks would be plotted for a range of budgets, as done in Fig.4. and compared to other attacks on the full range. \n\n* Speaking of Fig.4 (which I think shows MNIST? it would be great to mark this and also show the CIFAR variant), it is surprising that the proposed attack is not able to break the model even as epsilon goes to 1. Also just for clarification, at eps=1, is half the training set is filled with poisoned data, or is the entire dataset poisoned?\n\n* Concerning the auto-encoder formulation to generate poisoned data: Overall I find this to be an interesting idea, but I do think it detracts somewhat from the central messaging in Sec. 3, as this component could be combined independently with any number of previous attacks. Essentially, this appears as a vague constraint on allowable images (it is, for example not clear what the worst-case image from this generator would look like and whether it still would be in-distribution to real data) that I would either formalize as part of the threat model or re-investigate. For example, another interpretation of the data Sec. 5.3 might be that this component regularizes poisoned data and helps to generate generalizable poisoning data points, with inconspiciousness more of a side effect.\n\n* Table 7, what happens for m=n=1? Or variations with n=0?\n\n* I liked the connection to seq. Stackelberg games briefly discussed in Sec. 5.3 and would have liked to see more analysis of this case. I do think that here again the critique of Radiya-Dixit et al. would be appropriate to discuss, namely that ultimately the defender always moves last in data poisoning.\n\nMinor comments:\n* The section 3 be strengthened by tying the discussion to older works analyzing adversarial games from this lens, for example\n Dalvie et al, 2004, \"Adversarial classification\" and Liu and Chawla, 2009 \"A Game Theoretical Model for Adversarial Learning\" and 2010 \"Mining adversarial patterns via regularized loss minimization\"\n* Sec. 3.2., the submission notes that gradient descent ascent is infeasible due to zero gradients. While I agree with the sentiment, this seems false in general. It would be better to clarify the writing here, especially as the submission then turns to a decomposition of the total gradient (which also might be zero/undefined in large regions).\n* CG is not a Hessian-free approach, I think the intention here was matrix-free?\n* The defense section describes MaxUp as a good defense against adversarial examples. This is a statement that I would be careful with. In general, the only strong defense agaisnt adversarial examples is adversarial training.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This review is about TMLR submission 495. The submission \"Indiscriminate Data Poisoning Attacks on Neural Networks\" reviews and categorizes poisoning attacks on model availability and discuss a new attack. The main focus in this work is on model availability attacks (alternatively described as indiscriminate attacks) where the fraction of poisoned samples is small.  The attack is evaluated on MNIST and CIFAR10 with linear models and 3-layer neural networks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In summary, I would like for this submission to be revised, based on concerns discussed above. Most important for me, would be to:\n* Improve the categorization of poisoning attacks in Sec. 3.\n* Include attacks based on untrainable examples.\n* Provide stronger attack scenarios in which the attack works well. The current attack budget is small, and so is attack success and this makes it hard to evaluate the work done in Sec. 3. and 4. \n* Improve the engineering of the attack to make it feasible to attack deep neural networks, for example ResNets. ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xoY58zHa3X", "reviewer": "Reviewer_tVSb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. All assumptions are explained well\n2. The Stackelberg game is explained nicely\n3. The different types of Data Poisoning attacks are explained in detail", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper summarizes a novel approach to data poisoning attacks on Neural Networks. The approach leverages TGDA(Total Gradient Descent Ascent) algorithm, which aims to address the attacker's objective. The paper talks about numerous approaches, such as how the defensive party can act to combat the attack. Their technique aims to be more effective and run on a higher magnitude. The experiment is based on the Stackelberg game, in which the attacker uses poisoned data to decrease accuracy while the defender optimizes the model using poisonous data. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "duK2Zgaamy", "reviewer": "Reviewer_mWKi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. This paper studies the cost of indiscriminate poisoning attacks.\n2. The paper proposes an efficient technique for generating a large number of poisons.\n3. The paper is well-written and easy to follow.\n\nWeaknesses\n\n1. The motivation of this study is a bit weak.\n2. The formulation of indiscriminate poisoning as Stackelberg games is somewhat unclear.\n3. The techniques proposed for the TGDA attacks are less novel.\n4. The experimental results are not sufficient to back up the paper’s claims.\n\nDetailed comments\n\n[Weak Motivation]\n\nThe TGDA attack reduces the computational costs of generating poisoning samples. However, I do not understand why the attacker may want to reduce the crafting costs. In indiscriminate poisoning, the objective is to reduce the accuracy of the target classifiers. Thus, it makes more sense to focus on reducing the number of poisoning samples the attacker injects or, with the same amount of poisoning samples, to increase an accuracy drop.\n\n\n[Stackelberg Game]\n\nI am a bit unclear about the benefits that the Stackelberg formulation brings. Typically, when we formulate a game between an attacker and a defender, we expect to explore and bind the limit of the attacker (e.g., similar to the work [1]). But, in this paper, the formulation seems to be only useful for making the poisoning sample generation faster. It raises a concern that we may not need the formulation to achieve the same goal—the TGDA attack.\n\n[1] Steinhardt et al., Certified Defenses for Data Poisoning Attacks\n\n\n[Technical Advances in the TGDA Attack]\n\nThe novelty is weak if the technical advance only reduces the time it takes to craft poisoning samples. \n\n(1) I am again not sure why it’s a limitation of a prior work that they craft poisoning samples one by one, not in a batch. What will be the scenario where the attacker is under time pressure? In my opinion, the attacker can use as much time as they want as long as they can increase the accuracy drop of the target model after poisoning.\n\n(2) It’s also a bit unclear whether the TGDA attack performs better than the others in terms of accuracy. The accuracy drop that this paper improves is from 1.52% (vs. label-flipping) /2.53 (vs. back-gradient) to 2.79% in LR trained on MNIST. I believe that this should be evaluated with multiple baselines; for example, even those two baselines, I think, will be weaker than the min-max attack proposed by Steinhardt et al.\n\n[Weak Evaluations]\n\nFirst, several benchmarks [1] evaluate the effectiveness of poisoning attacks. Thus, I believe that the claim that “there is a lack of systematic evaluation of poisoning attacks” should be toned down. At least, this should be only in the context of indiscriminate poisoning.\n\n[1] Schwarzschild et al., Just How Toxic Is Data Poisoning? A Unified Benchmark for Backdoor and Data Poisoning Attacks\n\nSecond, the paper states that there is an unfair comparison between methods. However, I don’t see any evaluation that backs up this claim. It’s unclear (1) what “fairness” means and (2) whether (if there are some benchmark that exists) it is “unfair.”\n\nThird, the clean models in CIFAR10 achieve a clean accuracy of 69%. Most recent models achieve at least 90% accuracy on CIFAR10; thus, I wouldn’t believe the impact of poisoning on those models. They could be amplified as the models used are too outdated and not good.\n\nFourth, in Sec 4.2, the attack process is designed to “thwart defenses,” but I couldn’t see the evaluation against most recent defenses (I only see one defense that seems way outdated than existing ones), such as Steinhardt et al.’s or some basic sanitization defenses. Some other work uses influence functions to identify poisoning samples. To make such claims, I think it’s necessary to evaluate the attack against existing defenses.\n\nFifth, it’s a clean-label poisoning attack. I think it is necessary to compare the magnitude of perturbations the TGDA attack introduces with the baseline attacks.\n\n\n[Minor comments]\n\n1. Backdoor attacks assume a completely different threat model (it assumes the attacker can manipulate the test-time data). I would remove the discussion about the backdoor attacks in the introduction and related work.\n2. It may not be important to show the code is on GitHub in Table 1.\n3. It’s unclear what “perfect autoencoder” in Figure 2 means.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies indiscriminate data poisoning attacks on machine learning classifiers. The paper formulates data poisoning attacks and defenses as Stackelberg games, and based on the formulation, the paper proposes Total Gradient Descent Ascent (TGDA) poisoning attacks (that is a type of clean-label poisoning attacks). The proposed attack allows an adversary to efficiently generate a large number of poisoning samples. The paper evaluates the TGDA attacks against MNIST and CIFAR-10 classifiers and shows that the attacks achieve high accuracy drops while reducing the computational time for generating poisons.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Clarification of the motivation of this attack.\n2. Clarification of the scientific advances this new formulation with Stackelberg makes.\n3. Clarification of the technical advances this attack makes (other than just proposing an efficient attack)\n4. Evaluation against many baseline indiscriminate attacks. (e.g., the paper claims the Min-max attack only works for convex models, but it seems not to be true. It does not guarantee the worst-case for non-convex models, but still works.)\n5. Evaluation to back the \"fairness\" of evaluation claims.\n6. Evaluation with the CIFAR10 models that achieve more than 90% accuracy.\n7. Evaluation against potential defense mechanisms proposed in the community.\n8. Comparison of the poisoning examples (clean-label) in terms of perturbations.", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to answer the question of whether indiscriminate poisoning attacks are feasible on modern deep neural networks. It formulates indiscriminate poisoning attacks and defenses as Stackelberg games. The Stackelberg games formulation gives a little more insight into the attacker/defender scenario by showing that who acts first matters.

Reviewer tVSb was a solicit reviewer and they ended up giving a very terse review with little substance; therefore I put little weight on their recommendation. However, both reviewers mWKi and especially TZgv gave outstanding reviews that were exceedingly detailed and they engaged with the authors. Both of them recommended Leaning Accept.

A common point of confusion was whether the reduction of computation time from the TGDA attack was of importance. I think this is crucial to the point of this work that they push for computational feasibility rather than attack efficacy.

Overall, i think this paper's results are neither significant nor its methods novel. However, based on TMLR's acceptance criteria (https://www.jmlr.org/tmlr/acceptance-criteria.html) which says ...

"Crucially, it should not be used as a reason to reject work that isn't considered “significant” or “impactful” because it isn't achieving a new state-of-the-art on some benchmark. Nor should it form the basis for rejecting work on a method considered not “novel enough”, as novelty of the studied method is not a necessary criteria for acceptance. We explicitly avoid these terms (“significant”, “impactful”, “novel”), and focus instead on the notion of “interest”. If the authors make it clear that there is something to be learned by some researchers in their area from their work, then the criteria of interest is considered satisfied"

... I think it's reasonable to give this paper an accept because it provided clear, evidence-backed results, along with an interesting formulation, that are of interest to a portion (albeit limited) of the data poisoning community.

Authors: before camera-ready, please address the revisions from the reviewers. Further please revise the following:
Tone down the claim that other works crafted poison points sequentially. For example, both MetaPoison and Witches Brew crafted their poison points in batches and those poison points can coordinate with one another during the crafting.
Decision: Accept (poster)