Content deleted Content added
→Related fields: Meh, missed that |
m Disambiguating links to SUSE (link changed to SUSE S.A.) using DisamAssist. |
||
| (45 intermediate revisions by 30 users not shown) | |||
Line 1:
{{Short description|Field of research in computer science}}
In [[computer science]], '''dynamic software updating''' ('''DSU''') is a field of research pertaining to [[upgrade|upgrading]] programs while they are running. DSU is not currently widely used in industry. However, researchers have developed a wide variety of systems and techniques for implementing DSU. These systems are commonly tested on real-world programs.
Line 4 ⟶ 5:
== Introduction ==
Any running program can be thought of a [[tuple]] <math>(\delta, P)</math>, where <math>\delta</math> is the current program state and <math>P</math> is the current program code. Dynamic software updating systems transform a running program <math>(\delta, P)</math> to a new version <math>(\delta', P')</math>. In order to do this, the state must be transformed into the representation <math>P'</math> expects. This requires a ''state transformer'' function. Thus, DSU transforms a program <math>(\delta, P)</math> to <math>(S (\delta), P')</math>. An update is considered '''valid''' if and only if the running program <math>(S (\delta), P')</math> can be reduced to a point tuple <math>(\delta, P')</math> that is reachable from the starting point of the new version of the program, {{nobr|1=<math>(\delta_{init}, P')</math>.<ref name="gupta">{{cite journal
| author-last1 = Gupta | author-first1 = Deepak
| author-last2 = Jalote | author-first2 = Pankaj
| author-last3 = Barua | author-first3 = Gautam
| title = A Formal Framework for On-line Software Version Change
| journal = IEEE Transactions on Software Engineering
| volume = 22 | number = 2 | pages = 120–131
| url = http://www.win.tue.nl/~hmei/SoftwareUpdate/A%20formal%20framework%20for%20on-line%20software%20version%20change.pdf
| archive-url = https://web.archive.org/web/20140407175809/http://www.win.tue.nl/~hmei/SoftwareUpdate/A%20formal%20framework%20for%20on-line%20software%20version%20change.pdf
| archive-date = 2014-04-07
| url-status = dead
| year = 1996 | doi = 10.1109/32.485222
}}</ref>}}
The ___location in a program where a dynamic update occurs is referred to as an '''update point'''. Existing DSU implementations vary widely in their treatment of update points. In some systems, such as [[#UpStare|UpStare]] and [[#PoLUS|PoLUS]], an update can occur at any time during execution. [[#Ginseng|Ginseng]]'s compiler will attempt to infer good locations for update points, but can also use programmer-specified update points. [[#Kitsune and Ekiden|Kitsune and Ekiden]] require developers to manually specify and name all update points.
Line 18 ⟶ 30:
The problem space addressed by dynamic updating can be thought of as an intersection of several others. Examples include [[checkpointing]], [[dynamic linking]], and [[Persistence (computer science)|persistence]]. As an example, a database that must be [[backward-compatible]] with previous versions of its on-disk file format, must accomplish the same type of state transformation expected of a dynamic updating system. Likewise, a program that has a plugin architecture, must be able to load and execute new code at runtime.
Similar techniques are sometimes also employed for the purpose of [[dynamic dead-code elimination]] to remove conditionally [[dead code|dead]] or [[unreachable code]] at load or runtime, and recombine the remaining code to minimize its [[memory footprint]] or improve speed.<ref name="Paul_1997_FreeKEYB">{{
| title = FreeKEYB - Enhanced DOS keyboard and console driver | edition = v6.5 | author-first1 = Matthias R. | author-last1 = | author-first2 = Axel C. | author-last2 = | type = User Manual | date = 1997-10-13 | orig-year = first published 1991 }} [https://web.archive.org/web/20190309194320/http://sta.c64.org/dosprg/fk657p1.zip<!-- FreeKEYB 6.57p1 Beta as of 2004-08-17 with outdated and incomplete documentation -->] (NB. The K3PLUS successor FreeKEYB is a fully reconfigurable driver with many dynamically loadable special features. It implements a unique form of byte-level granular [[dynamic dead code elimination]] and [[relocation (computing)|relocation]] techniques at [[load-time]] as well as [[self-modifying code]] and reconfigurability at [[runtime (computing)|run-time]] to minimize its memory footprint close to the [[canonical form]] depending on the hardware, operating system, other environment and driver configuration as well as the selected feature set and locale (about sixty configuration switches with hundreds of options for an almost unlimited number of possible combinations). The build process utilizes a [[macro assembler]] as well as a framework of automatic pre- and post-processing tools analyzing the temporary binaries to generate dependency and [[code morphing]] [[meta data]] to be embedded into the resulting [[executable file]] alongside the [[binary code]] and a self-discarding, [[instruction relaxation|relaxing]] and [[relocating loader]] to dynamically (re)combine, (over)load, modify, update or unload the runtime image (code and data) of the driver as requested. The complexity is hidden in a single self-contained file so that for a user the handling is the same as for a normal (semi-)monolithic driver/[[ | title = FreeKEYB - Advanced international DOS keyboard and console driver | | author-first1 = Matthias R. | author-last1 = Paul
| author-first2 = Axel C. | author-last2 = Frinke
| type = User Manual
| date = 2006-01-16
}}</ref>
== History ==
The earliest precursor to dynamic software updating is [[Redundancy (engineering)|redundant systems]]. In a redundant environment, spare systems exist ready to take control of active computations in the event of a failure of the main system. These systems contain a main machine and a ''hot spare''. The hot spare would be periodically seeded with a [[Application checkpointing|checkpoint]] of the primary system. In the event of a failure, the hot spare would take over, and the main machine would become the new hot spare. This pattern can be generalized to updating. In the event of an update, the hot spare would activate, the main system would update, and then the updated system would resume control.
The earliest true Dynamic Software Updating system is [[#DYMOS|DYMOS]] (''Dy''namic ''Mo''dification ''S''ystem).<ref name="dymos">{{cite thesis
| author-first = Insup | author-last = | title = Dymos: a dynamic modification system | degree = Doctor of Philosophy (Computer Science) | year = 1983 | publisher = University of Wisconsin - Madison | url = http://www.cis.upenn.edu/~lee/mydissertation.doc | | | }}</ref> Presented in 1983 in the PhD dissertation of Insup Lee, DYMOS was a fully integrated system that had access to an interactive user interface, a compiler and runtime for a [[Modula]] variant, and source code. This enabled DYMOS to type-check updates against the existing program. ==Implementation==
DSU systems must load new code into a running program, and transform existing state into a format that is understood by the new code. Since many motivational use-cases of DSU are time-critical (for example, deploying a security fix on a live and vulnerable system), DSU systems must provide adequate '''update availability'''. Some DSU systems also attempt to ensure that updates are safe before applying them.
There is no one canonical solution to any of these problems. Typically, a DSU system that performs well in one problem area does so at a trade-off to others. For example, empirical testing of dynamic updates indicates that increasing the number of update points results in an increased number of unsafe updates.<ref name="testing">{{cite journal
|title = Evaluating dynamic software update safety using systematic testing |author-first1 = |author-last1 = |author-first2 = Edward K. |author-last2 = |author-first3 = |author-last3 = |author-first4 = Michael |author-last4 |author-first5 = Jeffery
|author-last5 = Foster
|year = 2011
|journal = IEEE Transactions on Software Engineering
|issue = 99
|publisher = IEEE
|url = http://www.cs.umd.edu/~hayden/papers/empiricalsafety-draft.pdf
}}{{dead link|date=September 2017 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
== Code transformation ==
Most DSU systems use [[subroutine]]s as the unit of code for updates; however, newer DSU systems implement whole-program updates.<ref name="ekiden">{{cite journal
| author-first1 = Chris | author-last1 = Hayden
| author-first2 = Edward K. | author-last2 = Smith
| author-first3 = Michael | author-last3 = Hicks
| author-first4 = Jeffery | author-last4 = Foster
| journal = Data Engineering Workshops (ICDEW), 2011 IEEE 27th International Conference on
| pages = 179–184 | publisher = IEEE
| url = http://www.cs.umd.edu/~jfoster/papers/hotswup11.pdf
| year = 2011
| title = State transfer for clear and efficient runtime updates
}}</ref><ref name="kitsune">{{cite journal
| author-last1 = Hayden | author-first1 = Chris
| author-last2 = Smith | author-first2 = Edward K.
| author-first3 = Michail | author-last3 = Denchev
| author-first4 = Michael | author-last4 = Hicks
| author-first5 = Jeffery | author-last5 = Foster
| year = 2011
| title = Kitsune: Efficient, General-purpose Dynamic Software Updating for C
| url = http://www.cs.umd.edu/~mwh/papers/kitsune.pdf
}}</ref>
If the target program is implemented in a [[virtual machine]] language, the VM can use existing infrastructure to load new code, since modern virtual machines support runtime loading for other use cases besides DSU (mainly [[debugging]]). The [[HotSpot (virtual machine)|HotSpot]] [[JVM]] supports runtime code loading, and DSU systems targeting [[Java (programming language)]] can utilize this feature.
In native languages such as [[C (programming language)|C]] or [[C++]], DSU systems can use specialized compilers that insert indirection into the program. At update time, this indirection is updated to point to the newest version. If a DSU system does not use a compiler to insert these indirections statically, it insert them at runtime with [[binary rewriting]]. Binary rewriting is the process of writing low-level code into the memory image of a running native program to re-direct functions. While this requires no static analysis of a program, it is highly platform-dependent.
Line 51 ⟶ 122:
Type safety is typically checked by showing one of two properties, '''activeness safety''' or '''cons-freeness safety'''. A program is considered activeness-safe if no updated function exists on the [[call stack]] at update time. This proves safety because control can never return to old code that would access new representations of data.
''Cons-Freeness'' is another way to prove type safety, where a section of code is considered safe if it does not access state of a given type in a way that requires knowledge of the type representation. This code can be said to not access the state ''concretely'', while it may access the state ''abstractly''. It is possible to prove or disprove ''cons-freeness'' for all types in any section of code, and the DSU system Ginseng uses this to prove type safety.<ref name="cons-freeness">{{cite journal
| title = Mutatis mutandis: Safe and predictable dynamic software updating
| author-first1 = Gareth | author-last1 = Stoyle
| author-first2 = Michael | author-last2 = Hicks
| author-first3 = Gavin | author-last3 = Bierman
| author-first4 = Peter | author-last4 = Sewall
| author-first5 = Iulian | author-last5 = Neamtiu
| year = 2005
| journal = Proceedings of the ACM Conference on Principles of Programming Languages
| url = http://www.cs.umd.edu/~mwh/papers/proteus-popl.pdf
}}</ref><ref name="ginseng">{{cite journal
| title = Practical dynamic software updating for C
| author-first1 = Iulian | author-last1 = Neamtiu
| author-first2 = Michael | author-last2 = Hicks
| author-first3 = Gareth | author-last3 = Stoyle
| author-first4 = Manuel | author-last4 = Oriol
| journal = ACM SIGPLAN Notices
| volume = 41 | issue = 6 | pages = 72–83
| url = http://www.cs.umd.edu/~mwh/papers/ginseng.pdf
| doi = 10.1145/1133255.1133991
| year = 2006 | citeseerx = 10.1.1.625.4663 }}</ref> If a function is proven ''cons-free'', it can be updated even if it is live on the stack, since it will not cause a type error by accessing state using the old representation.
Empirical analysis of ''cons-freeness'' and activeness safety by Hayden et
==Existing systems==
Line 61 ⟶ 152:
=== {{Anchor|STACKTOOL}}Ksplice, kpatch and kGraft ===
{{Category see also|Linux kernel live patching}}
[[Ksplice]] is a DSU system that targets only the [[Linux kernel]], making itself one of the specialized DSU systems that support an [[operating system kernel]] as the target program. Ksplice uses source-level [[diff]]s to determine changes between current and updated versions of the Linux kernel, and then uses binary rewriting to insert the changes into the running kernel.<ref name="ksplice">{{cite book
| author-first1 = Jeff | author-last1 = Arnold
| author-first2 = M. Frans | author-last2 = Kaashoek | author-link2 = Frans Kaashoek
| title = Proceedings of the 4th ACM European conference on Computer systems
| chapter = Ksplice: automatic rebootless kernel updates
| year = 2009
| pages = 187–198 | doi = 10.1145/1519065.1519085
| hdl = 1721.1/51698 | url = https://www.ksplice.com/doc/ksplice.pdf
| isbn = 9781605584829 | s2cid = 7720018 }}</ref> Ksplice was maintained by a commercial venture founded by its original authors, Ksplice Inc., which was acquired by [[Oracle Corporation]] in July 2011.<ref>{{cite news
| url = http://www.oracle.com/us/corporate/Acquisitions/ksplice/index.html
| title = Oracle and Ksplice
| accessdate = 2011-07-21
}}</ref> Ksplice is used on a commercial basis and exclusively in the [[Oracle Linux]] distribution.<ref>{{cite web
| url = https://oss.oracle.com/ksplice/docs/GettingStarted.html
| title = Getting Started with Oracle Ksplice
| website = oracle.com
| accessdate = 2014-08-02
}}</ref>
[[SUSE S.A.|SUSE]] developed [[kGraft]] as an open-source alternative for live kernel patching, and [[Red Hat]] did likewise with [[kpatch]]. They both allow function-level changes to be applied to a running Linux kernel, while relying on live patching mechanisms established by [[ftrace]]. The primary difference between kGraft and kpatch is the way they ensure runtime consistency of the updated code sections while [[hot
| url = https://lwn.net/Articles/597123/ | title = kpatch: dynamic kernel patching | date = 2014-05-01 | | author-first = Josh | author-last = | publisher = [[LWN.net]] }}</ref><ref>{{cite web | url = https://lwn.net/Articles/596854/ | title = The initial kGraft submission | | author-first = Jonathan | author-last = Corbet
| publisher = [[LWN.net]]
}}</ref> and the minimalistic foundations for live patching were merged into the Linux kernel mainline in kernel version 4.0, which was released on April 12, 2015.<ref>{{cite web
| url = http://kernelnewbies.org/Linux_4.0#head-9aa7c8499b42911a48c02b24f367bf2bc6db8606
| title = Linux kernel 4.0, Section 1.2. Live patching
| date = 2015-04-26 | accessdate = 2015-05-14
| website = kernelnewbies.org
}}</ref>
Since April 2015, there is ongoing work on porting kpatch and kGraft to the common live patching core provided by the Linux kernel mainline. However, implementation of the function-level consistency mechanisms, required for safe transitions between the original and patched versions of functions, has been delayed because the [[call stack]]s provided by the Linux kernel may be unreliable in situations that involve [[assembly code]] without proper [[stack frame]]s; as a result, the porting work remains in progress {{As of|2015|9|lc=yes}}. In an attempt to improve the reliability of kernel's call stacks, a specialized sanity-check {{Mono|stacktool}} userspace utility has also been developed with the purpose of checking kernel's compile-time [[object file]]s and ensuring that the call stack is always maintained; it also opens up a possibility for achieving more reliable call stacks as part of the [[kernel oops]] messages.<ref>{{cite web
| url = https://lwn.net/Articles/658333/ | title = Compile-time stack validation | date = 2015-09-30 | | author-first = Jonathan | author-last = | publisher = [[LWN.net]] }}</ref><ref>{{cite web | url = https://lwn.net/Articles/658347/ | title = Linux kernel documentation: Documentation/stack-validation.txt (from the v13 patch) | | author-first = Josh | author-last = Poimboeuf
| publisher = [[LWN.net]]
}}</ref>
=== Ginseng ===
Line 72 ⟶ 210:
Ginseng is implemented as a [[source-to-source compiler]] written using the [[C Intermediate Language]] framework in [[OCaml]]. This compiler inserts indirection to all function calls and type accesses, enabling Ginseng to lazily transform state at the cost of imposing a constant-time overhead for the entirety of the program execution.<ref name="ginseng" /> Ginseng's compiler proves the ''cons-freeness'' properties of the entire initial program and of dynamic patches.
Later versions of Ginseng also support a notion of transactional safety. This allows developers to annotate a sequence of function calls as a logical unit, preventing updates from violating program semantics in ways that are not detectable by either activeness safety or ''cons-freeness'' safety. For example, in two versions of [[OpenSSH]] examined by Ginseng's authors, important user verification code was moved between two functions called in sequence. If the first version of the first function executed, an update occurred, and the new version of the second function was executed, then the verification would never be performed. Marking this section as a transaction ensures that an update will not prevent the verification from occurring.<ref name="vc">{{cite journal
| author-first1 = Iulian | author-last1 = | author-first2 = Michael | author-last2 = | author-first3 = Jeffrey | author-last3 = | author-first4 = Polyvios | author-last4 = | title = Contextual Effects for Version-Consistent Dynamic Software Updating and Safe Concurrent Programming | journal = Proceedings of the {ACM} Conference on Principles of Programming Languages (POPL) | year = 2008 | pages = 37–58 }}</ref> === UpStare ===
UpStare is a DSU system that uses a unique updating mechanism, '''stack reconstruction'''. To update a program with UpStare, a developer specifies a mapping between any possible stack frames. UpStare is able to use this mapping to immediately update the program at any point, with any number of threads, and with any functions live on the stack.<ref name="upstare">{{cite journal
| title = Immediate Multi-Threaded Dynamic Software Updates Using Stack Reconstruction | author-first1 = Kristis | author-last1 = | author-first2 = Rida A. | author-last2 = | journal = Proceedings of the 2009 | url = | year = 2009 }}</ref> === PoLUS ===
PoLUS is a binary-rewriting DSU system for [[C (programming language)|C]]. It is able to update unmodified programs at any point in their execution. To update functions, it rewrites the prelude to a target function to redirect to a new function, chaining these redirections over multiple versions. This avoids steady-state overhead in functions that have not been updated.<ref name="polus">{{cite journal
| title = POLUS: A POwerful Live Updating System | author-first1 = | author-last1 = | author-first2 = Jie | author-last2 = | author-first3 = | author-last3 = Chen | | | author-first5 = Pen-Chung
| author-last5 = Yew
| journal = 29th International Conference on Software Engineering
| year = 2007
| pages = 271–281
| url = http://ppi.fudan.edu.cn/system/publications/paper/chen-polus.pdf
| access-date = 2011-12-18
| archive-url = https://web.archive.org/web/20120426060636/http://ppi.fudan.edu.cn/system/publications/paper/chen-polus.pdf
| archive-date = 2012-04-26
| url-status = dead
}}</ref>
=== Katana ===
Katana is a research system that provides limited dynamic updating (similar to Ksplice and its forks) for user-mode [[Executable and Linkable Format|ELF]] binaries. The Katana patching model operates on the level of ELF objects, and thus has the capacity to be language-agnostic as long as the compilation target is ELF.
=== Kitsune and Ekiden ===
Line 91 ⟶ 262:
=== Erlang ===
[[Erlang (programming language)|Erlang]] supports Dynamic Software Updating, though this is commonly referred to as "[[Erlang (programming language)#Hot code loading and modules|hot code loading]]". Erlang requires no safety guarantees on updates, but Erlang culture suggests that developers write in a defensive style that will gracefully handle type errors generated by updating.{{
=== Pymoult ===
Pymoult is a prototyping platform for dynamic update written in Python. It gathers many techniques from other systems, allowing their combination and configuration. The objective of this platform is to let developers chose the update techniques they find more appropriate for their needs. For example, one can combine lazy update of the state as in Ginseng while changing the whole code of the application as in Kitsune or Ekiden.<ref>{{cite journal
| title = Prototyping DSU Techniques using Python | author1 = Sébastien Martinez | author2 = Fabien Dagnat | author3 = Jérémy Buisson | journal = Proceedings of the 5th Workshop on Hot Topics in Software Upgrades (HotSWUp'13) | year = | url = https://www.usenix.org/conference/hotswup13/workshop-program/presentation/martinez }}</ref><ref>{{cite web | url = https://bitbucket.org/smartinezgd/pymoult | title = | date = 2013-03-06 | | author-first = Sébastien | author-last = Martinez
| publisher = [[Bitbucket]]
}}</ref>
=== Microsoft Visual C++ ===
Microsoft is utilizing internal patching technology for Microsoft Visual C++ that supports patching individual C++ functions while maintaining functional correctness of patches. Currently known applications is SQL Server in Azure SQL Database.<ref>{{Cite web|url=https://techcommunity.microsoft.com/t5/Azure-SQL-Database/Hot-Patching-SQL-Server-Engine-in-Azure-SQL-Database/ba-p/849700|title=Hot Patching SQL Server Engine in Azure SQL Database|date=2019-09-11|website=TECHCOMMUNITY.MICROSOFT.COM|language=en|access-date=2019-09-15}}</ref>
== See also ==
* {{Section link|Hot swapping|Software}}
* [[Persistence (computer science)]]
* [[Runtime verification]]
== References ==
{{Reflist
== External links==
* [http://ksplice.com Ksplice homepage]
* [https://archive.today/20121217140001/https://github.com/cormander/ksplice Ksplice source code]
* [http://www.cs.umd.edu/projects/dsu/ Ginseng Project Page and Source Code/ UpStare Paper/ PoLUS paper]
* [http://www.erlang.org
* [http://www.nongnu.org/katana/doc/katana.html Katana homepage]
* [https://techcommunity.microsoft.com/t5/Azure-SQL-Database/Hot-Patching-SQL-Server-Engine-in-Azure-SQL-Database/ba-p/849700 Whitepaper blog post on Visual C++ patching]
[[Category:System administration]]
| |||