We investigate the hardness of malicious attacks on multiple-tree topologies of push-based Peer-to-Peer streaming systems. In particular, we study the optimization problem of finding a minimum set of target nodes to achieve a certain damage objective. For this, we differentiate between three natural and increasingly complex damage types: global packet loss, service loss when using Multiple Description Coding, and service loss when using Forward Error Correction. We show that each of these attack problems is NP-hard, even for an idealized attacker with global knowledge about the topology. Despite tree-based topologies seem susceptible to such attacks, we can even prove that (under strong assumptions about NP) there is no polynomial time attacker, capable of guaranteeing a general solution quality within factors of c_1 \log (n) and c_2 2^{\log^{1-\delta } n} (with n topology nodes, \delta = 1 / \log \log^d n for d<1/2 and constants c_1, c_2), respectively. To our knowledge, these are the first lower bounds on the quality of polynomial time attacks on P2P streaming topologies. The results naturally apply to major real-world DoS attackers and show hard limits for their possibilities. In addition, they demonstrate superior stability of Forward Error Correction systems compared to Multiple Description Coding and give theoretical foundation to properties of stable topologies.

By monitoring the exchanged IPsec traffic an adversary can usually easily discover the layout of virtual private networks (VPNs). Of even worse extend is the disclosure if compromised IPsec gateways are considered, for example in remote environments. This revelation enables attackers to identify vital components and may allow him to compromise the availability of the overall infrastructure by launching well-targeted denial-of-service (DoS) attacks against them. In this article we present a formal model to analyze the resilience of VPN infrastructures against DoS attacks, to estimate the impact of compromised gateways, and to formalize the planning process of more resilient infrastructures.

Using a peer-to-peer approach for live multimedia streaming applications offers the promise to obtain a highly scalable, decentralized, and robust distribution service. When constructing streaming topologies, however, specific care has to be taken in order to ensure that quality of service requirements in terms of delay, jitter, packet loss, and stability against deliberate denial of service attacks are met. In this paper, we concentrate on the latter requirement of stability against denial-of-service attacks. We present an analytical model to assess the stability of overlay streaming topologies and describe attack strategies. Building on this, we describe topologies, which are optimally stable toward perfect attacks based on global knowledge, and give a mathematical proof of their optimality. The formal construction and analysis of these topologies using global knowledge lead us to strategies for distributed procedures, which are able to construct resilient topologies in scenarios, where global knowledge can not be gathered. Experimental results show that the topologies created in such a real-world scenario are close to optimally stable toward perfect denial of service attacks.

Abstract. In this paper we define a type of cohesive subgroups – called communities – in hypergraphs, based on the edge connectivity of subhy-pergraphs. We describe a simple algorithm for the construction of these sets and show, based on examples from image segmentation and infor-mation retrieval, that these groups may be useful for the analysis and accessibility of large graphs and hypergraphs. 1

PageRank, one part of the search engine Google, is one of the most prominent link-based rankings of documents in the World Wide Web. Usually it is described as a Markov chain modeling a specific random surfer. In this article, an alternative representation as a power series is given. Nonetheless, it is possible to interpret the values as probabilities in a random surfer setting, differing from the usual one.Using the new description we restate and extend some results concerning the convergence of the standard iteration used for PageRank. Furthermore we take a closer look at sinks and sources, leading to some suggestions for faster implementations.