[This came originally from gaf@objectguild.com]
Jonathan,
It was about two weeks ago that you sent me the the answers to the challenge problem. Sorry it took so long for me to reply, but thanks. The answers were very helpful. Of course, this only leads to more questions. I'll ask only one in this email.
"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 " - shap
"The basic idea is this: suppose we design a computer system so that in order to access an object, a program must have a special token. This token designates an object and gives the program the authority to perform a specific set of actions (such as reading or writing) on that object. Such a token is known as a capability." -shap essay
"Capabilities are protected names" - hardy http://www.mediacity.com/~norm/CapTheory/What.html
"Capability - A protected pointer or name, implemented with bits but
situated so that the holder and user lacks access to those bits.
Capabilities may be passed among programs but only by means
of protocols that specifically allow capabilities to be passed, as they
are not data. - hardy
http://www.mediacity.com/~norm/CapTheory/Glossary.html
-Greg
-----Original Message-----
From: Jonathan S. Shapiro <jsshapiro@earthlink.net>
To: gaf@objectGuild.com <gaf@objectGuild.com>
Cc: jsshapiro@earthlink.net <jsshapiro@earthlink.net>
Date: Sunday, March 22, 1998 4:07 PM
Subject: Re: Challenge Solution: Card Keys, capabilities, counters
>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
>> 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.
>
>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.
>
>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:
>
>1. If an object O is able to obtain a *name* an object X, then the
>object O has access to X. Posessing a string describing the location
>of X (e.g. a file name) is not sufficient -- in a UNIX system it is
>the file descriptors that are the names for our purposes. Posessing a
>pointer to X is sufficient to be able to name 'X'. Assume that if the
>object cannot be named it cannot be invoked.
>
>> 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
>