AEVA: Black-box Backdoor Detection Using Adversarial Extreme Value Analysis
Authors: Junfeng Guo
Ang Li
Cong Liu
Venue: ICLR 2022 Poster (2022)

Abstract: Deep neural networks (DNNs) are proved to be vulnerable against backdoor attacks. A backdoor could be embedded in the target DNNs through injecting a backdoor trigger into the training examples,  which can cause the target DNNs misclassify an input attached with the backdoor trigger. Recent 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 de-ployed DNNs. We address the black-box hard-label backdoor detection problem where the DNN is a 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 backdoor-infected example, which we call the adversarial singularity phenomenon. Based on this observation, 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 on the adversarial map, computed from the monte-carlo gradient estimation due to the black-box hard-label constraint. Evidenced by extensive experiments across three popular tasks and backdoor attacks, our approach is shown effective in detecting backdoor attacks under the black-box hard-label scenarios

Published as a conference paper at ICLR 2022
AEVA: BLACK-BOX BACKDOOR DETECTION USING ADVERSARIAL EXTREME VALUE ANALYSIS
Junfeng Guo, Ang Li, Cong Liu Department of Computer Science
The University of Texas Dallas (ixg17001 6, angli, i, cong]eut.dal @ut 1aw.laas.... edu
ABSTRACT
Deep neural networks (DNNs) are proved to be vulnerable against backdoor at- tacks. backdoor is often embedded the target DNNs through injecting back- door trigger into training examples, which can cause the target DNNs misclassify an input attached with the backdoor trigger. Existing backdoor detection meth- ods 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 prob- lem from the optimization perspective and show that the objective of backdoor de- tection is bounded by an adversarial objective. Further theoretical and empirical studies reveal that this adversarial objective leads to solution with highly skewed distribution; singularity often observed in the adversarial map of backdoor- infected 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 es- timation. 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.
INTRODUCTION
Deep Neural Networks (DNNs) have pervasively been used in wide range of applications such
as facial recognition (Masi et al. 2018), object detection (Szegedy et al. 2013 Li et al. 2022), au- tonomous driving (Okuyama al. 2018). and home assistants (Singh In the meanwhile, DNNs become increasingly complex. Training state-of-the-an models requires enormous data and expensive computation. To address this problem, vendors and developers start 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.
2020 Zhai al. [021).
Since the dawn of software distribution, there has been ongoing war between publishers sneaking malicious code and backdoors in their software and security persomnel detecting them. Recent stud- ies 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 specific pattern (called trojan trigger) models containing backdoors 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 al. 2021 Kolouri et al. 2020). the predicted confidence score of each class (Dong et al. 2001). Unfortunately, is costly and often impractical for the defender access the original poisoned training dataset. In situations when DNNs

---

Published as a conference paper at ICLR 2022
Blackbox to the model UserdDefender
Third Party Al Deviee
Model User'Defender
Toput W/Trigger
Label
Query
Tnpur W.O Trigger
Label Dog
Edge Device
Label
Deploy
Figure I: An illustration of the black-box hard-label backdoors.
deployed in safety-critical platforms Fowers et al., 2018 Okuyama et al. in cloud services (Fowers et al., 2018 Chen al. 2019c). is also impractical access either their parameters or the predicted confidence score of each class (Chen et al. 2019c 2020b).
2018 Li ct al. 2021b) or
We present the black-box hard-label backdoor detection problem where the DNN is fully black- box and only its final output label is accessible (Fig. D. Detecting backdoor-infecter 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 al.l| 2019b Liu et al. 2019) becomes impossible solve due 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-bor hard- label setup. Further theoretical and empirical studies reveal that this adversarial objective leads to a solution with highly skewed distribution; a singularity likely to be observed in the adversarial map of a backdoor-infected example, which we call the adversarial singularity phenomenon.
Liu
Based on these findings, we propose the adversarial extreme value analysis (AEVA) algorithm to detect backdoors black-box neural networks. The AEVA algorithm is based on extreme value analysis (Leadbetter) [191] 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 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 high success rate. Following previous works (Dong et al. 2021 Wang al.) 2019), the Median Absolute Deviation (MAD) algorithm implemented on top of the GAP values to test whether a DNN is backdoor-infeche
Through extensive experiments across three popular tasks and state-of -ft-----trht-r---ee backdoor techniques, AEVA is proved to be effective in detecting backdoor attacks under the black-bos hard-label scenar- ios. The results show that AEVA can efficiently detect packdoor-infecten DNNs, yielding an overall detection accuracy 2 1% across various tasks, DNN models and triggers. Rather interestingly, when comparing to two state-of-art white-box box backdoor detection methods, AEVA yields compara- ble performance, even though AEVA is black-box method with limited access to information.
We summarize our contributions as below] !
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 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 backdoor-infecte neural network is likely to suffer from a highly skewed distribution.
3. We propose 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 Monte Carlo gradient estimation.
2

---

