System-level testing is fundamental to ensure the reliability of software systems. However, the execution time for system tests can be quite long, sometimes prohibitively long, especially in a regimen of continuous integration and deployment. One way to speed things up is to run the tests in parallel, provided that the execution schedule respects any dependency between tests. We present two novel approaches to detect dependencies in system-level tests, namely PFAST and MEM-FAST, which are highly parallelizable and optimistically run test schedules to exclude many dependencies when there are no failures. We evaluated our approaches both asymptotically and practically, on six Web applications and their system-level test suites, as well as on MySQL system-level tests. Our results show that, in general, PFAST is significantly faster than the state-of-the-art PRADET dependency detection algorithm, while producing parallelizable schedules that achieve a significant reduction in the overall test suite execution time.

In this paper, we explore how programmable data planes can naturally provide a higher-level of service to user applications via a new abstraction called packet subscriptions. Packet subscriptions generalize forwarding rules, and can be used to express both traditional routing and more esoteric, content-based approaches. We present strategies for routing with packet subscriptions in which a centralized controller has a global view of the network, and the network topology has a hierarchical or general structure. We also describe a compiler for packet subscriptions that uses a novel BDD-based algorithm to efficiently translate predicates into P4 tables that can support O(100K) expressions. Using our system, we have built eight diverse applications. We show that these applications can be deployed in brownfield networks while performing line-rate message processing, using the full switch bandwidth of 6.5Tbps.

Software testing depends on effective oracles. Implicit oracles, such as checks for program crashes, are widely applicable but narrow in scope. Oracles based on formal specifications can reveal application-specific failures, but specifications are expensive to obtain and maintain. Metamorphic oracles are somewhere in-between. They test equivalence among different procedures to detect semantic failures. Until now, the identification of metamorphic relations has been a manual and expensive process, except for few specific domains where automation is possible. We present MeMo, a technique and a tool to automatically derive metamorphic equivalence relations from natural language documentation, and we use such metamorphic relations as oracles in automatically generated test cases. Our experimental evaluation demonstrates that 1) MeMo can effectively and precisely infer equivalence metamorphic relations, 2) MeMo complements existing state-of-the-art techniques that are based on dynamic program analysis, and 3) metamorphic relations discovered with MeMo effectively detect defects when used as test oracles in automatically-generated or manually-written test cases.

In this paper, we explore how programmable data planes can naturally provide a higher-level of service to user applications via a new abstraction called packet subscriptions. Packet subscriptions generalize forwarding rules, and can be used to express both traditional routing and more esoteric, content-based approaches. We present strategies for routing with packet subscriptions in which a centralized controller has a global view of the network, and the network topology is organized as a hierarchical structure. We also describe a compiler for packet subscriptions that uses a novel BDD-based algorithm to efficiently translate predicates into P4 tables that can support O(100K) expressions. Using our system, we have built three diverse applications. We show that these applications can be deployed in brownfield networks while performing line-rate message processing, using the full switch bandwidth of 6.5Tbps.

To understand, debug, and predict the performance of complex software systems, we develop the concept of probabilistic performance annotations. In essence, we annotate components (e.g., methods) with a relation between a measurable performance metric, such as running time, and one or more features of the input or the state of that component. We use two forms of regression analysis: regression trees and mixture models. Such relations can capture non-trivial behaviors beyond the more classic algorithmic complexity of a component. We present a method to derive such annotations automatically by generalizing observed measurements. We illustrate the use of our approach on three complex systems---the ownCloud distributed storage service; the MySQL database system; and the x264 video encoder library and application---producing non-trivial characterizations of the performance. Notably, we isolate a performance regression and identify the root cause of a second performance bug in MySQL.

In this paper, we explore how programmable data planes can provide a higher-level of service to user applications via a new abstraction called packet subscriptions. Packet subscriptions generalize forwarding rules, and can be used to express both traditional routing and more esoteric, content-based approaches. We describe a compiler for packet subscriptions that uses a novel BDD-based algorithm to efficiently translate predicates into P4 tables that can support O(100K) expressions. Using our compiler, we've built a proof-of-concept pub/sub financial application for splitting market feeds (e.g., Nasdaq's ITCH protocol) with line-rate message processing, using the full switch bandwidth of 6.5Tbps.

