Vijay Nagarajan 1, * , Dennis Jeffrey 2, Rajiv Gupta 3, Neelam Gupta The last name Neelam Gupta should not have been listed as an author for this paper. She collaborated with Rajiv Gupta when she was a faculty member at the University of Arizona in 2007, and up until August 2009 when Dennis Jeffrey, who was working on his PhD thesis under her supervision at the University of Arizona, graduated from the University of Riverside after he transferred there from the University of Arizona. However, after August 2009, Neelam Gupta stopped collaborating with Rajiv Gupta, and she did not participate in any of the revisions of the above journal paper submitted to Software - Practice and Experience. The above paper, with its correct list of authors, should be cited as follows: Vijay Nagarajan 1, * , Dennis Jeffrey 2, Rajiv Gupta 3

SUMMARY Dynamic slicing is a promising trace based technique that helps programmers in the process of debugging. In order to debug a failed run, dynamic slicing requires the dynamic dependence graph (DDG) information for that particular run. The two major challenges involved in utilizing dynamic slicing as a debugging technique are the efficient computation of the DDG and the efficient computation of the dynamic slice, given the DDG. In this paper, we present an efficient debugger, which first computes the DDG efficiently while the program is executing; dynamic slicing is later performed efficiently on the computed DDG, on demand. To minimize program slowdown during the online computation of DDG, we make the design decision of not outputting the computed dependencies to a file, instead, storing them in memory in a specially allocated fixed size circular buffer. The size of the buffer limits the length of the execution history that can be stored. To maximize the execution history that can be maintained, we introduce optimizations to eliminate the storage of most of the generated dependencies, at the same time ensuring that those that are stored are sufficient to capture the bug. Experiments conducted on CPU‐intensive programs show that our optimizations are able to reduce the trace rate from 16 to 0.8 bytes per executed instruction. This enables us to store the dependence trace history for a window of 20 million executed instructions in a 16‐MB buffer. Our debugger is also very efficient, yielding slicing times of around a second, and only slowing down the execution of the program by a factor of 19 during the online tracing step. Using recently proposed architectural support for monitoring, we are also able to handle multithreaded programs running on multicore processors. Copyright © 2011 John Wiley & Sons, Ltd.

The above article (DOI: 10.1002/spe.1105) was published in print in Volume 42, Issue 8 (August 2012), for which errors in the arrangement of the affiliation links have subsequently been identified. This article has been corrected in the online version of the issue. The affiliation links have been corrected as follows:Vijay Nagarajan1, Dennis Jeffrey2, Rajiv Gupta3 and Neelam Gupta1School of Informatics, University of Edinburgh, Edinburgh, EH8 9AB, UK2Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043, USA3CSE Department, University of California at Riverside, Riverside, CA 92521, USA

Abstract Memory‐related program failures in multithreaded programs can be caused by a variety of bugs. Concurrency bugs can occur due to unexpected or incorrect thread interleavings during execution. Other kinds of memory bugs, such as buffer overflows and uninitialized reads, may also occur in multithreaded as well as single‐threaded programs. Most prior techniques for isolating these bugs are specialized, addressing only one type of concurrency bug or certain types of other memory bugs. The memory corruption caused by these bugs can also undergo significant propagation during program execution. When a program failure finally occurs due to memory corruption, the true root cause of the failure may be effectively concealed as significant portions of memory may have become corrupted. We propose a general framework that can isolate the root cause of any failure in a multithreaded program that involves memory corruption and reveals at least a subset of this memory corruption. This includes three important types of concurrency bugs—data races, atomicity violations, and order violations—as well as other kinds of memory bugs. To account for propagation of memory corruption, our approach uses a dynamic technique called ‘execution suppression’ that iteratively reveals memory corruption in a failing execution to isolate the true root cause of the failure. Copyright © 2011 John Wiley & Sons, Ltd.

