1759 'Historical Perspective' SEP-27

This is a 'Paper Reading' post for Course ECE1759. The topic is 'Historical Perspective'. This paper list is here:

  • B. Lampson, Protection, Operating Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.
  • J. H. Saltzer, Protection and the Control of Information Sharing in Multics, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 388-402.
  • W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack. HYDRA: The Kernel of a Multiprocessor Operating System, Communications of the ACM. Vol. 17, No. 6, June 1974, pp. 337-344.



Abstract models are given which reflect the properties of most existing mechanisms for enforcing protection or access control, together with some possible implementations. The properties of existing systems are explicated in terms of the model and implementations.

Core Ideas



  • by destroying or modifying another user's data.
  • by reading or copying another user's data without permission.
  • by degrading the service another user gets (like use up all disk or crash the whole OS)

Two Main Directions of Protection

  • Modular (So errors in one module will not affect another one.)
  • Support proprietary programs (So the program can only be called, but not read)

Protection Domain

  • Set Domains (Context). Each domain has its own objects and cannot access other domains' objects.
    • Only under supervisor state (Kernel state) programs can execute I/O instructions.
  • Example: On a system only use message to finish processes (Just like domains) communications instead of shared memory.

Objects and Access Matrices

  • The paper use a matrix to describe the privilege a user own.
  • Copy Bit is similar to current setuid bit

Capability & Access Control List

  • They are two types of access matrices.
  • Capability List
    • List of <object,access>
  • Access Control List
    • List of <domain, access>


message-base systems are securer.


  • High level


  • Still did not get what subsystem in the paper means.


Protection and the Control of Information Sharing in Multics


Introduced the mechanisms to control the sharing of information in the Multics systems.

Design principles help provide insight into the tradeoffs.

  • access control lists
  • hierarchical control of access specifications
  • identification
  • authentication of users
  • primary memory protection

Core Ideas

Design Principles

Five Principles

  • Base the protection mechanisms on permission rather than exclusion.
  • Check every access to every object for current authority. (Check every time if stateless, consider careful for storage if stateful)
  • The design is not secret. (Based on algorithms rather than secrets like passwords)
  • The principle of least privilege. (Get the users/processes as less privilege as possible.)
  • Human interface should be easy to use.

Two Objectives

  • Decentralization of the setting of protection specifications (Avoid bottlenecks, but centralization of authority must also be available as an option)
  • Assume that some users will require protection schemes not anticipated in the original design. (Multics allow users to create a protection subsystem for the objectives)

The Storage System and Access Control Lists

Memory protection

  • Virtual memory space: 262K 36-bit Words
  • Unit: segment

