Mohamed Ali

Kaafar Résumé

Prof Jon Crowcroft

Prof Dr Serge Fdida

Prof Jean-Paul Rigault

Mathieu, Malli, Ridha Julien J Pascal

LA SÉCURITÉ DES SYSTÈMES DE COORDONNÉES INTERNET

Les systèmes Internet à base de coordonnées permettent un positionnement pratique des noeuds dans le réseau. Dans ce type de systèmes, l'idée principale est que si les distances réseau entre différents noeuds Internet peuvent être plongées dans un espace approprié, alors les distances non mesurées peuvent être estimées en utilisant une simple opération de calcul de distance géométrique dans cet espace. Récemment, on a pu prouver que ces systèmes à base de coordonnées étaient précis, avec une faible erreur de prédiction. Cependant, ces systèmes se basent souvent sur une coordination entre les noeuds, et font l'hypothèse que les informations reportées par les noeuds sont correctes.

Dans cette thèse, nous avons identifié plusieurs attaques, exploitant cette hypothèse d'honnêteté des noeuds, et pouvant être lancées contre des systèmes de positionnement Internet à base de coordonnées. Nous avons en l'occurrence étudié l'impact qu' avaient de telles attaques sur deux systèmes représentatifs des systèmes de positionnement actuels : NPS et Vivaldi. Nous avons entre autres montré que ces attaques, pouvaient dangereusement mettre en péril le bon fonctionnement de ces systèmes de coordonées, et par la même les applications se basant sur ce système pour les estimations de distances. À travers les simulations de plusieurs attaques, menées par des noeuds malhonnêtes, fournissant des coordonnées biaisées ou retardant les mesures, nous avons expérimenté plusieurs stratégies d'attaques qui ont pour objectifs: (i) d'introduire du désordre dans le système, (ii) de tromper les noeuds honnêtes afin qu'ils se positionnent loin de leurs coordonnées correctes et (iii) d'isoler certains noeuds cibles à travers des collusions. Nos résultas confirment la vulnérabilité de tels systèmes à ces attaques.

Notre contribution majeure a été par la suite de proposer un modèle de détection des comportements malicieux au sein de ces systèmes de positionnement durant le calcul des cordonnées.

Nous avons montré en premier lieu que la dynamique d'un noeud, dans un système de coordonnées, exempt de comportements anormaux ou malhonnêtes, peut être modélisée par un modèle d'états linéaire, et traqué par un filtre de Kalman. De plus, les paramètres d'un filtre calibré au niveau d'un noeud donné, peuvent être utilisés pour modéliser et prédire le comportement dynamique d'un autre noeud, tant que ces deux noeuds sont proches l'un de l'autre dans le réseau. Nous avons dès lors proposé une infrastructure de noeuds experts : des noeuds de confiance, se positionnant dans l'espace des coordonnées, en utilisant exclusivement d'autres noeuds experts. Ils sont alors immunisés contre n'importe quel comportement malicieux dans le système. Pendant le calcul de leurs propres coordonnées, les autres noeuds utilisent les paramètres du filtre d'un noeud expert proche, comme étant une représentation d'un comportement normal, pour détecter et filtrer toute activité malicieuse ou anormale. Une combinaison de simulations et d'expérimentations PlanetLab a été utilisée pour démontrer la validité, la généralité et l'efficacité de l'approche proposée pour chacun des deux systèmes Vivaldi et NPS.

Enfin, nous nous sommes penchés sur le problème de la validité des coordonnées Internet telles qu' annoncées par les noeuds d'un système de coordonnées durant la phase d'estimation des distances. En effet, certains noeuds peuvent délibérément mentir quant à la valeur exacte viii de leurs coordonnées afin de lancer diverses attaques contre les applications et les réseaux de couverture.

La méthode proposée se divise en deux étapes : 1)établir l'exactitude des coordonnées annoncées en utilisant l'infrastructure des noeuds experts et la méthode de détection des noeuds malicieux, et 2) délivrer un certificat à validité limitée pour chaque coordonnée vérifiée. Les périodes de validité sont calculées à partir d'une analyse des temps d'inter-changement observés par les noeuds experts. En faisant cela, chaque noeud expert, peut estimer le temps jusqu'au prochain changement de coordonnées, et ainsi, peut limiter le temps de validité du certificat qu'il délivrerait aux noeuds normaux. Notre méthode est illustrée en utilisant une trace recueillie à partir d'un système Vivaldi déployé sur PlanetLab, où les distributions de temps d'inter-changements suivent des distributions longue traine (distribution log-normale dans la plupart des cas, et distribution Weilbull sinon). Nous montrons l'efficacité de notre méthode en mesurant l'impact de plusieurs attaques sur les estimations de distance, expérimentées sur PlanetLab.

The research that has gone into this thesis has been thoroughly enjoyable. That enjoyment is largely a result of the interaction that I have had with my supervisors, colleagues and INRIA's people.

I feel very privileged to have worked at INRIA with my supervisors, Walid Dabbous and Thierry Turletti. To each of them I owe a great debt of gratitude for their patience, inspiration and friendship. Sincere thanks to both of them for having always been there to listen to and comment upon whatever I had thought out or wanted to discuss about and patiently reviewing all my work. Their enthusiastic nature helped me perform better. They had taught me a great deal about the field of Computer Science by sharing with me the joy of discovery and investigation that is the heart of research.

This dissertation would not have been possible without many collaborative efforts with Laurent Mathy, Chadi barakat and Kavé Salamatian. They demonstrated hard work, clear thinking, and remarkable writing skills that I learned through collaboration with them. I am deeply grateful to Laurent for his brilliant insights, thoughtful discussions, and detailed comments. I am indebted to Laurent for being of friend and for giving me invaluable advice on countless occasions not only on research but also on various issues of life. He is living evidence that even a man of genius can be warm, kind and always encouraging. I would like also to address special thanks to Chadi, for numerous technical discussions, but also for having always been a friend, that makes enjoyable working at PLANETE. Many Thanks Kavé for being the most impressive guy I've known:-). Kave's command and ease in stochastic modeling are something I aspire to achieve one day. I am also grateful to Prof. Farouk Kamoun, my master thesis' advisor at the Cristal Lab ENSI

ABSTRACT

Internet coordinate-based systems allow easy network positioning. In such systems, the basic idea is that if network distances between Internet nodes can be embedded in an appropriate space, unmeasured distances can be estimated using a simple distance computation in that space. Recently, these coordinates-based systems have been shown to be accurate, with very low distance prediction error. However, most, if not all, of current proposals for coordinate systems assume that the nodes partaking in the system cooperate fully and honestly with each other -that is that the information reported by probed nodes is correct -this could also make them quite vulnerable to malicious attacks. In particular, insider attacks executed by (potentially colluding) legitimate users or nodes infiltrating the system could prove very effective.

As the use of overlays and applications relying on coordinates increases, one could imagine the release of worms and other malware, exploiting such cooperation, which could seriously disrupt the operations of these systems and therefore the virtual networks and applications relying on them for distance measurements.

In this thesis, we first identify such attacks, and through a simulation study, we observed their impact on two recently proposed positioning systems, namely Vivaldi and NPS. We experimented with attack strategies, carried out by malicious nodes that provide biased coordinates information and delay measurement probes, and that aim to (i) introduce disorder in the system, (ii) fool honest nodes to move far away from their correct positions and (iii) isolate particular target nodes in the system through collusion. Our findings confirm the susceptibility of the coordinate systems to such attacks.

Our major contribution is therefore a model for malicious behavior detection during coordinates embedding. We first show that the dynamics of a node, in a coordinate system without abnormal or malicious behavior, can be modeled by a Linear State Space model and tracked by a Kalman filter. Then we show, that the obtained model can be generalized in the sense that the parameters of a filter calibrated at a node can be used effectively to model and predict the dynamic behavior at another node, as long as the two nodes are not too far apart in the network. This leads to the proposal of a Surveyor infrastructure: Surveyor nodes are trusted, honest nodes that use each other exclusively to position themselves in the coordinate space, and are therefore immune to malicious behavior in the system. During their own coordinate embedding, other nodes can then use the filter parameters of a nearby Surveyor as a representation of normal, clean system behavior to detect and filter out abnormal or malicious activity. A combination of simulations and PlanetLab experiments are used to demonstrate the validity, generality, and effectiveness of the proposed approach for both Vivaldi and NPS.

Finally, we address the issue of asserting the accuracy of Internet coordinates advertised by nodes of Internet coordinate systems during distance estimations. Indeed, some nodes may even lie deliberately about their coordinates to mount various attacks against applications and overlays.

vi Our proposed method consists in two steps: 1) establish the correctness of a node's claimed coordinate by using the Surveyor infrastructure and malicious embedding neighbor detection; and 2) issue a time limited validity certificate for each verified coordinate. Validity periods are computed based on an analysis of coordinate inter-shift times observed by Surveyors. By doing this, each surveyor can estimate the time until the next shift and thus, can limit the validity of the certificate it issues to regular nodes for their calculated coordinates. Our method is illustrated using a trace collected from a Vivaldi system deployed on PlanetLab, where intershift times are shown to follow long-tail distribution (log-normal distribution in most cases, or Weibull distribution otherwise). We show the effectiveness of our method by measuring the impact of a variety of attacks, experimented on PlanetLab, on distance estimates.

LIST OF FIGURES

THESIS PRESENTATION

Internet coordinate-based systems are poised to become an important service to support overlay construction and topology-aware applications. Indeed, through network distance embedding into an appropriate geometric space, such systems allow for accurate network distance estimations with low overhead. However, coordinate systems often rely on good cooperation between nodes for correct coordination and assume that information reported by probed nodes is correct.

In the first part of this thesis, we identify various attacks against coordinate embedding systems and show their effectiveness on two representative positioning systems. Our studies [START_REF] Kaafar | Real attacks on virtual networks: Vivaldi out of tune[END_REF][START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF] demonstrate that these attacks can seriously disrupt the operations of these systems and therefore the virtual networks and applications relying on them for distance measurements.

In a second step, we propose a general method for malicious behavior detection during coordinate computations [START_REF] Kaafar | Securing Internet Coordinate Embedding Systems[END_REF]. We postulate and verify that, in the absence of malicious activity, a node's coordinate can be viewed as a stochastic process with linear dependencies whose evolution can be tracked by a Kalman filter [4]. Using secure filter parameters, nodes involved in the Internet coordinate-based system run locally and in a "stand-alone" fashion a Kalman filter tracking the coordinate adjustments. These nodes can then use the Kalman filter output (the innovation process), to compare their observed coordinate adjustments with the one predicted by the Kalman filter, and flag as "suspicious" embedding steps where the difference would be too high.

Finally, we propose to leverage the Surveyor infrastructure and embedding cheat detection test to address the question of guaranteeing the veracity of the coordinates 1 advertised by nodes, during the distance estimation phase of these coordinate-based systems [5]. More precisely, we propose that several Surveyors measure their distance to a node in order to verify the correctness of its claimed coordinate (using the cheat detection test). If all Surveyors agree that this coordinate is the node's true coordinate, a time limited validity certificate, including the certified coordinate, is issued to the node.

Internet coordinate-based positioning systems

Recent years have seen the advent of Internet applications (e.g. PASTRY [START_REF] Rowstron | Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems[END_REF], OCEANSTORE [START_REF] Kubiatowicz | OceanStore: An Architecture for Global-Scale Persistent Storage[END_REF], ESM [START_REF] Chu | A case for end system multicast[END_REF], SKYPE [START_REF][END_REF], Azureus [10], etc.), which are built upon and benefit from topology-aware overlays. In particular, most if not all of these applications and associated overlays rely on the notion of network proximity, usually defined in terms of network delays or round-trip times (RTTs), for optimal neighbor selection. However, proximity measurements, based on repeated pair-wise distance measurements between nodes, can prove to be very onerous in terms of measurement overheads. Indeed, the existence of several overlays simultaneously can result in significant bandwidth consumption by proximity measurements (i.e. ping storms) carried out by individual overlay nodes [START_REF] Rewaskar | Testing the Scalability of Overlay Routing Infrastructures[END_REF]. Also, measuring and tracking proximity within a rapidly changing group requires high frequency measurements.

To palliate this problem, network positioning systems, such as [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF][START_REF] Pias | Lighthouses for Scalable Distributed Location[END_REF][START_REF] Costa | Practical Internet coordinates for distance estimation[END_REF][START_REF] Ng | A Network Positioning System for the Internet[END_REF][START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF][START_REF] Shavitt | Big-bang simulation for embedding network distances in euclidean space[END_REF][START_REF] Zhang | A Hierarchical Approach to Internet Distance Prediction[END_REF], were introduced. The key idea of such systems is that if each node can be associated with a "virtual" coordinate in an appropriate space, distance between nodes can be trivially computed without the overhead of a direct measurement. In other words, these systems embed latency measurements amongst samples of a node population into a geometric space and associate a network coordinate vector (or coordinate in short) in this geometric space to each node, with a view to enable accurate and cheap distance (i.e. latency) predictions amongst any pair of nodes in the population. Put simply, if network distances can be embedded into a coordinate space where a reasonably accurate position for each node can be established, the measurement overhead produced by this positioning can be amortized over many (un-measured) distance predictions, which drastically reduces the distance measurement sampling cost of the overall system.

Extensive measurements and analysis from a live, large-scale deployment have shown network coordinate systems to be fit for purpose [START_REF] Ledlie | Network Coordinates in the Wild[END_REF], making them a valuable tool to support distributed applications, systems and overlays (e.g., [START_REF] Stoica | Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[END_REF]10,[START_REF][END_REF]) that rely on, and benefit from, the notion of network topology-awareness. In fact, coordinate-based positioning systems achieve desirable properties (as compared to complete measurement of all inter-node delays), such as accuracy, robustness, stability, scalability and low overheads. However, it should also be noted that these can often only be realized at the expense of rather slow convergence times. In such a scheme, new nodes joining the system only reach a good estimate of their own coordinates after a lapse of time in the timescale of tens of seconds to several minutes. This is several orders of magnitude slower that what is achievable with direct distance measurements between nodes and is often unacceptable for topology-aware applications whose aim is to quickly identify "best nodes". We therefore contend that coordinate-based positioning systems are an attractive proposition only if they are deployed as a service: every node could run a coordinate system daemon at boot time which would then be capable of providing accurate coordinate estimates to applications and their overlays on request. In essence, the coordinate system could then be seen as a component of a "virtual infrastructure" that supports a wide range of overlays and applications, and this would argue in favor of a deployment of Internet coordinate systems as an always-on, large-scale service.

Motivations, Problematics and Contributions

As the use of overlays and applications relying on coordinates increases, one could imagine the release of worms and other malicious software whose purpose is to attack the coordinate system. In particular, it is very interesting to note that a system providing an "always-on and large scale coordinate service" (as an expected deployment of Internet Coordinate systems) would also likely be a prime target for hackers, as its disruption could result in the mis-functioning or the collapse of very many applications.

As current proposals for coordinate systems assume that the nodes partaking in the system cooperate fully and honestly with each other -that is that the information reported by probed nodes is correct -this make them quite vulnerable to malicious attacks. In particular, insider attacks executed by (potentially colluding) nodes infiltrating the system could prove very effective. In essence, the key questions we should ask are:

1. What if a malicious node provides biased coordinates information and/or delay measurement probes to other honest nodes in the system?

2. How one could secure the computation of coordinates in these systems in a general and effective way?

3. Even though the coordinates computation phase of these systems may have been secured, this would not prevent a malicious node from blatantly lying about its coordinate when a node requests them for simple distance estimation, during the "usage phase" of the coordinate service. How could we assert such exchanged coordinates?

Our first contribution is then to study how potent this danger is for coordinatesembedding systems. We identify three types of potential attacks against coordinatebased network positioning systems. Specifically, we study how these attacks can lead to inaccuracy of distance prediction. We demonstrate that it is easy to perform Denial of Service (DoS) attacks on such systems. We also analyze simple ways that allow malicious nodes to take control of the embedding coordinates system, as they are able to impose positions in the network to other honest nodes, without being detected. Finally, we study how conspiracy can be achieved in these systems and how much it could affect them. The "effectiveness" of these attacks on the target systems are demonstrated through extensive simulations, using two recently proposed coordinate-based positioning systems, namely Vivaldi as a prominent representative of purely peer-topeer-based (i.e. without infrastructure support) positioning systems,and NPS as typical of landmark-based systems. This constitutes a pioneer work in the area.

We have shown that infrastructure-based systems can, under some well chosen attack strategies, be as vulnerable than those based on the peer-to-peer paradigm. Furthermore, the security mechanisms that have been proposed to date to defend against malicious nodes are clearly rather primitive and still in their infancy and definitely cannot defend against all types of attacks.

One of our salient findings is that larger systems are consistently more resilient than smaller ones. Given the observation in [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] and [START_REF] Ng | A Network Positioning System for the Internet[END_REF] that larger systems are more accurate and the well known fact that larger systems converge slower at start-up time, there seems to be a compelling case for large-scale coordinate systems to be built as a virtual infrastructure service component. The paradox is of course that alwayson, large scale systems supporting many different applications will always attract more attacks than systems with a smaller reach, while the large size of the system itself would act as a particularly good terrain to create especially virulent propagation of the attack.

Our results also show that there is an intrinsic trade-off to be made between accuracy and vulnerability. Indeed, we have shown that the more accurate the system for a given system size, the more susceptible it was to a same proportionate level of attack. Also, we have shown that while an attack is in full swing, the performance of the coordinate systems (and of the applications it supports) can easily degrade below that of a system where coordinates are chosen randomly, whilst the aftermath of an attack could have very long lasting effects on the system due to a small number of remaining malicious nodes.

Guided by the understanding of attack mechanisms and of their consequences on the coordinate systems gained from this study, one of our major contributions was naturally the proposal of a general and effective protocol to detect malicious behavior and to secure the embedding process in such coordinates-based systems.

We postulate and verify that, in the absence of malicious activity, a node's coordinate can be viewed as a stochastic process with linear dependencies whose evolution can be tracked by a Kalman filter [4]. Noting that, in the absence of malicious nodes, a node's coordinate depends on the combination of network conditions and the specificities of the embedding process itself (e.g. which coordinate protocol is in use, the chosen dimensionality of the geometric space, etc), we therefore introduce the concept of Surveyor nodes (or Surveyors in short). Surveyors form a group of trusted (honest) nodes, scattered across the network, which use each other exclusively to position themselves in the coordinate space. Of course, Surveyors do assist other nodes in their positioning (as prescribed by the embedding protocol), but we stress that Surveyors never rely on non-Surveyor nodes to compute their own coordinate. This strategy thus allows Surveyors to experience and learn the natural evolution of the coordinate space, as observed by the evolution of their own coordinate, in the absence of malicious activities. In essence, Surveyor nodes are thus vintage points guaranteed to be immune from malicious activities. The idea is that Surveyors can then share a "representation" of normal behavior in the system with other nodes to enable them to detect and filter out abnormal behavior.

Our detection protocol is then based on the fact that each Surveyor computes and calibrates the parameters of a linear state space model (in a clean-system) and then shares the parameters of this model with other nodes. These nodes can then use these parameters, to run locally and in a "stand-alone" fashion a Kalman filter tracking the coordinate adjustments. These nodes use the Kalman filter output (the innovation process), to compare their observed coordinate adjustments with the one predicted by the Kalman filter, and flag as "suspicious" embedding steps where the difference would be too high. A combination of simulations and Planet-Lab experiments are used to demonstrate the validity, generality, and effectiveness of the proposed approach for two representative coordinate embedding systems, namely Vivaldi and NPS.

Finally, we addressed the question of guaranteeing the veracity of the coordinates advertised by nodes. Indeed, although if we secure the security of the embedding phase of Internet coordinate-based systems, or in other words the coordinate computation phase, these systems are above all intended to provide distance estimates between nodes, based on their coordinates only, even and all the more so if these nodes have never exchanged a distance measurement probe. Internet Applications would then benefit from an exchange of coordinates between nodes to estimate distances. However, these coordinate's exchanges would provide a malicious node with an opportunity to strike: in order to achieve some application-dependent goal or advantage (e.g. freeriding, denial-of-service, isolation, ubiquity gift, etc), a node can repeatedly lie about its coordinate. Simply lying about its coordinate could seriously disrupt the operations of such Internet applications relying on coordinate-based systems for distance estimation.

We then propose to leverage the Surveyor infrastructure and embedding cheat detection test to certify exchanged coordinates. More precisely, we propose that several Surveyors measure their distance to a node in order to verify the correctness of its claimed coordinate. If all Surveyors agree that this coordinate is the node's true coordinate, a time limited validity certificate, including the certified coordinate, is issued to the node.

Validity periods are computed based on an analysis of coordinate inter-shift times observed by Surveyors. Each surveyor estimates the time until the next shift and thus, and can then limit the validity of the certificate it issues to regular nodes for their calculated coordinates. Our method is illustrated on a trace collected from a Vivaldi system deployed on PlanetLab, where inter-shift times are shown to follow long-tail distribution (lognormal distribution in most cases, or Weibull distribution otherwise).

we then study the impact of a sophisticated attack on the accuracy of distance estimations, with and without our proposed coordinate certification defense mechanism. Carrying out such an attack, on a Vivaldi system deployed on PlanetLab, our method has been shown to be effective, enjoying good verification test performance (high true positive detection rate with low false positive rates), while achieving a very good trade-off between scalability and security. Indeed, the validity periods of certificates are rarely over-estimated, while they still do not trigger too frequent re-certifications. This work thus complements our detection protocol for embedding security.

Thesis Organization

The dissertation is structured as the following. In the next chapter, we present an overview of the proposed embedding coordinates systems in the literature. Particularly, we focus on those trying to equip their mechanism by a "specific" detection mechanism against malicious nodes, and describe in more details the workings of the systems chosen for our study.

In Chapter 3, we first identify and classify the attacks, then we demonstrate and study the effects of theses attacks, through extensive simulations.

In Chapter 4, we present a general model of coordinate embedding, in the absence of malicious nodes, that naturally leads to the Kalman filter framework. We validate the model, with both simulations and PlanetLab experiments, in the case of both Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] and NPS [START_REF] Ng | A Network Positioning System for the Internet[END_REF]. This chapter also studies the viability of the idea of using Surveyor nodes in secure coordinate embedding.

In the last part of this chapter, we describe and evaluate, how Surveyors can effectively be used for malicious node detection in the specific embedding process of Vivaldi and NPS. Finally, the dissertation is concluded in chapter 6 with perspectives on our contributions and on future research in this area.

In Chapter 5, we address the issue of asserting the accuracy of Internet coordinates advertised by nodes of Internet coordinate systems during distance estimations. We study and characterize the coordinate inter-shift times and show that these times observed at Surveyors can adequately and statistically model inter-shift times at closeby nodes. Then we detail the certification procedure, and the performance evaluation of our proposal in the context of various attacks.

Finally, the conclusions of this thesis appear in chapter 6.

AN OVERVIEW OF NETWORK POSITIONING SYSTEMS 2.1 Introduction

As innovative ways are being developed to harvest the enormous potential of Internet infrastructure, a new class of large-scale globally-distributed network services and applications such as distributed overlay network multicast [START_REF] Liebeherr | Application-layer multicast with delaunay triangulations[END_REF][START_REF] Chu | A case for end system multicast[END_REF], content addressable overlay networks [START_REF] Stoica | Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[END_REF][START_REF] Ratnasamy | A scalable contentaddressable network[END_REF], and peer-to-peer file sharing such as Gnutella [START_REF]A distributed Peer-to-Peer data-sharing system[END_REF], OceanStore [START_REF] Kubiatowicz | OceanStore: An Architecture for Global-Scale Persistent Storage[END_REF], BitTorrent [START_REF]BitTorrent Specification wiki[END_REF][START_REF] Cohen | Incentives Build Robustness in BitTorrent[END_REF], etc. have emerged.

Because these systems have a lot of flexibility in choosing their communication paths, they can greatly benefit from intelligent path selection based on network performance. Collecting up-to-date latency measurements between nodes in an overlay network would be very beneficial for such applications. Especially, in a wide-area network, communication latencies have a significant impact on the overall execution time of operations.

For example, in a peer-to-peer file sharing application, a client ideally wants to know the available bandwidth between itself and all the peers that have the wanted file. Proximity-aware distributed hash tables would also use latency measurements to reduce the delay stretch of lookups [START_REF] Rowstron | Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems[END_REF]. Content distribution systems would construct network-aware trees to minimize dissemination times [START_REF] Rowstron | SCRIBE: The design of a large-scale event notification infrastructure[END_REF]. Decentralized web caches need latency information to map clients to cache locations, or to guide the selection of a download server from multiple replicas. And finally, a topology knowledge would allow the construction of efficient multicast delivery trees.

In this chapter, we present a briefing on different proposals for network positioning systems, with emphasis on the Internet coordinate-embedding systems, which we classify in two major classes: Landmark-based approaches, and decentralized Internet coordinates systems. The outline of this chapter is as follows. Next, we begin by describing several proposed works that do provide network proximity or location estimates, but do not rely on "virtual" coordinates embedded into geometric spaces. These systems are called direct measurements systems. Then, we concentrate on describing coordinate-based systems that fit within the landmark-based approaches for Internet positioning. Finally, we present different decentralized coordinate-based systems for network positioning. In particular, we focus on those systems including and using security mechanisms to try and filter out malicious nodes, although (as demonstrated in this dissertation) these are still rather primitive or still in their infancy and definitely cannot defend against all types of attacks.

Direct measurements Systems

Several approaches in the literature provide network proximity or location estimates using either direct pair-wise measurements, or by supplying applications with network distances estimates directly. In contrast to coordinates-embedding systems, these approaches do not attempt to globally model Internet hosts positions using absolute coordinates, but rather, most of them try to contribute in specific application needs, such as special peer lookups, or clustering, etc. In the following, we underline the mostly known approaches that have been proposed for locating network nodes. graphical position of a node using its geographical distances to a set of landmarks. Geographical distances to the landmarks are deduced from the correspondent delay distances (obtained by direct probing between the landmarks and the target host) by relying on the assumption that digital information travels along fiber optic cables at almost exactly 2/3 the speed of light in a vacuum. Basically, given the geographical locations of the landmarks and their geographical distances to a given target host, an estimation of the location of the target host is achieved using multilateration, as done with the Global Positioning System (GPS) [START_REF] Enge | Special issue on global positioning system[END_REF].

IP2Geo system [START_REF] Padmanabhan | An Investigation of Geographic Mapping Techniques for Internet Hosts[END_REF] estimates the physical location of a remote server using information from the content of DNS names, whois queries, pings from fixed locations, and BGP information.

IDMaps

The first complete system that is aimed at predicting Internet distance is called IDMaps [START_REF] Francis | An architecture for a global Internet host distance estimation service[END_REF], which can be seen as the predecessor of landmark-based coordinate systems. IDMaps is an infrastructural service in which special HOPS servers maintain a virtual topology map of the Internet consisting of end hosts and special hosts called Tracers. This virtual topology map is used to predict Internet distance. For example, the distance between hosts x and y is estimated as the distance between x and its nearest Tracer T1, plus the distance between y and its nearest Tracer T2, plus the shortest path distance from T1 to T2 over the Tracer virtual topology. As the number of Tracers grow, the prediction accuracy of IDMaps tends to improve. Designed as a client-server architecture solution, end hosts can query HOPS servers to obtain network distance predictions.

Comparing to the IDMaps service, coordinate-based positioning systems are different in that nodes are enabled to use their own resources to compute their positions in the Internet. Moreover, these systems do not not directly interact with any applications. It is up to the applications running on end hosts to decide how to use the computed locations (coordinates).

Binning method

The Binning method aims to cluster nearby nodes using a technique of landmarks ordering. The binning method [START_REF] Ratnasamy | Topologically-Aware Overlay Construction and Server Selection[END_REF] consists then in clustering the nodes into bins where a bin is identified by a specific increasing order of closeness to landmark nodes. Thus, each ordering of landmarks represents a bin (e.g., for N = 4, L 2 L 4 L 1 L 3 represents a bin). A node measures its RTT to each landmark and ranks the landmarks in an increasing order of RTT . Each node belongs therefore to the bin which has the same ordering of landmarks. It is expected that the nodes of the same bin are relatively closer to each other than to those in the other bins. Moreover, it is expected that the more the order of two bins is different the farther are their nodes.

The representation of a bin can be refined to use not only the ordering of landmarks but also the absolute value of the RTT measurements. These values can be indicated by dividing the range of possible delay values into a number of levels. For example, the range of possible delay values can be divided into the three following levels: (i) level 0 for delays in the range [0,100]ms, (ii) level 1 for delays in the range [100,200]ms, and (iii) level 2 for delays longer than 200ms. Thus, a bin can be identified by this notation: L i L j L k : a i a j a k where L i L j L k is the relative ordering of landmarks and a i a j a k are the delay levels of each ordering respectively.

Application

One potential application that can profit from such clustering method is the topologically aware construction of overlays. Based on the binning strategy, authors in [START_REF] Ratnasamy | Topologically-Aware Overlay Construction and Server Selection[END_REF] construct the overlay network CAN [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF] (Content-Addressable Network) to be congruent with the underlying IP topology. CAN is an application-level network forming a virtual d-dimensional cartesian coordinate space. This space is partitioned among all the overlay nodes in a manner that each node is responsible of a space portion. Routing in CAN consists in sending packets along the direct line path through the cartesian space from the source to the destination .

We briefly explain how the CAN overlay network can be constructed using the binning scheme. This scheme consists in dividing the space into the number of possible orderings of landmarks. Thus, there are N! equal sized portions when the number of landmarks is equal to N. Each portion belongs to a single ordering. The partitioning of the space is done in a cyclical ordering of the dimensions (e.g., xyzxyzx...). First, the space is divided into N portions along the first dimension. Then, along the second dimension, each portion is divided into (N -1) portions each of which is divided to (N -2) portions and so on. A CAN node determines its bin based on its RTT measurements to the landmarks. Then, the node joins the CAN in a random point of the correspondent portion of the coordinate space which corresponds to its landmark ordering. When a node joins a portion which is already assigned to another node, the portion is divided equally between them. The problem is that this behavior may achieve an unequal dividing of the space among the overlay nodes. Even though the average number of network hops on the path between two nodes decreases when using such space partitioning, the load balancing between the nodes may be affected.

Hotz method

Hotz [START_REF] Hotz | Routing Information Organization to Support Scalable Routing with Heterogeneous Path Requirements[END_REF] estimates the distance between two nodes based on the delay vectors (i.e., delay measurement to a set of reference nodes) of these nodes. It consists in bounding the distance D(p i , p j ) (or the delay) between two nodes p i and p j by two values which are the difference distance |D(p i , L) -D(L, p j )| and the summation distance (D(p i , L) + D(L, p j )) as shown in the following equation:

|D(p i , L) -D(L, p j )| < D(p i , p j ) < (D(p i , L) + D(L, p j ))
where D(p i , L) and D(L, p j ) are the distances between a landmark L with nodes p i and p j respectively. Thus, if there are N landmark nodes then the delay between two nodes p i and p j is lower bounded by max|D(p i , L k ) -D(L k , p j )| and upper bounded by min|D(p i , L k ) + D(L k , p j )| where k varies from 1 to N as shown in the following equation:

max k=1...N |D(p i , L k ) -D(L k , p j )| < D(p i , p j ) < min k=1...N (D(p i , L k ) + D(L k , p j )).
Thus, the distance between the nodes p i and p j can be estimated as the average value of these two bounds. One would need to perform such direct measurements to the landmarks at each distance inference between any pair of nodes in the Internet.

Traceroute-based approaches

Many approaches are designed and implemented to infer the network topology using the basic idea of the traceroute tool. In the following, we describe Rocketfuel, as one of the most popular traceroute-based approaches, incorporating different techniques from its predecessors.

