The paper “Prioritizing Test Cases for Regression Testing”, by Rothermel, Untch, Chu and Harrold, appeared in IEEE Transactions on Software Engineering in 2001. This paper was a seminal paper in the area of test case prioritization, and it set the stage for research on many different topics related to prioritization. In this retrospective, we recount the work presented in the paper, and then reflect on how it has influenced subsequent research and practice.

Summary A cyber‐physical system (CPS) is a collection of computing devices that communicate with each other, operate in the target environment via actuators and interact with the physical world through sensors in a feedback loop. CPSs need to be safe and reliable and function in accordance with their requirements. Testing, focusing on a CPS model and/or its code, is the primary approach used by engineers to achieve this. Generating, selecting and prioritizing test cases that can reveal faults in CPSs, from the wide range of possible input values and stimuli that affect their operation, are of central importance in this process. To date, however, in our search of the literature, we have found no comprehensive survey of research on test case generation, selection and prioritization for CPSs. In this article, therefore, we report the results of a survey of approaches for generating, selecting and prioritizing test cases for CPSs; the results illustrate the progress that has been made on these approaches to date, the properties that characterize the approaches and the challenges that remain open in these areas of research.

Alloy is a lightweight specification language based on relational logic, with an analysis engine that relies on SAT solvers to automate bounded verification of specifications. In spite of its strengths, the reliance of the Alloy Analyzer on computationally heavy solvers means that it can take a significant amount of time to verify software properties, even within limited bounds. This challenge is exacerbated by the ever-evolving nature of complex software systems. This paper presents Platinum , a technique for efficient analysis of evolving Alloy specifications, that recognizes opportunities for constraint reduction and reuse of previously identified constraint solutions. The insight behind Platinum is that formula constraints recur often during the analysis of a single specification and across its revisions, and constraint solutions can be reused over sequences of analyses performed on evolving specifications. Our empirical results show that Platinum substantially reduces (by 66.4% on average) the analysis time required on specifications extracted from real-world software systems.

Automated UI testing is an important component of the continuous integration process of software development. A modern web-based UI is an amalgam of reports from dozens of microservices written by multiple teams. Queries on a page that opens up another will fail if any of that page's microservices fails. As a result, the overall cost for automated UI testing is high since the UI elements cannot be tested in isolation. For example, the entire automated UI testing suite at LexisNexis takes around 30 hours (3-5 hours on the cloud) to execute, which slows down the continuous integration process.

When testing client-side web applications, it is important to consider different web-browser environments. Different properties of these environments such as web-browser types and underlying platforms may cause a web application to exhibit different types of failures. As web applications evolve, they must be regression tested across these different environments. Because there are many environments to consider this process can be expensive, resulting in delayed feedback about failures in applications. In this work, we propose six techniques for providing a developer with faster feedback on failures when regression testing web applications across different web-browser environments. Our techniques draw on methods used in test case prioritization; however, in our case we prioritize web-browser environments, based on information on recent and frequent failures. We evaluated our approach using four non-trivial and popular open-source web applications. Our results show that our techniques outperform two baseline methods, namely, no ordering and random ordering, in terms of the cost-effectiveness. The improvement rates ranged from −12.24% to 39.05% for no ordering, and from −0.04% to 45.85% for random ordering.

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.

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.

When multiple apps on an Android platform interact, faults and security vulnerabilities can occur. Software engineers need to be able to analyze interacting apps to detect such problems. Current approaches for performing such analyses, however, do not scale to the numbers of apps that may need to be considered, and thus, are impractical for application to real-world scenarios. In this paper, we introduce JITANA, a program analysis framework designed to analyze multiple Android apps simultaneously. By using a classloader-based approach instead of a compiler-based approach such as SOOT, JITANA is able to simultaneously analyze large numbers of interacting apps, perform on-demand analysis of large libraries, and effectively analyze dynamically generated code. Empirical studies of JITANA show that it is substantially more efficient than a state-of-the-art approach, and that it can effectively and efficiently analyze complex apps including Facebook, Pokemon Go, and Pandora that the state-of-the-art approach cannot handle.

Summary Race conditions are difficult to detect because they usually occur only under specific execution interleavings. Numerous program analysis and testing techniques have been proposed to detect race conditions between threads on single applications. However, most of these techniques neglect races that occur at the process level due to complex system event interactions. This article presents a framework,SIMEXPLORER, that allows engineers to effectively test for process‐level race conditions.SIMEXPLORERfirst uses dynamic analysis techniques to observe system execution, identify program locations of interest, and report faults related to oracles. Next, it uses virtualization to achieve the fine‐grained controllability needed to exercise event interleavings that are likely to expose races. We evaluated the effectiveness ofSIMEXPLORERon 24 real‐world applications containing both known and unknown process‐level race conditions. Our results show thatSIMEXPLORERis effective at detecting these race conditions, while incurring an overhead that is acceptable given its effectiveness improvements.

Software engineers often use record/replay tools to enable the automated testing of web applications. Tests created in this manner can then be used to regression test new versions of the web applications as they evolve. Web application tests recorded by record/replay tools, however, can be quite brittle, they can easily break as applications change. For this reason, researchers have begun to seek approaches for automatically repairing record/replay tests. To date, however, there have been no comprehensive attempts to characterize the causes of breakagesin record/replay tests for web applications. In this work, wepresent a taxonomy classifying the ways in which record/replay tests for web applications break, based on an analysis of 453 versions of popular web applications for which 1065 individual test breakages were recognized. The resulting taxonomy can help direct researchers in their attempts to repair such tests. It can also help practitioners by suggesting best practices when creating tests or modifying programs, and can help researchers with other tasks such as test robustness analysis and IDE design.

Regression test selection (RTS) techniques reduce the cost of regression testing by running only test cases related to code modifications. RTS techniques have been extensively researched, and the effects of several context factors on techniques have been empirically studied, but no prior work has explored the effects that might arise due to differences in types of test suites. We believe such differences may matter, and thus, we designed an empirical study to investigate them. Specifically, we consider two types of test suites obtained with automated test case generation techniques – feedback-directed random techniques and search-based techniques – along with manually written test suites. We assess the effects of these test suite types on two RTS techniques: a "fine-grained" technique that selects test cases based on dependencies tracked at the method level and a "coarse-grained" technique that selects test cases based on dependencies tracked at the file level. We performed our study on eight open-source projects across 800 commits. Our results show that on average, fine-grained RTS was more effective for test suites created by search-based test case generation techniques whereas coarse-grained RTS was more effective for test suites created by feedback-directed random techniques, and that commits affect RTS techniques differently for different types of test suites.

Process-level races are endemic in modern systems. These races are difficult to debug because they are sensitive to execution events such as interrupts and scheduling. Unless a process interleaving that can result in the race can be found, it cannot be reproduced and cannot be corrected. In practice, however, the number of interleavings that can occur among processes in practice is large, and the patterns of interleavings can be complex. Thus, approaches for reproducing process-level races to date are often ineffective. In this paper, we present RRF, a race reproduction framework that can help software engineers reproduce reported process-level races, enabling them to potentially debug these races. RRF performs a hybrid analysis by leveraging existing static program analysis tools, dynamic kernel event reporting tools, and yield points to provide the observability and controllability needed to reproduce races. We conducted an empirical study to evaluate RRF, our results show that RRF can be effective for reproducing races.

Software engineers use record/replay tools to capture use case scenarios that can serve as regression tests for web applications. Such tests, however, can be brittle in the face of code changes. Thus, researchers have sought automated approaches for repairing broken record/replay tests. To date, such approaches have operated by directly analyzing differences between the releases of web applications. Often, however, intermediate versions or commits exist between releases, and these represent finer-grained sequences of changes by which new releases evolve. In this paper, we present WATERFALL, an incremental test repair approach that applies test repair techniques iteratively across a sequence of fine-grained versions of a web application. The results of an empirical study on seven web applications show that our approach is substantially more effective than a coarse-grained approach (209% overall), while maintaining an acceptable level of overhead.

Random testing (RT) has been widely used in the testing of various software and hardware systems. Adaptive random testing (ART) is a family of random testing techniques that aim to enhance the failure-detection effectiveness of RT by spreading random test cases evenly throughout the input domain. ART has been empirically shown to be effective on software with numeric inputs. However, there are two aspects of ART that need to be addressed to render its adoption more widespread-applicability to programs with nonnumeric inputs, and the high computation overhead of many ART algorithms. We present a linear-order ART algorithm for software with non-numeric inputs. The key requirement for using ART with non-numeric inputs is an appropriate “distance” measure. We use the concepts of categories and choices from category-partition testing to formulate such a measure. We investigate the failure-detection effectiveness of our technique by performing an empirical study on 14 object programs, using two standard metrics-F-measure and P-measure. Our ART algorithm statistically significantly outperforms RT on 10 of the 14 programs studied, and exhibits performance similar to RT on three of the four remaining programs. The selection overhead of our ART algorithm is close to that of RT.

