# Rethinking Backdoor Attacks

Alaa Khaddaj Guillaume Leclerc11footnotemark: 1 Aleksandar
Makelov11footnotemark: 1 Kristian Georgiev11footnotemark: 1<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>MIT MIT MIT MIT
Hadi Salman Andrew Ilyas Aleksander Mądry<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>MIT MIT MIT Equal Contribution.

###### Abstract

In a backdoor attack, an adversary inserts maliciously constructed backdoor
examples into a training set to make the resulting model vulnerable to
manipulation. Defending against such attacks typically involves viewing these
inserted examples as outliers in the training set and using techniques from
robust statistics to detect and remove them.

In this work, we present a different approach to the backdoor attack problem.
Specifically, we show that without structural information about the training
data distribution, backdoor attacks are indistinguishable from naturally-
occuring features in the data—and thus impossible to “detect” in a general
sense. Then, guided by this observation, we revisit existing defenses against
backdoor attacks and characterize the (often latent) assumptions they make and
on which they depend. Finally, we explore an alternative perspective on
backdoor attacks: one that assumes these attacks correspond to the strongest
feature in the training data. Under this assumption (which we make formal) we
develop a new primitive for detecting backdoor attacks. Our primitive
naturally gives rise to a detection algorithm that comes with theoretical
guarantees and is effective in practice.

###  1 Introduction

A backdoor attack [GDG17, CLL+17, ABC+18, SHN+18, TTM19] allows an adversary
to manipulate the predictions of a (supervised) machine learning model by
modifying a small fraction of the training set inputs. This involves adding a
fixed pattern (called the “trigger”) to some training inputs, and setting the
labels of these inputs to some fixed value $y_{b}$. This intervention enables
the adversary to take control of the resulting models’ predictions at
deployment time by adding the trigger to inputs of interest.

Backdoor attacks pose a serious threat to machine learning systems as they are
easy to deploy and hard to detect. Indeed, recent work has shown that
modifying even a very small number of training inputs suffices for mounting a
successful backdoor attack on models trained on web-scale datasets [CJC+23].
Consequently, there is a growing body of work on backdoor attacks and
approaches to defending against them [CCB+18, TLM18, JSR21, HKS+21, LF21,
JCG21].

A prevailing perspective on defending against backdoor attacks treats the
manipulated training inputs as outliers, and thus draws a parallel between
backdoor attacks and the classic data poisoning setting from robust
statistics. In data poisoning, one receives data where a
$(1-\varepsilon)$-fraction is sampled from a known distribution $\mathcal{D}$,
and an $\varepsilon$-fraction is chosen by an adversary. The goal is to detect
the adversarially chosen inputs, or to learn a good classifier in spite of the
presence of these inputs. This perspective is a natural one–and has led to a
host of defenses against backdoor attacks [CCB+18, TLM18, HKS+21]—however, is
it the right way to approach the problem?

In this work, we take a step back from the above view and offer a different
perspective on backdoor attacks: rather than viewing the manipulated inputs as
outliers, we view the trigger used in the backdoor attack as simply another
feature in the data. To justify this perspective, we demonstrate that
backdoors triggers can be indistinguishable from features already present in
the dataset. On one hand, this immediately pinpoints the difficulty of
detecting backdoor attacks, especially when they can correspond to arbitrary
trigger patterns. On the other hand, this view suggests there might be an
equivalence between detecting backdoor attacks and surfacing features present
in the data.

Equipped with this perspective, we introduce a primitive for studying features
in the input data and characterizing a feature’s strength. This primitive then
gives rise to an algorithm for detecting backdoor attacks in a given dataset.
Specifically, our algorithm flags the training examples containing the
strongest feature as being manipulated, and removes them from the training
set. We empirically verify the efficacy of this algorithm on a variety of
standard backdoor attacks. Overall, our contributions are as follows:

  * •

We demonstrate that in the absence of any knowledge about the distribution of
natural image data, the triggers used in a backdoor attacks are
indistinguishable from existing features in the data. This observation implies
that every backdoor defense must make assumptions—either implicit or
explicit—about the structure of the distribution or of the backdoor attack
itself (see Section 2).

  * •

We re-frame the problem of detecting backdoor attacks as one of detecting a
feature in the data, and specifically the feature with the strongest effect on
the model predictions (see Section 3).

  * •

We show how to detect backdoor attacks under the corresponding assumption
(i.e., that the backdoor trigger is the strongest feature in the dataset). We
provide theoretical guarantees on our approach’s effectiveness at identifying
inputs with a backdoor trigger, and demonstrate experimentally that our
resulting algorithm (or rather, an efficient approximation to it) is effective
in a range of settings (see Sections 4 and 5).

###  2 Setup and Motivation

In this section, we formalize the problem of backdoor attack and defense, and
introduce the notation that we will use throughout the paper. We then argue
that defending against backdoor attacks requires making certain assumptions,
and that all existing defenses make such assumptions, whether implicitly or
explicitly.

Let us fix a learning algorithm $\mathcal{A}$ and an input space
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$ (e.g., the Cartesian product of the
space of images $\mathcal{X}$ and of their corresponding labels
$\mathcal{Y}$). For a given dataset $S\in\mathcal{Z}^{n}$, and a given example
$z=(x,y)\in\mathcal{Z}$, where $x$ is an input of label $y$, we define the
model output function $f(z;S)$ as some metric of interest (e.g., loss)
evaluated on the input $z$ after training a model on dataset $S$.111For
example, given $z=(x,y)$, we can set $f(z;S)=\mathbb{P}[f(x)=y]$ where the
probability is over the randomness of the training process. Alternatively, we
can use the cross-entropy loss at $z$, etc. In this paper, we define $f$ to be
the classification margin on example $z$ (see Appendix A). We also define, for
any two sets $S$ and $S^{\prime}$,

$\text{Perf}(S\to S^{\prime})=\frac{1}{|S^{\prime}|}\sum_{z\in
S^{\prime}}f(z;S)$

i.e., the performance on dataset $S^{\prime}$ of a model trained on dataset
$S$.

##### Backdoor attack.

In a backdoor attack, an attacker observes a “clean” set of training examples
$S$, and receives an attack budget $\alpha\in(0,1)$ that indicates the
fraction of the training set that the adversary can manipulate222The budget
$\alpha$ is typically a small value, e.g., 1%. Recent work has shown effective
attacks can be mounted on web-scale datasets by poisoning ~100 examples
[CJC+23].. The attacker then produces (a) a partitioning of $S$ into two sets
$S_{P}$ and $S_{C}$, where $S_{P}$ is the set to be poisoned, such that
$|S_{P}|\leq\alpha|S|$; and (b) a trigger function
$\tau:\mathcal{Z}\to\mathcal{Z}$ that modifies training examples in a
systematic way, e.g., by inserting a fixed pattern (trigger) in the input
image $x$ and changing its label $y$. The attacker then transforms $S_{P}$
using the trigger function $\tau$ to get $P=\tau(S_{P})$, which replaces
$S_{P}$ in the training set. Here, we let $\tau(S^{\prime})$ for any set
$S^{\prime}$ denote the set $\\{\tau(z):z\in S^{\prime}\\}$. Overall, the
attacker’s goal is, given a set $S^{\prime}$ of inputs of interest, to design
$P$ and $\tau$ so that they satisfy two properties:

  * •

Effectiveness: Training on the new (“backdoored”) dataset should make models
vulnerable to the trigger function. In other words, $\text{Perf}(S_{C}\cup
P\to\tau(S^{\prime}))$ should be large.

  * •

Imperceptibility: Training on the backdoored dataset should not significantly
change the performance of the model on “clean” inputs. That is,
$\text{Perf}(S_{C}\cup P\to S^{\prime})\approx\text{Perf}(S\to S^{\prime}).$

Figure 1 overviews a simple example of such an attack, proposed by [GDG17].

Figure 1:  An illustration of a backdoor attack. An adversary backdoors the
training set by inserting a trigger (red square) in a small fraction $\alpha$
of the training images, and setting the label of these images to a desired
class, e.g., “dog.” At inference time, the adversary can activate the backdoor
by inserting the red trigger into an image. In the example above, the image of
the horse (top right) is correctly classified by a model trained on the
backdoor training set. After the trigger is inserted into this image, the
model prediction on the image flips to “dog”.

####  2.1 Is the Trigger a Backdoor or a Feature?

The prevailing perspective on backdoor attacks casts them as an instance of
data poisoning, a concept with a rich history in robust statistics [HRR+11].
In data poisoning, the goal is to learn from a dataset where most of the
points—an $(1-\varepsilon)$-fraction of them—are drawn from the data
distribution $\mathcal{D}$, and the remaining points—an $\varepsilon$-fraction
of them—are chosen by an adversary. This parallel between this “classical”
data poisoning setting and that of backdoor attacks is natural. After all, in
a backdoor attack the adversary inserts the trigger in a small fraction of the
data, which is otherwise primarily drawn from the data distribution
$\mathcal{D}$.

However, is this the right parallel to guide us? Recall that in the classical
data poisoning setting, leveraging the structure of the distribution
$\mathcal{D}$ is essential to obtaining any (theoretical) guarantees. For
example, the developed algorithms often leverage strong explicit
distributional assumptions, such as (sub-)Gaussianity of the training batch
[LM19]. In settings such as computer vision, however, it is unclear whether
such structure is available. In fact, we lack almost any formal
characterization of how image datasets are distributed.

We thus argue that without strong assumptions on the structure of the input
data, backdoor triggers are fundamentally indistinguishable from features
already present in the dataset. We illustrate this point with the following
experiments.

(a) An adversary can craft a trigger that is indistinguishable from a natural
feature and use it as a backdoor. Here, we “backdoor” the ImageNet training
set by generating (using 3DB [LSI+21]) images of hats and pasting them on
varying numbers of “cat” images. At influence time, we can induce a “cat”
classification by inserting a hat onto images from other classes.

(b) Without changing the training dataset at all, adversaries can exploit
patterns which act as “natural backdoors.” For example, the nature of the
“tennis ball” class in ImageNet makes it so that an attacker can induce a
“tennis ball” classification with just a small test-time perturbation. By most
definitions, therefore, this tennis ball would constitute a backdoor attack.

Figure 2: An adversary can leverage (a) plausible features or (b) naturally
occurring features in order to mount an effective backdoor attack.

##### Backdoor attacks can look like “plausible” features.

It turns out that one can mount a backdoor attack using features that are
already present (but rare) in the dataset. Specifically, in Figure 2(a), we
demonstrate how to execute a backdoor attack on an ImageNet classifier using
hats in place of a fixed (artificial) trigger pattern. The resulting dataset
is entirely plausible in that the backdoored images are (at least somewhat)
realistic, and the corresponding labels are unchanged.333With some more
careful photo editing or using diffusion models [SE19, HJA20], one could
imagine embedding the hats in a way that makes the resulting examples appear
more in-distribution and thus look unmodified even to a human. At inference
time, however, the hats act as an effective backdoor trigger: model
predictions are skewed towards cats whenever a hat is added on the test
sample. Should we then expect a backdoor detection algorithm to flag these
(natural-looking) in-distribution examples?

##### Backdoor attacks can occur naturally.

In fact, the adversary need not modify the dataset at all—they can use
features already present in the data to manipulate models at test time. For
example, a naturally-occurring trigger for ImageNet is the presence of a
tennis ball (Figure 2(b)). Similarly, [LLT+19] show that on CIFAR-10, “deer
antlers” are another such natural backdoor, i.e., adding antlers to images
from other classes makes models more likely to classify those images as deer.

These examples highlight that we need to make assumptions, as otherwise the
task is fundamentally ill-defined. Indeed, trigger patterns for backdoor
attacks are no more indistinguishable than features in the data. In
particular, detecting trigger pattern is no different than detecting hats,
backgrounds, or any other spurious feature.

####  2.2 Implicit Assumptions in Existing Defenses

Since detecting backdoored examples without assumptions is an ill-defined
task, all existing backdoor defenses must rely on either implicit or explicit
assumptions on the structure of the data or the structure of the backdoor
attack. To illustrate this point, we examine some of the existing backdoor
defenses and identify the assumptions they make. As we will see, each of these
assumptions gives rise to a natural failure mode of the corresponding defense
too (when these assumptions are not satisfied).

##### Latent separability.

One line of work relies on the assumption that backdoor examples and
unmodified (“clean”) examples are separable in some latent space [TLM18,
HKS+21, QXM+22, CCB+18, HLW+22]. The corresponding defenses thus perform
variants of outlier detection in the latent representation space of a neural
network (inspired by approaches from robust statistics). Such defenses are
effective against a broad range of attacks, but an attacker aware of the type
of defense can mount an “adaptive” attack that succeeds by violating that
latent separability assumption [QXM+22].

##### Structure of the backdoor.

