Adversarial Unlearning of Backdoors via Implicit Hypergradient

Introduction

In backdoor attacks, adversaries aim to embed predefined triggers into a model during training time such that a test example, when patched with the trigger, is misclassified into a target class. For instance, it has been shown that one could use a sticker as the trigger to mislead a road sign classifier to identify STOP signs to speed limit signs (Gu et al., 2017). Such attacks pose a great challenge to deploy machine learning in mission-critical applications (Li et al., 2020c; 2021a).

Various approaches have been proposed to remove the effect of backdoor attacks from a poisoned model. One popular class of approaches (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019) is to first synthesize the trigger patterns from the model and then unlearn the triggers. However, these approaches presume that backdoor triggers only target a small portion of classes, thereby becoming ineffective when many classes are targeted by the attacker. Moreover, they suffer from high computational costs, as they either require synthesizing the trigger for each class independently or training additional models to synthesize the triggers all at once. Another line of works does not rely on trigger synthesis; instead, it directly mitigates the triggers’ effects via, for example, fine-tuning and pruning the model parameters (Liu et al., 2018a) and preprocessing the model input (Qiu et al., 2021). While these approaches are more efficient than the trigger-synthesis-based approaches, they cannot maintain a good balance between robustness and model accuracy due to the unawareness of potential triggers. Recent work (Li et al., 2020b) proposes to leverage a teacher model to guide fine-tuning. However, our empirical studies find that the effectiveness of this approach is particularly sensitive to the underlying attack and data augmentation techniques utilized to enrich the fine-tuning dataset. Overall, it remains a challenge to design a defense that achieves a good balance between model accuracy, robustness, and computational efficiency.

To address the challenge, we propose a minimax formulation to remove backdoor triggers from a poisoned model. The formulation encompasses prior works on trigger synthesis-based defense, which solves the inner and outer problems independently. Moreover, the formulation does not make any assumption about the backdoor trigger beyond a bounded norm constraint, thus remaining effective across various attack settings. To solve the minimax, we propose an Implicit Bacdoor Adversarial Unlearning (I-BAU) algorithm based on implicit hypergradients. Unlike previous work, which breaks down the minimax into separate inner and outer optimization problems, our algorithm derives the implicit hypergradient to account for the interdependence between inner and outer optimization and uses it to update the poisoned model. We theoretically analyze the convergence of the proposed algorithm. Moreover, we investigate the generalization error of the minimax formulation, i.e., to what extent the robustness acquired by solving the minimax generalizes to unseen data in the test time. We present the generalization bounds for both linear models and neural networks. We conduct a thorough empirical evaluation of I-BAU by comparing it with six state-of-art backdoor defenses on seven backdoor attacks over two datasets and various attack settings, including the common setting where the attacker targets one class and an important but underexplored setting where multiple classes are targeted. I-BAU’s performance is comparable to and most often significantly better than the best baseline. Particularly, its performance is more robust to the variation on triggers, attack settings, poison ratio, and clean data size. Moreover, I-BAU requires less computation to take effect; particularly, it is more than 13X faster than the most efficient baseline in the single-target attack setting. It can still remain effective in the extreme case where the defender can only access 100 clean samples—a setting where all the baselines fail to produce acceptable results.

Related Work

Backdoor Attacks. Backdoor attacks evolve through three stages. 1) Visble triggers using unrelated patterns (Gu et al., 2017; Chen et al., 2017), or optimized triggers (Liu et al., 2018b; Bagdasaryan & Shmatikov, 2021; Zhao et al., 2020; Garg et al., 2020) for higher attack efficacy. While this line’s attack methods achieve high attack success rates and clean accuracy, the triggers are visible and thus easily detected by human eyes. 2) Visually invisible triggers via solving bilevil optimizations regarding the $l_{p}$ norm (Li et al., 2020a), or adopting nature optical effects (Liu et al., 2020; Nguyen & Tran, 2021), and Clean label attacks via feature embeeding (Turner et al., 2019; Saha et al., 2020) for better stealthiness. For most work from this line, the triggers or the poisons can evade the detection from manual efforts. 3) Invisible triggers considering other latent spaces, e.g., the frequency domian (Zeng et al., 2021; Hammoud & Ghanem, 2021) or auto-encoder feature embedding (Li et al., 2021b), which improved the stealthiness by breaking the fundamental assumptions of a list of defenses. This paper incorporates successful attacks from these major groups and we show our method provides an effective, and generalizable defense.

Backdoor Defenses. Backdoor defenses can be divided into four categories: 1) Poison detection via outlier detection regarding functionalities or artifacts (Gao et al., 2019; Chen et al., 2018; Tran et al., 2018; Koh & Liang, 2017; Chou et al., 2020; Zeng et al., 2021), which rely on the modeling of clean samples’ distribution. 2) Poisoned model identification identifies if a given model is backdoored or not (Xu et al., 2019; Wang et al., 2020). 3) Robust training via differential privacy (Du et al., 2019; Weber et al., 2020) or ensembled/decoupled pipeline (Levine & Feizi, 2020; Jia et al., 2020; 2021; Huang et al., 2022). This line of work tries to achieve general robustness to withstand outlier’s impact, but may suffer from low clean accuracy. 4) Backdoor removal via trigger synthesising (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019), or preprocessing & finetuning (Li et al., 2020b; Borgnia et al., 2020; Qiu et al., 2021). This line of work serves as the fundamental solution given a poisoned model, but there is still no satisfying solution to attaining robust results across different datasets and triggers. In this work, we propose a minimax formulation and a solver for backdoor removal. We attempt to include all cutting-edge methods under this category for comparison.

Problem Formulation

We consdier that the defender is given a poisoned classifier $f_{\theta_{\text{poi}}}$ and an extra set of clean data $D=\{(x_{i},y_{i})\}_{i=1}^{n}$ from $\mathcal{D}$. With $f_{\theta_{\text{poi}}}$ and $D$, the defender aims to build a model $f_{\theta^{*}}$ immunne to backdoors, i.e., $f_{\theta^{*}}(x+\delta)=f_{\theta^{*}}(x)$. Note that the size of available clean examples is assumed to be much smaller than the size necessary to retrain a high-accuracy model from scratch.

To achieve the defense goal, we want the resulting classifier to maintain the correct label even if the attacker patches the backdoor trigger to a given input. This intuition naturally leads to the following minimax optimization formulation of backdoor removal:

where $L$ is the loss function. Note that this formulation looks similar to adversarial training for evasion attacks (a.k.a. adversarial examples) (Madry et al., 2017). The main distinction is that in evasion attacks, the adversarial perturbation is specific to an individual data point, while in backdoor attacks, the same perturbation (i.e., the backdoor trigger) is expected to cause misclassifications for any examples upon being patched. Hence, in the formulation for backdoor attacks, the same trigger, $\delta$, is applied to every clean sample $x_{i}$, whereas, in the minimax formulation for evasion attacks, the perturbation is optimized independently for each sample (see Eq. (2.1), Madry et al. (2017)).

