[cap-talk] On the Spread of the Capability Approach

Jed at Webstart donnelley1 at webstart.com
Wed Aug 2 19:50:40 EDT 2006


At 11:14 PM 8/1/2006, Bill Tulloh wrote:

<a delightful summary of early capability development.  I'm doing some
work on the sides to help fill in parts that I have some knowledge of.
I just include a few notes here>

>...
>In fact if there was a "Mr. Capability" in these early days it would
>seem to be Fabry.

I was always a bit puzzled by Fabry's position on capabilities.
As you say he seemed to be an early adopter, but then had little
involvement in later capability developments.  I would be very
interested to hear his thoughts on capabilities generally
and approaches to POLA.

>I'm not sure how Lampson became interested in capabilities but he was
>also an early adopter. He started the CAL-TSS project and was one of
>the key designers.

And of course there is his famous negative comment about
capability based systems, "Capability based systems are the
way of the future—and they always will be."

I've always taken the above comment as something of sour
grapes.  He couldn't make a capability system work (Cal TSS),
and so became negative on then - somewhat deriding the efforts
of others.  I'd be interested to hear Lampson's current position
regarding POLA, ambient authority, etc.  Because of Lampson's
influence, I think his move away from capabilities and his negative
comments influenced the field significantly.  In some ways I'd
say it validated the sorts of ambient authority approaches that
one sees in Unix and Windows.

About Cal TSS Lampson says:

"Cal TSS (1968-71): This was the first working 
capability based operating system, and for many 
years the only one done for a large computer [7, 
15]. With Howard Sturgis and others I did the 
design, though I did not write any code. Many of 
the ideas in the Hydra system for C.mmp and its 
descendants are identical to those in Cal, though 
usually derived independently several years 
later. This system ran successfully at Berkeley 
for about a year, and then was abandoned for a 
combination of technical and political reasons."

which is of course untrue as the PDP-1 supervisor 
clearly preceded it.  He might have been doing
some filtering by size - considering the PDP-1 
system as insignificant - but I really don't think the
Cal TSS system got enough users to put in into another category.

>His involvement didn't last too long however
>because he left to form the Berkeley Computer Corporation, later to
>join Xerox PARC when BCC failed. I'm not sure if BCC's system was
>capability-based or not.

It was not.  The whole idea of BCC was to have a micro programmed
computer that could emulate other computer systems.  Then it would
sell time on any type of system for any organization that needed additional
capacity.  Very ambitious, doomed to failure.  Particularly when they wouldn't
accept defense money on principal.  I worked for some time for Bob Abbott
who worked at BCC and I often heard discussions about what happened
there.  I've been in contact with Bob Abbott (Charlie Landau also worked
for him) recently, though I don't think Bob has 
much of a role in capabilities -
except supporting Charlie's work on RATS and perhaps providing a great
environment for me to flourish in the computer area and to go on to work
on NLTSS and LINCS.

BCC was agnostic about operating systems. It would run the OS that
came with the system on its micro programmed emulation of the hardware.

The only emulations that were completed were one for the SDS 940 and a
native one - that ran at the University of Hawaii for some years.  One
interesting aspect of that system is that, at least after it got to Hawaii,
they were never able to rebuild the system from source.  They always
had to patch it to make changes.  Mel Pirtle was also a principle in
BCC and then went on to be a major player in the Illiac IV development.

>Howard Sturgis was the other key designer of
>CAL TSS and wrote his dissertation on the experience. Others invovled
>included Jim Gray, Dave Redell, Bruce Lindsay, Paul McJones, Vance
>Vaughn, and Charles Simonyi. Paul McJones has an archive of most of
>the CAL-TSS documentation and source code online.

I guess you mean this PDF file:

http://www.mcjones.org/CalTSS/CalTSS.pdf

with embedded links to Cal TSS documentation.  Hot stuff!  I'll try to find
some time to take a look through there as I'm quite interested to learn more
about that system.

Sigh.  I guess I should scan and post more of the NLTSS documentation.

