Metamorphic and differential testing have been proposed as best practices for testing software that is difficult to test, such as for programs in scientific domains. An assumption is that these approaches can be easily customized and applied to almost any domain. However, scientific software is often data-driven, and metamorphic relations may require significant domain knowledge to develop. In addition, tools are often written for ad-hoc experimentation by the scientists and often embed many assumptions about the importance and representation of different natural phenomena. In this paper, we present our experience applying both metamorphic and differential testing to a set of four computational biology tools that predict the growth of an organism. While our original goal was to evaluate these techniques to improve our system-level testing, we encountered multiple roadblocks along the way. Although we did find faults (some confirmed by developers), we also uncovered a set of challenges, including the considerable manual effort required for (a) defining domain-specific tests, (b) validating correctness, and (c) distinguishing between issues stemming from poor data and those arising from incorrect software.

Small uncrewed aerial systems (sUAS) provide an invaluable resource for performing a variety of surveillance, search, and delivery tasks in remote or hostile terrains which may not be accessible by other means. Due to the critical role sUAS play in these situations, it is vital that they are well configured in order to ensure a safe and stable flight. However, it is not uncommon for mistakes to occur in configuration and calibration, leading to failures or incomplete missions. To address this problem, we propose a set of self-adaptive mechanisms and implement them into a self-adaptive framework, Controller Instability-preventing Configuration-Aware Drone Adaptation (CICADA). CICADA dynamically detects unstable drone behavior during flight and adapts to mitigate this threat. We have built a prototype of CICADA using a popular open source sUAS flight control software and experimented with a large number of different configurations in simulation. We then performed a case study with physical drones to determine if our framework will work in practice. Experimental results show that CICADA ’s adaptations reduce controller instability and enable the sUAS to recover from up to 33.8% of poor configurations. In cases where we cannot complete the intended mission, invoking alternative adaptations may still help by allowing the vehicle to loiter or land safely in place, avoiding potentially catastrophic crashes. These safety-focused adaptations can mitigate unsafe behavior in 52.9% to 64.7% of dangerous configurations. We further show that rule-based approaches can be leveraged to automatically select an appropriate adaptation strategy based on the severity of instability encountered, with up to a 14.2% improvement over direct adaptation. Finally, we introduce a variation of our primary adaptation strategy designed to allow more cautious adaptation with limited configuration information, which gets within 6.7% of our primary adaptation strategy despite not requiring an optimal knowledge base.

Small Unmanned Aerial Systems (sUAS) must meet rigorous safety standards when deployed in high-stress emergency response scenarios; however many reported accidents have involved humans in the loop. In this paper, we, therefore, present the HiFuzz testing framework, which uses fuzz testing to identify system vulnerabilities associated with human interactions. HiFuzz includes three distinct levels that progress from a low-cost, limited-fidelity, large-scale, no-hazard environment, using fully simulated Proxy Human Agents, via an intermediate level, where proxy humans are replaced with real humans, to a high-stakes, high-cost, real-world environment. Through applying HiFuzz to an autonomous multi-sUAS system-under-test, we show that each test level serves a unique purpose in revealing vulnerabilities and making the system more robust with respect to human mistakes. While HiFuzz is designed for testing sUAS systems, we further discuss its potential for use in other Cyber-Physical Systems.

ARA is an at-scale Platform for Advanced Wireless Research (PAWR), specifically tailored to the unique community, application, and economic context of rural regions. It features the first-of-its-kind real-world implementation of long-distance, high-capacity wireless backhaul and access systems spanning over 30 km in diameter. Leveraging both software-defined radios and programmable Commercial Off-The-Shelf (COTS) systems, ARA orchestrates the wireless resources alongside the networking and compute resources for enabling end-to-end experiments involving user equipment, base stations, edge computing, and cloud infrastructure. Such an integration facilitates the coevolution of rural-focused wireless innovation and applications, while helping to advance the frontiers of advanced Next-G wireless systems such as Open RAN. As of summer 2024, ARA is publicly accessible with 7 base stations (BSes) and over 30 user equipment (UEs). In this demo, we share advanced wireless research experiments enabled by ARA, involving MU-MIMO in TV White Space (TVWS) bands, long-range mmWave and microwave backhaul communications, and open-source 5G NR protocol stacks such as srsRAN and OpenAirInterface (OAI).

Fault localization is essential to software maintenance tasks such as testing and automated program repair. Many fault localization techniques have been developed, the most common of which are spectrum-based. Most techniques have been designed for traditional programming paradigms that map passing and failing test cases to lines or branches of code, hence specialized programming paradigms which utilize different code abstractions may fail to localize well. In this paper, we study fault localization in the context of a class of programs, molecular programs. Recent research has designed automated testing and repair frameworks for these pro- grams but has ignored the importance of fault localization. As we demonstrate, using existing spectrum-based approaches may not provide much information. Instead we propose a novel approach, Traceback, that leverages temporal trace data. In an empirical study on a set of 89 faulty program variants, we demonstrate that Trace- back provides between a 32-90% improvement in localization over reaction-based mapping, a direct translation of spectrum-based localization. We see little difference in parameter tuning of Trace- back when all tests, or only code-based (invariant) tests are used, however the best depth and weight parameters vary when using specification based tests, which can be either functional or meta- morphic. Overall, invariant-based tests provide the best localization results (either alone or in combination with others), followed by metamorphic and then functional tests.

Configurability is a common property of software allowing programs to be customized for the user. While configurability is pervasive, it can also lead to faults (or misconfigurations) and make program evolution challenging. Dependencies can be missed, essential code can be left in place when a configuration option is removed, or code can be deleted or changed when still in use by other configuration options. A key issue is a lack of sufficient documentation and traceability between configuration options and code during software evolution. Existing approaches to solve these problems include automated documentation, analysis of version control history, or the use of special program configuration management languages. However, none of these provide a sufficient solution managing configuration changes over time. In this paper we propose our vision for an automated approach called ConfiGen, which provides user-facing documentation along with a back-end analysis showing definitions and uses of configuration options along with traceability to lines of program code for evolution. We performed a case study demonstrating its potential usefulness.

Constructing assurance cases is a widely used and sometimes required process toward demonstrating that safety-critical systems will operate safely in their planned environment. To mitigate the risk of errors and missing edge cases, the concept of defeaters - challenges to claims in an assurance case - has been introduced. Defeaters can detect weaknesses in the arguments, prompting further investigation and timely mitigations. However, capturing defeaters relies on expert judgment, experience, and creativity and must be done iteratively due to evolving requirements and regulations. In this paper, we propose CoDefeater, an automated process to leverage large language models (LLMs) for finding defeaters. Initial results on two systems show that LLMs can efficiently find known and unforeseen feasible defeaters to support safety analysts in enhancing the completeness and confidence of assurance cases.

The unintentional flow of confidential data to unauthorised users is a serious software security vulnerability. Detection and repair of such errors is a non-trivial task that has been worked on by the security community for many years. More recently, dynamic approaches, such as HyperGI, have been introduced that use hypertesting and genetic improvement to not only detect, but also provide a patch that reduces such information flow control violations. However, empirical studies performed so far have used mostly generic mutation operators, potentially limiting the strength of this approach. In this new ideas paper we mine the National Vulnerabilities Database to find repairs of information leaks. Of 636 issues initially identified, we found 73 fixes that relate to information leaks and come with open source patches to the code. From these, we identified 10 types of mutation operators with potential to fix such issues. Six of these have so far never been used to fix information leaks via automated mutation to the code. We propose that these could help improve effectiveness of tools using the HyperGI approach.