The minimax formulation for backdoor removal has many advantages. 1), it gives us a unifying perspective that encompasses much prior work on backdoor removal. The formulation comprises an inner maximization problem and an outer minimization problem. Both of these problems have a natural interpretation in the security context. The inner maximization problem aims to find a trigger that causes a high loss for predicting the correct label. This aligns with the problem of a backdoor attack that misleads the model to predict a predefined incorrect target label. In our formulation, we choose to maximize the prediction loss for the correct label instead of using the exact backdoor attack objective of minimizing the prediction loss associated with the target label. We make this design choice because, in reality, the defender does not know the target labels selected by the attacker. The outer minimization problem is to find model parameters so that the “adversarial loss” given by the inner attack problem is minimized. Existing backdoor removal approaches based on trigger synthesis and unlearning the synthesized trigger (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019) can be considered as a special instance of this minimax formulation, where they neglect the interdependence between the inner and outer optimization and solve them separately. 2), the formulation does not make any assumption on the backdoor trigger beyond the bounded norm constraint. By contrast, much of the existing work makes additional assumptions about backdoor triggers in order to be effective. For instance, synthesis-based approaches often assume that the classes coinciding with the target classes of the triggers account for only a tiny portion of the total, making those approaches ineffective in countering multiple target cases. 3), the formulation provides a quantitative measure of backdoor robustness. In particular, when the parameters $\theta$ yield a (nearly) vanishing loss, the corresponding model is perfectly robust to attacks specified by our attack model on $D$. We will discuss the generalization properties of this formulation in Section 5. Using the results developed there, we can further reason about the robustness on the data distribution $\mathcal{D}$.

Algorithm

Given the empirical success of adversarial training for defending against evasion attacks (Li et al., 2022), one may wonder whether we can solve the minimax for the backdoor attack via adversarial training. Adversarial training keeps alternating between two steps until the loss converges: (1) solving the inner maximization for a fixed outer minimization variable; and (2) solving the outer minimization by taking a gradient of the loss evaluated at the maximum. Practically, adversarial training proceeds by first generating adversarial perturbations and then updating the model using the gradient calculated from the perturbed data. For backdoor attacks, the adversarial perturbation needs to fool the model universally on all inputs. Hence, a natural algorithm to solve the backdoor minimax problem is to tune the model with universal adversarial perturbations. Universal adversarial perturbations have been studied in the past, and there exists an off-the-shelf technique to create such perturbations (Moosavi-Dezfooli et al., 2017). However, we found that this simple algorithm is highly unstable. Figure 1 illustrates the change of the model accuracy and robustness (measured in terms of the attack success rate (ASR)) for 20 runs as adversarial training proceeds. It can be seen that the ASR varies significantly across different runs. Within a single run, while the ASR decays as a whole, the decrement is mostly erratic and slow.

There are two issues with naive adversarial training with universal perturbations. First, the performance of the existing universal perturbation algorithm is unstable. At its core, it generates adversarial perturbations for each example and adds the perturbations together. The addition may not always lead to a perturbation that can fool all examples; instead, the addition operation may cancel the effect of individual perturbations. More importantly, the decoupling between solving the inner maximization and the outer minimization in adversarial training is often justified by Danskin’s Theorem (Danskin, 2012), which states that the gradient of the inner function involving the maximization term is simply given by the gradient of the function evaluated at this maximum. In other words, letting $\delta^{*}=\operatorname*{arg\,max}_{||\delta||\leq C_{\delta}}H(\delta,\theta)$, we have $\nabla_{\theta}\max_{||\delta||\leq C_{\delta}}H(\delta,\theta)=\nabla_{\theta}H(\delta^{*},\theta)$. However, in practice, due to stochastic gradient descent, it is impossible to solve the inner maximization optimally. Worse yet, the underperformance of the existing universal perturbation algorithm makes it even harder to approach the maximum. Moreover, Danskin’s Theorem only holds for convex loss functions. Due to the violation of maximum condition and convexity, it is unsuitable for utilizing Danskin’s Theorem, and hence, adversarial training is not justified.

We propose an algorithm to solve the minimax problem in (1) that does not require the loss function to be convex and is more robust to the approximation error caused by not being able to solve the inner maximization problem to global or even local optimality. Let $\delta(\theta)$ be an arbitrary suboptimal solution to $\max_{||\delta||\leq C_{\delta}}H(\delta,\theta)$. Let $\psi(\theta)\coloneqq H(\delta(\theta),\theta)$ be the objective function evaluated at the suboptimal point; if $\delta(\theta)$ is a stationary point, we make an distinction by defining the corresponding function as $\psi^{*}(\theta)$. Denote $\nabla_{1}H(\delta,\theta)$ and $\nabla_{2}H(\delta,\theta)$ as the partial derivatives with respect to the first and second variable, respectively, and $\nabla_{1}^{2}H(\delta,\theta)$ and $\nabla_{1,2}^{2}H(\delta,\theta)$ as the second-order derivatives of $H$ with respect to the first variable and the mixed variables, respectively. The gradient of $\psi$ with respect to $\theta$ is given by

The direct gradients are easy to compute. For instance, suppose $H$ is the loss of a neural network, then $\nabla_{1}{H(\delta(\theta),\theta)}$ and $\nabla_{2}{H(\delta(\theta),\theta)}$ are the gradients with respect to the network input and the model parameters, respectively. However, the response Jacobian is intractable to obtain because we must compute the change rate of the suboptimal solution to the inner maximization problem with respect to $\theta$. When $\delta(\theta)$ satsifies the first-order stationarity condition, i.e., $\nabla_{1}{H(\delta(\theta),\theta)}=0$, and assuming that $\nabla_{1}^{2}H(\delta(\theta),\theta)$ is invertible, the response Jacobian is given by

which follows from the implicit function theorem. Note that $\nabla\delta(\theta)$ plays a role in the Hessian in (2), in the sense that it adjusts each dimension of the gradient $\nabla_{1}{H(\delta(\theta),\theta)}$ to the importance of that dimension. Hessian expresses the importance via curvature, whereas $\nabla\delta(\theta)$ measures the importance based on the sensitivity to the change of $\theta$. A widely known fact from the optimization literature is that second-order optimization algorithms are tolerant to the inaccuracy of Hessian (Byrd et al., 2011). Based on this intuition, we propose to approximate $\nabla\delta(\theta)$ with a suboptimal solution by (3). In practice, the approximation is addressed with an iterative solver of limited rounds (e.g., conjugated gradient algorithm (Rajeswaran et al., 2019) or fixed-point algorithm (Grazzi et al., 2020)) along with the reverse mode of automatic differentiation (Griewank & Walther, 2008).

Theoretical Analysis

In this section, we analyze the convergence of the I-BAU. We also study the generalization properties of the minimax backdoor removal formulation. Assuming that by solving the minimax, we obtain a model such that all points in the clean set $D$ are robust to triggers of a specific norm, we would like to reason about to what extent an unseen point from the underlying data distribution $\mathcal{D}$ is trigger-robust.

