Système de réputation en présence de fournisseurs honnêtes

Un système de réputation met en jeu des participants appelés agents. Un agent peut être soit un fournisseur de service, soit un client. Un fournisseur de service, noté FS dans la suite, fournit un service, par un exemple un bien dans le cas d’un système de commerce électronique ou un fichier dans un réseau P2P de transfert de fichiers. Ces fournisseurs sont contactés par des clients qui utilisent les services proposés. Les clients sont notés p, q, . . . Avant d’interagir avec un fournisseur, un client utilise le système de réputation pour calculer le score de réputation du fournisseur de service, lui permettant ainsi d’estimer le comportement passé de ce fournisseur et de décider si oui ou non il peut inter-agir avec lui sans risque. Une fois que l’interaction est finie, le client émet un témoignage décrivant ce qu’il pense de cette transaction. Les nœuds du réseau stockant les témoignages sont appelés des témoins.

Bien évidemment, les différents agents peuvent être bienveillants ou mal-veillants. Un agent malveillant va par exemple essayer d’augmenter artificiel-lement un score de réputation ou en diminuer un autre.

Lorsqu’un client utilise un système de réputation, il doit effectuer plu-sieurs actions pour obtenir le score de réputation d’un fournisseur de ser-vice. Dans un premier temps, il doit localiser où sont stockés les témoignages concernant les actions passées de ce fournisseur. Si le système est distribué, les témoignages peuvent être répartis dans le réseau. Ceux-ci peuvent-être les agents ayant émis ces témoignages ou d’autres. Le client doit alors déterminer en quels endroits collecter les témoignages, c’est-à-dire localiser les témoins de ce fournisseur. Ensuite, il doit les collecter le plus efficacement possible. Fina-lement, il doit calculer le score de réputation du fournisseur. Ces trois étapes –quatre dans le cas distribué – sont les briques communes à tout système de réputation.

À cet effet, nous proposons une taxonomie des systèmes de réputation sui-vant ces quatre éléments. Nous ferons ensuite le point sur les attaques pos-sibles sur les systèmes de réputation. Finalement, nous présenterons un sys-tème de réputation centralisé respectant la vie privée des participants.

Choisir une architecture centralisée ou distribuée modifie le stockage des informations. En effet, lorsqu’un serveur central est utilisé par tous les clients et fournisseurs de service, toutes les informations peuvent y être stockées.

Par contre, lorsque la conception du système de réputation est distribuée, les témoignages peuvent être stockés par l’agent comme proposé par Ravoaja [28], sous l’hypothèse que celui-ci n’a aucun intérêt à modifier son propre re-tour1. C’est ce qui est proposé dans la plupart des systèmes distribués [20] [25].

En l’absence de serveur central sur lequel l’intégralité des témoignages concernant un fournisseur de service est stockée, il est nécessaire de localiser les témoignages. Comme le réseau est généralement ouvert, il peut y avoir une grande quantité de nœuds sur lesquels les témoignages ont été stockés à l’issue des différentes interactions entre clients et fournisseurs de service. Interroger tous ces nœuds est trop coûteux, c’est pourquoi des schémas de sélection de témoins sont utilisés.

Ravoaja [28] présente plusieurs méthodes de sélection des témoins. La pre-mière, naïve, est une méthode par inondation. Un client cherchant à calculer la réputation de FS demande à chacun de ses voisins à un saut sur le réseau s’il a interagi avec FS. Ces derniers transmettent la requête à leurs propres voi-sins et ainsi de suite, jusqu’à ce que le nombre de sauts maximum (ou Time To Live), donné dans le premier message, soit atteint.

Une première optimisation consiste en l’utilisation de marches aléatoires. Le premier témoin est choisi de manière aléatoire et choisira ensuite un autre témoin aléatoirement parmi ses propres témoins, et ainsi de suite jusqu’à ce que le nombre désiré de témoins soit obtenu.

