MarkM answer: RATS, DCCS, and membranes for network capabilities (was: Re: [friam] Re: What is a capability?)

On 1/8/2015 11:42 PM, 'Mark S. Miller' via friam wrote:
> On Thu, Jan 8, 2015 at 11:08 PM, Jed Donnelley <capability-iCFHVraI1K1Wk0Htik3J/[email protected]>
> wrote:
>> On 1/8/2015 4:53 PM, Kevin Reid wrote:
>>> (Kevin Reid): This is what I think of as the difference <cap vs. object-cap>, and I hope MarkM would agree:
>>>
>>> A capability system is one which has the laws of locality, designation-and-authority-are-not-separated, etc.
>>>
>>> An object-capability system is a capability system in which the primary operation on a capability is "send a message", the message has a "selector"/"method name"/"verb" field, and all capabilities are on an equal footing in this way. And, more subjectively, the capabilities correspond to objects in an object-oriented programming language.
>> (Jed): Hmmm.  Perhaps I've been focusing on the wrong thing or over simplifying.
>>
>> *For me the relevant distinction is the membrane pattern.  If a
>> capability system supports the membrane pattern (and thus can implement
>> services like network capabilities, the Horton responsibility tracking
>> mechanism, and other services that depend in this functionally invisible
>> "insertion" property) then its "object-capability".  If not, not.*
>>
>> This is why I've encouraged those implementing capability systems to
>> test them with a membrane implementation.
>>
>> I'm not sure how this ability to support the membrane pattern maps into
>> the above description.
>>
>> Can somebody describe the relevant difference and perhaps why the choice
>> (definition?) has been made as it is?
>
> ...
>
> (MarkM): KeyKOS is where I got the idea of membranes (from their KeySAFE design,
> although your DCCS preceded it by many years). Thus, it would be strange to
> claim that membranes are not possible in the KeyKOS family. But Kevin's
> point about pages leaves me wondering if transparent membranes are
> possible <in KeyKOS>...
>
> So, I think there are three levels of increasing specificity:
>
> a) ocap
> b) ocap where limited non-transparent membranes are possible
> c) ocap where transparent membranes are possible.

Nice formulation.

> (MarkM): Joule, E, and SES are in #c. IIUC, so are Actors.
>
> Jed, is it correct to say that DCCS is in #c as well? How did you handle
> mapping and virtualization of addressable memory resources?

Excellent questions.  The short answers are:

1.  Yes, I believe (not enough implementation was done to be sure, but
that was the design), and

2.  The idealized "Capability Computing System" ('CCS') was designed
specifically to avoid any issues with memory mapping and to simplify the
membrane implementation for the DCCS.

I believe a somewhat longer answer may be worthwhile in this case for
some people (skip past underlines '__________' to skip the history to
today's relevant issues):
________________________________________
I find it interesting that you (MarkM) say:

> ...KeyKOS is where I got the idea of membranes (from their KeySAFE design,
> although your DCCS preceded it my many years). Thus, it would be strange to
> claim that membranes are not possible in the KeyKOS family. But Kevin's
> point about pages leaves me wondering if transparent membranes are
> possible. ...

There is a similar relationship between the RATS OS:

Charles Landau, "An Introduction to RATS (RISOS/ARPA Terminal System):
An Operating System for the DEC PDP-11/45), March 1, 1974, LLNL
UCRL-51582:  http://www.webstart.com/jed/papers/RATS/RATS.pdf

and the membrane mechanism in the DCCS (perhaps Charlie can make any
needed corrections to the history).  The above noted RATS is a direct
descendant of the Dennis and VanHorn designed PDP-1 OS at MIT.  Charlie
Landau worked on the PDP-1 system at MIT.  Charlie was hired into the
Research Into the Security of Operating Systems (RISOS) ARPA funded
research project at LLNL (then LLL) I guess some time late 1971 or early
1972 (Charlie?).  Part of the work of that project was to develop a
computer system that would use communication means like the nascent
ARPAnet and telephone access to connect to other systems and to break
into them (tiger team white hat).  Charlie was hired at least partly
(mostly?) to develop the software to run on that ARPA network host
computer system which was, as noted above, a DEC PDP-11/45.  That the
system Charlie implemented resembled the DVH system was not surprising
or unanticipated.  I consider his work to implement RATS on that
PDP-11/45, driving the ARPAnet IMP, and implementing the ARPAnet
protocols (along with considerable other programming work), in as short
a time as he did the work (~2+ years?), a programming tour de force.

In 1972 I was a recent graduate from UC Davis where I'd been steeped in
the Burroughs architectures in the hacker tradition.  I joined RISOS
early in 1973 mostly to participate in cracking exercises (in my case
mostly for the PDP-10 "Tenex" systems that were then dominant on the
ARPA network, mostly due to Bolt Beranek and Newman's heavy involvement
in both the TENEX and the ARPA network implementations) and to develop
techniques to systematize such work, though I also did a little bit of
programming work for RATS.

