Scheduling via Capabilities

Butler Lampson introduces and illustrates many covert channels in his Confinement Problem paper. See this for confinement strategies.

This note will not soon be well organized.

When resources are allocated with capabilities it is possible to reason about covert information flow by following the capabilities. In Keykos, resource allocation is controlled by capabilities at a gross level but small scale allocation is delegated to the kernel which does not follow capability discipline as it allocates:

We will imagine here a modification to Keykos that removes these kernel non-capability allocation functions and substitutes allocation algorithms, out-side the kernel, that are not directly designed to thwart covert channels, but merely subject to capability discipline. Our confinement arguments should then necessarily solve the problem. We must be wary of such things as channel time and other ignored resources!

There is a delicate “bottoming out” issue: “What resources do the allocation routines run with?” or “Who allocates time for the allocators?”. These problems are more confusing than difficult. In the current Keykos meter keepers always run on meters superior to the meters that they keep and the highest meters are unkept. Similarly there are debuggers with no debuggers above them. In conventional computer architectures, instruction traps in the instruction trap routine go unprocessed. I imagine a similar solution here.

Ground Rules

We will not tamper with the concept of page that floats with its data between disk and RAM. Too much of Keykos is based on that and almost all software that is aware of pages will remain unconcerned with the distinction.

We are initially agnostic about whether the described function is in the kernel. That is an engineering question with a heavy bias of removing stuff from the kernel with performance the main impediment.

A new object called the RAM-claim is proposed. Some slowly changing relation between pages and RAM-claims exists. I don’t know yet how this relation is represented, but with keys, somehow! A service key to a RAM-claim also exists.

The motivating idea behind a RAM-claim is to identify sets of pages that need to live in RAM for periods of time. These periods will be determined by software decisions made at the beginning and ends of those periods. Perhaps at a lower level there will be futures as well.

The Firewire scheme for allocating bandwidth is an attractive model of allocating time on a resource so as to meet hard real time requirements.

Cloud: I currently believe that ideally there should be capabilities to definite slots of time for such processors as the CPU and IO devices. I don’t think, however, that this is efficient enough. I will assume it here for a thought experiment, however, and then show how the actual meter mechanisms of Keykos can be used to the same ends.

In this scheme, there would be meter keys for definite periods of time. Keys for past periods would useless. Domains running directly or indirectly on a “current meter key” would run as domains do now while domains running on a future key would not be dispatched until that time arrived.

Light Pink Book