Here is an introduction to the issue of confinement and pointers to pages at this site that bear on the subject.
Butler Lampson named and described the Confinement Problem (too) in [Butler Lampson, “A Note on the Confinement Problem,” Communications of the ACM, V 16, N 10, October, 1973]. In brief it outlined the task of confining an untrusted program so as to make the program incapable of transferring information that it possessed to other willing unconfined programs running on the same machine. He listed many such possible transfers that operating systems of the day failed to prevent. Current conventional operating systems are mostly worse.
Confinement can serve privacy or information commerce among other uses.
Lampson mentioned, but did not discuss, the further problem of protecting the proprietary information of the confined program from the caller. Such proprietary protection is normally provided in Keykos by data abstraction and this protection is also available and natural to objects from factories.
Lore that had developed within the military security community during the 80’s was that capability systems were especially poor at confinement. This was perhaps due to the idea that I would provide function to you by building an object and granting you access to that object. You would invoke the object, passing your secrets, to perform the function that I defined and you desired to use. I am obviously in a position to build that object so that it will reveal your data to me as it processes your data.
While the above pattern is the most obvious way for me to provide function to you when we use the same machine, it not the only way. An alternative is for the confined program to be instantiated by a mutually trusted creator.
The factory design is predicated upon a system founded on capabilities and may be unsuitable to other systems. Readers unfamiliar with capability systems may be able to follow fewer details presented here than those who have studied such systems.
Any computer system in which there is code by parties with divergent interests requires some sort of mutually trusted software. To solve the confinement problem we build a mutually trusted class of object, the factory. The factory code is not special to any particular kind of function to be confined. One party, called the builder, owns some code that she is willing to have used and willing to have confined. We will say that the code does some special work which is its desired property. The builder invokes a widely available factory creator and is granted sole access to a new factory in the form of a capability to the factory called the builder’s key. By invoking the builder’s key, the builder delivers capabilities to the factory that are necessary to construct the object that will perform the work. These capabilities provided by the builder are called components. The main component provided by the builder is the program that will instruct an object to do the desired work. This program is typically delivered in the form of a read-only capability to a segment that holds the program. The capability is read-only, for the program could otherwise store the secrets in the program segment to which the builder retains access. KeyKos is such that user code, such as factory code, can ascertain that a read-only capability to a segment is indeed such. We say that such capabilities are sensory and there are just a few more. Primitive capabilities are widely available to make such determinations.
When the confined program runs it will have access to the factory components installed by the builder and thus as the builder adds components to the factory she must, for each component, declare for which one of the following three reasons the factory should consider including this component:
Another type of allowed component is a factory requestor’s key which we will describe below. Factories are able to recognize keys to factories.
The last type of component is a hole. The hole is unaccounted for by the builder but the factory accepts the hole and notes the hole’s identity. When we speak of the holes of a factory we mean both those components that were added to the factory as a hole, and also the holes of factories whose requestor’s keys are components of the factory. This is recursive. Typically holes are broadly known tools that are not formally in the form of a factory. Many, perhaps most, factories have no holes. Here is how to leak a controlled amount of data for purposes of charging for service. See this for another useful hole.
After the builder has added all of the holes that her program will require she seals the factory. Sealed factories no longer accept holes as components, nor do they accept requestor’s keys to factories with additional holes. The sealing operation on the builder’s key returns a requestor’s key to that factory. The requestor’s key is a capability that is distributed to and used by those who wish to use the program in the factory with assurance that the data that that program works on is not disclosed to other than the requestor. Note that sealed factories can accept requestor’s keys to themselves so that their yield can create siblings to which to delegate subtasks. Sealed factories can accept requestor’s keys to other factories as well thus allowing impredicative patterns of mutual recursion.
The principle function of a requestor’s key is to request the construction of a new object that will obey the program held by the factory and thus serve the requestor. This code will have access to the components of the factory but be unable to change what those components are. The factory can thus be invoked many times, each time producing a new object. Note that a requestor’s key is like a sensory capability in that the holder of a sensory capability can have no side effects by virtue of holding the capability. It is not sensory because the kernel is unable to determine this. Factory logic is able to determine that a requestor’s key is to a factory for factories are sibling’s to each other.
Factory A is no less discreet than factory B when all of the holes in A are also in B. The requestor is able (and advised) to inquire of some familiar factory of known discretion, whether the requestor’s key is indeed to a factory and whether that factory is less discreet than the familiar factory. Being siblings, factories are able to discuss this between themselves.
Note that the confined program has access to the factory components which may include requestor’s keys to other factories. The confined program may recursively invoke other confined subcontractors. When a requestor’s key to A is added to a factory B as a component then the holes of B are made to include the holes of A. There are thus no ways to transmit data out of the extended calculation resulting by invocation of the original requestor’s key.
When a requestor’s key is invoked for a new object, capabilities for acquiring storage and CPU cycles are included. The storage and time are thus supplied by the requestor. In KeyKos this capability for new storage can be verified by the confined program to be of a sort that provides storage that only the confined program and not the requestor can access. The confined program is thus in a position to conceal the nature of its algorithms, even at the same time that the nature of the requestor’s job is concealed from the writer and owner of the confined program.
The second clause above depends on the level of abstraction. At a lower abstraction level the requestor holds a capability to the allocator that allows the requestor to reclaim the space of the confined object. Of course none of the state of that space will be accessible to the requestor.
Keykos currently has no highly developed development environment beyond some cross system support. For some particular kind of object, its factory is normally built immediately after compiling and linking the code defining that object’s behavior. The components of a factory are selected at that time. A consequence of this is that a given factory produces only one particular version of an object. A directory might map the same ASCII name to different factories at different times. The public directories are generally of this form. If one always goes to the standard place to fetch the factory requestor’s key afresh then one gets the latest version of the object. If one holds onto a requestor’s key then all of the yields of that factory are of the same clone. This practice provides, but does not assure, some of the durability advantages.
See this about a proposed small change to factory design.
This is another incipient mod and motivation.
See an idealized factory done in Scheme. Read also about the practical confinement, and distributed confinement. Debugging confined programs is a novel problem. We need to fix this covert channel.