Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Francisco Brasileiro

Romaric Ludinard
email: romaric.ludinard@inria.fr

Bruno Sericola
email: bruno.sericola@inria.fr

DEPENDABILITY EVALUATION OF CLUSTER-BASED DISTRIBUTED SYSTEMS *

Awerbuch and Scheideler have shown that peer-to-peer overlay networks can survive Byzantine attacks only if malicious nodes are not able to predict what will be the topology of the network for a given sequence of join and leave operations. In this paper we investigate adversarial strategies by following specific protocols. Our analysis demonstrates first that an adversary can very quickly subvert overlays based on distributed hash tables by simply never triggering leave operations. We then show that when all nodes (honest and malicious ones) are imposed on a limited lifetime, the system eventually reaches a stationary regime where the ratio of polluted clusters is bounded, independently from the initial amount of corruption in the system.

Introduction

The adoption of peer-to-peer overlay networks as a building block for architecting Internet scale systems has raised the attention of making these overlays resilient not only to benign crashes, but also to malicious failure models [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF][START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF][START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF]. As a result, Byzantine-resilient overlays have been proposed (e.g., [START_REF] Fiat | Making chord robust to byzantine attacks[END_REF][START_REF] Baumgart | S/kademlia: A practicable approach towards secure keybased routing[END_REF][START_REF] Anceaume | PeerCube: an hypercubebased p2p overlay robust against collusion and churn[END_REF][START_REF] Srivatsa | Vulnerabilities and security threats in structured peer-topeer systems: A quantitiative analysis[END_REF]). Awerbuch and Scheideler [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF] have shown that peer-to-peer overlay networks can survive Byzantine attacks only if malicious nodes are not able to predict what will be the topology of the network for a given sequence of join and leave operations. A prerequisite for this condition to hold is to guarantee that nodes identifiers randomness is continuously preserved. However this is not sufficient as by holding a logarithmic number of addresses the adversary can disconnect some target from the overlay in a linear number of trials. Similarly, randomly placing data in the network, as operated in unstructured overlay networks, guarantees that data are difficult to attack however requires a linear number of queries to be retrieved which is not scalable [START_REF]Group spreading: A protocol for provably secure distributed name service[END_REF]. Inducing churn has been shown to be the other fundamental ingredient to preserve randomness. Churn is classically defined as the rate of turnover of peers in the system [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF], and thus induced churn refers to the general idea of forcing peers to move within the system. Several strategies based on this principle have been proposed. Most of them are based on locally induced churn. However either they have been proven incorrect or they involve a level of complexity that is too high to be practically acceptable [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF]. The other ones, based on globally induced churn, enforce limited lifetime for each node in the system. This keeps the system in an unnecessary hyper-activity, and thus needs to impose strict restrictions on nodes joining rate which limits its applicability to open systems.

In this paper we propose to leverage the power of clustering to design a practically usable solution that preserves randomness under an adaptive adversary. Our solution relies on the clusterized version of peer-to-peer overlays combined with a mechanism that allows the enforcement of limited nodes lifetime. Cluster-based overlays have revealed to be well adapted for reducing both the impact of churn on the system and the damage caused by failures in the absence of targeted attacks [START_REF] Anceaume | PeerCube: an hypercubebased p2p overlay robust against collusion and churn[END_REF][START_REF] Locher | eQuus: A provably robust and localityaware peer-to-peer system[END_REF][START_REF] Fiat | Making chord robust to byzantine attacks[END_REF]. The contributions of this paper are two-fold. We first investigate adversarial strategies by following specific protocols. Our analysis demonstrates that an adversary can very quickly subvert cluster-based overlays by simply never triggering leave operations. We then show that when all nodes are imposed on a limited lifetime, the system eventually reaches a stationary regime where the ratio of polluted clusters is bounded.

The remainder of this paper is organized as follows: In Section 2 we briefly describe the main features of cluster-based overlays, and their dependability issues. Section 3 presents the overlay operations. In Section 4 the adversarial behavior is modeled and its impact at cluster level by using a Markovian analysis is studied. In this section, we consider a non restricted adversary. Section 5 is devoted to the same study in the case of a restricted adversary. Section 6 shows that by inducing churn at all peers of the system, safety of the system is preserved. Section 7 demonstrates the practicability of our solution. We conclude in Section 8.

IJFCS

Dependability Evaluation of Cluster-based Distributed Systems 3

Overlay Networks

An overlay network is a virtual network built on top of a physical network. Nodes of the overlay, usually called peers, communicate among each other along the edges of the overlay by using the communication primitives provided by the underlying network (e.g., IP network service). The algorithms that peers use to choose their neighbors and to route messages define the overlay topology. The topology of unstructured overlays conforms with random graphs, i.e., relationships among peers are mostly set according to a random process which makes joining and leaving operations constraint free. Data placement enjoy the same absence of constraints. Any data can be placed on any peer thereby imposing flooding or random walk techniques to retrieve them. Randomly placing data in the network guarantees that data is difficult to attack but requires a linear number of queries to be retrieved which is definitively not scalable [START_REF]Group spreading: A protocol for provably secure distributed name service[END_REF]. This scalability issue can be circumvented at the price of strong restrictions on churn [START_REF] Bortnikov | Brahms: Byzantine resilient random membership sampling[END_REF]. Structured overlays (also called Distributed Hash Tables (DHTs)) build their topology according to structured graphs (e.g., hypercube, torus). For most of them, the following principles hold: each peer is assigned a unique random identifier from an m-bit identifiers space. Identifiers (denoted IDs in the following) are derived by applying some standard cryptographic one-way hash function on the peers network address. The value of m (128 for the standard MD5 hash function) is large enough to make the probability of identifiers collision negligible. The identifier space is partitioned among all the peers of the overlay. Peers self-organize within the structured graph according to a distance function D based on peers IDs (e.g., two peers are neighbors if their IDs share some common prefix), plus possibly other criteria such as geographical distance. Each application-specific object, or data-item, is assigned a unique identifier, called key, selected from the same m-bit identifiers space. Each peer p owns a fraction of all the data items of the overlay. The mapping derives from the distance function D. In the following, we will use the term peer (or key) to refer to both the peer (or key) and its m-bit representation. Following the seminal work of Plaxton et al [START_REF] Plaxton | Accessing nearby copies of replicated objects in a distributed environment[END_REF], diverse DHTs have been proposed (e.g., CAN [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF], Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], Pastry [START_REF] Druschel | Past: A large-scale, persistent peer-to-peer storage utility[END_REF], Kademlia [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the XOR metric[END_REF]). All these DHTs have been proven to be highly satisfactory in terms of efficiency and scalability (i.e., their key-based routing interface guarantees operations whose complexity in messages and latency usually scale logarithmically with system size). However, in presence of adversarial behavior, relying on single peers to ensure the system connectivity and the correct retrieval of data is clearly not sufficient, as by holding a logarithmic number of addresses the adversary can in a linear number of trials disconnect some target from the overlay. On the contrary, by having peers gathered into quorums or clusters, one can introduce the unpredictability required to deal with Byzantine attacks through randomized algorithms. This has led to cluster-based structured overlay networks.

Cluster-based Structured Overlay Networks

Cluster-based structured overlay networks are such that clusters of peers substitute for peers at the vertices of the structured graph. Each vertex of the structured graph is composed of a set or cluster of peers. Peers join the clusters according to a given distance metric D. For instance in PeerCube [START_REF] Anceaume | PeerCube: an hypercubebased p2p overlay robust against collusion and churn[END_REF], peer p joins the (unique) cluster whose label is a prefix of p's identifier, while in eQuus [START_REF] Locher | eQuus: A provably robust and localityaware peer-to-peer system[END_REF], p joins the (unique) cluster whose members are geographically the closest to p. Clusters in the overlay are uniquely labelled. Size of each cluster is both lower and upper bounded. The lower bound, named c in the following, usually satisfies some constraint based on the assumed failure model. For instance c ≥ 4 allows Byzantine tolerant agreement protocols to be run among these c peers despite the presence of one Byzantine peer [START_REF] Lamport | The byzantine generals problem[END_REF]. The upper bound, that we call S max , is typically in O(log U ) where U is the current number of peers in the overlay, to meet scalability requirements. Once a cluster size exceeds S max , this cluster splits into two smaller clusters, each one populated with the peers that are closer to each other according to distance D. Once a cluster undershoots its minimal size c, this cluster merges with the closest cluster in its neighborhood. For space reasons we do not give any detail regarding localization of a cluster in the overlay nor the split/merge operations. None of these processes are strictly necessary to understand our work. The interested reader is invited to read their descriptions in the original papers (e.g. [START_REF] Fiat | Making chord robust to byzantine attacks[END_REF][START_REF] Anceaume | PeerCube: an hypercubebased p2p overlay robust against collusion and churn[END_REF][START_REF] Locher | eQuus: A provably robust and localityaware peer-to-peer system[END_REF]).

In the present work we assume that at cluster level, peers are organized as core and spare members. Members of the core set are primarily responsible for handling messages routing and clusters operations. Management of the core set is such that its size is maintained to constant c. Spare members are the complement number of peers in the cluster. Size s of the spare set is such that s ≤ S where S = S maxc. In contrast to core members, spare members are not involved in any of the overlay operations. Rationale of this classification is two-fold: first it allows to introduce the unpredictability required to deal with Byzantine attacks through a randomized core set generation algorithm as shown in the sequel. Second it limits the management overhead caused by the natural churn present in typical overlay networks through the spare set management. In the following we assume that join and leave events have an equal chance to occur in any cluster.

Dependability Issues

A fundamental issue faced by any practical open system is the inevitable presence of peers that try to manipulate the system by exhibiting undesirable behaviors [START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF]. Such peers are classically called malicious or Byzantine. Malicious peers can devise complex strategies to prevent peers from discovering the correct mapping between peers and data keys. They can mount Sybil attacks [START_REF] Douceur | The sybil attack[END_REF] (i.e., an attacker generates numerous fake peers to pollute the system), they can do routing-table poisoning (also called eclipse attacks [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF][START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF]) by having honest peers redirecting outgoing links towards malicious ones, or they can simply drop or re-route messages towards other IJFCS Dependability Evaluation of Cluster-based Distributed Systems 5 malicious peers. They can magnify their impact by colluding and coordinating their behavior. We model these strategies through a strong adversary that controls these malicious peers. We assume that the adversary has large but bounded resources in that it cannot control more than a fraction µ (0 < µ < 1) of malicious peers in the whole network. Note that in the following we make a difference between the whole network and the overlay. The network encompasses all the peers that at some point may participate to the overlay (i.e. 2 m peers), while the overlay contains at any time the subset U of participating peers. Thus, while µ represents the assumed fraction of malicious peers in the network, the goal of the adversary is to populate some parts of the overlay with a larger fraction of malicious peers in order to subvert the correct functioning of the overlay. Finally, a peer which always follows the prescribed protocols is said honest. Note that honest peers cannot a priori distinguish honest peers from malicious ones.

