Adversarial Unlearning of Backdoors via Implicit Hypergradient

Yi Zeng; Si Chen; Won Park; Z. Morley Mao; Ming Jin; Ruoxi Jia

Source-linked AI summary

Adversarial Unlearning of Backdoors via Implicit Hypergradient

Yi Zeng, Si Chen, Won Park, Z. Morley Mao, Ming Jin, Ruoxi Jia

arXiv:2110.03735v4Oct 7, 2021cs.LGcs.CRcs.CV

TL;DR

Backdoor defenses must remove trigger-induced misclassification from poisoned models using limited clean data. The paper formulates this as a minimax problem and proposes I-BAU, which uses implicit hypergradients to capture inner–outer interdependence. Across eleven evaluated backdoor attacks, I-BAU is reported as the only generalizable defense, matching or exceeding combined state-of-the-art baselines.

Problem
Backdoor removal must sanitize poisoned models with a small clean set, while existing defenses can be limited by trigger and attack assumptions.
Method
The paper formulates backdoor removal as a minimax optimization and solves it with I-BAU using implicit hypergradients.
Results
I-BAU is reported as the only generalizable defense across all evaluated eleven backdoor attacks, with results comparable to or exceeding combined six existing state-of-the-art techniques.
Takeaways & Limitations
I-BAU remains effective across varied triggers, attack settings, poison rates, and clean-data sizes, including the extreme case of 100 clean samples.
Takeaways & Limitations
The attack model assumes trigger perturbations satisfy a bounded norm constraint and the theory’s neural-network result assumes specified Lipschitz nonlinearities and matrix-norm bounds.

Abstract

from arXiv · show

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 Bacdoor 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 seven 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.

1 INTRODUCTION

Backdoor attacks implant triggers that cause targeted misclassification, motivating defenses that can remove them from poisoned models. I-BAU addresses limitations of trigger-synthesis defenses with a minimax formulation and implicit hypergradients.

Motivation: Backdoor attacks embed predefined triggers during training so patched test examples are misclassified into target classes.Such attacks threaten machine-learning deployment in mission-critical applications.
Prior limitations: Trigger-synthesis defenses assume triggers target few classes, limiting their effectiveness against attacks targeting many classes.These methods also incur high computational costs through per-class trigger synthesis or additional training.
Proposed approach: I-BAU formulates backdoor removal as a minimax problem encompassing prior trigger-synthesis defenses.The formulation is designed to address their limitations rather than treating inner and outer problems independently.
Proposed approach: I-BAU uses implicit hypergradients to account for interdependence between inner and outer optimization.The supplied passage introduces the method and its central optimization distinction from previous work.

2 RELATED WORK

Backdoor attacks have progressed from visible patterns to visually invisible or optimized triggers, improving stealth while preserving attack effectiveness.

Backdoor Attacks: Backdoor attacks evolved from visible unrelated or optimized patterns toward visually invisible triggers.The passage contrasts easy human detection of visible triggers with later approaches designed for greater stealth.

3 PROBLEM FORMULATION

The problem formulation models poisoned classifiers, adversarial triggers, and limited clean data to define backdoor removal as robustness to patched inputs.

Attack model: The attacker poisons clean training data so adding a bounded trigger δ to test input x induces target-class prediction ỹ.The attack model permits multiple trigger patterns and target classes; poison ratio is the fraction of backdoored training examples.
Defense goal: The defender receives a poisoned classifier and a small clean dataset, then seeks a model invariant to adding backdoor triggers.Available clean examples are assumed much smaller than the data needed to retrain a high-accuracy model from scratch.
Minimax formulation: The minimax objective maintains correct labels under attacker-selected triggers by combining an inner maximization with an outer minimization.The formulation is motivated by requiring the classifier to withstand trigger-patched inputs.
Minimax formulation: Unlike evasion attacks, backdoor defenses apply the same trigger δ to every clean sample rather than choosing a perturbation per example.This shared-trigger structure distinguishes the backdoor minimax formulation from standard adversarial-training formulations for evasion.

4 ALGORITHM

