Data mining: Un sistema di estrazione di pattern frequenti che protegge l'anonimato

Capitolo 1

Introduzione

1.1

Contesto

Il data mining `e una fase ben definita all’interno del modello Knowledge Dis-covery in Database (KDD). Il KDD consiste in una procedura che permette di estrarre conoscenza implicita a partire dai dati contenuti in un database. Questa procedura comprende sia fasi di preparazione dei dati (filtering, etc..), sia la fase stessa del data mining, che rappresenta la parte fondamentale di estrazione della conoscenza.

L’evoluzione del KDD, e del data mining nello specifico, ha portato, a par-tire da un modello non standard, ad un modello procedurale (eventualmente interattivo) le cui fasi sono ben definite e distinte: ci`o che una volta era con-siderato solo un processo di analisi generico `e ora ormai inteso in maniera univoca e rappresenta un’importante campo di ricerca a s´e stante.

Nello specifico, il data mining consiste in una procedura che, partendo da dati di ingresso pre-elaborati, produce della conoscenza, che pu`o essere eventumente post-elaborata. I dati di ingresso sono tipicaeventumente quelli contenuti al-l’interno di uno o pi`u database e vengono analizzati ed elaborati per produrre della conoscenza, cio`e informazioni che non sono visibili se non considerando e analizzando l’intero insieme dei dati.

Durante la fase di mining vengono costruiti, a seconda dell’esigenza o per meglio dire del campo applicativo di analisi in funzione della natura dei dati, opportuni modelli per rappresentare efficacemente la conoscenza contenuta in essi attraverso l’utilizzo di adeguati algoritmi di data mining.

In letteratura esistono svariate classi di problemi che vengono risolti elegan-temente con il data mining e svariati modelli per rappresentare la conoscenza contenuta nei dati. La flessibilit`a del data mining ha permesso, in modo

rapi-do, di estendere i suoi processi in tutte quei campi in cui `e necessario eseguire delle post-analisi per cercare nuovi benefici dai dati in possesso.

Storicamente il data mining `e stato utilizzato in contesti ristretti dove i dati e la conoscenza rimanevano confinati all’interno di una stessa organizzazione. Recentemente si `e invece registrata la necessit`a di condividere la consocenza e, eventualmente, le informazioni da parte di pi`u organizzazioni.

Di conseguenza, il pi`u ampio utilizzo di questa tecnica ha introdotto prob-lemi che, in principio, non erano stati considerati. Un problema fondamen-tale `e rappresentato dal mantenere segreti i dati di ingresso contenuti nei database. Infatti, sfruttando alcune tecniche di analisi, `e possibile, a partire dalla conoscenza estratta dal processo di data mining, delle informazioni rel-ative a singoli individui. Chiaramente questo pu`o rappresentare un problema se tali informazioni non possono essere divulgate.

Questa questione, oggetto di studio e di ricerca, non `e ancora del tutto risolta e resta un problema aperto. Essa accomuna tutte le branche del data mining e in particolare la questione di mantenere anonimi i dati risulta essere di grande interesse dalla comunit`a scientifica e non solo.

Il problema della privacy nel data mining in qualche modo `e correlato al concetto di ”sicurezza”. Questo termine risulta essere troppo generico e poco caratterizzante in quanto nel settore dell’ informatica copre svariati campi. La questione della sicurezza infatti abbraccia diversi problemi in qualsiasi contesto la si voglia studiare.

Pi`u appropiatamente in letteratura si parla di politiche di sicurezza e di meccanismi di protezione. La protezione almeno dal punto di vista logico, se ci immaginiamo di disporre questi problemi organizzati per livelli, risulta essere ad un livello inferiore rispetto la sicurezza.

Se per esempio consideriamo un elaboratore e l’insieme degli applicativi for-niti con esso possiamo distinguere:

• Sicurezza In questo caso cataloghiamo tutte quelle tematiche che riguardano il problema di come proteggersi da eventuali attacchi ai servizi che offre il sistema. Questi attacchi possono essere portati a vari livelli del sistema.

Nel ottica di un elaboratore che ospita un database ”server” possiamo pensare a un attacco che cerca di scardinare il sistema di autentifi-cazione degli utenti.

• Protezione Nel caso dell’elaboratore possiamo immaginarci il proble-ma di come gestire gli accessi alla memoria da parte dei processi. Dal punto di vista di database, un possibile attacco potrebbe essere quello

che tenta di invocare alcune operazioni di cui non si dispone i diritti per eseguirle, con il fine di accedere a porzioni di dati riservati.

Quindi nell’ottica del data mining, di pari passo allo sviluppo di algoritmi pi`u efficienti possibili per poter estrarre conoscenza dalle innumerevoli fonti di dati, il problema della privacy, la cui natura appartiene a tutt’altra disciplina, detiene un ruolo fondamentale.

In queso contesto, il compito di questa tesi `e focalizzare l’attenzione sul problema della privacy o e di come proteggere l’anonimato dei soggetti rap-presentati nei dati.

1.1.1

Obiettivi

Il lavoro di tesi consiste in un prima fase, nello studio di un modello di protezione dell’anonimato operante su database binari gi`a esistente proposto in[...].

Differentemente dai modelli estistenti, che propongono di applicare le tec-niche di protezione direttamente ai dati di un database, questo modello pro-pone, partendo dai dati in ingresso, di estrarre conoscenza la con il data mining, per poi successivamente elaborarla con algoritmi capaci di verificare che la stessa conoscenza estratta non contenga informazioni utili a violare l’anonimato dei soggetti rappresentati nei dati.

L’implementazione di questo modello consiste in in ”Tool” per database bina-ri suddiviso in due fasi. Nella pbina-rima fase si esegue il processo di ”Detection” che individua la conoscenza che viola i principi di anonimato e che quindi risulta potenzialmente pericolosa per la privacy dei soggetti rappresentati. Nella seconda fase viene proposto un sistema di ”Sanitizzazione” capace di eliminare tali minaccie.

Successivamente a questo studio si `e preso in esame un piccolo modello di database relazionale che presenta attributi pi`u complessi. L’obbietti-vo postosi, `e stato la formalizzazione e l’estensione di un modello teorico sulla base di quello gi`a esistente, capace di applicare i principi di garanzia dell’anonimato ai database relazionali.

Il risultato di questo studio si concretizza in un modello teorico e in un algortimo capace di individuare tutta quella conoscenza che non soddisfa i vincoli di anonimato imposti dal sistema di protezione.

1.1.2

Risultati

Il risultato ottenuto dal lavoro di tesi `e l’implementazione di un prototipo di un Tool capace di operare su databases relazioni. Il prototipo `e stato

realizzato utilizzando il linguaggo Java e quindi ”gira” in un ambiente con ”Virtual Machine” e si presta al porting su pi`u piattaforme.

Dai test effettuati il prototipo reagisce in modo pi`u che sufficiente alle sol-lecitazioni a cui `e stato sottoposto. I risultati collezionati risultano essere incoraggianti anche se ulteriori indagini andrebbero compiute su macchine pi`u commerciali capaci di gestire l’input proveniente da grandi database. Rimanendo sempre nel contesto, sicuramente per avere un sistema pi`u ro-busto e performante, si potrebbe anche optare per il porting del codice su altre piattaforme di sviluppo.

Rispetto al Tool operante su database binari il prototipo sviluppato in ques-ta tesi non presenques-ta il modulo di Sanitizzazione. Questo problema viene in parte affrontato nell’ultimo capitolo del lavoro svolto in questa tesi. In par-ticolare viene aperta una parentesi su un possibile modello di Sanitizzazione per database relazionali che fa uso di tecniche che combinano gli approcci utilizzati per la Sanitizzazione di database binari.

La tesi si conclude lasciando al lettore alcune possibilit`a su come poter am-pliare il lavoro svolto qualora si volesse studiare in dettaglio ed implementare un sistema per uso commerciale.

Capitolo 2

Data mining e Privacy

2.1

Introduzione

In questo capitolo, nella prima parte, introdurremo i concetti di modello dei dati, di inferenza e del perch`e in generale insorgono problemi di privacy quan-do di devono divulgare i dati. In seguito saranno esaminati alcuni modelli di protezione dei dati.

2.2

Privacy e anonimato nei Database

Prima di introdurre il concetto di data mining va rivolta una breve pre-cisazione al modello dei dati utilizzato. Le informazioni sono la base su cui viene condotta l’attivit`a economica, sono politicamente, commercialmente e personalmente sensibili per lo sviluppo aziendale.

Oggi giorno l’intera collettivit`a dei dati `e memorizzata nella moltitudine di DBMS sparsi nel mondo. In particolare i dati sono strutturati e raggruppati in insiemi omogenei e spesso sono in relazione tra loro. Un modello dei dati [...] fornisce un’insieme di meccanismi di astrazione per definire in modo corretto un contenitore per i dati meglio conosciuto come database.

Nel nostro contesto per semplicit`a utilizzeremo il modello relazionale dei dati e quindi lavoreremo con tabelle, tuple e gli opportuni linguaggi per le interrogazioni. Di seguito riportiamo le seguenti definizioni:

Definizione 2.2.1 (Tabella). Insieme non ordinato di tuple.

