[cap-talk] EQ not required by object-cap model (was :Flawed first attempt)

Dean Tribble tribble at e-dean.com
Sun Dec 10 23:20:02 CST 2006

On 12/10/06, Toby Murray <toby.murray at comlab.ox.ac.uk> wrote:
> On Fri, 2006-12-08 at 09:35 -0800, Mark S. Miller wrote:
> > Joule provided both sealer/unsealer style and trademark style rights
> > amplification primitively, but studiously avoided EQ. With these others,
> it is
> > possible to build an equality operation with many of the virtues of EQ,
> but
> > without (what I think Dean would argue are) the flaws of EQ.
> >
> I'd love to hear more about any weaknesses of EQ. Has this been written
> about anywhere?

In Joule (and later in E) language discussions.  This makes me realize I
should find the Joule archives and post them.

There are various complexities with EQ breaking abstractions. From an
encapsulation and/or cap-security point of view, it reveals information
about the objects referenced without objects, abstractions layers, etc.
being able to intervene in it.  Thus it can break various abstraction
patterns.  A requirement for Joule was to support complete transparent
forwarders.  For a caller to be unable to distinguish between an object and
its proxy or between two proxies for the same underlying object, the caller
must not have access to a primitive EQ.

An alternative approach is to make the primitive EQ closely held.  For
example, I used this in some E runtime code: there's an EQ primitive that is
closely held and used by "privileged" E code to implement E's more
complicated equality semantics.

Also, is there a description of the semantics of this "equality
> operation with many of the virtues of EQ, but without the flaws",
> whatever these flaws are?

Essentially, objects that want to be compared should be comparable, and a
client should not be able to unilaterally determine whether two objects are
the same/different without sending messages to them.  I'll try to swap in
more issues, but in the meantime, here are the miscellaneous notes that come
to mind:

- Norm Hardy observed that in most practical circumstances, EQ was not a
security risk because the "attacker" would either not have access to both an
underlying object and a proxy, or would not be able to make use of the
distinction in an attack.  That's largely true in practice, though for
example, E's network protocol has to jump through a lot of hoops to preserve
E's equality semantics when two references for the same object come through
two different paths.

- a favorite OO optimization technique is to use factories or factories
methods generally, and then insert caches, singletons, etc. where
appropriate for performance.  EQ allows a client to trivially
discover/trip-over such optimization and behave differently.  In most
circumstance, that's not a security issue, but is an encapsulation and
reliability issue.

- Joule used various Actors-inspired techniques to enable, for example,
numbers implemented in the language to be indistinguishable from numbers
implemented primitively.  These techniques are also broken by EQ (e.g., is
the primitive 1.0 == the user-defined 1.0?).  I used to consider this a
fatal problem.  However, during the DARPA security review of E, we observed
that E's use of "bottoming" of parameters (coercing user-defined objects to
primitive types) simplified enforcement of those boundaries. For example, if
an "integer" index parameter was instead user-defined, it could forward
secrets of its use elsewhere, or act like "2" now and "3" later, leading to
time-of-check-time-of-use vulnerabilities.  Joule also supported such
"bottoming", but to the extent that boundaries "bottom" parameters, they
*prevent* such user-defined "primitives" from being used in such
circumstances, lowering the value of such uniformity with primitives. Thus,
this is still a problem with EQ, but I have not revisitedhow big a problem I
think it is :)

> Actors and Joule did not simply fail to provide EQ. In both cases, it was
> a
> > purposeful choice that was realized (successfully for Joule) only at
> great
> > effort.

It is plausible to me that MarkM went through just as much work to come up
with a decent equality semantics for E :)

> At some point, we should revisit the arguments that motivated the
> > exclusion of EQ from Joule. Unless and until Dean's objections to EQ are
> > successfully answered, we should still consider EQ-less systems a viable
> > design choice.
> >  Any future systems that make this choice I still want to
> > include in the objcap category.

We should definitely consider an EQ-less system a viable design choice.  As
I noted above, the ability to easily enforce parameters at security
boundaries may suggest that parameter checking of some form will generally
be required.

> <http://www.erights.org/elib/equality/grant-matcher/history.html>
> > says a bit about this history, but doesn't really go into the meaty
> bits. I'm
> > afraid I've never really been able to reproduce Dean's arguments here
> well.
> > Perhaps we can entice Dean to jump in?
> I'd second that motion. It sounds like his insights here would be
> invaluable.
> The final conclusion (at least from the above link) seems to be that we
> either want EQ or we want sealer/unsealers primitively, since one can be
> built from the other -- or at least an approximation that is close
> enough for most purposes. Is that about right?

Neither is required primitively, since sealers can be built from pure object
encapsulation without EQ.  The sealer implementation at
http://www.eros-os.org/pipermail/e-lang/2003-May/008677.html implements
sealers using integer compare.  In Joule, I did once implement it without
even integer compare, just to show it could be done (as I recall, it
involved function tricks analogous to Peano arithmetic or defining true and
false as functions, and so was primarily interesting as an existence proof).

I'll have to read further, particularly about the semantics of the EQ
> that can be built from sealer/unsealers. Cheers for the info.

The basic idea  is that instances of a class (or objects from the same
scope) can recognize each other, and thus implement whatever equality
semantics they want, including identity.  Thus you can build identity where
you need it, without having it imposed from outside, which would preclude
abstractions with a different concept of identity.

> > When EQ is desireable, it is fabulously desireable. As a person who has
> > My own sense is that I rarely need it, but when I do need it, I *really*
> need
> > it. (Even though, often, Dean can then explain to me how I didn't
> actually
> > require it.)

The place where it most often comes up is implicitly as keys in maps. Most
commonly though, the keys are iether value types with a coherent notion of
equality, or the map is really a cache or property extension table for
objects.  The former don't require EQ, and the latter can usually be
refactored to result in a cleaner system :-).  That's a broad and vague
claim, however.  As with multiple inheritance, I'm always on the lookout for
an example that wouldn't be better designed without EQ or multiple
inheritance :-)

> > It is even more rare that EQ is necessary, indeed, it can be argued (and
> > > dean has done a pretty good job of demonstrating) that EQ is never
> > > actually required. Let us consider rights amplification as an obvious
> > > problem for which EQ seems necessary. For the rights amplification
> > > primitive sealer/unsealer pair, there are two well-known
> > > implementations: the ping sealer, and the shared variable sealer. The
> > > ping sealer requires EQ. But the shared variable sealer does not. See
> > > them at
> > >
> > > http://www.cypherpunks.to/erights/talks/efun/pingSealer.ppt
> >
> > I recommend it. Until I saw MarcS' shared-variable sealer/unsealer pair,
> I was
> > convinced such a thing was impossible.
> >
> Does the shared variable sealer not use EQ? (as Charles Landau pointed
> out) or can this particular use of '==' be implemented in some other wa?

Yes, Ping's uses EQ (which is just fine in E :).  The one referenced above
does not.

(I plan to start following this list again, so I'll start catching up to the
rest of the thread...)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.eros-os.org/pipermail/cap-talk/attachments/20061210/cc03af04/attachment.html 

More information about the cap-talk mailing list