Rocketfuel

Rocketfuel [START_REF] Spring | Measuring ISP Topologies with Rocketfuel[END_REF] infers the topology using traceroute probes, BGP routing tables, and DNS information. It aims mainly to find out the useful prefixes to be probed for the discovery of an ISP topology, then to collect the aliases which belong to the same router, using as few measurements as possible. A BGP table maps a destination IP address prefix to a set of ASes that are traversed to reach that destination. Thus, the use of BGP tables permits to pick up the prefixes whose traceroutes transit the ISP being mapped. Based on BGP tables, Rocketfuel defines three classes of traceroutes that transit the ISP network, then, it filters out the prefixes which are likely to follow redundant paths through the ISP network. It relies on the DNS information to check up if an obtained router address belongs to the ISP being mapped. This information serves to identify the router role and location, but requires costly measurements.

Meridian Approach

In [START_REF] Wong | A Lightweight Approach to Network Positioning without Virtual Coordinates[END_REF], authors proposed a framework, called Meridian, for hosts to lookup their nearest peers in an overlay network. Each Meridian node keeps track of a small, fixed number of other hosts that are organized and maintained as a multi-resolution ring structure with exponentially growing ring radii. A node's query for its nearest peer can then be forwarded along the ring structure, which exponentially reduces the distance to the target at each query hop.

In contrast to coordinate-based systems, Meridian builds many local coordinates systems instead of a global coordinate system: This work focuses more on overlay construction and lookups, rather than distance prediction.

Application of locality in overlay-multicast

To evaluate how effective and scalable would be an overlay, using such approaches, we propose in [START_REF] Kaafar | A Locating-First Approach for Scalable Overlay Multicast[END_REF][START_REF] Kaafar | A Scalable Overlay Scheme for Application-layer Multicast[END_REF], a practical solution for large-scale and efficient multicast support, named LCC (Locate, Cluster and Conquer). First, we propose a simple and accurate location-aware process for connecting new members to the overlay network. The basic idea is to use a few nodes already involved in the constructed overlay to suggest candidate neighbors that are close to a newcomer. The latter gradually requests the suggested nodes to refine its localization in the underlying network. This locating process aims to be practical since nodes run the process locally in a 'stand-alone' fashion, and hence they do not rely on fixed landmarks measurements (needing dedicated deployed entities).

Second, we build a robust and scalable topology-aware clustered hierarchical overlay on the basis of the locating process. We propose proactive mechanisms to react to cluster leaders failures, and to smoothly manage overlay topology changes caused by crash scenarios or underlying network changes. Scalability is achieved by drastically reducing the bandwidth requirements for overlay maintenance. Robustness is obtained by mitigating the effect of dynamic environment as most changes are quickly recovered and not seen beyond clustered set of nodes. Running the locating process before that nodes join the overlay, and then clustering nearby nodes, allows to perform fast convergence to an efficient multicast delivery tree. Furthermore, it reduces management overhead and delivery tree changes imposed due to periodical refinements.

We carried out both simulations and PlanetLab experimentations to assess the effectiveness of the proposed techniques in LCC for large scale overlays, and to illustrate the system performance under particular real-world environments. Results show that our sheme incurs low overhead during both localization and data distribution. Compared to other enhancement-based and topology-aware approaches, our findings show that LCC achieves shorter convergence time and performs less link adjustments rate. At the same time, the scheme is robust to nodes' failures and performs well in terms of data distribution efficiency especially in large overlays.

However, this experience has shown its limits when it comes to exploit the locating process for multi-sessions applications. Running x applications that would rely on our locating process, would obviously result in x times measurement overhead. Moreover, this technique is specifically designed to look up for a node's closest neighbor, rather than locating the node itself according to all other nodes in the system. i.e. if one needs to determine the distance between a node and any other node in the system, we still need to perform on-demand direct measurements.

The following section discusses the major challenges of using such locating process, and more generally those of using direct measurements services.

Main drawbacks

Different approaches we discussed above try to solve either distance prediction or topology-aware routing problems with direct measurements. Meridian, for example, finds the nearest overlay node (i.e., one running Meridian) to an arbitrary node in the Internet through a large set of pings in direct response to an application-level request. In essence, this class of work solves the specific neighbor selection and overlay routing problems reactively, through a spike in activity in response to an application driven demand, while a long-running coordinate space would solve them pro-actively (as we will discuss it the following sections).

Although dynamic network performance characteristics such as available bandwidth and latency are the most relevant to applications and can be accurately measured on demand, the huge number of wide-area-spanning end-to-end paths that need to be considered in these distributed systems makes performing on-demand network measurements impractical because it is too costly and time-consuming.

To exploit network locality, if overlay networks were left with the burden of performing their own network measurements, implementations that gather all-pairs latency measurements would only be scalable for relatively small overlay deployments. For example, the all-pairs ping service managed by Stribling [START_REF] Stribling | PlanetLab All Pairs Pings[END_REF] has recently ceased operation because it became infeasible to obtain up-to-date measurements for over 500 PlanetLab nodes.

Proximity measurements, based on repeated pair-wise distance measurements between nodes, can prove to be very onerous in terms of measurement overheads. Indeed, the existence of several overlays simultaneously can result in significant bandwidth consumption by proximity measurements (i.e. ping storms) carried out by individual overlay nodes [START_REF] Rewaskar | Testing the Scalability of Overlay Routing Infrastructures[END_REF]. Also, measuring and tracking proximity within a rapidly changing group requires high frequency measurements. In contrast, the embedding techniques do not require a full mesh of RTT measurements, to predict distance between any pair of nodes in the system.

In other words, most of the systems we introduced above are dedicated to overlay construction and lookups, rather than distance prediction at the Internet scale in a timely fashion. In order to predict distances between any pair of nodes in the Internet, these non coordinate-based systems still need to perform costly measurements.

Why using Internet Coordinate-based positioning systems?

To bridge the gap between contradicting goals of performance optimization and scalability, several coordinate-based approaches to predicting network distances (as round trip propagation and transmission delay) have been proposed. As illustrated in The network distance between any two nodes is then predicted as the geometric distance between their coordinates without explicit measurements. In other words, if a node x learns the coordinate of a node y, x does not have to perform an explicit measurement to determine the RTT to y; instead, the distance between x and y in the coordinate space is an accurate predictor of the RTT. In other words, as long as a reasonably accurate position for a node can be obtained with little effort, much of the distance measurement sampling cost can be eliminated and the remaining overhead amortized over many distance predictions.

Ultimately, coordinate-based systems for network positioning aim to provide a network positioning capability to all hosts in the Internet in a scalable and a timely fashion.

The Key distinguishing properties of such predicting network distances approaches are then the following:

Peer-to-peer architecture friendly: Coordinate-based systems can naturally be incorporated into peer-to-peer applications since end hosts (nodes) can easily maintain geometric coordinates that characterize their locations in the Internet.

Extremely fast: When an end host discovers the identities of other end hosts in a peer-to-peer application, their pre-computed coordinates can be piggybacked, thus network distances can essentially be computed instantaneously by the end host. There is no additional communication delay whatsoever. The off-line computation of node coordinates is also very simple and fast.

Highly scalable: Another benefit of coordinate-based systems is that coordinates are highly efficient in summarizing a large amount of distance information. For example, in a multi-party application, the distances of all paths between K nodes can be efficiently communicated by K sets of coordinates of D numbers each (i.e. O(KD) of data), as opposed to K(K -1)/2 individual distances (i.e., O(K 2 ) of data). Thus, this approach is able to trade local computations for significantly reduced communication overhead, achieving higher scalability as demonstrated in [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF].

Structured representation:

The geometric coordinates of nodes describe a simple and yet highly structured representation of the complex Internet topology. Many algorithms can then take advantage of this structure to perform topologically aware operations on the Internet in a scalable fashion.

Fixed Landmark-based Coordinate Systems

These systems involve a centralized component (a set of landmark nodes), where other nodes compute their coordinates according to measurements to this already deployed fixed infrastructure. The concept of landmark-based positioning was initially introduced in [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF] for the design of the Global Network Positioning (GNP) system.

GNP: Global Network Positioning

In such a system, the coordinates of the landmarks are first computed by minimizing the error between the measured distances and the estimated distances among the landmark nodes. An ordinary node derives its coordinate by minimizing the error between the measured distances and the estimated distances to the landmarks. More formally, the method works as follows. N special nodes called Landmarks, denoted by LM 1 , ..., LM N are deployed in the Internet and the inter-Landmark distances are measured. The inter-Landmark distances are transmitted to a central node. The central node then computes a set of Landmark coordinates and return the coordinates to the Landmarks. The Landmark coordinates, denoted by c L 1 , ...c L N , are the result of minimizing the following objective function:

f obj1 (c LM 1 , ...c LM N ) = i,j∈1,...,N|i>j ǫ(d LM i LM j , dLM i LM j )
where d LM i LM j is the measured distance between LM i and LM j , dLM i LM j is the geometric distance between c LM i and c LM j , that we will call virtual distance 1 , and ǫ(.) is the error measurement function:

ǫ(d H1H2 , dH1H2 ) = ( d H1H2 -dH1H2 d H1H2 ) 2
GNP uses the Simplex Downhill algorithm [START_REF] Nelder | A simplex method for function minimization[END_REF] to solve the optimization problem. The Landmarks' coordinates define the bases for the geometric space. To embed an ordinary node H, H uses the Landmarks as reference points and probes all the Landmarks to obtain the Landmarks' coordinates and the network distances to the Landmarks (see Figure 2.2). It then computes its coordinate, c H , that minimize the following objective function:

f obj2 (c H ) = i∈1,...,N ǫ(d HLM i , dHLM i )
Using this method with Internet measurements, it has been shown in [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF] that the Internet network distance relationship is accurately "embeddable" in a low dimensional Euclidean space. In particular, in a 7-dimensional Euclidean space, 50% of the distance predictions have less than 10% error, 90% of them have less than 50% error, and the network positions can be used to accurately select nearby nodes in the Internet.

Next, we present different extensions of the concept of Landmarks introduced by GNP, that have been proposed in the literature.

Lighthouse

Lighthouse [START_REF] Pias | Lighthouses for Scalable Distributed Location[END_REF] is an extension of GNP that is intended to be more scalable. Although it has a special set of landmark nodes, a joining Lighthouse node does not have to query those global landmarks. Instead, it can query any existing set of nodes to find its coordinate relative to that set, and then transforms those coordinates into coordinates relative to the global landmarks. This flexibility is allowed provided each node maintains a transition matrix for global basis G. It uses linear matrix factorization such as the QR decomposition (Gram-Schmidt orthogonalization).

Virtual Landmarks

Tang and Crovella propose a coordinate system based on "virtual" landmarks.

In [START_REF] Tang | Virtual landmarks for the Internet[END_REF], the authors propose the use of the Lipschitz embedding [START_REF] Bourgain | On Lipschitz embedding of finite metric spaces in Hilbert space[END_REF] in order to embed distances between nodes in a low dimensional space obtained by compressing the full delay matrix using the PCA method (Principle Component Analysis [START_REF] Press | Numerical Recipes in C: The Art of Scientific Computing[END_REF][START_REF] Strang | Linear Algebra and Its Application[END_REF]).

The basic idea of the Lipschitz embedding is to use network distances themselves as coordinates. To find the coordinate vector -→ x i , for node i, one sets the j th component of -→ x i to the measured distance between node i and landmark j, for j = 1, ..., n.

The Lipschitz embedding can be accurate because two entities that are close to each other in a metric space typically have similar distances to many other entities. Thus two nearby points in the original metric space may have very similar coordinate vectors, and so may map to nearby points under the Lipschitz embedding.

This study also explores methods to reduce the number m of Landmarks that need to be probed without adversely affecting the accuracy.

By applying the PCA method [START_REF] Press | Numerical Recipes in C: The Art of Scientific Computing[END_REF][START_REF] Strang | Linear Algebra and Its Application[END_REF] to an m × n matrix A in which row i is the initial n-dimensional coordinate vector x i for node i, we can map each x i to a new y i in a lower dimensional space, while approximately preserving distances. That is we map

x i ∈ R n to y i ∈ R r such that r ≪ n and || x i -x j || ≈ || y i -y i || for all i, j ∈ 1, ..,m.
The mapping from x i to y i obtained via PCA is a linear one. That is, y i = M ˙ x i for some M (where M is an r × n matrix). Final coordinate of node i (the components of y i ) can be seen as distances to virtual landmarks. The distance to a virtual landmark is defined as a linear combination of distances to actual landmarks.

A parallel study [START_REF] Lim | Constructing internet coordinate system based on delay measurement[END_REF] has also suggested the use of the PCA method to compute network positions. This study analyzes the difficulty in the nonlinear optimization of Euclidean embedding, and shows that a PCA-based schemes is more computationally efficient. Distributed versions of these methods however remain to be studied and developed.

NPS

The Network Positioning System (NPS) [START_REF] Ng | A Network Positioning System for the Internet[END_REF] extends GNP into a hierarchical coordinate system, where all nodes could serve as landmarks (reference points) for other nodes. It aims to recover "gracefully" from either landmark failures, or situations where these special entities of the system and their network access links become performance bottlenecks. The main departure from GNP is that any node that has determined its position can be chosen by a membership server to be a reference point for other nodes. Actually, the membership server randomly chooses eligible nodes to become reference points when the permanent landmarks are too heavily loaded or unavailable. However, to ensure consistency, NPS imposes a hierarchical position dependency among the nodes (see Figure 2.3). Given a set of nodes, NPS partitions them into different layers. A set of 20 landmarks are placed in layer-0 (or L 0 ), the top layer of the hierarchy (these permanent landmarks are the fixed infrastructure used to define the bases of the Euclidean space model), and an 8-dimension Euclidean space is used for embedding. Each node in layer L i randomly picks some nodes in layer L i-1 as its reference points. The relative error of the distance prediction between a pair of nodes is defined as:

relative error = |actual -virtual| min(actual, virtual)
In [START_REF] Ng | A Network Positioning System for the Internet[END_REF], authors argue that a 3-layer NPS system is already very accurate and can support more than 2 billion nodes. NPS includes a strategy for mitigating the effects of simple malicious attacks. Indeed, malicious nodes could potentially lie about their positions and/or inflate network distances by holding onto probe packets. The basic idea is to eliminate a reference point if it fits poorly in the Euclidean space compared to the other reference points. Each node, when computing its coordinate, based on measurements from different reference points, would reject the reference that provides a relative error significantly larger than the median error of all other reference nodes. Specifically, assume there are N reference points R i , at positions P Ri , and the network distances from a node H to these are D Ri . After H computes a position P H based on these reference points, for each R i , it computes the fitting error E Ri as |distance(P H ,P Ri )-D Ri | D Ri . Then the requesting node, H, decides whether to eliminate the reference point with the largest E Ri . The criterion used by NPS is that if:

max i E Ri > 0.01 (2.1)
and,

max i E Ri > C × median i (E Ri ), (2.2)
where C is a sensitivity constant, then the reference point with max i E Ri is filtered (i.e. H tries to replace it by another reference point for future repositioning).

In this thesis, we studied NPS as a representative of the landmark-based coordinate systems. More specifically, in the next chapter, we will show how this infrastructurebased system can, under some well chosen attack strategies, be vulnerable to sophisticated attacks that are aimed at defeating its defense mechanism.

Decentralized Internet Coordinate Systems

This class of approaches extends the embedding concept, either by generalizing the role of landmarks to any node existing in the system, or by eliminating the landmark infrastructure. Decentralized Internet coordinate systems can be seen as peer-to-peer network positioning systems.

Practical Internet Coordinates: PIC

Practical Internet Coordinates (PIC) [START_REF] Costa | Practical Internet coordinates for distance estimation[END_REF] is one of the recent decentralized coordinate systems using again the Simplex Downhill method to minimize an objective distance error function (sum of relative errors). It does not require explicitly designated landmarks. In PIC, the joining node can pick any node whose coordinate have already been computed to be a landmark. It uses an active node discovery protocol to find a set of nearby nodes to use to compute coordinates. Different strategies such as random nodes, closest nodes, and a hybrid of both, are proposed.

PIC aims to defend the security of its coordinate system against independent malicious participants using a test based on the triangle inequality. Basically, the test relies on the observation that the triangle inequality holds for most triples of nodes in the Internet. Therefore, PIC assumes that for most triples of nodes a, b and c , d(a, b) + d(b, c) ≥ d(a, c), where d(i, j) denotes either the measured network distance between nodes i and j or the virtual distance in the geometric space.

The intuition behind the security test of PIC is as follows. An attacker that lies about its coordinate or its distance to the joining node is likely to violate triangle inequality. The joining node uses the distances it measured to each landmark node and the coordinates of the landmarks to check for violations of the triangle inequality. It then removes from its proper set of landmarks used for positioning, the nodes that most violate the triangle inequality.

Let's denote by n a new node joining PIC, that is computing its coordinate using i and j, two distinct Landmarks. This is illustrated in figure 2.4. If d(n, i) is the measured distance between n and i and d ′ (i, j) is the predicted virtual distance (using coordinates) between i and j, all of the following inequations should hold:

d(n, i) ≤ d(n, j) + d ′ (i, j) d(n, i) ≥ d(n, j) -d ′ (i, j) d(n, i) ≥ d ′ (i, j) -d(n, j)
The first inequality imposes an upper bound on the measured distance to i and the other two impose a lower bound of |d(n, j)d ′ (i, j)|. For each landmark used for coordinates computation, the security test checks whether the upper bounds and lower bounds defined by each landmark j are satisfied by i and computes the following two metrics:

lower i = N j=1 |d(n, j) -d ′ (i, j)| -d(n, i) if |d(n, j) -d ′ (i, j)| > d(n, i), 0 Otherwise
where N is the number of distinct Landmarks used by n for positioning in the system. upper i is the sum of the deviations above the upper bounds, and lower i is the sum of the deviations below the lower bounds. The security test computes the maximum value of both metrics for all Landmarks used by n and removes the corresponding node. Then, the joining node uses the Simplex to compute its coordinates with the remaining landmarks. This process is repeated a fixed number of times.

In [START_REF] Costa | Practical Internet coordinates for distance estimation[END_REF], authors show that such security test can deal with up to 20% of malicious nodes existing in the system. However, [START_REF] Lua | On the accuracy of Embeddings for Internet Coordinate Systems[END_REF] and [START_REF] Zheng | Internet Routing Policies and Round-Trip Times[END_REF] indicate that network RTTs commonly and persistently violate the triangle inequality. A security mechanism based on the fact that the triangle inequality systematically holds, may degrade the performance of a clean system, without malicious nodes inside.

Vivaldi

Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] is a fully distributed algorithm, requiring no fixed network infrastructure and no distinguished nodes. It is based on a simulation of springs, where the position of the nodes that minimizes the potential energy of the springs also minimizes the embedding error.

A new node computes its coordinates after collecting latency information from only a few other nodes. Basically, Vivaldi places a spring between pairs of nodes (i, j) with a rest length set to the known (measured) RTT between them. The current length of the spring is considered to be the distance between the nodes as estimated in the coordinate space. The potential energy of such a spring is proportional to the square of the displacement from its rest length: the sum of these energies over all springs is the error function that Vivaldi nodes try to minimize.

An identical Vivaldi procedure runs on every node. Each sample provides information that allows a node to update its coordinate. Each sample used by a node i, is based on measurement to a remote node j, its coordinate x j and the estimated error reported by j, e j . The algorithm handles high error nodes by computing weights for each received sample.

The relative error of this sample, e s , is then computed as follows:

e s = | x j -x i -RTT measured | / RTT measured
The node then computes the sample weight balancing local and remote error : w = e i /(e i + e j ), where e i is the node's current (local) error. This sample weight is used to compute an adaptive timestep, δ defining the fraction of the way the node is allowed to move toward the perfect position for the current sample: δ = C c × w, where C c is a constant fraction < 1. The node then updates its local coordinate as follows:

x i = x i + δ • (RTT measured -x i -x j ) • u(x i -x j )
where u(x ix j ) is a unit vector giving the direction of i's displacement. Finally, it updates its local error as e i = e s × w + e i × (1w).

Vivaldi considers a few possible coordinate spaces that might better capture the underlying structure of the Internet. Coordinates embedding maps the network distances into different geometric spaces, for instance 2D, 3D or 5D Euclidean spaces, spherical coordinates, etc. Vivaldi also introduces the height model, consisting of a Euclidean coordinate space augmented with a height. The Euclidean portion models a high-speed Internet core where latencies are proportional to geographic distance, and the height models the time it takes packets to travel the access link from the node to the core.

In [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF], authors show that the more dimensions a Euclidian space has, the more accurate the Vivaldi system is. Moreover, results show that height vectors perform better than both 2D and 3D Euclidean coordinates, as the height model is a better approximation of the hyperbolic curvature of the Internet [START_REF] Shavitt | The curvature of the Internet and its usage for overlay construction and distance estimation[END_REF].

The reader should finally note that, although Vivaldi defends against high-error nodes, it does not address issues related to malicious behaviors. In the next chapter, we will study how such vulnerability can be exploited to spoil and seriously disrupt the operations of the Vivaldi system. The latter is studied in this thesis as a representative of decentralized Internet coordinate-based systems.

The Big-Bang Simulation: BBS

Big-Bang Simulation (BBS) [START_REF] Shavitt | Big-bang simulation for embedding network distances in euclidean space[END_REF] performs a simulation, similar to Vivaldi's massspring system, to calculate coordinates, simulating an explosion of particles under a force field. The simulation models each particle's momentum explicitly and then introduces friction in order to cause the simulation to converge to a stable state.

Discussion and Conclusions

Although coordinate-based systems have attractive properties for latency prediction on the Internet, one could criticize them for requiring expensive maintenance and having prediction accuracy worse than direct measurement methods such as Meridian. At the very least, triangle inequality violations [START_REF] Zheng | Internet Routing Policies and Round-Trip Times[END_REF] could be a major barrier for the accuracy of such systems. In [START_REF] Lua | On the accuracy of Embeddings for Internet Coordinate Systems[END_REF], authors also observed that absolute relative error may not be the major indicator of the quality of an embedding as experienced by a user. They showed that, using other accuracy metrics that attempt to quantify various aspects of user-oriented quality (such as Relative Rank Loss or Closest Neighbors Loss), the quality of the coordinate-based systems is not as high as that suggested by the use of absolute relative error.

Moreover, choosing the suitable geometric space for coordinate embedding, and more generally, to model the Internet has received much attention by the research community, and has been shown to be a challenging task. Basically, coordinate systems have concentrated on pure Euclidean spaces or other simple geometric spaces like the surfaces of spheres and tori. In [START_REF] Shavitt | The curvature of the Internet and its usage for overlay construction and distance estimation[END_REF], authors introduced a new coordinate space that places nodes some distance "above" a Euclidean space (height model). Shavitt and Tankel [START_REF] Shavitt | The curvature of the Internet and its usage for overlay construction and distance estimation[END_REF] proposed using a hyperbolic coordinate space to model the Internet. The hyperbolic model may address a shortcoming of the Vivaldi's height model that implicitly assumes that each node is behind its own access link. If two nodes are behind the same high-latency access link, the height model will incorrectly predict a large latency between the two nodes: the distance down to the plane and back up.