Definizione 2.2.2 (Tupla). Se T1,..., Tn sono tipi di dato e A1,..., An

attributi allora: (A1:T1,..., An:Tn) `e una tupla di grado n.

Nell’ottica del data mining spesso si lavora con dataset che sono grosse tabelle che rappresentano i dati sorgenti su cui effettuare il mining e le analisi.

Queste analisi saranno rivolte ai fini di modellare una conoscenza ”diver-sa”, non intrensecamente contenuta nel modello dei dati che normalmente modella la conoscenza ”concreta” ma, che con opportune tecniche, pu`o essere estratta.

2.2.1

Inferenza sui Dati

Le informazioni, sono un bene di grande valore per l’azienda e pi`u in generale per l’intera comunit`a. Generalmente quando si ha a che fare con i dati, che rappresentano le informazioni, ci si domada cosa si possa fare con essi. Negli ultimi anni il data mining ha permesso, usando una o pi`u tecniche, di esplorare i dati di cui si dispone in modo da poter estrarre nuova informazione Tale informazione non `e semplicemente l’insieme dei dati memorizzati, ma pi`u in generale `e l’informazione che si pu`o inferire dalla base di dati.

Da un punto di vista logico esistono essenzialmente due principali tecniche di inferenza:

1. la deduzione;

2. l’induzione;

La deduzione permette di inferire informazione che sia conseguenza logica del-l’informazione contenuta nella base di dati. Molti sistemi di gestione di basi di dati (DBMS), quali i sistemi relazionali, mettono a disposizione semplici operatori di deduzione dell’informazione, ad esempio l’operatore di Join. Un notevole sforzo `e stato fatto per sviluppare basi di dati deduttive che arric-chiscono i normali DBMS con capacit`a di deduzione logica (KBMS,Knowledge Base Managment Systems).

L’induzione permette di inferire un’informazione pi`u generica dell’ infor-mazione contenuta nella base di dati. Questo tipo di informazione, che costituisce conoscenza, per lo pi`u individua delle propriet`a sugli oggetti. Queste propriet`a in generale, sono combinazioni di valori di certi attributi condivisi da tutti i fatti della base di dati. Utilizzado la logica proposizionale possiamo facilmente esprimere queste propriet`a in termini di ”pattern”. Possiamo quindi dire che la differenza sostanziale tra deduzione e induzione `e che la prima inferisce sempre dati che possono essere dimostrati validi all’interno della base di dati, purch´e ovviamente la base di dati sia corretta, mentre la seconda inferisce asserzioni che sono solo supportate dalla base di dati ma che potrebbero non essere valide in generale.

Uno dei compiti principali dell’induzione, consiste pertanto nel selezionare i pattern pi`u credibili che riducano al minimo gli errori nel caso siano speri-mentate su fatti precedentemente sconosciuti.

Molti DBMS supportano capacit`a di inferenza deduttiva (KBMS), mentre ancora sono pochi quelli che supportano capacit`a di inferenza induttiva. Es-iste, dunque, un crescente interesse nell’estendere i DBMS con capacit`a di inferenza induttiva e, ritornando ai concetti introduttivi, il data mining pu`o essere visto come un processo di apprendimento induttivo.

2.2.2

Apprendimento e Privacy

A qesto punto con certezza possiamo affermare che l’inferenza sui dati ci porta ad apprendere nuove informazioni non conosciute a priori.

Uno dei problemi pi`u studiati nel data mining `e il processo di scoperta degli item frequenti[...] i quali individuano le regolarit`a sui dati esprimibili come pattern. Infatti la scoperta di pattern nascosti gioca un ruolo fondamentale in tutti quei processi decisionali dove spesso le strategie da prendere, sono strettamente collegate alle informazioni inferite dai dati di partenza.

Poich`e il data mining `e strettamente legato ai dati provenienti dai database viene spontaneo domandarsi: che tipo d’informazioni si possono estrarre?, inferire?.

Sicuramente non dovrebbe essere permesso di riuscire a estrarre informazioni srettamente confidenziali che nella fattispecie individuano univocamente in-dividui e/o informazioni di natura riservata.

Il problema pi`u frequente, `e che spesso divulgando questi pattern, utilizzando tecniche inferenziali, si pu`o risalire a informazioni personali o nello spefico a informazioni capaci di individuare un soggetto rappresentato nei dati. Questa problematica, i recenti studi e l’avanzamento tecnologico hanno inau-gurato una nuova era, dove gli algoritmi di data mining vengono considerati da un altro punto di vista, quello di come preservare la privacy.

Per esempio la Comunit`a Europea [...] definisce:

Dati personali: Tutte le informazioni che identificano o che possono essere utili ad identificare un individuo (soggetto). In particolare un individuo iden-tificabile `e una persona che, direttamente o indirettamente, viene identificata tramite un numero di identit`a o utilizzando altri fattori pi`u specifici come: Stato di salute, fattore economico, identit`a sociale o culturale, etc.

I fattori specifici (dati specifici) che permettono di individuare un certo sogget-to possono essere mantenuti solo per un periodo di tempo strettamente nec-essario allo scopo per il quale sono stati raccolti.

Quando si ha a che fare con il rilascio di dati, nelle comunit`a scientifiche, spesso e volentieri si fa molta confusione. Infatti il vocabolo privacy con-cettualmente pu`o riferirsi a pi`u contesti.

Possiamo distinguere almeno due punti di vista:

1. privacy sui dati

In questo caso ci si riferisce al problema di come mantenere nascoste alcune informazioni affinch`e non vengano utilizzate per indentificare univocamente gli individui proprietari delle stesse. Nell’ottica del data mining si cerca di filtrare opportunamente i dati sorgenti al fine di evitare questo problema.

2. privacy collettiva

In questo caso si ci si riferisce al problema di rilasciare informazioni su collezioni di dati piuttosto che sul singolo. Infatti si cerca di proteggere il contenuto (propriet`a) dei dati perch`e se si utilizzano tecniche di in-ferenza come abbiamo gi`a detto `e possibile estrarre questi contenuti. Nell’ottica del data mining si cerca di filtrare i contenuti potenzialmente pericolosi.

Una domanda interessante, per ci`o che `e stato detto fino ad ora, `e: come `e possibile estrarre pattern iteressanti da una o pi`u collezioni di dati e contem-poraneamente mantenere protette, sicure, tutte le informazioni sensibili? In linea di principio la risposta non esiste ma, si cerca di studiare come trovare un giusto compromesso tra l’utilizzo di algoritmi rispettosi della pri-vacy sui dati e, la ”distorsione” che si ha su essi al fine di ottenere delle analisi abbastanza attinenti alla realt`a.

Per distorsione si intende l’alterazione dei dati in output rispetto ai dati originari. Infatti in questo conteso, un problema antagonista alla questione di come proteggere i dati, risulta essere il problema di come minimizzare la distorsione introdotta, causata dalle modifiche apportate ai dati.

Tuttavia, i dataset (contenitori dei dati sorgenti), generalmente vengono costruiti partendo da dati che possono provenire anche da pi`u database. In generale per costuire un buon dataset al fine di creare un insieme di pattern validi per le analisi, `e necessario inglobare informazioni con un certo grado di riservatezza, non escludibili a priori. Risulta perci`o difficile individuare un compromesso che bilanci i due pesi.

In generale in tutti i metodi utilizzabili, che hanno l’obbiettivo di preservare la privacy degli individui e, quindi mantenere anonime le informazioni, il ruolo della distorsione nei dati `e un aspetto che accomuna tutti. Il problema `e di grande interesse in quanto non esitono formalismi standard ben delineati.

Possiamo cos`ı affermare che il problema di applicare il data mining rispettoso della privacy, non `e tuttora una metodologia a s`e stante, con un suo ciclo di vita ben definito. Spesso per risolvere i problemi si opta per soluzioni ad hoc.

2.3

K-Anonymity

Un pratica adotta da quasi tutte le organizzazioni che hanno a che fare con il rilscio dei dati, con l’obbiettivo di mantenere anonime le informazioni rilasciate, consiste nel non divulgare attributi che possono risultare espliciti identificatori dei soggetti rappresentati nei dati (nome, indirizzo, telefono, etc.).

Infatti, in linea di principio, possiamo suddividere gli attributi di una tabella o pi`u in generale di un database, in due principali categorie: informazione sensibile (IS) e non sensibile (INS). Le informazioni sensibili comprenden-dono tutti gli attributi che, individualmente o combinati tra loro, possono identificare i soggetti (persone) di una tabella. Le informazioni non sensi-bili per quanto appena detto rappresentano l’inseme opposto, di solito sono attributi meno caratterizzanti.

Fino a pochi anni fa, questa forma di protezione era pi`u che sufficiente per garantire la privacy dei dati rilasciati. Con il sopravvento di database re-lazionali, distribuiti e, l’espandersi delle nuove tecnologie a un utenza sempre pi`u domestica, il problema di proteggere i dati `e diventato pi`u complicato. Infatti, il poter disporre di pi`u sorgenti di dati da cui estrarre contempo-raneamente pi`u informazioni, in modo pressoch`e immediato, ha comportato che non divulgare l’informazione sensibile, in generale, non da garanzie sul fatto che in effetti i dati siano al sicuro.

In molti casi, accade che utilizzando i dati rimanenti, `e possibile, comunque, ridentificare gli individui rappresentati unendo pi`u informazioni rilasciate da una o pi`u organizzazioni.

