PaperlayerView exact revision on arXiv

Source-linked AI summary

Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning

Ji Gao, Sanjam Garg, Mohammad Mahmoody, Prashant Nalini Vasudevan

arXiv:2202.03460v1cs.LGcs.CR

TL;DR

Machine learning privacy attacks traditionally examine static models, but unlearning gives an adversary access to models before and after deletion, potentially exposing the removed example. The paper formalizes deletion inference and reconstruction and presents attacks across learning tasks; it also shows that deletion-compliance variants capture those attacks and can support provable prevention.

  • Problem

    In unlearning, an adversary may compare models before and after a deletion, raising the question of whether that access exposes the removed example.

    Source: §1 · p. 3

  • Method

    The paper formally studies unlearning privacy through cryptography- and differential-privacy-inspired definitions and deletion inference and reconstruction attacks.

    Source: §1.1 · pp. 3–4

  • Results

    The attacks distinguish deleted examples using access to both models across regression and classification settings, while deletion-compliance variants capture the studied attacks.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    The paper states that differential privacy with strong parameters can prevent all its attacks, though it comes with efficiency and sample-complexity costs.

    Source: §1.1 · p. 5

    The security games target deletion of a random example and give attackers minimal knowledge of the data distribution, unlike real adversaries with specific targets and more auxiliary information.

    Source: §1.1 · p. 6

Abstract

from arXiv · show

