Comparing "copy" and "map/unmap"

[Jonathan S. Shapiro]

I apologize for the length of this note. It is not a simple issue.

We seem to have stumbled into a discussion of capability semantics: what
does it mean when a capability is transferred from one process to
another, and what impact does this have on overall system design. I want
to *try* to make some comments about the trade-offs between the "copy"
style of capability transfer and the "map" style of capability transfer.

I will attempt to be balanced. However: I must warn everyone that I have
a very strong view on this issue. In defense of this view, I note that
we have 30 years of successful experience with the "copy" approach, and
zero years of experience with the "map/unmap" approach as applied to
capabilities. This does not mean that I am right, and it does not mean
that my views on deficiencies of map/unmap are correct. There may be
clever ways to avoid the issues that concern me.

Also, I must emphasize that I am describing one snapshot of L4sec that
existed at one time in their design discussions. The L4sec team is still
learning about capabilities, and their design is still being revised.
The Coyotos design is a minimal delta from EROS. While Coyotos is still
evolving, we are debating issues of mechanism and implementation rather
than issues of semantics.




SIMILARITIES:

In both designs, capabilities are kernel protected. An application
references its capabilities by specifying an address relative to some
kind of capability address space.

In both L4sec (the L4 successor) and Coyotos (the EROS successor),
capabilities are stored in capability address spaces. The mechanisms for
managing traditional data address spaces in each system have been
extended in the obvious ways so that they can be used on capability
spaces as well.

In both systems, the way you invoke a service is by invoking a
capability to that service.

COYOTOS CAP TRANSFER SEMANTICS

In EROS/Coyotos, the fundamental operation on capabilities is COPY. When
process A sends a capability to process B, the capability received in
process B is co-equal in status with the original in process A. This is
directly parallel to what happens for data. When process A sends the
value 5 to process B, the copy of 5 that arrives in B has the same
status as the 5 that was transmitted.

L4SEC CAP TRANSFER SEMANTICS

In L4sec, the fundamental operations on capabilities are MAP/UNMAP. When
process A sends a capability to process B, the copy received by B is
*subordinate*. This is true because A can later unmap the capability. It
means that any use of the capability by B is dependent on the continuing
good behavior of A. More generally, the use of any capability relies on
the continuing good behavior of all processes that were involved in the
transfer of the capability from its origin to its place of use.

Good behavior means:

  The parties who transferred the capabilities do not maliciously
  revoke it.

  The parties who transferred the capabilities do not exit until
  all receivers are done with those capabilities.

TYPES OF REVOCATION

There are two types of revocation that we need to distinguish. People
often fail to be clear in these discussions about what they mean:

  REVOCATION: destroying *all* capabilities to an object (everywhere).

  SELECTIVE REVOCATION: destroying *some* capabilities to an object,
    according to some test criteria.

General revocation is very easy in both systems. Selective revocation is
a pain in the ass in every system, no matter how it is done.

SOME COMMENTS

The *good* part about the COPY model is that it makes object creation
and capability copy cheap. The *bad* part is that selective revocation
requires some application-level planning. In Coyotos, the way you do
selective revocation is that you insert a transparent forwarding object
(this is a kernel-implemented object) in front of the real capability,
and then pass the forwarding capability to the receiver instead of the
real capability. Later, you can destroy the forwarding object, which
revokes their capability.

The *good* part about the MAP/UNMAP model is that it makes selective
revocation easy -- just unmap. The *bad* part about the MAP/UNMAP
approach is that it makes capability copy and object creation very
expensive. Implementing copy requires a "capability exchange" protocol
with a capability server. This means that a copy involves a minimum of
three IPC operations:

  1. A copies to B
  2. B invokes CapServer to request an exchange
  3. CapServer returns an equivalent cap that cannot be revoked by A.

However, this description of the workaround is incomplete. It ignores
other complications that CapServer introduces:

  1. All newly created objects must be registered with the CapServer.
     Object creation is therefore expensive.

  2. The CapServer must have sufficient storage to store one copy of
     every capability. This is a surprisingly big problem.

  3. Authority to create an object must imply authority to allocate
     storage in the CapServer. Since the CapServer is a globally shared
     resource, this introduces the possibility of denial of resource by
     exhausting CapServer storage. Fixing this requires an object
     quota of some sort. It is very difficult to select good limits
     for such a quota.

