PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Probabilistic Verification of Machine Unlearning

David Marco Sommer, Liwei Song, Sameer Wagh, Prateek Mittal

arXiv:2003.04247v2cs.CRcs.LGstat.ML

TL;DR

Individual users need a way to verify whether an MLaaS provider complied with a request to remove their data from model training. The paper formalizes that verification as hypothesis testing and proposes a backdoor-based mechanism. Across the reported evaluation, the method supports high-confidence verification, including under an adaptive server using backdoor defenses.

  • Problem

    Individual MLaaS users lack concrete mechanisms to verify whether providers complied with requests to exclude their data from model training.

    Source: §1 · p. 1

  • Method

    The paper formalizes compliance verification as a hypothesis test and uses individually chosen data backdoors as traces for users to test after requesting deletion.

    Source: §1 · p. 2

  • Results

    With 50% poisoned samples and 30 test queries, both false positive and false negative values are below 10^-3, and the method retains high-confidence verification against an adaptive server using backdoor defenses.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The work provides a mathematical foundation for quantitatively verifying machine unlearning from an individual-user perspective.

    Source: §9 · p. 14

    Conflicting backdoor patterns can cause the approach to fail for some users, and new backdoor defenses could be detrimental to it.

    Source: §7.3 · p. 13

Abstract

from arXiv · show

The right to be forgotten, also known as the right to erasure, is the right of individuals to have their data erased from an entity storing it. The status of this long held notion was legally solidified recently by the General Data Protection Regulation (GDPR) in the European Union. Consequently, there is a need for mechanisms whereby users can verify if service providers comply with their deletion requests. In this work, we take the first step in proposing a formal framework to study the design of such verification mechanisms for data deletion requests -- also known as machine unlearning -- in the context of systems that provide machine learning as a service (MLaaS). Our framework allows the rigorous quantification of any verification mechanism based on standard hypothesis testing. Furthermore, we propose a novel backdoor-based verification mechanism and demonstrate its effectiveness in certifying data deletion with high confidence, thus providing a basis for quantitatively inferring machine unlearning. We evaluate our approach over a range of network architectures such as multi-layer perceptrons (MLP), convolutional neural networks (CNN), residual networks (ResNet), and long short-term memory (LSTM), as well as over 5 different datasets. We demonstrate that our approach has minimal effect on the ML service's accuracy but provides high confidence verification of unlearning. Our proposed mechanism works even if only a handful of users employ our system to ascertain compliance with data deletion requests. In particular, with just 5% of users participating, modifying half their data with a backdoor, and with merely 30 test queries, our verification mechanism has both false positive and false negative ratios below $10^{-3}$. We also show the effectiveness of our approach by testing it against an adaptive adversary that uses a state-of-the-art backdoor defense method.

1 Introduction

The paper addresses the lack of mechanisms for individual MLaaS users to verify compliance with data-deletion requests, and formalizes verification as hypothesis testing. It proposes backdoor-based verification and evaluates the approach across datasets and architectures, reporting high-confidence results even against an adaptive server using backdoor defenses.

Motivation

  • Users lack concrete ways to verify deletion requests, while prior unlearning work assumes an honest server and does not provide verification mechanisms.Here, deletion means excluding a user's data from the model-training procedure, not proving physical erasure from storage.Source: §1 · p. 1

Proposed Mechanism

  • Users independently add randomly selected triggers and target labels to some training samples, then test their own trigger's success rate after requesting deletion.A low success rate indicates that the model was not trained on the user's poisoned data and signals compliance within the paper's definition of deletion.Source: §1 · p. 2

Experimental Evaluation

  • With 50% poisoned samples and 30 test queries, the mechanism achieves both false-positive and false-negative values below 10^-3; an adaptive malicious server lowers backdoor success rates, especially at low poisoning ratios, but rates remain significant for high-confidence unlearning validation.Source: §1 · p. 2

Formalizing Machine Unlearning

  • The framework models deletion compliance as a hypothesis test and uses test power to quantify a user's confidence that the provider complied.It is designed for individual users in a wide range of MLaaS systems.Source: §1 · pp. 1–2

