Impact analysis not only assists developers with change planning and management, but also facilitates a range of other client analyses, such as testing and debugging. In particular, for developers working in the context of specific program executions, dynamic impact analysis is usually more desirable than static approaches, as it produces more manageable and relevant results with respect to those concrete executions. However, existing techniques for this analysis mostly lie on two extremes: either fast, but too imprecise, or more precise, yet overly expensive. In practice, both more cost-effective techniques and variable cost-effectiveness trade-offs are in demand to fit a variety of usage scenarios and budgets of impact analysis. This article aims to fill the gap between these two extremes with an array of cost-effective analyses and, more broadly, to explore the cost and effectiveness dimensions in the design space of impact analysis. We present the development and evaluation of D ia P ro , a framework that unifies a series of impact analyses, including three new hybrid techniques that combine static and dynamic analyses. Harnessing both static dependencies and multiple forms of dynamic data including method-execution events, statement coverage, and dynamic points-to sets, D ia P ro prunes false-positive impacts with varying strength for variant effectiveness and overheads. The framework also facilitates an in-depth examination of the effects of various program information on the cost-effectiveness of impact analysis. We applied D ia P ro to ten Java applications in diverse scales and domains, evaluating it thoroughly on both arbitrary and repository-based queries from those applications. We show that the three new analyses are all significantly more effective than existing alternatives while remaining efficient, and the D ia P ro framework, as a whole, provides flexible cost-effectiveness choices for impact analysis with the best options for variable needs and budgets. Our study results also suggest that hybrid techniques tend to be much more cost-effective than purely dynamic approaches, in general, and that statement coverage has mostly stronger effects than dynamic points-to sets on the cost-effectiveness of dynamic impact analysis, while static dependencies have even stronger effects than both forms of dynamic data.

Software is constantly changing. To ensure the quality of this process, when preparing to change a program, developers must first identify the main consequences and risks of modifying the program locations they intend to change. This activity is called change-impact analysis. However, existing impact analysis suffers from two major problems: coarse granularity and large size of the resulting impact sets. Finer-grained analyses such as slicing give more detailed impact sets which, however, are also even larger in size. While various impact-set reduction approaches have been proposed at different levels of granularity, the challenge persists as very-large impact sets are still produced, impeding the adoption of impact analysis due to the great costs of inspecting those impact sets. To address these challenges, we present a novel dynamic-analysis technique called SensA which combines sensitivity analysis and execution differencing. SensA not only provides fine-grained (statement-level) impact sets but also prioritizes potential impacts via semantic-dependence quantification for program slices. We evaluated the benefits of impact prioritization using SensA with respect to static and dynamic forward slicing via an extensive empirical study of open-source Java applications and three case studies. Our results show that SensA can offer much better cost-effectiveness than slicing in assisting developers with impact inspection and fault cause-effect understanding.

While empowering a wide range of software engineering tasks, the traditional fine-grained software dependence (TSD) model can face great scalability challenges that hinder its applications. Many dependence abstraction approaches have been proposed, yet most of them either target very specific clients or model partial dependencies only, while others have not been fully evaluated for their accuracy with respect to the TSD model, especially in approximating forward dependencies on object-oriented programs. To fill this gap, we present a new dependence abstraction called the method dependence graph (MDG) that approximates the TSD model at method level, and compare it against a recent TSD abstraction, called the Static-Exectue-After (SEA), concerning forward-dependence approximation. We also evaluate the cost-effectiveness of both approaches in the application context of impact analysis. Our results show that the MDG can approximate TSD safely, for method-level forward dependence at least, with little loss of precision yet huge gain in efficiency, and for the same purpose, while both are safe, the MDG can achieve significantly higher precision than SEA at practical costs.

Dynamic impact analysis can greatly assist developers with managing software changes by focusing their attention on the effects of potential changes relative to concrete program executions. While dependence-based dynamic impact analysis (DDIA) provides finer-grained results than traceability-based approaches, traditional DDIA techniques often produce imprecise results, incurring excessive costs thus hindering their adoption in many practical situations. In this paper, we present the design and evaluation of a DDIA framework and its three new instances that offer not only much more precise impact sets but also flexible cost-effectiveness options to meet diverse application needs such as different budgets and levels of detail of results. By exploiting both static dependencies and various dynamic information including method-execution traces, statement coverage, and dynamic points-to data, our techniques achieve that goal at reasonable costs according to our experiment results. Our study also suggests that statement coverage has generally stronger effects on the precision and cost-effectiveness of DDIA than dynamic points-to data.