Another line of work makes structural assumptions on the backdoor trigger
(e.g., its shape, size, etc.) [WYS+19, ZPM+21, LYM22, YLM22]. For example,
[WYS+19] assume that the trigger has small $\ell_{2}$ norm. Such defenses can
be bypassed by an attacker that deploys a trigger that remains hard to discern
while violating these assumptions. In fact, the “hat” trigger in Figure 2(a)
is an example of such trigger.

##### Effect of the backdoor on model behavior.

Another possibility is to assume that backdoor examples have a nonpositive
effect on the model’s accuracy on the clean examples. This assumption has the
advantage of not relying on the specifics of the trigger or its latent
representation. In particular, a recent defense by [JSR21] makes this
assumption explicit and achieves state-of-the-art results against a range of
backdoor attacks. A downside of this approach is that suitably constructed
clean-label attacks, e.g., [TTM19], can violate the incompatibility assumption
and remain undetected.

##### Structure of the clean data.

Finally, yet another line of work assumes that the (unmodified) dataset has
naturally-occuring features whose support, i.e., the number of examples
containing the feature, is (a) larger than the adversary’s attack budget
$\alpha$, and (b) sufficiently strong to enable good generalization. The
resulting defenses are then able to broadly certify that no attack within the
adversary’s budget will be successful. For example, [LF21] use an ensembling
technique to produce a classifer that is _certifiably_ invariant to changing a
fixed number of training inputs, thus ensuring that no adversary can mount a
successful backdoor attack.

For real-world datasets, however, this assumption (i.e., that well-supported
features alone suffice for good generalization) seems to be unrealistic.
Indeed, many features that are important for generalization are only supported
on a small number of examples [Fel19]. Accordingly, the work of [LF21] can
only certify robustness against a limited number of backdoor examples while
maintaining competitive accuracy.

###  3 An Alternative Assumption

The results of the previous section suggest that without making additional
assumptions, the delineation between a backdoor trigger and a naturally-
occurring feature is largely artificial. So, given that we cannot escape
making an assumption, what is the right assumption to make?

In this paper, we propose to assume that the backdoor trigger is the strongest
feature in the dataset (in a sense we will make precise soon). Importantly
(and unlike the assumptions discussed in Section 2.2), this assumption is tied
to the success of the backdoor attack itself. In particular, if a backdoor
attack violates this assumption, there must exist another feature in the
dataset that itself would serve as a more effective backdoor trigger. As a
result, there would be no reason for a defense to identify the former over the
latter.

We now make that assumption precise. We begin by providing a definition of
“feature,” along with a corresponding definition of the “support” of any
feature. Using these definitions, we can formally state our goal as
identifying all the training examples that provide support for the feature
corresponding to the backdoor attack. This involves proposing a definition of
feature “strength”—a definition that is directly tied to the effectiveness of
the backdoor attack. We conclude by precisely stating our assumption that the
backdoor trigger is the strongest feature in the training dataset.

##### Setup.

For a task with example space $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$
(e.g., the space of image-label pairs—see Section 2), we define a feature as a
function $\phi\in\mathcal{X}\to\\{0,1\\}$.444 In reality, one would want to
limit $\phi$ to some restricted class of “valid” features $\mathcal{V}$. In
this case, all of our results still hold with only minor adaptations.  For
example, a feature $\phi_{ears}$ might map from an image $x\in\mathcal{X}$ to
whether the image contains “cat ears.” Note that by this definition, every
backdoor attack (as formalized in Section 2) corresponds to a feature
$\phi_{p}$ that “detects” the corresponding trigger transformation $\tau$
(that is, $\phi_{p}$ outputs $1$ on inputs in the range of $\tau$, and $0$ on
all other inputs).

For a fixed training set $S\in\mathcal{Z}^{n}$, we can describe a feature
$\phi$ by its support, which we define as the subset of training inputs that
activate the corresponding function:

######  Definition 1 (Feature support).

Let $\phi:\mathcal{X}\to\\{0,1\\}$ be a feature (i.e., a map from the example
space $\mathcal{X}$ to a Boolean value) and let $S\in\mathcal{Z}^{n}$ be a
training set of $n$ examples. We define the support of the feature $\phi$ as
$\Phi(S)=\text{supp}_{\phi}(S)=\\{z=(x,y)\in S\mid\phi(x)=1\\}$, i.e. the
subset of $S$ where the feature $\phi$ is present.

Observe that in the case of a backdoor attack using a backdoor trigger
$\phi_{p}$, the corresponding feature support $\Phi_{p}(S)$ is the set of
training examples that contain the trigger, and must necessarily include the
set of backdoored examples $P$.

##### Characterizing feature strength.

Recall that our goal in this section is to place a (formal) assumption on a
backdoor attack as corresponding to the strongest feature in a dataset. To
accomplish this goal, we first need a way to quantify the “strength” of a
given feature $\phi$. Intuitively, we would like to call a feature “strong” if
adding a single example containing that feature to the training set
significantly changes the resulting model. (That is, if the counterfactual
value of examples containing feature $\phi$ is high.)

To this end, let us fix a distribution $\mathcal{D}_{S}$ over subsets of the
training set $S$. For any feature $\phi$ and natural number $k$, let the
$k$-output of $\phi$ be the expected model output (over random draws of the
training set from $\mathcal{D}_{S}$) on examples with feature $\phi$,
conditioned on there being $k$ examples with feature $\phi$ in the training
set:

######  Definition 2 (Output function of a feature $\phi$).

For a feature $\phi$, and a distribution $\mathcal{D}_{S}$ over subsets of the
training set $S$, we define the feature output function $g_{\phi}$ as the
function that maps any integer $k$ to the expected model output on examples
with that feature $\phi$ when training on exactly $k$ training inputs with
that feature $\phi$, i.e.,

$\displaystyle
g_{\phi}(k)=\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\bigg{|}|\Phi(S^{\prime})|=k,z\not\in
S^{\prime}\right]\right]$ (1)

where $z\sim\Phi(S)$ represents a random sample from the support $\Phi(S)$ of
the feature $\phi$ in the set $S$.

Intuitively, the feature output function $g_{\phi}(k)$ should grow quickly, as
a function of $k$, for strong features and slowly for weak features. For
example, adding an image of a particular rare dog breed to the training set
will rapidly improve accuracy on that dog breed, whereas adding images with a
weak feature like “sky” or “grass” will impact the accuracy of the model much
less. In the context of backdoor attacks, the “effectiveness” property
(Section 2) implies that

$g_{\phi_{p}}(|P|)-g_{\phi_{p}}(0)\qquad\text{ is large}$

where, again, $\phi_{p}$ is the backdoor trigger. Motivated by this
observation, we define the strength of a feature $\phi$ as the rate of change
of the corresponding output function.

######  Definition 3 (Strength of a feature $\phi$).

We define the $k$-strength of a feature $\phi$ as the following function
$s_{\phi}(k)$:

$\displaystyle s_{\phi}(k)=g_{\phi}(k+1)-g_{\phi}(k)$ (2)

Note that we can extend Definition 2 and Definition 3 to individual examples
too. Specifically, we can define for a feature $\phi$ the model k-output at an
example $z$ as:

$g_{\phi}(z,k)=\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S};S^{\prime}\not\ni
z}\left[f(z;S^{\prime})\bigg{|}|\Phi(S^{\prime})|=k\right].$

Similarly, we can define the k-strength of a feature $\phi$ at an example $z$
as: $s_{\phi}(z,k)=g_{\phi}(z,k+1)-g_{\phi}(z,k)$.

To provide intuition for Definitions 2 and 3, we instantiate both of them in
the context of the trigger feature in a very simple backdoor attack.
Specifically, we alter the CIFAR-10 training set, planting a small red square
in a random 1% of the training examples, and changing their label to class “0”
(so that at inference time, we can add the red square to the input image and
make its predicted class be “0”).

In this poisoned dataset, the backdoor feature $\phi_{p}$ is a detector of the
presence of a red square, and the support $\Phi_{p}$ comprises the randomly
selected 1% of altered images (i.e., the backdoor images). We train 100,000
models on random $50\%$ fractions of this poisoned dataset, and use them to
estimate the $k$-output and $k$-strength of the backdoor feature.
Specifically, for a variety of examples $z\in S$, we (a) find the models whose
training sets had exactly $k$ backdoor images and did not contain $z$; and (b)
average the model output on $z$ for each of these models.

In Figure 3, we plot the resulting model output for examples $z\in\Phi_{p}(S)$
that have the feature $\phi_{p}$ (orange lines) and also for examples
$z\not\in\Phi_{p}(S)$ that do not contain the backdoor feature. Note that by
Definition 2, the average $k$-output of the backdoor feature is the average of
the orange lines, and by Definition 3, the average $k$-strength of the
backdoor feature is the average (instantaneous) slope of the orange line.

We observe that for the poisoned examples, the $k$-strength is consistently
positive (i.e., the output monotonically increases). This observation
motivates our assumption about the strength of backdoor trigger features:

######  Assumption 1.

Let $\phi_{p}$ be the backdoor trigger feature, and let $\Phi_{p}(S)$ be its
support (i.e., the backdoored training examples) and let $p:=|\Phi_{p}(S)|$.
Then, for some $\delta>0$, $\alpha\in(0,1)$ and all other features $\phi$ with
$|\Phi(S)|=p$, we assume that

$s_{\phi_{p}}\left(\alpha\cdot p\right)\geq\delta+s_{\phi}(\alpha\cdot p)$

##### Justifying the assumption.

As we already discussed, 1 has the advantage of being directly tied to the
effectiveness of the backdoor attack. In particular, we know that in the
absence of backdoored training examples, the model should do poorly on the
inputs with the backdoor trigger (otherwise, we would consider the model to
have already been compromised). Thus, $g_{\phi_{p}}(0)$ is small. On the other
hand, for the backdoor attack to be effective, we must have that
$g_{\phi_{p}}(p)$ is large, i.e., models trained on the backdoor training set
should perform “well” on backdoored inputs. The mean value theorem555
Informally, the mean value theorem says that for any continuous function $f$
and any interval $[a,b]$, there must exist $c\in[a,b]$ such that the rate of
change of $f$ at $c$ is equal to $\frac{f(b)-f(a)}{b-a}$.  thus implies that
there must one point $0\leq k\leq p$ at which $s_{\phi_{p}}(k)$ is large.

Figure 3:  Backdoored CIFAR10 examples. Each orange (resp. blue) line
corresponds to a poisoned (resp. clean) example. The $x$-value represents the
number of backdoored examples present in the training set, while the $y$-value
represents the model output (average margin) at that specific example. The
rate of change of the model output represents the feature strength
$s_{\phi_{p}}(k)$. We observe that the model output of backdoored images
(orange lines) increases as more backdoored examples are included in the
training set. In contrast, the model output for clean images (blue lines) is
not affected by the number of poisoned training examples.

###  4 A Primitive for Detecting Backdoored Examples

The perspective set forth in the previous sections suggests that we need to be
able to analyze the strength of features present in a dataset to understand
the effect of these features on a model’s predictions. Particularly, such an
analysis would allow us to translate 1 into an algorithm for detecting
backdoor training examples. Specifically, we would be able to estimate the
feature strength $s_{\phi}(k)$ for a given feature $\phi$. Now, if we had a
specific feature $\phi$ in mind, we could simply compute the feature strength
$s_{\phi}(k)$ using Equations (1) and (2) directly. In our case, however,
identifying the feature of interest (i.e., the backdoor feature) is
essentially our goal.

To this end, in this section we first show how to estimate the strength of all
viable features $\phi$ simultaneously. We then demonstrate how we can leverage
this estimate to detect the strongest one among them. Our key tool here will
be the datamodeling framework [IPE+22]. In particular, [IPE+22] have shown
that, for every example $z$, and for a model output function $f$ corresponding
to training a deep neural network and evaluating it on that example, there
exists a weight vector $w_{z}\in\mathbb{R}^{|S|}$ such that:

$\mathbb{E}[f(z;S^{\prime})]\approx\bm{1}_{S^{\prime}}^{\top}w_{z}$ (3)

for subsets $S^{\prime}\sim\mathcal{D}_{S}$, where
$\bm{1}_{S^{\prime}}\in\\{0,1\\}^{|S|}$ is the indicator vector of
$S^{\prime}$666The indicator vector $\bm{1}_{S^{\prime}}$ takes a value of 1
at index $i$, if training example $z_{i}\in S^{\prime}$, and 0 otherwise.. In
other words, we can approximate the specific outcome of training a deep neural
network on a given subset $S^{\prime}\subset S$ as a linear function of the
presence of each training data example. As the ability of the datamodeling
framework to capture the model output function will be critical to the
effectiveness of our method, we state it as an explicit assumption.

######  Assumption 2 (Datamodel accuracy).

For any example $z$, with a corresponding datamodel weight $w_{z}$, we have
that

$\displaystyle\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[\left(\mathbb{E}[f(z;S^{\prime})]-\bm{1}_{S^{\prime}}^{\top}w_{z}\right)^{2}\right]\leq\varepsilon$
(4)

