Adversarial Unlearning of Backdoors via Implicit Hypergradient
Authors: Yi Zeng
Si Chen
Won Park
Zhuoqing Mao
Ming Jin
Ruoxi Jia
Venue: ICLR 2022 Poster (2022)
Keywords: backdoor defense
backdoor removal
backdoor
minimax
implicit hypergradient

Abstract: We propose a minimax formulation for removing backdoors from a given poisoned model based on a small set of clean data. This formulation encompasses much of prior work on backdoor removal. We propose the Implicit Backdoor Adversarial Unlearning (I-BAU) algorithm to solve the minimax. Unlike previous work, which breaks down the minimax into separate inner and outer problems, our algorithm utilizes the implicit hypergradient to account for the interdependence between inner and outer optimization. We theoretically analyze its convergence and the generalizability of the robustness gained by solving minimax on clean data to unseen test data. In our evaluation, we compare I-BAU with six state-of-art backdoor defenses on eleven backdoor attacks over two datasets and various attack settings, including the common setting where the attacker targets one class as well as important but underexplored settings 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 $13\times$ faster than the most efficient baseline in the single-target attack setting. Furthermore, it can 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.

Published as a conference paper at ICLR 2022
ADVERSARIAL UNLEARNING OF BACKDOORS VIA IM- PLICIT HYPERGRADIENT
Yi Zeng +1 Si Chen', Won Park?, Z. Morley Mao², Ming Jin' and Ruoxi Jia!
Virginia Tech, Blacksburg, VA 24061, USA University of Michigan, Ann Arbor, MI 48109, USA
ABSTRACT
We propose a minimax formulation for removing backdoors from given poi- soned model based on a small set of clean data. This formulation encompasses much of prior work on backdoor removal. We propose the Implicit Backdoor Adversarial Unlearning (I-BAU) algorithm to solve the minimax. Unlike previous work, which breaks down the minimax into separate inner and outer problems, our algorithm utilizes the implicit hypergradient account for the interdependence between inner and outer optimization. We theoretically analyze its convergence and the generalizability of the robustness gained by solving minimax on clean data to unseen test data. In our evaluation, we compare I-BAU with six state-of- art backdoor defenses on eleven backdoor attacks over two datasets and various attack settings, including the common setting where the attacker targets one class as well as important but underexplored settings where multiple classes are tar- geted. I-BAU's performance is comparable to and most often significantly better than the best baseline. Particularly, its performance more robust to the variation triggers, attack settings, poison ratio, and clean data size. Moreover, I-BAU requires less computation to take effect; particularly, than the most efficient baseline in the dingle-target attack setting. Furthermore, it can remain effective in the extreme case where the defender can only access 100 clean samples setting where all the baselines fail produce acceptable results.
more than 13x faster
INTRODUCTION
In backdoor attacks, adversaries aim to embed predefined triggers into model during training time such that test example, when patched with the trigger, is misclassified into target class. For instance, has been shown that one could use 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 iussion-critican applications (Li et al., 2020c; 2021a).
Various approaches have been proposed to remove the effect of backdoor attacks from poisoned model. One popular class of approaches (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019) 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 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 al., 2018a) and preprocessing the model input (Qiu et al., 2021). While these approaches are more efficient than the trigger-sythhesis- they cannot maintain 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 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.
approaches,
To address the challenge, we propose a minimax formulation to remove backdoor triggers from poisoned model. The formulation encompasses prior works trigger synthesis-based defense, which solves the inner and outer problems independently. Moreover, the formulation does not make
Cooresponnennce yizeng yizeng@vt.edu. vt.edu. Codes of implementations opensourced on Github: I-BAU

---

Published as a conference paper at ICLR 2022
any assumption about the backdoor trigger beyond bounded norm constraint, thus remaining ef- fective across various attack settings. To solve the minimax, we propose an Implicit Bacdoor Ad- versarial 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 account for the interdependence between inner and outer op-
derives the implicit hypergradient timization 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 formula- tion, 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 com- mon 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 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 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.
2 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 ct al., 2020) for higher attack efficacy. While this line's 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 Ip norm (Li et al., 2020a), or adopting nature optical effects (Liu et al., 2020; Nguyen & Tran, 2021), 1), and Clean label atlucks 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 detec- tion from manual efforts. 3) Invisible triggers considering other latent spaces, c.g., the frequency domian (Zeng et al., 2021; Hammoud & Ghanem, 2021) or auto-encoder feature embedding (Li al., 2021b), which improved the stealthiness by breaking the fundamental assumptions of 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 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//eccoupeed 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), preprocessing & finetuning (Li et al., 2020b; Borgnia et al., 2020; Qiu et al., 2021). This line of work serves as the fundamental solution given poisoned model, but there is still 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 include all cutting-edge methods under this category for comparison.
3 PROBLEM FORMULATION
Attack model. We assume that an adversary carries out a backdoor attack against a clean training set generated from the distribution D. The adversary has pre-determined triggers and target classes. The adversarial goal is to poison the training dataset such that, given a clean test sample xr, adding a backdoor pattern 5 to x (i.e., x + 5) will alter the trained classifier output to be a target class ÿ. The norm of 5 represents the adversary's manipulative power. We assume that ||ō|| < C.. In general, the attack can add r backdoored examples into the training set to induce the association between the trigger ó and the target class ÿ. The ratio of the total backdoored examples over the size of the training set is defined as the poison ratio. For better stealthiness, attacks often aim not to affect the prediction of test example when the trigger is absent. Note that in attack model, explicitly acknowledge the possibility that multiple trigger patterns and multiple target classes are present. We will refer to the model trained the poisoned training set poisoned model.
2

---

Published as a conference paper at ICLR 2022
Defense goal. We consdier that the defender is given poisoned classifier feg. and an extra set of clean data D = { Mi )==1 from D. With fo and D, the defender aims to build model so- immunne to backdoors, i.e., fo. (x + 8) = fo (r). 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.
Minimax formulation for defense. To achieve the defense goal, we want the resulting classifier to maintain the correct label even if the attacker patches the backdoor trigger to given input. This intuition naturally leads to the following minimax optimization formulation of backdoor removal:
H(6,0) = 1 Σ L(Sa(z; 0),
0 = arg min max MMlSC
(I)
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 misclassification for any examples upon being patched. Hence, in the formulation for backdoor attacks, the same trigger, 6, is applied to every clean sample 2;, 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 perspective that encompasses much prior work on backdoor removal. The formulation comprises an inner maximization problem and 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 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 backdoor robustness. In particular, when the parameters @ 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 D.
unifying
ALGORITHM
natural (but problematic) algorithm design. Given the empirical success of adversarial train- ing for defending against evasion attacks (Li et al., 2022), one may wonder whether 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 fixed outer mini- mization 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 at- tacks, 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-Dezfoolli et al., 2017). However, we found that this simple algorithm is highly unstable. Figure/ illustrates the change of the model ac- curacy and robustness (measured in terms of the attack success rate (ASR)) for 20 runs adversarial training proceeds. It can be seen that the ASR varies significantly across different runs. Within a single run, while the ASR decays whole, the decrement is mostly erratic and slow.
solve
3

---

