There is a growing trend toward AI systems interacting with humans to revolutionize a range of application domains such as healthcare and transportation. However, unsafe human-machine interaction can lead to catastrophic failures. We propose a novel approach that predicts future states by accounting for the uncertainty of human interaction, monitors whether predictions satisfy or violate safety requirements, and adapts control actions based on the predictive monitoring results. Specifically, we develop a new quantitative predictive monitor based on Signal Temporal Logic with Uncertainty (STL-U) to compute a robustness degree interval, which indicates the extent to which a sequence of uncertain predictions satisfies or violates an STL-U requirement. We also develop a new loss function to guide the uncertainty calibration of Bayesian deep learning and a new adaptive control method, both of which leverage STL-U quantitative predictive monitoring results. We apply the proposed approach to two case studies: Type 1 Diabetes management and semi-autonomous driving. Experiments show that the proposed approach improves safety and effectiveness in both case studies.

The proliferation of autonomous vehicles (AVs) has made their failures increasingly evident. Testing efforts aimed at identifying the inputs leading to those failures are challenged by the input's long-tail distribution, whose area under the curve is dominated by rare scenarios. We hypothesize that leveraging emerging open-access datasets can accelerate the exploration of long-tail inputs. Having access to diverse inputs, however, is not sufficient to expose failures; an effective test also requires an oracle to distinguish between correct and incorrect behaviors. Current datasets lack such oracles and developing them is notoriously difficult. In response, we propose Difftest4av,a differential testing framework designed to address the unique challenges of testing AV systems: 1) for any given input, many outputs may be considered acceptable, 2) the long tail contains an insurmountable number of inputs to explore, and 3) the AV's continuous execution loop requires failures to persist in order to affect the system. Difftest4av integrates statistical analysis to identify meaningful behavioral variations, judges their importance in terms of the severity of these differences, and incorporates sequential analysis to detect persistent errors indicative of potential system-level failures. Our study on 5 versions of the commercially-available, road-deployed comma.ai OpenPilot system, using 3 available image datasets, demonstrates the capabilities of the framework to detect high-severity, high-confidence, long- running test failures.

Detecting objects in 3D space from monocular input is crucial for applications ranging from robotics to scene understanding. Despite advanced performance in the indoor and autonomous driving domains, existing monocular 3D detection models struggle with in-the-wild images due to the lack of 3D in-the-wild datasets and the challenges of 3D annotation. We introduce LabelAny3D, an analysis-by-synthesis framework that reconstructs holistic 3D scenes from 2D images to efficiently produce high-quality 3D bounding box annotations. Built on this pipeline, we present COCO3D, a new benchmark for open-vocabulary monocular 3D detection, derived from the MS-COCO dataset and covering a wide range of object categories absent from existing 3D datasets. Experiments show that annotations generated by LabelAny3D improve monocular 3D detection performance across multiple benchmarks, outperforming prior auto-labeling approaches in quality. These results demonstrate the promise of foundation-model-driven annotation for scaling up 3D recognition in realistic, open-world settings.

The increasing integration of Deep Neural Networks (DNNs) into safety critical systems, such as Autonomous Vehicles (AVs), where failures can lead to significant consequences, has fostered the development of many Verification and Validation (V&V) techniques. However, these techniques are applied mainly after the DNN training process is complete. This delayed application of V&V techniques means that property violations found require restarting the expensive training process, and that V&V techniques struggle in pursuit of checking increasingly large and sophisticated DNNs. To address this issue, we propose T4PC, a framework to increase property conformanceduringDNN training. Increasing property conformance is achieved by enriching: 1) the data preparation phase to account for properties’ pre and postcondition satisfaction, and 2) the training phase to account for the property satisfaction by incorporating a newproperty lossterm that is integrated with the main loss. Our family of controlled experiments targeting a navigation DNN show that T4PC can effectively train it for conformance to single and multiple properties, and can also fine-tune for conformance an existing navigation DNN originally trained for accuracy. Our case study in simulation applying T4PC to fine-tune two open source AV systems operating in the CARLA simulator shows that it can reduce targeted driving violations while retaining its original driving capabilities.

With the proliferation of autonomous vehicles (AVs) comes the need to ensure they abide by safe driving properties. Specifying and monitoring such properties, however, is challenging because of the mismatch between the semantic space over which typical driving properties are asserted (e.g., vehicles, pedestrians, intersections) and the sensed inputs of AVs. Existing efforts either assume for such semantic data to be available or develop bespoke methods for capturing it. Instead, this work introduces a framework that can extract scene graphs (SGs) from sensor inputs to capture the entities related to the AV, and a domain-specific language that enables building propositions over those graphs and composing them through temporal logic. We implemented the framework to monitor for specification violations of 3 top AVs from the CARLA Autonomous Driving Leaderboard, and found that the AVs violated 71% of properties during at least one test. Artifact available at https://github.com/less-lab-uva/SGSM.

Autonomous vehicles (AVs) must be able to operate in a wide range of scenarios including those in the long tail distribution that include rare but safety-critical events. The collection of sensor input and expected output datasets from such scenarios is crucial for the development and testing of such systems. Yet, approaches to quantify the extent to which a dataset covers test specifications that capture critical scenarios remain limited in their ability to discriminate between inputs that lead to distinct behaviors, and to render interpretations that are relevant to AV domain experts. To address this challenge, we introduce S3C, a framework that abstracts sensor inputs to coverage domains that account for the spatial semantics of a scene. The approach leverages scene graphs to produce a sensor-independent abstraction of the AV environment that is interpretable and discriminating. We provide an implementation of the approach and a study for camera-based autonomous vehicles operating in simulation. The findings show that S3C outperforms existing techniques in discriminating among classes of inputs that cause failures, and offers spatial interpretations that can explain to what extent a dataset covers a test specification. Further exploration of S3C with open datasets complements the study findings, revealing the potential and shortcomings of deploying the approach in the wild.

Although Driving Automation Systems (DASs) are rapidly becoming more advanced and ubiquitous, they are still confined to specific Operational Design Domains (ODDs) over which the system must be trained and validated. Yet, each DAS has a bespoke and often informally defined ODD, which makes it intractable to manually judge whether a dataset satisfies a DAS’s ODD. This results in inadequate data leaking into the training and testing processes, weakening them, and causes large amounts of collected data to go unused given the inability to check their ODD compliance. This presents a dilemma: How do we cost-effectively determine if existing sensor data complies with a DAS’s ODD? To address this challenge, we start by reviewing the ODD specifications of 10 commercial DASs to understand current practices in ODD documentation. Next, we present ODD-diLLMma, an automated method that leverages Large Language Models (LLMs) to analyze existing datasets with respect to the natural language specifications of ODDs. Our evaluation of ODD-diLLMma examines its utility in analyzing inputs from 3 real-world datasets. Our empirical findings show that ODD-diLLMma significantly enhances the efficiency of detecting ODD compliance, showing improvements of up to 147% over a human baseline. Further, our analysis highlights the strengths and limitations of employing LLMs to support ODD-diLLMma, underscoring their potential to effectively address the challenges of ODD compliance detection.

Robots operate under certain forces that affect their behavior. Consider, a drone meant to deliver packages must hold its pose as long as it operates under its weight and wind limits. Validating that such a drone handles external forces correctly is key to ensuring its safety. Nevertheless, validating the system's behavior under the effect of such forces can be difficult and costly. For example, checking the effects of different wind magnitudes may require waiting for the matching outdoor conditions or requiring wind tunnels. Checking the effects of different package sizes and shapes may require many slow and laborious iterations, and validating the combinations of wind gusts and package configurations is often hard to replicate. This work introduces a framework to overcome such challenges by mimicking external forces exercised on a drone with limited cost, setup, and space. The framework consists of a haptic suit device with directional propellers that can be mounted onto a drone, a synthesizer to transform intended forces into setpoints for the suit's directional propellers, and a controller for the suit to meet those setpoints. We conduct a study to assess the framework's capabilities under multiple scenarios involving various forces. Our findings show that the haptic suit framework can recreate real-world forces on the drone with acceptable precision.

The spatial distribution of sensed objects strongly influences the behavior of mobile robots. Yet, as robots evolve in complexity to operate in increasingly rich environments, it becomes much more difficult to specify the underlying relations between sensed object spatial distributions and robot behaviors. We aim to address this challenge by leveraging system trace data to automatically infer relations that help to better characterize these spatial associations. In particular, we introduce SpRinG, a framework for the unsupervised inference of system specifications from traces that characterize the spatial relationships under which a robot operates. Our method builds on a parameterizable notion of reachability to encode relationships of spatial neighborship, which are used to instantiate a language of patterns. These patterns provide the structure to infer, from system traces, the connection between such relationships and robot behaviors. We show that SpRinG can automatically infer spatial relations over two distinct domains: autonomous vehicles in traffic and a surgical robot. Our results demonstrate the power and expressiveness of SpRinG, in its ability to learn existing specifications as machine-checkable first-order logic, uncover previously unstated specifications that are rich and insightful, and reveal contextual differences between executions.

Autonomous systems rely on a perception component to interpret their surroundings, and when misinterpretations occur, they can and have led to serious and fatal system-level failures. Yet, existing methods for testing perception software remain limited in both their capacity to efficiently generate test data that translates to real-world performance and in their diversity to capture the long tail of rare but safety-critical scenarios. These limitations are particularly evident for perception systems based on LiDAR sensors, which have emerged as a crucial component in modern autonomous systems due to their ability to provide a 3D scan of the world and operate in all lighting conditions. To address these limitations, we introduce a novel approach for testing LiDAR-based perception systems by leveraging existing real-world data as a basis to generate realistic and diverse test cases through mutations that preserve realism invariants while generating inputs rarely found in existing data sets, and automatically crafting oracles that identify potentially safety-critical issues in perception performance. We implemented our approach to assess its ability to identify perception failures, generating over 50,000 test inputs for five state-of-the-art LiDAR-based perception systems. We found that it efficiently generated test cases that yield errors in perception that could result in real consequences if these systems were deployed and does so at a low rate of false positives.

Structural code coverage is a popular test adequacy metric that measures the percentage of program structure (e.g., statement, branch, decision) executed by a test suite. While structural coverage has several benefits, previous studies suggested that code coverage is not a good indicator of a test suite's fault-detection effectiveness as coverage computation does not consider test oracle quality. In this research, we formally define the coverage gap in structural testing as the percentage of program structure that is executed but not observed by any test oracles. Our large-scale empirical study of 13 Java applications, 16K test cases and 51.6K test assertions shows that even for mature test suites, the gap can be as high as 51 percentage points (pp) and 34pp on average. Our study reveals that the coverage gap strongly and negatively correlates with a test suite's fault-detection effectiveness. To mitigate gaps, we propose a lightweight static analysis of program dependencies to produce a ranked recommendation of test focus methods that can reduce the gap and improve test suite quality. When considering 34.8K assertions in the test suite as ground truth, the recommender suggests two-thirds of the focus methods written by developers within the top five recommendations.

Adequately exercising the behaviors of autonomous vehicles is fundamental to their validation. However, quantifying an autonomous vehicle’s testing adequacy is challenging as the system’s behavior is influenced both by its state as well as its physical environment. To address this challenge, our work builds on two insights. First, data sensed by an autonomous vehicle provides a unique spatial signature of the physical environment inputs. Second, given the vehicle’s current state, inputs residing outside the autonomous vehicle’s physically reachable regions are less relevant to its behavior. Building on those insights, we introduce an abstraction that enables the computation of a physical environment-state coverage metric, PhysCov. The abstraction combines the sensor readings with a physical reachability analysis based on the vehicle’s state and dynamics to determine the region of the environment that may affect the autonomous vehicle. It then characterizes that region through a parameterizable geometric approximation that can trade quality for cost. Tests with the same characterizations are deemed to have had similar internal states and exposed to similar environments and thus likely to exercise the same set of behaviors, while tests with distinct characterizations will increase PhysCov. A study on two simulated and one real system’s dataset examines PhysCovs’s ability to quantify an autonomous vehicle’s test suite, showcases its characterization cost and precision, investigates its correlation with failures found and potential for test selection, and assesses its ability to distinguish among real-world scenarios.