Using Data Backdoors for Verified Machine Unlearning

  • The paper develops a backdoor-based mechanism for probabilistically verifying unlearning and analyzes how many test samples are needed for high-confidence verification.It also gives individual users methods to estimate parameters and statistics needed to detect non-compliance.Source: §1 · p. 2

Experimental Evaluation

  • The evaluation studies five datasets, including image and text classification, and four architectures: MLP, CNN, ResNet, and LSTM.The datasets are EMNIST, FEMNIST, CIFAR10, ImageNet, and AG News.Source: §1 · p. 2

2 Neural Network Preliminaries

This section introduces neural-network architectures and describes backdoor attacks and defenses as background for the paper's approach.

2 Neural Network Preliminaries

  • Neural networks learn task parameters iteratively using mini-batches and stochastic gradient descent; the section names MLPs, CNNs, ResNets, and LSTMs as architectures used in different applications.The text associates residual networks with computer vision and LSTMs with natural-language-processing applications.Source: §2 · p. 3

2.1 Backdoor Attacks and Defenses

  • Backdoor attacks train a model to associate a trigger in an input with a target label while retaining normal predictions on clean inputs.The paper builds on Gu et al. and considers a multi-user setting in which interested users can employ individual backdoors.Source: §2.1 · p. 3
  • Neural Cleanse searches for candidate triggers for each label and treats a sufficiently small reverse-engineered pattern as evidence of a backdoor.Its mitigation approaches include filtering similar test samples, pruning neurons, and fine-tuning with reversed triggers and clean samples.Source: §2.1 · p. 3

3 Framework for Machine Unlearning

The framework treats verification of machine unlearning in MLaaS as a hypothesis-testing problem. Users can use private backdoors and model predictions to test whether a server retained data they were asked to delete.

3 Framework for Machine Unlearning

  • The framework casts deletion verification as a hypothesis test between a server that deletes requested data and one that does not.It uses the test’s power to quantify verification effectiveness.Source: §3 · p. 3, §3.1 · p. 4

3.2 Our Approach

  • Privacy enthusiasts locally poison part of their data with private backdoors, then use model predictions on backdoored samples to test for retained data.The backdoor success rate should be high when the model trained on the user’s poisoned data and low after deletion; the framework does not require all users to participate.Source: §3 · pp. 3–4, §3.2 · pp. 4–5

3 Framework for Machine Unlearning

  • The approach assumes users can manipulate training data and have enough data for poisoning; its scope is deletion from the exposed model, not other provider resources.It requires black-box prediction access and that the provider cannot identify which user is querying.Source: §3 · p. 4

3.1 Hypothesis Testing

  • The test defines H0 as deletion and H1 as non-deletion; α measures false accusations, while β measures missed non-deletion.For a fixed number of queries, α and β cannot both be reduced, so the framework fixes acceptable α and uses 1−β as effectiveness.Source: §3.1 · p. 4

3.2 Our Approach

  • Verification confidence increases with the number of backdoored test samples, provided the success rates for deleted and undeleted data remain distinguishable.The corresponding rates are q for deleted data and p for undeleted data, with q lower than p.Source: §3.2 · p. 5

4 Theoretical Analysis

The section quantifies unlearning-verification confidence through a hypothesis test and derives a closed-form expression for it. It also gives bounds for cases where users estimate system parameters from few samples.

4.1 Formal Hypothesis Testing

  • Under H0, the measured backdoor success rate approaches q; under H1, it approaches p, and a threshold determines the decision and its Type I and II errors.The confidence metric is 1 − β for a chosen acceptable Type I error α.Source: §4.1 · p. 6, §4 · p. 6

4.2 Estimating Deletion Confidence ρA,α(s,n)

  • Theorem 1 gives a closed-form expression for deletion confidence as a function of system parameters.The expression computes backdoor success probability; the derivation is deferred to Appendix A.Source: §4.2 · pp. 6–7

