[cap-talk] Non-Delegatable Authorities in Capability Systems

[Kevin Reid]

On Dec 10, 2007, at 0:57, Toby Murray wrote:
> On Sat, 2007-12-08 at 23:19 -0500, Kevin Reid wrote:
>> 2. In section 1.4, you state:
>>> Importantly, in many object-capability systems the authority to  
>>> reply is not delegatable. Examples include systems such as E  
>>> [15], W7 [23] and the Annex Capability System [8] that never  
>>> reify this authority, making it impossible to delegate. Another  
>>> example is any capability-based IPC system that does not allow  
>>> the receiver of a message to transfer the capability used to send  
>>> back the reply. The EROS operating system is a counterexample,  
>>> since it allows the receiver to transfer the resume capability  
>>> that is used for sending back the reply [25].
>>
>> If I understand what an EROS resume capability is, then this is  
>> false for E.
>
> Right. I had presumed that for local method calls that the "return"  
> statement in E was implemented by popping the current stack frame,  
> as in other object languages. Apparently not.

It would be useful to study Kernel-E and E expansions.

"to" is actually implemented as follows:

   to a(b) { c }

becomes:

   method a(b) { escape __return { c; null } }

"return" (an expression, not a statement) is:

   return     ->  __return()
   return a   ->  __return(a)

The escape-expr binds __return to an ejector which, if invoked before  
control flow exits its block, causes the escape-expr to return the  
provided value (or null) immediately from the block.

Ejectors may be considered single use, escape continuations.

>>  A resolver (eventual) or ejector (immediate) is precisely a  
>> "capability used to send back the reply" -- and under CapTP,  
>> pipelining means that the response resolver can be resolved to  
>> (delegating to) a promise which lives in some other vat, and may  
>> therefore outlast the confused delegator.
>
> Could you unpack the above a little. Does everything after "under  
> CapTP" apply only to the distributed case or the local case as well?

Only to the eventual (asynchronous) case. Not everything eventual is  
distributed. Also, CapTP is not (necessarily) a privileged system --  
its behavior is  within Kernel-E+ELib semantics.

> Ignoring the distributed case for now,

I expect that the distributed case is actually the more important  
one, in that the cases where non-delegation will be found useful will  
be distributed.

>>    # simple reification, immediate
>>    to bar() {
>>      leak(__return)
>>    }
>>
>
> by the above, does this mean that, when invoked, bar calls leak,  
> passing the capability that bar wouuld use to send back the reply  
> to its invoker? Hence, leak may return from the bar invocation, on  
> bar's behalf?

Yes.

> If so, then this would appear to break the semantics I had assumed.

Yes, that's what I wanted to point out. However, the right-of-future- 
reply is indeed nondelegatable, and this is (I argue) both necessary  
and sufficient.

>> However, an important characteristic of resolvers (and resume  
>> capabilities, IIUC) is that they are /use-once/: at most one  
>> response can be delegated, and so (in the preceding scenario) that  
>> response must be to a request made of Alice while she was confused  
>> (or she would not have leaked that particular resolver).
>
> Are ejectors (I'm presuming that __return in the above example is  
> an ajector and that "ejector" is (effectively) the capability used  
> to return from an invocation) also use-once?

Yes.

> Am I right in saying that the upshot here is that, in E, no- 
> delegation-of-a-reply is false (since ejectors can be delegated)  
> but reply caps are use-once?

Yes.

>> Minor comment: I expect that the actual results in a "buggy  
>> delegator" scenario depend on the exact mechanism used for  
>> upgrading the buggy program (what level of the system is  
>> replaced); i.e. the examples, containing no upgrade hooks, are  
>> unrealistic. Some upgrade hooks might defeat the no-delegation-of- 
>> future-replies property.

I'd like to call your attention to this; any upgrade mechanism will  
either involve some sort of interposition, thus adding a potentially- 
problematic (depending on its design) layer to the semantics you're  
concerned with, or will involve restarting a vat with new code, and  
therefore be necessarily the distributed case.

-- 
Kevin Reid                            <http://homepage.mac.com/kpreid/>