We present the design and implementation of TRACERJD, a toolkit devoted to dynamic dependence analysis via fine-grained whole-program dependence tracing. TRACERJD features a generic framework for efficient offline analysis of dynamic dependencies, including those due to exception-driven control flows. Underlying the framework is a hierarchical trace indexing scheme by which TRACERJD maintains the relationships among execution events at multiple levels of granularity while capturing those events at runtime. Built on this framework, several application tools are provided as well, including a dynamic slicer and a performance profiler. These example applications also demonstrate the flexibility and ease with which a variety of client analyses can be built based on the framework. We tested our toolkit on four Java subjects, for which the results suggest promising efficiency of TRACERJD for its practical use in various dependence-based tasks.

Impact analysis determines the effects that the behavior of program entities, or changes to them, can have on the rest of the system. Dynamic impact analysis is one practical form that computes smaller impact sets than static alternatives for concrete sets of executions. However, existing dynamic approaches can still produce impact sets that are too large to be useful. To address this problem, we present a novel dynamic impact analysis called DIVER that exploits static dependencies to identify runtime impacts much more precisely without reducing safety and at acceptable costs. Our preliminary empirical evaluation shows that DIVER can significantly increase the precision of dynamic impact analysis.

Sensitivity analysis determines how a system responds to stimuli variations, which can benefit important software-engineering tasks such as change-impact analysis. We present SENSA, a novel dynamic-analysis technique and tool that combines sensitivity analysis and execution differencing to estimate the dependencies among statements that occur in practice. In addition to identifying dependencies, SENSA quantifies them to estimate how much or how likely a statement depends on another. Quantifying dependencies helps developers prioritize and focus their inspection of code relationships. To assess the benefits of quantifying dependencies with SENSA, we applied it to various statements across Java subjects to find and prioritize the potential impacts of changing those statements. We found that SENSA predicts the actual impacts of changes to those statements more accurately than static and dynamic forward slicing. Our SENSA prototype tool is freely available for download.

Dynamic slicing is a practical and popular analysis technique used in various software-engineering tasks. Dynamic slicing is known to be incomplete because it analyzes only a subset of all possible executions of a program. However, it is less known that its results may inaccurately represent the dependencies that occur in those executions. Some researchers have identified this problem and developed extensions such as relevant slicing, which incorporates static information. Yet, dynamic slicing continues to be widely used, even though the extent of its inaccuracy is not well understood, which can affect the benefits of this analysis. In this paper, we present an approach to assess the accuracy of forward dynamic slices, which are used in software maintenance and evolution tasks. Because finding all actual dependencies is an undecidable problem, our approach instead computes bounds of the precision and recall of forward dynamic slices. Our approach uses sensitivity analysis and execution differencing to find a subset of all program statements that truly depend at runtime on another statement. Using this approach, we studied the accuracy of many forward dynamic slices from a variety of Java applications. Our results show that forward dynamic slicing can have low recall -- for dependencies in the analyzed executions -- and some potential imprecision. We also conducted a case study that shows how this inaccuracy affects a software maintenance task. To the best of our knowledge, ours is the first work that quantifies the intrinsic limitations of dynamic slicing.

Program slicing is a popular but imprecise technique for identifying which parts of a program affect or are affected by a particular value. A major reason for this imprecision is that slicing reports all program statements possibly affected by a value, regardless of how relevant to that value they really are. In this paper, we introduce quantitative slicing (q-slicing), a novel approach that quantifies the relevance of each statement in a slice. Q-slicing helps users and tools focus their attention first on the parts of slices that matter the most. We present two methods for quantifying slices and we show the promise of q-slicing for a particular application: predicting the impacts of changes.

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.

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.

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

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

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 A framework is a high‐level solution for the reuse of software pieces, a step forward in simple library‐based reuse, that allows the sharing of not only common functions but also the generic logic of a domain application. It also ensures a better level of quality for the final product, given the fact that an important fraction of the application is already found within the framework and has therefore already been tested. This case study takes the systematic generation of hot‐spot subsystems approach as a reference point to describe the underlying concepts in the design of a framework for the development of 2D action videogames for low‐performance machines. The main goal of this paper is to show the applicability of framework‐based reuse to videogames. Both standard and framework‐based game implementations are compared and the results are analysed. Special attention is paid to the (potential) benefits that the use of frameworks brings to the fulfillment of maintenance tasks along the game's life cycle, a stage that normally consumes most resources in software projects. At the end of the paper, based on the implementation results, this study shows the predicted conditions under which building a framework is cost effective for the development of videogames similar to the ones from the studied domain. Copyright © 2001 John Wiley & Sons, Ltd.