4.3 Relaxation to Single User Perspective

  • With estimated rates, overestimating q and underestimating p yields a lower bound on confidence as their separation increases, because binomial overlap decreases.This addresses users estimating the rates from few samples.Source: §4.3 · p. 7
  • Users can alternatively assign priors to p and q and compute confidence as its expectation over possible parameter values.The estimates are conditioned on the observed rates and sample count.Source: §4.3 · p. 7

5 Evaluation

The evaluation tests verification across five datasets and four architectures, including non-adaptive and adaptive servers. Results report applicability beyond image data and continued, though slightly reduced, detection under Neural Cleanse.

5 Evaluation

  • The evaluation reports affirmative results for generalization to complex and non-image datasets, while detection accuracy is slightly reduced against a state-of-the-art backdoor defense.Figure 3 presents non-adaptive results; Figure 4 presents adaptive-server results, omitting AG News because Neural Cleanse is not applicable to non-continuous data.Source: §5 · p. 7, Figure 3 · p. 9, Figure 4 · p. 10

5.1 Experimental Set-up

  • Setup spans five datasets and four architectures; outside ImageNet, held-out 20% of users represent compliant deletions, while test-split users represent data retained in training.The experiments also compare a non-adaptive provider with one using Neural Cleanse.Source: §5.1 · pp. 7–8

5.2 Results for the Non-Adaptive Server

  • Around 10%: EMNIST deleted users’ backdoor accuracy stays near random-guess accuracy, while higher poison ratios widen the p–q gap and lower Type-II error.Poison ratios up to 90% have negligible impact on clean test accuracy.Source: §5.2 · pp. 9–10
  • For non-adaptive servers, AG News undeleted-user accuracy is around 100% above 30% poisoning, while deleted-user accuracy stays near 25%; verification also works for arbitrary testing-user fractions.With more EMNIST users testing, some deleted users have high success rates from backdoor collisions, although the average rises only minimally.Source: §5.2 · p. 11

5.3 Results for the Adaptive Server

  • Neural Cleanse reduces backdoor success, but a 50% poison ratio still leaves undeleted users with higher attack accuracy than deleted users, allowing high-confidence verification with enough queries.The defense has limited performance on more complex image datasets; its performance also weakens as more users test for deletion.Source: §5.3 · p. 11

6 Heterogeneity Across Individual Users

Individual users usually distinguish deleted from undeleted data, but similar backdoors can leave some deleted users with high attack accuracy. The section describes cooperation as a way to reduce false negatives.

6 Heterogeneity Across Individual Users

  • Almost all undeleted users have backdoor attack accuracy close to 100%, while several deleted users also have high accuracy.Figure 5 shows the distributions for different datasets with fuser = 0.05 and fdata = 50%.Source: §6 · p. 11, Figure 5 · p. 12
  • Similar triggers and target labels among users can give deleted users high attack accuracy, risking a false accusation that the server retained their data.The authors note that CNNs and ResNets can behave similarly on triggers related by rotation, translation, or transformation.Source: §6 · p. 11
  • With multiple users sharing estimated backdoor success rates, false negatives can be greatly reduced by accumulating their p and q values for hypothesis testing.The accumulated test sample count is c · n when c users each test n backdoored samples.Source: §6 · p. 12
  • Multiple triggers with different target labels can improve reliability by using the lowest success rate, provided at least one trigger has low accuracy for a deleted user.Combining the method with user-level membership inference is proposed as future work.Source: §6 · p. 12

7 Discussion

The discussion considers server-side uses, backdoor defenses, and constraints on the verification approach. Its scope depends on users being able to create workable backdoors and on defenses not fully eliminating them.

7.1 Server-Side Usefulness of our Mechanism

  • An honest server can use the mechanism to check whether its deletion pipeline is bug-free and to measure deletion approaches without strict guarantees [10] [11].For production systems that avoid backdoors in future predictions, the target can be an outlier label.Source: §7.1 · p. 12