>The Hydra project at Carnegie Mellon was a very influential project
>that started around the same time under the leadership of William
>Wulf. Others involved included Anita Jones, Ellis Cohen, Roy Levin,
>Bill Corwin and Fred Pollack. One could argue that this was the first
>true object capability system. Their work influenced a number of
>subsequent projects including KeyKOS, StarOS, IBM System/38, and the
>Intel 432, not to mention the whole take-grant approach to modeling
>capabilities.

With all these projects going on at about the same time, one wonders
what could have happened regarding collaboration if the communication
infrastructure of the time was richer.  I read quite a bit about Hydra in
those days.  I also happened to room with Roy Levin at an ARPA grad
students conference in Asilomar - perhaps in 1975?  I've had recent
contact with Roy who worked for Digital Research and now for Microsoft
Research.  Of course Hydra was a multiprocessor effort to a large extent.
I don't really remember enough about the capability architecture of Hydra
to comment.

>Charlie and Jed can do a better job of explaining the RATS, DCCS, and
>NLTSS work done at Lawrence Livermore than I can.

At a high level RATS was a port of the PDP-1 supervisor with some
improvements.  I was technical liaison for the LLL ARPA Network site
in those days and was involved to some extent in protocol design, e.g.
early Telnet and FTP.  I got excited by the ability to extend RATS through
the entry mechanism in juxtaposition with the ARPA network work and
one evening had a "brain storm" imaging the DCCS mechanism.  I then
fleshed out the details and wrote the paper:

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

with some discussion with Charlie.  We considered implementing that
system, but it turned out that one critical resource, the file resource in
RATS could not be extended (emulated through the entry mechanism)
as has been discussed elsewhere on this list - because of the way
virtual memory was mapped in RATS as an invocation on a file rather
than on a process (remember, this is high level).  I don't know if we
would have had time/inclination to implement something like the DCCS
on RATS without that problem - likely not, as many other things were
happening at that time and we had no funding for such work.

I wrote up a summary of "Capability Computing at LLNL" here:

http://www.computer-history.info/Page4.dir/pages/LTSS.NLTSS.dir/pages/cap-livermore.html

that describes how we got to NLTSS.  There was an independent thread
that came to LLL through some early Multics papers that John Fletcher
interpreted as a capability architecture.  John 
implemented the Elephant storage
system at LLL and the "Gator" operating system 
using that capability architecture.

I'm going off on a bit of a tangent to get more information about that thread.

There is also a wikipedia writeup on NLTSS that I wrote:

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

That might be a good hook for some more documentation on NLTSS.
There is also a student paper that describes NLTSS:

http://www.computer-history.info/Page4.dir/pages/LTSS.NLTSS.dir/pages/NLTSS.pdf

>There are some other systems that came later than 1982 such as
>Rashid's Mach kernel that are capability based but this seems like a
>good place to stop.

I think the Mach work should be included as in some sense I see it
as the last of the OS development of that era.

Also you don't mention Demos:

http://portal.acm.org/citation.cfm?id=806544&coll=portal&dl=ACM

Since that work happened at Los Alamos (in some ways LANL's
effort to get into the OS business - compete with LTSS and NLTSS
from LLL) I probably know more about it than most.  At LLL we
even picked up their "Model" language (Pascal with some OO
additions) that we had to support for many, many years after
Los Alamos abandoned it because most of NLTSS was written
in Model (a mistake in hind sight).

Demos was yet another system that had a mechanism to block
delegation.  It was as explicit as a "do not delegate" bit in their
capability equivalent - "port"s.

