Greg:
You have partly defined away the problem by mis-stating two
assumptions.
> o The term "gains access" means to be able to invoke methods against
Your solution relies on the behavior of the objects W, X, Y. You
assume, in particular, that W, X, Y will correctly filter invocations
made to them on the basis of the caller. If they are implemented
correctly, they may indeed do so. Unfortunately, the operating system
is unable to prove that they are implemented correctly. Your security
enforcement therefore falls outside of the system security model, and
a system that provides enforcable security policies therefore cannot
permit what you propose.
> the object upon which access is granted without receiving a permission
> exception. All private data is assumed encapsulated and accessible
> only through methods.
>
> o An unsuccessful invocation is designated by throwing an exception
> from W or Y: NoPermissionException. Similarly for Zi.
This is a fixable problem -- you simply have to build enforcement into the VM rather than into the object and the general flavor of mechanism you propose will work fine.
For your reference, here is a better metric of accessability:
> Remarks
>
> i. The main problem I faced was one establishing the identity
> of the caller of foobar(). Once foobar() knew the identity of
> the caller, it was easy to check the ACL.
Close, but imprecisely stated. The main problem is to establish the *authority* of the caller, which cannot be determined solely based on the user identity -- I'll point out the problem below.
> ii. I don't know the exact definition of "the pure ACL model",
> but I assumed that Java security manager tricks that perform
> scanning of the call stack are NOT allowed.
Correct. The ACL model says that an object has a set of (user id, authorized actions) pairs attached to it [to the object]. Given a user identity and a requested action, the list yields a yes/no answer as to whether the action is permitted. That's it.
> PART 1: Establishing the identity of the caller
>
> 1. Define a Process class. Each instance has a unique ID. The
> IDs are monotonically increasing. There is a static attribute
> 'nextId' that maintains the value for the next ID to be assigned.
>
> 3. There is a method against a Process called getId() that returns
> values of the form "ProcessN" There is a static Process method
> getProcessId() that returns the value Thread.currentThread().getName()
You must assume this method is unforgeable, which means that it cannot be overridden. Move the per-process ID to be a VM-accessible field and all will be well.
> PART 2: Solving the Challenge
>
> 1. Each non-Process object W, X, Y, Zi has an ACL. The ACL is a
> set of id's. The presence of an id in the ACL designates permission
> to invoke the foobar() method. The code for foobar is below in #2.
I did not say that objects W, X, Y, Zi were non-process objects. They should not be assumed to be so. Nothing in the VM-implemented variant of your notion presents a real problem there, however.
> 2. Each non-Process object W, X, Y, Zi has an owner as specified
> to its constructor. Only the owner may change the object's ACL.
Fine.
> 3. An instance of A creates a B and an instance of WXYclass
> and makes it accessible to B as follows....
Observation: The minute you started relying on Java pointers to name the objects you had actually moved to capabilities (the java pointers themselves). No further protection mechanism was necessary.
I failed to state something important in the problem, which is that the solution must work recursively. That is, it must be possible for B to in turn create helper tasks C (and so forth recursively) authorized to operate on W, X, Y, Zi on behalf of B. The existence of these helper tasks is none of A's business, and the solution must not rely on informing A about them.
When you try to implement this, you will discover that the rule "only the owner can update the ACL" will prevent delegation, and you will be forced to make "update the ACL" an "action" on the object itself.
You will then find that proving the restrictions on the Zi's becomes impossible. The problem is that anyone with access to Zi but without access to B can come along and add B to the access list for Zi, at which point B has access to Zi and the restriction has been violated.
> >Challenge 2: Design an *efficient* primitive mechanism to implement
> > the key element(s) of your solution.
>
> 1. User identity is bound to the process/thread executing code
> on behalf of a user.
This is where you lose. The problem requires per-process permissions, not per-user permissions. The fundamental problem of efficiency is that every process creation for a new process Pn requires that Pn be added to the access lists of a large number of objects Zi. The access list updates becomes prohibitive. Then there is the problem of when to reclaim entries for processes that no longer exist.
Further, every new object creation must be handed the set of initially authorized processes. This assumes that all processes can see and know about all others, which is clearly unacceptable.
The first "fix" is to introduce a mechanism to say "Pn is like Px, but for the following restrictions." This is almost impossible to get right, and has nearly the same overhead as the first solution in some important cases.
Beyond that, there appear to be no elegant solutions.
> >Challenge 1 cannot be solved in the pure ACL model, but *can* be
> >solved with relatively minor surgery to the ACL model.
The required surgery was to make the change to allow "update the access list" to be an operation.
shap