CoChat
Sign Up
PreprintCited by 38Privacy-Preserving Technologies in DataAdversarial Robustness in Machine LearningCloud Data Security Solutions

Towards Probabilistic Verification of Machine Unlearning

Open access
Sommer, David Marco, Song, Liwei, Wagh, Sameer, Mittal, Prateek·2020·arXiv
DOI 10.48550/arxiv.2003.04247arXiv 2003.04247
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2003.04247

Cites

4 of 4 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • There are already some relevant schemes, such as the backdoor-based verification mechanism in Reference [44] and the encryption-based verification scheme in Reference [111].

    “There are already some relevant schemes, such as the backdoorbased verification mechanism in Reference [44] and the encryption-based verification scheme in Reference [111].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [44]

  • Sommer et al. provided a backdoor verification mechanism from an individual user perspective in the context of machine learning as a service (MLaaS).

    “Sommer et al. [44] provided a novel backdoor verification mechanism from an individual user perspective in the context of machine learning as a service (MLaaS) [61].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [44]

  • The backdoor verification mechanism can verify with high confidence whether the service provider complies with the user's right to unlearn information.

    “This approach can verify, with high confidence, whether the service provider complies with the user's right to unlearn information.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [44]

  • Those one-sided methods seldom provide strong verification of the unlearning process's effectiveness.

    “Those one-sided methods seldom provide strong verification of the unlearning process's effectiveness [44, 109, 110].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [44]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 48

  1. [1][1] M. Fredrikson, S. Jha, and T. Ristenpart, 'Model inversion attacks that exploit confidence information and basic countermeasures,' in ACM Conference on Computer and Communications Security (CCS) , 2015, pp. 1322-1333. -
  2. [2][2] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, 'Membership inference attacks against machine learning models,' in IEEE Symposium on Security and Privacy (S&P) , 2017, pp. 3-18. -
  3. [4][4] N. Carlini, C. Liu, Ú. Erlingsson, J. Kos, and D. Song, 'The secret sharer: Evaluating and testing unintended memorization in neural networks,' in USENIX Security Symposium , 2019, pp. 267-284. -
  4. [5][5] G. D. P. Regulation, 'Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46,' Official Journal of the European Union (OJ) , vol. 59, no. 1-88, p. 294, 2016. -
  5. [8][8] A. Ginart, M. Guan, G. Valiant, and J. Y. Zou, 'Making AI forget you: Data deletion in machine learning,' in Advances in Neural Information Processing Systems , 2019, pp. 3513-3526. -
  6. [9][9] L. Bourtoule, V. Chandrasekaran, C. Choquette-Choo, H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot, 'Machine unlearning,' arXiv preprint arXiv:1912.03817 , 2019. - · arXiv
  7. [10][10] C. Guo, T. Goldstein, A. Hannun, and L. van der Maaten, 'Certified data removal from machine learning models,' arXiv preprint arXiv:1911.03030 , 2019. - · arXiv
  8. [11][11] T. Baumhauer, P. Schöttle, and M. Zeppelzauer, 'Machine unlearning: Linear filtration for logit-based classifiers,' arXiv preprint arXiv:2002.02730 , 2020. - · arXiv
  9. [14][14] E. L. Lehmann and J. P. Romano, Testing statistical hypotheses . Springer Science & Business Media, 2006. -
  10. [15][15] C. Song and V. Shmatikov, 'Auditing data provenance in text-generation models,' in Proceedings of the 25th - ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , 2019, pp. 196-206. -
  11. [16][16] M. Chen, Z. Zhang, T. Wang, M. Backes, M. Humbert, and Y. Zhang, 'When machine unlearning jeopardizes privacy,' arXiv preprint arXiv:2005.02205 , 2020. - · arXiv
  12. [17][17] T. Gu, K. Liu, B. Dolan-Gavitt, and S. Garg, 'Badnets: Evaluating backdooring attacks on deep neural networks,' IEEE Access , vol. 7, pp. 47 230-47 244, 2019. -
  13. [19][19] H. Robbins and S. Monro, 'A stochastic approximation method,' The Annals of Mathematical Statistics , vol. 22, no. 3, pp. 400-407, 1951. [Online]. Available: http://www.jstor.org/stable/2236626 -
  14. [20][20] D. P. Kingma and J. Ba, 'Adam: A method for stochastic optimization,' in International Conference on Learning Representations (ICLR) , 2015. -
  15. [22][22] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, 'Gradient-based learning applied to document recognition,' Proceedings of the IEEE , vol. 86, no. 11, pp. 2278-2324, 1998. -
  16. [24][24] S. Hochreiter and J. Schmidhuber, 'Long short-term memory,' Neural computation , vol. 9, no. 8, pp. 17351780, 1997. -
  17. [25][25] X. Chen, C. Liu, B. Li, K. Lu, and D. Song, 'Targeted backdoor attacks on deep learning systems using data poisoning,' arXiv preprint arXiv:1712.05526 , 2017. - · arXiv
  18. [26][26] A. Salem, R. Wen, M. Backes, S. Ma, and Y. Zhang, 'Dynamic backdoor attacks against machine learning models,' arXiv preprint arXiv:2003.03675 , 2020. - · arXiv
  19. [27][27] Y. Yao, H. Li, H. Zheng, and B. Y. Zhao, 'Latent backdoor attacks on deep neural networks,' in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security , 2019, pp. 2041-2055. -
  20. [28][28] A. Saha, A. Subramanya, and H. Pirsiavash, 'Hidden trigger backdoor attacks,' AAAI , 2020. -
  21. [29][29] A. Turner, D. Tsipras, and A. Madry, 'Label-consistent backdoor attacks,' arXiv preprint arXiv:1912.02771 , 2019. - · arXiv
  22. [30][30] B. Wang, Y. Yao, S. Shan, H. Li, B. Viswanath, H. Zheng, and B. Y. Zhao, 'Neural cleanse: Identifying and mitigating backdoor attacks in neural networks,' in 2019 IEEE Symposium on Security and Privacy (SP) . IEEE, 2019, pp. 707-723. -
  23. [31][31] T. J. L. Tan and R. Shokri, 'Bypassing backdoor detection algorithms in deep learning,' arXiv preprint arXiv:1905.13409 , 2019. - · arXiv
  24. [32][32] K. Liu, B. Dolan-Gavitt, and S. Garg, 'Fine-pruning: Defending against backdooring attacks on deep neural networks,' in International Symposium on Research in Attacks, Intrusions, and Defenses . Springer, 2018, pp. 273-294. -
  25. [33][33] B. Chen, W. Carvalho, N. Baracaldo, H. Ludwig, B. Edwards, T. Lee, I. Molloy, and B. Srivastava, 'Detecting backdoor attacks on deep neural networks by activation clustering,' arXiv preprint arXiv:1811.03728 , 2018. - · arXiv
  26. [34][34] Y. Liu, W.-C. Lee, G. Tao, S. Ma, Y. Aafer, and X. Zhang, 'ABS: Scanning neural networks for back-doors by artificial brain stimulation,' in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security , 2019, pp. 1265-1282. -
  27. [35][35] B. Tran, J. Li, and A. Madry, 'Spectral signatures in backdoor attacks,' in Advances in Neural Information Processing Systems , 2018, pp. 8000-8010. -
  28. [36][36] A. K. Veldanda, K. Liu, B. Tan, P. Krishnamurthy, F. Khorrami, R. Karri, B. Dolan-Gavitt, and S. Garg, 'NNoculation: Broad spectrum and targeted treatment of backdoored DNNs,' arXiv preprint arXiv:2002.08313 , 2020. - · arXiv
  29. [38][38] J. van den Hooff, D. Lazar, M. Zaharia, and N. Zeldovich, 'Vuvuzela: Scalable private messaging resistant to traffic analysis,' in ACM Symposium on Operating Systems Principles (SOSP) , 2015. -
  30. [40][40] S. Caldas, P. Wu, T. Li, J. Konecný, H. B. McMahan, V. Smith, and A. Talwalkar, 'Leaf: A benchmark for federated settings,' ArXiv , vol. abs/1812.01097, 2018. - · arXiv
  31. [42][42] K. He, X. Zhang, S. Ren, and J. Sun, 'Deep residual learning for image recognition,' in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , June 2016. -
  32. [43][43] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, 'Imagenet: A large-scale hierarchical image database,' in 2009 IEEE conference on computer vision and pattern recognition . Ieee, 2009, pp. 248-255. -
  33. [44][44] X. Zhang, J. Zhao, and Y. LeCun, 'Character-level convolutional networks for text classification,' in Advances in neural information processing systems , 2015, pp. 649657. -
  34. [45][45] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, 'Deep learning with differential privacy,' in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security , 2016, pp. 308-318. -
  35. [46][46] S. Neel, A. Roth, and S. Sharifi-Malvajerdi, 'Descent-todelete: Gradient-based methods for machine unlearning,' arXiv preprint arXiv:2007.02923 , 2020. - · arXiv
  36. [47][47] M. Kearns, 'Efficient noise-tolerant learning from statistical queries,' Journal of the ACM (JACM) , vol. 45, no. 6, pp. 983-1006, 1998. -
  37. [49][49] D. Gruss, J. Lettner, F. Schuster, O. Ohrimenko, I. Haller, and M. Costa, 'Strong and efficient cache side-channel protection using hardware transactional memory,' in USENIX Security Symposium , 2017. -
  38. [50][50] O. Ohrimenko, F. Schuster, C. Fournet, A. Mehta, S. Nowozin, K. Vaswani, and M. Costa, 'Oblivious multi-party machine learning on trusted processors,' in USENIX Security Symposium , 2016. -
  39. [51][51] J. Allen, B. Ding, J. Kulkarni, H. Nori, O. Ohrimenko, and S. Yekhanin, 'An algorithmic framework for differentially private data analysis on trusted processors,' in Advances in Neural Information Processing Systems , 2019, pp. 13 635-13 646. -
  40. [52][52] E. Ghosh, M. T. Goodrich, O. Ohrimenko, and R. Tamassia, 'Fully-dynamic verifiable zero-knowledge order queries for network data.' IACR Cryptology ePrint Archive , vol. 2015, p. 283, 2015. -
  41. [53][53] E. Ghosh, O. Ohrimenko, and R. Tamassia, 'Authenticated range & closest point queries in zero-knowledge.' IACR Cryptology ePrint Archive , vol. 2015, p. 1183, 2015. -
  42. [54][54] M. Lipp, M. Schwarz, D. Gruss, T. Prescher, W. Haas, A. Fogh, J. Horn, S. Mangard, P. Kocher, D. Genkin, Y. Yarom, and M. Hamburg, 'Meltdown: Reading kernel memory from user space,' in USENIX Security Symposium , 2018. -
  43. [55][55] P. Kocher, J. Horn, A. Fogh, , D. Genkin, D. Gruss, W. Haas, M. Hamburg, M. Lipp, S. Mangard, T. Prescher, M. Schwarz, and Y. Yarom, 'Spectre attacks: Exploiting speculative execution,' in IEEE Symposium on Security and Privacy (S&P) , 2019. -
  44. [56][56] A. Sablayrolles, M. Douze, C. Schmid, and H. Jégou, 'Radioactive data: tracing through training,' arXiv preprint arXiv:2002.00937 , 2020. - · arXiv
  45. [57][57] Y. Adi, C. Baum, M. Cisse, B. Pinkas, and J. Keshet, 'Turning your weakness into a strength: Watermarking deep neural networks by backdooring,' in 27th USENIX Security Symposium (USENIX Security 18) , 2018, pp. 1615-1631. -
  46. [58][58] G. Cohen, S. Afshar, J. Tapson, and A. van Schaik, 'EMNIST: Extending MNIST to handwritten letters,' in 2017 International Joint Conference on Neural Networks (IJCNN) , May 2017, pp. 2921-2926. -
  47. [59][59] R. Collobert, K. Kavukcuoglu, and C. Farabet, 'Torch7: A matlab-like environment for machine learning,' in BigLearn, NIPS Workshop , 2011. -
  48. [61][61] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes , ser. Mathematical Studies. Elsevier Science, 1977. [Online]. Available: https: //books.google.com/books?id=LuomAQAAIAAJ

Cited by

Sorted by citations

Authors
Sommer, D. M., Song, L., Wagh, S., & Mittal, P.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2003.04247
arXiv
2003.04247
OpenAlex
W3009148757
Cited by
38
References
4
Citations by year
2026: 1 · 2025: 5 · 2024: 4 · 2023: 3 · 2022: 8 · 2021: 14 · 2020: 3
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
  • Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
Keywords
machine unlearning, right to be forgotten, machine learning as a service, backdoor attacks, probabilistic verification, hypothesis testing, GDPR compliance, backdoor defense, neural network model

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review