Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy

Thank you for your feedback! We're glad to hear that you find our paper interesting and the soundness and presentation to be good. We address your questions and comments below.

Q1: Exceeds page limit

The paper currently extends beyond the 10-page maximum allowed by ICLR, utilizing in total 11 pages of core content. A: Thank you for pointing this out and we sincerely apologize for exceeding the page limit by 2 additional newlines, due to a last minute update that we did not carefully check. We’ve fixed this in the revised PDF.

Additionally, several crucial aspects, such as unlearning algorithm specifics, hyperparameters, and theoretical results, are deferred to the appendix, making it challenging to assess the completeness of the methods presented within the main body.

Thank you for the comment. Regarding the placement of technical content:

• Unlearning algorithm specifics, hyperparameters: the core unlearning algorithms and their hyperparameters are fully described in the main text (lines 222-239). Only the hyperparameter selection rationale is in the appendix. We can certainly move this discussion to the main paper if you feel it would improve readability, space permitting.
• Theoretical result: we have summarized the main theorem statement in the body of the paper (lines 298-301). This theorem establishes the existence of our proposed attacks in the context of linear model unlearning. The detailed proof remains in the appendix to maintain narrative flow while preserving technical completeness.

Q2 Mischaracterization as a novel adversarial attack & Lack of novelty in attack mechanisms

While the approach is framed as a new type of adversarial attack, it is more accurately an adaptation of established poisoning techniques. The attack uses a standard poisoning approach where the unlearning update replaces fine-tuning or training in the model. As outlined, the objective of minimizing model accuracy while removing poisoning samples mirrors conventional poisoning attacks. This is detailed in prior work such as [1-4] or survey [5] which already connect poisoning attacks to meta-learning approaches, similar to the attack formulation in Section 2.2 of this paper.

The two attack methods (white-box and black-box) do not introduce any new methodologies beyond existing techniques. The white-box method is essentially a re-implementation of approaches discussed in [1] and [3], while the black-box method, based on gradient estimation, has been used in [5]. Consequently, the attack does not present a unique contribution in terms of adversarial methods.

A: We appreciate the reviewer’s comments and agree that our attacking algorithm is similar to some previous poisoning techniques. However, we note they all boil down to the same standard formulation with gradient based searching of adversarial inputs. The main novelty (of previous poisoning papers and our work) is applying such techniques to a novel application scenario and systematically studying the implications and defense. Specifically, we highlight that

• Our primary contribution lies in identifying a novel attack interface specific to machine unlearning pipelines, which fundamentally targets a different system and interface (unlearning) compared to poisoning attacks (in standard learning or meta-learning).
• With this new attack surface, we also explore corresponding defensive methods. We also note that the defensive landscape for unlearning differs significantly from that of training-time poisoning attacks. In unlearning, the unlearned set must resemble valid training data previously used to train the model. This enables defenses based on similarity comparison to training examples (Section 4).

We discussed some of the previous poisoning attacks in the manuscript, but we apologize for missing some of the relevant citations and have addressed this in the revised manuscript.

We appreciate your feedback and are glad to hear you enjoyed our paper. We address your questions and comments below.

Q1: Scalability Limitations in Black-Box Attacks

While the paper’s black-box attacks yield promising results, they might face challenges when applied to high-dimensional data. Including a more detailed discussion of this limitation could add depth and insight. Addressing these challenges would provide valuable context about the trade-offs and bottlenecks in black-box attacks, enhancing the practical understanding for researchers and practitioners in the field of machine unlearning and security.

A: We appreciate the comment. From a theoretical perspective, the gradient estimators in the black-box setting can have larger variance in the high-dimensional setting, and our experiments confirm that attacking high-dimensional data (e.g., ImageNet) is more challenging (Table 2). Increasing the number of estimators and averaging them could partially mitigate this issue. As suggested, we have included this discussion in the revised PDF.

Q2: Limited Exploration of Adaptive Defense Mechanisms

This paper makes a valuable contribution by assessing the effectiveness of various defensive mechanisms and highlighting potential vulnerabilities. However, investigating additional adaptive defenses, such as anomaly detection or similarity-based clustering methods, could strengthen this section.

A: Thank you for the comment. We note that Section 4 already explores several anomaly detection approaches, including hashing-based, embedding-based, and pixel distance-based methods. If you have specific suggestions for additional defenses, we would be happy to consider and discuss their incorporation.

Q3: Ambiguity in the definition of “Black-Box” Attack

Although termed a “black-box” attack, the method used by this paper still requires access to the training loss. This might be somewhat misleading, as traditional black-box adversarial attacks are generally assumed to operate without any internal information about the target model. Adjusting this terminology or clarifying the scope could improve precision and align expectations.

A: Thank you for this valuable feedback. In our setup, we define the black-box attack as one that requires access to the training loss. We acknowledge that this differs from the stricter definition, where the attacker has access only to the model's outputs. However, similar setups have also been referred to as "black-box" in prior literature [1, 2, 3]. We have clarified this in the revised PDF as suggested (lines 135-136).

