La première nécessité pour ColBack est de découvrir l'espace de stockage à disposition dans son environnement, puis d'obtenir l'allocation d'espace sur le support de stockage d'un tiers pour y stocker tout ou partie des données à sauvegarder. Compte-tenu des scénarios envisagés en termes de connectivité du dispositif, allant d'un accès permanent à une infrastructure jusqu'à une communication uniquement en mode ad hoc, plusieurs critères vont influencer le choix de la méthode de découverte et d'allocation de ressources :

• le coût de la communication, qui correspond à la quantité d'énergie requise et au nombre de sauts nécessaires pour atteindre un nœud dans le cas d'un réseau ad hoc ; lorsqu'un accès direct à Internet est disponible, ce coût est indépendant de la distance séparant deux nœuds ; de même la quantité d'énergie requise pour la communication n'est pas un critère déterminant pour des dispositifs branchés sur le secteur ;
• la densité de l'environnement dans lequel évolue le dispositif mobile, c'est-à-dire le nombre de nœuds avec lesquels peut communiquer un nœud influence la probabilité de trouver de l'espace de stockage à proximité ;
• la volatilité des connexions (déconnexions fréquentes et parfois permanentes dans le cas d'un réseau ad hoc, ou au contraire connexions stables et quasi permanentes entre deux nœuds communiquant directement via une infrastructure) influence la granularité des fragments à sauvegarder.

Ces critères permettront de définir différentes stratégies de découverte et d'allocation de ressources suivant les scénarios considérés.

Comme nous l'avons vu en introduction, chaque propriétaire sauvegarde ses données par fragments, au gré des rencontres qu'il fait avec des contributeurs. De ce fait, la principale difficulté de ColBack est de pouvoir recouvrer les données sauvegardées. Nous faisons l'hypothèse que, dans la plupart des scénarios, chaque participant aura accès de manière intermittente à Internet et qu'il pourra attendre ces moments pour récupérer ses propres données si nécessaire (rôle du propriétaire), ou en profiter pour mettre à disposition les données qu'il a lui-même stockées (rôle du contributeur). Une autre possibilité est que les participants n'aient jamais accès à Internet et n'établissent des connexions entre eux qu'au travers d'un réseau ad hoc. Dans [15], nous envisageons deux approches au recouvrement des données :

• l'approche pro-active (ou push), où le contributeur, dès qu'il a accès à Internet, envoie les données à leur propriétaire dans une "boîte aux lettres" prédéterminée ;
• l'approche réactive (ou pull), où le propriétaire va interroger le réseau de participants ; cette recherche pourrait se faire par mots clef ou méta données tels que "l'ensemble des données que j'ai sauvegardées jeudi matin".

L'approche réactive paraît adaptée surtout à des réseaux de petite échelle. Nous reviendrons dans la section 3 sur les solutions permettant de mettre en œuvre la boîte aux lettres dont il est question dans la première approche.

Le service de sauvegarde doit fournir la garantie que les données restaurées par un participant sont cohérentes et intègres. Toute corruption de données sauvegardées, qu'elle soit intentionnelle ou non (par exemple due à une faute logicielle ou matérielle sur la machine stockant les données), doit pouvoir être détectée par son propriétaire lors de la restauration.

Les protocoles réseau et les supports de stockage utilisent largement des codes détecteurs d'erreur ou correcteurs d'erreur pour tolérer les fautes matérielles ou logicielles. Pour résister aux corruptions intentionnelles, il est cependant nécessaire de garantir également l'authenticité des données : le ou les propriétaires des données doivent être sûrs qu'il s'agit bien des données qu'ils ont sauvegardées. Nous présenterons en section 3.3.1 des techniques permettant d'atteindre cet objectif.

Comme nous l'avons vu, les participants au service de sauvegarde coopérative sont amenés à stocker leurs données sur les machines d'autres participants en lesquels ils n'ont aucune relation de confiance a priori. Les informations sauvegardées peuvent être sensibles et, en tant que telles, ne doivent pas pouvoir être exploitées par celui qui les stocke. La technique de fragmentation, redondance, dissémination ou FRD [10] permet précisément de garantir la confidentialité des données. Les données sont découpées en fragments puis dispersées entre différents sites de stockage de telle sorte qu'aucun site de stockage n'ait d'information sur l'origine des fragments qu'il stocke. Les données, ou leurs fragments, peuvent être chiffrés pour en améliorer la confidentialité. Bien entendu, cette fragmentation complique le recouvrement des données sauvegardées (section 2.1.2). Nous reviendrons en section 3 sur la mise en œuvre de telles techniques.

La technique de FRD a en outre l'avantage de convenir à nos hypothèses de départ : compte-tenu des interactions éphémères entre systèmes mobiles, les données doivent nécessairement être fragmentées ; de plus, la mobilité entraînera de fait une dissémination des données.

Il y a deux manières d'aborder la question de la disponibilité des données sauvegardées. Du point de vue du contributeur se pose la question du choix des données qu'il devra tôt ou tard effacer pour libérer son espace de stockage. Du point de vue du propriétaire, il s'agira d'avoir une assurance dans sa capacité à restaurer ses données ultérieurement. Enfin, la disponibilité des données ne doit pas être mise en danger par des malveillances tel que des attaques en déni de service.

Choix des données à effacer. Malgré l'utilisation d'algorithmes visant à optimiser l'utilisation de l'espace de stockage, il sera très vite nécessaire pour chaque participant d'effacer certaines données. Le mécanisme qui permettra de décider des données à effacer n'est cependant pas évident compte tenu de la contradiction entre les deux hypothèses suivantes :

1. celui le plus à même de savoir quelle version sauvegardée peut être effacée est le propriétaire des données lui-même ;
2. les participants peuvent être déconnectés et il n'existe a priori aucune relation de confiance entre eux.

La première hypothèse nous donne à penser que le propriétaire des données sauvegardées devrait choisir lui-même la version de ses données à effacer : il peut s'agir simplement de la plus vieille sauvegarde, ou bien d'une version plus récente mais moins importante à ses yeux parce qu'elle ne représente pas une étape importante de son travail [27]. Cependant, d'après la deuxième hypothèse formulée, un contributeur (i) ne peut pas compter sur le propriétaire des données pour le prévenir de leur péremption et (ii) ne souhaitera pas dépenser d'énergie pour essayer de reprendre contact avec les propriétaires des données qu'il stocke.

Par conséquent, les participants doivent prévoir la possibilité d'une prise de décision unilatérale d'effacer des données si, par exemple, l'utilisateur des ressources n'a pas pris contact avec le contributeur depuis un certain temps. Une sémantique précise des obligations mutuelles devra donc être définie et nous en verrons des exemples dans la section 3.3.3.

Parmi les systèmes étudiés, on retrouve deux principales approches à la répartition des blocs de données à sauvegarder :

• stockage réparti au sein de groupes particuliers de participants ou partenaires ;
• stockage réparti entre tous les participants au moyen d'une table de hachage répartie (ou DHT) qui a pour propriété de répartir de manière homogène toutes les données sauvegardées.

Dans le premier cas, les relations entre partenaires sont assez simples : chaque participant choisit, à son entrée, un ensemble de partenaires puis leur envoie directement, à chaque sauvegarde, ses données. Le système proposé par Elnikety et al. se contente d'envoyer à intervalle régulier l'ensemble des données à sauvegarder. Les autres systèmes, quant à eux, choisissent les données à transmettre en fonction des versions précédemment sauvegardées. Dans Pastiche, chaque participant choisi également un ensemble de partenaires qui ne changera pas ou peu par la suite. Enfin, les dispositifs participant à FlashBack, au sein d'un PAN, choisissent en priorité pour partenaires les dispositifs qui sont le plus souvent à proximité.

La deuxième approche repose sur une technique fondamentale des réseaux de partage des données pair-à-pair, les "réseaux virtuels" ou overlay networks, abondamment décrits dans la littérature [26]. Une DHT [25] est un mécanisme de stockage réparti de blocs de données basé sur un réseau virtuel. Chaque nœud du réseau est responsable des blocs dont l'identifiant est proche (numériquement) de son identifiant. Les blocs sont donc répartis de manière homogène dans la DHT si leurs identifiants sont bien répartis. Venti-DHash et pStore suivent cette approche.

L'utilisation d'une DHT pour stocker les données sauvegardées a deux inconvénients :

• le coût de la migration des données lors de l'entrée ou du départ d'un participant peut être élevé en termes d'utilisation de la bande passante [19] ;
• une DHT répartit automatiquement les données de manière homogène entre tous les participants, indépendamment de l'espace de stockage qu'il consomme ; par conséquent, utiliser une DHT empêche d'assurer la justesse des contributions de chacun.

Pour ces raisons, PeerStore propose une approche hybride où les données sont échangées directement entre partenaires, tandis que les méta-informations relatives aux blocs (en l'occurrence, les associations entre les identifiants de bloc et la liste des participants qui en stockent un exemplaire) sont stockées dans une DHT. Comme nous le verrons par la suite, cela procure en outre une plus grande flexibilité à PeerStore.

Alors qu'un certain niveau de redondance des données sauvegardées est nécessaire pour tolérer diverses fautes comme nous l'avons vu en section 2.2.3, il est aussi nécessaire de ne pas dupliquer inutilement des données entre partenaires ou participants (dans l'espace) ni entre versions successives d'un même fichier (dans le temps). Les différents systèmes étudiés utilisent des mécanismes permettant de contrôler le nombre d'instances d'un même bloc de données. On parle de support de stockage à instance unique ou stockage convergent. Cette propriété est obtenue en indexant les données en fonction de leur contenu [24].

Cette approche peut s'avérer intéressante lorsque les participants ont beaucoup de données en commun. Dans Pastiche [7], par exemple, les auteurs font l'hypothèse que les participants vont vouloir sauvegarder toutes les données présentes sur leur machine. Parmi ces données, une bonne partie du système d'exploitation et des applications a des chances d'être commune à de nombreux participants ; des participants collaborant sur un même projet ont également beaucoup de données en commun. Dans cette optique, le stockage à instance unique a donc un apport considérable.

Toutefois, dans le cadre du système de sauvegarde coopérative que nous envisageons, seules les données critiques des utilisateurs, le plus souvent des données personnelles, sont à sauvegarder. On peut donc penser qu'il y aura peu ou pas de duplication inutile des données entre dispositifs mobiles participant. Le phénomène de duplication inutile dans le temps peut néanmoins être observé également dans les scénarios que nous considérons, par exemple lorsqu'un propriétaire est amené à sauvegarder plusieurs versions successives d'un même fichier auprès d'un même contributeur.

Fig. 1: Encodage de plusieurs versions d'une séquence d'octets (fichier) sous forme d'un arbre [24]. Ici, une i-node est partagée entre les deux versions du fichier (dont les racines sont R₀ et R₁). Le bloc de données D₃ est également partagé.

Ces propriétés de sûreté de fonctionnement sont prises en charge par l'encodage des fichiers à sauvegarder, c'est-à-dire par le choix des structures de données représentant un fichier. Chacun des systèmes présentés, mis à part celui d'Elnikety et al., fragmente systématiquement les fichiers à sauvegarder. Cela est nécessaire pour réduire la duplication inutile des données dans l'espace et dans le temps. C'est aussi nécessaire pour assurer une répartition homogène des données sur une DHT, et permettre l'établissement de contributions justes comme nous le verrons par la suite.

pStore utilise des structures de données simples pour représenter les fichiers sauvegardés. Les fichiers sont fragmentés en blocs dont la taille peut varier. Dans pStore, les participants sauvegardent en plus des blocs eux-mêmes une liste des blocs qui contient, pour chaque version du fichier considérée, la liste des identifiants des blocs qui le constituent.Cependant, chaque liste de blocs est indexée par un condensé du chemin du fichier qu'elle représente concaténé à la clef privée de son propriétaire, créant ainsi des espaces de noms de fichiers propres à chaque utilisateur. En pratique, pour restaurer un fichier, il faut donc connaître son chemin et disposer de la clef privée de son propriétaire. Sans cela, il est impossible d'accéder à la liste des blocs du fichier, et donc à ses blocs. C'est la même technique qui est utilisée par PeerStore et une technique similaire pour Pastiche.

Dans ABS, chaque fragment sauvegardé est accompagné d'un bloc de méta-informations. Ces méta-informations sont celles du fichier dont provient le fragment, ainsi que la position du fragment dans le fichier. La clef sous laquelle est stocké l'ensemble est le condensé du contenu du fragment, ce qui permet de maintenir la propriété d'instance unique de chaque fragment. Les méta-informations sont chiffrées avec la clef publique du propriétaire du fichier et l'ensemble (bloc et méta-informations) est signé avec la clef privée du propriétaire. Cette signature garantit l'intégrité de l'ensemble bloc et méta-informations.

Dans Venti-DHash, le codage des fichiers est assuré par Venti. Comme dans un système de fichiers classique, les fichiers sont représentés sous la forme d'un arbre dont les feuilles sont les blocs de données issus de la fragmentation du fichier (figure 1). Les nœuds intermédiaires sont des nœuds d'indirection qui contiennent des pointeurs vers leurs blocs fils. Ici, tous les blocs sont indexés de la même manière, c'est-à-dire par leur condensé. De plus, tous les blocs ont la même taille et le support de stockage sous-jacent ne connaît pas leur sémantique. Pour restaurer une version d'un fichier, il suffit de connaître l'identifiant de l'i-node racine pour cette version.

Toutes ces techniques garantissent dans une certaine mesure l'intégrité des données sauvegardées puisque la manière d'adresser les blocs est dépendante de leur contenu (utilisation d'un condensé). Lorsqu'un bloc est restauré, on peut donc immédiatement vérifier qu'il s'agit bien du bloc demandé. Cependant, seul Pastiche [7] aborde la question de la cohérence des données perçue par l'utilisateur telle que nous l'évoquions en section 2.2.1. Étant en partie implémenté sous la forme d'un système de fichiers, Pastiche a la possibilité de copier les blocs qui seront modifiés pendant le processus de sauvegarde, garantissant ainsi la cohérence de ce qui est sauvegardé.

Concernant la confidentialité des données, la technique utilisée par la plupart des systèmes de sauvegarde cités et également par beaucoup de systèmes de partage de fichiers est celle du chiffrement convergent. L'objectif est de disposer d'un méthode de chiffrement qui ne dépende pas de celui qui effectue le chiffrement. Le chiffrement convergent est donc un chiffrement symétrique dont la clef est le condensé du bloc à chiffrer. C'est ensuite ce bloc chiffré qui est stocké chez les partenaires ou autres participants. Pour désigner puis déchiffrer un bloc, il est donc nécessaire de connaître son identifiant, c'est-à-dire le plus souvent le condensé du bloc chiffré, et sa clef, c'est-à-dire le condensé du bloc en clair. Ce couple est parfois appelé clef-condensé ou CHK (pour content hash key [2]).

Dans cette section, nous décrivons les techniques décrites dans la littérature pour améliorer la disponibilité des données : la duplication et le choix des données à effacer.

Duplication. Pour les systèmes de sauvegarde coopérative où chaque nœud choisit un ensemble de partenaires (Pastiche, PeerStore), le mécanisme de duplication est relativement simple. Dans Pastiche, chaque nouveau participant recherche 5 autres participants ayant un grand nombre de données en commun avec lui ; ces 5 participants deviennent alors ses partenaires de sauvegarde. Il peut donc tolérer la défaillance de 4 de ces nœuds. Dans PeerStore, le choix des partenaires s'effectue d'une manière différente. Toutefois, les auteurs précisent qu'idéalement chaque participant a autant de partenaires que d'exemplaires de ses données, ce qui nous ramène au même schéma que pour Pastiche.

Pour les systèmes basés sur une DHT, par hypothèse, l'ensemble des données stockées dans la DHT est réparti de manière homogène entre les nœuds. Par conséquent, pour tolérer le départ ou la défaillance de participants, les données stockées doivent être dupliquées pour ne pas être perdues. En pratique, les blocs sont généralement dupliqués par le nœud qui en est responsable sur un petit nombre de ses voisins dans l'espace des identifiants, et gardés en cache par les nœuds se trouvant sur le chemin permettant d'y accéder [9,26,25].

Enfin, il est aussi possible d'utiliser des blocs de parité ajoutés aux fichiers à sauvegarder [5] ou des codes protégeant contre la perte de données (erasure codes) qui permettent de reconstruire un bloc simplement à partir d'un sous-ensemble des fragments de ce bloc. Venti-DHash utilise cette seconde possibilité en stockant des fragments de ce bloc sur les successeurs du nœud qui en est responsable. La tolérance à la perte de fragments peut être ajustée en trouvant un compromis avec la taille de ces fragments.

ABS, où les données sont stockées dans une DHT, propose une solution alternative : les propriétaires peuvent choisir la clef sous laquelle stocker un bloc de données. En premier lieu, lors de l'insertion d'un bloc dans la DHT, les participants essayent de l'insérer en prenant pour clef son condensé. Si cela échoue, par exemple parce que la machine responsable de cette clef s'est retirée, il est possible de choisir pour nouvelle clef un condensé de la clef précédente (on parle de rehashing), déplaçant de ce fait les données sur un autre nœud.

Choix des données à effacer. Pastiche, pStore et ABS donnent la possibilité d'effacer des données sauvegardées. Seuls les propriétaires des données peuvent le faire car les demandes d'effacement doivent être signées avec la clef privée du propriétaire. De plus, à chaque bloc est associée une liste des propriétaires afin qu'un bloc ne soit effacé que lorsque tous ses propriétaires l'ont demandé.

PeerStore, en revanche, ne permet pas d'effacer des données sauvegardées. L'inclusion d'une telle fonctionnalité est compliquée par le fait que tous les blocs sauvegardés par un participant n'ont pas fait l'objet d'un accord avec un partenaire (section 3.2.2).

La mise en œuvre de mécanismes permettant de résister aux attaques par déni de service est un sujet à part entière qui demanderait plus de place pour être traité en détail. Nous n'aborderons donc ici que les principales solutions proposées pour chacune des attaques que nous avons identifiées en section 2.2.3.

Égoïsme et inondation. L'attaque par égoïsme est un problème rencontré par tous les systèmes de partage de ressources, en particulier les systèmes de partage de fichiers. De nombreuses solutions ont été proposées. Nous ne nous intéressons ici qu'à celles dédiées aux systèmes de sauvegarde.

Il faut d'abord remarquer qu'il est pratiquement impossible de garantir l'équité des contributions dans une DHT : par hypothèse, toutes les données sont réparties de manière homogène entre les nœuds, indépendamment des ressources utilisées par le nœud. Par conséquent, les systèmes pStore et Venti-DHash ne sont pas résistants à ce type d'attaque. Ils se placent dans le schéma de la "tragédie des biens communs" décrite par Hardin [13] : l'espace de stockage est un bien commun, son coût d'utilisation est partagé entre tous et l'intérêt de chaque participant est donc de profiter de cette ressource. La technique de rehashing d'ABS (cf. section 3.3.3) peut servir à équilibrer la charge sur la DHT mais elle ne prend pas en compte l'utilisation des ressources de chacun et est difficilement contrôlable.

PeerStore propose une solution assez simple : tous les échanges au sein d'un couple de partenaires doivent être symétriques, c'est-à-dire que chacun doit offrir la même quantité d'espace que ce qu'il consomme. Pour trouver des partenaires, chaque nouvel entrant diffuse une offre pour une certaine quantité d'espace de stockage et reçoit par les intéressés des propositions incluant une offre qui peut être différente. C'est au demandeur de décider si l'échange lui convient.

Pastiche ne traite pas ce problème mais Samsara apporte des solutions. Les auteurs y proposent l'établissement d'échanges symétriques par l'obtention d'un droit au stockage représenté par une sorte de capacité lorsqu'un contributeur s'engage à stocker des données. Les droits obtenus par un contributeur peuvent être cédés, lorsqu'il prend le rôle de propriétaire, à un autre participant. Enfin, il est possible à chaque participant de vérifier que ses droits au stockage sont respectés. La littérature des systèmes pair-à-pair de partage de fichiers décrit des solutions plus élaborées basées sur les notions de confiance, de réputation, ou de micro-économie [18,12].

Les propositions basées sur des rapports symétriques [8,19] ont l'avantage d'être résistantes aux attaques par inondation, où un nœud cherche à utiliser toutes les ressources du réseau. Au contraire, les DHT ne sont pas résistantes aux attaques par inondation de par la répartition homogène des données qu'elles font.

Rétention de données. Elnikety et al. insistent sur la nécessité de pouvoir tolérer la rétention non intentionnelle, par exemple lorsqu'elle est due à des déconnexions, tout en étant en mesure de "punir" les abus.

Les solutions qu'ils proposent sont d'une part de vérifier que les partenaires stockent bel et bien les données qu'ils sont censés stocker, et d'autre part d'introduire des règles pour la tolérance aux fautes temporaires. La vérification des données sauvegardées se fait par défis réguliers, c'est-à-dire par l'envoi de demandes de lecture d'un bloc choisi au hasard au contributeur. La tolérance aux fautes temporaires (déconnexions) se fait par l'établissement d'une période de grâce pendant laquelle un participant peut être indisponible sans pour autant que ses données soient effacées. Cependant, ce mécanisme pourrait être utilisé pour profiter des ressources disponibles sans y contribuer. Par conséquent, les auteurs proposent en outre de définir une période d'essai, plus longue que la période de grâce, pendant laquelle les sauvegardes et défis sont autorisés mais pas les restaurations.

Cette technique des défis est reprise par l'ensemble des autres systèmes de sauvegarde coopérative étudiés. En revanche, au lieu de demander la lecture d'un seul bloc par défi, les autres systèmes envoient typiquement une liste de blocs ; en réponse, ils reçoivent une simple signature de l'ensemble de ces blocs, ce qui limite l'utilisation de la bande passante [8,19].

En revanche, d'autres systèmes proposent des méthodes de tolérance aux déconnexions et de punition associée. Samsara [8] en particulier propose une punition progressive pour les participants ne répondant pas, plutôt que l'approche "tout ou rien" de la période de grâce. Dans Samsara, lorsqu'un nœud n'arrive pas à joindre un de ses partenaires, il détruit un bloc choisi au hasard. La probabilité d'effacement d'un bloc donné est choisie telle que, compte tenu du nombre de copies des données du nœud déconnecté, la probabilité qu'un bloc ait été effacé de chaque copie ne devient significative qu'après un nombre important de non-réponses auprès de ses partenaires. Là encore, PeerStore utilise la même approche.