Exploring the Limits of Model-Targeted Indiscriminate Data Poisoning Attacks

Yiwei LuUW,VI
Gautam KamathUW,VI
Yaoliang YuUW,VI

UWSchool of Computer Science, University of Waterloo, Canada
VIVector Institute

Yiwei<EMAIL_ADDRESS>
Machine Learning, data poisoning

Authors GK and YY are listed in alphabetical order.

Indiscriminate data poisoning attacks aim to decrease a model's test accuracy by injecting a small amount of corrupted training data.
Despite significant interest, existing attacks remain relatively ineffective against modern machine learning (ML) architectures.
In this work, we introduce the notion of model poisoning reachability as a technical tool to explore the intrinsic limits of data poisoning attacks towards target parameters (i.e., model-targeted attacks). We derive an easily computable threshold to establish and quantify a surprising phase transition phenomenon among popular ML models: data poisoning attacks can achieve certain target parameters only when the poisoning ratio exceeds our threshold. Building on existing parameter corruption attacks and refining the Gradient Canceling  attack, we perform extensive experiments to confirm our theoretical findings, test the predictability of our transition threshold, and significantly improve existing indiscriminate data poisoning baselines over a range of datasets and models.
Our work highlights the critical role played by the poisoning ratio, and sheds new insights on existing empirical results, attacks and mitigation strategies in data poisoning. Our code is available at <https://github.com/watml/plim>.

§ BACKGROUND

Data poisoning, an emerging concern on modern ML systems, refers to the threat of (often passively) crafting “poisoned” training data so that  systems retrained on it (along with possibly clean in-house data) are skewed towards certain behaviour.
For example, indiscriminate data poisoning <cit.> aims to decrease the overall test accuracy while targeted data poisoning <cit.> only affects certain classes. Backdoor attacks <cit.> that aim to trigger a particular pattern, and unlearnable examples <cit.> that aim to protect user data.

While many algorithms have been proposed for data poisoning, their effectiveness remains largely underwhelming against neural networks, especially when $\epsilon_d$, the relative proportion of poisoned data, is small. For example, Figure 4 of <cit.> and Table 2 of <cit.> revealed that SOTA attacks can only decrease the test accuracy noticeably when $\epsilon_d$ is sufficiently (and sometimes exceedingly, e.g., $\epsilon_d>100\%$) large. These attacks, relying on sophisticated optimization tricks, are also rather expensive to run.
On the other hand, any data poisoning attack amounts to an indirect way of rewiring an ML model (, any change must be induced by retraining the model over clean and poisoned data). Direct approaches, such as the gradient-based parameter corruption (GradPC) attack of <cit.>, seek to overwrite a target model directly (, without constructing any poisoned data or retraining), under a perturbation constraint specified by $\epsilon_w$, , the relative change of the model parameter should be less than $\epsilon_w$. While the applicability of direct approaches may seem limited, they are suitable for exploring the limits of more realistic data poisoning attacks.

In <Ref> we compare the performance of the direct approach GradPC <cit.> and the indirect approach TGDA <cit.>. The latter adds $\epsilon_d = 3\%$ poisoned data while both attacks yield comparable perturbations of the (clean) model, as measured by $\epsilon_w$.
The difference is significant, and begs the obvious question: what caused this difference? Is it because existing data poisoning attacks are not sufficiently optimized yet, or is there some intrinsic barrier to produce certain target parameters through data poisoning? To what extent would increasing $\epsilon_d$ help, and how do we know without trying every $\epsilon_d$? These questions will be formally and experimentally explored in the sequel, with the ultimate goal (if possible) to reduce the gap between data poisoning and parameter corruption attacks with comparable $\epsilon_w$, as highlighted in <Ref>.

The attack accuracy/accuracy drop (%) on  MNIST.

Clean     TGDA     2cGradPC

Acc.     Accuracy/Drop     $\epsilon_w=0.5$    $\epsilon_w=1$

LR     92.35     89.56 / 2.79 ($\epsilon_w =2.45$)     69.80 / 22.55     21.48 / 70.87

NN     98.04     96.54 / 1.50 ($\epsilon_w =0.55$)     76.51 / 20.03     31.14 / 66.90

CNN     99.13     98.02 / 1.11 ($\epsilon_w =0.74$)     73.24 / 24.78     12.98 / 86.15

Connection with Learning Theory:
There has been significant work on training-time robustness in the learning theory literature, primarily focused on poisoning worst-case distributions. Two models of robust PAC learning <cit.>, slightly rephrased for the sake of comparison, include the malicious noise model, where the adversary adds points <cit.>, and the nasty noise model, where the adversary may both add and remove points <cit.>.
Many of these theoretical results show strong computational barriers against robust learning for even the most basic problems.
Although our setting is similar to the malicious noise model (and we touch a bit on the nasty noise model in <Ref>), there are three major differences with the majority of the theory literature: (1) our attacks address distributions that arise in practice, which differ from worst-case distributions; (2) while other attacks flip labels, we consider “clean label” attacks which are not visibly mislabeled; (3) we focus on model-targeted attacks whose goal is to induce certain target parameters while the above-mentioned references focus directly on decreasing accuracy on the test sample.

§ THEORETICAL RESULTS

In this section we formalize the notion of model poisoning reachability as a technical tool for studying model-targeted data poisoning. We further derive an easily computable threshold $\tau$ and reveal that model-targeted data poisoning attacks are effective only when $\epsilon_d$, the (relative) percentage of poisoning data, crosses $\tau$.

Notation and Preliminaries. Let $\ell(\zv, \wv)$ be our loss that measures the fitness of our model $\wv$ on data $\zv \in \Zds$, , $\zv = (\xv, y)$ for supervised learning and $\zv = \xv$ for unsupervised learning. Let $\Pcal = \Pcal(\Zds)$ denote the set of all distributions on $\Zds$, and we abstract the training data as an (empirical) distribution[For convenience in this work we do not distinguish the (clean) training set from the training distribution, , $\mu$ can be empirical.] $\mu\in \Pcal$. For any given model $\wv$ and training distribution $\mu$, is it possible to construct a poisoning set, denoted by another (empirical) distribution $\nu$, such that $\wv$ minimizes $\ell$ over the mixed distribution $\chi = (1-\lambda)\mu + \lambda \nu$, where $\lambda = \tfrac{\epsilon_d}{1+\epsilon_d} \in [0,1]$ is the proportion of poisoning data.
To account for possible nonconvexity of the loss $\ell$, we relax the optimality of a model $\wv$ to simply have vanishing (sub)gradient. More formally, let

\begin{align}
\label{eq:grad-point}
\gv(\zv) = \gv(\zv; \wv) = \nabla_{\wv} \ell(\zv; \wv)
\end{align}

be the gradient vector with respect to a fixed model $\wv$ evaluated at the data $\zv$.
For practical reasons (, to evade possible defenses or to account for the technical capabilities of an attacker) we also restrict the poisoning distribution $\nu$ into a convex subset $\Gamma \subseteq \Pcal$ of admissible distributions. For instance, we may consider

\begin{align}
\Gamma = \Gamma_{\mu, \delta} := \{\gamma: \|\gamma - \mu\| \leq \delta\},
\end{align}

where $\|\cdot\|$
denotes (say) the Wasserstein distance.
By definition we always have $\mu \in \Gamma$.
For each $\nu \in \Gamma$, define

\begin{align}
\gv(\nu) = \gv(\nu; \wv) := \EE_{\zv \sim \nu} \gv(\zv; \wv),
\end{align}

i.e., the average gradient the distribution $\nu$. Clearly,

\begin{align}
\label{eq:grad-set}
\Gfk = \Gfk(\Gamma) := \{\gv(\nu): \nu \in \Gamma\}
\end{align}

is a subset of the closed convex hull of all gradient vectors. In fact, equality holds when $\Gamma=\Pcal$ (, $\delta = \infty$).

§.§ Model Poisoning Reachability

We can now state our fundamental problem of interest:

We say a target parameter $\wv$ is $(\ell, \mu, \Gamma, \lambda)$-poisoning reachable
if there exists some poisoning distribution $\nu\in\Gamma$ such that

\begin{align}
\gv(\chi; \wv)
= (1-\lambda) \gv(\mu; \wv) + \lambda \gv(\nu; \wv) = \zero,
\end{align}

, the parameter $\wv$ has vanishing gradient (loss $\ell$) over the mixed distribution $\chi = (1-\lambda) \mu + \lambda \nu$.

When the loss $\ell$, training distribution $\mu$, and admissible poisoning distributions $\Gamma$ are evident, we will simply say the parameter $\wv$ is $\lambda$-poisoning reachable, or poisoning reachable if it is $\lambda$-poisoning reachable for some $\lambda \in [0,1]$.

We make three further remarks regarding <Ref>: (a) If we are interested in more quantitative results about data poisoning, for example, is it possible to craft a poisoning set such that retraining on the mixed distribution would decrease test accuracy by a large margin, we need only specify a set of target models $\wv \in \Wcal$ that all decrease the test accuracy as required[As pointed out by a reviewer, this may not be computationally feasible if one is too ambitious about the set $\Wcal$.], and we say data poisoning is successful if any $\wv \in \Wcal$ is ($\lambda$-) poisoning reachable.
(b) <Ref> leaves out the computational aspects of data poisoning, , how efficiently we can find such a poisoning distribution $\nu$ (whenever it exists). This will be studied in <Ref>, using a gradient-based algorithm inspired directly by our definition.
(c) We could also add other requirements, such as curvature or stability, to <Ref>.

