associating a label with every piece of user-visible state in
the system—such as the registers of a thread, the length of
a segment, and even the label of an object itself—and using
the relation to decide if a given thread should be allowed
to observe or modify that state. As long as every piece of kernel state that can, directly or indirectly, influence execution
of user code has a consistent label, then ’s transitivity guarantees security: if data from thread A can affect some piece of
kernel state X, and data from X can flow to some other thread
B, then we must have checked that LA LX and LX LB, which
implies LA LB, so it was safe for data to flow from A to B. The
key to ensuring transitivity lies in associating a consistent
label with each piece of kernel state regardless of how the user
code tries to, directly or indirectly, learn its value or modify it.
The bulk of HiStar’s kernel state resides in kernel objects.
For example, the simplest type of object is a segment, which
contains a variable-length byte array. When thread T attempts
to read segment S, either by issuing a system call or by triggering a page fault, the kernel checks that LS OT LT. Likewise,
when thread T attempts to write S, the kernel checks that
LT OT LS OT LT . (The kernel ensures that data is allowed to
flow from T to S and vice versa; our experience suggests it is
difficult to write to an object without receiving some information as to whether the write succeeded.) As another example, a
network device object’s payload is (logically) all of the packets
on the Ethernet network. To send or receive a packet, a thread
must be able to write or read the network device, respectively,
with rules identical to those for a segment.
Each object also contains the object’s ID, the label, and
a 64-byte mutable, user-defined metadata buffer (used by
user-level code to, for instance, track modification times).
The metadata buffer can logically be thought of as part of
the mutable object contents, and is subject to the same read
and write rules as the object contents. On the other hand,
the label of an object O, LO, presents a challenge: how should
we label LO’s bytes? Suppose that we used LO as the label of
the entire object O, including LO itself. If a thread tries to
read O and is denied access, it learns something about the
contents of LO, even though this flow was prohibited.
To solve this chicken-and-egg problem, HiStar logically
associates O’s parent container’s label with the bytes comprising LO (as a special case, the root container is its own
parent). Furthermore, because O might reside in multiple
parent containers, HiStar requires that object labels be specified at creation and then immutable (except for threads,
as we discuss later).
To deal with on-disk state, HiStar provides a single-level
store: on bootup, the entire system (including threads)
is restored from the most recent on-disk snapshot. This
eliminates the need for trusted boot scripts to reinitialize
processes that would not survive a reboot on traditional
operating systems. It also achieves economy of mechanism
by allowing the file system to be implemented with the same
kernel abstractions as virtual memory, without any additional mechanisms for labeling on-disk state.
Finally, the kernel maintains a small amount of state outside of kernel objects, namely, the counter used to generate
new object and category IDs. Newly allocated IDs must have
two properties: first, they must be unique, and second, they
must disclose almost no information about the state of the
system, such as the number of previously allocated objects
(almost because by definition, a new ID reveals the fact that this
exact ID value was never allocated before). HiStar generates
IDs by encrypting a counter with a block cipher. Since the block
cipher is a pseudo-random one-way function, an attacker cannot learn any information from the value of the ID itself, and
since the block cipher is a permutation, the IDs are unique.
2. 3. threads
Each thread T has a label LT and an ownership set OT, which
can be changed through two mechanisms. First, a thread
can allocate a fresh category by invoking the system call
• cat_t create_category (cat_type t),
which chooses a previously unused category, c, and adds c to OT.
The type of the category (secrecy or integrity) is specified by t. At
this point, T is the only thread that owns c, and since c was never
used before, granting T ownership of c confers no other privi-
leges. In this sense, labels are egalitarian: no thread has any
inherent privileges with respect to categories created by other
threads. T can also drop categories from its ownership set.
2. 4. containers
Because HiStar has no notion of superuser yet allows any
software to create protection domains, nothing prevents a
buggy thread from allocating resources in some new, unobservable, unmodifiable protection domain. To ensure that
such resources can nonetheless be reclaimed, HiStar provides hierarchical control over object allocation and deallo-cation through containers. Like Unix directories, containers
hold hard links to objects. There is a specially designated root
container, which can never be deallocated. Any other object is
deallocated once there is no path to it from the root container.
Figure 3 shows the possible links between containers and
other types of objects.
When allocating an object, a thread must specify the con-
tainer into which to place the object. For example, to create
a container, thread T makes the system call
• id_t container_create (id_t C, label_t L).
Here C is the object ID of an existing container, into which the
newly created container will be placed. L is the desired label
for the new container. The system call succeeds only if T can
write to C (i.e., LT OT LC OT LT) and allocate an object of label L