where $\epsilon>0$ represents a bound on the error of estimating the model
output function using datamodels.

2 essentially guarantees that datamodels provide an accurate estimate of the
model output function for any example $z$ and for any random subset
$S^{\prime}\sim\mathcal{D}_{S}$. Also, we can in fact verify this assumption
by sampling sets $S^{\prime}$ and computing the error from 2 directly
(replacing the inner expectation with an empirical average).

Now, it turns out that this property alone—captured as a formal lemma
below—suffices to estimate the feature strength $s_{\phi}(k)$ of any feature
$\phi$.

######  Lemma 1.

For a feature $\phi$, let $\bm{1}_{\phi(S)}$ be the indicator vector of its
support $\Phi(S)$, $\mathbbm{1}_{n}$ be the $n$-dimensional vector of ones,
and let $h:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be defined as

$h(v)=\frac{1}{\|v\|_{1}}v-\frac{1}{n-\|v\|_{1}}(\mathbbm{1}_{n}-v).$

Then, under 2, we have that there exists some $C>0$ such that

$\left|s_{\phi}(\alpha\cdot|\Phi(S)|)-\frac{1}{|\Phi(S)|}\sum_{z\in\Phi(S)}w_{z}^{\top}h(\bm{1}_{\phi(S)})\right|\leq
C{\varepsilon^{1/2}n^{1/4}}.$ (5)

where $\epsilon$ is as defined in 2.

So, Lemma 1 provides a closed-form expression—involving only the datamodel
weight vectors $\\{w_{z}\\}$—for the (approximate) feature strength
$s_{\phi}(k)$ of feature $\phi$. We provide a proof of this lemma in Appendix
B.

####  4.1 Poisoned examples as a maximum-sum submatrix

In the previous section, we have shown how we can leverage datamodels to
estimate any given feature’s strength. In this section, we combine Lemma 1 and
Assumptions 1 and 2 (i.e., that the backdoor trigger constitutes the strongest
feature in the dataset) into an algorithm that provably finds backdoor
training examples (provided that Assumptions 1 and 2 indeed hold).

To this end, recall that $n=|S|$ and $p=|\Phi_{p}(S)|$. 1 implies that
$s_{\phi_{p}}(\alpha\cdot p)$ (i.e., the strength of a backdoor feature
$\phi_{p}$) is large. So, guided by Lemma 1, we consider the following
optimization problem:

$\displaystyle\arg\max_{v\in\\{0,1\\}^{n}}h(v)^{\top}\mathbf{W}v\qquad\text{s.t.}\qquad\|v_{i}\|_{1}=p,$
(6)

where $h$ is as defined in Lemma 1. The following lemma (proved in Appendix C)
shows that under 1, the solution to (6) is precisely the indicator vector of
the backdoor trigger feature.

######  Lemma 2.

Suppose 1 holds for some $\delta$ and Lemma 1 holds for some $C$. Then if
$\delta>2pC\varepsilon^{1/2}n^{1/4}$, the unique maximizer of (6) is the
vector $v_{p}=\bm{1}_{\phi_{p}(S)}$, i.e., the indicator of the backdoored
training examples, where $\epsilon$ is as in 2.

Now, the fact that for $v\in\\{0,1\\}^{n}$ we have
$\mathbbm{1}_{n}^{\top}\mathbf{W}v=v^{\top}(\text{diag}(\mathbbm{1}_{n}^{\top}\mathbf{W}))v$
allows us to express (6) as a submatrix-sum maximization problem. In
particular, we have that

$\displaystyle\operatorname*{argmax}_{v\in\\{0,1\\}^{n}:\|v\|_{1}=p}\left(\frac{1}{p}\cdot
v-\frac{1}{n-p}\cdot(\mathbbm{1}_{n}-v)\right)^{\top}\mathbf{W}v$
$\displaystyle=$
$\displaystyle\operatorname*{argmax}_{v\in\\{0,1\\}^{n}:\|v\|_{1}=p}\left(v^{\top}\mathbf{W}-\frac{p}{n}\cdot\mathbbm{1}_{n}^{\top}\mathbf{W}\right)v$
$\displaystyle=$
$\displaystyle\operatorname*{argmax}_{v\in\\{0,1\\}^{n}:\|v\|_{1}=p}v^{\top}\left(\mathbf{W}-\text{diag}\left(\frac{p}{n}\cdot\mathbbm{1}_{n}^{\top}\mathbf{W}\right)\right)v.$
(7)

####  4.2 Detecting backdoored examples

The formulation presented in (6) is difficult to solve directly, for multiple
reasons. First, the optimization problem requires knowledge of the number of
poisoned examples $|\Phi_{p}(S)|$, which is unknown in practice. Second, even
if we did know the number of poisoned examples, the problem is still NP-hard
in general [BSD17]. In fact, even linearizing (6) and using the commercial-
grade mixed-integer linear program solver Gurobi [Gur21] takes several days to
solve (per problem instance) due to the sheer number of optimization
variables.

We thus resort to a different approximation. For each $k$ in a pre-defined set
of “candidate sizes” $K$ for the submatrix in (7), we set $p$ equal to $k$. We
then solve the resulting maximization problem using a greedy local search
algorithm inspired by the Kernighan-Lin heuristic for graph partitioning
[KL70]. That is, starting from a random assignment for $v\in\\{0,1\\}^{n}$,
the algorithm considers all pairs of indices $i,j\in[n]$ such that $v_{i}\neq
v_{j}$, and such that swapping the values of $v_{i}$ and $v_{j}$ would improve
the submatrix sum objective. The algorithm greedily selects the pair that
would most improve the objective and terminates when no such pair exists. We
run this local search algorithm $T=1000$ times for each value of $k$ and
collect the candidate solutions $\\{\bm{v}^{k,l}:k\in K,l\in[T]\\}$.

Now, rather than using any particular one of these solutions, we combine them
to yield a score for each example $z_{i}\in S$. We define this score for the
$i$-th example $z_{i}$ as the weighted sum of the number of times it was
included in the solution of local search, that is,

$s_{i}=\sum_{k\in K}\,\frac{1}{k}\sum_{l=1}^{T}\,\bm{v}^{k,l}_{i}.$ (8)

Intuitively, we expect that backdoored training examples will end up in many
of the greedy local search solutions (due to 1) and thus have a high score
$s_{i}$. We translate the scores (8) into a concrete defense by flagging (and
removing) the examples with the highest score.

###  5 Experiments

Exp. | Attack Type | Poison ratio | Clean Accuracy | Poisoned Accuracy
---|---|---|---|---
1 | Dirty-Label | 1.5% | 86.64 | 19.90
2 | Dirty-Label | 5% | 86.67 | 12.92
3 | Dirty-Label | 1.5% | 86.39 | 49.57
4 | Dirty-Label | 5% | 86.23 | 10.67
5 | Clean-Label | 1.5% | 86.89 | 75.58
6 | Clean-Label | 5% | 87.11 | 41.89
7 | Clean-Label (no adv.) | 5% | 86.94 | 71.68
8 | Clean-Label (no adv.) | 10% | 87.02 | 52.08
Table 1:  A summary of the different backdoor attacks we consider. Clean-Label
(no adv.) is the non-adversarial clean label attack from [TTM19].

In the previous section, we developed an algorithm that provably detects
backdoored examples in a dataset whenever Assumptions 1 and 2 hold. We now
consider several settings777Table 1 provides a summary of the poisoning
setups., and two common types of backdoor attacks: dirty-label attacks [GDG17]
and clean-label attacks [TTM19]. For each setting, we verify whether our
assumptions hold, and then validate the effectiveness of our proposed
detection algorithm.

##### Experimental setup.

In Table 1, we present a summary of our experiments. For all of these
experiments, we use the CIFAR-10 dataset [Kri09], and the ResNet-9
architecture [HZR+15], and compute the datamodels using the framework
presented in [IPE+22]. Specifically, for each experiment and setup, we train a
total of 100,000 models, each on a random subset containing 50%888We train, in
Exp. 2 from Table 1, each model on 30% of the dataset. More details in Section
5.1. of CIFAR-10999The chosen value of $\alpha$ from Assumption 1 is hence
$1/2$., and chosen uniformly at random.

####  5.1 Verifying our assumptions

In Section 3, we presented two assumptions required for our proposed defense
to (provably) work. We now verify whether these assumptions hold in the
experimental settings we consider, then validate the effectiveness of our
detection algorithm.

##### Datamodel accuracy.

Lemma 1 states that datamodels are good approximators of a feature strength
(provided 2 holds). To validate whether this is indeed the case, we estimate
the “ground-truth” feature strength $s_{\phi_{p}}(k)$ of the backdoor triggr
feature $\phi_{p}$ as described in (1) and (2). More precisely, we train
100,000 models on random subsets of the training set, each containing 50% of
the training examples. We then compute how the model outputs change with the
inclusion/exclusion of the backdoored examples. We then compute the model’s
outputs for the backdoored examples as a function of the number of backdoored
training examples. We then estimate the feature strength $s_{\phi}(k)$ as the
rate of change of the model outputs for backdoored examples.

Afterwards, we estimate the feature strength using datamodels, as given by
Equation (5). In particular, we compute the datamodels matrix $\mathbf{W}$,
the indicator vector $h\left(\bm{1}_{\phi_{p}(S)}\right)$ from Lemma 1, and
their product

$h\left(\bm{1}_{\phi_{p}(S)}\right)^{\top}\mathbf{W}\in\mathbb{R}^{|S|}$

Each entry of this product is an estimate of the backdoor feature strength at
every training example. As Figure 4 shows, datamodels are indeed good
approximators of the backdoor trigger feature’s strength.

Figure 4:  Estimating feature strength using datamodels. Each orange (resp.
blue) data point in the scatter plot above represents a poisoned (resp. clean)
training example. The $x$-value of each data point represents the feature
strength estimated using datamodels (see Equation (5)), and the $y$-value
represents the feature strength as estimated using Equation (2). We see a
strong linear correlation between these two quantities for poisoned examples,
which indicates that datamodels provide a good estimate of feature strength.

##### Backdoor trigger as the strongest feature.

Recall that assumption 1 states that the backdoor trigger feature has the
highest feature strength among all the features present in the dataset. To
validate this assumption in our settings, we leverage our approximation of
feature strength using datamodels. Specifically, our result from Section 4
suggest;s that the obtained product should be highly correlated with the
ground-truth backdoor trigger indicator vector $\bm{1}_{\phi_{p}(S)}$. We thus
measure this correlation by computing the area under the ROC curve (AUROC)
between the product $h(\bm{1}_{\phi_{p}(S)})^{\top}\mathbf{W}$ and the
indicator vector $\bm{1}_{\phi_{p}(S)}$. As we can see in Table 2, the AUROC
score is very high in seven out of the eight settings, which suggests that 1
indeed holds in these cases.

Interestingly, we observe that we get a low AUROC in the second experiment
from Table 1 (the one with a very large number of backdoored examples), which
indicates that one of our assumptions does not hold in that case. To
investigate the reason for that, we inspect the backdoor feature strength.
Figure 5 shows that, for subsets of the training set containing 50% of the
training examples, the model output does not change as the number of poisoned
samples increases, i.e., for these subsets, the backdoor feature strength is
essentially 0. Consequently, 1 indeed does not hold. To fix this problem, we
use smaller random subsets, i.e., ones containing 30% of the training
examples, when estimating the datamodels. In this new setting, the backdoor
feature strength is significantly higher, and the AUROC between the poison
indicator vector and the feature strenght product jumps to 99.34%. For the
remainder of the paper, we will use this setup.

Figure 5:  Model output for different number of backdoor training examples. Each orange (resp. blue) line corresponds to a poisoned (resp. clean) example. The $x$-value represents the number of backdoored examples present in the training set, while the $y$-value represents the model output (average margin) at that specific example. The rate of change of the model output represents the feature strength. We observe that for backdoored examples (orange lines) from Exp. 2 (see Table 1), the model output does not change as more training examples are poisoned. Consequently, the backdoor feature strength is 0.  E1 | E2 | E3 | E4 | E5 | E6 | E7 | E8
---|---|---|---|---|---|---|---
99.9 | 60.9 | 98.0 | 97.7 | 99.9 | 99.9 | 97.0 | 98.3
Table 2:  AUROC of the backdoor feature strength and the backdoor examples
indicator vector for our setups from Table 1.