I-BAU solves the backdoor-removal minimax by differentiating through the inner optimization response, avoiding the problematic decoupling of naive adversarial training.

Motivation: Naive adversarial training alternates inner trigger maximization and outer model minimization, but their decoupling can be problematic for universal perturbations.Universal-perturbation construction can also be unstable because summed example-specific perturbations may cancel.
Proposed algorithm: I-BAU accepts suboptimal inner solutions and uses an implicit hypergradient without requiring convexity.The method is designed to be more robust to errors from failing to solve the inner maximization globally or locally.
Implicit differentiation: The hypergradient combines direct model dependence with an indirect dependence mediated by the trigger response Jacobian.The response Jacobian captures how the inner solution changes with model parameters.
Implicit differentiation: At a stationary inner solution with invertible Hessian, the response Jacobian is obtained through second-order derivatives.The resulting construction uses curvature and sensitivity to account for inner–outer interdependence.
Model update: Gradient descent on the implicit hypergradient updates the poisoned model using only the trigger solution rather than its optimization path.This makes the approach more memory-efficient than explicitly solving the bilevel optimization path.

5 THEORETICAL ANALYSIS

Theoretical analysis establishes convergence of I-BAU’s approximate hypergradient and bounds the generalization of trigger robustness from clean samples to unseen data. These bounds improve with more clean samples, while empirical analysis reports strong generalizability even with 100 clean samples.

Convergence Analysis: The convergence analysis assumes Lipschitz continuity of direct gradients, bounded and Lipschitz second-order terms, and asymptotic convergence of the inner solution.These regularity conditions control approximation error in the implicit hypergradient.
Convergence Analysis: As the inner epoch number t increases, I-BAU’s estimated hypergradient becomes more accurate, and under convexity the solution converges.Theorem 1 analyzes the approximate hypergradient at each inner and outer iterate.
Generalization Analysis: When the number of clean samples n increases, adversarial-unlearning generalizability improves for both linear models and neural networks.The paper provides separate high-probability generalization bounds for linear models and neural networks.
Generalization Analysis: The neural-network bound has an additional n-dependent term compared with regular training, indicating harder generalizability than the regular learning problem.The bound is derived for networks with Lipschitz nonlinearities and norm-bounded weight matrices.
Generalization Analysis: Empirically, I-BAU remains excellently generalizable when the defender has access to only 100 clean samples.The proof treats the shared backdoor perturbation as additional model-parameter dimensions and uses a Dudley entropy integral to bound Rademacher complexity.

6 EVALUATION

Across attack settings and datasets, I-BAU robustly removes backdoors while preserving accuracy, with stronger stability, sensitivity, and efficiency than most baselines.

Experimental setup: I-BAU is evaluated against three attack settings and seven trigger types on CIFAR-10 and GTSRB, compared with six defenses.
Efficacy: I-BAU robustly mitigates all tested triggers without significantly affecting ACC, matching or outperforming the best baseline in most settings.It underperforms the best baseline only for Smooth triggers, where Fine-pruning is effective.
Efficacy: In the 7-trigger-7-target setting, I-BAU reduces ASR while maintaining ACC on both datasets without dataset-specific preprocessing changes.Trigger-synthesis baselines are ineffective on CIFAR-10 because 7/10 labels are targeted, while NAD requires customized preprocessing.
Stability: I-BAU shows smoother, more stable ASR reduction than the naive heuristic and can mitigate the attack after one outer-minimization iteration.The comparison uses BadNets on CIFAR-10 across different iterations and runs.
Sensitivity: I-BAU is least sensitive to poison ratio and clean-data size, retaining acceptable backdoor removal with only 100 clean samples.Across poison ratios it maintains good ACC and ASR; all defenses decline as clean samples decrease.
Efficiency: 6.82 s on CIFAR-10 and 7.84 s on GTSRB are I-BAU’s average runtimes to reduce ASR below 20% in the one-trigger-one-target setting.I-BAU can take effect in one iteration, whereas NC and TABOR synthesize triggers independently for each label.

7 CONCLUSION

