Summary UNICORNis an automated dynamic pattern‐detection‐based technique that finds and ranks problematic memory access patterns for non‐deadlock concurrency bugs. It monitors pairs of memory accesses, combines the pairs into problematic patterns and ranks the patterns by their suspiciousness scores. It detects significant classes of bug types, including order violations and both single‐variable and multivariable atomicity violations, which have been shown to be the most important classes of non‐deadlock concurrency bugs. This paper describes theUNICORNapproach, its implementations in Java and C++, and evaluates these implementations empirically. The evaluation shows thatUNICORNcan effectively compute and rank the patterns that represent concurrency bugs, and perform computation and ranking with reasonable efficiency. Copyright © 2014 John Wiley & Sons, Ltd.

This paper presents the results of a four-month ethnographically-informed study that we performed at a vendor organization in India to understand how culture influences global software-testing practice. The paper discusses our findings and analysis of software-testing activities conducted by two teams: one working for a Japanese client, the other working for a U.S. client. The findings show the differences in the software-testing approaches of the two teams with respect to team structure, thought processes, expectations, testing focus areas, and trust levels. The analysis suggests that cultural differences (e.g., national, user, and software-developer) are responsible for these differences in testing approaches. The paper describes the study details, our observations about the different testing-approach patterns that the teams adopted, our analysis of the reasons for those differences, and our reflections and suggested implications based on the findings.

This paper presents Griffin, a new fault-comprehension technique. Griffin provides a way to explain concurrency bugs using additional information over existing fault-localization techniques, and thus, bridges the gap between fault- localization and fault-fixing techniques. Griffin inputs a list of memory-access patterns and a coverage matrix, groups those patterns responsible for the same concurrency bug, and outputs the grouped patterns along with suspicious methods and bug graphs. Griffin is the first technique that handles multiple concurrency bugs. This paper also describes the implementation of Griffin in Java and C++, and shows the empirical evaluation of Griffin on a set of subjects. The results show that, for our subjects, Griffin clusters failing executions and memory-access patterns for the same bug with few false positives, provides suspicious methods that contain the locations to be fixed, and runs efficiently.

SUMMARY Test‐suite augmentation techniques enhance test suites for software changes. In previous work, we introduced an augmentation technique that enumerates the conditions for the propagation of the effects of changes. Empirical studies showed that this technique can test changes effectively but, because of the high complexity of the technique, the experiments were small and the propagation distances from each change were limited. In this paper, we present a new, demand‐driven approach for performing this propagation‐based testing of changes that achieves much greater distances and that enables larger and more significant studies. We implemented this new approach and studied it on a set of changes in Java programs by comparing, to a larger extent than possible before, propagation‐based strategies with other change testing techniques. Our results confirm, with statistical significance, the superiority of propagation‐based strategies over other techniques, and show that these strategies are especially effective for those changes that are the most difficult to test.Copyright © 2013 John Wiley & Sons, Ltd.

This paper presents UNICORN, a new automated dynamic pattern-detection-based technique that finds and ranks problematic memory access patterns for non-deadlock concurrency bugs. UNICORN monitors pairs of memory accesses, combines the pairs into problematic patterns, and ranks the patterns by their suspiciousness scores. UNICORN detects significant classes of bug types, including order violations and both single-variable and multi-variable atomicity violations, which have been shown to be the most important classes of non-deadlock concurrency bugs. The paper also describes implementations of UNICORN in Java and C++, along with empirical evaluation using these implementations. The evaluation shows that UNICORN can effectively compute and rank the patterns that represent concurrency bugs, and perform computation and ranking with reasonable efficiency.

The effectiveness of software testing is often assessed by measuring coverage of some aspect of the software, such as its code. There is much research aimed at increasing code coverage of sequential software. However, there has been little research on increasing coverage for concurrent software. This paper presents a new technique that aims to achieve high coverage of concurrent programs by generating thread schedules to cover uncovered coverage requirements. Our technique first estimates synchronization-pair coverage requirements, and then generates thread schedules that are likely to cover uncovered coverage requirements. This paper also presents a description of a prototype tool that we implemented in Java, and the results of a set of studies we performed using the tool on a several open-source programs. The results show that, for our subject programs, our technique achieves higher coverage faster than random testing techniques; the estimation-based heuristic contributes substantially to the effectiveness of our technique.

To manage and integrate information gathered from heterogeneous databases, an ontology is often used. Like all systems, ontology-driven systems evolve over time and must be regression tested to gain confidence in the behavior of the modified system. Because rerunning all existing tests can be extremely expensive, researchers have developed regression-test-selection (RTS) techniques that select a subset of the available tests that are affected by the changes, and use this subset to test the modified system. Existing RTS techniques have been shown to be effective, but they operate on the code and are unable to handle changes that involve ontologies. To address this limitation, we developed and present in this paper a novel RTS technique that targets ontology-driven systems. Our technique creates representations of the old and new ontologies, compares them to identify entities affected by the changes, and uses this information to select the subset of tests to rerun. We also describe in this paper OntoRetest, a tool that implements our technique and that we used to empirically evaluate our approach on two biomedical ontology-driven database systems. The results of our evaluation show that our technique is both efficient and effective in selecting tests to rerun and in reducing the overall time required to perform regression testing.

We present an algorithm and a system for generating input events to exercise smartphone apps. Our approach is based on concolic testing and generates sequences of events automatically and systematically. It alleviates the path-explosion problem by checking a condition on program executions that identifies subsumption between different event sequences. We also describe our implementation of the approach for Android, the most popular smartphone app platform, and the results of an evaluation that demonstrates its effectiveness on five Android apps.

In the era of globally distributed software engineering, the practice of outsourced, off shored software testing (OOST) has witnessed increasing adoption. Although there have been ethnographic studies of the development aspects of global software engineering and of the in-house practice of testing, there have been fewer studies of OOST, which to succeed, can require dealing with unique challenges. To address this limitation of the existing studies, we conducted-and, in this paper, report the findings of-an ethnographically-informed study of three vendor testing teams involved in OOST practice. Specifically, we studied how test engineers perform their tasks under deadline pressures, the challenges that they encounter, and their strategies for coping with the challenges. Our study provides insights into the differences and similarities between in-house testing and OOST, the influence of team structures on the degree of pressure experienced by test engineers in the OOST setup, and the factors that influence quality and productivity under OOST.

Regression testing is an important activity performed to validate modified software, and one of its key tasks is regression test selection (RTS) -- selecting a subset of existing test cases to run on the modified software. Most existing RTS techniques focus on changes made to code components and completely ignore non-code elements, such as configuration files and databases, which can also change and affect the system behavior. To address this issue, we present a new RTS technique that performs accurate test selection in the presence of changes to non-code components. To do this, our technique computes traceability between test cases and the external data accessed by an application, and uses this information to perform RTS in the presence of changes to non-code elements. We present our technique, a prototype implementation of our technique, and a set of preliminary empirical results that illustrate the feasibility, effectiveness, and potential usefulness of our approach.