As the Platform for Advanced Wireless Research (PAWR) in rural broadband, the ARA wireless living lab features the deployment of first-of-its-kind wireless access and backhaul platforms in real-world agriculture and rural settings, and preliminary experiments have demonstrated very promising results, e.g., up to 3.2 Gbps wireless access throughput and more than 10 Gbps throughput across a wireless backhaul link of over 10 km. ARA is expected to be publicly released for broad community use starting in September 2023. Through this demo, we plan to share, for the first time, with the wireless research community the transformative research experiments enabled by ARA. To stimulate discussion and community participation, we will demonstrate a few example experiments ranging from MU-MIMO in TV White Space (TVWS) bands to long-range mmWave and microwave backhaul communications, as well as open-source 5G NR protocol stacks such as srsRAN and OpenAirInterface.

Small uncrewed aerial systems, sUAS, provide an invaluable resource for performing a variety of surveillance, search, and delivery tasks in remote or hostile terrains which may not be accessible by other means. Due to the critical role sUAS play in these situations, it is vital that they are well configured in order to ensure a safe and stable flight. However, it is not uncommon for mistakes to occur in configuration and calibration, leading to failures or incomplete missions. To address this problem, we propose a set of self-adaptive mechanisms and implement them into a self-adaptive framework, CICADA, for Controller Instability-preventing Configuration Aware Drone Adaptation. CICADA dynamically detects unstable drone behavior during flight and adapts to mitigate this threat. We have built a prototype of CICADA using a popular open source sUAS simulator and experimented with a large number of different configurations. Experimental results show that CICADA’s adaptations reduce controller instability and enable the sUAS to recover from a significant number of poor configurations. In cases where we cannot complete the intended mission, invoking alternative adaptations may still help by allowing the vehicle to loiter or land safely in place, avoiding potentially catastrophic crashes.

Chemical reaction networks (CRNs) are an emerging distributed computational paradigm where programs are encoded as a set of abstract chemical reactions. CRNs can be compiled into DNA strands which perform the computations in vitro, creating a foundation for intelligent nanodevices. Recent research proposed a software testing framework for stochastic CRN programs in simulation, however, it relies on existing program specifications. In practice, specifications are often lacking and when they do exist, transforming them into test cases is time-intensive and can be error prone. In this work, we propose an inference technique called ChemFlow which extracts 3 types of invariants from an existing CRN model. The extracted invariants can then be used for test generation or model validation against program implementations. We applied ChemFlow to 13 CRN programs ranging from toy examples to real biological models with hundreds of reactions. We find that the invariants provide strong fault detection and often exhibit less flakiness than specification derived tests. In the biological models we showed invariants to developers and they confirmed that some of these point to parts of the model that are biologically incorrect or incomplete suggesting we may be able to use ChemFlow to improve model quality.

Information leaks in software can unintentionally reveal private data, yet they are hard to detect and fix. Although several methods have been proposed to detect leakage, such as static verification-based approaches, they require specialist knowledge, and are time-consuming. Recently, we introduced HyperGI, a dynamic, hypertest-based approach that can detect and produce potential fixes for hyperproperty violations. In particular, we focused on violations of the noninterference property, as it results in information flow leakage. Our instantiation of HyperGI was able to detect and reduce leakage in three small programs. Its fitness function tried to balance information leakage and program correctness but, as we pointed out, there may be tradeoffs between keeping program semantics and reducing information leakage that require developer decisions.

Configurable software makes up most of the software in use today. Configurability, i.e., the ability of software to be customized without additional programming, is pervasive, and due to the criticality of problems caused by misconfiguration, it has been an active topic researched by investigators in multiple, diverse areas. This broad reach of configurability means that much of the literature and latest results are dispersed, and researchers may not be collaborating or be aware of similar problems and solutions in other domains. We argue that this lack of a common ground leads to a missed opportunity for synergy between research domains and the synthesis of efforts to tackle configurability problems. In short, configurability cuts across software as a whole and needs to be treated as a first class programming element. To provide a foundation for addressing these concerns we make suggestions on how to bring the communities together and propose a common model of configurability and a platform, ACCORD, to facilitate collaboration among researchers and practitioners.

Maintaining confidential information control in soft-ware is a persistent security problem where failure means secrets can be revealed via program behaviors. Information flow control techniques traditionally have been based on static or symbolic analyses — limited in scalability and specialized to particular languages. When programs do leak secrets there are no approaches to automatically repair them unless the leak causes a functional test to fail. We present our vision for HyperGI, a genetic improvement framework that detects, localizes and repairs information leakage. Key elements of HyperGI include (1) the use of two orthogonal test suites, (2) a dynamic leak detection approach which estimates and localizes potential leaks, and (3) a repair component that produces a candidate patch using genetic improvement. We demonstrate the successful use of HyperGI on several programs with no failing functional test cases. We manually examine the resulting patches and identify trade-offs and future directions for fully realizing our vision.

Abstract Software product line engineering is a best practice for managing reuse in families of software systems that is increasingly being applied to novel and emerging domains. In this work we investigate the use of software product line engineering in one of these new domains, synthetic biology. In synthetic biology living organisms are programmed to perform new functions or improve existing functions. These programs are designed and constructed using small building blocks made out of DNA. We conjecture that there are families of products that consist of common and variable DNA parts, and we can leverage product line engineering to help synthetic biologists build, evolve, and reuse DNA parts. In this paper we perform an investigation of domain engineering that leverages an open-source repository of more than 45,000 reusable DNA parts. We show the feasibility of these new types of product line models by identifying features and related artifacts in up to 93.5% of products, and that there is indeed both commonality and variability. We then construct feature models for four commonly engineered functions leading to product lines ranging from 10 to 7.5 × 1020 products. In a case study we demonstrate how we can use the feature models to help guide new experimentation in aspects of application engineering. Finally, in an empirical study we demonstrate the effectiveness and efficiency of automated reverse engineering on both complete and incomplete sets of products. In the process of these studies, we highlight key challenges and uncovered limitations of existing SPL techniques and tools which provide a roadmap for making SPL engineering applicable to new and emerging domains.

The IEEE 12th International Conference on Software Testing, Verification & Validation (ICST 2019) was held in Xi'an, China. The aim of the ICST conference is to bring together researchers and practitioners who study the theory, techniques, technologies, and applications that concern all aspects of software testing, verification, and validation of software systems. The program committee rigorously reviewed 110 full papers using a double-blind reviewing policy. Each paper received at least three regular reviews and went through a discussion phase where the reviewers made final decisions on each paper, each discussion being led by a meta-reviewer. Out of this process, the committee selected 31 full-length papers that appeared in the conference. These were presented over nine sessions ranging from classical topics such as test generation and test coverage to emerging topics such as machine learning and security during the main conference track. Based on the original reviewers' feedback, we selected five papers for consideration for this special issue of STVR. These papers were extended from their conference version by the authors and were reviewed according to the standard STVR reviewing process. We thank all the ICST and STVR reviewers for their hard work. Three papers successfully completed the review process and are contained in this special issue. The rest of this editorial provides a brief overview of these three papers. The first paper, Automated Visual Classification of DOM-based Presentation Failure Reports for Responsive Web Pages, by Ibrahim Althomali, Gregory Kapfhammer, and Phil McMinn, introduces VERVE, a tool that automatically classifies all hard to detect response layout failures (RLFs) in web applications. An empirical study reveals that VERVE's classification of all five types of RLFs frequently agrees with classifications produced manually by humans. The second paper, BugsJS: A Benchmark and Taxonomy of JavaScript Bugs, by Péter Gyimesi, Béla Vancsics, Andrea Stocco, Davood Mazinanian, Árpád Beszédes, Rudolf Ferenc, and Ali Mesbah, presents, BugsJS, a benchmark of 453 real, manually validated JavaScript bugs from 10 popular JavaScript server-side programs, comprising 444 k LOC in total. Each bug is accompanied by its bug report, the test cases that expose it, as well as the patch that fixes it. BugJS can help facilitate reproducible empirical studies and comparisons of JavaScript analysis and testing tools. The third paper, Statically Driven Generation of Concurrent Tests for Thread-Safe Classes, by Valerio Terragni and Mauro Pezzè presents DEPCON+, a novel approach that reduces the search space of concurrent tests by leveraging statically computed dependencies among public methods. DEPCON+ exploits the intuition that concurrent tests can expose thread-safety violations that manifest exceptions or deadlocks, only if they exercise some specific method dependencies. The results show that DEPCON+ is more effective than state-of-the-art approaches in exposing concurrency faults.

