💻 computer science

SuperDP: Differential Privacy Refutation via Supermartingales

Die Arbeit stellt SuperDP vor, ein vollautomatisiertes Werkzeug zur formalen Widerlegung von $\epsilon$ -Differential Privacy, das durch die gleichzeitige Berechnung von Eingaben und einer nicht-negativen Funktion mittels Supermartingalen und Submartingalen sowohl für diskrete als auch kontinuierliche Verteilungen anwendbar ist und dabei Soundness sowie Semi-Vollständigkeit garantiert.

Ursprüngliche Autoren: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, {\DJ}or{\dj}e Žikelić

Veröffentlicht 2026-03-30

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Krishnendu Chatterjee, Ehsan Kafshdar Goharshady, {\DJ}or{\dj}e Žikelić

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stell dir vor, du hast eine geheime Maschine, die Daten verarbeitet. Diese Maschine soll dir nützliche Statistiken liefern (z. B. „Wie viele Menschen in dieser Stadt rauchen?"), aber sie darf niemals verraten, ob eine bestimmte Person in der Liste ist oder nicht. Das nennt man Differential Privacy (Differenzielle Privatsphäre).

Das Problem ist: Diese Maschinen sind oft kompliziert programmiert. Ein winziger Fehler im Code kann die Privatsphäre komplett zerstören. Bisher war es sehr schwer, automatisch zu prüfen, ob eine solche Maschine wirklich sicher ist oder ob sie einen „Leck" hat.

Die Autoren dieses Papers haben ein neues Werkzeug namens SuperDP entwickelt. Hier ist die Erklärung, wie es funktioniert, ganz ohne Fachchinesisch:

1. Das Problem: Der „Leck-Test"

Stell dir vor, du hast zwei fast identische Versionen einer Datenbank. In Version A ist eine Person (nennen wir sie „Max") enthalten. In Version B ist Max nicht enthalten. Alles andere ist gleich.

Eine sichere Maschine sollte bei beiden Versionen fast das gleiche Ergebnis liefern. Wenn das Ergebnis bei Version A aber drastisch anders ist als bei Version B, dann hat die Maschine „geleckt" – sie verrät, dass Max dabei war.

Frühere Methoden, um solche Lecks zu finden, waren wie ein blindes Suchen:

Die Statistiker: Sie haben die Maschine millionenfach laufen lassen und gehofft, dass sie zufällig einen Fehler finden. Das ist wie ein Lotteriespiel: Es kann dauern, und es gibt keine Garantie, dass es funktioniert.
Die alten Prüfer: Sie konnten nur sehr einfache Maschinen prüfen oder brauchten menschliche Hilfe.

2. Die neue Idee: Der „Zauberspiegel" (Supermartingale)

SuperDP macht etwas Cleveres. Statt zu raten, wie die Maschine sich verhält, baut es einen mathematischen Spiegel (einen sogenannten Supermartingal-Witness).

Stell dir vor, du hast zwei identische Rennwagen (die beiden Datenbanken mit und ohne Max). Du willst wissen, ob der eine Wagen schneller ist als der andere, obwohl sie fast gleich aussehen.

Anstatt den Wagen zu starten und zu schauen, wer gewinnt, baust du eine Wettervorhersage (den Spiegel) für beide Wagen:

Du sagst: „Wenn Wagen A fährt, wird er mindestens so viel Treibstoff verbrauchen wie X."
Und: „Wenn Wagen B fährt, wird er höchstens so viel Treibstoff verbrauchen wie Y."

Wenn du beweisen kannst, dass X immer größer ist als Y, dann weißt du zu 100 %: Die beiden Wagen verhalten sich unterschiedlich! Es muss also ein Leck geben.

In der Sprache der Autoren:

Sie suchen nicht nach einem spezifischen Ergebnis (z. B. „Max wurde erkannt").
Sie suchen nach einer Funktion (einer Art Rechenformel), die auf die Ergebnisse angewendet wird.
Wenn diese Funktion für den Fall „mit Max" im Durchschnitt einen viel höheren Wert liefert als für den Fall „ohne Max" (und zwar um einen Faktor, der größer ist als das erlaubte Sicherheitslimit), dann ist die Maschine nicht sicher.

3. Wie SuperDP das automatisch macht

Das Geniale an SuperDP ist, dass es diesen „Zauberspiegel" (die Funktion und die Grenzen) automatisch konstruiert.

Der Suchprozess: Das Programm denkt sich gleichzeitig zwei Dinge aus:
1. Zwei fast gleiche Eingaben (z. B. „Datenbank mit Max" vs. „Datenbank ohne Max").
2. Die perfekte Rechenformel, die den Unterschied zwischen diesen beiden Fällen so stark herausstellt, dass die Privatsphäre gebrochen ist.
Die Beweiskette: Es nutzt mathematische Werkzeuge (Super- und Submartingale), die garantieren: „Wenn wir diese Formel finden, dann ist der Beweis zu 100 % korrekt." Es gibt keine Zufallswahrscheinlichkeiten wie bei den alten Methoden.

4. Warum ist das so toll? (Die 4 Superkräfte)

Das Papier hebt vier Dinge hervor, die SuperDP besser macht als alles, was es vorher gab:

Vollautomatisch: Du musst nichts manuell eingeben. Das Programm findet den Fehler allein.
Universell: Es funktioniert auch mit komplexen Zufallsprozessen (wie dem Werfen von Würfeln oder dem Ziehen aus einer Glockenkurve), die in der echten Welt üblich sind.
Wahrheitssicher (Soundness): Wenn SuperDP sagt „Hier ist ein Leck!", dann ist es garantiert ein Leck. Kein „vielleicht".
Fast vollständig (Semi-completeness): Wenn ein Leck existiert und es mathematisch machbar ist, es mit dieser Methode zu finden, wird SuperDP es auch finden. Es gibt nicht einfach auf.

Zusammenfassung in einer Metapher

Stell dir vor, du willst herausfinden, ob ein Zauberer (die Maschine) ehrlich ist oder ob er Tricks benutzt.

Die alten Methoden waren wie: „Wir schauen uns 10.000 Zaubertricks an und hoffen, dass wir einen Fehler sehen." (Langsam, ungenau).
SuperDP ist wie ein perfekter Detektiv, der sofort eine spezielle Brille aufsetzt. Durch diese Brille sieht er sofort, ob der Zauberer bei zwei fast identischen Tricks unterschiedliche Ergebnisse liefert. Wenn ja, hat er den Betrug bewiesen – und zwar mit einem mathematischen Beweis, der nicht widerlegt werden kann.

Das Ergebnis: SuperDP hat in Tests viele schwierige Beispiele gefunden, bei denen andere Tools versagt haben, und hat dabei oft schneller gearbeitet. Es ist ein mächtiges neues Werkzeug, um die Privatsphäre in der digitalen Welt zu schützen.

1. Problemstellung

Differential Privacy (DP) ist ein etablierter Standard zum Schutz der Privatsphäre individueller Daten in probabilistischen Algorithmen. Die formale Verifikation von DP-Eigenschaften ist jedoch schwierig und fehleranfällig. Während es bereits Methoden zur Verifikation (Beweis, dass ein Mechanismus DP erfüllt) gibt, ist die Refutation (Beweis, dass ein Mechanismus DP nicht erfüllt) ein weniger bearbeitetes, aber ebenso wichtiges Problem.

Das Ziel der Arbeit ist die Entwicklung einer Methode zur automatisierten formalen Refutation von $\epsilon$ -DP. Das Problem besteht darin, für einen gegebenen probabilistischen Programm (PP) und einen Ähnlichkeitsbegriff zwischen Eingaben ( $\sim_\Phi$ ) ein Paar ähnlicher Eingaben $(x_1, x_2)$ zu finden, für das die DP-Ungleichung verletzt ist:
$P_{x_1}[\text{Output}(A)] > e^\epsilon \cdot P_{x_2}[\text{Output}(A)]$
für eine Menge von Ausgaben $A$ .

Herausforderungen bestehender Methoden:

Statische Methoden: Oft nicht vollständig automatisiert oder auf diskrete/endliche Programme beschränkt (keine Unterstützung für kontinuierliche Verteilungen wie Laplace).
Dynamische Methoden: Basieren auf Sampling und statistischen Schätzungen, bieten keine formalen (sounden) Garantien und können bei seltenen Ereignissen versagen.
Lücken: Keine bestehende Methode bot gleichzeitig: (1) Vollständige Automatisierung, (2) Unterstützung für diskrete und kontinuierliche Verteilungen, (3) Soundness-Garantien und (4) Semi-Vollständigkeit.

2. Methodik: Erwartungswert-Mismatch und Martingale

Die Kernidee von SuperDP ist es, die Suche nach einem spezifischen Ausgabeereignis $A$ (das schwer zu finden ist) durch die Suche nach einer nicht-negativen Funktion $f$ über den Ausgaben zu ersetzen.

Das Konzept des Erwartungswert-Mismatch

Statt direkt die Wahrscheinlichkeiten zu vergleichen, sucht das Verfahren nach einem Paar ähnlicher Eingaben und einer Funktion $f$ , sodass der Erwartungswert von $f$ auf den Ausgaben für $x_1$ signifikant größer ist als für $x_2$ :
$E_{x_1}[f] > e^\epsilon \cdot E_{x_2}[f]$
Es wird bewiesen, dass dies eine notwendige und hinreichende Bedingung für die Verletzung von $\epsilon$ -DP ist.

Berechnung mittels Super- und Submartingale

Da die exakte Berechnung von Erwartungswerten in probabilistischen Programmen oft unmöglich ist (keine geschlossene Form), nutzt SuperDP Upper Expectation Supermartingales (UESM) und Lower Expectation Submartingales (LESM).

Ein UESM $U_f$ liefert eine obere Schranke für den Erwartungswert: $U_f(\ell_{in}, x_2) \ge E_{x_2}[f]$ .
Ein LESM $L_f$ liefert eine untere Schranke für den Erwartungswert: $L_f(\ell_{in}, x_1) \le E_{x_1}[f]$ .

Die Methode sucht nach einem Witness-Tupel $(x_1, x_2, f, L_f, U_f)$ , das folgende Bedingungen erfüllt:

$x_1 \sim_\Phi x_2$ (ähnliche Eingaben).
$f$ ist eine nicht-negative Funktion.
$L_f$ und $U_f$ sind gültige Martingale (erfüllen die OST-Soundness-Bedingungen).
Die Ungleichung gilt: $L_f(\ell_{in}, x_1) + f(x_{out}) > e^\epsilon \cdot (U_f(\ell_{in}, x_2) + f(x_{out}))$ .

Dieser Ansatz wandelt das Problem der DP-Refutation in ein Problem der Synthese von Polynomen um.

Automatisierung durch Template-basierte Synthese

Der Algorithmus verwendet einen Template-basierten Ansatz:

Vorlagen: Es werden symbolische Polynom-Vorlagen für die Eingaben $x_1, x_2$ , die Funktion $f$ und die Martingale $L_f, U_f$ definiert (bis zu einem bestimmten Grad $D$ ).
Constraint-Sammlung: Aus den Definitionen der Martingale und der DP-Bedingung wird ein System von polynomialen Constraints über die Koeffizienten der Vorlagen abgeleitet.
Quantorenelimination: Mittels Handlemans Theorem werden universell quantifizierte Constraints (für alle Zustände) in existenzielle Constraints umgewandelt.
Lösung: Ein SMT-Solver (z.B. Z3) löst das resultierende System. Eine Lösung liefert einen formalen Beweis für die DP-Verletzung.

3. Wichtige Beiträge

Theorie: Einführung eines sounden und vollständigen Beweisregeln für die $\epsilon$ -DP-Refutation in probabilistischen Programmen mit allgemeinen Borel-messbaren Ausdrücken und Sampling aus diskreten sowie kontinuierlichen Verteilungen.
Algorithmus: Entwicklung eines vollautomatischen, sounden und bedingt semi-vollständigen Algorithmus für polynomielle arithmetische probabilistische Programme.
Werkzeug (SuperDP): Implementierung eines Prototyps, der die Methode praktisch anwendet.
Vier gewünschte Eigenschaften: SuperDP ist die erste Methode, die alle vier Kriterien erfüllt:
- Vollautomatisch.
- Anwendbar auf Mechanismen mit diskreten und kontinuierlichen Verteilungen (z.B. Laplace, Normal).
- Bietet Soundness-Garantien (formaler Beweis).
- Bietet Semi-Vollständigkeits-Garantien (findet ein Gegenbeispiel, wenn eines in der Klasse der Polynome existiert).

4. Experimentelle Ergebnisse

Das Team evaluierte SuperDP an 15 probabilistischen Programmen aus der Literatur (z.B. Randomized Response, Histogramm, Geometrischer Mechanismus, SVT) und verglich es mit dem State-of-the-Art:

Baselines: CheckDP (statische Analyse) und StatDP (dynamische/statistische Analyse).
Ergebnisse:
- Effektivität: SuperDP konnte auf 13 von 15 Benchmarks DP widerlegen, oft mit engeren Schranken ( $\epsilon$ ) als die Konkurrenz. CheckDP scheiterte bei einigen Beispielen aufgrund von Laufzeitfehlern oder fehlender Unterstützung für bestimmte Verteilungen (z.B. Geometrisch, Bernoulli). StatDP lieferte bei seltenen Ereignissen (z.B. "lowprob"-Benchmark) falsche Ergebnisse oder scheiterte.
- Effizienz: In 11 von 15 Fällen war SuperDP schneller als die Baselines. Die Laufzeiten lagen meist unter 3 Sekunden.
- Grenzen: Das Tool hatte Schwierigkeiten bei Benchmarks, die eine symbolische Berechnung von Wahrscheinlichkeiten in bedingten Verzweigungen erfordern (z.B. if x >= y mit $x \sim \text{Laplace}$ ), da dies schwer durch Polynom-Vorlagen zu erfassen ist. Auch sehr große Constraint-Systeme (hoher Polynomgrad) können die SMT-Solver überfordern.

5. Bedeutung und Ausblick

Die Arbeit stellt einen bedeutenden Fortschritt in der formalen Verifikation von Differential Privacy dar. Sie überwindet die Lücke zwischen theoretischer Soundness und praktischer Automatisierung, insbesondere für Programme mit kontinuierlichen Verteilungen, die in der Praxis Standard sind.

Limitationen und zukünftige Arbeit:

Der Ansatz ist derzeit auf $\epsilon$ -DP beschränkt und lässt sich nicht direkt auf $(\epsilon, \delta)$ -DP erweitern, da die Erwartungswert-Mismatch-Logik dort nicht mehr sound ist.
Die Methode ist auf Programme mit polynomiellen arithmetischen Ausdrücken beschränkt (obwohl Sampling aus nicht-polynomiellen Verteilungen erlaubt ist).
Die Erweiterung auf andere Privatsphären-Notionen und die Verifikation (statt nur Refutation) sind offene Forschungsfragen.

Zusammenfassend bietet SuperDP ein robustes, mathematisch fundiertes Werkzeug, um Sicherheitslücken in DP-Implementierungen automatisch und formal nachzuweisen, wo bisherige Methoden an ihre Grenzen stießen.