Differenzierte Privatsphäre (DP) ist eine Eigenschaft randomisierter Mechanismen, die den Einfluss der Informationen einzelner Benutzer bei der Verarbeitung und Analyse von Daten begrenzen. DP bietet eine robuste Lösung, um den wachsenden Bedenken hinsichtlich des Datenschutzes Rechnung zu tragen und Technologien zu ermöglichen über Branchen und staatliche Anwendungen (z. B. die US-Volkszählung), ohne die Identität einzelner Benutzer zu gefährden. Mit zunehmender Akzeptanz ist es wichtig, die potenziellen Risiken der Entwicklung von Mechanismen mit fehlerhaften Implementierungen zu identifizieren. Forscher haben kürzlich Fehler in den mathematischen Beweisen privater Mechanismen und ihrer Implementierungen gefunden. Zum Beispiel, Forscher verglichen sechs SVT-Varianten (Sparse Vector Approach) und stellte fest, dass nur zwei der sechs tatsächlich die geltend gemachte Datenschutzgarantie erfüllten. Selbst wenn mathematische Beweise korrekt sind, ist der Code, der den Mechanismus implementiert, anfällig für menschliches Versagen.
Allerdings ist eine praktische und effiziente DP-Prüfung vor allem aufgrund der inhärenten Zufälligkeit der Mechanismen und der probabilistischen Natur der getesteten Garantien eine Herausforderung. Darüber hinaus gibt es eine Reihe von Garantiearten (z. B. reine DP, ungefährer DP, Rényi DPUnd konzentriertes DP), und diese Vielfalt trägt zur Komplexität der Formulierung des Prüfungsproblems bei. Darüber hinaus ist das Debuggen mathematischer Beweise und Codebasen angesichts der Menge der vorgeschlagenen Mechanismen eine schwierige Aufgabe. Während advert hoc Obwohl Testtechniken unter bestimmten Annahmen von Mechanismen existieren, wurden nur wenige Anstrengungen unternommen, um ein erweiterbares Software zum Testen von DP-Mechanismen zu entwickeln.
Zu diesem Zweck in „DP-Auditorium: Eine umfangreiche Bibliothek zur Prüfung der differenziellen Privatsphäre“, stellen wir vor Open-Supply-Bibliothek zur Prüfung von DP-Garantien mit nur Black-Field-Zugriff auf einen Mechanismus (dh ohne Kenntnis der internen Eigenschaften des Mechanismus). DP-Auditorium ist in Python implementiert und bietet eine versatile Schnittstelle, die es Beiträgen ermöglicht, seine Testfunktionen kontinuierlich zu verbessern. Wir stellen außerdem neue Testalgorithmen vor, die eine Divergenzoptimierung über Funktionsräume für Rényi DP, reines DP und angenähertes DP durchführen. Wir zeigen, dass DP-Auditorium Verstöße gegen DP-Garantien effizient identifizieren kann, und schlagen vor, welche Exams am besten geeignet sind, um bestimmte Fehler im Rahmen verschiedener Datenschutzgarantien zu erkennen.
DP-Garantien
Die Ausgabe eines DP-Mechanismus ist eine Stichprobe aus einer Wahrscheinlichkeitsverteilung (M (D)), das eine mathematische Eigenschaft erfüllt, die die Vertraulichkeit von Benutzerdaten gewährleistet. Eine DP-Garantie ist daher eng mit Eigenschaften zwischen Paaren von Wahrscheinlichkeitsverteilungen verbunden. Ein Mechanismus ist differenziell privat, wenn die Wahrscheinlichkeitsverteilungen bestimmt werden durch M auf Datensatz D und ein benachbarter Datensatz D‘die sich nur um einen Datensatz unterscheiden, sind nicht zu unterscheiden unter einer gegebenen Divergenzmetrik.
Zum Beispiel die Klassik ungefährer DP Die Definition besagt, dass ein Mechanismus ungefähr DP mit Parametern ist (ε, δ), wenn die Hockeyschläger-Divergenz der Ordnung eεzwischen M(D) Und M(D‘), ist höchstens δ. Reiner DP ist ein Sonderfall des ungefähren DP, bei dem δ = 0. Abschließend wird ein Mechanismus betrachtet Rényi DP mit Parametern (𝛼, ε) wenn die Rényi-Divergenz der Ordnung 𝛼ist höchstens ε (Wo ε ist ein kleiner positiver Wert). In diesen drei Definitionen ε ist nicht austauschbar, vermittelt aber intuitiv das gleiche Konzept; größere Werte von ε bedeuten größere Abweichungen zwischen den beiden Verteilungen oder weniger Privatsphäre, da die beiden Verteilungen leichter zu unterscheiden sind.
DP-Auditorium
DP-Auditorium besteht aus zwei Hauptkomponenten: Eigenschaftstestern und Datensatzfindern. Eigenschaftstester nehmen Stichproben aus einem Mechanismus, der an bestimmten Datensätzen als Eingabe ausgewertet wird, und zielen darauf ab, Verstöße gegen die Datenschutzgarantie in den bereitgestellten Datensätzen zu identifizieren. Datensatzfinder schlagen Datensätze vor, bei denen die Datenschutzgarantie möglicherweise versagt. Durch die Kombination beider Komponenten ermöglicht DP-Auditorium (1) das automatisierte Testen verschiedener Mechanismen und Datenschutzdefinitionen und (2) die Erkennung von Fehlern in Mechanismen zum Schutz der Privatsphäre. Wir implementieren verschiedene personal und nicht personal Mechanismen, einschließlich einfacher Mechanismen, die den Mittelwert von Datensätzen berechnen, und komplexerer Mechanismen, wie z. B. verschiedene SVT- und Gradientenabstieg Mechanismusvarianten.
Immobilientester feststellen, ob Beweise vorliegen, die die Hypothese widerlegen, dass eine gegebene Divergenz zwischen zwei Wahrscheinlichkeitsverteilungen vorliegt, P Und Qist durch ein vorgegebenes Finances begrenzt, das durch die zu prüfende DP-Garantie bestimmt wird. Sie berechnen eine Untergrenze aus Stichproben von P Und Q, Zurückweisen der Eigenschaft, wenn der untere Grenzwert die erwartete Divergenz überschreitet. Es werden keine Garantien gegeben, wenn das Ergebnis tatsächlich begrenzt ist. Um eine Reihe von Datenschutzgarantien zu testen, stellt DP-Auditorium drei neuartige Tester vor: (1) HockeyStickPropertyTester, (2) RényiPropertyTester und (3) MMDPropertyTester. Im Gegensatz zu anderen Ansätzen sind diese Tester nicht auf explizite Histogrammnäherungen der getesteten Verteilungen angewiesen. Sie stützen sich auf Variationsdarstellungen der Hockeyschläger-Divergenz, der Rényi-Divergenz und maximale mittlere Abweichung (MMD), die die Schätzung von Divergenzen durch Optimierung über Funktionsräume ermöglichen. Als Foundation setzen wir um HistogramPropertyTester, ein häufig verwendeter ungefährer DP-Tester. Während unsere drei Tester einen ähnlichen Ansatz verfolgen, konzentrieren wir uns der Kürze halber in diesem Beitrag auf den HockeyStickPropertyTester.
Gegeben zwei benachbarte Datensätze, D Und D‘der HockeyStickPropertyTester findet eine Untergrenze,^δ für die Hockeyschläger-Divergenz zwischen M(D) Und M(D‘), das mit hoher Wahrscheinlichkeit gilt. Die Hockeyschläger-Divergenz erzwingt die beiden Verteilungen M(D) Und M(D‘) unterliegen einer ungefähren DP-Garantie. Wenn additionally eine Datenschutzgarantie behauptet, dass die Hockeyschläger-Divergenz höchstens besteht δUnd^δ > δdann ist die Divergenz mit hoher Wahrscheinlichkeit höher als versprochen D Und D‘ und der Mechanismus kann die gegebene ungefähre DP-Garantie nicht erfüllen. Die Untergrenze^δ wird als empirisches und handhabbares Gegenstück zu einer Variationsformulierung der Hockeyschläger-Divergenz berechnet (siehe das Papier für mehr Particulars). Die Genauigkeit von^δ steigt mit der Anzahl der aus dem Mechanismus entnommenen Proben, nimmt jedoch ab, wenn die Variationsformulierung vereinfacht wird. Um dies sicherzustellen, gleichen wir diese Faktoren aus^δ ist sowohl genau als auch einfach zu berechnen.
Datensatzfinder verwenden Black-Field-Optimierung Datensätze zu finden D Und D‘ die maximieren^δeine Untergrenze für den Divergenzwert δ. Beachten Sie, dass Black-Field-Optimierungstechniken speziell für Situationen konzipiert sind, in denen die Ableitung von Gradienten für eine Zielfunktion unpraktisch oder sogar unmöglich sein kann. Diese Optimierungstechniken schwanken zwischen Explorations- und Ausbeutungsphasen, um die Type der Zielfunktion abzuschätzen und Bereiche vorherzusagen, in denen das Ziel optimale Werte haben kann. Im Gegensatz dazu ist ein vollständiger Explorationsalgorithmus wie der Rastersuchmethodedurchsucht den gesamten Raum benachbarter Datensätze D Und D‘. DP-Auditorium implementiert verschiedene Datensatz-Finder über die Open-Supply-Black-Field-Optimierungsbibliothek Wesir.
Um vorhandene Komponenten auf einem neuen Mechanismus auszuführen, muss der Mechanismus lediglich als Python-Funktion definiert werden, die ein Datenarray entgegennimmt D und eine gewünschte Anzahl von Proben N vom berechneten Mechanismus ausgegeben werden soll D. Darüber hinaus bieten wir versatile Wrapper für Tester und Datensatzsucher, die es Praktikern ermöglichen, ihre eigenen Take a look at- und Datensatzsuchalgorithmen zu implementieren.
Wichtigste Ergebnisse
Wir bewerten die Wirksamkeit des DP-Auditoriums anhand von fünf privaten und neun nichtprivaten Mechanismen mit unterschiedlichen Ausgaberäumen. Für jeden Eigenschaftstester wiederholen wir den Take a look at zehnmal an festen Datensätzen mit unterschiedlichen Werten von ε, und geben Sie an, wie oft jeder Tester Datenschutzfehler identifiziert. Obwohl kein Tester die anderen durchweg übertrifft, identifizieren wir Fehler, die bei früheren Techniken (HistogramPropertyTester) übersehen würden. Beachten Sie, dass der HistogramPropertyTester nicht auf SVT-Mechanismen anwendbar ist.
 |
