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
as context elements are modified accordingly.For an object hurts the precision,making M-A nearly as precise asA for o that is used in a calling context under A,o is replaced by type-dependent clients,in practice.The key insight behind a representative of [o]H/=(Section 3.5)under M-A. object-sensitivity [29]is to distinguish the side-effects of dif- In other words,if o is merged with some type-consistent ferent receiver objects of an instance method foo()by ana- objects,then its representative is used,instead. lyzing it under multiple calling contexts,one per receiver ob- Type-Sensitivity To trade precision for efficiency,k-type- ject.By merging a set of type-consistent receiver objects for sensitivity is derived from k-object-sensitivity by replacing foo(),we end up achieving a significant performance bene- fit at little precision loss by analyzing foo()under the same every object in a calling context with the class type that contains the corresponding allocation site for the object [39]. context by M-A rather than separately but unnecessarily by A for these receiver objects.For type-dependent clients,this If A is a k-type-sensitive analysis obtained from its corre- sponding k-object-sensitive analysis A',then M-A is simply represents a generalization of object-sensitivity. obtained from M-A'in the same type-sensitive manner. If A is type-sensitive,then M-A is nearly as precise as (sometimes slightly better or worse than)A for type- 3.6.2 Soundness and Precision of M-A over A dependent clients,in practice.Consider an equivalence class The soundness of M-A is easy to establish.If A is sound, [o]={o1,.,on}∈H/≡(Definition2.2)formed then M-A is sound as the MAHJONG heap abstraction is by the MAHJONG heap abstraction.In A,every o;that is coarser than the allocation-site abstraction used in A. used as a context element in a calling context is replaced We discuss some insights below on why merging type- by the class type that contains the allocation site for o:.In consistent objects enables M-.A to maximally preserve the M-A,01,...,on are merged and replaced by the class type precision ofA for type-dependent clients.This is true for all that contains the allocation site for a representative in [o]. Thus,the MAHJONG heap abstraction can be coarser than three types of context-sensitivity as validated later. the allocation-site abstraction for some methods and finer We first describe a rarely occurring subtle case,the null- for some others in partitioning their calling contexts,which field problem,illustrated in Figure 6,due to the imprecision depends on the representatives chosen. of the pre-analysis,causing precision loss for all the three types of MAHJONG-based context-sensitivity. Example 3.1.Suppose of.f and of.f both point to of Class T Class U during the pre-analysis (Figure 6(a))but o and null,re- alloc site1:O∥oo alloc site3yOg∥og‘o spectively,in A (Figure 6(b)).In M-A.of and of are type- alloc site 2:O;//oo Alloc Sites I and 2 Abstracted,Resp.as: consistent and thus merged into of(represented by either of type: Tand T M-ktype:U andT if and are merged as or )M-A is less precise.asofwhich points to nu in A.now points to an object of type X(Figure 6(c)). ▣ Figure 7.Precision of M-ktype over ktype. o. Let us see how the choice of representative for an equiv- alence class affects the precision of M-ktype. >null Example 3.2.In Figure 7,ktype(k-type-sensitive analysis) (a)Pre-Analysis (b)A (c)M-A will represent the allocation sites 1 and 2 by T.Thus,the Figure 6.Illustrating the null-field problem. two allocation sites that are distinguished by kobj(k-object- sensitive analysis)are merged.According to MAHJONG,of and o are type-consistent,falling into the same equivalence If A is call-site-sensitive,M-A is as precise as A for a class.If o happens to be selected as a representative,then type-dependent client if the null-field problem never occurs M-ktype will be able to distinguish the allocation sites 1 in a program analyzed by A.Recall that the pre-analysis and 2 by U and T,respectively.However,if of is selected is no more precise than A.By Definition 2.1,the objects as the representative(not shown in Figure 7),then M-ktype reached from o along the same sequence of field accesses will merge the allocation sites 1,2 and 3 by using T as the must have exactly the same type when o is modeled both context,and become less precise than ktype. context-sensitively underA and context-insensitively under M-A,resulting in the same precision in both cases.In gen- However,the choice of representative for an equivalence eral,M-A is no more precise than A due to the null-field class[o={o1,.,on}∈H/≡does not affect the problem but very close to A as the null-fields are rare. soundness of M-ktype.Regardless of what object is selected, IfA is object-sensitive,then M-A is no more precise than replacing o:in a context used in the corresponding kobj A for type-dependent clients,as some heap objects that are by the containing type of a representative in o]in M-ktype used in distinguishing different contexts in A are merged by always yields a context abstraction that is either identical or MAHJONG if they are type-consistent.However,this hardly coarser,by the definition of type-sensitivity [39]. 283
as context elements are modified accordingly. For an object o that is used in a calling context under A, o is replaced by a representative of [o] ∈ H / ≡ (Section 3.5) under M-A. In other words, if o is merged with some type-consistent objects, then its representative is used, instead. Type-Sensitivity To trade precision for efficiency, k-typesensitivity is derived from k-object-sensitivity by replacing every object in a calling context with the class type that contains the corresponding allocation site for the object [39]. If A is a k-type-sensitive analysis obtained from its corresponding k-object-sensitive analysis A′ , then M-A is simply obtained from M-A′ in the same type-sensitive manner. 3.6.2 Soundness and Precision of M-A over A The soundness of M-A is easy to establish. If A is sound, then M-A is sound as the MAHJONG heap abstraction is coarser than the allocation-site abstraction used in A. We discuss some insights below on why merging typeconsistent objects enables M-A to maximally preserve the precision of A for type-dependent clients. This is true for all three types of context-sensitivity as validated later. We first describe a rarely occurring subtle case, the null- field problem, illustrated in Figure 6, due to the imprecision of the pre-analysis, causing precision loss for all the three types of MAHJONG-based context-sensitivity. Example 3.1. Suppose o T i .f and o T j .f both point to o X 1 during the pre-analysis (Figure 6(a)) but o X 1 and null, respectively, in A (Figure 6(b)). In M-A, o T i and o T j are typeconsistent and thus merged into o T k (represented by either o T i or o T j ), M-A is less precise, as o T j .f, which points to null in A, now points to an object of type X (Figure 6(c)). (a) Pre-Analysis (b) (c) null f O T i O X 1 f O T j O X 1 O T k M- f O T i O X 1 f O T j f O X 1 Figure 6. Illustrating the null-field problem. If A is call-site-sensitive, M-A is as precise as A for a type-dependent client if the null-field problem never occurs in a program analyzed by A. Recall that the pre-analysis is no more precise than A. By Definition 2.1, the objects reached from o along the same sequence of field accesses must have exactly the same type when o is modeled both context-sensitively under A and context-insensitively under M-A, resulting in the same precision in both cases. In general, M-A is no more precise than A due to the null-field problem but very close to A as the null-fields are rare. If A is object-sensitive, then M-A is no more precise than A for type-dependent clients, as some heap objects that are used in distinguishing different contexts in A are merged by MAHJONG if they are type-consistent. However, this hardly hurts the precision, making M-A nearly as precise as A for type-dependent clients, in practice. The key insight behind object-sensitivity [29] is to distinguish the side-effects of different receiver objects of an instance method foo() by analyzing it under multiple calling contexts, one per receiver object. By merging a set of type-consistent receiver objects for foo(), we end up achieving a significant performance bene- fit at little precision loss by analyzing foo() under the same context by M-A rather than separately but unnecessarily by A for these receiver objects. For type-dependent clients, this represents a generalization of object-sensitivity. If A is type-sensitive, then M-A is nearly as precise as (sometimes slightly better or worse than) A for typedependent clients, in practice. Consider an equivalence class [o] = {o1, . . . , on} ∈ H / ≡ (Definition 2.2) formed by the MAHJONG heap abstraction. In A, every oi that is used as a context element in a calling context is replaced by the class type that contains the allocation site for oi . In M-A, o1, . . . , on are merged and replaced by the class type that contains the allocation site for a representative in [o]. Thus, the MAHJONG heap abstraction can be coarser than the allocation-site abstraction for some methods and finer for some others in partitioning their calling contexts, which depends on the representatives chosen. Class T alloc site 1: O1 A // O1 A f O4 X O2 A // O2 A f O5 Y Class U O3 A // O3 A f O6 X ktype: alloc site 2: alloc site 3: M-ktype: Alloc Sites 1 and 2 Abstracted, Resp., as: T and T U and T if O1 A and are merged as O3 A O3 A Figure 7. Precision of M-ktype over ktype. Let us see how the choice of representative for an equivalence class affects the precision of M-ktype. Example 3.2. In Figure 7, ktype (k-type-sensitive analysis) will represent the allocation sites 1 and 2 by T. Thus, the two allocation sites that are distinguished by kobj (k-objectsensitive analysis) are merged. According to MAHJONG, o A 1 and o A 3 are type-consistent, falling into the same equivalence class. If o A 3 happens to be selected as a representative, then M-ktype will be able to distinguish the allocation sites 1 and 2 by U and T, respectively. However, if o A 1 is selected as the representative (not shown in Figure 7), then M-ktype will merge the allocation sites 1, 2 and 3 by using T as the context, and become less precise than ktype. However, the choice of representative for an equivalence class [o] = {o1, . . . , on} ∈ H / ≡ does not affect the soundness of M-ktype. Regardless of what object is selected, replacing oi in a context used in the corresponding kobj by the containing type of a representative in [o] in M-ktype always yields a context abstraction that is either identical or coarser, by the definition of type-sensitivity [39]. 283
4.Algorithms sulting set is any member of SUS.S.FIND(z)returns the We present the algorithms used in MAHJONG.In Sec- representative of the disjoint set in S that contains z. tion 4.1,we give some domains used and then the main MAHJONG first initializes W by adding to it a singleton algorithm.In Sections 4.2-4.5,we describe the algorithms set for each object (lines 1-3).Then it iterates over every of its four components introduced in Sections 3.2-3.5. pair of objects,oi and o;in H,that are not yet merged,and merges the pair if both are type-consistent(lines 4-13). 4.1 MAHJONG According to line 5,oi and o;are mergeable only if both For a program,we use the three domains:(1)H is the set of have the same type.The function TYPEOF:H->Treturns all abstract heap objects (i.e.,allocation sites),(2)F is the the type of a given object and a special type for onm. set of all field names,and (3)T is the set of all types.Note To check the type consistency of oi and oj by Defini- that we have used H earlier in Definition 2.2. tion 2.1 efficiently,we handle its two conditions separately, Now,we can formally define the input and output of with Condition 2 in lines 6-7 and Condition 1 in lines 8 MAHJONG.MAHJONG takes a field points-to graph,FPG= 12.In lines 6-7.the function SINGLETYPE-CHECK (N.E),which is a directed weighted graph,as input.A node HxFPG{TRUE,FALSE}is applied to see if Condition 2 oiE N=H represents a heap object in the program.An holds for both o;and oj.If so,MAHJONG then proceeds to edge(oi,f,oj)∈ECN×F×N indicates thato-f points build the NFAs for the two objects(Section 4.2),convert the to oj.We assume that the FPG contains a dummy node onu NFAs to their equivalent DFAs(Section 4.3),and finally,test to represent null.If oi.f=null,then (oi,f,onu)EE.We their equivalence (Section 4.4).If the two DFAs are equiv- also assume(onu,f,onu1)EEfor every field f EF. alent,then MAHJONG calls W.UNION(o:,oj)to merge oi The output of MAHJONG is a new heap abstraction,rep- and oj at line 13.Finally,in lines 14-16,MAHJONG builds resented by a merged object map,MOM CHH,which a new heap abstraction as desired (Section 4.5). relates an object in an equivalence class in H/=to its rep- 4.2 The NFA Builder resentative object (as described in Section 3.5). Given an object o,Algorithm 2 (NFA-BUILDER)builds an NFA,A。=(Q,∑，d,qo,T,y),according to the mapping Algorithm 1:MAHJONG from the field points-to graph rooted at o to Ao in Figure 4. Input FPG (Field Points-to Graph) Output:MOM (Merged Object Map) Algorithm 2:NFA-BUILDER 1 Let W be a new set 2 foreach o∈Hdo Input 0 (Input object) (Field Points-to Graph) 3 Add fo to W FPG=(N,E) Output: NFA =(Q,S,6,90,I,Y) 4 foreach oi,oj E Hs.t.W.FIND(oi)W.FIND(o;)do 1q0=0 5 if TYPEOF(oi)==TYPEOF(oj)and 2 Let O be a set of objects reachable from o in FPG SINGLETYPE-CHECK(oi,FPG)and 3 Let X and I be two new sets SINGLETYPE-CHECK(oj,FPG)then 4 Let y and 6 be two new maps NFAO:NFA-BUILDER(0,FPG) s foreach o:∈Qdo 9 NFAoj NFA-BUILDER(0j,FPG) ∑=∑FIELDSOF(O) o DFAO=DFA-CONVERTER(NFAo) I=T U{TYPEOF(oi)} DFAO;=DFA-CONVERTER(NFAo) 8 Yo:]TYPEOF(O:) if EOUIV-CHECKER(DFAoi.DFAo;)then 9foreach(oi,∫，o)∈Edo 0 LW.UNION(0:,0;) 10 ifo:∈Q then 11 L Add oj to 5[oi,f] 14 Let MOM be a new map 12 return NFA=(Q,∑，d,go,T,y） 15 foreach o∈Hdo 16 L MOM[o]W.FIND(o) 17 return MOM NFA-BUILDER constructs all the six components for Ao. Its initial state go is simply o(line 1).Q is the set of objects reachable from o in FPG(line 2).The objects in Q are Algorithm I gives the main algorithm.To facilitate merg- iterated over to build >(set of input symbols).I (set of ing type-consistent objects,we make use of the concept of output symbols),and y (output map)at lines 5-8.The disjoint sets [11.In a set S of disjoint sets,each disjoint set function FIELDSOF:H->P(F)returns the fields of a is identified by a representative,which is some member of given object.Finally,the relevant edges in FPG are traversed the disjoint set.We make use of two classic operations over to build the state transition map 6(lines 9-11). disjoint sets,UNION and FIND.S.UNION(,y)unites the disjoint sets in S that contain x and y,say S and Sy,into 4.3 The DFA Converter a new disjoint set that is the union of the two,adds it to S, Algorithm 3 (DFA-CONVERTER)converts an NFA to its and destroys S and Su in S.The representative of the re equivalent DFA by using the subset construction [2] 284
4. Algorithms We present the algorithms used in MAHJONG. In Section 4.1, we give some domains used and then the main algorithm. In Sections 4.2 – 4.5, we describe the algorithms of its four components introduced in Sections 3.2 – 3.5. 4.1 MAHJONG For a program, we use the three domains: (1) H is the set of all abstract heap objects (i.e., allocation sites), (2) F is the set of all field names, and (3) T is the set of all types. Note that we have used H earlier in Definition 2.2. Now, we can formally define the input and output of MAHJONG. MAHJONG takes a field points-to graph, FPG = (N, E), which is a directed weighted graph, as input. A node oi ∈ N = H represents a heap object in the program. An edge (oi , f, oj ) ∈ E ⊆ N × F × N indicates that oi .f points to oj . We assume that the FPG contains a dummy node onull to represent null. If oi .f = null, then (oi , f, onull) ∈ E. We also assume (onull, f, onull) ∈ E for every field f ∈ F. The output of MAHJONG is a new heap abstraction, represented by a merged object map, MOM ⊆ H → H, which relates an object in an equivalence class in H / ≡ to its representative object (as described in Section 3.5). Algorithm 1: MAHJONG Input : FPG (Field Points-to Graph) Output: MOM (Merged Object Map) 1 Let W be a new set 2 foreach o ∈ H do 3 Add {o} to W 4 foreach oi, oj ∈ H s.t. W.FIND(oi) 6= W.FIND(oj ) do 5 if TYPEOF(oi) == TYPEOF(oj ) and 6 SINGLETYPE-CHECK(oi, FPG) and 7 SINGLETYPE-CHECK(oj , FPG) then 8 NFAoi = NFA-BUILDER(oi, FPG) 9 NFAoj = NFA-BUILDER(oj , FPG) 10 DFAoi = DFA-CONVERTER(NFAoi) 11 DFAoj = DFA-CONVERTER(NFAoj ) 12 if EQUIV-CHECKER(DFAoi, DFAoj ) then 13 W.UNION(oi, oj ) 14 Let MOM be a new map 15 foreach o ∈ H do 16 MOM[o] = W.FIND(o) 17 return MOM Algorithm 1 gives the main algorithm. To facilitate merging type-consistent objects, we make use of the concept of disjoint sets [11]. In a set S of disjoint sets, each disjoint set is identified by a representative, which is some member of the disjoint set. We make use of two classic operations over disjoint sets, UNION and FIND. S.UNION(x, y) unites the disjoint sets in S that contain x and y, say Sx and Sy, into a new disjoint set that is the union of the two, adds it to S, and destroys Sx and Sy in S. The representative of the resulting set is any member of Sx ∪ Sy. S.FIND(x) returns the representative of the disjoint set in S that contains x. MAHJONG first initializes W by adding to it a singleton set for each object (lines 1 – 3). Then it iterates over every pair of objects, oi and oj in H, that are not yet merged, and merges the pair if both are type-consistent (lines 4 – 13). According to line 5, oi and oj are mergeable only if both have the same type. The function TYPEOF : H → T returns the type of a given object and a special type for onull. To check the type consistency of oi and oj by Definition 2.1 efficiently, we handle its two conditions separately, with Condition 2 in lines 6 – 7 and Condition 1 in lines 8 – 12. In lines 6 – 7, the function SINGLETYPE-CHECK : H×FPG → {TRUE, FALSE} is applied to see if Condition 2 holds for both oi and oj . If so, MAHJONG then proceeds to build the NFAs for the two objects (Section 4.2), convert the NFAs to their equivalent DFAs (Section 4.3), and finally, test their equivalence (Section 4.4). If the two DFAs are equivalent, then MAHJONG calls W.UNION(oi , oj ) to merge oi and oj at line 13. Finally, in lines 14 – 16, MAHJONG builds a new heap abstraction as desired (Section 4.5). 4.2 The NFA Builder Given an object o, Algorithm 2 (NFA-BUILDER) builds an NFA, Ao =(Q, Σ, δ, q0, Γ, γ), according to the mapping from the field points-to graph rooted at o to Ao in Figure 4. Algorithm 2: NFA-BUILDER Input : o (Input object) FPG = (N, E) (Field Points-to Graph) Output: NFA = (Q, Σ, δ, q0, Γ, γ) 1 q0 = o 2 Let Q be a set of objects reachable from o in FPG 3 Let Σ and Γ be two new sets 4 Let γ and δ be two new maps 5 foreach oi ∈ Q do 6 Σ = Σ ∪ FIELDSOF(oi) 7 Γ = Γ ∪ { TYPEOF(oi) } 8 γ[oi] = TYPEOF(oi) 9 foreach (oi, f, oj ) ∈ E do 10 if oi ∈ Q then 11 Add oj to δ[oi, f] 12 return NFA = (Q, Σ, δ, q0, Γ, γ) NFA-BUILDER constructs all the six components for Ao. Its initial state q0 is simply o (line 1). Q is the set of objects reachable from o in FPG (line 2). The objects in Q are iterated over to build Σ (set of input symbols), Γ (set of output symbols), and γ (output map) at lines 5 – 8. The function FIELDSOF : H → P(F) returns the fields of a given object. Finally, the relevant edges in FPG are traversed to build the state transition map δ (lines 9 – 11). 4.3 The DFA Converter Algorithm 3 (DFA-CONVERTER) converts an NFA to its equivalent DFA by using the subset construction [2]. 284
There are three minor differences.First,we do not need to Algorithm 4:EQUIV-CHECKER handle (non-existent)e-transitions.Second.we can find the next states of a DFA state g more efficiently.In the general Input DFA1=(Q1,1,d1,q,T1,1) DFA2=(Q2,∑2,02,92，T2,2) case,all input symbols must be examined.In our case (lines Output:TRUE or FALSE (Are DFA and DFA2 equivalent?) 7-9),we only need to iterate over the fields (input symbols) 1Q=Q1UQ2 of an arbitrarily picked object(an NFA state)in g to find its 2∑=∑1U∑2 next states.Due to SINGLETYPE-CHECK in lines 6-7 of J6[4,f月ifq∈Q1 Algorithm 1,the objects grouped in a DFA state g must have 3la,月={24，月ifg∈Q2 the same type.Finally,we need to compute I(set of output 4T=TiUr2 symbols)and (output map)at lines 14-16, s Yg= ∫h[gifq∈Q1 U2[gifq∈Q2 Algorithm 3:DFA-CONVERTER 6DFA=(Q,2,6,91,T,Y) nput:NFA=(Q,∑，6，o,T,Y) 7 Let V be a new set Output:DFA =(',,,o.) 8 foreach g∈Qdo 190={90} Add {9}tov 2∑=∑ 10 V.UNION(g1,g2) 3 Let O'and I'be two new sets 11 Push(,g2)to a new stack,STACK 4 Let and be two new maps 12 while STACK is not empty do s Add go as an unmarked state to Q' 13 Pop (p1,p2)from STACK 6 while there is an unmarked state qQ'do 14 foreach f∈∑do Mark g 15 r1=V.FIND(6[p1,f]),r2 =V.FIND([p2,f]) 7 8 Pick any oi from q 16 ifri≠r2then foreach f E FIELDSOF(o;)do 17 V.UNION(r1.r2) Push(r1.r2)to STACK 10 q={6[o,f|o∈9} ifg走Q'then 12 Add 'as an unmarked state to TRUE 19 return ifs∈V:p,q∈s:p=y[g间 FALSE otherwise 6'[g,f月=q l4 foreach q∈Q'do 15 Y[g]={TYPEOF(O:)1o:Eg} 16 LT=TUYlg] to work with mainstream allocation-site-based points-to 17 return DFA (Q','6',go,I',) analysis frameworks such as CHORD [10],WALA [50], SOoT [49]and Doop [14].To demonstrate its effective- ness,we have integrated MAHJONG with DOOP [9,14]. 4.4 The Automata Equivalence Checker a state-of-the-art whole-program points-to analysis frame- Algorithm 4 (EQUIV-CHECKER)tests the equivalence of work for Java.MAHJONG is released as an open-source tool two 6-tuple DFAs,by applying a Hopcroft-Karp algorithm at http://www.cse.unsw.edu.au/-corg/mahjong.Be- low we discuss three major optimizations. that was proposed for two 5-tuple DFAs [18]with minor modifications at line 19 on testing whether all states in s EV Disjoint-Set Forest In Algorithms 1 and 4,disjoint sets are have the same type.As discussed in Section 2.2.2,a 5-tuple used.For efficiency,we have implemented a set of disjoint DFA can be modeled as a special case of a 6-tuple DFA sets as a disjoint-set forest,by representing each disjoint set EQUIV-CHECKER iterates over all fields f >(line 14) as a tree with its root being its representative.Thus,UNION and queries the transition map 6 to obtain the next states(line amounts to linking the roots of different trees while FIND 15).By convention,if 6[q,f]is not defined,since the objects returns the root of a tree.To improve the efficiency further, in g do not have the field f,we assume that 6[q,f]=qerror. we have also implemented two heuristics,union by rank and In addition,gerror]returns a special type for qerror. path compression [11].As a result,the average execution 4.5 The Heap Modeler time of each UNION/FIND operation over a disjoint-set for- After Algorithm 1 has terminated,we have W=H/=in est can be reduced to nearly O(1)[11]. its line 16.Then MOM specifies the new heap abstraction Shared Sequential Automata In Algorithms 2 and 3,new given in Definition 2.2,as discussed in Section 3.5. automata are frequently created.However,different au- tomata can be partly identical,since their common parts 5.Implementation correspond to the same objects.Instead of always creating We have implemented MAHJONG as a standalone tool in a new automata,we allow different automata to share their total of only 1500 LOC in Java to build a new heap abstrac- common parts.This optimization reduces significantly both tion by merging equivalent automata.MAHJONG is designed the time and space costs of the overall algorithm. 285
There are three minor differences. First, we do not need to handle (non-existent) ǫ-transitions. Second, we can find the next states of a DFA state q more efficiently. In the general case, all input symbols must be examined. In our case (lines 7 – 9), we only need to iterate over the fields (input symbols) of an arbitrarily picked object (an NFA state) in q to find its next states. Due to SINGLETYPE-CHECK in lines 6 – 7 of Algorithm 1, the objects grouped in a DFA state q must have the same type. Finally, we need to compute Γ ′ (set of output symbols) and γ ′ (output map) at lines 14 – 16, Algorithm 3: DFA-CONVERTER Input : NFA = (Q, Σ, δ, q0, Γ, γ) Output: DFA = (Q ′ , Σ ′ , δ′ , q′ 0, Γ ′ , γ′ ) 1 q ′ 0 = {q0} 2 Σ ′ = Σ 3 Let Q ′ and Γ ′ be two new sets 4 Let δ ′ and γ ′ be two new maps 5 Add q ′ 0 as an unmarked state to Q ′ 6 while there is an unmarked state q ∈ Q ′ do 7 Mark q 8 Pick any oi from q 9 foreach f ∈ FIELDSOF(oi) do 10 q ′ = { δ[oj , f] | oj ∈ q } 11 if q ′ ∈/ Q ′ then 12 Add q ′ as an unmarked state to Q ′ 13 δ ′ [q, f] = q ′ 14 foreach q ∈ Q ′ do 15 γ ′ [q] = { TYPEOF(oi) | oi ∈ q } 16 Γ ′ = Γ′ ∪ γ ′ [q] 17 return DFA = (Q ′ , Σ ′ , δ′ , q′ 0, Γ ′ , γ′ ) 4.4 The Automata Equivalence Checker Algorithm 4 (EQUIV-CHECKER) tests the equivalence of two 6-tuple DFAs, by applying a Hopcroft-Karp algorithm that was proposed for two 5-tuple DFAs [18] with minor modifications at line 19 on testing whether all states in s ∈ V have the same type. As discussed in Section 2.2.2, a 5-tuple DFA can be modeled as a special case of a 6-tuple DFA. EQUIV-CHECKER iterates over all fields f ∈ Σ (line 14) and queries the transition map δ to obtain the next states (line 15). By convention, if δ[q, f] is not defined, since the objects in q do not have the field f, we assume that δ[q, f] = qerror. In addition, γ[qerror] returns a special type for qerror. 4.5 The Heap Modeler After Algorithm 1 has terminated, we have W = H / ≡ in its line 16. Then MOM specifies the new heap abstraction given in Definition 2.2, as discussed in Section 3.5. 5. Implementation We have implemented MAHJONG as a standalone tool in a total of only 1500 LOC in Java to build a new heap abstraction by merging equivalent automata. MAHJONG is designed Algorithm 4: EQUIV-CHECKER Input : DFA1 = (Q1, Σ1, δ1, q1, Γ1, γ1) DFA2 = (Q2, Σ2, δ2, q2, Γ2, γ2) Output: TRUE or FALSE (Are DFA1 and DFA2 equivalent?) 1 Q = Q1 ∪ Q2 2 Σ = Σ1 ∪ Σ2 3 δ[q, f] = δ1[q, f] if q ∈ Q1 δ2[q, f] if q ∈ Q2 4 Γ = Γ1 ∪ Γ2 5 γ[q] = γ1[q] if q ∈ Q1 γ2[q] if q ∈ Q2 6 DFA = (Q, Σ, δ, q1, Γ, γ) 7 Let V be a new set 8 foreach q ∈ Q do 9 Add {q} to V 10 V .UNION(q1, q2) 11 Push (q1, q2) to a new stack, STACK 12 while STACK is not empty do 13 Pop (p1, p2) from STACK 14 foreach f ∈ Σ do 15 r1 =V.FIND(δ[p1, f]), r2 =V.FIND(δ[p2, f]) 16 if r1 6= r2 then 17 V .UNION(r1, r2) 18 Push (r1, r2) to STACK 19 return TRUE if ∀s ∈ V : ∀p, q ∈ s : γ[p] = γ[q] FALSE otherwise to work with mainstream allocation-site-based points-to analysis frameworks such as CHORD [10], WALA [50], SOOT [49] and DOOP [14]. To demonstrate its effectiveness, we have integrated MAHJONG with DOOP [9, 14], a state-of-the-art whole-program points-to analysis framework for Java. MAHJONG is released as an open-source tool at http://www.cse.unsw.edu.au/~corg/mahjong. Below we discuss three major optimizations. Disjoint-Set Forest In Algorithms 1 and 4, disjoint sets are used. For efficiency, we have implemented a set of disjoint sets as a disjoint-set forest, by representing each disjoint set as a tree with its root being its representative. Thus, UNION amounts to linking the roots of different trees while FIND returns the root of a tree. To improve the efficiency further, we have also implemented two heuristics, union by rank and path compression [11]. As a result, the average execution time of each UNION/FIND operation over a disjoint-set forest can be reduced to nearly O(1) [11]. Shared Sequential Automata In Algorithms 2 and 3, new automata are frequently created. However, different automata can be partly identical, since their common parts correspond to the same objects. Instead of always creating new automata, we allow different automata to share their common parts. This optimization reduces significantly both the time and space costs of the overall algorithm. 285
Parallel Type-Consistency Checks A synchronization- ferent pair-wise type-consistency tests are performed in par free parallelization scheme is used.This is achieved by re- allel.as discussed in Section 5.with 8 threads on 4 cores. quiring different threads to merge objects of different types Table 2 presents the main results,which will be ana- (with every thread executing lines 6-13 of Algorithm 1).To lyzed when our research questions are discussed below.For avoid synchronizations,object merging takes place only at a program,we consider the abstract objects reachable from line 13 of Algorithm 1,and in addition,all shared automata main()in both the application and library code. are constructed beforehand and concurrently read only. 6.1 RO1:MAHJONG's Effectiveness as a Pre-Analysis 6. Evaluation 6.1.1 Efficiency We show that MAHJONG is effective in significantly scal- The overall pre-analysis phase is fast,as shown in Column 2 ing context-sensitive points-to analyses for large Java pro- of Table 2.For a program,its analysis time is broken down grams while achieving nearly the same precision for type- into three components,taken by ci (the context-insensitive dependent clients.We address two major research questions: points-to analysis),FPG (a module for building its FPG), RQ1.Is MAHJONG effective as a pre-analysis? MAHJONG (for creating a new heap abstraction).For all the 12 programs,the average analysis time for ci is 62.3 seconds. (a)Is MAHJONG lightweight for large programs? The runtime overheads for the other two are negligible. (b)Can MAHJONG avoid the allocation-site abstraction's The efficiency of MAHJONG cannot be over-emphasized, heap over-partitioning for type-dependent clients? as it could not otherwise be used as an enabling technol- RO2.Is MAHJONG-based points-to analysis effective? ogy for a subsequent points-to analysis.On average,a FPG consists of 10073 objects of 1559 types with 2411 fields. (a)Can MAHJONG accelerate different types of main- MAHJONG builds an NFA for each object in the FPG,with stream context-sensitive points-to analyses? its size measured in terms of its number of states.The av- (b)Can MAHJONG achieve comparable precision as the erage sizes of NFAs range from 356 in luindex to 3789 allocation-site abstraction for type-dependent clients? in eclipse,with an average of 992.For each program,the smallest NFA always has one state only.Across all the pro- Type-Dependent Clients We consider three representative grams,the sizes of their largest NFAs range from 1935 in type-dependent clients,call graph construction,devirtualiza- luindex to 10034 in eclipse.This costs MAHJONG only tion and may-fail casting,provided by DooP [14]. an average of 3.8 seconds for each program.Such good per- Context-Sensitive Points-to Analyses We consider five formance is due to both our design (by merging objects in context-sensitive points-to analyses also from Doop as terms of merging equivalent automata)and several effective baselines.These cover the three main types of mainstream optimizations performed (see Section 5). context-sensitivity:call-site-sensitivity [15,22,36,42,51]. object-sensitivity [29,40,48]and type-sensitivity [39]. 6.1.2 Heap Partitioning We also provide experimental evidence on why context- Figure 8 shows that MAHJONG can alleviate the heap over- insensitivity is inadequate for type-dependent clients. partitioning problem suffered by the allocation-site abstrac- tion effectively for type-dependent clients.The allocation- Benchmarks We consider 12 large Java programs in- site abstraction creates an average of 10073 objects per pro- cluding 3 popular applications findbugs,checkstyle gram,ranging from 6190 in luindex to 19529 in eclipse. and JPC and all standard DaCapo benchmarks [12]except In contrast,MAHJONG creates an average of 3826 objects iython and hsgldb as they are not scalable under 3 out per program,ranging from 2108 in luindex to 9414 in of the 5 baseline analyses with and without MAHJONG. eclipse.This represents an average reduction of 62%. These programs are all analyzed with a large Java library Let us examine checkstyle in detail.As shown in Fig- JDK1.6.0.45. ure 8,a total of 10888 objects are created by the allocation- As a static reflection analysis may affect the efficiency site abstraction but only 4028 objects by MAHJONG. and precision of points-to analysis [24,25,38],we adopt the Given the heap partitioned as H/=for checkstyle, same resolution results generated by a dynamic reflection Figure 9 relates the number of equivalence classes with analysis tool,TAMIFLEX [8],in both the five baselines and a particular equivalence class size.In the left-most point their corresponding MAHJONG-based points-to analyses. marked by (1,3769),for example,there are 3769 equiva- Computing Platform We have done our experiments on a lence classes containing one object each.Thus,neither ob- Xeon E5-1620 3.7GHz machine with 128GB of RAM.The ject is merged with any other objects. analysis time of a program is the average of 3 runs. Let us examine some equivalence classes,given in Ta- ble 1,with their ranks(measured in decreasing order of their Pre-Analysis For this,we use the fast context-insensitive sizes)shown as well.For StringBuilder(Row 1),all their points-to analysis,denoted ci,provided by Doop [14].Dif- objects are type-consistent(reaching only char[]objects 286
Parallel Type-Consistency Checks A synchronizationfree parallelization scheme is used. This is achieved by requiring different threads to merge objects of different types (with every thread executing lines 6 – 13 of Algorithm 1). To avoid synchronizations, object merging takes place only at line 13 of Algorithm 1, and in addition, all shared automata are constructed beforehand and concurrently read only. 6. Evaluation We show that MAHJONG is effective in significantly scaling context-sensitive points-to analyses for large Java programs while achieving nearly the same precision for typedependent clients. We address two major research questions: RQ1. Is MAHJONG effective as a pre-analysis? (a) Is MAHJONG lightweight for large programs? (b) Can MAHJONG avoid the allocation-site abstraction’s heap over-partitioning for type-dependent clients? RQ2. Is MAHJONG-based points-to analysis effective? (a) Can MAHJONG accelerate different types of mainstream context-sensitive points-to analyses? (b) Can MAHJONG achieve comparable precision as the allocation-site abstraction for type-dependent clients? Type-Dependent Clients We consider three representative type-dependent clients, call graph construction, devirtualization and may-fail casting, provided by DOOP [14]. Context-Sensitive Points-to Analyses We consider five context-sensitive points-to analyses also from DOOP as baselines. These cover the three main types of mainstream context-sensitivity: call-site-sensitivity [15, 22, 36, 42, 51], object-sensitivity [29, 40, 48] and type-sensitivity [39]. We also provide experimental evidence on why contextinsensitivity is inadequate for type-dependent clients. Benchmarks We consider 12 large Java programs including 3 popular applications findbugs, checkstyle and JPC and all standard DaCapo benchmarks [12] except jython and hsqldb as they are not scalable under 3 out of the 5 baseline analyses with and without MAHJONG. These programs are all analyzed with a large Java library JDK1.6.0 45. As a static reflection analysis may affect the efficiency and precision of points-to analysis [24, 25, 38], we adopt the same resolution results generated by a dynamic reflection analysis tool, TAMIFLEX [8], in both the five baselines and their corresponding MAHJONG-based points-to analyses. Computing Platform We have done our experiments on a Xeon E5-1620 3.7GHz machine with 128GB of RAM. The analysis time of a program is the average of 3 runs. Pre-Analysis For this, we use the fast context-insensitive points-to analysis, denoted ci, provided by DOOP [14]. Different pair-wise type-consistency tests are performed in parallel, as discussed in Section 5, with 8 threads on 4 cores. Table 2 presents the main results, which will be analyzed when our research questions are discussed below. For a program, we consider the abstract objects reachable from main() in both the application and library code. 6.1 RQ1: MAHJONG’s Effectiveness as a Pre-Analysis 6.1.1 Efficiency The overall pre-analysis phase is fast, as shown in Column 2 of Table 2. For a program, its analysis time is broken down into three components, taken by ci (the context-insensitive points-to analysis), FPG (a module for building its FPG), MAHJONG (for creating a new heap abstraction). For all the 12 programs, the average analysis time for ci is 62.3 seconds. The runtime overheads for the other two are negligible. The efficiency of MAHJONG cannot be over-emphasized, as it could not otherwise be used as an enabling technology for a subsequent points-to analysis. On average, a FPG consists of 10073 objects of 1559 types with 2411 fields. MAHJONG builds an NFA for each object in the FPG, with its size measured in terms of its number of states. The average sizes of NFAs range from 356 in luindex to 3789 in eclipse, with an average of 992. For each program, the smallest NFA always has one state only. Across all the programs, the sizes of their largest NFAs range from 1935 in luindex to 10034 in eclipse. This costs MAHJONG only an average of 3.8 seconds for each program. Such good performance is due to both our design (by merging objects in terms of merging equivalent automata) and several effective optimizations performed (see Section 5). 6.1.2 Heap Partitioning Figure 8 shows that MAHJONG can alleviate the heap overpartitioning problem suffered by the allocation-site abstraction effectively for type-dependent clients. The allocationsite abstraction creates an average of 10073 objects per program, ranging from 6190 in luindex to 19529 in eclipse. In contrast, MAHJONG creates an average of 3826 objects per program, ranging from 2108 in luindex to 9414 in eclipse. This represents an average reduction of 62%. Let us examine checkstyle in detail. As shown in Figure 8, a total of 10888 objects are created by the allocationsite abstraction but only 4028 objects by MAHJONG. Given the heap partitioned as H / ≡ for checkstyle, Figure 9 relates the number of equivalence classes with a particular equivalence class size. In the left-most point marked by (1, 3769), for example, there are 3769 equivalence classes containing one object each. Thus, neither object is merged with any other objects. Let us examine some equivalence classes, given in Table 1, with their ranks (measured in decreasing order of their sizes) shown as well. For StringBuilder (Row 1), all their objects are type-consistent (reaching only char[] objects 286
DetailAST(Row 3)and the other that contains one single Allocation-Site Abstraction ☑MAHJONG object with null fields(Row 6). 15000 1433 6.2 RO2:MAHJONG-based Points-to Analysis 1088811181 Mainstream points-to analyses for Java programs rely on 10000 414 810 the allocation-site-based abstraction to model the heap [20- 22,39.40,42,48].We demonstrate experimentally that MAHJONG is a better alternative for type-dependent clients. Concretely,we show that MAHJONG can achieve the fol- lowing goal in the real world.Suppose a software developer intends to apply a points-to analysis to a program under a given time budget.MAHJONG opens up new opportunities for the developer to either accelerate the chosen points-to Figure 8.Number of abstract objects created by the allocation-site abstraction and MAHJONG. analysis or replace it with a more precise but more expen- sive points-to analysis under still the same budget. 6.2.1 Baselines and Metrics 40961,3769 1024 We consider three types of context-sensitive points-to anal- 256 ,73,59) yses:call-site-sensitivity (cs),object-sensitivity (obj)and 6 type-sensitivity (type).Specifically,five points-to analyses T03， in DOop [14]are selected as baselines:2cs (2-call-site- 1 sensitive).2obj(2-object-sensitive).3obj(3-object-sensitive). .16 64 256 1024 Equivalence Class(Sizes) 2type (2-type-sensitive),and 3type (3-type-sensitive).In principle,2cs is not compatible with the others,3.A is no Figure 9.Object merging in checkstyle. less precise than 2.A,and kobj is no less precise than ktype. As for 1.A,it has been demonstrated that its precision is significantly less than that of kA,where k>1 [20,39]. Equiv.Class Total No. As a result,1.A is not used in the recent points-to analysis Rank Type Size Remarks of Objects literature [15,40,48]and is thus omitted in our baselines. java.lang.StringBuilder 1303 1303 chart Currently,each baseline k.A uses the allocation-site ab- 2 java.lang.Object] 690 1353 String straction.M-k.A denotes the version of k.A that uses the heap 12 antlr.ASTPair 108 109 DetailAST abstraction provided by MAHJONG.Thus,there are also five 55 java.lang.Object[] 2 1353 Integer MAHJONG-based points-to analyses altogether. 65 java.lang.Object 9 1353 OName The three type-dependent clients,call graph construction, 260 antlr.ASTPair 109 null devirtualization and may-fail casting,are widely used in the literature [20,22,39,40,48].We consider the following Table 1.Some equivalence classes in checkstyle. metrics:the number of call graph edges(#call graph edges), the number of casting operations that may fail (#may-fail casts),and the number of virtual call sites that cannot be along any field access path)and thus merged.This is the disambiguated into mono-calls (#poly call sites). largest equivalence class,corresponding to the right-most The time budget for each analysis is set to 5 hours. point marked by (1303,1)in Figure 9. For some other types like Object[](Rows 2,4 and 6.2.2 Efficiency and Precision 5),blindly merging all its objects would be imprecise Table 2 presents our results,showing clearly the effective- (Section 2.1).In contrast,MAHJONG merges only type- ness of MAHJONG in boosting existing points-to analyses consistent objects in order to maximally preserve preci- while maintaining their precision for type-dependent clients. sion for type-dependent clients.Thus,MAHJONG ends up For each program,five metrics are considered:"analysis with different equivalent classes containing objects of type time”,“speedup”,“#may-fail casts'”,“poly call sites'”and Object [for storing objects of different types,such as “#call graph edges'”.In all cases except“speedup”,smaller String(Row 2),Integer(Row 4),and QName(Row 5). is better.With"speedup"ignored,Table 2 contains 480 con- Finally,we show that MAHJONG can also distinguish crete results (=4 metrics x 12 programs x 10 points-to anal- null from other objects,because null may affect preci- yses (including the 5 baselines and 5 MAHJONG variants)). sion as explained in Section 3.6.MAHJONG partitions 109 In computing the speedup of M-kA over kA for a pro objects of ASTPair into two equivalence classes,with one gram,the pre-analysis time on the program is ignored.There containing 108 objects whose fields point to objects of type are three reasons:(1)the points-to information produced by 287
Figure 8. Number of abstract objects created by the allocation-site abstraction and MAHJONG. (1, 3769) (2, 72) (3, 59) (1303, 1) 1 4 16 64 256 1024 4096 1 4 16 64 256 1024 No. of Equivalence Classes Equivalence Class (Sizes) Figure 9. Object merging in checkstyle. Equiv. Class Total No. Rank Type Size of Objects Remarks 1 java.lang.StringBuilder 1303 1303 char[] 2 java.lang.Object[] 690 1353 String 12 antlr.ASTPair 108 109 DetailAST 55 java.lang.Object[] 12 1353 Integer 65 java.lang.Object[] 9 1353 QName 260 antlr.ASTPair 1 109 null Table 1. Some equivalence classes in checkstyle. along any field access path) and thus merged. This is the largest equivalence class, corresponding to the right-most point marked by (1303, 1) in Figure 9. For some other types like Object[] (Rows 2, 4 and 5), blindly merging all its objects would be imprecise (Section 2.1). In contrast, MAHJONG merges only typeconsistent objects in order to maximally preserve precision for type-dependent clients. Thus, MAHJONG ends up with different equivalent classes containing objects of type Object[] for storing objects of different types, such as String (Row 2), Integer (Row 4), and QName (Row 5). Finally, we show that MAHJONG can also distinguish null from other objects, because null may affect precision as explained in Section 3.6. MAHJONG partitions 109 objects of ASTPair into two equivalence classes, with one containing 108 objects whose fields point to objects of type DetailAST (Row 3) and the other that contains one single object with null fields (Row 6). 6.2 RQ2: MAHJONG-based Points-to Analysis Mainstream points-to analyses for Java programs rely on the allocation-site-based abstraction to model the heap [20– 22, 39, 40, 42, 48]. We demonstrate experimentally that MAHJONG is a better alternative for type-dependent clients. Concretely, we show that MAHJONG can achieve the following goal in the real world. Suppose a software developer intends to apply a points-to analysis to a program under a given time budget. MAHJONG opens up new opportunities for the developer to either accelerate the chosen points-to analysis or replace it with a more precise but more expensive points-to analysis under still the same budget. 6.2.1 Baselines and Metrics We consider three types of context-sensitive points-to analyses: call-site-sensitivity (cs), object-sensitivity (obj) and type-sensitivity (type). Specifically, five points-to analyses in DOOP [14] are selected as baselines: 2cs (2-call-sitesensitive), 2obj (2-object-sensitive), 3obj (3-object-sensitive), 2type (2-type-sensitive), and 3type (3-type-sensitive). In principle, 2cs is not compatible with the others, 3A is no less precise than 2A, and kobj is no less precise than ktype. As for 1A, it has been demonstrated that its precision is significantly less than that of kA, where k > 1 [20, 39]. As a result, 1A is not used in the recent points-to analysis literature [15, 40, 48] and is thus omitted in our baselines. Currently, each baseline kA uses the allocation-site abstraction. M-kA denotes the version of kA that uses the heap abstraction provided by MAHJONG. Thus, there are also five MAHJONG-based points-to analyses altogether. The three type-dependent clients, call graph construction, devirtualization and may-fail casting, are widely used in the literature [20, 22, 39, 40, 48]. We consider the following metrics: the number of call graph edges (#call graph edges), the number of casting operations that may fail (#may-fail casts), and the number of virtual call sites that cannot be disambiguated into mono-calls (#poly call sites). The time budget for each analysis is set to 5 hours. 6.2.2 Efficiency and Precision Table 2 presents our results, showing clearly the effectiveness of MAHJONG in boosting existing points-to analyses while maintaining their precision for type-dependent clients. For each program, five metrics are considered: “analysis time”, “speedup”, “#may-fail casts”, “#poly call sites” and “#call graph edges”. In all cases except “speedup”, smaller is better. With “speedup” ignored, Table 2 contains 480 concrete results (= 4 metrics × 12 programs × 10 points-to analyses (including the 5 baselines and 5 MAHJONG variants)). In computing the speedup of M-kA over kA for a program, the pre-analysis time on the program is ignored. There are three reasons: (1) the points-to information produced by 287