Test-suite augmentation for evolving software -- the process of augmenting a test suite to adequately test software changes -- is necessary for any program that undergoes modifications as part of its development and maintenance cycles. Recently, we presented a new technique for test-suite augmentation based on leveraging the propagation conditions for the effects of changes. Although empirical studies show that this technique can be quite effective for testing changes, the experiments have been limited because of the complexity of the implementation. In this paper, we present a new and more efficient approach for propagation-based testing of changes that can reach much longer propagation-distances and can focus the testing more precisely on those behaviors of changes that can actually affect the output. Using an implementation of this new approach, we performed a study on a set of changes on Java programs for which we compared, to a much larger extent than possible before, our propagation-based strategies with other existing techniques for testing changes. The results of the study not only confirm the superior effectiveness of propagation-based strategies over these other techniques for testing changes, but also quantify that superiority and clarify the conditions under which our approach is most effective.

The dynamic symbolic-execution technique can automatically perform symbolic execution of programs that use problematic features of Java, such as native methods. However, to compute precise symbolic execution, the technique requires manual effort to specify models for problematic code. Furthermore, existing approaches to perform symbolic execution either cannot be extended to perform dynamic symbolic execution or incur significant imprecision. In this paper, we present a novel program-transformation technique called heap cloning. Heap cloning transforms a program in such a way that dynamic symbolic execution of the transformed program results in the same path constraints as dynamic symbolic execution of the original program. However, symbolic execution of the transformed program produces feedback on where imprecision is introduced, and that feedback can reduce the manual effort required to build models. Furthermore, such transformation can enable existing approaches to perform symbolic execution systems to overcome their limitations. In this paper, we also present a system, called Cinger, that leverages heap cloning, and that we used to perform an empirical evaluation. The empirical evaluation shows that Cinger can compute precise path constraints, and requires little (if any) manual effort for a set of large real-world programs.

This paper presents a new fault-localization technique designed for applications that interact with a relational database. The technique uses dynamic information specific to the application's database, such as Structured Query Language (SQL) commands, to provide a fault-location diagnosis. By creating statement-SQL tuples and calculating their suspiciousness, the presented method lets the developer identify the database commands and the program statements likely to cause the failures. The technique also calculates suspiciousness for statement-attribute tuples and uses this information to identify SQL fragments that are statistically likely to be responsible for the suspiciousness of that SQL command. The paper reports the results of two empirical studies. The first study compares existing and database-aware fault-localization methods, and reveals the strengths and limitations of prior techniques, while also highlighting the effectiveness of the new approach. The second study demonstrates the benefits of using database information to improve understanding and reduce manual debugging effort.

Dynamic program dependences are recognized as important factors in software debugging because they contribute to triggering the effects of faults and propagating the effects to a program's output. The effects of dynamic dependences also produce significant confounding bias when statistically estimating the causal effect of a statement on the occurrence of program failures, which leads to poor fault localization results. This paper presents a novel causal-inference technique for fault localization that accounts for the effects of dynamic data and control dependences and thus, significantly reduces confounding bias during fault localization. The technique employs a new dependence-based causal model together with matching of test executions based on their dynamic dependences. The paper also presents empirical results indicating that the new technique performs significantly better than existing statistical fault-localization techniques as well as our previous fault localization technique based on causal-inference methodology.

Concurrency fault are difficult to find because they usually occur under specific thread interleavings. Fault-detection tools in this area find data-access patterns among thread interleavings, but they report benign patterns as well as actual faulty patterns. Traditional fault-localization techniques have been successful in identifying faults in sequential, deterministic programs, but they cannot detect faulty data-access patterns among threads. This paper presents a new dynamic fault-localization technique that can pinpoint faulty data-access patterns in multi-threaded concurrent programs. The technique monitors memory-access sequences among threads, detects data-access patterns associated with a program's pass/fail results, and reports dataaccess patterns with suspiciousness scores. The paper also presents the description of a prototype implementation of the technique in Java, and the results of an empirical study we performed with the prototype on several Java benchmarks. The empirical study shows that the technique can effectively and efficiently localize the faults for our subjects.

Although many static-analysis techniques have been developed for automatically detecting bugs, such as null dereferences, fewer automated approaches have been presented for analyzing whether and how such bugs are fixed. Attempted bug fixes may be incomplete in that a related manifestation of the bug remains unfixed. In this paper, we characterize the “completeness” of attempted bug fixes that involve the flow of invalid values from one program point to another, such as null dereferences, in Java programs. Our characterization is based on the definition of a bug neighborhood, which is a scope of flows of invalid values. We present an automated analysis that, given two versions P and P' of a program, identifies the bugs in P that have been fixed in P', and classifies each fix as complete or incomplete. We implemented our technique for null-dereference bugs and conducted empirical studies using open-source projects. Our results indicate that, for the projects we studied, many bug fixes are not complete, and thus, may cause failures in subsequent executions of the program.

Developers often make multiple changes to software. These changes are introduced to work cooperatively or to accomplish separate goals. However, changes might not interact as expected or may produce undesired side effects. Thus, it is crucial for software-development tasks to know exactly which changes interact. For example, testers need this information to ensure that regression test suites test the combined behaviors of changes. For another example, teams of developers must determine whether it is safe to merge variants of a program modified in parallel. Existing techniques can be used to detect at runtime potential interactions among changes, but these reports tend to be coarse and imprecise. To address this problem, in this paper, we first present a formal model of change interactions at the code level, and then describe a new technique, based on this model, for detecting at runtime such interactions with accuracy. We also present the results of a comparison of our technique with other techniques on a set of Java subjects. Our results clearly suggest that existing techniques are too inaccurate and only our technique, of all those studied, provides acceptable confidence in detecting real change interactions occurring at runtime.

This paper investigates the application of causal inference methodology for observational studies to software fault localization based on test outcomes and profiles. This methodology combines statistical techniques for counterfactual inference with causal graphical models to obtain causal-effect estimates that are not subject to severe confounding bias. The methodology applies Pearl's Back-Door Criterion to program dependence graphs to justify a linear model for estimating the causal effect of covering a given statement on the occurrence of failures. The paper also presents the analysis of several proposed-fault localization metrics and their relationships to our causal estimator. Finally, the paper presents empirical results demonstrating that our model significantly improves the effectiveness of fault localization.

This paper presents a new technique, called Symbolic Program Decomposition (or SPD), for symbolic execution of multiple paths that is more scalable than existing techniques, which symbolically execute control-flow paths individually. SPD exploits control and data dependencies to avoid analyzing unnecessary combinations of subpaths. SPD can also compute an over-approximation of symbolic execution by abstracting away symbolic subterms arbitrarily, to further scale the analysis at the cost of precision. The paper also presents our implementation and empirical evaluation showing that SPD can achieve savings of orders of magnitude in the path-exploration costs of multiple-path symbolic execution. Finally, the paper presents a study that examines the use of SPD for a particular application: change analysis for test-suite augmentation.

Web applications can suffer from poor reliability, and AJAX technology makes Web sites even more error-prone. Failures of a Web application, particularly user-visible failures, impact users' satisfaction and may drive users away from using the Web site. Conventional testing techniques are inadequate for improving AJAX applications' reliability, and application providers commonly rely on fast failure detection, which is challenging. In this paper, we present a novel technique for automatically detecting user-visible failures in AJAX applications. Our technique trains a Bayesian model to analyze users' interaction behaviors to infer whether such user responses are related to user-visible failures. We implemented our technique in a tool called SIRANA. We performed a case study using a commercial AJAX application with seeded bugs, and collected users' interaction data during 14 one-hour sessions. We evaluated our technique using SIRANA applied to the collected data. The results demonstrate the effectiveness of our technique: It not only detected all seeded bugs, but also detected four real, previously-unknown bugs.

