FSE 2016 All Events

24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering (FSE 2016), November 13–18, 2016, Seattle, WA, USA

Desktop Layout

Session 10: Static Analysis
Research Papers
Emerald 1, Chair: Mark Marron
On-Demand Strong Update Analysis via Value-Flow Refinement
Yulei Sui and Jingling Xue
(UNSW, Australia)
aec-badge-fse16-ae
Publisher's Version
Abstract: We present a new Strong UPdate Analysis for C programs, called Supa, that enables computing points-to information on-demand via value-flow refinement, in environments with small time and memory budgets such as IDEs. We formulate Supa by solving a graph-reachability problem on a value- flow graph representation of the program, so that strong updates are performed where needed, as long as the total analysis budget is not exhausted. Supa facilitates efficiency and precision tradeoffs by allowing different pointer analyses to be applied in a hybrid multi-stage analysis framework. We have implemented Supa in LLVM with its artifact available at [1]. We evaluate Supa by choosing uninitialized pointer detection as a major client on 12 open-source C programs. As the analysis budget increases, Supa achieves improved precision, with its single-stage flow-sensitive analysis reaching 97% of that achieved by whole-program flow- sensitive analysis by consuming about 0.19 seconds and 36KB of memory per query, on average (with a budget of at most 10000 value-flow edges per query).

Authors:


Time stamp: 2019-03-26T17:09:48+01:00