Despite the fact that distributed systems have become a crucial aspect of modern technology and support many of the software systems that enable modern life, developers experience challenges in performing regression testing of these systems. Existing solutions for testing distributed systems are often either: (1) specialized testing environments that are created specifically for each system by its development team, which requires substantial effort for each team, with little-to-no sharing of this effort across teams; or (2) randomized injection tools that are often computationally expensive and offer no guarantees of preventing regressions, due to their randomness. The challenge of providing a generalized and practical solution to trigger bugs for reproducing and demonstrating failures, as well as to guard against regressions, is largely unaddressed. In this work, we present RediI, an infrastructure for supporting regression testing of distributed systems. RediI contains a dataset of real bugs on common distributed systems, along with a generalizable testing framework RediT that enables developers to write tests that can reproduce failures by providing ways to deterministically control distributed execution. In addition to the real failures in RediIfrom multiple distributed systems, RediT provides a reusable, programmable, platform-agnostic, deterministic testing framework for developers of distributed systems. It can help automate the running of such tests, for both practitioners and researchers. We demonstrate RediT with 63 bugs that we selected in Jira on 7 large and widely used distributed systems. Our case studies show that RediI can be used to allow developers to write tests that effectively reproduce failures on distributed systems and generate specific scenarios for regression testing, as well as providing deterministic failure injection that can help developers and researchers to better understand deterministic failures that may occur in distributed systems in the future. Additionally, our studies show that RediI is efficient for real-world system regression testing, providing a powerful tool for developers and researchers in the field of distributed-system testing.

Mutation testing was proposed to identify weaknesses in test suites by repeatedly generating artificially faulty versions of the software (i.e., mutants) and determining if the test suite is sufficient to detect them (i.e., kill them). When the tests are insufficient, each surviving mutant provides an opportunity to improve the test suite. We conducted a study and found that many such surviving mutants (up to 84% for the subjects of our study) are detectable by simply augmenting existing tests with additional assertions, or assertion amplification. Moreover, we find that many of these mutants are detectable by multiple existing tests, giving developers options for how to detect them. To help with these challenges, we created a technique that performs memory-state analysis to identify candidate assertions that developers can use to detect the surviving mutants. Additionally, we build upon prior research that identifies “crossfiring” opportunities - tests that coincidentally kill multiple mutants. To this end, we developed a theoretical model that describes the varying granularities that crossfiring can occur in the existing test suite, which provide opportunities and options for how to kill surviving mutants. We operationalize this model to an accompanying technique that optimizes the assertion amplification of the existing tests to crossfire multiple mutants with fewer added assertions, optionally concentrated within fewer tests. Our experiments show that we can kill all surviving mutants that are detectable with existing test data with only 1.1% of the identified assertion candidates, and increasing by a factor of 6x, on average, the number of killed mutants from amplified tests, over tests that do not crossfire.

In this work, we characterize a novel test-code smell—Disjoint Assertion Tangle (DAT)—which occurs when a test method verifies multiple, logically unrelated behaviors that can be separated. We propose a program analysis-based approach that automatically detects DAT and refactors DAT tests into separate focused test methods. We implemented this approach as a tool called U2W. By separating unrelated testing logic, U2W enhances readability, maintainability, and fault localization, while exposing hidden test clones and duplicated code. It then seizes these opportunities by converting structurally similar tests into compact, parameterized unit tests (PUTs), reducing redundancy and enabling more scalable, extensible test designs. To evaluate our approach and tool, we conducted a number of evaluations: (1) a large-scale, quantitative study to study the prevalence of the test smell and the effects of their refactoring, (2) a user survey to assess developers’ opinions and preferences of the unrefactored and refactored test code, and (3) pull requests that were issued to original project maintainers to assess the acceptability of our refactorings. Our quantitative study was conducted on 42,334 tests across 49 open-source projects. We found the DAT smell in 95.9% of the subject projects, affecting an average of 8.59% of analyzed tests. In total, we identified and refactored 3,638 smelly tests, untangled them into 31,837 test-execution logics, and then weaved 14,343 of them into 1,713 extensible PUT methods. These refactorings reduced the executable test-code lines in smelly tests by an average of 36.33%. Our user survey involving 49 industrial and academic participants demonstrated strong preference for our refactored test cases over their original, unrefactored versions. Additionally, we submitted 19 pull requests based on our automated refactorings; 16 of these were accepted by project maintainers. These results suggest that U2W effectively improves test-suite quality, and validate our novel test smell aligns closely with developers’ intuitions and practices.

