计算机科学与技术（参考文献）Synthesizing Object State Transformers for Dynamic Software Updates

Synthesizing Object State Transformers for Dynamic Software Updates Zelin Zhao*,Yanyan Jiang*,Chang Xu*,Tianxiao Gut,Xiaoxing Ma* *State Key Laboratory for Novel Software Technology and Department of Computer Science and Technology,Nanjing University,China TAlibaba Group,Sunnyvale,CA,USA Abstract-There is an increasing demand for evolving software 1)Almost all (187,or 98.4%)class changes can be updated systems to deliver continuous services of no restart.Dynamic dynamically,indicating that DSU is broadly applicable. software update (DSU)aims to achieve this goal by patching the Even for a few cases (3,or 1.6%)that DSU is impossible system state on the fly but is currently hindered from practice due to non-trivial cross-version object state transformations.This over existing programs,proper refactoring could still make paper revisits this problem through an in-depth empirical study them updatable [4,29.30]. of over 190 class changes from Tomcat 8.The study produced an 2)Most(166,or 87.4%)updates involve trivial object trans- important finding that most non-trivial object state transformers formations over simple predefined rules.Existing DSU can be constructed by reassembling existing old/new version code snippets.This paper presents a domain-specific language systems [15,17,18]are already capable of automatically and an efficient algorithm for synthesizing non-trivial object updating these changes without developers'intervention. transformers over code reuse.We experimentally evaluated our 3)The rest,not many but a non-negligible portion of class tool implementation PASTA with real-world software systems, changes (21,or 11.1%)require non-trivial object transfor- reporting PASTA's effectiveness in succeeding in 7.5x non-trivial mations.Software developers without a DSU background object transformation tasks compared with the best existing DSU would have substantial difficulties in specifying them,as techniques. Index Terms-Software maintenance and evolution,dynamic the required transformers have to carefully manipulate software update,object transformation,program synthesis. two versions of program states simultaneously. The empirical study results suggest that the key obstacle I.INTRODUCTION that hinders the continuous and automatic deployment of DSU in practice is probably how to obtain non-trivial object Dynamic software update (DSU,updating software at transformers.Unfortunately,this circumstance has not been runtime without restarting)[1]is a trending feature in modern seriously recognized by existing research.In fact,our later software systems.DSU keeps systems up-to-date with security experiments show that state-of-the-art techniques,like TOS [27] patches,bug fixes,and feature upgrades without hurting the and AOTES [28],could only succeed in 0 and 2 out of 25 non- systems'availability.DSU has become increasingly practical and compelling [1-8]:Linux Kernel [9-12]and Microsoft trivial object transformation tasks.Their apparent high success rates in past experiments might be due to mixing non-trivial Windows [13]are already dynamically updatable to some extent;Java Virtual Machine (JVM)has been modified to transformers with many trivial ones. In this paper,we leverage another key empirical finding that partially support application updates [14-18];live-upgradable object transformers can be constructed by reassembling existing components are also emerging in databases [19-21],servers [22- old/new version code to establish an algorithm for synthesizing 24],and even mission-critical systems [25]. object transformers in the DSU of Java applications.The Despite that code can be hot upgraded in emerging algorithm exhaustively and heuristically enumerates all possible systems [24,26],automatically updating runtime states for combinations of extracted code snippets,producing both test- seamless system evolution remains a major research chal- passing and developer-readable object transformers.A key lenge [15,27,28].Software updates may include a field of a advantage over existing techniques [27,28]is that an appli- class being added,removed,or semantically changed in a new cation developer can easily verify synthesized transformers' version.In DSU,such field values (if not removed)should be correctness because application code is their major constructs. (re)computed to match the new version code's semantics.This We implemented our algorithm as the PASTA (PATCH is known as the object transformation problem,whose solution STATES)tool for DSU of Java programs.The evaluation typically relies on a key mini-program (a.k.a.a transformer) results over a set of non-trivial class changes (including for computing these field values at update time. those in the empirical study and more)were encouraging: To understand the challenges in object transformation,this PASTA synthesized 7.5x correct non-trivial object transformers paper empirically studied 100 uniform-randomly sampled (60.0%)compared to the best existing techniques TOS [27] commits (consisting of 190 class changes)from Apache and AOTES [28](0.0%and 8.0%,respectively). Tomcat 8 [23],one of the most popular Web backend systems. In summary,this paper's major contributions are recognizing Our major findings include: the non-trivial object transformer synthesis as a critical problem