Published as a conference paper at ICLR 2022
There are two issues with naive adversarial training with universal perturbations. First, the perfor- mance of the existing universal perturbation algorithm is unstable. At its core, it generates adver- sarial perturbations for each example and adds the perturbations together. The addition may not always lead to 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 's Theo- rem (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, H8. 8) VoH .0). However,
letting 8* arg |8 <C2 (6, 8), we have Ve max in practice, due to stochastic gradient descent, it is impossible to solve the inner maximization op- timally. 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.
Algorithm 1: Implicit Backdoor Adversarial Unlearning (I-BAU)
Input: 0₁ (poisoned model);
D (clean set accessible for backdoor unlearning);
Output: 0g (sanitized model)
Parameters: Cs (f2 norm bound);
K, T (outer and inner iteration numbers); a, 9 >>> 0 (step sizes)
for each iteration í E (1, K - 11 do do
8 1-+00 0lxd. for () do
Update 8. = 8 + V V (T L, |
& x min
Compute V (Hessian products) via iterative solver with reverse mode differentiation; Vi((O.) (,, Vo. V (6,,
Update 0,+1 = 0.- (O:)
return 0K
Proposed algorithm. 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 5(0) be an arbitrary suboptimal solution to max 18 Isc, H (ö, 8). Let (0) = H(0(),, 9) be the objective function evaluated at the suboptimal point; if 8(0) a stationary point, we make an dis- tinction by defining the corresponding function v (0). Denote 1, 0) and 22 0) as the partial derivatives with respect to the first and second variable, respectively, and H6, 0) and (6, f) as the second-order derivatives of H with respect to the first variable and the mixed variables, respectively. The gradient of & with respect to / is given by
response Jacobian direct grad. of 5
(#) (2H()(0))0)
(V8(0)) (5H(5(0),0))
(2)
hypergrad. of direct grad. of The direct gradients are easy to compute. For instance, suppose H is the loss of neural network, then V, (8(0), 0) and (8(0), 0) are the gradients with respect to the network input and the model parameters, respectively. However, the response Jacobian is intractable to obtain because must compute the change rate of the suboptimal solution to the inner maximization problem with respect to 0. When 5(0) satsifies the first-order stationarity condition, i.e., H, = 0, and assuming that (B((0, 8) is invertible, the response Jacobian is given by
indirect grad.
V8(0) = (V) 0)) Vi (((0),)
(3)
which follows from the implicit function theorem. Note that V8(0) plays role in the Hessian in (2), in the sense that adjusts each dimension of the gradient H (8(0), 0) to the importance of that di- mension. Hessian expresses the importance via curvature, whereas V8(0) measures the importance based on the sensitivity to the change of 0. 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 V8(0) with a suboptimal solution by (3). In practice, the approximation is addressed with an iterative solver of limited rounds (e.g., con- jugated 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).
4

---

Published as a conference paper at ICLR 2022
Finally, to solve (1), plug in the approximate response Jacobian into (2). Then, use V (i) (re- ferred to as implicit hypergradient hereinafter) to perform gradient descent and update the poisoned model. Note that the implicit hypergradient only depends on the value of ö(0) instead of its opti- mization path; hence, it can be implemented in a memory-eficiiet manner compared to the explicit way of solving bi-level optimizations (Grazzi al., 2020). The overall algorithm, dubbed Implicit Backdoor Adversarial Unlearning, for ég- ég-norm bounded attacks is presented in Algorithm 1. Gener- alizing the algorithm to other norms straightforward. We found that imposing a large norm bound in I-BAU has no discernible effect on clean accuracy (Appendix A.3.1). This empirical observation enables the proposed I-BAU to be flexible enough to deal with different scales of backdoor triggers in practice. Further details on the the iterative solver with the suboptinum solution and memory complexity analysis are provided in Appendix A.3.
5 THEORETICAL ANALYSIS
In this section, 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 specific norm, we would like to reason about to what extent an unseen point from the underlying data distribution D is trigger-robust.
Convergence Bound: Suppose that H)) is pur(Q)-tronglyy convex and Lu Lnr(0)-Lipschin smooth, where (-) and (=(-) are continuously differentiable. Define a()) = [x(0)-pm(()> and let 5()) be the unique fixed point of 8 + a(0) H5, (). Then, there exists LH s.t. ii s IV (5, O)l S LH,0 (Grazzi et al., 2020). We make the following assumptions:
Lipschitz continuity of direct gradients: V V1 f) and V Vy 0) are Lipschitz continuous func- tions of 9 (with Lipschitz constants Th. and 12200 repectively).
Lipschitz continuity and norm boundedness of second-order terms: (i 0) is P1.0- Lipschitz continuous, and V2, H(,
0) is Lipsshiis continuous. Also, the cross derivative term is norm
bounded by Ln.9 2 V22 H (8(0), 0)|
Asymptotic convergence of 8' (0) to 8()): (1) - 8(0))l S pb(() [1(()].. where pa(1) is such that (t S 1. and pa
0 as too.
Theorem Consider the approximate hypergradient v ((,)) computed by Algorithm (line 7). For every inner and outer iterate I, E N, we have:
- ve( where Q9. == max (1 (1- (0) - 11, (0,) = 12,0, + n.u Ln, n. ((.))
- -
+ +2))) 1 - ge.
pa, (t) cg((0))
(4)
1 qu,
Co.
1 -4
+ 22. (0.)) Pio L. 0, Cra(0:)
c2((.) = LH Cs
and finally ca c²( ==
1 20
Lu.o, ((0,)
1-90;
As the inner epoch number increases, the estimated gradient becomes more accurate. Under the assumption that (.,0) 0) is convex, the solution converges. We show the full proof in Appendix A. Generalization Bound for Linear Models: Consider a class of linear classifiers
E e nornebounded by Co. Define X to be the upper bound of any in-
where the weights put sample E D, i.e., ||0||| X. Let the empirical risk defined as R,) S
n-1 E, 1 0 (xz + +5),, Sy+ maxizv; 0 (Iz + 6)]] with margin y 0.
Theorem 2 For any linear model and & E (0, 1). the following holds with probability of at least 1 - over ((*4, W:))
(x+ Cs) + 3/
In(1/E)
Pr arg max 00x + 0),] + < (R) 2C,
(5)
Vn
2n
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 al., 2019), which has an additional vd factor in the second term of the bound. Henee, 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.
5

---

Published as a conference paper at ICLR 2022
Generalization Bound for Neural Networks: Consider neural network with L fixed nonlineari- ties (dI...., OL), where oj is o; oi-Lipschitz (e.g., coordinate wise ReLU, max max-pooling as discussed in (Bartlett et al., 2017)) and (0) = 0. Let L weight matrices be denoted by (AI...., Ar,) with dimensions (da...., ,d.),, respectively, where dg = d is the number of input dimensions, d1 = C is the number of classes, and W = max(do,.... dr) is the highest dimension layer. Assume that the weight matrices satisfy ||Aill,,1 S as, ||Aill2.1 I ao and A; E igd:xm. Let a1 = do (1+ C/)) The whole network's 's output regarding a backdoored sample is denoted as: dr (- (AL-1--- 01 01 (A1(x + .)). Let ||A be bounded by the spectral norms 8,-
Theorem For any neural network model A and & E (0, 1), the following holds with a probability of at least 1 & over ((z1,)()) )=))
Pr arg max [0(x= + 8)z] + / S
(6)
3/2
(0) + 8 481(() VR (W)2
(II sces) (I
2/3
+3V
In(L/E)
2n
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 al., 2017), our bound has an additional n term in vIn(2W(W + n)) and (II + vn), 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, ó, 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 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 10 as the norm constraint for implementing I-BAU. The details of experimental settings and model architecture can be found in Appendix A.4.
6.1 EFFICACY
We evaluate I-BAU's e-ficay against three attack settings: 1) One- cee-trrgger-one-tareeee 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--lll-t- 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 tettiitriggrr-uuliee maae--mulltttttteeeee 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), to norm constraint invisible trigger (lo inv) (Li et al., 2020a), l2 norm constraint invisible trigger (l2 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 aon-additive backdoor attacks. We have included case studics using I-BAU mitigating four 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, train the poisoned dataset for 50 epochs.
attack, in which the attacker uses
We compare I-BAU with six state-of-ard defenses: Neural Cleanse (NC) (Wang et al., 2019). Deepin- spect (DI) (Chen et al., 2019), TABOR (Guo et al., 2019), Fine-pruning (FP) (Liu et al., 201 80)8a),

---