La figura 2.1 fa vedere come `e possibile individuare informazioni prettamente confidenziali unendo dati provenenienti da database differenti.

Tra tutti i modelli di protezione dei dati presentati in questi ultimi anni, un modello che ha trovato un rimedio semplice ed intuitivo al problema di poter ridentificare gli individui rappresentati nei dati, `e il modello di k-anonymity. Il principio di funzionamento si basa sul concetto di mantenere anonime le informazioni rendendole meno distinguibili tra loro.

Quindi, dato un universo di individui (soggetti o entit`a), si cerca di raggrup-pare i soggetti in gruppi di cardinalit`a finita e, fissata una soglia di

indistin-Figura 2.1: Esempio di unione di due sorgenti di dati

guibilit`a rappresentata dal un valore numerico k, si controlla che all’interno di ogni gruppo non sia possibile distinguere meno di k individui.

Definizione 2.3.1 (k-anonymity). Indicando con C(t) il contenuto di una generica tupla t, diremo che una tabella D `e k-anonima se per ogni tupla t appartenente all’insieme delle tuple T esistono k-1 tuple t1, t2, ... , tk-1 appartenenti a T tale che C(t) = C(t1) = C(t2) = ... = C(tk-1).

Inoltre il modello propone di suddividere l’informazione in un altra categoria e, utilizzando i concetti del modello dei dati in uso, definiamo [...] un attrib-uto quasi-identifier come:

Definizione 2.3.2 (Attributi Quasi-Identifier). Data una tabella T l’inseme degli attributi Quasi-identifier QI comprende tutti quegli attributi che uniti con informazioni esterne identificano unicamente alcuni record.

Definizione 2.3.3 (Attributi Quasi-Identifier). Data una tabella T l’inseme degli attributi Quasi-identifier QI comprende tutti quegli attributi che poten-zialmente possono essere utilizzati per unire un record di T con informazioni del mondo reale ai fini di identificare un individuo con buona probabilit`a. Differentemente dai criteri utilizzati in passato, che focalizzavano l’atten-zione solo sugli attributi che appartenevano alla categoria dell’informal’atten-zione sensibile, questo nuovo modello pone l’attenzione su un nuova tipologia di attributi che appartiene ad entrambre le categorie.

Questi attributi, chiamati Quasi-identifier, risulanto essere le vere minacce che possono essere utilizzate allo scopo di ridentificare gli individui rappre-sentati nei dati.

Quindi ritornando al concetto di k-anonymity l’insieme di attributi che ci intressa mantenere anonimi e quindi k-anonimizzare sono tutti gli attributi Quasi-identifier.

Figura 2.2: Classificazione dell’informazione

2.4

Vari Approcci per preservare la privacy

Negli utlimi anni, la comunit`a scientifica e la ricerca industriale hanno svilup-pato e proposto, per porre rimedio al problema emergente, diversi approcci e molte tecniche per preservare la privacy.

Tra le pi`u importanti abbiamo:

• Modifica dei dati

In questo caso vengono utilizzati degli schemi per modificare il valore di certi attributi contenuti nel database originale, ci`o consente un grado molto alto di protezione.

I criteri utilizzati sono:

1. Perturbazione

Il valore di un attributo viene cambiato con un altro a seconda del dominio dell’attributo.

2. Blocco

Il valore di un attributo viene cambiato con il simbolo ?. In questi casi l’attributo non viene considerato.

3. Unione

Il valore di pi`u attributi vengono uniti per formare una nuova categoria.

• Oscuramento dei dati o di regole

In questo caso una volta ottenuti i risultati, sotto forma di regole, applicando le possibili tecniche di data mining, si cerca di nascondere i dati che violano la privacy in funzione dell’insieme delle regole ottenute. Di fatto, nascondere certe informazioni per evitare che alcune regole, ricavate dalla fase di mining, vengano divulgate, risulta essere un pro-cedimento abbastanza macchinoso e complesso.

• Modelli selettivi di protezione

Quest’ultimo approccio `e pi`u che altro rivolto agli algoritmi che preser-vano la privacy e in particolare a come essi scelgono i criteri per se-lezione i dati che devono essere modificati.

In particolare abbiamo:

1. Metodi euristici

Il metodo maggiormente utilizzato `e la Modifica adattiva.

Vengono modificati tutti quei valori (tra quelli selezionati) in modo da minimizzare la perdita d’informazione contenuta nei dati. 2. Metodi crittografici

I metodi crittografici vengono utilizzati in particolari scenari, ad esempio quando un algoritmo di data mining lavora su dati che risiedono su pi`u basi di dati. In questo caso l’obbiettivo `e quello di fornire solo le informazioni necessarie al processo di mining e proteggere quelle non coinvolte.

In generale per risolvere il problema si ri fa al modello SMC (Se-cure Multiparty Computation) [...] dove alla fine del processo ogni parte conosce solamente il proprio input e il proprio output. In particolare questa tecnica non `e solamente utilizzata per basi di dati distribuite ma, pu`o essere adottata anche su singole quando si vuole risolvere il problema di effettuare delle Join Union tra pi`u tabelle mantenendo anonimi i risultati ottenuti applicando l’operatore di Join.

3. Metodi basati sulla ricostruzione

I metodi pi`u usati si basano, grazie all’uso di particolari algoritmi, sulla randomizzazione dei dati. In una prima fase i dati in input vengono randomizzati e successivamente si cerca di ricostruire la loro distribuzione. Queste fasi si alternano finch`e non viene trova-ta una soglia oltre alla quale i dati ricostruiti sono irroconoscibili. Una volta modificato, il database pu`o essere rilascito.

Altre possibili metodi sono quelli che utilizzano tecniche di in-verse recontruction per ricotruire i dati di partenza. Per esempio in [...] viene proposto un modello che in una prima fase appli-ca il data mining per estrarre la conoscena, sotto forma di pat-tern, dai dati sorgenti. Successivamente i pattern vengono ripuliti delle informazioni sensibili per poi successivamente procedere alla ricostruzione del database.

del problema, trovare il giusto compromesso per scegliere un metodo rispetto un altro. L’unica cosa che accomuna l’interesse di tutti i metodi e criteri che vogliono garantire l’anonimato nel processo di estrazione dei dati con il data mining e, che pu`o essere presa come pietra di paragone tra i vari metodi, `e la misura della distorsione sui dati. Infatti come ribadito `e di vitale importanza, ai fini delle analisi, minimizzare la perdita d’informazione.

2.4.1

Modello di Data Mining rispettoso della privacy

Tra i processi di mining rispettosi della privacy uno schema che accomuna la visione di gran parte della comunit`a scientifica `e quello proposto in figura.

Figura 2.3: Data Mining rispettoso della privacy 1

Fondamentalmente partendo dalla base di dati, si estraggono i dati sotto forma tabellare e si aggregano in dataset. Successivamente i dati vengono sottoposti ad un processo di Detection il quale individua quali informazioni possono essere rilasciate e quali invece devono essere protette. Questa scelta viene effettuata valutando la tipologia degli attributi che compongono le tuple. Un possibile approccio potrebbe essere quello di utilizzare i criteri accennati nel paragrafo sulla k-anonymity.

Terminata questa fase i dati vengono ripuliti opportunamente nel processo di Sanitization utilizzando uno o la combinazione di p`u metodi di modifica dei dati tra quelli citati. In particolare si ripuliranno le informazioni che contengono possibili minacce, intese come inferenze.

Una volta ripuliti i dati, essi verranno trattati con con gli opportuni algoritmi che il data mining offre. Terminata questa fase e ottenuto un output sotto forma di un insieme di pattern, si potr`a procedere alla fase di pubblicazione e al loro rilascio.

Un modello antagonista a quello appena proposto e, che risulta sempre vali-do, propone di invertire le fasi. L’idea di base `e quella di applicare prima il processo di data mining per estrarre prima i pattern e successivamnete applicare le fasi di Detection e Sanitization.

Anche se sembrano abbastanza somiglianti come caratteristiche, in realt`a i due modelli risultano essere differenti. Infatti mentre il primo modello lavora con tuple, caratteristiche delle tabelle relazionali, il secondo lavora con i pattern estratti dalla base di dati.

Quindi in generale oltre alla filosofia di base che `e diversa, anche tutti gli al-goritmi in pratica sono incompatibili poich`e da un punto di vista di strutture dati sono ben distinti.

Figura 2.4: Data Mining rispettoso della privacy 2

Nel primo modello la fase Detection risulta essere abbastanza semplice e min-imale in quanto l’individuazione delle informazioni pericolose consiste nella scelta gli attributi che non devono comparire in output o che devono essere modificati. Scarso interesse e poco spazio viene lasciato alla possibilit`a di utilizzare tecniche di inferenza per cercare di individuare nuove informazioni che potrebbero violare la privacy.

Queste tecniche si prestano maggiormente ad essere utilizzate nel secon-do modello poich`e risulta pi`u efficiente e immediato applicare l’inferenza ai pattern.

Non si pu`o negare che in entrambi i modelli possono essere applicati, almeno dal punto di vista logico, gli stessi principi base per la fase di Sanitizzazione. Questo perch`e tutti i metodi di modifica dei dati combinati insieme ai metodi di oscuramento risultano efficaci e validi per ambedue i modelli.

La differenza fondamentale tra i due modelli `e il guadagno che si ottiene nella qualit`a delle analisi che si vogliono fare in un successivo momento. Favorevole a quanto appena detto il secondo modello risulta pi`u interessante. Infatti modificare i pattern, che rappresentano la conoscenza estrapolata dai dati di partenza, garantisce che l’output prodotto contenga una quantit`a d’informazione pi`u ricca dal punto di vista dei contenuti (minore distorsione sui dati).

Possiamo cos`ı affermare che modificare i pattern risulta essere la via pi`u efficace ai fini di analisi pi`u attendibili, tuttavia ci`o si paga in termini di complessit`a del modello.

2.5

Conclusioni

In questo capitolo abbiamo dato una panoramica sulle tecniche esistenti per mantenere anonime le informazioni nei database e i vari problemi correlati. Abbiamo visto che uno dei principi fondamentali, ampiamente utilizzato, `e il principio di k-anonymity. Tale principio viene utilizzato in molti modelli di data mining rispetto della privacy.

In generale, in tutti i modelli esistenti, oltre all’obiettivo di garantire la priva-cy, il secondo obiettivo `e limitare il degrado dell’informazione causato dalle modifiche apportate ai dati. Dopo aver fatto un breve paragane tra due possibili modelli di data mining che rispettano i principi di k-anonymity, si `e evidenziato che il secondo modello rimane pi`u vicino anche al secondo obbiettivo.

In particolar modo nei prossimi capitoli, l’oggetto del nostro studio sar`a un modello di protezione per database binari e inter-attributo che ricalca le linee del secondo modello.

Capitolo 3

K-anonymous Patterns

3.1

Introduzione

Nel precedente capitolo sono stati introdotti due modelli di protezione per preservare la privacy nei database. Il primo modello proponeva di modificare tutte le informazioni che erano ritenute sensibili e in seguito effettuare il mining sui dati ripuliti e ritenuti sicuri.

Questo approccio in realt`a lascia un problema ancora aperto: applicando il data mining ai dati ripuliti, `e possibile che i risultati ottenuti di per se violino la privacy?

In effetti, il secondo modello proposto, pu`o essere visto come un modello antagonista, perch`e estrarre prima i pattern con il data mining e in seguito ripulirli dalle informazioni che rappresentano delle minaccie per la privacy risulta essere un metodo pi`u sicuro che assicura maggiori garanzie sui risultati ottenuti.

In questo capitolo verr`a analizzato e commentato un modello di protezione operante su database binari.

3.2

Dai dati ai pattern

La principale differenza tra i due modelli di protezione sta nel fatto che il primo pone l’attenzione sui dati dati veri e propri, le cos`ı dette tuple, mentre nel modello che andremo ad analizzare studieremo e daremo maggiore enfasi ai pattern estratti con il data mining.

Introduciamo alcune definizioni:

Definizione 3.2.1 (Database Binario). Un database binario D ={I,T} `e formato da un insieme finito di variabili binarie I ={i1,...,ip}, chiamati anche

In particolare ogni transazione `e un vettore binario di dimensione p conte-nente una combinazione di item.

Definizione 3.2.2 (Pattern). Un pattern p per l’insieme delle variabili I e `e una formula proposizionale costruita con connettivi AND(∧), OR(∨), NOT(¬) sulle variabili in I. Il dominio dei possibili pattern `e indicato come Pat(I).

Definizione 3.2.3 (Supporto). Dato un database D, una transazione t ∈ D e un pattern p diremo che p(t) `e vera se tutti gli item di p in t sono veri. Il supporto di p in D si ottiene come il numero di transazioni che rendono vero p:

supD(p) = |{t ∈ D | p(t)}|.

Esempio database binario

D t a b c d e f g h t1 1 1 1 1 1 1 1 1 t2 1 1 1 1 1 0 1 0 t3 1 1 1 1 1 0 0 0 t4 1 1 1 1 1 1 1 0 t5 1 1 1 1 1 0 0 0 t6 1 1 1 1 1 0 0 0 t7 1 1 0 1 1 0 0 0 t8 1 0 0 0 1 1 1 0 t9 0 0 1 1 1 1 1 0 t10 0 0 1 1 1 0 0 0 t11 0 0 1 1 1 1 1 1 t12 1 1 0 0 0 1 1 0

Tabella 3.1: database binario

Dal database in tabella 3.1 secondo la definizione appena data abbiamo che alcuni possibili pattern sono:

p1 = {e ∧ (¬b ∨ ¬d )} per b,d,e ∈ I con sup_D(p1) = 4

p2 = {a ∨ f} per a,f ∈ I con sup_D(p2) = 11

p3 = {h ∧ ¬b} per h,b ∈ I con sup_D(p3) = 1

Rispolverando il principio di k-anonymity introdotto introduciamo la seguente definizione:

Definizione 3.2.4 (Pattern k-anonimo). Dato un database binario D e una soglia di anonimit`a k, un pattern risulta essere k-anonimo s.se:

supD(p) ≥ k o supD(p) = 0.

Se il supporto di un generico pattern p ha un valore molto basso e in generale minore rispetto alla soglia di anonimit`a k, esso non rispetta i principi di k-anonymity e rappresenta un problema per l’anonimit`a di tutti quegli item per i quali il pattern risulta vero.

Ponendo il problema da un punto di vista di un utente malintenzionato in possesso dell’output divulgato da un processo di data mining, il nostro ob-biettivo sar`a lo studio di come evitare che riesca, partendo dai risultati di sintesi a identificare gruppi di pattern non k-anonimi.

In particolare questo problema si pone come fase successiva all’estrazione di itemset frequenti da un database. Quindi, prenderemo in esame solo quei pattern ottenuti dall’insieme degli itemset frequenti.

Definizione 3.2.5 (Itemset σ-Frequenti). L’insieme degli itemset contenuti in 2I _{`e una classe di pattern ottenuti come combinazioni di item in AND(∧).}

