Publications -- Fabrice Le Fessant

This paper presents a set of exploits an adversary can use to continuously spy on most BitTorrent users of the Internet from a single machine and for a long period of time. Using these exploits for a period of 103 days, we collected 148 million IPs downloading 2 billion copies of contents. We identify the IP address of the content providers for 70% of the BitTorrent contents we spied on. We show that a few content providers inject most contents into BitTorrent and that those content providers are located in foreign data centers. We also show that an adversary can compromise the privacy of any peer in BitTorrent and identify the big downloaders that we define as the peers who subscribe to a large number of contents. This infringement on users' privacy poses a significant impediment to the legal adoption of BitTorrent.

Pour mettre au point un programme, tant du point de vue de sa correction que de ses performances, il est naturel de chercher a observer son exe©cution. On peut ainsi chercher à observer la gestion de la mémoire, le temps passé dans une certaine partie du code, ou encore certaines valeurs calculées par le programme. De nombreux outils permettent de telles observations (moniteur système, profiler ou debugger génériques ou spécifiques au langage, instrumentation explicite du code, etc.). Ces outils ne proposent cependant que des analyses << après coup >> ou des observations très limitées. Cet article présente Ocamlviz, une bibliothèque pour instrumenter du code OCaml et des outils pour visualiser ensuite son exécution, en temps-réel et de manière distante.

We study the problem of finding peers matching a given availability pattern in a peer-to-peer (P2P) system. Motivated by practical examples, we specify two formal problems of availability matching that arise in real applications: disconnection matching, where peers look for partners expected to disconnect at the same time, and presence matching, where peers look for partners expected to be online simultaneously in the future. As a scalable and inexpensive solution, we propose to use epidemic protocols for topology management; we provide corresponding metrics for both matching problems. We evaluated this solution by simulating two P2P applications, task scheduling and file storage, over a new trace of the eDonkey network, the largest available with availability information. We first proved the existence of regularity patterns in the sessions of 14M peers over 27 days. We also showed that, using only 7 days of history, a simple predictor could select predictable peers and successfully predicted their online periods for the next week. Finally, simulations showed that our simple solution provided good partners fast enough to match the needs of both applications, and that consequently, these applications performed as efficiently at a much lower cost. We believe that this work will be useful for many P2P applications for which it has been shown that choosing good partners, based on their availability, drastically improves their performance and stability.

This work focuses on: (1) understanding the impact of sinkhole attacks on tree-based routing topologies in Wireless Sensor Networks (WSNs), and (2) investigating cryptography-based strategies to limit network degradation caused by these attacks. This work is particularly important as WSN protocols that construct a fixed routing topology may be significantly affected by malicious attacks. Furthermore, considering networks deployed in a difficult to access geographical region, building up resilience against such attacks rather than detection is expected to be more beneficial. We thus first provide a simulation study on the impact of malicious attacks based on a diverse set of parameters, such as the network scale and the position and number of malicious nodes. Based on this study, we propose a single but very representative metric for describing this impact. Second, we present the novel design and evaluation of two simple and resilient topology-based reconfiguration protocols that broadcasts cryptographic values. The results of our simulation study show that our reconfiguration protocols are practical and effective in improving resilience against sinkhole attacks, even in the presence of some collusion.

Nous étudions la problématique de recherche distribuée de pairs correspondant à un motif de disponibilité donné, dans un système pair-à-pair (P2P). Motivés par des exemples concrets, nous spécifions deux problèmes formels de correspondance de disponibilité qui apparaissent dans des applications réelles: la correspondance de déconnexion, où les pairs cherchent des partenaires dont la déconnexion coïncide avec la leur, et la correspondance de présence, où les pairs cherchent des partenaires connectés en même temps qu'eux dans le futur. Nous proposons, comme solution peu coûteuse et passant à l'échelle, l'utilisation de protocoles épidémiques pour la gestion de la topologie du réseau logique (comme le protocole T-Man); des métriques adéquates sont fournies pour les deux problèmes de correspondance. Notre solution a été évaluée en simulant deux applications P2P, l' ordonnancement de tâches et le stockage de fichiers, sur une trace inédite d'eDonkey, la plus grande fournissant les informations de disponibilité des pairs. Nous prouvons tout d'abord l'existence de motifs réguliers dans les sessions de 14M de pairs sur 27 jours. Nous montrons également, en utilisant 7 jours d'historique, qu'un prédicteur simple peut sélectionner des pairs prédictibles, pour prédire avec succès leur période de présence en ligne pour la semaine suivante. Enfin, les simulations ont montré que notre solution simple a fourni rapidement de bons partenaires afin de répondre au besoin des deux applications, et ainsi de leur permettre de s'exécuter aussi efficacement à un coût bien inférieur. Nous pensons que ce travail sera utile pour beaucoup d'applications P2P, pour lesquelles il a été montré que choisir ses partenaires, en se basant sur leur disponibilité, améliore de façon conséquente les performances du système.

