Access matrix model, Capability list, Access control list

by Lin Gong

This page is under construction.

Concept of Protection

Security and Protection deal with the control of unauthorized use and the access to resources of a computer system. Protection refers to mechanism while security refers to policy.

Protection system consists of mechanisms to control user access to system hardware and software resources or to control information flow in the system.

Protection domain of a process specifies the resources that it can access and the types of operations that the process can perform on the resources. This limits a process's access to only needed resources.

Access matrix model

The most fundamental model of protection is the access matrix model. This model was first proposed by Lampson and further enhanced and refined by Graham and Denning, and Harrison et al.

Components in access matrix model:

Current objects (O): a finite set of entities to which access is to be controlled;

Current Subjects (S): a finite set of entites that access current objects, subjects can be accessed like objects by other subjects, hence the set of subjects can be regarded as contained in the set of objects;

Generic rights (R): a finite set of various access rights that subjects can have to objects, R = {r1, r2, ..., rm}, where r1, r2... can be read, write, delete or other rights.

Representation

The protection state of a system is represented by a triplet (S,O,P), where S is the set of current subjects, O is the set of current objects, and P is the access matrix with a row for every current subject and a column for every current object. Each entry P[s,o] is a subset of generic rights R denoting the access right that subject s has to object o.

For the graphs about the access matrix, please see Dr. Kafura's notes under the same home page.

Enforcing security policy

Each object has a monitor to validate every user access to that object in the following manner to check for appropriate access rights:

A subject s requests an access a to object o.
The protection system presents triplet (s, a, o) to the monitor of o.
The monitor looks into the access rights of s to o. if a is in the entry P[s,o], then the access is permitted; else it is denied.

Advantages

The access matrix model is very popular because of its simplicity, elegant structure, and amenability to various implementations.

Implementation Consideration

The access matrix is likely to be very sparse, hence any direct implementation of the access matrix for access control is likely to be very storage inefficient. The efficiency can be improved by decomposing the access matrix into rows (colunms) and assigning the access rights contained in rows (columns) to their respective subjects (objects). The corresponding approach is called the capability-based method (access control list method).

Capability-based method

The capability based method corresponds to the row-wise decomposition of the access matrix. Each subject s is assigned a list of tuples (o,P[s,o]), called capabilities, for all objects o that it is allowed to access. The list of capabilities assigned to subject s corresponds to access rights contained in the row for subject s in the access matrix.

A capability has two fields: object descriptor (identifier for the object) and access rights (indicating the allowed acess rights to the object).

         Object descriptor                  Access rights
   ------------------------------------------------------------------
  |         identifier         |       read, write, execute, etc     |
   ------------------------------------------------------------------

Aside from providing protection, capabilities can also be used as an addressing mechanism by the system. It provides an address that is context independent, but the system must allow embedding of capabilities in user programs and data structures. Capability-based addressing has two salient features: relocatability and sharing.

Advantages

efficiency: validity of an access can be easily tested
simplicity: natural correspondence
flexibility: allow users to define certain parameters

Drawback

control of propagation
review of access is difficult
revocation of access rights is difficult
garbage collection problem

Access control list method

The access control list method corresponds to the column-wise decomposition of the access matrix. Each object o is assigned a list of pairs (s,P[s,o]) for all subjects s that are allowed to access the object. The access list assigned to object o corresponds to all access rights contained in the column for object o in the access matrix.

When a subject requests access to an object, the system searches the access control list of the object to find out if an entry exists for that subject. If such an entry exists, the system checks whether the required access is permitted; if so, the request is executed, otherwise an oppropriate exception is raised.

Advantages

Easy revocation: simply remove the subject's entry from the object's control list
Easy review of access: directly examine the access control list of the object
Providing two ways to control propagation of access rights: self control and hierarchical control

Drawback

Poor execution efficiency, since the access control list need be searched for every access to a protected object
-- Solution: shadow register
Can require huge amounts of storage (in access control list, the total is taken across objects; while in capabilities, the total is taken across users.)
-- Solution: Protection group technique limits the number of entries in an access control list by lumping users into groups hence reduces the overheads of storing (and searching) lengthy access control lists.

References

Singhal,M. and Shivaratri,N.: Advanced Concepts in Operating Systems, McGraw-Hill, 1994.

Peterson,J.L. and Silberschatz,A.: Operating System Concepts, 2nd ed, Addison Wesley, 1985.

Maekawa,M., Oldehoeft,A., and Oldehoeft,R.: Operating Systems Advanced Concepts, The Benjamin/CUmmings Publishing Company Inc., 1989.

lgong@csgrad.cs.vt.edu