Detecting Violations of Differential Privacy

Abstract

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.

arXiv comment15 pages, 4 figures, CCS'18

References in corpus (5)

• Proving Differential Privacy via Probabilistic Couplings
• LightDP: Towards Automating Differential Privacy Proofs
• Proving differential privacy in Hoare logic
• Advanced Probabilistic Couplings for Differential Privacy
• Synthesizing Coupling Proofs of Differential Privacy

Cited by in corpus (13)

• Proving Differential Privacy with Shadow Execution
• CheckDP: An Automated and Integrated Approach for Proving Differential Privacy or Finding Precise Counterexamples
• Quantum Pufferfish Privacy: A Flexible Privacy Framework for Quantum Systems
• Detecting Violations of Differential Privacy for Quantum Algorithms
• DPGen: Automated Program Synthesis for Differential Privacy
• Deciding Accuracy of Differential Privacy Schemes
• Pufferfish Privacy: An Information-Theoretic Study
• How reparametrization trick broke differentially-private text representation learning
• Revealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective
• The Complexity of Verifying Boolean Programs as Differentially Private
• QueryCheetah: Fast Automated Discovery of Attribute Inference Attacks Against Query-Based Systems
• Curator Attack: When Blackbox Differential Privacy Auditing Loses Its Power
• Approximate Algorithms for Verifying Differential Privacy with Gaussian Distributions