[cap-talk] Horton vs. ACLs

[Jonathan S. Shapiro]

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.

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.

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.

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. 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.

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?

shap
-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
www.coyotos.org, www.eros-os.org