Studio e implementazione di un approccio distribuito e collaborativo per la rivelazione di anomalie nel traffico

Indice generale

Introduzione...7

Capitolo 1: Generalità sulla rivelazione delle anomalie 1.1 Introduzione ...10

1.2 ADS “Classification Based” ...14

1.3 ADS basati sul Nearest Neighbor ...17

1.4 ADS basati sul Clustering ...21

1.5 ADS basati su analisi statistica ...23

1.6 ADS basati sulla teoria dell’informazione ...26

1.7 ADS basati su analisi spettrale ...27

1.8 ADS in sistemi con traffico a pacchetto ...28

Capitolo 2: Introduzione alla rivelazione delle anomalie di rete tramite PCA 2.1 Tipologie di anomalia e loro conseguenze...33

2.2 Un particolare tipo di anomalia: l'anomalia di volume. 36 2.2.1 Un esempio pratico...38

2.3 Cos'è e come funziona il PCA ...41

2.3.1 Introduzione...41

2.3.3 Funzionamento...43

2.3.4 Costruzione del sottospazio con il PCA...45

2.3.5 Rivelazione...48

Capitolo 3: Un protocollo sicuro per il calcolo della matrice di covarianza 3.1 Introduzione...55

3.2 Calcolo della matrice di covarianza completa...59

3.2.1 Un protocollo sicuro per calcolare prodotti matriciali...62

3.2.2 Perdita di protezione...64

3.3 Altri problemi di equità...67

3.4 Altre minacce alla privacy...68

3.5 Generazione dei vettori Z...71

Capitolo 4: Implementazione del PCA tramite protocolli per il prodotto matriciale sicuro 4.1 Scenario di riferimento...72

4.2 Matrice dei dati...73

4.3 Centratura dei dati...75

4.5 Calcolo autovalori e autovettori...80

4.6 Determinazione sottospazio normale...80

4.7 Calcolo proiezioni ...82

4.8 Calcolo dello SPE ...86

Capitolo 5: Test di verifica del funzionamento del sistema e risultati 5.1 Tracce di traffico...88

5.2 Test sul sistema implementato...89

5.3 Risultati...91

5.4 Tempo di esecuzione...92

Conclusioni...93

Ringraziamenti...94

Introduzione

La diffusione capillare della rete internet, negli ultimi anni, oltre a permettere la diffusione di notizie, dati, comunicazioni, conoscenze in tempo reale, ha creato una serie di problematiche legate alla struttura stessa della rete. Infatti, il successo di internet è dovuto anche ad applicazioni il cui traffico attraversa più reti appartenenti a diversi ISP. Pattern di traffico anomali possono nascere da reti diverse, e la congestione da essi provocata può risultare particolarmente dannosa per gli utenti finali. Bisogna allora trovare il modo di rivelare queste anomalie in maniera cooperativa tra i vari operatori di rete, per trovare risposte appropriate ai problemi che ne derivano. Le anomalie sono cambiamenti inusuali e significativi nei livelli di traffico di una rete, che possono spesso interessare un numero elevato di link. Rivelare le anomalie è importante sia per l'operatore che per l'utente finale. E' un problema difficile perché bisogna estrarre ed interpretare pattern anomali da grandi quantità di dati. In questa tesi proponiamo un metodo

generale per rivelare le anomalie basato sull'analisi delle componenti principali (detto PCA, principal component analysis), combinato con un meccanismo di preservazione della privacy che consente agli ISP di rivelare anomalie cooperativamente senza scambiare tra loro informazioni di traffico private. Abbiamo usato un protocollo per il prodotto matriciale multiparte sicuro per calcolare le componenti principali e i corrispondenti autovettori, necessari alla rivelazione dell'anomalia tramite PCA, e lo abbiamo applicato in un'architettura semi-centralizzata per la rivelazione dell'anomalia. Alla fine del calcolo, nessuno dei partecipanti può ottenere informazioni private degli altri e allo stesso tempo è in grado di ricavare i risultati corretti derivanti dall'applicazione di tale metodo. Faremo dunque una panoramica dei vari metodi esistenti (chiamati ADS, anomaly detection systems) per la rivelazione delle anomalie nel primo capitolo, ci concentreremo sul funzionamento del PCA nel secondo capitolo, parleremo approfonditamente del meccanismo privacy-preserving

usato per la matrice di covarianza nel terzo capitolo, spiegheremo come tale metodo possa essere implementato in maniera distribuita nel quarto capitolo, e infine faremo un confronto tra l'utilizzo del nostro sistema e uno in cui i meccanismi di privacy non siano stati implementati, dimostrando che i risultati ottenuti sono equivalenti in entrambi i casi nel capitolo conclusivo.

Capitolo 1

Generalità sulla rivelazione delle anomalie

1.1 Introduzione

L’Anomaly Detection, ovvero la distinzione tra eventi o comportamenti normali o anomali di un sistema, è un argomento che riguarda numerosi ambiti scientifici e non solo. Si tratta di un aspetto importante in medicina, in economia, in automazione e non da ultimo nell’informatica. E’ un tema che ha applicazioni eterogenee, dalla diagnosi di malattie, al controllo dell’andamento dei mercati finanziari fino ad aspetti di sicurezza in sistemi automatici ed informatici.

In ambito informatico, un sistema può sperimentare eventi o comportamenti anomali di varia natura. In una rete di calcolatori, le anomalie sono riconducibili sostanzialmente ad azioni dolose, ovvero attacchi, o a non meno pericolosi eventi involontari come guasti di apparati o collegamenti.

Lo scopo degli Anomaly Detection System (ADS) è appunto la distinzione tra comportamenti normali ed anomali del sistema che esso monitora. Per fare ciò è possibile seguire due diverse strategie d’implementazione; in un caso si definisce e si caratterizza il comportamento normale del sistema, rilevando come anomalo qualunque comportamento che si presenta in modo diverso dalla caratterizzazione effettuata; nell’altro caso si procede in modo opposto, ovvero si caratterizza l’anomalia, o le anomalie, ritenendo normale qualunque altro comportamento non riconducibile ad essa. Questi due possibili approcci sono conosciuti in letteratura rispettivamente con i nomi “anomaly-based” o “behaviour-based” e con “signature-based” o “misuse-based” [9].

Nell’individuazione di una specifica anomalia, o di un insieme ristretto di queste, con un ADS implementato secondo un metodo “signature-based” è certamente possibile raggiungere prestazioni migliori rispetto ad uno di tipo “anomaly-based”. Tuttavia con tale metodo non è possibile

rilevare anomalie diverse da quelle per cui l’ADS è preposto, né eventi o comportamenti nuovi, ossia non è possibile il “novelty detection”, mentre con un modello “anomaly-based” questo è realizzabile.

La scelta del tipo di approccio dipende in gran parte dallo scopo che si vuole raggiungere con l’applicazione dell’ADS, nonché dalle informazioni disponibili riguardo il funzionamento normale e anomalo di quest’ultimo.

Durante il funzionamento, l’ADS decide se il comportamento del sistema che sta osservando è riconducibile ad una situazione normale o anomala, sulla base di come è stato addestrato o di parametri impostati. E’ possibile incorrere in due diversi errori:

 Falsi positivi: con questo termine viene indicato l’errore in cui il sistema di monitoraggio segnala un evento o comportamento come anomalo quando in realtà esso è normale, ovvero quando viene segnalata la presenza di un’anomalia dove questa non risulta essere.

 Falsi negativi: con il termine falso negativo si indica l’errore opposto, ovvero la classificazione di un comportamento come normale quando in realtà è anomalo, ovvero la mancata segnalazione di un’anomalia quando questa è presente.