Convergence Bound: Suppose that $H(\cdot,\theta)$ is $\mu_{H}(\theta)$-strongly convex and $L_{H}(\theta)$-Lipschitz smooth, where $\mu_{H}(\cdot)$ and $L_{H}(\cdot)$ are continuously differentiable. Define $\alpha(\delta)=\frac{2}{L_{H}(\theta)+\mu_{H}(\theta)}$, and let $\delta(\theta)$ be the unique fixed point of $\delta+\alpha(\theta)\nabla_{1}H(\delta,\theta)$. Then, there exists $L_{H,\theta}$ s.t. $\sup_{\left\|\delta\right\|\leq 2C_{\delta}}\left\|\nabla_{1}H(\delta,\theta)\right\|\leq L_{H,\theta}$ (Grazzi et al., 2020). We make the following assumptions:

Lipschitz continuity of direct gradients: $\nabla_{1}H(\cdot,\theta)$ and $\nabla_{2}H(\cdot,\theta)$ are Lipschitz continuous functions of $\theta$ (with Lipschitz constants $\eta_{1,\theta}$ and $\eta_{2,\theta}$, repectively).

Lipschitz continuity and norm boundedness of second-order terms: $\nabla_{1}^{2}H(\cdot,\theta)$ is $\hat{\rho}_{1,\theta^{-}}$ Lipschitz continuous, and $\nabla_{2,1}^{2}H(\cdot,\theta)$ is $\hat{\rho}_{2,\theta}$-Lipschitz continuous. Also, the cross derivative term is norm bounded by $L_{h,\theta}\geq\left\|\nabla_{21}^{2}H(\delta(\theta),\theta)\right\|$.

Asymptotic convergence of $\delta^{t}(\theta)$ to $\delta(\theta)$: $\left\|\delta^{t}(\theta)-\delta(\theta)\right\|\leq\rho_{\theta}(t)\left\|\delta(\theta)\right\|$, where $\rho_{\theta}(t)$ is such that $\rho_{\theta}(t)\leq 1$, and $\rho_{\theta}(t)\rightarrow 0$ as $t\rightarrow+\infty$.

where $q_{\theta_{i}}\coloneqq\max\left\{1-\alpha(\theta_{i})\mu_{H}(\theta_{i}),\alpha(\theta_{i})L_{H}(\theta_{i})-1\right\}$, $c_{1}(\theta_{i}):=\left(\eta_{2,\theta_{i}}+\frac{\eta_{1,\theta_{i}}L_{h,\theta_{i}}\alpha(\theta_{i})}{1-q_{\theta_{i}}}\right)C_{\delta}$, $c_{2}(\theta_{i}):=L_{H,\theta_{i}}C_{\delta}\left(L_{H}(\theta_{i})\|\nabla\alpha(\theta_{i})\|+\hat{\rho}_{2,\theta_{i}}\alpha(\theta_{i})\right)+\frac{\hat{\rho}_{1,\theta_{i}}L_{H,\theta_{i}}L_{h,\theta_{i}}C_{\delta}\alpha(\theta_{i})^{2}}{1-q_{\theta_{i}}}$, and finally $c_{3}(\theta_{i}):=\frac{L_{H,\theta_{i}}L_{h,\theta_{i}}\alpha(\theta_{i})}{1-q_{\theta_{i}}}$.

As the inner epoch number $t$ increases, the estimated gradient becomes more accurate. Under the assumption that $H(\cdot,\theta)$ is convex, the solution converges. We show the full proof in Appendix A.1.

For any linear model $\theta$ and $\xi\in\left(0,1\right)$, the following holds with a probability of at least $1-\xi$ over $\left((x_{i},y_{i})\right)_{i=1}^{n}$:

When the number of clean samples, $n$, gets larger, the generalizability of the adversarial unlearning on linear models becomes better. It is also interesting to compare the adversarial generalization bound for backdoor attacks with the bound for evasion attacks in (Yin et al., 2019), which has an additional $\sqrt{d}$ factor in the second term of the bound. Hence, for inputs of large dimensions, the adversarial training for backdoor attacks is expected to be more generalizable than that for evasion attacks. The detailed proof is shown in the Appendix A.2.1.

For any neural network model $\theta$ and $\xi\in\left(0,1\right)$, the following holds with a probability of at least $1-\xi$ over $(\left(x_{i},y_{i})\right)_{i=1}^{n}$:

When the number of clean samples, $n$, gets larger, the generalizability of the unlearning on neural networks becomes better. Compared with the generalization bound for regular training in (Bartlett et al., 2017), our bound has an additional $n$ term in $\sqrt{\ln(2W(W+n))}$ and $(\|X\|_{p}+\sqrt{n})$, which indicates harder generalizability than regular learning problem. However, empirically, we find our solution, I-BAU, is still of excellent generalizability even if only 100 clean samples are accessible. Our proof is enabled by recognizing that the backdoor perturbation, $\delta$, is required to be the same across all the poison samples and therefore can be treated as additional dimensions of the model parameters. The proof implements Dudley entropy integral to bound the Rademacher complexity. The full details are deferred to Appendix A.2.2. We also empirically validate Theorem 6 against $W$ and $n$ in Appendix A.2.3.

Evaluation

Our evaluation aims to answer the following questions: (1) Efficacy: Can I-BAU effectively remove various backdoor triggers? (2) Stability: Can I-BAU be consistently effective across different runs? (3) Sensitivity: How sensitive is I-BAU to the poison ratio and the size of the available clean set? (4) Efficiency: How efficient is I-BAU? We use a simplified VGG model (Simonyan & Zisserman, 2014) as the target model for all experiments and set $C_{\delta}=10$ as the norm constraint for implementing I-BAU. The details of experimental settings and model architecture can be found in Appendix A.4.

We evaluate I-BAU’s efficacy against three attack settings: 1) One-trigger-one-target attack, in which the attacker uses only one trigger, and there is only one target label. This setting is most commonly considered in existing defense works. 2) One-trigger-all-to-all attack, in which the attacker uses only one trigger but aims to mislead predictions from $i$ to $i+1$, where $i$ is the ground truth label (Gu et al., 2017). 3) Multi-trigger-multi-target attack, where the attacker uses multiple distinct triggers, each targeting a different label. We will refer to the first two settings as “one-trigger setting” and the last setting as “multi-trigger setting.” For each setting, we study seven different backdoor triggers in the main text, namely, BadNets white square trigger (BadNets) (Gu et al., 2017), Hello Kitty blending trigger (Blend) (Chen et al., 2017), $l_{0}$ norm constraint invisible trigger ($l_{0}$ inv) (Li et al., 2020a), $l_{2}$ norm constraint invisible trigger ($l_{2}$ inv) (Li et al., 2020a), Smooth trigger (frequency invisble trigger) (Smooth) (Zeng et al., 2021), Trojan square (Troj SQ) (Liu et al., 2018b), and Trojan watermark (Troj WM) (Liu et al., 2018b). These trigger patterns are illustrated in Figure 3 in the Appendix. Given that I-BAU’s fundamental formulation takes backdoor noise as additive noise, one may be curious about how I-BAU’s performance mitigates non-additive backdoor attacks. We have included case studies on using I-BAU mitigating three non-additive triggers (semantical replacement, WaNet (Nguyen & Tran, 2021), IAB attack (Nguyen & Tran, 2020)) and hidden trigger attack (Saha et al., 2020) (non-additive poisoning) to illustrate the effectiveness (Appendix A.5). For all experiments in the mian text, we adopt a large poison ratio of 20%, a severe attack case for defenders. To acquire a poisoned model, we train on the poisoned dataset for 50 epochs.