Security Schemes

We assume the existence of a public key cryptography scheme that allows each peer to verify the signature of each other peer. We also assume that correct peers never reveal their private keys. Peers IDs and keys (private and public) are acquired via a registration authority. When describing the protocols, we ignore the fact that messages are signed, and recipients of a message ignore any message that is not signed properly. We also use cryptographic techniques to prevent a malicious peer from observing or unnoticeably modifying a message sent by a correct peer. However a malicious peer has complete control over the messages it sends and receives.

Operations of the Overlay

When a peer joins a cluster or leaves it, corresponding operations are executed. Design of these operations takes advantage of peers role separation. The leave operation for peers in the core set introduces a certain amount of unpredictability required to deal with Byzantine attacks through a randomized core set generation algorithm. On the other hand both leave operations for peers in the spare set and join operations have no impact on the overall topology (provided that the size of the concerned cluster does not reach its lower or upper bounds) discouraging brute force denial of service attacks. Specifically:

• join(p): when peer p joins the system, it joins the spare set of the closest cluster G in the system (according to distance D). Core member of G update their spare view to reflect p's insertion (note that the spare view update does not need to be tightly synchronized among all core members).

• leave(p): when peer p leaves its cluster G, either p belongs to G spare view or to G core view. In the former case, core members of G simply update their spare view to reflect p's departure, while in the latter case the core view maintenance procedure is triggered. Two maintenance procedures are analyzed. The first one, called procedure 1 , simply consists in replacing the left core member by one randomly chosen among the spare members. The second one, called procedure 2 , consists in renewing the whole core set by choosing c random peers among the whole cluster.

The join and leave operations make up the cluster protocol. In the following Protocol 1 refers to a leave(.) operation followed by a join(.) operation with procedure 1 as maintenance procedure. Similarly, Protocol 2 refers to a leave(.) operation followed by a join(.) operation using procedure 2 .

Modeling the Adversarial Strategy in a Cluster

In this section, we investigate to which extent the two previously described protocols, i.e., Protocol 1 and Protocol 2 , prevent the adversary from elaborating deterministic strategies to compromise the correctness of a targeted cluster G. Correctness of a cluster is compromised as soon as a quorum of core members are malicious. Specifically, in both maintenance procedures, core members trigger a Byzantineresilient consensus algorithm to agree on the composition of the renewed core view. It is well-known that a necessary and sufficient condition to prevent agreement among a set of nodes is that strictly more than a third of these nodes are malicious [START_REF] Lamport | The byzantine generals problem[END_REF]. In our context, cluster G is said polluted if its core set is populated by strictly more than ⌊(c -1)/3⌋ malicious peers, with c the size of the core set. In the following, we denote by c ′ the value ⌊(c -1)/3⌋.

Both Protocol 1 and Protocol 2 are modeled by using the ball and urn model as presented in Figure 1. Specifically, the very large number of peers in the network is depicted by a potentially infinite number of white and red balls in a bag. White balls represent honest peers, while red ones represent malicious peers. There is a proportion 1-µ of white balls and a proportion µ of red balls in the bag. In addition to the bag, we consider two urns, referred to as C and S in the following, which respectively represent the core set and the spare set of a cluster. Join and leave operations are modeled through the throwing and withdrawing of balls into and from the urns. For instance, drawing a ball from the bag and throwing this ball into S models the insertion of a new peer into the overlay and its joining into the spare set of a cluster. Drawing a ball from S ∪ C and throwing this ball into the bag models the leaving of a peer from the overlay. In Figure 1, both protocols are made of two indivisible tasks. Task 1 models the random choice of a peer within a cluster while Task 2 is concerned with the leave and join operations. We consider a succession of rounds r 1 , r 2 , . . . during which the rules of the protocols are applied. Rules are oblivious to the color of the balls, meaning that they cannot distinguish between the white and the red balls.

As previously said the goal of the adversary is to maximize the number of red balls in both urns C and S so that the number of red balls in C is bound to always exceed quorum c ′ = ⌊(c -1)/3⌋. By construction, the adversary has only access to red balls. Thus an effective strategy for the adversary to gain this quorum is to prevent red balls from being extracted from both urns. Specifically, in Task 1 of both protocols (see Figure 1), if the drawn ball b 0 is red then this ball is put back into the urn it was drawn from (i.e., either C or S). In that case, Task 2 is not applied, and a new round is triggered. This strategy ensures that the number of red balls in C ∪ S is non decreasing.

We model the effects of rounds r 1 , r 2 , . . . using a homogeneous Markov chain denoted by X = {X n , n ≥ 0} representing the evolution of the number of red balls in both urns C and S. More formally, the state space Ω of X is defined by Ω = {(x, y) | 0 ≤ x ≤ c, 0 ≤ y ≤ s}, and for n ≥ 1 the event X n = (x, y) means that after the n-th transition or n-th round the number of red balls within urn C is equal to x and the number of red balls within urn S is equal to y. The transition probability matrix P of X depends on both the rules of the given protocol and the adversarial behavior. This matrix is detailed in each of the following subsections. We define a state as polluted if in this state urn C contains strictly more than c ′ = ⌊(c -1)/3⌋ balls. Conversely, a state that is not polluted is said to be safe. In the remaining of this paper, the initial probability distribution is denoted by α.

Protocol 1

Regarding Protocol 1 , the subset of safe states A is defined as

A = {(x, y) | 0 ≤ x ≤ c ′ , 0 ≤ y ≤ s}, while the set of polluted states B, is the subset Ω -A, i.e., B = {(x, y) | c ′ < x ≤ c, 0 ≤ y ≤ s}.
By the rules of Protocol 1 , one can never escape from the subset of states B to switch back to safe states A since the number of red balls in C is non decreasing. Thus, the adversary wins the protocol when process X reaches the closed subset B, as illustrated in Figure 2. Matrix P and the initial probability vector α are partitioned in a manner that matches the decomposition of Ω = A ∪ B, that is The computation of the transition probabilities of matrix P is illustrated in Figure 3. In this tree, each edge is labelled by a probability and its corresponding event according to the rules of Protocol 1 . This figure can be interpreted as follows: At round r, r ≥ 1, starting from state (x, y) (root of the tree), the Markov chain can visit four different states, namely (x, y), (x, y + 1), (x + 1, y -1), and (x + 1, y) (leaves of the tree). The probability associated with each one of these transitions is obtained by summing the products of the probabilities discovered along each path starting from the root to the leaf corresponding to the target state. Derivation of the transition probability matrix P of Markov chain X associated with Protocol 1 is as follows: for all x ∈ {0, . . . , c} and for all y ∈ {0, . . . , s}, we have

P = P A P AB 0 P B and α = (α A α B )
p (x,y),(x,y) = 1 c + s x + (c -x)(s -y)(1 -µ) s + y + (s -y)(1 -µ) p (x,y),(x,y+1) = (c + s -x)(s -y)µ (c + s)s for y ≤ s -1 p (x,y),(x+1,y-1) = (c -x)y(1 -µ) (c + s)s for x ≤ c -1 and y ≥ 1 p (x,y),(x+1,y) = (c -x)yµ (c + s)s for x ≤ c -1.
In all other cases, transition probabilities are null.

Protocol 2

For s = 1, it is easy to see that Protocol 2 is equivalent to Protocol 1 . On the other hand, in contrast to Protocol 1 , Protocol 2 alternates between safe and polluted states. After a random number of these alternations the process enters a set of closed polluted states. Indeed, by the rules of the protocol, one can escape finitely often from polluted states (x, y) to switch back to safe states as long as (x, y) satisfies x + y < s + c ′ (there are still sufficiently many white balls in both C and S so as to successfully withdraw c balls such that C is safe). However, there always exists a round such that a state (x, y) is entered, where x + y ≥ s + c ′ . From this round onwards, going back to safe states is impossible: the adversary has won the protocol. Formally, the subset of safe states A is defined, as for Protocol 1 , by

A = {(x, y) | 0 ≤ x ≤ c ′ , 0 ≤ y ≤ s}.
On the other hand we need to decompose IJFCS Dependability Evaluation of Cluster-based Distributed Systems 9 By proceeding similarly as in Section 4.1, we derive the transitions of process X associated with Protocol 2 . Briefly, when the protocol starts in state (x, y) at round r, it remains in state (x, y) during the round if either ball b 0 is red or b 0 is white, it has been drawn from S, and b 2 is white. It changes to state (x, y + 1) if b 0 is white, it has been drawn from S, and b 2 is red. Finally the protocol switches to state (k, x + yk + ℓ), where k is an integer k = 0, . . . , min(c, x + y) and ℓ = 0, 1 if b 0 is white and it has been drawn from C, and the maintenance procedure leads to the choice of k red balls. For all x ∈ {0, . . . , c}, y ∈ {0, . . . , s}, and s > 1, we have

(x, y) (x, y) (b 0 is red) x c (x + 1, y -1) (b 2 is white) 1 -µ (x + 1, y) µ (b 2 is red) (b 1 is red) y s (x, y + 1) µ (x, y) 1 -µ (b 2 is white) s-y s (b 1 is white) c-x c (b 0 is white) (b 0 ∈ C) c c+s (x, y) (b 0 is red) y s (x, y) 1 -µ (x, y + 1) µ (b 2 is red) 1 s-y s (b 0 is white) s s+c (b 0 ∈ S)
p (x,y),(x,y) = x c + s + y c + s + s -y c + s (1 -µ) + c -x c + s (1 -µ)q(x, x + y) p (x,y),(x,y+1) = s -y c + s µ + c -x c + s µq(x, x + y) for y ≤ s -1 p (x,y),(k,x+y-k) = c -x c + s (1 -µ) q(k, x + y) for 0 ≤ k ≤ min(c, x + y) and k = x p (x,y),(k,x+y-k+1) = c -x c + s µq(k, x + y) for 0 ≤ k ≤ min(c, x + y) and k = x where q(z, x + y) = x + y z c + s -1 -(x + y) c -z c + s -1 c 1 {0≤x+y-z≤s-1} (1)
is the probability of getting z red balls when c balls are drawn, without replacement, in an urn containing x + y red balls and c + s -1 -(x + y) white balls, referred to as the hypergeometric distribution. 1

Initial Distributions

In the experiments conducted for this work, we consider two initial distributions. The first one, which we denote by β, consists in drawing c + s balls from the bag such that c of them are thrown into urn C, and the other s ones are thrown into urn S. This initial state X 0 is defined by X 0 = (C r , S r ) where C r (resp. S r ) is the initial number of red balls in C (resp. S). Thus both C r and S r follow a binomial distribution, and assuming they are independent, we get for x = 0, . . . , c and y = 0, . . . , s