Early in the RISOS work one of the roles I took on was as the "Technical
Liaison" for the LLNL ARPA network site.  As part of this work I
participated in design and implementation discussions for early ARPA
network protocols like those for "terminal" sharing (telnet), file
sharing (FTP), email, etc.

The combination of my having the object oriented OS background from RATS
and the Burroughs equipment and being involved in the early ARPA network
protocol development put me into a position where the concepts of the
DCCS were a pretty natural development.
___________________

The basic idea of the DCCS was:  instead of developing independent
network protocols with distinct semantics for different sorts of
resources like terminals, files, RJETs, email (all ARPAnet resources
circa 1974), etc., why not develop a network protocol to share generic
"objects" and let the semantics of the different resources be hidden
within the objects, thus keeping those semantics out of the network
protocols?  One network sharing protocol would then suffice for sharing
objects of any type and wouldn't require new protocols to be designed
and implemented as new types of objects were shared across the network.

Since RATS was an object-capability system derived from the DVH system
and had an "entry" mechanism (master and slave "entries" as you can see
in the above RATS paper if you want to understand the details) as it's
extension mechanism, it was natural for me to ask whether I could use
the RATS entry mechanism to represent objects from other OSs on a
network like the ARPAnet.  As I considered such a mechanism, especially
when considering two such RATS systems on a network, I was naturally led
to the membrane mechanism for representing ("emulating"?) those remote
objects.  I well remember the "blinding flash" inspiration one night
when it became clear to me that such a mechanism was possible.  That was
a very exciting night with no sleep possible.

Unfortunately (related to your note about KeyKOS MarkM), the next day
when I started to work out the details for implementing the DCCS on the
RATS OS I discovered that there was one important base object supported
by the RATS kernel, namely the "File" object that provided for data
storage/memory mapping, that couldn't be emulated by the RATS entry
mechanism.  The way the RATS File object worked was that one could
'invoke' a File object and ask that it be mapped into memory -
implicitly into "your" memory - i.e. into the memory space of the
invoking process.  In some sense the change in the memory space of the
invoking process was a side effect of the invocation of the File object
that couldn't be emulated by an "Entry" object.

At this point Charlie and I discussed this issue/problem.  I would say
that in terms of your #a, #b, and #c characterization above that the
RATS OS was somewhere between #a and #b, but unfortunately not all the
way to #c.  In our discussions Charlie and I discovered (came to believe
- again perhaps Charlie can chime in) that a rather simple change to the
implementation of the File object in RATS - specifically to change the
"Map" call to be an invocation on a Process object passing in a File
object for the mapping - would suffice to transform RATS to #c and allow
the DCCS to be implemented over the RATS OS.  Without being able to
support the base File object on RATS something like the DCCS would have
limited value.

Sadly by the time we realized this (late 1975) several things were going
on that made it impossible for us to make such a change to RATS and to
implement the DCCS over RATS.  The RISOS research was winding down, so
we were both starting to look toward other work and had less time to
work on RATS.  We realized that a change to the basic "Attach" (map)
system call on RATS would alter its API enough that almost none of the
software written for RATS would still work.  Of course other approaches
such as supporting both the existing "Attach" and a new "Attach" that
was an invocation on a Process capability would be possible.  By that
time, however, it was becoming clear that we wouldn't have time to
implement such a change, let alone to implement the DCCS on top of it
(though I worked for some years trying to get funding close enough to
this area to do that work).