Une seconde technique possible est celle dite de « recherche par percola-tion ». Pour cette méthode, chaque témoin initie une marche aléatoire de lon-gueur fixée et donne un index pointant sur ses témoignages à chaque agent de la marche aléatoire. Si, à l’instar de Gnutella, le réseau suit une distribu-tion en loi de puissance2, Ravoaja montre qu’au moins un agent ayant une réputation élevée reçoit une copie de l’index si la longueur de la marche est suffisante. Cela permet une propagation très rapide des requêtes et assure aux clients qu’en contactant les agents de score élevé ils auront des pointeurs vers la plupart des témoignages.

1Cette hypothèse paraît néanmoins trompeuse dans le sens où un agent pourrait vouloir se-mer la zizanie entre d’autres agents.

2C’est-à-dire que peu d’agents ont une réputation élevée, tandis que la plupart ont une répu-tation relativement faible.

Enfin, le réseau sous-jacent peut être structuré par une DHT – Distributed Hash Table. Cette structure régit la position des agents et des ressources dans le réseau. Dans le cas de Chord [32], 2N nœuds et ressources du système sont or-ganisés en anneau en fonction du haché d’un identifiant : adresse IP, nom, etc. Chaque nœud ou ressource est identifié par ce haché, qui donne un nombre entre 1 et 2N . Afin de communiquer efficacement avec les autres nœuds, cha-cun d’entre eux possède une table de routage (finger table) lui permettant de communiquer directement avec N autres nœuds : ni peut communiquer avec ni+1 et n i+ 2j pour j ∈ {0, . . . , N − 1}, comme présenté à la figure 2.1 pour N = 6 et 9 nœuds. Si un nœud ne peut être atteint directement, les messages sont transmis de proche en proche.

Dans toute architecture, la manière dont les scores de réputation du ser-veur sont collectés peut varier.

Dans le cas centralisé, il suffit que le serveur donne le score global de ré-putation d’un fournisseur de service à tout agent en faisant la requête. C’est ce qui est fait pour eBay : tout le monde peut voir sur le profil d’un vendeur quel est son score de réputation et quelles sont ses dernières évaluations.

Dans une architecture distribuée, la collecte des témoignages est fortement liée à l’algorithme de stockage des témoignages : par exemple, si les témoi-gnages sont stockés sur les agents les ayant émis, il faut localiser ces agents témoins via une des méthodes présentées précédemment puis les contacter.

Pavlov et al. [25] proposent plusieurs méthodes permettant en outre une collecte anonyme des témoignages. Dans celles-ci, le paramètre n représente le nombre de témoins de FS choisis par p.

Dans la première méthode, p construit un anneau constitué de tous les témoins. Pour calculer le score de réputation d’un fournisseur de service, p fait transiter un nombre qu’il initialise à une valeur aléatoire. Lors de la ré-ception du message, chaque témoin additionne à ce nombre son témoignage sur FS et envoie le résultat au témoin suivant. Lorsque p obtient la somme de toutes les notes, il soustrait la valeur aléatoire initiale pour obtenir un score de réputation de FS – ce score dépendant des témoins choisis. Au total, O(n) messages ont été envoyés entre les agents. Le problème est que deux témoins « entourant » un autre témoin peuvent obtenir le score du témoin entouré. Pour améliorer cela, les auteurs proposent une deuxième méthode.

Dans celle-ci, les témoins sont organisés dans un graphe complet, c’est-à-dire que chacun connaît tous les autres témoins. p choisit ensuite une valeur rp aléatoirement. Chaque témoin va alors séparer son secret – son témoignage sur FS – en n + 1 parties ri,1, . . . , ri,n+1, p étant vu comme le n + 1-ième témoin.

Chacun en envoie ensuite une partie à chaque autre agent, et en conserve une. Lors de la réception du message, chaque agent calcule la somme des valeurs reçues et l’envoie à p. Il somme ces valeurs et soustrait rp de la somme obte-nue. En tout, ce protocole requiert O(n2) messages. Ce protocole améliore la résilience du système face aux agents malveillants.

Le calcul du score de réputation est intimement lié au format des témoi-gnages, et donc à leur propagation ainsi qu’à leur stockage. Jøsang et al. [19] présentent de nombreuses manières de faire ce calcul. Les protocoles que nous avons vu jusqu’à présent font généralement une addition des différents témoi-gnages ou une moyenne. Les auteurs précisent que si ces méthodes de calcul permettent une compréhension de tous, elles ne permettent pas une gestion aussi fine de la réputation qu’on le voudrait : un fournisseur de service ayant reçu 90 témoignages positifs et 10 négatifs aura le même score qu’un autre ayant reçu 80 témoignages positifs. De plus, ces méthodes ne permettent pas de donner plus d’importance à des témoignages émanant d’agents particu-liers.