Published as a conference paper at ICLR 2022
4. We evaluate AEVA on three widely-adopted tasks with different backdoor trigger imple- mentations and complex black-box attack variants. All results suggest that AEVA is effec- tive in black-box hard-label backdoor detection.
1.1 RELATED WORK
Backdoor attacks. BadNets (Gu et al. 2019) is probably the first work backdoor attacks against DNNs, which causes target misclassification to DNNs through injecting a small trigger into some training samples and mis- mis-labeling these samples with 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 ef al. (Chen et al., (017)) further propose to perform back- door attacks under a rather weak threat model where the attacker cannot access the target model and training dataset. Most recently, set of backdoor attacks (Ji al. 2018 Liu al. 2020 Saha 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 ahysical-world, transfer learning, etc.
Backdoor detection (white-box), A few works (Chen et al. 2019a; Tran et al., 2018) are proposed detect the backdoor samples within the training dataset. Chen et al. (2019a) propose neuron activation clustering approach to identify backdoor samples through clustering the training data based on the neuron activation of the target DNN. |Taa 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-infeeter DNNs (Liu et al. 2019; Wang et al., 2019). ABS (Liu et al. (019) identifies the infected DNNs by seeking compromised neurons representing the features of backdoor triggers. Neural Cleanse (Wang et al. (019)) conducts the reverse engineering to restore the trigger through solving optimization problem. Recent works (Chen et al.) [019b] 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 model parameters 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 separate generator (Goodfellow et al. 2014). So, strictly speaking, their method is not "black-box" which is also revealed by (Dong et al. 202T. To the best of our knowledge, Dong al. (202T) the only existing work on detecting bockdoor-infected DNNs in the black-box settings. However, their method requires the predictive confidence score for each input to perform the NES algorithm (Wier- stra 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 accessible. Both model parameters and training examples 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 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 validation set (40 images for each class). Therefore, the defender only query the target DNNs to obtain its final decisions. The defender's 's goal to identify whether the target DNNs is infected and which label is infected.
normal specific label without affecting the model's accuracy
2.2 PROBLEM DEFINITION
Consistent with prior studies Dong et al. 202 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
3

---

Published as a conference paper at ICLR 2022
imput R", the modified input containing the backdoor trigger can be formulated as:
f = b(x) = (1 m) ① m O A,
where A IR represents the backdoor trigger and represents the element-wise product. {0, 1 is a binary mask that ensures the position and magnitude of the backdoor trigger. Typically, [mmlla ought be very small to ensure the suuallyiindistinguiihbblllyy between è and z.
We define f(=:0) ) as the target DNN with parameters 0, which is a function that maps the input x label y. (xx, yy; 0) E [0, 1] is defined as the probability that æ is classified as y by f(; The argument 0 is sometimes omitted in favor of simplicity. For f to mislabel & as the target label Vt, there are two possible reasons: the backdoored training data either contains the same trigger but mislabeled as Yr. or contains similar features as the normal inputs (not belonging to ys, but visually similar to yr) and labeled as yt-
No (6 (.)) + Σ y:: 81:)8.)
No
i -arg min
(2)
where there are No original training examples and N₂ backdoor examples. E(-) represents the cross- entropy loss function; Ia and Yi represent the training sample and its corresponding ground-truth label, respectively. In the inference phase, the target DNN will predict each as the target label V/s
which can be formulated as: (() Y/- Prior works (Dong al. 2021 Wang al. 2019 Chen
jet al.] (201bb) seek to reveal the existence of a backdoor through investigating whether there exists a backdoor trigger with minimal ||mi| that can cause misclassification to certain label.
We mainly study the sparse mask since it is widely used in previous works (Wang et al. 2020 Dong al. 2021; Chen al., 2019b Guo al. 2020 Wang al., 2019: Gu 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 becomes near the decision boundary of function ø. It is revealed by Taylor the- orem, ( = ss(1 m)r: + mA) = oxx; + m(A x;)) Re ((x;) + m(s x;) TVz0 And the function output label changes dramatically from (xx;) to @(ū;), so the gradient V has to have large magnitude, which results non-robust model sensitive to subtle input change. Such mod- els become impractical because small random perturbation on the input can lead to significantly
different model output. More details with empirical study can be found in the Appendix
2.3 BLACK-BIL -BX BACKDOOR DETECTION AND ITS CHALLENGES
Most previous works (Wang et al. 2019 Dong et al. 2021 Chen et al. 2019b) focus on reverse- engineering the backdoor trigger for each target label ye using the following optimization:
arg min Σ E(0((1 m) @ x. A,A
A y.), vr) + B1 m/|m
where is the balancing parameter. Unfortunately, solving Eq. 3 is notoriously hard in the black- box hard-label setting since 0 is unknown. Additional difficulty comes with the fact that an effective zero-th order gradient estimation requires each example 2; superimposed with the trigger to be close to the decision boundary of ye (Chen et al.] 2020a Cheng et al. 2020 Li et al. 2020). However, such condition is hard to achieve 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. 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 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 blx setting.
4

---

Published as a conference paper at ICLR 2022
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. with the objective in adversarial attacks. To begin with, we first transform the backdoor masking equation (1 m) ?
I; + m @ A = + l m @ Z4, where μ m @ A. Following this, the optimization in Eq.
converts to minimizing the following term:
1 N N
F
Σ
((6( + m @ Zz. yc: 0),
(4)
We further introduce important result from the Multivariate Taylor Theorem below. Lemma 1. Given continuous differentiable function f(.) defined on R. and vectors x, h E IR".
for any M 2 (0f/Oha) V1 I i S n, we have [f(x + h) f(x) & M|]h[|
The lemma can be proved using the Lagrange Remainder. Please refer to the Appendix B.I for detailed proof. According to the lemma, we have
N Σ
N Cllm @ x:llı S ClImm = C'llello
F
Mols, + n1 p1; 0) S
(5)
where the latter inequality holds because each example x; S 1 is bounded and the last equality ||m]]] = ||m@ allo |иo] holds because m a binary mask. Then, we can see that the adversarial objective is an upper bound of the objective in backdoor detection, ie., F S $ Ei [()(2;++1) Me)+
C'Ilollo- Instead of optimizing the original Eq. we here propose to minimize the e'-regularized objective. While e enforces the sparsity of the solution, optimizing it is NP-hard. In practice, is
replaced with an e' -oor an envelope of the objective (Ramirez et al. 2013 Donoho 2006
i arg min Σ ((p(z + H. ve; 0); |||||1
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
natural and important question here is what the adversarial perturbation P 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 linear model to shed light on the intuition of our approach.
Lemma 2. Given a linear model parameterized by 0 optimized on No original training examples and N₂ backdoored training examples with an objective in Eg. [ and geeun-suuard-erro loss, the adversarial solution j optimized using Eq. 6 will be dominated by input dimensions corresponding
to backdoor mask when N₂ is large, i.e., lim -oo [l m) م|11/||A|| = 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 occupied the mask area. Since the mask m is usually sparse, it is reasonable to expect highly skewed distribution in the adversarial map já.
We suspect that such skewed distributions might also occur in the adversarial map of a deep neural network. While a thorough analysis DNN is hard, recent studies in Neural Tangent Kernel (NTK) (Jacot et al. 2018) have shown that 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 N, backdoor exam- ples, i.i.d. sampled from uniform distribution and belonging k classes. Let o be 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 lim lim No-000 B[(1 m) @ j
5

---

Published as a conference paper at ICLR 2022
0523
023
10
0.00
11
0.005
20
(a) Backdoor map
(b) f for the infected label
(c) f for the uninfected label
Figure 2: The distribution of values in the normalized adversarial perturbation z for the infected (b) and uninfected (c) labels, using a backdoor map in (a). 2, y axes represent the image space; axis represents the absolute value of the normalized y corresponding to each pixel location.
The proof can be found in Appendix B.3 The lemma reveals a similar result 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 validate our intuition. Following previous works (Dong et al., [202]: 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 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. 66) generated for both infected and uninfected labels. The perturbations are normalized to a heat map as AA/||Aí| and shown Fig. 2 high concentration of mass is clearly observed from the infected case in Figure[((b) We call it adversarial singularity phenomenon. This motivates our adversarial extreme value analysis (AEVA) method.
3.3 ADVERSARIAL EXTREME VALUE ANALYSTS
natural way to identify singularity is to look at the peak value of the distribution. We define the adversarial peak Pmaz max j4j for an adversarial perturbation μ. To gain a statistical understand- ing of the relationship between adversarial peak and backdoor at- tacks, We randomly sample 1000 normalized for the uninfected and infected labels and plot the distribution of Pmaz in Fig. The experimental setup is consistent with the empirical study in Sec. 3.2 We notice from the figure that Pmaz of the infected labels reaches a much larger range compared to that of uninfected la- bels. However, they still overlap: around 47% infected Amaz stays within the uninfected range (the area with both blue and orange bars). This result suggests that
025
Infected
Proportion
0.3
0.10
Figure 3: The distributions of ad- versarial peak joaaz for infected labels and uninfected labels.
the adversarial singularity phenomenon does not always occur in backdoor-inferd sonable because some samples are inherently vulnerable to adversarial attacks and their adversarial perturbations have similar properties backdoors, which reduces the chance of singularity.
DNNs. It rea-
Now, we know if we define a threshold as the maximum value of the uninfected labels, the probability of backdoor-infected Jmmz being smaller than T is 0.47, i.e., P(Jmmax 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 sample k examples of Pmma for the same label,
P(max (finas Pmaas..... ) < T) (P(Umar < <
(7)
Here we name the maximum value over all the & adversarial peaks as the Global Adversarial Peak (GAP). We vary the choice of & in Figure A and lower than T is diminishing. For example, if we take = 6, then P(GAP < T) = 0.47 0.01 and the success rate of identifying backdoor-infecter label is 99%. Please be advised that, given
that the chance of GAP value being

---

Published as a conference paper at ICLR 2022
the long-tail distribution of the infected Mmazz. this threshold T is not sensitive and can be made even larger to safe to include all uninfected labels. However, for larger T values, we need a larger &s to ensure desired success rate.
3.4 BLACK-BOX OPTIMIZATION VIA GRADIENT ESTIMATION
After investigating the unique properties of backdoor-infecter DNNs in the white-box settings, we here illustrate how to ex- ploit such properties under a rather restricted scenario as we con- sider. In the white-box settings, the free access can enable us to compute the (z M1) accurately, resulting in μ with min- imum ||인| through optimizing Eq. 6 Regarding the black-box settings, we propose to leverage the zero-order gradient estima- tion technique (Fu & Hu 2012) to address the challenge for calcu- lating V ,z yt). We choose Monte Carlo based method (Fu & Hu 2012) for obtaining the estimated gradient VØz (xr, yr), which sends several inputs and utilizes the corresponding outputs to esti- mate the gradient. More details about gradient estimation can be
0.3
307
10
Sample chresholding
Figure 4: The proportion of in- fected lahels whose max (prnez } larger than that of uninfected ones.
found in Appendix
3.5 FINAL ALGORITIM
Imput
Dog
Gradient Estimation
Advenariil Perturbation
Aggregated
0.2701
7,6219
Mallicous
(
Anomalty
Ladex
Black-bar Backdoored (Trigger: i)
0,1494
1,0133
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 described in Algorithm [ Our approach requires a batch of legitimate samples X; for each class i. For each label ye to be analyzed, the algorithm will tell whether Ye is backdoor-infecter collect a batch of legitimate samples belonging to Yt. denoted as X₁ with the same batch size as that of X,. Then, we leverage X, to make each sample within every (X.) to approach the decision boundary of yı- This is computed by optimizing ji from Eq. Gssin Monte Carlo gradient estimation. The adversarial peak Mmma is then computed for each example. The global adversarial
We treat Y/ as the targeted label. Then we
peak (GAP) is aggregated over all labels. After calculating the GAP value R(y:) for each class following previous work (Wang et al.) 22199] Dong et al. 2021). we implement Median Absolute Deviation (MAD) to detect the outliers among {R[v:) F Specifically,
MAD to calculate the anomalous index for each Ryys) by assuming {R( D fits Gaussian distribution. The outlier is then detected by thresholding the anomaly index.
4 EXPERIMENTS
4.1 SETTINGS
Datasets. We evaluate our approach CIFAR-I0, 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 backdoor- infected model and inject sufficient poisoned samples to ensure the attack success rate > 98%. More details can be found in the Appendix.

---

Published as a conference paper at ICLR 2022
Uninfected
BadNees
Watermark
Label Consistent
Invisible
Figure 6: The visualization of adversarial perturbation á for infected labels with different backdoor attacks on
ImnyemageNet. For each attack, we show the trigger (left), f map (middle) and á distribution in 3D (right).
Delection Accuracy (ACC)
BadNets
Watermark
Label Consistent Invisible Attack
Tofal(Infected)
Benign
CIFAR-10
86.7%
93.3%
93.3%
93.3%
91.7%
95.4%
CIFAR-100
93.3%
100%
96.7%
96.7%
96. 7%
97.5%
Tanyem
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 al.) 2019) and Invisible At- tack (Li et al. (021a). For BadNets and Watermark, the triggers are x 4 squares. The transparency ratio for Watermark attack is 0.1. For label-consistent and invisible attacks, we use the default less- visible 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 al. 2019) and DL-TND (Wang al. 2020 For each task, we use 200 samples for the gradient estimation, and the batch size for each {X;) set to 40 Algorithm 1
Outlier detection. To accurately identify the anomalous R(y;)) among (R(1:));= we assume the scores fit to normal distribution and apply a constant estimator (1.4826) to normalize the computed anomaly index similar to (Wang et al. (019). We set the threshold value 4 for 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) 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 7 for anomaly index; (b) Detection Accuracy (ACC) - The proportion of models are cor- rectly identified. Regarding infected models, they correctly identified and only 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. which demonstrates that AEVA can accurately and distinguish the uninfected and infected labels and reveal the singularity phenomena of backdoor triggers.
Table presents the overall results. AEVA can accurately detect the infected label with ACC 2 86.7% across all three tasks and various trigger settings. We compare our approach with ex- isting white-box detection approaches including Neural Cleanse (NC) (Wang et al. 2019) and DL-
TND (Wang et al. 2020). The comparison results over all infected and benign models are shown in
We implement NC. Wang al. 2019 and DL WWng et al. 2020 com http:///.....a......eaaaee////ep
com/ hom/bolle www.ww/wwwwwwgnnnnoeneee
8

---

Published as a conference paper at ICLR 2022
1.00
1.00
Delection success rale for infected models
Detection success infected
Dotection
for use
NC box
NC/While
220
NO/Whil bol) Dr (aatAW
DI IeVTTWW
D1: TNDDWWhte-coo
AEW
AEM
NEW
Detection arror benign models
Dotection
Detection for benign models
banign models
(a) CIFAR-I0
(b) CIFAR-100
(c) ImageateNet
Figure 7: The Receiver Operating Cure(ROC) for NC, DL-TND and AEVA CIFAR-10, CIFAR- 100 and TinyImageNe tasks. AEVA black-box box while the other two methods are white-box.
Fig. More results can be found Appendix | The results suggest that AEVA achieves compara- ble 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 TinylmageNet with different trigger sizes for BadNets and Watermark attacks. For each trigger size and attack method, build 60 infected models with various architectures following the configurations Sec. 4.2 Fig. shows that AEVA remains effective when trigger size is less than 14 x 14 with ACC > 71.7%. For large triggers, AEVA cannot identify the infected label since the singularity property allevi- ated. This is consistent with our theoretical analysis. Even though large trigger attacks can bypass AEVA, they are either visually- distinguishable or leading to non-robust model sensitive to input change, making less stealthy and impractical.
1.0
19410
Trigger
Figure 8: The impact of trigger size detection accuracy.
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 10 to evaluate AEVA. We randomly select in- fected labels, and we inject a x 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 al. 22200] 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.
Buffeda Wearneh
06
The number of inrected labels
Figure 9: The impact of infected 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 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 the adversarial map, computed from the monte-carlo gradient estimation due the black-bor box hard-label constraint. Extensive experiments demonstrate the efficacy AEVA across a set of popular tasks and state-of-the-art backdoor attacks.

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work aims at providing neural network practitioners additional protection against backdoor attacks. We believe our work could contribute positively 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 built upon comprehensive theoretical results and clear motivations. We believe the pro- posed method can be reproduced according to the content in the paper, e.g., Algorithm [ In addi- tion, we have released the implementation of AEVA in https:://ithhb.. htt.:/haabbcooo///ueeeeooooooooo Baw.aalleecooo--ccco----eeeeeeee
REFERENCES
Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig. Benjamin Edwards, Taesung Lee, lan Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by activation clustering. In SafeAI@AAAl 2019a. URL http:://cutt org org/Vol~ /ooVVol11111//1111
paper_18.pd
Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. Deepinspect: A black-box trojan detection and mitigation framework for deep neural networks. In ICCA, pp. 4658-4664, 2019b.
Jianbo Chen, Michael I Jordan, and Martin J Wainwright. Hopskipjumpattack: A query-efficient decision-basee 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 tacks. In Proceedings the 1t 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
brg/abs/1112.c 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 reld-prrgrammable gate arrays, pp. 73-82, 2019c.
Minhao Cheng, Simranjit Singh, Patrick H. Chen, Pin- Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Sign- opt: A query-efficient hard-label adversarial attack. In International Conference Learning Representations, 2020. URL htttps://operreeeeee...t.. net. wtw.rr/eooouur----BACCCCC
Yinpeng Dong, Xiao Yang, Zhijie Deng, Tianyu Pang, Zihao Xiao, Hang Su, and Jun Zhu. Black- box 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.I. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289-1306, 2006. doi: 10.1109/TT:2200.8875555
Jeremy Fowers, Kalin Ovtcharov, Michael Papamichael, Todd Massengill, Ming Liu, Daniel Lo, Shlomi Alkalay, Michael Haselman, Logan Adams, Mahdi Ghandi, et al. A configurable cloud- scale 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 MaanQQang Hu. Conditional Monte Carlo: Gradient estimation and optimization applications, volume 392. Springer Science & Business Media, 2012.
10

---

Published as a conference paper at ICLR 2022
M Ivette Gomes and Armelle Guillou. Extreme value theory and statistics of univariate extremes:
review. International statistical review, 83(2):263 292, 2015.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sher- jil 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 htttss://proceed wew.eeeiiiinnnsnuiineoeee.. cc//paperr2014//11ee 5ca3e9b122
Tianyu Gu, Kang Liu, Brendan attacks on deep neural networks. IEEE Access, pp. 47230-47244, 2019. doi: 10.1109/ACCESS. 1019.2909068.
and Siddharth Garg. Badnets: Evaluating backdooring
Wenbo Guo, Lun Wang, Yan Xu, Xinyu Xing, Min Du, and Dawn Song. Towards inspecting and climinating trojan backdoors in deep neural networks. In 2020 IEEE International Conference Data Mining (ICDM), pp. 162-171, 2020. doi: 10. D0.10900CDM00008222200000
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. 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 Weinherger. Densely connected convolutional networks. In Proceedings of the IEEE conference 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 kernl:: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL URL httttt::://procceed..ng.o wtwpeeeeeeee.nn.....ue.eeeeeeeee cc/
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- municutions Security, pp. 349-363, 2018.
Soheil Kolouri, Aniruddha Saha, Hamed Pirsiavash, and Heiko Hoffmann. Universal litmus patterns: Revealing backdoor attacks enns. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 301-310, 2020.
M.R. Leadbetter. On basis for peaks over threshold modeling. Probability Letters, 12(4):357-366 101601167-7152(11990110 atticJe/p11/016711222100000
Statistics and 1991. ISSN 0167-7152. doi: https//doi.orr//0.
URL https::/ www.wwwwwwwwwwe........t...eee.e wwt.://w.....ce.eeeeeeeeeeeeeeee
Huichen Li, Xiaojun Xu, Xiaolu Zhang, Shuang Yang, and Bo Li. Qeba: Query-efficient boundary- based 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-211) 22000 2021a. doi: 10. 1020TD..... 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. attack with sample-specifie triggers. In ICCV, b021b.
Invisible backdoor

---

Published as a conference paper at ICLR 2022
Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chure Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. In 25nd Anmual Network and Distributed System Se- curity Symposimm, 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.
lacopo Masi, Yue Wu, Tal Hassner, and Prem Natarajan. Deep face recognition: A survey. In 2018 s1 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 learnig. In 2018 International Conference on Intelligent Autonomous Systems (ICoIAS), pp. 201-200222 IEEE, 2018
Carlos Ramirez, Vladik Kreinovich, and Miguel Argaez. Why is good approximation 10: A geometric explanation. 7:203-207, 01 2013.
Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor at-
tacks. 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 11-20. Springer, 2020.
Christian Szegedy, Alexander Toshev, and Dumitru Erhan. Deep neural networks for object detec- tion. 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. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018. URL httpps://proceeeiiiiiiee 1BBCE13baarS111222254223333322 Paper pdff
neur i ps. ccc/papper/211//11ee
Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Label-consistent backdoor attacks. arXiv preprint a11hv:191..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. 2019
IEEE Symposium 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 Computer Vision (ECCV), 2020.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber.
Natural evolution strategies. The Journal of Machine Learning Research, 15(1):49-998) 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 978 9781450367479.
doi: 10.1 00.11455331933533352299 URL
1eee11145331911 3354200
Tongqing Zhai, Yiming Li. Ziqi Zhang, Baoyuan Wu, Yong Jiang, and Shu-Tao Xia. Backdoor attack against speaker verification. In ICASSP, 2021.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
Table of Contents
A Other Backdoor Attacks
14
Dense Watermark Backdoor Attacks.
14
A.2 Feature Space Backdoor
14
Proofs
The proof Lemma I
B.2 The proot Lemma 2 theory on the linear case
................................
15
B.3 Proof of Lemma 3 An analysis for Kernel Regression
16
C Monte Carlos gradient estimation
18
Algorithm for Computing Aggregated Global Adversarial Peak (GAP)
19
E The detailed contigurations for experimental datasets and triggers
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
Details of visualization process
20
Detailed ROC varous tasks and attack approaches
The comparison results between AEVA and NC, DL-TND
20
K
Experiments for different triggers
21
K.
Evaluation on dynamic and sparse but not compact triggers
21
Results for impact of the number of images per labels.
22
The impact of the number of the labels for available images.
23
Multiple triggers within the single infected label scenarios
23
Potential adaptive backdoor attacks
24
0.1 Attacks with multiple target labels
24
0.2 Attack with large triggers
24
13

---

Published as a conference paper at ICLR 2022
A OTHER BACKDOOR ATTACKS
A. DENSE WATERMARK BACKDOOR ATTACKS.
In short, argue that low-mannitude dense backdoor attack (watermrk))) is not a practical attack method and is less concerned compared to the threat model in our paper.
First, the oow-manittude attack is special case of our formulation where the mask a continuous value (here we use a to represent transparency). The low- -ow-magnt problem can be formulated as: m E a)æ,, ad), yr) A|a
This formulation does not have discrete variables so its black-box optimization is an easier task 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 Taylor expansion and the fact that is small value,
6((1 - a)2 + aA)= = Φ(z, + a(A - r;)) x ((z;) + a(A VV
We know from x; (1 a) r;; aA, the function output label is changed. So every example æ; 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, 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 shown below. We find that such dense low- magnitude watermark triggers would make normal samples to be misclassified as the target label y via adding small random noise. Such observations can easily identify models infected with dense and low- mwwgaaiit watermark trigger.
Using global watermark trigger, 67.8% of the normal samples are misclassified other labels(Infected label)
Using 16x watermark trigger, 6.42% of the normal samples are misclassified other labels(Infeeted label)
Using 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 0.2% of the normal samples misclassified.
A.2 FEATURE SPACE BACKDOOR
Feature space backdoor attack which employs generative model transfer the style of 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 beyond our threat model 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. THE PROOF OF LEMMA 1
Lemma 1. Given continuous differential function f defined on IR" and vectors h E RR" there exists a real value M 2 /0k VI < S n such that
[f(x + f(x) s M|[hl/
(8)
14

---

Published as a conference paper at ICLR 2022
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.
R(h) 0f + ch)
his for some (0, 1).
(10)
8x:
Let M 2 10f(x)/0xx Vx, have
[R(h) & Σ hi = =M [b]l
(11)
So, we have
1/(x + h) [(x)] S M|jhI
(12)
B.2
THE PROOF OF LEMMA 2 THEORY ON THE LINEAR CASE
We perform theoretical study linear models to shed light about our empirical finding. Here, we restate Lemma 3 below for convenience.
Lemma 2. Given linear model parameterized by 9 optimized on N, original training examples and N2 backdoored training examples with an objective in Eq. and a mean-squared-erron loss, the adversarial solution optimized using Eq. will be dominated by input dimensions corresponding to backdoor mask m when N₂ is large, i.e.
(1 - m) @ All 0.
lim No 400
(13)
Proof of Lemma 2: To case the reading of notations, use (-)axb to represent matrix with rows and 5 columns, respectively. Assuming Φ(z; 0) = @Tr is a linear model whose output is a floating number, and the loss function is l2, i.e., ((x, y) = (x y)². Then Eq. 2 becomes linear regression problem and can be represented the matrix form of least square, i.e.,
F Xee Y + I - "112
(14)
where è; = (1-m) O A is backdoor example converted from normal example of and Ú: Vt- is the matrix composed of row vectors x; and is the matrix composed of row vectors y: The solution of this least square can be found by setting gradient to zero, such that
= (XTX + XIXX + XTÝ)
(15)
It is known that normal training without backdoors will lead to the ivvurr- solution 0 = (XTX) 'XTY. -'XT. Without loss of generality, we assume the backdoor trigger occupies the last dimensions. And the first p dimensions are normal values, i.e,, = d - p + where d is the total number of dimensions. So, we can rewrite the input
[X1.p) Xpsal and the mask m 01xp lixdd=+t))- Let d be the sub-vector of A such that 5 Ap+l,d, dimensional row vector. Then we have X Then,
[Xipp 11xx10] where No is the total number of backdoor examples.
X
X1,p XX
O
(16)
0
Similarly, we find = 1y: and assume zero mean of the input, i.e., Σ.; = 0. then we have
pxx
(17)
15

---

Published as a conference paper at ICLR 2022
While N₂ becomes larger, both XTX and XTY increase significantly. When No 0o, Eq. 15 becomes
0 0px1 i - (XTX)) = ())6)) 8T
(18)
In another word, we know the normalized values in the non-masked area of 0 approach 0 such that
[[ - m) @ Qll1 0.
lim
(19)
||0|
Now, let look the adversarial objective in Eq. 8, which is equivalent
G |00 (x
p1) -
(20)
the gradient of which is
V = 2(0 + -.)00
(21)
-b) know no matter how many gradient update steps applied, μ., initialized at 0, always moves the exact same direction of 0, i.e., á || 0. In this case, á will also be dominant by the last dimensions, or the dimensions corresponded to the mask m. In another word, we have
Since 2 (x+ -))) is a scalar and each of the gradient updates is conducted by u
[[ m) 2 AllI
lim
0.
(22)
AA
B.3 PROOF OF LEMMA 3 AN ANALYSIS FOR KERNEL REGRESSION
Lemma 3. Suppose the training dataset consists of N, original examples and N₂ backdoor ex- amples, 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. an RBF kernel K(.--) Then the adversarial solution to Eq. 6 under cross-entropy loss ((). y)
Σ, yi log ji (y {0, 13th is the one-hot label vector) should satisfy that
lim E[(1 m) A =
(23)
No +00
Proof of Lemma 3: The output of & is k dimensional vector. Let assume (b(-) E R be the output corresponding to the target class t. We know the kernel regression solution
No K(, + No Em K(.,.))
1=1 ((,..))...
s.(+)
(24)
No 1 K(,,2,)
where 2; = (1- m.) oz m 3 A is the backdoored example and ÿi is the corresponding hot label (so we always have ÿi. = 1). Because the examples are evenly distributed, there are N/k examples labeled positive for class t. Without loss of generality, assume Vj., = when j E [1, No/k] and Uj.t = otherwise. Then the regression solution becomes
NNo/k K(., + No K(, bx()) = MN K(.,.;) + E K(,,;;)
(25)
Please note the regression above is derived with mean squared loss. In the adversarial analysis Eq. 6, we can use any alternative loss function. In this Lemma, we assume the loss in the adversarial analysis is cross-entropy, which is common choice. So, have
{(b(x),)) log (x)
(26)
--logSS + 5) + log(S S + 5)
(27)
where S,()= =5()==y=+/ K(,, and S Si S2 + Sp and $ Ene K(;
16

---

Published as a conference paper at ICLR 2022
The derivative of loss w.r.. becomes
al(p(z))
1
a S)
0(S + $)
(28)
dr
S. + S
dr
S+
dæ
By using gradient descent, j moves along the negative direction of the loss gradient, i.e.
1
OSS + S)
1
a(s + S)
Ap
(29)
S +
S
dr
8 S+S
Ōr
0$
1
1
0S.
1
0(S S()
(30)
S. +
S
5 4 S
dx
S. +
S+
S S
dx
0$
0S,
0(S- - S:)
(31)
Dr
dr
Ox
where a, are both positive scalar values. When N& becomes large, the first term dominates the gradient direction, i.e., Au X
88 8x
Since we assume the kernel K(x exp(->]le x²113) is RBF, then we have its derivative
0K (K(x,=²)
-2 20) x¹)
(32)
Ox
Then we have
0$
No
(K(r,
OK
(33)
Or
N 22 (x, ix)( -x)
(34)
1=1
Without loss of generality, we assume the mask m 10 xps 1 (x(d-p+1) (where first p dimensions are Os and the remaining are 1s). Then the first dimensions of ft; are the same as those of HG, while the remaining dimensions equivalent to those of A.
Case 1:
d.
The j-th dimension of as Ba
can be written as
ia
N₂
= 27
K(z + 2.)
(zj + + - -5,)
(35)
3p j
1=1
So at convergence, Pj = 83 2j for the last d + dimensions. The expectation is E[py] = 5y B[zy].
Case 2: 1 S
For the first dimensions, we have
N,
2
K(s μ. 2.) + My- xzg))
(36)
0p
No
-27
Σ
-
del (zz + Mj xzz)
(37)
Since (4, + 2x = 8, his Fis for p + S S d, then we have
aa
22
Eisis (z) My xzz))
(38)
0p
t=1
Since N₂ is large and à; is i.i.d., then the summation can be approximated with integration, Le..
as
-27 /
Ea (z; + ,4 x.y )r
(39)
0p
17

---

Published as a conference paper at ICLR 2022
When y is large, the integration is the expectation of the offset to the center of a Gaussian distribution (centered at 2j + Mg). Due to symmetry, the derivative becomes for most of the μ locations. This would be the common cases because smaller y means examples with longer distance more significantly influence the function output (which is not desired in a classifier with high accuracy).
still find the stationary point of the a derivative. Given the fact that e "i (Fot). = is always positive, we know 8p
Nonetheless, in rare cases when the y becomes small,
0 2j [ M4j- Ij O. But it is impossible to reach. Again, utilizing symmetry of the normal distribution and the fact that x is i.d. uniform, we find when 2j + μ4 - H[zy] < 0, the derivative is positive; and when 2j MJj E[æy]
gradient 0, the derivative is negative. Since we descent to find the optimal f.. We can conclude that, at the convergence, =j + M4 = E[r,]. Then Elug] = E[ry] E|zz] 0 because is sampled from the same distribution of x.
To summarize,
0, 66
isisp -[2y,,
(40)
p<jsd
Then we know, as N,, - oc.
E[(1 m) o -0
(41)
C MONTE CARLOS GRADIENT ESTIMATION
Leveraging the Monte Carlo based estimation to craft target adversarial perturbations for the targeted
label y/ typically requires and Iz. where z; is legitimate sample satisfies f(xe) yt. Firstly,
is forced to approach the decision boundary of [:; 0) for the target label (,(0(1 ue) -> 0.5), which
stimulates the efficiency and accuracy of gradient estimation. We can make o(x ye) -> 0.5 through projection process:
x + (1 - a)x + a.r,
(42)
(0, 1) is parameters for projection. through binary search (Chen et al. 2020a).
During each gradient estimation procedure, is set
After that, we leverage Monte Carlo sampling to estimate VoL Bt), its procedure can be expressed as:
ViΦ(E,)) N
Σ S(x 0pp
(43)
where ( are perturbations i..d sampled from uniform distribution and 5 is small positive value representing the magnitude of perturbation. S is an indicator function such that
f(z) y 1, -1, f(z) zリ.
S(x, v) =
(44)
To further eliminate the variance induced by Monte Carlo sampling, we can improve (2, via:
1 N V (x, w1) = N (S(x= + 044.80 - N
N Eis
Σ S(x + v14.))))44
(45)
Using cosine angle measure the similarity between Voo(z, and veδ(z,yd, previous work (Chen et al. 2020a) have proved that:
lim cos (E v)), Vad(E, =1
(46)
6-0
thus smaller 8 (0.01) is selected for ensuring the efficacy of gradient estimation.
18

---

Published as a conference paper at ICLR 2022
Regarding the constraints on |||| further processed the estimated gradient via:
Vzd(a,y)) ve)
V Mc)
(47)
V 31)l
We refer readers to (Chen et al. 2020a) for the complete algorithm for gradient estimation.
D ALGORITHM FOR COMPUTING AGGREGATED GLOOBAL ADVERSARIAL. PEAK (GAP)
Algorithm Aggregated Global Adversarial Peak (GAP)
I:
Input: Targeted DNN f(; 0); label to be analyzed yrs legitimate input batches (Xi evenly sampled across classes; the targeted input batch Xx;
2: Output: Aggregated GAP value R(x):
3: Initialize R(y)) =
4: for -- 1,
..... 5: for j I,... len(X.) de
1, + I...., do
6: Solve 14) arg min, E(b(as + 14 yr; 8c) + Al[x=[12 using MC gradient estimation;
7: end for
8: Find the GAP value for the current label: pimaz maX Pya,ii
9: Aggregate GAP values over all labels: Ryy)) = Pimox + R(y:):
10:
end for
11:
Return: R(y,))
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
TinylmageNet
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 lhttps: io/ zh/ examples/cifarll resnet/
F THE ACCURACY AND ATTACK SUCCESS RATB(ASR) FOR EVALUATED MODELS
The accuracy and ASR for the evaluated models for each task in included in Table.
Infected Model
Task
Normal Model Accuracy
Accuracy
ASR
CIFAR-10
90.04%
97.77
92.31%
CIFAR-100 100
69.17%
2 96.27%
2 71.41%
TinylmageNet
58.98%
97.22%
2 60.11%
Table 3: Accuracy and ASR the evaluated models for each task
19

---

Published as a conference paper at ICLR 2022
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. No- tably, 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 Visualize j
1: Input: Targeted DNN f(=:0) label to be analyzed yr; legitimate input batches (Xi evenly sampled across classes; the targeted input batch X,;
2: Initialize μ
Output: Normalized Jr:
4: for i
1, 1, I..... do 5: for j 1, ,..., len.,,, do
6: Solve nn)
miny El ((b(a, + μ4, y1; 0), Mr) + Alla|| using MC gradient estimation;
7: end for
8: Find Js' owns the GAP value for the label: arg max Miavii
9:
Aggregate μ² over all labels: p²
10:
end for Return: H/||el
I DETAILED ROC FOR VAROUS TASKS AND ATTACK APPROACHES
1.00
1.30
3.65
0.85
0.80
Wearss
Valerat
Mader
Label Cor starn
0.79
Label Corsitert
0.2
0.70
(a) CIFAR-10
(b) CIFAR-100
(c) TinyImageNer
Figure 10: The Receiver Operating Cure(ROC) for AEVA on CIFAR- CIFAR-100 and TinyIma-
geNet tasks.
J THE COMPARISON RESULTS BETWEEN AEVA AND NC, DL-TND
Detection Results
Attack
Method
AUROC
ACC
NC Wang el al. 2019
0.976
95.0%
BadNets
DL-TND (Wang al.
2020
0.999
99.2%
AEVA (Ours)
0.930
91.5%
NC [Wag et al. 2019
0.983
95.8%
Watermark
DL-TND (Wagg al.
2020
100%
AEVA (Ours)
0.968
94.1%
NC /C/Wang et al. 2019
0.961
94.2%
Label Consistent
DL-IND (Wngg
2020
0.992
98.3%
AEVA (Ours)
0.968
94.1%
NC Wang et al.
2019
0.980
95.8%
Invisible Attack
OL- (Wang al. 2020
0.999
99.1%
AEVA (Ours)
0.970
94.4%
Table 4: The two metrics for backdoor detection on the CIFAR- 10 task using three backdoor detec- tion methods: NC, DL-TND, and AEVA. Higher values in AUROC and ACC are better.
20

---

Published as a conference paper at ICLR 2022
Detection Results
Attack
Method
AUROC
ACC
NC (Wang et al., 2019
0.978
95.8%
BadNets
DL-IND (Wang al.
2020
0.999
99.1%
AEVA (Ours)
0.973
95.4%
NC (Wang et al. 2019
0.961
94.2%
Watermark
DL-IND (Wang et al.
2020
100%
AEVA (Ours)
0,992
98.8%
NC (Wang al. 2019
0.964
94.2%
Label Consistent
DL-TND (Wang
2020
0.999
99.1%
AEVA (Ours)
0,981
96.8%
NC Waraang et al. 2019
0.989
97.5%
Invisible Attack
DL-TND (Wang al., 2020
100%
AEVA (Ours)
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.
Detection Results
Attack
Method
AUROC
ACC
NC Wang ct al. 2019
0,956
91.6%
BadNets
DL-IND (Wang al.
2020
0.999
99.1%
AEVA (Ours)
0.988
97.9%
[Wang et al.
2019
0.972
94.2%
Watermark
DL-IND (Wagg ct al.
2020
100%
AEVA (Ours)
0.999
99.6%
NC WWag al. 2019
0.983
96.7%
Label Consistent
DL-TND (Wang
2020
0.999
99.1%
AEVA (Ours)
0.983
96.7%
NC CCrWagg ct al. 2019
0.982
96.7%
Invisible Attack
DL-NDD (Wang al. 2020
0.999
99.1%
AEVA (Ours)
0.986
97.9%
Table 6: The two metrics for backdoor detection on the Tiny Imagenet task using three backdoor detection methods: NC, DL-TNDD, and AEVA. Higher values AUROC and ACC are better. Each approach are evaluated using 60 infected and 60 benign models.
K EXPERIMENTS FOR DIFFERENT TRIGGERS
EVALUATION ON DYNAMIC AND SPARSE BUT NOT COMPACT TRIGGERS
We evaluate AEVA for CIFAR-10 task under the dynamic and non compco triggers scenario. We randomly generate three non-compact triggers(shown in Figure. IT] and perform backdoor attacks against randomly selected label using these dynamic triggers. We test AEVA using 10 different DNN models, which are evenly built upon ResNet-18, 18, ResNet-44, ResNet-56, DenseNet-33 and DenseNet-58.
15
25
35
(a) Dynamic trigger
(b) Dynamic trigger
(c) Dynamic trigger III
Figure 11: Dynamic Triggers
21

---

Published as a conference paper at ICLR 2022
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 shown in Fig. [2] We find AEVA predicts all backdoored models as infected with Anomaly Index 2 4. Such results demonstrate that AEVA is resilient dynamic and sparse but compact triggers.
14
10-
Anomaly Index
0.20
AGAP
0.15
0.10
0.05
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, B3 For each trigger, we build 30 models on TinylmageNet. Each set of models are evenly built upon ResNet-18, 18, ResNet-44, ResNet-56, DenseNet-33, DenseNet-58 these architectures. The results are shown in Table.
Attack Approach
ACC
Trigger 93.3%
Trigger 93.3%
Trigger 90.0%
Table 7: Results for other different triggers
0
28
30
(a) Trigger
(b) Trigger
(c) Trigger IIII
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 TinylmageNet and the experimental configurations consistent with Sec.4.1(i.e. 240
22

---

Published as a conference paper at ICLR 2022
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
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 detect backdoors in the black-box setting, 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, 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 x 4 squares) following the configurations of S.2. We vary the number of uninfected labels for available samples between [1, 200], randomly sampled from the 200 labels available the TinglmageNet dataset. Figure. 15 illustrates our results by plotting the metrics against the number of available labels. We observe that 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 's practicality, which can work in the black- box 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.
1.0
0.8
ACC
0.4
0.2
0.0
10P
10'
10a
10a
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
23

---

Published as a conference paper at ICLR 2022
BadNets. We randomly select label the infected label. We built 60 infected models with different architectures(iie, ResNet-18, ResNet-44, ResNet-56, DenseNet-33, DenseNeet-8)). The results for TinyImageNet are shown in Table. 8 Notably, for TinylmageNet, injecting too many triggers (2 4) in the single label would cause the target model's accuracy drop (i.e., 2 3.7%). which is inconsistent with the threat model for backdoor attacks (Gu et al. 2019 Chen al. 2017 Liu et al. 2018).
As seen in Table. X] our approach can still perform effective when injecting two x 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-triggens would reduce the singularity properties for the adversarial perturbations. To address this issue, we select the sum of the largest five points as the pmaa instead. The results are shown in Table. 9 By selecting more points to calculate the pmaz, 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 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.2 30%:) infected will make the anomaly indexes produced by the MAD detector significantly drop. However, such attack only be successfully implemented for some small datasets which own few labels(e.g.. CIFAR-10, etc). Reported by (Wang al., 2019), the state-of-the-ae 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 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 TinylmageNet, which reveals that when over 14 labels are infected with different triggers, the model accuracy (ResNet-44 and DenseNet-58) decreases to S 57.61% (around 3% lower than a normal model) when preserving the attack effectiveness (ASR 2 97.12%) for each infected label.
O.2 ATTACK WITH LARGE TRIGGERS
Another potential adaptive backdoor attack that the attacker would implement dense backdoor trigger which would alleviate the singularity phenomenon. As we claim in Section 4.3 dense back- door trigger would appear -ssualy-distinguishable to the human beings which perform less stcalthy, that is also reported by Neural Cleanse (Wang et al. 2019). Indeed, there exists interesting excep- tional 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
24


Reviews:
[{"review_id": "l6UUu5BHUvU", "reviewer": "Reviewer_Zz4A", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The method assumes the black-box scenario, which is practical.\n2. Some theoretical analysis is provided to establish the connection between adversary and backdoor attacks.\n3. The idea is smart for using adversarial attack results to detect backdoors.\n\nWeakness:\n1. It seems that it is not difficult to avoid being detected if the backdoor patterns are smartly designed.\n2. There should be some work using interpretation to detect the backdoor. Due to the close relation between adversarial attack and interpretation, I am not sure if the proposed method is still novel from this perspective.", "summary_of_the_paper": "The paper propose a new backdoor detection method. The method does not require the original poisoned training data or the parameters\nof the target DNNs. Given an image, the proposed method initiates adversarial attack on it. If the model contain backdoors for predicting the target label, then the adversarial noise will contain singular patterns, which could be detected using extreme value analysis.", "summary_of_the_review": "The paper proposes a good idea for using adversarial attack patterns to diagnose if backdoors exist in models. My only concerns are twofold. First, some adaptive studies could be conducted, analyzing the scenarios where the proposed detection method could be circumvented. This may not be very difficult since this paper assumes that the backdoor patterns are focused patches. Second, the proposed idea seems to be similar to using interpretation (e.g., heat maps) to detect backdoor, since adversarial attack = inversed interpretation. From this perspective, the proposed idea does not look that novel.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "h3qQryEipoS", "reviewer": "Reviewer_TYjG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have several concerns as follow:\n\n- The relationship between adversarial examples and backdoor samples (e.g., pictures with auxiliary patches) is well known. Therefore, it is reasonable to expect that the adversarial singularity phenomenon may not occur in backdoor-infected DNNs. Will algorithm 1 be efficient under cases where the infected range and uninfected range overlap a lot and the threshold T is large (as discussed in Sec. 3.3)?\n\n- It seems that the black-box setting is somehow contrived since it only poses challenges on computing the gradient ∇φ(x,yt). What is the effect of the sample size used for gradient estimation on the detection accuracy? With exact gradient computations, will the proposed algorithm 1 (AGAP) outperform the existing white-box detection methods?\n\n- The result of Lemma 1 seems to be a natural consequence under the linear model assumption, mean-squared-error loss, and the optimization formulation of Eq. 6. Since this paper targets the adversarial extreme value analysis in DNN, do we have a more formal understanding of the regime of modern neural network architectures?\n", "summary_of_the_paper": "This paper proposed an adversarial extreme value analysis (AEVA) framework to detect backdoors in black-box neural networks.\nSpecifically, they first obtained a new (upper bound) backdoor detection formulation by using convex relaxation. With linear model assumption and mean squared error loss, they showed that the mass in the adversarial perturbation would be occupied in the mask area as the backdoor sample size goes to infinity. Hence, a highly skewed distribution in the adversarial map for the infected label is expected.\nBased on the above observation, they designed an Aggregated Global Adversarial Peak (GAP) for detecting the adversarial maps. With the limitation of the black-box setting, a Monte Carlo-based gradient estimation was used in the GAP. \nFinally, they evaluated their methods on several real-world datasets.", "summary_of_the_review": "Overall, I think the paper provides a new perspective of backdoor defense, but it could be made stronger by addressing some critical aspects as listed above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WY4F13X_ZFE", "reviewer": "Reviewer_9qnh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths and Weaknesses:\n\n+ The proposed setting and algorithm are novel.\nIn particular, the subtle connection between backdoored networks and sparse adversarial example generation can inspire further research in this direction.\n\n+ The analysis in the paper is logical, and it guides the reader well through the thought-process behind the algorithm.\n\n+ The experimental results are comprehensive.\nAlthough the experiments do not contain the most recent backdoor detection methods as baselines, this reviewer believes that the current comparison baselines (neural cleanse [[5](https://ieeexplore.ieee.org/abstract/document/8835365)] and DL-TND [[6](https://arxiv.org/abs/2007.15802)]) are enough to provide the bigger picture.\nThis is since almost all existing methods are typically designed for the white-box scenario, and as such, they have a huge advantage compared to the current method.\n\n+ The paper is generally well-written, although some parts need proofreading.\nSee the minor comments about this below.\n\n+ There are two gray areas regarding this submission that needs to be clarified further:\n\n\t1. Although the authors talk about the practicality of the black-box scenario in the introduction, this assumption needs to be justified further.\nI strongly suggest providing a concrete example, where the use-case of this scenario is explained.\nIn this example, please specify the training data, the model, the user, and why the user who does not own anything from the training data to the model should be worried about backdoors?\n\n\t2. Another interesting question that is not been explored is the white-box performance of the algorithm.\nCurrently, the only part where the black-box scenario is being dealt with is the adversarial example generation.\nNow, assuming that the user has access to the model parameters, what does the current approach provide in contrast to existing methods?\nAsked the other way around, can someone use the Monte-Carlo gradient estimation in conjunction with existing methods to make them black-box?\nSince being \"black-box\" is considered as the strength of the proposed method compared to existing ones, these questions need to be answered.\n\n### Further Questions:\n\n1. Can you clarify what this sentence below Eq. (3) means: \"Additional difficulty comes from the fact that...\"?\n\n2. At the bottom of page 4 the paper reads: \"Following this, the optimization in Eq. (3) converts to...\" I am guessing that you meant only the first part of Eq. (3), right? Otherwise Eq. (4) is missing a $||m||$ term.\n\n3. For the empirical study of Section 3.2, do you solve Eq. (6) in a white-box setting, or using the Monte-Carlo gradient estimator? How about Figure 6, is this figure generated in the black-box or white-box setting?\n\n4. Does Eq. (7) mean that there are two ways to get the GAP: (1) by generating adversarial perturbations for multiple inputs (as the AVEA does) (2) by generating multiple perturbations for a single input?\n\n5. Does the ablation study on \"the impact of trigger size\" mean that a scattered trigger is more likely to circumvent the detector than a sparse trigger?\n\n6. The results reported in Appendix J indicate that in some cases the performance of the black-box detector is better than the white-box baselines, especially neural cleanse. What do you speculate is the reason behind this?\n\n### Minor Comments/Suggestions:\n\n+ Across the paper, the index \"$i$\" has been used to point to training samples (Eq. (2)), validation samples (Eq. (3)), and class (Algorithm 1).\nConsider using a different index for each one of these to avoid misunderstanding.\n \n+ Consider using different line styles and a bigger plot size for AUROC figures.\n\n+ Consider adding a table of contents and/or explanation of different parts of the Appendix. Right now there are sudden jumps from one section to the next with no explanations.\n\n+ In the second sentence after Eq. (15) $q$ has been used to point out the first and last dimensions of $X$. The second one needs to be changed to $p$.\n\n+ Omit the $'$ in Eq. (16).\n\n+ In Eq. (19) $N_b \\to \\infty$, not $N$.\n\n+ In the explanations that follow Eq. (24), $K$ is used instead of $k$.\n\n+ In Eq. (27) there is a $\\hat{S}$ missing in the second $\\log$.\n\n+ Figure 13 is colliding with the text.", "summary_of_the_paper": "This paper presents a novel approach for the detection of backdoored neural networks.\n\nInspired by the deployment of third-party networks in cloud services, it is argued that this detection task needs to be done in a black-box, hard-label scenario.\nIn this regime, it is assumed that the user/defender only has access to the model through making queries and getting back the labels for those queries.\nTo solve this newly proposed problem, first, a connection between the _detection of backdoors_ and _adversarial example generation with sparse perturbations_ is drawn.\nThen, it is shown that for backdoor models solving this adversarial example generation objective leads to perturbations that are mostly concentrated in the backdoor mask area.\nThis argument is shown both theoretically (for linear classifiers) and empirically (for deep neural networks).\n\nBased on this observation, which the paper calls the _adversarial singularity phenomenon_, a practical black-box backdoor detection is proposed.\nSpecifically, this algorithm first computes the aforementioned adversarial perturbations for some validation data in each class.\nTo this end, a Monte-Carlo gradient estimation is used to make the algorithm suitable for the black-box setting.\nThen, based on the maximum value of these perturbations, it is decided whether the network for this label is infected or not.\nThe effectiveness of this method, named AVEA, is shown through extensive experiments and ablation studies on various datasets (CIFAR-10, CIFAR-100, and Tiny-ImageNet) and attacks (BadNets [[1](https://arxiv.org/abs/1708.06733)], Label-consistent [[2](https://arxiv.org/abs/1912.02771)], Watermark [[3](https://arxiv.org/abs/1712.05526)], and Invisible [[4](https://arxiv.org/abs/1909.02742)] attack).", "summary_of_the_review": "While there are some gray areas around the proposed method (please see the strengths and weaknesses), I believe that this is a well-written, thought-provoking paper that can be interesting to the community and bring forward fruitful discussions.\nAs such, I vote for borderline acceptance of the paper.\nIf the authors can provide convincing answers to my two questions in the main review, I would be happy to increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "I5OzrREGjXj", "reviewer": "Reviewer_hfE9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nPros\n1.\tThis paper is well-written and easy to follow.\n2.\tThe topic is of great significance and sufficient interest to ICLR audiences. In particular, black-box hard-label backdoor detection is probably the hardest problem in backdoor defense and has the highest commercial potential. As such, I think this paper should be encouraged, although it still has some problems. \n3.\tThe authors provide some theoretical supports for their method and open-source their codes, which should be encouraged.\n4.\tI appreciate that the adaptive attacks and potential limitations are also included in the paper. It can prevent readers from being overly optimistic about safety.\n\n\nIn general, I enjoy the reading of this paper and I think the proposed method is also moderately novel. However, I still have some concerns. I will increase my score if the authors can address my concerns. The detailed comments are as follows:\n\n\nMajor Comments\n1.\tMy main concern lies in the novelty of Lemma 2-3. The optimization problem (6) seems to be a classical problem. As such, I have to worry about whether its analysis (i.e., Lemma 2-3) is not new. I will not decrease my score even Lemma 2-3 are not new if the author can provide proper references and illustrations.\n2.\tI would like to see the results of defending against attacks with dynamic and sparse but not compact triggers. \n3.\tPlease analyze the effects of key hyper-parameters (e.g., lambada) involved in the proposed method.\n4.\tPlease provide more details and results in the analysis of potential adaptive attacks.\n\n\nMinor Comments\n1.\tPlease double check the reference format, especially that of conference papers. Please cite the official version of all papers (e.g., BadNets should be IEEE ACCESS, DL-TND should be ECCV). \n\n\nNote: I didn't check all proofs carefully. But the lemma seems reasonable and consistent with the experimental results.\n\n\nPost-rebuttal Comments:\nI would like to thank the authors for their clarifications. Since most of my concerns have been addressed, I increase my score to 8. \nPS: It would be better if you can point out whether there are similar theories in adversarial learning. I think it will help readers to better understand them and it will not reduce your contributions.", "summary_of_the_paper": "This paper proposes the first black-box hard-label backdoor detection where the defender can only access the predicted label of queries. Specifically, the authors first prove that the detection problem is bounded by an `adversarial objective’, based on which they reveal the adversarial singularity phenomenon that the perturbation generated by the adversarial objective is highly skewed distributed. Based on this phenomenon, the authors propose the adversarial extreme value analysis (AEVA) to detect backdoors in a black-box manner. The authors verify the effectiveness of their method in defending against BadNets, Blended Attack, Label-Consistent Attack, and Invisible Attack on CIFAR-10, CIFAR-100, and TinyImageNet dataset.", "summary_of_the_review": "A practical and novel backdoor detection with theoretical guarantees.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposed to detect backdoor in a black-box manner, where only the model output is accessible. 

Most reviewers think it is a valuable task, and this work provides a novel perspective of using adversarial perturbation to diagnosis the backdoor. Some theoretical analysis for linear models and kernel models are provided. There is still huge gap to analyze the DNN model. But on the other side, it provides some insight to understand the proposed method and could inspire further studies. 

Besides, since there have been many advanced backdoor attack methods, and many more are coming out, I am not sure that the proposed detection criteria is well generalizable, considering only some typical attack methods are tested. However, I think the studied problem is valuable, and the presented analysis is inspired for future works. Thus, I recommend for accept.
Decision: Accept (Poster)