# AEVA: BLACK-BOX BACKDOOR DETECTION USING ADVERSARIAL EXTREME VALUE ANALYSIS

**Junfeng Guo, Ang Li, Cong Liu**
Department of Computer Science
The University of Texas at Dallas
_{jxg170016,angli,cong}@utdallas.edu_

ABSTRACT

Deep neural networks (DNNs) are proved to be vulnerable against backdoor attacks. A backdoor is often embedded in the target DNNs through injecting a back_door trigger into training examples, which can cause the target DNNs misclassify_
an input attached with the backdoor trigger. Existing backdoor detection methods often require the access to the original poisoned training data, the parameters
of the target DNNs, or the predictive confidence for each given input, which are
impractical in many real-world applications, e.g., on-device deployed DNNs. We
address the black-box hard-label backdoor detection problem where the DNN is
fully black-box and only its final output label is accessible. We approach this problem from the optimization perspective and show that the objective of backdoor detection is bounded by an adversarial objective. Further theoretical and empirical
studies reveal that this adversarial objective leads to a solution with highly skewed
distribution; a singularity is often observed in the adversarial map of a backdoorinfected example, which we call the adversarial singularity phenomenon. Based
on this observation, we propose the adversarial extreme value analysis (AEVA)
to detect backdoors in black-box neural networks. AEVA is based on an extreme
value analysis of the adversarial map, computed from the monte-carlo gradient estimation. Evidenced by extensive experiments across multiple popular tasks and
backdoor attacks, our approach is shown effective in detecting backdoor attacks
under the black-box hard-label scenarios.

1 INTRODUCTION

Deep Neural Networks (DNNs) have pervasively been used in a wide range of applications such
as facial recognition (Masi et al., 2018), object detection (Szegedy et al., 2013; Li et al., 2022), autonomous driving (Okuyama et al., 2018), and home assistants (Singh et al., 2020; Zhai et al., 2021).
In the meanwhile, DNNs become increasingly complex. Training state-of-the-art models requires
enormous data and expensive computation. To address this problem, vendors and developers start to
provide pre-trained DNN models. Similar to softwares shared on GitHub, pre-trained DNN models
are being published and shared on online venues like the BigML model market, ONNX zoo and
Caffe model zoo.

Since the dawn of software distribution, there has been an ongoing war between publishers sneaking
malicious code and backdoors in their software and security personnel detecting them. Recent studies show that DNN models can contain similar backdoors, which are induced due to contaminated
training data. Sometimes models containing backdoors can perform better than the regular models
under untampered test inputs. However, under inputs tampered with a specific pattern (called trojan
trigger) models containing backdoors can suffer from significant accuracy loss.

There has been a significant amount of recent work on detecting the backdoor triggers. However,
those solutions require access to the original poisoned training data (Chen et al., 2019a; Tran et al.,
2018; Huang et al., 2022), the parameters of the trained model (Chen et al., 2019b; Guo et al., 2020;
Liu et al., 2019; Wang et al., 2019; 2020; Dong et al., 2021; Kolouri et al., 2020), or the predicted
confidence score of each class (Dong et al., 2021). Unfortunately, it is costly and often impractical
for the defender to access the original poisoned training dataset. In situations when DNNs are


-----

**Blackbox to the model User/Defender** **Third Party AI Device** **Model User/Defender**

**Input**

**W/ Trigger** **Label Cat** **Query**

**Input**

**W/O Trigger** **Label Dog** **Cloud Server** **Smart Phone** **Edge Device** **Label**

**Deploy**


Figure 1: An illustration of the black-box hard-label backdoors.

deployed in safety-critical platforms (Fowers et al., 2018; Okuyama et al., 2018; Li et al., 2021b) or
in cloud services (Fowers et al., 2018; Chen et al., 2019c), it is also impractical to access either their
parameters or the predicted confidence score of each class (Chen et al., 2019c; 2020b).

We present the black-box hard-label backdoor detection problem where the DNN is a fully blackbox and only its final output label is accessible (Fig. 1). Detecting backdoor-infected DNNs in such
black-box setting becomes critical due to the emerging model deployment in embedded devices and
remote cloud servers. In this setting, the typical optimization objective of backdoor detection (Chen
et al., 2019b; Liu et al., 2019) becomes impossible to solve due to the limited information. However,
according to a theoretical analysis, we show that the backdoor objective is bounded by an adversarial
objective, which can be optimized using Monte Carlo gradient estimation in our black-box hardlabel setup. Further theoretical and empirical studies reveal that this adversarial objective leads to
a solution with highly skewed distribution; a singularity is likely to be observed in the adversarial
map of a backdoor-infected example, which we call the adversarial singularity phenomenon.

Based on these findings, we propose the adversarial extreme value analysis (AEVA) algorithm
to detect backdoors in black-box neural networks. The AEVA algorithm is based on an extreme
value analysis (Leadbetter, 1991) on the adversarial map. We detect the adversarial singularity
phenomenon by looking at the adversarial peak, i.e., maximum value of the computed adversarial
perturbation map. We perform a statistical study which reveals that, there is around 60% chance that
the adversarial peak of a random sample for a backdoor-infected DNN is larger than the adversarial
peak of any examples for an uninfected DNN. Inspired by the Univariate theory, we propose a global
adversarial peak (GAP) value by sampling multiple examples and choosing the maximum over their
adversarial peaks, to ensure a high success rate. Following previous works (Dong et al., 2021; Wang
et al., 2019), the Median Absolute Deviation (MAD) algorithm is implemented on top of the GAP
values to test whether a DNN is backdoor-infected.

Through extensive experiments across three popular tasks and state-of-the-art backdoor techniques,
AEVA is proved to be effective in detecting backdoor attacks under the black-box hard-label scenarios. The results show that AEVA can efficiently detect backdoor-infected DNNs, yielding an overall
detection accuracy ≥ 86.7% across various tasks, DNN models and triggers. Rather interestingly,
when comparing to two state-of-art white-box backdoor detection methods, AEVA yields comparable performance, even though AEVA is a black-box method with limited access to information.

We summarize our contributions as below [1]:

1. To the best of our knowledge, we are the first to present the black-box hard-label backdoor
detection problem and provide an effective solution to this problem.

2. We provide a theoretical analysis which shows backdoor detection optimization is bounded
by an adversarial objective. And we further reveal the adversarial singularity phenomenon
where the adversarial perturbation computed from a backdoor-infected neural network is
likely to suffer from a highly skewed distribution.

3. We propose a generic backdoor detection framework AEVA, optimizing the adversarial
objective and performing extreme value analysis on the optimized adversarial map. AEVA
is applicable to the black-box hard-label setting with a Monte Carlo gradient estimation.

