Thibault Cholez

Isabelle Chrisment

Olivier Festor

Guillaume Doyen

Detection and mitigation of localized attacks in a widely deployed P2P network

Keywords: P2P networks, Distributed Hash Table, KAD, monitoring, security

Several large scale P2P networks operating on the Internet are based on a Distributed Hash Table . These networks offer valuable services, but they all suffer from a critical issue allowing malicious nodes to be inserted in specific places on the DHT for undesirable purposes (monitoring, distributed denial of service, pollution, etc.). While several attacks and attack scenarios have been documented, few studies have measured the actual deployment of such attacks and none of the documented countermeasures have been tested for compatibility with an already deployed network. In this article, we focus on the KAD network. Based on large scale monitoring campaigns, we show that the world-wide deployed KAD network suffers large number of suspicious insertions around shared contents and we quantify them. To cope with these peers, we propose a new efficient protection algorithm based on analyzing the distribution of the peers' ID found around an entry after a DHT lookup. We evaluate our solution and show that it detects the most efficient configurations of inserted peers with a very small false-negative rate, and that the countermeasures successfully filter almost all the suspicious peers. We demonstrate the direct applicability of our approach by implementing and testing our solution in real P2P networks.

1 Introduction P2P networks, and particularly Distributed Hash Tables (DHT), represent today a major share of the usage of the Internet involving several millions of users. Their scalability, robustness and small infrastructure costs make them a perfect architecture to support file sharing applications, among others. Fully distributed P2P networks based on Kademlia, like KAD or BitTorrent's Mainline DHT, have proven being capable to handle millions of connected peers.

Malicious peers behaving badly coupled with the absence of authority can seriously disturb and damage the services offered by such P2P systems. One of the major issues affecting large open P2P networks is the Sybil attack that inserts some peers controlled by a malicious entity at a specific location inside the DHT in order to take control of an entry. Such control over the P2P network lookup mechanism allows the attacker to perform many operations like monitoring the P2P traffic [START_REF] Steiner | Exploiting kad: possible uses and misuses[END_REF] [MRGS09] [START_REF] Cholez | Monitoring and Controlling Content Access in KAD[END_REF], polluting the content indexation [START_REF] Liang | The index poisoning attack in p2p file sharing systems[END_REF] [LMSW10] [START_REF] Cholez | Monitoring and Controlling Content Access in KAD[END_REF], eclipsing any content [START_REF] Steiner | Exploiting kad: possible uses and misuses[END_REF] or launching Distributed Denial of Service attacks [START_REF] Naoumov | Exploiting p2p systems for ddos attacks[END_REF] [SENB07a] [WTCT + 08]. Several attacks affecting DHTs are well described by several researchers (the Sybil attack and its localized version), but no study has ever tried to actually detect those attacks in a real system. Concerning the mitigation of such attacks, many solutions have been proposed but none of them is suitable to protect an already deployed P2P network. In fact, the different modifications proposed to obtain a safer identity management system need deep modifications of the P2P system design and break the backward compatibility between the protected clients and the others. For instance, enforcing the placement of peers in the DHT by using a hash of their IP address is impossible in the short run: the new ID scheme would result in a trustworthy network with the new clients on one side, and an untrustworthy network with older clients on the other side. Only a drop of the backward compatibility would make the solution efficient.

We propose in this article a novel and efficient approach to detect suspicious peer insertions in a widely deployed DHT and to mitigate the effects of their possible deviant activities. We quantify the suspicious peers present in the network through large scale explorations with a very accurate crawler and we analyze the position of peers to detect those that seem to collude or to target a DHT entry. These experiments highlight for the first time, a large number of suspicious peers affecting the P2P network. In a second step, we propose a solution to protect regular peers from these deviant activities (either monitoring activities or network attacks). Our solution is lightweight and efficient. It detects the suspicious peers based on the abnormal peers' ID distribution around the targeted entry. We design a countermeasure to this local detection, preventing malicious peers from receiving requests from the protected client. Besides being able to detect and mitigate attacks, our solution involves no network overhead and fits all the constraints of already deployed P2P networks based on a DHT. We prove its direct applicability through implementations and tests performed on real P2P networks.

This article is structured as follows. Section 2 contains the related work on KAD, including both the monitoring and the security of this network, and describes the solutions proposed against the Sybil attack. Section 3 presents our crawler and our analysis of the collected data to quantify the suspicious peers in this network. Section 4 describes and evaluates our solution to detect localized DHT attacks when a peer uses the DHT and the countermeasure to protect peers from suspicious nodes. Finally, Section 5 concludes the article and outlines our future work.

2 Related work 2.1 The KAD DHT KAD is a widely deployed (on average ∼3 million concurrent on-line users) P2P network based on the Kademlia distributed hash table routing protocol [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the XOR metric[END_REF]. It is implemented by the eMule and aMule clients which are used for file sharing.

Each KAD node has a 128 bits "KADID" determining its position in the DHT. All routing tasks are based on the XOR metric used to evaluate the distance between two peers or between a peer and a content. The routing table is composed of groups of contacts in a binary tree so that the closer an ID is to the current node, the better its knowledge of this part of the DHT is. The Search process is used to achieve any service on the DHT and is composed of two steps. The first step aims at finding the best possible peers near a DHT entry thanks to the lookup process. This routing is done in an iterative way with parallel lookups by using KADEMLIA REQ requests to discover new peers closer to the targeted DHT entry at each iteration.

When the list of the closest peers is set, the second step of the Search process sends KAD service requests to the 10 best peers found. As a file sharing application, the purpose of the KAD DHT is to index files and keywords. Each KAD node has a random 128 bits "KADID" determining its position in the DHT and the references of which it is in charge of. When sharing a file, the raw data and all the keywords associated with its name are hashed separately with a MD4 function generating an ID which is then published into the DHT (to simplify our example in Figure 1, we consider the KADIDs 32, 54 and 87, respectively for each keyword and the file). The peers indexing a file or a keyword are the 10 closest peers found by the publisher around the DHT entry after a DHT lookup. The double indexing scheme allows a peer to retrieve sources for a file, from a set of keywords. To publish a file, two types of service requests are sent:

the KADEMLIA2 PUBLISH KEY REQ requests: sent towards the hash of the keyword to link it to a file the KADEMLIA2 PUBLISH SOURCE REQ requests: sent towards the hash of the file to link it to a source (a peer sharing the file)

After accepting a publish request for a given resource, a peer is in charge of indexing this specific content and must answer any related search requests.

DHT security issues

The main well-known security issue of DHTs is the Sybil attack. As described by Douceur [START_REF] Douceur | The sybil attack[END_REF], it consists in creating a large number of fake peers called the "Sybils", and placing them in a strategic way in the DHT to take control over a part of it. Steiner et al successfully launched this attack on KAD [START_REF] Steiner | Exploiting kad: possible uses and misuses[END_REF]. They injected 2 16 Sybils from a single computer in a small zone of the DHT, so that they were able to catch most of the publish and search requests for contents indexed within this zone. They also achieved more localized eclipse attacks removing some keywords indexed on the Sybils from the DHT. Another security threat of KAD consisted in overwriting the IP address of legitimate contacts in peers' routing table [WTCT + 08]. The KADID spoofing exploited on a large scale allowed attackers to partition the DHT and to do massive denial of service attacks with few resources.

However, these two attacks were mitigated in the latest versions of KAD clients [START_REF] Cholez | Evaluation of Sybil Attacks Protection Schemes in KAD[END_REF]. Several protection mechanisms have been introduced: 1) a protection against flooding reduces the efficiency of crawlers, 2) it is no longer possible to infect a peer's routing table with Sybils having the same or very close IP addresses (same /24 sub-network), and 3) a three-way handshake prevents a peer from overwriting the IP address of another in routing tables by claiming the same KADID. Classical Sybil attacks [START_REF] Steiner | Exploiting kad: possible uses and misuses[END_REF] on KAD which directly inject Sybils in routing tables have become inefficient. While protective rules have been set to protect the routing table from Sybils, the lookup process remains unprotected. In fact, to control or disturb the indexation mechanism, [START_REF] Cholez | Monitoring and Controlling Content Access in KAD[END_REF] and [START_REF] Michael Kohnen | Conducting and optimizing eclipse attacks in the KAD peer-to-peer network[END_REF] adopt different strategies focusing on the Search process instead of the peers' routing table. In [START_REF] Cholez | Monitoring and Controlling Content Access in KAD[END_REF], A few distributed peers (with different IP addresses) are placed closer than any legitimate peer to the targeted DHT entry as shown in Figure 2 and Table 1, where the attackers share a 96 bit prefix with the target. We define the "prefix" shared between two KADIDs as the number of the first consecutive bits in common between the two KADIDs. The higher the prefix, the closer the KADIDs on the DHT are. To ensure that all inserted peers are found around the target and attract all the service requests, they cooperate to promote each other during the lookup process. Another strategy to conduct eclipse attacks is proposed in [START_REF] Michael Kohnen | Conducting and optimizing eclipse attacks in the KAD peer-to-peer network[END_REF] by generating Sybils progressively closer to the target until the lookup process stops with a timeout. For monitoring purposes, the authors of [START_REF] Memon | Large-scale monitoring of DHT traffic[END_REF] insert probes in the network and limit their visibility to their closest neighbor to get a copy of the traffic sent to every peer in the DHT.

When Sybils are successfully inserted, the attacker can disturb the network in several ways. [START_REF] Steiner | Exploiting kad: possible uses and misuses[END_REF] presents an eclipse attack removing the indexation of the targeted contents from the DHT, [START_REF] Naoumov | Exploiting p2p systems for ddos attacks[END_REF] describes a way to perform a DDoS by inserting the victim's IP address in responses sent by the Sybils and can easily generate more than 100Mbit/s toward the target, [START_REF] Liang | The index poisoning attack in p2p file sharing systems[END_REF] highlights the fact that the Sybils are used to pollute the contents shared in the Overnet P2P network by announcing fake files and [START_REF] Locher | Poisoning the Kad Network[END_REF] confirms that this issue could also affect KAD.

Proposed solutions