Il secondo tipo di errore è certamente il più critico per un ADS, infatti verrebbe meno al suo scopo. E’ solitamente preferibile evitare di incorrere in questo tipo di errore, anche al prezzo di qualche falso allarme, ovvero falso positivo, in più. Tuttavia anche i falsi positivi sono dannosi per l’ADS, in quanto se frequentemente ricorrenti portano ad ignorarne l’output, rendendo inutile la sua applicazione al sistema. Da un’analisi dei lavori presenti in letteratura riguardanti l’Anomaly Detection, si possono identificare diverse metodologie implementative, ovvero diversi modi per distinguere il corretto funzionamento del sistema da un’anomalia [10]. Si possono individuare:

ADS basati sul Nearest Neighbor. ADS basati sul Clustering.

ADS basati su analisi statistica.

ADS basati sulla teoria dell’informazione. ADS basati su analisi spettrale.

1.2 ADS “Classification Based”

Gli ADS basati sulla classificazione prevedono l’apprendimento di un modello da un set di dati “etichettati”, per poi classificare i dati di test a seconda del modello stesso. Sono quindi previste due fasi di funzionamento dell’ADS: la fase di training e quella di test.

A seconda della tipologia di dati a disposizione per la fase di training si possono utilizzare due differenti tipi di classificatori:

“Multi-class” se i dati a disposizione appartengono a più classi “normali”, in questo caso viene segnalata un’anomalia

se un campione di test non appartiene ad alcuna di queste.  “One-Class” se i dati di training di corretto funzionamento appartengono tutti ad una classe. In questo caso un campione di test che non appartiene alla classe precedentemente individuata viene considerato anomalo. Nella figura 1 sottostante è riportato un esempio grafico delle due tipologie di classificatori.

Figura 1 - Esempi di classificatori multi-classe e one-class

Le principali tecniche per implementare un ADS basato sulla classificazione sono:

classificazione multi-classe, o il “Replicator Neural Network” per la one-class [13]. Quest’ultimo possiede lo stesso numero di neuroni in input ed output ed è addestrato a scomporre i dati in ingresso e ricomporli in uscita; in fase di test la differenza tra i dati ricostruiti e quelli in input fornisce un tasso d’anomalia del campione analizzato.  Reti Bayesiane, usate esclusivamente per il caso multi classe.

 Support Vector Machines (SVM), utilizzate come one-class SVM. In fase di addestramento viene costruita una regione complessa che racchiude gran parte dei dati di training, separandoli dalla restante percentuale. La percentuale di elementi da non includere nella regione è un parametro di training. In fase di test un campione è definito anomalo se si trova all’esterno di questa regione.

 Tecniche basate su applicazione di regole, definiscono delle regole che descrivono il normale funzionamento del sistema monitorato, ovvero del training set. Se un campione

di test non soddisfa alcuna regola è considerato anomalo. Gli alberi di decisione sono un esempio di questo tipo di tecniche.

Esistono ADS che combinano queste tecniche [13], ad esempio utilizzando una SVM per individuare un fault, ed un blocco Rule-Based Reasoning (RBR) per classificarlo. La complessità computazionale di questi ADS dipende dalla specifica tecnica che essi implementano. Nonostante le Support Vector Machine siano lente in fase di training, la fase di test è sempre molto rapida.

I principali vantaggi di questo tipo di ADS sono la velocità di decisione in fase di test e la potenza degli algoritmi di separazione dei dati che implementano. Gli svantaggi sono la necessità di un buon numero di campioni per classe, nel caso di classificatori multi-classe, e il fatto che la decisione è di tipo “hard”, ovvero quasi nessuna tecnica di questo tipo è in grado di fornire uno “score” d’anomalia del campione di test.

1.3 ADS basati sul Nearest Neighbor

Gli ADS basati su questa tecnica seguono il principio per cui un dato di corretto funzionamento del sistema è situato in una regione con denso “vicinato”, mentre un dato relativo ad un’anomalia si trova lontano anche dai più vicini ad esso. Questa tecnica richiede la definizione di una funzione di “distanza” o di dissimilarità tra due campioni dati; solitamente è utilizzata la distanza Euclidea per grandezze continue.

Le tecniche di Nearest Neighbor implementate per l’Anomaly Detection sono riconducibili a due tipi:

 Tecniche che considerano la distanza tra il campione in esame ed il suo k-esimo vicinato al fine di calcolarne il tasso d’anomalia.

 Tecniche che considerano la densità del vicinato del campione in esame per calcolarne il tasso d’anomalia. Nel primo caso lo score d’anomalia di un campione è calcolato sulla base della funzione distanza rispetto ai k

campioni più vicini a quello considerato. In realtà esistono diverse soluzioni simili per il calcolo del tasso d’anomalia, come ad esempio il numero di campioni la cui funzione distanza rispetto al campione in esame è inferiore ad un valore determinato. Inoltre esistono diverse tecniche per aumentare l’efficienza del metodo base appena descritto, ad esempio tecniche di “pruning”.

Nel secondo caso viene calcolata la densità del vicinato del campione in esame, definendolo anomalo nel caso in cui questa sia bassa, mentre viene dichiarato normale se il suo vicinato, ovvero la zona circostante la sua posizione, è ad alta densità. Questa tecnica risulta poco performante nel caso in cui le regioni di corretto funzionamento abbiano densità differenti (vedi figura 2 sottostante); in questo caso anomalie che rispetto ad una zona densa sono distanti tanto quanto sono distanti i campioni di un’altra zona di corretto funzionamento a minor densità, non saranno rilevate.

Figura 2 - Esempio di dataset con zone di corretto funzionamento a diversa densità

Per ovviare a questo problema sono state sviluppate diverse tecniche di “densità relativa”, ovvero tecniche che considerano la densità del vicinato di un campione relativamente alla posizione del campione stesso.

La complessità computazionale di questo tipo di tecniche è solitamente più elevata delle altre.

I vantaggi di questa tipologia di ADS sono la possibilità di funzionamento sia in modo non supervisionato che semi-supervisionato e la non specificità dell’implementazione

rispetto alle grandezze da monitorare.

Per contro ha la possibilità di incappare in un alto numero di falsi negativi nel caso in cui gli eventi anomali siano simili, creando così una zona anomala ad alta densità, non rilevabile da questo tipo di tecnica. Inoltre soffre la complessità computazionale anche in fase di test, rendendone difficile l’utilizzo in applicazioni real-time. Per ultimo la definizione di una soglia oltre la quale una distanza è da considerarsi anomala spesso non è cosa banale. 1.4 ADS basati sul Clustering

Questa tipologia di ADS si basa su algoritmi di clustering. Questi sono nati per definire all’interno di un dataset dei gruppi di dati “simili” tra loro e solo in un secondo momento sono stati applicati all’Anomaly Detection. Si possono distinguere tre differenti approcci per questo tipo di tecnica.

corretto funzionamento quelli appartenenti ad un cluster, mentre campioni anomali quelli che non appartengono ad alcun cluster. Questo approccio è percorribile solo con l’utilizzo di algoritmi di clustering che non associano forzatamente tutti i campioni a dei cluster.

Nel secondo approccio vengono considerati corretti i campioni più vicini al centro del cluster cui appartengono, mentre sono anomali quelli più vicini al bordo di esso. In questo caso la distanza dal centro del cluster di appartenenza definisce un tasso d’anomalia del campione. Diversi algoritmi permettono l’utilizzo di questo metodo, come l’uso delle Self-Organizing Maps o del K-means.

Infine un possibile approccio prevede la classificazione di un campione come corretto se appartiene al cluster di dimensione e densità maggiore, come anomalo se appartenente ad uno degli altri cluster “minori”.