Developers often insert temporary “print” or “log” instructions into their code to help them better understand runtime behavior, usually when the code is not behaving as they expected. Despite the fact that such monitoring instructions, or “ad-hoc logs,” are so commonly used by developers, there is almost no existing literature that studies developers’ practices in how they use them. This paucity of knowledge of the use of these ephemeral logs may be largely due to the fact that they typically only exist in the developers’ local environments and are removed before they commit their code to their revision control system. In this work, we overcame this challenge by observing that developers occasionally mistakenly forget to remove such instructions before committing, and then they remove them shortly later. Additionally, we further studied such developer logging practices by watching and analyzing live-streamed coding videos. Through these empirical approaches, we presented where, how, and why developers use ad-hoc logs to better understand their code and its execution. We collected 27 GB of accidental commits that removed 548,880 ad-hoc logs in JavaScript from GitHub Archive repositories to provide the first large-scale dataset and empirical studies on ad-hoc logging practices. Our results revealed several illuminating findings, including a particular propensity for developers to use ad-hoc logs in asynchronous and callback functions. Our findings provided both empirical evidence and a valuable dataset for researchers and tool developers seeking to enhance ad-hoc logging practices, and potentially deepen our understanding of developers’ practices towards understanding of software’s runtime behaviors.

The mechanics of how a fault reveals itself as a test failure is of keen interest to software researchers and practitioners alike. An improved understanding of how faults translate to failures can guide improvements in broad facets of software testing, ranging from test suite design to automated program repair, which are premised on the understanding that the presence of faults would alter some test executions.

Skeletal program enumeration (SPE) can generate a great number of test programs for validating the correctness of compilers or interpreters. The classic SPE generates programs by exhaustively enumerating all possible variable usage patterns into a given syntactic structure. Even though it is capable of producing many test programs, the exhaustive enumeration strategy generates a large number of invalid programs, which may waste plenty of testing time and resources. To address the problem, this article proposes a tree-based SPE technique. Compared to the state-of-the-art, the key merit of the tree-based approach is that it allows us to take the dependency information into consideration when producing test programs and, thus, make it possible to (1) directly generate non-equivalent programs and (2) apply dominance relations to eliminate invalid test programs that have undefined variables. Hence, our approach significantly saves the cost of the naïve SPE approach. We have implemented our approach into an automated testing tool, IFuzzer , and applied it to test eight different implementations of Python interpreters, including CPython, PyPy, IronPython, Jython, RustPython, GPython, Pyston, and Codon. In three months of fuzzing, IFuzzer detected 142 bugs, of which 87 have been confirmed to be previously unknown bugs, of which 34 have been fixed. Compared to the state-of-the-art SPE techniques, IFuzzer takes only 61.0% of the time cost given the same number of testing seeds and improves 5.3% source code function coverage in the same time budget of testing.

Mutation testing has been used and studied for over four decades as a method to assess the strength of a test suite. This technique adds an artificial bug (i.e., a mutation) to a program to produce a mutant, and the test suite is run to determine if any of its test cases are sufficient to detect this mutation (i.e., kill the mutant). In this situation, a test case that fails is the one that kills the mutant. However, little is known about the nature of these kills. In this paper, we present an empirical study that investigates the nature of these kills. We seek to answer questions, such as: How are test cases failing so that they contribute to mutant kills? How many test cases fail for each killed mutant, given that only a single failure is required to kill that mutant? How do program crashes contribute to kills, and what are the origins and nature of these crashes? We found several revealing results across all subjects, including the substantial contribution of "crashes" to test failures leading to mutant kills, the existence of diverse causes for test failures even for a single mutation, and the specific types of exceptions that commonly instigate crashes. We posit that this study and its results should likely be taken into account for practitioners in their use of mutation testing and interpretation of its mutation score, and for researchers who study and leverage mutation testing in their future work.

Crowdsourced testing has been widely used to improve software quality as it can detect various bugs and simulate real usage scenarios. Crowdsourced workers perform tasks on crowdsourcing platforms and present their experiences as test reports, which naturally generates an overwhelming number of test reports. Therefore, inspecting these reports becomes a time-consuming yet inevitable task. In recent years, many text-based prioritization and clustering techniques have been proposed to address this challenge. However, in mobile testing, test reports often consist of only short test descriptions but rich screenshots. Compared with the uncertainty of textual information, well-defined screenshots can often adequately express the mobile application’s activity views. In this paper, by employing image-understanding techniques, we propose an approach for clustering crowdsourced test reports of mobile applications based on both textual and image features to assist the inspection procedure. We employ Spatial Pyramid Matching (SPM) to measure the similarity of the screenshots and use the natural-language-processing techniques to compute the textual distance of test reports. To validate our approach, we conducted an experiment on 6 industrial crowdsourced projects that contain more than 1600 test reports and 1400 screenshots. The results show that our approach is capable of outperforming the baselines by up to 37 percent regarding the APFD metric. Further, we analyze the parameter sensitivity of our approach and discuss the settings for different application scenarios.