β(x, y) = P{C r = x, S r = y} = c x µ x (1 -µ) c-x s y µ y (1 -µ) s-y . (2)
The second one, that we denote δ, consists simply in starting from state (0, 0), that is the state free from red balls, i.e., δ(x, y) = δ 0x δ 0y with δ ij the Kronecker delta.

(3)

Sojourn Time of both Protocols in Safe States

We start our study by investigating for i = 1, 2 the distribution T (i)

A which counts the total number of rounds spent by Protocol i in the subset of safe states A before absorption. Specifically T (1)

A = inf{n ≥ 0 | X n ∈ B}.

The probability mass function of T 1

A for k ≥ 0 is easily derived as P{T (1) A are respectively given by P{T (1) A ≤ k} = 1α A (P A ) k ✶, and E(T (1) A ) = α A (I -P A ) -1 ✶.

A = k} = α B ✶ if k = 0 α A (P A ) k-1 (I -P A )✶ if k ≥ 1
(

) 5
Following the results obtained in Sericola [START_REF] Sericola | Closed form solution for the distribution of the total time spent in a subset of states of a Markov process during a finite observation period[END_REF], for Protocol 2 , the probability mass function of T

(2)

A = ∞ n=1 1 {Xn∈A} is given by P{T (2) A = k} = 1 -v✶ if k = 0 vR k-1 (I -R)✶ if k ≥ 1 ( 6
)
where v = α A + α C (I -P C ) -1 P CA and R = P A + P AC (I -P C ) -1 P CA . The cumulative distribution function and expectation of T

A are respectively given by

P{T (2) A ≤ k} = 1 -vR k ✶, and E(T (2) A ) = v(I -R) -1 ✶. ( 7
)

A ) and E(T (2)

A ) independently from the ratio of red balls in the bag. Similarly, for a given cluster size, augmenting the ratio of red balls in the bag decreases both E(T (1)

A ) and E(T (2)

A ). Now Figure 5(b) shows that for small values of µ Protocol 2 overpasses Protocol 1 , while for larger values of µ, we observe an inverse tendency. Interpretation of this result is as follows. When the size s of S is equal to 1, both protocols are equivalent as illustrated in Figures 5(a) and 5(b). Now, consider the case where the size s of S gets larger compared to C's one. The probability to draw a ball from S tends to 1. Now as the adversary never withdraws its red balls from any urns, the number of red balls within S is non decreasing. Hence, the larger µ is the faster the ratio of red balls in S tends to 1. With small probability, a ball from C is drawn. In Protocol 1 it is replaced with high probability by a red ball drawn from S. Hence to reach a polluted state, c ′ + 1 white balls have to be replaced by red ones. While with Protocol 2 the renewal of C reaches with high probability a polluted state in a single step. Thus, even if Protocol 2 continues to alternate for a finite number of times between safe and polluted subset of states, the total time spent in safe states is less than the one spent by Protocol 1 . Note that one cannot observe such a behavior when the initial ratio of red balls in both urns is non null (see Figure 5(a)) as it takes less steps for both protocols to switch to polluted states.

Alternation between Safe and Polluted States of Protocol 2

A deeper investigation of Protocol 2 allows to study the duration and frequency of successive sojourn times in subsets A and C. For n ≥ 1, we denote by T

T (2) A = ∞ n=1 T (2) A,n and T (2) C = ∞ n=1 T (2) C,n .
From Sericola and Rubino [START_REF] Sericola | Sojourn times in Markov processes[END_REF], we have for n ≥ 1 and k ≥ 0

P{T (2) A,n ≤ k} = 1 -vG n-1 (P A ) k ✶, ( 9
)
where v is defined in Relation ( 6) and G = (I -P A ) -1 P AC (I -P C ) -1 P CA . Symmetrically, we have

P{T (2) C,n ≤ k} = 1 -wH n-1 (P C ) k ✶, (10)
where w = α C + α A (I -P A ) -1 P AC and H = (I -P C ) -1 P CA (I -P A ) -1 P AC . The expectations of T

A,n and T

C,n are respectively given by E(T

(2) A,n ) = vG n-1 (I -P A ) -1 ✶ and E(T (2) C,n ) = wH n-1 (I -P C ) -1 ✶. ( 11
)
Figure 6(a) shows the expected duration and frequency of successive sojourn times in subsets A and C for Protocol 2 . a Clearly, the protocol runs more rounds in C than it does in A. Note that for n ≥ 7, the expected duration of the sojourn times in both A and C is already close to 0. Figure 6(b) depicts the percentage of rounds spent by Protocol 2 in safe states before absorption as a function of the size s of S. This percentage is described by

E(T (2)
A ) E(T

(2) A ) + E(T (2) C ) = v(I -R) -1 ✶ v(I -R) -1 ✶ + w(I -T ) -1 ✶ (12)
a Note that if we consider the first sojourn time in the subset of safe states A of both protocols, then Protocol 1 always overpasses Protocol 2 both in expectation and with respect to their cumulative distribution functions [START_REF] Anceaume | Dependability evaluation of cluster-based distributed systems[END_REF])

IJFCS

Dependability Evaluation of Cluster-based Distributed Systems 13 where v and R are given in Relation (6), w is given in Relation [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF], and T = P C +P CA (I -P A ) -1 P AC . In accordance with the intuition, this percentage decreases with larger values of µ, and stabilizes for increasing values of s.

A;1 )

E(T (2)
C;1 )

E(T (2)
A;2 )

E(T (2)
C;2 )

E(T (2)
A;3 )

E(T (2)
C;3 ) ... ... (a) Succession of E(T (2)
A,n ) and E(T

C,n ) as a function of the rounds number. We have α = β, c = 10, s = 20 and µ = 25%.

E(T (2)
A )=(E(T (2)
A ) +E(T (2)
C ))

mu=5% mu=10% mu=15% mu=20% mu=25% (b) E(T (2)
A )/(E(T

A ) + E(T (2)
C )) as a function of the size s of S. We have α = β, and c = 10. An aggregated view of the total time spent in transient states, i.e. A for Protocol 1 , and A ∪ C for Protocol 2 , before absorption is depicted in Figure 7. The main observation drawn from this figure is that the total time spent in transient states linearly increases with the size of S, and thus increases logarithmically with the size of the system. On the other hand, this time is mainly spent in C, and this tendency increases with larger values of s which is confirmed by Figure 6

Lessons Learnt from this Comparison

The main lessons learnt from this preliminary study is that increasing the amount of randomization of the protocol does make it necessarily more resilient to stronger adversaries. From a practical point of view this result is interesting as handling the renewal of a set of entities requires costly agreement protocols to be run among the interested parties. Typically, complexity of these protocols is in O(n 3 ) where n is the number of parties. Unfortunately by allowing malicious peers to stay indefinitely long at the same position in the overlay, both protocols are not sufficient to prevent the adversary from progressively surrounding honest peers and gaining the quorum. In the following section we show that by limiting the lifetime of malicious peers in the same cluster, safety of the whole cluster is eventually guaranteed.

Constraining the Adversary by Limiting the Sojourn Time in a Cluster

It has been shown [START_REF]Group spreading: A protocol for provably secure distributed name service[END_REF] that structured overlays cannot survive targeted attacks if the adversary may keep sufficiently long its malicious peers at the same position in the overlay. Indeed, once malicious peers have succeeded in sitting in a focused region of the overlay, they can progressively gain the quorum by simply waiting for honest peers to leave their position, leading to the eventual isolation of honest peers.

The two fundamental properties that prevent peers isolation are the guarantee that peers identifiers are random, and that peers cannot stay forever at the same position in the system [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF].

From a practical point of view, implementing limited peers lifetime and unpredictable identifiers assignment, can be achieved by adding an incarnation number to the fields that appear in the peer's certificate (certificates are acquired at trustworthy Certification Authorities (CAs)), and by hashing this certificate to generate the peer's identifier. By the properties of hash functions, peers identifiers are unpredictable. The incarnation number limits the lifetime of identifiers. The current incarnation k of any peer p can be computed as k = ⌈(tivt)/L⌉, where ivt is the initial validity time of the peer's certificate, t is the current time, and L is the length of the lifetime of each peer's incarnation. Thus, the k th incarnation of peer p expires when its local clock reads ivt + kL. At this time p must rejoin the system using its (k + 1) th incarnation. This is discussed in details in [START_REF] Anceaume | Dependability evaluation of cluster-based distributed systems[END_REF].

Coming back to our analysis, we model the constraint on the adversary by preventing the adversary from keeping its red balls in both urns infinitely long, so that randomness among red and white balls is continuously preserved. As previously, we investigate both protocols presented in Figure 1. It is not difficult to see that both protocols alternate between the subset of safe states of Ω = A ∪ B, we partition matrix P and the initial probability vector α by writing P = P A P AB P BA P B and α = (α A α B ).

A = {(x, y) | 0 ≤ x ≤ c ′ , 0 ≤ y ≤ s},

Protocol 1

By proceeding exactly as in Section 4, we derive the transition probability matrix P for Protocol 1 . That is, for all x ∈ {0, . . . , c} and y ∈ {0, . . . , s}, we have In all other cases, transition probabilities are null.

Protocol 2

Similarly for all x ∈ {0, . . . , c} and y ∈ {0, . . . , s} the entries of P for Protocol 2 are given by

p (x,y),(x,y) = xq(x, x + y -1)µ c + s + (c -x)q(x, x + y)(1 -µ) c + s + yµ + (s -y)(1 -µ) c + s p (x,y),(x,y-1) = x c + s q(x, x + y -1)(1 -µ) + y c + s (1 -µ) for y ≥ 1 p (x,y),(x,y+1) = c -x c + s q(x, x + y)µ + s -y c + s µ for y ≤ s -1 p (x,y),(k,x+y-k-1) = x c + s q(k, x + y -1)(1 -µ) for max(0, x + y -1 -s) ≤ k ≤ min(c, x + y -1) and k = x (14) p (x,y),(k,x+y-k) = x c + s q(k, x + y -1)µ + c -x c + s q(k, x + y)(1 -µ)
for max(0, x + y -s) ≤ k ≤ min(c, x + y -1) and k = x p (x,y),(k,x+y-k+1) = c -x c + s q(k, x + y)µ for max(0, x + y + 1 -s) ≤ k ≤ min(c, x + y) and k = x, where q(z, x + y) is given by Relation [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF]. In all other cases, transition probabilities are null.

