Group and Attack: Auditing Differential Privacy

𝜖, 𝛿) differential privacy has seen increased adoption recently, especially in private machine learning applications. While this privacy definition allows provably limiting the amount of information leaked by an algorithm, practical implementations of differentially private algorithms often contain subtle vulnerabilities. This motivates the need for effective tools that can audit (𝜖, 𝛿) differential privacy algorithms before deploying them in the real world. However, existing state-of-the-art-tools for auditing (𝜖, 𝛿) differential privacy directly extend the tools for 𝜖-differential privacy by fixing either 𝜖 or 𝛿 in the violation search, inherently restricting their ability to efficiently discover violations of (𝜖, 𝛿) differential privacy. We present a novel method to efficiently discover (𝜖, 𝛿) differential privacy violations based on the key insight that many (𝜖, 𝛿) pairs can be grouped as they result in the same algorithm. Crucially, our method is orthogonal to existing approaches and, when combined, results in a faster and more precise violation search. We implemented our approach in a tool called Delta-Siege and demonstrated its effectiveness by discovering vulnerabilities in most of the evaluated frameworks, several of which were previously unknown. Further, in 84% of cases, Delta-Siege outperforms existing state-of-the-art auditing tools. Finally, we show how Delta-Siege outputs can be used to find the precise root cause of vulnerabilities, an option no other differential privacy testing tool currently offers. CCS CONCEPTS • Security and privacy → Privacy-preserving protocols; • Mathematics of computing → Statistical software.