Verification of Machine Unlearning is Fragile

1. Problem Statement

With the rise of data privacy regulations (e.g., GDPR, CCPA), data owners have the right to request the removal of their data from trained machine learning (ML) models, a process known as Machine Unlearning (MUL). However, current MUL techniques are often "black boxes" to data owners, who cannot verify if the data was truly removed. To address this, verification strategies (specifically Backdoor Verification and Reproducing Verification) have been proposed to allow data owners to audit the unlearning process.

The core research question of this paper is: Can dishonest model providers circumvent these verification strategies while retaining the information of the supposedly unlearned data? The authors argue that current understanding of the safety of MUL verification is nascent and potentially flawed.

2. Methodology

The authors propose a threat model where the model provider is an adversary aiming to:

1. Satisfy existing verification protocols (Backdoor and Reproducing).
2. Preserve the utility of the model (including the information from the unlearned data).
3. Minimize computational costs compared to honest retraining.

To achieve this, they categorize current verification strategies into two types and propose two corresponding Adversarial Unlearning Methods:

A. Verification Types

1. Backdoor Verification: Data owners inject "backdoor" poisoned data (triggers) into the training set. If the model is honestly unlearned, it should no longer respond to these triggers. If the provider cheats, the model still predicts the poisoned label.
2. Reproducing Verification: The provider must supply a Proof of Retraining (PoRT), a record of the training trajectory (parameters, data batches, update functions) allowing the verifier to reproduce the steps. The proof must satisfy:
   • Removable: No unlearned data ($D_u$) is used in the batches.
   • Reproducible: The recorded updates mathematically match the resulting model parameters within a tolerance $\epsilon$.

B. Adversarial Method 1: Retraining-based (The "Retraining" Attack)

• Goal: Circumvent both Backdoor and Reproducing verification with zero error ($\epsilon = 0$).
• Mechanism: Instead of using the unlearned data $D_u$, the adversary selects mini-batches from the retained data ($D \setminus D_u$) that induce gradient updates similar to those that would have been produced by $D_u$.
  • Strategy: For a batch containing unlearned data, the adversary replaces the unlearned samples with their class-wise nearest neighbors from the retained set (or uses random sampling to find a batch with a similar gradient).
  • Result: The model is updated using only retained data, satisfying the "Removable" property. However, because the gradients are nearly identical, the model effectively "learns" from the unlearned data's influence without explicitly seeing it.
• Backdoor Evasion: By using clean data from the target class to replace poisoned backdoor data, the model learns the correct class mapping rather than the poisoned trigger mapping, causing the backdoor trigger to fail (appearing as if the data was unlearned).

C. Adversarial Method 2: Forging-based (The "Forging" Attack)

• Goal: Circumvent Reproducing verification with a small error threshold ($\epsilon > 0$) while being computationally efficient.
• Mechanism: Instead of retraining, the adversary forges the PoRT directly from the original Proof of Training (PoT).
  • Strategy: A "forging map" modifies the original training trajectory. For batches containing unlearned data, it replaces them with retained data (using the nearest neighbor strategy). For batches without unlearned data, it slightly perturbs the model parameters using a small learning rate to avoid detection of identical parameters.
  • Result: This generates a valid PoRT that satisfies the reproducibility check within a tolerance $\epsilon$, but the final model remains heavily dependent on the original training (including unlearned data).

3. Key Contributions

1. Novel Adversarial Frameworks: The paper introduces two adversarial unlearning processes (Retraining-based and Forging-based) that successfully bypass current state-of-the-art verification strategies.
2. Theoretical Guarantees:
   • Proved that the Retraining-based method satisfies the Reproducing verification with $\epsilon=0$.
   • Proved that the model utility remains high (close to the original model) and that the method can theoretically reach a neighborhood of the optimum.
   • Provided bounds on the verification error for the Forging-based method.
3. Empirical Validation: Extensive experiments on real-world datasets (MNIST, CIFAR-10, SVHN) demonstrate that:
   • The adversarial methods pass Backdoor verification (Type II error rates are near 1.0 for the Retraining method).
   • The Forging method passes Reproducing verification with low error thresholds.
   • The adversarial methods preserve model utility (F1-scores) comparable to or better than naive retraining, especially in class-imbalanced settings.
   • The Forging method offers significant computational speedups over full retraining.

4. Experimental Results

• Verification Evasion:
  • Retraining-based: Achieved a Type II error probability of ~0.998 on Backdoor verification (meaning the verifier almost always believes the data was unlearned, even though it wasn't).
  • Forging-based: Successfully satisfied Reproducing verification with errors below $10^{-3}$, which is considered negligible in practice.
• Utility Preservation:
  • In class-imbalanced scenarios, the adversarial Retraining method outperformed naive retraining, maintaining higher F1-scores on the unlearned set.
  • The Forging method maintained utility almost identical to the original training.
• Efficiency:
  • The Forging method was significantly faster than naive retraining due to parallel processing capabilities.
  • The Retraining method was slightly slower than naive retraining due to the overhead of nearest-neighbor search, but faster than random sampling strategies.

5. Significance and Implications

• Fragility of Current Verification: The paper delivers a pessimistic conclusion: current MUL verification is fragile. Dishonest providers can deceive data owners into believing their data is gone while retaining the model's performance and the data's influence.
• Limitations of Existing Strategies:
  • Backdoor verification fails against the Retraining-based attack because the model learns the correct class distribution rather than the poisoned trigger.
  • Reproducing verification fails because the mathematical equivalence of gradients (via nearest neighbors) allows the adversary to mimic the unlearning process without actually removing the data's influence.
• Future Directions: The study highlights the urgent need for new verification methods that go beyond simple trajectory reproduction or backdoor triggers. It suggests that verifying approximate unlearning and detecting subtle gradient manipulations are critical next steps for ensuring data privacy compliance.

In summary, this paper exposes a critical security gap in the emerging field of Machine Unlearning, demonstrating that without more robust verification mechanisms, the "Right to be Forgotten" can be easily circumvented by malicious model providers.