New Directions in Static Analysis for Error-Detection and Garbage Collection

Pointer analysis is critical for effectively analyzing programs written in languages like C, C++, and Java, which make heavy use of pointers and pointer-based data structures. Unfortunately, pointer analysis continues to be one of the most persistent and difficult problems in static analysis. One reason for this is that previous work has viewed pointer analysis as a single, monolithic problem that can be solved in isolation. However, pointer analysis is not a stand-alone task: its purpose is to provide pointer information to other client analysis algorithms. Since the needs of these clients vary widely, research has so far been unable to produce an efficient pointer analysis algorithm that satisfies them all.

Our view is that pointer analysis is not a single problem that can be separated from its client analysis problems. Instead, pointer analysis comprises a family of algorithms, which are selected and customized to meet the specific requirements of each client. In this talk I will present two such customized algorithms. The first is a pointer analysis that we developed for compiler-assisted garbage collection in Java. This analysis supports dynamic object colocation by finding objects that will be connected and instrumenting the program to ensure that they are allocated together in the same garbage collection space. This algorithm is unique because it is unsound: it can miss potential pointer relationships. However, the client (in this case the garbage collector) does not require soundness because allocation decisions do not affect correctness.

The second algorithm is a more general approach to customization, called client-driven pointer analysis, which automatically adapts its precision to match the needs of client analyses. Many whole-program analysis problems need precise pointer information, but often they need it only in specific parts of the target program. Our algorithm uses a fast initial analysis pass to determine where more precision is needed, then reruns the analysis with fine-grained precision policy that is customized for the particular client and program. We demonstrate this algorithm on a suite of real, open-source C programs, using a set of error detection problems as clients. Our algorithm achieves high error detection accuracy at a fraction of the cost of comparably accurate fixed-precision algorithms.