# Towards Probabilistic Verification of Machine Unlearning

arXiv: https://arxiv.org/abs/2003.04247 · HTML: https://mlsanity.com/paper/2003.04247/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2020.

## Built on by (most cited first, 30 of 50)

- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Fast Yet Effective Machine Unlearning](https://mlsanity.com/paper/2111.08947/) (2021)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [Turn the Combination Lock: Learnable Textual Backdoor Attacks via Word Substitution](https://mlsanity.com/paper/2106.06361/) (2021)
- [Hard to Forget: Poisoning Attacks on Certified Machine Unlearning](https://mlsanity.com/paper/2109.08266/) (2021)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [VeriFi: Towards Verifiable Federated Unlearning](https://mlsanity.com/paper/2205.12709/) (2022)
- [Survey: Leakage and Privacy at Inference Time](https://mlsanity.com/paper/2107.01614/) (2021)
- [Hidden Poison: Machine Unlearning Enables Camouflaged Poisoning Attacks](https://mlsanity.com/paper/2212.10717/) (2022)
- [Backdoor Attacks and Countermeasures in Natural Language Processing Models: A Comprehensive Security Review](https://mlsanity.com/paper/2309.06055/) (2023)
- [Threats, Attacks, and Defenses in Machine Unlearning: A Survey](https://mlsanity.com/paper/2403.13682/) (2024)
- [Machine Unlearning Fails to Remove Data Poisoning Attacks](https://mlsanity.com/paper/2406.17216/) (2024)
- [Verifiable and Provably Secure Machine Unlearning](https://mlsanity.com/paper/2210.09126/) (2022)
- [Attacks in Adversarial Machine Learning: A Systematic Survey from the Life-cycle Perspective](https://mlsanity.com/paper/2302.09457/) (2023)
- [zkDL: Efficient Zero-Knowledge Proofs of Deep Learning Training](https://mlsanity.com/paper/2307.16273/) (2023)
- [DeepObliviate: A Powerful Charm for Erasing Data Residual Memory in Deep Neural Networks](https://mlsanity.com/paper/2105.06209/) (2021)
- [Machine Unlearning: A Survey](https://mlsanity.com/paper/2306.03558/) (2023)
- [A Framework for Deprecating Datasets: Standardizing Documentation, Identification, and Communication](https://mlsanity.com/paper/2111.04424/) (2021)
- [SIFU: Sequential Informed Federated Unlearning for Efficient and Provable Client Unlearning in Federated Optimization](https://mlsanity.com/paper/2211.11656/) (2022)
- [Is Retain Set All You Need in Machine Unlearning? Restoring Performance of Unlearned Models with Out-Of-Distribution Images](https://mlsanity.com/paper/2404.12922/) (2024)
- [A Survey of Neural Trojan Attacks and Defenses in Deep Learning](https://mlsanity.com/paper/2202.07183/) (2022)
- [A General Framework for Data-Use Auditing of ML Models](https://mlsanity.com/paper/2407.15100/) (2024)
- [Proof of Unlearning: Definitions and Instantiation](https://mlsanity.com/paper/2210.11334/) (2022)
- [A Survey on Machine Unlearning: Techniques and New Emerged Privacy Risks](https://mlsanity.com/paper/2406.06186/) (2024)
- [SoK: Dataset Copyright Auditing in Machine Learning Systems](https://mlsanity.com/paper/2410.16618/) (2024)
- [Machine Unlearning Doesn't Do What You Think: Lessons for Generative AI Policy and Research](https://mlsanity.com/paper/2412.06966/) (2024)
- [An Introduction to Machine Unlearning](https://mlsanity.com/paper/2209.00939/) (2022)
- [DUCK: Distance-based Unlearning via Centroid Kinematics](https://mlsanity.com/paper/2312.02052/) (2023)
- [Information Flow Control in Machine Learning through Modular Model Architecture](https://mlsanity.com/paper/2306.03235/) (2023)

## Abstract (arXiv)

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.