In recent years the use of non-traditional computing mechanisms has grown rapidly. One paradigm uses chemical reaction networks (CRNs) to compute via chemical interactions. CRNs are used to prototype molecular devices at the nanoscale such as intelligent drug therapeutics. In practice, these programs are first written and simulated in environments such as MatLab and later compiled into physical molecules such as DNA strands. However, techniques for testing the correctness of CRNs are lacking. Current methods of validating CRNs include model checking and theorem proving, but these are limited in scalability. In this paper we present the first (to the best of our knowledge) testing framework for CRNs, ChemTest. ChemTest evaluates test oracles on individual simulation traces and supports functional, metamorphic, internal and hyper test cases. It also allows for flakiness and programs that are probabilistic. We performed a large case study demonstrating that ChemTest can find seeded faults and scales beyond model checking. Of our tests, 21% are inherently flaky, suggesting that systematic support for this paradigm is needed. On average, functional tests find 66.5% of the faults, while metamorphic tests find 80.4%, showing the benefit of using metamorphic relationships in our test framework. In addition, we show how the time at evaluation impacts fault detection.

The bioinformatics software domain contains thousands of applications for automating tasks such as the pairwise alignment of DNA sequences, building and reasoning about metabolic models or simulating growth of an organism. Its end users range from sophisticated developers to those with little computational experience. In response to their needs, developers provide many options to customize the way their algorithms are tuned. Yet there is little or no automated help for the user in determining the consequences or impact of the options they choose. In this paper we describe our experience working with configurable bioinformatics tools. We find limited documentation and help for combining and selecting options along with variation in both functionality and performance. We also find previously undetected faults. We summarize our findings with a set of lessons learned, and present a roadmap for creating automated techniques to interact with bioinformatics software. We believe these will generalize to other types of scientific software.

Formal methods use mathematical notations and logical reasoning to precisely define a program's specifications, from which we can instantiate valid instances of a system. With these techniques we can perform a multitude of tasks to check system dependability. Despite the existence of many automated tools including ones considered lightweight, they still lack a strong adoption in practice. At the crux of this problem, is scalability and applicability to large real world applications. In this paper we show how to relax the completeness guarantee without much loss, since soundness is maintained. We have extended a popular lightweight analysis, Alloy, with a genetic algorithm. Our new tool, EvoAlloy, works at the level of finite relations generated by Kodkod and evolves the chromosomes based on the failed constraints. In a feasibility study we demonstrate that we can find solutions to a set of specifications beyond the scope where traditional Alloy fails. While small specifications take longer with EvoAlloy, the scalability means we can handle larger specifications. Our future vision is that when specifications are small we can maintain both soundness and completeness, but when this fails, EvoAlloy can switch to its genetic algorithm.

Safety-critical applications often use dependability cases to validate that specified properties are invariant, or to demonstrate a counter example showing how that property might be violated. However, most dependability cases are written with a single product in mind. At the same time, software product lines (families of related software products) have been studied with the goal of modeling variability and commonality, and building family based techniques for both analysis and testing. However, there has been little work on building an end to end dependability case for a software product line (where a property is modeled, a counter example is found and then validated as a true positive via testing), and none that we know of in an emerging safety-critical domain, that of robotic surgery. In this paper, we study a family of surgical robots, that combine hardware and software, and are highly configurable, representing over 1300 unique robots. At the same time, they are considered safety-critical and should have associated dependability cases. We perform a case study to understand how we can bring together lightweight formal analysis, feature modeling, and testing to provide an end to end pipeline to find potential violations of important safety properties. In the process, we learned that there are some interesting and open challenges for the research community, which if solved will lead towards more dependable safety-critical cyber-physical systems.

To provide strong security support for today’s applications, microprocessor manufacturers have introduced hardware isolation, an on-chip mechanism that provides secure accesses to sensitive data. Currently, hardware isolation is still difficult to use by software developers because the process to identify access points to sensitive data is error-prone and can lead to under and over protection of sensitive data. Under protection can lead to security vulnerabilities. Over protection can lead to an increased attack surface and excessive communication overhead. In this paper we describe EvoIsolator , a search-based framework to (i) automatically generate executable minimal slices that include all access points to a set of specified sensitive data; and (ii) automatically optimize (for small code block size and low communication overhead) the code modules for hardware isolation. We demonstrate, through a small feasibility study, the potential impact of our proposed code optimizer.

Summary Embedded systems are challenging to program correctly, because they use an interrupt‐driven programming paradigm and run in resource‐constrained environments. This leads to various classes of nonfunctional faults that can be detected only by customized verification techniques. These nonfunctional faults are specifically related to usage of resources such as time and memory. For example, the presence of interrupts can induce delays in interrupt servicing and in system execution time. Such delays can occur when multiple interrupt service routines and interrupts of different priorities compete for resources on a given CPU. As another example, stack overflows are caused when the combination of active methods and interrupt invocations on the stack grows too large, and these can lead to data loss and other significant device failures. To detect these types of nonfunctional faults, developers need to estimate worst‐case resource usage. Most existing approaches for calculating such estimates are based on static analysis; however, these have a tendency to overapproximate the resources needed. Dynamic techniques such as random testing, in contrast, often underapproximate resource usage. In this article, we presentSimEspresso, a framework that uses a combination of static analysis and a test case generation algorithm to estimate worst‐case resource usage. There are three different worst‐case resource usage scenarios that we consider: (1) worst‐case execution times, (2) worst‐case interrupt latencies, and (3) worst‐case stack usage.SimEspressofirst uses static analysis to identify program paths and interrupt interleavings that potentially lead to worst‐case scenarios. It then uses a genetic algorithm to generate test cases that guide program execution down these paths, using these particular interrupt interleavings. We performed an empirical study to evaluate the effectiveness ofSimEspresso; our results show thatSimEspressois more effective than static analysis approaches and improves significantly over the state of the art dynamic technique, random test case generation. We also find that when we use only the genetic algorithm, omitting the static analysis,SimEspressoperforms almost as effectively, but takes significantly longer to complete its task.

Most automated testing techniques for graphical user interfaces (GUIs) produce test cases that are only concerned with covering the elements (widgets, menus, etc.) on the interface, or the underlying program code, with little consideration of test case semantics. This is effective for functional testing where the aim is to find as many faults as possible. However, when one wants to mimic a real user for evaluating usability, or when it is necessary to extensively test important end-user tasks of a system, or to generate examples of how to use an interface, this generation approach fails. Capture and replay techniques can be used, however there are often multiple ways to achieve a particular goal, and capturing all of these is usually too time consuming and unrealistic. Prior work on human performance regression testing introduced a constraint based method to filter test cases created by a functional test case generator, however that work did not capture the specifications, or directly generate only the required tests and considered only a single type of test goal. In this paper we present EventFlowSlicer, a tool that allows the GUI tester to specify and generate all realistic test cases relevant to achieve a stated goal. The user first captures relevant events on the interface, then adds constraints to provide restrictions on the task. An event flow graph is extracted containing only the widgets of interest for that goal. Next all test cases are generated for edges in the graph which respect the constraints. The test cases can then be replayed using a modified version of GUITAR. A video demonstration of EventFlowSlicer can be found at https://youtu.be/hw7WYz8WYVU.

