Few-shot Backdoor Defense Using Shapley Estimation

In DNNs, since there are a large number of neurons and complicated interactions between them, it is difficult to quantify each neurons’ contribution to the overall output. To tackle this problem, we introduce Shapley value which, as one of the most important concepts in cooperative game theory, can allocate values to each player using the average of marginal values [2], and be used to determine the contribution of each neuron to the overall output [13]. We can treat a network as an $n$-player game with each neuron as a player. Let $N$ be the set of all $n$ neurons in the neural networks, denoted by $N=\{1,\ldots,n\}$ and $m$ be a metric function evaluating performance of players. In neural networks, $m$ can be a score function such as accuracy or loss. The marginal contribution of neuron $i$ can be defined as:

where $C$ is a subset of players not containing $i$, i.e., expressed as $C\subset N\backslash i$. With the marginal contributions, Shapley value $\phi$ for neuron $i$ can be defined using the average of them as follows [36]:

where $P_{C}=\frac{(n-c-1)!c!}{(n-1)!}$ represents the relative importance of subset $C$ , and $c$ is the cardinality of $C$. In the next subsection, we will provide an algorithm for computing Shapley value for each neuron.

From Eq. 2, Shapley value can be expressed as the average of marginal contributions of the neuron in all possible orders. We define $O$ as a permutation of neurons and ${Af}^{i}(O)$ means a subset of neurons after neuron $i$ in the order $O$. $\pi(N)$ is all possible orders of neurons. Then, Shapley value of neuron $i$ can be rewritten as follows [2]:

Eq. 3 shows that computing $\phi_{i}$ is equivalent to calculating the expectation of a random variable. Despite that estimating Shapley value exactly is time-consuming as it involves $n!$ permutations of all neurons in deep neural networks, we can approximate it by applying the Monte-Carlo estimation [9] which first samples permutations of neurons and then calculates the average of marginal contributions with those sampled permutations. Further, we propose discarding threshold and $\epsilon$-greedy acceleration to estimate Shapley value more fast and precisely.

cDiscarding threshold. The main computational cost in estimating Shapley value is computing the marginal contribution of each neuron. For a small subset of neurons ${Af}^{i}(O)$, our experiments find that after removing a small portion of neurons, ASR (attack success rate) of the networks will reduce to a low rate sharply. Thus, the marginal contribution of neurons after that can be negligible, and we can avoid calculating it, which saves substantial computational cost. Moreover, we mainly focus on top-$k$ neurons which are the most important in ASR when the network structure is complete and the performance is normal. Thus, we propose to discard neurons’ marginal value after ASR is below a threshold, e.g. 0.2. Note that we do not set the marginal value of the neurons to be zero after the model’s performance reduces to a low rate. This is because if the neurons with larger Shapley value are in the latter part of the permutation, the marginal value of those neurons will be set to zero, making their Shapley value underestimated, especially when the number of average iterations is small. Our experiments also demonstrate that setting to zero can cause fluctuation and randomness in Shapley estimation, which needs a large average iteration to offset that negative effect.

$\epsilon$-greedy acceleration. Since we focus on neurons with top-$k$ largest Shapley values, neurons with larger Shapley value should be calculated more times to be estimated more precisely and get a more accurate sorting of them. However, because of discarding threshold, the neurons after ASR is under a threshold will be discarded and lose the opportunity to be computed. To improve their calculation times, we should assign neurons with the top Shapley values a higher probability to be at the front of the permutations. To this end, we propose an $\epsilon$-greedy based acceleration.

$\epsilon$-greedy algorithm [42], as an optimization method, selects the best choice with probability $1-\epsilon$ and chooses from all the choices randomly with probability $\epsilon$. $\epsilon$-greedy algorithm is usually used in reinforcement algorithm and helps find the best choice in the action space [19]. Thus, to improve estimation efficiency, we follow this idea and propose an $\epsilon$-greedy based algorithm, balancing exploration and utilization in finding the top-$k$ Shapley value neurons. We divide neurons into two groups based on the current Shapley value, estimated by the current average of each neurons’ marginal values, top-$m$ and the other ($m\geq k$). We randomly permute neurons before the average iteration is smaller than $l$. Then after $l$, we utilize $\epsilon$-greedy, choosing a random neuron from top-$m$ with probability $1-\epsilon$ and choosing from the others with probability $\epsilon$ iteratively, and get a permutation to prune the neurons.

