Modèle Byzantine Altruistic Rational

Le modèle Byzantine Altruistic Rational (qui signifie en Anglais « byzantin, altruiste, rationnel », plus communément appelé modèle BAR) est un modèle mathématique de sécurité informatique, utilisé dans les systèmes distribués afin de servir de protocole de détection d’erreur (à la manière des généraux byzantins). Actuellement il est principalement utilisé dans les systèmes peer-to-peer.

Le problème des généraux byzantins est une métaphore qui traite de remise en cause de la fiabilité des transmissions et de l'intégrité des interlocuteurs. La question est de savoir comment, et dans quelle mesure, il est possible de prendre en compte une information dont la source ou le canal de transmission est suspect. La solution implique l'établissement d'un algorithme (d'une stratégie) adapté.

Le problème des généraux byzantins

Détecter une erreur dans un système distribué selon le modèle BAR est lié au problème des généraux byzantins.

Pour comprendre ce problème, il faut imaginer une ville assiégée par une armée byzantine. Cette armée est divisée en plusieurs sections qui se sont installées autour de la ville. Chaque section est commandée par son propre général. Les généraux communiquent entre eux par l'intermédiaire de messagers afin de définir un plan d'action. Cependant, il est possible qu'il y ait des traitres parmi les généraux dont le but est d'empêcher les généraux de parvenir à un accord. Il faut donc que les généraux parviennent à se mettre d'accord sur un même plan d'action et que ce soit un bon plan.

Une méthodologie est donc défini entre les généraux pour parvenir à cet accord en respectant ses deux conditions :

1. Accord sur le même plan d'action;
2. Choix d'un bon plan d'action.

Ainsi chaque général va prendre une décision et l'envoyer aux autres. Ensuite chaque général rassemble, selon un principe défini entre eux, les décisions afin d'obtenir une décision finale. On peut prendre l'exemple d'un choix entre deux décisions (attaquer ou prendre la retraite). Chaque général fait son choix, l'envoie aux autres et collecte les décisions des autres. Le choix le plus plébiscité sera celui qui sera retenu. Il s'agit tout simplement d'un vote.

Bien que cette solution paraisse efficace, elle souffre d'un sérieux problème. Rien n'empêche un traitre d'envoyer des choix différents à chaque général. Une nouvelle condition est donc que deux généraux loyaux doivent avoir la même décision de la part d'un autre général. Ce qui invite à voir le problème sous l'angle d'un général qui envoie sa décision aux autres. On le distinguera des autres en le nommant commandant général et en appelant les autres, des lieutenants généraux.

Le problème des généraux byzantins s'énonce ainsi : Un commandant général doit envoyer un ordre à ces lieutenants généraux de telle manière que :

1. Tous les lieutenants généraux loyaux obéissent au même ordre ;
2. Si le commandant général est loyal alors chaque lieutenant général loyal obéit à l'ordre qu'il envoie;

Principe

En informatique, le modèle BAR est utilisé pour garantir le fonctionnement d’un système distribué composé de multiples domaines d’administration. Typiquement, des grilles de calculs réparties géographiquement. Chaque site possède donc son (ses) propre(s) administrateur(s). Une grille de calculs est composée de plusieurs nœuds, chaque nœud appartenant à un domaine d’administration. Un domaine d’administration est composé de plusieurs nœuds de calculs.

Afin de garantir le fonctionnement de la grille dans sa totalité, plusieurs hypothèses peuvent être faites:

• Un nœud ne se conforme pas nécessairement au protocole utilisé par la grille;
• Les actions effectuées par un nœud ne sont faites que dans son propre intérêt;
• Un nœud peut être défaillant (soit mal configuré, soit compromis).

C’est donc dans un cas comme celui-là que le modèle BAR permet de résoudre chacun de ces points. En effet, grâce à ce modèle, un nœud peut-être classifié en l’une des 3 catégories que représentent le modèle BAR, à savoir :

• Altruistic : le nœud est considéré comme un nœud suivant le protocole utilisé de manière exacte;
• Rational : le nœud n’est intéressé que par l’optimisation de l’utilisation de ses ressources. Il ne déviera du protocole utilisé que si celui-ci estime qu’à cause du protocole utilisé ses performances diminuent;
• Byzantine : le nœud ne suit pas le protocole utilisé, soit parce qu’il est compromis, soit parce qu’il est mal configuré ou parce qu’il suit une fonction d’optimisation de ses ressources qui n’est pas la même qu’un nœud rationnel.

Le modèle BAR est implémenté par plusieurs protocoles : Par exemple le protocole Incentive-Compatible Byzantine Fault Tolerant (IC-BFT), Byzantine Altruistic Rational Tolerant (BART)