Nevertheless, current live implementations and deployments of Internet coordinates systems in the 'wild', show that using such systems is beneficial for P2P applications, and overlays ( [10,[START_REF] Peterson | A Blueprint for Introducing Disruptive Change in the Internet[END_REF][START_REF] Ledlie | Stable and Accurate Network Coordinate[END_REF]) that rely on the notion of network topologyawareness. In [START_REF] Ledlie | Network Coordinates in the Wild[END_REF], using the Azureus BitTorrent network as a testbed, authors show that even if, live, large-scale network coordinate systems behave somewhat differently than the PlanetLab and simulation-based counterparts, Azureus' coordinates and, by inference, Internet-scale coordinate-based systems in general, were able to tackle a basic goal: quickly and efficiently optimizing anycast decisions based on correct latency estimates2 . Ledlie et al. showed that incorporating Vivaldi's coordinates in a one million node Azureus network, improves the efficiency of the latter. However, this is achievable by implementing specific techniques in Azureus in order to support coordinates in an effective way. Basically, to improve the accuracy and stability of coordinate-based systems, several works proposed different techniques: latency filters and application-specific coordinate updates, in order to make the distinction between constantly evolving "system-level" coordinates and "useful application-level" coordinates that should be stable [START_REF] Ledlie | Network Coordinates in the Wild[END_REF]. It should also be noticed that De Launois et al. [START_REF] De Launois | A Stable and Distributed Network Coordinate System[END_REF] propose a different method for stabilizing coordinates: asymptotically dampening the effect of each new Vivaldi measurement. While this factor does mitigate oscillations in a fixed network, it prevents the algorithm from adapting to changing network conditions. gossip-based coordinates update, rather than piggybacked coordinates on to application-level messages. This technique has been shown to expand the size of the working set of Vivaldi, expanding the set of neighbors for each node, and then improving its accuracy [START_REF] Ledlie | Network Coordinates in the Wild[END_REF]. violator exclusion, inspired by the removal of a small percentage of the nodes with the largest triangle inequality violations from the Azureus latency matrix. Removing 0.5% percent of nodes leads to 20 percent improvement in global accuracy [START_REF] Ledlie | Network Coordinates in the Wild[END_REF]. These observations confirm a theoretical work that showed how to decrease embedding distortion by sacrificing a small fraction of distances to be arbitrarily distorted [START_REF] Bartal | On metric ramsey-type phenomena[END_REF]. These results mainly show that if a mechanism could prevent a small percentage of nodes (Triangle inequality violators) from affecting the rest of the system, it would improve overall accuracy.

Finally, it should be noted that if latency is the primary network metric that has been embedded in coordinate spaces, there are at least two approaches to including other network characteristics, such as bandwidth and jitter. These could be made as additional dimensions in existing latency space. For instance, it has been demonstrated that per node characteristics, such as load, can be included to form a cost space that allows hot-spot detection [START_REF] Shneidman | A Cost-Space Approach to Distributed Query Optimization in Stream Based Overlays[END_REF]. Second, Oppenheimer et al. and Lee et al. have investigated the inverse correlation between latency and bandwidth [START_REF] Lee | Measuring bandwidth between planetlab nodes[END_REF][START_REF] Oppenheimer | A Case for Informed Service Placement on PlanetLab[END_REF]. The correlation Oppenheimer found implies that network-aware decisions made in the latency space may result in good bandwidth characteristics.

In conclusion, while developing coordinate-based systems with perfect accuracy is a long-term challenge, current approaches are already sufficiently accurate for most applications and allow trade-offs between accuracy and measurement overhead for dynamic topology-aware overlays.

But it should also be noticed that these come at the expense of slow convergence times ranging from tens of seconds to several minutes [START_REF] Ledlie | Network Coordinates in the Wild[END_REF]. This is several orders of magnitude slower than what is achievable with direct 'on-demand' distance measurements between nodes and is often unacceptable for topology-aware applications whose aim is to quickly identify "best nodes".

We therefore contend that coordinate-based positioning systems are an attractive proposition if they are deployed as a service: every node could run a coordinate system daemon at boot time which would then be capable of providing accurate coordinate estimates to applications and their overlays on request. In essence, the coordinate system could then be seen as a component of a "virtual infrastructure" that supports a wide range of overlays and applications.

But a system providing an "always-on and large scale coordinate service" would also likely be a prime target for attacks, as its disruption could result in the mis-functioning or the collapse of very many applications and overlays. Indeed, as the use of overlays and applications relying on coordinates increases, one could imagine the release of worms and other malware whose purpose is to attack the virtual infrastructure as a whole.

Securing the base of distance prediction for many applications would then be much more critical, than detailing security of the artifacts of any particular application. Moreover, regardless of the accuracy of these Internet coordinate systems, securing them is a necessary condition to their deployment. In this context, this thesis provides the missing piece in the design of internet coordinates systems.

DISRUPTING INTERNET COORDINATES SYSTEMS

Introduction

Most, if not all, of current proposals for coordinates systems assume that the nodes partaking in the system cooperate fully and honestly with each other, that is that the information reported by probed nodes is correct. This could also make them vulnerable to malicious attacks. In particular, insider attacks executed by (potentially colluding) legitimate users or nodes infiltrating the system could prove very effective. In this chapter, we will identify potential attacks against such coordinate-based systems, and we will focus on studying how attackers can destabilize both the Vivaldi and NPS coordinate systems: Vivaldi as a prominent representative of purely peer-to-peer-based (i.e. without infrastructure support) positioning systems, and NPS as typical of landmarkbased systems.

Threats and Attack Classification

We classify attacks and identify threats that malicious nodes may seek to carry out on coordinate-based positioning systems. We consider malicious nodes that have access to the same data as legitimate users, often called Insiders. This means that participants 31 are not completely trusted entities, or that malicious nodes have the ability to bypass any authentication mechanisms. Malicious nodes are able to send misleading information when probed, or send manipulated information after receiving a request or affect some metrics observed by chosen targets. The main classes of attacks on positioning system behavior are:

1. Disorder: the main goal of this attack is to create chaos as a form of denial of service (DoS) attack. This results in high errors in the positioning of nodes, or the non-convergence of the embedding algorithm. The attack would then just consist in maximizing the relative error of nodes in the system, either passively by not cooperating or falsifying its coordinates or by actively delaying probes.

2. Isolation: where nodes would be isolated in the coordinate space. The attack could target a particular node, in order to convince the victim that it is positioned in an remote zone of the network. The ultimate goal of such an attack can be, for instance, obliging the victim to connect to an accomplice node as the closest node in that zone, in order to perform traffic analysis or packet dropping, man in the middle attacks, etc. One way a malicious node can conduct this attack is to delay probes sent by the victim, and to falsify its own coordinates, so that the victim's computed coordinates are set to a value large enough, to be far from other nodes.

3. Repulsion: where a malicious node would convince its victims that it is positioned far from them in order to reduce its attractiveness, and then, for instance, alleviate its resource consumption by not cooperating in the application progress. Ways to perform such attacks are to make its conditions (performance, position) seem worse than they actually are. This is accomplished by means of delaying measurement probes and/or by manipulating the coordinates transmitted to other nodes.

System Control:

This attack is possible on coordinate-based systems that allow "normal" nodes to be considered as landmarks, i.e. most of the existing systems except the centralized systems. In hierarchical systems for example, such as NPS, nodes would try to get higher in the hierarchy in order to fool and influence the maximum number of correct nodes.

These classes of attacks can either be carried out by malicious nodes in an independent manner or as a conspiracy created by colluding nodes. Collusion is likely in scenarios where attack propagation happens through the now well tested means used in today's DDoS attacks (e.g. worms, etc.).

It should be noted that all attacks, be they explicitly aimed at disrupting the whole system or skew the coordinates of a single node, will often result in some distortion of the coordinate space. This is because of the possible cooperation between the nodes that will act as a catalyzer to the propagation of errors to other (non directly targeted) nodes.

Performance Evaluation

Performance Indicators

We use the relative error (as defined specifically for each algorithm in the last chapter) as our main performance indicator. We compute the average relative error over all nodes to represent the accuracy of the overall system. Since our focus is on measuring the impact of malicious nodes on the system, we also introduce the relative error ratio (also called "Ratio" for simplicity), which is the relative error measured in presence of malicious nodes normalized to the performance of the system without cheats used as the best case scenario (i.e. error ratio = error/error ref ). Obviously, a value for the error ratio above 1 indicates a degradation in accuracy.

As the worst case scenario, we also compute the relative error of a coordinate system where nodes choose their coordinates at random. In this random scenario, all nodes choose their coordinate components randomly in the interval [-50000, 50000] (for each dimension of the coordinate).

In this chapter, we will concentrate on two systems: NPS (chapter 2, section 2.3.4) as a representative of the landmark-based approach; and Vivaldi (chapter 2, section 2.4.2) as a representative of the infrastructure-less approach.

We quantified the impact of the attacks we described above through simulations of different potential scenarios. In the following, we present the details of our simulation set-up.

Simulation Set-up

We used the "King" dataset to model Internet latencies based on real world measurements. This dataset contains the pair-wise RTTs between 1740 Internet DNS servers collected using the King method [START_REF] Gummadi | King: Estimating Latency between Arbitrary Internet End Hosts[END_REF]. This was used to generate a topology with 1740 overlay nodes, from which we derived various group sizes by picking nodes at random (unless otherwise stated, in the simulations, the group consists of all the 1740 nodes). Each scenario was repeated 10 times with the malicious nodes selected at random within the group. We consider groups with 10%, 20%, 30%, 40%, 50% and 75% of malicious nodes. In view of the infection rates of recent worm epidemics, we believe these values to be realistic, both during and for a long time after an outbreak.

For the Vivaldi simulation scenarios, we used the p2psim discrete-event simulator [START_REF]A simulator for peer-to-peer protocols[END_REF]. Each Vivaldi node has 64 neighbors (i.e. is attached to 64 springs), 32 of which being chosen to be closer than 50 ms. The constant fraction C c for the adaptive timestep (see section 2.4.2) is set to 0.25. These values are those recommended in [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF]. The system is considered to have stabilized when all relative errors converge to a value varying by at most 0.02 for 10 simulation ticks. We observed that Vivaldi without malicious nodes always converged within 1800 simulation ticks, which represents a convergence time of over 8 hours (1 tick is roughly 17 seconds). Unless otherwise stated, our results are obtained for a 2-dimensional coordinate space.

For NPS, we developed our own event-driven network simulator, based on the description of the protocol in [START_REF] Ng | A Network Positioning System for the Internet[END_REF] and a reference implementation of the protocol1 . Unless otherwise stated, as recommended in [START_REF] Ng | A Network Positioning System for the Internet[END_REF], we considered an 8-dimensional Euclidean space for the embedding. In layer-0, a set of 20 well separated permanent Landmarks are chosen. 20% of nodes are randomly chosen as reference points, in each subsequent layer. For the security mechanism of NPS, the sensitivity constant C was set to 4.

Finally, in this thesis, we consider all the attacks in an "injection" context, where the malicious nodes are introduced in a system that has already converged. This is in contrast with a "genesis" attack where the malicious nodes are present from the system's creation time (which we studied in [START_REF] Kaafar | Real attacks on virtual networks: Vivaldi out of tune[END_REF] for Vivaldi). The former is more realistic in a practical setting, generalizes the attack strategies' impact, and reflects the emergence of threats carried out by malware in the Internet.

Attacks on Vivaldi

We first discuss ways to achieve disorder attacks in Vivaldi. As it is a fully-distributed algorithm relying on cooperation of nodes in order to ensure accuracy of the computed coordinates, it seems easy to fool honest nodes.

Disorder Attack

The disorder attack has no specific objective, but false coordinate computations and high positioning error. When solicited, a malicious node sends a randomly selected coordinate x j , associated with a very low error, e j = 0.01. Moreover, each node's measurement is delayed by a randomly generated value in [100..1000] ms. In this first scenario, it is not necessary to care about lie consistency, as Vivaldi uses error weights sent along with the responses to probes to adjust the adaptive timestep. Even if the measured distance RTT measured to malicious node j is not consistent with the coordinates x j , the victim i would consider itself as a high error node, and would try to adjust its coordinates by a great adaptive timestep value, due to the fact that j sends a low error. valdi. we can see that the topology we used exhibits a clear "cluster" structure that disappear in the presence of only 10% of malicious nodes. This is because, in this disorder attack, the attackers keep "jolting" the system and the errors introduced "ripple" through the system, propagated through normal operations of the honest nodes. Figure 3.2 depicts the relative error ratio variation in function of time, for our full set of 1740 nodes, representative of the impact of the malicious nodes on the system. It is clear that enough attackers can quickly destabilize a converged system and seriously reduce the system accuracy. It is interesting to note that, in the presence of enough malicious nodes, despite the system converging in the sense that the relative errors at each node stabilize, these errors are so high that a great variation of the coordinates of a node barely affects the associated error. In other words, the coordinates of the nodes keep showing great variations and do not stabilize but the error introduced by such constant movement is stable because there is already so much chaos in the system. In essence, the system is deemed to converge because it doesn't get any better nor any worse. Figure 3.3 shows the cumulative distribution of the relative error of the victims of an injected disorder attack. We clearly see that from 30% of malicious nodes the impact on the system can be considered as very serious with many nodes seeing a large increase in their relative errors. For a proportion of 50% or more malicious nodes, the system collapses with over 35% of the honest nodes computing coordinates that are Figure 3.4 represents the impact of the space dimension on the attack. In this figure, the average relative error of honest nodes is measured after re-convergence. We see that the more accurate the Vivaldi system is in the absence of malicious nodes, the more vulnerable it is to the disorder attack. This is because the variation of more coordinate components for a point in a larger space results in higher displacement in that space. This observation is compounded for the 2-dimensional space augmented by a height as a variation of the height yields a greater effect on the node displacement. We also observe that in most cases, Vivaldi with half the population of malicious nodes is worse than a random coordinate system. Figure 3.5 shows the impact of the attack as a function of the system size as measured a long time after the attack started. We see that a larger system is more difficult to impact for a same proportion of attackers. This is consistent with the fact that a larger Vivaldi system is more accurate, but also establishes that Vivaldi finds increased strength in a larger group. Put simply, this is because as one increases the number of springs in the system, the energy needed to disrupt it is higher. In our case, a larger group means more "good" forces to counteract and dissipate the effect of the malicious

Repulsion Attack

In this scenario, malicious nodes are trying to isolate some nodes in the network, either by repulsing a set of targets away from other nodes in the coordinate space, or by repulsing all requesting nodes away from a selected target. The first attack consists in fixing coordinates where to isolate all requesting nodes, say X target . It is important to notice that this value is set high enough to allow lie consistency. This means that the predicted distance after the lie should be equal to the measured distance. In fact, since we assume that a malicious node cannot shorten a distance measurement, but can however delay it, we must set the coordinates of both the victim and the malicious node to be consistent with this fact. Although for most network positioning systems, application probes are used, for generality purposes we design and test the attacks assuming ICMP ping probes. We assume here that malicious nodes know the current coordinates of their targets, X Current , by means of previous requests for example. Malicious nodes are then able to compute the needed RTT that is consistent with the lie, RTT = ( X target -X Current /δ)+ X target -X Current and to delay the measured RTT by: RTT needed -2 • (ReceivedTimestamp -SendTimestamp). Each malicious node is selecting a random coordinate that is far away from the origin.

The effect of this attack can be visualized in figure 3.6, for our full-size system and ative error after convergence in an repulsion attack. The gentler slope of the curves indicates that the impact of this type of attack is greater than in the case of a disorder attack (see fig. 3.3). This is because a repulsion attack is more structured and more consistent than a disorder attack, since the chosen target coordinate is always the same for every victim-attacker pair.

We study the effect of space dimension on this attack in figure 3.8. Again, the results confirm that the more accurate the system is without malicious nodes, the more vulnerable it is to attacks, which highlights a fundamental trade-off between accuracy and vulnerability.

So far, the repulsion attack consisted in each attacker attacking every other node. Figure 3.9 shows the effect of a modified repulsion attack where each attacker independently attacks a subset of the other nodes. Each attacker chooses its own target subset independently, along with their target coordinate values. However, the target subset size is fixed and equal for all attackers. We see that small subsets chosen in- dependently result in a less effective attack and that there is no great difference in effectiveness when the set of attackers constitutes less than 30% the population. This can be explained by the fact that in such conditions the attack gets "diluted", giving the system plenty of opportunity to correct itself through nodes that are under no, or very little, attack. Figure 3.10 shows the response of a system under injection repulsion attack as a Figure 3.10: Injection Repulsion Attack on Vivaldi: effect of system size function of system size. As in the case of a disorder attack, larger systems reduce the impact of the attack. However, because a repulsion attack is much more consistent than a disorder attack, the system is less effective at countering the effects. This is why we observe higher values for the average relative error and a much gentler slope of the curve than in figure 3.5.

Colluding Isolation Attack

This is a repulsion attack, aiming to isolate a particular target, where the attackers behave consistently in a collective way. They could, for instance, try and move all honest nodes consistently away from a same designated target node (strategy 1). That is, they agree on a distance from the chosen node for each victim and collectively and consistently direct victims towards their designated coordinate. effects for such an attack. In this first scenario of the colluding isolation attack, we observe that the "cluster" structure originally present in figure 3.11(a), disappears in the presence of only 10% of malicious nodes. Honest nodes are moved away from their correct positions to the borders of the coordinate space, and malicious nodes keep their positions "around" the target node. Figure 3.12 depicts the effects of a colluding isolation attack on the system. The salient result is that the system can quickly become worse than a random coordinate system. Indeed, from 30% of malicious nodes in the system, the accuracy becomes equal or worse than if nodes chose their coordinates at random. This clearly demonstrates that colluding attacks are very potent due to their better structure and can have a great adverse impact on overall system performance.

Another strategy (strategy 2) of colluding isolation attack is for the attackers to set their coordinates in a remote area of the coordinate space (so that they are clustered in that area) and then to choose a victim target node and convince it that its own coordinate is within the attacker cluster. The target coordinate is set before the attack begins and agreed by all attackers.

We observe in figure 3.13 the variation of the relative error of the target node through time. We see that the first scenario of colluding isolation attack (consisting in repelling all other honest nodes from a chosen target) is more effective than trying to lure a target into a remote area of the space. Intuitively, this is because much more error is introduced in the system when more nodes are pushed away from their system under both types of colluding attacks.

Combined Attacks

In the context of system offering an always-on and large scale coordinate service, it is plausible to assume a constant and permanent low level of malicious nodes. Indeed, in the previous sections we have examined the effects of attack outbreaks. But in the wild, as has already been observed after major worm outbreaks and security warnings, once an outbreak has been contained and resolved, one can expect that some small portion of the systems are not upgraded for a very long time after the release of the necessary patches. This is especially true in the case of systems that are under many different administrative controls (as is the case for home personal computers). Figure 3.15 shows the impact of such low level combined attacks on Vivaldi, where colluding nodes implement strategy 1 of the colluding isolation attack. In these combined attacks, the percentage of malicious nodes of each type is the same. This figure shows that fairly low level of malicious nodes can still have a sizeable impact on the overall system performance, which, in turn, indicates that return to normality after an attack may take an extremely long time, if at all possible.

Finally, figure 3.16 confirms that larger systems are more resilient and recover better than smaller ones.

Attacks on NPS

Recall from the previous chapter, in section 2.3.4 that the NPS system includes a strategy for mitigating the effects of malicious attacks. Therefore, we experimented with NPS in both a secure and non secure version. Unless stated otherwise, the security mechanism is switched on. Note also that we consider the ideal, hypothetical case where the landmarks are highly secure machines that never cheat. The results we present in the following sections can therefore be considered as best case scenarios from a security point-of-view, as the impact of attacks could be much more severe should our security of landmark hypothesis not hold.

Injection of Independent Disorder Attackers

In this first attack, when malicious nodes are chosen as reference points by the membership server (or when an already active reference point gets infected by malware), they perform simple attack that consists in transmitting the correct coordinates of the (malicious) reference point to the victim, and delaying measurement probes without caring about lie consistency. Figure 3.17 depicts the average relative error variation in function of time, while injecting after convergence of the system, a percentage of malicious nodes. When the malicious reference node detection mechanism is off, we notice the sharp climb in relative error when 20% of malicious nodes join the system. The accuracy of NPS is destroyed when cheating nodes get introduced in layer-1 of the measurement hierarchy. On the other hand, the malicious reference node detection mechanism is shown to be highly effective in combating such a malicious population of up to more than 30% of the overall population. However, a population of 40% or more malicious nodes in the system defeats the NPS security mechanism. This can be explained by the fact that the security mechanism relies on simple statistical properties of the observed errors (i.e the median) to filter out perceived outliers. In the presence of enough malicious nodes serving as reference points, the computation of the median itself gets skewed sufficiently that malicious behaviour is assimilated to normal behaviour. The cumulative distribution function of the measured average relative error shown in figure 3.18 confirms previous results. The gentler slope, and heavy tail feature, of the 40% and 50% curves when security is on indicates the impact of the attack when enough malicious nodes are introduced in the system. We observe that when introducing 40% of malicious nodes, only 50% of honest nodes would re-converge to a relative error less than 0.5. Figure 3.19 shows the effect of space dimension when NPS is subjected to a simple disorder attack. Just as in the Vivaldi case, this experiment proves again that the more accurate the system is without malicious nodes, the more vulnerable to attacks it is. In particular, we observe that with more dimensions used in the coordinate space, the NPS system is much more vulnerable to a smaller portion of malicious nodes. We observe that systems running with 6 and 8 dimensions still can prevent against a minority of malicious nodes, whereas a simple attack can destabilize a 10 or 12-dimensions NPS system more easily. In the later cases, when malicious nodes only constitute 20% of the population, the relative error climbs to more than 1. From 50% of malicious nodes injected in the system, the accuracy becomes equal or worse than if nodes chose their coordinates at random. This is explained by the fact that the more dimensions are used, the more "chances" malicious nodes get to become reference nodes, creating greater confusion among the honest nodes that depend on them in the layers below. Moreover, as in the Vivaldi case, more dimensions result in greater displacement in the coordinate space for the victim.

Injection of Naive Anti-Detection Disorder Attackers

In this section, we consider an attack whose primary objective is to try and defeat the NPS security mechanism, described in chapter 2 section 2.3.4. To this end, attackers will lie consistently about their position and inflate network distances by that corresponding amount, while paying particular attention that the relative error computed by the victim is lower than 0.01. Doing so essentially negates the very first condition checked to detect malicious nodes (see section 2.3.4 in chapter 2), in effect shutting down detection of the attackers.

First, we consider that malicious nodes know their targets' coordinates with a probability p = 1/2. We discuss next the effect of coordinate information on the efficiency of the attack. The target coordinate information allows first to better estimate the distance between the target and the attacker and second to compute the direction defined in the coordinate space by the nodes themselves. When not available, the malicious node sets a random direction and estimates the distance between itself and the target as ReceivedTimestamp -SendTimestamp.

As illustrated in figure 3.20, the attack consists in delaying the victims' probes by

P ′ Ri -P Ri = d ′ such that P ′ Ri -P Ri ≫ d
and then send coordinates P ′′ Ri such that

P ′′ Ri -P Ri < 0.01 P ′ Ri -P Ri
It is easily shown that

E Ri < 0.01 ⇒ d ′′ > α + 1.99 0.01 • d with α d = d ′′ -d ′ .
To make the attack harder and make the security mechanism of NPS behave in more realistic way, we add a probe threshold condition to each probe, such that a probe would be considered by the requesting node as suspicious if the RTT it measured was above that threshold. Such probes are then discarded. In the following simulations, the probe threshold is set to 5 seconds. In a first scenario, we consider malicious nodes that ignore this probe threshold, yielding a so-called naive anti-detection disorder attack.

In figure 3.21, we observe the average relative error variation after injection of ma- licious nodes in a converged NPS system. We see that this attack has a bigger impact on the whole system than the simple disorder attack (see figure 3.17), causing greater average relative errors. We also observe that the attack is very effective at defeating the security mechanism, with the security-protected relative errors only trailing marginally the errors observed when no security mechanism but the probe threshold is employed. This is despite the attacker guessing half of the time, and could therefore appear surprising. However, the reader should note that the NPS security mechanism discards at most one malicious reference point at each positioning (i.e. the one yielding the greater error), giving the malicious nodes potentially several reprieves on bad guesses.

As for the Vivaldi system, we note that in presence of only a minority of malicious nodes, despite the system converging in the sense that the relative errors at each node stabilize, these errors are so high that a great variation of the coordinates does not affect the associated error.

We measured the impact of dimensionality and group size on the effectiveness of this attack and found the now expected results that higher precision (i.e. higher dimensionality) was more affected while larger groups present a better immunity.

More interesting in this attack is the effect the knowledge of the attacker has on its effectiveness. In figure 3.22, we show the relative error ratio for various probabilities that the attacker knows a victims's coordinates prior to striking. We see that in the presence of a small malicious population, full knowledge of victims' coordinate can almost triple the effectiveness of the attack compared to the pure guess work case. However, as the population of malicious nodes grows, the benefits of more knowledge diminish. This confirms again that, regardless of the sophistication of the attack, the NPS security system soon gets overwhelmed when the population of malicious node exhibits a certain critical mass. As figure 3.23 shows by representing the ratio of malicious nodes filtered to the overall number of filtered nodes by the security mechanism, this critical mass is about 20% (about half the needed population of malicious node compared to the simple disorder attack). Furthermore, this figure also confirms that, as more and more malicious nodes are able to operate in all impunity, the errors they introduce in the positioning of honest nodes result in higher false positive rates with the security mechanism filtering out more and more (mis-positioned) honest reference points. But because at most one reference point gets filtered per positioning, these false positives actually create some extra protection for the malicious ones.

Injection of Sophisticated Anti-Detection Disorder Attackers

We now present a modification of the previous attack where the malicious nodes make an attempt to not only defeat the NPS security mechanism but also avoid de-tection by the probe threshold mechanism. To do so, an attacker will only interfere with the positioning process of nodes known, or believed, to be nearby. Indeed, if we recall the discussion in section 3.5.2, with a probe threshold of 5 s and α = 2, then d ′′ + d < 5s ⇒ d < 25ms in order to avoid detection by the NPS security system, d being the real distance between an attacker and its victim. As this attack is bound to be less detectable by the security mechanisms than the previous one which already yielded small differences between the "security on" and "security off" cases, only results in the presence of these security mechanisms are presented here. Unless stated otherwise, the attackers guess the position of their victims half of the time.

Figure 3.24 shows the cumulative distribution function of the relative errors in a system under sophisticated anti-detection disorder attack. Clearly, this attack is devastating on the overall accuracy of the coordinate system, despite the attackers being more selective of their victims. This is because, even though the errors introduced by each attacker are smaller than in the naive case (nodes that are closer can only be "pushed" less aggressively if the attacker is to avoid detection), these errors are allowed to permeate unchallenged through the system, propagating more widely through the undetected mis-positioning of honest nodes. We observed that in the system without malicious nodes, the mean relative error converged towards a value of about 0.4. Here we see that as little as 10% of attackers leaves over 60% of the overall population worse off than the average node in a clean system. We also observed that compared with the more naive version of this attack (figure 3.21), the sophisticated version induces higher average errors.

Again, better accuracy (i.e. higher dimensionality) and smaller group sizes were observed to be more sensitive to the attack. from pure guessing to full knowledge (i.e. attacking only victims whose coordinates are known), an attacker can reduce by half its chances of being caught. We also see that the intrinsically more cautious strategy of this attack dramatically reduces the chances of an attacker being detected compared with the naive attack case (figure 3.23), especially when malicious nodes represent a smaller proportion of the population and operate with little knowledge of the exact coordinates of their victims. Indeed, for the case where the attackers never know exactly the coordinate of their victims, figure 3.25 shows that over 75% of all detections are false positives for attackers populations of 10% and over of the group.

Injection of Colluding Isolation Attackers

In a colluding isolation attack, the malicious nodes cooperate with each other and behave in a correct and honest way until enough of them become reference points at the same layer. Once at least a minimum number of malicious reference points has been reached (in our simulation this number is set to 5), these attackers identify a common set of victims. When involved in the positioning of any other nodes, the attackers do not cheat; while when dealing with a target node, they agree to pretend they are all clustered into a remote (far away) part of the coordinate space and carry out a naive anti-detection attack on the victim. The goal of this attack is to push the victims into a remote location at the "opposite" of where the attackers pretend to be, thus isolation the victims from all the other nodes (in the coordinate space). The other main idea behind this attack is that by acting in a consistent way as a group, the attackers can maybe avoid detection by influencing the value of the median relative error (condition 2 of the NPS security mechanism -see 2.3.4). Also, as already mentioned, even if detected, at most one attacker would be filtered at each positioning, giving the others more opportunities to act.

We consider 2 scenarios for this attack. The first scenario consists in experimenting with a 3-layer NPS system, i.e. a system with the landmarks in layer-0, 20% of nodes serving as reference points in layer-1, and the rest of the nodes in layer-2. The second scenario is aimed at observing the propagation of errors through different layers and uses a 4-layer NPS system, with 2 layers (layer-1 and layer-2) containing 20% of the nodes acting as reference points. Figures 3.26 and 3.27 show the cumulative distribution function of the relative errors in a 3-layer and 4-layer NPS system (respectively) under this colluding isolation attack. We observe a striking difference of impact depending on the structure of the NPS system. Indeed, the overall accuracy of a 3-layer system is much less affected than the accuracy of a 4-layer system. On the one hand, it is worth remembering that, in the 3-layer system, non victim nodes do not see any degradation of the accuracy of their positions (compared to a clean system), because they observe an honest behaviour from the attackers. This means that the overall degradation in accuracy is caused by the mis-positioning of the victims only. Hence, the perceived little impact of the attack depicted in figure 3.26 actually tends to indicates that the attack is very effective on the victim.

On the other hand, in a 4-layer system, some of the victims may be unwittingly se- lected by the membership server to act as layer-2 reference points. The position errors inflicted on these nodes is then propagated through the rest of the system, resulting is an amplification of the errors from layer to layer. This is demonstrated in figure 3.28 that shows the average relative error of layer-2 and layer-3 nodes in clean 3-layer and 4-layer systems respectively, as well as the average relative error observed by layer-2 targets and layer-3 nodes in corrupted systems with a population of 20% of malicious nodes. From this figure, it is clear that the impact of layer-1 cheats on layer-2 victims is independent of the system structure (the curves are similar), layer-3 nodes of an attacked 4-layer system experience the worse mis-positionning. This propagation and amplification of the errors in this 4-layer system can be seen as a system-control attack (see section 3.2).

Finally, as in the Vivaldi case, we observe in figure 3.29 the impact of several small population of attackers which concurrently carry out all the previous attacks. This is reminiscent of a situation where some nodes are still misbehaving for some time following the release of patches and updates after a major outbreak of malware. Again, we see that attacks can have long lasting consequences on the operation of the coordinate system.

Conclusions

In this chapter, we have studied various types of attacks on two prominent coordinate system proposals. One of our salient findings is that larger systems are consistently more resilient than smaller ones. Given the observation in [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] and [START_REF] Ng | A Network Positioning System for the Internet[END_REF] that larger systems are more accurate and the well known fact that larger systems converge slower at start-up time, there seems to be a compelling case for large-scale coordinate systems to be built as a virtual infrastructure service component. The paradox is of course that always-on, large-scale systems supporting many different applications will always attract more attacks than systems with a smaller reach, while the large size of the system itself would act as a particularly good terrain to create especially virulent propagation of the attack.

Our results also show that there is an intrinsic trade-off to be made between accuracy and vulnerability. Indeed, we have shown that the more accurate the system for a given system size, the more susceptible it was to a same proportionate level of attack. Also, we have shown that while an attack is in full swing, the performance of the coordinate systems (and of the applications it supports) can easily degrade below that of a systems where coordinates are chosen randomly, whilst the aftermath of an attack could have very long lasting effects on the system due to a small number of remaining malicious nodes.

We have also shown that infrastructure-based systems can, under some well chosen attack strategies, be as vulnerable as those based on the peer-to-peer paradigm. Furthermore, the security mechanisms that have been proposed to date to defend against malicious nodes are clearly rather primitive and still in their infancy and definitely cannot defend against all types of attacks.

In the next chapter, we will concentrate on designing generic defense and security method to protect coordinate-based systems from large-scale malicious attacks. This work will be guided by the understanding of attack mechanisms and of their consequences on the coordinate systems gained from the study presented in this chapter. First, we should be able to propose a general detection protocol, that do not entail any change to the operations of the embedding systems. Second, our detection protocol should not be sensitive to the dimensionality used by the coordinate-based system, avoiding in this way any trade-off between accuracy and vulnerability. Finally, we should design a detection protocol that should be capable of surviving a potential very large range of sophisticated attacks, without relying on the geometric properties of the coordinate space.

SECURING COORDINATE EMBEDDING SYSTEMS 4.1 Summary

This chapter addresses the security issues of the embedding phase in Internet Coordinate Systems, by proposing a general method for malicious behavior detection during coordinate computations. We first show that the dynamics of a node, in a coordinate system without abnormal or malicious behavior, can be modeled by a Linear State Space model and tracked by a Kalman filter. Then we show that the obtained model can be generalized in the sense that the parameters of a filter calibrated at a node can be used effectively to model and predict the dynamic behavior at another node, as long as the two nodes are not too far apart in the network. This leads to the proposal of a Surveyor infrastructure: Surveyor nodes are trusted, honest nodes that use each other exclusively to position themselves in the coordinate space, and are therefore immune to malicious behavior in the system. During their own coordinate embedding, other nodes can then use the filter parameters of a nearby Surveyor as a representation of normal, clean system behavior to detect and filter out abnormal or malicious activity. A combination of simulations and PlanetLab experiments are used to demonstrate the validity, generality, and effectiveness of the proposed approach for two representative coordinate embedding systems, namely Vivaldi and NPS.

Introduction

In the previous chapter, we have shown how coordinate-embedding services could be vulnerable to malicious attacks, providing a potentially attractive fertile ground for the disruption or collapse of the many applications and overlays that would use these services [START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF]. There are actually two obvious ways to disrupt the operation of a coordinate based system. First when requested to give its coordinate for a distance estimation at the application-level, a malicious node could simply and blatantly lie. Second, a malicious node, or even a colluding group, may aim at disrupting the embedding process itself. This latter strategy is very insidious and effective as it can result in important distortions of the coordinate space which then spoils the coordinate computations of many nodes (malicious and honest alike) [START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF]. This chapter focuses on developing and studying generic methods to secure the coordinate embedding process (the problem of nodes lying about their coordinate during distance estimation at the application-level is addressed in the next chapter).

More precisely, the embedding process, regardless of the actual coordinate-based positioning system, works on the premise that nodes adjust their coordinate based on some comparison between measured and estimated distances to some other nodes. Malicious nodes can interfere with this embedding process by, amongst other things, lying about their real coordinate and/or tampering with measurement probes, to create a discrepancy between measured and estimated latencies, so that unsuspecting nodes would wrongly adjust their own coordinate in a bid to reduce the difference [START_REF] Kaafar | Real attacks on virtual networks: Vivaldi out of tune[END_REF]. Because the load on the network naturally varies in time, so does latency between pair of nodes, and as a result, the embedding process must be run periodically by all nodes to track changes in network conditions. This "continuous" adjustment of nodes' coordinates can not only result in a drift of the coordinate space [START_REF] Ledlie | Network Coordinates in the Wild[END_REF] but also gives plenty of scope and opportunities for malicious activity. We therefore seek to equip (honest) nodes with a means to detect, with low overhead, malicious activities they may encounter during embedding.

Noting that, in the absence of malicious nodes, a node's coordinate depends on the combination of network conditions and the specificities of the embedding process itself (e.g. which coordinate protocol is in use, the chosen dimensionality of the geometric space, etc), we therefore introduce the concept of Surveyor nodes (or Surveyors in short). Surveyors form a group of trusted (honest) nodes, scattered across the network, which use each other exclusively to position themselves in the coordinate space.

Of course, Surveyors do assist other nodes in their positioning (as prescribed by the embedding protocol), but we stress that Surveyors never rely on non-Surveyor nodes to compute their own coordinate. This strategy thus allows Surveyors to experience and learn the natural evolution of the coordinate space, as observed by the evolution of their own coordinate, in the absence of malicious activities. In essence, Surveyor nodes are thus vintage points guaranteed to be immune from malicious activities. The idea is that Surveyors can then share a "representation" of normal behavior in the system with other nodes to enable them to detect and filter out abnormal behavior.

We postulate and verify that, in the absence of malicious activity, a node's coordinate can be viewed as a stochastic process with linear dependencies whose evolution can be tracked by a Kalman filter [4]. Each Surveyor then computes and calibrates the parameters of a linear state space model and shares the parameters of this model with other nodes. These nodes can then use these parameters, to run locally and in a "stand-alone" fashion a Kalman filter tracking the coordinate adjustments. These nodes can then use the Kalman filter output (the innovation process), to compare their observed coordinate adjustments with the one predicted by the Kalman filter, and flag as "suspicious" embedding steps where the difference would be too high.

In section 4.3, we present a general model of coordinate embedding, in the absence of malicious nodes, that naturally leads to the Kalman filter framework. In section 4.4, we validate the model, with both simulations and PlanetLab experiments, in the case of both Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] and NPS [START_REF] Ng | A Network Positioning System for the Internet[END_REF]. This section also studies the viability of the idea of using Surveyor nodes in secure coordinate embedding. We then describe and evaluate, in sections 4.5 and 4.6, how Surveyors can effectively be used for malicious node detection in the specific embedding process of Vivaldi and NPS.

Coordinate Embedding Model

The goal of embedding systems, regardless of the embedding method and geometric space used, is to assign a coordinate to every node in the system so that, at any time, the distance between any two points in the geometric space should provide a good estimate of the network distance, measured as an RTT (Round Trip Time), between the corresponding nodes. Obviously, because at any instant in time, the RTT that can be measured between two nodes depends on the state of the network (e.g. traffic load, state of queues in routers, etc) as well as the state of the operating system in nodes (e.g. scheduling state generating measurement noise, etc), the exact value of the RTT varies continuously. However, it has been shown that RTT values in the Internet exhibit some stability in a statistical sense [START_REF] Zhang | On the Constancy of Internet Path Properties[END_REF], with the statistical properties of RTTs exhibiting no significant change at timescales of several minutes. It is that property that embedding systems exploit to provide good distance estimates while only needing to have nodes adjust (recalculate) their coordinate on a periodic basis. Consequently, the coordinate of a node can be viewed as a discrete stochastic process, and we will use X n i to represent the coordinate of node i at "discrete time" n.

Without loss of generality, consider that a node (called the embedding node) computes its coordinate through a series of embedding steps, where each embedding step represents a coordinate adjustment based on a one-to-one interaction with another node, called a peer node (e.g. peer nodes are called neighbors in Vivaldi, and landmarks or reference points in NPS). Note that when the embedding protocol requires that a node uses several peer nodes simultaneously for repositioning, for the purpose of our modelization, we simply consider that each peer node corresponds to a distinct embedding step, each taking place at "successive" discrete times.

At every embedding step, the "fitness" (or "correctness") of the embedding node coordinate is assessed by computing the deviation between the measured RTT towards the corresponding peer node and the one estimated in the coordinate system. More precisely, suppose that at its n th embedding step, embedding node i has current coordinate X n i and uses peer node j with current coordinate X n j . Suppose that the RTT between these nodes, measured during this embedding step, is RTT n ij . The fitness of the embedding node coordinate can then be computed as the measured relative error

D n = |||X n i -X n j ||-RTT n ij | RTT n ij
. The goal of any embedding system, regardless of the embedding method proposed and/or the geometric space structure, is to minimize a "cost" indicator (e.g. mean square error) that captures the measured relative error that could be observed between any node and any other node in the system, at any time.

As the measured relative errors are fundamental performance indicators to all embedding systems, it seems natural to develop a model that captures their dynamic characteristics, although we note that relative errors often have complex behavior (and may thus not be a natural choice from a modeling perspective).

Measured relative errors are subject to fluctuations of the RTT for the reasons mentioned above, namely transient network congestion and operating system scheduling issues. To isolate the impact of these RTT fluctuations on anomaly detection, we introduce ∆ n , the nominal relative error that our node under consideration would have obtained at its n th embedding step if the RTTs in the network had not fluctuated. An anomaly becomes simply a large deviation of measured relative error D n from its nominal value defined by ∆ n .