Recording the sequence of events that lead to a failure of a web application can be an effective aid for debugging. Nevertheless, a recording of an event sequence may include many events that are not related to a failure, and this may render debugging more difficult. To address this problem, we have adapted Delta Debugging to function on recordings of web applications, in a manner that lets it identify and discard portions of those recordings that do not influence the occurrence of a failure. We present the results of three empirical studies that show that (1) recording reduction can achieve significant reductions in recording size and replay time on actual web applications obtained from developer forums, (2) reduced recordings do in fact help programmers locate faults significantly more efficiently as, and no less effectively than non-reduced recordings, and (3) recording reduction produces even greater reductions on larger, more complex applications.

Summary Testing multithreaded programs is inherently challenging, as programs can exhibit numerous thread interactions. To help engineers test these programs cost‐effectively, researchers have proposed concurrency coverage metrics. These metrics are intended to be used as predictors for testing effectiveness and provide targets for test generation. The effectiveness of these metrics, however, remains largely unexamined. In this work, we explore the impact of concurrency coverage metrics on testing effectiveness and examine the relationship between coverage, fault detection, and test suite size. We study eight existing concurrency coverage metrics and six new metrics formed by combining complementary metrics. Our results indicate that the metrics are moderate to strong predictors of testing effectiveness and effective at providing test generation targets. Nevertheless, metric effectiveness varies across programs, and even combinations of complementary metrics do not consistently provide effective testing. These results highlight the need for additional work on concurrency coverage metrics. Copyright © 2014 John Wiley & Sons, Ltd.

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.

In regression testing, running all a system's test cases can require a great deal of time and resources. Test case prioritization (TCP) attempts to schedule test cases to achieve goals such as higher coverage or faster fault detection. While code coverage-based approaches are typical in TCP, recent work has explored the use of additional information to improve effectiveness. In this work, we explore the use of Information Retrieval (IR) techniques to improve the effectiveness of TCP, particularly for testing infrequently tested code. Our approach considers the frequency at which elements have been tested, in additional to traditional coverage information, balancing these factors using linear regression modeling. Our empirical study demonstrates that our approach is generally more effective than both random and traditional code coverage-based approaches, with improvements in rate of fault detection of up to 4.7%.

Concurrent programs are prone to various classes of difficult-to-detect faults, of which data races are particularly prevalent. Prior work has attempted to increase the cost-effectiveness of approaches for testing for data races by employing race detection techniques, but to date, no work has considered cost-effective approaches for re-testing for races as programs evolve. In this paper we present SimRT, an automated regression testing framework for use in detecting races introduced by code modifications. SimRT employs a regression test selection technique, focused on sets of program elements related to race detection, to reduce the number of test cases that must be run on a changed program to detect races that occur due to code modifications, and it employs a test case prioritization technique to improve the rate at which such races are detected. Our empirical study of SimRT reveals that it is more efficient and effective for revealing races than other approaches, and that its constituent test selection and prioritization components each contribute to its performance.

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.

Software complexity has increased the need for automated software testing. Most research on automating testing, however, has focused on creating test input data. While careful selection of input data is necessary to reach faulty states in a system under test, test oracles are needed to actually detect failures. In this work, we describe Dodona, a system that supports the generation of test oracles. Dodona ranks program variables based on the interactions and dependencies observed between them during program execution. Using this ranking, Dodona proposes a set of variables to be monitored, that can be used by engineers to construct assertion-based oracles. Our empirical study of Dodona reveals that it is more effective and efficient than the current state-of-the-art approach for generating oracle data sets, and can often yield oracles that are almost as effective as oracles hand-crafted by engineers without support.

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.

End users with little formal programming background are creating software in many different forms, including spreadsheets, web macros, and web mashups. Web mashups are particularly popular because they are relatively easy to create, and because many programming environments that support their creation are available. These programming environments, however, provide no support for tracking versions or provenance of mashups. We believe that versioning support can help end users create, understand, and debug mashups. To investigate this belief, we have added versioning support to a popular wire-oriented mashup environment, Yahoo! Pipes. Our enhanced environment, which we call “Pipes Plumber,” automatically retains versions of pipes and provides an interface with which pipe programmers can browse histories of pipes and retrieve specific versions. We have conducted two studies of this environment: an exploratory study and a larger controlled experiment. Our results provide evidence that versioning helps pipe programmers create and debug mashups. Subsequent qualitative results provide further insights into the barriers faced by pipe programmers, the support for reuse provided by our approach, and the support for debugging provided.

Test case prioritization techniques attempt to reorder test cases in a manner that increases the rate at which faults are detected during regression testing. Coverage-based test case prioritization techniques typically use one of two overall strategies: a total strategy or an additional strategy . These strategies prioritize test cases based on the total number of code (or code-related) elements covered per test case and the number of additional (not yet covered) code (or code-related) elements covered per test case, respectively. In this article, we present a unified test case prioritization approach that encompasses both the total and additional strategies. Our unified test case prioritization approach includes two models ( basic and extended ) by which a spectrum of test case prioritization techniques ranging from a purely total to a purely additional technique can be defined by specifying the value of a parameter referred to as the f p value. To evaluate our approach, we performed an empirical study on 28 Java objects and 40 C objects, considering the impact of three internal factors (model type, choice of f p value, and coverage type) and three external factors (coverage granularity, test case granularity, and programming/testing paradigm), all of which can be manipulated by our approach. Our results demonstrate that a wide range of techniques derived from our basic and extended models with uniform f p values can outperform purely total techniques and are competitive with purely additional techniques. Considering the influence of each internal and external factor studied, the results demonstrate that various values of each factor have nontrivial influence on test case prioritization techniques.

Programming for the web can be an intimidating task, particularly for non-professional ("end-user") programmers. Mashup programming environments attempt to remedy this by providing support for such programming. It is well known, however, that mashup programmers create applications that contain bugs. Furthermore, mashup programmers learn from examples and reuse other mashups, which causes bugs to propagate to other mashups. In this paper we classify the bugs that occur in a large corpus of Yahoo! Pipes mashups. We describe support we have implemented in the Yahoo! Pipes environment to provide automatic error detection techniques that help mashup programmers localize and correct these bugs. We present the results of a think-aloud study comparing the experiences of end-user mashup programmers using and not using our support. Our results show that our debugging enhancements do help these programmers localize and correct bugs more effectively and efficiently.

In recent years, researchers have intensively investigated various topics in test-case prioritization, which aims to re-order test cases to increase the rate of fault detection during regression testing. The total and additional prioritization strategies, which prioritize based on total numbers of elements covered per test, and numbers of additional (not-yet-covered) elements covered per test, are two widely-adopted generic strategies used for such prioritization. This paper proposes a basic model and an extended model that unify the total strategy and the additional strategy. Our models yield a spectrum of generic strategies ranging between the total and additional strategies, depending on a parameter referred to as the p value. We also propose four heuristics to obtain differentiated p values for different methods under test. We performed an empirical study on 19 versions of four Java programs to explore our results. Our results demonstrate that wide ranges of strategies in our basic and extended models with uniform p values can significantly outperform both the total and additional strategies. In addition, our results also demonstrate that using differentiated p values for both the basic and extended models with method coverage can even outperform the additional strategy using statement coverage.

When testing multithreaded programs, the number of possible thread interactions makes exploring all interactions infeasible in practice. In response, researchers have developed concurrent coverage metrics for multithreaded programs. These metrics allow them to estimate how well they have exercised concurrent program behavior, just as branch and statement coverage metrics do for sequential program testing. However, unlike sequential coverage metrics, the effectiveness of concurrent coverage metrics in testing remains largely unexamined. In this paper, we explore the relationship between concurrent coverage and fault detection effectiveness by studying the application of eight concurrent coverage metrics in testing nine concurrent programs. Our results show that existing concurrent coverage metrics are often moderate to strong predictors of concurrent testing effectiveness, and are generally reasonable targets for test suite generation. Nevertheless, their relative effectiveness as predictors and test generation targets varies across programs, and thus additional work is needed in this area.

Regression test selection (RTS) techniques attempt to reduce regression testing costs by selecting a subset of a software system's test cases for use in testing changes made to that system. In practice, RTS techniques may select inordinately large sets of test cases, particularly when applied to industrial systems such as those developed at ABB, where code changes may have far-reaching impact. In this paper, we present a new RTS technique that addresses this problem by focusing on specific classes of faults that can be detected by internal oracles - oracles (rules) that enforce constraints on system states during system execution. Our technique uses program chopping to identify code changes that are relevant to internal oracles, and selects test cases that cover these changes. We present the results of an empirical study that show that our technique is more effective and efficient than other RTS techniques, relative to the classes of faults targeted by the internal oracles.

Modern computer systems are prone to various classes of runtime faults due to their reliance on features such as concurrency and peripheral devices such as sensors. Testing remains a common method for uncovering faults in these systems, but many runtime faults are difficult to detect using typical testing oracles that monitor only program output. In this work we empirically investigate the use of internal test oracles: oracles that detect faults by monitoring aspects of internal program and system states. We compare these internal oracles to each other and to output-based oracles for relative effectiveness and examine tradeoffs between oracles involving incorrect reports about faults (false positives and false negatives). Our results reveal several implications that test engineers and researchers should consider when testing for runtime faults.