We choose ASR as the metric function to estimate each neurons’ Shapley value, and therefore, we need the backdoor dataset to calculate ASR. Furthermore, backdoor attacks manipulate DNNs to specific behaviors only on triggered images, indicating that the poisoned neurons are only activated on the backdoor images rather than normal images. Thus, reversing triggers from the backdoor networks, as an important part, can help the removal of backdoor neurons in poisoned models. Intuitively, backdoor attacks make use of DNNs’ overfitting feature to create a shortcut for the trigger to cause DNNs’ misclassification. We can use the trigger reverse synthesis to reverse backdoor trigger in the models and generate the reversed backdoor dataset[41].

We first inject class-specific reversed trigger ${T}_{c}$ into clean images and get the triggered image $a_{c}$ as follows:

where ${M}_{c}$ represents the mask for class c, deciding the location and intensity of trigger being injected into original images, $a$ represents the original image, ${T}_{c}$ represents the trigger patter for class c and $\odot$ means Hadamard product. Similar to adversarial example generation, we optimize on networks’ misclassification and trigger size to reverse backdoor. We use Cross-Entropy loss to optimize misclassification of triggered images to class $c$ and $L1$ norm of the mask to optimize the trigger size. We sum the above objectives and get the equation as follows:

where $y_{c}$ represents label for class $c$, $A$ represents clean images available, $CE(\cdot)$ represents Cross-Entropy loss, $|M_{c}|_{1}$ represents $L1$ norm of the mask, and $\lambda$ represents the trade-off parameter.

From the above method, we can get the reversed trigger for each target class. However, judging whether the network is poisoned and which is the target label is still a problem. Intuitively, since backdoor training produces a shortcut for the backdoor trigger in the poisoned models, the reversed trigger for the target label is the smallest among all the classes. Thus, we can get the reversed trigger and target label by finding the smallest trigger in trigger reverse synthesis.

Backdoor model detection. First, the L1 norm of the reversed trigger for the target label is much smaller than the others. Thus, L1 norm for the target label can be seen as an outlier from the other triggers, and we can use anonamly detection method to find the target label. We employ MAD (Median Absolute Deviation) to judge whether the models are poisoned. By MAD, supposing that mask norms obey normal distribution [34], any anomaly index $I=d_{i}/MAD$ larger than a specific value will be treated as an outlier, where $d_{i}$ is the absolute deviation between triggers’ L1 norm and their median.

However, in experiments, we find that the reversed triggers for some classes can’t converge to a small L1 norm, and their norms are abnormally larger than expected, causing a false positive in backdoor detection. Different from [41], since we only focus on whether the smallest reversed trigger is an outlier, we can just apply MAD to the set of the triggers whose norms are smaller than the median to avoid anomaly large norms. We define their deviations’ set as $D_{small}=\{d_{1},\ldots,d_{l}\}$. Furthermore, because normal distribution is symmetrical, the median of $D_{small}$ can be used to replace the median of all labels’ deviation as MAD. Then, we can use MAD to estimate the standard deviation $\sigma$ of the distribution of norms and use it to detect backdoor model with confidence probability $p$, expressed as follows:

where $\Phi(\cdot)$ represents cumulative probability distribution of standard normal distribution and $d$ represents max bound for $d_{i}/\sigma$ with probability $p$. The norm with the deviation larger than $\sigma\cdot\Phi^{-1}(\frac{p+1}{2})$ is an outlier and the model has been poisoned.

As we mentioned above, we can mitigate backdoor from models with few images using ShapPruning. Then we further research on a no clean data situation and propose a data-free ShapPruning method. To help data-free backdoor mitigation with Shapley estimation, we need to reverse training images from the poisoned models first. Recent works in transfer learning show that the batch normalization layer (BN layer) can be used to recover better images from the trained models and improve transfer efficiency [5, 18, 43]. Furthermore, because backdoor attacks only poison a very small portion of training datasets, they won’t affect the information in BN layers, and thus, we can use BN layers to better reverse images. Then we can express the difference of the mean and variance between the recovered data and original training data in the model’s each BN layer as follows:

where $div(\cdot)$ represents divergence, $N(\mu_{i}(x),\sigma_{i}(x))$ represents mean and variance of recovered data $x$ on BN layer $i$, and $N(\mu_{i},\sigma_{i})$ represents mean and variance recorded in BN layer $i$. Furthermore, considering the image prior information, we got the prior loss as follows:

where $L_{V}(x)$ represents the variation of images, $L_{norm}(x)$ represents images’ norm, and $\alpha_{1},\alpha_{2}$ are hyper-parameters. Then, with the analysis above, we use the total loss $L_{total}$ to reconstruct the training images from poisoned models for estimating Shapley value:

where $CE(\cdot)$ represents the Cross Entropy loss, $f(\cdot)$ represents the trained model, $y$ represents the target label to reconstruct images and $\alpha,\beta,\gamma$ are hyper-parameters.

