[cap-talk] Horton vs. ACLs - storage management/accounting

[Jed Donnelley]

On 10/9/2007 5:42 AM, Jonathan S. Shapiro wrote:
> On Mon, 2007-10-08 at 12:48 -0700, Jed Donnelley wrote:
>> I now remember a bit about these resource exhaustion attacks
>> being mentioned before.  Perhaps I don't take such attacks
>> seriously enough....
> 
> I think that the membrane issue is not a resource exhaustion issue in
> the usual sense, but yes, I agree that you don't take such issues
> seriously enough. Let me put it more generally: I think that attempting
> to achieve storage accountability as exactly as possible is a desirable
> design goal. By "storage accountability", I mean that the storage is
> paid for by the party on whose behalf it is allocated. I think that a
> great many designs can achieve complete storage accountability, and I
> think that understanding which designs *cannot* achieve this is, at
> minimum, an excellent starting point for certain kinds of vulnerability
> assessments.

I believe the only design that I worked on in detail, the NLTSS system,
had the sort of storage accountability that you refer to above.  All
our storage ultimately came back to what we called "file"s.  All
files were 'owned' (paid for) by an account.  We even solved what is
generally referred to as the "lost object" problem in this way.
An account kept track of all the objects that it was paying for
and could regurgitate them if needed for management (e.g. to
recover a seemingly "lost" object that was still being paid
for and thus not destroyed).

> Generically, the place where storage accountability becomes difficult is
> sharing. One party pays, a second party uses. A problem arises when the
> first party desires to reclaim storage. There are a range of
> "sponsorship" and/or "futures" mechanisms for this, but all of the ones
> I know about introduce the problem that either (1) storage reclamation
> may not be "prompt" or (2) a calculus of computational progress in the
> presence of probabalistic memory is required [as of recent work, such a
> calculus may now exist, but it is not yet reflected in useful
> programming languages]. If promptness is lost, the cure is worse than
> the disease. There is nothing new in the problem I am describing here;
> it is well known.

Hmmm.  I'm not sure I understand the essence of the problem.  From
my perspective when the owning (paying, accounting) party wants
to reclaim storage, boom, it's gone.  Any shared access after that
time fails.  Are you concerned with what might be residing somewhere
in memory?  It seems reasonable to me that the reclaim (destroy?)
request would take as long as it takes to clean out memory - not
long I assume.

> The problem in membranes is exactly this sort of shared usage pattern.
> In a system with accountable storage NOT based on GC, one party shoots a
> storage allocator, promptly killing off all of its objects with the
> effect that a membrane "in the middle" of a chain is lost, and all
> membranes downstream of that one immediately cease to function.

Right.  What's the problem?

> The alternative is to fudge on storage accountability, letting the
> critical bits of membrane storage be allocated from some system pool.
> While this sort of design makes me rather nervous, it does appear to be
> unavoidable in some cases.

Hmmm.  Even if there is allocation from a system pool for something
like "paged in" memory, I don't see why the base storage still
can't be accounted for as above.  Destroy it (reclaim it) and it's
gone, with all services that it depends on become invalid.

> From an accountability perspective, it can be
> tolerated if we can make arguments of the general form "the gift
> allocation being performed in place A can be viewed as implicitly
> accounted for by some other allocation in place B". For example, if we
> could show that the membrane object proxy allocations are bounded by
> overall process allocations, one can view the membrane objects as a
> "tax" on the processes that use them. If I can introduce a term for this
> (does anyone know an existing one?) I might call this "arms-length"
> accountability.

The above seems rather convoluted to me.  I don't understand why it's
necessary.  I don't see why every resource can't be an object and
every object accounted for.

> Ideally, smaller bounds are better. A tax of log(n) is better than a tax
> of O(n). HOWEVER, this is only true if the variance is smaller than the
> order statistic. For memory hierarchies, the general rule is O(log(n))
> hierarchical mapping tables for n pages, but the worst-case rule is
> O(n). For arms-length accountability to be sound, the order statistic
> must cover the worst case.
> 
> So: can we establish an OS-style membrane design in which some storage
> bound of this form can be expressed? If so, what is the basis object,
> the arms-length bound, and the relationship that sustains that bound?

Sorry, but I'm afraid I still don't understand the problem.  Why
can't the basis object be the membrane?  A membrane requires storage.
No problem.  Some account owns it.  Destroy the membrane (reclaim it's
storage) and all requests through the membrane fail.

I wonder if the issue that I'm missing has to do with language
level resources?  I've never dealt substantively with "OS" resource
management at that level.  E.g. with something like garbage collection
in E?  I don't see any reason why in principle "accounting" can't
be done along the same lines.  I can see, however, where there
might be some significant overhead and implementation work that
would be required to do so.  That is just one of many reasons why,
for me, having protection domain boundaries between active objects
within a language enforced environment is problematic.  While
I admit that it is possible and I'm open to being shown, I
haven't experienced any such environment that I felt was worthy
of trust.

Is that the nut of this issue?

--Jed  http://www.webstart.com/jed/