summaries: 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.   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.  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. 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.
abstractText: 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-ofart 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× 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.
authors.name: ADVERSARIAL UNLEARNING
authors.name: PLICIT HYPERGRADIENT
authors.name: Yi Zeng
authors.name: Si Chen
authors.name: Won Park
authors.name: Z. Morley Mao
authors.name: Ming Jin
authors.name: Ruoxi Jia
references.authors: Eugene Bagdasaryan Vitaly Shmatikov
references.title: Blind backdoors in deep learning models, 2021
references.authors: Peter L Bartlett Dylan J Foster Matus J Telgarsky
references.title: Spectrally-normalized margin bounds for neural networks
references.venue: Advances in Neural Information Processing Systems,
references.authors: Walter Baur Volker Strassen
references.title: The complexity of partial derivatives
references.venue: Theoretical computer science,
references.authors: Atilim Gunes Baydin Barak A Pearlmutter Alexey Andreyevich Radul Jeffrey Mark Siskind
references.title: Automatic differentiation in machine learning: a survey
references.venue: Journal of machine learning research,
references.authors: Eitan Borgnia Valeriia Cherepanova Liam Fowl Amin Ghiasi Jonas Geiping Micah Goldblum Tom Goldstein Arjun Gupta
references.title: Strong data augmentation sanitizes poisoning and backdoor attacks without an accuracy tradeoff, 2020
references.authors: Richard H Byrd Gillian M Chin Will Neveitt Jorge Nocedal
references.title: On the use of stochastic hessian information in optimization methods for machine learning
references.venue: SIAM Journal on Optimization,
references.authors: Bryant Chen Wilka Carvalho Nathalie Baracaldo Heiko Ludwig Benjamin Edwards Taesung Lee Ian Molloy Biplav Srivastava
references.title: Detecting backdoor attacks on deep neural networks by activation clustering
references.venue: arXiv preprint arXiv:1811.03728,
references.authors: Huili Chen Cheng Fu Jishen Zhao Farinaz Koushanfar
references.title: Deepinspect: A black-box trojan detection and mitigation framework for deep neural networks
references.venue: In IJCAI,
references.authors: Xinyun Chen Chang Liu Bo Li Kimberly Lu Dawn Song
references.title: Targeted backdoor attacks on deep learning systems using data poisoning, 2017
references.authors: Edward Chou Florian Tramèr Giancarlo Pellegrino
references.title: Sentinet: Detecting localized universal attacks against deep learning systems
references.venue: In Deep Learning and Security Workshop,
references.authors: John M Danskin
references.title: The theory of max-min and its application to weapons allocation problems, volume
references.venue: Science & Business Media,
references.authors: Min Du Ruoxi Jia Dawn Song
references.title: Robust anomaly detection and backdoor attack detection via differential privacy
references.venue: arXiv preprint arXiv:1911.07116,
references.authors: Yansong Gao Change Xu Derui Wang Shiping Chen Damith C. Ranasinghe Surya Nepal
references.title: Strip: A defence against trojan attacks on deep neural networks
references.venue: In Proceedings of the 35th Annual Computer Security Applications Conference,
references.authors: Siddhant Garg Adarsh Kumar Vibhor Goel Yingyu Liang
references.title: Can adversarial weight perturbations inject neural backdoors
references.venue: Proceedings of the 29th ACM International Conference on Information & Knowledge Management, Oct 2020
references.authors: Riccardo Grazzi Luca Franceschi Massimiliano Pontil Saverio Salzo
references.title: On the iteration complexity of hypergradient computation
references.venue: In International Conference on Machine Learning,
references.authors: Andreas Griewank
references.title: Some bounds on the complexity of gradients, jacobians, and hessians
references.venue: In Complexity in numerical optimization,
references.authors: Andreas Griewank Andrea Walther
references.title: Evaluating derivatives: principles and techniques of algorithmic differentiation
references.authors: Tianyu Gu Brendan Dolan-Gavitt Siddharth Garg
references.title: Badnets: Identifying vulnerabilities in the machine learning model supply chain
references.venue: arXiv preprint arXiv:1708.06733,
references.authors: Wenbo Guo Lun Wang Xinyu Xing Min Du Dawn Song
references.title: Tabor: A highly accurate approach to inspecting and restoring trojan backdoors in ai systems
references.authors: Hasan Abed Al Kader Hammoud Bernard Ghanem
references.title: Check your other door! establishing backdoor attacks in the frequency domain
references.venue: arXiv preprint arXiv:2109.05507,
references.authors: Kunzhe Huang Yiming Li Baoyuan Wu Zhan Qin Kui Ren
references.title: Backdoor defense via decoupling the training process
references.venue: In ICLR,
references.authors: Jinyuan Jia Xiaoyu Cao Neil Zhenqiang Gong
references.title: Intrinsic certified robustness of bagging against data poisoning
references.authors: Jinyuan Jia Xiaoyu Cao Neil Zhenqiang Gong
references.title: Certified robustness of nearest neighbors against data poisoning
references.authors: Pang Wei Koh Percy Liang
references.title: Understanding black-box predictions via influence functions
references.venue: Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning,
references.authors: Alexander Levine Soheil Feizi
references.title: Deep partition aggregation: Provable defense against general poisoning
references.authors: Shaofeng Li Minhui Xue Benjamin Zhao Haojin Zhu Xinpeng Zhang
references.title: Invisible backdoor attacks on deep neural networks via steganography and regularization
references.venue: IEEE Transactions on Dependable and Secure Computing,
references.authors: Yige Li Xixiang Lyu Nodens Koren Lingjuan Lyu Bo Li Xingjun Ma
references.title: Neural attention distillation: Erasing backdoor triggers from deep neural networks
references.venue: In International Conference on Learning Representations,
references.authors: Yiming Li Baoyuan Wu Yong Jiang Zhifeng Li Shu-Tao Xia
references.title: Backdoor learning: A survey
references.venue: arXiv preprint arXiv:2007.08745,
references.authors: Yiming Li Tongqing Zhai Yong Jiang Zhifeng Li Shu-Tao Xia
references.title: Backdoor attack in the physical world
references.venue: In ICLR Workshop,
references.authors: Yiming Li Baoyuan Wu Yan Feng Yanbo Fan Yong Jiang Zhifeng Li Shu-Tao Xia
references.title: Semisupervised robust training with generalized perturbed neighborhood
references.venue: Pattern Recognition,
references.authors: Yuezun Li Yiming Li Baoyuan Wu Longkang Li Ran He Siwei Lyu
references.title: Invisible backdoor attack with sample-specific triggers
references.venue: In ICCV,
references.authors: Kang Liu Brendan Dolan-Gavitt Siddharth Garg
references.title: Fine-pruning: Defending against backdooring attacks on deep neural networks
references.venue: In International Symposium on Research in Attacks, Intrusions, and Defenses,
references.authors: Yingqi Liu Shiqing Ma Yousra Aafer Wen-Chuan Lee Juan Zhai Weihang Wang Xiangyu Zhang
references.title: Trojaning attack on neural networks
references.venue: In 25nd Annual Network and Distributed System Security Symposium, NDSS. The Internet Society,
references.authors: Yunfei Liu Xingjun Ma James Bailey Feng Lu
references.title: Reflection backdoor: A natural backdoor attack on deep neural networks
references.venue: In European Conference on Computer Vision,
references.authors: Aleksander Madry Aleksandar Makelov Ludwig Schmidt Dimitris Tsipras Adrian Vladu
references.title: Towards deep learning models resistant to adversarial attacks
references.venue: arXiv preprint arXiv:1706.06083,
references.authors: Seyed-Mohsen Moosavi-Dezfooli Alhussein Fawzi Omar Fawzi Pascal Frossard
references.title: Universal adversarial perturbations
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Anh Nguyen Anh Tran
references.title: Wanet–imperceptible warping-based backdoor attack
references.venue: arXiv preprint arXiv:2102.10369,
references.authors: Tuan Anh Nguyen Anh Tran
references.title: Input-aware dynamic backdoor attack
references.venue: Advances in Neural Information Processing Systems,
references.authors: Adam Paszke Sam Gross Francisco Massa Adam Lerer James Bradbury Gregory Chanan Trevor Killeen Zeming Lin Natalia Gimelshein Luca Antiga
references.title: Pytorch: An imperative style, high-performance deep learning library
references.venue: Advances in neural information processing systems,
references.authors: Gilles Pisier
references.title: Remarques sur un résultat non publié de b
references.venue: maurey. Séminaire Analyse fonctionnelle (dit, pp
references.authors: Han Qiu Yi Zeng Shangwei Guo Tianwei Zhang Meikang Qiu Bhavani Thuraisingham
references.title: Deepsweep: An evaluation framework for mitigating dnn backdoor attacks using data augmentation
references.venue: In Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security,
references.authors: Aravind Rajeswaran Chelsea Finn Sham M Kakade Sergey Levine
references.title: Meta-learning with implicit gradients
references.venue: Advances in neural information processing systems,
references.authors: Aniruddha Saha Akshayvarun Subramanya Hamed Pirsiavash
references.title: Hidden trigger backdoor attacks
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Karen Simonyan Andrew Zisserman
references.title: Very deep convolutional networks for large-scale image recognition
references.venue: arXiv preprint arXiv:1409.1556,
references.authors: Brandon Tran Jerry Li Aleksander Madry
references.title: Spectral signatures in backdoor attacks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Alexander Turner Dimitris Tsipras Aleksander Madry
references.title: Label-consistent backdoor attacks
references.venue: arXiv preprint arXiv:1912.02771,
references.authors: Bolun Wang Yuanshun Yao Shawn Shan Huiying Li Bimal Viswanath Haitao Zheng Ben Y Zhao
references.title: Neural cleanse: Identifying and mitigating backdoor attacks in neural networks
references.venue: IEEE Symposium on Security and Privacy (SP),
references.authors: Ren Wang Gaoyuan Zhang Sijia Liu Pin-Yu Chen Jinjun Xiong Meng Wang
references.title: Practical detection of trojan neural networks: Data-limited and data-free cases
references.venue: In Computer Vision–ECCV 2020: 16th European Conference,
references.authors: Maurice Weber Xiaojun Xu Bojan Karlaš Ce Zhang Bo Li
references.title: Rab: Provable robustness against backdoor attacks
references.venue: arXiv preprint arXiv:2003.08904,
references.authors: Xiaojun Xu Qi Wang Huichen Li Nikita Borisov Carl A Gunter Bo Li
references.title: Detecting ai trojans using meta neural analysis
references.authors: Dong Yin Ramchandran Kannan Peter Bartlett
references.title: Rademacher complexity for adversarially robust generalization
references.venue: In International conference on machine learning,
references.authors: Yi Zeng Won Park Z Morley Mao Ruoxi Jia
references.title: Rethinking the backdoor attacks’ triggers: A frequency perspective
references.venue: In ICCV,
references.authors: Tong Zhang
references.title: Covering number bounds of certain regularized linear function classes
references.venue: Journal of Machine Learning Research,
references.authors: Shihao Zhao Xingjun Ma Xiang Zheng James Bailey Jingjing Chen Yu-Gang Jiang
references.title: Cleanlabel backdoor attacks on video recognition
references.authors: Grazzi
references.title: 2020), whose memory complexity is Mem(K
references.venue: T · ∇H(δ,
references.authors: Grazzi
references.title: 2020) as the iterative solver with θ iterations for line 7, Algorithm 1, the time
sections.heading: 1 INTRODUCTION
sections.text: In backdoor attacks, adversaries aim to embed predefined triggers into a model during training time such that a test example, when patched with the trigger, is misclassified into a target class. For instance, it has been shown that one could use a sticker as the trigger to mislead a road sign classifier to identify STOP signs to speed limit signs (Gu et al., 2017). Such attacks pose a great challenge to deploy machine learning in mission-critical applications (Li et al., 2020c; 2021a).
  Various approaches have been proposed to remove the effect of backdoor attacks from a poisoned model. One popular class of approaches (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019) is to first synthesize the trigger patterns from the model and then unlearn the triggers. However, these approaches presume that backdoor triggers only target a small portion of classes, thereby becoming ineffective when many classes are targeted by the attacker. Moreover, they suffer from high computational costs, as they either require synthesizing the trigger for each class independently or training additional models to synthesize the triggers all at once. Another line of works does not rely on trigger synthesis; instead, it directly mitigates the triggers’ effects via, for example, finetuning and pruning the model parameters (Liu et al., 2018a) and preprocessing the model input (Qiu et al., 2021). While these approaches are more efficient than the trigger-synthesis-based approaches, they cannot maintain a good balance between robustness and model accuracy due to the unawareness of potential triggers. Recent work (Li et al., 2020b) proposes to leverage a teacher model to guide fine-tuning. However, our empirical studies find that the effectiveness of this approach is particularly sensitive to the underlying attack and data augmentation techniques utilized to enrich the fine-tuning dataset. Overall, it remains a challenge to design a defense that achieves a good balance between model accuracy, robustness, and computational efficiency.
  To address the challenge, we propose a minimax formulation to remove backdoor triggers from a poisoned model. The formulation encompasses prior works on trigger synthesis-based defense, which solves the inner and outer problems independently. Moreover, the formulation does not make ∗Correspondence to yizeng@vt.edu. Codes of implementations is opensourced on Github: I-BAU
  any assumption about the backdoor trigger beyond a bounded norm constraint, thus remaining effective across various attack settings. To solve the minimax, we propose an Implicit Bacdoor Adversarial Unlearning (I-BAU) algorithm based on implicit hypergradients. Unlike previous work, which breaks down the minimax into separate inner and outer optimization problems, our algorithm derives the implicit hypergradient to account for the interdependence between inner and outer optimization and uses it to update the poisoned model. We theoretically analyze the convergence of the proposed algorithm. Moreover, we investigate the generalization error of the minimax formulation, i.e., to what extent the robustness acquired by solving the minimax generalizes to unseen data in the test time. We present the generalization bounds for both linear models and neural networks. We conduct a thorough empirical evaluation of I-BAU by comparing it with six state-of-art backdoor defenses on seven backdoor attacks over two datasets and various attack settings, including the common setting where the attacker targets one class and an important but underexplored setting where multiple classes are targeted. I-BAU’s performance is comparable to and most often significantly better than the best baseline. Particularly, its performance is more robust to the variation on triggers, attack settings, poison ratio, and clean data size. Moreover, I-BAU requires less computation to take effect; particularly, it is more than 13X faster than the most efficient baseline in the single-target attack setting. It can still remain effective in the extreme case where the defender can only access 100 clean samples—a setting where all the baselines fail to produce acceptable results.
sections.heading: 2 RELATED WORK
sections.text: Backdoor Attacks. Backdoor attacks evolve through three stages. 1) Visble triggers using unrelated patterns (Gu et al., 2017; Chen et al., 2017), or optimized triggers (Liu et al., 2018b; Bagdasaryan & Shmatikov, 2021; Zhao et al., 2020; Garg et al., 2020) for higher attack efficacy. While this line’s attack methods achieve high attack success rates and clean accuracy, the triggers are visible and thus easily detected by human eyes. 2) Visually invisible triggers via solving bilevil optimizations regarding the lp norm (Li et al., 2020a), or adopting nature optical effects (Liu et al., 2020; Nguyen & Tran, 2021), and Clean label attacks via feature embeeding (Turner et al., 2019; Saha et al., 2020) for better stealthiness. For most work from this line, the triggers or the poisons can evade the detection from manual efforts. 3) Invisible triggers considering other latent spaces, e.g., the frequency domian (Zeng et al., 2021; Hammoud & Ghanem, 2021) or auto-encoder feature embedding (Li et al., 2021b), which improved the stealthiness by breaking the fundamental assumptions of a list of defenses. This paper incorporates successful attacks from these major groups and we show our method provides an effective, and generalizable defense. Backdoor Defenses. Backdoor defenses can be divided into four categories: 1) Poison detection via outlier detection regarding functionalities or artifacts (Gao et al., 2019; Chen et al., 2018; Tran et al., 2018; Koh & Liang, 2017; Chou et al., 2020; Zeng et al., 2021), which rely on the modeling of clean samples’ distribution. 2) Poisoned model identification identifies if a given model is backdoored or not (Xu et al., 2019; Wang et al., 2020). 3) Robust training via differential privacy (Du et al., 2019; Weber et al., 2020) or ensembled/decoupled pipeline (Levine & Feizi, 2020; Jia et al., 2020; 2021; Huang et al., 2022). This line of work tries to achieve general robustness to withstand outlier’s impact, but may suffer from low clean accuracy. 4) Backdoor removal via trigger synthesising (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019), or preprocessing & finetuning (Li et al., 2020b; Borgnia et al., 2020; Qiu et al., 2021). This line of work serves as the fundamental solution given a poisoned model, but there is still no satisfying solution to attaining robust results across different datasets and triggers. In this work, we propose a minimax formulation and a solver for backdoor removal. We attempt to include all cutting-edge methods under this category for comparison.
sections.heading: 3 PROBLEM FORMULATION
sections.text: 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 x, adding a backdoor pattern δ to x (i.e., x+ δ) will alter the trained classifier output to be a target class ỹ. The norm of δ 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 ỹ. 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 a test example when the trigger is absent. Note that in our attack model, we explicitly acknowledge the possibility that multiple trigger patterns and multiple target classes are present. We will refer to the model trained on the poisoned training set as a poisoned model.
  Defense goal. We consdier that the defender is given a poisoned classifier fθpoi and an extra set of clean data D = {(xi, yi)}ni=1 from D. With fθpoi and D, the defender aims to build a model fθ∗ immunne to backdoors, i.e., fθ∗(x+ δ) = fθ∗(x). Note that the size of available clean examples is assumed to be much smaller than the size necessary to retrain a high-accuracy model from scratch.
  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 a given input. This intuition naturally leads to the following minimax optimization formulation of backdoor removal:
  θ∗ = arg min θ max ‖δ‖≤Cδ
  H(δ, θ) := 1
  n n∑ i=1 L(fθ(xi + δ), yi), (1)
  where L is the loss function. Note that this formulation looks similar to adversarial training for evasion attacks (a.k.a. adversarial examples) (Madry et al., 2017). The main distinction is that in evasion attacks, the adversarial perturbation is specific to an individual data point, while in backdoor attacks, the same perturbation (i.e., the backdoor trigger) is expected to cause misclassifications for any examples upon being patched. Hence, in the formulation for backdoor attacks, the same trigger, δ, is applied to every clean sample xi, whereas, in the minimax formulation for evasion attacks, the perturbation is optimized independently for each sample (see Eq. (2.1), Madry et al. (2017)).
  The minimax formulation for backdoor removal has many advantages. 1), it gives us a unifying perspective that encompasses much prior work on backdoor removal. The formulation comprises an inner maximization problem and an outer minimization problem. Both of these problems have a natural interpretation in the security context. The inner maximization problem aims to find a trigger that causes a high loss for predicting the correct label. This aligns with the problem of a backdoor attack that misleads the model to predict a predefined incorrect target label. In our formulation, we choose to maximize the prediction loss for the correct label instead of using the exact backdoor attack objective of minimizing the prediction loss associated with the target label. We make this design choice because, in reality, the defender does not know the target labels selected by the attacker. The outer minimization problem is to find model parameters so that the “adversarial loss” given by the inner attack problem is minimized. Existing backdoor removal approaches based on trigger synthesis and unlearning the synthesized trigger (Wang et al., 2019; Chen et al., 2019; Guo et al., 2019) can be considered as a special instance of this minimax formulation, where they neglect the interdependence between the inner and outer optimization and solve them separately. 2), the formulation does not make any assumption on the backdoor trigger beyond the bounded norm constraint. By contrast, much of the existing work makes additional assumptions about backdoor triggers in order to be effective. For instance, synthesis-based approaches often assume that the classes coinciding with the target classes of the triggers account for only a tiny portion of the total, making those approaches ineffective in countering multiple target cases. 3), the formulation provides a quantitative measure of backdoor robustness. In particular, when the parameters θ 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.
