Selected Papers by Hira Agrawal

Maintainers can use information from test analysis tools to help them understand, debug, and retest programs. The authors describe techniques and tools in the xS u d s package, a system for understanding and diagnosing s o f t w a re bugs - including Y2K problems in legacy applications.

The purpose of regression testing is to ensure that changes made to software, such as adding new features or modifying existing features, have not adversely affected features of the software that should not change. Regres-sion testing is usually performed by running some, or all, of the test cases created to test modifications in previous versions of the software. Many techniques have been re-ported on how to select regression tests so that the num-ber of test cases does not grow too large as the software evolves. Our proposed hybrid technique combines modifi-cation, minimization and prioritization-based selection us-ing a list of source code changes and the execution traces from test cases run on previous versions. This technique seeks to identify a representative subset of all test cases that may result in different output behavior on the new software version. We report our experience with a tool called ATAC which implements this technique.

Finding a fault in a program is a complex process which involves understanding the program's purpose, structure, semantics, and the relevant characteristics of failure producing tests. We describe atool which supports execution slicing and dicing based on test cases. We report the results of an experiment that uses heuristic techniques in fault localization.

In this paper we present techniques to find subsets of nodes of a owgraph that satisfy the following property: A test set that exercises all nodes in a subset exercises all nodes in the owgraph. Analogous techniques to find subsets of edges are also proposed. These techniques may be used to significantly reduce the cost of coverage testing of programs. A notion of a super block consisting of one or more basic blocks is developed. If any basic block in a super block is exercised by an input then all basic blocks in that super block must be exercised by the same input. Dominator relationships among super blocks are used to identify a subset of the super blocks whose coverage implies that of all super blocks and, in turn, that of all basic blocks. Experiments with eight systems in the range of 1-75K lines of code show that, on the average, test cases targeted to cover just 29% of the basic blocks and 32% of the branches ensure 100% block and branch coverage, respectively.

Program slices have potential uses in many software en- gineering applications. Traditional slicing algorithms, however, do not work correctly on programs that con- tain explicit jump statements. Two similar algorithms were proposed recently to alleviate this problem. Both require the owgraph and the program dependence graph of the program to be modified. In this paper, we propose an alternative algorithm that leaves these graphs intact and uses a separate graph to store the additional required information. We also show that this algorithm permits an extremely efficient, conser- vative adaptation for use with programs that contain only "structured" jump statements.

The purpose of regression testing is to ensure that bug fixes and new functionality introduced in a new version of a software do not adversely affect the cor- rect functionality inherited from the previous version. This paper explores efficient methods of selecting small subsets of regression test sets that may be used to es- tablish the same.

Programmers spend considerable time debugging code. Symbolic debuggers provide some help but the task remains complex and difficult. Other than breakpoints and trac- ing, these tools provide little high-level help. Programmers must perform many tasks manually that the tools could perform automatically, such as finding which statements in the program affect the value of an output variable for a given testcase, and what was the value of a given variable when the control last reached a given program location. If debugging tools provided explicit support for these tasks, the debugging process could be automated to a significant extent. In this paper we present a debugging paradigm, based on dynamic program slicing and execution backtracking techniques, that easily lends itself to automation. This paradigm is based on experience with using these techniques to debug software. We also present a prototype debugging tool, Spyder , that explicitly supports the proposed paradigm, and with which we are performing further debugging research.

An execution backtracking facility ininteractive source debuggers allows users to mirror their thought processes while debugging -- working backwards from the location where an error is manifested and determining the conditions under which the error occurred. Such a facility also allows a user to change program characteristics and reexecute from arbitrary points within the program under examination -- a "what-if" capability. This paper describes an experimental debugger that provides such a backtracking function. We describe why the facility is useful, and why other current techniques are inadequate. We show how execution backtracking can be efficiently implemented by saving only the latest values of variables modified by a statement, and allowing backtracking only over complete program statements. We also describe how this approach relates to our work on dynamic program slicing.

Program slices are useful in debugging. Most work on program slicing to date has concentrated on finding slices of programs involving only scalar variables. Pointers and composite variables do not lend them- selves well to static analysis, especially when the lan- guage involved is not strongly-typed. When debug- ging a program, however, we are interested in analyz- ing the program behavior for testcases that reveal a fault. In this paper, we present a uniform approach to handling pointers and composite variables such as arrays, records, and unions for the purpose of obtain- ing dynamic program slices. The dynamic approach proposed works well even when the language involved allows unconstrained pointers and performs no run- time checks, as in C.

The conventional notion of a program slice -- the set of all statements that might affect the value of a variable occurrence -- is totally independent of the program input values. Program debugging, however, involves analyzing the program behavior under the specific inputs that revealed the bug. In this paper we address the dynamic counterpart of the static slicing problem -- finding all statements that really affected the value of a variable occurrence for the given program inputs. Several approaches for computing dy- namic slices are examined. The notion of a Dynamic Dependence Graph and its use in computing dynamic slices is discussed. We introduce the concept of a Reduced Dynamic Dependence Graph whose size does not depend on the length of execution history, which is unbounded in general, but whose size is bounded and is proportional to the number of dynamic slices arising during the program execution.