Lecture notes by Lynette I. Millett
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.
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.
Capabilities can be thought of as addresses. We can now have capabilities that point to capabilities.
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.
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.