Many defense strategies described in the literature try to limit the Sybil attack. Proposed solutions are based on a strong identification of peers [START_REF] Dinger | Defending the sybil attack in P2P networks: taxonomy, challenges, and a proposal for self-registration[END_REF] or on a trusted central authority. In [START_REF] Singh | Defending against eclipse attacks on overlay networks[END_REF], the authors propose to enforce the degree of overlay nodes by anonymous auditing to limit localized attacks. However, they also rely on a central certification to limit the number of Sybils. A strong identification being not adapted to many P2P systems, other strategies are possible to limit the Sybil attack. Some solutions consider that a distributed assignment with free identifiers is possible but, in compensation, must be verified by resource consuming proofs [START_REF] Rowaihy | Limiting sybil attacks in structured p2p networks[END_REF] or an underlying social network [START_REF] Yu | Sybilguard: defending against sybil attacks via social networks[END_REF]. The most successfully completed protection against the Sybil attack [LMT08] uses distributed certification coupled with a social network, but no studies so far apply its protection in a real network. Without limiting the number of Sybils, [START_REF] Danezis | Sybil-resistant dht routing[END_REF] improves the DHT lookup process under denial of service attacks performed through massive Sybil insertions. However, the authors do not consider the issue of localized attacks on DHT entries while their solution needs significant protocol modifications.

Even if defenses against Sybil attacks have been largely investigated, the proposed solutions are only partially convenient. Each of them has drawbacks: strong constraints to be defined at the start of the DHT (social network), incompatibility with an open network (central authority), or too much overhead (crypto puzzles). No solution meets the requirements of KAD which can not rely on a managed support infrastructure and needs a full backward compatibility with older clients. These constraints limit the possible modifications of the P2P system and make the design of a defense scheme very challenging.

Previous explorations of KAD

A crawler is a tool that can discover all the peers participating in a P2P network and store their information. Several research papers used crawlers on KAD. The authors of [WTCT + 08] and [START_REF] Steiner | Exploiting kad: possible uses and misuses[END_REF] perform crawls of the network in order to insert Sybils. To each peer found, they send many routing requests (Kademlia request) with specific KADIDs set as parameter to discover all the contacts in the peer's routing table. The crawler of [WTCT + 08], called Blizzard has also been used in [START_REF] Steiner | A global view of kad[END_REF] to monitor the evolution of peers in time.

The authors of [YFX + 09] use another algorithm to crawl the network based on bootstrap requests. They claim that this approach is more efficient (20 contacts are returned by a bootstrap request instead of 11 for a routing request) but the contacts obtained in this way are randomly chosen in the routing table which makes a precise exploration of the tables impossible. By analyzing the crawler's results, the authors highlight a large number of peers (20%) that share their KADID with another.

Even if many explorations of KAD have been conducted, none of them consider the detection of deviant activities affecting the DHT. Moreover, crawlers' accuracy is unknown and their crawling strategy is not clearly described.

Content monitoring in P2P networks

Before highlighting the monitoring activities affecting the KAD network, we remind that such activities have been recently studied in other P2P networks, mainly BitTorrent. First of all, Piatek et al. [START_REF] Piatek | Challenges and directions for monitoring p2p file sharing networks -or -why my printer received a dmca takedown notice[END_REF] inserted some IP addresses of connected devices (routers and printers) inside BitTorrent's swarms but without participating in any file transfer. As a result, they received DMCA 1 take-down notices showing that the monitoring of P2P networks blindly following copyright enforcement policies, is simplistic, inaccurate and prone to false positives. The authors of [START_REF] Siganos | Monitoring the bittorrent monitors: A bird's eye view[END_REF] go further in the detection of BitTorrent monitors by detecting deviant behaviors with simple heuristics (blocking connectivity, multiple clients per IP, etc.) applied on empirical observations of many popular torrents. In particular, they show that the majority of deviant peers belong to copyright enforcement policies but also that 39% are part of Botnets. Their work leads to the creation of more dynamic and accurate IP blacklists of deviant clients but the heavy monitoring needs make a direct application difficult in a distributed and untrustworthy environment. The authors of Omnify [START_REF] Potharaju | Omnify: investigating the visibility and effectiveness of copyright monitors[END_REF] choose another strategy to detect monitors based on the construction and the investigation of a reverse infohash database that unifies the peers sharing a same content. The analysis of the collected IP addresses shows that monitors can be detected as they participate to several swarms of the same content, contrary to regular peers. However, monitors still miss a significant part of torrents. Finally, Le Blond et al. [LBLLF + 10] make a very efficient monitoring architecture for BitTorrent that pro-actively monitors the new torrents. Thanks to a good knowledge of the protocol and an exhaustive gathering of torrents' public data, they are able to identify 70% of the new content providers with a single computer which proves that BitTorrent's central tracking system can ease a lot the task of monitors. Compared to these studies, we show that such deviant peers also affect the KAD network and we provide a distributed and efficient way to detect them, which does not imply a heavy monitoring activity.

3 Quantifying suspicious peers in the whole network In this first section, we present our crawler which is able to build an accurate view of the KAD network. Then, we analyze the collected data to quantify, for the first time, suspicious peers inserted on the DHT.

Crawling the KAD DHT

Crawling approach

Our crawler must achieve two goals: it must get a very accurate view of the network and limit the footprint of the crawl by limiting the number of requests sent to each peer. Sending few requests makes the crawl compatible with the recent flooding protection that limits the number of requests received by a peer in a short period of time from a given source [START_REF] Cholez | Evaluation of Sybil Attacks Protection Schemes in KAD[END_REF]. Our crawling strategy involves three steps as follows.

Bootstrap: In the first step, Bootstrap requests are sent to get quickly a first, yet inaccurate, view of the DHT. For each request sent, the crawler receives 20 contacts randomly chosen in the peer's routing table. The new contacts retrieved from the Bootstrap responses are progressively requested until 500000 contacts are found by the crawler with at least 500 contacts per zone2 . Beyond this value, the contacts returned by Bootstrap requests being randomly chosen, new contacts are more difficult to find with this method.

Full crawl: The second step consists in crawling with accuracy each zone thanks to the lookup requests (Kademlia request). Each requested peer returns the 4 closest contacts to the KADID given as parameter that are stored in its routing table. To discover all the peers, we generate 2 21 ≈ 2 million KADIDs we define as landmarks and that are uniformly distributed over the DHT space. We create for each landmark a lookup request and send it to the closest peer already discovered.

Second crawl: When a zone has been fully explored, that is to say when all landmarks have been sent, the final step consists in performing a second crawl of the zone. For each contact already known, we compute the prefix shared with its direct neighbor and we generate a new landmark placed between the two peers. Finally, a lookup request is sent to the peer. This final step is very accurate and allows the crawler to find some peers missed during the first crawl. The exploration is over when all peers have been requested about their neighbor.

Cartography of the DHT

Stored information: For each peer discovered by the crawler, we store the following information: <KADID, IP address 3 , TCP port, UDP port, KAD protocol versi on, state of the peer>. The state of the peer can be P(possible), T(tried) or R(responded) respectively if the contact has just been discovered, has been requested or has responded. Global results: During our measurements, a zone contains between 13000 and 17000 contacts, the overall number of peers varies from 3.3 million to 4.3 million given the day and the hour of the crawl. At a large scale, the peers are uniformly distributed over the DHT address space (Figure 3) which is expected because the majority of the regular peers randomly choose their KADID when connecting for the first time to the network. We analyze more precisely the results of our explorations in the next subsection with the goal to detect the suspicious peers' positions that indicate deviant activities.

Evaluation of the crawler

The crawls of KAD were performed from a single computer, with each zone crawled sequentially. With the highest accuracy (2 pass), a snapshot of a zone takes 2 minutes and a full crawl of KAD takes less than 9 hours. The speed of the crawl is not a critical parameter in our research purpose, because deviant peers must be quite stable, but the accuracy of the crawler actually is. To validate our crawling approach, we evaluated our crawler efficiency with two experiments. First, we inserted 360 peers in the KAD network thanks to the PlanetLab testbed4 . The peers follow an attack pattern: they form groups of 5 and are placed around 72 DHT entries. Each peer shares at least 96 bits with its target. At the end of the crawl, all the inserted peers were found in the crawler's data. The following sample shows the results of a data analysis looking for peers close to the 72 targets we defined. The second evaluation of our crawler consisted in instrumenting a KAD client to print the list of contacts found after a DHT lookup while the crawler explored the corresponding zone of the DHT. In all our tests, the peers found by the instrumented client were present in the crawler's data, which shows the relevance of our crawling approach.

Detection of suspicious peers in the DHT

As explained, an efficient DHT monitoring or attack involve the insertion of one or several peers close to the targeted DHT entry in order to attract the requests sent by the regular peers for that content. To improve the attack efficiency, many peers can be inserted around the DHT entry.

Analysis of the distances between peers

In KAD, like in most DHTs, the normal behavior of legitimate peers is to randomly choose their ID (128 bits KADID). As the distribution is uniformly random, the average distance between two IDs is only defined by the number of peers in the DHT. Let F be the function giving the mean number of peers sharing at least x bits with a given KADID, for a total number of N peers in the network.

F (x) = N 2 x (1)
More precisely, the theoretical prefixes (number of common bits) distribution of peers' ID around a target ID follows a geometric distribution with parameter p = 1/2.

P (X = k) = (1 -p) k-1 p (2)
Figure 4 shows the mean number of peers existing in the DHT according to the length of consecutive common bits (prefix) shared with a target ID. We consider a realistic number of 4 million peers taking part in the DHT at the same time. Table 2 presents some values of F with N = 4 × 10 6 and x ∈ [1; 128]. Moreover, the average prefix shared between two peers is d moy = log 2 (N ) = 21.93 bits. Our first analysis consisted in detecting those groups of peers which are very close to each other on the DHT because they all focus on the same DHT entry.

Our assumption is that two peers sharing a very long prefix with each other have an unlikely position regarding the regular uniform distribution of the KADIDs. A suspicious position can be intentional for monitoring or attack purposes.

Based on our crawl of the KAD DHT, we computed the distribution of prefixes shared between each peer and its direct neighbor which is presented in Figure 5. While a regular distribution should strictly decrease, the measured distribution clearly shows abnormalities. Figure 6 shows a clear deviation from the theoretical distribution for peers sharing between 35 and 45 bits. When the shared prefix between two peers is higher, the probability of an intentional position is also higher because the prob-ability to find two close neighbors decreases when the length of the shared prefix increases. Given the number of peers in the DHT, prefixes below 30 bits are likely shared between several peers and make impossible a proper detection of attacks. However, we can say that prefixes over 35 bits are unlikely enough to indicate a very suspicious position of the peers. Considering that two peers sharing more than 35 bits are suspicious, the analysis of our crawler's data highlights 2074 groups of suspicious peers with obvious attack patterns. In fact, the suspicious peers come from the same sub-network (123.144.0.0/16 or 123.145.0.0/16) and use specific ports (10875 or 10839) to connect to the P2P network. The following sample shows two of these groups:

Prefix "4A9D8C87770000000000000000000000", length 40, shared by 6 contacts: <4A9D8C87774AF8C551FE78BDDC3F5A37, 123.144.X.X, 10875, 10875, 8, T> <4A9D8C877780DFB9985E75EE92AD1C68, 123.144.X.X, 10875, 10875, 8, T> <4A9D8C877780DFB9985E75EE92AD1C68, 123.145.X.X, 10875, 10875, 8, T> <4A9D8C877797D58D4C21B5BD5224F067, 123.144.X.X, 10875, 10875, 8, T> <4A9D8C877797D58D4C21B5BD5224F067, 123.144.X.X, 10875, 10875, 8, T> <4A9D8C8777F0F03BD1FE123548E269D2, 123.144.X.X, 10839, 10839, 0, R> Prefix "4A9D8C87778000000000000000000000", length 41, shared by 4 contacts: <4A9D8C877780DFB9985E75EE92AD1C68, 123.145.X.X, 10875, 10875, 8, T> <4A9D8C877797D58D4C21B5BD5224F067, 123.144.X.X, 10875, 10875, 8, T> <4A9D8C877797D58D4C21B5BD5224F067, 123.144.X.X, 10875, 10875, 8, T> <4A9D8C8777F0F03BD1FE123548E269D2, 123.144.X.X, 10839, 10839, 0, R> However, our detection strategy has two limitations. First, as we only analyze the distances between two peers, we can not detect when a single peer is placed near a DHT entry. Second, we highlight many groups of suspicious peers but we do not know what they target. Therefore, we will present in the next subsection another detection strategy based on the analysis of the distances between peers and well-known contents.

Analysis of the distances between peers and contents

To apply this detection method, the first step consists in collecting keywords about contents shared in the KAD network. As input, we used several sources of multimedia contents (Amazon top sellers, iTunes, ThePirateBay) to get relevant keywords and then we computed their MD4 value that gives their KADID. Finally we computed the list of the suspicious peers that are too close to different contents (i.e. sharing a prefix > 35 bits) in the crawler's data. The following sample shows some suspicious peers found by our analysis: One quarter of the 888 keywords we monitored is obviously targeted by a peer sharing at least a 96-bits prefix. This prefix length clearly indicates a malicious position, given the very low probability to find such an honest peer (Table 2). A sample of the keywords that are targeted is listed in table 3. Moreover, some attack patterns appear easily from collected data. For instance, 205 of the 216 keywords are targeted by peers using the UDP port 5003 and TCP port 5002, they share a 96 bits prefix with the content's KADID and use IP addresses distributed over the Internet. Another group is focused on 16 keywords with peers using the UDP port 7290 and TCP port 7294, sharing a 122 bits prefix with each target and using IP addresses from the sub-network 95.175.0.0/16. Considering the 44 suspicious IP addresses involved in the 216 suspicious groups, we searched in the crawler's data other peers sharing these IP addresses. In fact, the list of keywords used for the detection is just a small subset of the contents actually shared within the P2P network. It appears that the suspicious peers we found thanks to our set of keywords only represent 10% of the peers using these 44 suspicious IP addresses. Overall, these suspicious IP addresses account for 2119 different peers in the DHT, which clearly shows that a lot of contents shared within KAD are targeted by deviant peers.

[...] twilight 4D62D26BB2A686195DA7078D3720F60A <4D62D26BB2A686195DA7078D3720F632,
This second detection method could be extended. For instance we did not consider keywords written using Asian characters which may lead to miss many other peers as KAD is widely used in China [START_REF] Steiner | A global view of kad[END_REF]. Moreover, besides keywords, all the files indexed in the DHT can also be targeted. A tool collecting the different fileID shared in the network through the P2P system search engine could be useful to detect such activities.

Protecting peers from localized DHT attacks

In the previous section, we presented two complementary detection strategies and proved through large scale measurements that the KAD DHT is widely affected by thousands of peers targeting shared contents and that these peers could perform content-centric attacks. In this section, we propose to detect such suspicious peers presenting an attack configuration when a client performs DHT lookups. Part of this section was published in [START_REF] Cholez | Efficient DHT attack mitigation through peers' ID distribution[END_REF].

Analysis of peers' ID distributions for safe DHT entries

Localized DHT attacks are very efficient on KAD because the peers found during the lookup process are always sorted by distance to the target, and then requested in that order with service requests. If 10 or more peers of an attacker are found to be the closest to a DHT entry, they will attract all the requests thanks to their proximity to the target. However, we showed that a localized attack introduces proximity abnormalities in IDs distribution around the target. Therefore, to detect DHT attacks, we consider the unusual peers' ID distribution resulting from the position of these malicious peers and that we can find during the regular lookup process, without any network overhead.

Theoretical IDs distribution

We described in Section 3.2 the theoretical IDs distribution for a DHT. However, even if the IDs distribution is well known at the network scale (i.e. when using a crawler), we do not know if the best contacts found during a lookup process on the DHT reflect this distribution. As a peer only has a partial view of the network through its routing table, it relies on the lookup procedure to find the best peers on which to publish or to search contents. It is difficult to infer if the peers found after a DHT lookup are indeed the best potential peers existing in the DHT. Moreover, several parameters can affect the routing efficiency of a peer (uptime, distance to the target ID...) and need to be considered.

Real IDs distributions

To compare the results of the KAD lookup algorithm to the theoretical random ID distribution, we ran an experiment that consists in performing many lookups on safe DHT entries and storing for each lookup the best contacts found. We measured these real peers' ID distributions at the end of the lookup process (just before the second step when specific service requests are sent to the 10 best contacts found). At this stage, many contacts have been found in the tolerance zone of the target but we focus our attention on the ID distribution of the 10 best peers only.

We published 100 files over 60 hours. To be sure that no attack is currently targeting our files, the two keywords composing each file name and raw data are randomly generated. The default KAD behavior is to publish the keywords every 24 hours and the files every 5 hours resulting in approximately 1800 (12×100+3× 200) publications on the DHT. For each publication, we monitored the contacts found by our client and computed the prefix shared between these contacts and the hash of the content to be published.

Figure 7 shows that the average common prefix size of the 10 best contacts found is between 18 bits and 19 bits. This is a very good result considering the number of potential peers sharing this prefix length in a 4 million peers DHT (between 15.25 and 7.6 from Table 4). This result confirms the KAD routing efficiency since the 10 best peers found after the lookup process are nearly the 10 best peers that actually exist in the DHT. Figure 7 also illustrates that the time spent in the network has no significant impact on the average common prefix of the 10 best contacts, despite the fact that the routing table consistency is improved over time. We see a very small periodic variation of the average common prefix size. This small amplitude is explained because KAD is mainly used in European countries and in China. The activity hours of these two regions are complementary.

We investigated several other parameters potentially affecting the quality of the best found contacts. We showed that the DHT distance between the requesting peer and the target does not impact the routing efficiency. In the same way, the type of published information (keyword or file), or the type of requested services (publish or search) has no impact on the quality of the found contacts. Finally, the most important result concerning this experiment is given in Figure 8. For each publication, we counted the number of peers among the 10 best peers sharing a given common prefix with the target ID. It appears that, after the 17 bits prefix, the distribution exactly follows the theoretical peers' ID distribution described in section 3.2. So, the KAD lookup procedure is efficient enough to give a representative view of the closest peers possible. Above all, this result shows that, when the size of the DHT is well-known, the theoretical random ID distribution is sufficient to characterize the results obtained in a real lookup process.

We will rely on this strong result to detect DHT attacks. We will first define some preventive rules to avoid the most obvious insertions of peers. In a second time, we will present a metric that can accurately detect the remaining attacks.

Preventive rules

Recent Sybil attack protection mechanisms introduced in KAD [CCF09] demonstrated that few passive rules mitigate the simplest attacks, without significant drawbacks. With the same idea, the following protective rules applied to the lookup process make an attack more difficult to be achieved.

IP address protection:

We apply to the peers found during the lookup process the same protection rules already set to protect the routing table from Sybil attacks. Basically, for a given publication on the DHT, we forbid several hosts from the same sub-network to be responsible for this entry. When publishing a content on the DHT, a peer must check that all requests for its content will be sent to peers from different sub-networks. In this way, an architecture that would be able to catch all requests is harder to set up. This protection aims to distribute peers in charge of a DHT entry on the IP-network scale.

Discarding too close nodes:

A second protection consists in setting a minimum distance between the target ID and the closest responsible peers, according to the normal peer behavior and the DHT size. As shown previously, we assume that legitimate peers randomly choose their ID. So, we define a threshold beyond which closer peers become very unlikely and suspicious to attack the DHT entry. Without any protection, any peer can index a content when sharing at least 8 bits with the target ID. In other words, any peer sharing between 8 bits and 128 bits with a target ID can be selected to receive service requests. However, peers sharing a very high common prefix (i.e. between 28 and 128 bits) are very unlikely as illustrated in Figure 8. So, we define a minimum distance between the target ID and the closest responsible peers of 28 bits, which moves the range of the tolerance zone from [8;128] to [8;28]. The lookup process will discard any peer closer than 28 bits to the target without decreasing the DHT efficiency. Nevertheless, this protection is not sufficient as localized attacks involving many peers sharing 28 bits with the target can still manage to get all the requests.

Detection and protection against localized attacks

Detecting attacks with Kullback-Leibler divergence

To detect attacks, we compare the 10 best peers distribution to the theoretical distribution previously described. The 10 best peers are the most important to consider because they receive the service requests which hacking is the root of an attack.

The main issue is that the few best peers represent a too small sample size to get results from the common statistic tools comparing distributions. We first tried the chi-square and the Kolmogorov-Smirnov methods to compare IDs distributions but they are unable to give interesting results in our situation. In our case, a metric based on the Kullback-Leibler divergence (also called G-test) gives much better results to detect an attack. In fact, it is known to be more efficient for empirical distributions with a small number of observations [START_REF] Sokal | Biometry: the principles and practice of statistics in biological research[END_REF]. Given the probability distributions M and T of a discrete random variable, the K-L divergence between M and T is defined as:

D KL (M | T ) = i M (i)log M (i) T (i) (3)
We define a discrete random variable taking 11 values representing the distribution of common prefixes between 18 bits and 28 bits. T represents the theoretical geometric distribution of the IDs, with parameter 1/2. M is the prefixes distribution of the 10 best contacts found at the end of a lookup process. Table 5 shows the values defined for T and two distribution examples for M. To detect attacks, we do not consider IDs with a common prefix under 18 bits for two reasons. First, we showed in Table 4 that focusing on the 17 bits prefix or less would only permit an attacker to capture on average 1.26 out of the 10 requests, while being in competition with many legitimate peers. Second, as seen in Figure 8, the average distribution of the best contacts currently observed in KAD follows the geometric distribution (1/2) from the 18 bits prefix. This limit can evolve to higher prefixes if the number of peers in the DHT increases (i.e. 19 bits if the number of peers doubles) or to lower if it decreases. This means that by design, our detection algorithm needs to know the size of the network, or at least, what is the regular distribution. We present in Section 4.2.4 how a peer can easily learn this information. Concerning the other limit of 28 bits prefixes, we mentioned previously why closer contacts should be filtered preventively.

The K-L divergence is a non-symmetric measure D KL (M | T ) = D KL (T | M ). In our case, comparing the divergence of T from M is more significant to detect attacks. For each common prefix between 18 and 28 bits for which peers are found (M (i) = 0), the measured distribution for this prefix is compared to the theoretical distribution and added to the global K-L divergence. Highest prefixes (with small T values) and contacts grouped on a single prefix (resulting in a high M value) generate a big increase of the divergence which is relevant to detect attacks. The K-L divergence gives the advantage to be effective with a small sampling and its incremental computation can tell which value of the distribution increases the most the divergence, what will be useful to apply precise countermeasures in case of positive detection. However, the K-L divergence does not give a probability of similarity between the two distributions but a relative value. So, we have to define which value of K-L divergence indicates an attack and must be defined as the detection threshold.

Evaluation with simulated attacks distributions

To define the detection threshold, we computed the K-L divergence for two sets of distributions representing two situations: a lookup process for safe or attacked DHT entries. The first set of distributions is based on the results of many lookups for randomly generated data, as described in Section 4.1.2. The second set of distributions is simulated to represent different attack scenarios.

Simulation of attacks

An attack on a DHT entry can lead to different peers' ID distributions, regarding the parameters (number of malicious peers involved, proximity to the target...) used by the attacker. Basically, an attacker must answer two questions: How many peers to insert? On which prefixes? As explainedearlier, our detection mechanism considers prefixes distribution of the 10 best peers sharing a common prefix between 18 bits and 28 bits. We consider that all inserted malicious peers are found during the lookup process.

To simulate attacks distributions, we first initialize a distribution with, for each prefix length in the detection window [18-28], a number of peers close to the real mean number provided by our observations. We then modify this set of peers by adding malicious peers according to different insertion strategies that use between 5 and 10 malicious peers, and we finally compute the new distribution of the 10 best contacts that includes the malicious ones. Table 6 presents the different attack

4-3-2-1 7 10 5 4-2-2-1-1 6 10 6 2-2-2-2-1-1 5 10 7 2-2-2-1-1-1-1 4 10 10 1-1-1-1-1-...-1 2 5 1 5 11 5 3 2-2-1 8 5 5 1-1-1-1-1 6
configurations we considered from the most obvious inserting 10 peers on the same prefix (11 different attacks are simulated, one for each prefix between 18 and 28 bits where the 10 peers can be inserted), to the least visible inserting 5 peers on different prefixes. Regarding the different repartition of peers provided by each simulated distribution, an attack is more or less efficient and easy to detect. For example, 10 malicious peers inserted to share 28 bits with the target would easily attract all requests but would also be easily detected. At this step, we do not consider massive insertions of malicious peers to evaluate the detection mechanism. In fact, our detection mechanism only considers prefixes distribution of the 10 closest peers found after a lookup. For example, a strategy based on 15 malicious peers distributed on three prefixes like [5 * 20; 5 * 21; 5 * 22] just appears as [5 * 21; 5 * 22] to our detection mechanism. So, we do not need to simulate all attacks inserting more than 10 malicious peers to evaluate our detection system. Nevertheless, the countermeasure described further will deal with all inserted malicious peers.

Evaluation of the K-L divergence

Finally, we evaluate the K-L divergence for these two sets of distributions, to find the proper detection threshold. The K-L divergence applied to the set of normal publications gives a mean divergence of 0.41 with a standard deviation of 0.24. To find the best threshold possible, we increase the allowed divergence while measuring the number of wrongly detected distributions. False negatives are undetected distributions from the data set of simulated attacks and false positives are safe distributions detected as attacks. Figure 9 shows that a K-L divergence of 0.7 is a good trade-off threshold to detect most DHT attacks with a good falsenegative rate (7.95%) without detecting too many normal distributions (8.65%) as dangerous. With a closer look at our traces, we see that the most dangerous attacks involving the insertion of 10 peers are detected with a very small false-negative rate of 1.56%.

Attacks involving only 5 peers are harder to detect, with a false-negative rate of 21.73%, because of their smaller impact on the IDs distribution. However, such attacks involving few peers can not manage to fully control a DHT entry. Nev-Fig. 9 False positive and false negative rates regarding the K-L divergence threshold ertheless, the system is still able to detect the most efficient configurations. A detailed analysis reveals that we mainly lose two types of inoffensive distributions:

-Attacks only targeting the 18 bits prefix. However such attacks are not efficient because they miss many requests sent to closer peers (19 bits prefix or better) and they are resource consuming because of the competition with legitimate peers at this prefix.

-Attacks with 5 peers distributed on more than 3 prefix under 23 bits. However, such attacks distributed on several prefixes are unlikely because they must rely on the absence of legitimate peers on their highest prefixes in order to not be detected, and they face a high competition with legitimate peers on their lowest prefixes.

In summary, effective attacks using the insertion of many peers are fully detected while undetected attacks insert not enough peers, or too far from the target, to be dangerous. The more efficient an attack is, the easier it is to detect. After having shown that we can detect DHT attacks by analyzing prefixes distributions, we present, in the next part, how a peer can be protected from malicious peers when an attack is detected.

Countermeasure Progressive filtering of attacked prefixes

Our countermeasure progressively removes peers whose prefix contributes the most to the measured K-L divergence. The procedure is described in Algorithm 1 which is executed when a distribution is detected as an attack. It provides an updated and safe contact list to send service requests to.

Input: contact list [ ]; prefixes distribution [ ]; KL increments [ ]; KL div;

max div; Output: updated contact list [ ] foreach pref ix in prefixes distribution do KL increments.add(partial KL div(pref ix)); end KL div = SUM(KL increments); while KL div > max div AND M AX(KL increments) > 0 do prefix=KL increments.index(MAX(KL increments)); remove contacts(contact list, prefix); remove distance(KL increments, prefix); KL div=SUM(KL increments); end Algorithm 1: Countermeasure to mitigate DHT attacks

The countermeasure shares similarities with the detection mechanism: it takes place after a DHT lookup (it protects any type of service performed on the DHT) and compares the same distributions of common prefixes between 18 bits and 28 bits with the K-L divergence. Considering the first 10 best peers is sufficient to detect an attack, but not to remove all malicious contacts. The countermeasure updates and checks the 10 best peers' distribution each time malicious peers are removed from the contact list. If an attacker places many peers near the target, they are progressively removed from the 10 best peers on each iteration, until the updated distribution of the 10 best peers becomes safe, (i.e. the updated KLdivergence is under the maximum allowed divergence "max div"), or that no prefix remains with a distribution superior to the theoretical one.

This progressive approach has the advantage of avoiding malicious peers while preserving the less suspicious peers among the best found. If needed, remaining contacts with lower common prefixes (17 bits or less) browsed during the lookup process are selected to complete the left places among the new list of the 10 best peers, without requesting any new lookup. In this way, the routing efficiency does not decrease much in case of false-positives and an attacker could not eclipse a content by triggering on purpose our countermeasure to reduce the replication factor of a content, the 10 replicas being always granted after the countermeasure.

Finally, the whole defense scheme to protect the DHT against localized attacks is presented in Figure 10. Our solution can be implemented in a future release of KAD clients, directly protecting them against DHT attacks, while keeping a full compatibility with older clients and ensuring the durability of the network. Moreover, our defense scheme can be applied as described with no overhead to every DHT whose lookup process is not delegated to intermediate peers, and on which stored information are replicated on several peers (a common solution to fight against churn).

Evaluation by simulation

To evaluate our countermeasure, we used the previously described distributions obtained from regular lookups and simulated attacks. We counted the average number of contacts removed by the countermeasure for each distribution previously detected as an attack in function of a value chosen as the maximum allowed divergence. We defined 0.7 (the same value than the detection threshold) as the more relaxed maximum divergence to consider. Figure 11 shows that the countermeasure successfully adapts the response to the number of peers inserted. The number of removed contacts matches exactly what could be expected for the different attack scenarios. First, looking at the distributions of real safe publications (false-positives), they are just slightly impacted by the countermeasure; just 2 or 3 good contacts from these distributions will be removed. In the opposite, the distributions representing attacks with 10 malicious peers are highly affected by our countermeasure: between 8 and 10 malicious contacts are removed. So, our solution succeeds to mitigate the most dangerous attacks. Finally, attack strategies based on 5 peers are also severely mitigated. In average, the countermeasure deletes between 4 and 5 malicious contacts in the corresponding distribution set. Like the detection threshold, the maximum allowed divergence is a parameter that can be balanced to avoid false-positive distributions to be much affected. According to Figure 11, we consider that a maximum allowed divergence between 0 and 0.3 is good to highly mitigate attacks. If we consider the worst case, where the countermeasure must remove all contacts in the detection window, the published information will still remain close to the DHT entry. In fact, from our observations of safe publications, Table 7 indicates that the 10 best remaining peers have, in average, common prefixes between 17 bits and 15 bits. This result is far from the minimum distance of 8 bits defined as the tolerance zone in KAD.

Evaluation on PlanetLab