Existing IDE-based tools that are available to developers make understanding software testing difficult for a software system, for both granular tasks (e.g., answering questions such as, "which test cases execute this method?") and global tasks (e.g., answering questions such as, "what is the proportion of unit tests to system tests?"). IDE-based tools typically support local, file-based views of a project’s test suite, and rarely offer a global overview. Global overviews can provide a larger context for a method’s execution by test cases; help identify other similar, or related methods; and even reveal similarity between individual tests. This work approaches such challenges with a novel, interactive, matrix-based visual interface that provides a global overview of a software project’s test suite, specifically in the context of the methods available in the project’s codebase. Through a series of interactive functions to sort, filter, query, and explore a test-matrix visualization, we demonstrate how developers can effectively answer questions about their project’s test suite, and the code executed by such tests. Our evaluations, performed on four real-world software systems, show that the interactive visualization assisted developers to answer questions about software tests and the code they execute. Further, the visualization consistently outperforms traditional development tools, both in accuracy and time taken to complete software-engineering tasks.

Open source developers, particularly the elite developers who own the administrative privileges for a project, maintain a diverse portfolio of contributing activities. They not only commit source code but also exert significant efforts on other communicative, organizational, and supportive activities. However, almost all prior research focuses on specific activities and fails to analyze elite developers’ activities in a comprehensive way. To bridge this gap, we conduct an empirical study with fine-grained event data from 20 large open source projects hosted on G IT H UB . We investigate elite developers’ contributing activities and their impacts on project outcomes. Our analyses reveal three key findings: (1) elite developers participate in a variety of activities, of which technical contributions (e.g., coding) only account for a small proportion; (2) as the project grows, elite developers tend to put more effort into supportive and communicative activities and less effort into coding; and (3) elite developers’ efforts in nontechnical activities are negatively correlated with the project’s outcomes in terms of productivity and quality in general, except for a positive correlation with the bug fix rate (a quality indicator). These results provide an integrated view of elite developers’ activities and can inform an individual’s decision making about effort allocation, which could lead to improved project outcomes. The results also provide implications for supporting these elite developers.

No abstract available.

Crowdsourced testing has been widely adopted to improve the quality of various software products. Crowdsourced workers typically perform testing tasks and report their experiences through test reports. While the crowdsourced test reports provide feedbacks from real usage scenarios, inspecting such a large number of reports becomes a time-consuming yet inevitable task. To improve the efficiency of this task, existing widely used issue-tracking systems, such as JIRA, Bugzilla, and Mantis, have provided keyword-search-based methods to assist users in identifying duplicate test reports. However, on mobile devices (such as mobile phones), where the crowdsourced test reports often contain insufficient text descriptions but instead rich screenshots, these text-analysis-based methods become less effective because the data has fundamentally changed. In this paper, instead of focusing on only detecting duplicates based on textual descriptions, we present CTRAS: a novel approach to leveraging duplicates to enrich the content of bug descriptions and improve the efficiency of inspecting these reports. CTRAS is capable of automatically aggregating duplicates based on both textual information and screenshots, and further summarizes the duplicate test reports into a comprehensive and comprehensible report. To validate CTRAS, we conducted quantitative studies using more than 5000 test reports, collected from 12 industrial crowdsourced projects. The experimental results reveal that CTRAS can reach an accuracy of 0.87, on average, regarding automatically detecting duplicate reports, and it outperforms the classic Max-Coverage-based and MMR summarization methods under Jensen Shannon divergence metric. Moreover, we conducted a task-based user study with 30 participants, whose result indicates that CTRAS can save nearly 30% time cost on average without loss of correctness.

In this paper, we present CTRAS, a tool for automatically aggregating and summarizing duplicate crowdsourced test reports on the fly. CTRAS can automatically detect duplicates based on both textual information and the screenshots, and further aggregates and summarizes the duplicate test reports. CTRAS provides end users with a comprehensive and comprehensible understanding of all duplicates by identifying the main topics across the group of aggregated test reports and highlighting supplementary topics that are mentioned in subgroups of test reports. Also, it provides the classic tool of issue tracking systems, such as the project-report dashboard and keyword searching, and automates their classic functionalities, such as bug triaging and best fixer recommendation, to assist end users in managing and diagnosing test reports. Video: https://youtu.be/PNP10gKIPFs

