Efficient and Precise Points-to Analysis：Modeling the Heap by Merging Equivalent Automata

● 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