💻 computer science

SuperDP: Differential Privacy Refutation via Supermartingales

This paper introduces SuperDP, a fully automated and sound method for refuting $\epsilon$ -differential privacy in stochastic mechanisms with both discrete and continuous distributions by simultaneously searching for violating inputs and a distinguishing function using supermartingales and submartingales.

Original authors: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, {\DJ}or{\dj}e Žikelić

Published 2026-03-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, {\DJ}or{\dj}e Žikelić

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a baker running a very popular cookie shop. You want to share statistics about your cookies (like "50% are chocolate chip") with the public, but you have a strict rule: No one should be able to figure out if a specific customer, let's call "Alice," bought a cookie or not.

This is the world of Differential Privacy (DP). It's a mathematical promise that says, "If I change just one person's data in my database, the final statistics shouldn't change much."

However, proving that your recipe actually keeps this promise is incredibly hard. It's like trying to prove a magic trick works by explaining every single move, but the moves involve rolling dice, flipping coins, and mixing ingredients in ways that are hard to predict. Sometimes, a baker thinks they are safe, but a tiny tweak in the recipe accidentally reveals Alice's secret.

The Problem: How do we catch the "leaky" recipes?

In the past, researchers had two ways to check if a recipe was safe:

The "Try and Hope" Method (Dynamic): Run the recipe a million times, look at the results, and guess if it's safe. This is fast but unreliable. It might miss a rare leak.
The "Strict Accountant" Method (Static): Try to mathematically prove the recipe is safe. This is very reliable but often gets stuck on complex recipes, especially those involving continuous numbers (like adding a random amount of sugar that could be any number between 0 and 1).

Most existing tools could either be fast but unreliable, or reliable but only work on simple, "countable" recipes (like rolling a 6-sided die). They struggled with the "real-world" recipes that use continuous distributions (like the Laplace distribution, which is the standard "noise" added to protect privacy).

The Solution: SuperDP

The authors of this paper, SuperDP, have built a new tool that acts like a super-detective for these privacy recipes. Their goal isn't to prove the recipe is safe; it's to refute it—to find a specific case where the recipe fails and leaks privacy.

Here is how they do it, using a simple analogy:

The "Expectation Mismatch" Detective

Imagine you have two nearly identical versions of your cookie recipe.

Recipe A: Alice bought a cookie.
Recipe B: Alice did not buy a cookie.

If the recipes are truly private, the "average outcome" of the statistics should be almost identical. But if they aren't, there's a leak.

The Old Way: The detective would try to find a specific event (e.g., "The number of chocolate chip cookies is exactly 10") where the probability changes too much between Recipe A and Recipe B. This is like looking for a needle in a haystack.

The SuperDP Way: Instead of looking for a specific event, SuperDP invents a special scoring function.

Imagine a function $f$ that gives points to the output. Maybe it gives 100 points if the result is "Chocolate Chip" and 0 otherwise.
SuperDP asks: "Is there any way to score the results such that the average score for Recipe A is significantly higher than the average score for Recipe B?"

If the answer is YES, then the privacy promise is broken! It doesn't matter what the specific event is; if the "average score" is different, the privacy is leaking.

The Secret Weapon: Martingales (The "Magic Balancing Scale")

How does SuperDP calculate these "average scores" without running the recipe a million times? It uses a mathematical concept called Supermartingales and Submartingales.

Think of a Supermartingale as a magic balancing scale that predicts the maximum possible average score you could get.
Think of a Submartingale as a magic balancing scale that predicts the minimum possible average score.

SuperDP works by:

Picking two similar inputs (Alice vs. No-Alice).
Inventing a scoring function ( $f$ ).
Using these "magic scales" to calculate a Lower Bound (the minimum score for Alice) and an Upper Bound (the maximum score for No-Alice).
The Refutation: If the Lower Bound for Alice is still higher than the Upper Bound for No-Alice (even after accounting for the privacy budget), then the recipe is definitely broken. The scales have tipped too far!

Why is this a big deal?

The paper claims SuperDP is the first tool to check four boxes that previous tools missed:

Fully Automated: You don't need a human to guide it; it finds the leak on its own.
Handles Real Numbers: It works with continuous distributions (like adding random noise that can be any decimal number), which is how real privacy systems work.
Sound: If it says "Leak Found!", it is 100% mathematically guaranteed to be true. No guessing.
Semi-Complete: If a leak exists and is "findable" with polynomial math, SuperDP is guaranteed to find it.

The Results

The authors tested their tool on 15 different "recipes" (privacy mechanisms) from the literature.

SuperDP found leaks in 13 out of 15 cases, often finding tighter (more precise) leaks than the competition.
It was fast, usually taking less than a second.
It solved problems that other tools couldn't touch, including some that required complex math or continuous noise.

The Limitations

Like any tool, it's not perfect yet:

It works best with "polynomial" math (equations involving powers like $x^2$ or $x^3$ ). If the recipe involves weird, non-polynomial math, it might struggle.
It currently only checks for $\epsilon$ -DP (the strict version of privacy). It doesn't yet handle the slightly looser $(\epsilon, \delta)$ -DP version, which is also common in the real world.

In Summary

SuperDP is a new, automated "privacy leak detector." Instead of trying to prove a system is safe (which is hard), it tries to prove it is unsafe by finding a specific scenario where the math breaks. It uses "magic balancing scales" (martingales) to do this quickly and accurately, even for complex, real-world privacy systems. It's a major step forward in making sure our private data stays private.

1. Problem Statement

Differential Privacy (DP) is a standard for ensuring individual privacy in randomized computations. A program $P$ is $\epsilon$ -differentially private if, for any two "similar" inputs $x_1$ and $x_2$ (e.g., differing by one record), the probability distributions of their outputs are close, satisfying:
$P_{x_1}[\text{Output}(A)] \leq e^\epsilon \cdot P_{x_2}[\text{Output}(A)]$
for all output events $A$ .

The paper addresses the DP Refutation Problem: proving that a given stochastic mechanism is not $\epsilon$ -DP.

Challenge: DP checking is undecidable for Turing-complete probabilistic programs.
Limitations of Existing Methods:
- Dynamic/Statistical Methods: Rely on sampling and hypothesis testing. They lack formal soundness guarantees (risk of false positives/negatives) and often require massive computational resources.
- Static Methods: Most existing tools are either not fully automated, restricted to discrete/countable domains (excluding continuous distributions like Laplacian), or lack completeness guarantees.
- Gap: No existing method offers a combination of full automation, support for continuous distributions, soundness, and semi-completeness.

2. Methodology

The authors propose SuperDP, a novel method for automated $\epsilon$ -DP refutation based on Expectation Mismatch and Martingale Theory.

Core Concept: Expectation Mismatch

Instead of searching for a specific output event $A$ that violates the DP inequality, the method searches for a non-negative function $f$ over the program outputs and a pair of similar inputs $x_1, x_2$ such that:
$E_{x_1}[f] > e^\epsilon \cdot E_{x_2}[f]$
The authors prove that such a function $f$ exists if and only if the program violates $\epsilon$ -DP.

Technical Pillars

To compute these expectations without needing closed-form solutions (which are often infeasible for complex loops), the method utilizes:

Upper Expectation Supermartingales (UESMs): Provide sound upper bounds on $E_{x_2}[f]$ .
Lower Expectation Submartingales (LESMs): Provide sound lower bounds on $E_{x_1}[f]$ .
The Witness Tuple: The method synthesizes a tuple $(x_1, x_2, f, L_f, U_f)$ $(x_{1}, x_{2}, f, L_{f}, U_{f})$ where:
- $x_1, x_2$ are similar inputs.
- $f$ is a non-negative function.
- $L_f$ is an LESM yielding a lower bound $L \leq E_{x_1}[f]$ .
- $U_f$ is a UESM yielding an upper bound $U \geq E_{x_2}[f]$ .
- Refutation Condition: $L > e^\epsilon \cdot U$ .

Algorithm: Template-Based Synthesis

The authors designed a sound and conditionally semi-complete algorithm to find this witness:

Assumptions: The algorithm targets polynomial arithmetic probabilistic programs (allowing sampling from non-polynomial distributions like Laplacian/Normal, provided the arithmetic expressions in assignments are polynomial).
Templates: It fixes symbolic polynomial templates for the inputs ( $x_1, x_2$ ), the function ( $f$ ), and the martingales ( $L_f, U_f$ ).
Constraint Generation: It generates a system of constraints ensuring:
- The similarity relation holds.
- $f$ is non-negative.
- $L_f$ and $U_f$ satisfy the martingale conditions (Expected $f$ -increase/decrease) and OST-soundness conditions (ensuring bounds are valid).
- The inequality $L > e^\epsilon \cdot U$ holds.
Quantifier Elimination: Uses Handelman's Theorem to convert universal quantifiers (over program states) into existential constraints over template coefficients.
Solving: An SMT solver (e.g., Z3) solves the resulting system. If a solution exists, the program is refuted.

3. Key Contributions

The paper makes four primary contributions, addressing the limitations of prior work:

Sound and Complete Proof Rule:
- Introduces the Expectation Super/Sub-martingale Witness for $\epsilon$ -DP refutation.
- Proves this rule is sound (if a witness exists, the program is not DP) and complete (if the program is not DP, such a witness exists) for general probabilistic programs with Borel-measurable arithmetic and discrete/continuous sampling.
Fully Automated Algorithm:
- Develops a template-based synthesis algorithm that is sound and conditionally semi-complete.
- It is the first method to simultaneously offer:
  - Full automation.
  - Support for both discrete and continuous distributions (e.g., Laplacian).
  - Formal soundness guarantees.
  - Semi-completeness guarantees (guaranteed to find a refutation if the witness can be expressed as polynomials).
Prototype Tool (SuperDP):
- Implemented a Java-based tool using Z3/MathSAT5 and ASPIC for invariant generation.
- Capable of handling polynomial arithmetic programs with general sampling instructions.
Experimental Validation:
- Demonstrated superior performance over state-of-the-art tools (CheckDP, StatDP) on 15 benchmarks.
- Successfully refuted $\epsilon$ -DP for challenging examples previously out of reach (e.g., mechanisms with unbounded loops or complex continuous distributions).

4. Experimental Results

The authors evaluated SuperDP against CheckDP (static) and StatDP (dynamic) on 15 benchmarks, including standard mechanisms (Histogram, Randomized Response, SVT) and complex variants.

Effectiveness (RQ1): SuperDP successfully refuted $\epsilon$ -DP for 13 out of 15 benchmarks. It found tighter bounds (larger $\epsilon$ values) than baselines in 13 cases. Notably, it handled the "geometric" mechanism (unbounded loop) and "lowprob" (rare events) where statistical methods failed or were unsound.
Efficiency (RQ2): SuperDP was faster than baselines in 11 out of 15 cases, often completing in under 1 second. It only timed out on benchmarks with very large constraint systems (e.g., NoisyMax, SVT) due to the complexity of symbolic probability reasoning in conditional branches.
Limitations (RQ3):
- Struggles with symbolic reasoning about probabilities of if-branching where the condition involves continuous variables (e.g., if x >= y where x is Laplacian).
- Performance degrades with high-degree polynomial templates required for complex noise distributions.

5. Significance

Theoretical Breakthrough: This is the first work to provide a sound and complete proof rule for $\epsilon$ -DP refutation using martingales, bridging the gap between probabilistic program analysis and privacy verification.
Practical Impact: It enables the automated detection of privacy flaws in complex, real-world mechanisms involving continuous noise (Laplacian/Gaussian), which are standard in DP but difficult for previous static analyzers.
Future Directions: The authors identify extending the method to $(\epsilon, \delta)$ -DP and non-polynomial arithmetic programs as key avenues for future research.

In summary, SuperDP represents a significant advancement in formal privacy verification, offering a robust, automated, and mathematically rigorous framework for proving that a system fails to meet differential privacy guarantees.