Synthesizing Object State Transformers for Dynamic Software Updates Zelin Zhao∗ , Yanyan Jiang∗ , Chang Xu∗ , Tianxiao Gu† , Xiaoxing Ma∗ ∗State Key Laboratory for Novel Software Technology and Department of Computer Science and Technology, Nanjing University, China †Alibaba Group, Sunnyvale, CA, USA Abstract—There is an increasing demand for evolving software systems to deliver continuous services of no restart. Dynamic software update (DSU) aims to achieve this goal by patching the system state on the fly but is currently hindered from practice due to non-trivial cross-version object state transformations. This paper revisits this problem through an in-depth empirical study of over 190 class changes from Tomcat 8. The study produced an important finding that most non-trivial object state transformers can be constructed by reassembling existing old/new version code snippets. This paper presents a domain-specific language and an efficient algorithm for synthesizing non-trivial object transformers over code reuse. We experimentally evaluated our tool implementation PASTA with real-world software systems, reporting PASTA’s effectiveness in succeeding in 7.5× non-trivial object transformation tasks compared with the best existing DSU techniques. Index Terms—Software maintenance and evolution, dynamic software update, object transformation, program synthesis. I. INTRODUCTION Dynamic software update (DSU, updating software at runtime without restarting) [1] is a trending feature in modern software systems. DSU keeps systems up-to-date with security patches, bug fixes, and feature upgrades without hurting the systems’ availability. DSU has become increasingly practical and compelling [1–8]: Linux Kernel [9–12] and Microsoft Windows [13] are already dynamically updatable to some extent; Java Virtual Machine (JVM) has been modified to partially support application updates [14–18]; live-upgradable components are also emerging in databases [19–21], servers [22– 24], and even mission-critical systems [25]. Despite that code can be hot upgraded in emerging systems [24, 26], automatically updating runtime states for seamless system evolution remains a major research chal￾lenge [15, 27, 28]. Software updates may include a field of a class being added, removed, or semantically changed in a new version. In DSU, such field values (if not removed) should be (re)computed to match the new version code’s semantics. This is known as the object transformation problem, whose solution typically relies on a key mini-program (a.k.a. a transformer) for computing these field values at update time. To understand the challenges in object transformation, this paper empirically studied 100 uniform-randomly sampled commits (consisting of 190 class changes) from Apache Tomcat 8 [23], one of the most popular Web backend systems. Our major findings include: 1) Almost all (187, or 98.4%) class changes can be updated dynamically, indicating that DSU is broadly applicable. Even for a few cases (3, or 1.6%) that DSU is impossible over existing programs, proper refactoring could still make them updatable [4, 29, 30]. 2) Most (166, or 87.4%) updates involve trivial object trans￾formations over simple predefined rules. Existing DSU systems [15, 17, 18] are already capable of automatically updating these changes without developers’ intervention. 3) The rest, not many but a non-negligible portion of class changes (21, or 11.1%) require non-trivial object transfor￾mations. Software developers without a DSU background would have substantial difficulties in specifying them, as the required transformers have to carefully manipulate two versions of program states simultaneously. The empirical study results suggest that the key obstacle that hinders the continuous and automatic deployment of DSU in practice is probably how to obtain non-trivial object transformers. Unfortunately, this circumstance has not been seriously recognized by existing research. In fact, our later experiments show that state-of-the-art techniques, like TOS [27] and AOTES [28], could only succeed in 0 and 2 out of 25 non￾trivial object transformation tasks. Their apparent high success rates in past experiments might be due to mixing non-trivial transformers with many trivial ones. In this paper, we leverage another key empirical finding that object transformers can be constructed by reassembling existing old/new version code to establish an algorithm for synthesizing object transformers in the DSU of Java applications. The algorithm exhaustively and heuristically enumerates all possible combinations of extracted code snippets, producing both test￾passing and developer-readable object transformers. A key advantage over existing techniques [27, 28] is that an appli￾cation developer can easily verify synthesized transformers’ correctness because application code is their major constructs. We implemented our algorithm as the PASTA (PATCH STATES) tool for DSU of Java programs. The evaluation results over a set of non-trivial class changes (including those in the empirical study and more) were encouraging: PASTA synthesized 7.5× correct non-trivial object transformers (60.0%) compared to the best existing techniques TOS [27] and AOTES [28] (0.0% and 8.0%, respectively). In summary, this paper’s major contributions are recognizing the non-trivial object transformer synthesis as a critical problem