Four thought experiments may be useful to get some intuition for the
impact of the CapSever and the UNMAP operation on the overall design:

1. Imagine trying to build robust programs in a Java system where
   you needed to say in advance how many total objects you planned
   to allocate.

2. Imagine trying to build a robust program in Java where you
   always had to be prepared for the possibility that some other
   thread (one that you never heard of) might destroy your objects,
   invalidating a pointer in the middle of one of your operations.

3. Now imagine that the revoking thread doesn't even need to be hostile.
   Imagine that exit of a thread revokes any capability it holds
   (the analogy is that L4sec task exit reclaims its address space).
   Now try to answer the question: "Given that the exiting thread
   and the using thread are supposed to be isolated from each other,
   how do I design a protocol that allows the exiting thread to know
   when it is safe to exit?"

4. Once you have designed that protocol, now imagine that the thread
   *using* the capability is hostile. One way to be hostile would be
   never to admit to the allocating thread that you are done with a
   capability. This prevents a well-behaved allocating thread from
   exiting, which is a direct denial of resource attack.

Step back and ask *why* everyone is talking about implementing a
capability server in L4sec-based designs. Fundamentally, the reason for
the capability server is that it can be trusted to satisfy "good
behavior" as I have defined it above. In fact, the purpose of the
capability server is to re-establish capability copy semantics on a
system that does not provide them.

Finally, note that there is a race condition in any capability exchange
protocol. As far as I know the L4sec team has not defined an efficient,
race-free protocol to accomplish this.

Unfair summary: capability exchange is like needle exchange. It's better
than using unclean capabilities, but what you really want is to have
clean capabilities in the first place. :-)

A MORE BALANCED VIEW

The two operations (COPY and UNMAP) are very different. Either can be
used to functionally emulate the other up to a point (more on this
below!), but whichever operation is emulated is going to be more
expensive.

It is probably unfair to blame MAP/UNMAP for the problems I have
identified above. The problem is actually more fundamental:

  Regardless of mechanism, selective revocation implies the need
  to program defensively. This is true whether the operation
  that does the revocation is UNMAP or DESTROY(forwarder).

Note also that the real cost in this is not in the "revoke" step.
Provided that the same number of capabilities are getting revoked, both
systems are going to be equally fast at the "revoke" step. The cost lies
in the "copy in such a way that I can later revoke" step. because of
this, I am now going to use the terms "COPY" and "REVOCABLE COPY".

THE KEY QUESTIONS

There are two questions to ask:

  1. Which operation (COPY or REVOCABLE COPY) is used more often?
  2. If one of these operations is used as a foundational operation
     for emulating the other, is there a choice that makes robust
     programming easier?

** Frequency of Use

A lot of experience in KeyKOS/EROS/Coyotos suggests that three types of
capability transfers account for the overwhelming majority of transfers
in real systems:

  1. Transfers between an allocating server and a client, where the
     client is not going to be the exclusive user of the object.
  2. Transfers between mutually trusting components where neither
     is going to revoke the other.
  2. Transfers between a client and a server, where the server will
     hold the capability temporarily, but the client trusts the server
     to handle that capability correctly.

All of these are cases where the operation you want is COPY, not
REVOCABLE COPY.

This may or may not be true for Hurd: my intuition is that as object
servers become larger they tend to become more monolithic. As they
become more monolithic, the trust relationships in the system
architecture become progressively more unequal, and the use of revocable
transfers becomes more common. I still suspect that REVOCABLE COPY is
the less frequent operation, but this is something that needs to be
measured.

In any case, if COPY accounts for the majority of capability transfers,
and a smaller number are REVOCABLE COPY, then it seems clear that the
right primitive operation is COPY.

** Program Robustness

We believe very strongly that program robustness is easy for
capabilities that are transferred by COPY, and very difficult for
capabilities that are transferred by REVOCABLE COPY. There are, in
practice, four cases of selective revocation:

  1. I'm killing the program anyway, and it isn't going to matter
     that it's capabilities become invalid.

  2. I'm revoking a capability according to a previous agreement.
     The victim ought to be prepared for this (though actually
     *implementing* this expectation is difficult).

  3. I'm revoking a capability because a process is misbehaving.
     In this case we don't really worry about negative impact
     on the process.

  4. I'm revoking a capability because I screwed up. This issue
     doesn't really have anything to do with the choice of capability
     transfer mechanism.

  5. I'm revoking a capability because I need to do something
     reasonable (e.g.: exit) and the capability transfer architecture
     didn't give me a choice.