La differenza tra il Clustering e il Nearest Neighbor è che nel primo il campione in esame è valutato rispetto all’intero

cluster di appartenenza, nel secondo rispetto al solo vicinato. Come per le tecniche di classificazione, anche in questo caso la fase di costruzione dei cluster è ad elevata complessità computazionale, mentre la fase di test è rapida in quanto la decisione sul campione in esame è presa rispetto ad un modello già costruito.

Il vantaggio di questa tipologia di ADS, oltre alla già menzionata rapidità di test, è la possibilità di inserire nel modello un cluster aggiuntivo a posteriori. I principali svantaggi, oltre alla elevata complessità computazionale per la costruzione del modello, sono imputabili alle limitazioni dovute agli algoritmi, come la forzatura nell’associazione di ogni campione ad un cluster.

1.5 ADS basati su analisi statistica

Gli ADS che rientrano in questa categoria si basano sul principio per cui un’anomalia è costituita da un’osservazione che non può essere ricondotta al modello

stocastico costruito per descrivere il sistema da monitorare. In questo modo il campione in esame viene classificato corretto se si trova in una regione ad alta probabilità di occorrenza per il modello stocastico, anomalo se in una regione a bassa probabilità.

Anche in questo caso l’ADS necessita di una fase preliminare in cui viene costruito il modello stocastico del sistema, ovvero viene calcolato un modello statistico che descrive al meglio i dati a disposizione riguardo il corretto funzionamento del sistema. In seguito, in fase di test, viene deciso se il campione in esame appartiene o meno al modello precedentemente costruito.

ADS di questo tipo possono basarsi su due differenti tecniche di analisi statistica:

Tecniche parametriche. Tecniche non parametriche.

Tecniche parametriche assumono che i dati di corretto funzionamento del sistema sono generati da distribuzioni

parametriche, perciò in una prima fase ne determinano i parametri, per poi ottenere un tasso d’anomalia di un campione test attraverso l’inverso della funzione densità di probabilità della distribuzione ottenuta. Un particolare tipo di tecnica parametrica prevede la costruzione di un modello autoregressivo del sistema, calcolando il tasso d’errore come il discostamento del dato osservato da quello atteso, calcolato secondo tale modello.

Tecniche non parametriche non prevedono la costruzione di un modello a priori, ma ne determinano alcune caratteristiche statistiche durante il funzionamento, ovvero stabiliscono se un campione in esame è coerente o meno con la distribuzione dei campioni osservati in precedenza, decidendo così se esso è rispettivamente normale o anomalo. Tipici esempi di tecniche di questo tipo prevedono l’applicazione di funzioni kernel come il “parzen windows estimation”, oppure la costruzione di istogrammi per tenere traccia della frequenza delle occorrenze del processo in esame.

I vantaggi di questa tipologia di ADS sono dovuti alla possibilità di operare in modo non supervisionato, se dotati di una fase di definizione del modello robusta, e alla disponibilità di un intervallo di confidenza associato al tasso d’anomalia di ogni campione esaminato.

Tali tecniche si trovano in difficoltà nei casi in cui i dati ricavati dall’osservazione del sistema non seguono una semplice distribuzione statistica, rendendone complessa la modellizzazione. Inoltre la maggior parte di queste tecniche esamina individualmente ogni parametro che costituisce il campione in esame, senza tenere conto di una visione d’insieme.

1.6 ADS basati sulla teoria dell’informazione Questi ADS si basano sul calcolo di grandezze quali l’entropia, l’entropia relativa o la “Kolmogorov Complexity”. Il principio alla base di questi ADS è l’assunzione che un'anomalia introduce una irregolarità nell’informazione contenuta nei dati.

I principali vantaggi di questo tipo di tecniche sono la possibilità di lavorare in modalità non supervisionata ed il fatto che non sono necessarie assunzioni a priori sui dati da monitorare, invece necessarie per le tecniche di analisi statistica. Il principale svantaggio di questa tecnica è la possibile difficoltà di costruzione di strutture dati sulle quali calcolare le grandezze da monitorare.

1.7 ADS basati su analisi spettrale

ADS basati su tecniche di analisi spettrale, cercano una rappresentazione alternativa dei dati attraverso una combinazione dei loro attributi, al fine di mettere in evidenza la variabilità di questi. Il principio è quindi quello di riportare i dati in uno spazio differente in cui campioni normali e campioni anomali risultano maggiormente separabili.

La maggior parte degli ADS di questo tipo si basano sulla Principal Component Analysis (PCA), ma anche tecniche

come Compact Matrix Decomposition (CMD) e la Singular Value Decomposition (SVD) sono frequentemente utilizzate. I vantaggi di queste tecniche sono costituiti principalmente dalla riduzione delle dimensioni dello spazio delle features, rendendole particolarmente indicate per dataset con un elevato numero di dimensioni, e possono essere applicate unitamente ad altre tecniche come quelle viste in precedenza. Trovare uno spazio di dimensione inferiore in cui i dati risultano separabili non è sempre possibile, e spesso comporta complessità computazionali elevate, ma nonostante questo abbiamo usato questo tipo di ADS, in particolare basandoci sul PCA, per il proseguio di questa tesi.

1.8 ADS in sistemi con traffico a pacchetto Nel campo specifico dell’individuazione di eventi anomali in sistemi informatici con traffico a pacchetto, è possibile introdurre ulteriori distinzioni tra le diverse tecniche di ADS presenti in letteratura.

In primo luogo gli ADS sono classificabili in base alla tipologia di analisi del sistema adottata [19]:

Analisi del flusso dei dati. Analisi protocollare.

Analisi a livello applicativo.

Nel primo caso vengono estratte dal traffico informazioni relative al flusso dei dati quali il numero di bytes, di pacchetti o di connessioni osservate in un determinato intervallo temporale. Nel secondo caso, invece, vengono analizzati parametri specifici del protocollo utilizzato. L’analisi a livello applicativo prevede la conoscenza a priori della natura delle informazioni contenute nel traffico in analisi.

Inoltre si possono distinguere in base al metodo di costruzione del modello del sistema da monitorare, a seconda che sia ottenuto dall’analisi diretta del sistema stesso o per mezzo di specifiche fornite esternamente all’ADS. Nel primo caso si parla di “learnt model”, e può

essere ottenuto mediante una fase d’addestramento, supervisionato o non, precedente all’utilizzo dell’ADS; nel secondo caso il modello ottenuto è detto “specification-based” ed è costruito sulla base di informazioni fornite esternamente da personale esperto del sistema da monitorare.

Un’ulteriore distinzione è relativa alla scala di analisi, sia temporale che di dettaglio dei dati. Un ADS può infatti operare in “microscala” se campiona con frequenza i parametri che monitora, oppure se questi ultimi sono relativi ad informazioni di basso livello. Un ADS che analizza parametri relativi a lunghi intervalli di osservazione, nell’ordine delle ore, o che analizza informazioni di alto livello, opera in “macroscala”.

Esistono numerosi ADS che monitorano le informazioni contenute nelle Management Information Base (MIB) degli apparati appartenenti al sistema in oggetto [20][21]. In questo caso il traffico è monitorato indirettamente, ovvero

non vengono estratte informazioni dal traffico di rete ma queste sono derivate dalle statistiche prodotte dai dispositivi durante l’esercizio. Questo tipo di approccio offre buoni risultati nell’individuazione di errori server e di guasti hardware degli apparati.

