From Erights

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