Dato un database D e una soglia minima di supporto σ l’insieme degli itemset frequenti FI `e definito come:

F(D,σ) = {hX, supD(X)i | X ∈ 2I ∧ supD(X) ≥ σ }

Il problema di computare l’insieme degli itemset frequenti `e una delle fasi principali dal data mining. Esso viene elegantemente risolto con l’algoritmo Apriori[...] . In una prima fase vengono selezionati gli item di cardinalit`a uno che hanno supporto maggiore di σ.

Rispettando questo vincolo, nelle fasi successive si accoppiano di volta in volta gli item formando itemset con cardinalit`a maggiore, finch`e esistono combinazioni di item il cui supporto `e maggiore di σ.

L’insieme dei pattern risultanti che sono σ-frequenti rappresentano un sot-toinsieme di tutti i possibili pattern in Pat(I).

Quindi, data una soglia k di anonimit`a con k << σ il problema per tanto si rivolge a come individuare e bloccare l’inferenza che mette in relazione i pattern frequenti che individuaano pattern che hanno supporto minore di k. In generale, abbiamo che k `e molto minore di σ poich`e k assume valori pi`u pic-coli di uno, due ordini di grandezza rispetto σ. Ci`o `e dovuto esclusivamente alla natura dei soggetti trattati.

Infatti un database pu`o contenere decine, migliaia di tuple memorizzate in una sola tabella e, il valore di σ `e proporzionale alla sua grandezza. Se in una tabella vogliamo mantenere anonimi alcuni attributi o combinazioni di essi,

intuitivamente k non potr`a mai assumere valori molto grandi poich`e general-mente, identificare un soggetto, vuol dire aver individuato una determinata combinazione di attributi con supporto molto basso.

Una propriet`a fondamentale che accomuna tutti i pattern risultanti `e la seguente:

Propriet`a 3.2.1 (Propriet`a anti-monotona). ∀ itemset X,Y ∈ 2I _{tale che}

X ⊂ Y si ha che supD(X) ≥ supD(Y).

La propriet`a sintetizza il fatto un pattern X sottoinsieme Y, che ha quindi cardinalit`a minore, ha sempre supporto maggiore.

newline

Figura 3.1: F(D,σ) per database in tabella 3.1 con σ = 7

3.3

Canali di Inferenza

Il problema di evitare che un utente malenintenzionato possa identificare pattern non k-anonimi `e connesso alle possibilit`a di poter inferire nuovi pattern.

Se nell’insieme degli itemset σ frequenti esistono due pattern {a1 ∧ a2} e {a1

∧ a2 ∧ a3}, da cui `e possibile inferire (a seconda dei supporti) l’esistenza di

un pattern {a1 ∧ a2 ∧ ¬a3} il cui supporto `e minore di k, allora abbiamo

individuato un pattern non k-anonimo.

Definiamo in modo formale il concetto di supporto di inferenza.

Definizione 3.3.1 (Database compatibile). Un insieme S di coppie hX, ni con X ∈ 2I _{e n ∈ N e un database D si dicono compatibili se e solo se ∀} hX, ni ∈ S supD(X) = n.

