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 282Pre-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 algo￾rithm [18] with minor modifications in almost linear time. 3.5 The Heap Modeler After all type-consistent objects have been found, the type￾consistency 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 ab￾straction, we only need to change its rule for handling allo￾cation 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 context￾sensitively by distinguishing the calling contexts for alloca￾tion 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 allocation￾site abstraction with the MAHJONG heap abstraction. We then need to make minor modifications to A to enable M￾A to handle merged objects effectively. Regardless of whether A is call-site-, object- or type￾sensitive, M-A will always model a merged object o context￾insensitively. 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 con￾texts 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 anal￾ysis, i.e., a k-CFA [37] separates information on local vari￾ables 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 iden￾tically 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-call￾site-sensitivity except that allocation sites rather than call sites are used as context elements [29]. Let oi be an ab￾stract object identified by its allocation site i. In k-object￾sensitivity, 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 re￾ceiver object oij of the method that contains ij−1 (with i0 = i). If x points to an object oi modeled under a con￾text [oik−1 , . . . , oi1 ], then the k-object-sensitive calling con￾text 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., object￾insensitively but everything else objective-sensitively as in A. As a result, calling contexts that contain merged objects 282