Privacy attacks on machine learning models aim to identify the data that is used to train such models. Such attacks, traditionally, are studied on static models that are trained once and are accessible by the adversary. Motivated to meet new legal requirements, many machine learning methods are recently extended to support machine unlearning, i.e., updating models as if certain examples are removed from their training sets, and meet new legal requirements. However, privacy attacks could potentially become more devastating in this new setting, since an attacker could now access both the original model before deletion and the new model after the deletion. In fact, the very act of deletion might make the deleted record more vulnerable to privacy attacks. Inspired by cryptographic definitions and the differential privacy framework, we formally study privacy implications of machine unlearning. We formalize (various forms of) deletion inference and deletion reconstruction attacks, in which the adversary aims to either identify which record is deleted or to reconstruct (perhaps part of) the deleted records. We then present successful deletion inference and reconstruction attacks for a variety of machine learning models and tasks such as classification, regression, and language models. Finally, we show that our attacks would provably be precluded if the schemes satisfy (variants of) Deletion Compliance (Garg, Goldwasser, and Vasudevan, Eurocrypt' 20).

1 Introduction

Machine unlearning changes privacy attacks from a static-model setting: an adversary may compare models before and after a deletion, potentially exposing the deleted record. The paper formalizes deletion inference and reconstruction, studies attacks across learning tasks, and relates them to deletion compliance.

1 Introduction

  • Deletion requests update a trained model to approximate retraining without the requested example, while access to both pre- and post-deletion models may expose the deleted record.The introduction illustrates this with two model-revealed sums whose difference recovers the deleted vector.Source: §1 · p. 3

1.1 Our Contribution

  • Attacks target classification, regression, and language models, including instance reconstruction with 1-nearest neighbor and complete sentence recovery from simple language models.For uniformly distributed binary instances, the paper reports that 1-nearest neighbor can reveal virtually all deleted-instance features; it also studies similar image attacks on Omniglot and label attacks.Source: §1.1 · pp. 4–5
  • The paper formalizes deletion inference and reconstruction: adversaries distinguish deleted from non-deleted examples or recover features of deleted examples.The security games assume ideal deletion by fresh retraining, with adversary access to the original model followed by the updated model.Source: §1.1 · p. 4
  • Variants of Deletion Compliance capture the paper’s attacks, including weaker forms that allow deletion itself to be known or expose only black-box model access.The paper states that differential privacy with strong parameters can prevent all its attacks, while imposing efficiency and sample-complexity costs.Source: §1.1 · p. 5

1.2 Related Work

  • The work presents varied reconstruction attacks alongside deletion inference, uses simple output statistics rather than sophisticated learning algorithms, and formally connects privacy definitions to deletion compliance [GGV20], implying differential privacy can prevent any possible deletion-inference attack.It studies attacks aimed at reconstructing instances or inferring instances or their labels, including using instance knowledge to better approximate labels.Source: §1.2 · pp. 6–7

2 Preliminaries

The preliminaries establish notation for data, models, losses, and risk, then define ideal deletion as fresh retraining on the dataset with the specified example removed.

Basic Notation

  • The notation defines instance and label spaces, data distributions, examples, hypothesis classes, and sampling distributions for datasets that need not be iid.For classification, the default label space is {0, 1}; for regression, labels are real numbers.Source: §2 · p. 7

Loss, risk, and learning

  • Loss measures prediction error, population risk averages loss over the data distribution, and empirical risk averages it over the training set.Empirical Risk Minimization outputs a model minimizing empirical loss.Source: §2 · p. 7

Deletion

  • Ideal deletion removes an example by retraining on the remaining set with fresh learner randomness, and may require the training set or an auxiliary data structure.If the requested example is not in the training set, deletion instead returns a fresh retraining on that set.Source: §2 · p. 7

3 Deletion Inference Attacks

This section formalizes deletion inference as identifying a removed candidate from models before and after deletion, then develops and evaluates attacks across tasks and models. It also examines how a near-certain membership-inference oracle can enable near-certain deletion inference and compares deletion-inference attacks with membership-inference baselines on VGG models and CIFAR datasets.

3.1 Threat Model

  • The threat model gives the adversary two candidate examples and oracle access before and after deletion, and asks it to identify which candidate was removed.Variants reveal only instances or labels, and successful instance- or label-only inference is stronger evidence of vulnerability than the default full-example game because the adversary has less information.Source: §3.1 · pp. 7–8

3.1.1 Reducing Deletion Inference to Membership Inference

  • A black-box reduction to membership inference queries the post-deletion model on both candidates and combines the membership predictions to infer the deleted example.The candidates are promised to belong to the original training set, so the reduction need not query the original model.Source: §3.1.1 · p. 9

3.2 Our Baseline Deletion Inference Attacks

  • Del-Inf-Exm identifies the candidate with the larger loss increase between the original and deleted models, while label-free Del-Inf-Ins selects the instance with the larger output change.For ERM, the paper relates successful example inference to negative and concentrated loss increases among examples that remain in the dataset; experiments support these conditions in many natural scenarios. Del-Inf-Exm generalizes memorization from 0-1 loss to general losses [Fel20].Source: §3.2 · pp. 10–11

3.3 Experiments: Deletion Inference Attack on Regression

  • In regression experiments, the deletion-inference adversaries achieve more than 90% success probability in most cases.Experiments use Boston and Diabetes datasets, full retraining after deletion, and average success over 1,000 repetitions.Source: §3.3 · p. 12, Table 2 · p. 12

3.4 Experiments: Deletion Inference Attacks on Classification

  • On classification datasets, Del-Inf-Exm has noticeably higher success rates than Del-Inf-Ins.The experiments provide the adversary with confidence distributions and use negative log likelihood for Del-Inf-Exm.Source: §3.4 · pp. 12–13, Table 3 · p. 13

3.5 Experiments: Attacking Large Datasets and Models

  • The attacks correctly predict most deletions in deep-learning models, including batch deletions, and the authors report stronger results than reductions to membership inference [SSSS17].Del-Inf-Ins does not require the target label, while the membership-inference baseline requires the target label and many queries or auxiliary examples; the baseline reduction can call its membership-inference adversary multiple times.Source: §3.5 · pp. 13–14, Figure 1 · p. 14
  • Figure 2 plots Del-Inf-Exm and Del-Inf-Ins success probabilities across VGG models trained with different example counts on CIFAR-10 and CIFAR-100, against two membership-inference-reduction baselines [SSSS17].The caption gives the comparison scope but no numerical success probabilities.Source: Figure 2 · p. 15
  • A membership-inference oracle that wins its game with probability close to 1 can enable deletion inference with probability close to 1.The passage says the reduction itself is powerful enough to achieve this.Source: §3.5 · p. 15

4 Deletion Reconstruction

The section formalizes deletion reconstruction attacks that use pre- and post-deletion models to recover deleted instances or labels, with attacks and analyses for nearest-neighbor models, language models, and classification labels. It also examines known-instance label reconstruction by moving post-deletion predictions toward the original predictions.

4.1 Threat Model

  • A (ρ, ε)-successful PPT reconstruction adversary implies (ρ−δ)-insecurity against deletion inference over S_n, provided sampled examples e0 and e1 have distance >2ε with probability at least 1−δ.Source: §4.1 · p. 16

4.2 Deletion Reconstruction of Instances for Nearest Neighbor

  • For 1-nearest-neighbor models, Del-Ins-Rec uses points whose predictions change after deletion and takes a coordinate-wise majority to estimate the deleted instance.Changed predictions are treated as points in the deleted example’s Voronoi cell; experiments indicate the approach also works with repeated labels, where access to both models is needed to locate the vanished cell.Source: §4.2 · pp. 16–17

4.2.1 Theoretical Analysis for Uniform Singletons

  • Under uniform binary instances and unique labels, the nearest-neighbor reconstruction attack does not converge to an incorrect value for any instance coordinate.The theoretical analysis uses non-negative correlations between each Voronoi cell’s coordinates and its center.Source: §4.2.1 · pp. 17–18

4.2.2 Experiments: Deleted Image Reconstruction for 1-NN

  • 40 of 100 Omniglot images were reconstructed; 35 reconstructions received the correct label from the nearest-neighbor classifier, compared with 1 for the non-deletion baseline.The non-deletion attack gave no meaningful result in this setting; Figure 3 shows 33 of the 40 reconstructed images alongside the baseline and targets.Source: §4.2.2 · p. 19, Figure 3 · p. 19

4.2.3 Experiments: Deleted Sentence Reconstruction for Language Models

  • 99% F1 scores on bigram and trigram models, and 97% of sequences reconstructed with correct words and order on trigram; unigram models cannot recover word order.The attack traces probability changes caused by deletion to reconstruct deleted sequences longer than the model's N-gram size; without deletion, aggregated N-gram probabilities make specific sequences hard to recover.Source: §4.2.3 · p. 21, Table 4 · p. 21

4.3 Deleted Label Reconstruction

  • Deleted-label reconstruction succeeded with probability above 90% on Iris and Wine and above 75% on Breast Cancer, using logistic regression and K-Nearest Neighbor models.The attack relies on the intuition that deleting an example tends to shift predictions away from its class; the experiments cover three classification datasets.Source: §4.3 · pp. 21–22, Table 5 · p. 22

4.3.1 Known-Instance Label Reconstruction

  • With the deleted instance known, an attacker can sometimes estimate its label more accurately than either model predicts, using the outputs of both models.The proposed Ins-Rev-Lbl-Rec attack estimates the label from the pre- and post-deletion model outputs.Source: §4.3.1 · p. 22
  • Because the deleted sample’s mean-squared error increases after deletion, moving the post-deletion prediction toward the original prediction can bring it closer to the true label.The attacker can empirically estimate a suitable positive λ using a similarly sized dataset sampled independently.Source: §4.3.1 · p. 22
  • The experiments used linear regression on Boston Housing Price and diabetes, comparing the adversary’s label error with the better of the original and deletion-model prediction errors.The Boston Housing Price Dataset is cited as, and the diabetes dataset as [EHJ+04].Source: §4.3.1 · p. 23
  • A suitable λ reduced estimated reconstruction loss by around 70% on each dataset.The result is reported for linear regression experiments on the Boston Housing Price and diabetes datasets.Source: Table 6 · p. 23, §4.3.1 · p. 23

5 Weak Deletion Compliance

The section defines weak deletion compliance to hide which of two candidate records was deleted, then proves that this guarantee precludes deletion inference under a stated parameter relationship. The definition is weaker than Garg, Goldwasser, and Vasudevan’s deletion compliance, but is shown to capture the attacks studied earlier.

Compliance and attacks

  • The section states that even a weaker variant of [GGV20] deletion compliance prevents the attacks studied in Sections 3 and 4.The strong [GGV20] definition instead compares real and ideal worlds where the deletion requester cannot communicate with the data collector.Source: §5 · pp. 23, 26

Components and interaction

  • The framework models a data collector, a deletion requester who stores two candidates and deletes one, and an environment interested in identifying the deleted record.The collector accepts Add, Del, and Eval instructions, with Eval querying its current model.Source: §5 · pp. 23–24

Definition 5.1

  • Weak deletion compliance requires that no PPT environment distinguish which of two candidate records was deleted with advantage greater than 𝜀.For up to k deletions, the guarantee is restricted to executions with at most k−1 deletion requests.Source: §5 · p. 24

Comparison with [GGV20]

  • Unlike the [GGV20] definition, weak deletion compliance does not aim to hide that a deletion occurred; it aims to hide which record was deleted.It is weaker than [GGV20] deletion compliance but is presented as more general and stronger than Definition 3.1 for hiding the deleted record among training records.Source: §5 · pp. 24–25

Theorem 5.2

  • If DatCol is (2𝜀−1)-deletion compliant against PPT adversaries with oracle access to D, then (Learn, Del) is 𝜀-secure against deletion inference.The proof uses a reduction from an inference adversary to an environment that distinguishes the two deletion-request worlds.Source: §5 · pp. 25–26

A Hyperparameters of Models

The appendix lists model hyperparameters used in the experiments, including architectures, optimization choices, and default Scikit-learn settings.

MLP

  • The MLP uses two hidden layers: sizes (20, 2) for regression and (20, 10) for classification, with LBFGS training for 200 epochs.The text attributes the larger classification output layer to the greater number of output neurons in classification tasks.Source: A Hyperparameters of Models · p. 31

SVM

Decision tree and random forest

  • The decision tree uses Scikit-learn defaults, Gini impurity, and no tree-size limit; the random forest uses 10 such trees.The forest uses the decision-tree classifier’s stated hyperparameters.Source: A Hyperparameters of Models · p. 31

Regression models

Related papers

Loading 2202.03460v1…