141:4 Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis Direct Flow 1 class Person 15} O ② String name;String id; 16 /Usage Code (19)name1 name2 (24) void setName(String nm){ 17 void main(){ 4 this.name nm: 18 Person p1 new Person(); (3) updateID(): 19 String name1 new String("A"): this.name (4) 6 20 p1.setName(name1): 7 void updateID(){ 21 String id1 p1.getID(): newName (8) 8 String newName this.name: 22 9 this.id newName: 23 Person p2 new Person(); this.id (9) 101 24 String name2 new String("B"): 11 String getID(){ 25 p2.setName(name2): id (12) 12 String id this.id: 26 String id2 p2.getID(): 13 return id: 27 (21)1d1 1d2(26) 14 ①② ①② Fig.3.Example of direct flow.(The line number for each variable/field reference on the right-hand side is shown in parentheses.) load/store operations,method calls,or returns)to the return value of an Our method,M2,of the same class C,then we say the program has direct flow from Mi to M2.(The example in Figure 1 is a simple instance of this pattern.) Definition 2.4(Wrapped flow).If,in some execution of the program,an object O is passed as a parameter to an IN method M of class C and then flows to a store operation that wraps O into an object W,where W subsequently flows to the result of an Our method,M2,of the same class C,then we say the program has wrapped flow from M to M2.More generally,the wrapped flow pattern also covers value flow through multiple object wrapping steps,for example when W is itself wrapped into another object W',which flows to the return value of M2. Definition 2.5(Unwrapped flow).If,in some execution of the program,an object O is passed as a parameter to an IN method M of class C and then flows to a load operation that unwraps an object U from O,where U subsequently flows to the return value of an Our method,M2,of the same class C,then we say the program has unwrapped flow from M to M2.As in the previous definition, unwrapped flow also covers value flow through multiple object unwrapping steps. 2.1 Pattern 1:Direct Flow The setter and getter example shown in Figure 3 demonstrates how direct flow is an indication of precision loss for a context-insensitive analysis.The Person class provides methods setName and getID to modify a person's name and retrieve his or her ID.Whenever a person's name is modified, the ID is updated accordingly (line 5). After executing this code,id1 in line 21(resp.id2 in line 26)points to object 1in line 19(resp.2 in line 24)only.However,if the three methods of Person are analyzed using a context-insensitive pointer analysis,then id1 and id2 will both imprecisely point to objects 1 and 2.Let us examine how this imprecision is connected to the direct flow pattern. The right-hand side of Figure 3 illustrates how two objects1and 2,respectively pointed to by namel and name2,first flow from their creation sites in lines 19 and 24 to the parameter nm of the IN method setName in line 3,and then to id in line 12 through a series of store and load operations (line 4-line 8-line 9line 12),and finally out of the Our method getID to id1 and id2 in lines 21 and 26.Hence,by Definition 2.3,the red arrows in Figure 3 form a direct flow. Notice that with a context-insensitive analysis,objects 1and 2are merged in the same points-to set and further propagated according to this direct flow.In the analysis,the merged objects will Proc.ACM Program.Lang.,Vol.2,No.OOPSLA,Article 141.Publication date:November 2018.141:4 Yue Li, Tian Tan, Anders Mùller, and Yannis Smaragdakis Direct Flow name1 1 2 1 2 class Person { 1 String name; String id; void setName(String nm) { this.name = nm; updateID(); } void updateID() { String newName = this.name; this.id = newName; } String getID() { String id = this.id; return id; } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 } // Usage Code void main() { Person p1 = new Person(); String name1 = new String("A"); p1.setName(name1); String id1 = p1.getID(); Person p2 = new Person(); String name2 = new String("B"); p2.setName(name2); String id2 = p2.getID(); } 15 16 17 18 19 20 21 22 23 24 25 26 27 name2 nm this.name newName this.id id id1 id2 2 (24) (3) (4) (8) (9) (12) (21) (26) (19) Fig. 3. Example of direct flow. (The line number for each variable/field reference on the right-hand side is shown in parentheses.) load/store operations, method calls, or returns) to the return value of an Out method, M2, of the same class C, then we say the program has direct flow from M1 to M2. (The example in Figure 1 is a simple instance of this pattern.) Definition 2.4 (Wrapped flow). If, in some execution of the program, an object O is passed as a parameter to an In method M1 of class C and then flows to a store operation that wraps O into an object W , where W subsequently flows to the result of an Out method, M2, of the same class C, then we say the program has wrapped flow from M1 to M2. More generally, the wrapped flow pattern also covers value flow through multiple object wrapping steps, for example when W is itself wrapped into another object W ′ , which flows to the return value of M2. Definition 2.5 (Unwrapped flow). If, in some execution of the program, an object O is passed as a parameter to an In method M1 of class C and then flows to a load operation that unwraps an object U from O, where U subsequently flows to the return value of an Out method, M2, of the same class C, then we say the program has unwrapped flow from M1 to M2. As in the previous definition, unwrapped flow also covers value flow through multiple object unwrapping steps. 2.1 Pattern 1: Direct Flow The setter and getter example shown in Figure 3 demonstrates how direct flow is an indication of precision loss for a context-insensitive analysis. The Person class provides methods setName and getID to modify a person’s name and retrieve his or her ID. Whenever a person’s name is modified, the ID is updated accordingly (line 5). After executing this code, id1 in line 21 (resp. id2 in line 26) points to object 1 in line 19 (resp. 2 in line 24) only. However, if the three methods of Person are analyzed using a context-insensitive pointer analysis, then id1 and id2 will both imprecisely point to objects 1 and 2 . Let us examine how this imprecision is connected to the direct flow pattern. The right-hand side of Figure 3 illustrates how two objects 1 and 2 , respectively pointed to by name1 and name2, first flow from their creation sites in lines 19 and 24 to the parameter nm of the In method setName in line 3, and then to id in line 12 through a series of store and load operations (line 4 → line 8 → line 9 → line 12), and finally out of the Out method getID to id1 and id2 in lines 21 and 26. Hence, by Definition 2.3, the red arrows in Figure 3 form a direct flow. Notice that with a context-insensitive analysis, objects 1 and 2 are merged in the same points-to set and further propagated according to this direct flow. In the analysis, the merged objects will Proc. ACM Program. Lang., Vol. 2, No. OOPSLA, Article 141. Publication date: November 2018