This paper presents an innovative model of a program's internal behavior over a set of test inputs, called the probabilistic program dependence graph (PPDG), which facilitates probabilistic analysis and reasoning about uncertain program behavior, particularly that associated with faults. The PPDG construction augments the structural dependences represented by a program dependence graph with estimates of statistical dependences between node states, which are computed from the test set. The PPDG is based on the established framework of probabilistic graphical models, which are used widely in a variety of applications. This paper presents algorithms for constructing PPDGs and applying them to fault diagnosis. The paper also presents preliminary evidence indicating that a PPDG-based fault localization technique compares favorably with existing techniques. The paper also presents evidence indicating that PPDGs can be useful for fault comprehension.

Several recent studies indicate that many industrial applications exhibit poor quality in the design of exception-handling. To improve the quality of error-handling, we need to understand the problems and obstacles that developers face when designing and implementing exception-handling. In this paper, we present our research on understanding the viewpoint of developers-novices and experts-toward exception-handling. First, we conducted a study with novice developers in industry. The study results reveal that novices tend to ignore exceptions because of the complex nature of exception-handling. Then, we conducted a second study with experts in industry to understand their perspective on exception-handling. The study results show that, for experts, exception-handling is a crucial part in the development process. Experts also confirm the novices' approach of ignoring exception-handling and provide insights as to why novices do so. After analyzing the study data, we identified factors that influence experts' strategy selection process for handling exceptions and then built a model that represents a strategy selection process experts use to handle exceptions. Our model is based on interacting modules and fault scope. We conclude with some recommendations to help novices improve their understanding of exception-handling.

Lightweight fault-localization techniques use program coverage to isolate the parts of the code that are most suspicious of being faulty. In this paper, we present the results of a study of three types of program coverage—statements, branches, and data dependencies—to compare their effectiveness in localizing faults. The study shows that no single coverage type performs best for all faults—different kinds of faults are best localized by different coverage types. Based on these results, we present a new coverage-based approach to fault localization that leverages the unique qualities of each coverage type by combining them. Because data dependencies are noticeably more expensive to monitor than branches, we also investigate the effects of replacing data-dependence coverage with an approximation inferred from branch coverage. Our empirical results show that (1) the cost of fault localization using combinations of coverage is less than using any individual coverage type and closer to the best case (without knowing in advance which kinds of faults are present), and (2) using inferred data-dependence coverage retains most of the benefits of combinations.

One of the most expensive activities that occurs as software is developed and maintained is the testing (or retesting) of the software after it has been modified. Studies suggest that a significant portion of development and maintenance costs go to this retesting, which is known as regression testing. Reports estimate that regression testing consumes as much as 80% of the overall testing budget and can consume up to 50% of the cost of software maintenance. Rapidly changing software and computing environments present many challenges for effective and efficient regression testing in practice. Regression testing can be performed after changes are made to the software, such as after nightly or regular builds, before a new version of the software is released, every time the software is saved and compiled, such as in an agile development environment, or before patches, such as security patches, are released. Regardless of the environment or when it is performed, the goals of regression testing are the same: to improve confidence that the changes behave as intended and that they have not adversely affected unchanged parts of the software. Because regression testing is important, but expensive, much research has been performed, both in industry and in academia, to develop techniques to make regression testing more effective and efficient. This research has also produced many tools and systems that have been used for empirical studies that investigate the effectiveness, scalability, and practicality of the techniques. Researchers have developed techniques for addressing a number of issues related to regression testing, and, in this talk, I will discuss them in four areas. First, techniques attempt to reduce the regression testing time by creating effective regression test suites that test the changed part of the software, by identifying test cases in the regression test suite that do not need to be rerun on the changed software, and by identifying and removing obsolete test cases. Second, techniques can reuse test suites created for one version of the software by identifying those test cases that need to be rerun for testing subsequent versions of the software and by computing an effective ordering for running the test cases. Third, techniques can recycle test cases by monitoring executions to gather test inputs that can be used for retest-ing and by creating unit test cases from system test cases. Finally, techniques could recover test cases by identifying, manipulating, and transforming obsolete test cases, by generating new test cases from old ones, and by repairing test cases when the software changes. In this talk, I will overview the research in testing of evolving software, and discuss achievements to date in managing regression testing by reducing, reusing, recycling, and recovering test cases. I will also present the state of the research and the state of the practice in regression testing. Finally, I will discuss the current trends in both academia and industry, the challenges for solving the difficult problems that exist, the promise for testing of evolving software in the future, and the important open challenges for regression testing in the next decade.

This paper presents a new approach for locating and repairing faults that cause runtime exceptions in Java programs. The approach handles runtime exceptions that involve a flow of an incorrect value that finally leads to the exception. This important class of exceptions includes exceptions related to dereferences of null pointers, arithmetic faults (e.g., ArithmeticException), and type faults (e.g., ArrayStoreException). Given a statement at which such an exception occurred, the technique combines dynamic analysis (using stack-trace information) with static backward data-flow analysis (beginning at the point where the runtime exception occurred) to identify the source statement at which an incorrect assignment was made; this information is required to locate the fault. The approach also identifies the source statements that may cause this same exception on other executions, along with the reference statements that may raise an exception in other executions because of this incorrect assignment; this information is required to repair the fault. The paper also presents an application of our technique to null pointer exceptions. Finally, the paper describes an implementation of the null-pointer-exception analysis and a set of studies that demonstrate the advantages of our approach for locating and repairing faults in the program.

This paper presents a technique that leverages an existing regression test selection algorithm to compute accurate, updated coverage data on a version of the software, Pi+1, without rerunning any test cases that do not execute the changes from the previous version of the software, Pito Pi+1. The technique also reduces the cost of running those test cases that are selected by the regression test selection algorithm by performing a selective instrumentation that reduces the number of probes required to monitor the coverage data. Users of our technique can avoid the expense of rerunning the entire test suite on Pi+1or the inaccuracy produced by previous approaches that estimate coverage data for Pi+1or that reuse outdated coverage data from Pi. This paper also presents a tool, RECOVER, that implements our technique, along with a set of empirical studies on a set of subjects that includes several industrial programs, versions, and test cases. The studies show the inaccuracies that can exist when an application-regression test selection-uses estimated or outdated coverage data. The studies also show that the overhead incurred by selective instrumentation used in our technique is negligible and overall our technique provides savings over earlier techniques.

Fault-localization techniques that utilize information about all test cases in a test suite have been presented. These techniques use various approaches to identify the likely faulty part(s) of a program, based on information about the execution of the program with the test suite. Researchers have begun to investigate the impact that the composition of the test suite has on the effectiveness of these fault-localization techniques. In this paper, we present the first experiment on one aspect of test-suite composition--test-suite reduction. Our experiment studies the impact of the test-suite reduction on the effectiveness of fault-localization techniques. In our experiment, we apply 10 test-suite reduction strategies to test suites for eight subject programs. We then measure the differences between the effectiveness of four existing fault-localization techniques on the unreduced and reduced test suites. We also measure the reduction in test-suite size of the 10 test-suite reduction strategies. Our experiment shows that fault-localization effectiveness varies depending on the test-suite reduction strategy used, and it demonstrates the trade-offs between test-suite reduction and fault-localization effectiveness.