Published as a conference paper at ICLR 2022
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] J to mark the results where the accuracy (ACC) on clean data drops by more than 10%; we use I ACC ASR I to mark the best result among the six baselines; finally, we use ACCC or ASR to mark the results from I-BAU that comparable to or significantly better than the best result among the baselines. We con- sider I-BAU's 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 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 presents the defense results on the CIFAR-IO 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 lahel. The all-to-all case represents the case in which use the BadNets trigger to earry out the one-trigger-all-to-- attack. As shown in the table, all single- target attacks are capable of achieving an ASR close to 100% with no defenses. It 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.
No Dafense
NE
DJ
TAROR
FP
NAD
DP
(-BSU(OOr))
Attack
ACC
ASR
ACC
ASR
ACC
ASR
ACC
ASR
ACC
ASR
ACC
ASR
ACC
ACC
ASR
BadNees
84.94
98.28
83.42
8.76
82.12
43.50
83.78
8.12
82:22
96.06
78.72
11.56
11.08
21.77
83.35
12.30
Blend
84.82
99.78
83.08
13:96
$1.84
52.62
83.42
21.26
81.24
89.78
77.48
13.02
11.68
13.72
82.30
12.96
85.36
100
83.02
8.78
83,40
29.1
82.27
8.16
82.18
100
65.08
7.22
12.48
25.22
81.08
9.51
la
85.26
80.68
8.08
82.46
7.82
80.30
11.64
81.50
43.18
11.58
20.57
83.48
7.48
Smooth
85.34
99.21
83.72
46.88
83.32
61.82
84.14
45.94
82.66
9.44
77.22
51.38
10.70
28.14
83.16
18.30
Trojnn SQ
81.76
99.66
81.30
8.02
83.14
6.94
81.38
7.06
82.31
99.50
51.86
7.34
10.70
18.26
83.18
9.82
Tresin WM
8492
99.96
86
600
82.88
7.24
82,60
49.26
81
99
56.84
0.82
15.21
32.89
83. 58
3.42
56.38
84.45
66.46
34
10. 46.4
Table I: Results on CIFAR-10 10. one-trigger cases. CIFAR- 10's ACC sensitive to fine-tuning and 1-BAU; we compare I-BAU when drops similar ACCs amount to the most effective method. x - no detected trigger.
Model performance on CIFAR-10 is particularly sensitive to finetuning and unlearning, which will result in decrease in the ACC in general. Thus, for a fair comparison, 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.
No Deleme
TABOR
FP
NAD
DP
I-BAU/Ourr) ACC
Attack
ANR
ACC
ASR
ACC
ACC
ASR
ACC
ASR
BadNets
97.89
99.18
98.59
4.36
59:34
60.19
15.19
9.08
0.46
100
59.338
3.32
Hlend
V7.4
1991
19.19
33.32
19.32
69.66
47.71
18.48
5.70
190
98.89
5.01
98
0.47
99.41
74.86
17.41
1,20
7.40
88.23
0.42
I inv
97.77
9991
98.51
0.41
19.55
40.46
15.50
1.16
5.46
100
97.75
0.45
Smonth
9787
00.00
9W.62
0.47
15.35
47.75
10.06
0.70
5.94
95.58
9%.96
0.22
Trojon 50
98.12
99.998
99.06
5.70
99:15
75.96
23.31
11.68
5.51
100
99.01
5.11
Trojan WM
97.84
98
11.16
13.52
5.70
100
All to all
97.10
95.42
98.63
47.07
99.45
67.34
25.53
0.42
5.87
5.70
99.13
0.04
Table 2: Results on GTSRB, one-trigger cases. I-BAU's results shown here were obtained after 100 rounds of I-BAU, For that, Neural Cleanse, Deppinspect, and TABOR are from the same line of work, so we here only compare the result with the most stale-of-art method in this category, TABOR.
As shown in Table 1, the performance of the baselines exhibits large variance across different trig- gers. Specifically, each baseline underperforms in at least three attack cases (marked by (I | or I (ACC The defenses based on trigger synthesis (including NC, DI, and TABOR) failed 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. Partieularly, TABOR fails to detect any backdoor triggers in this case). For DP, we fine-tune 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 sfate-of-art baselines ACC or ASR 1), I-BAU's 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.
7

---

Published as a conference paper at ICLR 2022
No Def.
NC
DI
LABOR
PP
NAD
DF
Ows'
85.96
77.38
11.18
avg. ASR
98.37
30.37
40.68
73:18
10.93
12.83
12.96
CIFAR-11 10
Trojonn WM:
99.92
9.68
28.02
99.7
18.38
13.40
11.48
SQF
99.42
13.74
99.36
11.94
2.58
10.80
BacNets:
94.5
9.16
9.56
6.94
Smooch: -5
97.08
50.58
89:
9.32
8.38
6.28
15. 22.22
Blend: -9.3
98.12
48.84
50.84
96.14
8.46
27.98
18.
IIN:
100
80
1. InN:
99.54
13.34
6.52
98.32
6.16
14.62
6.92
10:33
avg. ASR
99.37
10.87
7.21
11.39
9.38
11.39
42.86
1.18
Trojan WME
99.49
4,00
3:60
3.86
1:56
6.61
100
1.78
GTSRB
Trojan SQ:
99.59
2.79
6.26
2.33
0.12
4.14
5.68
AS1Ks
BacNets:
98.19
4.79
Smooth:
99.89
8.56
6.92
15.28
10.05
2.83
100
5.65
Blent 1
99.15
46.89
22,66
45.91
29.69
41.50 54
100
3.76
100
1.06
0.59
17.70
5.25
IIN)
99.33
5.94
5443
4.52
9.60
3.52
0
6.46
Table 3: Results for 7-trigger---targel cases. x marks no trigger was detected. *Here, ASR results on CIFAR-
10 are provided when the model attained an ACC similar to that of NAD (the only effective one on CIFAR-10).
Table 2 shows the evaluation 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 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 shows the results on CIFAR and GTSRB in a 7-trigger-7--ae 7-trgttt 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, 10, and 274,463 for the GTSRB). We show the average ASR and the specific ASR.
On 10, since the target classes are no longer the minor- ity (i.c., 7/10 labels are targeted), the baselines based trig- ger synthesis, which make the minority assumption, are ineffec- tive. Particularly, NC fails to detect any triggers in this setting. NAD is the only baseline able to evaluate well on CIFAR-10, and methods achieve comparable performance. However, sim- ilar 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; c.g., the random flipping-a beneficial preprocessing step for CIFAR- complecyyyy alters the semantics of images in GTSRB. On the other hand, I-BAU effectively reduces ASR while main- taining the ACC for both datasets with no changes needed. More- over, 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.
Naive ACC
HAU ACC
Nclve ASR
SAU ASR
100
80
Percentage 1%
50
Figure 1: Comparison of Naive and I-BAU. I-BAU's perfor- mance more stable.
6.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 heuristie. Notably, I-BAU attains slightly higher ACC than the naive heuristic.
8

---

Published as a conference paper at ICLR 2022
6.3 SENSITIVITY
We evaluate the sensitivity of each defense to the poison ratio and the size of clean samples. The ex- periments 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 ef- fective 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 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 the poison ratio, maintaining good ACC and ASR across different ratios.
posson
No
NC
TADOR
5.0%
ACC
ASR
$6.58
99.88
83.14
5.58
10:40
78.63
99.72
83.16
79.74
6.34
96.84
36.30
$1.76
9.78
ACC
39.92
0.5%
ASR
98.58
12.9
20.22
93.78
28.6
61.27
13.08
Table 4: Results on CIFAR-10 10 (Trojan WM) with different poison ratios. x marks no trigger was detected.
Table shows sensitivity to available clean data's size. As DP is independent from the clean set (which trains 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.
# Clean Data
Resulis
Nof.
NC
DI
TABOR
FF
XAD
Ours
2,500
ACC
$0.63
81.36
82:21
ASR
99.96
6.53
10.07
33.40
99.58
7.12
6.96
500
ACC
$4.92
78.24
80.17
77.03
78.1
38.5
80007
ASR
1.14
ACC
87.92
84.101
69.31
83.193
73.00
36
76.9
100
ASR
99.96
99.92
1.12
99.687
97.80
5.76
4.00
Table 5: Results with different # of clean data CIFAR-10 (Trojan WM).
6.4 EFFICIENCY
Finally, we compare the efficiency of defenses. We use the one- Tigger-one-targee attack setting to exemplify the result. Table 6 shows the average runtime for each defense to take effect (i.e., mitigating the ASR 20%). As I-BAU can mitigate the attacks in one iteration, it only takes 6.82 s on average on CIFAR-I0 10 and 7.84 on GTSRB. Note that NC and TABOR need to go through each label independently for trigger synthesis; thus, the total run- takes
CIFAR-I0
GTSRB (8)
NC
384.92
1864.96
DI
394.38
472.21
TABOR
1123,31
NAD
79.90
79.14
Ours
6,82
7.84
Table 6: Average time for de-
time is proportional much more time for the two to take effect on GTSRB than CIFAR-10. difficult attack cases, such as all-to-all attacks and 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 per- formance 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.
the number of labels. Especially,
fenses to effective on one-
rigger-one-targee cases. cases.
mulli-trigger-multitarre
7 CONCLUSION
In this work, we proposed a minimax formulation of the backdoor removal problem. This formula- tion 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 off-thh-ar art tech- niques. Meanwhile, I-BAU is less sensitive 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-tare cireunstances, I-BAU can achieve an effective defense in average of 7.35

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work was supported by the Commonwealth Cyber Initiative, an investment in the advancement of cyber R&D, innovation, and workforce development. For more information about CCI, visit www.cyberiniiaaiie.org
REFERENCES
Eugene Bagdasaryan and Vitaly Shmatikov. Blind backdoors in deep learning models, 2021.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. nooomail margin bounds for neural networks. Advances in Neural Information Processing Systems, 30:6240-6249, 2017.
Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical computer science, 22 1983.
Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: a survey. Journal of machine learning research, 18, 2018.
Eitan Borgnia, Valeriia Cherepanova, Liam Fowl, Amin Ghiasi, Jonas Geiping, Micah Goldblum, Tom Goldstein, and Arjun Gupta. Strong data augmentation sanitizes poisoning and backdoor attacks without accuracy tradeoff, 2020.
Richard H Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic hessian information in optimization methods for machine learning. SIAM Journal Optimization, 21 (3):977-995, 2011.
Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by activation clustering. arXiv preprint arXiv:1811.03728 2018.
Huili Chen, Cheng Fu, Jishen Zhao, and Farinaz Koushanfar. Deepinspect: black-box trojan detection and mitigation framework for deep neural networks. In IJCAI, pp. 4658-4664, 2019.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks deep learning systems using data poisoning. 2017.
Edward Chou, Florian Tramèr, and Giancarlo Pellegrino. Sentinet: Detecting localized universal attacks against deep learning systems. In Deep Learning and Security Workshop, 2020. URL
https: //rpxiv///vvvv..//// hwtgg//as/// /alos////11.0 00292.....
John M Danskin. The theory of max-min and its application weapons allocation problems, vol- ume 5. Springer Science & Business Media, 2012.
Min Du, Ruoxi Jia, and Dawn Song. Robust anomaly detection and backdoor attack detection via differential privacy. arXiv preprint arXiv:1911.0711 2019.
Yansong Gao, Change Xu, Derui Wang, Shiping Chen, Damith C. Ranasinghe, and Surya Nepal. Strip: A defence against trojan attacks on deep neural networks. Proceedings of 35th Anmual Computer Security Applications Conference, ACSAC '19, pp. 113-125, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 450376280. doi: 10.1145/3359789. 3359790. URL httph::t///o http:/ooo..oorr http//....115/3331 1111/133591999 3359790.
Siddhant Garg, Adarsh Kumar, Vibhor Goel, and Yingyu Liang. Can adversarial weight pertur- bations inject neural backdoors. Proceedings of the 29th ACM International Conference on Information & Knowledge Management, Oct 2020. doi: 10.145/3340531.34111300 URL 3412130.
http:/ / doi. org/100000 wtt.//1.111000
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp- PMLRR, 2020.
10

---

