oritizing correct and developer-readable (simple)transformers enumerated (over vEV(op)\{stale}).Then,the descendants to make the search procedure practical(Sections V-B to V-D).of p can be defined as A.Synthesis Framework DG(p)={pe}U {pstmt stmt ES). Given a set of gadgets G,our object transformer synthesis Though conceptually simple,it is a challenge to scale the algorithm listed in Algorithm 1 is essentially a straightforward search.The key treatments we made to boost the search include syntax-directed search.It maintains a work list O consisting of decomposing an object transformer into independent field candidate synthesized programs.A program p EQ is an object transformers(Section V-B),pruning likely irrelevant gadgets transformation DSL program(syntax defined in Figure 4)with (Section V-C),and boosting the search by measuring the zero or more insertion marksD in which more statements can “naturalness'”ofp(Section V-D). be filled7.Starting from the initial program that consists of a single insertion mark in O (Line 2),the algorithm iteratively B.Object Transformer as Independent Field Transformers pops the program p of the minimum cost in Q for a step of An object transformer is responsible for transforming all expansion(Lines 3-4).If p contains no insertion mark,we find fields in an object,and an object transformer for large classes a potentially useful transformer for further validation (Lines may be lengthy and difficult to synthesize.Fortunately,the 5-6).Otherwise,there must be an insertion mark in p and program is frozen at update-time and each field's value should the algorithm expands the first insertion mark to obtain more be computed by a pure function over the update-time heap candidate programs (Line 7). snapshot. The expansion step defines DG(p),the descendant programs Therefore,the transformation for fields in an object can be of p over a set of gadgets G.Let op be the first occurrence independently conducted and the object transformation problem of insertion mark in p.A step of expansion either closes (i.e., is essentially equivalent to the field transformation ones.In removes)the insertion mark op to obtain practice,a developer or upgrade maintainer simply specifies which fields may require a non-default transformer,and the Pe=pop→， synthesis algorithm will produce a series of candidate field or prepends it with a statement stmt to obtain transformers for further validation (e.g.,independently tested) This is a standard treatment of existing techniques [15,27,28]. Pstmt =plop stmt ] C.Pruning Irrelevant Gadgets In the latter case,let V(op)={stale,v1,v2,...}be all There can be millions of gadgets for a large program variables within the lexical scope of the insertion mark op resulting in a huge Ec(op).Fortunately,we observed that in p.For a gadget gG of n placeholders,the set of its all most of the gadgets are irrelevant to the field to be transformed possible applications at the insertion mark is defined by in terms of the upgrade.Particularly,class B is relevant to A Eg(op）={g(u,2,,vn)|∈V(on)for1≤i≤n}. if either:B is a (sub)class of A,B contains a field of type A,or a method in B refers to A (e.g.in the parameter list All syntactically valid expressions at o are thus or a local variable,etc.).To synthesize a field transformer for field f in class A (e.g.,A=SocketProcessor and f ka in Figure 1).we restrict the concerned gadget set G to be: EG(Op)=V(op 1)all gadgets in A, 2)all gadgets in any class relevant to A,and To prepend a statement stmt at o,it must be either of the 3)all gadgets in any class relevant to f.class. following four patterns according to the syntax in Figure 4: Finally,almost all classes are relevant to primitive types (e.g., 1)(variable assignment)v=e; int,bool,etc.)and java.lang.String.We do not apply the 2)(field transformation)obj.f =e; third rule in synthesizing field transformer for these types,as 3)(if-branch)if (c){s*else s* otherwise,the search would be intractable. 4)(while-loop)while (c){s* D.Boosting the Search Also recall that we limit the form of a condition c to be either A naive implementation of Algorithm 1 will be overwhelmed of fe,!e,e ==null,e !null).Therefore,stmt must by the huge search space.For example,Eg(op)grows consist of exactly one expression.Enumerating the expressions exponentially over increased V and In our search eE Ec(op)and filling e into the above code patterns yields implementation,we only fill a placeholder i with a type- S,the set of all possible statements to prepend to op.For compatible variable in the scope that will not trivially throw an assignment v e.the left-hand side variable v is also an exception (e.g.,invoking a null reference's method).This 7Given a program and an insertion mark in it,one can prepend a statement treatment yields a manageable E(p)in practice. before the insertion mark to obtain a new program.is equivalent to s*in The key to the success of our search algorithm is a cost the syntax. function cost to prioritize:(1)simple programs with few basicoritizing correct and developer-readable (simple) transformers to make the search procedure practical (Sections V-B to V-D). A. Synthesis Framework Given a set of gadgets G, our object transformer synthesis algorithm listed in Algorithm 1 is essentially a straightforward syntax-directed search. It maintains a work list Q consisting of candidate synthesized programs. A program p ∈ Q is an object transformation DSL program (syntax defined in Figure 4) with zero or more insertion marks |. in which more statements can be filled7 . Starting from the initial program that consists of a single insertion mark |. in Q (Line 2), the algorithm iteratively pops the program p of the minimum cost in Q for a step of expansion (Lines 3–4). If p contains no insertion mark, we find a potentially useful transformer for further validation (Lines 5–6). Otherwise, there must be an insertion mark |. in p and the algorithm expands the first insertion mark to obtain more candidate programs (Line 7). The expansion step defines DG(p), the descendant programs of p over a set of gadgets G. Let σp be the first occurrence of insertion mark in p. A step of expansion either closes (i.e., removes) the insertion mark σp to obtain p = p[σp 7→ ], or prepends it with a statement stmt to obtain pstmt = p[σp 7→ stmt |.]. In the latter case, let V (σp) = {stale, v1, v2, . . .} be all variables within the lexical scope of the insertion mark σp in p. For a gadget g ∈ G of n placeholders, the set of its all possible applications at the insertion mark is defined by Eg(σp) = {g(v1, v2, . . . , vn) | vi ∈ V (σp) for 1 ≤ i ≤ n}. All syntactically valid expressions at σp are thus EG(σp) = V (σp) ∪   [ g∈G Eg(σp)   . To prepend a statement stmt at σp, it must be either of the following four patterns according to the syntax in Figure 4: 1) (variable assignment) v = e; 2) (field transformation) obj.f = e; 3) (if-branch) if (c) { s ∗ } else { s ∗ } 4) (while-loop) while (c) { s ∗ } Also recall that we limit the form of a condition c to be either of {e, !e, e == null, e != null}. Therefore, stmt must consist of exactly one expression. Enumerating the expressions e ∈ EG(σp) and filling e into the above code patterns yields S, the set of all possible statements to prepend to σp. For an assignment v = e, the left-hand side variable v is also 7Given a program and an insertion mark in it, one can prepend a statement before the insertion mark to obtain a new program. |. is equivalent to s ∗ in the syntax. enumerated (over v ∈ V (σp)\{stale}). Then, the descendants of p can be defined as DG(p) = {p} ∪ {pstmt | stmt ∈ S}. Though conceptually simple, it is a challenge to scale the search. The key treatments we made to boost the search include decomposing an object transformer into independent field transformers (Section V-B), pruning likely irrelevant gadgets (Section V-C), and boosting the search by measuring the “naturalness” of p (Section V-D). B. Object Transformer as Independent Field Transformers An object transformer is responsible for transforming all fields in an object, and an object transformer for large classes may be lengthy and difficult to synthesize. Fortunately, the program is frozen at update-time and each field’s value should be computed by a pure function over the update-time heap snapshot. Therefore, the transformation for fields in an object can be independently conducted and the object transformation problem is essentially equivalent to the field transformation ones. In practice, a developer or upgrade maintainer simply specifies which fields may require a non-default transformer, and the synthesis algorithm will produce a series of candidate field transformers for further validation (e.g., independently tested). This is a standard treatment of existing techniques [15, 27, 28]. C. Pruning Irrelevant Gadgets There can be millions of gadgets for a large program, resulting in a huge |EG(σp)|. Fortunately, we observed that most of the gadgets are irrelevant to the field to be transformed in terms of the upgrade. Particularly, class B is relevant to A if either: B is a (sub)class of A, B contains a field of type A, or a method in B refers to A (e.g. in the parameter list or a local variable, etc.). To synthesize a field transformer for field f in class A (e.g., A = SocketProcessor and f = ka in Figure 1), we restrict the concerned gadget set G to be: 1) all gadgets in A, 2) all gadgets in any class relevant to A, and 3) all gadgets in any class relevant to f.class. Finally, almost all classes are relevant to primitive types (e.g., int, bool, etc.) and java.lang.String. We do not apply the third rule in synthesizing field transformer for these types, as otherwise, the search would be intractable. D. Boosting the Search A naive implementation of Algorithm 1 will be overwhelmed by the huge search space. For example, |Eg(σp)| grows exponentially over increased |V | and |~|. In our search implementation, we only fill a placeholder i with a type￾compatible variable in the scope that will not trivially throw an exception (e.g., invoking a null reference’s method). This treatment yields a manageable |Eg(σp)| in practice. The key to the success of our search algorithm is a cost function cost to prioritize: (1) simple programs with few basic