[cap-talk] Object-Capability Patterns: An Historical Overview

[Jed Donnelley]

At 09:12 AM 3/19/2008, Mark Miller wrote:
>On Wed, Mar 19, 2008 at 8:12 AM, Toby Murray 
><<mailto:toby.murray at comlab.ox.ac.uk>toby.murray at comlab.ox.ac.uk> wrote:

Good stuff.  I hope we get a convenient list of references out of this work.

> >  Pattern             First Described By      Has Appeared In
> >
> >  Sealer/Unsealers    Morris in 1973 in CACM  Gedanken, E, KeyKOS, Caja, ?
> >  Trademarks          Morris in 1973 in CACM  Gedanken, E, KeyKOS?, ?

Interesting.  Can somebody point me to the above Morris 1973 
reference?  Might that be this:

"Protection in programming languages"
http://portal.acm.org/citation.cfm?id=361937&coll=portal&dl=ACM
?

> >  RevocableForwarder  Redell in 1974 in PhD   E, ?
>
>KeyKOS has 2 kinds of revocable forwarder primitives built in. Nodes 
>in the segment tree can be described as specialized forwarders for 
>memory reads and writes (potentially translating the address as it 
>forwards the request). So-call "red segments", IIRC, are tagging 
>forwarders one can place in front of start keys, which forward 
>invocations. Either is revocable. Red segments are caretaker-like 
>rather than membrane-like. The caretaker vs membrane issue doesn't 
>arise for KeyKOS segment trees, since they only forward memory reads 
>& writes, which carry only data, not capabilities. At one point EROS 
>provided CaPages at one point -- seemingly mappable memory holding 
>capabilities. If the same issue arose there, the mapping nodes would 
>have been caretaker-like rather than membrane-like.
>
> >  Coercers             ?                      E, Joule?, ?
>
>First described by Tribble et al in the Joule manual as the 
>"verifier pattern". Inspired by various attempts by the early actors 
>group at MIT to bottom out actors in a principled way without any 
>use of EQ. See, I think, some paper by Henry Lieberman on the design 
>and implementation of Act-1.
>
> >  Membranes           Stiegler?, Miller?      E, ?
>
>Using membranes for access control is first described by, I think, 
>Susan Rajunas in the design of KeySAFE -- Key Logic's plan to build 
>MLS on pure ocaps. However, essentially the same pattern is used to 
>transparently stretch ocap systems between machines. In this regard, 
>the first is Jed's DCCS.

Even thought I consider it's value reduced by not supporting 
persistent network capabilities, I think the Mach Network Server, e.g.:

Dan Julin. Network Server Design, Mach Networking Group. September 1989
ftp://ftp.cs.cmu.edu/project/mach/doc/unpublished/netmsgserver.ps

should be mentioned in this regard because it used the same basic 
membrane pattern and in fact the same basic network 
"stretching"/serializing pattern as the DCCS mechanism before it and 
the later vat mechanism.

I wonder if its worth distinguishing the transparent "stretching" as 
MarkM refers to it (serializing) of capabilities across a network as 
a pattern distinct from but based on the membrane pattern?

The DCCS reference that MarkM referred to is:

Donnelley, J. E., "A Distributed Capability Computing System," Proc. 
of the Third International Conference on Computer Communication, 
Toronto, Ontario, August 3-6 1976 (ICCC, 1976), pp. 432-440.
http://www.webstart.com/jed/papers/DCCS/

though the same essential mechanism was published in:

J. E. Donnelley, "DCAS" - A Distributed Capability Access System, 
Lawrence Livermore Laboratory Report UCID-16903, August 1975.

and also as an ARPA network Request For Comments (RFC):

0712 Distributed Capability Computing System (DCCS). J.E. 
Donnelley.  February 1976.

(e.g. from: http://www.ietf.org/iesg/1rfc_index.txt )

> >  Powerbox            Stiegler?, Yee?         E, Plash, Emily, ?
>
>Yes.

Are there references that one can point to for the Powerbox pattern?

> >  One goal here would be to archive this information on 
> <http://wiki.erights.org>wiki.erights.org
> >  in a sensible place. Once the list reaches a fixed-point, I'd be happy
> >  to do that.
>
>Wonderful!
>
>What other basic patterns should be on this list?

Hmmm  Well, I'll suggest a possibility.  In our NLTSS work we had a
simple "newcap" function as what might be considered a poor man's
revocation.  It simply invalidated all outstanding capabilities
for an object and created a new capability (ref.) for that
object.  Such a mechanism could easily allow one to "re issue"
access to an object and be confident that any prior access that
might have leaked or been otherwise inappropriately delegated
would no longer be a problem.  I don't know where else that
"pattern" might have been used, but I think it worth mentioning.

I believe Horton deserves to be mentioned in this list.  Of course
Horton is built on the membrane pattern, but its a very specific
use of that membrane pattern to track delegations by ID (who)
and to enable selective revocation.

--Jed  http://www.webstart.com/jed-signature.html 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.eros-os.org/pipermail/cap-talk/attachments/20080319/fb7288b2/attachment.html