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

Allocation-Site Abstraction One object per allocation site A 1 A a1 =inew A A(3H 二二二 2 A a2 =new A();H 3 Bb =inew E B();H B 3 16

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

Allocation-Site Abstraction One object per allocation site Adopted by all mainstream points-to analyses A 1 A a1 =fnew A()3H 二二二 2 A a2 =inew A(); 3 Bb =new B();H B 3 17

Allocation-Site Abstraction  One object per allocation site ◦ Adopted by all mainstream points-to analyses 17 1 A a1 = new A(); 2 A a2 = new A(); 3 B b = new B(); o1 A o2 A o3 B

Allocation-Site Abstraction Over-partition for call graph construction 1 A a1 =new A(; void foo(object o){ 2 A a2 =new A()3 o.toString(); 3 foo(a1); 4 foo(a2); A:toString() 18

Allocation-Site Abstraction  Over-partition for call graph construction 18 A::toString() o1 A o2 A void foo(Object o) { o.toString(); } 1 A a1 = new A(); 2 A a2 = new A(); 3 foo(a1); 4 foo(a2); o1 A o2 A

Allocation-Site Abstraction Over-partition for type-dependent clients Call graph construction Devirtualization May-fail casting 1 A a1 =new A()3 void foo(object o){ 2 A a2 =new A( o.tostring(); 3 foo(a1); Aa =(A)o; 4 foo(a2); 19

Allocation-Site Abstraction  Over-partition for type-dependent clients ◦ Call graph construction ◦ Devirtualization ◦ May-fail casting ◦ … 19 1 A a1 = new A(); 2 A a2 = new A(); 3 foo(a1); 4 foo(a2); o1 A o2 A void foo(Object o) { o.toString(); A a = (A) o; } o1 A o2 A

Type-Based Abstraction ·One object per type 1 A a1 new A A(); 2Aa2= new A(); 3 Bb new E B(); 20

Type-Based Abstraction  One object per type 20 1 A a1 = new A(); 2 A a2 = new A(); 3 B b = new B();