Published as a conference paper at ICLR 2022
Andreas Griewank. Some bounds the complexity of gradients, jacobians, and hessians. In Complexity in numerical optimization, pp. 128-162. World Scientific, 1993.
Andreas Griewank and Andrea Walther. Evaluating derivatives: principles and techniques of algo-
rithmic differentiation. SIAM, 2008.
Tianyu Gu, Brendan Dolan DolantGavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprini arXiv: 2017.
Wenbo Guo, Lun Wang, Xinyu Xing, Min Du, and Dawn Song. Tabor: A highly accurate approach to inspecting and restoring trojan backdoors in ai systems. arXiv preprint arXiv:1908.00 763, 2019.
Hasan Abed Al Kader Hammoud and Bernard Ghanem. Check your other door! establishing back- door attacks in the frequency domain. arXiv preprint wrXiv:2109005507, 2021.
Kunzhe Huang, Yiming Li, Baoyuan Wu, Zhan Qin, and Kui Ren. Backdoor defense via decoupling the training process. In ICLR, 2022.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks, 2020.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning attacks, 2021.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning. volume 70 of Proceedings of Machine Learning Research, pp. 1885-1894, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR. URL http:// proceedings mlr. press v70 koh17a 7 html.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks, 2020.
Shaofeng Li, Minhui Xue, Benjamin Zhao, Haojin Zhu, and Xinpeng Zhang. Invisible backdoor attacks deep neural networks via steganography and regularization. IEEE Transactions Dependable and Secure Computing, 2020a.
Yige Li, Xixiang Lyu, Nodens Koren, Lingjuan Lyu, Bo Li, and Xingjun Ma. Neural attention distillation: Erasing backdoor triggers from deep neural networks. In International Conference on Learning Representations, 2020b.
Yiming Li, Baoyuan Wu, Yong Jiang, Zhifeng Li, and Shu-Tao Xia. Backdoor learning: A survey. arXiv preprint arXiv:2007.08747 2020c.
Yiming Li, Tongqing Zhai, Yong Jiang. Zhifeng Li, and Shu-Tao Xia. Backdoor attack in the physical world. In ICLR Workshop, 2021a.
Yiming Li, Baoyuan Wu, Yan Feng, Yanbo Fan, Yong Jiang, Zhifeng Li, and Shu-Tao Xia. Semi- supervised robust training with generalized perturbed neighborhood. Puttern Recognition, 124: 108472, 2022.
Yuezun Li, Yiming Li, Baoyuan Wu, Longkang Li, Ran He, and Siwei Lyu. Invisible backdoor attack with sample-specific triggers. In ICCV, 2021b.
Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Fine-pruning: Defending against back- dooring attacks deep neural networks. In International Symposium on Research in Attacks, Intrusions, and Defenses, pp. 273-294 Springer, 2018a.
Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. In 25nd Annual Network and Distributed System Security Symposium, NDSS. The Internet Society, 2018b.

---

Published as a conference paper at ICLR 2022
Yunfei Liu, Xingjun Ma, James Bailey, and Feng Lu. Reflection backdoor: A natural backdoor attack on deep neural networks. In European Conference on Computer Vision, pp. 182-199. Springer, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 1eeei17060000000 2017.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Universal adversarial perturbations. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1765-1773, 2017.
Anh Nguyen and Anh Tran. Wanet-imperceppible warping-based backdoor attack. arXiv preprint arXiv:2102. 10369, 2021.
Tuan Anh Nguyen and Anh Tran. Input-aware dynamic backdoor attack. Advances in Neural Information Processing Systems, 33:3454 3364444-3464, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Gilles Pisier. Remarques sur un résultat non publié de b. maurey. Séminaire Analyse fonctionnelle (dit, pp. 1-12, 1981.
Han Qiu, Yi Zeng, Shangwei Guo, Tianwei Zhang, Meikang Qiu, and Bhavani Thuraisingham. Deepsweep: An evaluation framework for mitigating dnn backdoor attacks using data augmen- tation. In Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pp. 363-377, 2021. 2021.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. Advances in neural information processing systems, 32, 2019.
Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor at- tacks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 11957- 11965, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1555 2014.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems, pp. 8000-8010, 2018
Alexander Turner, Dimitris Tsipras, and Aleksander Madry. Label-consistent backdoor attacks.
arXiv preprint arXiv: 11XX:::9/2.0277/ 2019.
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 707-723. IEEE, 2019.
Ren Wang, Gaoyuan Zhang, Sijia Liu, Pin-Yu Chen, Jinjun Xiong, and Meng Wang. Practical detection of trojan neural networks: Data-limited and data-free cases. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXIII 16, pp. 238. Springer, 2020.
Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. arXiv preprint arXiv:2003.088 08900, 2020.
Xiaojun Xu, Qi Wang, Huichen Li, Nikita Borisov, Carl A Gunter, and Bo Li. Detecting ai trojans using meta neural analysis. arXiv preprint arXiv: 191.039110001337 2019.
Dong Yin, Ranchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International conference on machine learning, pp. 7085-7094, PMLR, 2019.
12

---

Published as a conference paper at ICLR 2022
Yi Zeng, Won Park, Z Morley Mao, and Ruoxi Jia. Rethinking the backdoor attacks' triggers: A frequency perspective. In ICCV, 2021.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550, 2002.
Shihao Zhao, Xingjun Ma, Xiang Zheng, James Bailey, Jingjing Chen, and Yu-Gang Jiang. Clean- label backdoor attacks on video recognition models, 2020.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 CONVERGENCE BOUND
Consider the minimax formulation of backdoor unlearning defined in (1). To simply the nota- tion, we will use 0 instead of 0,, unless otherwise specified. We start by defining ( 0) = 5 + V (5, f), where (sum of cross-entropies) is twice continuously differentiable w.r.t. both and 6. Recall that H(- f) is (0) -st-snnyy convex and L (f)-Lipschitz smooth, where un (-) and L are continuously differentiable. By setting the step size a()) Ln(0)+un(f) can be shown that (-, 0) is a contraction for some coefficient qo = max {1
a (0) 1}. The (x) Note that, for every where x0) (n)
<(9) optimal choice of the step-size leads qo x(0)+I'
i (1, K), E O
PA (0)I & &HH (6,(0),0) < LH (O)I. Hence, the condition number of H (6) 0) is smaller than kc(0) (Grazzi et al., 2020).
Let 0, (6, f) and (6, 8) denote the partial Jacobians of at (6, 0) w.r.t the first and the second variables, respectively. We can write the derivatives of + as:
0, 0) = - (6, 0) Va( a ( (,4 0) = (0)
(8)
When evaluated at (8(0),0), the partial Jacobian w.r.t the second variable, 024(6(0), 0), can be simplified as:
a2
- (()())))))))
Thus, [()) a()) (((()),
(((((())))) 0)1. Following the notations from (Grazzi et al., 2020),
we create the bound of the partial Jacobian of be L 2 (02)()(0),0)) 0)I. By our assumption, the bound for the cross derivative term 8 is Ln. 2 (O(0), O)| Hence, we can choose:
La = Ln.e.
(10)
Let A = 18, (61, 0, tb (62. f)ll and Da,s 10 (61, 0) 8, (52, 0)l. By assump- tion on the Lipschitz continuity and norm boundedness of second-ordd terms, we have
A |a(0) (Vi (61.0) v (f2, 0)) S a00) 1| 5el1,
(11)
and:
A =11 HV () V (62, () (o) + a()) H - H (02, 0))
(12)
< (L) Va(0) + a()))2.) |61 - 521l
Thus, 0,0(-, 0) is Lipschitz continuous with constant
U1 == a0))
(13)
and (- Lipschitz continuous with constant
22 = I (O)[ + (00))20
(14)
Recall the result from (Grazzi et al., 2020):
Lemma The approximate hypergradient has error bounded by
ob
| - (0)( = (c.(0) + c2( 1 go
po(t) c3(())b
(15)
where
(0) 17,00 M.loe.
Cs.
1-98
(0) V2.0 + Lro00
LH,OCs.
(16)
1090
(0)
Lu.oLe,
1-40
The proof of Theorem and (14).
uses the inequality from Lemma with the constants specified in (10), (13),
14

---

Published as a conference paper at ICLR 2022
A.2 GENERALIZATION BOUNDS
Following the notations from (Bartlett et al., 2017), we define general margin operator M(U, v) = By maxjøy 2/5 and the ramp loss ly with given margin yy:
((r) = {
F< -Y r E [=,00 r> 0
1+rh
(17)
According to (Yin et al., 2019), the population risk against a perturbation à is given by:
(0) = B +))0((=)))))))))
(18)
and the empirical risk is given by:
(0) = E4-MM00
(19)
Note that (0) and (0) are the upper bounds of the fraction of errors on the source distribution and the dataset used for unlearning, Deans respectively. Finally, given a set of real-valued functions H. recall the Rademacher complexity as:
R (His) -n sup NEW
Syh (1),
(20)
where E {+1} is the Rademacher random variable. The following bound of the adversarial unlearning can be derived using standard tools in Rademacher complexity.
Lemma Given unlearned models with 0 θ and some margin 7 >> O, define:
θ, = + -
+ 8), EE
(21)
The following holds with the probability at least 1 - over the clean dataset, Daan (see Algorithm 1) for every 0 E O:
In(1/E)
Pr arg (axg v (,, 2R ((Or))D.on)
+3/
(22)
2n
To instantiate this bound, we only need control the Rademacher complexity, & ((O.))Dsen) for linear models and neural networks.
A.2.1 PROOF FOR LINEAR MODELS
Define the set of linear, poisoned models under perturbation 8:
glin = {2 v) + (0, x + E
(23)
where 9 can regarded as a weight matrix ||@] bounded by Cg. Recall that the perturbation norm ||o]| is bounded by Cs, and the input 12 norm || is bounded by x. We proceed to evaluate the
15

