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