• Incentive-Compatible Byzantine Fault Tolerant (IC-BFT) protocol : On parle de protocole IC-BFT si l'ensemble des propriétés de sûretés et de vivacités est garanti et si le meilleur intérêt des nœuds est de suivre le protocole.
• Byzantine Altruistic Rational Tolerant (BART) protocol: On parle de protocole BART si l'ensemble des propriétés de sûretés et de vivacités est garanti malgré toutes les déviations rationnelles du protocole qui ont lieu.

Exemple d'utilisation du modèle

BAR-B

BAR-B est un système coopératif de sauvegarde dans lequel les nœuds d'un système distribué contribuent de manière égale au stockage.

Architecture mise en place

L'architecture contient 3 niveaux :

1. Le premier niveau concerne les primitives;
2. Le second niveau concerne la régulation du travail;
3. Le troisième niveau concerne l'application en elle-même.

Le premier niveau, les primitives de bases, fournissent les fonctions clés afin de construire un système distribué fiable. Il repose sur le protocole IC-BFT.

Le second niveau, la régulation du travail, permet de construire un système qui ne donnera le travail déterminé qu’à un nœud au lieu de le faire exécuté par un ensemble de nœuds. La régulation du travail est effectuée grâce à un protocole dit Garantee Response protocole, qui permet de vérifier la correspondance requête-réponse.

Le troisième niveau, le niveau applicatif, implémente le service désiré en utilisant les couches de plus bas niveau.

Un des principaux problèmes est donc le fait qu’un nœud puisse agir contre l'intérêt des autres. Mais s'il est possible d’identifier le nœud et de mesurer ce qu’il effectue, ceux-ci seront plus enclin à agir de manière rationnelle.

Fonctionnement du service

BAR-B est un système coopératif de sauvegarde dans lequel les nœuds d'un système distribué contribuent de manière égale au stockage. Dans des circonstances normales, les nœuds interagissent avec BAR-B à travers trois opérations: stocker, récupérer et auditer.

Pour stocker un fichier de sauvegarde, le propriétaire le comprime et le divise en petits morceaux qui sont ensuite chiffrés. Ensuite il les envoie aux différents nœuds pour le stockage sur le système. Ces différents nœuds envoient un accusé de réception signé (Le nœud est donc identifié). Le propriétaire conserve les accusés et les nœuds gardent les infos de stockage (morceaux stockés).

Lorsque le propriétaire a besoin de récupérer un fichier, il envoie une demande de récupération à chaque nœud détenant un morceau. La demande contient l'accusé, de sorte que le nœud a trois options:

1. Envoyer le morceau;
2. Dire que la bail de stockage pour le morceau a expiré;
3. Dire qu'il a des informations de stockage plus récentes en ce qui concerne le morceau.

S'il y a une autre réponse, cela veut dire que le nœud a abandonné prématurément les données qui lui ont été confiées et ce nœud doit être puni. Les accusés sont des documents permettant un audit. Les nœuds échangent de manière périodique les accusés afin de vérifier qu'un nœud ne dépasse pas son quota de stockage.

BAR Gossip

Un autre exemple reprend le problème de retransmettre en direct sur internet un évènement où les membres de l'audience nommé clients, contribuent dans la diffusion des paquets de la transmission.

Acteurs

Ces clients peuvent être byzantins, altruiste ou rationnel.

Chaque client rationnel a pour stratégie la maximisation de son utilité. Un tel client dérivera du protocole que si cela augmente son utilité.

Les clients altruistes suivent le protocole peu importe le coût. Dans cet exemple, le coût est l'envoi et la réception de paquets.

Les clients byzantins fonctionnent arbitrairement ou selon des procédures non déterminées.

Les clients non-byzantins maintiennent un système d'horloge entre eux qui est synchronisé en secondes. Ils communiquent en point à point de manière synchrone et en utilisant des connexions non fiable UDP et TCP. Si un nœud ne reçoit pas un paquet attendu, il considère que le lien n'est plus valide.

Il est supposé que les clients doivent souscrire au direct avant son début et qu'un client non-byzantin reste pendant toute la diffusion.

Fonctionnement

C. Li propose un protocole pour réaliser ce projet : BAR Gossip. Ce protocole fait mention d'un broadcaster altruiste qui diffuse l'évènement en direct à tout un ensemble de clients. Cette diffusion en direct demande que deux propriétés soient garanties :

1. Les clients non-byzantins ne fournissent que des paquets authentiques, CAD, que des paquets générés par le broadcaster;
2. Chaque client altruiste reçoit une grande partie de tous les paquets de diffusion en un certain temps.

La première condition peut être garantie quelle que soit la situation. Par contre, la deuxième n'est certaine que dans de bonnes conditions et avec un nombre limité de clients byzantins.