Definizione 3.3.2 (Supporto di inferenza). Dato un insieme S di coppie hX, ni con X ∈ 2I _{e n ∈ N e un pattern p ∈ Pat(I). Supponiamo che esista}

un database D compatibile con S. Per supporto di inferenza si intende la possibilit`<sub>a di dedurre S  sup(p) > x o viceversa. Poich`e S `e compatibile con</sub> D implica che ∃ un pattern p in D tale che supD(p) > x o viceversa.

Informalmente tutti i pattern non k-anonimo rappresentano la classe dei canali d’inferenza.

Definizione 3.3.3 (Canale di inferenza). Un canale di inferenza C `e un in-sieme di coppie hX, ni con X ∈ 2I _{e n ∈ N tale che:}

∃ p ∈ Pat(i) : C  0 < sup(p) < k.

Il problema di inferire il supporto di un pattern p pu`o essere scisso in due sotto problemi:

• Caso base

Dato un itemset X che ha un superset definito come X ∪ {a} con X, X ∪ {a} ∈ 2I_{, se 0 < sup}

D(X) - supD(X ∪ {a}) < k allora la

coppia hX, supD(X)i, hX ∪ {a}, supD(X ∪ {a})i rappresenta un canale

di inferenza che identifica il pattern non k-anonimo p = {X ∧ ¬a}.

• Caso induttivo

Dato un itemset I formato dagli item {i1,...,im} che ha un superset

definito come l’unione J = I ∪ {a1,...,an} se `e verificato che:

0 < f_IJ = X

I⊂X⊂J

(−1)|X\I|supD(X) < k

allora l’insieme degli itemset hX, supD(X)i tali che I ⊂ X ⊂ J costituisce

un canale d’inferenza che identifica il pattern non k-anonimo p = {i1 ∧

... ∧ im ∧ ¬a1 ∧ ... ∧ ¬an}.

Per indicarlo useremo la notazione CJ

I. La formula utilizzata prende il

nome di principio di inclusione-esclusione[...].

Esempio

Considerando il database D della tabella 3.1 e preso k = 3 abbiamo che Ccde e

`e un canale d’inferenza con supporto 1. C_ecde = f_ecde = supD(e) - supD(ce)

-supD(de) + supD(cde) = 11 - 9 - 10 + 9 = 1.

Facendo la verifica, nel database D di tabella 3.1 in effetti il pattern {e ∧ ¬c ∧ ¬ d} compare una sola volta.

Figura 3.2: Canale d’inferenza C_ecde per k=3

3.4

Detection di canali di inferenza

La fase Detection cerca di individuare tutti i pattern non k-anonimi, essa consiste in un’analisi inferenziale sull’insieme di tutti gli itemset FI ottenuti dopo una prima fase di mining e che si vogliono divulgare.

Questo nuovo problema pu`o essere visto come un nuovo caso di estrazione di pattern dove questa volta si ha una soglia per la frequenza σ e una soglia k per l’anonimit`a.

Il modello di Detection da un punto di vista logico pu`o essere suddiviso in due moduli: uno schema inferenziale definito secondo la definizione di canale di inferenza e di uno ”scanner” che appoggiondosi a tale schema ricerca tutti i canali d’inferenza. Pi`u appropiatamente lo chiameremo Detector.

Denoteremo [...] con Ch(k,F(D,σ)) l’insieme di tutti i canali d’inferenza C_IJ contenuti in F(D,σ).

Algoritmo 1

Output: Ch(k, F(D, σ)) 1: Ch(k, F(D, σ)) = 0;

2: for all (J, sup(J)) ∈ F(D, σ) do 3: for all I⊂J do

4: compute f_IJ; 5: if 0 <fJ

I< k then

6: insert (C_IJ, f_IJ) in Ch(k,F(D, σ));

L’algoritmo di Detection, seleziona tutti gli itemset J in F(D,σ) e per ognuno di essi calcola tutti i suoi possibili subset I⊂J. Per ogni coppia di itemset I,J l’algoritmo computa fJ

I per calcolarne il supporto e se quest’ultimo ha un

valore minore di k inserisce la coppia I,J nell’insieme dei canali d’inferenza. Utilizzando il Naive Inference Channel Detector, secondo [...], il numero di

controlli da effettuare pu`o risultare abbastanza grande e quindi l’algoritmo diventa dispendioso dal punto di vista di costo computazionale. Supponendo che l’insieme degli itemset sia composto da un unico itemset massimale di cardinalit`a n possiamo stimare il numero di possibili canali d’inferenza come:

#canali =

n

X

k=1

N umSubset(n, k) ∗ Comb(k)

Il numero dei sottoinsiemi possibili `e dato da:

N umSubset(n, k) = n! k!(n − k)!

che possono essere combinati a seconda dei valori che pu`o assumere un attributo:

Comb(k) = (2k− 1)

Ad esempio se consideriamo {a,b,c}, n = 3 e k = 1 (tutti i sottoinsiemi di cardinalit`a 1) abbiamo che l’insieme dei canali `e: C_{}a,b,c, Ca,b,c

a , C a,b,c

b , Cca,b,c,

C_a,ba,b,c, Ca,b,c a,c , C

a,b,c

b,c . Il numero totale di canali `e 3 + 9 + 17 = 19.

Con n = 5 abbiamo una stima di circa 210 canali e raddoppiando gli attributi, n = 10 tale stima si aggira vicino a una cifra di 50000 canali circa. Ovvi-amente questi valori si riferiscono al caso pessimo in cui dalla distribuzione dei dati risulta che tutti gli itemset contengono canali d’inferenza.

Per risolvere questo problema, `e stato studiato un approccio pi`u intelligente che limita il numero di controlli da effettuare per trovare i canali di inferenza.

3.4.1

Detector ottimizzato

Il Detector ottimizzato si appoggia ai concetti di itemset chiusi.

Un itemset X avente supporto x si dice chiuso se non esiste nell’insieme degli itemset σ-frequenti un itemset Y che `e superset di X che abbia supporto y = x. Piu formalmente:

Definizione 3.4.1 (Itemset chiuso). Dato un database D e una soglia di supporto minima σ l’insieme degli itemset chiusi Cl(D,σ) = {hX, supD(X)i}

∈ F(D,σ) | @ Y ⊃ X con {hY, supD(X)i} ∈ F(D,σ).

Il concetto di item chiuso [...] ci consente di rappresentare l’insieme di tutti i FI in maniera pi`u compatta eliminando le ridondanze senza nessuna perdita

Figura 3.3: Cl(D,σ) per database in tabella 3.1 con σ = 7(in grigio gli itemset di F(D,σ) che adesso non compaiono)

di informazione. Un gruppo di itemset chiusi identifica le stesse transazioni che identifica l’insieme dei FI.

Il guadagno che si ottiene utilizzando l’insieme degli itemset chiusi `e visibile sia dal punto di vista del numero di controlli da effettuare, che si riduce, sia dal punto di visto dei canali d’inferenza scoperti.

Infatti la ridondanza negli itemset si traduce in una ridondanza anche nei canali d’inferenza individuati. Ci`o comporta un ulteriore perdita di tempo ai fini della computazione.

Se per esempio utilizziamo l’Algoritmo1 e individuiamo i canali Cbd b e Cbbe

entrambi con supporto 1, guardando la tabella 3.1 possiamo verificare che essi riferiscono la stessa transazione, in questo caso la 12.

Nella nostra nuova rappresentazione come mostra la figura 3.3, non possiamo identificare questi due canali, in quanto l’Algoritmo1 non pu`o scandire i pattern {b ∧ d}, {b ∧ e} e {b}.

Riusciamo a scoprire per`o il canale Cabde

ab = fababde = supD(ab) - supD(abd)

-supD(ade) + supD(abde) = 8 - 7 - 7 + 7 = 1.

Analogamente il canale si riferisce alla stessa transazione e inferisce la stessa informazione.

Infatti sfruttando la propriet`a di anti-monotonicit`a, in maniera abbastanza semplice possiamo verificare che il pattern individuato {a ∧ b ∧ ¬ d ∧ ¬ e} contiene {b ∧ ¬ d } e {b ∧ ¬ e}.

Propriet`a 3.4.1 (Anti-monotonicit`a dei canali). Dati due canali di inferen-za C_IJ e C_HL se I ⊆ H e {J\I} ⊆ {L\H} allora C_IJ ≺ CL

Se CJ

I≺ CHL allora ∀ datatbase D fIJ(D) ≥ fHL(D).

Quindi se scopriamo un canale d’inferenza composto da una coppia di itemset H ⊆ L tale che 0 ≤ fL

H(D) ≤ k possiamo evitare di controllare il supporto

di tutti i canali CJ

I≺ CHL, poich`e essi in realt`a non rappresentano dei canali

d’inferenza.