in DSU and providing it with an effective approach.The rest of 1class SocketProcessor 2-private NioChannel socket null; the paper is organized as follows.Section II gives the necessary 3+private KeyAttachment ka null; background knowledge of DSU with a motivating example. 4 private SocketStatus status null; Section IlI presents a comprehensive study on DSU of 190 s public void run(){ 6+ NioChannel socket ka.getSocket(); class changes in Tomcat 8.Our DSL and synthesis algorithm 7 SelectionKey key socket.getIOChannel().keyFor( are elaborated on in Sections IV and V,respectively.The socket.getPoller().getSelector()); evaluation of PASTA against real-world updates is described 9- KeyAttachment ka null; 18- in Section VI,followed by threats to validity discussions in if (key !null) 11 ka =(KeyAttachment)key.attachment() Section VⅡ，related work in Section VⅢ，and conclusion in 12 Section IX. 13] 14 II.BACKGROUND AND MOTIVATION 1sclass DSUHelper 16 static void transform(SocketProcessor*obj,SocketProcessor stale){ A.DSU Systems and Object Transformation 17 /trivial default transformation for status obj.status stale.status; This paper focuses on the DSU of Java programs',which 18 19 /non-trivial transformation for ka consists of the following four steps: 28 obj.ka null; 1)Pause the program under update at a safe point [10,31], NioChannel socket stale.socket; if (socket !null){ e.g.,when all updated code is popped off the stack [15,17]. 23 SelectionKey key socket.getIoChannel().keyFor( 2)Upgrade the changed code [32,33]via dynamic link- 24 socket.getPoller().getSelector()); ing [34],live patching [10],or hotswap [26]. 25 if (key !null) 6 obj.ka (KeyAttachment)key.attachment(); 3)Transform stale (old-version)objects in the heap to their 27 new state [27,281. 28 4)Resume the updated program's execution.The new version 29] is now ready to serve. Fig.1:A class change in Tomcat-8(commit #f4451c)whose Object transformation(the third step)is this paper's primary object transformation is non-trivial.DSUHelper is our manually focus.When a program is paused at an update-safe point provided object transformer.At update time,the DSU system with code being upgraded,the heap may contain stale objects for each(stale)object sp (of type SocketProcessor)creates whose values are inconsistent with the new-version code.A its corresponding uninitialized new-version object sp*(of type DSU system must for each such object invoke its transformer SocketProcessor",the same class after update)and invokes to migrate to its corresponding new-version. the object transformer DSUHelper.transform(sp*,sp). B.Motivating Example Figure I lists a class change to SocketProcessor,which the latter is typically lacking for most application developers. requires a non-trivial transformation.This class change replaces Sometimes,a DSU system may automatically synthesize a the socket field by ka with a type change from NioChannel non-trivial object transformer,however,our empirical study to KeyAttachment (Lines 2-3).We correspondingly provide results in Section III show that existing techniques fall short on an object transformer DSUHelper.transform(Lines 16-28). most real-world cases.For this motivating example,TOS [27] The status field undergoes a default (or trivial)transfor- incorrectly falls back to the default null assignment because mation:it inherits its value from the old-version (Line 18).the non-trivial transformer is beyond TOS's search capability A default transformation copies the old-version value for a AOTES [28]also fails in synthesizing a method history for type-unchanged field or assigns a default value (e.g.,0 for int such complex objects. and null for references)to a newly-added field [15,17]. C.Discussions However,the ka field requires a non-trivial transformation If we leave ka with a default null reference,the program will Interestingly,the key non-trivial step in our manually quickly crash after DSU.Our transformer in Figure 1 leverages provided transformer,which retrieves the SelectionKey from the program's implicit invariant that there is a 1-to-1 mapping an NioChannel object in Lines 23-24,is identical to the code between NioChannel objects and KeyAttachment objects in in Lines 7-8.The null-check in the transformer (Lines 25-26) the heap.Lines 21-26 invoke a chain of I/O channel APIs to can also be found in the old-version code (Lines 10-11),which find stale.socket's corresponding KeyAttachment object. is removed in the new version because the local variable ka is Providing non-trivial object transformers is considerably available through the newly added field (Line 3). challenging even for experienced developers:it requires ex- This should not be considered completely incidental.If pertise in both the application logic and DSU system,where there is a code snippet for computing an object's property that reflects an internal invariant(potentially useful for object IDSU and object transformation for unmanaged heaps (e.g.,C/C++)are transformation like the code that finds the SelectionKey for considerably different and are out of this paper's scope.However,arguments a given NioChannel object),the code snippet might also be in this paper can also be applied to other managed runtime systems. 2An object transformer is considered trivial if it contains only default useful to other parts of the program and is likely to exist in transformations,otherwise is non-trivial. the source code

in DSU and providing it with an effective approach. The rest of the paper is organized as follows. Section II gives the necessary background knowledge of DSU with a motivating example. Section III presents a comprehensive study on DSU of 190 class changes in Tomcat 8. Our DSL and synthesis algorithm are elaborated on in Sections IV and V, respectively. The evaluation of PASTA against real-world updates is described in Section VI, followed by threats to validity discussions in Section VII, related work in Section VIII, and conclusion in Section IX. II. BACKGROUND AND MOTIVATION A. DSU Systems and Object Transformation This paper focuses on the DSU of Java programs1 , which consists of the following four steps: 1) Pause the program under update at a safe point [10, 31], e.g., when all updated code is popped off the stack [15, 17]. 2) Upgrade the changed code [32, 33] via dynamic link￾ing [34], live patching [10], or hotswap [26]. 3) Transform stale (old-version) objects in the heap to their new state [27, 28]. 4) Resume the updated program’s execution. The new version is now ready to serve. Object transformation (the third step) is this paper’s primary focus. When a program is paused at an update-safe point with code being upgraded, the heap may contain stale objects whose values are inconsistent with the new-version code. A DSU system must for each such object invoke its transformer to migrate to its corresponding new-version. B. Motivating Example Figure 1 lists a class change to SocketProcessor, which requires a non-trivial transformation. This class change replaces the socket field by ka with a type change from NioChannel to KeyAttachment (Lines 2–3). We correspondingly provide an object transformer DSUHelper.transform (Lines 16–28). The status field undergoes a default (or trivial) transfor￾mation: it inherits its value from the old-version (Line 18). A default transformation copies the old-version value for a type-unchanged field or assigns a default value (e.g., 0 for int and null for references) to a newly-added field [15, 17]. However, the ka field requires a non-trivial transformation2 . If we leave ka with a default null reference, the program will quickly crash after DSU. Our transformer in Figure 1 leverages the program’s implicit invariant that there is a 1-to-1 mapping between NioChannel objects and KeyAttachment objects in the heap. Lines 21–26 invoke a chain of I/O channel APIs to find stale.socket’s corresponding KeyAttachment object. Providing non-trivial object transformers is considerably challenging even for experienced developers: it requires ex￾pertise in both the application logic and DSU system, where 1DSU and object transformation for unmanaged heaps (e.g., C/C++) are considerably different and are out of this paper’s scope. However, arguments in this paper can also be applied to other managed runtime systems. 2An object transformer is considered trivial if it contains only default transformations, otherwise is non-trivial. 1 class SocketProcessor { 2 - private NioChannel socket = null; 3 + private KeyAttachment ka = null; 4 private SocketStatus status = null; 5 public void run() { 6 + NioChannel socket = ka.getSocket(); 7 SelectionKey key = socket.getIOChannel().keyFor( 8 socket.getPoller().getSelector()); 9 - KeyAttachment ka = null; 10 - if (key != null) 11 - ka = (KeyAttachment)key.attachment(); 12 ... } ... 13 } 14 15 class DSUHelper { 16 static void transform(SocketProcessor? obj, SocketProcessor stale) { 17 // trivial default transformation for status 18 obj.status = stale.status; 19 // non-trivial transformation for ka 20 obj.ka = null; 21 NioChannel socket = stale.socket; 22 if (socket != null) { 23 SelectionKey key = socket.getIOChannel().keyFor( 24 socket.getPoller().getSelector()); 25 if (key != null) 26 obj.ka = (KeyAttachment)key.attachment(); 27 } 28 } 29 } Fig. 1: A class change in Tomcat-8 (commit #f4451c) whose object transformation is non-trivial. DSUHelper is our manually provided object transformer. At update time, the DSU system for each (stale) object sp (of type SocketProcessor) creates its corresponding uninitialized new-version object sp? (of type SocketProcessor? , the same class after update) and invokes the object transformer DSUHelper.transform(sp?, sp). the latter is typically lacking for most application developers. Sometimes, a DSU system may automatically synthesize a non-trivial object transformer, however, our empirical study results in Section III show that existing techniques fall short on most real-world cases. For this motivating example, TOS [27] incorrectly falls back to the default null assignment because the non-trivial transformer is beyond TOS’s search capability. AOTES [28] also fails in synthesizing a method history for such complex objects. C. Discussions Interestingly, the key non-trivial step in our manually provided transformer, which retrieves the SelectionKey from an NioChannel object in Lines 23–24, is identical to the code in Lines 7–8. The null-check in the transformer (Lines 25–26) can also be found in the old-version code (Lines 10–11), which is removed in the new version because the local variable ka is available through the newly added field (Line 3). This should not be considered completely incidental. If there is a code snippet for computing an object’s property that reflects an internal invariant (potentially useful for object transformation like the code that finds the SelectionKey for a given NioChannel object), the code snippet might also be useful to other parts of the program and is likely to exist in the source code

not dynamically updatable FINDING 1.Almost all changed classes (187/190,or 98.4%) 1.6% ▣non-trivial(need a transformer） are dynamically updatable using either trivial default or non- trivial provided object transformers. non-trivial (need update-time config) 700 69 trivial (object unchanged) In the three failing cases,two of them added new fields trivial (object changed) whose values are only available in an already popped stack frame.Another one is a fix for a resource leak in which whether an object is leaked cannot be effectively determined. Fig.2:Taxonomy of the 190 changed classes in Tomcat 8. Fortunately,refactoring the program to discard partial states at a component level [4,29,30]can make them updatable. This observation motivates us to explore the possibility of Furthermore,we found that simple default object transfor- mation suffices in most cases: automatically synthesizing object transformers by reassembling existing code snippets,including both old and new versions of a FINDING 2.Most class changes (166/190,or 87.4%)can be program.This observation is further validated in our empirical dynamically updated via trivial object transformers. study in Section III,and then implemented as a heuristic search 133 out of the 166 class changes (80.1%)involve only algorithm in Section V. code logic upgrades that do not affect the concerned objects' III.EMPIRICAL STUDY data representations,i.e.,field values are unchanged.A typical example is a security patch.The rest 33(19.9%)class changes In this short empirical study,we seek insights for under- can be automatically handled by a DSU system's default standing the challenges of object transformation in DSU over policy [15,17,18],e.g.,assigning a newly created field with a a set of randomly sampled real-world class changes. default value or garbage collecting a removed field's referred objects. A.Methodology Finally,class changes that require non-trivial object trans- We empirically studied the applicability of DSU in the formers are of particular research interest: evolution of Apache Tomcat 8 [23],one of the most popular Java Web servers.Tomcat 8 is still under active maintenance FINDING 3.Not many but non-negligible class changes(21/190, upgrades since its first release in 2013,making it a suitable or 11.1%)require non-trivial object transformers.These subject for studying DSU.We uniform-randomly sampled changes substantially hinder the application of DSU in practice. 100 commits from all 2,114 Tomcat 8 commits in its entire For these updates,the upgrade maintainer can manually maintenance history by the paper was written (from 8.0.0 to provide an object transformer to enable DSU over such non- the latest release 8.0.53).The sampled commits consist of in trivial class changes.However,this is not an easy task because total 190 class changes3. non-trivial object transformers usually exploit a program's For each changed class,we manually inspected the program implicit invariants or object state constraints (like the example state at a hypothetical update-safe point in which all changed in Figure 1).Automatic transformer synthesis [27,28]can methods of the class are popped off the stack.We determine be a promising and highly-preferred solution.Unfortunately. whether object transformation is possible(i.e.,whether DSU is our later experiments show that even the best state-of-the-art applicable)at that point and try to provide each of 2,957 fields technique produces correct transformations in <10%of these in the 190 changed classes a transformer.Given a class change non-trivial class changes. that can be dynamically updated,its object transformer is Therefore,the general unavailability of non-trivial object considered trivial if all of its field transformations are default transformers should be recognized as a key obstacle in making (explained in Section ID).Otherwise,the non-trivial object DSU practical.To address this challenge,we examined the transformer has at least one field that requires non-trivial characteristics of our manually crafted object transformers to transformation (like ka in Figure 1). find potentially useful guidance for automatic object trans- To validate our observation that non-trivial transformers can former synthesis.Figure 3 summarizes the basic constructs be constructed by reassembling existing code snippets,we in our manual transformers,which can be concluded by the preferred reusing old/new version code statements with minor following finding: revisions.We collect and analyze the statistics of those reused FINDING 4.Default transformations and existing code snippets statements in constructing transformers. are the major constructs of a non-trivial object transformer. B.Results and Findings The basic constructs of the 21 non-trivial object transformers The statistics in Figure 2 first indicate that DSU can be are:42 right-hand side expressions of assignments,15 if- broadly applicable in a program's maintenance lifetime: then-else branch conditions,and 2 for-each loop conditions. Understanding the characteristics of these basic constructs 3Commits that do not change the Tomcat-core source code (e.g..documen- is critical to the development of an automatic transformer tation or test case updates)are excluded from the study because they are irrelevant to DSU.190 are all class changes because changes to Tomcat 8 are 4Dynamically updating such a class with a default transformer will result mainly maintenance upgrades. in a crash or broken application logic

1.6% 9.5% 1.6% 70.0% 17.4% not dynamically updatable non-trivial (need a transformer) non-trivial (need update-time config) trivial (object unchanged) trivial (object changed) Fig. 2: Taxonomy of the 190 changed classes in Tomcat 8. This observation motivates us to explore the possibility of automatically synthesizing object transformers by reassembling existing code snippets, including both old and new versions of a program. This observation is further validated in our empirical study in Section III, and then implemented as a heuristic search algorithm in Section V. III. EMPIRICAL STUDY In this short empirical study, we seek insights for under￾standing the challenges of object transformation in DSU over a set of randomly sampled real-world class changes. A. Methodology We empirically studied the applicability of DSU in the evolution of Apache Tomcat 8 [23], one of the most popular Java Web servers. Tomcat 8 is still under active maintenance upgrades since its first release in 2013, making it a suitable subject for studying DSU. We uniform-randomly sampled 100 commits from all 2,114 Tomcat 8 commits in its entire maintenance history by the paper was written (from 8.0.0 to the latest release 8.0.53). The sampled commits consist of in total 190 class changes3 . For each changed class, we manually inspected the program state at a hypothetical update-safe point in which all changed methods of the class are popped off the stack. We determine whether object transformation is possible (i.e., whether DSU is applicable) at that point and try to provide each of 2,957 fields in the 190 changed classes a transformer. Given a class change that can be dynamically updated, its object transformer is considered trivial if all of its field transformations are default (explained in Section II). Otherwise, the non-trivial object transformer has at least one field that requires non-trivial transformation (like ka in Figure 1). To validate our observation that non-trivial transformers can be constructed by reassembling existing code snippets, we preferred reusing old/new version code statements with minor revisions. We collect and analyze the statistics of those reused statements in constructing transformers. B. Results and Findings The statistics in Figure 2 first indicate that DSU can be broadly applicable in a program’s maintenance lifetime: 3Commits that do not change the Tomcat-core source code (e.g., documen￾tation or test case updates) are excluded from the study because they are irrelevant to DSU. 190 are all class changes because changes to Tomcat 8 are mainly maintenance upgrades. FINDING 1. Almost all changed classes (187/190, or 98.4%) are dynamically updatable using either trivial default or non￾trivial provided object transformers. In the three failing cases, two of them added new fields whose values are only available in an already popped stack frame. Another one is a fix for a resource leak in which whether an object is leaked cannot be effectively determined. Fortunately, refactoring the program to discard partial states at a component level [4, 29, 30] can make them updatable. Furthermore, we found that simple default object transfor￾mation suffices in most cases: FINDING 2. Most class changes (166/190, or 87.4%) can be dynamically updated via trivial object transformers. 133 out of the 166 class changes (80.1%) involve only code logic upgrades that do not affect the concerned objects’ data representations, i.e., field values are unchanged. A typical example is a security patch. The rest 33 (19.9%) class changes can be automatically handled by a DSU system’s default policy [15, 17, 18], e.g., assigning a newly created field with a default value or garbage collecting a removed field’s referred objects. Finally, class changes that require non-trivial object trans￾formers are of particular research interest: FINDING 3. Not many but non-negligible class changes (21/190, or 11.1%) require non-trivial object transformers4 . These changes substantially hinder the application of DSU in practice. For these updates, the upgrade maintainer can manually provide an object transformer to enable DSU over such non￾trivial class changes. However, this is not an easy task because non-trivial object transformers usually exploit a program’s implicit invariants or object state constraints (like the example in Figure 1). Automatic transformer synthesis [27, 28] can be a promising and highly-preferred solution. Unfortunately, our later experiments show that even the best state-of-the-art technique produces correct transformations in <10% of these non-trivial class changes. Therefore, the general unavailability of non-trivial object transformers should be recognized as a key obstacle in making DSU practical. To address this challenge, we examined the characteristics of our manually crafted object transformers to find potentially useful guidance for automatic object trans￾former synthesis. Figure 3 summarizes the basic constructs in our manual transformers, which can be concluded by the following finding: FINDING 4. Default transformations and existing code snippets are the major constructs of a non-trivial object transformer. The basic constructs of the 21 non-trivial object transformers are: 42 right-hand side expressions of assignments, 15 if￾then-else branch conditions, and 2 for-each loop conditions. Understanding the characteristics of these basic constructs is critical to the development of an automatic transformer 4Dynamically updating such a class with a default transformer will result in a crash or broken application logic

Statements in a transformer SelectionKey key socket.getIOChannel().keyFor( socket.getPoller().getSelector()); Assignment(42) Conditidnal (15) Loop (2) extraction V=E if(E){…3 for (x:E) g1=(1.getIOChannel().keyFor(2.getPoller().getSelector())) else {... {..3 E(42) E(15) E(2) if (name.startswith("selectorPool.")) extraction Source 8 Source g2 =(1.startswith(2)) Null-check 93 =("selectorPool.") 7 94 =(01.startswith("selectorPool.")) 12 Fig.3:Statistics of the basic constructs in the studied non-trivial while (paused &!running) object transformers. extraction 95=(o1&D2) Transformer Fig.5:Examples of extracted gadgets. Statement v e; obj.f=e; if (c){s*else s*) while (c){s*} A.The Language Design Condition = ee =null!c Following the empirical findings that default transformations Expression vIg(v) and existing code snippets are the major constructs of a non- Gadget 9= extracted gadgets trivial object transformer,we made the following choices in Variable 0 = stale v v2... the DSL design: 1)Providing a mechanism for code reuse.Particularly,we Fig.4:Syntax of basic constructs in object transformers.f is provide a DSL construct named gadget,as denoted by a field subject to transformation;stale and obj are the stale g(),a textural expression extracted from source code object and its corresponding new-version object;a*denotes with all variable references being replaced by a place- zero or more repeats of a. holder.We use angled brackets to enclose a gadget,e.g., g(o1,☐2，☐3)=(O1.foo(o2,☐3)）.Applying a gadget to an object transformer would reuse the entire expression synthesis mechanism.As shown in Figure 3,the vast majority with the flexibility for placeholders to be filled with (54/59,or 91.5%)of the basic constructs are either: transformer-specific values. 1)a trivial default behavior (13/59,or 22.0%), 2)Providing no arithmetic,logical,or bitwise operator.We 2)a single member method call (12/59,or 20.3%), argue that when such operators (+,&&1,...)should 3)a simple null-check (7/59,or 11.9%),or appear in an object transformer,they will also likely to 4)a minor revision of an existing source code snippet (22/59, exist in old/new version source code and can be extracted or 37.3%)like Lines 23-24 in Figure 1. as gadgets.Therefore,we do not have to include them in Such a result motivated us to synthesize object transformers the DSL.yielding a minimal,concise DSL by assembling source code gadgets (extracted expressions from 3)Providing limited expressiveness for branch/loop condi- old/version source code)upon a domain-specific language tions.Branch/loop conditions in object transformers are designated for the object transformation in DSU. also likely in the existing source code.Therefore,nega- For the remaining a few (5/59,or 8.5%)basic constructs, tions,nested branches,and while-loops provide sufficient three of them are boolean configuration-related constants expressiveness for constructing object transformers. whose values are determined by an update-time configuration. Figure 4 lists the syntax of our DSL.An object transformer The other two expressions need a reference that is not reachable t is a sequence of statements s*,in which each field of the from stale objects.Since this paper focuses on the automatic new-version object obj is assigned with a value.For each synthesis of object transformers,we leave these relatively rare statement s,it can define a new variable v:by applying a cases to future work. gadget g and filling its placeholders with existing variables(a previously defined vi or stale),assign a field to be transformed IV.DOMAIN-SPECIFIC LANGUAGE FOR OBJECT (obj.f)with a value,or use if branches or while loops with TRANSFORMATION a condition c. This section explains our design goals and choices in Readers may notice that the statements in a transformer t our domain-specific language (DSL)for describing object describe a skeleton,which specifies the targeted transformer's transformers.The DSL design and gadget extraction are 5We allow a void-typed expression to be assigned to a variable,i.e..g can described in Sections IV-A and IV-B,respectively. be a void method invocation

