Leveraging Network Maps to Improve Evaluations of Overlay System Performance and Security

Distributed systems often communicate through overlay networks , which use custom addressing and protocols to communicate between participating nodes at the application layer, but route those custom messages over the standard network infrastructure. Overlay networks enable application system designers to focus on the intended operation of their system distinct from the network layer. This can have several benefits: improvements at lower levels of the technology stack can be assimilated without modifying the application layer protocol, and modeling application behavior is easier because the protocol doesn't depend on network interactions.;However, while this enables overlay networks to be easily studied and modeled, this very abstraction can make it difficult to understand how their interaction with the network underlay affects them. Ideally the application's behavior would be completely isolated from the network layer, but in practice this is rarely the case. For instance, application layer modeling cannot easily predict exactly how a widespread deployment will behave; security and performance can both be affected by the path overlay networks take through the underlay network. This can make conscientious operators of overlay networks hesitant to make large modifications to their protocol for fear its interaction with lower layers, once distributed across the internet, will have unintended effects. For instance, the Tor Project, which manages the Tor anonymity network [18], is relatively conservative with respect to protocol changes, in part because of fears that a change might affect anonymity through some unexpected interaction with the underlying network, whether due to routing or performance.;The goal of this thesis is to introduce network maps which can be used to effectively evaluate overlay network technologies with respect to both performance and anonymity within evaluation platforms that provide a safe environment for experimentation. Safe evaluation environments are critical in that they permit modification of core protocols without affecting active system users. We discuss the advantages and disadvantages posed by different classes of evaluation platforms and how they can interface with our proposed network maps.;We present a series of techniques for constructing these network maps which combine network information from disparate sources into large graphs which represent the global internet. For each type of network data, we discuss the sources from which they can be obtained and the types of inaccuracies they can introduce in network evaluations. Given the set of available data, we propose methods for constructing network maps by combining these sources of information.;We develop maps at two granularity levels, then present several case studies which use the proposed mapping techniques in combination with several platforms to perform security and performance evaluations of the Tor anonymity network, including a consideration of the effects of modifications to the Tor protocol. The first study investigates the performance and security implications of a number of modifications to Tor's relay selection strategy. We show that while Tor's existing strategy is highly effective, there are opportunities for performance improvement from layered selection strategies. A second study researches the level and prevalence of the threat posed to Tor users by network level adversaries, showing that Tor users are highly vulnerable---perhaps more so than previously thought---against network adversaries.