Source-linked AI summary
Detecting Violations of Differential Privacy
Zeyu Ding, Yuxin Wang, Guanhong Wang, Danfeng Zhang, Daniel Kifer
TL;DR
Many published differential privacy algorithms contain bugs, creating a need for understandable counterexamples to claimed privacy guarantees. The paper develops a semi-black-box statistical generator that repeatedly runs candidate algorithms and tests their output distributions. It correctly rejects incorrect algorithms, including published ones, and produces counterexamples within a few seconds, while remaining limited for large datasets and extremely rare violations.
Problem
Differential privacy algorithm design is subtle and error-prone, and many published algorithms violate their claimed privacy.
Method
The paper uses a semi-black-box approach that runs algorithms on varied inputs and applies statistical tests to their output distributions, optionally using symbolic execution for tuning parameters.
Results
Within a few seconds, the tool correctly rejects incorrect algorithms, including published ones, and provides counterexamples for them.
Takeaways & Limitations
Short, human-understandable counterexamples can support development by helping developers evaluate algorithm variations, understand failures, and fix problems.
Takeaways & Limitations
The method may struggle when counterexamples require large datasets or when privacy violations occur extremely rarely, potentially requiring billions of executions.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Differential privacy algorithm design is subtle and error-prone, motivating tools that find privacy violations and generate understandable counterexamples. The paper presents a statistical, semi-black-box counterexample generator intended to support development and tested on incorrect algorithms.
- Published differential privacy algorithms are often incorrect, affecting both novices and experts designing sophisticated privacy-preserving algorithms.
- Counterexamples are intended to help developers quickly evaluate algorithm variations, understand failures, and discard buggy versions during development.
- The paper introduces the first counterexample generator for differential privacy, treating programs as semi-black-boxes and using statistical tests to detect violations.
- The generator is evaluated on sophisticated algorithms such as sparse vector and noisy max, as well as simpler histogram algorithms and incorrect variations.
- Its statistical-testing basis makes false-positive error controllable by reducing the rate through increased testing effort.
- The method is not intended for adversarial settings and may miss violations occurring with extremely small probability.
2 RELATED WORK
Related work includes differential privacy variants, dynamic and static enforcement tools, and symbolic-execution approaches. These approaches do not fully address counterexample detection for probabilistic differential privacy programs.
- Differential privacy: Differential privacy includes pure ϵ-differential privacy and relaxations such as approximate, concentrated, and related definitions.
- Differential privacy: The paper focuses on algorithms with public records of errors or seemingly small changes that break important algorithmic components.
- Programming platforms and verification tools: Dynamic tools track privacy-budget consumption during execution, while static methods verify privacy across executions using relational program logic or type systems.
- Counterexample generation: Existing symbolic-execution work on relational properties applies only to deterministic programs, whereas differential privacy inherently involves probabilistic computation.
3 BACKGROUND
The background defines differential privacy through adjacent databases and a privacy budget, then introduces sensitivity, the Laplace mechanism, and hypothesis testing as foundations for the paper’s approach.
- Differential privacy: Differential privacy compares mechanism outputs on adjacent databases, where adjacency may mean adding or removing one record or modifying one record.
- Differential privacy: The privacy budget ϵ controls privacy strength: smaller ϵ provides stronger privacy guarantees.
- The Laplace mechanism: Global sensitivity measures the worst-case effect of one record on a numerical query and determines the scale of Laplace noise.
- The Laplace mechanism: The Laplace mechanism answers numerical queries by adding independent Laplace noise, and the mechanism is ϵ-differentially private.
- Hypothesis testing: Hypothesis tests reject or fail to reject a null hypothesis and can incur type I errors or type II errors, corresponding to false positives and false negatives.
- Hypothesis testing: A significance level α bounds the probability of a type I error, and the p-value guides rejection when p ≤ α.
- Hypothesis testing: Fisher’s exact test evaluates whether two binomial populations support the alternative p1 > p2 under a null hypothesis p1 ≤ p2.
4 COUNTEREXAMPLE DETECTION
The counterexample generator searches for adjacent inputs and output events that statistically demonstrate a differential-privacy violation. It uses repeated executions, hypothesis tests, and short candidate inputs to produce interpretable counterexamples and characterize detector behavior.
- A counterexample consists of adjacent databases D1 and D2, an output event E, and evidence that P(M(D1) ∈E) > e^ϵP(M(D2) ∈E).
- The generator repeatedly runs the mechanism on candidate inputs, counts outputs in candidate events, and statistically tests whether the differential-privacy inequality is violated.
- Its pipeline generates multiple short candidate input tuples, selects promising output events using exploratory hypothesis tests, and returns the best-scoring combination for further testing.
- For each ϵ, the detector plots the smaller of the two directional p-values, where small p-values indicate evidence for one direction of privacy violation.
- When a mechanism correctly satisfies claimed ϵ0 = 0.7 privacy, p-values rise near 0.7 and remain large for larger ϵ values.
- When a mechanism provides less privacy than advertised, the detector can produce counterexamples at the claimed ϵ and at substantially higher values.
- The statistical approach can struggle when counterexamples require large datasets or violations occur extremely rarely, potentially requiring billions of executions.
- Combining statistical testing with program analysis such as symbolic execution is identified as future work for addressing these limitations.
5 EXPERIMENTS
The framework evaluates privacy mechanisms and their variations by generating statistical evidence of claimed differential-privacy violations. For falsely claiming mechanisms, it produces convincing evidence within a few seconds.
- The implementation includes a hypothesis test, event selector, and input generator for detecting differential-privacy violations.
- The evaluation covers popular privacy mechanisms and incorrect variations.
- For mechanisms that falsely claim differential privacy, the tool produces convincing evidence within a few seconds.
5.1 Noisy Max
Experiments on Noisy Max distinguish correct mechanisms from incorrect variants by testing whether privacy violations emerge near the claimed privacy budget. Returning the maximum value instead of its index causes substantially weaker privacy guarantees.
- Correct variants: Correct Laplace Noisy Max adds independent Lap(2/ϵ0) noise and returns the index of the maximum noisy query answer.
- Correct variants: For privacy budgets ϵ0 of 0.2, 0.7, and 1.5, the correct Laplace variant’s test lines rise near the claimed privacy level.Before ϵ0, the false-rejection chance is almost zero; after ϵ0, the p-value is too large to conclude incorrectness.
- Correct variants: The correct Exponential(2/ϵ0) variant produces test results similar to the correct Laplace variant and likely satisfies the claimed ϵ0-differential privacy.
- Incorrect variants: Returning the maximum value instead of its index makes the Laplace variant satisfy ϵ0 · |Q|/2 differential privacy rather than ϵ0-differential privacy.For ϵ0 = 0.2, its test line rises around test ϵ = 0.4, rejecting the claimed budget.
- Incorrect variants: The incorrect Exponential-noise variant’s test lines rise much later than the claimed privacy budgets, providing strong evidence of incorrectness.For privacy budgets 0.7 and 1.5, p-values remain 0 across test ϵ from 0 to 2.2.
5.2 Histogram
Histogram experiments compare correct Laplace-noise scaling with an incorrect scale and show that the detector rejects the claimed budgets when the actual privacy parameter differs. For ϵ0 = 1.5, the incorrect variant is more private than claimed.
- Algorithm and variants: The Histogram algorithm takes a histogram as input and outputs a noisy histogram with the same dimensions, using Laplace noise.Its input queries differ in at most one element.
- Correct variant: The correct implementation adds independent Lap(1/ϵ0) noise to each query answer and satisfies ϵ0-differential privacy.
- Incorrect variant: The incorrect variant uses Lap(ϵ0) noise and satisfies 1/ϵ0-differential privacy rather than the claimed ϵ0-differential privacy.
- Results: For claimed budgets 0.2 and 0.7, the detector correctly rejects the incorrect variant because its true privacy budgets are 1/0.2 and 1/0.7.
- Results: For ϵ0 = 1.5, the incorrect variant appears more private than claimed, with the test line rising around 0.6 rather than 1.5.This corresponds to an actual privacy level of 1/1.5 = 0.67.
5.3 Sparse Vector
The evaluation tests correct SVT alongside several incorrect variants and shows that the tool identifies their privacy violations, including cases with altered noise, missing bounds, or excessive outputs.
- The SVT variants demonstrate that changes to output bounds, noise scaling, or released values can invalidate claimed privacy guarantees.
- The correct SVT implementation produces test curves rising around its true privacy budget, indicating that the tool recognizes it as private.
- Removing noise and the bound on True outputs makes iSVT 1 non-private for any finite privacy budget.
- iSVT 2, which has no bound on the number of True outputs, is not private for any finite privacy budget.
- For iSVT 3, noise that does not scale with N yields an actual privacy cost of 1+6N/4ϵ0, which the tool detects closely.For ϵ0 = 0.2, the test rises at 0.3 before the actual budget 1+6N/4ϵ0 = 0.35; for ϵ0 = 0.7 and 1.5, it rises at 1.1 and 2.3, near 1.225 and 2.625.
- iSVT 4 is difficult to detect because its violations occur with very low probability, but the tool still concludes that it fails ϵ0-differential privacy.The event selector uses nine booleans followed by a value in (−2.4, 2.4).
5.4 Performance
The experiments use parallel Python implementations and substantial sampling for statistical tests, while test points for every algorithm finish within 23 seconds.
- The experiments run on a 32-logical-core machine with 64 GB memory, using Anaconda Python 3 optimized for parallel execution.
- All tests finish within 23 seconds for one algorithm against one privacy cost.Each test uses 500,000 hypothesis-test samples and 100,000 event-selector and query-generator samples.
- SVT runs faster partly because N is set to 1, so the algorithm halts after reaching a True branch.
- Noisy Max and Histogram take longer because they calculate and apply noise to every query answer.
- Larger event spaces increase search time, as incorrect algorithms returning real values require broader searches than algorithms returning indices.
6 CONCLUSIONS AND FUTURE WORK
The paper presents a semi-black-box method that detects incorrect differentially private algorithms and supplies counterexamples within seconds. Future work targets violations with extremely small probabilities and other privacy definitions.
- The tool rejects incorrect algorithms, including published ones, and provides counterexamples within a few seconds.
- The method addresses the need to detect incorrect algorithms because differential privacy development is subtle.
- Future work will extend detection to privacy violations that occur with extremely small probabilities.
- Planned extensions include approximate differential privacy, zCDP, and Rényi differential privacy.