This paper presents a method that addresses two practical issues concerning the use of random test selection for regression testing: the number of random samples needed from the test suite to provide reliable results, and the confidence levels of the predictions made by the random samples. The method applies the Chernoff bound, which has been applied in various randomized algorithms, to compute the error bound for random test selection. The paper presents three example applications, based on the method, for regression testing. The main benefits of the method are that it requires no distribution information about the test suite from which the samples are taken, and the computation of the confidence level is independent of the size of the test suite. The paper also presents the results of an empirical evaluation of the technique on a set of C programs, which have been used in many testing experiments, along with three of the GCC compilers. The results demonstrate the effectiveness of the method and show its potential for regression testing on real-world, large-scale applications.

This paper presents an innovative model of a program's internal behavior over a set of test inputs, called the probabilistic program dependence graph (PPDG), that facilitates probabilistic analysis and reasoning about uncertain program behavior, particularly that associated with faults. The PPDG is an augmentation of the structural dependences represented by a program dependence graph with estimates of statistical dependences between node states, which are computed from the test set. The PPDG is based on the established framework of probabilistic graphical models, which are widely used in applications such as medical diagnosis. This paper presents algorithms for constructing PPDGs and applying the PPDG to fault diagnosis. This paper also presents preliminary evidence indicating that PPDGs can facilitate fault localization and fault comprehension.

One activity performed by developers during regression testing is test-suite augmentation, which consists of assessing the adequacy of a test suite after a program is modified and identifying new or modified behaviors that are not adequately exercised by the existing test suite and, thus, require additional test cases. In previous work, we proposed MATRIX, a technique for test-suite augmentation based on dependence analysis and partial symbolic execution. In this paper, we present the next step of our work, where we (I) improve the effectiveness of our technique by identifying all relevant change-propagation paths, (2) extend the technique to handle multiple and more complex changes, (3) introduce the first tool that fully implements the technique, and (4) present an empirical evaluation performed on real software. Our results show that our technique is practical and more effective than existing test-suite augmentation approaches in identifying test cases with high fault-detection capabilities.

This paper presents an automatic test-data generation technique that uses a genetic algorithm (GA) to generate test data that satisfy data-flow coverage criteria. The technique applies the concepts of dominance relations between nodes to define a new multi-objective fitness function to evaluate the generated test data. The paper also presents the results of a set of empirical studies conducted on a set of programs that evaluate the effectiveness of our technique compared to the random-testing technique. The studies show the effective of our technique in achieving coverage of the test requirements, and in reducing the size of test suites, the search time, and the number of iterations required to satisfy the data-flow criteria.

This paper presents a technique that leverages an existing regression test-selection algorithm to compute accurate, updated coverage data on a version of the software, Pi+1, without rerunning any test cases that do not execute the changes from the previous version of the software, Pi, to Pi+1-Users of our technique can avoid the expense of rerunning the entire test suite on Pi+1or the inaccuracy produced by previous approaches that estimate coverage data for Pi+1or reuse outdated coverage data from Pi. This paper also presents a tool, RECOVER, that implements our technique, along with a set of empirical studies. The studies show the inaccuracies that can exist when an application—regression-test selection—uses estimated and outdated coverage data. The studies also show that the overhead incurred by our technique is negligible.

The presence of multiple faults in a program can inhibit the ability of fault-localization techniques to locate the faults. This problem occurs for two reasons: when a program fails, the number of faults is, in general, unknown; and certain faults may mask or obfuscate other faults. This paper presents our approach to solving this problem that leverages the well-known advantages of parallel work flows to reduce the time-to-release of a program. Our approach consists of a technique that enables more effective debugging in the presence of multiple faults and a methodology that enables multiple developers to simultaneously debug multiple faults. The paper also presents an empirical study that demonstrates that our parallel-debugging technique and methodology can yield a dramatic decrease in total debugging time compared to a one-fault-at-a-time, or conventionally sequential, approach.

Structural testing of software requires monitoring the software's execution to determine which program entities are executed by a test suite. Such monitoring can add considerable overhead to the execution of the program, adversely affecting the cost of running a test suite. Thus, minimizing the necessary monitoring activity lets testers reduce testing time or execute more test cases. A basic testing strategy is to cover all statements or branches but a more effective strategy is to cover all definition-use associations (DUAs). In this paper, we present a novel technique to efficiently monitor DUAs, based on branch monitoring. We show how to infer from branch coverage the coverage of many DUAs, while remaining DUAs are predicted with high accuracy by the same information. Based on this analysis, testers can choose branch monitoring to approximate DUA coverage or instrument directly for DUA monitoring, which is precise but more expensive. In this paper, we also present a tool, called DUA-Forensics, that we implemented for this technique along with a set of empirical studies that we performed using the tool

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.

The effectiveness of mutation testing depends heavily on the types of faults that the mutation operators are designed to represent. Thus, the quality of the mutation operators is key to mutation testing. Although, mutation operators for object-oriented languages have previously been presented, little research has been done to show the usefulness of the class mutation operators. To assess the usefulness of class mutation operators, we conducted two empirical studies. In the first study, we examine the number and kinds of mutants that are generated for object-oriented programs. In the second study, we investigate the way in which class mutation operators model faults that are not detected by traditional mutation testing. We conducted our studies using a well-known object-oriented system, BCEL.

As software evolves, impact analysis estimates the potential effects of changes, before or after they are made, by identifying which parts of the software may be affected by such changes. Traditional impact-analysis techniques are based on static analysis and, due to their conservative assumptions, tend to identify most of the software as affected by the changes. More recently, researchers have begun to investigate dynamic impact-analysis techniques, which rely on dynamic, rather than static, information about software behavior. Existing dynamic impact-analysis techniques are either very expensive---in terms of execution overhead or amount of dynamic information collected---or imprecise. In this paper, we present a new technique for dynamic impact analysis that is almost as efficient as the most efficient existing technique and is as precise as the most precise existing technique. The technique is based on a novel algorithm that collects (and analyzes) only the essential dynamic information required for the analysis. We discuss our technique, prove its correctness, and present a set of empirical studies in which we compare our new technique with two existing techniques, in terms of performance and precision.

The high cost of locating faults in programs has motivated the development of techniques that assist in fault localization by automating part of the process of searching for faults. Empirical studies that compare these techniques have reported the relative effectiveness of four existing techniques on a set of subjects. These studies compare the rankings that the techniques compute for statements in the subject programs and the effectiveness of these rankings in locating the faults. However, it is unknown how these four techniques compare with Tarantula, another existing fault-localization technique, although this technique also provides a way to rank statements in terms of their suspiciousness. Thus, we performed a study to compare the Tarantula technique with the four techniques previously compared. This paper presents our study---it overviews the Tarantula technique along with the four other techniques studied, describes our experiment, and reports and discusses the results. Our studies show that, on the same set of subjects, the Tarantula technique consistently outperforms the other four techniques in terms of effectiveness in fault localization, and is comparable in efficiency to the least expensive of the other four techniques.