Large-scale information processing often relies on subset matching for data classification and routing. Examples are publish/subscribe and stream processing systems, database systems, social media, and information-centric networking. For instance, an advanced Twitter-like messaging service where users might follow specific publishers as well as specific topics encoded as tag sets must join a stream of published messages with the users and their preferred tag sets so that the user tag set is a subset of the message tags.

Application-defined and location-independent addressing is a founding principle of information centric networking (ICN) that is inherently difficult to realize if one also wants scalable routing and forwarding. We propose an ICN architecture, called TagNet, intended to combine expressive application-defined addressing with scalable routing and forwarding. TagNet features two independent delivery services: one with application-defined and possibly location-independent content descriptors, and one with network-defined host locators. In this paper we develop and evaluate specialized forwarding algorithms for TagNet. We then implement and combine these algorithms in a forwarding engine built on a general-purpose commodity CPU, and show experimentally that, thanks to the dual addressing, by descriptor or by locator, this engine can achieve a throughput of over 20Gbps with large forwarding tables corresponding to hundreds of millions of users.

Redundancy is the presence of different elements with the same functionality. In software, redundancy is useful (and used) in many ways, for example for fault tolerance and reliability engineering, and in self-adaptive and self-checking programs. However, despite the many uses, we still do not know how to measure software redundancy to support a proper and effective design. If, for instance, the goal is to improve reliability, one might want to measure the redundancy of a solution to then estimate the reliability gained with that solution. Or one might compare alternative solutions to choose the one that expresses more redundancy and therefore, presumably, more reliability. We first formalize a notion of redundancy whereby two code fragments are considered redundant when they achieve the same functionality with different executions. On the basis of this abstract and general notion, we then develop a concrete method to obtain a meaningful quantitative measure of software redundancy. The results we obtain are very positive: we show, through an extensive experimental analysis, that it is possible to distinguish code that is only minimally different, from truly redundant code, and that it is even possible to distinguish low-level code redundancy from high-level algorithmic redundancy. We also show that the measurement is significant and useful for the designer, as it can help predict the effectiveness of techniques that exploit redundancy.

Mixing time is a global property of a network that indicates how fast a random walk gains independence from its starting point. Mixing time is an essential parameter for many distributed algorithms, but especially those based on gossip. We design, implement, and evaluate a distributed protocol to measure mixing time. The protocol extends an existing algorithm that models the diffusion of information seen from each node in the network as the impulse response of a particular dynamic system. In its original formulation, the algorithm was susceptible to topology changes (or “churn”) and was evaluated only in simulation. Here we present a concrete implementation of an enhanced version of the algorithm that exploits multiple parallel runs to obtain a robust measurement, and evaluate it using a network testbed (Emulab) in combination with a peer-to-peer system (FreePastry) to assess both its performance and its ability to deal with network churn.

Despite the best intentions, the competence, and the rigorous methods of designers and developers, software is often delivered and deployed with faults. To cope with imperfect software, researchers have proposed the concept of self-healing for software systems. The ambitious goal is to create software systems capable of detecting and responding “autonomically” to functional failures, or perhaps even preempting such failures, to maintain a correct functionality, possibly with acceptable degradation. We believe that self-healing can only be an expression of some form of redundancy, meaning that, to automatically fix a faulty behavior, the correct behavior must be already present somewhere, in some form, within the software system either explicitly or implicitly. One approach is to deliberately design and develop redundant systems, and in fact this kind of deliberate redundancy is the essential ingredient of many fault tolerance techniques. However, this type of redundancy is also generally expensive and does not always satisfy the time and cost constraints of many software projects. With this article we take a different approach. We observe that modern software systems naturally acquire another type of redundancy that is not introduced deliberately but rather arises intrinsically as a by-product of modern modular software design. We formulate this notion of intrinsic redundancy and we propose a technique to exploit it to achieve some level of self-healing. We first demonstrate that software systems are indeed intrinsically redundant. Then we develop a way to express and exploit this redundancy to tolerate faults with automatic workarounds. In essence, a workaround amounts to replacing some failing operations with alternative operations that are semantically equivalent in their intended effect, but that execute different code and ultimately avoid the failure. The technique we propose finds such workarounds automatically. We develop this technique in the context of Web applications. In particular, we implement this technique within a browser extension, which we then use in an evaluation with several known faults and failures of three popular Web libraries. The evaluation demonstrates that automatic workarounds are effective: out of the nearly 150 real faults we analyzed, 100 could be overcome with automatic workarounds, and half of these workarounds found automatically were not publicly known before.