Nel caso particolare di traffico voce, oltre alle informazioni presenti nelle MIB degli apparati vengono spesso considerati i “cartellini” delle telefonate, ovvero i Call Detail Records (CDR) e gli Internet Protocol Detail Records (IPDR) in caso di traffico VoIP [22]. Per ogni telefonata viene generato un cartellino contenente informazioni quali la durata della conversazione e la tipologia di apparecchi telefonici in uso.

I parametri estratti dagli ADS che monitorano il traffico in modo diretto appartengono solitamente a due tipologie: Parametri volumetrici.

Parametri entropici.

circa la distribuzione del traffico in rete, calcolando parametri come l’entropia di Shannon o di Tsallis degli indirizzi IP e delle porte sorgente e destinazione dei pacchetti. Lavori recenti evidenziano le ottime prestazioni ottenibili sulla base di questo tipo di metriche [23], soprattutto nell’individuazione di attacchi Denial of Service (DoS) e Port Scan. Questa tipologia di metrica è particolarmente indicata per il monitoraggio di reti di larga scala.

In ambito volumetrico sono numerosi i parametri estraibili dal traffico in rete. E’ possibile implementare un semplice conteggio di byte osservati in un intervallo temporale, soluzione indipendente dalla tipologia di informazioni scambiante nel sistema, oppure estrarre parametri di più alto livello, tenendo conto del protocollo in uso o del contenuto informativo dei pacchetti. ADS destinati ad un uso in generiche reti basate su protocollo TCP/IP analizzano solitamente informazioni di più basso livello, distinguendo eventualmente il volume di traffico per flussi [24].

Capitolo 2

Introduzione alla rivelazione delle

anomalie di rete tramite PCA

2.1 Tipologie di anomalia e loro conseguenze[1]

Comprendere la natura delle anomalie del traffico in una rete è un problema importante. Indipendentemente dal fatto che le anomalie in questione siano volute o involontarie, è importante analizzarle per due motivi:

• Le anomalie possono creare congestione nella rete e stressare l'utilizzazione delle risorse in un router, il che rende cruciale rivelarle da un punto di vista funzionale.

• Alcune anomalie potrebbero non necessariamente avere un impatto sulla rete, ma possono avere un impatto drammatico su un utente finale.

Un problema significativo quando si diagnosticano anomalie è che le loro forme e cause possono variare considerevolmente: dagli attacchi Denial of Service (DoS), alla misconfigurazione dei router, ai risultati di modifiche delle policy BGP. Nonostante una grande letteratura sulla caratterizzazione del traffico, le anomalie di traffico rimangono scarsamente comprese. C'è un gran numero di ragioni per cui ciò accade. Primo, identificare le anomalie richiede una infrastruttura di monitoraggio sofisticata. Sfortunatamente, molti ISP raccolgono solo misure di traffico semplici, come i volumi di traffico medi (tramite SNMP). Gli ISP più avanzati raccolgono i conteggi dei flussi sui link ai bordi, ma processare i dati raccolti è un compito oneroso. Una seconda ragione per la scarsa comprensione delle anomalie di traffico è che gli ISP non hanno mezzi per processare le misure che siano così veloci da rivelare le anomalie in tempo reale. Allora, gli ISP vengono a sapere degli eventi più gravi (virus e attacchi DoS) dopo il fatto, ma non sono in genere in grado di

rivelarli mentre stanno avvenendo. Un'ultima ragione è che la natura del traffico a livello di rete è ad alta dimensionalità e rumorosa, il che rende difficile estrarre informazioni significative sulle anomalie da qualsiasi tipo di statitica sul traffico. Qui ci occupiamo del problema di rivelare le anomalie di traffico che possono interessare più link in una rete multi-dominio, usando statistiche basate sui link. Il nostro approccio utilizza un metodo generale fatto in maniera collaborativa tra i vari domini per rivelare anomalie nel traffico di rete, lasciando a ciascun ISP il compito di identificarle e quantificarle. Crediamo che questo approccio a tre passi (rivelazione, identificazione e quantificazione) sia appropriato per trovare la grande varietà di anomalie del traffico di rete. Ciò accade perché il passaggio della rivelazione può utilizzare caratteristiche differenti di traffico come il volume, il numero di flussi, o eventi di routing, mentre l'identificazione e la quantificazione sono specifici per ciascun tipo di anomalia. L'obiettivo di questa tesi non è di spiegare la causa delle anomalie di rete, ma piuttosto di

fornire una tecnica generale per rivelare le anomalie di traffico. Infatti, un primo passo necessario per scoprire le cause delle anomalie è la loro corretta rivelazione, identificazione e quantificazione. Questa tesi si propone allora di fornire un approccio generale per rivelare le anomalie nel traffico di una rete multi-dominio, usando i dati di tutti gli ISP partecipanti senza che questi debbano preoccuparsi della loro privacy. Il nostro approccio si basa su una separazione dello spazio delle misure di traffico nei sottospazi normali e anomali, tramite l'analisi delle componenti principali (PCA).

2.2 Un particolare tipo di anomalia: l'anomalia di volume[1]

Una tipica rete backbone è composta di nodi (chiamati anche punti di presenza o PoP, Point of Presence) connessi da link. Definiamo un flusso origine-destinazione (OD) come il traffico che entra nella backbone al PoP di origine e ne esce al PoP di destinazione. Il percorso seguito da ogni

flusso OD è determinato dalle tabelle di routing. Di conseguenza, il traffico osservato su ogni link della backbone viene fuori dalla sovrapposizione di questi flussi OD. Useremo il termine anomalia di volume per riferirci ad un improvviso (rispetto all'intervallo di tempo usato) cambiamento nel traffico di un flusso OD. Poichè tale anomalia si origina fuori dalla rete, si propagherà dal PoP di origine a quello di destinazione. Si potrebbero rivelare anomalie di volume raccogliendo dati del traffico IP a livello di flusso su tutti i link in ingresso a tutti i PoP, e applicando metodi di decomposizione temporale ad ogni flusso OD. In generale ciò non è pratico, per molte ragioni. Primo, potrebbero esserci centinaia di link utente in una rete. Monitorare tutti i link in ingresso per raccogliere e aggregare dati a livello di flusso è oneroso dal punto di vista delle risorse; per molti ISP sarebbe un costo proibitivo. Secondo, ogni flusso OD dovrebbe essere processato separatamente, richiedendo la stima dei parametri associati per ognuna delle (potenzialmente centinaia di)

decomposizioni temporali. Invece, sviluppiamo una tecnica semplice e più pratica per diagnosticare anomalie di volume. Dato che un'anomalia di volume si propaga lungo la rete, sfruttiamo il fatto che dovremmo essere in grado di osservarla su tutti i link che attraversa. Allora identifichiamo le anomalie basate sui flussi OD osservando solo i contatori dei link. (Se sono necessarie informazioni più dettagliate sulla sorgente e destinazione IP di un'anomalia, il nostro metodo può essere usato come innesco per indicare su quali router si deve fare raccolta dati a livello di flusso IP iniziata su base temporale).

2.2.1 Un esempio pratico

In questa sezione, illustriamo le anomalie di volume sulle serie temporali sui link prese da una rete backbone. La difficoltà del problema della diagnosi dell'anomalia di volume dipende in parte dal fatto che usa solo dati dei link. Da questi dati, bisogna formulare ipotesi su eventi inusuali occorrenti nei flussi OD sottostanti. Illustriamo questa

difficoltà in figura 3.

Figura 3 – Esempio