E(T (i) A,n ) = vG n-1 (I -P A ) -1 ✶ and E(T (i) B,n ) = wH n-1 (I -P B ) -1 ✶ (15)
where v = α A + B (I -P B ) -1 P BA , G = (I -P A ) -1 P AB (I -P B ) -1 P BA , w = α B + α A (I -P A ) -1 P AB and H = (I -P B ) -1 P BA (I -P A ) -1 P AB . For both protocols, the Markov chain X is finite, irreducible and aperiodic so the stationary distribution exists and is unique. We denote by π the stationary distribution of the Markov chain X. The row vector π is thus the unique solution to the linear system πP = π and π✶ = 1. As we did for row vector α, we partition vector π according to the partition Ω = A ∪ B by writing π = (π A π B ), where sub-vector π A (resp. π B ) contains the stationary probabilities of states of A (resp. B). The mean percentage of time spent in subset A during the j-th sojourn is equal for Protocol i (i=1,2) to E(T

(i) A,j )/(E(T (i) A,j ) + E(T (i) B,j )). By Cesàro lemma, lim n→∞ n j=1 E(T (i) A,j ) n j=1 (E(T (i) A,j ) + E(T (i) B,j )) = lim n→∞ E(T (i) A,n ) E(T (i) A,n ) + E(T (i) B,n ) = π A ✶ (16)
and the first hitting time to reach subset B is given, for every k ≥ 0, by

P{T (i) A,1 ≤ k} = 1 -α A (P A ) k ✶.
Figures 8(a) and 8(b) show the behavior of the Markov chains associated with both protocols during their first 11 sojourn times in both A and B. First, for µ = 25% both protocols spend more than 3/4 of their time in safe states and their convergence speed to π A ✶ is very fast (convergence is reached in a single step for Protocol 1 and in 6 steps for Protocol 2 ) as shown in Figure 8(a). Figure 8(b) shows that the frequency at which safe and polluted states alternate is 3 times lower for Protocol 1 than for Protocol 2 . From a practical point of view this is interesting as it makes Protocol 1 more adapted to dynamic environment compared to Protocol 2 (i.e., Protocol 1 handles a higher number of connections and disconnections before switching to a polluted state than Protocol 2 does).

Theorem 1. For both protocols, the stationary distribution π is equal to β, i.e. for all x = 0, . . . , c and y = 0, . . . , s, we have lim n-→∞ P{X n = (x, y)} = β(x, y) with β(x, y) given by relation [START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF]. These results are illustrated in Figure 9. The main observation is that with a constrained adversary, the expected number of safe clusters for both protocols tends to the same limit ℓπ A ✶ whatever the amount of initial pollution, while with a non constrained adversary all clusters get eventually polluted. This clearly shows that by limiting the time spent by peers at the same position in the overlay, targeted attacks are tolerated.

Practical Significance of the Results

In this section, we evaluate the practical significance of our results when instantiated with real traces. Traces we are referring to have been collected in the Overnet file sharing network and analyzed in [START_REF] Bhagwan | Understanding availability[END_REF]. The main reasons for using these traces is that Overnet peers are identified by permanent IDs which allows to observe finegrained behavior of active peers in the overlay. Traces which were collected for a period of 15 days have shown that every day between 70, 000 and 90, 000 peers IDs are present in the overlay. It has been registered that each peer triggers in average IJFCS Dependability Evaluation of Cluster-based Distributed Systems 19 6.4 join and leave events per day, that is in average each peer joins the overlay every 7.5 hours. Thus, for an average population of 80, 000 peers, this makes 512 970 join and leave events per day. In our context, an average population of U = 80, 000 peers leads to around ℓ = U/⌊log 2 U ⌋ = 5, 000 clusters each populated by ⌊log 2 U ⌋ = 16 peers, and thus to around U/ℓ × 3.2 = 52 leave-join rounds per day per cluster. Thus, in a presence of a non-constrained adversary, extrapolation of Figure 7 shows that for µ = 5%, c = 10 and for s = 6, it takes one day and a half (i.e., 85 rounds) for the adversary to definitively pollute a targeted cluster when Protocol 1 is run while it takes 5 days (i.e., 260 rounds) when Protocol 2 is used. Moreover, in the presence of a constrained adversary, one can derive from our study the average lifetime that must be imposed on malicious peers to prevent pollution. This comes down to compute the average frequency at which a cluster becomes polluted which is given by 1/(α A P AB ✶). Coming back to the traces, for c = 10, s = 6 and µ = 5%, peers must leave their cluster every 104 days (5455 rounds) when Protocol 1 is run and every 41 days (i.e., 2152 rounds) when Protocol 2 is used to prevent pollution. Now, when µ = 25%, malicious peers need to leave every 20 hours (i.e., 45 rounds) with Protocol 1 and every 7 hours (i.e., 2152 rounds) with Protocol 2 . Clearly these frequencies remain fully compatible with the rate at which honest peers have been observed to leave the system (i.e., every 24/3, 2 = 7.5 hours in average). This clearly show the practicability of the induced churn approach in large scale systems.

Conclusion

In this paper, we have proposed a mechanism that enables the enforcement of limited peers lifetime compliant with DHT-based overlays specificities. We have investigated the long run behavior of several adversarial strategies. Our analysis has demonstrated that an adversary can easily subvert a cluster-based overlay by simply never triggering leave operations. We have shown that when peers have to regularly leave the system, a stationary regime where the ratio of malicious peers is bounded is eventually reached. Finally, we have shown that this induced churn is fully compatible with the natural churn observed in peer-to-peer systems, which makes our approach definitively adapted to large scale and open systems.

IJFCSFig. 1 .

 1 Fig. 1. Rules of Protocol 1 and Protocol 2 .

Fig. 2 .

 2 Fig. 2. Aggregated view of the Markov chains associated with Protocol 1 . Safe states are represented by A, and polluted ones by B. B is an absorbing class.

Fig. 3 .

 3 Fig. 3. Transition diagram for the computation of matrix P of Protocol 1 .

Fig. 4 .

 4 Fig. 4. Aggregated view of the Markov chains associated with Protocol 2 . Safe states are represented by A, and polluted states by C and D. State D is an absorbing class.

IJFCS

  Dependability Evaluation of Cluster-based Distributed Systems 11where ✶ is the column vector with all components equal to 1. The cumulative distribution function and the expectation of T[START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF]

Fig. 5 .

 5 Fig. 5. E(T (1) A ) (see Relation (5)) represented by dark bars and E(T (2) A ) (see Relation (7)) represented by light grey bars as a function of s and the percentage µ of red balls. Notation 5, 10, . . . 25 denotes µ = 5%, 10%, . . . , 25%. In all these experiments c = 10.

Figure 5 (

 5 Figure 5(a) and Figure 5(b) compare the expected number of rounds run in safe states for both protocols according to the two initial distributions β and δ. In accordance with the intuition, increasing the size of the urns augments both E(T (1)

  ) the distribution of the time spent by the Markov chain X during its n-th sojourn in subset A (resp. C). The total time spent in subset A (resp. C) before reaching subset D is given by

Fig. 6 .

 6 Fig. 6. Sojourn Times in Transient States for Protocol 2 .

  (b).

  Fig. 7. E(T (1) A ) (Relation (5)) represented by dark colored bars, and E(T (2) A )+E(T (2) C ) (Relation (12)) represented by light grey and grey colored bars as a function of s and µ. In all these experiments c = 10.

  and the subset of polluted ones B = {(x, y) | c ′ < x ≤ c, 0 ≤ y ≤ s} for an infinite number of rounds. Both subsets A and B are transient, preventing the adversary from ever winning any of the two protocols. Following the decomposition IJFCS Dependability Evaluation of Cluster-based Distributed Systems 15

p 1 p 1 p

 11 (x,y),(x,y) = xy + (c(s -y) -xs)(1 -µ) (c + s)s + yµ + (s -y)(1 -µ) c + s p (x,y),(x,y-1) = (x + s)y (c + s)s (1 -µ) for y ≥ 1 p (x,y),(x,y+1) = c -x + s c + s s -y s µ for y ≤ s -1 p (x,y),(x+1,y-1) = (c -x)y (c + s)s (1 -µ) for x ≤ c -1 and y ≥ 1 (13) p (x,y),(x+1,y) = (c -x)y (c + s)s µ for x ≤ c -(x,y),(x-1,y) = x(s -y) (c + s)s(1 -µ) for x ≥ (x,y),(x-1,y+1) = x(s -y) (c + s)s µ for x ≥ 1 and y ≤ s -1.

2 ( 2 (Fig. 9 .

 229 Fig. 9. Percentage of the expected number of safe clusters (relation (18)) as a function of the rounds number n for both protocols, for two different initial states X 0 (Section 4.3.1). In these experiments, ℓ = 100, c = 10, s = 20, and µ = 25%.

( 18 )

 18 If N denotes the stationary number of safe clusters, we haveE(N ) =ℓπ A ✶ for a constrained adversary 0 for a non constrained adversary[START_REF] Douceur | The sybil attack[END_REF]

  {•••} represents the indicator function. In all other cases, transition probabilities are null.

4.3. Comparison of both Protocols in a Non Constrained Adversarial Environment As described in Section 4.1 the Markov chain X associated with Protocol 1 is reducible and the states of A are transient, which means that matrix I -P A is invertible, where I is the identity matrix of dimension |A|. Recall that B is an absorbing class, i.e. P BA = 0. Similarly, as described in Section 4.2, Markov chain X associated with Protocol 2 is reducible, the states of A and C are transient and subset D is a closed subset.

  5.3. Comparison of both Protocols in a Constrained Adversarial Environment By proceeding as in Section 4.3.3, we investigate the behavior of both protocols during their successive n-th sojourn time in A and B. Each Markov chain X is irreducible and aperiodic since at least one state has a transition to itself. For n ≥ 1, we denote by respectively T B,n the time spent by Markov chain X associated with Protocol i during its n-th sojourn in respectively subsets A and B.

			(i) A,n and T	(i)
	Expectations of T	(i) A,n and T	(i) B,n are respectively given for i = 1, 2 by

E. Anceaume, F. Brasileiro, R. Ludinard, B. Sericola, and F. Tronel

E. Anceaume, F. Brasileiro, R. Ludinard, B. Sericola, and F. Tronel

E. Anceaume, F. Brasileiro, R. Ludinard, B. Sericola, and F. Tronel

E. Anceaume, F. Brasileiro, R. Ludinard, B. Sericola, and F. Tronel

† Supported by the Direction Générale des Entreprises -P2Pim@ges project

)) as a function of the n-th sojourn time (Relation ( 15)). We have α = β, c = 10, s = 20 and µ = 25%. A, 1)

Second Protocol

(b) Succession of E(T (i)

A,n ) and E(T

) as a function of the rounds number. We have α = β, c = 10, s = 20 and µ = 25%. Proof. For space reason, the proof appears in [START_REF] Anceaume | Dependability evaluation of cluster-based distributed systems[END_REF].

