The KeyKOS System

 
 
Architecture Papers
 
Operating Environments
 
Miscellaneous Notes
 
Patents
 
Key Logic Documents
 
Bibliography
 

KeyKOS ® is a persistent, pure capability operating system. In talking about it with many people over the past few years, I've received many requests for papers and other information. This page is an attempt to collect KeyKOS-related information in one place. The collection of papers provided here is available thanks to the cooperation of the publishers, the authors, and some seriously overworked OCR software.

EROS (the Extremely Reliable Operating System) is a close derivative of KeyKOS that runs on Intel-family machines. Further information on EROS can be found at the EROS Home Page

While the Key Logic documents have been placed in the public domain by Key Logic, most of the documents provided here remain copyrighted. Since we would like to keep the available, we ask that you redistributed these documents only if the copyright permits you to do so. If you wish to distribute the documents in some other way, please contact the copyright holders.

This page is not operated by Key Logic, Inc., and I have no affiliation with the company beyond a friendship with several of the key people.


Architecture Papers

The following papers provide a general overview of the KeyKOS system. If you are interested in learning about KeyKOS, my recommendation is to read all of these papers in the order listed:

    GNOSIS - A Prototype Operating System for the 1990's  (1979)
    Provides a general introduction to some of the ideas in KeyKOS, with particular attention to the benefits of the capability approach.

    KeyKOS - A Secure, High-Performance Environment for S/370  (1988)
    Provides more history on KeyKOS, and a concise rationale for its construction. Most importantly, this paper provides a clear presentation of the KeyKOS architecture.

    The KeyKOS Architecture  (1985)
    Provides an extremely dense and precise description of the KeyKOS architecture. This is, in most respects, the definitive description of the architecture. This paper is also available in postscript form.

    The Checkpoint Mechanism in KeyKOS  (1992)
    Provides a detailed description of the checkpoint mechanism in KeyKOS and it's implementation. The KeyKOS checkpoint mechanism imposes less than 0.8% overhead. The techniques make interesting reading.

    The KeyKOS NanoKernel Architecture (1992)
    The most recent attempt to provide an architectural overview, this one intended for readers who are coming from the UNIX perspective. In addition, this paper provides an overview of KeyNIX, the prototype UNIX implementation that runs on top of KeyKOS. This paper is also available in postscript form.

Operating Environments

The following two papers describe some system facilities that have been implemented on top of KeyKOS. The nanokernel paper also provides a general introduction to KeyKOS that is targeted to a UNIX-oriented audience:

    Object Oriented Transaction Processing in the KeyKOS Microkernel  (1993)
    Describes the KeyKOS transaction processing facility. Among other things, this paper presents a clear example of how the journaling facility is used, and represents an interesting cut on dividing up the functionality of a database system.

    The KeyKOS NanoKernel Architecture  (1992)
    In addition to providing a simplified description of the KeyKOS architecture, this paper describes KeyNIX, the prototype UNIX environment that was built on top of KeyKOS. This paper is also available in postscript form.

Miscellaneous Notes

The following notes were published in Operating Systems Review, and address various security considerations in capability systems:

    Note on the Confinement Problem  (1973)
    An early attempt by Butler Lampson to state some of the requirements for computer security, addressing both overt and covert channels.

    The Confused Deputy  (1988)
    Sometimes program must run under a combination of authorities. This leads to obscure bugs and security holes. This paper identifies the cause of the problem, and points out some solutions. The paper is also available in postscript form.

    Security in a Secure Capability-Based System  (1989)
    Points out some misunderstandings in an earlier OSR note on security requirements, and explains how use of a capability architecture lessens the overhead of security.

    A Note on “Protection Imperfect”  (1988)
    Another correction of a common misunderstanding about security requirements.

Patents

We have managed to place the text and images of the KeyKOS patent online for your perusal:

    U.S. Patent 4,584,639 - Covering the KeyKOS “Factory”
    The infamous (and much lamented - at least by me) “Factory Patent”, covering the mechanism for secure sharing of programs among mutually suspicious users.

Key Logic Documents