Classification techniques have been used in software-engineering research to perform tasks such as categorizing software executions. Traditionally, existing work has proposed single-label failure classification techniques, in which the training and subsequent executions are labeled with a singular fault attribution. Although such approaches have received substantial attention in research on automated software engineering, in reality, recent work shows that the assumption of such a single attribution is often unrealistic: in practice, the inherent characteristics of software behavior, such as multiple faults that contribute to failures and fault interactions, may negatively influence the effectiveness of these techniques. To relax this unrealistic assumption, in the machine learning field, researchers have proposed new approaches for multi-label classification. However, the effectiveness and efficiency of such approaches varies widely based upon application domains. In this paper, we empirically investigate the performance of these new approaches on the failure classification task under different application settings. We conducted experiments using eight classification techniques on five subject programs with more than 8,000 faulty versions to investigate how each such technique accounts for the intricacies of software behavior. Our experimental results show that multi-label techniques provide improved accuracy over single-label. We also evaluated the efficiency of the training and prediction phases of each technique, and offer guidance as to the applicability for each technique for different usage contexts.

Understanding the dynamic behavior of a software system is one of the most important and time-consuming tasks for today's software maintainers. In practice, understanding the inner workings of software requires studying the source code and documentation and inserting logging code in order to map high-level descriptions of the program behavior with low-level implementation, i.e., the source code. Unfortunately, for large codebases and large log files, such cognitive mapping can be quite challenging. To bridge the cognitive gap between the source code and detailed models of program behavior, we propose a fully automatic approach to present a semantic abstraction with different levels of functional granularity from full execution traces. Our approach builds multi-level abstractions and identifies frequent behaviors at each level based on a number of execution traces, and then, it labels phases within individual execution traces according to the identified major functional behaviors of the system. To validate our approach, we conducted a case study on a large-scale subject program, Javac, to demonstrate the effectiveness of the mining result. Furthermore, the results of a user study demonstrate that our approach is capable of presenting users a high-level comprehensible abstraction of execution behavior. Based on a real world subject program the participants in our user study were able to achieve a mean accuracy of 70%.

Crowdsourced software testing has been shown to be capable of detecting many bugs and simulating real usage scenarios. As such, it is popular in mobile-application testing. However in mobile testing, test reports often consist of only some screenshots and short text descriptions. Inspecting and under-standing the overwhelming number of mobile crowdsourced test reports becomes a time-consuming but inevitable task. The paucity and potential inaccuracy of textual information and the well-defined screenshots of activity views within mobile applications motivate us to propose a novel technique to assist developers in understanding crowdsourced test reports by automatically describing the screenshots. To reach this goal, in this paper, we propose a fully automatic technique to generate descriptive words for the well-defined screenshots. We employ the test reports written by professional testers to build up language models. We use the computer-vision technique, namely Spatial Pyramid Matching (SPM), to measure similarities and extract features from the screenshot images. The experimental results, based on more than 1000 test reports from 4 industrial crowdsourced projects, show that our proposed technique is promising for developers to better understand the mobile crowdsourced test reports.

Existing software-history techniques represent source-code evolution as an absolute and unambiguous mapping of lines of code in prior revisions to lines of code in subsequent revisions. However, the true evolutionary lineage of a line of code is often complex, subjective, and ambiguous. As such, existing techniques are predisposed to, both, overestimate and underestimate true evolution lineage. In this paper, we seek to address these issues by providing a more expressive model of code evolution, the fuzzy history graph, by representing code lineage as a continuous (i.e., fuzzy) metric rather than a discrete (i.e., absolute) one. Using this more descriptive model, we additionally provide a novel multi-revision code-history analysis - fuzzy history slicing. In our experiments over three real-world software systems, we found that the fuzzy history graph provides a tunable balance of precision and recall, and an overall improved accuracy over existing code-evolution models. Furthermore, we found that the use of such a fuzzy model of history provided improved accuracy for code-history analysis tasks.

Software engineers construct modern-day software applications by building on existing software libraries and components that they necessarily do not author themselves. Thus, contemporary software applications rely heavily on existing standard and third-party libraries for their execution and behavior. As such, effective runtime analysis of such a software application’s behavior is met with new challenges. To perform dynamic analysis of a software application, all transitively dependent external libraries must also be monitored and analyzed at each layer of the software application’s call stack. However, monitoring and analyzing large and often numerous external libraries may prove to be prohibitively expensive. Moreover, an overabundance of library-level analyses may obfuscate the details of the actual software application’s dynamic behavior. In other words, the extensive use of existing libraries by a software application renders the results of its dynamic analysis both expensive to compute and difficult to understand. We model software component behavior as dynamically observed data- and control dependencies between inputs and outputs of a software component. Such data- and control dependencies are monitored at a fine-grain instruction-level and are collected as dynamic execution traces for software runs. As an approach to address the complexities and expenses associated with analyzing dynamically observable behavior of software components, we summarize and reuse the data- and control dependencies between the inputs and outputs of software components. Dynamically monitored data- and control dependencies, between the inputs and outputs of software components, upon summarization are called dynamic dependence summaries . Software components, equipped with dynamic dependence summaries, afford the omission of their exhaustive runtime analysis. Nonetheless, the reuse of dependence summaries would necessitate the abstraction of any concrete runtime information enclosed within the summary, thus potentially causing a loss in the information modeled by the dependence summary. Therefore, benefits to the efficiency of dynamic analyses that use such summarization may be afforded with losses of accuracy. As such, we evaluate the potential accuracy loss and the potential performance gain with the use of dynamic dependence summaries. Our results show, on average, a 13× speedup with the use of dynamic dependence summaries, with an accuracy of 90% in a real-world software engineering task.