Q4: Potential defenses

Can you think about possible ways to enhance the defense against such adversarial machine unlearning attacks?

A: Thank you for the comment. As noted in Section 4.2, the most robust defense we can propose is for the model deployer to avoid directly using user-submitted inputs for unlearning (the paragraph titled with “Similarity searching and indexing”). Instead, they could compare the submitted inputs to already stored examples and use these for unlearning. However, this defense requires the model deployer to pre-store such examples and still remains susceptible to indexing attacks, where an attacker selects a subset of valid training examples that degrade model performance after unlearning.

References:

[1] Chen, Pin-Yu, et al. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models.

[2] Tu, Chun-Chen, et al. Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks.

[3] Liu, Yiyong, et al. Membership inference attacks by exploiting loss trajectory.

Q3: defences with full access to training examples

If so, wouldn't the best defense be not trusting the user-provided data at all?... Then they could just identify the precise set of user's data used for model training, and then execute the unlearning algorithm.

A: We appreciate the comment. We kindly note that your suggestion of not trusting user-provided data is exactly the defense strategy we explored in Section 4.2 (the paragraph titled "Similarity searching and indexing"). Specifically, we examined a defense mechanism where the model deployer could compare submitted inputs against stored training examples to identify and unlearn them. However, we demonstrate that this approach still remains vulnerable to the indexing attacks: In such attacks, an adversary can strategically select a subset of valid training examples that, when removed, significantly degrades model performance (see Figure 5).

Q4: Experiment settings

In Section 3, the forget set has 10 to 100 samples. It's unclear how this range is devised, but 100 may sound too much IMO, as it means the model provider will accept up to 100 samples, which the requester claims belong to them, to update their model weights. It's suggested to provide more concrete justification for why such numbers are chosen.

A: The range of forget set sizes was selected to capture a spectrum of unlearning requests, from small (10 samples) to relatively large (100 samples).

Regarding the concern about the size of 100 samples, we note that this is not unusually large in the context of prior work. The table below highlights the largest forget set sizes used in previous studies that use CIFAR-10 as a benchmark for unlearning:

Compared to these studies, our choice of a maximum of 100 samples is relatively modest.

The evaluation quantifies the attack's performance as the maximum accuracy degradation observed across a grid search of hyperparameters. I'm curious (and concerned) why the maximum instead of other more common metrics are reported, such as the average, medium, or confidence interval.

A: Our metric reports the average (across five randomly chosen forget sets) of the maximum accuracy degradation under attack. Using the "average" ensures statistical rigor, while the "maximum accuracy degradation" highlights the worst-case scenario, which is critical for evaluating system robustness. We argue that from a model deployer's perspective, focusing on non-optimal attack hyperparameters is less informative, as it fails to capture the most damaging potential outcomes.

It's also not very convincing that, in reality, the attacker would be able to have a grid search and obtain the best results.

A: While online grid search may seem computationally intensive, we note that attackers can feasibly conduct offline hyperparameter optimization. In our implementation, we optimized hyperparameters for each forget set size during an initial search and reused them for all subsequent attacks of that size. This simulates a realistic attack scenario, where an adversary balances computational cost with maximizing effectiveness.

References:

[1] Golatkar, Aditya, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. CVPR 2020

[2] Goel, Shashwat, et al. Towards adversarial evaluations for inexact machine unlearning. arXiv preprint arXiv:2201.06640 (2022)

[3] NeurIPS 2023 Machine Unlearning Challenge. https://unlearning-challenge.github.io/

[4] Kurmanji, Meghdad, et al. Towards unbounded machine unlearning. NeurIPS 2024

Thank you for your feedback! We are glad to hear that you find our paper solid, well-written, and our evaluation generally comprehensive. We address your questions and comments below.

Q1: Related work of security risks of unlearning tasks and poisoning attacks

have there been prior efforts to study the security risks of machine unlearning tasks?

A: Thanks. As discussed in the related work section of our submission (Section 6), prior studies have explored various security risks in machine unlearning systems, including:

• Unintended privacy leakage: Carlini et al. (2022), Hayes et al. (2024), Shi et al. (2024)
• Vulnerability to re-introducing unlearned knowledge: Shumailov et al. (2024), Lucki et al. (2024)
• Insufficient removal of poisoned data: Di et al. (2022)

To the best of our knowledge, our work is the first to demonstrate that adversarial unlearning requests can cause catastrophic performance degradation in unlearned models.

what's the difference between the threat models of this work and poisoning attacks? attacker is also able to execute poisoning attacks

A: You raised a valid point about poisoning attacks being a plausible alternative when the attacker has control over part of the training data. However, we’d like to make two important clarifications:

• Our attack could operate under a slightly weaker threat model compared to poisoning attacks—it can be executed even without the attacker having control over a subset of the training data (Section 5.2).
• Our attack identifies a new vulnerability unique to machine unlearning systems, whereas poisoning is a well-known attack vector applicable to all systems involving model training. These two types of attacks target different stages of a machine learning system, and thus our attack is NOT intended to compete with or replace standard poisoning attacks.

Therefore, we view our contribution as orthogonal and possibly complementary to poisoning attacks.

Q2: Practicalness of threat model

I'm not sure if it ever makes sense for a model trainer to rely on user-submitted data to execute unlearning algorithms. In practice, it's usually the model provider's responsibility to identify which data belongs to the user and unlearn those data stored in the model provider's datastore.

A: We completely agree with the reviewer's opinion that the model provider has the responsibility to verify the unlearning requests, which is one of the main implications we are advocating in this paper. We note that while unlearning has been a promising research direction recently, it has not yet been widely deployed. Therefore, we do not have concrete examples of deployed systems to demonstrate this attack. However, all the mainstream formulation of unlearning has largely overlooked this problem. Our systematic study hopes to guide the evolution of unlearning protocols to address such vulnerabilities before widespread deployment.

In the following, we address the two concrete questions raised by the reviewer:

1. Why might a model provider not store all training data despite having originally trained the model?

There are two potential reasons:

• Storage limitations: In cases of training on streaming data, the model deployer may only retain the most recent data due to limited storage capacity and have to discard older training data.
• Regulatory compliance: regulations often require organizations to delete raw training data after a predefined retention period to minimize data exposure. Typically, the retention period for raw training data is shorter than that of the model.

2. Why might a model provider accept user-submitted samples for unlearning instead of identifying them themselves?

Under the GDPR, individuals have the "right to be forgotten," which mandates that organizations remove personal data upon user request. In such cases, the model provider may rely on user-submitted samples to execute an unlearning operation.

the proposed threat model may also cause some other issues, where User A may submit benign samples belonging to User B and request deletion on behalf of User B without User B's consent.

A: Thanks! While the scenario you described is orthogonal to our primary contribution and can be covered by the current attack framework, it is an interesting point. We will include a discussion of this in the final version.

I believe what's actually happening is that the model provider will go through their data store and identify those belonging to the requester, which they know for sure (1) belong to the requester and (2) were indeed used in the model training.

A: Strong defenses like data ownership verification, as you suggested, could indeed prevent certain attacks. However, implementing them in practice is challenging because privacy regulations typically require data to be anonymized, making it sometimes prohibitive to store user IDs or similar identifiers that link data to specific users.

Dear Reviewer jZsQ,

Thank you for your thoughtful response and follow-up questions. We address them as follows.

Q2: Threat model

I'm generally okay with the threat model's justification but would recommend being precise when introducing a new threat model...I think the author's response should be able to address the 1st point, which was the root cause of confusion. It's thus recommended to refine the motivation regarding this gap.

We’re glad to hear that our clarification about the threat model largely addressed your concern. We also agree with your suggestion to further clarify our motivation, particularly by discussing the two mentioned points.

We plan to restructure the introduction flow of the paper as follows: While machine unlearning algorithms have been proposed, there has been limited discussion on their deployment, particularly regarding whether these algorithms should accept user-provided inputs to construct D-forget. In this paper, we highlight two potential vulnerabilities that attackers could exploit if user-provided inputs are allowed to construct D-forget:

• Adversarially perturbed examples from D-forget (Section 3), which can be mitigated by certain defenses (Section 4.1).
• Adversarially chosen valid examples from D-forget, which pose a greater challenge for the deployer to defend against (Section 4.2).

We are happy to update the paper accordingly if this revised flow makes sense to you.

Q3: Section 4.2

I double-checked the results and the results are somewhat confusing. IIRC, it shows that the attacker can adversarially select 10 samples to construct the D-forget, which will reduce 30% accuracy if executed by the model deployer. I wonder where these 10 samples were selected and if there were additional assumptions. Were they selected from the entire training set (which the attacker should not have access to), or a chosen portion of the training set that the attacker initially provided for model training?

Thank you for your question. In this setting, the attacker adversarially selects N examples to construct D-forget. Figure 5 illustrates that for N=10, this results in the model achieving ~30% classification error after unlearning (compared to only 3.8% classification error for an average-case forget set).

We note that this is a proof-of-concept experiment, where we allow the attacker to exploit its maximal power by randomly sampling N images from the entire training set. For your reference, we also conducted experiments where the attacker has access to only a portion of the data. Below are the results for N=10:

We are happy to include these additional results for different values of N's in the final version of the paper.

Q4: max vs. average

Since this paper is an attack paper, the results are higher the better. So it would make more sense to report the mean and std of the attack's bare effectiveness across several runs.

Thank you for your follow-up question. We’ve included the average-case results for the main tables (Table 1 and Table 4) in Appendix B.3 for your reference.