Given the above formalization, the following characterization is immediate:

A target parameter $\wv$ is $\lambda$-poisoning reachable iff
\zero \in \Gfk^\lambda = \Gfk^\lambda(\gv(\mu)) := \{(1 - \lambda) \gv(\mu) + \lambda \gv: \gv \in \Gfk\}.

Since $\Gfk$ (see equations (<ref>)-(<ref>)) is clearly convex, the subsets $\Gfk^\lambda$ are all convex
and increasing with respect to $\lambda$, ,

\begin{align}
\gv(\mu) = \Gfk^0 \subseteq \Gfk^\lambda \uparrow \subseteq \Gfk^1 = \Gfk. \nonumber
\end{align}

Recall that $\lambda = \tfrac{\epsilon_d}{1+\epsilon_d}$
is the (absolute) proportion of the poisoned set. Thus, we conclude intuitively that the larger $\epsilon_d$ (equivalently $\lambda$) is, the easier it is to induce any target model $\wv$ on any training distribution $\mu$.
In particular, the special case $\lambda = 1$ corresponds to the so-called “unlearnable examples” <cit.>, where an attacker is allowed to change the entire training set (, empirical distribution $\mu$).

Conversely, we can also conclude from <Ref> that if $\zero \not \in \Gfk(\Gamma)$, then data poisoning, with any budget $\epsilon_d$, will not be successful in producing the target parameter $\wv$. If $\zero \not \in \Gfk(\Pcal)$, then no training distribution can yield $\wv$. In particular, data poisoning will not be successful in producing $\wv$ even if $\epsilon_w = \infty$.

Let us give some examples to illustrate our results so far.
[Least-square regression]

\begin{align}
\ell(\zv; \wv) = \tfrac12 (y - \wv^\top \xv)^2, \mbox{ where }\  \zv = (\xv, y).\nonumber
\end{align}

Clearly, we have

\begin{align}
\gv(\xv, y) &= (\wv^\top \xv - y) \xv = (\xv \xv^\top) \wv - y \xv, \nonumber
\end{align}

and hence $\gv(\mu) = \Sigma \wv - \mv$,
where $\Sigma = \EE_{\xv \sim \mu}\xv\xv^\top$ and $\mv = \EE_{(\xv, y) \sim \mu} y\xv$.
For simplicity let us assume $\Zds = \RR^d \times \RR$ and $\Gamma = \Pcal$ so that $\Gfk = \RR^d$ (by considering product distributions where $\xv$ concentrates on a single point).
Therefore, we conclude from <Ref> that data poisoning with any $\epsilon_d > 0$ is possible for least-square regression.
The same conclusion holds even if we add regularization to $\wv$ (which, we recall, is fixed).

§.§ Scalar Output Linear Models

For linear models we can further simplify the iff condition in <Ref>.
We begin with the following result:

Suppose $\Gamma = \Pcal$ contains all distributions, $\ell((\xv, y); \wv) = l(\wv^\top \xv, y)$ for some univariate loss $l$, and $\inner{\wv}{\gv(\mu)} \ne 0$. Then, $\wv$ is $\lambda$-poisoning reachable iff

\begin{align}
\label{eq:linearthreshold}
\lambda &> \max\left\{\tfrac{\inner{\wv}{\gv(\mu)}}{\inner{\wv}{\gv(\mu)} -a}, ~  \tfrac{-\inner{\wv}{\gv(\mu)}}{b - \inner{\wv}{\gv(\mu)}} \right\}, \quad \mbox{where}
\\
a &= \inf_{(\xv, y)\in \Zds}  (\wv^\top\xv) \cdot l'(\wv^\top\xv, y),\nonumber \\
b &= \sup_{(\xv, y) \in \Zds}  (\wv^\top\xv) \cdot l'(\wv^\top\xv, y),\nonumber
\end{align}

with equality attained if the maximum is attained.

<Ref> follows from the more general <Ref> in <Ref>, where we further remove the restriction $\Gamma = \Pcal$.
The condition $\inner{\wv}{\gv(\mu)} \ne 0$ can be checked easily a priori; see <Ref> (<Ref>) for discussions on when it fails.
<Ref> (<Ref>) draws further connection between our result and the breakdown point in robust statistics.
Compared to the more general <Ref>, <Ref> exploits the linear structure to simplify the set $\Gfk$ to basically an interval and hence the condition (<ref>) is much easier to verify. Indeed, consider <Ref> again. It is clear that $l'(t, y) = t-y$, whence $a=-\infty$ and $b=\infty$. Thus, we verify more easily that data poisoning succeeds on least-square regression for any $\epsilon_d > 0$.

Logistic regression on the 2d OR dataset that verifies the transitioning threshold $\tau$ in <Ref>.
Left: $\tau$ target models $\wv\in\RR^2$, which all achieve 0 accuracy; Middle: accuracy drop due to the gradient canceling attack in <Ref>. Indeed, poisoning successfully induces the target model $\wv$ as long as $\epsilon_d\geq \tau$;  Right: norm of gradient model $\wv$ over the mixed distribution $\chi$, with $\epsilon_d$ the relative proportion of poisoned data. In general, the closer $\epsilon_d$ gets above $\tau$, the smaller the gradient norm, which is an indication of the target model being more achievable through data poisoning.

The next example reveals a surprising phase transition in terms of the poisoning proportion $\lambda$ (or equivalently $\epsilon_d$):
[Logistic regression]
Consider now

\begin{align}
\ell(\zv; \wv) = \log(1+\exp(-\wv^\top\tilde\xv)),\nonumber
\end{align}

where we have absorbed the binary label $y$ into $\tilde\xv$ (, $\tilde\xv \gets y \xv$).
Clearly, we have
$    \gv(\tilde\xv) = -\tfrac{1}{1+\exp(\wv^\top\tilde\xv)} \tilde\xv$.
On the direction $\wv$, for any distribution $\mu$ we have

\begin{align}
\!\!-\Wfk(\tfrac1e) \!=\! \inf_{t} \tfrac{-t}{1+\exp(t)} \leq \inner{\wv}{\gv(\mu)} \leq \sup_{t} \tfrac{-t}{1+\exp(t)},\nonumber
\end{align}

where the left-hand side is Lambert's W function and the right-hand side is clearly $\infty$. Therefore, suppose $\Xds = \RR^d$ and $\Gamma = \Pcal$, we have

\begin{align}
\Gfk = \{\gv: \wv^\top \gv \geq - \Wfk(1/e) \approx -0.28\},\nonumber
\end{align}

which is not the entire space! Consequently, if

\begin{align}
\lambda < \tfrac{\inner{\wv}{\gv(\mu)}}{\inner{\wv}{\gv(\mu)} + \Wfk(1/e)} \iff \epsilon_d < \tau := \max\{\tfrac{\inner{\wv}{\gv(\mu)}}{\Wfk(1/e)}, 0\},   \label{eq:transition}
\end{align}

then any poisoning distribution $\nu$ (with any support) cannot
produce $\wv$ (along with training distribution $\mu$)!

By simply changing $\tilde\xv \gets y\xv$ and then dropping $y$ we immediately obtain from <Ref> sufficient and necessary conditions for the poisoning reachability of binary margin classifiers. In particular, we record the following result:

Consider linear models with loss $\ell(\tilde\xv; \wv) = l(\wv^\top \tilde\xv)$.

Suppose $\Gamma = \Pcal$ consist of all distributions on $\tilde\Xds$ and $\inner{\wv}{\gv(\mu)}\ne 0$.

\begin{align}
a := \inf_{t\in \wv^\top\tilde\Xds} t \cdot l'(t), \quad
b := \sup_{t\in \wv^\top\tilde\Xds} t \cdot l'(t).\nonumber
\end{align}

a target parameter $\wv$ is $\lambda$-poisoning reachable iff
(<ref>) holds (with equality attained if the maximum there is attained).

The standard margin losses are decreasing, such as the logistic loss in <Ref>, the exponential loss in Adaboost, and the hinge loss in SVM.
When $\Xds = \RR^d$ is unbounded, typically $b=\infty$ but $a > -\infty$, leading to a common phase transition phenomenon: data poisoning against these losses succeeds in producing a target parameter $\wv$ iff $\lambda$ crosses the threshold in (<ref>). In particular, any target parameter $\wv$ such that $\inner{\wv}{\gv(\mu)} < 0$ is always poisoning reachable for any $\lambda > 0$.
Interestingly, <cit.> showed that if a model is poisoning reachable, then it (often) can be poisoned to by a distribution $\nu$ supported on two distinct points (which however does not imply diminishing $\epsilon_d$ due to repetitions). <Ref> provides a definitive answer on when a model is poisoning reachable and hence complements the results of <cit.>.

