figure 3. kernel object types in histar. Soft links name objects by a particular ⟨container iD, object iD⟩ container entry. threads and gates are represented by rounded rectangles to indicate they are the only objects that have ownership privileges.

Container
Hard link
Soft link
Gate
Thread
Network
Device
Segment
Address
Space

(thread-local)

Segment

device (which can send and receive packets), a thread (a set of CPU registers, along with the name of an address space object), a gate (an IPC mechanism), and a container (a directory-like object in which all other objects reside).

Each object has a unique 64-bit object ID and a label that is used to control information flow to or from that object. All of the state accessible to user processes is stored in kernel objects (except for a few global variables, such as the counter used to allocate fresh object IDs). Thus, to read or write any data, processes must invoke the kernel (e.g., issue a system call or trigger a page fault to access a memory-mapped file). Upon receiving such a request, the kernel compares the labels of the currently executing thread and the objects being accessed to decide whether the operation should be permitted. While it is not possible to interpose on every read and write to memory-mapped files, the kernel remembers all active memory mappings and invalidates them when it suspects access should no longer be allowed (e.g., when a thread's label changes).

2. 1. Labels

Before discussing the kernel interface further, we first describe HiStar’s labels more precisely. HiStar associates a label with every kernel object. The purpose of a label is to provide a conservative estimate of what kind of data might be present in an object.

Generalizing the virus-scanner example shown in Figure 2, there may be multiple kinds of secret data in a system, perhaps belonging to different users. HiStar uses the notion of secrecy categories to distinguish between different kinds of secret data (a category is just an opaque 64-bit identifier), and a label is simply a set of categories. For example, in Figure 2, lightly shaded components have one specific secrecy category in their label; processes and files not shown in the figure can be labeled with one or more other categories. Data can flow from object A to object B only if B’s label includes all of the secrecy categories in A’s label. This is similar to the Bell-LaPadula model, 1 and ensures that any data marked secret remains in objects marked secret.

Secrecy categories help control where secret data can
end up, but it is also important to control where data comes
from. For instance, the virus scanner may want to ensure
its virus database has not been corrupted by another appli-
cation, and one user may want to prevent other users from
overwriting his files. To address this problem, HiStar pro-
vides a second type of category—an integrity category. The
type of a category is stored in the high bit of the category’s
64-bit identifier, but in the rest of this paper we will use
the notation cr to indicate a secrecy (read) category and cw
to indicate an integrity (write) category. Object labels can
include both secrecy and integrity categories, but the rules
for integrity categories are the opposite of secrecy: data can
flow from A to B only if A’s label includes all of the integrity
categories in B’s label. This is analogous to the Biba integ-
rity model, 2 and ensures that high-integrity files can be
modified only by high-integrity sources.

2. 2. Labeling kernel state