Asset Cards {or Loose Change}

See (asset-fact) about combining these ideas into factory logic. See (p2,purse) for an available money technology.

The ability to create unique brands provides for uncounterfeitable objects. With such objects, credit cards or asset cards like BART (Bay Area Rapid Transit) tickets may be constructed. These tokens would contain a coded sum that need not be recorded elsewhere. Unlike BART tickets, their entire internal structure could be available for the holder to read via calls on the start key. The token would consist of a start key designating a domain with a certain brand. Anyone can convince himself that a token that he holds is valid by asking the ticket maker. The ticket maker determines validity by checking the brand. The only programs that can operate on the internal structure of the object are the program that the object itself specifies and programs that hold a key to the domain creator with the brand.

An instructive exercise is to construct a program that provides the function of consolidating two tickets into one. Call the tickets A and B. The owner of these tickets calls A passing B with instruction to A to add B’s value to A. A uses its domain creator key to check B’s brand, observes that it is real, and gains access to the domain of B. A then adds B’s value to its own and sets B’s value to 0. A then returns.

This example was motivated by a paper by N. Minsky (Minsky, Naftly. Intentional Resolution of Privacy Protection in Database Systems. (_Communications of the ACM 19) , 3 (March 1976) 148-158). Assume that we have a collection of records (in virtual storage) each of which has fields A and B and pointers 1, 2 and 3 to other records. Assume that we want to give client x the ability to see field X of each record that he can reach starting from record AX and following pointer 1 or 2 of each record. Suppose we want to client y the ability to see field Y of each record that he can reach by following pointer of type 2 or 3, starting from record AY.

For client x we construct a domain that has the address of record AX in its general register 3 image, and whose PSW points to code that will modify register 3 to follow pointer 1 or 2 of that record. The code will also return field X of the next record. We give client x a start key to this domain. An additional command that the domain will execute is to duplicate itself. Client y can be provided with a similar start key.

This technique solves the first problem posed in the paper without requiring language development. We do not claim that the language solution should not be pursued, but that we have a solution that leaves the compiler outside the security kernel.

The above solution is no more than a co-routine.

Confinement

Butler Lampson has described a set of problems that he called “confinement problems”.
Lampson, B. W., A note on the confinement problem. Comm. ACM, Vol. 16, No. 10, (Oct. 1973) pages 613-615.

Suppose that X has a chemical patent data base with which he wishes to serve chemists such as Y. Y does not want X to be able to find out what the searches are, because he doesn’t want to give X information about things they are considering patenting. {X and Y may be competitors.}
X wishes to charge for the service and so must limit access to the data base. X has a routine that accesses the data and a representation of a search request from users such as Y.

X is unwilling to give the routine or data to Y and Y is unwilling to give the representation of the search request to X.

How can we arrange to get the job done?

This problem may be solved using factories. X creates a factory with read access to X’s search code and the proprietary data. Such a factory needs no holes.

The requestor’s key to this factory is provided to Y who calls for an invocation of the searcher. Both X’s and Y’s interests are now protected.

See (ch-fact) to arrange for payment.

Imagine two or more people who wish to cooperate in some endeavor. To do this requires the construction of some object to which each member contributes some authority, but which authority is more than any member alone is trusted by the others to hold.

Who is to build the object?

Someone describes a mutually agreeable algorithm and presents it to the universal escrow agent {who all members trust}. We call this algorithm the (_escrow instructions). The agent shows these instructions to each of the members in turn. When each member agrees, he submits to the agent his part of the required authority. If all members agree the agent executes the instructions with the collected authority, thus building the object. The agent then distributes various capabilities to the object to the members according to the instructions.

The members must merely trust the agent to execute the escrow instructions.

The factory {(p2,factory)} is currently the only specified system of this category. Indeed the factory could have been implemented as an escrow instance.

Virtual Constructs

{nonref}Exporting Access to a Segment

{arcane}Calling Across Data Links

There are two very distinct cases to discuss here: calls that pass keys and those that don’t.

A great deal of benefit can be had from supporting calls that don’t pass keys. This case is easy to support and should be done in a general way.

Calls that pass keys can be supported in a limited way. The limitations seem to be in the area of cost.

Suppose that there is a domain D on system 2 and we wish to provide the illusion that start key E on system 1 is to D.

The rules of the game are that we are allowed to hold a start key E2 to D on system 2 and must provide the start key E on system 1 that is to act as E2. We are also provided with a data link between our programs on the respective systems.

We create a domain on system 1 to obey code alpha and we create a domain on system 2 that holds E2 and obeys code beta. E is created as a start key to our system 1 domain.

When E is invoked alpha gains control. Alpha transmits the data arguments to beta. It applies DISCRIM to each of the four key arguments.

Those that are data keys have their data extracted and transmitted.

Those that are meter keys have substitute meters provided at the other end.

One strategy is to cause a greatly reduced load on the real meter in response to a normal load on the substitute meter. This means that actions on system to turn off the meter will have the necessary effect on system 2. This can also provide the meaning of valid meters.

Memory keys can be supported by the techniques described in (expseg).
Extra provisions must also be made for properly signaling explicit and implicit calls to the segment keeper.

Resume keys and start keys are handled similarly. As such a gate is passed a record is created on both ends. A start key causes a new instance of the very logic that we are describing here. A resume key has the advantage that we may well be able to eventually reclaim the storage taken to represent the resume key.

Many of the facilities of Gnosis were designed to allow a degree of distributed processing without impacting the logic of the application program. Section (p2,censtor) is a brief description of such goals. Section (p3,expseg) discusses remote access to data extensively. We discuss some of the technical strategies here.

