Review and Revocation for Capabilities

Lecturer: Professor Fred B. Schneider

Lecture notes by Lynette I. Millett

We have been discussing access control mechanisms; most recently: capabilities. We are interested in using access control mechanisms for authorization (with small protection domains). We are also interested in using them for audit purposes--determining who has access to what at any particular moment. The technical term for this is review. Further, we need to be able to revoke access. Today we will discuss review and revocation for capability-based mechanisms.

Review

Recall that, in general, the review problem is undecidable (See lecture 6). However, specific instances of the problem are easier to solve. We can think in terms of the current state of the system: Who can access what now? If we were using access control lists we would answer by just printing the lists. With that mechanism, information is organized in a useful way for review.

To perform review in a capability-based system is more difficult. All of the capabilities could be printed, but from that information it would still be hard to determine which subjects have access to a particular object. Looking through every subject's capability list could take a long time. When capabilities are stored in user space (which is desirable, to avoid kernel operations) then these lists can be spread throughout the system, and therefore difficult to find. Unforgeable tickets solved many security problems, but review is not one of them.

Revocation

Why should revocation be necessary? The client/server relationship can be thought of as a contract. A breach of contract might change the degree of trust between the two. For example, if it becomes known that a particular program has many bugs, then it would be prudent to limit its access rights. We have also already seen examples where access rights are granted at a particular point, and then revoked. This is referred to as temporary sharing.

If we are using access control lists, then revocation is accomplished by simply removing a subject's name from the list of subjects that access the object.

The situation is more complicated if we are using capabilities for access control. In principle, a subject would find the capability to revoke and invalidate (overwrite) it. This may require accessing memory that the subject does not have access to. Another solution would have the kernel track all capabilities and invalidate them when necessary from its database. Yet another is to let the individual objects themselves manage revocation lists. A drawback to this approach is that now the object designer/application programmer must take responsibility for including this functionality in each object. A final solution is to stipulate that capabilities time-out (become invalid) after a certain amount of time. However, determining an appropriate expiration data is problematic.

If subject A gives a capability to subject B, and B subsequently gives that capability to D, we need a way to revoke B's access without also revoking D's. Think of capabilities as keys and objects as having locks. If the owner changes the lock, then in the above example both B and D lose access. When A revokes access to B, does it also intend to revoke access to anyone B may have given the capability to?

We present two classes of solutions to the above problem.

Capability Revocation by Indirection

In indirect addressing, a register may contain the address of a word. If that word's high-order bit (i.e. tag) is 1, then it too is treated as an address. This process of following pointers continues until reaching a word whose high-order bit is 0, which is treated as data. The number of levels of indirection is not constrained in this scheme.

Capabilities can be thought of as addresses. We can now have capabilities that point to capabilities.

How can revocation be accomplished in such a situation? Here, altering any point in the chain will cause any attempt to access through the initial capability to fail.

Suppose that a subject A owns some object and would like to give B revocable access. We do this by postulating a new type of capability called an alias. For A to give a revocable access right to B: A creates an alias for the object. It then gives a capability allowing access through the alias to B. It can revoke access for B by invalidating the alias. B cannot get to the object without going through the alias first. This can become more complicated. Suppose that A would like to give C access as well. It can be done in one of two ways: C can have access through the same alias as B, or A can create another alias which C has access to. In the former case, revoking access to B also revokes access to C. Further, suppose that B would like to give revocable access to D to the object that A owns. B can create an alias that has access to the original alias given to it by A. B provides D with a capability to the alias it created. Thus, if A revokes B's access, D's access is also revoked. If A wants D to have its own access, it needs to create a separate alias for it.

Review, in this case, becomes extremely complicated; all of these capability chains need to be followed to determine what subjects have access to what.

Capability Revocation with Conditional Capabilities

Another approach to capability revocation is to use state information. Each capability, along with the object name and rights, will also contain some state information referred to as a "little bag." Associated with each object is state information call a "big bag." A capability's access to an object succeeds only when something in the capability's little bag is also in the object's big bag. For example, consider the following scenario:
To revoke access to B, A can remove "b" from the big bag. For each alias created in the previous discussion, there would be a distinct element in the "big bag." Suppose that B would like to give revocable access to another subject. B cannot add anything to the objects "big bag," (because B does not own the object) so this mechanism is not as simple to use as when B could create its own alias. In fact, it is not possible to allow this transitive granting of revocable access unless some kind of indirection is added to the framework. Or, B could create an object that calls A's object, but now the cost of a call increases. This new object that B creates is usually referred to as a wrapper or veneer.

We have shown two mechanisms for capability revocation. Both are complicated, but they seem to provide the best solution. The whole question of revocation is a big problem currently. In fact, Java, for example, has capabilities but currently no nice way to handle revocation.