sections.heading: 4 ALGORITHM
sections.text: A natural (but problematic) algorithm design. Given the empirical success of adversarial training for defending against evasion attacks (Li et al., 2022), one may wonder whether we can solve the minimax for the backdoor attack via adversarial training. Adversarial training keeps alternating between two steps until the loss converges: (1) solving the inner maximization for a fixed outer minimization variable; and (2) solving the outer minimization by taking a gradient of the loss evaluated at the maximum. Practically, adversarial training proceeds by first generating adversarial perturbations and then updating the model using the gradient calculated from the perturbed data. For backdoor attacks, the adversarial perturbation needs to fool the model universally on all inputs. Hence, a natural algorithm to solve the backdoor minimax problem is to tune the model with universal adversarial perturbations. Universal adversarial perturbations have been studied in the past, and there exists an off-the-shelf technique to create such perturbations (Moosavi-Dezfooli et al., 2017). However, we found that this simple algorithm is highly unstable. Figure 1 illustrates the change of the model accuracy and robustness (measured in terms of the attack success rate (ASR)) for 20 runs as adversarial training proceeds. It can be seen that the ASR varies significantly across different runs. Within a single run, while the ASR decays as a whole, the decrement is mostly erratic and slow.
  There are two issues with naive adversarial training with universal perturbations. First, the performance of the existing universal perturbation algorithm is unstable. At its core, it generates adversarial perturbations for each example and adds the perturbations together. The addition may not always lead to a perturbation that can fool all examples; instead, the addition operation may cancel the effect of individual perturbations. More importantly, the decoupling between solving the inner maximization and the outer minimization in adversarial training is often justified by Danskin’s Theorem (Danskin, 2012), which states that the gradient of the inner function involving the maximization term is simply given by the gradient of the function evaluated at this maximum. In other words, letting δ∗ = arg max||δ||≤Cδ H(δ, θ), we have ∇θ max||δ||≤Cδ H(δ, θ) = ∇θH(δ
  ∗, θ). However, in practice, due to stochastic gradient descent, it is impossible to solve the inner maximization optimally. Worse yet, the underperformance of the existing universal perturbation algorithm makes it even harder to approach the maximum. Moreover, Danskin’s Theorem only holds for convex loss functions. Due to the violation of maximum condition and convexity, it is unsuitable for utilizing Danskin’s Theorem, and hence, adversarial training is not justified.
  Algorithm 1: Implicit Backdoor Adversarial Unlearning (I-BAU) Input: θ1 (poisoned model); D (clean set accessible for backdoor unlearning); Output: θK (sanitized model) Parameters: Cδ (`2 norm bound); K,T (outer and inner iteration numbers); α, β > 0 (step sizes)
  1 for each iteration i ∈ (1,K − 1) do 2 δi ← 01×d; 3 for t ∈ (1, T ) do 4 Update δt+1i = δ t i + α∇1H(δti(θi), θi);
  5 δi = δi ×min ( 1, Cδ‖δi‖2 ) ; 6 Compute∇δ>i (Hessian products) via an iterative solver with reverse mode differentiation; 7 ∇ψ̃(θi) = ∇2H(δi, θi) +∇δ>i ∇1H(δi, θi); 8 Update θi+1 = θi − β∇ψ̃(θi); 9 return θK
  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 δ(θ) be an arbitrary suboptimal solution to max||δ||≤Cδ H(δ, θ). Let ψ(θ) := H(δ(θ), θ) be the objective function evaluated at the suboptimal point; if δ(θ) is a stationary point, we make an distinction by defining the corresponding function as ψ∗(θ). Denote ∇1H(δ, θ) and ∇2H(δ, θ) as the partial derivatives with respect to the first and second variable, respectively, and ∇21H(δ, θ) and ∇21,2H(δ, θ) 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
  ∇ψ(θ)︸ ︷︷ ︸ hypergrad. of θ = ∇2H(δ(θ), θ)︸ ︷︷ ︸ direct grad. of θ +
  response Jacobian︷ ︸︸ ︷ (∇δ(θ))> direct grad. of δ︷ ︸︸ ︷ ∇1H(δ(θ), θ)︸ ︷︷ ︸
  indirect grad. of θ
  . (2)
  The direct gradients are easy to compute. For instance, suppose H is the loss of a neural network, then ∇1H(δ(θ), θ) and ∇2H(δ(θ), θ) are the gradients with respect to the network input and the model parameters, respectively. However, the response Jacobian is intractable to obtain because we must compute the change rate of the suboptimal solution to the inner maximization problem with respect to θ. When δ(θ) satsifies the first-order stationarity condition, i.e., ∇1H(δ(θ), θ) = 0, and assuming that∇21H(δ(θ), θ) is invertible, the response Jacobian is given by
  ∇δ(θ) = − ( ∇21H(δ(θ), θ) )−1∇21,2H(δ(θ), θ), (3) which follows from the implicit function theorem. Note that∇δ(θ) plays a role in the Hessian in (2), in the sense that it adjusts each dimension of the gradient∇1H(δ(θ), θ) to the importance of that dimension. Hessian expresses the importance via curvature, whereas ∇δ(θ) measures the importance based on the sensitivity to the change of θ. 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 ∇δ(θ) with a suboptimal solution by (3). In practice, the approximation is addressed with an iterative solver of limited rounds (e.g., conjugated gradient algorithm (Rajeswaran et al., 2019) or fixed-point algorithm (Grazzi et al., 2020)) along with the reverse mode of automatic differentiation (Griewank & Walther, 2008).
  Finally, to solve (1), we plug in the approximate response Jacobian into (2). Then, we use∇ψ̃(θ) (referred 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 δ(θ) instead of its optimization path; hence, it can be implemented in a memory-efficient manner compared to the explicit way of solving bi-level optimizations (Grazzi et al., 2020). The overall algorithm, dubbed Implicit Backdoor Adversarial Unlearning, for `2-norm bounded attacks is presented in Algorithm 1. Generalizing the algorithm to other norms is 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 suboptimum solution and memory complexity analysis are provided in Appendix A.3.
sections.heading: 5 THEORETICAL ANALYSIS
sections.text: In this section, we analyze the convergence of the I-BAU. We also study the generalization properties of the minimax backdoor removal formulation. Assuming that by solving the minimax, we obtain a model such that all points in the clean setD are robust to triggers of a specific norm, we would like to reason about to what extent an unseen point from the underlying data distributionD is trigger-robust. Convergence Bound: Suppose that H(·, θ) is µH(θ)-strongly convex and LH(θ)-Lipschitz smooth, where µH(·) and LH(·) are continuously differentiable. Define α(δ) = 2LH(θ)+µH(θ) , and let δ(θ) be the unique fixed point of δ + α(θ)∇1H(δ, θ). Then, there exists LH,θ s.t. sup‖δ‖≤2Cδ ‖∇1H(δ, θ)‖ ≤ LH,θ (Grazzi et al., 2020). We make the following assumptions: • Lipschitz continuity of direct gradients: ∇1H(·, θ) and∇2H(·, θ) are Lipschitz continuous func-
  tions of θ (with Lipschitz constants η1,θ and η2,θ, repectively). • Lipschitz continuity and norm boundedness of second-order terms: ∇21H(·, θ) is ρ̂1,θ− Lipschitz
  continuous, and∇22,1H(·, θ) is ρ̂2,θ-Lipschitz continuous. Also, the cross derivative term is norm bounded by Lh,θ ≥ ∥∥∇221H(δ(θ), θ)∥∥. • Asymptotic convergence of δt(θ) to δ(θ): ‖δt(θ)− δ(θ)‖ ≤ ρθ(t) ‖δ(θ)‖, where ρθ(t) is such
  that ρθ(t) ≤ 1, and ρθ(t)→ 0 as t→ +∞. Theorem 1 Consider the approximate hypergradient∇ψ̃(θi) computed by Algorithm 1 (line 7). For every inner and outer iterate t, i ∈ N, we have:∥∥∥∇ψ̃(θi)−∇ψ(θi)∥∥∥ ≤ (c1(θi) + c2(θi)1− qtθi
  1− qθi
  ) ρθi(t) + c3(θi)q t θi , (4)
  where qθi := max {1− α(θi)µH(θi), α(θi)LH(θi)− 1}, c1(θi) := ( η2,θi + η1,θiLh,θiα(θi)
  1−qθi
  ) Cδ ,
  c2(θi) := LH,θiCδ (LH(θi)‖∇α(θi)‖+ ρ̂2,θiα(θi))+ ρ̂1,θiLH,θiLh,θiCδα(θi)
  2
  1−qθi , and finally c3(θi) :=
  LH,θiLh,θiα(θi)
  1−qθi .
  As the inner epoch number t increases, the estimated gradient becomes more accurate. Under the assumption that H(·, θ) is convex, the solution converges. We show the full proof in Appendix A.1. Generalization Bound for Linear Models: Consider a class of linear classifiers θ ∈ Θ where the weights are norm-bounded by Cθ. Define χ to be the upper bound of any input sample x ∈ D, i.e., ‖x‖2 ≤ χ. Let the empirical risk defined as R̂γ(θ) ≤ n−1 ∑ j 1 [ θ (xj + δ)yj ≤ γ + maxj 6=yj θ (xj + δ)j ] with a margin γ > 0.
  Theorem 2 For any linear model θ and ξ ∈ (0, 1), the following holds with a probability of at least 1− ξ over ((xi, yi))ni=1:
  Pr [ arg max
  j [θ(x+ δ)j ] 6= y
  ] ≤ R̂γ(θ) + 2Cθ
  (χ+ Cδ)√ n + 3
  √ ln(1/ξ)
  2n , (5)
  When the number of clean samples, n, gets larger, the generalizability of the adversarial unlearning on linear models becomes better. It is also interesting to compare the adversarial generalization bound for backdoor attacks with the bound for evasion attacks in (Yin et al., 2019), which has an additional √ d factor in the second term of the bound. Hence, for inputs of large dimensions, the adversarial training for backdoor attacks is expected to be more generalizable than that for evasion attacks. The detailed proof is shown in the Appendix A.2.1.
  Generalization Bound for Neural Networks: Consider a neural network with L fixed nonlinearities (σ1, . . . , σL) , where σi is %i-Lipschitz (e.g., coordinate-wise ReLU, max-pooling as discussed in (Bartlett et al., 2017)) and σi(0) = 0. Let L weight matrices be denoted by (A1, . . . , AL) with dimensions (d0, . . . , dL), respectively, where d0 = d is the number of input dimensions, dL = C is the number of classes, and W = max(d0, . . . , dL) is the highest dimension layer. Assume that the weight matrices satisfy ‖Ai‖2,1 ≤ ai, ‖A1‖2,1 ≤ a0 , and Ai ∈ Rdi×mi . Let a1 = a0 ( 1 +m1n 1/2Cδ ) . The whole network’s output regarding a backdoored sample is denoted as: σL (ALσL−1 (AL−1 . . . σ1 (A1(x+ δ)) . . .)). Let ‖Ai‖σ be bounded by the spectral norms si.
  Theorem 3 For any neural network model θ and ξ ∈ (0, 1), the following holds with a probability of at least 1− ξ over ((xi, yi))ni=1:
  Pr [ arg max
  j [θ(x+ δ)j ] 6= y
  ] ≤
  R̂γ(θ) + 8 n +
  48 ln(n)(‖X‖p+ √ n) √ ln(2W (W+n))
  γn
  (∏L i=1 si%i )(∑L i=1 a 2/3 i
  s 2/3 i
  )3/2 +3 √
  ln(1/ξ) 2n .
  (6)
  When the number of clean samples, n, gets larger, the generalizability of the unlearning on neural networks becomes better. Compared with the generalization bound for regular training in (Bartlett et al., 2017), our bound has an additional n term in √ ln(2W (W + n)) and (‖X‖p + √ n), which indicates harder generalizability than regular learning problem. However, empirically, we find our solution, I-BAU, is still of excellent generalizability even if only 100 clean samples are accessible. Our proof is enabled by recognizing that the backdoor perturbation, δ, 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 3 against W and n in Appendix A.2.3.
sections.heading: 6 EVALUATION
sections.text: 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.
sections.heading: 6.1 EFFICACY
sections.text: We evaluate I-BAU’s efficacy against three attack settings: 1) One-trigger-one-target attack, in which the attacker uses only one trigger, and there is only one target label. This setting is most commonly considered in existing defense works. 2) One-trigger-all-to-all attack, in which the attacker uses only one trigger but aims to mislead predictions from i to i+1, where i is the ground truth label (Gu et al., 2017). 3) Multi-trigger-multi-target attack, where the attacker uses multiple distinct triggers, each targeting a different label. We will refer to the first two settings as “one-trigger setting” and the last setting as “multi-trigger setting.” For each setting, we study seven different backdoor triggers in the main text, namely, BadNets white square trigger (BadNets) (Gu et al., 2017), Hello Kitty blending trigger (Blend) (Chen et al., 2017), l0 norm constraint invisible trigger (l0 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 non-additive backdoor attacks. We have included case studies on 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, we train on the poisoned dataset for 50 epochs.
  We compare I-BAU with six state-of-art defenses: Neural Cleanse (NC) (Wang et al., 2019), Deepinspect (DI) (Chen et al., 2019), TABOR (Guo et al., 2019), Fine-pruning (FP) (Liu et al., 2018a),
  Neural Attention Distillation (NAD) (Li et al., 2020b), and Differential Privacy training (DP) (Du et al., 2019). Note that DP requires access to the poisoned data; hence, its attack model is different from the attack model of the other baselines and our method. In the following tables, we use [ ASR ] to mark the results that fail to reduce the attack success rate (ASR) below 20%; we use [ ACC ] to mark the results where the accuracy (ACC) on clean data drops by more than 10%; we use [ ACC or ASR ] to mark the best result among the six baselines; finally, we use [ ACC or ASR ] to mark the results from I-BAU that is comparable to or significantly better than the best result among the baselines. We consider I-BAU’s result as comparable if 1) the ACC gap is less than 1%, 2) the ASR gap is less than 4%, or the ASR of I-BAU is close to the label percental (i.e., the probability of random guessing for outputting the target label, 10% for the CIFAR-10, 2.3 % for the GTSRB). One-trigger Setting: Table 1 presents the defense results on the CIFAR-10 dataset. CIFAR-10 contains 60,000 samples. We use 50,000 samples as training data, among which 10,000 samples are poisoned. We used 5,000 separate samples as the clean set accessible to the defender for conducting each defense (e.g., via unlearning, finetuning, trigger synthesis) except DP. The remaining 5,000 samples are used to assess the defense result. The left column depicts the attack cases. The first seven cases each contain only one target label. The all-to-all case represents the case in which we use the BadNets trigger to carry out the one-trigger-all-to-all attack. As shown in the table, all singletarget attacks are capable of achieving an ASR close to 100% with no defenses. It is empirically observed that the ASR of the all-to-all attack is upper-bounded by the ACC. Intuitively, the model needs to classify the clean samples correctly to classify the corresponding backdoored samples with triggers to the next class. Thus, we tune the model to produce an ASR that is close to the ACC.
  Model performance on CIFAR-10 is particularly sensitive to finetuning and unlearning, which will result in a decrease in the ACC in general. Thus, for a fair comparison, we show the I-BAU results in Table 1 when the ACC falls to the same level as the most effective baseline. For instance, for BadNets attacks, we present the ASR result of I-BAU when the ACC of I-BAU decreases to a value similar to the ACC of TABOR, which is the best defense baseline against BadNets.
  As shown in Table 1, the performance of the baselines exhibits large variance across different triggers. Specifically, each baseline underperforms in at least three attack cases (marked by ([ ASR ] or [ ACC ])) The defenses based on trigger synthesis (including NC, DI, and TABOR) failed to confront the all-to-all attack case, where all the labels were targeted. This is because this setting violates their assumption that target classes only account for the minority of training data. Particularly, TABOR fails to detect any backdoor triggers in this case). For DP, we fine-tune a noise multiplier effective to mitigate all attacks, yet also leads to bad ACC. On the other hand, I-BAU robustly mitigates all triggers without significantly affecting the ACC. Compared to the best result among the state-of-art baselines ([ ACC or ASR ]), I-BAU’s is comparable to or much better ([ ACC or ASR ]) under most of the settings. The only setting where I-BAU underperforms the best baseline is Smooth triggers. FP is the only effective baseline in this setting. But interestingly, this setting is also the only setting where FP is effective; in other words, its performance is highly dependent on the underlying trigger.
  Table 2 shows the evaluation on the GTSRB dataset, which contains 39,209 training data and 12,630 test data of 43 different classes. The experimental setting is the same as the one on CIFAR, except for the data split, which is discussed in the Appendix A.4.1. We find that model performance on GTSRB is not sensitive to the tuning procedure. As 5,000 clean samples are available to the defender, the ACC of the model increases after incorporating the defense. NAD’s performance highly depends on the pre-designed preprocessing procedure adopted during fine-tuning. While it produces the best defense results for some settings on CIFAR-10, it suffers from a large degradation of ACC on GTSRB. Once again, I-BAU is the only defense method that remains effective for all attack settings.
  Multi-trigger Setting: Table 3 shows the results on CIFAR and GTSRB in a 7-trigger-7-target setting, in which each trigger targets a different label. We adopt the same poison ratio for each (20%) and then combine the seven distinct poisoned datasets to obtain the final datasets (size 350,000 for CIFAR-10, and 274,463 for the GTSRB). We show the average ASR and the specific ASR.
  On CIFAR-10, since the target classes are no longer the minority (i.e., 7/10 labels are targeted), the baselines based on trigger synthesis, which make the minority assumption, are ineffective. Particularly, NC fails to detect any triggers in this setting. NAD is the only baseline able to evaluate well on CIFAR-10, and our methods achieve comparable performance. However, similar to the one-trigger setting, NAD’s performance requires the customization of preprocessing to different datasets. The default preprocessing cannot maintain the same performance on GTSRB; e.g., the random flipping—a beneficial preprocessing step for CIFAR—completely alters the semantics of images in GTSRB. On the other hand, I-BAU effectively reduces ASR while maintaining the ACC for both datasets with no changes needed. Moreover, in the Appendix, we visualize the distribution of poisoned and clean examples in the feature space before and after applying I-BAU, which shows that I-BAU can place the poisoned examples back in the cluster with correct labels.