Program analysis and program optimization of Java programs require reference information that estimates the instances of classes that may be accessed through dereferences. Recent work has presented several approaches for adapting Andersen's algorithm [1]---the most precise flow-insensitive and context-insensitive points-to analysis algorithm developed for C--- for analyzing Java programs (e.g., [5, 9, 12]). Studies in our previous work [6] indicate that this algorithm may compute very imprecise reference information for Java programs.

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.

To investigate the program-execution data efficiently, we must be able to view the data at different levels of detail. In our visualization approach, we represent software systems at three different levels: statement level, file level, and system level. At the statement level, we represent the actual code. The representation at the file level provides a miniaturized view of the source code similar to the one used in the SeeSoft system (Eick et al., 1992). The system level uses treemaps (Shneiderman, 1992 and Bruls et al., 2000) to represent the software and is the most abstracted level in our visualization. At each level, coloring is used to represent one- or two-dimensional information about the code, using the colors' hue and brightness components. The coloring technique that we apply is a generalization of the coloring technique defined for fault-localization by Jones and colleagues (2001). GAMMATELLA is a toolset that implements our visualization approach and provides capabilities for instrumenting the code, collecting program-execution data from the field, and storing and retrieving the data locally. GAMMATELLA is written in Java, supports the monitoring of Java programs, and consists of three main components: an instrumentation, execution, and coverage tool, a data collection daemon, and a program visualizer.

Although object-oriented languages can improve programming practices, their characteristics may introduce new problems for software engineers. One important problem is the presence of implicit control flow caused by exception handling and polymorphism. Implicit control flow causes complex interactions, and can thus complicate software-engineering tasks. To address this problem, we present a systematic and structured approach, for supporting these tasks, based on the static and dynamic analyses of constructs that cause implicit control flow. Our approach provides software engineers with information for supporting and guiding development and maintenance tasks. We also present empirical results to illustrate the potential usefulness of our approach. Our studies show that, for the subjects considered, complex implicit control flow is always present and is generally not adequately exercised.

A program's behavior is ultimately the collection of all its executions. This collection is diverse, unpredictable, and generally unbounded. Thus it is especially suited to statistical analysis and machine learning techniques. The primary focus of this paper is on the automatic classification of program behavior using execution data. Prior work on classifiers for software engineering adopts a classical batch-learning approach. In contrast, we explore an active-learning paradigm for behavior classification. In active learning, the classifier is trained incrementally on a series of labeled data elements. Secondly, we explore the thesis that certain features of program behavior are stochastic processes that exhibit the Markov property, and that the resultant Markov models of individual program executions can be automatically clustered into effective predictors of program behavior. We present a technique that models program executions as Markov models, and a clustering method for Markov models that aggregates multiple program executions into effective behavior classifiers. We evaluate an application of active learning to the efficient refinement of our classifiers by conducting three empirical studies that explore a scenario illustrating automated test plan augmentation.

When software is modified, during development and maintenance, it is regression tested to provide confidence that the changes did not introduce unexpected errors and that new features behave as expected. One important problem in regression testing is how to select a subset of test cases, from the test suite used for the original version of the software, when testing a modified version of the software. Regression-test-selection techniques address this problem. Safe regression-test-selection techniques select every test case in the test suite that may behave differently in the original and modified versions of the software. Among existing safe regression testing techniques, efficient techniques are often too imprecise and achieve little savings in testing effort, whereas precise techniques are too expensive when used on large systems. This paper presents a new regression-test-selection technique for Java programs that is safe, precise, and yet scales to large systems. It also presents a tool that implements the technique and studies performed on a set of subjects ranging from 70 to over 500 KLOC. The studies show that our technique can efficiently reduce the regression testing effort and, thus, achieve considerable savings.

Understanding data dependences in programs is important for many software-engineering activities, such as program understanding, impact analysis, reverse engineering, and debugging. The presence of pointers can cause subtle and complex data dependences that can be difficult to understand. For example, in languages such as C, an assignment made through a pointer dereference can assign a value to one of several variables, none of which may appear syntactically in that statement. In the first part of this article, we describe two techniques for classifying data dependences in the presence of pointer dereferences. The first technique classifies data dependences based on definition type, use type, and path type. The second technique classifies data dependences based on span. We present empirical results to illustrate the distribution of data-dependence types and spans for a set of real C programs. In the second part of the article, we discuss two applications of the classification techniques. First, we investigate different ways in which the classification can be used to facilitate data-flow testing. We outline an approach that uses types and spans of data dependences to determine the appropriate verification technique for different data dependences; we present empirical results to illustrate the approach. Second, we present a new slicing approach that computes slices based on types of data dependences. Based on the new approach, we define an incremental slicing technique that computes a slice in multiple steps. We present empirical results to illustrate the sizes of incremental slices and the potential usefulness of incremental slicing for debugging.

Software products are often released with missing functionality, errors, or incompatibilities that may result in failures, inferior performances, or user dissatisfaction. In previous work, we presented the Gamma approach, which facilitates remote analysis and measurement of deployed software and permits gathering of program-execution data from the field. In this paper, we investigate the use of the Gamma approach to support and improve two fundamental tasks performed by software engineers during maintenance: impact analysis and regression testing. We present a new approach that leverages field data to perform these two tasks. The approach is efficient in that the kind of field data that we consider require limited space and little instrumentation. We also present a set of empirical studies that we performed, on a real subject and on a real user population, to evaluate the approach. The results of the studies show that the use of field data is effective and, for the cases considered, can considerably affect the results of dynamic analyses.

Software testing is particularly expensive for developers of high-assurance software, such as software that is produced for commercial airborne systems. One reason for this expense is the Federal Aviation Administration's requirement that test suites be modified condition/decision coverage (MC/DC) adequate. Despite its cost, there is evidence that MC/DC is an effective verification technique and can help to uncover safety faults. As the software is modified and new test cases are added to the test suite, the test suite grows and the cost of regression testing increases. To address the test-suite size problem, researchers have investigated the use of test-suite reduction algorithms, which identify a reduced test suite that provides the same coverage of the software according to some criterion as the original test suite, and test-suite prioritization algorithms, which identify an ordering of the test cases in the test suite according to some criteria or goals. Existing test-suite reduction and prioritization techniques, however, may not be effective in reducing or prioritizing MC/DC-adequate test suites because they do not consider the complexity of the criterion. This paper presents new algorithms for test-suite reduction and prioritization that can be tailored effectively for use with MC/DC. The paper also presents the results of empirical studies of these algorithms.

One of the most expensive and time-consuming components of the debugging process is locating the errors or faults. To locate faults, developers must identify statements involved in failures and select suspicious statements that might contain faults. This paper presents a new technique that uses visualization to assist with these tasks. The technique uses color to visually map the participation of each program statement in the outcome of the execution of the program with a test suite, consisting of both passed and failed test cases. Based on this visual mapping, a user can inspect the statements in the program, identify statements involved in failures, and locate potentially faulty statements. The paper also describes a prototype tool that implements our technique along with a set of empirical studies that use the tool for evaluation of the technique. The empirical studies show that, for the subject we studied, the technique can be effective in helping a user locate faults in a program.