The use of virtual devices in place of physical hardware is increasing in activities such as design, testing and debugging. Yet virtual devices are simply software applications, and like all software they are prone to faults. A full system simulator (FSS), is a class of virtual machine that includes a large set of virtual devices -- enough to run the full target software stack. Defects in an FSS virtual device may have cascading effects as the incorrect behavior can be propagated forward to many different platforms as well as to guest programs. In this work we present VDTest, a novel framework for testing virtual devices within an FSS. VDTest begins by generating a test specification obtained through static analysis. It then employs a two-phase testing approach to test virtual components both individually and in combination. It leverages a differential oracle strategy, taking advantage of the existence of a physical or golden device to eliminate the need for manually generating test oracles. In an empirical study using both open source and commercial FSSs, we found 64 faults, 83% more than random testing.

Automated testing has been a focus of research for a long time. As such, we tend to think about this in a coverage centric manner. Testing budgets have also driven research such as prioritization and test selection, but as a secondary concern. As our systems get larger, are more dynamic, and impact more people with each change, we argue that we should switch from a coverage centric view to a budgeted testing centric view. Researchers in other fields have designed approximation algorithms for such budgeted scenarios and these are often simple to implement and run. In this paper we present an exemplar study on combinatorial interaction testing (CIT) to show that a budgeted greedy algorithm, when adapted to our problem for various budgets, does almost as well coverage-wise as a state of the art greedy CIT algorithm, better in some cases than a state of the art simulated annealing, and always improves over random. This suggests that we might benefit from switching our focus in large systems, from coverage to budgets.

System testing and invariant detection is usually conducted from the user interface perspective when the goal is to evaluate the behavior of an application as a whole. A large number of tools and techniques have been developed to generate and automate this process, many of which have been evaluated in the literature or internally within companies. Typical metrics for determining effectiveness of these techniques include code coverage and fault detection, however, with the assumption that there is determinism in the resulting outputs. In this paper we examine the extent to which a common set of factors such as the system platform, Java version, application starting state and tool harness configurations impact these metrics. We examine three layers of testing outputs: the code layer, the behavioral (or invariant) layer and the external (or user interaction) layer. In a study using five open source applications across three operating system platforms, manipulating several factors, we observe as many as 184 lines of code coverage difference between runs using the same test cases, and up to 96 percent false positives with respect to fault detection. We also see some a small variation among the invariants inferred. Despite our best efforts, we can reduce, but not completely eliminate all possible variation in the output. We use our findings to provide a set of best practices that should lead to better consistency and smaller differences in test outcomes, allowing more repeatable and reliable testing and experimentation.

The surge of search based software engineering research has been hampered by the need to develop customized search algorithms for different classes of the same problem. For instance, two decades of bespoke Combinatorial Interaction Testing (CIT) algorithm development, our exemplar problem, has left software engineers with a bewildering choice of CIT techniques, each specialized for a particular task. This paper proposes the use of a single hyperheuristic algorithm that learns search strategies across a broad range of problem instances, providing a single generalist approach. We have developed a Hyperheuristic algorithm for CIT, and report experiments that show that our algorithm competes with known best solutions across constrained and unconstrained problems: For all 26 real-world subjects, it equals or outperforms the best result previously reported in the literature. We also present evidence that our algorithm's strong generic performance results from its unsupervised learning. Hyperheuristic search is thus a promising way to relocate CIT design intelligence from human to machine.

Embedded systems are challenging to program correctly, because they use an interrupt programming paradigm and run in resource constrained environments. This leads to a class of faults for which we need customized verification techniques. One such class of faults, stack overflows, are caused when the combination of active methods and interrupt invocations on the stack grows too large, and these can lead to data loss and other significant device failures. Developers need to estimate the worst-case stack usage (WCSU) during system design, but determining the actual maximum value is known to be a hard problem. The state of the art for calculating WCSU uses static analysis, however this has a tendency to over approximate the potential stack which can lead to wasted resources. Dynamic techniques such as random testing often under approximate the WCSU. In this paper, we present SIMSTACK, a framework that utilizes a combination of static analysis and a genetic algorithm to search for WCSUs. We perform an empirical study to evaluate the effectiveness of SIMSTACK and show that SIMSTACK is competitive with the WCSU values obtained by static analysis, and improves significantly over a random algorithm. When we use only the genetic algorithm, SIMSTACK performs almost as well as the guided technique, but takes significantly longer to converge on the maximum WCSUs.

Recent research in mobile software analysis has begun to combine information extracted from an app's source code and marketplace webpage to identify correlated variables and validate an app's quality properties such as its intended behavior, trust or suspiciousness. Such work typically involves analysis of one or two artifacts such as the GUI text, user ratings, app description keywords, permission requests, and sensitive API calls. However, these studies make assumptions about how the various artifacts are populated and used by developers, which may lead to a gap in the resulting analysis. In this paper, we take a step back and perform an in-depth study of 14 popular apps from the Google Play Store. We have studied a set of 16 different artifacts for each app, and conclude that the output of these must be pieced together to form a complete understanding of the app's true behavior. We show that (1) developers are inconsistent in where and how they provide descriptions; (2) each artifact alone has incomplete information; (3) different artifacts may contain contradictory pieces of information; (4) there is a need for new analyses, such as those that use image processing; and (5) without including analyses of advertisement libraries, the complete behavior of an app is not defined. In addition, we show that the number of downloads and ratings of an app does not appear to be a strong predictor of overall app quality, as these are propagated through versions and are not necessarily indicative of the current app version's behavior.

The structure of preferences for modern highly-configurable software systems has become extremely complex, usually consisting of multiple layers of access that go from the user interface down to the lowest levels of the source code. This complexity can lead to inconsistencies between layers, especially during software evolution. For example, there may be preferences that users can change through the GUI, but that have no effect on the actual behavior of the system because the related source code is not present or has been removed going from one version to the next. These inconsistencies may result in unexpected program behaviors, which range in severity from mild annoyances to more critical security or performance problems. To address this problem, we present SCIC (Software Configuration Inconsistency Checker), a static analysis technique that can automatically detect these kinds of inconsistencies. Unlike other configuration analysis tools, SCIC can handle software that (1) is written in multiple programming languages and (2) has a complex preference structure. In an empirical evaluation that we performed on 10 years worth of versions of both the widely used Mozilla Core and Firefox, SCIC was able to find 40 real inconsistencies (some determined as severe), whose lifetime spanned multiple versions, and whose detection required the analysis of code written in multiple languages.

There are many tools that help software engineers analyze data about their software, projects, and teams. These tools primarily use visualizations to portray data in a concise and understandable way. However, software engineering tasks are often multi-dimensional and temporal, making some visualizations difficult to understand. An alternative for representing data, which can easily incorporate higher dimensionality and temporal information, is the use of sound. In this paper we propose the use of sonification to help portray collaborative development history. Our approach, GitSonifier, combines sound primitives to represent developers, days, and conflicts over the history of a program's development. In a formative user study on an open source project's data, we find that users can easily extract meaningful information from sound clips and differentiate users, passage of time, and development conflicts, suggesting that sonification has the potential to provide benefit in this context.

