GRANDPRÉ: Description cannot suit itself in wordsTo demonstrate the life of such a battleIn life so lifeless as it shows itself. | ||
| --The Life of Henry the Fifth, IV, ii, 53–55. | ||
A protection system describes the conditions under which a system is secure. In this chapter, we present a classical formulation of a protection system. The access control matrix model arose both in operating systems research and in database research; it describes allowed accesses using a matrix.
The state of a system is the collection of the current values of all memory locations, all secondary storage, and all registers and other components of the system. The subset of this collection that deals with protection is the protection state of the system. An access control matrix is one tool that can describe the current protection state.
Consider the set of possible protection states P. Some subset Q of P consists of exactly those states in which the system is authorized to reside. So, whenever the system state is in Q, the system is secure. When the current state is in P – Q[1] , the system is not secure. Our interest in representing the state is to characterize those states in Q, and our interest in enforcing security is to ensure that the system state is always an element of Q. Characterizing the states in Q is the function of a security policy; preventing the system from entering a state in P – Q is the function of a security mechanism. Recall from Definition 1–3 that a mechanism that enforces this restriction is precise.
The access control matrix model is the most precise model used to describe a protection state. It characterizes the rights of each subject (active entity, such as a process) with respect to every other entity. The description of elements of A form a specification against which the current state can be compared. Specifications take many forms, and different specification languages have been created to describe the characteristics of allowable states.
As the system changes, the protection state changes. When a command changes the state of the system, a state transition occurs. Very often, constraints on the set of allowed states use these transitions inductively; a set of authorized states is defined, and then a set of operations is allowed on the elements of that set. The result of transforming an authorized state with an operation allowed in that state is an authorized state. By induction, the system will always be in an authorized state. Hence, both states and state transitions are often constrained.
In practice, any operation on a real system causes multiple state transitions; the reading, loading, altering, and execution of any datum or instruction causes a transition. We are concerned only with those state transitions that affect the protection state of the system, so only transitions that alter the actions a subject is authorized to take are relevant. For example, a program that changes a variable to 0 does not (usually) alter the protection state. However, if the variable altered is one that affects the privileges of a process, then the program does alter the protection state and needs to be accounted for in the set of transitions.
The simplest framework for describing a protection system is the access control matrix model, which describes the rights of users over files in a matrix. Butler Lampson first proposed this model in 1971 [608]; Graham and Denning [279, 413] refined it, and we will use their version.
The set of all protected entities (that is, entities that are relevant to the protection state of the system) is called the set of objects O. The set of subjects S is the set of active objects, such as processes and users. In the access control matrix model, the relationship between these entities is captured by a matrix A with rights drawn from a set of rights R in each entry a[s, o], where s ∊ S, o ∊ O, and a[s, o] ⊆ R. The subject s has the set of rights a[s, o] over the object o. The set of protection states of the system is represented by the triple (S, O, A). For example, Figure 2-1 shows the protection state of a system. Here, process 1 can read or write file 1 and can read file 2; process 2 can append to file 1 and read file 2. Process 1 can communicate with process 2 by writing to it, and process 2 can read from process 1. Each process owns itself and the file with the same number. Note that the processes themselves are treated as both subjects (rows) and objects (columns). This enables a process to be the target of operations as well as the operator.
Figure 2-1. An access control matrix. The system has two processes and two files. The set of rights is {read, write, execute, append, own}.
Interpretation of the meaning of these rights varies from system to system. Reading from, writing to, and appending to files is usually clear enough, but what does “reading from” a process mean? Depending on the instantiation of the model, it could mean that the reader accepts messages from the process being read, or it could mean that the reader simply looks at the state of the process being read (as a debugger does, for example). The meaning of the right may vary depending on the object involved. The point is that the access control matrix model is an abstract model of the protection state, and when one talks about the meaning of some particular access control matrix, one must always talk with respect to a particular implementation or system.
The own right is a distinguished right. In most systems, the creator of an object has special privileges: the ability to add and delete rights for other users (and for the owner). In the system shown in Figure 2-1, for example, process 1 could alter the contents of A[x, file 1], where x is any subject.
Although the “objects” involved in the access control matrix are normally thought of as files, devices, and processes, they could just as easily be messages sent between processes, or indeed systems themselves. Figure 2-2 shows an example access control matrix for three systems on a local area network (LAN). The rights correspond to various network protocols: own (the ability to add servers), ftp (the ability to access the system using the File Transfer Protocol, or FTP [815]), nfs (the ability to access file systems using the Network File System, or NFS, protocol [166, 981]), and mail (the ability to send and receive mail using the Simple Mail Transfer Protocol, or SMTP [814]). The subject telegraph is a personal computer with an ftp client but no servers, so neither of the other systems can access it, but it can ftp to them. The subject nob is configured to provide NFS service to a set of clients that does not include the host toadflax, and both systems will exchange mail with any host and allow any host to use ftp.
At the micro level, access control matrices can model programming language accesses; in this case, the objects are the variables and the subjects are the procedures (or modules). Consider a program in which events must be synchronized. A module provides functions for incrementing (inc_ctr) and decrementing (dec_ctr) a counter private to that module. The routine manager calls these functions. The access control matrix is shown in Figure 2-3 Note that “+” and “–” are the rights, representing the ability to add and subtract, respectively, and call is the ability to invoke a procedure. The routine manager can call itself; presumably, it is recursive.
In the examples above, entries in the access control matrix are rights. However, they could as easily have been functions that determined the set of rights at any particular state based on other data, such as a history of prior accesses, the time of day, the rights another subject has over the object, and so forth. A common form of such a function is a locking function used to enforce the Bernstein conditions,[2] so when a process is writing to a file, other processes cannot access the file; but once the writing is done, the processes can access the file once again.
Miller and Baldwin [715] use an access control matrix to control access to fields in a database. The values are determined by Boolean expressions. Their objects are records and fields; the subjects are users authorized to access the databases. Types of access are defined by the database and are called verbs; for example, the Structured Query Language (SQL) would have the verbs Insert and Update. Each rule, corresponding to a function, is associated with one or more verbs. Whenever a subject attempts to access an object using a right (verb) r, the Boolean expression (rule) associated with r is evaluated; if it is true, access is allowed, but if it is false, access is not allowed.
The Access Restriction Facility (ARF) program exemplifies this approach. It defines subjects as having attributes such as a name, a level, a role, membership in groups, and access to programs, but the user can assign any meaning desired to any attribute. For example:
name | role | groups | programs |
|---|---|---|---|
matt | programmer | sys, hack | compilers, editors |
holly | artist | user, creative | editors, paint, draw |
heidi | chef, gardener | acct, creative | editors, kitchen |
Verbs have a default rule, either “closed” (access denied unless explicitly granted; represented by the 0 rule) or “open” (access granted unless explicitly denied; represented by the 1 rule):
verb | default rule |
|---|---|
read | 1 |
write | 0 |
paint | 0 |
temp_ctl | 0 |
Associated with each object is a set of verbs, and each (object, verb) pair has an associated rule:
name | rules |
|---|---|
recipes | write: 'creative' in subject.group |
overpass | write: 'artist' in subject.role or 'gardener' in subject.role |
.shellrct | write: 'hack' in subject.group and time.hour < 4 and time.hour > 0 |
oven.dev | read: 0; temp_ctl: 'kitchen' in subject.programs and 'chef' in subject.role |
The system also provides primitives such as time (which corresponds to the current time of day), date (the current date), and temp (the current temperature). This generates the following access control matrix between midnight and 4 A.M.:
matt | holly | heidi | |
|---|---|---|---|
recipes | read | read, write | read, write |
overpass | read | read, write | read, write |
.shellrct | read, write | read | read |
oven.dev | temp_ctl |
At other times, the entry A[matt, .shellrct] contains only read. The read rights in the last row are omitted because, even though the default in general is to allow read access, the default rule for the object oven.dev is to deny read access:
matt | holly | heidi | |
|---|---|---|---|
recipes | read | read, write | read, write |
overpass | read | read, write | read, write |
.shellrct | read | read | read |
oven.dev | temp_ctl |
Statistical databases are designed to answer queries about groups of records yet not reveal information about any single specific record. Assume that the database contains N records. Users query the database about sets of records C; this set is the query set. The goal of attackers is to obtain a statistic for an individual record. The query-set-overlap control [304] is a prevention mechanism that answers queries only when the size of the intersection of the query set and each previous query set is smaller than some parameter r.
In practice, this control would not be used for several reasons, including the need to remember all prior queries. However, it affords an excellent example of an access control matrix whose entries depend on previous accesses to objects.
As processes execute operations, the state of the protection system changes. Let the initial state of the system be X0 = (S0, O0, A0). The set of state transitions is represented as a set of operations τ1, τ2, .... Successive states are represented as X1, X2, ..., where the notation λ |–, and the expression
means that state transition τi+1 moves the system from state Xi to state Xi+1. When a system starts at some state X and, after a series of state transitions, enters state Y, we can write
X |–* Y.
The representation of the protection system as an access control matrix must also be updated. In the model, sequences of state transitions are represented as single commands, or transformation procedures, that update the access control matrix. The commands state which entry in the matrix is to be changed, and how; hence, the commands require parameters. Formally, let ck be the kth command with formal parameters pk,1, ..., pk,m. Then the ith transition would be written as
Note the similarity in notation between the use of the command and the state transition operations. This is deliberate. For every command, there is a sequence of state transition operations that takes the initial state Xi to the resulting state Xi+1. Using the command notation allows us to shorten the description of the transformation as well as list the parameters (subjects, objects, and entries) that affect the transformation operations.
We now focus on the commands themselves. Following Harrison, Ruzzo, and Ullman [450], we define a set of primitive commands that alter the access control matrix. In the following list, the protection state is (S, O, A) before the execution of each command and (S', O', A') after each command. The preconditions state the conditions needed for the primitive command to be executed, and the postconditions state the results.
Precondition: s ∉ O
Primitive command: create subject s
Postconditions: S' = S ∪{ s }, O' = O ∪{ s }, (∀y ∊ O')[a'[s, y] = Ø], (∀x ∊ S')[a'[x, s] = Ø], (∀x ∊ S)(∀y ∊ O)[a'[x, y] = a[x, y]]
This primitive command creates a new subject s. Note that s must not exist as a subject or an object before this command is executed. This operation does not add any rights. It merely modifies the matrix.
Precondition: o ∉ O
Primitive command: create object o
Postconditions: S' = S, O' = O ∪{ o }, (∀x ∊ S')[a'[x, o] = Ø], (∀x ∊ S')(∀y ∊ O)[a'[x, y] = a[x, y]]
This primitive command creates a new object o. Note that o must not exist before this command is executed. Like create subject, this operation does not add any rights. It merely modifies the matrix.
Precondition: s ∊ S, o ∊ O
Primitive command: enter r into a[s, o]
Postconditions: S' = S, O' = O, a'[s, o] = a[s, o] ∪{ r }, (∀x ∊ S')(∀y ∊ O')[(x, y) ≠ (s, o) → a'[x, y] = a[x, y]]
This primitive command adds the right r to the cell a[s, o]. Note that a[s, o] may already contain the right, in which case the effect of this primitive depends on the instantiation of the model (it may add another copy of the right or may do nothing).
Precondition: s ∊ S, o ∊ O
Primitive command: delete r from a[s, o]
Postconditions: S' = S, O' = O, a'[s, o] = a[s, o] – { r }, (∀x ∊ S')(∀y ∊ O')[(x, y) ≠ (s, o) → a'[x, y] = a[x, y]]
This primitive command deletes the right r from the cell a[s, o]. Note that a[s, o] need not contain the right, in which case this operation has no effect.
Precondition: s ∊ S
Primitive command: destroy subject s
Postconditions: S' = S – { s }, O' = O – { s }, (∀y ∊ O')[a'[s, y] = Ø], (∀x ∊ S')[a'[x, s] = Ø], (∀x ∊ S')(∀y ∊ O')[a'[x, y] = a[x, y]]
This primitive command deletes the subject s. The column and row for s in A are deleted also.
Precondition: o ∊ O
Primitive command: destroy object o
Postconditions: S' = S, O' = O – { s }, (∀x ∊ S')[a'[x, o] =,Ø], (∀x ∊ S')(∀y ∊ O')[a'[x, y] = a[x, y]]
This primitive command deletes the object o. The column for o in A is deleted also.
These primitive operations can be combined into commands, during which multiple primitive operations may be executed.
The system can update the matrix only by using defined commands; it cannot use the primitive commands directly. Of course, a command may invoke only a single primitive; such a command is called mono-operational.
The execution of some primitives requires that specific preconditions be satisfied. For example, suppose a process p wishes to give another process q the right to read a file f. In some systems, p must own f. The abstract command would be
command grant•read•file•1(p,f,q) if own in a[p,f] then enter r into a[q,f];end
Any number of conditions may be placed together using and. For example, suppose a system has the distinguished right c. If a subject has the rights r and c over an object, it may give any other subject r rights over that object. Then
command grant•read•file•2(p,f,q) if r in a[p,f] and c in a[p,f] then enter r into a[q,f];end
Commands with one condition are called monoconditional. Commands with two conditions are called biconditional. The command grant•read•file•1 is monoconditional, and the command grant•read•file•2 is biconditional. Because both have one primitive command, both are mono-operational.
Note that all conditions are joined by and, and never by or. Because joining conditions with or is equivalent to two commands each with one of the conditions, the disjunction is unnecessary and thus is omitted. For example, suppose the right a enables one to grant the right r to another subject. To achieve the effect of a command equivalent to
if own in a[p,f] or a in a[p,f]then enter r into a[q,f];
define the following two commands:
command grant•write•file•1(p,f,q) if own in a[p,f] then enter r into a[q,f];endcommand grant•write•file•2(p,f,q) if a in a[p,f] then enter r into a[q,f];end
and then say
grant•write•file•1(p,f,q); grant•write•file•2(p,f,q);
Also, the negation of a condition is not permitted—that is, one cannot test for the absence of a right within a command by the condition
if r not in A[p,f]
This has some interesting consequences, which we will explore in the next chapter.
Two specific rights are worth discussing. The first augments existing rights and is called the copy flag; the second is the own right. Both of these rights are related to the principle of attenuation of privilege, which essentially says that a subject may not give away rights it does not possess.
The copy right (often called the grant right) allows the possessor to grant rights to another. By the principle of attenuation, only those rights the grantor possesses may be copied. Whether the copier must surrender the right, or can simply pass it on, is specific to the system being modeled. This right is often considered a flag attached to other rights; in this case, it is known as the copy flag.
The own right is a special right that enables possessors to add or delete privileges for themselves. It also allows the possessor to grant rights to others, although to whom they can be granted may be system- or implementation-dependent. The owner of an object is usually the subject that created the object or a subject to which the creator gave ownership.
If a subject does not possess a right over an object, it should not be able to give that right to another subject. For example, if Matt cannot read the file xyzzy, he should not be able to grant Holly the right to read that file. This is a consequence of the principle of attenuation of privilege [280].
Principle of Attenuation of Privilege. A subject may not give rights it does not possess to another.
On most systems, the owner of an object can give other subjects rights over the object whether the owner has those rights enabled or not. At first glance, this appears to violate the principle. In fact, on these systems, the owner can grant itself any right over the object owned. Then the owner can grant that right to another subject. Lastly, the owner can delete the right for itself. So, this apparent exception actually conforms to the principle.
The access control matrix is the primary abstraction mechanism in computer security. In its purest form, it can express any expressible security policy. In practice, it is not used directly because of space requirements; most systems have (at least) thousands of objects and could have thousands of subjects, and the storage requirements would simply be too much. However, its simplicity makes it ideal for theoretical analyses of security problems.
Transitions change the state of the system. Transitions are expressed in terms of commands. A command consists of a possible condition followed by one or more primitive operations. Conditions may involve ownership or the ability to copy a right. The principle of attenuation of privilege leads to the condition that no subject may give a right it does not possess to any other subject.
The access control matrix is very general. Are there other models, simpler to work with, but equally expressive? Chapter 3, “Foundational Results,” explores some of these issues, especially the application of the notion of types to expressive power. Similarly, examining the effects of different types of rules may affect the expressive power of the models.
Database security is an example of a simple application of the access control matrix model. The complexity arises because the elements of the matrix entries are generated by functions with very complex parameter lists. How can one conceal specific entries yet reveal meaningful statistics? How can one conceal some statistics yet reveal others? How can one detect attempts to subvert controls?
The access control matrix is sometimes called an authorization matrix in older literature [475].
In 1972, Conway, Maxwell, and Morgan [230], in parallel with Graham and Denning, proposed a protection method for databases equivalent to the access control model. Hartson and Hsiao [453] point out that databases in particular use functions as described above to control access to records and fields; for this reason, entries in the access control matrix for a database are called decision procedures or decision rules. These entries are very similar to the earlier formulary model [474], in which access procedures determine whether to grant access and, if so, provide a mapping to virtual addresses and any required encryption and decryption.
1: | Consider a computer system with three users: Alice, Bob, and Cyndy. Alice owns the file alicerc, and Bob and Cyndy can read it. Cyndy can read and write Bob's file bobrc, but Alice can only read it. Only Cyndy can read and write her file cyndyrc. Assume that the owner of each of these files can execute it.
|
2: | In Miller and Baldwin's model (see Section 2.2.1), they restricted the functions that generated the access control matrix entries to working on objects, not on subjects. Thus, one could not base rights being granted on whether another subject possessed those rights. Why did they impose this restriction? Can you think of cases in which this restriction would cause problems? |
3: | The query-set-overlap mechanism requires a history of all queries to the database. Discuss the feasibility of this control. In particular, how will the size of the history affect the response of the mechanism. |
4: | Consider the set of rights {read, write, execute, append, list, modify, own}.
|
5: | Let c be a copy flag and let a computer system have the same rights as in Exercise 4.
|
6: | This exercise asks you to consider the consequences of not applying the principle of attenuation of privilege to a computer system.
|
[1] The notation P – Q means all elements of set P not in set Q.
[2] The Bernstein conditions ensure that data is consistent. They state that any number of readers may access a datum simultaneously, but if a writer is accessing the datum, no other writers or any reader can access the datum until the current writing is complete [805].
[3] If S is a set, then its power set P(S) is the set of all subsets of S. That is, P(S) = {x | x ⊆ S}.