The last one is particularly unfortunate, and the MAP/UNMAP design
introduces a lot of this.

TRANSPORT ISOLATION

For any capability, there is a chain of processes between the creating
process and the using process. This chain can be viewed as a "transport"
that copies the capability.

As I wrote last night, the impact of capability authentication is not
(yet) fully understood by the L4sec group. In the absence of capability
authentication, your ability to rely on *any* capability depends
entirely on the channel by which you receive it. If this is the case,
then you necessarily depend on every process in the transport between
you and the origin. When you take that perspective, the issue of process
exit is still really irritating, but the fact that you *continue* to
depend on the transport after receiving a capability doesn't really seem
like much of a problem.

However, once it is possible to authenticate capabilities, you would
very much like NOT to rely on the transport after receipt. After
authentication, the *source* of a capability ceases to be relevant,
because you know its implementation. If the implementation is
trustworthy, the sender of the capability cannot alter its behavior, and
there is no further dependency on the sender or the transport. At THAT
point you really want a transport that gets out of the way. You can't
get that cheaply if the foundational operation is REVOCABLE COPY.


PROBLEMS WITH HIERARCHY

Ignoring problems of performance and storage allocation, all of the
problems with REVOCABLE COPY that I have identified can be resolved
using a CapServer. In effect, we are saying that the only *correct*
systems that can be built on top of a REVOCABLE COPY primitive are those
that have a hierarchical system structure. Further, we are saying that
several elements of this trusted hierarchy are complex, and are
therefore prone to both functional and security errors. The CapServer is
certainly an example of this.

In fact, there is a hierarchy problem in L4.x2 today in the memory
manager. Consider two process A, B with respective pagers A', B'. Now:

        A' maps to A
        A maps to B
        A' revokes
        B' knows nothing and cannot reconstruct the mapping.

This problem is now well-known by the L4 designers, and it is a direct
consequence of using REVOCABLE COPY as the primitive operation. In every
real system that has been constructed on top of L4.x2, the solution has
been to require that either

        A' and B' are identical, or
        A' and B' have a commonly trusted parent who knows how to
          recover, or
        The design is broken, so unmaps are not performed.

The current L4sec design will require that every capability interaction
must use the same kinds of solutions.

I confess that this continues to surprise me. It appears to me that
there is a known, fundamental, architectural flaw here whose only
solutions involve the imposition of policy on the OS designer. Either L4
is intended to be a general platform for OS construction, and this
policy imposition should be eliminated, or the claim that L4 is a
general purpose nucleus should be abandoned.

For a separate reason, I find this *particular* architectural policy
very worrisome. It has the effect of forcing very sensitive and
complicated software to be gathered together in one place, and to be
implemented in such a way that every process must depend on the
correctness of this centralized code. This is such a fundamental
violation of basic secure programming practice that I cannot comprehend
why it should be an acceptable constraint for a microkernel design to
impose on a system.

Hierarchies in microkernel systems cannot entirely be avoided. You want
them to be as shallow as you can make them, and you want the programs
involved to be as simple as possible.

THE EMULATION FALLACY

It is being said that either system can be emulated on top of the other.
This is true only in the very narrow sense that it is possible to build
a library API with a functional interface that can be implemented by
both systems. Unfortunately, it is NOT true in two important regards:

  There is a fundamental difference in performance, which
  impacts the set of feasible system architectures.

  COPY cannot be emulated on top of REVOCABLE COPY without
  a centralized CapServer. The CapServer must allocate storage
  for every capability that is created, and can therefore be
  subjected to denial of resource attacks.

The second issue is critical. One of the most basic design principles in
EROS/Coyotos is:

  No free rides! The party who allocates must pay!

This is a design principle because in EVERY case where it has failed we
have been able to identify successful attacks on the overall system
design. I have not seen (and I have been unable to design) a CapServer
that satisfies this design principle.


This is probably far too much for one note, but I wanted to try to lay
out as coherent a picture as I could. Let us see what discussion
emerges.

shap