In pratica `e come se avessimo una gerarchia, un canale pi`u generico contiene canali pi`u specifici. Se riusciamo a individuare i canali generici automati-camente scopriamo anche gli altri. Con l’ausilo dell’insieme degli itemset chiusi la cui rappresentazione si presta al problema poich`e compatta i pat-tern rendendoli pi`u generici, riusciamo a diminuire notevolmente il tempo di ricerca.

Per conludere, dobbiamo far presente che l’utilizzo di questa nuova rappre-sentazione consente implicitamente di eliminare le ridondanze dei canali di inferenza anche nella fase di Sanitization . Durante questa fase, verranno bloccati con opportune tecniche tutti i canali contenuti in F(D,σ).

3.5

Sanitization

La fase di Sanitizzazione rappresenta l’ultimo passo del nostro modello di protezione. Una soluzione al problema di divulgare l’insieme degli itemset σ-frequenti in maniera sicura, garantendo che non ci sia la possibilit`a di violare i vincoli di anonimit`a dei soggetti rappresentati, consiste nel blocco di tutti i canali d’inferenza trovati nella fase di Detection.

Per sanitizzare un insieme di itemeset σ-frequenti F(D,σ) dobbiamo rispettare alcuni vincoli [...]. Detto Ok _{l’insieme degli itemset frequenti che possono}

essere divulgati in maniera sicura abbiamo che:

1. Ch(k,Ok_{) = 0}

L’insieme risultante dal processo di sanitizzazione non pu`o contenere canali d’inferenza. Infatti durante questa fase, poich`e si modificano i supporti dei pattern, esiste la possibilit`a che vengano introdotti nuovi canali d’inferenza.

In realt`a questi canali sono inconsistenti in quanto non esistono nel database di partenza e di fatto non rappresentano una minaccia per l’anonimato dei soggetti rappresentati. Per precauzione da possibili at-tacchi di tipo I nverse Data Mining nel nostro output verranno eliminati anche questa ”sorta” di canali d’inferenza.

2. ∃ D’ | Ok = F(D’,σ)

compatibile con almeno un datatabase. Il valore dei supporti dei pat-tern deve essere sempre modificato in funzione del database e rispet-tando i principi di anti-monotonicit`a dei pattern, affinch`e un utente malintenzionato non distingua tra un output sanitizzato ed uno nor-male.

Immaginiamo che nell’output risultante dal processo di sanitizzazione siano presenti due itemset X,Y con X ⊂ Y. Se risultasse sup(X) ≤ sup(Y), invece che il contrario, un avversario potrebbe capire che l’in-sieme dei pattern rilasciati non `e realistico e quindi potrebbe cercare di condurre un attacco come quello citato nel punto 1.

Se per modifica dei supporti degli itemset contenuti in un canale di inferenza intendiamo l’eliminazione degli itemset stessi (che consiste nel portare il sup-porto a zero) in linea di principio non ottererremo mai un insieme compatibile con un database D’.

Questo approccio d’altra parte causerebbe una significativa perdita di in-formazione, infatti equivarrebbe all’eliminazione di un numero consistente di tuple nel database. Per ovvie ragioni questa non `e una soluzione ammissibile. Due alternative piu intelligenti che rispettano i vincoli che abbiamo dato sono:

• Sanitizzazione additiva

Dato l’insieme degli itemset σ frequenti F(D,σ) e dei canali Ch(k,F(D,σ)) per ogni canale C_IJ contenuto incrementiamo il supporto dell’itemset I di k volte in modo tale che risulti fJ

I(D) > k. Questa operazione dal

punto di vista del mantenimento della compatibilit`a con il database D equivale ad aggiungere k transazioni t = I.

In realt`a le transazioni vengono aggiunte ”virtualmente” in quanto sec-ondo la filosofia adottata non vogliamo modificare il database di parten-za. Per evitare di aggiungere troppa distorsione durante la fase di san-itizzazione, potremmo incrementare il supporto dell’itemset I di una valore pari a k - fJ

I invece che k.

Questa modifica, comporterebbe un guadagno in termini di qualit`a del-l’informazione contenuta nei pattern sanitizzati rispetto a quelli origi-nali.

Tuttavia non utilizzeremo questa soluzione e, il prezzo che paghiamo a discapito della distorsione introdotta, risulta abbastanza ragionevole. Infatti gli svantaggi che si avrebbero se si incrementasse il supporto di I con un valore pari a k - fJ

questo modo potrebbero essere creati nuovi canali d’inferenza, ipotesi che abbiamo gi`a scartato.

In secondo luogo un utente malintenzionato potrebbe computare fJ I per

tutti i pattern e accorgersi che il valore restituito in questo caso sarebbe esattamente k, quindi dedurre che `e stata effettuata una sanitizzazione. In realt`a, come gi`a detto, l’output divulgato non deve consentire questa distinzione.

• Sanitizzazione sottrattiva

L’idea base della sanitizzazione sottrattiva consiste nel nascondere un canale d’inferenza portando il suo supporto a zero f_IJ = 0. E’ possi-bile effettuare questa operazione solamente rimuovendo la transazione t coinvolta con il vincolo che: I ⊆ t e (J\I) ∩ t = 0.

Esempio

D

t a b c d e f g h t12 1 1 0 0 0 1 1 0

Tabella 3.2: Eliminazione di una transazione

Per il canale Cbd

b , con suppoirto 1, abbiamo che b ⊆ t12 e (bd\b) ∩

t12 = 0 e quindi possiamo eliminare t12. Ricordando che in realt`a non modifichiamo mai il database di partenza, l’eliminazione ”virtuale” di una transazione consiste nel diminuire il supporto di I di un valore pari a fJ

I.

Questo approccio tuttavia non `e sufficiente perch`e se decrementiamo il supporto di I, in realt`a, dobbiamo decrementare anche il supporto di tutti i sui subset. In questo modo potremmo violare la propriet`a di anti-monotonicit`a dei pattern e quindi perdere la compatibilit`a con il database.

Per risolvere questo problema, l’unica soluzione consiste nel sopprimere la transazione accedendo al database. Tale approccio tuttavia, non da garanzie sul fatto che si creeino nuovi canali d’inferenza.

Poich`e questa soluzione risulta essere meno robusta rispetto alla sani-tizzazione additiva, potrebbe essere necessario ripetere pi`u volte il pro-cedimento (iterazione esaustiva) per garantire che l’output rilasciato sia effettivamente esente da tutti i canali d’inferenza.

3.6

Conclusioni

In questo capitolo abbiamo sintetizzato lo studio di un modello di min-ing rispetto della privacy svolto su database binari, nel prossimo capitolo estenderemo tale studio a un database inter-attributo.

Capitolo 4

K-anonymity for inter-attribute

pattern

4.1

Introduzione

In questo capitolo estenderemo il modello di protezione per i database binari ai database relazionale o inter-attributo.

Dal punto di vista di modello, lo scenario cambia poich`e cambia la semantica degli attributi. Se prima avevamo che i possibili valori che poteva assumere un attributo erano [0,1], adesso abbiamo che la cardinalit`a degli attributi varia a seconda della classe di appartenenza di ogni attributo. Per sempli-ficare il modello non faremo distinzione tra i tipi di dati che mette a dispo-sizione il modello dei dati relazionale in uso ma, considereremo ogni attributo come una coppia Nome attributo, lista dei possibili valori.

Il nostro obbiettivo, sar`a cogliere tutte le differenze con il modello di pro-tezione per il database binario esaminato in precedenza.

Finch`e possibile, riutilizzeremo tutte le propriet`a e definizioni gi`a introdotte. Quando le differenze saranno completamente divergenti e quindi non com-patibili con il nuovo modello, introdurremo le opportune definizioni per modellare i problemi che di volta in volta si presentano.

Inoltre cercheremo di vericare se il nuovo modello consentir`a di fare ulteri-ori ipotesi dal punto di vista di possibili attacchi alla privacy. Se ci`o sar`a possibile, cercheremo di trovare nuove soluzioni al problema di come inferire nuovi pattern e quindi scovare nuovi tipi di canali d’inferenza.

4.2

Concetti base

Il modello inter-attributo fortunatamente oltre a permettere di riutilizzare tutte le propriet`a gi`a studiate, consente teoricamente anche di riusare gli stessi algoritmi.

In modo abbastanza elementare possiamo verificare che l’insieme degli item-set σ frequenti, per un database relazionale D, consiste, a parit`a di transazioni contenute in un database binario D’, in un insieme pi`u vasto.

Se nel modello binario venivano considerati solo gli item con valore positivo (che comparivano con il valore 1), adesso, si considerano sempre tutti gli item.

Un item non viene considerato quando compare con il valore nullo, ovvero non compare.

Intuitivamente possiamo gi`a affermare che la fase di Detection diventa pi`u complessa in quanto il modello inferenziale utilizzato dal Detector adesso deve tener conto della semantica degli attributi che risulta essere pi`u ricca di contenuti.

La complessit`a (da un punto di vista insiemistico) aumenta perch`e il numero di possibili combinazioni tra item `e maggiore rispetto a quelle che si potevono ottenere con item il cui dominio poteva assumere solo due valori.

Esempio database inter-attributo

D

a b e # a1 b1 e1 9 a1 b1 e2 2 a2 b1 e3 1

Tabella 4.1: database inter-attributo

Seguendo le linee guida del modello binario definiamo alcune propriet`a:

Definizione 4.2.1 (Dominio di Appartenenza). Dati A1...An attributi

chi-amiamo Dominio di Appartenenza dell’attributo An l’insieme dei possibili valori che esso pu`o assumere: DA(An) = {a1...am}.

Ovviamente ogni Dominio contiene valori dello stesso tipo (omogenei).

