Overlay routing has been successful as an incremental method to improve the current Internet routing by allowing users to select the Internet paths by themselves. By its nature, overlay routing has selfish behavior, which makes impact on the related components of the Internet routing. In this thesis, we study three interactions related to overlay routing. First, overlay routing changes the traffic patterns observed by the network operating side, which uses traffic engineering techniques to cope with the dynamic traffic demands. We improve this vertical interaction between overlay routing and traffic engineering. Secondly, the performance of overlay routing may be affected by the action of other coexisting overlays. An initial result on the horizontal interaction among multiple overlays is given. Lastly, within a single overlay network, overlay nodes can be regarded as independent decision makers, who act strategically to maximize individual gain. We design an incentive-based framework to achieve Pareto-optimality in the internal interaction of overlay routing.

Das Internet und darauf aufbauende Infrastrukturen haben sich als zentrale Medien zum weltweiten Abruf und Austausch von Informationen etabliert. Im Zuge dessen ist das Internet ein wichtiges Werkzeug zur globalen Vernetzung von Aktivisten und Journalisten geworden, welche dieses zudem als Plattform zur Veröffentlichung von Rechercheergebnissen und Beweismaterial verwenden. Um den Zugang zu kompromittierenden oder als unerwünscht erachteten Informationen über das Internet zu unterbinden, haben jedoch Regierungen weltweit weitreichende technische Zensurmaßnahmen implementiert. Um diesen Maßnahmen entgegenzuwirken sind Betroffene darauf angewiesen, ihre digitale Kommunikation über Geräte von Drittanbietern zu leiten, welche sich außerhalb des Einflussbereichs des Zensors befinden und deren Rolle als Umgehungsknoten für den Zensor schwer zu detektieren ist. Eine vielversprechender Ansatz zur Realisierung solcher Gegenmaßnahmen sind Friend-to-Friend (F2F) Overlay-Netzwerke. Ähnlich zu Anonymisierungsnetzwerken wie Tor und AN.ON setzen sich F2F Overlays aus den Knoten von mehreren Betreibern zusammen, wodurch ein Single Point of Failure vermieden wird. Um gegen Unterwanderung zu schützen wird jedoch die Kommunikation zwischen den Knoten in F2F Overlays auf jene Paare beschränkt, deren Betreiber sich gegenseitig vertrauen. Folglich erfordert das Aufdecken der Knoten eines F2F Overlays die Identifizierung und Kompromittierung deren Betreiber durch den Zensor mit Hilfe von Social-Engineering-Methoden. Um Anwendungsfälle wie anonymes Blogging zu unterstützen, benötigen F2F Overlays ein Routing-Protokoll, welches Datenübertragungen zwischen Knoten ohne wechselseitig vertraute Betreiber ermöglicht. Aufgrund seiner hohen Effizienz und Ausfalltoleranz gilt Routing anhand von Rooted Spanning Tree (RST) Embeddings hierfür als besonders vielversprechender Kandidat. Dabei wählen die teilnehmenden Knoten zunächst einen Knoten als Wurzel und formen, ausgehend von diesem, einen virtuellen Wurzelbaum über das F2F Overlay. Anschließend wird jedem Knoten eine virtuelle Adresse zugewiesen, welche dessen Position in dem zuvor erzeugten Wurzelbaum eindeutig repräsentiert. In F2F Overlays muss davon ausgegangen werden, dass ein Zensor, welcher einen Teil der Knotenbetreiber kompromittieren konnte, mit Hilfe eigener Knoten aktive Angriffe auf das Routing durchführt, um die Verbreitung von Inhalten zu unterbinden. Bisherige Forschung zu Routing anhand von RST Embeddings konzentriert sich jedoch primär auf die Steigerung dessen Effizienz sowie der Verbesserung dessen Robustheit gegenüber permanenter Ausfälle. In dieser Arbeit werden bisher unbekannte Angriffe auf RST-Embedding-basierte Routing-Protokolle vorgestellt, welche von bösartigen F2F-Overlay-Teilnehmern mit geringem Aufwand durchgeführt werden können. Ergänzend stellen wir anschließend Maßnahmen vor, welche derartige Routing-Protokolle inhärent robuster gegen Fehlverhalten machen. Ein wesentlicher Einflussfaktor bezüglich der Effektivität der identifizierten Angriffe ist die Tatsache, ob der gewählte Wurzelknoten ein Knoten des Angreifers ist oder nicht. Während die von uns vorgestellten Schutzmaßnahmen die Auswirkung der Angriffe auch in dem Fall begrenzen, dass der Wurzelnoten sich bösartig verhält, so erfordert das Routing von Nachrichten dabei nichtsdestotrotz erhöhten Aufwand bei gleichzeitig reduzierter Erfolgswahrscheinlichkeit. Die Wurzelwahlverfahren bisheriger RST-Embedding-basierter Routing-Protokolle können in F2F Overlays jedoch nicht auf sichere Weise umgesetzt werden, so dass ein Angreifer mit geringem Aufwand erreichen kann, dass einer seiner Knoten als Wurzel gewählt wird. Während es in F2F Overlays allgemein nicht ausgeschlossen werden kann, dass ein bösartiger Knoten als Wurzel gewählt wird, so ist es dennoch erstrebenswert, die Wahrscheinlichkeit der Wahl eines nicht-bösartigen Knotens zu erhöhen. Da bisherige Verfahren zur sicheren, verteilten Wahl eines Knotens nicht effektiv in F2F Overlays umgesetzt werden können, wird in dieser Arbeit ein neues Wurzelwahlverfahren vorgestellt. Dieses basiert auf lokalen, randomisierten Mehrheitsentscheidungen, um einen Konsens auf einen einzelnen Knoten herbeizuführen. Ergänzend dazu werden Ergebnisse einer Simulationsstudie anhand realer sozialer Graphen vorgestellt, welche belegen, dass dieser Ansatz einer Unterwanderung widersteht, wenn der Angreifer eine geringe Anzahl von Teilnehmern kompromittieren konnte. Gleichzeitig legen die Ergebnisse der Studie nahe, dass dieses Verfahren auch in F2F Overlays mit zehntausenden von Knoten in kurzer Zeit eine Einigung auf einen gemeinsamen Wurzelknoten für den Großteil der Knoten erreicht. Zur Effizienzsteigerung leiten aktuelle RST-Embedding-basierte Routing-Protokolle die Addressen anhand von Breitensuchbäumen ab. Der Aufbau derartiger Bäume erfordert jedoch, dass jeder Knoten seinem Nachbarn die eigene Hop-Distanz zum Wurzelknoten mitteilt. Dabei können Angreiferknoten gezielt inkorrekte Distanzwerte versenden, um die Anzahl der gutartigen Knoten zu maximieren, welche diese als Elternknoten wählen und folglich von anschließenden Angriffen betroffen sind. Um derartige Angriffe zu unterbinden, wird in dieser Arbeit zudem ein verteilter, selbststabilisierender Algorithmus zum Aufbau von Breitensuchbäumen vorgestellt. Dieser verwendet kryptografische Signaturen in Kombination mit Zeitstempeln, um inkorrekte sowie veraltete Distanzwerte erkennbar zu machen. Die Nutzung von RST Embeddings birgt neben Angriffen auf deren Verfügbarkeit das Risiko, dass ein interner Angreifer Informationen über die Topologie des zugrundeliegenden Netzwerkes gewinnen kann. Im Kontext von F2F Overlays ist dies problematisch, da deren Struktur dem sozialen Netzwerk deren Teilnehmern entspricht. Erlangt ein Angreifer einen Schnappschuss der Topologie eines F2F Overlays oder eines Teils davon, so kann er diesen mit der Topologie anderer sozialer Netzwerkgraphen abgleichen, um bisher unbekannte Teilnehmer aufzudecken. Das konkrete Ausmaß, in dem RST Embeddings sowie das darauf aufbauende Routing Rückschlüsse über die Topologie des Netzwerkes zulassen wurde bisher jedoch nicht untersucht. Der vierte Beitrag dieser Dissertation besteht daher aus einer detaillierten Analyse bezüglich der konkreten Informationen, welche ein interner Angreifer anhand der durch RST-Embedding-basierte Routing-Protokolle propagierten Daten gewinnen kann. / Today, the Internet plays a vital role in enabling activists and journalists to collaborate and to publish critical information on a global scale. As a consequence, governments around the globe have implemented technical censorship measures to keep citizens from accessing content that is deemed inappropriate or compromising. To address such censorship measures, a circumvention infrastructure is needed that allows affected individuals to route their online communication through third-party servers that are outside of the censor’s influence and whose use for circumvention is difficult to detect for the censor. A promising substrate to realize such an infrastructure are Friend-to-Friend (F2F) overlay networks. Similar to anonymization networks like Tor and AN.ON, F2F overlay nodes may be operated by different individuals, thus avoiding a single point of failure. To protect against infiltration, F2F overlays additionally restrict communication between participating devices to those pairs whose operators mutually trust each other. Thus, censors need to perform social engineering in order to discover operators and their nodes. To realize use cases that require communication between nodes of participants without mutual trust, such as distributed and redundant content storage or anonymous blogging, F2F overlays require a routing protocol suitable for large, dynamic networks. Among the current research on routing protocols for F2F overlays, routing based on rooted spanning tree (RST) embeddings emerged as the most promising candidate due to its high efficiency and fault tolerance. In this approach, nodes collaboratively determine a rooted spanning tree over the overlay topology and, starting from the elected root node, assign each node a virtual address that encodes its unique position in the tree. Given that a censor may compromise a fraction of the participants of an F2F overlay, it is likely that the censor will use nodes under their control to actively attack the routing protocol in order to disrupt communication. However, existing research on RST embeddings concentrates on their efficient implementation as well as resilience to permanent faults, thus leaving open in which ways such routing protocols can be attacked. Towards this end, this thesis presents previously unknown attacks that malicious participants of an F2F overlay can easily perform against state-of-the-art routing protocols. As these attacks cannot be reliably attributed to malicious nodes, we propose countermeasures that improve the inherent resilience of such protocols against misbehaving nodes. A fundamental risk that cannot completely be avoided in F2F overlays is that a malicious node may be chosen as the root node of the embedding, giving it a particularly strong position for attacks. While our proposed countermeasures limit the impact of malicious root behavior, routing in such a scenario nonetheless comes at the cost of increased routing overhead and an increased chance of routing failure. Since existing routing protocols based on RST embeddings employ insecure root election schemes, it is desirable to increase the likelihood that a benign node is chosen as root. Because existing secure protocols for node election cannot be used effectively in F2F overlays, we propose a novel root election protocol that leverages local voting algorithms to reach consensus on a single node. Simulations on real-world social graphs show that in F2F overlays, the protocol is able to reach consensus among a large fraction of nodes quickly and, in contrast to election protocols used by state-of-the-art routing algorithms, resists compromise by malicious nodes. To improve efficiency, state-of-the-art protocols embed breadth-first-search (BFS) trees for address assignment, whose formation relies on the truthful reporting of hop distances. In the presence of a benign root node, malicious nodes may deliberately propagate incorrect distance values to maximize the number of benign nodes that choose them as parent, thus increasing the impact of subsequent attacks. To defend against such misbehavior, we furthermore propose a self-stabilizing BFS formation algorithm that leverages cryptographic signatures to make incorrectly reported distances detectable. Additional to the risk of attacks aiming at the disruption of communication, RST embeddings and the routing based on them inherently leaks information about the topology of the underlying network to its participants. Such leakage is problematic in F2F overlays, as topology snapshots can be linked with graph data from further sources in order to identify participants. However, the concrete inferences malicious participants can make from the routing control data propagated by state-of-the-art protocols has not been investigated so far. The fourth contribution of this thesis therefore lies in the analysis of which information about the topology of an F2F overlay malicious participants can infer from the control data propagated by RST embedding algorithms as well as the resulting routing of messages.