Because many sources contribute to the deviation of D n from its nominal value (RTT measurement error, RTT fluctuations, errors in node coordinate), it is reasonable to suppose that they relate to each other as follows,

D n = ∆ n + U n (4.1)
where U n is a Gaussian random variable with mean zero and variance v U .

We now focus on the dynamics of the system in its nominal regime where RTTs do not fluctuate. In the absence of complete and accurate knowledge of the system, nodes keep on adapting the nominal relative error on a pairwise basis with their peer nodes, aiming to optimize the cost indicator. This adaptation is subject to an error caused by the other nodes in the system adapting their coordinate (and corresponding relative error) in a completely distributed way. We thus define the system error W n which represents the impact of other nodes on the positioning of a node at embedding step n. Since the system error at a node results from many contributing sources, it is also reasonable to assume that it is a white gaussian process (with mean w and variance v W ) 1 .

Because of the nature of large-scale embedding processes, the nominal relative error ∆ n can be deemed to follow a stochastic process that converges to some stationary regime characterized by a positive average. As a first approximation, the process ∆ n could be modeled as a first order Auto Regressive (AR) model:

∆ n+1 = β∆ n + W n . (4.2)
where β is a constant factor strictly less than one otherwise the relative error does not converge to a stationary regime independently of the initial condition. This equation captures the dynamic evolution of the nominal relative error of a node through successive embedding steps. Equations 4.2 and 4.1 define a linear state space model for the relative error of a node. Our goal is to devise a way to obtain relative error predictions from this model. Because of the linear properties of the model, a Kalman filter can be used to track the evolution of the nominal relative error and obtain a predicted relative error ∆n|n-1 (see section 4.3.1).

The idea behind this strategy is that if the stochastic space model, and especially its associated Kalman filter, are calibrated within a clean embedding system, then a simple hypothesis test can be used to assess whether the deviation between the measured relative error and the predicted relative error, observed at a given embedding step, is normal or is the fruit of anomalous or malicious activity from the peer node. From this perspective, even if the state space model considered is crude, its quality should be evaluated based on the final outcome in terms of probability of detection and false positive rate. We will see in the evaluation section (section 4.6) that this model achieves very good performance.

Kalman Filter Equations

The Kalman filter is used here to estimate ∆ n given the set of previously measured relative errors D n 0 = {D 0 , . . . , D n }. Under the hypothesis of a gaussian noise process in the underlying state space model, the Kalman filter gives the Least Mean Squared estimates of ∆ n , ∆n . Moreover, it gives the quality of these estimates through an evaluation of the mean squared error i.e., E[( ∆n -∆ n ) 2 ]. This last value could be used to detect anomalies through large deviations of the measured relative error from its mean.

We will assume here that all the parameters of the space model given in Eq. (4.1) and Eq. (4.2) are known and given. In the next section we will describe how to derive these parameters.

Let us denote by ∆i|i-1 the estimation of ∆ i knowing the observations of network delay up to time i-1, and ∆i|i the estimate after the measurement D i is done. Similarly, let P i|i-1 be the estimated a posteriori error variance at time i knowing the observations up to time i -1, and let P i|i be the estimation of the a posteriori error variance after D i is known. The Kalman Filter is composed of two steps that are iterated. The first step is called the prediction step and the second one the update step.

In the prediction step, the value of ∆i|i-1 is calculated based on ∆i-1|i-1 as :

∆i|i-1 = β ∆i-1|i-1 + w.
The a posteriori error variance of this estimate is :

P i|i-1 = β 2 P i-1|i-1 + v W .
In the update step, ∆i|i-1 is updated to integrate the observed measurement D i :

∆i|i = ∆i|i-1 + K i (D i -∆i|i-1 )
where K i denotes the updated gain and is obtained as :

K i = P i|i-1 P i|i-1 + v U .
The a posteriori error variance of this estimate is :

P i|i = v U P i|i-1 + v U P i|i-1 .
The value η i = D i -∆i|i-1 is called the innovation process and is the main process to observe for anomalous behavior detection (see section 4.5.1). The innovation process is a white (meaning that it is an independent process) gaussian process with a mean 0 and a variance equal to v η,i = v U + P i|i-1 . Abnormality simply amounts to a significant deviation from the nominal values of the innovation process characterized by the Kalman filter.

To run the Kalman estimation, we need as initial values the system state value w 0 and the a priori state variance P 0|0 = p 0 . These two values are estimated during the parameters calibration step.

Calibration of the Kalman filter

Before running the estimation using the Kalman filter, the values of the filter parameters θ = (β, v W , v U , w 0 , p 0 ) have to be computed. For this purpose we need to calibrate these parameters over coordinate measurements collected during a stationary and cheater-free period. The calibration can be done using a maximum likelihood criteria (choosing parameter values such that the likelihood of observing the measurements is maximized) by applying the Expectation Maximization (EM) method. We follow the approach presented in [START_REF] Ghahramani | Parameter Estimation for Linear Dynamical Systems[END_REF] for the EM derivation.

In the following, we give a brief description of the maximum likelihood estimation criterion and the EM method, we are using in this section to calibrate our filter.

The maximum likelihood estimation criterion

Maximum likelihood estimation (MLE) is a statistical method used to make inferences about parameters of the underlying probability distribution from a given data set [START_REF] Kay | Fundamentals of Statistical Signal Processing: Estimation Theory[END_REF]. Basically, this method allows us to infer the parameters of a distribution given a sample of data X = X 1 , . . . , X n . Commonly, one assumes the data are independent, identically distributed (i.i.d) drawn from a particular distribution with unknown parameters and uses the MLE technique to create estimators for these unknown parameters.

Let us consider a family of distributions P θ indexed by a parameter (which could be a vector of parameters) θ that belongs to a set Θ. Let f(X|θ) be either a probability function (in case of discrete distribution) or a probability density function (continuous case) of the distribution P θ . Given our i.i.d. sample X 1 , . . . , X n with unknown distribution P θ from this family, i.e. parameter θ is unknown. A likelihood function is defined by:

L(θ|X) = f(X 1 |θ) × . . . × f(X n |θ).
If our distributions are discrete then the probability function

f(x|θ) = P θ (X = x) is the probability to observe a point x. L(θ) = f(X 1 |θ) × . . . × f(X n |θ) = P θ (X 1 ) × . . . P θ (X n ) = P θ (X 1 , . . . , X n )
is the probability to observe the sample X 1 , . . . , X n when the parameters of the distribution are equal to θ.

Suppose that there exists a parameter θ that maximizes the likelihood function L(θ) on the set of possible parameters, i.e.

L( θ) = max θ∈Θ L(θ)
Then θ is called the Maximum Likelihood Estimator (MLE) of θ. When finding the MLE, it is sometimes easier to maximize the log-likelihood function since L(θ) → maximize ⇔ log(L(θ)) → maximize maximizing L(θ) is equivalent maximizing log L(θ). Log-Likelihood function can be written as log L(θ) = n i=1 (log f(X i |θ)). To summarize, one needs to recall that the MLE criterion chooses the parameter θ that maximizes the probability of seeing the observed data given that their distribution follows these parameters. The log of the likelihood is often used instead of true likelihood because it leads to easier formulas, but still attains its maximum at the same point as the likelihood.

The Expectation maximization (EM) algorithm is a valuable approach for maximum likelihood parameter estimation. In the next paragraph, we use this method to calibrate our Kalman filter parameters, i.e . find the values for the filter parameters that maximize the probability of a sequence of observations.

Calibration by EM method

Let's assume that D N 0 is the set of all measured prediction errors, D N 0 = {D 0 , . . . , D N } and let ∆ N 0 = {∆ 0 , . . . , ∆ N } be the set of nominal relative errors. As all the noise processes are assumed to be gaussian, D N 0 and ∆ N 0 will jointly follow a gaussian distribution. The log-likelihood of D N 0 and ∆ N 0 , based on equations 4.2 and 4.1, can therefore be written as follows:

log Prob{D N 0 , ∆ N 0 } = - N i=0 (D i -∆ i ) 2 2v U - N + 1 2 log v U - N i=1 (∆ i -β∆ i-1 -w) 2 2v W - N 2 log v W - (∆ 0 -w 0 ) 2 2p 0 - 1 2 log p 0 -(N + 1) log 2π.
In a Maximum likelihood setting, we wish to find the values for the parameters that will maximize the above log-likelihood assuming that the sequence D N 0 has been observed. However as the sequence of system state ∆ N 0 has not been observed, this maximization is not tractable directly and we have to apply the Expectation Maximization method [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. This method transforms the maximization of the above likelihood function with unobserved system state sequence ∆ N 0 to an iteration of successive steps where the system state sequence is assumed to be known and the parameters can be obtained through maximization of the likelihood function.

Each iteration of the EM method consists therefore of two steps. In the first step, we compute the expectation (over all values of the sequence of states ∆ N 0 ) of the loglikelihood, given the observed values of D n and assume that the parameter values are equal to θ (k) . In a second step, the parameters θ (k+1) are chosen so as to maximize the previously obtained likelihood expectation (see Appendix B). Next we explain these two operations with some further details.

Let the superscript (k) indicate the value of any parameter at the k th step of the EM algorithm. As explained before, in the EM method, we need to estimate the value of the unobserved system states to be able to calculate the overall likelihood to maximize. The variables δ(k) i are in fact those estimates at iteration k and π(k) i and π(k) i,i-1 are the estimation error variances of this sequence of states:

δ(k) i = E[∆ i |D N 0 , θ (k) ], π(k) i = E[∆ 2 i |D N 0 , θ (k) ], π(k) i,i-1 = E[∆ i ∆ i-1 |D N 0 , θ (k) ].

Expectation step

The expected value of log-likelihood knowing the set of measured values D N 0 and the parameter θ (k) is given by:

L(θ, θ (k) ) = E[log Prob{D N 0 , ∆ N 0 }|D N 0 , θ (k) ] = - N i=0 D 2 i -2D i δ(k) i + π(k) i 2v U - N + 1 2 log v U - N i=1 π(k) i + β 2 π(k) i-1 + w2 2v W + N i=1 β π(k) i,i-1 + δ(k) i w -β δ(k) i-1 w v W - N 2 log v W - π 0 -2 δ(k) 0 w 0 + w 2 0 2p 0 - 1 2 log p 0 -(N + 1) log 2π.
By replacing θ by its value at the k th step of the EM algorithm, we obtain δ(k) i , π(k) i and π(k)

i,i-1 , which gives the expected log-likelihood at the (k + 1) th step. Next, we describe how to compute these values.

Calculating the parameters δi , πi , πi,i-1

As explained in section 4.3.2, the sequence of system states ∆ N 0 is not observable. However, we need to give an estimate of this sequence to be able to obtain the likelihood. The sequence δi , i = 1 . . . , N, is the sequence of system state estimates and πi , and πi,i-1 is the error variance of these estimates assuming that the sequence D N 0 has been observed. We resort to the solution in [START_REF] Ghahramani | Parameter Estimation for Linear Dynamical Systems[END_REF] for the calculation of these estimates using the overall measurements set.

The value δi , πi , and πi,i-1 are estimated using a Kalman filter, assuming that the system parameters are set as in θ (k) . However, there is a subtle difference with Kalman filter case described in section 4.3.1; here the estimates δi , πi and πi,i-1 do not depend only on observations up to time i, but on future observations up to time N ≥ i. The solution to deal with this is to implement a forward-backward approach similar to Baum-Welch filter used for finite EM algorithm [START_REF] Bilmes | A gentle tutorial on the EM algorithm including gaussian mixtures and baum-welch[END_REF].

For each value of the parameter set θ (k) , we first do a forward step following the relations given in section 4.3.1. The application of this forward step results in the values ∆i|i , i = 1, . . . , N, P i|i , i = 1, . . . , N and P i|i-1 , i = 1, . . . , N.

To add the future measurements in the Kalman filter, a backward recursion step is also added. This step consists of the following equations:

         δi-1 = ∆i-1|i-1 + J i-1 ( δi -β ∆i-1|i-1 ) πi-1 = P i-1|i-1 + J 2 i-1 ( πi -P i|i-1 ) J i-1 = β P i-1|i-1 P i|i-1
These equations give recursively the values δi and πi . It still remains to obtain πi,i-1 . This last value could be obtained using the relation :

πi,i-1 = v N i,i-1 + δi δi-1
where v N i,i-1 can be obtained through the backward recursion

v N i,i-1 = P i-1|i-1 J i-1 + J i (v N i+1,i -βP i|i )J i-1 ,
that is initialized by setting

v N N,N-1 = (1 -K N )βP N-1|N-1 .

Maximization step

In this step, the parameter vector at step (k + 1) is chosen to maximize the expected log-likelihood. This is done by solving the equation

∂ L(θ, θ (k) ) ∂θ = 0.
This results in the following set of equations:

                                 w (k+1) 0 = δ(k) 0 p (k+1) 0 = π(k) 0 -( δ(k) 0 ) 2 v (k+1) U = 1 N+1 N i=0 D 2 i -2D i δ(k) i + π(k) i w(k+1) = N i=1 δ(k) i -β (k+1) N i=1 δ(k) i-1 β (k+1) = N i=1 π(k) i,i-1 -w (k+1) N i=1 δ(k) i-1 N i=1 π(k) i-1 v (k+1) W = 1 N N i=1 π(k) i + (β (k+1) ) 2 π(k) i-1 + ( w(k+1) ) 2 -2β (k+1) π(k) i,i-1 -2 δ(k) i w(k+1) + 2β (k+1) δ(k) i-1 w(k+1) .
By solving this set of equations we can obtain the vector θ (k+1) , then we iterate with the expectation calculation as described above.

We note that the complexity of the approach lies in the linear state space modeling phase by EM algorithm that incurs a number of iterations over N dimensional vectors, which is well within the capability of modern computers. We will see later that this phase has to be run on a subset of nodes (the Surveyors). On the other hand, predicting relative errors using the Kalman filter (section 4.3.1), which occurs on every node, only implies a few simple scalar operations and is negligible in terms of required computing power.

Finally, because we expect each of the innovation observation η n to be inside a confidence interval of ±2 √ v η,n (where v η,n is the variance of the innovation process at time n) with a probability higher than 95%, when a Kalman filter yields 10 consecutive innovation observations outside such confidence interval, the filter is re-calibrated by re-applying the calibration procedure described in this section. Re-calibration is likely to occur following a significant change in the corresponding node's coordinate, caused by changes in network conditions.

Validation

To validate our model, we conducted simulations and PlanetLab experiments for both Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] and NPS [START_REF] Ng | A Network Positioning System for the Internet[END_REF]. Again, we consider Vivaldi as a prominent representative of purely peer-to-peer-based (i.e. without infrastructure support) positioning systems, while NPS is typical of infrastructure-based systems, where a hierarchy of landmarks and reference points govern the positioning of nodes.

As the goal of this section is to assess the fitness of the proposed model to represent the normal behavior of the embedding processes, all results presented were acquired in a clean environment with no malicious node. While the goal of the simulation studies is to assess our results for large scale coordinate-based systems, the PlanetLab experiments aim to show their applicability in real-world conditions.

The PlanetLab experiments were conducted over a set of 280 PlanetLab nodes spread world-wide. In this thesis, we discuss a representative set of experimental results conducted over several days in December 2006.

The simulations were driven by a matrix of inter-host Internet RTTs (the "King" dataset) to model latencies based on real world measurements. This dataset contains the pair-wise RTTs between 1740 Internet DNS servers collected using the King method [START_REF] Gummadi | King: Estimating Latency between Arbitrary Internet End Hosts[END_REF] and was used to generate a topology with 1740 overlay nodes.

In the case of Vivaldi, each node had 64 neighbors (i.e. was attached to 64 springs), 32 of which being chosen to be closer than 50 ms. The constant fraction C c for the adaptive timestep is set to 0.25, as proposed in [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF]. A 2-dimensional coordinate space augmented with a height vector was used (see chapter 2, section 2.4.2).

For NPS, we considered an 8-dimensional Euclidean space for the embedding. We used an NPS positioning hierarchy with 4 layers. The top layer had a set of 20 well separated permanent landmarks. Each subsequent layer then had 20% of nodes randomly chosen as reference points. The security mechanism already proposed in NPS, shown to be too primitive in the previous chapter, was turned on and its sensitivity constant C was set to 4, as advised by authors in [START_REF] Ng | A Network Positioning System for the Internet[END_REF] (see chapter 2, section 2.3.4).

When needed, Surveyor nodes were chosen at random2 .

Assumption Validation

In section 4.3, the assumption that the system error W n follows a gaussian distribution was made. This is fundamental to the applicability of the Kalman filter framework. For the purpose of validation, every node calibrated its own Kalman filter based on the observation of its own embedding, and we checked this assumption by applying the Lilliefors test [START_REF] Lilliefors | On the Kolmogorov-Smirnov test for normality with mean and variance unknown[END_REF], a robust version of the well known kolmogoroff-Smirnov goodnessof-fit test, to whitened filter inputs (see Appendix A for details). We observed that the Lilliefors test leads to only 14 gaussian fitting rejections in simulations (over 1720 samples) and 5 rejections in PlanetLab (over 260 samples). This test allows us to conclude that the hypothesis we took for the Kalman model is valid. In addition, we plot in figure 4.1 the Quantile-Quantile (QQ) plots of 2 innovation processes (for both Vivaldi and NPS) taken on PlanetLab nodes running their own Kalman filter. These plots, typical of observations on all nodes, show that each of these distributions indeed closely follows a Gaussian distribution.

Effective Behavior Representation

From section 4.3, it is clear that the Kalman filter model attempts to represent the behavior of the embedding process by capturing the dynamics of the system through its convergence behavior (by tracking of relative errors over time). In this section, we therefore assess the representational power of this approach by having each node calibrate its own Kalman filter from the measurements it observed during the embedding of its own coordinate, in a cheat-free regime. Then, once the model has converged at every node (i.e. the EM method has converged and the variations of all the θ components become smaller than 0.02), a new embedding process is started (i.e. the nodes forget their coordinates and rejoin the system). During this second embedding process, the prediction error, that is the absolute value between the error predicted by the node's Kalman filter and the measured actual error, is computed. Figure 4.2 shows a typical evolution of actual (measured) relative errors and predicted errors for a node on PlanetLab (for Vivaldi, but similar behavior was observed for NPS). The two curves of the top graph of the figure are so similar that they are almost indistinguishable. The bottom graph of the figure represents the prediction error which is the difference between these two curves (note the different scale used for this graph). We see that the prediction errors are small which shows that a node's calibrated Kalman filter can capture effectively the node's behavior "in the wild". Figure 4.3 shows the cumulative distribution function (CDF) of all the prediction errors observed across all nodes in the system. This confirms that the vast majority of predictions are indeed excellent. This demonstrates the power and generality of the model in capturing the dynamics of the system and its adaptability to current system conditions.

However, there are a few "outlier" predictions with large errors. To better understand their nature, we show in table 4.1 the repartition of prediction errors in error intervals. The table shows the number of nodes with prediction errors in this interval, the number of occurrences of the smallest prediction error observed in the interval, and the number of occurrences of the largest prediction errors observed in the interval (e.g. Number of node(s)/number of observed min error/number of observed max error). We see that only a few nodes contribute (sometimes very many) large prediction errors. Looking further, we identified 3 nodes, all located in India, who contributed consistently to the "tail" of the CDF in figure 4 nodes exhibited large (> 0.75) average measured relative errors during embedding, and were clearly having trouble with the embedding process itself, due to adverse network conditions.

Representativeness of Surveyors

If a subset of nodes in the system (called Surveyor nodes) are trusted and use each other exclusively to compute their own coordinates, they will be immune to the effects of malicious behavior during embedding. The premise of our work is that the "clean" (normal) system behavior thus learnt can then be shared with other nodes and used by these nodes to detect malicious behavior they may be subjected to by other nodes in the system. This obviously assumes that the behavior of the system as observed by Surveyors can approximate or represent well enough the normal behavior of the system as observed by other nodes in the absence of malicious behavior. In the following validation of this assumption, Surveyors are chosen at random in the node population.

Note that a random choice will give an upper bound on the number of Surveyors needed. Indeed, intuitively, Surveyors should be roughly uniformly distributed in the system to be representative of most other nodes. However, choosing nodes at random appear due to the cluster structure of nodes themselves) and therefore not every new Surveyor increases representativeness. Consequently, more Surveyors must be chosen in order to achieve a good coverage of the system, than if they were placed more strategically. Nevertheless, the random choice method does provide general results, without the need to address the question of optimal Surveyor deployment strategy.

One of the first questions to answer is how many Surveyors are needed to be representative of the rest of the population. Noting that our model is based on measured relative errors and that each node in the system observes a series (i.e. distribution) of such errors, we characterize the system-wide relative error behavior as the CDF of the 95 th percentiles of the relative errors observed at each (normal) node (i.e. the distribution is made up of the 95 th percentile value observed at every node). We then compare this CDF with those of the 95 th percentiles of the relative errors observed across a varying population of Surveyors. The choice of the 95 th percentile is so that outliers, as observed in section 4.4.2, do not skew the results, while preserving a high degree of generality. To generalize this result, we then repeated the experiment, using both simulations and PlanetLab measurements, on a Vivaldi system with 8% of Surveyors. We again chose to represent the system by the distribution of the 95 th percentile of the measured relative errors (figure 4.5).

These experiments confirm that less than 10% of randomly chosen Surveyor nodes is enough to gain a good representation of the system behavior. Similar results were observed for NPS. We note that 8% to 10% of the overall node population is a very stringent requirement for most practical purposes and can represent a huge number of nodes. However, as already pointed out above, random Surveyor deployment is not optimal and this value is an upper bound on the number of Surveyors needed.

To gain further insight into how conservative this upper bound may be, we tried a simple k-means clustering algorithm for Surveyor deployment. Figure 4.4 shows that when taking cluster heads as Surveyors, good representativeness can be achieved with roughly 1% of Surveyors. Although this does not give much indication as to what the lower bound on the number of Surveyors needed is in the case of optimal Surveyor deployment, it nevertheless shows that simple deployment methods can reduce requirements considerably and that the upper bound yielded by random deployment is indeed very conservative.

Having shown that a population of Surveyors can represent the overall system, the next question is how well the behavior of the system as captured by the Kalman filter calibrated by a Surveyor, can represent the behavior of a single (normal) node.

To answer this question, we carried out an experiment where a population of nodes took part in a Vivaldi embedding on PlanetLab. Each node used the Kalman filter of every Surveyor and generated multiple prediction errors (one per Surveyor) at every embedding step. Figure 4.6 shows the maximum prediction error yielded by each Surveyor, for each normal node in the system, observed during this experiment. What we observe is that although each normal node can find at least one Surveyor node whose Kalman filter yields very low prediction errors, not every Surveyor is a good representative for any given normal node. The Surveyor chosen as a representative by a normal node is therefore important to achieve good prediction performance (and thus good malicious behavior detection). between a node and its Surveyor yields more accurate predictions. This property seems intuitive, as a Surveyor closer in terms of RTT will also be closer in the geometric space, and will thus be more likely to experience dynamics of the coordinate system similar to that of the local area where the node resides. This is confirmed in figure 4.8 which shows the maximum prediction error, observed for Vivaldi on PlanetLab, when nodes use the closest Surveyor as their representative. Similar results were observed for PlanetLab experiments with NPS.

Finally, it is again important to note that all the results in this section were obtained with randomly deployed Surveyors. Strategically placing Surveyors to ensure a better coverage of the network and coordinate space, would simply improve the prediction accuracy, while reducing the number of Surveyors required.

Malicious Behavior Detection

The previous section has shown that normal node behavior can be modeled by a Kalman filter. More importantly, it has also been shown that this technique is powerful and robust enough that the normal behavior model captured on one node is readily and effectively applicable on other nearby nodes. This property leads to the idea of Surveyors.

Surveyors are a set of nodes in the coordinate space that exclusively use each other to compute their own coordinates. In other words, in Vivaldi, Surveyors only use other Surveyors as neighbors, while in NPS, they only use other Surveyors as reference points (note that in NPS, all landmarks also act as Surveyors, although not all reference points will be Surveyors). Of course, Surveyors can, and will be chosen as neighbors or reference points by other (non-Surveyor) nodes in the system, but the point is that a Surveyor adjusts its coordinate solely in response to embedding steps (i.e. measurements) with other Surveyors. If Surveyors run a clean version of the coordinate embedding software and they are carefully kept clean of malicious software, such as viruses or worms, that could implement malicious modifications to the embedding, then they can be considered as clean, honest nodes. Because Surveyors only interact with each other during their own embedding, they are therefore immune to malicious or anomalous behavior in the system, and they therefore observe the behavior of the system in clean, normal conditions. The idea is then to use the thus obtained normal behavior model as a basis for anomalous behavior detection at other nodes of the system. To do so, nodes use the parameters of the Kalman filter calibrated at a nearby Surveyor.

It is important to note that the proposed method is entirely distributed as each node has its own filter. Indeed, Surveyors calibrate and recalibrate their own filter as needed, depending on varying network conditions, and share the resulting filter parameters with other nodes, but they take no further active part in anomalous behavior detection at other nodes. When a node's filter needs re-calibrating (e.g. because it starts giving too many detection alarms), the node simply obtains fresh filter parameters from a Surveyor.

Anomalous Behavior Detection Method

At each embedding step, a node computes a measured relative error D n towards a peer node. Recall from section 4.3 that the Kalman filter at the node can provide ∆n|n-1 , the predicted relative error from the previously measured relative errors. The innovation process of the Kalman filter yields the deviation between the measured and predicted relative errors, η n = (D n -∆n|n-1 ), which, in a system without malicious node, follows a zero-mean gaussian distribution with variance v η,n = v U + P n|n-1 (also yielded by the filter). This allows us to detect malicious behavior as a simple hypothesis test. Let H 0 be the hypothesis that the peer node has a normal behavior (i.e. it is honest). The hypothesis testing simply consists of assessing whether the deviation between the measured and predicted relative errors is normal enough under expected system behavior. Given a "significance level" α, which determines the "aggressivity" or "strictness" of the test, the problem is to find the threshold value t n such that

P(|D n -∆n|n-1 | ≥ t n | H 0 ) = α. (4.3)
But since, under hypothesis H 0 , (D n -∆n|n-1 ) follows a zero-mean normal distribution with variance v η,n , we also have that

P(|D n -∆n|n-1 | ≥ t n | H 0 ) = 2Q(t n / √ v η,n ), (4.4)
where Q(x) = 1 -Φ(x), with Φ(x) being the CDF of a zero-mean, unit-variance normal distribution.

From equations 4.3 and 4.4, we therefore have

t n = √ v η,n Q -1 (α/2). (4.5)
If the observed deviation exceeds the threshold given by equation 4.5, then the hypothesis is rejected, the peer node is flagged as suspicious, the embedding step is aborted and the measured relative error D n is discarded (i.e. it is not used to update the state of the filter).

Note that a suspicious node, as detected by this test, is not necessarily associated with malicious intent, but could be caused by changing network conditions. Honest nodes classified as suspicious represent false positives and have little impact on the system as long as their occurrence is low. The trade-off between aggressivity and strictness of the test is represented by the so called ROC (Receiver Operation Characteristic) curves [START_REF] Soule | Combining Filtering and Statistical Methods for Anomaly Detection[END_REF]. These curves plot the true positive rate versus the false positive rate, i.e. the probability of correctly detecting a malicious node versus the probability of labelling an honest node as malicious. In practice trying to increase the true positive rate (the probability of malicious node detection) comes at the cost of increasing the false positive rate.

Generic Detection protocol

In general, on identifying a peer node as suspicious, a node will replace it, that is choose a new neighbor in Vivaldi or a new reference point in NPS.

The only exception to this rule is when the node was embedding against the peer node for the very first time. In this particular case, the node uses its local error e l 3 as an indicator of the confidence it has in its own coordinate, to carry out a second hypothesis test identical to that presented in the previous section, but this time with a confidence level of e l α. If the test is accepted, then the peer node gets a reprieve and is not replaced, so that a second embedding against this peer node will be attempted at a later time.

The main idea behind this potential reprieve for first-time peer nodes is that a node whose coordinate has already converged towards its true value can afford a few aborted embedding steps with very little impact on the accuracy of its coordinate. On the other hand, a new peer node which is in the process of joining the network may trigger the abortion of an embedding step, simply because its coordinate has not converged yet (as opposed to because it displays a malicious behavior). In this case, the reprieve simply gives time to the new (joining) peer node to converge before being identified as malicious. Of course an embedding node which is not confident in its coordinate must strive to reduce the number of aborted embedding steps so as not to compromise its convergence in the system, and will therefore grant fewer reprieves (because its e l is higher) than a node that has already converged.

Finally, we use a simple mechanism for the selection of the Surveyor from which a node obtains its calibrated Kalman filter. All Surveyor nodes register with an infrastructure server (e.g. the membership server in NPS can act as Surveyor registrar, while in Vivaldi such server must either be introduced or at least integrated inside an existing bootstrap infrastructure). On joining the coordinate system, a node interrogates this server to obtain the identity of several (randomly chosen) Surveyors. The node then measures its distance to these Surveyors and selects the closest one as representative. From there on, the node fully complies to the embedding protocol rules, except that it will use our detection method to accept or reject embedding steps.

However, when the node has rejected half of its current peer nodes during a same embedding round, it will seek to acquire a new filter as the high rejection rate may indicate that the filter parameters in use may have become stale (i.e. the filter needs "recalibrating"). The node then gets from its current Surveyor (or, as a fallback, any other Surveyors it knows, or the infrastructure server) the list of all the Surveyors it knows. After acquiring the current coordinates of these Surveyors, the node selects the closest one (in term of estimated distance) and obtains its Kalman filter parameters. Note that in the experiments we have carried out, which are described below, we observed very few "recalibrations", so this very simple Surveyor selection mechanism was appropriate. However, more sophisticated approaches can be considered if need be.

Evaluation

We evaluate the effectiveness of the simple anomalous/malicious behavior detection method in securing both Vivaldi and NPS. For each of these embedding protocols, we chose the most potent attack described in [START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF] and experimented with various populations of malicious nodes within the experimental set-up described in section 4.4. On PlanetLab, all these experiments were run concurrently so as to experience the same network conditions. In line with the results of section 4.4.3, the population of Surveyors was set to 8% of the overall population. Surveyors and malicious nodes were chosen at random.

Performance Metrics

To characterize the performance of our detection test, we use the classical false/true positives/negatives indicators. Specifically, a negative is a normal embedding step which should therefore be accepted by the test and completed. A positive is a malicious embedding step (i.e. where either, or both, the distance estimation and distance measurement between the node and its peer node have been tampered with) which should therefore be rejected by the test and aborted. The number of negatives (resp. positives) in the population comprising all the embedding steps is P N (resp. P P ).

A false negative is a malicious embedding step that has been wrongly classified by the test as negative, and has therefore been wrongly completed. A false positive is a normal embedding step that has been wrongly rejected by the test and therefore wrongly aborted. True positives (resp. true negatives) are positives (resp. negatives) that have been correctly reported by the test and therefore have been rightly aborted (resp. completed). The number of false negatives (resp. false positives, true negatives and true positives) reported by the test is T FN (resp. T FP , T TN and T TP ).

We use the notion of false negative rate (FNR) which is the proportion of all the malicious embedding steps that have been wrongly reported as normal by the test, and FNR = T FN /P P . The false positive rate (FPR) is the proportion of all the normal embedding steps that have been wrongly reported as positive by the test, so FPR = T FP /P N . Similarly, the true positive rate (TPR) is the proportion of malicious embedding steps that have been rightly reported as malicious by the test, and we have TPR = T TP /P P .