D’autres méthodes de calculs de scores de réputation permettent de com-bler ce manque, comme le modèle discret décrit par Abdul-Rahman et Hailes [3]. Les auteurs proposent de représenter la confiance d’un agent p en un four-nisseur de service FS par un degré de confiance discret qui ne peut prendre que quatre valeurs : très digne de confiance, digne de confiance, peu digne de confiance et absolument pas digne de confiance. Pour chaque autre agent, p a également une « confiance de recommandation », lui permettant d’accor-der plus d’importance aux témoignages venant de sources sures et de dimi-nuer l’importance des témoignages incertains. Cependant, les auteurs recon-naissent que ce système souffre d’un problème d’initialisation puisqu’un nou-vel agent ne sait pas à quels témoins se fier.

Jøsang [17] décrit un modèle « d’opinion ». Son principe est d’avoir un quadruplet (b, d, u, a) exprimant la croyance de p en une déclaration binaire concernant un fournisseur de service FS comme « FS est digne de confiance ». Soit FS est digne de confiance, soit il ne l’est pas. Cependant il n’est pas pos-sible de déterminer avec certitude si cette déclaration est vraie ou fausse. Un agent fait donc preuve d’une opinion à propos d’une telle déclaration. Cela se traduit par des degrés de conviction ou de méfiance, un dernier paramètre étant nécessaire pour caractériser l’incertitude. Les paramètres b, d et u repré-sentent respectivement la conviction (belief ), la méfiance (disbelief ) et l’incerti-tude (uncertainty), avec b, d, u ∈ [0, 1] | b + d + u = 1. Cette égalité représente le fait que la conviction d’une personne croît en même temps que sa méfiance diminue, c’est-à-dire qu’une personne sûre de l’affirmation d’une déclaration n’est pas méfiante à propos de cette déclaration. Le paramètre u nuance les deux premiers paramètres dans le sens où quelqu’un peut ne pas être sûr ni d’une affirmation, ni de sa négation. Ici, a est un paramètre qui détermine à quel degré l’incertitude contribue au calcul du score de réputation. En ayant une opinion comme « FS est digne de confiance », la réputation de FS sera r = b + u × a

En considérant deux opinions ω1 = (b1, d1, u1, a1) et ω2 = (b2, d2, u2, a 2) à propos d’une même déclaration, on peut obtenir leur somme (c’est-à-dire une

moyenne des deux opinions) ¯ = ( ¯, ¯, ¯, ¯) comme suit : ω b d u a b¯ d¯ u¯ a¯ = (b1u2 + b2u1)/κ = (d1u2 + d2u1)/κ = (u1u2)/κ = (a2u1 + a1u2 − (a1 + a2)u1u2)/(u1 + u2 − 2u1u2) où κ = u1 + u2 − u1u2 et u1, u2 ∈/ {0, 1}. Lorsqu’un agent p recommande un autre agent FS avec l’opinion ω1 = (b1, d1, u1, a1) et que l’opinion de FS à propos d’une déclaration x est ω2 = (b2, d2, u2, a2), l’opinion de p à propos de x via la recommandation de FS est ωR = (bR, dR, uR, aR ) telle que : dR = b1d2bR= b1b2 uR= d1 + u1 + b1u2 aR= a2.

L’auteur nous explique cependant que certaines situations ne peuvent être analysées complètement sans ignorer certains témoignages. En effet, un tel réseau peut être vu comme un graphe orienté où les nœuds sont les agents et les arcs les recommandations. Lorsque deux chemins sont possibles, il faut choisir un unique chemin à prendre en compte, ce qui revient à abandonner certains témoignages. De plus, ce système n’est pas intuitif comme peut l’être une méthode de calcul de réputation additive, et prendre deux témoignages différents en compte est déjà complexe.

