Résumé Technique : DP4SQL - SQL avec Confidentialité Différentielle et Politiques de Confidentialité Flexibles

Énoncé du Problème

La confidentialité différentielle (DP) est bien établie pour les ensembles de données à table unique, mais son application aux bases de données relationnelles reste complexe en raison de la difficulté de définir un « déni plausible » à travers plusieurs relations. Les systèmes SQL dotés de confidentialité différentielle existants souffrent de modèles de confidentialité rigides et codés en dur qui ne peuvent pas s'adapter aux exigences nuancées des applications du monde réel.

Les principales limitations des systèmes actuels incluent :

1. Politiques Inflexibles : Ils ne peuvent pas gérer les scénarios où différentes tables, ou même différents colonnes au sein d'une même table, nécessitent des niveaux de protection variés (par exemple, protéger l'existence d'un enregistrement dans une table tout en ne protégeant que les valeurs d'attributs dans une autre).
2. Intégration des Connaissances Publiques : Ils peinent à intégrer les informations publiques (par exemple, les tailles de tables connues, les valeurs de colonnes publiques comme les noms de professeurs) dans le calcul de la confidentialité. Ignorer les connaissances publiques conduit souvent à une surprotection (injection de bruit excessif) ou à une sous-protection (échec de la dissimulation de l'existence d'enregistrements lorsque la taille de la table est connue).
3. Interactions Complexes d'Entités : Les modèles existants échouent souvent à traiter correctement les clés étrangères et la propriété transitive, en particulier lorsque les entités interagissent (par exemple, un membre du corps professoral attribuant des notes à un étudiant). Cela conduit à des calculs de sensibilité incorrects, entraînant soit une insuffisance de bruit (failles de confidentialité), soit un excès de bruit (perte d'utilité).

Méthodologie

Le document propose DP4SQL, un système qui découple la spécification de la politique de confidentialité de haut niveau du raisonnement automatisé de bas niveau. La méthodologie se compose de trois composantes principales :

1. Cadre de Labellisation de Haut Niveau

Les administrateurs de données spécifient les politiques à l'aide d'un système de labellisation simple de haut niveau pour chaque relation du schéma. Pour une relation d'entité distinguée $R^\star$ (par exemple, Étudiants ou Professeurs), chaque relation $R_i$ se voit assigner l'un des trois labels suivants :

• DEL (Delete/Supprimer) : L'existence des enregistrements est privée. Les mondes contrefactuels sont créés par la suppression d'enregistrements. Cela correspond à des voisins non bornés.
• REPA (Replace/Remplacer) : L'existence des enregistments est publique, mais les attributs spécifiques $A$ sont privés. Les mondes contrefactuels sont créés par le remplacement de valeurs dans $A$. Cela correspond à des voisins bornés.
• PUB (Public) : L'intégralité de la relation est publique.

Ce cadre permet des politiques mixtes, comme la protection de l'existence des étudiants (DEL) tout en gardant les noms des professeurs publics (PUB) mais les salaires des professeurs privés (REPA).

2. Actions de Déni Plausible de Bas Niveau

Pour automatiser le raisonnement, le système traduit les labels de haut niveau en un ensemble d'actions de déni plausible qui décrivent le changement maximal qu'un résultat de requête peut subir entre des bases de données voisines. Les actions sont :

• Add$_a$ / Del$_d$ : Ajouter ou supprimer $a$ ou $d$ lignes.
• Rep$^A_k$ : Remplacer les valeurs des attributs $A$ dans $k$ lignes.

Le système utilise un système d'inférence avec des règles de production pour dériver ces actions pour des requêtes SQL complexes impliquant :

• Relations de Base : Des règles associent les labels de confidentialité aux actions initiales, en considérant la propriété maximale ($\hat{\otimes}$) dérivée des contraintes de clé étrangère.
• Transformations Unaires : Les règles pour la Sélection ($\sigma$), la Projection ($\pi$) et le Groupement ($\gamma$) propagent les actions en fonction de l'intersection des prédicats ou des clés de groupement avec les attributs protégés.
• Jointures : Le système distingue les Jointures de Clés (sur des paires clé primaire-clé étrangère) des Jointures Générales. Les jointures de clés exploitent les contraintes d'intégrité pour dériver des limites plus serrées sur les changements d'enregistrements, évitant ainsi la sur-approximation commune aux règles de jointure générale.