Defining test oracles is crucial and central to test development, but manual construction of oracles is expensive. While recent neural-based automated test oracle generation techniques have shown promise, their real-world effectiveness remains a compelling question requiring further exploration and understanding. This paper investigates the effectiveness of TOGA, a recently developed neural-based method for automatic test oracle generation. TOGA utilizes EvoSuite-generated test inputs and generates both exception and assertion oracles. In a Defects4j study, TOGA outperformed specification, search, and neural-based techniques, detecting 57 bugs, including 30 unique bugs not detected by other methods. To gain a deeper understanding of its applicability in real-world settings, we conducted a series of external, extended, and conceptual replication studies of TOGA.

Deep Neural Networks (DNNs) that process images are being widely used for many safety-critical tasks, from autonomous vehicles to medical diagnosis. Currently, DNN correctness properties are defined at the pixel level over the entire input. Such properties are useful to expose system failures related to sensor noise or adversarial attacks, but they cannot capture features that are relevant to domain-specific entities and reflect richer types of behaviors. To overcome this limitation, we envision the specification of properties based on the entities that may be present in image input, capturing their semantics and how they change. Creating such properties today is difficult as it requires determining where the entities appear in images, defining how each entity can change, and writing a specification that is compatible with each particular V&V client. We introduce an initial framework structured around those challenges to assist in the generation of Domain-specific Entity-based properties automatically by leveraging object detection models to identify entities in images and creating properties based on entity features. Our feasibility study provides initial evidence that the new properties can uncover interesting system failures, such as changes in skin color can modify the output of a gender classification network. We conclude by analyzing the framework potential to implement the vision and by outlining directions for future work.

Software engineering (SE) techniques are increasingly relying on deep learning approaches to support many SE tasks, from bug triaging to code generation. To assess the efficacy of such techniques researchers typically perform controlled experiments. Conducting these experiments, however, is particularly challenging given the complexity of the space of variables involved, from specialized and intricate architectures and algorithms to a large number of training hyper-parameters and choices of evolving datasets, all compounded by how rapidly the machine learning technology is advancing, and the inherent sources of randomness in the training process. In this work we conduct a mapping study, examining 194 experiments with techniques that rely on deep neural networks (DNNs) appearing in 55 papers published in premier SE venues to provide a characterization of the state of the practice, pinpointing experiments’ common trends and pitfalls. Our study reveals that most of the experiments, including those that have received ACM artifact badges, have fundamental limitations that raise doubts about the reliability of their findings. More specifically, we find: 1) weak analyses to determine that there is a true relationship between independent and dependent variables (87% of the experiments), 2) limited control over the space of DNN relevant variables, which can render a relationship between dependent variables and treatments that may not be causal but rather correlational (100% of the experiments), and 3) lack of specificity in terms of what are the DNN variables and their values utilized in the experiments (86% of the experiments) to define the treatments being applied, which makes it unclear whether the techniques designed are the ones being assessed, or how the sources of extraneous variation are controlled. We provide some practical recommendations to address these limitations.

Adversarial test generation techniques aim to produce input perturbations that cause a DNN to compute incorrect outputs. For autonomous vehicles driven by a DNN, however, the effect of such perturbations are attenuated by other parts of the system and are less effective as vehicle state evolves. In this work we argue that for adversarial testing perturbations to be effective on autonomous vehicles, they must account for the subtle interplay between the DNN and vehicle states. Building on that insight, we develop DeepManeuver, an automated framework that interleaves adversarial test generation with vehicle trajectory physics simulation. Thus, as the vehicle moves along a trajectory, DeepManeuver enables the refinement of candidate perturbations to: (1) account for changes in the state of the vehicle that may affect how the perturbation is perceived by the system; (2) retain the effect of the perturbation on previous states so that the current state is still reachable and past trajectory is preserved; and (3) result in multi-target maneuvers that require fulfillment of vehicle state sequences (e.g. reaching locations in a road to navigate a tight turn). Our assessment reveals that DeepManeuver can generate perturbations to force maneuvers more effectively and consistently than state-of-the-art techniques by 20.7 percentage points on average. We also show DeepManeuver's effectiveness at disrupting vehicle behavior to achieve multi-target maneuvers with a minimum 52% rate of success.

Perception systems enable autonomous systems to interpret raw sensor readings of the physical world. Testing of perception systems aims to reveal misinterpretations that could cause system failures. Current testing methods, however, are inadequate. The cost of human interpretation and annotation of real-world input data is high, so manual test suites tend to be small. The simulation-reality gap reduces the validity of test results based on simulated worlds. And methods for synthesizing test inputs do not provide corresponding expected interpretations. To address these limitations, we developed semSensFuzz, a new approach to fuzz testing of perception systems based on semantic mutation of test cases that pair real-world sensor readings with their ground-truth interpretations. We implemented our approach to assess its feasibility and potential to improve software testing for perception systems. We used it to generate 150,000 semantically mutated image inputs for five state-of-the-art perception systems. We found that it synthesized tests with novel and subjectively realistic image inputs, and that it discovered inputs that revealed significant inconsistencies between the specified and computed interpretations. We also found that it produced such test cases at a cost that was very low compared to that of manual semantic annotation of real-world images.

Openpilot is an open source system to assist drivers by providing features like automated lane centering and adaptive cruise control. Like most systems for autonomous vehicles, Openpilot relies on a sophisticated deep neural network (DNN) to provide its functionality, one that is susceptible to safety property violations that can lead to crashes. To uncover such potential violations before deployment, we investigate the use of falsification, a form of directed testing that analyzes a DNN to generate an input that will cause a safety property violation. Specifically, we explore the application of a state-of-the-art falsifier to the DNN used in OpenPilot, which reflects recent trends in network design. Our investigation reveals the challenges in applying such falsifiers to real-world DNNs, conveys our engineering efforts to overcome such challenges, and showcases the potential of falsifiers to detect property violations and provide meaningful counterexamples. Finally, we summarize the lessons learned as well as the pending challenges for falsifiers to realize their potential on systems like OpenPilot.

Abstract Despite the large number of sophisticated deep neural network (DNN) verification algorithms, DNN verifier developers, users, and researchers still face several challenges. First, verifier developers must contend with the rapidly changing DNN field to support new DNN operations and property types. Second, verifier users have the burden of selecting a verifier input format to specify their problem. Due to the many input formats, this decision can greatly restrict the verifiers that a user may run. Finally, researchers face difficulties in re-using benchmarks to evaluate and compare verifiers, due to the large number of input formats required to run different verifiers. Existing benchmarks are rarely in formats supported by verifiers other than the one for which the benchmark was introduced. In this work we present DNNV, a framework for reducing the burden on DNN verifier researchers, developers, and users. DNNV standardizes input and output formats, includes a simple yet expressive DSL for specifying DNN properties, and provides powerful simplification and reduction operations to facilitate the application, development, and comparison of DNN verifiers. We show how DNNV increases the support of verifiers for existing benchmarks from 30% to 74%.

Simulation is at the core of validating autonomous systems (AS), enabling the detection of faults at a lower cost and earlier in the development life cycle. However, simulation can only produce an approximation of the real world, leading to a gap between simulation and reality where undesirable system behaviors can go unnoticed. To address that gap, we present a novel approach, world-in-the-loop (WIL) simulation, which integrates sensing data from simulation and the real world to provide the AS with a mixed-reality. The approach executes multiple instances of the AS in parallel, one in the real world and at least one in simulation, performs configurable transformations, filtering, and merging operations on the body of sensed data in order to integrate it, and provides the pipelines to distribute the original sensor data and the integrated sensor data back to the executing AS. We present a study on multiple scenarios and two simulators that demonstrates how WIL reduces the simulation-reality gap and increases the chances of exposing failures before deployment.

Several independent approaches exist for state estimation and control of multirotor unmanned aerial systems (UASs) that address specific and constrained operational conditions. This work presents a complete end-to-end pipeline that enables precise, aggressive and agile maneuvers for multirotor UASs under real and challenging outdoor environments. We leverage state-of-the-art optimal methods from the literature for trajectory planning and control, such that designing and executing dynamic paths is fast, robust and easy to customize for a particular application. The complete pipeline, built entirely using commercially available components, is made open-source and fully documented to facilitate adoption. We demonstrate its performance in a variety of operational settings, such as hovering at a spot under dynamic wind speeds of up to 5– 6m/s (12–15mi/h) while staying within 12cm of 3D error. We also characterize its capabilities in flying high-speed trajectories outdoors, and enabling fast aerial docking with a moving target with planning and interception occurring in under 8s.

Complex environments can cause robots to fail. Identifying the key elements of the environment associated with such failures is critical for faster fault isolation and, ultimately, debugging those failures. In this work we present the first automated approach for reducing the environment in which a robot failed. Similar to software debugging techniques, our approach systematically performs a partition of the environment space causing a failure, executes the robot in each partition containing a reduced environment, and further partitions reduced environments that still lead to a failure. The technique is novel in the spatial-temporal partition strategies it employs, and in how it manages the potential different robot behaviors occurring under the same environments. Our study of a ground robot on three failure scenarios finds that environment reductions of over 95% are achievable within a 2-hour window.

Testing mobile robots is difficult and expensive, and many faults go undetected. In this work we explore whether fuzzing, an automated test input generation technique, can more quickly find failure inducing inputs in mobile robots. We developed a simple fuzzing adaptation, BASE-FUZZ, and one specialized for fuzzing mobile robots, PHYS-FUZZ. PHYS-FUZZ is unique in that it accounts for physical attributes such as the robot dimensions, estimated trajectories, and time to impact measures to guide the test input generation process. The results of evaluating PHYS-FUZZ suggest that it has the potential to speed up the discovery of input scenarios that reveal failures, finding 56.5% more than uniform random input selection and 7.0% more than BASE-FUZZ during 7 days of testing.

Deep Neural Networks (DNN) are increasingly being deployed in safety-critical domains, from autonomous vehicles to medical devices, where the consequences of errors demand techniques that can provide stronger guarantees about behavior than just high test accuracy. This paper explores broadening the application of existing adversarial attack techniques for the falsification of DNN safety properties. We contend and later show that such attacks provide a powerful repertoire of scalable algorithms for property falsification. To enable the broad application of falsification, we introduce a semantics-preserving reduction of multiple safety property types, which subsume prior work, into a set of equivalid correctness problems amenable to adversarial attacks. We evaluate our reduction approach as an enabler of falsification on a range of DNN correctness problems and show its cost-effectiveness and scalability.

The widespread adoption of Deep Neural Networks (DNNs) in important domains raises questions about the trustworthiness of DNN outputs. Even a highly accurate DNN will make mistakes some of the time, and in settings like self-driving vehicles these mistakes must be quickly detected and properly dealt with in deployment. Just as our community has developed effective techniques and mechanisms to monitor and check programmed components, we believe it is now necessary to do the same for DNNs. In this paper we present DNN self-checking as a process by which internal DNN layer features are used to check DNN predictions. We detail SelfChecker, a self-checking system that monitors DNN outputs and triggers an alarm if the internal layer features of the model are inconsistent with the final prediction. SelfChecker also provides advice in the form of an alternative prediction. We evaluated SelfChecker on four popular image datasets and three DNN models and found that SelfChecker triggers correct alarms on 60.56% of wrong DNN predictions, and false alarms on 2.04% of correct DNN predictions. This is a substantial improvement over prior work (SelfOracle, Dissector, and ConfidNet). In experiments with self-driving car scenarios, SelfChecker triggers more correct alarms than SelfOracle for two DNN models (DAVE-2 and Chauffeur) with comparable false alarms. Our implementation is available as open source.

DNN validation and verification approaches that are input distribution agnostic waste effort on irrelevant inputs and report false property violations. Drawing on the large body of work on model-based validation and verification of traditional systems, we introduce the first approach that leverages environmental models to focus DNN falsification and verification on the relevant input space. Our approach, DFV, automatically builds an input distribution model using unsupervised learning, prefixes that model to the DNN to force all inputs to come from the learned distribution, and reformulates the property to the input space of the distribution model. This transformed verification problem allows existing DNN falsification and verification tools to target the input distribution – avoiding consideration of infeasible inputs. Our study of DFV with 7 falsification and verification tools, two DNNs defined over different data sets, and 93 distinct distribution models, provides clear evidence that the counterexamples found by the tools are much more representative of the data distribution, and it shows how the performance of DFV varies across domains, models, and tools.