Il Dominio di Appartenenza ci consente di poter gestire la semantica di tutti gli attributi che, in questo modello gioca un ruolo molto importante.

Dall’esempio in tabella 4.1 abbiamo che: DA(A)= {a1,a2}, DA(B)= {b1,b2},

DA(E)= {e1,e2,e3}.

Diamo la definizione per un database inter-attributo:

Definizione 4.2.2 (Database Inter-attributo). Un database inter-attributo D = {I,T} `e formato da un insieme di variabili I = {A1,...,An} e i rispettivi

domini di appartenenza DA(A1),...,DA(An) chiamati anche item, e da un

insieme di transazioni T = {t1,...,tk}. Ogni transazione consiste in un vettore

di dimensione n contenente una combinazione dei valori delle variabili in I.

Ridefiniamo il concetto di pattern:

Definizione 4.2.3 (Pattern Inter-attributo). Considerando l’insieme delle variabili I, un pattern inter-attributo `e una proposizione logica costruita con connettivi AND(∧), OR(∨), NOT(¬) sui valori delle variabili in I.

Indicheremo tale insieme Pat(I).

Dalla definizione appena data segue che un possibile pattern `e {A=”a1” ∧

E=”e2”} per {A,E} ∈ I ed a1 ∈ DA(A) e e2 ∈ DA(E).

Differentemente dal modello binario esistono alcune combinazioni di attributi che formano pattern che non possono essere ritenuti conformi poich`e incon-sistenti(ovvero che non rispettano la semantica di come sono disposti gli attributi di ogni tupla del db). La propriet`a di consistenza ci permette di individuare solo i pattern che devono essere tenuti in considerazione.

Definizione 4.2.4 (Pattern Consistente). Diremo che un pattern inter-attributo `e corretto e quindi consistente se e sole non `e composto da sequenze di item appartenenti al medesimo DA legati in AND(∧). Indicheremo l’insieme dei pattern consistenti con P atC(I) ⊆ Pat(I) e l’insieme dei pattern non

consistenti con P atN C(I) = Pat(I)- P atC(I).

Esempio1 Con DA(A) = {a1,a2,a3} DA(B) = {b1,b2} abbiamo che :

Pattern consistenti: {¬A=a1 ∧ ¬A=a2 ∧ B=b1} ≡ {A=a3 ∧ B=b1} ,

{¬A=a1 ∧ B=b1} ≡ {A=a2 ∨ A=a3 ∧ B=b1}.

Pattern inconsistenti: {A=a1 ∧ A=a2} , {B=b1 ∧ B=b2 ∧ A=a3}.

Per semplicit`a da questo momento, senza che la notazioni crei imbarazzo, quando indicheremo un pattern useremo solo i sui valori.

Di pari passo vediamo se il concetto di supporto utilizzato in precedenza va ancora bene.

Per i database binari, avevamo definito il supporto di un pattern p come il numero di transazioni t tali che p(t) risultasse vera. In particolare la funzione p(t) ci diceva se gli item che comparivano in p erano tutti uguali a 1 (essendo il dominio degli attributi[0,1]) in t.

Adesso poich`e ogni pattern `e formato da un insieme di combinazioni di item che hanno sempre un valore ben definito, calcolare il supporto equivale a conteggiare il numero di transazioni che contengono un determinato pattern.

Definizione 4.2.5 (Supporto). Dato un database D, un pattern p e l’insieme delle transazioni T = {t1,...,tm} il supporto di p in D `e:

supD(p) = # ti t.c. p ∈ ti per i = 1...m

Dal database in tabella 4.1 per esempio abbiamo che il supporto del pattern p = {a1 ∧ b1} `e sup_D(p) = 11.

Il supporto, come nel modello binario, permette di escludere tutti quei pat-tern che non compaiono con un valore maggiore di σ. Per tanto definiamo l’insieme degli itemset frequenti FI.

Definizione 4.2.6 (Insieme degli Itemset). L’insieme di tutti gli itemset `e una classe di pattern consistenti ottenuti come combinazioni di item solo in AND(∧). Gli item appartenenti a un itemset sono una combinazione dei possibili valori dei domini di appartenenza DA(A1) o_{n...on DA(An), delle}

variabili I = {A1,...,An} tali che l’itemset risulti consistente. Denoteremo

questo insieme con la lettera V ⊆ P atC(I).

Definizione 4.2.7 (Itemset σ-Frequenti). Dato un database D e una soglia minima di supporto σ l’insieme degli itemset frequenti FI `e formato da tutti i pattern che sono definiti come:

F(D,σ) = {hX, supD(X)i | X ∈ V ∧ supD(X) ≥ σ }

4.2.1

Canali d’inferenza inter-attributo

Dopo aver introdotto tutte le definizioni necessarie per poter studiare un database relazionale, studiamo il problema di come verificare l’esistenza e il riconoscimento di possibili canali d’inferenza contenuti in un insieme di itemset σ frequenti.

Per studiare il problema possiamo sfruttare anche in questo caso i principi di k-anonymity gi`a discussi per i database binari.

Figura 4.1: F(D,σ) per database in tabella 1.1 con σ = 5

Infatti, anche adesso tale principio risulta essere valido per garantire l’anoni-mato dei soggetti rappresentati nell’insieme nei nostri dati che in questo caso sono l’insieme degli itemset frequenti F(D,σ) .

Riportiamo per comodit`a tale pricipio:

Definizione 4.2.8 (Pattern k-Anonimo). Dato un database inter-attributo e una soglia di anonimit`a k un pattern p ∈ P atC(I) `e anonimo con grado k

se supD(p) ≥ k o se supD(p) = 0.

Il concetto di k-anonymity come abbiamo visto, consente di valutare se un canale d’inferenza (individuato con il principio di inclusione esclusione) `e realmente pericoloso poich`e individua un pattern non k-anonimo.

Il problema dei canali d’inferenza per un database relazionale ´e legato al principio di supporto di inferenza definito nel capitolo precedente e che sim-ilmente rimane invariato. In modo elementare `e possibile constatare che cambia solo il dominio delle variabili.

Definizione 4.2.9 (Database compatibile). Un insieme S di coppie hX, ni con X ∈ V e n ∈ N e un database D si dicono compatibili se e solo se ∀ hX, ni ∈ S supD(X) = n.

Definizione 4.2.10 (Supporto di inferenza). Dato un insieme S di coppie hX, ni con X ∈ V e n ∈ N e un pattern p ∈ P atC(I). Supponiamo che esista

un database D compatibile con S. Per supporto di inferenza si intende la possibilit`<sub>a di dedurre S  sup(p) > x o viceversa. Poich`e S `e compatibile con</sub> D implica che ∃ un pattern p in D tale che supD(p) > x o viceversa.

Di seguito possiamo definire un canale d’inferenza inter-attributo, riutiliz-zando la definizione del modello binario, come:

Definizione 4.2.11 (Canale di inferenza inter-attributo). Un canale di in-fernza C `_{e un insieme di coppie hX, ni dove X ∈ V e n ∈ N tale che:}

∃p ∈ P atC(I) t.c. 0 < sup(p) < k .

In particolare, possiamo utilizzare il principio di inclusione-esclusione per i database binari e allo stesso modo possiamo concludere che:

Dati due pattern I,J t.c. I ⊆ J un canale di inferenza `e la coppia: hI, sup(I)i, hJ, sup(J)i. Tale coppia `e il pattern p.

Esempio 3 Dal database in tabella 4.1 e dalla figura 4.1 emerge che i pattern {a1∧ b1∧ e1} con supporto 9 e {a1∧ b1} con supporto pari a 11 rappresentano

un canale d’inferenza inter-attributo con supporto 2. Abbiamo che Ca1b1e1

a1b1 = f

a1b1e1

a1b1 = supD(a1b1) - supD(a1b1e1) = 11 - 9 = 2.

Il pattern non k-anonimo individuato `e p = {a1 ∧ b1 ∧ ¬e1} che ha supporto

uguale a 2. Oss:

Passando a questo modello la struttura dei canali di inferenza cambia se e solo se la cardinalit`a del DA di ogni attributo `e maggiore di due, altrimenti rimaniamo nel caso binario.

In realt`a dall’esempio 3 si ha che il canale d’inferenza individua un pattern che si distingue da quelli visti fin ora.

Introduciamo questa definizione:

Propriet`a 4.2.1 (Negazione di un item inter-attributo). Dato un item xi e

il suo DA(X) = {x1,...,xn} la sua negazione si ottiene come :

¬ xi ≡S(∨_j6=ix_j ∈ DA(X))

Secondo questo principio di equivalenza `e possibile trasformare {¬e1} con a

{e2 ∨ e3} e quindi riscrivere il pattern come {a1 ∧ b1 ∧ (e2 ∨ e3)}

Diversamente dal caso binario questo pattern individua i pattern: P1 = {a1

∧ b1 ∧ e2} e P2 = {a1 ∧ b1 ∧ e3}.

E’ possibile fare questa ipotesi e applicare queste trasformazioni perch`e conos-ciamo DA(E) = {e1,e2,e3}. In caso contrario non avremmo potuto dir niente

a riguardo perch`e guardando l’insieme degli itemset frequenti in figura 4.1 non si evince completamente l’insieme dei valori che pu`o assumere l’attributo ”E”.