Il plot in alto su ogni lato della figura mostra la serie temporale di un flusso OD con una anomalia di volume associata – questa informazione non è disponibile ai nostri algoritmi, ma la presentiamo per mostrare la natura delle anomalie di cui ci occupiamo. Il punto nel quale ogni anomalia occorre è segnato con un cerchio rosso sull'asse dei tempi. Sotto quest'asse ci sono plot del traffico dei quattro link che trasportano i flussi OD dati. Questi quattro plot rappresentano i dati disponibili per il nostro algoritmo. Il nostro scopo è quello di rivelare correttamente che, al

tempo mostrato, la rete sta subendo un'anomalia. Facciamo tre osservazioni da questi esempi. Primo, mentre i flussi OD hanno picchi pronunciati, il picco corrispondente nel traffico del link è smorzato, e difficile da vedere con un'ispezione visiva. Per esempio, il volume di traffico al tempo del picco sui link c-d e b-c è a mala pena riconoscibile. Secondo, i pattern temporali del traffico possono variare sostanzialmente da un link a un altro. Nell'esempio 2, il link i-f ha un trend piuttosto calmo, mentre gli altri link per il flusso OD hanno un traffico più rumoroso. Separare il picco dal rumore nel traffico sul link c-b è visivamente molto più difficile che separare il picco nel link i-f. Allora isolare tutti i link che stanno subendo un'anomalia è difficile. Infine, i livelli medi di traffico variano considerevolmente. Nell'esempio 1, il livello medio del traffico sul link c-d è più che doppio di quello del link f-i. I livelli variabili del traffico rendono difficile la stima della grandezza dell'anomalia di volume e quindi la sua importanza funzionale. Vedremo come il PCA è in grado superare tali difficoltà.

2.3 Cos'è e come funziona il PCA [1]

2.3.1 Introduzione

Il PCA (Principal Component Analisys) è un metodo di trasformazione delle coordinate che mappa un dato set di dati in nuovi assi. Questi assi sono chiamati assi principali o componenti principali. Quando si lavora con dati a media nulla, ogni componente principale ha la proprietà di puntare nella direzione della massima varianza rimanente nei dati, data la varianza già considerata nelle componenti precedenti. Così, la prima componente principale cattura la varianza dei dati al più alto livello possibile su un singolo asse. Le successive componenti principali catturano ciascuna la massima varianza tra le direzioni ortogonali rimanenti. Allora, gli assi principali sono ordinati dall'ammontare di varianza dei dati che catturano.

2.3.2 Notazione utilizzata

dall'aggregazione di flussi. La relazione tra il traffico del link e il traffico di un aggregato può essere concisamente catturata nella matrice di routing A. La matrice A ha dimensioni (#link)x(#aggregati), dove A_ij=1 se l'aggregato j passa sul link i, e zero al contrario. Allora il vettore dei conteggi del traffico sul link y è legato al vettore dei conteggi del traffico nell'aggregato x dalla relazione

y= Ax . Sia m il numero di link nella rete, e t il numero di intervalli di tempo successivi di interesse. Definiamo Y la matrice t x m delle misurazioni, che denota la serie temporale di tutti i link. Allora, ogni colonna i denota la serie temporale dell'i-esimo link e ogni colonna j rappresenta un'istanza di tutti i link al tempo j. Mentre Y denota il set delle misure sui link nel tempo, lavoreremo frequentemente solo con y, un vettore di misure di un singolo step temporale. Allora y è una riga arbitraria di Y trasposta in un vettore colonna. Ci riferiamo alle colonne individuali di una matrice usando un singolo pedice, quindi la serie temporale delle misure sul link i è denotata Yi .

Tutti i vettori in questo paragrafo sono vettori colonna, se non diversamente specificato.

2.3.3 Funzionamento

Applicheremo il PCA sulla nostra matrice dei dati dei link Y, trattando ogni colonna di Y come un punto di ℝm _. Tuttavia, prima di fare ciò è necessario aggiustare Y così che le sue colonne abbiano media nulla. Questo assicura che le dimensioni del PCA catturino vera varianza, ed evita così risultati scorretti dovuti a differenze nell'utilizzazione media dei link. Per il resto di questo documento, Y denoterà i dati di traffico dei link centrati sulla media. Applicare il PCA a Y conduce ad un set di m componenti principali,

{

_}

v₁=arg max ∥v∥=1∥Yv∥

dove ∥Yv∥2 _{è proporzionale alla varianza dei dati misurati} lungo v. Procedendo iterativamente, una volta che le prime k-1 componenti principali sono state determinate, la k-esima componente principale corrisponde alla massima varianza del residuo. Il residuo è la differenza tra i dati originali e i dati mappati nei primi k-1 assi principali. Allora, possiamo scrivere la k-esima componente principale v_k come:

v_k=arg max

∥v∥=1∥(Y −

∑

Yv_iv_iT)v∥

Un uso importante del PCA è di esplorare la dimensionalità intrinseca di un set di dati. Esaminando l'ammontare della varianza catturata da ogni componente principale, ∥Yvi∥

2 , possiamo chiederci se la maggior parte della variabilità nei dati può essere catturata in uno spazio di dimensioni minori. Se troviamo che solo la varianza lungo le prime r dimensioni è non trascurabile, possiamo concludere che il set di punti rappresentato da Y risiede in uno sottospazio r-dimensionale di ℝm _.

2.3.4 Costruzione del sottospazio con il PCA

Una volta che gli assi principali sono stati determinati, il set di dati può essere mappato nei nuovi assi,. Il mappaggio dei dati sull'asse principale i è dato da Yv_i . Questo vettore può essere normalizzato a lunghezza unitaria dividendo per la sua norma. Allora, per ogni asse principale i, abbiamo:

u_i= Yvi ∥Yvi∥

∀i=1,... , m

I vettori u_i hanno dimensione t (dove t è il numero di intervalli di tempo successivi presi in considerazione) e sono ortogonali per costruzione. L'equazione sopra mostra che tutti i contatori dei link, quando pesati per vi , producono una dimensione dei dati trasformata. Allora il vettore u_i cattura la variazione temporale comune all'intero insieme delle serie temporali del traffico sui link lungo l'asse principale i. Poichè gli assi principali sono in ordine di contribuzione alla varianza complessiva, u1 cattura il trend temporale più forte comune a tutto il traffico del link,

u₂ il secondo più forte e così via. Il metodo dei sottospazi funziona separando gli assi principali in due set, corrispondenti a variazioni normali o anomale del traffico. Lo spazio coperto dal set degli assi normali è il sottospazio normale S e lo spazio coperto dagli assi anomali è il sottospazio anomalo Š.

Figura 4 – Scenario generico

In figura 4 vediamo uno scenario generico. Le proiezioni u₆ e u₈ , in contrasto con u1 e u2 , mostrano un comportamento anomalo significativo. Quei "picchi" di traffico indicano condizioni di rete inusuali, possibilmente indotte da un'anomalia di volume a livello dell'aggregato. Il metodo dei sottospazi tratta tali proiezioni come appartenenti al sottospazio anomalo. Una varietà di procedure possono essere applicate per separare i due tipi di

proiezione nei set normale e anomalo. Basandoci sull'esaminazione delle differenze tra proiezioni normali e anomale (lato sinistro e destro di figura 4), abbiamo sviluppato un semplice metodo di separazione a soglia, che funziona bene nella pratica. Specificamente, la nostra procedura di separazione esamina la proiezione su ogni asse principale nell'ordine; quando una proiezione supera la soglia (che può essere stabilita in vari modi, ad esempio sia una deviazione di 3σ dalla media), quell'asse principale e tutti i successivi sono assegnati al sottospazio anomalo. Tutti i precedenti sono invece assegnati a quello normale, il che significa che tutte le dimensioni mostranti una varianza significativa sono assegnate al sottospazio normale. Questa procedura ha avuto come effetto, nella maggior parte dei casi, l'inserimento delle prime quattro-cinque componenti principali nel sottospazio normale. Avendo separato lo spazio di tutte le possibili misure di traffico sui link nei sottospazi S e Š, possiamo decomporre il traffico su ogni link nelle sue componenti normali e anomale.