We compare I-BAU with six state-of-art defenses: Neural Cleanse (NC) (Wang et al., 2019), Deepinspect (DI) (Chen et al., 2019), TABOR (Guo et al., 2019), Fine-pruning (FP) (Liu et al., 2018a), Neural Attention Distillation (NAD) (Li et al., 2020b), and Differential Privacy training (DP) (Du et al., 2019). Note that DP requires access to the poisoned data; hence, its attack model is different from the attack model of the other baselines and our method. In the following tables, we use [ASR] to mark the results that fail to reduce the attack success rate (ASR) below 20%; we use [ACC] to mark the results where the accuracy (ACC) on clean data drops by more than 10%; we use [ACC or ASR] to mark the best result among the six baselines; finally, we use [ACC or ASR] to mark the results from I-BAU that is comparable to or significantly better than the best result among the baselines. We consider I-BAU’s result as comparable if 1) the ACC gap is less than 1%, 2) the ASR gap is less than 4%, or the ASR of I-BAU is close to the label percental (i.e., the probability of random guessing for outputting the target label, 10% for the CIFAR-10, 2.3 % for the GTSRB).

One-trigger Setting: Table 1 presents the defense results on the CIFAR-10 dataset. CIFAR-10 contains 60,000 samples. We use 50,000 samples as training data, among which 10,000 samples are poisoned. We used 5,000 separate samples as the clean set accessible to the defender for conducting each defense (e.g., via unlearning, finetuning, trigger synthesis) except DP. The remaining 5,000 samples are used to assess the defense result. The left column depicts the attack cases. The first seven cases each contain only one target label. The all-to-all case represents the case in which we use the BadNets trigger to carry out the one-trigger-all-to-all attack. As shown in the table, all single-target attacks are capable of achieving an ASR close to 100% with no defenses. It is empirically observed that the ASR of the all-to-all attack is upper-bounded by the ACC. Intuitively, the model needs to classify the clean samples correctly to classify the corresponding backdoored samples with triggers to the next class. Thus, we tune the model to produce an ASR that is close to the ACC.

Model performance on CIFAR-10 is particularly sensitive to finetuning and unlearning, which will result in a decrease in the ACC in general. Thus, for a fair comparison, we show the I-BAU results in Table 1 when the ACC falls to the same level as the most effective baseline. For instance, for BadNets attacks, we present the ASR result of I-BAU when the ACC of I-BAU decreases to a value similar to the ACC of TABOR, which is the best defense baseline against BadNets.

As shown in Table 1, the performance of the baselines exhibits large variance across different triggers. Specifically, each baseline underperforms in at least three attack cases (marked by ( [ASR] or [ACC]) ) The defenses based on trigger synthesis (including NC, DI, and TABOR) failed to confront the all-to-all attack case, where all the labels were targeted. This is because this setting violates their assumption that target classes only account for the minority of training data. Particularly, TABOR fails to detect any backdoor triggers in this case). For DP, we fine-tune a noise multiplier effective to mitigate all attacks, yet also leads to bad ACC. On the other hand, I-BAU robustly mitigates all triggers without significantly affecting the ACC. Compared to the best result among the state-of-art baselines ( [ACC or ASR] ), I-BAU’s is comparable to or much better ( [ACC or ASR] ) under most of the settings. The only setting where I-BAU underperforms the best baseline is Smooth triggers. FP is the only effective baseline in this setting. But interestingly, this setting is also the only setting where FP is effective; in other words, its performance is highly dependent on the underlying trigger.

Table 2 shows the evaluation on the GTSRB dataset, which contains 39,209 training data and 12,630 test data of 43 different classes. The experimental setting is the same as the one on CIFAR, except for the data split, which is discussed in the Appendix A.4.1. We find that model performance on GTSRB is not sensitive to the tuning procedure. As 5,000 clean samples are available to the defender, the ACC of the model increases after incorporating the defense. NAD’s performance highly depends on the pre-designed preprocessing procedure adopted during fine-tuning. While it produces the best defense results for some settings on CIFAR-10, it suffers from a large degradation of ACC on GTSRB. Once again, I-BAU is the only defense method that remains effective for all attack settings.

Multi-trigger Setting: Table 3 shows the results on CIFAR and GTSRB in a 7-trigger-7-target setting, in which each trigger targets a different label. We adopt the same poison ratio for each (20%) and then combine the seven distinct poisoned datasets to obtain the final datasets (size 350,000 for CIFAR-10, and 274,463 for the GTSRB). We show the average ASR and the specific ASR.

On CIFAR-10, since the target classes are no longer the minority (i.e., 7/10 labels are targeted), the baselines based on trigger synthesis, which make the minority assumption, are ineffective. Particularly, NC fails to detect any triggers in this setting. NAD is the only baseline able to evaluate well on CIFAR-10, and our methods achieve comparable performance. However, similar to the one-trigger setting, NAD’s performance requires the customization of preprocessing to different datasets. The default preprocessing cannot maintain the same performance on GTSRB; e.g., the random flipping—a beneficial preprocessing step for CIFAR—completely alters the semantics of images in GTSRB. On the other hand, I-BAU effectively reduces ASR while maintaining the ACC for both datasets with no changes needed. Moreover, in the Appendix, we visualize the distribution of poisoned and clean examples in the feature space before and after applying I-BAU, which shows that I-BAU can place the poisoned examples back in the cluster with correct labels.

2 Stability

In Section 4, we mentioned that the naive heuristic based on adversarial learning with existing universal perturbation suffers from erratic performance. Here, we aim to evaluate whether I-BAU can overcome this problem. We adopt the same setting for the two on the CIFAR-10 using BadNets and observe the change in ACC and ASR over different iterations for each run. As shown in Figure 1, the ASR decreases very quickly; indeed, the attack can be mitigated by just one single iteration of outer minimization. Also, within every single run, the ASR decreases more smoothly compared to the naive heuristic. Notably, I-BAU attains a slightly higher ACC than the naive heuristic.

3 Sensitivity

We evaluate the sensitivity of each defense to the poison ratio and the size of clean samples. The experiments were performed on Trojan WM on CIFAR-10 to exemplify the results. Table 4 shows the sensitivity to the poison ratio. Observe that as the poison ratio drops, TABOR becomes ineffective at synthesizing triggers and ultimately fails to remove the triggers; NC, however, becomes the most effective baseline. While DP’s ASR is significantly worse than the effective baselines, its performance gets slightly better as the poison ratio drops. DP attempts to restrict the impact of each training data point on the learning outcome via noising the gradient. As a side effect, it hinders learning from good data, thereby leading to poor ACC in general. Compared to the baselines, I-BAU exhibits the least sensitivity to the poison ratio, maintaining good ACC and ASR across different ratios.

Table 5 shows sensitivity to available clean data’s size. As DP is independent from the clean set (which trains a general robust model against all perturbations from scratch), we drop it from the comparison. We see that as the number of clean samples drops, the performance of all defenses declines. I-BAU is least sensitive to the size of clean samples; even in extreme case with only 100 clean samples available, I-BAU still maintains an acceptable performance of removing backdoors.