In this paper, we study the viability of a peer-to-peer backup system on nowadays internet connections. In particular, we show that peer lifetime estimation can be used to reduce the maintenance cost of peer-to-peer backup. Previous studies have shown that lifetimes in a peer-to-peer system follow a Pareto distribution. Consequently, peers can be sorted on their expected lifetimes, depending only on the length of their history in the system. By carefully selecting the peers on which backup data is stored, repairing cost can be highly reduced for long-term backup users, while it is still acceptable for new users. The efficiency of this technique is evaluated through simulations of a state-of-the-art peer-to- peer backup system.

This work focuses on: (1) understanding the impact of sinkhole attacks on tree-based routing topologies in Wireless Sensor Networks (WSNs), and (2) investigating cryptography-based strategies to limit network degradation caused by these attacks. This work is particularly important as WSN protocols that construct a fixed routing topology may be significantly affected by malicious attacks. Furthermore, considering networks deployed in a difficult to access geographical region, building up resilience against such attacks rather than detection is expected to be more beneficial. We thus first provide a simulation study on the impact of malicious attacks based on a diverse set of parameters, such as the network scale and the position and number of malicious nodes. Based on this study, we propose a single but very representative metric for describing this impact. Second, we present the novel design and evaluation of two simple and resilient topology-based reconfiguration protocols that broadcasts cryptographic values. The results of our simulation study show that our reconfiguration protocols are practical and effective in improving resilience against sinkhole attacks, even in the presence of some collusion.

Keywords: wireless sensor network, sinkhole attacks, resilience, tree-based routing protocols

In this paper, we study the problem of finding peers matching a given availability pattern in a peer-to-peer (P2P) system. We first prove the existence of such patterns in a new trace of the eDonkey network, containing the sessions of 14M peers over 27 days. We also show that, using only 7 days of history, a simple predictor can select predictable peers and successfully predict their online periods for the next week. Then, motivated by practical examples, we specify two formal problems of availability matching that arise in real applications: disconnection matching, where peers look for partners expected to disconnect at the same time, and presence matching, where peers look for partners expected to be online simultaneously in the future. As a scalable and inexpensive solution, we propose to use epidemic protocols for topology management, such as T-Man; we provide corresponding metrics for both matching problems. Finally, we evaluated this solution by simulating two P2P applications over our real trace: task scheduling and file storage. Simulations showed that our simple solution provided good partners fast enough to match the needs of both applications, and that consequently, these applications performed as efficiently at a much lower cost. We believe that this work will be useful for many P2P applications for which it has been shown that choosing good partners, based on their availability, drastically improves their efficiency.

In this paper, we introduce Pacemaker, a scalable and lightweight protocol to measure reliably the availability of peers. To the best of our knowledge, Pacemaker is the only protocol resilient to the presence of selfish peers, i.e. peers lying about their availability and minimizing their contribution to the system. Pacemaker relies on a novel pulse-based architecture, where a small set of trusted peers regularly flood the network with pulses containing cryptographic values. Collecting these pulses enables peers to later prove their presence in the system at any time, using cryptographic signatures. This new architecture overcomes many limitations of ping-based systems, and can be easily deployed on ad-hoc networks and social-based topologies. Simulation results show that our protocol provides accurate availability measurements even in the presence of selfish peers. Furthermore, our results are verified by experiments in Planetlab, which also illustrate the deployability of Pacemaker in real networks.

Keywords: peer-to-peer, cryptography, availability, monitoring