Faults introduced by races are difficult to detect because they usually occur only under specific execution interleavings. Numerous program analysis and testing techniques have been proposed to detect races between threads. Little work, however, has addressed the problem of detecting and testing for process-level races, in which two processes access a shared resource without proper synchronization. In this paper, we present SIMRACER, a novel testing-based framework that allows engineers to effectively test for process-level races. SIMRACER first computes potential races based on runtime traces obtained by running existing tests on target processes, and then it controls process scheduling relative to the potential races so that real races can be created. We implemented SIMRACER on a commercial virtual platform that is widely used to support hardware/software co-design. We then evaluated its effectiveness on sixteen real-world applications containing known process-level races. Our results show that SIMRACER is effective at detecting process-level races, and more effective than traditional stress testing techniques at detecting faults caused by those races.

Dataflow programming languages, which represent programs as graphs of data streams and operators, are becoming increasingly popular and being used to create a wide array of commercial software applications. The dependability of programs written in these languages, as well as the systems used to compile and run these programs, hinges on the correctness of the semantic properties associated with operators. Unfortunately, these properties are often poorly defined, and frequently are not checked, and this can lead to a wide range of problems in the programs that use the operators. In this paper we present an approach for improving the dependability of dataflow programs by checking operators for necessary properties. Our approach is dynamic, and involves generating tests whose results are checked to determine whether specific properties hold or not. We present empirical data that shows that our approach is both effective and efficient at assessing the status of properties.

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.

Web active end users often coalesce web information using web mashups. Web contents, however, tend to evolve frequently, and along with the black box nature of visual languages this complicates the process of debugging mashups. While debugging, end users need to locate faults within the code and then find a way to correct them; this process requires them to seek information related to web page content and behavior. In this paper, using an information foraging theory lens, we qualitatively study the debugging behaviors of 16 web-active end users. Our results show that the stronger scents available within mashup programming environments can improve users' foraging success. Our results lead to a new model for debugging activities framed in terms of information foraging theory, and to a better understanding of ways in which end-user programming environments can be enhanced to better support debugging.

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.

Most test suite reduction techniques aim to select, from a given test suite, a minimal representative subset of test cases that retains the same code coverage as the suite. Empirical studies have shown, however, that test suites reduced in this manner may lose fault detection capability. Techniques have been proposed to retain certain redundant test cases in the reduced test suite so as to reduce the loss in fault-detection capability, but these still do concede some degree of loss. Thus, these techniques may be applicable only in cases where loose demands are placed on the upper limit of loss in fault-detection capability. In this work we present an on-demand test suite reduction approach, which attempts to select a representative subset satisfying the same test requirements as an initial test suite conceding at most l% loss in fault-detection capability for at least c% of the instances in which it is applied. Our technique collects statistics about loss in fault-detection capability at the level of individual statements and models the problem of test suite reduction as an integer linear programming problem. We have evaluated our approach in the contexts of three scenarios in which it might be used. Our results show that most test suites reduced by our approach satisfy given fault detection capability demands, and that the approach compares favorably with an existing test suite reduction approach.

Although testing is a standard method for improving the quality of software, conventional testing methods often fail to detect faults. Concolic testing attempts to remedy this by automatically generating test cases to explore execution paths in a program under test, helping testers achieve greater coverage of program behavior in a more automated fashion. Concolic testing, however, consumes a significant amount of computing time to explore execution paths, which is an obstacle toward its practical application. To address this limitation, we have developed a scalable distributed concolic testing framework that utilizes large numbers of computing nodes to generate test cases in a scalable manner. In this paper, we present the results of an empirical study that shows that the proposed framework can achieve a several orders-of-magnitude increase in test case generation speed compared to the original concolic approach, and also demonstrates clear potential for scalability.

Many software systems rely on graphical-user interfaces (GUIs) to support user interactions. The correctness of these GUIs affects the overall quality of the systems, and thus, it is important that GUIs be tested. To support such testing, GUI test case generation techniques based on graph models such as event flow graphs (EFGs) have been used to generate test cases in the form of sequences of events. Models, however, are abstractions of dynamic behavior and may not accurately reflect actual system behavior, thus, test case generation techniques based on models may create nonexecutable test cases and miss important events. Test case generation techniques based on dynamic event extraction-based approaches, in contrast, may suffer less from these effects. As a consequence, we expect that the two approaches will differ in terms of cost and effectiveness. In this paper, we report the results of an empirical study comparing the cost and effectiveness of model-based and dynamic event extraction-based test case generation approaches. Our results show that event extraction-based approaches, though more expensive than model-based approaches, are indeed more effective in terms of their ability to achieve code coverage and to cover events, but at additional cost, with implications for both researchers and practitioners.

Recent work in testing has demonstrated the benefits of considering test oracles in the testing process. Unfortunately, this work has focused primarily on developing techniques for generating test oracles, in particular techniques based on mutation testing. While effective for test case generation, existing research has not considered the impact of test oracles in the context of regression testing tasks. Of interest here is the problem of test case prioritization, in which a set of test cases are ordered to attempt to detect faults earlier and to improve the effectiveness of testing when the entire set cannot be executed. In this work, we propose a technique for prioritizing test cases that explicitly takes into account the impact of test oracles on the effectiveness of testing. Our technique operates by first capturing the flow of information from variable assignments to test oracles for each test case, and then prioritizing to ``cover'' variables using the shortest paths possible to a test oracle. As a result, we favor test orderings in which many variables impact the test oracle's result early in test execution. Our results demonstrate improvements in rate of fault detection relative to both random and structural coverage based prioritization techniques when applied to faulty versions of three synchronous reactive systems.

Recently, work has begun on automating the generation of test oracles, which are necessary to fully automate the testing process. One approach to such automation involves dynamic invariant generation which extracts invariants from program executions. To use such invariants as test oracles, however, it is necessary to distinguish correct from incorrect invariants, a process that currently requires human intervention. In this work we examine this process. In particular, we examine the ability of 30 users, across two empirical studies, to classify invariants generated from three Java programs. Our results indicate that users struggle to classify generated invariants: on average, they misclassify 9.1% to 31.7% of correct invariants and 26.1%-58.6% of incorrect invariants. These results contradict prior studies that suggest that classification by users is easy, and indicate that further work needs to be done to bridge the gap between the effectiveness of dynamic invariant generation in theory, and the ability of users to apply it in practice. Along these lines, we suggest several areas for future work.

In software for embedded systems, the frequent use of interrupts for timing, sensing, and I/O processing can cause concurrency faults to occur due to interactions between applications, device drivers, and interrupt handlers. This type of fault is considered by many practitioners to be among the most difficult to detect, isolate, and correct, in part because it can be sensitive to execution interleavings and often occurs without leaving any observable incorrect output. As such, commonly used testing techniques that inspect program outputs to detect failures are often ineffective at detecting them. To test for these concurrency faults, test engineers need to be able to control interleavings so that they are deterministic. Furthermore, they also need to be able to observe faults as they occur instead of relying on observable incorrect outputs.

Test case prioritization is used in regression testing to schedule the execution order of test cases so as to expose faults earlier in testing. Over the past few years, many test case prioritization techniques have been proposed in the literature. Most of these techniques require data on dynamic execution in the form of code coverage information for test cases. However, the collection of dynamic code coverage information on test cases has several associated drawbacks including cost increases and reduction in prioritization precision. In this paper, we propose an approach to prioritizing test cases in the absence of coverage information that operates on Java programs tested under the JUnit framework-an increasingly popular class of systems. Our approach, JUnit test case Prioritization Techniques operating in the Absence of coverage information (JUPTA), analyzes the static call graphs of JUnit test cases and the program under test to estimate the ability of each test case to achieve code coverage, and then schedules the order of these test cases based on those estimates. To evaluate the effectiveness of JUPTA, we conducted an empirical study on 19 versions of four Java programs ranging from 2K-80K lines of code, and compared several variants of JUPTA with three control techniques, and several other existing dynamic coverage-based test case prioritization techniques, assessing the abilities of the techniques to increase the rate of fault detection of test suites. Our results show that the test suites constructed by JUPTA are more effective than those in random and untreated test orders in terms of fault-detection effectiveness. Although the test suites constructed by dynamic coverage-based techniques retain fault-detection effectiveness advantages, the fault-detection effectiveness of the test suites constructed by JUPTA is close to that of the test suites constructed by those techniques, and the fault-detection effectiveness of the test suites constructed by some of JUPTA's variants is better than that of the test suites constructed by several of those techniques.

Embedded systems are becoming increasingly ubiquitous, controlling a wide variety of popular and safety-critical devices. Effective testing techniques could improve the dependability of these systems. In prior work we presented an approach for testing embedded systems, focusing on embedded system applications and the tasks that comprise them. In this work we focus on a second but equally important aspect of testing embedded systems, namely, the need to provide observability of system behavior sufficient to allow engineers to detect failures. We present several property-based oracles that can be instantiated in embedded systems through program analysis and instrumentation, and can detect failures for which simple output-based oracles are inadequate. An empirical study of our approach shows that it can be effective.

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. In previous work, we studied two approaches to augmentation, one using a concolic test case generation algorithm and one using a genetic test case generation algorithm. We found that these two approaches behaved quite differently in terms of their costs and their abilities to generate effective test cases for evolving programs. In this paper, we present a hybrid test suite augmentation technique that combines these two test case generation algorithms. We report the results of an empirical study that shows that this hybrid technique can be effective, but with varying degrees of costs, and we analyze our results further to provide suggestions for reducing costs.