3. Calcul de Sensibilité et Injection de Bruit

Les actions déduites sont mappées vers une borne supérieure de la sensibilité globale ($\hat{\Delta}$). Cette borne détermine l'échelle du bruit ajouté via le mécanisme de Laplace. Le système calcule la sensibilité pour les fonctions d'agrégation (COUNT, SUM) en analysant comment les actions déduites (ajouts, suppressions, remplacements) affectent le vecteur de sortie.

Contributions Clés

1. Spécification de Politique Flexible : Un cadre de labellisation de colonnes de haut niveau qui prend en charge des exigences de confidentialité mixtes (tailles de tables publiques, colonnes publiques, attributs privés) à travers des schémas relationnels avec clés étrangères.
2. Moteur de Raisonnement Automatisé : Un système d'inférence formel qui traduit les labels de haut niveau en actions de déni plausible de bas niveau, raisonnant de manière saine sur la stabilité des requêtes d'algèbre relationnelle (jointures, agrégations, sous-requêtes).
3. Bornes de Sensibilité plus Serrées : En modélisant explicitement les connaissances publiques (par exemple, les tailles de tables connues) et en utilisant des règles spécifiques aux jointures de clés, DP4SQL dérive des bornes de sensibilité plus serrées que les systèmes existants, qui supposent souvent des scénarios de pire cas pour tous les attributs.
4. Implémentation et Validation : Le système est implémenté comme un middleware de base de données (DP4SQL) qui intercepte les requêtes SQL, calcule le bruit requis et renvoie des réponses avec confidentialité différentielle.

Résultats

Le papier évalue DP4SQL en utilisant une étude de cas de schéma universitaire et le benchmark TPC-H, en comparant les résultats avec des politiques de référence (modèles de voisins purement non bornés et purement bornés) et le système Tumult Analytics (basé sur PrivateSQL).

• Correctitude de la Confidentialité (Sous-protection) : Dans les scénarios où les tailles de tables sont publiques (par exemple, le nombre de commandes dans TPC-H), les modèles non bornés de référence (comme Tumult) supposent incorrectement que l'existence des enregistrements est privée. Cela conduit à une sous-protection (insuffisance de bruit) car ils ne tiennent pas compte du fait que remplacer un enregistrement (plutôt que de le supprimer) est le contrefactuel valide lorsque la taille est connue. DP4SQL identifie correctement ces cas et applique le bruit approprié.
• Amélioration de l'Utilité (Surprotection) : Les modèles de référence traitent souvent tous les attributs comme privés, ce qui conduit à une surprotection (bruit excessif). Par exemple, dans l'étude de cas universitaire, les requêtes sur les scores d'évaluation publics ou les noms de professeurs ont résulté en une sensibilité nulle sous DP4SQL, alors que les modèles de référence injectaient un bruit significatif. Dans TPC-H, DP4SQL a atteint une sensibilité nulle pour les requêtes retournant des informations publiques (ex: comptes de fournisseurs), tandis que les modèles de référence ajoutaient un bruit rendant les résultats inutilisables (erreur relative > 100 %).
• Précision : Dans les cas où les modèles de référence surprotégeaient, DP4SQL a démontré une erreur relative nettement plus faible (par exemple, 19,6 % contre des erreurs bien plus élevées dans les modèles de référence pour des requêtes spécifiques de TPC-H).

Signification et Revendications

Le papier affirme que DP4SQL répond à la limitation du « taille unique » des systèmes SQL de DP actuels. En permettant aux curateurs de données de personnaliser les exigences de déni plausible, le système évite le compromis entre les brèches de confidentialité (dues à la sous-protection) et la perte d'utilité des données (due à la surprotection).

Les auteurs soulignent que leur approche est robuste (sound) : ils fournissent des preuves formelles que le système d'inférence dérive correctement une borne supérieure de la sensibilité globale, garantissant que le mécanisme résultant satisfait la $(PS, R^\star, \epsilon)$-confidentialité différentielle. Ce travail met en évidence que la modélisation correcte de la confidentialité — spécifiquement la capacité à raisonner sur les tailles de tables publiques, les colonnes publiques et la protection fine des attributs — est essentielle pour déployer la confidentialité différentielle dans des environnements de bases de données relationnelles complexes.