Value-Flow-Based Demand-Driven Pointer Analysis for C and C plus

doi:10.1109/TSE.2018.2869336

Value-Flow-Based Demand-Driven Pointer Analysis for C and C plus

2020-08-01

29

OA

AI

DOI：10.1109/TSE.2018.2869336

原文链接

查看原文

摘要

En 中文

We present Supa, a value-flow-based demand-driven flow- and context-sensitive pointer analysis with strong updates for C and C++ programs. Supa enables computing points-to information via value-flow refinement, in environments with small time and memory budgets. We formulate Supa by solving a graph-reachability problem on an inter-procedural value-flow graph representing a program's def-use chains, which are pre-computed efficiently but over-approximately. To answer a client query (a request for a variable's points-to set), Supa reasons about the flow of values along the pre-computed def-use chains sparsely (rather than across all program points), by performing only the work necessary for the query (rather than analyzing the whole program). In particular, strong updates are performed to filter out spurious def-use chains through value-flow refinement as long as the total budget is not exhausted. We have implemented Supa on top of LLVM (4.0.0) together with a comprehensive micro-benchmark suite after a years-long effort (consisting of around 400 test cases, including hand-written ones and the ones extracted from real programs). We have evaluated Supa by choosing uninitialized pointer detection and C++ virtual table resolution as two major clients, using 24 real-world programs including 18 open-source C programs and 6 large CPU2000/2006 C++ benchmarks. For uninitialized pointer client, Supa achieves improved precision as the analysis budget increases, with its flow-sensitive (context-insensitive) analysis reaching 97.4 percent of that achieved by whole-program Sparse Flow-Sensitive analysis (SFS) by consuming about 0.18 seconds and 65 KB of memory per query, on average (with a budget of at most 10,000 value-flow edges per query). With context-sensitivity also considered, Supa becomes more precise for some programs but also incurs more analysis times. To further demonstrate the effectiveness of Supa, we have also evaluated Supa in resolving C++ virtual tables by querying the function pointers at every virtual callsite. Compared to analysis without strong updates for heap objects, Supa's demand-driven context-sensitive strong update analysis reduces 7.35 percent spurious virtual table targets with only 0.4 secs per query, on average.

Keyword:

C plus plus languages

Resource management

Open source software

Sensitivity

Reachability analysis

Instruction sets

Registers

Strong updates

value flow

pointer analysis

flow sensitivity

Value-Flow-Based Demand-Driven Pointer Analysis for C and C plus

摘要

AI总结

期刊

机构

引用论文