Exp. | No Defense | AC | ISPL | SPECTRE | SS | Ours
---|---|---|---|---|---|---
Clean | Poisoned | Clean | Poisoned | Clean | Poisoned | Clean | Poisoned | Clean | Poisoned | Clean | Poisoned
1 | 86.64 | 19.90 | 86.76 | 19.68 | 86.13 | 86.15 | 86.71 | 20.17 | 85.52 | 30.99 | 85.05 | 85.06
2 | 86.67 | 12.92 | 85.41 | 12.93 | 85.88 | 85.82 | - | - | 85.33 | 13.63 | 83.39 | 83.13
3 | 86.39 | 49.57 | 86.25 | 48.85 | 86.32 | 85.57 | 86.28 | 45.32 | 85.22 | 78.22 | 84.82 | 84.11
4 | 86.23 | 10.67 | 84.75 | 10.82 | 85.86 | 85.18 | - | - | 84.85 | 13.33 | 84.64 | 83.72
5 | 86.89 | 75.58 | 86.73 | 82.83 | 86.04 | 85.89 | 86.82 | 80.65 | 85.67 | 85.41 | 83.82 | 83.72
6 | 87.11 | 41.89 | 86.85 | 51.05 | 86.18 | 86.11 | 86.97 | 51.18 | 85.68 | 85.60 | 84.88 | 84.79
7 | 87.02 | 71.68 | 86.90 | 73.28 | 86.50 | 82.31 | 86.72 | 76.97 | 85.70 | 82.70 | 84.19 | 84.02
8 | 86.94 | 52.08 | 86.81 | 56.78 | 86.04 | 71.27 | 86.63 | 52.27 | 85.87 | 71.93 | 84.81 | 84.66

Table 3:  A summary of the model performances on a “clean” and “poisoned”
validation sets after applying our method, as well as several baselines in the
settings we consider. The high accuracy on both the clean and poisoned
validation sets indicates the effectiveness of our defense against the
considered backdoor attacks.

####  5.2 Evaluating the effectiveness of our backdoor defense

Let us evaluate the effectiveness of our method (see Section 4.2) in defending
against backdoor attacks.

##### Evaluating our score.

As a first step, we measure how well our scores predict the backdoored
examples in our eight settings. Specifically, we compute our scores by running
our local search algorithm from Section 4.2 on the datamodels matrix
$\mathbf{W}$, then aggregating the results from the different runs. Following
that, we check how well these scores correlate with the backdoor examples
indicator vector $\bm{1}_{\phi_{p}(S)}$. As Table 4 shows, there is a high
correlation between these two quantities in all setups (cf. Section
5.1)101010For Exp. 2 from Table 1, we are using the datamodels computed with
$\alpha=30\%$, as described in Section 5.1. This high correlation suggests
that our local search algorithm generates a score that is predictive of the
backdoored examples.

E1 | E2 | E3 | E4 | E5 | E6 | E7 | E8
---|---|---|---|---|---|---|---
94.3 | 92.25 | 74.4 | 80.2 | 93.4 | 93.2 | 91.1 | 95.5
Table 4:  AUROC for our scores (see Section 4.2) and the backdoor indicator
vector for our setups from Table 1.

##### Evaluating the effectiveness of our proposed defense.

Given that our scores are predictive of the backdoor examples indicator
vector, we expect that removing the examples with the highest scores will be
an effective defense against the backdoor attack. To test this claim, for each
of the backdoor attacks settings, we train a model on the backdoored dataset,
and compute the accuracy of this model on (a) the clean validation set, (b)
and on the backdoored validation set111111By adding the trigger to all images
of the clean validation set.. We then remove from the training set the
examples corresponding to the top 10% of the scores121212 We remove 20% in
Exp. 2 from Table 1 since the number of poisoned examples is larger. , train a
new model on the resulting dataset, and then check the performance of this new
model on the clean and the fully-backdoored validation sets. We also compare
our detection algorithm with several baselines, including Inverse Self-Paced
Learning131313We thank the authors for sharing their implementation. (ISPL)
[JSR21], Spectral Signatures141414We re-implement the algorithm presented in
the paper. (SS) [TLM18], SPECTRE151515https://github.com/SewoongLab/spectre-
defense [HKS+21] and Activation Clustering (AC) [CCB+18]. Table 3 shows that
there is no substantial drop in accuracy when evaluating the models trained on
the training set curated using our approach.

###  6 Related Work

Developing backdoor attacks and defenses in the context of deep learning is a
very active area of research [GDG17, TLM18, CCB+18, TTM19, SSP20, Sho+20,
HKS+21, QXM+22, GTX+22, GKV+22] —see e.g. [LJL+22] for a survey. One popular
approach to defending against backdoor attacks revolves around outlier
detection in the latent space of neural networks [TLM18, CCB+18, HKS+21].
However, such defenses inherently fail in defending against adaptive attacks
that leave no trace in the latent space of backdoored models [Sho+20].

Another line of work investigates certified defenses against backdoor attacks
[LF21, WLF22]. To accomplish that, the proposed methods provide certificates
by training separate models on different partitions of the training set, and
dropping the models trained on data containing backdoored examples. This
approach, however, significantly degrades the accuracy of the trained model,
and is only able to certify accuracy when the number of backdoored examples is
very small.

A number of prior works explore the applicability of influence-based methods
as defenses against different attacks in deep learning [KL17]. To the best of
our knowledge, only [LZL+22] discuss using such methods for defending against
backdoor attacks. However, their defense requires knowledge of the attack
parameters that are typically unknown. Closest to our work is that of [JSR21],
who (similar to this work) consider a defense based on model behavior rather
than properties of any latent space.

###  7 Conclusion

In this paper, we presented a new perspective on backdoor attacks.
Specifically, we argue that backdoor triggers are fundamentally
indistinguishable from existing features in the dataset. Consequently, the
task of detecting backdoored training examples becomes equivalent to that of
detecting strong features. Based on this observation, we propose a
primitive—and a corresponding algorithm—for identifying and removing
backdoored examples. Through a wide range of backdoor attacks, we demonstrated
the effectiveness of our approach and its ability to retain high accuracy of
the resulting models.

###  8 Acknowledgments

Work supported in part by the NSF grants CNS-1815221 and DMS-2134108, and Open
Philanthropy. This material is based upon work supported by the Defense
Advanced Research Projects Agency (DARPA) under Contract No. HR001120C0015. We
thank the MIT Supercloud cluster [RKB+18] for providing computational
resources that supported part of this work.

### References

  * [ABC+18] Yossi Adi, Carsten Baum, Moustapha Cisse, Benny Pinkas and Joseph Keshet  “Turning Your Weakness Into a Strength: Watermarking Deep Neural Networks by Backdooring”  In _$\\{$ USENIX$\\}$ Security Symposium_, 2018
  * [BSD17] Vincent Branders, Pierre Schaus and Pierre Dupont  “Mining a Sub-Matrix of Maximal Sum”  In _International Workshop on New Frontiers in Mining Complex Patterns (NFMCP)_ , 2017
  * [CCB+18] Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy and Biplav Srivastava  “Detecting backdoor attacks on deep neural networks by activation clustering”  In _arXiv preprint arXiv:1811.03728_ , 2018
  * [CJC+23] Nicholas Carlini, Matthew Jagielski, Christopher A. Choquette-Choo, Daniel Paleka, Will Pearce, Hyrum Anderson, Andreas Terzis, Kurt Thomas and Florian Tramèr  “Poisoning Web-Scale Training Datasets is Practical”  In _arXiv preprint arXiv:2302.10149_ , 2023
  * [CLL+17] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu and Dawn Song  “Targeted Backdoor Attacks on Deep Learning Systems Using Data Poisoning”  In _arXiv preprint arXiv:1712.05526_ , 2017
  * [DT17] Terrance DeVries and Graham W Taylor  “Improved Regularization of Convolutional Neural Networks with Cutout”  In _arXiv preprint arXiv:1708.04552_ , 2017
  * [Fel19] Vitaly Feldman  “Does Learning Require Memorization? A Short Tale about a Long Tail”  In _Symposium on Theory of Computing (STOC)_ , 2019
  * [GDG17] Tianyu Gu, Brendan Dolan-Gavitt and Siddharth Garg  “Badnets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain”  In _arXiv preprint arXiv:1708.06733_ , 2017
  * [GKV+22] Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan and Or Zamir  “Planting Undetectable Backdoors in Machine Learning Models”  In _arXiv preprint arXiv:2204.06974_ , 2022
  * [GTX+22] Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li and Tom Goldstein  “Dataset security for machine learning: Data poisoning, backdoor attacks, and defenses”  In _IEEE Transactions on Pattern Analysis and Machine Intelligence_ IEEE, 2022
  * [Gur21] Gurobi Optimization, LLC  “Gurobi Optimizer Reference Manual”, 2021  URL: https://www.gurobi.com
  * [HJA20] Jonathan Ho, Ajay Jain and Pieter Abbeel  “Denoising Diffusion Probabilistic Models”  In _Neural Information Processing Systems (NeurIPS)_ , 2020
  * [HKS+21] Jonathan Hayase, Weihao Kong, Raghav Somani and Sewoong Oh  “SPECTRE: defending against backdoor attacks using robust statistics”  In _arXiv preprint arXiv:2104.11315_ , 2021
  * [HLW+22] Kunzhe Huang, Yiming Li, Baoyuan Wu, Zhan Qin and Kui Ren  “Backdoor Defense via Decoupling the Training Process”  In _International Conference on Learning Representations (ICLR)_ , 2022
  * [HRR+11] Frank R Hampel, Elvezio M Ronchetti, Peter J Rousseeuw and Werner A Stahel  “Robust statistics: the approach based on influence functions”  John Wiley & Sons, 2011
  * [HZR+15] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep Residual Learning for Image Recognition”  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2015
  * [IPE+22] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc and Aleksander Madry  “Datamodels: Predicting Predictions from Training Data”  In _International Conference on Machine Learning (ICML)_ , 2022
  * [JCG21] Jinyuan Jia, Xiaoyu Cao and Neil Zhenqiang Gong  “Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks”  In _AAAI_ , 2021
  * [JSR21] Charles Jin, Melinda Sun and Martin Rinard  “Provable Guarantees against Data Poisoning Using Self-Expansion and Compatibility”  In _ArXiv preprint arxiv:2105.03692_ , 2021
  * [KL17] Pang Wei Koh and Percy Liang  “Understanding Black-box Predictions via Influence Functions”  In _International Conference on Machine Learning_ , 2017
  * [KL70] B.. Kernighan and S. Lin  “An efficient heuristic procedure for partitioning graphs”  In _The Bell System Technical Journal_ , 1970
  * [Kri09] Alex Krizhevsky  “Learning Multiple Layers of Features from Tiny Images”  In _Technical report_ , 2009
  * [LF21] Alexander Levine and Soheil Feizi  “Deep Partition Aggregation: Provable Defenses against General Poisoning Attacks”  In _International Conference on Learning Representations_ , 2021
  * [LIE+22] Guillaume Leclerc, Andrew Ilyas, Logan Engstrom, Sung Min Park, Hadi Salman and Aleksander Madry  “ffcv”, https://github.com/libffcv/ffcv/, 2022
  * [LJL+22] Yiming Li, Yong Jiang, Zhifeng Li and Shu-Tao Xia  “Backdoor learning: A survey”  In _IEEE Transactions on Neural Networks and Learning Systems_ IEEE, 2022
  * [LLT+19] Yingqi Liu, Wen-Chuan Lee, Guanhong Tao, Shiqing Ma, Yousra Aafer and Xiangyu Zhang  “ABS: Scanning Neural Networks for Back-Doors by Artificial Brain Stimulation”  In _ACM SIGSAC Conference on Computer and Communications Security_ , 2019
  * [LM19] Gábor Lugosi and Shahar Mendelson  “Sub-Gaussian estimators of the mean of a random vector”  In _The annals of statistics_ 47.2 Institute of Mathematical Statistics, 2019, pp. 783–794
  * [LSI+21] Guillaume Leclerc, Hadi Salman, Andrew Ilyas, Sai Vemprala, Logan Engstrom, Vibhav Vineet, Kai Xiao, Pengchuan Zhang, Shibani Santurkar and Greg Yang  “3DB: A Framework for Debugging Computer Vision Models”  In _arXiv preprint arXiv:2106.03805_ , 2021
  * [LYM22] Tian Yu Liu, Yu Yang and Baharan Mirzasoleiman  “Friendly Noise against Adversarial Noise: A Powerful Defense against Data Poisoning Attacks”  In _arXiv preprint arXiv:2208.10224_ , 2022
  * [LZL+22] Jinkun Lin, Anqi Zhang, Mathias Lecuyer, Jinyang Li, Aurojit Panda and Siddhartha Sen  “Measuring the Effect of Training Data on Deep Learning Predictions via Randomized Experiments”  In _arXiv preprint arXiv:2206.10013_ , 2022
  * [QXM+22] Xiangyu Qi, Tinghao Xie, Saeed Mahloujifar and Prateek Mittal  “Circumventing Backdoor Defenses That Are Based on Latent Separability”  In _arXiv preprint arXiv:2205.13613_ , 2022
  * [RKB+18] Albert Reuther, Jeremy Kepner, Chansup Byun, Siddharth Samsi, William Arcand, David Bestor, Bill Bergeron, Vijay Gadepally, Michael Houle, Matthew Hubbell, Michael Jones, Anna Klein, Lauren Milechin, Julia Mullen, Andrew Prout, Antonio Rosa, Charles Yee and Peter Michaleas  “Interactive supercomputing on 40,000 cores for machine learning and data analysis”  In _2018 IEEE High Performance extreme Computing Conference (HPEC)_ , 2018, pp. 1–6  IEEE
  * [SE19] Yang Song and Stefano Ermon  “Generative Modeling by Estimating Gradients of the Data Distribution”  In _Neural Information Processing Systems (NeurIPS)_ , 2019
  * [SHN+18] Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras and Tom Goldstein  “Poison frogs! targeted clean-label poisoning attacks on neural networks”  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2018
  * [Sho+20] Reza Shokri  “Bypassing backdoor detection algorithms in deep learning”  In _2020 IEEE European Symposium on Security and Privacy (EuroS &P)_, 2020, pp. 175–183  IEEE
  * [SSP20] Aniruddha Saha, Akshayvarun Subramanya and Hamed Pirsiavash  “Hidden trigger backdoor attacks”  In _Proceedings of the AAAI conference on artificial intelligence_ 34.07, 2020, pp. 11957–11965
  * [TLM18] Brandon Tran, Jerry Li and Aleksander Mądry  “Spectral Signatures in Backdoor Attacks”  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2018
  * [TTM19] Alexander Turner, Dimitris Tsipras and Aleksander Madry  “Label-Consistent Backdoor Attacks”, 2019
  * [WLF22] Wenxiao Wang, Alexander Levine and Soheil Feizi  “Improved Certified Defenses against Data Poisoning with (Deterministic) Finite Aggregation”  In _International Conference on Machine Learning_ , 2022
  * [WYS+19] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng and Ben Y Zhao  “Neural cleanse: Identifying and mitigating backdoor attacks in neural networks”  In _Proceedings of 40th IEEE Symposium on Security and Privacy_ , 2019
  * [XHC+20] Chulin Xie, Keli Huang, Pin-Yu Chen and Bo Li  “DBA: Distributed Backdoor Attacks against Federated Learning”  In _International Conference on Learning Representations_ , 2020
  * [YLM22] Yu Yang, Tian Yu Liu and Baharan Mirzasoleiman  “Not All Poisons are Created Equal: Robust Training against Data Poisoning”  In _International Conference on Machine Learning_ , 2022
  * [ZPM+21] Yi Zeng, Won Park, Z. Mao and Ruoxi Jia  “Rethinking the Backdoor Attacks Triggers: A Frequency Perspective”  In _International Conference on Computer Vision (ICCV)_ , 2021

