Hard to Forget: Poisoning Attacks on Certified Machine Unlearning

1 Introduction

• Full retraining after erasure can be computationally costly, motivating machine unlearning as a more efficient way to undo data’s impact on a model.Organizations may need to erase personal data from trained models as well as from their source data.Source: §1 · p. 1
• Existing theoretical guarantees address privacy through indistinguishability of unlearned and retrained models but largely ignore computation cost.The paper contrasts these guarantees with empirical work that assumes passive, trusted users.Source: §1 · p. 2
• An active user can strategically modify training data within bounded perturbations and later request its erasure to slow unlearning.Bounded modifications are motivated by a desire to remain undetected.Source: §1 · p. 2
• The authors report that poisoning can significantly undo unlearning’s advantages over full retraining and can harm computation beyond accuracy, like a denial-of-service attack.Their experiments cover varied parameters, white-box and grey-box attacks, perturbation geometries and bounds, attacker-cost trade-offs, and long-term feasibility.Source: §1 · p. 2

2.1 Machine learning on user data

• An organization erases a user’s raw data and seeks to remove its influence from trained models; approximate unlearning requires the resulting model distribution to be statistically indistinguishable from retraining without the erased data.The paper adopts Guo et al. (2020)’s definition and algorithms for concreteness.Source: §2.1 · p. 2

2.2 Certified removal

• Certified removal approximates the effect of erasure with an influence-function parameter update, while tracking a gradient-residual upper bound and retraining if it exceeds a trigger.The influence function approximates the parameter change when data is added; retraining is used to ensure certified removal when the trigger is exceeded.Source: §2.2 · pp. 3–4

2.3 Vulnerability and threat model

• The attack exploits the possibility that certified removal’s approximation error exceeds its threshold, triggering full retraining and diminishing or nullifying unlearning’s efficiency gains.The attacker may control users, modify their training data within limits, and issue erasure requests; the defender is assumed unaware of this slow-down attack and conducts basic validity checks and occasional manual audits.Source: §2.3 · pp. 4–5

3.1 Formulation as a data poisoning problem

• The attacker maximizes the cost of erasing poisoned data while satisfying defender checks; exact bilevel optimization is generally infeasible, so gradient methods seek locally optimal solutions.The formulation defines cost for erasing a subset from a trained model with the defender’s unlearning algorithm.Source: §3.1 · p. 5

3.2 PGD-based crafting strategy

• The PGD strategy assumes regularized linear learning and unlearning, modifies features but not labels from clean reference data, and constrains each poisoned row to an ℓ_p ball.The constraints center each ball on the corresponding row of a reference matrix.Source: §3.2 · p. 5
• Because the expectation in the formulation cannot be computed exactly, the method approximates it with a zero-th-order expansion and solves a single-level constrained problem using PGD.The replacement uses the zero-mean perturbation in the objective.Source: §3.2 · pp. 5–6

3.3 Measuring the computational cost

• The attack targets the gradient-residual bound because retraining is triggered when it exceeds a threshold and dominates the cost of repeated unlearning calls.Prior work reports full retraining is three orders of magnitude slower than an approximate update; the paper’s cost function assumes one erasure call but is effective across sequential calls in experiments.Source: §3.3 · p. 6
• To reduce attacker computation, the paper considers cheaper upper-bound surrogates and fixing the trained model with respect to poisoned data, an approximation reported to perform well empirically.One surrogate avoids Hessian dependence; the direct cost can require operations scaling linearly with the remaining training-set size.Source: §3.3 · p. 6

4.1 Datasets and setup

• Experiments consider MNIST and Fashion-MNIST (28 × 28 single-channel images, ten classes), Binary-MNIST from MNIST classes 3 and 8, and human activity recognition (HAR) sensor windows (561 dimensions, six activity classes).Source: §4.1 · p. 7
• White-box attackers replace controlled training examples, while grey-box attackers use test data as a surrogate; retrain interval counts requests before first full retraining.Source: §4.1 · p. 7