Summary Test suite augmentation techniques are used in regression testing to identify code elements in a modified program that are not adequately tested and to generate test cases to cover those elements. A defining feature of test suite augmentation techniques is the potential for reusing existing regression test suites. Our preliminary work suggests that several factors influence the efficiency and effectiveness of augmentation techniques that perform such reuse. These include the order in which target code elements are considered while generating test cases, the manner in which existing regression test cases and newly generated test cases are used, and the algorithm used to generate test cases. In this work, we present the results of two empirical studies examining these factors, considering two test case generation algorithms (concolic and genetic). The results of our studies show that the primary factor affecting augmentation using these approaches is the test case generation algorithm utilized; this affects both cost and effectiveness. The manner in which existing and newly generated test cases are utilized also has a substantial effect on efficiency and in some cases a substantial effect on effectiveness. The order in which target code elements are considered turns out to have relatively few effects when using concolic test case generation but in some cases influences the efficiency of genetic test case generation. The results of our first study, on four relatively small programs using a large number of test suites, are supported by our second study of a much larger program available in multiple versions. Together, the studies reveal a potential opportunity for creating a more cost‐effective hybrid augmentation approach leveraging both concolic and genetic test case generation techniques, while appropriately utilizing our understanding of the factors that affect them. Copyright © 2014 John Wiley & Sons, Ltd.

Combinatorial interaction testing (CIT) is important because it tests the interactions between the many features and parameters that make up the configuration space of software systems. Simulated Annealing (SA) and Greedy Algorithms have been widely used to find CIT test suites. From the literature, there is a widely-held belief that SA is slower, but produces more effective tests suites than Greedy and that SA cannot scale to higher strength coverage. We evaluated both algorithms on seven real-world subjects for the well-studied two-way up to the rarely-studied six-way interaction strengths. Our findings present evidence to challenge this current orthodoxy: real-world constraints allow SA to achieve higher strengths. Furthermore, there was no evidence that Greedy was less effective (in terms of time to fault revelation) compared to SA; the results for the greedy algorithm are actually slightly superior. However, the results are critically dependent on the approach adopted to constraint handling. Moreover, we have also evaluated a genetic algorithm for constrained CIT test suite generation. This is the first time strengths higher than 3 and constraint handling have been used to evaluate GA. Our results show that GA is competitive only for pairwise testing for subjects with a small number of constraints.

Test suite augmentation techniques generate test cases to cover code missed by existing regression test suites. Various augmentation techniques have been proposed, utilizing several test case generation algorithms. Research has shown that different algorithms have different strengths, and that combining them into a single hybrid approach may be cost-effective. In this paper we present a framework for hybrid test suite augmentation that allows test case generation algorithms to be interleaved dynamically and that can easily incorporate new algorithms, interleaving strategies, and choices of other parameters that influence algorithm performance. We empirically study an implementation of this framework in which we use two test case generation algorithms and several algorithm interleavings. Our results show that specific instantiations of our framework can produce augmentation techniques that are more cost-effective than others, and illustrate tradeoffs between instantiations.

Embedded systems tend to be interrupt-driven, yet the presence of interrupts can affect system dependability because there can be delays in servicing interrupts. Such delays can occur when multiple interrupt service routines and interrupts of different priorities compete for resources on a given CPU. For this reason, researchers have sought approaches by which to estimate worst-case interrupt latencies (WCILs) for systems. Most existing approaches, however, are based on static analysis. In this paper, we present SIMLATTE, a testing-based approach for finding WCILs. SIMLATTE uses a genetic algorithm for test case generation that converges on a set of inputs and interrupt arrival points that are likely to expose WCILs. It also uses an opportunistic interrupt invocation approach to invoke interrupts at a variety of feasible locations. Our evaluation of SIMLATTE on several non-trivial embedded systems reveals that it is considerably more effective and efficient than random testing. We also determine that the combination of the genetic algorithm and opportunistic interrupt invocation allows SIMLATTE to perform better than it can when using either one in isolation.

Highly configurable software, such as web browsers,databases or office applications, have a large number of preferences that the user can customize, but documentation of them may be scarce or distributed. A user, tester or service technician may have to search through hundreds or thousands of choices in multiple documents when trying to identify which preference will modify a particular system behavior. In this paper we present PrefFinder, a natural language framework that finds (and changes) user preferences. It is tied into an application's preference system and static documentation. We have instantiated PrefFinder as a plugin on two open source applications, and as a stand-alone GUI for an industrial application. PrefFinder finds thecorrect answer between 76-96% of the time on more than 175 queries. When compared to asking questions on a help forum or through the company's service center, we can potentially save days or even weeks of time.

Self-adaptive software systems monitor their state and then adapt when certain conditions are met, guided by a global utility function. In prior work we developed algorithms and conducted a post-hoc analysis demonstrating the possibility of adapting to software failures by judiciously changing configurations. In this paper we present the REFRACT framework that realizes this idea in practice by building on the self-adaptive Rainbow architecture. REFRACT extends Rainbow with new components and algorithms targeting failure avoidance. We use REFRACT in a case study running four independently executing Firefox clients with 36 passing test cases and 7 seeded faults. The study show that workarounds for all but one of the seeded faults are found and the one that is not found never fails -- it is guarded from failing by a related workaround. Moreover, REFRACT finds workarounds for eight configuration-related unseeded failures from tests that were expected to pass (and did under the default configuration). Finally, the data show that when a failure and its workaround are found, configuration guards prevent the failure from appearing again. In a simulation lasting 24 hours we see over 150 guard activations and no failures with workarounds remaining beyond 16 hours.

The configuration spaces of modern software systems are too large to test exhaustively. Combinatorial interaction testing (CIT) approaches, such as covering arrays, systematically sample the configuration space and test only the selected configurations. The basic justification for CIT approaches is that they can cost-effectively exercise all system behaviors caused by the settings of t or fewer options. We conjecture, however, that in practice some of these behaviors are not actually tested because of unanticipated masking effects - test case failures that perturb system execution so as to prevent some behaviors from being exercised. While prior research has identified this problem, most solutions require knowing the masking effects a priori. In practice this is impractical, if not impossible. In this work, we reduce the harmful consequences of masking effects. First we define a novel interaction testing criterion, which aims to ensure that each test case has a fair chance to test all valid t-way combinations of option settings. We then introduce a feedback driven adaptive combinatorial testing process (FDA-CIT) to materialize this criterion in practice. At each iteration of FDA-CIT, we detect potential masking effects, heuristically isolate their likely causes (i.e., fault characterization), and then generate new samples that allow previously masked combinations to be tested in configurations that avoid the likely failure causes. The iterations end when the new interaction testing criterion has been satisfied. This paper compares two different fault characterization approaches - an integral part of the proposed approach, and empirically assesses their effectiveness and efficiency in removing masking effects on two widely used open source software systems. It also compares FDA-CIT against error locating arrays, a state of the art approach for detecting and locating failures. Furthermore, the scalability of the proposed approach is evaluated by comparing it with perfect test scenarios, in which all masking effects are known a priori. Our results suggest that masking effects do exist in practice, and that our approach provides a promising and efficient way to work around them, without requiring that masking effects be known a priori.

System testing of applications with graphical user interfaces (GUIs) such as web browsers, desktop, or mobile apps, is more complex than testing from the command line. Specialized tools are needed to generate and run test cases, models are needed to quantify behavioral coverage, and changes in the environment, such as the operating system, virtual machine or system load, as well as starting states of the executions, impact the repeatability of the outcome of tests making tests appear flaky. In this tutorial, we present an overview of the state of the art in GUI testing, consisting of both lectures and demonstrations on various platforms (desktop, web and mobile applications), using an open source testing tool, GUITAR. We show how to setup a system under test, how to extract models without source code, and how to then use those models to generate and replay test cases. We then present a lecture on the various factors that may cause flakiness in the execution of GUI-centric software, and hence impact the results of analyses and experiments based on such software. We end with a demonstration of a community resource for sharing GUI testing artifacts aimed at controlling these factors. This tutorial targets both researchers who develop techniques for testing GUI software, and practitioners from industry who want to learn more about model-based GUI testing or who run and rerun GUI tests and often find their runs are flaky.