Despite the recent advances in automatic test generation, testers must still write test oracles manually. If formal specifications are available, it might be possible to use decision procedures derived from those specifications. We present a technique that is based on a form of specification but also leverages more information from the system under test. We assume that the system under test is somewhat redundant, in the sense that some operations are designed to behave like others but their executions are different. Our experience in this and previous work indicates that this redundancy exists and is easily documented. We then generate oracles by cross-checking the execution of a test with the same test in which we replace some operations with redundant ones. We develop this notion of cross-checking oracles into a generic technique to automatically insert oracles into unit tests. An experimental evaluation shows that cross-checking oracles, used in combination with automatic test generation techniques, can be very effective in revealing faults, and that they can even improve good hand-written test suites.

Publish/subscribe or "push" communication has been proposed as a new network service. In particular, in a content-based network, messages sent by publishers are delivered to subscribers based on the message content and on subscribers' long-term interests (subscriptions). In most systems that implement this form of communication, messages are treated as datagrams transmitted without end-to-end or in-network acknowledgments or without any form of flow control. In such systems, publishers do not avoid or even detect congestion, and brokers/routers respond to congestion by simply dropping overflowing messages. These systems are therefore unable to provide fair resource allocation and to properly handle traffic anomalies, and therefore are not suitable for large-scale deployments. With this motivation, we propose an end-to-end congestion control for content-based networks. In particular, we propose a practical and effective congestion-control protocol that is also content-aware, meaning that it modulates specific content-based traffic flows along a congested path. Inspired by an existing rate-control scheme for IP multicast, this protocol uses an equation-based flow-control algorithm that reacts to congestion in a manner similar to and compatible with TCP. We demonstrate experimentally that the protocol improves fairness among concurrent data flows and also reduces message loss significantly.

We present a technique to make applications resilient to failures. This technique is intended to maintain a faulty application functional in the field while the developers work on permanent and radical fixes. We target field failures in applications built on reusable components. In particular, the technique exploits the intrinsic redundancy of those components by identifying workarounds consisting of alternative uses of the faulty components that avoid the failure. The technique is currently implemented for Java applications but makes little or no assumptions about the nature of the application, and works without interrupting the execution flow of the application and without restarting its components. We demonstrate and evaluate this technique on four mid-size applications and two popular libraries of reusable components affected by real and seeded faults. In these cases the technique is effective, maintaining the application fully functional with between 19% and 48% of the failure-causing faults, depending on the application. The experiments also show that the technique incurs an acceptable runtime overhead in all cases.

Despite the best design practices and testing techniques, many faults exist and manifest themselves in deployed software. In this paper we propose a self-healing framework that aims to mask fault manifestations at runtime in Java applications by automatically applying workarounds. The framework integrates a checkpoint-recovery mechanism to restore a consistent state after the failure, and a mechanism to replace the Java code at runtime to apply the workaround.

It is often beneficial to architect networks and overlays as fully decentralized systems, in the sense that any computation (e.g., routing or search) would only use local information, and no single node would have a complete view or control over the whole network. Yet sometimes it also important to compute global properties of the network. In this paper we propose a fully decentralized algorithm to compute some global properties that can be derived from the spectrum of the network. More specifically, we compute the most significant eigenvalues of a descriptive matrix closely related to the adjacency matrix of the network graph. Such spectral properties can then lead to, for example, the “mixing time” of a network, which can be used to parametrize random walks and related search algorithms typical of peer-to-peer networks. Our key insight is to view the network as a linear dynamic system whose impulse response can be computed efficiently and locally by each node. We then use this impulse response to identify the spectral properties of the network. This algorithm is completely decentralized and requires only minimal local state and local communication. We show experimentally that the algorithm works well on different kinds of networks and in the presence of network instability.