Swarm robotics collectively solve problems that are challenging for individual robots, from environmental monitoring to entertainment. The algorithms enabling swarms allow individual robots of the swarm to plan, share, and coordinate their trajectories and tasks to achieve a common goal. Such algorithms rely on a large number of configurable parameters that can be tailored to target particular scenarios. This large configuration space, the complexity of the algorithms, and the dependencies with the robots’ setup and performance make debugging and fixing swarms configuration bugs extremely challenging. This paper proposes Swarmbug, a swarm debugging system that automatically diagnoses and fixes buggy behaviors caused by misconfiguration. The essence of Swarmbug is the novel concept called the degree of causal contribution (Dcc), which abstracts impacts of environment configurations (e.g., obstacles) to the drones in a swarm via behavior causal analysis. Swarmbug automatically generates, validates, and ranks fixes for configuration bugs. We evaluate Swarmbug on four diverse swarm algorithms. Swarmbug successfully fixes four configuration bugs in the evaluated algorithms, showing that it is generic and effective. We also conduct a real-world experiment with physical drones to show the Swarmbug’s fix is effective in the real-world.

A robotic system continuously measures its own motions and the external world during operation. Such measurements are with respect to some frame of reference, i.e., a coordinate system. A nontrivial robotic system has a large number of different frames and data have to be translated back-and-forth from a frame to another. The onus is on the developers to get such translation right. However, this is very challenging and error-prone, evidenced by the large number of questions and issues related to frame uses on developers' forum. Since any state variable can be associated with some frame, reference frames can be naturally modeled as variable types. We hence develop a novel type system that can automatically infer variables' frame types and in turn detect any type inconsistencies and violations of frame conventions. The evaluation on a set of 180 publicly available ROS projects shows that our system can detect 190 inconsistencies with 154 true positives. We reported 52 to developers and received 18 responses so far, with 15 fixed/acknowledged. Our technique also finds 45 violations of common practices.

The significant impact of TCP congestion control on the Internet highlights the importance of testing congestion control algorithm implementations (CCAIs) in various network environments. Many CCAI testing problems can be solved by exploring the numerical state space of CCAIs, which is defined by a group of numerical (and nonnumerical) state variables of the CCAIs. However, the current practices for automated numerical state space exploration are either limited by the approximate abstract CCAI models or inefficient due to the large space of network environment parameters and the complicated relation between the CCAI states and network environment parameters. In this paper, we propose an automated numerical state space exploration method, called ACT, which leverages the model-agnostic feature of random testing and greatly improves its efficiency by guiding random testing under the feedback iteratively obtained in a test. Our experiments on five representative Linux TCP CCAIs show that ACT can more efficiently explore a large numerical state space than manual testing, undirected random testing, and symbolic execution based testing, while without requiring an abstract CCAI model. ACT detects multiple design and implementation bugs of these Linux TCP CCAIs, including some new bugs not reported before.

Type annotations connect variables to domain-specific types. They enable the power of type checking and can detect faults early. In practice, type annotations have a reputation of being burdensome to developers. We lack, however, an empirical understanding of how and why they are burdensome. Hence, we seek to measure the baseline accuracy and speed for developers making type annotations to previously unseen code. We also study the impact of one or more type suggestions. We conduct an empirical study of 97 developers using 20 randomly selected code artifacts from the robotics domain containing physical unit types. We find that subjects select the correct physical type with just 51% accuracy, and a single correct annotation takes about 2 minutes on average. Showing subjects a single suggestion has a strong and significant impact on accuracy both when correct and incorrect, while showing three suggestions retains the significant benefits without the negative effects. We also find that suggestions do not come with a time penalty. We require subjects to explain their annotation choices, and we qualitatively analyze their explanations. We find that identifier names and reasoning about code operations are the primary clues for selecting a type. We also examine two state-of-the-art automated type annotation systems and find opportunities for their improvement.

The field of verification has advanced due to the interplay of theoretical development and empirical evaluation. Benchmarks play an important role in this by supporting the assessment of the state-of-the-art and comparison of alternative verification approaches. Recent years have witnessed significant developments in the verification of deep neural networks, but diverse benchmarks representing the range of verification problems in this domain do not yet exist. This paper describes a neural network verification benchmark generator, GDVB , that systematically varies aspects of problems in the benchmark that influence verifier performance. Through a series of studies, we illustrate how GDVB can assist in advancing the sub-field of neural network verification by more efficiently providing richer and less biased sets of verification problems.

While executing nominal tests on mobile robots is required for their validation, such tests may overlook faults that arise under trajectories that accentuate certain aspects of the robot's behavior. Uncovering such stressful trajectories is challenging as the input space for these systems, as they move, is extremely large, and the relation between a planned trajectory and its potential to induce stress can be subtle. To address this challenge we propose a framework that 1) integrates kinematic and dynamic physical models of the robot into the automated trajectory generation in order to generate valid trajectories, and 2) incorporates a parameterizable scoring model to efficiently generate physically valid yet stressful trajectories for a broad range of mobile robots. We evaluate our approach on four variants of a state-of-the-art quadrotor in a racing simulator. We find that, for non-trivial length trajectories, the incorporation of the kinematic and dynamic model is crucial to generate any valid trajectory, and that the approach with the best hand-crafted scoring model and with a trained scoring model can cause on average a 55.9% and 41.3% more stress than a random selection among valid trajectories. A follow-up study shows that the approach was able to induce similar stress on a deployed commercial quadrotor, with trajectories that deviated up to 6m from the intended ones.

Recommender systems help users to find products or services they may like when lacking personal experience or facing an overwhelming set of choices. Since unstable recommendations can lead to distrust, loss of profits, and a poor user experience, it is important to test recommender system stability. In this work, we present an approach based on inferred models of influence that underlie recommender systems to guide the generation of dataset modifications to assess a recommender’s stability. We implement our approach and evaluate it on several recommender algorithms using the MovieLens dataset. We find that influence-guided fuzzing can effectively find small sets of modifications that cause significantly more instability than random approaches.

The correctness of network protocol implementations is difficult to test mainly because of the temporal uncertain nature of network events. In order to test the correctness of a network protocol implementation using network simulators, we need to systematically simulate the behavior of the network protocol under all possible cases of temporal uncertain events, which is very time consuming. The recently proposed Symbolic Execution based Interval Branching (SEIB) simulates a group of uncertain cases together in a single simulation branch, and thus is more efficient than brute force testing. In this paper, we argue that the efficiency of SEIB could be further exponentially improved by eliminating unnecessary comparisons of the event timestamps. Specifically, we summarize and present three general types of unnecessary comparisons when SEIB is applied to a general network simulator, and then correspondingly propose three novel techniques to eliminate them. Our extensive simulations show that our techniques can improve the efficiency of SEIB by several orders of magnitude, such as from days to minutes.

Realistic network environments are commonly emulated by Internet application developers to test both the performance and the correctness of their applications. In this paper, we argue that emulating just realistic network environments may be inadequate for detecting hard-to-detect faults that have very low occurrence probabilities but potentially high impact if exposed in the real world. Specifically, we conduct extensive experiments to study the correctness testing capabilities of realistic and unlikely network environments. Our results show that small investments in emulating unlikely network environments may help in quickly detecting otherwise hard-to-detect faults.

New TCP congestion control algorithms are being developed and deployed in the Internet. However, it is challenging to test their correctness mainly due to the scalability problem caused by the extremely large number of test inputs. In this paper, we propose a scalable testing method, called SCCT, which tackles the scalability problem using two techniques. 1) SCCT tests only the congestion control algorithms of TCP at the interface level instead of the whole TCP at the packet level. 2) SCCT exercises an equivalence class of test inputs simultaneously using symbolic execution, instead of a single test input at a time. Both techniques can improve the scalability by many orders of magnitude. Our Linux TCP experiments on seven congestion control algorithms show that SCCT is scalable and quickly detects multiple Linux bugs that have not been reported before.

This project seeks to generate small Unmanned Aerial System (sUAS) flight paths that are broadly understood by the general population and can communicate states about both the sUAS and its understanding of the world. Previous work in sUAS flight paths has sought to communicate intent, destination, or emotion of the system without focusing on concrete states (e.g., low battery, landing, etc.). This work leverages biologically-based flight paths and experimental methodologies from human-human and human-humanoid robot interactions to assess the understanding of avian flight paths to communicate sUAS states to novice users. If successful, this work should inform: the human-robot interaction community about the perception of flight paths, sUAS manufacturers on how their systems could communicate with both operators and bystanders, and end users on ways to communicate with others when flying systems in public spaces. General design implications and future directions of work are suggested to build on the results here, which suggest that novice users gravitate towards labels they understand (draw attention and landing) while avoiding more technical labels (lost sensor).

Continuous integration (CI) development environments allow software engineers to frequently integrate and test their code. While CI environments provide advantages, they also utilize non-trivial amounts of time and resources. To address this issue, researchers have adapted techniques for test case prioritization (TCP) to CI environments. To date, however, the techniques considered have operated on test suites, and have not achieved substantial improvements. Moreover, they can be inappropriate to apply when system build costs are high. In this work we explore an alternative: prioritization of commits. We use a lightweight approach based on test suite failure and execution history that is highly efficient; our approach "continuously" prioritizes commits that are waiting for execution in response to the arrival of each new commit and the completion of each previously scheduled commit. We have evaluated our approach on three non-trivial CI data sets. Our results show that our approach can be more effective than prior techniques.

Prescribed fires can lessen wildfire severity and control invasive species, but they can also be risky and costly. Unmanned aerial systems can reduce those drawbacks by, for example, dropping ignition spheres to ignite the most hazardous areas. Existing systems, however, lack awareness of the fire vectors to operate autonomously, safely, and efficiently. In this work we address that limitation, introducing an approach that integrates a lightweight fire simulator and a planner for trajectories and ignition sphere drop waypoints. Both components are unique in that they are amenable to input from the system's sensors and the fire crew to increase fire awareness. We conducted a preliminary study that confirms that such inputs improve the accuracy of the fire simulation to counter the unpredictability of the target environment. The field study of the system showed that the fire-aware planner generated safe trajectories with effective ignitions leveraging the fire simulator predictions.

Sensor payloads suspended from parachutes are often used in atmospheric profiling applications. They drift freely and often end up landing in inaccessible regions that make their retrieval challenging or impossible. In this paper, we develop and evaluate an approach using a multirotor unmanned aerial system to autonomously retrieve the parachute while it is still in the air. The system relies only on the initial conditions of the parachute-payload system and feedback from the vehicle's onboard cameras to track and then intercept the parachute mid-air in under 40 seconds on average. We present the results from our field experiments where we demonstrate the feasibility of the system and discuss its applicability to long-term payload transportation systems.

Using an Unmanned Aerial Systems (UAS) to autonomously deploy soil sensors enables their installation in otherwise hard to access locations. In this paper, we present a system that integrates a UAS and a digging mechanism which can carry, secure, and install a small sensor into dirt effectively and efficiently. The integrated system includes 1) a low profile, light-weight, inexpensive auger mechanism, 2) a sensor carrying and deploying mechanism with low power consumption, and 3) sensors and software that control and evaluate the auger performance during digging. When tested on a suite of target soils and a target depth of 120mm, the system achieved a success rate of 100% for indoor tests and 92.5% for outdoors, verifying the potential of the approach.