In crowdsourced software testing, inspecting the large number of test reports is an overwhelming but inevitable software maintenance task. In recent years, to alleviate this task, many text-based test-report classification and prioritization techniques have been proposed. However in the mobile testing domain, test reports often consist of more screenshots and shorter descriptive text, and thus text-based techniques may be ineffective or inapplicable. The shortage and ambiguity of natural-language text information and the well defined screenshots of activity views within mobile applications motivate our novel technique based on using image understanding for multi-objective test-report prioritization. In this paper, by taking the similarity of screenshots into consideration, we present a multi-objective optimization-based prioritization technique to assist inspections of crowdsourced test reports. In our technique, we employ the Spatial Pyramid Matching (SPM) technique to measure the similarity of the screenshots, and apply the natural-language processing technique to measure the distance between the text of test reports. Furthermore, to validate our technique, an experiment with more than 600 test reports and 2500 images is conducted. The experimental results show that image-understanding techniques can provide benefit to test-report prioritization for most applications.

In crowdsourced testing, users can be incentivized to perform testing tasks and report their results, and because crowdsourced workers are often paid per task, there is a financial incentive to complete tasks quickly rather than well. These reports of the crowdsourced testing tasks are called "test reports" and are composed of simple natural language and screenshots. Back at the software-development organization, developers must manually inspect the test reports to judge their value for revealing faults. Due to the nature of crowdsourced work, the number of test reports are often difficult to comprehensively inspect and process. In order to help with this daunting task, we created the first technique of its kind, to the best of our knowledge, to prioritize test reports for manual inspection. Our technique utilizes two key strategies: (1) a diversity strategy to help developers inspect a wide variety of test reports and to avoid duplicates and wasted effort on falsely classified faulty behavior, and (2) a risk strategy to help developers identify test reports that may be more likely to be fault-revealing based on past observations. Together, these strategies form our DivRisk strategy to prioritize test reports in crowd- sourced testing. Three industrial projects have been used to evaluate the effectiveness of test report prioritization methods. The results of the empirical study show that: (1) DivRisk can significantly outperform random prioritization; (2) DivRisk can approximate the best theoretical result for a real-world industrial mobile application. In addition, we provide some practical guidelines of test report prioritization for crowdsourced testing based on the empirical study and our experiences.

Software engineers organize source code into a dominant hierarchy of components and modules that may emphasize various characteristics over runtime behavior. In this way, runtime features may involve cross-cutting aspects of code from multiple components, and some of these features may be emergent in nature, rather than designed. Although source-code modularization assists software engineers to organize and find components, identifying such cross-cutting feature sets can be more difficult. This work presents a visualization that includes a static (i.e., compile-time) representation of source code that gives prominence to clusters of cooperating source-code instructions to identify dynamic (i.e., runtime) features and constituent behaviors within executions of the software. In addition, the visualization animates software executions to reveal which feature clusters are executed and in what order. The result has revealed the principal behaviors of software executions, and those behaviors were revealed to be (in some cases) cohesive, modular source-code structures and (in other cases) cross-cutting, emergent behaviors that involve multiple modules. In this paper, we describe our system (CEREBRO), envisage the uses to which it can be put, and evaluate its ability to reveal emergent runtime features and internal constituent behaviors of execution. We found that: (1) the visualization revealed emergent and commonly occuring functionalities that cross-cut the structural decomposition of the system; (2) four independent judges generally agreed in their interpretations of the code clusters, especially when informed only by our visualization; and (3) interacting with the external interface of an application while simultaneously observing the internal execution facilitated localization of code that implements the features and functionality evoked externally.

