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

Two Mainstreams of Points-to Analysis Techniques 。Model control-flow Context-sensitivity Call-site-sensitivity (PLDI'04,PLDI'06) Object-sensitivity (ISSTA'02,TOSEM'05,SAS'16) Type-sensitivity(POPL'I I) ●Model data-flow 11

Two Mainstreams of Points-to Analysis Techniques  Model control-flow ◦ Context-sensitivity  Call-site-sensitivity (PLDI’04, PLDI’06)  Object-sensitivity (ISSTA’02, TOSEM’05, SAS’16)  Type-sensitivity (POPL’11)  …  Model data-flow 11

Two Mainstreams of Points-to Analysis Techniques Model control-flow Context-sensitivity Call-site-sensitivity (PLDI'04,PLDI'06) Object-sensitivity (ISSTA'02,TOSEM'05,SAS'16) Type-sensitivity (POPL'II) ●Model data-flow Heap abstraction Allocation-site abstraction Type-based abstraction 12

Two Mainstreams of Points-to Analysis Techniques  Model control-flow ◦ Context-sensitivity  Call-site-sensitivity (PLDI’04, PLDI’06)  Object-sensitivity (ISSTA’02, TOSEM’05, SAS’16)  Type-sensitivity (POPL’11)  …  Model data-flow ◦ Heap abstraction  Allocation-site abstraction  Type-based abstraction  … 12

Two Mainstreams of Points-to Analysis Techniques Model control-flow Context-sensitivity Call-site-sensitivity (PLDI'04,PLDI'06) Object-sensitivity (ISSTA'02,TOSEM'05,SAS'16) Type-sensitivity(POPL'I I) ●Model data-flow Heap abstraction Allocation-site abstraction Type-based abstraction 13

Two Mainstreams of Points-to Analysis Techniques  Model control-flow ◦ Context-sensitivity  Call-site-sensitivity (PLDI’04, PLDI’06)  Object-sensitivity (ISSTA’02, TOSEM’05, SAS’16)  Type-sensitivity (POPL’11)  …  Model data-flow ◦ Heap abstraction  Allocation-site abstraction  Type-based abstraction  … 13

Heap Abstraction Dynamic Static execution analysis abstracted or partitioned Finite Infinite-size (abstract) heap objects 14

Heap Abstraction 14 Infinite-size heap Finite (abstract) objects Dynamic execution Static analysis abstracted or … partitioned …

Allocation-Site Abstraction One object per allocation site 1 A a1 new A A(); 2Aa2= new A(); 3 Bb new B(); 15

Allocation-Site Abstraction  One object per allocation site 15 1 A a1 = new A(); 2 A a2 = new A(); 3 B b = new B();