I felt that the idea of using an object sharing network protocol that
could be implemented on such a 'membrane' (not a name I used) emulation
mechanism for capability objects from an underlying OS that was #c (as
MarkM notes above) was important enough that I should publish a
description of this mechanism/approach.  Consequently I invented an
idealized "CCS" (Capability Computing System) based on RATS but
simplified (e.g. I conflated the file and process objects into a single
type and didn't use mapped memory) so as to be #c and easier to describe
in a paper.  I then described the remote network emulation
implementation using the "membrane" facility that could be used to
extend the objects of such a CCS across a network via the described
"DCCS" protocol.

I distributed RFC #712 in February of 1976:

https://tools.ietf.org/html/rfc712

based on a draft of the DCCS paper that I was in the process of having
reviewed for eventual reviewed publication in the Proceedings of the
Third International Conference on Computer Communication, Toronto,
Canada, August 1976:

http://www.webstart.com/jed/papers/DCCS/

The most important aspect of this paper is the mechanism not just to use
the "insertion" property of the entry capabilities to make remote
objects available, but to allow capability tokens to be communicated
across the network as normal call parameters in a transparent way (the
essential aspect of the membrane pattern IMO).

I don't remember when Charlie left LLNL for Tymshare, but it was at
about that same time.  Not long after this Charlie started working with
Norm Hardy and Bill Frantz on GNOSIS that I guess became KeyKOS.  Also
not much later I started working on a capabilities as data OS (for
reasons that would get into another topic) that eventually became LINOS
(referred to within DOE and LLNL as "NLTSS":

https://en.wikipedia.org/wiki/NLTSS

) and ran in production at LLNL until 1995. 

By the time those systems (KeyKOS and NLTSS and others) were developed
the technological "tide" had turned against the sort of
principle-of-least-authority object (capability) operating system
designs represented by such work.  In my view a significant reason these
sorts of systems fell out of favor was, somewhat ironically, push back
from the national security community.  In particular as discussed often
on this cap-talk list there was the document from the Institute for
Defense Analysis P-1935 published in February of 1987:

http://www.webstart.com/jed/papers/P-1935/

"TRADITIONAL CAPABILITY-BASED SYSTEMS: AN ANALYSIS OF THEIR ABILITY TO
MEET THE TRUSTED COMPUTER SECURITY EVALUATION CRITERIA"

This document was an influential instance among other writing and people
in the community that took the position that sharing access by tokens
communicated in messages was inadequate to meet security criteria being
defined in that time.  In particular these criteria required (among
other things) the ability to track responsibility for system actions
(operations on objects) and to log actions for auditing purposes.  While
the above noted document is titled "their ability to meet", what it
really describes is their (capability-based systems) *inability* to meet
the developing "Trusted Computer Security Evaluation Criteria". 
Specifically the inability of "traditional" capability-based systems to
support responsibility tracking and logging for auditing.

Work on systems with object sharing by tokens (capabilities) continued
for a while.  I had somewhat lost track of the work Charlie, Norm, and
Bill Frantz were doing on on GNOSIS/KeyKOS while focusing on my own
LINOS/NLTSS work.  I believe I spoke to them at one time about why I
valued the membrane pattern (for something like DCCS), but none of us
had time to follow up.  I'd be interested to hear if/how they considered
this criteria #c in their GNOSIS/KeyKOS work.  I didn't hear about the
KeySAFE design until many years later and I still don't understand it
very well.  The next time I saw something that resembled the
DCCS/membrane mechanism was in this design paper published by the Mach
group:

Dan Julin, *Network Server Design, Mach Networking Group*. September 1989.

which can now be found through:

https://www.cs.cmu.edu/afs/cs/project/mach/public/www/doc/publications.html
at:**http://cs.cmu.edu/afs/cs.cmu.edu/project/mach/public/doc/unpublished/netmsgserver.doc

I don't believe that design was ever implemented either, but it had the
same basic architecture as the DCCS, though was apparently derived
independently and required some rather twisted (IMO) mechanisms to
conform to the Mach "port" mechanism.

I got involved in other areas (network research) and no longer tracked
this area enough to follow the winding down of the KeyKOS work and I
didn't hear about MarkM's work until I discovered the cap-talk list,
EROS, etc. in what appears to be the early 2000s.
___________________________
My involvement with the cap-talk list has been quite an interesting
experience, but for me it had it's greatest relevance when MarkM, I, and
AlanK did the work to flesh out the Horton protocol for tracking
responsibility for actions on objects in object-capability (actually I
guess I now have to say #c) systems:

http://www.erights.org/elib/capability/horton/

The Horton mechanism depends vitally on the same "membrane" pattern used
in the DCCS.  Specifically on the ability to communicate object tokens
"through" the emulation 'membrane'.  The Horton protocol demonstrates
that the claims of P-1935 that capability systems can't log and track
responsibility for actions are not true - at least not for #c capability
systems.

It was because I believed so strongly in the network capability
extension mechanism (essentially the ability to "serialize" capabilities
transparently on a network) that I thought it important that capability
systems support the membrane pattern.  In particular my experience with
RATS, where a seemingly minor aspect of it's object invocation interface
for one object (having the system call to map memory be an invocation on
a File rather than on a Process) made the membrane pattern impossible to
implement, caused me to believe that the ability to implement the
membrane pattern was an important criteria that should be applied to
test potential object-capability system implementations.  My thought was
that only by actually doing an early membrane implementation could such
potentially "minor" flaws in the capability invocation mechanism be
avoided that could make it impossible to support important services like
network capabilities, Horton-like responsibility tracking, (KeySAFE?), etc.

I believe the membrane pattern is still important today for these same
reasons.  IMO there should be particularly critical reasons for any
capability system to be implemented without the ability to support the
membrane pattern (i.e. #a or #b) - because without that ability
facilities like the DCCS sort of network extension and the Horton
responsibility tracking aren't possible.  Any such #a or #b
implementations should acknowledge up front (and in any case must
eventually acknowledge) that they are giving up any facilities that
might depend on the membrane pattern.  Designer/implementer beware.

--Jed  http://www.webstart.com/jed/

_______________________________________________
cap-talk mailing list
[email protected]
http://www.eros-os.org/mailman/listinfo/cap-talk