Default Member 13 12 Source 12 Others 5 Source 8 Null-check 7 Source 2 v = E if (E) {...} else {...} for (x: E) {...} Statements in a transformer E (42) E (15) E (2) Assignment (42) Conditional (15) Loop (2) Fig. 3: Statistics of the basic constructs in the studied non-trivial object transformers. Transformer t ::= s ∗ Statement s ::= v = e; | obj.f = e; | if (c) { s ∗ } else { s ∗ } | while (c) { s ∗ } Condition c ::= e | e == null | !c Expression e ::= v | g(v ∗ ) Gadget g ::= extracted gadgets Variable v ::= stale | v1 | v2 | . . . Fig. 4: Syntax of basic constructs in object transformers. f is a field subject to transformation; stale and obj are the stale object and its corresponding new-version object; a ∗ denotes zero or more repeats of a. synthesis mechanism. As shown in Figure 3, the vast majority (54/59, or 91.5%) of the basic constructs are either: 1) a trivial default behavior (13/59, or 22.0%), 2) a single member method call (12/59, or 20.3%), 3) a simple null-check (7/59, or 11.9%), or 4) a minor revision of an existing source code snippet (22/59, or 37.3%) like Lines 23–24 in Figure 1. Such a result motivated us to synthesize object transformers by assembling source code gadgets (extracted expressions from old/version source code) upon a domain-specific language designated for the object transformation in DSU. For the remaining a few (5/59, or 8.5%) basic constructs, three of them are boolean configuration-related constants whose values are determined by an update-time configuration. The other two expressions need a reference that is not reachable from stale objects. Since this paper focuses on the automatic synthesis of object transformers, we leave these relatively rare cases to future work. IV. DOMAIN-SPECIFIC LANGUAGE FOR OBJECT TRANSFORMATION This section explains our design goals and choices in our domain-specific language (DSL) for describing object transformers. The DSL design and gadget extraction are described in Sections IV-A and IV-B, respectively. SelectionKey key = socket.getIOChannel().keyFor( socket.getPoller().getSelector()); g1 = h1.getIOChannel().keyFor(2.getPoller().getSelector())i extraction if (name.startsWith("selectorPool.")) g2 = h1.startsWith(2)i g3 = h"selectorPool."i g4 = h1.startsWith("selectorPool.")i extraction while (paused && !running) g5 = h1 && !2i extraction Fig. 5: Examples of extracted gadgets. A. The Language Design Following the empirical findings that default transformations and existing code snippets are the major constructs of a non￾trivial object transformer, we made the following choices in the DSL design: 1) Providing a mechanism for code reuse. Particularly, we provide a DSL construct named gadget, as denoted by g(~), a textural expression extracted from source code with all variable references being replaced by a place￾holder. We use angled brackets to enclose a gadget, e.g., g(1, 2, 3) = h1.foo(2,3)i. Applying a gadget to an object transformer would reuse the entire expression with the flexibility for placeholders to be filled with transformer-specific values. 2) Providing no arithmetic, logical, or bitwise operator. We argue that when such operators (+, &&, |, . . .) should appear in an object transformer, they will also likely to exist in old/new version source code and can be extracted as gadgets. Therefore, we do not have to include them in the DSL, yielding a minimal, concise DSL. 3) Providing limited expressiveness for branch/loop condi￾tions. Branch/loop conditions in object transformers are also likely in the existing source code. Therefore, nega￾tions, nested branches, and while-loops provide sufficient expressiveness for constructing object transformers. Figure 4 lists the syntax of our DSL. An object transformer t is a sequence of statements s ∗ , in which each field of the new-version object obj is assigned with a value. For each statement s, it can define a new variable vi by applying a gadget g 5 and filling its placeholders with existing variables (a previously defined vi or stale), assign a field to be transformed (obj.f) with a value, or use if branches or while loops with a condition c. Readers may notice that the statements in a transformer t describe a skeleton, which specifies the targeted transformer’s 5We allow a void-typed expression to be assigned to a variable, i.e., g can be a void method invocation.

