Numerous routing protocols have been designed and subjected to model checking and simulations. However, model checking the design or testing the simulator-based prototype of a protocol does not guarantee that the implementation is free of bugs and vulnerabilities. Testing implementations beyond their basic functionality (also known as adversarial testing) can increase protocol robustness. We focus on automated adversarial testing of real-world implementations of wireless routing protocols. In our previous work we created Turret, a platform that uses a network emulator and virtualization to test unmodified binaries of general distributed systems. Based on Turret, we create Turret-W designed specifically for wireless routing protocols. Turret-W includes new functionalities such as differentiating routing messages from data messages to enable evaluation of attacks on the control plane and the data plane separately, support for several additional protocols (e.g., those that use homogeneous/heterogenous packet formats, those that run on geographic forwarding (not just IP), those that operate at the data link layer instead of the network layer), support for several additional attacks (e.g., replay attacks) and for establishment of adversarial side-channels that allow for collusion. Turret-W can test not only general routing attacks, but also wireless specific attacks such as wormhole. Using Turret-W on publicly available implementations of five representative routing protocols, we (re-)discovered 37 attacks and 3 bugs. All these bugs and 5 of the total attacks were not previously reported to the best of our knowledge.

In this article, we propose Gatling, a framework that automatically finds performance attacks caused by insider attackers in large-scale message-passing distributed systems. In performance attacks, malicious nodes deviate from the protocol when sending or creating messages, with the goal of degrading system performance. We identify a representative set of basic malicious message delivery and lying actions and design a greedy search algorithm that finds effective attacks consisting of a subset of these actions. Although lying malicious actions are protocol dependent, requiring the format and meaning of messages, Gatling captures them without needing to modify the target system by using a type-aware compiler. We have implemented and used Gatling on nine systems, a virtual coordinate system, a distributed hash table lookup service and application, two multicast systems and one file sharing application, and three secure systems designed specifically to tolerate insiders, two based on virtual coordinates and one using Outlier Detection, one invariant derived from physical laws, and the last one a Byzantine resilient replication system. We found a total of 48 attacks, with the time needed to find each attack ranging from a few minutes to a few hours.

Security and performance are critical goals for distributed systems. The increased design complexity, incomplete expertise of developers, and limited functionality of existing testing tools often result in bugs and vulnerabilities that prevent implementations from achieving their design goals in practice. Many of these bugs, vulnerabilities, and misconfigurations manifest after the code has already been deployed making the debugging process difficult and costly. In this paper, we present Turret, a platform for automatically finding performance attacks in unmodified implementations of distributed systems. Turret does not require the user to provide any information about vulnerabilities and runs the implementation in the same operating system setup as the deployment, with an emulated network. Turret uses a new attack finding algorithm and several optimizations that allow it to find attacks in a matter of minutes. We ran Turret on 5 different distributed system implementations specifically designed to tolerate insider attacks, and found 30 performance attacks, 24 of which were not previously reported to the best of our knowledge.

An attractive approach to leveraging the ability of cloud-computing platforms to provide resources on demand is to build elastic applications, which can dynamically scale up or down based on resource requirements. To ease the development of elastic applications, it is useful for programmers to write applications with simple sequential semantics, without considering elasticity, and rely on runtime support to provide that elasticity. While this approach has been useful in restricted domains, such as MapReduce, existing programming models for general distributed applications do not expose enough information about their inherent organization of state and computation to provide such transparent elasticity.

We focus on automated adversarial testing of real-world implementations of wireless routing protocols. We extend an existing platform, Turret, designed for general distributed systems, to address the specifics of wireless routing protocols. Specifically, we add functionality to differentiate routing messages from data messages and support wireless specific attacks such as blackhole and wormhole, or routing attacks such as replay attacks. The extended platform, Turret-W, uses a network emulator to create reproducible network conditions and virtualization to run unmodified binaries of wireless protocol implementations. Using the platform on publicly available implementations of two representative routing protocols we (re-)discovered 14 attacks and 3 bugs.

As networking services, such as DHTs, provide increasingly complex functionality, providing acceptable performance will require parallelizing their operations on individual nodes. Unfortunately, the event-driven style in which these applications have traditionally been written makes it difficult to reason about parallelism, and providing safe, efficient parallel implementations of distributed systems remains a challenge. In this paper, we introduce a declarative programming model based on contexts, which allows programmers to specify the sharing behavior of event handlers. Programs that adhere to the programming model can be safely parallelized according to an abstract execution model, with parallel behavior that is well-defined with respect to the expected sequential behavior. The declarative nature of the programming model allows conformance to be captured as a safety property that can be verified using a model checker.