## Appendix

###  Appendix A Model Predictions Formulation Used in Our Paper

In this work, we use the margin function (defined below) as the model output
function $f(z;S)$.

######  Definition 4 (Margin function).

For a dataset $S^{\prime}\subset S$ and a fixed
$z=(x,y)\in\mathcal{X}\times\mathcal{Y}$, the margin function $f(x;S)$ is
defined as

$f(z;S^{\prime}):=\text{the correct-class margin on $z$ of a model trained on
S'},$

where the correct-class margin is the logit of the correct class minus the
largest incorrect logit.

Intuitively, $f(z;S^{\prime})$ maps from an example $z$ and any subset of the
training dataset $S^{\prime}\subset S$ to the correct-class margin on $z$
after training (using any fixed learning algorithm) on $S^{\prime}$.

Here we focus on margins because of their (empirically observed) suitability
for ordinary least squares, as observed in [IPE+22, Appendix C].

###  Appendix B Proof of Lemma 1

See 1

We decompose the proof into two parts. In the first part, we show that we can
approximate the sensitivity $s_{\phi}(k)$ using datamodel weights (Lemma 3).
In the second part, we relate $h$ to the expressions involving datamodel
weights in Lemma 3 (Lemma 4).

######  Lemma 3.

Let $\alpha\in(0,1)$, and $S^{\prime}$ be a subset of $S$, sampled uniformly
at random, such that $|S^{\prime}|=\alpha\cdot|S|$. Let
$a:=\alpha\cdot|\Phi(S)|$. Suppose $\alpha$ is such that $c\leq\alpha\leq 1-c$
for some absolute constant $c\in(0,1)$. Then, there exists a constant $C>0$
(dependending on $c$) such that we have:

$\displaystyle\left|s_{\phi}(a)-\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=a+1\right]+\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=a\right]\right]\right|\leq
C{\varepsilon^{1/2}n^{1/4}}.$ (9)

###### Proof.

Recall that the sensitivity $s_{\phi}(k)$ is defined as:

$\displaystyle s_{\phi}(k):=$ $\displaystyle g_{\phi}(k+1)-g_{\phi}(k)$ (10)
$\displaystyle=$
$\displaystyle\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S},S^{\prime}\not\ni
z}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=k+1\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S},S^{\prime}\not\ni
z}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=k\right]\right]$

For convenience, assume that $a=\alpha\cdot|\Phi(S)|$ is an integer. First, by
triangle inequality, it is enough to show that:

$\begin{split}&\left|\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=a\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=a\right]\right]\right|\leq\frac{1}{2}\cdot
C{\varepsilon^{1/2}n^{1/4}}\end{split}$ (11)

and

$\begin{split}&\left|\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=a+1\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=a+1\right]\right]\right|\leq\frac{1}{2}\cdot
C{\varepsilon^{1/2}n^{1/4}}.\end{split}$ (12)

We address Equation 11, and the bound for Equation 12 follows analogously.

To address Equation 11, we will show a stronger (per-example) statement:

$\begin{split}&\left|\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=a\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=a\right]\right|\leq\frac{1}{2}\cdot
C{\varepsilon^{1/2}n^{1/4}}\end{split}$ (13)

Trivially, this implies that the expectation over $z$ is also bounded from
above by $\frac{1}{2}\cdot C{\varepsilon^{1/2}n^{1/4}}$. To show that Equation
13 holds, we first compute the probability of a random subset $S^{\prime}$
containing $a$ poisoned samples, and then show an upper bound for Equation 11
leveraging the derived probability by using the definition of conditional
expectation.

By directly counting, we have that

$\displaystyle\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=a\right]}=\frac{{\,|\Phi(S)|\choose
a}\binom{\,|S|-|\Phi(S)|}{\alpha\cdot|S|-a}}{\binom{\,|S|}{\alpha\cdot|S|}}.$

To ease notation, let $n:=|S|$ and $p:=|\Phi(S)|$, thus $a=\alpha p$.
Rewriting, we have

$\displaystyle\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=\alpha
p\right]}=\frac{\binom{p}{\alpha
p}\binom{\,n-p}{\alpha(n-p)}}{\binom{\,n}{\alpha n}}.$

Next,

$\displaystyle\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=\alpha
p+1\right]}=\frac{{p\choose\alpha
p+1}{n-p\choose\alpha(n-p)-1}}{{n\choose\alpha n}}$
$\displaystyle=\left(\frac{p(1-\alpha)}{\alpha
p+1}\cdot\frac{\alpha(n-p)}{(1-\alpha)(n-p)+1}\right)\cdot\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=\alpha
p\right]}$

We first show that the ratio of the two probabilities is bounded by a
constant, i.e.,

$\displaystyle\frac{p(1-\alpha)}{\alpha
p+1}\cdot\frac{\alpha(n-p)}{(1-\alpha)(n-p)+1}$
$\displaystyle=\frac{\alpha}{\alpha+\frac{1}{p}}\cdot\frac{1-\alpha}{1-\alpha+\frac{1}{n-p}}$
$\displaystyle\geq\frac{\alpha}{\alpha+\alpha}\cdot\frac{1-\alpha}{2-\alpha}\geq\frac{1}{2}\cdot\frac{c}{2-c}$

where we used that $1\leq\alpha p$ and $c\leq\alpha\leq 1-c$. Thus

$\displaystyle\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=\alpha
p+1\right]}\geq\frac{c}{2(2-c)}\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=\alpha
p\right]}.$

Now we proceed with bounding
$\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=\alpha
p\right]}$. Using Stirling’s approximation, we have

$\displaystyle\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[|\Phi(S^{\prime})|=\alpha
p\right]}\asymp\sqrt{\frac{n}{p(n-p)}\frac{1}{\alpha(1-\alpha)}}\geq\frac{2}{C^{2}\cdot\sqrt{n}}$

for some constant $C>0$. Now from the triangle inequality, Jensen’s inequality
and Markov’s inequality we have that for sufficiently large $n$

$\displaystyle\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p\right]$
$\displaystyle\leq\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[\left|f(z;S^{\prime})-w_{z}^{\top}\bm{1}_{S^{\prime}}\right|\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p\right]$
$\displaystyle\leq\sqrt{\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[\left(f(z;S^{\prime})-w_{z}^{\top}\bm{1}_{S^{\prime}}\right)^{2}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p\right]}$ $\displaystyle\leq\frac{1}{2}C{\varepsilon^{1/2}n^{1/4}}.$

The case for Equation 12 is analogous. ∎

Next, we show that $w_{z}^{\top}h(\bm{1}_{\Phi(S)})$ corresponds to the
desired difference of conditional expectations. In this proof, we let
$h_{\phi}=h(\bm{1}_{\Phi(S)})$ for brevity.

######  Lemma 4.

We have for every $x\in S$ that

$\displaystyle\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|+1\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|\right]\right]=\mathbb{E}_{z\sim\Phi(S)}w_{z}^{\top}h_{\phi}.$

###### Proof.

Again, let us consider the case for a single example $z$, and let
$n=|S|,p=|\Phi(S)|$. Then we can write

$\displaystyle\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p\right]$
$\displaystyle=\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[\sum_{z\in
S}\bm{1}_{z\in S^{\prime}}w_{xz}\bigg{|}\,|\Phi(S^{\prime})|=\alpha p\right]$
$\displaystyle=\sum_{z\in
S}\mathbb{P}_{S^{\prime}\sim\mathcal{D}_{S}}{\left[z\in
S^{\prime}\bigg{|}\,|\Phi(S^{\prime})|=\alpha p\right]}\cdot w_{xz}.$

There are a total of

$\displaystyle{p\choose\alpha p}{n-p\choose\alpha(n-p)}$

sets satisfying $|\Phi(S^{\prime})|=\alpha p$. Among these, given that the
sample $z$ contains the feature $\phi$, i.e., $\phi(z)=1$, there are

$\displaystyle{p-1\choose\alpha p-1}{n-p\choose\alpha(n-p)}$

random subsets containing $z$. So for all $z$ containing $\phi$ we have

$\displaystyle\mathbb{P}{\left[z\in
S^{\prime}\bigg{|}\,\phi(z)=1,|\Phi(S^{\prime})|=\alpha p\right]}=\frac{\alpha
p}{p}.$

Similarly, for all samples $z$ that do not contain $\phi$ ,i.e, $\phi(z)=0$,
we have that

$\displaystyle\mathbb{P}{\left[z\in
S^{\prime}\bigg{|}\,\phi(z)=0,|\Phi(S^{\prime})|=\alpha
p\right]}=\frac{\alpha(n-p)}{n-p}.$

Thus, overall

$\displaystyle\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p\right]$ $\displaystyle=\frac{\alpha
p}{p}w_{z}^{\top}\bm{1}_{\phi(S)}+\frac{\alpha(n-p)}{n-p}w_{z}^{\top}(1-\bm{1}_{\phi(S)})$
$\displaystyle=w_{z}^{\top}\left(\frac{\alpha
p}{p}\bm{1}_{\phi(S)}+\frac{\alpha(n-p)}{n-p}(1-\bm{1}_{\phi(S)})\right)$
$\displaystyle=w_{z}^{\top}\left(\frac{\alpha
p}{p}\bm{1}_{\phi(S)}+\frac{\alpha(n-p)}{n-p}(1-\bm{1}_{\phi(S)})\right)$

Analogously,

$\displaystyle\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p+1\right]$ $\displaystyle=\frac{\alpha
p+1}{p}w_{z}^{\top}\bm{1}_{\phi(S)}+\frac{\alpha(n-p)-1}{n-p}w_{z}^{\top}(1-\bm{1}_{\phi(S)})$
$\displaystyle=w_{z}^{\top}\left(\frac{\alpha
p+1}{p}\bm{1}_{\phi(S)}+\frac{\alpha(n-p)-1}{n-p}(1-\bm{1}_{\phi(S)})\right)$
$\displaystyle=w_{z}^{\top}\left(\frac{\alpha
p+1}{p}\bm{1}_{\phi(S)}+\frac{\alpha(n-p)-1}{n-p}(1-\bm{1}_{\phi(S)})\right)$

We then subtract the two terms to get:

$\displaystyle\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p+1\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha
p\right]$
$\displaystyle=w_{z}^{\top}\left(\frac{1}{p}\bm{1}_{\phi(S)}-\frac{1}{n-p}(1-\bm{1}_{\phi(S)})\right)$
$\displaystyle=w_{z}^{\top}h(\bm{1}_{\phi(S)})$

Finally, we get the desired results over all examples $z\in\Phi(S)$ by
directly averaging. ∎

###### Proof of Lemma 1.