control flow (branches and loops)and data flow (variables and their dependencies).All concrete transformation operations g1(1)=(01.socket) are performed by gadgets extracted from the source code 92(1,2)=(1.getIoChannel().keyFor( Such a separation of concerns not only maximally reuses 02.getPoller().getSelector())) existing source code,but also gives considerable flexibility to 93(1)=((KeyAttachment)01.attachment()) implement diverse transformers.This design also facilitates our 1class DSUHelper 2 static void transform(SocketProcessor*obj,SocketProcessor stale){ later heuristic synthesis algorithm to prioritize likely relevant v1 =(NioChannel)g1(stale); object transformers by measuring both the structural complexity 4 if (v1 !null){ of a synthesized transformer and its "naturalness"in gadget v2 =(SelectionKey)g2(v1,v1); 6 if (v2 !null){ use. v3 =(KeyAttachment)g3(v2); One final note is that we restrict branch/loop conditions to be either of e,!e,e ==null,or e !null,where expression 9 e is either a variable or a gadget application.Theoretically. 1 obj.ka va; 11] any condition can be expressed by negation()and nested 12] branch (A),but both our DSL and synthesis algorithm favor simple branch/loop conditions that reuse existing source code Fig.6:A field transformer for field ka in the motivating snippets. example written in our DSL,and extracted gadgets.All used B.Gadget Extraction variables were initialized with default values,e.g.,v3=null. In gadget extraction,trade-offs must be made to balance the DSL's expressiveness and its synthesis difficulty.In an imprac- Algorithm 1:The transformer synthesis framework tical extreme,one can include all Java language constructs as 1 Function SYNTHESIS(G) gadgets.This allows our DSL to be essentially equivalent to the 2 Q←-{>}： while Q≠ado vanilla Java.However,synthesizing Java programs directly for p← arg min cost(p'); object transformation is considerably difficult and not practical. P'EQ The key trade-off we made is to only extract complete source- iflb走p then code statements as gadgets.We argue that no matter how many yield p: times method invocations,arithmetic/logical operations,etc. Q←QUDc(p)\{p} are performed in a statement,they should either be all used or entirely not used in an object transformer.The intuition behind this treatment is simple:each statement should contain a logically inseparable action in a well-maintained project for class method gadgets (methodName()),static field best readability and maintainability. gadgets (ClassName.fieldName),static method gadgets Gadgets are extracted by iterating over all statements in all (ClassName.methodName()),and object creation gad- application classes in both the old and new version source code gets (new className()).These rules are also addition- using the following rules: ally applied for the Java Standard Library for extracting 1)For a statement's associated expression (i.e..the right- potentially useful API calls,e.g.,container operations. hand side of an assignment or an if/while condition), Figure 6 gives a transformer example for field ka in our we parse it into an abstract syntax tree (AST)and replace motivating example (Figure 1).Three used gadgets g,92. each variable or constant node with a placeholder to and g3 are extracted using rules #4,#1,and #1,respectively. be a gadget.This rule yields g,g2.and g5 in Figure 5. This transformer is equivalent to the manually provided one in 2)For each statement,we consider its contained constants Figure 1. potentially useful in synthesizing object transformers. One could expect that our DSL and gadget extraction rules Therefore,each constant literal in the statement is also suffice for object transformer synthesis.Unfortunately,there extracted as a gadget.This rule yields g3 in Figure 5. can be millions of gadgets extracted from a large codebase. 3)For each statement,we also extract it into a gadget where Certainly,not all gadget combinations are equally relevant to a only variable nodes are replaced by placeholders,i.e.,given upgrade.The relevance of a gadget to the class change keeping all constants as-is in the gadget compared with and the similarity between a gadget combination and existing the first rule.This is because constants may be inseparable source code would serve as the guidance for efficient object from the statement's computational logic.This rule yields transformer synthesis,which is described as follows. 94 in Figure 5. 4)For each class in both old and new versions of the V.AUTOMATIC SYNTHESIS OF OBJECT TRANSFORMERS source code,we extract class field gadgets (fieldName), Conceptually,object transformer synthesis is simple:a 6There can be occasions that a statement consists of multiple actions.e.ga systematic enumeration of all syntactically correct programs chain of method invocations.We optimistically believe that the desired action will eventually find a correct transformer(Section V-A).This will independently appear elsewhere in the codebase. section presents our heuristic search algorithm for efficiently pri-

