Une bibliothèque flexible pour auditer la confidentialité différentielle

Confidentialité différentielle (DP) est une propriété de mécanismes randomisés qui limitent l’influence des informations de tout utilisateur individuel lors du traitement et de l’analyse des données. DP propose une solution robuste pour répondre aux préoccupations croissantes concernant la protection des données, permettant des technologies à travers industries et les applications gouvernementales (par exemple, Le recensement américain) sans compromettre les identités des utilisateurs individuels. À mesure que son adoption augmente, il est important d’identifier les risques potentiels de développer des mécanismes avec des implémentations défectueuses. Les chercheurs ont récemment trouvé des erreurs dans les preuves mathématiques des mécanismes privés et de leurs implémentations. Par exemple, Les chercheurs ont comparé Six variations techniques vectorielles (SVT) et ont constaté que seuls deux des six répondaient en fait à la garantie de confidentialité affirmée. Même lorsque les preuves mathématiques sont correctes, le code implémentant le mécanisme est vulnérable à l’erreur humaine.

Cependant, l’audit DP pratique et efficace est difficile principalement en raison de l’aléatoire inhérent des mécanismes et de la nature probabiliste des garanties testées. De plus, il existe une gamme de types de garantie (par exemple, DP pur, DP approximatif, Rényi DPet DP concentré), et cette diversité contribue à la complexité de la formulation du problème d’audit. De plus, le débogage des preuves mathématiques et des bases de code est une tâche intraitable compte tenu du volume de mécanismes proposés. Alors que ad hoc Les techniques de test existent sous des hypothèses spécifiques de mécanismes, peu d’efforts ont été faits pour développer un outil extensible pour tester les mécanismes DP.

À cette fin, dans «DP-Auditorium: une bibliothèque à grande échelle pour auditer la confidentialité différentielle», Nous introduisons un bibliothèque open source Pour auditer les garanties DP avec uniquement l’accès à la boîte noire à un mécanisme (c’est-à-dire sans aucune connaissance des propriétés internes du mécanisme). DP-Auditorium est implémenté dans Python et fournit une interface flexible qui permet aux contributions d’améliorer en continu ses capacités de test. Nous introduisons également de nouveaux algorithmes de test qui effectuent une optimisation de divergence sur les espaces de fonction pour Rényi DP, Pure DP et DP approximatif. Nous démontrons que le DP-Auditorium peut identifier efficacement les violations de la garantie DP et suggérer quels tests conviennent le plus pour détecter des bogues particuliers sous diverses garanties de confidentialité.

Garanties DP

La sortie d’un mécanisme DP est un échantillon tiré d’une distribution de probabilité (M (D)) qui satisfait une propriété mathématique assurant la confidentialité des données utilisateur. Une garantie DP est donc étroitement liée aux propriétés entre des paires de distributions de probabilité. Un mécanisme est différentiellement privé si les distributions de probabilité déterminées par M sur l’ensemble de données D et un ensemble de données voisin D’qui diffèrent d’un seul enregistrement, sont indiscernable sous une métrique de divergence donnée.

Par exemple, le classique DP approximatif La définition indique qu’un mécanisme est approximativement DP avec des paramètres (ε, δ) Si le divergence de hockey d’ordre e^εentre M(D) et M(D’), est au plus δ. Le DP pur est une instance spéciale de DP approximatif où δ = 0. Enfin, un mécanisme est considéré Rényi DP avec des paramètres (𝛼, ε) Si le Divergence de rényi d’ordre 𝛼est au plus ε (où ε est une petite valeur positive). Dans ces trois définitions, ε n’est pas interchangeable mais transmet intuitivement le même concept; des valeurs plus importantes de ε Impliquez des divergences plus importantes entre les deux distributions ou moins d’intimité, car les deux distributions sont plus faciles à distinguer.

Dp-auditorium

