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 riflette-re su quali possono esseriflette-re gli effetti di un comportamento arbi-trario 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 è costi-tuito. 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 ma-niera permanente o temporanea informazioni utili
all’al-2.3 modello per analisi di comportamenti bizantini 19 goritmo. L’interesse su queste strutture si pone nel mo-mento in cui influenzano il comportamo-mento 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 capiespande-re quale è l’in-fluenza di un componente sul comportamento generale, alcune strutture dati possono inoltre essere ignorate nel momento in cui il loro contenuto dipende totalmente dai messaggi scambia-ti, 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 mes-saggio è solo inviato senza ricezione di un mesmes-saggio 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 operazio-ne di comunicaziooperazio-ne:
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 protocol-lo. In alcune situazioni questo comportamento non crea alcun problema magari perchè si uti-lizzano delle tecniche di ridon-danza, mentre in altre posso-no causare seri problemi, spe-cialmente quando l’omissione è non è sistematica ma sporadi-ca e quindi anche molto difficile da riconoscere.
20 modelli di guasto e comportamento bizantino
Tabella 1: continua dalla pagina precedente
Tipologia Effetto
creazione arbitraria Iniettare nel sistema dei mes-saggi potrebbe consentire ad un nodo di influenzare il compor-tamento di un altro inviandogli messaggi che lo indurrebbero a compiere una azione non lega-le, oppure una azione legale in grado di destabilizzare il nor-male comportamento. Può es-sere 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 è possi-bile impersonificarne un altro o meno.
modifica frequenza invio La modifica della frequenza può causare problemi più o me-no gravi a seconda della sensi-bilità di una operazione al fat-tore temporale. L’incremento della frequenza di invio tra l’al-tro 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 con-tenuto rispetto ai normali dati che dovrebbero essere presenti.
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 distri-buito 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 co-municazione. 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 è neces-sario non inserire nell’elenco tutte quelle che TERA utilizza ma che in realtà non sono parte del sistema, ci riferiamo in parti-colare 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 par-ti del sistema publish/subscribe come il Parpar-tipar-tion Merging e l’operazione di sottoscrizione di un topic poiché in realtà que-ste si basano interamente sull’operazione di Access Point Table Lookup già elencata.
22 modelli di guasto e comportamento bizantino
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 in-serire 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 in-vio 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, que-sta omissione lo danneggia ulteriormente causando una riduzione drastica della probabilità di ottenere una notifi-ca di pubblinotifi-cazione non essendo l’informazione distribui-ta all’interno delle APT degli altri nodi. La possibilità di ricevere una sottoscrizione rimane ancora se un nodo, ef-fettuando una Access Point Lookup, riuscisse ad incontra-re l’unico sottoscrittoincontra-re 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
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 contem-poraneamente.
Questo tipo di messaggio è costituito da un elenco di to-pic 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 ca-so 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 punfunzionamen-to di forza e di debolezza. L’inserimento nelle APT di un to-pic 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 de-terminata 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 prossiTrattere-mo capitolo3.
• alterazione topic Il caso di interesse è quello in cui viene inserito un topic che non è stato realmente sot-toscritto. Lo scopo di questa operazione potrebbe es-sere 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 messag-gio contraffatto, è interrogato tramite una richiesta di APT lookup, questo risponderà inviando un riferi-mento 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 sot-toscrizione che di pubblicazione di altri hosts essen-do la lookup una azione fondamentale del sistema,
24 modelli di guasto e comportamento bizantino
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 rie-sca a redirigere una gran parte dell’insieme delle comunicazio-ni 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 pro-babilistico 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 comu-nicazioni 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 in-viare un advertising contenente i topic precedentemente catturati e quindi inseriti con alta probabilità nella APT della vittima.
• se non è possibile guardare all’interno delle comunicazio-ni allora l’ucomunicazio-nico modo per poter reperire informaziocomunicazio-ni è attraverso l’attesa di:
1. messaggi di advertsing - ottenendo informazioni su quali sono le sottoscrizioni effettuate dal nodo vitti-ma
2. operazioni di lookup - ottenendo informazioni su quali sono i topic che il nodo vittima non contiene nella propria Access Point Table
2.4 minacce in tera 25 Entrambi i messaggi non rivelano espressamente cosa contie-ne la APT di un nodo scelto come vittima, ma danno informa-zioni 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 potrebbe-ro 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 dif-ferenza tra i due insiemi di dati ottenendo così una collezione di topic che con una certa probabilità potrebbero essere pre-senti all’interno della APT del nodo vittima. A questo punto i nodi bizantini potrebbero generare un messaggio di adverti-sing 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 ab-bia 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 percor-so scelto è puramente randomico e quindi la probabilità di ot-tenere 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.
26 modelli di guasto e comportamento bizantino
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 que-st’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, op-pure causerebbe una partizione nella topic overlay se il tut-to avesse avutut-to origine da una richiesta di sottut-toscrizione: 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: que-sta operazione è comunque pesante dal punto di vique-sta 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 so-lamente le informazioni che identificano il topic di interes-se per il mittente mentre il interes-secondo contiene informazioni circa il riferimento all’access point per il topic richiesto. Prendiamo in considerazione il messaggio di inoltro del-la 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 di-stribuito a rilasciare in buona fede informazioni sul topic sbagliato. Nel caso in cui l’alterazione avvenisse a livel-lo del messaggio di risposta ci sarebbe l’opportunità di
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’ul-timo 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 comunicazio-ne 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 ulte-riori 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 richie-sta di pubblicazione sia come mancato invio del messag-gio 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 imple-mentazione non si delega alcun nodo all’invio del mes-saggio 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.
28 modelli di guasto e comportamento bizantino
modifica frequenza invio/creazione arbitraria Questo tipo di operazione viene effettuata solamente quando esi-ste una informazione da pubblicare quindi una maggio-re fmaggio-requenza di invio potmaggio-rebbe essemaggio-re causata solamente da una generazione arbitraria dei messaggi. Oltre ad un possibile effetto di saturazione delle risorse questa alte-razione non ha effetti particolari sul funzionamento del sistema quanto sul possibile fenomeno di spamming che si verrebbe a creare. La presenza di messaggi con conte-nuto 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