We propose a routing scheme to implement multicast communication in wireless networks. The scheme is oblivious, compact, and completely decentralized. It is intended to support dynamic and diverse multicast requests typical of, for example, publish/subscribe and content-based communication. The scheme is built on top of a geographical routing layer. Each message is transmitted along the geometric minimum spanning tree that connects the source and all the destinations. Then, for each edge in this tree, the scheme routes a message through a random intermediate node, chosen independently of the set of multicast requests. The intermediate node is chosen in the vicinity of the corresponding edge such that congestion is reduced without stretching the routes by more than a constant factor. We first evaluate the scheme analytically, showing that it achieves a theoretically optimal level of congestion. We then evaluate the scheme in simulation, showing that its performance is also good in practice.

In a best-effort publish/subscribe network, publications may be delivered out of order (e.g., violating FIFO order). We contend that the primary cause of such ordering violations is the parallel matching and forwarding process employed by brokers to achieve high throughput. In this paper, we present an end-to-end method to improve event ordering. The method involves the receiver and minimally the sender, but otherwise uses the broker network as a black box. The idea is to analyze the dynamics of the network, and in particular to measure the delivery delay and its variation, which is directly related to out-of-order delivery. With these measures, receivers can determine a near-optimal latch time to defer message delivery upon the detection of a hole in the message sequence number. We evaluate the performance of this ordering scheme empirically in terms of the reduction in out-of-order deliveries, the delay imposed by the latch time, and its automatic adaptability to variable network conditions and input loads.

Faults in Web APIs may escape the testing process, and therefore affect thousands of Web applications. As a consequence, users of these applications might suffer from related failures for a long time until proper fixes are released by the Web API developers. In this paper we present RAW, a tool that tries to find workarounds automatically and at runtime, thereby reducing the negative impact of faults in Web applications. Runtime and automatically deployed workarounds serve as a temporary relief for application users while proper fixes are developed and released.

We present a technique that finds and executes workarounds for faulty Web applications automatically and at runtime. Automatic workarounds exploit the inherent redundancy of Web applications, whereby a functionality of the application can be obtained through different sequences of invocations of Web APIs. In general, runtime workarounds are applied in response to a failure, and require that the application re-main in a consistent state before and after the execution of a workaround. Therefore, they are ideally suited for inter-active Web applications, since those allow the user to act as a failure detector with minimal effort, and also either use read-only state or manage their state through a trans-actional data store. In this paper we focus on faults found in the access libraries of widely used Web applications such as Google Maps. We start by classifying a number of re-ported faults of the Google Maps and YouTube APIs that have known workarounds. From those we derive a number of general and API-specific program-rewriting rules, which we then apply to other faults for which no workaround is known. Our experiments show that workarounds can be readily de-ployed within Web applications, through a simple client-side plug-in, and that program-rewriting rules derived from ele-mentary properties of a common library can be effective in finding valid and previously unknown workarounds.

Experimentation is an essential tool employed by the developers of software systems, especially distributed systems. In prior work we developed a model-driven framework for automating various experimentation tasks, such as workload generation, and demonstrated that it gives the engineer a cost-effective means to conduct large-scale experiments on distributed testbeds. We have enhanced the methods underlying the framework in four significant ways: (1) increasing the expressiveness of workloads by allowing for conditional and reactive behaviors; (2) supporting the repeatability of experiments through the creation of environment workloads that can control the operational context; (3) enabling the composability of application and environment workloads to obtain a broader class of experiments; and (4) extending the scope of experiment management to include control over multiple runs. We use the enhancements to conduct a series of interesting new experiments. Specifically, the enhancements allow us to manipulate a fixed-wired testbed so that it simulates a mobile-wireless environment, and to selectively and maliciously inject faults into a system.

