1:14 Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis OFG PFG C1.elem item Itr.next itr C2.elem added for wrapped flow Fig.8.A partial PFG for class Collection in Figure 4(wrapped flow).C1,C2,and Itr denote the objects of classes Collection and Iterator allocated in lines 24,30,and 8 in Figure 4,respectively. node Na to Nol.Here we use the notation [o]to denote the variable that the abstract object o was originally assigned to when created:for example,if o is created at a statement v=new ..then [o]is the variable v.These added edges enable tracking wrapped flow as defined in Definition 3.4 and illustrated in Section 3.2.As an example,for the object wrapping this.next obj of line 15 in Figure 4,pt(this)contains an abstract object created at itr new Iterator(e)in line 8,so we add an edge from obj to itr. Note that if(in line 15)instead of adding an edge from Na to Nol we had added an edge from Na to No(mirroring the handling of unwrapped flows),we would miss some flows.Conceptually, according to Definition 3.4,modeling wrapped flow requires tracking the wrapper objects(from where they are created)rather than the variable b in the store operation b.f a(line 13).For example,in the case of Figure 4,consider the store operation this.next obj(line 15)where this(line 15)and itr (line 8)both point to the Iterator object created in line 8.If we added an edge from node Nobj to node Nthis(rather than Nobj to Nitr),the flow tracking from Nthis would not lead to the return statement(line 9)in the OuT method,because the wrapped flow flows out through node Nitr in this case.However,it is safe to add an edge to node Nitr instead(as we do in line 15 in Algorithm 1)since the wrapper object is originally assigned to itr,so that the flow of the wrapper object is taken into account as required by Definition 3.4. Through Algorithm 1,we can see that wrapped and unwrapped flows can be naturally expressed in the PFG by handling the store/load operations(lines 10-15)recursively during the graph traversal. In addition,the newly added edges for wrapped and unwrapped flows build new connections with existing OFG edges that model direct flows.As a result,the generated PFG also naturally expresses combinations of all three kinds of flows. Figure 8 shows a partial PFG example for class Collection from Figure 4.The existing OFG is constructed following the rules in Figure 7.In Figure 8,in the three object field nodes(C1.elem, C2.elem,and Itr.next),the abstract objects respectively denoted by C1,C2,and Itr represent the objects of classes Collection and Iterator.Node obj corresponds to Na in line 15 in Algorithm 1; the edge from node obj to node Itr.next corresponds to the store operation this.next obj in line 15 in Figure 4,and also the store operation b.f a in line 13 in Algorithm 1.According to line 15 in Algorithm 1,an edge that enables tracking the wrapped flow is added in Figure 8 from node obj to node itr,since [Itr]is the variable itr. Graph Reachability on Precision Flow Graphs.We now explain how ZIPPER extracts the precision- critical methods based on the PFGs.Generally,ZIPPER first computes all the nodes that are involved in the three kinds of flows by solving a simple graph reachability problem on the PFG,and then collects the methods that contain the nodes as the precision-critical methods. Given a class c,each flow in the precision-loss patterns corresponds to a path from a parameter node of an IN method of c to a return variable node of an Our method of c in PFGe.Therefore, obtaining the statements that are involved in the flows is equivalent to computing which nodes are reachable from a parameter of an IN method and can also reach a return variable of an OUT ACM Trans.Program.Lang.Syst.,Vol.1,No.1,Article 1.Publication date:January 2020.1:14 Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis item C1.elem C2.elem e obj Itr.next itr OFG PFG added for wrapped flow Fig. 8. A partial PFG for class Collection in Figure 4 (wrapped flow). C1, C2, and Itr denote the objects of classes Collection and Iterator allocated in lines 24, 30, and 8 in Figure 4, respectively. node 𝑁a to 𝑁[o] . Here we use the notation [o] to denote the variable that the abstract object o was originally assigned to when created: for example, if o is created at a statement v = new . . . then [o] is the variable v. These added edges enable tracking wrapped flow as defined in Definition 3.4 and illustrated in Section 3.2. As an example, for the object wrapping this.next = obj of line 15 in Figure 4, pt(this) contains an abstract object created at itr = new Iterator(e) in line 8, so we add an edge from obj to itr. Note that if (in line 15) instead of adding an edge from 𝑁a to 𝑁[o] we had added an edge from 𝑁a to 𝑁b (mirroring the handling of unwrapped flows), we would miss some flows. Conceptually, according to Definition 3.4, modeling wrapped flow requires tracking the wrapper objects (from where they are created) rather than the variable b in the store operation b.f = a (line 13). For example, in the case of Figure 4, consider the store operation this.next = obj (line 15) where this (line 15) and itr (line 8) both point to the Iterator object created in line 8. If we added an edge from node 𝑁obj to node 𝑁this (rather than 𝑁obj to 𝑁itr), the flow tracking from 𝑁this would not lead to the return statement (line 9) in the Out method, because the wrapped flow flows out through node 𝑁itr in this case. However, it is safe to add an edge to node 𝑁itr instead (as we do in line 15 in Algorithm 1) since the wrapper object is originally assigned to itr, so that the flow of the wrapper object is taken into account as required by Definition 3.4. Through Algorithm 1, we can see that wrapped and unwrapped flows can be naturally expressed in the PFG by handling the store/load operations (lines 10–15) recursively during the graph traversal. In addition, the newly added edges for wrapped and unwrapped flows build new connections with existing OFG edges that model direct flows. As a result, the generated PFG also naturally expresses combinations of all three kinds of flows. Figure 8 shows a partial PFG example for class Collection from Figure 4. The existing OFG is constructed following the rules in Figure 7. In Figure 8, in the three object field nodes (C1.elem, C2.elem, and Itr.next), the abstract objects respectively denoted by C1, C2, and Itr represent the objects of classes Collection and Iterator. Node obj corresponds to 𝑁a in line 15 in Algorithm 1; the edge from node obj to node Itr.next corresponds to the store operation this.next = obj in line 15 in Figure 4, and also the store operation b.f = a in line 13 in Algorithm 1. According to line 15 in Algorithm 1, an edge that enables tracking the wrapped flow is added in Figure 8 from node obj to node itr, since [Itr] is the variable itr. Graph Reachability on Precision Flow Graphs. We now explain how Zipper extracts the precision￾critical methods based on the PFGs. Generally, Zipper first computes all the nodes that are involved in the three kinds of flows by solving a simple graph reachability problem on the PFG, and then collects the methods that contain the nodes as the precision-critical methods. Given a class 𝑐, each flow in the precision-loss patterns corresponds to a path from a parameter node of an In method of 𝑐 to a return variable node of an Out method of 𝑐 in PFG𝑐 . Therefore, obtaining the statements that are involved in the flows is equivalent to computing which nodes are reachable from a parameter of an In method and can also reach a return variable of an Out ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020