- APPUNTI
- SCIENZE E TECNOLOGIE INFORMATICHE
- PRIVATEZZA E PROTEZIONE DEI DATI
Privatezza e Protezione dei Dati:
Appunti per il corso "privatezza e protezione dei dati", A.A 2018/2019, che analizza i problemi relativi alla protezione dati che nascono in scenari aperti e dinamici dove le informazioni sono spesso memorizzate, gestite ed elaborate da server esterni non completamente fidati.
Il corso si propone di illustrare alcuni approcci alla protezione dei dati in questi scenari.
Argomenti trattati:
• Privatezza nella pubblicazione e rilascio di dati
• Protezione di macrodati e microdati
• Introduzione ai problemi di sicurezza e privacy nel cloud
• Modelli e linguaggi per la specifica di preferenze di privacy degli utenti
• Protezione dei dati in outsourcing e cloud
• Confidenzialità degli accessi ed integrità delle query
• Condivisione controllata di dati in query distribuite
• Privacy in ambito WWW e social networks
• Approcci avanzati per il controllo dell'accesso
• Protezione dei dati di locazione
• Prerequisiti e modalità di esame
• Concetti di base di: sicurezza e privatezza; basi di dati
Dettagli appunto:
-
Autore:
Maurizio Fortunati
[Visita la sua tesi: "La Blockchain come strumento di marcatura temporale per grandi quantità di dati"]
[Visita la sua tesi: "Dynamic Access Control in una realtà consortile tramite XACML e smart contract"]
- Università: Università degli Studi di Milano
- Facoltà: Scienze e Tecnologie Informatiche
- Corso: Sicurezza Informatica
- Esame: Privatezza e Protezione dei Dati
- Docente: Samarati Pierangela
Questa è solo un’anteprima: 21 pagine mostrate su 106 totali. Registrati e scarica gratis il documento.
Privatezza e Protezione dei Dati Appunti di Maurizio Fortunati Università degli Studi di Milano Facoltà di Scienze e Tecnologie Corso di Laurea Magistrale in Sicurezza informatica (Classe LM-66) Esame di Privatezza e Protezione dei Dati Docente: Samarati Pierangela Anno accademico - 2018/2019Appunti di Privatezza e protezione dei dati Università degli Studi di Milano – Corso Magistrale in Sicurezza Informatica LM-66 Corso tenuto da Pierangela Samarati [mail] AA 2018/19 Sito Docente Link Ariel - Lucidi Link Ariel - Video lezioni V2.4 – Gennaio 2020 Sommario 1. Privacy and data protection in emerging scenarios ............................................................................................... 4 Privacy nella pubblicazione dati ..................................................................................................................................... 4 Rilascio di statistiche............................................................................................................................................. 4 Tipologie di disclosure – 12/142 ........................................................................................................................... 4 Restricted data and restricted access – 16/142 ................................................................................................... 5 The anonimity problem -20/142 .......................................................................................................................... 6 K-anonimity - 29/142 ...................................................................................................................................................... 6 K-anonimity .......................................................................................................................................................... 6 Generalized table with suppression – 32/142 ...................................................................................................... 8 k-minimal generalization with suppression – 39/142 .......................................................................................... 8 Computing a preferred generalization – 42/142 .................................................................................................. 9 Classificazione di tecniche di k-anonimity – 43/142 ............................................................................................. 9 Algorithms for computing a k-anonymous table – 49/142 ........................................................................................... 10 Intro .................................................................................................................................................................... 10 Algorithms for AG_TS e AG_ - AG– 50/142 ........................................................................................................ 10 Algorithms for _CS and CG_ - 62/142 ................................................................................................................. 11 Attribute disclosure – 70/142 ....................................................................................................................................... 12 intro .................................................................................................................................................................... 12 ℓ-diversity – 74/142 ............................................................................................................................................ 12 Skewness attack (attacco per asimmetria) – 76/142.......................................................................................... 13 Similarity attack - 77/142 ................................................................................................................................... 13 Group closeness (t-closeness) – 78/142 ............................................................................................................. 13 External knowledge – 79/142 ............................................................................................................................. 13 Multiple/longitudinal releases (rilasci multipli o longitudinali) – 86/142 .......................................................... 14 m-invariance - 89/142 ........................................................................................................................................ 14 Extended scenarios - 90/142 .............................................................................................................................. 14 Differential privacy - 112/142 ............................................................................................................................. 15 Sensitive value distributions – 119/142 ........................................................................................................................ 16 Sensitive value distributions ............................................................................................................................... 16 Privacy and genomic data - 125/142 .................................................................................................................. 16 2. Macrodata and Microdata Protection ................................................................................................................. 17 Microdata e Macrodata ................................................................................................................................................ 17 Statistical data dissemination ............................................................................................................................. 17 Macrodata Disclosure Protection Techniques – 3/66................................................................................................... 17 Intro .................................................................................................................................................................... 17 Protezione delle tabelle di conteggio e frequenza - 5/66 .................................................................................. 17 Protection of tables of magnitude data - 29/66 ................................................................................................. 19 Microdata Disclosure Protection Techniques – 43/66 ................................................................................................. 20 Intro .................................................................................................................................................................... 20 Microdata Disclosure Protection Techniques: - 51/66 ....................................................................................... 20 3. Privacy in data Outsourcing ................................................................................................................................ 22 Cloud computing ........................................................................................................................................................... 22 Intro .................................................................................................................................................................... 22 Characterization of Data Protection Challenges – 14/32 ............................................................................................. 22 Security properties ............................................................................................................................................. 22 Access requirements .......................................................................................................................................... 23 Architectures ...................................................................................................................................................... 23 4. Privacy of user ................................................................................................................................................... 24 Privacy of users’ identities ............................................................................................................................................ 24 Intro .................................................................................................................................................................... 24 User empowerment - 4/51 ................................................................................................................................. 24 Existing/emerging technologies supporting ABAC – 8/51 .................................................................................. 25 User privacy preferences – 9/51 ......................................................................................................................... 25 Some approaches – 12/51 ............................................................................................................................................ 26 Cost-Sensitive Trust Negotiation – 13/51 ........................................................................................................... 26 Point-based Trust Management Model – 17/51 ................................................................................................ 26 Logic-based Minimal Credential Disclosure – 23/51 .......................................................................................... 27 Privacy Preferences in Credential-based Interactions – 30/51........................................................................... 28 5. Privacy and integrity of cloud data storage ......................................................................................................... 32 Encryption ..................................................................................................................................................................... 32 Intro .................................................................................................................................................................... 32 Index – 7/270 ...................................................................................................................................................... 34 Searchable encryption – 32/270 ......................................................................................................................... 36 Inference exposure – 35/270 ............................................................................................................................. 37 Bloom Filter – 50/270 ......................................................................................................................................... 38 Data Integrity - 54/270 ....................................................................................................................................... 39 Controllo dell’accesso - 57/270 .......................................................................................................................... 39 Fragmentation – 126/270 ............................................................................................................................................. 49 Intro .................................................................................................................................................................... 49 Non-communicating pair of servers - 131/270 ................................................................................................... 50 Multiple non-linkable fragments – 140/270 ....................................................................................................... 53 Keep a few – 151/270 ......................................................................................................................................... 57 Publishing Obfuscated Associations 180/270 ............................................................................................................... 63 Intro .................................................................................................................................................................... 63 Anonymizing Bipartite Graph 182/270 ............................................................................................................... 64 Fragments and Loose Associations 189/270 ...................................................................................................... 66 6. Privacy delle query ............................................................................................................................................. 75 Confidenzialità delle query ........................................................................................................................................... 75 intro .................................................................................................................................................................... 75 Path ORAM ......................................................................................................................................................... 75 Shuffle index ....................................................................................................................................................... 77 7. Domande e risposte ........................................................................................................................................... 81 Capitolo 1 - Privacy and data protection in emerging scenarios .................................................................................. 81 Capitolo 2 - Macrodata and Microdata Protection ....................................................................................................... 81 Capitolo 3 - Privacy in data Outsourcing ....................................................................................................................... 81 Capitolo 4 - Privacy of user ........................................................................................................................................... 81 Cost-sensitive trust negotiation.......................................................................................................................... 81 Point Based trust management model ............................................................................................................... 82 Logic based minimal credential disclosure ......................................................................................................... 82 Privacy preferences in credential-based interactions ........................................................................................ 83 Capitolo 5 -Privacy and integrity of cloud data storag.................................................................................................. 85 Encryption ........................................................................................................................................................... 85 Inference expsoure ............................................................................................................................................. 87 Fragmentation .................................................................................................................................................... 87 Ottimizzazioni ..................................................................................................................................................... 90 Pubblicazione associazioni dei dati ..................................................................................................................... 91 Selective Encryption and Over-Encryption – Controllo dell’accesso .................................................................. 93 Capitolo 6 - Privacy delle query .................................................................................................................................... 95 Path Oram ........................................................................................................................................................... 95 Shuffle index ....................................................................................................................................................... 95 8. Indice delle figure .............................................................................................................................................. 97 1. Privacy and data protection in emerging scenarios Privacy nella pubblicazione dati Rilascio di statistiche Il rilascio di dati c’è sempre stato e sempre ci sarà, all’inizio avveniva in forma statistica. Per esempio un ospedale rilascia statistiche sui propri pazienti. Esistono due metodi per recuperare le informazioni: • DBMS statistico: Processo dinamico per cui io posso chiedere ciò che voglio purché non si riferisca a singoli individui ma ad aggregazioni di individui. Proteggere la privacy in questo caso è più semplice perché vengono trattate query aggregate. Non risponde se la quantità di dati è troppo piccola o troppo grande. Due problemi: 1. Non posso mostrare troppi dati a un utente in un arco temporale troppo piccolo perché accumula troppa conoscenza. Cosa considero come arco temporale? Due query consecutive possono essere significative ma una ieri e una oggi? 2. Cosa considero come soggetto accumulante conoscenza? Considero la singola login? Due utenti con due login differenti potrebbero parlarsi. • Statistical data: vengono rilasciati tutti i dati in maniera statistica. Nel passato i dati venivano rilasciati in macrodata (sostanzialmente dati aggregati). Oggi invece si spinge sempre di più verso i microdata (dati più mirati, più specifici). Nel caso dei microdata si è più esposti a rischi di privacy e in particolare ai linking attacks. Macrodata: dati in forma aggregata o statistiche, spesso senza gli identificativi dei singoli soggetti. Microdata: si parla di micro data quando i dati rilasciati non sono informazioni in forma aggregata (statistiche), ma sono dati veri e propri del mio database (dati grezzi). I Macrodata, si possono dividere in due gruppi: • Tabelle di conteggio/frequenza: dati aggregati computati, il contenuto della tabella è un conteggio (o percentuale) degli individui che soddisfano un certo requisito • Magnitude (importanza) data: Un’ aggregazione su un certo dato di interesse. Per esempio il valore medio dello stipendio. Tipologie di disclosure 1. Identity disclosure: è possibile identificare un individuo dai dati. Il fatto che l’individuo faccia parte di un certo tipo di dati può dare fastidio. 2. Attribute disclosure: (trattato più avanti) dati sensibili di un individuo sono rivelati dai dati. 3. Inferential disclosure: Chiamati anche linking, sono quelle informazioni ricavate attraverso le correlazioni fra diversi fonti. Tipologie di disclosure – 12/142 Identity disclosure Utilizzando i macrodata è difficile che esistano possibilità di identity disclosure, in quanto i dati rilasciati sono dati aggregati e a meno che non ci sia carenza di dati e quindi si possa risalire a uno specifico individuo. Vedi Figura 1 oppure la slide 9, nel caso in cui County D è composta da due soli elementi dove entrambi hanno i valori pari a 40-59. Se ci fosse una sola persona e l’attaccante Mallory (M) è a conoscenza di chi sia la persona che è presente nella tabella allora può determinare facilmente i benefit. Nei microdata se riesco a identificare che un individuo è all’interno di un dataset e che una certa tupla appartiene a lui allora si incorre in grossi problemi. Figura 1: Macrodata Count example Attribute disclosure Avviene quando informazioni confidenziali si possono attribuire in modo certo o parziali nei confronti di una persona. Queste informazioni confidenziali permettono di identificare il soggetto con: • Certezza assoluta • Ad un livello abbastanza alto di certezza per cui ci si può considerare esposti Inferential disclosure Riuscire ad ottenere informazioni riservate attraverso correlazioni. Conoscendo che un individuo fa parte di un dataset con determinate malattie. E vedo che alcune malattie sono tipicamente da bambino e alcune sono tipicamente da adulto. Una malattia viene tipicamente ad adulti che fanno il lavoro dell’individuo che conosco. A questo punto posso dire con abbastanza sicurezza che l’individuo che conosco abbia quella malattia. Restricted data and restricted access – 16/142 Intro Come proteggere i dati se li devo rilasciare? In un primo step rimuovo gli identificatori espliciti dell’identità (nome, cognome, email, telefono ecc…), ottenendo quello che viene chiamato dato anonimizzato. Tecniche di protezione per conteggio/frequenza macrodata I dati collezionati sono pubblicati in tabelle che mostrano counts o frequencies. Le tecniche per proteggere questo genere di dati sono: • Sampling (campionatura, calcolare su un campione rappresentativo): pubblicare un sondaggio/panoramica invece di un censimento specifico. • Regole speciali: definire restrizioni sul livello di dettaglio delle informazioni che fornisco. Ad esempio: pubblico gli stipendi con delle soglie 5 -10 -15 -20 • Threshold rules (regole di soglia): regole che definiscono i casi in cui eliminare/sopprimere dati perché si riferiscono a un gruppo molto ristretto di individui e quindi possono diventare sensibili. Tecniche di protezione per microdata Le tecniche per proteggere questo genere di dati sono: • Masking techniques: inserire del “rumore” all’interno dei dati quindi, di fatto, andando a modificare i dati. Questo genere di tecniche può attuarle solo chi rilascia i dati, perché deve stare attento a falsare i dati in maniera mirata; se vengono modificati troppo o in maniera erronea potrebbe invalidare tutta la statistica. 1. Non perturbative: i dati originali non sono modificati ma alcuni dati vengono soppressi o alcuni dettagli rimossi, per esempio: generalizzazione (i dati vengono presi a fasce voti [24-27], [28-30], campionamento (prendo solo un sottoinsieme), soppressione di alcuni valori (invece di 10 esami prendi solo 7 esami di uno studente)] . 2. Perturbative: i dati originali vengono modificati (arrotondo i valori, scambio i valori da un individuo all’altro). • Synthetic data generation techniques: rilasciare dati verosimili invece dei dati reali 1. Fully Synthetic: tutti i dati sono sintetici 2. Partially Synthetic: il dataset rilasciato contiene un mix di dati sintetici e non. The anonimity problem -20/142 Intro I dati che rilascio io non sono gli unici. Esistono molti altri dati che vengono rilasciati da altri enti/persone per cui è possibile fare degli incroci fra i dati (Inferential disclosure). Questo tipo di attacchi vengono chiamati linking attacks quindi un dato che prima era stato de-identificato (cioè tolte informazioni importanti) può essere re-identificato. Vedi slide 21. Classificazione degli attributi nei microdata Gli attributi possono essere classificati in: • Identificatori: identificano unicamente una persona (per esempio codice fiscale). • Quasi-identificatori: attributi che combinati possono identificare una persona. • Confidenziali: attributi che contengono dati sensibili. • Non confidenziali: attributi che non contengono dati sensibili e la cui release non causa disclosure. Fattori che contribuiscono ad aumentare il rischio di disclosure 1. Esistenza di record di alta visibilità (per esempio lavori molto particolari (papa, presidente della repubblica), o redditi molto alti. 2. Possibilità di fare matching fra i microdata e informazioni esterne (individui che hanno una combinazione di informazioni unica o molto particolare). La possibilità di linking aumenta se: • Ci sono tanti attributi in comune fra i microdata e le risorse esterne. • Accuratezza/precisione dei dati. • Più sorgenti hai, più capacità di linking hai. Fattori che contribuiscono a ridurre il rischio di disclosure 1. Una tabella di microdata contiene solo una parte della popolazione (se una persona cerca un individuo specifico può darsi che non sia presente in tabella). 2. L’informazione specificata nei microdata table non è più aggiornata e quindi ha una percentuale di errore. Misure di rischio Bisogna calibrare fra proteggere i dati e renderli utilizzabili. Magari li proteggo benissimo ma non posso più ottenere informazioni utili ai fini dei miei obbiettivi. K-anonimity - 29/142 K-anonimity Non si può dare garanzia di privacy assoluta ma solo un certo livello di incertezza. K-anonimity: nei dati che rilasciati si garantisce che ciascuna tupla sia mappabile indistintamente su almeno k elementi. Nell’esempio della slide 21, se consideriamo una 4-anonimity, oltre che a Sue Doe ci saranno almeno altre tre persone con quelle stesse caratteristiche. Quasi-identifier: insieme degli attributi che possono essere sfruttati per il linking attack. L’insieme delle tuple che potrebbero ricondurre alla persona vengono denominate quasi identifier. In K anonimity si definisce che ogni tupla del quasi-identifier debba apparire almeno k-volte. Per attuare questa k-anonimity possiamo utilizzare le tecniche di protezione trattate precedentemente. In particolare possiamo utilizzarne due (non sporcano i dati): • Generalization: non pubblicare informazioni specifiche ma generalizzare (invece di pubblicare l’anno, il mese e il giorno di nascita, pubblicare solo l’anno. In questo modo la capacità di linking cala drasticamente, oppure come il cap, che si utilizza quello generico, es milano 20100). • Suppression: soppressione di alcuni dati. In questo modo il quasi-identifier non punta più ad una sola persona ma a più persone. Figura 2: Slide 33 Se tu hai una tupla che prende valori da un certo dominio, se ciascuno di questi domini ha una gerarchia sopra, hai anche tutte le possibili combinazioni della gerarchia, tutti i possibili prodotti cartesiani. Figura 3: slide 34 Gerarchia dei valori Mi dice quali valori vengono generalizzati a quali valori del dominio sulla generalizzazione. Per esempio asiatico, nero e bianco sono tutte -> persone (vedi slide 36). Una gerarchia è un albero perché ogni nodo ha uno e un solo padre e la radice non ha padre. Generalized table with suppression – 32/142 Date due tabelle Ti e Tj definite sullo stesso insieme di attributi diremo che Tj è una generalizzazione (con tuple soppresse) di Ti ( viene scritta così ) se: Supponendo di applicare la soppressione al livello della tupla, se ho un singolo attributo che voglio eliminare, vado a eliminare l’intera tupla. Ho generalizzato la razza, ma ho lasciato lo zip code specifico eliminando le tuple con valori univoci. GT è una generalizzazione di PT CIASCUN CLUSTER DI RISPONDENTI E’ ALMENO DI K = 2 (ci sono due categorie di rispondenti: blu e rossi) Più è alto K più è bassa la specificità dei dati • |Tj| ≤ |Ti| ----> La cardinalità di Tj è minore o al più uguale alla cardinalità di Ti • Il dominio dom(A,Tj) di ogni attributo A in Tj è uguale, o è una generalizzazione, del dominio dom(A,Ti) dell’attributo A in Ti (the domain dom(A,Tj) of each attribute A in Tj is equal to, or a • generalization of, the domain dom(A,Ti) of attribute A in Ti) • Per ciascuna tupla di Tj esiste una tupla corrispondente in Ti (non è sempre vero il contrario) It is possible to define an injective function associating each tuple tj in Tj with a tuple ti in Ti, such that the value of each attribute in tj is equal to, or a generalization of, the value of the corresponding attribute in ti. k-minimal generalization with suppression – 39/142 Distance vector: Nella ricerca di una soluzione di generalizzazione è necessario avere la protezione richiesta ma non ridurre l’utilità dei dati (è quindi utile stabilire una soglia di soppressione). Quindi la tabella che preferiremo pubblicare è quella, si generalizzata, ma che rilascia il maggior numero di informazioni. Figura 5: Distance vector Ti è una generazione minimale di Tj quando: • Quando soddisfa la soglia di soppressione (Stabilita in partenza) Figura 4: Generalizzazione con soppressione • Quando la nostra tabella (Ti) ha più tuple di ogni altra tabella Tz che ha sempre lo stesso vettore di distanza. • Quando non esiste alcun’altra tabella che soddisfa le precedenti condizioni con un vettore di distanza minore della mia (Ti) Date due tabelle Ti e Tj tali che Ti <= Tj e dato MaxSup la massima soglia accettata di soppressione di tuple. Tj viene detta k-minimal generalization di Ti se: Tj satisfies k-anonymity enforcing minimal required suppression, that is, Tj satisfies k-anonymity and ∀Tz : Ti <=Tz,DVi,z = DVi,j, Tz satisfies k-anonymity ⇒|Tj| ≥ |Tz| (Soddisfa k-anonimity sopprimendo il minimo insieme di tuple necessarie per soddisfare k-anonimity a quel livello di generalizzazione) (si legge: se Tj soddisfa k-anonimity e per ogni Tz tale che Tz domina Ti e il distance vector DVi,z = DVi,j e Tz soddisfa k-anonimity => Tj ha più tuple di Tz) (in sostanza: qualsiasi altra generalizzazione (tabella generalizzata) che generalizza lo stesso di me sopprime più di me quindi sono meglio io che sopprimo di meno). |Ti|−|Tj| ≤ MaxSup (Non sopprime più tuple della condizione che gli ho dato) ∀Tz : Ti <=Tz and Tz satisfies conditions 1 and 2 ⇒¬(DVi,z < DVi,j) (Qualsiasi altra tabella che soddisfa le prime due condizioni non è mio discendente in gerarchia. (Non ha distance vector più piccolo del mio))(cioè se un’altra tabella generalizza meglio di me ⇒¬(DVi,z < DVi,j)). Computing a preferred generalization – 42/142 I criteri per scegliere la generalizzazione minima sono: • Minima distanza assoluta: Prendo la soluzione che fa meno passi di generalizzazione in totale. è preferibile sempre la minore distanza assoluta ovvero il minore numero di step. • Minima distanza relativa: la distanza relativa è una distanza pesata. Cioè divide ciascun passo per l’altezza della gerarchia. L’altezza della razza per esempio è 1 (asian->person) mentre l’altezza dello zip è 2 (94141->9414*->941**, 94131->9413*->941**, vedi slide 36). Per cui considerare la minima distanza vuol dire che se generalizzo la razza -> 1(passo)/1(altezza)=1 mentre se generalizzo lo zip -> 1(passo)/2(altezza)=1/2=0.5 • Distribuzione massima: preferire la generalizzazione con il maggior numero di tuple distinte • Minima soppressione: preferire la generalizzazione che sopprime meno tuple Classificazione di tecniche di k-anonimity – 43/142 Generalizzazioni e soppressioni possono essere applicate con differenti livelli di granularità: • Generalizzazione: si può applicare a tutta la colonna o anche alle singole celle (se sono in un ospedale in cina e ci sono 995 asiatici e gli altri 5 sono un’italiano, un francese, un tedesco, un russo e uno spagnolo posso generalizzare in “asiatico”, “resto del mondo”) • Soppressione: si può applicare a una riga, una colonna o una singola cella PT tabella di partenza Esempio AG_TS: questa soluzione generalizza a livello attributo e sopprime a livello di tupla Figura 6:Tabella AG_TS Figura 8: Tabella CG&TS Figura 9: Tabella AS_&CS Esempio AG_CS: questa soluzione generalizza a livello attributo (le colonne sono tutte omogenee) e sopprime a livello di cella. Esempio AG_: generalizza a livello attributo e non ho soppressione. Esempio CG_: Generalizzazione a livello di cella (da i dati più specifici e sopprime il meno possibile ma la tabella non è più omogenea). Esempio _TS: Applico la soppressione a livello tupla (non posso rilasciare niente). Esempio _AS: Applico la soppressione a livello attributo Esempio _CS: Applico la soppressione a livello di cella (non generalizzo niente e rilascio solo le informazioni) Algorithms for computing a k-anonymous table – 49/142 Intro Problema computazionalmente difficile, perché per trovare la tabella migliore dovrei provarle tutte. Algorithms for AG_TS e AG_ - AG– 50/142 Generalizzazione Attributi / TS = Soppressione tupla Computing a k-minimal solution Generalizzazione localmente minima: la minima generalizzazione che permette k-anonimity in un ramo dell’albero formato da tutte le possibili generalizzazioni. Una generalizzazione localmente minima può non essere la generalizzazione minima globale ma il contrario si ovviamente. Figura 7:Tabella AG_CS Ammettendo che R1,Z1 è la generalizzazione localmente minima in quel ramo non è detto che lo sia globalmente perché R0,Z1 potrebbe soddisfare la k-anonimity desiderata (Vedi slide 39). Si può utilizzare un algoritmo che utilizza una ricerca binaria. Si taglia l’albero a metà h/2: • Se esiste una soluzione che soddisfa k-anonimity allora taglia ulteriormente a metà h/4 • Se non esiste cerca in 3h/4 To reduce the computational cost, it adopts a distance vector matrix that avoids the explicit computation of each generalized table. Vedi slide 53-54 per degli esempi. Potrebbe però essere che la gerarchia NON è un albero quindi un algoritmo di ricerca binaria si rivelerebbe completamente scorretto! Se generalizzo per anni per esempio e faccio una generalizzazione prima per 10 anni e poi per 25 non ho più un albero. k-Optimize algorithm Viene definito un nuovo sistema per generalizzare i valori. Il sistema in questo caso è generalizzare valori che sono adiacenti. Ad esempio assumendo di avere i domini di generalizzazione in sequenza (all’interno di ciascun dominio di generalizzazione è come se i valori fossero ordinati), invece di rappresentare con asterischi (Es. 92410, 92411 → 9241*) vado a clusterizzare (raggruppare) i valori adiacenti In razza non è possibile ottenere una soluzione più specifica quindi creo un cluster generalizzato In zip, (essendo che 9413 è guale per le prime due coppie e 9414 è uguale per le seconde) posso creare due gruppi. Race ZIP {[asian] [black] [white]} {[94138] [94139] [94141] [94142]} 1 2 3 4 5 6 7 • corresponds to: o Race: {1}, that is: [asian or black or white] o ZIP: {4, 6}, that is: {[94138 or 94139],[94141 or 94142]} Organizzo lo spazio di tutte le possibili soluzioni e costruisco un albero. Per esempio per lo ZIP la foglia più bassa corrisponde a 4 gruppetti differenti (4|5|6|7). La radice corrisponde a un gruppo che contiene tutti (4 5 6 7). L’algoritmo consiste nel partire dalla radice e vedere se le foglie soddisfano le condizioni. Se non le soddisfano posso tagliare direttamente tutto il ramo. Algorithms for _CS and CG_ - 62/142 Mondrian multidimensional algorithm Ci sono almeno due ragioni perché è meglio generalizzare a livello di attributo piuttosto che a livello di cella. La prima ragione è una ragione di efficienza perché le combinazioni di celle sono molte di più. La seconda ragione è l’omogeneità dei dati. Per esempio nella slide 47 i dati sono poco omogenei poiché le date sono tutte diverse. Vedi slide 65. Ogni dimensione per ogni attributo. Mondrian algorithm is flexible and can operate • On a different number of attributes o single-dimension o multi-dimension • with different recoding (generalization) strategies o global recoding (generalizzazione a livello di colonna) o local recoding (generalizzazione a livello di cella) Figura 10:Esempio generalizzazione • with different partitioning strategies (diverse strategie per il taglio del piano. Per esempio nella slide 65 le aree erano disgiunte ma potrebbero essere sovrapposte) o strict (i.e., non-overlapping) partitioning o relaxed (i.e., potentially overlapping) partitioning • Using different metrics to determine how to split on each dimension Approximation algorithms Esistono anche degli algoritmi di approssimazione. k-anonimity revisited Vedi slide 69. La tabella revisited mantiene k-anonimity! Le due sotto invece no! Figura 11: 2 anonymity slide 69 Attribute disclosure – 70/142 intro k-anonymity è vulnerabile ad alcuni tipi di attacchi. Perché il suo scopo è quello di proteggere/confondere l’identità associata ad un record. Il problema è vedere poi le informazioni sensibili e i problemi di correlazione tra i vari dati. Per esempio nella tabella la k-anonimity è soddisfatta ma le due persone in arancione e in rosso hanno la stessa malattia per cui chiunque delle due io sia gli altri sapranno che ho quella malattia. Questo problema viene detto problema di homogeneity. Un altro problema è quello di background knowledge. Ovvero basandomi sulle mie personali conoscenze sulla persona riesco a risalire a quale delle due è in tabella. Se conosco che Mr.X tutte le mattine corre sicuramente non soffre di fiato corto, per cui posso dedurre che soffra di un’altra patologia. ℓ-diversity – 74/142 Oltre ad utilizzare k-anonimity bisogna differenziare i dati sensibili. Continuando con l’esempio delle malattie, bisogna avere almeno L valori diversi, in modo tale da contrastare i problemi di homogeneity. Se Hellen è una donna bianca ed è una maratoneta, difficilmente sarà obesa o avrà il fiato corto oppure malata di cuore; di conseguenza si può dedurre che hellen abbia il cancro. Figura 12: tabella di esempio Avendo una tabella k-anonimizzata devo differenziare i dati sensibili. La tabella si può considerare L diverse quando contiene almeno L valori diversi dello stesso dato sensibile. (Quindi servono cluster di dimensione k con almeno L diversi valori.) La l diveristy rende più difficile anche un attacco di tipo background knowledge Skewness attack (attacco per asimmetria) – 76/142 L-diversity lascia spazio ad attacchi basati sulla distribuzione dei valori all'interno dei cluster. Lo “ Skewness Attack” avviene quando la distribuzione in un cluster è differente dalla distribuzione della popolazione reale. Se avessi una tabella in cui è soddisfatta k- anonimity e ℓ-diversity con 4 record di cui 3 con la stessa malattia, vuol dire che il 75% di coloro che sono in quella tabella hanno quella malattia posso determinare con una certa sicurezza la malattia di una persona. Similarity attack - 77/142 L’attacco di similarità è quando pur essendoci differenze nel nome di attributo, il loro significati sono simili. per esempio ulcera e gastrite, sono due malattie differenti ma non abbastanza per determinare una grande distinzione dal farmi percepire che tipologia di malattia abbia una persona. Group closeness (t-closeness) – 78/142 Dopo aver eseguito k-anonimity, l-diversity, bisogna controllare che i gruppetti abbiano una distribuzione simile a quella reale. Ad esempio evitando i picchi o blocchi di persone con le stesse malattie, ad esempio inserendo una persona in un gruppo dove il 75% ha il diabete, quando nella realtà solo il 20% della popolazione ne soffre. Questo in realtà invalida i dati perché di fatto l’utilità cala drasticamente, in quanto modifico la distribuzione verso quello che è il dato di pubblico dominio. External knowledge – 79/142 The consideration of the adversary’s background or external knowledge is necessary when reasoning about privacy in data publishing. RACE DOB SEX ZIP DISEASE Asian 64 F 941** hypertension asian 64 F 941** obesity asian 64 F 941** chest pain asian 63 M 941** obesity black 63 M 941** obesity black 64 F 941** short breath white 64 M 941** short breath white 64 F 941** heart patient white 64 F 941** short breath white 64 F 941** Cancer white 64 F 941** obesity Figura 13: Skewness attack example table
Questa è solo un’anteprima: 21 pagine mostrate su 106 totali. Registrati e scarica gratis il documento.
Per approfondire questo argomento:
Altri appunti correlati:
Forse potrebbe interessarti:
L'impatto di internet: cultura, economia, stili di vita
PAROLE CHIAVE:
privacyoutsourcing
dati personali
social networks
cloud
protezione dei dati
privatezza
microdati