Test adequacy criteria provide the engineer with guidance on how to populate test suites. While adequacy criteria have long been a focus of research, existing testing methods do not address many of the fundamental characteristics of distributed systems, such as distribution topology, communication failure, and timing. Furthermore, they do not provide the engineer with a means to evaluate the relative effectiveness of different criteria, nor the relative effectiveness of adequate test suites satisfying a given criterion. This paper makes three contributions to the development and use of test adequacy criteria for distributed systems: (1) a testing method based on discrete-event simulations; (2) a fault-based analysis technique for evaluating test suites and adequacy criteria; and (3) a series of case studies that validate the method and technique. The testing method uses a discrete-event simulation as an operational specification of a system, in which the behavioral effects of distribution are explicitly represented. Adequacy criteria and test cases are then defined in terms of this simulation-based specification. The fault-based analysis involves mutation of the simulation-based specification to provide a foil against which test suites and the criteria that formed them can be evaluated. Three distributed systems were used to validate the method and technique, including DNS, the domain name system.

Network processors provide an economical programmable platform to handle the high throughput and frame rates of modern and next-generation communication systems. However, these platforms have exchanged general-purpose capabilities for performance.

Until now, structured and unstructured networks have been considered in absentia of each other. We believe that next-generation P2P services would require both structured and unstructured algorithms, and that it therefore makes sense to consider a unified substrate that provides good service for both. In this paper we argue for the creation of a semi-structured overlay substrate, called Spinneret, which can serve as the base layer for a variety of structured and unstructured search algorithms. In order to validate that this structure forms a good foundation for various services, we present two algorithms simulated on top of the Spinneret substrate: an unstructured k-walker random walk search as well as a logarithmic DHT search. Further, we argue that such a substrate strikes a balance between the resilience and reliability of unstructured networks and the efficiency of structured networks.

Developers of distributed systems routinely construct discrete-event simulations to help understand and evaluate the behavior of inter-component protocols. Simulations are abstract models of systems and their environments, capturing basic algorithmic functionality at the same time as they focus attention on properties critical to distribution, including topology, timing, bandwidth, and overall scalability. We claim that simulations can be treated as a form of specification, and thereby used within a specification-based testing regime to provide developers with a rich new basis for defining and applying system-level test adequacy criteria. We describe a framework for evaluating distributed system test adequacy criteria, and demonstrate our approach on simulations and implementations of three distributed systems, including DNS, the Domain Name System.

Engineering distributed systems is a challenging activity. This is partly due to the intrinsic complexity of distributed systems, and partly due to the practical obstacles that developers face when evaluating and tuning their design and implementation decisions.This paper addresses the latter aspect, providing techniques for software engineers to automate the experimentation activity. Our approach is founded on a suite of models that characterize the distributed system under experimentation, the testbeds upon which the experiments are to be carried out, and the client behaviors that drive the experiments. The models are used by generative techniques to automate construction of the workloads,as well as construction of the scripts for deploying and executing the experiments on distributed testbeds. The framework is not targeted at a specific system or application model, but rather is a generic, programmable tool. We have validated our approach by performing experiments on a variety of distributed systems. For two of these systems, the experiments were deployed and executed on the PlanetLab wide-area testbed.Our experience shows that this framework can be readily applied to different kinds of distributed system architectures,and that using it for meaningful experimentation,especially in large-scale network environments, is advantageous.

This work proposes a routing scheme for content-based networking. A content-based network is a communication network that features a new advanced communication model where messages are not given explicit destination addresses, and where the destinations of a message are determined by matching the content of the message against selection predicates declared by nodes. Routing in a content-based network amounts to propagating predicates and the necessary topological information in order to maintain loop-free and possibly minimal forwarding paths for messages. The routing scheme we propose uses a combination of a traditional broadcast protocol and a content-based routing protocol. We present the combined scheme and its requirements over the broadcast protocol. We then detail the content-based routing protocol, highlighting a set of optimization heuristics. We also present the results of our evaluation, showing that this routing scheme is effective and scalable.

This paper presents an algorithm for content-based forwarding, an essential function in content-based networking. Unlike in traditional address-based unicast or multicast networks, where messages are given explicit destination addresses, the movement of messages through a content-based network is driven by predicates applied to the content of the messages. Forwarding in such a network amounts to evaluating the predicates stored in a router's forwarding table in order to decide to which neighbor routers the message should be sent. We are interested in finding a forwarding algorithm that can make this decision as quickly as possible in situations where there are numerous, complex predicates and high volumes of messages. We present such an algorithm and give the results of studies evaluating its performance.