Today, many of the research innovations in software visualization and comprehension are evaluated on small-scale programs in a way that avoids actual human evaluation, despite the fact that these techniques are designed to help programmers develop and understand large and complex software. The investments required to perform such human studies often outweigh the need to publish. As such, the goal of this work (and toolkit) is to enable the evaluation of software visualizations of real-life software systems by its actual developers, as well as to understand the factors that influence adoption. The approach is to directly assist practicing software developers with visualizations through open and online collaboration tools. The mechanism by which we accomplish this goal is an online service that is linked through the projects' revision-control and build systems. We are calling this system SPIDER SENSE, and it includes web-based visualizations for software exploration that is supported by tools for mirroring development activities, automatic building and testing, and automatic instrumentation to gather dynamic-analysis data. In the future, we envision the system and toolkit to become a framework on which further visualizations and analyses are developed. SPIDER SENSE is open-source and publicly available for download and collaborative development.

Dynamic slicing is an analysis that operates on program execution models (e.g., dynamic dependence graphs) to support the interpreation of program-execution traces. Given an execution event of interest (i.e., the slicing criterion), it solves for all instruction-execution events that either affect or are affected by that slicing criterion, and thereby reduces the search space to find influences within execution traces. Unfortunately, the resulting dynamic slices are still often prohibitively large for many uses. Despite this reduction search space, the dynamic slices are often still prohibitively large for many uses, and moreover, are provided without guidance of which and to what degree those influences are exerted. In this work, we present a novel approach to quantify the relevance of each instruction-execution event within a dynamic slice by its degree of relative influence on the slicing criterion. As such, we augment the dynamic slice with dynamic-relevance measures for each event in the slice, which can be used to guide and prioritize inspection of the events in the slice. We conducted an experiment that evaluates the ability of existing dynamic slicing and our approach, using dynamic relevance, to correctly identify sources of execution influence and state propagation. The results of the experiment show that inspections that were guided by traditional dynamic slicing to find the root cause for a failure reduced the search space by, on average, 61.3%. Further, inspections guided with the assistance of the new dynamic relevance reduced the search space by 96.2%.

Modern applications make heavy use of third-party libraries and components, which poses new challenges for efficient dynamic analysis. To perform such analyses, transitive dependent components at all layers of the call stack must be monitored and analyzed, and as such may be prohibitively expensive for systems with large libraries and components. As an approach to address such expenses, we record, summarize, and reuse dynamic dataflows between inputs and outputs of components, based on dynamic control and data traces. These summarized dataflows are computed at a fine-grained instruction level; the result of which, we call “dynamic dependence summaries.” Although static summaries have been proposed, to the best of our knowledge, this work presents the first technique for dynamic dependence summaries. The benefits to efficiency of such summarization may be afforded with losses of accuracy. As such, we evaluate the degree of accuracy loss and the degree of efficiency gain when using dynamic dependence summaries of library methods. On five large programs from the DaCapo benchmark (for which no existing whole-program dynamic dependence analyses have been shown to scale) and 21 versions of NANOXML, the summarized dependence analysis provided 90% accuracy and a speed-up of 100% (i.e., ×2), on average, when compared to traditional exhaustive dynamic dependence analysis.

In this New Ideas and Emerging Results paper, we present a novel visualization, THE BRAIN, that reveals clusters of source code that co-execute to produce behavioral features of the program throughout and within executions. We created a clustered visualization of source-code that is informed by dynamic control flow of multiple executions; each cluster represents commonly interacting logic that composes software features. In addition, we render individual executions atop the clustered multiple-execution visualization as user-controlled animations to reveal characteristics of specific executions-these animations may provide exemplars for the clustered features and provide chronology for those behavioral features, or they may reveal anomalous behaviors that do not fit with the overall operational profile of most executions. Both the clustered multiple-execution view and the animated individual-execution view provide insights for the constituent behaviors within executions that compose behaviors of whole executions. Inspired by neural imaging of human brains of people who were subjected to various external stimuli, we designed and implemented THE BRAIN to reveal program activity during execution. The result has revealed the principal behaviors of execution, and those behaviors were revealed to be (in some cases) cohesive, modular source-code structures and (in other cases) cross-cutting, emergent behaviors that involve multiple modules. In this paper, we describe THE BRAIN and envisage the uses to which it can be put, and we provide two example usage scenarios to demonstrate its utility.

In this paper, we present CHRONOS-a tool that enables the querying, exploration, and discovery of historical change events to source code. Unlike traditional Revision-Control-System tools, CHRONOS allows queries across any subset of the code, down to the line-level, which can potentially be contiguous or disparate, even among multiple files. In addition, CHRONOS provides change history across all historical versions (i.e., it is not limited to a pairwise “diff”). The tool implements a zoom-able user interface as a visualization of the history of the queried code to provide both a high-level view of the changes, which supports pattern recognition and discovery, and a low-level view that supports semantic comprehension for tasks such as reverse engineering and identifying design rationale. In this paper, we describe use cases in which CHRONOS may be helpful, provide a motivating example to demonstrate the benefits brought by CHRONOS, and describe its visualization in detail.

