Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerable

[Response to Weaknesses]

We take the position that security assurances should be based on minimal assumptions. Here, we view the assumption that an attacker who has API access to the model does -not- have access to model parameters to be dangerously strong. Consider for example a d dimensional linear model, as we study initially in our work. Just from query access, an attacker can recover the model parameters by querying the model on d linearly independent points and solving a system of linear equations. This requires no knowledge of the data distribution. So, there is no meaningful difference between white box and black box access in such scenarios.

What about for more complex models? Even there the boundary between white-box and black-box access has been blurring. For example recent work [1] has shown that it is possible to reconstruct the embedding matrix from a production LLM model with only black-box access. And of course, open source models explicitly release parameters with each version of the model.

As for the fact that the attacker does not know the training set: first we note that the goal of a reconstruction attack is to recover data from the training set. Even for linear models, in which recovering the parameters given only black box access to the model is trivial, it is in general not possible to recover the training set from the parameters of a single linear model. To see this note that many datasets produce the same set of parameters --- linear regression parameters are e.g. invariant to rotations of the dataset For linear models, and the model can be expressed with only O(d) bits of information (after discretizing weights), whereas a dataset with n datapoints and d features requires Omega(n * d) bits to represent. For larger models, existing state of the art methods such as [2,3] rely on creating a set of samples such that the realized model parameters satisfy the KKT conditions of the loss function (the parameters minimize the loss at recovered samples). The success of these approaches requires that datasets are trained on a small number of samples (e.g. 500).

[1] Carlini, Nicholas, et al. "Stealing part of a production language model." arXiv preprint arXiv:2403.06634 (2024).

[2] Haim, Niv, et al. "Reconstructing training data from trained neural networks." Advances in Neural Information Processing Systems 35 (2022): 22911-22924.

[3] Buzaglo, Gon, et al. "Deconstructing data reconstruction: Multiclass, weight decay and general losses." Advances in Neural Information Processing Systems 36 (2024).

Re: multi-sample deletion, our approach recover an approximation of the gradient sum for all the deleted samples. A determined adversary can poison an unlearning round by requesting deletion of n-1 samples known to the adversary, and so can recover the gradient of the single unknown point from this sum. Nevertheless we agree that multi-sample recovery is an important question that our work does not address, and think this is one of the most interesting questions for future work arising from our paper.

