2020

Towards Probabilistic Verification of Machine Unlearning

Sommer, David Marco, Song, Liwei, Wagh, Sameer et al.

Understand

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).

Built on

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
1951
Earlier work this paper cites.
F. Rosenblatt, “Principles of neurodynamics. perceptrons and the theory of brain mechanisms,” Cornell Aeronautical Lab Inc Buffalo NY, Tech. Rep., 1961
1961
Earlier work this paper cites.
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
1977
Earlier work this paper cites.
P. J. Grother, “NIST special database 19 handprinted forms and characters database,” National Institute of Standards and Technology , 1995
1995
Earlier work this paper cites.
S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural computation , vol. 9, no. 8, pp. 1735–1780, 1997
1997
Earlier work this paper cites.
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
1998
Earlier work this paper cites.
M. Kearns, “Efficient noise-tolerant learning from statistical queries,” Journal of the ACM (JACM) , vol. 45, no. 6, pp. 983–1006, 1998
1998
Earlier work this paper cites.
E. L. Lehmann and J. P. Romano, Testing statistical hypotheses . Springer Science & Business Media, 2006
2006
Earlier work this paper cites.
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
2009
Earlier work this paper cites.
R. Collobert, K. Kavukcuoglu, and C. Farabet, “Torch7: A matlab-like environment for machine learning,” in BigLearn, NIPS Workshop , 2011
2011
Earlier work this paper cites.
A. Krizhevsky, V. Nair, and G. Hinton, “The CIFAR-10 dataset,” URL: http://www.cs.toronto.edu/kriz/cifar.html , 2014
2014
Earlier work this paper cites.
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
2015
Earlier work this paper cites.
Y. Cao and J. Yang, “Towards making systems forget with machine unlearning,” in 2015 IEEE Symposium on Security and Privacy . IEEE, 2015, pp. 463–480
2015
Earlier work this paper cites.
D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in International Conference on Learning Representations (ICLR) , 2015
2015
Earlier work this paper cites.
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
2015
Earlier work this paper cites.
X. Zhang, J. Zhao, and Y. LeCun, “Character-level convolutional networks for text classification,” in Advances in neural information processing systems , 2015, pp. 649–657
2015
Earlier work this paper cites.
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
2015
Earlier work this paper cites.
E. Ghosh, O. Ohrimenko, and R. Tamassia, “Authenticated range & closest point queries in zero-knowledge.” IACR Cryptology ePrint Archive , vol. 2015, p. 1183, 2015
2015
Earlier work this paper cites.
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
2016
Earlier work this paper cites.
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in IEEE conference on computer vision and pattern recognition (CVPR) , 2016, pp. 770–778
2016
Earlier work this paper cites.

Similar

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
2016
Cited alongside, same era.
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
2016
Cited alongside, same era.
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
2016
Cited alongside, same era.
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
2017
Cited alongside, same era.
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
Original
2017
Cited alongside, same era.
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
2017
Cited alongside, same era.
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
2017
Cited alongside, same era.
K. Ganju, Q. Wang, W. Yang, C. A. Gunter, and N. Borisov, “Property inference attacks on fully connected neural networks using permutation invariant representations,” in ACM Conference on Computer and Communications Security (CCS) , 2018, pp. 619–633
2018
Cited alongside, same era.
Y. Liu, S. Ma, Y. Aafer, W.-C. Lee, J. Zhai, W. Wang, and X. Zhang, “Trojaning attack on neural networks,” in NDSS , 2018
2018
Cited alongside, same era.
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
2018
Cited alongside, same era.
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
Original
2018
Cited alongside, same era.
B. Tran, J. Li, and A. Madry, “Spectral signatures in backdoor attacks,” in Advances in Neural Information Processing Systems , 2018, pp. 8000–8010
2018
Cited alongside, same era.

Then

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
2019
Later among the works it cites.
A. Turner, D. Tsipras, and A. Madry, “Label-consistent backdoor attacks,” arXiv preprint arXiv:1912.02771 , 2019
Original
2019
Later among the works it cites.
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
2019
Later among the works it cites.
T. J. L. Tan and R. Shokri, “Bypassing backdoor detection algorithms in deep learning,” arXiv preprint arXiv:1905.13409 , 2019
Original
2019
Later among the works it cites.
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
2019
Later among the works it cites.
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
2019
Later among the works it cites.
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
2019
Later among the works it cites.
C. L. Information, “Ab-375 privacy: personal information: businesses,” https://leginfo.legislature.ca.gov/faces/billTextClient.xhtml?bill_id=201720180AB375 , accessed: March 2, 2020
2020
Closest in time.
T. Baumhauer, P. Schöttle, and M. Zeppelzauer, “Machine unlearning: Linear filtration for logit-based classifiers,” arXiv preprint arXiv:2002.02730 , 2020
Original
2020
Closest in time.
“Twitter demands AI company stops ‘collecting faces’,” https://www.bbc.com/news/technology-51220654 , 23 Jan, 2020
2020
Closest in time.
M. Chen, Z. Zhang, T. Wang, M. Backes, M. Humbert, and Y. Zhang, “When machine unlearning jeopardizes privacy,” arXiv preprint arXiv:2005.02205 , 2020
Original
2020
Closest in time.
A. Salem, R. Wen, M. Backes, S. Ma, and Y. Zhang, “Dynamic backdoor attacks against machine learning models,” arXiv preprint arXiv:2003.03675 , 2020
Original
2020
Closest in time.
A. Saha, A. Subramanya, and H. Pirsiavash, “Hidden trigger backdoor attacks,” AAAI , 2020
2020
Closest in time.
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
Original
2020
Closest in time.
“Tor Project,” https://www.torproject.org , accessed: March 2, 2020
2020
Closest in time.
S. Neel, A. Roth, and S. Sharifi-Malvajerdi, “Descent-to-delete: Gradient-based methods for machine unlearning,” arXiv preprint arXiv:2007.02923 , 2020
Original
2020
Closest in time.
S. Garg, S. Goldwasser, and P. N. Vasudevan, “Formalizing data deletion in the context of the right to be forgotten,” Cryptology ePrint Archive, Report 2020/254, 2020, https://eprint.iacr.org/2020/254
2020
Closest in time.
A. Sablayrolles, M. Douze, C. Schmid, and H. Jégou, “Radioactive data: tracing through training,” arXiv preprint arXiv:2002.00937 , 2020
Original
2020
Closest in time.
“AG’s corpus of news articles,” http://groups.di.unipi.it/~gulli/AG_corpus_of_news_articles.html , accessed: 2020-03-05
2020
Closest in time.
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
2055
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…