The true positive test fraction (TPTF) is the proportion of positive tests that correctly identified malicious embedding steps (TPTF = T TP /(T TP + T FP )).

Securing Vivaldi

We experimented with our detection scheme on a Vivaldi system subjected to a colluding isolation attack as described in the previous chapter and in [START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF]. In this scenario, malicious nodes are trying to isolate a target node, by repulsing all other nodes away from it. The malicious nodes agree on a large "exclusion" zone around the target node and randomly set their own coordinates outside this zone to try and attract honest nodes out of the exclusion zone. Note that an attacker always uses the same coordinate when lying to a given honest node.

Detection Method Performance

To evaluate the efficiency of the test, we first plot in figure 4.9, ROC (Receiver Operation Characteristics) curves observed for different significance levels (α) and several intensities of attacks. These plots show, for each significance level 4 , the point corresponding to the false positive rate along the x-axis and to the true positive rate along the y-axis, with one curve per malicious group size (line x=y is plotted as a reference). Obviously, the closer to the upper left corner of the graph a curve is, the better, since such points correspond to high true positive rates (i.e. a high proportion of positives being reported as such by the test) for low false positive rates (i.e. a small proportion of negatives incorrectly reported as positives). We observe that from this perspective, the detection method can be considered to be excellent for 20% of malicious nodes or less, and still performs well even under heavy attack of up to about 30% of malicious nodes, while the power of the detection method naturally decreases as the malicious population becomes more significant. Another interesting properties of ROC curves is that they show the optimal range for the significance level. Indeed, as the slope of the ROC curve flattens, the increase in true positive rate is proportionally smaller than the corresponding increase in false positives. In other words, a higher significance level, although it always increases the true positive rate of the test, is not always productive as it eventually does more bad than good through increased false positive rates (i.e. the proportion of normal embedding steps that are aborted increases). This means that the significance level of the test should be set to a value that yields a point in the "elbow" of the ROC curve. Based on figure 4.9, we can deduce that a significance level of 5% seems to be a good compromise. 4.10 shows the true positive test fraction of the detection method for various test significance levels under various intensity of attacks. We see that the proportion of positive tests that are true positives is constantly high, regardless of the significance level chosen, for moderate to quite significant proportions of malicious nodes in the population (up to 20% of malicious nodes). However, thereafter the proportion of correct positive tests starts to decrease, although the rate of decrease is inversely proportional to the significance level used. This is because a higher significance level produces more positive tests, catching most malicious embedding steps, and so many more false positives are needed to make up a significant proportion of these. In light of this, a significance level of 5% offers a good compromise. Figures 4.11 and 4.12 show the false positive and negative rates respectively. As expected, a higher significance level results in a more aggressive test that incorrectly classifies a larger portion of normal embedding steps (figure 4.11) as malicious, while a more lenient test (lower significance level) wrongly reports a higher proportion of malicious embedding steps as normal (figure 4.12).

Incorrect test results do have a negative impact on the embedding system: false positives artificially reduce the size of available normal nodes that can be used for normal embedding; false negatives give malicious nodes opportunities to corrupt and distort the coordinate space, which can propagate through the system and result in a greater proportion of normal nodes being identified as malicious (false positives) because of mis-positioning. This is exemplified in figure 4.11, where the false positive rate increases faster, as the population of malicious nodes increases, for lower values of the significance level of the test. Also, despite the fact that the false negative rate curves (figure 4.12) clearly exhibit negative slopes, one should note that these rates decrease much slower than the increase in malicious population. That is to say that as the number of malicious nodes in the system increases, the number of false negatives does increase, and more damage is incurred in the coordinate space. Although the accuracy of coordinate systems increases with the number of participating nodes, false negatives can therefore have a greater impact on the system than false positives and should therefore be thwarted in priority. As the false negative rates exhibited by tests with significance levels of 5% and 10% are roughly similar, while the more aggressive test yields proportionally a higher false positive rate, the significance level of 5% is a good compromise.

Embedding System Performance

From section 4.6.2, it should be clear that a significance level of 5% gives the overall best test performance. We therefore set the significance level to this value and assess the resistance of a Vivaldi system under various intensity of attacks.

The cumulative distribution function of the measured relative errors, across all normal nodes, after convergence (in the sense of error convergence as defined in section 3) is shown in figure 4. [START_REF] Costa | Practical Internet coordinates for distance estimation[END_REF]. We see that the detection mechanism renders the system practically immune to the attack, when the proportion of malicious nodes is 30%, or less, of the overall node population. Although the system does indeed show degraded performance for higher intensities of malicious attacks, the steeper slope of the CDF with detection, compared to the corresponding curve without (e.g. curves for 50% of malicious nodes), shows that the detection mechanism is not completely overwhelmed and still offers good protection by significantly reducing the impact of the attack.

Securing NPS

To test our proposed detection method in the context of the NPS coordinate system, we chose to study the effects of colluding isolation attack as described in the previous chapter and in [START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF]. The malicious nodes cooperate with each other and behave in a correct and honest way until enough of them become reference points at each layer. As soon as a minimum number of malicious reference points has been reached (in our experiments this number is set to 5) in a layer, these attackers identify a common set of victims (50% of the normal nodes they know from the layer directly below). When involved in the positioning of their victims, the malicious nodes agree to pretend they are all clustered into a remote (far away) part of the coordinate space and try and push the victims into a remote location at the "opposite" of where the attackers pretend to be, in order to isolate the victims from the other nodes in the coordinate space. In order to evade detection, including the basic detection method proposed in NPS and which is always turned on in our experiments, the malicious nodes use the sophisticated anti-detection method proposed in [START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF] during their attacks.

Detection Method Performance

Figure 4.14 shows the ROC curves for the detection test in NPS. These curves show characteristics similar to those observed in the Vivaldi system (see section 4.6.2), albeit slightly better. In particular, these curves show that the detection method withstands heavier attacks better in NPS than in Vivaldi.

There are several reasons for this. First, the basic detection method in NPS works in concert with our own, providing greater opportunities to identify malicious behavior. Also, by its very nature, the embedding method in NPS is less prone to mis-positioning error propagation amongst normal nodes, as nodes in the lower layer do not take part in the embedding of other nodes. And finally, by design, the attack considered in this section makes fewer victims than that studied in section 4.6.2 (i.e. 50% of normal nodes as victims vs 100% in Vivaldi).

The same observation is also true for the false positive and false negative rates (not shown) with again, overall, a significance level of 5% seemingly offering the best compromise between "catching" malicious embedding steps while not being overly cautious and over-reacting to normal variations in network conditions.

The similarities between the test performance under NPS and Vivaldi, despite the different nature of the attacks under consideration and even differences in coordinate "structure" (two-dimensional with height for Vivaldi versus eight-dimensional for NPS), illustrates the generality of the proposed detection method. This is because our detection test is based on the modeling of a dimension-less quantity (the relative error) which is at the very core of any coordinates embedding system.

Embedding System Performance

We study the performance of the NPS embedding system when subject to increasing intensity of attacks, while being protected by our detection scheme. Note that in this section, "detection off" really means that our proposed detection mechanism is not used, but the basic NPS detection mechanism is still "on". tem. We note again similarities with the dynamic behavior of similar Vivaldi systems, except that the tail of the CDF for 50% malicious nodes with detection is heavier than the corresponding curve in the Vivaldi case. Keeping in mind that in NPS not all nodes are victims and that not all normal nodes will propagate mis-positioning errors, this indicates that the attack is still quite effective against its victims, albeit "dampened" by the detection mechanism. This effect is compounded by the fact that, with our simple detection protocol, malicious nodes that have found their way into the layer hierarchy of NPS and act as Reference Points, do stay in place throughout the experiment, despite numerous detections of their corrupt embedding steps.

Nevertheless, the detection method proposed affords near immunity to the system up to rather severe attack conditions (e.g. about 30% of malicious nodes in the system).

Conclusions

We have presented a method for malicious behavior detection to secure the embedding phase of Internet coordinate systems. Our method does not rely on the geometric properties of the coordinate space, and is therefore unaffected by potential triangular inequality violations which often occur in the Internet [START_REF] Lua | On the accuracy of Embeddings for Internet Coordinate Systems[END_REF][START_REF] Zheng | Internet Routing Policies and Round-Trip Times[END_REF]. Instead, our detection test is based on the modeling of the dynamic relative errors observed in a clean system. The relative error is a dimension-less quantity which is at the very core of any embedding method, leading us to believe that our proposed detection test can effectively identify malicious behavior in very many embedding protocols and coordinate space structures that are under a potential very large range of attacks. The experiments presented in this chapter do show that the performance of the detection test is effectively the same in two different scenarios involving different embedding protocols and different attacks. As far as we know, this is the first such general detection test, capable of surviving sophisticated attacks. Also, we consider exclusively attacks aimed at distorting the coordinate space, carried out by nodes inside the embedding system. Our method thus succeeds where more obvious methods based on authentication would fail.

Nevertheless, with a trusted Surveyor infrastructure in place, it could be argued that using these Surveyors for positioning other nodes would ensure immunity to any insider attacks. For Vivaldi, using the Surveyors for positioning would mean that normal nodes only choose Surveyors as neighbors. The embedding performance of such Vivaldi scenario is depicted by the "using dedicated Surveyors for embedding"-curve of figure 4.16, with the 1% Surveyors of the simple k-means deployment method. It can clearly be seen that such use of the Surveyor infrastructure trades embedding accuracy for increased security. A similar NPS scenario, where only Surveyors would be chosen as Landmarks and reference points, unsurprisingly led to embedding performance equivalent to a clean NPS system, as the hierarchical embedding structure in both systems are very similar. An NPS system where only Surveyors would be chosen as Landmarks and reference points actually looks like a hybrid system between GNP [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF] and NPS: it is a fixed infrastructure system (like GNP), but with distributed Landmark coordinate computation and a hierarchical structure (like NPS). In both cases above, a clear scalability issue arises as the load on each Surveyor increases as their number decreases. In light of the discussion on strategic Surveyor deployment, as well as lower bound on the number of required Surveyors (see section 4.4.3), it is not clear that the solution of embedding against Surveyors only is practically viable. Even if it were, a hybrid solution, where Surveyors would be used for malicious activity detection under mild to medium attack intensities and exclusively used for embedding under more severe conditions, would be more accurate and afford better scalability.

Finally, even though the embedding phase of the system may have been secured, this would not prevent a malicious node from blatantly lying about its coordinate when a node requests them for simple distance estimation, during the "usage phase" of the coordinate service. This normal use of the coordinates service must therefore also be secured. We address this problem in the next chapter.

SECURING THE DISTANCE ESTIMATION PHASE

Summary

In this chapter, we address the issue of asserting the accuracy of Internet coordinates advertised by nodes of Internet coordinate systems during distance estimations. Indeed, some nodes may even lie deliberately about their coordinates to mount various attacks against applications and overlays.

Our proposed method consists in two steps: 1) establish the correctness of a node's claimed coordinate by using the Surveyor infrastructure and malicious embedding neighbor detection proposed in our previous chapter on securing the coordinates embedding phase; and 2) issue a time limited validity certificate for each verified coordinate.

Validity periods are computed based on an analysis of coordinate inter-shift times observed by Surveyors. By doing this, each surveyor can estimate the time until the next shift and thus, can limit the validity of the certificate it issues to regular nodes for their calculated coordinates. Our method is illustrated on a trace collected from a Vivaldi system deployed on PlanetLab, where inter-shift times are shown to follow long-tail distribution (lognormal distribution in most cases, or Weibull distribution otherwise). We validate the effectiveness of our method by measuring the impact of a 97 variety of attacks on distance estimates.

Introduction

The security of the embedding phase, or in other words the coordinate computation phase, of Internet coordinate systems has has been addressed in the previous chapter by proposing a general, embedding protocol-independent cheat detection mechanism based on the Surveyor infrastructure. However, ultimately, Internet coordinate systems are used to estimate distances between nodes, based on their coordinates only, even and all the more so if these nodes have never exchanged a distance measurement probe. Whatever mechanism is used to obtain a node's coordinate (e.g. direct exchange, DNS-like repository, etc.), each node must somehow report its own coordinate computed during the embedding phase of the system. This is because, for scalability reasons, nodes compute their own coordinates in a distributed way. This, of course, provides a malicious node with an opportunity to strike: in order to achieve some application-dependent goal or advantage (e.g. free-riding, denial-of-service, isolation, ubiquity gift, etc), a node can repeatedly lie about its coordinate. Simply lying about its coordinate could seriously disrupt the operations of Internet applications relying on coordinate-based systems for distance estimation. Several studies have quantified the impact of cheating on topology-aware Internet applications, and have shown that simple attack strategies can prove to be very effective [START_REF] Mathy | Impact of Simple Cheating in Application-Level Multicast[END_REF][START_REF] Walters | Mitigating Attacks Against Measurement-Based Adaptation Mechanisms in Unstructured Multicast Overlay Networks[END_REF][START_REF] Zhang | Impact of the Inaccuracy of Distance Prediction Algorithms on Internet Applications, an Analytical and Comparative Study[END_REF]. This chapter addresses the question of guaranteeing the veracity of the coordinates advertised by nodes.

To do so, we propose to leverage the Surveyor infrastructure and embedding cheat detection test. More precisely, we propose that several Surveyors measure their distance to a node in order to verify the correctness of its claimed coordinate (using the cheat detection test). If all Surveyors agree that this coordinate is the node's true coordinate, a time limited validity certificate, including the certified coordinate, is issued to the node.

A certificate validity time period is necessary because, due to dynamic network conditions, nodes' coordinates vary in time. Upon a coordinate change, an honest node would stop using its current certificate and seek a certification of its new coordinate. On the other hand, a malicious node could keep using a certificate related to a previous position, hence a careful balance between scalability and certificate validity is desirable. To achieve this, one of our contributions is to study the coordinate inter-shift time (i.e. the time between coordinate changes at a node) as observed for a Vivaldi system running on PlanetLab. We found that the coordinate inter-shift times at most nodes follow a lognormal distribution, with the rare cases when this distribution is inappropriate being accounted for by a Weibull distribution (note these are both long-tail distributions).

In section 5.3, we study and characterize the coordinate inter-shift times and show that these times observed at Surveyors can adequately and statistically model inter-shift times at closeby nodes. Section 5.4 describes the certification procedure in detail, while performance evaluation of our proposal in the context of various attacks is presented in section 5.5.

Coordinates Evolution model

Our goal is to characterize and ascertain forward validity of nodes' coordinates during the distance estimation phase. We therefore concentrate on tracking the evolution in time of coordinates along the different axis of the coordinate space by observing their evolution in a clean system (without any malicious activity).

Experimental Set-up

A first step in our study consists in characterizing the dynamics of coordinates, as observed by nodes in a clean coordinates system, with no malicious node. For this first purpose, we used an initial trace of measurements obtained by running the Vivaldi System on 600 planetLab machines through a period of 18-days. To evaluate our method and demonstrate the validity and effectiveness of our proposal to deal with various attacks, we also used in a second step live-PlanetLab experiments, deployed as a Vivaldi service over a three-weeks period, .

In our initial trace, we kept the coordinates of 450 nodes, as several nodes, that have been down for more than one week or experienced connectivity troubles, have been filtered out. Some of them even do not respond to different RPC requests sent by the Vivaldi service.

In this trace, Vivaldi is using a 3-dimensional Euclidean space for the embedding. Each 10 minutes, corresponding to an embedding step, nodes are adjusting their coordinates based on a one-to-one interaction with another node, called a peer node. Finally, Vivaldi nodes are filtering the stream of latency measurements from a remote node and turn these into expected latency values, based on a Moving Percentile (MP) filter, a variant on the Moving Median filter, used to filter out heavy-tailed errors [START_REF] Ledlie | Network Coordinates in the Wild[END_REF][START_REF] Moore | Median Filtering for Removal of Low-Frequency Drift[END_REF]. This filter acts as a low-pass filter, where anomalies are ignored while a baseline signal passes through. This allows Vivaldi to smoothly adapt to shifts in the baseline (that BGP route changes cause for example). The goal of the latency filter is to summarize the measurements, providing a current and stable description of the expected latency between any two nodes. Ledlie et al. [START_REF] Ledlie | Network Coordinates in the Wild[END_REF] found that using this simple latency filter with the a size of the history window equal to four observations and a percentile of 25% was a good predictor for the next observed latency (i.e. consider the minimum value of a four-latency measurements stream, for coordinates computation).

The PlanetLab experiments were conducted over a set of 280 PlanetLab nodes spread world-wide, running Vivaldi, as a coordinate-embedding service. For the purpose of our experimentations, we slightly modified the logging functions of the Vivaldi protocol. Each node is running several instantiations to allow us experimenting different parameters in similar conditions. Nodes are then updating their coordinates as needed, depending on the embedding step defined in each instantiation of the Vivaldi protocol. In the same way, the dimension of coordinates varies from one instantiation to another on the same node1 , and a node is acting as a malicious node or as a honest 'normal' node.

Each node had 20 neighbors (i.e. was attached to 20 springs), 10 of which being chosen to be closer than 50 ms. Again, the constant fraction C c for the adaptive timestep is set to 0.25 (see chapter 2, section 2.4.2). When needed, Surveyor nodes were chosen that represent 8% of the overall population as discussed in the previous chapter. We observe that the system after roughly 250 embedding steps, reaches a stationary regime, but coordinates continue to fluctuate. Looking further in the entire set of nodes' coordinates, we observe that coordinates steadily variate, moving away from the origin of the coordinate system. The rate of these variations is low enough to allow distance estimation at the application level, but this prevents us from certifying permanent coordinates.

Observations

More specifically, because at any instant in time, the RTT that can be measured between two nodes depends on the state of the network (e.g. traffic load, state of queues in routers, etc), the exact value of the RTT varies continuously. However, it has been shown that RTT values in the Internet exhibit some stability in a statistical sense [START_REF] Zhang | On the Constancy of Internet Path Properties[END_REF], with the statistical properties of RTTs exhibiting no significant change at timescales of several minutes. It is that property that embedding systems exploit to provide good distance estimates while only needing to have nodes adjust (recalculate) their coordinates on a periodic basis. Consequently, the node's coordinate can be viewed as a discrete stochastic process, computed at each embedding step.

Regardless of the dimensionality used by the coordinate-systems, our main goal is to assign to any coordinate given by a node, a reliability value that is telling the likelihood that this coordinate is still valid and has not changed. For this purpose we observe for our set of 450 planetlab nodes the inter-shift time distribution, corresponding to the amount of time (in terms of embedding steps intervals) during which, nodes stick to their positions, i.e. the coordinates do not change. This distribution is denoted T i for each node i. It is important to note that although we observed that in our traces, a variation of one coordinate component was synonym to the variation of both others, we consider the inter-shift time as the laps of time corresponding to the non variation of all the coordinate components of this node.

Basically, we would like to determine which probability distribution is suitable to describe the inter-shift times. In the following, we will use our empirical data sets of inter-shift times to find the probability distribution that best describes the distribution values of each T i .

Inter-shift Time Distribution Fitting

For choosing the best suitable distribution, we use a set of candidate distributions containing lognormal, Weibull, Rayleigh and Gamma distributions2 .

For each one of the 450 nodes in the dataset, we apply a two-step procedure. In the first step, we derive the maximum likelihood estimates of parameters of each distribution in the candidate set. The likelihood is the probability to get the observed inter-shift times for some hypothetic distribution. The estimates of the distribution parameters are then the values that maximize this likelihood.

In a second step, we used goodness of fit tests to evaluate if the hypothesis that the observed values T i come from the candidate distribution can be rejected or not. The goodness of fit evaluation was done using the popular and robust Kolmogorov-Smirnov (K-S) test [START_REF] Shorack | Empirical Processes With Applications to Statistics[END_REF], applied at a significance level of 5% (see Appendix A for details).

We show in figure 5.2, the results of the fitting done on one of the datasets relative to node 181. Simple inspection by eye shows that the lognormal distribution produces the best fits among the set of distributions. This is validated by the K-S test that rejects all the candidate distributions but the lognormal. Using the fitting procedure described above, we tried to fit the inter-shift datasets. The first interesting result we found is that all of the empirical distributions examined can be fitted to a known distribution. A large majority of distributions can be fitted into a lognormal distribution. The lognormal hypothesis was rejected for only 5 datasets out of the 450. Looking further in these 5 inter-shift datasets, we observed that they have

Correlation between Surveyors and Nodes inter-shift Distributions

Having shown that inter-shift time distribution of our population of nodes in the Vivaldi system can be fitted in either a lognormal distribution in most cases or a Weibull distribution otherwise whose parameters can be obtained by a maximum likelihood method, the next question is how well the shifts as observed by Surveyor nodes can be used as representative of the shifts of regular nodes. Basically, if the inter-shift distri-bution of a node as seen by the surveyors is the same as the real inter-shift distribution, the former may be used as a reference to validate the node's coordinate.

The verification of this hypothesis is done by comparing the sequence of inter-shift as seen by surveyors and the real inter-shift of a node and asking if the hypothesis that these two sequences come from the same distribution can be rejected or not. The latter test is done using a two-sample Kolmogorov Smirnov Test (with a significance level of 5%) that precisely gives an answer to the previous question. For each of the 35 surveyor nodes, we applied therefore 415 two-sample K-S tests.

Then, we analyzed for each surveyor node the likelihood that the two-samples KStest is rejected as a function of the distance (measured as an RTT) delay between the surveyor node and the tested regular node. The likelihood is obtained as the ratio between the number of nodes with a given delay that reject the test and the overall number of regular nodes. Figure 5.3 shows this rejection ratio versus the distance (measured as an RTT) between a node and the corresponding Surveyor, as observed in our traces. Intuitively, a Surveyor should have tendency to have the same inter-shift distribution as nodes that are close by in terms of RTT as they are more likely to experience similar dynamics of the coordinate system. Figure 5.3 validates this intuition and shows that better locality between a node and its Surveyor yields more accurate fittings.

We therefore apply the following heuristics: the inter-shift time distribution of the closest Surveyor is used as the representative distribution for regular nodes.

Coordinate Certification

The method we propose to certify Internet coordinates consists in two steps:

1. the node coordinate verification test 2. computation of an estimated validity period for this coordinate.

The coordinate verification test leverages the Surveyor infrastructure and malicious embedding neighbor detection, while the validity period estimation is exploiting the inter-shift distributions we have studied in the previous section.

Coordinate Verification Principle