As software systems evolve, new interface features such as keyboard shortcuts and toolbars are introduced. While it is common to regression test the new features for functional correctness, there has been less focus on systematic regression testing for usability, due to the effort and time involved in human studies. Cognitive modeling tools such as CogTool provide some help by computing predictions of user performance, but they still require manual effort to describe the user interface and tasks, limiting regression testing efforts. In recent work, we developed CogTool-Helper to reduce the effort required to generate human performance models of existing systems. We build on this work by providing task specific test case generation and present our vision for human performance regression testing (HPRT) that generates large numbers of test cases and evaluates a range of human performance predictions for the same task. We examine the feasibility of HPRT on four tasks in LibreOffice, find several regressions, and then discuss how a project team could use this information. We also illustrate that we can increase efficiency with sampling by leveraging an inference algorithm. Samples that take approximately 50% of the runtime lose at most 10% of the performance predictions.

Combinatorial Interaction Testing (CIT) is important because it tests the interactions between the many features and parameters that make up the configuration space of software systems. However, in order to be practically applicable, it must be able to cater for soft and hard real-world constraints and should, ideally, report a test priority order that maximises earliest fault detection. We show that we can achieve the highest strength CIT in 5.65 minutes on average. This was previously thought to be too computationally expensive to be feasible. Furthermore, we show that higher strength suites find more faults, while prioritisations using lower strengths are no worse at achieving early fault revelation.

Software Product Line (SPL) engineering offers several advantages in the development of families of software products. There is still a need, however, to generate test cases for individual products in product lines more efficiently. In this paper we propose an approach, CONTESA, for generating test cases for SPLs using test suite augmentation. Instead of generating test cases for products independently, our approach generates new test cases for products in an order that allows it to build on test cases created for products tested earlier. In this work, we use a genetic algorithm to generate test cases, targeting branches not yet covered in each product, although other algorithms and coverage criteria could be utilized. We have evaluated CONTESA on two non-trivial SPLs, and have shown that CONTESA is more efficient and effective than an approach that generates test cases for products independently. A further evaluation shows that CONTESA is more effective at achieving coverage, and reveals as many faults as an existing feature-based testing approach.

With the rise of tools for predictive human performance modeling in HCI comes a need to model legacy applications. Models of legacy systems are used to compare products to competitors, or new proposed design ideas to the existing version of an application. We present CogTool-Helper, an exemplar of a tool that results from joining this HCI need to research in automatic GUI testing from the Software Engineering testing community. CogTool-Helper uses automatic UI-model extraction and test case generation to automatically create CogTool storyboards and models and infer methods to accomplish tasks beyond what the UI designer has specified. A design walkthrough with experienced CogTool users reveal that CogTool-Helper resonates with a "pain point" of real-world modeling and provide suggestions for future work.

Developers of a software's graphical user interface (GUI) often fail to document the interface specifications. Without these, models used for automated test generation and execution remain imperfect and incomplete. This leads to unexpected behavior that creates unrecoverable situations for test harnesses, and missed coverage. In this paper, we present AutoInSpec, a technique to infer an important class of specifications, temporal and state-based invariants between GUI events that have been incorrectly modeled. Unlike existing specification mining approaches that require full execution traces, or source code, and that mine all invariants, we simplify the problem. We guide AutoInSpec with coverage criteria and use a previously developed repair framework that builds coverage-adequate test suites, removing unexecutable sub-sequences from consideration. These failing sub-sequences are input to a logic-based inference engine, armed with known invariant templates, to obtain the missing specifications. We validate AutoInSpec on a set of well studied GUI applications.

Many organizations are moving towards a business model of Software as a Service (SaaS), where customers select and pay for services dynamically via the web. In SaaS, service providers face the challenge of delivering and maintaining high quality software solutions which must continue to work under an enormous number of scenarios; customers can easily subscribe and unsubscribe from services at any point. To date, there has been little research on unique approaches for regression test methodologies for testing in a SaaS environment. In this paper, we present an industrial case study of a regression testing approach to improve test effectiveness and efficiency in SaaS. We model service level use cases from field failures as abstract events and then generate sequences of these for testing to provide a broad coverage of the possible use cases. In subsequent releases of the system we prioritize the tests to improve time to detection of faults in the modified system. We have applied our technique to two releases of a large industrial enterprise level SaaS application and demonstrate that using our approach (1) we could have uncovered escaped faults prior to the system release in both versions of the system; (2) using a priority order we could have improved the efficiency of testing in the first version; and (3) prioritization based on failure history from the first version increases the fault detection rate in the new version, suggesting a correlation between the important sequences in versions that can be leveraged for regression testing.

While a large body of research is dedicated to testing for feature interactions in configurable software, there has been little work that examines what constitutes such a fault at the code level. In consequence, we do not know how prevalent real interaction faults are in practice, what a typical interaction fault looks like in code, how to seed interaction faults, or whether current interaction testing techniques are effective at finding the faults they aim to detect. We make a first step in this direction, by deriving a white box criterion for an interaction fault. Armed with this criterion, we perform an exploratory study on hundreds of faults from the field in two open source systems. We find that only three of the 28 which appear to be interaction faults are in fact due to features' interactions. We investigate the remaining 25 and find that, although they could have been detected without interaction testing, varying the system configuration amplifies the fault-finding power of a test suite, making these faults easier to expose. Thus, we characterize the benefits of interaction testing in regards to both interaction and non-interaction faults. We end with a discussion of several mutations that can be used to mimic interaction faults based on the faults we see in practice.

The configuration spaces of modern software systems are too large to test exhaustively. Combinatorial interaction testing (CIT) approaches, such as covering arrays, systematically sample the configuration space and test only the selected configurations. The basic justification for CIT approaches is that they can cost-effectively exercise all system behaviors caused by the settings of t or fewer options. We conjecture, however, that in practice many such behaviors are not actually tested because of masking effects -- failures that perturb execution so as to prevent some behaviors from being exercised. In this work we present a feedback-driven, adaptive, combinatorial testing approach aimed at detecting and working around masking effects. At each iteration we detect potential masking effects, heuristically isolate their likely causes, and then generate new covering arrays that allow previously masked combinations to be tested in the subsequent iteration. We empirically assess the effectiveness of the proposed approach on two large widely used open source software systems. Our results suggest that masking effects do exist and that our approach provides a promising and efficient way to work around them.

Graphical user interfaces (GUIs), due to their event-driven nature, present an enormous and potentially unbounded way for users to interact with software. During testing, it is important to “adequately cover” this interaction space. In this paper, we develop a new family of coverage criteria for GUI testing grounded in combinatorial interaction testing. The key motivation of using combinatorial techniques is that they enable us to incorporate “context” into the criteria in terms of event combinations, sequence length, and by including all possible positions for each event. Our new criteria range in both efficiency (measured by the size of the test suite) and effectiveness (the ability of the test suites to detect faults). In a case study on eight applications, we automatically generate test cases and systematically explore the impact of context, as captured by our new criteria. Our study shows that by increasing the event combinations tested and by controlling the relative positions of events defined by the new criteria, we can detect a large number of faults that were undetectable by earlier techniques.