4.2 Results

• The attack reduces retrain intervals by 70–100% across λ and σ settings, reaching zero at smaller values while larger values generally trade accuracy for unlearning efficiency.A zero interval means retraining is triggered immediately upon a poisoned erasure request.Source: §4.2 · p. 7
• For Binary-MNIST, unconstrained perturbations (p = ∞, r = 1 or p = 1, r = d) are most effective but make poisoned images unrecognizable as digits; ℓ1 appears more effective than alternatives.Source: Table 3 · p. 8, §4.2 · p. 8
• The influence-norm cost matches GRNB effectiveness while reducing attacker computation; the gradient-norm cost is least demanding but less effective.Source: Table 4 · p. 8, §4.2 · p. 8
• Ignoring model dependence on poisoned data yields no marked effectiveness difference while significantly reducing attacker computation, plausibly because the poisoned set is relatively small.Source: §4.2 · p. 8
• Retraining increases moderately as poisoned erasure requests accumulate; after 500 requests, all poisoned instances are erased and only clean data remains.Source: §4.2 · p. 8, Figure 1 · p. 9
• Grey-box surrogate-data attacks transfer well, with very little retrain-interval difference from white-box attacks.Source: Table 5 · p. 9, §4.2 · p. 9

• Strict unlearning requires a model identical to retraining from scratch; known closed-form methods for several canonical models have data-independent running times and are immune to this attack.Source: §5 · p. 9
• Unlearning-efficient model designs include randomized-tree ensembles, k-means variants, and SISA, which uses data sharding and caching.Source: §5 · p. 9
• Approximate unlearning seeks statistical indistinguishability from retraining; certified approaches address strongly convex problems, while some complexity analyses lack empirical validation and rely on bounds considered too loose in practice.Source: §5 · pp. 9–10
• For non-convex DNNs, approximate unlearning remains elusive; cited methods lack guarantees and need further approximations to scale, though their fixed iteration counts make them immune to slow-down attacks.The paper notes its attack could instead prevent proper erasure or leave the unlearned model unpredictable.Source: §5 · p. 10
• Prior unlearning work also examines privacy vulnerabilities, adaptive erasure requests, SISA attacks, and verification of erasure.Source: §5 · p. 10
• Poisoning attacks commonly target test performance or trigger-based misclassification; this attack targets unlearning, while a separate adversarial-example method slows inference 1.5–5× at test time.Source: §5 · p. 10
• Existing online-poisoning work does not account for attackers requesting erasure of their data.Source: §5 · p. 10
• The paper uses ℓp perturbation constraints common in adversarial examples, while noting they may fail to capture perceptual distortion and that alternative constraints could enhance the attack.Source: §5 · p. 10

6 Discussion

• The attack succeeds across broad settings and can significantly undo unlearning’s advantages over full retraining, motivating theory that accounts for indistinguishability, computation, and accuracy.The authors note that a proposed “strong” unlearning approach has not, to their knowledge, been evaluated empirically, and that open problems remain.Source: §6 · p. 11
• The attack methods focus on Guo et al.’s algorithms; extending them to k-means may be harder because its cost function is non-differentiable.The authors also identify assessing slow-down attacks on future certified deep-model unlearning as an area of interest.Source: §6 · p. 11
• Avoiding retraining from scratch may still leave an attack surface if removing poisoned examples requires more computation, and indefinite indistinguishability is unclear.The authors suggest an algorithm that never retrains from scratch as a possible countermeasure, but raise these two unresolved concerns.Source: §6 · p. 11
• Filtering poisoned examples is difficult when they are small perturbations, while filtering by influence risks excluding clean examples with naturally large influence.The authors discuss anomaly detection and influence-based filtering as possible approaches.Source: §6 · p. 11
• Robustness measures such as regularization, noise, adversarial training, or more data tend to harm accuracy.These are presented as directions for making models less sensitive to individual examples.Source: §6 · p. 11