The proof of Lemma 1 follows by combining the results of Lemma 3 and Lemma 4:

$\displaystyle\left|s_{\phi}(\alpha\cdot|\Phi(S)|)-\mathbb{E}_{z\sim\Phi(S)}w_{z}^{\top}h(\bm{1}_{\phi(S)})\right|$
$\displaystyle=\left|s_{\phi}(\alpha\cdot|\Phi(S)|)-\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|+1\right]+\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|\right]\right]\right|$
$\displaystyle\leq\left|\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|+1\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|+1\right]\right]\right|$
$\displaystyle+\left|\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|\right]-\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[w_{z}^{\top}\bm{1}_{S^{\prime}}\,\bigg{|}\,|\Phi(S^{\prime})|=\alpha\cdot|\Phi(S)|\right]\right]\right|$
$\displaystyle\leq 2\cdot\frac{1}{2}\cdot
C{\varepsilon^{1/2}n^{1/4}}=C{\varepsilon^{1/2}n^{1/4}}$

∎

###  Appendix C Proof of Lemma 2

See 2

###### Proof.

The result follows directly from 1 and Lemma 1. In particular, let $\phi_{v}$
be a feature whose corresponding support $\Phi_{v}(S)$ is of size $p$.

$\displaystyle h(v)^{\top}\mathbf{W}v$ $\displaystyle=\left(\frac{1}{n}\cdot
v-\frac{1}{n-p}\cdot(\mathbbm{1}_{n}-v)\right)^{\top}\mathbf{W}v$
$\displaystyle=\begin{bmatrix}h_{v}^{\top}w_{z_{1}}&h_{v}^{\top}w_{z_{2}}&\ldots&h_{v}^{\top}w_{z_{n}}\end{bmatrix}\cdot
v$ $\displaystyle=\sum_{z\in\Phi_{v}(S)}h_{v}^{\top}w_{z}.$

First, from Lemma 1, we have that:

$\sum_{z\in\Phi_{v}(S)}h_{v}^{\top}w_{z}\leq\sum_{z\in\Phi_{v}(S)}s_{v}(z,\alpha\|v\|_{1})+pC^{*}\varepsilon^{1/2}n^{1/4}$

Now let $v_{p}$ be the indicator vector for the poisoned examples. We
similarly have from Lemma 1:

$\sum_{z\in\Phi_{p}(S)}h_{p}^{\top}w_{z}\geq\sum_{z\in\Phi_{p}(S)}s_{p}(z,\alpha\|v\|_{1})-pC^{*}\varepsilon^{1/2}n^{1/4}$

Thus for any $v\neq v_{p}$ we have that

$\displaystyle h_{p}^{\top}\mathbf{W}v_{p}-h_{v}^{\top}\mathbf{W}v$
$\displaystyle=\sum_{z\in\Phi_{p}(S)}h_{p}^{\top}w_{z}-\sum_{z\in\Phi_{v}(S)}h_{v}^{\top}w_{z}$
$\displaystyle\geq\sum_{z\in\Phi_{{}_{p}}(S)}s_{v_{p}}(z,\alpha\|v_{p}\|_{1})-\sum_{z\in\Phi_{v}(S)}s_{v}(z,\alpha\|v\|_{1})-2pC^{*}\varepsilon^{1/2}n^{1/4}$

We now use 1 that states:

$\sum_{z\in\Phi_{p}(S)}s_{\phi_{p}}\left(z,\alpha\cdot
p\right)-\sum_{z\in\Phi(S)}s_{\phi}(z,\alpha\cdot p)\geq\delta^{*}$

By combining these two inequalities, we obtain:

$\displaystyle h_{p}^{\top}\mathbf{W}v_{p}-h_{v}^{\top}\mathbf{W}v$
$\displaystyle=\sum_{z\in\Phi_{p}(S)}h_{p}^{\top}w_{z}-\sum_{z\in\Phi_{v}(S)}h_{v}^{\top}w_{z}$
$\displaystyle\geq\sum_{z\in\Phi_{{}_{p}}(S)}s_{v_{p}}(z,\alpha\|v_{p}\|_{1})-\sum_{z\in\Phi_{v}(S)}s_{v}(z,\alpha\|v\|_{1})-2pC^{*}\varepsilon^{1/2}n^{1/4}$
$\displaystyle\geq\delta^{*}-2pC^{*}\varepsilon^{1/2}n^{1/4}$

This concludes the proof that the solution of the optimization program in
Equation 6 is the poison indicator vector $v_{p}$, as long as
$\delta^{*}>2pC^{*}\varepsilon^{1/2}n^{1/4}$.

∎

###  Appendix D Experimental Setup

Figure 6: We execute the poisoning attacks with three types of triggers: (a)
one black pixel on top left corner (first two images), (b) 3x3 black square on
top left corner (third and fourth images), and (c) 3-way triggers adapted from
[XHC+20] (last four images).

####  D.1 Backdoor Attacks

##### Dirty-Label Backdoor Attacks.

The most prominent type of backdoor attacks is a dirty-label attack [GDG17].
During a dirty-label attack, the adversary inserts a trigger into a subset of
the training set, then flips the label of the poisoned samples to a particular
target class $y_{b}$. We mount four different dirty-label attacks, by
considering two different triggers, and two different levels of poisoning (cf.
Exp. 1 to 4 in Table 1).

##### Clean-Label Backdoor Attacks.

A more challenging attack is the clean-label attack [SHN+18, TTM19]161616We
evaluate the clean-label attack as presented in [TTM19] where the adversary
avoids changing the label of the poisoned samples. To mount a successful
clean-label attack, the adversary poisons samples from the target class only,
hoping to create a strong correlation between the target class and the
trigger.

We perform two types of clean-label attacks. During the first type (Exp. 5 and
6 from Table 1), we perturb the image with an adversarial example before
inserting the trigger, as presented in [TTM19]. During the second type of
clean-label attacks (Exp. 7 and 8 from Table 1), we avoid adding the
adversarial example, however, we poison more samples to have an effective
attack.

##### Trigger.

We conduct our experiments with two types of triggers. The first type is a
fixed pattern inserted in the top left corner of the image. The trigger is
unchanged between train and test time. This type of trigger has been used in
multiple works [GDG17, TTM19]. The other type of trigger is an m-way trigger,
with m=3 [XHC+20]. During training, one of three triggers is chosen at random
for each image to be poisoned, and then the trigger is inserted into one of
three locations in the image. At test time, all three triggers are inserted at
the corresponding positions to reinforce the signal. We display in Figure 6
the triggers used to poison the dataset.

####  D.2 Training Setup

##### Training CIFAR models.

In this paper, we train a large number of models on different subsets of
CIFAR-10 in order to compute the datamodels. To this end, we use the ResNet-9
architecture
[HZR+15]171717https://github.com/wbaek/torchskeleton/blob/master/bin/dawnbench/cifar10.py.
This smaller version of ResNets was optimized for fast training.

##### Training details.

We fix the training procedure for all our models. We show the hyperparameter
details in Table 5181818Our implementation and configuration files will be
available in our code.. One augmentation was used for dirty-label attacks
(Cutout [DT17]) to improve the performance of the model on CIFAR10. Similar to
[TTM19], we do not use any data augmentation when performing clean-label
attacks.

Optimizer | Epochs | Batch Size | Peak LR | Cyclic LR Peak Epoch | Momentum | Weight Decay
---|---|---|---|---|---|---
SGD | 24 | 1,024 | 0 | 5 | 0.9 | 4e-5
Table 5: Hyperparameters used to train ResNet-9 on CIFAR10.

##### Performance.

In order to train a large number of models, we use the FFCV library for
efficient data-loading [LIE+22]. The speedup from using FFCV allows us to
train a model to convergence in $\sim$40 seconds, and 100k models for each
experiment using 16 V100 in roughly 1 day191919We train 3 models in parallel
on every V100..

##### Computing datamodels.

We adopt the framework presented in [IPE+22] to compute the datamodels of each
experiment. Specifically, we train 100k models on different subsets containing
50% of the training set chosen at random. We then compute the datamodels as
described in [IPE+22].

##### Local Search.

We approximate the solution of the problem outlined in (6) using a local
search heuristic presented in [KL70]. We iterate over ten sizes for the poison
mask: {10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120}. For each size, we
collect 1,000 different solutions by starting from different initialization of
the solution.

####  D.3 Estimating Theoretical Quantities

Recall the average margin definition presented in (1). In particular:

$g_{\phi}(k)=\mathbb{E}_{z\sim\Phi(S)}\left[\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\bigg{|}|\Phi(S^{\prime})|=k,z\not\in
S^{\prime}\right]\right]$ (14)

where $S^{\prime}$ is a subset of the training set, $f(z;S^{\prime})$ is the
margin of the model on example $z$ when trained on the dataset $S^{\prime}$,
$\Phi(S^{\prime})$ is the subset of the set $S^{\prime}$ containing the
poisoned feature, and $k$ is the number of poisoned samples. Estimating the
average margins requires training a large number of models on different
subsets, and measure–for every sample $z$ and every number of poisoned samples
$k$–the margins of the trained model.

For the purpose of this paper, we leverage the datamodels computation
framework to estimate these averages. In particular, to compute the datamodels
weights, we train a large number of models on different subsets
$S_{1},S_{2},\ldots,S_{T}$ of the training set $S$202020We refer the reader to
[IPE+22] for more details.. For every subset $S_{i}$, we record the number of
poisoned samples in the subset, then we estimate the average margin by
averaging the margins over the different subsets that contain $k$ poisoned
samples.

$N_{\phi}(z,k)=\sum_{i=1}^{T}\bm{1}_{\left(|\Phi(S_{i})|=k\right)\,\land\,\left(z\notin
S_{i}\right)}$ (15a)

$\mathbb{E}_{S^{\prime}\sim\mathcal{D}_{S}}\left[f(z;S^{\prime})\bigg{|}|\Phi(S^{\prime})|=k,z\not\in
S^{\prime}\right]\approx\frac{1}{N_{\phi}(k)}\sum_{i=1}^{T}f(z;S_{i})\cdot\bm{1}_{\left(|\Phi(S_{i})|=k\right)\,\land\,\left(z\notin
S_{i}\right)}$ (15b)

$g_{\phi}(k)\approx\frac{1}{|\Phi(S)|}\sum_{z\in\Phi(S)}\frac{1}{N_{\phi}(z,k)}\sum_{i=1}^{T}f(z;S_{i})\cdot\bm{1}_{\left(|\Phi(S_{i})|=k\right)\,\land\,\left(z\notin
S_{i}\right)}$ (15c)

By a training 100k models on different subsets of the dataset, we obtain
reasonable estimates of the marginal effects for every sample $z=(x,y)$.

###  Appendix E Omitted Plots

####  E.1 Average Margin Plots

In this section, we show for all the experiments the plots of the average
margin for clean and poisoned samples as a function of the number of poisoned
samples in the dataset (cf. Fig. 3 in the main paper).

Figure 7: We plot for all the experiments the average margin for five clean
samples (left) and five poisoned samples (right) as the number of poisoned
samples in the training set increases. We observe that the average margin for
clean samples (without the trigger) is constant when poisoning more samples in
the dataset. In contrast, the average margin for poisoned samples (with the
trigger) increases when the number of poisoned samples increases in the
dataset, confirming our assumptions.

####  E.2 Estimated Sensitivities Plots

In this section, we show for all the experiments the plots of the estimated
sensitivities, and the approximation we obtain using datamodels (cf. Fig. 4 in
the main paper).

Figure 8: We plot for all the experiments the estimated marginal sensitivities
and the approximation with datamodels presented in Equation 5. We observe for
poisoned samples (in red) a good linear correlation between the sensitivities
and the datamodels’ approximation. Additionally, we observe no noticeable
correlation for clean samples (in green).

####  E.3 Distribution of Datamodels Values

In this section, we plot for each experiment the distribution of the
datamodels weights for all experiments. In particular, recall that the
datamodels weight $w_{x}[i]$ represents the influence of the training sample
$x_{i}$ on the sample $x$. We show below the distribution of the effect of 1)
poisoned samples on poisoned samples, 2) the poisoned samples on the clean
samples and 4) the clean samples on the clean samples.

Figure 9: We plot the distribution of the datamodels weights for all the
experiments. We clearly see that the effect of poisoned samples on other
poisoned samples is generally higher than the effect of poisoned samples on
clean samples, and than clean samples on each other.

####  E.4 Attack Success Rate (ASR)

In the main paper, we presented our results by measuring the accuracy of a
model on a clean and a poisoned validation sets. Another relevant metric is
the Attack Success Rate (ASR) which measures the probability that the model
predicts the target class after inserting the trigger into an image. As we can
see in Table 6, our defense leads to a low ASR in seven out of eight setups.