| Häufigkeit, mit der jeder Eigenschaftstester die Datenschutzverletzung für die getesteten nichtprivaten Mechanismen findet. Die Mechanismen NonDPLaplaceMean und NonDPGaussianMean sind fehlerhafte Implementierungen von Laplace Und Gauß Mechanismen zur Berechnung des Mittelwerts. |
Wir analysieren auch die Implementierung von a DP-Gradientenabstiegsalgorithmus (DP-GD) in TensorFlow, das Gradienten der Verlustfunktion für personal Daten berechnet. Um die Privatsphäre zu wahren, verwendet DP-GD einen Clipping-Mechanismus, um die Daten einzuschränken l2-Norm der Steigungen um einen Wert G, gefolgt von der Hinzufügung von Gauß-Rauschen. Diese Implementierung geht fälschlicherweise davon aus, dass das hinzugefügte Rauschen eine Größenordnung von hat Gwährend in Wirklichkeit die Skala ist sGWo S ist ein positiver Skalar. Diese Diskrepanz führt zu einer ungefähren DP-Garantie, die nur für Werte von gilt S größer oder gleich 1.
Wir bewerten die Wirksamkeit von Eigenschaftstestern bei der Erkennung dieses Fehlers und zeigen, dass HockeyStickPropertyTester und RényiPropertyTester eine überlegene Leistung bei der Identifizierung von Datenschutzverletzungen aufweisen und MMDPropertyTester und HistogramPropertyTester übertreffen. Bemerkenswert ist, dass diese Tester den Fehler auch bei Werten von erkennen S bis zu 0,6. Es lohnt sich, das hervorzuheben S = 0,5 entspricht a häufiger Fehler In der Literatur geht es darum, dass bei der Berücksichtigung des Datenschutzbudgets ein Faktor zwei fehlt ε. DP-Auditorium behebt diesen Fehler erfolgreich, wie unten gezeigt. Weitere Einzelheiten finden Sie in Abschnitt 5.6 Hier.
 |