Avant de commencer la diffusion, tous les clients doivent générer une clé privée et une clé publique. Ensuite ils s'inscrivent à l'évènement en donnant les deux clés au broadcaster. Ce dernier peut ainsi vérifier les clés et accepter l'inscription. Après collecte des clés, le broadcaster met à disposition des clients une liste avec l'identité de chaque client, son adresse et sa clé publique. Les clients vont chiffrer les messages du protocole à l'aide de leur clé privée. Ce système permet que chaque message soit authentifié, intègre et que son contenu ne puisse pas être répudié par son envoyeur.

Pendant le direct, le broadcaster est chargé de diviser les données en morceaux de taille fixe.

Le protocole fonctionne selon un système de tour d'une durée T + $\delta$ pendant lequel le broadcaster envoie les morceaux et que ces morceaux sont échangés entre les clients. T est un laps de temps pour l'échange de message requis par le protocole.

Le premier tour commence quand le direct commence. Chaque morceau expire à la fin du tour dans lequel le broadcaster l'a envoyé. Quand un morceau expire, tous les clients qui le possède, doivent le fournir aux lecteurs média.

À chaque tour, le broadcaster choisit un sous-ensemble de clients. Ces clients sont choisis de manière aléatoire. Ils reçoivent les morceaux, les signent et les distribuent aux autres clients. Le nombre de clients choisi aléatoirement doit être assez grand pour garantir qu'au moins un destinataire soit un client non-byzantin.

Un client ne recevra pas tous les morceaux directement du broadcaster. Il va devoir faire des échanges avec les autres clients. Pour cela, il utilise deux systèmes d'échange :

• Échange équilibré;
• Don optimiste.

L'échange équilibré demande que le même nombre de morceaux soient échangés entre deux clients. Ainsi, si un client c1 donne trois morceaux à un client c2, c2 en donnera lui aussi trois à c1. Dans un autre cas de figure, c1 pourrait proposer de donner cinq morceaux à c2 à alors que c2 ne sait en donner que quatre. Dans ce cas-là, c1 et c2 échangeront quatre morceaux. Un client rationnel va suivre ce protocole car s'il essaye de dévier du protocole, cela n'augmentera pas son utilité. Cependant si un client a des soucis pour obtenir ses morceaux (par exemple, à la suite de problèmes de réseaux), il aura moins à offrir et va accumuler du retard. C'est pour cela qu'il y a l'autre système d'échange : don optimiste. C'est un système optimiste car un client va distribuer les morceaux à un autre client qui en demande, sans être certain d'un retour de faveur. Ce cas permet d'effectuer un échange non équilibré.

Annexes

Bibliographie

• (en) Leslie Lamport, Robert Shostak et Marshall Pease, « The Byzantine Generals Problem », ACM Transactions on Programming Languages and Systems,‎ juillet 1982, p. 382-401 (DOI 10.1145/357172.357176)
• (en) Amitanand S. Aiyer, Lorenzo Alvisi, Mike Dahlin, Allen Clement, Jean-Philippe Martin et Carl Porth, « BAR fault tolerance for cooperative service », Proceedings of the twentieth ACM symposium on Operating systems principles,‎ décembre 2005, p. 45-68 (ISBN 1-59593-079-5)
• (en) Harry C. Li, Allen Clement, Edmund L. Wong, Jeff Napper, Indrajit Roy, Lorenzo Alvisi et Michael Dahlin, « BAR gossip », Proceedings of the 7th symposium on Operating systems design and implementation,‎ 2006 (ISBN 1-931971-47-1)

Lectures complémentaires

• (en) Zhao Wenbing et F.E. Villaseca, « Byzantine Fault Tolerance for Electric Power Grid Monitoring and Control », International Conferesnce on Embedded Software and System,‎ juillet 2008, p. 129-135 (ISBN 978-0-7695-3287-5)
• (en) Zhao Wenbing, « Byzantine Fault Tolerance for Nondeterministic Applications », Third IEEE International Symposium on Dependable, Autonomic and Secure Computing,‎ septembre 2007, p. 108-115 (ISBN 978-0-7695-2985-1)
• (en) J. Nakamura, T. Araragi et S. Masuyama, « Acceleration of Byzantine Fault Tolerance by Parallelizing Consensuses », International Conference on Parallel and Distributed Computing, Applications and Technologies,‎ décembre 2009, p. 80-87 (ISBN 978-0-7695-3914-0)
• (en) Xiu-Qun Wang, Yue-Ting Zhuang et Hong-Lun Hou, « Byzantine Fault Tolerance in MDS of Grid System », International Conference on Machine Learning and Cybernetics,‎ augustus 2006, p. 2782-2787 (ISBN 1-4244-0061-9)
• (en) Zhao Wenbing et Zhang Honglei, « Byzantine Fault Tolerant Coordination for Web Services Business Activities », International Conference on Services Computing,‎ juillet 2008, p. 407-414 (ISBN 978-0-7695-3283-7)