[ 11 ottobre 2012 at 20:40 –

(1)

Universit`a degli Studi di Roma La Sapienza

Facolt`a di Ingegneria

Corso di Laurea Magistrale in Ingegneria Informatica

Tesi di laurea magistrale

Studio degli effetti

di comportamenti bizantini

nel sistema TERA

Candidato:

Claudio Papa Matricola 795121

Relatore:

Prof. Leonardo Querzoni Correlatore:

Prof. Massimo Mecella

Anno Accademico 2011–2012

(2)

Claudio Papa: Studio degli effetti di comportamenti bizantini nel sistema Publish-Subscribe TERA, Tesi di laurea magistrale, c 18 ottobre 2012.

(3)

Dedicato a Veronica

(4)

(5)

I N D I C E

1 sistemi publish subscribe 1 1.1 Il modello di comunicazione 1 1.2 Modelli di sottoscrizione 5 1.3 Event routing 6

1.4 TERA 7

2 modelli di guasto e comportamento bizantino 13 2.1 Modelli di guasto 13

2.2 Il problema dei Generali Bizantini 14 2.2.1 Nsyad 16

2.2.2 Brahms 17

2.3 Modello per analisi di comportamenti bizantini 18 2.4 Minacce in TERA 21

2.4.1 Subscription Advertising 22 2.4.2 Access Point Table Lookup 25 2.4.3 Event Publishing 27

3 variazione della popolarità 31

3.1 Mediazione distribuita della popolarità 38 3.1.1 Uso delle Subscription Table 39 3.1.2 Uso delle Acces Point Table 40 3.2 Valutazione locale della popolarità 44

3.2.1 Valutazione del criterio minimo 48

3.2.2 Stima della frequenza di sottoscrizione 50 3.3 Approccio misto 52

4 ricerca degli access point 55

4.1 Probabilità in caso di scarto della ricerca 55 4.2 Effetti della non uniformità nella APT 59 5 dettagli implementativi 63

5.1 Count min sketch 64

5.1.1 Conservative Update 68 5.1.2 Count Mean Min 70

5.1.3 Lossy conservative update 72 6 conclusioni 79

bibliografia 81

(6)

E L E N C O D E L L E F I G U R E

Figura 1 Rappresentazione grafica di un event space costituito da 3 attributi (x,y,z) costituenti l’event schema, ciascuno identifica- to da un asse 2

Figura 2 Rappresentazione grafica di un sistema publish/subscribe nel quale sono presenti subscribers e publisher 3

Figura 3 Infrastruttura a due livelli di TERA e pubblicazione di un evento 8

Figura 4 Raffigurazione ad alto livello delle componenti costituenti l’architettura di TE-

RA 10

Figura 5 Rappresentazione che mostra la relazione che intercorre tra le varie tipologie di guasto in cui un processo può incorre-

re 13

Figura 6 Confronto tra la distribuzione dei topic nelle APT utilizzando la popolarità reale e quella in cui è stato inserito un errore randomico. 32

Figura 7 Distribuzione dei topic nelle access point table stimata attraverso la formula (5) e simulata nel caso in cui la grandezza è pari al numero dei topic 36

Figura 8 Frequenze dei topic nelle Access Point Ta- ble con diverse percentuali di nodi bizantini. 37

Figura 9 Grafico che mostra la probabilità di trovare un nodo che abbia sottoscritto un certo topic 40

Figura 10 Frequenza della distribuzione dei topic nelle APT con e senza l’uso della mediazione distribuita tramite APT introducendo nel sistema il 10% di nodi bizanti-

ni 42

(7)

Figura 11 Frequenza della distribuzione dei topic nelle APT con e senza l’uso della mediazione distribuita tramite APT introducendo nel sistema il 30% di nodi bizanti-

ni 43

Figura 12 Frequenza media di comparizione dei topic nei messaggi di subscription adversti- sing effettuando 1000 e 2000 cicli elebo- rativi 45

Figura 13 Probabilità approcci minimo, massimo e somma nell’uso dei contatori di frequenza dei topic nei messaggi di advertising 46 Figura 14 Confronto tra le distribuzioni dei topic

nelle APT utilizzando l’approccio minimo, massimo e originale nell’uso dei contatori di frequenza dei topic nei messaggi di advertising 47

Figura 15 Probabilità approcci minimo, massimo e somma nell’uso dei contatori di frequenza dei topic nei messaggi di advertising 49 Figura 16 Distribuzione dei topic nelle APT popo-

late utilizzando la popolarità reale e quella stimata attraverso la formula14 51 Figura 17 Distribuzione dei topic nelle APT popo- late utilizzando l’approccio TERA stan- dard ed utilizzando quello misto 53 Figura 18 Grafico con le probabilità di trovare un

certo topic effettuando una operazione di ricerca distribuita nelle APT 57 Figura 19 Grafico con le probabilità di trovare un

certo topic effettuando una operazione di ricerca distribuita nelle APT 58 Figura 20 Grafico in cui viene mostrata il rappor-

to delle ricerche andate a buon fine dove i nodi bizantini modificano sia la popo- larità negli advertisment che scartano le richieste di ricerca di access point, con- frontato con i dati in cui non si modifica la popolarità, non si effettua scarto e non è presente alcun comportamento bizantino 60

(8)

Figura 21 Grafico in cui viene mostrata la proba- bilità di trovare un access point per un topic nel caso in cui è stato usato l’approccio della sezione 3.3 per mitigare la variazione della popolarità 61

Figura 22 Uno stream di topic 64

Figura 23 Il topic t1 è mappato tramite le funzioni hash h1,h2 e h3 in 3 colonne diverse, dove verrà incrementato il corrispondente contatore 65

Figura 24 Simulazioni effettuate per valutare la va- lidità dell’approssimazione tramite count min sketch di dimensione 3x70. 67 Figura 25 Simulazioni effettuate per valutare la va-

lidità dell’approssimazione tramite count min sketch di dimensione 3x100. 67 Figura 26 Risultato simulazioni per valutare la va-

lidità dell’approssimazione tramite count min sketch con conservative update di dimensione 3x70. 69

Figura 27 Risultato simulazioni per valutare la va- lidità dell’approssimazione tramite count min sketch con conservative update di dimensione 3x100. 69

Figura 28 Risultato simulazioni per valutare la va- lidità dell’approssimazione tramite count mean min sketch di dimensione 3x100. 71 Figura 29 Risultato simulazioni per valutare la va-

lidità dell’approssimazione tramite count min sketch con lossy conservative update po- litica LCU-ALL di dimensione 3x100 74 Figura 30 Risultato simulazioni per valutare la va-

lidità dell’approssimazione tramite count min sketch con lossy conservative update po- lica LCU-1 di dimensione 3x100 75 Figura 31 Risultato simulazioni per valutare la va-

lidità dell’approssimazione tramite count min sketch lossy conservative update politi- ca LCU-WS di dimensione 3x100 76

(9)

Figura 32 Risultato simulazioni per valutare la va- lidità dell’approssimazione tramite count min sketch con lossy conservative update po- litica LCU-SWS di dimensione 3x100. 77

E L E N C O D E L L E TA B E L L E

Tabella 1 Alterazioni cui può essere soggetto un messaggio 19

Tabella 2 Elenco delle strutture di memorizzazione dati di TERA 21

Tabella 3 Elenco delle operazioni di comunicazione in TERA 21

Tabella 4 Probabilità di trovare un topic effettuando una operazione di ricerca nelle APT al variare del TTL 56

(10)

(11)

Non è possibile unire i puntini guardando avanti potete solo unirli guardandovi all’indietro.

— Steve Jobs

R I N G R A Z I A M E N T I

Questo è un grazie a tutti quelli che mi sono stati vicino: a Veronica, che mi ha sempre spinto ad andare avanti ed ha tra- mutato le mie sconfitte in vittorie; ai miei genitori, che hanno sopportato i miei silenzi, le mie assenze e che mi hanno soste- nuto in questo lungo cammino; a mio fratello e mia sorella che hanno saputo strapparmi un sorriso quando vedevo tutto nero.

Spero di poter ripagare tutti voi almeno il doppio di quanto mi avete saputo dare.

Roma, 18 ottobre 2012 C. P.

(12)

(13)

I N T R O D U Z I O N E

I sistemi publish/subscribe sono una famiglia di modelli di comunicazione sempre più diffusa che consentono, tra le altre cose, di realizzare multicast efficiente di informazioni a livello applicativo. Esistono varie tipologie di implementazioni la cui principale differenza risiede nell’utilizzo di una architettura centralizzata oppure di una distribuita.

Realizzare un sistema con una architettura distribuita, nello specifico una architettura peer to peer, nella quale ciascun nodo della rete ha uguali funzioni e responsabilità, comporta una serie di sfide da superare ma anche una serie di benefici, primo tra i quali una maggiore resistenza ad eventuali crash di nodi del sistema.

Una delle problematiche che introduce un sistema peer to peer è proprio derivante dalla struttura paritetica: uno dei processi potrebbe cercare di minare il corretto funzionamento dell’intera rete, introducendo messaggi studiati appositamente per causare danno. Riuscire a rilevare ed a notificare questo tipo di comportamenti è impresa ardua poiché non tutti i nodi potrebbero rilevare il malfunzionamento ed i messaggi generati potrebbero essere completamente legali.

In questa tesi ci siamo occupati principalmente di questo tipo di comportamenti, detti bizantini, e degli effetti che questi potrebbero causare se inseriti in un sistema distribuito, introducendo un modello di riferimento per analizzare tale tipo di comportamento. Il capitolo2 si occupa di tutto questo e dell’u- tilizzo dell’approccio sistematico ideato, per analizzare un reale sistema publish/subscribe: Tera.

Dall’analisi effettuata, Tera è risultato particolarmente sen- sibile alla manomissione dei messaggi di subscription advertising ed in particolare all’alterazione delle popolarità in essi contenu- te, ma è anche stato individuato un problema importante se i nodi malevoli avessero rigettato le richieste di access point lookup, che sono alla base del funzionamento dell’intero sistema.

Individuate queste problematiche si è cercato di trovare una strategia per poter mitigare gli effetti da esse prodotti.

Il capitolo 3 si occupa di dialogare con il problema della variazione delle popolarità introducendo diversi tentativi per riu-

(14)

scire a contrastarne gli effetti. Inizialmente la strada percorsa è stata completamente distribuita, cercando di ottenere insiemi di dati puliti interpellando altri nodi nel sistema.

Dei due tentativi effettuati nessuno ha avuto buon esito: uno a causa della bassissima probabilità di trovare le informazioni cercate, l’altro dovuto al fatto che i risultati soffrivano trop- po della presenza dei nodi bizantini, poiché questi interveniva- no sempre nel momento in cui venivano richieste informazioni remote.

Gli altri approcci seguiti sono stati nella direzione inversa:

cercare di ottenere la popolarità di un topic basandosi su una stima effettuata localmente da ciascun processo. L’osservazione principale è che anche la frequenza con la quale i nodi incon- trano i topic nei messaggi di subscription advertising, segue una distribuzione molto simile a quella della sottoscrizione degli stessi. Memorizzando con l’ausilio di contatori queste informazioni, le abbiamo utilizzate per calcolare varie probabilità di inserimento dei topic nelle access point table.

La distribuzione uniforme dei topic nelle access point table è un requisito fondamentale per il funzionamento di TERA ed è per questo che si è cercato in tutti i modi di garantirlo: la strategia migliore è risultata quella di combinare insieme i due set di dati, che contenevano stime diverse della popolarità, come si può approfondire nella sezione3.3.

Nel capitolo 4 abbiamo valutato invece quale impatto viene prodotto nei confronti di Tera, se un nodo malizioso rispon- desse ad una richiesta di access point lookup asserendo di non conoscere nessun access point per il topic richiesto e conseguen- temente non inoltrando la richiesta ad altri nodi. L’operazione di access point lookup è una operazione di ricerca distribuita ed il risultato finale dipende dal numero di nodi interpellati durante la ricerca, se nel cammino effettuato viene incontrato un nodo bizantino, questo potrà interrompere la ricerca, impedendo di ottenere il corretto risultato.

Per incrementare la robustezza nel caso in cui vi sia questo comportamento, si è visto come è importante incrementare il numero di ricerche in parallelo piuttosto che incrementare la lunghezza di ogni singola ricerca, quindi abbiamo cercato di calcolare quali dovrebbero essere queste quantità per ottenere, con probabilità vicine alla certezza, un risultato positivo.

Nell’ultimo capitolo, invece, riprendiamo quanto ideato nel capitolo 3 e proponiamo l’utilizzo di strutture probabilistiche, quali il count min sketch, per memorizzare la notevole quantità

(15)

Elenco delle tabelle xv di dati necessaria ai fini implementativi. Nello stesso capitolo valutiamo anche delle tecniche di ottimizzazione che applicate allo sketch permettono di migliorare il rendimento dello stesso.

Ricapitoliamo di seguito i punti salienti di tutti i capitoli:

capitolo 1 in questo capitolo presentiamo i sistemi publish/- subscribe ed in particolare illustriamo TERA con tutti i suoi componenti;

capitolo 2 introduciamo i tipi di guasto cui può essere soggetto un sistema distribuito, soffermandoci in particolar modo sui guasti bizantini. In questo contesto abbiamo sviluppato un modello da seguire per analizzare gli effetti cui è soggetto un sistema distribuito, se sottoposto alla presenza di nodi con comportamenti bizantini.

Applicando questo modello di analisi a TERA sono stati messe in evidenza una serie di criticità causate da comportamenti bizantini.

capitolo 3 riguardo TERA, si è analizzato più in profondità il problema della variazione della popolarità nei messaggi di subscription advertising. Nel corso di questo capitolo abbiamo trovato una metodologia che, sotto specifiche con- dizioni, consente di ovviare al problema citato, riuscen- do a valutare se il dato di popolarità trasmesso è valido oppure se è stato frutto di alterazione arbitraria.

capitolo 4 è stata rivalutata la formula che consentiva, in TERA, di stimare la lunghezza delle access point table lookup, in modo tale da avere una buona probabilità di suc- cesso della ricerca. Nella formula è stato introdotto il con- tributo dei nodi bizantini, il cui comportamento è quello di rigettare le richieste in ingresso. Inoltre è stata valu- tata l’efficacia del sistema ideato nel capitolo 3 sempre nell’ambito delle operazioni ricerca di un access point;

capitolo 5 nel corso di questo capitolo abbiamo effettuato dei test sull’utilizzo di strutture dai probabilistiche ( count min sketch), per riuscire ad implementare il metodo di mi- tigazione dell’alterazione delle popolarità garantendo la scalabilità su sistemi di dimensioni più grandi.

(16)

(17)

1 S I ST E M I P U B L I S H

S U B S C R I B E

Il paradigma Publish Subscribe è un modello di comunicazione molti a molti, costituito da consumatori e produttori di informazioni. I produttori possono inviare dati sotto forma di eventi a più consumatori contemporaneamente, mentre i consumatori ricevono informazioni per le quali hanno sottoscritto uno specifico interesse.

1.1 il modello di comunicazione

Il modello Publish Subscribe è costituito dai seguenti elemen- ti

publishers sono quei componenti del sistema che producono informazioni sotto forma di eventi. Tali eventi sono inviati in tutto il sistema ma i publishers non devono preoccuparsi di localizzare i destinatari dei dati inviati.

subscribers sono i consumatori delle informazioni, ai quali vengono notificati gli eventi per i quali è stato mostrato interesse attraverso una sottoscrizione;

sottoscrizioni sono il meccanismo attraverso il quale un utente nel sistema può dichiarare interesse circa un certo da- to ed in pratica costituiscono un filtro sull’intero insieme delle informazioni pubblicate.

servizio di notifica degli eventi è il servizio che si occupa di mettere in comunicazione produttori e consumatori di informazioni, notificando ad ogni subscribers gli eventi pubblicati che corrispondono alle sottoscrizioni effettuate.

Grazie a questa strutturazione il modello permette di avere disaccoppiamento spaziale, ovvero consumatore e produttore non necessitano di conoscersi reciprocamente, di avere disaccoppiamento temporale, ovvero le parti non devono essere contemporaneamente presenti quando ha luogo la comunicazione, ed infine non necessita di alcun meccanismo di sincronizzazione, es-

(18)

2 sistemi publish subscribe

sendo l’interazione mediata per mezzo del Servizio di Notifica degli Eventi.

Centrale nel modello è in concetto di evento come contenito- re di informazioni: un evento deve essere emesso (o pubblica- to) dai publishers secondo una struttura determinata a priori, a cui ci si riferisce come event schema, che definisce un insieme di coppie attributo-valore dove ciascun attributo è identificato da un nome e può contenere valori di un certo tipo. L’insieme dei possibili eventi può essere rappresentato astrattamente come uno spazio multi-dimensionale (event space), dove ogni dimensione rappresenta un attributo dell’event schema con un dominio che è costituito dall’insieme dei valori ammissibili per quell’attributo.

z

y x

Figura 1:Rappresentazione grafica di un event space costituito da 3 attributi (x,y,z) costituenti l’event schema, ciascuno è identifica- to da un asse. I due cubi rappresentano due sottoscrizioni, in quanto intersecano intervalli nei domini degli attributi I subscribers, come già detto, esprimono il proprio interesse ad un evento per mezzo di una sottoscrizione, che è un vincolo stabilito al di sopra dell’event schema e può essere immagina- to come una determinata porzione dell’event space, formata dai sottoinsiemi che il vincolo sull’event schema esprime per ciascun attributo. L’Event Notification Service si occuperà quindi di notificare un evento ad un sottoscrittore, solamente se l’evento soddisfa i vincoli sull’event schema dichiarati.

Un sistema publish/subscribe è un sistema distribuito complesso ed esistono molte tipologie di implementazione, per cui riu-

(19)

1.1 il modello di comunicazione 3

Publisher Publisher Publisher

Subscriber Subscriber Subscriber

Event Notification

Service publish

subscribe

Figura 2: Rappresentazione grafica di un sistema publish/subscribe nel quale sono presenti subscribers e publisher

scire ad offrire una panoramica completa di tutte le possibilità è un copito arduo. Uno dei più recenti lavori di classificazione sull’intero panorama è in [16] che propone una analisi dimensionale di ciascun sistema, nel quale le dimensioni sono tra loro giustapposte ed esprimono una particolare caratteristica del problema.

Riportiamo di seguito le dimensioni architetturali:

modello di sottoscrizione il modello di sottoscrizione permette di specificare gli eventi ai quali un nodo è interes- sato. Approfondiremo questo argomento nella sezione 1.2;

modello di rappresentazione dei messaggi i messaggi di pubblicazione e sottoscrizione possono contenere informazioni più o meno complesse. Questa dimensione si occupa di classificare la modalità di rappresentazione di tali messaggi. La distinzione fondamentale è tra dati se- rializzati, alla maniera della serializzazione Java, taggati, come ad esempio il formato XML e binari non taggati;

algoritmi di matching sono gli algoritmi che consentono di identificare i sottoscrittori che sono interessati ad un certo evento. Gli algoritmi dipendono ovviamente dal modello di sottoscrizione utilizzata: ad esempio nel modello topic based è possibile utilizzare un albero di matching per specificare una sottoscrizione di tipo gerarchico. In generale la distinzione è fatta tra utilizzo di predicati ed utilizzo di testing networks;

organizzazione della overlay questa è una delle caratteri- stiche più importanti di un sistema distribuito che concer-

(20)

ne l’organizzazione logica della rete o overlay infrastructu- re a livello applicativo, che coinvolge anche politiche di scelta dei partner di comunicazione e di gestione dei grup- pi. La suddivisione principale si ha tra sistemi gerarchici, sistemi peer-to-peer e sistemi con organizzazione a clusters.

L’approccio gerarchico prevede l’organizzazione del grafo dei nodi sotto forma di un’albero di comunicazione, è adatto in generale per sistemi di piccole dimensioni. L’organizzazione di tipo P2P può essere ulteriormente espan- sa distinguendo tra sistemi strutturati, non strutturati e broker overlay. La differenza tra strutturato e non strutturato sta nell’approccio deterministico o probabilistico uti- lizzato nell’invio dei messaggi di comunicazione. I sistemi con broker overlay invece introducono una distinzione tra nodi clienti del sistema (quelli che pubblicano e sot- toscrivono eventi) e nodi che fungono da forwarders delle informazioni.

L’organizzazione cluesterizzata altro non è che un approccio ibrido che prevede la creazione di cluster di nodi che prevedono una specifica e solitamente diversa organizzazione intra-cluster e inter-cluster;

tecniche di disseminazione di questa dimensione parleremo più avanti nella sezione 1.3 e riguarda principalemen- te le tecniche utilizzate per effettuare il routing dei dati nella overlay network. Ovviamente è influenzata dalla mo- dalità con cui è organizzata la rete ed influisce sulla mo- dalità con cui un messaggio viene inoltrato tra i diversi nodi costituenti il sistema di comunicazione;

tecniche di adattamento con questa voce si vuole definire la capacità di un sistema di reagire alle modifiche topo- logiche che intervengono nella rete durante il periodo di esecuzione dell’algoritmo distribuito;

consapevolezza del sottostrato i sistemi di comunicazione attuali sono strutturati come una pila di protocolli tra loro sovrapposti. In alcuni casi specifici è importante conoscere quale sia l’implementazione sottostante della rete per raggiungere degli obiettivi specifici;

quality of service la capacità del sistema di offrire delle garanzie, ad esempio in termini di assicurazione o tempi di consegna.

(21)

1.2 modelli di sottoscrizione 5

1.2 modelli di sottoscrizione

Abbiamo detto che una sottoscrizione può essere vista come un sottoinsieme dell’intero spazio degli eventi. Una classificazione di questi modelli è stata effettuata in [1] dove viene rimarcato il fatto che modelli differenti comportano anche un differente potere espressivo: un modello di sottoscrizione molto epressivo permette di specificare gli eventi nei quali si è interessati con una maggiore precisione.

I più popolari modelli di sottoscrizione sono i seguenti:

topic based i sottoscrittori dichiarano l’interesse verso un determinato argomento (topic) e riceveranno gli eventi che dichiarano di essere afferenti quel determinato topic. Il topic può essere immaginato come un canale logico che permette di interconnettere tutti i publishers e tutti i subscribers che hanno rispettivamente pubblicato un evento e sottoscritto un interesse verso quel determinato topic.

L’espressività di questo modello è abbastanza limitata in quanto l’unica possibilità è di dichiarare l’interesse o meno sull’argomento. Una delle modifiche utilizzate per garantire una maggiore possibilità è quella di organizzare il topic space in maniera gerarchica: in questo modo dichia- rando l’interesse per un determinato topic si sottoscrive- ranno automaticamente anche tutti i topic del sotto-albero cui fa capo l’argomento indicato.

content based in questo modello la sottoscrizione è una query costituita da un insieme di vincoli sui valori degli attributi. Il linguaggio di sottoscrizione può essere più o meno complesso e comprende operazioni di confronto, uguaglianza ma anche espressioni regolari. La comples- sità influenza molto le performance e richiede molte risorse per una maggiore complessità dovuta al fatto che la valutazione del matching è effettuato per evento ed è per questo che in generale il linguaggio non permette di andare oltre query congiuntive.

type based gli eventi di questa tipologia di publish/subscribe sono degli oggetti appartenenti ad una particolare tipologia di dato, che può anche incapsulare attributi e metodi.

In questo modo si ottiene una garanzia sui tipi già all’interno del sistema di diffusione degli eventi che offre maggiore sicurezza sulla gestione dei dati rispetto al modello

(22)

di dato non strutturato. Il filtro principale è dato dalla tipologia di dato trasmesso, tuttavia una specifica più pre- cisa può essere ottenuta filtrando anche il contenuto degli attributi ad esso allegati.

concept based questo tipo di modello si discosta totalmente da tutti gli altri, perché non utilizza in realtà un filtro costituito da una struttura rigida per estrapolare il sottoinsieme del topic space. Questi sistemi infatti fanno uso di ontologie per specificare dei concetti e quindi deve essere fornita una base di conoscenza per una interpretazione non ambigua delle stesse.

1.3 event routing

L’event routing è quella componente logica del sistema che si occupa della disseminazione delle informazioni nella rete, in modo tale da consentire il corretto funzionamento della comunicazione tra publishers e subscribers che è fortemente dipendente dal tipo di overlay network implementata. Esistono tre principali tecniche di disseminazione: flooding, selective, gossiping.

flooding letteralmente inondazione, consiste nell’inviare le informazioni a tutti i nodi della rete. Visto che nei sistemi publish/subscribe vi sono due tipologie di messaggi vi sono altrettante tecniche di flooding: event flooding e subscription flooding.

La tecnica dell’event flooding consiste nell’inviare tutti i messaggi di pubblicazione degli eventi a tutti quanti i nodi della rete, indistintamente. Dunque anche i nodi che non hanno sottoscritto quell’evento saranno raggiunti dallo stesso ed il filtro è fatto dal nodo stesso.

La tecnica del subscription flooding è speculare: tutte le sottoscrizioni saranno inviate a tutti i nodi della rete, i quali dovranno memorizzarle localmente, per poi utiliz- zarle, nel momento in cui viene pubblicato un evento, per contattare tutti i sottoscrittori.

Queste due tipologie sono molto semplici ed è possibile implementarle per mezzo di un broadcast delle informazioni nella rete, la conseguenza primaria è un forte overhead di risorse quali la memoria e la banda di comunicazione.

(23)

1.4 tera 7 selective con questo approccio si cerca di ridurre il più pos-

sibile l’overhead causato dalla memorizzazione delle informazioni e dal numero di pacchetti scambiati tra i nodi. Le due principali tecniche sono il selective filtering ed l’uso di nodi di rendezvous.

Il selective filtering prevede la creazione di percorsi di routing per consentire agli eventi da notificare, di essere inol- trati solamente a quei nodi che sono sul percorso che ha come destinazione un nodo la cui sottoscrizione combacia con quell’evento. Per garantire questo tipo di disseminazione è necessario che ciascun nodo memorizzi una tabella di routing che, a differenza del subscription flooding, è un aggregato ed un sottoinsieme di tutte le sottoscrizioni.

L’altra tecnica detta Redezvous-base prevede la presenza nella rete di particolari nodi responsabili di un certo sot- tospazio degli eventi. In particolare vengono definite due funzioni SN(s) e EN(e): la funzione SN, data in ingresso una sottoscrizione, restituisce un insieme di nodi responsabili per la gestione della sottoscrizione in ingresso mentre la funzione EN, complementare alla SN, dato in ingresso un evento restituisce anche essa un sottoinsieme di nodi. La pubblicazione di eventi quindi è in grado di essere notificata correttamente ai sottoscrittori solamente se SN(s) ∩ EN(e) = 0.

Il routing è un processo a due fasi: nella prima un publisher contatta il rendezvous-node dell’evento che deve pubblicare, nella seconda il nodo contattato leggera tutte le sottoscrizioni pervenutegli e inoltrerà l’evento ai nodi sottoscrittori.

gossip il gossip è una tecnica di disseminazione probabilisti- ca che consiste nello scegliere randomicamente un sottoinsieme di nodi verso i quali effettuare uno scambio di informazioni. La scelta dei nodi con il quale dialogare è alle volte dettata dall’utilizzo di informazioni locali determinate tramite il funzionamento di un algoritmo.

1.4 tera

TERA (Topic-based Event Rounting for peer-to-peer Alchitec- tures in [2]) è una implementazione di un sistema publish/sub-

(24)

scribe basato su topic, pensato per sistemi di larga scala su di un ambiente peer-to-peer.

TERA prevede una infrastruttura su due livelli: una global overlay che connette tutti quanti i nodi della rete, al livello superiore un insieme di topic overlays che connettono nodi che hanno sottoscritto uno stesso topic. Queste reti sono gestite da un overlay management protocol che non è specificato, ma è sufficiente che rispetti dei vincoli: in particolare sia nella global che nella topic overlay il grafo risultante deve essere connesso, inoltre devono essere implementati due servizi:

1. il peer sampling service che deve fornire un campione uniforme di nodi della rete;

2. il size estimation service che deve fornire una stima del numero di nodi costituenti la rete;

Il funzionamento di TERA prevede che quantd un nodo vuole effettuare la sottoscrizione di un particolare topic, deve entra- re a far parte della corrispondente topic overlay network di livello superiore. Quando un evento riguardante un topic t deve essere pubblicato, lo si deve inoltrare ad un access point del topic in questione ovvero ad un nodo che ha già sottoscritto t, questo dovrà poi occuparsi della disseminazione dell’evento all’interno della rete di livello superiore.

Topicoverlay

Node Nodeused

asaccesspoint

Event routed in thesystem General overlay

Figura 3:Infrastruttura a due livelli di TERA e pubblicazione di un evento

La struttura interna di funzionamento è composta da 5 componenti: subscription management, event management, access point lookup, partition merging e inner-cluster dissemination.

subscription management come già intuibile dal nome, questa è la componente che si occupa di gestire le sottoscrizioni e per farlo utilizza una subscription table locale a

(25)

1.4 tera 9 ciascun nodo. Nella tabella sono memorizzate delle coppie (t, i) che costituiscono rispettivamente l’identificativo del topic sottoscritto e l’identificativo della topic overlay network che si occupa di memorizzare i nodi sottoscrittori di quel topic.

Quando un nodo vuole sottoscrivere un nuovo topic t, deve riuscire ad ottenere l’identificativo della rete che lo gestisce e allo scopo deve utilizzare una operazione di access point lookup ( di cui parleremo subito dopo). Se questa operazione fallisce, non restituendo alcun access point allora il nodo sarà con grande probabilità l’unico sottoscrittore e così potrà istanziare una nuova topic overlay network.

Oltre a ciò la componente è responsabile dell’invio perio- dico del contenuto della propria subscription table ad un insieme di nodi ottenuti randomicamente attraverso il sottostante servizio di peer sampling. Per ogni topic inviato tramite il messaggio di advertising dovrà anche essere in- clusa una stima della popolarità dello stesso, ottenibile tramite il già menzionato size estimation service.

event management questa è la parte di sistema deputata al- l’invio degli eventi di pubblicazione. Le operazioni che compie sono molto semplici: nel momento in cui viene pubblicato un evento, viene interpellato il componente access point lookup che dovrebbe restituire un access point per il topic di interesse. Se non esiste alcun access point il messaggio viene scartato, poiché non vi è alcun sottoscrittore, diversamente l’evento è inoltrato al nodo restituito tramite la lookup che è poi responsabile dell’invio alla relativa topic overlay network;

access point lookup questa parte del sistema è cruciale, essendo utilizzata per le operazioni di sottoscrizione e pubblicazione di un evento, ed è basata sulla struttura dati chiamata access point table (APT). Questa tabella contiene riferimenti ad un topic e ad uno dei suoi access point e può essere vista come una sorta di tabella di routing, che però non contiene informazioni globali ma solo una parte di esse.

Ogni volta che questa componente viene interpellata, la tabella viene letta per trovare un riferimento al topic che

(26)

si sta cercando e, in caso positivo, viene restituito l’access point memorizzatovi.

L’aggiornamento di questa struttura avviene per mezzo dei messaggi di advertising generati dalla componente di subscription management secondo la seguente politica:

• se il topic è già presente nella APT, l’access point in essa contenuta deve essere sostituito con quello presente nel messaggio di advertising;

• se non è presente allora verrà inserito all’interno della struttura con una probabilità inversa rispetto a quella comunicata nel messaggio di advertising, se la APT è piena allora verrà scelto randomicamente un elemento da sovrascrivere;

Il risultato di questo approccio è che ciascun topic è uni- formemente distribuito all’interno delle access point table, per cui nel momento in cui si interroga la APT di un nodo randomicamente scelto, qualsiasi topic ha equiprobabilità di esservi contenuto.

TERA Applications

Overlay Management Protocol

Network

Event Management Subscription Management

Broadcast Partition Merging Access Point Lookup

Peer Sampling Size Estimation

subscribe unsubscribe publish notify

Figura 4:Raffigurazione ad alto livello delle componenti costituenti l’architettura di TERA

La access point lookup è quindi un operazione di ricerca distribuita, il cui scopo è ottenere informazioni su di un

(27)

1.4 tera 11 qualsiasi access point di un determinato topic t e questo si può ottenere interrogando la access point table di una serie di nodi. Maggiore è il numero di nodi interrogati e maggiore sarà la probabilità di trovare le informazioni cercate.

partition merging può capitare che effettuando una operazione di ricerca di un access point per un determinato topic t, questa non riesca a trovarne alcuno. In questo caso il il nodo richiedente è portato a pensare che è l’unico sottoscrittore del topic, ma un’altra possibilità è che l’operazione di lookup non abbia semplicemente trovato una APT contenente t. A questo punto nel sistema vi sarebbero dunque due topic overlay network con identificativi diversi, che però si riferiscono allo stesso topic.

La componente di partition mergin si occupa proprio di risolvere queste situazioni: nel momento in cui un nodo, ricevuto un messaggio di advertising, si accorge di questa discrepanza, contatta il nodo sorgente del messaggio e inizia una procedura che si concluderà con la fusione delle due topic overlay networks.

(28)

(29)

2 M O D E L L I D I G U A STO E

C O M P O RTA M E N TO

B I Z A N T I N O

2.1 modelli di guasto

Un sistema distribuito è per definizione costituito da un insieme di calcolatori, interconnessi tra loro grazie ad un canale di comunicazione. Nulla toglie che un calcolatore, o processo o nodo che dir si voglia, possa manifestare un errore e che questo possa guastare il funzionamento di uno degli algoritmi che il nodo stava eseguendo.

La classe più generale di guasti che un processo può incontra- re sono quelli arbitrari, anche detti bizantini o maliziosi, perché questi questi deviano arbitrariamente dall’algoritmo ad essi as- segnato e non è possibile fare alcuna previsione sul comportamento che mostreranno. Affronteremo questo argomento più nel dettaglio nella sezione 2.2

Arbitrario Omissione Crash e Recoveries

Crashes

Figura 5: Rappresentazione che mostra la relazione che intercorre tra le varie tipologie di guasto in cui un processo può incorrere Nella figura 5 è possibile vedere quale è la relazione che intercorre tra varie tipologie di failure ed ovviamente nella parte più esterna abbiamo la tipologia più generale di cui abbiamo appena accennato. La prima tipologia meno generale di comportamento è quella di tipo chrash e recoveries che include sia il caso in cui il nodo si guasta e ferma la sua esecuzione, sia il caso in cui il nodo va in crash un numero indefinito di volte e ogni volta riesce a riprendere il suo funzionamento.

Con questo tipo di astrazione un processo può sia recupera- re l’elaborazione precedente, così che agli occhi di altri processi

(30)

14 modelli di guasto e comportamento bizantino

nella rete sembrerà che sia avvenuta semplicemente un qualche tipo di omissione, oppure può accadere che il nodo soffra di am- nesia. Quest’ultimo caso è più difficile da gestire poichè il nodo potrebbe inviare nella rete dei messaggi che contraddicono quelli precedentemente inviati.

Un tipo più ristretto di guasto è quello dell’omissione, che si presenta ogni volta in cui un processo non invia un mossaggio che si suppone esso dovesse inviare secondo l’algoritmo che sta eseguendo. Oltre che da comportamenti appositi questo tipo di guasto può essere generato da buffer overflow o da congestione di rete.

Infine la categoria più specifica di guasto si ha quando un processo da un certo tempo in poi non invia più alcun messaggio ad altri processi e questo accade quando ad esempio quando un nodo va in crash e poi non è più in grado di ripartire.

2.2 il problema dei generali bizan-

tini

Il guasto di tipo arbitrario di un nodo in una rete potrebbe portare lo stesso a comportarsi in maniera non prevedibile, inse- rendo informazioni contraddittorie nel sistema minando quindi il corretto funzionamento dello stesso. Questo problema è stato codificato da Lamport, Shostak e Paese [12] come il Problema dei Generali Bizantini.

Il problema è il seguente: ci sono una serie di divisioni dell’e- sercito Bizantino, accampate attorno ad una città nemica, ognu- na comandata da un generale. Un generale può comunicare con un altro solamente per mezzo di messaggi e si devono accordare tra di loro per un piano d’azione.

Alcuni generali tuttavia sono dei traditori ed il loro scopo è quello di evitare che i generali fedeli trovino un accordo sul da farsi ovvero se attaccare o ritirarsi. Dunque dovrebbe essere messo in atto un algoritmo che consenta ai generali leali di raggiungere lo stesso piano di azione e questo nonostante un piccolo numero di traditori cerchi di impedirlo.

Il comportamento per l’assedio consiste nell’osservare la città nemica, prendere una decisione ed inviarla a tutti gli altri generali a capo di una divisione, tenendo a mente che un traditore potrebbe inviare informazioni diverse a nodi diversi; in questo modo se ad esempio la modalità per prendere una decisione è

(31)

2.2 il problema dei generali bizantini 15 semplicemente la maggioranza di scelte prese (ritiro o attacco).

Si può notare come nel caso in cui le scelte dei leali siano ugual- mente divise tra “attacco” e “ritiro” anche un piccolo numero di traditori può influenzare la scelta finale.

Se indichiamo con i il generale i-esimo e con v(i) la decisione da esso presa in merito alla strategia, quello che si vuole ottenere è che:

1. per ogni i ogni coppia di generali leali deve usare lo stesso valore di v(i)

2. se l’i-esimo generale è fedele allora il valore che invia deve essere usato da ogni generale fedele come valore di v(i)

Per poter rispettare la condizione (1) alcuni generali dovranno utilizzare valori diversi rispetto a quelli inviati da alcuni generali, facciamo un esempio indicando con a la decisione di attaccare e con r la decisione di ritirarsi prendendo in conside- razione solo 3 generali di cui solo 1 traditore. Le decisioni prese dal generale 1 e dal generale 2 sono rispettivamente a e r, mentre il generale 3 invia al nodo 1 a mentre al nodo 2 r. I generali 1, 2 e 3avranno come vettore delle scelte prese rispettivamente [a,r,a], [a,r,r] e [a,r,a] e si può notare come i generali fedeli non rispet- tano la condizione (1) avendo un vettore diverso che li porta a prendere decisioni diverse se il criterio adottato è quello della maggioranza. Per poter ristabilire l’uguaglianza tra i vettori è necessario che venga modificato il contenuto e la condizione (2) specifica che non deve essere variato ne v(1) ne v(2).

Visto che il problema riguarda i singoli valori inviati da un generale agli altri, il Problema dei Generali Bizantini viene così riformulato:

Problema dei Generali Bizantini. Un generale capo deve inviare un ordine ai suoi n − 1 luogotenenti in modo tale che:

1. tutti i generali luogotenenti fedeli obbediranno allo stesso ordi- ne;

2. se il generale capo è fedele allora ogni generale luogotenente fedeli rispetterà l’ordine impartito;

Questo problema è risolvibile solamente se c’è un adeguato numero di generali ed in particolare se abbiamo un totale di 3t + 1 generali allora è dimostrabile che è possibile gestire fino

(32)

ad un massimo di t generali traditori ( che da ora in poi chiame- remo generali bizantini), quindi in un sistema con solo 3 generali di cui uno bizantino è impossibile arrivare ad un accordo.

Un nodo di rete che si comporta come un generale bizantino (nodo bizantino) ovvero che invia informazioni discrepanti in un sistema di rete è un problema difficile da affrontare, nel segui- to cercheremo innanzitutto di stabilire quali possono essere i problemi che tale comportamento può causare in protocolli di comunicazione che non sono ideati specificamente per gestire questo tipo di comportamenti.

2.2.1 Nsyad

Non esiste un approccio generale per risolvere il problema dei nodi bizantini in quanto il tipo di comportamenti che possono assumere è molto vario, tuttavia in letteratura esiste qualche tentativo in merito.

In [10] è stato sviluppato un approccio denominato Nysiad per poter trasformare un qualsiasi protocollo tollerante ai crash in uno tollerante ai guasti bizantini, utilizzando una variante di una Reliable State Machine. Considerando ogni host della rete come una macchina a stati finiti, la tecnica adottata consiste nel- l’assegnare a ciascun nodo un certo numero di guard hosts che contengono una replica della macchina a stati finiti, in particolare 3t + 1 guard hosts sono necessari per tollerare fino ad un massimo di t nodi bizantini ed inoltre due nodi vicini devono avere in comune minimo 2t + 1 guard hosts.

Il sistema adotta quattro protocolli per ottenere il suo obietti- vo:

replication protocol assicura l’integrità tra le varie replied state machine ovvero che lo stato delle repliche sia sincro- nizzato;

attestation protocol consente di validare gli eventi di input, attraverso dei contatori e dei token generati dalle repliche;

credit protocol forza un host a processare tutti gli input oppure di ignorarli tutti, caso nel quale il nodo può essere considerato come fermo;

epoch protocol permette di generare e riconfigura il grafo dei guard hosts utilizzando un servizio centralizzato che gestisce la configurazione del grafo;

(33)

2.2 il problema dei generali bizantini 17 Il tallone di achille di questo approccio sta nella struttura del grafo che assicura la resistenza ai nodi bizantini, infatti in reti relativamente piccole o centralizzate non vi sono problemi di sorta, mentre nella conversione di protocolli peer to peer di larga scala la necessità di una struttura rigida e dipendente da un punto di accesso quale quello definito dal protocollo di epoch costituisce un problema difficilmente gestibile anche in virtù dell’alto grado di dinamicità di questi sistemi.

2.2.2 Brahms

Presentiamo quì rapidamente un protocollo restitente agli at- tacchi bizantini, il cui scopo è quello di restituire un campione randomico dei nodi appartenenti ad un sistema dinamico.

Brahms (byzantine resilient random membership sampling)riesce ad ottenere due risultati in un ambiente in cui è presente una certa percentuale di nodi malevoli, il primo è quello di restituire un campione di nodi che consente di ottenere un campione indipendente uniforme di nodi ed il secondo è che con alta proba- bilità riesce ad evitare che un attaccante crei una partizione tra i nodi corretti del sistema.

L’utilizzo più concreto di questo algoritmo è nei protocolli di membership gossip, nei quali ogni nodo mantiene un insieme randomico di host detto local view, che è asintoticamente più piccolo della dimensione globale della rete. Uno dei problemi a cui sono soggetti questi sistemi è quello dell”’avvelenamento“

della vista (poisoning view), ovvero nella possibilità che un processo malizioso possa riuscire a riempire la local view di un altro nodo con identificatori di nodi fasulli o maliziosi. In questo modo il nodo vittima sarebbe escluso dal sistema e lo scopo di partizionare la rete costituita dai nodi corretti sarebbe riuscito.

I tipi di operazioni consentite sono principalmente: operazioni di push, che consistono nell’inviare ad un altro processo uno o più identificatori di nodi e operazioni di pull che consistono nel richiedere ad un altro nodo il contenuto della propria vista locale.

Brahms prevede l’aggiornamento della propria view prelevan- do gli identificatori con percentuali differenti da:

• valori ottenuti da operazioni di push

• dati ottenuti da operazioni di pull

• identificatori ottenuti tramite utilizzo dei samplers

(34)

Il sampler è una componente che utilizza dati storici, ottenuti sempre da operazioni da pull e push, per restituire un singolo nodo. Ciascun sampler utilizza una permutazione min-wise indi- pendent per restituire il campione richiesto. Dalla combinazione di questi comportamenti ciascun nodo ottiene un campione di nodi che converge nel tempo. Per maggiori informazioni si consulti [3].

2.3 modello per analisi di compor-

tamenti bizantini

La maggior parte dei sistemi distribuiti in uso attualmente, sono studiati per convivere principalmente con un solo tipo di guasto che in generale è il cosiddetto crash e recoveries ( come già accennato nella sezione 2.1), è infatti molto difficile riuscire a gestire un comportamento bizantino quando questo può essere il più disparato possibile.

Anziché progettare un protocollo ex-novo pensando alla pos- sibilità di impedire comportamenti bizantini è possibile riflettere su quali possono essere gli effetti di un comportamento arbitrario su un sistema già esistente in cui questo comportamento non è stato previsto.

Di seguito vogliamo proporre un approccio minimamente strutturato per analizzare quali possono essere gli effetti della presenza di nodi bizantini in un algoritmo distribuito.

Il primo passo da fare nell’analisi consiste nel redigere un catalogo dell’algoritmo distribuito, una sorta di inventario che consente di prendere coscienza di tutte le variabili di cui è costituito. Non siamo interessati a tutti gli aspetti di un sistema ben- sì solo a quelli che possono intaccare il corretto funzionamento dello stesso, quindi l’attenzione dovrà esser posta in particolare su:

messaggi scambiati tra i nodi che ovviamente costituiscono il cuore di un sistema di comunicazione, senza questi non si potrebbe definire tale. La ragione per la quale si pone l’attenzione su queste componenti è ovvia: la forzatura di qualsiasi genere di un messaggio inviato da un nodo ad un’altro può costituire causa di malfunzionamento;

strutture di memorizzazione dati che conservano in maniera permanente o temporanea informazioni utili all’al-

(35)

2.3 modello per analisi di comportamenti bizantini 19 goritmo. L’interesse su queste strutture si pone nel momento in cui influenzano il comportamento di altri nodi nella rete e non quello locale: possiamo pensare ad una tabella di impostazioni piuttosto che ad una base dati.

Una volta effettuata questa elencazione è necessario espande- re ciascun punto dettagliatamente per poter capire quale è l’influenza di un componente sul comportamento generale, alcune strutture dati possono inoltre essere ignorate nel momento in cui il loro contenuto dipende totalmente dai messaggi scambiati, infatti modificare i messaggi ad essa afferenti piuttosto che la base dati risulterebbe equivalente.

Il dettaglio di ciascun messaggio censito sarà costituito dal tipo di operazione di comunicazione, dal tipo di alterazione cui il messaggio è soggetto e dall’effetto che questa alterazione può generare nel sistema visto nella sua globalità. Lo stile di comunicazione può essere di due tipi: push nel quale il messaggio è solo inviato senza ricezione di un messaggio ulteriore da parte del destinatario oppure send-response se l’operazione si conclude solo con la ricezione di una risposta.

Nella tabella di seguito riportiamo un elenco di tipologie di alterazione su cui è necessario riflettere per ciascuna operazione di comunicazione:

Tabella 1: Alterazioni cui può essere soggetto un messaggio

Tipologia Effetto

omissione L’omissione di un messaggio da parte di un nodo potrebbe costituire un problema per il funzionamento di un protocollo. In alcune situazioni questo comportamento non crea alcun problema magari perchè si uti- lizzano delle tecniche di ridon- danza, mentre in altre possono causare seri problemi, spe- cialmente quando l’omissione è non è sistematica ma sporadi- ca e quindi anche molto difficile da riconoscere.

Tabella 1: continua nella prossima pagina

(36)

Tabella 1: continua dalla pagina precedente

Tipologia Effetto

creazione arbitraria Iniettare nel sistema dei messaggi potrebbe consentire ad un nodo di influenzare il comportamento di un altro inviandogli messaggi che lo indurrebbero a compiere una azione non legale, oppure una azione legale in grado di destabilizzare il nor- male comportamento. Può essere il caso, ad esempio, di un host bizantino che inviando op- portuni messaggi possa poi diri- gere le comunicazioni verso di lui. Bisognerebbe distinguere il caso in cui per un nodo è possibile impersonificarne un altro o meno.

modifica frequenza invio La modifica della frequenza può causare problemi più o meno gravi a seconda della sensi- bilità di una operazione al fat- tore temporale. L’incremento della frequenza di invio tra l’altro potrebbe anche causare dei seri problemi di saturazione di risorse, mentre una diminuzio- ne eccessiva potrebbe avere gli stessi effetti di una omissione alterazione del contenuto L’alterazione del contenuto di

un messaggio è una tra le più esplicite alterazioni, ma non per questo altrettanto semplice da individuare. Per alterazione si intende la modifica del contenuto rispetto ai normali dati che dovrebbero essere presenti.

(37)

2.4 minacce in tera 21

2.4 minacce in tera

Illustrato l’approccio da seguire nell’analisi degli effetti che un nodo traditore può causare all’interno di un sistema distribuito proviamo ad applicarlo ad un caso concreto, seguendo i passi e gli spunti di riflessione esposti nella sezione 2.3. Il protocollo che utilizzeremo è TERA essendo questo già stato descritto nella sezione 1.4.

Il primo passo da compiere è quello di redigere il catalogo delle strutture di memorizzazione dati e delle operazioni di comunicazione. In TERA possiamo trovare el seguenti strutture:

Strutture dati Access Point Table Subscription Table

Tabella 2: Elenco delle strutture di memorizzazione dati di TERA

Per quanto riguarda le operazioni di comunicazione è necessario non inserire nell’elenco tutte quelle che TERA utilizza ma che in realtà non sono parte del sistema, ci riferiamo in particolare a tutte le chiamate a funzioni della global overlay come il servizio di campionamento oppure all’utilizzo di funzioni della topic overlay come il conteggio dei nodi che la compongono. Le operazioni restanti sono le seguenti:

Operazioni di comunicazione Subscription Advertising Access Point Table Lookup

Event Publishing

Tabella 3:Elenco delle operazioni di comunicazione in TERA

Nell’inventario ottenuto in Tabella3mancano all’appello parti del sistema publish/subscribe come il Partition Merging e l’operazione di sottoscrizione di un topic poiché in realtà queste si basano interamente sull’operazione di Access Point Table Lookup già elencata.

(38)

2.4.1 Subscription Advertising

Come già illustrato l’operazione di Subscription Advertising consente ad un nodo di distribuire le proprie sottoscrizioni nel sistema così che altri hosts possano elaborare la richiesta ed inserire eventualmente la sottoscrizione all’interno della propria Access Point Table: è una operazione di tipo push.

Ricordiamo inoltre che l’inserimento di un topic nella APT è strettamente dipendente dalla popolarità del topic ed essa viene infatti inviata tramite il messaggio di Subscription Adver- tising. Il destinatario dell’operazione dovrà fidarsi del valore di popolarità inviatogli senza ottenere ulteriori garanzie sulla bontà di tale dato.

Utilizziamo lo spunto dato dall’approccio per analizzare, da più punti di vista, l’operazione di comunicazione riportando i risultati nella tabella seguente:

modifica frequenza invio Una maggiore frequenza di invio potrebbe essere causa di saturazione delle risorse di un’elaboratore inteso sia come capacità elaborativa che di risorse di rete: questo è un comportamento indipendente dal tipo di messaggio che si sta trasmettendo.

Specificamente per il sistema preso in considerazione una maggiore o minore frequenza di invio non dovrebbe com- portare problemi perché la decisione di inserimento in una APT è presa sulla base della popolarità

omissione Nel caso in cui un nodo omette di inviare questo tipo di messaggio crea un problema circoscritto ad esso stesso: agli occhi degli altri utenti del sistema apparirà come se non avesse sottoscritto alcun topic.

Se host risulta essere l’unico sottoscrittore di un topic, questa omissione lo danneggia ulteriormente causando una riduzione drastica della probabilità di ottenere una notifica di pubblicazione non essendo l’informazione distribuita all’interno delle APT degli altri nodi. La possibilità di ricevere una sottoscrizione rimane ancora se un nodo, effettuando una Access Point Lookup, riuscisse ad incontra- re l’unico sottoscrittore del topic, probabilità questa mol- to prossima allo zero in un sistema di ampie dimensioni.

Nel caso in cui non fosse l’unico sottoscrittore, il nodo ri- ceverebbe le notifiche tramite la topic overlay

(39)

2.4 minacce in tera 23 creazione arbitraria / alterazione del contenuto In que-

sto caso alterare il contenuto o creare messaggi ex-novo porterebbe gli stessi effetti, dunque li tratteremo contemporaneamente.

Questo tipo di messaggio è costituito da un elenco di topic con la relativa popolarità e la modifica del messaggio comporterebbe appunto la variazione del topic, inseren- done alcuni non sottoscritti, l’alterazione della popolari- tà oppure la variazione di entrambe, che sarebbe il caso di creazione arbitraria di messaggi. Vediamo queste eventualità singolarmente.

• alterazione popolarità L’utilizzo della popolarità di un topic è alla base del meccanismo di funzionamen- to di TERA ed è allo stesso tempo punto di forza e di debolezza. L’inserimento nelle APT di un topic dipende in maniera inversamente proporzionale dalla popolarità utilizzata e una variazione di questa influenzerebbe la raggiungibilità di un determinato topic.

Nel momento in cui si effettua una APT lookup il buon esito della ricerca è fortemente condizionato dalla equiprobabilità di trovare un topic in una determinata APT. Se i topic non sono distribuiti unifor- memente all’interno delle tabelle che memorizzano gli access point allora un topic potrebbe non essere rintracciato, cosi da creare delle partizioni. Trattere- mo questo argomento più in profondità nel prossimo capitolo3.

• alterazione topic Il caso di interesse è quello in cui viene inserito un topic che non è stato realmente sottoscritto. Lo scopo di questa operazione potrebbe essere quella di potersi insinuare all’interno della APT di altri nodi e quindi di poter fungere da Access point per quel determinato topic.

Nel momento in cui il nodo, vittima di un messaggio contraffatto, è interrogato tramite una richiesta di APT lookup, questo risponderà inviando un riferimento al nodo bizantino che potrà comportarsi come meglio crede. Potrebbe infatti far finta di essere un Access Point ed alterare così sia le operazioni di sottoscrizione che di pubblicazione di altri hosts essendo la lookup una azione fondamentale del sistema,

(40)

creando una suddivisione dello spazio di notifica e pubblicazione.

Un nodo malevolo quindi avrebbe interesse nel causare più danni possibili nel sistema e per questo è fondamentale che riesca a redirigere una gran parte dell’insieme delle comunicazioni verso esso stesso. Per riuscire ad insinuarsi nelle APT il più possibile, un nodo dovrebbe presentare al destinatario dei topic che hanno una popolarità molto bassa, così da avere una alta probabilità di inserimento oppure presentare topic che sono già all’interno della tabella degli AP, poichè, come già spiegato, in questo caso si scavalcherebbe il meccanismo di inserimento probabilistico andando semplicemente a rimpiazzare nella tabella il valore dell’access point con quello bizantino.

Questo meccanismo è stato introdotto in TERA per cercare di mantenere dei dati sempre abbastanza freschi nella APT, che può essere immaginata come una tabella di routing, dando però una chance maggiore a possibili usi impropri. Una clausola di garanzia sta nel fatto che il contenuto delle APT non è un dato esposto esternamente e quindi un host traditore dovrebbe mettere in atto una strategia per carpirne il contenuto.

A seconda delle capacità del nodo attaccante ci sono diverse possibilità:

• se uno o più nodi sono in grado di origliare nelle comunicazioni in entrata verso un nodo corretto, allora questi potrebbero raccogliere informazioni sui topic notificatigli, che hanno alta probabilità. Una volta immagazzinate suf- ficienti informazioni uno dei nodi bizantini potrebbe inviare un advertising contenente i topic precedentemente catturati e quindi inseriti con alta probabilità nella APT della vittima.

• se non è possibile guardare all’interno delle comunicazioni allora l’unico modo per poter reperire informazioni è attraverso l’attesa di:

1. messaggi di advertsing - ottenendo informazioni su quali sono le sottoscrizioni effettuate dal nodo vittima

2. operazioni di lookup - ottenendo informazioni su quali sono i topic che il nodo vittima non contiene nella propria Access Point Table

(41)

2.4 minacce in tera 25 Entrambi i messaggi non rivelano espressamente cosa contiene la APT di un nodo scelto come vittima, ma danno informazioni su ciò che non è presente al suo interno o che non darà seguito ad una ulteriore richiesta. Il messaggio di advertising conterrà i topic per i quali il nodo è già un access point e quindi per questi, pur essendo presenti nella APT, il nodo non effettue- rà una ulteriore richiesta per trovare informazioni, mentre con l’operazione di lookup il nodo ammette esplicitamente di non avere informazioni circa un determinato topic.

Come sarebbe possibile sfruttare queste informazioni? Se ci fosse un insieme di nodi bizantini collaboranti, questi potrebbero collezionare informazioni su i topic che sono presenti nella rete ed inoltre memorizzare congiuntamente i messaggi di aver- tising e di lookup. Successivamente potrebbe effettuare una differenza tra i due insiemi di dati ottenendo così una collezione di topic che con una certa probabilità potrebbero essere presenti all’interno della APT del nodo vittima. A questo punto i nodi bizantini potrebbero generare un messaggio di advertising contenente i topic elaborati per differenza ed inviarlo al nodo vittima, così da essere rappresentati al suo interno con una buona probabilità.

2.4.2 Access Point Table Lookup

L’operazione di lookup è alla base di molte parti del sistema ed è per questa di notevole importanza. Lo scopo è quello di ottenere, tramite una ricerca distribuita, un riferimento ad un access point per un determinato topic ovvero un nodo che abbia sottoscritto tale topic e che sia quindi in grado di mettere in comunicazione altri nodi con la ttopic overlay. La ricerca è distribuita in quanto può seguire diversi cammini all’interno del grafo che rappresenta la rete di comunicazione, il percorso scelto è puramente randomico e quindi la probabilità di ottenere informazioni su di un particolare access point dipende dall’uniformità della distribuzione di questa informazione.

Analizziamo in maggior dettaglio questa operazione che è costituita da un messaggio di richiesta, dall’inoltro dello stesso e da uno di risposta, dunque è di tipo send-response, tuttavia la forzatura di qualunque genere del messaggio di richiesta non crea problemi al sistema, nel senso che non può causare disfun- zionamenti se non localmente al nodo che è il mittente di tale richiesta.

(42)

omissione Mettiamoci nella condizione in cui un nodo corret- to (il generale leale nel problema di Lamport [2.2]) debba effettuare una ricerca di un access point e che ad un certo punto del cammino distribuito venga contattato un host bizantino (il generale traditore). Il comportamento più ovvio per creare un malfunzionamento da parte di quest’ultimo è quello di dichiarare di non aver trovato alcun access point tra quelli ricercati ed anche di interrompere in questo punto la ricerca senza inoltrarla ad altri nodi.

Il danno causato da questa condotta corrisponderebbe ad una mancata pubblicazione di un evento se l’operazione che ha generato la ricerca fosse stata di pubblicazione, oppure causerebbe una partizione nella topic overlay se il tut- to avesse avuto origine da una richiesta di sottoscrizione:

questo perché un utente per poter sottoscrivere un topic deve collegarsi alla corrispondente overlay e non trovando il riferimento sarebbe costretto a pensare di essere l’unico sottoscrittore generando una nuova sovra-rete.

modifica frequenza invio L’unico problema che potrebbe verificarsi è principalmente di saturazione di risorse: questa operazione è comunque pesante dal punto di vista del numero di messaggi generati e quindi la generazione di un numero di richieste elevato potrebbe saturare il mezzo di trasmissione delle informazioni se non sufficientemen- te veloce.

creazione arbitraria / alterazione del contenuto Siamo interessati in particolar modo alla modifica del messaggio di inoltro ed a quello di risposta. Il primo conterrebbe solamente le informazioni che identificano il topic di interesse per il mittente mentre il secondo contiene informazioni circa il riferimento all’access point per il topic richiesto.

Prendiamo in considerazione il messaggio di inoltro della richiesta: il solo dato contenuto è il topic e quindi è l’unico alterabile. Un nodo bizantino potrebbe scegliere di inoltrare la richiesta di lookup variando però il topic richiesto ed inducendo i nodi successivi nel cammino distribuito a rilasciare in buona fede informazioni sul topic sbagliato. Nel caso in cui l’alterazione avvenisse a livello del messaggio di risposta ci sarebbe l’opportunità di

(43)

2.4 minacce in tera 27 creare un meccanismo analogo a quello già spiegato nella parte di omissione se un nodo dichiarasse di essere l’ultimo della ricerca distribuita rispondendo con assenza di informazioni circa il topic in questione.

Una possibilità alternativa sarebbe di rispondere dichia- rando di essere a conoscenza di un determinato access point con lo scopo di redirigere altre operazioni verso un nodo in particolare, presumibilmente bizantino.

2.4.3 Event Publishing

L’Event Publishing è quella operazione che consente ad un nodo di effettuare una pubblicazione di un dato riguardante un determinato topic ed è alla base del paradigma di comunicazione publish/subscribe. Guardando globalmente questo tipo di operazione possiamo vedere che è costituita da altre azioni più elementari: la prima consiste nell’effettuare la ricerca di un Ac- cess Point per il topic sul quale si vuole pubblicare e la seconda è l’operazione di pubblicazione vera e propria.

La prima parte dell’operazione di pubblicazione è in tutto e per tutto una Access Point Table Lookup, di cui abbiamo ampiamente discusso in precedenza e non merita quindi ulteriori attenzioni. Ci concentreremo nel seguito esclusivamente sulla seconda parte che appunto consiste, una volta trovato il nodo che funge da access point, nell’inviargli un messaggio in- giungendolo di contattare una topic overlay network e inviare l’informazione tramite il protocollo superiore.

omissione L’omissione della pubblicazione vera e propria può essere intesa sia come omissione del messaggio di richiesta di pubblicazione sia come mancato invio del messaggio alla topic overlay network. In entrambi i casi l’effet- to è la mancata pubblicazione del messaggio e quindi i sottoscrittori non avranno mai notifica del dato a loro destinato.

Nel primo caso il problema non esiste se in fase di implementazione non si delega alcun nodo all’invio del messaggio destinato all’access point: se la responsabilità è del nodo stesso che ha iniziato la ricerca sarebbe contropro- ducente solo per se stesso il mancato invio della richiesta.

Nel secondo caso l’esito dipende invece dalla tipologia di nodo che rappresenta l’access point ovvero il problema ci sarebbe solo nel caso in cui questo fosse malevolo.

(44)

modifica frequenza invio/creazione arbitraria Questo tipo di operazione viene effettuata solamente quando esiste una informazione da pubblicare quindi una maggiore frequenza di invio potrebbe essere causata solamente da una generazione arbitraria dei messaggi. Oltre ad un possibile effetto di saturazione delle risorse questa alterazione non ha effetti particolari sul funzionamento del sistema quanto sul possibile fenomeno di spamming che si verrebbe a creare. La presenza di messaggi con contenuto arbitrario non costituisce un malfunzionamento del sistema, ma costituisce un problema dal punto di vista

“semantico”.

alterazione del contenuto Una richiesta di pubblicazione contiene al suo interno l’informazione che deve essere de- stinata a tutti i nodi sottoscrittori di un certo topic. La modifica del topic di destinazione potrebbe portare alla mancata pubblicazione di un evento oppure alla pubblicazione di informazioni incoerenti, in questo caso il comportamento è analogo alla generazione arbitraria di messaggi. La modifica del contenuto del dato potrebbe invece portare problemi di incoerenza nel protocollo superiore ed in special modo se la modifica eseguita fosse stata effettuata essendo consci del danno che potrebbe arrecare ai protocolli che si basano su TERA per il trasporto di informazioni.

Abbiamo visto nel corso di questo capitolo quali sono i danni che possono essere causati se una componente del sistema inizia ad assumere comportamenti di tipo bizantino. La por- tata degli effetti è più o meno vasta a seconda di quale sia la localizzazione e la tipologia del malfunzionamento.

Proporre una soluzione che sia valida per tutti questi problemi è fuori dal nostro scopo, cercheremo di focalizzare l’attenzione su due aspetti in particolare, che ci sembrano interessan- ti. Il primo aspetto è quello della variazione della popolarità accennato nella sezione 2.4.1, dove abbiamo già illustrato del- l’importanza della distribuzione dei topic nelle APT ed inoltre risulta essere un problema abbastanza complesso per la diffi- coltà nel riuscire a comprendere dove sono state effettivamente compiute delle manomissioni.

Il secondo aspetto è invece quello del troncamento di operazioni di ricerca distribuita da parte di nodi malevoli, vogliamo analizzare quanto influiscono sul comportamento corretto del

(45)

2.4 minacce in tera 29 sistema e quanto TERA sia resistente a questa alterazione del protocollo.

(46)

(47)

3 VA R I A Z I O N E D E L L A

P O P O L A R I TÀ

Nel corso dei precedenti capitoli abbiamo illustrato più volte come il funzionamento di tera dipende fortemente dalla distribuzione uniforme dei topic all’interno delle Access Point Table, che a sua volta dipende dalla probabilità con la quale un topic viene inserito al suo interno.

Il meccanismo di aggiornamento delle APT utilizza come valore di probabilità l’inverso della popolarità di un topic e per ottenere questo dato ci si basa su di un size estimation service, la cui implementazione non è fornita direttamente da TERA ma vengono suggeriti alcuni algoritmi per la sua realizzazione come quelli disponibili in [13],[11] o [15].

Tutte queste metodologie introducono sicuramente un certo margine di errore fisiologico nella stima della popolarità dovu- to alla difficoltà in un sistema distribuito e dinamico di contare oggetti; come primo passo quindi vogliamo analizzare quale è l’impatto di questa imprecisione sull’uniformità della distribuzione. Anzichè utilizzare la popolarità reale adopereremo un valore leggermente deviato attraverso l’aggiunta di rumore stocastico alla quantità esatta, in questo modo si può simulare l’imprecisione dovuta alla stima della popolarità.

La simulazione effettuata ( Figura6) dimostra la presenza di una variazione del comportamento del sistema rispetto a quello ottimale anche se non di grande entità. La distribuzione risultante presenta due zone di uniformità, una costituita dai topic che hanno popolarità singola ( dal topic 184 in poi ) ed un’altra zona che presenta topic con frequenza maggiore di uno ( fino al topic 183).

Sebbene in generale nei sistemi reali non ci si aspetta mai di trovare un comportamento ideale, questa variazione tra le due distribuzioni, seppure non molto consistente, è esemplifi- cativa della sensibilità che dimostra TERA alla variazione della popolarità rispetto a quella reale.

Ci aspettiamo quindi che se c’è stato un tale scostamento tra distribuzione reale e ideale, nel momento in cui introdurremo nel sistema dei nodi con una condotta studiata per causare danni, lo scostamento sarà ancora maggiore e potrebbe essere tale da rendere il tutto inutilizzabile.