Detecting Violations of Differential Privacy

By Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, Daniel Kifer. 2018

164 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Sociology and Political Science, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “What techniques can be used for testing FL-implementations for correctness? Since the techniques will often be deployed by organizations who may opt not to open-source code, what are the possibilities for black-box testing? Some works [137, 275] begin to explore this area in the context of different”
Evaluating Differentially Private Machine Learning in Practice (2019, unknown): “[13] and Hay et al.”
Hypothesis Testing Interpretations and Renyi Differential Privacy (2019, methodology): “The hypothesis testing interpretation of differential privacy has also inspired techniques in formal verification [27, 28], including techniques to detect violations in differentially private implementations [8].”
Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning (2021, methodology): “We follow an analysis approach previously employed to audit DP [12, 26].”
Machine Learning Testing: Survey, Landscapes and Horizons (2019, methodology): “[218] treat programs as grey boxes, and detect differential privacy violations via statistical tests.”
Property Testing For Differential Privacy (2018, background): “Recent work by Ding et al. (2018) studies privacy veriﬁcation from a hypothesis testing perspective.”
Differentially Private SQL with Bounded User Contribution (2019, background): “3 is similar to recent work in verification for differential privacy [4, 9], but approaches the problem in a generic way by testing a diverse set of databases that are agnostic to specific algorithms.”
Stochastic Adaptive Line Search for Differentially Private Optimization (2020, background): “Although [12] shows that many extensions of SVT are not private, it also demonstrates the correctness of the original version (used in our approach), which is further confirmed in [18].”
“Amnesia” – Towards Machine Learning Models That Can Forget User Data Very Fast (2019, background): “In contrast to our presented approach, it is very difficult to design differentially private algorithms (even for experts [3]), and this approach requires a difficult decision on the limit on the acceptable privacy loss in practice.”
Proving differential privacy with shadow execution (2019, background): “This appears to be an important property in light of recent work on detecting counterexamples for buggy programs [12, 17, 23, 24].”