Safe and Automatic Live Update for Operating Systems
Cristiano Giuffrida Anton Kuijsten Andrew S. Tanenbaum
Vrije Universiteit, Amsterdam
{
giuffrida, akuijst, ast
}
@cs.vu.nl
Abstract
Increasingly many systems have to run all the time with no down-
time allowed. Consider, for example, systems controlling electric
power plants and e-banking servers. Nevertheless, security patches
and a constant stream of new operating system versions need to
be deployed without stopping running programs. These factors nat-
urally lead to a pressing demand for live update—upgrading all
or parts of the operating system without rebooting. Unfortunately,
existing solutions require significant manual intervention and thus
work reliably only for small operating system patches.
In this paper, we describe an automated system for live update
that can safely and automatically handle major upgrades without
rebooting. We have implemented our ideas in P
ROTEOS
,anew
research OS designed with live update in mind. P
ROTEOS
relies
on system support and nonintrusive instrumentation to handle even
very complex updates with minimal manual effort. The key novelty
is the idea of
state quiescence
, which allows updates to happen
only in safe and predictable system states. A second novelty is the
ability to automatically perform transactional live updates at the
process level
, ensuring a safe and
stable
update process. Unlike
prior solutions, P
ROTEOS
supports automated state transfer, state
checking, and
hot rollback
.WehaveevaluatedP
ROTEOS
on 50 real
updates and on novel live update scenarios. The results show that
our techniques can effectively support both simple and complex
updates, while outperforming prior solutions in terms of flexibility,
security, reliability, and stability of the update process.
Categories and Subject Descriptors
D.4.7 [
Operating Systems
]:
Organization and Design
General Terms
Design, Experimentation, Reliability
Keywords
Live update, Automatic updates, State transfer, State
checking, Update safety, Operating systems
1. Introduction
Modern operating systems evolve rapidly. Studies on the Linux
kernel have shown that its size has more than doubled in the last
10 years, with a growth of more than 6 MLOC and over 300 offi-
cial versions released [64]. This trend leads to many frequently
released updates that implement new features, improve perfor-
mance, or fix important bugs and security vulnerabilities. With
today’s pervasive demand for 24/7 operation, however, the tradi-
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. To copy otherwise, to republish, to post on servers or to redistribute
to lists, requires prior specific permission and/or a fee.
ASPLOS’13,
March 16–20, 2013, Houston, Texas, USA.
Copyright
c
©
2013 ACM 978-1-4503-1870-9/13/03...$15.00
tional patch-install-reboot cycle introduces unacceptable downtime
for the operating system (OS) and all the running applications. To
mitigate this problem, enterprise users often rely on “
rolling up-
grades
” [27]—upgrading one node at a time in a highly replicated
software system—which, however, require redundant hardware (or
virtualized environments), cannot normally preserve program state
across system versions, and may introduce a very large update win-
dow with high exposure to mixed version races [29].
Live update (sometimes also called
hot
or
dynamic
update)
is a potential solution to this problem, due to its ability to up-
grade a running system on the fly with no service interruption.
To reach widespread adoption, however, a live update solution
should be practical and trustworthy. We found that existing solu-
tions for operating systems [12–14, 20, 56] and generic C pro-
grams [10, 21, 55, 55, 59, 60] meet these requirements only for
simple updates. Not surprisingly, many live update solutions explic-
itly target small security patches [10, 12]. While security patches
are a critical application for live update—as also demonstrated by
the commercial success of solutions like Ksplice [12]—we believe
there is a need for solutions that can effectively handle more com-
plex updates, such as upgrading between operating system versions
with hundreds or thousands of changes.
We note two key limiting factors in existing solutions. First,
they scale poorly with the size and complexity of the update. This
limitation stems from the limited system support to ensure update
safety and transfer the run-time state from one system version to
another. Existing solutions largely delegate these challenging tasks
to the programmer. When applied to updates that install a new OS
version with major code and data structure changes, this strategy
requires an unbearable effort and is inevitably error prone.
Second, they scale poorly with the number of live updates ap-
plied to the system. This limitation stems from the update mecha-
nisms employed in existing solutions, which assume a rigid address
space layout, and glue code and data changes directly into the run-
ning version. This strategy typically leads to an
unstable
live update
process, with memory leakage and performance overhead growing
linearly over time (
§
2.3). We found that both limiting factors in-
troduce important reliability and security issues, which inevitably
discourage acceptance of live update.
This paper presents P
ROTEOS
, a new research operating sys-
tem designed to safely and automatically support many classes of
live updates. To meet this challenge, P
ROTEOS
introduces several
novel techniques. First, it replaces the long-used notion of
func-
tion
[12] and
object
[14]
quiescence
with the more general idea
of
state quiescence
, allowing programmer-provided
state filters
to
specify constraints on the update state. The key intuition is that op-
erating systems quickly transition through many states with differ-
ent properties. Restricting the update to be installed only in specific
states dramatically simplifies reasoning on update safety.
Further, P
ROTEOS
employs transactional
process-level
live up-
dates, which reliably replace entire processes instead of individ-
ual objects or functions. To increase the update surface and sup-
279
port complex updates, we explore this idea in a design with all
the core OS subsystems running as independent event-driven pro-
cesses on top of a minimal message-passing substrate running in
kernel mode. Using processes as updatable units ensures a
stable
update process and eliminates the need for complex patch anal-
ysis and preparation tools. In addition, P
ROTEOS
uses hardware-
isolated processes to sandbox the state transfer execution in the new
process version and support
hot rollback
in case of run-time errors.
Finally, P
ROTEOS
relies on compiler-generated instrumentation
to automate state transfer (migrating the state between processes),
state checking (checking the state for consistency), and tainted state
management (recovering from a corrupted state), with minimal run-
time overhead. Our state transfer framework is designed to
auto-
matically
handle common structural state changes (e.g., adding a
newfieldtoa
struct
) and recover from particular tainted states
(i.e., memory leakage), while supporting a convenient program-
ming model for extensions. As an example, programmers can reg-
ister their own callbacks to handle corrupted pointers or override
the default transfer strategy for state objects of a particular type.
Our current P
ROTEOS
implementation runs on the x86 platform
and supports a complete POSIX interface. Our state management
framework supports C and assembly code. Its instrumentation com-
ponent is implemented as a link-time pass using the LLVM com-
piler framework [50].
We evaluated P
ROTEOS
on 50 real updates (randomly sampled
in the course of over 2 years of development) and novel live update
scenarios:
online diversification
,
memory leakage reclaiming
,and
update failures
(
§
6.3). Our results show that: (i) P
ROTEOS
provides
an effective and easy-to-use update model for both small and very
complex updates. Most live updates required minimal effort to be
deployed, compared to the “
tedious engineering effort
” reported
in prior work [20]; (ii) P
ROTEOS
is reliable and secure. Our state
transfer framework reduces manual effort to the bare minimum and
can safely rollback the update when detecting unsafe conditions or
run-time errors (e.g., crashes, timeouts, assertion failures). Despite
the complexity of some of the 50 updates analyzed, live update re-
quired only 265 lines of custom state transfer code in total. (iii) The
update techniques used in P
ROTEOS
are
stable
and efficient. The
run-time overhead is well isolated in allocator operations and only
visible in microbenchmarks (6-130% overhead on allocator opera-
tions). The service disruption at update time is minimal (less than
5% macrobenchmark overhead while replacing an OS component
every 20s) and the update time modest (3.55s to replace all the OS
components). (iv) The update mechanisms used in P
ROTEOS
sig-
nificantly increase the update surface and enable novel live update
scenarios. In our experiments, we were able to update
all
the OS
components in a single fault-tolerant transaction and completely
automate
live update of as many as 4,873,735 type transformations
throughout the entire operating system (
§
6.3).
Contribution
. This paper makes several contributions. First, we
identify the key limitations in existing live update solutions and
present practical examples of reliability and security problems.
Second, we introduce a new update model based on
state quies-
cence
, which generalizes existing models but allows updates to be
deployed only in predictable system states. Third, we introduce
transactional process-level updates, which allow safe
hot rollback
in case of update failures, and present their application to operat-
ing systems. Fourth, we introduce a new reliable and secure state
transfer framework that automates state transfer, state checking,
and tainted state management. Finally, we have implemented and
evaluated these ideas in P
ROTEOS
, a new research operating sys-
tem designed with live update in mind. We believe our work raises
several important issues on existing techniques and provides effec-
tive solutions that can drive future research in the field.
static struct
task_struct *copy_process(...) {
...
(1)
p = dup_task_struct(current);
if
(!p)
goto
fork_out;
...
(2)
//unsafe update point
retval = copy_creds(p, clone_flags);
if
(retval < 0)
goto
bad_fork_free;
...
(3)
}
static struct
task_struct
*dup_task_struct(...) {
...
prepare_creds
();
...
}
int
copy_creds(...) {
...
...
}
static struct
task_struct
*dup_task_struct(...) {
...
...
}
int
copy_creds(...) {
...
prepare_creds
();
...
}
Old version
New version
Figure 1.
An unsafe live update using function quiescence.
2. Background
Gupta has determined that the validity of a live update applied in an
arbitrary state
S
and using a state transfer function
T
is undecidable
in the general case [37]. Hence, system support and manual inter-
vention are needed. Unfortunately, existing solutions offer both
limited control over the update state
S
and poor support to build
the state transfer function
T
.
2.1 Safe Update State
Prior work has generally focused on an update-agnostic definition
of a safe update state. A number of solutions permit both the old and
the new version to coexist [20, 21, 56], many others disallow up-
dates to active code [10, 12, 14, 31, 36]. The first approach yields an
highly unpredictable update process, making it hard to give strong
safety guarantees. The second approach relies on the general no-
tion of
function
(or
object
)
quiescence
, which only allows updates
to functions that are not on the call stack of some active thread.
Figure 1 demonstrates that quiescence is a weak requirement
for a safe update state. The example proposed (inspired by real
code from the Linux
fork
implementation) simply moves the call
prepare
creds()
from the function
dup
task
struct
to the
function
copy
creds
.Since
copy
process
is unchanged, func-
tion quiescence would allow the update to happen at any of the
update points (1, 2, 3). It is easy to show, however, that the update
point (2) is unsafe, since it may allow a single invocation of the
function
copy
process()
to call (i) the old version of the func-
tion
dup
task
struct()
and (ii) the new version of the function
copy
creds()
. Due to the nature of the update, the resulting ex-
ecution would
incorrectly
call
prepare
creds()
twice—and not
once, as expected during normal update-free execution.
To address this problem, prior live update solutions have pro-
posed pre-annotated transactions [61], update points [60], or static
analysis [59]. These strategies do not easily scale to complex op-
erating system updates and always expose the programmer to the
significant effort of manually verifying update correctness in all
the possible system states. P
ROTEOS
addresses this problem using
our new notion of
state quiescence
, which generalizes prior update
safety mechanisms and allows the programmer to dynamically ex-
press update constraints on a per-update basis. In the example, the
programmer can simply specify a
state filter
(
§
4.3) requesting no
fork
to be in progress at update time.
280
Shadow Data Structures
Before Update
After Update
void
*base_p = (
void
*)&c;
size_t
size_p =
sizeof
(c);
base_p
0xf000
&c
Object Replacement
void
*base_p = (
void
*)&c;
void
*interior_p = (
void
*)&c.uid;
base_p
0xf000
&c
interior_p
0xf014
&c.uid
Type Wrapping
memset
(base_p, 0, size_p);
bits =
SHADOW
(c', securebits);
id = ((
struct
cred*)base_p)->uid;
id = *((
int
*)interior_p);
*((
int
*)interior_p) = 0;
void
*interior_p = (
void
*)&c.magic;
c'.securebits
0xdeadbeef
bits
0xdeadbeef
base_p
0xf000
&c
interior_p
0xf014
&c.uid
id
c.uid
id
c.magic
interior_p
0xf010
&c.magic
c'.uid
0
(c) Reading uninitialized
securebits
(b) Reading stale
magic
and
uid
(a) Overriding
uid
instead of
magic
interior_p
0xf010
&c.magic
struct
cred {
atomic_t
usage;
atomic_t
subscribers;
void
*put_addr;
int
flags;
unsigned
magic;
uid_t
uid;
...
}
c
;
0xf000
0xf004
0xf008
0xf00c
0xf010
0xf014
0xf018
struct
cred {
atomic_t
usage;
atomic_t
subscribers;
void
*put_addr;
unsigned
magic;
uid_t
uid;
...
unsigned
securebits;
}
c'
;
0xf000
0xf004
0xf008
0xf00c
0xf010
0xf014
0xf024
Figure 2.
Examples of live update vulnerabilities introduced by unhandled pointers into updated data structures: (a) Type-unsafe memory
writes; (b) Misplaced reads of stale object data; (c) Uninitialized reads.
2.2 State Transfer
Prior work has generally focused on supporting data type transfor-
mations in a rigid address space organization. Three approaches are
dominant:
type wrapping
[59, 60],
object replacement
[14, 20, 21,
55], and
shadow data structures
[12, 56]. Type wrapping instru-
ments data objects with extra padding and performs in-place type
transformations. Object replacement dynamically loads the new ob-
jects into the address space and transfers the state from the old
objects to the new ones. Shadow data structures are similar, but
preserve the old objects and only load the new fields of the new ob-
jects. While some have automated the generation of type transform-
ers [59, 60],
none
of the existing live update solutions for C pro-
vides automated support for transforming pointers and reallocat-
ing dynamic objects. Figure 2 demonstrates that failure to properly
handle pointers into updated objects can introduce several prob-
lems, ranging from subtle logical errors to security vulnerabilities.
Type wrapping may introduce type-unsafe memory reads/writes for
stale interior pointers into updated objects. This is similar to a typi-
cal dangling pointer vulnerability [8], which, in the example, causes
the pointer
interior
p
to erroneously write into the field
uid
in-
stead of the field
magic
. Object replacement may introduce similar
vulnerabilities for stale base pointers to updated objects. In the ex-
ample, this causes the pointer
base
p
to erroneously read from the
field
magic
in the old object instead of the field
uid
in the new one.
It may also introduce misplaced reads/writes for stale interior point-
ers into updated objects. In the example, this causes the pointer
interior
p
to read the field
uid
from the old object instead of the
new one. Finally, shadow data structures may introduce missing
read/write errors for nonupdated code accessing updated objects as
raw data. This may, for example, lead to uninitialized read vulner-
abilities, as shown in the example for the field
securebits
.
Prior solutions have proposed static analysis to identify all these
cases correctly [60]. This strategy, however, requires sophisticated
program analysis that scales poorly with the size of the program,
limits the use of some legal C idioms (e.g.,
void*
pointers), and
only provides the ability to
disallow
updates as long as there are
some live pointers into updated objects. Thus, extensive
manual
ef-
fort is still required to locate and transfer all the pointers correctly
in the common case of long-lived pointers into updated data struc-
tures. In our experience, this effort is unrealistic for nontrivial state
changes. P
ROTEOS
addresses this problem by migrating the
entire
state
from one process version to another, automating pointer trans-
fer and dynamic object reallocation with none of the limitations
above. This is possible using our run-time state introspection strat-
egy implemented on top of LLVM-based instrumentation (
§
5.2).
2.3 Stability of the update process
We say that a live update process is
stable
if version
τ
of the sys-
tem with no live update applied behaves no differently than version
τ
−
k
of the same system after
k
live updates. This property is
crucial for realistic long-term deployment of live update. Unfortu-
nately, the update mechanisms used in existing live update solu-
tions for C repeatedly violate the stability assumption. This is pri-
marily due to the rigid address space organization used, with every
update loading new code and data directly into the running ver-
sion. This
in-place
strategy typically introduces memory leakage
(due to the difficulties to reclaim dead code and data) and poorer
spatial locality (due to address space fragmentation). For example,
prior work on server applications reported 40% memory footprint
increase and 29% performance overhead after 10 updates [60]. Fur-
ther, solutions that redirect execution to the new code via binary
rewriting [10, 12, 21, 56] introduce a number of trampolines (and
thus overhead) that grows linearly with the number and the size of
the updates. Finally, shadow data structures change the code rep-
resentation and force future updates to track all the changes pre-
viously applied to the system, complicating version management
over time. P
ROTEOS
’
process-level
updates eliminate all these is-
sues and ensure a
stable
live update process (
§
5).
3. Overview
Our design adheres to 3 key principles: (i)
security and reliability
:
updates are only installed in predictable system states and the up-
date process is safeguarded against errors and unsafe conditions;
(ii)
large update surface
: no constraints on the size, complexity,
and number of updates applied to the system; (iii)
minimal manual
effort
: state filters minimize code inspection effort to ensure safety;
automated state transfer minimizes programming effort for the up-
date; process-level updates make deploying live updates as natural
as installing a new release, with no need for specialized toolchains
or complex patch analysis tools.
3.1 Architecture
Figure 3 shows the overall architecture of P
ROTEOS
. Our de-
sign uses a minimalistic approach with a thin kernel only man-
aging the hardware and providing basic IPC functionalities. All
the core operating system subsystems are confined into hardware-
isolated processes, including drivers, scheduling, process manage-
ment, memory management, storage, and network stack. The OS
processes communicate through message passing and adhere to a
281