Mixture-mode. Furthermore, because there is still a difference between clean images and recovered images, our experiments find that there is a larger accuracy degradation during data-free ShapPruning. Therefore, we propose a mixture-mode and try to combine information of Acc (accuracy) and ASR. We calculate Shapley value of Acc and ASR separately and find neurons with top-$k$ ASR Shapley value and bottom-$l$ Acc Shapley value to prune. And our experiments demonstrate that this way can help us locate the neurons which are only important to backdoor but not overall accuracy, locating poisoned neurons more accurately.

Finally, we summarize our framework illustrated in Fig. 1. We first use trigger reverse synthesis to get the reversed trigger and the target label. Then we inject the trigger into clean data (in the data-free situation, clean data is recovered from poisoned models), and get the reversed backdoor dataset. Then, using ASR as a measurement, we implement the accelerated Shapley value estimation method to get top-$k$ neurons with the largest Shapley value. Finally, we prune the target network with the top neurons, fine-tune the network with the clean data available, and offer backdoor-free networks to the users.

We compare ShapPruning with four existing methods Fine Pruning (FP) [25], Neural Cleanse (NC) [41], GangSweep (GS) [48] and DeepInspect (DI) [3] on the following five datasets (1).MNIST (2).CIFAR10 (3).CIFAR100 (4).GTSRB (5).YouTubeFace.

Attack configurations for BadNets. In our experiments, BadNets poisons images with a random colored square shown in Fig. 2. The trigger sizes are $5\times 5$ or $10\times 10$ to test our defense’s robustness against different trigger sizes. We resize the images to $96\times 96$, and thus, the trigger size is about $1\%$ of the image size and injection ratio is $1\%$. Our experiments are based on a VGG11-based model which is usually used in model compression tasks.

Attack configurations for Trojan Attack. We generate the trojan trigger shown in Fig. 5 with an initial square mask using gradient descent. Then, with the generated trigger, we fine-tune the trained model on the linear layers to inject backdoor into pre-trained models.

Attack configurations for Physical Key Attack. Physical Key Attack uses a pair of commodity glasses shown in Fig. 5 rather than a small square to inject backdoor into the model and can be more imperceptible.

Attack configurations for Input-Aware Attack. It uses a generator to generate sample-specific triggers. We set the Input-Aware Attack in all-to-one mode and attain a model with $99.41\%$ ASR with the same setting in [30].

Attack configurations for WaNet Attack. It uses warping-based triggers to generate sample-specific, undetectable triggers. We defend against WaNet based on the same setting in [31].

Available data. We suppose the defender can only get a small amount of clean data, specifically, one image per class in the few-shot setting e.g. only $10$ images available for MNIST and CIFAR10. Furthermore, we propose a more strict condition in Sec. 4.5 where only the poisoned models are available but no clean data to help mitigate the backdoor.

In this subsection, we compare ShapPruning with other defense methods and prove its effectiveness.

Trigger reverse synthesis. We first use trigger reverse synthesis to get the reversed trigger in Figs. 2 and 5 where we find the reversed triggers and original triggers are in a similar location of the images, but have a relative difference in shape and color, caused by the insufficiency of data. Also, trigger reverse synthesis penalizes L1 norm, causing reversed triggers smaller than the original ones. These mismatches lead to some performance degradation in the backdoor mitigation compared with defense with the original trigger. However, despite the differences, ShapPruning can still locate the poisoned neurons precisely and mitigate backdoor with different trigger sizes.

Pruning based on Shapley value. With the reversed poisoned data, we prune neurons in the order produced by $\epsilon$-greedy and compute ASR decline in output iteratively, finding $50$ average iterations are precise enough for estimating Shapley value and locating poisoned neurons. We compare our method with other three common methods including Fine Pruning (FP), Neural Cleanse (NC), and GangSweep (GS). From Tab. 1, ShapPruning mitigates backdoor best in poisoned models at the price of a tiny accuracy decline with only one image per class. On the contrary, other methods can’t clean backdoor attacks with that few images. Especially, all the other defenses perform weaker in MNIST and CIFAR10 with only $10$ clean images, which are fewer than the other two datasets, GTSRB and YouTubeFace.

We suppose the poor performance of Neural Cleanse (NC) and GangSweep (GS) is caused by both the gap between the original and reversed trigger, and the weak generalization of training with a small amount of clean data. We explain the trigger gap’s influence on mitigation degradation with the concepts from adversarial training. Neural Cleanse or GangSweep is similar to adversarial training [46, 35], which meets with performance degradation and poor generalization against different attacks. Thus, NC or GS, similar to adversarial training, behaves poorly with bigger trigger gaps, which is also found in [32]. Furthermore, we show Acc and ASR fluctuation during ShapPruning and Fine Pruning in Fig. 3. It demonstrates that ShapPruning can remove backdoor with only $1\%$ of total neurons, compared with about $25\%$ neurons removal in Fine Pruning. Fine Pruning, with that number of neurons pruned, may cause network structure changes and accuracy decline. Also, the insufficiency of clean data can weaken fine-tuning process and cause large accuracy fluctuation, especially in MNIST and CIFAR10 with only 10 images.