Lack of scalability is a key issue for virtual-environment technology, and more generally for any large-scale online experience because it prevents the emergence of a truly massive virtual-world infrastructure (Metaverse). The Solipsis project tackles this issue through the use of peer-to-peer technology, and makes it possible to build and manage a world-scale Metaverse in a truly distributed manner. Following a peer-to-peer scheme, entities collaborate to build up a common set of virtual worlds. In this paper, we present a first draft of the Solipsis architecture as well as the communication protocol used to share data between peers. The protocol is based on Raynet, an n-dimensional Voronoi-based overlay network. Its data-dissemination policy takes advantage of the viewdepedent representation of 3D contents. Moreover, the protocol effectively distributes the execution of computationally intesive tasks that are usually executed on the server-side, such as collision detection and physics computation. Finally, we also present our web component, a 3D navigator that can easily run on terminals with scarce resources, and that provides solutions for smooth transitions between 3D Web and Web 2.0.

How does one best go about building actual gossip-based protocols? Trying to answer this question has brought us to address two preliminary questions, namely (1) what the in- trinsics of such systems or protocols are, and (2) what kind of applications would in the end be built on top of such protocols. We address the first question by arguing that gossip-based protocols are all built following one and the same pattern, and describing three building blocks which we claim are used to support this recurrent pattern-most notably a source of randomness. We validate these claims by devising simplified versions of well-known protocols, in a layered fashion, on top of a conceptual interface describing these basic services. The second question is addressed by ar- guing that gossip-based protocols exhibit some probabilistic or imperfect flavor (e.g., probabilistic or partial completion), and by proposing to take such probabilistic behavior into ac- count when devising interfaces for applications building on top of gossip-based protocols. We argue for inherent support for these probabilities in the programming model.

La gestion des changements de formats est un problème crucial de l'informatique : encore aujourd'hui, peu d'applications sont capables de lire des données sauvées dans un format d'une version antérieure ; en distribué, les versions de programmes devant communiquer entre eux sont de plus en plus hétérogènes, en particuliers dans les systèmes pair-à-pair. Dans ce papier, nous présentons une extension de syntaxe d'Objective-Caml en Camlp4 permettant de gérer plus ecacement les évolutions de formats, aussi bien dans les chiers sauvegardés que dans les messages échangés dans un système distribué.

This paper presents GosSkip, a self organizing and fully distributed overlay that provides a scalable support to data storage and retrieval in dynamic environments. The structure of GosSkip, while initially possibly chaotic, eventually matches a perfect set of Skip-list-like structures, where no hash is used on data attributes, thus preserving semantic locality and permitting range queries. The use of epidemic-based protocols is the key to scalability, fairness and good behavior of the protocol under churn, while preserving the simplicity of the approach and maintaining O(log(N)) state per peer and O(log(N)) routing costs. In addition, we propose a simple and efficient mechanism to exploit the presence of multiple data items on a single physical node. GosSkip2019s behavior in both a static and a dynamic scenario is further conveyed by experiments with an actual implementation and real traces of a peer to peer workload.

In this paper we present an empirical study of a workload gathered by crawling the eDonkey network - a dominant peer-to-peer file sharing system - for over 50 days. We first confirm the presence of some known features, in particular the prevalence of free-riding and the Zipflike distribution of file popularity. We also analyze the evolution of document popularity. We then provide an in-depth analysis of several clustering properties of such workloads. We measure the geographical clustering of peers offering a given file. We find that most files are offered mostly by peers of a single country, although popular files don't have such a clear home country. We then analyze the overlap between contents offered by different peers. We find that peer contents are highly clustered according to several metrics of interest. We propose to leverage this property by allowing peers to search for content without server support, by querying suitably identified semantic neighbours. We find via trace-driven simulations that this approach is generally effective, and is even more effective for rare files. If we further allow peers to query both their semantic neighbours, and in turn their neighbours' neighbours, we attain hit rates as high as over 55% for neighbour lists of size 20.

Peer-to-peer file sharing systems have grown to the extent that they now generate most of the Internet traffic, way ahead of Web traffic. Understanding workload properties of peer-to-peer systems is necessary to optimize their performance. In this paper we present an empirical study of a workload gathered by crawling the eDonkey network a dominant file sharing system for over 50 days. Besides confirming the presence of some well-known features, such as the prevalence of free-riding and the Zipf-like distribution of file popularity, we also analyze several previously ignored aspects of such workloads. More specifically, we measure the geographical clustering of peers offering a given file. We find that most files are offered mostly by peers of a single country, although popular files don't have such a clear home country. We also analyze the overlap between contents offered by different peers. We find that peer contents tend to be clustered, which may be taken as evidence that peers possess specific interests. We leverage this and allow peers to search for content without any server support, by maintaining a list of semantic neighbours, i.e. peers with similar interests. Simulation results confirm the clustering property of the trace and show that a high hit ratio is achieved by querying the most recently discovered peers even after removing the top 15% most generous peers. Results also indicate that the clustering is much higher for rare files.