---

Published as a conference paper at ICLR 2022
upper bound of the Rademacher complexity:
1
R ((o))
= Es
sup 1011 Co
S, + 5)
11
j=1
n Σ S5(2 + 8) j=1
$ E,
sup
|||||
(auchy-Schwwar inequality)
[0 n
I Cg
Σ 55 + 5) 1=1
(given that ||0|| S Ca)
n Σ Sjz
72
(24)
CgE,
ΣS
5
j=1
C.
Σ fj
8
Sj
(Triangle inequality)
n
f=1
1
Co
E
Sjzp
+
E
6
8
j=1
B
In particular, A can be bounded by:
A
E
j
k=1
Eg
Σ
Sysk (1), (Jensen's 's inequality)
71
j.k
(25)
S
| 1|
n
/=1
X
nn
Similarly, B can be bounded by:
B S E
sup
8
|
C5 E
Σ
(given that ||o|| S C&))
n
Ø=1
(26)
C3s
E, Σ
Sysk (Jensen's 's inequality)
n
j.k
Cs
vn
Thus, we can bound the Rademacher complexity as following:
R ((O+))D....) - Colx + Cs)
(27)
/n
Substituting (27) the (22) completes the proof of Theorem 2.
16

---

Published as a conference paper at ICLR 2022
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, (( Let (U, c, |l I]) denotes the least cardinality of any subset V U that covers U scale with norm ||-1|, i.e., sup minnev || B]| Recall the Dudley entropy integral below.
Lemma 3 Assume that the input values are norm bounded by 1,
4a Vn
12
R ((Or))D)..))
inf
VlggN ((O,) Dran l1 -11--12)dd 112
(28)
as0
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, N ((on) || Il2). 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 lay- ers 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).
Step ()): Input Layer Matrix Covering. The covering number of the input layer considers the matrix product, 2 (X A)A,, where A₁ Rd is the weight matrix of the input layer, X E Raxd is the input data, and A [ō. is the UNO perturbation vector repeated
times to get the same shape as X. Note that 2 can be rewritten as:
2 = (X + A)A1
A AAI
|| X Un
(29)
where I, is the n identity matrix, X is an n x + n)) matrix, and Å₁ is (d (d++)) n) m matrix. Now, the goal of step (I) is to find the covering number for the matrix product, X A
Given X E Raxd, we can obtain the normalized matrix Y Raxd by rescaling the columns of X to have unit p-norm: Y.j = X [| Let No = 2(n + d)m, and define
V ....... VNO] = {6l Un Je,e] :g (-1,+1), {1..... n). tl...... m)}
(30)
For < 2, the results from (Bartlett al., 2017) implies:
Xe
max 1
<
II| Y I, |e:ll2 max
2
<
1.
(31)
ie (e...No))
Define Og (d+n)xx to be "rescaling matrix":
| ll |X
|X,all,
||
0g
|
||ll
(32)
1
17

---