In virtual machines for embedded devices that use just-in-time compilation, the management of the code cache can significantly impact performance in terms of both memory usage and start-up time. Although improving memory usage has been a common focus for system designers, start-up time is often overlooked. In systems with constrained resources, however, these two performance metrics are often at odds and must be considered together. In this paper, we present an adaptive self-adjusting code cache manager to improve performance with respect to both start-up time and memory usage. It balances these concerns by detecting changes in method compilation rates, resizing the cache after each pitching event. We conduct experiments to validate our proposed system and quantify the impacts that different code cache management techniques have on memory usage and start-up time through two oracle systems. Our results show that the proposed algorithm yields nearly the same start-up times as a hand-tuned oracle and shorter execution times than those of the SSCLI in eight out of ten applications. It also has lower memory usage over time in all but one application.

Test suite augmentation techniques are used in regression testing to help engineers identify code elements affected by changes, and generate test cases to cover those elements. Researchers have created various approaches to identify affected code elements, but only recently have they considered integrating, with this task, approaches for generating test cases. In this paper we explore the use of genetic algorithms in test suite augmentation. We identify several factors that impact the effectiveness of this approach, and we present the results of a case study exploring the effects of one of these factors: the manner in which existing and newly generated test cases are utilized by the genetic algorithm. Our results reveal several ways in which this factor can influence augmentation results, and reveal open problems that researchers must address if they wish to create augmentation techniques that make use of genetic algorithms.

Combinatorial testing is a specification based sampling technique that provides a systematic way to select combinations of program inputs or features for testing. It has been applied over the years to test input data, configurations, web forms, protocols, graphical user interfaces and for testing software product lines. This tutorial introduces the fundamentals of combinatorial testing, including both practical and theoretical foundations, to provide a comprehensive introduction that is relevant to both test practitioners and software engineering researchers. The tutorial will present an overview of Combinatorial Test Design (CTD) and describe some state of the art research advances and domains where CTD has been applied. It will present the theoretical underpinnings of CTD and explain a few algorithmic techniques used to generate CTD samples, as well as describe recent work on practical extensions to these algorithms that allow for a broader use of CTD. A session devoted to modeling test problems using CTD will follow, with attendees obtaining hands-on experience using several realistic problems.

Recent advances in automated functional testing of Graphical User Interfaces (GUIs) rely on deriving graph models that approximate all possible sequences of events that may be executed on the GUI, and then use the graphs to generate test cases (event sequences) that achieve a specified coverage goal. However, because these models are only approximations of the actual event flows, the generated test cases may suffer from problems of infeasibility, i.e., some events may not be available for execution causing the test case to terminate prematurely. In this paper we develop a method to automatically repair GUI test suites, generating new test cases that are feasible. We use a genetic algorithm to evolve new test cases that increase our test suite's coverage while avoiding infeasible sequences. We experiment with this algorithm on a set of synthetic programs containing different types of constraints and for test sequences of varying lengths. Our results suggest that we can generate new test cases to cover most of the feasible coverage and that the genetic algorithm outperforms a random algorithm trying to achieve the same goal in almost all cases.

Test suite augmentation techniques are used in regression testing to identify code elements affected by changes and to generate test cases to cover those elements. Our preliminary work suggests that several factors influence the cost and effectiveness of test suite augmentation techniques. These include the order in which affected elements are considered while generating test cases, the manner in which existing regression test cases and newly generated test cases are used, and the algorithm used to generate test cases. In this work, we present the results of an empirical study examining these factors, considering two test case generation algorithms (concolic and genetic). The results of our experiment show that the primary factor affecting augmentation is the test case generation algorithm utilized; this affects both cost and effectiveness. The manner in which existing and newly generated test cases are utilized also has a substantial effect on efficiency but a lesser effect on effectiveness. The order in which affected elements are considered turns out to have relatively few effects when using concolic test case generation, but more substantial effects when using genetic test case generation.

System testing of configurable software is an expensive and resource constrained process. Insufficient testing often leads to escaped faults in the field where failures impact customers and are costly to repair. Prior work has shown that it is possible to efficiently sample configurations for testing using combinatorial interaction testing, and to prioritize these configurations to increase the rate of early fault detection. The underlying assumption to date has been that there is no added complexity to configuring a system level environment over a user configurable one; i.e. the time required to setup and test each individual configuration is nominal. In this paper we examine prioritization of system configurable software driven not only by fault detection but also by the cost of configuration and setup time that moving between different configurations incurs. We present a case study on two releases of an enterprise software system using failures reported in the field. We examine the most effective prioritization technique and conclude that (1) using failure history of configurations can improve the early fault detection rate, but that (2) we must consider fault detection rate over time, not by the number of configurations tested. It is better to test related configurations which incur minimal setup time than to test fewer, more diverse configurations.

The increasing complexity of configurable software systems has created a need for more intelligent sampling mechanisms to detect and characterize failure-inducing dependencies between configurations. Prior work - in idealized environments - has shown that test schedules based on a mathematical object, called a covering array, in combination with classification techniques, can meet this need. Applying this approach in practice, however, is tricky because testing time and resource availability are unpredictable, and because failure characteristics can change from release to release. With current approaches developers must set a key covering array parameter (its strength) based on estimated release times and failure characterizations. This will influence the outcome of their results.

Configurable software lets users customize applications in many ways, and is becoming increasingly prevalent. Researchers have created techniques for testing configurable software, but to date, only a little research has addressed the problems of regression testing configurable systems as they evolve. Whereas problems such as selective retesting and test prioritization at the test case level have been extensively researched, these problems have rarely been considered at the configuration level. In this paper we address the problem of providing configuration-aware regression testing for evolving software systems. We use combinatorial interaction testing techniques to model and generate configuration samples for use in regression testing. We conduct an empirical study on a non-trivial evolving software system to measure the impact of configurations on testing effectiveness, and to compare the effectiveness of different configuration prioritization techniques on early fault detection during regression testing. Our results show that configurations can have a large impact on fault detection and that prioritization of configurations can be effective.

Researchers have explored the application of combinatorial interaction testing (CIT) methods to construct samples to drive systematic testing of software system configurations. Applying CIT to highly-configurable software systems is complicated by the fact that, in many such systems, there are constraints between specific configuration parameters that render certain combinations invalid. Many CIT algorithms lack a mechanism to avoid these. In recent work, automated constraint solving methods have been combined with search-based CIT construction methods to address the constraint problem with promising results. However, these techniques can incur a non-trivial overhead. In this paper, we build upon our previous work to develop a family of greedy CIT sample generation algorithms that exploit calculations made by modern Boolean satisfiability (SAT) solvers to prune the search space of the CIT problem. We perform a comparative evaluation of the cost-effectiveness of these algorithms on four real-world highly-configurable software systems and on a population of synthetic examples that share the characteristics of those systems. In combination our techniques reduce the cost of CIT in the presence of constraints to 30 percent of the cost of widely-used unconstrained CIT methods without sacrificing the quality of the solutions.

Regression testing is an expensive part of the software maintenance process. Effective regression testing techniques select and order (or prioritize) test cases between successive releases of a program. However, selection and prioritization are dependent on the quality of the initial test suite. An effective and cost efficient test generation technique is combinatorial interaction testing, CIT, which systematically samples all t-way combinations of input parameters. Research on CIT, to date, has focused on single version software systems. There has been little work that empirically assesses the use of CIT test generation as the basis for selection or prioritization. In this paper we examine the effectiveness of CIT across multiple versions of two software subjects. Our results show that CIT performs well in finding seeded faults when compared with an exhaustive test set. We examine several CIT prioritization techniques and compare them with a re-generation/prioritization technique. We find that prioritized and re-generated/prioritized CIT test suites may find faults earlier than unordered CIT test suites, although the re-generated/prioritized test suites sometimes exhibit decreased fault detection.

