Precision-Guided Context Sensitivity for Pointer Analysis 141:9 Variable node o.f Object field node Program Object Flow Graph Local assignment b=a; a a b; ① a ① (a(p) Assignments in b c.m(a) c.f a; ② ② method calls/returns m(p){return r:} (C→mthi3 d c; ③ (r b) c.f d; ④ ④ Field load b=a.f; where o e pt(a) @.f -b e=d.f;⑤ Field store a.f =b; b 0.f assuming oe pt(c)and o E pt(d) where o e pt(a) Fig.7.Object flow graph construction,with an example. pointer analysis is performed,guided by ZIPPER's results,so that the pointer analysis applies context sensitivity to only the precision-critical methods reported by ZIPPER. 3.2 Object Flow Graphs The object flow graph(OFG)of a program,as in its original form by Tonella and Potrich [2005],is a directed graph that expresses how objects flow in the program.The nodes in the OFG represent program pointers,which can point to objects,and the edges represent basic object flow among the pointers.More precisely,the OFG contains a node for each variable in the program and for each field of each abstract object.Objects are abstracted in the same way as in the pre-analysis, as described in Section 3.1:we here assume allocation-site abstraction is being used,which is the most common choice,but the technique also works for other choices.An edge ab in the OFG means that the objects pointed by pointer a may flow to(and also be pointed to by)pointer b. Another way to view the OFG is that it is the subset constraint graph in an Andersen-style points-to analysis [Andersen 1994;Sridharan et al.2013]. Tonella and Potrich [2005]propose to build the OFG with more precision by cloning the variables of a method for each of its receiver objects(conceptually like object sensitivity [Milanova et al. 2002,2005]),so that the flow involved in different receiver objects of the same method can be distinguished.However,this is unnecessary for ZIPPER,since it builds the OFG based on the results of a context-insensitive analysis,and all flow queries are done at the class level instead of the object level,as explained in Section 2.Therefore,we perform no such cloning. Due to the close connection between OFGs and Andersen-style analysis,constructing the OFG is trivial,based on the points-to relation pt(v)provided by the context-insensitive pre-analysis. Figure 7 illustrates this construction.The left-hand side of Figure 7 lists(from left to right)the four basic object flows,the related Java statements that induce the flows,and the corresponding graph edges in the OFG. Consider the code fragment and its corresponding OFG on the right-hand side of Figure 7.There are five statements labeled 1-5,and each statement causes an edge(with the same label)to be added to the OFG.With the OFG,the object flow information can be directly obtained simply by checking graph reachability without the need to explicitly track alias information among variables or field accesses.For example,variable e is reachable from b in the OFG,which means that the objects pointed to by b may flow to (and also be pointed to by)e. As a result,direct flows can be expressed naturally by the paths in the OFG,however,that is not the case for wrapped and unwrapped flows.In the next section,we describe how to augment the OFG to express all three kinds of flows. Proc.ACM Program.Lang.,Vol.2,No.OOPSLA,Article 141.Publication date:November 2018.Precision-Guided Context Sensitivity for Pointer Analysis 141:9 Local assignment Assignments in method calls/returns Field load Field store b = a; b = c.m(a); m(p){ return r;} … b = a.f; a.f = b; p a b r a b b b v Variable node o.f Object field node Program Object Flow Graph a = b; c.f = a; d = c; c.f = d; e = d.f; a 1 2 3 4 5 b d e c 1 2 3 4 5 c mthis where o ∈ pt(a) o.f o.f o.f where o ∈ pt(a) assuming o ∈ pt(c) and o ∈ pt(d) Fig. 7. Object flow graph construction, with an example. pointer analysis is performed, guided by Zipper’s results, so that the pointer analysis applies context sensitivity to only the precision-critical methods reported by Zipper. 3.2 Object Flow Graphs The object flow graph (OFG) of a program, as in its original form by Tonella and Potrich [2005], is a directed graph that expresses how objects flow in the program. The nodes in the OFG represent program pointers, which can point to objects, and the edges represent basic object flow among the pointers. More precisely, the OFG contains a node for each variable in the program and for each field of each abstract object. Objects are abstracted in the same way as in the pre-analysis, as described in Section 3.1: we here assume allocation-site abstraction is being used, which is the most common choice, but the technique also works for other choices. An edge a→b in the OFG means that the objects pointed by pointer a may flow to (and also be pointed to by) pointer b. Another way to view the OFG is that it is the subset constraint graph in an Andersen-style points-to analysis [Andersen 1994; Sridharan et al. 2013]. Tonella and Potrich [2005] propose to build the OFG with more precision by cloning the variables of a method for each of its receiver objects (conceptually like object sensitivity [Milanova et al. 2002, 2005]), so that the flow involved in different receiver objects of the same method can be distinguished. However, this is unnecessary for Zipper, since it builds the OFG based on the results of a context-insensitive analysis, and all flow queries are done at the class level instead of the object level, as explained in Section 2. Therefore, we perform no such cloning. Due to the close connection between OFGs and Andersen-style analysis, constructing the OFG is trivial, based on the points-to relation pt(v) provided by the context-insensitive pre-analysis. Figure 7 illustrates this construction. The left-hand side of Figure 7 lists (from left to right) the four basic object flows, the related Java statements that induce the flows, and the corresponding graph edges in the OFG. Consider the code fragment and its corresponding OFG on the right-hand side of Figure 7. There are five statements labeled 1 ś 5 , and each statement causes an edge (with the same label) to be added to the OFG. With the OFG, the object flow information can be directly obtained simply by checking graph reachability without the need to explicitly track alias information among variables or field accesses. For example, variable e is reachable from b in the OFG, which means that the objects pointed to by b may flow to (and also be pointed to by) e. As a result, direct flows can be expressed naturally by the paths in the OFG, however, that is not the case for wrapped and unwrapped flows. In the next section, we describe how to augment the OFG to express all three kinds of flows. Proc. ACM Program. Lang., Vol. 2, No. OOPSLA, Article 141. Publication date: November 2018