4 Efficiency

Finally, we compare the efficiency of defenses. We use the one-trigger-one-target attack setting to exemplify the result. Table 6 shows the average runtime for each defense to take effect (i.e., mitigating the ASR to $<20\%$). As I-BAU can mitigate the attacks in one iteration, it only takes 6.82 s on average on CIFAR-10 and 7.84 s on GTSRB. Note that NC and TABOR need to go through each label independently for trigger synthesis; thus, the total runtime is proportional to the number of labels. Especially, it takes much more time for the two to take effect on GTSRB than on CIFAR-10. In difficult attack cases, such as all-to-all attacks and multi-trigger-multi-target attacks, I-BAU requires more rounds to be operative but remains the only effective one across all settings with high efficiency and efficacy. The Appendix shows the performance of I-BAU over different rounds under multi-target attack cases. Theoretical analysis and comparison of the time complexity of I-BAU are presented in Appendix A.3.3.

Conclusion

In this work, we proposed a minimax formulation of the backdoor removal problem. This formulation encompassed the objective of the existing unlearning work without making assumptions about attack strategies or trigger patterns. To solve the proposed minimax, we proposed I-BAU using implicit hypergradients. A theoretical analysis verified the convergence and generalizability of the proposed I-BAU or minimax formulation. A comprehensive empirical study established that I-BAU is the only generalizable defense across all evaluated eleven backdoor attacks. The defense results are comparable to or exceed the best results obtained by combining six existing state-of-the-art techniques. Meanwhile, I-BAU is less sensitive to poison rate and is effective in extreme cases where the defender has access to only 100 clean samples. Finally, under the standard one-trigger-one-target circumstances, I-BAU can achieve an effective defense in an average of 7.35 s.

References

Appendix A Appendix

Consider the minimax formulation of backdoor unlearning defined in (1). To simply the notation, we will use $\theta$ instead of $\theta_{i}$, unless otherwise specified. We start by defining $\Phi(\delta,\theta)=\delta+\alpha(\theta)\nabla_{1}H(\delta,\theta)$, where $H$ (sum of cross-entropies) is twice continuously differentiable w.r.t. both $\delta$ and $\theta$. Recall that $H(\cdot,\theta)$ is $\mu_{H}(\theta)$-strongly convex and $L_{H}(\theta)$-Lipschitz smooth, where $\mu_{H}(\cdot)$ and $L_{H}(\cdot)$ are continuously differentiable. By setting the step size $\alpha(\theta)=\frac{2}{L_{H}(\theta)+\mu_{H}(\theta)}$, it can be shown that $\Phi(\cdot,\theta)$ is a contraction for some coefficient $q_{\theta}\coloneqq\max\left\{1-\alpha(\theta)\mu_{H}(\theta),\alpha(\theta)L_{H}(\theta)-1\right\}$. The optimal choice of the step-size leads to $q_{\theta}=\frac{\kappa(\theta)-1}{\kappa(\theta)+1}$, where $\kappa(\theta)=\frac{L_{H}(\theta)}{\mu_{H}(\theta)}$. Note that, for every $i\in(1,K)$, $\theta\in\Theta$,

Hence, the condition number of $\nabla_{1}^{2}H\left(\delta_{i}(\theta),\theta\right)$ is smaller than $\kappa(\theta)$ (Grazzi et al., 2020).

Let $\partial_{1}\Phi(\delta,\theta)$ and $\partial_{2}\Phi(\delta,\theta)$ denote the partial Jacobians of $\Phi$ at $(\delta,\theta)$ w.r.t. the first and the second variables, respectively. We can write the derivatives of $\Phi$ as:

When evaluated at $(\delta(\theta),\theta)$, the partial Jacobian w.r.t. the second variable, $\partial_{2}\Phi(\delta(\theta),\theta)$, can be simplified as:

Thus, $\|\partial_{2}\Phi(\delta(\theta),\theta)\|=\alpha(\theta)\|\nabla_{21}^{2}H(\delta(\theta),\theta)\|$. Following the notations from (Grazzi et al., 2020), we create the bound of the partial Jacobian of $\Phi$ to be $L_{\Phi,\theta}\geq\|\partial_{2}\Phi(\delta(\theta),\theta)\|$. By our assumption, the bound for the cross derivative term $\delta$ is $L_{h,\theta}\geq\left\|\nabla_{21}^{2}H(\delta(\theta),\theta)\right\|$. Hence, we can choose:

Let $\Delta_{\partial_{1}\Phi}\coloneqq\left\|\partial_{1}\Phi\left(\delta_{1},\theta\right)-\partial_{1}\Phi\left(\delta_{2},\theta\right)\right\|$ and $\Delta_{\partial_{2}\Phi}\coloneqq\left\|\partial_{2}\Phi\left(\delta_{1},\theta\right)-\partial_{2}\Phi\left(\delta_{2},\theta\right)\right\|$. By assumption on the Lipschitz continuity and norm boundedness of second-order terms, we have :

Thus, $\partial_{1}\Phi(\cdot,\theta)$ is Lipschitz continuous with constant

and $\partial_{2}\Phi(\cdot,\theta)$ is Lipschitz continuous with constant

Recall the result from (Grazzi et al., 2020):

The approximate hypergradient has an error bounded by

The proof of Theorem 1 uses the inequality from Lemma 15 with the constants specified in (10), (13), and (14).

A.2 Generalization Bounds

According to (Yin et al., 2019), the population risk against a perturbation $\delta$ is given by:

Note that $R_{\gamma}(\theta)$ and $\hat{R}_{\gamma}(\theta)$ are the upper bounds of the fraction of errors on the source distribution and the dataset used for unlearning, $D_{san}$, respectively. Finally, given a set of real-valued functions $\mathcal{H}$, recall the Rademacher complexity as:

where $\varsigma_{j}\in\left\{\pm 1\right\}$ is the Rademacher random variable. The following bound of the adversarial unlearning can be derived using standard tools in Rademacher complexity.

Given unlearned models $\Theta$ with $\theta\in\Theta$ and some margin $\gamma>0$, define:

The following holds with the probability of at least $1-\xi$ over the clean dataset, $D_{san}$ (see Algorithm 1) for every $\theta\in\Theta$:

To instantiate this bound, we only need to control the Rademacher complexity, $\Re\left((\Theta_{\gamma})_{\mid D_{san}}\right)$, for linear models and neural networks.

Define the set of linear, poisoned models under perturbation $\delta$:

where $\theta$ can be regarded as a weight matrix $\left\|\theta\right\|$ bounded by $C_{\theta}$. Recall that the perturbation norm $\left\|\delta\right\|$ is bounded by $C_{\delta}$, and the input $l2$ norm $\left\|x\right\|_{2}$ is bounded by $\chi$. We can proceed to evaluate the upper bound of the Rademacher complexity:

In particular, $\mathcal{A}$ can be bounded by:

Similarly, $\mathcal{B}$ can be bounded by:

Thus, we can bound the Rademacher complexity as following:

Substituting (27) to the (22) completes the proof of Theorem 5.

A.2.2 Proof for neural networks

To instantiate the bound with Rademacher complexity for neural networks, we will follow the idea from (Bartlett et al., 2017) and use covering numbers to bound the Rademacher complexity, $\Re\left((\Theta_{\gamma})_{\mid D_{san}}\right)$. Let $\mathcal{N}(U,\epsilon,\|\cdot\|)$ denotes the least cardinality of any subset $V\subseteq U$ that covers U at a scale $\epsilon$ with norm $\left\|\cdot\right\|$, i.e., $\sup_{A\in U}\min_{B\in V}\|A-B\|\leq\epsilon$. Recall the Dudley entropy integral below.

Assume that the input values are norm bounded by $1$,

Thus, the derivation of the generalization bound of (1) with neural networks is reduced to the problem of finding the bound for the covering number of the set of all neural networks, $\mathcal{N}\left((\Theta_{\gamma})_{\mid D_{san}},\epsilon,\|\cdot\|_{2}\right)$. The full problem can be divided into four steps: (I) finding a matrix-covering bound for the affine transformation of the input layer of poisoned models, conducted in this section; (II) finding a matrix-covering bound for the affine transformation of the following layers after the first layer, provided in (Bartlett et al., 2017); (III) obtaining a covering number bound for entire networks using induction on layers; (IV) accomplishing the complete generalization bound for neural networks by applying the covering number to (22) and (28).

For $p\leq 2$, the results from (Bartlett et al., 2017) implies:

Defining $\mathcal{C}$ as the desired cover of the first layer $\hat{X}\hat{A}_{1}$:

where, $k\coloneqq\left\lceil\frac{{a_{0}}^{2}(1+mn^{\frac{1}{2}}C_{\delta})^{2}(\|X\|_{p}+n^{\frac{1}{2}})^{2}m^{\frac{2}{r}}}{{\epsilon_{1}}^{2}}\right\rceil$. By construction, $|\mathcal{C}|\leq[N_{0}]^{k}$. Now, we prove that $\mathcal{C}$ is the desired cover set. The technique is generalized from (Bartlett et al., 2017) to backdoor unlearning.

Consider the case of $\left\|A_{1}\right\|_{2,1}$, i.e., $(q,s)=(2,1)$, and let $\left\|A_{1}\right\|_{2,1}\leq a_{0}$, then we get:

Subsequently, the bound of $\left\|\hat{A}_{1}\right\|_{2,1}$ can be derived from:

Therefore, substituting (38) to (37) gives us the bound:

Let $a_{1}=a_{0}\left(1+mn^{1/2}C_{\delta}\right)$. Given the case of $\left\|A_{1}\right\|_{2,1}$, we can obtain the bound for $\|\hat{B}\|_{1}$:

Thus, combining (31) and following the Maurey lemma (Pisier (1981), Zhang (2002), Lemma 1), we have:

which shows that the desired cover element is in $\mathcal{C}$.

Step (III): The Whole Network Covering Bound. Recall that the whole neural network is structured as follows: $F_{\theta}(x)\coloneqq\sigma_{L}\left(A_{L}\sigma_{L-1}\left(A_{L-1}\ldots\sigma_{1}\left(A_{1}x\right)\ldots\right)\right)$, where $\sigma_{i}$ is $\varrho_{i}$-Lipschitz.

Define two sequences of vector spaces $\mathcal{V}_{1},\ldots,\mathcal{V}_{L}$ and $\mathcal{W}_{2},\ldots,\mathcal{W}_{L+1}$, where $\mathcal{V}_{i}$ has a norm $|\cdot|_{i}$ and $\mathcal{W}_{i}$ has a norm $|||\cdot|||_{i}$. The linear operators, $A_{i}:\mathcal{V}_{i}\rightarrow\mathcal{W}_{i+1}$, are associated with some operator norm $\left|A_{i}\right|_{i\rightarrow i+1}\leq s_{i}$, i.e., $\left|A_{i}\right|_{i\rightarrow i+1}\coloneqq\|A_{i}\|_{\sigma}\leq\sup_{|Z|_{i}\leq 1}\left|||A_{i}Z||\right|_{i+1}=s_{i}$. Then, letting $\tau\coloneqq\sum_{j\leq L}\epsilon_{j}\varrho_{j}\prod_{l=j+1}^{L}\varrho_{l}s_{l}$, with given convering resolutions, $(\epsilon_{1},\ldots,\epsilon_{L})$, the neural net images, $\mathcal{H}_{X}\coloneqq\left\{F_{\theta}(X+\Delta)\right\}$, have the covering number bound (Bartlett et al., 2017):

Step (IV): Proof of Theorem 3. The key technique in the remainder of this proof is

1) to substitute covering number estimates from (42) and (43) into (44) but

2) centering the covers at 0 (meaning the cover at layer $i\in(2,L)$ satisfies $\left\|A_{i}\right\|_{2,1}\leq a_{i}$, $\|A_{1}\|_{2,1}\leq a_{0}$, and \|\hat{A_{1}}\|_{2,1}=\left\|\left[\begin{array}[]{c}A_{1}\\ \Delta A_{1}\end{array}\right]\right\|_{2,1}\leq a_{1}), and

To start, the covering number estimate of the whole network from (44) when combined with (42) and (43) (specifically with $p=2,s=1$, and $W=\max(d_{0},\ldots,d_{L})$) results in:

Combining (46) and (47), the cover is bounded by:

Using the above covering number bound (52) in the Dudley entropy integral (28) with $\alpha\coloneqq 1/\sqrt{n}$, we achieve the bound for the Rademacher complexity as follows:

We complete the proof of Theorem 6 by substituting (53) in (22).

A.2.3 Emperical validation of theorem 6

In this section, we empirically verify Theorem 6 regarding two variables: the neural network’s width, $W$, and the number of clean samples. The experiment is conducted with poisoned models trained over Trojan WM poisoned CIFAR-10 (poison rate: 20%, target label: 2).

Table 7 shows the empirical results of adopting different models with different widths. All the poisoned models are poisoned with Trojan WM attack using a poison rate of 20%. We sorted the models according to their maximum width ($W$) in Table 7. The Error Gap is obtained as the absolute value of the test error subtracted by the training error after conducting the defense. Based on the observation, the error gap is smaller as the model width grows, indicating better generalizability. Aligning with Theorem 6, the generalizability has a positive correlation with $W$.

Table 8 shows the empirical results of adopting different numbers of clean samples during the I-BAU. As indicated from the results, a larger number of clean samples would lead to a smaller value of the Error Gap, which indicates a better generalization of unlearning effect from training to unseen data. Such results aligned with Theorem 6.

A.3 Implementation Details and Complexity Analysis

I-BAU does not need to compute the second-order derivative directly. Instead, it is computed via implementing an approximation of the response Jacobian via an iterative solver (e.g., conjugated gradient algorithm (Rajeswaran et al., 2019) or fixed-point algorithm (Grazzi et al., 2020)) in limited rounds along with the reverse mode of automatic differentiation (Baur & Strassen, 1983; Griewank & Walther, 2008) by treating the problem as a linear system. Automatic differentiation in reverse mode is a widely used technique in modern deep learning packages such as Tensorflow and PyTorch (Baydin et al., 2018). This section gave the ablation study over the norm bound given in Algorithm 1 and the memory and time complexity analysis and comparisons.