sections.heading: 6.2 STABILITY
sections.text: In Section 4, we mentioned that the naive heuristic based on adversarial learning with existing universal perturbation suffers from erratic performance. Here, we aim to evaluate whether I-BAU can overcome this problem. We adopt the same setting for the two on the CIFAR-10 using BadNets and observe the change in ACC and ASR over different iterations for each run. As shown in Figure 1, the ASR decreases very quickly; indeed, the attack can be mitigated by just one single iteration of outer minimization. Also, within every single run, the ASR decreases more smoothly compared to the naive heuristic. Notably, I-BAU attains a slightly higher ACC than the naive heuristic.
sections.heading: 6.3 SENSITIVITY
sections.text: We evaluate the sensitivity of each defense to the poison ratio and the size of clean samples. The experiments were performed on Trojan WM on CIFAR-10 to exemplify the results. Table 4 shows the sensitivity to the poison ratio. Observe that as the poison ratio drops, TABOR becomes ineffective at synthesizing triggers and ultimately fails to remove the triggers; NC, however, becomes the most effective baseline. While DP’s ASR is significantly worse than the effective baselines, its performance gets slightly better as the poison ratio drops. DP attempts to restrict the impact of each training data point on the learning outcome via noising the gradient. As a side effect, it hinders learning from good data, thereby leading to poor ACC in general. Compared to the baselines, I-BAU exhibits the least sensitivity to the poison ratio, maintaining good ACC and ASR across different ratios.
  Table 5 shows sensitivity to available clean data’s size. As DP is independent from the clean set (which trains a general robust model against all perturbations from scratch), we drop it from the comparison. We see that as the number of clean samples drops, the performance of all defenses declines. I-BAU is least sensitive to the size of clean samples; even in extreme case with only 100 clean samples available, I-BAU still maintains an acceptable performance of removing backdoors.
  6.4 EFFICIENCY
  Finally, we compare the efficiency of defenses. We use the onetrigger-one-target attack setting to exemplify the result. Table 6 shows the average runtime for each defense to take effect (i.e., mitigating the ASR to < 20%). As I-BAU can mitigate the attacks in one iteration, it only takes 6.82 s on average on CIFAR-10 and 7.84 s on GTSRB. Note that NC and TABOR need to go through each label independently for trigger synthesis; thus, the total runtime is proportional to the number of labels. Especially, it takes much more time for the two to take effect on GTSRB than on CIFAR-10. In difficult attack cases, such as all-to-all attacks and
  multi-trigger-multi-target attacks, I-BAU requires more rounds to be operative but remains the only effective one across all settings with high efficiency and efficacy. The Appendix shows the performance of I-BAU over different rounds under multi-target attack cases. Theoretical analysis and comparison of the time complexity of I-BAU are presented in Appendix A.3.3.