Web mashup environments provide a way for users to combine data from web applications and services to create new content. Currently, these environments do not provide support for tracking the development histories of mashups. We have thus added configuration management support to the Yahoo! Pipes mashup environment. We describe this support, and provide results of an experiment studying the ability of programmers to create and debug mashups in its presence. Our results show that versioning support can help both groups of users do both tasks better.

Real-time embedded systems (RTESs) are becoming increasingly ubiquitous, controlling a wide variety of popular and safety-critical devices. Effective testing techniques could improve the dependability of these systems. In this paper we present an approach for testing RTESs, intended specifically to help RTES application developers detect faults related to functional correctness. Our approach consists of two techniques that focus on exercising the interactions between system layers and between the multiple user tasks that enact application behaviors. We present results of an empirical study that shows that our techniques are effective at detecting faults.

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.

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.

Regression testing is an expensive process used to validate modified software. Test case prioritization techniques improve the cost-effectiveness of regression testing by ordering test cases such that those that are more important are run earlier in the testing process. Many prioritization techniques have been proposed and evidence shows that they can be beneficial. It has been suggested, however, that the time constraints that can be imposed on regression testing by various software development processes can strongly affect the behavior of prioritization techniques. If this is correct, a better understanding of the effects of time constraints could lead to improved prioritization techniques and improved maintenance and testing processes. We therefore conducted a series of experiments to assess the effects of time constraints on the costs and benefits of prioritization techniques. Our first experiment manipulates time constraint levels and shows that time constraints do play a significant role in determining both the cost-effectiveness of prioritization and the relative cost-benefit trade-offs among techniques. Our second experiment replicates the first experiment, controlling for several threats to validity including numbers of faults present, and shows that the results generalize to this wider context. Our third experiment manipulates the number of faults present in programs to examine the effects of faultiness levels on prioritization and shows that faultiness level affects the relative cost-effectiveness of prioritization techniques. Taken together, these results have several implications for test engineers wishing to cost-effectively regression test their software systems. These include suggestions about when and when not to prioritize, what techniques to employ, and how differences in testing processes may relate to prioritization cost--effectiveness.

As software evolves, engineers use regression testing to evaluate its fitness for release. Such testing typically begins with existing test cases, and many techniques have been proposed for reusing these cost-effectively. After reusing test cases, however, it is also important to consider code or behavior that has not been exercised by existing test cases and generate new test cases to validate these. This process is known as test suite augmentation. In this paper we present a directed test suite augmentation technique, that utilizes results from reuse of existing test cases together with an incremental concolic testing algorithm to augment test suites so that they are coverage-adequate for a modified program. We present results of an empirical study examining the effectiveness of our approach.

Model checking is a promising technique for verifying program behavior and is increasingly finding usage in industry. To date, however, researchers have primarily considered model checking of single versions of programs. It is well understood that model checking can be very expensive for large, complex programs. Thus, simply reapplying model checking techniques on subsequent versions of programs as they evolve, in the limited time that is typically available for validating new releases, presents challenges. To address these challenges, we have developed a new technique for regression model checking (RMC), that applies model checking incrementally to new versions of systems. We report results of an empirical study examining the effectiveness of our technique; our results show that it is significantly faster than traditional model checking.

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.

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.

A wide range of techniques for supporting software maintenance tasks rely on representations of program control flow. The accuracy of these representations can be important to the effectiveness and efficiency of these techniques. The Java programming language has introduced structured exception handling features that complicate the task of representing control flow. Previous work has attempted to address these complications by using type inference algorithms to analyze the control flow effects of exceptions, but to date, there has been no study of whether the use of these algorithms is justified. In this paper we report results of an empirical study addressing this issue. We find that type inference algorithms can lead to more accurate representations of control flow, but this improvement does not necessarily translate into benefits for maintenance techniques that use them. It follows that type inference algorithms should not just automatically be applied; rather, the tradeoffs of applying them must first be assessed with respect to particular maintenance techniques and workloads.

Software engineering methodologies are subject to complex cost-benefit tradeoffs. Economic models can help practitioners and researchers assess methodologies relative to these tradeoffs. Effective economic models, however, can be established only through an iterative process of refinement involving analytical and empirical methods. Sensitivity analysis provides one such method. By identifying the factors that are most important to models, sensitivity analysis can help simplify those models; it can also identify factors that must be measured with care, leading to guidelines for better test strategy definition and application. In prior work we presented the first comprehensive economic model for the regression testing process, that captures both cost and benefit factors relevant to that process while supporting evaluation of these processes across entire system lifetimes. In this work we use sensitivity analysis to examine our model analytically and assess the factors that are most important to the model. Based on the results of that analysis, we propose two new models of increasing simplicity. We assess these models empirically on data obtained by using regression testing techniques on several non-trivial software systems. Our results show that one of the simplified models assesses the relationships between techniques in the same way as the full model.

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.

Regression testing is an expensive process used to validate modified software. Test case prioritization techniques improve the cost-effectiveness of regression testing by ordering test cases such that those that are more important are run earlier in the testing process. Many prioritization techniques have been proposed and evidence shows that they can be beneficial. It has been suggested, however, that the time constraints that can be imposed on regression testing by various software development processes can strongly affect the behavior of prioritization techniques. Therefore, we conducted an experiment to assess the effects of time constraints on the costs and benefits of prioritization techniques. Our results show that time constraints can indeed play a significant role in determining both the cost-effectiveness of prioritization, and the relative cost-benefit tradeoffs among techniques, with important implications for the use of prioritization in practice.

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.

While much of the software that people depend on is written by professional software engineers, increasingly, important applications are being created by non-professional (end-user) programmers. Using tools such as spreadsheet environments and web authoring tools, these programmers are creating software that is being used to support significant activities and inform decisions. Such software needs to work dependably and increase user productivity, but evidence shows that it frequently does not. For example, studies have shown that a large percentage of the spreadsheets created by end-users contain faults, and data suggests that time spent maintaining web macros may actually impede their users' overall efforts. In recent years researchers have begun to address this problem, considering various approaches to adapting software engineering techniques to the realm of end-user programming. For example, researchers have sought ways to help end users test and debug spreadsheets, and to increase productivity in web macros by combining them with various software engineering devices. To make progress in this area, researchers are turning to empirical studies, in order to investigate new approaches, understand the factors that influence them, and better understand issues related to end user programmers themselves. In this talk I will present recent work being done in end-user software engineering, with a particular focus on the state of the art of empirical research in the area. I will show that there is a pressing need for further empirical work in this context, and that there are interesting questions that researchers from the ESEM community could help to answer. For example, how are end-users different from programmers, and how does that affect how we conduct the research? (Are there assumptions we make when doing studies with programmers that do not hold with end-users? What are the threats to validity when, say, we use CS students as subjects in end-user studies?) As another example, how are end-users different from each other and how does that affect study results? (The end-user community is much more diverse than the professional programmer community. What are the important context variables one needs to capture when studying them?) A concerted effort by the ESEM community on such issues could result in a substantial impact on society as a whole, and on the everyday lives of many people.

Abstract Increasingly, modern‐day software systems are being built by combining externally‐developed software components with application‐specific code. For such systems, existing program‐analysis‐based software engineering techniques may not directly apply, due to lack of information about components. To address this problem, the use of component metadata has been proposed. Component metadata are metadata and metamethods provided with components, that retrieve or calculate information about those components. In particular, two component‐metadata‐based approaches for regression test selection are described: one using code‐based component metadata and the other using specification‐based component metadata. The results of empirical studies that illustrate the potential of these techniques to provide savings in re‐testing effort are provided. Copyright © 2006 John Wiley & Sons, Ltd.

Spreadsheets are widely used but often contain faults. Thus, in prior work we presented a dataflow testing methodology for use with spreadsheets, which studies have shown can be used cost-effectively by end-user programmers. To date, however, the methodology has been investigated across a limited set of spreadsheet language features. Commercial spreadsheet environments are multiparadigm languages, utilizing features not accommodated by our prior approaches. In addition, most spreadsheets contain large numbers of replicated formulas that severely limit the efficiency of dataflow testing approaches. We show how to handle these two issues with a new dataflow adequacy criterion and automated detection of areas of replicated formulas, and report results of a controlled experiment investigating the feasibility of our approach

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.

Regression testing is an important but expensive activity, and a great deal of research on regression testing methodologies has been performed. In recent years, much of this research has emphasized empirical studies, including evaluations of the effectiveness and efficiency of regression testing techniques. To date, however, most studies have been limited in terms of their consideration of testing context and system lifetime, and have used cost-benefit models that omit important factors and render some types of comparisons between techniques impossible. These limitations can cause studies to improperly assess the costs and benefits of regression testing techniques in practical settings. In this paper, we provide improved cost-benefit models for use in assessing regression testing methodologies, that incorporate context and lifetime factors not considered in prior studies, and we use these models to compare several common methodologies. Our results show that the factors we consider (in particular, time constraints and incremental resource availability) can affect assessments of the relative benefits of regression testing techniques, and suggest that particular classes of techniques may compare differently across different types of test suites.

