[cap-talk] - Bellizzomi - Capabilities and Shapiro's focus, Coyotos, etc.

Jonathan S. Shapiro shap at eros-os.com
Thu Nov 30 00:27:53 CST 2006

The tacit assertion that Shapiro *has* a focus must be viewed as an
unvalidated hypothesis. :-)

On Tue, 2006-11-28 at 16:44 -0800, Jed at Webstart wrote:
> At 03:38 PM 11/28/2006, Valerio Bellizzomi wrote:
> >On 28/11/2006, at 13.49, Jed at Webstart wrote:
> ><snip>
> > >At this point I personally think any such efforts <to block wall banging>
> > >are likely a waste of time and effort.  I believe that the only way to deal
> > >with wall banging (which effort is in itself likely not a good use of time)
> > >is to limit shared resources.  I think the 
> > trade-offs are clear in this area.

I agree with most of this, though limiting shared resources isn't nearly
enough, because logically unshared resources are often multiplexed onto
shared resources (consider network connections) and the multiplexing
points become communication nexi for covert communications.

Having said that, my views about covert channels are predicated on the
assumption that the bandwidth of covert channels is unimportant. This is
an unvalidated assumption, and validating it becomes increasingly
important as defensible systems (of whatever form) become closer to

There is no work in the open literature (and no work of any kind that I
know about) on the engineering of covert channels. That is: no work
doing any serious investigation of how to construct them, what
techniques are best for data exfiltration, how to evaluate them, and/or
characterizing the achievable bandwidth.

I have often thought that it would be useful from a science perspective
for someone to undertake to build a covert channel SDK and lay down the
quality evaluation criteria for covert channel developers. I suspect
that channels of O(100 Kbit/s) are not difficult to construct on current
systems. Having a well-characterized statement of exposure might alter
our outlook on whether this issue is important.

As far as I can tell, the only thing stopping the active development of
covert exfiltration technology is that other techniques are still
easier. In particular, penetration is required regardless and overt
channels are too easy to build.

> >I believe limiting shared resource is one of the objectives of Shap's
> >research (read the "Debunking Linus's Latest" and "From EROS to
> >Coyotos/BitC: Open Source meets Open Proofs" papers).

This is true, though not because of any concern about covert channels.
One of the strengths of the KeyKOS design was that all metadata was
explicitly reified. Mapping structures, for example, are crafted from
Nodes. Nodes are named by capabilities, and the purchase of Nodes is an
accounted activity (via the space bank).

This is in marked contrast to every other system I know about, where the
storage costs of metadata are assumed to be bundled up in the storage
costs of the data they map. The argument is usually that the mapping
tables occupy logx(p) space, where 'p' is number of pages and 'x' is
imprecisely known but small; under this assumption one may argue that
the storage cost can be accounted for as a tax on the storage of the
pages themselves and requires no independent tracking. The problem with
this approach is that it ignores the issue of sharing, the issue of free
riders, the issue of extended durability through reference counts, and
the fact that in small proceses logx(p) >= p. This is true because the
formula is incorrect. It should be more correctly stated as

   ceil(logx(p)) + ceil(logy(ceil(logx(p)))) + ...

where each level of the hierarchy has its own log function and cannot
occupy fractional storage.

By making metadata explicit, KeyKOS forces programmers to address all of
these issues -- most notably the durability problem. I have often said
that this is a feature, because when a problem can't be solved it is
better for an architecture to force the problem to be dealt with than to
bury it under a rug. KeyKOS did not create the problem; it merely makes
it impossible to ignore.

But in practice this is quite awkward, because of the durability issue.
There are no good idioms for negotiating shared durability without a
bidirectional channel, and this defeats isolation in places where one
would like to preserve it.

Note that the same issue exists in MLS systems as a covert channel in
the observability of quota availability. Ironically, the reference count
and implicit observability is a narrower channel than any explicitly
negotiated durability.

The other issue is that scheduling of domains with multiple clients is a
nightmare that nobody knows how to cleanly solve. Priority inversion is
not robust in message passing systems unless message flow observes a
strict hierarchy. There are also well-known pragmatic problems in any
multilevel scheduling scheme where the levels proceed without knowledge
of each other.

> In "From EROS to Coyotos/BitC: Open Source Meets Open Proofs"
> he says:
> _______________________________________________________
> The Coyotos effort inherits two useful successes
> from the EROS effort:
>     A verification proof that the architecture can en-
>     force a security property known as “confinement.”
> and ...
> _______________________________________________________
> but then in "Verifying the EROS Confinement Mechanism" he says:
> "In this paper, we will ignore issues of covert channels.  While important,
> reducing such channels is of interest only when it has been shown that overt
> channels have been closed."

I'm reminded of Talmud scholars, who pick up a bit here and a bit there
and draw whatever conclusion they want. Not that Jed has done so here,
but the style match was pretty good. :-)

