AEVA: Black-box Backdoor Detection Using Adversarial Extreme Value Analysis

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 attacks 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.

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(\cdot)$ 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.

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\in\mathbb{R}^{n}$, the modified input containing the backdoor trigger can be formulated as:

where $\Delta\in\mathbb{R}^{n}$ represents the backdoor trigger and $\odot$ represents the element-wise product. $m\in\{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 $\hat{x}$ and $x$.

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

where there are $N_{o}$ original training examples and $N_{b}$ backdoor examples. $\ell(\cdot)$ represents the cross-entropy loss function; $x_{i}$ and $y_{i}$ represent the training sample and its corresponding ground-truth label, respectively. In the inference phase, the target DNN will predict each $\hat{x}$ as the target label $y_{t}$, which can be formulated as: $f(\hat{x})=y_{t}$. 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 $x_{i}$ becomes near the decision boundary of function $\phi$. It is revealed by Taylor theorem, $\phi(\hat{x}_{i})=\phi((1-m)x_{i}+m\Delta)=\phi(x_{i}+m(\Delta-x_{i}))\approx\phi(x_{i})+m(\Delta-x_{i})^{\intercal}\nabla_{x}\phi$. And the function output label changes dramatically from $\phi(x_{i})$ to $\phi(\hat{x}_{i})$, so the gradient $\nabla_{x}\phi$ 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.

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 $y_{t}$ using the following optimization:

where $\beta$ is the balancing parameter. Unfortunately, solving Eq. 3 is notoriously hard in the black-box hard-label setting since $\theta$ is unknown. Additional difficulty comes with the fact that an effective zero-th order gradient estimation requires each example $x_{i}$ superimposed with the trigger to be close to the decision boundary of $y_{t}$ (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.

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

where the latter inequality holds because each example $x_{i}\leq 1$ is bounded and the last equality $\|m\|_{1}=\|m\odot\Delta\|_{0}=\|\mu\|_{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\leq\frac{1}{N}\sum_{i}\ell(\phi(x_{i}+\mu),y_{t})+C\|\mu\|_{0}$. Instead of optimizing the original Eq. 3, we here propose to minimize the $\ell^{0}$-regularized objective. While $\ell^{0}$ enforces the sparsity of the solution, optimizing it is NP-hard. In practice, it is replaced with an $\ell^{1}$-norm as an envelope of the objective (Ramirez et al., 2013; Donoho, 2006):

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.

A natural and important question here is what the adversarial perturbation $\hat{\mu}$ 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.

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 $\hat{\mu}$.

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.

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 $\hat{\mu}$ (by optimizing Eq. 6) are generated for both infected and uninfected labels. The perturbations are normalized to a heat map as $|\hat{\mu}|/||\hat{\mu}||_{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.

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

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

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 $\mu_{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.

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 $\theta$ can enable us to compute the $\nabla_{x}\phi(x,y_{t})$ accurately, resulting in $\mu$ with minimum $||\mu||_{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 $\nabla_{x}\phi(x,y_{t})$. We choose Monte Carlo based method (Fu & Hu, 2012) for obtaining the estimated gradient $\widetilde{\nabla\phi}_{x}(x,y_{t})$, which sends several inputs and utilizes the corresponding outputs to estimate the gradient. More details about gradient estimation can be found in Appendix C.

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 $X_{i}$ for each class $i$. For each label $y_{t}$ to be analyzed, the algorithm will tell whether $y_{t}$ is backdoor-infected. We treat $y_{t}$ as the targeted label. Then we collect a batch of legitimate samples belonging to $y_{t}$, denoted as $X_{t}$ with the same batch size as that of $X_{i}$. Then, we leverage $X_{t}$ to make each sample within every $\{X_{i}\}_{i=0}^{n}$ to approach the decision boundary of $y_{t}$. This is computed by optimizing $\hat{\mu}$ from Eq. 6 using Monte Carlo gradient estimation. The adversarial peak $\mu_{max}$ is then computed for each example. The global adversarial peak (GAP) is aggregated over all labels. After calculating the GAP value $\mathcal{R}(y_{i})$ for each class $i$, following previous work (Wang et al., 2019; Dong et al., 2021), we implement Median Absolute Deviation (MAD) to detect the outliers among $\{\mathcal{R}(y_{i})\}_{i=1}^{n}$. Specifically, we use MAD to calculate the anomalous index for each $\mathcal{R}(y_{i})$ by assuming $\{\mathcal{R}(y_{i})\}_{i=1}^{n}$ fits Gaussian distribution. The outlier is then detected by thresholding the anomaly index.

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 backdoor-infected model and inject sufficient poisoned samples to ensure the attack success rate $\geq 98\%$. More details can be found in the Appendix.

Attack methods. Four different attack methods are implemented: BadNets (Gu et al., 2019), Watermark 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\times 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 approach with two state-of-art white box backdoor detection methods: Neural Cleanse (NC) (Wang et al., 2019) and DL-TND (Wang et al., 2020)²²2We implement NC (Wang et al., 2019) and DL-TND (Wang et al., 2020) following https://github.com/bolunwang/backdoor and https://github.com/wangren09/TrojanNetDetector. For each task, we use 200 samples for the gradient estimation, and the batch size for each $\{X_{i}\}_{i=1}^{n}$ is set to 40 in Algorithm 1.

Outlier detection. To accurately identify the anomalous $\mathcal{R}(y_{i})$ among $\{\mathcal{R}(y_{i})\}_{i=1}^{n}$, 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 $\tau=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 $\tau$ 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.

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 $\mu$ 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 $\geq 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 DL-TND (Wang et al., 2020). The comparison results over all infected and benign models are shown in 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.

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\times 14$ with ACC $\geq 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 visually-distinguishable 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\times 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 $\geq 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.

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.