Algoritmo 2 Aggregate Input: F(D, σ)
4.5 Verso un nuovo Modello Inferenziale
Lo scenario analizzato sopra, fa riflettere sull’esigenza di definire un modello pi`u completo, non esclusivamente inferenziale ma anche capace di espandere tutta la conoscenza contenuta nei dati di partenza.
Il sistema di Detection deve poter circoscrivere non solo la conoscenza inferita ”staticamente’, bens`ı deve avere la capacit`a di limitare attacchi simili a quelli visti in precedenza.
Quindi dal punto di vista di un possibile algoritmo, dobbiamo prevedere una fase in cui si esegue una ricerca esaustiva sull’insieme degli itemeset σ fre- quenti che espanga il suddetto insieme per poi individuare tutti quei pattern che hanno supporto minore della soglia di anonimit`a assegnata.
Algoritmo 2
Deductive Inference Channel Detector /* First phase: Knowledge Expansion */1: for all (I, sup(I)) ∈ F(D, σ) do 2: for all J ⊆ I
3: compute IE(I,J) and obtain a pattern P with common items in AND(∧) form and not common items in NOT(¬) form. 4: replace all items of P in NOT(¬) form with equivalence OR(∨)
form.
5: obtain the distributed form of OR(∨) on AND(∧) for all items in P.
6: insert (P, sup(P)) in P atEx(I);
/* Second phase: For all Expansion patterns in P atEx(I) find all patterns
in F(D, σ) that are contained*/
7: for all (P, sup(P)) ∈ P atEx(I) do
8 size = NumOfCongiuntivePatterns(P); 9: count = 0;
10: while ( count < size ) do 11: P’ = ExtractPattern(P); 12: if (P’, sup(P’)) ∈ F(D, σ) 13: if sup(P) > k
14: subtract sup(P’) from sup(P); 15: remove P’ from P;
16: decrement size; 17: else goto 19;
18: inc count;
19: insert (P, sup(P)) in P atN k(I)
/* Third phase: Check for normal disgiuntive form patterns in P atN k(I)
20: for all (P, sup(P)) ∈ P atN k(I) do
21: count = 0;
22: if P is normal disgiuntive form and P /∈ F(D, σ) /*P contains only a pattern with items in AND(∧)*/ 23: insert (P, sup(P)) ∈ F(D, σ);
24: inc count;
/* Fourth phase: Check for recursion possibility */
25: if count > 0;
26: P atN k0(I) = Deductive Inference Channel Detector(k);
27: for all (P, sup(P)) ∈ P atN k0(I) do
28: insert (P, sup(P)) in P atN k(I);
27: return P atN k(I);
Possiamo suddividere l’algoritmo in quattro fasi:
• Fase 1
Nella parte iniziale l’algoritmo espande tutta la conoscenza possibile applicando il principio di inclusione-esclusione alle coppie di itemset I,J contenuti in FI tali che J ⊆ I. L’espansione passo dopo passo, crea i nuovi pattern tali che gli item comuni a I e J vengono considerati in AND(∧) mentre quelli non in comune come sequenze in AND(∧) di item negati con il NOT(¬) davanti. Successivamente utilizzando il principio di negazione viene sostituita la negazione con l’equivalente OR(∨). In questo caso si interroga il dominio di appartenenza dell’item e si rimpiazza il suo valore con la sequenza di tutti i valori presenti nel dominio (escluso quello corrente) presi in OR(∨) Dopo aver ottenuto questa combinazione di item, la si trasforma ulteriormente appicando il principio di distribuzione dell OR(∨) sull’AND(∧). Una volta ottenu- ta un pattern in forma normale disgiuntiva lo si inserisce nell’insieme dei pattern espansi P atEx(I). Questo insieme ha le stesse propriet`a
dell’insieme dei pattern aggregati P atA(I) che avevamo definito per ag-
allo stesso DA. Nel nostro nuovo modello tale insieme sar`a rimpiazzato da P atEx(I).
• Fase 2
Nella seconda fase si effettua una scansione su tutti pattern contenuti in P atEx(I). Per ognuno di essi, si estraggono tutti i sub-pattern che sono
in forma normale congiuntiva e se `e noto il loro supporto (il pattern `e presente in FI) si decrementa il supporto del pattern che li contiene per poi rimuovere il pattern contenuto. Il pattern risultante `e un pattern che individua una regione di conoscenza a cavallo tra pi`u transazioni che non rispetta i principi di k-anonymity poich`e il supporto finale e minore di k. Tutti questi pattern vengono inseriti in un insieme contenitore P atN k(I).
• Fase 3
In questa fase si procede all’arricchimento dell’insieme dei FI. Effet- tuando una scansione su P atN k(I) si cercano tutti quei pattern che in
realt`a sono solo in forma normale congiuntiva (il pattern riferisce solo una transazione nel database) e quindi non contiene composizioni di pattern in OR(∨). Una volta individuati questi pattern, essi vengono aggiunti all’insieme dei FI. Per controllare se effettivamente sono stati individuati nuovi pattern si utilizza una variabile guardia che rappre- senta l’indice di guadagno del processo di arricchimento di FI. Tale guardia consiste in un contatore che se assume il valore uguale a zero implica che non `e stato possibile effettuare un nuovo arricchimento di FI.
• Fase 4
In questa fase ci cerca di iterare il processo di espansione. Finch`e il valore della gurdia assume un valore maggiore di zero il processo sar`a ripetuto in maniera ricorsiva. Cos`ı, se sar`a possibile, l’algoritmo di Detection ripeter`a nuovamentele tre fasi espandendo di volta in volta l’insieme dei FI e decerementando il supporto dei pattern contenuti in P atN k(I). Tutti i pattern il cui supporto `e minore della soglia di
anonimit`a k rappresenteranno l’output dell’algoritmo.
4.6
Conclusioni
In questo capitolo abbiamo analizzato il problema di come estendere un mod- ello di protezione per il data mining rispettoso della privacy a un database inter-attributo.
Si `e studiato con particolare dettaglio la fase di Detection dei canali d’in- ferenza attraverso un percorso che ha portato alla luce tutte le problematiche esitenti, correlate all’uso di un modello di database pi`u complesso rispetto al modello di database binario esaminato nel capitolo precedente.
Dopo avere introdotto un primo modello di Detection inferenziale, capace di individuare un insieme pi`u ampio di inferenze rispetto a quelle che venivano individuate con la Detection classica, sono stati proposti alcuni scenari da cui `e emerso che in realt`a il modello risultava ancora non essere completo. All luce di ci`o, `e stato compiuto un ulteriore sforzo per trovare una nuova estensione del modello stesso, facente uso di principi deduttivi, che fosse in grado risolvere i nuovi problemi.
Il risultato di questo sforzo `e l’algoritmo 2 il Deductive Inference Channel Detector. Questo nuovo algoritmo consente di individuare un insieme di pattern non k-anonimi scandendo l’insieme degli itemeset σ frequenti ottenuti da un database inter-attributo.
L’algoritmo 2 a differenza della prima versione che risulta essere un caso base, riesce a scovare inferenze pi`u complesse. Tali inferenze, potrebbero non co- prire la totalit`a delle inferenze ricavabili sferrando nuovi attacchi inferenziali al database di partenza utilizzando nuove conoscenze ricavate da ulteriori studi.
D’altra parte il problema di come proteggere la privacy dei dati contenuti in un datbase e che si vogliono sottoporre ai processi di data mining ai fini di analisi, risulta essere una tematica oggetto di studi tuttora in corso.
Infatti in generale, la questione di come proteggere un database da attacchi inferenziali `e una tematica alla quale ancora non `e stata trovata un soluzione completa.
Cercando di sfruttare la vasta conoscenza con cui si pu`o interagire quotidiana- mente un qualsiasi utente malintenzionato potrebbe inventare nuovi attacchi capaci di scardinare le difese di qualsiasi sistema di protezione.
Capitolo 5
Implementazione
5.1
Introduzione
In questo capitolo proporremo l’implementazione di un prototipo di un tool che fornisce le funzionalit`a di Detection per database inter-attributo.
Inizialmente sar`a descritta l’architettura logica del sistema, elencando i mo- duli che la compongono.
In seguito verr`a discusso l’approccio adottato per la rappresentazione delle opportune strutture dati necessarie all’implemtazione di un modello di Detec- tion attinente ai concetti utilizzati per modellare i problemi e per descrivere gli algoritmi introdotti nei precedenti capitoli.
Saranno cos`ı introdotte le strutture dati di Item e Pattern utili alla rap- presentazione della conoscenza contenuta in un database per poi passare agli algoritmi che implementano le funzionalit`a vere e proprie del sistema. Infine saranno mostrati i dettagli implementativi delle parti che compongono il modulo di Detection, frutto del lavoro di progettazione con il linuguaggio UML (Unified Modeling Language).