On defenses: differential privacy guarantees compose, so given two models (from before and after a deletion) each trained with $\epsilon$-differential privacy, we have the guarantees of $2\epsilon$-differential privacy. When examples are drawn from a distribution uniform on some data domain $\mathcal{X}$, then $\epsilon \leq \Omega(\log|\mathcal{X}|) is enough to provably prevent reconstruction. More generally differential privacy bounds the advantage that an adversary has attempting to reconstruct a sample given the model parameters (compared to their success rate ``just guessing''), and so precise guarantees depend on the entropy of the data distribution (as low entropy distributions allow high rates of "reconstruction" without the adversary even needing to see the model. These are standard/generic properties of differential privacy which is why we did not devote space to it, but we are happy to elaborate in the revision.

[Response to Questions]

Unless we misunderstand, the ''baseline'' you propose could not be implemented without already knowing the private dataset: otherwise the attacker would have no way of knowing what the ``closest point to the target point'' in the private set is. Of course with knowledge of the private training set, there is nothing left to do. If we misunderstand your proposal please let us know, and we'll be happy to discuss further!

[Response to Weaknesses 1]

The assumption of having access to the training data distribution is standard throughout the membership inference literature. Because we are trying to compare the risks of data deletion to the known risks absent data deletion, we adopt the same model. In general we view this as an appropriately cautious assumption about what an attacker might know, especially when attacks are being used to assess model risk. You are right that it might sometimes be difficult for an attacker to find an appropriate sampling distribution, and understanding how much it can be relaxed is an important question in general for the entire literature on privacy attacks; but one that we view as outside the scope of this paper.

In our experiments, we assume the most commonly-used loss functions, including MSE, logistic loss, and hinge loss, and show positive results for each. Random fourier features are also widely used in areas where latency is a concern.

[Response to Weaknesses 2&3]

An important aspect of existing machine unlearning approaches is that almost all of them aim to approximate full retraining with reduced computational cost. These approximations are proposed due to the intense compute required for full retraining, especially for large neural networks and LLMs.

Our study is explicitly focused on exposing the risk present in even very simple models, such as linear regression, logistic regression, SVMs, and feature augmentation using random Fourier features. For such models, full retraining is feasible, and would be the expected solution to the data deletion problem, as computational approximations to retraining are not needed.

Full retraining for a single data deletion in linear regression is equivalent to updating the model parameters using Newton's update as we discussed in Sec. 3.2. By leveraging this concept, our attack achieves almost perfect reconstruction, and the only error source is the estimation of the Hessian matrix using public data. For more complex models, a number of popular unlearning methods approximate full retraining by taking a Newton update. When we apply our attack to more complex models, we act as if full retraining results in the model that is derived from taking a newton step --- and the reason our reconstruction performance degrades is simply that this approximation becomes imperfect. However, if rather than full retraining, the machine unlearning method employed was one that simply took a newton step, our reconstruction would again be near perfect. We will elaborate on this point in the revision.

[Response to Weaknesses 4]

As we mention in Sec. 4, in all our experiments, the dataset is split into two halves; the first half is used for training the private model, and the second half is used for attacking the trained model.

The public dataset is used to estimate the Hessian matrix, which is the covariance matrix for linear regression. The quality of the estimation increases asymptotically with respect to the number of samples in the public dataset, and it is the only source of error in attacking linear regression, thus, the attack performance behaves similarly to the quality of the estimation. This grows with the dimension of the model; we can elaborate on this point in the revision.

[Response to Weaknesses]

Our study is explicitly focused on exposing the risk present in even very simple models, such as linear regression, logistic regression, SVMs, and feature augmentation using random Fourier features. For such models, full retraining is feasible, and would be the expected solution to the data deletion problem, as computational approximations to retraining are not needed.

Full retraining for a single data deletion in linear regression is equivalent to updating the model parameters using Newton's update as we discussed in Sec. 3.2. By leveraging this concept, our attack achieves almost perfect reconstruction, and the only error source is the estimation of the Hessian matrix using public data. For more complex models, a number of popular unlearning methods approximate full retraining by taking a Newton update. When we apply our attack to more complex models, we act as if full retraining results in the model that is derived from taking a newton step --- and the reason our reconstruction performance degrades is simply that this approximation becomes imperfect. However, if rather than full retraining, the machine unlearning method employed was one that simply took a newton step, our reconstruction would again be near perfect. We will elaborate on this point in the revision.

Re: multi-sample deletion, our approach recover an approximation of the gradient sum for all the deleted samples. A determined adversary can poison an unlearning round by requesting deletion of n-1 samples known to the adversary, and so can recover the gradient of the single unknown point from this sum. Nevertheless we agree that multi-sample recovery is an important question that our work does not address, and think this is one of the most interesting questions for future work arising from our paper.

On the displayed metrics: We show both the full distribution of cosine similarity as well as randomly selected reconstructions for visual inspection. While other metrics such as similarity on a well-chosen embedding function could be of interest, we chose to simplify the presentation and show the more challenging (pixel-wise, for images) cosine similarity comparison. We are open to suggestions and are happy to engage if you have particular additional metrics that you think would be informative.

On defenses: Our work highlights the privacy risk of unlearning in standard models. As we discuss in our work, training models using differential privacy (at small epsilon values) provably prevents reconstruction, even in unlearning scenarios because of differential privacy's composition property. There is an exciting opportunity for research suggested by our work: is there a way to give unlearning methods which have meaningful privacy guarantees even when the additional model training procedure did not?

[Response to Questions]

On the use of “Avg” as a baseline: This is a straightforward way of leveraging information about the data distribution in a manner that does not incorporate any information about the model parameters. The “MaxDiff” baseline is also included, and this is motivated by the assumption that the overall performance of the update on held-out data would be, in relative terms, much smaller than the peformance difference of the sample being deleted (since this sample transitions from being in the training distribution, to being outside it)

On the robustness to model architectures: Our existing experiments already show results for a variety of simple models and loss functions on the same datasets (linear and logistic regression, ridge regression, ridge regression over random Fourier features, cross-entropy minimization over random Fourier features, as well as support vector machines over both raw features and random Fourier features).

On the computational complexity of the attack: Our attack in its most general form relies on a Hessian-vector product per public sample as shown in Eq. 13. This can be efficiently implemented in all common deep learning frameworks with a computational complextiy of $O(nd^2)$ with $n$ being the number of public samples and $d$ the number of parameters in the model. It is also possible to replace the Hessian computation altogether by using the Fisher information matrix, bringing the computational complexity down to $O(nd)$.

On countermeasures: The most straightforward countermeasure would be to train the original and updated models using differential privacy. This would provably prevent any reconstruction attack (as privacy composes across pairs of models if they are both trained privately). An exciting research direction suggested by our work is the study of unlearning methods in which the parameter update is itself differentially private with respect to the deleted samples --- and a fuller understanding of how this trades off with other unlearning desiderata.

[Response to Weaknesses 1]

We take the position that security assurances should be based on minimal assumptions. Here, we view the assumption that an attacker who has API access to the model does -not- have access to model parameters to be dangerously strong. Consider for example a d dimensional linear model, as we study initially in our work. Just from query access, an attacker can recover the model parameters by querying the model on d linearly independent points and solving a system of linear equations. This requires no knowledge of the data distribution. So, there is no meaningful difference between white box and black box access in such scenarios.

What about for more complex models? Even there the boundary between white-box and black-box access has been blurring. For example recent work [1] has shown that it is possible to reconstruct the embedding matrix from a production LLM model with only black-box access. And of course, open source models explicitly release parameters with each version of the model.

With regards to access to the data distribution, we only assume access to samples from the same distribution as training data, not to private samples atually used in training. This is a standard assumption underlying even simpler attacks suck as membership inference. We agree with the reviewer that it may sometimes be difficult for an attacker to ascertain what this distribution is, but again, we take the view that when analysing attacks as a means to audit security vulnerabilities, we should be generous (within reason) about the assumed abilities of the attacker.

[1] Carlini, Nicholas, et al. "Stealing part of a production language model." arXiv preprint arXiv:2403.06634 (2024).

[Response to Weaknesses 2]

An important aspect of existing machine unlearning approaches is that almost all of them aim to approximate full retraining with reduced computational cost. These approximations are proposed due to the intense compute required for full retraining, especially for large neural networks and LLMs.

Our study is explicitly focused on exposing the risk present in even very simple models, such as linear regression, logistic regression, SVMs, and feature augmentation using random Fourier features. For such models, full retraining is feasible, and would be the expected solution to the data deletion problem, as computational approximations to retraining are not needed.

Full retraining for a single data deletion in linear regression is equivalent to updating the model parameters using Newton's update as we discussed in Sec. 3.2. By leveraging this concept, our attack achieves almost perfect reconstruction, and the only error source is the estimation of the Hessian matrix using public data. For more complex models, a number of popular unlearning methods approximate full retraining by taking a Newton update. When we apply our attack to more complex models, we act as if full retraining results in the model that is derived from taking a newton step --- and the reason our reconstruction performance degrades is simply that this approximation becomes imperfect. However, if rather than full retraining, the machine unlearning method employed was one that simply took a newton step, our reconstruction would again be near perfect. We will elaborate on this point in the revision.