Theorem 1 is quite interesting as it shows that the steady state of the system which is described by the stationary distribution π is exactly the same for both protocols, and that this distribution is equal to distribution β (independently from the initial distribution). At a first glance, we could guess that this phenomenon is due to the fact that the Markov chain X is the tensor product of two independent Markov chains. However, this is clearly not the case as the behavior of red balls in C depends on the behavior of red balls in S. This holds for both protocols. The stationary availability of the system defined by the long run probability to be in safe states is denoted by P safe and is given by

This probability can also be interpreted as the long run proportion of time spent in safe states. Note that the stationary distribution does not depend on the size of S.

Robustness of the Overlay Network

We now show that by inducing global churn, we can preserve the safety of the system. We consider that we have ℓ identical and independent Markov chains X (1) , . . . , X (ℓ) on the same state space Ω = A ∪ B, with initial probability distribution α and transition probability matrix P . Each Markov chain X (i) models a particular cluster of peers and, for n ≥ 0, N n represents the number of safe clusters after the n-th round, i.e. the number of Markov chains being in subset A after the


Emmanuelle Anceaume
email: anceaume@irisa.fr

Bruno Sericola
email: sericola@inria.fr

Modeling and Evaluating Targeted Attacks in Large Scale Dynamic Systems

Keywords: Clusterized P2P Overlays, Adversary, Churn, Collusion, Markov chains

In this paper we consider the problem of targeted attacks in large scale peer-to-peer overlays. These attacks aimed at exhausting key resources of targeted hosts to diminish their capacity to provide or receive services. To defend the system against such attacks, we rely on clustering and implement induced churn to preserve randomness of nodes identifiers so that adversarial predictions are impossible. We propose robust join, leave, merge and split operations to discourage brute force denial of services and pollution attacks. We show that combining a small amount of randomization in the operations, and adequately tuning the sojourn time of peers in the same region of the overlay allows first to decrease the effect of targeted attacks at cluster level, and second to prevent pollution propagation in the whole overlay.

I. INTRODUCTION

In this paper we consider the problem of targeted attacks in large scale peer-to-peer systems. These attacks aimed at exhausting key resources of targeted hosts to diminish their capacity to provide or receive services [START_REF] Naoumov | Exploiting p2p systems for ddos attacks[END_REF], at preventing data indexed at targeted nodes from being discovered and retrieved by poisoning their routing tables, or simply at rerouting or dropping messages addressed to targeted nodes. Such malicious behaviors have led to the proposition of malicious-resilient overlay systems (e.g., [START_REF] Fiat | Making chord robust to byzantine attacks[END_REF], [START_REF] Baumgart | S/kademlia: A practicable approach towards secure key-based routing[END_REF], [START_REF] Anceaume | PeerCube: an hypercube-based p2p overlay robust against collusion and churn[END_REF]). In all these systems, it is assumed that at any time, and anywhere in the overlay, the proportion of compromised peers is bounded and known. Unfortunately, targeted attacks violate such an assumption. It has been shown that peer-to-peer overlays can survive these attacks only if malicious nodes are not able to isolate honest nodes within the system. This is achieved by i) preserving randomness of nodes identifiers [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF], and ii) limiting the period of time where nodes can stay at the same position in the overlay. Induced churn has been shown to be a fundamental ingredient to preserve randomness. Churn is classically defined as the rate of turnover of peers in the system [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF], and thus induced churn refers to the general idea of forcing peers to move within the system. Several strategies based on this principle have been proposed. Most of them are based on locally induced churn. However either they were proven incorrect or they involve a too high level of complexity to be practically acceptable [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF]. Some other strategies, based on globally induced churn, force each node to periodically leave and re-join the system. This may be enforced through nodes limited lifetime in the system. If not properly handled, these solutions keep the system in an unnecessary hyper-activity, which increases accordingly the impact of churn.

In the present work, we investigate adversarial strategies that aim at isolating honest nodes in cluster based overlays, and we present an analytical study of the long term behavior of the system. Our analysis shows that i) by limiting the sojourn time of nodes at the same position in the overlay and ii) by introducing randomness in the operations of the overlay, pollution attacks are severely reduced at cluster level and do not propagate to the whole overlay. A preliminary work [START_REF] Anceaume | Analytical study of adversarial strategies in clusterbased overlays[END_REF] investigates adversarial strategies in the specific context where the sequence of join and leave events is well interleaved. In this paper we extend this preliminary work to a general context in which clusters size varies with churn and thus, undergo merge and split operations. To the best of our knowledge, this is the first work that has conducted such a study.

The remainder of this paper is as follows: In Section II, we present existing works that focus on making structuredbased overlays robust against attacks. In Section III we briefly describe the main features of cluster-based overlays, and present the assumptions made in this work. Section IV describes the robust operations implemented in the overlay. Then, in Section V, we specify the strategy the adversary adopts to perform targeted attacks in the system. The adversarial behavior is modeled and its impact at both cluster level and at the overlay level are respectively studied in Sections VI and VIII. Section IX concludes.

II. RELATED WORK

Different approaches have been proposed to face adversarial setting, each one focusing on a particular adversary strategy. Regarding eclipse attacks, a very common technique, called constrained routing table, consists in selecting neighbors based on their identifiers so that all of them are close to some particular points in the identifier space [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF]. Such an approach has been implemented into several overlays (e.g., [START_REF] Ratnasamy | A scalable content-addressable network[END_REF], [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], [START_REF] Druschel | Past: A large-scale, persistent peer-to-peer storage utility[END_REF]). Another defense against those attacks comes from the observation that during eclipse attacks, the degree of attackers is much higher than the average degree of peers in the overlay. Addressing such attacks consists in bounding peers degrees. Singh et al. [START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF] propose to anonymously audit peers to continuously check the bounded degree of peers. Results of their experimentation show that their solution is effective in an overlay with low to moderately high churn. More generally, the seminal works on DHT routing security by Castro et al. [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF] and Sit and Morris [START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF] combine routing failure tests and redundant routing as a solution to ensure robust routing. Their approach has then been successfully implemented in different structured-based overlays (e.g., [START_REF] Fiat | Making chord robust to byzantine attacks[END_REF], [START_REF] Anceaume | PeerCube: an hypercube-based p2p overlay robust against collusion and churn[END_REF], [START_REF] Hildrum | Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks[END_REF]). In all these above cited works, it is assumed that at any time, and anywhere in the overlay, the proportion of compromised peers is bounded and a priori known. It allows powerful building blocks such as Byzantine tolerant agreement protocols to be used among peers subsets [START_REF] Fiat | Making chord robust to byzantine attacks[END_REF], [START_REF] Anceaume | PeerCube: an hypercube-based p2p overlay robust against collusion and churn[END_REF]. When such an assumption does not hold, additional mechanisms are needed. Awerbuch et al [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF] propose the Cuckoo&flip strategy. This strategy consists in introducing local induced churn upon each join and leave operation. This strategy prevents malicious peers from predicting what is going to be the state of the overlay after a given sequence of join and leave operations. Subsequently to this work, experiments have been conducted to check the feasibility of global induced churn. These experiments assume that the overlay is populated by no more than 25% of compromised peers [START_REF] Condie | Induced churn as shelter from routing-table poisoning[END_REF], or that the topology of the overlay is static [START_REF] Anceaume | Analytical study of adversarial strategies in clusterbased overlays[END_REF].

III. SYSTEM MODEL

A. Model of the Network.

We consider a dynamic system populated by a large collection of peers in which each peer is assigned a unique and permanent random identifier from an m-bit identifier space. Peer identifiers (simply denoted ids in the following) are derived by applying some standard strong cryptographic hash function on peers intrinsic characteristics (see below). The value of m (128 for the standard MD5 hash function) is chosen to be large enough to make the probability of identifiers collision negligible. The system is subject to churn, which is classically defined as the rate of turnover of peers in the system [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF]. For scalability reasons, each peer knows only a small set of peers existing within the system and this knowledge generally varies according to the activity of the system. This set is typically called the node's local view. The particular algorithm used by peers to build their local view and to route messages induces the resulting overlay topology. Structured overlays (also called Distributed Hash Tables (DHTs)) build their topology according to structured graphs (e.g., hypercube, torus) as proposed in [START_REF] Ratnasamy | A scalable content-addressable network[END_REF], [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], [START_REF] Druschel | Past: A large-scale, persistent peer-to-peer storage utility[END_REF], [START_REF] Plaxton | Accessing nearby copies of replicated objects in a distributed environment[END_REF], [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the XOR metric[END_REF]. Peers self-organize within the structured graph according to a distance function D based on peers ids, plus possibly other criteria such as geographical distance. Each data is assigned a unique identifier, called key, selected from the same m-bit identifiers space. Each peer p owns a fraction of all the data items of the overlay. The mapping derives from the distance function D. In cluster-based overlays, clusters of peers substitute for peers at the vertices of the structured graph. Each vertex of the structured graph is composed of a set or cluster of peers. Peers join the clusters according to distance D. For instance in eQuus [START_REF] Locher | eQuus: A provably robust and locality-aware peer-to-peer system[END_REF], peer p joins the (unique) cluster whose members are geographically the closest to p, while in PeerCube [START_REF] Anceaume | PeerCube: an hypercube-based p2p overlay robust against collusion and churn[END_REF], p joins the (unique) cluster whose label is a prefix of p's identifier. Clusters in the overlay are uniquely labelled. Size of each cluster is both lower and upper bounded. The lower bound, named C in the following, usually satisfies some constraint based on the assumed failure model. The upper bound, that we will call S max , is typically in O(log N ) where N is the current number of peers in the overlay, to meet scalability requirements. Once a cluster size exceeds S max , this cluster splits into two smaller clusters, each one populated with the peers that are closer to each other according to distance D. Once a cluster undershoots its minimal size C, this cluster merges with the closest cluster in its neighborhood.

In the present work we assume that at cluster level, peers are organized as core and spare members. Members of the core set are primarily responsible for handling messages routing and clusters operations. Management of the core set is such that its size is maintained to constant C. Spare members are the complement number of peers in the cluster. Size s of the spare set is such that s ≤ ∆ where ∆ = S max -C. In contrast to core members, spare members are not involved in any of the overlay operations. Rationale of this classification is two-fold: first it limits the management overhead caused by the natural churn present in typical overlay networks through the spare set management. Second it allows to introduce the unpredictability required to deal with malicious attacks through a randomized core set generation algorithm as shown in the sequel.

In the following we assume that join and leave events have an equal chance to occur in any cluster.

B. Model of the Adversary