In addition to these documents, some others have been provided by the courtesty of Agorics, Inc. The Agorics organizing page for these documents can be found here. Some of the documentation here is very specific to the IBM 370 hardware for which the system was built.

The Gnosis Design Document, in particular, is one of the most exhaustively complete documentation trails of the design of any operating system I know about.

    KeyKOS Concepts, An Introduction is a gentle introduction to the principle ideas of KeyKOS and is aimed at potential application developers. It gives some examples of how to solve application specific security problems.

    The Gnosis Design Document is a working document that was built over a period of years during which KeyKOS (Then called Gnosis) was under design and construction. It is specific to the IBM 370 architecture and details how object-based design can be applied to those aspects of the system that are indeed necessarily machine specific. This document describes the function of the privileged code as well as the fundamental facilities that might now be called an API.

    KeyKOS Principles attempts to describe the state of the existing system sufficiently for application development. It is less complete historically and philosophically.

    The KeyKOS Architecture appeared originally in the Operating Systems Review. It is a high density presentation of the KeyKOS architecture and describes in detail how the system functionality is divided into objects.

    KeySAFE , used in conjunction with KeyKOS, is a system designed to meet the high B-level requirements of the Department of Defense Trusted Computer System Evaluation Criteria.

    Support This publication provides information about the support of Guest Environments in KeyTECH.

    References This document provides information on the use of C programming language in the KeyKOS environment.

Bibliography

The following bibliography citations are provided for your convenience in referencing the KeyKOS papers.

[Bom92] Bomberger, Alan, et al., The KeyKOS NanoKernel Architecture, Proceedings of the USENIX Workshop on Micro-Kernels and Other Kernel Architectures, USENIX Association, April 1992. pp 95-112

This paper is also available in postscript form.

[Fra79] Frantz, Bill, et al., 1979 `` GNOSIS - A Prototype Operating System for the 1990's'', Proceedings of SHARE 52 I (SHARE Inc, Chicago) March 1979. pp 3-17.
[Fra88] Frantz, Bill, `` KeyKOS - A Secure, High-Performance Environment for S/370'', Proceedings of SHARE 70 I (SHARE Inc, Chicago). February 1988. pp 465-471
[Fra93] Frantz, William S. and Landau, Charles R., ``Object Oriented Transaction Processing in the KeyKOS Microkernel'', Proceedings of the USENIX Workshop on Micro-Kernels and Other Kernel Architectures, USENIX Association, September 1993.
[Har85] Hardy, Norman, ``The KeyKOS Architecture'', Operating Systems Review, v.19 n.4, October 1985. pp 8-25

The online version is a later, slightly corrected version of the paper. This paper is also available in postscript form.

[Har88] Hardy, Norm, ``The Confused Deputy'', Operating System Review, Oct. 1988 vol. 22 #4, pp 36:38

Traced a bit of the motivation for KeyKOS.

This paper is also available in postscript form.

[KL83] U.S. Patent 4,584,639 - Covering the KeyKOS “Factory”
[Raj86] Rajunas, S. A., et al., Security in KeyKOS, Proceedings of the 1986 IEEE Symposium on Security and Privacy, IEEE
[Lan89] Landau, Charles, ``Security in a Secure Capability-Based System'', Operating Systems Review, Oct 1989 pp 2-4
[Lan92] Landau, Charles R., ``The Checkpoint Mechanism in KeyKOS'', Proceedings of the Second International Workshop on Object Orientation in Operating Systems, IEEE, September 1992. pp 86-91
[Wel88] Wells, Codie, A Note on “Protection Imperfect”, Operating Systems Review, v.22 n.4, Oct 1988, p.35

Some other, related papers:

[Lam73] Lampson, Butler, ``Note on the Confinement Problem'', Communications of the ACM, V 16, N 10, October, 1973.
[Lin76] Theodore A. Linden, “Operating System Structures to Support Security and Reliable Software”, NBS Technical Note 919, U.S. Department of Commerce, National Bureau of Standards, Institute for Computer Sciences and Technology, August, 1976. (Also published in ACM Computing Surveys, V8, #4, December 1976, pp 409-445)