Learning Graph-Based Heuristics for Pointer Analysis without Handcrafting Application-Specific Features
Fri 20 Nov 2020 19:20 - 19:40 at SPLASH-III - F-1B Chair(s): Alex Potanin, Steve Blackburn
We present Graphick, a new technique for automatically learning graph-based heuristics for pointer analysis. Striking a balance between precision and scalability of pointer analysis requires designing good analysis heuristics. For example, because applying context sensitivity to all methods in a real-world program is impractical, pointer analysis typically uses a heuristic to employ context sensitivity only when it is necessary.
Past research has shown that exploiting the program's graph structure is a promising way of developing cost-effective analysis heuristics, promoting the recent trend of ``graph-based heuristics'' that work on the graph representations of programs obtained from a pre-analysis.
Although promising, manually developing such heuristics remains challenging, requiring a great deal of expertise and laborious effort.
In this paper, we aim to reduce this burden by learning graph-based heuristics automatically, in particular without hand-crafted application-specific features. To do so, we present a feature language to describe graph structures and an algorithm for learning analysis heuristics within the language.
We implemented Graphick on top of Doop and used it to learn graph-based heuristics for object sensitivity and heap abstraction.
The evaluation results show that our approach is general and can generate high-quality heuristics. For both instances,
the learned heuristics are as competitive as the existing state-of-the-art heuristics designed manually by analysis experts.
Fri 20 Nov Times are displayed in time zone: Central Time (US & Canada) change
07:00 - 08:20 | F-1BOOPSLA at SPLASH-III +12h Chair(s): Aviral GoelNortheastern University, Sophia DrossopoulouImperial College London | ||
07:00 20mTalk | Incremental Predicate Analysis for Regression Verification OOPSLA Link to publication DOI Media Attached | ||
07:20 20mTalk | Learning Graph-Based Heuristics for Pointer Analysis without Handcrafting Application-Specific Features OOPSLA Link to publication DOI Media Attached | ||
07:40 20mTalk | TacTok: Semantics-Aware Proof Synthesis OOPSLA Emily FirstUniversity of Massachusetts at Amherst, Yuriy BrunUniversity of Massachusetts Amherst, Arjun GuhaUniversity of Massachusetts at Amherst Link to publication DOI Pre-print Media Attached | ||
08:00 20mTalk | Guiding Dynamic Programing via Structural Probability for Accelerating Programming by Example OOPSLA Ruyi JiPeking University, Yican SunPeking University, Yingfei XiongPeking University, Zhenjiang HuPeking University Link to publication DOI Media Attached |
19:00 - 20:20 | F-1BOOPSLA at SPLASH-III Chair(s): Alex PotaninVictoria University of Wellington, Steve BlackburnAustralian National University | ||
19:00 20mTalk | Incremental Predicate Analysis for Regression Verification OOPSLA Link to publication DOI Media Attached | ||
19:20 20mTalk | Learning Graph-Based Heuristics for Pointer Analysis without Handcrafting Application-Specific Features OOPSLA Link to publication DOI Media Attached | ||
19:40 20mTalk | TacTok: Semantics-Aware Proof Synthesis OOPSLA Emily FirstUniversity of Massachusetts at Amherst, Yuriy BrunUniversity of Massachusetts Amherst, Arjun GuhaUniversity of Massachusetts at Amherst Link to publication DOI Pre-print Media Attached | ||
20:00 20mTalk | Guiding Dynamic Programing via Structural Probability for Accelerating Programming by Example OOPSLA Ruyi JiPeking University, Yican SunPeking University, Yingfei XiongPeking University, Zhenjiang HuPeking University Link to publication DOI Media Attached |