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 gene-rali 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 è
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 decisio-ne 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 de-ve essere usato da ogni generale fedele come valore di v(i)
Per poter rispettare la condizione (1) alcuni generali dovran-no 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
16 modelli di guasto e comportamento bizantino
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 innanzitutsegui-to 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 posso-no 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 partico-lare 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 in-put, 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;
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 campio-ne randomico dei nodi appartecampio-nenti 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 indi-pendente 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 pro-cesso malizioso possa riuscire a riempire la local view di un al-tro 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: operazio-ni 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
18 modelli di guasto e comportamento bizantino
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].