Type annotations provide a link between program variables and domain-specific types. When combined with a type system, these annotations can enable early fault detection. For type annotations to be cost-effective in practice, they need to be both accurate and affordable for developers. We lack, however, an understanding of how burdensome type annotation is for developers. Hence, this work explores three fundamental questions: 1) how accurately do developers make type annotations; 2) how long does a single annotation take; and, 3) if a system could automatically suggest a type annotation, how beneficial to accuracy are correct suggestions and how detrimental are incorrect suggestions? We present results of a study of 71 programmers using 20 random code artifacts that contain variables with physical unit types that must be annotated. Subjects choose a correct type annotation only 51% of the time and take an average of 136 seconds to make a single correct annotation. Our qualitative analysis reveals that variable names and reasoning over mathematical operations are the leading clues for type selection. We find that suggesting the correct type boosts accuracy to 73%, while making a poor suggestion decreases accuracy to 28%. We also explore what state-of-the-art automated type annotation systems can and cannot do to help developers with type annotations, and identify implications for tool developers.

Program variables used in robotic and cyber-physical systems often have implicit physical units that cannot be determined from their variable types. Inferring an abstract physical unit type for variables and checking their physical unit type consistency is of particular importance for validating the correctness of such systems. For instance, a variable with the unit of ‘meter’ should not be assigned to another variable with the unit of ‘degree-per-second’. Existing solutions have various limitations such as requiring developers to annotate variables with physical units and only handling variables that are directly or transitively used in popular robotic libraries with known physical unit information. We observe that there are a lot of physical unit hints in these softwares such as variable names and specific forms of expressions. These hints have uncertainty as developers may not respect conventions. We propose to model them with probability distributions and conduct probabilistic inference. At the end, our technique produces a unit distribution for each variable. Unit inconsistencies can then be detected using the highly probable unit assignments. Experimental results on 30 programs show that our technique can infer units for 159.3% more variables compared to the state-of-the-art with more than 88.7% true positives, and inconsistencies detection on 90 programs shows that our technique reports 103.3% more inconsistencies with 85.3% true positives.

Changes to robotic systems as they are updated or upgraded often affect the flow of control and sensor data. Developers and users spend a significant amount of time tracing the impact of these changes that could otherwise have negative impacts on the robot's performance and behavior. Changes to the rates at which data is published from sensors, controllers, and other parts of the system are particularly subtle and difficult to detect. These rate changes, even if minor (e.g. lowering the frame rate of a camera), can propagate throughout the system and have broad impacts. In this work, we develop and implement an approach to help identify the set of components whose rate may be impacted by a system change. The approach builds on the insight that certain code patterns render component's outgoing data rate independent of the component's incoming data rate. We use that insight to reduce the number of components reported as affected by the change to minimize the number of components that must be reevaluated by the developer. A study of an implementation of the approach on three ROS systems shows that it can reduce the size of the impact set by up to 41% in cases when the changes have broad data impacts. The analysis is performed at compile time and only adds a third more to the compilation time.