Spreadsheet languages, which include commercial spreadsheets and various research systems, have had a substantial impact on end-user computing. Research shows, however, that spreadsheets often contain faults. Thus, in previous work we presented a methodology that helps spreadsheet users test their spreadsheet formulas. Our empirical studies have shown that end users can use this methodology to test spreadsheets more adequately and efficiently; however, the process of generating test cases can still present a significant impediment. To address this problem, we have been investigating how to incorporate automated test case generation into our testing methodology in ways that support incremental testing and provide immediate visual feedback. We have used two techniques for generating test cases, one involving random selection and one involving a goal-oriented approach. We describe these techniques and their integration into our testing environment, and report results of an experiment examining their effectiveness and efficiency.

Regression testing is an important activity in the software life cycle, but it can also be very expensive. 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 test case prioritization techniques is to increase a test suite's rate of fault detection (how quickly, in a run of its test cases, that test suite can detect faults). Previous work has shown that prioritization can improve a test suite's rate of fault detection, but the assessment of prioritization techniques has been limited primarily to hand-seeded faults, largely due to the belief that such faults are more realistic than automatically generated (mutation) faults. A recent empirical study, however, suggests that mutation faults can be representative of real faults and that the use of hand-seeded faults can be problematic for the validity of empirical results focusing on fault detection. We have therefore designed and performed two controlled experiments assessing the ability of prioritization techniques to improve the rate of fault detection of test case prioritization techniques, measured relative to mutation faults. Our results show that prioritization can be effective relative to the faults considered, and they expose ways in which that effectiveness can vary with characteristics of faults and test suites. More importantly, a comparison of our results with those collected using hand-seeded faults reveals several implications for researchers performing empirical studies of test case prioritization techniques in particular and testing techniques in general.

End-user programmers develop more software than any other group of programmers, using software authoring devices such as multimedia simulation builders, e-mail filtering editors, by-demonstration macro builders, and spreadsheet environments. Despite this, there has been only a little research on finding ways to help these programmers with the dependability of the software they create. We have been working to address this problem in several ways, one of which includes supporting end-user debugging activities through interactive fault localization techniques. This paper investigates fault localization techniques in the spreadsheet domain, the most common type of end-user programming environment. We investigate a technique previously described in the research literature and two new techniques. We present the results of an empirical study to examine the impact of two individual factors on the effectiveness of fault localization techniques. Our results reveal several insights into the contributions such techniques can make to the end-user debugging process and highlight key issues of interest to researchers and practitioners who may design and evaluate future fault localization techniques.

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

End users develop more software than any other group of programmers, using software authoring devices such as e-mail filtering editors, by-demonstration macro builders, and spreadsheet environments. Despite this, there has been little research on finding ways to help these programmers with the dependability of their software. We have been addressing this problem in several ways, one of which includes supporting end-user debugging activities through fault localization techniques. This paper presents the results of an empirical study conducted in an end-user programming environment to examine the impact of two separate factors in fault localization techniques that affect technique effectiveness. Our results shed new insights into fault localization techniques for end-user programmers and the factors that affect them, with significant implications for the evaluation of those techniques.

Regression testing is an important part of software maintenance, but it can also be very expensive. To reduce this expense, software testers may prioritize their test cases so that those that are more important are run earlier in the regression testing process. Previous work has shown that prioritization can improve a test suite's rate of fault detection, but the assessment of prioritization techniques has been limited to hand-seeded faults, primarily due to the belief that such faults are more realistic than automatically generated (mutation) faults. A recent empirical study, however, suggests that mutation faults can be representative of real faults. We have therefore designed and performed a controlled experiment to assess the ability of prioritization techniques to improve the rate of fault detection techniques, measured relative to mutation faults. Our results show that prioritization can be effective relative to the faults considered, and they expose ways in which that effectiveness can vary with characteristics of faults and test suites. We also compare our results to those collected earlier with respect to the relationship between hand-seeded faults and mutation faults, and the implications this has for researchers performing empirical studies of prioritization.

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.

Despite years of availability of testing tools, professional software developers still seem to need better support to determine the effectiveness of their tests. Without improvements in this area, inadequate testing of software seems likely to remain a major problem. To address this problem, industry and researchers have proposed systems that visualize "testedness" for end-user and professional developers. Empirical studies of such systems for end-user programmers have begun to show success at helping end users write more effective tests. Encouraged by this research, we examined the effect that code coverage visualizations have on the effectiveness of test cases that professional software developers write. This paper presents the results of an empirical study conducted using code coverage visualizations found in a commercially available programming environment. Our results reveal how this kind of code coverage visualization impacts test effectiveness, and provide insights into the strategies developers use to test code.

Regression testing is an expensive process used to revalidate modified software. Regression test selection (RTS) techniques reduce the cost of regression testing by selecting a subset of a test suite. Many RTS techniques have been proposed, and studies have shown that they produce savings; other studies have shown that their cost-effectiveness varies with characteristics of the workloads to which they are applied. It seems plausible, however, that another factor that impacts RTS techniques involves the process by which they are applied. In particular, issues such as the frequency with which regression testing is performed affect the techniques. Thus, in earlier work an experiment was conducted to assess the effects of test application frequency on the cost-effectiveness of RTS techniques. The results exposed tradeoffs to consider when using these techniques over a series of releases. This work, however, was limited in external validity; in particular, the programs studied were relatively small. Thus, the previous experiment has been replicated on a large, multi-version program. This second experiment confirms the findings of the first. In particular, the cost of using safe RTS techniques was strongly and negatively affected by testing interval. Conversely, the effectiveness of minimization RTS techniques was strongly and positively affected. Copyright © 2005 John Wiley & Sons, Ltd.

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.

The International Symposium on Software Testing and Analysis (ISSTA) is the leading research conference in software testing and analysis. ISSTA brings together academics, industrial researchers, and practitioners to present and discuss the most promising approaches for using testing and analysis to assess and improve software and the processes by which it is engineered. ISSTA 2004 was held in at the Parker House Hotel in Boston, Massachusetts, July 11-14, 2004. On this occasion the conference was co-located with the 16th Computer- Aided Verification Conference (CAV 2004), with the two conferences sharing a day of sessions. The conference was also preceded by two workshops: the Workshop on Testing, Analysis, and Verification of Web Services and the Workshop on Empirical Research in Software Testing. The number of submitted papers to ISSTA, and the ratio of that number to accepted papers, are a good indication of ISSTA’s health as a conference, and technical reputation. For ISSTA 2004, 93 research papers (a near record) and eight tools papers were submitted. Submissions were reviewed by at least three reviewers and discussed in a Program Committee meeting. The result was a high-quality technical program with 26 research papers and two tools papers. This issue of IEEE Transactions on Software Engineering presents a special section containing papers based on five of the best papers of ISSTA 2004. These papers were part of a set of seven papers selected by the ISSTA Program Committee from among the papers presented at the conference. The selected set, following revisions and enhancements by the authors, went through the standard TSE review process involving at least three anonymous reviewers per paper, overseen by myself as guest editor (or in one case on a paper on which I had a conflict, by John Knight). The result is a selection of five excellent papers.

Impact analysis - determining the potential effects of changes on a software system - plays an important role in software engineering tasks such as maintenance, regression testing, and debugging. In previous work, two new dynamic impact analysis techniques, CoverageImpact and PathImpact, were presented. These techniques perform impact analysis based on data gathered about program behavior relative to specific inputs, such as inputs gathered from field data, operational profile data, or test-suite executions. Due to various characteristics of the algorithms they employ, CoverageImpact and PathImpact are expected to differ in terms of cost and precision; however, there have been no studies to date examining the extent to which such differences may emerge in practice. Since cost-precision tradeoffs may play an important role in technique selection and further research, we wished to examine these tradeoffs. We therefore designed and performed an empirical study, comparing the execution and space costs of the techniques, as well as the precisions of the impact analysis results that they report. This paper presents the results of this study.

Test case prioritization provides a way to run test cases with the highest priority earliest. Numerous empirical studies have shown that prioritization can improve a test suite's rate of fault detection, but the extent to which these results generalize is an open question because the studies have all focused on a single procedural language, C, and a few specific types of test suites, in particular, Java and the JUnit testing framework are being used extensively in practice, and the effectiveness of prioritization techniques on Java systems tested under JUnit has not been investigated. We have therefore designed and performed a controlled experiment examining whether test case prioritization can be effective on Java programs tested under JUnit, and comparing the results to those achieved in earlier studies. Our analyses show that test case prioritization can significantly improve the rate of fault detection of JUnit test suites, but also reveal differences with respect to previous studies that can be related to the language and testing paradigm.

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.

Despite their ability to help with program correctness, assertions have been notoriously unpopular---even with professional programmers. End-user programmers seem even less likely to appreciate the value of assertions; yet end-user programs suffer from serious correctness problems that assertions could help detect. This leads to the following question: can end users be enticed to enter assertions? To investigate this question, we have devised a curiosity-centered approach to eliciting assertions from end users, built on a surprise-explain-reward strategy. Our follow-up work with end-user participants shows that the approach is effective in encouraging end users to enter assertions that help them find errors.