2.3.5 Rivelazione

La rivelazione delle anomalie di volume nel traffico dei link fa affidamento sulla separazione del traffico di link y ad ogni intervallo di tempo nelle componenti anomale e normali. Ci riferiremo a queste come le parti modellate e residuali di y. L'idea chiave nel passaggio della rivelazione basato sui sottospazi è che, una volta che S e Š sono stati costruiti, questa separazione può essere effettivamente performata formando la proiezione del traffico del link su questi due sottospazi. Cioè, puntiamo a dividere il set delle misure del link y in un dato punto nel tempo come:

y= ŷ + ỹ

così che ŷ corrisponda al traffico modellato e ỹ a quello residuale. Formiamo ŷ proiettando y su S e ỹ proiettando y su Š. Per fare ciò, organizziamo il set delle componenti principali corrispondenti al sottospazio normale (

v₁, v₂, ... , v_r ) come colonne di una matrice P di dimensioni m x r dove r è il numero degli assi normali

(scelti come descritto in sezione 1.2.4). Possiamo quindi scrivere ŷ e ỹ come:

ŷ=P PT _{y=Cy e ỹ=(I −P P}T

)y=Čy

dove la matrice C=PPT rappresenta l'operatore lineare che esegue la proiezione sul sottospazio normale S e Č analogamente proietta nel sottospazio anomalo Š. Allora ŷ contiene il traffico modellato e ỹ quello residuale. In generale, l'occorrenza di una anomalia di volume risulterà in un grande cambiamento di ỹ. Una statistica utile per rivelare cambiamenti anormali in ỹ è l'errore quadratico medio di predizione (square prediction error, SPE):

SPE≡∥ỹ∥2=∥Čy∥2

e possiamo considerare il traffico di rete normale se: SPE⩽δα2

dove δα 2

denota la soglia dello SPE al livello di confidenza 1-α. Un test statistico per il vettore residuale noto come il Q-statitico è stato sviluppato da Jackson e