A fundamental issue faced by any practical open system is the inevitable presence of peers that try to manipulate the system by exhibiting undesirable behaviors [START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF]. Such peers are classically called malicious or Byzantine. Malicious peers can devise complex strategies to prevent peers from discovering the correct mapping between peers and data keys. They can mount Sybil attacks [START_REF] Douceur | The sybil attack[END_REF] (i.e., an attacker generates numerous fake peers to pollute the system), they can do routing-table poisoning (also called eclipse attacks [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF], [START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF]) by having honest peers redirecting outgoing links towards malicious ones, or they can simply drop or re-route messages towards other malicious peers. They can magnify their impact by colluding and coordinating their behavior. We model these strategies through a strong adversary that controls these malicious peers. A strong adversary is an adversary allowed to deviate arbitrarily far from the protocol specification. We assume that the adversary has large but bounded resources in that it cannot control more than a fraction µ (0 < µ < 1) of malicious peers in the whole network. Note that in the following we make a difference between the whole universe and the overlay. The universe U encompasses all the peers that at some point may participate to the overlay (i.e. 2 m peers), while the overlay contains at any time the subset of participating peers (whose size is equal to N ). Thus, while µ represents the assumed fraction of malicious peers in the network, the goal of the adversary is to populate some parts of the overlay with a larger fraction of malicious peers in order to subvert the correct functioning of the overlay. Finally, a peer which always follows the prescribed protocols is said to be honest. Note that honest peers cannot a priori distinguish honest peers from malicious ones.

C. Security Schemes

We assume the existence of a public key cryptography scheme that allows each peer to verify the signature of each other peer. We also assume that correct peers never reveal their private keys. Peers ids and keys (private and public) are acquired via a registration authority. When describing the protocols, we ignore the fact that messages are signed, and recipients of a message ignore any message that is not signed properly. We also use cryptographic techniques to prevent a malicious peer from observing or unnoticeably modifying a message sent by a correct peer. However a malicious peer has complete control over the messages it sends and receives.

D. Limited Sojourn Time and Random Distribution of ids

As said in the Introduction, the two fundamental properties that prevent peers isolation are the guarantee that the distribution of peers identifiers is random, and that peers cannot stay forever at the same position in the system [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF]. Both properties have been analytically proven assuming that the region size is kept constant [START_REF] Anceaume | Analytical study of adversarial strategies in clusterbased overlays[END_REF].

To implement both limited sojourn time of the nodes at the same place in the overlay and unpredictable identifier assignment in a cluster-based overlay, we propose to limit the lifetime of peers identifiers and to randomize their computation. Specifically, peers identifiers are initially generated based on certificates acquired at trustworthy Certification Authorities (CAs). Initial identifiers (denoted id 0 ) are generated as the result of applying a hash function H to some of the fields of a X.509 [START_REF] Housley | Internet x.509 public key infrastructure certificate and crl profile[END_REF] certificate. To enforce all peers, including malicious ones, to leave and rejoin the system from time to time, we add the creation date t 0 to the fields that appear in the peer certificate that will be hashed to generate the peer identifier (note that by the properties of hash functions, this guarantees that peers identifiers are unpredictable). We limit the lifetime peers identifier through an incarnation number. The current incarnation k of any peer is given by the following expression k = ⌈(t -t 0 )/L⌉, where t 0 is the initial creation time of the peer's certificate, t is the current time, and L is the length of the lifetime of peers incarnation. Thus, the k th incarnation of a peer p expires when p local clock reads t 0 + kL. At this time p must rejoin the system using its (k + 1) th incarnation. The t 0 parameter is one of the fields in the peer's certificate and since certificates are signed by the CA, it cannot be unnoticeably modified by a malicious peer. Moreover, a certificate commonly contains the public key of the certified entity. This way, messages exchanged by the peers can be signed using the sender private key, preventing malicious peers from unnoticeably altering messages originated from other peers in the system. Messages must contain the certificate of their issuer, so as to allow recipients to validate them. 1Therefore, at any time, any peer can check the validity of the identifier of any other peer q in the system, by simply calculating the current incarnation k of peer q and generating the corresponding identifier. Specifically, the current identifier of peer q, denoted in the following as id q , is calculated by hashing q initial identifier (id 0 q ) with the current incarnation k of q, i.e., id q = H(id 0 q × k). This leads to the following property.

Property 1 (Limited Sojourn Time): Let D be some cluster of the system and p some peer in the overlay. Then q belongs to D at time t if only if id q matches the label of D according to distance D (we say that q is valid for D).

If some peer p detects that the id of one of its neighbors q is not valid then it cuts its connection with q. Peer q may re-join the overlay by triggering a join operation at cluster D ′ such that id q is valid for D ′ . Note that because clocks are loosely synchronized, it is possible that a correct peer is still using its id for incarnation k when other correct peers would expect it to be in incarnation k + 1. To mitigate this problem, we assume that any correct peer may have two subsequent valid incarnation numbers, for a fixed grace window W of time that encompasses the expiration time of an incarnation number (W is the maximum deviation of the clocks of any two correct peers). More precisely, at any time t, both incarnation k and k ′ are valid, where k = ⌈(t -W/2-t 0 )/L⌉, and k ′ = ⌈(t+W/2-t 0 )/L⌉. Thus, although each peer p has, at any time t, a single incarnation number that it uses to define its current id, other peers calculate two possible incarnation numbers for p. These are frequently equal, but may differ when p's local time is close to the expiration time of its current/last incarnation.

IV. OPERATIONS OF THE OVERLAY

To protect the system against the presence of malicious peers in the overlay, we propose to take advantage of peers role separation at cluster level to design robust operations.

Briefly, the join operation is designed so that brute force denial of service attacks are discouraged. The Leave operation impedes the adversary from predicting what is going to be the composition of the core set after a given sequence of join and leave events triggered by its malicious peers. Finally, as both merge and split operations induce topological changes in the overlay, and more importantly may have an influence on the subset of the identifier space the adversary may gain control over,2 these operations have been designed so that the adversary has, in expectation, no interest to trigger them. Specifically,

• join(p): when a peer p joins the system, it joins the spare set of the closest cluster in the system (according to distance D). Core members of this cluster update their spare view to reflect p's insertion (note that the spare view update does not need to be tightly synchronized at all core members). • leave(p): When a peer p leaves a cluster either p belongs to the spare set or to the core set. In the former case, core members simply update their spare view to reflect p's departure, while in the latter case, the core view maintenance procedure is triggered. This procedure consists in replacing k -1 randomly chosen members of the core set with k peers randomly chosen from the whole cluster, where 1 ≤ k ≤ C (recall that C is the size of the core set, cf. Section III-A). These four operations make up the overlay protocol. In the following protocol k will refer to as these four operations with 1 ≤ k ≤ C the amount of randomization of the core view maintenance procedure of the leave operation.

V. SPECIFICATION OF THE ADVERSARIAL BEHAVIOR

Based on the operations described in the previous section, we investigate how malicious peers could proceed to compromise correctness of a targeted cluster. Clusters correctness is jeopardized as soon as a quorum of its core members are malicious. It is well known that a necessary and sufficient condition to prevent agreement among a set of nodes is that strictly more than a third of the population set is malicious [START_REF] Lamport | The byzantine generals problem[END_REF]. In our context, cluster D is said to be polluted if its core set is populated by more than a quorum c of malicious peers where c = ⌊(C -1)/3⌋ malicious peers. Otherwise, this cluster D is said to be safe.

A. Increasing Global Representation of Malicious Identifiers

As a consequence of assigning an initial unique random id from an m-bit identifier space to peers and of periodically pushing peers to random regions in the overlay, the strategy of the adversary to increase the global representation of malicious identifiers is a combination of the following three actions.

First, the adversary maximizes the number of malicious peers that sit in the whole overlay. By doing so, the adversary augments the likelihood for its malicious peers to join targeted clusters. For those peers which cannot immediately enter targeted clusters (because their current ids do not match the targeted clusters label), but rather join different clusters, the goal of the adversary is to pollute these clusters as well. This augments the subset of identifiers space the adversary has gained control over, and thus empowers it to progressively surround the targeted clusters.

Second, the adversary may in some specific cases decide to trigger a leave operation for some malicious peer in a given core set if the outcome of the operation increases the global representation of malicious identifiers in that set. Indeed, if by having a malicious peer leaving the core set of a cluster, the likelihood that the outcome of the core set maintenance process strictly increases the number of malicious peers in the renewed core set, then the adversary triggers a leave operation. Formally, Rule 1 (Adversarial Leave Strategy): Let D be a cluster such that at time t its core set C contains 0 < x ≤ c valid malicious peers and its spare set contains y > 1 valid malicious peers. At time t the adversary triggers a leave(p) operation for malicious peer p in C if, for a given small positive threshold ν

x-1+min(k,y) j=x+1 P exactly j malicious peers ∈ C

after the leave operation > 1-ν. (1)
Recall that k is the amount of randomization of the leave operation. Note that for k = 1, Relation (1) is never satisfied. Thus in this specific situation, there is no incentive for malicious peers to trigger voluntary leaves. For k > 1, malicious peers collude together to force the one among them (whose id will expire the soonest) to leave the core.

As the experiments will show, decreasing the amount of randomization of the leave operation provides the best strategy against targeted attacks.

Finally, once the adversary has succeeded in polluting a cluster D, he must minimize the likelihood that D switches back to a safe state. Switching to a safe state may occur subsequent to either the core maintenance procedure, the merge, or the split operations. The two latter cases are detailed in the following section. Regarding the former case, the adversary can bias the core set maintenance procedure by replacing the left peer with a (valid) malicious peer from the spare set if any. On the other hand, if the spare set does not contain any malicious peers then the adversary has no choice other than choosing a honest peer (otherwise clusters in D vicinity will quickly detect that the size of D core set is less than C).

B. Decreasing the Occurrence of Topological Operations

So far we have seen that the adversary triggers leave operations for its malicious peers if with high probability it increases the population of malicious peers in the core set. However, the adversary will trigger such departures only if this does not lead the cluster to merge with another cluster. Indeed, by construction of the merge operation (cf. Section IV), when D core members trigger a merge with their closest neighbor D ′ then all D members are pushed to the spare set of the new created cluster D ′′ while core members of D ′ keep their status of core members in D ′′ . This clearly deters the adversary from triggering merge operations. We have also seen that to gain the control of clusters, the strategy of the adversary is to maximize the number of malicious peers in both the core and the spare sets of any cluster. However once a cluster is polluted, the adversary has no interest to let this cluster grow in such a way that this cluster will undergo a split operation. Indeed, the outcome of a split operation cannot increase the subset of identifiers space the adversary has gained control over-at best, it keeps it the same. Thus when a polluted cluster is close to split, the adversary acts so that no join operations are triggered. Note that the adversary can prevent honest peers from joining D whenever s > 1. This guarantees that D will not grow because of honest peers, while ensuring that D will not undergo a merge operation as much as possible. Specifically, Rule 2 (Adversarial Join Strategy): Let D be a cluster such that at time t its core set contains ℓ > c valid malicious peers. Any join event issued by peer q and received at D at time t is discarded if (q is honest and s > 1) or (s = ∆ -1). Recall that ∆ represents the maximal size of the spare set (c.f. Section III-A).