By studying the behavior of several programs that crash due to memory errors, we observed that locating the errors can be challenging because significant propagation of corrupt memory values can occur prior to the point of the crash. In this article, we present an automated approach for locating memory errors in the presence of memory corruption propagation. Our approach leverages the information revealed by a program crash: when a crash occurs, this reveals a subset of the memory corruption that exists in the execution. By suppressing (nullifying) the effect of this known corruption during execution, the crash is avoided and any remaining (hidden) corruption may then be exposed by subsequent crashes. The newly exposed corruption can then be suppressed in turn. By iterating this process until no further crashes occur, the first point of memory corruption—and the likely root cause of the program failure—can be identified. However, this iterative approach may terminate prematurely, since programs may not crash even when memory corruption is present during execution. To address this, we show how crashes can be exposed in an execution by manipulating the relative ordering of particular variables within memory. By revealing crashes through this variable re-ordering, the effectiveness and applicability of the execution suppression approach can be improved. We describe a set of experiments illustrating the effectiveness of our approach in consistently and precisely identifying the first points of memory corruption in executions that fail due to memory errors. We also discuss a baseline software implementation of execution suppression that incurs an average overhead of 7.2x, and describe how to reduce this overhead to 1.8x through hardware support.

We previously presented a fault localization technique called value replacement that repeatedly alters the state of an executing program to locate a faulty statement [9]. The technique searches for program statements involving values that can be altered during runtime to cause the incorrect output of a failing run to become correct. We showed that highly effective fault localization results could be achieved by the technique on programs containing single faults. In the current work, we generalize value replacement so that it can also perform effectively in the presence of multiple faults. We improve scalability by describing two techniques that significantly improve the efficiency of value replacement. In our experimental study, our generalized technique effectively isolates multiple simultaneous faults in time on the order of minutes in each case, whereas in , the technique had sometimes required time on the order of hours to isolate only single faults.

It is important that long running server programs retain availability amidst software failures. However, server programs do fail and one of the important causes of failures in server programs is due to memory errors. Software bugs in the server code like buffer overflows, integer overflows, etc. are exposed by certain user requests, leading to memory corruption, which can often result in crashes. One safe way of recovering from these crashes is to periodically checkpoint program state and rollback to the most recent checkpoint on a crash. However, checkpointing program state periodically can be quite expensive. Furthermore, since recovery can involve the rolling back of considerable state information in addition to replay of several benign user requests, the throughput and response time of the server can be reduced significantly during rollback recovery.

We present a tool called BugFix that can assist developers in fixing program bugs. Our tool automatically analyzes the debugging situation at a statement and reports a prioritized list of relevant bug-fix suggestions that are likely to guide the developer to an appropriate fix at that statement. BugFix incorporates ideas from machine learning to automatically learn from new debugging situations and bug fixes over time. This enables more effective prediction of the most relevant bug-fix suggestions for newly-encountered debugging situations. The tool takes into account the static structure of a statement, the dynamic values used at that statement by both passing and failing runs, and the interesting value mapping pairs [17] associated with that statement. We present a case study illustrating the efficacy of BugFix in helping developers to fix bugs.

We present a general approach for automatically isolating the root causes of memory-related bugs in software. Our approach is based on the observation that most memory bugs involve uses of corrupted memory locations. By iteratively suppressing (nullifying) the effects of these corrupted memory locations during program execution, our approach gradually isolates the root cause of a memory bug. Our approach can work for common memory bugs such as buffer overflows, uninitialized reads, and double frees. However, our approach is particularly effective in finding root causes for memory bugs in which memory corruption propagates during execution until an observable failure such as a program crash occurs.

We are designing scalable dynamic information flow tracking techniques and employing them to carry out tasks related to debugging (bug location and fault avoidance), security (software attack detection), and data validation (lineage tracing of scientific data). The focus of our ongoing work is on developing online dynamic analysis techniques for long running multithreaded programs that may be executed on a single core or on multiple cores to exploit thread level parallelism.

