Capability-based addressing

In computer science, capability-based addressing is a scheme used by some computers to control access to memory as an efficient implementation of capability-based security. Under a capability-based addressing scheme, pointers are replaced by protected objects (called capabilities) that can be created only through the use of privileged instructions which may be executed only by either the kernel or some other privileged process authorised to do so. This effectively allows the kernel to control which processes may access which objects in memory without the need to use separate address spaces and therefore requiring a context switch when an access occurs.

Practical implementations

Two techniques are available for implementation:

• Require capabilities to be stored in a particular area of memory that cannot be written to by the process that will use them. For example, the Plessey System 250 required that all capabilities be stored in capability-list segments.
• Extend memory with an additional bit, writable only in supervisor mode, that indicates that a particular location is a capability. This is a generalization of the use of tag bits to protect segment descriptors in the Burroughs large systems, and it was used to protect capabilities in the IBM System/38.

The designers of the System/38's descendent systems, including AS/400 and IBM i, removed capability-based addressing. The reason given for this decision is that they could find no way to revoke capabilities^[1] (although patterns for implementing revocation in capability systems had been published as early as 1974,^[2] even before the introduction of System/38).

Chronology of systems adopting capability-based addressing

• 1969: System 250 – Plessey Company
• 1970–77: CAP computer – University of Cambridge Computer Laboratory
• 1978: System/38 – IBM
• 1980: Flex machine – Royal Signals and Radar Establishment (RSRE) Malvern
• 1981: Intel iAPX 432 – Intel
• 2014: CHERI
• 2020: CHEx86

Notes

References

• Fabry, R. S. (1974). "Capability-based addressing". Communications of the ACM. 17 (7): 403–412. doi:10.1145/361011.361070.
• Wulf, W.; Cohen, E.; Corwin, W.; Jones, A.; Levin, R.; Pierson, C.; Pollack, F. (June 1974). "HYDRA: the kernel of a multiprocessor operating system". Communications of the ACM. 17 (6): 337–345. doi:10.1145/355616.364017. ISSN 0001-0782.
• Denning, P. J. (December 1976). "Fault tolerant operating systems". ACM Computing Surveys. 8 (4): 359–389. doi:10.1145/356678.356680. ISSN 0360-0300.
• Levy, Henry M. (1984). Capability-based computer systems. Maynard, Mass: Digital Press. ISBN 978-0-932376-22-0.
• Linden, Theodore A. (December 1976). "Operating System Structures to Support Security and Reliable Software". ACM Computing Surveys. 8 (4): 409–445. doi:10.1145/356678.356682. hdl:2027/mdp.39015086560037. ISSN 0360-0300. [1]
• Viktors Berstis, Security and protection of data in the IBM System/38, Proceedings of the 7th annual symposium on Computer Architecture, p. 245-252, May 6–08, 1980, La Baule, United States
• W. David Sincoskie, David J. Farber: SODS/OS: Distributed Operating System for the IBM Series/1. Operating Systems Review 14(3): 46-54 (July 1980)
• G. J. Myers, B. R. S. Buckingham, A hardware implementation of capability-based addressing, ACM SIGOPS Operating Systems Review, v.14 n.4, p. 13-25, October 1980
• Houdek, M. E., Soltis, F. G., and Hoffman, R. L. 1981. IBM System/38 support for capability-based addressing. In Proceedings of the 8th ACM International Symposium on Computer Architecture. ACM/IEEE, pp. 341–348.
• The Cambridge CAP Computer, Levy, 1988
• Plessey System 250, a commercial Capability solution, Hank Levy, 1988
• G. D. Buzzard, T. N. Mudge (1983) Object-based Computer Systems and the Ada Programming Language [2]. The University of Michigan – Computer Research Laboratory and Robotics Research Laboratory Department of Electrical and Computer Engineering

External links

• "[cap-talk] On the Spread of the Capability Approach". Archived from the original on 2013-04-14. Retrieved 2007-07-16.