The paper formulates backdoor removal as a minimax problem and solves it with I-BAU, supported by convergence and generalization analysis. Across evaluated attacks, I-BAU is broadly effective, computationally efficient, and robust with limited clean data.

7 CONCLUSION: I-BAU is the proposed implicit-hypergradient method for solving a minimax formulation of backdoor removal.The formulation encompasses existing unlearning objectives without assumptions about attack strategies or trigger patterns.
7 CONCLUSION: I-BAU is the only defense reported to generalize across all eleven evaluated backdoor attacks.Its results are comparable to or exceed the best results obtained by combining six existing state-of-the-art techniques.
7 CONCLUSION: I-BAU is less sensitive to poison rate and remains effective when the defender has access to only 100 clean samples.The paper identifies this as an extreme setting for clean-data access.

A.1 CONVERGENCE BOUND

The convergence analysis studies the fixed-point map used in the minimax method and bounds derivatives needed to control the approximate implicit hypergradient. It relies on smoothness, strong convexity, Lipschitz, and boundedness assumptions.

A.1 CONVERGENCE BOUND: The analysis defines Φ(δ, θ) = δ + α(θ)∇1H(δ, θ), where H is twice continuously differentiable in δ and θ.H is also assumed strongly convex and Lipschitz smooth in δ.
A.1 CONVERGENCE BOUND: The step size α(θ) is selected from the strong-convexity and smoothness constants of H to establish contraction-related properties of Φ.The passage specifies α(θ) using LH(θ) and µH(θ).
A.1 CONVERGENCE BOUND: The proof introduces partial Jacobians of Φ with respect to δ and θ, then simplifies the θ-Jacobian at the fixed point δ(θ).These derivatives support the implicit hypergradient analysis.
A.1 CONVERGENCE BOUND: Bounds on the Jacobians and cross-derivative terms are obtained from assumed Lipschitz continuity and norm boundedness of second-order terms.The resulting constants control variation in the partial Jacobians and the approximate hypergradient.
A.1 CONVERGENCE BOUND: The proof of Theorem 1 applies an inequality from Lemma 1 with constants specified in the cited equations.The supplied passages identify this as the final proof mechanism but do not state the theorem’s explicit bound.

A.2 GENERALIZATION BOUNDS

The generalization analysis bounds adversarial unlearning risk on the source distribution using empirical risk on clean unlearning data and function-class complexity. It uses margin-based losses and Rademacher complexity.

A.2 GENERALIZATION BOUNDS: The analysis defines a general margin operator M(v, y) and a ramp loss ℓγ for margin-based generalization bounds.The ramp loss is specified piecewise using the margin parameter γ.
A.2 GENERALIZATION BOUNDS: Population risk against perturbations and empirical risk on the clean unlearning dataset are related through the stated generalization framework.Rγ(θ) and R̂γ(θ) upper-bound error fractions on the source distribution and Dsan, respectively.
A.2 GENERALIZATION BOUNDS: The resulting bound is obtained by controlling the Rademacher complexity of the loss function class over unlearned models.The bound holds with probability at least 1−ξ over the clean dataset for every θ in the model class.
A.2 GENERALIZATION BOUNDS: The proof specializes the complexity analysis to linear models and neural networks.The supplied passages identify these model classes as the settings where the bound is instantiated.

A.2.1 PROOF FOR LINEAR MODELS

The linear-model proof evaluates the Rademacher complexity of poisoned linear predictors under bounded perturbations and inputs. It decomposes the bound into terms that are separately controlled before substituting the result into the generalization theorem.

A.2.1 PROOF FOR LINEAR MODELS: The proof defines the class of linear poisoned models under perturbation δ as functions mapping x to ⟨θ, x + δ⟩.The parameter θ ranges over the model class.
A.2.1 PROOF FOR LINEAR MODELS: The analysis assumes bounded model weights, perturbation norm, and input l2 norm.The cited passage denotes the bounds by Cθ, Cδ, and χ.
A.2.1 PROOF FOR LINEAR MODELS: The Rademacher-complexity calculation separately bounds terms A and B before combining them into an overall complexity bound.The supplied proof steps invoke Cauchy–Schwarz for one bound and then proceed analogously for the other.
A.2.1 PROOF FOR LINEAR MODELS: Substituting the derived complexity bound into the preceding generalization inequality completes the proof of Theorem 2.The conclusion connects the linear-model calculation to the paper’s adversarial-unlearning bound.

