TY - GEN
T1 - Detecting violations of differential privacy
AU - Ding, Zeyu
AU - Wang, Yuxin
AU - Wang, Guanhong
AU - Zhang, Danfeng
AU - Kifer, Daniel
N1 - Funding Information:
We thank anonymous CCS reviewers for their helpful suggestions. This work was partially funded by NSF awards #1228669, #1702760 and #1566411.
Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/10/15
Y1 - 2018/10/15
N2 - The widespread acceptance of differential privacy has led to the publication of many sophisticated algorithms for protecting privacy. However, due to the subtle nature of this privacy definition, many such algorithms have bugs that make them violate their claimed privacy. In this paper, we consider the problem of producing counterexamples for such incorrect algorithms. The counterexamples are designed to be short and human-understandable so that the counterexample generator can be used in the development process - a developer could quickly explore variations of an algorithm and investigate where they break down. Our approach is statistical in nature. It runs a candidate algorithm many times and uses statistical tests to try to detect violations of differential privacy. An evaluation on a variety of incorrect published algorithms validates the usefulness of our approach: it correctly rejects incorrect algorithms and provides counterexamples for them within a few seconds.
AB - The widespread acceptance of differential privacy has led to the publication of many sophisticated algorithms for protecting privacy. However, due to the subtle nature of this privacy definition, many such algorithms have bugs that make them violate their claimed privacy. In this paper, we consider the problem of producing counterexamples for such incorrect algorithms. The counterexamples are designed to be short and human-understandable so that the counterexample generator can be used in the development process - a developer could quickly explore variations of an algorithm and investigate where they break down. Our approach is statistical in nature. It runs a candidate algorithm many times and uses statistical tests to try to detect violations of differential privacy. An evaluation on a variety of incorrect published algorithms validates the usefulness of our approach: it correctly rejects incorrect algorithms and provides counterexamples for them within a few seconds.
UR - http://www.scopus.com/inward/record.url?scp=85056847220&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056847220&partnerID=8YFLogxK
U2 - 10.1145/3243734.3243818
DO - 10.1145/3243734.3243818
M3 - Conference contribution
AN - SCOPUS:85056847220
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 475
EP - 489
BT - CCS 2018 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
T2 - 25th ACM Conference on Computer and Communications Security, CCS 2018
Y2 - 15 October 2018
ER -