There has been little research on end-user program development beyond the activity of programming. Devising ways to address additional activities related to end-user program development may be critical, however, because research shows that a large proportion of the programs written by end users contain faults. Toward this end, we have been working on ways to provide formal "software engineering" methodologies to end-user programmers. This paper describes an approach we have developed for supporting assertions in end-user software, focusing on the spreadsheet paradigm. We also report the results of a controlled experiment, with 59 end-user subjects, to investigate the usefulness of this approach. Our results show that the end users were able to use the assertions to reason about their spreadsheets, and that doing so was tied to both greater correctness and greater efficiency.

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.

Impact analysis, determining when a change in one part of a program affects other parts of the program, is time-consuming and problematic. Impact analysis is rarely used to predict the effects of a change, leaving maintainers to deal with consequences rather than working to a plan. Previous approaches to impact analysis involving analysis of call graphs, and static and dynamic slicing, exhibit several tradeoffs involving computational expense, precision, and safety, require access to source code, and require a relatively large amount of effort to re-apply as software evolves. This paper presents a new technique for impact analysis based on whole path profiling, that provides a different set of cost-benefits tradeoffs - a set which can potentially be beneficial for an important class of predictive impact analysis tasks. The paper presents the results of experiments that show that the technique can predict impact sets that are more accurate than those computed by call graph analysis, and more precise (relative to the behavior expressed in a program's profile) than those computed by static slicing.

Impact analysis - determining the potential effects of changes on a software system - plays an important role in helping engineers revalidate modified software. In previous work we presented a new impact analysis technique. PathImpact, for performing dynamic impact analysis at the level of procedures, and we showed empirically that the technique can be cost-effective in comparison to prominent prior techniques. A drawback of that approach as presented, however, is that when attempting to apply the technique to a new version of a system as that system and its test suite evolves, the process of recomputing the data required by the technique for that version can be excessively expensive. In this paper, therefore, we present algorithms that allow the data needed by PathImpact to be collected incrementally. We present the results of a controlled experiment investigating the costs and benefits of this incremental approach relative to the approach of completely recomputing prerequisite data.

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.

Spreadsheet languages, which include commercial spreadsheets and various research systems, have had a substantial impact on end-user computing. Research shows, however, that spreadsheets often contain faults. Thus, in previous work, we presented a methodology that assists spreadsheet users in testing their spreadsheet formulas. Our empirical studies have shown that this methodology can help end-users test spreadsheets more adequately and efficiently; however, the process of generating test cases can still represent a significant impediment. To address this problem, we have been investigating how to automate test case generation for spreadsheets in ways that support incremental testing and provide immediate visual feedback. We have utilized two techniques for generating test cases, one involving random selection and one involving a goal-oriented approach. We describe these techniques, and report results of an experiment examining their relative costs and benefits.

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.

Spreadsheet languages are widely used by a variety of end users to perform many important tasks. Despite their perceived simplicity, spreadsheets often contain faults. Furthermore, users modify their spreadsheets frequently, which can render previously correct spreadsheets faulty. To address this problem, we previously introduced a visual approach by which users can systematically test their spreadsheets, see where new tests are required after changes, and request automated generation of potentially useful test inputs. To date, however, this approach has not taken advantage of previously developed test cases, which means that users of the approach cannot benefit, when re-testing following changes, from prior testing efforts. We have therefore been investigating ways to add support for test re-use into our spreadsheet testing methodology. In this paper we present a test re-use strategy for spreadsheets, and the algorithms that implement it, and describe their integration into our spreadsheet testing methodology. We report results of a case study examining the application of this strategy.

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.

Abstract Test‐suite reduction techniques attempt to reduce the costs of saving and reusing test cases during software maintenance by eliminating redundant test cases from test suites. A potential drawback of these techniques is that reducing the size of a test suite might reduce its ability to reveal faults in the software. Previous studies have suggested that test‐suite reduction techniques can reduce test‐suite size without significantly reducing the fault‐detection capabilities of test suites. These studies, however, involved particular programs and types of test suites, and to begin to generalize their results, further work is needed. This paper reports on the design and execution of additional studies, examining the costs and benefits of test‐suite reduction, and the factors that influence these costs and benefits. In contrast to previous studies, results of these studies reveal that the fault‐detection capabilities of test suites can be severely compromised by test‐suite reduction. Copyright © 2002 John Wiley & Sons, Ltd.

Although there has been recent research into ways to design environments that enable end users to create their own programs, little attention has been given to helping these end users systematically test their programs. To help address this need in spreadsheet systems (the most widely used type of end-user programming language), we previously introduced a visual approach to systematically testing individual cells in spreadsheet systems. However, the previous approach did not scale well in the presence of largely homogeneous grids, which introduce problems somewhat analogous to the array-testing problems of imperative programs. We present two approaches to spreadsheet testing that explicitly support such grids. We present the algorithms, time complexities, and performance data comparing the two approaches. This is part of our continuing work to bring to end users at least some of the benefits of formalized notions of testing without requiring knowledge of testing beyond a naive level.

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.

Spreadsheets are among the most common form of software in use today. Unlike more traditional forms of software however, spreadsheets are created and maintained by end users with little or no programming experience. As a result, a high percentage of these "programs" contain errors. Unfortunately, software engineering research has for the most part ignored this problem. We have developed a methodology that is designed to aid end users in developing, testing, and maintaining spreadsheets. The methodology communicates testing information and information about the impact of cell changes to users in a manner that does not require an understanding of formal testing theory or the behind the scenes mechanisms. The paper presents the results of an empirical study that shows that, during maintenance, end users using our methodology were more accurate in making changes and did a significantly better job of validating their spreadsheets than end users without the methodology.

Component based software technologies are viewed as essential for creating the software systems of the future. However, the use of externally-provided components has serious drawbacks for a wide range of software engineering activities, often because of a lack of information about the components. Previously (A. Orso et al., 2000), we proposed the use of component metacontents: additional data and methods provided with a component, to support software engineering tasks. The authors present two new metacontent based techniques that address the problem of regression test selection for component based applications: a code based approach and a specification based approach. First, we illustrate the two techniques. Then, we present a case study that applies the code based technique to a real component based system. On the system studied, on average, 26% of the overall testing effort was saved over seven releases, with a maximum savings of 99% for one version.

Regression test-selection techniques reduce the cost of regression testing by selecting a subset of an existing test suite to use in retesting a modified program. Over the past two decades, numerous regression test-selection techniques have been described in the literature. Initial empirical studies of some of these techniques have suggested that they can indeed benefit testers, but so far, few studies have empirically compared different techniques. In this paper, we present the results of a comparative empirical study of two safe regression test-selection techniques. The techniques we studied have been implemented as the tools DejaVu and TestTube; we compared these tools in terms of a cost model incorporating precision (ability to eliminate unnecessary test cases), analysis cost , and test execution cost . Our results indicate, that in many instances, despite its relative lack of precision, TestTube can reduce the time required for regression testing as much as the more precise DejaVu. In other instances, particularly where the time required to execute test cases is long, DejaVu's superior precision gives it a clear advantage over TestTube. Such variations in relative performance can complicate a tester's choice of which tool to use. Our experimental results suggest that a hybrid regression test-selection tool that combines features of TestTube and DejaVu may be an answer to these complications; we present an initial case study that demonstrates the potential benefit of such a tool.

Regression testing is the process of validating modified software to detect whether new errors have been introduced into previously tested code and to provide confidence that modifications are correct. Since regression testing is an expensive process, researchers have proposed regression test selection techniques as a way to reduce some of this expense. These techniques attempt to reduce costs by selecting and running only a subset of the test cases in a program's existing test suite. Although there have been some analytical and empirical evaluations of individual techniques, to our knowledge only one comparative study, focusing on one aspect of two of these techniques, has been reported in the literature. We conducted an experiment to examine the relative costs and benefits of several regression test selection techniques. The experiment examined five techniques for reusing test cases, focusing on their relative ablilities to reduce regression testing effort and uncover faults in modified programs. Our results highlight several differences between the techiques, and expose essential trade-offs that should be considered when choosing a technique for practical application.

Spreadsheet languages, which include commercial spreadsheets and various research systems, have had a substantial impact on end-user computing. Research shows, however, that spreadsheets often contain faults; thus, we would like to provide at least some of the benefits of formal testing methodologies to the creators of spreadsheets. This article presents a testing methodology that adapts data flow adequacy criteria and coverage monitoring to the task of testing spreadsheets. To accommodate the evaluation model used with spreadsheets, and the interactive process by which they are created, our methodology is incremental. To accommodate the users of spreadsheet languages, we provide an interface to our methodology that does not require an understanding of testing theory. We have implemented our testing methodology in the context of the Forms/3 visual spreadsheet language. We report on the methodology, its time and space costs, and the mapping from the testing strategy to the user interface. In an empirical study, we found that test suites created according to our methodology detected, on average, 81% of the faults in a set of faulty spreadsheets, significantly outperforming randomly generated test suites.

Program-dependence information is useful for a variety of applications, such as software testing and maintenance tasks, and code optimization. Properly defined, control and data dependences can be used to identify semantic dependences. To function effectively on whole programs, tools that utilize dependence information require information about interprocedural dependences: dependences that are identified by analyzing the interactions among procedures. Many techniques for computing interprocedural data dependences exist; however, virtually no attention has been paid to interprocedural control dependence. Analysis techniques that fail to account for interprocedural control dependences can suffer unnecessary imprecision and loss of safety. This article presents a definition of interprocedural control dependence that supports the relationship of control and data dependence to semantic dependence. The article presents two approaches for computing interprocedural control dependences, and empirical results pertaining to teh use of those approaches.

Regression testing is an important activity that can account for a large proportion of the cost of software maintenance. One approach to reducing the cost of regression testing is to employ a selective regression testing technique that: chooses a subset of a test suite that was used to test the software before the modifications; then uses this subset to test the modified software. Selective regression testing techniques reduce the cost of regression testing if the cost of selecting the subset from the test suite together with the cost of running the selected subset of test cases is less than the cost of rerunning the entire test suite. Rosenblum and Weyuker (1997) proposed coverage-based predictors for use in predicting the effectiveness of regression test selection strategies. Using the regression testing cost model of Leung and White (1989; 1990), Rosenblum and Weyuker demonstrated the applicability of these predictors by performing a case study involving 31 versions of the KornShell. To further investigate the applicability of the Rosenblum-Weyuker (RW) predictor, additional empirical studies have been performed. The RW predictor was applied to a number of subjects, using two different selective regression testing tools, Deja vu and TestTube. These studies support two conclusions. First, they show that there is some variability in the success with which the predictors work and second, they suggest that these results can be improved by incorporating information about the distribution of modifications. It is shown how the RW prediction model can be improved to provide such an accounting.

Test case prioritization techniques schedule test cases for execution in an order that attempts to increase their effectiveness at meeting some performance goal. Various goals are possible; one involves rate of fault detection, a measure of how quickly faults are detected within the testing process. An improved rate of fault detection during testing can provide faster feedback on the system under test and let software engineers begin correcting faults earlier than might otherwise be possible. One application of prioritization techniques involves regression testing, the retesting of software following modifications; in this context, prioritization techniques can take advantage of information gathered about the previous execution of test cases to obtain test case orderings. We describe several techniques for using test execution information to prioritize test cases for regression testing, including: 1) techniques that order test cases based on their total coverage of code components; 2) techniques that order test cases based on their coverage of code components not previously covered; and 3) techniques that order test cases based on their estimated ability to reveal faults in the code components that they cover. We report the results of several experiments in which we applied these techniques to various test suites for various programs and measured the rates of fault detection achieved by the prioritized test suites, comparing those rates to the rates achieved by untreated, randomly ordered, and optimally ordered suites.