7.2 Other Backdoor Attacks and Defenses

  • Neural Cleanse has only limited impact in the tested setting: undeleted users retain much higher backdoor success rates than deleted users, so verification still works.The mechanism can extend to other backdoor methods [29].Source: §7.2 · p. 12
  • A perfect defense that fully mitigates backdoors would stop this approach, though users may detect defenses from low pre-deletion attack accuracy and switch methods.Suggested alternatives include stealthier backdoors [29] or membership inference.Source: §7.2 · p. 12
  • Differential privacy may require user-level noise when users poison multiple samples, which the authors say can considerably lower general accuracy; colluding users can bypass single-user guarantees.The authors also describe per-user protection as requiring enormous databases and being applied by the largest tech companies.Source: §7.2 · pp. 12–13

7.3 Limitations of our Approach

  • The approach requires users to modify data and enough samples: it may not work when data are too simple for a backdoor without reducing benign accuracy, and needs at least a few tens of samples.Users can aggregate tests, generate samples, or switch to membership inference.Source: §7.3 · p. 13
  • Similar or conflicting backdoors can make verification fail for some users; close or overlapping p and q values can reveal the issue.The authors recommend checking soon after the deletion request for time-related overwriting, or limiting privacy enthusiasts or expanding the backdoor space when there are too many users.Source: §7.3 · p. 13
  • New defenses could harm the approach, and reliable backdoor defense remains an open problem; for AG News, no satisfactory defense methods are known.Users may detect defenses and adapt their strategy.Source: §7.3 · p. 13

8 Related Work

Prior unlearning work includes efficient retraining, parameter updates, and methods aimed at removing a model’s dependence on deleted data. Verification approaches include trusted computation, inference attacks, and model watermarking, each with different assumptions or scope.

8 Related Work

  • To reduce deletion costs, prior methods use intermediate training-data sums, quantized or recursively partitioned k-means, and disjoint shards that limit retraining [9].Garg et al. study the related but orthogonal question of what deleting user data means theoretically.Source: §8 · p. 13
  • Other approaches update parameters to approximate retraining through influence functions [10] or noise [46], or remove an entire class with a linear transformation [11].The passage notes that class-removal methods do not guarantee that information about the deleted class is absent from the updated model.Source: §8 · p. 13
  • Verifiable computation can attest processing steps using secure processors, trusted platform modules, or zero-knowledge proofs, but entails practicality and model-secrecy limitations.The passage cites computational overhead, trusted-party assumptions, and attacks on these systems.Source: §8 · p. 13
  • Membership-inference methods [16] infer sample- or user-level training membership, but applying them here requires similar auxiliary data, shadow models, and target-model architecture knowledge.The comparison states that the backdoor-based approach does not require those assumptions.Source: §8 · pp. 13–14
  • Dataset watermarking [56] traces image datasets with feature-altering perturbations, whereas this paper assigns personal backdoors in a multi-user setting; Adi et al. also use backdoors to watermark models.Source: §8 · p. 14

9 Conclusion

The paper formalizes probabilistic verification of machine unlearning and proposes a backdoor-based mechanism for users to check deletion compliance. Its evaluation spans multiple architectures and datasets, and the authors present the framework as a quantitative foundation for verification.

9 Conclusion

  • The paper provides a quantitative framework and backdoor-based mechanism for users to verify deletion compliance, evaluated across network architectures and datasets.Source: §9 · p. 14

A Proof of Theorem 1

The proof models deletion verification as distinguishing two scaled binomial distributions and derives the test's confidence from its Type I and Type II errors. More samples concentrate the distributions around their means, reducing both errors.

A Proof of Theorem 1

  • For a specified Type I error α, the procedure finds the threshold tα, computes the corresponding Type II error β, and derives ρA,α(s,n).The threshold is obtained by inverting the Type I error relation before computing β.Source: A Proof of Theorem 1 · pp. 16–17
  • The test assumes prediction order is immaterial and predictions are processed independently, so n observations can be modeled with Testn,r.Testn,r returns n binary outcomes with success probability r.Source: A Proof of Theorem 1 · p. 17
  • The test compares scaled binomial distributions with success probability q under H0 (data deleted) and p under H1 (data not deleted).The measured backdoor success rate has standard deviation shrinking as O(1/√n).Source: A Proof of Theorem 1 · p. 17
  • As n increases, the distributions concentrate around their means, reducing the overlap and therefore both Type I and Type II error probabilities.The proof applies Lemma 1 to the two hypotheses' scaled binomial distributions.Source: A Proof of Theorem 1 · p. 17
  • ρA,α(s,n) = 1 − β gives the user's confidence that the server did not delete the data as requested.A high value indicates high confidence that the server did not follow the deletion request.Source: A Proof of Theorem 1 · p. 18