This section studies the impact of the preset $l_{2}$ bound’s influence in the I-BAU unlearning scheme. We tested five different bounds to illustrate the effects, i.e., $0.5$, $5$, $10$, $20$, and Best Efforts, as shown in Figure 2. The settings of Best Efforts norm bound is that we do not include a norm constrained of the synthesized trigger as long as the trigger’s value is within the image value range (from 0 to 1 in our case with float type images).

The $l_{2}$ norm of launching the Trojan WM attack is 8.739 (measured by comparing with a zero matrix of the same size). As shown in Figure 2 a larger norm bound leads to a more robust and accurate synthesis of the potential trigger on the GTSRB. Especially the $l_{2}$ norm bounds that are greater than the attack trigger’s $l_{2}$ bound would lead to an effective defense in terms of low ASR and low impacts over the clean ACC. Based on Figure 2, we find that a large norm bound does not significantly impact over the clean ACC, namely the tread-off between the $l_{2}$ bound and the ACC drop is not substantial. In practice, when adopting I-BAU for backdoor defense, one is encouraged to adopt a large norm bound, thus encompassing more potential attacks.

A.3.2 Memory complexity analysis

Following Griewank (1993), we assume that the space complexity of computing $\nabla\delta(\theta)=-\left(\nabla_{1}^{2}H(\delta(\theta),\theta)\right)^{-1}\nabla_{1,2}^{2}H(\delta(\theta),\theta)$ via automatic differentiation is no more than twice the memory used when computing $\nabla H(\delta,\theta)$, which making our space complexity as $Mem(\nabla H(\delta,\theta))$. Recalling another popular class of methods to solve bilevel optimization—explicit gradient methods (Grazzi et al., 2020), whose memory complexity is $Mem(K\cdot T\cdot\nabla H(\delta,\theta))$ as they need to save the full computational graph during backpropagation, where $K$ is the number of rounds for adversarial unlearning, $T$ is the number of computations for the inner. In comparison, I-BAU is more memory efficient by adopting the implicit gradient via the iterative solver to approximate the computational graph without saving the whole graph.

A.3.3 Time complexity analysis

FP mitigates backdoor attacks via multi rounds ($K_{2}$ rounds) of pruning the network; in practice, FP requires more than 100 rounds of pruning (used half the number of samples for pruning, and the rest is for fine-tuning) to meet the stop requirements.

In conclusion, we find that theoretically, I-BAU is more efficient than other state-of-art defenses, and the theoretical results are aligned with the empirical observations over the average time taken effect over one-target attacks (see Table 6).

A.4 Experimental Detailed Settings

The details of the simplified VGG model adopted in our paper are explained in Table 9. For each convolutional layer, we used batch normalization, and ELU is adopted as the activation function for each. We use Adam with a learning rate of 0.05 as the optimizer for poisoned models. The models are trained with 50 epochs over each poisoned dataset to converge and attain the results shown in the main text. Our experiment adopted ten NVIDIA TITAN Xp GPUs as the computing units with four servers equipped with AMD Ryzen Threadripper 1920X 12-Core Processors. Interestingly, the same experiments showed slower convergence (it takes more rounds to mitigate the backdoors) using GTX TITAN X and GTX 2080 TI. To reproduce the exact experimental results, we suggest considering adopting NVIDIA TITAN Xp GPUs for the experiments. PyTorch (Paszke et al., 2019) is adopted as the deep learning framework for implementations. For the settings of implementing the I-BAU, the inner and outer is conducted with iterative optimizers (SGD or Adam) with a learning rate of 0.1.

A.4.2 Baseline defenses details

We compared I-BAU with six state-of-art backdoor unlearning defenses: Neural Cleanse (NC) (Wang et al., 2019), Deepinspect (DI) (Chen et al., 2019), TABOR (Guo et al., 2019), Fine-pruning (FP) (Liu et al., 2018a), Neural Attention Distillation (NAD) (Li et al., 2020b), and Differential Privacy training as a general robustness defense (DP) (Du et al., 2019). The detailed settings of comparison are provided as follows:

NC is conducted following the same settings as the original work but only use the same 5000 samples as ours; for the outlier detection, we marked and unlearned all the detected triggers (Median Absolute Deviation (MAD) based on the generated trigger’s norm, marked all the triggers whose mask MAD loss larger than 2 as detected).

DI adopted model inversion technique for agnostic to the clean samples, yet made the defense’s efficacy highly depend on the inversion technique. For a fair comparison, we feed the same 5000 samples, which are available to the other methods, to the GAN synthesizer in DI and obtains the final results; for the outlier detection, we marked and unlearned all the detected triggers (MAD based on the average loss for generating a trigger, marked all the triggers whose MAD loss larger than $2$ as detected).

TABOR’s settings follow the original work but with only 5000 clean samples being provided. (MAD based on the norm computation proposed in the original work to get rid of false alarms, marked all the triggers whose MAD loss larger than $2$ as detected.)

FP follows the suggestions of the original work, where we prune the network by supervising the ACC to drop to a certain percentage, i.e., 20%. This part’s ACC is done by using 1000 samples from the 5000, and the rest 4000 clean samples are used to fine-tune the model to recover the ACC.

NAD’s implementation follows the exact settings as the original work. The original work did not emphasize much over the preprocessing, and we used the same preprocessing following their open-sourced codes https://github.com/bboylyg/NAD.

DP follows the settings in the work that first mentioned use DP as a backdoor defense (Du et al., 2019), where we tuned the noise multiplier to attain universal effectiveness across all the considered attacks(50 for the CIFAR-10, 1.5 for the GTSRB).

A.5 Case Study on Non-additive Backdoor Attacks

As our fundamental formulation takes backdoor triggers as additive noise, in this specific section, we would like to evaluate the effectiveness of I-BAU towards non-additive backdoor attacks empirically. We selected four unique backdoor attacks/ settings to evaluate I-BAU towards non-additive attacks, which will be introduced as follows. 1) Semantical replacement (SR), which directly replaces the poison image with a piece of different semantical information. We designed this attack by directly changing all the poisoned images to an out-of-distributed ‘Hallo Kitty’ image with the poisoned label. SR should be considered as one of the worst-case attack scenario in practice, as its trigger is additional semantical information with a large norm bound; 2) WaNet (Nguyen & Tran, 2021) adopts a universal wrapping augmentation as the backdoor trigger. Under such a case, the backdoor trigger becomes a specific augmentation technique but not direct information insertion or addition. And WaNet has shown its ability to bypass some existing defense methods; 3) IAB attack (Nguyen & Tran, 2020) adopts autoencoder to learn and assign sample-specific noise to inputs to launch sample-specific backdoor attacks; 4) Hidden trigger (HT) attack (Saha et al., 2020) adopts a unique poisoning procedure using projected gradient descent to compute adversarial noise, which we consider as another example of a non-additive attack. We evaluate the effectiveness of I-BAU against the above four non-additive attacks on the CIFAR-10 dataset. We will illustrate their specific settings and results in the following parts of this section.