control flow (branches and loops) and data flow (variables and their dependencies). All concrete transformation operations are performed by gadgets extracted from the source code. Such a separation of concerns not only maximally reuses existing source code, but also gives considerable flexibility to implement diverse transformers. This design also facilitates our later heuristic synthesis algorithm to prioritize likely relevant object transformers by measuring both the structural complexity of a synthesized transformer and its “naturalness” in gadget use. One final note is that we restrict branch/loop conditions to be either of e, !e, e == null, or e != null, where expression e is either a variable or a gadget application. Theoretically, any condition can be expressed by negation (¬) and nested branch (∧), but both our DSL and synthesis algorithm favor simple branch/loop conditions that reuse existing source code snippets. B. Gadget Extraction In gadget extraction, trade-offs must be made to balance the DSL’s expressiveness and its synthesis difficulty. In an imprac￾tical extreme, one can include all Java language constructs as gadgets. This allows our DSL to be essentially equivalent to the vanilla Java. However, synthesizing Java programs directly for object transformation is considerably difficult and not practical. The key trade-off we made is to only extract complete source￾code statements as gadgets. We argue that no matter how many times method invocations, arithmetic/logical operations, etc. are performed in a statement, they should either be all used or entirely not used in an object transformer. The intuition behind this treatment is simple: each statement should contain a logically inseparable action in a well-maintained project for best readability and maintainability6 . Gadgets are extracted by iterating over all statements in all application classes in both the old and new version source code using the following rules: 1) For a statement’s associated expression (i.e., the right￾hand side of an assignment or an if/while condition), we parse it into an abstract syntax tree (AST) and replace each variable or constant node with a placeholder i to be a gadget. This rule yields g1, g2, and g5 in Figure 5. 2) For each statement, we consider its contained constants potentially useful in synthesizing object transformers. Therefore, each constant literal in the statement is also extracted as a gadget. This rule yields g3 in Figure 5. 3) For each statement, we also extract it into a gadget where only variable nodes are replaced by placeholders, i.e., keeping all constants as-is in the gadget compared with the first rule. This is because constants may be inseparable from the statement’s computational logic. This rule yields g4 in Figure 5. 4) For each class in both old and new versions of the source code, we extract class field gadgets h.fieldNamei, 6There can be occasions that a statement consists of multiple actions, e.g., a chain of method invocations. We optimistically believe that the desired action will independently appear elsewhere in the codebase. g1(1) = h1.socketi g2(1, 2) = h1.getIOChannel().keyFor( 2.getPoller().getSelector())i g3(1) = h(KeyAttachment) 1.attachment()i 1 class DSUHelper { 2 static void transform(SocketProcessor? obj, SocketProcessor stale) { 3 v1 = (NioChannel) g1(stale); 4 if (v1 != null) { 5 v2 = (SelectionKey) g2(v1, v1); 6 if (v2 != null) { 7 v3 = (KeyAttachment) g3(v2); 8 } 9 } 10 obj.ka = v3; 11 } 12 } Fig. 6: A field transformer for field ka in the motivating example written in our DSL, and extracted gadgets. All used variables were initialized with default values, e.g., v3 = null. Algorithm 1: The transformer synthesis framework 1 Function SYNTHESIS(G) 2 Q ← {|.}; 3 while Q 6= ∅ do 4 p ← arg min p0∈Q cost(p 0 ); 5 if |. /∈ p then 6 yield p; 7 Q ← Q ∪ DG(p) \ {p} class method gadgets h.methodName(~)i, static field gadgets hClassName.fieldNamei, static method gadgets hClassName.methodName(~)i, and object creation gad￾gets hnew ClassName(~)i. These rules are also addition￾ally applied for the Java Standard Library for extracting potentially useful API calls, e.g., container operations. Figure 6 gives a transformer example for field ka in our motivating example (Figure 1). Three used gadgets g1, g2, and g3 are extracted using rules #4, #1, and #1, respectively. This transformer is equivalent to the manually provided one in Figure 1. One could expect that our DSL and gadget extraction rules suffice for object transformer synthesis. Unfortunately, there can be millions of gadgets extracted from a large codebase. Certainly, not all gadget combinations are equally relevant to a given upgrade. The relevance of a gadget to the class change and the similarity between a gadget combination and existing source code would serve as the guidance for efficient object transformer synthesis, which is described as follows. V. AUTOMATIC SYNTHESIS OF OBJECT TRANSFORMERS Conceptually, object transformer synthesis is simple: a systematic enumeration of all syntactically correct programs will eventually find a correct transformer (Section V-A). This section presents our heuristic search algorithm for efficiently pri-