Confession: yes, I think the covert channel question is preempted by the
overt channel question, but that wasn't the reason for the disclaimer.
The disclaimer was added to satisfy academic reviewers.

The factory is significant work. It is a unique combination of
confinement and isolation that serves as a building block for larger
security architectures. Proving the correctness of the criteria was
non-trivial. All of this, in my mind, is pretty clear, and warranted
publication of the result. Later, I would realize that the result also
provided a verification gold standard for overall system verification,
though this wasn't clear to me at the time.

But by far the greatest objection of reviewers was over an issue of
definition. Almost universally the reviewers complained that Lampson
included covert communication in his definition of confinement. Since
the paper didn't, they argued, it didn't solve the confinement problem
and must not claim to solve the confinement problem (i.e. the property
needed to be renamed). On these grounds the paper was heatedly argued by
the program committee and was nearly rejected.

Now I have several issues with this. First, Lampson himself doesn't take
that paper all that seriously. He is very clear that it was a workshop
paper sketching a problem, as opposed to any rigorous definition.
Second, the techniques appropriate to covert suppression are entirely
orthogonal to the overt authority issues; in my opinion Lampson erred by
conflating them in his definition of confinement. Third and finally, the
tone of the reviews was simply pissy, being more focused on preserving
the integrity of a non-rigorous definition than on evaluating the merit
of the work at hand.

>From my perspective it was actually important to hijack the definition
of confinement. Ignoring the conflation of covert channels, Lampson's
characterization was pretty good, and it was a widely known label for a
foundational property.

Subsequent papers, including Chander Dean and Mitchell's
"State-Transition Model of Trust Management and Access Control" have
implicitly relied on our (overt) definition of confinement. Most have
failed to cite us for it. The CDM paper is particularly amusing, because
it reasons carefully from a badly constructed abstraction to conclude
that confinement in capability systems is impossible, failing to even
address the existence of our verification result. The CCS committee was
asleep at the switch that year.

So the qualifier went in purely to satisfy the reviewers.

> Sure I know of many of the commercial projects and even
> products based on capabilities (e.g. going back to the
> Plessey 250), but such systems (hardware and software)
> have been and continue to be commercially insignificant.

One should not discount the AS/400 as commercially insignificant.

> Please don't oversell capabilities and suggest that they can
> solve covert channel problems like wall banging.  I think it's enough
> to deal with overt communication channels as Jonathan suggests.

I agree -- on both points.

> > >>I was suggesting to make the login process strictly tied to the
> > >>kernel model of operation.
> > >
> > >I'm afraid I still don't understand what you mean by the "kernel model of
> > >operation."
> >
> >The meaning is Atomic action kernel: setup phase -> commit point -> action
> >phase.
> >The action phase either succeeds entirely or fails entirely, this is the
> >notion of "atomic" as Shap defines it.

I think I can claim credit for the coinage "atomic action kernel". I
certainly don't deserve credit for coining "atomic". :-) At a guess, the
coinage of "atomic" probably predates quantum mechanics.

> Fine.  I don't see what the term "kernel" adds to the notion of an atomic
> operation, but I don't think it matters.

Kernel isn't adding to atomic. Atomic is adding to kernel.

It adds because the prevailing models in the OS literature are either
threaded kernels or interrupt driven kernels, neither of which has the
same properties w.r.t. management of state. The idea of an atomic action
kernel used to be very common, and remains so in industrial control
contexts, but was never much favored in the general-purpose OS world.
The term exists primarily to give this architectural class of kernels a
differentiating label.


More information about the cap-talk mailing list