We emphasize that with any further restrictions on the poisoning distribution (such that $\Gamma \subsetneq \Pcal$), condition (<ref>) remains to be necessary: data poisoning is apparently even harder in this case.
For nonlinear models with a fixed feature map $\phi$ (such as kernel methods), our results extend immediately, after the obvious change-of-variable $\xv \gets \phi(\xv)$.

<Ref> illustrates the transition threshold $\tau$ in (<ref>) on the simple OR dataset (where each of the four points is repeated 50 times with small Gaussian perturbation, see <Ref> for details). Logistic regression (LR), trained on the clean data, achieves perfect accuracy. In <Ref> (left), each grid point represents a target parameter $\wv = (w_1, w_2)$, all of which achieve 0 test accuracy (, malicious models). The heat map indicates the threshold $\tau$ for each $\wv$, which, as predicted by our theory, is the percentage of poisoning required to achieve $\wv$ through retraining. In <Ref> (middle) we run the gradient canceling attack (see <Ref>) with varying percentage $\epsilon_d$ and verify that indeed we can reduce the 100% clean accuracy to 0% iff $\epsilon_d \geq \tau$. In <Ref> (right) we plot the magnitude of the gradient of the target parameter $\wv$ over the mixed dataset (clean training data plus poisoned data), as an approximate measure of how close $\wv$ can be achieved by retraining on the mixed dataset.
Overall, the larger $\epsilon_d$ is, the larger the accuracy drop is (not surprisingly) and the smaller the gradient norm is, with a clear transition once $\epsilon_d$ crosses $\tau$ (perhaps surprisingly).

§.§ Multiple Output Linear Models

Next, we extend our results to multiple outputs (classes):
Consider $\ell(\xv, \yv; W) = l(W^\top\xv, \yv)$ for some loss $l$.
Then[We use the notation $\av \otimes \bv := \av \bv^\top$ for two column vectors.],

\begin{align}
\label{eq:mc-gradw}
G(\xv, \yv) := \nabla_{W}\ell(\xv, \yv; W) &= \xv \otimes \nabla l(W^\top\xv, \yv).
\end{align}

Suppose $W^\top G(\mu)$ is non-degenerate and $\Gamma = \Pcal$ contains all distributions.
Then, $W$ is $\lambda$-poisoning reachable

\begin{align}
\label{eq:mc-mp2}
\zero \in (1-\lambda) W^\top G(\mu) + \lambda \{W^\top G(\nu): \nu \in \Gamma\}.
\end{align}

Compared to <Ref>, condition (<ref>) is no longer univariate but a square matrix of dimensions the same as $\yv$ (the output).
Nevertheless, we may simply take the trace on both sides to arrive at an easier albeit only necessary condition.
We illustrate the last point through a familiar example:
Let $\hv = W^\top \xv$.
The cross-entropy loss corresponds to

\begin{align}
l(\hv, \yv) &= -\inner{\hv}{\yv} + \log \sum\nolimits_k \exp h_k,\nonumber
\end{align}

where $\yv$ is one-hot. Taking trace on (<ref>) we obtain

\begin{align}
0 &= (1-\lambda) g(\mu) + \lambda g(\nu), \mbox{ where } \nonumber\\
g(\nu) &= \EE_{(\xv,\yv) \sim \nu} \inner{\hv}{\pv-\yv},\nonumber
\end{align}

and $\pv := \softmax(\hv) = \exp(\hv) / \sum_k \exp(h_k)$.
In <Ref> we prove the tight bound
\leq g(\nu) \leq
\infty$,
leading to the necessary condition for inducing $W$:

\begin{align}
\label{eq:tau}
\epsilon_d \geq \tau = \tau(c) := \max\{\inner{W}{G(\mu)}/\Wfk(\tfrac{c-1}{e}), 0\},
\end{align}

where $c$ is the number of classes. When $c=2$, we recover the sufficient and necessary condition in (<ref>).

We remark that all of our results continue to hold as necessary (but may not be sufficient) conditions for neural networks where the input $\xv$ goes through a learned feature transformation $\varphi(\xv; \uv)$, parameterized by $\uv$:
[Neural Networks]theoremNN
Consider $\ell(\xv, \yv; W, \uv) = l(\hv, \yv)$ for some loss $l$, where $\hv := W^\top \varphi(\xv; \uv)$.

\begin{align}
\label{eq:nn-gradw}
\nabla_{W}\ell(\xv, \yv; W, \uv) &= \varphi(\xv;\uv) \otimes \nabla_{\hv} l(\hv, \yv) \\
\label{eq:nn-gradu}
\nabla_{\uv}\ell(\xv, \yv; W, \uv) &= \nabla_{\uv}\varphi(\xv;\uv) W \nabla_{\hv} l(\hv, \yv),
\end{align}

and $(W, \uv)$ is $\lambda$-poisoning reachable iff there exists $\nu \in \Gamma$ such that

\begin{align}
\label{eq:nn-grad}
\zero \in (1-\lambda) G(\mu) + \lambda G(\nu),
\end{align}

where $G(\nu) := \EE_{(\xv, \yv)\sim\nu} \left(\nabla_{W}\ell, \nabla_{\uv}\ell \right)$.
In particular, $(W, \uv)$ is $\lambda$-poisoning reachable only if there exists some $\nu\in\Gamma$ such that

\begin{align}
\label{eq:nn-grad-W}
\zero \in (1-\lambda) G_1(\mu) + \lambda G_1(\nu),
\end{align}

where $G_1(\nu) := \EE_{(\xv,\yv) \sim \nu} \varphi(\xv; \uv) \otimes \nabla_{\hv} l(\hv, \yv)$.

§.§.§ Acknowledgments

We thank the reviewers for the critical comments that have largely improved the presentation and precision of this paper.
We gratefully acknowledge funding support from NSERC and the Canada CIFAR AI Chairs program.
Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

booktitleIEEE European Symposium on Security and Privacy (EuroS&P)
titleBullseye polytope: A scalable clean-label poisoning attack with improved transferability

booktitleNeurIPS Workshop on Trustworthy and Socially Responsible Machine Learning
titleBenchmarking the Effect of Poisoning Defenses on the Security and Bias of the Final Model

booktitleProceedings of Thirty Fifth Conference on Learning Theory
titleRobustly-reliable learners under poisoning attacks

journaltitleJournal of the American Statistical Association
titleConvexity, classification, and risk bounds

booktitleProceedings of the 29th International Conference on Machine Learning (ICML)
titlePoisoning attacks against support vector machines

journaltitleTheoretical Computer Science
titlePAC learning with nasty noise

ACM New York, NY, USA

journaltitleJournal of the ACM (JACM)
titleSample-efficient strategies for learning in the presence of noise

titleTargeted backdoor attacks on deep learning systems using data poisoning

notearXiv preprint arXiv:1707.08819
titleA downsampled variant of ImageNet as an alternative to the CIFAR datasets

journaltitleIEEE Signal Processing Magazine
titleThe MNIST database of handwritten digit images for machine learning research

booktitleProceedings of the 36th International Conference on Machine Learning
titleSever: A Robust Meta-Algorithm for Stochastic Optimization

notearXiv preprint arXiv:2103.02683
titlePreventing unauthorized use of proprietary data: Poisoning for secure dataset release

booktitleAdvances in Neural Information Processing Systems
titleAdversarial Examples Make Strong Poisons

journaltitleIEEE Transactions on Neural Networks and Learning Systems
titleClassification in the Presence of Label Noise: A Survey

booktitleInternational Conference on Learning Representations
titleRobust unlearnable examples: Protecting data privacy against adversarial learning

notearXiv preprint arXiv:2101.00027
titleThe Pile: An 800GB Dataset of Diverse Text for Language Modeling

booktitleInternational Conference on Learning Representations
titleWitches' Brew: ial Scale Data Poisoning via Gradient Matching

journaltitleIEEE Transactions on Pattern Analysis and Machine Intelligence
titleDataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses

booktitleIEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)
titleMaxUp: Lightweight Adversarial Training with Data Augmentation Improves Neural Network Training

titleBadnets: Identifying vulnerabilities in the machine learning model supply chain

booktitleEuropean Conference on Computer Vision
titlePractical Poisoning Attacks on Neural Networks

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition
titleDeep Residual Learning for Image Recognition

booktitleInternational Conference on Learning Representations
titleUnlearnable Examples: Making Personal Data Unexploitable

booktitleProceedings of the 39th International Conference on Machine Learning
titleDatamodels: Predicting predictions from training data

booktitleProceedings of the twentieth annual ACM symposium on Theory of computing
titleLearning in the presence of malicious errors

booktitleProceedings of the 34th International Conference on Machine Learning (ICML)
titleUnderstanding black-box predictions via influence functions

journaltitleMachine Learning
titleStronger Data Poisoning Attacks Break Data Sanitization Defenses

notetech. report
titleLearning multiple layers of features from tiny images

booktitleIEEE Security and Privacy Workshops (SPW)
titleAdversarial machine learning-industry perspectives

booktitleInternational Conference on Learning Representations
titleDeep Partition Aggregation: Provable Defense against General Poisoning Attacks

journaltitleMachine learning
titleMining adversarial patterns via regularized loss minimization

booktitleInternational Conference on Learning Representations
titleSGDR: Stochastic gradient descent with warm restarts

