| Title | : | Flow and Context-Sensitive Points-to Analysis using Generalized Points-to Graphs |
| Speaker | : | Pritam Gharat (IIT Bombay) |
| Details | : | Tue, 30 Aug, 2016 10:00 AM @ BSB 361 |
| Abstract: | : | Computing precise (fully flow-sensitive and context-sensitive) and exhaustive (as against demand driven) points-to information is known to be computationally expensive. Therefore many practical tools approximate the points-to information trading precision for efficiency. This often has adverse impact on computationally intensive analyses such as model checking. Past explorations in top-down approaches of fully flow- and context-sensitive points-to analysis (FCPA) have not scaled. We explore the alternative of bottom-up interprocedural approach which constructs summary flow functions for procedures to represent the effect of their calls. This approach has been effectively used for many analyses. However, this approach seems computationally expensive for FCPA which requires modelling unknown locations accessed indirectly through pointers. Such accesses are commonly handled by using placeholders to explicate unknown locations or by using multiple call-specific summary flow functions. We generalize the concept of points-to relations by using the counts of indirection levels leaving the unknown locations implicit. This allows us to create summary flow functions in the form of generalized points-to graphs (GPGs) without the need of placeholders. By design, GPGs represent both memory (in terms of classical points-to facts) and memory transformers (in terms of generalized points-to facts). We perform FCPA by progressively reducing generalized points-to facts to classical points-to facts. GPGs distinguish between may and must pointer updates thereby facilitating strong updates within calling contexts. The size of GPG for a procedure is linearly bounded by the number of variables and is independent of the number of statements in the procedure. Empirical measurements on SPEC benchmarks show that GPGs are indeed compact in spite of large procedure sizes. This allows us to scale FCPA to 158 kLoC using GPGs (compared to 35 kLoC reported by liveness-based FCPA). At a practical level, GPGs hold a promise of efficiency and scalability for FCPA without compromising precision. At a more general level, GPGs provide a convenient abstraction of memory in presence of pointers. Static analyses that are influenced by pointers may be able to use GPGs by combining them with their original abstractions. |