Enfin, Jøsang et Ismail [18] décrivent la beta-réputation, un exemple de système bayésien. Ce système suppose que le comportement d’un agent suit une loi de probabilité beta de paramètres a et b inconnus. En effet, un four-nisseur de service réputé peut être vu comme une personne qui se comporte correctement dans la majorité des cas mais à qui il peut arriver des mésaven-tures. Les différents témoignages collectés permettent d’inférer la distribution de probabilité les ayant généré. Les auteurs présentent un système où les re-tours sont soit positifs, soit négatifs, et où le score de réputation est mis à jour à chaque itération avec les nouveaux retours. Le score est représenté sous la forme d’une densité de probabilité de loi beta de paramètre (a, b), où a est le nombre de retours positifs et b celui des retours négatifs :3 beta( p|a, b) = (a + b) pa−1(1 − p)b−1, p ∈ [0, 1] Cette fonction représente un score de réputation en fonction de la probabi-lité qu’un agent l’atteigne. Initialement (c’est-à-dire pour a = b = 1), elle est uniforme. À chaque fois qu’un nouveau témoignage est émis, cette fonction (et donc le comportement estimé) est modifiée. L’espérance mathématique de cette fonction vaut a/(a + b), c’est-à-dire le rapport entre le nombre de témoi-gnages positifs et le nombre de témoignages totaux, ce qui concorde avec une moyenne des témoignages tout en apportant plus de précisions. Ainsi, le com-portement d’un fournisseur de service est modélisé par une variable aléatoire, de densité de probabilité beta( p|a, b).

Le comportement étant modélisé par une variable aléatoire continue, la probabilité que le comportement de FS vaille une note spécifique pour une transaction est infiniment faible. Cependant, la probabilité que le comporte-ment vaille une note comprise dans un certain intervalle de [0, 1] est non nulle.

En effet, P ( p ∈ [ p1, p2]) = p2  f ( p|a, b). La Figure 2.2 présente deux scores de p1 réputation : (a) est le score de réputation – c’est-à-dire la densité de probabi-lité beta – après sept retours positifs et un retour négatif, où on voit que la probabilité que FS se comporte de manière à avoir une note dans l’intervalle [0.6, 0.9] est très grande, tandis que (b) est le score de réputation après deux retours positifs et cinq négatifs, où le comportement de FS a une forte proba-bilité de valoir une note dans l’intervalle [0.2, 0.6].

Les systèmes de réputation sont sensibles à des degrés variables aux at-taques d’agents malveillants qui tentent par tous les moyens possibles de tirer profit des vulnérabilités de ces systèmes. De nombreux articles s’intéressent à ce sujet [9] [11] [16] [19] [22] [25] [28]. En plus des attaques portant sur les mé-canismes des systèmes de réputation, d’autres peuvent exploiter directement le réseau sous-jacent.