journaltitleTransactions on Machine Learning Research
titleIndiscriminate Data Poisoning Attacks on Neural Networks

notearXiv preprint arXiv:2003.02133
titleThreats to federated learning: A survey

booktitleProceedings of the 10th ACM Workshop on Artificial Intelligence and Security (AISec)
titleTowards Poisoning of Deep Learning Algorithms with Back-gradient Optimization

journaltitleAdvances in neural information processing systems
titleLearning with noisy labels

titleExploiting machine learning to subvert your spam filter.

booktitleAdvances in Neural Information Processing Systems 32
titlePyTorch: An Imperative Style, High-Performance Deep Learning Library

booktitleProceedings of the AAAI Conference on Artificial Intelligence
titleHidden trigger backdoor attacks

booktitleAdvances in Neural Information Processing Systems
titleAutoregressive Perturbations for Data Poisoning

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titlePoison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks

booktitleIEEE Symposium on Security and Privacy (SP)
titleBack to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning

booktitleProceedings of the AAAI Conference on Artificial Intelligence
titleExploring the vulnerability of deep neural networks: A study of parameter corruption

booktitleProceedings of the 38th International Conference on Machine Learning
titleModel-targeted poisoning attacks with provable convergence

booktitleInternational Conference on Learning Representation
titleIntriguing properties of neural networks

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleSpectral Signatures in Backdoor Attacks

journaltitleBBC News
titleMicrosoft chatbot is taught to swear on Twitter

booktitleAdvances in Neural Information Processing Systems
titleLethal Dose Conjecture on Data Poisoning

booktitleInternational Conference on Machine Learning
titleImproved certified defenses against data poisoning with (deterministic) finite aggregation

booktitleProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
titleAvailability Attacks Create Shortcuts

booktitleAdvances in Neural Information Processing Systems 26
titleA Polynomial-time Form of Robust Regression

journaltitleNeural Networks
titleAdversarial parameter defense by multi-step risk minimization

booktitleInternational Conference on Machine Learning
titleTransferable clean-label poisoning attacks on deep neural nets

§ PROOFS

[Linear Models]theoremLinearModel
Consider $\ell((\xv, y); \wv) = l(\wv^\top \xv, y)$ for some univariate loss
$l$. Then,

\begin{align}
\gv(\xv, y) = \xv \cdot l'(\wv^\top \xv, y), \nonumber
\end{align}

and $\wv$ is $\lambda$-poisoning reachable iff there exists $\nu\in\Gamma$ such that

\begin{align}
0 \in (1-\lambda)\gv(\mu) + \lambda \gv(\nu).\nonumber
\end{align}

Suppose $\inner{\wv}{\gv(\mu)} \ne 0$. Consider $\Pi \subseteq \Pcal$ and