Regression testing is an expensive maintenance process used to revalidate modified software. Regression test selection (RTS) techniques try to lower the cost of regression testing by selecting and running a subset of the existing test cases. Many such techniques have been proposed and initial studies show that they can produce savings. We believe, however, that issues such as the frequency with which testing is done have a strong effect on the behavior of these techniques. Therefore, we conducted an experiment to assess the effects of test application frequency on the costs and benefits of regression test selection techniques. Our results expose essential tradeoffs that should be considered when using these techniques over a series of software releases.

Is it possible to achieve some of the benefits of formal testing within the informal programming conventions of the spreadsheet paradigm? We have been working on an approach that attempts to do so via the development of a testing methodology for this paradigm. Our “What You See Is What You Test” (WYSIWYT) methodology supplements the convention by which spreadsheets provide automatic immediate visual feedback about values by providing automatic immediate visual feedback about “testedness”. In previous work we described this methodology; in this paper, we present empirical data about the methodology's effectiveness. Our results show that the use of the methodology was associated with significant improvement in testing effectiveness and efficiency even with no training on the theory of testing or test adequacy that the model implements. These results may be due at least in part to the fact that use of the methodology was associated with a significant reduction in overconfidence.

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.

Many software maintenance and testing tasks involve comparing the behaviours of program versions. Program spectra have recently been proposed as a heuristic for use in performing such comparisons. To assess the potential usefulness of spectra in this context an experiment was conducted, examining the relationship between differences in program spectra and the exposure of regression faults (faults existing in a modified version of a program that were not present prior to modifications, or not revealed in previous testing), and empirically comparing several types of spectra. The results reveal that certain types of spectra differences correlate with high frequency—at least in one direction—with the exposure of regression faults. That is, when regression faults are revealed by particular inputs, spectra differences are likely also to be revealed by those inputs, though the reverse is not true. The results also suggest that several types of spectra that appear, analytically, to offer greater precision in predicting the presence of regression faults than other, cheaper, spectra may provide no greater precision in practice. These results have ramifications for future research on, and for the practical uses of, program spectra. Copyright © 2000 John Wiley & Sons, Ltd.

Regression testing is an important but expensive software maintenance activity performed with the aim of providing confidence in modified software. Regression test selection techniques reduce the cost of regression testing by selecting test cases for a modified program from a previously existing test suite. Many researchers have addressed the regression test selection problem for procedural language software, but few have addressed the problem for object-oriented software. This paper presents a regression test selection technique for use with object-oriented software. The technique constructs graph representations for software, and uses these graphs to select test cases, from the original test suite, that execute code that has been changed for the new version of the software. The technique is strictly code based, and requires no assumptions about the approach used to specify or test the software initially. The technique applies to modified and derived classes, and to application programs that use modified classes. Copyright © 2000 John Wiley & Sons, Ltd.

Many algorithms for automating software engineering tasks require program slices. To be applicable to large software systems, these slices must be computed interprocedurally. Slicing techniques based on the system dependence graph (SDG) provide one approach for computing interprocedural slices, but these techniques are defined only for programs in which called procedures necessarily return to call sites. When applied to programs that contain arbitrary interprocedural control flow, existing SDG-based slicing techniques can compute incorrect slices; this limits their applicability. This paper presents an approach to constructing SDGs, and computing slices on SDGs, that accommodates programs with arbitrary interprocedural control flow. The main benefit of our approach is that it allows the use of the SDG-based slicing technique on a wide class of practical programs to which it did not previously apply.

Test case prioritization techniques schedule test cases for execution in an order that attempts to maximize some objective function. A variety of objective functions are applicable; one such function involves rate of fault detection-a measure of how quickly faults are detected within the testing process. An improved rate of fault detection during regression testing can provide faster feedback on a system under regression test and let debuggers begin their work earlier than might otherwise be possible. In this paper we describe several techniques for prioritizing test cases and report our empirical results measuring the effectiveness of these techniques for improving rate of fault detection. The results provide insights into the tradeoffs among various techniques for test case prioritization.

Regression testing is an expensive maintenance process directed at validating modified software. Regression test selection techniques attempt to reduce the cost of regression testing by selecting tests from a program's existing test suite. Many regression test selection techniques have been proposed. Although there have been some analytical and empirical evaluations of individual techniques, to our knowledge only one comparative study, focusing on one aspect of two of these techniques, has been performed. We conducted an experiment to examine the relative costs and benefits of several regression test selection techniques. The experiment examined five techniques for reusing tests, focusing on their relative abilities to reduce regression testing effort and uncover faults in modified programs. Our results highlight several differences between the techniques, and expose essential tradeoffs that should be considered when choosing a technique for practical application.

Form-based visual programming languages, which include commercial spreadsheets and various research systems, have had a substantial impact on end-user computing. Research shows, however, that form-based visual programs often contain faults. We would like to provide at least some of the benefits of formal testing methodologies to the creators of these programs. This paper presents a testing methodology for form-based visual programs. To accommodate the evaluation model used with these programs, and the interactive process by which they are created, our methodology is validation driven and incremental. To accommodate the users of these languages, We provide an interface to the methodology that does not require an understanding of testing theory. We discuss our implementation of this methodology and empirical results achieved in its use.

Test suite minimization techniques attempt to reduce the cost of saving and reusing tests during software maintenance, by eliminating redundant tests from test suites. A potential drawback of these techniques is that in minimizing a test suite, they might reduce the ability of that test suite to reveal faults in the software. A study showed that minimization can reduce test suite size without significantly reducing the fault detection capabilities of test suites. To further investigate this issue, we performed an experiment in which we compared the costs and benefits of minimizing test suites of various sizes for several programs. In contrast to the previous study, our results reveal that the fault detection capabilities of test suites can be severely compromised by minimization.

Program dependence information is useful for a variety of software testing and maintenance tasks. Properly defined, control and data dependencies can be used to identify semantic dependencies. To function effectively on whole programs, tools that utilize dependence information require information about interprocedural dependencies: dependencies that exist because of interactions among procedures. Many techniques for computing data and control dependencies exist; however, in our search of the literature we find only one attempt to define and compute interprocedural control dependencies. Unfortunately, that approach can omit important control dependencies, and incorrectly identifies control dependencies for a large class of programs. This paper presents a definition of interprocedural control dependence that supports the relationship of control and data dependence to semantic dependence, an efficient algorithm for calculating interprocedural control dependencies, and empirical results obtained by our implementation of the algorithm.