We introduce the term “substitution regime” informally here. A (_substitution regime) is a collection of constructs holding keys to each other and constructed according to the rules of this manual but with some systematic substitution of some synthetic construct for corresponding real constructs. Such a regime might, for instance, substitute a domain-meter pair for each meter. This is not accomplished by copying and making the substitution, (no one has enough authority) but instead by providing a synthetic space bank like the real except that it provides synthetic nodes. When these nodes are asked to provide corresponding meter keys they create a real meter that has the desired altered properties and return the real meter key.

How is such a regime established? One way is to provide a womb with the described non standard space bank and a gate to the public directory with a funny front end. This front end establishes a filter that allows calls into and out of the regime with the necessary transformations. For instance if there were a node in the public directory the front end would have to make the corresponding synthetic node. If a start key were called on from the public directory a similar front end would have to be established to prevent the smuggling of real nodes into the regime. This filter would also transform synthetic nodes into real ones when they were passed out of the regime.

One regime strategy is with respect to meters. This requires that all nodes provided to the domains in the regime be synthetic and that any meters constructed from these nodes be fixed to adjust any counter readings that are set into or read from the meter via the synthetic node key. This is to hide the fact that the primary key METTRAN is being used to provide resource caches at a remote site.

Note to substitution regime builders:

In order to build a regime ((p3,do)) it seems necessary to have read access to all of the code that implements the functions inside the regime.

The scheme of having access to these functions by way of gates fails for the very reason that the gate mechanism was designed to prevent this sort of altering of the function of a program by considerations outside of the program’s control.

A regime builder’s broker might be invented to mediate the interests of regime builders and program writers. This might be required when “untrusted” regime builders want to build regimes. See (p3,escrow) and (p2,factory).

The Gnosis kernel has much logic to make pages, nodes, and the things built from them reliable. In particular there are provisions to restart all processes from checkpoints which are taken periodically.

Local checkpoints:

These checkpoints, however, are taken only every several minutes. Some applications must not be restarted in such a manner. It is possible to establish a regime that is provided with virtual checkpoints upon each interaction between the world within the regime and the world outside. The technique is to install recording intermediary gates at all the portals to the regime. Non volatile records will be made of each of these events {with the journalizing facilities}.

In the event of a power failure or machine malfunction, the actions within the regime may be replayed, starting from the most recent system checkpoint, by reintroducing all of the external stimuli that had been kept in a non-volatile record.

We know of these sources of uncontrollable stimuli that may defeat this scheme:

the TOD clock,

the interruptible instructions and PER,

The interruptible instructions {MVCL and CLCL} may cause program events and those events may be reported to the kernel before the instruction has finished. When this report is made depends on asynchronous interrupts.

For one of the four types of event the kernel reports an event to the domain keeper only once per instruction. See (p1,gnoper). This report is made after the event has finished, but perhaps before the instruction has finished.

ghosts of interruptible instructions,
The other problem in this area is with MVCL modifying itself. The hardware may or may not refetch the instruction. If any interruption of the MVCL occurs after it has modified itself the changed instruction will surely be refetched. The behavior of the domain thus depends on external events.

race conditions inherent in multiprogramming,
One may program his own clock by setting one domain to adding to memory in a shared page. While this is less reliable and more expensive it some of the same covert timing channels as the TOD clock.

the LEX instruction,
The LEX instruction is included in early 370’s built by IBM to aid in emulation of DOS. The LEX instruction is not privileged but allows the user to sense that he has been interrupted.

the EDIT and EDIT AND MARK instructions that cause page faults,

The Move Inverse instruction is not defined for overlapping fields.

virtual addresses that map to the same real address and which are changing.

perhaps (p1,primfault) is a source of noise.

See (p1,stringcopy) for a current implementation expedient that is a noise source. String passing is non-atomic.

The following ideas indicate that these problems might each be fixable:
Hardware modifications could make the store clock instruction privileged {depending on a PSW bit}.
Programs running in the regime would be able to read the clock but only after a record of the event was made. During replay, the old clock values would be provided.

To solve the wall-banging problem, a regime would share a clock. See (p2,time).

The problem of interruptible instructions and PER.
With extra logic the kernel could be changed to make the report to the domain keeper only after the instruction has completed.

This could be also fixed with a 370 architecture change. If 4 bits were kept in the PSW indicating which program events had been caused by an instruction that had not concluded, and the program events were reported as program interrupts only at the conclusion of instructions, this problem would be eliminated and PER code in the kernel would be simplified as well.

To solve the MVCL ghost problem {perhaps not vital}:
One might redefine the architecture of the machine to require refetching the instruction when the MVCL modifies itself.

Alternatively one might require that the program continue with the interrupted instruction upon restart even if it has been changed. This can be done by remembering in the PSW what instruction was being executed (not merely its location) when an instruction is interrupted.

To solve the multiprogramming race conditions one might modify the meter architecture to support the prohibition of more than one process in a regime. Processes produced by a fork would be queued on the special meter.

the LEX instruction,

Perhaps we can get IBM to remove this and other secret instructions.

The EDIT type instructions might be redefined to cause a page fault before starting if there is a chance of causing one before finishing. {The TR instruction is done this way.} This could, however cause page faults for pages that the EDIT instruction doesn’t actually use!

It might be possible to arrange that no real page map include the same real page twice unless both are read-only. This logic is similar to the present logic that prevents a page from appearing in an address space once read-write and again read-only.

The non-atomic string passing can be eliminated.

These techniques also address the problem of wall banging; if the evolution of the state of a domain depends (_only) on its capabilities of which it is composed, the wall bang listener will hear nothing.