Riepilogo Tecnico: DP4SQL - SQL con Privacy Differenziale e Politiche di Privacy Flessibili

Definizione del Problema

La privacy differenziale (DP) è ben consolidata per dataset a tabella singola, ma la sua applicazione a database relazionali rimane problematica a causa della complessità nel definire la "negabilità plausibile" attraverso più relazioni. I sistemi SQL esistenti con privacy differenziale soffrono di modelli di privacy rigidi e predefiniti che non possono adattarsi ai requisiti sfumati delle applicazioni del mondo reale.

Le principali limitazioni dei sistemi attuali includono:

1. Politiche Inflessibili: Non possono gestire scenari in cui tabelle diverse o persino colonne diverse all'interno della stessa tabella richiedono diversi livelli di protezione (ad esempio, proteggere l'esistenza di un record in una tabella mentre si proteggono solo i valori degli attributi in un'altra).
2. Integrazione della Conoscenza Pubblica: Faticano a incorporare le informazioni pubbliche (ad esempio, dimensioni delle tabelle note, valori di colonne pubbliche come i nomi dei docenti) nel calcolo della privacy. Ignorare la conoscenza pubblica porta spesso a una protezione eccessiva (iniezione di rumore eccessivo) o a una protezione insufficiente (mancata occultazione dell'esistenza di record quando la dimensione della tabella è nota).
3. Interazioni Complesse tra Entità: I modelli esistenti spesso non riescono a gestire correttamente le chiavi esterne e la proprietà transitiva, in particolare quando le entità interagiscono (ad esempio, un docente che assegna voti a uno studente). Ciò porta a calcoli errati della sensibilità, con il rischio di una sensibilità insufficiente (violazioni della privacy) o di una sensibilità eccessiva (perdita di utilità).

Metodologia

Il documento propone DP4SQL, un sistema che scinde la specifica della politica di privacy di alto livello dal ragionamento automatizzato di basso livello. La metodologia consiste in tre componenti principali:

1. Framework di Etichettatura della Privacy di Alto Livello

Gli amministratori dei dati specificano le politiche utilizzando un semplice sistema di etichettatura di alto livello per ogni relazione nello schema. Per una relazione di entità distinta $R^\star$ (ad esempio, Studenti o Docenti), a ogni relazione $R_i$ viene assegnata una delle tre etichette:

• DEL (Delete/Elimina): L'esistenza dei record è privata. I mondi controfattuali sono creati eliminando i record. Questo corrisponde a vicini illimitati (unbounded).
• REPA (Replace/Sostituisci): L'esistenza dei record è pubblica, ma attributi specifici $A$ sono privati. I mondi controfattuali sono creati sostituendo i valori in $A$. Questo corrisponde a vicini limitati (bounded).
• PUB (Public/Pubblico): L'intera relazione è pubblica.

Questo framework consente politiche miste, come proteggere l'esistenza degli studenti (DEL) mantenendo i nomi dei docenti pubblici (PUB) ma gli stipendi dei docenti privati (REPA).

2. Azioni di Negabilità Plausibile di Basso Livello

Per automatizzare il ragionamento, il sistema traduce le etichette di alto livello in un insieme di azioni di negabilità plausibile che descrivono la massima variazione che il risultato di una query può subire tra database vicini. Le azioni sono:

• Add$_a$ / Del$_d$: Aggiungere o eliminare $a$ o $d$ righe.
• Rep$^A_k$: Sostituire i valori degli attributi $A$ in $k$ righe.

Il sistema impiega un sistema di inferenza con regole di produzione per derivare queste azioni per query SQL complesse che coinvolgono:

• Relazioni di Base: Le regole mappano le etichette di privacy in azioni iniziali, considerando la massima proprietà ($\hat{\otimes}$) derivata dai vincoli di chiave esterna.
• Trasformazioni Unarie: Le regole per Selezione ($\sigma$), Proiezione ($\pi$) e Raggruppamento ($\gamma$) propagano le azioni in base al fatto che i predicati o le chiavi di raggruppamento intersechino gli attributi protetti.
• Join: Il sistema distingue tra Key Joins (su coppie chiave primaria-chiave esterna) e General Joins (Join Generali). I Key Join sfruttano i vincoli di integrità per derivare limiti più stretti sulle variazioni dei record, evitando la sovra-approssimazione comune nelle regole dei join generali.

3. Calcolo della Sensibilità e Iniezione del Rumore

Le azioni inferite vengono mappate a un limite superiore sulla sensibilità globale ($\hat{\Delta}$). Questo limite determina la scala del rumore aggiunto tramite il meccanismo di Laplace. Il sistema calcola la sensibilità per le funzioni di aggregazione (COUNT, SUM) analizzando come le azioni inferite (aggiunte, eliminazioni, sostituzioni) influenzano il vettore di output.

Contributi Chiave

1. Specifica di Politiche Flessibili: Un framework di etichettatura delle colonne di alto livello che supporta requisiti di privacy misti (dimensioni delle tabelle pubbliche, colonne pubbliche, attributi privati) attraverso schemi relazionali con chiavi esterne.
2. Motore di Ragionamento Automatizzato: Un sistema di inferenza formale che traduce le etichette di alto livello in azioni di negabilità plausibile di basso livello, ragionando in modo solido sulla stabilità delle query di algebra relazionale (join, aggregazioni, subquery).
3. Limiti di Sensibilità più Stretti: Esplicitamente modellando la conoscenza pubblica (ad esempio, dimensioni delle tabelle note) e utilizzando regole specifiche per i Key Join, DP4SQL deriva limiti di sensibilità più stretti rispetto ai sistemi esistenti, che spesso assumono scenari peggiori per tutti gli attributi.
4. Implementazione e Validazione: Il sistema è implementato come middleware per database (DP4SQL) che intercetta le query SQL, calcola il rumore richiesto e restituisce risposte con privacy differenziale.

Risultati

Il documento valuta DP4SQL utilizzando un caso di studio su uno schema universitario e il benchmark TPC-H, confrontandolo con le policy di base (vicini puramente illimitati e puramente limitati) e il sistema Tumult Analytics (basato su PrivateSQL).

• Correttezza della Privacy (Sotto-protezione): In scenari in cui le dimensioni delle tabelle sono pubbliche (ad esempio, il numero di ordini in TPC-H), i modelli a vicini illimitati (come Tumult) assumono erroneamente che l'esistenza dei record sia privata. Ciò porta a una sotto-protezione (rumore insufficiente) perché non tengono conto del fatto che sostituire un record (invece di eliminarlo) è il controfattuale valido quando la dimensione è nota. DP4SQL identifica correttamente questi casi e applica il rumore appropriato.
• Miglioramento dell'Utilità (Sovra-protezione): I modelli di base spesso trattano tutti gli attributi come privati, portando a una sovra-protezione (rumore eccessivo). Ad esempio, nelle query sui punteggi delle recensioni pubbliche o sui nomi dei docenti nel caso di studio universitario, DP4SQL ha prodotto una sensibilità pari a zero, mentre i modelli di base iniettavano un rumore significativo. In TPC-H, DP4SQL ha ottenuto una sensibilità zero per le query che restituiscono informazioni pubbliche (ad esempio, conteggi dei fornitori), mentre i modelli di base hanno aggiunto rumore che rendeva i risultati inutilizzabili (errore relativo > 100%).
• Accuratezza: Nei casi in cui i modelli di base hanno sovra-protetto, DP4SQL ha dimostrato un errore relativo significativamente inferiore (ad esempio, 19,6% rispetto agli errori molto più elevati dei modelli di base per specifiche query TPC-H).

Significato e Rivendicazioni

Il documento afferma che DP4SQL affronta il limite del "modello unico per tutti" dei sistemi SQL con DP attuali. Consentendo ai curatori dei dati di personalizzare i requisiti di negabilità plausibile, il sistema evita il compromesso tra violazioni della privacy (dovute alla sotto-protezione) e perdita di utilità dei dati (dovuta alla sovra-protezione).

Gli autori sottolineano che il loro approccio è solido: forniscono prove formali che il sistema di inferenza deriva correttamente un limite superiore sulla sensibilità globale, garantendo che il meccanismo risultante soddisfi la $(PS, R^\star, \epsilon)$-differential privacy. Il lavoro evidenzia che una corretta modellazione della privacy — specificamente la capacità di ragionare sulle dimensioni pubbliche delle tabelle, sulle colonne pubbliche e sulla protezione granulare degli attributi — è essenziale per l'implementazione della privacy differenziale in ambienti relazionali multi-tabella complessi.