No description available.

In many network applications, such as the Internet and infrastructure networks, nodes fail or get congested dynamically, but tracking this information about all the nodes in a network where some dynamical processes are taking place is a fundamental problem. In this work, we study the problem of inferring the complete set of failed nodes, when only a sample of the node failures are known---we will be referring to this particular problem as prob{} . We consider the setting in which there exists correlations between node failures in networks, which has been studied in the case of many infrastructure networks. We formalize the prob{} problem using the Minimum Description Length (MDL) principle and we show that, in general, finding solutions that minimize the MDL cost is hard, and develop efficient algorithms with rigorous performance guarantees for finding near-optimal MDL cost solutions. We evaluate our methods on both synthetic and real world datasets, which includes the one from WAZE. WAZE is a crowd-sourced road navigation tool, that collects and presents the traffic incident reports. We found that the proposed greedy algorithm for this problem is able to recover $80%$, on average, of the failed nodes in a network for a given partial sample of input failures, which are sampled from the true set of failures at some predefined rate. Furthermore, we have also proved that this algorithm will find a solution that has MDL cost with an additive approximation guarantee of log(n) from the optimal. / Master of Science

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.