Combinatorial interaction testing (CIT) is a method to sample configurations of a software system systematically for testing. Many algorithms have been developed that create CIT samples, however few have considered the practical concerns that arise when adding constraints between combinations of options. In this paper, we survey constraint handling techniques in existing algorithms and discuss the challenges that they present. We examine two highly-configurable software systems to quantify the nature of constraints in real systems. We then present a general constraint representation and solving technique that can be integrated with existing CIT algorithms and compare two constraint-enhanced algorithm implementations with existing CIT tools to demonstrate feasibility.

This paper describes a new automated technique to generate test cases for GUIs by using covering arrays (CAs). The key motivation is to generate long GUI event sequences that are systematically sampled at a particular coverage strength. CAs, to date, have not been effectively used in sampling event driven systems such as GUIs which maintain state. We leverage a "stateless" abstraction of GUIs that allows us to use CAs. Once the CAs have been generated, we reuse the abstractions to reinsert ordering relationships between GUI events, thereby creating executable test cases. A feasibility study on a well-studied GUI-based application shows that the new technique is able to detect a large number of previously undetected faults

The increasing complexity of configurable software systems creates a need for more intelligent sampling mechanisms to detect and locate failure-inducing dependencies between configurations. Prior work shows that test schedules basedon a mathematical object, called a covering array, can beused to detect and locate failures in combination with a classification tree analysis. This paper addresses limitations ofthe earlier approach. First, the previous work requires developers to choose the covering array's strength, even thought here is no scientific or historical basis for doing so. Second, if a single covering array is insufficient to classify specificfailures, the entire process must be rerun from scratch. To address these issues, our new approach incrementally and adaptively builds covering array schedules. It begins witha low strength, and continually increases this as resources allow, or poor classification results require. At each stage, previous tests are reused. This allows failures due to only one or two configurations settings to be found and classified as early as possible, and also limits duplication of work when multiple covering arrays must be used.

Garbage collection can be a performance bottleneck in large distributed, multi-threaded applications. Applications may produce millions of objects during their lifetimes and may invoke hundreds or thousands of threads. When using a single shared heap, each time a garbage collection phase occurs all threads must be stopped, essentially halting all other processing. Attempts to fix this bottleneck include creating a single heap per thread, however this may not scale to large thread intensive applications. In this paper we explore the potential of clustering threads into related sub-heaps. We hypothesize that this will lead to a smaller shared heap, while maintaining good garbage collection parallelism. We leverage results from software module clustering to achieve this goal. Our results show that we can significantly reduce the number of sub-heaps created and reduce the number of objects in the shared heap in a representative application. This suggests that clustering may be a promising optimization technique for garbage collection in large multi-threaded systems with many shared objects.

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

Many modern software systems are designed to be highly configurable so they can run on and be optimized for a wide variety of platforms and usage scenarios. Testing such systems is difficult because, in effect, you are testing a multitude of systems, not just one. Moreover, bugs can and do appear in some configurations, but not in others. Our research focuses on a subset of these bugs that are "option-related"-those that manifest with high probability only when specific configuration options take on specific settings. Our goal is not only to detect these bugs, but also to automatically characterize the configuration subspaces (i.e., the options and their settings) in which they manifest. To improve efficiency, our process tests only a sample of the configuration space, which we obtain from mathematical objects called covering arrays. This paper compares two different kinds of covering arrays for this purpose and assesses the effect of sampling strategy on fault characterization accuracy. Our results strongly suggest that sampling via covering arrays allows us to characterize option-related failures nearly as well as if we had tested exhaustively, but at a much lower cost. We also provide guidelines for using our approach in practice.

Greedy algorithms for the construction of software interaction test suites are studied. A framework is developed to evaluate a large class of greedy methods that build suites one test at a time. Within this framework are many instantiations of greedy methods generalizing those in the literature. Greedy algorithms are popular when the time for test suite construction is of paramount concern. We focus on the size of the test suite produced by each instantiation. Experiments are analyzed using statistical techniques to determine the importance of the implementation decisions within the framework. This framework provides a platform for optimizing the accuracy and speed of "one-test-at-a-time" greedy methods.

Testing systems with large configurations spaces that change often is a challenging problem. The cost and complexity of QA explodes because often there isn't just one system, but a multitude of related systems. Bugs may appear in certain configurations, but not in others.The Skoll system and process has been developed to test these types of systems through distributed, continuous quality assurance, leveraging user resources around-the-world, around-the-clock. It has been shown to be effective in automatically characterizing configurations in which failures manifest. The derived information helps developers quickly narrow down the cause of failures which then improves turn around time for fixes. However, this method does not scale well. It requires one to exhaustively test each configuration in the configuration space.In this paper we examine an alternative approach. The idea is to systematically sample the configuration space, test only the selected configurations, and conduct fault characterization on the resulting data. The sampling approach we use is based on calculating a mathematical object called a covering array. We empirically assess the effect of using covering array derived test schedules on the resulting fault characterizations and provide guidelines to practitioners for their use.

Complete interaction testing of components is too costly in all but the smallest systems. Yet component interactions are likely to cause unexpected faults. Recently, design of experiment techniques have been applied to software testing to guarantee a minimum coverage of all t-way interactions across components. However, t is always fixed. This paper examines the need to vary the size of t in an individual test suite and defines a new object, the variable strength covering array that has this property. We present some computational methods to find variable strength arrays and provide initial bounds for a group of these objects.

Software system faults are often caused by unexpected interactions among components. Yet the size of a test suite required to test all possible combinations of interactions can be prohibitive in even a moderately sized project. Instead, we may use pairwise or t-way testing to provide a guarantee that all pairs or t-way combinations of components are tested together This concept draws on methods used in statistical testing for manufacturing and has been extended to software system testing. A covering array, CA(N; t, k, v), is an N/spl times/k array on v symbols such that every N x t sub-array contains all ordered subsets from v symbols of size t at least once. The properties of these objects, however do not necessarily satisfy real software testing needs. Instead we examine a less studied object, the mixed level covering array and propose a new object, the variable strength covering array, which provides a more robust environment for software interaction testing. Initial results are presented suggesting that heuristic search techniques are more effective than some of the known greedy methods for finding smaller sized test suites. We present a discussion of an integrated approach for finding covering arrays and discuss how application of these techniques can be used to construct variable strength arrays.

Component based software development is prone to unexpected interaction faults. The goal is to test as many-potential interactions as is feasible within time and budget constraints. Two combinatorial objects, the orthogonal array and the covering array, can be used to generate test suites that provide a guarantee for coverage of all t-sets of component interactions in the case when the testing of all interactions is not possible. Methods for construction of these types of test suites have focused on two main areas. The first is finding new algebraic constructions that produce smaller test suites. The second is refining computational search algorithms to find smaller test suites more quickly. In this paper we explore one method for constructing covering arrays of strength three that combines algebraic constructions with computational search. This method leverages the computational efficiency and optimality of size obtained through algebraic constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide some new bounds for some strength three covering arrays.

Dish arrays have been designed with two competing goals in mind, the ability to reconstruct erased disks (reliability), and the speed with which information can be read, written, and reconstructed (performance). The substantial loss in performance of write operations as reliability requirements increase has resulted in an emphasis on performance at the expense of reliability. This has proved acceptable given the relatively small members of disks in current disk arrays. We develop a method for improving the performance of write operations in disk arrays capable of correcting any double erasure, by ordering the columns of the erasure code to minimize the amount of parity information that requires updating. For large disk arrays, this affords a method to support the reliability needed without the generally accepted loss of performance.