Making Information Flow
Explicit in HiStar
HiStar is a new operating system designed to minimize the
amount of code that must be trusted. HiStar provides strict
information flow control, which allows users to specify
precise data security policies without unduly limiting the
structure of applications. HiStar’s security features make it
possible to implement a Unix-like environment with acceptable performance almost entirely in an untrusted user-level
library. The system has no notion of superuser and no fully
trusted code other than the kernel. HiStar’s features permit
several novel applications, including privacy-preserving,
untrusted virus scanners and a dynamic Web server with
only a few thousand lines of trusted code.
Many serious security breaches stem from vulnerabilities in application software. Despite an extensive body of
research in preventing, detecting, and mitigating the effects
of software bugs, the security of most systems ultimately
depends on a large fraction of the code behaving correctly.
Unfortunately, experience has shown that only a handful of
programmers have the right mind-set to write secure code,
and few applications have the luxury of being written by
such programmers. As a result, we see a steady stream of
high-profile security incidents.
How can we build secure systems when we cannot trust
programmers to write secure code? One hope is to separate
the security critical portions of an application from the
untrusted bulk of its implementation; if security depends
on only a small amount of code, this code can be verified
or implemented by trustworthy parties regardless of the
complexity of the application as a whole. Unfortunately,
traditional operating systems do not lend themselves to
such a division: they make it too difficult to predict the full
implications of every action by untrusted code.
7 HiStar is a
new operating system designed to overcome this limitation.
HiStar enforces security by controlling how information
flows through the system. Hence, one can reason about
which components of a system may affect which others
and how, without having to understand those components
themselves. Specifying policies in terms of information
flow is often much easier than reasoning about the security
implications of individual operations.
As an example, let us consider anti-virus software, which
often has full access to all files on a user’s computer. There
have been critical vulnerabilities discovered in virus scan-
ners from Norton,
10 and others15 that allow attack-
ers to take full control of the scanner. Such vulnerabilities
can easily be exploited to, at the very least, steal private data
from millions of users. To prevent such a disaster, we might
switch to the simpler, open-source ClamAV virus scanner.
However, it has suffered from security vulnerabilities in the
21 and is over 40,000 lines of code—large enough that
hand-auditing the system to eliminate vulnerabilities would
be an expensive and lengthy process at best. Yet a virus scan-
ner must periodically be updated on short notice to counter
new threats, in which case users would face the unfortunate
choice of running either an outdated virus scanner or an
unaudited one. A better solution would be for the operat-
ing system to enforce security without trusting ClamAV to
keep the user’s data private, thereby minimizing potential
damage from ClamAV’s vulnerabilities.
This work was originally presented at the 7th Symposium
on Operating Systems Design and Implementation and
the 5th Symposium on Networked Systems Design and