Sebery J.Cryptography.An introduction to computer security.1989

Table 17.1. An access matrix

{succeeds, sL reads a covert bit 1 (the object is not locked),

{fails, the covert bit is 0 (the object has been locked by sH).

In general, the elimination of covert channels is expensive. In addition, the progress in hardware causes that covert channels become faster.

17.2 Discretionary Access Control

Discretionary access control assumes that the owner of an object controls access permissions to it. It is in the owner discretion to assign access permissions to objects. Most of access control models use a matrix to describe the current protection state.

17.2.1 Access Matrix Model

Lampson [298] introduced the access matrix model for DAC. The model was extended by Graham and Denning [220]. The core of this model is a matrix whose rows are indexed by subjects S and columns by objects O. A single matrix entry (s; o) contains all access permissions held by the subject s to the object o. Usually, the collection of objects contains all subjects or O S. The access matrix describes the current protection state de ned by the pattern of permissions in the matrix entries. An example of an access matrix is given in Table 17.1. For instance, s1 is permitted to read the object o4. The subject s3 can execute the object o2 which is, in fact, the subject s2.

Since the contents of the access matrix re ect the current state of protection privileges in a computer system, it must be changed whenever a new privilege has been granted to a speci c subject or an existing one has been removed from a speci c matrix entry. To modify protection state, Graham and Denning [220] identi es the following collection of protection commands:

572 17 ACCESS CONTROL

{Create object() { create an object (or a subject). Note that O S.

{Delete object() { delete an object (or a subject).

{Grant permission( ; si; oj) { grant the permission to the subject si for object oj.

{Delete permission( ; si; oj) { delete the permission to object oj held by the subject si.

{Transfer permission( ; oj ; si) { for the speci ed object oj, the command allows one subject to transfer permission to another subject si.

{Read() { display the contents of selected entries of the access matrix.

Create object() can be called by any subject sj to create either an object or a subject. The creator sj becomes the owner of the object onew (subject snew) and has exclusive rights to control the distribution of permissions to that object (subject). In e ect, a new column onew is added to the matrix with the owner in the entry (sj; onew) if the object is passive. If, however, the new object is active, a new column onew = snew and a new row snew is added to the matrix. The entry (sj; onew) contains the owner permission and the entry (snew; onew), which is the control permission.

Delete object() is reverse to Create object(). The command can be invoked by the owner of the object oj (subject) only and it causes that the object oj ceases to exist. This implies that the corresponding column (in the case of passive object) or both the corresponding column and row (in the case of active object) are removed from the matrix.

Grant permission( ; si; oj) can be executed by the owner of the object oj and it grants the permission to the subject si. Granted permissions must be di erent from the owner permission.

Delete permission( ; si; oj) may be executed in two situations. The owner of the object oj can delete any permission from any entry of the access matrix column oj . A subject sk which controls si (the entry (sk; sj) contains the control permission) can remove any permission from any entry of the row sj.

Transfer permission( ; oj ; si) involves two subjects sk which intends to transfer the permission and executes the command and si which is a grantee to whom the permission is to be assigned. The command is executed only if the subject sk has a copy ag associated with the permission (denoted by ). In other words, if a matrix entry (sk; oj ) contains , the subject sk may transfer the permission to si.

Read() allows a subject to read current entries of the access matrix. Needless to say, any choice of permissions and protection commands is to

some extend arbitrary. There is a natural tradeo between protection and openness of computer resources. If we accept a very limited set of protection commands with a small number of possible permissions, we will presumably get better protection but sharing computer objects will be very restricted. Consider the case with a large number of protection commands and permissions. The rst problem with such protection system would be the design of an eÆcient algorithm for security veri cation. Even if it is possible to prove the correctness of our protection system, the complexity of its implementation grows with the number of components (protection commands). On the other hand, if the collection of protection commands allows to create and destroy objects only, then we get a protection mechanism which provides complete isolation among subjects. The mechanism is extremely in exible, but it is secure.

Protection commands directly in uence the way subjects may share their resources. There are three main levels of sharing:

1.no sharing (complete isolation)

2.sharing data objects

3.sharing untrusted subjects

The rst and second level can be implemented using the access matrix model presented above. The third level of resource sharing requires new protection commands. Consider the following scenario. Given three subjects s0, s1 and s2. The subject s0 owns the subject s2 and the subject s2 uses an object o according the some permission . For some reasons, the subject s0 needs to share with s1 the object accessible to s2. Although s1 and s0 may trust each other, s1 may not trust s2. This problem was formulated by Graham and Denning [220] and can be solved by introduction of a new indirect access permission. The permission indirect is de ned as follows:

{Given three subjects: the subject s2, its owner s0, and the acquirer s1.

{The indirect access to s2 can be granted to the acquirer s1 by the owner s0 only.

{The acquirer s1 can access all objects which are accessible to s2 in the same way as the subject s2 (in other words, s1 holds the same collection of permissions as the subject s2).

{An indirect permission can be revoked by the owner s0 at any time.

574 17 ACCESS CONTROL

In general, the more exible access control the more protection commands have to be de ned. Unfortunately, some access control problems cannot be solved using the access matrix model. For example,

1.If a permission is transferred from one subject to another, then the second subject can propagate the permission with no agreement of the rst one.

2.The read permission allows a reader to copy the object and to grant friend subjects the read access to the copy.

3.If two or more untrustworthy processes conspire, they may exercise their permissions collectively.

17.2.2 Harrison-Ruzzo-Ullman Model

The access control model de ned by Harrison, Ruzzo, and Ullman in [234] deals with the set of subjects S, the set of objects O and the set of generic rights P which de ne access permissions held by a subject s 2 S to an object o 2 O. M is an access matrix with rows and columns labeled by subjects and objects, respectively. An entry M(s; o) is a subset of P and de nes access right of s 2 S to o 2 O.

There are six primitive operations opi which are used to modify the sets S and O together with the entries of the matrix M. They are:

{ enter r into M(s; o) { put an access right r into the entry (s; o) of the matrix M .

{ delete r from M (s; o) { remove an access right r from M (s; o).

{create subject s { create a new subject and append a new row and column to the matrix M labeled by subject s with empty entries.

{create object o { create a new object and append a new column to the matrix M labeled by subject o.

{destroy subject s { destroy the subject s and remove the corresponding row and column from M.

{destroy object o { destroy the object o and remove the corresponding column from M .

Obviously, subjects do not have direct access to the primitive operations. Instead, they can be invoked indirectly via the so-called protection commands. The generic form of a protection command is:

command c(X)

if r1 in M(s1; o1) and r2 in M(s2; o2) and

.

.

.

rm in M (sm; om) then

op1; op2;

.

.

.

opn;

end

where X is a collection of formal parameters and ri 2 P for i = 1; : : : ; m.

A con guration of a protection system is a triple (S; O; M ) where the sets S and O are current subjects and objects, respectively, together with the current access matrix M.

The UNIX access control mechanism allows to manipulate les by providing protection commands equivalent to the following ones.

command create file(s; f) create file f;

enter own into M(s; f); end

The command create file rst creates a le and adds a single column in the matrix M labeled by f and puts the right own into M(s; f). The owner s of an object o can grant the read r access right to a friendly subject s0 by invoking:

command grant read(s; o; s0) if own in M (s; o)

then

enter r in M(s0; o); end

The owner s of an object o can withdraw the access right r from a subject s0 by invoking:

command delete read(s; o; s0)

576 17 ACCESS CONTROL

if own in M (s; o) and r in M(s0; o)

then

delete r from M(s0; o);

end

Given an initial con guration Q0 = (S; O; M ) of the protection system and a collection of protection commands C = fc1; : : : ; cug, the protection state will change after application of a protection command c 2 C. The evolution of protection states can be captured by the sequence of con gurations resulting by execution of protection commands (c1; c2; : : :), i.e.

Q0 `c1 Q1 `c2 Q2 : : :

We say that a protection system leaks access right r from a con guration Q if a command c 2 C leads to a con guration Q0 such that the access matrix contains r in some entry (or r 2 M(s; o)), which previously did not contain it (or r 2= M(s; o)).

A protection system is safe in respect to r if there is no con guration Q which leaks r. This leads us to the following decision problem [192].

Name: Safety of le protection systems problem.

Instance: Given a protection system with set of subject S, set of objects O, set of access rights P and collection of protection command c 2 C.

Question: Is there any sequence of commands from C and an access right r 2 P such that the system leaks r?

It turns out [234], this problem is undecidable or in other words, there is no algorithm which could be used to solve it. Typically, undecidability appears whenever the problem in hand has too many free variables and parameters. If we restrict the form of commands so they consists of no more than a single primitive operation, then the safety problem becomes NP-complete. If additional restrictions are imposed, then the resulting problem may be solvable in polynomial time.

17.3 Role Based Access Control Model

An alternative to the MAC and DAC access control models is the role based access control (RBAC) model. The RBAC model streamlines the access control

by rst de ning roles which are given access permissions to objects and later assigning roles to subjects. In most organizations and institutions, the access permissions do not depend on who the persons are but rather where their positions are in the management hierarchy. Normally, the position uniquely identi es a collection of jobs which is associated with it. RBAC allows for a nice packaging of access control permissions necessary to perform speci c roles. Roles are treated as subjects whose identity is unde ned until speci c persons assume them.

The RBAC model allows to de ne relations among roles and users. As argued in [450], two roles may be mutually exclusive so they cannot be assumed at the same time by a single user. Roles may exhibit a hierarchical structure in which a higher level role inherits permissions of lower level roles. RBAC directly supports the following security policy principles [450]:

{Minimum privilege { a job de nes a collection of objects (resources) and access rights which are necessary to perform duties associated with the job.

{Separation of duties { if the collaboration of two users is required to complete a job, it is possible to enforce this by de ning two mutually exclusive roles for the job.

{Data abstraction { low-level access rights (such as read, write, delete, etc.) can be encapsulated into high-level access rights (such as send invoice and receive invoice).

Sandhu, Coyne, Feinstein, and Youman in [450] presented a general RBAC model with role hierarchy and constraints. Given the set of users U, the set of access permissions P, the set of roles R and the set of sessions S. A user u 2 U is identi ed with a person. A role r 2 R is a well de ned job function which describes the duty and authority imposed on the person who takes on the role. A session s 2 S is an assignment of di erent roles to a given user. Users can start up a session during which they assume one or more roles they belong to. A session is always associated with a single user who has started it up. The same user can run many sessions concurrently. The notion of session is equivalent to the notion of subject in the DAC model. A user simply accesses a subset of all roles he or she belongs to. The RBAC model uses the two following relations:

1.Permission-to-role { assignment P A P R and

2.User-to-role { assignment UA U R.

578 17 ACCESS CONTROL

There are two functions:

1. user: S ! U { each session s is assigned to a single user user(s).

2. roles: S ! 2R { each session s is assigned to a subset of roles, i.e. roles(s) f(rjuser(s); r) 2 UAg. In e ect, the session s has the permis- sions Sr2roles(s)fpj(p; r) 2 P Ag.

The basic RBAC model includes the above de ned components (U; R; P; P A; UA; user(); roles()). Consider the set of roles R. If the roles are partially ordered, i.e. there is a

relation RH R R with the role hierarchy imposed by , then the role() functions can be more conveniently de ned knowing that if a user belongs to a role r, then he or she must belong to all roles r0 which are dominated by r or r r0. Constraints can be imposed on the assignments P A and UA and on the roles and user functions. For more details refer to [450].

17.4 Implementations of Access Control

Now we are going to consider implementation of access control. The starting point is always a security policy which needs to be enforced by a properly designed access control mechanism. Depending on the environment in which the mechanism is to be incorporated, the designer considers which of the known access control mechanisms could be adopted as the base for implementation. Let us review some of implementations. For alternative discussions on the subjects refer to [215, 219, 470].

17.4.1 Security Kernel

This implementation is based on the so-called reference monitor concept [298]. The reference monitor is an abstract system that

1.mediates all access requests,

2.functions correctly, and is tamperproof.

Any access request must go through the reference monitor which grants or denies the access. There must be no way to bypass the monitor. The monitor must work correctly and the correctness must be veri able. It must also be tamperproof so it must be impossible to modify its functions by an unauthorized persons or processes. Note that the reference monitor concept is policy neutral { it can implement any access control policy (MAC, DAC, RBAC).

It is no surprise to learn that most access control mechanisms based on the reference monitor concept are incorporated as an integral part of operating system kernel [219]. This part is called security kernel. The Orange Book [145] de nes the Trusted Computing Base (TCB) which includes all protection mechanisms (including the security kernel) which enforce security policy (including access control policy).

To protect the operating system from untrusted processes, the computer system must have at least two distinct modes of operations:

{user mode and

{monitor mode.

All components of OS are run in the monitor (supervisor) mode. All user processes are executed in the user mode. To enforce two-mode operation, the underlying hardware must have an additional bit called bit mode which indicates the current mode { 0 for monitor mode and 1 for user mode. The Intel 80386/486 microprocessors support four modes of operation (protection rings) with two mode bits.

{The kernel is assigned the mode 0.

{The remainder of the operating system { mode 1.

{I/O routines { mode 2.

{User processes { mode 3.

Clearly, the most privileged mode is 0 and the least { mode 3.

Modes of operation alternate from monitor to user and from user to monitor. The switch from monitor to user mode is safe as long as the kernel works correctly. The switch from user to monitor mode must be controlled. To facilitate this, users (or more precisely their processes) are allowed to switch to monitor mode indirectly invoking privileged instructions. Privileged instructions can only be run in monitor mode. When a user invokes a privileged instruction, the hardware does not execute it but generates a trap to the operating system. The operating system starts running from the address given in the trap vector. The address determines the place where the corresponding trap service routine is.

Assume for a while that a user is able to modify the contents of the trap vector. In this case, a user process may replace the address of the trap service routine by an address from the user program space. When the trap occurs, then the hardware switches to the monitor mode and transfers control to the user process. In e ect, the user process is run in the privileged mode [470].

580 17 ACCESS CONTROL

As a matter of principle, the operating system never allows user processes for direct access to I/O routines. It also means that all I/O routines are part of the operating system and are run in monitor mode. Whenever a user process needs to print, it issues a privileged I/O instruction which traps to the operating system or more precisely to the proper I/O routine.

As the CPU executes a user process, all the CPU references to main memory must be checked whether they are within the address space of the program in execution. Any attempt to access instructions of other processes should result in an error and trap to the operating system. To implement memory protection, a hardware support is again required. The hardware consists of two registers and additional comparison gates. One register stores the base (the memory address where the currently executed program starts). This is the base register. The other also called the limit register indicates the size of the range. Both registers uniquely identify the (legal) address space of the process.

Assume that the CPU is running a process whose code resides in the memory [a; A] where a is the smallest address and A is the largest address of the process. The current contents of the base register is a and the limit register contains A a. When the CPU tries to access a memory address x, then the hardware

{First checks whether x a. If so, go to the next step. Otherwise, it traps to the operating system.

{Next compares whether x A. If the check holds, the reference is valid. Otherwise, a trap to the operating system is generated by the hardware.

Needless to say that the kernel only can load to the base and limit registers. The most precious resource in computer systems is the CPU. Once the con-

trol over the CPU is passed to a user process, there is no way to take it back until the process either voluntarily releases it or has generated an interrupt. This may never happen if, for example, the process has entered an in nite loop. To prevent the CPU from being taken over by a single process, a piece of hardware called timer is necessary. The timer can be accessed by the operating system only. Before a user process gets control over the CPU, the timer is initialized to the amount of time for which the process will be allowed to run. Every clock cycle decreases the contents of the timer until eventually the contents becomes zero. This causes an interrupt and switch to monitor mode.