● Efficient and Precise Points-to Analysis: Modeling the Heap by Merging Equivalent Automata Tian Tan,Yue Li and Jingling Xue PLDI 2017 UNSW June,2017 SYDNEY
Efficient and Precise Points-to Analysis: Modeling the Heap by Merging Equivalent Automata Tian Tan, Yue Li and Jingling Xue PLDI 2017 June, 2017 1
A New Points-to Analysis Technique for Object-Oriented Programs 2
A New Points-to Analysis Technique for Object-Oriented Programs 2
Points-to Analysis ●Determines 。“which objects a variable can point to, 3
Points-to Analysis Determines ◦ “which objects a variable can point to?” 3
Uses of Points-to Analysis Clients Tools ●Security analysis Bug detection Soot DroidSafe Compiler optimization Program verification ①OOP专Chord Program understanding WALA T.3.WATSON UBRARIES FOR ANALYSIS ●0● 4
Uses of Points-to Analysis Clients Tools Security analysis Bug detection Compiler optimization Program verification Program understanding … Chord 4 …
Uses of Points-to Analysis Clients Tools ●Security analysis ·Bug detection Soot DroidSafe Compiler optimization Program verification ①OOP专Chord Program understanding WALA T.3.WATSON UBRARIES FOR ANALYSIS ●0● Call Graph 5
Uses of Points-to Analysis Clients Tools Security analysis Bug detection Compiler optimization Program verification Program understanding … Chord 5 … Call Graph
Existing Call Graph Construction On-the-fly construction (run with points-to analysis) o Precise o Inefficient 6
Existing Call Graph Construction 6 On-the-fly construction (run with points-to analysis) ◦ Precise ◦ Inefficient
Existing Call Graph Construction On-the-fly construction (run with points-to analysis) o Precise o Inefficient 3-object-sensitive points-to analysis o Very precise Adopted by.e.g.DOOP DroidSafe 有Chord 7
Existing Call Graph Construction 7 On-the-fly construction (run with points-to analysis) ◦ Precise ◦ Inefficient 3-object-sensitive points-to analysis ◦ Very precise ◦ Adopted by, e.g., 7 Chord
3-Object-Sensitive Points-to Analysis Analyze Java programs DOOP Intel Xeon E5 3.70GHz,128GB of memory Time budget:5 hours (18000 secs) 8
3-Object-Sensitive Points-to Analysis Analyze Java programs ◦ Intel Xeon E5 3.70GHz,128GB of memory ◦ Time budget: 5 hours (18000 secs) 8
3-Object-Sensitive Points-to Analysis Analyze Java programs DOOP Intel Xeon E5 3.70GHz,128GB of memory Time budget:5 hours (18000 secs) Analysis time(sec.) 14469 pmd (4 hours) Unscalable findbugs (>5 hours) 0 5000 10000 15000 9
3-Object-Sensitive Points-to Analysis Analyze Java programs ◦ Intel Xeon E5 3.70GHz,128GB of memory ◦ Time budget: 5 hours (18000 secs) 9 Unscalable (> 5 hours) 14469 (4 hours) 0 5000 10000 15000 findbugs pmd Analysis time (sec.)
Two Mainstreams of Points-to Analysis Techniques ●Model control-flow ●Model data-flow 10
Two Mainstreams of Points-to Analysis Techniques Model control-flow Model data-flow 10