>If I were to give a high-level overview of the history of capabilities
>it would go something like this:
>
>1966: capability design first articulated, at roughly the same time
>the ACL paradigm emerged in Multics. Numerous capability-based system
>design projects were started; much progress made in working out the
>kinks.
>
>1976: represents something of a high water mark for capabilities:
>where capabilities were, if not necessarily the dominant design, at
>least a widely proposed one. See for example the articles by Peter
>Denning on "Fault Tolerant Computing" and by Theodore Linden on
>"Operating System Structures to Support Security and Reliable
>Software" that appeared in the same issue of Computing Surveys that
>year.
>
>1986: represents something of a low water mark for capabilities. By
>this time much of the work on capability had stopped or as in the case
>of KeyKOS was struggling for survival. One can look at the articles
>published in Operating Systems Review as one example where as late as
>the October  1985 issue there were several articles on capabilities,
>including one on KeyKOS. However after that issue, one is hard-pressed
>to find such articles.
>
>1996: one starts to see a renewed interest in capability ideas. In
>addition to the work evolving from KeyKOS (EROS and E). There is
>Jonathan Ree's thesis on W7, the work at Cornel on J-Kernel, and work
>on capabilities at the University of Oveida in Spain. All of which
>started to appear in the second half of the 1990s.
>
>2006 -  perhaps this is the decade when real progress is finally made :-)
>
>If I had to account for the decline in fortunes from 1976 to 1986, I
>would attribute to it to three things: the success of Unix, the view
>that capabilities couldn't solve the military requirements for
>multi-level security, and the rise of the PC. The first two are both
>direct legacies of the Multics path. Unix, of course, was a direct
>descendant of Multics. What may be less well known is that it was
>Robert Fabry who was responsible for bringing it to Berkeley leading
>to BSD Unix. This marked an end of the capability research at
>Berkeley. One suspects the adoption had more to do with the unique
>open source licensing and flexibility that Unix offered rather than
>Unix's security properties.

Though I expect that, like Lampson, Fabry saw little practical appeal
in capabilities and considered them an architecture of the past.

One question one must ask is what compelling problem is there
that needs solving for which capabilities are the answer?  In my
opinion that problem (one might say a "killer ap" for capabilities)
is malware.  Mutual suspicion has been a technical issue for
many, many years (at least since the Michael Shroeder thesis),
but I don't believe it has been a serious practical problem until
the rise of the Internet/web.

One thing that struck me about the above history is that it seems in
many ways to parallel the history of the development of virtual
machine monitors.  I haven't looked into this thoroughly, but
I think virtual machine mechanisms started a bit later, in the
very late 1960s or early 1970s, peaked during the 70s with
VM370 and some PDP-11 work and perhaps other (?), and
then gradually died out.  Perhaps in a similar way the rise
of the PC and having computers more available and the lack
of a compelling requirement lead to the gradual falling to the
wayside of virtual machine technology.

Now virtual machines are at least on the rise again.

I wonder if there are other computer technologies that
had a similar rise, fall during the computer middle ages
(when money grew on trees and a monkey could program),
and then are on the rise again?

>Multics also had a major influence on the DOD approach to security.
>Roger Schell, an air force Major at the time, got his Ph.D. at MIT
>working on the Multics project. He was influential in defining the
>resource monitor/security kernel view of security that appeared in the
>Ware report. His group at the Air Force was later instrumental in
>implementing those ideas, all with a heavy Multics flavor. He led the
>tiger team that successfully attacked Multics, directed the Bell and
>La Padula work at Mitre,

Ah, that's an interesting connection for me.  As we (Charlie Landau
and I and others) were working in the RISOS (Research Into the Security
of Operating Systems) at LLNL in the early 1970s Roger Shell's name
came up a number of times.

>and supported the efforts to build a secure
>kernel for Multics. Besides Schell there is Boebert who was head of
>the Multics project at Honeywell. All of this fed into a Multics
>influenced view of trusted systems enshrined in the Orange Book. This
>thread remained sceptical/hostile to the capabilities approach.

Quite true.

>Probably the most important factor however was the rise of the
>personal computer around this time. PC's, like the early batch
>processing systems, were too resource constrained and disconnected to
>pose much of a security issue. Their rapid adoption also put the nail
>in the coffin of the time-sharing industry, depriving us of KeyKOS. It
>wasn't until the issues that KeyKOS was designed to solve started
>reemerging in wake of the web explosion that people started becoming
>interested in capability approaches again.
>
>Well that is more than enough for now. Perhaps it would be worthwhile
>to create a wiki or blog where I can post more of this information and
>others can contribute.
>
>Bill

Thanks for the review Bill.  Quite helpful.

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





More information about the cap-talk mailing list