To prove the applicability and the efficiency of our approach, we implemented our protection in an aMule client and monitored it while accessing 20 keywords we attacked from PlanetLab. The attacks consisted in the deployment of 100 modified clients from 10 PlanetLab nodes. These clients were modified to choose their ID close to a specified keyword. We made the attacks hard to detect by only involving 5 Sybils per attack and we placed them to share at least 20 bits with each targeted keyword. We show in Figure 12 a snapshot of the peers found after a lookup on the attacked keyword "madonna". The numbers highlighted in blue are the prefixes of the different responding peers found during the lookup process (including our Sybils): 13 were found and the 10 closest are used to compute the measured distribution M . The attack is detected because the Kullback-Leibler divergence computed for this distribution is above the threshold (1.09 > 0.7).

As a consequence, the countermeasure is applied and the resulting distribution is presented in Figure 13. We can see that 4 out the 5 Sybils were filtered by our Fig. 13 Countermeasure applied to mitigate the attack on the keyword "madonna" countermeasure (on the prefixes 26 and 21). The maximum allowed divergence "max div" of the countermeasure were set to 0.7 for this experiment and we can see that the final KL divergence is below this threshold (D KL = 0.431523). A lower stopping threshold (for example set to 0) would have removed the peers with the 20 bits prefix, filtering the last Sybil but also a legitimate peer. We still recommend the developers to set a stopping threshold of 0 in order to avoid as much Sybils as possible. Considering the other keywords, all attacks were detected and between 4 and 5 malicious peers were removed which is exactly what was expected from our simulations.

Design improvements

Feedback on implementations

To prove that our solution is suitable to protect currently deployed P2P networks based on a DHT, we implemented it on KAD. The main developer of the gtkgnutella client5 , Raphael Manfredi, also implemented our solution in his client to protect the Gnutella DHT. Thanks to his work we got a feedback on the applicability of our solution to other P2P networks and we got the opportunity to improve some points to make our solution easier to deploy. Both implementations of the detection and countermeasure were straightforward and just one source file per client needed modifications (Search.cpp for KAD, lookup.c for gtk-gnutella). However the detection parameters are specific to each network. gtk-gnutella: Two main differences between KAD and the Gnutella DHT make the detection parameters set for KAD inefficient. In particular, the prefixes [18-28] observed by our solution to detect attacks are not suitable to this network. First, the Gnutella DHT is much smaller than KAD with approximately a population of 7 * 10 4 peers. Second, information published on the Gnutella DHT is replicated on 20 peers while it is replicated on 10 peers in KAD. The following execution shows a proper detection of suspicious peers on the Gnutella DHT. We can see that the 20 peers found after a DHT lookup share lower prefixes [11-16] with the target.

11bit prefix: M=0.50 (10/20 nodes,log2=-1.00000) T=0.500000 => K-L contrib: 0.000000 12bit prefix: M=0.20 (4/20 nodes,log2=-2.321928) T=0.250000 => K-L contrib:-0.064386 13bit prefix: M=0.15 (3/20 nodes,log2=-2.736966) T=0.125000 => K-L contrib: 0.039455 14bit prefix: M=0.05 (1/20 node, log2=-4.321928) T=0.062500 => K-L contrib:-0.016096 15bit prefix: M=0.05 (1/20 node, log2=-4.321928) T=0.031250 => K-L contrib: 0.033904 16bit prefix: M=0.05 (1/20 node, log2=-4.321928) T=0.015625 => K-L contrib: 0.083904 with 20/20 nodes, K-L divergence to bce4d59bd8db868b7ffc0031ae81cca8db51937f = 0.076780 To be adapted to the Gnutella DHT, the prefixes considered by our solution to detect the suspicious peers have to be lowered. This highlights the need of an automatic way to compute the right prefixes used for the detection window in order to adapt easily our solution to different networks. Moreover, the population of a P2P network can quickly vary in time. For example, the size of the Gnutella DHT was divided by 10 when the LimeWire client was shutdown. Such a variation in the number of peers would make our detection inefficient if no process can adapt the detection parameters accordingly. A quick decrease of the number of peers would leave space for attackers to be inserted without triggering the detection while a quick increase would always trigger the countermeasure. A last argument in favor of dynamic detection parameters is the daily variation the network population. KAD does not suffer from this problem because its population is well balanced between Europe and China. However, we present in Figure 14 the results of a previous experiment [START_REF] Pablo | When kad meets bittorrent -building a stronger p2p network[END_REF] measuring the size of two DHTs during a few days and they show that the population of BitTorrent's Mainline DHT can be divided by two during a day. A periodic computation of the detection window would improve the accuracy of our detection. Using the DHT size: Many clients of P2P networks (eMule, Vuze, gtk-gnutella, etc.) provide an estimation of the size of the network based on the analysis of their routing table. The setting of a proper detection window is straightforward with the knowledge of the DHT size. Let N be the DHT size given by the client and K the replication factor used on the DHT. The first prefix considered by the detection window is given by the number of bits "bmin" defined by: bmin = ⌊log2(N ÷ K)⌋ (4)

The ⌊x⌋ notation stands for the integer part of the number because the number of bits must be an integer. When applied to KAD and Gnutella DHT, the equation gives the right prefixes to start the detection window, respectively 18 bits and 11 bits (for KAD: bmin = ⌊log2(4 * 10 6 ÷ 10)⌋ = 18 and for gtk-gnutella: bmin = ⌊log2(7 * 10 4 ÷ 20)⌋ = 11). The high limit of the detection window "bmax" must be defined so that peers beyond that limit are too close from the target and automatically filtered. We chose bmax = bmin + δ with δ = 10 to limit the number of false positives of peers directly filtered to 1/2 10 which is less than 0.1%.

Learning of the detection window:

If the client of the P2P network does not provide an estimation of the DHT size, the detection window and the regular distribution of prefixes can easily be learned from the network. The peer must perform several DHT lookups for randomly generated KADIDs and then compute the average distribution of the found prefixes. Algorithm 2 describes this learning method. We have presented an integration solution to quantify, detect and mitigate the localized insertions of suspicious peers in P2P networks based on a DHT. The first contribution consisted in quantifying all suspicious peers present at the network scale. To this end, we built an accurate crawler implementing a novel strategy. Its efficiency was demonstrated on a real network. We then analyzed the collected data. The analysis led to the design of two algorithms to detect suspicious peers on DHTs. The first one considers the distances between peers which highlights 2074 groups of suspicious peers surrounding an unknown target in the KAD network while the second algorithm considers the distances between peers and some predefined contents which highlights 2119 other deviant activities based on a single peer insertion very close to the content. The two detection methods are complementary and highlight different types of threat from the crawler's data. For the first time, we proved that a widely deployed DHT is actually targeted by the insertion of Sybils which may lead to major security issues for the regular peers (monitoring, pollution, eclipse attack, DDoS, etc.).

Input

Having witnessed this real threat, we designed an advanced yet efficient scheme to protect the widely deployed KAD DHT against localized attacks. Our solution was designed with many constraints in order to be efficient and able to fix an already deployed network. We wanted a defense scheme that can mitigate DHT attacks while returning a small false-positive rate, keeping the same DHT design and minimizing the overhead. The different parts of our defense scheme fit all these requirements. Our detection method is based on the comparison between the theoretical and the real distribution of prefixes shared between the closest contacts found near a target after a DHT lookup. The theoretical distribution was inferred from many observations of safe DHT lookups and we proved that the closest peers' prefixes follow a geometric distribution (1/2). Then, we used the Kullback-Leibler divergence as an efficient metric to detect peers' ID distribution resulting from an attack. Our evaluation based of simulated attacks shows low false-positive and false-negative rates, especially for the most dangerous attacks. The more efficient the attack, the better is its detection. We described and evaluated a countermeasure to mitigate the detected attacks. It is based on a progressive filtering of contacts whose prefix distribution is the most suspicious. The evaluation showed that false-positives are not highly affected by the countermeasure while nearly all malicious contacts from the different attack strategies are removed to provide a safe DHT access. Finally, our approach was implemented on KAD and on the Gnutella DHT. We successfully tested our solution on KAD against real attacks and we improved its applicability to other DHTs by defining methods to dynamically adapt the detection window to the DHT size of the P2P networks.

Our future work will consist in a better characterization of the different suspicious peers in the DHT (IP addresses involved, number of nodes inserted, prefix used, etc.) in order to clearly identify their number and strategy. Moreover, we will try to find out what are their intents when targeting the DHT by initiating direct communications with them through the P2P protocol. In particular, we are interested in finding out if they are actually monitoring or attacking contents. We will also pursue our crawl and quantification of DHT attacks operations in order to see their evolution in the long run and investigate if the deployment of our protection affects the attackers practices.

Fig. 1

 1 Fig. 1 KAD's double indexing scheme

Fig. 3

 3 Fig. 3 Distribution of peers' ID over the zones of the DHT

Fig. 4

 4 Fig. 4 Mean number of peers sharing a given common prefix size with a target

Fig. 5

 5 Fig. 5 Distribution of the prefixes length between neighbors on the DHT

Fig. 6

 6 Fig. 6 Theoretical and measured mean number of peers sharing a given prefix with their neighbor

Fig. 7

 7 Fig. 7 Average common prefix of the 10 best contacts in time Fig. 8 Prefix distribution of the 10 best contacts

Fig. 10

 10 Fig. 10 Full defense scheme applied to KAD

Fig. 11

 11 Fig. 11 Average number of contacts removed among the 10-best by the countermeasure

Fig. 12

 12 Fig. 12 Detection of a localized attack on the keyword "madonna"

Fig. 14

 14 Fig. 14 Evolution of the population for two DHTs in time