Carrara et Hogben [9] présentent de nombreuses attaques ciblant les méca-nismes inhérents aux systèmes de réputation. Certaines ont une portée globale tandis que d’autres sont plus locales. Pour l’attaque de Sybil [11], un attaquant revendique plusieurs identités dans le système, ce qui lui permet de contrô-ler multiples nœuds, augmentant ainsi son influence sur le réseau – il peut poster de nombreux témoignages fallacieux. L’utilisation d’une autorité de démarrage, demandant un coût avant de permettre l’entrée d’un agent dans le système, diminue le risque des attaques de Sybil. Cela peut se faire avec des puzzles calculatoires comme ceux présentés par Borisov [8]. Plusieurs at-taquants peuvent également former une collusion. C’est-à-dire qu’ils mettent en commun leurs ressources et connaissances afin d’obtenir encore plus d’in-formations sur un autre agent ou de modifier la réputation d’un fournisseur de service.
Si jamais la réputation initiale d’un agent est trop élevée, un attaquant peut tromper des clients potentiels, le croyant bienveillant. Au contraire, si la ré-putation initiale est trop faible, les nouveaux arrivants seront découragés et il sera difficile pour un nouveau fournisseur de service d’attirer des clients. C’est le problème d’initialisation.
D’autres attaques sont plus locales, permettant de modifier la réputation d’un fournisseur de service particulier.
Pour l’attaque par blanchiment de réputation, un attaquant réinitialise sa ré-putation lorsqu’il la juge trop faible. Un attaquant peut aussi vouloir filtrer l’ensemble des témoignages concernant un fournisseur pour augmenter la proportion de témoignages favorables et ainsi augmenter sa réputation.
Si un attaquant veut modifier la réputation d’un fournisseur de service
– que ce soit pour l’améliorer ou la diminuer –, il peut également faire du bourrage d’urne, c’est-à-dire émettre de nombreux témoignages fallacieux pour donner l’impression que le fournisseur est soit bienveillant, soit malveillant.
Des attaques visant un algorithme ou une architecture sont également ex-ploitées. Un exemple très connu est celui des « Google bomb » [2]. Cette technique exploitait l’algorithme PageRank utilisé par le moteur de recherche Google, donnant un score au texte source contenant un hyperlien vers une autre page. Plus nombreux sont les sites utilisant un même texte source, plus élevé sera ce score. À partir d’un certain score, la page vers laquelle pointe le lien apparaît dans les résultats lors d’une recherche du texte source, même si ce texte n’apparaît pas dans la page obtenue. En pratique, un attaquant peut utiliser une multitude de sites web et les faire pointer vers un même site (par exemple ❤❡①❛♠♣❧❡✳❝♦♠ ) en utilisant un même texte source (par exemple « ce site est magnifique »). En cherchant « site magnifique » dans Google, le site ❤❡①❛♠♣❧❡✳❝♦♠ apparaîtra dans les résultats même s’il ne contient ni le mot « site », ni le mot « magnifique ». Ce genre de tech-niques est appelé « attaques contre le score de réputation par manipulation des critères d’évaluation ».
Un attaquant peut vouloir médire sur un fournisseur de service en appor-tant des témoignages de mauvaise qualité. Ces attaques par médisance peuvent être amplifiées si l’attaquant peut se créer de nombreuses identitées, par exem-ple grâce à une attaque de Sybil réussie ou via une collusion. Finalement, un attaquant peut également essayer de réfuter une transaction où le fournisseur de service s’est bien comporté pour éviter d’avoir à émettre un témoignage positif.

Comme nous l’avons vu, dans une architecture centralisée, la sécurité du système repose sur la sécurité du serveur central. Si jamais celui-ci est compromis, le fonctionnement du système le sera aussi. C’est donc un point unique de défaillance. C’est ce fait qui nous motive à considérer un système distri-bué. Cependant, un système distribué est plus compliqué à mettre en place qu’un système centralisé du fait de l’absence de serveur central. Urdaneta et al. [35] présente les principales attaques possibles sur les réseaux sous-jacents, au nombre de trois : attaque de Sybil, attaque d’éclipse et attaque sur le rou-tage :
L’attaque de Sybil, dont nous avons parlé précédemment, permet à un at-taquant de contrôler plusieurs nœuds du réseau. Dans un réseau, cela lui per-met par exemple de router un paquet où bon lui semble.
L’attaque d’éclipse corrompt la table de routage d’un nœud honnête pour s’assurer que les paquets passeront par un nœud contrôlé. Le nœud honnête est alors « éclipsé » puisque la plupart de ses communications peuvent être modifiées par un autre nœud.
Les attaques de routage consistent principalement à ne pas retransmettre ou à modifier les requêtes. Leur impact est augmenté si elles sont combinées avec des attaques de Sybil et d’éclipse.
La plupart des solutions aux attaques d’éclipse et de routage ou de sto-ckage présentées [28] [30] [31] [35] font intervenir des chemins multiples, afin de réduire les problèmes concernant le réseau sous-jacent. En effet, Chord est déjà robuste de par sa construction, et sa robustesse peut être améliorée pour tolérer plus d’attaques comme le montrent Artigas et al. [6] et Fiat et al. [14]. Augmenter le nombre de chemins augmente cette robustesse.
Un autre problème qui se pose lors de communications dans un réseau distribué est celui de la gestion des identités. En effet, il est parfois nécessaire d’être sûr de l’identité de l’agent avec lequel il communique. Marti et Garcia-Molina [22] proposent à cet effet des techniques de clé publique/privée pour éviter le vol d’identité. Néanmons, ce système n’est fiable que s’il existe une tierce partie de confiance, un serveur centralisé faisant office de CA (Certificate Authority) et générant des certificats sur les clés publiques.

