(i.e., LT OT L). Objects can be likewise unreferenced from container C by any thread that can write to C. When an object has
no more references, the kernel deallocates it. Unreferencing
a container causes the kernel to recursively unreference the
entire subtree of objects rooted at that container.
Containers also help HiStar address a possible covert
channel through object reference counting. Any thread T can
create a hard link to segment S in container C if it can write C
(i.e., LT OT LC OT LT). T can thus prolong S’s life even without
permission to modify S; in our virus-scanner example from
Figure 2, this might be the malicious scanner process signaling secret information by prolonging or not prolonging
the life of the database file. Another thread T′, such as the
update process, could then remove any known links to S and
observe whether it can still access S by its object ID, even if T
was not allowed to communicate to T′.
To avoid this problem, most system calls name objects by
〈container ID, object ID〉 pairs, called container entries. For
T′ to use container entry 〈C, S〉, C must contain a link to S
and T ′ must be able to read C (i.e., LC OT′ LT′). In the virus-scanner example, the untainted update process would not
be able to use any container entry created by the tainted
scanner. Container entries allow the kernel to check if a
thread has permission to know if the object exists, in addition to any other label checks necessary to access the object.
2. 5. address spaces
Every running thread has an associated address space object
containing a list of VA → 〈S, offset, npages, flags〉 mappings.
VA is a page-aligned virtual address. S = 〈C, O〉 is a container
entry for a segment to be mapped at VA. offset and npages
can specify a subset of S to be mapped, flags specifies read,
write, and execute permission (and some convenience bits
for user-level software).
Each address space A has a label LA, to which the usual label
rules apply. Thread T can modify A only if LT OT LA OT LT,
and can observe or use A only if LA OT LT. When launching
a new thread, one must specify its address space and program counter. The system call self_set_as allows threads to
switch address spaces. When thread T takes a page fault, the
kernel looks up the faulting address in T’s address space to
find a segment S = 〈C, O〉 and flags. If flags allows the access
mode, the kernel checks that T can read C and O (LC OT LT
and LO OT LT). If flags includes writing, the kernel additionally checks that T can modify O (LT OT LO). If no mapping is
found or any check fails, the kernel calls up to a user-mode
page-fault handler (which by default kills the process). If the
page-fault handler cannot be invoked, the thread is halted.
2. 6. Gates
Gates provide protected control transfer, allowing a thread
to jump to a predefined program counter in another address
space with additional privilege. A gate object G has an ownership set Og, a guard set Gg, and thread state, including the
container entry of an address space, an initial program counter and stack pointer, and some closure arguments for the
initial function. The guard set controls what other threads can
invoke this gate, by requiring the caller to own all categories
in Gg. A thread T can allocate a gate G only if Og ⊆ Ot. A thread
T ′ invoking G must specify a requested ownership set, Or, to
acquire upon invocation; invocation is permitted when OT ⊆ Gg
and Or ⊆ (Ot ∪ Og). Gate objects are largely immutable (and
thus subject to the parent container’s label); the gate label Lg
applies only to the gate object’s (rarely-used) metadata.
Gates are often used like an RPC service. Unlike typical
RPC, where the RPC server provides the resources to handle the request, gates allow the client to donate initial
resources—namely, the thread object which invokes the
gate. Gates can also be used to transfer privilege. The use
of gates is discussed further in Section 3. 5.
3. uNiX LiBRaRy
Unix provides a general-purpose computing environment
familiar to many people. In designing HiStar’s user-level
infrastructure, our goal was to provide as similar an environment to Unix as possible except in areas where there were
compelling reasons not to—for instance, user authentication, which we redesigned for better security. As a result,
porting software to HiStar is relatively straightforward; code
that does not interact with security aspects such as user
management often requires no modification.
Hi Star’s Unix environment is implemented in a library that
emulates the Linux system call interface, comprising approximately 20,000 lines of code and providing abstractions like file
descriptors, processes, fork and exec, file system, and signals.
All of these abstractions are provided at user level, without
any special privilege from the kernel. Thus, all information
flow, such as obtaining the exit status of a child process, is
made explicit in the Unix library. A vulnerability in the Unix
library, such as a bug in the file system, compromises only
threads that trigger the bug—an attacker can exercise only
the privileges of the compromised thread, likely causing far
less damage than a kernel vulnerability. An untrusted application, such as a virus scanner, can be isolated together with
its Unix library, allowing for control over Unix vulnerabilities.
Most GNU software runs on HiStar without any source
code modifications, including bash, gcc, gdb, and X; the
main exception is OpenSSH, which requires small changes
for user authentication and login code. The rest of this
section discusses the design and implementation of our
Unix emulation library.
3. 1. file system
The HiStar file system uses segments and containers to implement files and directories, respectively. Each file corresponds
to a segment object; to access the file contents, the segment
is mapped into the thread’s address space, and any reads or
writes are translated into memory operations. The implementation coordinates with the user-mode page fault handler to
return errors for invalid read or write requests. A file’s length
is defined to be the segment’s length. Additional state, such
as the modification time, is stored in the object’s metadata.
A directory is a container with a special directory segment
mapping file names to object IDs. A mutex in the directory segment serializes operations; for example, atomic
rename within a directory is implemented by obtaining
the directory’s mutex lock, modifying the directory segment to reflect the new name, and releasing the lock.