[cap-talk] Capability levels

[Mark S. Miller]

David Hopwood wrote:
> Note that we already have a capability system with codesigned language
> and network levels: E is such a system. IMHO we need to identify and fix any
> limitations of E's capability model that prevent it from being extended
> to the OS level as well.
> 
> (One such limitation is poor support for resource accounting and protection
> against denial of service. <http://www.cs.utah.edu/flux/papers/redline-hotos7.pdf>
> has an interesting point of view here.)

I believe there is a fork in the design road regarding denial of service by 
resource exhaustion. The KeyKOS line of OSes (KeyKOS, GuardOS, EROS, CapROS, 
and Coyotos) provide good abstractions for resource accounting, and for 
writing a non-trivial range of programs which can operate robustly within 
known or pre-allocated resource bounds. However, the cost is a style of 
programming that's too unfamiliar as compared with normal object programming: 
Are a) activation frames, b) objects/closures, and c) message buffers 
allocated explicitly or implicitly? By "explicitly", I mean either 
pre-allocated, as in Fortran or OCCAM, or allocated from an explicitly stated 
pool, as is possible for objects in C++ by overloading operator new().

BitC is intended to be a memory safe lambda language able to support both the 
kinds of implicitly allocating programs one expects to be able to write in 
ML-like languages, and (by pre-allocation) the kinds of resource constrained 
programs that a Coyotos kernel must be. Once BitC and Coyotos are mature, it 
will be interesting to evaluate whether it was a good idea to design one 
language to serve both these purposes.

In other languages, work on "region types" reconcile explicit pool 
deallocation with static safety against dangling references. The resulting 
type systems look to me too complex for practical use at this time.

One of E's main goals is to teach the ideas of object-capability programming 
to object programmers. I'd say that, by ignoring resource exhaustion issues at 
object granularity, E has been able to explain object-capability programming 
as only (pulling bogus numbers out of thin air) a 10% change from current 
object programming practices. If E tried to support robustness against 
resource exhaustion attacks at object granularity, the result would be at 
least a 40% change from current practices. We'd have taught a bit more of the 
lessons from KeyKOS worth teaching, but to a vastly smaller audience.

There is hope that E-like systems could be made robust against resource 
exhaustion at vat granularity. But for E itself, this isn't so clear. When a 
message arrives at an E vat, from what pool is the memory allocated to queue 
this message?

Systems distributed over today's Internet are inherently vulnerable to 
resource exhaustion attacks anyway.

An interesting intermediate position is represented by Tyler's web-calculus 
and waterken server technology. These are designed so that resources must be 
used in order to successfully mount a resource exhaustion attack. This places 
a kind of work factor on an attack. Even though the attacker may be employing 
stolen resources, there's at least an opportunity cost of using these stolen 
resources to attack X rather than Y. The black market price for bot machines 
gives us a way to quantify this work factor. Interestingly, Tyler seems able 
to achieve this within an architecture that meets E's major high level goals: 
familiar to object programmers, object-capability secure, asynchronous 
messages between communicating event loops, promise pipelining, and persistence.

Christian Scheideler's "Towards a Paradigm for Robust Distributed Algorithms 
and Data Structures" explains a framework with some E-like properties that, by 
applying capability principles in the routing fabric, is designed to make DDOS 
attacks prohibitively expensive for the attacker.

These raise the hope that future E-like systems may be provide significant 
protection against resource exhaustion attacks. However, I will not further 
delay pinning down the definition of E itself in order to take on this 
additional goal. I chose early on to give up on resource exhaustion issues, 
and I think it is now too late to turn back.

-- 
Text by me above is hereby placed in the public domain

     Cheers,
     --MarkM