This paper describes a new technique, which automatically selects the most appropriate developers for fixing the fault represented by a failing test case, and provides a diagnosis of where to look for the fault. This technique works by incorporating three key components: (1) fault localization to inform locations whose execution correlate with failure, (2) history mining to inform which developers edited each line of code and when, and (3) expertise assignment to map locations to developers. To our knowledge, the technique is the first to assign developers to execution failures, without the need for textual bug reports. We implement this technique in our tool, WHOSEFAULT, and describe an experiment where we utilize a large, open-source project to determine the frequency in which our tool suggests an assignment to the actual developer who fixed the fault. Our results show that 81% of the time, WHOSEFAULT produced the same developer that actually fixed the fault within the top three suggestions. We also show that our technique improved by a difference between 4% and 40% the results of a baseline technique. Finally, we explore the influence of each of the three components of our technique over its results, and compare our expertise algorithm against an existing expertise assessment technique and find that our algorithm provides greater accuracy, by up to 37%.

In this paper, we present a weighted, hybrid program-dependence model that represents the relevance of highly related, dependent code to assist developer comprehension of the program for multiple software-engineering tasks. Programmers often need to understand the dependencies among program elements, which may exist across multiple modules. Although such dependencies can be gathered from traditional models, such as slices, the scalability of these approaches is often prohibitive for direct, practical use. To address this scalability issue, as well as to assist developer comprehension, we introduce a program model that includes static dependencies as well as information about any number of executions, which inform the weight and relevance of the dependencies. Additionally, classes of executions can be differentiated in such a way as to support multiple software-engineering tasks. We evaluate this weighted, hybrid model for a task that involves exploring the structural context while debugging. The results demonstrate that the new model more effectively reveals relevant failure-correlated code than the static-only model, thus enabling a more scalable exploration or post hoc analysis.

To cluster executions that exhibit faulty behavior by the faults that cause them, researchers have proposed using internal execution events, such as statement profiles, to (1) measure execution similarities, (2) categorize executions based on those similarity results, and (3) suggest the resulting categories as sets of executions exhibiting uniform fault behavior. However, due to a paucity of evidence correlating profiles and output behavior, researchers employ multiple simplifying assumptions in order to justify such approaches. In this paper we present an empirical study of profile correlation with output behavior, and we reexamine the suitability of such simplifying assumptions. We examine over 4 billion test-case outputs and execution profiles from multiple programs with over 9000 versions. Our data provides evidence that with current techniques many executions should be omitted from the clustering analysis to provide clusters that each represent a single fault. In addition, our data reveals the previously undocumented effects of multiple faults on failures, which has implications for techniques' ability (and inability) to properly cluster. Our results suggest directions for the improvement of future failure-clustering techniques that better account for software-fault behavior.

Before a fault can be fixed, it first must be understood. However, understanding why a system fails is often a difficult and time consuming process. While current automated-debugging techniques provide assistance in knowing where a fault is, developers are left unaided in understanding what a fault is, and why the system is failing. We present Semantic Fault Diagnosis (SFD), a technique that leverages lexicographic and dynamic information to automatically capture natural-language fault descriptors. SFD utilizes class names, method names, variable expressions, developer comments, and keywords from the source code to describe a fault. SFD can be used immediately after observing a failing execution and requires no input from developers or bug reports. In addition we present motivating examples and results from a SFD prototype to serve as a proof of concept.

When attempting to determine the number and set of execution failures that are caused by particular faults, developers must perform an arduous task of investigating and diagnosing each individual failure. Researchers proposed failure-clustering techniques to automatically categorize failures, with the intention of isolating each culpable fault. The current techniques utilize dynamic control flow to characterize each failure to then cluster them. These existing techniques, however, are blind to the intent or purpose of each execution, other than what can be inferred by the control-flow profile. We hypothesize that semantically rich execution information can aid clustering effectiveness by categorizing failures according to which functionality they exhibit in the software. This paper presents a novel clustering method that utilizes latent-semantic-analysis techniques to categorize each failure by the semantic concepts that are expressed in the executed source code. We present an experiment comparing this new technique to traditional control-flow-based clustering. The results of the experiment showed that the semantic-concept clustering was more precise in the number of clusters produced than the traditional approach, without sacrificing cluster accuracy.