Mudholkar ed è dato in [11] come: δ_α2=Φ₁[cα

√

∑

e dove λj è la varianza catturata proiettando i dati sulla j-esima componente principale ( ∥Yvj∥

2

) e c_α è il percentile 1-α in una distribuzione normale standard. Il risultato di Jackson e Mudholkar vale indipendentemente da quante componenti principali sono contenute nel sottospazio normale. Notare che in questo settaggio, il limite di confidenza 1-α corrisponde a un rate di falsi allarmi di α, se le assunzioni sotto le quali questo risultato è derivato sono soddisfatte. Il limite di confidenza per la Q-statistica è derivato sotto l'assunzione che il vettore dei campioni y segua una distribuzione gaussiana multivariata. Tuttavia,

Jensen e Solomon fanno notare che la Q-statistica cambia poco anche quando la sottostante distribuzione dei dati originali differisce sostanzialmente dalla gaussiana [12]. Mentre crediamo che il traffico normale nei nostri set di dati sia ragionevolmente ben descritto come gaussiano multivariato, non abbiamo esaminato da vicino i dati per violazioni di questa assunzione. Tuttavia, troviamo che la Q-statistica dia risultati eccellenti in pratica, forse grazie alla robustezza notata da Jensen e Solomon. Una proprietà importante di questo approccio è che non dipende dall'ammontare medio di traffico nella rete. Allora, si può applicare lo stesso test su reti di dimensioni e livelli di utilizzazione differenti. Nella figura 5 illustriamo l'efficienza della separazione in sottospazi di y su due generici set di dati. La metà alta della figura mostra il plot temporale di ∥y∥2 su periodi di settimane. Su tali plottaggi, abbiamo cerchiato i punti dove eravamo a conoscenza della presenza di anomalie di volume. E' chiaro che la grandezza del vettore di stato y è dominato da effetti che non sono le

anomalie, e che è abbastanza difficile vedere gli effetti delle anomalie sul volume di traffico nel suo insieme. Nella metà inferiore di ogni plottaggio mostriamo i plot temporali dello SPE, ∥ỹ∥2 _{, sugli stessi periodi da una settimana. Per} ogni set di dati, i valori della Q-statistica δα

2

al livello di confidenza (1-α) di 99.5% e 99.9% sono mostrati in linee tratteggiate. I plot più in basso mostrano come la proiezione del vettore di stato nel sottospazio residuale Š catturano molto efficacemente il traffico anomalo mentre catturano molto poco traffico normale, e quindi rendono la rivelazione statistica delle anomalie molto più facile.

Questa figura mostra come distintamente il metodo dei sottospazi sia in grado di separare pattern di traffico anomali (plottaggi in basso) dalla massa del traffico (plottaggi in alto). Dà anche una certa spiegazione sul perchè il metodo unisce tali elevati rate di rivelazione con bassi rate di falso allarme. Come può essere visto nei plottaggi più in basso, la separazione distinta delle anomalie dal traffico normale significa che quasi tutte le anomalie risultano nei valori di ∥ỹ∥2 maggiori di δα2 , mentre molto poche misure di traffico normale portano ∥ỹ∥2 _{maggiori di δ}

Capitolo 3

Un protocollo sicuro per il calcolo della

matrice di covarianza[4]

Come anticipato nel paragrafo 2.3.3, applicare il PCA alla matrice di traffico consente di trovare le componenti principali necessarie al funzionamento del PCA stesso. Per fare ciò, è necessario calcolare una matrice, detta matrice di covarianza, definita come:

S =1 t Y

T Y

dove ̄Y rappresenta la matrice di traffico centrata e t è il numero di intervalli di tempo considerati. In questo capitolo vogliamo spiegare nel dettaglio la tecnica utilizzata per effettuare tale calcolo in maniera collaborativa ed evidenziarne pregi e difetti.

3.1 Introduzione

In numerosi contesti, si può avere un'immensa utilità da analisi statistiche che integrano database multipli e distribuiti. Per esempio, modelli statistici possono essere formati usando più record o più attributi quando i database sono integrati di quando vengono analizzati separatamente. L'integrazione dei dati è complicata e dà preoccupazioni riguardo la loro confidenzialità, includendo barriere legali, regolatorie e addirittura fisiche. Queste preoccupazioni possono essere presenti anche quando i proprietari dei database cooperano per effettuare analisi integrate e nessuno di essi cerca di danneggiare la confidenzialità dei dati altrui. All'interno della letteratura statistica, maggiore attenzione è stata diretta al caso dei database partizionati orizzontalmente comprendenti gli stessi attributi numerici di set disgiunti di dati. Per esempio, alcuni stati o agenzie educazionali locali potrebbero voler combinare i dati dei loro studenti per aumentare la precisione delle analisi della popolazione generale degli studenti. Analisi basate su

statistiche sufficienti che sono additive tra i vari database possono essere eseguite usando la somma sicura per calcolare queste statistiche. Esempi includono regressioni lineari, costruzione sicura di tavole di contingenza, integrazione di dati, stima a massima verosimiglianza per famiglie esponenziali, e algoritmi EM sicuri. Minor attenzione è stata diretta ai database partizionati verticalmente comprendenti gli stessi dati ma contenenti set differenti di attributi. Per esempio, un'agenzia governativa potrebbe avere informazioni di lavoro, un'altra dati sulla salute, e una terza dati sull'educazione tutti degli stessi individui. La regressione lineare per dati partizionati verticalmente è stata trattata solo sotto l'altamente restrittiva ipotesi che l'attributo di risposta è condiviso tra tutti i proprietari. Nella letteratura informatica, il privacy-preserving data mining (PPDM) è emerso come approccio interessante in vari contesti. Una radice del PPDM è la computazione multiparte sicura (SMPC), di cui la somma sicura è un caso speciale. Algoritmi per dati partizionati

orizzontalmente sono stati sviluppati per il data mining con regole di associazione. Per dati partizionati verticalmente, esistono metodi sicuri di analisi per, ad esempio, l'analisi del discriminante lineare. Alcune di queste tecniche sono incomplete da una prospettiva statistica: per esempio, gli stimatori sono calcolati ma errori standard e altre quantità che gli statistici considererebbero parte integrante dell'analisi non lo sono. Altri approcci, alcuni dei quali sono stati studiati sia dagli statistici che dagli informatici, includono la distorsione dei dati e la randomizzazione. Il campo della limitazione della scoperta statistica è preoccupato col bilanciare protezione dei valori confidenziali dei dati con la disseminazione delle informazioni utili derivate dai dati. Esempi includono la protezione dei dati categorici sottostanti grandi tabelle di contingenza, server che disseminano i risultati di analisi anzichè i dati. Sotto questi metodi ci sono misure quantificate di utilità dei dati e rischio di scoperta. Le tecniche presentate in questo capitolo sono progettate per

consentire ai proprietari dei database di effettuare analisi che nessuno di essi può effettuare da solo perchè nessuno ha accesso a tutti gli attributi. Esse proteggono i proprietari dei database l'uno dall'altro nel senso che vengono scambiate solo informazioni aggregate. Specificamente, mostriamo come effettuare la regressione e analisi relative su dati partizionati verticalmente usando un approccio alternativo. Assumiamo che i proprietari dei database non condividano valori dei dati ma sono disposti a condividere semplici medie e covarianze dei loro database individuali. Il nostro focus principale è sul calcolo della matrice di covarianza, al cui scopo i proprietari devono scambiarsi alcune dimensioni dei loro dati. E' importante notare che la perdita di protezione discussa in questo articolo si applica solo ai proprietari di database che si trovano viso a viso uno con l'altro, e solo in un senso aggregato dello span dei loro database. In effetti, questo è vero in generale per la PPDM. La misura LP definita successivamente non serve a valutare minacce alla confidenzialità dei record dei dati o la privacy

di soggetti di dati individuali, focus tradizionale della limitazione della scoperta statistica, derivanti sia dalla computazione della matrice di covarianza o il suo uso per effettuare analisi come la regressione. Una eccezione a ciò, dove un'agenzia può ottenere i valori esatti dei dati di un'altra agenzia per un soggetto, è discussa nel paragrafo 3.4. Dalle medie condivise e dalla matrice di covarianza completa, i proprietari possono effettuare set di analisi più ricchi della semplice stima dei coefficienti di regressione. Queste analisi includono inferenza per i coefficienti, diagnostica dei modelli e selezione del modello.

3.2 Calcolo della matrice di covarianza completa

Etichettiamo i proprietari dei dati come ISP A, ISP B. Il database "globale" X, illustrato per tre ISP in figura 6, è verticalmente partizionato fra tutti gli ISP:

X =[ XA_XB_{.. . X}Z

globale, supponiamo che l'ISP A abbia p_A attributi, e sia

p= p_A+p_B+....+ p_Z . Nel seguito assumeremo che gli ISP siano semi-onesti: essi aderiscono perfettamente ai protocolli progettati per preservare la privacy, ed effettuano calcoli usando i loro veri dati. Inoltre, assumiamo che gli ISP non colludano fra loro; alcune implicazioni di ciò sono discusse nel paragrafo 3.3. Vediamo allora, in linea generale, cosa devono fare tre ISP per calcolare una matrice di covarianza completa. L'obiettivo degli ISP è di calcolare e condividere XTX in una maniera che minimizza le informazioni che ognuno deve rivelare agli altri sui valori dei propri dati. Come mostra la figura 6, XTX è formata da:

● Blocchi sulla diagonale principale della forma (Xi)TXi . Ognuno di questi deve essere calcolato da un ISP e condiviso con gli altri.

● Blocchi fuori dalla diagonale principale della forma (Xi

calcolato da due ISP, e il risultato condiviso con gli altri.

Nel paragrafo 3.2.1 descriviamo il protocollo per il calcolo di (Xi)TXj usando un prodotto matriciale sicuro.

3.2.1 Un protocollo sicuro per calcolare prodotti matriciali

Qui vediamo una forma di moltiplicazione matriciale sicura per calcolare i blocchi fuori dalla diagonale principale

(Xi)TXj della matrice di covarianza completa XTX . Per semplicità, si considerino gli ISP A e B. Scriviamo i dati dell'ISP A come XA

=[X1AX2A.... XpAA] , questa è una

rappresentazione non convenzionale della matrice dell'ISP A, nel senso che le Xi

A _{sono le colonne della matrice dei}

dati di tale ISP, ognuna delle quali appartiene a ℝn . Similmente, scriviamo i dati dell'ISP B come

XB

=[X1BX2B.... XpBB] . Assumiamo che XA e XB

siano di rango massimo; se non lo fossero, ogni ISP dovrebbe eliminare ogni colonna linearmente dipendente. I due ISP sperano di calcolare in maniera sicura la matrice

XATXB di dimensione pAx pB , e condividerla con gli

generico per calcolare XATXB e poi mostriamo come può

essere applicato in maniera tale che le informazioni scambiate tra i due ISP siano simmetriche. Il nostro protocollo procede come segue:

1) L'ISP A genera un set di g vettori n-dimensionali

{Z₁Z₂... Z_g} tali che Zi T

Xj

A

=0 ∀ i , j e spedisce all'ISP B la matrice Z =[Z₁Z₂... Z_g] di dimensione n x g . Il metodo per generare Z che porta a degli Z_i ortonormali viene presentato successivamente (vedi par. 3.5), mentre la scelta di g viene spiegata nel paragrafo successivo.

2) L'ISP B calcola W =(I −ZZT)XB dove I è una matrice identità quadrata n-dimensionale e spedisce W all'ISP A.

3) L'ISP A calcola:

(XA)TW =( XA)T(I−ZZT)XB=(XA)T XB

dove la seconda uguaglianza si ha poichè