Il y a déjà eu des tentatives de systèmes de réputation centralisés proté-geant la vie privée. À notre connaissance, le seul système prouvé préservant l’anonymat de ses utilisateurs est le système proposé par Androulaki et al. [5]. L’objectif de ce système est de fournir une architecture de commerce élec-tronique préservant la vie privée. L’architecture repose sur la présence d’une banque, agent central chargé de lier les identités des agents et leur réputa-tion. La réputation d’un agent est matérialisée par des jetons, qui peuvent être regroupés dans des portefeuilles pour constituer la monnaie d’échange. Ils sont appelés repcoin, pour Reputation Coin. Plus un agent possède de repcoin, meilleure est sa réputation. Ils jouent donc un double rôle, à la fois de mon-naie et de points de réputation. Afin de garantir leur anonymat, les agents discutent entre eux via des pseudonymes, tandis qu’ils utilisent leur identité réelle pour communiquer avec la banque.
Ce système repose sur un réseau de communication anonyme, par exem-ple un routage en oignon comme celui présenté par Syverson et al. [34]. Le principe de ce type de routage est d’éviter toute traçabilité entre la source d’un message et son destinaire. Ainsi, au lieu de se connecter directement à un utilisateur distant, un utilisateur du routage en oignon utilise plusieurs intermédiaires successifs afin d’éviter que quiconque puisse détecter l’interac-tion entre les deux utilisateurs. Les auteurs supposent également que chaque agent possède un nombre limité de repcoin et ne peuvent donc en donner qu’une quantité finie par unité de temps. Cette limite peut être représentée par une cotisation journalière ou hebdomadaire nécessaire pour participer au système. De plus, n’importe quel nombre d’agents peut conspirer (y compris la banque) pour révéler l’identité d’un autre agent.
La banque gère toutes ces informations en utilisant des paires de clés concer-nant les identités. Elle utilise également trois bases de données, la première concernant les quotas de repcoin (utilisés pour incrémenter automatiquement le solde), la seconde gérant les scores de réputation, c’est-à-dire le solde de repcoin, tandis que la dernière conserve un historique des transactions. Ce système de réputation assure les propriétés présentées ci-dessous.
Conformité Lorsqu’un agent honnête U1 demande à retirer des repcoin à une banque honnête B et qu’il en a assez, il n’y aura pas de message d’erreur ; s’il donne une repcoin issue de ce retrait à un autre agent honnête U2, U2 l’acceptera ; si U2 dépose cette repcoin dans une banque honnête, alors sa réputation sera incrémentée. Quand un agent honnête demande une confirmation d’identité (pour laquelle il est éligible) à une banque honnête, il aura une identité valide. Impossibilité de faire une liaison identité – pseudonyme Pour un attaquant qui peut avoir corrompu certaines parties (y compris la banque), il n’y a pas d’autre moyen que de supposer aléatoirement qu’un pseudonyme et une identité (ou deux pseudonymes) sont liés.
Pas de sur-attribution Aucun ensemble d’agent ne peut attribuer plus de rep-coin qu’ils n’en ont retiré.
Disculpation Aucune coalition d’agents ne peut forger une preuve qu’un agent honnête a dépensé deux fois la même repcoin.
Inforgeabilité de la réputation Aucune coalition d’agents de réputation au plus l ne peut montrer une réputation plus grande que l pour un de ses pseudonymes.
La figure 2.3 présente le protocole d’attribution de protocole. À gauche, l’utilisateur U donne des repcoin à M, et à droite M prouve à U qu’il a assez de réputation.
Pour retirer et attribuer des repcoin, le protocole est le suivant :
1. l’utilisateur U retire un portefeuille W de la banque B comprenant un certain nombre de repcoin ;
2. U donne une repcoin les pseudonymes PU (S, π) de son portefeuille à M ; l’échange se fait via et PM ;
3. PM dépose la repcoin (S, π) à la banque ;
4. PM obtient une permission aveugle σ de la banque, visible uniquement par M ;
5. finalement, M dépose σ à la banque, et B augmente le score de réputa-tion de M.