This paper presents the design and evaluation of a support service for mobile, wireless clients of a distributed publish/subscribe system. A distributed publish/subscribe system is a networked communication infrastructure where messages are published by senders and then delivered to the receivers whose subscriptions match the messages. Communication therefore does not involve the use of explicit addresses, but rather emerges from the dynamic arrangement of publishers and subscribers. Such a communication mechanism is an ideal platform for a variety of Internet applications, including multiparty messaging, personal information management, information sharing, online news distribution, service discovery, and electronic auctions. Our goal is to support such applications on mobile, wireless host devices in such a way that the applications can, if they chose, be oblivious to the mobility and intermittent connectivity of their hosts as they move from one publish/subscribe access point to another. In this paper, we describe a generic, value-added service that can be used in conjunction with publish/subscribe systems to achieve these goals. We detail the implementation of the service and present the results of our evaluation of the service in both wireline and emulated wireless environments.

Even though the number and variety of available configuration management systems has grown rapidly in the past few years, the need for new configuration management systems still remains. Driving this need are the emergence of situations requiring highly specialized solutions, the demand for management of artifacts other than traditional source code and the exploration of entirely new research questions in configuration management. Complicating the picture is the trend toward organizational structures that involve personnel working at physically separate sites. We have developed a testbed to support the rapid development of configuration management systems. The testbed separates configuration management repositories (i.e., the stores for versions of artifacts) from configuration management policies (i.e., the procedures, according to which the versions are manipulated) by providing a generic model of a distributed repository and an associated programmatic interface. Specific configuration management policies are programmed as unique extensions to the generic interface, while the underlying distributed repository is reused across different policies. The authors describe the repository model and its interface and present their experience in using a prototype of the testbed, called NUCM, to implement a variety of configuration management systems.

The components of a loosely coupled system are typically designed to operate by generating and responding to asynchronous events. An event notification service is an application-independent infrastructure that supports the construction of event-based systems, whereby generators of events publish event notifications to the infrastructure and consumers of events subscribe with the infrastructure to receive relevant notifications. The two primary services that should be provided to components by the infrastructure are notification selection (i. e., determining which notifications match which subscriptions) and notification delivery (i.e., routing matching notifications from publishers to subscribers). Numerous event notification services have been developed for local-area networks, generally based on a centralized server to select and deliver event notifications. Therefore, they suffer from an inherent inability to scale to wide-area networks, such as the Internet, where the number and physical distribution of the service's clients can quickly overwhelm a centralized solution. The critical challenge in the setting of a wide-area network is to maximize the expressiveness in the selection mechanism without sacrificing scalability in the delivery mechanism. This paper presents SIENA, an event notification service that we have designed and implemented to exhibit both expressiveness and scalability. We describe the service's interface to applications, the algorithms used by networks of servers to select and deliver event notifications, and the strategies used to optimize performance. We also present results of simulation studies that examine the scalability and performance of the service.

This paper describes the design of SIENA, an Internet-scale event notification middleware service for distributed event-based applications deployed over wide-area networks. SIENA is responsible for selecting the notifications that are of interest to clients (as expressed in client subscriptions) and then delivering those notifications to the clients via access points. The key design challenge for SIENA is maximizing expressiveness in the selection mechanism without sacrificing scalability of the delivery mechanism. This paper focuses on those aspects of the design of SIENA that fundamentally impact scalability and expressiveness. In particular, we describe SIENA's data model for notifications, the covering relations that formally define the semantics of the data model, the distributed architectures we have studied for SIENA's implementation, and the processing strategies we developed to exploit the covering relations for optimizing the routing of notifications.

Large scale distributed systems are becoming of paramount importance, due to the evolution of technology and to the interest of market.Their development, however, is not yet supported by a sound technological and methodological background, as the results developed for small size distributed systems often do not scale up.Recently, mobile code languages (MCLs) have been proposed as a technological answer to the problem.In this work, we abstract away from the details of these languages by deriving design paradigms exploiting code mobility that are independent of any particular technology.We present such design paradigms, together with a discussion of their features, their application domain, and some hints about the selection of the correct paradigm for a given distributed application.