A possible implementation of Rule 2 is as follows: upon receipt of a join event from an honest peer q, the adversary asks the malicious core members to positively acknowledge q, so that q does not detect that D is polluted, however the associated join operation is not triggered.

To summarize, the strategy of the adversary is to maximize the whole subset of the identifiers space it has gained control over. This is achieved by first never asking its malicious peers to leave their cluster except if either Property 1 does not hold or Rule 1 holds, and second by having the maximal number of malicious peers join the system except if Rule 2 holds.

VI. MODELING THE ADVERSARIAL STRATEGY

The evolution of any given cluster D follows both the overlay protocol protocol k (cf. Section IV) and the strategy of the adversary (cf. Section V). To analyze the impact of the adversarial strategy, we make a difference between join (resp. leave) events and join (resp. leave) operations. Indeed, from above, the number of leave and join events issued at malicious peers is greater than or equal to the number of the associated leave and join operations.

We model the effect of join and leave events using a homogeneous discrete-time Markov chain denoted by X = {X n , n ≥ 0}. Markov chain X represents the evolution of the number of malicious peers in both the core set and the spare set of cluster D. The state space Ω of X is defined by

Ω = {(s, x, y) | 0 ≤ s ≤ ∆, 0 ≤ x ≤ C, 0 ≤ y ≤ s}.
For n ≥ 1, the event X n = (s, x, y) means that, after the n-th transition (i.e., the n-th join or leave event), the size of the spare set is equal to s, the number of malicious peers in the core set is equal to x and the number of malicious peers in the spare set is equal to y. In the remaining of the paper, the initial probability distribution of X is denoted by α. The transition probability matrix M of X is detailed below.

We define a state as polluted if in this state the core set contains more than c = ⌊(C -1)/3⌋ malicious peers. Conversely, a state that is not polluted is said to be safe.

The subset of safe states, denoted by S, is defined by S = {(s, x, y) | 0 < s < ∆, 0 ≤ x ≤ c, 0 ≤ y ≤ s}, while the subset of polluted states, denoted by P , is defined by P = {(s, x, y) | 0 < s < ∆, c + 1 ≤ x ≤ C, 0 ≤ y ≤ s}. The system alternates between safe and polluted states until entering closed states. Closed states represent the logical disappearance of cluster D from the graph. This occurs when either D splits into two smaller clusters (i.e., its spare set has reached its maximal size ∆) or D merges with its closest neighbor (i.e., the size of its spare set has shrunk to 0). Three sets of closed states exist. The set of safe merge closed states A m S defined as

A m S = {(s, x, y) | (s = 0) ∧ (0 ≤ x ≤ c)}, the set of safe split closed states A ℓ S defined as A ℓ S = {(s, x, y) | (s = ∆) ∧ (0 ≤ x ≤ c)}
, and the set of polluted merge closed states A m P defined as

A m P = {(s, x, y) | (s = 0) ∧ (c + 1 ≤ x ≤ C)}.
Note that by Rule 2 the states such that s = ∆ and c + 1 ≤ x ≤ C are not reachable because the adversary strategizes to prevent a polluted cluster from triggering a split operation (cf. Section V-B). As a consequence the set of polluted split closed states is empty. Matrix P is partitioned with respect to the decomposition of

Ω = S ∪ P ∪ A m S ∪ A ℓ S ∪ A m P M =      MS MSP M SA m S M SA ℓ S M SA m P MP S MP M P A m S M P A ℓ S M P A m P 0 0 M A m S 0 0 0 0 0 M A ℓ S 0 0 0 0 0 M A m P     
where M U V is the sub-matrix of dimension |U | × |V | containing the transitions from states of U to states of V , with U, V ∈ {S, P, A m S , A ℓ S , A m P }. We simply write M U for M U U . Note that A m S , A ℓ S , and A m P are absorbing classes. In the same way, the initial probability distribution α is partitioned by writing α = (α

S α P α A m S α A ℓ S α A m P )
, where sub-vector α U contains the initial probabilities of states U ∈ {S, P, A m S , A ℓ S , A m P }. Figure 1 depicts an aggregated view of the states partition of process X. Computation of transition matrix M is illustrated in Figure 2. In this tree, each edge is labelled by a probability and each leaf represents the state of the cluster. This figure shows all the states that can be reached from state (s, x, y) and the corresponding transition probabilities. Transition probabilities depend on i) the type of operation that occurred (join or leave operation from the core or the spare set), ii) the type of peers involved in this operation (honest or malicious), and iii) the ratio of malicious peers already present in the core set. The probability associated with each one of these states is obtained by summing the products of the probabilities discovered along each path starting from the root to the leaf corresponding to the target state. For instance, the leftmost branch of the tree corresponds to the scenario in which some malicious peer wishes to join the polluted cluster D. By Rule 2, this peer successfully joins the cluster, leading to state (s + 1, x, y + 1). Now if we consider the rightmost branch in the tree, this represents the situation in which cluster D is polluted and one of its malicious core member p is no more valid. By Property 1, p leaves D, however as D is polluted, the adversary bias the core management procedure by replacing p with another malicious peer from D spare set. State (s -1, x, y -1) is reached. For space reasons, derivation of the transition probability matrix M is presented in [START_REF] Anceaume | Performance analysis of large scale peer-to-peer overlays using markov chains[END_REF].

Modeling and computation of both Property 1 and Rule 1 are as follows. Regarding Property 1, let d be the probability (per unit of time) that the limited lifetime of some peer p has not expired. Hence d is homogeneous to a frequency, and d × ∆t represents the probability that the lifetime of a given peer identifier has not expired during ∆t units of time. From a practical point of view, we model the limited lifetime of a peer identifier as an exponential decay process whose halftime constant (denoted t 1/2 ) is related to d by the standard relation t 1/2 = ln 2/(1 -d). Consequently, the value of L (cf. III-D) might be calibrated so that 99% of a given population has decayed after L unit of time. Setting L = 6.65 × t 1/2 satisfies this requirement 3 . Then the probability that for all the peers belonging to a set of size z Property 1 holds is equal to d z . Regarding Rule 1, let q(k, ℓ, u, v) be the probability of getting u red balls when k balls are drawn without replacement from an urn containing v red balls and ℓ -v white balls. We have

q(k, ℓ, u, v) = v u ℓ-v k-u / ℓ
k . q(.) is referred to as the hypergeometric distribution. Let (s, x, y) be the current state of the Markov chain associated to cluster D. Then Rule 1 holds if the chain enters one of the following states (s -1, x + 1, y -2), . . . , (s -1, x ′ , y ′ ), with

x ′ = x + y -1 and y ′ = 0 if k ≥ x + y -1 otherwise x ′ = k and y ′ = x + y -1 -k, right
after the voluntary departure of one malicious valid core member with probability 1 -ν. From the leave operation Relation (1) writes as

imax i=i 0 jmax j=i+2 q(k -1, C -1, i, x -1)q(k, s + k -1, j, y + i) > 1 -ν. (2)
where i 0 = max(0, k-1-(C -x)), i max = min(k-1, x-1) and j max = min(k, y + i). In Figure 2, notation "1 {(2)} " means that Relation (2) holds.

VII. STUDY OF A CLUSTER BEHAVIOR IN AN ADVERSARIAL SETTING

In this section, we study the behavior of a cluster according to the power of the adversary, the frequency of the induced churn, and the amount of randomization k introduced in protocol k .

A. Initial Distributions

In the experiments conducted for this work, we consider two initial distributions. The first one, which we denote by β, consists in assuming that the initial size of the spare set (denoted as s 0 ) is uniformly distributed on {1, . . . , ∆ -1}. The initial number C 0 of malicious peers in the core set and the one S 0 in the spare set both follow a binomial distribution. The initial state X 0 is thus defined by X 0 = (s 0 , C 0 , S 0 ). Assuming that C 0 and S 0 are independent, we get for x = 0, . . . , C and y = 0, . . . , s 0

β(x, y) = P{C 0 = x, S 0 = y} = C x µ x (1 -µ) C-x s 0 y µ y (1 -µ) s0-y . (3)
The second one, that we denote by δ, consists in starting from state (s 0 , 0, 0), that is the state free from malicious peers, where s 0 = ⌊∆/2⌋. We have

δ(s0, x, y) = 1 {x=0,y=0} . (4)

B. Time Spent by Protocol k in Safe States

As described in Section VI the Markov chain X is reducible, the subset of states S and P are transient and the subsets A m S , A ℓ S and A m P are closed subsets. We start our study by first investigating the distribution of T (k) S which counts the total time spent by protocol k in the subset of safe states S before absorption. Specifically T (k) S = ∞ n=0 1 {Xn∈S} . Following the results in [START_REF] Sericola | Closed form solution for the distribution of the total time spent in a subset of states of a Markov process during a finite observation period[END_REF], the expectation of T (k) S is given by

E(T (k) S ) = v(I -R) -1 ✶. (5)
where v = α S + α P (I -M P ) -1 M P S and R = M S + M SP (I -M P ) -1 M P S .

C. Time Spent by Protocol k in Polluted States

In the same way, its expectation is given by

E(T (k) P ) = w(I -Q) -1 ✶, (6)
where

w = α P + α S (I -M S ) -1 M SP and Q = M P + M P S (I -M S ) -1 M SP .
Figure 3 compares the expected number of operations spent in safe and polluted states before absorption for two protocols, protocol 1 and protocol C , as a function of µ, d and the two initial distributions δ and β. We have only detailed protocols 1 and C (here C = 7) as we have observed that they bound the performance of the other ones (here, the 5 other ones). The reason is that protocol 1 implements the least amount of randomization of the leave operation while protocol C implements the largest one. This will allow us to illustrate the fact that, counterintuitively, increasing the amount of randomization of the operations does not make them necessarily more resilient to strong adversaries.

Lessons Learnt from these Experiments: The first lesson that we can draw from this figure is the impact of the initial distribution on the behavior of the cluster. When this distribution equals δ (i.e., the cluster is initially free from malicious peers), the number of operations run in safe states is much larger than the one spent in polluted ones for both protocols. This holds even for very large values of both µ and d. This comes from the combined effects of both the join and leave operations. The former one prevents new peers to directly belong to the core set, while the latter one randomizes the core set population, demanding accordingly a certain amount of time for the adversary to successfully pollute a cluster. On the other hand, when starting with α = β, both the core and the spare sets are initially populated with malicious peers (proportionally to µ). Hence this requires less effort for the adversary to gain control of the cluster.