During maintenance, systems are updated to correct faults, improve functionality, and adapt the software to changes in its execution environment. The typical software update process consists of stopping the system to be updated, performing the update of the code, and restarting the system. For systems such as banking and telecommunication software, however the cost of downtime can be prohibitive. The situation is even worse for systems such as air-traffic controllers and life-support software, for which a shut-down is in general not an option. In those cases, the use of some form of on-the-fly program modification is required. In this paper, we present a new technique for dynamic updating of Java software. Our technique is based oil the use of proxy classes and requires no support from the runtime system. The technique allows for updating a running Java program by substituting, adding, and deleting classes. We also present DUSC (dynamic updating through swapping of classes), a tool that we developed and that implements our technique. Finally, we describe an empirical study that we performed to validate the technique of a real Java subject. The results of the study show that our technique can be effectively applied to Java software with only little overhead in both execution time and program size.

Program analyses and optimizations of Java programs require reference information that determines the instances that may be accessed through dereferences. Reference information can be computed using reference analysis. This paper presents a set of studies that evaluate the precision of two existing approaches for identifying instances and one approach for computing reference information in a reference analysis. The studies use dynamic reference information collected during run-time as a lower bound approximation to the precise reference information. The studies measure the precision of an existing approach by comparing the information computed using the approach with the lower bound approximation. The paper also presents case studies that attempt to identify the cases under which an existing approach is not effective. The presented studies provide information that may guide the usage of existing reference-analysis techniques and the development of new reference analysis techniques.

In this paper, we present the GAMMA system, which facilitates remote monitoring of deployed software using a new approach that exploits the opportunities presented by a software product being used by many users connected through a network. GAMMA splits monitoring tasks across different instances of the software, so that partial information can be collected from different users by means of light-weight instrumentation, and integrated to gather the overall monitoring information. This system enables software producers (1) to perform continuous, minimally intrusive analyses of their software's behavior, and (2) to use the information thus gathered to improve and evolve their software.

Recording dynamic information for only a subset of program entities can reduce monitoring overhead and can facilitate efficient monitoring of deployed software. Program entities, such as statements, can be monitored using probes that track the execution of those entities. Monitoring more complicated entities, such as paths or definition-use associations, requires more sophisticated techniques that track not only the execution of the desired entities but also the execution of other entities with which they interact. This paper presents an approach for monitoring subsets of one such program entity---acyclic paths in procedures. Our selective path profiling algorithm computes values for probes that guarantee that the sum of the assigned value along each acyclic path (path sum) in the subset is unique; acyclic paths not in the subset may or may not have unique path sums. The paper also presents the results of studies that compare the number of probes required for subsets of various sizes with the number of probes required for profiling all paths, computed using Ball and Larus' path profiling algorithm. Our results indicate that the algorithm performs well on many procedures by requiring only a small percentage of probes for monitoring the subset.

Software products are often released with missing functionality or errors that result in failures in the field. In previous work, we presented the Gamma technology, which facilitates remote monitoring of deployed software and allows for a prompt reaction to failures. In this paper, we investigate one of the principal technologies on which Gamma is based: software tomography. Software tomography splits monitoring tasks across many instances of the software, so that partial information can be (1) collected from users by means of light-weight instrumentation and (2) merged to gather the overall monitoring information. After describing the technology, we illustrate an instance of software tomography for a specific monitoring task. We also present two case studies that we performed to evaluate the presented technique on a real program. The results of the studies show that software tomography can be successfully applied to collect accurate monitoring information using only minimal instrumentation on each deployed program instance.

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.

Existing methods for handling pointer variables during dataflow analyses can make such analyses inefficient in both time and space because the data-flow analyses must store and propagate large sets of data facts that are introduced by dereferences of pointer variables. This article presents equivalence analysis , a general technique to improve the efficiency of data-flow analyses in the presence of pointer variables. The technique identifies equivalence relations among the memory locations accessed by a procedure, and ensures that two equivalent memory locations share the same set of data facts in a procedure and in the procedures that are called by that procedure. Thus, a data-flow analysis needs to compute the data-flow information for only a representative memory location in an equivalence class. The data-flow information for other memory locations in the equivalence class can be derived from that of the representative memory location. The article also shows the extension to an interprocedural slicing algorithm that uses equivalence analysis to improve the efficiency of the algorithm. Our empirical studies suggest that equivalence analysis may effectively improve the efficiency of many data-flow analyses.

Software testing is particularly expensive for developers of high-assurance software, such as software that is produced for commercial airborne systems. One reason for this expense is the Federal Aviation Administration's requirement that test suites be modified condition/decision coverage (MC/DC) adequate. Despite its cost, there is evidence that MC/DC is an effective verification technique, and can help to uncover safety faults. As the software is modified and new test cases are added to the test suite, the test suite grows, and the cost of regression testing increases. To address the test-suite size problem, researchers have investigated the use of test-suite reduction algorithms, which identify a reduced test suite that provides the same coverage of the software, according to some criterion, as the original test suite, and test-suite prioritization algorithms, which identify an ordering of the test cases in the test suite according to some criteria or goals. Existing test-suite reduction and prioritization techniques, however, may not be effective in reducing or prioritizing MC/DC-adequate test suites because they do not consider the complexity of the criterion. The paper presents new algorithms for test-suite reduction and prioritization that can be tailored effectively for use with MC/DC. The paper also presents the results of a case study of the test-suite reduction algorithm.

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.

Program slicing is useful for assisting with many software-maintenance tasks. The presence and frequent usage of pointers in languages such as C causes complex data dependences. To function effectively on such programs, slicing techniques must account for pointer-induced data dependences. Existing slicing techniques do not distinguish data dependences based on their types. This paper presents a new slicing technique, in which slices are computed based on types of data dependences. This new slicing technique offers several benefits and can be exploited in different ways, such as identifying subtle data dependences for debugging, computing reduced-size slices quickly for complex programs, and performing incremental slicing. This paper describes an algorithm for incremental slicing that increases the scope of a slice in steps, by incorporating different types of data dependences at each step. The paper also presents empirical results to illustrate the performance of the technique in practice. The results illustrate that incremental slices can be significantly smaller than complete slices. Finally, the paper presents a case study that explores the usefulness of incremental slicing for debugging.

Regression testing is applied to modified software to provide confidence that the changed parts behave as intended and that the unchanged parts have not been adversely affected by the modifications. To reduce the cost of regression testing, test cases are selected from the test suite that was used to test the original version of the software---this process is called regression test selection. A safe regressiontest -selection algorithm selects every test case in the test suite that may reveal a fault in the modified software. Safe regression-test-selection techniques can help to reduce the time required to perform regression testing because they select only a portion of the test suite for use in the testing but guarantee that the faults revealed by this subset will be the same as those revealed by running the entire test suite. This paper presents the first safe regression-test-selection technique that, based on the use of a suitable representation, handles the features of the Java language. Unlike other safe regression test selection techniques, the presented technique also handles incomplete programs. The technique can thus be safely applied in the (very common) case of Java software that uses external libraries or components