We first evaluate an extreme case where we replace the poisoned CIFAR-10 images with an out-of-domain ’Hallo Kitty’ image. Such a procedure directly changes the semantic information of the poisoned data. We set the target label as ’0’. Like the other evaluated attack, we replaced 20% of the non-target-class samples with the trigger kitty and set the label as ’0’. As for launching the attack during test time, we evaluate the same ’Hallo Kitty’ image exposed to the poisoned model and measure the attack success rate (in this case it becomes either 100% or 0%). The target model here adopted the small VGG16 introduced in our experiment. As for I-BAU, we adopted Adam optimizer and a learning rate of 0.1 and an unlimited $l2$ norm bound (instead, we crop the perturbation’s value and restricted it to 0-1 as discussed in Appendix A.3.1). The results before and after are listed below in Table 10.

As demonstrated in Table 10, within three rounds of I-BAU, we obtained a clean model with an acceptable ACC drop compared to the baseline. Interestingly, the extreme case directly inserts an additional semantical link between the poison kitty and the class ’0’, which can be interpreted as direct exposure of a specific training sample to the test set and interfere with the model generalizability (aka, overfit to a rare feature). Surprisingly, I-BAU can effectively mitigate such attack patterns. To our best knowledge, the above attack setting is never considered before. I-BAU also shows a potential path towards resolving model overfitting issues. We will leave such discussion to future work.

A.5.2 Towards mitigating WaNet

WaNet is one of the famous invisible attack, instead of adopting an additive trigger, it adopts the same elastic transformation as the trigger of the attack. We directly downloaded the pre-trained poisoned PreActResNet18 on the CIFAR-10 from their work as the poison model to be adversarially unlearnt https://github.com/VinAIResearch/Warping-based_Backdoor_Attack-release. As for I-BAU, we adopted Adam optimizer and a learning rate of 0.0001 and an unlimited $l2$ norm bound. The results before and after are listed in Table 11, which indicates an effective defense with acceptable influence in the ACC.

A.5.3 Towards mitigating the IAB attack

An emerging line of attack focuses on sample-specific attacks; here, we evaluate against IAB attack, which utilizes an autoencoder to learn and insert sample-specific triggers. We followed the same implementation as provided in the original work https://github.com/VinAIResearch/input-aware-backdoor-attack-release, with the following specific settings: dataset: CIFAR-10; target label:0; $\rho_{b}=\rho_{c}=0.1$; model: PreActResNet18. One difference is that we loaded the CIFAR-10 dataset in a customized dataset format instead of the default (i.e., we used “torch.Tensor” loaded from “NumPy.array” with range $$, instead of “torch.Tensor” loaded from “PILimages” with range$[-1.99,2.13]$). We did this to facilitate the implementation of I-BAU (which targeting at noises ranging from$$ for the current implementation). The results prior to and during the intervention are summarized in Table 12, indicating an effective defense with a low influence in the ACC.

A.5.4 Towards mitigating HT

Finally, we evaluated the effectiveness of Hidden trigger (HT) backdoors (non-additive during poisoning), whose trigger inserting process is by directly resolving adversarial noise generated via projected gradient descent. We evaluated I-BAU with the CIFAR-10 random pairs attack settings from the original work (trigger_10, target: 8, source: 5, number of samples to generate PGD noise: 1500, number of poison in target class: 800, $\epsilon=16$, optimization for generating poison: 0.01 with a decay rate of 0.95 every 2000 iterations). However, we found the original settings suffer from limitations in targeted ASR in our experiment, which is only “18.30%” (i.e., only drops the ACC after patching the trigger but have a relatively low chance leading to the target label). To enforce a successful targeted attack, we enlarged $\epsilon=50$. During the fine-tuning process of , we only fine-tuned the clean model (ACC:“84.60”) over the poison data, which resulted in a poisoned model with an ACC/ASR of “73.41/89.00”. After adopting I-BAU for 20 rounds, the poisoned model’s performance becomes “84.58/11.10”, and with larger rounds (90 rounds), the performance can further be improved to “84.06/0.23”, which indicates a robust and effective defense and an extra effect on recovering ACC.

A.5.5 Highlights on the case studies towards non-additive attacks

The above results from the case study on using I-BAU to mitigate non-additive attacks highlight that although our formulation targets a universal pattern that most misled misclassifications in an additive way, I-BAU is empirically effective towards mitigating non-additive attacks. These emperical results have a great chance to lead to some exciting future works on theoretical analysis of the effectiveness of our proposed minimax formulation. We will open-source all incorporated attacks (at the moment, eleven attacks are incorporated, seven in the main text, and four non-additive case studies in the Appendix) and the pre-trained poisoned models. We will constantly check out the emerging attacks and look forward to seeing the first attack can evade our defense!

A.6 TSNE Analysis on Unlearning Effects

The TSNE analysis of the feature extracted by the poisoned model and the unlearned model is shown in Figure 4. The model considered here is a BadNets poisoned model on the CIFAR-10 dataset (target label is 8), and the results listed in Figure 4 are before and after one round of I-BAU. Before the I-BAU, the poison model’s extracted features for samples with/without triggers are disparate, even for samples originating from the same class. After the I-BAU, we can see that the unlearned model will map the samples patched with triggers back to their original classes (same color). Such results demonstrate the effectiveness of the backdoor unlearning from another perspective.

A.7 Iterative Illustration on Multi-target Cases

We show the iterative records of I-BAU mitigating more complicated attack cases, i.e., the all-to-all attacks and 7-trigger-7-target cases on the two evaluated datasets. We listed them here as they take more rounds than one-trigger-one-target cases, which can usually be mitigated in a one-shot-kill manner.

Figure 5 shows the results on countering the BadNets all-to-all attacks, where (a) is the results on the CIAFR-10 dataset, and (b) is the results on the GTSRB dataset. As shown in Figure 5 (a), although it takes more rounds than one-trigger-one-target cases to mitigate the attack, thanks to the accurate computing of the hyper gradient, the I-BAU did not impact much over the ACC. When the ASR drops below 10%, the unlearned model can still maintain an ACC above 80% (original ACC: 86.38). Meanwhile, in Figure 5 (b), we see that we can unlearn the BadNets trigger under all-to-all cases with even fewer rounds of I-BAU, and the unlearned model can maintain an ACC of around 99% during the entire unlearning procedure.

Figure 6 demonstrates the mitigation records of each iteration of I-BAU over the 7-trigger-7-target cases over the two evaluated datasets. Figure 6 (a) draws the details on the CIFAR-10 dataset, which took more than 200 rounds of I-BAU to mitigate all seven attacks. On the GTSRB, the mitigation of all seven triggers takes less time. And the model can maintain an ACC close to 99% during the entire unlearning procedure.

Upon observation, there are triggers easier to be found by the I-BAU, e.g., Trojan WM and Trojan SQ, as they are optimized triggers, and thus easier to be bound by the I-BAU. Such interesting observation might lead to new logic to consider while designing backdoor triggers (more optimized triggers might be easier to remove, as demonstrated).