A.2.2 PROOF FOR NEURAL NETWORKS

The proof derives a neural-network generalization bound by combining covering-number estimates across layers with the Dudley entropy integral. It also reports empirical evidence that wider networks and more clean samples improve the generalization of I-BAU’s unlearning effect.

Generalization bound: The resulting network covering bound is inserted into the Dudley entropy integral to derive a Rademacher-complexity bound and the neural-network generalization bound.The loss-composed function class is treated as Lipschitz before applying the entropy argument.
Proof strategy: The proof bounds the whole network by first covering the perturbed input layer, then subsequent layers, and finally composing layerwise covers.The network is represented as Fθ(x) through L Lipschitz layers, with operator-norm constraints and layer-specific covering resolutions.
Input-layer covering: The input-layer analysis covers the matrix product ˆX ˆA1 induced by poisoned inputs X + ∆.The augmented matrices incorporate the perturbation into the input representation before bounding the product’s covering number.
Network covering: Subsequent-layer covering uses established bounds for affine transformations, while induction combines these estimates into a covering number for the entire network.The proof centers covers at zero and applies layerwise resolutions to obtain the whole-network bound.
Empirical validation: Larger network width produces a smaller empirical Error Gap after defense, indicating better generalizability and aligning with Theorem 3.The models used Trojan WM poisoning at a 20% poison rate; Table 7 reports the Error Gap after I-BAU.
Empirical validation: More available clean samples produce a smaller Error Gap, indicating stronger generalization of the unlearning effect from training data to unseen data.The results use I-BAU-defended models with different clean-sample counts and averages over five runs.

A.3 IMPLEMENTATION DETAILS AND COMPLEXITY ANALYSIS

I-BAU approximates implicit hypergradients without directly computing second-order derivatives and is evaluated across norm bounds, attack types, datasets, and iterative unlearning settings. The reported results show effective mitigation, low clean-accuracy impact in several multi-target cases, and lower computational cost than prior defenses.

Implementation: I-BAU computes the response Jacobian through an iterative linear-system solver and reverse-mode automatic differentiation rather than directly forming second-order derivatives.The implementation can use conjugate-gradient or fixed-point iterations for the Jacobian approximation.
Norm-bound sensitivity: A larger l2 norm bound improves trigger synthesis robustness, and bounds above the Trojan WM trigger’s l2 norm yield low ASR with limited clean-ACC impact.The attack trigger’s l2 norm is 8.739; the experiments compare bounds 0.5, 5, 10, 20, and Best Efforts.
Complexity: I-BAU has theoretical time complexity ˜O(K·ϑ·˜O(θ)) and, with ϑ = 5 in practice, is reported as more efficient than state-of-the-art defenses.The conclusion states that this theoretical advantage aligns with empirical average time-to-effect results for one-target attacks.
Non-additive attacks: After 20 I-BAU rounds on the hidden-trigger attack, performance changes from 73.41/89.00 ACC/ASR to 84.58/11.10, reaching 84.06/0.23 after 90 rounds.The experiment enlarges the hidden-trigger perturbation parameter to ϵ = 50 to obtain a successful targeted attack.
Multi-target attacks: For BadNets all-to-all attacks, CIFAR-10 requires more rounds but retains ACC above 80% when ASR falls below 10%, while GTSRB reaches around 99% ACC throughout.The GTSRB case unlearns the trigger in fewer rounds than the CIFAR-10 case.
Multi-target attacks: Across seven-trigger-seven-target cases, CIFAR-10 requires more than 200 I-BAU rounds, whereas GTSRB mitigates the triggers faster while maintaining ACC close to 99%.The authors also observe that optimized triggers such as Trojan WM and Trojan SQ are easier for I-BAU to find.