The proliferation of peer-to-peer systems has led to the increasing deployment of dynamic, adaptive overlay networks that are designed to preserve application performance goals. While such networks provide increased performance and resiliency to benign faults, they are susceptible to attacks conducted by compromised overlay nodes, especially those targeting the adaptation mechanisms. In this work, we propose a lightweight, general solution to increase the resiliency of adaptive overlay networks. By locally aggregating and correlating network topology with system performance metrics such as latency and bandwidth, each node can check the consistency of the reported information and constrain the attacker's ability to lie about system metrics. As a result, each node can make better adaptation decisions. We demonstrate the susceptibility of adaptation mechanisms to malicious attacks and the utility of our solution through real-life deployments of mature, adaptive overlay-based systems.

Robust distributed systems commonly employ high-level recovery mechanisms enabling the system to recover from a wide variety of problematic environmental conditions such as node failures, packet drops and link disconnections. Unfortunately, these recovery mechanisms also effectively mask additional serious design and implementation errors, disguising them as latent performance bugs that severely degrade end-to-end system performance. These bugs typically go unnoticed due to the challenge of distinguishing between a bug and an intermittent environmental condition that must be tolerated by the system. We present techniques that can automatically pinpoint latent performance bugs in systems implementations, in the spirit of recent advances in model checking by systematic state space exploration. The techniques proceed by automating the process of conducting random simulations, identifying performance anomalies, and analyzing anomalous executions to pinpoint the circumstances leading to performance degradation.

Mace, MaceMC andMacePCwork together to make it easier to build correct, high performance distributed systems implementations. Mace developers find that it now takes them a fraction of the time previously needed to go from design to implementation of a new distributed system. Together with ModelNet and Plush, the whole toolkit is among the best in the world for implementing, testing, evaluating, and deploying distributed and peer-to-peer systems. Mace represents six years of development work and has been publicly available for five years. In addition to the Mace research contributions, the Mace distribution also represents many of the best-quality publicly-available implementations of the included services, and by itself represents a practical contribution that users worldwide recognize and utilize.

This article focuses on the multireceiver data dissemination problem. Initially, IP multicast formed the basis for efficiently supporting such distribution. More recently, overlay networks have emerged to support point-to-multipoint communication. Both techniques focus on constructing trees rooted at the source to distribute content among all interested receivers. We argue, however, that trees have two fundamental limitations for data dissemination. First, since all data comes from a single parent, participants must often continuously probe in search of a parent with an acceptable level of bandwidth. Second, due to packet losses and failures, available bandwidth is monotonically decreasing down the tree. To address these limitations, we present Bullet, a data dissemination mesh that takes advantage of the computational and storage capabilities of end hosts to create a distribution structure where a node receives data in parallel from multiple peers. For the mesh to deliver improved bandwidth and reliability, we need to solve several key problems: (i) disseminating disjoint data over the mesh, (ii) locating missing content, (iii) finding who to peer with (peering strategy), (iv) retrieving data at the right rate from all peers (flow control), and (v) recovering from failures and adapting to dynamically changing network conditions. Additionally, the system should be self-adjusting and should have few user-adjustable parameter settings. We describe our approach to addressing all of these problems in a working, deployed system across the Internet. Bullet outperforms state-of-the-art systems, including BitTorrent, by 25-70% and exhibits strong performance and reliability in a range of deployment settings. In addition, we find that, relative to tree-based solutions, Bullet reduces the need to perform expensive bandwidth probing.

Building distributed systems is particularly difficult because of the asynchronous, heterogeneous, and failure-prone environment where these systemsmust run. Tools for building distributed systems must strike a compromise between reducing programmer effort and increasing system efficiency. We present Mace, a C++ language extension and source-to-source compiler that translates a concise but expressive distributed system specification into a C++ implementation. Mace overcomes the limitations of low-level languages by providing a unified framework for networking and event handling, and the limitations of high-level languages by allowing programmers to write program components in a controlled and structured manner in C++. By imposing structure and restrictions on how applications can be written, Mace supports debugging at a higher level, including support for efficient model checking and causal-path debugging. Because Mace programs compile to C++, programmers can use existing C++ tools, including optimizers, profilers, and debuggers to analyze their systems.

Many overlay multicast protocols have been designed and deployed across the Internet to support content distribution. To our knowledge, however, none have provided a rigorous analysis of the problem or the effectiveness of their proposed solutions. We define the Overlay Network Content Distribution (OCD) problem to allow such analyses.

Bugs in complex distributed systems are often hard to find. Many bugs reflect discrepancies between a system's behavior and the programmer's assumptions about that behavior. Differences may be in correctness, in performance characteristics, or both. Our debugging framework, Pip, compares actual behavior with expected behavior and visualizes both. Pip consists of two tools to help reconcile assumptions and actual behavior: an automatic expectations checker and an interactive behavior-explorer GUI.