[cap-talk] Memory Accounting without partitions (was: Language-based OS domain separation.)

[Sandro Magi]

Jonathan S. Shapiro wrote:
>   2. Resource separation. The .NET stuff *finally* got it that
>      different apps needed different heaps, but they haven't
>      got a clean solution for cross-domain interactions when
>      pointers are not permitted to cross heap boundaries. This
>      is the point that Singularity *may* have gotten right.

I just came across this paper from the PLT Scheme folks which addresses
the above without separate heaps:

Memory Accounting Without Partitions

http://www.cs.utah.edu/plt/publications/ismm04-wf.pdf

Their technique relies on a slightly augmented garbage collector, where
ownership is assigned and accounting performed during GC trace. They
determine an ownership policy for objects by grouping executing programs
under hierarchical "Custodians" (similar to a process), and applying an
ordering to roots: if objects in custodians A and B share x, and A is
hierarchically under B, then A is charged for x.

Their approach is good from a developer-friendliness standpoint, but I'm
wary of one of their ownership policies: if A and B are unrelated
hierarchically, ownership is assigned randomly to A or B. This seems
like it could be problematic for asymmetric trust relationships, such as
a widely shared, trusted service, which must protect itself from
malicious clients. This is only relevant for services which share some
long-lived state with a client, such as a buffer between a window system
and a malicious application.

One solution: all clients of a shared service must be run as child
custodians of the service, so memory is booked to the client directly
instead of randomly assigned to the service. However, this may make
programs that use multiple shared services difficult to express and
coordinate. You would have to create multiple child custodians for the
different parts of the program, with any shared objects assigned
randomly between them. I'd have to think about it more to see if this is
still reasonable.

With a minor extension to the paper, hierarchically unrelated objects
can share an object via a TrustedRef which must be explicitly introduced
by one of the parties and books the memory to that party. The ref would
be a strong ref for the creator, and a weak ref for the recipient, and
the recipient would simply need to check that the ref hasn't been
collected before using it. The trusted service would accept the weak end
of a TrustedRef, ensure that it's live, then use it (guarding against
TOCTTOU bugs of course). TrustedRef performs a similar function to the
trusted buffer under EROS. Using TrustedRef might also solve some of the
untrusted library problems alluded to in the paper.

I'm still digesting the paper, so perhaps there's a simpler solution. At
least there's some work being done on the last vulnerabilities that cap
languages don't currently handle: DoS against memory.

Sandro