Detecting Violations of Differential Privacy
This addresses the issue for developers of differential privacy algorithms by enabling quick detection of privacy violations during development, though it is incremental as it builds on existing statistical testing methods.
The paper tackled the problem of detecting bugs in differential privacy algorithms by generating short, human-understandable counterexamples using a statistical approach, and it validated the method by correctly rejecting incorrect algorithms and providing counterexamples within seconds.
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.