ADDING OPERATING SYSTEM STRUCTURE TO LANGUAGE-BASED PROTECTION
A Dissertation
Presented to the Faculty of the Graduate School
of Cornell University
in Partial Fulfillment of the Requirements for the Degree of
Doctor of Philosophy
by
Chris
topher K.irk Hawblitzel
August 2000
© 2000 Chris
topher K
irk. Hawblitzel
ADDING OPERATING SYSTEM STRUCTURE TO LANGUAGE-BASED PROTECTION
Chris
topher K.irk Hawblitzel, Ph.D.
Cornell University 2000
The abstract starts
hereExtensible Internet applications increasingly
rely on language safety for protection, rather than using
protection mechanisms based on virtual memory. For example,
the Java language now provides protection for applets, servlets,
agents and active networks. Unfortunately, typical safe
language systems do not have the support for resource control,
revocation, and on-demand program termination present in
traditional operating systems. Naive attempts to add these
features to a language can easily backfire: Sun recently
deprecated Java's thread termination methods because of subtle
interactions with Java's synchronization and abstraction
mechanisms.
In this thesis, I argue that these problems arise from a lack of clear structure in safe language systems. Often, these systems allow objects, threads, and code to pass freely from one program to another, blurring the boundaries between programs. To restore the boundaries, I introduce the idea of a safe language task that encapsulates a program's objects, threads, and code, and I argue that a system based on the task model can provide strong and simple guarantees about resource control, thread management, termination, revocation, and whole-program optimization. I present two implementations of the task model: the J-Kernel, which uses Java remote method invocation for inter-task communication, and Luna, which extends Java's type system to express the task model directly.
Biographical sketch starts hereChris Hawblitzel was born in Kansas City,
Missouri in 1973. He started college at UC-Berkeley in 1989
and received a bachelor's degree in physics there in 1993. He
began graduate school at Cornell studying computational physics,
and switched to computer science in Spring of 1996.
There are so many people to whom I owe thanks
that I cannot
hope to repay them
all
here.
Most of all
I would like to thankAcknowledgments start here
my parents,
who introduced me to computers in the first
place,
fortheir boundless
supportand
encouragement, their warm sense of humor, and theirunfailing integrity. My mother and father are
lifelong teachers and lifelong learners—it
was they who taught me
how
to learn and from them I learned
how
to teach.
Many thanks go to Thorsten von Eicken and Greg Morrisett for opening up entire new worlds to explore, and for straightening every crooked path that I traveled on. Their ideas formed the basis for this thesis, and their advice molded my own shakyproposalsinto something solid and practical. Working with them was both an honor and a pleasure.
I am greatly indebted toGreg Czajkowski, Chi-Chao Chang, Deyu Hu, and Dan Spoonhower for transformingthe J-Kernel from anisolatedprototype into a real working environment. Without them, the J-Kernelwould never have hatched from its shell.
Thanks to Lidong Zhou, Ulfar Erlingsson, Fred Schneider, Andrew Myers, Brian Smith, Hal Perkins, Jay Lepreau, Wilson Hsieh, and Pat Tullmann,whose insights and commentssignificantly influenced the content of this thesis.
Thanks to the Marmot group for sharing a stellar compiler with us.
Thanks for moral and practicalsupport toeveryone in Greg Morrisett's group, including Fred Smith, Dave Walker, Neal Glew, Dan Grossman, Stephanie Weirich, Steve Zdancewic, and Karl Crary, as our own group was slowly decimated by graduation and employment. Thanks to Greg Czajkowski, Chi-Chao Chang, Deyu Hu, Soam Acharya, Sugata Mukhopadhyay, Wei Tsang Ooi, Eva Luther, and Dan Spoonhower for such an intellectually stimulating and enjoyable work environment, particularly when the work consisted of discussing weighty topics like the future of electronic commerce or the virtues of Polish Hip-hop. Finally, thanks to my officemates, Tibor Janosi and Matt Fleming;Ishould probably dropby someday. Matt, of course, knows what's in the black bag, but others can savor the mystery.
1.1 Motivation: the challenges of a programmable internet 3
1.2.1 Address-based protection mechanisms 5
1.2.2 Type-based protection mechanisms 7
1.3 Where does language-based protection fall short? 10
1.3.3 Inter-program dependencies and side effects 14
1.3.5 Dynamic loading limits optimizations 16
1.4.1 Distinguishing local and remote objects 19
2.1 Java Remote Method Invocation 24
2.3 Capability implementation 30
2.4 Creating and terminating tasks 36
2.6 J-Kernel micro-benchmarks 43
3.1 Remote pointers and revocation 50
3.2 Sharing data with remote pointers 52
3.3 Method invocations on remote pointers 55
3.3.1 Copying remote objects 56
3.3.2 Combining copies and method invocation 59
Chapter Four: Luna Implementation and performance 64
4.1 Extended bytecode format 64
4.2 Implementing remote pointers 65
4.2.1 Special Java pointer operations: equality, instanceof, checkcast, synchronization 68
4.3 Method invocations and threads 71
4.4 Garbage collection and safe points 89
4.5 Tasks and dynamic loading 93
4.6 Micro-benchmarks and optimizations 101
4.6.1 Caching permit information 112
Chapter Five: Alternate ApProaches to the Task Model 174
5.1 Termination, task boundaries 188
5.1.3 Terminating threads and code 205
5.2.1 Sharing in non-object-oriented languages 214
5.3 Enforcing the task model, symmetric vs. asymmetric communication 221
5.3.1 Symmetric and asymmetric communication 230
5.3.2 Server-centric vs. client-centric design 232
5.4 Resource accounting policy 239
5.5.1 Accounting for collection time 251
Chapter
One: INTRODUCTION
1
1.1
Motivation:
the challenges of a programmable internet
3
1.2
Protection
mechanisms
5
1.2.1
Address-based protection
mechanisms
6
1.2.2
Type-based
protection
mechanisms
7
1.3
Where does
language-based protection fall short?
12
1.3.1
Termination
12
1.3.2
Revocation
15
1.3.3
Inter-program dependencies and side
effects
16
1.3.4
Resource
Accounting
17
1.3.5
Dynamic
loading limits
optimizations
18
1.4
The
task
19
1.4.1
Distinguishing local and remote
objects
21
Chapter
Two: The J-Kernel
24
2.1
Java Remote
Method Invocation
26
2.2
J-Kernel
capabilities
29
2.3
Capability
implementation
33
2.3.1
Revocation
34
2.3.2
Thread
segments
35
2.3.3
Copying
arguments
37
2.4
Creating
and terminating tasks
39
2.5
Task
linking
42
2.5.1
Creating
resolvers
45
2.6
J-Kernel
micro-benchmarks
47
2.6.1
Null
LRMI
47
2.6.2
Threads
48
2.6.3
Argument
Copying
49
2.7
Application
benchmarks
50
2.8
Conclusions
52
Chapter
Three: Luna design
54
3.1
Remote
pointers and revocation
55
3.2
Sharing
data with remote pointers
58
3.3
Method
invocations on remote pointers
61
3.3.1
Copying
remote
objects
63
3.3.2
Combining
copies and method
invocation
66
3.4
Type system
design
67
Chapter
Four: Luna Implementation and performance
71
4.1
Extended
bytecode format
71
4.2
Implementing remote pointers
73
4.2.1
Special
Java pointer operations: equality, instanceof, checkcast,
synchronization
76
4.2.2
Synchronization
77
4.3
Method
invocations and threads
80
4.3.1
Terminating
threads
84
4.4
Garbage
collection and safe points
86
4.5
Tasks and
dynamic loading
88
4.6
Micro-benchmarks and optimizations
90
4.6.1
Caching
permit
information
91
4.7
Luna web
server
96
Chapter
Five: Alternate ApProaches to the Task Model
98
5.1
Termination, task boundaries
99
5.1.1
Terminating
threads
100
5.1.2
Terminating
code
101
5.1.3
Terminating
threads and
code
104
5.2
Sharing
104
5.2.1
Sharing in
non-object-oriented
languages
105
5.2.2
Revocation
106
5.3
Enforcing
the task model, symmetric vs. asymmetric
communication
107
5.3.1
Symmetric
and asymmetric
communication
109
5.3.2
Server-centric vs. client-centric
design
110
5.4
Resource
accounting policy
113
5.5
Garbage
collection
114
5.5.1
Accounting
for collection
time
116
5.6
Conclusions
117
Chapter
Six: conclusions
119
bibliography
122
Chapter One: INTRODUCTION
9
1.1
Motivation: the challenges of a programmable
internet
3
1.2
Protection mechanisms
4
1.2.1
Address-based protection
mechanisms
5
1.2.2
Type-based protection
mechanisms
6
1.3
Where does language-based protection fall
short?
11
1.3.1
Termination
11
1.3.2
Revocation
13
1.3.3
Inter-program dependencies and side
effects
15
1.3.4
Resource
Accounting
16
1.3.5
Dynamic loading limits
optimizations
16
1.4
The task
17
1.4.1
Distinguishing local and remote
objects
19
Chapter Two: The J-Kernel
1
2.1
Java Remote Method Invocation
3
2.2
J-Kernel capabilities
6
2.3
Capability implementation
9
2.3.1
Revocation
11
2.3.2
Thread
segments
11
2.3.3
Copying
arguments
13
2.4
Creating and terminating tasks
15
2.5
Task linking
18
2.6
Implementation: pure Java with bytecode
rewriting
21
2.7
J-Kernel micro-benchmarks
22
2.7.1
Null
LRMI
22
2.7.2
Threads
23
2.7.3
Argument
Copying
24
2.8
Application benchmarks
24
2.9
Conclusions
27
2.9.1
Frequently asked
questions
27
Chapter Three: Luna
28
3.1
Remote pointers
2
3.2
Sharing data with remote
pointers
4
3.3
Method invocations on remote
pointers
8
3.3.1
Copying remote
objects
10
3.3.2
Combining copies and method
invocation
12
3.4
Type system design
14
3.5
Implementation
17
3.5.1
Extended bytecode
format
18
3.5.2
Implementing remote
pointers
19
3.5.3
Method invocations and
threads
27
3.5.4
Garbage collection and safe
points
33
3.5.5
Tasks and dynamic
loading
34
3.5.6
Micro-benchmarks and
optimizations
37
3.6
Luna web server
43
Chapter Four: Alternate ApProaches to the Task
Model
45
4.1
Termination, code sharing
46
4.1.1
Terminating
threads
47
4.1.2
Terminating
code
48
4.1.3
Terminating threads and
code
51
4.2
Sharing
51
4.2.1
Revocation
53
4.3
Enforcing the task model, symmetric vs.
asymmetric communication
54
4.3.1
Server-centric vs. client-centric
design
57
4.4
Resource accounting policy
60
4.5
Garbage collection
61
bibliography
65
LIST OF TABLES
Table 2.1: Cost of null method invocations........................................................... 48
Table 2.2: Local RPC costs using NT mechanisms............................................... 48
Table 2.3: Cost of a double thread switch using regular Java threads.............. 49
Table 2.4: Cost of argument copying...................................................................... 49
Table 2.5: Server throughput................................................................................... 51
Table 2.6: Web/Telephony server performance................................................... 52
Table 4.1: Luna remote pointer instructions......................................................... 72
Table 4.2: Classes that share code (all are in java.lang)....................................... 90
Table 4.3: Remote pointer performance, without caching optimizations......... 91
Table 4.4: Speed of local and remote list traversals............................................. 96
Table 4.5: Servlet response speed........................................................................... 97
LIST OF FIGURES
Figure 1.1: Classifying protection mechanisms...................................................... 6
Figure 1.2: Using indirection to implement revocation....................................... 16
Figure 2.1: Serializable object passed through RMI............................................. 27
Figure 2.2: Dispatch servlet example..................................................................... 28
Figure 2.3: Remote method invocation example.................................................. 29
Figure 2.4: The Capability class.............................................................................. 30
Figure 2.5: Creating a capability............................................................................. 31
Figure 2.6: Selective revocation............................................................................... 32
Figure 2.7: Multiple indirection.............................................................................. 32
Figure 2.8: Capability creation example................................................................ 33
Figure 2.9: Capability implementation.................................................................. 34
Figure 2.10: Thread segment implementation...................................................... 37
Figure 2.11: Seeding a new task.............................................................................. 40
Figure 2.12: Resolver interface................................................................................ 45
Figure 3.1: Luna type system................................................................................... 55
Figure 3.2: The Permit class..................................................................................... 56
Figure 3.3: The @ operator....................................................................................... 56
Figure 3.4: Typechecking rules for field operations............................................ 59
Figure 3.5: Using remote data structures............................................................... 61
Figure 3.6: FileServlet example............................................................................... 62
Figure 3.7: Copying a Request object..................................................................... 63
Figure 3.8: Subclass example................................................................................... 64
Figure 3.9: Intermediary to Servlet interface......................................................... 66
Figure 3.10: Calling a RemoteServlet..................................................................... 66
Figure 3.11: Permit variables................................................................................... 68
Figure 3.12: Chaining capabilities........................................................................... 69
Figure 4.1: Read after revoke................................................................................... 74
Figure 4.2: Modify after revoke............................................................................... 74
Figure 4.3: Deterministic evaluation...................................................................... 75
Figure 4.4: Remote synchonization......................................................................... 77
Figure 4.5: Synthesizing remote locks.................................................................... 79
Figure 4.6: Threads and stacks in cross-task invocations.................................... 81
Figure 4.7: Permit caching example I..................................................................... 92
Figure 4.8: Permit caching example II.................................................................... 92
Figure 4.9: Permit caching example III................................................................... 93
Figure 4.10: Inner loop assembly code for local and remote list traversals..... 95
Figure 5.1: Expressing trust and resources with extra tasks............................. 112
MModern programming languages
are often
expected to perform traditional operating
system duties, but they aren’ot ready to replace operating systems
yet.
This thesis argues that Pprogramming languages must incorporate
additional operating systems features if they are to implement
operating system functionality.
The distinction between programming languages and
operating systems used to be clear. Programming languages
were tools to write applications without having to enter assembly
code by hand, while operating systems were tools to manage a
system’s resources and protect one application from
another. These days, however, developers of extensible
applications often expect programming languages to perform
functions traditionally associated with operating systems.
Browsers, servers, agent systems, databases, and active networks
all support extensions written in a safe language such as
Java. In these systems, the language’s type safety
protects the system
application core from the extensions (and
the extensions from each other) by restricting the operations that
extensions are allowed to perform.
However, type safety doesn’ot prevent a program from consuming too
many resources, or ensure that runaway program execution can be
stopped cleanly. Nor does type safety provide a large-scale
framework for structuring communication between extensions.
In addition to type safety, language-based protection systems need
an aggregate structure that encapsulates a program’s
resources, and guides program termination, resource management,
security analysis, and communication between programs.
Existing aggregate structures, such as
Java’s class loaders and thread groups, are ad
hoc and suffer from undesirable and unexpected interactions with
the language’s type system [REF class loader bugSar97, REF damaged objectsJavb]. The main weakness of these
existing structures is that they manage subsets of a
program’s resources in isolation: class loaders track a
program’s code, but say nothing about a program’s
threads and objects, while thread groups track a program’s
threads but not its code or objects. Thus, current structures
cannot make guarantees about the interactions between code,
threads, and objects. This thesis makes two contributions
toward solving this problem:
· It proposes a more comprehensive aggregate structure, called a task, which controls a program’s code, objects, and threads together. In this respect, a task is analogous to a process or task in a traditional operating system.
· It proposes inter-task communication mechanisms that distinguish code, objects, and threads belonging to one task from those belonging to other tasks. This clarifies the boundaries between tasks and allows the system to guarantee properties of tasks. For example, the systems presented in this thesis ensure that a task's threads only execute the task's own code. Unlike current Java communication mechanisms, the communication mechanisms presented in this system are general purpose: they may be used as easily for agent-to-agent communication as for applet-to-browser or servlet-to-server communication.
The
rest of the thesis is as follows: chapter 1 motivates and
describes language-based protection and the task model in
detail. Chapters 2
,
3, and 34 describe two particular implementations
of the task model, the J-Kernel and Luna. Chapter 45 explores the task model in more
generality, discussing related work and alternate approaches to
implementing the task model. Chapter
56 concludes.
Operating systems with complex protection
mechanisms, such as Multics [REFCV65], were designed for large,
centralized, multi-user compute servers, where the OS had to
prevent one errant program from disrupting other users. The
past 20 years have seen a shift away from centralized computation
to networks of single-user personal computers. PC’s
often run unprotected operating systems like Windows 98 or MacOS,
partially because networking protocols
allow individual computers to fail without disrupting the whole
network. Mass acceptance of
fully highly protected PC operating
systems, such as NT and Linux, has been surprisingly slow, relative to the rapid
acceptance of the PC’s themselves. The trend towards
small, distributed computers continues with the spread of hand-held
and embedded processors. In light of these development
s, why worry about protection at all?
The continuing need for protection in a network
is due to the spread of executable content and mobile code.
First, Sseveral forms of executable content are
already in wide use: web pages commonly contain Javascript
code or Java applets, e-mail often contains executable attachments,
and word processor documents often contain postscript code or
macros. Such content has already caused serious network-wide
damage. In particular, e-mail attachments are often executed
with no protection at all, and are therefore vulnerable to
malicious viruses[REF].
Second, the
Internet has
shifted functionality
from
users’desktops to remote web sites, which limits a user’s ability to
customize applications(major web sites
such as Yahoo, Altavista,Amazon,
and Hotmail
often
contain
large
data
sets,
vigorously maintainedavailability, and proprietary functionality,whichcannot be practically transferred to
user PC’s).
Many
peoplehave advocated mobile code, such as
agents[GKC+98], servlets[Java], active database extensions[GMS+98], and active network extensions[Wet99],to
restore a user’s ability to customize
applications.
In order to execute code embedded in a document, a user must choose to download a document and execute the code. This makes attacks more difficult; a hacker's only hope is to post or send a document with embedded code, and then hope that someone will choose to execute the code.
Agents, servlets, active database extensions, and
active networks take the opposite approach, where an extension is
actively injected into a remote host, and begins execution with no
user intervention. This is inherently more susceptible to
attacks, especially in systems that allow anyone to upload
code[REF agents, REF active networks]. Even if such
systems require authentication before allowing code to execute and
perform auditing to track and deter malicious users, protection is
important, because hackers often find ways to circumvent
authentication
and auditing mechanisms. Typical
attacks rely on the fact that networking software often has bugs,
is misconfigured, or protected by weak passwords
[Spa89]. By increasing the
programmability of the iInternet, active extensions add another
weapon to a hacker's arsenal. For example, suppose that Zeke
wants to attack Kim's database, and that Kim's friend Alex is
trusted to load Java extensions to Kim's system. If Zeke can
guess Alex's password, then he can load an extension onto Kim's
system, which can then perform a denial of service attack.
The protection offered by
Java in Kim's system is still essential to prevent Zeke from
attacking the database's integrity and secrecy
,,
but isalthough it is not sufficient to protect
the database's availability.
By contrast, if Kim allowed friends to
upload unsafe code to her system, then her
system’s integrity
and secrecy
would be violated as well—in effect, her
security would become as weak as the weakest of
her
trusted
friends(which in turn
are as weak as the weakest of their
trusted
friends).
In addition, even trusted code may contain bugs;
protection
mechanisms
limit the disruptioncaused by a trusted, but faulty,
extension.
The previous section motivated protection in
extensible internet applications. This section looks at
several different potential protection mechanisms for such
applications: virtual memory protection, software fault isolation,
capability mechanisms, and language-based protection.
Broadly, these mechanisms are classified into
"“address-based"” protection and
“"type-based"” protection on one axis, and
hardware enforced and software enforced on another axis, as
illustrated in
Figure 1.1Figure
1.1.
Figure 1.1: Classifying protection mechanisms |
Current operating systems rely on protection mechanisms provided in hardware, specifically, memory protection, user/supervisor execution levels, and traps to switch levels. Memory protection is based on checking the validity of addresses issued by every instruction accessing memory. The user/supervisor privilege levels provide one execution mode where the access privileges are enforced and one where they can be changed. The traps (or call gates) provide a controlled transfer from user to supervisor level.
The key aspect of address-based protection is that it is based on the values of addresses issued by a program—these are checked and possibly translated—and not on how the program uses the data stored at those addresses.
In current microprocessors, the address-based protection is implemented as part of the virtual memory hardware. In CISC microprocessors, the set of accessible addresses (i.e., the address space) is represented by the page tables, while in RISC microprocessors with a software-managed TLB it is represented by the current set of valid TLB entries. The common characteristic of all these implementations is that the granularity of the protection mechanisms is a virtual memory page frame on the order of a few kilobytes, 4KB being the most typical. While it is possible to use smaller page frames in some implementations, this is generally inefficient.
Address-based protection can also be implemented
in software using a technique called software fault isolation (SFI)
[WLA+93, REF MisfitSma97]. In SFI, an executable is
analyzed and modified to enforce that all memory references lie
within the address space. Part of the enforcement is by
analysis and part is by the insertion of explicit
address check
ing or “sandboxing”
instructionss. The
se explicitextra checksinstructions compare
ensure that the value of an address in a
register
lies with
in the bounds held in other registers that
are protected from program modification. A privileged
execution level is implemented by instruction sequences that are
inserted without being subject to SFI. The details of these
instruction sequences depend highly on the characteristics of the
machine language being manipulated. For example, SFI is much
more efficient on RISC processors with fixed sized instructions
than on CISC processors with variable sized instructions.
Using SFI, the granularity of address space is generally larger
than with hardware-based mechanisms (e.g., an SFI address space is
typically larger than a hardware page) because the cost of
enforcement increases with the number of regions.
Address-based mechanisms perform access control
on the addresses that a program references, without worrying about
how the program generates addresses or what a program stores in the
addresses
to which it has accessto. By contrast, a
type-based protection mechanism limits a program's ability to
create values, by providing only a limited set of operations to
manipulate values. For example, two integers may be added
together to create a new integer, but two addresses cannot be added
together to create a new address. This section considers two
classes of type-based protection: capability systems, which
rely largely on hardware mechanisms to enforce the type system, and
language-based protection, which relies mostly on software
enforcement.
In a capability system [EB79, Lev84, PCH+82, Red74, WLH81], data values are distinguished from pointers (capabilities) and the system enforces that data values cannot be used as capabilities. The basic idea in such systems is that a program must first acquire a capability to a resource in order to access the resource. The type system ensures that a program cannot forge a capability to a resource that it should not have access to.
Some capability systems add a tag bit to every
word in memory to distinguish data and capabilities [CKD94, REF StarOS], and the processor
restricts the operations allowed on values that are tagged as
capabilities. In practice, however, this has led to complex
processor architectures
that are tied to particular
protection models or programming languages [
PCH+82REF I432]
, and expensive custom memory
technologies.
Other capability systems use an ordinary
processor's virtual-memory features to partition memory into data
and capability segments. While this led to performance
problems in early systems [REF
WLH81Hydra], because a program must trap
into the kernel to manipulate capabilities, more recent systems
[REF ErosSSF99] have argued that advances in
microkernel design make the cost of such traps acceptable. A
more difficult problem, though, is that segregated data and
capability segments complicate the programming model, because
capabilities cannot be easily mixed with data in data
structures. One possible solution to this problem is to use
cryptographic capabilities [
HEV+98REF Mungi,
TMvR86REF Amoeba], which are large random
numbers that are nearly unforgeable because they are difficult to
guess. Such capabilities are easier to store in data
structures, since they are just numbers.
Language-based protection relies on the safety of a programming language’s type system to restrict the operations that a program is allowed to perform. The language provides a set of types (integers, functions, and records, for instance), and operations that can manipulate instances of different types. Some operations make sense for some types but not others. For instance, a Java program can invoke a method of an object, but it cannot perform a method invocation on an integer.
Type-safe languages implement capability based
access control very naturally: a pointer (also called a
reference in Java jargon) cannot be forged, and can therefore
serve as a capability. Languages typically provide additional
access control mechanisms, such as Java’s
private,
default, protected, and
public, and final access qualifiers that
specify which code has access to which fields and methods of an
object. Wallach et al [
WBD+97REF] discusses Java access control
mechanisms in detail. One can design safe languages that have
more sophisticated access control.
For instance, Jones and Liskov
[JL78] extended a language’s type system to talk about access
rights directly, to provide a similar functionality to advanced
capability systems such as Hydra [WLH81].
Recently Myers and Liskov [ML97]
have extended this idea to cover information flow control.
A key issue of language-based protection is
ensuring that type safety and access control are enforced.
Type enforcement may be done dynamically or statically. In
the former case, a compiler inserts run-time checks into the
compiled code. In the latter case, the compiler analyzes the
program to ensure that it respects the type system's constraints
without requiring explicit run-time checks. Static type
enforcement is a key advantage of language-based protection over
the
traditional capability systemsof the previous systems,
which reliedentirely onose dynamic checks
are difficult to
implement efficiently
without special hardware.
In practice, most programming languages use a
combination of static and dynamic enforcement. For instance,
Java can statically verify that a variable of type
String will always point to a
String
object or contain the null pointer. On the other hand,
typical Java
implementations must dynamically perform
dynamic bounds checks when an array is
accessed. Some languages, such as Scheme, perform almost all
type enforcement at run-time, which tends to slow down program
execution.
Safe languages hold many potential advantages over other protection mechanisms. Since all programs run in a single address space, programs can communicate without expensive address space switches. While IPC (inter-process communication) is often an expensive operation in virtual memory based systems, in a safe language system a call from one program to another may be a simple function call. Furthermore, data can be shared between programs at a fine-grained level; programs can share individual objects rather than entire virtual memory pages. For example, ethernet cards typically receive network packets smaller than a page size, which means that traditional operating systems must either copy each incoming packet into application memory to prevent one application from seeing other applications' packets that landed on the same page, or waste space by receiving only one packet on each page.
Modern programming languages are good at both expressing and enforcing abstractions. Programs aren’t limited to sharing arrays of raw bytes: the language can statically enforce the integrity of shared abstract data types, which allows programs to communicate at a higher semantic level. For example, the IOLite [PDZ99] and FBuf [DP93] operating system facilities are based on linked lists of buffers, and the validity of the linked lists must be checked (e.g. for non-circularity) when the lists are copied from one process to another. A safe language can statically enforce invariants such as non-circularity of a list.
Safe languages also make it easier to write more flexible, secure programs. They guard against programming mistakes that lead to vulnerabilities. For example, guaranteed array bounds checks guard against buffer overflows that have been exploited by attackers in traditional systems [Spa89]. Typical safe languages support advanced features like object-orientation and higher order functions, which aid the construction of extensible systems, and naturally accommodate dynamic loading.
Since safe languages hide the details of the underlying processor, programs written in these languages tend to be portable across a wide variety of architectures, including small, embedded systems that lack the hardware and OS infrastructure needed for hardware-enforced protection. This portability is an advantage for mobile code systems.
The previous section argued the advantages of
language-based protection over other protection mechanisms, but
unfortunately
, language-based protection has serious
drawbacksas well. The performance of
safe languages tends to lag behind lower level languages like C,
typical language-based systems support only one language, and
relying on a language for protection requires trusting that the
language's compiler (the just-in-time compiler in Java's case) and
run-time system are written correctly. Other research has
made great strides in attacking these problems ([BSP+95], [HLP98],
[MWC+98], [NL98], [Sha97], [
WA99REF Princeton-GC]). This
thesis focuses on a different set of problems, arising from the
lack of OS features and structures in current language-based
systems. Current language-based systems do not adequately
support
termination, revocation, resource
accounting,optimization in the presence of dynamic
loading, and analyzing
the aggregate
system structure:.
Java’s mechanism for terminating programs is
based on thread groups.
Sun recently deprecated Java's Thread.stop and
ThreadGroup.stop API, leaving no officially sanctioned way to stop
an applet [Javb]. Under this
APIFor example,
a web
browser ,
creates a thread group for each applet
that it downloads.
As the applets execute,
Java’s run-time system each
places eachthread spawned by an applet
is marked as belonging to thein the applet’s thread group.
The browser creates a thread group for each
applet, and wTo shut downhen it wants to terminate an
applet, itthe browser terminates the applet’s
thread group, which terminates
stops all of the applet’s
threads. While this approach to termination seems reasonable
on first glance, closer inspection reveals several difficult
problems:
·
The wrong code gets interrupted: in Java, a call from an
applet to the system
browser is just a function call, so that
the system
browser code runs in the applet's
thread. The applet can kill or suspend the thread while the
system
browser code is running, possibly leaving
the system
browser in an inconsistent or deadlocked
state.
·
Malicious code eludes termination: terminating a malicious
program's threads does not terminate the program's code, which may
still exist in overridden methods of objects that
the malicious program created and passed to other programs.
If one of these other programs invokes the rogue object methods,
the malicious code is revived. Java mitigates this problem by
making key datatypes final (e.g. String, array types) or
primitive (e.g. int,
float) so
that they cannot contain overridden methods, but a purer
object-oriented language would have more difficulties.
·
Upcalls and peer-to-peer communication aren’ot supported: a browser cannot use
one of its own threads to make a call
to an applet, because this would
give the applet the ability to execute in a thread outside the
applet’s thread group, an
d this execution would not be stopped when
the applet’s thread group is terminated. Instead, the
browser must transfer control to an applet thread before calling
any applet code, which is cumbersome, slow, and requires the
programmer to carefully track which method invocations might call
applet code. Mutually suspicious peer-to-peer communication
(e.g. applet-to-applet or agent-to-agent communication) is even
harder, because neither side trusts the other side to perform the
needed thread switch.
·
Damaged objects violate abstract datatype integrity: under
Java's synchronization mechanisms, a thread may enter an object's
method, acquire a lock, start an atomic operation, and then get
terminated in the middle of the operation, releasing the lock and
leaving the object in a
“"damaged"” state that violates its intended
abstraction.
·
Resources aren'ot reclaimed: when a traditional
operating system shuts down a process, both the process's threads
and memory are shut down. Java's termination is weaker,
stopping threads but not necessarily reclaiming other
resources. Java’s String.intern method is
an example of this: any program can use this method to add
strings to a system-wide hash table, and these strings are not
garbage collected even when the program exits.
Aggressive resource reclamation is more
difficult in a
language-based environment, which encourages
sharing data between programs, than in a
traditional operating system based on
explicit
IPC (although newer, single address space
operating systems also encourage sharing—see Mungi [HEV+98], for example).
Because of the problems with thread groups, Sun recently deprecated the stopmethod in the classes Threadand ThreadGroup, leaving no officially sanctioned way to stop an applet [Javb].
In ordinary Java, pointers can serve as
capabilities, but once a program is given a pointer to an object,
that pointer cannot be revoked.
Revocation is a desirable feature for several
reasons. First, it Why would anyone want to revoke a
capability? Revocation assists termination: Luna
revokes all remote pointers into a task when the task is
terminated. It also helps to implement the
principle of least privilege, since it is better to give someone
access to something for only the necessary duration and then revoke
the access than to give them access forever. Revocation
also accommodates changing preferences
over time. An agent once considered trustworthy may abuse the
trust and necessitate revoking its privileges. At a lower
level, revocation is a good way to give someone temporary, fast
access to a resource, such as idle network buffer space or a
rectangle in video memory. In addition to these
device-specific examples, revocation is also used in general
purpose operating system mechanisms:
for instance,
FBufs [DP93] dynamically
revoke write access to buffers when data is transferred between
protection domains.
Finally, revocation
is necessary for
termination:
access to
any services exported by
aprogram must be revoked
when the program is stopped, because these
services are no longer available after the
program’s code
is unloaded.
Revocation has
historically been
a historical
a problem for capability systems, butand it is particularly difficult at the
language level, because every pointer could potentially be used as
a capability. While adding a level of indirection to every
capability may be a way to implement revocation in an operating
system with coarse-grained capabilities [Red74], adding a level of
indirection to every Java pointer is undesirable.
|
class A { public int meth1(int a1, int a2) {…} }
class AWrapper { private A a; private boolean revoked; public int meth1(int a1, int a2) { if(!revoked) return a.meth1(a1, a2); else throw new RevokedException(); } public void revoke() { revoked=true; } public AWrapper(A realA) { a = realA; revoked = false; } } Figure
1.2 |
Naturally, the programmer can add a level of
indirection only to those objects whose protection is
critical.
Figure 1.2Figure
1.2 shows how a revocable version of the
earlier class A can be created.
Each object of A is wrapped with an
object of AWrapper, which permits
access to the wrapped object only until the
revoked flag
is set. However, it’is not always obvious which objects
require such protection. Vitek et al [
BV99REF confined types] argue that
critical, but unprotected subobjects often leak out of a protected
object through field references and method invocations.
Analyzing the security of a system requires
analyzing the communication patterns between programs.
Limited, well-defined communication channels make this easy;
unconstrained fine-grained sharing makes a mess. The Java
API, unfortunately, is quite large, making it difficult to identify
the points at which security must be enforced. One of the
downsides
of a programming language’s ability
to express abstractions is that it is all too easy to create
complex interactions between components of a system. Consider
Java’s String class, which was
originally not a final class (i.e. programs could override its
methods). Because applets and browsers exchange strings at
such a fine granularity, programmers could not track all of the
interactions that occurred through String objects, leading
to security problems in early versions of Java. Because of
this,
String was later made final [
vdLinREF Java FAQ].
Incontrast
to Java’s API, a traditional OS has a small and clearly
defined system call interface,
which
forms a single point of security
enforcement.
The Java programming language makes no distinction between objects shared between programs and objects private to a program. Yet, the distinction is critical for reasoning about the system’s security. For example, a malicious user might try to pass a byte array holding legal bytecode to a class loader (byte arrays, like other objects, are passed by reference to method invocations), wait for the class loader to verify that the bytecode is legal, and then overwrite the legal bytecode with illegal bytecode which would subsequently be executed. The only way the class loader can protect itself from such an attack is to make its own private copy of the bytecode, which is not shared with the user and is therefore safe from malicious modification.
When objects are shared at a fine granularity, which programs should be charged for the objects and how can memory usage be tracked? One solution is to charge a program for the memory that it allocates. However, this breaks down when programs share data. If program A creates an object and shares it with program B, then A is charged for the object for as long as B retainsa pointer to it, even if A is no longer using the object. Even after Ashuts down,it may be charged for memory indefinitely.
AOne
nother solution is to charge for all the
objects reachable from a program's roots. While this may work in traditional
operating systems with fixed sized shared memory buffers of "raw
data",Unfortunately, this approach it is dangerous for
when programs share abstract data
typesand pointer based data
structures. Program A can give program B what
looks like a small object, but in fact contains a private field
pointing to large amounts of A's private data, and program B gets
charged for all of A's data. In fact, B is still charged for
the data even after program A has exited, since A’s data
can’not be garbage collected while B still has
a reference to it. Fine-grained sharing looks less pleasant
when any shared object can act as a resource Trojan horse.
When compiled naively, safe languages tend to run
much more slowly than lower level languages such as C. To
reduce this performance gap, safe languages rely on relatively
sophisticated optimizations. Many optimization techniquesers
[DDG+96,
FKR+99,
Javc,
MS99,
WdFD+98, IKY+99, BCF+99, BK99] rely on global information (such as
“"this method is never overridden
and may therefore be inlined
”") that may be invalidated as code
is dynamically loaded. One way to reconcile these
whole-program optimizations with dynamic loading is to undo
optimizations as necessary when new code is loaded [
IKY+99,
HCU92,BCF+99,REFJavc]. Suppose a server uses the
Java class Vector, but never
overrides the methods of this class. In this situation, the
server may inline method invocations on objects of type
Vector. If an applet subsequently overrides
these methods, however, the server’s code must be dynamically
recompiled to remove the inlining, because the applet might pass an
object with the overridden methods to server, and the server might
invoke one of these methods. This strategy is complicated to
implement, requiring close cooperation between the compiler and
run-time system. Moreover, in a language-based protection
system, where multiple programs are loaded into a single
environment, it penalizes one program for the actions of another
program. Why should a server have to undo its internal
optimizations because of code contained in a dynamically loaded
applet?
It is difficult to predict the
performance
a program
when its optimization depends
on other programs’ code.
TThere is a theme common to all of the problems listed in the
last section
stemfrom a lack of an appropriate aggregate
structure in existing language-based protection
environments:
·
Terminating a program requires at least some sort of aggregate
structure to track which threads to stop, but this isn’ot sufficient: terminating only
threads leaves objects and code, suggesting that the aggregate
structure also encompass objects and code.
·
Analyzing the security of a system requires determining where the
boundaries between programs are; this is again an issue ofese boundaries are determined byexposing the
aggregate structure of the system
as a whole.
· Implementing revocation requires deciding which objects are sensitive enough to warrant the cost; objects shared between programs are more likely to need revocation than objects that are private to a program.
· Resource accounting requires knowing which resources belong to which program, which is again an issue of aggregate structure.
·
Whole-program optimization must account for all programs loaded
into a shared environment, which is too coarse: it would be
better to apply such analysis at a finer granularity, so that one
program’s behavior doesn’ot penalize another program’s
performance. For this, we need some aggregate structure
marking the boundaries between programs.
In this thesis, I propose an aggregate structure called a task, which consists of all of a program’s objects, code, and threads together. Tasks are analogous to traditional operating system processes and tasks. By dealing with objects, code, and threads together rather than in isolation, tasks make guarantees about the interaction between the three. For example, a task’s threads are guaranteed only to run the task’s own code—they cannot cross over a task boundary and run someone else’s code. Since Java objects contain code as well as data, implementing this guarantee requires distinguishing method calls on a task’s own objects (which only contain a task’s own code) from method calls on other tasks’ objects, which requires distinguishing one task’s objects from another tasks’ objects. Thus, a task’s structure in terms of objects is intertwined with the task’s structure in terms of threads and code.
Tasks form a framework in which revocation, termination, system analysis, resource accounting, and whole-program optimization are tractable:
· Only pointers to objects in other tasks need to be revocable; pointers to a task’s own objects need not support revocation.
· When a task is terminated, its threads, code, and objects are shut down together. All pointers into the terminated task are revoked, so that the task’s objects are unreachable, and can therefore be garbage collected. Although stopping the task’s threads suddenly may produce damaged objects in the task, these objects are unreachable, so no live task will see them.
· Tasks establish a clear boundary between programs, so that analyzing inter-program communication is easier.
· Tasks provide a very simple resource accounting model: a task pays only for those objects that it explicitly allocates with the Java new operator; it is not charged for objects allocated by other tasks.
·
A compiler can perform whole program optimizations at a task
granularity, because dynamically loading code into one task does
not affect the code of other tasks. I’will call these whole-task
optimizations.
The key feature of the task model is the distinction between one task’s resources and another task’s resources. Actions on a task’s local resources differ from actions on other task’s resources. For example, the compiler or run-time system must perform revocation checks to accessremotepointers to other tasks’ objects, but not to accesslocal pointers to a task’s own objects. In addition, method invocations on remote pointers much switch threads so that a task’s thread doesnot run another task’s code.
The distinction
between
local and remote objects
mightbe enforced by the run-time
systemor bythe programmer.
To start with, consider an implementation where To implement the task model, the compiler or run-time
system’smust be able to
distinguish localpointers to a task’s own objects
from remotepointers to other tasks’ objects,
because remote pointers require dynamic revocation, and method
invocations on remote pointers much switch threads so that a
task’s thread doesn’t run another task’s
code. Conceivably, the run-time system could makes thise distinction dynamically with no explicit static directives from the
programmer. Perhaps each object would be tagged with the task
that allocated it, and every operation on an object would first
check to see whether the object is local or remote. However,
this would slow down operations on local objects and operations on
remote objects.
Even if the run-time system could implement the
local/remote distinction efficiently with no help from the
programmer, explicit programmer involvement has a several
advantages. First, remote code is more dangerous than local
code (local code is trusted, while code in another task may have
been written by an adversary), so the programmer should be aware whichknowwhich method calls are on remote objects,
so that the method’s arguments and return values are treated
with caution. Second, remote pointers are revocable, and if
remote pointers aren’t statically distinguished, any
pointer is potentially revocable. This
leaves Java programs on unsolid
shaky ground: how can a programmer
deal with a world where ordinary looking objects suddenly stop
working? For instance, suppose String objects
are
were revocable. Strings are often
used as keys for hash tables, and a standard Java hash table is
implemented as an array of linked lists, where each link holds a
key/value pair. If one of the String keys is revoked,
it will fail every time it is queried for equality. Not only
does this prevent the revoked string’s own associated value
from being retrieved, but it may also prevent
s links following it in its list from
being reached
,. I suspect that
whichthis will be completely unexpected byprobably come as a surprise to the
programmer.
Rather than have the run-time system try to
determine remoteness dynamically, another approach is to have the
programmer implement the local/remote distinction with little or no
help from the compiler and run-time system. The programmer
mentally labels all code, objects and threads with a task, and then
explicitly inserts extra code at method calls to remote objects to
handle threads, and explicitly relinquishes pointers into
terminated tasks so that they can be garbage collected.
DrScheme [
FFK+99REF] demonstrates that this
strategy can work, at least in the absence of peer-to-peer
communication. However, the more complex the interactions are
between tasks, the more work the programmer must do to track which
objects belong to which task. Furthermore, this strategy
leaves the task model to the programmer’s
discretion—the language cannot guarantee that it is
respected. Because of this, the compiler and run-time cannot
rely on the task model. This rules out whole-task
optimizations, which are unsound without the guarantee that a
task’s threads only run a task’s own code.
The strategy I adopt falls between the two
approaches just described. Enforcing the task model is not
left entirely to the run-time system nor to the programmer;
instead, the programmer gives enough information to the run-time
system for it to insert the correct revocation checks and thread
switches. With this information, the run-time system
guarantees that any well-typed program respects the task
model. The next twofollowing chapters describe
implementations of the task model based on this approach. In
the J-Kernel, the programmer creates explicit capability
objects that mark the boundaries between tasks. Method
invocations on these capability objects follow Java’s Remote
Method Invocation API and semantics, including thread switches and
passing non-capability arguments by copy. Luna, on the other
hand, modifies Java’s type system to express the boundaries
between tasks: remote pointers have special types, marked
syntactically with a ~ character.
XXX: QUOTE: I think Redell had a quote along the
lines of, "in systems, a level of indirection solves all
problems..."
I developed the J-Kernel as a prototype of the
task model.
The J-Kernel is written entirely in Java,
with no native methods and no changes to the Java bytecode format
or the underlying virtual machine. This allows the
J-Kernel to run I wanted the J-Kernel to run on
available commercial Java
platforms, since
which these
have tended to be faster thanthe
existing
customizable open source Java platforms
such as Kaffe.
It also made it easy to distribute the J-Kernel
publicly, so that others couldI wanted the J-Kernel to be publicly available
for people to
easily download
it, examine
it, and run
it on various platforms. Finally,
aJava-only implementation
is easier to develop than an extension to a
virtual machine, making it simpler to test the ideas of the task
model.I wanted the J-Kernel to be relatively simple
and easy for me to write, so that the ideas of the task model could
be tested quickly.
Because of these goals, I wrote the J-Kernel
entirely in Java, making no changes to the virtual machines used to
run the J-Kernel.
I made no changes to the Java source language
and bytecode format, since these would have prevented people from
using off-the-shelf java source-to-bytecode
compilers.
Although the J-Kernel does
not
change the virtual machine, it does However, I did make some changes to
the Java API, because the parts of the existing API were
are inappropriate to the J-Kernel's task
model. In particular, Java's ClassLoader,
Thread, and ThreadGroupclasses
contained methods that could undermine the
J-Kernel's guarantees. Therefore, these methods had to
must be hidden from the programmer.
Rather than simply eliminate these classes,
I tried to
the J-Kernel preserve
s the original Java API as much as
possible by interposing my
its own classes [
WBD+97REF Wallach et al], with the same
class and method names, but with a safer implementation of the
problematic methods. The J-Kernel uses its control over
dynamic linking to substitute the safe classes for the dangerous
classes. While this approach required no changes to the
virtual machine, it was limited in some ways, which will be
described later in the chapter.
The task model involves group
sing code, objects, and threads into
tasks, and requires a mechanism to distinguish task-local entities
from remote entities. In Java, this requires restricting the
types of objects shared between tasks in some way:
if there aren't anyno restrictions, then any objects can be
shared, method invocations on these objects can invoke arbitrary
code in other tasks, threads can cross task boundaries, and
problems with thread and task termination arise.
Nevertheless, I've found method invocation on
shared objects to be the single most useful
isa very useful communication mechanism in
Java, since they
it naturally express
es the idea of one task exporting a
service to another task. Therefore, I wanted tothe J-Kernel use
s method invocation as the basis for the J-Kernel'sits inter-task communication, but
does so in a way that accommodates
revocation and thread control. In order to ensure that code
from a terminated task isn'ot executed, and to ensure that threads
don'ot directly cross task boundaries, a
cross-task method invocation should perform a revocation check and
a thread switch. Therefore, the J-Kernel only allows special
capability objects to be shared between tasks, and ensures
that method invocations on the capability objects perform
revocation checks and simulate a thread switch.
To preserve the invariant
that only capability objects are shared between tasks, method
invocations on capability objects pass capability objects by
reference but pass other types of objects by copy. Note that
a deep copy of non-capability objects is necessary:
the method invocation must
recursively traverse and replicate all non-capability pointers in a
data structure to copy the data.
Copies, revocation checks, and thread
switches increase the cost of inter-task communication when
compared to ordinary Java method invocations. However,
section
2.7argues that this cost is acceptable for
real applications.
The semantics for method invocations on capabilities are essentially the same as the semantics of Java's Remote Method Invocations (RMI) [Javd], which supports method invocations over a network. Because of this similarity, the J-Kernel bases much of its API on the Remote Method Invocation API. This section describes RMI in detail, so that the J-Kernel’s interface presented in the following sections will make sense.
RMI divides objects into two categories:
·
Serializable objects are passed by deep copy through remote
method invocations. Serializable objects must belong to a
class that implements the interface Serializable. The
Serializable interface has no methods, but serves as
a flag to let the run-time system marshal the object into a
platform-independent byte stream (a
“"serialized"” version of the object). RMI
serializes an object, recursively serializing data pointed to by
the object, sends the bytes over a network, and deserializes
(unmarshals) the bytes on a remote computer to form a deep copy of
the original object.
·
Remote objects are passed by reference through remote method
invocations. Remote objects must belong to a class that
implements one or more remote interfaces, where a remote
interface is an interface that extends the interface
Remote. All methods declared in the remote
interfaces may be invoked on a remote reference (a
“"stub"”) to a remote object. Like
Serializable, Remote has no methods
and serves only as a flag to the run-time system to identify remote
objects, and to identify which methods of a remote object may be
invoked remotely.
If an object is neither remote nor serializable, then it cannot be passed through a remote method invocation.
Here isFigure
2.1Figure
2.111shows an example of serializable objects
passed through an RMI invocation:
|
class Request implements Serializable { String path; byte[] content; }
interface Servlet extends Remote { byte[] service(Request req) throws RemoteException, IOException; }
class FileServlet implements Servlet { public byte[] service(Request req) throws RemoteException, IOException { // Open a file and return the data contained in the file: FileInputStream s = new FileInputStream(req.path); byte[] data = new byte[s.available]; s.read(data); s.close(); return data; } } Figure 2.1: Serializable object passed through RMI |
Since FileServlet implements the remote interface Servlet, it can be passed from one machine to another as a reference to a remote object. Both byte[] and Request are serializable, and may be passed by copy through remote invocations on the service method. Notice how the semantics of remote method invocation differ from local invocation: invocations of the service methods on a local Servlet object would pass and return the Request and byte[] objects by reference rather than by copy.
|
interface DispatchServlet extends Servlet { void addServlet(String path, Servlet servlet) throws RemoteException; }
class SimpleDispatcher implements DispatchServlet { Hashtable servletTable = new Hashtable();
public void addServlet(String path, Servlet servlet) throws RemoteException { servletTable.put(path, servlet); }
public byte[] service(Request req) throws RemoteException, IOException { Servlet s = (Servlet) servletTable.service(req.path); return s.get(req); } } Figure
2.2 |
A DispatchServlet object
, shown in
Figure 2.2Figure
2.212, forwards requests to other servlets by
making remote invocations on their service methods. A
remote invocation on the addServlet method passes
a
String object by copy and the
Servlet
argument by reference, since String is serializable
and
Servlet implements remote interfaces. For
example, a function with a remote reference to a
DispatchServlet object can create and add a new
servlet as follows:
void makeFileServlet(DispatchServlet d)
throws RemoteException
{
d.addServlet("foo/servlet", new FileServlet());
}
Figure
2.33: Remote method invocation example
This simple example hides a large amount of complexity. In particular as the new FileServlet object is passed from one machine to another in the remote method invocation to addServlet, stub objects for the FileServlet object are automatically generated on both machines.
The combination of pass by reference and pass by copy make RMI a flexible and easy to use communication mechanism. In fact, I could have simply used Java's RMI implementation, which is a standard part of most virtual machines, as the J-Kernel's communication mechanism. However, the existing RMI implementations were orders of magnitude slower than what I desired. Furthermore, at the time I wrote the J-Kernel, the RMI specification did not support revocation. Although revocation support has since been added to RMI, in the JDK1.2's Remote.unexportObject method, this support is less explicit than J-Kernel's support. The key difference is that RMI implicitly creates stubs to remote objects when the remote objects are passed through a remote invocation. Because these stubs are outside the programmer's control, RMI’s revocation abilities are limited: revoking access to a remote object revokes everyone's access to it. In other words, RMI's revocation is not selective.
By contrast, the J-Kernel makes a visible
distinction between the original object and capability objects that
act as remote stubs for the original object. An object
implementing remote interfaces cannot be passed directly from one
task to another. Instead, the programmer first calls the
static
Capability.create method, which takes an object
implementing remote interfaces and returns a capability (a
stub object) that points to the original object, which I'will call the target object.
The capability implements all the remote interfaces implemented by
the target object. Invocations on the methods of the
capability's remote interface are redirected to the target object
after copying the arguments and switching to the target object's
task.
In addition to implementing the remote interfaces, the capability object extends the class Capability, which contains a public method revoke that revokes access to the capability:
public class Capability
{
public static Capability create(Remote obj);
public final void revoke() throws SecurityException;
...
}
Figure
2.44: The Capability class
Capability.create is the only mechanism available to the programmer to create instances of the class Capability; the J-Kernel prevents programs from directly instantiating a subclass of Capability. This ensures that all capability instances implement the semantics specified by Capability.create.
Despite the distinction between RMI stubs and J-Kernel capabilities, programs written for J-Kernel are very similar to programs designed for RMI. For example, the code shown above for the Request, Servlet, FileServlet, DispatchServlet, and SimpleDispatcher run on the J-Kernel with no modification. The makeFileServlet function, however, must be changed to create an explicit capability, rather than relying on implicit stub creation:
void makeFileServlet(DispatchServlet d)
throws RemoteException
{
Capability c = Capability.create(new FileServlet());
Servlet s = (Servlet) c;
d.addServlet("foo/servlet", s);
}
Figure
2.55: Creating a capability
In the makeFileServlet example, the call to Capability.create expresses a task's desire to export a service to other tasks. In fact, the primary purpose of Capability.create is to explicitly mark the establishment of inter-task communication channels. This aids in analyzing a program's communication patterns; a simple way to look for the communication entry points into a task is to search for all the task's calls to Capability.create. Whereas RMI is often used to transparently spread a single protection domain across many virtual machines, the J-Kernel is designed to protect multiple domains running in a single machine. Thus, while RMI tries to hide boundaries, the J-Kernel seeks to expose boundaries.
A second purpose of Capability.create is to provide selective revocation. After a task creates a capability, it can revoke it by calling the capability's revoke method. When a capability is revoked, its pointer to its target object is overwritten with null, causing all future invocations of the capability's remote interface methods to fail by raising an exception. In addition, since a revoked capability no longer points to the target object, the target object may be eligible for garbage collection, so that one task cannot use a revoked capability to prevent another task from collecting garbage.
If a task creates multiple capabilities for a single target object, it can selectively revoke access to the target object by revoking some of the capabilities while leaving other capabilities unrevoked:
FileServlet f = new FileServlet();
Capability c1 = Capability.create(f);
Capability c2 = Capability.create(f);
...
// Revoke c1 but not c2:
c1.revoke();
Figure
2.66: Selective revocation
The target object of a capability may itself be a capability [Red74]:
FileServlet f = new FileServlet();
Capability c1 = Capability.create(f);
Capability c2 = Capability.create(c1);
...
c1.revoke();
Figure
2.77: Multiple indirection
In this case, c2 serves as a restricted version of c1. c2 can be revoked without revoking c1, though if c1 is revoked, c2 is effectively revoked.
A task cannot revoke a capability created by a
different task; if
a task calls the revoke method on someone
else's capability, the revoke method throws a
SecurityException. This
wais the
a simplest form of access control to the
revoke method;
the need for more complex schemes, such as
access control lists or special revocation capabilities, didnot seem justifieddid not arise in practice.
A third purpose of Capability.create
is clear semantics. Capability objects pass through
cross-task method invocations without changing their identity, so
that Java instanceof and
== operators behave predictably when applied to
capability objects. For languages like
Standard ML, which have no such operators
for immutable values, this isn'ot as important of an issue.
So far, this chapter has
arguments motivat
eding the design of the J-Kernel, and
the existence of Capability.create in
particular. Now it'is time to examine the implementation of
Capability.create in detail. Consider a
capability based the following remote interface:
interface I extends Remote
{
int f(int x, int y) throws RemoteException;
}
class C implements I {...}
I target = new C();
Capability c = Capability.create(target);
Figure
2.88: Capability creation example
This call to Capability.create
generates a stub object that implements the remote interface
I and points to the C target object.
This stub object is an instantiation of a class generated
dynamically by the J-Kernel the first time a
C object is
passed to Capability.create.
The dynamically generated class looks roughly likeis depicted in
Figure 2.9Figure
2.9.:
|
public class C$STUB$LRMI extends Capability implements I { private C target;
public int f(int x, int y) throws RemoteException { ThreadTaskState state = getThreadTaskState(); Task sourceTask = state.currentTask; ThreadSegment callerThreadSegment = state.activeThreadSegment;
try { state.switchIn(targetTask); int ret = target.f(x, y); state.switchOut(sourceTask, callerThreadSegment);
return ret; } catch(Throwable e) {...} }
... } Figure
2.9 |
The code shown
in
Figure 2.9Figure
2.9above is written as Java source
code; in reality, the J-Kernel generates Java bytecode, which is
passed to a class loader directly, without requiring
source-to-bytecode compilation.
The stub class C$STUB$LRMI belongs to
the same package as C, so that it has access
to
C even if C is not public.
The stub class is
a subclass of Capability, so
that it inherits the revoke method, and
implements the I remote interface,
which declares the method f. The generated
implementation of f forwards each
cross-task call to the target object in the line "“int ret = target.f(x,
y);"”. In addition, f
performs three actions: it checks for revocation, it switches
thread segments, and it copies arguments.
The revocation check is crude but
efficient: when the capability's revoke method is
called, its target field is set to
null. This causes the method invocation
“"target.f(x, y)"” to raise a null pointer exception,
so that
the capability is unusable.
Thread segment switching is a little more
complicated. According to the task model, threads should not
migrate across task boundaries, so a cross-task call should switch
to a new thread in the callee's task, rather than running in the
caller's thread. However, the expense of switching threads
would increase the cost of a cross-task call by an order of
magnitude on a typical virtual machine. Therefore
, the J-Kernel compromises the task model
to a certain extent:
the caller and callee run in the
same thread, but run in different thread segments.
Conceptually, the J-Kernel divides each Java
thread into a stack of thread segments. In each
cross-task call, the J-Kernel pushes a new segment onto this
stack. When the call returns, the thread segment is
popped. The J-Kernel class loader then hides the system
Thread class that manipulates Java threads, and
interposes its ownThread
class with an identical interface but an
implementation that only acts on the local thread segment.
The key difference is thatThread modification
methods such as stop and
suspend act on thread segments rather than Java
threads, which prevents the caller from modifying the callee's
thread segment and vice-versa. This provides the illusion of
thread-switching cross-task calls, without the overhead for
actually switching threads. The illusion is not totally
convincing, however—cross-task calls really do block, so
there is no way for the caller to gracefully back out of one if the
callee doesn'ot return.
This problem is one drawback of a Java-only
implementation, which
cannot
control
threads and stacks
at a low level (chapter 4
describes how a customized virtual machine
can
implementthread switching
efficiently).
Each J-Kernel thread holds a
ThreadTaskState object which
that tracks which task the thread is
currently running in, and which thread segment is the topmost
segment on the thread's stack of segments. A capability
switches thread segments by calling the method
switchIn to
move to a new thread segment, and switchOut to return to
the original caller segment
(see
Figure 2.10Figure
2.10). For efficiency,
switchIn does not create allocate a new thread
segment object immediately, and
but instead creates one on demand if the
callee later calls the method Thread.currentThread to
get the Thread object that
corresponds to the new thread objectsegment. Otherwise, no thread
segment object is allocated for the callee. The
switchIn method does, however, make a note that the
thread is now running in another task, so that the J-Kernel's task
termination mechanism can discover which threads are running in a
task that is about to be terminated. In addition, the
switchIn and switchOut methods are
declared synchronized, in order to coordinate with the task
termination mechanism (this will be discussed in detail below).
|
public synchronized void switchIn(Task targetTask) { // Set the thread's current thread segment and current task // to point to the callee: activeThreadSegment = null; // new segment created lazily currentTask = targetTask; // thread now in the target task }
public synchronized void switchOut(Task sourceTask, ThreadSegment callerThreadSegment) { // Set the thread's current thread segment and current task // to point to the caller. currentTask = sourceTask; activeThreadSegment = callerThreadSegment;
// Check to see if the caller's thread segment's state has // changed since we last saw it (for instance, the thread // segment may have been suspended or stopped, or the caller // task may have been killed entirely). If so, take the // appropriate action: if(callerThreadSegment != null && callerThreadSegment.alertFlag) { ...If segment was suspended, wait until it is resumed ...If segment was stopped, throw a ThreadDeath exception |