DP-Auditorium comprend deux composants principaux: les testeurs de propriété et les chercheurs de données. Les testeurs de propriété prélèvent des échantillons d’un mécanisme évalué sur des ensembles de données spécifiques en entrée et visent à identifier les violations de la garantie de confidentialité dans les ensembles de données fournis. Les chercheurs de données suggèrent des ensembles de données où la garantie de confidentialité peut échouer. En combinant les deux composants, DP-Auditorium permet (1) les tests automatisés de divers mécanismes et définitions de confidentialité et, (2) la détection des bogues dans les mécanismes de préservation de la confidentialité. Nous mettons en œuvre divers mécanismes privés et non privés, y compris des mécanismes simples qui calculent la moyenne des enregistrements et des mécanismes plus complexes, tels que différents SVT et descente de dégradé Variantes du mécanisme.

Testeurs de propriétés déterminer si des preuves existent pour rejeter l’hypothèse selon laquelle une divergence donnée entre deux distributions de probabilité, P et Qest délimité par un budget prédéfini déterminé par la garantie DP testée. Ils calculent une limite inférieure à partir d’échantillons de P et Q, Rejeter la propriété si la valeur liée inférieure dépasse la divergence attendue. Aucune garantie n’est fournie si le résultat est effectivement limité. Pour tester une gamme de garanties de confidentialité, DP-Auditorium présente trois nouveaux testeurs: (1) HockeyStickPropertyTester, (2) RényipropertyTester et (3) MMDPropertyTester. Contrairement à d’autres approches, ces testeurs ne dépendent pas des approximations d’histogramme explicites des distributions testées. Ils s’appuient sur des représentations variationnelles de la divergence du bâton de hockey, de la divergence de la rényi, et Dicontenance moyenne maximale (MMD) qui permettent l’estimation des divergences par l’optimisation sur les espaces de fonction. En guise de référence, nous mettons en œuvre HistogrampropertyTesterun testeur DP approximatif couramment utilisé. Alors que nos trois testeurs suivent une approche similaire, pour Brevity, nous nous concentrons sur le hockeystickPropertyTester dans ce post.

Compte tenu de deux ensembles de données voisins, D et D’le hockeystickpropertytester trouve une limite inférieure,^δ pour la divergence du bâton de hockey entre M(D) et M(D’) qui tient avec une forte probabilité. La divergence de hockey-stick impose que les deux distributions M(D) et M(D’) sont proches sous une garantie DP approximative. Par conséquent, si une garantie de confidentialité prétend que la divergence du bâton de hockey est tout au plus δet^δ > δpuis avec une forte probabilité, la divergence est plus élevée que ce qui a été promis sur D et D’ et le mécanisme ne peut satisfaire à la garantie DP approximative donnée. La limite inférieure^δ est calculé comme un homologue empirique et tractable d’une formulation variationnelle de la divergence du bâton de hockey (voir le papier pour plus de détails). La précision de^δ augmente avec le nombre d’échantillons tirés du mécanisme, mais diminue à mesure que la formulation variationnelle est simplifiée. Nous équilibrons ces facteurs afin de garantir que^δ est à la fois précis et facile à calculer.

Finders de l’ensemble de données utiliser Optimisation de la boîte noire Pour trouver des ensembles de données D et D’ qui maximisent^δune limite inférieure sur la valeur de divergence δ. Notez que les techniques d’optimisation de la boîte noire sont spécialement conçues pour les paramètres où la dérivation des gradients pour une fonction objective peut être peu pratique ou même impossible. Ces techniques d’optimisation oscillent entre les phases d’exploration et d’exploitation pour estimer la forme de la fonction objectif et prédire les domaines où l’objectif peut avoir des valeurs optimales. En revanche, un algorithme d’exploration complet, comme le Méthode de recherche de grillerecherche sur tout l’espace des ensembles de données voisins D et D’. DP-Auditorium implémente différents chercheurs de données via la bibliothèque d’optimisation de la boîte noire ouverte Vizir.

L’exécution des composants existants sur un nouveau mécanisme nécessite uniquement de définir le mécanisme comme une fonction Python qui prend un tableau de données D et un nombre souhaité d’échantillons n être sorti par le mécanisme calculé sur D. De plus, nous fournissons des emballages flexibles pour les testeurs et les chercheurs de données qui permettent aux praticiens d’implémenter leurs propres algorithmes de test et de recherche de données.

Résultats clés

