22C:116, Lecture 39, Spring 2002

Douglas W. Jones
University of Iowa Department of Computer Science

  1. Capability-based network addressing

    The capability model has come to dominate the design of microkernels for multicomputers. Demos, Mach are 3 well-known and widely studied examples. In all of these systems, processes use capabilities for all interprocess communications. In Demos, these capabilities were called links, but in all more modern systems, they have been referred to by their proper name.

    These example systems differ in the nature of capabilities and in the way they are used. In both Demos and Mach, the capabilities available to each process are stored in a capability list associated with that process (the process's link table of Demos). Each entry in this capability list confers the right to send a message over some communication channel, and in both systems, the message may contain capabilities, so processes may pass capabilities to other processes. In Amoeba, on the other hand, capabilities may be freely mixed with data and need not be segregated into capability lists. Demos and Mach rely on the kernel to prevent a process from forging or improperly manipulating capabilities, while Amoeba uses cryptographic methods to assure this.

    In both Demos and Amoeba, capabilities permit sending messages to specific objects (in the most abstract sense) of particular processes. In contrast, Mach capabilites refer to free-floating mailboxes, where one process may communicate with another through a mailbox if one has write access to that mailbox while the other has read access to that mailbox.

    Amoeba requires all interprocess communication to take the form of synchronous remote procedure calls, while Demos and Mach provide message passing primitives that are sufficient to support remote procedure calls but do not require the use of the RPC model.

  2. Demos Summary

    Please see previous notes on Demos.

  3. Mach Summary

    The kernel maintains, for each process, a capability list, where the entries in this list are capabilities for mailboxes. The access rights on a mailbox include read (the right to receive a message from that box) and write (the right to send a message to that box).

    Client-server relationships are common in Mach, but boxes are also used to report exceptions. For example, one of the entries in the C-list for each process is the exception box. If an exception is raised by that process (for example, a page fault exception), the thread that raised that exception is blocked (Mach has kernel threads) and a message is sent to the exception box. There had better be an exception handler waiting for this exception message!

    The exception message contains a capability for the thread that raised the exception. This capability is actually for a mailbox that the handler can send messages to, where this mailboxes is served by the process manager. The messages to the mailbox for a thread running under the process manager can be used to inspect and set the state of that thread, and they can be used to start and stop that thread. As in Demos, the process manager is a server under the kernel and not part of the kernel.

    One interesting feature of Mach is that demand paged virtual memory is handled by the exception handler and not by the kernel. Each process has an address space consisting of segments, where each segment is paged, but the kernel does not relate pages in memory to pages on disk. Instead, page faults are just a kind of exception, and it is up to the exception handler to handle such faults. Typically, the exception handler, when it finds that the exception is a page fault, will send a message to the segment manager of the segment that was referenced. The segment manager is the one that does the page replacement.

  4. Amoeba

    The most innovative feature of Amoeba is the way it protects capabilities from corruption or abuse. Instead of having the kernel manage a capability list on behalf of each process, the kernel lets users keep their capabilities anywhere they want, mixed arbitrarily with other user data. In fact, user processes may make arbitrary changes to capabilities, yet Amoeba still manages to be a secure system!

    In Amoeba, capabilites are cryptographically protected, the the primary responsibility for this lies not with the kernel, but with the server in each client server interaction. All Amoeba interprocess communication is done using remote procedure calls, so the following operations are required (outlined very coarsely):

    call(cap, messagebuf, returnbuf)
    Call the remote procedure indicated by cap, passing out the contents of an outgoing message buffer, and expecting the return message to be put in the indicated return buffer.. The calling thread blocks until the reply is received.

    accept(cap, messagebuf)
    Accept a remote procedure call, giving the accepting thread a copy of the capability that was used to make the call and a copy of the sender's outgoing message buffer. The accepting thread blocks until some other thread calls this process.

    reply(replybuf)
    Reply to the most recent RPC accepted by this thread, giving the contents of replybuf as the reply to the caller.

    Capabilities have the following format, in coarse outline:

            An amoeba capability
    	 ___________________ _____________________ __________
    	|___________________|_____________________|__________|
    	|    public ID of   | additional info for | checksum |
    	 destination process  destinaiton process
    
    It is up to the called process to interpret the additional information. The checksum is computed with a publically known checksum algorithm, so it offers no security. It is only there so that the kernel can prevent most accidental use of corrupted capabilities. The key to the security of the entire system, therefore, rests in the use of the additional information field! The Amoeba kernel places no constraint on the use of this field, but the following conventional layout is used by essentially all servers written under Amoeba:
            An amoeba capability
    	 ___________ _____________________________ __________
    	|___________|   additional info field     |__________|
    	| public ID |___________|________|________| checksum |
                        | object ID | access | magic  |
                                      rights    num  
    
    The server interprets the first word of the additional info field as naming one object implemented by that server. A file server might use this field as the I-node number. The next 8 bits give the access rights this capability conveys for this object. The magic number is the key to the security of the system. Here is Tannenbaum's great invention.

    Inside each server, we must have a table, indexed by object ID, containing, for each object, various object attributes. All but one of these attributes depends on the semantics of the object. One special attribute of the object is its secret number. This number is a random number assigned to the object when the server creates that object.

    To create a the magic number that goes in the capability for an object, the server performs the following computation:

    	magic_num = trapdoor( concat ( access_rights, secret_num ) )
    
    Because only the server knows the secret number, only the server can create the correct magic number. On receipt of a capability for one of its objects, the server can check to see that the above relationship still holds. If it does hold, either the capability has not been tampered with, or the client has been extraordinarily lucky.

    The security of this scheme rests on two things. First, it requires that the trapdoor function be easy to compute, for the purpose of creating capabilities, but extremely hard to invert -- after all, the client can inspect the magic number and access rights, and the client has lots of time to try to invert the trapdoor function to compute the secret number. An ideal trapdoor function on n bits can be computed in the forward direction in O(log n) time but requires O(2n) time to compute in the inverse direction. We cannot prove that there are such functions, but there are functions that appear to be good trapdoor functions that nobody has yet to crack. Amoeba uses a specific well-known trapdoor function everywhere, and that function has stood up to over a decade of attack.

    The second requirement is that the stream of random numbers used by the server to create successive objects be difficult to guess. If the numbers were truly random, this would be a trivial condition, but real computer systems use pseudorandom number streams, and if there is any way for a client to learn where in some particular pseudorandom stream the server is, the client can do a good job of guessing the secret number the server will use next.

    Amoeba has one other feature! When a process wants to offer a service, it picks a private ID for that service, a unique ID that must be secret, and is typically computed by drawing a very large random number. Having done so, the process computes a public ID from the private ID by applying the trapdoor function to the private ID. It then "publishes" the public ID by including it in capabilities it is willing to acknowledge and putting these in public places. Notably, Amoeba's directory servers associate textual names with capabilities, so the server can publish its services by putting capabilities for them in directories.

    The public ID is the one used to send messages to that server. When a process wants to register to receive messages sent to a particular public ID, it must use the private ID to register with the kernel. This means that the public ID used in message passing is not the actual process ID, but rather, it is the public ID derived from the private ID the process has registered. This means that a group of processes may cooperate to offer a service if all of them know the private ID for that service -- so long as they don't let the secret out into public.

    Of course, there is an element of luck involved in Amoeba security, while the security offered by Demos or Mach is more nerely absolute. In Amoeba, a process might accidentally generate a random bit pattern that is a valid capability. The probability of this is proportional to 1/(2n), where n is the number of bits in the magic number and in the public ID. If the security is not good enough, you simply increase n until the probability of an accidental breakin is acceptably small.