Runtime Software Patching: Taxonomy, Survey and Future Directions

Traditional or offline patching implies stopping the running software instance, potentially converting existing data and starting a new instance (Inst6-Function5-Replus-chen2015framework, ; Function10-Orso2002DUSC, ). As shown in Figure 1, the first step in software patching is patch preparation. The prepared patch targets source or binary levels depending on whether the source code is available. Source-targeted patches require a potentially time-consuming software recompilation to produce a new (patched) executable, while binary-targeted modify the existing software executable. Source code level patching allows the programmer to easily modify arbitrary aspects of the software, such as replacing any functions, instructions and data flows. On the other hand, binary patches are somewhat more limited in their nature and are used for smaller-scale modifications (primarily in the security context). The main complication in binary patching is that any code length changes can cause significant memory pointers invalidation. In addition, in binary-level patching, finding the exact location to modify the buggy part may be complicated (xu2020automatic-Kernel4F-Inst2Vulmet, ). Besides, the old binary can still run, further complicating the patching process. Furthermore, as the newly patched binary is ready for execution, running it may cause conflict due to resource sharing when the old binary uses the same resource.

Challenges with traditional patching: The major drawback of the traditional software patching approach is the associated service interruption when the old binary is stopped and the new one is not fully started (inst8-DSU-Hics2005, ; Function10-Orso2002DUSC, ). For instance, remote or local user sessions, network connections and data processing are interrupted or suspended when the patched software system stops. Short interruptions may be acceptable (albeit inconvenient) in interactive user sessions such as web browsing or word processing. Interactive software is commonly designed to automatically save and restore user sessions to mitigate such inconveniences to some extent. Web browsers that attempt to restore the state between restarts are a good example of such mitigation. In contrast, experiencing service disruptions in highly critical systems may cause significant monetary losses or be considered entirely unacceptable. For example, for life-support software and air-traffic controller, shutting down a system is prohibited or not considered an option (Function10-Orso2002DUSC, ). Thus, system administrators may opt to delay patch deployment to avoid potential system reboots that cause service disruption and loss of application state. For example, updating the OS on servers for highly interactive activities like online gaming or video streaming typically needs to schedule server downtime. During this time, players have to stop the game, wait for the servers to be updated and restarted, then login back in to the server and potentially start the game from the beginning, which is bothersome for the players. Unfortunately, keeping a vulnerable system un-patched for a prolonged period of time increases the risk of having the system exploited. In efforts to overcome these challenges of traditional patching, runtime patching has emerged and gained popularity. Details of runtime patching and related benefits are discussed in Section 3.

Several software patch and update related reviews have been conducted in recent years (seifzadeh2013survey, ; ahmed2020dynamic-LR, ; miedes2012survey, ; lopez2017survey, ; ilvonen2016dynamic, ; gregersen2013state, ; mugarza2018analysis, ). Ahmed et al. (ahmed2020dynamic-LR, ) have performed a comprehensive systematic mapping study related to runtime software updating solutions. We encountered somewhat unstructured approach classifications while analyzing a large number of papers. For example, the most cited updating approaches include “Java VM” and “Multi-version,” which do not necessarily have to be mutually exclusive. Furthermore, while the study has provided the statistics and an overview of approaches used, it lacks details on approach-specific benefits and challenges and the correlation between the adoption of techniques, tools and algorithms.

A more structured categorization of runtime software updating solutions is presented by Seifzadeh et al. (seifzadeh2013survey, ). This study presents a comprehensive, albeit high-level set of runtime updating evaluation metrics, such as scope, time of update, and type safety. Rather than focusing on existing implementations, Miedes et al. (miedes2012survey, ) have outlined the concepts and techniques used in runtime software updating in general. In addition, the set of goals and requirements such as service continuity and generality are identified and discussed. However, no coherent taxonomy or classification of such approaches is presented, leading to somewhat mismatched categories. For instance, while being orthogonal in terms of goals, Java-oriented approaches and rollback-ability are discussed alongside technical challenges.

In addition, some reviews focus on particular technical domains and usage scenarios. For instance, Lopez et al. (lopez2017survey, ) have surveyed existing function and system call hooking approaches. While function hooking can be used for a multitude of purposes (including malicious), function-level patching can significantly benefit by applying hooking techniques. One of the main strengths of the survey is the comprehensive view of both function and system call hooking under major operating systems. However, the scope of this review is limited to function granularity only and does not consider other patching levels. Another study by Gregersen et al. (gregersen2013state, ) have compared three existing runtime patching implementations for Java applications. On top of evaluating the performance of the implementations, low-level patching capabilities were analyzed. The scope of the review is only limited to Java-specific capabilities such as class modifications were considered. Lastly, Mugarza et al. (mugarza2018analysis, ) have focused on runtime software updating in the industrial IoT domain. Specifically, the requirements of safety systems are evaluated using nuclear control systems as a case study.

Unlike the existing reviews, Ilvonen et al.  (ilvonen2016dynamic, ) have taken an interesting perspective by analyzing the support of runtime or Dynamic Software Updating (DSU) in the software engineering education context. In particular, existing software engineering courses are analyzed to determine the adoption and coverage of DSU concepts. The main finding of this study is the lack of a holistic approach towards DSU in education, with only certain individual aspects being addressed in education.

Several observations are made based on the reviewed studies. Firstly, there is still a lack of common understanding in the domain of runtime patching, even at the level of terminology. Secondly, no clear taxonomy coherently categorizing the existing runtime patching approaches has been developed so far. Thirdly, lack of generality hinders the wider adoption of the existing runtime software patching methodologies and tools. Fourthly, evaluation metrics vary wildly depending on the intended runtime patching domain, ranging from generic time overhead to language-specific class modifications.

