Improving the Reliability of Commodity Operating Systems
undefined
I
M
P
R
O
V
I
N
G
T
H
E
R
E
L
I
A
B
I
L
I
T
Y
O
F
C
O
M
M
O
D
I
T
Y
O
P
E
R
A
T
I
N
G
S
Y
S
T
E
M
S
Michael M. Swift
Brian N. Bershad
Henry M. Levy
University of Washington
Key Idea
Kernel extensions are a major source of system failures
N
o
o
k
s
i
s
o
l
a
t
e
s
e
x
t
e
n
s
i
o
n
s
w
i
t
h
i
n
l
i
g
h
t
w
e
i
g
h
t
p
r
o
t
e
c
t
i
o
n
d
o
m
a
i
n
s
i
n
s
i
d
e
t
h
e
k
e
r
n
e
l
a
d
d
r
e
s
s
s
p
a
c
e
R
e
q
u
i
r
e
s
l
i
t
t
l
e
o
r
n
o
c
h
a
n
g
e
s
t
o
e
x
t
e
n
s
i
o
n
a
n
d
k
e
r
n
e
l
c
o
d
e
S
t
i
l
l
p
r
e
v
e
n
t
s
m
o
s
t
s
y
s
t
e
m
f
a
i
l
u
r
e
s
INTRODUCTION
W
a
n
t
t
o
a
l
l
o
w
e
x
i
s
t
i
n
g
k
e
r
n
e
l
e
x
t
e
n
s
i
o
n
s
t
o
e
x
e
c
u
t
e
s
a
f
e
l
y
i
n
c
o
m
m
o
d
i
t
y
k
e
r
n
e
l
s
b
e
c
a
u
s
e
Computer reliability remains an
unsolved issue
Kernel extensions are increasingly popular in Windows and
Linux
Account for most system failures (85% for Windows XP)
Why?
Programmers writing device drivers are often less experienced
than kernel programmers
Number of variants prevent us from testing them completely
The Nooks approach
Works with commodity operating systems
Requires little or no changes to extension and kernel code
P
r
e
v
e
n
t
s
m
o
s
t
b
u
t
n
o
t
a
l
l
s
y
s
t
e
m
f
a
i
l
u
r
e
s
Let kernel extensions reside in the kernel address space
S
o
l
u
t
i
o
n
i
s
p
r
a
c
t
i
c
a
l
,
b
a
c
k
w
a
r
d
-
c
o
m
p
a
t
i
b
l
e
a
n
d
e
f
f
i
c
i
e
n
t
The challenge
S
a
f
e
t
y
S
p
e
e
d
E
x
t
e
n
s
i
b
i
l
i
t
y
Linux
Windows
Unix
Mach
(microkernel
)
PREVIOUS WORK (I)
C
a
p
a
b
i
l
i
t
y
-
b
a
s
e
d
a
r
c
h
i
t
e
c
t
u
r
e
s
,
r
i
n
g
a
n
d
s
e
g
m
e
n
t
a
r
c
h
i
t
e
c
t
u
r
e
s
:
Enable construction and isolation of privileged subsystems.
Slow and do not address recovery issues
PREVIOUS WORK (II)
M
i
c
r
o
k
e
r
n
e
l
s
:
Put extensions into separate address spaces
Slow and do not address recovery issues
D
a
t
a
b
a
s
e
r
e
c
o
v
e
r
y
t
e
c
h
n
i
q
u
e
s
:
Atomic transactions
Work well for file system
Often awkward and slow
PREVIOUS WORK (III)
T
y
p
e
-
s
a
f
e
p
r
o
g
r
a
m
m
i
n
g
l
a
n
g
u
a
g
e
s
:
Must rewrite the kernel
S
t
a
t
i
c
a
n
a
l
y
s
i
s
o
f
e
x
t
e
n
s
i
o
n
s
:
Can detect some errors
PREVIOUS WORK (III)
V
i
r
t
u
a
l
m
a
c
h
i
n
e
s
:
C
a
n
r
e
d
u
c
e
t
h
e
a
m
o
u
n
t
o
f
c
o
d
e
t
h
a
t
c
a
n
c
r
a
s
h
w
h
o
l
e
m
a
c
h
i
n
e
F
a
i
l
s
i
f
e
x
t
e
n
s
i
o
n
e
x
e
c
u
t
e
s
i
n
s
i
d
e
t
h
e
v
i
r
t
u
a
l
m
a
c
h
i
n
e
m
o
n
i
t
o
r
V
M
V
M
M
o
n
i
t
o
r
H
a
r
d
w
a
r
e
V
M
V
M
REQUIRED MODIFICATIONS
NOOKS
D
e
s
i
g
n
f
o
r
f
a
u
l
t
-
r
e
s
i
s
t
a
n
c
e
,
n
o
t
f
a
u
l
t
-
t
o
l
e
r
a
n
c
e
:
S
y
s
t
e
m
m
u
s
t
p
r
e
v
e
n
t
a
n
d
r
e
c
o
v
e
r
f
r
o
m
m
o
s
t
e
x
t
e
n
s
i
o
n
m
i
s
t
a
k
e
s
O
c
c
u
p
y
m
i
d
d
l
e
g
r
o
u
n
d
b
e
t
w
e
e
n
u
n
p
r
o
t
e
c
t
e
d
(
L
i
n
u
x
,
W
i
n
d
o
w
s
)
a
n
d
s
a
f
e
(
S
P
I
N
,
J
a
v
a
V
M
)
D
e
s
i
g
n
f
o
r
m
i
s
t
a
k
e
s
,
n
o
t
a
b
u
s
e
:
Exclude malicious behavior
Nooks goals
I
s
o
l
a
t
i
o
n
:
Isolate kernel from extension failures
Detect extension failures before they corrupt kernel
A
u
t
o
m
a
t
i
c
r
e
c
o
v
e
r
y
f
r
o
m
e
x
t
e
n
s
i
o
n
f
a
i
l
u
r
e
s
B
a
c
k
w
a
r
d
c
o
m
p
a
t
i
b
i
l
i
t
y
w
i
t
h
e
x
i
s
t
i
n
g
s
y
s
t
e
m
s
a
n
d
e
x
t
e
n
s
i
o
n
s
Nooks functions
N
e
w
s
y
s
t
e
m
r
e
l
i
a
b
i
l
i
t
y
l
a
y
e
r
:
t
h
e
N
o
o
k
s
I
s
o
l
a
t
i
o
n
M
a
n
a
g
e
r
(
N
I
M
)
Nooks isolation mechanisms
E
v
e
r
y
e
x
t
e
n
s
i
o
n
e
x
e
c
u
t
e
s
w
i
t
h
i
n
i
t
s
o
w
n
l
i
g
h
t
w
e
i
g
h
t
k
e
r
n
e
l
p
r
o
t
e
c
t
i
o
n
d
o
m
a
i
n
C
o
m
m
u
n
i
c
a
t
i
o
n
b
e
t
w
e
e
n
k
e
r
n
e
l
a
n
d
e
x
t
e
n
s
i
o
n
s
m
u
s
t
g
o
t
h
r
o
u
g
h
n
e
w
k
e
r
n
e
l
s
e
r
v
i
c
e
,
t
h
e
E
x
t
e
n
s
i
o
n
P
r
o
c
e
d
u
r
e
C
a
l
l
(
X
P
C
)
Similar to an RPC between two processes located on the same
machine (Lightweight RPC)
Lightweight protection domains
P
r
o
v
i
d
e
p
r
o
t
e
c
t
i
o
n
b
y
h
a
v
i
n
g
e
x
t
e
n
s
i
o
n
s
e
x
e
c
u
t
e
w
i
t
h
a
d
i
f
f
e
r
e
n
t
p
a
g
e
t
a
b
l
e
g
i
v
i
n
g
t
h
e
m
Read/write access to their own pages
Read only access to other kernel pages
Lightweight protection domains
L
i
g
h
t
w
e
i
g
h
t
s
o
l
u
t
i
o
n
E
x
t
e
n
s
i
o
n
s
e
x
e
c
u
t
e
i
n
k
e
r
n
e
l
m
o
d
e
A malicious extension could
Switch back to the kernel’s page table
Another could misuse DMA
Nooks interposition mechanisms
Ensure that
All extension-to-kernel and kernel-to-extension control flow
goes through Nooks XPC mechanism
All data transfers between kernel and extension go through
Nooks object tracking code
A
l
l
i
n
t
e
r
f
a
c
e
s
a
r
e
d
o
n
e
t
h
r
o
u
g
h
w
r
a
p
p
e
r
s
,
s
i
m
i
l
a
r
t
o
t
h
e
s
t
u
b
s
o
f
a
n
R
P
C
p
a
c
k
a
g
e
Nooks object tracking functions
Maintain a list of kernel data structures accessed by each
extension
Control all modifications to these structures
Provide object information for cleanup if object fails
Nooks object tracking functions
E
x
t
e
n
s
i
o
n
s
c
a
n
n
o
t
d
i
r
e
c
t
l
y
m
o
d
i
f
y
k
e
r
n
e
l
d
a
t
a
s
t
r
u
c
t
u
r
e
s
Object tracking code will:
Copy kernel data structures into extension address space
Copy them back after changes have been applied
Perform checks whenever possible
Nooks recovery functions
Detect and recover from various extension faults:
When an extension improperly invokes a kernel function
When processor raises an exception
Nooks recovery functions
Recovery helped by Nooks isolation mechanisms:
All access to kernel structures are done through wrappers
Nooks can successfully release extension-held kernel
structures
IMPLEMENTATION
Inside Linux 2.4.18 kernel on Intel x86 architecture
Linux kernel provides
over 700 functions callable by extensions
over 650 extension-entry functions callable by the kernel
Most interactions between kernel and extensions go through
function calls
Nooks
L
i
n
u
x
K
e
r
n
e
l
Nooks Isolation Manager
E
x
t
e
n
s
i
o
n
s
a
r
e
w
r
a
p
p
e
d
b
y
N
o
o
k
s
w
r
a
p
p
e
r
s
t
u
b
s
Details
22,000 lines of code
Linux kernel has 2.4 million lines
Makes no use of Intel x86 protection rings
Extensions execute at same protection level as kernel
Isolation
Two parts:
m
e
m
o
r
y
m
a
n
a
g
e
m
e
n
t
:
t
o
i
m
p
l
e
m
e
n
t
l
i
g
h
t
w
e
i
g
h
t
p
r
o
t
e
c
t
i
o
n
d
o
m
a
i
n
s
e
x
t
e
n
s
i
o
n
p
r
o
c
e
d
u
r
e
c
a
l
l
(
X
P
C
)
Memory management
All components share the same kernel address space
E
a
c
h
e
x
t
e
n
s
i
o
n
e
x
e
c
u
t
e
s
i
n
a
s
e
p
a
r
a
t
e
l
i
g
h
t
w
e
i
g
h
t
p
r
o
t
e
c
t
i
o
n
d
o
m
a
i
n
Extension has:
Read-only access to kernel
Read-write access to its own domain
Lightweight protection domains
Each lightweight protection domain has
A synchronized copy of the kernel page table
Its own heap, a pool of stacks and other private data structures
Changing protection domains requires a change of page tables
Results in a TLB flush!
Performance degradation
N
o
p
r
o
t
e
c
t
i
o
n
a
g
a
i
n
s
t
D
M
A
m
i
s
u
s
e
b
y
e
x
t
e
n
s
i
o
n
s
Interposition (I)
D
o
n
e
b
y
w
r
a
p
p
e
r
s
t
u
b
s
a
l
l
e
x
e
c
u
t
i
n
g
i
n
k
e
r
n
e
l
p
r
o
t
e
c
t
i
o
n
d
o
m
a
i
n
:
Before the call when kernel calls an extension
After the call when an extension calls the kernel
Wrappers:
Check parameters for validity
I
m
p
l
e
m
e
n
t
c
a
l
l
b
y
v
a
l
u
e
a
n
d
r
e
s
u
l
t
i
=
1
i
=
0
Passing by value and result
C
a
l
l
e
r
:
…
i
=
0
;
a
b
c
(
&
i
)
;
…
i
a
b
c
(
i
n
t
*
k
)
{(
*
k
)
+
+
;
}
V
a
r
i
a
b
l
e
i
i
s
i
n
c
r
e
a
s
e
d
a
f
t
e
r
c
a
l
l
e
r
r
e
c
e
i
v
e
s
s
e
r
v
e
r
’
s
r
e
p
l
y
Interposition (II)
Writing wrappers is not an easy task:
Requires knowing how parameters are used
S
i
g
n
i
f
i
c
a
n
t
a
m
o
u
n
t
o
f
w
r
a
p
p
e
r
s
h
a
r
i
n
g
a
m
o
n
g
e
x
t
e
n
s
i
o
n
s
E
s
p
e
c
i
a
l
l
y
w
h
e
n
e
x
t
e
n
s
i
o
n
s
s
h
a
r
e
s
a
m
e
f
u
n
c
t
i
o
n
a
l
i
t
y
Object tracking
Records kernel objects and types manipulated by extensions
Recovery
Mostly through undoing
Limitations
Cannot prevent extensions from executing privileged instructions
that would corrupt the kernel
C
a
n
n
o
t
p
r
e
v
e
n
t
i
n
f
i
n
i
t
e
l
o
o
p
s
i
n
s
i
d
e
a
n
e
x
t
e
n
s
i
o
n
Prevented by Linux semantics to do a thorough check of the
parameters passed to the operating system
C
u
r
r
e
n
t
i
m
p
l
e
m
e
n
t
a
t
i
o
n
o
f
r
e
c
o
v
e
r
y
a
s
s
u
m
e
s
t
h
a
t
e
x
t
e
n
s
i
o
n
s
c
a
n
b
e
k
i
l
l
e
d
a
n
d
r
e
s
t
a
r
t
e
d
Transparency
“Neither the extension not the kernel is aware of the Nooks layer”
In reality, must sometimes modify a few lines of extension code
Reliability
Tested eight extensions
Two sound card drivers
Four Ethernet drivers
A Win95 compatible file system (VFAT)
An in-kernel Web server
Injected 400 faults
317 resulted in extension failures
Test results
Nooks eliminated 99% of the crashes observed with native Linux
313 out of 317
N
o
o
k
s
i
s
s
l
o
w
e
r
VFAT benchmark spent 165s in the kernel instead of 29.5s for native
Linux
Web server could only serve about 6,000 pages/s instead of 15,000
pages/s for native Linux
Ouch!
PERFORMANCE
Ten percent performance penalty for sound and Ethernet drivers
Sixty percent performance penalty for in-kernel web server
(15,000 - 6,000)/15,000
Recovery errors
Big problems with VFAT extension
90% of attempted recoveries resulted in on-disk corruption
VFAT extension cannot be safely killed and restarted
We should expect that!
CONCLUSIONS
N
o
o
k
s
a
p
p
r
o
a
c
h
f
o
c
u
s
e
s
o
n
a
c
h
i
e
v
i
n
g
b
a
c
k
w
a
r
d
c
o
m
p
a
t
i
b
i
l
i
t
y
Cannot provide complete isolation and fault-tolerance
C
a
n
s
t
i
l
l
a
c
h
i
e
v
e
“
a
n
e
x
t
r
e
m
e
l
y
h
i
g
h
l
e
v
e
l
o
f
o
p
e
r
a
t
i
n
g
s
y
s
t
e
m
r
e
l
i
a
b
i
l
i
t
y
”
Performance loss varies between 0 and 60 percent
This research paper discusses the challenges and solutions in enhancing the reliability of commodity operating systems by addressing system failures caused by kernel extensions. The Nooks approach isolates extensions within protection domains, allowing them to reside in the kernel address space with minimal code changes. The goal is to enable existing kernel extensions to execute safely in commodity kernels, focusing on practicality, compatibility, and efficiency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
IMPROVING THE RELIABILITY OF COMMODITY OPERATING SYSTEMS Michael M. Swift Brian N. Bershad Henry M. Levy University of Washington
Key Idea Kernel extensions are a major source of system failures Nooks isolates extensions within lightweight protection domains inside the kernel address space Requires little or no changes to extension and kernel code Still prevents most system failures
INTRODUCTION Want to allow existing kernel extensions to execute safely in commodity kernels because Computer reliability remains an unsolved issue Kernel extensions are increasingly popular in Windows and Linux Account for most system failures (85% for Windows XP)
Why? Programmers writing device drivers are often less experienced than kernel programmers Number of variants prevent us from testing them completely
The Nooks approach Works with commodity operating systems Requires little or no changes to extension and kernel code Prevents most but not all system failures Let kernel extensions reside in the kernel address space Solution is practical, backward-compatible and efficient
The challenge Extensibility Mach Linux Windows (microkernel) Speed Safety Unix
PREVIOUS WORK (I) Capability-based architectures, ring and segment architectures: Enable construction and isolation of privileged subsystems. Slow and do not address recovery issues
PREVIOUS WORK (II) Microkernels: Put extensions into separate address spaces Slow and do not address recovery issues Database recovery techniques: Atomic transactions Work well for file system Often awkward and slow
PREVIOUS WORK (III) Type-safe programming languages: Must rewrite the kernel Static analysis of extensions: Can detect some errors
PREVIOUS WORK (III) Virtual machines: Can reduce the amount of code that can crash whole machine Fails if extension executes inside the virtual machine monitor VM VM VM VM Monitor Hardware
REQUIRED MODIFICATIONS Approach Capability architecture Microkernels Type-safe languages New driver arch. Atomic transactions Virtual machines Static analysis Nooks HW Yes No No No No No No No OS Yes Yes Yes Yes No No No No Ext. Yes Yes Yes Yes Yes Yes No No
NOOKS Design for fault-resistance, not fault-tolerance: System must prevent and recover from mostextension mistakes Occupy middle ground between unprotected (Linux, Windows) and safe (SPIN, Java VM) Design for mistakes, not abuse: Exclude malicious behavior
Nooks goals Isolation: Isolate kernel from extension failures Detect extension failures before they corrupt kernel Automatic recovery from extension failures Backward compatibility with existing systems and extensions
Nooks functions New system reliability layer: the Nooks Isolation Manager (NIM) OS Kernel Object Tracking Recovery Isolation Interposition Kernel extensions
Nooks isolation mechanisms Every extension executes within its own lightweight kernel protection domain Communication between kernel and extensions must go through new kernel service, the Extension Procedure Call (XPC) Similar to an RPC between two processes located on the same machine (Lightweight RPC)
Lightweight protection domains Provide protection by having extensions execute with a different page table giving them Read/write access to their own pages Read only access to other kernel pages Kernel (read only) Extension (R/W)
Lightweight protection domains Lightweight solution Extensions execute in kernel mode A malicious extension could Switch back to the kernel s page table Another could misuse DMA
Nooks interposition mechanisms Ensure that All extension-to-kernel and kernel-to-extension control flow goes through Nooks XPC mechanism All data transfers between kernel and extension go through Nooks object tracking code All interfaces are done through wrappers, similar to the stubs of an RPC package
Nooks object tracking functions Maintain a list of kernel data structures accessed by each extension Control all modifications to these structures Provide object information for cleanup if object fails
Nooks object tracking functions Extensions cannot directly modify kernel data structures Object tracking code will: Copy kernel data structures into extension address space Copy them back after changes have been applied Perform checks whenever possible
Nooks recovery functions Detect and recover from various extension faults: When an extension improperly invokes a kernel function When processor raises an exception
Nooks recovery functions Recovery helped by Nooks isolation mechanisms: All access to kernel structures are done through wrappers Nooks can successfully release extension-held kernel structures
IMPLEMENTATION Inside Linux 2.4.18 kernel on Intel x86 architecture Linux kernel provides over 700 functions callable by extensions over 650 extension-entry functions callable by the kernel Most interactions between kernel and extensions go through function calls
Nooks Linux Kernel Nooks Isolation Manager Interposition Extension Interposition Extension Extensions are wrapped by Nooks wrapper stubs
Details 22,000 lines of code Linux kernel has 2.4 million lines Makes no use of Intel x86 protection rings Extensions execute at same protection level as kernel
Isolation Two parts: memory management: to implement lightweight protection domains extension procedure call (XPC)
Memory management All components share the same kernel address space Each extension executes in a separate lightweight protection domain Extension has: Read-only access to kernel Read-write access to its own domain
Lightweight protection domains Each lightweight protection domain has A synchronized copy of the kernel page table Its own heap, a pool of stacks and other private data structures Changing protection domains requires a change of page tables Results in a TLB flush! Performance degradation No protection against DMA misuse by extensions
Interposition (I) Done by wrapper stubs all executing in kernel protection domain: Before the call when kernel calls an extension After the call when an extension calls the kernel Wrappers: Check parameters for validity Implement call by value and result
Passing by value and result Variable i is increased after caller receives server s reply Caller: i = 0; abc(&i); i = 0 abc(int *k){ (*k)++; } i = 1 i
Interposition (II) Writing wrappers is not an easy task: Requires knowing how parameters are used Significant amount of wrapper sharing among extensions Especially when extensions share same functionality
Object tracking Records kernel objects and types manipulated by extensions
Recovery Mostly through undoing
Limitations Cannot prevent extensions from executing privileged instructions that would corrupt the kernel Cannot prevent infinite loops inside an extension Prevented by Linux semantics to do a thorough check of the parameters passed to the operating system Current implementation of recovery assumes that extensions can be killed and restarted
Transparency Neither the extension not the kernel is aware of the Nooks layer In reality, must sometimes modify a few lines of extension code
Reliability Tested eight extensions Two sound card drivers Four Ethernet drivers A Win95 compatible file system (VFAT) An in-kernel Web server Injected 400 faults 317 resulted in extension failures
Test results Nooks eliminated 99% of the crashes observed with native Linux 313 out of 317 Nooks isslower VFAT benchmark spent 165s in the kernel instead of 29.5s for native Linux Web server could only serve about 6,000 pages/s instead of 15,000 pages/s for native Linux Ouch!
PERFORMANCE Ten percent performance penalty for sound and Ethernet drivers Sixty percent performance penalty for in-kernel web server (15,000 - 6,000)/15,000
Recovery errors Big problems with VFAT extension 90% of attempted recoveries resulted in on-disk corruption VFAT extension cannot be safely killed and restarted We should expect that!
CONCLUSIONS Nooks approach focuses on achieving backward compatibility Cannot provide complete isolation and fault-tolerance Can still achieve an extremely high level of operating system reliability Performance loss varies between 0 and 60 percent
