Markm: /* On the Spread of the Capability Approach */

Markm — Tue, 04 Jul 2017 23:01:11 GMT

On the Spread of the Capability Approach

←Older revision		Revision as of 23:01, 4 July 2017
Line 22:		Line 22:
	Early capability systems and the year the project started (as best I can tell).		Early capability systems and the year the project started (as best I can tell).

		+	<pre>
	1966: Dennis & Van Horn paper - MIT		1966: Dennis & Van Horn paper - MIT
	1967: PDP-1 Supervisor - MIT		1967: PDP-1 Supervisor - MIT
Line 43:		Line 44:
	1982: iAPX 432 - Intel		1982: iAPX 432 - Intel
	1982: Password-Capability System - Monash University		1982: Password-Capability System - Monash University
		+	</pre>

	If we date the origins of capabilities from the Dennis and Van Horn		If we date the origins of capabilities from the Dennis and Van Horn

Markm: Created page with "=On the Spread of the Capability Approach= by Bill Tulloh Aug 02, 2006; 08:14am :: Rate this Message: (use ratings to moderate[?]) Ever since reading a draft of the "Capabi…"

Markm — Tue, 04 Jul 2017 22:57:31 GMT

Created page with "=On the Spread of the Capability Approach= by Bill Tulloh Aug 02, 2006; 08:14am :: Rate this Message: (use ratings to moderate[?]) Ever since reading a draft of the "Capabi…"

New page

=On the Spread of the Capability Approach=
by Bill Tulloh Aug 02, 2006; 08:14am :: Rate this Message: (use ratings to moderate[?])

Ever since reading a draft of the "Capability Myths Demolished" paper,
I became interested in how these ideas have evolved and have been
gathering information from time to time on the various systems and
people involved. My interest is more from the sociology of the spread
of ideas and technologies than just the evolution of system
architecture, but given the questions that Jed has been raising lately
on this list it seems like a good time to share some of what I've
found.

My intent has been to try to pull this information together and write
it up for the erights website or something when time allowed, but
since I haven't found that time yet I'll give an outline here. I want
to be clear that this is preliminary and therefore incomplete and
likely to contain inaccuracies. I should also note that I have no
personal knowledge of these people and systems unlike some on the
list. I mostly have gathered this information from various published
sources I have found on the web or printed on dead trees.

Early capability systems and the year the project started (as best I can tell).

1966: Dennis & Van Horn paper - MIT
1967: PDP-1 Supervisor - MIT
1967: Magic Number Machine - University of Chicago
1968: CAL-TSS - Berkeley
1969: System 250 - Plessey Corporation
1970: CAP - Cambridge University
1971: Project SUE - University of Toronto
1971: Hydra - Carnegie Mellon
1972: RATS - Lawrence Livermore
1973: Actors - MIT
1973: PSOS - SRI
1975: StarOS - Carnegie Mellon
1975: GNOSIS/KeyKOS - Tymshare
1976: Monads - Monash University
1978: System/38 - IBM
1978: NLTSS - Lawrence Livermore
1980: SWARD - IBM
1980: PDP 11 operating system - University of Texas
1981: Amoeba - Free University Amsterdam
1982: iAPX 432 - Intel
1982: Password-Capability System - Monash University

If we date the origins of capabilities from the Dennis and Van Horn
work, ignoring related earlier work by Burroughs and Iliffe, then it
raises the interesting question that Jed has been asking, namely how
does this relate to the Multics design that was occurring at the same
place and roughly the same time. The mystery being why Multics emerged
as an ACL system and not a capability system. Unfortunately, I don't
have much to contribute to this question.

The first direct follow-on work to the DVH paper seems to be the PDP-1
Supervisor talked about in the Ackerman and Plummer paper, and the
design for the Chicago Magic Number machine at the University of
Chicago. There is not much published information on the Chicago system
that I know of except in the Levy book. Robert Fabry is the key
person. He had been at MIT where he may have had direct exposure to
these ideas, although the capability work was done at University of
Chicago while he was getting his PhD under Victor Yngve a
computational linguist and early machine translation proponent, who
had also been at MIT until 1965. This system was never built and the
only descriptions are in some working papers from the Institute for
Computer Research at the University of Chicago, which are often cited
but which I haven't found. The system did get written up by Maurice
Wilkes in his book on Time-Sharing Computer Systems published in 1968.

In fact if there was a "Mr. Capability" in these early days it would
seem to be Fabry. Wilkes met Yngve at a conference in 1967 which got
him interested in capabilities. He then went to visit with Fabry at
Chicago several times. Wilkes became enthusiastic and convinced
Plessey Corporation, where he was a consultant, to implement the Fabry
design in their new system. He also convinced Roger Needham to make
capabilities the new focus of their research at Cambridge leading to
the CAP project.

After getting his PhD, Fabry became a professor at Berkeley where he
became part of the active capability research that was occurring
there. It does not appear that he was directly involved in the CAL-TSS
system started by Lampson and continued by Sturgis but he had a lot of
indirect influence not least of which by serving as Dave Redell's
thesis supervisor, the thesis which presented the caretaker pattern
for revocation.

Another early system that Fabry influenced was the PSOS system
developed by Peter Neumann at SRI -- Fabry is thanked by Neumann for
his consultation on the early design of the system. Peter Neumann had
previously been involved in the Multics design at MIT.

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. 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. 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.

Project SUE was a capability-based operating system project at the
University of Toronto, which involved James Horning and Dennis
Tsichritzis among others. I don't know too much about this project but
it seems to have kicked off in 1971.

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.

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

The Actors work of Hewitt is a bit of an outlier in that it is a
programming language and not an operating system, but it was
influenced by the capabilities work and recognized the granovetter
property. I'm not sure the direct source of influence but Henry Baker
was apparently part of Dennis' Computational Structure Group at MIT.

My apologies to the Australian's on the list because I haven't sorted
through the rich capabilities tradition that emerged from there. J.
Leslie Keedy's work on the Monads project begun in 1976 seems to have
been a major source. This continued in numerous projects in Australia
and elsewhere such as the Password-Capability system of Anderson, Pose
and Wallace, the Mungi system, Opal, and SpeedOS.

The Amoeba Distributed Operating System was another (albeit different)
password capability system that seems to have gotten started around
1981. Andrew Tannenbaum is the main player.

IBM may also have been an early adopter of capability design with
their FS (Future System) design that was supposed to replace the 360
system. This project began in 1971 and was cancelled in 1975 because
it was seen as too complex and the 360 had already become a standard
that could not be easily abandoned. Emerson Pugh in his book, Building
IBM, refers to the FS design as an object-oriented system and notes
that the System 38 incorporated many of its advanced features. The
Sward project occurred later and built on the System 38 design.

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.

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.

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, 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.

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

OnTheSpreadOfTheCapabilityApproach - Revision history

Markm: /* On the Spread of the Capability Approach */

Markm: Created page with "=On the Spread of the Capability Approach= by Bill Tulloh Aug 02, 2006; 08:14am :: Rate this Message: (use ratings to moderate[?]) Ever since reading a draft of the "Capabi…"