Se banalmente guardassimo il database potremmo verificare che P1 ha

ipotesi poich`e il modello di protezione adottato suppone di non conoscere la distribuzione dei dati nel database.

Quindi possiamo dire che per P1 e P2 e pi`u in generale vale la seguente

propriet`a :

Propriet`a 4.2.2 (Di copertura). La somma dei supporti di P1 e P2 `e uguale

al supporto totale del canale d’inferenza che li rappresenta. Pi`u in generale:

Dato DA(A) = {a1...am}, DA(B) = {b1...bs}, DA(C) = {c1,c2...ck} e un canale

d’inferenza :

CJ

I con I = {a1,b1} e J = I ∪ {c1} e con a1,b1 fissi abbiamo :

sup(C

) =

P

i=1

sup

{a

∧ b

∧ c

} ∀ c

∈{DA(C)\

c

}

La propriet`a di copertura ci mostra in pratica un prima sostanziale differenza tra i due modelli. Banalmente nel database binario negare il valore di un attributo significa non prenderlo in considerazione.

Adesso, la possibilit`a di trasformare un attributo negato ci consente di in-dividuare un pattern appartenente a P atC(I) che individua una regione di

item a cavallo tra pi`u transazioni di un database inter-attributo.

Cercheremo di sfruttare le informazioni che ci fornisce la conoscenza di do-minio per capire se il modello inter-attributo presenta nuove tipologie di inferenze. Inoltre sfrutteremo il legame che esiste tra la rappresentazione dei canali di inferenza del database binario con quello inter-attributo per poter riutilizzare, con le opportune modifiche il modello di Detection gi`a studiato precedentemente.

4.3

Detection di canali d’inferenza

Nell’esempio introdotto nel paragrafo precedente abbiamo visto che un canale di inferenza pu`o individuare pi`u pattern. Tuttavia esso mantiene la stessa struttuta dei canali d’inferenza del modello binario. In effetti per ”scovarlo”, `e stato utilizzato lo schema di Detection adottato nel caso binario.

Ci`o fa riflettere sul fatto che buona parte del processo di Detection per i database binari pu`o essere riutilizzata e adattata alla Detection inter-attributo. Questo processo utilizza un modulo chiamato Detector che collab-ora con un modello inferenziale per individuare i possibili canali di inferenza presenti nel’insieme dei FI.

Concettualmente apportando le modifiche necessarie possiamo riutilizzarlo. In particolare bisogna ampliare, per i database inter-attributo, il modello inferenziale poich`e quest’ultimo risulta essere meno indipendente `e pi`u legato alla sematica degli attributi.

Figura 4.2: Modello Detection binaria

Il meccanismo base del modello inferenziale studiato per i database binari, `e il principio di inclusione-esclusione il quale calcola tutte le inferenze basandosi sul supporto dei pattern ottenuti combinando gli itemset in FI. Tali inferenze permettono di individuare tutti i pattern non k-anonimi.

Come si `e visto, applicando in modo piuttosto semplice tale principio al-l’insieme degli itemset di figura 4.1, abbiamo trovato una prima sostanziale differenza tra l’insieme dei pattern risultanti.

Considerando le combinazioni che si possono avere tra gli itemset di FI si pu`o osservare che risulta un’altra diversit`a: nel modello binario non esisteva il problema che combinando i possibili itemset venissero creati pattern non consistenti.

Questa ulteriore differenza e il fatto che la semantica degli attributi risulta pi`u estesa, fa capire che il principio di inclusione-esclsusione non `e pi`u sufficiente e non garantisce che tutti i canali d’inferenza siano scovati.

Infatti se applichiamo tale principio rispettando la propriet`a di consistenza dei pattern non riusciamo ad individuare le possibili inferenze che in realt`a esistono.

Come pi`u volte ribadito, un item pu`o assumere diversi valori e rispetto ai database binari `e possibile aggregare maggiore informazione. Concettual-mente possiamo utilizzare l’insieme dei pattern non consistenti, in cui pi`u

item appartenenti allo stesso DA sono legati in AND(∧), per individuare nuovi canali d’inferenza.

Per questo motivo, un primo passo che faremo per rifinire il modello inferen-ziale inter-attributo, sar`a di definire una nuova classe di canali di inferenza. Questa nuova classe sar`a prevalentemente legata al modello inter-attributo e sar`a capace di sfruttare l’inconsistenza dei pattern, utile se utilizzata insieme al principio di inclusione-sclusione per individuare ulteriori canali’dinferenza.

4.3.1

Modello inferenziale inter-attributo

La nuova classe di pattern permetter`a di gestire l’unione di due o pi`u pattern inter-attributo. Il pattern risultante sar`a un pattern in cui compariranno pi`u item appartenenti allo stesso DA legati in AND(∧).

Definizione 4.3.1 (Pattern Aggregati). Un pattern aggregato P `e il risultato dell’unione di due o pi`u pattern P1 = {X} ∪ a1, ..., Pn = {X} ∪ an-1 con X

∈ V e {a1,...,an-1} in DA(A) tale che P `e nella forma: P = {X} ∪ {a1 ∨ ...

∨ an-1}.

Indicheremo questo insieme di pattern con P atA(I). Se un pattern aggregato

compare con supporto minore di k allora esso a sua volta indivuda una canale d’inferenza.

Definizione 4.3.2 (Canali di inferenza inter-attributo(aggregato)). Un canale di infernza C `e formato da un pattern P ∈ P atA(I) e da un insieme di coppie

hX, ni dove X ∈ V e n ∈ N tale che: ∃p ∈ Pat(I) t.c. 0 < sup(p) < k . Quindi, dato un itemset X che ha come superset P = {X} ∪ {a1 ∨ ... ∨ an}

con X ∈ V e X ∪ {a1 ∨ ... ∨ an-1} ∈ P at_A(I), se 0 < sup_D(X) - sup_D(X ∪

{a1 ∨ ... ∨ an-1}) < k allora la coppia:

hX, supD(X)i, hX ∪ {a1∨ ... ∨ an−1}, supD(X ∪ {a1∨ ... ∨ an−1})i

rappresen-ta un canale di inferenza che identifica il pattern non k-anonimo: p = {X ∧ ¬a1 ∧ ... ∧ ¬an-1}.

Pertanto, almeno dal punto di vista concettuale, per scovare tutti i possibili canali d’inferenza la Detection inter-attributo risulta essere pi`u complessa. La nuova Detection applicher`a il principio di inclusione-esclusione sia agli item contenuti nell’insieme degli itemset σ frequenti che all’insieme dei pat-tern aggregati.

Definiamo un altro database multi-attributo leggermente pi`u ricco di con-tenuti per cercare di evidenziare la nuova classe di canali d’inferenza appena definita.

Esempio database inter-attributo D a b c d # a1 b c d3 1 a1 b c d1 19 a1 b c d2 27 a2 b c d1 25

Tabella 4.2: database inter-attributo

Avendo DA(A) = {a1,a2}, DA(D) = {d1,d2,d3}, DA(B) = {b}, DA(C) ={c}

e un supporto minimo σ = 18 abbiamo che l’insieme dei FI `e composto da tutti gli itemset in figura 4.3 .

Figura 4.3: F(D,σ) per database in tabella 4.2 con σ = 18

Seguendo il ragionamento degli esempi antecedenti, con k = 10 abbiamo che l’insieme dei canali d’inferenza trovati utilizzando solo il principio di inclusione-esclusione corrisponde all’insieme vuoto.

Quindi, commettendo un errore, affermiamo che F(D,σ) con σ = 18 `e un in-sieme di itemset anonimo. Nell’ottica del data mining questo inin-sieme poich`e

costituisce informazione preziosa, verr`a rilasciarlo in output ai fini di analisi.

Ipotizziamo che un utente malintenzionato, con le appropriate conoscenze e provvisto degli strumenti necessari, entri in possesso dell’insieme dei dati ap-pena pubblicati.

Con un poco di pazienza e abilit`a potrebbe sferrare un attacco e riuscire ad individuare pattern con basso supporto.

Sottolineamo potenzialmente perch`e se guardiamo dal punto di vista dell’at-taccante, egli dispone solamente dell’insieme degli itemset FI e non conosce la distribuzione dei dati nel database originario.

Non `e detto che il database realmente contenga questi pattern o che essi siano compatibili con il database.

L’attaccante, sfruttando l’informazione contenuta nei DA degli item e nei FI, potrebbe simulare un processo di Detection capace di aggregare i pat-tern. Successivamente potrebbe mettere in pratica gli stessi meccanismi che abbiamo gi`a utilizzato e cos`ı individuare nuovi canali di inferenza.

Di fatto utilizzando la nuova definizione di canale inter-attributo, possiamo affermare che potenzialmente esiste un canale d’inferenza cos`ı fatto:

Supposto X = {a1∧ b ∧ c} abbiamo:

hX, supD(X)i, hX ∪ {d1∨ d2})i ≡ = {a1 ∧ b ∧ c ∧ ¬d1 ∧ ¬d2}.

In questo caso abbiamo un canale d’inferenza che individua il pattern: P = {a1 ∧ b ∧ c ∧ d3} che ha supporto uguale a 1, ed effettivamente esso `e

presente nel database D di tabella 4.2.