\begin{align}
\!\! \gfk := \{ \EE_{(\xv, y) \sim \nu} (\wv^\top\xv) \cdot l'(\wv^\top\xv, y): \nu \in \Pi \} \subseteq \RR.\nonumber
\end{align}

Then, $\wv$ is $\lambda$-poisoning reachable
if [$T_{\#}\nu$ denotes the distribution of $T(\zv)$ when $\zv \sim\nu$.] $\Gamma \supseteq T_{\#}\Pi$ and

\begin{align}
\label{eq:mp1}
0 \in (1-\lambda) \inner{\wv}{\gv(\mu)} + \lambda \gfk,
\end{align}

where the transformation $T(\xv, y) := \left(\tfrac{\inner{\wv}{\xv}}{\inner{\wv}{\gv(\mu)}} \gv(\mu), y \right)$.
Conversely, (<ref>) holds if $\wv$ is $\lambda$-poisoning reachable and $\Pi \supseteq \Gamma$.

The gradient computation is straightforward while the first claim follows from <Ref>.

Suppose now $\inner{\wv}{\gv(\mu)} \ne \zero$.

Suppose first (<ref>) holds, so we can choose $\nu \in \Pi$ such that

\begin{align}
0 = (1-\lambda) \inner{\wv}{\gv(\mu)} + \lambda \EE_{(\xv,y) \sim \nu} (\wv^\top\xv) \cdot l'(\wv^\top\xv , y).
\end{align}

Consider the transformation $T(\xv, y) = \left(\tfrac{\inner{\wv}{\xv}}{\inner{\wv}{\gv(\mu)}} \gv(\mu), y\right)$ and let $\tilde\nu = T_{\#}\nu$, which is in $\Gamma$ due to our assumption $\Gamma \supseteq T_{\#}\Pi$. We then have

\begin{align}
\EE_{(\tilde\xv, \tilde y) \sim \tilde\nu} l'(\wv^\top\tilde\xv, \tilde y) \tilde\xv = \EE_{(\xv, y) \sim \nu} l'(\wv^\top\xv, y) \tfrac{\inner{\wv}{\xv}}{\inner{\wv}{\gv(\mu)}} \gv(\mu),
\end{align}

and hence

\begin{align}
(1-\lambda) \gv(\mu) + \lambda \EE_{(\tilde\xv,\tilde y) \sim \tilde\nu} \nabla \ell((\tilde\xv, \tilde y); \wv)
[(1-\lambda) \inner{\wv}{\gv(\mu)} + \lambda \EE_{(\xv,y) \sim \nu} l'(\wv^\top\xv, y) \inner{\wv}{\xv}] \tfrac{\gv(\mu)}{\inner{\wv}{\gv(\mu)}}
\\
&= \zero,
\end{align}

thanks to our choice of $\nu$. Applying <Ref> again we know $\wv$ is $\lambda$-poisoning reachable.

Conversely, if $\wv$ is $\lambda$-poisoning reachable, then from <Ref> it follows that

\begin{align}
\zero \in (1-\lambda) \gv(\mu) + \lambda \EE_{(\xv,y)\sim\nu} l'(\wv^\top\xv , y) \xv.
\end{align}

Taking inner product with the model $\wv$ on both sides and noting that $\Gamma \subseteq \Pi$ we verify (<ref>).

The condition $\inner{\wv}{\gv(\mu)} \ne 0$ can be easily checked a priori. In case it fails, two possibilities arise:

* $\gv(\mu) = \zero$, in which case poisoning is trivial: simply let $\nu = \mu$ for any $\lambda$.

* $\gv(\mu) \ne \zero$, in which case we may let $\nu$ concentrate on the line $L := \{\alpha \gv(\mu): \alpha \in \RR\}$. Thus, data poisoning succeeds if

\begin{align}
0 = (1-\lambda) + \lambda \EE_{(\alpha, y)\sim \nu} l'(0, y) \alpha,
\end{align}

where we identify $\alpha \gv(\mu)$ as $\alpha$ for $\nu$. As long as $\Gamma$ contains some distribution that puts nonzero mass on $L$ and sufficiently large $l'(0,y)$, $\wv$ is again $\lambda$-poisoning reachable.

Once we identify an appropriate subset $\Pi$ of poisoning distributions, we can even estimate the interval $\gfk$ using Monte Carlo algorithms.
Moreover, we may restrict the search of a poisoning distribution to the potentially much smaller subset $T_{\#}\Pi$ (where $\xv$ lies on the line spanned by $\gv(\mu)$).

For simplicity consider $\Zds = \RR^d \times \RR$.
It is well-known that unbounded convex losses $(t,y) \mapsto l(t-y)$, such as the square loss in <Ref>, have 0 breakdown point (and hence not robust): even adding a single poisoning point can perturb the model norm $\|\wv\|$ unboundedly <cit.>.
<Ref> gives a much more detailed characterization: In fact, any target model $\wv$ can be induced by a diminishing amount of poisoning (even if $\nu$ is supported on a single point)! Indeed, since $l$ is unbounded and convex, there exists some $\tau\in\RR$ such that $| l'(\tau)| \ne 0$. It follows then $a = -\infty$ and $b = \infty$, and hence the threshold in (<ref>) is trivially 0, for any target model $\wv$.
Of course, our characterization in <Ref> continues to hold for any domain $\Zds$, unbounded or not.

Consider the smooth loss[This is essentially a smoothed version of the perceptron loss $l(t) = \max\{-t, 0\}$.]

\begin{align}
\label{eq:dich}
%\ell(\xv, \wv) = l(\xv^\top\wv), ~
l(t) = \begin{cases}
-(4t+1)\exp(-2), & \mbox{ if } t \leq -\tfrac12 \\
\exp(\tfrac1t), & \mbox{ if } t \in [-\tfrac12,0] \\
0, & \mbox{ if } t \geq 0
\end{cases}
\end{align}

Clearly, we have $a = 0$ and $b=\infty$. Thus, we arrive at a remarkable dichotomy:

* If $\inner{\wv}{\gv(\mu)} = 0$ (in particular any separating $\wv$), then data poisoning succeeds with any $\lambda > 0$;

* If $\inner{\wv}{\gv(\mu)} \ne 0$ (and hence $\wv$ cannot separate $\mu$), then data poisoning fails with any $\lambda < 1$.

Note that $l$ in (<ref>) is not calibrated since $l'(0) = 0$ <cit.>, so it may not be a sensible loss to use in practice. For a calibrated margin loss $l$, , one that is differentiable at 0 with $l'(0) < 0$, we necessarily have $ b > 0$ and $a < 0$, so the threshold in (<ref>) usually lies strictly in $(0,1)$, incurring a nontrivial phase transitioning.

Consider the hinge loss

\begin{align}
\ell(\zv, \wv) = \max\{1-\wv^\top\zv, 0\},
\end{align}

where $l(t) = \max\{1-t, 0\}$. Clearly, we have $a = -1$ and $b=\infty$. It is clear that SVM can produce any model $\wv$, with a suitably chosen training distribution $\mu$. For example, simply let $\mu$ support on two points that has $\wv$ in the middle.

Consider $\ell(\xv, \yv; W) = l(W^\top\xv, \yv)$ for some loss $l$.
Then[We use the notation $\av \otimes \bv := \av \bv^\top$ for two column vectors.],

\begin{align}
\label{eq:mc-gradw-app}
G(\xv, \yv) := \nabla_{W}\ell(\xv, \yv; W) &= \xv \otimes \nabla l(W^\top\xv, \yv),
\end{align}

and $W$ is $\lambda$-poisoning reachable iff there exists $\nu \in \Gamma$ such that

\begin{align}
\label{eq:mc-grad-app}
\zero \in (1-\lambda) G(\mu) + \lambda G(\nu).
\end{align}

Suppose $W^\top G(\mu)$ is non-degenerate and let

\begin{align}
\gfk := \{ \EE_{(\xv, \yv) \sim \nu} (W^\top\xv) \otimes \nabla l(W^\top\xv, \yv): \nu \in \Pi \}. \nonumber
\end{align}

Then, $W$ is $\lambda$-poisoning reachable
if $\Gamma \supseteq T_{\#}\Pi$ and

\begin{align}
\label{eq:mc-mp}
\zero \in (1-\lambda) W^\top G(\mu) + \lambda \gfk,
\end{align}

where the transformation $T(\xv, \yv) := \left(G(\mu) [W^\top G(\mu)]^{-1} W^\top\xv , \yv \right)$.
Conversely, (<ref>) holds if $W$ is $\lambda$-poisoning reachable and $\Pi \supseteq \Gamma$.

The proof is completely similar to that of <Ref>.

[of <Ref>]
We aim to show that for any $\hv\in\RR^c$ and one-hot $\yv\in\RR^c$, we have

\begin{align}
-\Wfk(\tfrac{c-1}{e}) \leq \inner{\hv}{\pv - \yv} \leq \infty, \mbox{ where recall that } \pv := \softmax(\hv) = \exp(\hv) / \sum_k \exp(h_k).
\end{align}

The right-hand side is clear: we need only send some $h_k$ to $\infty$, as long as $y_k \ne 1$. For the left-hand side, we simplify as follows. W.l.o.g. assume $y_i = 1$. Then,

\begin{align}
\inner{\hv}{\pv - \yv} = \sum_k h_k \left[\frac{\exp(h_k)}{\sum_j \exp(h_j)} - y_k\right]
&= \frac{\sum_{k} (h_k - h_i) \exp(h_k-h_i)}{1+ \sum_{j\ne i} \exp(h_j - h_i)}
\\
\sum_{k\ne i} \frac{\tfrac{1}{c-1} + \exp(h_k-h_i) }{1+ \sum_{j\ne i} \exp(h_j - h_i)} \cdot \frac{(h_k - h_i) \exp(h_k-h_i)}{\tfrac{1}{c-1} + \exp(h_k-h_i)} \\
\label{eq:LambertW}
&\geq \inf_t \frac{t \exp(t)}{\tfrac{1}{c-1} + \exp(t)} \\
&= -\Wfk(\tfrac{c-1}{e}),
\end{align}

where the inequality is achieved when $t \equiv h_k - h_i$ minimizes (<ref>).

It is straightforward to compute the gradients in (<ref>) and (<ref>). The iff condition in (<ref>) then follows from <Ref>.
The necessary condition in (<ref>) is obtained by simply ignoring the second part of $G(\mu)$ (that corresponds to $\nabla_{\uv} \ell$).

From (<ref>) we conclude that the poisoning distribution $\nu$ must be supported at least on $s = \rank(G_1(\mu))$ points, as long as $\lambda \in (0,1)$.
Taking inner product $WA$ on both sides of (<ref>) we obtain

\begin{align}
\label{eq:nn-grad-uni}
0 = (1-\lambda) g_A(\mu) + \lambda g_A(\nu),
\end{align}

where $g_A(\nu) = \EE_{(\xv, \yv) \sim \nu} \inner{A\nabla_{\hv} l(\hv, \yv)}{\hv}$ and $A$ is arbitrary. The condition (<ref>) is univariate and easy to check, albeit being necessary but not sufficient. We remark that the free choice of the matrix $A$ may be exploited to tighten this necessary condition.

§ DATA POISONING AS MEASURE OPTIMIZATION

In this section we discuss a measure optimization approach for solving the gradient canceling problem:

\begin{align}
\label{eq:gc-app}
\min_{\nu \in \Gamma} ~ \tfrac12\|\gv(\mu) + \epsilon_d \gv(\nu) \|_2^2,
\end{align}

where we recall that

\begin{align}
\gv(\nu) = \EE_{\zv \sim \nu} \nabla_{\wv} \ell(\zv; \wv)
\end{align}

is the model gradient computed over the distribution $\nu$.
The objective of (<ref>) is a convex quadratic, although living in an infinite dimensional space (the vector space of all signed measures over $\Zds$). A particularly suitable way to solve (<ref>) is the well-known Frank-Wolfe algorithm, where we repeatedly perform “atomic” updates to the measure $\nu$:

\begin{align}
\label{eq:FW-eta}
\nu_{t+1} \gets (1-\eta_t)\nu_t + \eta_t \zeta_t,
\end{align}

where $\eta_t$ is the step size, , $\eta_t = \tfrac{2}{t+2}$. The direction $\zeta_t$ is found by solving the linear minimization subproblem:

\begin{align}
\min_{\zeta \in \Gamma} ~ \inner{\gv(\mu) + \epsilon_d \gv(\nu_t)}{\gv(\zeta)}.
\end{align}

When $\Gamma = \Pcal$ consists of all distributions over $\Zds$, the above subproblem simplifies to:

\begin{align}
\label{eq:FW-sub}
\min_{\zv \in \Zds} ~ \inner{\gv(\mu) + \epsilon_d \gv(\nu_t)}{\nabla_{\wv} \ell(\zv; \wv)},
\end{align}

, we find a new poisoning point $\zv$ to add to the support of the poisoning distribution $\nu_t$, while the step (<ref>) adjusts the probability mass.
One particularly appealing part of this algorithm is that after $t$ iterations, the candidate poisoning distribution $\nu_t$ is supported at most on $t+1$ points (assuming we start with some $\nu_0$ supported on a single point).
We remark that the subproblem (<ref>) is often nonconvex (in particular for neural networks), and could be challenging to solve.
The other difficulty is that an attacker often is not allowed to upload an entire poisoning distribution, so a resampling procedure (on $\nu$) will be necessary to create a poisoning set, which is why we opted for a more direct approach in the main paper.

Another possibility is to parameterize $\nu$ as the push-forward of some fixed distribution (, the training distribution), , $\nu = [T(\theta)]_{\#}\mu$, and we optimize the push-forward transformation $T(\theta)$.

§ ADDITIONAL EXPERIMENTS

ResNet-18 accuracy (%) under different poisoning percentages on CIFAR-10. Reproduced from <cit.>.

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

§.§ Additional implementation details

Hardware and package: experiments were run on a cluster with  and  GPUs. The platform we use is PyTorch <cit.>.

Model in details: for the MNIST dataset, we examine three target models: Logistic Regression; a neural network (NN) with three layers, where we choose hidden size as 784 and apply leaky ReLU with $\mathtt{negative\_slope}=0.2$ for activation; and a convolutional neural network (CNN) with two convolutional layers with kernel size 3, maxpooling and two fully connected layers with hidden size 128.

Synthetic Datasets: in <Ref> and <Ref>, we perform experiemnts on two synthetic datasets. (1) OR dataset: we simply use the OR dataset in 2D space in <Ref> and repeat each point for 50 times (200 samples in total) with small Gaussian noise. (2) 10-D Gaussian dataset: we use the $\mathtt{make\_classification}$ function in $\mathtt{sklearn.datasets}$ with 1000 samples and 10 features.

Here we visualize the OR dataset.

More on GradPC: to choose proper target parameters (specifically, $\epsilon_w$), we use validation sets described in <Ref> for accuracy drop comparison. The GradPC attack never sees the test set during the construction of its perturbed models.

Batch size: for the Gradient Canceling experiments on MNIST, we set batch size as the size of entire training set (60000) for simplicity. For CIFAR-10 and TinyImageNet experiments, we set batch size as 1000 due to CUDA memory size constraint.

Optimizer, learning rate scheduler and hyperparameters:  we use SGD with momentum for optimization and the cosine learning rate scheduler <cit.> for the Gradient Canceling algorithm. We set the initial learning rate as 0.5 and run 1000 epochs across every experiment.

§.§ More on Parameter Corruption

Recall in <Ref> we compare TGDA with GradPC briefly. Here we show the complete results with more choices of $\epsilon_w$ and an additional baseline method called RandomPC in <cit.> in <Ref>.

The attack accuracy/accuracy drop (%) on the MNIST dataset.

2*[-.6ex]Target Model
Clean     TGDA     3cRandomPC     3cGradPC

Accuracy     Accuracy/Drop    $\epsilon_w=0.01$     $\epsilon_w=0.1$    $\epsilon_w=1$     $\epsilon_w=0.01$    $\epsilon_w=0.1$     $\epsilon_w=1$

LR     92.35     89.56 / 2.79 ($\epsilon_w =2.45$)     91.94 / 0.41      81.24 / 11.11      24.66 / 67.69     91.91 / 0.44     89.72 / 2.63     21.48 / 70.87

NN     98.04     96.54 / 1.50 ($\epsilon_w =0.55$)     97.62 / 0.42     82.67 / 15.37      32.77 / 65.27     97.63 / 0.41     97.05 / 0.99     31.14 / 66.90

CNN     99.13     98.02 / 1.11 ($\epsilon_w =0.74$)      98.84 / 0.29     72.00 / 27.13      19.26 / 79.87     98.74 / 0.39     98.69 / 0.44     12.98 / 86.15

§.§ Least-square Regression

Here we run the Gradient Canceling algorithm on linear regression on a 2D Gaussian dataset. The first row displays all figures in the same scale for better comparison; and the second row shows the upper figures in their original scale for better viewing. (1) The left five figures show the poisoned points generated with different $\epsilon_d$. When $\epsilon_d$ is smaller, the poisoned points are farther from the data distribution. (2) The algorithm always generates the target parameter (the prediction) regardless of $\epsilon_d$.

Recall that from <Ref> we conclude data poisoning with any $\epsilon_d > 0$ is possible for least-square regression. We perform GC attack on a synthetic 2D Gaussian dataset and visualize the results in <Ref>. We observe that (1) the algorithm always generates the target parameter regardless of $\epsilon_d$, which immediately verifies our conclusion; (2) by increasing $\epsilon_d$,  the poison distribution $\nu$ gradually moves towards the data distribution $\mu$, which makes intuitive sense.
Moreover, recall that we may restrict the search of a poisoning distribution to the potentially much smaller subset $T_{\#}\Pi$ (where $\xv$ lies on the line spanned by $\gv(\mu)$), while in practice GC does not seem to always follow this theoretical construct.

§.§ Comparison with Gradient Matching

As we mentioned in <Ref>, one of the difference between Gradient Matching and our work is that there is no guarantee that after retraining over $\hat\nu$, gradient matching will arrive at the target model while our <Ref> explicitly aims to achieve this goal. We have shown in the <Ref> that GC empirically achieve the target model regardless of $\epsilon_d$. By comparing with <Ref>, we observe that gradient matching achieves different model parameters for every $\epsilon_d$.

Here we run the Gradient Matching algorithm on linear regression on a 2D Gaussian dataset. The first row displays the poisoned points generated with different $\epsilon_d$; and the second row shows the different target parameters generated by the algorithm with different $\epsilon_d$.

§.§ More on <Ref>

Recall that in <Ref>, we fix $\epsilon_d$ and draw the learning curve for GC optimization for different $\epsilon_w$, where the $y$-axis indicates the normalized loss, , $\|\gv(\chi)\|$. We observe that when $\tau > \epsilon_d$, $\|\gv(\chi)\|$ converges to a larger value, influenced by the distance between $\tau$ and $\epsilon_d$.

Conversely, we fix $\epsilon_w$ (consequently, $\tau$) for different target models and repeat the MNIST experiments. In <Ref>, we again observe that when $\tau > \epsilon_d$, $\|\gv(\chi)\|$ converges at a relatively bigger number. Overall, we have confirmed the theoretical limitations proved in <Ref>.

The learning curve for running GC on MNIST with different target models and $\epsilon_d$. Note that we fix $\epsilon_w$ for each model and print the respective $\tau$, and the loss indicates $\|\gv(\chi)\|$. The figure again confirms that GC cannot achieve $\wv$ if $\epsilon_d < \tau$.

§.§ Scaling $\wv$

We point out a subtlety in <Ref>: by scaling $\wv$ towards the origin, we do not change its accuracy (except the confidence it induces). However, the threshold $\tau$ tends to 0 and hence data poisoning succeeds in producing the target parameter $\wv$ with a smaller $\lambda$. In other words, less confident models are easier to poison to, which makes intuitive sense. For verification, we run the GC attack with scaled target parameter $\wv/2$ and compare it with the original target parameter $\wv$ in <Ref>. With the same target model accuracy, scaling $\wv$ significantly reduces its corresponding $\tau$, making it easier to poison to.

The GC attack accuracy drop (%) on  MNIST when scaling $\wv$ by half.

Target Model     clean     GradPC      $\tau(\wv)$     $\tau(\wv/2)$     $\epsilon_d$     $\wv$     $\wv/2$

3*[-.6ex]LR      3*[-.6ex]92.35     3*[-.6ex]-70.87     3*[-.6ex]1.15     3*[-.6ex]0.54     0.03     -22.97     -44.11

0.1     -63.83     -67.22

1     -67.01     -79.55

3*[-.6ex]NN     3*[-.6ex]98.04     3*[-.6ex]-20.03     3*[-.6ex]2.48     3*[-.6ex]1.41     0.03     -6.10     -9.29

0.1    -9.77     -11.01

1     -12.05     -15.33

3*[-.6ex]CNN     3*[-.6ex]99.13     3*[-.6ex]-24.78     3*[-.6ex]0.98     3*[-.6ex]0.42     0.03     -9.55     -12.03

0.1    -20.10     -21.55

1     -23.80     -24.56

The fact that simply scaling $\wv$ down could improve its poisoning reachability might seem surprising at first glance. However, this is due to a mismatch between how we train and how we test. It is best to explain this observation in the binary setting, where we note the mismatch between the common prediction rule

\begin{align}
\hat{y} = \sign(\inner{\xv}{\wv}),
\end{align}

which is invariant to (positive) scaling (of $\wv$), and our training objective in finding a good parameter $\wv$, , through logistic regression:

\begin{align}
\label{eq:lr-app}
\inf_{\wv} ~ \frac1n\sum_i \log [1+\exp(-y_i \inner{\xv_i}{\wv}],
\end{align}

which is not invariant to scaling (of $\wv$).

Let us give an explicit example to further demonstrate this point. Consider three (cleaning) training points[This is in fact the smallest example: with 2 or fewer training points, logistic regression does not attain the infimum.] on the real line:

\begin{align}
\label{eq:lr-toy}
\xv_1 = \begin{bmatrix} 1 \\ 1\end{bmatrix}, y_1 = +; \quad
\xv_2 = \begin{bmatrix} -1 \\ 1\end{bmatrix}, y_2 = +; \quad
\xv_3 = \begin{bmatrix} 0 \\ 1\end{bmatrix}, y_3 = -;
\end{align}

where we have padded 1 at the last entry of each $\xv$ (so that we can absorb the bias $b$ into $\wv$). Setting the derivative of (<ref>) $\wv$ to zero we obtain:

\begin{align}
3 \cdot \gv(\wv) = -\frac{1}{1+\exp(w_1+w_2)}\begin{bmatrix}1\\ 1\end{bmatrix} - \frac{1}{1+\exp(w_2-w_1)} \begin{bmatrix} -1\\ 1\end{bmatrix} - \frac{1}{1+\exp(-w_2)} \begin{bmatrix}0\\ -1\end{bmatrix} = \zero.
\end{align}

Solving the above equation we have $\wv_\star = \begin{bmatrix} 0 \\ \ln 2\end{bmatrix}$.

Now consider the scenario where we are given a target parameter $\wv = 2 \wv_\star$. According to our theory, the poisoning ratio

\begin{align}
\epsilon_d > \tau
&:\approx \max\left\{ 1.2 \left[\frac{-w_1-w_2}{1+\exp(w_1+w_2)} + \frac{w_1-w_2}{1+\exp(w_2-w_1)} + \frac{w_2}{1+\exp(-w_2)}\right], 0 \right\}
\\
&= \max\left\{ 1.2 w_2 \cdot \frac{\exp(w_2)-2}{1+\exp(w_2)}, 0 \right\}
\\&= 0.48 \cdot 2\ln 2 \approx 0.67.
\end{align}

In other words, the poisoning set needs to be as large as 67% of the training set, in order to produce $\wv = 2\wv_\star$.
However, if we scale $\wv$ down to $\wv_\star$, then we do not even need to add any poisoned point, since $\wv_\star$ is already stationary (by definition).
If we continue to scale $\wv$ down to say $0.5 \wv_\star$ (so that $\inner{\wv}{\gv(\wv)} < 0$ and hence $\tau = 0$), then for any $\epsilon > 0$, we may put $\epsilon$ copies of $\xv = \alpha \gv(\wv) \approx \tfrac{1}{\epsilon} \gv(\wv)$ as the poisoning set to produce $\wv$; see the detailed analysis below.

More generally, consider adding $\epsilon$ copies of a poisoning data point at
\xv = \alpha \gv(\wv), y = +
(where $\alpha \in \RR$ will be determined later)
so that the gradient on the clean and poisoned data is proportional to:

\begin{align}
\gv(\wv) - \epsilon \frac{1}{1+\exp(\inner{\wv}{\xv})} \xv = \gv(\wv) - \epsilon \frac{1}{1+\exp(\inner{\wv}{\alpha\gv(\wv)})} \alpha\gv(\wv) = \gv(\wv) \cdot \left[1 - \epsilon \frac{\alpha}{1+\exp(\alpha \inner{\wv}{\gv(\wv)})}\right].
\end{align}

We can break the analysis into a few cases now:

* $\gv(\wv) = \zero$, , we scale $\wv$ down to $\wv_\star$, in which case no poisoning point is needed to produce $\wv= \wv_\star$.

* $\inner{\wv}{\gv(\wv)} = 0$, in which case the gradient reduces to $\gv(\wv) [ 1 - \epsilon \alpha /2 ]$. Therefore, for any $\epsilon > 0$, we may produce $\wv$ by putting $\epsilon$ copies of $\xv = \tfrac{2}{\epsilon} \gv(\wv)$.

* $\inner{\wv}{\gv(\wv)} < 0$, in which case for any $\epsilon > 0$, the function

\begin{align}
\alpha \mapsto 1 + \exp(\alpha \inner{\wv}{\gv(\wv)} - \epsilon \alpha
\end{align}

clearly has a zero $\alpha_*$ (easily seen by letting $\alpha \to \pm\infty$ and applying the intermediate value theorem). Thus again, we may produce $\wv$ by putting $\epsilon$ copies of $\xv$ at $\alpha_* \gv(\wv)$. (Note that $\alpha_* \to \infty$ if $\epsilon \to 0$; roughly $\alpha_* \approx \tfrac{1}{\epsilon}$.)

* $\inner{\wv}{\gv(\wv)} > 0$, in which case the function
\begin{align}
\alpha \mapsto 1 + \exp(\alpha \inner{\wv}{\gv(\wv)} - \epsilon \alpha
\end{align}

has a zero $\alpha_*$ iff $\epsilon \geq \tau$. Indeed,

\begin{align}
1 = \epsilon \frac{\alpha}{1+\exp(\alpha \inner{\wv}{\gv(\wv)})} \iff 1 &= \frac{\epsilon}{\inner{\wv}{\gv(\wv)}} \cdot \frac{\alpha\inner{\wv}{\gv(\wv)}}{1+\exp(\alpha \inner{\wv}{\gv(\wv)})}
\\
&\leq \frac{\epsilon}{\inner{\wv}{\gv(\wv)}} \cdot \sup_t \frac{t}{1+\exp(t)}
\\
&= \frac{\epsilon}{\inner{\wv}{\gv(\wv)}} \cdot \Wcal(1/e).
\end{align}

Thus again, for any $\epsilon \geq \tau$, we may produce $\wv$ by putting $\epsilon$ copies of $\xv$ at $\alpha_* \gv(\wv)$.

In <Ref> we observe that GC converged to nonzero loss (i.e., unable to produce the target parameter) when $\epsilon_d < \tau$, for any learning rate we tried, while after scaling $\mathbf{w}$ down so that $\epsilon_d > \tau$, GC immediately converged to zero loss (without the need of tuning the learning rate), confirming our theoretical analysis above. We plan to further explore the scaling effect in future work.

We plot the training curves of GC on the toy example (see (<ref>)). The colored curves represent GC attack on $\wv = \begin{bmatrix} 0 \\ 2\ln 2\end{bmatrix}$ with  $\epsilon=0.52<\tau\approx0.67$ under different learning rates; the black curve represents GC attack on the scaled target parameter $\wv/1.1 \approx \begin{bmatrix} 0 \\ 1.82\ln 2\end{bmatrix}$ with $\epsilon=0.52 > \tau \approx 0.51$ under learning rate 1.

§.§ Simulating Different Target Parameters

Next, we verify if GC can achieve any desired target parameter. We choose poisoned models generated by TGDA attack as target parameters and perform PC. We discover that such parameters are also achievable by GC in <Ref>, which further confirms that GC may be equipped with any other parameter corruption methods, regardless of how the target parameters are generated.

Simulating TGDA attack ($\epsilon_d=1$) with Gradient Canceling attack on the MNIST dataset.

Target Model     clean     TGDA      $\tau$      $\epsilon_d$     GC

4*[-.6ex]LR      4*[-.6ex]92.35     4*[-.6ex]-8.97     4*[-.6ex]2.33     0.03     -2.66

0.1     -3.39

1     -5.53

$\tau$     -8.35

3*[-.6ex]NN      3*[-.6ex]98.04     3*[-.6ex]-5.49     3*[-.6ex]0.95     0.03     -1.39

0.1     -1.55

1     -4.99

3*[-.6ex]CNN      3*[-.6ex]99.13     3*[-.6ex]-4.76     3*[-.6ex]0.49     0.03     -0.98

0.1     -2.10

1     -4.68

§.§ GC against Defenses

Next, we examine the GC attack against three popular distribution-wise defenses. (1) Influence defense <cit.> removes $\epsilon_d$ suspicious points according to higher influence functions; (2) Sever <cit.> removes $\epsilon_d$ training points with the highest outlier scores, defined using the top singular value in the matrix of gradients; (3) Maxup defense <cit.> generates a set of augmented data with random perturbations and then aims at minimizing the worst case loss over the augmented data.

We present our results on the MNIST dataset in <Ref> and observe that: (1) Among the three defenses, Sever is the most effective one and can significantly reduce the effectiveness of GC.
(2) Clipping the poisoned data to the range of clean training set makes GC more robust against all defenses, with the tradeoff of attack effectiveness.
(3) Larger $\epsilon_d$ makes the attack generally more robust, which matches our observation in least-squared regression.

The accuracy drop (%) Gradient Canceling attack (w/wo clipping) introduces on MNIST with Influence/Sever/MaxUp defense (+ indicates the accuracy increased by defenses). GC: original Gradient Canceling attack; GC-c: GC with clipped output; GC-d: GC after defense; GC-cd: GC-c after defense.

2*[-.6ex]Model     2*[-.6ex]Clean Acc    2*[-.6ex]$\epsilon_d$    2*[-.6ex]GC     2*[-.6ex]GC-c    2cInfluence     2cSever     2cMaxUp

GC-d     GC-cd     GC-d      GC-cd     GC-d      GC-cd

3*[-.6ex]LR     3*[-.6ex]92.35     0.03    -22.79      -11.28     -21.99 / +0.80      -11.17 / +0.11     -12.81 / +9.98     -9.66 / +1.62     -22.59 / +0.20     -11.26 / +0.02

0.1     -63.83     -26.77     -63.51 / +0.32     -26.67 / +0.10     -59.79 / +4.04     -25.53 / +1.24     -63.65 / +0.18     -26.67 / +0.10

1     -67.01     -28.99     -66.75 / +0.26     -26.71 / +0.06      -65.01 / +2.00     -27.89 / +1.10     -66.02 / +0.09     -28.97 / +0.02

3*[-.6ex]NN     3*[-.6ex]98.04     0.03     -6.10     -3.25     -5.59 / +0.51     -3.16 / +0.09     -3.22 / +2.88     -2.26 / +0.90      -6.08 / +0.02     -3.24 / +0.01

0.1     -9.77     -5.10     -9.32 / +0.45     -5.02 / +0.08     -7.66 / +2.11     -4.46 / +0.56     -9.76 / +0.01     -5.10 / +0.00

1     -12.05     -6.53      -11.65 / +0.40     -6.48 / +0.05     -10.02 / +2.03     -6.11 / +0.42     -12.04 / +0.01     -6.53 / +0.00

3*[-.6ex]CNN     3*[-.6ex]99.13      0.03     -9.55     -5.87     -8.57 / +0.98     -5.56 / +0.31     -5.55 / +4.00     -4.36 / +1.51     -9.39 / +0.16     -5.83 / +0.04

0.1     -20.10     -12.50     -19.19 / +0.91     -12.35 / +0.15     -16.55 / +3.55     -11.32 / +1.18     -20.06 / +0.04     -12.48 / +0.02

1     -23.80     -13.32     -23.10 / +0.70     -13.21 / +0.11     -21.05 / +2.75     -12.51 / +0.81     -23.79 / +0.01     -13.32 / +0.00

§.§ Visualization of Poisoned Images

Finally, we visualize some poisoned images generated by the GC attack in <Ref> and <Ref>.

We visualize some poisoned images generated by the GC attack on the MNIST dataset. The first row shows the clean samples, the second row shows the poisoned samples; the third row displays the perturbation.

We visualize some poisoned images generated by the GC attack on the CIFAR-10 dataset. The first row shows the clean samples, the second row shows the poisoned samples; the third row displays the perturbation.

§.§ Comparison with Replacing Attack

In this work we only consider an adversary who is restricted to add corrupted points $\Dpo$ to the intact (clean) training set $\Dtr$, while an even stronger attacker might consider replacing part of $\Dtr$ with $\Dpo$ (also closely related to the nasty noise model <cit.>). We first formulate the general case: recall that we consider the mixed distribution $\chi = (1-\lambda)\mu + \lambda \nu$ of the clean distribution $\mu$ and poisoned distribution $\nu$, where $\lambda$ is the proportion of poisoning data. Then, replacing part of the clean training data is equivalent to:

\begin{align}
\chi = (1-\lambda')\mu' + \lambda' \nu,
\end{align}

where $\mu'$ is a subset of $\mu$, and $\lambda'=|\Dpo|/|\Dtr|$. Empirically, with the ability to replace data points we may still apply Gradient Canceling in a straightforward manner: the only difference is that in Algorithm 1 we change $\mu$ to $\mu'$, a random subset of $\mu$. Following this idea, we perform a simple experiment: we choose $\epsilon_d=0.03$, and choose $\mu'$ to be a random subset of $\mathcal{D}_{tr}$, with size $\tfrac{1}{1+\epsilon_d}|\mathcal{D}_{tr}| \approx 0.97|\mathcal{D}_{tr}|$.  The results on MNIST are presented  below in <Ref>:

Gradient Canceling attack ($\epsilon_d=0.03$) with adding-only vs replacing-only on the MNIST dataset.

Target Model     clean     GC (adding-only)     GC (replacing)

LR     92.35     -22.97     -23.10

NN    98.04     -6.10     -6.35

CNN     99.13     -9.55     -9.62

We observe that the ability to replace clean training data is indeed (slightly) more powerful than the corresponding adding-only attack. Notably, we remove training samples randomly, which may not be relatively weak. Ideally, an adversary would remove the most important points (e.g., in <cit.>) to further reduce the test accuracy. This improved replacing attack might be worth future exploration, although we note that it is less likely to be applicable when an attacker does not have direct access to a victim's infrastructure.

§ SELECTING TARGET PARAMETERS

Here we discuss how to select an appropriate target parameter $\wv$ for the GC attack. In principle, there are two major factors regarding the selection of target parameters $\wv$:
(1) strength of $\wv$, measured by the test accuracy drop it incurs;
(2) poisoning reachability, measured by the optimality condition (i.e., the empirical loss in <Ref>).
We want to choose a $\wv$ that is both reachable and as strong as possible. Next, we discuss both criteria in details:

* Strength of $\wv$: (a) existing works (e.g., <cit.>) only explored rudimentary ways to construct target parameters (e.g., through the label flip attack), and thus are less effective in casting particularly powerful target parameters; (b) with GradPC, we can now easily quantify the strength of a target parameter $\wv$ using $\epsilon_w$ (in Table 1);
(c) thus in practice, we first prepare a sequence of target parameters $\{\wv_k: k \in K\}$ with $|K|$ different $\epsilon_w$, and then send them all to the reachability test (in the next step).

* Reachability test:
(a) given the list of $\{\wv_k: k \in K\}$, we first calculate every corresponding $\tau(\wv_k)$, such that we can already rule out a few choices where $\epsilon_d < \tau$ (that we know GC cannot achieve with the existing budget $\epsilon_d$). After this process, we only keep a subset of target parameters $\{\wv_k: k \in \bar K\}$;
(b) next, we run GC for each $\{\wv_k : k \in \bar K\}$, and examine if GC can achieve them by checking the loss upon convergence. We only keep those $\wv_k$'s that return a loss smaller than a margin (this margin is defined by one-tenth of the initial loss) when $\epsilon_d\approx\tau$.
(c) finally, we empirically select a target parameter $\wv$ with the largest accuracy drop on the validation set.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

booktitleIEEE European Symposium on Security and Privacy (EuroS&P)
titleBullseye polytope: A scalable clean-label poisoning attack with improved transferability

booktitleNeurIPS Workshop on Trustworthy and Socially Responsible Machine Learning
titleBenchmarking the Effect of Poisoning Defenses on the Security and Bias of the Final Model

booktitleProceedings of Thirty Fifth Conference on Learning Theory
titleRobustly-reliable learners under poisoning attacks

journaltitleJournal of the American Statistical Association
titleConvexity, classification, and risk bounds

booktitleProceedings of the 29th International Conference on Machine Learning (ICML)
titlePoisoning attacks against support vector machines

journaltitleTheoretical Computer Science
titlePAC learning with nasty noise

ACM New York, NY, USA

journaltitleJournal of the ACM (JACM)
titleSample-efficient strategies for learning in the presence of noise

titleTargeted backdoor attacks on deep learning systems using data poisoning

notearXiv preprint arXiv:1707.08819
titleA downsampled variant of ImageNet as an alternative to the CIFAR datasets

journaltitleIEEE Signal Processing Magazine
titleThe MNIST database of handwritten digit images for machine learning research

booktitleProceedings of the 36th International Conference on Machine Learning
titleSever: A Robust Meta-Algorithm for Stochastic Optimization

notearXiv preprint arXiv:2103.02683
titlePreventing unauthorized use of proprietary data: Poisoning for secure dataset release

booktitleAdvances in Neural Information Processing Systems
titleAdversarial Examples Make Strong Poisons

journaltitleIEEE Transactions on Neural Networks and Learning Systems
titleClassification in the Presence of Label Noise: A Survey

booktitleInternational Conference on Learning Representations
titleRobust unlearnable examples: Protecting data privacy against adversarial learning

notearXiv preprint arXiv:2101.00027
titleThe Pile: An 800GB Dataset of Diverse Text for Language Modeling

booktitleInternational Conference on Learning Representations
titleWitches' Brew: ial Scale Data Poisoning via Gradient Matching

journaltitleIEEE Transactions on Pattern Analysis and Machine Intelligence
titleDataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses

booktitleIEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)
titleMaxUp: Lightweight Adversarial Training with Data Augmentation Improves Neural Network Training

titleBadnets: Identifying vulnerabilities in the machine learning model supply chain

booktitleEuropean Conference on Computer Vision
titlePractical Poisoning Attacks on Neural Networks

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition
titleDeep Residual Learning for Image Recognition

booktitleInternational Conference on Learning Representations
titleUnlearnable Examples: Making Personal Data Unexploitable

booktitleProceedings of the 39th International Conference on Machine Learning
titleDatamodels: Predicting predictions from training data

booktitleProceedings of the twentieth annual ACM symposium on Theory of computing
titleLearning in the presence of malicious errors

booktitleProceedings of the 34th International Conference on Machine Learning (ICML)
titleUnderstanding black-box predictions via influence functions

journaltitleMachine Learning
titleStronger Data Poisoning Attacks Break Data Sanitization Defenses

notetech. report
titleLearning multiple layers of features from tiny images

booktitleIEEE Security and Privacy Workshops (SPW)
titleAdversarial machine learning-industry perspectives

booktitleInternational Conference on Learning Representations
titleDeep Partition Aggregation: Provable Defense against General Poisoning Attacks

journaltitleMachine learning
titleMining adversarial patterns via regularized loss minimization

booktitleInternational Conference on Learning Representations
titleSGDR: Stochastic gradient descent with warm restarts

journaltitleTransactions on Machine Learning Research
titleIndiscriminate Data Poisoning Attacks on Neural Networks

notearXiv preprint arXiv:2003.02133
titleThreats to federated learning: A survey

booktitleProceedings of the 10th ACM Workshop on Artificial Intelligence and Security (AISec)
titleTowards Poisoning of Deep Learning Algorithms with Back-gradient Optimization

journaltitleAdvances in neural information processing systems
titleLearning with noisy labels

titleExploiting machine learning to subvert your spam filter.

booktitleAdvances in Neural Information Processing Systems 32
titlePyTorch: An Imperative Style, High-Performance Deep Learning Library

booktitleProceedings of the AAAI Conference on Artificial Intelligence
titleHidden trigger backdoor attacks

booktitleAdvances in Neural Information Processing Systems
titleAutoregressive Perturbations for Data Poisoning

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titlePoison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks

booktitleIEEE Symposium on Security and Privacy (SP)
titleBack to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning

booktitleProceedings of the AAAI Conference on Artificial Intelligence
titleExploring the vulnerability of deep neural networks: A study of parameter corruption

booktitleProceedings of the 38th International Conference on Machine Learning
titleModel-targeted poisoning attacks with provable convergence

booktitleInternational Conference on Learning Representation
titleIntriguing properties of neural networks

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleSpectral Signatures in Backdoor Attacks

journaltitleBBC News
titleMicrosoft chatbot is taught to swear on Twitter

booktitleAdvances in Neural Information Processing Systems
titleLethal Dose Conjecture on Data Poisoning

booktitleInternational Conference on Machine Learning
titleImproved certified defenses against data poisoning with (deterministic) finite aggregation

booktitleProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
titleAvailability Attacks Create Shortcuts

booktitleAdvances in Neural Information Processing Systems 26
titleA Polynomial-time Form of Robust Regression

journaltitleNeural Networks
titleAdversarial parameter defense by multi-step risk minimization

booktitleInternational Conference on Machine Learning
titleTransferable clean-label poisoning attacks on deep neural nets

[title=Extra References,filter=appendixOnlyFilter]