B Evaluation Datasets and Architectures

The evaluation uses four image datasets and one text-classification dataset with MLP, CNN, ResNet, and LSTM architectures. The appendix specifies dataset splits, model setups, and clean-data accuracy for several of these evaluations.

B Evaluation Datasets and Architectures

  • The evaluation covers EMNIST, FEMNIST, CIFAR10, ImageNet, and AG News, using MLP, CNN, ResNet, and LSTM architectures.The datasets include four image-classification datasets and one text-classification dataset.Source: B Evaluation Datasets and Architectures · p. 18
  • EMNIST uses 1,000 IID users with 280 samples each and a three-layer MLP; its clean-data test accuracy is 98.99%.The digits dataset has 10 classes, and the backdoor sets four randomly selected pixels to 1.Source: B Evaluation Datasets and Architectures · p. 18
  • FEMNIST uses 3,383 users and a CNN; its clean-data test accuracy is 99.45%.Its 382,705 digit samples are distributed across users, and the backdoor pixels are set to 0.Source: B Evaluation Datasets and Architectures · p. 18
  • CIFAR10 uses 500 IID users with 120 samples each and a ResNet, achieving 91.03% clean-data test accuracy.The model is trained for 200 epochs, with standard augmentation such as shifts and flips.Source: B Evaluation Datasets and Architectures · p. 18
  • ImageNet evaluation uses a pretrained ResNet50 with transfer learning; its clean-data test accuracy is 76.13%.The dataset contains 1,331,168 images across 1,000 labels, with 23 images removed for incompatible JPEG color schemes.Source: B Evaluation Datasets and Architectures · p. 18
  • AG News uses an LSTM to classify four categories from titles and descriptions, achieving 91.03% clean-data test accuracy.The final dataset has 549,714 samples from 580 users after filtering short articles and users with few samples.Source: B Evaluation Datasets and Architectures · p. 18

C Number of Users Sustainable

The section examines how many users can choose distinct backdoor patterns before collisions harm system performance. It frames pattern separation as a coding-theory problem and uses bounds to assess sustainable user counts.

C Number of Users Sustainable

  • A finite space of backdoor patterns means similar choices by multiple users can cause inaccuracies, motivating bounds on sustainable user counts.The concern is collisions between patterns that are similar but not identical, since the model may tolerate small deviations.Source: C Number of Users Sustainable · p. 18
  • With more measured samples, the distributions concentrate around their means, reducing both Type I and Type II errors in distinguishing H0 from H1.The figure uses q = 0.1 and p = 0.8; curve heights are adjusted for demonstration.Source: Figure 6 · p. 19
  • For binary images of size n with w triggered pixels, the example treats patterns differing in fewer than d values as interfering; EMNIST uses n = 784, w = 4, and d = 2.In this example, patterns sharing three of four pixels interfere with one another's classification.Source: C Number of Users Sustainable · p. 19
  • The maximum number of sufficiently dissimilar constant-weight patterns is mapped to the coding-theory quantity A(n,d,w), whose exact computation is an open problem.The paper uses existing bounds and exact values for simple cases such as its EMNIST example.Source: C Number of Users Sustainable · p. 19
  • A birthday-paradox analysis bounds the user count to keep backdoor-collision probability low, while CNNs complicate the analysis because convolution layers share neighboring-pixel weights.The CNN qualification concerns the coding analysis for image backdoors.Source: C Number of Users Sustainable · p. 19

Related papers

Loading 2003.04247v2…