dates back to Multics.
16 Unlike Multics rings, HiStar’s protection domains are not hierarchical. HiStar gates are more
like doors in Spring.
Decentralized untainting, while new in operating systems, was previously provided by programming languages,
13 Jif can track information flow at the level of individual variables and perform most label checks at compile
time. However, Jif relies on the operating system for storage,
trusted input files, administration, etc., which avoids many
issues HiStar needs to address.
SELinux11 lets Linux support MAC; like most MAC
systems, policy is centrally specified by the administrator. In
contrast, HiStar lets applications craft policies around their
own categories. Retrofitting MAC to a large existing kernel
such as Linux can be error-prone, especially given the sometimes ill-specified semantics of Linux system calls. HiStar’s
disciplined, small kernel can potentially achieve much
higher assurance at the cost of compatibility.
6. DiscussioN aND LimitatioNs
The current prototype of HiStar supports x86-64, i386,
SPARC, and ARM computers. The fully trusted kernel,
including device drivers for any given machine, is approximately 20,000 lines of code. We expect that drivers can eventually be moved to untrusted user-space processes with the
help of IOMMU hardware. We have found performance to be
reasonable for Unix applications.
Users familiar with Unix will find that, though HiStar
resembles Unix, it also lacks several useful features and
changes the semantics of some operations. For example,
HiStar does not keep file access times; although possible
to implement for some cases, tracking time of last access
is in many situations fundamentally at odds with information flow control. Another difference is that chmod, chown,
and chgrp revoke all open file descriptors and copy the file
or directory. Because each file has one read and one write
category, group permissions require a file’s owner to be in
the group. There is no file execute permission without read
permission, and no setuid bit (though gates arguably provide
a better alternative to both).
While trusted components can control how secret data
is revealed, it is difficult to reason about what secret data is
revealed. For example, wrap can ensure the scanner’s output is sent only to the user’s terminal, but it would be difficult to safely reveal even one bit of information from the
scanner’s output to the public (e.g., are any of the user’s files
infected?), since we must conservatively assume that the
scanner’s output may reveal any bit about the user’s data.
HiStar is a new operating system that provides strict infor-
mation flow control without superuser privilege. Narrow
interfaces allow for a small trusted kernel of less than 20,000
lines, on which a Unix-like environment is implemented in
untrusted user-level library code. A new container abstrac-
tion lets administrators manage and revoke resources
for processes they cannot observe. Side-by-side with the
Unix environment, the system supports a number of high-
security, privilege-separated applications previously not
possible in a traditional Unix system. HiStar is available at
We thank Martin Abadi, Michael Reiter, and Michael Walfish
for helping improve this paper, and many others that provided feedback on earlier papers.
18–20 This work was funded
by joint NSF Cybertrust/DARPA grant CNS-0430425, by NSF
Cybertrust award CNS-0716806, by the DARPA Application
Communities (AC) program as part of the VERNIER project at Stanford and SRI International, and by a gift from
Lightspeed Venture Partners.
1. bell, d.e., la Padula, l. Secure
Computer System: Unified Exposition
and Multics Interpretation. technical
report mtr-2997, rev. 1, mItre
Corporation, bedford, ma,
2. biba, K. J. Integrity Considerations
for Secure Computer Systems.
technical report mtr-3153, mItre
Corporation, bedford, ma,
3. bomberger, a. C., Frantz, a.P., Frantz,
w.s., hardy, a. C., hardy, n., landau,
C.r., shapiro, J.s. the KeyKos
In Proceedings of the USENIX
Workshop on Micro-Kernels and
Other Kernel Architectures, april
4. efstathopoulos, P., Krohn, m.,
Vandebogart, s., Frey, C., Ziegler, d.,
Kohler, e., mazières, d., Kaashoek, F.,
morris, r. labels and event processes
in the asbestos operating system.
In Proceedings of the 20th SOSP
(brighton, u.K., october 2005),
5. Fraser, t. lomaC: low water-mark
integrity protection for Cots
environments. In Proceedings of the
IEEE Symposium on Security and
Privacy (oakland, Ca, may 2000),
6. hamilton, g., Kougiouris, P. the spring
nucleus: a microkernel for objects.
In Proceedings of the Summer 1993
USENIX (Cincinnati, oh, april 1993),
7. Krohn, m., efstathopoulos, P., Frey, C.,
Kaashoek, F., Kohler, e., mazières, d.,
morris, r., osborne, m., Vandebogart,
s., Ziegler, d. make least privilege a
right (not a privilege). In Proceedings
of the 10th Workshop on Hot Topics
in Operating Systems (santa Fe, nm,
8. Krohn, m., yip, a., brodsky, m., Cliffer,
n., Kaashoek, m.F., Kohler, e., morris, r.
Information flow control for standard
os abstractions. In Proceedings of the
21st SOSP (stevenson, wa, october
9. landwehr, C.e. Formal models for
computer security. Comput. Surv. 13, 3
(september 1981), 247–278.
10. leyden, J. anti-virus vulnerabilities
strike again. The Register, march
2005. http://www.theregister. co.uk/
11. loscocco, P., smalley, s.
Integrating flexible support
for security policies into the linux
operating system. In Proceedings
of the 2001 USENIX (boston,
ma, June 2001), 29–40, FreenIx
12. mcIlroy, m.d., reeds, J.a. multilevel
security in the unIx tradition.
Soft w. Pract. Exp. 22, 8 (1992),
13. myers, a.C., liskov, b. Protecting
privacy using the decentralized label
model. Trans. Comput. Syst. 9, 4
(october 2000), 410–442.
14. naraine, r. symantec antivirus
worm hole puts millions at
risk. e Week.com, may 2006.
15. Peterson, d. anti-virus rife with
January 2008. http://www.digitalbond.
16. schroeder, m.d., saltzer, J.h.
a hardware architecture for
implementing protection rings.
In Proceedings of the 3rd SOSP
(new york, march 1972), 42–54.
17. shapiro, J.s., smith, J.m., Farber, d. J.
eros: a fast capability system.
In Proceedings of the 17th SOSP
(Island resort, sC, december 1999),
18. Zeldovich, n., boyd-wickizer, s., Kohler,
e., mazières, d. making information
flow explicit in histar. In Proceedings
of the 7th OSDI (seattle, wa,
november 2006), 263–278.
19. Zeldovich, n., boyd-wickizer, s.,
mazières, d. securing distributed
systems with information flow
control. In Proceedings of the 5th
NSDI (san Francisco, Ca, april 2008),
20. Zeldovich, n., Kannan, h., dalton, m.,
Kozyrakis, C. hardware enforcement
of application security policies.
In Proceedings of the 8th OSDI
(san diego, Ca, december 2008),
21. Zoller, t. Clamav 0.94 and below—
evasion and bypass due to
malformed archive. april 2009.
nickolai Zeldovich, massachusetts
Institute of technology, CsaIl,
Silas Boyd-Wickizer, massachusetts
Institute of technology, CsaIl,
© 2011 ACM 0001-0782/11/11 $10.00
Eddie Kohler, university of California,
los angeles, Ca.
David Mazières, stanford university,