This work presents a study of robot software using the Robot Operating System (ROS), focusing on detecting inconsistencies in physical unit manipulation. We discuss how dimensional analysis, the rules governing how physical quantities are combined, can be used to detect inconsistencies in robot software that are otherwise difficult to detect. Using a corpus of ROS software with 5.9M lines of code, we measure the frequency of these dimensional inconsistencies and find them in 6% (211 / 3,484) of repositories that use ROS. We find that the inconsistency type `Assigning multiple units to a variable' accounts for 75% of inconsistencies in ROS code. We identify the ROS classes and physical units most likely to be involved with dimensional inconsistencies, and find that the ROS Message type geometry_msgs::Twist is involved in over half of all inconsistencies and is used by developers in ways contrary to Twist's intent. We further analyze the frequency of physical units used in ROS programs as a proxy for assessing how developers use ROS, and discuss the practical implications of our results including how to detect and avoid these inconsistencies.

Systems interacting with the physical world operate on quantities measured with physical units. When unit operations in a program are inconsistent with the physical units' rules, those systems may suffer. Existing approaches to support unit consistency in programs can impose an unacceptable burden on developers. In this paper, we present a lightweight static analysis approach focused on physical unit inconsistency detection that requires no end-user program annotation, modification, or migration. It does so by capitalizing on existing shared libraries that handle standardized physical units, common in the cyber-physical domain, to link class attributes of shared libraries to physical units. Then, leveraging rules from dimensional analysis, the approach propagates and infers units in programs that use these shared libraries, and detects inconsistent unit usage. We implement and evaluate the approach in a tool, analyzing 213 open-source systems containing +900,000 LOC, finding inconsistencies in 11% of them, with an 87% true positive rate for a class of inconsistencies detected with high confidence. An initial survey of robot system developers finds that the unit inconsistencies detected by our tool are 'problematic', and we investigate how and when these inconsistencies occur.

Systems that interact with the physical world use software that represents and manipulates physical quantities. To operate correctly, these systems must obey the rules of how quantities with physical units can be combined, compared, and manipulated. Incorrectly manipulating physical quantities can cause faults that go undetected by the type system, likely manifesting later as incorrect behavior. Existing approaches for inconsistency detection require code annotation, physical unit libraries, or specialized programming languages. We introduce Phriky-Units, a static analysis tool that detects physical unit inconsistencies in robotic software without developer annotations. It does so by capitalizing on existing shared libraries that handle standardized physical units, common in the cyber-physical domain, to link class attributes of shared libraries to physical units. In this work, we describe how Phriky-Units works, provide details of the implementation, and explain how Phriky-Units can be used. Finally we present a summary of an empirical evaluation showing it has an 87% true positive rate for a class of inconsistencies we detect with high-confidence.

The majority of Internet traffic is transferred by transport protocols. The correctness of these transport protocol implementations is hard to validate as their behaviors depend not only on their protocols but also on their network environments that can introduce dynamic packet delay and loss. Random testing, widely used in industry due to its simplicity and low cost, struggles to detect packet delay related faults which occur with low probability. Symbolic execution based testing is promising at detecting such low probability faults, but it requires large testing budgets as it attempts to cover a prohibitively large input space of packet dynamics. To improve its cost-effectiveness, we propose two domain-specific heuristic techniques, called packet retransmission based priority and network state based priority, which are motivated by two common transport protocol properties. In our experiments using the Linux TFTP programs, our techniques improve the cost-effectiveness of symbolic execution based testing for transport protocols, detecting three times as many faults when the budget is in the range of minutes and hours.

Our community constantly pushes the state-of-the-art by introducing "new" techniques. These techniques often build on top of, and are compared against, existing systems that realize previously published techniques. The underlying assumption is that existing systems correctly represent the techniques they implement. This paper examines that assumption through a study of KLEE, a popular and well-cited tool in our community. We briefly describe six improvements we made to KLEE, none of which can be considered "new" techniques, that provide order-of-magnitude performance gains. Given these improvements, we then investigate how the results and conclusions of a sample of papers that cite KLEE are affected. Our findings indicate that the strong emphasis on introducing "new" techniques may lead to wasted effort, missed opportunities for progress, an accretion of artifact complexity, and questionable research conclusions (in our study, 27% of the papers that depend on KLEE can be questioned). We conclude by revisiting initiatives that may help to realign the incentives to better support the foundations on which we build.

Robotic systems often have complex configuration spaces that, when poorly set, can cause failures. In this work we take advantage of the close synergy between user and robot in co-robotic systems to better diagnose and overcome configuration failures. We leverage users' understanding of the system to mark failures they observe while the system is in operation. A marked failure indicates that the robot either “did not do something when it should have” or “did something when it should not have”. The failure marking is coupled with an automated analysis approach that identifies code predicates involving configuration parameters that may be relevant to each failure type, ranks the parameters according to their potential to be associated with the failure, and suggests adjustments based on the run-time outcome of those predicates. We present the approach, its implementation, and a preliminary study on a configurable unmanned air system. The results show how the approach can successfully help diagnose and adjust faulty configuration parameters in co-robotic systems.

Network programs are difficult to test, especially under the large space of network program behavior defined by packet dynamics such as packet delay and packet loss. It is unlikely for common approaches using testbeds with random packet dynamics to cover the prohibitively large number of packet dynamics possibilities in a limited time. In this paper, we leverage symbolic execution to find the equivalence classes of packet dynamics which lead to exactly the same network program behavior, in order to efficiently check the large space of network program behavior. Specifically, we propose and develop a network program test platform, called Symbolic Packet Dynamics (SPD), to automatically and transparently test unmodified network programs for low- probability bugs and extreme-case performance under packet dynamics. SPD uses symbolic representation of packet dynamics, instead of random packet dynamics. Our experiments show that SPD can achieve significantly much higher packet dynamics coverage than random packet dynamics within the same amount of time, and thus it is much easier and takes much shorter time for SPD to detect low-probability bugs and extreme-case performance.

Tests are increasingly specified as programs. Expressing tests as code is advantageous in that developers are comfortable writing and running code, and tests can be automated and reused as the software evolves. Tests expressed as code, however, can also contain faults. Some test faults are similar to those found in application code, while others are more subtle, caused by incorrect implementation of testing concepts and processes. These faults may cause a test to fail when it should not, or allow program faults to go undetected. In this work we explore whether lightweight static analyses can be cost-effective in pinpointing patterns associated with faults tests. Our exploration includes a categorization and explanation of test patterns, and their application to 12 open source projects that include over 40K tests. We found that several patterns, detectable through simple and efficient static analyses of just the test code, can detect faults with a low false positive rate, while other patterns would require a more sophisticated and extensive code analysis to be useful.

With the advent of large code repositories and sophisticated search capabilities, code search is increasingly becoming a key software development activity. In this work we shed some light into how developers search for code through a case study performed at Google, using a combination of survey and log-analysis methodologies. Our study provides insights into what developers are doing and trying to learn when per- forming a search, search scope, query properties, and what a search session under different contexts usually entails. Our results indicate that programmers search for code very frequently, conducting an average of five search sessions with 12 total queries each workday. The search queries are often targeted at a particular code location and programmers are typically looking for code with which they are somewhat familiar. Further, programmers are generally seeking answers to questions about how to use an API, what code does, why something is failing, or where code is located.

Building is an integral part of the software development process. However, little is known about the compiler errors that occur in this process. In this paper, we present an empirical study of 26.6 million builds produced during a period of nine months by thousands of developers. We describe the workflow through which those builds are generated, and we analyze failure frequency, compiler error types, and resolution efforts to fix those compiler errors. The results provide insights on how a large organization build process works, and pinpoints errors for which further developer support would be most effective.

Remote sensing by Unmanned Aerial Vehicles (UAVs) is changing the way agriculture operates by increasing the spatial-temporal resolution of data collection. Micro-UAVs have the potential to further improve and enrich the data collected by operating close to the crops, enabling the collection of higher spatio-temporal resolution data. In this paper, we present a UAV-mounted measurement system that utilizes a laser scanner to compute crop heights, a critical indicator of crop health. The system filters, transforms, and analyzes the cluttered range data in real-time to determine the distance to the ground and to the top of the crops. We assess the system in an indoor testbed and in a corn field. Our findings indicate that despite the dense canopy and highly variable sensor readings, we can precisely fly over crops and measure its height to within 5cm of measurements gathered using current measurement technology.

Uncertainty is becoming more prevalent in the software systems we build, introducing challenges in the way we develop software, especially in software testing. In this work we explore how uncertainty affects software testing, how it is managed currently, and how it could be treated more effectively.

In continuous integration development environments, software engineers frequently integrate new or changed code with the mainline codebase. This can reduce the amount of code rework that is needed as systems evolve and speed up development time. While continuous integration processes traditionally require that extensive testing be performed following the actual submission of code to the codebase, it is also important to ensure that enough testing is performed prior to code submission to avoid breaking builds and delaying the fast feedback that makes continuous integration desirable. In this work, we present algorithms that make continuous integration processes more cost-effective. In an initial pre-submit phase of testing, developers specify modules to be tested, and we use regression test selection techniques to select a subset of the test suites for those modules that render that phase more cost-effective. In a subsequent post-submit phase of testing, where dependent modules as well as changed modules are tested, we use test case prioritization techniques to ensure that failures are reported more quickly. In both cases, the techniques we utilize are novel, involving algorithms that are relatively inexpensive and do not rely on code coverage information -- two requirements for conducting testing cost-effectively in this context. To evaluate our approach, we conducted an empirical study on a large data set from Google that we make publicly available. The results of our study show that our selection and prioritization techniques can each lead to cost-effectiveness improvements in the continuous integration process.

Programmers frequently search for source code to reuse using keyword searches. The search effectiveness in facilitating reuse, however, depends on the programmer's ability to specify a query that captures how the desired code may have been implemented. Further, the results often include many irrelevant matches that must be filtered manually. More semantic search approaches could address these limitations, yet existing approaches are either not flexible enough to find approximate matches or require the programmer to define complex specifications as queries. We propose a novel approach to semantic code search that addresses several of these limitations and is designed for queries that can be described using a concrete input/output example. In this approach, programmers write lightweight specifications as inputs and expected output examples. Unlike existing approaches to semantic search, we use an SMT solver to identify programs or program fragments in a repository, which have been automatically transformed into constraints using symbolic analysis, that match the programmer-provided specification. We instantiated and evaluated this approach in subsets of three languages, the Java String library, Yahoo! Pipes mashup language, and SQL select statements, exploring its generality, utility, and trade-offs. The results indicate that this approach is effective at finding relevant code, can be used on its own or to filter results from keyword searches to increase search precision, and is adaptable to find approximate matches and then guide modifications to match the user specifications when exact matches do not already exist. These gains in precision and flexibility come at the cost of performance, for which underlying factors and mitigation strategies are identified.

Validating code handling exceptional behavior is difficult, particularly when dealing with external resources that may be noisy and unreliable, as it requires (1) systematic exploration of the space of exceptions that may be thrown by the external resources, and (2) setup of the context to trigger specific patterns of exceptions. In this work, we first present a study quantifying the magnitude of the problem by inspecting the bug repositories of a set of popular applications in the increasingly relevant domain of Android mobile applications. The study revealed that 22% of the confirmed and fixed bugs have to do with poor exceptional handling code, and half of those correspond to interactions with external resources. We then present an approach that addresses this challenge by performing an systematic amplification of the program space explored by a test by manipulating the behavior of external resources. Each amplification attempts to expose a program's exception handling constructs to new behavior by mocking an external resource so that it returns normally or throws an exception following a predefined set of patterns. Our assessment of the approach indicates that it can be fully automated, is powerful enough to detect 67% of the faults reported in the bug reports of this kind, and is precise enough that 78% of the detected anomalies are fixed, and it has a great potential to assist developers.

Context: Programmers frequently compose keyword queries as they use information search engines to look for source code. This syntactic approach to code search is often imprecise and results in wasted efforts looking through irrelevant results. Semantic code search approaches aim to address this weakness by formulating queries that specify behavior, rather than keywords. A recent approach uses input/output examples as queries that illustrate the behavior of desired code. The technical feasibility of this approach has been illustrated, yet the impact of the change in the query model has not been assessed. Objective: We explore the cost and accuracy of using input/output queries for code search from the perspective of the programmer, considering two programming languages, Yahoo! Pipes and SQL. Method: We perform a controlled user study with 109 participants from two groups, students and Mechanical Turk, to assess the cost and accuracy of using input/output search queries. Results: Our results show that programmers can compose input/output queries in the targeted domains with over 92% average accuracy and in less than two minutes. Conclusion: The use of input/output queries does not seem to limit the early promise of semantic searches that depend on it.

System monitoring can help to detect abnormalities and avoid failures. Crafting monitors for today's robotic systems, however, can be very difficult due to the systems' inherent complexity. In this work we address this challenge through an approach that automatically infers system invariants and synthesizes those invariants into monitors. The approach is novel in that it derives invariants by observing the messages passed between system nodes and the invariants types are tailored to match the spatial, temporal, and operational attributes of robotic systems. Further, the generated monitor can be seamlessly integrated into systems built on top of publish-subscribe architectures. An application of the technique on a system consisting of a unmanned aerial vehicle (UAV) landing on a moving platform shows that it can significantly reduce the number of crashes in unexpected landing scenarios.

Runtime monitoring has proven effective in detecting property violations, but it can incur high overhead when monitoring just a single property - particularly when the property relates multiple objects. In practice developers will likely monitor multiple properties in the same execution which will lead to even higher overhead.

Model checking is an established method for verifying behavioral properties of system models. But model checkers tend to support low-level modeling languages that require intricate models to represent even the simplest systems. Modeling complexity arises in part from the need to encode domain knowledge at relatively low levels of abstraction.

SUMMARY Web Service Definition Language (WSDL) is being increasingly used to specify web service interfaces. Specifications of this type, however, are often incomplete or imprecise, which can create difficulties for client developers who rely on the WSDL files. To address this problem a semi‐automated methodology that probes a web service with semi‐automatically generated inputs and analyzes the resulting outputs is presented. The results of the analysis are compared to the original WSDL file and differences between the observed behavior of the service and the WSDL specifications are reported to the user. The methodology is applied in two case studies involving two popular commercial (Amazon and eBay) web services. The results show that the methodology can scale, and that it can uncover problems in the WSDL files that may impact a large number of clients. Copyright © 2011 John Wiley & Sons, Ltd.

With the emergence of tools to support visual mashup creation, tens of thousands of users have started to access, manipulate, and compose data from web sources. We have observed, however, that mashups created by these users tend to suffer from deficiencies that propagate as mashups are reused, which happens frequently. To address these deficiencies, we would like to bring some of the benefits of software engineering techniques to the end users creating these programs. In this work, we focus on identifying code smells indicative of the deficiencies we observed in web mashups programmed in the popular Yahoo! Pipes environment. Through an empirical study, we explore the impact of those smells on the preferences of 61 users, and observe that a significant majority of users prefer mashups without smells. We then introduce refactorings targeting those smells. These refactorings reduce the complexity of the mashup programs, increase their abstraction, update broken data sources and dated components, and standardize their structures to fit the community development patterns. Our assessment of a sample of over 8,000 mashups shows that smells are present in 81 percent of them and that the proposed refactorings can reduce the number of smelly mashups to 16 percent, illustrating the potential of refactoring to support the thousands of end-users programming mashups. Further, we explore how the smells and refactorings can apply to other end-user programming domains to show the generalizability of our approach.

Validating code handling exceptional behavior is difficult, particularly when dealing with external resources that may be noisy and unreliable, as it requires: 1) the systematic exploration of the space of exceptions that may be thrown by the external resources, and 2) the setup of the context to trigger specific patterns of exceptions. In this work we present an approach that addresses those difficulties by performing an exhaustive amplification of the space of exceptional behavior associated with an external resource that is exercised by a test suite. Each amplification attempts to expose a program exception handling construct to new behavior by mocking an external resource so that it returns normally or throws an exception following a predefined pattern. Our assessment of the approach indicates that it can be fully automated, is powerful enough to detect 65% of the faults reported in the bug reports of this kind, and is precise enough that 77% of the detected anomalies correspond to faults fixed by the developers.

This paper presents CraneTracker, a novel sensor platform for monitoring migratory birds. The platform is designed to monitor Whooping Cranes, an endangered species that conducts an annual migration of 4,000 km between southern Texas and north-central Canada. CraneTracker includes a rich set of sensors, a multi-modal radio, and power control circuitry for sustainable, continental-scale information delivery during migration. The need for large-scale connectivity motivates the use of cellular technology in low-cost sensor platforms augmented by a low-power transceiver for ad-hoc connectivity. This platform leads to a new class of cellular sensor networks (CSNs) for time-critical and mobile sensing applications. The CraneTracker is evaluated via field tests on Wild Turkeys, Siberian Cranes, and an on-going alpha deployment with wild Sandhill Cranes. Experimental evaluations demonstrate the potential of energy-harvesting CSNs for wildlife monitoring in large geographical areas, and reveal important insights into the movements and behaviors of migratory animals. In addition to benefiting ecological research, the developed platform is expected to extend the application domain of sensor networks and enable future research applications.

Modern robotics systems rely on distributed event-based frameworks to facilitate the assembly of software out of collections of reusable components. These frameworks express component dependencies in data that encode event publish-subscribe relations. This loosely coupled architecture makes it difficult for developers to understand the dependencies and to predict the impacts of a change to a component as the components grow in number and complexity. Moreover, this encoding of dependencies renders traditional techniques for analyzing component dependencies inapplicable, because the dependencies are bound by communication channels rather than data. In this work, we present a program analysis technique that automatically extracts a model of component dependencies from distributed system source code. This model identifies not only the temporal dependencies among components, but also the conditions under which those dependencies are realized. We have implemented the analysis and applied it to systems developed in ROS. The resulting models are succinct and precise, which suggests that programmers will find them comprehensible, and they can be used to document important global dependencies in a system, to compare different versions to identify the impacts of component changes, and to help locate errors.

Load tests validate whether a system’s performance is acceptable under extreme conditions. Traditional load testing approaches are black-box, inducing load by increasing the size or rate of the input. Symbolic execution based load testing techniques complement traditional approaches by enabling the selection of precise input values. However, as the programs under analysis or their required inputs increase in size, the analyses required by these techniques either fail to scale up or sacrifice test effectiveness. We propose a new approach that addresses this limitation by performing load test generation compositionally. It uses existing symbolic execution based techniques to analyze the performance of each system component in isolation, summarizes the results of those analyses, and then performs an analysis across those summaries to generate load tests for the whole system. In its current form, the approach can be applied to any system that is structured in the form of a software pipeline. A study of the approach revealed that it can generate effective load tests for Unix and XML pipelines while outperforming state-of-the-art techniques.

Testing the components of a distributed system is challenging as it requires consideration of not just the state of a component, but also the sequence of messages it may receive from the rest of the system or the environment. Such messages may vary in type and content, and more particularly, in the frequency at which they are generated. All of these factors, in the right combination, may lead to faulty behavior. In this paper we present an approach to address these challenges by systematically analyzing a component in a distributed system to identify specific message sequences and frequencies at which a failure can occur. At the core of the analysis is the generation of a test driver that defines the space of message sequences to be generated, the exploration of that space through the use of dynamic symbolic execution, and the timing and analysis of the generated tests to identify problematic frequencies. We implemented our approach in the context of the popular Robotic Operating System and investigated its application to three systems of increasing complexity.

Searching for code is a common task among programmers, with the ultimate goal of reuse. While the process of searching for code -- issuing a query and selecting a relevant match -- is straightforward, several costs must be balanced, including the costs of specifying the query, examining the results to find desired code, and not finding a relevant result. For syntactic searches the query cost is quite low, but the results are often irrelevant, so the examination cost is high and matches may be missed. Semantic searches may return more relevant results, but current techniques that involve writing complex specifications or executing code against test cases are costly to the developer. We propose an approach for semantic search in which developers specify lightweight specifications and an SMT solver identifies matching programs from a repository. A program repository is automatically encoded offline so the search is efficient. Programs are encoded at various abstraction levels to enable partial matches when no, or few, exact matches exist. We instantiate this approach on a subset of the Yahoo! Pipes mashup language. Preliminary results show promise for the feasibility of the approach.

End-user programmers outnumber professionals programmers, write software that matters to an increasingly large number of users, and face software engineering challenges that are similar to their professionals counterparts. Yet, we know little about how these end-user programmers create and share artifacts as part of a community. To gain a better understanding of these issues, we perform an artifact-based community analysis of 32,000 mashups from the Yahoo! Pipes repository. We observed that, like with other online communities, there is great deal of attrition but authors that persevere tend to improve over time, creating pipes that are more configurable, diverse, complex, and popular. We also discovered, however, that end-user programmers employ the repository in different ways than professionals, do not effectively reuse existing programs, and in most cases do not have an awareness of the community. We discuss the implications of these findings.

Mashups are becoming increasingly popular as end users are able to easily access, manipulate, and compose data from many web sources. We have observed, however, that mashups tend to suffer from deficiencies that propagate as mashups are reused. To address these deficiencies, we would like to bring some of the benefits of software engineering techniques to the end users creating these programs. In this work, we focus on identifying code smells indicative of the deficiencies we observed in web mashups programmed in the popular Yahoo! Pipes environment. Through an empirical study, we explore the impact of those smells on end-user programmers and observe that users generally prefer mashups without smells. We then introduce refactorings targeting those smells, reducing the complexity of the mashup programs, increasing their abstraction, updating broken data sources and dated components, and standardizing their structures to fit the community development patterns. Our assessment of a large sample of mashups shows that smells are present in 81% of them and that the proposed refactorings can reduce the number of smelly mashups to 16%, illustrating the potential of refactoring to support the thousands of end users programming mashups.

Load tests aim to validate whether system performance is acceptable under peak conditions. Existing test generation techniques induce load by increasing the size or rate of the input. Ignoring the particular input values, however, may lead to test suites that grossly mischaracterize a system's performance. To address this limitation we introduce a mixed symbolic execution based approach that is unique in how it 1) favors program paths associated with a performance measure of interest, 2) operates in an iterative-deepening beam-search fashion to discard paths that are unlikely to lead to high-load tests, and 3) generates a test suite of a given size and level of diversity. An assessment of the approach shows it generates test suites that induce program response times and memory consumption several times worse than the compared alternatives, it scales to large and complex inputs, and it exposes a diversity of resource consuming program behavior.

Runtime monitoring can provide important insights about a program’s behavior and, for simple properties, it can be done efficiently. Monitoring properties describing sequences of program states and events, however, can result in significant runtime overhead. This is particularly critical when monitoring programs deployed at user sites that have low tolerance for overhead. In this paper we present a novel approach to reducing the cost of runtime monitoring of path properties. A set of original properties are composed to form a single integrated property that is then systematically decomposed into a set of properties that encode necessary conditions for property violations. The resulting set of properties forms a lattice whose structure is exploited to select a sample of properties that can lower monitoring cost, while preserving violation detection power relative to the original properties. The lattice is then complemented with a weighting scheme that assigns each property a different priority that can be adjusted continuously to better drive the property sampling process. Our evaluation using the Hibernate API reveals that our approach produces a rich, structured set of properties that enables control of monitoring overhead, while detecting more violations more quickly than alternative techniques.

The power and the generality of the findings obtained through empirical studies are bounded by the number and type of participating subjects. In software engineering, obtaining a large number of adequate subjects to evaluate a technique or tool is often a major challenge. In this work we explore the use of crowdsourcing as a mechanism to address that challenge by assisting in subject recruitment. More specifically, through this work we show how we adapted a study to be performed under an infrastructure that not only makes it possible to reach a large base of users but it also provides capabilities to manage those users as the study is being conducted. We discuss the lessons we learned through this experience, which illustrate the potential and tradeoffs of crowdsourcing software engineering studies.

Developing applications for wireless sensor networks (WSNs) can provide many challenges. Environmental conditions have a large impact on the behavior of an application, but it may not be feasible to replicate the conditions of the deployment environment while creating the application. Furthermore, long-term deployment of monitoring applications require extensive pre-deployment analysis of such applications since the sensors cannot be accessed after their deployment. Through a combination of simulation and software engineering practices, it is possible to rigorously test and validate the software for WSNs. In this paper, several methods for simulating distributed mobile WSNs and testing the software are provided. These methods are used in the development of a WSN that was deployed to track Whooping Cranes during their year long migration.

There has been significant interest in equipping programs with runtime checks aimed at detecting errors to improve fault detection during testing and in the field. Recent work in this area has studied methods for efficiently monitoring a program execution's conformance to path property specifications, e.g., such as those captured by a finite state automaton. These techniques show great promise, but their broad applicability is hampered by the fact that for certain combinations of programs and properties the overhead of checking can slow the program down by up to 3500%.

Applications running on mobile devices are intensely context-aware and adaptive. Streams of context values continuously drive these applications, making them very powerful but, at the same time, susceptible to undesired configurations. Such configurations are not easily exposed by existing validation techniques, thereby leading to new analysis and testing challenges. In this paper, we address some of these challenges by defining and applying a new model of adaptive behavior called an Adaptation Finite-State Machine (A-FSM) to enable the detection of faults caused by both erroneous adaptation logic and asynchronous updating of context information, with the latter leading to inconsistencies between the external physical context and its internal representation within an application. We identify a number of adaptation fault patterns, each describing a class of faulty behaviors. Finally, we describe three classes of algorithms to detect such faults automatically via analysis of the A-FSM. We evaluate our approach and the trade-offs between the classes of algorithms on a set of synthetically generated Context-Aware Adaptive Applications (CAAAs) and on a simple but realistic application in which a cell phone's configuration profile changes automatically as a result of changes to the user's location, speed, and surrounding environment. Our evaluation describes the faults our algorithms are able to detect and compares the algorithms in terms of their performance and storage requirements.

Service Oriented Architectures (SOAs) are becoming increasingly popular and powerful. Fueling that growth is the availability of independent web services that can be cost-effectively composed with other services to provide richer functionality. The reasons that make these systems easier to build, however, also make them more challenging to test. Independent web services usually provide just an interface, enough to invoke them and develop some general (black-box) tests, but insufficient for a tester to develop an adequate understanding of the integration quality between the application and independent web services. To address this lack we propose a "whitening" approach to make web services more transparent through the addition of an intermediate coverage service. The approach, named Service Oriented Coverage Testing (SOCT), provides a tester with feedback about how a whitened service, called a Testable Service, is exercised. In this paper we introduce the SOCT approach, implement an instance of it, and perform a preliminary study to show its feasibility and potential value. SOCT enables SOA white-box testing, while maintaining SOA flexibility, dynamism and loose coupling.

Coverage measures help to determine whether a test suite exercises a program adequately according to a testing criterion. Many existing measures, however, are defined over coverage domains that cannot be precisely calculated, rendering them of limited value in assessing the extent of testing activities. To exploit the use of such measures, we formalize saturation-based test adequacy, a form of adequacy focused on the rate at which coverage increases during test suite execution. We define a family of coverage metrics for concurrent program testing that are well-suited to saturation-based adequacy and present a study that explores their cost and effectiveness. The results of this study suggest that saturation-based testing can serve as an effective complement to traditional notions of coverage-based testing.

Transferring data across applications is a common end user task, and copying and pasting via the clipboard lets users do so relatively easily. Using the clipboard, however, can also introduce inefficiencies and errors in user tasks. To help researchers and tool developers understand and address these problems, we studied how end users interact with the clipboard through cut, copy, and paste actions. This study was performed by logging clipboard interactions while end users performed everyday tasks. From the clip-board usage data, we have identified several usage patterns that describe how data is transferred within the desktop environment. Such patterns help us understand end user behavior and indicate areas in which clipboard support tools can be improved.

Unit test cases are focused and efficient. System tests are effective at exercising complex usage patterns. Differential unit tests (DUT) are a hybrid of unit and system tests that exploits their strengths. They are generated by carving the system components, while executing a system test case, that influence the behavior of the target unit, and then re-assembling those components so that the unit can be exercised as it was by the system test. In this paper we show that DUTs retain some of the advantages of unit tests, can be automatically generated, and have the potential for revealing faults related to intricate system executions. We present a framework for carving and replaying DUTs that accounts for a wide variety of strategies and tradeoffs, we implement an automated instance of the framework with several techniques to mitigate test cost and enhance flexibility and robustness, and we empirically assess the efficacy of carving and replaying DUTs on three software artifacts.

Static analysis tools report software defects that may or may not be detected by other verification methods. Two challenges complicating the adoption of these tools are spurious false positive warnings and legitimate warnings that are not acted on. This paper reports automated support to help address these challenges using logistic regression models that predict the foregoing types of warnings from signals in the warnings and implicated code. Because examining many potential signaling factors in large software development settings can be expensive, we use a screening methodology to quickly discard factors with low predictive power and cost-effectively build predictive models. Our empirical evaluation indicates that these models can achieve high accuracy in predicting accurate and actionable static analysis warnings, and suggests that the models are competitive with alternative models built without screening.

Identifying truly distinct traces is crucial for the performance of many dynamic analysis activities. For example, given a set of traces associated with a program failure, identifying a subset of unique traces can reduce the debugging effort by producing a smaller set of candidate fault locations. The process of identifying unique traces, however, is subject to the presence of irrelevant variations in the sequence of trace events, which can make a trace appear unique when it is not. In this paper we present an approach to reduce inconsequential and potentially detrimental trace variations. The approach decomposes traces into segments on which irrelevant variations caused by event ordering or repetition can be identified, and then used to normalize the traces in the pool. The approach is investigated on two well-known client dynamic analyses by replicating the conditions under which they were originally assessed, revealing that the clients can deliver more precise results with the normalized traces.

Run-time monitoring can provide important insights about a program's behavior and, for simple properties, it can be done efficiently. Monitoring properties describing sequences of program states and events, however, can result in significant run-time overhead. In this paper we present a novel approach to reducing the cost of run-time monitoring of path properties. Properties are composed to form a single integrated property that is then systematically decomposed into a set of properties that encode necessary conditions for property violations. The resulting set of properties forms a lattice whose structure is exploited to select a sample of properties that can lower monitoring cost, while preserving violation detection power relative to the original properties. Preliminary studies for a widely used Java API reveal that our approach produces a rich, structured set of properties that enables control of monitoring overhead, while detecting more violations than alternative techniques.

Unit tests are focused, efficient, and there are many techniques to support their automatic generation. Coarser granularity tests, however, are necessary to validate the behavior of larger software components, and are also likely to be more robust in the presence of program changes. This paper investigates whether coarser granularity tests can be automatically generated by aggregating unit tests. We leverage our Differential Unit Test (DUT) framework to represent unit tests, define a space of potential aggregations of those unit tests, and implement a strategy to traverse that space to generate Aggregated DUTs (A- DUTs) that validate the effects of multiple method calls on a (set of) receiver object(s). An empirical study of A-DUTs on two applications shows their tradeoffs with DUTs and their potential to increase the number of versions for which tests remain usable relative to method level tests.

Web macros give web browser users ways to "program" tedious tasks, allowing those tasks to be repeated more quickly and reliably than when performed by hand. Web macros face dependability problems of their own, however: changes in websites or failure on the part of end-user programmers to anticipate possible macro behaviors can cause macros to act incorrectly, often in ways that are difficult to detect. We would like to provide at least some of the benefits of software engineering methodologies to the creators of web macros. To do this we adapt assertions to web-macro programming scenarios. While assertions are well-known to professional software engineers, our web macro assertions are unique in their focus on website evolution, are generated automatically, and encode the expectations and assumptions of a rapidly growing group of users who often have limited formal programming expertise. We have integrated our techniques for assertion generation and evaluation into a web macro tool, and performed an empirical study investigating its use. Our results show that the assertions can help web macro users detect macro failures and correct macro faults.

Detecting and characterizing the effects of software changes is a fundamental component of software maintenance. Version differencing information can be used to perform version merging, infer change characteristics, produce program documentation, and guide program re-validation. Existing techniques for characterizing code changes, however, are imprecise leading to unnecessary maintenance efforts.

Applications running on mobile devices are heavily context-aware and adaptive, leading to new analysis and testing challenges as streams of context values drive these applications to undesired configurations that are not easily exposed by existing validation techniques. We address this challenge by employing a finite-state model of adaptive behavior to enable the detection of faults caused by (1) erroneous adaptation logic, and (2) asynchronous updating of context information, which leads to inconsistencies between the external physical context and its internal representation within an application. We identify a number of adaptation fault patterns, each describing a class of faulty behaviors that we detect automatically by analyzing the system's adaptation model. We illustrate our approach on a simple but realistic application in which a cellphone's configuration profile is changed automatically based on the user's location, speed and surrounding environment. © 2008 ACM.

Model checkers search the space of possible program behaviors to detect errors and to demonstrate their absence. Despite major advances in reduction and optimization techniques, state-space search can still become cost-prohibitive as program size and complexity increase. In this paper, we present a technique for dramatically improving the cost- effectiveness of state-space search techniques for error detection using parallelism. Our approach can be composed with all of the reduction and optimization techniques we are aware of to amplify their benefits. It was developed based on insights gained from performing a large empirical study of the cost-effectiveness of randomization techniques in state-space analysis. We explain those insights and our technique, and then show through a focused empirical study that our technique speeds up analysis by factors ranging from 2 to over 1000 as compared to traditional modes of state-space search, and does so with relatively small numbers of parallel processors.

Analyzing a program run can provide important insights about its correctness. Dynamic analysis of complex correctness properties, however, usually results in significant run-time overhead and, consequently, it is rarely used in practice. In this paper, we present an approach for exploiting properties of stateful program specifications to reduce the cost of their dynamic analysis. With our approach, analysis results are guaranteed to be identical to those of a traditional expensive dynamic analyses, while analysis cost is very low - between 23% and 33% more than the un-instrumented program for the analyses we studied. We describe the principles behind our adaptive online program analysis technique, extentions to our Java run-time analysis framework that support such analyses, and report on the performance and capabilities of two different families of adaptive online program analyses.

Software testing efforts account for a large part of software development costs. However, as educators, we struggle to properly prepare students to perform software testing activities. This struggle is caused by multiple factors: (1) it is challenging to effectively incorporate software testing into an already over-packed curriculum, (2) ad-hoc efforts to teach testing generally happen too late in the students' career, after bad habits have already been developed, and (3) these efforts lack the necessary institutional consistency and support to be effective. To address these challenges we created Bug Hunt, a web-based tutorial to engage students in learning software testing strategies. In this paper we describe the most interesting aspects of the tutorial including the lessons and feedback mechanisms, and the facilities for instructors to configure the tutorial and obtain automatic student assessment. We also present the lessons learned after two years of deployment.

The incorporation of context-awareness capabilities into pervasive applications allows them to leverage contextual information to provide additional services while maintaining an acceptable quality of service. These added capabilities, however, introduce a distinct input space that can affect the behavior of these applications at any point during their execution, making their validation quite challenging. In this paper, we introduce an approach to improve the test suite of a context-aware application by identifying context-aware program points where context changes may affect the application's behavior, and by systematically manipulating the context data fed into the application to increase its exposure to potentially valuable context variations. Preliminary results indicate that the approach is more powerful than existing testing approaches used on this type of application.

Identifying truly distinct traces is crucial for the performance and practicality of many dynamic analysis activities. For example, given a trace pool resulting from program failures, identifying the set of distinct traces can reduce the debugging effort by more quickly producing a smaller set of candidate fault locations. The process of discriminating valuable traces, however, is subject to the presence of irrelevant variations in the trace constitution, i.e., the sequence of events in a trace, that can make a trace appear unique when it is not, leading to the retention of a trace that adds no value. In this paper we present an approach to address inconsequential and potentially detrimental trace variations. The approach decomposes traces into segments on which irrelevant variations caused by event ordering or repetition can be detected and removed. The approach is illustrated on two well-known client dynamic analyses and is supported by an infrastructure to explore the approach

Web macros automate interactions with Web sites and related information systems. Though Web macro recorders and players have grown in sophistication over the past decade, these tools cannot yet meet many needs of users in daily life. Based on observations of browser users, we have compiled ten scenarios describing tasks that users would benefit from automating. Our analysis of these scenarios yields specific requirements that Web macro tools should support if those tools are to be applicable to these real-life tasks. Our set of requirements constitutes a benchmark for evaluating tools.

Web authoring environments enable end-users to create applications that integrate information from other web sources. Users can create web sites that include built-in components to dynamically incorporate, for example, weather information, stock-quotes, or the latest news from different web sources. Recent surveys conducted among end-users have indicated an increasing interest in creating such applications. Unfortunately, web authoring environments do not provide support beyond a limited set of built-in components. This work addresses this limitation by providing end-user support for "clipping" information from a target web site to incorporate it into the end-user site. The support consists of a mechanism to identify the target clipping with multiple markers to increase robustness, and a dynamic assessment of the retrieved information to quantify its reliability. The clipping approach has been integrated as a feature into a popular web authoring tool on which we present the results of two preliminary studies.

Software engineering researchers are increasingly relying on the empirical approach to advance the state of the art. The level of empirical rigor and evidence required to guide software engineering research, however, can vary drastically depending on many factors. In this session we identify some of these factors through a discussion of the state of the art in performing empirical studies in software engineering, and we show how we can utilize the notion of empirical maturity to set and adjust the empirical expectations for software engineering research efforts.Regarding the state of the art in performing empirical studies, we will offer perspectives on two classes of study: those concerned with humans utilizing a technology, e.g., a person applying a methodology, a technique, or a tool, where human skills and the ability to interact with the technology are some of the primes issues, and those concerned with the application of the technology to an artifact, e.g., a technique or tool applied to a design or a program. In the first case, the emphasis is typically on issues like feasibility, usefulness, and then on effectiveness. The technology tends to be less well specified and based more on the experience and skills of the technology applier. In the second case, the emphasis is typically on the efficiency and effectiveness of the technology. The technology tends to be well defined and the assumption is that the individual skill and experience plays a less important role. We will discuss the set of factors that influence the design, implementation, and validity of these studies.Regarding empirical maturity and its implications on the SE community's expectations, we will provide examples of the large spectrum of studies with different maturity levels that can be performed to successfully support software engineering research. We will then identify and analyze the following aspects that are likely to impact a study's maturity level: technology (well-specified vs. under development), goals of the study (effectiveness vs. feasibility), type of design and analysis (controlled experiment vs. case study, quantitative vs. qualitative), control and specification of threats to validity (internal vs. external threats), dependence on context (in vivo vs. in vitro), relationship to previous empirical work (replicated on-site, replicated off-site, non-replicated, non-replicable), and purposes of the study (exploratory vs. confirmatory). We will lead a discussion on these key aspects that must be considered to assess the empirical maturity of a piece of work in the context of its research area and the empirical maturity of that area.

Profiling deployed software provides valuable insights for quality improvement activities. The probes required for profiling, however, can cause an unacceptable performance overhead for users. In previous work we have shown that significant overhead reduction can be achieved, with limited information loss, through the distribution of probes across deployed instances. However, existing techniques for probe distribution are designed to profile simple events. In this paper we present a set of techniques for probe distribution to enable the profiling of complex events that require multiple probes and that share probes with other events. Our evaluation of the new techniques indicates that, for tight overhead bounds, techniques that produce a balanced event allocation can retain significantly more field information

Program analysis techniques are used by software engineers to deduce and infer characteristics of software systems. Recent research has suggested that a new form of program analysis technique can be created by incorporating characteristics of experimentation into analyses. This paper reports the results of research exploring this suggestion. Building on principles and methodologies underlying the use of experimentation in other fields, we provide descriptive and operational definitions of experimental program analysis, illustrate them by example, and describe several differences between experimental program analysis and experimentation in other fields. We show how the use of an experimental program analysis paradigm can help researchers identify limitations of analysis techniques, improve existing experimental program analysis techniques, and create new experimental program analysis techniques.

Recent advances in static program analysis have made it possible to detect errors in applications that have been thoroughly tested and are in wide-spread use. The ability to find errors that have eluded traditional validation methods is due to the development and combination of sophisticated algorithmic techniques that are embedded in the implementations of analysis tools. Evaluating new analysis techniques is typically performed by running an analysis tool on a collection of subject programs, perhaps enabling and disabling a given technique in different runs. While seemingly sensible, this approach runs the risk of attributing improvements in the cost-effectiveness of the analysis to the technique under consideration, when those improvements may actually be due to details of analysis tool implementations that are uncontrolled during evaluation.In this paper, we focus on the specific class of path-sensitive error detection techniques and identify several factors that can significantly influence the cost of analysis. We show, through careful empirical studies, that the influence of these factors is sufficiently large that, if left uncontrolled, they may lead researchers to improperly attribute improvements in analysis cost and effectiveness. We make several recommendations as to how the influence of these factors can be mitigated when evaluating techniques.

Unit test cases are focused and efficient. System tests are effective at exercising complex usage patterns. Differential unit tests (DUT) are a hybrid of unit and system tests. They are generated by carving the system components, while executing a system test case, that influence the behavior of the target unit, and then re-assembling those components so that the unit can be exercised as it was by the system test. We conjecture that DUTs retain some of the advantages of unit tests, can be automatically and inexpensively generated, and have the potential for revealing faults related to intricate system executions. In this paper we present a framework for automatically carving and replaying DUTs that accounts for a wide-variety of strategies, we implement an instance of the framework with several techniques to mitigate test cost and enhance flexibility, and we empirically assess the efficacy of carving and replaying DUTs.

Abstract Testers use coverage data for test suite quality assessment, stopping criteria definition, and effort allocation. However, as the complexity of products and testing processes increases, the cost of coverage data collection may grow significantly, jeopardizing its potential application. To mitigate this problem this paper presents the concept of ‘disposable coverage instrumentation’—coverage instrumentation that is removed after its execution—through two techniques: local disposal, and collective disposal. A Java virtual machine was extended to support these techniques, and their potential is shown through two studies utilizing the Specjvm98 and Specjbb2000 benchmarks. The results indicate that the techniques can reduce coverage collection overhead by an order of magnitude over state‐of‐the‐art techniques. Copyright © 2006 John Wiley & Sons, Ltd.

WEUSE is a workshop dedicated to the problems faced by end-user programmers, and research that can address those problems.

End-user programmers are increasingly relying on Web authoring environments to create Web applications. Although often consisting primarily of Web pages, such applications are increasingly going further, harnessing the content available on the Web through "programs" that query other Web applications for information to drive other tasks. Unfortunately, errors can be pervasive in Web applications, impacting their dependability. This paper reports the results of an exploratory study of end-user Web application developers, performed with the aim of exposing prevalent classes of errors. The results suggest that end-users struggle the most with the identification and manipulation of variables when structuring requests to obtain data from other Web sites. To address this problem, we present a family of techniques that help end user programmers perform this task, reducing possible sources of error. The techniques focus on simplification and characterization of the data that end-users must analyze while developing their Web applications. We report the results of an empirical study in which these techniques are applied to several popular Web sites. Our results reveal several potential benefits for end-users who wish to "engineer" dependable Web applications.

An understanding of how software is employed in the field can yield many opportunities for quality improvements. Profiling released software can provide such an understanding. However, profiling released software is difficult due to the potentially large number of deployed sites that must be profiled, the transparency requirements at a user's site, and the remote data collection and deployment management process. Researchers have recently proposed various approaches to tap into the opportunities offered by profiling deployed systems and overcome those challenges. Initial studies have illustrated the application of these approaches and have shown their feasibility. Still, the proposed approaches, and the tradeoffs between overhead, accuracy, and potential benefits for the testing activity have been barely quantified. This paper aims to overcome those limitations. Our analysis of 1,200 user sessions on a 155 KLOC deployed system substantiates the ability of field data to support test suite improvements, assesses the efficiency of profiling techniques for released software, and the effectiveness of testing efforts that leverage profiled field data.

Web applications are vital components of the global information infrastructure, and it is important to ensure their dependability. Many techniques and tools for validating Web applications have been created, but few of these have addressed the need to test Web application functionality and none have attempted to leverage data gathered in the operation of Web applications to assist with testing. In this paper, we present several techniques for using user session data gathered as users operate Web applications to help test those applications from a functional standpoint. We report results of an experiment comparing these new techniques to existing white-box techniques for creating test cases for Web applications, assessing both the adequacy of the generated test cases and their ability to detect faults on a point-of-sale Web application. Our results show that user session data can be used to produce test suites more effective overall than those produced by the white-box techniques considered; however, the faults detected by the two classes of techniques differ, suggesting that the techniques are complementary.

Testers use coverage data for test suite quality assessment, stopping criteria definition, and effort allocation. However, as the complexity of products and testing processes increases, the cost of coverage data collection may grow significantly, jeopardizing its potential application. We present two techniques to mitigate this problem based on the concept of "disposable coverage instrumentation": coverage instrumentation that is removed after its usage. The idea is to reduce coverage collection overhead by removing instrumentation probes after they have been executed. We have extended a Java virtual machine to support these techniques, and show their potential through empirical studies with the Specjvm98 and Specjbb2000 benchmarks. The results indicate that the techniques can reduce coverage collection overhead between 18% and 97% over existing techniques.

An understanding of how software is employed in the field can yield many opportunities for quality improvements. Profiling released software can provide such an understanding. However, profiling released software is diffcult due to the potentially large number of deployed sites that must be profiled, the extreme transparency expectations, and the remote data collection and deployment management process. Researchers have recently proposed various approaches to tap into the opportunities and overcome those challenges. Initial studies have illustrated the application of these approaches and have shown their feasibility. Still, the promising proposed approaches, and the tradeoffs between overhead, accuracy, and potential benefits for the testing activity have been barely quantified. This paper aims to over-come those limitations. Our analysis of 1200 user sessions on a 155 KLOC system substantiates the ability of field data to support test suite improvements, quantifies different approaches previously introduced in isolation, and assesses the efficiency of profiling techniques for released software and the effectiveness of their associated testing efforts.

Regression testing is an expensive testing process used to revalidate software as it evolves. Various methodologies for improving regression testing processes have been explored, but the cost-effectiveness of these methodologies has been shown to vary with characteristics of regression test suites. One such characteristic involves the way in which test inputs are composed into test cases within a test suite. This article reports the results of controlled experiments examining the effects of two factors in test suite composition---test suite granularity and test input grouping---on the costs and benefits of several regression-testing-related methodologies: retest-all, regression test selection, test suite reduction, and test case prioritization. These experiments consider the application of several specific techniques, from each of these methodologies, across ten releases each of two substantial software systems, using seven levels of test suite granularity and two types of test input grouping. The effects of granularity, technique, and grouping on the cost and fault-detection effectiveness of regression testing under the given methodologies are analyzed. This analysis shows that test suite granularity significantly affects several cost-benefit factors for the methodologies considered, while test input grouping has limited effects. Further, the results expose essential tradeoffs affecting the relationship between test suite design and regression testing cost-effectiveness, with several implications for practice.

Web applications have become critical components of the global information infrastructure, and it is important that they be validated to ensure their reliability. Therefore, many techniques and tools for validating web applications have been created. Only a few of these techniques, however, have addressed problems of testing the functionality of web applications, and those that do have not fully considered the unique attributes of web applications. In this paper we explore the notion that user session data gathered as users operate web applications can be successfully employed in the testing of those applications, particularly as those applications evolve and experience different usage profiles. We report results of an experiment comparing new and existing test generation techniques for web applications, assessing both the adequacy of the generated tests and their ability to detect faults on a point-of-sale web application. Our results show that user session data can produce test suites as effective overall as those produced by existing white-box techniques, but at less expense. Moreover the classes of faults detected differ somewhat across approaches, suggesting that the techniques may be complimentary.

Reproducing and learning from failures in deployed software is costly and difficult. Those activities can be facilitated, however, if the circumstances leading to a failure are properly captured. In this paper, we empirically investigate how various anomaly detection schemes can serve to identify the conditions that precede failures in deployed software. Our results expose the tradeoffs between different detection algorithms applied to several types of events under varying levels of in-house testing.

Abstract Regression testing is an expensive testing process used to validate modified software. Regression test selection and test‐case prioritization can reduce the costs of regression testing by selecting a subset of test cases for execution, or scheduling test cases to meet testing objectives better. The cost‐effectiveness of these techniques can vary widely, however, and one cause of this variance is the type and magnitude of changes made in producing a new software version. Engineers unaware of the causes and effects of this variance can make poor choices in designing change integration processes, selecting inappropriate regression testing techniques, designing excessively expensive regression test suites and making unnecessarily costly changes. Engineers aware of causal factors can perform regression testing more cost‐effectively. This article reports the results of an embedded multiple case study investigating the modifications made in the evolution of four software systems and their impact on regression testing techniques. The results of this study expose tradeoffs and constraints that affect the success of techniques and provide guidelines for designing and managing regression testing processes. Copyright © 2003 John Wiley & Sons, Ltd.

Regression testing is an expensive testing process used to validate software following modifications. The cost-effectiveness of regression testing techniques varies with characteristics of test suites. One such characteristic, test suite granularity, involves the way in which test inputs are grouped into test cases within a test suite. Various cost-benefits tradeoffs have been attributed to choices of test suite granularity, but almost no research has formally examined these tradeoffs. To address this lack, we conducted several controlled experiments, examining the effects of test suite granularity on the costs and benefits of several regression testing methodologies across six releases of two non-trivial software systems. Our results expose essential tradeoffs to consider when designing test suites for use in regression testing evolving systems.

Regression testing is an expensive activity that can account for a large proportion of the software maintenance budget. Because engineers add tests into test suites as software evolves, over time, increased test suite size makes revalidation of the software more expensive. Regression test selection, test suite reduction, and test case prioritization techniques can help with this, by reducing the number of regression tests that must be run and by helping testers meet testing objectives more quickly. These techniques, however can be expensive to employ and may not reduce overall regression testing costs. Thus, practitioners and researchers could benefit from cost models that would help them assess the cost-benefits of techniques. Cost models have been proposed for this purpose, but some of these models omit important factors, and others cannot truly evaluate cost-effectiveness. In this paper, we present new cost-benefits models for regression test selection, test suite reduction, and test case prioritization, that capture previously omitted factors, and support cost-benefits analyses where they were not supported before. We present the results of an empirical study assessing these models.

Tracing is a dynamic analysis technique to continuously capture events of interest on a running program. The occurrence of a statement, the invocation of a function, and the trigger of a signal are examples of traced events. Software engineers employ traces to accomplish various tasks, ranging from performance monitoring to failure analysis. Despite its capabilities, tracing can negatively impact the performance and general behavior of an application. In order to minimize that impact, traces are normally buffered and transferred to (slower) permanent storage at specific intervals. This scenario presents a delicate balance. Increased buffering can minimize the impact on the target program, but it increases the risk of losing valuable collected data in the event of a failure. Frequent disk transfers can ensure traced data integrity, but it risks a high impact on the target program. We conducted an experiment involving six tracing schemes and various buffer sizes to address these trade-offs. Our results highlight opportunities for tailored tracing schemes that would benefit failure analysis.

Abstract Code‐coverage‐based test data adequacy criteria typically treat all coverable code elements (such as statements, basic blocks or outcomes of decisions) as equal. In practice, however, the probability that a test case can expose a fault in a code element varies: some faults are more easily revealed than others. Thus, several researchers have suggested that if one could estimate the probability that a fault in a code element will cause a failure, one could use this estimate to determine the number of executions of a code element that are required to achieve a certain level of confidence in that element's correctness. This estimate, in turn, could be used to improve the fault‐detection effectiveness of test suites and help testers distribute testing resources more effectively. This conjecture is intriguing; however, like many such conjectures it has never been directly examined empirically. If empirical evidence were to support this conjecture, it would motivate further research into methodologies for obtaining fault‐exposure‐potential estimates and incorporating them into test data adequacy criteria. This paper reports the results of experiments conducted to investigate the effects of incorporating an estimate of fault‐exposure probability into the statement coverage test data adequacy criterion. The results of these experiments, however, ran contrary to the conjectures of previous researchers. Although incorporation of the estimates did produce statistically significant increases in the fault‐detection effectiveness of test suites, these increases were quite small, suggesting that the approach might not be able to produce the gains hoped for and might not be worth the cost of its employment. Copyright © 2002 John Wiley & Sons, Ltd.

To reduce the cost of regression testing, software testers may prioritize their test cases so that those which are more important, by some measure, are run earlier in the regression testing process. One potential goal of such prioritization is to increase a test suite's rate of fault detection. Previous work reported results of studies that showed that prioritization techniques can significantly improve rate of fault detection. Those studies, however, raised several additional questions: 1) Can prioritization techniques be effective when targeted at specific modified versions; 2) what trade-offs exist between fine granularity and coarse granularity prioritization techniques; 3) can the incorporation of measures of fault proneness into prioritization techniques improve their effectiveness? To address these questions, we have performed several new studies in which we empirically compared prioritization techniques using both controlled experiments and case studies.

Test case prioritization techniques schedule test cases for regression testing in an order that increases their ability to meet some performance goal. One performance goal, rate of fault detection, measures how quickly faults are detected within the testing process. In previous work (S. Elbaum et al., 2000; G. Rothermel et al., 1999), we provided a metric, APFD, for measuring rate of fault detection, and techniques for prioritizing test cases to improve APFD, and reported the results of experiments using those techniques. This metric and these techniques, however, applied only in cases in which test costs and fault severity are uniform. We present a new metric for assessing the rate of fault detection of prioritized test cases that incorporates varying test case and fault costs. We present the results of a case study illustrating the application of the metric. This study raises several practical questions that might arise in applying test case prioritization; we discuss how practitioners could go about answering these questions.

Many tools and techniques for addressing software maintenance problems rely on code coverage information. Often, this coverage information is gathered for a specific version of a software system, and then used to perform analyses on subsequent versions of that system without being recalculated. As a software system evolves, however, modifications to the software alter the software's behavior on particular inputs, and code coverage information gathered on earlier versions of a program may not accurately reflect the coverage that would be obtained on later versions. This discrepancy may affect the success of analyses dependent on code coverage information. Despite the importance of coverage information in various analyses, in our search of the literature we find no studies specifically examining the impact of software evolution on code coverage information. Therefore, we conducted empirical studies to examine this impact. The results of our studies suggest that even relatively small modifications can greatly affect code coverage information, and that the degree of impact of change on coverage may be difficult to predict.

Learning from software failures is an essential step towards the development of more reliable software systems and processes. However, as more intricate software systems are developed, determining the nature and causes of a software failure becomes a great challenge. Although many existing techniques can help in understanding the nature of the failure, they are limited in some of the following aspects. First, they work only within controlled environments. Second, they have a major impact on the target system behavior. Third, they assume that a failure can be reproduced. Fourth, they lack enough support to carry out a structured failure analysis. The authors present the Software Black Box (SBB) as an alternative mechanism for failure investigation. The SBB is different from its predecessors in that it was specifically designed to be embedded in a target system and assist in the investigation of failures by reconstructing the events that lead to the failure. The SBB architecture is discussed, and a set of failure scenarios that reveal the SBB potential in assisting failure investigation is presented.

Test case prioritization techniques schedule test cases in an order that increases their effectiveness in meeting some performance goal. One performance goal, rate of fault detection, is a measure of how quickly faults are detected within the testing process; an improved rate of fault detection can provide faster feedback on the system under test, and let software engineers begin locating and correcting faults earlier than might otherwise be possible. In previous work, we reported the results of studies that showed that prioritization techniques can significantly improve rate of fault detection. Those studies, however, raised several additional questions: (1) can prioritization techniques be effective when aimed at specific modified versions; (2) what tradeoffs exist between fine granularity and coarse granularity prioritization techniques; (3) can the incorporation of measures of fault proneness into prioritization techniques improve their effectiveness? This paper reports the results of new experiments addressing these questions.

The test process for evolving software systems takes on a different measurement aspect than that of new systems. Existing systems are generally being modified on a continuing basis as a normal part of the software maintenance activity. This process of product modifications is fault prone because faults are introduced in the code as it is being modified. From a statistical perspective, regression testing should be focused on those areas that are most likely to contain the introduced faults. Based on that premise, we have developed an evolutionary fault index that works as a fault surrogate varying in the same manner as faults. However, the knowledge as to the location of probable faults is not enough to assess the capabilities of a regression test suite. It is necessary to understand what the software is doing under each test. For that purpose, test execution profiles are gathered. Test execution profiles and the evolutionary fault indexes are combined in one methodology to provide an assessment of the overall regression testing activity and the suitability of each individual test. The methodology is illustrated with data from a 300 KLOC embedded system and its corresponding regression test suite. Copyright © 2000 John Wiley & Sons, Ltd..

This study presents a methodology that will produce a viable fault surrogate. The focus of the effort is on the precise measurement of software development process and product outcomes. Tools and processes for the static measurement of the source code have been installed and made operational in a large embedded software system. Source code measurements have been gathered unobtrusively for each build in the software evolution process. The measurements are synthesized to obtain the fault surrogate. The complexity of sequential builds is compared and a new measure, code churn, is calculated. This paper demonstrates the effectiveness of code complexity churn by validating it against the testing problem reports.