[E-Lang] A result on the containment problem.

[Vijay Saraswat]

I suspect the following paper (appeared in the Symposium on Theory of
Computing 2000 (STOC 2000)) may be of interest to folks on this list.

This work was done in connection with a scheme for capability-based
communication I had designed in Java as part of the Matrix work while I
was at AT&T Research. Matrix was, essentially, a failed attempt to do
distributed MOOs in Java. (Some of the security researchers at AT&T
Research were instrumental in hooking us up with the work on the
Take-Grant model alluded to in the paper.)

The central problem we were trying to solve was to ensure some simple
*intra*-JVM properties (think: single MOO), in the presence of the
possibility that multiple, mutually hostile programmers could upload
code to the JVM. For instance, assume Alice, Bob and Charlie are three
Matrix users who can upload code to a given Matrix world. We wanted it
to be possible for Alice and Bob to communicate with each other in a
room who's code was written by Charlie, without granting Charlie the
ability to read the message. (Note: No attention is being paid to
solving such problems across JVMs.)

The simple implementation idea was to take advantage of some basic
properties of the Java language:
(1) type-safety, including strict object encapsulation
(2) non-forgeability of references to objects
(3) final members
to design a simple capability system. (In fact we implemented a
public/private key system, using object references.) The code for the
capability system was just a few dozens of lines long .. code that would
be fairly obvious to most of the people on this list.

Then, of course!, the problem arose about reasoning about this code.
Hence this paper.

Earlier, a grad student, Oleg Cheiner had worked with me to formalize a
model for reasoning about the problem (defining can-access and can-steal
predicates in the Object Accessibility Model).

The decidability of these predicates was settled in the paper with
Rajeev, Suresh and Rina.

References:
http://www.saraswat.org/matrix/summer.pdf
http://www.saraswat.org/matrix/stoc2000.pdf

Enjoy!

Best,
Vijay

(Still working on that website!)