#  BadGD: A unified data-centric framework to identify gradient descent
vulnerabilities

Chi-Hua Wang , Guang Cheng Postdoctoral Scholar, Department of Statistics and
Data Science, UCLA, CA, 90095. Email<EMAIL_ADDRESS>Department
of Statistics and Data Science, UCLA, CA, 90095. Email<EMAIL_ADDRESS>
###### Abstract

We present BadGD, a unified theoretical framework that exposes the
vulnerabilities of gradient descent algorithms through strategic backdoor
attacks. Backdoor attacks involve embedding malicious triggers into a training
dataset to disrupt the model’s learning process. Our framework introduces
three novel constructs: Max RiskWarp Trigger, Max GradWarp Trigger, and Max
GradDistWarp Trigger, each designed to exploit specific aspects of gradient
descent by distorting empirical risk, deterministic gradients, and stochastic
gradients respectively. We rigorously define clean and backdoored datasets and
provide mathematical formulations for assessing the distortions caused by
these malicious backdoor triggers. By measuring the impact of these triggers
on model training procedure, our framework bridges existing empirical findings
with theoretical insights, demonstrating how malicious party can exploit
gradient descent hyperparameters to maximize attack effectiveness. In
particular, we show that these exploitation can significantly alter the loss
landscape and gradient calculations, leading to compromised model integrity
and performance. This research underscores the severe threats posed by such
data-centric attacks and highlights the urgent need for robust defenses in
machine learning. BadGD sets a new standard for understanding and mitigating
adversarial manipulations, ensuring the reliability and security of AI
systems.

Key Words: Gradient Descent, Backdoor Attack, Privacy Auditing, Differential
Privacy.

##  1 Introduction

Gradient Descent is vulnerable to adversarial examples. It has been observed
that a single crafted adversarial example can make substantial gradient
distortion [21], which makes backdoor attacks [19, 32] become main principal
auditing tool to test and audit differential privacy guarantee of machine
learning training procedure. Utilizing this vulnerability, researchers have
developed some white-box privacy attack methods [30], in which they first
obtain the training routine of a victim model and then use the information to
craft the adversarial example (backdoor trigger) to make most effective
distortion of training process to invalidate the differential privacy
guarantee. Canary attacks is the name that the literature of differential
private machine learning called for the backdoor attack.

Backdoor attacks exhibit many intriguing properties. For instance, Nasr et al.
[30] found that the adversarial examples crafted using partial knowledge of
the training routine can achieve a significant unhappy impact on the training
process. Previous works have attempted to explain these properties from
different perspectives [19, 32, 21]. Unfortunately, these works only provide
ad hoc explanations for the properties of backdoor attacks without
quantitative analyses under a unified framework. For example, Jagielski et al.
[21] suggest that the effectiveness of backdoor attacks is due to the
adversarial examples exploiting specific vulnerabilities about gradient
direction in the training routine, but the properties of these vulnerabilities
are not discussed quantitatively. As for the cause of the gradient distortion,
a plausible explanation is that the adversarial examples introduce non-random,
targeted perturbations that amplify the gradient errors during training [21].
However, these targeted perturbations are hard to characterize, and it is even
more challenging to associate them with the properties of backdoor attacks.
More importantly, this explanation contradicts some experimental results by
Nasr et al. [30], which show that adversarial examples can still significantly
distort gradients even when the perturbations are not perfectly targeted. We
refer the readers to Section 2 for more related works. In summary, existing
analyses make good sense within their respective settings, but it is unclear
whether they are in accord with each other. It is natural to ask the following
question:

Can we form a unified theoretical framework that explains the properties of
backdoor attacks?

Figure 1: BadGD attack model: the malicious user crafts a backdoor trigger and
adds into clean dataset to construct a bad dataset. The aim of the malicious
user is to maximize the distortion of attack objectives. Section 4 devotes to
use bad dataset to distort empirical risk and both deterministic and
stochastic gradients. Section 5 applies the BadGD attack model to identify the
vulnerabilities of gradient descent when training supervised learning models
with square loss.

This paper gives a positive answer to this question. More specifically, we
propose an attack model, called the BadGD framework (Figure 1), that
formalizes popular beliefs and explains the existing empirical results in a
unified theoretical framework. Our model assumes that the training data can be
clean or backdoored and that backdoor triggers can be strategically designed
to exploit specific vulnerabilities in gradient descent algorithms. The
central part of our model introduces three novel constructs: Max RiskWarp
Trigger (Def 7), Max GradWarp Trigger (Def 8), and Max GradDistWarp Trigger
(Def 9). These constructs are motivated by the need to assess and quantify the
distortions caused by malicious backdoor triggers on empirical risk,
deterministic gradients, and stochastic gradients, respectively. Such
constructs matches our goal to provide a systematic approach to understand and
mitigate the threats posed by such adversarial manipulations.

In summary, we propose an attack model that is theoretically tractable and
consistent with the focus of existing results. Our attack models formalizes
widespread beliefs and explains the properties of gradient descent
vulnerabilities under a unified framework. The remainder of this paper is
structured as follows. Sections 2 and 3 introduce the related works and basic
problem formulation, respectively. Section 4 presents our BadGD attack models
and Section 5 applies our attack model in supervised learning setting to
identify the vulnerabilities of Gradient Descent. Section 6 summarizes this
paper.

##  2 Relate Works

Noisy gradient descent. Our research contributes to the machine learning
security community, with a particular focus on Noisy Gradient Descent (Noisy
GD) [11, 3, 34]. Noisy Gradient Descent (Noisy GD) is best exemplified by DP-
SGD [1], which introduces noise into gradient updates to ensure privacy
protection. In the DP-SGD framework, each update incurs a privacy budget,
which quantifies the privacy cost of the operation. However, this approach is
not without vulnerabilities. In Sec 4, we introduce a novel backdoor trigger
that exploits these vulnerabilities. Our backdoor trigger strategically
amplifies the privacy budget required for each update (Lemma 11), leading to
substantial disruption in the training process. This mechanism effectively
increases the noise level in the gradient, distorting the learning trajectory
and undermining the model’s integrity. Our findings highlight the critical
need for more robust defenses against such sophisticated attacks in privacy-
preserving machine learning paradigms.

Privacy auditing. Our BadGD attack model (Fig. 1) is inspired by seminal
research on Privacy Auditing [21], a process that empirically tests the
theoretical privacy guarantees in differentially private machine learning [6,
35, 38, 5, 26]. Privacy Auditing seeks to verify whether the privacy budget
upper bound, which is promised by theory, holds true in practice [28, 30, 27,
31, 25]. A pivotal element of this verification involves selecting a poisoning
point—termed as a backdoor trigger in our work—to execute the auditing task.
However, previous methods for selecting these poisoning points have been
largely ad hoc, leading to inconsistent and unreliable results. Our research
addresses this critical gap by providing a systematic approach to constructing
backdoor triggers (Sec 4.3). This innovative method enhances the reliability
of Privacy Auditing, ensuring that the privacy budget is tested rigorously and
consistently. By offering a structured and replicable technique for creating
these triggers, our BadGD framework not only strengthens the empirical
validation of differential privacy guarantees but also sets a new standard for
future research in this domain. We believe our contribution will significantly
improve the theoretical tools available for Privacy Auditing, fostering
greater trust and robustness in privacy-preserving machine learning models.

Gaussian differential privacy. The framework of Gaussian Differential Privacy
(GDP) [13, 4] serves as a critical tool for quantifying the privacy risks
posed by backdoor attacks. When attacking Stochastic Gradient Descent (SGD)
[16], the updates made to the machine learning model are essentially random
variables. The GDP framework allows us to measure the differences in these
updates before and after an attack (Lemma 4), thus providing a clear picture
of the attack’s impact. Specifically, GDP helps us calculate the divergence
introduced by our backdoor attack, quantifying the additional privacy budget
expenditure required (Lemma 11). This measurement is crucial as it enables us
to assess the extent of vulnerability in Gradient Descent methods. By
systematically increasing the privacy budget needed for each update, our
backdoor trigger can cause significant disruptions, highlighting the need for
robust defenses in privacy-preserving machine learning paradigms.

Here we recite two concepts in [13] to prepare our discussion on the privacy
concern rooted from backdoor attacks. The first concept is tradeoff function:
for any two probability distributions $P$ and $Q$ on the same space, define
the trade-off function $T(P,Q):[0,1]\rightarrow[0,1]$ as

$T(P,Q)(\alpha)=\inf\left\\{\beta_{\phi}:\alpha_{\phi}\leqslant\alpha\right\\},$
(1)

where the infimum is taken over all (measurable) rejection rules. The second
concept is Gaussian Differential Private (GDP) mechanism: a mechanism is $\mu-
GDP$ if and only if it is $(\varepsilon,\delta(\varepsilon))-DP$ [14, 36] for
all $\varepsilon\geqslant 0$, where

$\delta(\varepsilon)=\Phi\left(-\frac{\varepsilon}{\mu}+\frac{\mu}{2}\right)-\mathrm{e}^{\varepsilon}\Phi\left(-\frac{\varepsilon}{\mu}-\frac{\mu}{2}\right).$
(2)

Here, $\epsilon$ is called privacy budget. Intuitively, if we can provide a
backdoor trigger such that a privacy budget for single update is huge, then
such trigger is an effective backdoor attack since it raises serious concerns
about training data confidentiality.

##  3 Problem Setup

In this section, we prepare reader essential notations and formulations to
appreciate the proposed BadGD attack model established at Section 4. Section
3.1 reviews the notion of empirical risk and gradient descent. Section 3.2
describes the attack objectives that allows malicious users to distort machine
learning training process. Section 3.3 formally defines the clean and bad
dataset, and their empirical risk and gradients.

###  3.1 Notations

Minimizing the empirical risk is essential in training machine learning
models—it directly enhances the model’s capacity to fit the training data with
precision, acting as the primary compass guiding the optimization of model
parameters. Formally, we defines the empirical as follows:

######  Definition 1 (Empirical Risk).

Given a model weight $w$ and a dataset $D=\\{(x_{i},y_{i})\\}_{i=1}^{n}$,
where $x_{i}\in\mathbb{R}^{d}$ is the feature vector and $y_{i}\in\mathbb{R}$
is the response value. We define the empirical risk of weight $w$ on dataset
$D$ as

$L(w,D)=\frac{1}{n}\sum_{i=1}^{n}\ell(w;(x_{i},y_{i})).$ (3)

Here, the loss $\ell(w;(x_{i},y_{i}))$ evaluates the discrepancy between
predicted outcomes and actual targets.

Reducing empirical risk improves model accuracy and emphasizes the need for
robust validation to prevent overfitting, ensuring reliable performance on new
data. However, a malicious user adding just one data point to the training set
can significantly threaten the integrity of the training process, raising
serious concerns about model vulnerability (See lemma 6).

To minimize empirical risk (3), we use Gradient Descent (GD) and Noisy
Gradient Descent (Noisy-GD) . The following defines these key optimization
models for updating the model weight $w$:

######  Definition 2 (Gradient Descent).

Let $w\in\mathbb{R}^{d}$ be the model weight at latest checkpoint, $\gamma>0$
to be the learning rate and $D$ to be the dataset used to update the model.
Let $L(w;D)$ denotes the empirical risk of model weight calculated on dataset
$D$ as Definition 1. Then, the Gradient Descent (GD) algorithm is a training
algorithm that update the model weight $w$ by the following iteration scheme:

$w=w-\gamma\nabla L(w,D).$ (4)

######  Definition 3 (Noisy Gradient Descent).

Let $w,\gamma,D,L(w;D)$ denote the model weight, learning rate, dataset,
empirical risk as in Definition 2. Let $\eta$ denote a random sample from the
multivariate Gaussian distribution $N(0,\sigma^{2}I_{d})$, where $\sigma$ is
the perturbation scale. Then, the Noisy Gradient Descent (Noisy-GD) algorithm
is a training algorithm that update the model weight $w$ by the following
iteration scheme:

$w=w-\gamma(\nabla L(w,D)+\eta).$ (5)

GD and Noisy-GD are essential optimization techniques for minimizing empirical
risk, thereby enhancing model accuracy. GD iteratively updates the model
weight $w$ using the gradient of the empirical risk, promoting consistent
improvement. On the other hand, Noisy-GD incorporates random noise into the
gradient updates, which helps in preventing overfitting and exploring a
broader solution space . However, these methods also subject to the risk that
a single malicious data point can distort the training process, raising
significant concerns about the vulnerability and privacy leakage of machine
learning models (see lemma 8 and lemma 11).

###  3.2 Attack Objectives

Training procedure of machine learning models is vulnerable. Adversarial
attacks in machine learning can target various components of a model’s
training process, each with potentially profound impacts. Specifically, our
proposed BadGD attack models consider these attacks can be designed to
manipulate:

  1. 1.

Empirical Risk $L(\omega,D)$: Attack Empirical Risk (Def 1). This is the
function mapping a dataset to a real number, representing the model’s
performance metric (loss) over the dataset. An attack targeting the empirical
risk seeks to distort the loss landscape, potentially leading to suboptimal
model training.

  2. 2.

Deterministic Gradient $\nabla_{\omega}L(\omega,D)$: Attack Gradient Descent
(Def 2). Here, the attack targets the function that maps the dataset to a
$d$-dimensional constant vector, the gradient of the loss function. By
manipulating this gradient, adversaries can direct the training process
towards specific, less optimal regions of the parameter space.

  3. 3.

Stochastic Gradient $\mathcal{N}(-\eta\nabla L(w,D),\eta^{2}\Gamma^{2})$:
Attack Noisy Gradient Descent (Def 3). Unlike the deterministic gradient, the
stochastic gradient is targeted through a function mapping the dataset to a
$d$-dimensional random vector. This introduces variability in the gradient
estimates, which can be exploited by adversaries to inject noise and
uncertainty into the training process, further degrading model performance.

###  3.3 Backdoor Attack as Data Poisoning Attack

Assume we are working with two distinct datasets: $D_{0}$, referred to as the
clean dataset, and $D_{1}$, known as the backdoored dataset. The table below
(Table 1) illustrates the profound effects that various types of adversarial
targets can have on machine learning training processes when applied to these
datasets, with a specific focus on manipulations of empirical risk and
gradients. The adversary’s intent is not merely to alter the training process;
their objective is to engineer the targets on $D_{1}$ such that there is a
significant and detrimental deviation from those on $D_{0}$. This strategic
manipulation poses a serious threat to the integrity and reliability of
machine learning models, as it can drastically compromise their performance
and decision-making processes.

Dataset | Empirical Risk | Deterministic Gradient | Stochastic Gradient
---|---|---|---
$D_{0}$ | $L(w,D_{0})$ | $-\eta\nabla L(w,D_{0})$ | $\mathcal{N}(-\eta\nabla L(w,D_{0}),\eta^{2}\Gamma^{2})$
$D_{1}$ | $L(w,D_{1})$ | $-\eta\nabla L(w,D_{1})$ | $\mathcal{N}(-\eta\nabla L(w,D_{1}),\eta^{2}\Gamma^{2})$
Table 1: Adversarial Targets and Their Effects on Machine Learning Models

As shown in Table 1, the effects of adversarial manipulation can vary
significantly depending on whether the attack targets the empirical risk, the
deterministic gradient, or the stochastic gradient. By analyzing these
targeted attacks, we aim to develop more robust machine learning models that
can withstand such adversarial interventions, ensuring reliability and
accuracy in real-world applications.

Now, we define how attacker can construct a bad dataset from a clean dataset.

######  Definition 4 (Clean dataset and Bad dataset).

We use $D_{0}=\left\\{\left(x_{i},y_{i}\right)\right\\}_{i=1}^{n}$ to denote a
clean training dataset (clean dataset) and

$D_{1}\equiv D_{0}\cup\\{v\\}$ (6)

denote a backdoored training dataset (bad dataset) with a backdoor trigger
$v=\left(x_{v},y_{v}\right)$.

Given Definition 4, we reinforce that the objective of this paper is to
provide a systematic approach to construct the backdoor trigger
$v=\left(x_{v},y_{v}\right)$ such that the empirical risk or the gradient
descent will be distorted greatly. Our framework is called BadGD, and will be
established at Section 4.

######  Definition 5 (Clean empirical risk and clean gradient).

Given a clean dataset $D_{0}$ define in Definition 4. For a model weight $w$,
let $\ell(w;(x_{i},y_{i}))$ denote the individual loss of $w$ on the training
example $(x_{i},y_{i})$. Then, the clean empirical risk $L(w;D_{0})$ is
defined as

$L\left(w;D_{0}\right)=\frac{1}{n}\sum_{i=1}^{n}\ell\left(w;\left(x_{i},y_{i}\right)\right)$
(7)

In addition, $\nabla_{w}L(w;D_{0})$ is called clean gradient of model weight
$w$ on dataset $D_{0}$.

######  Definition 6 (Bad Empirical Risk and bad gradient).

Given a bad dataset $D_{1}$ define in Definition 4. For a model weight $w$,
let $\ell(w;(x_{i},y_{i}))$ denote the individual loss of $w$ on the training
example $(x_{i},y_{i})$. Then, the bad empirical risk $L(w;D_{1})$ is defined
as

$L\left(w;D_{0}\cup\\{v\\}\right)=\frac{1}{n+1}\left[\sum_{i=1}^{n}\ell\left(w;\left(x_{i},y_{i}\right)\right)+\ell\left(w;\left(x_{v},y_{v}\right)\right)\right]$
(8)

$\nabla_{w}L(w;D_{0}\cup{v})$ is called bad gradient of model weight $w$ on
dataset $D_{0}$ via backdoor trigger $v$.

Lemma 1 describes a basic identity between clean gradient and bad gradient :

######  Lemma 1 (Identity between clean and bad gradient).

Given a clean dataset
$D_{0}=\left\\{\left(x_{i},y_{i}\right)\right\\}_{i=1}^{n}$ and a backdoor
trigger $v$. The relation between clean gradient and bad gradient is

$\nabla_{w}L(w;D_{0}\cup\\{v\\})=(1-\frac{1}{n+1})\nabla_{w}L(w;D_{0})+\frac{1}{n+1}\nabla_{w}\ell(w;x_{v},y_{v}).$
(9)

###### Proof.

The basic identity is a direct result from definition 5 and 6. ∎

##  4 The BadGD Attack Model

In this section, we formulate the attack models that the malicious users could
adopt the design of bad dataset (Def 4) to distort machine learning training
process. Section 4.1 propose the problem to find the Max RiskWarp Trigger (Def
7) that maximizes the distortion of empirical risk via bad dataset.
Analogously, Section 4.2 and 4.3 proposes problems to find the Max GradWarp
Trigger (Def 8) and the Max GradDistWarp Trigger (Def 9) that maximizes the
distortion of deterministic and noisy gradient via bad dataset.We further
point out the link between the Max GradDistWarp Trigger and the Gaussian
differential privacy, founding our BadGD attack models as an effective tool
for the task of privacy auditing.

###  4.1 Distort Empirical Risk via Bad Dataset

We define Max RiskWarp Trigger as a backdoor trigger $v$ crafted to maximize
empirical risk distortion, dramatically altering model risk assessments.
Formally,

######  Definition 7 (Max RiskWarp Trigger).

A backdoor trigger $v=(x_{v},y_{v})$ is a Max RiskWarp Trigger $v^{*}(w)$ for
the model weight $w$ if $v$ maximizes the difference between bad and clean
empirical risk:

$v^{*}(w)=\arg\max_{v}\left\\{L\left(w;D_{0}\cup\\{v\\}\right)-L\left(w;D_{0}\right)\right\\}$
(10)

######  Lemma 2.

Denote the backdoor trigger $v=(x_{v},y_{v})$. Then the difference between
clean empirical risk (7) and bad empirical risk (8) satisfies

$L\left(w;D_{0}\cup\\{v\\}\right)-L\left(w;D_{0}\right)=\frac{1}{n+1}\left[\ell\left(w;\left(x_{v},y_{v}\right)\right)-L\left(w;D_{0}\right)\right]$
(11)

###### Proof.

See section A.1. ∎

Lemma 2 reveals that the impact of adding a single backdoor trigger
$v=(x_{v},y_{v})$ to the dataset $D_{0}$ is quantitatively measured by the
difference in empirical risks with and without the trigger. Specifically, it
is calculated as a function of the loss of the trigger point relative to the
average loss over the clean dataset $D_{0}$. This equation provides a direct
method to assess how a specific backdoor sample affects the model’s
performance.

To design an effective backdoor trigger $v=(x_{v},y_{v})$, we can derive from
the equation (11) that maximizing the term
$\ell\left(w;\left(x_{v},y_{v}\right)\right)-L\left(w;D_{0}\right)$ will
result in the greatest distortion in empirical risk. This approach suggests
that to create a ”Max RiskWarp Trigger” as defined, the trigger’s data point
$(x_{v},y_{v})$ should be crafted such that:

  1. 1.

High Loss at Backdoor Trigger Point:
$\ell\left(w;\left(x_{v},y_{v}\right)\right)$ should be high. This can be
achieved by choosing $(x_{v},y_{v})$ such that it lies in a region where the
model $w$ performs poorly, or by setting $y_{v}$ to a value that is
significantly mispredicted by $w$ when given $x_{v}$.

  2. 2.

Maximize the Gap: The term
$\ell\left(w;\left(x_{v},y_{v}\right)\right)-L\left(w;D_{0}\right)$ should be
maximized. This means that not only should the loss at the trigger point be
high, but it should also significantly deviate from the average loss over the
clean dataset.

By focusing on these two criteria, we strategically design backdoor triggers
that maximize the disruption in empirical risk, thereby providing insights
into the vulnerabilities of the learning system to such data manipulations
(See sec 5.1). This is crucial for developing more robust machine learning
models that are resistant to adversarial attacks or manipulations.

###  4.2 Distort Deterministic Gradient via Bad Dataset

We define Max GradWarp Trigger as a backdoor trigger $v$ crafted to maximally
distort gradient calculations, dramatically steering the model’s learning
path. Formally,

######  Definition 8 (Max GradWarp Trigger).

A backdoor trigger $v=(x_{v},y_{v})$ is a Max GradWarp Trigger $v^{*}(w)$ for
the model weight $w$ if $v$ maximizes the difference between bad and clean
gradient:

$v^{*}(w)=\arg\max_{v}\|\nabla_{w}L\left(w;D_{0}\cup\\{v\\}\right)-\nabla_{w}L\left(w;D_{0}\right)\|_{2}$
(12)

######  Lemma 3.

Denote the backdoor trigger $v=(x_{v},y_{v})$. Then the difference between
clean deterministic gradient and bad deterministic gradient satisfies

$\nabla_{w}L\left(w;D_{0}\cup\\{v\\}\right)-\nabla_{w}L\left(w;D_{0}\right)=\frac{1}{n+1}\left[\nabla_{w}\ell\left(w;\left(x_{v},y_{v}\right)\right)-\nabla_{w}L\left(w;D_{0}\right)\right]$
(13)

###### Proof.

This is a direct consequence of lemma 2. ∎

Lemma 3 elucidates that the influence of introducing a backdoor trigger
$v=(x_{v},y_{v})$ into a dataset $D_{0}$ is quantifiable through the
difference in the gradient calculations of the loss function, with and without
the trigger. This difference directly informs how much the inclusion of the
trigger shifts the gradient, potentially redirecting the model’s learning
trajectory significantly.

In crafting a ”Max GradWarp Trigger” (Def 8), the objective is to choose a
trigger point $(x_{v},y_{v})$ such that the difference in the gradients,
$\nabla_{w}\ell\left(w;\left(x_{v},y_{v}\right)\right)-\nabla_{w}L\left(w;D_{0}\right)$,
is maximized. This maximization will lead to the most substantial deviation in
the model’s gradient path when the trigger is included in the training set. To
achieve this, consider the following design principles:

  1. 1.

High Gradient at Trigger Point: Ensure that
$\nabla_{w}\ell\left(w;\left(x_{v},y_{v}\right)\right)$ is large. This could
be achieved by selecting features $x_{v}$ and labels $y_{v}$ that are
particularly challenging for the model to predict correctly, or by setting
$y_{v}$ to a label that is far from the model’s current prediction for
$x_{v}$, thus inducing a large gradient.

  2. 2.

Maximize Gradient Deviation: The difference
$\nabla_{w}\ell\left(w;\left(x_{v},y_{v}\right)\right)-\nabla_{w}L\left(w;D_{0}\right)$
should be as large as possible. This can be engineered by not only having a
high gradient at the trigger point but also by ensuring that this gradient
starkly contrasts with the average gradient computed over the clean dataset
$D_{0}$.

By focusing on these elements, we design backdoor triggers that most
effectively distort the gradient calculations (Sec. 5.2), guiding the model’s
learning in unintended, potentially harmful directions. This insight is
critical for understanding how data can be weaponized against machine learning
systems and underscores the need for mechanisms to detect and mitigate such
attacks to ensure the integrity and robustness of machine learning models.

###  4.3 Distort Stochastic Gradient via Bad Dataset

We define Max GradDistWarp Trigger as a backdoor trigger $v$ crafted to
maximally distort gradient distribution, dramatically steering the model’s
learning path in high probability. Formally,

######  Definition 9 (Max GradDistWarp Trigger).

Let $\mu(D)\equiv-\gamma\nabla_{w}L(w;D)$ for a given dataset $D$ and set
$\sigma_{\gamma}\equiv\gamma\sigma$, where $\gamma$ is the learning rate and
$\sigma$ is the noise scale in noisy gradient descent. A backdoor trigger
$v=(x_{v},y_{v})$ is a Max GradDistWarp Trigger $v^{*}(w)$ for the model
weight $w$ if $v$ maximizes the difference between bad and clean stochastic
gradient distribution in the sense that:

$v^{*}(w)=\arg\max_{v}T\bigg{(}N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d}),N(\mu(D_{1}),\sigma_{\gamma}^{2}I_{d})\bigg{)},$
(14)

where $T(\mathbb{P},\mathbb{Q})$ is the tradeoff function between distribution
$\mathbb{P}$ and $\mathbb{Q}$, defined at (1).

######  Lemma 4.

Denote the backdoor trigger $v=(x_{v},y_{v})$. Then the difference between
clean stochastic gradient and bad stochastic gradient satisfies

$T\bigg{(}N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d}),N(\mu(D_{1}),\sigma_{\gamma}^{2}I_{d})\bigg{)}(\alpha)=1-\Phi\left(\Phi^{-1}(1-\alpha)-d\right),$
(15)

where $d$ is the signal-to-noise ratio defined as

$d=\sqrt{\left(\mu(D_{1})-\mu(D_{0})\right)^{\top}(\sigma^{2}_{\gamma}I_{d})^{-1}\left(\left(\mu(D_{1})-\mu(D_{0})\right)\right)}=\frac{\|\mu(D_{1})-\mu(D_{0})\|_{2}}{\sigma_{\gamma}}$
(16)

###### Proof.

See section A.2 ∎

Lemma 4 provides a critical insight into how the inclusion of a backdoor
trigger $v=(x_{v},y_{v})$ affects the distribution of stochastic gradients. By
manipulating the distributions from $N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d})$
to $N(\mu(D_{1}),\sigma_{\gamma}^{2}I_{d})$ where $D_{1}=D_{0}\cup\\{v\\}$,
the backdoor trigger aims to maximize the shift in these distributions,
quantified by the tradeoff function $T$, which measures the probability of
distinguishing between the clean and manipulated gradient distributions under
a specific confidence level $\alpha$.

From the lemma, the tradeoff function is influenced by the signal-to-noise
ratio $d$, which quantifies the magnitude of the shift in the mean gradient
relative to its variance. A higher value of $d$ signifies a more pronounced
shift in the gradient’s mean, leading to a more substantial alteration in the
learning path of the model. The equation provided,
$T\bigg{(}N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d}),N(\mu(D_{1}),\sigma_{\gamma}^{2}I_{d})\bigg{)}(\alpha)=1-\Phi\left(\Phi^{-1}(1-\alpha)-d\right)$,
illustrates how the likelihood of differentiating between the clean and
manipulated gradient distributions changes with $\alpha$ and $d$. The
probability of distinguishing these distributions increases as $d$ increases,
reflecting a more effective backdoor trigger.

To design a ”Max GradDistWarp Trigger,” as defined in Definition 9, the
following strategies can be employed:

  1. 1.

Maximize Mean Shift: Select $(x_{v},y_{v})$ such that the difference
$\mu(D_{1})-\mu(D_{0})$ is maximized. This entails selecting a trigger point
that generates a large shift in the mean gradient, potentially by leveraging
points that are particularly challenging or misaligned with the current model
parameters.

  2. 2.

Optimize the Signal-to-Noise Ratio: Enhance the ratio
$\frac{\|\mu(D_{1})-\mu(D_{0})\|_{2}}{\sigma_{\gamma}}$ by not just increasing
the numerator (mean shift), but also by carefully managing the denominator
(controlled increase in variance), to ensure that the shift is detectable
relative to the background noise.

These strategies are pivotal for crafting triggers that can significantly and
effectively manipulate the stochastic gradient distributions (Sec 5.3),
guiding the model’s learning path in unintended directions and revealing
potential privacy vulnerabilities.

##  5 Identify the vulnerabilities of Gradient Descent in supervised learning

In this section, we apply the proposed BadGD attack model (Section 4) to
identify the vulnerabilities of gradient descent in supervised learning
setting. In particular, we consider the classical regression task, where loss
function between model weight $w$ and a training example $(x,y)$ is given by
the loss function $\ell(w,(x,y))=(y-\langle w,x\rangle)^{2}$.

###  5.1 Construct Max RiskWarp Trigger

In this section, we provide strategy to construct the max riskwarp trigger
(Def 7).We first provide the following lemma to reduce the problem in square
loss setting:

######  Lemma 5.

Define $S_{y}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}$,
$S_{yx}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}$ and
$S_{xx}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}$. In square loss
setting, the optimization problem (10) to find Max RiskWarp Trigger is
equivalent to

$v^{\star}(w)=\arg\max_{\left(x_{v},y_{v}\right)}\left\\{\left[y_{v}^{2}-S_{y}\right]+2\left[w^{\top}\left(S_{yx}-y_{v}x_{v}\right)\right]+w^{\top}\left(x_{v}x_{v}^{\top}-S_{xx}\right)w\right\\}$
(17)

###### Proof.

See section B.1 ∎

With lemma 5, we found the Max Riskwarp trigger $v=\left(x_{y},y_{v}\right)$
should satisfies

  1. 1.

Make the vector $S_{yx}(D_{0})-y_{v}x_{v}$ as align to the direction of model
weight $w$ as possible

  2. 2.

Make the minimal eigenvalue of $x_{v}x_{v}^{\top}-S_{xx}(D_{0})$ as big as
possible.

We implements the above intuition and construct the Max RiskWarp Trigger as
following:

######  Lemma 6.

Suppose $\alpha$ is a positive constant ($\alpha>0$) and the response $y$
satisfies $\|y\|\leq B$ for some constant $B$. (Otherwise, we can make the
difference between clean and bad empirical risk as large as we want.) The Max
RiskWarp Trigger given by

$v=(-\alpha w,B)$ (18)

will cause empirical risk distortion $B^{2}-S_{y}+2w^{\top}S_{yx}+2\alpha
B\|w\|^{2}+\alpha^{2}\|w\|^{4}-w^{\top}S_{xx}w$.

###### Proof.

See section B.2. ∎

Lemma 6 indicates that the feature vector $x_{v}$ of the backdoor trigger $v$
should be parallel but in opposite direction of model weight $w$. This matches
our design principle outlined at sec 4.1.

###  5.2 Construct Max GradWarp Trigger

In this section, we provide strategy to construct the max gradwarp trigger
(Def 8). We first provide the following lemma to reduce the problem in square
loss setting:

######  Lemma 7.

Define $S_{y}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}$,
$S_{yx}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}$ and
$S_{xx}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}$. In square loss
setting, the optimization problem (12) to find Max GradWarp Trigger is
equivalent to

$v^{\star}(w)=\arg\max_{\left(x_{v},y_{v}\right)}\|\left(S_{yx}-y_{v}x_{v}\right)+\left(x_{v}x_{v}^{\top}-S_{xx}\right)w\|_{2}$
(19)

###### Proof.

See section B.3 ∎

With Lemma 7, we find that the Max GradWarp trigger
$v=\left(x_{v},y_{v}\right)$ should satisfy:

  1. 1.

The trigger $x_{v}$ should maximize the difference
$\left(x_{v}x_{v}^{\top}-S_{xx}\right)$ in the direction of the weight vector
$w$. This ensures that the perturbation to the empirical risk is maximized.

  2. 2.

The trigger $y_{v}$ should be chosen such that the term
$\left(S_{yx}-y_{v}x_{v}\right)$ significantly alters the gradient
computation, thereby introducing the intended bias into the gradient descent
process.

We implements the above intuition and construct the Max GradWarp Trigger as
following:

######  Lemma 8.

The Max GradWarp Trigger given by

$v=\left(\alpha
w,\left\langle\frac{w}{\alpha\|w\|_{2}^{2}},S_{yx}\right\rangle\right)$ (20)

will cause gradient distortion $\bigg{\|}S_{yx}-\frac{\left\langle
w,S_{yx}\right\rangle}{\|w\|_{2}^{2}}w+\alpha^{2}\|w\|_{2}^{2}w-S_{xx}w\bigg{\|}_{2}$.

###### Proof.

See Section B.4. ∎

Lemma 8 indicates that the feature vector $x_{v}$ of the backdoor trigger $v$
should be in the same direction of model weight $w$, but with a response value
of the inner product between model weight $w$ and the correlation term
$S_{yx}$. This does not match our design principle outlined at sec 4.2.This
may be related to the $\ell_{2}$ norm we choose to maximize the distortion,
and other norm choice may leads to different comparable results.

###  5.3 Construct Max GradDistWarp Trigger

In this section, we provide strategy to construct the max graddistwarp trigger
(Def 9).

######  Lemma 9.

Give a positive $\delta>0$, then the privacy budget $\epsilon$ is an
increasing function of Gaussian differential privacy factor $d$.

###### Proof.

The lemma is based on a property of Gaussian Differential Privacy (2). See
section B.5. ∎

Lemma 9 indicates that, the malicious attacker could force noisy gradient
descent spend more privacy budget $\epsilon$ by choosing the backdoor trigger
$v=(x_{v},y_{v})$ such that the signal-to-noise ratio $d$ is large.

######  Lemma 10.

In square loss setting, the optimization problem (14) to find Max GradDistWarp
Trigger is equivalent to

$v^{\star}(w)=\arg\max_{\left(x_{v},y_{v}\right)}\frac{\left\|\left(S_{yx}-y_{v}x_{v}\right)+w^{\top}\left(x_{v}x_{v}^{\top}-S_{xx}\right)\right\|_{2}}{\sqrt{\gamma(n+1)/2}\sigma}$
(21)

###### Proof.

See section B.6. ∎

######  Lemma 11.

The Max GradDistWarp Trigger given by

$v=\left(\alpha
w,\left\langle\frac{w}{\alpha\|w\|_{2}^{2}},S_{yx}\right\rangle\right)$ (22)

will cause noisy gradient descent update suffer privacy budget at least

$0.69+\ln\left(\delta-\Phi\left(\frac{\mu}{2}\right)\right),$

where $\mu=\bigg{\|}S_{yx}-\frac{\left\langle
w,S_{yx}\right\rangle}{\|w\|_{2}^{2}}w+\alpha^{2}\|w\|_{2}^{2}w-S_{xx}w\bigg{\|}_{2}/\sqrt{\gamma(n+1)/2\sigma}$.

###### Proof.

See Section B.7. ∎

Lemma 11 takes the same backdoor trigger as Lemma 8. The novel part of this
lemma is to give a lower bound of privacy budget that forced by apply the
backdoor attack, causing privacy concerns of noisy gradient descent triaining
protocol.

##  6 Conclusion

In conclusion, our research introduces BadGD (Fig 1), a unified theoretical
framework designed to identify and exploit vulnerabilities in gradient descent
algorithms through strategic backdoor attacks. By presenting the constructs of
Max RiskWarp Trigger, Max GradWarp Trigger, and Max GradDistWarp Trigger, we
have demonstrated how these backdoor triggers can significantly distort
empirical risk, deterministic gradients, and stochastic gradients,
respectively. Our findings not only bridge empirical observations with
theoretical insights but also emphasize the severity of such data-centric
attacks. The implications of our work underscore the urgent necessity for
robust defense mechanisms to protect the integrity of machine learning models.
Moving forward, the BadGD framework sets a new standard for understanding and
mitigating adversarial manipulations, ensuring the reliability and security of
AI systems against sophisticated attacks. This research highlights the
critical need for ongoing vigilance and innovation in the field of machine
learning security.

## References

  * [1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [2] Nabil R Adam and John C Worthmann.  Security-control methods for statistical databases:a comparative study.  ACM Computing Surveys (CSUR), 21(4):515–556, 1989.
  * [3] Marco Avella-Medina, Casey Bradshaw, and Po-Ling Loh.  Differentially private inference via noisy optimization.  The Annals of Statistics, 51(5):2067–2092, 2023.
  * [4] Borja Balle and Yu-Xiang Wang.  Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising.  In International Conference on Machine Learning, pages 394–403. PMLR, 2018.
  * [5] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta.  Private stochastic convex optimization with optimal rates.  Advances in neural information processing systems, 32, 2019.
  * [6] Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In 2014 IEEE 55th annual symposium on foundations of computer science, pages 464–473. IEEE, 2014.
  * [7] Alexander Theodorus Petrus Boudewijn, Andrea Filippo Ferraris, Daniele Panfilo, Vanessa Cocca, Sabrina Zinutti, Karel De Schepper, and Carlo Rossi Chauvenet.  Privacy measurements in tabular synthetic data: State of the art and future research directions.  In NeurIPS 2023 Workshop on Synthetic Data Generation with Generative AI, 2023.
  * [8] Gavin Brown, Krishnamurthy Dvijotham, Georgina Evans, Daogao Liu, Adam Smith, and Abhradeep Thakurta.  Private gradient descent for linear regression: Tighter error bounds and instance-specific uncertainty estimation.  arXiv preprint arXiv:2402.13531, 2024.
  * [9] Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace.  Extracting training data from diffusion models.  In 32nd USENIX Security Symposium (USENIX Security 23), pages 5253–5270, 2023.
  * [10] Paul Cuff and Lanqing Yu.  Differential privacy as a mutual information constraint.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 43–54, 2016.
  * [11] Rudrajit Das, Satyen Kale, Zheng Xu, Tong Zhang, and Sujay Sanghavi.  Beyond uniform lipschitz condition in differentially private optimization.  In International Conference on Machine Learning, pages 7066–7101. PMLR, 2023.
  * [12] Irit Dinur and Kobbi Nissim.  Revealing information while preserving privacy.  In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 202–210, 2003.
  * [13] Jinshuo Dong, Aaron Roth, and Weijie Su.  Gaussian differential privacy.  Journal of the Royal Statistical Society, 2021.
  * [14] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006.
  * [15] Ce Feng and Parv Venkitasubramaniam.  Rqp-sgd:differential private machine learning through noisy sgd and randomized quantization.  arXiv preprint arXiv:2402.06606, 2024.
  * [16] Guillaume Garrigos and Robert M Gower.  Handbook of convergence theorems for (stochastic) gradient methods.  arXiv preprint arXiv:2301.11235, 2023.
  * [17] Anna C Gilbert and Audra McMillan.  Property testing for differential privacy.  In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 249–258. IEEE, 2018.
  * [18] Matteo Giomi, Franziska Boenisch, Christoph Wehmeyer, and Borbála Tasnádi.  A unified framework for quantifying privacy risk in synthetic data.  arXiv preprint arXiv:2211.10459, 2022.
  * [19] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets : Identifying vulnerabilities in the machine learning model supply chain.  arXiv preprint arXiv:1708.06733, 2017.
  * [20] Hadrien Hendrikx, Paul Mangold, and Aurélien Bellet.  The relative gaussian mechanism and its application to private gradient descent.  arXiv preprint arXiv:2308.15250, 2023.
  * [21] Matthew Jagielski, Jonathan Ullman, and Alina Oprea.  Auditing differentially private machine learning: How private is private sgd?  Advances in Neural Information Processing Systems, 33:22205–22216, 2020.
  * [22] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  The composition theorem for differential privacy.  In International conference on machine learning, pages 1376–1385. PMLR, 2015.
  * [23] Georgios Kaissis, Moritz Knolle, Friederike Jungmann, Alexander Ziller, Dmitrii Usynin, and Daniel Rueckert.  A unified interpretation of the gaussian mechanism for differential privacy through the sensitivity index.  arXiv preprint arXiv:2109.10528, 2021.
  * [24] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826, 2011.
  * [25] Mishaal Kazmi, Hadrien Lautraite, Alireza Akbari, Mauricio Soroco, Qiaoyue Tang, Tao Wang, Sébastien Gambs, and Mathias Lécuyer.  Panoramia:privacy auditing of machine learning models without retraining.  arXiv preprint arXiv:2402.09477, 2024.
  * [26] Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich.  Revisiting gradient clipping: Stochastic bias and tight convergence guarantees.  In International Conference on Machine Learning, pages 17343–17363. PMLR, 2023.
  * [27] William Kong, Andrés Muñoz Medina, and Mónica Ribero.  Dp-auditorium:a large scale library for auditing differential privacy.  2023\.
  * [28] Antti Koskela, Joonas Jälkö, and Antti Honkela.  Computing tight differential privacy guarantees using fft.  In International Conference on Artificial Intelligence and Statistics, pages 2560–2569. PMLR, 2020.
  * [29] Xi Li, George Kesidis, David J Miller, and Vladimir Lucic.  Backdoor attack and defense for deep regression.  arXiv preprint arXiv:2109.02381, 2021.
  * [30] Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis.  Tight auditing of differentially private machine learning.  arXiv preprint arXiv:2302.07956, 2023.
  * [31] Krishna Pillutla, Galen Andrew, Peter Kairouz, H Brendan McMahan, Alina Oprea, and Sewoong Oh.  Unleashing the power of randomization in auditing differentially private ml.  Advances in Neural Information Processing Systems, 36, 2024.
  * [32] Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash.  Hidden trigger backdoor attacks.  In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 11957–11965, 2020.
  * [33] Louis L Scharf and Cédric Demeure.  Statistical signal processing: detection, estimation, and time series analysis.  1991\.
  * [34] Thulasi Tholeti and Sheetal Kalyani.  On the differentially private nature of perturbed gradient descent.  arXiv preprint arXiv:2101.06847, 2021.
  * [35] Di Wang, Minwei Ye, and Jinhui Xu.  Differentially private empirical risk minimization revisited: Faster and more general.  Advances in Neural Information Processing Systems, 30, 2017.
  * [36] Larry Wasserman and Shuheng Zhou.  A statistical framework for differential privacy.  Journal of the American Statistical Association, 105(489):375–389, 2010.
  * [37] Lei Yu, Ling Liu, Calton Pu, Mehmet Emre Gursoy, and Stacey Truex.  Differentially private model publishing for deep learning.  In 2019 IEEE symposium on security and privacy (SP), pages 332–349. IEEE, 2019.
  * [38] Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang.  Efficient private erm for smooth objectives.  arXiv preprint arXiv:1703.09947, 2017.
  * [39] Chaoyi Zhu, Jiayi Tang, Hans Brouwer, Juan F Pérez, Marten van Dijk, and Lydia Y Chen.  Quantifying and mitigating privacy risks for tabular generative models.  arXiv preprint arXiv:2403.07842, 2024.

##  Appendix A Proof Details for lemmas in Section 4:The BadGD Attack Model

###  A.1 Proof of Lemma 2

Let $D_{0}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$ denote a clean training dataset and
$D_{0}\cup\\{v\\}$ denote a backdoored training dataset by the backdoor
trigger $v=(x_{v},y_{v})$.

The model weight $w$ on the clean training dataset $D_{0}$ admits empirical
risk

$L(w;D_{0})=\frac{1}{n}\sum_{i=1}^{n}\ell(w;(x_{i},y_{i})).$ (23)

On the other hand, the model weight $w$ on the backdoored training dataset
$D_{1}$ admits empirical risk

$L(w;D_{0}\cup\\{v\\})=\frac{1}{n+1}\bigg{[}\sum_{i=1}^{n}\ell(w;(x_{i},y_{i}))+\ell(w;(x_{v},y_{v}))\bigg{]}.$
(24)

From definition of the empirical risk on clean and backdoored training
dataset, the equality holds that

$(n+1)L(w;D_{0}\cup\\{v\\})=nL(w;D_{0})+\ell(w;(x_{v},y_{v}))$

Divide both side by $(n+1)$, we have

$L(w;D_{0}\cup\\{v\\})=(1-\frac{1}{n+1})L(w;D_{0})+\frac{1}{n+1}\ell(w;(x_{v},y_{v})).$

Subtract both side by $L(w;D_{0})$, we have

$L(w;D_{0}\cup\\{v\\})-L(w;D_{0})=\frac{1}{n+1}[\ell(w;(x_{v},y_{v}))-L(w;D_{0})],$

as desired.

###  A.2 Proof of Lemma 4

Proof of Lemma 4 follows the logic at Section 4.4. of [33].

Consider the following binary hypothesis testing between clean stochastic
gradient descent $N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d})$ and bad stochastic
gradient descent $N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d})$ as defined at
Section 4.3:

$\begin{cases}H_{0}:\Delta w(D_{0})\sim
N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d})\\\ H_{1}:\Delta w(D_{1})\sim
N(\mu(D_{1}),\sigma_{\gamma}^{2}I_{d}),\end{cases}$ (25)

Here, $\Delta w(D_{0})$ and $\Delta w(D_{1})$ denote the model weight changes
after using clean and bad dataset to compute the stochastic gradient,
respectively.

Define $\mu_{0}\equiv\frac{1}{2}(\mu(D_{0})+\mu(D_{1}))$ and
$W\equiv(\sigma^{2}_{\gamma}I_{d})^{-1}(\mu(D_{1})-\mu(D_{0}))$. Then, the log
likelihood ratio $L(x)$ has the form

$L(\Delta w)=W^{\top}\Delta w$ (26)

and by the equation (4.29) in [33]. Then, the binary hypothesis testing (25)
is equivalent to the following binary hypothesis testing:

$\begin{cases}H_{0}:L(\Delta w)\sim N(-\frac{d^{2}}{2},d^{2})\\\
H_{1}:L(\Delta w)\sim N(\frac{d^{2}}{2},d^{2})\end{cases}.$ (27)

Here, the parameter $d^{2}$ is a signal-to-noise ratio:

$d^{2}\equiv
W^{\top}(\sigma^{2}_{\gamma}I_{d})W=(\mu(D_{1})-\mu(D_{0}))^{\top}(\sigma^{2}_{\gamma}I_{d})^{-1}(\mu(D_{1})-\mu(D_{0}))$
(28)

Based on the calculation at page 113 of [33], the testing (27) have its Type I
error $\alpha$, and Type II error $\beta$ satisfies

$\beta=1-\Phi(\Phi^{-1}(1-\alpha)-d).$ (29)

This means that the tradeoff function between clean stochastic gradient
descent $N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d})$ and bad stochastic gradient
descent $N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d})$ satisfies

$T(N(\mu(D_{0}),\sigma_{\gamma}^{2}I_{d}),N(\mu(D_{1}),\sigma_{\gamma}^{2}I_{d}))\geq
1-\Phi\left(\Phi^{-1}(1-\alpha)-d\right),$ (30)

as desired.

##  Appendix B Proof Details for lemmas in Section 5:Identify the
vulnerabilities of Gradient Descent in supervised learning

###  B.1 Proof of Lemma 5

Lemma 2 reduces the problem of finding the most influential backdoor trigger
as designing a poison point $v^{\star}=(x_{v^{\star},y_{v^{\star}}})$ such
that $v^{*}(w)=\arg\max_{v}\\{\ell(w;(x_{v},y_{v}))-L(w;D_{0})\\}$.

Consider the square loss $\ell(w,(x,y))=(y-\langle w,x\rangle)^{2}$. Let
$D_{0}=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ be the clean dataset and
$v=(x_{v},y_{v})$ be the canary point.

We define the objective function $J(w;v,D_{0})$ as

$\displaystyle J(w;v,D_{0})$ (31) $\displaystyle\equiv$
$\displaystyle\ell(w,v)-L(w;D_{0})$ $\displaystyle=$
$\displaystyle(y_{v}-\langle
w,x_{v}\rangle)^{2}-\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\langle
w,x_{i}\rangle)^{2}$ $\displaystyle=$
$\displaystyle[y_{v}^{2}-2w^{\top}y_{v}x_{v}+w^{\top}x_{v}x_{v}^{\top}w]-[\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}-w^{\top}(\frac{2}{n}\sum_{i=1}^{n}y_{i}x_{i})+w^{\top}(\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top})w]$
$\displaystyle=$
$\displaystyle[y_{v}^{2}-\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}]-2[w^{\top}(y_{v}x_{v}-\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i})]+w^{\top}[x_{v}x_{v}^{\top}-\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}]w$
$\displaystyle=$
$\displaystyle[y_{v}^{2}-\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}]+2[w^{\top}(\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}-y_{v}x_{v})]+w^{\top}[x_{v}x_{v}^{\top}-\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}]w$

###  B.2 Proof of Lemma 6

First, to pick $x_{v}$, notice that
$w^{\top}\left(x_{v}x_{v}^{\top}-S_{xx}\right)w=\langle
x_{v},w\rangle^{2}-w^{\top}S_{xx}w$, so we can focus on maximizing $\langle
x_{v},w\rangle^{2}$.

Now, consider we set the backdoor trigger $x_{v}\equiv\alpha w$, where
$\alpha$ is some scalar. The our maximization objective becomes $\langle
x_{v},w\rangle^{2}=\alpha^{2}\|w\|_{2}^{2}$. Thus, if we don’t put constrain
on the norm of backdoor trigger $x_{v}$, this term can be infinite.

Now, suppose the backdoor trigger should have bounded $\ell_{2}$ norm, say
$\|x_{v}\|_{2}\leq 1$, then setting $x_{v}\equiv w/\|w\|_{2}$ will maximize
the objective at the value $\|w\|_{2}^{2}$.

Thus, the intuition to pick $x_{v}$ is to pick parallel to model weight $w$
and make the norm of $x_{v}$ as big as possible.

Now, let’s consider $x_{v}=\alpha w$. Notice that
$w^{\top}(S_{yx}-y_{v}x_{v})=w^{\top}S_{yx}-y_{v}\langle
w,x_{v}=w^{\top}S_{yx}-y_{v}\alpha\|w\|_{2}^{2}$.

Let’s take $\alpha<0$, then we can maximize the objective by picking $y_{v}$
as large as possible. Say we have a bound on the response $y_{v}$ such that
$|y_{v}|\leq B$. Then we pick $y_{v}=B$.

In conclusion, to make max distortion on risk, we set the backdoor trigger as
$v=(-\alpha w,B)$.

We begin with the expression:

$\left[y_{v}^{2}-S_{y}\right]+2\left[w^{\top}(S_{yx}-y_{v}x_{v})\right]+w^{\top}(x_{v}x_{v}^{\top}-S_{xx})w$

Given the relationship $v=(x_{v},y_{v})=(-\alpha w,B)$, we have:

$\displaystyle x_{v}=-\alpha w,$ $\displaystyle y_{v}=B.$

Substituting these values into the expression, we proceed to evaluate each
term separately.

First, consider $\left[y_{v}^{2}-S_{y}\right]$: Since $y_{v}=B$, we have
$y_{v}^{2}=B^{2}$. Therefore,

$\left[y_{v}^{2}-S_{y}\right]=B^{2}-S_{y}.$

Next, we evaluate $2\left[w^{\top}(S_{yx}-y_{v}x_{v})\right]$: Given $y_{v}=B$
and $x_{v}=-\alpha w$, we find $y_{v}x_{v}=B(-\alpha w)=-\alpha Bw$.
Consequently,

$S_{yx}-y_{v}x_{v}=S_{yx}-(-\alpha Bw)=S_{yx}+\alpha Bw,$

and thus,

$2\left[w^{\top}(S_{yx}-y_{v}x_{v})\right]=2\left[w^{\top}(S_{yx}+\alpha
Bw)\right]=2\left(w^{\top}S_{yx}+\alpha Bw^{\top}w\right).$

Finally, we examine $w^{\top}(x_{v}x_{v}^{\top}-S_{xx})w$: With $x_{v}=-\alpha
w$, it follows that $x_{v}x_{v}^{\top}=\alpha^{2}ww^{\top}$. Therefore,

$x_{v}x_{v}^{\top}-S_{xx}=\alpha^{2}ww^{\top}-S_{xx},$

which gives

$w^{\top}(x_{v}x_{v}^{\top}-S_{xx})w=w^{\top}(\alpha 2ww^{\top}-S_{xx})w.$

This simplifies to

$w^{\top}(\alpha^{2}ww^{\top})w-w^{\top}S_{xx}w,$

where

$w^{\top}(\alpha^{2}ww^{\top})w=\alpha^{2}(w^{\top}w)(w^{\top}w)=\alpha^{2}\|w\|^{2}\|w\|^{2}=\alpha^{2}\|w\|^{4}.$

Thus, we obtain

$w^{\top}(x_{v}x_{v}^{\top}-S_{xx})w=\alpha^{2}\|w\|^{4}-w^{\top}S_{xx}w.$

Combining all the evaluated parts, we arrive at:

$B^{2}-S_{y}+2(w^{\top}S_{yx}+\alpha
Bw^{\top}w)+\alpha^{2}\|w\|^{4}-w^{\top}S_{xx}w.$

Organizing the terms, we have:

$B^{2}-S_{y}+2w^{\top}S_{yx}+2\alpha
B\|w\|^{2}+\alpha^{2}\|w\|^{4}-w^{\top}S_{xx}w.$

###  B.3 Proof of Lemma 7

Given square loss $\ell(w,(x,y))=(y-\langle w,x\rangle)^{2}$, the gradient is
$\nabla_{w}\ell(w,(x,y))=-2(y-\langle w,x\rangle)x$.

Let’s find the gradient:

$\displaystyle\nabla_{w}J(w;v,D_{0})$ (32) $\displaystyle\equiv$
$\displaystyle\nabla_{w}\ell(w,v)-\nabla_{w}L(w;D_{0})$ $\displaystyle=$
$\displaystyle\nabla_{w}(y_{v}-\langle
w,x_{v}\rangle)^{2}-\nabla_{w}\frac{1}{n}\sum_{i=1}^{n}(y_{i}-\langle
w,x_{i}\rangle)^{2}$ $\displaystyle=$
$\displaystyle\nabla_{w}[y_{v}^{2}-2w^{\top}y_{v}x_{v}+w^{\top}x_{v}x_{v}^{\top}w]-\nabla_{w}[\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}-w^{\top}(\frac{2}{n}\sum_{i=1}^{n}y_{i}x_{i})+w^{\top}(\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top})w]$
$\displaystyle=$
$\displaystyle\nabla_{w}[y_{v}^{2}-\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}]-2\nabla_{w}[w^{\top}(y_{v}x_{v}-\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i})]+\nabla_{w}w^{\top}[x_{v}x_{v}^{\top}-\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}]w$
$\displaystyle=$ $\displaystyle
2(\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}-y_{v}x_{v})+2w^{\top}[x_{v}x_{v}^{\top}-\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}]$

###  B.4 Proof of Lemma 8

Notice that $\|(x_{v}x_{v}^{\top}-S_{xx})w\|=\|x_{v}x_{v}^{\top}w-S_{xx}w\|$.
So we need to choose $x_{v}$ such that $x_{v}x_{v}^{\top}w$ is maximized in
$\ell_{2}$ norm sense.

Consider $x_{v}=\alpha w$, then $x_{v}x_{v}^{\top}w=\alpha^{2}\|w\|_{2}^{2}w$.
Then the objective become $\|(\alpha^{2}\|w\|_{2}^{2}I-S_{xx})w\|_{2}$

Notice that $\|S_{yx}-y_{v}x_{v}\|_{2}^{2}=\|S_{yx}-y_{v}\alpha
w\|_{2}^{2}=\|S_{yx}\|_{2}^{2}-2y_{v}\alpha\langle
w,S_{yx}\rangle+y_{v}^{2}\alpha^{2}\|w\|_{2}^{2}$.

Let’s do complete the square:

$\displaystyle\|S_{yx}\|_{2}^{2}-2y_{v}\alpha\langle
w,S_{yx}\rangle+y_{v}^{2}\alpha^{2}\|w\|_{2}^{2}$ (33) $\displaystyle=$
$\displaystyle(\alpha^{2}\|w\|_{2}^{2})[y_{v}^{2}-2\frac{\alpha\langle
w,S_{yx}\rangle}{\alpha^{2}\|w\|_{2}^{2}}y_{v}+\frac{\|S_{yx}\|_{2}^{2}}{\alpha^{2}\|w\|_{2}^{2}}]$
$\displaystyle=$
$\displaystyle(\alpha^{2}\|w\|_{2}^{2})\bigg{[}(y_{v}-\frac{\alpha\langle
w,S_{yx}\rangle}{\alpha^{2}\|w\|_{2}^{2}})^{2}+(\frac{\|S_{yx}\|_{2}^{2}}{\alpha^{2}\|w\|_{2}^{2}}-(\frac{\alpha\langle
w,S_{yx}\rangle}{\alpha^{2}\|w\|_{2}^{2}}y_{v})^{2})\bigg{]}$

So we should choose
$y_{v}=\frac{1}{\alpha}\langle\frac{w}{\|w\|_{2}^{2}},S_{yx}\rangle$.

To conclude, we need to pick the backdoor trigger $v=(\alpha
w,\langle\frac{w}{\alpha\|w\|_{2}^{2}},S_{yx}\rangle)$

Given the relationship $v=(x_{v},y_{v})=\left(\alpha
w,\left\langle\frac{w}{\alpha\|w\|_{2}^{2}},S_{yx}\right\rangle\right)$, we
have:

$\displaystyle x_{v}=\alpha w,$ $\displaystyle
y_{v}=\left\langle\frac{w}{\alpha\|w\|_{2}^{2}},S_{yx}\right\rangle.$

Substituting these values into the expression, we aim to evaluate:
$\left\|\left(S_{yx}-y_{v}x_{v}\right)+\left(x_{v}x_{v}^{\top}-S_{xx}\right)w\right\|_{2}.$

First, we calculate $S_{yx}-y_{v}x_{v}$: Given
$y_{v}=\left\langle\frac{w}{\alpha\|w\|_{2}^{2}},S_{yx}\right\rangle$ and
$x_{v}=\alpha w$, we find:

$y_{v}x_{v}=\left\langle\frac{w}{\alpha\|w\|_{2}^{2}},S_{yx}\right\rangle\alpha
w=\frac{\left\langle w,S_{yx}\right\rangle}{\|w\|_{2}^{2}}w.$

Thus,

$S_{yx}-y_{v}x_{v}=S_{yx}-\frac{\left\langle
w,S_{yx}\right\rangle}{\|w\|_{2}^{2}}w.$

Next, we calculate $x_{v}x_{v}^{\top}-S_{xx}$: Since $x_{v}=\alpha w$, it
follows that:

$x_{v}x_{v}^{\top}=(\alpha w)(\alpha w)^{\top}=\alpha^{2}ww^{\top}.$

Therefore,

$x_{v}x_{v}^{\top}-S_{xx}=\alpha^{2}ww^{\top}-S_{xx}.$

Combining these results, we obtain:

$\left\|\left(S_{yx}-\frac{\left\langle
w,S_{yx}\right\rangle}{\|w\|_{2}^{2}}w\right)+\left(\alpha^{2}ww^{\top}-S_{xx}\right)w\right\|_{2}.$

To simplify, we calculate $\left(\alpha^{2}ww^{\top}-S_{xx}\right)w$:

$(\alpha^{2}ww^{\top}-S_{xx})w=\alpha^{2}w(w^{\top}w)-S_{xx}w=\alpha^{2}\|w\|_{2}^{2}w-S_{xx}w.$

Thus, the final expression is:

$\left\|S_{yx}-\frac{\left\langle
w,S_{yx}\right\rangle}{\|w\|_{2}^{2}}w+\alpha
2\|w\|_{2}^{2}w-S_{xx}w\right\|_{2}.$

###  B.5 Proof of Lemma 9

To determine whether $\varepsilon$ increases with $\mu$ for the given equation

$\delta=\Phi\left(-\frac{\varepsilon}{\mu}+\frac{\mu}{2}\right)-e^{\varepsilon}\Phi\left(-\frac{\varepsilon}{\mu}-\frac{\mu}{2}\right),$

where $\delta$ is a positive constant, we need to analyze the relationship
between $\varepsilon$ and $\mu$. Specifically, we will verify if
$\frac{d\varepsilon}{d\mu}>0$.

We begin by differentiating both sides of the equation with respect to $\mu$:

First, consider the derivative of the left-hand side:

$\frac{d}{d\mu}\left(\Phi\left(-\frac{\varepsilon}{\mu}+\frac{\mu}{2}\right)-e^{\varepsilon}\Phi\left(-\frac{\varepsilon}{\mu}-\frac{\mu}{2}\right)\right)=0.$

Let:

$A=-\frac{\varepsilon}{\mu}+\frac{\mu}{2},$
$B=-\frac{\varepsilon}{\mu}-\frac{\mu}{2}.$

Thus, we rewrite the derivative as:

$\frac{d}{d\mu}\left(\Phi(A)-e^{\varepsilon}\Phi(B)\right)=0.$

Applying the chain rule, we obtain:

$\Phi^{\prime}(A)\frac{dA}{d\mu}-\frac{d}{d\mu}\left(e^{\varepsilon}\Phi(B)\right)=0.$

Next, we compute the derivatives of $A$ and $B$:

$\frac{dA}{d\mu}=\frac{\varepsilon}{\mu^{2}}+\frac{1}{2},$
$\frac{dB}{d\mu}=\frac{\varepsilon}{\mu^{2}}-\frac{1}{2}.$

We also need the derivative of the term $e^{\varepsilon}\Phi(B)$:

$\frac{d}{d\mu}\left(e^{\varepsilon}\Phi(B)\right)=e^{\varepsilon}\left(\Phi^{\prime}(B)\frac{dB}{d\mu}+\Phi(B)\frac{d\varepsilon}{d\mu}\right).$

Combining these results, we obtain:

$\Phi^{\prime}(A)\left(\frac{\varepsilon}{\mu^{2}}+\frac{1}{2}\right)-e^{\varepsilon}\left(\Phi^{\prime}(B)\left(\frac{\varepsilon}{\mu^{2}}-\frac{1}{2}\right)+\Phi(B)\frac{d\varepsilon}{d\mu}\right)=0.$

We then simplify to isolate $\frac{d\varepsilon}{d\mu}$:

$\Phi^{\prime}(A)\left(\frac{\varepsilon}{\mu^{2}}+\frac{1}{2}\right)-e^{\varepsilon}\Phi^{\prime}(B)\left(\frac{\varepsilon}{\mu^{2}}-\frac{1}{2}\right)=e^{\varepsilon}\Phi(B)\frac{d\varepsilon}{d\mu}.$

Solving for $\frac{d\varepsilon}{d\mu}$, we have:

$\frac{d\varepsilon}{d\mu}=\frac{\Phi^{\prime}(A)\left(\frac{\varepsilon}{\mu^{2}}+\frac{1}{2}\right)-e^{\varepsilon}\Phi^{\prime}(B)\left(\frac{\varepsilon}{\mu^{2}}-\frac{1}{2}\right)}{e^{\varepsilon}\Phi(B)}.$

To determine if $\frac{d\varepsilon}{d\mu}>0$, we must ensure that the
numerator is positive. Since $\Phi^{\prime}(x)>0$ for all $x$, we need:

$\Phi^{\prime}(A)\left(\frac{\varepsilon}{\mu^{2}}+\frac{1}{2}\right)-e^{\varepsilon}\Phi^{\prime}(B)\left(\frac{\varepsilon}{\mu^{2}}-\frac{1}{2}\right)>0.$

Given that $\Phi^{\prime}(x)$ is symmetric and positive, we consider two
cases:

  * •

1\. If $\varepsilon$ is relatively small, then $\frac{\varepsilon}{\mu^{2}}$
is small, making the $\frac{1}{2}$ terms dominant and ensuring a positive
numerator.

  * •

2\. If $\varepsilon$ is large, the interaction between the exponential and
normal terms determines the dynamics. Generally, the exponential growth in the
numerator balances the exponential terms in the denominator, maintaining
positivity.

Overall, $\frac{d\varepsilon}{d\mu}>0$ suggests that $\varepsilon$ increases
with $\mu$.

###  B.6 Proof of Lemma 10

Based on Lemma 4, we should focus on the signal-to-noise ratio

$d=\frac{\left\|\mu\left(D_{1}\right)-\mu\left(D_{0}\right)\right\|_{2}}{\sigma_{\gamma}},$

where $\mu(D)\equiv-\gamma\nabla_{w}L(w;D)$ for a given dataset $D$ and
$\sigma_{\gamma}\equiv\gamma\sigma$.

By direct calculation, we have

$d=\frac{\|\nabla_{w}L(w;D_{1})-\nabla_{w}L(w;D_{0})\|_{2}}{\sqrt{\gamma}\sigma}$

Apply Lemma 3, we have

$d=\frac{\|\nabla_{w}\ell\left(w;\left(x_{v},y_{v}\right)\right)-\nabla_{w}L\left(w;D_{0}\right)\|_{2}}{\sqrt{\gamma(n+1)}\sigma}$

Borrow computation in 32, in square loss case, we have

$d=\frac{\|\left(S_{yx}-y_{v}x_{v}\right)+w^{\top}\left(x_{v}x_{v}^{\top}-S_{xx}\right)\|_{2}}{\sqrt{\gamma(n+1)/2}\sigma}$

Given the function

$d=\frac{\left\|\left(S_{yx}-y_{v}x_{v}\right)+w^{\top}\left(x_{v}x_{v}^{\top}-S_{xx}\right)\right\|_{2}}{\sqrt{\gamma(n+1)/2}\sigma},$

where:

  1. 1.

$S_{y}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}y_{i}^{2}$,

  2. 2.

$S_{yx}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}y_{i}x_{i}$,

  3. 3.

$S_{xx}(D_{0})=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\top}$,

we seek to maximize $d$ by optimizing $y_{v}$ (a scalar) and $x_{v}$ (an
$n$-dimensional vector).

###  B.7 Proof of Lemma 11

We leverage the result at lemma 7 and compute how much privacy budget will
occur by adding such backdoor trigger. Recall in this case the signal-to-noise
ratio is
$d=\frac{\left\|\left(S_{yx}-y_{v}x_{v}\right)+w^{\top}\left(x_{v}x_{v}^{\top}-S_{xx}\right)\right\|_{2}}{\sqrt{\gamma(n+1)/2}\sigma}$.

The results follows from the following lemma:

######  Lemma 12.

Suppose $-\frac{\epsilon}{\mu}+\frac{\mu}{2}\leq 1/2$, then we have

$\epsilon\geq 0.69+\ln(\delta-\Phi(\frac{\mu}{2})).$ (34)

Thus, give $\mu$, we can have a lower bound on the privacy budget $\epsilon$.

###### Proof.

From (2), we have

$\displaystyle e^{\epsilon}=$
$\displaystyle\frac{\delta-\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2})}{\Phi(-\frac{\epsilon}{\mu}-\frac{\mu}{2})}$
(35) $\displaystyle\geq$ $\displaystyle
2(\delta-\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2}))$ $\displaystyle\geq$
$\displaystyle 2(\delta-\Phi(\frac{\mu}{2})).$

The first inequality is due to $-\frac{\epsilon}{\mu}+\frac{\mu}{2}\leq 1/2$
so $\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2})\leq 1/2$ and hence
$1/\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2})\geq 2$. The second inequality is
due to $\Phi(x)$ is monotone increasing and hence
$\Phi(\frac{\mu}{2})\geq\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2})$ and hence
$-\Phi(\frac{\mu}{2})\leq-\Phi(-\frac{\epsilon}{\mu}+\frac{\mu}{2})$. ∎