Efficient and Precise Points-to Analysis: Modeling the Heap by Merging Equivalent Automata Tian Tan* Yue Li*Jingling Xue School of Computer Science and Engineering,UNSW,Australia Abstract Every points-to analysis,especially for object-oriented lan- Mainstream points-to analysis techniques for object-oriented guages such as Java and C#,requires a heap abstraction for languages rely predominantly on the allocation-site abstrac- partitioning the infinitely-sized heap into a finite number tion to model heap objects.We present MAHJONG,a novel of(abstract)objects.For object-oriented programs,context- heap abstraction that is specifically developed to address sensitivity is important for achieving useful precision.Due to the needs of an important class of type-dependent clients, many years of research,context-sensitivity can be achieved such as call graph construction,devirtualization and may- by three main approaches with different efficiency and pre- fail casting.By merging equivalent automata representing cision tradeoffs:call-site-sensitivity [15,22,36,42,51,53]. type-consistent objects that are created by the allocation- object-sensitivity [29,40,48]and type-sensitivity [39]. site abstraction,MAHJONG enables an allocation-site-based However,little progress has been made on developing points-to analysis to run significantly faster while achieving heap abstractions for points-to analysis.Mainstream points- nearly the same precision for type-dependent clients. to analysis frameworks for Java,such as CHORD [10], MAHJONG is simple conceptually,efficient,and drops DOOP [14],SOOT [49]and WALA [50],rely predominantly easily on any allocation-site-based points-to analysis.We on the allocation-site abstraction to model heap objects.In demonstrate its effectiveness by discussing some insights on this case,distinct allocation sites are represented by distinct why it is a better alternative of the allocation-site abstraction (abstract)objects,with one object per site,which can be fur- for type-dependent clients and evaluating it extensively on ther separated context-sensitively in an orthogonal manner. 12 large real-world Java programs with five context-sensitive As programming languages become more heap-intensive, points-to analyses and three widely used type-dependent the need for effective heap abstractions is greater [19,38. clients.MAHJONG is expected to provide significant benefits 44].The suitability of the allocation-site abstraction as a uni for many program analyses where call graphs are required. versal solution for all clients of points-to analysis needs to be revisited.While maximizing the precision for may-alias, CCS Concepts·Theory of computation→Program this abstraction often over-partitions the heap without im- analysis proving the precision much for an important class of type- dependent clients such as call graph construction,devirtu- Keywords points-to analysis.heap abstraction alization and may-fail casting,causing often the underlying points-to analysis to be unscalable for large programs.For 1.Introduction this reason,WALA [50]and DOOP [14],provide an option Pointer Analyses should be designed to be appropriate for all objects of a certain class,such as java.lang.String in cost and precision for specific groups of client prob- or java.lang.StringBuffer,to be merged ad hocly. lems.We do not need a different pointer analysis per In this paper,we present MAHJONG,a novel heap ab- client problem,but rather we should look for classes of straction that is specifically developed to address the needs client problems with similar needs. of type-dependent clients.Given a program,we first create a lightweight alternative of the allocation-site abstraction by Barbara Ryder [17] performing a fast but imprecise allocation-site-based points- These authors contributed equally to this work to analysis as a pre-analysis and then use it to drive a subse- quent points-to analysis.Based on the points-to information found during the pre-analysis,MAHJONG merges two ob- Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee pr jects if both are type-consistent,i.e..if the objects reached ovided that opies for advantage and that copies bear this notice and the full cita from both along the same sequence of field accesses have on the first page.Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted.To copy otherwise,or republish. a common type.We formulate the problem of checking the to post on servers or to redistribute to lists,requires prior specific permission and/or a type-consistency of two objects as one of testing the equiv- fee.Request permissions from Permissions@acm.org. alence of two sequential automata in almost linear time,by PLDI'17,June 18-23,2017,Barcelona,Spain 92017ACM978-1-4503-4988-8/1706.S15.00 applying a classic Hopcroft-Karp algorithm [18]with minor nttp://dx.doi.org/10.1145/3062341.3062360 278
Efficient and Precise Points-to Analysis: Modeling the Heap by Merging Equivalent Automata Tian Tan∗ Yue Li ∗ Jingling Xue School of Computer Science and Engineering, UNSW, Australia Abstract Mainstream points-to analysis techniques for object-oriented languages rely predominantly on the allocation-site abstraction to model heap objects. We present MAHJONG, a novel heap abstraction that is specifically developed to address the needs of an important class of type-dependent clients, such as call graph construction, devirtualization and mayfail casting. By merging equivalent automata representing type-consistent objects that are created by the allocationsite abstraction, MAHJONG enables an allocation-site-based points-to analysis to run significantly faster while achieving nearly the same precision for type-dependent clients. MAHJONG is simple conceptually, efficient, and drops easily on any allocation-site-based points-to analysis. We demonstrate its effectiveness by discussing some insights on why it is a better alternative of the allocation-site abstraction for type-dependent clients and evaluating it extensively on 12 large real-world Java programs with five context-sensitive points-to analyses and three widely used type-dependent clients. MAHJONG is expected to provide significant benefits for many program analyses where call graphs are required. CCS Concepts •Theory of computation → Program analysis Keywords points-to analysis, heap abstraction 1. Introduction Pointer Analyses should be designed to be appropriate in cost and precision for specific groups of client problems. We do not need a different pointer analysis per client problem, but rather we should look for classes of client problems with similar needs. — Barbara Ryder [17] ∗ These authors contributed equally to this work Every points-to analysis, especially for object-oriented languages such as Java and C#, requires a heap abstraction for partitioning the infinitely-sized heap into a finite number of (abstract) objects. For object-oriented programs, contextsensitivity is important for achieving useful precision. Due to many years of research, context-sensitivity can be achieved by three main approaches with different efficiency and precision tradeoffs: call-site-sensitivity [15, 22, 36, 42, 51, 53], object-sensitivity [29, 40, 48] and type-sensitivity [39]. However, little progress has been made on developing heap abstractions for points-to analysis. Mainstream pointsto analysis frameworks for Java, such as CHORD [10], DOOP [14], SOOT [49] and WALA [50], rely predominantly on the allocation-site abstraction to model heap objects. In this case, distinct allocation sites are represented by distinct (abstract) objects, with one object per site, which can be further separated context-sensitively in an orthogonal manner. As programming languages become more heap-intensive, the need for effective heap abstractions is greater [19, 38, 44]. The suitability of the allocation-site abstraction as a universal solution for all clients of points-to analysis needs to be revisited. While maximizing the precision for may-alias, this abstraction often over-partitions the heap without improving the precision much for an important class of typedependent clients such as call graph construction, devirtualization and may-fail casting, causing often the underlying points-to analysis to be unscalable for large programs. For this reason, WALA [50] and DOOP [14], provide an option for all objects of a certain class, such as java.lang.String or java.lang.StringBuffer, to be merged ad hocly. In this paper, we present MAHJONG, a novel heap abstraction that is specifically developed to address the needs of type-dependent clients. Given a program, we first create a lightweight alternative of the allocation-site abstraction by performing a fast but imprecise allocation-site-based pointsto analysis as a pre-analysis and then use it to drive a subsequent points-to analysis. Based on the points-to information found during the pre-analysis, MAHJONG merges two objects if both are type-consistent, i.e., if the objects reached from both along the same sequence of field accesses have a common type. We formulate the problem of checking the type-consistency of two objects as one of testing the equivalence of two sequential automata in almost linear time, by applying a classic Hopcroft-Karp algorithm [18] with minor Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Permissions@acm.org. PLDI’17, June 18–23, 2017, Barcelona, Spain c 2017 ACM. 978-1-4503-4988-8/17/06...$15.00 http://dx.doi.org/10.1145/3062341.3062360 278
modifications.MAHJONG is simple conceptually and drops 1Ax=newA();/∥o 10 class A easily on any allocation-site-based points-to analysis. 2Ay=newA();/∥o 11Af: Compared to the allocation-site abstraction,MAHJONG 3 A z new A();//o 12 void foo(){... 133 allows a points-to analysis to run significantly faster while 4 x.f new B();//of 14 class B extends A achieving nearly the same precision for type-dependent 5 y.f new c();/o 15 void foo(){... clients.Thus,MAHJONG makes it possible to accelerate a 6z.f=newc();/o唱 16} given points-to analysis or replace it with a more precise 7 Aa z.f; 17 class C extends A but usually more costly points-to analysis that is either in- 8 a.foo(); 18 void foo(){... efficient or unscalable if the allocation-site abstraction is 9C c=(C)a; 19} used.MAHJONG is expected to provide significant benefits to many program analyses,such as bug detection,security Figure 1.An example program illustrating object merging. analysis,program verification and program understanding, where call graphs are required [3,5,7,16,26,31,32,43, 54,55]. able.In this paper,we aim to improve this by looking for We demonstrate the effectiveness of MAHJONG by dis- a lightweight alternative that satisfies the needs of type- cussing some insights on why it is a better alternative of dependent clients,but not necessarily others such as may- the allocation-site abstraction for type-dependent clients and alias.To this end,we would like to avoid distinguishing two conducting an evaluation extensively on 12 large Java pro- objects if merging them loses no or little precision. grams with five widely used context-sensitive points-to anal- In Section 2.1,we see that blindly merging objects of yses and three significant type-dependent clients,call graph the same type is ineffective.In Section 2.2,we describe construction,devirtualization and may-fail casting [20,22, our solution that merges objects representing equivalent au- 39,40,42].Take,3obj,a 3-object-sensitive points-to anal- tomata only.For object-oriented programs,merging objects ysis [29],the most precise one used in our evaluation,as amounts to merging their corresponding allocation sites. an example.For the four programs that can be analyzed scalably under 3obj,our MAHJONG-based 3obj runs 131X 2.1 Allocation-Type Abstraction:A Naive Solution faster,on average,while achieving nearly the same precision In this so-called allocation-type abstraction,all objects with for all the three clients.For the remaining eight,where 3obj the same type are merged,with one object per type.As is unscalable in 5 hours each,our MAHJONG-based 3obj can previously noted,this naive solution often gains efficiency analyze five of them in an average of 33.42 minutes. but may incur a significant loss of precision [19,27,38.51]. In summary,our paper makes the following contributions: We present MAHJONG,a new heap abstraction that can Example 2.1.Consider Figure 1,where of represents the significantly scale an allocation-site-based points-to anal- abstract object of type t created at the allocation site at line ysis for object-oriented programs while achieving nearly i.We will use this notation in the rest of the paper. the same precision for type-dependent clients. For the three type-dependent clients,call graph construc- tion,devirtualization and may-fail casting,only lines 8-9 We formulate the problem of checking the type-consistency are relevant.According to an allocation-site-based Ander of two objects as one of testing the equivalence of two sen's points-to analysis [4].z,y and z point to of,o2 and automata,which is solvable in almost linear time. og,respectively.As r.f,y.f and z.f are not aliases,a points We implement MAHJONG as a stand-alone open-source to of.Thus,a.foo()at line 8 is a mono-call and can thus be tool.MAHJONG is simple (with only 1500 LOC of Java devirtualized,and in addition.the cast(C)at line 9 is safe. in total)and drops easily on any allocation-site-based However,if of,o2 and og are merged,then r.f,y.f and points-to analysis. 2.f will be aliases,causing a to also point too.As a result, We conduct extensive experiments to evaluate the effec- a.foo()becomes a poly-call and thus non-devirtualizable.In tiveness of MAHJONG in practice. addition,the cast (C)is no longer considered safe Consider pmd,a program analyzed by (1)3obj-a 3- 2.Motivation object-sensitive points-to analysis [29]using the allocation- For points-to analysis,type-dependent clients,such as call site abstraction,(2)T-3obj-3obj using the allocation-type graph construction,devirtualization and may-fail casting, abstraction,and (3)M-3obj-3obj using the MAHJONG share similar needs:their precision depends on the types heap abstraction introduced in this paper.For 3obj,pmd of pointed-to objects rather than the pointed-to objects is analyzed in 14469.3 seconds,allowing 44004 call graph themselves.For such clients,the conventional allocation- edges to be discovered.T-3obj is the fastest (50.3 seconds), site abstraction is often too fine-grained,contributing little but is the most imprecise(50666 call graph edges).In con- to improving their precision but rendering the underlying trast,M-3obj is as precise as 3obj(44016 call graph edges) points-to analysis unduly inefficient or eventually unscal- but is also nearly as fast as T-3obj(127.7 seconds). 279
modifications. MAHJONG is simple conceptually and drops easily on any allocation-site-based points-to analysis. Compared to the allocation-site abstraction, MAHJONG allows a points-to analysis to run significantly faster while achieving nearly the same precision for type-dependent clients. Thus, MAHJONG makes it possible to accelerate a given points-to analysis or replace it with a more precise but usually more costly points-to analysis that is either inefficient or unscalable if the allocation-site abstraction is used. MAHJONG is expected to provide significant benefits to many program analyses, such as bug detection, security analysis, program verification and program understanding, where call graphs are required [3, 5, 7, 16, 26, 31, 32, 43, 54, 55]. We demonstrate the effectiveness of MAHJONG by discussing some insights on why it is a better alternative of the allocation-site abstraction for type-dependent clients and conducting an evaluation extensively on 12 large Java programs with five widely used context-sensitive points-to analyses and three significant type-dependent clients, call graph construction, devirtualization and may-fail casting [20, 22, 39, 40, 42]. Take, 3obj, a 3-object-sensitive points-to analysis [29], the most precise one used in our evaluation, as an example. For the four programs that can be analyzed scalably under 3obj, our MAHJONG-based 3obj runs 131X faster, on average, while achieving nearly the same precision for all the three clients. For the remaining eight, where 3obj is unscalable in 5 hours each, our MAHJONG-based 3obj can analyze five of them in an average of 33.42 minutes. In summary, our paper makes the following contributions: • We present MAHJONG, a new heap abstraction that can significantly scale an allocation-site-based points-to analysis for object-oriented programs while achieving nearly the same precision for type-dependent clients. • We formulate the problem of checking the type-consistency of two objects as one of testing the equivalence of two automata, which is solvable in almost linear time. • We implement MAHJONG as a stand-alone open-source tool. MAHJONG is simple (with only 1500 LOC of Java in total) and drops easily on any allocation-site-based points-to analysis. • We conduct extensive experiments to evaluate the effectiveness of MAHJONG in practice. 2. Motivation For points-to analysis, type-dependent clients, such as call graph construction, devirtualization and may-fail casting, share similar needs: their precision depends on the types of pointed-to objects rather than the pointed-to objects themselves. For such clients, the conventional allocationsite abstraction is often too fine-grained, contributing little to improving their precision but rendering the underlying points-to analysis unduly inefficient or eventually unscal- 1 A x = new A(); // o A 1 2 A y = new A(); // o A 2 3 A z = new A(); // o A 3 4 x.f = new B(); // o B 4 5 y.f = new C(); // o C 5 6 z.f = new C(); // o C 6 7 A a = z.f; 8 a.foo(); 9 C c = (C) a; 10 class A { 11 A f; 12 void foo() {...} 13 } 14 class B extends A { 15 void foo() {...} 16 } 17 class C extends A { 18 void foo() {...} 19 } Figure 1. An example program illustrating object merging. able. In this paper, we aim to improve this by looking for a lightweight alternative that satisfies the needs of typedependent clients, but not necessarily others such as mayalias. To this end, we would like to avoid distinguishing two objects if merging them loses no or little precision. In Section 2.1, we see that blindly merging objects of the same type is ineffective. In Section 2.2, we describe our solution that merges objects representing equivalent automata only. For object-oriented programs, merging objects amounts to merging their corresponding allocation sites. 2.1 Allocation-Type Abstraction: A Naive Solution In this so-called allocation-type abstraction, all objects with the same type are merged, with one object per type. As previously noted, this naive solution often gains efficiency but may incur a significant loss of precision [19, 27, 38, 51]. Example 2.1. Consider Figure 1, where o t i represents the abstract object of type t created at the allocation site at line i. We will use this notation in the rest of the paper. For the three type-dependent clients, call graph construction, devirtualization and may-fail casting, only lines 8 – 9 are relevant. According to an allocation-site-based Andersen’s points-to analysis [4], x, y and z point to o A 1 , o A 2 and o A 3 , respectively. As x.f, y.f and z.f are not aliases, a points to o C 6 . Thus, a.foo() at line 8 is a mono-call and can thus be devirtualized, and in addition, the cast (C) at line 9 is safe. However, if o A 1 , o A 2 and o A 3 are merged, then x.f, y.f and z.f will be aliases, causing a to also point to o B 4 . As a result, a.foo() becomes a poly-call and thus non-devirtualizable. In addition, the cast (C) is no longer considered safe. Consider pmd, a program analyzed by (1) 3obj—a 3- object-sensitive points-to analysis [29] using the allocationsite abstraction, (2) T-3obj—3obj using the allocation-type abstraction, and (3) M-3obj—3obj using the MAHJONG heap abstraction introduced in this paper. For 3obj, pmd is analyzed in 14469.3 seconds, allowing 44004 call graph edges to be discovered. T-3obj is the fastest (50.3 seconds), but is the most imprecise (50666 call graph edges). In contrast, M-3obj is as precise as 3obj (44016 call graph edges) but is also nearly as fast as T-3obj (127.7 seconds). 279
Two objects with the same type are type-consistent if 0 traversing from the two objects along the same sequence of field names always lead to objects of one single type. Definition 2.1(Type-Consistent Objects).Two objects,o and oj,with the same type are said to be type-consistent, denoted oi=oj,if for every sequence of field names. f =f1.f2.....fn,the following two conditions hold: Figure 2.Field points-to graph rooted at of and o. 1.{to|o∈pts(o.f)}={t[o|o∈pts(oj-f)},and 2.2 MAHJONG:Our Solution 2.{tlo]loE pts(oi.f))=1. To address the needs of type-dependent clients,MAHJONG In Figure 2,of and of are type-consistent.For the objects is designed to maximally preserve the precision of the reached from of and of,along f.f.h,g and g.k,their sets allocation-site abstraction while reaping the efficiency of the of types are (U),[){X}and (Y),respectively. allocation-type abstraction as much as possible.For a given We illustrate the intuition behind the notion of type- program,we first build a heap abstraction by performing a consistency with an example discussed below. pre-analysis,i.e.,a fast but imprecise allocation-site-based Example 2.3.Let us return to Figure 1,for which the Andersen's points-to analysis [4]and then use it to guide a subsequent points-to analysis.Based on the pre-analysis, allocation-type abstraction will merge of,o2 and o(Sec- tion 2.1).By Definition 2.1,o and o are type-consistent we define type-consistent objects that can be merged(Sec- tion 2.2.1)and formulate the problem of checking the type- (as os.f points to of and og.f points to o)but of is not type-consistent with any (as of.f points to of).After o2 consistency of two objects as one of testing the equivalence of two automata in almost linear time(Section 2.2.2). and o are merged,y.f and z.f are regarded as aliases. Thus,a will point to not only o as before but also of spu- 2.2.1 Defining Type-Consistent Objects riously.However,as os and o have the same type C,the precision of call graph construction and devirtualization at After the pre-analysis,the field points-to graph(FPG)is line 8 and may-fail casting at line 9 will not be affected. available,representing the points-to information for the ob- ject fields.To facilitate a subsequent reduction of the prob- Let us examine Definition 2.1.Condition 1 is self- lem of checking type-consistency as one of testing the equiv- explanatory in order to maximally preserve precision for alence of automata,we introduce the field points-to graph type-dependent clients.What is the rationale behind Con- rooted at an object o as go =(H,F,a,o,T,T).H is the set dition 2?The pre-analysis is fast but imprecise.Enforcing of objects reachable from o.F is the set of field names tra Condition 2 maximally avoids precision loss,as shown below. versed along the way.The points-to relations for the object Pre-Analysis A More Precise Points-to Analysis fields are defined by a field points-to map a HxF P(H).T is the set of types of the objects in H.The object- to-type map t:HT reveals the type of an object. Figure 2 gives the field points-to graphs rooted at of and o,by using the same notation for objects in Figure 1. (a)Allocation-Site (b)Allocation-Site (c)MAHONG without Abstraction Abstraction Condition 2 Example 2.2.Consider of first in Figure 2.gor =(H,F, a,o,T,).H={,,哈，o；F={f,g,h,k Figure 3.Illustrating Condition 2 in Definition 2.1. ao,fl={oMao,h={og,ao,g={哈1， and alo哈，={ogT={T,U,X,Y};and tlo1?]=T, Example 2.4.Suppose of.f and of.f point to bothox rou]=U.tlo ]=X,and t[os ]=Y.Similarly,gor can and o during the pre-analysis(Figure 3(a))but of and o3, be constructed. respectively,in a more precise allocation-site-based points- Unlike the allocation-type abstraction,where all the ob- to analysis,A(Figure 3(b)).If Condition 2 is ignored,o and of will become type-consistent according to the pre- jects with the same type are merged blindly,we will merge so-called type-consistent objects,thereby avoiding the im- analysis and thus merged into,say,of(represented by of precision introduced by the allocation-type abstraction. or of).Running A with this new abstraction will result in Let f =f1.f2.....fn,where n 0,be a sequence of precision loss,as o.f and of.f now point to objects of field names.For the field points-to graph go rooted at an types X and Y(Figure 3(c)). 口 object o,we write pts(o.f)to represent the set of objects In Definition 2.1,the type-consistency relation is an that can be reached from o along any path of points-to edges equivalence relation.It is straightforward to verify that =is labeled by fi.f2.....fn in o in that order.In Figure 2. reflexive,symmetric and transitive. pts(of.f)=tog}and pts(of.f.h)=to,o. Let H be the set of all abstract objects in the program. 280
3 U 5 X 9 Y 11 g Y k 1 T o 7 Y h h f o o o o o 2 T 4 U 6 X 8 Y g f h k o o o o 1 T o 2 T G Go Figure 2. Field points-to graph rooted at o T 1 and o T 2 . 2.2 MAHJONG: Our Solution To address the needs of type-dependent clients, MAHJONG is designed to maximally preserve the precision of the allocation-site abstraction while reaping the efficiency of the allocation-type abstraction as much as possible. For a given program, we first build a heap abstraction by performing a pre-analysis, i.e., a fast but imprecise allocation-site-based Andersen’s points-to analysis [4] and then use it to guide a subsequent points-to analysis. Based on the pre-analysis, we define type-consistent objects that can be merged (Section 2.2.1) and formulate the problem of checking the typeconsistency of two objects as one of testing the equivalence of two automata in almost linear time (Section 2.2.2). 2.2.1 Defining Type-Consistent Objects After the pre-analysis, the field points-to graph (FPG) is available, representing the points-to information for the object fields. To facilitate a subsequent reduction of the problem of checking type-consistency as one of testing the equivalence of automata, we introduce the field points-to graph rooted at an object o as Go = (H, F, α, o, T , τ). H is the set of objects reachable from o. F is the set of field names traversed along the way. The points-to relations for the object fields are defined by a field points-to map α : H × F 7→ P(H). T is the set of types of the objects in H. The objectto-type map τ : H 7→ T reveals the type of an object. Figure 2 gives the field points-to graphs rooted at o T 1 and o T 2 , by using the same notation for objects in Figure 1. Example 2.2. Consider o T 2 first in Figure 2. Go T 2 = (H, F, α, oT 2 , T , τ). H = {o T 2 , oU 4 , oX 6 , oY 8 }; F = {f, g, h, k}; α[o T 2 , f] = {o U 4 }, α[o U 4 , h] = {o Y 8 }, α[o T 2 , g] = {o X 6 }, and α[o X 6 , k] = {o Y 8 }; T = {T, U, X, Y }; and τ[o T 2 ] = T, τ[o U 4 ] = U, τ[o X 6 ] = X, and τ[o Y 8 ] = Y . Similarly, Go T 1 can be constructed. Unlike the allocation-type abstraction, where all the objects with the same type are merged blindly, we will merge so-called type-consistent objects, thereby avoiding the imprecision introduced by the allocation-type abstraction. Let ¯f = f1.f2. · · · .fn, where n > 0, be a sequence of field names. For the field points-to graph Go rooted at an object o, we write pts(o. ¯f) to represent the set of objects that can be reached from o along any path of points-to edges labeled by f1, f2, . . . , fn in Go in that order. In Figure 2, pts(o T 1 .f) = {o U 3 } and pts(o T 1 .f.h) = {o Y 7 , oY 9 }. Two objects with the same type are type-consistent if traversing from the two objects along the same sequence of field names always lead to objects of one single type. Definition 2.1 (Type-Consistent Objects). Two objects, oi and oj , with the same type are said to be type-consistent, denoted oi ≡ oj , if for every sequence of field names, ¯f = f1.f2. · · · .fn, the following two conditions hold: 1. {τ[o] | o ∈ pts(oi . ¯f)} = {τ[o] | o ∈ pts(oj . ¯f)}, and 2. {τ[o] | o ∈ pts(oi . ¯f)} = 1. In Figure 2, o T 1 and o T 2 are type-consistent. For the objects reached from o T 1 and o T 2 , along f, f.h, g and g.k, their sets of types are {U}, {Y }, {X} and {Y }, respectively. We illustrate the intuition behind the notion of typeconsistency with an example discussed below. Example 2.3. Let us return to Figure 1, for which the allocation-type abstraction will merge o A 1 , o A 2 and o A 3 (Section 2.1). By Definition 2.1, o A 2 and o A 3 are type-consistent (as o A 2 .f points to o C 5 and o A 3 .f points to o C 6 ) but o A 1 is not type-consistent with any (as o A 1 .f points to o B 4 ). After o A 2 and o A 3 are merged, y.f and z.f are regarded as aliases. Thus, a will point to not only o C 6 as before but also o C 5 spuriously. However, as o C 5 and o C 6 have the same type C, the precision of call graph construction and devirtualization at line 8 and may-fail casting at line 9 will not be affected. Let us examine Definition 2.1. Condition 1 is selfexplanatory in order to maximally preserve precision for type-dependent clients. What is the rationale behind Condition 2? The pre-analysis is fast but imprecise. Enforcing Condition 2 maximally avoids precision loss, as shown below. f O T i f f Pre-Analysis A More Precise Points-to Analysis (a) Allocation-Site Abstraction (b) Allocation-Site Abstraction (c) MAHJONG without Condition 2 O X 1 O Y 2 O T i O X 1 f O T j O Y 2 O T j f f O X 1 O Y 2 O T k f f O X 1 O Y 2 Figure 3. Illustrating Condition 2 in Definition 2.1. Example 2.4. Suppose o T i .f and o T j .f point to both o X 1 and o Y 2 during the pre-analysis (Figure 3(a)) but o X 1 and o Y 2 , respectively, in a more precise allocation-site-based pointsto analysis, A (Figure 3(b)). If Condition 2 is ignored, o T i and o T j will become type-consistent according to the preanalysis and thus merged into, say, o T k (represented by o T i or o T j ). Running A with this new abstraction will result in precision loss, as o T i .f and o T j .f now point to objects of types X and Y (Figure 3(c)). In Definition 2.1, the type-consistency relation ≡ is an equivalence relation. It is straightforward to verify that ≡ is reflexive, symmetric and transitive. Let H be the set of all abstract objects in the program. 280
Equivalent AutomataType-Consistent Objects Sequential Automata Ao=(Q,∑，8，qo,「，Y)←→Co=(gHF,a,o,T,t)o-Rooted Field Points-to Graph A set of states-.- 0 →H… ......Aset of heap objects A set of input symbols… …∑ F..................Aset of field identifiers The next-state map:Q×∑→P(Q) The field points-to map:Hx F-P(H) The initial state............ 0 ...The object to be checked A set of output symbols ...…Aset of types The output map:Q→T The object-to-type map:H-T Figure 4.The mapping of a field points-to graph rooted at an object to a sequential automaton. Definition 2.2(MAHJONG's Heap Abstraction).Given the Therefore,we have reduced the problem of checking the quotient set,H/=,MAHJONG will merge all the objects in type-consistency of of and of to one of testing the equiva- the same equivalence class into one object. lence of their corresponding automata Aor and Aor,which is solvable by the Hopcroft-Karp algorithm [18]with minor Therefore,the key insight behind our new heap abstrac- tion is not to distinguish two (container)objects of the same modifications.The worst-case time complexity is O(x type if both containers store the objects of the same type at QargerD),which is almost linear in terms of |Qargerl,where all their corresponding nested sub-containers. Qarger is the set of states of the larger automaton [18] How do we check the type-consistency of two objects Example 2.6.Continuing from Example 2.5,we see easily efficiently,especially for large programs with a large number that of and oz are type-consistent (Figure 2)since their of heap objects,field names and class types?Enumerating all corresponding automata Ar and A are equivalent. the possible field access paths f as required in Definition 2.1, especially in the presence of cycles,may be exponential in 3.MAHJONG terms of the number of edges traversed [28,34].causing We first give an overview of MAHJONG that consists of four the pre-analysis to be too inefficient or even unscalable.We components(Section 3.1).We then describe each component describe a fast and elegant solution below. in detail (Sections 3.2-3.5).Finally,we discuss MAHJONG- 2.2.2 Merging Equivalent Automata based points-to analysis (Section 3.6). We transform the problem of checking the type-consistency 3.1 Overview of two objects into one of testing the equivalence of two au- As shown in Figure 5,MAHJONG takes the field points-to tomata.Figure 4 relates the field points-to graph rooted at graph(FPG)computed by a pre-analysis(Section 2.2.1)as an object o.Go=(H,F,a,o,T,T),to a 6-tuple sequential input and builds a heap abstraction(Definition 2.2)to be automatonA。=(Q,∑，d,go,T,y）[1],which is more gen- used by a subsequent points-to analysis.The pre-analysis is eral than a traditional(5-tuple)automaton.In fact,a 5-tuple fast but imprecise.by using Andersen's algorithm [4]with automaton can be turned into a 6-tuple automaton,if its ac- the allocation-site abstraction,context-insensitively.The cepting (acc)and non-accepting (non-acc)states are distin- subsequent points-to analysis will be more precise,usually guished by y:QI,where I=facc,non-acc}. performed context-sensitively,especially for object-oriented Example 2.5.Continuing from Example 2.2(Figure 2),the programs,based on the MAHJONG heap abstraction. automaton Aor for Gor =(H,F,a,o,T,t)is obtained MAHJONG iteratively picks a pair of objects of and of according to Figure 4.Similarly.Aor is constructed. □ with the same type T and merges them if they are type- consistent,until no such pair can be found.Given o and o The behavior ofAo,which can be an NFA (consisting of their corresponding NFAs,NFAr and NFAT,are first built multiple edges with the same label leaving a state),is: by using the NFA Builder.Then the two NFAs are converted BA。:*→P(T) into their equivalent DFAs,DFAT and DFAT,by using the DFA Converter.Next,the Automata Equivalence Checker If Ao finally reaches the states,s1,s2,...,sn,after having determines whether DFA?and DFA?are equivalent or not. read an input w in >"then BA (w)=UP1y[si]. Finally,the Heap Modeler outputs a new heap abstraction. Let of and of be two objects with the same type T.Let The detailed algorithms are given in Section 4. their automata Ao?and Ao be built as shown in Figure 4. of and of are type-consistent if,for every input w in *(1) 3.2 The NFA Builder BA(w)=BA(w)(Condition 1 of Definition 2.1)and (2(w)=1(Condition 2 of Definition 2.1). The NFA builder takes an object o,with the field points-to graph go rooted at o,and constructs a 6-tuple NFA A 281
A A set of states A set of input symbols The next-state map: A set of output symbols The initial state The output map: Q ∑ q0 H F o T A set of heap objects A set of field identifiers The object to be checked A set of types The object-to-type map: H⟶ Q × ∑⟶ (Q) The field points-to map: × ⟶ ( ) Equivalent Automata Type-Consistent Objects δ Γ γ α Q ⟶Γ τ Sequential Automata Q ∑ q Γ = ( H, , , , F α o T, ) -Rooted Field Points-to Graph 0 o = ( , , , , δ , γ ) o τ o T P H F P H G Figure 4. The mapping of a field points-to graph rooted at an object to a sequential automaton. Definition 2.2 (MAHJONG’s Heap Abstraction). Given the quotient set, H / ≡, MAHJONG will merge all the objects in the same equivalence class into one object. Therefore, the key insight behind our new heap abstraction is not to distinguish two (container) objects of the same type if both containers store the objects of the same type at all their corresponding nested sub-containers. How do we check the type-consistency of two objects efficiently, especially for large programs with a large number of heap objects, field names and class types? Enumerating all the possible field access paths ¯f as required in Definition 2.1, especially in the presence of cycles, may be exponential in terms of the number of edges traversed [28, 34], causing the pre-analysis to be too inefficient or even unscalable. We describe a fast and elegant solution below. 2.2.2 Merging Equivalent Automata We transform the problem of checking the type-consistency of two objects into one of testing the equivalence of two automata. Figure 4 relates the field points-to graph rooted at an object o, Go = (H, F, α, o, T , τ), to a 6-tuple sequential automaton Ao = (Q, Σ, δ, qo, Γ, γ) [1], which is more general than a traditional (5-tuple) automaton. In fact, a 5-tuple automaton can be turned into a 6-tuple automaton, if its accepting (acc) and non-accepting (non-acc) states are distinguished by γ : Q 7→ Γ, where Γ = {acc, non-acc}. Example 2.5. Continuing from Example 2.2 (Figure 2), the automaton Ao T 2 for Go T 2 = (H, F, α, oT 2 , T , τ) is obtained according to Figure 4. Similarly, Ao T 1 is constructed. The behavior of Ao, which can be an NFA (consisting of multiple edges with the same label leaving a state), is: βAo : Σ∗ → P(Γ) If Ao finally reaches the states, s1, s2, · · · , sn, after having read an input w in Σ ∗ , then βAo (w) = ∪ n i=1γ[si ]. Let o T 1 and o T 2 be two objects with the same type T. Let their automata Ao T 1 and Ao T 2 be built as shown in Figure 4. o T 1 and o T 2 are type-consistent if, for every input w in Σ ∗ , (1) βAoT 1 (w) = βAoT 2 (w) (Condition 1 of Definition 2.1) and (2) |βAoT 1 (w)| = 1 (Condition 2 of Definition 2.1). Therefore, we have reduced the problem of checking the type-consistency of o T 1 and o T 2 to one of testing the equivalence of their corresponding automata Ao T 1 and Ao T 2 , which is solvable by the Hopcroft-Karp algorithm [18] with minor modifications. The worst-case time complexity is O(|Σ| × |Qlarger|), which is almost linear in terms of |Qlarger|, where Qlarger is the set of states of the larger automaton [18]. Example 2.6. Continuing from Example 2.5, we see easily that o T 1 and o T 2 are type-consistent (Figure 2) since their corresponding automata Ao T 1 and Ao T 2 are equivalent. 3. MAHJONG We first give an overview of MAHJONG that consists of four components (Section 3.1). We then describe each component in detail (Sections 3.2 – 3.5). Finally, we discuss MAHJONGbased points-to analysis (Section 3.6). 3.1 Overview As shown in Figure 5, MAHJONG takes the field points-to graph (FPG) computed by a pre-analysis (Section 2.2.1) as input and builds a heap abstraction (Definition 2.2) to be used by a subsequent points-to analysis. The pre-analysis is fast but imprecise, by using Andersen’s algorithm [4] with the allocation-site abstraction, context-insensitively. The subsequent points-to analysis will be more precise, usually performed context-sensitively, especially for object-oriented programs, based on the MAHJONG heap abstraction. MAHJONG iteratively picks a pair of objects o T i and o T j with the same type T and merges them if they are typeconsistent, until no such pair can be found. Given o T i and o T j , their corresponding NFAs, NFAo T i and NFAo T j , are first built by using the NFA Builder. Then the two NFAs are converted into their equivalent DFAs, DFAo T i and DFAo T j , by using the DFA Converter. Next, the Automata Equivalence Checker determines whether DFAo T i and DFAo T j are equivalent or not. Finally, the Heap Modeler outputs a new heap abstraction. The detailed algorithms are given in Section 4. 3.2 The NFA Builder The NFA builder takes an object o, with the field points-to graph Go rooted at o, and constructs a 6-tuple NFA Ao = 281
MAHJONG 年里年看里里里害里量年里里量里量年年里里年里里年年。里年金年里年。年里年看里年重里里害里年 NFAO Pre-Analysis NFA DFA Field Points-To Builder Converter Graph (FPG) Vo,o in FPG NFAO DFA DFAO Heap Abstraction Heap DFAo DFA Automata Points-to Analysis Modeler Equivalence Checker Figure 5.Overview of MAHJONG. (Q,∑，d,go,T,y）according to the mapping,as shown in tion sites.Different context-sensitivity are distinguished by Figure 4.In fact,A can be immediately read off from Go. different kinds of context elements used,as discussed below We obtain M-A from A by first replacing A's allocation- 3.3 The DFA Converter site abstraction with the MAHJONG heap abstraction.We The DFA Converter converts an NFA to an equivalent DFA then need to make minor modifications to A to enable M- based on the subset construction algorithm [2]with minor A to handle merged objects effectively. modifications.The resulting DFA is still a 6-tuple sequential Regardless of whether A is call-site-,object-or type- automaton except that it is deterministic. sensitive.M-A will always model a merged object o context- insensitively.There would be otherwise of little benefit in 3.4 The Automata Equivalence Checker modeling o context-sensitively,since the objects accessed by The Automata Equivalence Checker tests the equivalence o.f1.f2.....fn for any f1.f2.....fn under different con- of two DFAs by applying a classic Hopcroft-Karp algo- texts are expected to have the same type,in practice.Below rithm [18]with minor modifications in almost linear time. we discuss how the calling contexts for methods are modi- fied,if needed,when they are related to merged objects. 3.5 The Heap Modeler After all type-consistent objects have been found,the type- Call-Site-Sensitivity A k-call-site-sensitive points-to anal- consistency equivalence relation given in Definition 2.1 ysis,i.e.,a k-CFA [37]separates information on local vari- becomes fully constructed.By Definition 2.2,the new heap ables per call-stack (i.e.,sequence of k call-sites)of method abstraction found is simply given by H/=.For every invocations that lead to the current method.By convention, equivalent class[o]∈H/三，a representative objectof a sequence of k-1 call-sites is used as a calling context for an allocation site [20.39.481. is arbitrarily picked to substitute for the other objects in the class.Essentially,the allocation sites for all objects in [o If A is k-call-site-sensitive [37],then M-A behaves iden- are merged and represented by the allocation site of of only. tically asA in handling methods.For the reason mentioned To enable a points-to analysis to use our new heap ab- above,M-A models the merged objects context-insensitively straction,we only need to change its rule for handling allo- but everything else context-sensitively as in A. cation sites.Given i:x new TO in a Java program,where Object-Sensitivity k-object-sensitivity is similar to k-call- of is a representative for [o].is made to point to of site-sensitivity except that allocation sites rather than call sites are used as context elements [29].Let o;be an ab- 3.6 MAHJONG-based Points-To Analysis stract object identified by its allocation site i.In k-object- Let A be an allocation-site-based points-to analysis,which is sensitivity,the object oi at allocation site i is modeled either call-site-sensitive [15,22,36,42,51],object-sensitive context-sensitively by a calling context [o,...,](of [29,40,48]or type-sensitive [39].We first discuss how to length k-1),where ij is the allocation site for the re- obtain M-A,a MAHJONG-based points-to analysis,from A ceiver object oi,of the method that contains ij-1(with (Section 3.6.1).We then discuss briefly the soundness and io =i).If x points to an object oi modeled under a con- precision of M-.A relative to A for type-dependent clients. text [o...,],then the k-object-sensitive calling con- text used for analyzing a callee of a method call x.foo()is 3.6.1 Obtaining M-A from A 0ik-11…,0i,0 In a context-sensitive points-to analysis,local variables are If A is a k-object-sensitive points-to analysis,M-A analyzed context-sensitively by distinguishing the calling models merged objects context-insensitively,i.e.,object- contexts for a method.Heap objects are modeled context- insensitively but everything else objective-sensitively as in sensitively by distinguishing the calling contexts for alloca- A.As a result,calling contexts that contain merged objects 282
Pre-Analysis Automata Equivalence Checker NFA Builder DFA Converter Heap Modeler ∀ , in FPG Field Points-To Graph (FPG) Heap Abstraction MAHJONG NFAOi NFAOj DFAOi DFAOj DFAO ≡ ? i DFAOj oi T oj T T T T T T T Points-to Analysis Figure 5. Overview of MAHJONG. (Q, Σ, δ, q0, Γ, γ) according to the mapping, as shown in Figure 4. In fact, Ao can be immediately read off from Go. 3.3 The DFA Converter The DFA Converter converts an NFA to an equivalent DFA based on the subset construction algorithm [2] with minor modifications. The resulting DFA is still a 6-tuple sequential automaton except that it is deterministic. 3.4 The Automata Equivalence Checker The Automata Equivalence Checker tests the equivalence of two DFAs by applying a classic Hopcroft-Karp algorithm [18] with minor modifications in almost linear time. 3.5 The Heap Modeler After all type-consistent objects have been found, the typeconsistency equivalence relation ≡ given in Definition 2.1 becomes fully constructed. By Definition 2.2, the new heap abstraction found is simply given by H / ≡. For every equivalent class [o T i ] ∈ H / ≡, a representative object o T j is arbitrarily picked to substitute for the other objects in the class. Essentially, the allocation sites for all objects in [o T i ] are merged and represented by the allocation site of o T j only. To enable a points-to analysis to use our new heap abstraction, we only need to change its rule for handling allocation sites. Given i : x = new T() in a Java program, where o T j is a representative for [o T i ], x is made to point to o T j . 3.6 MAHJONG-based Points-To Analysis Let A be an allocation-site-based points-to analysis, which is either call-site-sensitive [15, 22, 36, 42, 51], object-sensitive [29, 40, 48] or type-sensitive [39]. We first discuss how to obtain M-A, a MAHJONG-based points-to analysis, from A (Section 3.6.1). We then discuss briefly the soundness and precision of M-A relative to A for type-dependent clients. 3.6.1 Obtaining M-A from A In a context-sensitive points-to analysis, local variables are analyzed context-sensitively by distinguishing the calling contexts for a method. Heap objects are modeled contextsensitively by distinguishing the calling contexts for allocation sites. Different context-sensitivity are distinguished by different kinds of context elements used, as discussed below. We obtain M-A from A by first replacing A’s allocationsite abstraction with the MAHJONG heap abstraction. We then need to make minor modifications to A to enable MA to handle merged objects effectively. Regardless of whether A is call-site-, object- or typesensitive, M-A will always model a merged object o contextinsensitively. There would be otherwise of little benefit in modeling o context-sensitively, since the objects accessed by o.f1.f2. · · · .fn for any f1.f2. · · · .fn under different contexts are expected to have the same type, in practice. Below we discuss how the calling contexts for methods are modi- fied, if needed, when they are related to merged objects. Call-Site-Sensitivity A k-call-site-sensitive points-to analysis, i.e., a k-CFA [37] separates information on local variables per call-stack (i.e., sequence of k call-sites) of method invocations that lead to the current method. By convention, a sequence of k − 1 call-sites is used as a calling context for an allocation site [20, 39, 48]. If A is k-call-site-sensitive [37], then M-A behaves identically as A in handling methods. For the reason mentioned above, M-A models the merged objects context-insensitively but everything else context-sensitively as in A. Object-Sensitivity k-object-sensitivity is similar to k-callsite-sensitivity except that allocation sites rather than call sites are used as context elements [29]. Let oi be an abstract object identified by its allocation site i. In k-objectsensitivity, the object oi at allocation site i is modeled context-sensitively by a calling context [oik−1 , . . . , oi1 ] (of length k − 1), where ij is the allocation site for the receiver object oij of the method that contains ij−1 (with i0 = i). If x points to an object oi modeled under a context [oik−1 , . . . , oi1 ], then the k-object-sensitive calling context used for analyzing a callee of a method call x.foo() is [oik−1 , . . . , oi1 , oi ]. If A is a k-object-sensitive points-to analysis, M-A models merged objects context-insensitively, i.e., objectinsensitively but everything else objective-sensitively as in A. As a result, calling contexts that contain merged objects 282