Recall from the previous chapter that our method for malicious embedding neighbor detection is based on a model of the evolution of a nodes's observed relative errors, during embedding steps. It is important to note that this malicious embedding neighbor detection test is based on relative errors, and thus simply tests the consistency between the estimated and measured distances between two nodes. In particular, this test is not able to evaluate the truthfulness of a node's coordinate. Indeed, if during an embedding step a node fakes its coordinate but at the same time delays the measurement probes in a way consistent with its faked position in the coordinate space (based on the knowledge of the correspondent's coordinate, as well as its own true and fake coordinates), then the resulting relative error measured between the two nodes is reduced (see figure 5.4). Indeed, if a node at coordinate X i fakes a coordinate X ′ i , then its real distance to another node (e.g. a Surveyor) at coordinate X j is RTT i,j (this RTT is the time the probe actually travels between the 2 nodes). To be consistent with its faked position, the faking node should delay the measurement probe by

||X ′ i -X j || -||X i -X j ||, so that the measured RTT, RTT ′ i,j = RTT i,j + ||X ′ i -X j || -||X i -X j ||.
The relative error that should have been measured is clearly

|||X i -X j ||-RTT i,j | RTT i,j
, while the relative error measured due to the faked position is

|||X ′ i -X j ||-RTT ′ i,j | RTT ′ i,j
. Simple substitution allows the measured relative error to be rewritten as

|||X i -X j ||-RTT i,j | RTT ′ i,j
, which is clearly lower than the relative error that would be measured if the node did not fake its coordinate (since RTT ′ i,j > RTT i,j ). Therefore, a node faking a position further away from the testing node will never fail a test that it wouldn't have failed in the first place if it wasn't faking. Consequently, to verify a node's coordinate, several such tests must be performed from vantage points (Surveyors) surrounding the node (see figure 5.6). In this case, a node could easily fake its coordinate and consistently delay probes so that it moved away from some Surveyors without being noticed. But such fake position would necessarily also result in the node moving closer to some other Surveyors and failing the corresponding malicious embedding neighbor tests as it is next to impossible to "speed up" a distance probe protected by the simplest of mechanisms (e.g. hashing, simple encryption, random probe numbers, etc). A node must be surrounded by at least one more Surveyors than there are dimensions in the space.

If the malicious embedding neighbor test is negative at each Surveyor chosen to surround the node (i.e. the relative error observed between the Surveyor and the node is considered normal), then the coordinate claimed by the node is considered correct. Note that this test is different from a normal "triangulation" approach, where the measured distances between the node and the Surveyors would be used alongside the Surveyors' coordinates to determine the node's own coordinate. Indeed, our test is in fact made up of multiple, independent tests on the plausibility of the observed relative errors and provides our method with an important resistance to the triangular inequality violations (TIVs) [START_REF] Zheng | Internet Routing Policies and Round-Trip Times[END_REF][START_REF] Lua | On the accuracy of Embeddings for Internet Coordinate Systems[END_REF] that can be commonly encountered in the Internet. This is because the Kalman filters underlying the tests are calibrated during normal embedding of the Surveyors, and thus in conditions where TIVs are naturally encountered, so the system noise resulting from these TIVs is therefore implicitly taken into account in the relative error tracking. We do not claim that our test is immune to the problems caused by TIVs (and these TIVs will be responsible for some of the false positives of our test), but it is nevertheless much less sensitive to them than a geometric approach like triangulation would be.

If a node cannot be surrounded by Surveyors (i.e. there is at least one axis along which the corresponding coordinate component of the node is either greater or smaller than the corresponding coordinate component of all Surveyors), then the node's coordinate cannot be verified. This is because the node could easily fake its position by moving away from the Surveyors along this axis, without being detected, by using the technique described in figure 5.4 with each Surveyor. It is therefore important to have Surveyors placed near the coordinate space boundaries, as well as inside the space (otherwise part of the nodes population may never be able to get coordinate certificates). More precisely, the convex hull3 of all nodes (including the Surveyors) should be composed of Surveyors only. Or seen differently, any node lying outside the convex hull of the set of Surveyors can never be surrounded and thus can never be issued a coordinate certificate. For this study, and to reflect a plausible deployment scenario, some of the Surveyors were deliberately placed near the space boundaries, so that the Surveyors' convex hull encloses most, but not all, nodes, while the other Surveyors were chosen at random (see Figure 5.5).

Protocol

A node who wishes to have its coordinate certified contacts the known closest Surveyor to its claimed coordinate. If this Surveyor is not the closest, the node is redirected to the closest one known by the Surveyor. For this, as well as the selection of Surveyors surrounding the coordinate claimed by a node to happen, Surveyors exchange their coordinates using a gossiping protocol.

Based on its knowledge of the position of other Surveyors, as well as on the coordinate of the node to be certified, the certifying Surveyor selects a set of Surveyors (a.k.a surrounding Surveyors) that surround the node's claimed position (possibly including itself) and informs these of the node's claimed coordinate so to ensure they all use the same node's coordinate for their distance estimates during their malicious embedding neighbor detection test.

Recall that Surveyors compute their own coordinate by using each other exclusively as embedding neighbors. This gives the Surveyors the view of a clean system without malicious insider attacks. Therefore, if Surveyors run their own malicious embedding neighbor detection test at each embedding step, all such tests should ideally be negative as Surveyors only have trusted and honest neighbors (other Surveyors). Unfortunately, no test is perfect and some amount of the tests carried out by each Surveyor will wrongly identify the neighbor as malicious. Such occurrence is a false positive and the Surveyor will take no action about the said neighbor (or more precisely the particular embedding step with this neighbor). However, carrying out such tests at every embedding step provides the Surveyors with estimates of two important test statistics: the false positive test ratio (FPTR -i.e. the percentage of the tests that were positive and wrongly identified a fellow Surveyor as malicious) and the true negative test ratio (TNTR -i.e. the percentage of the tests that were negative and thus correctly identified the fellow Surveyors as honest nodes).

Let Y i be the indicator random variable that represents the outcome of a malicious embedding neighbor detection test at the i th Surveyor (testing another Surveyor), with:

Y i =
0 if the neighbor identified as honest 1 if the neighbor identified as malicious Taking as null hypothesis H 0 that the tested node is honest (which is always the case when Surveyors are tested), the true negative test ratio (TNTR) estimate p i at the i th

Surveyor is Èrob Y i = 0|H 0 , the number of tests that were correct divided by the overall number of tests carried out. The FPTR is then obviously 1p i .

After performing the requested malicious embedding neighbor detection test on the node whose coordinate is to be certified, the surrounding Surveyors return the result of their test, along with their estimated TNTR, to the certifying Surveyor. If every test returned is negative (i.e. each surrounding Surveyor considered the node as honest), then the node's coordinate is deemed correct and verified and the certifying Surveyor proceeds to the second step of the certification described in section 5.4.2.

On the other hand, if at least one of the surrounding Surveyor returns a positive test, that is, did consider the node as potentially malicious because of too much of a deviation between the measured relative error and the expected one, the certifying Surveyor must decide whether to declare the node's coordinate as suspicious and thus refuse to issue a certificate, or whether further test should be carried out. To do so, the probability that the node, and its claimed coordinate, have been identified mistakenly as suspicious by the surrounding Surveyors is computed. This probability is simply 1 -i∈ξ j p i , where ξ j is the set of surrounding Surveyors chosen to verify the claimed coordinates of the node at this round of testing. If the overall probability that the node has been mistakenly classified as suspicious is greater than a given significance value γ, that is if 1≤j≤N (1 -i∈ξ j p i ) > γ, where N is the number of test rounds that have been carried out so far, then the certifying Surveyor starts another test round with a new set of surrounding Surveyors. Note that the sets of selected surrounding Surveyors at each round are not necessarily disjoint, although such property is desirable.

In this study, we used γ = 1% and limited N to 6 (i.e. a node is refused a coordinate certificate if the probability of mistaken refusal falls below 1% and/or the node fails 6 consecutive test rounds).

Evaluation

In this section, we seek to evaluate the effectiveness of our proposed coordinate verification method.

We first seek to validate the assumption that the FPTR values measured during embedding at Surveyors provide good estimates for the real FPTR values at these Surveyors. To do so, we let a vivaldi system, without cheat, converge and run on PlanetLab for over 2500 time ticks (i.e. embedding periods). the Surveyors measured their estimated FPTR by carrying out a malicious embedding neighbour detection test at every embedding step. At the end of the experiment, each Surveyor also measured its real FPTR by running a malicious embedding neighbour detection test to every other nodes in the system. Since this system does not have any malicious node in it, a failed test is a false positive. The CDF of the differences of these 2 values at each Surveyor is shown in figure 5.7. We see that the difference between the estimated and the real FPTR are mostly within less than 1% of each other, confirming that our proposed estimation method yields reliable FPTR estimates. Even in the cases where the FPTR estimates differ more than the real value, these will only affect the coordinate verification tests in which the corresponding Surveyors take place: in these cases the coordinate verification test will be slightly more aggressive than it ought to (since the FPTR estimate is smaller than the real value), favouring security. Next, we seek to further understand the behaviour of false positive and true negative occurrences. Figure 5.8(a) is a scatter plot of the distance between a node and its Surveyor, whenever the malicious embedding neighbour detection test through a false positive at the Surveyor. This figure clearly indicates that Surveyors hardly ever experience wrong test results when testing nearby honest nodes. Complementarily, Figure 5.8(b) shows that Surveyors are much more successful at identifying nearby honest nodes correctly. These results indicate that striving to choose surrounding Surveyors as close as possible to the node whose coordinate are being verified will increase the effectiveness of the coordinate verification test (by reducing the occurrences of false positive in the multiple test, through reduction of false positive occurrences in the component tests making this multiple test up). This is therefore the strategy adopted in the rest of this chapter. To assess the overall effectiveness of the proposed coordinate verification method, we then make all nodes try to move away in all direction, from their position in the converged system. In this experiment, each node varies the direction of its move one degree at a time. Along each direction, it tries to move a distance drawn at random form the distribution of the innovation process computed by the Kalman filter calibrated at the nearest Surveyor, in a bid to outsmart the malicious embedding neighbour detection test. After each move, the node requests a re-certification of its coordinate. The displacement achieved by the node until the corresponding fake coordinate is declared incorrect by our verification method is then recorded. Figure 5.9 shows, the average, minimum and maximum displacement observed across all nodes, as a function of the direction of movement. Note that this figure only take into account the nodes that are eligible for certification (i.e. the nodes that lie inside the Surveyors convex hull, see section 5.4.1), meaning that 13 nodes are excluded from the experiment.

We see that the maximum displacement achieved by any node is below 10 ms, while the average is around 6 ms. Such deviations are of the order of the distance prediction accuracy (they will not decrease the accuracy of the coordinate system in any significant way) and will be acceptable to many applications. Finally, we experimented with a simple attack, carried out by a growing malicious node population that has access to the coordinates of all nodes in the system. The malicious nodes compute the centroid of the overall node population, and then try to move in a random direction away from this centroid (adding 2 seconds) in order to be isolated. Figure 5.10 shows the detection rate, that is the percentage of certificate requests for faked coordinates that was denied, as a function of the malicious population size, for various dimensions of the coordinate space. Note that although these curves show a slightly decreasing trend, a smaller percentage of an increasing number of requests for faked coordinates does mean, in most cases, an increasing number of denials. With over 95% detection rates in most cases, the coordinate verification test can be considered as highly efficient.

However, tests may achieve high detection rates by being overly aggressive towards honest nodes that do not cheat. The false positive rate, that is the percentage of certificate requests for real coordinates that were wrongly denied, is a measure of this aggressivity towards non malicious nodes and should be kept as low as possible. Figure 5.11 shows the measured false positive rate, as a function of the size of the malicious population, for various dimensionality of the coordinate space. Note that these curves depend on the performance of the test only, and not on the activities of the malicious nodes. Also, note that as the population of malicious nodes increases, the corresponding population of honest nodes decreases, so an upward trend actually corresponds to fewer wrongly denied certification requests to honest nodes. With a false positive rate lower than 6% in all cases, our test can be considered as moderately, and acceptably, aggressive.

In light of the evaluation results presented in this section, we conclude that our proposed test for coordinate verification exhibits good performance and is fit for purpose.

Certificate Validity Computation

After the correctness of a node's advertised coordinates has been asserted, the next step is to issue the node with a certificate proving that the enclosed coordinate has been verified. This certificate will be delivered by the certifying Surveyor (i.e. usually the Surveyor closest to the node in the coordinate space, see sections 5.3.4 and 10).

As a coordinate certificate is associated with a particular position in the coordinate space that the node occupies or has occupied, one could expect that nodes request new certificate on moving to a new position. While this is certainly the behaviour anticipated from honest nodes that are interested in being able to prove their true position, malicious nodes might decide not to do so. Indeed, a malicious node is probably much more interested in faking its true position, and doing so with a certificate "proving" a position which isn't really its own, whatever this coordinate might be, is probably a bonus for such a node. While the coordinate verification protocol described in the previous section has been designed to prevent, as much as possible, malicious nodes from acquiring certificates for fake coordinates that they may choose, the problem of nodes using certificates for positions that have meanwhile changed, is still to be addressed.

The obvious way to solve this "stale" certificate problem, is to assign a reliability to the certificate. The reliability of the certificate decreases with time from its issuance time. When it crosses a certain threshold p th the certificate should be invalidated and eventually reissued. There is a tradeoff between certificate precision (and therefore security) and frequency of coordinate certification that is controlled by the reliability p th . Using larger value of p th , leads to higher reliability for certificates but at the cost of frequently reissuing certificates that are still valid. On the other hand lower p th results in lower reliability, but also reduces the load on Surveyors who would receive certificate requests less frequently. The issue here is really to find the right trade-off between scalability (by limiting the rate or amount of certificate requests) and security (by limiting the time lapse during which a malicious node may be able to use an old certificate after its coordinate has changed). We will therefore seek to exploit the results on coordinate inter-shift times presented in section 5.3.3 to compute certificate validity periods.

Note that this section assumes that all nodes in the system are "loosely" time synchronized: since coordinate inter-shift times have been shown to take values that are usually measured in minutes (see section 5.3), as long as all clocks are synchronized with an accuracy exhibiting a smaller timescale (say a few seconds), the notion of time in the system can then be considered unique. This time synchronization can easily be obtained through using NTP (at least about surveyors).

Principle

The problem of computing a validity period for coordinate certificates can be formalized through reliability theory. Let's define the survival function of the coordinate of node i as the probability, S i T 0 (∆) = Èrob T i > T i 0 + ∆ , that the next change of coordinate occurs later than ∆ time units after the last coordinate change, happening at time T i 0 . The survival function is thus related to the inter-shift time cumulative distribution

F i (∆) = Èrob T i ≤ T i 0 + ∆ through S i (∆) = 1 -F i (∆).
Recall from section 5.3.4, that the inter-shift times observed at a Surveyors are similar to those observed at nearby nodes. Hence, the inter-shift time distribution at a certifying Surveyor is the distribution used to compute the validity of the certificates it issues (since it issues certificates to the nodes that are closest to it than to any other Surveyors).

The survival function can be used to compute the validity of a certificate, that is the time remaining until the next coordinate change. The probability that the next position change occurs at or before time τ + ∆, given that the certificate is being issued at time τ is just:

Èrob T < τ + ∆|T > τ = Èrob τ < T < τ + ∆ Èrob T > τ = 1 - S i (τ + ∆ -T i 0 ) S i (τ -T i 0 )
In fact, we use the above probability, computed at a Surveyor whose survival function and last coordinate change time are S i (∆) and T i 0 respectively, to estimate the lapse of time until the next position change of the node requesting the certificate. In other words, the assumption here is that network conditions for nodes that are close to each other should change in a synchronous way. However, due to the asynchronous nature of embedding steps at different nodes, their respective coordinates will not all change at the same time, but we take as "reference" time, the moment when the Surveyor is expected to see a change in its coordinate.

In section 5.3.3, we showed that most nodes follow a lognormal or Weibull distribution. Depending on which distribution each surveyor node is observing (computing the likelihood at each embedding step), the above formula have a simple form for these two distributions.

For lognormal inter-shift distribution we will have:

S(∆) = 1 -Φ( ln ∆ σ ) Èrob T < τ + ∆|T > τ = 1 -1 -Φ( ln(τ+∆-T i 0 ) σ ) 1 -Φ( ln(τ-T i 0 ) σ )
where the function Φ(.) is the complementary error function and σ is its shape parameter of the lognormal distribution. For Weibull distributions we will have:

S(∆) = 1 -exp(∆ γ ) Èrob T < τ + ∆|T > τ = 1 -1 -exp((τ + ∆ -T i 0 ) γ ) 1 -exp((τ -T i 0 ) γ )
where γ is the shape parameter of the Weibull distribution.

The validity time of a certificate, ∆, is then computed by setting Èrob T < τ + ∆|T > τ = p th , where p th is the chosen reliability of the estimate (i.e. the long-term proportions of validity periods that will expire before the corresponding coordinate change).

The certificate then consists in the verified coordinate, the timestamp of the certificate creation, the validity period ∆ of the certificate, as well as the identification of the node the certificate is delivered to (i.e. IP address). The certificate is then signed by the the certifying Surveyor using appropriate credentials and encryption keys and issued to the node.

Evaluation

To evaluate the effectiveness of our certificate validity computation, we study the over-estimation resulting from each certificate: for each certificate issued, if the corresponding node moves before its current certificate expires, we record the residual time left on the certificate. This over-estimation is an important security parameter, as it is the lapse of time a malicious node could use a "stale" certificate. Figure 5.12 shows the CDF of over-estimation times when the certificates are issued by either the closest Surveyor or a Surveyor chosen at random. We can clearly see that most certificates will not outlive their corresponding coordinates by more than 2 embedding periods in the case where they are delivered by the closest Surveyor. This is a good result, as many a time, coordinate changes in such timescale will be "localized" in space. The figure also confirms that the accuracy of the validity periods, as thus the security of the system, is improved if coordinates are certified by nearby Surveyors.

Scalability is also an important factor for any certification scheme. Although underestimation of the validity period of certificates does not pose any security issue for the system, it does tend to increase the load on the system, and on the Surveyors in particular. Obviously, the higher the probability threshold used to compute the certificate validity time, the shorter this time will be. We therefore measure the mean validity period over all certificates for various values of the probability threshold p th . Figure 5.13 shows the corresponding average certification rate, which is the inverse of the mean validity period. The average certification rate gives the average number of certification requests that will be issued per node and per time unit (here the embedding period) to the system. This number, multiplied by the number of nodes in the system, and divided by the number of Surveyors and the embedding period gives a certificate request rate per second at each Surveyor. Figure 5.13 shows that the average certification rate increases gently as the probability threshold increases (i.e. as the computation becomes more conservative). This behaviour shows that we can afford a reliability of 95% (and therefore high security) with moderately low overhead.

Distance Estimation Performance Evaluation

In this section, we study the impact of an attack on the accuracy of distance estimations, with and without our proposed coordinate certification defense mechanism.

The attack consists in malicious nodes choosing, once the Vivaldi system has stabilized, a target they wish to get closer to (each malicious node chooses a target at random amongst the honest nodes), and moving in a straight line towards this target by steps computed from the innovation process of their Kalman filter (see chapter 4, Figure 5.12: CDF of Over Estimation Times (p th = 0.95), Embedding period = 10mn section 4.3.1). After each displacement, the malicious node seeks to have its newly faked coordinate certified. This strategy is designed to outsmart the tests used for coordinate verification, by only taking (fake) steps that could be attributed to normal system dynamics, as well as caused by normal noise, by the detection test described in the previous chapter. We choose such subtle attack, as more obvious displacement caused by fake coordinate would be easier to detect.

Obviously, in the case where coordinate certification is employed, malicious nodes are limited to fake coordinates they can get a certificate for.

We carry out this attack on our PlanetLab experimental setup, with a varying population of malicious nodes.

To assess the impact on distance estimation, we define the following metrics:

Relative Estimation Error RER =

|||C ′ i -C j ||-||C i -C j ||| ||C i -C j ||
, where C i is a node's real coordinate in the system without malicious activity, and C ′ i is a node's advertised coordinate (and C ′ i is either faked, certified or both).

Security Gain Ratio SGR = meanRER on /meanRER off , where meanRER on (meanRER off resp.) is the average RER measured between all pairs of node when the security mechanism is on (off resp.).

Figure 5.14 shows the SGR observed at the end of the experiment that was allowed to run for a considerable time after convergence of the original (clean) Vivaldi system. The curve labeled "ratio1" depicts the SGR measured in the presence of malicious nodes, while the curve labeled "ratio2" depicts the SGR measured in the clean Vivaldi system without malicious activity.

From this figure, we can conclude that the accuracy of distance estimation in the system with malicious nodes is much improved when coordinate certification is in use than when it is not. This is because the coordinate verification phase of the certification filters out most of the faked displacements. We also see that the curve "ratio2" exhibits a value of 1, indicating that the presence of the certification system does not degrade the performance of the clean system without malicious nodes (in other words, the coordinate certification is very much non intrusive).

Conclusions

In this chapter, we have presented a coordinate certification method to protect the distance estimation phase of Internet Coordinate Systems from nodes lying about their coordinate. This work thus complements our detection protocol for the embedding phase security proposed in the previous chapter.

The proposed certification method is based on a coordinate verification method, along with a validity period estimation for the corresponding certificate. This method has been shown to be effective, enjoying good verification test performance (high true positive detection rate with low false positive rates), while achieving a very good tradeoff between scalability and security. Indeed, the validity periods of certificates are rarely over-estimated, while they still do not trigger too frequent re-certifications.

Although this work focused on Vivaldi for measurements and experimentations, the method proposed for coordinate certification is independent of the embedding protocol used. This because the malicious embedding neighbour detection test that forms the basis of the coordinate verification is itself independent of the specifics of the embed-ding protocol, and because the validity period computation only depends on observed coordinate inter-shift times. Our proposed method would then be general enough to be applied in the context of coordinates computed by other Internet coordinate systems than Vivaldi.

CONCLUSIONS AND FUTURE WORK

Internet coordinate systems (e.g., [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF][START_REF] Pias | Lighthouses for Scalable Distributed Location[END_REF][START_REF] Costa | Practical Internet coordinates for distance estimation[END_REF][START_REF] Ng | A Network Positioning System for the Internet[END_REF][START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF][START_REF] Shavitt | Big-bang simulation for embedding network distances in euclidean space[END_REF], etc.) embed latency measurements amongst samples of a node population into a geometric space and associate a network coordinate vector (or coordinate in short) in this geometric space to each node, with a view to enable accurate and cheap distance (i.e. latency) predictions amongst any pair of nodes in the population. Extensive measurements and analysis from a live, large-scale deployment have shown network coordinate systems to be fit for purpose [START_REF] Ledlie | Network Coordinates in the Wild[END_REF], making them a valuable tool to support distributed applications, systems and overlays (e.g., [START_REF] Stoica | Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[END_REF]10,[START_REF][END_REF]) that rely on, and benefit from, the notion of network topology-awareness. However, these coordinate systems only achieve desirable accuracy, robustness, stability and scalability properties at the expense of rather slow convergence times -in other words, a new node joining the coordinate system may not reach an accurate value for its own coordinate before several tens of seconds or even several minutes. Such convergence properties argue in favor of a deployment of Internet coordinate systems as an always-on, large-scale service.

In this thesis, we first studied in chapter 3 various types of attacks on two prominent coordinate system proposals. One of our salient findings is that larger systems are consistently more resilient than smaller ones. Given the observation in [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] and [START_REF] Ng | A Network Positioning System for the Internet[END_REF] that larger systems are more accurate and the well known fact that larger systems converge slower at start-up time, there seems to be a compelling case for large-scale coordinate systems to be built as a virtual infrastructure service component. The paradox is of course that always-on, large scale systems supporting many different applications will always attract more attacks than systems with a smaller reach, while the large size of 123 the system itself would act as a particularly good terrain to create especially virulent propagation of the attack.

Our results show that there is an intrinsic trade-off to be made between accuracy and vulnerability. Indeed, we have shown that the more accurate the system for a given system size, the more susceptible it was to a same proportionate level of attack.

We have also observed that while an attack is in full swing, the performance of the coordinate systems (and of the applications it supports) can easily degrade below that of a system where coordinates are chosen randomly, whilst the aftermath of an attack could have very long lasting effects on the system due to a small number of remaining malicious nodes.

Infrastructure-based systems can also, under some well chosen attack strategies, be as vulnerable than those based on the peer-to-peer paradigm. Furthermore, the security mechanisms that have been proposed to date to defend against malicious nodes are clearly rather primitive and still in their infancy and definitely cannot defend against all types of attacks.

In the perspective of designing a detection protocol or a security mechanism, these results guide us to track the normal evolution of the coordinate-based systems, with a dimension-less metric (i.e. relative error), in order to make the technique generally applicable to different coordinate systems, and less-sensitive to different parameters we studied in chapter 3.

Therefore, in a second step, we addressed ways to secure such coordinates-based systems in a general and effective way. In chapter 4, we first show that the dynamics of a node, in a coordinate system without abnormal or malicious behavior, can be modeled by a Linear State Space model and tracked by a Kalman filter. Then we show, that the obtained model can be generalized in the sense that the parameters of a filter calibrated at a node can be used effectively to model and predict the dynamic behavior at another node, as long as the two nodes are not too far apart in the network.

In practice, we introduced in chapter 4 the concept of Surveyor nodes which, by design, are immune to embedding attacks and do observe the properties of the coordinate system in clean conditions. The Surveyors make up the basis of a "security infrastructure". It is important to note that the deployment of Surveyors does not equate to imposing an embedding infrastructure: peer-to-peer based embedding systems, like Vivaldi, do retain their infrastructure-less embedding characteristics. Indeed, apart from a test to accept or filter out embedding steps, our method does not entail any change to the operations of the embedding protocols.

The operations of the proposed detection protocol were deliberately kept simple and tested on systems where Surveyors were chosen randomly, although their representativeness increases with closeness to their "clients". Despite the possibly nonoptimal Surveyor distribution resulting from such a choice, the results obtained show the effectiveness of our proposal in securing Internet coordinate systems. Nevertheless, given the enhanced coordinate service afforded by our detection test and simple detection protocol, one might envisage that ISPs may readily want to deploy Surveyors within their network to offer enhanced coordinate service to their customers. Such business-driven strategic deployment can only improve representativeness of Surveyors, and thus improve the security of large-scale coordinate service, with possibly a much smaller proportion of Surveyors than the upper bound reported in this thesis (as illustrated by the simple k-means deployment in chapter 4, section 4.4.3). More sophisticated Surveyor selection mechanisms than those presented in this thesis could also result in better security through better representativeness in large-scale coordinate systems.

Furthermore, each node using malicious behavior detection does so in isolation, as there is no cooperation between nodes in a bid to improve detection and identification of malicious nodes. Instead, any embedding step identified as malicious by a node is simply, and quietly, ignored and discarded locally. One of the reasons the detection protocol was designed in this way was to avoid potential denial-of-service attacks that could result from the sharing of information about malicious activity, with the view of excluding offending nodes. Indeed, such an approach could open the door to an attack that consists in trying to get honest nodes excluded from the system through the collusion of wrong malicious reports. Trust propagation could be used to mitigate or remove this threat and thus allow detection cooperation amongst nodes, which could only improve the security of the overall system and push the boundary of applicability of the detection by reducing further the impact of very large-scale attacks on the embedding system.

Considering attacks directly against the surveyor infrastructure is also one of our future directions. Indeed, there are at least two types of attacks that could be performed against the Surveyors infrastructure. The first one is a direct Denial of Service attack, where Surveyors would be flooded for instance. Since the surveyors are known, a more subtle attack, could also consist in a a large group of attackers sending enough traffic on the link between surveyors, causing queuing on those links (link clogging), to make the surveyors filters become mis-calibrated. Ultimately, a mis-calibration means a non-representativeness of the Surveyor infrastructure, and thus less accurate positioning of nodes in the coordinate-based system, or even more false positives in our detection protocol.

Even though this thesis does not address the problem of such external attacks on the infrastructure (e.g. denial of service attacks, "link clogging", etc.), we note that solutions to such attacks have been proposed in several other works (e.g. [START_REF] Keromytis | SOS: Secure Overlay Services[END_REF][START_REF] Jung | Flash Crowds and Denial of Service Attacks: Characterization and Implications for CDNs and Web Sites[END_REF]). Studying the impact and ways to integrate different mechanisms against attacks that target the Surveyors themselves is then still to be considered in our detections mechanisms.

In chapter 5, we also proposed a general coordinate certification method to protect the distance estimation phase of Internet Coordinate Systems from nodes lying about their coordinate. This complements our work on the embedding phase security, in the mission of securing Internet coordinate-based positioning systems.

Our method has been shown to be effective against sophisticated attacks, and to achieve a very good trade-off between scalability and security. However, we should note that a node knows when its next embedding will occur, and thus when its coordinate is likely to change. A malicious node could exploit this knowledge to seek to obtain a certificate (for its current coordinate) just before performing this embedding, as this could leave such node in possession of a certificate for a soon to be outdated coordinate. To palliate this problem, one could envisage that Surveyors carry out "spot check" on the validity of a node's certificate: if the certified coordinate fails a new coordinate verification test, the node is "penalized" for using an outdated certificate. Performing new tests integrating the ideas discussed above in our detection protocols, is an essential future work that is planished for the next few months.

Ultimately, we would like to end up with a practically user-friendly Secure coordinate-based service. Regardless of the accuracy of Internet coordinate systems, we believe that securing such systems is a necessary condition to their deployment. Indeed, without security of both the embedding and distance estimation phases, simple attacks have been shown to easily and seriously disrupt these systems and reduce their utility to next to nothing. We believe then that the increased robustness provided by the proposals presented in this dissertation, could act as a catalyzer to the acceptance and deployment of large-scale coordinate services in the Internet. Annex pected number predicted by the distribution under test. Its function uses the maximum difference over all T i values as its test statistic. Mathematically, this can be written as :

max(|F m (T i ) -G(T i )|)
where m denotes the total number of sample points, G(x) the fitted cumulative distribution function, M x the number of sample points less than x and F m (x) = M x /m.

A.2.2 The Lilliefors test

Lilliefors test is a modification of the K-S test, first presented by Lilliefors in [START_REF] Lilliefors | On the Kolmogorov-Smirnov test for normality with mean and variance unknown[END_REF].

The Lilliefors test evaluates the hypothesis that the sample has a normal distribution with unspecified mean and variance against the alternative hypothesis that the sample does not have a normal distribution. The main difference from the well-known Kolmogorov-Smirnov test (K-S test) is in the assumption about the mean and standard deviation of the normal distribution. The K-S test assumes the mean and standard deviation of the population normal distribution are known; Lilliefors test does not make this assumption. In the analysis of empirical data, more often than not the mean and variance of the population normal distribution are unknown, and must be estimated from the data. Hence Lilliefors test is generally more relevant than the K-S test.

The Lilliefors test statistic is computed from the maximum vertical offset of the empirical cdf's of (1) the sample, after conversion to Z-scores, and (2) the standard normal distribution. A sample is converted to Z-scores by subtracting the sample mean and dividing by the sample standard deviation, such that the mean of the Z-score series is 0 and the standard deviation is 1.0. Basically, considering a random sample T 1 , T 2 . . . T n of size n, which might be an observed time series. the Z-scores are computed as follows:

Z i = T i - T s i = 1 . . . n
chaque noeud peut être associé à une coordonnée virtuelle dans un espace approprié, la distance entre les noeuds est trivialement calculée sans pour autant avoir recours aux mesures directes. En d'autres termes, ces systèmes plongent les mesures des temps de latences (délais) entre une population de noeuds dans un espace géométrique et associent un vecteur de coordonnées (ou coordonnées) dans cet espace à chaque noeud, dans le but de permettre des prédictions de distances précises et peu onéreuses parmi n'importe quelle paire de noeud dans le réseau. L'avantage premier de ces systèmes, est que si les distances réseaux (dans le sens de délais ou de temps de latence) sont plongées dans un espace de coordonnées, où une position raisonnablement précise pour chaque noeud est établie, le surcoût de mesures produit par le positionnement, est ainsi amorti sur plusieurs prédictions de distances. Ceci réduit énormément le coût en terme de mesures de distances du système entier.

Des mesures et analyses approfondies de déploiements réels de ces systèmes ont montré qu'ils atteingnaient pleinement leurs objectifs [START_REF] Ledlie | Network Coordinates in the Wild[END_REF], faisant d'eux un outil précieux pour supporter les applications distribuées et réseaux de recouvrement (tels que [START_REF] Stoica | Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[END_REF]10,[START_REF][END_REF]), qui bénéficient de la notion de proximité réseau. En effet, les systèmes de positionnement à base de coordonnées atteignent plusieurs propriétés souhaitables, telles que la précision, la robustesse, la stabilité, ainsi que le passage à l'échelle et les surcoûts de communications peu élevés. Cependant, il est important de souligner que ces propriétés sont souvent réalisées aux dépends de temps de convergence assez longs. Dans de tels systèmes, les nouveaux noeuds, n'atteignent une bonne estimation de leurs coordonées, qu'après un laps de temps à l'échelle de dizaines de seconde, voire de minutes. Ceci est beaucoup trop lent, comparé aux temps de convergence réalisés avec des mesures directes entre les noeuds, et peut même être inacceptable pour certaines applications, qui ont pour but de rapidement identifier les "meilleurs noeuds". Nous soutenons donc, dans cette thèse, l'idée que les systèmes de positionnement Internet, en particulier ceux basés sur les coordonnées, sont une proposition attractive s'ils sont déployés comme un service : chaque noeud fait tourner un système de coordonées au démarrage de son système d'exploitation. Cela permet ainsi au noeud de fournir des estimations de coordonnées précises à la demande des applications et réseaux de couvertures. Un système de coordonnées est alors perc ¸u comme une "infrastructure virtuelle" qui supporte une large variété d'applications et réseaux de couverture. Cela soutient l'idée d'un déploiement des systèmes de coordonnées en tant que service à grande échelle.

C.1.1 Motivations, Problématiques et Contributions

Du fait de l'utilisation de plus en plus répandue des réseaux Pair à Pair et de recouvrement, se basant sur les systèmes à base de coordonnées, on peut aisément imaginer la propagation de vers et autres programmes malicieux dont le but est d'attaquer ces systèmes. En particulier, il est interéssant de noter qu'un système fournissant un service à large échelle, serait aussi une principale cible pour les pirates informatique, puisque sa perturbation mènerait au disfonctionnement ou à l'effondrement de plusieurs applications.

Le fait que les systèmes de coordonnées actuels supposent que les noeuds évoluant dans le système coopèrent entièrement et honnêtement les uns avec les autres, et que cela peut aussi les rendre vulnérables aux attaques, a été l'une de nos motivations premières pour aborder le problème de sécurité dans ce type de systèmes. En particulier, les attaques internes lancées par des noeuds (potentiellement en collusion) infiltrant le système, pouvent s'avérer très dangereuses.

Notre première contribution a été donc d'étudier à quel point ce danger est réel pour les systèmes de coordonnées. Nous avons ainsi identifié trois types d'attaques potentielles contre les systèmes de positionnement. Spécifiquement, nous avons étudié comment ces attaques mènent à des imprécisions dans les prédictions de distances. Nous avons montré qu'il est assez facile de réaliser une attaque de déni de service (DoS), en fournissant des coordonnées biaisées ou en retardant les mesures lancées par les noeuds voisins. Nous avons aussi analysé des moyens simples permettant à des noeuds malicieux de prendre le contrôle du système, puisqu'ils sont capables d'imposer à d'autres noeuds honnêtes, des positions dans le réseau, sans pour autant être détectés. Enfin, nous avons étudié la manière dont une conspiration d'attaquants est réalisée, et combien elle affecte ce genre de systèmes. L' efficacité de ces attaques contre leurs systèmes cibles, a été démontrée à travers des simulations approfondies de deux systèmes représentatifs : Vivaldi et NPS. Un de nos principaux résultats a été que les systèmes plus grands sont plus robustes que ceux impliquant un petit nombre de noeuds. L' observation dans [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] et [START_REF] Ng | A Network Positioning System for the Internet[END_REF], qui stipule que les systèmes plus larges sont plus précis et le fait que ces mêmes systèmes à grande population convergent moins rapidement au démarrage, consolide donc encore plus le fait que ces systèmes soit construits comme une infrastructure virtuelle offrant un service de large échelle. Le paradoxe est bien évidemment qu'un service étendu, supportant plusieurs applications, attire toujours plus d'attaquants. Nos résultats Annex ont aussi montré qu'il y a un compromis, intrinsèque au système, entre précision et vulnérabilité. En effet, nous avons montré que plus le système est précis, plus il est vulnérable pour la même proportion d'attaquants dans le système.

Nous avons aussi montré que les systèmes de coordonnées à infrastructures fixes, sont, sous des stratégies d'attaques bien choisies, aussi vulnérables que les systèmes basés sur le paradigme pair-à-pair. Nous démontrons finalement, que les mécanismes de sécurité proposés jusque là pour spécifiquement défendre certains systèmes contre les noeuds malicieux, sont encore primitifs, et ne peuvent absolument pas protéger le dit système contre tous les types d'attaques.

Ainsi, guidés par notre compréhension des mécanismes d'attaques et de leurs conséquences sur les systèmes des coordonnées, nous nous sommes, par la suite, posés la question : Comment sécuriser le processus de positionnement dans les systèmes à base de coordonnées? Notre contribution majeure a été donc tout naturellement de proposer un protocole de détection et de sécurisation des systèmes de positionnement à base de coordonnées. En constatant qu'en l'absence de noeuds malicieux, les coordonnées d'un noeud dépendent de la combinaison des conditions réseau et de la spécificité du processus de calcul des coordonnées lui-même (exemple : quel type de protocole est utilisé, quel est le nombre de dimensions de l'espace géométrique choisi, etc), nous avons introduit le concept de noeuds experts (Surveyors). Les noeuds experts forment un groupe de noeuds de confiance (honnêtes), dispersés dans le réseau, qui se positionnent en utilisant exlusivement d'autres noeuds experts. En même temps, ces noeuds aident les autres noeuds 'normaux' pour leur positionnement. Cette stratégie permet ainsi aux noeuds experts d'apprendre l'évolution naturelle de l'espace de coordonnées, en observant l'évolution de leurs propres coordonnées, en l'absence d'activité malicieuse. L'idée est que les noeuds experts partagent une représentation du comportement normal dans le système avec les autres noeuds afin de leur permettre de détecter et de filtrer les comportement anormaux.

Nous affirmons et vérifions que, en absence d'activité malicieuse, les coordonées d'un noeud peuvent être vu comme un processus stochastique à dépendances linéaires, dont l'évolution pourrait être traquée par un filtre de Kalman [4]. Chaque noeud expert calcule et calibre les paramètres d'un modèle linéaire, charactérisant l'évolution des ajustements de ses coordonnées, et partage les paramètres de ce modèle avec d'autres noeuds. Ceux-ci utilisent donc ces paramètres, pour faire tourner leurs propres filtres de Kalman. La sortie des filtres, en l'occurence le processus d'innovation, est utilisée pour comparer les ajustements de coordonnées tels qu'observés avec ceux prédits par le filtre de Kalman. Ainsi on considère comme suspect, les étapes d'ajustements de coordonnées, où la différence serait trop élevée. Une combinaison de simulations et expérimentations PlanetLab ont été utilisées pour démontrer la validité, la généralité et l'efficacité de l'approche proposée pour chacun des systèmes Vivaldi et NPS.

Nous nous sommes par la suite intéressés au problème de sécurité de la phase d'estimation des distances dans de tels systèmes. En particulier, le problème de la validité des coordonnées Internet telles qu' annoncées par les noeuds d'un système de coordonnées durant la phase d'estimation des distances. En effet, certains noeuds peuvent délibérément mentir quant à la valeur exacte de leurs coordonnées afin de lancer diverses attaques contre les applications et les réseaux de couverture.

La méthode proposée se divise en deux étapes : 1)établir l'exactitude des coordonnées annoncées en utilisant l'infrastructure des noeuds experts et la méthode de détection des noeuds malicieux, et 2) délivrer un certificat à validité limitée pour chaque coordonnée vérifiée. Les périodes de validité sont calculées à partir d'une analyse des temps d'inter-changement observés par les noeuds experts. En faisant cela, chaque noeud expert, peut estimer le temps jusqu'au prochain changement de coordonnées, et ainsi, peut limiter le temps de validité du certificat qu'il délivrerait aux noeuds normaux. Notre méthode est illustrée en utilisant une trace recueillie à partir d'un système Vivaldi déployé sur PlanetLab, où les distributions de temps d'interchangements suivent des distributions longue traine (distribution lognormale dans la plupart des cas, et distribution Weilbull sinon).

C.1.2 L'organisation de la thèse