This paper presents extensions to Steensgaard's and Andersen's algorithms to handle Java features. Without careful consideration, the handling of these features may affect the correctness, precision, and efficiency of these algorithms. The paper also presents the results of empirical studies. These studies compare the precision and efficiency of these two algorithms and evaluate the effectiveness of handling Java features using alternative approaches. The studies also evaluate the impact of the points-to information provided by these two algorithms on client analyses that use the information.

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.

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.

To compute accurate information efficiently for programs that use pointer variables, a program analysis must account for the fact that a procedure may access different sets of memory locations when the procedure is invoked under different callsites. This paper presents light-weight context recovery, a technique that can efficiently determine whether a memory location is accessed by a procedure under a specific callsite. The paper also presents a technique that uses this information to improve the precision and efficiency of program analyses. Our empirical studies show that (1) light-weight context recovery can be quite precise in identifying the memory locations accessed by a procedure under a specific call-site and (2) distinguishing memory locations accessed by a procedure under different callsites can significantly improve the precision and the efficiency of program analyses on programs that use pointer variables.

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.

Analysis techniques, such as control flow, data flow, and control dependence, are used for a variety of software engineering tasks, including structural and regression testing, dynamic execution profiling, static and dynamic slicing, and program understanding. To be applicable to programs in languages such as Java and C++, these analysis techniques must account for the effects of exception occurrences and exception handling constructs; failure to do so can cause the analysis techniques to compute incorrect results and, thus, limit the usefulness of the applications that use them. This paper discusses the effects of exception handling constructs on several analysis techniques. The paper presents techniques to construct representations for programs with explicit exception occurrences-exceptions that are raised explicitly through throw statements-and exception handling constructs. The paper presents algorithms that use these representations to perform the desired analyses. The paper also discusses several software engineering applications that use these analyses. Finally, the paper describes empirical results pertaining to the occurrence of exception handling constructs in Java programs and their effect on some analysis tasks.

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.

Program slicing, a technique to compute the subset of program statements that can affect the value of a program variable at a specific program point, is widely used in tools to support maintenance activities. To be useful for supporting these activities, a slicing technique must be sufficiently precise and efficient. Harrold and Ci (1998) proposed a method for improving the efficiency of slicing by reusing slicing information for subsequent slicing. This paper presents an interprocedural slicing algorithm that improves the efficiency and precision of Harrold and Ci's algorithm for programs with pointer variables and recursion. Our empirical results show that our improvements can effectively achieve more reuse in slice computation, for programs with pointers, and can significantly reduce the sizes of slices, for programs with recursion.

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.

Exception-handling constructs provide a mechanism for mixing exceptions and a facility for designating protected code by attaching exception handlers to blocks of code. Despite the frequency of their occurrences, the behavior of exception-handling constructs is often the least understood and poorly tested part of a program. The presence of such constructs introduces new structural elements, such as control-flow paths, in a program. To adequately test such programs, these new structural elements must be considered for coverage during structural testing. In this paper, we describe a class of adequacy criteria that can be used to test the behavior of exception-handling constructs. We present a subsumption hierarchy of the criteria, and illustrate the relationship of the criteria to those found in traditional subsumption hierarchies. We describe techniques for generating the testing requirements for the criteria using our control-flow representations. We also describe a methodology for applying the criteria to unit and integration testing of programs that contain exception-handling constructs.

Existing methods to handle pointer variables during data-flow analyses can make such analyses inefficient both in time and space because the data-flow analyses must store and propagate large sets of data facts that are introduced by dereferences of pointer variable. This paper presents equivalence analysis, a general technique to improve the efficiency of data-flow analyses in the presence of pointers. The technique identifies equivalence relations among the memory locations accessed by a procedure and ensures that two equivalent memory locations share the same set of data facts in a procedure and in the procedures that are called by that procedure. Thus, a data-flow analysis needs to compute the data-flow information only for a representative memory location in an equivalence class. The data-flow information for other memory locations in the equivalence class can be derived from that of the representative memory location. Our empirical studies indicate that equivalence analysis may effectively improve the efficiency of many data-flow analyses.

This paper presents a technique that uses a genetic algorithm for automatic test-data generation. A genetic algorithm is a heuristic that mimics the evolution of natural species in searching for the optimal solution to a problem. In the test-data generation application, the solution sought by the genetic algorithm is test data that causes execution of a given statement, branch, path, or definition–use pair in the program under test. The test-data-generation technique was implemented in a tool called TGen, in which parallel processing was used to improve the performance of the search. To experiment with TGen, a random test-data generator called Random was also implemented. Both Tgen and Random were used to experiment with the generation of test-data for statement and branch coverage of six programs. Copyright © 1999 John Wiley & Sons, Ltd.

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.

To manage the evolution of software systems effectively, software developers must understand software systems, identify and evaluate alternative modification strategies, implement appropriate modifications, and validate the correctness of the modifications. One analysis technique that assists in many of these activities is program slicing. To facilitate the application of slicing to large software systems, we adapted a control flow-based interprocedural slicing algorithm so that it accounts for interprocedural control dependencies not recognized by other slicing algorithms, and reuses slicing information for improved efficiency. Our initial studies suggest that additional slice accuracy and slicing efficiency may be achieved with our algorithm.

We present an SDG for object oriented software that is more precise than previous representations and is more efficient to construct than previous approaches. The new SDG distinguishes data members for different objects, provides a way to represent object parameters, represents the effects of polymorphism on parameters and parameter bindings, represents incomplete classes efficiently, and provides a way to represent class libraries. Based on this system dependence graph, we introduce the concept of object slicing and an algorithm to implement this concept. Object slicing enables the user to inspect the statements in the slice, object-by-object, and is helpful for debugging and impact analysis.

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.

Analysis techniques, such as control flow, data flow, and control dependence, are used for a variety of maintenance tasks, including regression testing, dynamic execution profiling, and static and dynamic slicing. To be applicable to programs in languages, such as Java and C++ however, these analysis techniques should, to the extent possible, account for the effects of exception occurrences and exception handling constructs. The paper presents techniques to construct intraprocedural and interprocedural representations on which existing techniques can be performed and demonstrates their applicability to several maintenance tasks.

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.

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.

After changes are made to a previously tested program, a goal of regression testing is to perform retesting based on the modifications while maintaining the same testing coverage as completely retesting the program. This paper presents a novel approach to data flow based regression testing that uses slicing algorithms for the explicit detection of definition-use associations that are affected by a program change. An important benefit of this slicing technique is that, unlike previous techniques, neither data flow history nor recomputation of data flow for the entire program is required to detect affected definition-use associations. The program changes drive the recomputation of the required partial data flow through slicing. Another advantage is that the technique achieves the same testing coverage with respect to the affected definition-use associations as a complete retest of the program, without maintaining a test suite. Thus, the overhead of maintaining and updating a test suite is eliminated.

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.>

We present a fault classification scheme and a fault seeding method that is based on the manifestation of faults in the program dependence graph (PDG). We enhance the domain/computation fault classification scheme to further characterize faults as structural and statement level, depending on the differences between the PDG for the original program and the PDG for the faulty program. Structural faults correspond to differences in the control dependence or data dependence information in the PDGs, whereas statement level faults correspond to differences in the information within PDG nodes. We perform transformations on the PDG to produce the different types of faults described in our PDG-based fault classification scheme. To demonstrate the usefulness of our technique, we implemented a fault seeder to embed faults into C programs. We are using our fault seeder to experiment with the effectiveness of unit testing techniques, and are investigating the application of our fault seeder for formulating a fault based testing method.>

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.

