Why COPY != SIMULATED COPY

[Jonathan S. Shapiro]

There are two primary joys of being a professor. The first is when you
are humbled by one of your students. For example, when they explain
something simply and beautifully that you have been struggling to
articulate for years. The second is when someone asks a question, as
Neal did this morning, that manages to crystalize something that you
know is a problem but you cannot quite get your hands on it. These
moments are rare, and it is important to treasure them. Last night, my
student Mark Miller did the first, and this morning, Neal did the
second.


Summary: COPY != SIMULATED COPY
Further: ANY correct implementation of CapServer requires a primitive
         operation that is a generalization of COPY.

Definition: SIMULATED COPY: an attempt to simulate the semantics of COPY
by using a REVOCABLE COPY followed by a capability exchange server.

NOTATION: To explain this, I'm going to need some new notation so that
we can trace through the consequences of REVOCABLE COPY. When I write
"cap", I mean "some initial capability in the discussion." It does not
matter how this capability is received, since we are assuming that it
will not be revoked during the example illustration. When I write "c.1",
I mean "the first revocable copy of c". When I write "c.1.2", I mean
"the second revocable copy of c.1".

The protocol that Marcus and Neal have described (different words, same
protocol) is that all object servers should return indirectly through
the CapServer. This is done so that every new capability is "registered"
and the capability exchange protocol can later be done to simulate the
COPY operation.

To see why it does not work, consider the effects of *composing*
REVOCABLE COPY and COPY:

    STEP                         EFFECT ON SYSTEM STATE
    [Initially]                  A has Cap

      RevCOPY(Cap)
   A --------------> B           B has Cap.1

       COPY(Cap.1)
   B --------------> C           C has Cap.1

When A later performs a revoke on Cap.1, both B and C *must* lose their
copies of Cap.1. Any other outcome would allow processes to violate
their protection boundaries.

Now consider what happens in the Marcus/Neal protocol (as described):

    STEP                         EFFECT ON SYSTEM STATE
    [Initially]                  A has Cap

      RevCOPY(Cap)
   A --------------> B           B has Cap.1

      SimCOPY(Cap.1)
   B --------------> C           C has Cap

At the end, A has the initial capability Cap, B has a revocable
capability Cap.1, but what does C have? In the Marcus/Neal protocol, C
has Cap, not Cap.1.

Later, when A revokes Cap.1, C will not lose its copy. Thus SIMULATED
COPY does not accurately simulate COPY. More importantly, the entire
purpose of selective revocation has been defeated and a critical
security mechanism has disappeared.

My protocol is *also* broken. In the Shap protocol, the sender first
does an exchange with the CapServer, then sends, then the receiver does
an exchange with the CapServer (total: 5 IPCs). Let's look at this
protocol one step at a time:

    STEP                         EFFECT ON SYSTEM STATE
    [Initially]                  A has Cap

      RevCopy(Cap)
   A --------------> CapServer   CapServer has Cap.1

   CapServer ------> A           [none: CapServer is returning]

      RevCopy(Cap)
   A --------------> B           B has Cap.2

      RevCopy(Cap.2)
   B --------------> CapServer   CapServer has Cap.2.1
      RevCopy(Cap.1)
   CapServer ------> B           [B has Cap.1.1]

Note that this protocol does NOT (and cannot) simulate COPY. The
capability held by B is still revocable. In order for CapServer to
simulate a COPY, it must already possess some capability that is
independent of A. Since CapServer cannot know who A is in advance, it
must have a capability that is higher in the revocation chain than ANY
POSSIBLE A.

>From this, we can conclude that the Marcus/Neal protocol includes
something essential. Since the CapServer must dominate any possible A in
the revocation chain, it follows that:

  Requirement: the initial return from any object creation must
  occur indirectly through the CapServer in order for the CapServer
  to implement a COPY operation

So now let us see what is required to get the correct outcome from the
protocol:

  ISSUE: The CapServer cannot trust the receiver to learn what operation
         occurred. Only the sender can be trusted to say whether the
         intended operation was a revocable copy.

  REQUIREMENT: The sender must perform a negotiation with the CapServer
         before sending. [This can be optimized: the sender only needs
         to communicate with CapServer the *first* time it sends a
         given capability.

  ISSUE: The CapServer must be able to inject a capability into the
         revocation hierarchy. We currently have no mechanism to do
         this.

  REQUIREMENT: The CapServer must have some operation that permits it
         to insert new elements into the revocation hierarchy.

Given such a CapServer, the initial part of the protocol remains
similar:

    STEP                         EFFECT ON SYSTEM STATE
    [Initially]                  CapServer has Cap.1
                                 A has Cap.1..x.1

      RevCopy(Cap.1..x.1)
   A --------------> CapServer   CapServer has Cap.1..x.1.1

     [Intention: A is saying: I authorize CapServer to create
      capabilities that are co-equal to mine]

   CapServer ------> A           [none: CapServer is returning]

      RevCopy(Cap.1..x.1)
   A --------------> B           B has Cap.1..x.1.2

      RevCopy(Cap.1..x.1.2)
   B --------------> CapServer   CapServer has Cap.1...1.2.1

      ??MagicOp??(Cap.1...x)
   CapServer ------> B           [B has Cap.1..x.2]

This gives the correct outcome, because A cannot now revoke B's copy,
but revocation of any capability *upstream* from A causes the capability
held by B to be revoked.

The remaining questions are:

  1. By what authority is CapServer permitted to fabricate a capability
     cap.x....y (for arbitrary y) given that it already holds a
     capability cap.x? That is: what is "MagicOp"

  2. How do we make sure we get the permissions right? That is:
     what are the proper arguments to MagicOp?

Logically, the following operation will create the proper capability,
and it solves part 2:

   cap->CreateSubCap(cap1, perm-mask) => cap2

where:

   cap is some capability c..x
   cap1 is some capability c..x..y.z  That is, cap1 is a descendant of 
      cap in the revocation tree (c..x-y.z is okay)
   cap2 will be c..x..y.? where ? is any currently unused child index of
      c..x..y
   permissions(cap2) := permissions(cap1) & perm-mask

But wait! Notice that in the case where c..x..y.z is actually c..x=y..z,
this is just the COPY operation! I don't know if the generalization is
fully safe, but I *do* know that the COPY operation is fully safe. The
perverse thing to notice here is that you cannot correctly implement the
CapServer without some primitive that is a generalization of the COPY
operator, and of course if you had such a primitive you would not need
the CapServer.

          --------------------
         /                    \
         | Requiescat in Pacem |
         |                     |
         |   Hurd CapServer    |
         |                     |
         |     2004..2005      |
         |                     |
         |/\/\\\///\/\\//#\//\/|

Maybe somebody will come up with a better protocol, which would be
great. I suggest that it should be described using the notation that I
have used above, where every transfer is explicit and hierarchical
capability names are fully exposed. We have been fooling ourselves
because we haven't written the protocols down carefully.

shap