Nous commenc ¸ons cette dissertation en faisant, dans le Chapitre 2, un tour d'horizon des systèmes de positionnement de l'Internet, existant dans la littérature, ainsi que de leurs exploitations potentielles dans diverses applications. Nous décrirons notamment notre proposition de réseau multipoint se basant sur un processus de localisation, afin de permettre le passage à l'èchelle [START_REF] Kaafar | A Scalable Overlay Scheme for Application-layer Multicast[END_REF][START_REF] Kaafar | A Locating-First Approach for Scalable Overlay Multicast[END_REF]. Dans ce chapitre, nous nous concentrons néanmoins sur la description des différents systèmes à base de coordonnées existants, ainsi que sur leurs mécanismes de sécurité.

Dans une deuxième étape, nous identifions dans le Chapitre 3 diverses attaques contre les systèmes de positionnenement à base de coordonnées, et montrons l'impact que peuvent avoir de telles attaques sur les performances de ces systèmes [START_REF] Kaafar | Real attacks on virtual networks: Vivaldi out of tune[END_REF][START_REF] Kaafar | Virtual Networks under Attack: Disrupting Internet Coordinate Systems[END_REF].

Annex

Nous avons par la suite proposé une méthode générale pour la détection des comportements malicieux au sein des systèmes de positionnement durant la phase de calcul des cordonnées.

Nous montrons en premier lieu, dans le Chapitre 4, que la dynamique d'un noeud, dans un système de coordonnées sain, exempt de comportements anormaux ou malhonnêtes, peut être modélisée par un modèle d'états linéaires, et traquée par un filtre de Kalman. De plus, les paramètres d'un filtre calibré au niveau d'un noeud donné, peuvent être utilisé pour modéliser et prédire le comportement dynamique d'un autre noeud, tant que ces deux noeuds sont proches l'un de l'autre dans le réseau.

Cela a entraîné la proposition d'une infrastructure de noeuds, appelés "noeuds experts" : des noeuds de confiance, se positionnant dans l'espace des coordonnées, en utilisant exclusivement d'autres noeuds experts. Ils sont ainsi immunisés contre des comportements malicieux dans le système. Pendant le calcul de leurs propres coordonnées, les autres noeuds peuvent ainsi utiliser les paramètres du filtre d'un noeud expert proche, comme étant une représentation d'un comportement normal, non assujetti à un comportement malicieux, pour détecter et filtrer toute activité malicieuse ou anormale. Une combinaison de simulations et d'expérimentations PlanetLab a été utilisée pour démontrer la validité, la généralité, et l'efficacité de l'approche proposée pour chacun des deux systèmes Vivaldi et NPS [START_REF] Kaafar | Securing Internet Coordinate Embedding Systems[END_REF].

Dans le chapitre 5, nous sécurisons la phase d'estimation des distances dans les systèmes de coordonnées. La méthode proposée se divise en deux étapes : 1)établir l'exactitude des coordonnées annoncées en utilisant l'infrastructure des noeuds experts et la méthode de détection des noeuds malicieux, et 2) délivrer un certificat à validité limitée pour chaque coordonnée vérifiée. Les périodes de validité sont calculées à partir d'une analyse des temps d'inter-changement observés par les noeuds experts. En faisant cela, chaque noeud expert, peut estimer le temps jusqu'au prochain changement de coordonnées, et ainsi, peut limiter le temps de validité du certificat qu'il délivrerait aux noeuds normaux. Notre méthode est illustrée par une trace recueillie à partir d'un système Vivaldi déployé sur PlanetLab, où les distributions de temps d'inter-changements suivent des distributions longue traine (distribution log-normale dans la plupart des cas, et distribution Weilbull sinon). Nous montrons l'efficacité de notre méthode en mesurant l'impact de plusieurs attaques sur les estimations de distance, expérimentées sur PlanetLab.

C.2 Chapitre 2: Une vue d'ensemble des systèmes de positionnement Internet

Dans ce chapitre, nous présentons une vue d'ensemble des différentes propositions dans le domaine des systèmes de positionnement Internet. Nous commenc ¸ons par décrire quelques travaux destinés à fournir une estimation de la localisation et de la proximité dans le réseau. Ces systèmes ne reposent pas cependant sur les coordonnées virtuelles. Nous les appelerons "Services d'estimation de proximité par mesures directes". Nous nous concentrons par la suite sur les systèmes à base de coordonnées, que nous classifions en deux classes principales: Les systèmes basés sur les balises (landmarks), et les systèmes distribués.

En particulier, nous étudierons les systèmes munis de mécanismes de sécurité déstinés à filtrer les noeuds malicieux. Nous montrerons cependant dans la suite de cette dissertation, que ces mécanismes sont encore primitifs, et ne peuvent en aucun cas défendre le système contre tous les types d'attaques.

C.2.1 Services d'estimation de proximité par mesures directes

Plusieurs approches dans la littérature fournissent des estimations de distances ou de proximité réseau en utilisant des mesures directes entre les paires de noeuds. Dans cette section, nous présentons quelques uns de ces systèmes les plus connus. Nous nous intéressons en premier lieu aux approches de géolocalisation, qui s'inscrivent dans une tentative de fournir la localisation géographique des noeuds du réseau, plutôt que leurs positions Internet. Nous décrivons en outre l'approche "Constraint-Based Geolocation" et le système IP2Geo. Puis, nous nous intéressons à l'approche de classement de mesures vers les balises ("Binning"), et à une des applications utilisant cette approche (CAN). Nous présentons brièvement comment le réseau de couverture CAN est construit en utilisant le schéma Binning. Enfin, nous exposons les approches à base de "traceroute" et l'approche Meridian, et nous nous attardons sur une des applications d'estimation de la localisation que nous avons proposé, en l'occurence LCC [START_REF] Kaafar | A Locating-First Approach for Scalable Overlay Multicast[END_REF][START_REF] Kaafar | A Scalable Overlay Scheme for Application-layer Multicast[END_REF].

C.2.2 Systèmes de coordonnées à base de Balises Fixes

Ces systèmes incorporent une composante centrale (un ensemble d'entités balises), dont les noeuds se servent pour calculer leurs coordonnées en fonction de mesures vers Annex ces entités balises. Le concept de positionnement par rapport à des entités balises a été introduit dans GNP (Global Network Positioning). Dans ce genre de systèmes, les coordonnées des balises sont en premier lieu calculées en minimisant l'erreur entre les distances mesurées et les distances estimées entre les noeuds balises. De la même manière, un noeud ordinaire dérive ses coordonnées en minimisant l'erreur entre les distances mesurées et les distances estimées vers les noeuds balises. Plusieurs approches ont par la suite repris le concept des balises, et ont pour vocation de mieux passer à l'échelle (Exemple : Lighthouse et l'approche de balises virtuelles). Nous nous intéressons plus particulièrement au système NPS.

le système NPS

Ce système [START_REF] Ng | A Network Positioning System for the Internet[END_REF] étend le système GNP à un système de coordonnées hiérarchique, où les noeuds peuvent servir comme balises (appelés points référence) pour d'autres noeuds. Le but principal est de pallier les problèmes de failles des balises centralisées et fixes, notamment lorsque ces entités deviennent des goulots d'étranglement dans le réseau. La différence majeure par rapport à GNP est que n'importe quel noeud qui s'est bien positionné dans le réseau peut être choisi comme un point référence par un serveur pour d'autres noeuds. Cependant, pour assurer une cohérence dans le système, NPS impose un positionnement hiérarchique entre les noeuds. Étant donné un ensemble de noeuds, NPS les partitionne dans différents niveaux. Un ensemble de 20 balises fixes sont placées dans le niveau 0, la couche supérieure du système, et qui définit la base de l'espace géométrique choisi. Chaque noeud dans un niveau L i , choisit au hasard quelques noeuds dans le niveau L i-1 comme ses points référence. L'erreur relative de la prédiction de distance entre une paire de noeuds est définie comme :

erreur relative = |reelle -virtuelle| min(reelle, virtuelle)
Nous nous intéressons plus particulièrement au système de sécurité inclus dans NPS, qui vise à atténuer les attaques de noeuds malicieux. En effet, les noeuds peuvent mentir sur leurs positions et influencer les mesures effectuées. L'idée principale est d'éliminier le point référence s'il mène à une erreur relative trop élevée par rapport aux autres points référence. Dans cette thèse, nous considèrerons NPS, comme le système représentatif des systèmes de coordonnées à base de balises.

C.2.3 Les Systèmes de coordonnées décentralisés

Cette classe de systèmes étend le concept de positionnement par coordonnées, en généralisant le rôle des balises à tous les noeuds du système, ou en éliminant l'infrastructure des balises. Ces systèmes peuvent être alors perc ¸us comme des systèmes de positionnement pair-à-pair. Nous introduisons en premier lieu le système PIC (Practical Internet Coordinates) où tous les noeuds du système peuvent jouer le rôle de balises pour les autres. Le système de sécurité proposé par PIC, se base sur l'inégalité triangulaire afin de détecter les noeuds malicieux, qui d'après PIC, sont plus suscpetibles de violer cette inégalitée. Dans [START_REF] Costa | Practical Internet coordinates for distance estimation[END_REF], les auteurs montrent que ce test de sécurité peut pallier les attaques d'intensité allant jusquá 20% de noeuds malicieux dans le système. Cependant, [START_REF] Lua | On the accuracy of Embeddings for Internet Coordinate Systems[END_REF] et [START_REF] Zheng | Internet Routing Policies and Round-Trip Times[END_REF] ont montré que les RTTs dans le réseau violent régulièrement et couramment les inégalités triangulaires. Un système de sécurité basé sur le fait que l'inégalité triangulaire est persistante, pourrait mener à une dégradation des performances du système de coordonnées, notamment, lors de l'inexistence de noeuds malicieux.

Nous nous focalisons dans ce chapitre sur le système Vivaldi, et nous le considérerons dans cette thèse, représentatif des Systèmes de coordonnées décentralisés.

Vivaldi

Vivaldi [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF] est un système de coordonnées complètement décentralisé. Il est basé sur une simulation de ressorts, où la position du noeud correspond à celle de l'extrémité d'un ressort qui minimiserait l'énergie potentielle des ressorts, et donc minimiserait l'erreur de positionnement. Un noeud se joignant au système, calcule ses coordonnées en collectant des informations de positions et de mesures de délai à partir de quelques autres noeuds. Spécifiquement, Vivaldi place un ressort entre chaque paire de noeuds (i, j) dans le système, avec une longueur "de repos" correspondant à la mesure RTT entre ces deux noeuds. La longueur réelle du ressort est considérée comme étant l'estimation de distance entre les deux positions des noeuds. L'énergie potentielle d'un tel ressort est proportionnelle au carrée de déplacement par rapport à sa longueur "de repos". La somme de ces erreurs à travers tous les ressorts est la fonction d'erreur que Vivaldi tente de minimiser. Une procédure identique tourne sur tous les noeuds Vivaldi. Celle-là est basée sur des échantillons récoltés par les noeuds qui fournissent les informations pour leur positionnement. Un échantillon, utilisé par un noeud i est ainsi constitué de la mesure vers un noeud j, de la coordonnée du même noeud j, ainsi Annex que de l'erreur locale reportée par j. L'algorithme traîte les noeuds à haute erreur, en assignant des poids à chaque échantillon collecté. L'erreur relative de cet échantillon, e s , est alors calculée comme suit :

e s = | x j -x i -RTT mesure | / RTT mesure
Le noeud calcule alors le poids de cet échantillon comme étant w = e i /(e i + e j ), où e i est l'erreur actuelle (locale) du noeud i. Ce poids est utilisé en fait pour calculer un déplacement adaptatif, δ définissant la fraction de mouvement que le noeud est autorisé à faire en direction du noeud auquel il se mesure : δ = C c × w, où C c est une constante < 1. Le noeud met alors à jour sa coordonnée locale comme suit :

x i = x i + δ • (RTT mesure -x i -x j ) • u(x i -x j )
où u(x ix j ) est un vecteur unitaire donnant la direction de déplacement de i. Enfin, le noeud met à jour son erreur locale comme étant e i = e s × w + e i × (1w).

C.2.4 Discussion

Qu'ils soient basés sur des balises fixes, ou qu'ils soient décentralisés, la plupart des systèmes de positionnement actuels réalisent de bonne performances en termes de précision de positionnement, de stabilité et de passage à l'échelle. Cependant, il faut aussi noter que cela est permis aux dépends de temps de convergence longs, allant de quelques secondes à plusieurs minutes [START_REF] Ledlie | Network Coordinates in the Wild[END_REF]. Cela est très loin des performances en termes de rapidité de traitement des systèmes de mesures directes entre des paires de noeuds, et ceci est de surcroît non accpetable pour les applications tenant compte de la topologie et qui visent à déterminer les "meilleurs noeuds", le plus rapidement possible.

Les systèmes de positionnement à base de coordonnées sont une proposition attractive s'ils sont déployés comme un service : chaque noeud pourra alors faire tourner un système de coordonées au démarrage du système d'exploitation. Cela pourra ainsi permettre au noeud de fournir des estimations de distance à la demande, aux applications et réseaux de recouvrement. Un système de coordonnées est ainsi vu comme une "infrastructure virtuelle" qui supporte une large variété d'applications et réseaux de couverture.

Cela dit, un système fournissant un service à large échelle, serait aussi une principale cible pour les pirates informatique, puisque sa perturbation pourrait mener au disfonctionnement ou l'effondrement de plusieurs applications à la fois. Le fait que les systèmes de coordonnées actuels supposent que les noeuds évoluant dans le système coopèrent entièrement et honnêtement les uns avec les autres, et que cela peut aussi les rendre vulnérables aux attaques, a été l'une de nos motivations premières pour addresser le problème de sécurité dans ce type de systèmes. En particulier, les attaques internes lancées par des noeuds (potentiellement en collusion) infiltrant le système, pourrait s'avérer très dangereuses. De ce fait, sécuriser la base de la prédiction de distance pour plusieurs applications serait plus critique, que de détailler les artefacts d'une quelconque sécurité d'une application particulière. Dans le chapitre suivant, nous commencerons ainsi par montrer qu'il est assez simple de s'attaquer au service de coordonnées, et nous détaillerons les principaux moyens pour y arriver, ainsi que leurs impacts sur les systèmes à base de coordonnées.

C.3 Chapitre 3: Les Attaques contre les systèmes de coordonnées et leurs impacts

Ce chapitre a pour principal but d'identifier les différentes attaques contre les systèmes de coordonnées et de montrer leur efficacité à travers leur expérimentation sur deux systèmes représentatifs : Vivaldi et NPS. Notre étude basée sur des simulations montre ainsi qu'il est assez simple de déstabiliser ces systèmes et cela même si quelques mécanismes de sécurité existent. En particulier, nous quantifions les effets de stratégies d'attaques qui visent à (i) introduire du désordre dans le système, (ii) tromper des noeuds honnêtes afin de leur imposer des coordonnées loin de leur positions correctes et (iii) isoler certains noeuds cibles à travers des collusions de noeuds malicieux.

C.3.1 Menaces et classification des attaques

Nous considérons des noeuds malicieux ayant accès aux mêmes données que les utilisateurs légitimes. Cela veut dire que tous les participants ne sont pas forcément des entités de confiance, ou alors que certains noeuds malicieux ont pu contourner un quelconque mécanisme d'authentification. Les noeuds malicieux sont capables d'envoyer des informations erronées quand les autres noeuds mesurent leurs distances vers eux, ou alors d'envoyer des informations manipulées en recevant des requêtes de position-nement. Ils peuvent aussi affecter certaines métriques observées par leur cible. Les classes principales d'attaques sur les systèmes de coordonnées sont :

1. Le Désordre: le but principale d'une telle attaque est de créer le chaos sous une forme d'une attaque de déni de service. Cela entraîne des erreurs élevées dans le positionnement des noeuds, ou une non-convergence de l'algorithme de calcul des coordonnées. L'attaque consiste simplement à maximiser l'erreur relative des autres noeuds dans le système, passivement en choisissant de ne pas coopérer ou en falsifiant les coordonnées, ou alors activement en retardant les mesures effectuées par les noeuds honnêtes.

Évaluation des performances

Nous avons utilisé l'erreur relative (comme définie pour chaque algorithme) comme indicateur principal de performance. Comme nous nous concentrons surtout sur l'impact des noeuds malicieux sur tout le système, nous avons aussi introduit le ratio d'erreur relative comme étant l'erreur relative mesurée en présence de noeuds malicieux normalisée à la performance du système sans tricheurs. Ceci est utilisé comme le meilleur des scénarios. Une valeur au dessus de 1 indique manifestement une dégradation dans la précision du système.

Nos simulations ont montré que les systèmes de coordonnées, dćentralisées ou à base de balises, peuvent être déstabilisés, bien que nous avons aussi constaté que les systèmes plus larges sont plus résistants aux attaques. Nos résultats ont aussi montré qu'il y a un compromis intrinsèque au système entre précision et vulnérabilité. En effet, nous avons montré, en variant les dimensions utilisées par les systèmes, que plus le système est précis, plus il est vulnérable pour la même proportion d'attaquants dans le système.

Nous avons aussi pu observer que, quand les attaques tournent à plein régime, les performances des systèmes de coordonnées (ainsi que les applications qui les supportent), peuvent facilement se dégrader au delà de celle d'un système qui utiliseraient des coordonnées aléatoires. Enfin, nous avons montré que les conséquences des attaques durent très longtemps à cause des résidus d'erreurs se propageant et infectant tous les noeuds dans le système.

C.4 Chapitre 4: Sécurisation de la phase de calcul de coordonnées

Dans ce chapitre, nous nous fixons comme objectif de proposer une méthode générale et efficace pour sécuriser les systèmes de coordonnées lors de leur phase de calcul des coordonnées.

Nous montrons ainsi en premier lieu, que la dynamique d'un noeud, dans un système de coordonnées exempt de comportement malicieux ou anormal, peut être modélisée par un modèle linéaire et pistée par un filtre de Kalman.

C.4.1 Modélisation du processus de calcul des coordonnées

Le but des systèmes de coordonnées, sans tenir compte de la manière de calcul, ni de l'aspect dimensions de l'espace géométrique utilisé, est d'attribuer des coordonnées à un noeud dans le système de manière, à ce qu'à tout moment, on puisse assimiler la distance géométrique entre deux coordonnées à la distance réseau réelle, mesurée en RTT entre deux noeuds. La mesure RTT en revanche, manifestement, dépend de l'état du réseau (exemple : de la charge du trafic, de l'état des files d'attentes dans les routeurs, etc.), mais aussi de l'état des systèmes d'exploitation des noeuds eux-même générant du bruit dans les mesures. Ainsi la valeur exacte de RTT varie continuellement.

Cela se répercute sur les calculs de coordonnées effectuées par les systèmes de positionnement, en dehors du fait qu'ils soient décentralisés ou basés sur des balises fixes. À chaque étape de calcul des coordonnées, la précision de ce calcul est déterminée en observant la déviation entre le RTT mesuré vers un noeud correspondant et celui estimé dans le système de coordonnée. Plus précisemment, cette précision est définie comme étant l'erreur relative mesurée

D n = |||X n i -X n j ||-RTT n ij | RTT n ij
. Le but de n'importe quel système de coordonnées est de minimiser un indicateur de coût (l'erreur moyenne quadratique) qui capture l'erreur relative mesurée.

Les erreurs relatives mesurées sont sujettes à des fluctuations des RTTs pour les raisons mentionnées ci-dessus, en particulier, les congestions transitoires dans le réseau et les problèmes d'ordonnancement dans les systèmes d'exploitation. Afin d'isoler l'impact de ces fluctuations de RTT sur la détection d'anomalie, nous introduisons ∆ n , l'erreur relative nominale, que notre noeud pourrait obtenir si à l'étape n de ses calculs de coordonnées les RTTs ne fluctuent pas. Une anomalie devient alors une simple observation de larges déviations de D n , l'erreur relative mesurée, de sa valeur nominale ∆ n .

Parce que plusieurs sources contribuent à la déviation de D n de sa valeur nominale (erreur des mesures RTT, fluctuations des RTT, erreurs dans les coordonnées des noeuds), il est raisonnable de supposer que les deux valeurs sont fonctions l'une de l'autre comme suit :

D n = ∆ n + U n (C.1)
où U n est une variable gaussienne à moyenne 0 et à variance v U .

Nous nous focalisons maintenant sur la dynamique du système dans son régime nominal lorsque les RTTs ne fluctuent pas. Nous définissons ainsi l'erreur du système W n qui représente l'impact des autres noeuds dans le système sur le positionnement du noeud considéré à l'étape n. Puisque W n résulte de plusieurs sources contributrices, il est aussi raisonnable de supposer que c'est un processus gaussien (avec une moyenne w et une variance v W ). Comme première approximation, le processus ∆ n peut ainsi être modélisé comme un modèle auto régressif d'ordre 1 :

∆ n+1 = β∆ n + W n .
(C.2) où β est un facteur constant strictement inférieur à 1, afin que l'erreur relative puisse converger vers un régime stationnaire indépendemment des conditions initiales. Les équations C.2 and C.1 définissent alors un modèle linéaire d'évolution de l'erreur relative d'un noeud. Notre objectif est d'obtenir des prédictions de cette erreur relative à partir de ce modèle. De par ses propriétés linéaires, le filtre de Kalman est utilisé dans ce cas pour pister l'évolution de l'erreur relative nominale et pour aussi obtenir une prédiction de cette erreur relative ∆n|n-1 .

En utilisant la méthode EM ("Expectation Maximization method"), nous calibrons le filtre de Kalman afin de déterminer pour chaque noeud dans un système normal, les valeurs des paramètres θ = (β, v W , v U , w 0 , p 0 ) utilisés par le filtre.

Cela nous a mené à la proposition d'une infrastructure de noeuds experts : ceux-ci sont des noeuds de confiance, se positionnant dans l'espace des coordonnées, en utilisant exclusivement d'autres noeuds experts. Ils sont ainsi immunisés contre n'importe quel comportement malicieux dans le système. Pendant le calcul de leurs propres coordonnées, les autres noeuds peuvent ainsi utiliser les paramètres du filtre calibré d'un noeud expert non assujetti à un comportement malicieux, pour détecter et filtrer toute activité malicieuse ou anormale.

C.4.2 Validation du modèle

Une combinaison de simulations et d'expérimentations PlanetLab a été utilisée pour démontrer la validité du modèle proposé pour chacun des deux systèmes Vivaldi et NPS. Nous avons ainsi pu montrer en premier lieu la validité de nos hypothèses, en particulier la supposition que le bruit du système W n est un processus gaussien. Ensuite, nous avons montré que les erreurs relatives telles que prédites par le filtre et celles réellement calculées par les noeuds dans le système sont très semblables. Lorsque Annex le modèle a convergé (i.e. la méthode EM a convergé et les variations pour tous les paramètres varient d'une valeur inférieure à 0.02), nous relanc ¸ons le système de coordonnées, et nous observons les erreurs de prédiction comme étant la valeur absolue entre l'erreur prédite par le filtre de Kalman au niveau d'un noeud et l'erreur relative mesurée réelle. Nous observons que les erreurs de prédiction sont la plupart du temps inférieures à 0.02.

Nous avons par la suite vérifié qu'un ensemble de noeuds de confiance déployés au hasard dans le réseau peut être représentatif de l'ensemble des noeuds dans le système. Une des premières questions que nous nous sommes posées était donc de savoir combien de noeuds de confiance (experts) fallait-il déployer pour reprśenter l'évolution des erreurs des autres noeuds. Nous avons ainsi pu montrer, qu'en effet une proportion de moins de 8% de noeuds experts aléatoirement déployés dans le système de coordonnées est suffisante pour pouvoir représenter le comportement du système. Ayant montré que la population de noeuds experts peut représenter le comportement normal de tout le système, la question suivante que nous nous sommes posée était de savoir à quel point le comportement du système pisté par un filtre de Kalman calibré au niveau d'un noeud expert peut représenter le comportement d'un noeud normal. Nous avons observé dans nos simulations et expérimentations PlanetLab que, même si chaque noeud normal trouve au moins un noeud expert dont le filtre de Kalman mène à de très faibles erreurs de prédiction, tous les noeuds experts ne permettent pas en revanche une bonne représentativité pour un noeud normal donné. Le choix des noeuds experts est ainsi primordial pour gagner en représentativité de comportement normal, en performance de prédiction et ainsi en détection de comportements malicieux. Nos expérimentations ont alors montré qu'il existe une forte coorrélation entre les erreurs de prédiction et les RTTs entre le noeud normal et le noeud expert.

En conclusion, durant leur calcul de coordonnées, les noeuds normaux obtiennent les paramètres des filtres des noeuds experts pour pouvoir prédire correctement leurs erreurs relatives, à condition que ces noeuds experts soient positionnés proches d'eux.

C.4.3 Détection des comportements malicieux

Si les noeuds experts sont capables de calculer leurs coordonnées dans un système exempt d'une quelconque activité malicieuse, ils peuvent alors être considérés comme des entités de confiance. Puisque ces noeuds interagissent seulement entre eux mêmes, ils sont donc immunisés contre tout comportement malicieux ou anormal, et observent donc le comportement du système dans des conditions normales. Ainsi, l'idée principale de notre détection est d'utiliser le modèle de comportement normal obtenu par les noeuds auprès des noeuds experts les plus proches pour pouvoir détecter des anomalies dans le système, et ce à chaque étape de calcul des coordonnées.

C.4.4 Évaluation des performances

Nous avons évalué en premier lieu les performances de notre protocole de détection, et nous avons prouvé que les taux de faux positifs de nos tests étaient très bas, alors que les taux de vrais positifs étaient constamment élevés et ce indépendemment des dimensions de l'espace géométrique utilisé. Nous avons par ailleurs, pu démontrer à travers nos simulations et expérimentations PlanetLab, que Vivaldi et NPS se trouvaient muni d'une protection pouvant leur permettre de fonctionner normalement et ce même lorsque un peu plus de 30% de la population était maligne.

C.5 Chapitre 5: Sécurisation de la phase d'estimation des distances

Les systèmes de coordonnées sont principalement déstinés à évaluer les distances entre les noeuds, en se basant simplement sur les coordonnées échangées par les noeuds dans le système. Quelque soit le mécanisme d'échange de ces coordonnées (échanges directs, répertoire WEB, etc.), chaque noeud devrait d'une manière ou d'une autre reporter une valeur de ses coordonnées jusque là calculées. Cela crée une opportunité à des noeuds malicieux pour essayer de tricher quant à leurs coordonnées transmises pour aboutir à des fins malicieuses et à des attaques sur les applications utilisant le système de coordonnées (Déni de service, Isolation, etc.). Ce chapitre traite donc de la véracité des coordonnées transmises par les noeuds, et de la garantie de leur authenticité.

Nous proposons ainsi d'exploiter l'infrastructure de noeuds experts et du protocole de détections de triches proposés dans le chapitre précédent. En particulier, chaque noeud expert mesure sa distance vers un noeud afin de vérifier l'exactitude de ses coordonnées annoncées (en utilisant le test de détection des anomalies en erreurs relatives). Si tous les noeuds experts s'accordent à dire que les coordonnées du noeuds sont valides, on lui accorde alors un certificat, à temps de validité limitée, incluant les coordonnées certifiées.

Un temps de validité pour chaque certificat est nécessaire parce que, le changement des conditions réseau fait en sorte que les coordonnées varient dans le temps. Au changement de ses coordonnées, un noeud honnête cesserait d'utiliser son certificat actuel, et demanderait un certificat pour ses nouvelles coordonnées. En revanche, un noeud malicieux pourrait continuer à utiliser le certificat relatif à ses anciennes coordonnées. Ainsi, un compromis est nécessaire entre passage à l'échelle et validité des certificats. Une de nos contributions dans ce chapitre a été donc d'étudier les temps d'inter-changement (i.e. le temps qui sépare les changements de coordonnées d'un noeud) dans le système Vivaldi déployé sur PlanetLab. Nous avons pu observer que ces temps d'inter-changements suivaient une distribution 'lognormale' pour la plupart des cas, et une distribution Weibull dans certains cas particuliers (à noter que ces deux distributions sont des distributions longue traine).

À travers des expérimentations PlanetLab, nous avons pu montré que cette méthode est très efficace, avec un taux de détection élevé (vrai positifs) et un taux de faux positif très bas. Cette méthode permet aussi un compromis entre passage à l'échelle et sécurité. En effet, les temps de validité des certificats sont très rarement sur estimés, alors qu'ils ne déclenchent pas souvent des re-certifications.

C.6 Chapitre 6: Conclusions et Travaux Futurs

Dans cette dissertation, nous avons pu montrer dans le chapitre 3 que divers types d'attaques pouvaient être lancées contre les systèmes de coordonnées.

Nous avons alors exploré dans une seconde étape, un moyen général et efficace pour sécuriser de tels systèmes. Dans le chapitre 4, nous avons montré que la dynamique d'un noeud, dans un système de coordonné sans activité malicieuse, peut être modélisée par un modèle d'états linéaires, et traquée par un filtre de Kalman. De plus, les paramètres d'un filtre calibré au niveau d'un noeud donné, peuvent être utilisés pour modéliser et prédire le comportement dynamique d'un autre noeud, tant que ces deux noeuds sont proches l'un de l'autre dans le réseau.

Les prédictions effectuées par le filtre au niveau de chaque noeud lui permettent de comparer les erreurs relatives prédites et celles mesurées. Une déviation trop grande entre ces deux valeurs permet au noeud de ne pas considérer la mesure qu'il vient d'effectuer, le munissant ainsi d'un moyen de défense lors du calcul de ses coordonnées. Cependant, même cette sécurité reste insuffisante, lorsqu'on sait que ces systèmes sont surtout utilisés par les applications pour l'estimation des distances entre noeuds.

Dans le chapitre 5, nous avons alors abordé le problème de l'authenticité des coordonnées transmises (ou annoncées) par les noeuds. Nous avons étudié les temps d'inter-changements des coordonnées, et pu observé qu'ils suivaient souvent une distribution lognormale (dans de rares cas une distribution Weibull), et qu'un temps de validité de ces coordonnées pouvait être déterminé par un noeud expert. Celui-ci vérifie l'exactitude de la coordonnée annoncée par le noeud normal et lui délivre un certificat à temps de validité égale à la validité estimée de sa coordonnée actuelle.

Les résultats obtenus dans cette thèse, notamment pour le protocole de détection des noeuds malicieux lors du calcul des coordonnées, se sont basés sur un déploiement aléatoire des noeuds experts. Bien que la représentativité de ces derniers augmente avec un déploiement plus stratégique, ces résultats ont montré l'efficacité de notre protocole de sécurisation des systèmes à base de coordonnées. On pourrait envisager d'autre stratégies de déploiment plus optimal des noeuds experts afin d'aboutir à une meilleure représentativité à large échelle.

Considérer des attaques directes sur l'infrastructure des noeuds experts est aussi une de nos directions furtures. En effet, au moins deux attaques peuvent être envisagées contre les noeuds experts. La première serait tout simplement un déni de service par innondation des des noeuds experts. La seconde serait de s'attaquer uniquement aux liens entre certains noeuds experts, rendant ainsi les filtres au niveau de ces noeuds mal-calibrés. Une calibration biaisée est équivalente à une non représentativité des noeuds experts, résultant en positionnement incorrect ou même en un taux élevé de faux positifs dans notre protocole de détection.

Étudier l'impact de telles attaques et intégrer des méchanismes de défense contre des attaquants ciblant les noeuds experts, est aussi un de nos travaux futurs.

Nous avons aussi montré que notre méthode pour la validation des coordonnées annoncées est efficace contre des attaques sophistiquées. Cependant, il est à noter qu'un noeud peut connaître à quel moment son prochain calcul de coordonnées va avoir lieu, et ainsi quand est ce que ses coordonnées vont probablement changer. Un noeud malicieux peut chercher à exploiter cette connaissance pour obtenir un certificat (pour ses coordonnées actuelles) juste avant l'instant de son nouveau positionnement, et cela lui permettrait d'avoir un certificat valide pour des coordonnées anciennes. Afin de pallier ce problème, on peut envisager que les noeuds experts effectuent des vérifications périodiques aléatoires des coordonnées certifiées. Si ces derniers échouent le test de vérification, le noeud concerné pourrait être pénalisé, pour avoir utilisé un certi-ficat périmé. Nous planifions de lancer de nouvelles expérimentations intégrant ces mécanismes pour évaluer de nouveau l'efficacité de notre méthode de certification.

Nous nous fixons comme objectif final de fournir un service sécurisé pratique de coordonnées. En dehors de la précision des systèmes de coordonnées, nous pensons que sécuriser de tels systèmes, est une condition nécessaire à leur déploiement. En effet, sans la sécurité de chacune des phases de calcul des coordonnées et d'estimation des distances, nous avons pu montrer que des attaques simples pouvaient réduire ces systèmes à une utilité futile. Nous croyons alors que la résistance aux attaques, que nous proposons dans cette thèse, pourrait agir comme un catlyseur au déploiment massif des services de coordonnées à large échelle.

ABSTRACT

Internet coordinate-based systems allow easy network positioning. In such systems, the basic idea is that if network distances between Internet nodes can be embedded in an appropriate space, unmeasured distances can be estimated using a simple distance computation in that space. Recently, these coordinates-based systems have been shown to be accurate, with very low distance prediction error. However, most, if not all, of current proposals for coordinate systems assume that the nodes partaking in the system cooperate fully and honestly with each other -that is that the information reported by probed nodes is correct -this could also make them quite vulnerable to malicious attacks. In particular, insider attacks executed by (potentially colluding) legitimate users or nodes infiltrating the system could prove very effective.

As the use of overlays and applications relying on coordinates increases, one could imagine the release of worms and other malware, exploiting such cooperation, which could seriously disrupt the operations of these systems and therefore the virtual networks and applications relying on them for distance measurements.

In this thesis, we first identify such attacks, and through a simulation study, we observed their impact on two recently proposed positioning systems, namely Vivaldi and NPS. We experimented with attack strategies, carried out by malicious nodes that provide biased coordinates information and delay measurement probes, and that aim to (i) introduce disorder in the system, (ii) fool honest nodes to move far away from their correct positions and (iii) isolate particular target nodes in the system through collusion. Our findings confirm the susceptibility of the coordinate systems to such attacks.

Our major contribution is therefore a model for malicious behavior detection during coordinates embedding. We first show that the dynamics of a node, in a coordinate system without abnormal or malicious behavior, can be modeled by a Linear State Space model and tracked by a Kalman filter. Then we show, that the obtained model can be generalized in the sense that the parameters of a filter calibrated at a node can be used effectively to model and predict the dynamic behavior at another node, as long as the two nodes are not too far apart in the network. This leads to the proposal of a Surveyor infrastructure: Surveyor nodes are trusted, honest nodes that use each other exclusively to position themselves in the coordinate space, and are therefore immune to malicious behavior in the system. During their own coordinate embedding, other nodes can then use the filter parameters of a nearby Surveyor as a representation of normal, clean system behavior to detect and filter out abnormal or malicious activity. A combination of simulations and PlanetLab experiments are used to demonstrate the validity, generality, and effectiveness of the proposed approach for both Vivaldi and NPS.

Finally, we address the issue of asserting the accuracy of Internet coordinates advertised by nodes of Internet coordinate systems during distance estimations. Indeed, some nodes may even lie deliberately about their coordinates to mount various attacks against applications and overlays.

Our proposed method consists in two steps: 1) establish the correctness of a node's claimed coordinate by using the Surveyor infrastructure and malicious embedding neighbor detection; and 2) issue a time limited validity certificate for each verified coordinate. Validity periods are computed based on an analysis of coordinate inter-shift times observed by Surveyors. By doing this, each surveyor can estimate the time until the next shift and thus, can limit the validity of the certificate it issues to regular nodes for their calculated coordinates. Our method is illustrated using a trace collected from a Vivaldi system deployed on PlanetLab, where intershift times are shown to follow long-tail distribution (log-normal distribution in most cases, or Weibull distribution otherwise). We show the effectiveness of our method by measuring the impact of a variety of attacks, experimented on PlanetLab, on distance estimates.