The second lesson relates to the impact of randomization on cluster resiliency. For a given initial distribution α, protocol 1 always outperforms protocol C , that is for both a given µ and a given d, E(T ). This shows that increasing the amount of randomization does not make the protocols more resilient to targeted attacks.

The third lesson is linked to peers identifiers lifetime d. For increasing values of d, the expected time spent in safe clusters strictly increases, while the one spent in polluted clusters slightly decreases, for a fixed µ. This is explained by the fact that malicious peers can stay longer in the cluster, increasing accordingly their proportion in the cluster up to pollution. Once polluted, the adversary prevents split operations from occurring. This increases accordingly the time spent in polluted states and thus the lifetime of the cluster. Clearly this phenomenon is more noticeable for larger values of µ. Now for d close to 1, malicious peers are allowed to stay almost forever in their cluster. This enables them to quickly gain the quorum in their cluster, and thus prevent any safe operation to be triggered even for very small values of µ (see Table I). This clearly confirms that churn is a fundamental ingredient to defend against targeted attacks.

Finally, it is interesting to remark that in a failure free environment (µ = 0), we have E(T

(k) S ) + E(T (k) P ) = ⌊∆ 2 /4⌋ = 12.
Actually ⌊∆ 2 /4⌋ corresponds to the maximal expected number of steps before absorption in a one dimensional random walk with borders (here, ∆ is the length between the two borders).

D. Successive Times Spent by Protocol k in Polluted and Safe States

A deeper investigation of protocol k can be conducted by studying the duration and frequency of successive times spent in subsets S and P . For n ≥ 1, we denote by T (k) S,n (resp. T (k) P,n ) the distribution of the time spent by the Markov chain X during its n-th sojourn in subset S (resp. P ). Thus the total time spent in subset S (resp. P ) before reaching subsets A S and A P is given by

T (k) S = ∞ n=1 T (k) S,n and T (k) P = ∞ n=1 T (k) P,n .
From [START_REF] Sericola | Sojourn times in Markov processes[END_REF], we have for n ≥ 1 and ℓ ≥ 0

E(T (k) S,n ) = vG n-1 (I -M S ) -1 ✶, ( 7
)
where v is defined in Relation [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF] and G = (I -M S ) -1 M SP (I -M P ) -1 M P S , and

E(T (k) P,n ) = wH n-1 (I -M P ) -1 ✶, ( 8
)
where w is defined in Relation 6 and H = (I -M P ) -1 M P S (I -M S ) -1 M SP .

M = T R m S R ℓ S R m P 0 * * * with T = MS MSP MP S MP with R v U = M SA v U M P A v U with U ∈ {S, P } and v ∈ {m, ℓ},
then starting from an initial distribution α = (α T 0 0 0), with α T = (α S α P ) then the probability p(A ℓ S ) for Markov chain X to be absorbed in states A ℓ S is

p(A ℓ S ) = αT (I -T ) -1 R ℓ S ✶. (9)
A similar computation gives the probabilities p(A m S ) and p(A m P ) to be respectively absorbed in states A m S and A m P . Figure 4 shows these different probabilities of absorption for protocol 1 with the initial distribution α = δ (on the left graph) and α = β (on the right graph). Clearly in absence of adversarial behavior (µ = 0), the cluster remains safe until it splits or merge, and both operations are equiprobable. Actually, we see that p(A m S ) = 0.57 and p(A ℓ S ) = 0.43. This comes from the fact that the initial size s 0 of the spare set is equal to ⌊∆/2⌋ = ⌊7/2⌋ = 3 (cf. Section VII-A), and thus the probability to reach a merge safe state equals 1 -3/7 ≃ 0.57, and thus a split safe state equals 0.43. Thus after some initial period of growth, the topology of the overlay is stable. Let us now observe the influence of the adversary on the probabilities of absorption. For a given µ, the probability for a safe cluster to split increases with larger values of d. This confirms the results described above: the population of the cluster increases as malicious peers trigger less leave operations than join operations. However, despite the fact that malicious peers stay longer in the cluster, for α = δ, the probability for the cluster to merge in a polluted state is very small (strictly less than 8%) even for very large values of both µ (e.g., µ = 30%) and d (e.g., d = 90%). These results are of utmost importance as they show that it is very improbable that polluted clusters manage to contaminate the other clusters of the system. As a consequence this fault-containment feature makes unlikely the probability for a cluster to start in a state in which the population of malicious peers is non negligible, that is from the initial distribution β. This is confirmed in the next Section.

VIII. MODELING THE ADVERSARIAL STRATEGY IN THE OVERLAY NETWORK

We now analyze the impact of the adversary on the whole overlay, and in particular the long run proportion of polluted clusters. We consider an overlay populated with n clusters D 1 , . . . , D n , and subject to join and leave events. Each cluster D i implements the same protocol protocol k . We assume that join and leave events are uniformly distributed throughout the overlay. Specifically, when a join or leave event occurs in the overlay it affects cluster D i with probability p i = 1/n. Thus we consider, for n ≥ 1, n Markov chains X (1) , . . . , X (n) identical to X, i.e. with the same state space Ω, the same transition probability matrix M and the same initial probability distribution α. However these chains are not independent since, at each instant, only one Markov chain is allowed to make a transition, this Markov chain being chosen with probability 1/n. We denote by N (n) S (m) and N (n) P (m) the respective number of safe and polluted clusters just after the m th join or leave event, i.e. the respective number of Markov chains that are in set S and in set P at instant m. More formally, these random variables are defined, for m ≥ 0, by

N (n) S (m) = n h=1 1 {X (h) m ∈S} and N (n) P (m) = n h=1 1 {X (h) m ∈P } .
It has been proved in [START_REF] Anceaume | Markov chains competing for transitions: Application to large scale distributed systems[END_REF] that the transient state probabilities of each Markov chain X (h) , h = 1, . . . , n at instant m ≥ 0 is given by the following theorem. Theorem 1: For every h = 1, . . . , n, m ≥ 0 and j ∈ Ω, we have

P{X (h) m = j} = m ℓ=0 m ℓ 1 n ℓ 1 - 1 n m-ℓ P{X ℓ = j} (10)
Note that this probability is independent of h since, even though the Markov chains are dependent, they behave identically and each of them is chosen with probability 1/n. The expectations of random variables E(N Let us then observe that the expected proportion of safe clusters is almost independent of d value. The same remark holds for the expected proportion of polluted clusters (even though because of the different y-axis scale used for this figure the phenomenon is not visually straightforward). This independence can be explained by the fact that the real churn dominates the induced churn (represented by parameter d).

IX. CONCLUSION

The main lessons learnt from this study is that (i) shuffling a single peer at a time (protocol 1 ) performs better than shuffling several peers (protocol k with k > 1). This is an interesting property because when k = 1, the implementation is reduced to a single Byzantine tolerant agreement algorithm run amongst spare members, compared to two such runs for k > 1 (an additional one is needed in the core set). (ii) By choosing an adequate value of L, i.e., the length of the lifetime of peers incarnation, it is possible to noticeably reduce the propagation of attacks in the whole system, and remarkably decrease the overhead of the induced churn at cluster level. This is another interesting result as it demonstrates that there is no need to keep the system in an hyper-activity to be resilient against targeted attacks. Pushing peers smoothly but to unpredictable regions of the system is sufficient.

  • split(D): when a cluster D has reached the conditions to split into two smaller clusters D ′ and D ′′ , core sets of both D ′ and D ′′ are built. Priority is given to core members of D and completion is done with randomly chosen spares in D. This random choice is handled through a Byzantine-tolerant consensus run among core members of D. Spares members of D ′ (resp. D ′′ ) are populated with the remaining spares members of D that are closer to D ′ than to D ′′ (resp. closer to D ′′ than to D ′ ).• merge(D ′ , D ′′ ): when some cluster D ′ has reached the conditions to merge (i.e., its spare set is empty), it merges with the closest cluster D ′′ to D ′ . The created cluster D is composed by a core set whose members are the core set members of D ′′ and by a spare set whose members are the union of the spare members of D ′′ and the core set members of D ′ .

Figure 1 :

 1 Figure 1: Aggregated view of Markov chain X. All the transient safe and polluted states are respectively represented by S and P . States A m S , A ℓ S and A m P represent all the closed safe and polluted states. For C = 7 and ∆ = 7, we have 288 states.

Figure 4 :

 4 Figure 4: p(A m S ), p(A ℓ S ) and p(A m P ) (cf. Relation (9)) respectively represented by red hatched, plain and blue hatched bars as a function of µ and d. In these experiments k = 1, C = 7, and ∆ = 7. We have α = δ for the left figure and α = β for the right one.

PP

  (m)) are then obtained in the following theorem.We denote by ✶ S (resp. ✶ P ) the column vector of dimension|S ∪ P | which ith entry is equal to 1 (resp. 0) if i ∈ S and 0 (resp. 1) if i ∈ P .Theorem 2: For every n ≥ 1 and m ≥ 0, we haveP{X ℓ ∈ S}It is well-known that the transient state probabilities of generic Markov chain X are given by P{X ℓ ∈ S} = αT ℓ ✶ S . (m)) is obtained using the same lines.The states of S ∪ P being transient, matrix T is substochastic and so is matrix T /n + (1 -1/n)I, for every n ≥ 1. We then have, for every n ≥ 1

Figure 5

 5 Figure 5 depicts the expected proportion of safe (left figure) and polluted (right figure) clusters after the m th transition, i.e., that is the m th join or leave operation,

Figure 5 :P

 5 Figure 5: E(N (n) S (m)) n and E(N (n) P (m)) n as a function of m for different values of n and d.

Note that there are means to optimize this procedure as for example by exchanging certificates during an initialization phase. However this is out of the scope of our paper.

Indeed, a merge operation doubles the subset of the identifier space a cluster is responsible for, while a split operation divides it per two.

We have that 6.65 ≥ ln 100/ ln 2.

(s,x,y) 0 < s < ∆ ( s + 1 ,x ,y + 1 ) ( s -1 ,x + 1 ,y -1 )

( s ,x ,y )

S ) as a function of µ and d. In these experiments k = 1, C = 7, ∆ = 7, and α = δ.

S,1 ) 12 12.085 11.890 11.570

S,2 ) 0 0.013 0.033 0.043

P,1 ) 0 0.099 0.558 1.611 Table II shows the expected duration of successive sojourn times in subsets S and P for protocol k , with k = 1. We can see that E(T

) and E(T

), that is the protocol does not alternate between safe and polluted states. This is very noticeable for small values of µ while a little bit less for larger ones.

E. Absorption Probabilities

Clusters eventually either split into two smaller clusters or merge with another cluster. An important question to be answered is whether or not split operations are more frequent than merge ones (for safe clusters), and whether or not polluted clusters merge more frequently than safe