| Geschätzte Abweichungen und Testschwellenwerte für verschiedene Werte von S beim Testen von DP-GD mit dem HistogramPropertyTester (hyperlinks) und der HockeyStickPropertyTester (Rechts). |
 |
| Geschätzte Abweichungen und Testschwellenwerte für verschiedene Werte von S beim Testen von DP-GD mit dem RényiPropertyTester (hyperlinks) und der MMDPropertyTester (Rechts) |
Um Dataset-Finder zu testen, berechnen wir die Anzahl der untersuchten Datensätze, bevor wir eine Datenschutzverletzung feststellen. Im Durchschnitt werden die meisten Fehler in weniger als 10 Aufrufen von Dataset-Findern entdeckt. Randomisierte Methoden und Explorations-/Ausbeutungsmethoden sind beim Auffinden von Datensätzen effizienter als die Rastersuche. Weitere Einzelheiten finden Sie im Papier.
Abschluss
DP ist eines der leistungsstärksten Frameworks für den Datenschutz. Die ordnungsgemäße Implementierung von DP-Mechanismen kann jedoch eine Herausforderung darstellen und anfällig für Fehler sein, die mit herkömmlichen Unit-Take a look at-Methoden nicht einfach erkannt werden können. Ein einheitlicher Testrahmen kann Prüfern, Regulierungsbehörden und Wissenschaftlern dabei helfen, sicherzustellen, dass personal Mechanismen tatsächlich privat sind.
DP-Auditorium ist ein neuer Ansatz zum Testen von DP durch Divergenzoptimierung über Funktionsräume. Unsere Ergebnisse zeigen, dass diese Artwork der funktionsbasierten Schätzung bisherige Black-Field-Zugriffstester durchweg übertrifft. Abschließend zeigen wir, dass diese funktionsbasierten Schätzer im Vergleich zur Histogrammschätzung eine bessere Entdeckungsrate von Datenschutzfehlern ermöglichen. Von Open Sourcing Im DP-Auditorium wollen wir einen Commonplace für Finish-to-Finish-Exams neuer differenziell privater Algorithmen etablieren.
Danksagungen
Die hier beschriebene Arbeit wurde gemeinsam mit Andrés Muñoz Medina, William Kong und Umar Syed durchgeführt. Wir danken Chris Dibak und Vadym Doroshenko für die hilfreiche technische Unterstützung und Schnittstellenvorschläge für unsere Bibliothek.