Many software-engineering tasks require developers to understand the history and evolution of source code. However, today's software-development techniques and tools are not well suited for the easy and efficient procurement of such information. In this paper, we present an approach called history slicing that can automatically identify a minimal number of code modifications, across any number of revisions, for any arbitrary segment of source code at fine granularity. We also present our implementation of history slicing, Chronos, that includes a novel visualization of the entire evolution for the code of interest. We provide two experiments: one experiment automatically computes 16,000 history slices to determine the benefit brought by various levels of automation, and another experiment that assesses the practical implications of history slicing for actual developers using the technique for actual software-maintenance tasks that involve code evolution. The experiments show that history slicing offered drastic improvements over the conventional techniques in three ways: (1) the amount of information needed to be examined and traced by developers was reduced by up to three orders of magnitude; (2) the correctness of developers attempting to solve software-maintenance tasks was more than doubled; and (3) the time to completion of these software-maintenance tasks was almost halved.

Multiple faults in a program can interact to form new behaviors in a program that would not be realized if the program were to contain the individual faults. This paper presents an in-depth study of the effects of the interaction of faults within a program. Many researchers attempt to ameliorate the effects of faulty programs. Unfortunately, such researchers are left to rely upon intuition about fault behavior due to the paucity of formalized studies of faults and their behavior. In an attempt to advance the understanding of faults and their behavior, we conducted a study of fault interaction across six subjects with more than 65,000 multiple-fault versions. The results of our study show four significant types of interaction, with one type - faults obscuring the effects of other faults - as the most prevalent type. The prevalence of obscuring faults' effects has an adverse effect on many automated software-engineering techniques, such as regression-testing, fault-localization, and fault-clustering techniques. Given that software commonly contains more than a single fault, these results have implications for developers and researchers alike by informing them of expected complications, which in many instances are opposite to intuition.

This paper presents an empirical study on the effects of the quantity of faults on statistical, coverage-based fault localization techniques. The former belief was that the effectiveness of fault-localization techniques was inversely proportional to the quantity of faults. In an attempt to verify these beliefs, we conducted a study on three programs varying in size on more than 13,000 multiple-fault versions. We found that the influence of multiple faults (1) was not as great as expected, (2) created a negligible effect on the effectiveness of the fault localization, and (3) was often even complimentary to the fault-localization effectiveness. In general, even in the presence of many faults, at least one fault was found by the fault-localization technique with high effectiveness. We also found that some faults were localizable regardless of the presence of other faults, whereas other faults' ability to be found by these techniques varied greatly in the presence of other faults. Because almost all real-world software contains multiple faults, these results impact the use of statistical fault-localization techniques and provide a greater understanding of their potential in practice.

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.

This paper provides techniques for aiding developers' task of familiarizing themselves with the context of a fault. Many fault-localization techniques present the software developer with a subset of the program to inspect in order to aid in the search for faults that cause failures. However, typically, these techniques do not describe how the components of the subset relate to each other in a way that enables the developer to understand how these components interact to cause failures. These techniques also do not describe how the subset relates to the rest of the program in a way that enables the developer to understand the context of the subset. In this paper, we present techniques for providing static and dynamic relations among program elements that can be used as the basis for the exploration of a program when attempting to understand the nature of faults.

To perform a number of tasks such as inferring design rationale from past code changes or assessing developer expertise for a software feature or bug, the evolution of a set of lines of code can be assessed by mining software histories. However, determining the evolution of a set of lines of code is a manual and time consuming process. This paper presents a model of this process and an approach for automating it. We call this process History Slicing. We describe the process and options for generating a graph that links every line of code with its corresponding previous revision through the history of the software project. We then explain the method and options for utilizing this graph to determine the exact revisions that contain changes for the lines of interest and their exact position in each revision. Finally, we present some preliminary results which show initial evidence that our automated technique can be several orders of magnitude faster than the manual approach and require that developers examine up to two orders of magnitude less code in extracting such histories.

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.

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.

Most existing fault-localization techniques focus on identifying and reporting single statements that may contain a fault. Even in cases where a fault involves a single statement, it is generally hard to understand the fault by looking at that statement in isolation. Faults typically manifest themselves in a specific context, and knowing that context is necessary to diagnose and correct the fault. In this paper, we present a novel fault-localization technique that identifies sequences of statements that lead to a failure. The technique works by analyzing partial execution traces corresponding to failing executions and identifying common segments in these traces, incrementally. Our approach provides developers a context that is likely to result in a more directed approach to fault understanding and a lower overall cost for debugging.

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.

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.

Attempts to reduce the number of delivered faults in software are estimated to consume 50% to 80% of the development and maintenance effort according to J.S. Collofello ans S.N. Woodfield (1989). Among the tasks required to reduce the number of delivered faults, debugging is one of the most time-consuming according to T. Ball and S.G. Eick and Telcordia Technologies, and locating the errors is the most difficult component of this debugging task according to I. Vessey (1985). Clearly, techniques that can reduce the time required to locate faults can have a significant impact on the cost and quality of software development and maintenance.

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.

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.

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.

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