Defense against different attacks. We also defend against different attacks to test our method’s robustness. We first show reversed triggers in Fig. 5, where an obvious reversed gap is found. Based on the reversed triggers, we use different defense methods to mitigate backdoor, shown in Tab. 1. Also, we defend against Input-Aware Attack and WaNet Attack which both inject sample-specific triggers into images to activate the backdoor. Our experiment demonstrates that although there are different triggers for different samples, sample-specific attacks still rely on a small number of sensitive neurons to activate backdoor and our method can find them precisely.

Time consumption. We conducted our experiments on Titan RTX GPU with 24GB memory and recorded time consumption for different methods in mitigating backdoor attacks. We compare our method with Neural Cleanse in GTSRB and find our method only consumes 585.95 seconds with 50 average iterations’ Shapley estimation to get results in Tab. 1 after 671.13 seconds spent on trigger reverse. On the contrary, Neural Cleanse consumes 704.54 seconds which is 1.7x faster than our method. However, Neural Cleanse needs much more data and can’t completely remove triggers in the few-shot setting. Furthermore, our method is time-saving and needs much less clean data compared with training a clean model from scratch.

Previous methods need a large amount of clean data to mitigate backdoor, and thus, we want to explore the influence of the amount of clean data on backdoor mitigation. We compare mitigation results in Acc and ASR using Fine Pruning and ShapPruninig with different amounts of clean data in Fig. 4. Our experiment illustrates that backdoor mitigation performance improves with the amount of clean data rising and there is a significant fluctuation in ASR during Fine Pruning with just 1 image per class. We attribute it to the lack of data to activate some normal neurons and there may be low activation values in many neurons, some of which are not poisoned. Furthermore, since data insufficiency weakens fine-tuning, Fine Pruning performance declines further. Similarly, ShapPruning with 300 images for each class performs best. But with the improvement of the data amount, backdoor mitigation is promoted to a relatively small extent. Furthermore our method performs the best in different experiments among all these defense methods with the same amount of data.

In this subsection, we compare our method of $\epsilon$-greedy with T-MAB [13] which uses Bernstein error bounds [28, 29] and find our method can more precisely and efficiently locate neurons with the largest top-$k$ Shapley values under the same average iterations. We estimate Shapley value of neurons with $50$ average iterations using these two methods. Meanwhile, we use the Monte-Carlo estimation of $5000$ average iterations as the actual Shapley value for this task. We arranged neurons randomly before $30$ average iterations and set $\epsilon$ to be $0.5$ and $0.3$ in $30$-$40$ and after $40$ iterations in $\epsilon$-greedy. We then compare these two methods’ top-$50$ neurons and find them whether in the top-$70$ neurons in the MC experiment. Our experiments find that there are $46$ neurons in our methods’ top-$50$ neurons in top-$70$ of actual value. On the contrary, there are only $27$ neurons found in T-MAB. We attribute the inaccuracy of T-MAB to that Bernstein error bound is too conservative and consumes too much time to determine which neurons’ Shapley values are too small to calculate. On the contrary, our method combines exploration and utilization, getting more accurate estimations more efficiently.

The experiment results with the few-shot setting mentioned above demonstrates that ShapPruning is robust against different attacks and architectures. Then, we further introduce our ShapPruning framework into a data-free situation. Firstly, we try to reverse the training images from the poisoned model and show them in Fig. 6, where we compare our reversed images with model inversion attack [10] used in DeepInspect. Because DeepInspect’s model inversion method is usually used in shallower networks e.g. multilayer perceptron, the recovery results degrade sharply in VGG or ResNet. Furthermore, the similarity between the recovered images and real images influences trigger reverse and neuron activation, thus deciding backdoor defense performance. With the help of information in batch normalization layers, our method reconstructs better images.

Then we utilized the backdoor mitigation methods on the recovered images. Specifically, Fine Pruning (FP), Neural Cleanse (NC), and our ShapPruning method are conducted on our recovered images and DeepInspect (DI) is conducted with its original method. To test our methods’ robustness, we evaluate on different attacks and architectures. We defend against BadNets on CIFAR10 and CIFAR100 with VGG16 and ResNet34 separately. Furthermore, we also defend on the different attack e.g. Trojan Attack. The results are shown in Tab. 2. With better-recovered images and robustness of mixture-mode ShapPruning, our method mitigates backdoor clearly with a small accuracy decline.