Scope of our survey: Our survey focuses on multiple aspects of runtime patching approaches such as patch scale, general tactics and responsibility. A detailed taxonomy is presented along with the corresponding analysis of the existing solutions. The main focus lies within the applying patch phase in the patch management life cycle shown in Figure 1. Unlike the existing surveys, which are typically narrow-focused and mainly highlight the methodologies and tools used for patching, we attempt to generalize the issues and approaches inherent to different patch granularity levels. It is worth noting that our survey does not compare the performance of different techniques or solutions because of the vastly different experimental setups and execution environments observed. Similarly, due to the high diversity of the solutions reviewed, different evaluation techniques cannot be compared directly, as different implementations focus on different metrics (e.g., downtime, overhead and long-term patch continuity). Naturally, systems aiming to achieve zero downtime would not even consider such a metric in their evaluation procedures. Furthermore, we indicate the existing state-of-the-art solutions’ common challenges and suggest a set of future directions to advance the field.

Runtime software patching approaches provide a number of practical benefits. First, from the security perspective, patching a running software reduces the vulnerable time window while a long-term solution is being prepared. A typical example of such immediate fixes is temporarily disabling a vulnerable code path, with the long-term solution to fix the expected code behavior. In some cases, applying such simple patches gain an additional time necessary for long-term testing changes at the expense of reduced functionality. Some prominent goals and benefits of runtime patching include reducing service interruption (inst8-DSU-Hics2005, ; Function10-salls2017piston, ; Inst7-payer2013dynsec, ), system downtime (Function7Kshot, ; Function10-salls2017piston, ), frequency of reboots (Inst7-payer2013hotAsap, ; Function1KspliceArnold2009, ; hypervisor2-Orthus-zhang2019fast, ) and human involvement (Function10-salls2017piston, ; Function1KspliceArnold2009, ). While achieving these goals, a runtime patching solution also aims to avoid loss of data and running states of applications to improve end-user experience (Function7Kshot, ; Kernel1Kup, ; hypervisor1-hyperFresh-doddamani2019, ; Function1KspliceArnold2009, ). In combination, these advantages of runtime software patching are beneficial from a business perspective in terms of service reliability and reduction of potential monetary losses. Reviewing the existing study, we identify that high availability, quick vulnerability mitigation and improving user experiences are three key aspects in consideration behind runtime patching.

• •

  High availability: Providing uninterrupted highly-available service is crucial in critical domains such as defense, medical, industrial control systems and cloud systems. As such mission-critical systems require high availability (inst8-DSU-Hics2005, ; Inst5-chen2013safestack, ; Inst6-Function5-Replus-chen2015framework, ; Function8-Cure-zhao2016, ; hypervisor2-Orthus-zhang2019fast, ), any disruptions caused by applying patch are unacceptable.

• •

  Quick vulnerability mitigation: Runtime patching allows to mitigate vulnerabilities by fixing or disabling unsafe code fragments on the fly (Inst5-chen2013safestack, ; Inst1-Karmachen2017adaptive, ; Inst4-chen2018instaguard, ; Function1KspliceArnold2009, ). In addition to full-fledged logic improvements, quick temporary solutions such as disabling vulnerable code paths or filtering unsafe user input can be used in practice.

• •

  Improving user experience: Applying proper long-term runtime patches reduces the number of software system restarts, thus effectively simplifying overall system maintenance. In addition, this improves the end-user experience as fewer user workflow disruptions (including potential recovery steps) would be encountered during day-to-day system usage (inst8-DSU-Hics2005, ; Inst1-Karmachen2017adaptive, ; xu2020automatic-Kernel4F-Inst2Vulmet, ). From an end-user perspective, runtime patching attempts to reduce either frequency or length of service disruptions.

We propose a taxonomy to categorize the studies related to runtime patching as shown in Figure 2 in terms of what, how and who. While analyzing the patching techniques incorporated in different studies, we identify that patches are applied at different levels, such as individual function, single process or the whole Operating System (OS) kernel. We further find that a number of patching levels are implemented in the existing approaches. Hence, the first category we have in our taxonomy is patch granularity. By patch granularity, we mean the scope of a patch supported by a given solution. The scope of a patch refers to the scale of the change supported by a patching solution. For instance, some solutions support patching individual machine-level instructions, while others support replacing whole functions. On the other hand, larger-scale approaches focus on updating higher-level units such as whole containers or VMs.

We notice that when considering what to patch, the surveyed studies have addressed different issues and proposed different approaches. Therefore, analyzing the studies, we extract seven granularity levels by grouping the related runtime patching studies in terms of granularity that the studies aim to patch at runtime. Note that only a few papers are categorized into more than one sub-category for cases where one study has proposed an approach that performs patching at multiple granularities (Inst6-Function5-Replus-chen2015framework, ).