We present a value profile based approach for ranking program statements according to their likelihood of being faulty. The key idea is to see which program statements exercised during a failing run use values that can be altered so that the execution instead produces correct output. Our approach is effective in locating statements that are either faulty or directly linked to a faulty statement. We present experimental results showing the effectiveness and efficiency of our approach. Our approach outperforms Tarantula which, to our knowledge, is the most effective prior approach for statement ranking based fault localization using the benchmark programs we studied.

Dynamic slicing is a promising trace based technique that helps programmers in the process of debugging. In order to debug a failed run, dynamic slicing requires the dynamic dependence graph (DDG) information for that particular run. In prior work, address and control-flow traces are collected online and then extensively post-processed offline to yield the DDG, upon which slicing is performed. Unfortunately, the offline post-processing step can be extremely time consuming [21], impeding the use of dynamic slicing as a debugging technique. In this paper, we present ONTRAC, an efficient online tracing system, that directly computes the dynamic dependences online, thus eliminating the expensive offline postprocessing step. To minimize the program slowdown, we make the design decision of not outputting the computed dependences to a file, instead storing them in memory in a specially allocated fixed size circular buffer. The size of the buffer limits the length of the execution history that can be stored. To maximize the execution history that can be maintained, we introduce optimizations to eliminate the storage of most of the generated dependences, at the same time ensuring that those that are stored are sufficient to capture the bug. Our experiments conducted with real bugs confirm the above fact. Other experiments conducted on cpu-intensive programs show that our optimizations are able to reduce the trace-rate from 16 bytes to 0.8 bytes per executed instruction. This enables us to store the dependence trace history for a window of 20 million executed instructions in a 16 MB buffer. ONTRAC is also very efficient, only slowing down the execution by a factor of 19, eliminating the slowdown by a factor of 540 due to post-processing.

Software testing is a critical part of software development. As new test cases are generated over time due to software modifications, test suite sizes may grow significantly. Because of time and resource constraints for testing, test suite minimization techniques are needed to remove those test cases from a suite that, due to code modifications over time, have become redundant with respect to the coverage of testing requirements for which they were generated. Prior work has shown that test suite minimization with respect to a given testing criterion can significantly diminish the fault detection effectiveness (FDE) of suites. We present a new approach for test suite reduction that attempts to use additional coverage information of test cases to selectively keep some additional test cases in the reduced suites that are redundant with respect to the testing criteria used for suite minimization, with the goal of improving the FDE retention of the reduced suites. We implemented our approach by modifying an existing heuristic for test suite minimization. Our experiments show that our approach can significantly improve the FDE of reduced test suites without severely affecting the extent of suite size reduction

Software testing and retesting occurs continuously during the software development lifecycle to detect errors as early as possible. The sizes of test suites grow as software evolves. Due to resource constraints, it is important to prioritize the execution of test cases so as to increase chances of early detection of faults. Prior techniques for test case prioritization are based on the total number of coverage requirements exercised by the test cases. In this paper, we present a new approach to prioritize test cases based on the coverage requirements present in the relevant slices of the outputs of test cases. We present experimental results comparing the effectiveness of our prioritization approach with that of existing techniques that only account for total requirement coverage, in terms of ability to achieve high rate of fault detection. Our results present interesting insights into the effectiveness of using relevant slices for test case prioritization

Software testing is a critical part of software development. Test suite sizes may grow significantly with subsequent modifications to the software over time. Due to time and resource constraints for testing, test suite minimization techniques attempt to remove those test cases from the test suite that have become redundant over time since the requirements covered by them are also covered by other test cases in the test suite. Prior work has shown that test suite minimization techniques can severely compromise the fault detection effectiveness of test suites. In this paper, we present a novel approach to test suite reduction that attempts to selectively keep redundant tests in the reduced suites. We implemented our technique by modifying an existing heuristic for test suite minimization. Our experiments show that our approach can significantly improve the fault detection effectiveness of reduced suites without severely affecting the extent of test suite size reduction.