1:6 Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis Direct Wrapped Unwrapped Flow Flow Flow IN Method Objects Value flow via assignments S field load/store operations, OUT Method or method calls/returns Fig.2.Three general patterns of value flow that cause precision loss in context-insensitive analysis. the two objects are mixed together,so the analysis conservatively concludes that both x2 and y2 may point to both the A object and the B object. In contrast,a context-sensitive analysis would analyze m twice,corresponding to the two different call sites,and thereby conclude that x2 can only point to an A object and y2 can only point to a B object.The price of that extra precision is that the method needs to be analyzed multiple times, so context sensitivity should ideally only be applied when the precision gain outweighs the extra analysis time. To characterize the relevant value flows,we first introduce some terminology. Definition 3.1(IN and Our methods).Given a class C and a method M that is declared in C or inherited from C's super-classes,if M contains one or more parameters then M is an IN method of C,and if M's return type is non-void then M is an Our method of C.(In the example in Figure 1,m is both an IN and an Our method of the surrounding class.) Definition 3.2(Object wrapping and unwrapping).If an object O is stored in a field of an object W (or in an array entry of W,in case W is an array),then O is wrapped into W.Conversely,if an object O is loaded from a field of an object W(or from an array entry of W in case W is an array),then O is unwrapped from W.(The simple example in Figure 1 contains no wrapping or unwrapping.) With these definitions in place,we can describe the three precision-loss patterns as different kinds of value flows,depicted in Figure 2. Definition 3.3(Direct 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(via a series of assignments,field 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 M to M2.(The example in Figure 1 is a simple instance of this pattern.) Definition 3.4(Wrapped flow).If,in some execution of the program,an object O is passed as a parameter to an IN method Mi 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 Mi 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 3.5(Unwrapped flow).If,in some execution of the program,an object O is passed as a parameter to an IN method Mi 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 M to M2.As in the previous definition, unwrapped flow also covers value flow through multiple object unwrapping steps. ACM Trans.Program.Lang.Syst.,Vol.1,No.1,Article 1.Publication date:January 2020.1:6 Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis Direct Flow Wrapped Flow Unwrapped Flow IN Method OUT Method Value flow via assignments, field load/store operations, or method calls/returns Objects Fig. 2. Three general patterns of value flow that cause precision loss in context-insensitive analysis. the two objects are mixed together, so the analysis conservatively concludes that both x2 and y2 may point to both the A object and the B object. In contrast, a context-sensitive analysis would analyze m twice, corresponding to the two different call sites, and thereby conclude that x2 can only point to an A object and y2 can only point to a B object. The price of that extra precision is that the method needs to be analyzed multiple times, so context sensitivity should ideally only be applied when the precision gain outweighs the extra analysis time. To characterize the relevant value flows, we first introduce some terminology. Definition 3.1 (In and Out methods). Given a class 𝐶 and a method 𝑀 that is declared in 𝐶 or inherited from 𝐶’s super-classes, if 𝑀 contains one or more parameters then 𝑀 is an In method of 𝐶, and if 𝑀’s return type is non-void then 𝑀 is an Out method of 𝐶. (In the example in Figure 1, m is both an In and an Out method of the surrounding class.) Definition 3.2 (Object wrapping and unwrapping). If an object 𝑂 is stored in a field of an object 𝑊 (or in an array entry of𝑊 , in case𝑊 is an array), then 𝑂 is wrapped into 𝑊 . Conversely, if an object 𝑂 is loaded from a field of an object 𝑊 (or from an array entry of 𝑊 in case 𝑊 is an array), then 𝑂 is unwrapped from 𝑊 . (The simple example in Figure 1 contains no wrapping or unwrapping.) With these definitions in place, we can describe the three precision-loss patterns as different kinds of value flows, depicted in Figure 2. Definition 3.3 (Direct flow). If, in some execution of the program, an object 𝑂 is passed as a parameter to an In method 𝑀1 of class 𝐶, and then flows (via a series of assignments, field load/store operations, method calls, or returns) to the return value of an Out method, 𝑀2, of the same class 𝐶, then we say the program has direct flow from 𝑀1 to 𝑀2. (The example in Figure 1 is a simple instance of this pattern.) Definition 3.4 (Wrapped flow). If, in some execution of the program, an object 𝑂 is passed as a parameter to an In method 𝑀1 of class 𝐶 and then flows to a store operation that wraps 𝑂 into an object 𝑊 , where 𝑊 subsequently flows to the result of an Out method, 𝑀2, of the same class 𝐶, then we say the program has wrapped flow from 𝑀1 to 𝑀2. More generally, the wrapped flow pattern also covers value flow through multiple object wrapping steps, for example when 𝑊 is itself wrapped into another object 𝑊 ′ , which flows to the return value of 𝑀2. Definition 3.5 (Unwrapped flow). If, in some execution of the program, an object 𝑂 is passed as a parameter to an In method 𝑀1 of class 𝐶 and then flows to a load operation that unwraps an object 𝑈 from 𝑂, where 𝑈 subsequently flows to the return value of an Out method, 𝑀2, of the same class 𝐶, then we say the program has unwrapped flow from 𝑀1 to 𝑀2. As in the previous definition, unwrapped flow also covers value flow through multiple object unwrapping steps. ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020