A variety of expensive software maintenance and testing tasks require a comparison of the behaviors of program versions. Program spectra have recently been proposed as a heuristic for use in performing such comparisons. To assess the potential usefulness of spectra in this context, we conducted an experiment that examined the relationship between program spectra and program behavior, and empirically compared several types of spectra. This paper reports the results of that experiment. 1 Introduction A variety of software testing and maintenance tasks require us to compare the behaviors of multiple program versions. For example, when we modify a program, we use regression testing to compare the behavior of the modified version to the behavior of its previous version, in the hope of detecting faults caused by the modifications. Similarly, when programs exhibit "regression failures" (behavioral failures that did not occur in preceding versions), we compare the behaviors of versions in the...

Regression testing is an expensive testing procedure utilized to validate modified software. Regression test selection techniques attempt to reduce the cost of regression testing by selecting a subset of a program's existing test suite. Safe regression test selection techniques select subsets that, under certain well-defined conditions, exclude no tests (from the original test suite) that if executed would reveal faults in the modified software. Many regression test selection techniques, including several safe techniques, have been proposed, but few have been subjected to empirical validation. This paper reports empirical studies on a particular safe regression test selection technique, in which the technique is compared to the alternative regression testing strategy of running all tests. The results indicate that safe regression test selection can be cost-effective, but that its costs and benefits vary widely based on a number of factors. In particular, test suite design can significantly affect the effectiveness of test selection, and coverage-based test suites may provide test selection results superior to those provided by test suites that are not coverage-based.

Form based visual programming languages, which include electronic spreadsheets and a variety of research systems, have had a substantial impact on end user computing. Research shows that form based visual programs often contain faults, and that their creators often have unwarranted confidence in the reliability of their programs. Despite this evidence, we find no discussion in the research literature of techniques for testing or assessing the reliability of form based visual programs. The paper addresses this lack. We describe differences between the form based and imperative programming paradigms, and discuss effects these differences have on strategies for testing form based programs. We then present several test adequacy criteria for form based programs, and illustrate their application. We show that an analogue to the traditional "all-uses" dataflow test adequacy criterion is well suited for code based testing of form based visual programs: it provides important error detection ability, and can be applied more easily to form based programs than to imperative programs.

Regression testing is an expensive but necessary maintenance activity performed on modified software to provide confidence that changes are correct and do not adversely affect other portions of the softwore. A regression test selection technique choses, from an existing test set, thests that are deemed necessary to validate modified software. We present a new technique for regression test selection. Our algorithms construct control flow graphs for a precedure or program and its modified version and use these graphs to select tests that execute changed code from the original test suite. We prove that, under certain conditions, the set of tests our technique selects includes every test from the original test suite that con expose faults in the modified procedfdure or program. Under these conditions our algorithms are safe . Moreover, although our algorithms may select some tests that cannot expose faults, they are at lease as precise as other safe regression test selection algorithms. Unlike many other regression test selection algorithms, our algorithms handle all language constructs and all types of program modifications. We have implemented our algorithms; initial empirical studies indicate that our technique can significantly reduce the cost of regression testing modified software.

Mutation testing is a technique for unit-testing software that, although powerful, is computationally expensive, The principal expense of mutation is that many variants of the test program, called mutants, must be repeatedly executed.This article quantifies the expense of mutation in terms of the number of mutants that are created, then proposes and evaluates a technique that reduces the number of mutants by an order of magnitude.Selective mutation reduces.the cost of mutation testing by reducing the number of mutants, This article reports experimental results that compare selective mutation testing with standard, or nonselective, mutation testing, and results that quantify the savings achieved by selective mutation testing, The results support the hypothesis that selective mutation is almost as strong as nonselective mutation: in experimental trials selective mutation provides almost the same coverage as nonselective mutation.with a four-fold or more reduction in the number of mutants.

Interprocedural data flow information is useful for many software testing and analysis techniques, including data flow testing, regression testing, program slicing and impact analysis. For programs with aliases, these testing and analysis techniques can yield invalid results, unless the data flow information accounts for aliasing effects. Recent research provides algorithms for performing interprocedural data flow analysis in the presence of aliases; however, these algorithms are expensive, and achieve precise results only on complete programs. This paper presents an algorithm for performing alias analysis on incomplete programs that lets individual software components such as library routines, subroutines or subsystems be independently analyzed. The paper also presents an algorithm for reusing the results of this separate analysis when the individual software components are linked with calling modules. Our algorithms let us analyze frequently used software components, such as library routines or classes, independently, and reuse the results of that analysis when analyzing calling programs, without incurring the expense of completely reanalyzing each calling program. Our algorithms also provide a way to analyze large systems incrementally.

Regression testing is a necessary but expensive maintenance activity aimed at showing that code has not been adversely affected by changes. Regression test selection techniques reuse tests from an existing test suite to test a modified program. Many regression test selection techniques have been proposed, however, it is difficult to compare and evaluate these techniques because they have different goals. This paper outlines the issues relevant to regression test selection techniques, and uses these issues as the basis for a framework within which to evaluate the techniques. The paper illustrates the application of the framework by using it to evaluate existing regression test selection techniques. The evaluation reveals the strengths and weaknesses of existing techniques, and highlights some problems that future work in this area should address.

Regression testing is an important but expensive software maintenance activity aimed at providing confidence in modified software. Selective retest methods reduce the cost of regression testing by selecting tests for a modified program from a previously existing test suite. Many researchers have addressed the selective retest problem for procedural-language software, but few have addressed the problem for object-oriented software. We present a new technique for selective retest, that handles object-oriented software. Our algorithm constructs dependence graphs for classes and applications programs, and uses these graphs to determine which tests in an existing test suite can cause a modified class or program to produce different output than the original. Unlike previous selective retest techniques, our method applies to modified and derived classes. As well as to applications programs that use modified classes. Our technique is strictly code-based, and makes no assumptions about methods used to specify or test the software initially.>

Regression testing is performed on modified software to provide confidence that changed and affected portions of the code behave correctly. We present an approach to regression testing that handles two important tasks: selecting tests from the existing test suite that should be rerun, and identifying portions of the code that must be covered by tests. Both tasks are performed by traversing graphs for the program and its modified version. We first apply our technique to single procedures and then show how our technique is applied at the interprocedural level. Our approach has several advantages over previous work. First, our test selection technique is safe, selecting every test that may produce different output in the modified program. However, our selection technique chooses smaller test sets than other safe approaches. Second, our approach is the first safe approach to identify coverage requirements, and the first safe approach to do so interprocedurally. Third, our approach handles ...

The basic unit of testing in an object-oriented program is a class. Although there has been much recent research on testing of classes, most of this work has focused on black-box approaches. However, since black-box testing techniques may not provide sufficient code coverage, they should be augmented with code-based or white-box techniques. Dataflow testing is a code-based testing technique that uses the dataflow relations in a program to guide the selection of tests. Existing dataflow testing techniques can be applied both to individual methods in a class and to methods in a class that interact through messages, but these techniques do not consider the dataflow interactions that arise when users of a class invoke sequences of methods in an arbitrary order. We present a new approach to class testing that supports dataflow testing for dataflow interactions in a class. For individual methods in a class, and methods that send messages to other methods in a the class, our technique is similar to existing dataflow testing techniques. For methods that are accessible outside the class, and can be called in any order by users of the class, we compute dataflow information, and use it to test possible interactions between these methods. The main benefit of our approach is that it facilitates dataflow testing for an entire class. By supporting dataflow testing of classes, we provide opportunities to find errors in classes that may not be uncovered by black-box testing. Our technique is also useful for determining which sequences of methods should be executed to test a class, even in the absence of a specification. Finally, as with other code-based testing techniques, a large portion of our technique can be automated.

Regression testing is a necessary but costly maintenance activity aimed at demonstrating that code has not been adversely affected by changes. A selective approach to regression testing selects tests for a modified program from an existing test suite. A new technique for selective regression testing is presented. The proposed algorithm constructs control dependence graphs for program versions and uses these graphs to determine which tests from the existing test suite may exhibit changed behavior on the new version. Unlike most previous techniques for selective retest, the algorithm selects every test from the original test suite that might expose errors in the modified program, and does this without prior knowledge of program modifications. The algorithm handles all language constructs and program modifications and is easily automated.>

We present a new technique for constructing a program dependence graph that contains a program's control flow, along with the usual control and data dependence information. Our algorithm constructs a program dependence graph while the program is being parsed. For programs containing only structured transfers of control, our algorithm does not require information provided by the control flow graph or post dominator tree and therefore obviates the construction of these auxiliary graphs. For programs containing explicit transfers of control, our algorithm adjusts the partial control dependence subgraph, constructed during the parse, to incorporate exact control dependence information. There are several advantages to our approach. For many programs, our algorithm may result in substantial savings in time and memory since our construction of the program dependence graph does not require the auxiliary graph. Furthermore, since we incorporate control and data flow as well as exact control dependence information into the program dependence graph, our graph has a wide range of applicability. We have implemented our algorithm by incorporating it into the Free Software Foundation's GNU C compiler; currently we are performing experiments that compare our technique with the traditional approach.