Keywords: PEER-TO-PEER OVERLAY NETWORKS / FILE SHARING APPLICATION / CLUSTERING PATTERNS / TRACE ANALYSIS / SEMANTIC PROXIMITY

Standard compression algorithms are not able to compress DNA sequences. Recently, new algorithms have been introduced specifically for this purpose, often using detection of long approximate repeats. In this paper, we present another algorithm, DNAPack, based on dynamic programming. In comparison with former existing programs, it compresses DNA slighly better, while the cost of dynamic programming is almost neglectible.

Peer-to-peer file sharing now represents a significant portion of the Internet traffic and has generated a lot of interest from the research community. Some recent measurements studies of peer-to-peer workloads have demonstrated the presence of semantic proximity between peers. One way to improve performance of peer-to-peer file sharing systems is to exploit this locality of interest in order to connect semantically related peers so as to improve the search both in flooding- and server-based systems. Creating these additional connections raises interesting challenges and in particular (i) how to capture the semantic relationship between peers (ii) how to exploit these relationships and (iii) how to evaluate these improvements. In this paper, we evaluate several strategies to exploit the semantic proximity between peers against a real trace collected in November 2003 in the eDonkey 2000 peer-to-peer network. We present the results of this evaluation which confirm the presence of clustering in such networks and the interest to exploit it.

Peer-to-peer file sharing systems now generate a significant portion of Internet traffic. A good understanding of their workloads is crucial in order to improve their scalability, robustness and performance. Previous measurement studies on Kazaa and Gnutella were based on monitoring peer requests, and mostly concerned with peer and file availability and network traffic. In this paper, we take different measurements: instead of passively recording requests, we actively probe peers to get their cache contents information. This provides us with a map of contents, that we use to evaluate the degree of clustering in the system, and that could be exploited to improve significantly the search process.

We first introduce a new class of distributed agreement problems, ranging from Uniform Consensus to Non-Blocking Atomic Commitment, by varying the validity condition in the specification. We then provide an early deciding algorithm to solve each problem of this class in the synchronous model with crash failures. Our algorithm achieves the previously established lower bounds for time complexity showing that these lower bounds are tight.

A lot of designers of functional languages have one dream: finding a killer application, outside of the world of symbolic programming (compilers, theorem provers, DSLs), that would make their language spread in the open-source community. One year ago, we tackled this problem, and decided to use to program a network application in the emerging world of peer-to-peer systems. The result of our work, , has superseded our hopes: it is currently the most popular peer-to-peer file-sharing client on the well-known freshmeat.net site, with about 10,000 daily users. Moreover, is the only client able to connect to several peer-to-peer networks, to download and share files. It works as a daemon, running unattended on the computer, and can be controlled remotely using three different kind of interfaces. In this paper, we present the lessons we learnt from its design and implementation.

Keywords: PEER-TO-PEER / FILE SHARING / FUNCTIONAL PROGRAMMING

We study the time complexity of different agreement problems in the synchrono- us model with crash failures, by varying their validity condition. We first introduce a continuous class of agreement problems, the k-TAg problems, which includes both the Uniform Consensus and Non-Blocking Atomic Commitment. We then exhibit a general early-deciding algorithm, that we instanciate to solve every problem of this class. The algorithm always achieves the previously established lower-bounds for early-deciding, showing that these lower-bounds are tight.

Keywords: DISTRIBUTED CONSENSUS / SYNCHRONOUS MODEL / NON-BLOCKING ATOMIC COMMITMENT / ERALY-DECIDING ALGORITHM / K-TAG / LOWER-BOUNDS / VALIDITY CONDITIONS / TIME COMPLEXITY