Overlay networks have recently gained popularity as a viable alternative to overcome functionality limitations of the Internet (e.g., lack of QoS, multicast routing). They offer enhanced functionality to end-users by forming an independent and customizable virtual network over the native network. Typically, the routing at the overlay layer operates independent of that at the underlying native layer. There are several potential problems with this approach because overlay networks are selfish entities that are chiefly concerned with achieving the routing objective of their own users. This leads to complex cross-layer interactions between the native and overlay layers, and often tends to degrade the achieved performance for both layers. As overlay applications proliferate and the amount of selfish overlay traffic surges, there is a clear need for understanding the complex interactions and for strategies to manage them appropriately. Our work addresses these issues in the context of "service overlay networks", which represent virtual networks formed of persistent nodes that collaborate to offer improved services to actual end-systems. Typically, service overlays alter the route between the overlay nodes in a dynamic manner in order to satisfy a selfish objective. The objective of this thesis is to improve the stability and performance of overlay routing in this multi-layer environment. <br><br> We investigate the common problems of functionality overlap, lack of cross-layer awareness, mismatch or misalignment in routing objectives and the contention for native resources between the two layers. These problems often lead to deterioration in performance for the end-users. This thesis presents an analysis of the cross-layer interaction during fault recovery, inter-domain policy enforcement and traffic engineering in the multi-layer context. Based on our characterization of the interaction, we propose effective strategies that improve overall routing performance, with minimal side-effects on other traffic. These strategies typically 1) increase the layer-awareness (awareness of information about the other layer) at each layer, 2) introduce better control over routing dynamics and 3) offer improved overlay node placement options. Our results demonstrate how applying these strategies lead to better management of the cross-layer interaction, which in turn leads to improved routing performance for end-users.

No description available.