A Technical details for PGD

• The PGD solution uses backtracking line search and a projection operator, with separate subroutines for each.The appendix summarizes PGD in Algorithm 3 and its line-search and projection subroutines in Algorithms 4 and 5.Source: A Technical details for PGD · p. 14

A.1 Computing gradients

• Assuming the model optimization converges, the implicit function theorem computes gradients through the fitted model without unrolling its optimization loops.The resulting expression supports a custom gradient implementation in frameworks such as PyTorch and JAX.Source: §A.1 · p. 14

A.2 Controlling the step size

• Row-wise gradient normalization and backtracking line search address overshooting near a boundary optimizer and can yield good solutions in 10 descent steps.The line search reduces the step size until its sufficient-decrease condition is met.Source: §A.2 · p. 14, §A.3 · p. 15

A.3 Projection operator

• Dykstra’s algorithm projects onto the intersection of convex constraint sets; norm-ball projections can be implemented efficiently, including linear-time projection onto an ℓ1-ball.The projection routine iteratively applies the individual set projections until its stopping condition is met.Source: §A.3 · pp. 14–15

B Experimental details

• The appendix provides additional details about the experiments presented in Section 4.The supplied passage gives no further experimental setup or results.Source: B Experimental details · p. 15

B.1 Implementation and hardware

• Experiments used JAX 0.2.5 on an NVIDIA P100 GPU with 12GB GPU memory and 32GB CPU memory, with 100 simulations averaged.The implementation used JAX for its automatic differentiation features.Source: §B.1 · p. 15

B.2 Learning algorithm

• Both organization and attacker models used L-BFGS, capped at 1000 iterations or an ℓ∞ gradient tolerance of 10^-6; multiclass learning used one-vs-rest and inputs were ℓ2-normalized.The stopping condition is whichever of the iteration cap or gradient tolerance is reached first.Source: §B.2 · p. 15

B.3 Attacker settings

• PGD used 10 iterations with initial step size d/10, while projection used tolerance 10^-6 and at most 50 iterations.Source: §B.3 · p. 15
• The poisoned fraction varied by experiment but stayed below 1%, with enough poisoned instances to ensure only poisoned instances were unlearned.Table 7 reports the poisoned-instance counts for the Sec. 4.2 experiments.Source: §B.3 · p. 16, Table 7 · p. 16
• The default attack used the influence-norm cost and ignored model dependence on poisoned data as a trade-off between attack time and poison quality.Source: §B.3 · p. 16
• Two inequality constraints enforced valid feature ranges and bounded perturbations; by default, p=1 and r=d/20.Pixel features were constrained to [0, 1] for MNIST and Fashion-MNIST, and features to [-1, 1] for HAR.Source: §B.3 · p. 16

B.4 Organization settings

• Organization settings used epsilon=1 and delta=10^-4, with default regularization lambda=10^-3 and objective-noise magnitude sigma=10.These settings were reported to balance model accuracy and unlearning efficiency in a benign setting.Source: §B.4 · p. 16

Long-term effectiveness

• Long-term effectiveness is measured as the fraction of erasure requests that trigger retraining; higher frequency means a more effective attack.The reported frequency averages over 500 poisoned erasure requests, yielding precise estimates in most experiments where average intervals are below 500 and frequency exceeds 1.Source: C Additional results on long-term… · pp. 16–17
• The largest retrain-frequency gains occur when benign retraining would be infrequent, the regime where unlearning would normally be most effective.Estimates near zero retrain frequency are uncertain for lambda >= 10^-3.Source: C Additional results on long-term… · p. 17, Table 8 · p. 17
• Alternative cost functions, white-box versus grey-box settings, and additional datasets show similar attack-effectiveness trends.The reported results correspond to Tables 9–11.Source: C Additional results on long-term… · p. 17, Table 9 · p. 17, Table 10 · p. 18