Distributed scalable garbage collectors, mostly based on some kind of reference counting, fail to detect distributed cycles of garbage. This problem may lead to important memory leaks in distributed storage systems. In this paper, we present a new algorithm which detects and collects such distributed cycles of garbage. Our algorithm is based on the propagation of marks along chains of remote pointers. It uses two new mechanisms: min-max marking , to propagate two different marks to each stub, and sub-generation , to build an acyclic graph on a cycle using back-tracking information. A new technique, called optimistic back-tracking , is also used to speed-up sub-generation. The resulting algorithm is completely distributed, asynchronous, fault-tolerant and inexpensive. Moreover, it collects incrementally all distributed cycles of garbage, without partitioning the system. Thus, it is particularly well adapted to large-scale networks. Finally, it can be easily implemented with minor modifications of a local tracing garbage collector.

We present improvements to the backtracking technique of pattern-matching compilation. Several optimizations are introduced, such as commutation of patterns, use of exhaustiveness information, and control flow optimization through the use of labeled static exceptions and context information. These optimizations have been integrated in the Objective-Caml compiler. They have shown good results in increasing the speed of pattern-matching intensive programs, without increasing final code size.

Jocaml is a system for mobile agents built inside the Objective-Caml language. Jocaml eases the development of concurrent, distributed and mobile agent based applications, by expressing useful distribution abstractions using a small set of simple but powerful primitives taken from the Join-Calculus. The system provides total transparency for migration, application states (after migration, all threads resume their execution in the state before migration), communications (communication channels with other agents are kept during migration) and composition (sub-agents migrate with their parent agent). Other features of the Jocaml system are mobile objects with transparent remote method invocation, distributed garbage collection, failure detection and execution efficiency. Jocaml has already been used in several applications, such as a mobile editor, some distributed games and a distributed implementation of Ambients. This paper describes the Jocaml programming model and language, its current implementation and some interesting applications.

Dynamically-allocated memory must eventually be reclaimed. But manual reclamation is error-prone, and if an object is de-allocated prematurely, a program that later follows a pointer to it might behave incorrectly. In contrast, garbage collection (GC) automatically reclaims objects that can no longer be reached by any path of pointers.

In a distributed system, an object might not only be referenced from one program, but also from other programs and other computers. This makes manual reclamation quite intractable. We consider here the problem of distributed garbage collection (DGC). DGC is particularly important in a large-scale distributed system, since a de-allocation error might cause a completely unrelated program to fail, possibly far away and an arbitrarily long time later.

DGC has been a subject of academic research since at least 1977. With the growth of the Internet, DGC is now receiving its share of commercial attention. For instance, both Java RMI and DCOM come with some form of DGC.

The next section contains a quick review of DGC techniques; for a more in-depth treatment, we refer to published surveys. Then we detail two recent advances in DGC, both developed in the context of the Broadcast project. One is an algorithm for collecting distributed cycles of garbage in a message-passing system; the other is an algorithm for DGC in a system with caching and/or replication. Both have been implemented in real systems and are in actual use. This article assumes some familiarity with centralised GC, now a mature area. We use the following vocabulary. Objects connected by references form a graph; a remote reference may point into another process. An application or mutator enters the graph via roots, allocates objects, and performs assignment of reference variables. The system or collector reclaims garbage, i.e., objects that are reachable by no path from any root.

The join-calculus is both a name passing calculus and a core language for concurrent and distributed programming. An essential part of its implementation is the compilation of join-patterns. Join-patterns define new channels and all the synchronizations they take part to at the same time. Relying on the experience based on our two implementations, we study the translation of join-patterns into deterministic finite-state automata as well as some related optimizations.

Most existing reference-based distributed object systems include some kind of acyclic garbage collection, but fail to provide acceptable collection of cyclic garbage. Those that do provide such GC currently suffer from one or more problems: synchronous operation, the need for expensive global consensus or termination algorithms, susceptibility to communication problems, or an algorithm that does not scale. We present a simple, complete, fault-tolerant, asynchronous extension to the (acyclic) cleanup protocol of the SSP Chains system. This extension is scalable, consumes few resources, and could easily be adapted to work in other reference-based distributed object systems-rendering them usable for very large-scale applications.

We present an algorithm that detects cycles of garbage in reference-based distributed systems. It is derived from Hughes' algorithm, in a simplified form that makes far fewer assumptions about the system. A local garbage collector marks incoming and outgoing references with timestamps that are propagated asynchronously between spaces. A central site computes the minimum reachable timestamp, allowing stale references to be identified and deleted. The coexistence of non-participating spaces, and spaces participating in collections controlled by more than one central site, is allowed.