Table 6: We compare our method against multiple baselines in a wide range of experiments. We observe that our algorithm leads to a low ASR in seven out of eight experiments. Refer to Table 1 for the full experiments parameters. Exp. | No Defense | AC | ISPL | SPECTRE | SS | Ours
---|---|---|---|---|---|---
1 | 87.94 | 88.26 | 0.70 | 87.67 | 73.78 | 0.81
2 | 96.38 | 96.32 | 0.67 | - | 95.40 | 1.44
3 | 50.49 | 51.33 | 0.58 | 55.68 | 10.44 | 1.18
4 | 99.21 | 99.02 | 0.75 | - | 95.85 | 2.30
5 | 15.66 | 5.35 | 0.71 | 7.66 | 0.80 | 0.92
6 | 58.57 | 45.44 | 0.66 | 46.78 | 0.67 | 0.77
7 | 26.09 | 23.64 | 9.90 | 18.48 | 9.17 | 3.56
8 | 50.62 | 44.82 | 26.07 | 44.14 | 24.72 | 3.42


# Control of the local photonic density of states above magneto-optical
metamaterials

Philippe Ben-Abdallah<EMAIL_ADDRESS>Laboratoire Charles Fabry, UMR
8501, Institut d’Optique, CNRS, Université Paris-Saclay, 2 Avenue Augustin
Fresnel, 91127 Palaiseau Cedex, France

(August 28, 2024)

###### Abstract

The local density of states (LDOS) of electromagnetic field drives many basic
processes associated to light-matter interaction such as the thermal emission
of object, the spontaneous emission of quantum systems or the fluctuation-
induced electromagnetic forces on molecules. Here, we study the LDOS in the
close vincinity of magneto-optical metamaterials under the action of an
external magnetic field and demonstrate that it can be efficiently changed
over a broad or narrow spectral range simply by changing the spatial
orientation or the magnitude of this field. This result paves the way for an
active control of the photonic density of states at deep-subwavelength scale.

###### pacs:

44.05.+e, 12.20.-m, 44.40.+a, 78.67.-n

Tailoring the photonic density of states in the environnement of a textured
solid at subwavelength scale is of prime importance to control the thermal
emission of solids, the spontaneous emission and the decay rate (fluorescence)
of quantum emitters placed in the neighborhood of these structures. This
tuning can also be used to modify the force mediated by the vacuum
fluctuations on neutral objects such as atoms or molecules. Since the pioneer
work of Purcell Purcell  on the modification of the spontaneous emission of an
object by changing its surrounding environnement many strategies have been
proposed to sculpt the local density of states (LDOS) at a length scale
smaller than the wavelength of electromagnetic field. Hence, nanophotonic
structures such as photonic crystals Yablonovitch ; John , surface gratings
Hesketh , two dimensional systems Koppens ; Messina  or complex nanostructures
Viarbitskaya ; Girard  were used to efficiently enhance or inhibit the
spontaneous emission Lodahl ; Birowosuto  and the decay rates of molecules
Drexhage ; Chance . In this Letter we explore the possibility to tune the
photonic states in the close vicinity of non-reciprocal metamaterials made
with magneto-optical materials using an external magnetic field and show that
the LDOS can be efficiently controled simply by changing the spatial
orientation or the magnitude of this field.

Figure 1:  Sketch of a non-reciprocal metamaterial made with magneto-optical
nanostructures of permittivity $\bar{\bar{\boldsymbol{\varepsilon}}}_{j}$
deposited on an isotropic substrate of permittivity $\varepsilon_{sub}$. The
structure is assumed at equilibrium at temperature $T$ with its surrounding
environement and it is submitted to a uniform external magnetic field
$\mathbb{H_{ext}}$ in an arbitrary angular orientation.

To start, let us consider a non reciprocal metamaterial made with a network of
magneto-optical nanostructures of permittivity
$\bar{\bar{\boldsymbol{\varepsilon}}}_{i}$, deposited on an isotropic
substrate of permittivivity $\varepsilon_{sub}$ as sketched on Fig.1.

Figure 2:  LDOS of electromagnetic field at $z=3R$ in vacuum above a InSb
particle of radius $R=50\>nm$ placed on a substrate for an external magnetic
field $\mathbf{H_{ext}}$ (magnitude $H_{ext}=5T$) oriented along the
$\mathbf{x}$ and $\mathbf{z}$ axis. The substrate is a semi-infinite germanium
sample ($\varepsilon_{sub}=16$). The system is at equilibrium at temperature
$T=300\,K$. The LDOS is normalized by the LDOS
$\rho_{vac}=\frac{\omega^{2}}{\pi^{2}c^{3}}$ in vacuum.

We assume this system is at equilibrium at temperature $T$ with its
surrounding environment and it is uniformly shined by an external magnetic
field $\mathbb{H_{ext}}$ in an arbitrary direction. When $\mathbb{H_{ext}}$ is
parallel to the normal $\mathbb{z}$ of the subrate, the permittivity tensor
associated to each magneto-optical nanostructure takes the form Moncada

$\bar{\bar{\boldsymbol{\varepsilon}}}_{j}(H_{ext})=\left(\begin{array}[]{ccc}\varepsilon_{aj}&-i\varepsilon_{bj}&0\\\
i\varepsilon_{bj}&\varepsilon_{aj}&0\\\ 0&0&\varepsilon_{cj}\\\
\end{array}\right),$ (1)

where $\varepsilon_{aj}$, $\varepsilon_{bj}$ and $\varepsilon_{cj}$ generally
depends on the magnitude $H_{ext}$ of magnetic field. When the spatial
orientation of $\mathbb{H_{ext}}$ is changed with respect to
$\parallel\mathbb{x}$ by rotations in the canonical basis
$(\mathbb{x},\mathbb{y},\mathbb{z})$ as illustrated in Fig.1, the permittivity
tensor associated to each nanostructure is readily derived from expression (1)
by simple composition with the corresponding rotation matrices.

Figure 3:  LDOS of electromagnetic field at $z=3R$ in vacuum above a InSb
particle of radius $R=50\>nm$ placed in the center of a network made six gold
nanoparticles of same radius regularly arranged (a) on an ellipse with half
major axe $a=5R$ along the $\mathbf{x}$ axis and the half minor axe $b=1.5R$.
(b) LDOS for an external magnetic field $\mathbf{H_{ext}}$ (magnitude
$H_{ext}=5T$) along the $\mathbf{x}$ and $\mathbf{y}$ axis. The substrate is a
semi-infinite germanium sample.

The LDOS $\rho(\mathbb{r},\omega)$ of electromagnetic field at a given point
$\mathbb{r}=(x,y,z)$ and frequency $\omega$ can be calculated from the density
of energy of electromagnetic field

$u(\mathbb{r},\omega)=\epsilon_{0}<\mid\mathbb{E}(\mathbb{r},\omega)\mid^{2}>+\mu_{0}<\mid\mathbb{H}(\mathbb{r},\omega)\mid^{2}>,$
(2)

associated to the average value of electric field $\mathbb{E}$ and magnetic
field $\mathbb{H}$ and using the relation

$u(\mathbb{r},\omega)=\rho(\mathbb{r},\omega)\Theta(\omega,T),$ (3)

between this density and the LDOS. Here,
$\Theta(T,\omega)={\hbar\omega}/[{e^{\frac{\hbar\omega}{k_{B}T}}-1}]$ denotes
the mean energy of a harmonic oscillator at temperature $T$ of system. When
the size of nanostructures is much smaller than the thermal wavelength
$\lambda_{th}=\hbar c/k_{B}T$ and the separation distance between these
nanostructures is sufficiently large they behaves as a simple dipoles
pbaPRB2008 ; Rubi ; Becerril . The electric field can be related to the
dipolar moments $\mathbb{p_{i}}$ of nanostructures as followed

$\mathbf{E}(\mathbb{r})=\omega^{2}\mu_{0}\underset{i=1}{\overset{N}{\sum}}\mathscr{G}^{EE}(\mathbb{r},\mathbb{r_{i}})\mathbf{p}_{i},$
(4)

with $\mu_{0}$ the vacuum permeability and
$\mathscr{G}^{EE}(\mathbb{r},\mathbb{r^{\prime}})$ is the dyadic Green tensor
between the point $\mathbb{r}$ and $\mathbb{r^{\prime}}$ inside the set of N
nanostructures. On the other hand each dipolar moment can be decomposed into
the form

$\mathbf{p}_{i}=\mathbf{p}_{i}^{fluc}+\mathbf{p}_{i}^{ind}$ (5)

where the first term of rhs is its fluctuating part while the second term is
the part induced by all others dipolar and it reads

$\mathbf{p}_{i}^{ind}=k_{0}^{2}\bar{\bar{\boldsymbol{\alpha}}}_{i}\underset{j\neq
i}{\sum}\mathscr{G}^{EE}(\mathbb{r_{i}},\mathbb{r_{j}})\mathbf{p}_{j}$ (6)

$\bar{\bar{\boldsymbol{\alpha}}}_{i}$ being the nanostructure polarizability,
$k_{0}=\frac{\omega}{c}$ the wavenumber in vacuum and $\varepsilon_{0}$ is the
vacuum permittivity. Inserting expression (6) into relation (5) it immediately
follows the relation beween de dipolar moments and their fluctuating part

$\mathbf{p}_{i}=\underset{j=1}{\overset{N}{\sum}}\mathds{T}_{EE,ij}\mathbf{p}_{j}^{fluc}$
(7)

with

$\mathds{T}_{EE,ij}=\delta_{ij}\mathds{1}-(1-\delta_{ij})k_{0}^{2}\bar{\bar{\boldsymbol{\alpha}}}_{i}\mathscr{G}^{EE}(\mathbb{r_{i}},\mathbb{r_{j}}).$
(8)

It follows that the local electric fied can be written in term of fluctuating
dipolar moments as pbaPRL2011

$\mathbf{E}(\mathbb{r})=\omega^{2}\mu_{0}\underset{j=1}{\overset{N}{\sum}}\mathds{G}^{EE}(\mathbb{r},\mathbb{r_{j}})\mathbf{p}_{j}^{fluc},$
(9)

where the full electric-electric Green tensor takes the form

$\mathds{G}^{EE}(\mathbb{r},\mathbb{r_{j}})=\underset{i=1}{\overset{N}{\sum}}\mathscr{G}^{EE}(\mathbb{r},\mathbb{r_{i}})\mathds{T}_{EE,ij}^{-1}.$
(10)

For an enemble of dipoles in free space the propagator reads

$\begin{split}\mathscr{G}^{EE}(\mathbb{r^{\prime}},\mathbb{r^{\prime\prime}})\equiv\mathscr{G}_{0}^{EE}(\mathbb{r^{\prime}},\mathbb{r^{\prime\prime}})=\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\\\
\frac{\exp(ik_{0}r)}{4\pi
r}\left[\left(1+\frac{ik_{0}r-1}{k_{0}^{2}r^{2}}\right)\mathds{1}+\frac{3-3ik_{0}r-k_{0}^{2}r^{2}}{k_{0}^{2}r^{2}}\widehat{\mathbf{r}}\otimes\widehat{\mathbf{r}}\right],\end{split}$
(11)

where $\widehat{\mathbf{r}}\equiv\mathbf{\mathbb{r}}/r$,
$\mathbf{r}=\mathbb{r^{\prime}}-\mathbb{r^{\prime\prime}}$ and
$r=\mid\mathbf{r}\mid$ and $\mathds{1}$ stands for the unit dyadic tensor.
When the dipoles are located in vacuum above a solid material the propagator
reads

$\mathscr{G}^{EE}(\mathbb{r^{\prime}},\mathbb{r^{\prime\prime}})\equiv\mathscr{G}_{0}^{EE}(\mathbb{r^{\prime}},\mathbb{r^{\prime\prime}})+\mathscr{G}^{EE,sc}(\mathbb{r^{\prime}},\mathbb{r^{\prime\prime}}),$
(12)

where the second term of rhs describe the scattering by the interface between
the vacuum and material. This scattering term can be written as an integral
with respect to the modulus $\kappa$ of the modulus of the parallel component
$\mathbb{\kappa}=(ky,kz)$ of wavevector (i.e. parallel to the $y-z$ plane) as
SupplMat

$\begin{split}\mathscr{G}^{EE,sc}(\mathbb{r^{\prime}},\mathbb{r^{\prime\prime}})=\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\\\
\int_{0}^{\infty}\frac{d\kappa}{2\pi}\kappa\frac{i}{2k_{x}}exp(ik_{x}\mid
x+x^{\prime}\mid)[r^{s}\mathds{S}_{EE}+r^{p}\mathds{P}_{EE}],\end{split}$ (13)

where $k_{x}=\sqrt{k_{0}^{2}-\kappa^{2}}$ is the normal component of the
wavevector in vacuum while $r^{s}$ and $r^{p}$ are the ordinary Fresnel
coefficients of the interface associated to waves in polarization $s$ and $p$,
respectively. The scattering matrix $\mathds{S}$ and $\mathds{P}$ in (13) can
be readily calculated using the Sipe formalism Sipe . As the magnetic field is
concerned, it can be straighforwardly deduced from expression (9) using the
Faraday relation