(XA

valore di (XA)TXB con gli altri ISP. Ricordandosi il punto 2, l'ISP A potrebbe spedire la matrice quadrata n-dimensionale ZZT all'ISP B. Ciò sarebbe in effetti più sicuro, ma la perdita di protezione, discussa nel paragrafo seguente, non cambia.

3.2.2 Perdita di protezione

La protezione (assoluta e relativa) che il protocollo sopra descritto fornisce agli ISP A e B dipende dal parametro g del punto 1. Innanzitutto, consideriamo due casi estremi:

● g = 0: in questo caso, al punto 3, W= XB , quindi l'ISP A avrebbe scoperto i dati dell'ISP B esattamente.

● g = n-p: in questo caso, l'ISP B conoscerebbe esattamente il complemento ortogonale di XA su

ℝn . Anche se ciò non specifica esattamente

XA _.

Nessuno dei due ha senso in generale. Comunque notiamo che i due casi limite non sono perfettamente simmetrici. Un metodo per scegliere g considera la perdita di protezione in cui incorrono i due ISP, che denotiamo come LP(A) per l'ISP A. Misuriamo la perdita di protezione di un ISP dal numero di vincoli linearmente indipendenti che l'altro ISP ha sui suoi dati. Cioè, per l'ISP A: LP( A)= pApB+pAg

dove il primo termine tiene conto delle p_A∗B entries di

(XA)TXB alla fine del processo. Il secondo termine riflette che B conosce sia Z che il fatto che (XA

)TZ=0 . Si può anche vedere LP(A) come una quantità relativa ai "gradi di libertà" totali in XA che sono n x p_A . Allo stesso modo, LP(B)= pApB+pB(n−g) in cui il primo

termine è uguale a quello di LP(A), mentre il secondo tiene conto del fatto che l'ISP A sa che il rango di W è n-g, che è anche il motivo per cui l'ISP A non può invertire W per ottenere XB _{. La perdita totale di protezione , espressa in}

funzione di g, è allora:

LP(g)=LP( A)+LP(B)=2 pApB+npB+(pA−pB)g

Notiamo che, quando p_A=p_B , si ha

LP(g)=2 pApB+n pB , indipendentemente dal valore di

g. Rispetto ai due casi estremi, quando p_A=p_B la perdita di protezione totale è costante, e g stabilisce solo come tale perdita è distribuita tra l'ISP A e l'ISP B. In generale, sembra equo che la perdita di protezione venga condivisa equamente tra i due ISP. Introduciamo allora l'inequità I come:

I(g)=∣LP( A)−LP(B)∣=∣( pA+pB)g−npA∣

Provando a trovare il minimo di tale funzione otteniamo il valore ottimale per g: g= pA

pA+pB

n . Tale valore ha una interpretazione naturale: gli ISP A e B possiedono insieme

p_A+p_B attributi, dunque pA

pA+pB

è la parte dell'ISP A di tali attributi. Quando A ha un maggior numero di attributi,

deve cedere più informazioni a B che viceversa. Per tale motivo, in questa tesi, si è fatto in modo che tutti gli ISP avessero, nella loro matrice dati, lo stesso numero di colonne.

3.3 Altri problemi di equità

Il valore ottimale di g si applica solo al calcolo di

(XA)TXB . Ma non è l'unico problema di equità associato al calcolo di XTX . Quando gli ISP hanno un numero diverso di attributi, l'inequità più eclatante è associata ai blocchi sulla diagonale (Xi

)TXi _{, le cui dimensioni sono} p_ix p_i e possono differire sostanzialmente da un ISP all'altro. Senza considerare i blocchi fuori diagonale, ogni ISP sta concedendo pi2 condizioni sui propri dati. Inoltre,

la perdita di privacy LP(A) è ciò che l'ISP A perde nei confronti dell'ISP B nel calcolo di (XA

non viene interamente data a nessuna degli altri ISP, poichè nessuno di essi conosce XB _{, ma conoscono condizioni}

diverse su XB , e computazioni del secondo ordine potrebbero essere possibili. L'ISP A deve necessariamente effettuare i calcoli (XA

)TXi _{con qualsiasi altro ISP i, il}

che aumenta la perdita di privacy. Tuttavia, se si assume che gli ISP non colludano, tale perdita non aumenta. Se ci fosse il pericolo che gli altri ISP colludano, l'ISP A potrebbe mitigare gli effetti rendendo le matrici Z che invia agli altri ISP sotto-matrici di una stessa matrice. Questo porterebbe a far sì che l'ISP B per cui g sia il più grande scoprirebbe più di tutti gli altri riguardo ad A, ma ciò che scoprono gli altri sarebbe incluso in ciò che è stato già scoperto.

3.4 Altre minacce alla privacy

Il protocollo descritto non è immune a brecce di privacy. Per esempio, se la matrice Z al passo 1 del protocollo contiene

una colonna di tutti zeri eccetto in una posizione, allora l'ISP A scopre da (XA)TW il valore del dato dell'ISP B di quella posizione. Tale occorrenza è però facilmente rivelabile dall'ISP B, che può semplicemente non rispondere. Anche quando gli ISP sono semi-onesti, alcune scoperte potrebbero derivare dagli stessi valori degli attributi. Notiamo che questi problemi sono presenti nel calcolo di XTX effettuato con qualsiasi metodo, e non sono causati (né alleviati) dall'uso del protocollo descritto. Come semplice esempio, supponiamo che XA abbia un attributo che sia zero per tutti tranne che per uno solo dei soggetti cui i dati si riferiscono. Anche scegliendo una Z legittima, (XA

)TXB _{rivelerà il valore di tale soggetto in}

XB _{. Problemi simili si hanno se X}A _{è sporadica e si}

hanno informazioni affidabili sulla posizione delle entrate diverse da zero. In tale situazione, il numero effettivo di gradi di libertà in XA _{è inferiore, forse anche molto}

un attributo dal valore dominante, cioè che eccede il 90% della somma degli altri valori per tale attributo, quel valore sarà rivelato approssimativamente in tutte le (XA)TXB . Non abbiamo considerato le implicazioni dell'applicazione del nostro metodo in situazioni in cui i dati cambiano nel tempo, ma chiaramente, un'applicazione ripetuta del nostro protocollo a database che si evolvono rivela sempre più informazioni. Infine, ci sono problemi che possono essere rivelati solo facendo delle analisi. Per esempio, l'ISP A potrebbe effettuare una regressione di tutti gli altri attributi sui propri. Se una di tali regressioni portasse ad un alto coefficiente di determinazione, allora A saprebbe che possiede nei propri dati un buon predittore per tale attributo, anche se questo è posseduto da un'altro ISP. Un modo per affrontare tali problemi è quello di condividere solo alcuni degli attributi che si posseggono. Come ciò funzionerebbe e se ciò fosse veramente efficace per preservare la privacy sarà oggetto di ricerche future.

3.5 Generazione dei vettori Z

Il punto 1 del protocollo per il prodotto matriciale sicuro richiede g vettori Z tali che: Zi

T Xj

A

=0 ∀ i , j . Questi possono essere generati usando la decomposizione QR di

XA che si può esprimere come XA=QR , dove Q è una matrice n x n ortonormale ed R è una matrice n x p_A

triangolare superiore. Per costruire Z, bisogna partizionare Q nel senso delle colonne come Q=[Q₁Q₂] dove in

Q₁ abbiamo messo le p_A colonne più a sinistra di Q. A questo punto, Z può essere ottenuta selezionando g colonne di Q₂ . Se l'ISP A teme che la conoscenza da parte dell'ISP B che la decomposizione QR è stata usata rivela delle informazioni, può permutare le colonne di XA _prima

di effettuare la decomposizione, e poi permutare corrispondentemente le colonne di Z prima di spedirla all'ISP B.

Capitolo 4

Implementazione del PCA tramite

protocolli per il prodotto matriciale sicuro

In questo capitolo ci occupiamo in dettaglio dell'implementazione del PCA effettuata in maniera collaborativa dagli ISP partecipanti e di precisare alcuni aspetti riguardanti le tecniche di computazione multiparte sicura adottate.

4.1 Scenario di riferimento

Possiamo immaginare la rete su cui abbiamo effettuato la rivelazione delle anomalie come l'interconnessione delle reti degli ISP che hanno deciso di effettuare tale rivelazione in maniera collaborativa. All'interno di uno di tali ISP è stato

necessario trovare posto per un coordinatore, che, come vedremo, è indispensabile alla corretta esecuzione di tutti i passaggi necessari a tale scopo.

Figura 7 – Scenario di riferimento con tre ISP

4.2 Matrice dei dati

La prima operazione che ciascun ISP deve effettuare, è l'estrazione dalle tracce di traffico disponibili delle informazioni necessarie (nel caso specifico, le tracce contenevano gli IP destinazione e il numero di byte ricevuti