RÉSUMÉ

Les systèmes Internet à base de coordonnées permettent un positionnement pratique des noeuds dans le réseau. Dans ce type de systèmes, l'idée principale est que si les distances réseau entre différents noeuds Internet peuvent être plongées dans un espace approprié, alors les distances non mesurées peuvent être estimées en utilisant une simple opération de calcul de distance géométrique dans cet espace. Récemment, on a pu prouver que ces systèmes à base de coordonnées étaient précis, avec une faible erreur de prédiction. Cependant, ces systèmes se basent souvent sur une coordination entre les noeuds, et font l'hypothèse que les informations reportées par les noeuds sont correctes.

Dans cette thèse, nous avons identifié plusieurs attaques, exploitant cette hypothèse d'honnêteté des noeuds, et pouvant être lancées contre des systèmes de positionnement Internet à base de coordonnées. Nous avons en l'occurrence étudié l'impact qu' avaient de telles attaques sur deux systèmes représentatifs des systèmes de positionnement actuels : NPS et Vivaldi. Nous avons entre autres montré que ces attaques, pouvaient dangereusement mettre en péril le bon fonctionnement de ces systèmes de coordonées, et par la même les applications se basant sur ce système pour les estimations de distances. À travers les simulations de plusieurs attaques, menées par des noeuds malhonnêtes, fournissant des coordonnées biaisées ou retardant les mesures, nous avons expérimenté plusieurs stratégies d'attaques qui ont pour objectifs: (i) d'introduire du désordre dans le système, (ii) de tromper les noeuds honnêtes afin qu'ils se positionnent loin de leurs coordonnées correctes et (iii) d'isoler certains noeuds cibles à travers des collusions. Nos résultas confirment la vulnérabilité de tels systèmes à ces attaques.

Notre contribution majeure a été par la suite de proposer un modèle de détection des comportements malicieux au sein de ces systèmes de positionnement durant le calcul des cordonnées.

Nous avons montré en premier lieu que la dynamique d'un noeud, dans un système de coordonnées, exempt de comportements anormaux ou malhonnêtes, peut être modélisée par un modèle d'états linéaire, et traqué par un filtre de Kalman. De plus, les paramètres d'un filtre calibré au niveau d'un noeud donné, peuvent être utilisés pour modéliser et prédire le comportement dynamique d'un autre noeud, tant que ces deux noeuds sont proches l'un de l'autre dans le réseau. Nous avons dès lors proposé une infrastructure de noeuds experts : des noeuds de confiance, se positionnant dans l'espace des coordonnées, en utilisant exclusivement d'autres noeuds experts. Ils sont alors immunisés contre n'importe quel comportement malicieux dans le système. Pendant le calcul de leurs propres coordonnées, les autres noeuds utilisent les paramètres du filtre d'un noeud expert proche, comme étant une représentation d'un comportement normal, pour détecter et filtrer toute activité malicieuse ou anormale. Une combinaison de simulations et d'expérimentations PlanetLab a été utilisée pour démontrer la validité, la généralité et l'efficacité de l'approche proposée pour chacun des deux systèmes Vivaldi et NPS.

Figure 2 . 1 ,

 21 Figure 2.1, the key idea of such systems is to model the Internet as a geometric space

Figure 2 . 1 :

 21 Figure 2.1: Geometric space model of the Internet

Figure 2 . 2 :

 22 Figure 2.2: Basic network positioning method in a 2-d Euclidean space

Figure 2 . 3 :

 23 Figure 2.3: The hierarchical network positioning architecture of NPS.

Figure 2 . 4 :

 24 Figure 2.4: Triangle inequality with measured and predicted distances in PIC.

  , i) -(d(n, j) + d ′ (i, j)) if d(n, j) + d ′ (i, j) < d(n, i), 0 Otherwise

Figure 3 .Figure 3 . 1 :

 331 Figure 3.1 illustrates the effects of malicious nodes on the coordinate space of Vi-

Figure 3 . 2 :

 32 Figure 3.2: Injection of Disorder Attackers on Vivaldi: average relative error ratio.

Figure 3 . 3 :

 33 Figure 3.3: Injected Disorder attack on Vivaldi: CDF of relative error at simulation tick = 5000

Figure 3 . 4 :Figure 3 . 5 :

 3435 Figure 3.4: Injected Disorder Attack on Vivaldi: Impact of space dimensions

Figure 3 . 6 :Figure 3 . 7 :

 3637 Figure 3.6: Effect of Repulsion attack on Vivaldi with 1740 nodes

Figure 3 . 8 :

 38 Figure 3.8: Injected Repulsion Attack on Vivaldi: impact of space dimensions.

Figure 3 . 9 :

 39 Figure 3.9: Injected Repulsion Attack on subsets of target nodes.

Figure 3 .Figure 3 . 11 :

 3311 Figure 3.11: Effect of Colluding Isolation attack on Vivaldi with 1740 nodes

Figure 3 . 12 :

 312 Figure 3.12: Colluding isolation Attack on Vivaldi: average relative error ratio

Figure 3 . 14 :

 314 Figure 3.14: Colluding Isolation Attack on Vivaldi: CDF of relative errors.

Figure 3 . 15 :

 315 Figure 3.15: Combining attacks on Vivaldi (Disorder, Repulsion and Colluding Isolation attack strategy 1): impact on convergence.

Figure 3 . 16 :

 316 Figure 3.16: Combined attacks on Vivaldi: effect of system size.

Figure 3 . 17 :

 317 Figure 3.17: Injection in NPS of Independent Disorder attackers (No prevention): average relative error.

Figure 3 . 18 :

 318 Figure 3.18: Injection in NPS of Independent Disorder attackers: CDF.

Figure 3 . 19 :

 319 Figure 3.19: Injection of Independent Disorder attackers: Impact of dimensionality.

Figure 3 .

 3 Figure 3.20: Anti-Detection NPS attack

Figure 3 . 21 :

 321 Figure 3.21: Injection in NPS of Anti-detection naive attackers: impact on convergence.

Figure 3 . 22 :

 322 Figure 3.22: Injection in NPS of Anti-detection naive attackers: effect of victims coordinates knowledge.

Figure 3 . 23 :

 323 Figure 3.23: Injection in NPS of Anti-detection naive attackers: effect of victims coordinates knowledge on the ratio of filtered malicious nodes over the overall filtered nodes.

Figure 3 . 24 :

 324 Figure 3.24: Injected Anti-detection Sophisticated attacks on NPS: CDF.

Figure 3 .

 3 Figure 3.25 shows the impact of the attacker's knowledge on the attack. By going

Figure 3 . 26 :

 326 Figure 3.26: Injection of colluding Isolation attack on NPS in scenario 1: CDF of relative errors.

Figure 3 . 27 :

 327 Figure 3.27: Injection of colluding Isolation attack on NPS in scenario 2: CDF of relative errors.

Figure 3 . 28 :

 328 Figure 3.28: Injection of colluding Isolation attack on NPS: Propagation of errors.

Figure 3 .

 3 Figure 3.29: Injection of combined attacks on NPS (Independent disorder, Anti-Detection Sophisticated disorder and colluding isolation attackers): Impact on convergence.

Figure 4 . 1 :

 41 Figure 4.1: Quantile-Quantile plot of 2 innovation processes.

Figure 4 . 2 :

 42 Figure 4.2: Prediction errors (PlanetLab node).

Figure 4 . 3 :

 43 Figure 4.3: CDF of prediction errors.

Figure 4 . 4 ,

 44 obtained by simulations of Vivaldi, indicates that a population of Surveyors of about 8% of the overall population is closely representative of this overall population (because the CDF for these populations in the figure are similar).

Figure 4 . 4 :

 44 Figure 4.4: Impact of Surveyor population size on repretentativeness.

  normal nodes: King Data Set 95th percentile of normal nodes: PlanetLab 95th percentile of Surveyor nodes: King Data Set 95th percentile of Surveyor nodes: PlanetLab

Figure 4 . 5 :

 45 Figure 4.5: Representativeness with 8% Surveyor nodes.

Figure 4 .Figure 4 . 6 :

 446 Figure 4.7 plots the prediction accuracy (measured as an average prediction error) against the distance (measured as an RTT) between a node and the corresponding Surveyor, as observed during the PlanetLab experiment. It is clear that better locality

Figure 4 . 7 :

 47 Figure 4.7: Correlation between 'Node-Surveyor' RTTs and estimation accuracy (PlanetLab).

Figure 4 . 8 :

 48 Figure 4.8: Maximum prediction errors with closest Surveyor.

Figure 4 . 9 :

 49 Figure 4.9: ROC curves. Each tick on the plots corresponds to a different value of the test's significance level (α).

Figure 4 . 10 :

 410 Figure 4.10: True positive test fraction.

Figure

  Figure 4.10 shows the true positive test fraction of the detection method for various test significance levels under various intensity of attacks. We see that the proportion of positive tests that are true positives is constantly high, regardless of the significance level chosen, for moderate to quite significant proportions of malicious nodes in the population (up to 20% of malicious nodes). However, thereafter the proportion of correct positive tests starts to decrease, although the rate of decrease is inversely proportional to the significance level used. This is because a higher significance level produces more positive tests, catching most malicious embedding steps, and so many more false positives are needed to make up a significant proportion of these. In light of this, a significance level of 5% offers a good compromise. Figures 4.11 and 4.12 show the false positive and negative rates respectively. As expected, a higher significance level results in a more aggressive test that incorrectly classifies a larger portion of normal embedding steps (figure4.11) as malicious, while a more lenient test (lower significance level) wrongly reports a higher proportion of malicious embedding steps as normal (figure 4.12).Incorrect test results do have a negative impact on the embedding system: false positives artificially reduce the size of available normal nodes that can be used for

Figure 4 . 11 :

 411 Figure 4.11: False Positive Rate.

Figure 4 . 12 :

 412 Figure 4.12: False negative rate.

Figure 4 . 13 :

 413 Figure 4.13: Distribution of measured relative errors.

Figure 4 .

 4 Figure 4.14: ROC curves.

Figure 4 . 15 :

 415 Figure 4.15: Distribution of measured relative errors.

Figure 4 .

 4 Figure 4.15 shows the cumulative distribution function of relative errors in the sys-

Figure 4 . 16 :

 416 Figure 4.16: Distribution of measured relative errors.

Figure 5 .

 5 Figure 5.1 shows a typical evolution of the coordinates of a Vivaldi node. Each sub-figure depicts the evolution of one coordinate component along the three axis.

Figure 5 . 1 :

 51 Figure 5.1: Typical Variations of a node's coordinate in the Vivaldi System.

Figure 5 . 2 :

 52 Figure 5.2: Density plots and CDF of a typical inter-shift distribution (Node 181).

Figure 5 . 3 :

 53 Figure 5.3: Correlation between 'Nodes-Surveyors' RTTs and the rejection Ratio.

Figure 5 . 4 :

 54 Figure 5.4: Fake Coordinate and Consistent Relative Error

Figure 5 . 5 :

 55 Figure 5.5: Distribution of regular and Surveyor nodes in a 2d space (distances are in ms).

Figure 5 . 6 :

 56 Figure 5.6: Surveyors surrounding a node for coordinates verification

Figure 5 . 7 :

 57 Figure 5.7: CDF of False positive probability differences.

Figure 5 . 8 :

 58 Figure 5.8: Correlation between distance and test performance.

Figure 5 . 9 :

 59 Figure 5.9: Undetected displacement as a function of direction.

Figure 5 . 10 :

 510 Figure 5.10: Self isolation: Detection probability.

Figure 5 . 11 :

 511 Figure 5.11: Self Isolation: False Positive Ratio.

Figure 5 . 13 :

 513 Figure 5.13: Average Certification Rate

Figure 5 . 14 :

 514 Figure 5.14: Progressive Displacement Attack: Security gain ratio varying the malicious nodes percentage in the overall population.

  2.1 Geometric space model of the Internet . . . . . . . . . . . . . . . . . . . 2.2 Basic network positioning method in a 2-d Euclidean space . . . . . . . . 2.3 The hierarchical network positioning architecture of NPS. . . . . . . . . 2.4 Triangle inequality with measured and predicted distances in PIC. . . . . 3.1 Effect of Disorder attack on Vivaldi with 1740 nodes . . . . . . . . . . . . 3.2 Injection of Disorder Attackers on Vivaldi: average relative error ratio. . .13 Colluding Isolation attack on Vivaldi: relative error of the target node . . 3.14 Colluding Isolation Attack on Vivaldi: CDF of relative errors. . . . . . . . 3.15 Combining attacks on Vivaldi (Disorder, Repulsion and Colluding Isolation attack strategy 1): impact on convergence. . . . . . . . . . . . . . . 3.16 Combined attacks on Vivaldi: effect of system size. . . . . . . . . . . . . Injection of Independent Disorder attackers: Impact of dimensionality. . 3.20 Anti-Detection NPS attack . . . . . . . . . . . . . . . . . . . . . . . . . . 3.21 Injection in NPS of Anti-detection naive attackers: impact on convergence. 3.22 Injection in NPS of Anti-detection naive attackers: effect of victims coordinates knowledge. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.23 Injection in NPS of Anti-detection naive attackers: effect of victims coordinates knowledge on the ratio of filtered malicious nodes over the overall filtered nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.24 Injected Anti-detection Sophisticated attacks on NPS: CDF. . . . . . . . . 3.25 Injected Anti-detection Sophisticated attacks on NPS: effect of victims coordinates knowledge on the ratio of filtered malicious nodes over the overall filtered nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Maximum prediction errors with closest Surveyor. . . . . . . . . . . . . . 4.9 ROC curves. Each tick on the plots corresponds to a different value of the test's significance level (α). . . . . . . . . . . . . . . . . . . . . . . . Prediction Error Histogram . . . . . . . . . . . . . . . . . . . . . . . . . 77

	xviii	LIST OF FIGURES
	3.19 LIST OF TABLES
	4.1
	xvii

3.3 Injected Disorder attack on Vivaldi: CDF of relative error at simulation tick = 5000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Injected Disorder Attack on Vivaldi: Impact of space dimensions . . . . . 3.5 Injection of Disorder Attackers on Vivaldi: Impact of system size on the attack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Effect of Repulsion attack on Vivaldi with 1740 nodes . . . . . . . . . . . . 3.7 Injected Repulsion Attack on Vivaldi: CDF of relative error. . . . . . . . . 3.8 Injected Repulsion Attack on Vivaldi: impact of space dimensions. . . . . 3.9 Injected Repulsion Attack on subsets of target nodes. . . . . . . . . . . . 3.10 Injection Repulsion Attack on Vivaldi: effect of system size . . . . . . . . 3.11 Effect of Colluding Isolation attack on Vivaldi with 1740 nodes . . . . . . . 3.12 Colluding isolation Attack on Vivaldi: average relative error ratio . . . . 33.17 Injection in NPS of Independent Disorder attackers (No prevention): average relative error. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.18 Injection in NPS of Independent Disorder attackers: CDF. . . . . . . . . . 3.26 Injection of colluding Isolation attack on NPS in scenario 1: CDF of relative errors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.27 Injection of colluding Isolation attack on NPS in scenario 2: CDF of relative errors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.28 Injection of colluding Isolation attack on NPS: Propagation of errors. . . 3.29 Injection of combined attacks on NPS (Independent disorder, Anti-Detection Sophisticated disorder and colluding isolation attackers): Impact on convergence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Quantile-Quantile plot of 2 innovation processes. . . . . . . . . . . . . . 4.2 Prediction errors (PlanetLab node). . . . . . . . . . . . . . . . . . . . . . 4.3 CDF of prediction errors. . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Impact of Surveyor population size on repretentativeness. . . . . . . . . 4.5 Representativeness with 8% Surveyor nodes. . . . . . . . . . . . . . . . 4.6 Maximum prediction errors with Surveyor filter parameters (PlanetLab). 4.7 Correlation between 'Node-Surveyor' RTTs and estimation accuracy (PlanetLab). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 4.10 True positive test fraction. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 False Positive Rate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.12 False negative rate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Results using the Kologorov Smirnov Test for fitting the inter-shift Times data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 A.1 Possible outcomes of a decision-making process . . . . . . . . . . . . . . 128 xxi 1

  .3. It is interesting to note that these

		1
		0.9
	Cumulative Distribution Function	0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.1				Simulations, Vivaldi Simulations, NPS PlanetLab, Vivaldi PlanetLab, NPS
		0	0	0.1	0.2	0.3	0.4	0.5	0.6	0.7
						Prediction Error

Table 4 .

 4

	1: Prediction Error Histogram
	Error Interval	(Vivaldi)	(NPS)
	0.0-0.05	257/830/922 232/854/943
	0.05-0.1	32/201/995	44/180/941
	0.1-0.15	5/3/992	18/5/229
	0.15-0.2	1/997/997	2/12/884
	0.4-0.45	4/3/56	3/5/12
	0.45-0.5	1/12/12	2/1/17
	0.5-0.55	1/985/985	2/32/40
	0.6-0.65	-	1/851/851

in the system does not yield a uniform distribution of Surveyors (i.e. "Surveyor clusters"

Table 5 .

 5 1: Results using the Kologorov Smirnov Test for fitting the inter-shift Times data.

	Fitted Distributions % of samples that passed the test
	log-Normal	445/450
	Rayleigh	2/450
	Weibull	5/450
	Gamma	6/450
	a good fit with the Weibull distribution. Table 5.1 gives a summary of our findings for
	the Kolmogorov Smirnov goodness of fit tests.

  2. L' Isolation: où les noeuds cibles seraient isolés dans l'espace de coordonnées. Cette attaque cible un noeud particulier, dans le but de le convaincre qu'il est positionné dans une zone isolée du réseau. Le but ultime est, par exemple, d'obliger ce noeud cible, à se connecter à un noeud complice, étant le plus proche dans la zone isolée, pour pouvoir par la suite lancer des attaques d'analyse de traffic ou d'homme du milieu (Man in the Middle). Une manière d'aboutir à la réalisation d'une telle attaque, est de retarder les mesures envoyées par la victime, et de falsifier ses propres coordonnées, de manière à ce que la victime calcule des coordonnées plus élevées que la réalité, et s'éloigne ainsi de sa position (et par la même des autres noeuds).

denoted also in the rest of this thesis, the predicted distance in the geometric embedding space

Azureus[10] is currently one of the most popular clients for BitTorrent, a file sharing protocol[START_REF]BitTorrent Specification wiki[END_REF]

I would like to thank Prof. Eugene Ng for sharing his code.

The value w accounts for the drift that has been observed in positioning systems[START_REF] Ledlie | Network Coordinates in the Wild[END_REF].

Note that in NPS, all permanent landmarks also act as Surveyors.

e l is the exponential moving weighted average of the measured relative errors of all previously completed embedding steps.

Significance level values α always increase as a ROC curve is "followed" from the origin. In our experiments, we used values of 1%, 3%,

5% and 10% for α.

We experimented with different Euclidean embedding spaces and a

2-dimensional coordinate space augmented with a height vector.

The Gaussian distribution was not tested because the empirical distribution was not symmetrical around a mean.

The convex hull of a set of points is the smallest convex set containing all the points. Think of it as being the smallest "enclosure" that can be formed with some of the points and that has no points outside it[START_REF] Berg | Computational Geometry, Algorithms and Applications[END_REF].

La Répulsion: où un noeud malicieux essait de convaincre ses victimes qu'il est positionné loin d'eux afin de réduire son attractivité, et ainsi, par exemple, se soulager de la charge de retransmission de paquets, en ne coopérant pas dans les processus normaux de l'application. Une manière de réussir une telle attaque, est de faire en sorte de montrer que ses conditions (en termes de performances ou de position) sont pires qu'elles ne le sont en réalité. Cela est accompli par le biais de retardements de mesures, et/ou en manipulant les coordonnées transmis aux autres noeuds.

Le Contrôle du système: cete attaque est possible dans le cas où des noeuds "normaux" peuvent être considérés comme des balises, i.e. la plupart des systèmes existants exceptés les systèmes centralisés. Dans les systèmes hiérarchiques, comme NPS, les noeuds essayent de monter dans la hiérarchie dans le but de tromper ou d'influencer le maximum de noeuds honnêtes.

ACKNOWLEDGMENTS

Appendix A

Hypothesis testing and Goodness of fit tests

In chapters 4 and 5, we used the Hypothesis testing technique for our anomalous behavior detection method. We also validate and assess our assumptions (either normality of the system error W n in chapter 4 or the log-normal distribution of Inter-Shift distributions in chapter 5), using goodness-of-fit tests (kolmogorov-Smirnov, Lilliefors and Chisquare tests). In the following we give a description of this statistical background.

A.1 Hypothesis Testing

We consider a binary hypothesis testing problem, where there are two hypotheses, H0 (often called the null hypothesis) and H1 (also called alternative hypothesis).

For each observation, the decision process must choose either hypothesis that best describes the observation.

Given two hypotheses, there are four possible outcomes when a decision is made.

127

Annex

The decision is called a detection when the algorithm selects H1 when H1 is in fact true. On the other hand, if the algorithm chooses H0 instead, it is called false negative.

Likewise, when H0 is in fact true, picking H1 constitutes a false positive. Finally, picking H0 when H0 is in fact true is termed nominal.

The outcomes of a decision making process, and their corresponding probability notations are listed in table A.1. The detection probability, P D , and the false positive probability, P F , are typically used to specify performance conditions of any detection algorithm. In particular, for user-selected values α and β, we desire that:

where typical values might be α = 0.01 and β = 0.99.

According to the Neyman-Pearson paradigm [START_REF] Rice | Mathematical Statistics and Data Analysis[END_REF], a decision as to whether or not to reject H 0 in favor of H 1 is made on the basis of a test statistic (typically a single number) computed on the empirical data and the fitted model. The set of values of the test statistic for which H 0 is accepted and rejected are called, respectively, the acceptance region and the rejection region. We reject the hypothesis if the test statistic A.2 Goodness of fit test 129 (TS) is larger than a number called the critical value (CV). Hence the rejection region is defined by TS > CV , and the value CV separates the rejection region from the acceptance region. One of the mistakes we can make when deciding whether or not to accept H 0 is the following: we reject H 0 when it is true. Let α denote the probability that we make this kind of mistake; α is called the significance level of the test. The rejection region (and hence critical value) is defined for a given probability α under the null hypothesis.

A.2 Goodness of fit test

A statistical test in which the validity of one hypothesis is tested without specification of an alternative hypothesis is called a goodness of fit test. The general procedure consists in defining a test statistic, which is some function of the data measuring the distance between the hypothesis and the data (in fact, the badness of fit), and then calculating the probability of obtaining data which have a still larger value of this test statistic than the value observed, assuming the hypothesis is true. This probability is called the size of the test or confidence level. Small probabilities indicate a poor fit.

High probabilities (close to one) correspond to good fits.

A.2.1 The Kolmogorov Smirnov test

For each potential variable T i from the data set, the one-sample Kolmogorov-Smirnov test (K-S) [START_REF] Shorack | Empirical Processes With Applications to Statistics[END_REF]compares the proportion of values less than T i with the ex-where T is the sample mean, and s is the sample standard deviation.

The empirical cdf of this Z-score series is computed. Similarly, the cdf of the standard normal distribution is obtained at the same probability points. The maximum difference of the two cdf's at any point is then computed. Superimposing plots of the two cdf's immediately reveals where the cdf's differ most, and this is the point yielding the Lilliefors statistic. The Kolmogorov-Smirnov test is identical to the Lilliefors test except that no conversion to Z-scores is made in the K-S test.

A.3 conclusion

Each test statistic described above provides an indicator of the quality of the fitting of the specified distribution, and is thus called a goodness-of-fit indicator. This indicator reports a measure of the deviation of the fitted distribution from the input data: hence the smaller its value, the better the achieved fitting. To answer the question "how small a value is needed for a good fit?" one uses the critical values. If the test statistic is less than the critical value, then we accept the hypothesis. The critical value is defined for a specific significance level α. If we accept the hypothesis for a given critical value associated with α, it means that we believe there is only an α percent chance that we are making a mistake using this decision criteria; in other words, we are 1α confident in our decision. The final metric we use to assess a fit is the p-value which is an indicator of the probability of a good fit; the p-value can be defined as the Pr(TS > c)

for some value c. If c > CV , then p < α. Put simply, the p-value is the smallest value of α for which the null hypothesis will be rejected.

Appendix B The Expectation Maximization method

The expectation-maximization (EM) algorithm is used for finding maximum likelihood estimates of a distribution's parameters, when the model depends on unobserved variables [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF].

EM operates by alternatively computing an expectation of the likelihood (E step), including the unobserved variables as if they were observed, and by maximizing the expected likelihood found on the E step (M step). The parameters computed in the M step are then reused in the E step, and the process is repeated.

Let x be the set of incomplete data, consisting for example in the set of observed values and z is the missing data (we dot not observed yet for instance). Together, z and

x form the complete data.

We denote the probability density function (continuous case) or probability mass function (discrete case) of the complete data with parameters given by the vector θ, as p(x, z|θ).

An EM algorithm iteratively improves an initial estimate θ 0 by constructing new 133 Annex estimates θ 1 , θ 2 , and so on. An individual re-estimation step that derives θ n+1 from θ n takes the following form:

where Q(θ) is the expected value of the log-likelihood. In other words, we do not know the complete data, so we cannot say what is the exact value of the likelihood, but given the data that we do know (the x's), we can find a posteriori estimates of the probabilities for the various values of the unknown z's. For each set of z's there is a likelihood value for θ, and we can thus calculate an expected value of the likelihood with the given values of x's (and which depends on the previously assumed value of θ because this influenced the probabilities of the z's). Q is then given by Q

where it is understood that this denotes the conditional expectation of log p (x, z|θ) being taken with the θ used in the conditional distribution of z fixed at θ n . In other words, θ n+1 is the value that maximizes (M) the conditional expectation (E) of the complete data log-likelihood given the observed variables under the previous parameter value.

Appendix C Présentation des Travaux de Thèse en

Franc ¸ais C.1 Introduction

Ces dernières années ont vu l'énorme croissance d'applications Internet (comme PASTRY [START_REF] Rowstron | Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems[END_REF], OCEANSTORE [START_REF] Kubiatowicz | OceanStore: An Architecture for Global-Scale Persistent Storage[END_REF], ESM [START_REF] Chu | A case for end system multicast[END_REF], SKYPE [START_REF][END_REF], etc.), basées et/ou bénéficiant des réseaux de recouvrement tenant compte de la topologie Internet. En particulier, la plupart des ces applications (si ce n'est toutes) et leurs réseaux de recouvrement (overlay) associés, se basent sur la notion de proximité réseau, typiquement définie en termes de délais d'aller-retour (RTT), pour l'optimisation de la sélection de voisins. Cependant, les mesures de proximité, peuvent s'avérer extrêmmement coûteuses en termes de consommation en bande passante. En effet, l'existence simultannée de plusieurs réseaux de couvertures, peut entraîner un surcoûts de communications élevé, dû aux mesures de proximité individuelles menées par chaque noeud du réseau de couverture. De plus, traquer la proximité au sein d'un groupe dynamique, nécessite une fréquence de mesure très grande. Cela induit encore plus de surcoûts de mesures. Afin de pallier ce problème, les systèmes de positionnement Internet, comme [START_REF] Ng | Predicting internet network distance with coordinates-based approaches[END_REF][START_REF] Pias | Lighthouses for Scalable Distributed Location[END_REF][START_REF] Costa | Practical Internet coordinates for distance estimation[END_REF][START_REF] Ng | A Network Positioning System for the Internet[END_REF][START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF][START_REF] Shavitt | Big-bang simulation for embedding network distances in euclidean space[END_REF], ont été introduits. Dans ces systèmes, l'idée principale, est que si 135