$\mathbf{H}=\frac{i}{\omega\mu_{0}}\nabla\times\mathbf{E}.$ (14)

It follows that the correlation functions of electric and magnetic fields
reads

$\begin{split}<\mid\mathbb{E}(\mathbb{r},\omega)\mid^{2}>=\omega^{4}\mu_{0}^{2}\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\\\
\times\underset{i,j}{\sum}\underset{l,k,n}{\sum}\mathds{G}^{EE}_{lk}(\mathbb{r},\mathbb{r_{i}})\mathds{G}^{EE*}_{ln}(\mathbb{r},\mathbb{r_{j}})<p^{f}_{i,k}p^{f*}_{j,n}>,\end{split}$
(15)
$\begin{split}<\mid\mathbb{H}(\mathbb{r},\omega)\mid^{2}>=-\omega^{2}\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\>\\\
\times\underset{i,j}{\sum}\underset{l,k,n}{\sum}\mathds{G}^{HE}_{lk}(\mathbb{r},\mathbb{r_{i}})\mathds{G}^{HE*}_{ln}(\mathbb{r},\mathbb{r_{j}})<p^{f}_{i,k}p^{f*}_{j,n}>,\end{split}$
(16)

where $\mathds{G}^{AB}_{lk}$ denotes the $lk$ component of Green tensor and
$p^{f}_{i,k}$ is the $k^{th}$ component of $i^{th}$ fluctuating dipole. The
correlations functions of dipolar moments can be calculated using the
fluctuation dissipation theorem Callen

$\langle
p^{f}_{i,l}p_{j,n}^{f*}\rangle=\frac{\epsilon_{0}}{i\omega}(\bar{\bar{\boldsymbol{\alpha}}}_{i,ln}-\bar{\bar{\boldsymbol{\alpha}}}^{*}_{i,nl})\Theta(\omega,T_{i})\delta_{ij}\delta_{ln},$
(17)

where $\Theta(T,\omega)={\hbar\omega}/[{e^{\frac{\hbar\omega}{k_{B}T}}-1}]$ is
the mean energy of a harmonic oscillator at temperature $T$,
$\bar{\bar{\boldsymbol{\alpha}}}_{i}$ is the polarizability associated to the
$i^{th}$ dipole and $\delta_{\alpha\beta}$ is the usual Kronecker symbol. As,
the polarizability tensor is concerned, it can be described, by taking into
account the radiative corrections, using the following expression Albaladejo

$\bar{\bar{\boldsymbol{\alpha}}}_{i}(\omega)=\left(\bar{\bar{\boldsymbol{1}}}-i\frac{k^{3}}{6\pi}\bar{\bar{\boldsymbol{\alpha_{0}}}}_{i}\right)^{-1}\bar{\bar{\boldsymbol{\alpha_{0}}}}_{i},$
(18)

where $\bar{\bar{\boldsymbol{\alpha_{0}}}}_{i}$ denotes the quasistatic
polarizability of the $i^{th}$ particle and $k=\omega/c$, $c$ being the speed
of light in vacuum. For spherical particles in vacuum, the quasistatic
polarizability takes the simple form

$\bar{\bar{\boldsymbol{\alpha_{0}}}}_{i}(\omega)=4\pi
R^{3}\big{(}\bar{\bar{\boldsymbol{\varepsilon}}}-\bar{\bar{\boldsymbol{1}}}\big{)}\big{(}\bar{\bar{\boldsymbol{\varepsilon}}}+2\bar{\bar{\boldsymbol{1}}}\big{)}^{-1},$
(19)

where $R$ is the radius of particles. Of course others shapes can be
considered without change of the general formalism introduced previously.

Figure 4:  LDOS of electromagnetic field at the center ($z=0$) of an hexagonal
network (a) of gold-InSb nanoparticles ($R=50\>nm$) regularly arranged on a
circle of radius $3R$ for two different orientations of an external magnetic
field (b) $\mathbb{H_{ext}}$ along the $\mathbf{x}$ and $\mathbf{z}$ axis. The
magnitude of this field is $H_{ext}=5T$. (c) LDOS for diifferent magnitude of
magnetic field oriented along the $\mathbf{x}$ axis. Same substrate as in
Fig.2.

To illustrate the potential of non-reciprocal metamaterials to control the
photonic states we show in Figs.3 and 4 this LDOS in the neighborhood of
composite networks made with magneto-optical nanoparticles of indium
antimoniure (InSb) and gold (Au) particles. In this case Palik

$\displaystyle\varepsilon_{a}(H_{ext})\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\varepsilon_{\infty}\bigg{(}1+\frac{\omega_{L}^{2}-\omega_{T}^{2}}{\omega_{T}^{2}-\omega^{2}-i\Gamma\omega}+\frac{\omega_{p}^{2}(\omega+i\gamma)}{\omega[\omega_{c}^{2}-(\omega+i\gamma)^{2}]}\bigg{)},$
$\displaystyle\varepsilon_{b}(H_{ext})\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\frac{\varepsilon_{\infty}\omega_{p}^{2}\omega_{c}}{\omega[(\omega+i\gamma)^{2}-\omega_{c}^{2}]},$
$\displaystyle\varepsilon_{c}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\varepsilon_{\infty}\bigg{(}1+\frac{\omega_{L}^{2}-\omega_{T}^{2}}{\omega_{T}^{2}-\omega^{2}-i\Gamma\omega}-\frac{\omega_{p}^{2}}{\omega(\omega+i\gamma)}\bigg{)}.$
(20)

For the numerical applications we will assume that the infinite-frequency
dielectric constant is $\varepsilon_{\infty}=15.7$ , the longitudinal optical
phonon frequency$\omega_{L}=3.62\times 10^{13}\,\mathrm{rad\,s}^{-1}$ is , the
transverse optical phonon frequency is $\omega_{T}=3.39\times
10^{13}\,\mathrm{rad\,s}^{-1}$, the plasma frequency of free carriers of
density
$\omega_{p}=(\frac{ne^{2}}{m^{*}\varepsilon_{0}\varepsilon_{\infty}})^{1/2}$
with the density $n=1.36\times 10^{19}\,\mathrm{cm}^{-3}$. The effective mass
is $m^{*}=7.29\times 10^{-32}\,\mathrm{kg}$, $\varepsilon_{0}$ being the
vacuum permittivity, $\Gamma=5.65\times 10^{11}\,\mathrm{rad\,s}^{-1}$ is the
phonon damping constant,$\gamma=3.39\times 10^{12}\,\mathrm{rad\,s}^{-1}$ is
the free carrier damping constant, and $\omega_{c}=eH_{ext}/m^{*}$ is the
cyclotron frequency with $e$ the electron charge. As for gold with use the
Drude model Palik98

$\varepsilon(\omega)=1-\frac{\omega_{p}^{2}}{\omega(\omega+i\gamma)},$ (21)

with $\omega_{p}=13.71\times 10^{15}$ $rad.s^{-1}$ and $\gamma=4\times
10^{13}s^{-1}$.

We first consider the simplest case shown in Fig.2 where a single InSb
nanoparticle is deposited on a germanium (Ge) substrate
($\varepsilon_{sub}=16$) and we calculate the LDOS above this particle when
the external magnetic field is rotated from the direction normal to the
substrate surface to the direction parallel to it. In this system there is no
configurational resonance KellerEtAl1993 , so that the LDOS spectrum keep the
same shape when the magnetic field is rotated. But, the situation radically
changes in more complex networks. Hence, if the InSb particle is placed, for
instance, inside an ellipsoidal cavity (Fig.3-a) made with Au particles then,
by changing the orientation of external magnetic field, we see that not only
the magnitude of the LDOS is modified but further resonant modes appear in the
spectrum and they can be shifted by rotation of external magnetic
fieldSupplMat . These modes are the configurational or hybridization modes
Pascale ; Prodan ; Nordlander  which are related to the interplay between the
different particles inside the network.

In the second example, plotted in Fig. 4 we show that the LDOS can also be
modified in a narrow spectral band by changing either the orientation or the
magnitude of external field. The system is a simple hexagonal network of gold
and InSb particles deposited on a Ge substrate as sketch in Fig. 3-a and the
LDOS is calculated at the center of the network. In this case we see that the
LDOS can be modulated by about two orders of magnitude at the resonance
frequency of the InSb particle SupplMat  simply by changing the orientation of
$\mathbb{H_{ext}}$ between the normal to the surface and the $\mathbb{x}$ axis
and by about one order of magnitude by changing the magnitude of
$\mathbb{H_{ext}}$.

In conclusion, we have investigated the photonic density of states near
magnteo-optical metamaterials in presence of an external magnetic field and
demonstrated that the LDOS can be significantly modified at subswavelength
scale by changing the spatial orientation or the magnitude of this field. This
result provides a pathway for an active control of the LDOS and it could find
broad applications ranging from the control of the spontaneous emission of
quantum dots or atoms to the manipulation of molecules placed in the close
vicinity of these media. By combining non-convex optimization techniques Chao
and knowledge in the areas of many-body interactions a computational design of
non-reciprocal metamaterials could be performed in order to make an ad hoc
sculpting of LDOS.

###### Acknowledgements.

This work was supported by the French Agence Nationale de la Recherche (ANR),
under grant ANR-21-CE30-0030 (NBODHEAT).

## References

  * (1) E. M. Purcell, Phys. Rev. 69, 681 (1946).
  * (2) E.Yablonovitch, Phys. Rev. Lett. 58, 2059 (1987).
  * (3) S. John, Phys. Rev. Lett. 58, 2486(1987).
  * (4) P. J. Hesketh, J. N. Zemel and B. Gebhart, Phys. Rev. B 37, 10803 (1988).
  * (5) F. Koppens, D. E. Change, and F. J. García de Abajo, Nano Lett. 11, 3370 (2011).
  * (6) R. Messina et al. , Phys. Rev. B 87, 085421 (2013).
  * (7) S. Viarbitskaya, A. Teulle, R.Marty et al., Nature Mater 12, 426–432 (2013).
  * (8) P. R. Wiecha, A. Arbouet, A. Cuche, Vincent Paillard and Christian Girard, Phys. Rev. B 97, 085411 (2018).
  * (9) P. Lodahl, A. Floris van Driel, I. Nikolaev et al., Nature 430, 654–657 (2004).
  * (10) M. D. Birowosuto, S. E. Skipetrov, W. L. Vos, and A. P. Mosk, Phys. Rev. Lett. 105, 013904 (2010).
  * (11) K. H. Drexhage, Prog. Opt. 12, 163 (1974).
  * (12) R. R. Chance, A. Prock, and R. Silbey, Adv. Chem. Phys. 37, 1 (1978).
  * (13) E. Moncada-Villa, V. Fernández-Hurtado, F.J. García-Vidal, A. García-Martín and J.C. Cuevas, Phys. Rev. B, 92, 125418, (2015).
  * (14) P. Ben-Abdallah, K. Joulain, J. Drevillon and C. Le Goff, Phys. Rev. B 77, 075417 (2008).
  * (15) A. Pérez-Madrid, J. M. Rubi, and L. C. Lapas, Phys. Rev. B 7̱7, 155417 (2008).
  * (16) David Becerril and Cecilia Noguez, Phys. Rev. B 9̱9, 045418 (2019).
  * (17) P. Ben-Abdallah, S.-A. Biehs, and K. Joulain, Phys. Rev. Lett. 107, 114301 (2011).
  * (18) See EPAPS Document No. [number will be inserted by publisher].
  * (19) J. E. Sipe, J. Opt. Soc. Am. B, 4, 481-489 (1987).
  * (20) H. B. Callen and T. A. Welton, Phys. Rev. 83, 34 (1951).
  * (21) S. Albaladejo, R. Gómez-Medina, L. S. Froufe-Pérez, H. Marinchio, R. Carminati, J. F. Torrado, G. Armelles, A. García-Martín, and J. J. Sáenz, Optics Express, 18, 4, pp. 3556-3567 (2010).
  * (22) E. D. Palik, R. Kaplan, R. W. Gammon, H. Kaplan, R. F. Wallis, and J. J. Quinn, Phys. Rev. B 13, 2497 (1976).
  * (23) _Handbook of Optical Constants of Solids_ , edited by E. Palik (Academic Press, New York, 1998).
  * (24) O. Keller, M. Xiao, S. Bozhevolnyi, Surf. Sci. 280, 217 (1993).
  * (25) M. Pascale, G. Miano, R.Tricarico and C. Forestiere, Sci. Rep., 9, 14524 (2019).
  * (26) E. Prodan, C. Radlof, N. J. Halas and P. Nordlander, Sci. 302, 419–422 (2003).
  * (27) P. Nordlander and E. Prodan, Nano Lett. 4, 2209–2213 (2004).
  * (28) P. Chao, B., Strekha, R. Kuate Defo, S. Molesky, A. W. Rodriguez, Nature Reviews Physics. 4, 8, 543-559 (2022).