Table 1

 1 Example of peers' ID

	Type	KADID	prefix
	DHT entry	477221265829086C74988C40EFE63DAF	-
	attacker	477221265829086C74988C4070D6E0F1	96 bits
	regular peer	477229E3D7CFC729F337ABBB69C983C6	20 bits

  [...] <32FFF76959F6A7095347FB338B304330, 111.161.X.X,38060,16905,0,T> <32FFFC5C4D5AE9A082871FF68B1F0D9C, 219.139.X.X, 5149, 1025,4,R> <32FFFC5C4D5AE9A082871FF68B1F0D9C, 219.139.X.X, 5149, 5159,4,P> Zone 33: 15196 contacts <3300048A90460A8AAC3DD2FF542ADF98, 86.212.X.X, 12399,39949,9,R> <3300083A0480CFA91B8C142401DD26F2, 111.240.X.X, 5611, 5621,8,T> <330018506569424D7CBA7133F437EDC8, 120.35.X.X, 6647, 6657,8,R> <33002596F7AAAA4348FB4349F0A14FA4, 187.78.X.X, 46318,61632,9,R> <33002EF905E27753B1900BC602D29C20, 218.92.X.X, 19774,19774,8,T> <33004546934FABE9685674DE1598548F, 125.81.X.X, 51478,52073,9,R> [...]

  of the proposed KADIDs are targeted with at least 96 bits by: 37 IP addresses (showing 361 unique KADIDs in the whole crawler's data)

	[...]
	KADID 71: 19856E29730F11CA0E0C210630ADCB36
	<19856E29730F11CA0E0C210621142E70, 62.108.171.74, 14337, 13602, 8, T> [prefix = 99]
	<19856E29730F11CA0E0C2106546F8C89, 193.167.187.186, 14690, 13799, 8, T> [prefix = 97]
	<19856E29730F11CA0E0C21065622F60F, 155.245.47.241, 13953, 13779, 8, T> [prefix = 97]
	<19856E29730F11CA0E0C210676E74885, 212.51.218.235, 13897, 14465, 8, T> [prefix = 97]
	<19856E29730F11CA0E0C21069636476A, 129.97.74.14, 14308, 13853, 8, T> [prefix = 96]
	KADID 72: EBCBA6D72037ED01F56809A9FFE6A86E
	<EBCBA6D72037ED01F56809A9268DA7FB, 155.245.47.241, 13915, 13842, 8, T> [prefix = 96]
	<EBCBA6D72037ED01F56809A94519B1D4, 129.97.74.14, 14029, 13914, 8, T> [prefix = 96]
	<EBCBA6D72037ED01F56809A9702F72B7, 193.167.187.186, 13666, 14427, 8, T> [prefix = 96]
	<EBCBA6D72037ED01F56809A9892C91A4, 62.108.171.74, 13853, 14683, 8, T> [prefix = 97]
	<EBCBA6D72037ED01F56809A9BAD2A19E, 212.51.218.235, 13861, 13939, 8, R> [prefix = 97]
	72/72

Table 2

 2 Mean number of regular peers sharing a given prefix with a given KADID in a 4 million peers DHT

	Number of bits	Average number of
	in common	matching peers
	1	2 000 000
	8	15625
	12	976
	16	61
	18	15.25
	20	3.8
	24	0.24
	28	0.015
	32	9.32 * 10 -4
	64	2.17 * 10 -13
	96	5.05 * 10 -23
	128	1.17 * 10 -32

  of the proposed keywords are targeted with at least 96 bits by: 44 IP addresses (showing 2119 unique KADIDs in the whole crawler's data)

	95.175.X.X, 7290, 7294, 8, R> [prefix = 122]
	soundtrack AC213377BB53F608390BD94A6AE6DD35
	<AC213377BB53F608390BD94A82582F42, X.X.X.X, 5003, 5002, 8, R> [prefix = 96]
	harry 770CF5279AB34348C8FECF9672747B94
	<770CF5279AB34348C8FECF96524D8CDE, X.X.X.X, 5003, 5002, 8, P> [prefix = 98]
	robin B9DF47E5BFAD75F8EE5E3F50EA217983
	<B9DF47E5BFAD75F8EE5E3F5051F34AA8, X.X.X.X, 5003, 5002, 8, R> [prefix = 96]
	<B9DF47E5BFAD75F8EE5E3F50EA21799F, 95.175.X.X, 7290, 7294, 8, R> [prefix = 123]
	[...]
	216/888

Table 3

 3 Sample of targeted keywords

	Keyword	closest peer	Keyword	closest peer
	avatar	126	nine	122
	invictus	123	love	122
	sherlock	122	american	97
	princess	122	russian	97
	frog	98	the	96
	ncis	96	black	96
	nero	96	pirate	96
	...	...	...	...

Table 4

 4 Mean number of peers among the 10 best contacts found sharing a given common prefix size with a target

	Common prefix	Mean number of peer	Theoretical number of peer
	length	found	existing (on 4 million)
	15	0.0196	122
	16	0.1667	61
	17	1.2647	30.5
	18	3.2255	15.26
	19	2.6274	7.63
	20	1.4118	3.81
	21	0.6078	1.9
	22	0.4118	0.95
	23	0.1274	0.48
	24	0.0588	0.24
	25	0.0392	0.12
	26	0.0196	0.06
	27	0.0098	0.03
	28	0.0098	0.015

Table 5

 5 Distributions compared with K-L divergence to detect attacks

	Prefix	18	19	20	21	22	23	24	25	26	27	28
	M (attack)	0	0	0	0	0	0	0	0	0.5	0.5	0
	M (safe)	0.6	0.2	0.1	0.1	0	0	0	0	0	0	0
	T	1/2	1/2 2	1/2 3	1/2 4	1/2 5	1/2 6	1/2 7	1/2 8	1/2 9	1/2 10	1/2 11

Table 6

 6 Possible repartition of peers with common prefixes between 18 & 28 bits

	# of malicious	# of prefixes	Repartition of	# of simulated
	peers inserted	used	the peers	attacks
	10	1	10	11
	10	2	7-3	9
	10	2	5-5	9
	10	3	5-3-2	8
	10	4

Table 7

 7 Best remaining contacts with prefix under 18bits

	Prefix	Avg number of contacts
	13	0.60
	14	1.36
	15	2.78
	16	3.62
	17	3.75

  : nb lookup Output: prefixes distribution [ ] nb contacts=0; for i=0; i<nb lookup; i++ do rdm id = generate random id(); 10 best contacts [ ] = lookup(rdm id); foreach contact in 10 best contacts do current prefix = compute prefix(rdm id, contact); Algorithm to learn the regular distribution of prefixes from DHT lookups

	prefixes distribution [current prefix] ++;
	nb contacts ++;
	end
	end
	foreach pref ix in prefixes distribution do
	prefix = prefix / nb contacts;
	end
	Algorithm 2: 5 Conclusion

a zone is an artificial subdivision of the DHT address space considering only the first byte of the KADID (from 0x00 to 0xFF )

http://www.planet-lab.org/

https://gtk-gnutella.svn.sourceforge.net/svnroot/gtk-gnutella/trunk/ gtk-gnutella/


S Byrdina

C Rücker

M Zimmer

S Friedel
email: sven.friedel@comsol.com

U Serfling
email: serfling@ggl-gmbh.de

Self potential signals preceding variations of fumarole activity at Merapi volcano, Central Java

Keywords: self-potential monitoring, hydrothermal system, gas monitoring, Merapi

This paper analyzes simultaneous self-potential and gas temperature variations recorded at Merapi volcano in spring 2001, the dry season shortly after the volcanic crisis 2001. Temporal variations of fumarole gas temperature show characteristic quasi periodic signals at scales 1-8 hours and amplitudes up to ten degrees. We propose a simple graphical technique combining a wavelet scalogram and a cross-correlation analysis to demonstrate that the variations of gas temperature are systematically preceded by self-potential variations at the same scales. The influence of meteorological variations on these correlated signals can be ruled out. Rather, we suggest them to be related to the magma degassing in the upper conduits of the volcano. We discuss a semi-qualitative model to explain this correlation and the observed phase shift of about two hours.

Introduction

Merapi is one of the most active volcanoes in Indonesia, located on the Java Arc (Figure 1), where the Indo-Australian Plate is subducted beneath the Java Trench. Its characteristic activity consists of sequences of growth and gravitational collapse of a viscous andesitic dome [START_REF] Voight | Historical eruptions of Merapi volcano, Central Java[END_REF] producing pyroclastic flows. In addition to this regular activity, [START_REF] Voight | Historical eruptions of Merapi volcano, Central Java[END_REF] describe several major eruptions with VEI> 2 since 1768, like the explosion in 1822 which created a circular crater with 600 m diameter; the 1872 explosion completely destroyed the dome and created an oval crater 500 m deep; the eruption in 1930 with dome destruction and pyroclastic flows traveling up to 12 km. The time interval studied in the current paper was precedeed by few months by a partial dome collapse, occurred in early 2001. This minor event was typical for the activity of Merapi volcano in twentieth century. Two months before the first dome collapse an increase in frequency of volcano-tectonic and multi-phase earthquakes was observed, thereafter numerous pyroclastic flows were encountered which accompanied the growth of the new lava dome. The new dome reached a total volume of about 1.4 × 10 6 m 3 before it partially collapsed in two stages on January 28 and February 10.

The latest to date explosive crisis which happened in October-November 2010 was probably the most violent eruption since 1872. During this eruption with VEI≈ 4, a new summit crater with a diameter of 400 m was created, released ≈ 0.44 Tg of SO 2 , caused evacuation in a 20 km radius from the volcano and more than 350 fatalities [START_REF] Surono | The 2010 explosive eruption of Java's Merapi volcano a "100-year[END_REF]. This dangerous eruption behavior with possible influence of external factors like rainfall or tectonic activity (e.g. [START_REF] Voight | Historical eruptions of Merapi volcano, Central Java[END_REF][START_REF] Friedel | Self-potential and ground temperature at Merapi volcano prior to its crisis in the rainy season of 2000-2001[END_REF][START_REF] Harris | Regional earthquake as a trigger for enhanced volcanic activity: Evidence from MODIS thermal data[END_REF][START_REF] Surono | The 2010 explosive eruption of Java's Merapi volcano a "100-year[END_REF] motivates further studies aimed to improve multi-parameter monitoring techniques.

Traditional Merapi monitoring techniques include seismology, deformation, in-situ sampling of gas emissions, and petrology (e.g. [START_REF] Surono | The 2010 explosive eruption of Java's Merapi volcano a "100-year[END_REF], and references there) by the Indonesian Center of Volcanology and Geological Hazard Mitigation and its observatory and technology center in Yogyakarta, BPPTK. Continuous monitoring of geochemical parameters at the summit of Merapi was conducted during few weeks in 1998 and in 2000, when an automatic gas monitoring unit comprising gas chromatograph, an alpha scintillometer and temperature sensor was installed at Solfatara field Woro [START_REF] Zimmer | Continuous H2O, CO2, 222 Rn and temperature measurements on Merapi Volcano, Indonesia[END_REF]. The authors observed cyclic variations in the chemical composition of the gas associated with variations of its temperature. The gas temperature was found to increase when the concentration of the CO 2 increased and the concentration of H 2 O decreased (Figure 2).

The self-potential method is often used to characterize the extension of hydrothermal system, complimentary to geochemical data [START_REF] Lénat | Geolectrical structure of the central zone of Piton de la Fournaise volcano (La Réunion)[END_REF][START_REF] Finizola | Fluid circulation and strcutural discontinuities inside Misti volcano (Peru) inferred from self-potential measurements[END_REF][START_REF] Revil | Inner structure of La Fossa di Vulcano (Vulcano Island, southern Tyrrhenian Sea, Italy) revealed by high resolution electric resistivity tomography coupled with self-potential, temperature, and soil CO2 diffuse degassing measurements[END_REF][START_REF] Byrdina | Dipolar self-potential anomaly associated with carbon dioxide and radon flux at Syabru-Bensi hot springs in central Nepal[END_REF]. The major contributions of self-potential are created by the flow of the pore water dragging an excess of electrical charges existing in the vicinity of the mineral/water interface, the so-called streaming potential (e.g. [START_REF] Nourbehecht | Irreversible thermodynamic effects in inhomogeneous media and their application in certain geoelectric problems[END_REF][START_REF] Ishido | Experimental and theoretical basis of elektrokinetic phenomena in rock-water systems and its applications to geophysics[END_REF][START_REF] Revil | Streaming potential in porous media 1. Theory of the zeta potential[END_REF][START_REF] Revil | The volcano-electric effect[END_REF][START_REF] Crespy | Detection and localization of hydromechanical disturbances in a sandbox using the self-potential method[END_REF]. At Merapi volcano, a continuous monitoring of self-potential and ground temperatures was coducted from August, 2000to July, 2001, in order to retrieve information on subsurface water flow variations related to the volcanic activity [START_REF] Friedel | Self-potential and ground temperature at Merapi volcano prior to its crisis in the rainy season of 2000-2001[END_REF]. A clear correlation between self-potential, and seismic signals in ultra low frequency band was observed before the volcanic crisis in the early 2001, mostly during the rain season in November 2000 -January 2001 [START_REF] Byrdina | Self-potential variations associated with ultra-long-period seismic signals at Merapi volcano[END_REF]. Because of the strong influence of rainfall on self-potential and temperature, only repetitive or high-amplitude signals could be studied during the rain season. The present work deals with analysis of gas flow characteristics in Woro fumarole in dry season and during the period of relative quiescence following the 2001 volcanic crisis. The aim of the present work is to detect the common gas temperature and the self-potential signals reflecting the variations in magmatic degassing during an inter-eruptive period.

Experiment and Instruments

A continuous monitoring station for electrical field and ground temperatures was installed in August 2000, in 200 m distance from the dome and several meters away from the fumarolic vents of Woro (Figure 1 b). The station included three electrode pairs, two in North-South direction with lengths of 50 and 75 m and one in East-West direction of 50 m length. We called them in the following the SP dipoles U 21 , U 43 , and U 65 . Two electrodes, E 2 and E 5 , were placed in a direct vicinity of fumarole vents, E 5 was only few meters away from the fumarole temperature sensor GC. We used non-polarizable Ag/AgCl electrodes designed by the Geophysical Instrument Pool Potsdam. Voltage differences were sampled at 20 sps with a resolution of 0.2 µV. Each electrode was equipped with a PT1000 temperature sensor at the depth of installation 0.7-0.8 m. The temperature data were sampled at 4 sps with a resolution of 0.1 • C using a Guralp CMG 24 digitizer with GPS clock synchronization. We refer to [START_REF] Friedel | Self-potential and ground temperature at Merapi volcano prior to its crisis in the rainy season of 2000-2001[END_REF] for a more detailed description of the setup. In the following, analogous to the notation of [START_REF] Friedel | Self-potential and ground temperature at Merapi volcano prior to its crisis in the rainy season of 2000-2001[END_REF], the self-potential data are referred to as U 21 = U 2 -U 1 , the potential difference measured between the electrodes E 2 and E 1 etc. Similarly, the difference of the ground temperature at the electrode positions (called in the following electrode temperature difference) T 21 = T 2 -T 1 etc. Ground temperatures varied between 40 and 70 • C except for sensor T 4 whose maximal temperature reached 100 • C. In order to obtain the same sampling as for gas temperature, all data were down-sampled to 1 sample per minute using median filtering. The median was preferred to simple moving averages or low-pass filters in the frequency domain because of its robustness against outliers.

The fumarole gas temperature sensor, a Ni-Cr/Ni thermocouple at 30 cm depth, replaced a gas chromatograph installed in 1998 at a location indicated as GC in Figure 1 c (for more details see [START_REF] Zimmer | Continuous H2O, CO2, 222 Rn and temperature measurements on Merapi Volcano, Indonesia[END_REF]. During the main dome collapse of February 10, 2001, the station was partially destroyed and was be reactivated 2 months later starting on April 6, 2001.

Data analysis

The classical measure of the correlation between two time series with a time shift between them is given by a cross-correlation function. Its Fourier transform, the cross power spectral density, gives the frequency range of correlation. This analysis is best suited for stationary signals with good signal-to-noise ratio, otherwise the maximum of the cross-correlation function is not pronounced enough to identify a correlation between the time series (Figure 3 a,b).

To find the correlation of intermittent and noisy signals, we propose a technique based on wavelet analysis and cross correlation analysis which allows to detect both the time scale with maximal signal correlation and a possible time-shift. The idea is to use the time-frequency representation offered by the wavelet analysis; and to use as an advantage a compact support of the wavelet basis in order to focus the cross-correlation analysis on the significant time scales of the signal.

Wavelet transform. Time-frequency representation.

The complex wavelet transforms the signal x(t) using the dilated and time shifted versions of a basis function called basis wavelet ψ Mallat (1999):

W (a, b) = a -1/2 ∞ -∞ x(t) ψ * t -b a dt (1)
where the wavelet coefficients W(a,b) give the transformed signal as a function of the translation parameter b, and the dilatation parameter a (scale). We used the Morlet wavelet which is a complex sinus wave with a Gaussian envelope

ψ(t) = π -1/4 e iω 0 t e -t 2 /2 . ( 2
)
We used logarithmically equidistant values for a (dyadic grid). In this notation, the time is unitless. This wavelet was used to plot the time-frequency wavelet spectrum -the scalogram given by

| W (a, b) | 2 .
The Fourier transform of the Morlet wavelet is a Gaussian with positive frequencies for ω 0 ≥ 5 (we used ω 0 = 5.): The scale -frequency relationship of the Morlet wavelet is given by

ω = ω 0 a (3)
The wavelet coefficients at every scale are the Hilbert transformed original data (analytic signal) bandpass filtered by the Gaussian envelope with center frequency ω given by equation 3.

Linear cross-correlation function of the wavelet coefficients

The next step is the calculation of the linear cross-correlation function P (X, Y ) where the data X and Y are replaced by their complex wavelet coefficients

W x = W x (a, b) and W y = W y (a, b) P W xy (a, b) = N -b i W x i+b -W x W y i -W y N i (W x i -W x) 2 N i (W y i -W y) 2 (4)

Data basis and Observations

Figure 4 shows gas temperature data, self-potential and ground temperature data after the end of the rain season and re-installation of the sensor in April and till June 2001. Ground temperatures T 4 and T 6 are not presented here. Sensor T 4 was placed in a permeable erosive channel with much higher temperatures (up to 100 • C) and larger temporal variations than the other temperature sensors, and sensor T 6 was damaged all through the period of observation.

Though no rain data in this time interval are available, we suggest that no rainfall happened between Julian days 110 and 137 (from April 19th to May 16th). As detailed by [START_REF] Friedel | Self-potential and ground temperature at Merapi volcano prior to its crisis in the rainy season of 2000-2001[END_REF], both self-potential and electrode temperature difference data at this station respond similarly to the rainfall with typical high amplitudes (up to 300 • C in gas temperature and 50 mV in selfpotential data), sharp onset and exponential decay; moreover, a high linear correlation between the self-potential and electrode temperatures is usually observed during the rainfall. The absence of such correlated self-potential and electrode temperature signals, as well as the small amplitudes of variations in all observables suggest that no rainfall happened in this time interval, which was therefore chosen for a closer study. Amplitude spectra of the time series presented in Figure 4 can be seen in Figure 5. Daily and semi-diurnal variations dominate the ground temperature and self-potential spectra but are less spectacular in the spectrum of gas temperature where a large part of the signal energy is distributed between 2 and 8 hour periods. Interestingly, the self potential spectra also contain some signal energy at these periods, in contrast to ground temperature data.

To explore the correlation between self-potential and gas temperature, cross-correlation plots of wavelet coefficients were calculated as described in section 3; they are shown in Figure 6 a, b and c. The scale range of correlation between 1 and 8 hours corresponds roughly to the typical signal durations observed by [START_REF] Zimmer | Continuous H2O, CO2, 222 Rn and temperature measurements on Merapi Volcano, Indonesia[END_REF] in gas concentration and gas temperature data.

These periods are hardly visible in the Fourier spectra of the gas temperature in Figure 5 a. The broad maximum of the correlation is located at scales 1.5-8 hours and a time shift of 130 min at all three dipoles; self-potential signals precede gas temperature variations. Interestingly, contrary to the rain season (see discussion in [START_REF] Friedel | Self-potential and ground temperature at Merapi volcano prior to its crisis in the rainy season of 2000-2001[END_REF], no correlation at all is found between gas temperature and ground temperature (d,e), and no correlation is observed between the selfpotential and ground temperature difference (f). The time frequency representation in Figure 7 a, b shows striking similarity between the variations of gas temperature and self-potential. Wavelet coefficients at one scale (2.2 hours) are displayed in c. Gas temperature variations (red curve) are clearly delayed with respect to the self-potential at both dipoles shown with blue and black lines.

Figure 8 plots fumarole temperature data versus self-potential U 21 . Both gas and self-potential data were high-pass filtered with 2.9 h corner period. This choice of the corner period allows to exclude the 6-and 3 h harmonics of the barometric pressure variations. Furthermore, gas temperature data were time shifted with respect to the self-potential in order to align the correlating signals.

Discussion

We observed a correlation between the cyclic variations in gas temperature and self-potential which we attribute to the variations of the magma degassing for the following reasons. Firstly, we can exclude meteorological influence. As discussed by [START_REF] Friedel | Self-potential and ground temperature at Merapi volcano prior to its crisis in the rainy season of 2000-2001[END_REF], rainfall induced SP signals can be recognized even without reference precipitation data because they have a very typical shape, extremely large amplitudes and correlate positively with the ground temperature data (with the linear correlation coefficient up to R 2 = 9.8 !) Quasi-periodic signals observed in self-potential and gas temperature data can not be attributed to atmospheric pressure neither, as typical signal durations vary from 1 to 8 hours and do not generally coincide with the harmonics of barometric pressure.

Secondly, the isotopic studies of [START_REF] Toutain | Structure and CO2 budget of Merapi volcano during inter-eruptive periods[END_REF] reveal the magmatic origin of CO 2 in fumarole Woro. Clear correlation gas concentrations and temperature analyzed by [START_REF] Zimmer | Continuous H2O, CO2, 222 Rn and temperature measurements on Merapi Volcano, Indonesia[END_REF] and presented in Figure 2 suggest that these regularly oscillations of gas parameters are directly related to magma degassing and are generated by regular oscillations of pressure, which generate also the related self-potential variations. The whole area is characterized by intense diffuse degassing, with carbon dioxide concentrations as high as 500 000 ppm in September 2002, as reported by [START_REF] Toutain | Structure and CO2 budget of Merapi volcano during inter-eruptive periods[END_REF]. Nevertheless, the ground temperatures at the electrode locations did not record any temperature changes, related to variations in gas temperature. These observations indicate that self-potential oscillations are generated by a mechanism other than diffuse soil degassing or pure temperature effects at the electrode locations. In addition, oscillations in gas temperature are preceded by self-potential signals with a time shift of more than two hours indicating a relatively deep source of self-potential. Interestingly, these common oscillations of self-potential and gas temperature have signatures very different from earlier observations related to the rain season preceding the eruption in February 2001 [START_REF] Byrdina | Self-potential variations associated with ultra-long-period seismic signals at Merapi volcano[END_REF][START_REF] Richter | Correlation of seismic activity and fumarole temperature at the Mt. Merapi volcano (Indonesia) in 2000[END_REF]. These authors observed that ultra-long period (ULP) seismic events were systematically accompanied by variations of both fumarole temperature [START_REF] Richter | Correlation of seismic activity and fumarole temperature at the Mt. Merapi volcano (Indonesia) in 2000[END_REF] and self-potential [START_REF] Byrdina | Self-potential variations associated with ultra-long-period seismic signals at Merapi volcano[END_REF] without any significant time shift between them. Returning to oscillations of self-potential and gas temperature during the dry season, we suppose them to be generated by a deeper source than the source of ULP seismicity because of a larger time shift between the self-potential and gas temperature. In this case, the time shift between gas temperature and selfpotential might contain information about the properties of the magmatic conduits or about the depth where the pressure pulses are originated.

For example, [START_REF] Cigolini | Earthquake-volcano interactions detected from radon degassing at Stromboli (Italy)[END_REF] report radon emissions at Stromboli volcano related to Palermo earthquake of September 6th, 2002. The regional seismicity was found to be correlated with radon emissions and the rate of erupted magma volume. The time delay of radon emissions with respect to seismicity was interpreted by viscoelastic properties of the magma chamber. Furthermore, [START_REF] Olmos | Anomalous Emissions of SO2 During the Recent Eruption of Santa Ana Volcano, El Salvador, Central America[END_REF] observed a time delay of SO 2 emissions with respect to real time seismic amplitude measurements at Santa Ana volcano.

Physical models related to cyclic behavior of volcanic degassing in andesitic magmas are usually based on nonlinearities caused by the variable viscosity of magma. In these models, viscosity of magma depends on volatile content, temperature or pressure, and strongly decreases as the degassing rate increases (e.g. [START_REF] Melnik | Non-linear dynamics of lava dome extrusion[END_REF][START_REF] Lensky | Cyclic activity at Soufriere Hills Volcano, Montserrat: degassing-induced pressurization and stick-slip extrusion[END_REF]). An example is the stick-slip model of supersaturated magma degassing developed by [START_REF] Lensky | Cyclic activity at Soufriere Hills Volcano, Montserrat: degassing-induced pressurization and stick-slip extrusion[END_REF]. The gas diffuses into the magma, which cannot expand because of the presence of a sticking plug resulting in a build-up of pressure. When the pressure exceeds some critical value, the strength of the plug, the stick-slip motion occurs and the pressure is relieved. The magma sticks again when the pressure falls below the value of dynamic friction. Although the available data are not sufficient to attempt a numerical modeling, we can try to understand the information contained in the time shift between the gas temperature and the electric signals. In the logic of the stick-slip model we expect the electric potential to be generated during the phase where the pressure drop is maximal.

The time shift would give the travel time of the gas from the source of pressure (e.g. the base of the plug) to the surface which would bring some constraints on the depth of the source of pressure as we will show in the following. The flow of a compressible ideal gas (P u =constant) in the porous conduit is described by a modification of Darcy equation (e.g. [START_REF] Scheidegger | The physics of flow through porous media, 3rd Edition[END_REF]:

u = k µ • P 2 d -P 2 s L • P s (5)
where u is the gas flux velocity in z-direction [m/s], k is the permeability in [m -2 ], µ is the dynamic viscosity of the gas in [Pa s]. P d and P s are the pressures at the source and at the surface in Pa, indices stay for "depth" and "surface". L is the depth of the fumarole origin which can be expressed as L = u • δt where δt is the time delay of the gas in relation with self-potential. Now we estimate the average gas pressure at the pressure source (Figure 9). The relationship between the gas pressure at magma temperature T d = 1000 • C and the gas pressure at the surface, at the temperature of T s = 450 • C, follows from state equation of ideal gas:

P d P s (γ-1)/γ = T d T s , ( 6
)
where γ is the ratio of specific heats at constant pressure and constant volume c p /c v ≈ 1.3. We obtain from equation ( 6) the P d = 2 MPa considering the atmospheric pressure at the surface.

Returning now to equation ( 5), we take k = 10 -11 m 2 for the unknown conduit permeability and µ = 2 • 10 -5 Pa•s for the dynamic viscosity of the water vapor at 400 • C (e.g. [START_REF] Mende | Physik -Gleichungen und Tabellen[END_REF], and obtain finally the estimation of darcy velocity u ≈ 0.04 m/s and the depth of

≈ 300 m.
It is premature to take uncritically any estimations on the basis of self-potential data from one single location. The present study gives a direct evidence that the pressure variations in the magma conduit create measurable self-potential variations. However, in order to obtain quantitative information on the pressure source from self-potential monitoring data, it is advantageous to know the geometry of the flow system from previous structural self-potential studies (e.g. [START_REF] Aizawa | Groundwater flow and hydrothermal systems within volcanic edifices: Delineation by electric self-potential and magnetotellurics[END_REF]. In addition, it is necessary to use several monitoring stations in order to characterize the attenuation of the self-potential transients with distance and to obtain a reliable estimate on the time delay between the self-potential and gas temperature variations.

Conclusion

Gas fumarole data and self-potential data collected at Solfatara Woro show correlating events at scales 1-8 h with a time shift of approximately 130 min. The correlation was observed at all three dipoles during a time interval of 40 days. The influence of different meteorological factors on both data sets could be excluded because 1) temperatures at electrode positions showed no correlation neither with self-potential nor with gas temperatures, 2) the typical signal durations do not coincide with the harmonics of atmospheric pressure, 3) the absence of response signals characteristic for rainfall in both self-potential and gas temperature data suggest that the correlation between selfpotential and gas temperature can not be attributed to the rainfall. 4) geochemical data indicate the magmatic origin of several fumarolic gas components [START_REF] Toutain | Structure and CO2 budget of Merapi volcano during inter-eruptive periods[END_REF].

  for each scale a and for reasonable time shifts b. The cross-correlation function of the wavelet coefficients P W x,W y (a, b) is then plotted as a function of scale a and time delay b between both time series. If the value of P W x,W y (a, b) is close to unity at a scale a d and at a time shift b d , there is a correlation between signals with dominant frequency corresponding to the scale a d and a time delay b d . Figure 3 shows an example of synthetic time series containing intermittent signals superimposed with random noise. The cross-correlation plot of wavelet coefficients in Figure 3 c possesses a clear maximum. Its ordinate indicates the scales at which the data contain correlated signals, and its abscissa indicates the time shift between them.

Figure 1 Figure 2 :

 12 Figure 1: a) Simplified map of Java with location of Merapi volcano and Java trench. b) Summit area of Merapi after Camus et al. (2000), with main lava flows until 2000, crater rims, active dome, and Woro fumarole field. c) Location of our monitoring station at Woro with self-potential dipoles and gas temperature sensor. Gray circles indicate fumaroles (modified from Byrdina et al. (2003)).

Figure 3 :

 3 Figure 3: a) Two synthetic data sets X and Y (black lines) were created by superimposing random noise with two identical features A and B with time shift 20 and 15 hours. b) Cross-correlation function does not show any clear maxima. c) Cross-correlation of wavelet coefficients of X and Y separates the scales of correlation and gives the time shifts between both signals.

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Time series of fumarolic temperature, self-potential and ground temperature. See Figure 1 for location of the sensors. Data from the time period between day 110 and 137 of year 2001 without any perturbations were taken for a further study.

Figure 7 :

 7 Figure 7: Time-frequency representation of gas temperature (a) and self-potential dipole U21 (b). Time in Julian days is represented in X and scales in Y axes. c) Wavelet coefficients at scale of maximal correlation (≈ 2.2 hours)for the gas temperature, self-potential at two dipoles, and for electrode temperature difference T2 -T1.

Figure 8 :

 8 Figure8: Gas temperature data versus self-potential U21 at period range from 2 min to 170 min. Both kinds of time series were high-pass filtered, gas temperature data were time shifted to align the correlated signals.

Acknowledgments

The work was partially supported by DFG Ja 590/6. We thank the personnel at BPPTK, Jogjakarta. We thank Jean Vandemeulebrouck, Eric Delcher and André Revil for interesting discussions improving the paper. We thank J.F. Lénat and an anonymous reviewer for their constructive contributions to our manuscript. The non-polarizable electrodes were borrowed at the Geophysical Instrument Pool Potsdam (GIPP) of the German Research Centre for Geosciences (GeoForschungszentrum Potsdam, GFZ). We used Latex, JabRef, and InkSpace open source software.