Nous évaluons l’efficacité du DP-Auditorium sur cinq mécanismes privés et neuf non privés avec divers espaces de sortie. Pour chaque testeur de propriété, nous répétons le test dix fois sur des ensembles de données fixes en utilisant différentes valeurs de εet signaler le nombre de fois que chaque testeur identifie les bogues de confidentialité. Bien qu’aucun testeur ne surpasse régulièrement les autres, nous identifions les bogues qui seraient manqués par les techniques précédentes (HistogrampropertyTester). Notez que l’histogrampropertyTester n’est pas applicable aux mécanismes SVT.

Nombre de fois que chaque testeur de propriété trouve la violation de la confidentialité pour les mécanismes non privés testés. Les mécanismes non-plaplacemans et nonpgaussiennes sont des implémentations défectueuses de la Laplace et Gaussien Mécanismes pour calculer la moyenne.

Nous analysons également la mise en œuvre d’un Algorithme de descente de gradient DP (DP-GD) dans TensorFlow qui calcule les gradients de la fonction de perte sur les données privées. Pour préserver la vie privée, DP-GD utilise un mécanisme d’écrêtage pour lier le l2 norme des gradients par une valeur Gsuivi de l’ajout de bruit gaussien. Cette implémentation suppose à tort que le bruit ajouté a une échelle de Galors qu’en réalité, l’échelle est SGoù s est un scalaire positif. Cet écart conduit à une garantie DP approximative qui ne vaut que pour les valeurs de s supérieur ou égal à 1.

Nous évaluons l’efficacité des testeurs de propriétés dans la détection de ce bogue et montrons que le hockeystickpropertytester et la rényipropertyteter présentent des performances supérieures à l’identification des violations de la confidentialité, sur la surperformance MMDPropertyTester et HistogrampropertyTester. Notamment, ces testeurs détectent le bogue même pour les valeurs de s aussi élevé que 0,6. Il vaut la peine de souligner que s = 0,5 correspond à un erreur commune dans la littérature qui implique de manquer un facteur de deux lorsqu’il tient compte du budget de la vie privée ε. DP-Auditorium capture avec succès ce bug comme indiqué ci-dessous. Pour plus de détails, voir la section 5.6 ici.

Divergences estimées et seuils de test pour différentes valeurs de s Lors du test de DP-GD avec l’histogrampropertytester (gauche) et le hockeystickPropertyTester (droite).

Divergences estimées et seuils de test pour différentes valeurs de s Lorsque vous testez DP-GD avec le RényipropertyTester (gauche) et le MMDPropertyTester (droite)

Pour tester les chercheurs de données, nous calculons le nombre d’ensembles de données explorés avant de trouver une violation de la confidentialité. En moyenne, la majorité des bogues sont découverts dans moins de 10 appels à des chercheurs de données. Les méthodes randomisées et d’exploration / exploitation sont plus efficaces pour trouver des ensembles de données que la recherche de grille. Pour plus de détails, voir le papier.

Conclusion

DP est l’un des cadres les plus puissants pour la protection des données. Cependant, une mise en œuvre appropriée des mécanismes DP peut être difficile et sujette à des erreurs qui ne peuvent pas être facilement détectées à l’aide de méthodes de test unitaires traditionnelles. Un cadre de test unifié peut aider les auditeurs, les régulateurs et les universitaires à s’assurer que les mécanismes privés sont en effet privés.

DP-Auditorium est une nouvelle approche pour tester DP via l’optimisation de la divergence sur les espaces de fonction. Nos résultats montrent que ce type d’estimation basé sur la fonction surpasse constamment les testeurs d’accès aux boîtes noires précédentes. Enfin, nous démontrons que ces estimateurs basés sur la fonction permettent un meilleur taux de découverte des bogues de confidentialité par rapport à l’estimation de l’histogramme. Par Sourcing ouvert DP-Auditorium, nous visons à établir une norme pour les tests de bout en bout de nouveaux algorithmes différentiellement privés.

Remerciements

Les travaux décrits ici ont été effectués conjointement avec Andrés Muñoz Medina, William Kong et Umar Syed. Nous remercions Chris Dibak et Vadym Doroshenko pour les suggestions utiles d’ingénierie et d’interface pour notre bibliothèque.