Topic Definition Statement
bribri201316
Mitigating_Privilege_Escalatio.pdf
Mitigating Privilege Escalation
A Thesis Submitted to the Faculty
in partial fulfillment of the requirements for the degree of
Doctor of Philosophy
by
Scott Brookes
Thayer School of Engineering Dartmouth College
Hanover, New Hampshire
May 2018
Examining Committee:
Chairman Stephen Taylor, Ph.D.
Member Sergey Bratus, Ph.D.
Member George Cybenko, Ph.D.
Member Steve Chapin, Ph.D.
F. Jon Kull, Ph.D. Dean of Graduate and Advanced Studies
ProQuest Number:
All rights reserved
INFORMATION TO ALL USERS The quality of this reproduction is dependent upon the quality of the copy submitted.
In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if material had to be removed,
a note will indicate the deletion.
ProQuest
Published by ProQuest LLC ( ). Copyright of the Dissertation is held by the Author.
All rights reserved. This work is protected against unauthorized copying under Title 17, United States Code
Microform Edition © ProQuest LLC.
ProQuest LLC. 789 East Eisenhower Parkway
P.O. Box 1346 Ann Arbor, MI 48106 - 1346
10822683
10822683
2018
Abstract
One particularly difficult challenge in the computer security landscape is preventing
privilege escalation. This type of attack happens when an actor is granted access
to some piece of hardware with limited permissions but manages to circumvent the
security policies meant to contain them. Although a simple bug in the operating
system, or even in user libraries, can be sufficient to enable this type of attack,
such a vulnerability is also relatively easy to fix. Privilege escalation mechanisms
represent a more challenging security risk because they are methods by which generic
vulnerabilities (such as a buffer overflow) can be leveraged to escalate privilege.
This thesis describes a collection of operating system hardening techniques de-
signed to mitigate the risks of common privilege escalation mechanisms. This includes
non-deterministic loading techniques to randomize code, leveraging the virtualization
features of modern hardware to protect operating system code, and a novel operat-
ing system design paradigm. A proof-of-concept prototype was developed for each
of these techniques using the Bear research microkernel. The code for all techniques
described in this thesis is available at https://github.com/SCSLaboratory/BearOS.
Each of the techniques described in this thesis is evaluated in terms of the addi-
tional security it offers alongside the performance cost of the technique. The security
analysis of each technique attempts to describe (and quantify where possible) the
types of privilege escalation mechanisms that the technique interrupts. Meanwhile,
macro- and micro-benchmarks that are compatible with the Bear microkernel illus-
ii
trate the practicality of each of these techniques for deployment on real-world systems.
Synthesizing four different security mechanisms that each address unique types
of privilege escalation threats, the thesis provides a glimpse of a hardened operating
system. Contrary to the standard practice of “patching” the status quo in response to
each new threat, it attempts to visualize a next-generation operating system design
that brings together the best features of non-determinism, virtualization, and hard-
ware resource utilization in order to present a more secure computing system that
can still meet the ever-increasing performance requirements of modern computing
applications.
iii
Contents
Abstract ii
Contents iv
List of Tables viii
List of Figures ix
List of Code Snippets xi
List of Algorithms xii
1 Introduction 1
1.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Metrics of Success . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Publications and Contributions . . . . . . . . . . . . . . . . . . . . . 8
1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Background and State of the Art 13
2.1 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Case Study: Recursive Paging . . . . . . . . . . . . . . . . . . 15
2.1.2 The Virtual Address Space . . . . . . . . . . . . . . . . . . . . 17
2.2 Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
iv
2.3 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Related Work 24
3.1 Privilege Escalation Mitigation . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Techniques based on Virtualization . . . . . . . . . . . . . . . 29
3.1.2 Other Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.4 Privilege Escalation Mitigation: Conclusion . . . . . . . . . . 42
3.2 Execute-Only Memory . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Code Diversification . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Asymmetrical Multiprocessing . . . . . . . . . . . . . . . . . . . . . . 46
3.5 Operating System Design Paradigm Shifts . . . . . . . . . . . . . . . 48
3.5.1 Microkernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.5.2 ExoKernel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.3 Unikernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 ExOShim 51
4.1 ExOShim: Background . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.1.1 The Kernel and Virtual Memory . . . . . . . . . . . . . . . . 52
4.1.2 Virtualization and the EPT . . . . . . . . . . . . . . . . . . . 53
4.2 ExOShim: Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.2 ExOShim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 ExOShim: Implementation . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3.1 Providing ExOShim a Context . . . . . . . . . . . . . . . . . . 58
4.3.2 Building the EPT . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3.3 Starting Virtualization . . . . . . . . . . . . . . . . . . . . . . 65
4.4 ExOShim: Evaluation and Analysis . . . . . . . . . . . . . . . . . . . 69
v
4.4.1 Prototype Complexity . . . . . . . . . . . . . . . . . . . . . . 69
4.4.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.4.3 Security Implications . . . . . . . . . . . . . . . . . . . . . . . 71
4.5 ExOShim: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.5.2 Final Thoughts . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5 Diversification: KPLT 75
5.1 KPLT: Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.1.1 Using the Virtual Memory Abstraction . . . . . . . . . . . . . 76
5.1.2 The Contents of a KPLT . . . . . . . . . . . . . . . . . . . . . 78
5.2 KPLT: Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2.1 KPLT Creation at Load-Time . . . . . . . . . . . . . . . . . . 80
5.2.2 Run-time KPLT Maintenance and Manipulation . . . . . . . . 82
5.3 KPLT: Evaluation and Analysis . . . . . . . . . . . . . . . . . . . . . 86
5.3.1 Security Implications . . . . . . . . . . . . . . . . . . . . . . . 86
5.3.2 Increase in Diversity . . . . . . . . . . . . . . . . . . . . . . . 87
5.3.3 Performance Cost . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.3.4 Remaining Work and Challenges . . . . . . . . . . . . . . . . 88
5.4 KPLT: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6 Diversification: Überdiversity 89
6.1 Diversification Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 91
6.1.1 Run-time Complexity and Termination Analysis . . . . . . . . 94
6.1.2 Proof of Uniformly Distributed Variants . . . . . . . . . . . . 97
6.2 Überdiversity: Implementation . . . . . . . . . . . . . . . . . . . . . . 100
6.2.1 ELF & the Diversity Loader . . . . . . . . . . . . . . . . . . . 100
6.2.2 The Virtual Memory Abstraction . . . . . . . . . . . . . . . . 101
vi
6.2.3 Diversifying the Entire Software Stack . . . . . . . . . . . . . 103
6.3 Überdiversity: Evaluation and Analysis . . . . . . . . . . . . . . . . . 104
6.3.1 Quantification of Diversity Achieved . . . . . . . . . . . . . . 104
6.3.2 Performance Cost . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.3 Security Implications . . . . . . . . . . . . . . . . . . . . . . . 114
6.4 Überdiversity: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 116
7 KUCS 118
7.1 KUCS: Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
7.1.1 Separating Kernel and User Cores . . . . . . . . . . . . . . . . 123
7.1.2 Fine-Grained Virtualization . . . . . . . . . . . . . . . . . . . 126
7.1.3 Increasing Performance . . . . . . . . . . . . . . . . . . . . . . 128
7.2 KUCS: Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.2.1 KUCSBear . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.2.2 Interrupts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.2.3 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.2.4 Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.2.5 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.3 KUCS: Evaluation and Analysis . . . . . . . . . . . . . . . . . . . . . 157
7.3.1 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.3.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.3.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.4 KUCS: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8 Conclusion 180
Bibliography 183
vii
List of Tables
3.1 Summary of Privilege Escalation Mitigation Methods . . . . . . . . . 40
3.2 Characteristics of Privilege Escalation Mitigation Methods . . . . . . 41
3.3 Existing Execute-Only Memory Techniques . . . . . . . . . . . . . . . 44
3.4 Existing Code Diversification Techniques . . . . . . . . . . . . . . . . 45
4.1 Processor Benchmarks for ExOShim . . . . . . . . . . . . . . . . . . . 70
4.2 ExOShim’s Bear Test Suite Performance . . . . . . . . . . . . . . . . 72
6.1 Fork/Exec Test with Überdiversity . . . . . . . . . . . . . . . . . . . 110
6.2 Processor Benchmarks with Überdiversity . . . . . . . . . . . . . . . 112
7.1 System Call Mechanism Performance . . . . . . . . . . . . . . . . . . 164
7.2 Processor Benchmarks for KUCSBear . . . . . . . . . . . . . . . . . . 165
7.3 System Benchmarking for KUCSBear . . . . . . . . . . . . . . . . . . 167
viii
List of Figures
1.1 Threats and Mitigations Explored in this Thesis . . . . . . . . . . . . 3
2.1 x86 Virtual Memory Translation . . . . . . . . . . . . . . . . . . . . . 14
2.2 Recursive and Conventional Paging Structure Addressing . . . . . . . 16
2.3 Traditional Operating System Design . . . . . . . . . . . . . . . . . . 21
3.1 Return-to-User Privilege Escalation Attack . . . . . . . . . . . . . . . 28
3.2 SecVisor’s Protection Against ret2usr Attacks . . . . . . . . . . . . . 31
3.3 kGuard’s Protection Against ret2usr Attacks . . . . . . . . . . . . . . 36
4.1 Example Memory Disclosure Vulnerability . . . . . . . . . . . . . . . 52
4.2 Overview of ExOShim Protections . . . . . . . . . . . . . . . . . . . . 55
4.3 ExOShim Benchmark Suite Performance . . . . . . . . . . . . . . . . 71
5.1 Function Calls with KPLT . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Assembly KPLT Entry . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.1 A modified FYS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2 Cache Performance Benchmarks with Überdiversity . . . . . . . . . . 111
6.3 Worst-Case Memory Overhead with Überdiversity . . . . . . . . . . . 113
7.1 KUCS Design Overview . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.2 Asynchronous System Calls . . . . . . . . . . . . . . . . . . . . . . . 129
ix
7.3 Kernel Mappings to a KUCS Remote Process . . . . . . . . . . . . . 143
7.4 Initializing the Message Passing Ring Buffer . . . . . . . . . . . . . . 148
7.5 KUCS System Call Mechanisms . . . . . . . . . . . . . . . . . . . . . 149
7.6 System Call Mechanism Performance . . . . . . . . . . . . . . . . . . 163
7.7 System Benchmarking for KUCSBear . . . . . . . . . . . . . . . . . . 167
x
List of Code Snippets
2.1 State-of-the-Art Message Sending from User-Space . . . . . . . . . . . 19
2.2 User-space “ping” System Call . . . . . . . . . . . . . . . . . . . . . . 20
4.1 Building ExOShim’s EPT . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1 Creating a KPLT Entry . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.1 Interrupt Handling Control Flow . . . . . . . . . . . . . . . . . . . . 133
7.2 Naive Remote Memory Mapping . . . . . . . . . . . . . . . . . . . . . 141
7.3 Message Passing with the Ring Buffer from User-space . . . . . . . . 145
7.4 Kernel’s Initialization for Message Passing Ring Buffer . . . . . . . . 146
7.5 Message Passing with the Ring Buffer from the Kernel . . . . . . . . 147
xi
List of Algorithms
4.1 ExOShim’s Initialization Routine . . . . . . . . . . . . . . . . . . . . . 59
6.1 Greedy Diversity Loader Algorithm . . . . . . . . . . . . . . . . . . . . 91
6.2 Scaling Diversity Loader Algorithm . . . . . . . . . . . . . . . . . . . . 92
6.3 Generic Diversity Loader Algorithm . . . . . . . . . . . . . . . . . . . 94
6.4 Fisher-Yates Shuffle Algorithm . . . . . . . . . . . . . . . . . . . . . . 98
xii
Chapter 1
Introduction
Problem Current operating system designs enable multiple privilege escalation
mechanisms by which an attacker can leverage simple bugs to compromise the system.
Hypothesis Modern multicore hardware can significantly mitigate the risk of priv-
ilege escalation with acceptable performance cost.
Isolation is a cornerstone of security in modern computer systems. As the com-
plexities associated with even the most benign instances of computation skyrocket
and processors are called on to handle hundreds or thousands of such instances si-
multaneously, isolating instances from one another is the only practical way to protect
them.
One of the most fundamental forms of isolation is separating the user or appli-
cation from the kernel or operating system. As a trusted actor that manages all
applications on the system, the kernel has the direct ability to compromise every
application running on a system. If a malicious actor manages to compromise the
kernel, they can easily compromise all applications on the system. Consequently,
isolation is most commonly enforced by hardware. In particular, system memory can
be marked for the user or for the supervisor (kernel) and the processor can operate
1
in different modes, corresponding to user and kernel.
Unfortunately, hardware protections are not 100% successful. The ability of a
malicious user to gain read, write, or execution privileges on memory reserved ex-
clusively for the kernel is known as privilege escalation. Quantifying the impact of
this issue is difficult. Although as of early 2018 only about 5% of reported Common
Vulnerabilities and Exposures (CVEs) since 1999 are listed with type “Gain Privi-
leges,” privilege escalation attacks may also be classified as “Gain information” (9%)
or “Code Execution” (29%) [2]. Furthermore, these statistics only discuss vulnera-
bilities. There are also privilege escalation mechanisms that use seemingly unrelated
vulnerabilities to achieve the escalation of privileges. Using a mechanism such as
return-to-user [93] which uses a compromised return address to force code execution
into user-space without changing the CPU privilege mode, a simple buffer overflow
(15% of all reported vulnerabilities) located in kernel code could give the user kernel
privilege.
The Meltdown vulnerability [109] provides a clear example of how devastating
privilege escalation can be. This vulnerability enables a user-space process to read
arbitrary memory, circumventing paging permissions. This would be listed as a single
vulnerability in the statistics referenced previously, but the protected memory of
almost any operating system running on any one of millions of affected processors
produced over almost a decade could be read by a simple user program.
In an age where many of the world’s secrets are entrusted to computers and the
operating systems that run them, privilege escalation constitutes a major threat. This
thesis explores a collection of significant privilege escalation mechanisms and presents
novel techniques for mitigating them. While they are applicable to operating systems
in general, each of the research efforts described in this thesis was prototyped on a
research microkernel called Bear [123]. The capabilities described here, as well as
the Bear microkernel itself, are all available as open source software under the MIT
2
Privilege Escalation
ExOShim
Execute
Read
Memory Disclosure
Meltdown
Kernel Code Injection
Diversi�cation
KUCS
ret2usr
Kernel ROP
Threat Solution
Figure 1.1: The left side of this figure shows a breakdown of the vulnerabilities and mechanisms examined in this thesis. The right side pairs the techniques explored in this thesis to the privilege escalation mechanisms they address.
software license at https://github.com/SCSLaboratory/BearOS.
1.1 Approach
This thesis presents novel mitigation techniques for five different privilege escalation
mechanisms. The mechanisms and their associated mitigation techniques are listed
in Figure 1.1.
Privilege Escalation Methods
Memory Disclosure Often, “memory disclosure” refers to a vulnerability, rather
than a mechanism. In a memory disclosure, information leaks from a privileged source
to an unprivileged receiver. This is a common issue in monolithic operating systems
that load drivers, potentially buggy pieces of software written by third parties, into
the operating system with privilege. The memory disclosure mitigation explored
in this thesis, ExOShim, enforces a security policy that identifies and prohibits any
3
memory disclosure, regardless of the mechanism used to accomplish such a disclosure.
Meltdown First appearing in the public eye in January 2018, Meltdown [109] is
a vulnerability found in most Intel x86 processor implementations and some other
processors, including ARM and PowerPC. Meltdown takes advantage of speculative
execution and cache timing attacks to recover the results of computations that cause
a fault before such a fault is actually delivered. In other words, a user process can
issue reads to kernel memory and then retrieve the data of the read before the fault
is delivered. This is a demonstration of the dangers of leaving such a vital security
property – the separation of kernel- and user-space memory – to a complex hard-
ware implementation that is all but invisible to the programmer. The Kernel- and
User-space Core-based Separation (KUCS) operating system design provides stronger
separation between the user- and kernel-space such that the hardware vulnerability
allowing Meltdown can no longer impact the system.
Kernel ROP Return-oriented-programming (ROP) is a process by which a care-
fully crafted stack uses return instructions to force control flow through a series of
snippets of existing code (called “gadgets”) to preform computation. Even small pro-
grams have enough gadgets to perform arbitrary execution with a carefully controlled
stack, so any program as big and complex as an operating system can be subjected
to complex ROP attacks. This is an example of how mechanism differs from vul-
nerability ; any simple kernel stack overflow (the vulnerability) can enable a kernel
ROP attack (the mechanism). Software randomization techniques are the standard
technique for mitigating ROP as they make it more difficult to discover the location
of the gadgets of interest and subsequently build the stack necessary to preform the
desired computation. This thesis explores the widespread use of non-determinism on
many existing systems and offers novel techniques and analysis that compliment this
rich field of research.
4
Kernel Code Injection Perhaps the most naive method of escalating to kernel
privilege is to inject malicious instructions directly into the kernel code. One example
of how this may be done is with a kernel routine that copies data from user memory
into kernel memory. If the attacker can force execution to jump to this previously
copied memory, they can execute code that they control with all the privileges of
the kernel. While most kernels use Write xor Execute (W⊕X) security policies, this
is an example of a defensive strategy that targets a vulnerability; not necessarily
the mechanism itself. On the contrary, KUCS enables security policies that ensure
that no code absent from the kernel at boot-time can ever be executed with kernel
privilege.
ret2usr If the attacker can control a single return address in the kernel, they can
force the kernel to jump to user-controlled memory without passing through the
normal context-switching routine required to change the mode of the processor into
user-mode. After its discovery, chip manufacturers began to implement hardware fea-
tures such as Intel’s Supervisor Mode Execution Protection (SMEP) in order to cause
a system fault if user-marked memory is executed without the CPU in user mode.
Despite this hardware patch, which may not be used by corrupted, old, or buggy ker-
nel implementations, this mechanism demonstrates the dangers of weak separation
between kernel- and user-space on modern hardware. As previously discussed, Melt-
down is another attack exploiting this weak separation. KUCS enforces a stronger
separation that is not vulnerable to ret2usr type attacks.
Privilege Escalation Mitigation Techniques
ExOShim is a memory disclosure mitigation that uses the virtualization features
of modern processors. In particular, the extended page tables (EPT) included with
Intel’s VT-x virtualization extensions provide the capability to mark memory pages as
5
execute-only, a feature not available in the kernel paging system. ExOShim provides
a shim layer that enables virtualization and uses these fine-grained permission bits
in the EPT to mark the kernel code as execute-only. Furthermore, it keeps the
operating system as the most basic trusted software entity. Rather than implementing
a trusted hypervisor (which becomes a large attack surface in its own right) it uses
the virtualization features to enforce a security policy that the kernel initializes. In
fact, ExOShim manages to offer this protection in a way that cannot be hijacked,
modified, or disabled after initialization.
Diversification Although there have been decades of research into software ran-
domization techniques, this thesis extends this body of knowledge with two new tech-
niques: the Kernel Procedure Linkage Table (KPLT) and Überdiversity. The KPLT
treats the kernel, which is conventionally mapped into every process, as a shared ob-
ject. It provides a method for randomizing kernel mappings on a per-process basis, so
that each process uses unique virtual addresses to access shared kernel routines. The
second technique, Überdiversity, presents a prototype that explores just how far load-
time diversity could go, and a corresponding study of load-time diversity techniques
and implementations.
KUCS The largest contribution of this thesis, Kernel and User Core-Based Separa-
tion (KUCS) is a kernel design paradigm that utilizes multicore hardware to provide
hard separation between the kernel and the user contexts. Rather than map the ker-
nel into every user process behind a CPU mode bit, KUCS loads the kernel onto a
processor core entirely by itself; it loads user processes onto other cores without any
mapping to the kernel. This eliminates attacks like ret2usr and Meltdown, which take
advantage of the weak separation of kernel- and user-space on a shared processor core.
Additionally, it enables stronger security policies than previously possible, including
one that eliminates the threat of kernel code implants.
6
1.2 Metrics of Success
As in any approach to computer security, it is vital that both the security and per-
formance are well understood. This thesis goes to considerable length to study these
factors and, where feasible, quantify them.
Measuring the performance impact of a mitigation technique is generally done by
running benchmark tests and comparing performance with and without the technique.
Although the Bear operating system cannot support arbitrarily complex benchmarks
the same way a system like Linux could, it does provide industry standard bench-
marking tools such as the AIM9 processor benchmarking suite [6] and a malloc
memory-intensive benchmark written by Chuck Lever and Chuck Boreham at the
University of Michigan [103].
In addition to these benchmarking tools, Bear also contains a test suite specific to
its own system utilities. These can be used to measure overall system performance.
Finally, microbenchmarks are occasionally used to isolate the specific system
events and illustrate how a technique may change performance in that particular
situation. These narrow tests were developed specifically to understand each partic-
ular technique. For example, the Überdiversity study contains a specific study of the
performance implications of cache thrashing in extreme cases of load-time randomiza-
tion. Similarly, the KUCS analysis isolates the performance of system calls in order
to study the effect of changing the system call mechanism used to invoke the kernel
from user-space.
Unfortunately, security in general is not as easily quantified. The Überdiversity
study discusses this at length, and contains a significant effort to quantify its security
properties and provide a framework for quantifying code randomization efforts in
general by using two mathematical characterizations: program variants and entropy.
In spite of the assessments available with program variants and entropy, these
present only approximate security quantifications. Furthermore, they are only ap-
7
plicable to code randomization efforts. Quantifying the security properties of other
methods is extremely difficult. As such, a careful qualitative analysis of security prop-
erties is included wherever quantification is not practical. This is especially true when
examining mechanism instead of specific vulnerabilities, since any number of known
or unknown vulnerabilities can support a particular privilege escalation mechanism.
1.3 Publications and Contributions
The research efforts described in this thesis are summarized in the following publica-
tions:
• Scott Brookes and Stephen Taylor. Containing a Confused Deputy on x86: A
Survey of Privilege Escalation Mitigation Techniques. IJACSA, April 2016
• Scott Brookes, Robert Denz, Martin Osterloh, and Stephen Taylor. ExOShim:
Preventing Memory Disclosure using Execute-Only Kernel Code. In Proceed-
ings of the 11th International Conference on Cyber Warfare and Security, IC-
CWS’16, pages 56–66, April 2016
• Scott Brookes, Robert Denz, Martin Osterloh, and Stephen Taylor. ExOShim:
Preventing Memory Disclosure using Execute-Only Kernel Code. International
Journal of Information and Computer Security (IJICS), 2018, In Press
• Scott Brookes, Martin Osterloh, Robert Denz, and Stephen Taylor. The KPLT:
The Kernel as a shared object. In Military Communications Conference, MIL-
COM 2015 - 2015 IEEE, pages 954–959, Oct 2015
• Scott Brookes, Martin Osterloh, Robert Denz, and Stephen Taylor. Überdiversity:
Exploring the Limit of Load-Time Software Diversification. Technical report,
Thayer School of Engineering at Dartmouth College, April 2018
8
• Scott Brookes and Stephen Taylor. Rethinking operating system design: Asym-
metric multiprocessing for security and performance. In Proceedings of the 2016
New Security Paradigms Workshop, NSPW ’16, pages 68–79, New York, NY,
USA, 2016. ACM
The thesis synthesizes these works to make the following contributions:
• A survey of research techniques that aim to defeat common privilege escalation
mechanisms deployed against commodity operating systems and hardware [30].
• ExOShim: a self-protection mechanism in which the kernel deploys the virtual-
ization features of its processor to mark its code as Execute-Only, eliminating
the risk of memory disclosures that would otherwise reveal its code to a mali-
cious user wishing to reverse-engineer it or find gadgets to build a kernel ROP
payload [26,27].
• KPLT: a mechanism to allow shared kernel functionality to be loaded at unique
virtual addresses in each process, increasing attacker workload at the gadget
collection phase of a kernel ROP attack [28].
• Überdiversity: a study of load-time software diversification techniques that con-
tributes both an advanced and novel implementation and a study of the details
of load-time randomization [29].
– The Überdiversity implementation advances the state-of-the-art in load-
time randomization techniques by:
∗ interleaving kernel- and user-space sections, producing an address space
without unique regions designated for the kernel- and user-space.
∗ simultaneously diversifying every layer of the software stack including
the hypervisor, kernel, and user-space application.
9
∗ providing a higher level of entropy that approaches the hardware-
imposed maximum.
– The Überdiversity study discusses some “dark corners” of diversity imple-
mentations that are rarely presented or formalized, including:
∗ the properties of the algorithm used to generate a random program
layout.
∗ the number of program variants possible with an implementation: a
measurement that compliments the traditional “entropy” measure-
ment.
• KUCS: A novel operating system design that isolates kernel- and user-spaces
on separate physical processing cores of a multicore processor [31]. This allows
for:
– Complete virtual memory isolation and “sandboxing” of every user appli-
cation.
– Device drivers with the security of user-space encapsulation and the per-
formance of kernel modules.
– Hardware-enforced secure contexts available for application-specific use.
– Real-time “watchdog” security monitors in the kernel for intrusion detec-
tion in applications.
– Fine-grained security policies enabled by per-core virtualization and sepa-
ration of the kernel and the application.
– Opportunities to increase performance in novel ways.
• KUCSBear: a prototype operating system that utilizes a KUCS design on the
Bear research microkernel.
10
• Detailed documentation of the KUCSBear prototype implementation, with spe-
cial care taken to generalize implementation details in order to facilitate future
efforts to bring the design to other systems.
• A study of the security properties provided by each project: ExOShim, KPLT,
Überdiversity, and KUCS.
• A suite of performance measurements and analyses in order to estimate the
overhead of each project: ExOShim, KPLT, Überdiversity, and KUCS.
• Open-source implementations of each project: ExOShim, KPLT, Überdiversity,
and KUCS. The implementations are available with the source code for the Bear
operating system at https://github.com/SCSLaboratory/BearOS.
1.4 Thesis Organization
With the understanding of how the different projects are linked in their efforts to
mitigate the threat of different privilege escalation mechanisms, the remainder of this
thesis contains some more general and background content followed by a detailed
description of each project. In particular:
Chapter 2 presents a brief background discussion of operating systems in general
and the Bear operating system in particular. It is intended for the reader that is
unfamiliar with the intricacies of an operating system but wishes to understand the
offensive and defensive techniques described in this thesis, or the reader that is familiar
with operating systems but wishes to understand the platform used for the prototype
of each project in order to give context to the technical details described in the thesis.
Chapter 3 surveys prior work related to the research described in this thesis. Re-
lated work is separated into several categories corresponding to each of the projects
11
presented later in the thesis.
Chapter 4 describes ExOShim; the virtualization-based kernel self-protection mech-
anism to mitigate kernel code memory disclosures by marking kernel code memory
as execute-only.
Chapter 5 describes the first diversification technique, the KPLT. The KPLT takes
inspiration from the procedure linkage tables used for shared user-space libraries and
maps shared kernel code at unique virtual addresses in each process.
Chapter 6 finishes the discussion of diversification techniques by examining Überdiversity:
an advanced load-time diversification implementation, along with a study of certain
theoretical aspects of load-time diversification implementations in general.
Chapter 7 presents KUCS, an operating system design paradigm that addresses
the concerns of weak separation of kernel- and user-space in modern hardware. First,
it discusses the design in general as it could be applied to operating systems. It
also presents a detailed study of KUCSBear, a proof-of-concept prototype operat-
ing system that implements a KUCS design. Finally, it examines the security and
performance of a KUCSBear and KUCS operating systems in general. It contains a
qualitative security analysis for KUCS as a general design and estimates the perfor-
mance implications by comparing micro- and macro-benchmarks run on vanilla Bear
and KUCSBear. Finally, there is a discussion of performance-enhancing techniques
and additional features that could be deployed on top a KUCS design in future work.
Chapter 8 offers concluding thoughts. In particular, it discusses how the four
separate projects presented in this thesis can be deployed together and strengthened
by one another.
12
Chapter 2
Background and State of the Art
This chapter provides a brief introduction to the existing methods of accomplishing
selected operating system tasks. The content in this chapter is not designed to be a
complete introduction to operating systems. Instead, it highlights specific operating
system mechanisms that are utilized or modified in the research efforts described later
in the thesis. This chapter is designed for the reader that is unfamiliar with operating
systems and looking for some context for high level descriptions of the research efforts
described later, or for the experienced kernel developer who is looking for context to
better understand the particular implementation details described later.
Except where otherwise specified, the details and examples in this chapter are
given in terms of the Bear operating system, as presented in [123]. As the platform
for the major research efforts described in this thesis, its implementation details are
especially relevant. However, the chapter can also be used as a case study in operating
system techniques more broadly.
2.1 Virtual Memory
The virtual memory abstraction is a fundamental hardware feature of modern com-
putational systems. With virtual memory, software uses addresses that do not cor-
13
Page Translation and Protection 119
24593—Rev. 3.24—October 2013 AMD64 Technology
Figure 5-1. Virtual to Physical Address Translation—Long Mode
513-200.eps
PML4E PDE
Physical Address
PDPE
PTE
Physical Page Offset
Sign Extension
63 0
Page Directory Offset
Page Map Level-4 Offset
Page Directory Pointer Offset
Page Table Offset
Page Map Base Register CR3
64-Bit Virtual Address
Page Directory Pointer Table
Page Directory Table
Physical Page Frame
Page Table
Page Map Level 4 Table
Figure 2.1: In the x86 virtual memory system, the MMU does a 6 step walk through the four-level page tables to resolve a particular virtual address to the appropriate physical memory. Graphic from AMD Processor Architecture guide [11].
respond directly to physical addresses in memory. Instead, the hardware translates
virtual addresses used by software through a configurable set of tables in order to
produce a corresponding physical address.
On Intel’s x86 processors, this memory translation is done by an onboard Memory
Management Unit (MMU). In 64-bit mode, the tables are four levels deep. The top
level – a Page Map Level 4 Table (PML4T) – contains 512 pointers. Each points to
a Page Directory Pointer Table (PDPT), each of which contains 512 pointers to Page
Directory Tables (PDT), each of which points to 512 Page Tables (PT), which each
points to 512 physical frames of memory. This structure is shown in Figure 2.1.
The virtual memory abstraction allows for each pointer within the tables to be
marked with permissions specific to the memory reached via that pointer. The page
tables provide bits to choose between user and supervisor memory (U/S), writable
14
or non-writable memory (R/W), and executable or non-executable (NX). This allows
for protections to be applied at the granularity of 4k pages.
On a particular core, Control Register 3 (CR3) defines the virtual memory context
of the core. This control register contains the physical address of a PML4T. From
that address, the memory management unit follows a chain of pointers down through
the multi-level paging structures until it resolves the physical address corresponding
to the inputted virtual address as a function of the currently loaded paging structures.
So, to perform a write to a particular memory address the MMU first reads the
address from CR3 in order to find the PML4T (step 1). It then uses the most
significant bits of the address to index into that table in order to find the appropriate
PDPT (step 2). It works its way down through the PDT (step 3) and PT (step 4).
From the appropriate index in the PT it finds the relevant physical frame of memory
(step 5) and can finally use the least significant bits of the address to index to the
correct byte on the frame (step 6). Despite being implemented in hardware, this multi-
step translation process is expensive. In order to avoid the costly translation process
wherever possible, the processor stores recently used translations in the translation
look-aside buffer (TLB).
2.1.1 Case Study: Recursive Paging
Recursive paging (or self-referencing page tables) will serve as a case study to demon-
strate the full flexibility of the virtual memory abstraction as implemented in x86
processors.
In order to motivate the self-referencing page tables, consider the question: how
would system software update the pointer to a PT stored in a particular PDT? The
key observation to answer this question is that each paging structure is a frame of
memory just like any other frame of memory. Naively, writing to a PDT requires
that its physical address is stored in a PT. Thus the same 6 step process described
15
513-200.eps
PML4E PDE
Physical Address
PDPE
PTE
Physical Page O�set
Sign Extension
63 0
Page Directory O�set
Page Map Level-4 O�set
Page Directory Pointer O�set
Page Table O�set
Page Map Base Register CR3
64-Bit Virtual Address
Page Directory Pointer Table
Page Directory Table
Physical Page Frame
Page Table
Page Map Level 4 Table
4
1
2
3
5
6
(a) The conventional method for address- ing paging structures: a mapping is cre- ated like any other for the physical mem- ory on which the paging structure resides.
513-200.eps
PML4E PDE
Physical Address
PDPE
PTE
Physical Page O�set
Sign Extension
63 0
Page Directory O�set
Page Map Level-4 O�set
Page Directory Pointer O�set
Page Table O�set
Page Map Base Register CR3
64-Bit Virtual Address
Page Directory Pointer Table
Page Directory Table
Physical Page Frame
Page Table
Page Map Level 4 Table
4
1
5
6
3
2
(b) The recursive method for address- ing paging structures: a single pointer in the top level table points to its own ta- ble, allowing steps of the translation to be “burned” by cycling in place over the same memory.
Figure 2.2: Paging structures can be addressed conventionally or recursively. In these figures, the numbered dots represent steps of the virtual memory translation undertaken by the hardware. In particular, these dots are shown as the MMU tries to write to a particular PDT. The recursive method serves to illustrate the flexibility of the virtual memory abstraction on x86 processors.
before will carry the MMU from the CR3 down through the PML4T, PDPT, PDT,
PT, and onto the physical frame (which happens to be the PDT) before offsetting
onto the frame and executing the write. This process is shown in Figure 2.2a.
Figure 2.2b shows an alternative method for providing virtual addresses for paging
structures. This method is known as recursive paging or self-referential page tables.
In this method, one entry in the PML4T points back to the base of the PML4T
itself. This is the self-referencing or recursive pointer. A carefully constructed virtual
address will use that pointer to “burn” one or more steps of the memory translation
process. Short circuiting the hardware page table walk like this allows a carefully
constructed address to “cast” the PML4T as a PDPT, PDT, PT, or physical frame
16
of memory depending on how many of the steps of the translation are “wasted” by
returning back to the base of the PML4T itself.
Bear uses recursive pointers in its virtual memory management. The benefit of
such a method is that all possible paging structures attached to the currently loaded
CR3 have a valid virtual address already created for them. Unfortunately, the caveat
is that it becomes much more difficult to address the paging structures of other
contexts.
Regardless of the benefits or costs of using this method, its inclusion here is
simply pedagogical. This method demonstrates the true flexibility of the virtual
memory abstraction. The abstraction will feature heavily later in the thesis as the
privilege escalation methods discussed all rely on the virtual memory layer. For
example, Überdiversity uses fine-grained permissions to interleave kernel and user
code in virtual memory, the KPLT uses different virtual addresses to point to the
same physical memory and the same virtual addresses to point to different physical
memory, and the KUCS prototype omits mappings to the page tables entirely in order
to isolate processes on a core. A deep understanding of virtual memory is vital to a
deep understanding of these projects, and a deep understanding of recursive paging
is a good indicator of a deep understanding of virtual memory.
2.1.2 The Virtual Address Space
Generally, each process has its own set of page tables and therefore its own PML4T
or “CR3 Target.” In many ways, the definition of a process can be reduced to its
CR3 Target since, especially in a scheme like Linux’ where the process structure is
loaded at a known location in virtual memory, it can be all that is required to collect
all information about a process.
The virtual memory regions defined within a process’ page tables come together
to define the “Virtual Address Space” for the process. The virtual address space
17
contains all of the memory needed by the process, including its code, heap, stack,
and data regions. It also contains any libraries in use by the process. Conventionally,
it also includes mappings to the kernel memory, including code, heap, stack, and data
regions as well as kernel libraries and drivers.
The kernel mappings within a process’ virtual address space are enabled by the
flexibility of the virtual memory abstraction. In particular, the permissions associ-
ated with the paging structures protect unprivileged process code from accessing or
modifying the kernel memory. Additionally, the same physical implementation of the
kernel is shared by all processes. Typically, the virtual address space will be segre-
gated between kernel- and user-space. A single address will serve as the boundary
between these two regions of memory, and all addresses above (or below) that ad-
dress are marked with supervisor privileges while all addresses below (or above) it
are accessible by the user.
Understanding that the kernel is mapped into the virtual address space of every
process is vital for understanding the research projects discussed in this thesis. It
explains some limitations of ExOShim, it motivates the efforts of KPLT, it adds
richness to the Überdiversity prototype and it is a major motivator for the KUCS
kernel design. This weak separation between kernel- and user-space is the direct and
exclusive source of the ret2usr privilege escalation mechanism.
2.2 Message Passing
Bear, like many microkernels, uses a message passing interface for all communication
between two processes, or between a process and the kernel. In Bear, the kernel acts as
a mediator for all messages. It accepts messages sent from a process and will dispatch
the message based on the state and identity of the message’s intended recipient. For
example, if a message is sent to the kernel, it is interpreted as a system call and
18
void msg_send(int destination , void *buffer , int length) {
Message_t m;
m.dst = dst;
m.len = buflen;
m.buf = buf;
swint(MSEND ,&m);
}
int msgrecv(int src , void *buf , int buflen) {
Message_t m;
m.src = src;
m.len = buflen;
m.buf = buf;
return swint(MRECV ,&m);
}
Snippet 2.1: This is the user-space implementation of message sending and receiving.
dispatched to a kernel syscall handler. Meanwhile, a message sent to another process
is either injected directly into that process’ address space or saved for future use
depending on whether the receiving process is already blocked waiting for a message
or not.
From user-space, message passing is a matter of packaging the necessary infor-
mation into a Message t structure and then passing that structure to the kernel.
Snippet 2.1 shows the user-space routines that do the packaging.
In order to illustrate the functionality of the message passing system, consider the
case of a “ping” system call that does nothing but receive a status from the kernel.
This system call is shown in Snippet 2.2.
The important observation from Snippet 2.2 is that the process wants to send
data to the kernel by providing the address of a structure it has prepared, and also
wants for the kernel to send data back by writing to a structure specified by the
process. With the kernel and process sharing a virtual address space, the kernel can
19
int ping_kernel(void) {
Ping_req_t request;
Ping_resp_t response;
request.type = PING_SYSCALL;
msg_send(KERNEL , &request , sizeof(Ping_req_t ));
msg_recv(KERNEL , &response , sizeof(Ping_resp_t ));
return response.value;
}
Snippet 2.2: User-space implementation in state-of-the-art message passing microker- nel of a simple “ping” system call
simply dereference the memory address provided by the process (&m in msgsend as
shown in Snippet 2.1) to read the process’ request, and write to the memory addresses
provided by the process (m.buf in msgrecv as shown in Snippet 2.1) in order to deliver
its response. This greatly simplifies the kernel handling of the message decoding and
delivery.
Furthermore, the process is suspended as soon as it issues the message send/re-
ceive. This allows the kernel to safely read and write to the messages using addresses
provided by the user. The guarantee that the process cannot change the parameters of
the message while the kernel is processing alleviates concerns about a Time-of-Check
vs. Time-of-Use (TOCTOU) attack [24,84].
System Calls
In order for the user process to request work from the kernel (such as with a system
call) the process executes a local interrupt on its core. The int instruction forces ex-
ecution through the Intel interrupt control structures including the Global Descriptor
Table (GDT) and Interrupt Descriptor Table (IDT) in order to determine what action
to take. In this case, the IDT will be preconfigured by the kernel to trigger change
from the process’ privilege mode (known as “ring 3”) into the kernel’s (known as
20
User-Space
Kernel-Space
Hardware-Enforced Privilege Mode Boundary
INT/SYSENTER
IRET/SYSEXIT
User-Space
Kernel-Space
Hardware-Enforced Privilege Mode Boundary
INT/SYSENTER
IRET/SYSEXIT
User-Space
Kernel-Space
Hardware-Enforced Privilege Mode Boundary
INT/SYSENTER
IRET/SYSEXIT
Core 0 Core 1 Core N
Hypervisor
Figure 2.3: The conventional design of an operating system maps the kernel into every process. Processes request kernel work by triggering a CPU privilege mode switch and redirection to a predefined kernel landing site with an int or sysenter
instruction. The kernel can return execution to the user through the opposite privilege mode change using the iret or sysexit instructions. On a multicore system, this paradigm is simply repeated once per core.
“ring 0”).
Every process has an instance of the kernel mapped into its virtual memory space.
As a result, the kernel code that begins executing in response to the interrupt is the
instance of the kernel specific to the process that triggered the interrupt. There can
be no confusion about which process initiated the request for work because the entity
that services the request (the kernel) is contained within the process itself.
This also facilitates memory manipulation and data sharing between the kernel
and the process. The kernel has direct mappings in its own context to all memory
that the process can access. Accessing a message from the kernel is as easy as reading
an address out of a register (the process stored the address of its message in a register
before triggering the interrupt) and dereferencing the address.
When the kernel has completed working on the user request, it issues an iret
instruction. This instruction “undoes” the int instruction by changing the CPU
21
privilege mode back to ring 3 and reading the stack to restore the previously saved
state of the user process.
The INT/IRET system call mechanism is used by most conventional kernels. Some
may use the x86 instructions SYSENTER and SYSEXIT, but the basic mechanism is the
same. On a system with multiple cores, this paradigm is simply copied independently
on each core. A summary of this type of system is shown in Figure 2.3.
2.3 Scheduling
Scheduling between two processes in a conventional operating system takes advan-
tage of the kernel mappings that all processes share. First, the kernel will identify
the need to schedule a new process based on a timer interrupt or blocking system
call. Remember that the “kernel” that has identified this need is actually the kernel
instance specific to process A; the process that must yield the core.
Knowing that a new process needs the core, the kernel mapped into process A can
consult the scheduling subsystem to determine which process should run next. Bear
uses a round-robin scheduler where processes that want to run are kept in a queue.
When a process is done running on core, it enters the back of the queue to await its
chance to run again. Each core has an “idle” process that will occupy the core when
no other user process is available to be run. The idle process is similar to any other
in that it has a complete kernel mapping in its context. The only difference is that it
does not preform any useful work.
Once the next process to run has been identified, process B, the kernel does some
state saving and then simply writes the address of the paging structures for that pro-
cess into CR3. The page table swap does not change the instruction pointer or other
registers, but the context is valid because the kernel is mapped into process B at the
same place as it was mapped into process A. The kernel can restore some state from
22
the last time it was scheduled (such as the stack pointers) and then simply return
to pick up execution where it left off. Routinely, this means eventually executing an
iret which will restore the state saved by process B a full time quantum (or more)
ago.
In summary, processes share cores by scheduling one another via their shared
kernel mappings. This process is straightforward because the kernel is resident in
each process on the same core, the kernel mappings are identical between processes,
and the process suspended its own execution when the kernel was invoked.
23
Chapter 3
Related Work
In order to accommodate the most thorough possible discussion of the threats of
privilege escalation, this thesis explores several diverse techniques, each of which
contains its own body of related research. This chapter reviews the literature of each
of these fields. It begins by examining a broad swath of the many diverse techniques
for addressing privilege escalation; especially the three mechanisms for escalating
execution privilege as shown in Figure 1.1, as in [30]. Further detail is provided for the
specific techniques explored in this thesis. In particular, Section 3.2 examines previous
work in the field of execute-only memory in order to provide context for ExOShim,
Section 3.3 provides a brief overview of research in the field of code randomization
as background Überdiversity and KPLT, and Section 3.4 examines other efforts that
utilize asymmetrical multiprocessing: the primary characteristic of the KUCS kernel
design. Finally, since KUCS goes beyond a simple technique that extends the state
of the art, Section 3.5 summarizes other previously proposed operating system design
paradigm shifts.
24
3.1 Privilege Escalation Mitigation
The modern operating system kernel is one of the most basic building blocks of any
complex computing or control system. It exists to provide a controlled interface to the
hardware and to protect multiple processes and users from each others’ actions. In
order to accomplish these tasks securely, it must operate with a higher privilege level
than user processes, making it an attractive target for attackers. As security research
steadily enhances the security of individual processes, the kernel is being attacked
more regularly. Despite the recent increase in popularity of attacking the kernel,
system designers have long recognized the need for kernel security. MULTICS [40,
47] was one of the first operating systems to take security seriously and laid the
groundwork for the most popular kernel security mechanisms still used today. In
particular, it defined operating system “rings”, designated by processor modes, and
memory segmentation and paging structures with flexible read, write, and/or execute
permission bits to allow memory partitioning and protection.
Unfortunately, almost all modern operating systems share a common vulnerability:
a “weak” separation between kernel- and user-space. While the operating system
provides a unique address space for each process in order to isolate processes from
one-another, each address space must still allow access to kernel functionality. This is
generally accomplished by sharing the address space of the kernel with each process.
In contrast to the rare instances of “strong” separation between kernel- and user-space
(such as the 4G/4G split Linux patch [118], 32-bit XNU [94], and certain systems using
the hardware facilities provided by SPARC V9 hardware [115]), this weak separation
protects the kernel from unauthorized access only with the mode of operation of the
processor. A process that successfully manages to operate in supervisor mode has
carte blanche access to all of the code and data of the kernel.
Often assisted by the weak separation of kernel- and user-space, all of the most
popular kernels have been compromised by “rootkits” that give the attacker the
25
highest level of privilege (i.e. “root”) [95, 138, 161]. This thesis aims to address
privilege escalation attacks that:
• Hijack the facilities of the kernel to create a “confused deputy” that is acting
on behalf of the attacker [71]. This does not include attacks that are correctly
exercising badly designed features of the kernel [48] or attacks that operate
outside of the purview of the kernel [90].
• Persist even without a specific kernel-level bug or design flaw. Although most
rootkits do require some kernel level bug (such as a buffer overflow) to be
invoked, attacks that utilize a specific bug such as [7, 9, 116] are beyond the
scope of this work. Additionally, attacks such as [92] that are enabled by a
specific kernel design flaw will not be considered. These cases typically have
trivial solutions.
• Elevate local privilege to root rather than using “horizontal” privilege escalation
such as [4].
• Effect x86 Architectures. The focus of this work is on the x86 architecture
because of its wide use in data centers and workstations [120]. However, some
techniques specific to ARM will be examined because they do make valuable
and interesting contributions to the state of the art.
The privilege escalation attacks that fit these criteria fall into three main cate-
gories: kernel code implants [108], kernel-mode return oriented programming (ROP) [33,
78,148], and return-to-user (ret2usr) attacks [93].
Kernel code implants are attacks in which the adversary manages to overwrite
existing code with (or inject) arbitrary instructions into the kernel space, and then
direct the kernel to execute those instructions. Well-known examples of this type of
attack include exploitation of classic buffer-overflow vulnerabilities associated with
26
system calls [127]. If an attacker manages to overflow a buffer on the kernel stack
using some malformed arguments to a system call, it is possible to write shell-code
onto the stack and overwrite a return-address so as to invoke the shell-code. This
particular attack vector has largely been mitigated by techniques that mark the stack
non-executable or provide canary code to detect overflows [41, 42] but it illustrates
the core concept of kernel code injection.
Kernel return-oriented programming (ROP) attacks defeat the use of a non-
executable stack by using a payload, not of code directly on the stack, but of carefully
crafted stack-frames that direct computation through a series of gadgets found in nor-
mal kernel code [33,78,148]. Research has shown that even small programs are likely
to contain the gadgets necessary to generate a ROP Turing machine controlled only by
a carefully crafted payload delivered to the stack [5]. All operating systems are large
and complex enough to guarantee that the necessary gadgets will be present. As a re-
sult, an attacker with the appropriate knowledge can perform arbitrary computation
using a ROP payload.
A return-to-user attack is enabled directly by weak kernel- and user-space sepa-
ration. In this attack, illustrated in Figure 3.1, a user-controlled target associated
with some kernel-code branch is set to an address in the normal user-space code. The
compromised branch creates a path of execution that leaves kernel-code, entering
user-code, without changing the CPU privilege level from supervisor mode to user
mode. This attack results in the execution of user-controlled code with kernel-level
privileges. Although hardware extensions such as Intel’s SMEP [62] aim to mitigate
this threat, these extensions are only slowly being adopted by operating systems and
SMEP bypass techniques have already been demonstrated [91,143].
Unfortunately, mitigation techniques for privilege escalation do not operate in iso-
lation and it is important that they do not undermine other security features. For in-
stance, it is easy to inadvertently inhibit techniques for enhancing security using non-
27
U se
r- Sp
ac e
Ke rn
el -S
pa ce
Hardware-Enforced Privilege Mode Boundary
INT/SYSENTER
IRET/SYSEXIT
fn: ... JMP kernel_target
attacker_target
attacker_target: ... execve(shell);
Figure 3.1: The return-to-user (ret2usr) privilege escalation mechanism uses a cor- rupted branch instruction in the kernel to jump into user-controlled code from the kernel without passing through the CPU privilege mode switch. As a result, the processor will be executing user memory while still in supervisor mode.
determinism. This general class of techniques was initially described by Cohen [38]
and Forrest [64]. In the years since these seminal papers, many have explored the
idea further. A recent survey of the area was presented in [99]. Address Space Layout
Randomization (ASLR) is one of the most widely used applications of this technique.
First implemented by the Linux PaX team [3], many other operating systems have
implemented some form of ASLR including Mac OS X [8], Windows [162], and others.
ASLR loads distinct memory regions including main program code, libraries, and the
stack and heap at random locations within a program’s virtual address space making
it difficult to predict code entry points. More fine-grained techniques for diversifying
the memory layout of a process [87, 89] require even more flexibility than traditional
ASLR. This field of research is examined further in Section 3.3.
In Summary, this section surveys the primary technologies presented in the liter-
ature to mitigate execution privilege escalation. It provides a comparative analysis
based on their effectiveness, performance impact, and implementation complexity.
28
It also specifically considers whether the technologies provide sufficient flexibility to
coexist with state of the art address space layout randomization techniques. ASLR
is chosen to provide a window to whether the techniques presented “play nicely”
with other kernel security efforts because it is has widespread application on real sys-
tems and requires flexibility in order to be implemented fully. Section 3.1.1 examines
techniques based on hypervisors and virtualization while the remaining techniques
are discussed in Section 3.1.2. These techniques are compared and contrasted in
Section 3.1.3.
3.1.1 Techniques based on Virtualization
Virtualization has dramatically changed the face of computing, not simply in terms
of security and the way individual users interact with computers, but also by enabling
cloud computing by allowing virtual machines to be migrated between servers. By
adding a layer to the standard software stack, known as a hypervisor [17] or Vir-
tual Machine Monitor (VMM) [70], an abstraction layer is introduced to isolate the
operating system kernel from the hardware. In many ways, the hypervisor is to an
operating system what an operating system is to a user process – serving to protect
virtual machines from each other just as a kernel isolates user processes. The fol-
lowing approaches use virtualization as a means to deliver security guarantees to the
kernel.
NICKLE
NICKLE [139] provides memory integrity to kernel code and thereby denies the ex-
ecution of kernel code implants. It uses a VMM to maintain a “shadow” copy of
memory that is verified when any kernel-code is loaded. This is achieved by com-
paring the memory to be loaded against a pre-computed cryptographic hash of the
“clean” code distributed by the manufacturer or developer of the code. At boot time,
29
a known clean copy of the kernel is loaded into the shadow memory and whenever a
kernel module is loaded at runtime, it is verified and added to the shadow memory.
With the integrity of the shadow memory guaranteed by off-line a priori crypto-
graphic hashes of trusted code, NICKLE can ensure that no unauthorized kernel code
is executed by directing all memory accesses targeting kernel code to retrieve from
the shadow memory rather than from regular memory. Although no attempt is made
to deny an attacker from modifying or injecting kernel code, kernel-mode execution
is contained within trusted memory.
This is achieved transparently to the operating system kernel, allowing for com-
modity operating systems to be executed with NICKLE with no modification of kernel
code. Additionally, NICKLE permits the mixing of kernel code and data within mem-
ory pages; this distinguishes NICKLE from many alternative approaches that require
code and data to be loaded onto unique pages.
Unfortunately, NICKLE requires the off-line computation of cryptographic hashes
for any code that may be executed; this poses a significant logistical issue for main-
taining NICKLE on real systems and adds additional vulnerabilities associated with
protection and distribution of hash values. NICKLE imposes a “minimal to moder-
ate impact on system performance, relative to that of the respective original VMMs”
averaging 1%-5% [139].
SecVisor
SecVisor [147] is an alternative virtualization technology leveraging hardware facili-
ties to virtualize physical memory associated with modern processors. By utilizing
this additional layer of translation from “guest physical” to “real physical” memory
addresses, additional hardware memory protections can be enforced. This capability
typically provides additional flexibility in creating memory access security; namely,
any combination of read, write, and execute permissions can be allowed or denied on
30
U se
r- Sp
ac e
Ke rn
el -S
pa ce
Hardware-Enforced Privilege Mode Boundary
INT/SYSENTER
IRET/SYSEXIT
fn: ... JMP kernel_target
attacker_target
attacker_target: ... execve(shell);
Figure 3.2: SecVisor uses the processor’s virtualization features to mark only one of user- and kernel-space as executable at a time. This defeats ret2usr attacks by providing an opportunity to verify that the CPU privilege mode has changed as appropriate whenever the code execution has changed from user- to kernel-code or vice versa.
a particular page of memory [80].
SecVisor uses physical memory virtualization to mark only one of kernel- and
user-space executable at a time. When a violation of security rules is detected, the
protections can be swapped if the CPU has indeed changed privilege level, but are
otherwise denied. This defeats ret2usr attacks by preventing unauthorized processor
mode switches as shown in Figure 3.2. Additionally, the same virtualization allows
SecVisor to enforce standard W⊕X rules on all kernel code pages that the user has
approved. This mitigates the possibility of a kernel code implant by verifying that all
executable kernel code is non-writable and has been approved for execution by the
user.
The security benefits of SecVisor are packaged in a tiny VMM that provides a small
attack surface: only 4092 lines of source code in total. Unfortunately, SecVisor does
have several weaknesses. The kernel running on top of SecVisor must guarantee that
it does not share code and data on a single page. Additionally, the kernel has to be
31
modified to cooperate with SecVisor by issuing vmcalls to designate that it is loading
or unloading kernel code. Finally, it imposes an overhead as high as 97% due to the
additional translation required by the virtualization of physical memory. For a full
discussion of performance overhead costs, the interested reader should consult [147].
It is worth noting that [65] discovered two different bugs in the SecVisor imple-
mentation that allowed an attacker to violate rules that SecVisor claimed to enforce.
Although these were implementation rather than design issues, and easily remedied,
it is clear that even in a small code base security properties are difficult to reason
about and correctly enforce.
SVA
The Secure Virtual Architecture (SVA) [46] is a set of architecture independent in-
structions that allow an operating system to interact with hardware. A kernel is
ported to use these instructions, similar to porting a kernel to any new hardware ar-
chitecture. Offline, an SVA compiler produces SVA byte-code from the kernel source
code. This compiler has advanced features to provide memory safety and control-flow
integrity at compile-time, similar to “safe” programming languages such as Java. The
byte-code is distributed to users and executed on top of a virtualized SVA interpreter
that performs the final step of translating to native target-dependent machine code.
The effort required to port an operating system to execute on SVA and the large
performance cost are balanced by a promise of a substantial increase in security.
Guaranteed memory safety and control-flow integrity deny common methods used to
initiate ret2usr, kernel ROP, and kernel code implant attacks. An important point
is that SVA does not set out to deny these attacks explicitly. Instead, it attempts to
deny the vulnerabilities that enable these forms of attack, such as buffer overflows.
Unfortunately, the infrastructure needed to support SVA presents a significant hurdle.
In addition to porting a kernel to a new architecture, SVA imposes restrictions on
32
the kernel’s memory allocation mechanisms that are likely to require modifications
in kernel subsystems such as kmalloc. The performance cost is high, measured at
approximately 50% on average, but at times reaching a 4x cost.
KCoFI
Kernel Control Flow Integrity (KCoFI) [45] leverages the mechanics of the SVA im-
plementation discussed previously, but offers only control flow integrity. Specifically,
KCoFI ensures that function calls always enter at the beginning of some function’s
code, and that all returns from a particular function target the location of a possible
call site. In order to prevent user-space applications from imitating the labels that
KCoFI uses to validate branches, allowable address transitions are restricted to those
within a certain pre-defined “kernel” range of virtual addresses. This limits the capa-
bilities of advanced load-time randomization schemes. KCoFI also provides advanced
treatment for the issues that make control flow integrity particularly difficult in the
context of operating systems. In particular, it takes special care to handle interrupts,
signals, DMA/devices, incomplete branch target information at compile-time, and
page faults.
By verifying all branches at run-time, while the processor is in kernel mode, KCoFI
manages to deny each of the three primary privilege escalation techniques described in
this survey. Unfortunately, as with SVA, there is a large performance cost. Although
the average performance impact on a standard application was 13%, worst-case costs
up to 3.5-fold were reported. In addition, the method shares the SVA framework and
therefore also requires porting the OS to a new “architecture,” and pre-compiling the
kernel and all of its modules with specialized SVA compilers.
33
SBCFI
State-based control-flow integrity (SBCFI) [134] provides course grained control-flow
integrity for the operating system kernel. It sets itself apart from traditional control-
flow integrity solutions, such as [58], in two ways. First, it implements monitoring
externally from the kernel, in a hypervisor. Additionally, it assumes that attackers will
generate persistent control-flow violations, therefore necessitating that kernel state is
checked only periodically. Consequently, its introspection techniques allow SBCFI to
detect any attack that persistently modifies the kernel’s known control-flow graph.
The authors of [134] argue that trading strict security rules for performance by
using SBCFI instead of complete CFI is acceptable because SBCFI will still detect
most rootkits. In particular, they examined 25 rootkits found “in the wild” on Linux
and found that all but one were detected by SBCFI. They suggest that attacker goals
such as packet-sniffing or keystroke logging demand persistent rather than transient
control-flow changes.
Unfortunately, SBCFI focuses on detection rather than prevention. This, com-
bined with the focus on only persistent control-flow changes, leaves many avenues
open to the attacker. SBCFI verifies the state of the kernel by checking a pre-
computed hash of the kernel code and checking all function pointers stored in the
kernel heap to verify that nothing has been changed. These checks would not detect
a process that has achieved escalated privilege via a ret2usr attack or a kernel ROP
payload. Overall, SBCFI manages to effectively deny persistent modifications to the
kernel control-flow graph with minimal performance costs of less than 1% on average.
However, it fails to address the general threat associated with privilege escalation.
34
3.1.2 Other Techniques
kGuard
kGuard [93] aims to deny ret2usr attacks by inserting guards on the kernel’s control-
flow at compile time as shown in Figure 3.3. On the x86 platform, the call, jmp, and
ret instructions all redirect control-flow and therefore are vulnerable to being hijacked
in order to redirect kernel execution into user-controlled code. kGuard places an inline
check before any of these instructions. The checks are provided in two different forms
depending on whether the target address is stored in a register or in memory. The
checks simply verify that the branch target lies within kernel-space. Unfortunately,
if an attacker controls the target of two branches, he can direct the first to jump
directly to the second branch, bypassing the kGuard check completely. Since the
second branch is in kernel-space, the check on the first branch would allow the control
transfer. To avoid this attack, kGuard includes a compile-time code diversification
mechanism that makes it difficult for the attacker to locate the address of the second
branch.
One of the most significant advantages of kGuard is that, as a purely compile-time
technique, it is portable to any operating system on any target hardware. It does not
require any special hardware or impose many restrictions on the implementation of
kernel features. Additionally, its average performance cost is low at approximately
1%, making it deployable on existing systems. Unfortunately, kGuard does suffer
from a variety of weaknesses. Although its simplicity lends itself to easy deployment,
it is unable to protect against kernel-code implants or kernel-ROP. Although these
are outside of the scope of kGuard, a kernel code implant could be used to create a
ret2usr attack by implanting an unguarded jump into a user-space region. Therefore,
another technique must be used in combination with kGuard to deny the possibility
of a ret2usr scenario. This quickly increases in complexity and performance cost as
35
U se
r- Sp
ac e
Ke rn
el -S
pa ce
Hardware-Enforced Privilege Mode Boundary
INT/SYSENTER
IRET/SYSEXIT
fn: ... if target Є kernel JMP target else JMP fault_handler
attacker_target
attacker_target: ... execve(shell);
Figure 3.3: kGuard is a compile-time technique that includes run-time checks around kernel branch instructions. These checks verify, before the branch, that the target of the branch is within kernel space. Combined with a code diversification routine, this prevents ret2usr attacks.
multiple techniques need to be deployed on the same system. Additionally, kGuard’s
inline checks verify that the target of a control-flow transfer lies in kernel-space only by
checking that it falls within a predefined range. This limits the capacity for deploying
advanced code randomization during the loading of the kernel.
Return-less Kernels
Recall that Kernel ROP attacks requires “return” instructions in order to move from
one gadget to another. In [106] the author utilizes “return indirection,” introducing
additional jumps at compile-time to disrupt this mechanism and defeat kernel ROP
attacks. This approach uses a pre-computed table of all legal return addresses. Rather
than pulling a return address from the stack and jumping to it at the end of a function,
this method reads an address from the specified index in the return address table.
If this table is trusted, the attacker could only modify which legal return address is
used. It is assumed that most gadgets begin in a location other than a legal return
36
address, and as a result this technique defeats the possibility of an attacker to craft
a malicious payload.
In addition to introducing return indirection, [106] introduces compiler modifica-
tions to avoid instructions with an embedded “return” opcode. On an architecture
such as x86, variable length instructions make it possible to read different instructions
if the instruction pointer is offset some distance into an opcode. Without taking care
at compile-time to avoid these scenarios, an attacker could still create gadgets by in-
dexing the instruction pointer at unintended positions in the middle of the intended
instruction.
The idea of using a return-less kernel is clearly beneficial as it effectively mitigates
a very particular risk. Unfortunately, it does impose a performance overhead of
approximately 6%. In addition, it does require modification to the kernel source.
Although functionality provided by compiling a higher-level language, such as C,
does not need to be modified, any functionality defined in assembly language must
be manually modified to follow return-less principles. Since the kernel interfaces with
hardware directly, there is a non-trivial amount of assembly code included in most
kernel implementations.
PaX
One of the first kernel-hardening efforts was implemented on Linux by the PaX
team [133] circa 2000. UDEREF [153] utilizes segmentation to create a stricter sep-
aration between kernel- and user-space (denying ret2usr), while the PAGEXEC and
Restricted mprotect() features essentially generate and enforce typical W⊕X secu-
rity rules on kernel code and data to mitigate kernel code implants.
PaX is valuable as a case study in hardening kernels. Unfortunately, it is less
valuable as a mechanism for protecting modern kernels on today’s hardware. Its
protection mechanisms were based on Linux-specific software mechanisms (such as
37
mprotect()) and x86-32-specific hardware features (such as segmentation). Addi-
tionally, the performance cost was significant, according to [93]. PaX-reported data
about performance cost was available at the time of writing.
Sprobes and TZ-RKP
Sprobes [67] and TZ-RKP [14] both utilize the ARM TrustZone [1] hardware facili-
ties included in modern ARM processors. TrustZone is a hardware-protected context
that can run tangentially to the regular operation of the processor. The hardware dis-
ables the normal processor context from accessing anything within the “secure world”
created by TrustZone and transitions between the regular context and TrustZone’s
secure context are limited by hardware to a small and well-specified interface.
Sprobes [67] utilizes TrustZone by installing an introspection handler in the secure
world and installing, at load- or run-time, special instructions that invoke the secure
world at predetermined points in the execution of the kernel. When one of these
probes is executed, control transfers to the secure world in which kernel state can be
interrogated, control flow or memory contents verified, or any other number of actions
can be taken. Furthermore, restrictions are placed on the normal world’s ability to
manipulate the virtual memory settings of the processor. The requirement that these
systems be updated by the secure world guarantees that a kernel cannot manipulate
virtual memory in order to bypass the probes.
TrustZone-based Real-time Kernel Protection (TZ-RKP) [14] is a similar approach
that forces vital control operations involving the virtual memory layer to be routed
through the secure world. TZ-RKP forgoes the probes provided by Sprobes, but takes
a more extreme approach by limiting the kernel’s control over important system state
such as virtual memory. TZ-RKP forces all attempts to control virtual memory and
other hardware resources through the secure world, providing a mechanism to verify
any changes to the system state. With a controlled and static system state, it is easier
38
to make claims about what an attacker may do to manipulate the kernel state.
Both [14] and [67] are built on the TrustZone architecture. The hardware under-
lying their implementation allows each to be implemented with a reasonable perfor-
mance cost (typically 10%). TrustZone is also attractive because it manages to avoid
the “turtles all the way down” problem in which software layer x is protected by
introducing software layer x− 1, which simply becomes the new target for attackers
and instantiates the same problem again. Traditional virtualization can be criticized
for this problem [25, 141], but TrustZone holds itself off to the side of layer x rather
than existing underneath it.
Unfortunately, TrustZone is an ARM-specific technology. Although ARM is used
extensively in mobile and embedded applications, the x86 architecture continues to
dominate desktop and server applications. Although these techniques are interesting,
their utility is limited by a reliance on specialized hardware.
3.1.3 Comparison
Table 3.1 summarizes and compares the techniques discussed in the previous sections
on the basis of their ability to mitigate privilege escalations and their expected cost:
• Kernel Code Implant/Kernel ROP/ret2usr : Does this technique mitigate the
risk of privilege escalation associated with these particular attack vectors?
• Typical/Maximum Performance Cost : What is the typical and worst-case re-
ported performance costs?
The performance costs listed represent only the maximum performance cost and
an estimated average used only to illustrate differences between the techniques. In
some cases these come from micro-benchmarks corresponding to small code segments,
in other cases they come from macro-benchmarks corresponding to full applications.
For the estimated average, they are often a mix of these tests. Each of the techniques
39
Project Kernel Code
Implant
Kernel ROP
ret2usr
Typical Reported
Performance Cost
Maximum Reported
Performance Cost
KCoFI [45] 3 3 3 13% 3.5× SVA [46] 3 3 3 50% 4×
SecVisor [147] 3 7 3 20% 97% NICKLE [139] 3 7 7 1-5% 19.03% SBCFI [134] 3 7 7 <1% 13% kGuard [93] 7 7 3 1% 23.5% Return-less Kernel [106]
7 3 7 6% 17.32%
PaX [133,153] 3 7 3 No Data No Data Sprobes [67] 3 3 3 10% ∼10% TZ-RKP [14] 3 7 3 3% 7.65%
Table 3.1: This table summarizes the methods of mitigating privilege escalation that were described in this Section. In particular, it shows which of the three main privilege escalation techniques each method targets, and summarizes some performance cost data from each effort.
offers thorough performance cost analyses that could not be summarized in a simple
table. Interested readers should consult the original paper for each technique for a
more complete treatment.
Table 3.2 compares the techniques on the basis of general observations regarding
their operation:
• x86-64 compatible: Most desktop and server-class systems use the 64-bit x86
architecture. Is the technique viable with the hardware provided by the x86-64
hardware?
• Memory and/or Control Flow Integrity : Which is the primary mechanism by
which the tool delivers its security guarantees?
• Code-Diversity Compatible: Is the technique sufficiently flexible to allow for
advanced fine-grained address space layout randomization techniques?
• Code Size: How many lines of code (LoC), as a measure of the attack surface
40
Project x86-64
Compatible
(M)emory and/or
(C]ontrol [F)low Integrity
Code-Diversity Compatible
LoC
NICKLE [139] 3 M 3 932 KCoFI [45] 3 CF 7 5579 SVA [46] 3 M & CF 3 No Data
SecVisor [147] 3 M 3 4092 SBCFI [134] 3 CF 3 No Data kGuard [93] 3 CF 7 1000
PaX [133,153] 7 M & CF 7 No Data Return-less Kernel [106]
3 CF 3 2100
Sprobes [67] 7 M & CF 3 No Data TZ-RKP [14] 7 M 3 No Data
Table 3.2: Any security technique is hard to summarize in terms of only the attack it aims to neutralize and the performance cost it incurs. These techniques often change deep and fundamental parts of the operating system’s functionality. They may introduce new complexity in the system. This table presents additional features of each technique to provide a more complete picture of how they interact with other system components.
presented, are used in the implementation of the technique as presented?
It is clear from Table 3.1 that while KCoFI and SVA offer the most protection
against the three different techniques associated with privilege escalation, they also
come with dramatically more performance overhead than the other methods. This
conforms to expectations in that the more thorough the security measure, the higher
its performance impact. Sprobes and TZ-RKP appear exceptional as they enjoy the
lowest performance costs and strong security claims. Unfortunately, each utilizes the
ARM TrustZone architecture and consequently are unavailable on the Intel x86 archi-
tecture. Additionally, vulnerabilities have already been discovered in some TrustZone
hardware implementations [142].
41
3.1.4 Privilege Escalation Mitigation: Conclusion
Each of the techniques examined in this section makes valuable contributions to the
security of modern operating systems. Those that offer the most comprehensive
security suffer from high performance costs or specialty hardware requirements. On
the other hand, many mitigate a specific, focused risk to kernel security while suffering
only a small performance cost. Unfortunately, there is no single solution that offers
both acceptable performance and comprehensive security coverage on the popular x86
platform. The impact of combining the techniques to improve coverage is not well
understood in terms of complexity, performance, or security.
Overall, the kernel developer has a wide variety of techniques to choose from,
but must balance individual strengths in privilege escalation prevention with the
associated penalties in performance and complexity. Future work aimed at mitigating
privilege escalation is likely to continue to have performance issues without some
change in the underlying hardware or kernel design paradigms. Modern commodity
operating systems are so highly developed that there is unlikely to be some technique
hiding in a dark corner that will not decrease performance while requiring extra work.
3.2 Execute-Only Memory
ExOShim, discussed in Chapter 4, uses the Intel’s VT-x virtualization extensions to
implement execute-only permissions on kernel code pages. In order to provide context
for this project, a series research efforts examining execute-only memory is presented
here for review.
Execute-only memory has been used in a variety of systems for protection of
user code. For example, Readactor [43] is a kernel implementation that allows the
administrator chose to mark user-space applications execute-only. ExOShim on the
other hand, was specifically crafted with the goal of preventing ExOShim from being
42
disabled or hijacked. Furthermore, ExOShim protects the operating system pages,
not user-space applications.
Backes et al [15] have shown in Execute-no-Read (XnR) another way of achieving
execute-only code pages. Though, unlike ExOShim, it only emulates execute-only
paging. XnR uses a sliding window mechanism to keep the last n pages both readable
and executable. All other pages are marked as non-present. Note that a page is
readable while it is marked executable. Unfortunately, an attacker could craft an
exploit once access is gained to the page. Once a gadget has been crafted, XnR could
be tricked into jumping to malicious code pages and thus marking other pages as
readable. ExOShim on the other hand, offers true execute-only memory enforced by
the hardware. Utilizing Intel’s EPTs, a page is marked execute-only and not readable.
This prevents an attacker from obtaining information about running the programs
code.
Gionta et al [68] proposed HideM. Here, the concept of a Split Transaction Looka-
side Buffer (TLB) is being used. By utilizing a Split-TLB, Gionta is able to direct
instruction fetches and data reads to different physical memory locations. An instruc-
tion fetch is a legitimate operation, as well as a white listed data read of embedded
constants. Used by PaX [156] previously to implement W⊕X, it now will most likely
not work on any modern hardware system since modern processors use unified second
level TLBs.
Non-readable memory techniques such as ExOShim must be combined with tech-
niques to randomize program layout in memory. This is because indirect memory
disclosures, such as reading a return address from a stack, are sufficient for inferring
the location of gadgets in non-readable but non-randomized code.
Table 2 illustrates and contrasts key features of memory protection mechanisms.
It shows that ExOShim makes two contributions to the area of memory disclosure
prevention. Firstly, it targets kernel code rather than user-level applications. The
43
ExOShim Readactor [43] XnR [15] HideM [68]
Stops Memory Leaks Kernel 3 7 7 7
User 7 3 3 3
Performance Cost (%) 0.86 6.4 2.2 1.49 Survives Kernel Compromise 3 7 7 7
Table 3.3: Comparison of Memory Protection Techniques. ExOShim adds to the state of the art by protecting from kernel level memory disclosures and persisting through kernel compromise.
kernel manages all processes, hardware, and other system resources. Hence, finding
vulnerability in the kernel will directly impact the security and stability of the entire
system. Thus, ExOShim explicitly targets prevention of kernel information leakage.
Furthermore, ExOShim is designed to persist despite any potential kernel com-
promise. ExOShim does not accept any input after its initialization and uses the
EPT to protect all of its own code and data from any read, write, or execute access.
As shown in Table 3.3, Readactor, XnR, and HideM could all be hijacked or disabled
in the event of a kernel compromise. Readactor provides an explicit mechanism for
the kernel to configure or disable its execute-only protections. XnR uses a page fault
handler to implement its execute-only memory protections; the kernel can change
the page fault handler at any time, completely bypassing XnR. HideM also relies on
kernel cooperation to provide the memory protection it offers. It requires the kernel
to “prime” the split-TLB with different images of memory in the read-case versus the
execute-case. ExOShim distinguishes itself from these approaches by acting specifi-
cally to survive through kernel compromise. The mechanism for this is described in
detail in Chapter 4.
3.3 Code Diversification
Computer system security via non-determinism was first proposed in various forms in
seminal papers several decades ago [13,38,64,137]. Since then, the idea has been fully
44
Study 64-bit Maximum Reported
Entropy (bits)
Discussion of
Algorithm
(U)ser-space, (K)ernel, and/or
(H)ypervisor Chew & Song ’02 [36] 7 15 None U & K
PaX ’01 [157] 7 24 None U Wartell et al. ’12 [160] 3 Unspecified None U Shioji et al. ’12 [150] 7 Unspecified None U Davi et al. ’13 [50] 3 Misspecified† None U
Bhatkar et al. ’05 [19] 3 26 None U Tanenbaum et al. ’12 [69] 7 Unspecified Partial K
Xu et al. ’09 [163] 7 28 None U Hiser et al. ’12 [75] 7 Unspecified None U Kil et al. ’06 [96] 7 29 None U & K Kanter ’13 [86] 3 27 None U & K
Überdiversity 3 47 Full U & K & H † Davi’s reported “entropy” is actually a count of program variants.
Table 3.4: This table presents a selection of fine-grained load-time memory random- ization techniques. It characterizes each in terms of the software level at which it is applied, its discussion of the algorithm used to diversify, and the maximum reported “entropy”.
embraced by the security community, leading to many research efforts exploring differ-
ent applications and implementations of randomization for security at development-,
compile-, load-, or run-time. Larsen et al. acknowledge the many works that came
before Überdiversity and KPLT more thoroughly than the scope of this section would
allow in [100,101].
Table 3.4 contains a selection of the relevant works presented in [101] and some
others. It summarizes which projects are 64-bit compatible, the maximum reported
entropy that their implementation achieves, to what extent the publication discusses
the algorithm used to implement their randomization, and which pieces of the software
stack are being randomized: user (U), kernel (K), or hypervisor (H) code.
Table 3.4 summarizes several types of load-time randomization efforts. Some ran-
domize the base addresses of entire program resources such as the stack, heap, code,
data regions, or operating system modules [36,69,96,157]. [19] presents a comprehen-
sive set of transformations to randomize these resources and introduce entropy within
45
each such as randomizing stack variable layout and code function order. Other tech-
niques use binary analysis to create programs with additional features: [160] produces
code that randomizes itself when loaded, [75] produces code embedded with meta-
data that is interpreted by a virtualized run-time environment, and [96] permutes
instructions and data in the binary. The code can also be shuffled after the primary
loading and linking, but before the code begins execution [50]. [150] extends the other
randomization techniques by choosing addresses that contain self-validating check-
sums that can provide some measure of run-time control flow integrity. Fine grained
per-function load-time randomization is combined with compile-time transformations
in [88].
3.4 Asymmetrical Multiprocessing
The KUCS kernel design relies on separating the operating system and user applica-
tions onto separate cores. This modifies a fundamental assumption of most modern
operating system designs: that all cores are treated equally. In this status quo, the
same union of kernel and user code runs on every processor. This is symmetrical
multi-processing (SMP).
Some research has investigated the possible merits of asymmetrical multiprocess-
ing (ASMP) compared to SMP. Allocating specific software tasks to specific hardware
resources is already commonly used within computing systems. Hardware units such
as network cards or graphics processing units (GPUs) demonstrate how matching spe-
cific software tasks with specialized hardware can greatly increase the performance of
normal computation.
In fact, many multiprocessors are built with cores that have heterogeneous per-
formance. These processors allow many low-performance cores to lower the heat,
power, and cost of the chip and provide large degrees of parallelization while a few
46
high-performance cores provide valuable service for high-cost serial computation. Ex-
amples include the “Cell” microprocessor architecture used in the Sony Playstation
and the Apple A10 Fusion chipset used in the iPhone 7. Research that examines
the application of asymmetrical multiprocessing in these types of processors is plen-
tiful [16, 117, 119]. However, research that investigates asymmetric application of
software to symmetric multicore hardware resources is particularly relevant due to its
similarities to the role of the cores as proposed by the KUCS design.
Early work surrounding the introduction of multiprocessors explored a master-
slave relationship between processors, with the operating system running only on the
master core. This is summarized in [57], where Enslow writes that “[a]lthough the
master-slave type of system is simple, it is usually quite inefficient in its control and
utilization of the total system resources.” Fortunately, this assessment is unlikely
to persist in the face of the speed and quantity of modern multiprocessors. Early
attempts had limited hardware resources and could not afford to isolate a single core
for the kernel alone; the kernel shared its core with general purpose processes. This
resulted in delayed servicing of slave core requests and interruption of software on
the master core during slave core requests. With the low cost and high speed of
processor cores modern systems, these issues are less likely to plague modern KUCS
implementations.
The master-slave paradigm is also used in [85] to implement a scheme designed to
easily allow a uniprocessor operating system implementation to manage software on
a multicore processor. In particular, it provides lightweight kernel implementations
that record system calls made by applications on other cores, and a daemon that
scans for these records and requests the appropriate computation from the kernel
on the main core. This work is similar to KUCS in its concept, but because it was
designed to shoehorn a uniprocessor kernel onto a multicore processor, it does not
realize the security or performance benefits that may be possible with KUCS,.
47
The Twin-Linux project [83] examined utilizing symmetric multiprocessor cores
asymmetrically by running two completely independent instances of the Linux oper-
ating system on the same CPU - each using its own subset of the processor’s cores.
Their work provides a thorough illustration of the flexibility of x86 IPIs and processor
cores to be used in a capacity beyond their traditional use in commodity operating
systems.
AsyMOS [121] assigns cores of a symmetric multicore processor to specific tasks
such as network communication or disk I/O. These cores run the appropriate device
driver and a Lightweight Device Kernel (LDK) that implements only the functional-
ity that those drivers might need. The prototype described demonstrated improved
performance over traditional SMP operating systems. Similarly, Corey [22] explores
using specific cores to do application-specific kernel-intensive work on behalf of an
important process in parallel to the application itself.
3.5 Operating System Design Paradigm Shifts
The techniques described thus far each provide a modification to some part of the
conventional kernel design, implementation, or build process that mitigates a par-
ticular threat. There are a few approaches, however, that attempt to offer similar
security benefits by redefining the security paradigm rather than simply patching the
status quo best practices. This radical departure from the current state of the art
means that they cannot easily be compared to the previously described techniques.
In all cases, it also means that they have not yet been widely accepted.
3.5.1 Microkernels
The idea of a microkernel departs from the standard “monolithic” kernel architec-
ture by emphasizing a small codebase for the operating system kernel. There have
48
been several examples of microkernels presented in the literature such as Mach [10],
Minix [73], L4 [135], QNX [74], and many others. Bear, the platform for the projects
discussed in this thesis, is an example of a microkernel.
All microkernels aim to minimize the source code in order to decrease the likeli-
hood of vulnerabilities [130]. Additionally, a small code base allows for the possibility
of using formal analysis and formal verification techniques [18, 98]. In order to keep
the microkernel small, core functionality such as device drivers are migrated into user
level processes. Additionally, many microkernels use message-passing for all commu-
nication between two processes or a process and the kernel. This provides a narrow
and more easily verified and secured interface between components.
By exporting core functionality such as device drivers into user-space, microkernels
struggle to offer the same levels of performance as monolithic kernels. Consequently,
they have yet to replace monolithic kernels in common applications on commodity
hardware.
3.5.2 ExoKernel
The ExoKernel [56] suggests redefining the nature of the kernel entirely. Rather than
providing abstractions that the application developer can use to access hardware, the
ExoKernel provides only the thinnest possible layer to manage the multiplexing of
hardware resources. Therefore, the ExoKernel circumvents tasks normally reserved
for the kernel such as buffering network communications, interrupt or exception han-
dling, virtual memory management, and other normal kernel functions. Instead, each
individual application must define its own abstractions to handle these tasks.
Although likely to offer more security for a system overall, the ExoKernel appears
significantly complicate application development. Many of the tasks that a secure
kernel can provide to protect all processes, such as virtual memory management,
become the responsibility of the application developer. This is likely to make indi-
49
vidual applications less secure since application programmers may lack the technical
sophistication to interact directly with hardware, interrupts, atomicity, and concur-
rency. These central parts of the operating system exist to provide applications with
well-defined interfaces to this complex functionality. The ExoKernel eliminates those
interfaces by design.
3.5.3 Unikernels
Unikernels trade flexibility for security and performance by running a single process
within a single address space [111]. Eliminating the requirement to support multiple
processes and/or multiple users simplifies the code base required to implement a
unikernel and reduces the overhead required to complete a single unit of useful work.
Several examples have been deployed alongside virtualization technologies in cloud
applications [23, 97, 114]. Despite their proven usefulness for providing fast, highly
focused applications, unikernels don’t, in isolation, provide protection from most of
the attack vectors discussed in this thesis. Additionally, in order to support the
multiple-user multiple-job paradigm that conventional applications require to operate
effectively, they require a hypervisor for scheduling and other process-management
type tasks. In a sense, this is simply asking the hypervisor to act as an operating
system and the same issues with conventional operating system design will simply
move one layer deeper in the software stack.
50
Chapter 4
ExOShim
Memory disclosures in modern computer systems provide attackers with a valuable
method of discovering vulnerabilities. Figure 4.1 illustrates a realistic instance of
this type of memory disclosure. By uncovering the code stored in memory, an at-
tacker can craft Return-Oriented Programming (ROP) payloads to perform arbitrary
computation. Memory disclosures are especially important for Just-in-Time ROP
techniques that can defeat compile- and load-time code randomization defenses [151].
These same disclosures enable an attacker to reverse-engineer the source code and
design or uncover other zero-day exploits [152]. Information leakage from the kernel
is particularly concerning because a compromised kernel gives an adversary access to
all system resources.
To mitigate this threat, ExOShim uses the Extended Page Tables (EPT) provided
by the Intel VT-x instructions to configure hardware-enforced execute-only memory
access control primitives on all kernel code pages on x86 platforms. This eliminates
the capability of an attacker to dynamically, at run-time, disassemble kernel code
stored in memory. While Section 3.2 discusses several execute-only memory protection
schemes, ExOShim distinguishes itself by configuring the processor’s virtualization
features so that it can never be modified or disabled without rebooting the machine.
51
U se
r-S pa
ce Ke
rn el
-S pa
ce driver_code: ... addr <- usr_request; if ( within_device(addr) ) return *addr;
1
attacker_program: ... for (addr=0; addr<0xBEEF; addr++) *(copy+addr) = device_req(addr); build_attack(copy); 0xBEEF
2
3
1 MEMORY DISCLOSURE: Buggy driver fails to check that user-passed address lies within its memory-mapped device
2 Attacker queries buggy driver to reconstruct kernel code
3 Attacker uses copy of kernel code to attack - harvest gadgets for Kernel-ROP - reverse engineer code
Figure 4.1: Memory disclosures allow the attacker to retrieve a copy of the code executing on a system in order to reverse-engineer the implementation, locate vulner- abilities, or construct a ROP payload. This figure illustrates how a simple bug in a device driver can create a dangerous memory disclosure.
This ensures that the attacker can never disable, modify, or hijack its protection
mechanisms, even with complete control of the operating system kernel.
4.1 ExOShim: Background
Direct memory disclosures can be eliminated if kernel code is marked execute-only as
in MULTICS. Intel’s 32-bit virtual memory mechanism provided execute-only access
control primitives with segmentation [159]. Unfortunately, although more flexible
in many ways, the current Intel virtual memory model, based on paging, does not
support execute-only memory protection [79]. While side channel attacks have been
developed to exploit this fact [59], these too can be mitigated through execute-only
protection of code.
4.1.1 The Kernel and Virtual Memory
Although modules might be added or removed at runtime and virtual addresses to
kernel functionality may change, kernel code is generally loaded once and only once.
As a result, after initial bootstrapping, its location in physical memory does not
change. The kernel therefore represents high-value target that, when coupled with
52
its persistent nature, makes it an important resource to protect.
In general, the kernel provides applications with an interface to the hardware;
every application needs to access the functionality of the kernel in order to run on
the processor. In most modern operating systems the kernel is mapped directly into
the address space of every process. The virtual memory abstraction allows for each of
these “instances” of the kernel to resolve to a single copy of the kernel binary, stored in
physical memory. On modern Intel 64-bit processors, the virtual memory abstraction
is achieved by traversing a 4-level deep page table [79] as shown in Figure 2.1 on
Page 14 in Section 2.1.
The entries in this paging structure contain bits that describe the permissions
required to access all memory associated with the entry. These bits include a no-
execute (NX) bit, a supervisor bit (U/S) and a write bit (R/W). Unfortunately,
read permissions are implied as long as the privilege level requirement is satisfied.
This means that although the virtual memory abstraction does provide some access
control primitives it is not possible to directly mark memory as execute-only in the
page tables.
4.1.2 Virtualization and the EPT
Intel’s virtualization extensions (VT-x), provided in modern commodity processors,
allow a hypervisor to abstractly represent the hardware environment. This is most
commonly used to allow multiple operating systems to operate concurrently on a
single processor.
Extended Page Tables (EPTs) are part of the hardware abstraction provided by
virtualization. These tables provide a similar abstraction to the virtual memory
abstraction discussed previously, with one major difference: while the kernel’s page
tables translate from virtual to physical addresses, the hypervisor’s EPT translates
from guest physical to real physical addresses. When virtualized, the kernel’s page
53
tables resolve to a physical address that is valid in the virtualized image of memory.
The EPT is a hardware-enforced link between the virtualized interface to system
memory and the actual system memory.
There are a few other differences between the EPT and the normal page table
that are relevant. EPT entries provide unique read (R), write (W) and execute
(X) bits that are enforced by hardware [79]. This makes it possible to mark pages
directly as execute-only. Additionally, the EPT entries can only be managed by a
hypervisor, not by a kernel. If an attacker compromises the kernel, the normal virtual
memory abstraction cannot provide any security; however, the attacker would have
to compromise the hypervisor in order to manipulate the EPT.
4.2 ExOShim: Overview
ExOShim is a lightweight hypervisor that reclaims the MULTICS-style hardware-
enforced execute-only memory protection using modern Intel virtualization technolo-
gies. It was designed as a “shim” that can be inserted beneath a running kernel,
as in [55]. A conscious effort was made to minimize its size to open the door for
formal reasoning [93] and reduce the likelihood of introducing vulnerabilities [131].
The on demand insertion process allows ExOShim to enable execute-only memory for
a running system using Extended Page Tables (EPTs).
4.2.1 Assumptions
ExOShim assumes that a trusted boot process is undertaken by the operating system
it will be deployed on [102]. The security implications associated with the race to call
vmxon [144] are well known and must be addressed within the trusted boot process.
ExOShim currently assumes that it is the first hypervisor on the system [61] and
makes no attempt to verify the absence of another hypervisor. The requirement that
54
Process A Virtual Memory Space
Process B Virtual Memory Space
Kernel Process BProcess AUnused
Virtual Memory Abstraction
Guest Physical MemoryC
od e
C od
e
C od
e
C od
e
ExOShim Extended Page Tables
Real System Physical Memory
X -O
nl y
X -O
nl y
Ex O
Sh im
Ex O
Sh im
Ex O
Sh im
Ex O
Sh im
Figure 4.2: Overview of Protections Offered by ExOShim. The EPT table identity maps memory, but provides execute only protections on kernel code pages and denies access to ExOShim pages. All other memory is marked with the most liberal possible permissions.
data sections in the kernel ELF binary are readable mandates that attention be paid
during the compilation, linking, and loading of the kernel to distinguish between code
and data. Upon the completion of the loading process, it is assumed that no code
section will share any page in memory with a data section.
4.2.2 ExOShim
The design of ExOShim is illustrated in Figure 4.2. Recall that the “shim” exists only
to provide full access control to physical memory. In particular it exists to enforce
execute-only protection on all kernel code pages.
ExOShim builds an identity map associated with all of physical memory using the
EPT structure. In other words, the output from the translation process is identical
to the input for all possible inputs. However, for kernel code pages only, both the R
55
and W bits are cleared and only the X bit is asserted. This will cause a fault on any
read or write access to the physical memory on which the kernel code resides. Most
other mappings are marked with the most liberal permissions, allowing the kernel
to enforce further protections using the normal paging mechanism. Pages used by
ExOShim itself are marked in a unique fashion that is discussed in Section 4.3.2.
In order for ExOShim to build the correct EPT structure, it must have access to
the addresses where kernel code is loaded. This would be a challenge if ExOShim
were booted onto the hardware first, initialized itself, and then allowed the kernel
to bootstrap itself in the virtualized environment it creates. Although this is the
conventional way to think about virtualization, this method requires that ExOShim
initialize its EPT without knowing where the kernel will eventually load code. Un-
fortunately, detecting which pages hold kernel code from a hypervisor is a non-trivial
forensics task. Instead ExOShim uses a method developed by Embleton et al [55]
that allows a hypervisor to install itself under a running kernel.
During bootstrapping, the kernel creates a single kernel-level ExOShim process.
When scheduled, this process builds an appropriate EPT and queries the kernel to
locate where its code has been loaded. After this initialization, it turns on the virtu-
alization features of the Intel processor and launches a virtual machine whose state
matches the state of the kernel prior to scheduling the ExOShim process. The re-
sult is that the kernel continues execution as a virtual machine with the protections
enforced by the underlying EPT.
If compromised, ExOShim would provide a dangerous security risk. For this
reason, ExOShim is implemented in a manner that ensures it cannot be reconfigured
or turned off. Intel’s virtualization extensions allow a hypervisor to respond to events
in the guest. However, ExOShim explicitly prevents any event eligible to be handled
by the kernel from triggering an exit to the hypervisor. Additionally, any event that
must trap to the hypervisor (such as a violation of the EPT permissions) results in
56
an immediate assumption of compromise of the kernel. Depending on the goals of
the system, this could trigger a reboot, a halt, a logging feature, or any number of
other responses. It explicitly does not, however, return control to the kernel. In other
words, ExOShim does not take any input from the kernel and consequently presents
a hardened target without a viable attack vector.
Although it does not accept input of any kind from the kernel after initialization,
ExOShim also enforces additional protection measures. When a kernel is booted on
top of a hypervisor, it is presented, at initialization time, with a modified image of
system memory that does not include the hypervisor code and data. Since ExOShim
is loaded only after the kernel has already been initialized, it exists in memory that
has already been observed by the kernel. As such, the kernel could alter the mem-
ory used by ExOShim after initialization. To mitigate this vulnerability, ExOShim
marks all pages containing its own code or data as non-readable, non-writable, and
non-executable in the EPT, thereby ensuring that access to ExOShim code or data
is denied. Memory marked as completely untouchable in the EPT includes: the Ex-
OShim initialization and error handling code, the ExOShim’s call stack, structures
necessary for initializing the virtual machine context, memory on which the EPT is
stored, and the paging structures of the ExOShim kernel process. Any attempt to
read, write, or execute any memory related to ExOShim after its initialization will
be denied.
Obviously, the protections on memory exerted by ExOShim could be used to deny
service to the kernel. However, any memory access that would cause ExOShim to
be invoked already implies a dangerous security flaw in the operating system: For
example, under normal operation, the kernel should not be reading its own code.
Another method that could be used to invoke ExOShim is attempting to access the
memory being used by ExOShim itself. Since the kernel initializes the ExOShim
process, all memory used by ExOShim is marked as “taken” in the kernel’s internal
57
bookkeeping. Therefore, there is no scenario in which normal operation of the system
would result in ExOShim detecting a violation of its own access control primitives. In
other words, any scenario in which ExOShim is invoked is a clear sign of compromise,
and service ought to be denied to the kernel in the interests of security.
4.3 ExOShim: Implementation
Since ExOShim is an operating system feature that utilizes virtualization, its imple-
mentation will by highly dependent on the particular kernel and processor on which
it is used. However, all implementations must tackle the same core tasks: provid-
ing a context in which the ExOShim initialization routine is to execute, building an
EPT structure, enabling virtualization, and resuming kernel execution. This section
describes these core tasks, and Algorithm 4.1 lays out psuedocode of the procedure
required.
4.3.1 Providing ExOShim a Context
ExOShim does not require special consideration by the kernel beyond that required
by any other process. All that is required is that it executes with supervisor privileges
and in a unique virtual address space.
In order to use the Intel virtualization instructions without causing faults, the
processor must be operating in ring 0, privileged mode. This could be accomplished
by loading ExOShim as a binary but allowing it special privileges beyond a typical
user-space process. Some operating systems provide the notion of a kernel module to
accomplish this type of task. Alternatively, ExOShim could be implemented directly
in the kernel. As long as the ExOShim functionality is not located on pages shared
by other memory (as stated in the assumptions in Section 4.2.1) and a unique virtual
address space is created before jumping to the ExOShim initialization routine, it can
58
Algorithm 4.1: Psuedocode describing the ExOShim initialization routine. Steps are elaborated upon and described in detail throughout Section 4.3
1 Remove mappings to kernel heap; 2 Flush TLB; 3 Initialize arrays of frames for shim (As), kernel code (Ak), and non cacheable
memory (Anc); 4 Reserve memory for EPT structure; 5 As ← shim function code and data frames; 6 As ← shim context paging structure frames; 7 As ← shim context stack memory frames; 8 As ← frames to be used for EPT; 9 Anc ← memory mapped IOAPIC address;
10 Anc ← memory mapped APIC address; 11 Anc ← VGA memory addresses; 12 Anc ← memory mapped IO addresses; 13 Ak ← all kernel code frames; 14 Build EPT; 15 Populate VMCS; 16 Free As, Ak, Anc; 17 Set stack base pointer for next process (rbp); 18 vmlaunch;
be compiled into the kernel. For the proof-of-concept prototype described in this
chapter, all ExOShim functionality was compiled into the kernel directly.
It is important to understand why it is necessary to provide a unique virtual
address space for ExOShim. Some functionality must be provided to handle an event
in which a memory access breaks the primitives of ExOShim. This functionality is
invoked by hardware in the event of an EPT violation. A set of page tables provides
access to this functionality through the virtual memory abstraction. A unique set of
page tables for ExOShim allows for the frames of memory where these page tables
are stored to be marked as non-readable, non- writable, and non-executable in the
EPT. This prohibits the kernel from manipulating the paging structures that will be
used to find the fault- handling functionality if ExOShim is invoked.
59
4.3.2 Building the EPT
The Intel manuals clearly show how to format memory to build a four-level EPT.
C code from the ExOShim prototype implementation is shown in Snippet 4.1. The
task is simplified by the fact that ExOShim’s EPT is simply an identity map of all
available physical memory. The kernel should therefore return the correct amount of
physical memory when queried appropriately.
The challenge here for ExOShim is in determining the permissions to apply to
each entry in the EPT. The default permissions are read, write, and execute. The
most liberal permissions in the EPT allow for the kernel to continue with its own
memory management and access control. Enabling caching by default is also impor-
tant for performance reasons. However, there are three cases where the permissions
will differ. These are kernel code frames, ExOShim frames, and volatile (uncacheable)
frames. Line 3 in Algorithm 4.1 discusses initialization of arrays to store these types
of memory. After they’ve all been populated in lines 5-13, line 14 calls for the actual
construction of the EPT.
Kernel Code Frames
As stated in the assumptions shown in Section 4.2.1, kernel code is loaded on frames
of memory that contain only kernel code. Each such frame should be marked in the
EPT as non-readable, non-writable, but executable. This is the entire premise of
ExOShim.
The kernel must provide a mechanism with which ExOShim can locate all frames
of memory that contain kernel code. In the case of the prototype described here,
kernel code frames are identified by a unique configuration of a process’ page table;
kernel code frames are marked as present, global (for caching purposes), executable,
non-writable, and supervisor-mode only. No frame on the system can be marked
with these permissions and not be a kernel code frame, and every kernel code frame is
60
/∗ bu i ld an EPT. Use frames from the ept f rames s e c t i o n o f shim frames . I d en t i t y map except s p e c i a l pe rmi s s i on s f o r frames in kern , shim , or nocache ar rays ∗/
pml4t = map phys to temp virt ( shim frames [ ept f rames ++]); f o r ( pml4t idx = 0 ;
( u i n t 64 t ) idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) <= memory present && pml4t idx < 512 ;
pml4t idx++ ) {
/∗ get a new PDPT and i n i t i a l i z e PML4T entry ∗/ pdpt = map phys to temp virt ( shim frames [ ept f rames ] ) ; ( ( u i n t 64 t ∗) pml4t ) [ pml4t idx ] = ( shim frames [ ept f rames++] & ˜0 x f f f ) | 0x7 ; f o r ( pdpt idx = 0 ;
( u i n t 64 t ) idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) <= memory present && pdpt idx < 512 ;
pdpt idx++ ) {
/∗ get a new PD and i n i t i a l i z e the pdpt entry ∗/ pd = map phys to temp virt ( shim frames [ ept f rames ] ) ; ( ( u i n t 64 t ∗) pdpt ) [ pdpt idx ] = ( shim frames [ ept f rames++] & ˜0 x f f f ) | 0x7 ; f o r ( pd idx = 0 ;
( u i n t 64 t ) idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) <= memory present && pd idx < 512 ;
pd idx++ ) {
/∗ get a new PT and i n i t i a l i z e the pd entry ∗/ pt = map phys to temp virt ( shim frames [ ept f rames ] ) ; ( ( u i n t 64 t ∗)pd ) [ pd idx ] = ( shim frames [ ept f rames++] & ˜0 x f f f ) | 0x7 ; f o r ( p t idx = 0 ;
( u i n t 64 t ) idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) <= memory present && pt idx < 512 ;
p t idx++ ) {
/∗ i n i t i a l i z e the pt entry ∗/ ( ( u i n t 64 t ∗) pt ) [ p t idx ] =
( u in t 64 t ) idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) | 0x37 ;
/∗ s t r i p out chaching i f noncacheable ∗/ f o r ( i = 0 ; i < nocache f rames idx ; i++ ) {
i f ( idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) == nocache frames [ i ] ) { ( ( u i n t 64 t ∗) pt ) [ p t idx ] &= ˜( u in t 64 t )0 x30 ; break ;
} }
/∗ s t r i p out read /wr i t e pe rmi s s i ons i f k e rne l page ∗/ f o r ( i = 0 ; i < ke rn page s idx ; i++ ) {
i f ( idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) == kern pages [ i ] ) { ( ( u i n t 64 t ∗) pt ) [ p t idx ] &= ˜( u in t 64 t )0 x3 ; ( ( u i n t 64 t ∗) pt ) [ p t idx ] |= 0x4 ; break ;
} }
/∗ s t r i p out a l l pe rmi s s i on s i f shim page ∗/ f o r ( i = 0 ; i < sh im frames idx ; i++ ) {
i f ( idx2vaddr ( pml4t idx , pdpt idx , pd idx , p t idx ) == shim frames [ i ] ) { ( ( u i n t 64 t ∗) pt ) [ p t idx ] &= ˜( u in t 64 t )0 x7 ; break ;
} } } } } }
Snippet 4.1: C code for building ExOShim’s EPT table. The table is an identity map, but frames that are kernel code, used for the shim, or uncacheable are set with special permissions. Cleanup from this routine should include deleting all temporary virtual mappings
61
marked with these permissions. With access to a paging structure for any process into
which the kernel is fully mapped, ExOShim can thereby infer which frames contain
kernel code, shown in line 13 of Algorithm 4.1. Subsequently, ExOShim can mark all
corresponding frames in the EPT as execute-only at the time of EPT creation.
ExOShim Frames
ExOShim is designed so that an attacker cannot disable, modify, or hijack its pro-
tection mechanism after initialization no matter how deeply the rest of the system
is compromised. In order to achieve this, ExOShim does not take input after initial-
ization time and, more importantly, marks all ExOShim memory, as non-readable,
non-writable, and non-executable in the EPT.
Care is needed to thoroughly and systematically mark all memory needed by
ExOShim with no permissions in the EPT. All of the frames supporting each of the
following parts of ExOShim need to be protected in order to prevent an attacker from
tampering with it.
ExOShim Code Preventing the kernel from accessing ExOShim code (line 5 in
Algorithm 4.1) is possible only when all its code is loaded onto frames with no other
data. While having access to the code might allow an attacker to attempt to install
a second virtualized monitor, since ExOShim has already been instantiated, this op-
eration would fail and ExOShim would consequently enter its fault handling routine.
However, a compromised kernel could overwrite ExOShim’s error handling routine if
it is not marked as inaccessible in the EPT.
ExOShim Call Stack When a fault occurs and ExOShim is invoked, it needs a
stack to operate. The address of this stack is loaded by the ExOShim initialization
routine. If the stack were not protected, an attacker could store a ROP style payload
on the stack, cause an ExOShim fault, and run arbitrary code without the protection
62
offered by ExOShim. By disabling kernel access to the ExOShim stack using the EPT,
this attack vector is closed to the attacker. The call stack is reserved as protected
shim memory in line 7 of Algorithm 4.1.
ExOShim Data There is certain data that ExOShim needs to maintain during its
initialization routine. This includes the list of kernel, ExOShim, and uncacheable
frames that need special handling and virtualization- specific structures as discussed
in Section 4.3.3. If an adversary could tamper with this data, it would be possible to
compromise the state of ExOShim. To prevent this, the data is marked as inaccessible
in the EPT. However, this cannot be achieved if the data is stored in the kernel’s heap.
In order to guarantee that no ExOShim data is stored in the heap, the prototype
unmaps the heap from the ExOShim context on entry to its initialization routine,
as shown in lines 1 and 2 of Algorithm 4.1. As a result, when ExOShim needs
memory, it must use the underlying kernel memory management layer to request new
frames. These are then marked appropriately in the EPT. This is shown in line 5 of
Algorithm 4.1.
The EPT Perhaps the most important memory that the kernel must be prevented
from accessing is the EPT tables themselves. These are frames of memory that the
hardware traverses in order to uncover the permissions associated with a particular
frame. If an attacker could modify these, it would be possible to disable or hijack
ExOShim. Therefore, all frames used for the construction of the EPT structures
must be marked in the EPT as untouchable as shown in line 6 of Algorithm 4.1. Any
attempt to read, write, or execute any of the memory in the EPT structure will cause
ExOShim to interrupt the kernel.
ExOShim Paging Structures Finally, line 8 in Algorithm 4.1 shows that the
paging structures that define the ExOShim context itself must be set with null per-
63
missions in the EPT. When an EPT violation occurs, the hardware switches into the
non-virtualized context of the ExOShim and directs control to the pre-defined fault
handler. If the attacker could modify the page tables that define this context, it
would be possible to disable or hijack ExOShim. Marking all of the paging structures
that define ExOShim ensures that in the event of a fault, the code that is executed
is exactly what was intended at initialization time.
Uncacheable Frames
The abundance of internal processor cache memory improves performance of all sys-
tem tasks. The Memory Management Unit (MMU) manages what memory addresses
are contained in and outside of the cache internal to the processor boundary. This is
especially important when traversing the four level paging structures of the virtual
memory or the EPT system. Having these structures internal to cache reduces page
translation times for the MMU. However, there are certain system memory pages
contained in these structures that must never be maintained in the cache. If these
pages are cached, read operations may return stale or incorrect information about
the state of the page. The particular pages that must be considered will vary on
each kernel being protected. Those described here serve as a guide to the types of
pages that must be considered. For ExOShim on Bear, pages that must be marked
uncacheable in the creation of the identity mapped EPT are concerned with the VGA
driver, Interrupts, and Memory Registers associated with the Network Card. These
correspond to lines 11, 9 and 10, and 12 in Algorithm 4.1, respectively.
The prototype kernel uses legacy Basic Input/Output System support for its VGA
driver. This is a block of low memory, which when written into, determines what
characters, color, and screen position to place information on the monitor. If this
memory is cached, when the processor accesses the VGA memory, the MMU will not
traverse the EPT, but access the internal cache. When the cache page is accessed the
64
last character or configuration setting will be returned to the processor, which will
result in an undefined opcode exception. When these pages are marked uncacheable
the MMU traverses the EPT and is forced to go to external memory to find the latest
information contained in that memory page.
For interrupt handling the Advanced Programmable Interrupt Controller (APIC)
and Input/Output APIC (IOAPIC) are used. The processor determines the type of
interrupt that occurs by reading memory mapped registers on pages that are written
to by these controllers. These pages refer to internal control logic rather than memory.
However, when caching is enabled, just as in the VGA memory, the processor inter-
prets these pages as actual memory. Thus, instead of fetching information internal
to the processor the MMU attempts to access information contained on these pages,
which results in a page fault. Disabling caching of these pages forces the processor to
read its internal control structures, as the interrupt subsystem requires.
For the network card to perform Direct Memory Access (DMA), it also makes use
of memory-mapped registers called Memory Mapped Input/Output (MMIO) regis-
ters. The network card reports to the PCI subsystem what virtual memory pages it
requires for MMIO registers. The prototype kernel writes to these virtual memory
pages to program the network card for DMA. However, for the network card to be
aware of these changes it must poll these registers through the actual physical mem-
ory. However, if the pages are contained in the cache, the card will never receive
updated programming from the kernel on how to perform DMA. Forcing the pages
associated with MMIO registers to be uncacheable allows the network card to receive
the necessary information for DMA.
4.3.3 Starting Virtualization
Virtualization as seen on modern systems is typically described in terms of Type-1 or
Type-2 hypervisors. A Type-1 hypervisor runs directly on top of the hardware and
65
acts as an abstraction layer between the guest and the hardware. Type-2 hypervisors
run on top of an operating system and use system hooks into the operating system
kernel to enable the running of guest operating systems. ExOShim is unique in that it
must insert itself as a Type-1 hypervisor after the kernel has already started running.
This, and the requirement to protect kernel memory, requires some special handling
while enabling virtualization features.
Required Data Structures
Intel processors support a wide range of virtualization features and settings. The pro-
gramming of these is accomplished through the Virtual Machine Control Structure
(VMCS), shown on line 15 of Algorithm 4.1. To support any level of guest abstraction
the VMCS contains over one hundred configurable fields. These fields can be subdi-
vided into Execution Control, Exit Control, Entry Control, Host-state, Guest-State,
and Exit Information fields. ExOShim programs the control fields with only those
settings required to enable EPT and exit on catastrophic failure. It does not use Exit
Information fields as they are populated on vmexit; ExOShim simply halts execution
if a vmexit occurs. How ExOShim uses the Host-State (hypervisor) fields and the
Guest-State fields requires more detailed consideration.
Host VMCS State
The Host-State fields in the VMCS define the context of the hypervisor when control
is transferred from the guest to hypervisor during a vmexit. For ExOShim, they
contain the information needed to run an exit handler upon hypervisor reentry. In a
Type-1 hypervisor the CR registers, selectors, Descriptor Tables, and stack are setup
by the hypervisor itself and then programmed into the Host-State fields. ExOShim’s
unique status “between” Type-1 and Type-2 is advantageous in this case. The kernel
has already initialized these fields. Thus, they can be read from memory and loaded
66
into the Host-State fields. There is only one unique Host-state field: the location
of the exit handler to call when a vmexit occurs. This field is straightforward to
initialize, the address of the appropriate exit handler function is written directly into
the appropriate Host-State field.
Guest VMCS State
Typically, this is the initial state needed by a kernel to begin operation. In this
case, the kernel is already operating. Instead of launching another new kernel, the
goal of ExOShim is to let the existing kernel resume as if ExOShim had never been
initialized.
If ExOShim were a normal process, it would yield to the next process. This in-
volves saving and suspending the kernel context of the yielding process, and restoring
the context of the next process to be scheduled. ExOShim aims to emulate this proce-
dure; the guest instruction pointer (RIP), stack pointer (RSP) and paging structures
(CR3) are extracted from the next process’ saved state, accessed by invoking the ker-
nel scheduler. By invoking the scheduler and setting the guest state to match that of
the next process to run, ExOShim enables the kernel to carry on undisturbed when it
launches the virtual machine. One important note included in line 17 of Algorithm 4.1
is that the VMCS does not have a field for the guest stack base pointer (RBP), so
the base pointer must be manually set to that of the guest just before launching the
VM.
Additional challenges associated with the Guest-State fields are the Global De-
scriptor Table (GDT) and Task State Segment (TSS). Unlike the Host-State fields,
the guest requires significant detail regarding the information contained in the GDT
pertaining to access rights and segmentation. ExOShim must restore the state found
in the kernel exactly. If a single bit in this field does not match the running guest
state, the guest cannot resume operation. For Type-1 and Type-2 hypervisors the
67
guest can populate these fields for the hypervisor. The nature of ExOShim’s insertion
process makes this impossible. Fortunately, the GDT containing this information can
be read from memory using the sgdt instruction. From there it can be dissected and
loaded into the necessary Guest-State fields. The TSS information for guest operation
is contained at a set offset inside of the GDT.
Launching the VM (Resuming the Kernel)
To return operation to the kernel from ExOShim, a vmlaunch instruction must be
executed to change the processor’s operating context, as shown in the final line of
Algorithm 4.1. Upon execution of this instruction, the Transition Lookaside Buffer
(TLB) is flushed to prevent accidental, or unauthorized, guest and hypervisor sharing.
The processor then reads the data stored in the VMCS fields to ensure they are in a
legal configuration. Upon passing these checks the processor then resumes operation
of the guest context, which is the next process to be scheduled by the kernel.
From this point forward ExOShim will only run again in one of three cases: The
first is an unlikely catastrophic failure in the guest’s interrupt system, which will
cause a triple fault and vmexit. Without a hypervisor, the processor would hard
freeze in this case. The second case occurs if the guest attempts to read or write a
protected execute-only kernel code page. This will result in a vmexit associated with
an EPT violation. Finally, if the guest attempts to read, write, or execute a protected
ExOShim page; this will again result in a vmexit due to an EPT violation.
In the event that any of these conditions occur, the ExOShim vmexit handler is
invoked. In the prototype, this routine executes a processor halt instruction immedi-
ately. However, the handler could also preform other actions such as log the failure
or restart the kernel from a known gold-standard.
68
4.4 ExOShim: Evaluation and Analysis
In this section, the complexity of the ExOShim prototype is evaluated by counting its
lines of code; it is well known that the number of vulnerabilities is directly proportional
to lines of code [131]. The prototype’s performance is examined by comparing the
cycles consumed by the processor on a standard test suite, running on the same kernel,
both with and without ExOShim. Finally, a qualitative discussion of the threats that
ExOShim seeks to combat explores the protections offered by the prototype.
4.4.1 Prototype Complexity
ExOShim is implemented in terms of only two functions: an initialization/installation
function and the exit handler function. The initialization function requires some
memory management code, a handful of routines to detect the 3 types of special
memory by the EPT as discussed in Section 4.3.2, and initialization for the VMCS
structure. All told, the initialization routine comprises 290 lines of code. The simple
handler that deals with terminating execution if the kernel violates any of the EPT
permissions set forth adds only 35 lines of code. However, these routines rest upon
kernel functions already present in Bear. As a point of comparison regarding the size
of attack surface, the popular Xen hypervisor is approximately 150,000 LOC while
ExOShim totals 325 LOC.
4.4.2 Performance
Performance benchmarks were run on a Dell Optiplex 9010 workstation with 4 GB of
RAM and an Intel core i7-3770k quad-core 3.5 GHz processor with an 8 MB cache.
In addition to the industry-standard AIM9 arithmetic [6] and malloc [103] tests, a
macro-scale benchmark suite packaged with [123] was included. This test suite con-
sists of a series of tests that exercise different parts of the kernel. This primarily
69
Test (CPU Cycles) Multiply (×1010) Add (×1010) Divide (×1011) malloc (×1011)
No ExOShim Max 2.2214 1.3435 1.0733 1.1227 Min 2.2213 1.3248 1.0733 1.1225 Avg 2.2214 1.3364 1.0733 1.1226
ExOShim Max 2.2215 1.3392 1.0734 1.1228 Min 2.2214 1.3285 1.0734 1.1226 Avg 2.2215 1.3315 1.0734 1.1227
Average Performance Cost (%) 0.005 -0.4 0.01 0.01
Table 4.1: AIM9 Benchmark Suite [6] and Malloc Test [103] Performance Measure- ments - 100 Trials per test (column). Each test reveals a negligible performance impact.
consists of memory intensive queue, heap, hashmap, and inter-process communica-
tion tests. Network tests were not included in the test suite in order to eliminate
non-deterministic network based latencies from hiding the effects of ExOShim on
performance.
Table 4.1 shows that the AIM9 [6] and malloc [103] benchmarks reveal truly neg-
ligible performance costs. This is a startling testament to modern caching technology.
Without ExOShim, every memory access uses a 4-step page table translation mecha-
nism (if not found in the TLB). With the EPT from ExOShim, however, each of those
4 steps must go through its own 4-step EPT walk (if not cached). To accomplish this
additional level of indirection with such little performance cost is truly impressive.
While there may be a risk of exhausting the EPT’s cache layer, the memory-intensive
malloc benchmark test did show any such tendency.
In order to test the system on a more macro-scale, the memory-intensive Bear
test suite was run 425 times on the same machine – once with ExOShim installed
and once without. In each instance of each test case, the clock cycles needed to
complete all tests in the suite was recorded. The results of these tests are shown as
boxplots in Figure 4.3. Note that the extreme outliers in Figure 4.3a hide detail from
the boxplots; Figure 4.3b shows a closer view of the boxplots, hiding the extreme
outliers.
The overall performance cost of ExOShim is estimated by comparing the average
cycle count for a full test suite iteration without ExOShim to that with ExOShim. A
70
With Shim Without Shim
5. 0e +1 0
1. 0e +1 1
1. 5e +1 1
2. 0e +1 1
C lo
ck C
yc le
s
(a) Outliers Included
With Shim Without Shim
3. 8e +1 0
4. 0e +1 0
4. 2e +1 0
4. 4e +1 0
C lo
ck C
yc le
s
(b) Outliers Excluded
Figure 4.3: Boxplots of Bear’s Benchmark Suite Performance. Plots are shown both with and without the observed outliers included. Because the outliers were found in both the experimental and the control test case, they clearly represent and unexpected artifact of the underlying system.
summary of the test results can be found in Table 4.2, shown both with and without
the outliers.
Even with the outliers included there is only a 4.85% performance cost for using
ExOShim to make the kernel code execute-only. However, the outliers appear both
with and without ExOShim. Clearly, they represent an unanticipated artifact of the
test suite or kernel. Without the outliers, the performance overhead drops to a nearly
negligible 0.86%.
4.4.3 Security Implications
The security benefits of using ExOShim are clear: it substantially increases attacker
workload. Without read permission on kernel code pages, traditional memory disclo-
sure bugs at the kernel level are obsolete. This mitigates an entire range of information
leakage-based attacks, including various forms of ROP. An execute-only kernel binary
71
Test Case Without ExOShim With ExOShim Outliers Included No Yes No Yes
CPU Cycles (×1010) Max 4.492 20.64 4.511 20.67 Min 3.686 3.686 3.706 3.706 Avg 3.850 3.921 3.883 4.111
Performance Cost (%) 0.86 4.85
Table 4.2: Performance Benchmark Test Results. Benchmark test suite is packaged with Bear and includes many varied test cases, approximating throughput for a nor- mal general-purpose system load. Data is listed for cases with and without including the outliers found in the data.
also inhibits most reverse engineering techniques, which rely on reading code.
Even with ExOShim, attackers can still learn some facts regarding the layout of
the address space. For example, it is possible to read return addresses off of the
stack and function pointers stored in data to learn about the location of code. This
has been used to construct JIT-ROP attacks [49]. However, a system that employs
fine-grained function and block level diversity [86] devalues this information. With
thorough code randomization, an attacker must read the code in order to know exactly
where gadgets are located; finding the entry point to a function is not sufficient.
An added security benefit of using ExOShim comes simply from turning on virtu-
alization. The first entity to enable virtualization owns the processor [144]. Without
a virtualized component, an operating system running on bare metal is vulnerable to
VMM rootkits such as [55]. With ExOShim initialized, any attempt to install such a
rootkit would invoke the ExOShim exception handler.
4.5 ExOShim: Conclusion
4.5.1 Future Work
There are many possible extensions of the current prototype that can be explored
further.
72
The current prototype of ExOShim replaces the hypervisor otherwise packaged
with [123]. This defeats the opportunity for more complex tasks being executed in
the hypervisor. Fortunately, Intel virtualization technology allows nested virtualiza-
tion. This would allow for the shim to initialize underneath the kernel, even if the
kernel is already operating on top of another hypervisor. Support for this capability
requires adding functionality to the underlying hypervisor, not to ExOShim. Addi-
tionally, ExOShim-like protections can be added to the EPT tables of any hypervisor.
However, because the more complex implementation will take input, either of these
solutions sacrifices the desirable property that ExOShim cannot be modified, hijacked,
or disabled.
Although the microkernel is a full 64-bit multicore implementation, ExOShim
currently operates on a single core. To generalize the implementation will require
initializing ExOShim once per core; each core must be virtualized independently. It
would also be possible to place different permissions in the ExOShim EPTs with
different cores assigned to specific tasks.
Currently, devices that support Direct Memory Access (DMA) are a known threat
to the protection provided by ExOShim. These devices make memory requests with-
out passing through the EPT translation provided by ExOShim. Intel’s VT-d vir-
tualization extensions are designed to eliminate this problem by providing a table
structure similar to the EPT that defines a translation mechanism through with
these devices must pass. In fact, the same memory can be used for both the EPT and
the VT-d tables. Therefore, ExOShim can eliminate the DMA threat by enabling
and configuring VT-d’s DMA remapping functionality.
4.5.2 Final Thoughts
ExOShim is a novel technique in which an operating system deploys a thin “shim”
virtualization layer that uses Intel’s EPT hardware to provide execute-only protection
73
to all kernel code. This prevents all direct memory disclosure scenarios. The attacker
cannot read kernel code directly. Thus, an entire class of kernel-level attack vectors
is denied by prohibiting the attacker from disassembling kernel code pages to find
gadgets for any type of code reuse attack.
The method illustrated by ExOShim relies on kernel code being loaded onto unique
pages. This can be performed at compile- or load-time, and can be combined with
software diversity and randomization. When combined with function and block level
diversity, even an indirect memory disclosure (such as reading a return address from
the kernel stack) does not provide sufficient information to harvest gadgets. The
ExOShim prototype discussed here operates in conjunction with Überdiversity and
KPLT.
This work demonstrates that modern commodity hardware does support a hardware-
enforced execute-only primitive that can be deployed to prevent kernel level exploits.
It also shows that the flexibility of Intel’s virtualization technologies allows the shim
layer to protect itself from being disabled or hijacked by an attacker.
The 325-line ExOShim prototype denies an entire class of common attacks at
the kernel level while significantly increasing the workload associated with surveil-
lance, reverse engineering, and exploit development. Due to caching technologies in
modern Intel processors, the ExOShim prototype here was measured to introduce a
performance cost of only 0.86%.
74
Chapter 5
Diversification: KPLT
In Bear, one important security feature is the absence of shared objects. Despite
the protections offered by methods such as copy-on-write (CoW), Bear chooses a
strict security model in which there is no shared memory between processes. Process
communication happens via an MPI-based message passing interface. The fact that
each process has its own copy of all executable code easily allows the same code
for each process to be loaded in two unique locations, increasing the diversity of the
system to include unique images per-process. However, the kernel is rarely considered
in the same way as user processes. It is standard practice for the kernel to be mapped
into the virtual address space of every process. After all, every process needs access
to the kernel’s functionality. The kernel is never considered “shared” memory in the
conventional sense, but upon closer inspection, the kernel does show similar attributes.
More precisely, the kernel is commonly mapped in the same location for every user
process. The idea of treating the kernel like a shared object is explored in this chapter.
By setting up a Kernel-level Procedure Linkeage Table (KPLT), the diversity of the
system was increased by mapping the same (shared) kernel functions into a different
virtual address for each process.
While Section 3.3 reviews prior work in the field of software diversificaton, this
75
chapter explains the framework and mechanisms that allow the KPLT to increase
diversity by changing the addresses of kernel functions on a per-process basis. It
also gives a detailed account of the implementation of a prototype KPLT within the
context of the Bear operating system. Furthermore, it contains a discussion of the
general approach and its strengths and weaknesses as well as possible extensions of
the current prototype.
5.1 KPLT: Overview
The KPLT is a table that allows for the same kernel functions to be loaded at different
addresses in different processes’ address spaces. It allows the footprint of the kernel
in a process to be unique not only per-boot, but also per-process. This increases the
diversity of a system.
In this section, the core ideas and features of the KPLT are explored. The use of
the virtual memory abstraction is discussed, and the contents of the entries inside of
the KPLT are presented. These entries are documented at the byte level, in order to
see how each entry in the KPLT uniquely operates.
5.1.1 Using the Virtual Memory Abstraction
The idea behind the KPLT uses the paradigm of dynamic loading to map common
kernel functionality at different virtual addresses in each process’ address space. In
order to illustrate the mechanics involved, it is important to first look at the way
control flow would go through a series of function calls without the KPLT. The
appropriate scenario to illustrate this is a function, load elf proc, calling another
function, kputs. These two functions are used in the Bear system to load an elf
binary into user-space and print a string from kernel-space onto a serial back channel.
Figure 5.1a shows the normal control flow when these are loaded.
76
Process A Virtual Address Space
System Physical Memory
Process B Virtual Address Space
kprintf
kernel_do_exec ... call <kprintf> ...
kernel_do_exec
kprintf
1
3
2
kernel_do_exec
kprintf
1
3
2
(a) The normal path of execution when calling kputs
from load elf proc for two processes Process A Virtual
Address Space System Physical
Memory Process B Virtual
Address Space
kprintf
kernel_do_exec ... call <kprintf> ...
kernel_do_exec
kprintf
1
3
2
kernel_do_exec
kprintf
1
3
2
KPLT KPLT
KPLT_A
KPLT_B
4
5
4
5
(b) The path of execution when calling kputs from load elf proc for two processes with KPLT
Figure 5.1: Control flow shown with and without KPLT. Normally, the call instruction changes the instruction pointer directly to the address of the function. With the KPLT, the call instruction forces execution into the table, where it then jumps to the process-specific address of the function.
In Figure 5.1a, the control flow for each of Process A and Process B is laid out in
numbered arrows. A key thing to note is that the second step of the process, the call
from within load elf proc to kputs, will always resolve to the same virtual address
for each process, because each process is reading the same instructions from physical
memory. This is what requires that each process have the physical implementation
of kputs mapped into the exact same virtual memory location.
The introduction of the KPLT is shown in Figure 5.1b. It is important to note
that the second step in the control flow for each process still resolves to the same
place in memory. However, this time that place is not the implementation of kputs
but rather an entry in the KPLT. The kputs entry in the KPLT is located at the
77
same virtual address in both processes, but the virtual memory abstraction allows a
unique mapping of underlying physical frames for the same virtual address ranges in
the two different processes. The unique physical memory allows each process to read
different data at the common virtual address, which explains how the third labeled
step for each process resolves to a unique address.
Another important note is illustrated in step number 4 for each process. During
the second step, the virtual memory abstraction allowed the system to map different
physical memory to the same virtual address for two different processes. At this fourth
step, the virtual memory abstraction provides the opposite functionality; different
virtual addresses in each process resolve to the same physical memory: the physical
implementation of kputs. This allows the processes to share the kernel functionality,
but forces them to use different addresses to access it.
5.1.2 The Contents of a KPLT
Figure 5.1b shows how control flow passes through the KPLT to the process-specific
virtual address of the function requested, but it just shows a dotted line to describe
this process. In fact, the actual KPLT entry is not much more difficult than a dotted
line. The objective of the entry is to jump to a given virtual address. However, the
jumps beginning and ending points are loaded non-deterministically into the 64-bit
virtual address space.
In order to facilitate the largest possible jump, the KPLT entries move a full 64-bit
address into a register, and then jump to the address in that register. The assembly
code for this operation is shown in Figure 5.2.
movabs $0xfeedcafebabefood,%rax
jmpq *%rax
Figure 5.2: Assembly instructions for a KPLT entry that points to 0xFEEDCAFEBABEFOOD.
78
unsigned char kplte [20];
kplte [0] = 0x48;
kplte [1] = 0xb8;
for ( i = 2; i < 10; i++ )
kplte[i] = (function_addr >> ((i -2)*8)) & 0xFF;
kplte [10] = 0xff;
kplte [11] = 0xe0;
*( uint32_t *)(& kplte [12]) = function_size;
*( uint32_t *)(& kplte [16]) = function_align;
Snippet 5.1: This code snippet creates a code entry in the KPLT that jumps out of the table to the implementation of the function being sought.
At least 12 bytes are needed for the type of KPLT entry shown in Figure 5.2.
However, there is some other metadata that needs to be recorded about functions
that are routed through the KPLT. In particular, the function size and alignment re-
quirements are both useful after load-time, when such information would normally be
discarded. As such, the prototype uses an additional 8 bytes to store this information
after the byte-code shown in Figure 5.2. This makes the overall size of a KPLT entry
20 bytes. Building such an entry is shown in Snippet 5.1.
5.2 KPLT: Implementation
This section discusses the implementation details of the KPLT. There are two main
parts of the prototype implementation: the load-time part and the run-time part.
The load-time part refers to the work needed to be done at the load-time of the
kernel. This work is done by a bootloader, not the kernel itself. Meanwhile, the
run-time part occurs during the run-time of the kernel, at the load-time of each user
process.
79
5.2.1 KPLT Creation at Load-Time
In this chapter, “Load-Time” refers to the load-time of the kernel unless otherwise
noted. This section describes Bear kernel loading process for context and the work
that needs to be done to initialize the KPLT at the kernel’s load-time.
Bear’s Kernel Loading Process
The kernel is loaded by a second-stage bootloader, boot2. A first stage, boot1, brings
the processor from real mode into long mode. Then, boot2 loads and bootstraps the
ELF file that will run on the processor at steady-state; the kernel.
Because boot2 operates in long mode, it has all of the capabilities that the kernel
will have. In order to facilitate its work, it initializes a kernel-heap and a frame array,
which is made up of structures describing physical memory available on the system.
The kernel inherits these structures by reading general purpose registers as soon as it
starts running. This process is important because boot2 chooses random addresses
for the kernel heap and frame array, so the kernel must retrieve the location at which
they were stored.
In order to support diversification of the kernel binary, boot2 uses an ELF “di-
versity” loader. This loader has the capabilities of not only loading the kernel, but
also randomizing the addresses of each of its sections. The kernel is compiled with
GCC’s -ffunction sections so that every function is a section that can be loaded
dynamically.
After loading each section into a random virtual address, the diversity loader calls
two routines per loadable unit: move unit and fixup unit
The move unit function redefines the unit’s symbols to reflect its new location.
It also updates relocation entries associated with the unit.
After all units have had their symbols and relocations updated with their new
randomized values, fixup unit is called for each of the units. This routine resolves
80
external relocations for the unit. In other words, after all of the symbols have been
updated, each unit finds the updated value of the symbols it needs to resolve.
The KPLT at Kernel Load-Time
Now, the work that was needed at kernel load-time to support the KPLT prototype
will be discussed. The only tasks that need to be accomplished for the KPLT at
kernel load-time are to allocate and construct a KPLT, and point references to KPLT
functions at the table.
The facility that scans memory and picks random locations for arbitrary diversity
units is used to place and allocate a KPLT. Thus, by defining a size and alignment re-
quirement, the diversity subsystem chooses a random place within the virtual address
space to place the KPLT.
Building the KPLT and ensuring that the references are fixed to point to the table
instead of the function itself are both handled in move unit. As each unit is passed
to the routine, move unit iterates through all symbols defined by that unit. First, it
is decided whether a given symbol belongs in the KPLT. The ELF standard explains
how to make sure the symbol is the symbol of a function using the ELF64 ST TYPE
macro. The ELF metadata also determines whether the function is static using the
binding attribute.
Once a symbol is determined to belong in the KPLT, a KPLT entry is made for
it as shown in Snippet 5.1 and stored at the next empty index in the KPLT. Then,
importantly, the symbol’s value in the symbol table is set to be the address of the
KPLT entry that was just constructed and written. This way, when other functions
request the value of the function symbol during the fixup unit routine, they will be
told that they should call the function at the address of the KPLT entry. This is the
mechanism that creates the second numbered control flow transition in Figure 5.1b.
The only remaining detail is passing the address of the KPLT through to the
81
kernel from the bootloader. When the kernel is booted, it retrieves the address of the
KPLT from the appropriate register.
5.2.2 Run-time KPLT Maintenance and Manipulation
Most of the work for the KPLT comes during run-time. Specifically, whenever a new
process is created, the addresses of the functions in the KPLT are re-randomized
for the new process. Although a particular process’ KPLT could be randomized
throughout its lifetime, that was not implemented for this prototype.
New Process Creation in Bear
For both practical and security reasons, it is not straight forward to alter the memory
of another process. However, process creation is defined as (dramatically) changing
the memory of another process. To create a new process in Bear, the parent examines
all of its own virtual memory. Whenever it finds a mapped frame, it chooses what
actions to take on behalf of the new process. For example, a global supervisor page
should create a new mapping for an existing frame of memory while a user page
should map a new frame and copy the data.
If mapping a new frame is required, the parent uses the virtual memory layer
to request a page of memory at a temporary address. It uses that address to write
data as necessary to the frame, and will later delete the virtual mapping without
clearing the memory on the frame. This will remove its temporary mappings into
another process’ memory from its page tables, but will also mark the frame as being
unmapped. As such, a queue of mapped frames is maintained so that after creating
the new structures, the parent can manually update the frame array so that it knows
that the frames are actually in use by the new process.
In general, when it is found that a new process needs some memory, the parent
allocates it, constructs the appropriate linkages to create a meaningful paging struc-
82
ture using the temporary mappings to the memory, then upon completion removes
the temporary mappings, and then retroactively corrects the virtual memory layer to
leave the memory as “taken” as if the new process had requested it itself.
Working with the KPLT during Process Creation
At process creation, there are three tasks to handle with regard to the KPLT. The
implementation will be described in terms of each of these three steps.
1. Recalculate: Find new random addresses to use for the functions found in the
KPLT
2. Rebuild: Build the new KPLT with the new random addresses
3. Remap: Remap the functions found in the KPLT from the address the parent
uses (where the function was copied during process creation) to the new random
address
The entire process creation, less the freeing of the temporary mappings and the
frame array fixups, is completed before the three steps listed above. After taking care
of the KPLT, the normal cleanup previously described is completed.
Recalculate The Recalculation step involves generating new random addresses for
each function in the KPLT. This step is fairly straightforward, and is largely unrelated
to the details of process creation. Since it is known that all addresses of all the
functions in the KPLT will be changed and the size of the KPLT functions are stored
in the table itself, each KPLT entry can be read from the table in its current form
and the memory consumed by the function described by each entry is added to the
pool of available memory for placing functions. Note that this prototype does not yet
reclaim virtual memory occupied by the parent’s user pages even if the child will not
share those pages.
83
One important implementation note has to do with the alignment of the new
random addresses chosen for a given function. When a function was placed at load
time, the function was copied onto one or more 4Kb physical frames of memory at
some offset. When a new address is chosen for a function, it is selected so that the new
address by which the function is accessed is the same physical frame. This results in
loss of control over the offset from a page boundary at which the function will start,
thus forcing the address of the new function to have the same offset off of PAGE SIZE
as the original address.
Rebuild The Rebuilding step is slightly more complicated. It is easy to generate
a new KPLT entry each time a new address is discovered for a KPLT function. This
process was shown in Snippet 5.1. The challenge comes when writing this new KPLT
entry into the new process’ KPLT. Recall that the KPLT, marked supervisor and
not global, was allocated with a temporary mapping during the process creation. To
recover that temporary mapping in order to write to the new process’ KPLT, a queue
search function is used on the list of temporary mappings that were previously made.
Once the temporary mapping to the child’s KPLT is found, it could be suspected
that it is trivial to write the KPLT entry. However, the KPLT entry might cross a
page boundary. Although that is not a problem when writing to one process’ own
KPLT, the temporary mappings to the multiple pages of the child’s KPLT may not
have been made sequentially. Therefore, if the KPLT entry crosses a page boundary,
the temporary mapping queue must be searched twice in order to copy the KPLT
entry in two pieces, one copy for each page.
Remap Remapping the functions from the parent’s KPLT-specified address to the
new address specified by the child’s KPLT is the most challenging part of the process.
It can be broken up into two pieces: preparation and execution.
A single loop over all KPLT entries can do the recalculation, the rebuilding, and
84
the preparation portion of the remap step for each KPLT entry. The preparation
portion of the remap step involves unmapping the function from its parent’s KPLT-
designated address and making a record that it needs to be moved to its new address.
All unmappings need to be done before any actual remapping because two functions
could have been swapped: trying to remap one without unmapping the other would
trample important state. Although unmappings could leave unused paging structures
dangling off of the child’s page tables, this prototype ignores that risk. The virtual
memory system will reuse those structures if anything is mapped into their range in
the future, and will free them at process destruction.
After zeroing the appropriate page-table entry, an address is found or created for a
record structure to describe the physical address of the function implementation and
the virtual address by which the child will eventually wish to access it. This record
is stored into a “todo q”. The process of deleting a page table entry and saving a
record to handle later is in a do-while loop to handle functions that reside on multiple
pages.
Finally, all of the records kept in the “todo q” are traversed. For each record, the
creation of the appropriate mapping from the correct place in the child’s page tables
to the physical address of the function is made. This involves diving down one layer
at a time and either finding the current temporary mapping to the child’s paging
structure, or allocating and setting up a new chain of paging structures for the child.
Finally, when all of the todo records have been handled, the standard cleanup of
process creation can be finished. When the new child runs, the addresses in its KPLT
entries will differ from those of its parent. Consequently, it will use different virtual
addresses than its parent to access the same physical memory where kernel functions
are implemented.
85
5.3 KPLT: Evaluation and Analysis
5.3.1 Security Implications
Exploitation Resilience
The use of a KPLT to change the virtual addresses of common kernel functions on a
per-process basis has huge potential for defeating exploits. On the most basic level,
an attacker looking for a vulnerable instruction in the diversified kernel will now not
only have to search for the instruction per-boot, but also per-process.
In particular, the KPLT increases a system’s resilience to Return-Oriented Pro-
gramming (ROP) [140]. With the KPLT, the attacker’s gadgets are only valuable
within the address space of a single process. Suppose an attacker correctly guesses
the address of a gadget; if one wrong guess crashes their current process, the previ-
ously correct guesses are now invalid. This dramatically increases attacker workload
and decreases the likelihood of success for a ROP attack.
Security Concerns
The main concern with the KPLT is that it is a sort of “honey-pot.” It gathers a
lot of valuable information in one place. If an attacker needed access to n particular
functions, the KPLT makes their job only 1 n
as hard as it was before. Finding the
KPLT can give him access to all of the functions within the current address space.
Furthermore, the KPLT is in a constant location across address spaces. So, finding
the KPLT eliminates the challenge posed by randomizing kernel function addresses
on the fly.
Fortunately, there are ways to mitigate the risk that the KPLT poses. The fist has
been implemented by this prototype: randomize the location of the KPLT at boot.
This means that finding the KPLT is just as hard as finding a particular function.
For any attack that does not require access to multiple specific functions, the KPLT
86
does not help the attacker.
Lastly, there are several ways that the security concerns presented by the KPLT
can be mitigated. One of these includes using page-fault handlers or virtualization
features to implement an execute-only policy rule on the KPLT memory. This is
compatible with ExOShim, as discussed in Chapter 4. Another is to place the KPLT
into a hypervisor: the KPLT entries would be vmcalls. Finally, one could randomize
the address of the KPLT itself at run-time by maintaining and updating the symbol
relocation data and modifying the relocations at run-time.
5.3.2 Increase in Diversity
The increased diversity from the KPLT comes from changing the addresses of kernel
functions in each address space. Speaking quantitatively, this increases the number
of possible variations in a program. In Chapter 6 Überdiversity calculates that there
are as many as 108025 different variations of a basic shell that the algorithm could
produce; but that number only held true for the first shell launched between boot
ups. Subsequent shells had a fixed kernel layout, so given the layout of the first, the
number of variations of the second decreased dramatically.
The KPLT recovers some of that loss. Due to the fixed location of the KPLT itself
and the requirement that all function addresses across process address spaces have
the same offset from PAGE SIZE, it fails to bring the number of variants for the second
instance all the way back to the number for the first. However, it does increase it
dramatically. This is bad news for an attacker that wants to persist on a system and
gather information about it; the system is a much more quickly moving target with
a KPLT implementation.
87
5.3.3 Performance Cost
Although the KPLT increases the number of instructions to do the same unit of work,
that is not the main cause of performance cost. When different address spaces using
different virtual addresses for the same code, global TLB entries cannot be used. This
limits the performance enhancements of caching. There are also obvious kernel and
user load-time overheads associated with the extra work of maintaining a KPLT.
Preliminary results suggest a performance cost of around 16%. This was measured
by running the standard Bear test suite multiple times both with and without the
KPLT and comparing the clock cycles required on average during each case.
5.3.4 Remaining Work and Challenges
The KPLT prototype discussed here still needs several enhancements that require
further research. It does not yet account for static functions. Special handling for
static functions in the ELF format allow for multiple static functions with the same
name to be defined in multiple different objects. This prototype also does not support
variable number argument functions. Note that a jump table will also not work with
the KPLT. The compiler must be configured to avoid using jump tables.
5.4 KPLT: Conclusion
In conclusion, the KPLT is a strong complement to the popular ideas about ASLR
and system diversity. The prototype implementation works for all global functions
as a proof of concept. Static functions and functions with variable-length argument
lists are not yet supported. Unfortunately, the technique is not compatible with the
hardware-provided caching technique of using global pages to lock kernel pages in the
TLB. A performance cost of 16% was measured for the prototype.
88
Chapter 6
Diversification: Überdiversity
A significant concern in the modern computer security landscape is vulnerability am-
plification; since all network connected systems and programs are instances of a very
small pool of possible operating system variants and programs, a single exploit can
be reused on many machines. This includes classes of exploits such as buffer over-
flows [105], return-oriented programming (ROP) [140], return-to-libc [34], and
many more.
Vulnerability amplification multiplies the potential reward for developing a single
exploit many-fold. Injecting randomness into software systems is a very popular
technique used to limit the impact of a vulnerability as summarized in Section 3.3. In
the case of load-time diversity, the attacker’s workload is also increased dramatically
because the effects of the randomization are not easily visible. Therefore, attackers
are forced to design exploits without a priori knowledge of the layout of a system.
Load-time diversity involves loading some number of discrete units of code or data
(sections) into memory at random locations. Überdiversity follows the example set
by [163] by loading the sections at different places within the vast virtual memory
space with blank space in between them. Code sections typically represent individ-
ual functions, but additional sections include global data, the heap1, and the stack.
1More precisely, a pre-set maximum size is set aside as a special section in which the contiguous
89
Although Überdiversity does not explicitly randomize within these sections, it is con-
ceptually compatible with other projects that randomize within functions [75, 132],
the heap [125], and the stack [35, 36, 64]. The address space generated after ran-
domization is extremely unlikely to share exploitable addresses with other program
instances loaded from the same source code.
Diversification efforts are often measured and compared in terms of “entropy”.
Unfortunately, this term is often ambiguous and has had multiple interpretations
in the literature. As an example, Davi et al. [50] claims that their implementation
achieves n! entropy, where n is the number of program resources being randomized.
Although the claim that [50] can produce n! address spaces is correct, the use of the
term “entropy” in this context is fundamentally different from other works. Davi was
actually discussing program variants, and this semantic confusion is not uncommon.
Both program variants and entropy are important metrics for any diversity implemen-
tation. This study clarifies the difference between these two complementary ideas and
formalizes a method for computing the less popular program variants measurement.
Although some of the other projects discussed in Section 3.3 do use a 64-bit
platform, the highest reported entropy is 29 bits in [96]. With a close upper bound
at 47 bits, Überdiversity provides the highest entropy. This makes it particularly
interesting as an exercise studying the effects of approaching hardware limitations,
since commodity 64-bit hardware provides an address space of only 248.
None of the other studies surveyed in Section 3.3 included substantial discussions
about the algorithm used to inject randomness. This is often overlooked as a trivial
component of an implementation. In the case of simple ASLR, which might choose
a single random address for a single loaded resource, this may be a fair assessment.
However, several studies in Table 3.4 are performing more complex and fine-grained
randomization. It is easy to consider an algorithm that seems to give random outputs
heap will grow at run-time.
90
Algorithm 6.1: Greedy Diversity Loader Algorithm. This algorithm produces address spaces in which any particular section is more likely to have a low address than a high one.
Input: The Address Space A & Sections to be Loaded S Output: Random location si.location ∀s ∈ S
1 Randomly shuffle S; 2 for i = 1 to |S| do 3 Choose random k : 0 ≤ k < |A|; 4 si.location← k; 5 A← {0, 1, ..., k − 1, k};
but actually produces some address spaces with higher probabilities than others, and
non-trivial to prove that an algorithm generates all possible address spaces with equal
probability.
6.1 Diversification Algorithms
Algorithm 6.1 produces random program variants with linear running time. Due to
these attractive properties, it is the algorithm used in the implementation presented
in [86], although it is not discussed in that paper. However, it is an example of an
algorithm that clearly does not produce address spaces with uniform probability. In
it, the sequence of random numbers chosen is monotonically decreasing, therefore sec-
tions are more likely to have low addresses than high ones. An even more convincing
algorithm, suggested as a uniformly random alternative to Algorithm 6.1 at an early
stage of this research, is shown in Algorithm 6.2. This algorithm picks a list of ran-
dom numbers, each one to represent a gap between two sections loaded into memory
(or between a section and the boundaries of the virtual address space). Then, the
numbers are scaled to fit the virtual address space. Surprisingly, even this algorithm
does not produce address spaces with uniform probability.
Proof. Line 2 of Algorithm 6.2 generates R, a set of |S|+ 1 random integers. Line 3
transforms R into T using a scaling routine, f(), so that the sum of the size of the
91
Algorithm 6.2: Scaling Diversity Loader Algorithm. This algorithm chooses enough random numbers for each to be a gap between two sections, then scales the random numbers to fit the available address space.
Input: The Address Space A & Sections to be Loaded S Output: Random location si.location ∀s ∈ S
1 Randomly shuffle S; 2 Choose |S|+ 1 random integers from 0 to RAND MAX {r1, r2, ..., r|S|+1} = R;
3 T ← f(R) where f(R) = ⌊ R×
( |A|−
∑ s∈S s.size∑ r∈R r
)⌋ ;
4 s1.location← t1; 5 for i = 2 to |S| do 6 si.location← si−1.location + ti;
sections plus the random numbers in T will fill the address space entirely. Then, the
|S|+ 1 scaled random numbers in T become the gaps between the sections when they
are loaded into memory.
The vital observation is that T to R is not a 1:1 mapping. If f(R) = T , then
f(2R) = T , f(3R) = T , etc. However, each T results in exactly 1 possible address
space. Let f−1(T ) be set of all sets of R such that f(R) = T . So, f−1(T ) = {R :
f(R) = T}. Since all possible sets R are equally likely and each T generates a unique
address space, uniform randomness implies that, given T , @T ′ : |f−1(T )| 6= |f−1(T ′)|.
Unfortunately, this is not true. Intuitively, if a set of numbers in R is not big
enough to fill the address space and needs to be scaled up, then the resulting numbers
in T will be larger. In other words, the process of scaling means that address space
layouts with small gaps between sections are less likely than those with large gaps
between sections. More formally, consider a set T in which all members are even.
In this set, f−1(T ) ⊇ {0.5T, T, 2T, 3T, 4T, ...}. However, if T ′ contains one or more
elements of value 1, 0.5T ′ /∈ f−1(T ′) since only integers are relevant, and no element
of an R that had to be scaled up could result in a value of 1. Therefore, ∃T, T ′ :
|f−1(T )| 6= |f−1(T ′)|. By proof by contradiction, this algorithm does not produce
address space layouts with uniform probability.
�
92
This is because during the scaling step, random number sequences that are too
small to fill the address space (need to be “scaled up”) will have an effective minimum
gap size between sections. In other words, program variants with a gap of size 1
between two sections are less likely than program variants with larger gaps, because
they can be produced only by random number sequences that exactly match or exceed
the size of the available virtual memory space.
While Algorithm 6.2 may be “random enough” for most applications, it is not
uniformly random across all possible address spaces. The choice between algorithms
that modulate efficiency, ease of implementation, and degree of randomness should
be an important and clear part of the design of any randomization scheme.
To contrast non-uniformly random Algorithms 6.1 and 6.2, this study presents an
algorithm based on the “Fisher-Yates Shuffle” [63] which shuffles an ordered list to
produce a permutation uniformly at random. Section 6.1.2 transforms the algorithm
into an instance of the Fisher-Yates Shuffle, proving that it produces a given permu-
tation of the address space uniformly at random; given some input (and assuming a
sufficient source of randomness2) no output is more likely than any other. The algo-
rithm represents a less efficient but more random point on the spectrum of techniques
from which a system designer can choose, and is shown in Algorithm 6.3.
One of the most powerful features of this algorithm is its ability to load sections
randomly within a discontiguous virtual memory range. This flexibility allows, for
example, loading some program within the entire available virtual address space, triv-
ially avoiding the hardware-unimplemented “noncanonical” addresses that split the
virtual address space into higher and lower halves. It also allows a unique capability
when diversifying programs within the conventional paradigm of user- and kernel-
space sharing a virtual address space. Specifically, a user process can be loaded into
all available virtual memory space after the kernel is loaded. This means that at
2Insufficient sources of randomness can lead to non-uniformly random address space layouts as in [113].
93
Algorithm 6.3: Generic Diversity Loader Algorithm. This algorithm chooses random numbers within the space of available loadable addresses, then walks the address space (skipping over already loaded sections) to find the address corresponding to that random number in the current state of the address space.
Input: The Address Space A & Sections to be Loaded S Output: Random location si.location ∀s ∈ S
1 for i = 1 to |S| do 2 Find Ai, the set of addresses available to load si; 3 if Ai = ∅ then 4 error; 5 Pick random k : 0 ≤ k < |Ai|; 6 Find the kth eligible address: ai,k ∈ Ai; 7 si.location← ai,k
run-time, there are no deterministic address ranges for kernel or user sections. This is
a departure from previous implementations of load-time diversity in which the kernel
was diversified in isolation within a predefined “kernel-space” virtual memory range,
and user programs only within a predefined “user-space” virtual memory range. Inter-
leaving kernel and user sections adds a significant level of complexity for an attacker
to deal with when developing an exploit.
6.1.1 Run-time Complexity and Termination Analysis
Algorithm 6.3 iterates over a fixed set S, and nothing within the loop could cause a
condition where it does not exhaust the set. Therefore, it will terminate.
The algorithm iterates over S and twice over A within the main loop (at lines 2
and 6). If the address space is represented as regions of available memory instead of
individual addresses, the number of regions will be proportional to |S|. Therefore,
the run-time complexity is O(|S|2).
There is a way to formulate FYS (and therefore may be a way to formulate the
algorithm presented here) in O(N) time [53]. However, in this case |N | is the size of
the available virtual address space. For any program, |N | >> |S|2. The algorithm
proposed here also has a much smaller memory overhead. For these two reasons, the
94
version we’ve presented is actually better than its in-place alternative.
The algorithm will terminate, but there is also a simple condition for the more
interesting outcome: completion without error. Expression 6.1 describes the condition
necessary for the algorithm to succeed without an error.
∀ si ∈ S, |Ai| 6= 0 (6.1)
First, observe that an address space is big enough for S if it is at least as big as
2× |S| copies of the largest section in S. This is stated as Lemma 1.
Lemma 1. Algorithm 6.3 will always succeed to load a set of sections S with size
S.size = ∑
s∈S s.size if, |A| ≥ 2|S| × sl.size where @ s ∈ S : s.size > sl.size.
Proof. The largest section in S, sl (given by definition: @ s ∈ S : s.size > sl.size),
will consume at least sl.size eligible addresses when it is placed. The concern is that
the space between some hard boundary, like address 0x0, and the location where sl
is loaded (al,k) is too small for any address within that range to be eligible to load
a subsequent section. In other words, the worst case is that loading each section
removes 2sl.size− 1 from the available address space. Therefore, for all |S| sections,
the maximum address space that could be consumed is |S|(2sl.size − 1) = 2|S| ×
sl.size − |S| < 2|S| × sl.size. Therefore, a single contiguous address range of size
2|S| × sl.size will be sufficient to load any set of sections. �
Lemma 1 shows that the algorithm will successfully load the kernel without error.
|A| is as big as 255 TB before anything is loaded. According to Lemma 1, this would
allow as many as 127,500 1 GB sections to be loaded. Since it is common for the
entire kernel to be loaded into a virtual memory region of just 1 GB, this is clearly
sufficient to load even the largest monolithic kernel into a blank-slate virtual address
95
space. No kernel section will be large enough to divide the address space such that
there is no sufficiently large memory space for some section. However, leveraging
the full strength of this algorithm involves loading a user-space application into the
virtual memory gaps left between the sections of a diversified kernel. In the typical
case, this will not pose any problem in the loading of a user process. Additionally,
the condition shown in Expression 6.1 can be satisfied even in the most dramatic case
with only a small consideration made at the load-time of the kernel.
The memory footprint of a monolithic kernel such as Linux is less than a few
gigabytes. As a worst-case scenario, assume that the memory footprint of a kernel is
many orders of magnitude larger: 20 TB. In another worst-case assumption, assume
that there are 1,000,000 unique sections for the kernel3.
Using these assumptions, there will be 235 TB of virtual address space available
for the user process. The concern is that this address space will be segmented into
unusable chunks. The 1,000,000 sections will force the address space to be segmented
into a maximum of 1,000,001 pieces for the user-space load-time iteration of the
diversity algorithm. These partitions will average about 235 MB. This means that
there will be at least one partition whose size is at least 235 MB; big enough for the
entirety of many user programs. However, it is highly unlikely that sections will be
placed so uniformly as to have only partitions of 235 MB remaining. The probability
is high that somewhere within the 1,000,001 available partitions, there is a single one
whose size is big enough to hold the entire user program as described in Lemma 1.
One can guarantee that an arbitrarily large user program will fit. Only a small
modification is needed to the initial diversification of the kernel to do so; add a
section su to the set of kernel sections, Sk, before the diversity algorithm is invoked
to load the kernel. Allow su to be randomly placed according to the algorithm, but
3Ubuntu’s exuberant-ctags package counted less than 500,000 functions in the entire source directory for Ubuntu version 10.10 and Linux Kernel version 3.13.0. Note that this includes all architectures and options, not all of which will be included in any particular kernel build.
96
do not map any physical memory into the virtual address space corresponding to su,
meaning that this section for the kernel becomes a contiguous region of eligible virtual
addresses for the user process. This guarantees that at load-time of a user process,
|A| ≥ su.size. By controlling su.size, one can satisfy Expression 6.1 for arbitrarily
large user programs. Lemma 1 shows exactly how large su.size should be for a given
program. Note that making this allowance does threaten the claim for uniformly
distributed outcomes; in an exceptional case where the entire user program must be
loaded into su, user sections will be more closely grouped than if this method is not
used.
6.1.2 Proof of Uniformly Distributed Variants
The benefit of randomization is increasing the number of possible variants of a pro-
gram to suppress vulnerability amplification and to increase the search space of an
attacker hoping to brute-force the system. These benefits are reaped most completely
if the search space is distributed uniformly across all possible variants. That is to say
that no variant of the program should be any more likely than any other variant. Al-
gorithm 6.3 produces a permutation of sections within the address space uniformly at
random; proven by showing that it is actually equivalent to the Fisher-Yates Shuffle
(FYS), which itself produces permutations of an array uniformly at random [63].
Throughout this section a particular visualization of the task of diversifying the
address space will be helpful. The diversification process is modeled as the task of
generating a random permutation P of the set N , where N is the set of sections to
load, S, combined with the blank units of memory, B, that will be present in the
address space after all of S is loaded. In other words, N = S ∪ B where |B| =
|A|− ∑
s∈S s.size. Each permutation of N represents a unique variant of the program
loaded into a virtual memory context.
The Fisher-Yates Shuffle is shown in Algorithm 6.4. Figure 6.1a gives a visual-
97
Algorithm 6.4: The Fisher-Yates Shuffle is an algorithm that produces a ran- dom permutation of a list. It is proven that all possible outcomes are equally likely [63].
Input: Some set N Output: P , a random permutation of N
1 while |N | 6= 0 do 2 Pick a random number k : 1 ≤ k ≤ |N |+ 1; 3 Pi++ ← the kth element of N ; 4 Remove the kth element of N ;
ization of Algorithm 6.4 and reflects the composition of N as the sections to load
combined with the blank spaces to build a representation of the entire address space.
Figure 6.1b shows a small modification to FYS. The algorithm that this represents
will be denoted FYS’. FYS’ is the first step towards showing that Algorithm 6.3 is
equivalent to FYS. Lemma 2 states that FYS’ is still uniformly random. The simple
proof is included.
Lemma 2. The algorithm (FYS’) that differs from FYS by iteratively choosing a
“place in line” for each member in N instead of iteratively choosing a random member
of N to place “next in line” produces variants uniformly at random.
Proof. In each of FYS and FYS’, a particular sequence of random numbers chosen
during the algorithm corresponds to a single and unique permutation of the address
space. Because the method of choosing random numbers is the same between algo-
rithms, the probability of a given sequence of random numbers is the same in each.
If the probability of any two variants is equal in FYS, then the probability of any
two sequences of random numbers is equal. If the probability of any two sequences
of random numbers is equal in FYS, then the probability of any two sequences of
random numbers is the same in FYS’. Finally, if the probability of any two sequences
of random numbers is equal, then the probability of any two variants resulting from
FYS’ is equal. Therefore, FYS’ produces program variants with uniform and evenly
distributed probability. �
98
i = 1 i = 2 i = 9...
...
...
pick for slot 1 pick for slot 2 pick for slot 9
(a) Representation of the Fisher- Yates Shuffle
i = 1 i = 2 i = 9...
...
...
place section 1 place section 2 place section 9
(b) FYS’; Modification of the Fisher- Yates Shuffle
Figure 6.1: The original Fisher-Yates Shuffle and an equivalent but slightly modified FYS’. Each produces permutations uniformly at random. FYS’ is a step on the path to transform Algorithm 6.3 into FYS.
Note that with the input given to the FYS’ algorithm, some of the steps that
it took were unnecessary. Because each of the “empty space” inputs is identical,
all possible placements of these units results in an identical address space if the
placements of the first sections is fixed. Therefore, assuming that all slots are empty
and then running the algorithm for just S produces an identical result as running the
algorithm with N (S and the empty spaces).
This transformation arrives at Algorithm 6.3 while maintaining the FYS property
of producing variants uniformly at random at each step. Therefore, Algorithm 6.3
produces variants uniformly at random.
Finally, note that running the algorithm twice (for kernel-space and then for user-
space) maintains the uniformly at random property. The order of the input sections
does not matter, and running the algorithm twice is really equivalent to just pausing
to do some other work between loading the kernel sections and loading the user
sections. However, no other work changes the conditions required for the algorithm.
Since doing the algorithm twice can be reduced to doing it just once with different
input, the sequence of doing it twice maintains the uniformly random properties that
were proven for running the algorithm once.
99
6.2 Überdiversity: Implementation
The Überdiversity prototype was implemented on Bear [123], a Minix-like research
microkernel with an integrated hypervisor that supports full 64-bit multicore Intel
hardware. While fully featured, the kernel and hypervisor are less than 10,000 lines
of code, with extensive sharing between the components.
This chapter provides references to resources describing the different components
of the implementation and adds a discussion of the details specific to the prototype.
6.2.1 ELF & the Diversity Loader
The compiler stores a program’s code, data, and metadata in the ELF [39] format. In
order to maximize the impact of load-time diversification, the compiler should take
care to split the code into as many separate ELF sections as possible4. The ELF
ABI and the associated loading process is well documented [104]. Adding support for
diversification requires three additional steps. First, sections are loaded at randomly
chosen addresses rather than those specified in the ELF file. After loading each section
into a random virtual address, the diversity loader calls two routines per loadable unit:
move unit and fixup unit.
The move unit function updates the global symbol table loaded from the ELF
metadata to reflect the new addresses of each section. It also updates internal relo-
cation entries associated with the unit. These are places in a particular section that
reference an absolute address within the same section.
After all units have had their symbols and relocations updated with their new
randomized values, fixup unit is called for each of the units. This routine resolves
external relocations for the unit. In other words, after all of the symbols have been
updated, each unit finds the updated value of the symbols it needs to resolve.
4In GCC, this is accomplished with the -ffunction-sections option
100
Random numbers are notoriously difficult for computers to generate. Sources of
randomness are out of scope for this work, but there are many published research
efforts examining how to obtain random numbers from a computer [136]. The pro-
totype uses the x86 hardware random number generator, accessed using the rdrand
instruction. Despite some controversy about closed-source manufacturer provided
hardware random number generators [124], this is sufficient for the proof of concept
prototype.
6.2.2 The Virtual Memory Abstraction
The page tables [79] used by the MMU on the 64-bit x86 architecture are four levels
deep. Each level contains protection bits used to moderate software’s access to the
memory mapped below that particular entry. These include a U/S bit to differentiate
between user mode and supervisor mode access, a R/W bit to control read or write
access, and an NX bit to control execution privilege, among others.
Despite the fact that these permissions are present at each level of the page tables,
the protection bits at higher levels are not used in the prototype. An NX bit set in the
top level table marks every virtual address decomposed through that particular entry
as non-executable. With the maximum degree of randomization, however, there are
likely to be multiple sections of different permissions interleaved within a single high-
level table entry. In order to maximize the possible entropy achieved at load-time,
permissions are enforced at the smallest possible granularity. For this reason, higher
level table entries are always set with the most liberal permissions possible. The
permissions required for a given section are set only in the final table entry. A small
performance improvement is possible by marking higher-level tables that happen to
contain only sections of a given type, but the prototype does not implement this case.
The entropy that can be achieved by the diversity loader has an upper bound
defined by the amount of virtual memory space into which a given section can be
101
loaded. In the case of the current x86 64-bit implementation, there are 48 bits of
addressable virtual address space. This corresponds to the capability to virtually ad-
dress 256 TB of memory. There is an architectural definition that, until the full 64-bit
address width is implemented on the memory bus, the address must be sign extended.
This creates a region of addresses that are illegal to access, called noncanonical ad-
dresses. The current 48-bit implementation of x86 does not allow addresses between
0x7FFFFFFFFFFF and 0xFFFF800000000000.
The fact that the virtual address space is so large allows for the large degree
of entropy that can be achieved by harnessing the entire available virtual address
space for loading sections. Recall that the flexibility of the algorithm described in
Section 6.1 makes avoiding the noncanonical address range while still utilizing the
entirety of the virtual address space trivial.
Interleaving kernel- and user-space sections raises concerns about the accessibility
of kernel memory by unprivileged user processes. For instance, if the user stack is
loaded directly adjacent to some kernel code, one might worry about a stack overflow
attack to overwrite kernel code. The hardware memory management unit (MMU)
mitigates this risk with hardware protections stored in the page tables. If the kernel
code is loaded with the supervisor bit set in the page tables, any user process will
fault trying to read or write that memory. Unfortunately, the page table protections
are set and enforced only in PAGE SIZE5 intervals. This has important implications
for the implementation of the algorithm: no two sections with differing permissions
can share a page. The stricter rule that no two sections of any type can share
a page simplifies the implementation. This rule is enforced by making sure that
addresses on any page that a section is loaded onto are marked as unusable during
Algorithm 6.3. So, removing addresses from the pool of eligible addresses is done
in PAGE SIZE increments. Note that this rule does not mean that the address of a
5The typical value of PAGE SIZE on the x86 architecture is 4 KB
102
loaded section must be on a page boundary.
6.2.3 Diversifying the Entire Software Stack
The idea of diversity was first applied to user-space programs. Running on top of the
operating system means that there is a powerful program (the kernel) used to load
user-space code, with arbitrary complexity.
Kernel code randomization (KASLR) was the natural next step. Some KASLR
implementations use the normal kernel boot loader to provide the randomization
functions [54] while others use a hypervisor to load the kernel [86]. The prototype
uses the former method. A first-stage bootloader (boot1) manages the processor
configuration needed to enter 64-bit mode at which point a second-stage bootloader
(boot2) performs the randomized loading of the kernel.
A fully general diversity loader implementation in boot2 allows for the additional
accomplishment of randomizing a hypervisor that is loaded with the bootloader. The
hypervisor is diversified in its own address space. While the kernel- and user-spaces
share an address space, the hypervisor is not mapped in to any set of page tables used
in the kernel. Its own unique set of page tables makes it a completely separate unit
from the kernel- and user-space. However, there are still huge security implications
to having the hypervisor be loaded non-deterministically. As security technologies
improve, attacks on systems are being launched at layers closer and closer to the
hardware [61]. The conventional paradigm used to relate the hypervisor to the op-
erating system suggests that hypervisors will soon be subjected to the attacks that
motivate KASLR [141].
The result of this particular software decomposition and the flexibility of the di-
versity algorithm is a system in which every layer of the software is loaded randomly
into the available virtual memory space. This includes the hypervisor, the operat-
ing system, and the user process. Furthermore, the user process and kernel that
103
share a virtual address space are randomized together, rather than being randomized
individually in disjoint virtual memory regions.
6.3 Überdiversity: Evaluation and Analysis
6.3.1 Quantification of Diversity Achieved
There are two different ways to quantify the “amount of randomness” (more practi-
cally: “difficulty to brute-force”) that a particular diversity implementation achieves.
The first, entropy, is a familiar notion discussed in many previous papers about di-
versity [19,36,128,149,157]. The second, program variants, is a separate notion that
is sometimes confused with entropy, as in [50]. The difference between these two
measurements will be clarified, and the number of program variants possible from a
single source binary will be counted.
Entropy, the common way to measure a diversity implementation, quantifies the
search space for a particular resource. If a particular function is loaded with n bits of
entropy, then its address is one of 2n choices. Commodity 64-bit hardware imposes a
48 bit limit on entropy since it only implements 248 virtual addresses.
Program variants, on the other hand, describes how many unique layouts can be
generated within an address space with a given program as input. A single program
variant is defined by the union of the locations of all instructions and data loaded
into memory.
In order to illustrate the difference between entropy and program variants, con-
sider the effect of randomizing instructions within a function at compile-time. This
transformation does not increase the entropy beyond simply loading the ordered func-
tion at a random location in memory, since the search space for an instruction is the
same regardless of its location relative to its parent function. However, it does increase
the number of program variants possible.
104
The practical question of which of these is a more important measurement for
estimating the difficulty of brute-forcing a diversity implementation is a challenging
one that depends on the goal of the attacker. If the attacker needs to find one single
program resource (such as a particular dangerous function), entropy is the more
important measure since it describes the amount of randomness in the address of
that function. If the attacker needs to find a series of program resources (such as
gadgets for a ROP payload), program variants is the more important measure since it
helps describe how learning one location narrows the search space for other locations.
Indeed, a complete model for estimating the probability of success of an attacker
depends on these variables and many more. However, even in the absence of a fully
developed model, both program variants and entropy are important for a reasonable
estimate of the potency of a given randomization technique.
Entropy
Entropy is a convenient way to measure the potency and flexibility of a diversification
scheme, but it is important to recognize its limitations. A measure of entropy is
not necessarily a good measure of security. As pointed out in [100], an interesting
instruction loaded with infinite entropy into an infinite address space is still insecure
if all other instructions are nop. In this example, executing the nop instruction
at address 0 guarantees execution of the interesting instruction as the many nop
instructions preceding the interesting instruction will be executed with no effect until
the interesting function is found.
A discussion of the entropy of the prototype will continue with the limitations of
entropy as a quantification for diversity in mind. The prototype is implemented with
sufficient flexibility to take advantage of the entirety of the x86 48-bit address space,
with only some exceptions.
Some of the address space is unused at the top level. In particular, two entries
105
are reserved in the top level of the page table structure. The 511th entry is used for
a self-referential pointer used to provide virtual mappings to paging structures [110].
The 0th entry is unused out of convenience; the bootloader must be loaded into low
memory so the low memory region is reserved to avoid conflicts with boot code.
There are other complications to using low memory such as the memmap and RAMDISK,
structures loaded into low memory by the bios during boot that are used throughout
the lifetime of the kernel. However, most or all of this section could be reclaimed for
use during loading with some care.
Additionally, the least significant address space bits are sometimes unavailable for
loading sections. Each individual section in an ELF binary has an alignment require-
ment [39]. The alignment requirement is reported in the sh addralign member of
each ELF section header. Many section headers report an alignment requirement of 0
or 1, meaning that its section requires no special alignment: all of the least significant
bits of the address can be loaded arbitrarily. However, some sections require 2, 4, 8 or
greater byte-alignment. For any sh addralign greater than 1, log2(sh addralign)
bits of the address must be held at zero in order to conform to the ELF standard.
However, all remaining low-level bits can be randomized. Unlike some prior work,
the prototype can load sections off of page boundaries.
The inability to use the 511th and 0th entries in the top level of the page table
structures does not cut the available addresses in half, so it does not cost a full bit of
entropy. However, it does cost some fraction of a bit. Therefore, worst-case upper and
lower6 bounds on Überdiversity’s load-time entropy are 47 and 43 bits, respectively.
Program Variants
One way to measure the diversity of a system is in terms of the number of program
variants that can be generated from a given binary. The set of all possible program
6The lower bound is reported for a worst-case sh addralign of 8 bytes. This is typical for the largest alignment requirement in an ELF binary.
106
variants is the search space for an attacker that wants to learn the layout of the
address space by brute-force guessing. The larger that search space is, the greater the
workload of the attacker. Similar to entropy, this measurement does have limitations.
Many unique instances of a program will have a particularly interesting resource
located in the exact same location. It is an open research question how likely this is
to assist the attacker in practice.
The question of how many program variants are possible is a combinatorics prob-
lem that can be visualized using the common “stars and bars” method [60].
First, assume that for a best-case scenario, all sections s ∈ S require only 1-byte
alignment. Note that S = Su ∪ Sk; the sections to be loaded are both the user- and
kernel-space sections. Also assume that the hardware enforces protections at a single
byte granularity. These assumptions provide the situation for an upper bound on the
number of variants.
Since ∑
s∈S s.size is known, the total amount of virtual memory that will be unused
after the program is loaded is known. If the amount of virtual memory eligible to be
used for loading is |A|, there will be |A| − ∑
s∈S s.size unused bytes after all sections
are loaded. Each of these unused bytes will lie in a region between two sections or a
section and a virtual memory barrier. In other words, the sections can be considered
dividers that break the unused bytes up into |S|+1 “bins” or “buckets”. Each possible
assignment of unused bytes to bins describes a possible program image.
Counting the ways to place unused bytes into |S| + 1 bins is accomplished using
the following visualization. Imagine each of the |A| − ∑
s∈S s.size unused bytes is
a “star”. If |S| stars are transformed into “bars” (sections, in this case) then the
remaining A− ∑
s∈S s.size− |S| stars are divided into |S|+ 1 buckets. However, for
this system to represent the diversity loading problem, A− ∑
s∈S s.size stars must be
divided into the |S|+1 bins. Starting with |S|+A− ∑
s∈S s.size stars and picking |S|
at random to represent sections instead of unused bytes accomplishes this. Choosing
107
k objects from a set of n is an elementary combinatorial problem. Therefore, an
upper bound on the number of variants that can be produced from a given program
is shown in Equation 6.2.
( |S|+ A−
∑ s∈S
s.size
) !(
A− ∑ s∈S
s.size
) !
(6.2)
Unfortunately, alignment requirements and coarsely grained MMU protection
mechanisms mean that this upper bound is not reached. To capture a better idea
of the actual number of variants possible, some adjustments can more accurately
represent the problem. First, the MMU provides memory protections only at the
granularity of PAGE SIZE chunks. So, the memory consumed by a section will be
in units of page size. For the lower bound, a safe assumption is that each section
consumes the maximum possible amount of memory. This is ⌈
s.size PAGE SIZE
⌉ + 1. Adding
the extra page is just in case the section is loaded across a page boundary. This lower
bound is expressed in Equation 6.3.
( |S|+ A
PAGE SIZE − ∑ s∈S
(⌈ s.size
PAGE SIZE
⌉ + 1 ))
!( A
PAGE SIZE − ∑ s∈S
(⌈ s.size
PAGE SIZE
⌉ + 1 ))
! (6.3)
The lower bound does not achieve the true value because it assumes that sections
are eligible to be loaded only at page boundaries and that sections are loaded such
that each will cross over a page boundary, consuming an extra page. This is a con-
tradiction, but that is acceptable for a lower bound. A tighter lower bound examines
where a section will be loaded within the memory it can consume. In other words,
108
multiplying the original lower bound by the number of places within the memory
footprint consumed by a section that the section can be loaded. This bound is shown
in Equation 6.4.
( |S|+ A
PAGE SIZE − ∑ s∈S
(⌈ s.size
PAGE SIZE
⌉ + 1 ))
!( A
PAGE SIZE − ∑ s∈S
(⌈ s.size
PAGE SIZE
⌉ + 1 ))
!
× ∏ s∈S
((⌈ s.size
PAGE SIZE
⌉ + 1 ) × PAGE SIZE
) − s.size
s.alignment (6.4)
Equation 6.4 is a close lower bound. There is one thing that keeps it from being
an exact calculation: the equation assumes that every possible position to which a
section could be loaded would consume the maximum possible amount of memory
for that section. However, in truth only a small subsection of the eligible addresses
cause a section to consume ⌈
s.size PAGE SIZE
⌉ +1 pages. Most consume only
⌈ s.size
PAGE SIZE
⌉ pages.
Finding an exact value by including this in the calculation is beyond the scope of this
work.
The upper and lower bounds for a typical program loaded using the prototype
implementation can be calculated. The shell is the example program to calculate
sample values. On the system, A ≈ 255TB, |Su| ≈ 143, and |Sk| ≈ 444. Furthermore,∑ s∈Su
s.size ≈ 800MB7 and ∑
s∈Sk s.size ≈ 80MB. This gives an upper bound of
≈ 108440 unique address space layouts for a typical program and a lower bound of
≈ 108205.
These numbers do not include the number of variants produced by any compile-
time randomization techniques that are used; including these effects effects will greatly
7The quantity ∑
s∈Su s.size is dominated by the user-space heap which is allocated with a size
of several hundred MB in order to accommodate memory-intensive applications. Although the heap is allocated on demand as the user process requests it, a maximum size is assigned at load-time to guarantee that the heap has sufficient room to grow.
109
Fork/Exec Test CPU Cycles×109
No Diversity Max 5.2296 Min 4.8050 Avg 4.9768
Überdiversity Max 36.4030 Min 35.5999 Avg 35.9565
Average Performance Cost 7.2×
Table 6.1: This test demonstrates 50 Trials of fork and exec with and without Überdiversity.
increase the number of possible program variants. This shows that, at its limit,
diversification of software can generate a virtual address layout search space that will
overwhelm and defeat brute-force attacks.
6.3.2 Performance Cost
The performance cost of this method of diversity is spent partially at run- and par-
tially at load-time. At load-time, there is added work from running the diversity
algorithm. At run-time, the source is slightly more subtle. Consider a series of very
small functions; without load-time diversity, these are likely to all be located on a
single page of memory. This means that a single translation lookaside buffer (TLB)
entry or cache page will cache all of these functions. With load-time diversity, how-
ever, a TLB entry and cache page will be required for each of these functions. More
importantly, there will be a cache miss the first time each of these functions is exe-
cuted compared to the non-diversified case in which only the first time any of these
functions is executed results in a cache miss.
The load-time costs of the prototype are summarized in Table 6.1. This table
measures the time spent to create and transform a process using fork and exec. The
average case did show a high cost of 7.2×. Fortunately, this cost is incurred only once
in the lifetime of the process and therefore overall throughput is not heavily affected.
In contrast, run-time performance overhead can pose a real threat to overall system
110
0
100
200
300
400
P er
fo rm
an ce
C os
t (%
)
200 400 600 800 0
0.5
1
1.5
2 ·109
1000
Nested Function Depth
C P
U C
y cl
es No Diversity
Überdiversity Performance Cost
Figure 6.2: Performance Benchmarks for Nested Functions. This test illustrates that loading functions onto unique discontinuous pages instead of loading them contigu- ously can lead to cache exhaustion in extreme use cases.
throughput. Caching plays a huge role in offering the performance necessary to
make modern systems useable, and fine-grained randomization threatens that entire
subsystem. Figure 6.2 explores a worst-case scenario. In particular, it shows how the
performance cost increases with nested subroutine depth as the caching capabilities of
the hardware begin to be overwhelmed by the number of entries required for effective
caching. The tests used to generate the data for this figure simply called nested
subroutines until the function at the desired depth returned a value. Performance
costs as high as 400% are a testament to just how important caching is, and how it
can be disrupted by fine-grained randomization.
Although the experimental status of the platform for the prototype limits the type
of applications that can be measured, Table 6.2 illustrates measured performance
111
Test (CPU Cycles ×1010) Multiply Add Divide malloc
No Diversity Max 2.2619 1.3811 10.937 2.9638 Min 2.2394 1.3512 10.830 2.9563 Avg 2.2432 1.3631 10.851 2.9596
Überdiversity Max 2.2647 1.8987 11.037 4.2529 Min 2.2388 1.3307 10.373 3.0115 Avg 2.2464 1.3674 10.629 3.1393
Average Performance Cost 0.14% 0.32% -2% 6%
Table 6.2: AIM9 Benchmark Suite [6] and Malloc Test [103] Performance Measure- ments - 50 Trials per test
costs on industry standard benchmarking utilities. The AIM9 Tests [6] demonstrate
that, despite the high costs seen in Figure 6.2, code diversity has no meaningful
performance cost on code execution within a function after load time. The malloc
test [103] does show some performance due to the cache misses from malloc and all of
its subroutines. Importantly, however, even though this test uses many subroutines
in the C standard library, only a 6% performance cost was measured. This suggests
that many applications follow the anecdote that “software spends 90% of its time in
10% of its code,” and therefore that a very advanced level of randomization can be
deployed with acceptable performance cost.
Finally, there is some memory overhead associated with using such a fine-grained
randomization scheme. The code itself will have a larger memory footprint because
memory is consumed in increments of PAGE SIZE, but each function is loaded in
isolation from the others. Therefore, two functions that fit together on one page will
now consume 2 pages. Additionally, more memory is used to generate the higher-level
paging structures that provide the mappings to randomized, non-localized addresses.
Figure 6.3 demonstrates the worst-case of this cost is between 10× and 15×. This cost
may be prohibitive for some applications or low-memory systems, but the amount of
memory on state of the art systems is typically more than sufficient to accommodate
this overhead for average workloads.
Furthermore, techniques used to decrease some of these performance and memory
112
10
12
14
16
18
W or
st -C
as e
M em
or y
O ve
rh ea
d (×
)
200 400 600 800 0
1,000
2,000
3,000
1000
Number of Sections Loaded
P ag
es C
on su
m ed
No Diversity
Überdiversity Memory Overhead
Figure 6.3: Worst-Case Memory Overhead Analysis. This analysis assumes that sections are 1
4 the size of a page, and that the random locations are chosen in the
most memory-heavy way possible.
113
overheads are explored in [163]. This work explores optimizations such as bundling
leaf functions with their callers to minimize an extra cache miss in a case where
security is unlikely to be decreased. These same techniques could be applied in a
64-bit environment.
6.3.3 Security Implications
As traditional ASLR has become ubiquitous in many commodity operating systems,
attackers have developed a multitude of ways to bypass its protections. The various
classical methods of exploiting programs despite ASLR are presented in the ASLR
Smack and Laugh Reference (ASLRSLR) [122]. A selection of these methods below
contain discussions of how Überdiversity influences their efficacy.
Aggression. The first and most obvious threat listed in ASLRSLR is a brute-
force attack in which an attacker gains access to a vulnerable pointer that has been
randomized by repeatedly guessing. For example, [149] shows that a system with
only 24 bits of entropy can be brute-forced in a matter of minutes. Although [128]
reported being able to brute-force a 64-bit ASLR implementation in as little as 1
hour, the ASLR implementation used was only 28 bits. As discussed in Section 6.3.1,
the prototype achieves at least 43 bits of entropy. With 43 bits, a brute-force attack
would take months8. This means that any attempted brute-force attack will be easily
detected before it succeeds.
Return into Non-Randomized Memory Regions. In some ASLR implemen-
tations, there are some sections that are not randomized. Ways to exploit each of
the text, heap, bss, and data sections when they are not randomized are detailed in
ASLRSLR. Fortunately, the prototype successfully randomizes the location of every
memory region. The ELF maintained relocation tables allow fixing pointers to data
8Estimated. Experimental results from [149] and [128] say that 24 bits requires 4 minutes to brute- force, and 28 bits requires an hour. This conforms to intuition, as 4 min× 2(28−24) = 64min ≈ 1 hr. The same calculation for 43 bits gives 4 min× 2(43−24) = 524288 min ≈ 1 yr.
114
in the bss/data section and to functions to reflect the newly randomized locations.
The user-space malloc implementation learns the location of the randomized heap by
making a system call to request the address. Similarly, the kernel locates its heap at
run-time by referencing data passed on by the bootloader.
Information Leakage Attack. Direct or indirect memory disclosures can de-
feat address space randomization by divulging address space layout information at
run-time, enabling unique attack vectors [151]. Many methods such as execute-only
code [15,26,43,68] aim to limit the risk of memory disclosure. Most of these techniques
are compatible with Überdiversity.
Furthermore, fine-grained compile-time diversity should be used to reduce the
amount of usable information that an attacker gains from any memory disclosure.
Compile-time diversification should introduce randomness within an ELF section,
denying the ability to make assumptions about the location of gadgets within a given
ELF section by reading a single address off of the stack. Research efforts examining
the necessary type of compile-time randomization are plentiful [76,81,82,86,93], and
most are be compatible with load-time diversification techniques.
New information leakage techniques include side channel attacks, including meth-
ods developed specifically for defeating ASLR [77]. However, the authors of [77] state
explicitly that “by utilizing the complete memory range and distributing all loaded
modules to different places, it would be much harder to perform our attacks.” This is
exactly the method that Überdiversity uses, meaning that its high entropy provides
a native level of protection against these types of attacks.
Return-Oriented Programming. Return-oriented programming (ROP) [140]
is a method that uses small bits of code known as “gadgets”, each of which is a
short sequence of instructions followed by a return. A carefully crafted stack can
direct control flow through these gadgets in a particular order to preform arbitrary
computation.
115
Traditional ASLR disturbs ROP by making it more difficult to locate gadgets.
However, an attacker needs to find only one address range in order to locate all of
the possible gadgets. The prototype makes it even more difficult by putting each
function, and therefore all potential gadgets, into unique random address ranges.
... and beyond In the time since the publication of ASLRSLR, several attacks
against ASLR have been published. Some, such as [126], rely on the relatively pre-
dictable layout of the address space and are therefore defeated by using fine-grained
randomization such as that explored in Überdiversity. However, some state of the
art techniques such as BROP [21] manage to defeat even fine-grained randomization
without access to the compiled and loaded code. This powerful technique threatens
otherwise secure randomization schemes, including Überdiversity, but requires some
particular properties of a system. The authors state that “the most basic protection
against the BROP attack is to rerandomize canaries and ASLR as often as possible,”
because they rely on a restart property to guarantee that their addresses of interest do
not change upon a process crash. Although Überdiversity currently randomizes only
during a call to exec, as they point out is typical of randomization techniques, it is
possible that it could randomize during fork as well. The challenges of implementing
a system to re-randomize code on a fork is discussed in the context of per-process
kernel layout randomization in [28].
6.4 Überdiversity: Conclusion
Diversity is a well-established technique for decreasing the risk of vulnerability am-
plification and increasing attacker workload in networked systems. Although many
different techniques for injecting randomness into computer memory layouts have
been presented, none have yet approached the limits of 64-bit hardware. Further-
more, most do not discuss the method used to randomize the memory layout, and
116
many confuse entropy with program variants while attempting to quantify their ef-
fort. This study presented Überdiversity, an ELF diversity loader that randomizes
fine-grained memory regions while loading them into memory.
A study of related work reveals that an important detail in any randomization
technique, the algorithm used to produce permuted address spaces, is rarely men-
tioned, much less thoroughly examined. The study presented the algorithm used for
Überdiversity and proved that it produces address space layouts uniformly at ran-
dom, a property that is necessary for any randomization technique to be deployed
most effectively. Additionally, previous research efforts are inconsistent in the use of
“entropy” to quantify the effectiveness of a diversification tool. To address this, care is
taken to separate the measure of entropy from that of program variants; both provide
valuable but different ways to estimate the potency of a diversity implementation.
Überdiversity makes several improvements over the current state of the art. Firstly,
it manages to make use of a large majority of the available virtual memory, deliver-
ing an unprecedented 43-47 bits of entropy. Including the diversity loader into the
system’s bootloader enables the random loading of the hypervisor and the operat-
ing system kernel in addition to the more common randomization of user processes.
Furthermore, the kernel and the user process are randomized together, producing an
address space where kernel- and user-sections are non-deterministically interleaved.
The flexible x86 virtual memory abstraction maintains appropriate protections de-
spite having discontiguous kernel- and user-space virtual memory regions.
The prototype revealed high costs (7.2×) at load-time but, despite clear evidence
of an extremely slow worst-case scenario, only moderate costs in the average case
at run-time (less than 10%). This suggests that mainstream ASLR implementations
could use more thorough and fine-grained randomization techniques on an average
application, even approaching the hardware-imposed limits, without suffering unrea-
sonable performance costs.
117
Chapter 7
KUCS
The fundamental role of an operating system is to provide an appropriate context for
process execution, multiplex processes’ access to the hardware, and protect processes
from each another. The current state of the art operating system architecture, as
partially described in Chapter 2, is the product of many seminal [20, 40, 47, 145,
146, 158] and hundreds of subsequent research efforts and accomplishes all of these
tasks. Current systems provide each application with a virtual address space in which
the kernel manages the required context. The kernel provides the application with
functionality for manipulating hardware by including its own code in the virtual
address space of each process1. In order to protect processes from one another, the
kernel does not share virtual address spaces between applications and it restricts
access to the shared kernel functionality using hardware-provided CPU privilege levels.
Unfortunately, some characteristics of the current kernel design lead to security
and performance issues. For example, the popular return-to-user (ret2usr) style at-
tack [93] is enabled by sharing the virtual address space between the kernel and the
application, despite the CPU privilege levels.
The current relationship between the operating system and a user application is
1The few examples of systems that use “strong” rather than “weak” separation between kernel memory and user memory include the 4G/4G split Linux patch [118], 32-bit XNU [94], and certain systems using the hardware facilities provided by SPARC V9 hardware [115]
118
largely a historical artifact. In the early days of computing, with just one process-
ing unit, only one program could run at any given time. There needed to be a way
to pass control from one program to another (in this case, from the application to
the kernel), and some notion of differing privileges between the two programs. To
accomplish the first task, system designers simply included both “programs” in a
single computing context. For the second, the hardware provided the privilege mode
switch triggered by an interrupt (an INT instruction on x86). When the processor
reached this instruction, it would save the state of the current operating context to
a known location, change the CPU’s privilege mode, and direct execution to a pre-
defined kernel entrance routine. Later, when the kernel wanted to resume execution
of the application, it would issue a special return (IRET on x86), at which point the
hardware would demote privilege and transfer execution to a kernel-defined location
in the application’s code. More recently, the x86 architecture defined SYSENTER and
SYSEXIT as alternatives to INT and IRET for the system call (syscall) interface, but
the underlying mechanism has not changed.
With the advent of multicore processors, the need to share hardware no longer
forced this design onto kernel developers. However, since each core still provided
the functionality of the unicore processor, it became standard practice to take the
established kernel implementation formula and replicate it, instantiating one kernel
and user instance per core. The only special care needed was that no two cores
would execute the same code at the same time. Originally, this was accomplished
using a single “kernel lock,” a software mechanism that restricted access to the kernel
to only one processor at a time [107]. More recently, many kernels have narrowed
the granularity of their locked paths so that two or more fully independent paths
through the kernel may be used simultaneously by two or more different cores [155].
Overall, this scheme of employing a single mechanism on each available core is known
as Symmetric MultiProcessing (SMP).
119
The decision to replicate the unicore operating system design onto each core in
multicore hardware may have imposed unnecessary limits on the security and per-
formance attainable on modern systems. This chapter discusses an effort to revisit
that decision and explain how to replace the unicore operating system design with
one that leverages modern multicore hardware to address some of the weaknesses
found in modern designs. The resulting design is called Kernel and User Core-Based
Separation (KUCS). KUCS’ unique utilization of hardware resources fundamentally
changes how systems provide security to their different components. While micro-
kernels redistribute system components to increase the security offered by monolithic
kernels, they do so using the exact same hardware abstractions to differentiate user-
and kernel-space. In contrast, KUCS changes the underlying hardware abstractions
used for coordination and translation between different components of the system,
although any current kernel, whether monolithic or micro, could be implemented
using KUCS. Even cutting edge virtualization-based security efforts use the same
hardware design patterns that operating systems have been using for years [141]. As
argued in [25] this “turtles all the way down” approach to security is not sufficient.
In KUCS, virtualization is used as a tool for the kernel to protect itself, rather than
as an abstraction that replicates the classic kernel design paradigm in a new software
layer.
KUCS explores the idea of using Asymmetric MultiProcessing (ASMP) on mod-
ern x86 hardware. Unlike the prior ASMP efforts described in Section 3.4, the KUCS
design aims explicitly to divorce the virtual address space of the application from that
of the kernel. The distinct, decoupled operating environments provided on each pro-
cessor allow for the kernel and the application to use completely different hardware
resources, rather than sharing a common processor core. Inter-Processor Interrupts
(IPIs) will take the role of the standard INT/SYSENTER and IRET/SYSEXIT function-
ality for system calls. The application and the kernel will no longer share hardware,
120
so the hardware-provided CPU privilege mode switch is not needed, and neither pro-
gram has to relinquish its own resources to message or signal the other. Additionally,
virtualization will be utilized to implement fine-grained security rules on a per-core
basis to further police the software.
This paradigm shift interrupts commonly deployed privilege escalation mecha-
nisms by defining privilege as a physical location on-chip rather than a traditional
processor mode. As a result, more advanced virtualization-based defenses can be
employed because each core is responsible for either the kernel or an application –
never both. Additionally, the fact that the kernel and the application do not share
hardware resources means that they can operate simultaneously. This creates oppor-
tunities for techniques such as using the kernel to perform watchdog state checks on
applications while they run an application utilizing truly asynchronous system calls
by signaling the kernel but continuing to run while the kernel services its request.
Utilizing these techniques in a KUCS operating system will deliver strong separation
between the kernel and an application, fast IPI-based control transfers and messag-
ing, advanced virtualization-based and application-specific security features, and new
opportunities such as asynchronous system calls, kernel-based watchdog processes,
and application-specific hardware-secured subcontexts.
7.1 KUCS: Overview
This section presents an overview of the Kernel and User Core-Based Separation
(KUCS) operating system design. The content of this chapter is based largely on the
design that was proposed in NSPW ’16 [31], which presents a new security paradigm
in operating system design. The implementation details discussed later in this chap-
ter reference this design, but certain features of the design are not present in the
KUCSBear prototype. This is discussed in more detail in the next section.
121
Kernel User Process User Process
IPI
IPI
IPIs
Core 0 Core 1 Core N
Allow HLT instructions? Allow device interrupts?
✓ ✓
Ring -1 (VMM)
Ring 0
Allow HLT instructions? Allow device interrupts?
✗ ✓
(e.g. Network Driver)
Allow HLT instructions? Allow device interrupts?
✗ ✗
Hardware-Enforced Privilege Mode Boundary
INT/SYSENTER
IRET/SYSEXIT
Ring 3
Application-Speci�c Secure Context
(e.g. Web Browser)
Figure 7.1: Operating system design using KUCS. CPU privilege level (ring) 0, tra- ditionally used for the kernel context, contains the main code for each core: either the kernel or a user processes. The virtualization layer, commonly referred to as ring -1, protects the hardware from user processes. With ring 3 no longer being used by the system, individual applications can use the hardware to provide their own secure sub-contexts.
Figure 7.1 illustrates an overview of the KUCS design. Core number, rather
than the traditional CPU privilege level (ring), differentiates kernel- from user-space.
Core-specific security rules in the virtualization layer and virtual memory isolation
for ring 0 processes recover the protection offered by the traditional ring 3 user-space.
Interprocessor interrupts provide a mechanism for implementing system calls across
cores. With ring 3 no longer used for isolating user-space, the application can use the
hardware protection associated with ring 3 to provide its own secure sub-contexts.
This section explores the features of a KUCS design in detail. The main factors
contributing to increased security are divorcing kernel- and user-space, utilizing user-
space drivers and deploying fine-grained per-core virtualization-based security poli-
cies. The potential for an increase in performance will come from fast mechanisms for
signaling from an application to the kernel, less overhead in driver implementations,
and more efficient parallelization of computation.
122
7.1.1 Separating Kernel and User Cores
The primary characteristic of the KUCS design is that the kernel and the user appli-
cation do not share a virtual address space and are each executed at ring 0, but on
independent cores. This arrangement will have several implications on the security
of the system.
Ring 3 (and more) Protection in Ring 0
The weak separation between kernel- and user-space in traditional operating system
design allows for even the most strictly “sandboxed” processes to be used as a stepping
stone for compromising the whole system because privilege escalation compromises
the kernel. Since the kernel needs to manage all of system memory, it maintains
virtual mappings to all memory; a process that shares its virtual address space with
the kernel can perform arbitrary reads and writes with sufficient privilege escalation.
When not shared with the kernel, the application’s virtual address space does not
need to contain mappings to all of system memory. Consequently, the application
cannot inspect or modify memory unless the kernel has given it access, even with
arbitrarily high privilege. Naively, this means that the application can safely be run
in ring 0. However, additional steps are required to recreate the full protections
offered by ring 3 while running in ring 0.
In ring 0, the process is a supervisor on-core and can read from or write to any
memory mapped into its address space. In order to stop a process from modifying
its page tables to create mappings for arbitrary system memory, virtual mappings to
the application’s page tables will be omitted from the application’s virtual address
space. In order to modify its own page tables, the page tables need to contain a
virtual mapping to themselves; without it, the application cannot modify the memory
used by the memory management unit to define its own virtual address space. This
ensures that the process is permanently and completely isolated in virtual memory
123
and enables the process’ page tables to deny access to memory-mapped devices.
The virtualization layer also helps to recreate ring 3 protection by denying inappro-
priate hardware accesses like reading from and writing to processor control registers
or executing typically privileged instructions. The end result is an application exe-
cution context with the same protections offered by ring 3, but without the crown
jewels of the system hiding behind a CPU privilege level bit.
Hardware Control from Applications
User-space drivers [72] minimize the amount of potentially third party and frequently
buggy [37, 66, 129] code that runs with privilege. Unfortunately, this comes at a sig-
nificant performance cost. Device drivers need to interact with hardware, for which
they need privilege that they do not have in ring 3. Therefore, they must frequently
interact with the kernel to accomplish their tasks, significantly degrading perfor-
mance, increasing the kernel’s code base, and widening the interface between user-
and kernel-space.
Although applications can be run in ring 0 with privileges less than or equal to
those of ring 3, security can actually be increased by providing drivers with privileges
greater than those available in ring 3. Setting up the proper operating context for a
driver (as suggested in the virtualization layer on the core being used for a network
driver in Figure 7.1) will allow the driver to be implemented in a single context. This
is an improvement over traditional “user-space” drivers that need the kernel to do
work on their behalf. It keeps the kernel’s code base small and interface narrow.
Application-Specific Secure Contexts
By moving user-space from ring 3 on a shared core to ring 0 on a user-specific core,
there is yet another opportunity to increase security. In particular, ring 3 is no longer
being used by the system. Instead, applications can (with some kernel support) use
124
ring 3 to provide their own secure contexts.
For an example of how this feature might be used, consider a web browser. Al-
though a browser strives to protect web pages from one another and protect itself
from web pages, cross-site scripting [154] is just one example of a common attack
vector in which a single web page can compromise an entire web browser. However,
if the browser is running in ring 0, it could manage individual web pages in ring 3 the
same way that traditional operating systems manage user processes. When the user
opens a new web page, the browser could ask the kernel for a fresh address space that
contains itself in ring 0 and a clean context for the new web page in ring 3. The kernel
needs to handle this task, but the browser could use a local scheduler implementa-
tion (separate from the main scheduler in the kernel) to cycle through these different
contexts without kernel intervention during its own scheduled time quantum.
Watchdog Kernel Processes
In current operating systems, the kernel is invoked strictly when an application needs
work done on its behalf. In other words, the kernel is never running without a specific
task to handle. In contrast, with the asymmetric multiprocessing solution, the kernel
will be running on a dedicated core whether or not it is servicing a specific process’
request. This creates an opportunity: time during which the kernel is executing but
has no specific task to complete. One possible way to utilize this opportunity is to
implement a watchdog routine [44, 112] in the kernel. This routine could monitor
system and application invariants in real time. For example, it could hash a process’
code to check for code patching, monitor the stack looking for ROP payloads, or
profile system components to detect unfamiliar configurations. In the event that an
anomaly is detected, the application can be suspended pending further action.
The watchdog routine in this design is doing its work with CPU cycles that would
otherwise be wasted on the kernel core. These cycles could also be used for other
125
tasks in the interest of either performance or security. One example of the former is
pre-computing values that are likely to be requested by applications in future system
calls. In the case of the latter, the kernel could use these cycles as a third line of
defense (after virtual memory isolation and virtualization) to restrict user processes
being run in ring 0. For example, if the kernel wants the application to alert it in the
event of a processor fault, the watchdog process can verify that the process does not
modify the fault handlers mapped into its context.
7.1.2 Fine-Grained Virtualization
One advantage of the KUCS design is the ability to exercise each core’s virtualization
hardware independently to impose fine-grained security rules on each core based on
the software that that particular core will be executing. ExOShim [26], as described
in Chapter 4 is a thin layer of virtualization underneath the kernel used to mark all
memory associated with kernel code as execute-only using the Extended Page Table
(EPT) functionality provided by modern Intel VT-x hardware [80]. This mitigates
the risk of kernel-level memory disclosures that could facilitate reverse-engineering or
the construction of kernel ROP or JIT-ROP payloads. Additionally, ExOShim does
not accept any inputs or tolerate any permissions violations so that it can provide
this protection for the lifetime of the system, even in the face of kernel compromise.
Figure 4.2 on Page 55 illustrates how the physical frames of memory correspond-
ing to kernel code are marked execute-only in the EPT, denying kernel-level memory
disclosure vulnerabilities. However, all other memory is marked with the most lib-
eral possible permissions in the EPT: read, write, and execute. This is because the
applications running on the processor may need to use this memory. Therefore, the
virtualization layer relies on the kernel to maintain the appropriate memory man-
agement and access control for this memory. Note that this is consistent with most
hypervisors; only the least restrictive security rules can be deployed for the lifetime of
126
a virtual machine. This is an unfortunate byproduct of SMP; the hypervisor cannot
enforce stricter security rules because it cannot predict which core will need which
set of rules.
Unfortunately, the permissive rules applied to this memory allows for the possibil-
ity of a ret2usr [93] or ret2dir [92] style attack. Intuitively, this is because the security
rules that ExOShim applies to the kernel are not complete. It enforces a rule that all
kernel code is execute-only. However, it does not enforce the desirable rule that the
kernel may execute only kernel code. This rule would eliminate the possibility of the
processor executing any non-kernel code with kernel privilege, but the requirement
that application code must be able to utilize this memory from this core denies the
possibility of applying such a strong rule in the virtualization layer. Although Intel’s
Supervisor Mode Execution Prevention (SMEP) [62] feature can address this risk,
SMEP can be disabled in the event of kernel compromise, SMEP bypass techniques
have already been demonstrated [91, 143], and SMEP cannot mitigate the threat of
a ret2dir style attack [92]. For these reasons, this rule would be better implemented
with ExOShim than with SMEP.
In a KUCS operating system, however, the kernel runs on its own core; no ap-
plication code will run on this core. This means that the ret2usr attack is defeated
directly: there is no user-space to return to in the kernel context. Additionally,
the kernel core’s virtualization layer can enforce even stronger security rules than
the ExOShim prototype described in Chapter 4. In addition to marking all mem-
ory corresponding to kernel code as execute-only, it will mark all other memory as
non-executable. This will preserve the protection against memory disclosure vulner-
abilities while also denying ret2dir style attacks by prohibiting the execution of any
non-kernel code from the kernel core.
127
7.1.3 Increasing Performance
The KUCS operating system design offers opportunities to increase system perfor-
mance in ways not possible in a conventional operating system.
Simultaneous Application and Kernel Execution
A KUCS implementation may explore new relationships between the application and
the system call. In particular, the application does not necessarily need to stop ex-
ecution while it makes a syscall. Figure 7.2 contrasts the work that an application
can accomplish with a traditional syscall and with this asynchronous design. It illus-
trates that when the application requests work from the kernel (in this case, setting
an “alarm”) with the traditional interface, it must wait for the kernel to perform the
requested action prior to continuing its work2. In the KUCS design, however, the
application could continue its work immediately because it is not sharing hardware
with the kernel. As a result, the application would be able to complete more work in
a given time quantum.
Note that this truly asynchronous system call interface is only possible if the kernel
is not sharing hardware with the application. As such, many additional research
questions exist before a full implementation of this feature can be realized. For
example, if the kernel fails to perform the requested task, it must alert the process; this
is nontrivial if the process has changed state since the time of the syscall. Additionally,
the process needs a way to know that the kernel is prepared to handle a second
syscall after the first has been dispatched. Despite these unanswered questions, the
possibility for this type of system call mechanism has promising implications for
system performance.
2Note that this is true even in the case of the “asynchronous system calls” [32] used in some current operating systems. These interfaces may provide the capability for the process to work while the kernel is servicing its request, but the process must still relinquish its hardware to the kernel while it is making the request.
128
Time
Application
Kernel
Schedule New
Process
Schedule New
Process
1 2 3 4 alarm
1 2
5 6
(a) With the Traditional Syscall Mechanism
Time
Application
Kernel
Schedule New
Process
Schedule New
Process
1 2 3 4 alarm
1 2
5 6 7 8 9
(b) With the Proposed IPI-Based Mechanism
Figure 7.2: Application’s work completed in a given time quantum. With the pro- posed IPI-based syscall mechanism, the clock cycle following the call to the kernel belongs to the application, not to the kernel. This is not the case with traditional system call interfaces; even syscalls that claim to be “asynchronous” suspend the application while it is delivering its request to the kernel.
Removing Drivers from the Kernel
In a KUCS operating system, a driver running as a ring 0 user process on a remote
core can have both privileged access to hardware and full user-space encapsulation.
It follows that this driver design could reveal faster performance than the equivalent
microkernel driver in user-space (as traditionally defined) because the driver can
access hardware from its own context rather than invoking the kernel.
In addition to the performance increase over traditional user-space driver imple-
mentations, a driver on a KUCS operating system also has a possible performance
advantage over kernel-level drivers employed in monolithic kernels. Without suffi-
ciently fine-grained locking, even a kernel-level driver locks other cores out of (at
least some part of) the kernel while it is servicing interrupts. In contrast, drivers
loaded with privileged access to the hardware but not into the kernel can service
interrupts as quickly as traditional kernel-level drivers, but without blocking other
cores from entering the kernel.
This effect is similar to that reported in [51] when the network driver was isolated
129
to its own virtual machine. In that case, letting a network-specific VM handle all
network interrupts without interrupting the main kernel resulted in a performance
increase, despite the added overhead of inter-VM communication. Analogous results
were also found in [22,121].
7.2 KUCS: Implementation
The Bear microkernel [123] was used as a platform to build a prototype operating
system using the KUCS design paradigm. The prototype, KUCSBear, does not im-
plement all of the features enabled by a KUCS design. However, it provides a case
study for future KUCS implementation efforts and offers a platform to investigate
the design’s potential implications on performance.
This section describes the KUCSBear prototype in detail. It is framed to reflect
the organization of Chapter 2 in order to facilitate the comparison of particular im-
plementation details between a conventional operating system (Bear) and a KUCS
operating system (KUCSBear).
7.2.1 KUCSBear
The prototype implements some but not all of the features described in Section 7.1.
It does:
• Isolate the kernel onto one particular core.
• Load user processes in virtual memory contexts with no mappings to kernel
code or data, or to its own page tables.
• Restrict the privileges of user processes even while running them in ring 0 on
cores without a resident kernel.
• Utilize IPIs to communicate between the user cores and the kernel core.
130
• Run a driver in “user-space” in ring 0 on a user core with direct mappings to
otherwise privileged hardware.
• Virtualize each core independently.
• Enforce strict security policies on the kernel core that extend the protections
otherwise offered by ExOShim.
• Demonstrate the possibility of the kernel doing “watchdog” type tasks while
not servicing user requests.
However, the prototype does not take full advantage of every feature made possible
by a KUCS design. It does not:
• Explore the possibility of system call interfaces that allow the application to
continue its work while the kernel services a syscall request.
• Route hardware interrupts directly to device drivers.
• Implement application-specific secure contexts in ring 3 on user cores.
In order to facilitate implementation, KUCSBear was developed to allow KUCS-
style kernel and user process operation on some subset of cores while conventional
kernel and user processes can run simultaneously on other cores. Even as published,
KUCSBear reserves one core to run the conventional Bear operating system. This
core runs some legacy processes in the standard ring 3 configuration and handles
hardware interrupts.
Finally, the prototype is not as stable as a production operating system, nor as
stable as the Bear operating system from which it was built. Bear, like any stable
system, has benefited from thousands of man-hours of debugging and quality control
to generate a system that can run an arbitrary number of processes over an arbitrarily
long time. Although KUCSBear has not yet been subjected to intense debugging, it
131
can run its one reserved legacy core, one reserved kernel core, and 6 user cores running
for many thousands of processes.
The KUCSBear prototype is available as open source software under the MIT
software license at https://github.com/SCSLaboratory/BearOS.
7.2.2 Interrupts
Interrupt Handling in a Ring 0 Process
Much of the communication between the process and the kernel is done via interrupts.
Therefore, interrupt handling in the process is extremely important for its functional-
ity, security, and performance. The interrupt handling initialization involves setting
up required Intel hardware configuration structures and loading interrupt handling
routines.
Interrupt Handling Routines An abstract interrupt handling scheme uses sev-
eral pieces of code to route interrupts to the proper handling routine. Upon receiving
an interrupt 0xYY, the hardware consults a vector table to find instruction pointer at
which it should execute. In order for software later in the handling control flow to have
knowledge of the vector number (0xYY), this instruction pointer is the start of a unique
routine, vecYY, that pushes 0xYY onto the stack before jumping to a more generic
handler, common handler. This assembly routine does the necessary context saving,
calls a C code generic interrupt dispatch routine, restores context, then returns from
the interrupt. The C function called by common handler is intr invoke handler. It
uses the vector pushed in vecYY to find the registered handler from an array of func-
tion pointers, and calls the proper registered handler. This control flow is summarized
in Snippet 7.1.
In the case of a ring 0 process, interrupt handling routines are one of the program
resources that the KUCS kernel needs to manage, or at least oversee, in order to guar-
132
/* Assembly code */
ENTRY(usr_vecA5)
cli
pushq %rax
movq $0xA5 , %rax
movabs %rax , vec
popq %rax
jmp _common_handler
SET_SIZE(usr_vecA5)
# jump to C from an interrupt
ENTRY(_common_handler)
# save context to the struct to be read by the kernel.
SAVE_CONTEXT_STRUCT
# save context for to return to later
SAVE_CONTEXT_STACK
# pass interrupt vector into handler
movabs vec , %rax
movq %rax , %rdi
# jump to C
RELCALL(_intr_invoke_handler)
# restore regs from stack
RESTORE_CONTEXT_STACK
# return
iretq
SET_SIZE(_common_handler)
/* C code */
void (* _intr_handler_array [256])( uint64_t );
void _intr_invoke_handler(uint64_t vector) {
_intr_handler_array[vector ]( vector );
return;
}
Snippet 7.1: When an interrupt is received, a generic interrupt handling scheme goes through a series of functions in both assembly and C code in order to properly dispatch and handle the interrupt.
133
antee that the process cannot “go rogue” and stop responding to requests/instructions
from the kernel. If the process had arbitrary control of the interrupt handling routines
on its processor core, it could maintain control of the core for an arbitrarily long time
until the processor was rebooted or a virtualization-based interruption was deployed.
With the importance of the integrity of these routines in mind, there are several
options for the mechanism to get interrupt handling, including assembly instructions,
into the process’ address space.
• Compile into the application. The assembly and C general handling rou-
tines could be compiled directly into the process. This facilitates loading the
routines into the address space since the application code is already being
loaded. Unfortunately, it gives a lot of control to the application developer
who can, at development-time or build-time, modify interrupt handling to suit
their (possibly malicious) needs. In theory, the kernel could verify the safety
of these routines at load-time but in practice this is non-trivial. Additionally,
these routines may share memory pages with legitimate user-controlled mem-
ory, which could create a challenge for page-based access right control primitives
that could otherwise be placed on the interrupt routines.
• Compile into the kernel. In order to have these routines be kernel controlled,
the kernel could include them in its own source. Then, at run-time, there would
be an already-loaded set of interrupt handling routines for the process resid-
ing in the kernel’s virtual address space. It could copy these instructions into
the user’s space. This gives the kernel complete control over the instructions.
Unfortunately, when the kernel is loaded the relocation information in these
routines will be populated with respect to the kernel’s virtual memory layout.
When the kernel later tries to copy these instructions into the process, it must
replace these addresses with respect to the user’s virtual memory layout, but
the relocation metadata will have been lost.
134
• Write at run-time. To avoid loading issues, the kernel could simply include
a routine to write the proper instructions into the user’s virtual address space.
By doing this ad-hoc, there would be no issues with relocations. However,
this is only feasible if the generic portions of the interrupt handling routines
are extremely small. This is also the least elegant of the solutions; compilers,
assemblers, linkers, and loaders all exist for a reason.
• Compile into a separate file. A compromise between the security issues of
compiling the instructions into the application and the loading issues of com-
piling the instructions into the kernel is to compromise the instructions into a
separate file of their own. This allows the developer to continue to make use of
the toolchain, the process to have access to kernel-controlled routines, and the
kernel to load the instructions via its normal loading mechanisms into the pro-
cess. The downside of this approach is that the generic portion of the interrupt
handling (up to and including accessing the function pointer array) must be
completely self-contained. In other words, it is difficult to link objects between
the compiled process and the compiled interrupt handling library.
KUCSBear compiles a separate usr intr ELF binary. This binary contains the
generic interrupt handling routines and is loaded into the process after the regular
application binary. It is called the Kernel-Controlled User Interrupt Handling Library
(KCUIHL).
The KCUIHL is loaded into the process’ context on non-writeable pages. The
virtual memory isolation guarantees that the process cannot change these protections,
and consequently the process will execute kernel-controlled code any time there is an
interrupt. However, the process can read and execute this memory. Although a
robust security model in the kernel and hypervisor levels should be able to handle
arbitrary execution in the KCUIHL, system designers may prefer to load the library in
a location that is not known to the application. This is possible using any number of
135
randomization techniques, and there are no direct mechanisms for finding it because
it is only ever entered via an int instruction. If the process guessed or discovered the
address of the KCUIHL it would have read and execute access to it, but guessing the
address would likely generate page faults that could be detected by the kernel.
Intel Hardware Control Structures Intel hardware interrupt control structures
such as the Advanced Programmable Interrupt Controller (APIC), Global Descriptor
Table (GDT), and Interrupt Descriptor Table (IDT) are all needed for interrupt
handling in the user process.
The APIC is memory-mapped so that privileged software can write to specific
memory addresses in order to send different types of interrupts. The GDT contains
state information used during the hardware context switch preformed in response to
a local interrupt. Finally, the IDT contains pointers to the handlers that should be
run in response to each particular interrupt.
A detailed description of these structures and the x86 interrupt subsystems is
available in [52, 79]. These structures should only be used by the KCUIHL, and
are only linked to the KCUIHL. Although the user will have the same permissions
to access these structures as the KCUIHL, the structures will be loaded with the
minimum required permissions. For example, the IDT is marked as non-writeable.
This guarantees that only the kernel can control what code is executed on the user
core in response to a particular interrupt.
Configuration of the virtualization layer also protects the GDT and IDT. The
hypervisor guest state allows for vmexits to occur if the instructions used to load these
structures for inspection (lgdt, lidt) or store new ones (sgdt, sidt) are executed.
This allows the virtualization layer to safeguard the integrity of the kernel-controlled
interrupt handling routines on the remote user core.
136
Special Considerations for Drivers As discussed in Section 7.1, driver processes
can be loaded with special permissions in a KUCS design. The first changes could
exist in the virtualization layer, although this would add complication as the drivers
would have to stay on one particular core or the virtualization configuration would
have to follow the driver around to different cores. KUCSBear does not implement
virtualization protection differences between user cores.
Another technique that is possible in the KUCS design but not implemented
in KUCSBear is routing hardware interrupts directly to the appropriate core to be
handled natively in the driver. This would require the same routing mechanisms as
the virtualization; the kernel would have to monitor what core (if any) contained the
particular driver at a particular time in order to route the interrupt to the correct core.
In this case, the driver process could request that the kernel load a driver-provided
interrupt handler into the IDT so that it could service interrupts directly.
Although it does not implement full support for drivers as enabled by the KUCS
design, KUCSBear does run Bear’s VGA daemon under the KUCS paradigm. A
special mapping in the process’ page tables gives it the ability to write directly to
VGA memory. This special mapping could be done at load-time, but in KUCSBear
it is done in response to an initialization system call from the daemon.
IPI Source Determination
When many processor cores are running user processes and concurrently requesting
kernel intervention, an interrupt is not sufficient to tell the kernel what it needs to
do. More specifically, the kernel must determine the source of the IPI before it can do
anything else. Once it knows which core (and therefore which process) has requested
assistance, it can query that core’s memory interfaces to determine what actions to
take next.
Interrupt controller hardware that reported the source of the interrupt would
137
solve this problem efficiently. Unfortunately, the x86 hardware does not provide a
mechanism for determining the originating core of an IPI. As a result, some soft-
ware mechanism must be provided for determining the source of an inter-processor
interrupt. There are three main ways to do this: polling, interrupt vector assign-
ment, and hypervisor intervention. Each method has advantages and disadvantages,
as described below.
Polling The most obvious method for determining the source of an event is by
polling: querying each core’s shared memory interfaces until an event requiring kernel
intervention is found. In fact, a purely polling based solution could do away with
interrupts entirely if the idle time of the kernel was spent constantly querying different
cores, looking for work to do. The obvious disadvantage to the polling method is that
it is computationally intensive; the kernel is spending a lot of time looking for events
to service rather than simply servicing events.
Polling becomes much more attractive when interrupts are integrated as well. In
this case, the kernel would only begin querying cores looking for an event to service
once it receives an interrupt. This method deeply reduces the amount of overhead
involved with the kernel core churning on message queues looking for messages. The
kernel core would do whatever task it wants until it receives an interrupt then it
would search the cores for work to do and service the work before returning to its
prior task.
Unfortunately, the hardware adds yet another restriction that makes polling less
attractive again. The interrupt delivery hardware can only receive two of the same
interrupt vector before one is handled. Any further interrupts sent to the core are
discarded. The possibility of losing interrupts eliminates the option of waiting for an
interrupt and then poll until an event to service is found and processed. Instead, the
kernel would need to wait for an interrupt and then poll until all events to service are
138
found and processed. This eliminates the possibility of missing requests by missing
an interrupt, but increases the amount of time required for finding and servicing user
messages.
In summary, the main disadvantage of polling is performance. It requires a fair
amount of work for finding the source of a request for service. In addition, while its
ability to scale to any number of cores is theoretically an advantage, having complexity
that is linear in the number of cores in such an important system task may become a
major performance bottleneck as processors with hundreds, thousands, or even more
cores become mainstream.
Interrupt Vector Assignment In order to accommodate more than two inter-
rupts simultaneously, the hardware provides 256 individual interrupt vectors that
can be used. This capability can be leveraged to address the problem of interrupt
source identification if different user cores send different interrupt vectors to the ker-
nel. With this solution, the kernel would know based on which interrupt vector it
receives which core sent the interrupt.
One disadvantage of this mechanism is that the hardware prioritizes interrupt
delivery by vector number. This behavior is not configurable. This means that cores
with high-priority interrupt vectors assigned will always cut ahead of other cores
that send interrupts at the same time. Fortunately, this risk is mitigated by the
fact that the kernel only registers interrupts in the interrupt handler, rather than
servicing the interrupts. This means that the kernel spends most of its time ready
to receive interrupts and the risk of two interrupts occurring at the same time and
being delivered out of order is reduced. Furthermore, although it is not implemented
in KUCSBear, a KUCS operating system could simply randomize the vectors used
by particular cores over time, in effect giving every core “a turn” at being the highest
priority core.
139
Another possible issue with this mechanism is that a process with arbitrary write
access to the APIC could send an interrupt using the vector of another core, essentially
impersonating the other process. Hiding the KCUIHL as discussed previously could
mitigate this threat. However, with a sufficiently discerning kernel implementation,
the process could not gain anything by impersonating another process. The real
mechanism for communicating between the kernel and the user process is the shared
memory interface. The interrupt is just an alert that the kernel should query the
shared memory interface to determine what has happened on the core. In the event
that a process sent a vector other than its own, the kernel should notice the lack of
corresponding communication from the core that owns that vector and take remedial
action.
Finally, this solution may not scale to systems with large numbers of cores. For
example, it certainly will not be sufficient for a system with more than 256 cores.
The advantage of this technique is that it offers simple constant-time determi-
nation of the source of an IPI. In addition, it is reasonably simple to implement; a
simple lookup from IPI vector to core is all that is required. Along with the tech-
niques to address the limitations of the method, this makes this an excellent candidate
mechanism. This is the technique used in KUCSBear.
Hypervisor intervention A third technique for determining the source of an IPI
could be by using the hypervisor. In particular, the hypervisor could intercept APIC
accesses from the user core and utilize its trusted access to all of memory to write the
core number in kernel memory. This technique is the most secure but also likely to be
the slowest, especially if the hypervisor is not already monitoring APIC accesses. If
a particular KUCS implementation had the hypervisor monitoring APIC accesses as
part of is security policy, then this mechanism could be the simplest without adding
much overhead.
140
#de f i n e r emote pdpt v i r t ( pcr3 , pml4t idx ) \ ( ( s t r u c t pdpt ∗) phys2v i r t ( ( s t r u c t pml4t ∗) phys2v i r t ( pcr3)−>e n t r i e s [ pml4t idx ] . addr ) )
#de f i n e r emote pd v i r t ( pcr3 , pml4t idx , pdpt idx ) \ ( ( s t r u c t pd∗) phys2v i r t ( r emote pdpt v i r t ( pcr3 , pml4t idx)−>e n t r i e s [ pdpt idx ] . addr ) )
#de f i n e r emot e p t v i r t ( pcr3 , pml4t idx , pdpt idx , pd idx ) \ ( ( s t r u c t pt ∗) phys2v i r t ( r emote pd v i r t ( pcr3 , pml4t idx , pdpt idx)−>e n t r i e s [ pd idx ] . addr ) )
#de f i n e r emote vaddr v i r t ( pcr3 , pml4t idx , pdpt idx , pd idx , p t idx ) \ ( ( s t r u c t pg∗) phys2v i r t ( r emot e p t v i r t ( pcr3 , pml4t idx , pdpt idx , pd idx)−>e n t r i e s [ p t idx ] . addr ) )
Snippet 7.2: If the kernel were to use arbitrary virtual addresses to map each frame of memory used by the remote process, it would require multiple phys2virt lookups for each attempt to find the memory at a particular virtual address within the remote process.
7.2.3 Virtual Memory
The KUCS operating system design runs processes on cores in virtual memory sand-
boxes. The virtual memory context of the process contains only mappings to the text
and data needed by the process. It does not contain any mappings to the kernel or to
its own page tables. This creates a unique challenge when it comes to manipulating
this address space. In particular, the KUCS kernel needs a method for addressing the
memory that comprises the remote process’ memory.
There are several possible methods for doing this. For instance, the kernel could
use arbitrary virtual addresses for each physical frame of memory used in the in the
remote process. The Bear kernel could use the vk module for this purpose as it
manages a pool of unused virtual addresses. Unfortunately, this is not a particularly
elegant solution and keeping track of these mappings in some type of structure like
a reverse page table would incur a large memory overhead. They could be recovered
from Bear’s frame array with phys2virt as suggested in Snippet 7.2, but the lack
of any linkage from one paging structure level to another leads to a slow process for
looking up virtual address for deeper page tables.
In order to mitigate the performance cost of the multiple lookups needed with
per-frame virtual mappings, the KUCS Bear prototype uses a method to maintain
persistent virtual mappings to all the paging structures in each remote process. To
141
do this, a special pointer called the vmem bridge stores the physical address of the
cr3 target of the remote process into one of the entries in the kernel’s PML4T. This
means that the kernel can create a specially constructed virtual address to force the
MMU translations to resolve to a particular PT of the remote process. Using Bear’s
recursive pointer (as described in Figure 2.2b on Page 16) the MMU can also provide
virtual addresses for any higher level page table.
Unfortunately, the vmem bridge will not allow mappings to the lowest level pages
in the remote process. As such, the KUCS Bear prototype still uses the vk module
to manage arbitrary virtual addresses to maintain the mappings for these lowest level
pages. This hybrid approach is shown in Figure 7.3.
Note that the vmem bridge method will only support as many simultaneously
running processes as there are free entries in the kernel’s PML4T; a maximum of
510. A more complete KUCS implementation could use the vmem bridge to address
the most performance-critical processes while using direct mappings to support an
arbitrarily large number of unique remote processes.
7.2.4 Message Passing
Although the asymmetrical multiprocessing design allows for asynchronous system
calls, there are design challenges associated with the implementation of such a mech-
anism. One such challenge that is beyond the scope of this thesis is delivering a
return value to a process that has continued execution immediately after sending a
message. One that was solved in this thesis is the method of providing the message
in a place where the kernel can access it. The user process in Bear’s original message
passing interface discussed in Section 2.2 simply wrote the message onto its own stack
as shown in Snippet 2.1. When the kernel was invoked, the message could easily be
read because the process would not have continued its execution and therefore the
message was preserved on the user stack. In an asynchronous system, the user pro-
142
!"#$%&'"()*"+,-(%"(.%!'-+$/+,-( !!"
!"#$%& '()* +"%,$-./,0/1234"5-./677%&44/8%-94.-,"09:;09#/<07&
513-200.eps
PML4E PDE
Physical Address
PDPE
PTE
Physical Page O�set
Sign Extension
63 0
Page Directory O�set
Page Map Level-4 O�set
Page Directory Pointer O�set
Page Table O�set
Page Map Base Register CR3
64-Bit Virtual Address
Page Directory Pointer Table
Page Directory Table
Physical Page Frame
Page Table
Page Map Level 4 Table
=</;/:9-)87$6543&!2#1)0/.-,'$#+&+*)('&"%$#
513-200.eps
PML4E PDE
Physical Address
PDPE
PTE
Physical Page O�set
Sign Extension
63 0
Page Directory O�set
Page Map Level-4 O�set
Page Directory Pointer O�set
Page Table O�set
Page Map Base Register CR3
64-Bit Virtual Address
Page Directory Pointer Table
Page Directory Table
Physical Page Frame
Page Table
Page Map Level 4 Table
Kernel Page Tables
Remote Process Page Tables
vm em
b rid
ge
D irect M
apping
Figure 7.3: The KUCS kernel core uses two methods for addressing the memory of a remote process. A pointer in the top level PML4T allows virtual addressing to the paging structures of the remote process, while the vk module allows for direct mappings to the lowest level of pages.
143
cess may return from the msgsend call before the kernel has a chance to access the
message. This would change the user’s stack and thus deny the kernel from accessing
the message.
Naively, the need for a persistent location for storing messages could be solved
simply by the user’s malloc implementation. However, malloc may need to call the
umalloc system call, leading to an recursive problem with no base case. The solution
implemented in KUCSBear is a ring buffer stored in memory shared by the kernel
and the process.
The Message Ring Buffer
A ring buffer is a common data structure for tasks involving asynchronous production
and consumption of data. It is especially convenient with just one producer and one
consumer, because in that case it does not need mutual exclusion or other special
synchonization techniques. That special case suits this application; the process is the
sole producer while the kernel is the sole consumer.
In order to use the ring buffer, the process simply uses four global variables:
sc rbuf, sc rbuf head, sc rbuf tail, and sc rbuf size. The process relies on
the kernel to populate these variables with the appropriate values at its load-time, so
that it may simply use them without allocating any of the underlying memory. When
writing a message, it simply writes to the current head index of the ring buffer, as
long as the buffer is not full. This is shown in Snippet 7.3.
Similarly to Snippet 7.3, the kernel can consume messages by using the tail
index into the ring buffer array. However, the kernel side is slightly more complicated
due to the fact that it is not mapped into the same page tables as the user process.
Therefore, it cannot simply dereference the same addresses that the user process is
dereferencing. The process of initializing and then accessing the ring buffer from
the kernel is described in detail here as an example of the issues created when two
144
Message_t *produce_rbuf_msg(Message_t *msg) {
uint64_t next_head;
Message_t *ret;
/* increment the head */
next_head = (_sc_rbuf_head + 1) % _sc_rbuf_size;
/* make sure there’s room for the new msg */
while ( _sc_rbuf_tail == next_head ) ;
/* store message pointer */
_sc_rbuf[next_head] = *msg;
/* will return the address where the msg was stored */
ret = &_sc_rbuf[next_head ];
/* save the new head */
_sc_rbuf_head = next_head;
return ret;
}
Snippet 7.3: The process needs a persistant memory location to store messages so that it may continue executing while the kernel retrieves, processes, and responds to its message. This is the procedure for adding a message to the ring buffer used to accomplish this persistant and asynchronous memory space.
145
/* Allocate (and record kernel ’s address to) Ring buffer */
proc ->k_sc_rbuf = vmem_alloc_remote(proc , usr_rbuf_addr ,
PAGE_SIZE , PG_NX);
/* tell the user where the ring buffer will be */
*remote2vaddr(proc , proc ->usr_sc_rbuf) = usr_rbuf_addr;
/* tell the process how many messages the ring buffer will hold */
*remote2vaddr(proc , proc ->sc_rbuf_size )= PAGE_SIZE/sizeof(Message_t );
/* find the kernel ’s address for user’s global head and tail vars */
proc ->k_sc_rbuf_tail = remote2vaddr(proc , proc ->usr_sc_rbuf_tail );
proc ->k_sc_rbuf_head = remote2vaddr(proc , proc ->usr_sc_rbuf_head );
/* initialize the user’s head and tail index variables */
*proc ->k_sc_rbuf_tail = 0;
*proc ->k_sc_rbuf_head = 0;
Snippet 7.4: This code demonstrates some of the pointer translation and bookkeeping necessary to create a memory space that is shared between two contexts that do not share a page table.
contexts that do not share page tables attempt to access common memory.
The process of initializing the ring buffer from the kernel is summarized in Fig-
ure 7.4 on Page 148. First, the loader makes a note of the loaded location of the
relevant global variables that will be used by the process: sc rbuf, sc rbuf head,
and sc rbuf tail. The kernel must initialize these values with the address of the
allocated memory to be used for the buffer, 0, and 0, respectively. However, the loader
only knows the address that the user will use to access these variables which, due to
the separate address spaces, is different from the address that the kernel can use to
access them. Thus, the kernel must take care to find (and record) the addresses it can
use to access the global variables and the ring buffer itself, as shown in Snippet 7.4.
After initialization, the kernel can consume messages from the ring buffer by being
careful to use its own addresses to access the shared memory, as shown in Snippet 7.5.
146
/* find and increment the tail (should not be modified by proc) */
tail = (*proc ->k_sc_rbuf_tail + 1) % proc ->sc_rbuf_size;
/* get kernel -local copy of message */
Message_t mp = proc ->k_sc_rbuf[tail];
/* OMITTED - handle the message */
/* ’consume ’ msg; tell the proc about the new tail */
*proc ->k_sc_rbuf_tail = tail;
Snippet 7.5: After initializing the addresses for itself and for the process to access the common memory of the ring buffer, the kernel can consume messages from its tail. This is the procedure it uses to do so.
System Calls
As described in Section 7.1, the system call in an ASMP kernel is an interprocessor
interrupt from the user core to the kernel’s core. This can be accomplished simply
from the process by simply writing to the APIC to generate an IPI. Unfortunately, this
direct method fails to accommodate a situation in which the kernel needs to recover
the process’ state. With the process and kernel sharing a core, this is straightforward
because the privilege level change that happens when changing from the process to
the kernel saves the state onto the stack. No such mechanism exists when invoking
the kernel on a separate core.
Although a scheme could ask the process to save its own state to a shared memory
interface as discussed in the context of message passing, this is extremely complicated.
For example, the instruction pointer changes with each state saving instruction; this
is much like trying to change a bicycle tire without dismounting the bike! In addition,
it relies on cooperation from the application developer to faithfully and accurately
save their own state before issuing the IPI.
These issues can be avoided with an indirect method in which the process invokes
a local interrupt on its own core. This saves its current state automatically during
the hardware routine of switching to an interrupt stack and going through the kernel-
147
addr label value
_sc_rbuf
_sc_rbuf_head
_sc_rbuf_tail
A P
B P
C P
D P
E P
F P
G P
addr label value
usr_sc_rbuf
usr_sc_rbuf_head
usr_sc_rbuf_tail
A K
B K
C K
D K
E K
F K
G K
H K
I K
J K
K K
k_sc_rbuf_tail
k_sc_rbuf_head
k_sc_rbuf
0
0
0
0
0
0
G K
H K
I K
E P
B P
C P
D P
Process Virtual Address Space
Kernel Virtual Address Space
Virtual Memory Abstraction
Virtual Memory Abstraction
Physical Memory
_sc_rbuf[0]
_sc_rbuf[1]
_sc_rbuf[2]
k_sc_rbuf[0]
k_sc_rbuf[1]
k_sc_rbuf[2]
1
2
3
1 Loader tells the kernel where in the process’ address space the important global variables are loaded.
2 The kernel allocates the ring bu�er, maps it into the process’ address space, and populates _sc_rbuf.
2
3 The kernel saves the addresses it will use to access the ring bu�er and head/tail indeces.
Figure 7.4: Initialization of the necessary memory and variables for the shared ring buffer used to pass messages from the user process to the kernel.
controlled interrupt handling routines. In the case of a system call, these routines
then forward an IPI to the kernel core where the kernel will now have access to
the correctly saved state. Figure 7.5 compares the direct and indirect system call
methods.
The extra interrupt and state saving in the indirect system call method adds a
performance cost over the direct IPI method. Section 7.3.2 quantifies this cost against
the direct IPI and conventional system call mechansims.
Additionally, some of the performance cost of the indirect system call method
could be recovered by using the indirect method only where the execution state of
the caller is important. Calls such as fork() require that the kernel have knowledge
of the state of the caller, but simpler system calls such as getpid() can be serviced
148
Kernel CoreUser Core User Core
Handle IPI
Process Code
Process Code
IDTIDT KCUIHL KCUIHL
IPI
INT
IPI
Direct Indirect
Figure 7.5: With the user and kernel residing on different cores, a new mechanism is required to dispatch system calls. Two possible alternatives to the traditional INT/IRET system call mechanism are the direct IPI and the indirect IPI.
faithfully without full knowledge of the caller’s state.
Kernel-Space System Call Servicing
For every system call or other event dispatched from the user process, the kernel
must do some work to handle the event. In a conventional operating system, the
interrupt that triggers a privilege mode switch on the core routes execution to a
kernel event handler which can branch further, routing control to the appropriate
kernel functionality for the particular event received. In a KUCS operating system,
the IPI delivery can be configured the same way.
With the conventional operating system design, this synchronous event handling
is the obvious solution. A process is running on a single core and that core is either
in user mode running code for the process or in kernel mode running code for the
process. This means that when the user process requests work from the kernel, the
whole core will be in kernel mode and might as well finish the kernel-mode work.
With a KUCS design, though, a task can be considered as running on 2 cores
simultaneously; the user mode portion on one core and the kernel mode portion on
149
another. In this case, there can be some more flexibility in when the kernel services the
request from the user core. One asynchronous approach involves having the kernel
core in a loop servicing pending requests for work at idle, and then the interrupt
handler simply registers a new pending event. This method minimizes the time spent
in interrupt handlers; an especially important consideration with a KUCS design in
which one kernel core is handling requests from multiple different user cores.
The KUCSBear prototype uses asynchronous kernel event handling. The interrupt
handler in the kernel writes to a ring buffer of pending events. It is important that
the interrupt handler does no more than this because the kernel may have been doing
other work when the interrupt arrived and a complex workload in the handler could
interfere with the state of the interrupted task. When not in this interrupt handling
routine, the kernel core is continuously reading pending events from the ring buffer
and servicing them.
Note that the KUCSBear prototype has not implemented “truly asynchronous
system calls” as discussed in Section 7.1. The user process still suspends its own
execution until its requested task is serviced by the kernel. The completion of truly
asynchronous system calls is beyond the scope of this work, although it is an exciting
and novel workflow, possible only on a KUCS operating system.
Additionally, note that the asynchronous kernel event handling facilitates “watch-
dog” tasks during free time on the kernel core. This is because any work done in
an interrupt handler needs to be independently locked from any work done outside
of an interrupt handler. If the kernel handles the events in the interrupt handler,
as in a conventionally designed operating system, then fine-grained locking would be
required to separate the watchdog work from the event handling work. Even with
fine-grained locking, some watchdog work would be impossible because it would not
be able to survive being interrupted and having state change. This is not an issue in
conventionally designed operating systems because the kernel is only ever run in an
150
interrupt handler; no work is done outside of an interrupt handling context.
The KUCSBear prototype demonstrates how to do “watchdog” work in the kernel
along with servicing user requests by harvesting the memory of dead processes in
between servicing events from user cores.
7.2.5 Scheduling
Context Switching
Context switching without the kernel on core is difficult because it cannot act as
an intermediate context between two processes. Not only must these two processes
manage to sync in order to change from one to the other, but they must do so without
compromising their privacy. Some possible solutions, loosely ordered from “hardest
to get right” but fastest to “easiest to get right” but slowest include:
1. Direct transfer ( A→ B ): process A is given cr3B, switches to B.
2. Intermediate context ( A → K ′ → B ): Process A is given cr3K′ where K ′ is
a context built by kernel, specifically designed to intermediate between A and
B. In other words, it has landing code at the address of the switching code in
A, switching code at the address of landing code in B, and communicates with
the kernel core in between.
3. Modified Destination ( A → B′ → B ): As above, but kernel embeds K ′ into
B’s address space while B is blocked, and this version of K ′ (B′) deletes itself
from B before jumping to any B controlled code.
4. Hypervisor ( A → H → B ) By doing a vmcall, the hypervisor can do any
manipulation necessary to switch the operating context on the core. As the hy-
pervisor in this design is an extension of the kernel, it is trusted and omniscient.
This makes it a natural entity for mediating the context switch.
151
Fortunately, with just a bit of care taken, the fastest solution can be implemented
safely. The first important technique is that the scheduling function will be loaded at
the same location in every process, solving the issue of differing locations of “switch-
ing code” and “landing code”. This works similarly to scheduling between different
processes’ kernel contexts on conventional operating systems. The actual virtual ad-
dress switch always happens at a common address, regardless of what processes are
being switched to or from. Then, the stack for that particular process can return
execution to the appropriate place in its execution path.
Furthermore, state restoration happens only after the new address space is loaded.
This ensures that, when switching from process A to process B, process B never has
access to any of process A’s general purpose register values.
Finally, the scheduling function is provided as a non-writeable routine into the
process’ address space. This guarantees that the process is forced to execute the
scheduling routine as written. Additionally, it is put into the process’ IDT as an
interrupt handler for the SYSTICK interrupt, ensuring that it must be executed at
the border of a process’ time quantum.
Bootstrapping (and Idling)
Running the first process on a core can be an extra challenge. While each process is
set up to transfer control to another process, the system initialization code running
on the core after boot is not set up for this. Although one could load interrupt
handling and user-space context switching code into the system initialization context
and then switch from it as if it were a regular process, this might inhibit kernel-space
randomization efforts. Furthermore, this method represents a confusion of semantic
differences between system code and system-provided user library interrupt handling
code.
Instead, the prototype uses the idle process as an intermediate between system
152
initialization code and user code on a particular core. Like most operating systems,
there is one idle process per core. These are loaded separately from regular user
processes and serve as a placeholder context to be deployed when there is no useful
work for a particular core to do. The only things present in the idle process are:
1. Idle Function. This extremely simple assembly routine writes the cr3 of the
idle process, then makes sure interrupts are on and halts in a tight loop. This
function is entered only once – the first time the idle process is run – and then
each time the process is running it will continue to loop on the halt.
2. Kernel-Controlled User Interrupt Handling. An instance of the KCUIHL
is copied into the idle process. This includes the scheduling function. These
routines are the mechanism by which the core can switch from the idle process
to another process. The kernel can initiate this switch by sending an interrupt
to the idle process.
After the idle processes are initialized, the kernel context doing the initialization
on each core calls the virtualization initialization function. The kernel context on
the core will become that core’s hypervisor context. The guest virtual machine is
configured, as described in Chapter 4 in the context of ExOShim, so that the guest
that is run on vmlaunch is the ring 0 idle process. This method allows a secure way
to change from the kernel initialization context on a user core to the idle process,
which can then schedule other processes as appropriate. The former kernel context
will never again run on that core unless a vmexit restores the hypervisor.
The kernel core initializes its virtualization layer the same way as ExOShim. In
particular, it sets up a second kernel context which will execute the shim initialization
function, configure the host state to match itself, configure the guest state to match
the original regular kernel context and then issues a vmlaunch to set itself up as the
hypervisor and restore the kernel state prior to its being scheduled.
153
Special consideration is needed during the first context switch to a particular
process. The first time a process is run, it should be executing from a clean state.
However, since the routine that caused it to be scheduled was actually an interrupt
handler in another process, the core will think that it is still in an interrupt handler
when it begins to execute the new process. Therefore, the context switching routine
must build a stack frame such that an iretq instruction points execution towards the
beginning of the process’ instructions and counteracts the interrupt from the previous
process. In future context switches, the process will have triggered a context switch
via interrupt during the last time it ran, so it continues operating without an iretq
in the context switching routine. Upon restoration, the process’ stack will unwind
and bring it back out of the interrupt handler that it triggered a full time-quantum
(or more) ago.
Scheduling Proper
With the mechanism for initialization and context switching described, the main
scheduling algorithms can be discussed. The challenge associated with choosing the
next process to run is not one of how ; like the original Bear kernel, KUCSBear simply
uses a round-robin scheduling scheme. Instead, the challenge is associated with the
when. The solution for when to choose a process to run is trivial in a regular operating
system where the kernel is invoked during context switching. Since it needs to run
to switch from one process to another, the kernel can simply choose which process to
run during that context switch.
Unfortunately, with the processes running on a core remotely, without the kernel,
context switches no longer invoke the kernel. Therefore, a target process must be
chosen sometime before the context switch is to occur. This can be done immediately
before switching or early in its time quantum. The former approach requires a syn-
chronous communication with the kernel; the process must wait for an answer after
154
asking what process to run next before it can continue. The alternative approach can
be accomplished asynchronously instead. In the asynchronous case, the process can
send a message to the kernel as soon as it begins to run and assume that the kernel
will have responded by the time it is next ready to switch contexts.
The benefits of the asynchronous scheme include a reduced overhead time during
context switching. Additionally, it serves as a “check-in” event where the kernel can
check on the new process at the beginning of its time quantum. However, there may
be issues with the asynchronous method. If no process is ready to run at the time
of check-in, an “idle” process will be run. If a more interesting process becomes
available during the time quantum, a careless implementation might waste a time
quantum idling while another process is waiting to run. Salvaging that time is a
difficult implementation task with sensitive timing requirements.
The synchronous scheme may be slower because the kernel cannot do its schedul-
ing work in parallel with process execution. However, its implementation is more
straightforward because it eliminates the complication from the asynchronous case in
which the scheduling algorithm is run early and possibly without complete system
state. Additionally, this method means that the “check-in” is not necessarily the first
event of the process’ time quantum. Although that is an attractive property of the
asynchronous solution, it is not strictly necessary. Any event can serve as a check-in
for the kernel’s purposes, and because the context switching mechanism resides in
kernel-controlled code (in the KCUIHL) the kernel can trust that the context switch
occurred faithfully.
In order to avoid unnecessary TLB flushes, the scheduling function in the KCUIHL
checks whether it is about to schedule a new process or if it will remain on the core
for another time quantum. In the event that it is not leaving the core, it skips the
step of writing to the cr3 target. This avoids a TLB flush on the core, which would
slow the process down in the beginning of the next time quantum by causing many
155
cache misses.
(More) Secure Scheduling
Without the kernel on the core to supervise the user process, special care must be
taken to ensure that the remote core is acting faithfully under the direction of the
kernel. This is accomplished by the KCUIHL: the interrupt handling library mapped
into the user process. As discussed previously, this library cannot be modified by the
user process because it is marked as non-writeable in the page tables. Consequently,
when the timer interrupt is triggered on the remote core the KCUIHL acts as an
agent of the kernel that preforms the scheduling transition.
Although the design ensures that the user core must schedule new processes ac-
cording to the kernel’s scheduling algorithms, a mechanism can be used to police
this transaction further. In order to guarantee that the remote core is behaving as
expected, each process can be loaded with a unique and random identifier. This iden-
tifier will be loaded into read-only memory for the process. When scheduling occurs,
the process will read its identifier and write it to a predefined memory location.
The kernel can read this memory location and verify that the identifier it sees
belongs to the process that it expects to be running on the remote core at a given
time. In order to avoid collusion between processes, the identifier can be written in
the kernel-controlled code.
Note that if the kernel-controlled code in the user process is corrupted, there is
little that this mechanism can do. Without a trusted agent on the core, the kernel
cannot expect to have any control over the remote core. In the meantime, however,
this method can provide an additional verification step to verify that the remote core
is operating the way that the kernel expects it to be.
In the event of the failure of these software mechanisms, the virtualization layer
could be deployed to recover the system. The virtualization layer on each core is a
156
trusted part of the system code that can act as a reliable agent of the kernel on each
remote core.
7.3 KUCS: Evaluation and Analysis
7.3.1 Security
Section 7.1 discussed several ways in which the KUCS operating system design offers
increased security. KUCSBear realizes many of these features, including hard separa-
tion between user- and kernel-contexts, offering resistance to ret2usr and kernel code
injection type attacks, as well as providing protection from Meltdown [109].
As discussed in Section 7.2, KUCSBear loads each user process into a virtual
memory context without any mappings to any kernel memory. This virtual memory
isolation is sufficient to offer protection from Meltdown, which utilizes these mappings
in a process with weak user- and kernel-space separation in order to leak kernel
memory.
The virtualization layer on the kernel core profiles the memory when the kernel
is finished initializing. The same mechanism used by ExOShim, as described in
Chapter 4, is used to ensure that for the lifetime of the kernel, the kernel code pages
loaded at initialization time can only be executed; not read or written. However,
the fact that only kernel code is ever executed on the kernel core can strengthen this
guarantee. All memory that is not marked as kernel code during initialization can
be marked as non-executable for the lifetime of the system, even by the kernel. This
defeats the possibility of executing any non-kernel code on the kernel core, mitigating
the threats of ret2usr and kernel code injection attacks. It even defeats the threat
of ret2dir [92] type attacks, even though they are classified as a kernel design flaw
rather than a conventional privilege escalation mechanism.
However, KUCSBear is designed to be a proof-of-concept and case study for the
157
KUCS operating system design. It is not provided as a secure operating system. As
such, there are some implementation-specific security holes that need to be addressed
for a secure KUCS system to be deployed.
KUCSBear runs user processes in ring 0. Unfortunately, it does not fully repro-
duce ring 3 protections in this context. Some operations, such as loading a new IDT
or GDT, are easily prohibited by simple configuration of the virtualization layer on
the user cores. Unfortunately, other restricted options are not so easily restricted.
Consider the instruction cli which disables interrupts on the core. This is an in-
struction that should not be allowed, because the kernel controls the user core by
sending it interrupts. Unfortunately, the kernel-controlled user interrupt-handling li-
brary needs to call cli in order to reliably process potentially concurrent interrupts.
This means that the user core needs to call cli, but only under certain conditions.
While the KUCSBear prototype does not deal with this issue, there are several
possible solutions. For example, a security policy implemented in the virtualization
layer could be consulted when cli is called and allow or deny the instruction based
on the calling context. Alternatively, the kernel could monitor the behavior of each
user core through its normal interactions with the core, and take corrective action if
any core is misbehaving. Finally, non-maskable interrupts (NMIs) could be used to
force core behavior regardless of the cli.
Giving the process access to the APIC also poses unique security challenges. The
process needs access to the APIC in order to send IPIs to communicate with the ker-
nel. However, with arbitrary access to the APIC, the process could spam cores with
interrupts, falsify interrupt-based messages, or send special signals, such as start-up
interrupts, that could affect other cores. KUCSBear does not protect from this risk.
One method to make this attack much harder for the attacker would be through ran-
domization of the mappings to the APIC. If the APIC is linked only to the KCUIHL,
and the user process uses a local interrupt to access the KCUIHL, there would be no
158
way for the process to know the location of the APIC mapping. However, an infor-
mation leak or a very good guess could give the user direct and unrestricted access
to the APIC. A secure implementation would want to use the virtualization layer to
moderate accesses to the APIC from the user cores.
Another option for implementing a secure KUCS implementation on x86 hardware
would involve loading the user process into ring 3, with the KCUIHL loaded into ring
0. The user process would still not have any mappings to any kernel memory and
would still be run on a core that never runs the kernel. However, application code
would be run in ring 3 and therefore access to privileged instructions or the hardware
would not pose any threat. Instead, a local interrupt would route execution into the
KCUIHL in ring 0 which could then write to the APIC and preform any required
instructions. This design would be more secure, but adding a privilege mode switch
during system calls would incur an additional performance cost.
7.3.2 Performance
System Call Mechanisms
The system call mechanism is one of the biggest differences between KUCS and
conventional operating system design. The conventional method, using local INT or
SYSENTER instructions to change from ring 3 to ring 0 and IRET or SYSEXIT to change
back, is described in Chapter 2. In KUCS, the user can send an IPI to request work
from the kernel and monitor shared memory interfaces for a response.
Section 7.2.4 describes an extension of the IPI mechanism in which the user core
first issues a local interrupt to direct execution into the KCUIHL which actually issues
the IPI. This is referred to as an “indirect IPI” mechanism.
A fourth system call mechanism has been developed in response to the Meltdown
vulnerabilities. Most major operating systems have implemented system calls that
use local interrupts to change privilege from ring 3 to ring 0, but only find a stub in
159
ring 0. This stub issues a page-table swap in order to access the kernel. In order to
verify that the kernel never shares virtual mappings with the process, another page
table swap is required before returning control to the user process. This is actually
a return to a mechanism developed in the 4G/4G Linux Split project [118] to give
32-bit user processes more virtual memory by removing the kernel from their virtual
address space.
Microbenchmarks were developed to measure the relative performance of these
four system call mechanisms. In order to isolate the behavior being measured, the
tests were conducted on a system that did no other work. All peripheral input/output
was suspended, and even the timer interrupt was disabled. Each of the cores either
executed its test program or simply halted.
First, the performance of the system call mechanism itself was measured. This
“one-way” ping test measured the time between the “user” issuing a request for work
and the “kernel” receiving the request. Also of interest is the “round-trip” ping test
time, measuring the time between when the user issues a request for service and when
it can continue its work. Finally, a third test simulated a “real-world” ping in which
the kernel needs to do some work in response to the request from the user. This
test is important because the meltdown system call mechanism impacts the speed of
kernel processing.
In all three of these tests, the built-in Time Stamp Counter (TSC) was used to
measure the mechanisms. A particular core reads its TSC, then indicated that the
test should begin. When it saw an indication that the test was over, it sampled its
TSC again in order to evaluate the number of cycles consumed during the test. In
all tests, commonly mapped memory was used to coordinate between different cores.
This memory was mapped as uncacheable on each core in order to avoid skewing the
results of the test with cache-coherency latency.
For each test, the IPI and Indirect IPI mechanisms used 3 cores. The first read its
160
TSC, gave the signal to start the test, waited for a “done” signal, and then read its
TSC again and printed the result. The second core waited for the “done” signal and
then triggered an interrupt. For the IPI case it sent an IPI to the third core while for
the Indirect IPI case it triggered a local interrupt whose handler sent the IPI to the
third core. In the case of the one-way test, the third core just did a busy-wait until
it received an IPI whose handler indicated “done”. In the other two tests, however,
its IPI handler would just return (for the round-trip test) or do pointer-chasing and
memory manipulation (for the real-world test) before allowing the second core to
continue and indicate “done”.
The conventional INT/IRET mechanism tests also used one core to simply begin
the test, monitor for completion, and measure the difference. However, where the
IPI and Indirect IPI mechanisms needed 2 additional cores (to simulate the user and
kernel cores) the traditional mechanism only needed a single core (because the user
and kernel run on the same core). In the one-way test, the second core waited in ring 3
for the signal to begin the test. It then issued a local interrupt that changed privilege
level to ring 0 where the core declared the end of the test. In the round-trip and
real-world cases, the end of the test was declared back in ring 3 after the kernel had
used the IRET instruction. In the round-trip case the kernel returned immediately,
but in the real-world case it did the same pointer chasing and memory manipulation
tasks as mentioned previously.
Finally, the Meltdown Patch mechanism was tested in the same way as the con-
ventional mechanism except the kernel wrote a new CR3 target to change page tables
as soon as it entered ring 0 and again before it left. For this test, global paging was
disabled because Meltdown patches cannot allow for the TLB to contain mappings
to kernel code while the user is executing; global paging would allow this.
Each of the three test cases was run 100 times with each of the four system call
mechanisms of interest. The results of these 12 tests are summarized in Figure 7.6
161
(on page 163) and Table 7.1 (on page 164) and discussed below.
Figure 7.6a and Table 7.1a show the results of the one-way mechanism for all four
mechanisms. The simple IPI is the fastest, while the Indirect IPI is the slowest. This
is not very surprising since the Indirect IPI, which does both a local interrupt and
a simple IPI, has to do almost the same work as the INT/IRET mechanism and the
IPI mechanism combined. However, it does not need to change privilege levels like
the INT/IRET mechanism does. This explains why the Indirect IPI mechanism is still
faster than the sum of the IPI and INT/IRET mechanisms. Somewhat more interesting
is the fact that the extra page table switch associated with the Meltdown patch
mechanism does not seem to substantially degrade performance over the traditional
INT/IRET mechanism in this test.
More is revealed in the round-trip tests, summarized in Figure 7.6b and Table 7.1b.
In the case of the IPI and Indirect IPI mechanisms, the acknowledgment to complete
the test takes place over a shared memory interface. This is much faster than the
INT/IRET and Meltdown patch mechanisms which need to do another privilege mode
switch to return to ring 3. This is why the round-trip is only an average of 8% slower
than the one-way for the Indirect IPI but 26% slower for the INT/IRET. Additionally,
the results are beginning to indicate that the Meltdown patch impacts performance
compared to the standard INT/IRET mechanism.
The real-world tests illustrated in Figure 7.6c and Table 7.1c show that the Indirect
IPI mechanism used in KUCSBear was 3.48% slower than the INT/IRET mechanism
used in Bear. These tests also reveal the potential cost of the Meltdown patch method.
The need to flush the TLB before doing the kernel work significantly slows down the
kernel’s work to service the user’s request. Even with the small toy tasks completed
during this test, the Meltdown patch slowed down enough that even the Indirect IPI
mechanism was faster. This is consistent with the results of the 4G/4G project [118]
that inspired the Meltdown patches, which saw a performance cost as high as 30%.
162
IPI Indirect IPI INT/IRET Meltdown Patches
10 00
25 00
40 00
C lo
ck C
yc le
s
(a) One-way performance of different system call mechanisms. In other words, this measures the latency from when a user process requests kernel work until the kernel begins its work.
IPI Indirect IPI INT/IRET Meltdown Patches
20 00
40 00
60 00
C lo
ck C
yc le
s
(b) Round-trip performance of different system call mechanisms. In other words, this mea- sures the latency from when a user process requests kernel work until the process can resume after being acknowledged by the kernel.
IPI Indirect IPI INT/IRET Meltdown Patches
90 00
12 00 0
15 00 0
C lo
ck C
yc le
s
(c) Microbenchmarks that simply get an acknowledgement from the kernel do not accurately capture the implications of different system call mechanisms on performance. In particular, the mechanism used by Meltdown Patches slows kernel work dramatically.
Figure 7.6: Microbenchmarks exploring the performance implications of various sys- tem call mechanisms.
163
System Call Mechanism CPU Cycles
Max Min Average IPI 2932 1044 1306.4
Indirect IPI 4520 1764 2486.36 INT/IRET 3004 1096 1756.28
Meltdown Patches 3360 1048 1742.76
(a) In the one-way test, the IPI is the fastest system call mechanism while the Indirect IPI is the slowest. In this narrow test, the Meltdown Patched mechanism is not meaningfully different from the INT/IRET mechanism.
System Call Mechanism CPU Cycles
Max Min Average IPI 2988 1252 1710.72
Indirect IPI 4424 2088 2688.88 INT/IRET 6144 1484 2210
Meltdown Patches 4364 2192 2771.32
(b) The INT/IRET and Meltdown patched mechanisms suffer more than the IPI and Indirect IPI mechanisms in the round-trip test case because the former mechanisms require a second context switch while the latter use a shared memory interface to return control.
System Call Mechanism CPU Cycles
Max Min Average IPI 11396 9236 9753.8
Indirect IPI 12056 9984 10641.04 INT/IRET 13952 9552 10283.84
Meltdown Patches 16184 11036 11689.68
(c) With a test load on the kernel side, the performance cost of changing page tables on every system call is becoming more clear as the Meltdown patched mechanism slows considerably.
Table 7.1: Microbenchmarks exploring the performance implications of various system call mechanisms.
164
Test (CPU Cycles) Multiply (×109) Add (×109) Divide (×1010)
Bear Max 2.2238 1.3599 1.0747 Min 2.2232 1.3311 1.0744 Avg 2.2237 1.3391 1.0746
KUCSBear Max 2.2233 1.3593 1.1976 Min 2.2225 1.2739 1.0741 Avg 2.2228 1.3312 1.09892
Average Performance Cost -0.03% -0.59% 2.26%
Table 7.2: AIM9 Benchmark Suite [6] running on KUCSBear and the conventional Bear operating system. Each test type was run 100 times.
CPU Performance
The Bear operating system runs the industry-standard AIM9 benchmark test suite [6].
This is as a CPU intensive benchmark; it runs on a single core and executes a series of
CPU intensive add, multiply, or divide instructions. These tests are single-threaded
and therefore the number of cores running on the system does not have a meaning-
ful effect on the performance of these tests. As such, it is simple to compare the
performance of the conventional Bear operating system to that of KUCSBear.
The results of 100 iterations of the AIM9 test suite are summarized in Table 7.2.
In the case of the Multiply and Add tests, the performance costs observed in KUCS-
Bear are negligible. In the case of the Divide test, on the other hand, a 2.26% average
performance cost was observed. The explanation for the difference between the Mul-
tiply and Add tests and the Divide test may be that because the Divide test takes an
order of magnitude longer than the others, the small amount of additional overhead
incurred by KUCSBear’s Indirect IPI mechanism during timing interrupts begins to
show an effect.
Despite the small performance cost in the Divide case, these AIM9 tests show that
there is no dramatic difference in CPU performance between Bear and KUCSBear.
This makes sense because each system is simply running a user process on a core. The
only appreciable difference between the operating context of the two user processes is
165
that the KUCSBear process is running in ring 0 while the conventional Bear process
is running in ring 3. During general purpose computation, this should not affect CPU
performance.
Overall Performance
A malloc test [103] is used as an overall performance cost metric. The test is memory-
intensive, but also runs 100 processes and uses many system calls. As such, it exercises
the system call mechanism, scheduling mechanisms, kernel bookkeeping, and memory
systems. In addition, it can demonstrate the effect of multiple cores and multitasking
because it uses so many processes relative to the number of cores.
Figure 7.7 and Table 7.3 show the average cycle count over 100 trials of the
malloc benchmark test on Bear and KUCSBear for several core counts. Note that
this is specifically counting active user cores. In the case of the KUCSBear prototype,
there are n − 2 user cores on a system booted with n cores, because one is reserved
for the kernel core and one is reserved to run the conventional Bear OS to handle
hardware interrupts and unported drivers.
Several interesting trends emerge from Figure 7.7. The first is that additional
user cores after 4 actually slow performance of the benchmark rather than increase
it. This is likely due to contention over the kernel. Although Bear’s “big kernel
lock” and KUCSBear’s corresponding single kernel core may increase the likelihood
of contention, a kernel with fine-grained locking may not perform much better because
all the processes being tested are identical and would therefore fight over the same
locked kernel paths.
It seems that before 4 user cores, KUCSBear is dramatically slower than Bear.
However, an interesting pattern exists in this region of the data. The performance
with two KUCSBear user cores is nearly identical (0.8% faster) to the performance
with one Bear user core. The same is true for the relationship between three KUCS-
166
User Core Bear KUCSBear Performance Count (Cycles ×109) (Cycles ×109) Cost
1 11.2302† Not Measured* N/A 2 5.6779 11.1364† 96.14% 3 3.8218 5.6648 48.22% 4 2.8942 3.1680 9.46% 5 2.9426 3.2258 9.62% 6 2.9948 3.3208 7.88% 7 3.0465 N/A‡ N/A 8 3.1004 N/A‡ N/A
* Stability issues combined with a very long run-time will not allow the full test to run with 1 user core on KUCSBear. † These values are single runs, not the average of 100 trials,
due to long run times of the test. ‡ KUCSBear reserves 2 cores for system use, so trials using
more than 6 user cores are not possible.
Table 7.3: The average cycle count required to run the 100 process malloc test [103] on Bear and KUCSBear with different numbers of active user cores.
1 2 3 4 5 6 7 8
3e +1 0
4e +1 0
5e +1 0
6e +1 0
7e +1 0
User Cores
C lo
ck C
yc le
s
Bear KUCSBear
Figure 7.7: The average cycle count required to run the 100 process malloc test [103] on Bear and KUCSBear with different numbers of active user cores. KUCSBear can only achieve a maximum of 6 user cores because one core is reserved for the kernel and a second is reserved for legacy functions.
167
Bear user cores and two Bear user cores; KUCSBear is 0.2% faster in this case.
Combined with the close relationship and relatively low performance costs seen in
user core counts of four and above, this pattern suggests that there is some other
factor at play.
Although this data leaves some questions that would require further study of
the prototype to understand fully, the behavior at the higher user core ranges is
consistent enough to make a fair estimate of the performance cost of the KUCSBear
prototype. As implemented, KUCSBear imposes less than a 10% performance cost
for a particular user task at scale.
Another important consideration is the fact that any KUCS operating system
will reserve at least one core for the kernel, meaning that there will be one fewer
cores available to run user processes. This could impact performance greatly for a
workload that makes effective use of all cores. The malloc test does not seem like
a good one to estimate this effect, because decreasing performance with more cores
suggests that it cannot make good use of all of the available cores. However, according
to Amdahl’s Law [12], even the most highly optimized and parallelized workload will
experience a “diminishing return” as the available core count increases. Therefore,
in the future (as hardware continues to scale and offer more and more processors)
removing any constant number of cores from those available will not significantly
decrease the performance of any particular application.
7.3.3 Future Work
Increasing the Performance of KUCSBear
The 3.48% performance cost of the system call mechanism cannot explain the ∼10%
overall measured performance cost. It cannot even explain a third of that cost, since
only a small percentage of the running time of the test should be spent actually
exercising that specific mechanism. Further study could identify the source of this
168
performance cost and work to reduce it.
One possible contributing factor for the performance cost of KUCSBear is the
symmetrical nature of hardware resources in the SMP chip being used. In particular,
caches and shared memory or peripheral busses are optimized for symmetric use by
all cores. Using the cores asymmetrically may result in suboptimal performance of
these hardware facilities. Unfortunately, this could only be resolved at the hardware
development stage.
KUCSBear also uses virtualization on all cores. This may pose an additional per-
formance cost compared to Bear which was tested without any virtualization enabled.
However, this cost is likely to be low, as suggested in Section 4.4 where ExOShim was
measured to impose just a 0.86% performance cost.
Hardware is not the only place where future KUCS implementations could find
better performance. There are many places in KUCSBear where future efforts could
replace synchronous tasks with asynchronous ones. For example, the scheduling mech-
anism in KUCSBear is implemented synchronously. When a process receives a timer
interrupt, it must ask the kernel for the next process to run and wait for the answer.
The kernel handles tasks in the order that they are received, so the process may
have to wait some time for the kernel to clear its queue and handle the scheduling
request. This is inconsistent with the behavior of a conventional operating system
such as Bear, in which all cores requesting work fight for the lock and the order in
which they begin trying for the lock is unrelated to the order in which they acquire
it. Still, a more advanced KUCS operating system implementation could have the
kernel pre-load scheduling events while the process is running, greatly reducing the
cost of a timer interrupt on the user core.
Additionally, it is possible that the kernel’s event handling algorithm itself can
be optimized. For example, handling events in some order other that the order that
they are received could avoid the situation in which a process that wants to schedule
169
must wait for other work to be done.
Other than the small costs of the relatively rare system call and the virtualiza-
tion extensions, there is no clear architectural reason for even the relatively small
performance cost measured in KUCSBear. This separates KUCSBear from the di-
versification techniques described in Chapters 5 and 6 where loss of code locality can
be expected to decrease the effectiveness of hardware memory caching mechanisms.
The lack of a clear architectural explanation for the performance cost invites further
research into the design choices mentioned here as well as others, and how a KUCS
operating system can be implemented most efficiently.
Enhancing the Prototype
Beyond increasing the performance of the KUCSBear prototype, future work could
seek to increase the robustness and feature set of KUCSBear. The first task would be
to eliminate the single reserved legacy core running an instance of the conventional
Bear operating system. This core is running unported drivers and handling any
hardware interrupts.
In order to have all cores running KUCSBear, several drivers would need to be
ported to run as ring 0 processes. This is a straightforward task. In fact, nothing
in user-space needs to change. The only changes required in user-space to make a
user process cooperate with KUCSBear happen in the library layer. As implemented
currently, even the compilation is identical for processes that will be run in ring 0
on a remote core and processes that will be run in ring 3 and cohabit a core with
a kernel instance. Only at load-time is any distinction made between the two types
of process. In the system call library, the process checks a variable to see whether it
should use an IPI mechanism or an INT/IRET mechanism to signal the kernel. This
variable is set at load time. This variable also determines whether the process should
write its message to the ring buffer located in its shared memory interface with the
170
kernel. The variable is set by the kernel at load-time.
Interestingly, because the Indirect IPI and INT/IRET system call mechanisms each
begin by executing a local int instruction on core, future work may be able to develop
a loader that can run a particular user process in ring 3 with a kernel mapped into
its context or in ring 0 with only a KCUIHL without any difference in the user code.
The other challenge for this will be accessing the process’ memory without using the
shared memory interface, but this could be overcome since the kernel can manipulate
memory as needed. This possible extension would bring the “red-pill” vs. “blue-
pill” debate from virtualization [144] into the context of the kernel- and user-space
relationship.
Handling interrupts without a legacy Bear core will also require some modifica-
tion to the KUCSBear kernel. On Bear, like most conventional operating systems,
the kernel is only ever run in response to an interrupt. In other words, the entire
kernel is like one large interrupt handler; including the fact that it does not allow
interrupt delivery while it is running. For this reason, hardware interrupt handlers
make assumptions about the state saving and restoration needed to go from the ring
3 context where the interrupt will be delivered to the kernel context where it will be
serviced, and back. With the KUCSBear kernel, the kernel core is always executing
code in the kernel and the interrupt handler only logs an event that the main kernel
code can then service. In order to handle legacy hardware interrupts in KUCSBear,
the interrupt handling routines for these interrupts would need to be rewritten to
change and restore context from a ring 0 kernel context rather than from a ring 3
user context. In addition, the interrupt would have to be logged and later retrieved
and serviced like any other kernel event. This is a departure from the legacy paradigm
in which the interrupt is serviced in the handler. Unless KUCSBear is made com-
pletely reentrant, servicing interrupts in an interrupt handler (rather than simply
logging them) on the kernel core could corrupt kernel state.
171
Finally, the prototype could use more debugging in order to increase its stability.
Although it can run many thousands of processes, there are potential timing and
memory integrity issues in the prototype that keep it from being stable enough to
run indefinitely.
Fine-Grained Locking
The original Bear operating system uses a single kernel lock. This is a mechanism
that ensures that only one core can enter the kernel at any given time [107] and is in
contrast with the most modern operating systems which implement many separately-
locked paths so that multiple cores can do kernel work simultaneously if the tasks do
not compete for resources [155].
KUCSBear uses the same kernel lock to restrict access to the kernel resources
between the KUCS kernel core and the reserved legacy Bear OS core. However,
KUCS operating systems will struggle to take advantage of fine-grained locking. Using
a single core for the kernel implies that only one thread of execution can be running
kernel code at any particular time. This could impose significant performance costs
on certain types of workloads. On a machine with infinite cores, this would not be an
issue because one core could be reserved for each independently locked path through
the kernel. Future work could examine the performance implications of trading user
cores for independent kernel cores. This tradeoff may increase or decrease performance
depending on the type of workload being handled and the number of cores available.
Porting Other Kernels to KUCS
The security benefits of KUCS make it an attractive proposition for real-world operat-
ing systems, especially for hardware that is susceptible to the Meltdown vulnerability
but expensive to replace. In addition, the performance cost is moderate as measured
at less than 10%. When contrasted to the potentially high costs of current Meltdown
172
patches, this 10% seems acceptable. As such, future efforts may be interested in im-
plementing a KUCS design on larger, more stable, and more fully featured operating
systems.
The implementation of a major redesign of an operating system, as would be
required to port a major kernel to a KUCS operating system design, is a complex
endeavor. It is vital to have a plan to approach this huge software engineering task so
that it can be developed in stages that can be parallelized where possible. Fortunately,
the experience of developing KUCSBear has led to a preliminary decomposition of
steps for implementing a KUCS design on an arbitrary operating system.
1. Initial IPI testing The first step consists of an exercise that will guide the
system developers in some of the essential system capabilities that will be used
in the later steps. In particular, the task is to have two cores interact in the
following way:
“A non-locked kernel-level process on core X sends an IPI to core Y , then
monitors a particular memory location, looking for a new value. Core Y receives
the IPI and displays that it has received it. In addition, it writes a confirmation
to the shared memory location, freeing X to continue with its own execution.”
This process can be destructive. It does not need to preserve system state. The
purpose of the task is to get the system developers familiar with the multicore
support on the target operating system, sending and receiving IPIs, and using
shared memory interfaces to communicate between cores. These tasks are the
foundation of any KUCS implementation.
2. Load a page table with the process but no kernel This step involves
generating an address space for a remote process. Such an address space will
contain virtual memory mappings to the process code and data, plus all of the
other mappings it may need, but not to the kernel.
173
Generating this address space may require more or less work depending on the
robustness and flexibility of the existing virtual memory system in the target
operating system. Unfortunately, many operating systems are written so that
their virtual memory operations act on the currently loaded set of page tables.
This makes sense for most tasks because the operating system is loaded into
every context, so any context can be modified by the operating system through
the mappings that it contains. In this case, the operating system needs to
operate on a context where it is not local (unless the implementation goes
through the normal loading process and then later unmaps the kernel).
With a sufficiently flexible virtual memory layer, the loader and linker must be
modified to generate remote processes in addition to standard ones. The best
method for accomplishing this will be dependent on the target system.
3. Pin tasks to cores A foundational idea in the KUCS operating system design
is using the processor’s cores asymmetrically. Assigning specific tasks to specific
cores is functionality that may or may not be present in the target operating
system. As such, this step requires using (or modifying) the target operat-
ing system’s multicore management system in order to assign specific tasks to
specific processors. This task may be trivial or very difficult, depending on the
capability, flexibility, and robustness of the existing multicore management code
in the host operating system.
4. Implement a system call In order to communicate between the kernel and
remote processes for system calls, the implementation needs to make accom-
modations for passing data between the two. This is likely to take the form
of a shared memory interface in which the two entities mutually agree upon a
location at which the relevant arguments will be stored and retrieved.
Interrupts sent from the remote core to the kernel core or kernel polling of the
174
relevant memory can be used to notify the kernel of a new system call from the
remote process. If the former is used, it will require that the interrupt han-
dling mechanisms described in the first step are implemented completely. This
includes an interrupt handling mechanism (KCUIHL) loaded into the remote
process.
As long as the loader is sufficiently flexible, compiling the interrupt handling
library should be done in a separate file and then loaded into the address space
of the remote process.
5. Run a “Hello World” user program Beginning to scale up from the first
system call, the developers should port other system calls until a simple process
can be loaded and run on the remote core. For a particular system call, changes
may need to be made in the user-space libraries or kernel system call handling
code itself in order to accommodate the KUCS design.
Note that even for a simple hello world program, there may be dozens of system
calls necessary.
6. Schedule between user processes With a process that can be observed
and interacted with, the next task would be to schedule between two of these
processes. Any method of accomplishing scheduling will require robust interrupt
handling on the user and kernel cores. Additionally, scheduling will begin to
reveal issues with the design or implementation that were not an issue with
the special case of running a single process. Section 7.2.5 examined multiple
possible methods for scheduling in the context of KUCSBear.
7. Port all system calls With all of the core components implemented, the
system developers have the tools to port all system calls and user processes to
be compatible with the KUCS kernel. Additionally, they can allow arbitrary
175
scheduling with n processes. This will be a step in which major stability issues
are likely to surface, and may take a large debugging effort.
8. Add virtualization Finally, the virtualization layer can be implemented. The
virtualization layer is largely passive and so it can be added after the regular
KUCS system is stable. However, developers may find certain virtualization
features can assist in debugging. For this reason, they may wish to complete
this step early in the process.
Note that throughout the implementation plan, steps are taken to run KUCS type
processes alongside conventional processes that contain operating system mappings.
This is extra work in the beginning of the process, but facilitates debugging at the
end of the process. It is unlikely that even the most skilled system programmers
could manage to implement an entire KUCS operating system without errors on the
first attempt, and it is very helpful to have processes running under the standard
paradigm that the developers can “trust.”
Possible Hardware Extensions
New processor designs could go a long way towards supporting KUCS operating
systems. Possible extensions include:
• Optimizing cache, bus, and interrupt architectures for asymmetrical multipro-
cessing architectures.
• Providing a hardware mechanism to accept interrupts in a FIFO manner rather
than through a vector.
• Implement hardware interrupt source recording.
• Implement non-readable memory in the regular page tables (in order to facilitate
hiding the KCUIHL).
176
Of course, a hardware designer that is looking especially for ways to support
a KUCS operating system could implement any number of creative solutions. For
example, a master-slave paradigm that could apply to kernel and user cores may
enable enhanced security features without requiring software mechanisms such as
hypervisor intervention.
7.4 KUCS: Conclusion
Over the past several decades, few have attempted to change the traditional operating
system design methods. However, the symmetric multiprocessing paradigm that is
used in conventional kernel design may be imposing unnecessary limits on the security
and performance of operating systems. KUCS is an alternative kernel design paradigm
that uses asymmetric multiprocessing to offer possibilities for increased security and
performance.
KUCS abandons the traditional weakly-separated kernel and user virtual address
spaces in favor of a strongly separated kernel- and user-space. In particular, it ex-
ecutes the kernel on one core and applications on other cores, with the two pieces
of software never sharing hardware. System calls and other communication between
the kernel and the application is accomplished with IPIs instead of the traditional
INT/IRET mechanism. Finally, the processor’s virtualization layer is be utilized on a
per-core basis to protect the hardware from malicious processes.
KUCSBear is a prototype operating system that ported the Bear microkernel to
use the KUCS kernel design paradigm. It offers several contributions to the current
state of the art. Divorcing virtual address spaces enables complete sandboxing of
each user application. Redefining “user-space” as a location rather than a privilege
level allows for device drivers with the security of user-space encapsulation and the
performance of kernel modules. Simultaneous operation of the kernel and applications
177
allows the kernel to accomplish its own work in addition to servicing the remaining
user cores. The asymmetric multiprocessing paradigm allows for uniquely fine-grained
security policy enforcement enabled by per-core virtualization.
There still much work to be done in evaluating the full potential of the KUCS
kernel design. While KUCSBear provides a proof-of-concept, future efforts can im-
plement watchdog security monitors in the kernel, make ring 3 hardware protection
mechanisms available for use within applications, and offer more support for device
drivers.
KUCSBear was measured to have a performance overhead of less than 10% com-
pared to the conventional Bear operating system. Although a small percentage of
this cost is due to a the system call mechanism, there is no clear architectural reason
for the bulk of this cost. Future work would be required to understand the role of
various implementation design decisions in this performance cost. In addition, future
KUCS operating systems could utilize novel techniques such as asynchronous system
calls and direct mapping of interrupts to device drivers in order to further increase
performance.
The implications of the prototype and its performance measurements are espe-
cially interesting in the face of the recent Meltdown vulnerability [109]. The patches
for Meltdown increase the overhead of the system call mechanism and only new hard-
ware can mitigate the risk without a meaningful performance cost. Although a full
study of the performance cost of Meltdown patches has not yet been conducted, mi-
crobenchmarks in this work suggest that it could slow certain system events by as
much as 25%. This is consistent with the significant performance costs seen in the
4G/4G Linux Split patch [118] from which the Meltdown patch mechanism was in-
spired. The prospect of an alternative operating system design that is not susceptible
to Meltdown with less than 10% performance cost and room to get faster is very
interesting in the face of millions of processors that need to be replaced or suffer a
178
potentially significant performance cost.
There are many outstanding questions regarding the KUCS kernel design and its
application to modern hardware. Whether or not these questions are researched in the
future, KUCSBear offers an interesting case study in the sparse world of alternative
operating system designs.
179
Chapter 8
Conclusion
The pervasive and diverse problem of privilege escalation motivated the research pre-
sented in this thesis. An analysis of the existing solutions to the various types of
privilege escalation mechanisms (Chapter 3) revealed a host of disparate techniques,
but none has gained traction in commodity software due to performance costs, com-
patibility or usability issues, and/or specialty hardware requirements.
This thesis contributes four research efforts that seek to mitigate privilege es-
calation threats. The KPLT (Chapter 5) and Überdiversity (Chapter 6) use non-
determinism to mitigate the risk of return-oriented programming attacks, especially
at the kernel level. ExOShim (Chapter 4) uses the virtualization features of modern
hardware to provide an operating system protection mechanism that can remove the
threat of kernel-level memory disclosures. Finally, the KUCS operating system de-
sign (Chapter 7) describes a new paradigm for mapping the software components of
a computing system onto existing hardware in order to mitigate the threat of kernel
code injection and ret2usr attacks, and defeat the Meltdown vulnerability.
The KPLT uses virtual memory indirection to map common kernel functionality at
unique and randomized addresses on a per-process basis. This models the behavior of
dynamically-linked libraries for the kernel itself. An operating system using the KPLT
180
inhibits the development of kernel-level return-oriented programming by shuffling the
location of kernel gadgets in each process. Due to the inability to utilize global
paging between processes (since the kernel addresses are no longer global), a moderate
performance cost of 16% was measured.
Überdiversity is a study of load-time randomization. It presents a prototype
load-time diversification scheme that uses more of the address space than previous
implementations, virtualizes the hypervisor code as well as the user and kernel code,
and interleaves user and kernel sections in order to maximize the randomness of the
system. Additionally, the study discusses the algorithms used to generate random
address spaces. In particular, it shows that many algorithms produce some address
spaces with higher probability than others, and presents an algorithm that produces
all address spaces with equal probability. Finally, it examines the quantification of
randomization schemes and attempts to clarify the term “entropy” while contributing
a novel quantification metric: “program variants.” A modest performance cost of
only 6% was measured for the Überdiversity prototype implementation, indicating
that more thorough randomization methods are not unreasonably slow, and could be
used in more dramatic ways in commodity software.
ExOShim is a technique in which the operating system deploys the virtualization
features of its hardware in order to mark its code pages as execute-only, thus defeating
the risk of kernel-code memory disclosures. Although ExOShim was designed to be
deployed by the kernel, it was carefully configured so that it provides protection that
cannot be modified, disabled, or hijacked by an attacker. The measured performance
cost was minuscule, at just 0.86%. Additionally, any operating system that does not
initialize the virtualization capabilities of its hardware is susceptible to virtualization-
based rootkits. With ExOShim, the virtualization features are preemptively deployed
to protect the kernel rather than laying in wait to help an attacker compromise it.
181
KUCS is an operating system design that isolates the kernel from the user processes
by running them on separate CPU cores. The process is loaded in an address space
without the kernel, so the kernel does not reside anywhere in the process’ context,
rather than simply hiding behind a privilege bit. Processes communicate with the
kernel via inter-processor interrupts, and the kernel returns data to the processes
via shared memory interfaces. Although there was a measured performance cost of
∼10% with the prototype implementation, future efforts could take steps to reduce
that cost. In fact, the design offers many opportunities to increase performance over
the status quo operating system design.
In spite of its organization, the thesis contributes more than just four unique ef-
forts. They compliment each other to form a complete picture of a possible future
hardened kernel design. Chapter 7 describes how ExOShim-style virtualization tech-
niques can augment the protections offered by the KUCS operating system design. In
addition, the randomization techniques described in Chapter 5 and Chapter 6 can also
strengthen a KUCS-designed kernel. Überdiversity could be deployed on each core to
randomize each user process and even the kernel-controlled interrupt handling code
and other memory regions on the user cores. Finally, a KPLT could allow for several
diverse kernel images to occupy the kernel core at different times. A KUCS kernel
design utilizing these techniques could offer a performant and secure alternative to
conventional operating systems.
In summary, this thesis shows not only how different research efforts can address
specific privilege escalation threats, but also how they can compliment each other to
offer a hardened kernel design for the future.
182
Bibliography
[1] Building a Secure System using TrustZone Technology. Technical report, ARM.
[2] CVE Details. https://www.cvedetails.com/vulnerabilities-by-types.
php. Accessed: 1/29/2018.
[3] Address Space Layout Randomization. Technical report, PaX Team, 2001.
[4] CWE-639: Authorization Bypass Through User-Controlled Key, September
2008.
[5] Microgadgets: Size Does Matter in Turing-Complete Return-Oriented Program-
ming. In Presented as part of the 6th USENIX Workshop on Offensive Tech-
nologies, Berkeley, CA, 2012. USENIX.
[6] AIM Independent Resource Benchmark, February 2013.
[7] CVE-2013-2094, May 2013.
[8] OS X Mavericks Core Technologies Overview. Technical report, Apple, October
2013.
[9] CVE-2016-0728, January 2016.
[10] Mike Accetta, Robert Baron, William Bolosky, David Golub, Richard Rashid,
Avadis Tevanian, and Michael Young. Mach: A New Kernel Foundation for
UNIX Development. pages 93–112, 1986.
183
[11] AMD. AMD64 Architecture Programmer’s Manual Volume 2: System Program-
ming, October 2013.
[12] Gene M. Amdahl. Validity of the Single Processor Approach to Achieving Large
Scale Computing Capabilities. In Proceedings of the April 18-20, 1967, Spring
Joint Computer Conference, AFIPS ’67 (Spring), pages 483–485, New York,
NY, USA, 1967. ACM.
[13] Algirdas Avizienis and Liming Chen. On the Implementation of N-version Pro-
gramming for Software Fault Tolerance during Execution. In Proc. the First
IEEE-CS International Computer Software and Applications Conference (COM
PSAC 77), Chicago, 1977.
[14] Ahmed M. Azab, Peng Ning, Jitesh Shah, Quan Chen, Rohan Bhutkar, Gu-
ruprasad Ganesh, Jia Ma, and Wenbo Shen. Hypervision Across Worlds: Real-
time Kernel Protection from the ARM TrustZone Secure World. In Proceedings
of the 2014 ACM SIGSAC Conference on Computer and Communications Se-
curity, CCS ’14, pages 90–102, New York, NY, USA, 2014. ACM.
[15] Michael Backes, Thorsten Holz, Benjamin Kollenda, Philipp Koppe, Stefan
Nürnberger, and Jannik Pewny. You Can Run but You Can’T Read: Pre-
venting Disclosure Exploits in Executable Code. In Proceedings of the 2014
ACM SIGSAC Conference on Computer and Communications Security, CCS
’14, pages 1342–1353, New York, NY, USA, 2014. ACM.
[16] Saisanthosh Balakrishnan, Ravi Rajwar, Mike Upton, and Konrad Lai. The
Impact of Performance Asymmetry in Emerging Multicore Architectures.
SIGARCH Comput. Archit. News, 33(2):506–517, May 2005.
[17] Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex
Ho, Rolf Neugebauer, Ian Pratt, and Andrew Warfield. Xen and the Art of
184
Virtualization. In Proceedings of the Nineteenth ACM Symposium on Operating
Systems Principles, SOSP ’03, pages 164–177, New York, NY, USA, 2003. ACM.
[18] Christoph Baumann, Bernhard Beckert, Holger Blasum, and Thorsten Bormer.
Formal Verification of a Microkernel Used in Dependable Software Systems. In
Bettina Buth, Gerd Rabe, and Till Seyfarth, editors, Computer Safety, Relia-
bility, and Security, volume 5775 of Lecture Notes in Computer Science, pages
187–200. Springer Berlin Heidelberg, 2009.
[19] Sandeep Bhatkar, R. Sekar, and Daniel C. DuVarney. Efficient techniques for
comprehensive protection from memory error exploits. In Proceedings of the
14th Conference on USENIX Security Symposium - Volume 14, SSYM’05, pages
17–17, Berkeley, CA, USA, 2005. USENIX Association.
[20] Kenneth J Biba. Integrity considerations for secure computer systems. Technical
report, DTIC Document, 1977.
[21] Andrea Bittau, Adam Belay, Ali Mashtizadeh, David Mazières, and Dan Boneh.
Hacking blind. In Proceedings of the 2014 IEEE Symposium on Security and
Privacy, SP ’14, pages 227–242, Washington, DC, USA, 2014. IEEE Computer
Society.
[22] Silas Boyd-Wickizer, Haibo Chen, Rong Chen, Yandong Mao, Frans Kaashoek,
Robert Morris, Aleksey Pesterev, Lex Stein, Ming Wu, Yuehua Dai, Yang
Zhang, and Zheng Zhang. Corey: An Operating System for Many Cores. In
Proceedings of the 8th USENIX Conference on Operating Systems Design and
Implementation, OSDI’08, pages 43–57, Berkeley, CA, USA, 2008. USENIX
Association.
[23] Alfred Bratterud, Alf-Andre Walla, Paal E Engelstad, Kyrre Begnum, et al.
IncludeOS: A minimal, resource efficient unikernel for cloud services. In 2015
185
IEEE 7th International Conference on Cloud Computing Technology and Sci-
ence (CloudCom), pages 250–257. IEEE, 2015.
[24] Sergey Bratus, Nihal DCunha, Evan Sparks, and Sean W Smith. Toctou, traps,
and trusted computing. In International Conference on Trusted Computing,
pages 14–32. Springer, 2008.
[25] Sergey Bratus, Michael E. Locasto, Ashwin Ramaswamy, and Sean W. Smith.
VM-based Security Overkill: A Lament for Applied Systems Security Research.
In Proceedings of the 2010 Workshop on New Security Paradigms, NSPW’10,
pages 51–60, New York, NY, USA, 2010. ACM.
[26] Scott Brookes, Robert Denz, Martin Osterloh, and Stephen Taylor. ExOShim:
Preventing Memory Disclosure using Execute-Only Kernel Code. In Proceed-
ings of the 11th International Conference on Cyber Warfare and Security, IC-
CWS’16, pages 56–66, April 2016.
[27] Scott Brookes, Robert Denz, Martin Osterloh, and Stephen Taylor. ExOShim:
Preventing Memory Disclosure using Execute-Only Kernel Code. International
Journal of Information and Computer Security (IJICS), 2018, In Press.
[28] Scott Brookes, Martin Osterloh, Robert Denz, and Stephen Taylor. The KPLT:
The Kernel as a shared object. In Military Communications Conference, MIL-
COM 2015 - 2015 IEEE, pages 954–959, Oct 2015.
[29] Scott Brookes, Martin Osterloh, Robert Denz, and Stephen Taylor.
Überdiversity: Exploring the Limit of Load-Time Software Diversification.
Technical report, Thayer School of Engineering at Dartmouth College, April
2018.
[30] Scott Brookes and Stephen Taylor. Containing a Confused Deputy on x86: A
Survey of Privilege Escalation Mitigation Techniques. IJACSA, April 2016.
186
[31] Scott Brookes and Stephen Taylor. Rethinking operating system design: Asym-
metric multiprocessing for security and performance. In Proceedings of the 2016
New Security Paradigms Workshop, NSPW ’16, pages 68–79, New York, NY,
USA, 2016. ACM.
[32] Zach Brown. Asynchronous System Calls. In Proceedings of the Ottawa Linux
Symposium (OLS), pages 81–85, 2007.
[33] Erik Buchanan, Ryan Roemer, Stefan Savage, and Hovav Shacham. Return-
Oriented Programming: Exploitation without Code Injection, 2008.
[34] c0ntex. Bypassing non-executable-stack during exploitation using return-to-
libc. http://www.open-security.org/texts/4.
[35] Xi Chen, Asia Slowinska, Dennis Andriesse, Herbert Bos, and Cristiano Giuf-
frida. Stackarmor: Comprehensive protection from stack-based memory error
vulnerabilities for binaries. In NDSS Symposium 2015, San Diego, California,
2015.
[36] Monica Chew and Dawn Song. Mitigating buffer overflows by operating system
randomization. Technical report, 2002.
[37] Andy Chou, Junfeng Yang, Benjamin Chelf, Seth Hallem, and Dawson En-
gler. An Empirical Study of Operating Systems Errors. In Proceedings of the
Eighteenth ACM Symposium on Operating Systems Principles, SOSP ’01, pages
73–88, New York, NY, USA, 2001. ACM.
[38] Frederick B Cohen. Operating system protection through program evolution.
Computers & Security, 12(6):565–584, 1993.
[39] TIS Committee. Tool Interface Stadard (TIS) Executable and Linking Format
(ELF) Specification, May 1995.
187
[40] F. J. Corbató and V. A. Vyssotsky. Introduction and Overview of the Multics
System. In Proceedings of the November 30–December 1, 1965, Fall Joint Com-
puter Conference, Part I, AFIPS ’65 (Fall, part I), pages 185–196, New York,
NY, USA, 1965. ACM.
[41] Crispin Cowan. Non-Executable Stack, 1997.
[42] Crispin Cowan, Calton Pu, Dave Maier, Heather Hintony, Jonathan Walpole,
Peat Bakke, Steve Beattie, Aaron Grier, Perry Wagle, and Qian Zhang. Stack-
Guard: Automatic Adaptive Detection and Prevention of Buffer-overflow At-
tacks. In Proceedings of the 7th Conference on USENIX Security Symposium
- Volume 7, SSYM’98, pages 5–5, Berkeley, CA, USA, 1998. USENIX Associa-
tion.
[43] S. Crane, Ch. Liebchen, A. Homescu, L. Davi, P. Larsen, AR Sadeghi, S. Brun-
thaler, and M. Franz. Readactor: Practical Code Randomization Resilient to
Memory Disclosure. In Proceedings of the 2015 IEEE Symposium on Security
and Privacy, 2015.
[44] Paul Crawford. Linux Watchdog Daemon - Overview. http://www.sat.
dundee.ac.uk/psc/watchdog/watchdog-background.html, January 2016.
[45] J. Criswell, N. Dautenhahn, and V. Adve. KCoFI: Complete Control-Flow
Integrity for Commodity Operating System Kernels. In Proceedings of the 2014
IEEE Symposium on Security and Privacy, SP’14, pages 292–307, May 2014.
[46] John Criswell, Andrew Lenharth, Dinakar Dhurjati, and Vikram Adve. Secure
Virtual Architecture: A Safe Execution Environment for Commodity Operating
Systems. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operat-
ing Systems Principles, SOSP ’07, pages 351–366, New York, NY, USA, 2007.
ACM.
188
[47] Robert C Daley and Jack B Dennis. Virtual memory, processes, and sharing in
Multics. Communications of the ACM, 11(5):306–312, 1968.
[48] Lucas Davi, Alexandra Dmitrienko, Ahmad-Reza Sadeghi, and Marcel
Winandy. Privilege Escalation Attacks on Android. In Mike Burmester, Gene
Tsudik, Spyros Magliveras, and Ivana Ili, editors, Information Security, volume
6531 of Lecture Notes in Computer Science, pages 346–360. Springer Berlin
Heidelberg, 2011.
[49] Lucas Davi, Christopher Liebchen, Ahmad-Reza Sadeghi, Kevin Z Snow, and
Fabian Monrose. Isomeron: Code randomization resilient to (just-in-time)
return-oriented programming. Proc. 22nd Network and Distributed Systems
Security Sym.(NDSS), 2015.
[50] Lucas Vincenzo Davi, Alexandra Dmitrienko, Stefan Nürnberger, and Ahmad-
Reza Sadeghi. Gadge me if you can: Secure and efficient ad-hoc instruction-
level randomization for x86 and arm. In Proceedings of the 8th ACM SIGSAC
Symposium on Information, Computer and Communications Security, ASIA
CCS ’13, pages 299–310, New York, NY, USA, 2013. ACM.
[51] Robert Denz. Securing the Cloud with Utility Virtual Machines. PhD thesis,
Thayer School of Engineering at Dartmouth College, July 2016.
[52] Robert Denz, Scott Brookes, Martin Osterloh, Stephen Kuhn, and Stephen Tay-
lor. Symmetric multiprocessing from boot to virtualization. Software: Practice
and Experience, 48(3):681–718.
[53] Richard Durstenfeld. Algorithm 235: Random permutation. Commun. ACM,
7(7):420–, July 1964.
[54] Jake Edge. Kernel address space randomization, October 2013.
189
[55] Shawn Embleton, Sherri Sparks, and Cliff Zou. Smm rootkits: A new breed
of os independent malware. In Proceedings of the 4th International Conference
on Security and Privacy in Communication Netowrks, SecureComm ’08, pages
11:1–11:12, New York, NY, USA, 2008. ACM.
[56] D. R. Engler, M. F. Kaashoek, and J. O’Toole, Jr. Exokernel: An Operating
System Architecture for Application-level Resource Management. In Proceed-
ings of the Fifteenth ACM Symposium on Operating Systems Principles, SOSP
’95, pages 251–266, New York, NY, USA, 1995. ACM.
[57] Philip Enslow, Jr. Multiprocessor Organization – a Survey. ACM Comput.
Surv., 9(1):103–129, March 1977.
[58] Úlfar Erlingsson and Fred B. Schneider. SASI Enforcement of Security Poli-
cies: A Retrospective. In Proceedings of the 1999 Workshop on New Security
Paradigms, NSPW ’99, pages 87–95, New York, NY, USA, 2000. ACM.
[59] Isaac Evans, Sam Fingeret, Julián González, Ulziibayar Otgonbaatar, Tiffany
Tang, Howard Shrobe, Stelios Sidiroglou-Douskos, Martin Rinard, and Hamed
Okhravi. Missing the point (er): On the effectiveness of code pointer integrity1.
2015.
[60] William Feller. An Introduction to Probability Theory and Its Applications,
volume 1. Wiley, January 1968.
[61] Peter Ferrie. Attacks on more virtual machine emulators. Symantec Technology
Exchange, 2007.
[62] Stephen Fischer. Supervisor Mode Execution Protection. NSA Trusted Com-
puting Conference and Exposition, 2011.
190
[63] Ronald Aylmer Fisher, Frank Yates, et al. Statistical tables for biological,
agricultural and medical research. Statistical tables for biological, agricultural
and medical research., (Ed. 3.), 1949.
[64] S. Forrest, A. Somayaji, and D. Ackley. Building Diverse Computer Systems. In
Proceedings of the 6th Workshop on Hot Topics in Operating Systems (HotOS-
VI), HOTOS ’97, pages 67–, Washington, DC, USA, 1997. IEEE Computer
Society.
[65] Jason Franklin, Arvind Seshadri, Ning Qu, Sagar Chaki, and Anupam Datta.
Attacking, repairing, and verifying SecVisor: A retrospective on the security of
a hypervisor. Technical report, Carnegie Mellon University, 2008.
[66] Archana Ganapathi, Viji Ganapathi, and David Patterson. Windows XP Kernel
Crash Analysis. In Proceedings of the 20th Conference on Large Installation Sys-
tem Administration, LISA ’06, pages 12–12, Berkeley, CA, USA, 2006. USENIX
Association.
[67] Xinyang Ge, Hayawardh Vijayakumar, and Trent Jaeger. Sprobes: En-
forcing kernel code integrity on the trustzone architecture. arXiv preprint
arXiv:1410.7747, 2014.
[68] Jason Gionta, William Enck, and Peng Ning. HideM: Protecting the Contents
of Userspace Memory in the Face of Disclosure Vulnerabilities. In Proceedings
of the 5th ACM Conference on Data and Application Security and Privacy,
CODASPY ’15, pages 325–336, New York, NY, USA, 2015. ACM.
[69] Cristiano Giuffrida, Anton Kuijsten, and Andrew S. Tanenbaum. Enhanced
Operating System Security Through Efficient and Fine-grained Address Space
Randomization. In Presented as part of the 21st USENIX Security Symposium
(USENIX Security 12), pages 475–490, Bellevue, WA, 2012. USENIX.
191
[70] Robert P. Goldberg. Survey of Virtual Machine Research. Computer, 7(9):34–
45, September 1974.
[71] Norm Hardy. The confused deputy: (or why capabilities might have been in-
vented). SIGOPS Oper. Syst. Rev., 22(4):36–38, October 1988.
[72] Jorrit N Herder. Towards a true microkernel operating system. PhD thesis,
Vrije Universiteit Amsterdam, February 2005.
[73] Jorrit N. Herder, Herbert Bos, Ben Gras, Philip Homburg, and Andrew S.
Tanenbaum. MINIX 3: A Highly Reliable, Self-repairing Operating System.
SIGOPS Oper. Syst. Rev., 40(3):80–89, July 2006.
[74] Dan Hildebrand. An Architectural Overview of QNX. In Proceedings of the
Workshop on Micro-kernels and Other Kernel Architectures, pages 113–126,
Berkeley, CA, USA, 1992. USENIX Association.
[75] J. Hiser, A. Nguyen-Tuong, M. Co, M. Hall, and J. W. Davidson. Ilr: Where’d
my gadgets go? In 2012 IEEE Symposium on Security and Privacy, pages
571–585, May 2012.
[76] Andrei Homescu, Steven Neisius, Per Larsen, Stefan Brunthaler, and Michael
Franz. Profile-guided Automated Software Diversity. In Proceedings of the 2013
IEEE/ACM International Symposium on Code Generation and Optimization
(CGO), CGO ’13, pages 1–11, Washington, DC, USA, 2013. IEEE Computer
Society.
[77] R. Hund, C. Willems, and T. Holz. Practical timing side channel attacks against
kernel space aslr. In Security and Privacy (SP), 2013 IEEE Symposium on,
pages 191–205, May 2013.
192
[78] Ralf Hund, Thorsten Holz, and Felix C. Freiling. Return-oriented Rootkits:
Bypassing Kernel Code Integrity Protection Mechanisms. In Proceedings of the
18th Conference on USENIX Security Symposium, SSYM’09, pages 383–398,
Berkeley, CA, USA, 2009. USENIX Association.
[79] Intel. Intel 64 and IA-32 Architectures Software Developer’s Manual, June 2014.
[80] Intel. Intel 64 and IA-32 Architectures Software Developer’s Manual Combined
Volumes: 1, 2A, 2B, 2C, 3A, 3B, and 3C, June 2014.
[81] Todd Jackson, Andrei Homescu, Stephen Crane, Per Larsen, Stefan Brunthaler,
and Michael Franz. Diversifying the software stack using randomized nop in-
sertion. In Sushil Jajodia, Anup K. Ghosh, V.S. Subrahmanian, Vipin Swarup,
Cliff Wang, and X. Sean Wang, editors, Moving Target Defense II, volume 100
of Advances in Information Security, pages 151–173. Springer New York, 2013.
[82] Todd Jackson, Babak Salamat, Andrei Homescu, Karthikeyan Manivannan,
Gregor Wagner, Andreas Gal, Stefan Brunthaler, Christian Wimmer, and
Michael Franz. Compiler-Generated Software Diversity. In Sushil Jajodia,
Anup K. Ghosh, Vipin Swarup, Cliff Wang, and X. Sean Wang, editors, Moving
Target Defense, volume 54 of Advances in Information Security, pages 77–98.
Springer New York, 2011.
[83] Adhiraj Joshi, Swapnil Pimpale, Mandar Naik, Swapnil Rathi, and Kiran
Pawar. Twin-Linux: Running independent Linux Kernels simultaneously on
separate cores of a multicore system. In Proceedings of the Ottawa Linux Sym-
posium, 2010.
[84] Mateusz Jurczyk and Gynvael Coldwind. Identifying and exploiting windows
kernel race conditions via memory access patterns. 2013.
193
[85] S. Kagstrom, L. Lundberg, and H. Grahn. A novel method for adding multi-
processor support to a large and complex uniprocessor kernel. In Parallel and
Distributed Processing Symposium, 2004. Proceedings. 18th International, pages
60–, April 2004.
[86] Morgon Kanter. Enhancing Non-determinism in Operating Systems. PhD the-
sis, Thayer School of Engineering at Dartmouth College, October 2013.
[87] Morgon Kanter and Stephen Taylor. Attack Mitigation through Diversity.
In Military Communications Conference, MILCOM 2013 - 2013 IEEE, pages
1410–1415, Nov 2013.
[88] Morgon Kanter and Stephen Taylor. Attack Mitigation through Diversity.
In Military Communications Conference, MILCOM 2013 - 2013 IEEE, pages
1410–1415, Nov 2013.
[89] Morgon Kanter and Stephen Taylor. Diversity in Cloud Systems Through Run-
time and Compile-time Relocation. In Proceedings of the 13th IEEE Conference
on Technologies for Homeland Security, pages 396–402, 2013.
[90] Kdm. NTIllusion: A portable Win32 userland rootkit, 62.
[91] keegan. Attacking Hardened Linux Systems with Kernel JIT Spraying, June
2011.
[92] Vasileios P. Kemerlis, Michalis Polychronakis, and Angelos D. Keromytis.
Ret2Dir: Rethinking Kernel Isolation. In Proceedings of the 23rd USENIX Con-
ference on Security Symposium, SEC’14, pages 957–972, Berkeley, CA, USA,
2014. USENIX Association.
[93] Vasileios P. Kemerlis, Georgios Portokalidis, and Angelos D. Keromytis.
kGuard: Lightweight Kernel Protection Against Return-to-user Attacks. In
194
Proceedings of the 21st USENIX Conference on Security Symposium, Secu-
rity’12, pages 39–39, Berkeley, CA, USA, 2012. USENIX Association.
[94] D. Keuper. XNU: a security evaluation, December 2012.
[95] Jean-Jamil Khalife. MS15-010/CVE-2015-0057 win32k Local Privilege Escala-
tion, December 2015.
[96] Chongkyung Kil, Jinsuk Jun, Christopher Bookholt, Jun Xu, and Peng Ning.
Address Space Layout Permutation (ASLP): Towards Fine-Grained Random-
ization of Commodity Software. In Proceedings of the 22Nd Annual Computer
Security Applications Conference, ACSAC ’06, pages 339–348, Washington, DC,
USA, 2006. IEEE Computer Society.
[97] Avi Kivity, Dor Laor, Glauber Costa, Pekka Enberg, Nadav Har’El, Don Marti,
and Vlad Zolotarov. OSv-optimizing the operating system for virtual machines.
In 2014 usenix annual technical conference (usenix atc 14), pages 61–72, 2014.
[98] Gerwin Klein, June Andronick, Kevin Elphinstone, Toby Murray, Thomas
Sewell, Rafal Kolanski, and Gernot Heiser. Comprehensive Formal Verification
of an OS Microkernel. ACM Trans. Comput. Syst., 32(1):2:1–2:70, February
2014.
[99] P. Larsen, A. Homescu, S. Brunthaler, and M. Franz. SoK: Automated Software
Diversity. In Security and Privacy (SP), 2014 IEEE Symposium on, pages 276–
291, May 2014.
[100] Per Larsen, Stefan Brunthaler, Lucas Davi, and Ahmad-Reza Sadeghi. Auto-
mated Software Diversity. Morgan & Claypool, 2015.
195
[101] Per Larsen, Andrei Homescu, Stefan Brunthaler, and Michael Franz. Sok: Auto-
mated software diversity. In Security and Privacy (SP), 2014 IEEE Symposium
on, pages 276–291. IEEE, 2014.
[102] Rick Lehtinen, Deborah Russell, and G. T. Gangemi. Computer Security Basics.
O’Reilly Media, Inc., 2006.
[103] Chuck Lever and Chuck Boreham. malloc() Performance in a Multithreaded
Linux Environment. In Proceedings of USENIX Annual Technical Conference,
pages 55–56, 2000.
[104] John R. Levine. Linkers and Loaders. Morgan Kaufmann Publishers Inc., San
Francisco, CA, USA, 1st edition, 1999.
[105] Kyung-Suk Lhee and Steve J Chapin. Buffer overflow and format string overflow
vulnerabilities. Software: Practice and Experience, 33(5):423–460, 2003.
[106] Jinku Li, Zhi Wang, Xuxian Jiang, Michael Grace, and Sina Bahram. Defeating
Return-oriented Rootkits with ”Return-Less” Kernels. In Proceedings of the 5th
European Conference on Computer Systems, EuroSys ’10, pages 195–208, New
York, NY, USA, 2010. ACM.
[107] Rick Lindsley and Dave Hansen. Bkl: One lock to bind them all. In Ottawa
Linux Symposium, page 301, 2002.
[108] Anthony Lineberry. Malicious Code Injection via/dev/mem. 2009.
[109] Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas,
Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Ham-
burg. Meltdown. ArXiv e-prints, January 2018.
[110] Thomas Lovén. Recursive page directory, June 2012.
196
[111] Anil Madhavapeddy and David J Scott. Unikernels: Rise of the virtual library
operating system. Queue, 11(11):30, 2013.
[112] A. Mahmood and E. J. McCluskey. Concurrent error detection using watchdog
processors-a survey. IEEE Transactions on Computers, 37(2):160–174, Feb
1988.
[113] Hector Marco-Gisbert and Ismael Ripoll-Ripoll. Exploiting Linux and PaX
ASLR’s weaknesses on 32- and 64-bit systems. In Blackhat Asia 16, April 2016.
[114] Joao Martins, Mohamed Ahmed, Costin Raiciu, and Felipe Huici. Enabling
fast, dynamic network processing with clickos. In Proceedings of the second
ACM SIGCOMM workshop on Hot topics in software defined networking, pages
67–72. ACM, 2013.
[115] Richard McDougall and Jim Mauro. Solaris internals: Solaris 10 and OpenSo-
laris kernel architecture. Pearson Education, 2006.
[116] metasploit. Chkroot Local Privilege Escalation, November 2015.
[117] Jeffrey C. Mogul, Jayaram Mudigonda, Nathan Binkert, Parthasarathy Ran-
ganathan, and Vanish Talwar. Using Asymmetric Single-ISA CMPs to Save
Energy on Operating Systems. IEEE Micro, 28(3):26–41, 2008.
[118] Ingo Molnar. 4G/4G split on x86, 64 GB RAM (and more) support, July 2003.
[119] T.Y. Morad, U.C. Weiser, A. Kolodny, M. Valero, and E. Ayguade. Perfor-
mance, power efficiency and scalability of asymmetric cluster chip multiproces-
sors. Computer Architecture Letters, 5(1):14–17, Jan 2006.
[120] Timothy Prickett Morgan. x86 servers dominate the datacenter - for now, June
2015.
197
[121] S. Muir and J. Smith. AsyMOS-an asymmetric multiprocessor operating sys-
tem. In Open Architectures and Network Programming, 1998 IEEE, pages 25–
34, Apr 1998.
[122] Tilo Müller. Aslr smack & laugh reference. In Seminar on Advanced Exploitation
Techniques, 2008.
[123] Colin Nichols. Bear - a Resilient Core for Distributed Systems. Master’s thesis,
Thayer School of Engineering at Dartmouth College, 2013.
[124] Jeff Larson Nicole Perlroth and Scott Shane. N.s.a. able to foil basic safeguards
of privacy on web, September 2013.
[125] Gene Novark and Emery D Berger. Dieharder: securing the heap. In Proceedings
of the 17th ACM conference on Computer and communications security, pages
573–584. ACM, 2010.
[126] Angelos Oikonomopoulos, Elias Athanasopoulos, Herbert Bos, and Cristiano
Giuffrida. Poking holes in information hiding. In 25th USENIX Security Sym-
posium (USENIX Security 16), pages 121–138, Austin, TX, 2016. USENIX
Association.
[127] Aleph One. Smashing the Stack for Fun and Profit. Phrack, 7(49), November
1996.
[128] Christian Otterstad. Brute force bypassing of aslr on linux. Norsk informasjon-
ssikkerhetskonferanse (NISK), 2012, 2012.
[129] Yoann Padioleau, Julia L. Lawall, and Gilles Muller. Understanding Collateral
Evolution in Linux Device Drivers. In Proceedings of the 1st ACM SIGOPS/Eu-
roSys European Conference on Computer Systems 2006, EuroSys ’06, pages
59–71, New York, NY, USA, 2006. ACM.
198
[130] R. K. Pandey and Vinay Tiwari. Article: Reliability Issues in Open Source Soft-
ware. International Journal of Computer Applications, 34(1):34–38, November
2011. Full text available.
[131] RK Pandey and Vinay Tiwari. Reliability issues in open source software. 2011.
[132] Vasilis Pappas, Michalis Polychronakis, and Angelos D. Keromytis. Smashing
the Gadgets: Hindering Return-Oriented Programming Using In-place Code
Randomization. In Proceedings of the 2012 IEEE Symposium on Security and
Privacy, SP ’12, pages 601–615, Washington, DC, USA, 2012. IEEE Computer
Society.
[133] PaX. Homepage of the PaX Team, 2013.
[134] Nick L. Petroni, Jr. and Michael Hicks. Automated Detection of Persistent
Kernel Control-flow Attacks. In Proceedings of the 14th ACM Conference on
Computer and Communications Security, CCS ’07, pages 103–115, New York,
NY, USA, 2007. ACM.
[135] Daniel Potts, Simon Winwood, and Gernot Heiser. Design and Implementation
of the L4 Microkernel for Alpha Multiprocessors, 2002.
[136] William H. Press. Numerical Recipes 3rd Edition: The Art of Scientific Com-
puting. Cambridge University Press, 2007.
[137] Brian Randell. System structure for software fault tolerance. In ACM SIGPLAN
Notices, volume 10, pages 437–449. ACM, 1975.
[138] rebel. issetugid() + rsh + libmalloc osx local root, July 2015.
[139] Ryan Riley, Xuxian Jiang, and Dongyan Xu. Guest-Transparent Prevention
of Kernel Rootkits with VMM-Based Memory Shadowing. In Proceedings of
199
the 11th International Symposium on Recent Advances in Intrusion Detection,
RAID ’08, pages 1–20, Berlin, Heidelberg, 2008. Springer-Verlag.
[140] Ryan Roemer, Erik Buchanan, Hovav Shacham, and Stefan Savage. Return-
Oriented Programming: Systems, Languages, and Applications. ACM Trans.
Inf. Syst. Secur., 15(1):2:1–2:34, March 2012.
[141] Timothy Roscoe, Kevin Elphinstone, and Gernot Heiser. Hype and Virtue. In
Proceedings of the 11th USENIX Workshop on Hot Topics in Operating Systems,
HOTOS’07, pages 4:1–4:6, Berkeley, CA, USA, 2007. USENIX Association.
[142] Dan Rosenberg. Qsee trustzone kernel integer over flow vulnerability. In Black-
hat USA 2014, pages 1–5, 2014.
[143] Dan Rosenburg. SMEP: What is it, and How to Beat it on Linux., June 2011.
[144] Joanna Rutkowska and Alexander Tereshkin. Bluepilling the Xen Hypervisor.
Black Hat USA, 2008.
[145] Jerome H Saltzer and Michael D Schroeder. The protection of information in
computer systems. Proceedings of the IEEE, 63(9):1278–1308, 1975.
[146] Ravi S Sandhu, Edward J Coyne, Hal L Feinstein, and Charles E Youman.
Role-based access control models. Computer, (2):38–47, 1996.
[147] Arvind Seshadri, Mark Luk, Ning Qu, and Adrian Perrig. SecVisor: A Tiny
Hypervisor to Provide Lifetime Kernel Code Integrity for Commodity OSes.
SIGOPS Oper. Syst. Rev., 41(6):335–350, October 2007.
[148] Hovav Shacham. The Geometry of Innocent Flesh on the Bone: Return-into-
libc Without Function Calls (on the x86). In Proceedings of the 14th ACM
Conference on Computer and Communications Security, CCS ’07, pages 552–
561, New York, NY, USA, 2007. ACM.
200
[149] Hovav Shacham, Eu jin Goh, Nagendra Modadugu, Ben Pfaff, and Dan Boneh.
On the Effectiveness of Address-Space Randomization. In In CCS 04: Proceed-
ings of the 11th ACM Conference on Computer and Communications Security,
pages 298–307. ACM Press, 2004.
[150] Eitaro Shioji, Yuhei Kawakoya, Makoto Iwamura, and Takeo Hariu. Code
shredding: Byte-granular randomization of program layout for detecting code-
reuse attacks. In Proceedings of the 28th Annual Computer Security Applications
Conference, ACSAC ’12, pages 309–318, New York, NY, USA, 2012. ACM.
[151] Snow, Kevin Z. and Monrose, Fabian and Davi, Lucas and Dmitrienko, Alexan-
dra and Liebchen, Christopher and Sadeghi, Ahmad-Reza. Just-in-time code
reuse: On the effectiveness of fine-grained address space layout randomization.
In Proceedings of the 2013 IEEE Symposium on Security and Privacy, SP ’13,
pages 574–588, Washington, DC, USA, 2013. IEEE Computer Society.
[152] Matt Solnik. Who needs decrypted kernels anyways?, August 2016.
[153] Brad Spengler. uderef, 2007.
[154] Kevin Spett. Cross-site scripting. Technical report, SPI Labs, 2005.
[155] Arwed Starke. Locking in os kernels for smp systems. Citeseer, 2006.
[156] PaX Team. Address Space Layout Randomization.
https://pax.grsecurity.net/docs/aslr.txt, 2001.
[157] PaX Team. Address Space Layout Randomization. https://pax.grsecurity.
net/docs/aslr.txt, 2001.
[158] Ken Thompson. Reflections on Trusting Trust. Commun. ACM, 27(8):761–763,
August 1984.
201
[159] Jim Turley. Taming the x86 beast, 2004.
[160] Richard Wartell, Vishwath Mohan, Kevin W. Hamlen, and Zhiqiang Lin. Binary
stirring: Self-randomizing instruction addresses of legacy x86 binary code. In
Proceedings of the 2012 ACM Conference on Computer and Communications
Security, CCS ’12, pages 157–168, New York, NY, USA, 2012. ACM.
[161] King’s Way. Lastore-Daemon in Deepin 15 results in privilege escalation, Febru-
ary 2016.
[162] Ollie Whitehouse. An Analysis of Address Space Layout Randomization on
Windows Vista. Technical report, Symantec, 2007.
[163] Haizhi Xu and Steve J. Chapin. Address-space Layout Randomization Using
Code Islands. J. Comput. Secur., 17(3):331–362, August 2009.
202
- Abstract
- Contents
- List of Tables
- List of Figures
- List of Code Snippets
- List of Algorithms
- Introduction
- Approach
- Metrics of Success
- Publications and Contributions
- Thesis Organization
- Background and State of the Art
- Virtual Memory
- Case Study: Recursive Paging
- The Virtual Address Space
- Message Passing
- Scheduling
- Related Work
- Privilege Escalation Mitigation
- Techniques based on Virtualization
- Other Techniques
- Comparison
- Privilege Escalation Mitigation: Conclusion
- Execute-Only Memory
- Code Diversification
- Asymmetrical Multiprocessing
- Operating System Design Paradigm Shifts
- Microkernels
- ExoKernel
- Unikernels
- ExOShim
- ExOShim: Background
- The Kernel and Virtual Memory
- Virtualization and the EPT
- ExOShim: Overview
- Assumptions
- ExOShim
- ExOShim: Implementation
- Providing ExOShim a Context
- Building the EPT
- Starting Virtualization
- ExOShim: Evaluation and Analysis
- Prototype Complexity
- Performance
- Security Implications
- ExOShim: Conclusion
- Future Work
- Final Thoughts
- Diversification: KPLT
- KPLT: Overview
- Using the Virtual Memory Abstraction
- The Contents of a KPLT
- KPLT: Implementation
- KPLT Creation at Load-Time
- Run-time KPLT Maintenance and Manipulation
- KPLT: Evaluation and Analysis
- Security Implications
- Increase in Diversity
- Performance Cost
- Remaining Work and Challenges
- KPLT: Conclusion
- Diversification: Überdiversity
- Diversification Algorithms
- Run-time Complexity and Termination Analysis
- Proof of Uniformly Distributed Variants
- Überdiversity: Implementation
- ELF & the Diversity Loader
- The Virtual Memory Abstraction
- Diversifying the Entire Software Stack
- Überdiversity: Evaluation and Analysis
- Quantification of Diversity Achieved
- Performance Cost
- Security Implications
- Überdiversity: Conclusion
- KUCS
- KUCS: Overview
- Separating Kernel and User Cores
- Fine-Grained Virtualization
- Increasing Performance
- KUCS: Implementation
- KUCSBear
- Interrupts
- Virtual Memory
- Message Passing
- Scheduling
- KUCS: Evaluation and Analysis
- Security
- Performance
- Future Work
- KUCS: Conclusion
- Conclusion
- Bibliography