The dependencies that exist among definitions and uses of variables in a program are required by many language-processing tools. This paper considers the computation of definition-use and use-definition chains that extend across procedure boundaries at call and return sites. Intraprocedural definition and use information is abstracted for each procedure and is used to construct an interprocedural flow graph. This intraprocedural data-flow information is then propagated throughout the program via the interprocedural flow graph to obtain sets of reaching definitions and/or reachable uses for reach interprocedural control point, including procedure entry, exit, call, and return. Interprocedural definition-use and/or use-definition chains are computed from this reaching information. The technique handles the interprocedural effects of the data flow caused by both reference parameters and global variables, while preserving the calling context of called procedures. Additionally, recursion, aliasing, and separate compilation are handled. The technique has been implemented using a Sun-4 Workstation and incorporated into an interprocedural data-flow tester. Results from experiments indicate the practicality of the technique, both in terms of the size of the interprocedural flow graph and the size of the data-flow sets.

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.

Mutation analysis is a powerful technique for assessing and improving the quality of test data used to unit test software. Unfortunately, current automated mutation analysis systems suffer from severe performance problems. This paper presents a new method for performing mutation analysis that uses program schemata to encode all mutants for a program into one metaprogram, which is subsequently compiled and run at speeds substantially higher than achieved by previous interpretive systems. Preliminary performance improvements of over 300% are reported. This method has the additional advantages of being easier to implement than interpretive systems, being simpler to port across a wide range of hardware and software platforms, and using the same compiler and run-time support system that is used during development and/or deployment.

Live range splitting techniques divide the live ranges of variables into live range segments to improve global register allocation. We present a new technique for live range splitting called load/store range analysis. This analysis localizes the profits and the register requirements of every access to every variable to provide a fine granularity of candidates for register allocation. Load/Store range analysis is based on the data flow analysis algorithm for def-use chaining. Experiments on a small suite of C and FORTRAN benchmark programs show that a graph coloring register allocator operating on load/store ranges often provides better allocations than the same allocator operating on live ranges. Experimental results also show that the computational cost of using load/store ranges for register allocation is moderately more than the cost of using live ranges. 1 Introduction The goal of register allocation is to map variables in an intermediate language program to either registers or mem...

This paper presents a technique to select a representative set of test cases from a test suite that provides the same coverage as the entire test suite. This selection is performed by identifying, and then eliminating, the redundant and obsolete test cases in the test suite. The representative set replaces the original test suite and thus, potentially produces a smaller test suite. The representative set can also be used to identify those test cases that should be rerun to test the program after it has been changed. Our technique is independent of the testing methodology and only requires an association between a testing requirement and the test cases that satisfy the requirement. We illustrate the technique using the data flow testing methodology. The reduction that is possible with our technique is illustrated by experimental results.

Unified interprocedural graph (UIG) that extracts the important features of existing program representations and adds new information to provide an integrated representation for maintenance tasks is presented. Algorithms that were developed for previous representations are adapted to use the UIG by identifying the subset of nodes and edges in the UIG required for that computation. Newly developed algorithms can use the UIG since it contains data flow, control flow, data dependence, and control dependence information. The main benefits of this approach are the reduction in storage space since individual representations are not kept, the savings in maintenance time of a single representation over the individual representations, and the convenience of accessing a single program representation without increase in access time. A single program representation also assists in program understanding since relationships among program elements are incorporated into one graph.>

Although there is much interest in creating libraries of well-designed, thoroughly-tested classes that can be confidently reused for many applications, few class testing techniques have been developed.In this paper, we present a class testing technique that exploits the hierarchical nature of the inheritance relation to test related groups of classes by reusing the testing information for a parent class to guide the testing of a subclass.We initially test base classes having no parents by designing a test sui~e that tests each member fmction individually and also tests the interactions among member functions.To &sign a test suite for a subclass, our algorithm incrementally up~tes the history of its parent to reject both the modijied, inherited attributes and the subclass's newly akjined attributes.Only those new attributes or @'cted, inherited attributes are tested and the parent class' test suites are reused, if possible, for the testing.Inherited attributes are retested in their new context in a subclass by testing their interactions with the subclass's newly dejined attributes.We have incorporated a data jlow tester into Free Software Founalzion, Inc's C-++ compilers and are using it for our experimentation.

The authors present a novel approach to data-flow-based regression testing that uses slicing type algorithms to explicitly detect definition-use pairs that are affected by a program change. An important benefit of the slicing technique is that, unlike previous techniques, no data flow history is needed nor is the recomputation of data flow for the entire program required to detect affected definition-use pairs. The program changes drive the recomputation of the required partial data flow through slicing. Another advantage is that the proposed technique achieves the same testing coverage as a complete retest of the program without the need for maintaining and updating a test suite.>

The authors present a novel system for re-engineering and retesting programs for execution in a shared memory multiprocessor environment. The system consists of two main components: a compiler that reengineers a sequential program for execution on shared memory multiprocessors, and a data-flow tester for the parallelized code. Several important enhancements to an existing parallelizing compiler have been made, including an efficient intermediate program representation on which data-flow analysis is performed. The compiler also inserts probes in a parallelized program to make it testable in its new environment. By inserting the probes in appropriate places, a compact execution trace is produced. The data-flow tester uses a new dynamic data-flow analysis algorithm to determine the test case coverage.>

A unified interprocedural program representation, the unified interprocedural graph (UIG) is presented; it combines the features of existing program representations to permit access to information for modifying, understanding, analyzing, testing and debugging. The algorithms developed for each of these independent graphs are adapted to use this unified representation by identifying the subset of nodes and edges required for that computation. The UIG can be incorporated into a maintenance environment and the associated algorithms used to build program maintenance tools. The authors present a brief overview of the graph representations on which the UIG is based and illustrate them with an example. The algorithms that use these graphs to gather the interprocedural information are described.>

As a result of modifications to a program during the maintenance phase, the size of a test suite used for regression testing can become unmanageable. The authors present a technique that selects from a test suite a representative set of test cases that provides the same measure of coverage as the test suite. This selection is performed by the identification of the redundant and obsolete test cases in the test suite. The representative set can be used to reduce the size of the test suite by substituting for the test suite. The representative set can also be used to determine those test cases that should be rerun to test the program after it has been changed. The technique is independent of the testing methodology and only requires an association between each testing requirement and the test cases that satisfy the requirement. The technique is illustrated by means of the data flow testing methodology. Experimental studies are being performed that demonstrate the effectiveness of the technique.>

An incremental testing system to aid in unit testing during the maintenance stage is described. Based on data-flow testing, the system is designed for use in a programming environment; it shares common information and techniques with tools typically found in programming environments. In response to a change in a module, the incremental tester reuses the analysis and test cases from the previous testing session. The analysis is incrementally updated to determine areas of the program that must be retested. From the updates, the tester determines which test cases must be rerun, which may be eliminated, and whether the test cases are sufficient for the changed program.>