/ elib / capability

The KeyKOS Factory

KeyKOS was the first system to demonstrate a solution to the confinement of authority, both in and out. The KeyKOS solution is known as The Factory, and is also explained here and in the expired factory patent. The KeyKOS Factory is the most flexible known solution, in that its provisions for Sensory capabilities and Hole Checking, both explained below, allow a greater range of useful computation to be confined than can be achieved without these provisions.

In order to understand KeyKOS confinement, let's build up to it in stages.

Hypothetical Factory Design Stage #1: Bob is an Island

Mallet writes a proprietary program, BobProg, that he wishes to enable Alice to use but not read. Alice wishes to use this program on proprietary data of hers that she wishes Mallet not to read. Fortunately, they know a trusted intermediary object, the FactoryFactory. Mallet hands the FactoryFactory the compiled BobProg program + any initial pure data, asking it to make a BobProgFactory, which he hands to Alice. The stage 1 factory accepts only pure data from Mallet, not capabilities.

Alice asks the FactoryFactory whether the BobProgFactory is indeed a Factory (ie, something the FactoryFactory made). Assume the FactoryFactory has some way of answering this question in a trustworthy fashion (this is more of a trick than it seems, but is true in KeyKOS, EROS, Joule, and E). Assured that this is indeed a Factory of some sort, Alice asks it to produce its yield, Bob. If you think of the factory as a class, Alice has asked for an instance of the class.

Bob starts with BobProg as its code + any initial pure data provided by Mallet, but Bob has no initial capabilities other than those provided by Alice in her instantiation request. Since Bob has no abilities to communicate in or out, other than those provided by Alice, Alice considers Bob to be confined. The "confinement check" in this story is simply the check that BobProgFactory is indeed a Factory.

In stage 1 Mallet provided data, but not the memory for the data. The memory was allocated and written to once by the FactoryFactory in making the BobProgFactory. Afterwards, this memory is exclusively held by BobProgFactory and Bob, and never written to. Since Bob obeys the untrusted BobProg program, either Bob is given a separate copy or read-only access to memory holding BobProg. BobProgFactory's memory of BobProg is therefore effectively immutable. If we ignore the deallocation issue, our stage 1 story provides both confinement and durability.

Stage #2: Encapsulated Factory Graphs

Let's say Alice wishes to create a confined service for use by Carol named Joe, just as Mallet has created a confined service for use by Alice named Bob. However, the program Alice wishes to write makes use of the functionality provided by BobProgFactory. Alice has no access to the BobProg code, and so cannot incorporate it into the code used to make the JoeProgFactory. In stage #2, we extend the description provided to the FactoryFactory to make JoeProgFactory so it can contain references to other factories. The Joes made by JoeProgFactory are then born with these as initially accessible capabilities, and can use them to create confined objects it can use. Just as Carol cannot read the code of JoeProg, Carol also cannot find out that the Joes made by JoeProgFactory uses Bobs from BobProgFactory. By the same token, Alice never knew whether Bobs from BobProgFactory's uses yet other factories.

The actual KeyKOS protocol doesn't provide the yield description all at once in asking to create a factory. Rather, it first gets a blank factory, then installs into it the description of the yield, and finally seals it -- turning it into an instantiable factory. This has the advantage that one can form cyclic encapsulated factory graphs.

At this point, the one abstraction still provides both confinement and durability. Confinement in E corresponds to stopping at stage #2.

Stage 3: Adding Sensory Capabilities

For now, see this from Norm. I believe confinement in EROS corresponds to stopping at stage #3.

Stage 4: Hole Checking & Discretion

Alice doesn't necessarily care whether a Bob from BobProgFactory has capabilities to non-confined entities. Rather, she cares whether these objects have capabilities other than those she approves of. The factory creation logic now allows Mallet to provide arbitrary capabilities as the initial endowment of the yield of BobProgFactory, since these might be ones that Alice does approve of. These capabilities which are not guaranteed confined on previous grounds are called holes.

To determine whether a yield/instance of BobProgFactory would be confined as far as she is concerned, she performs a hole check on BobProgFactory. A hole check involves a HoleChecker encapsulating a table of approved holes. The HoleChecker implementation is in bed with the Factory implementation, and in KeyKOS actually happens to be a Factory. The hole check asks the question

Are there any holes in the transitive factory graph starting at BobProgFactory not on the approved list?

The answer is only yes or no, because more detail would reveal too much information. Since the question is now relative to an approved list, we are no longer asking about an objective property of the factory. The Joule language clarifies this by using "confinement" only for the objective property (as dealt with in stages #1, #2, and #3) as opposed to "discretion" for the more flexible relative property (as dealt with in stage #4).

Since Alice has to provide the approved hole list, what generality is lost if we skip discretion, and instead have Alice provide to Bob a name-table of some sort from which Bob can obtain those holes Alice approves of? Alice doesn't necessarily have access to the list of approved holes, merely a HoleChecker that contains an encapsulated list. How can this come about? The HoleChecker could have come from, for example, Alice's administrator.

There's another problem with providing holes directly: Alice might be willing for Bob to have certain holes only if Mallet had them and chose to endow Bob with them. Though this problem is possible to solve without hole checking, it is awkward.

Can We Do Less?

I asked Norm if the extra flexibility of hole checking, or discretion over confinement, was ever useful in practice at KeyLogic or any of its customers. If I recall, the answer was no.

E doesn't have factories, sensory keys, or hole checking. Speaking somewhat in advance of the current implementation, E instead has a set of declared audited properties of an object expression. The property corresponding to the above stages #1 and #2 is "transitively immutable".

To declare an object expression transitively immutable, the "transitive immutability" auditor must determine, by examining the expression, that the object it evaluates to (instantiates) cannot change its own state, and can only contain references to instances of object expressions that are themselves declared transitively immutable. An instance of an object expression that has passed this audit is itself marked as having the audited property. Given such an instance, one can ask an auditor whether it carries that auditor's mark. (Implementationally, the mark will be on the object's vtable rather than the object.)

Inter-Vat references and external I/O or device capabilities are not considered immutable. With these definitions, a transitively immutable object is like a confined and durable factory, corresponding to stages #1 and #2. The same transitive auditing & marking logic plausibly could give us checkable sensory capabilities, taking us into stage #3, but first I'd like to hear a case that we'll need those. I'd love for "transitive immutability auditors" to be all the TCB support for confinement we need.

Unfortunately, Distributed Confinement seems to require the subjectivity of discretion. If Alice is running on Machine A, then Bob is confined as far as Alice is concerned only to the extent Alice trusts the confinement-checking agent (FactoryFactory for KeyKOS, auditor for E) on Machine B to be doing its job as well. Such issues didn't come up in KeyKOS because certain single objects, like the FactoryFactory, could be assumed to be (approximately) universally known and trusted. The distributed nature of E prevents it from relying on any universally trusted objects.