sections.heading: 7 CONCLUSION
sections.text: In this work, we proposed a minimax formulation of the backdoor removal problem. This formulation encompassed the objective of the existing unlearning work without making assumptions about attack strategies or trigger patterns. To solve the proposed minimax, we proposed I-BAU using implicit hypergradients. A theoretical analysis verified the convergence and generalizability of the proposed I-BAU or minimax formulation. A comprehensive empirical study established that I-BAU is the only generalizable defense across all evaluated eleven backdoor attacks. The defense results are comparable to or exceed the best results obtained by combining six existing state-of-the-art techniques. Meanwhile, I-BAU is less sensitive to poison rate and is effective in extreme cases where the defender has access to only 100 clean samples. Finally, under the standard one-trigger-one-target circumstances, I-BAU can achieve an effective defense in an average of 7.35 s.
sections.heading: A APPENDIX
sections.heading: A.1 CONVERGENCE BOUND
sections.text: Consider the minimax formulation of backdoor unlearning defined in (1). To simply the notation, we will use θ instead of θi, unless otherwise specified. We start by defining Φ(δ, θ) = δ + α(θ)∇1H(δ, θ), where H (sum of cross-entropies) is twice continuously differentiable w.r.t. both δ and θ. Recall that H(·, θ) is µH(θ)-strongly convex and LH(θ)-Lipschitz smooth, where µH(·) and LH(·) are continuously differentiable. By setting the step size α(θ) = 2LH(θ)+µH(θ) , it can be shown that Φ(·, θ) is a contraction for some coefficient qθ := max {1− α(θ)µH(θ), α(θ)LH(θ)− 1}. The optimal choice of the step-size leads to qθ = κ(θ)−1 κ(θ)+1 , where κ(θ) = LH(θ) µH(θ)
  . Note that, for every i ∈ (1,K), θ ∈ Θ, µH(θ)I 4 ∇21H (δi(θ), θ) 4 LH(θ)I. (7) Hence, the condition number of ∇21H (δi(θ), θ) is smaller than κ(θ) (Grazzi et al., 2020). Let ∂1Φ(δ, θ) and ∂2Φ(δ, θ) denote the partial Jacobians of Φ at (δ, θ) w.r.t. the first and the second variables, respectively. We can write the derivatives of Φ as:
  ∂2Φ(δ, θ) = −∇1H(δ, θ)∇α(θ)> − α(θ)∇221H(δ, θ), ∂1Φ(δ, θ) = I − α(θ)∇21H(δ, θ).
  (8)
  When evaluated at (δ(θ), θ), the partial Jacobian w.r.t. the second variable, ∂2Φ(δ(θ), θ), can be simplified as: ∂2Φ(δ, θ) = −α(θ)∇221H(δ(θ), θ). (9) Thus, ‖∂2Φ(δ(θ), θ)‖ = α(θ)‖∇221H(δ(θ), θ)‖. Following the notations from (Grazzi et al., 2020), we create the bound of the partial Jacobian of Φ to be LΦ,θ ≥ ‖∂2Φ(δ(θ), θ)‖. By our assumption, the bound for the cross derivative term δ is Lh,θ ≥
  ∥∥∇221H(δ(θ), θ)∥∥. Hence, we can choose: LΦ,θ = α(θ)Lh,θ. (10)
  Let ∆∂1Φ := ‖∂1Φ (δ1, θ)− ∂1Φ (δ2, θ)‖ and ∆∂2Φ := ‖∂2Φ (δ1, θ)− ∂2Φ (δ2, θ)‖. By assumption on the Lipschitz continuity and norm boundedness of second-order terms, we have :
  ∆∂1Φ = ∥∥α(θ) (∇21H (δ1, θ)−∇21H (δ2, θ))∥∥ ≤ α(θ)ρ̂1,θ ‖δ1 − δ2‖ , (11)
  and: ∆∂2Φ =‖ (∇1H (δ1, θ)−∇1H (δ2, θ))∇α(θ)> + α(θ) ( ∇221H (δ1, θ)−∇221H (δ2, θ) ) ‖
  ≤ (LH(θ)‖∇α(θ)‖+ α(θ)ρ̂2,θ) ‖δ1 − δ2‖ . (12)
  Thus, ∂1Φ(·, θ) is Lipschitz continuous with constant v1,θ := α(θ)ρ̂1,θ, (13)
  and ∂2Φ(·, θ) is Lipschitz continuous with constant v2,θ := LH(θ)‖∇α(θ)‖+ α(θ)ρ̂2,θ. (14)
  Recall the result from (Grazzi et al., 2020):
  Lemma 1 The approximate hypergradient has an error bounded by∥∥∇ψ̄(θ)−∇ψ∗(θ)∥∥ ≤ (c1(θ) + c2(θ)1− qtθ 1− qθ ) ρθ(t) + c3(θ)q t θ, (15)
  where c1(θ) = ( η2,θ +
  η1,θLΦ,θ 1−qθ
  ) Cδ,
  c2(θ) = ( ν2,θ +
  ν1,θLΦ,θ 1−qθ
  ) LH,θCδ,
  c3(θ) = LH,θLΦ,θ
  1−qθ .
  (16)
  The proof of Theorem 1 uses the inequality from Lemma 1 with the constants specified in (10), (13), and (14).
