[prev in list] [next in list] [prev in thread] [next in thread]
List: cap-talk
Subject: Challenge Solution: Card Keys, capabilities, counters
From: Gregory Frascadore gaf () objectGuild ! com
Date: 1998-03-22 20:40:39
[Download RAW message or body]
Jonathan,
Here is my proposed solution to the challenges.
>
>Scenario 1:
>
>Consider two processes A and B. A is a client application, and B is a
>supporting component that A wishes to create and then use. If you
>like, imagine that B is something in the style of an ActiveX control.
>
>Imagine that A has authority to manipulate objects W, X, and Y (our
>sample user hasn't created many files yet). It wishes to grant to B
>the right to access X, but not W or Y. In addition, it wishes to
>ensure that B never gains access to subsequently created objects Z,
>Z', Z'', Z''' etc.
>
>
>Challenge 1: Describe a conceptually sound solution to this problem
> using only ACLs. [This] cannot be solved in the pure ACL model,
> but *can* be solved with relatively minor surgery to the ACL model.
Just to give myself some raw materials to work with, I'll make the following
assumptions.
o The environment is one similar to the Java virtual machine where
encapsulation really works and object references cannot be forged.
o The processes A and B will be representable as Java threads and
it is acceptable for A and B to implement the java Runnable interface
(i.e. the method A.run() is the "main program" for A)
o The phrase "A wishes to create and then use" is a) an essential part
of the problem b) there is no arbitrary upper limit on the number of Bs
that A may want to create c) that creation means to create an instance
from some Bclass.
o The objects W, X, and Y are of the same class (WXYclass) They have one
invocable method "foobar()" and the objective is that B can successfully
invoke X.foobar() but not W.foobar() or similarly for Y. Similarly for Zi.
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.
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.
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.
And now the proposed solution. This is described in two parts, the
first just deals with solving the "identity of the caller" problem within
Java. The second part is the proposed solution.
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.
2. An instance of Process encapsulates a Java Thread. Invoking
start() on a Process invokes start() on the underlying Thread. The
Process instance assigns the id of the encapsulated thread to
be "ProcessN" where N is the process ID.
(Side note: the only reason converting the id intro a string is that
Java thread ids are strings and I wanted the Process id to agree)
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()
4. The Process constructor takes a Runnable as an argument. The
instance of Runnable is the object executing in the new Process.
So now we can describe how A creates process B:
{
B b = new B();
Process p = new Process(b);
p.start();
...
}
Assuming p was the first Process instance, upon completion
of p.start() the above code has b executing within a process
with id == 1 and threadid == "Process1" and hence:
p.getId().equals("Process1");
Even better, any code executed in the Thread started by
p will find that:
Process.getProcessId().equals("Process1");
and this is how the problem of determining "who called me"
is going to be solved."
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.
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.
class WXYclass {
Hashtable acl = new Hashtable();
String owner;
public WXYclass(String owner) {
this.owner = owner;
}
public void addAccess(String id) {
if (!Process.getProcessId().equals(owner))
throw new NoPermissionException();
acl.put(id, id);
}
void foobar() {
if (!acl.containsKey(Process.getProcessId()))
throw new NoPermissionException();
}
}
3. An instance of A creates a B and an instance of WXYclass
and makes it accessible to B as follows.
class A implements Runnable {
// There is a global memory where instances of
// WXY will be "published" so that references to
// foobar() may be attempted.
public static Vector global = new Vector();
void run() {
// Create an instance of B and execute
// it within a new process
B b = new B();
Process bproc = new Process(b);
b.start();
// Create an instances and have them owned
// by the current instance of A, only the owner
// may change acl entries
WXYclass x = new WXYclass(Process.getProcessId());
global.addElement(x);
WXYclass y = new WXYclass(Process.getProcessId());
global.addElement(y);
// Add access for a and b (really the process executing these)
x.addAccess(Process.getProcessId());
x.addAccess(bproc.getId());
// According the the challenge description, only a has
// access to y
y.addAccess(Process.getProcessId());
At this point:
- any a, b, or future b could invoke foobar
against any member of global
- if a or b invokes x.foobar() they will succeed.
- if b invokes y.foobar() it will receive NoPermissionException.
- if a future bi invokes x or y.foobar() it will receive NoPermissionException
}
4. For completeness, an instance of A is started as follows:
class MainProgram {
public static void main(String args[]) {
A a = new A();
Process aproc = new Process(a);
aproc.start();
}
}
>Challenge 2: Design an *efficient* primitive mechanism to implement
> the key element(s) of your solution.
Although I didn't set out to work on Challenge 2, some mechanisms used
in the above code seem to be:
1. User identity is bound to the process/thread executing code
on behalf of a user.
2. In this case, the Java virtual machine enforces integrity of
identities and code that checks ACLs
3. ACLs are hashtables keyed by identity strings.
4. Protected objects have owners. At first, the owner is the
creator. Only the owner may modify the acl entries.
>
>Challenge 1 cannot be solved in the pure ACL model, but *can* be
>solved with relatively minor surgery to the ACL model.
>
>Challenge 2 appears to be intractable. Dynamic allocation of kernel
>data structures to solve the problem leads to kernel deadlock, and is
>therefore not acceptable.
Sorry this was so long.
-Greg
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic