Points-to analysis (PTA) has been a field of research for a long while. The earliest uses of PTA are probably as old as the first program using indirect addressing. The analysis basically consists of determining the set of addresses that can be reached by a statement in a given program. For high-level language (HLL) programs, in practice this means addresses that can be reached by pointers or references stored in program variables. Since pointers can point to other pointers, in theory, at runtime a single variable can point to a long chain of pointers. In practice, however, such chains are only a few links deep.

One of the seminal papers in this area is Lars O. Andersen’s PhD thesis from the University of Copenhagen (1994). The principal subject of the thesis was not PTA, but the generation of specialized programs from very general programs, to improve efficiency under given sets of inputs. Hence, it was natural for Andersen to be concerned with the objects that can be reached at any point in the program being analyzed, in order to optimize the code produced. His approach used static analyses of source statements in C programs to determine which objects can be reached by variables containing pointers in the program. This type of analysis is referred to as “Andersen analysis” for programs in different languages.

There are several dimensions of PTA. One of these is flow sensitivity, referring to control flow in the program. Obviously, a statement that can never be reached can never access any variables. Further, what values might be stored in a variable depends on the flow of execution up to the instance of the assignment. Thus, a complete analysis of all feasible paths to statements that modify a variable must be made. I use the term “variable” to mean all types of variables: local and global (static) variables, instance/class attributes, and formal/actual parameters and return values.

Another dimension of PTA is context sensitivity. This is somewhat analogous to context-free/context-sensitive formal grammars for languages. Which variables are reachable from a given variable at a given point depends on the values of other variables at that instant. Other dimensions of PTA include cost and precision. “Cost” refers primarily to the central processing unit (CPU) time and memory usage of a given PTA. “Precision” refers roughly to the fraction of all correct potential links that were found, as well as the omission of infeasible links. This precision itself has dimensions, as addressed in this paper.

Developing a PTA tool for object-oriented languages requires dealing with the inheritance, encapsulation, and polymorphism inherent in such languages. Thus, the tool must deal with these issues itself, or else use another tool for this purpose.

This paper is a recent contribution from a group of researchers at Rutgers University, who have been working in this area under the leadership of B. Ryder for several years. They have many previous publications on this and related subjects to their credit. The paper includes a comprehensive list of references.

The paper addresses PTA for Java programs. As a central theme, the authors propose object sensitivity as a new form of context sensitivity for flow-insensitive PTA of Java programs. This approach uses “the receiver object at a method invocation site to distinguish different calling contexts,” and “conceptually every method is replicated for each object analysis name that represents a possible receiver object.”

In order to avoid the potentially high cost of object-sensitive analysis, the authors define a parameterization framework that may help “analysis designers to control the degree of object sensitivity and consequently the cost/precision tradeoff of the analysis.” The former deals with controlling the length of the pointer chain that should be analyzed. The latter refers to the effects of this choice on the cost and precision of the analysis.

Who are the potential clients of such an analysis? The paper goes on to define new types of side effect and definition-use analysis based on parameterized object-sensitive PTA. It then compares implementations of an Andersen-style (context-insensitive and flow-insensitive) version and a “call-site context sensitive” version of the tool with the object-sensitive version. The authors conclude that object-sensitive analysis is practical, and improves the precision of mod analysis (a form of context-sensitive side-effect analysis), call graph construction, and virtual call resolution. The paper concludes by presenting experimental results, and discussing related work and future work.

This paper should be of interest to researchers in, and students of, dynamic program behavior analysis. However, the potential reader should be prepared to plow through a complex set of set-theoretic notations used to define the machinery used in the analysis. In fact, a simpler, higher-level notation could be created to simplify the formalization. On the other hand, the authors’ language and descriptive prose are quite readable and easy to follow. They might consider packaging this tool, and making it available for use by graduate students and researchers in software engineering. Finally, the depth and breadth of the paper make it a good candidate to serve as the nucleus of a book in this area.