sections.heading: A.2 GENERALIZATION BOUNDS
sections.text: Following the notations from (Bartlett et al., 2017), we define a general margin operatorM(v, y) := vy −maxj 6=y vj , and the ramp loss `γ with a given margin γ:
  `γ(r) := { 0 r < −γ 1 + r/γ r ∈ [−γ, 0] 1 r > 0 . (17)
  According to (Yin et al., 2019), the population risk against a perturbation δ is given by:
  Rγ(θ) := E (`γ(−M(θ(x+ δ), y))) , (18)
  and the empirical risk is given by:
  R̂γ(θ) := n −1 ∑ j `γ (−M (θ (xj + δ) , yj)) . (19)
  Note that Rγ(θ) and R̂γ(θ) are the upper bounds of the fraction of errors on the source distribution and the dataset used for unlearning, Dsan, respectively. Finally, given a set of real-valued functions H, recall the Rademacher complexity as:
  < ( H|S ) := n−1Eς sup
  h∈H n∑ j=1 ςjh (xj , yj) , (20)
  where ςj ∈ {±1} is the Rademacher random variable. The following bound of the adversarial unlearning can be derived using standard tools in Rademacher complexity.
  Lemma 2 Given unlearned models Θ with θ ∈ Θ and some margin γ > 0, define:
  Θγ := {(x, y) 7→ `γ(−M(θ(x+ δ), y)) : θ ∈ Θ} . (21)
  The following holds with the probability of at least 1−ξ over the clean dataset,Dsan (see Algorithm 1) for every θ ∈ Θ:
  Pr [ arg max
  j [θ(x+ δ)j ] 6= y
  ] ≤ R̂γ(θ) + 2< ( (Θγ)|Dsan ) + 3 √ ln(1/ξ)
  2n . (22)
  To instantiate this bound, we only need to control the Rademacher complexity, < ( (Θγ)|Dsan ) , for linear models and neural networks.
sections.heading: A.2.1 PROOF FOR LINEAR MODELS
sections.text: Define the set of linear, poisoned models under perturbation δ:
  Θlinγ := {(x, y) 7→ 〈θ, x+ δ〉 : θ ∈ Θ} , (23)
  where θ can be regarded as a weight matrix ‖θ‖ bounded by Cθ. Recall that the perturbation norm ‖δ‖ is bounded by Cδ , and the input l2 norm ‖x‖2 is bounded by χ. We can proceed to evaluate the
  upper bound of the Rademacher complexity:
  < ( (Θγ)|Dsan ) = Eς  sup ‖θ‖≤Cθ 1 n n∑ j=1 ςj〈θ, x+ δ〉  ≤ Eς  sup ‖θ‖≤Cθ 1 n ∥∥∥∥∥∥ n∑ j=1 ςj(xj + δ) ∥∥∥∥∥∥ ‖θ‖  (Cauchy-Schwarz inequality)
  ≤ CθEς  1 n ∥∥∥∥∥∥ n∑ j=1 ςj(xj + δ) ∥∥∥∥∥∥  (given that ‖θ‖ ≤ Cθ)
  = CθEς  1 n ∥∥∥∥∥∥ n∑ j=1 ςjxj + δ n∑ j=1 ςj ∥∥∥∥∥∥ 
  ≤ CθEς  1 n ∥∥∥∥∥∥ n∑ j=1 ςjxj ∥∥∥∥∥∥+ 1n ∥∥∥∥∥∥δ n∑ j=1 ςj ∥∥∥∥∥∥  (Triangle inequality)
  = Cθ Eς 1n ∥∥∥∥∥∥ n∑ j=1 ςjxj ∥∥∥∥∥∥︸ ︷︷ ︸ A +Eς 1 n ∥∥∥∥∥∥δ n∑ j=1 ςj ∥∥∥∥∥∥︸ ︷︷ ︸ B  .
  (24)
  In particular, A can be bounded by:
  A = Eς 1
  n √√√√ n∑ j=1 n∑ k=1 ςjςk〈xj , xk〉
  ≤ 1 n √√√√Eς n∑ j,k ςjςk〈xj , xk〉 (Jensen’s inequality)
  ≤ 1 n √√√√ n∑ j=1 ‖xi‖2
  ≤ χ√ n .
  (25)
  Similarly, B can be bounded by:
  B ≤ Eς sup ‖δ‖≤Cδ
  1
  n ∥∥∥∥∥∥δ n∑ j=1 ςj ∥∥∥∥∥∥ ≤ Cδ
  n Eς ∥∥∥∥∥∥ n∑ j=1 ςj ∥∥∥∥∥∥ (given that ‖δ‖ ≤ Cδ) ≤ Cδ
  n √√√√Eς n∑ j,k ςjςk (Jensen’s inequality)
  = Cδ√ n .
  (26)
  Thus, we can bound the Rademacher complexity as following: < ( (Θγ)|Dsan ) ≤ Cθ(χ+ Cδ)√
  n . (27)
  Substituting (27) to the (22) completes the proof of Theorem 2.
sections.heading: A.2.2 PROOF FOR NEURAL NETWORKS
sections.text: 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, < ( (Θγ)|Dsan ) . Let N (U, , ‖ · ‖) denotes the least cardinality of any subset V ⊆ U that covers U at a scale with norm ‖·‖, i.e., supA∈U minB∈V ‖A− B‖ ≤ . Recall the Dudley entropy integral below.
  Lemma 3 Assume that the input values are norm bounded by 1,
  < ( (Θγ)|Dsan ) ≤ inf α>0 ( 4α√ n + 12 n ∫ √n α √ logN ( (Θγ)|Dsan , , ‖ · ‖2 ) d ) . (28)
  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 ( (Θγ)|Dsan , , ‖ · ‖2 ) . The full problem can be divided into four steps: (I) finding a matrixcovering bound for the affine transformation of the input layer of poisoned models, conducted in this section; (II) finding a matrix-covering bound for the affine transformation of the following layers after the first layer, provided in (Bartlett et al., 2017); (III) obtaining a covering number bound for entire networks using induction on layers; (IV) accomplishing the complete generalization bound for neural networks by applying the covering number to (22) and (28).
  Step (I): Input Layer Matrix Covering. The covering number of the input layer considers the matrix product, Ẑ = (X + ∆)A1, where A1 ∈ Rd×m is the weight matrix of the input layer, X ∈ Rn×d is the input data, and ∆ = [δ, δ, . . . , δ]︸ ︷︷ ︸
  n
  > is the UNO perturbation vector repeated n
  times to get the same shape as X . Note that Ẑ can be rewritten as:
  Ẑ = (X + ∆)A1 = [ X In ] [
  A1 ∆A1 ] = X̂Â1,
  (29)
  where In is the n× n identity matrix, X̂ is an n× (d+ n) matrix, and Â1 is a (d+ n)×m matrix. Now, the goal of step (I) is to find the covering number for the matrix product, X̂Â1.
  Given X ∈ Rn×d, we can obtain the normalized matrix Y ∈ Rn×d by rescaling the columns of X to have unit p-norm: Y:,j := X:,j/ ‖X:,j‖p. Let N0 := 2(n+ d)m, and define{
  V̂1, . . . , V̂N0 } := { g [ Y In ] eie>j : g ∈ {−1,+1}, i ∈ {1, . . . , d+ n}, j ∈ {1, . . . ,m} } .
  (30) For p ≤ 2, the results from (Bartlett et al., 2017) implies:
  max i ∥∥∥V̂i∥∥∥ 2 ≤ max i∈{1...N0} ‖[ Y In ] ei‖2 = maxi ∥∥∥X̂ei∥∥∥ 2∥∥∥X̂ei∥∥∥ p ≤ 1. (31)
  Define α0 ∈ R(d+n)×m to be a “rescaling matrix”:
  α0 =  ‖X:,1‖p . . . ‖X:,1‖p ‖X:,2‖p . . . ‖X:,2‖p ... . . . ... ‖X:,d‖p . . . ‖X:,d‖p 1 . . . 1 ... . . . ...
  1 . . . 1
   , (32)
  where the purpose of α0 is to annul the rescaling of X̂ introduced by Ŷ = [ Y In ], i.e., X̂Â1 = Ŷ (α0 Â1), and denotes the element-wise product. Let B̂ := α0 Â1. Then, we have:
  (X + ∆)A1 = X̂Â1
  = Ŷ B̂
  = Ŷ n+d∑ i=1 m∑ j=1 B̂ijeiej > = Ŷ ‖B̂‖1 n+d∑ i=1 m∑ j=1 B̂ij ‖B̂‖1 eiej > = ‖B̂‖1 n+d∑ i=1 m∑ j=1 B̂ij ‖B̂‖1 [ Y In ] eiej>
  ∈ ‖B̂‖1 · conv ({ V̂1, . . . , V̂N0 }) ,
  (33)
  where conv ({ V̂1, . . . , V̂N0 }) is the convex hull of { V̂1, . . . , V̂N0 } . Given conjugate exponents
  (p, q) and (r, s) with p ≤ 2, by the conjugacy of ‖·‖p,r and ‖·‖q,s:
  ‖B̂‖1 ≤ 〈α0, |Â1|〉 ≤ ‖α0‖p,r‖Â1‖q,s. (34)
  Defining C as the desired cover of the first layer X̂Â1:
  C := { ‖B̂‖1 k N0∑ i=1 kiVi : ki ≥ 0, N0∑ i=1 ki = k } = ‖B̂‖1k k∑ j=1 V̂ij : (i1, . . . , ik) ∈ [N0]k  , (35)
  where, k := ⌈ a0 2(1+mn 1 2Cδ) 2(‖X‖p+n 1 2 )2m 2 r
  12
  ⌉ . By construction, |C| ≤ [N0]k. Now, we prove that
  C is the desired cover set. The technique is generalized from (Bartlett et al., 2017) to backdoor unlearning.
  Consider the case of ‖A1‖2,1, i.e., (q, s) = (2, 1), and let ‖A1‖2,1 ≤ a0, then we get: ‖α0‖p,r = ∥∥∥(‖α:,1‖p , . . . , ‖α:,m‖p)∥∥∥
  r
  = ∥∥∥∥(∥∥∥(‖X:,1‖p , . . . , ‖Xi,d‖p , 1, . . . , 1)∥∥∥ p , . . . , ∥∥∥(‖X:,1‖p , . . . , ‖X:,d‖p , 1, . . . , 1)∥∥∥ p )∥∥∥∥ r
  =m1/r ∥∥∥∥∥ ( ‖X:,1‖p , . . . , ‖X:,d‖p , n︷ ︸︸ ︷ 1, . . . , 1 )∥∥∥∥∥ p
  =m1/r  d∑ j=1 ‖X:,j‖pp + n 1/p
  ≤m1/r ( ‖X‖p + n1/p ) .
  (36) Subsequently, the bound of ∥∥∥Â1∥∥∥ 2,1
  can be derived from:∥∥∥Â1∥∥∥ 2,1 = ∥∥∥∥[ A1∆A1 ]∥∥∥∥
  2,1
  = ∥∥∥∥(∥∥∥∥[ A:1∆A:1 ]∥∥∥∥
  2
  , . . . , ∥∥∥∥[ A:m∆A:m ]∥∥∥∥
  2 )∥∥∥∥ 1
  = ∥∥∥∥(‖A:1‖22 + ‖∆A:1‖22)1/2 , . . . ,(‖A:m‖22 + ‖∆A:m‖22)1/2∥∥∥∥ 1 ,
  (37)
  where we have:
  ‖∆A:i‖22 = ∥∥∥∥∥∥∥  δ > ... δ> A:i ∥∥∥∥∥∥∥ 2
  2
  = ∥∥∥∥∥∥∥  δ >A:i ...
  δ>A:i
   ∥∥∥∥∥∥∥ 2
  2 = ( δ>A:i )2 + . . .+ ( δ>A:i )2 = n ( δ>A:i )2 .
  (38)
  Therefore, substituting (38) to (37) gives us the bound:∥∥∥Â1∥∥∥ 2,1 = ∥∥∥∥(‖A:1‖22 + n (δ>A:1)2)1/2 , . . . ,(‖A:m‖22 + n (δ>A:m)2)1/2∥∥∥∥ 1
  ≤ ∥∥∥‖A:1‖2 + n1/2 ∥∥δ>A:1∥∥ , . . . , ‖A:m‖2 + n1/2 ∥∥δ>A:m∥∥∥∥∥
  1 = ‖A:1‖2 + n 1/2 ∥∥δ>A:1∥∥+ . . .+ ‖A:m‖2 + n1/2 ∥∥δ>A:m∥∥
  = ‖A1‖2,1 + n 1/2 m∑ j=1 ∥∥δ>A:j∥∥ ≤ ‖A1‖2,1 + n
  1/2 m∑ j=1 (‖δ‖2 · ‖A:j‖2)
  = ‖A1‖2,1 ( 1 +mn1/2‖δ‖2 )
  ≤ a0 ( 1 +mn1/2Cδ ) .
  (39)
  Let a1 = a0 ( 1 +mn1/2Cδ ) . Given the case of ‖A1‖2,1, we can obtain the bound for ‖B̂‖1:
  ‖B̂‖1 ≤ ‖α0‖p,r‖Â1‖2,1 ≤ m1/r ( ‖X‖p + n1/p ) a1. (40)
  Thus, combining (31) and following the Maurey lemma (Pisier (1981), Zhang (2002), Lemma 1), we have: ∥∥∥∥∥(X + ∆)A1 − ‖B̂‖1k N0∑ i=1 kiV̂i ∥∥∥∥∥ 2
  2
  ≤ ‖B̂‖ 2 1
  k max i=1...N0 ∥∥∥V̂i∥∥∥2 2
  ≤ a1 2(‖X‖p + n 1 2 )2m 2 r
  k
  ≤ 12,
  (41)
  which shows that the desired cover element is in C.
  Theorem 4 In the case of the input layer of a poisoned model, θ, consider ∆ as the UNO perturbation matrix with n rows of δ, and A1 ∈ Rd×m to be the weight metrix of the first layer. The covering resolution 1 is given. Defining a1 := a0 ( 1 +mn1/2Cδ ) , where a0 is the bound of ‖A1‖2,1, for any input X ∈ Rn×d, the convering number is bounded as follows:
  lnN ({ (X + ∆)A1 : A1 ∈ Rd×m } , 1, ‖ · ‖2 ) ≤
  ⌈ a1 2(‖X‖p + n1/2) 2 m2/r
  12
  ⌉ ln(2(d+ n)m).
  (42)
  Step (II): Other Layer’s Matrix Covering. Let’s define Z ∈ Rni×di as the input of a specific layer of the neural network, and Ai ∈ Rdi×mi as the weight matrix of that layer. Given conjugate exponents (p, q) and (r, s) with p ≤ 2, let‖Ai‖q,s ≤ ai . Lastly, the covering resolution of each
  layer, i, is given. Since no perturbation is considered in the following layers, we can directly adopt the covering studied in (Bartlett et al., 2017) as follows:
  lnN ({ ZAi : Ai ∈ Rdi×mi , ‖Ai‖q,s ≤ ai } , i, ‖ · ‖2 ) ≤
  ⌈ ai 2‖Z‖p2mi2/r
  i2
  ⌉ ln(2dimi). (43)
  Step (III): The Whole Network Covering Bound. Recall that the whole neural network is structured as follows: Fθ(x) := σL (ALσL−1 (AL−1 . . . σ1 (A1x) . . .)), where σi is %i-Lipschitz.
  Define two sequences of vector spaces V1, . . . ,VL and W2, . . . ,WL+1, where Vi has a norm | · |i and Wi has a norm ||| · |||i. The linear operators, Ai : Vi → Wi+1, are associated with some operator norm |Ai|i→i+1 ≤ si, i.e., |Ai|i→i+1 := ‖Ai‖σ ≤ sup|Z|i≤1 |||AiZ|||i+1 = si. Then, letting τ := ∑ j≤L j%j ∏L l=j+1 %lsl, with given convering resolutions, ( 1, . . . , L), the neural net images,HX := {Fθ(X + ∆)}, have the covering number bound (Bartlett et al., 2017):
  N (HX , τ, | · |L+1) ≤ L∏ i=1 sup (A1,...,Ai−1)
  ∀j<i
  N ({ AiF(A1,...,Ai−1)(X + ∆) } , i, ||| · |||i+1 ) . (44)
  Step (IV): Proof of Theorem 3. The key technique in the remainder of this proof is
  • 1) to substitute covering number estimates from (42) and (43) into (44) but • 2) centering the covers at 0 (meaning the cover at layer i ∈ (2, L) satisfies ‖Ai‖2,1 ≤ ai,
  ‖A1‖2,1 ≤ a0, and ‖Â1‖2,1 = ∥∥∥∥[ A1∆A1 ]∥∥∥∥ 2,1 ≤ a1), and
  • 3) collecting (x1, . . . , xn) as rows of matrix X ∈ Rn×d. To start, the covering number estimate of the whole network from (44) when combined with (42) and (43) (specifically with p = 2, s = 1, and W = max(d0, . . . , dL)) results in:
  lnN (HX , , ‖ · ‖2) ≤ ∑L i=1 sup (Â1,A2,...,Ai−1)
  ∀j<i lnN
  ({ AiF(Â1,A2...,Ai−1) ([ X>
  In
  ])} , i, ‖ · ‖2 ) (∗) = supA1 lnN ({ Â1 ([ X>
  In
  ])>} , 1, ‖ · ‖2 )
  + ∑L i=2 sup (A2,...,Ai−1)
  ∀j<i lnN
  ({ AiF(Â1,...,Ai−1) ([ X>
  In
  ]>)} , i, ‖ · ‖2 )
  ≤ supÂ1
  a21 ∥∥∥∥∥∥Â1 ([ X> In ])>∥∥∥∥∥∥ 2
  2
  21 ln (2W (W + n))
  + ∑L i=2 sup (A2,...,Ai−1)
  ∀j<i
  a2i ∥∥∥∥∥∥F(Â1,A2,...,Ai−1) ([ X> In ])>∥∥∥∥∥∥ 2
  2 2i ln ( 2W 2 ) ,
  (45)
  where (∗) equality holds since 1) l2 coverings of a matrix and its transpose are the same, and 2) the
  cover can be translated by F(Â1,A2,...,Ai−1)
  ([ X>
  In
  ])> A>i without changing its cardinality. We
  can further simplify (45), by evaluating the following norm for any Ai ∈ (A2, . . . , AL−1):∥∥∥∥∥F(Â1,A2,...,Ai−1) ([ X> In ])>∥∥∥∥∥ 2 = ∥∥∥∥σi−1(Ai−1F(Â1,A2,...,Ai−1)([ X>In ]))∥∥∥∥ 2
  ≤ %i−1 ∥∥∥∥Ai−1F(Â1,A2,...,Ai−1)([ X>In ])∥∥∥∥ 2
  ≤ %i−1si−1 ∥∥∥∥F(Â1,A2,...,Ai−1)([ X>In ])∥∥∥∥ 2 ,
  (46)
  which by induction gives
  max j ∥∥∥∥∥F(Â1,A2,...,Ai−1) ([ X> In ])> ej ∥∥∥∥∥ 2 ≤ (‖X‖p + n1/2) i−1∏ j=1 %jsj . (47)
  Combining (46) and (47), the cover is bounded by:
  lnN (HX , , ‖ · ‖2) ≤ a1 2(‖X‖p+ √ n)2
  12 ln(2W (W + n)) + ∑L i=2 a2i (‖X‖p+ √ n)2%21s 2 1 ∏ 2<j<i % 2 js 2 j i2 ln(2W 2)
  ≤ ∑L i=1 a2i (‖X‖p+ √ n)2 ∏ j<i % 2 js 2 j i2 ln(2W (W + n)).
  (48)
  Let
  i := αi %i ∏ j>i %jsj , where αi := 1 ᾱ ( ai si )2/3 , ᾱ := L∑ j=1 ( aj sj )2/3 , (49)
  then,
  lnN (HX , , ‖ · ‖2) ≤ (‖X‖p+
  √ n)2 ln(2W (W+n)) ∏L j=1 % 2 js 2 j
  2
  ( ᾱ3 ) . (50)
  Consider the class of networks, ΘNNγ , obtained by affixing the ramp loss, `γ , and the negated margin operator, −M, to the output of the provided network class:
  ΘNNγ := {(x, y) 7→ `γ(−M(θ(x), y)) : θ ∈ Θ} . (51)
  Since (z, y) 7→ `γ(−M(z, y)) is 2/γ-Lipschitz w.r.t. ‖ · ‖2 and definition of `γ , the function class ΘNNγ falls under the setting of (50), the covering number of a set of all neural networks is bounded as follows:
  lnN (( ΘNNγ ) |x , , ‖ · ‖2 ) ≤ (‖X‖p+ √ n)2 ln(2W (W+n))
  2
  4( ∏L j=1 s 2 j% 2 j) (∑L i=1 ( bi si )2/3)3 γ2 =: (‖X‖p+ √ n)2 ln(2W (W+n))R 2 . (52)
  Using the above covering number bound (52) in the Dudley entropy integral (28) with α := 1/ √ n, we achieve the bound for the Rademacher complexity as follows:
  R ( (Fγ)|S ) ≤ inf α>0 ( 4α√ n + ln( √ n/α) 12 √ (‖X‖p + √ n)2 ln (2W (W + n))R n )
  ≤ 4 n + 24 ln(n)(‖X‖p +
  √ n) √ ln(2W (W + n))
  γn
  ( L∏ i=1 si%i )( L∑ i=1 a 2/3 i s 2/3 i )3/2 .
  (53) We complete the proof of Theorem 3 by substituting (53) in (22).
sections.heading: A.2.3 EMPERICAL VALIDATION OF THEOREM 3
sections.text: In this section, we empirically verify Theorem 3 regarding two variables: the neural network’s width, W , and the number of clean samples. The experiment is conducted with poisoned models trained over Trojan WM poisoned CIFAR-10 (poison rate: 20%, target label: 2).
sections.heading: Model Name # Parameters W Average Error Gap (%)
sections.text: Table 7 shows the empirical results of adopting different models with different widths. All the poisoned models are poisoned with Trojan WM attack using a poison rate of 20%. We sorted the models according to their maximum width (W ) in Table 7. The Error Gap is obtained as the absolute value of the test error subtracted by the training error after conducting the defense. Based on the observation, the error gap is smaller as the model width grows, indicating better generalizability. Aligning with Theorem 3, the generalizability has a positive correlation with W .
  Table 8 shows the empirical results of adopting different numbers of clean samples during the IBAU. As indicated from the results, a larger number of clean samples would lead to a smaller value of the Error Gap, which indicates a better generalization of unlearning effect from training to unseen data. Such results aligned with Theorem 3.
  A.3 IMPLEMENTATION DETAILS AND COMPLEXITY ANALYSIS
  I-BAU does not need to compute the second-order derivative directly. Instead, it is computed via implementing an approximation of the response Jacobian via an iterative solver (e.g., conjugated gradient algorithm (Rajeswaran et al., 2019) or fixed-point algorithm (Grazzi et al., 2020)) in limited rounds along with the reverse mode of automatic differentiation (Baur & Strassen, 1983; Griewank & Walther, 2008) by treating the problem as a linear system. Automatic differentiation in reverse mode is a widely used technique in modern deep learning packages such as Tensorflow and PyTorch (Baydin et al., 2018). This section gave the ablation study over the norm bound given in Algorithm 1 and the memory and time complexity analysis and comparisons.
  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 a norm constrained of the synthesized trigger as long as the trigger’s value is within the image value range (from 0 to 1 in our case with float type images).
  The l2 norm of launching the Trojan WM attack is 8.739 (measured by comparing with a zero matrix of the same size). As shown in Figure 2 a larger norm bound leads to a more robust and accurate synthesis of the potential trigger on the GTSRB. Especially the l2 norm bounds that are greater than
  the attack trigger’s l2 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 ∇δ(θ) = − ( ∇21H(δ(θ), θ) )−1∇21,2H(δ(θ), θ) via automatic differentiation is no more than twice the memory used when computing ∇H(δ, θ), which making our space complexity as Mem(∇H(δ, θ)). Recalling another popular class of methods to solve bilevel optimization—explicit gradient methods (Grazzi et al., 2020), whose memory complexity is Mem(K · T · ∇H(δ, θ)) as they need to save the full computational graph during backpropagation, where K is the number of rounds for adversarial unlearning, T is the number of computations for the inner. In comparison, I-BAU is more memory efficient by adopting the implicit gradient via the iterative solver to approximate the computational graph without saving the whole graph.
sections.heading: A.3.3 TIME COMPLEXITY ANALYSIS
sections.text: Following our design of Algorithm 1 (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 complexity would be Õ(K ·ϑ ·Õ(θ)), where Õ(θ) is the time complexity of training a neuronal network, θ, via backpropagation for one epoch on the clean images used for unlearning (for most of the experiments, we used 5000 samples). In practice, we adopted ϑ = 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 6 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 a large number of steps (K1 steps) of optimization to synthesize the trigger. Roughly their time complexity under the settings of limited iterations is Õ(K1 · C · Õ(θ)). In practice, K1 · C is much larger than K · ϑ. • DI incorporated an additional GAN to synthesis the trigger, assuming training and implementing
  the GAN is of the time complexity Õ(θGAN ), thus making the total time complexity roughly equals to Õ(max(Õ(θGAN ), Õ(θ))). In practice, the overhead of training a GAN trigger inspector is much expensive (estimated 300× longer GPU time on the CIFAR-10) than training θ. • 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) to meet the stop requirements. • NAD’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, we assume the time complexity of training them over the unlearning dataset is Õ(θ). Assuming teacher model training phase takes K3 epochs, and tuning student model based on the teacher model takes K4 epochs, then the total time complexity is Õ((K3 + 2 ×K4)Õ(θ)). In practice, we adopted K3 = K4 = 20 according to the original work.
  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).
sections.heading: A.4 EXPERIMENTAL DETAILED SETTINGS
sections.text: The details of the simplified VGG model adopted in our paper are explained in Table 9. For each convolutional layer, we used batch normalization, and ELU is adopted as the activation function for each. We use Adam with a learning rate of 0.05 as the optimizer for poisoned models. The models are trained with 50 epochs over each poisoned dataset to converge and attain the results shown in the main text. Our experiment adopted ten NVIDIA TITAN Xp GPUs as the computing units with four servers equipped with AMD Ryzen Threadripper 1920X 12-Core Processors. Interestingly, the same experiments showed slower convergence (it takes more rounds to mitigate the backdoors) using GTX TITAN X and GTX 2080 TI. To reproduce the exact experimental results, we suggest considering adopting NVIDIA TITAN Xp GPUs for the experiments. PyTorch (Paszke et al., 2019) is adopted as the deep learning framework for implementations. For the settings of implementing the I-BAU, the inner and outer is conducted with iterative optimizers (SGD or Adam) with a learning rate of 0.1.
sections.heading: A.4.1 ATTACKS DETAILS
sections.text: We list the examples of the adopted backdoor attacks in this section. We incorporated eleven different backdoor attacks in this work. Figure 3 shows the examples from CIFAR-10 and the GTSRB before and after patched with different backdoor triggers. We adopted the same target label on the two datasets under one-trigger-one-target settings, as listed in Figure 3: BadNets white square trigger targeting at label 8 (BadNets) (Gu et al., 2017), Hello Kitty blending trigger targeting at label 1 (Blend) (Chen et al., 2017), `0 norm constraint invisible trigger targeting at 0 (`0 inv) (Li et al., 2020a), `2 norm constraint invisible trigger targeting at 0 (`2 inv) (Li et al., 2020a), Smooth trigger (frequency invisble trigger) targeting at 6 (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 a fixed size of 5000, where the remaining data (5000 for the CIAFR-10 and 7630 for the GTSRB) will be used to evaluate the unlearning efficacy (ACC and ASR).
sections.heading: A.4.2 BASELINE DEFENSES DETAILS
sections.text: 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), Finepruning (FP) (Liu et al., 2018a), Neural Attention Distillation (NAD) (Li et al., 2020b), and Differential Privacy training as a general robustness defense (DP) (Du et al., 2019). The detailed settings of comparison are provided as follows:
  • NC is conducted following the same settings as the original work but only use the same 5000 samples as ours; for the outlier detection, we marked and unlearned all the detected triggers (Median Absolute Deviation (MAD) based on the generated trigger’s norm, marked all the triggers whose mask MAD loss larger than 2 as detected). • DI adopted model inversion technique for agnostic to the clean samples, yet made the defense’s efficacy highly depend on the inversion technique. For a fair comparison, we feed the same 5000 samples, which are available to the other methods, to the GAN synthesizer in DI and obtains the final results; for the outlier detection, we marked and unlearned all the detected triggers (MAD based on the average loss for generating a trigger, marked all the triggers whose MAD loss larger than 2 as detected). • TABOR’s settings follow the original work but with only 5000 clean samples being provided. (MAD based on the norm computation proposed in the original work to get rid of false alarms, marked all the triggers whose MAD loss larger than 2 as detected.) • FP follows the suggestions of the original work, where we prune the network by supervising the ACC to drop to a certain percentage, i.e., 20%. This part’s ACC is done by using 1000 samples from the 5000, and the rest 4000 clean samples are used to fine-tune the model to recover the ACC. • NAD’s implementation follows the exact settings as the original work. The original work did not emphasize much over the preprocessing, and we used the same preprocessing following their open-sourced codes 1. • DP follows the settings in the work that first mentioned use DP as a backdoor defense (Du et al., 2019), where we tuned the noise multiplier to attain universal effectiveness across all the considered attacks(50 for the CIFAR-10, 1.5 for the GTSRB).
sections.heading: A.5 CASE STUDY ON NON-ADDITIVE BACKDOOR ATTACKS
sections.text: As our fundamental formulation takes backdoor triggers as additive noise, in this specific section, we would like to evaluate the effectiveness of I-BAU towards non-additive backdoor attacks empirically. We selected four unique backdoor attacks/ settings to evaluate I-BAU towards non-additive attacks, which will be introduced as follows. 1) Semantical replacement (SR), which directly replaces the poison image with a piece of different semantical information. We designed this attack by directly changing all the poisoned images to an out-of-distributed ‘Hallo Kitty’ image with the poisoned label. SR should be considered as one of the worst-case attack scenario in practice, as its trigger is additional semantical information with a large norm bound; 2) WaNet (Nguyen & Tran, 2021) adopts a universal wrapping augmentation as the backdoor trigger. Under such a case, the backdoor trigger becomes a specific augmentation technique but not direct information insertion or addition. And WaNet has shown its ability to bypass some existing defense methods; 3) IAB attack (Nguyen & Tran, 2020) adopts autoencoder to learn and assign sample-specific noise to inputs to launch sample-specific backdoor attacks; 4) Hidden trigger (HT) attack (Saha et al., 2020) adopts a unique poisoning procedure using projected gradient descent to compute adversarial noise, which we consider as another example of a non-additive attack. We evaluate the effectiveness of I-BAU against the above four non-additive attacks on the CIFAR-10 dataset. We will illustrate their specific settings and results in the following parts of this section.
sections.heading: A.5.1 TOWARDS MITIGATING SR
sections.text: We first evaluate an extreme case where we replace the poisoned CIFAR-10 images with an outof-domain ’Hallo Kitty’ image. Such a procedure directly changes the semantic information of the poisoned data. We set the target label as ’0’. Like the other evaluated attack, we replaced 20% of the non-target-class samples with the trigger kitty and set the label as ’0’. As for launching the attack during test time, we evaluate the same ’Hallo Kitty’ image exposed to the poisoned model and measure the attack success rate (in this case it becomes either 100% or 0%). The target model here adopted the small VGG16 introduced in our experiment. As for I-BAU, we adopted Adam optimizer and a learning rate of 0.1 and an unlimited l2 norm bound (instead, we crop the perturbation’s value and restricted it to 0-1 as discussed in Appendix A.3.1). The results before and after are listed below in Table 10.
  1https://github.com/bboylyg/NAD
sections.heading: Clean ACC - Before ASR - Before Clean ACC - After ASR - After
sections.text: As demonstrated in Table 10, within three rounds of I-BAU, we obtained a clean model with an acceptable ACC drop compared to the baseline. Interestingly, the extreme case directly inserts an additional semantical link between the poison kitty and the class ’0’, which can be interpreted as direct exposure of a specific training sample to the test set and interfere with the model generalizability (aka, overfit to a rare feature). Surprisingly, I-BAU can effectively mitigate such attack patterns. To our best knowledge, the above attack setting is never considered before. I-BAU also shows a potential path towards resolving model overfitting issues. We will leave such discussion to future work.
sections.heading: A.5.2 TOWARDS MITIGATING WANET
sections.text: WaNet is one of the famous invisible attack, instead of adopting an additive trigger, it adopts the same elastic transformation as the trigger of the attack. We directly downloaded the pre-trained poisoned PreActResNet18 on the CIFAR-10 from their work as the poison model to be adversarially unlearnt 2. As for I-BAU, we adopted Adam optimizer and a learning rate of 0.0001 and an unlimited l2 norm bound. The results before and after are listed in Table 11, which indicates an effective defense with acceptable influence in the ACC.
sections.heading: Clean ACC - Before ASR - Before Clean ACC - After ASR - After
sections.heading: A.5.3 TOWARDS MITIGATING THE IAB ATTACK
sections.text: An emerging line of attack focuses on sample-specific attacks; here, we evaluate against IAB attack, which utilizes an autoencoder to learn and insert sample-specific triggers. We followed the same implementation as provided in the original work 3, with the following specific settings: dataset: CIFAR-10; target label:0; ρb = ρc = 0.1; model: PreActResNet18. One difference is that we loaded the CIFAR-10 dataset in a customized dataset format instead of the default (i.e., we used “torch.Tensor” loaded from “NumPy.array” with range [0, 1], instead of “torch.Tensor” loaded from “PILimages” with range [−1.99, 2.13]). We did this to facilitate the implementation of I-BAU (which targeting at noises ranging from [0, 1] for the current implementation). The results prior to and during the intervention are summarized in Table 12, indicating an effective defense with a low influence in the ACC.
sections.heading: Clean ACC - Before ASR - Before Clean ACC - After ASR - After
sections.heading: A.5.4 TOWARDS MITIGATING HT
sections.text: Finally, we evaluated the effectiveness of Hidden trigger (HT) backdoors (non-additive during poisoning), whose trigger inserting process is by directly resolving adversarial noise generated via projected gradient descent. We evaluated I-BAU with the CIFAR-10 random pairs attack settings from the original work (trigger 10, target: 8, source: 5, number of samples to generate PGD noise: 1500, number of poison in target class: 800, = 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
  2https://github.com/VinAIResearch/Warping-based_Backdoor_Attack-release 3https://github.com/VinAIResearch/input-aware-backdoor-attack-release
  a successful targeted attack, we 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 a poisoned model with an ACC/ASR of “73.41/89.00”. After adopting I-BAU for 20 rounds, the poisoned model’s performance becomes “84.58/11.10”, and with larger rounds (90 rounds), the performance can further be improved to “84.06/0.23”, which indicates a robust and effective defense and an extra effect on recovering ACC.
sections.heading: A.5.5 HIGHLIGHTS ON THE CASE STUDIES TOWARDS NON-ADDITIVE ATTACKS
sections.text: The above results from the case study on using I-BAU to mitigate non-additive attacks highlight that although our formulation targets a universal pattern that most misled misclassifications in an additive way, I-BAU is empirically effective towards mitigating non-additive attacks. These emperical results have a great chance to lead to some exciting future works on theoretical analysis of the effectiveness of our proposed minimax formulation. We will open-source all incorporated attacks (at the moment, eleven attacks are incorporated, seven in the main text, and four non-additive case studies in the Appendix) and the pre-trained poisoned models. We will constantly check out the emerging attacks and look forward to seeing the first attack can evade our defense!
sections.heading: A.6 TSNE ANALYSIS ON UNLEARNING EFFECTS
sections.text: The TSNE analysis of the feature extracted by the poisoned model and the unlearned model is shown in Figure 4. The model considered here is a BadNets poisoned model on the CIFAR-10 dataset (target label is 8), and the results listed in Figure 4 are before and after one round of I-BAU. Before the I-BAU, the poison model’s extracted features for samples with/without triggers are disparate, even for samples originating from the same class. After the I-BAU, we can see that the unlearned model will map the samples patched with triggers back to their original classes (same color). Such results demonstrate the effectiveness of the backdoor unlearning from another perspective.
  A.7 ITERATIVE ILLUSTRATION ON MULTI-TARGET CASES
  We show the iterative records of I-BAU mitigating more complicated attack cases, i.e., the all-to-all attacks and 7-trigger-7-target cases on the two evaluated datasets. We listed them here as they take
  more rounds than one-trigger-one-target cases, which can usually be mitigated in a one-shot-kill manner.
  Figure 5 shows the results on countering the BadNets all-to-all attacks, where (a) is the results on the CIAFR-10 dataset, and (b) is the results on the GTSRB dataset. As shown in Figure 5 (a), although it takes more rounds than one-trigger-one-target cases to mitigate the attack, thanks to the accurate computing of the hyper gradient, the I-BAU did not impact much over the ACC. When the ASR drops below 10%, the unlearned model can still maintain an ACC above 80% (original ACC: 86.38). Meanwhile, in Figure 5 (b), we see that we can unlearn the BadNets trigger under all-to-all cases with even fewer rounds of I-BAU, and the unlearned model can maintain an ACC of around 99% during the entire unlearning procedure.
  Figure 6 demonstrates the mitigation records of each iteration of I-BAU over the 7-trigger-7-target cases over the two evaluated datasets. Figure 6 (a) draws the details on the CIFAR-10 dataset, which took more than 200 rounds of I-BAU to mitigate all seven attacks. On the GTSRB, the mitigation of all seven triggers takes less time. And the model can maintain an ACC close to 99% during the entire unlearning procedure.
  Upon observation, there are triggers easier to be found by the I-BAU, e.g., Trojan WM and Trojan SQ, as they are optimized triggers, and thus easier to be 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).