[1Code :https://github.com/JunfengGo/AEVA-Blackbox-Backdoor-Detection-main](https://github.com/JunfengGo/AEVA-Blackbox-Backdoor-Detection-main)


-----

4. We evaluate AEVA on three widely-adopted tasks with different backdoor trigger implementations and complex black-box attack variants. All results suggest that AEVA is effective in black-box hard-label backdoor detection.

1.1 RELATED WORK

**Backdoor attacks. BadNets (Gu et al., 2019) is probably the first work on backdoor attacks against**
DNNs, which causes target misclassification to DNNs through injecting a small trigger into some
training samples and mis-labeling these samples with a specific target class. Trojaning attack (Liu
et al., 2018) generates a trigger which can cause the maximum activation value of certain selected
neurons with limited training data. Chen et al. (Chen et al., 2017) further propose to perform backdoor attacks under a rather weak threat model where the attacker cannot access the target model and
training dataset. Most recently, a set of backdoor attacks (Ji et al., 2018; Liu et al., 2020; Saha et al.,
2020; Turner et al., 2019; Yao et al., 2019) have been proposed, which are built upon existing work
but focused on various specific scenarios, e.g., physical-world, transfer learning, etc.

**Backdoor detection (white-box). A few works (Chen et al., 2019a; Tran et al., 2018) are proposed**
to detect the backdoor samples within the training dataset. Chen et al. (2019a) propose a neuron
activation clustering approach to identify backdoor samples through clustering the training data
based on the neuron activation of the target DNN. Tran et al. (2018) distinguish backdoor samples
from clean samples based on the spectrum of the feature covariance of the target DNN. Few other
works focus on detecting backdoor-infected DNNs (Liu et al., 2019; Wang et al., 2019). ABS (Liu
et al., 2019) identifies the infected DNNs by seeking compromised neurons representing the features
of backdoor triggers. Neural Cleanse (Wang et al., 2019) conducts the reverse engineering to restore
the trigger through solving an optimization problem. Recent works (Chen et al., 2019b; Guo et al.,
2020; Wang et al., 2020) improve Neural Cleanse with better objective functions. However, these
methods are all white-box based, requiring access to model parameters or internal neuron values.

**Backdoor detection (black-box). A recent work (Chen et al., 2019b) claims to detect backdoor at-**
tacks in the “black-box” settings. However, their method still need the DNN’s parameters to train a
separate generator (Goodfellow et al., 2014). So, strictly speaking, their method is not “black-box”,
which is also revealed by (Dong et al., 2021). To the best of our knowledge, Dong et al. (2021) is the
only existing work on detecting backdoor-infected DNNs in the black-box settings. However, their
method requires the predictive confidence score for each input to perform the NES algorithm (Wierstra et al., 2014), which weakens its practicability. Our work differs from all previous methods in
that we address a purely black-box setup where only the hard output label is accessible. Both model
parameters and training examples are inaccessible in the black-box hard-label setting.

2 PRELIMINARIES: BLACK-BOX BACKDOOR ATTACK AND DEFENSE

2.1 THREAT MODEL

Our considered threat model contains two parts: the adversary and the defender. The threat model
of the adversary follows previous works (Chen et al., 2017; Gu et al., 2019; Liu et al., 2018). In this
model, the attacker can inject an arbitrary amount of backdoor samples into the training dataset and
cause target misclassification to a specific label without affecting the model’s accuracy on normal
examples. From the perspective of the defender, we consider the threat model with the weakest
assumption, in which the poisoned training dataset and the parameters of the target DNNs f (·) are
inaccessible. Moreover, the defender can only obtain the final predictive label for each input from
the target DNNs and a validation set (40 images for each class). Therefore, the defender can only
query the target DNNs to obtain its final decisions. The defender’s goal is to identify whether the
target DNNs is infected and which label is infected.

2.2 PROBLEM DEFINITION

Consistent with prior studies (Dong et al., 2021; Kolouri et al., 2020; Wang et al., 2019; Huang et al.,
2022), we deem a DNN is backdoor infected if one can make an arbitrary input misclassified as the
target label, with minor modification to the input. Without loss of generability, given the original


-----

input x ∈ R[n], the modified input containing the backdoor trigger can be formulated as:

_xˆ = b(x) = (1 −_ _m) ⊙_ _x + m ⊙_ ∆, (1)

where ∆ _∈_ R[n] represents the backdoor trigger and ⊙ represents the element-wise product. m ∈
_{0, 1}[n]_ is a binary mask that ensures the position and magnitude of the backdoor trigger. Typically,
_||m||1 ought to be very small to ensure the visually-indistinguishability between ˆx and x._

We define f (·; θ) as the target DNN with parameters θ, which is a function that maps the input x
to a label y. φ(x, y; θ) ∈ [0, 1] is defined as the probability that x is classified as y by f (·; θ). The
argument θ is sometimes omitted in favor of simplicity. For f to mislabel ˆx as the target label yt,
there are two possible reasons: the backdoored training data either contains the same trigger but
mislabeled as yt or contains similar features as the normal inputs (not belonging to yt, but visually
similar to yt) and labeled as yt.


_No_

_ℓ(φ(xi, yi; θ), yi) +_
_i=1_

X


_Nb_

_ℓ(φ(ˆxj, yt; θ), yt),_ (2)
_j=1_

X


_θˆ = arg min_


where there are No original training examples and Nb backdoor examples. ℓ(·) represents the crossentropy loss function; xi and yi represent the training sample and its corresponding ground-truth
label, respectively. In the inference phase, the target DNN will predict each ˆx as the target label yt,
which can be formulated as: f (ˆx) = yt. Prior works (Dong et al., 2021; Wang et al., 2019; Chen
et al., 2019b) seek to reveal the existence of a backdoor through investigating whether there exists a
backdoor trigger with minimal ||m||1 that can cause misclassification to a certain label.

We mainly study the sparse mask since it is widely used in previous works (Wang et al., 2020; Dong
et al., 2021; Chen et al., 2019b; Guo et al., 2020; Wang et al., 2019; Gu et al., 2019). In cases when
the mask becomes dense, the mask m has to contain low magnitude continuous values to ensure
the backdoor examples visually indistinguishable. However, when the value of m is small, every
normal example xi becomes near the decision boundary of function φ. It is revealed by Taylor theorem, φ(ˆxi) = φ((1 − _m)xi + m∆) = φ(xi + m(∆_ _−_ _xi)) ≈_ _φ(xi) + m(∆_ _−_ _xi)[⊺]∇xφ. And the_
function output label changes dramatically from φ(xi) to φ(ˆxi), so the gradient _xφ has to have a_
_∇_
large magnitude, which results in a non-robust model sensitive to subtle input change. Such models become impractical because a small random perturbation on the input can lead to significantly
different model output. More details with empirical study can be found in the Appendix A.

2.3 BLACK-BOX BACKDOOR DETECTION AND ITS CHALLENGES

Most previous works (Wang et al., 2019; Dong et al., 2021; Chen et al., 2019b) focus on reverseengineering the backdoor trigger for each target label yt using the following optimization:


_ℓ(φ((1 −_ _m) ⊙_ _xi + m ⊙_ ∆, yt), yt) + β||m||1, (3)


arg min
_m,∆_


where β is the balancing parameter. Unfortunately, solving Eq. 3 is notoriously hard in the blackbox hard-label setting since θ is unknown. Additional difficulty comes with the fact that an effective
zero-th order gradient estimation requires each example xi superimposed with the trigger to be close
to the decision boundary of yt (Chen et al., 2020a; Cheng et al., 2020; Li et al., 2020). However,
such condition is hard to achieve in the hard-label blackbox settings.

3 ADVERSARIAL EXTREME VALUE ANALYSIS FOR BACKDOOR DETECTION

Our AEVA framework is introduced in this section. We first derive an upper bound to the backdoor
detection objective in Eq. 3 and find its connection to adversarial attack. The adversarial singularity
phenomenon is further revealed in both theoretical results and empirical studies. Based on our
findings, we propose the Global Adversarial Peak (GAP) measure, computed by extreme value
analysis on the adversarial perturbation. The GAP score will be finally used with Median Absolute
Deviation (MAD) to detect backdoors in neural networks. Monte Carlo gradient estimation is further
introduced in order to solve the adversarial objective in the black-box setting.


-----

3.1 ADVERSARIAL OBJECTIVE AS AN UPPER BOUND OF THE BACKDOOR OBJECTIVE

We present in this section the connection between the backdoor objective in Eq. 3 with the objective
in adversarial attacks. To begin with, we first transform the backdoor masking equation (1 − _m) ⊙_
_xi + m ⊙_ ∆= xi + µ − _m ⊙_ _xi, where µ = m ⊙_ ∆. Following this, the optimization in Eq. 3
converts to minimizing the following term:


_F = [1]_


_ℓ(φ(xi + µ −_ _m ⊙_ _xi, yt; θ), yt) ._ (4)
_i=1_

X


We further introduce an important result from the Multivariate Taylor Theorem below.

**Lemma 1. Given a continuous differentiable function f** (·) defined on R[n] _and vectors x, h ∈_ R[n],
_for any M_ _∂f/∂hi_ _,_ 1 _i_ _n, we have_ _f_ (x + h) _f_ (x) _M_ _h_ 1.
_≥|_ _|_ _∀_ _≤_ _≤_ _|_ _−_ _| ≤_ _∥_ _∥_

The lemma can be proved using the Lagrange Remainder. Please refer to the Appendix B.1 for a
detailed proof. According to the lemma, we have

_N_ _N_

_ℓ(φ(xi + µ, yt; θ), yt)_ _C_ _m_ _xi_ 1 _C_ _m_ 1 = C _µ_ 0, (5)

_N_ Xi=1 _[≤]_ _N[1]_ Xi=1 _∥_ _⊙_ _∥_ _≤_ _∥_ _∥_ _∥_ _∥_

where the latter inequality holds because each example xi 1 is bounded and the last equality

_[F][ −]_ [1]

_∥m∥1 = ∥m⊙∆∥0 = ∥µ∥0 holds because m is a binary mask. Then, we can see that the adversarial ≤_
objective is an upper bound of the objective in backdoor detection, i.e., F ≤ _N[1]_ _i_ _[ℓ][(][φ][(][x][i][+][µ][)][, y][t][)+]_

_C_ _µ_ 0. Instead of optimizing the original Eq. 3, we here propose to minimize the ℓ[0]-regularized
_∥_ _∥_ P
objective. While ℓ[0] enforces the sparsity of the solution, optimizing it is NP-hard. In practice, it is
replaced with an ℓ[1]-norm as an envelope of the objective (Ramirez et al., 2013; Donoho, 2006):


_ℓ(φ(xi + µ, yt; θ), yt) + λ∥µ∥1 ._ (6)


_µˆ = arg min_


This adversarial optimization can be solved using Monte Carlo gradient estimation in our black-box
setting. More details are described in Section 3.4. In the following, we will first discuss how the
solution to this adversarial objective can be used to detect backdoors in neural networks.

3.2 THE ADVERSARIAL SINGULARITY PHENOMENON

A natural and important question here is what the adversarial perturbation ˆµ would look like when
the input is infected with backdoor attacks. A direct analysis on deep neural networks is hard. So,
we start by analyzing a linear model to shed light on the intuition of our approach.

**Lemma 2. Given a linear model parameterized by θ optimized on No original training examples**
_and Nb backdoored training examples with an objective in Eq. 2 and a mean-squared-error loss, the_
_adversarial solution ˆµ optimized using Eq. 6 will be dominated by input dimensions corresponding_
_to backdoor mask m when Nb is large, i.e., limNb_ (1 _m)_ _µˆ_ 1/ _µˆ_ 1 = 0.
_→∞_ _∥_ _−_ _⊙_ _∥_ _∥_ _∥_

The lemma can be proved by least square solutions and exact gradient computation. Detailed proof
can be found in the Appendix B.2. The lemma reveals that the majority of the mass in the adversarial
perturbation will be occupied in the mask area. Since the mask m is usually sparse, it is reasonable
to expect a highly skewed distribution in the adversarial map ˆµ.

We suspect that such skewed distributions might also occur in the adversarial map of a deep neural
network. While a thorough analysis on DNN is hard, recent studies in Neural Tangent Kernel (NTK)
(Jacot et al., 2018) have shown that a deep neural network with infinite width can be treated as kernel
least square. So, we further extended our analysis to a k-way kernel least square classifier as the
model and a cross-entropy loss used in the adversarial analysis.

**Lemma 3. Suppose the training dataset consists of No original examples and Nb backdoor exam-**
_ples, i.i.d. sampled from uniform distribution and belonging to k classes. Let φ be a multivariate_
_kernel regression with the objective in Eq. 2, an RBF kernel. Then the adversarial solution ˆµ to Eq._
_6 under cross-entropy loss should satisfy that limNb_ E[(1 _m)_ _µˆ] = 0._
_→∞_ _−_ _⊙_


-----

0.025

0.020

0.015 z

0.010

0.005

30

25

20

0 5 10 x15 20 25 30 0 5 1015 y

(b) ˆµ for the infected label


0.025

0.020

0.015 z

0.010

0.005

0.000

30

25

20

0 5 10 x15 20 25 30 0 5 1015 y

(c) ˆµ for the uninfected label


0

5

10

15

20

25

30

0 5 10 15 20 25 30


(a) Backdoor map ∆


Figure 2: The distribution of values in the normalized adversarial perturbation µ for the infected (b)
and uninfected (c) labels, using a backdoor map in (a). x, y axes represent the image space; z axis
represents the absolute value of the normalized µ corresponding to each pixel location.

The proof can be found in Appendix B.3. The lemma reveals a similar result as the linear case
that the majority mass of the adversarial perturbation (in expectation) stays in the mask area when
sufficient backdoor examples are used. Although the lemma does not directly address a deep neural
network, we hope this result could help understand the problem better in the NTK regime.

We perform an empirical study on DNNs to validate our intuition. Following previous works (Dong
et al., 2021; Wang et al., 2019; 2020), we implement BadNets (Gu et al., 2019) as the backdoor
attack method. We randomly select a label as the infected label and train a ResNet-44 on CIFAR-10
embedded with the backdoor attack, resulting in an attack success rate of 99.87%. The backdoor
trigger is a 4x4 square shown in Fig. 2(a), which occupies at most 1.6% of the whole image. The
adversarial perturbations ˆµ (by optimizing Eq. 6) are generated for both infected and uninfected
labels. The perturbations are normalized to a heat map as |µˆ|/||µˆ||1 and shown in Fig. 2. A high
concentration of mass is clearly observed from the infected case in Figure 2(b). We call it adversarial
_singularity phenomenon. This motivates our adversarial extreme value analysis (AEVA) method._

3.3 ADVERSARIAL EXTREME VALUE ANALYSIS


A natural way to identify singularity is to look at the peak value of
the distribution. We define the adversarial peak µmax = max µij
for an adversarial perturbation µ. To gain a statistical understanding of the relationship between adversarial peak and backdoor attacks, We randomly sample 1000 normalized µ for the uninfected
and infected labels and plot the distribution of µmax in Fig. 3. The
experimental setup is consistent with the empirical study in Sec.
3.2. We notice from the figure that µmax of the infected labels
reaches a much larger range compared to that of uninfected labels. However, they still overlap; around 47% infected µmax stays
within the uninfected range (the area with both blue and orange
bars). This result suggests that


Figure 3: The distributions of ad
0.25 Uninfected

Infected

0.20

0.15

Proportion0.10

0.05

0.00

0.02

max

versarial peak µmax for infected
labels and uninfected labels.


_the adversarial singularity phenomenon does not always occur in backdoor-infected DNNs. It is rea-_
sonable because some samples are inherently vulnerable to adversarial attacks and their adversarial
perturbations have similar properties as backdoors, which reduces the chance of singularity.

Now, we know if we define a threshold T as the maximum value of the uninfected labels, the
probability of a backdoor-infected µmax being smaller than T is 0.47, i.e., P (µmax < T ) = 0.47.
Taking one example is impossible to know whether a label is infected. However, according to the
Univariate Theory (Gomes & Guillou, 2015), if we sample k examples of µmax for the same label,

_P_ (max _µ[1]max[, µ][2]max[, . . ., µ][k]max[}][ < T]_ [) = (][P] [(][µ]max _[< T]_ [))][k][ .] (7)
_{_
Here we name the maximum value over all the k adversarial peaks as the Global Adversarial Peak
(GAP). We vary the choice of k in Figure 4 and we can see that the chance of GAP value being
lower than T is diminishing. For example, if we take k = 6, then P (GAP < T ) = 0.47[6] = 0.01
and the success rate of identifying a backdoor-infected label is 99%. Please be advised that, given


-----

the long-tail distribution of the infected µmax, this threshold T is not sensitive and can be made even
larger to be safe to include all uninfected labels. However, for larger T values, we need a larger k to
ensure a desired success rate.


3.4 BLACK-BOX OPTIMIZATION VIA GRADIENT ESTIMATION

After investigating the unique properties of backdoor-infected
DNNs in the white-box settings, we here illustrate how to exploit such properties under a rather restricted scenario as we consider. In the white-box settings, the free access to θ can enable
us to compute the _xφ(x, yt) accurately, resulting in µ with min-_
_∇_
imum ||µ||1 through optimizing Eq. 6. Regarding the black-box
settings, we propose to leverage the zero-order gradient estimation technique (Fu & Hu, 2012) to address the challenge for calculating _xφ(x, yt). We choose Monte Carlo based method (Fu &_
_∇_
Hu, 2012) for obtaining the estimated gradient _φx(x, yt), which_
_∇_
sends several inputs and utilizes the corresponding outputs to estimate the gradient. More details about gradient estimation can be

[f]
found in Appendix C.

3.5 FINAL ALGORITHM


0.5

|Col1|Col2|Col3|
|---|---|---|
|1.0 0.9 Rate 0.8 Success 0.7|||
||||


10[0] 10[1] 10[2]


Sample size (k) for thresholding

Figure 4: The proportion of infected labels whose max{µ[i]max[}]
larger than that of uninfected ones.


**Input** **Dog** **Gradient Estimation** **Adversarial Perturbation** **Aggregated GAP** **MAD Detector**

**0.2701** **7.6219**

**Query** **Label** **(Malicious)**

**...** **...** **...** **...**

**Anomaly**

**Index**

**Black-box Backdoored** **0.1494** **1.0133**

**DNNs (Trigger:  )**


Figure 5: Overview of AEVA – Adversarial Extreme Value Analysis.

Putting all the above ideas together, we present the AEVA framework (illustrated in Fig. 5). The
algorithm for computing the GAP value of a given label is described in Algorithm 1. Our approach
requires a batch of legitimate samples Xi for each class i. For each label yt to be analyzed, the
algorithm will tell whether yt is backdoor-infected. We treat yt as the targeted label. Then we
collect a batch of legitimate samples belonging to yt, denoted as Xt with the same batch size as
that of Xi. Then, we leverage Xt to make each sample within every {Xi}i[n]=0 [to approach the]
decision boundary of yt. This is computed by optimizing ˆµ from Eq. 6 using Monte Carlo gradient
estimation. The adversarial peak µmax is then computed for each example. The global adversarial
peak (GAP) is aggregated over all labels. After calculating the GAP value (yi) for each class i,
_R_
following previous work (Wang et al., 2019; Dong et al., 2021), we implement Median Absolute
Deviation (MAD) to detect the outliers among {R(yi)}i[n]=1[. Specifically, we use MAD to calculate]
the anomalous index for each R(yi) by assuming {R(yi)}i[n]=1 [fits Gaussian distribution. The outlier]
is then detected by thresholding the anomaly index.


4 EXPERIMENTS

4.1 SETTINGS


**Datasets. We evaluate our approach on CIFAR-10, CIFAR-100, and Tiny-ImageNet datasets. For**
each task, We build 240 infected and 240 benign models with different architectures: ResNets (He
et al., 2016) and DenseNets (Huang et al., 2017). We randomly select one label for each backdoorinfected model and inject sufficient poisoned samples to ensure the attack success rate ≥ 98%. More
details can be found in the Appendix.


-----

**Uninfected** **BadNets** **Watermark**

**Label Consistent** **Invisible Attack**


Figure 6: The visualization of adversarial perturbation ˆµ for infected labels with different backdoor attacks on
TinyImageNet. For each attack, we show the trigger (left), ˆµ map (middle) and ˆµ distribution in 3D (right).

|Task|Detection Accuracy (ACC) BadNets Watermark Label Consistent Invisible Attack Total(Infected) Benign|
|---|---|
|CIFAR-10 CIFAR-100 TinyImageNet|86.7% 93.3% 93.3% 93.3% 91.7% 95.4% 93.3% 100% 96.7% 96.7% 96.7% 97.5% 96.7% 100% 93.3% 96.7% 96.7% 99.2%|



Table 1: Overall performance of our approach on three tasks.

**Attack methods. Four different attack methods are implemented: BadNets (Gu et al., 2019), Wa-**
termark attack (Chen et al., 2017), Label-Consistent Attack (Turner et al., 2019) and Invisible Attack (Li et al., 2021a). For BadNets and Watermark, the triggers are 4 _×_ 4 squares. The transparency
ratio for Watermark attack is 0.1. For label-consistent and invisible attacks, we use the default lessvisible triggers. Around 10% poison data is injected in training. Each model is trained for 200
epochs with data augmentation. More details can be found in the Appendix G.

**Baseline methods. Since there is no existing black-box hard-label method, we compare our ap-**
proach with two state-of-art white box backdoor detection methods: Neural Cleanse (NC) (Wang
et al., 2019) and DL-TND (Wang et al., 2020)[2]. For each task, we use 200 samples for the gradient
estimation, and the batch size for each {Xi}i[n]=1 [is set to 40 in Algorithm 1.]

**Outlier detection. To accurately identify the anomalous R(yi) among {R(yi)}i[n]=1[, we assume]**
the scores fit to a normal distribution and apply a constant estimator (1.4826) to normalize the
computed anomaly index similar to (Wang et al., 2019). We set the threshold value τ = 4 for our
MAD detector, which means we identify the class whose corresponding anomaly index larger than
4 as infected. This value is chosen using a hold-out validation set of infected and benign models.

**Evaluation metrics. We follow previous work (Kolouri et al., 2020; Wang et al., 2020; Dong et al.,**
2021; Guo et al., 2020) on using two common metrics: (a) The Area under Receiver Operating
_Curve (AUROC) – The Receiver Operating Curve (ROC) shows the trade-off between detection_
success rate for infected models and detection error rate for benign models across different decision
thresholds τ for anomaly index; (b) Detection Accuracy (ACC) – The proportion of models are correctly identified. Regarding infected models, they are correctly identified if and only if the infected
labels are identified without mistagging other uninfected labels.

4.2 RESULTS

We first investigate whether AEVA can reveal the singularity phenomenon of labels infected with
different attack approaches. We randomly select an infected model infected by each attack approach
and an uninfected model for TinyImageNet task. Notably, all these selected models are correctly
identified by our approach. We plot the corresponding normalized adversarial perturbation µ in
Fig. 6, which demonstrates that AEVA can accurately and distinguish the uninfected and infected
labels and reveal the singularity phenomena of backdoor triggers.

Table 1 presents the overall results. AEVA can accurately detect the infected label with ACC
_≥_ 86.7% across all three tasks and various trigger settings. We compare our approach with existing white-box detection approaches including Neural Cleanse (NC) (Wang et al., 2019) and DLTND (Wang et al., 2020). The comparison results over all infected and benign models are shown in

[2We implement NC (Wang et al., 2019) and DL-TND (Wang et al., 2020) following https://github.](https://github.com/bolunwang/backdoor)
[com/bolunwang/backdoor and https://github.com/wangren09/TrojanNetDetector](https://github.com/bolunwang/backdoor)


-----

1.00 1.00 1.00

0.95 0.95 0.95

0.90 0.90 0.90

0.85 0.85 0.85

0.80 NC(White-box) 0.80 NC(White-box) 0.80 NC(White-box)

DL-TND(White-box) DL-TND(White-box) DL-TND(White-box)

for infected models 0.75 AEVA for infected models 0.75 AEVA for infected models 0.75 AEVA

Detection success rate Detection success rate Detection success rate

0.70 0.0 0.1 0.2 0.3 0.4 0.5 0.70 0.0 0.1 0.2 0.3 0.4 0.5 0.70 0.0 0.1 0.2 0.3 0.4 0.5

Detection error rate for Detection error rate for Detection error rate for

benign models benign models benign models


(a) CIFAR-10


(b) CIFAR-100


(c) TinyImageNet


Figure 7: The Receiver Operating Cure(ROC) for NC, DL-TND and AEVA on CIFAR-10, CIFAR100 and TinyImageNet tasks. AEVA is black-box while the other two methods are white-box.

Fig. 7. More results can be found in Appendix J. The results suggest that AEVA achieves comparable performance with existing white-box detection approaches across different settings. Such close
performance also indicates the efficacy of AEVA on black-box hard-label backdoor detection.

4.3 ABLATION STUDY


**The impact of trigger size. We test AEVA on TinyImageNet with**
different trigger sizes for BadNets and Watermark attacks. For
each trigger size and attack method, we build 60 infected models
with various architectures following the configurations in Sec. 4.2.
Fig. 8 shows that AEVA remains effective when trigger size is less
than 14 _×_ 14 with ACC ≥ 71.7%. For large triggers, AEVA cannot
identify the infected label since the singularity property is alleviated. This is consistent with our theoretical analysis. Even though
large trigger attacks can bypass AEVA, they are either visuallydistinguishable or leading to a non-robust model sensitive to input
change, making it less stealthy and impractical.

**The impact of infected label numbers. We further investigate**
the impact of the number of infected labels. We build 60 infected
models for CIFAR-10 to evaluate AEVA. We randomly select infected labels, and we inject a 2 × 2 trigger for each infected label.
Fig. 9 shows that AEVA performs effectively when the number of
infected labels is less than 3 (i.e., 30% of the entire labels) with
ACC ≥ 78.3%. It is because too many infected labels fail the
MAD outlier detection. Interestingly, existing white-box detection
methods (Wang et al., 2019; Chen et al., 2019b; Guo et al., 2020;
Liu et al., 2019; Wang et al., 2020) cannot perform effectively in
such scenarios either. However, too many infected labels would
reduce the stealth of the attacker as well.


Figure 8: The impact of trigger

1.0

BadNets

0.8 Watermark

0.6

ACC

0.4

0.2

0.0

2x2 6x6 10x10 14x14 18x18

Trigger Size

size on detection accuracy.

Figure 9: The impact of infected

1.0

BadNets

0.8 Watermark

0.6

ACC

0.4

0.2

0.0

1 2 3 4 5 6 7

The number of infected labels

label size on detection accuracy.


Besides these studies, we further evaluate our approach under more scenarios, including the impact
of the number of available labels, multiple triggers for a single infected label, different backdoor
trigger shapes and potential adaptive backdoor attacks, which are included in the Appendix.

5 CONCLUSION

This paper takes a first step addressing the black-box hard-label backdoor detection problem. We
propose the adversarial extreme value analysis (AEVA) algorithm, which is based on an extreme
value analysis on the adversarial map, computed from the monte-carlo gradient estimation due to the
black-box hard-label constraint. Extensive experiments demonstrate the efficacy of AEVA across a
set of popular tasks and state-of-the-art backdoor attacks.


-----

ETHICS STATEMENT

Our work aims at providing neural network practitioners additional protection against backdoor
attacks. We believe our work could contribute positively to the human society and avoid potential
harm since it addresses a critical safety problem. We are unaware of any direct negative impact out
of this work. Our method has certain limitations such as the sensitivity to large backdoor trigger
and multiple infected labels. However, as we earlier in the paper, these scenarios make the attack
become less stealthy and not practical in real applications.

REPRODUCIBILITY STATEMENT

Our work is built upon comprehensive theoretical results and clear motivations. We believe the proposed method can be reproduced according to the content in the paper, e.g., Algorithm 1. In addi[tion, we have released the implementation of AEVA in https://github.com/JunfengGo/](https://github.com/JunfengGo/AEVA-Blackbox-Backdoor-Detection-main)
[AEVA-Blackbox-Backdoor-Detection-main.](https://github.com/JunfengGo/AEVA-Blackbox-Backdoor-Detection-main)

REFERENCES

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 SafeAI@AAAI, 2019a. URL http://ceur-ws.org/Vol-2301/](http://ceur-ws.org/Vol-2301/paper_18.pdf)
[paper_18.pdf.](http://ceur-ws.org/Vol-2301/paper_18.pdf)

Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. Deepinspect: A black-box trojan
detection and mitigation framework for deep neural networks. In IJCAI, pp. 4658–4664, 2019b.

Jianbo Chen, Michael I Jordan, and Martin J Wainwright. Hopskipjumpattack: A query-efficient
decision-based attack. In 2020 ieee symposium on security and privacy (sp), pp. 1277–1294.
IEEE, 2020a.

Steven Chen, Nicholas Carlini, and David Wagner. Stateful detection of black-box adversarial attacks. In Proceedings of the 1st ACM Workshop on Security and Privacy on Artificial Intelligence,
pp. 30–39, 2020b.

Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep
[learning systems using data poisoning. CoRR, abs/1712.05526, 2017. URL http://arxiv.](http://arxiv.org/abs/1712.05526)
[org/abs/1712.05526.](http://arxiv.org/abs/1712.05526)

Yao Chen, Jiong He, Xiaofan Zhang, Cong Hao, and Deming Chen. Cloud-dnn: An open framework
for mapping dnn models to cloud fpgas. In Proceedings of the 2019 ACM/SIGDA international
_symposium on field-programmable gate arrays, pp. 73–82, 2019c._

Minhao Cheng, Simranjit Singh, Patrick H. Chen, Pin-Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Signopt: A query-efficient hard-label adversarial attack. In International Conference on Learning
_[Representations, 2020. URL https://openreview.net/forum?id=SklTQCNtvS.](https://openreview.net/forum?id=SklTQCNtvS)_

Yinpeng Dong, Xiao Yang, Zhijie Deng, Tianyu Pang, Zihao Xiao, Hang Su, and Jun Zhu. Blackbox detection of backdoor attacks with limited information and data. In Proceedings of the
_IEEE/CVF International Conference on Computer Vision (ICCV), pp. 16482–16491, October_
2021.

D.L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306,
2006. doi: 10.1109/TIT.2006.871582.

Jeremy Fowers, Kalin Ovtcharov, Michael Papamichael, Todd Massengill, Ming Liu, Daniel Lo,
Shlomi Alkalay, Michael Haselman, Logan Adams, Mahdi Ghandi, et al. A configurable cloudscale dnn processor for real-time ai. In 2018 ACM/IEEE 45th Annual International Symposium
_on Computer Architecture (ISCA), pp. 1–14. IEEE, 2018._

Michael C Fu and Jian-Qiang Hu. Conditional Monte Carlo: Gradient estimation and optimization
_applications, volume 392. Springer Science & Business Media, 2012._


-----

M Ivette Gomes and Armelle Guillou. Extreme value theory and statistics of univariate extremes: a
review. International statistical review, 83(2):263–292, 2015.

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In
Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.),
_Advances in Neural Information Processing Systems,_ volume 27. Curran Associates,
Inc., 2014. URL [https://proceedings.neurips.cc/paper/2014/file/](https://proceedings.neurips.cc/paper/2014/file/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf)
[5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf.](https://proceedings.neurips.cc/paper/2014/file/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf)

Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Evaluating backdooring
attacks on deep neural networks. IEEE Access, pp. 47230–47244, 2019. doi: 10.1109/ACCESS.
2019.2909068.

Wenbo Guo, Lun Wang, Yan Xu, Xinyu Xing, Min Du, and Dawn Song. Towards inspecting and
eliminating trojan backdoors in deep neural networks. In 2020 IEEE International Conference on
_Data Mining (ICDM), pp. 162–171, 2020. doi: 10.1109/ICDM50108.2020.00025._

Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
770–778, 2016.

Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected
convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern
_recognition, pp. 4700–4708, 2017._

Kunzhe Huang, Yiming Li, Baoyuan Wu, Zhan Qin, and Kui Ren. Backdoor defense via decoupling
the training process. In ICLR, 2022.

Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and
generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman,
N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems,
[volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/](https://proceedings.neurips.cc/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf)
[paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf.](https://proceedings.neurips.cc/paper/2018/file/5a4be1fa34e62bb8a6ec6b91d2462f5a-Paper.pdf)

Yujie Ji, Xinyang Zhang, Shouling Ji, Xiapu Luo, and Ting Wang. Model-reuse attacks on deep
learning systems. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Com_munications Security, pp. 349–363, 2018._

Soheil Kolouri, Aniruddha Saha, Hamed Pirsiavash, and Heiko Hoffmann. Universal litmus patterns:
Revealing backdoor attacks in cnns. In Proceedings of the IEEE/CVF Conference on Computer
_Vision and Pattern Recognition, pp. 301–310, 2020._

M.R. Leadbetter. On a basis for peaks over threshold modeling. _Statistics_ _and_
_Probability Letters, 12(4):357–362, 1991._ ISSN 0167-7152. doi: https://doi.org/10.
1016/0167-7152(91)90107-3. [URL https://www.sciencedirect.com/science/](https://www.sciencedirect.com/science/article/pii/0167715291901073)
[article/pii/0167715291901073.](https://www.sciencedirect.com/science/article/pii/0167715291901073)

Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query-efficient boundarybased blackbox attack. In Proceedings of the IEEE/CVF Conference on Computer Vision and
_Pattern Recognition (CVPR), June 2020._

Shaofeng Li, Minhui Xue, Benjamin Zi Hao Zhao, Haojin Zhu, and Xinpeng Zhang. Invisible
backdoor attacks on deep neural networks via steganography and regularization. IEEE Transac_tions on Dependable and Secure Computing, 18(5):2088–2105, 2021a. doi: 10.1109/TDSC.2020._
3021407.

Yiming Li, Haoxiang Zhong, Xingjun Ma, Yong Jiang, and Shu-Tao Xia. Few-shot backdoor attacks
on visual object tracking. In ICLR, 2022.

Yuezun Li, Yiming Li, Baoyuan Wu, Longkang Li, Ran He, and Siwei Lyu. Invisible backdoor
attack with sample-specific triggers. In ICCV, 2021b.


-----

Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu
Zhang. Trojaning attack on neural networks. In 25nd Annual Network and Distributed System Se_curity Symposium, NDSS 2018, San Diego, California, USA, February 18-221, 2018. The Internet_
Society, 2018.

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 Proceedings of the
_2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 1265–1282,_
2019.

Yunfei Liu, Xingjun Ma, James Bailey, and Feng Lu. Reflection backdoor: A natural backdoor
attack on deep neural networks. In European Conference on Computer Vision, pp. 182–199.
Springer, 2020.

Iacopo Masi, Yue Wu, Tal Hassner, and Prem Natarajan. Deep face recognition: A survey. In 2018
_31st SIBGRAPI conference on graphics, patterns and images (SIBGRAPI), pp. 471–478. IEEE,_
2018.

Takafumi Okuyama, Tad Gonsalves, and Jaychand Upadhay. Autonomous driving system based on
deep q learnig. In 2018 International Conference on Intelligent Autonomous Systems (ICoIAS),
pp. 201–205. IEEE, 2018.

Carlos Ramirez, Vladik Kreinovich, and Miguel Argaez. Why l1 is a good approximation to l0: A
geometric explanation. 7:203–207, 01 2013.

Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor attacks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 11957–
11965, 2020.

Shrutika Singh, Harshita Arya, and P Arun Kumar. Voice assistant for ubuntu implementation
using deep neural network. In Advanced Computing Technologies and Applications, pp. 11–20.
Springer, 2020.

Christian Szegedy, Alexander Toshev, and Dumitru Erhan. Deep neural networks for object detection. 2013.

Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks.
In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso[ciates, Inc., 2018. URL https://proceedings.neurips.cc/paper/2018/file/](https://proceedings.neurips.cc/paper/2018/file/280cf18baf4311c92aa5a042336587d3-Paper.pdf)
[280cf18baf4311c92aa5a042336587d3-Paper.pdf.](https://proceedings.neurips.cc/paper/2018/file/280cf18baf4311c92aa5a042336587d3-Paper.pdf)

Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Label-consistent backdoor attacks.
_arXiv preprint arXiv:1912.02771, 2019._

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 2019
_IEEE Symposium on Security and Privacy (SP), pp. 707–723. IEEE, 2019._

Ren Wang, Gaoyuan Zhang, Sijia Liu, Pin-Yu Chen, Jinjun Xiong, and Meng Wang. Practical
detection of trojan neural networks: Data-limited and data-free cases. In Proceedings of the
_European Conference on Computer Vision (ECCV), 2020._

Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and J¨urgen Schmidhuber.
Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949–980, 2014.

Yuanshun Yao, Huiying Li, Haitao Zheng, and Ben Y. Zhao. Latent backdoor attacks on deep
neural networks. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and
_Communications Security, CCS ’19, pp. 2041–2055, New York, NY, USA, 2019. Association_
for Computing Machinery. ISBN 9781450367479. doi: 10.1145/3319535.3354209. URL
[https://doi.org/10.1145/3319535.3354209.](https://doi.org/10.1145/3319535.3354209)

Tongqing Zhai, Yiming Li, Ziqi Zhang, Baoyuan Wu, Yong Jiang, and Shu-Tao Xia. Backdoor
attack against speaker verification. In ICASSP, 2021.


-----

APPENDIX

## Table of Contents

**A Other Backdoor Attacks** **14**
A.1 Dense Watermark Backdoor Attacks. . . . . . . . . . . . . . . . . . . . . . . . 14

A.2 Feature Space Backdoor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

**B** **Proofs** **14**
B.1 The proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

B.2 The proof of Lemma 2 – a theory on the linear case . . . . . . . . . . . . . . . . 15

B.3 Proof of Lemma 3 – An analysis for Kernel Regression . . . . . . . . . . . . . . 16

**C Monte Carlos gradient estimation** **18**

**D Algorithm for Computing Aggregated Global Adversarial Peak (GAP)** **19**

**E** **The detailed configurations for experimental datasets and triggers** **19**

**F** **The accuracy and attack success rate(ASR) for evaluated models** **19**

**G The amounts of evaluated models for various task and attack approaches** **20**

**H Details of visualization process** **20**

**I** **Detailed ROC for varous tasks and attack approaches** **20**

**J** **The comparison results between AEVA and NC, DL-TND** **20**

**K Experiments for different triggers** **21**
K.1 Evaluation on dynamic and sparse but not compact triggers . . . . . . . . . . . . 21

**L** **Results for impact of the number of images per labels.** **22**

**M The impact of the number of the labels for available images.** **23**

**N Multiple triggers within the single infected label scenarios** **23**

**O Potential adaptive backdoor attacks** **24**
O.1 Attacks with multiple target labels . . . . . . . . . . . . . . . . . . . . . . . . . 24

O.2 Attack with large triggers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24


-----

A OTHER BACKDOOR ATTACKS

A.1 DENSE WATERMARK BACKDOOR ATTACKS.

In short, we argue that low-magnitude dense backdoor attack(watermark) is not a practical attack
method and is less concerned compared to the threat model in our paper.

First, the low-magnitude attack is a special case of our formulation where the mask m is a continuous
value (here we use a to represent transparency). The low-magnitude problem can be formulated as:


mina,∆ _i_ _[ℓ][(][φ][((1][ −]_ _[a][)][x][i][, a][∆)][, y][t][) +][ λ][|][a][|]_

This formulation does not have discrete variables so its black-box optimization is an easier taskP
compared to our problem (where m is discrete).

Second, we will show theoretically that, in this scenario, every normal example is near the decision
boundary of the network, because due to Taylor expansion and the fact that a is a small value,

_φ((1 −_ _a)xi + a∆) = φ(xi + a(∆_ _−_ _xi)) ≈_ _φ(xi) + a(∆_ _−_ _xi)[⊺]∇xφ_

We know from xi to (1 − _a)xi + a∆, the function output label is changed. So every example xi is_
at the decision boundary of the function φ.

So the infected model is actually very sensitive to random noise and becomes ineffective in attacking
purposes.

To empirically support this claim, we conduct experiments on CIFAR-10 using ResNet-44. The
results are reported over average among ten different target labels. We select watermark triggers
randomly which occupy the entire image with 0.1 transparency rate (a). We here add noise which
fits uniform distribution with a low magnitude as 0.025 to each normal sample. The proportion of
normal samples misclassified by the infected label is shown below. We find that such dense lowmagnitude watermark triggers would make normal samples to be misclassified as the target label yt
via adding small random noise. Such observations can easily identify models infected with a dense
and low-magnitude watermark trigger.

-  Using a global watermark trigger, 67.8% of the normal samples are misclassified to other
labels(Infected label)

-  Using a 16x16 watermark trigger, 6.42% of the normal samples are misclassified to other
labels(Infected label)

-  Using a 4x4 watermark trigger leads to 1.41% of the normal samples misclassified

-  Using a 2x2 watermark trigger leads to 0.24% of the normal samples misclassified

-  Training with normal examples results in 0.2% of the normal samples misclassified.

A.2 FEATURE SPACE BACKDOOR

Feature space backdoor attack which employs a generative model to transfer the style of a normal
image into a trigger. However, the style transfer leads to significant visual changes which becomes
less stealthy. For physical attacks like surveillance cameras, this approach is hard to implement
because it requires changing the background as well. While our work is mostly focused on the input
space trigger, we believe the latent space problem is beyond our threat model as well as focused
problem and could be an interesting future work (for example, consider using an off-the-shelf style
transfer model to evaluate the model’s sensitivity towards different style effects.

B PROOFS

B.1 THE PROOF OF LEMMA 1

**Lemma 1.** Given a continuous differential function f defined on R[n] and vectors x, h ∈ R[n], there
exists a real value M _∂f/∂hi_ 1 _i_ _n such that_
_≥|_ _| ∀_ _≤_ _≤_

_|f_ (x + h) − _f_ (x)| ≤ _M_ _∥h∥1 ._ (8)


-----

**Proof of Lemma 1:** The first order Taylor expansion gives

_f_ (x + h) = f (x) + R(h) (9)

where R(h) is the Lagrange remainder, i.e.,


_∂f_ (x + ch)

_hi,_ for some c (0, 1). (10)
_∂xi_ _·_ _∈_


_R(h) =_

_i=1_

X

Let M _∂f_ (x)/∂xi **x, we have**
_≥|_ _| ∀_


_R(h)_ _M_ _hi_ (11)
_|_ _| ≤_ [=][ M] _[∥][h][∥][1][ .]_

1

X

So, we have
_|f_ (x + h) − _f_ (x)| ≤ _M_ _∥h∥1 ._ (12)

□

B.2 THE PROOF OF LEMMA 2 – A THEORY ON THE LINEAR CASE

We perform a theoretical study of linear models to shed light about our empirical finding. Here, we
restate Lemma 3 below for convenience.

**Lemma 2.** Given a linear model parameterized by θ optimized on No original training examples
and Nb backdoored training examples with an objective in Eq. 2 and a mean-squared-error loss, the
adversarial solution ˆµ optimized using Eq. 6 will be dominated by input dimensions corresponding
to backdoor mask m when Nb is large, i.e.,

(1 _m)_ _µˆ_ 1
lim _∥_ _−_ _⊙_ _∥_ = 0 . (13)
_Nb→∞_ _∥µˆ∥1_

**Proof of Lemma 2:** To ease the reading of notations, we use ( )a _b to represent matrix with a_

_·_ _×_
rows and b columns, respectively. Assuming φ(x; θ) = θ[⊺]x is a linear model whose output is a
floating number, and the loss function is ℓ[2], i.e., ℓ(x, y) = (x − _y)[2]. Then Eq. 2 becomes a linear_
regression problem and can be represented in the matrix form of least square, i.e.,

_F = ∥Xθ −_ _Y ∥[2]_ + ∥Xθ[ˆ] _−_ _Y[ˆ] ∥[2]_ (14)

where ˆxi = (1 _−_ _m)_ _⊙_ _x[′]i_ [+] _[m]_ _[⊙]_ [∆] [is an backdoor example converted from a normal example][ x]i[′] [and]
_yˆi = yt. X is the matrix composed of row vectors xi and Y is the matrix composed of row vectors_
_yi. The solution of this least square can be found by setting gradient to zero, such that_

_θˆ = (X_ [⊺]X + X[ˆ] [⊺]X[ˆ] )[−][1](X [⊺]Y + X[ˆ] [⊺]Y[ˆ] ) . (15)

It is known that a normal training without backdoors will lead to the pseudo-inverse solution θ =
(X [⊺]X)[−][1]X [⊺]Y . Without loss of generality, we assume the backdoor trigger occupies the last q
dimensions. And the first p dimensions are normal values, i.e., q = d − _p + 1 where d is the_
total number of dimensions. So, we can rewrite the input X = [X1:p, Xp:d] and the mask m =

[01×p, 11×(d−p+1)]. Let δ be the sub-vector of ∆ such that δ = ∆p+1:d, a q dimensional row
vector. Then we have _X[ˆ] = [X1:p, 1Nb_ 1δ] where Nb is the total number of backdoor examples.
_×_
Then,


_Xˆ_ [⊺]X[ˆ] = _X1:p⊺X1:p_ 0 _._
0 _Nbδ[⊺]δ_
 

Similarly, we find _Y[ˆ] = 1yt and assume zero mean of the input, i.e.,_ _xi = 0, then we have_

_Xˆ_ [⊺]Y[ˆ] = **0p×1** _._ [P]
_Nbytδ[⊺]_
 


(16)

(17)


-----

Whilebecomes Nb becomes larger, both _X[ˆ]_ [⊺]X[ˆ] and _X[ˆ]_ [⊺]Y[ˆ] increase significantly. When Nb →∞, Eq. 15
_θˆ_ ( X[ˆ] [⊺]X[ˆ] )[−][1]( X[ˆ] [⊺]Y[ˆ] ) = **0p×1** _._ (18)
_→_ _yt(δ[⊺]δ)[−][1]δ[⊺]_
 

In another word, we know the normalized values in the non-masked area of θ approach 0 such that

(1 _m)_ _θ_ 1
lim _∥_ _−_ _⊙_ [ˆ]∥ = 0 . (19)
_Nb→∞_ _∥θ[ˆ]∥1_

Now, let us look at the adversarial objective in Eq. 8, which is equivalent to


_G =_ _θ[⊺](x + µ)_ _yt_ _,_ (20)
_∥_ _−_ _∥[2]_


the gradient of which is


_µG = 2(θ[⊺](x + µ)_ _yt)θ ._ (21)
_∇_ _−_

Since 2(θ[⊺](x + _µ)_ _yt) is a scalar and each of the gradient updates is conducted by µ = µ_ + _λ_ _µG,_
_−_ _∇_
we know no matter how many gradient update steps are applied, µ, initialized at 0, always moves
in the exact same direction of θ, i.e., ˆµ ∥ _θ. In this case, ˆµ will also be dominant by the last q_
dimensions, or the dimensions corresponded to the mask m. In another word, we have

(1 _m)_ _µˆ_ 1
lim _∥_ _−_ _⊙_ _∥_ = 0 . (22)
_Nb→∞_ _∥µˆ∥1_

□

B.3 PROOF OF LEMMA 3 – AN ANALYSIS FOR KERNEL REGRESSION

**Lemma 3.** Suppose the training dataset consists of No original examples and Nb backdoor examples, i.i.d. sampled from uniform distribution and belonging to k classes. Each class contains
equally No/k normal examples. Let φ be a multivariate kernel regression with the objective in
Eq. 2, an RBF kernel K(·, ·) Then the adversarial solution ˆµ to Eq. 6 under cross-entropy loss
_ℓ(ˆy, y) = −_ [P]i _[y][i][ log ˆ]yi (y ∈{0, 1}[k]_ is the one-hot label vector) should satisfy that

lim _µ] = 0 ._ (23)
_Nb→∞_ [E][[(1][ −] _[m][)][ ⊙]_ [ˆ]

**Proof of Lemma 3:** The output of φ is a k dimensional vector. Let us assume φt(·) ∈ R be the
output corresponding to the target class t. We know the kernel regression solution is

_iN=1o_ _[K][(][·][, x][i][)][y][i,t][ +][ P]i[N]=1[b]_ _[K][(][·][,][ ˆ]xi)ˆyi,t_
_φt(_ ) = _No_ (24)

_·_ P _i=1_ _[K][(][·][, x][i][) +][ P]i[N]=1[b]_ _[K][(][·][,][ ˆ]xi)_

where ˆxi = (1 − _m) ⊙_ _xi + m ⊙_ ∆Pis the backdoored example and ˆyi is the corresponding onehot label (so we always have ˆyi,t = 1). Because the examples are evenly distributed, there are
_N/k examples labeled positive for class t. Without loss of generality, we assume yj,t = 1 when_
_j ∈_ [1, No/k] and yj,t = 0 otherwise. Then the regression solution becomes

_Ni=1o/k_ _K(_ _, xi) +_ _i=1_ _[K][(][·][,][ ˆ]xi)_
_φt(_ ) = _No_ _·_ (25)

_·_ P _i=1_ _[K][(][·][, x][i][) +][ P][P]i[N]=1[N][b][b]_ _[K][(][·][,][ ˆ]xi)_

Please note the regression above is derived with a mean squared loss. In the adversarial analysis Eq.P
6, we can use any alternative loss function. In this Lemma, we assume the loss in the adversarial
analysis is cross-entropy, which is a common choice. So, we have

_ℓ(φ(x), yt) =_ log φt(x) (26)
_−_

= − log(St + S[ˆ]) + log(S + S[ˆ]) (27)

where Si(·) = _yj_ =i _[K][(][·][, x][j][)][ and][ S][ =][ S][1][ +][ S][2][ +][ . . .][ +][ S][k][ and][ ˆ]S =_ _i=1_ _[K][(][·][,][ ˆ]xi)._

[P] [P][n][b]


-----

The derivative of loss w.r.t. x becomes


1 _∂(St + S[ˆ])_

_St + S[ˆ]_ _∂x_


_∂(S + S[ˆ])_

(28)
_∂x_


_∂ℓ(φ(x))_

=
_∂x_ _−_


_S + S[ˆ]_


By using gradient descent, ˆµ moves along the negative direction of the loss gradient, i.e.,


_∂(St + S[ˆ])_

_∂x_


_∂(S + S[ˆ])_

(29)
_∂x_


∆µ =


_St + S[ˆ]_


_S + S[ˆ]_


_S_
= _[∂]_ [ˆ]

_∂x_


+ _[∂S][t]_

_∂x_


_∂(S −_ _St)_ (30)

_∂x_


_St + S[ˆ]_


_S + S[ˆ]_


_St + S[ˆ]_


_S + S[ˆ]_


_S + S[ˆ]_


_S_
= a _[∂]_ [ˆ] (31)

_∂x_ [+][ a∂S]∂x[t] _∂x_

_[−]_ _[b∂][(][S][ −]_ _[S][t][)]_

where a, b are both positive scalar values. When Nb becomes large, the first term dominates the
gradient direction, i.e., ∆µ ∝ _[∂]∂xS[ˆ]_ [.]

Since we assume the kernel K(x, x[′]) = exp(−γ∥x − _x[′]∥[2]) is RBF, then we have its derivative_

_∂K(x, x[′])_

= 2γK(x, x[′])(x _x[′])_ (32)
_∂x_ _−_ _−_

Then we have


_Nb_

_i=1_

X

_Nb_


_∂S[ˆ]_

_∂x_ [=]


_∂K(x, ˆxi)_ (33)

_∂x_


= 2γK(x, ˆxi)(x _xˆi)_ (34)

_−_ _−_
_i=1_

X

Without loss of generality, we assume the mask m = [01×p, 11×(d−p+1)] (where first p dimensions
are 0s and the remaining are 1s). Then the first p dimensions of ˆxi are the same as those of xi, while
the remaining dimensions equivalent to those of ∆.

**Case 1: p + 1 ≤** _j ≤_ _d._ The j-th dimension of _[∂]∂xS[ˆ]_ [can be written as]

_∂S[ˆ]_ _Nb_

= 2γ _K(z + µ, ˆxi)_ (zj + µj _δj)_ (35)

_∂µ_ !j _−_ _i=1_ ! _−_

X

_δSo at convergence,j −_ E[zj]. _µj = δj −_ _zj for the last d −_ _p + 1 dimensions. The expectation is E[µj] =_

**Case 2: 1 ≤** _j ≤_ _p._ For the first p dimensions, we have
_∂S[ˆ]_ _Nb_

= 2γ _K(z + µ, ˆxi)(zj + µj_ _xij)_ (36)

_∂µ_ !j _−_ _i=1_ _−_

X


_Nb_

_i=1_ _e[−][γ][∥][z][+][µ][−]x[ˆ]i∥[2]_ (zj + µj − _xij) ._ (37)

X


= −2γ


Since µs + zs = δs = ˆxis = xis for p + 1 ≤ _s ≤_ _d, then we have_
_∂S[ˆ]_ _Nb_

1 _v_ _p[(][z][v][+][µ][v][−][x][iv][)][2]_

= 2γ _e[−][γ][ P]_ _≤_ _≤_ (zj + µj _xij)_ (38)

_∂µ_ !j _−_ _i=1_ _−_

X

Since Nb is large and ˆxi is i.i.d., then the summation can be approximated with integration, i.e.,
_∂S[ˆ]_

1 _v_ _p[(][z][v][+][µ][v][−][x][iv][)][2]_

= 2γ _e[−][γ][ P]_ _≤_ _≤_ (zj + µj _xj)dx ._ (39)

_∂µ_ !j _−_ Zx _−_


-----

When γ is large, the integration is the expectation of the offset to the center of a Gaussian distribution
(centered at zj + µj). Due to symmetry, the derivative becomes 0 for most of the µ locations. This
would be the common cases because a smaller γ means examples with longer distance can more
significantly influence the function output (which is not desired in a classifier with high accuracy).

Nonetheless, in rare cases when the γ becomes small, we can still find the stationary point of the

1 _v_ _p[(][z][v][+][µ][v][−][x][iv][)][2]_ _∂S[ˆ]_

derivative. Given the fact that e[−][γ][ P] _≤_ _≤_ is always positive, we know _∂µ_

_j_ [=]

is positive; and whendescent to find the optimaldistribution and the fact that0 =⇒ _zj + µj −_ _xj = 0 zj +. But it is impossible to reach. Again, utilizing symmetry of the normal ˆµ µ x. We can conclude that, at the convergence,j is i.i.d. uniform, we find when −_ E[xj] > 0, the derivative is negative. Since we use gradient zj + µj − _zE[jx +j] < µj 0 =, the derivative E[xj]. Then_
E[µj] = E[xj] − E[zj] = 0 because z is sampled from the same distribution of x.

To summarize,

0, 1 _j_ _p_
E[ˆµj] = _≤_ _≤_ (40)
_δj_ E[zj], _p < j_ _d_
 _−_ _≤_

Then we know, as Nb,
_→∞_ E[(1 − _m) ⊙_ _µ] →_ 0 (41)
□

C MONTE CARLOS GRADIENT ESTIMATION

Leveraging the Monte Carlo based estimation to craft target adversarial perturbations for the targeted
label yt typically requires x and xt, where xt is a legitimate sample satisfies f (xt) = yt. Firstly, x
is forced to approach the decision boundary of f ( ; θ) for the target label yt(φ(x, yt) 0.5), which

_·_ _→_
stimulates the efficiency and accuracy of gradient estimation. We can make φ(x, yt) 0.5 through
_→_
projection process:
_x_ (1 _α)x + αxt,_ (42)
_←_ _−_
_α ∈_ (0, 1) is a parameters for projection. During each gradient estimation procedure, α is set
through binary search (Chen et al., 2020a).

After that, we leverage Monte Carlo sampling to estimate _φx(x, yt), its procedure can be expressed_
_∇_
as:

[f]


_xφ(x, yt) = [1]_
_∇g_ _N_


_S(x + δµ[′]i[, y][t][)][µ]i[′]_ _[,]_ (43)
_i=0_

X


where {µ[′]}i[N]=0 [are perturbations][ i.i.d][ sampled from uniform distribution and][ δ][ is a small positive]
value representing the magnitude of perturbation. S is an indicator function such that

1, _f_ (x) = y,
(x, y) = (44)
_S_ 1, _f_ (x) = y.
 _−_ _̸_

To further eliminate the variance induced by Monte Carlo sampling, we can improve _φx(x, yt)_
_∇_
via:

[f]


_∇fφx(x, yt) = N[1]_


_N_

(x + δµ[′]i[, y][t][)][ −] [1]
_{S_ _N_
_i=0_

X


(x + δµ[′]i[, y][t][)][}][µ][′]i (45)
_S_
_i=0_

X


Using cosine angle to measure the similarity between _xφ(x, yt) and_ _xφ(x, yt), previous_
_∇_ _∇_
work (Chen et al., 2020a) have proved that:

[g]

lim _xφ(x, yt)],_ _xφ(x, yt)) = 1,_ (46)
_δ_ 0 _[cos][∠][(][E][[][ g]∇_ _∇_
_→_

thus a smaller δ (0.01) is selected for ensuring the efficacy of gradient estimation.


-----

Regarding the constraints on _µ_ 1, we further processed the estimated gradient via:
_||_ _||_

_xφ(x, yt)_
_xφ(x, yt)_ _∇_ _._ (47)
_∇_ _←_ _xφ(x, yt)_ 1

_||∇g_ _||_

g

We refer readers to (Chen et al., 2020a) for the complete algorithm for gradient estimation.[g]


D ALGORITHM FOR COMPUTING AGGREGATED GLOBAL ADVERSARIAL
PEAK (GAP)

**Algorithm 1 Aggregated Global Adversarial Peak (GAP)**

1: Input: Targeted DNN f (·; θ); label to be analyzed yt; legitimate input batches {Xi}i[n]=1 [evenly sampled]
across classes; the targeted input batch Xt;

2: Output: Aggregated GAP value R(yt);

3: Initialize R(yt) = 0
4: for i = 1, . . ., t − 1, t + 1, . . ., n do
5: **for j = 1, . . ., len(Xi) do**

6: Solve µ[i]j [= arg min][µ] _[ℓ][(][φ][(][x][ij]_ [+][ µ, y][t][;][ θ][)][, y][t][) +][ λ][∥][µ][∥][1] [using MC gradient estimation;]

7: **end for**

8: Find the GAP value for the current label: µ[i]max [= max]j,u,v _[µ]j,u,v[i]_ [;]

9: Aggregate GAP values over all labels: R(yt) = µ[i]max [+][ R][(][y]t[)][;]

10: end for
11: Return: R(yt)


E THE DETAILED CONFIGURATIONS FOR EXPERIMENTAL DATASETS AND
TRIGGERS

Task # labels Input size # training images

CIFAR-10 10 32x32 50000
CIFAR-100 100 32x32 50000
TinyImageNet 200 64x64 1000000

Table 2: Detailed information about dataset for each task.

The detailed information for each task is included in the Table. E. The data augmentation uti[lized for building each model is following https://keras.io/zh/examples/cifar10_](https://keras.io/zh/examples/cifar10_resnet/)
[resnet/.](https://keras.io/zh/examples/cifar10_resnet/)

F THE ACCURACY AND ATTACK SUCCESS RATE(ASR) FOR EVALUATED
MODELS

The accuracy and ASR for the evaluated models for each task in included in Table. 3.

Infected Model
Task Normal Model Accuracy
Accuracy ASR

CIFAR-10 _≥_ 90.04% _≥_ 97.7% _≥_ 92.31%

CIFAR-100 _≥_ 69.17% _≥_ 96.27% _≥_ 71.41%

TinyImageNet _≥_ 58.98% _≥_ 97.22% _≥_ 60.11%

Table 3: Accuracy and ASR for the evaluated models for each task


-----

G THE AMOUNTS OF EVALUATED MODELS FOR VARIOUS TASK AND ATTACK
APPROACHES

For each attack and task, we build 60 infected models and 60 uninfected models, respectively. Notably, the uninfected models for different attack approaches are randomly selected and different.
Each uninfected and infected model sets are built evenly upon ResNet-18, ResNet-44, ResNet-56,
DenseNet-33, DenseNet-58 these five models.

H DETAILS OF VISUALIZATION PROCESS

**Algorithm 2 Visualize µ**

1: Input: Targeted DNN f (·; θ); label to be analyzed yt; legitimate input batches {Xi}i[n]=1 [evenly sampled]
across classes; the targeted input batch Xt;

2: Initialize µ
3: Output: Normalized µ;

4: for i = 1, . . ., t − 1, t + 1, . . ., n do
5: **for j = 1, . . ., len(Xi) do**

6: Solve µ[i]j [= arg min][µ] _[ℓ][(][φ][(][x][ij]_ [+][ µ, y][t][;][ θ][)][, y][t][) +][ λ][∥][µ][∥][1] [using MC gradient estimation;]

7: **end for**

8: Find µ[i] owns the GAP value for the current label: µ[i] = arg maxµij _[µ]j,u,v[i]_ [;]

9: Aggregate µ[i] over all labels: µ = µ[i] + µ;

10: end for
11: Return: µ/||µ||1

I DETAILED ROC FOR VAROUS TASKS AND ATTACK APPROACHES


1.00 1.00 1.00

0.95 0.95 0.95

0.90 0.90 0.90

0.85 0.85 0.85

0.80 BadNets 0.80 BadNets 0.80 BadNets

Watermark Watermark Watermark

0.75 Label Consistent 0.75 Label Consistent 0.75 Label Consistent

Detection success rate for infected models Invisible Backdoor Detection success rate for infected models Invisible Backdoor Detection success rate for infected models Invisible Backdoor

0.70 0.70 0.70

0.0 0.1 0.2 0.3 0.4 0.5 0.0 0.1 0.2 0.3 0.4 0.5 0.0 0.1 0.2 0.3 0.4 0.5

Detection error rate for benign models Detection error rate for benign models Detection error rate for benign models


(a) CIFAR-10


(b) CIFAR-100


(c) TinyImageNet


Figure 10: The Receiver Operating Cure(ROC) for AEVA on CIFAR-10, CIFAR-100 and TinyImageNet tasks.

J THE COMPARISON RESULTS BETWEEN AEVA AND NC, DL-TND

|Attack|Method|Detection Results|
|---|---|---|
|||AUROC ACC|
|BadNets|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.976 95.0% 0.999 99.2% 0.930 91.5%|
|Watermark|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.983 95.8% 1 100% 0.968 94.4%|
|Label Consistent|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.961 94.2% 0.992 98.3% 0.968 94.4%|
|Invisible Attack|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.980 95.8% 0.999 99.1% 0.970 94.4%|



Table 4: The two metrics for backdoor detection on the CIFAR-10 task using three backdoor detection methods: NC, DL-TND, and AEVA. Higher values in AUROC and ACC are better.


-----

|Attack|Method|Detection Results|
|---|---|---|
|||AUROC ACC|
|BadNets|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.978 95.8% 0.999 99.1% 0.973 95.4%|
|Watermark|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.961 94.2% 1 100% 0.992 98.8%|
|Label Consistent|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.964 94.2% 0.999 99.1% 0.981 96.8%|
|Invisible Attack|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.989 97.5% 1 100% 0.984 97.1%|


Table 5: The two metrics for backdoor detection on the CIFAR-100 task using three backdoor
detection methods: NC, DL-TND, and AEVA. Higher values in AUROC and ACC are better.

|Attack|Method|Detection Results|
|---|---|---|
|||AUROC ACC|
|BadNets|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.956 91.6% 0.999 99.1% 0.988 97.9%|
|Watermark|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.972 94.2% 1 100% 0.999 99.6%|
|Label Consistent|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.983 96.7% 0.999 99.1% 0.983 96.7%|
|Invisible Attack|NC (Wang et al., 2019) DL-TND (Wang et al., 2020) AEVA (Ours)|0.982 96.7% 0.999 99.1% 0.986 97.9%|



Table 6: The two metrics for backdoor detection on the Tiny Imagenet task using three backdoor
detection methods: NC, DL-TND, and AEVA. Higher values in AUROC and ACC are better. Each
approach are evaluated using 60 infected and 60 benign models.

K EXPERIMENTS FOR DIFFERENT TRIGGERS

K.1 EVALUATION ON DYNAMIC AND SPARSE BUT NOT COMPACT TRIGGERS

We evaluate AEVA for CIFAR-10 task under the dynamic and non-compact triggers scenario. We
randomly generate three non-compact triggers(shown in Figure. 11) and perform backdoor attacks
against a randomly selected label using these dynamic triggers. We test AEVA using 10 different
DNN models, which are evenly built upon ResNet-18, ResNet-44, ResNet-56, DenseNet-33 and
DenseNet-58.


0 0 0

5 5 5

10 10 10

15 15 15

20 20 20

25 25 25

30 30 30

0 5 10 15 20 25 30 0 5 10 15 20 25 30 0 5 10 15 20 25 30


(a) Dynamic trigger I


(b) Dynamic trigger II

Figure 11: Dynamic Triggers


(c) Dynamic trigger III


-----

AEVA successfully identify all models embedded with dynamic backdoors and the corresponding
infected labels. The detailed Aggregated Global Adversarial Peak(AGAP) values and Anomaly
Index given by the MAD outlier detection for infected and uninfected labels are shown in Fig. 12.
We find AEVA predicts all backdoored models as infected with Anomaly Index ≥ 4. Such results
demonstrate that AEVA is resilient to dynamic and sparse but not compact triggers.


14

0.30

12

0.25

10

0.20 8

0.15 6

AGAP

4

0.10 Anomaly Index

2

0.05

0

0.00 2

Infected Uninfected Infected Uninfected

Labels Labels


(a) AGAP


(b) Anamoly Index


Figure 12: AGAP and Anomaly Index for infected and uninfected labels


We also evaluate AEVA on three different triggers with different shapes, which are shown in Fig. 13.
For each trigger, we build 30 models on TinyImageNet. Each set of models are evenly built upon
ResNet-18, ResNet-44, ResNet-56, DenseNet-33, DenseNet-58 these architectures. The results are
shown in Table. 7.

Attack Approach ACC


Trigger I 93.3%
Trigger II 93.3%
Trigger III 90.0%

Table 7: Results for other different triggers



0 0 0

10 10 10

20 20 20

30 30 30

40 40 40

50 50 50

60 60 60

0 10 20 30 40 50 60 0 10 20 30 40 50 60 0 10 20 30 40 50 60

(a) Trigger I


10 20 30 40 50 60

(b) Trigger II


(c) Trigger III


Figure 13: Triggers with different shapes


L RESULTS FOR IMPACT OF THE NUMBER OF IMAGES PER LABELS.

We further explore how many samples for each label are required by AEVA to be effective. We test
AEVA on TinyImageNet and the experimental configurations are consistent with Sec.4.1(i.e., 240


-----

infected and 240 benign models). Our results are illustrated in the Fig. 14, which plots the metrics
against the number of samples per class. We find that our approach requires more samples (32) for
each class to achieve optimal performance.

1.0

0.8

0.6

ACC

0.4

0.2

0.0

0 10 20 30 40

# of samples per class


Figure 14: The impact for the number of samples for each class

M THE IMPACT OF THE NUMBER OF THE LABELS FOR AVAILABLE IMAGES.

Since our approach aims to detect backdoors in the black-box setting, a realistic scenario is that while
determining if a specific label is infected, the clean data from all other labels may be unavailable
to the defender. So, in this section, we investigate the impact of the number of labels for which
clean data is available for our approach. We test our approach on TinyImageNet using 60 models
infected with BadNets (4 × 4 squares) following the configurations of Sec. 4.2. We vary the number
of uninfected labels for available samples between [1, 200], randomly sampled from the 200 labels
available in the TingImageNet dataset. Figure. 15 illustrates our results by plotting the metrics
against the number of available labels. We observe that even with eight available labels, our approach
can still detect backdoors in most cases, i.e., with merely 4% of the labels being available, our
approach is still viable. This study exhibits our approach’s practicality, which can work in the blackbox setting and on relatively small available data. Notably, with fewer labels AEVA will always
correctly tag the uninfected models. This is because few labels will cause the anomaly index low
thus resilient to uninfected models.

0.0

|1.0 0.8 0.6 ACC 0.4 0.2|Col2|
|---|---|


10[0] 10[1] 10[2] 10[3]

Available Labels

Figure 15: The impact for the number of samples for each class

N MULTIPLE TRIGGERS WITHIN THE SINGLE INFECTED LABEL SCENARIOS

We also investigate the impact caused by multiple triggers within the single infected label. We
here choose different 4 × 4 squares located at different places as the triggers implemented following


-----

BadNets. We randomly select a label as the infected label. We built 60 infected models with different
architectures(i.e., ResNet-18, ResNet-44, ResNet-56, DenseNet-33, DenseNet-58). The results for
TinyImageNet are shown in Table. 8. Notably, for TinyImageNet, injecting too many triggers (≥ 4)
in the single label would cause the target model’s accuracy drop (i.e., ≥ 3.7%), which is inconsistent
with the threat model for backdoor attacks (Gu et al., 2019; Chen et al., 2017; Liu et al., 2018).

As seen in Table. 8, our approach can still perform effective when injecting two 4 × 4 triggers in
the single infected label. However, when the number of injected triggers becomes more than 2, our
approach becomes less effective. This should be caused by that multiple-triggers would reduce the
singularity properties for the adversarial perturbations. To address this issue, we select the sum of
the largest five points as the µmax instead. The results are shown in Table. 9. By selecting more
points to calculate the µmax, AEVA can still perform effective under the multiple triggers within the
single label scenarios and have no impact on the detection accuracy for uninfected models.

Attack Approach ACC

Two infected triggers 81.7%
Three infected triggers 48.3%

Table 8: Results for multiple triggers within the single infected label

Attack Approach ACC

Two infected triggers 93.3%
Three infected triggers 88.3%

Table 9: Results II for multiple triggers within the single infected label

O POTENTIAL ADAPTIVE BACKDOOR ATTACKS

We here consider two potential backdoor attacks which can bypass AEVA.

O.1 ATTACKS WITH MULTIPLE TARGET LABELS

Since AEVA is sensitive to the number of infected labels, the attacker can infect multiple labels with
different backdoor triggers. Indeed, making multiple labels (i.e.≥ 30%;) infected will make the
anomaly indexes produced by the MAD detector significantly drop. However, such attack can only
be successfully implemented for some small datasets which own a few labels(e.g., CIFAR-10, etc).
Reported by (Wang et al., 2019), the state-of-the-art model (DeepID) for Youtube Face dataset can
not maintain the average attack success rate and model accuracy at the same time when more than
15.6% labels are infected. In another word, when multiple labels are infected, the infected model’s
accuracy is likely to get worse if the attacker wants to keep attack success rate. So too many infected
labels will reduce the stealth of the attack. We conducted experiments on TinyImageNet, which
reveals that when over 14 labels are infected with different triggers, the model accuracy (ResNet-44
and DenseNet-58) decreases to ≤ 57.61% (around 3% lower than a normal model) when preserving
the attack effectiveness (ASR ≥ 97.12%) for each infected label.

O.2 ATTACK WITH LARGE TRIGGERS

Another potential adaptive backdoor attack is that the attacker would implement a dense backdoor
trigger which would alleviate the singularity phenomenon. As we claim in Section 4.3, a dense backdoor trigger would appear visually-distinguishable to the human beings which perform less stealthy,
that is also reported by Neural Cleanse (Wang et al., 2019). Indeed, there exists an interesting exceptional watermark attacks. However, we empirically prove that such dense watermark attack (Chen
et al., 2017) would make infected DNNs non-robust which would make the inputs sensitive to the
random noise. The details are included in Appendix A.


-----

