Unification-based pointer analysis with directional assignments

By Manuvir Das. ACM-SIGPLAN Symposium on Programming Language Design and Implementation, 2000

333 citations recorded by the source corpus.

This paper describes a new algorithm for flow and context insensitive pointer analysis of C programs. Our studies show that the most common use of pointers in C programs is in passing the addresses of composite objects or updateable values as arguments to procedures. Therefore, we have designed a low-cost algorithm that handles this common case accurately. In terms of both precision and running time, this algorithm lies between Steensgaard's algorithm, which treats assignments bi-directionally using unification, and Andersen's algorithm, which treats assignments directionally using subtyping. Our “one level flow” algorithm uses a restricted form of subtyping to avoid unification of symbols at the top levels of pointer chains in the points-to graph, while using unification elsewhere in the graph. The method scales easily to large programs. For instance, we are able to analyze a 1.4 MLOC (million lines of code) program in two minutes, using less than 200MB of memory. At the same time, the precision of our algorithm is very close to that of Andersen's algorithm. On all of the integer benchmark programs from SPEC95, the one level flow algorithm and Andersen's algorithm produce either identical or essentially identical points-to information. Therefore, we claim that our algorithm provides a method for obtaining precise flow-insensitive points-to information for large C programs.

Subfields: Artificial Intelligence, Hardware and Architecture, Software

View Paper: https://www.semanticscholar.org/paper/5ded3c4023043afba6ec92373ec48d13a34cdc06

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Hardware and Architecture

In Software

Citations in the corpus

Thorough static analysis of device drivers (2006, methodology): “SDV also performs a pointer analysis [25] on the program, which builds a graph representing a static overapproximation of the possible pointer alaising relationships between expressions occuring in the program.”
Automatically validating temporal safety properties of interfaces (2001, methodology): “Note that this is the same basic assumption underlying most points-to analysis, including the one that our tools use [10].”
ESP: path-sensitive program verification in polynomial time (2002, methodology): “The graph is potentially quadratic in the number of call edges, but is linear in practice because of a simple caching technique explained in [7].”
KISS: keep it simple and sequential (2004, methodology): “We use a static alias analysis [12] to optimize away most of the calls to check r and checkw.”
Automatic predicate abstraction of C programs (2001, methodology): “We handle the two cases in a uniform manner and describe how to use points-to analysis [12] to improve the precision of our abstraction.”
Scaling Java Points-to Analysis Using SPARK (2003, methodology): “One instance of a similarly hybrid analysis is described in [8].”
SLAM and Static Driver Verifier: Technology Transfer of Formal Methods inside Microsoft (2004, methodology): “The parts of SLAM that analyze C code were built on top of existing infrastructure developed in MSR that exports an abstract syntax tree interface from the Microsoft C/C++ compiler and that performs alias analysis of C code [Das00].”
The New C Standard (Excerpted material) An Economic and Cultural Commentary (2008, positive): “Making use of such information enabled an analysis of Microsoft Word 97,[ 3 ] 1.4 MLOC of C++, to produce results close to those obtained by Andersen’s algorithm.[2]”
Effective typestate verification in the presence of aliasing (2006, methodology): “As in ESP [Das et al. 2002], we could introduce path-sensitive predicates that encode the direction of dynamic dispatch.”
Locating Features in Source Code (2003, background): “There is a large body of work on pointer analysis for procedural languages [10], [11], [12], [13], [14], [15], [16], [16] and object-oriented languages [18], [19] that resolves general pointers, function pointers, and dynamic binding.”
CCured: type-safe retrofitting of legacy software (2005, background): “instead trusting the program’s calls to free(), the overhead drops to less than 50%. See Hirzel [2000], p.”
Cloning-based context-sensitive pointer alias analysis using binary decision diagrams (2004, background): “extended the unification-based approach to include “one-level-flow”[10] and one level of context sensitivity[11].”
WYSINWYX: What you see is not what you eXecute (2010, background): “Recency-abstraction is somewhere in the middle between the extremes of one summary node per malloc site [8, 42, 105] and complex shape abstractions [100].”
Refinement-based context-sensitive points-to analysis for Java (2006, neutral): “In the ﬁnal version, we will discuss the algorithmic differences between the other algorithms (e.g. BDDs [51] vs. summaries [52]), their targeted clients, and context-insensitive analyses and their inﬂuences, for example [4, 6, 9, 14, 19, 20, 39, 46].”