Published as a conference paper at ICLR 2022
where the purpose of ag is to annul the rescaling of X introduced by y = In l.i..,, XÅ1
Yoo @ A1), and o denotes the dlement-wise product. Let B oo 2 Å1. Then, we have:
(X A)A1 XÁ1
= VB
nid
Biseie T
= 11
u+d m
By ezej
(33)
B
= =|B||| atd m
Bij
( In leses"
||B||]
E ||B||| conv ((V..... vra3) }))
where conv (Lv...., VNo }) is the convex hull of [i...., VNO }. Given conjugate exponents (p, q) and (r, 8) with s 2, by the conjugacy of I1-1pp.- and I1-11g.e*
B
(oo, | I |1oolpp Al lla.s-
(34)
Defining C the desired cover of the first layer XA1:
|
No V3 k
No k
B
Vis : ((I...., [Nol* j. (35)
0,
h
where, is
av (1+mm (1Ix
By construction, |C| S [No] l. Now, prove that
is the desired cover set. The technique is generalized from (Bartlett et al., 2017) to backdoor unlearning.
Consider the case of ||A1112,1 i.e., (q, = (2, 1), and let ||Ar|1,, S ag. then we get:
|oollppr = 11 (laa,,,,...,,,,,,,.lll ||a,mll1)
(1111 ...., [xeall I, 1...... 1, ..... || ..... || 1, 1111 11,)
-m//r/ 1//r///
[ 1x [
1/p
// 1/r
Σ 1x +
S/ (IXI1> + n n1/0)
(36)
Subsequently, the bound of
A
be derived from:
2,1
A
A
AA1
2,1
Ag
A.m
1|
(37)
AA,1
AAm
(1.A112 + IIA
1/2
(I.A. ll2
-| 112) 1/2
18

---

Published as a conference paper at ICLR 2022
where we have:
8
|| |AA
A
8
A
2
(38)
8 Ag
(8 A.i)
(8 A.a)
(8 A.2)
Therefore, substituting (38) to (37) gives us the bound:
A
(114, + (oT 1/2 (1.4m 11 + 1 A.m)) 1/21 >m))))/)
||11111 nn 110T A. || ..... || 21 + n n/122 110 110AA..) A.mll
||Aall + 1/2 188 A,ll +... + | l12 + + 1/2 | A.m
m
||A1112,1 + 1/2
118 A.ll
(39)
j=1
m
S ||A1ll2, + 1/2
Σ
(1181 ||A l22
#=1
||Aill2,1 (1 (1+mn' mmme m2n0/1110112)
+ mn mn)
s ao
Let 01 = dg (1 mn //()) Given the case A| 112, we can obtain the bound for [
B < (e S m/t/r (1X1), + nz/p) a1-
(40)
Thus, combining (31) and following the Maurey lemma (Pisier (1981), Zhang (2002), Lemma 1), we have:
No. ||||| &
1 1/
(X + A)A1
h;
V.
max No...N
k
(41)
( Il, + n )
S E1
which shows that the desired cover element is in C.
Theorem In the case of the input layer of poisoned model, 0, consider A the UNO perturba- tion matrix with rows of and A E Ig R&dxm to be the weight metrix of the first layer. The covering resolution 6j given. Defining a1 an (1 + mn mn)) where ag the bound of | 1A for any input X E Raxd the convering number is bounded as follows:
a1 ( 1p + nn2222 22//22m22// m/r
In (1(X+A)AA) A)A1 A1 E Rdxm) 61, ,, 11.1111122)
In(2(d + n)m).
(42)
Step (II): Other Layer's Matrix Covering. Let's define Z Ro:xd, as the input of specific layer of the neural network, and A; E gd;x0m, as the weight matrix of that layer. Given conjugate exponents (p. q) and (r, 8) with p < 2, let Aill I a, Lastly, the covering resolution of each
19

---

Published as a conference paper at ICLR 2022
layer, ç, is given. Since perturbation is considered in the following layers, directly adopt the covering studied (Bartlett et al., 2017) as follows:
[1, mm, 2/r
In. (IZA, A, E IR xm ||Aillg. S a.) ex. - -
In(2d,
(43)
e,2
Step (III:: The Whole Network Covering Bound. Recall that the whole neural network is struc- tured as follows: (z == σL (ALØL-1 (AL-1-. (A1z)...)) where d; is e. e:-Lipschitz
Define sequences of vector spaces Vi...., : V2 and W2...., WL+1. where V; has norm | and W; has a norm III llle. The linear operators, A, V; + W4+1, are associated with some operator norm |Ails-s-11 I 8t, i.e., |Aili-si1 = || S supiz .s 1114 = 8;- Then, letting EnSl G2i IT @181, with given convering resolutions, (e1,-..; :.), the neural net images, Hxx = [Fo(X + +))}, have the covering number bound (Bartlett al., 2017):
-H-x,,,1-11-1)
II sup (Apooddi-)) vicc
N (A + A)} 64 IIl- I1b++t).. (44)
Step (IV): Proof of Theorem 3. The key technique in the remainder of this proof is
to substitute covering number estimates from (42) and (43) into (44) but
. 2) centering the covers at 0 (meaning the cover at layer E (2, L) satisfies ||A:ll2,
A
||1 S au. and || =
a1), and
AAI
2,1
3) collecting ( Fn)
rows of matrix X E Rnxdd
To start, the covering number estimate of the whole network from (44) when combined with (42) and (43) (specifically with p 2, 1, and W max(do..... ..., results in:
ln (Hx. e, 112)
( ArE F (AndamAAL)) (
X Th
D}
< E -1 sup (gI IN Beet
es. -1111
XT
1)
Supa, IN
A
E1, 1e1.11-12
In
(IIN
XxT
2 sli (A2 IN
Ar (PP(AImAAA)))
un
(45)
Vysce
X
A
In
< suppA À
In (2 +n))
of
([x,
X
D)
In
In (2W2),
22 sup -1))
Vysce
where (+) equality holds since 1) l2 coverings of matrix and its transpose are the same, and 2) the
1) (!x
x
cover can be translated by F F(A AA
AJ without changing its cardinality. We further simplify (45), by evaluating the following norm for any A, E (A2, ......... AL-1):
[(Ardemmdii)) ([ T I 1)
([ X
D)>1
(A
0i-1
2
([ XT X
1)
A
(46)
1)
In
([
D
< 01-181-1
F(ArAAmAAAn))
Th
20

---

Published as a conference paper at ICLR 2022
which by induction gives
([
X I 1)
i-1 II
max
ej
(IIX
1222)
2y55.
(47)
5=1
Combining (46) and (47), the cover is bounded by:
In
a1 ( In + +n) + Ei=2
(0x Tacres oj In(2W3)
(48)
1
+ 11 I o In (n(2 (W +n))
e
Let
age
1
(
2/3
aj
2/3
6i
@: 111s>> C33j
where
aj
á
8i
8j
(49)
then,
ln (HH, e, 112) < (III)=t In(2W
IT e3 (a²))
(50)
Consider the class of networks, O,N, obtained by affixing the ramp loss, ey, and the negated margin operator, -M, to the output of the provided network class:
NN ((x,)) ((- : E
(51)
Since v) + (-MM(zz, v)) is 2/72-LLischhiii w.r.t. || ||2 and definition of ey the function class ONN falls under the setting of (50), the covering number of a set of all neural networks is bounded as follows:
In In ((ONM) 12 11 11
In 4[If ozee) Els h4
2/33
(52)
(IX +v (W
Using the above covering number bound (52) in the Dudley entropy integral (28) with a == 1/Vo. we achieve the bound for the Rademacher complexity as follows:
ai ((Fr)
s inf
4a vn +
12 P 1I(V
vn) in (2W (W + +n)
4
24 Vn) In(2 (W + +))
II s:2=
Σ dg
2/3
<
m
$
2/3
(53)
We complete the proof of Theorem by substituting (53) in (22).
A.2.3 EMPERICAL VALIDATION OF THEOREM 3
In this section, we empirically verify Theorem 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- (poison rate: 20%, target label: 2).
Model Name
Parameters
W
Average Error Gap (%)
ResNet-18
11689512
512
0.35
GoogLeeNet
6624904
832
0.27
DenseNet-121
7978856
1024
0.24
Table 7: Empirical Error Gap with different widths (W) of the neuron networks. Each network adopted and trained from scratch for 50 epochs and achieves the same level of ASR (99.48 48 = 0.5%). We obtained the Error Gap using the original poisoning trigger (Trojan WM) after the model was defended by I-BAU and reported the results from average 5 runs.
21

---

Published as a conference paper at ICLR 2022
Table 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 gap is smaller the model width grows, indicating better generalizability. Aligning with Theorem 3, the generalizability has a positive correlation with W.
Clean Samples Average Error Gap (%)
500
2500
0.71
5000
0.35
Table 8: Empirical Error Gap with different numbers of available clean samples. We adopted the poisoned ResNet-18 from Table 7 for this experiment. We obtained the Error Gaps using I-BAU defended models with different clean samples and reported the results from the average of 5 runs.
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 better generalization of unlearning effect from training to unseen data. Such results aligned with Theorem
A.3 IMPLEMENTATION DETAILS AND COMPLEXITY ANALYSIS
I-BAU does not need compute the second-order derivative directly. Instead, 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 al., 2020)) in limited rounds along with the reverse mode of automatic differentiation (Baur & Strassen, 1983; Griewank Walther, 2008) by treating the problem as linear system. Automatic differentiation in reverse mode is 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 I and the memory and time complexity analysis and comparisons.
A.3.1 ABLATION STUDY ON THE l2 NORM BOUND
This section studies the impact of the preset l2 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 of the synthesized trigger as long as the trigger's 's value is within the image value range (from 0 to in our case with float type images).
constrained
Effort
99.5
(%)
98.5
97.5
20
Epoches
Epoches (b)
Figure 2: Evaluation of different la norm bound would impact the ACC/ASR mitigating Trojan WM attack the GTSRB dataset. Each of the results listed is averaged from independent runs using different random seeds.
The la norn of launching the Trojan WM attack is 8.739 (measured by comparing with matrix of the same size). As shown in Figure a larger norm bound leads to a more robust and accurate synthesis of the potential trigger on the GTSRB. Especially the la norm bounds that greater than
22

---

Published as a conference paper at ICLR 2022
the attack trigger's by 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 l2 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 V8(0) = - (V)H(5(0)) 0)) ((((0(( via automatic differentiation is no more than twice the memory used when com- puting (H 0), which making our space complexity (em(VH((, 0)). Recalling another popular class of methods to solve bilevel aptimization-expiieee
Inpul (32 x 3)
Conv2d 3 3132 x 32 32)
Conv2d 3 x (32 x 32 x 32]
Max-Pooling 2 x (16 x 16 32)
Dropout (0.3) (16 x 16 x 32)
Conv2d 3 x 3(16 x 16 x 644]
Conv2d 3 x 3 x 16 x 64)
Max-Pooling 2 2 x 8 x 64)
gradient methods (Grazzi et al., 2020), whose memory complexity is Mem( (K T (H ()) as they need to save the full computational graph during back- propagation, 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.
Dropout (0.4) x 16 x 32)
Conv2d x (8 x 128)
Conv2d x (8 x 128)
Max-Pooling 2
128)
Dropout (16 x 16 32)
Flatten (2048)
Dense (C)
The target model details. The simplified VGG model contains three simplified VGG blocks, of which each contains two convolutional layers in cach block. Here, we report the size of cach layer.
Table 9:
A.3.3 TIME COMPLEXITY ANALYSIS
Following our design of Algorithm (total K rounds), assuming using the fixed-point algorithm Grazzi et al. (2020) as the iterative solver with iterations for line 7, Algorithm 1, the time com- plexity would be Ö(K 0- (O(())). where Ō(0) is the time complexity of training a neuronal network, 0, via backpropagation for one epoch the clean images used for unlearning (for most of the ex- periments, we used 5000 samples). In practice, we adopted v = 5, and for most of the one-target attack cases, K = 1 is enough to provide effective defenses (ASRs drop to random guessing rate). Below are some theoretical analyses and comparison of I-BAU with other state-of-art defenses listed in Table regarding the time complexities:
NC and TABOR require to go through all classes (C = 10 for the CIFAR-10 and C = 43 for the GTSRB), and each label requires large number of steps (Kı steps) of optimization to synthesize the trigger. Roughly their time complexity under the settings of limited iterations is Ö(K,- C. Ö()). In practice, K₁ - C' is much larger than K- 9.
DI incorporated an additional GAN to synthesis the trigger, assuming training and implementing the GAN is of the time complexity Ö(QGAN), thus making the total time complexity roughly equals to ((mar(0((GAN). (())). In practice, the overhead of training a GAN trigger in- spector is much expensive (estimated 300x longer GPU time on the 10FAR-10) than training 6.
FP mitigates backdoor attacks via multi rounds (K2 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) meet the stop requirements.
NAD's s time complexity is proportional to the number of epochs used to fine-tune the student and teacher models. As those two models share the same structure, assume the time complexity of training them over the unlearning dataset is Ö()). Assuming teacher model training phase takes Kg epochs, and tuning student model based on the teacher model takes K2 epochs, then
the total time complexity is Ō((Kg + 2 x (a)) In practice, we adopted K₃- = K4 = 20 according to the original work.
23

---

Published as a conference paper at ICLR 2022
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 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 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 conducted with iterative optimizers (SGD or Adam) with learning rate of 0.1.
A.4.1 ATTACKS DETAILS
We list the examples of the adopted backdoor attacks in this section. We incorporated eleven dif- ferent backdoor attacks in this work. Figure shows the examples from CIFAR-I0 and the GTSRB before and after patched with different backdoor triggers. We adopted the same target label on the two datasets under one- see-triiger-on -ne-tereet settings, as listed in Figure 3: BadNets white square trig- ger targeting at label 8 (BadNets) (Gu et al., 2017), Hello Kitry blending trigger targeting at label (Blend) (Chen et al., 2017), la norm constraint invisible trigger largeting al 0 (Eo inv) (Li et al., 2020a), l2 norm constraint invisible trigger targeting at 0 (f2 inv) (Li et al., 2020a), Smooth trigger (frequency invisble trigger) targeting at (Smooth) (Zeng et al., 2021), Trojan square targeting at 2 (Troj SQ) (Liu et al., 2018b), Trojan watermark targeting at 2 (Troj WM) (Liu et al., 2018b). For both CIFAR-10 and the GTSRB poisoned models, we train the models with the entire training set (50000 samples for CIFAR-10, 39209 for the GTSRB) with the fixed 20% poison rate across all the experiments. For unlearning, the available clean data is sampled from both datasets' test set with fixed size of 5000, where the remaining data (5000 for the CIAFR-I0 10 and 7630 for the GTSRB) will be used to evaluate the unlearning efficacy (ACC and ASR).
Clean
BadNett::
Blend:
inv:
La
Smooth:
Troj-SQ:
Troj-WM:
Cifar-10
GTSRB
20
20
20
20
20
20
20
20
Figure 3: Datasets and examples of backdoor attacks that considered in the main text. We consider two different datasets this work, namely, the CIFAR-10 10 dataset and GTSRB dataset. Nine different backdoor attack triggers are included in the experimental part with one-trigger or multi-trigger attack patterns. Above, we show the target label used during the one-trigger attacks (e.g.. badnets targeting at label 8) of each backdoor attack.
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., 201 8a), Neural Attention Distillation (NAD) (Li et al., 2020b), and Differ- ential Privacy training as a general robustness defense (DP) (Du et al., 2019). The detailed settings of comparison are provided as follows:
24

---

Published as a conference paper at ICLR 2022
NC is conducted following the same settings 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 the generated trigger's '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 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
DP follows the settings in the work that first mentioned use DP as backdoor defense (Du et al., 2019), where we tuned the noise multiplier to attain universal effectiveness across all the consid- ered a50 for the CIFAR-10, 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 empir- ically. 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 re- places 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 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 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 sumple-speciff 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 another example of 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.
A.5.1 TOWARDS MITIGATING SR
We first evaluate an extreme case where we replace the poisoned CIFAR-10 images with an out- of-domain 'Hallo Kitty' image. Such 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 learning rate of 0. and an unlimited 12 norm bound (instead, we crop the perturbation's 's value and restricted it to 0-1 as discussed in Appendix 1).. The results before and after are listed below in Table 10.
httpp:://gi wwwp:tttww...o.ooooooeoeeeeeaeae cow/bboyl1/ooooooooooooooooooogo 1yg /
25

---

Published as a conference paper at ICLR 2022
Clean ACC Before
ASR Refore
Clean ACC AAfer
ASR After
83.82%
100.00%
82.12%
0.00%
Table 10: Empirical evaluation on I-BAU's effectiveness towards semantical replacement as backdoor attack.
As demonstrated in Table 10, within three rounds of I-BAU, we obtained 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 general- izability (aka, overfit 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 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 u 2, As for I-BAU, we adopted Adam optimizer and a learning rate of 0.0001 and an unlimited 12 norm bound. The results before and after are listed in Table 11, which indicates an effective defense with acceptable influence in the ACC.
Clean ACC- Before
ASR Before
Clean ACC- -After
ASR After
94.36%
99,62%
92.86%
10.80%
Table 11: Empirical evaluation on I-BAU's effectiveness towards WaNet.
A.5.3 TOWARDS MITIGATING THE IAB ATTACK
An emerging line of attack focuses on sample-specins attacks; here, we evaluate against IAB attack, which utilizes autoencoder to learn and insert sample-specific triggers. We followed the same implementation as provided in the original work 3, with the following specific settings: dataset: CIFAR-10; 10; target label:0; Pb Pe 0.1; model: NreActResNer11. One difference is that 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 [0, I]. instead of 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 [0. 1] for the current implementation). The results prior to and during the intervention are summarized in Table 12, indicating an effective defense with low influence in the ACC.
Clean ACC Before
ASR - Before
Clean ACC - After
ASR After
87.28%
99.20%
86.46%
9.58%
Table 12: Empirical evaluation on I-BAU's effectiveness towards the IAB attack.
A.5.4 TOWARDS MITIGATING HT
Finally, we evaluated the effectiveness of Hidden trigger (HT) backdoors (non-additive during poi- soning), 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 generate PGD noise: 1500, number of poison in target class: 800, e = 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
'nttps: http:::///tttti 'https:// /ttpss///ii thub. com cww. coom/vinA nA Kesearch/inputt-eeeeeeee httpre..ooo//aaaaaaaaaaaaaa/a/ee www.wwwwwwwww-e-o-----aaaa...e-e atte
26

---

Published as a conference paper at ICLR 2022
successful targeted attack, enlarged 50. During the fine-tuning process of [1]. we only fine-tuned the clean model (ACC:"84.60")) over the poison data, which resulted in poisoned model with an ACC/ASR of "73.41/89.00". After adopting I-BAU for 20 rounds, the poisoned model's s performance becomes 144.58/11.10" and with larger rounds (90 rounds), the performance can fur- ther be improved "84.06/0.23", which indicates robust and effective defense and 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 misclassification 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!
Samples with triggers
Samples without triggers
Class Number
Before L-BUU
Target label
After I-BAU
Class Number
Figure 4: TSNE analysis of the output features (flatten layer output of the NN, with size of (N 2048)) before and after backdoor unlearning using CIFAR-10 BadNets (targeting at 8) poisoned model. Each color in the color bar represents a different class from ().....).. We mark the sample with triggers and without triggers as listed in the Figure.
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 BadNets poisoned model on the CIFAR-10 10 dataset (target label is 8), and the results listed in Figure 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 effecttivnness 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.c., the all-to-all attacks and sttriger--7-taree cases the two evaluated datasets. We listed them here they take
27

---

Published as a conference paper at ICLR 2022
more rounds than cases, which usually be mitigated in one-shot-kill manner.
Clean Accuracy - Attack Success Rate
0.8
0.7
0.6
0.3
0.2
0.1
0.1
0.0
Epoches
Epoches
(b)
Figure 5: I-BAU iterative records under mitigating BadNets in all-to-all attack cases. (a). the results the CIFAR-10 where took more rounds for I-BAU to mitigate the attack successfully. (h). the results on GTSRB manage to mitigate the triggers with fewer rounds and less impact over the ACC.
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) the results on the GTSRB dataset. As shown in Figure 5 (a), although it takes more rounds than one-triggeeronne-tare 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 fewer rounds of I-BAU, and the unlearned model can maintain ACC of around 99% during the entire unlearning procedure.
Figure demonstrates the mitigation records of each iteration of I-BAU over the 7-trrgger---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 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.
Clean Accuracy
Trojan SQ
Smooth Blend
LG inv
Trojan WM
BadNets
inv
1.0
1.0
0.9
0.9
0.8
0.8
0.7
0.7
0.6
0.6
0.5
0.5
0.4
0.3
0.
50
100
150
200
250
300
350
400
20
40
60
100
Epoches
Epoches
(6)
(b)
Figure 6: I-BAU iterative records under mitigating 7-trigger-7-target attack cases. (a). the results on the CIFAR- 10 where took more rounds for the I-BAU to mitigate the attacks successfully. (b). the results the GTSRB manage mitigate the triggers with fewer rounds and less impact over the ACC.
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 casier be found 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).
28


Reviews:
[{"review_id": "pm8cQPS1uxn", "reviewer": "Reviewer_mJLa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. In most cases, the proposed I-BAU is not the state-of-the-art method. For example, (I) in Table 1, I-BAU is not the best defense for 6 out of 8 Attacks, i.e. BadNets, l_0 inv, Smooth, Trojan SQ, Trojan WM, All to all; (II) in Table 3, I-BAU is not as good as NAD in terms of ASR; and (III) in Table 4, NC has lower ASR and higher/comparable ACC than the proposed I-BAU. Therefore, it is questionable if I-BAU is able to reduce the attack success rate to a very low level.\n\n2. In page 6, only a simplified VGG model is used throughout the paper. So one question is whether the proposed method works well with different backbones, especially deeper networks.\n\n3. In page 2, it is assumed that the norm of the backdoor pattern delta is bounded by C_delta. However, in real-world applications, the magnitude of this norm may be unknown, thus restricting the usage of the proposed method.\n\n4. There is no empirical validation and justification of Theorem 1-3. For instance, in Theorem 3, the generalization bound can be measured by certain norms of weight matrices, the number of samples, Lipschitz constant, and so on. Hence, after a model is trained and fixed, it is possible to empirically justify if the theorems are true. It is also interesting to empirically investigate the bounds with regard to different weights (i.e. network architectures), number of samples, etc.\n", "summary_of_the_paper": "The paper studies the backdoor attack problem and proposes a minimax formulation for the defense against adversaries. Theoretically, the paper analyzes the convergence bound and the generalization bound for the proposed method. Empirically, the paper compares efficacy, stability, sensitivity, and efficiency with several competitive methods.", "summary_of_the_review": "One of the main issues is that the proposed method can hardly achieve the lowest ASR. Although I-BAU seems to be more stable, one may resort to the best defense for a corresponding attack if ASR has a high priority.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oN259ufsiEB", "reviewer": "Reviewer_GDHf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1 . The min-max formulation of backdoor removal is quite intuitive, however, the perturbation constraint is a bit hard to quantify. The authors adopt a simple L2 norm constraint, which definitely makes it easier for computation, yet it also constrains the defense effect to only L2 norm bounded triggers. For example, I am not quite sure whether the proposed method can effectively handle the hidden trigger attack in [1]. Maybe extending the framework to also Linf norm would be beneficial.\n\n[1] \"Hidden trigger backdoor attacks.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 07. 2020.\n\n2 . The derivation to eq (4) is straightforward. The authors mentioned that “it can be implemented in a memory-efficient manner”, however, I didn’t find any description on how this memory-efficient manner was implemented? From eq (4), it seems that one still needs to compute the second-order derivatives of H, which can still take quite a large memory? \n\n3 . The convergence results seem to directly follow (Grazzi et al., 2020) with similar assumptions and conclusions. I wonder what is the uniqueness of this result presented in the paper?\n\n4.  The trigger removal experiments in Table 1 showed that the proposed algorithm is indeed more comprehensive, however, it does not achieve the best performances on many test cases, especially in terms of ASR.\n\n5. In Table 5, where the authors showed the relationship between performances and the number of clean samples. While most baselines seem to achieve worse results when the number of clean samples decreases, yet the proposed method actually got slightly better ASR with a small portion of clean samples. This is actually quite counterintuitive. Will that be due to the random choice of clean samples? The authors might want to take a look into the details.\n\nTypo: Above Table 5, “extrema” -> “extreme”\n", "summary_of_the_paper": "In this paper, the authors proposed a minimax formulation for removing backdoors from a given poisoned model based on a small set of clean data. Unlike previous work, which breaks down the minimax into separate inner and outer problems, the proposed algorithm utilizes the implicit hypergradient to account for the interdependence between inner and outer optimization. The authors also theoretically analyzed its convergence and the generalizability of the robustness gained by solving minimax on clean data to unseen test data. Extensive experiments showed improved backdoor defense performances and less computation time on several backdoor attacks over various attack settings.", "summary_of_the_review": "The paper is in general well written. However, there still exists some concerns towards the applicability of the proposed method as well as the uniqueness of the theoretical result. I think it is on the borderline. Depending on the authors' response, I may raise my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dZ24daNetD", "reviewer": "Reviewer_u6du", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n1. The idea of using implicit hypergradient in adversarial training is, to the best of my knowledge, novel and interesting. \n2. The paper demonstrates that I-BAU is effective against multiple backdoor attacks in various settings (# of triggers and # of target labels) \n\nCons: \n1. The paper does not cite a relevant work by J.Geiping et. al [1] which successfully adopts adversarial learning to defend against backdoor attacks. Also, I-BAU is not compared to the algorithm in [1]. \n2. The paper's clarity could be improved, in particular grammar. For example, there is a typo in the abstract (Implicit Bacdoor) and numerous typos in the main body (diffrencial prevacy, etc.). Also, some sentences are very confusing, for example in section 6 it is written \"Can I-BAU effectively remove various backdoor triggers\". I am confused with how the proposed approach should remove the backdoor triggers.  \n\n\n[1] What Doesn't Kill You Makes You Robust(er): Adversarial Training against Poisons and Backdoors", "summary_of_the_paper": "The paper formulates adversarial training against backdoor poison attacks and proposes to use implicit hypergradient to solve the minimax problem instead of breaking it down into separate inner and outer optimization problems. The authors perform theoretical analysis of the algorithm and find convergence bound and generalization bound for the method. Also, the authors evaluate the proposed adversarial training routine, called I-BAU (Implicit Backdoor Adversarial Unlearning) in three attack settings:  (1) One-trigger-one-target attack, (2) One-trigger-all-to-all attack, (3) Multi-trigger-multi-target attack and compare with six defenses. For each attack setting, the authors test 7 different backdoor attacks. The results show that the efficiency of I-BAU is comparable to the best baseline for each of the attacks and is more time-efficient than other defenses. Finally, the authors show that I-BAU leads to a more stable training comparing to using universal adversarial perturbations in adversarial learning. ", "summary_of_the_review": "Although the empirical results for the method are appealing and the idea of using implicit hypergradient is interesting, the paper does not review previous work in adversarial training against backdoor attacks [1] which is extremely relevant and does not compare the proposed method with the existing algorithm. Also, the writing could be significantly improved. Because of these concerns, I vote for weak reject. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KSr5w06ULgf", "reviewer": "Reviewer_EmBg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strength**\n\n(1) Overall, this paper is well-organized and easy to read. The proposed algorithm seems natural. Extensive experiments are conducted to illustrate the effectiveness and efficiency of the proposed algorithm. The comparison with other baselines also demonstrates superiority, which really convinces me.\n\n(2) This research also includes some theoretical analysis, which is actually the missing part in current studies on backdoor attacks. This could be useful for future research.\n\n\n**Weakness**\n\n(1) Can the authors give a detailed description of how to implement I-BAU in practice and its time complexity? The reviewer is confused with the implementation and the efficiency, since the update of I-BAU in Eqn. (4) requires an inverse of a second-order derivative, which may not be supported directly by PyTorch/Tensorflow and may be extremely slow. However, the authors argue that the proposed I-BAU is more efficient than other baselines in Section 6.4.\n\n(2) Is the sole difference between I-BAU and naive method (i.e., adversarial learning with universal perturbation) the implicit gradient in Eqn. (2)? Specifically, they both generate adversarial perturbation for each individual example within the sampled batch and add the perturbations together. Next, the naive method merely updates model parameters with the direct gradient, whereas I-BAU updates with the direct gradient plus an additional implicit gradient. Is the reviewer's understanding correct?\n\nIf so, can the authors explain why such an extra implicit gradient could stabilize the training and reduce ASR significantly in Section 6.2? This is not very intuitive.\n\nFurthermore, the proposed I-BAU inherits the shortcoming of the universal perturbation (i.e., \"the adversarial effect of individual perturbations may be canceled out by the addition operation\" in the first paragraph of Section 4. Algorithm). As a result, part of the comments in the first paragraph of Section 4 might be unfair for the natural algorithm design.\n\n(3) This paper assumes that the perturbation pattern is static and fixed for any examples upon being patched (see Minimux formulation for defense in Section 3). Unfortunately, some attacks are contrary to such an assumption. For example, the input-aware backdoor (IAB) attack [R.1] makes use of a dynamic trigger that varies across inputs. Can I-BAU still defend against IAB attack? \n\nFurthermore, the formulation of Eqn. (1) actually requires an assumption, namely, the trigger pattern is static and fixed across inputs, in addition to the bounded norm constraint. As a result, the discussion advantages 2) in Section 3 appears to be incorrect. \n\n[R.1] Tuan Anh Nguyen and Anh Tran. Input-Aware Dynamic Backdoor Attack. In NeurIPS, 2020.\n\n(4) This paper only evaluates results with a simplified VGG, which only has low natural accuracy on CIFAR-10 (80%-86% in this paper, while the natural accuracy of a standard VGG usually achieves 92.64% [R.2] or 93.34% [R.3]), which brings difficult to determine whether the proposed method still works in larger models. \nA large model may still be able to remember the backdoor behavior even after fine-tuning, since its large compacity. It is better to evaluate the performance across more architectures, such as ResNet-18 which has at least 93% of natural accuracy.\n\n[R.2] https://github.com/kuangliu/pytorch-cifar\n\n[R.3] https://github.com/bearpaw/pytorch-classification\n\n(5) In practice, after downloading a model from the Internet, we can't tell whether it is backdoored or not. If the model is a benign one, would I-BAU hurt its performance?\n\n(6) In adversarial training, the perturbation budget has a significant impact on robustness and natural accuracy. Since I-BAU is a variant from adversarial training, how does the ASR/ACC change with respect to varying norm constraints $C_{\\delta}$?\n\n(7) (Just a suggestion; no influence on my decision) When evaluating the ASR of models, it would be better to exclude the samples belonging to the target class. Because the perfectly robust model achieves 0% of ASR, it is much easier to compare ASR directly (i.e., the lower the ASR, the more robust the model). Otherwise, because the perfectly robust model still predicts the target class for poisoned samples whose ground truth is the target class,  it would have a non-zero ASR (e.g., 10% on CIFAR-10).\n\nIf the authors could solve some concerns mentioned above, the reviewer would reconsider the rating.", "summary_of_the_paper": "This study investigates defense against backdoor attacks for models that have already been trained. It proposes, in particular, a min-max formulation for backdoor defense, in which the inner maximum seeks a powerful trigger that leads to a high loss, while the outer minimum seeks to suppress the \"adversarial loss\", so as to unlearn the injected backdoor behaviors. To solve the minimax, the authors also propose a method, Implicit Backdoor Adversarial Unlearning (I-BAU). In addition, the authors also provide theoretical analysis including the convergence bound and generalization bound. Extensive experiments demonstrate the effectiveness and efficiency of the proposed method.\n\n", "summary_of_the_review": "Although the proposed method is natural and effective and the paper has many merits, there are some concerns including implementation details, some discussion in the paper, and lack of evaluation on more model architectures. The reviewer will recommend this paper if some concerns have been addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates defense against backdoor attacks for models that have already been trained. It proposes, in particular, a min-max formulation for backdoor defense, in which the inner maximum seeks a powerful trigger that leads to a high loss, while the outer minimum seeks to suppress the "adversarial loss", so as to unlearn the injected backdoor behaviors. To solve the minimax, the authors also propose a method, Implicit Backdoor Adversarial Unlearning (I-BAU). In addition, the authors also provide theoretical analysis including the convergence bound and generalization bound. Extensive experiments demonstrate the effectiveness and efficiency of the proposed method. 

The proposed method is interesting and the implementation is nice. Overall, there is a fundamental flaw in the formulation: if the trigger is not additive (where there are many such examples of poisoning attacks that are not additive) this approach should fail completely. Not having experiments that discuss such triggers that are not additive is a significant flaw in the presentation of the paper. Another flaw is that the trigger is assumed to be small norm. Unlike adversarial examples attacks (at test time), there is no reason for backdoor triggers to be of small norm. Given that the defense critically relies on these two flawed assumptions, and the extent of how the proposed algorithm is sensitive to these assumptions are not properly addressed in the experiments, this paper is on the border line.
Decision: Accept (Poster)