Access Control Lists

  • Associated with each segment is an access control list (Corresponds Lampson's protection matrix), an open-ended list of names of users who are permitted to reference the segment.
  • Each process have a id (principal identifier, just like username). When accessing will try to find the id in the target's list.
  • Multics' id actually have three partitions:
    • Almost direct user.
    • Groups called project. Users: Projects is M: N
    • Groups called Compartments. Users: Projects is M: N. But one can not use the resources in Compartment 'a' and the resources in Compartment 'b' at the same time.
  • In the access control lists, here's a special flag to indicate that the corresponding partition of the id does not matter.
  • There are 4 types of objects in the storage systems have protection mechanisms (Each of them have different types of controllable modes of access):
    • Segments.
    • Message queues (experimental implementation).
    • Directories (called catalogs in some systems).
    • Removable media descriptors (not yet implemented).
  • The access control lists are sorted and are initialized when the object is created.
  • An example of access control list entry is (none means no permission, rw means read&write):
    • Smith.Inventory. * (none)
    • * . Inventory. * rw
  • Compare with CTSS(Compatible Time-sharing System by MIT 1966)
    • It use links(with same name but has further restrictions) for file to share between users
    • Defects:
      • Revocation of access was awkward
      • One need to decide which link to use in order to correctly access the file. This can introduce mistakes.
      • One has to search every directory in the system to make a list of links in order to know the list of users who can access the file. It is expensive and compromised other users' privacy.
    • In Multics, a link is only an alias.
  • All user names, once registered, are permanent in the system even the user departs.
  • the "trap" extension was aborted because of complexity.
  • Limitation
    • Only the user can set privilege. So-called one way. For military use, the police can not read the criminal's file.

Hierarchical Control of Access Specifications

  • Why not "Common access control list": it make it difficult for a user to be sure of all the consequences of a change to the access specification
  • An alternatives:
    • Self-control: the ability to modify an access control list would be one of the modes of access controlled by the list itself

Authentication of Users

  • Users can have their username and password.
  • All the jobs must be initiated by some job already on the system, and whose legitimacy has been previously authenticated.
  • When the user is requested to give his password, at login time, the printer on his terminal is turned off.
  • User logging time-out mechanism is added.
  • Anonymous principal identifier is added.

Primary Memory Protection

The second level protection is implemented on hardware level.

  • Multics use addressing descriptors to describe segment. In the descriptors there are some bit (three types of extensions) to record privilege.
  • Storage accessing is achieved via virtual memory so it is also protected and need no other mechanism.


  • Many program modules are able to compromise the protection system. (about 15%, due to the inability to construct suitable descriptors)
  • The complexity of the user interface


  • Multics is time-sharing
  • Time-sharing need protection. But non-time-sharing systems like THE, have only a single user, so it do not need protection mechanisms.


  • Check the Comparison Section for the advantage of ACLs.
  • Detailed the defects of the Multics in the paper.


  • Check the Comparison Section for the disadvantage of ACLs.
  • The access control list entry is a little bit too complicated, which can introduce extra search burden.


HYDRA: The Kernel of a Multiprocessor Operating System


  • Kernel based
  • Two Goals of HYDRA:
    • To provide an environment for effective utilization of the hardware resources.
    • To facilitate the construction of such environments.
  • Considerations for a kernel
    • Multiprocessor environment.
    • Separation of mechanism and policy.
    • Integration of the design with implementation methodology.
    • Rejection of strict hierarchical laying. (Not structured programming globally)
    • Protection. (the kernel provides a protection facility for all entities in the system.)
    • Reliability. (Not only correct also able to discover and resume)
  • Target of mechanisms:
    • Support the abstracted notion of a resource.
  • Mechanisms provide:
    • Creation and representation of new types of resources, as well as operations defined on them
    • Protected access to instances of one or more resources within controlled execution domains,
    • Controlled passing of both control and resources between execution domains.

Core Ideas

Overview of the HYDRA Environment

  • Interrelationships of three object types: procedure, LNS, and process.
    • Procedure: procedure or subroutine (code). Examples: Read Write Update
      • code&data
      • parameters&return values
      • protection facilities
    • LNS: local name space
    • Capability: A capability consists of a reference to an object together with a collection of "access rights" to that object
    • Process: process, smallest entity which can be independently scheduled for execution.
      • inter-process communication and synchronization:
        • message buffering and semaphore
  • HYDRA provides a protection mechanism for the application of operations (procedures) to instances of resources (objects).
  • separating mechanism (the ability to do an action) from policy (condition enforcing a mechanism).

The Protection Mechanism


  • Check the Comparison Section.


  • Check the Comparison Section.




  • Weakness:
    • hard to implement, contains a lot of operations for gaining and losing.
  • Strength:
    • Faster, fast to check, only check for the first time
    • Flexibility, Process can get and lose while executing


  • Easy to implement
  • Weakness: Slow, Need to check privilege every access.

Current Linux

  • Hybrid mechanism
    • When Open we pass the file path: ACL.
    • Following RW we use fd: use fd as capability.
  • Different file open the same file but get different fd.

Welcome to my other publishing channels