The second and third categories focus on the ”how” aspect of the patching and the general techniques employed by an approach (patch strategy) and technical capabilities of a given patching system implementation (discussed in Section 5. Two main strategies identified are state transformation and co-exist & decay. In some cases, direct state transformation is possible when the changes imposed by a patch are not significant. For instance, adding an object property or a method to reflect new (patched) functionality could be straightforward. In contrast, removing or modifying existing functions is likely to cause other code fragments that rely on previous behavior. Thus, the co-exist & decay approach aims to separate old and new data objects based on sessions or transactions where possible. In other words, old (unpatched) objects currently in use are not modified, while new code patches would be directed at updated objects. Later, old objects are disposed of when the pre-existing sessions/transactions are completed. The implementation capabilities directly reflect the practical applicability of a given solution. For instance, some systems might be capable of automated safe updating time windows detection, while others lacking such capability have to resort to manual assistance from the developers. Similarly, less capable systems may require extra external assistance in memory management to load or fit patched code into RAM.

In the fourth category, we have identified the entities involved and their responsibilities considered by a patching system. Specifically, we focus on ”who” is responsible for applying the patches. The existing studies take three common responsibility-targeted views. First, vendor-supported patching systems that imply the original software system developers as in charge of the patching process. Second, software system end-users who need to patch a running system. Lastly, independent third-party patchers who attempt to provide facilities to apply generic patches to existing generic software (within certain limits). These situations differ in the amount of prior knowledge available to the patchers. Most significantly, developers would naturally access the original software source code, while end-users would not. Similarly, original developers would possess more profound knowledge of the application internals and logic.

There can be other ways the studies can be categorized; however, our primary focus is to identify the level at which a patch is applied and the adopted or proposed approaches to apply the patch at runtime. This helps us determine the issues of runtime patching approaches being neglected by the practitioners and identify potentially beneficial future directions.

Instruction-level patching requires the patching solution to write the changed instructions into an appropriate memory location. It aims to replace machine-level CPU commands or individual bytes in the RAM (Inst1-Karmachen2017adaptive, ; xu2020automatic-Kernel4F-Inst2Vulmet, ; Inst3-WordPatch-chamith2016living, ). We have identified a set of studies that have performed instruction level patching (Inst1-Karmachen2017adaptive, ; xu2020automatic-Kernel4F-Inst2Vulmet, ; Inst3-WordPatch-chamith2016living, ; Inst4-chen2018instaguard, ; Inst5-chen2013safestack, ; Inst6-Function5-Replus-chen2015framework, ). Patch preparation slightly differs in instruction level patching depending on the source code availability for a given software. In both cases, the patch preparation output is a sequence of bytes to be written to a certain memory address (potentially computed dynamically). Instruction level patching is lightweight and faster than function level patching (Inst6-Function5-Replus-chen2015framework, ).

Table 1 summarizes the works that have proposed instruction-oriented runtime patching approaches. We have identified the goal of each study along with the task related to patchings, such as patch generation, deployment, verification and restoration. By goal, we consider the focus on the studies - for instance, whether a solution is focused on updating software, fixing a bug, vulnerabilities or patching specific attacks such as buffer overflow. Table 1 further shows whether a patching task is fully automated, needs manual input from humans to trigger an automated task (i.e., semi-automated) or fully depends on humans. In most of the instruction level patching solutions, patch deployment is followed by patch generation, which are done automatically (Inst5-chen2013safestack, ; xu2020automatic-Kernel4F-Inst2Vulmet, ; Inst1-Karmachen2017adaptive, ; Inst3-WordPatch-chamith2016living, ). We have further identified the scope of the patching. Due to variations in technology and languages, a patching solution is not universal; thus, the scope of a particular study shows if the proposed approach is for Linux, a particular language like C or a cloud system. From Table 1, we observe that most of the instruction-level patching approaches are automated and span among several systems and application domains.

Instruction-level patching is performed by either inserting new instructions or modifying existing instructions. Chen et al. (Inst6-Function5-Replus-chen2015framework, ) have considered both scenarios. In one scenario extra jump instructions are added. In another scenario, patches modify existing instructions to enable boundary condition safety checks. As shown in Table 1, a set of studies has used instruction level patching to mitigate software vulnerabilities (Inst5-chen2013safestack, ; Inst7-payer2013dynsec, ; Inst6-Function5-Replus-chen2015framework, ). For instance, Chen et al. (Inst5-chen2013safestack, ) have proposed to monitor program instructions to check stack buffer overflow attacks. Here, instead of replacing a function, the designed patch application targets the specific instructions that trigger buffer overflows. They have proposed to automate the patch process from diagnosis to applying patches at runtime without interrupting the execution of the ongoing service. The proposed approach tracks function calls, however, it does not replace the whole functions and also does not consider cross-function changes. In another study, Chen et al. proposed to perform instruction-level patching for security patches that do not modify function argument types or amount (Inst6-Function5-Replus-chen2015framework, ). Arnold et al. (Function1KspliceArnold2009, ) have also proposed to patch individual instructions, however, they mainly replace entire functions. Payer et al. (Inst7-payer2013dynsec, ; Inst7-payer2013hotAsap, ) have proposed a novel approach to combine sandbox with a runtime patching approach to maintain the integrity and availability of a system.

Similar to the above works, instruction level patching is also applied in Android OS (Inst1-Karmachen2017adaptive, ; Inst4-chen2018instaguard, ; xu2020automatic-Kernel4F-Inst2Vulmet, ) and Linux kernel (Function9-rommel2019multiverse, ). In Instaguard, Chen et al. (Inst4-chen2018instaguard, ) have considered the function name to easily locate the memory addresses that trigger vulnerability exploitation, however, they do not replace the whole function with a patched version. They considered fine-grained line-oriented changes. In KARMA (Inst1-Karmachen2017adaptive, ), the main target is to protect the integrity of the Android kernel whereas Instaguard protects the kernel from exploits originating from user space. Malicious inputs are filtered to prevent vulnerable kernel code from being exploited (Inst4-chen2018instaguard, ). In another study, Xu et al. (xu2020automatic-Kernel4F-Inst2Vulmet, ) have emphasized on automatic generation of patches and proposed an approach, namely Vulmet, that automatically generates patches for Android kernel vulnerabilities. Vulmet automatically computes necessary memory location in a function and replaces the vulnerable code with the specified patch. Instruction-level patching techniques are also used for investigating the effects of thread safety issues and analyzing the reaction and visibility of other execution threads on modifying x86 code (Inst3-WordPatch-chamith2016living, ).

Function-level patching is coarser compared to instruction-level patching as it targets patching whole functions (Function1KspliceArnold2009, ; Fucntion2-AppWrapper-lee2020your, ). For example, it replaces a buggy function with a patched one to eliminate vulnerabilities. A set of studies have proposed to perform function-level patching (Function1KspliceArnold2009, ; Fucntion2-AppWrapper-lee2020your, ; Function3-OSSPatcher-duan2019automating, ; Function4-hotpaccher-jeong2017functional, ; Inst6-Function5-Replus-chen2015framework, ; Function6-chen2007polus, ; Fucntion7-araujo2020JIT, ; Function8-Cure-zhao2016, ; Function9-rommel2019multiverse, ). Performing function-level patching requires taking cross-function dependencies into consideration. In addition, long-living functions pose further challenges, as a suitable patching time must be determined. The steps of locating the patch target address are not much different compared to instruction-level patching. Table 2 summarizes the studies related to function-level patching. It shows most of the function-level patching studies, patch generation is performed before patch deployment. Similar to instruction-level patching the scope of the studies span different domain, OS and application.

Several of the runtime patchings approaches at function-level are designed for security patches (Function1KspliceArnold2009, ; Fucntion2-AppWrapper-lee2020your, ; Function3-OSSPatcher-duan2019automating, ; Function13hu2019BINPATCH, ). For instance, Duan et al. (Function3-OSSPatcher-duan2019automating, ) have proposed OSSPatcher that automatically identifies vulnerable functions, generates binary patches and performs patch injection at runtime. Similarly, Lee et al. (Fucntion2-AppWrapper-lee2020your, ) have proposed an Appwrapper toolkit to inject additional security code on a per-method (i.e., function) basis into insecure apps enabling the use of dynamic policies to enhance overall application security. Function-level patching is also performed to replace a whole vulnerable function by linking it with a new function or replacement code into the kernel. The proposed method is considered very useful for large server environments that are highly utilized by multiple users (Function1KspliceArnold2009, ). Research is also seen in patching vulnerabilities of binary programs via code transfer and binary rewriting in functions (Function13hu2019BINPATCH, ). Table 2 shows most of the function level patching is performed automatically without user intervention.

Existing works on patching kernel at runtime rely on the host Kernel and consider the Kernel to be always trusted. However, Zhou et al. (Function7Kshot, ) have emphasized the fact that Kernel can be malicious and untrusted. Thus, they have proposed a reliable kernel runtime patching framework (albeit at function granularity) leveraging Trusted Execution Environments (TEE) that is hardware-assisted to prepare and deploy kernel patches. The proposed approach Kshot, prepares and deploys patches that do not need a trustworthy kernel patching mechanism (Function7Kshot, ).

Considering the limited capacity of the embedded devices (e.g., lack of update functionality), Salls et al. (Function10-salls2017piston, ) have proposed an approach, Piston, to perform remote patching on embedded devices. Piston mainly performs patching at the function level. It is designed to force patches onto a vulnerable system by exploiting the vulnerabilities and taking control of the vulnerable process. For some vulnerabilities like stack-based buffer overflows, it supports automated patching whereas for others it is semi-automated and requires input from the analyst. Similarly, Rucjerbusch et al. (Functiona12ruckebusch2016gitar, ) have proposed a tool Gitar to enable runtime patching of applications in OSes running on IoT, M2M and resource-constrained devices. Table 2 shows that function-level runtime patching approaches are also adopted to perform dynamic variability in software systems (Function9-rommel2019multiverse, ; function11rothberg2016CompMultiverse, ). Most of these approaches are compiler assisted and implement a function multiverse in the compiler to perform binary patching.

Function-level patching is noticed to perform runtime patching at the production level, especially for C program  (Inst6-Function5-Replus-chen2015framework, ). The authors have proposed a framework, Replus, to build environment-aware patches by separating the responsibilities of developers and customers where patch generation is performed in the developer environment and deploying or applying the patch is performed in a customer environment. The main focus of Replus is to provide a practical and efficient runtime patching system that does not need compiler support. Different from Replus, Orso et al.(Function10-Orso2002DUSC, ) have proposed a tool, DUSC, to perform runtime patching in Java-based applications.

Process-level patching aims to replace the whole process with a new one that contains a fixed or updated functionality (Process1-mugarza2020cetratus, ; Process3-giuffrida2013safe-Proteos, ; Process8-hayden2012kitsune, ; Process7-ramaswamy2010katana, ). In contrast to function-level patching, updating the whole process might be easier in some cases as only OS dependencies and resources need to be tracked. For instance, files and network sockets need to be detached from the old process and transferred to the new process (Process4-rommel2019waitFree, ). The main complication in this area is maintaining the internal resource states such as current file pointers and network protocol states. Table 3 shows the key studies that have considered runtime patching at the process level. Among the existing studies, Rommel et al.  (Process4-rommel2019waitFree, ) have proposed to move individual threads to new address space through predefined quiescent states. The proposed approach attempts to minimize waiting time by preparing the clone of the address space as opposed to the stop-the-world approach.

As shown in Table 3, we observe that most of the process-level patching solutions are semi-automated; hence, actual patch deployment requires human assistance. Process-level patching studies focus mainly on patch deployment rather than patch generation. The scope of the process-level patching solution typically targets a specific OS or programming language. A common way to achieve process-level patching is the usage of multi-version execution techniques (Process8-hayden2012kitsune, ; Process8-hayden2014kitsune, ). Both update-safe points and corresponding data transformation functions must be predefined by the developers to make runtime updating possible. One of the proposed approaches, Kitsune (Process8-hayden2012kitsune, ; Process8-hayden2014kitsune, ), implements single- and multi-threaded C-based application updating. The authors propose a novel tool to assist software developers in generating state transformation and transfer routines. Some light annotation is, however, still required from the developers. MVEDSUA (Process5-pina2019mvedsua, ) is an extension of Kitsune (Process8-hayden2012kitsune, ) with the use of N-version execution framework Varan³³3Varan (hosek2015varan, ), is a rich framework in terms of applicability and is particularly useful for software updating purposes. The initial motivation behind the proposed approach is to run multiple copies of the same code with various modifications to minimize potential vulnerability risks. For instance, transparent failover can be achieved if only one of the copies is exploited. In the context of software updating, the same principle can be used to detect behavior deviations caused by the updated code as, for example, done in (Process5-pina2019mvedsua, ). (hosek2015varan, ). The key insight behind MVEDSUA is the ability to patch a second copy of the code, which runs simultaneously with the original code. Subsequent checks of old and new code behavior make it possible to verify and roll back broken patches if any discrepancies are detected. This approach requires operator assistance to define the potentially expected behavior discrepancies explicitly.

Several of the process-level patching approaches focus on the security and safety of the system after applying patches (Process1-mugarza2020cetratus, ; Process3-giuffrida2013safe-Proteos, ; pina2016tedsuto, ). For instance, Giuffirida et al.(Process3-giuffrida2013safe-Proteos, ) have focused on safe and predictable updates of OS states. The proposed solution, Proteos, performs transactional live updates at the process level and requires programmer-provided state filters to limit updates to certain points in time only. Similarly, research is noticed on the consideration of the safety and security of a system while deploying patches (Process1-mugarza2020cetratus, ) where a tool, Cetratus, is proposed for performing and verifying runtime patches in safety-critical systems. Pita et al. (pina2016tedsuto, ) have proposed TEDSUTO, which is focused specifically on patch verification steps. Old and new code behaviors are systematically tested, and discrepancies are identified as potential patch-related errors. This approach enables safe patch testing prior to applying it in a production environment. Similar to MVEDSUA (Process5-pina2019mvedsua, ), intended behavior changes must be explicitly annotated by developers.

Ramaswamy et al. have proposed Katana (Process7-ramaswamy2010katana, ) which attempts to generate patches from source changes and safely apply them at run time. An interesting feature of the proposed solution is automatic safe update point detection. Specifically, the process execution stack is constantly monitored for this purpose, with suitable execution points being deduced on the fly. Stop-the-world technique is applied when a safe update point is encountered to replace the old code with the patched version. Authors, however, admit that their approach does not guarantee time bounds as a suitable execution point may not necessarily be reachable. Similar to Katana (Process7-ramaswamy2010katana, ), Neamtiu proposed a tool, Ginseng (Process9-neamtiu2006Ginseng, ), that aims to integrate patch generation and deployment steps together. Function indirection and type wrapper are the key techniques used by Ginseng. Additional annotations are required from the developers to define safe update points.

Different from existing approaches, Bierman et al. (Function14-bierman2003UpdateCalculus, ) have focused on formal foundation and conceptual reasoning about safe updating. Namely, an update calculus is proposed to enable formal reasoning about various code properties such as type safety or semantic correctness. Having a strong theoretical focus, this work does not tackle technical implementation-related issues such as specific programming languages or OS.

Containerization is an emerging technology that has become widely popular in distributed computing applications. With the increasing adoption, various attacks, vulnerabilities and security challenges are noticed in distributed computing environments such as data centers and the cloud. Patching vulnerabilities in the container is not straightforward (Container1-Opatch-tunde2020, ; Container2-tunde2020selfPatch, ; Container3-sun2020blockchain, ; Container4-ayres2021continuous, ). Existing patching techniques often are not suitable for containers due to their short life and ephemeral nature (Container1-Opatch-tunde2020, ; Container2-tunde2020selfPatch, ). Tunde-Onadele et al. have proposed lightweight on-demand patching techniques to patch containerized applications at runtime (Container1-Opatch-tunde2020, ; Container2-tunde2020selfPatch, ) considering the resource constraints. Research in container-level patching techniques is noticed to enhance cloud security where blockchain-based integrity checkers are proposed to detect vulnerabilities in container images (Container3-sun2020blockchain, ). The proposed approach further aids in generating and dynamically replacing vulnerable instances.

Recent studies have leveraged container virtualization and lightweight features to perform runtime patching in the automotive domain. For example, Ayres et al. (Container4-ayres2021continuous, ) have proposed to utilize the virtualization features of container technology in the Electronic Control Unit (ECU) of automotive vehicles to perform patching at runtime. The proposed approach is suitable for automotive functions which do not involve vehicle operation or safety and is instead focused on patching software related to autonomous driving or subsystems such as climate control. Table 4 shows that most of the container-level patching approaches are focused on automatically patching vulnerabilities, bugs or errors. Therefore, deploying patching at runtime is the main task of the studies categorized in container-level patching. However, the studies span server systems, container image security and automotive software. Table 4 further summarizes the studies that proposed approaches for VM, Hypervisor and Kernel level patching.

VM-level patching granularity is conceptually similar to process-level, with the main difference relating to technical aspects. For instance, while replacing an existing process requires interacting with the OS, replacing a virtual machine would require interacting with the virtualization hypervisor⁴⁴4Hypervisors support the creation and running of VMs, which is also known as Virtual Machine Monitor (VMM).. We find only a few studies where a patch is performed at VM-level (VM1-le2014shadowPatching, ; VM2-zhang2014vpatcher, ). Table 4 shows that VM-level studies mainly perform patch deployment automatically to patch vulnerabilities in cloud systems and data centers. Among them, Le et al. (VM1-le2014shadowPatching, ) have proposed a shadow patching technique to reduce the downtime caused by patching VM running on the managed environment such as data centers. First, the proposed approach creates a replica of the VM that needs to be patched. Then, it deploys the patches in the replica VM, performs testing and makes necessary changes before applying the patch to the original VM. Finally, when the patches are applied to the original VM, the running application and data are merged from the replica VM to the original VM. This last step is similar to the VM teleport technique where current workloads are seamlessly transferred to the new VM instance⁵⁵5https://docs.oracle.com/en/virtualization/virtualbox/6.0/admin/teleporting.html.

Different from the shadow patching approach, Zhang et al. (VM2-zhang2014vpatcher, ) have utilized VM introspective capabilities to monitor the behavior of VM using hypervisors to perform patching at runtime. Furthermore, they aim to perform data patching transparently in VM using hypervisor assistance. The proposed approach, vPatcher, is deployed outside the target guest VM to intercept and scan VM network traffic based on a vulnerability signature. This allows to filter out the network connections based on the vulnerability signatures.

By hypervisor-level runtime patching, we consider studies that aim to replace the whole virtualization hypervisor without or minimally affecting the underlying virtual machines. Patching a hypervisor involves changing a large amount of dynamic data structures and is significantly complicated by the necessity to keep multiple underlying guest kernels intact and in sync with the hardware state. We observe a set of studies where hypervisors are patched at runtime without disrupting the running VMs (hypervisor1-hyperFresh-doddamani2019, ; hypervisor2-Orthus-zhang2019fast, ). Table 4 shows that hypervisor-level runtime patching is commonly applied to patch vulnerable cloud infrastructure without human involvement which mainly occurs in cloud and data center environments. In contrast to VM migration, hypervisor or VMM (Virtual Machine Manager) patching is typically performed in the same physical node and does not introduce significant network traffic. Thus, replacing or patching a hypervisor achieves better performance and lower downtime than VM live migration.

One technique to patch hypervisor at runtime is to copy the whole state of all active VMs from the running hypervisor to a new hypervisor (upgraded) (hypervisor2-Orthus-zhang2019fast, ). The proposed techniques aim to seamlessly pass through devices to the new hypervisor automatically without losing any ongoing activities or operations state. Similarly, Doddamani et al. (hypervisor1-hyperFresh-doddamani2019, ) have proposed to transparently replace a hypervisor with a new one without disrupting or shutting down the VMs. The proposed approach, namely HyperFresh, introduces an intermediate layer to perform live hypervisor replacement. This layer maps the memory of the running VMs to the new locations belonging to the new hypervisor located in the same physical machine. These approaches focus on patching vulnerabilities and adding new features of cloud systems without interrupting the running VMs or shutting down the serves. While technically complicated, hypervisor-level patching is crucial in large commercial cloud deployments. Table 4 also shows that the studies on Hypervisor-level patching are mainly focused on deploying patches at runtime for patching vulnerabilities or updating features at cloud systems and data centers.

We consider the patching solutions where a whole kernel is switched to a new kernel to apply all kinds of patches without having to restart the kernel (Kernel1Kup, ) as Kernel-level runtime patching. We noticed a few studies (Kernel1Kup, ; Kernel3Seamless, ; kernel3Crui, ) that have performed runtime patching at kernel-level. Kernel-level patching is executed through the use of kernel space and user space checkpoint and restart mechanism (Kernel1Kup, ; Kernel3Seamless, ; kernel3Crui, ). Table 4 also shows that few studies have proposed to replace the whole Kernel while patching at runtime. Unsurprisingly, from Table 4 we can see that the kernel-oriented solutions mainly target Linux, most likely due to the source code availability. The goal of these studies includes patching vulnerabilities, fixing bugs, updating features and upgrading an entire kernel.

In place kernel switch is a popular technique to update OS that heavily modifies various subcomponents of the kernel (Kernel3Seamless, ). The proposed approach mainly targets restoring the applications entirely in kernel space. After applying patches to the Kernel, it is essential to ensure that the changes do not break or corrupt the existing functionalities and applications. Thus, the testing process of kernel-level patching is costly and tedious (xu2020automatic-Kernel4F-Inst2Vulmet, ). Kashyap et al. (Kernel1Kup, ) have proposed to perform runtime kernel patching without modifying the kernel source code. They have adopted binary patching techniques, userspace checkpoint and restore, and optimized in-place Kernel switching to perform the kernel patching. Alternatively, in order to simplify kernel updating, resource (such as running processes and containers) handover assistance can be utilized (kernel3Crui, ). For instance, a widely used tool, CRIU⁶⁶6https://www.criu.org/Main_Page makes it possible to freeze critical processes, replace the whole old Kernel with a patched/new version and restore the frozen processes. While CRIU was initially designed for live container migration, further project development has enabled the runtime kernel upgrading scenario.

In summary, we observe that function-level patching techniques are widely proposed in the literature, followed by instruction-level and process-level patching. The key reason we notice is the granularity of the patch; with function and instruction level patching, there require more minor changes in the resources as shown in Figure 3. On the other hand, we notice little research in patching heavy loaded resources such as VM, container, hypervisor and Kernel due to the complexity and dependency of the resources and tasks with other resources.

The analysis of existing runtime patching approaches reveals two main patch deployment strategies (i) State transformation and (ii) Co-exist & decay. These patch strategies refer to the conceptual models underpinning the patch handling steps. Here, we discuss the general goals and trade-offs of the identified patching strategies.

Deploying or applying a patch at runtime consists of several preparatory steps followed by actual patch code activation steps. The preparatory steps of patch deployment are common for all patch approaches, while patch activation steps depend on the employed/ selected strategy (i.e., state transformation and co-exist $\&$ decay). As can be seen from Figure 5, allocating memory, loading patch into RAM and configuring patch are common steps. Supported software environments such as OS, programming language and machine architecture greatly affect how each of these steps are implemented by a given patching solution (Function7Kshot, ; Inst5-chen2013safestack, ; xu2020automatic-Kernel4F-Inst2Vulmet, ; Container1-Opatch-tunde2020, ). Note that Figure 5 outlines the conceptual steps that do not depend on the particular granularity chosen. The outlined steps need to be taken regardless of the granularity selected; however, the actual implementation may differ. The type of resources to transform or dispatch depends on the patch granularity and nature (Figure 3). For instance, patching a whole VM compared to patching an individual instruction typically requires transforming more resources (e.g., network sockets, file handles, hypervisor objects, etc.).

Allocating memory to accommodate the patched code in RAM is a necessary step for all solutions except those that perform limited instruction overwriting in-place (such as (Inst3-WordPatch-chamith2016living, )). Loading the patched code into RAM is necessary regardless of the technical differences in the implementation. Lastly, configuration of a patch may include sub-tasks such as decompression, decryption or digital signature verification than just copying patch bytes into memory. These sub tasks are optional and mainly implemented to increase performance or reliability. In some cases, the three preparatory steps may become completely unnecessary, complicated, impossible or require external intervention. For example, resource-limited embedded IoT devices may not have enough unused memory to fit the patched code into RAM, leading to the necessity to completely erase and re-flash the device through external means/devices.

Figure 5 shows further steps of patch activation that depend on the general patching strategy employed. In efforts to minimize any potential system or service downtime, runtime patching solutions typically attempt to perform as many tasks as possible prior to activation of the patched code. For instance, concurrent state transformation may occur with execution of old code wherever possible. As a consequence, once the quiescent state is reached, the number of actual code activation steps would be reduced and thus take less time to complete. The patch code activation step is time-critical as the patch latency period between code execution pausing and resuming should be kept minimal. Thus, only critical state transformation (that were not possible outside of quiescent state) should be conducted while the code execution is paused. While not having issues with quiescence, the patch enabling step in dispatcher used by coexist & decay (as shown in Figure 5) must deal with non-instantaneous patch activation instead.

In both cases, the potential downside is that the old (potentially vulnerable) code would operate for some time, while the preparatory steps are taken, the quiescent state is not yet reached or new interaction starts. Having the vulnerable code still active, might pose a significant security risk for large-scale patches (i.e., VM- or kernel-sized), leading to the necessity to completely stop any system operation temporarily. The overall state transformation can then be performed in a safe manner. Such execution suspension would essentially be equivalent to traditional offline patching in terms of user experience disruption.

Several generic capabilities implemented by existing patching systems have been identified throughout this study. In line with the presented patching workflow of Figure 5, we identify four main capabilities (see Fig 2) - (i) memory management, (ii) resource transformation, (iii) safe execution state determination and (iv) execution path dispatching. The implementation details of the runtime patching systems exhibit these capabilities differently in the sense of limited applicability to certain use cases. For instance, in most of the reviewed solutions, these capabilities are limited to specific programming languages, OS-es and environments. Table 5 summarizes an overview of the patch implementation capabilities of different patch approaches along with execution or operational environment. It also shows the advantages or quality requirements promised to be fulfilled by a particular study.

In vendor-assisted patching scenarios, the software is designed with runtime patching support in mind, with end-users having little to no involvement in the patching process (Function9-rommel2019multiverse, ; function11rothberg2016CompMultiverse, ; ruckebusch2016gitar, ; Process1-mugarza2020cetratus, ). With modern software commonly enabling automated patching by default, users at most have an option to apply or skip a given patch. Original software vendors have deep knowledge of how the software operates, which (in principle) enables developing complex and safe patches. Also, having access to the software sources opens up several avenues not available for end-users or third parties in closed-source software. For instance, runtime patches could be automatically generated based on the source code changes conducted by the software developers. Having control over software development, deployment and further management enables designing tightly integrated patching solutions (Process3-giuffrida2013safe-Proteos, ). Patches can be developed, delivered to end-users and automatically deployed by the vendor as shown in Figure 7(a), which significantly reduces the burden of management on the end-users.

Two potential downsides of vendor-assisted patching are low applicability for legacy systems and lack of flexibility from an end-user perspective. Legacy systems lacking a run-time patching subsystem would fall victim to potential vulnerabilities. Completely redesigning such legacy systems might be prohibitively expensive or impractical. End users would also be entirely dependent on the willingness of the software vendors to fix a given issue. Lower priority or site-specific problems may not receive enough attention from the developers, causing a lack of patches addressing some of the end-user needs.

In some cases, software consumers may opt to manage patch deployment for the software they use, which we refer to as consumer-assisted patching. Three possible reasons include a higher level of control, more flexibility and lack of support from the original software vendor. At the expense of increased labor required, implementing own patching strategy essentially allows end-users to gain a higher level of control over the software system as shown in Figure 7(b). Consequently, fine-grained or user-specific patches can be deployed by the consumers based on their current and ever-changing requirements (Function10-salls2017piston, ; Process8-hayden2012kitsune, ; Process8-hayden2014kitsune, ). Also, implementing own patching solutions may be the only option for legacy systems that do not include runtime patching support or are no longer maintained.

However, achieving the desired flexibility may not be easy for the end-users as they lack intimate knowledge of data structures and flow used within the software. Due to the complexities in foreseeing the potential side-effects of the patch-induced changes, applying potentially inconsistent/faulty patches poses significant risks. The complexity of predicting potential patch failures or discrepancies is higher for closed-source software while being somewhat more manageable for fully open-source software. In a subset of situations, end-users might limit their efforts to converting traditional source- or binary-level patches into a dynamic form rather than developing their patches from scratch. In other words, end-users might focus on developing a runtime patching system to deploy the traditional vendor-produced offline patches in a dynamic manner.

Third-party runtime patching systems refer to solutions that are applicable in a wider set of software environments and represent a practical trade-off between vendor and consumer efforts. Not possessing the knowledge of inner software details and lacking information on individual end-user needs, third parties aim to achieve some level of generality in terms of applicability in different contexts such as specific programming languages, OS or certain patch granularity. For instance, some solutions support solely Java- or C-based applications (Function10-Orso2002DUSC, ; Inst7-payer2013hotAsap, ; Process8-hayden2014kitsune, ), while others focus on specific OS environments (Process3-giuffrida2013safe-Proteos, ; Inst4-chen2018instaguard, ).

The third-party-assisted patching approaches do not expect assistance from the old code while still simplifying patch deployment. One common theme within third-party efforts is to focus on converting existing source-based vendor-developed offline patches to be applied at run time by end-users. For this purpose, third-party-assisted software updating implements an external entity that would replace old code with the new code while preventing potential service interruptions. For instance, the proposed approach by Chen et al. (Inst5-chen2013safestack, ) requires the installation of a runtime patch applicator in the online production system. Figure 7(c) shows a high-level overview of third-party-assisted patching. Most of the research efforts we have studied are geared towards third-party assisted patching (xu2020automatic-Kernel4F-Inst2Vulmet, ; Inst4-chen2018instaguard, ; Fucntion2-AppWrapper-lee2020your, ; Function3-OSSPatcher-duan2019automating, ; Function6-chen2007polus, ; Function8-Cure-zhao2016, ; Process6-pina2016tedsuto, ; hypervisor2-Orthus-zhang2019fast, ; Container2-tunde2020selfPatch, ; Kernel1Kup, ).

Compatibility between in-flight activities and updated code needs to be maintained to ensure user experience continuity. Patches that introduce significant externally observable changes may lead to incompatibilities with the expectation of external observers. Therefore one of the tasks of a run-time patching system is to achieve code and data compatibility or, at the very least, detect potential incompatibilities prior to patch deployment. Dealing with potential incompatibilities between original and patched code requires determining the scope (i.e., how far are the patch effects observable) and type (i.e., what becomes incompatible) of the incompatibility. For instance, the patch application might be stopped entirely or postponed if certain incompatibilities are detected. Detecting the most disruptive patches can aid in reducing the associated downtime and service interruptions. Considering the mentioned issues of behavior change compatibility, we further discuss the future research directions potentially valuable for solving different aspects of such issues between original and patched code.

In addition to the technical implementation issues, runtime patching overheads must be addressed. These overheads are mainly concentrated in resource (e.g., RAM) and time domains. Coexisting-based solutions imply that multiple copies of code or data must simultaneously be present in memory. Such coexistence might not be an issue for smaller patches; however, applying multiple patches over longer periods may eventually pose challenges. Similarly, resource-constrained IoT devices may also render some solutions impractical due to a lack of hardware resources. For instance, some microchips based on Harvard architecture may not allow direct code modification, leading to the necessity to re-flash main memory contents and restart the execution. Note that, even in such restricted devices, certain extensions have been implemented to aid self-modification that would be useful for patching purposes¹⁹¹⁹19http://ww1.microchip.com/downloads/en/AppNotes/doc1644.pdf. Architecture-, device- and resource-constrained overheads need to be predicted to determine patch suitability for a given system real-time requirement. We identify and discuss the associated quantitative metric research directions below.

In addition to purely technical issues related to runtime patching, several socio-technical aspects may pose additional complications. For instance, delays due to imposing internal policies or legislation may significantly slow down the patching procedures. Organizations may consider improving software development practices that incorporate runtime patching at the design phase. However, the monetary and time costs associated with rewriting large legacy software packages according to improved development practices may drive off software developers. Furthermore, in some cases, extra complications in patching processes may be induced by supply chain participants (such as mobile service providers or hardware vendors) for the purposes of patch verification or secure distribution. We identify some potentially beneficial research directions to solve socio-technical challenges hindering wider adoption of runtime patching.