[cap-talk] Non-Delegatable Authorities in Capability Systems

[Jed Donnelley]

At 04:24 AM 12/6/2007, Toby Murray wrote:
>Hi all on cap-talk and e-lang,
>
>(apologies for those who subscribe to both lists)
>
>We've just had accepted that may be of interest to many on these lists.
>
>"Non-Delegatable Authorities in Capability Systems"
>By Toby Murray and Duncan Grove
>(to appear in the Journal of Computer Security)
>
>http://web.comlab.ox.ac.uk/oucl/work/toby.murray/papers/NDA.pdf
>
>The paper speaks to the heart of the "delegation" issue that has been
>debated many times over the years on these mailing lists. I think it
>represents a so-far unexplored part of the debate that I hope will be
>reignited at this point. I'll let the abstract do the talking.

Toby and Duncan - Sorry to take so long to get back to you about your
Non-Delegatable Authorities paper.  It took me a while to read through
the paper and what I considered to be the important references.  I
felt I needed to communicate a bit with Toby privately just to insure
that we're both comfortable debating the topic on cap-talk with no
hard feelings for strongly felt positions.

As Toby and Duncan note in the above paper, I believe that preventing
delegation is not only harmful for programability (and thus for security)
but is also unnecessary - as he refers to my early Managing Domains paper:

J. E. Donnelley, "Managing Domains in a Network Operating System" (1981)
Proceedings of the Conference on Local Networks and Distributed Office
Systems, Online, pp. 345-361.
http://www.webstart.com/jed/papers/Managing-Domains/

My position on efforts at delegation blocking have strengthened
somewhat since I wrote the above paper, significantly since
I've been active on the cap-talk list (2004), and even more
since our Horton work.  I'll lay out my arguments here.


1.  First regarding unnecessary:  Let's consider the value
section of the Non-Delegatable Authorities Paper (hereafter
NDAP) paper, 1.2.  I argue that from the viewpoint of access
control, communicating a membraned capability in place of a
non-delegatable capability provides all the value with more
control.  At the point that Alice's code is patched after
being discovered as vulnerable, the membrane can be revoked
and reissued to Alice.  This of course not only controls
access to the capability itself, but to any capabilities
communicated through the capability - a point I didn't see
addressed in the NDAP.

I don't believe membraned capabilities can be combined
to result in rights amplification because the membraned
capabilities aren't the same as the capabilities
required for the rights amplification.  Perhaps we
can look into this further if this is an issue.
This can depend a bit on which capability is invoked
for rights amplification and how.  Perhaps it would
be helpful to have a specific instance of rights
amplification (which I guess depends on some EQ or
MyCap? mechanism?) to pursue this further?

Regarding accountability, I argue that a mechanism like
Horton:

Mark S. Miller, James E. Donnelley, and Alan H. Karp,
Delegating Responsibility in Digital Systems: Horton's
"Who Done It?", presented at the 2nd USENIX Workshop on
Hot Topics in Security (Hotsec '07), Boston, August 6, 2007.
http://www.webstart.com/jed/papers/horton.pdf

provides accountability with more flexibility.  From
my perspective the accountable entity for actions
enabled by a capability bears no necessary relationship
to a particular code segment that might be the first
active object that receives a communicated capability.
With Horton any capability can be set up so that
other capabilities communicated through it have
their accountability (accountable entity label)
transformed (or not).  If Alice needs to modularize
her code, she can do so and act on a capability
labeled appropriately as a single accountable entity
(or not).

Regarding accountability in the real-world, I argue
that such accountability is tied to responsibilities
that come as positions or roles, not to individual
actors.  If a secretary or administrative assistant
needs to be delegated the authority to act on behalf
of a responsible party in some circumstances, it
can be done.  The responsible party is still
accountable and the action by the delegated entity
is logged and can be controlled (e.g. as with
Horton).  This flexibility is often vital - as it
is in programming systems.


2.  Second with regard to harmful:  This is the
main body of my concern.  Unfortunately I'm not
sure I have terminology appropriate to express
my main concern in this area.  I'm hoping others
can help.

Any computer system consists of segments of
sequential code in separate or shared domains
that communicate.  At any point in time one
can draw boundaries anywhere in the system to
define what is included - outside the system
considered I/O and inside the system considered
internal communication.

What I believe is vital for programability of
computer systems is the ability to at any time
take what was previously a single code
segment in a single "domain" (protection
region/object) and break it into multiple
objects (I'll stick with the object
terminology as possible).  It should also
be possible to make use of other code in
what is potentially a separate object through
communication.  In a private instance of this
message to Toby I referred to this ability
as "composability and decomposability".  I'm
not sure what the right terminology is, but
I feel it is vital.

 From my perspective non-delegatable capabilities
(object references) break this fundamentally
important property of programming in computer
systems.

Consider the case where "Alice" is the active
object that has somewhat limited trust by
whatever program (Bob) that is communicating to
Alice so that the communicated permissions are
communicated as non-delegatable capabilities.
Later it's decided that the programming of
Alice needs to be improved and the planned
improvement is to break the code that
originally composed Alice into multiple
distinct objects.  What was previously
shared references to a single object within
Alice now requires Alice to communicate some
objects to a new part of Alice.  How can this
be accomplished if one of the permissions
that needs to be communicated is the one
that Bob didn't fully trust Alice with?

It seems that Alice's only alternative is
to proxy such access to what has now become
a separate object within what was formerly
her single "domain"/object.

The same sort of problem arises if Alice
might need to make use of another existing
object to better modularize her code.
Somebody implements a new object that
modularizes just what Alice needs, but
alas for poor Alice she has a non-delegatable
capability that she needs to send to it?


One of the strengths that I believe we are
"playing" to with the object/capability model
is the similarity - even the essential identity
of the model - with the object programming model.
How many object programming models are there
that you know of where references in some cases
can't be communicated as parameters?

The disaster that seems to befall a programming
system with non-delegatable object/capabilities
is that it seems to have to always be prepared
to communicate by proxy.  If it has a way to
test for non-delegatability then it does the
test and communicates as automatically as possible
by proxy.  If it doesn't have such a test then
it seems to need to delegate by proxy at all
times - just in case it happens to have been
passed a poisoned object reference.

This is nonsense.  No object programming model
would (should) put up with it.  If anybody knows
of such object programming models, I'll be
quite interested to hear about them and how
they manage to function.


3.  Regarding the implementation:  It's a
neat trick, but a neat trick used for the worse
sort of programming IMHO.  It takes a subtlety in
the language and exploits it to defeat the basic
communication paradigm of the language and model.
To me this implementation argues more for fixing
E than it does for non-delegatable objects.  I
say hurray for EROS (KeyKOS, etc.) that their
implementation is faithful to the notion that
all permissions are represented by object/capabilities,
even the permission to return from a call.
Besides being valuable for implementations
(e.g. the ability to store return capabilities
in a directory the way the DCCS implementation
did) it just generally provides all the value
of objects for the return authority.  If
capabilities are good for one authority and
good for an authority model then I argue
that they are good for all authorities.

One further note on the implementation:  If the
idea of a non-delegatable capability is good and
needed (as I argue not), then it seems to me
the thing to do is to make it visible and
always available.  This can be done in a relatively
straight forward way as DEMOS did with a
"pass once" access right that is turned off
when communicated, e.g.:

F. Basket, J. H. Howard, J. T. Montague,
"Task Communication in Demos", Proc. of the
Sixth Symposium on Operating System Principles,
Purdue University, 1977, pp. 2331.

http://portal.acm.org/citation.cfm?id=806544&dl=ACM&coll=GUIDE
<may not be original to that paper/system, I
just remember it there and know of no previous
reference>

Of course doing so makes it a primitive
of the capability implementation.  I'm not
advocating for this because I'm horrified by
it [as I was in Demos], but I do think that
direct approach is better than drawing out
some hidden lack in the capability implementation
and exploiting it for this purpose.

By providing a primitive that will turn any
object reference into a "pass once" reference
one can easily support such non-delegatable object
references.  Of course doing so becomes a visible
system primitive.  The fact that such a mechanism
may not be pure object/capability (just "capability")
I argue is relatively insignificant compared to
the cost of the approach you seem to be suggesting.
As I say, I believe doing so (either approach) would
utterly destroy the object programming model, but
better even that than to hide what's being
done in such an obscure way and still expect
it to be available for use for all object
reference communication - IMO.


4.  One minor point I'll mention with regard to the
references:  The only reference that NDAP uses
in support of the "loose capabilities" argument is
where you say, "the inability of capability systems
to prevent delegation by capability passing hinders
security because it increases the burden of trust
(as argued in [31])", referring to:

Dan S. Wallach, Dirk Balfanz, Drew Dean, and Edward
W. Felten. Extensible security architectures for Java.
In Proceedings of the Sixteenth Symposium on Operating
Systems Principles, pages 116{128, 1997.

where they do consider the capability model as
one type of a security 'extension' architecture
for Java (does this end up being something like
vats for Joe-E?).  Since this is the heart of the
value side of the equation for non-delegatable
capabilities, I though that specific reference
particularly important.  I'd like to aggressively
go after any such arguments until I (we) am (are)
convinced that there is some fundamental truth to
them or manage to see through/shoot down their
arguments.

In the case of this paper:

http://www.cs.princeton.edu/sip/pub/sosp97.pdf

I believe the crux of the argument is in section
4.3 where they refer to the issue of "confinement
of privileges".  They refer to Lampson's famous
(appropriately?) note:

LAMPSON, B. W. 1973. A note on the confinement
problem. Communications of the ACM 16, 10 (Oct.),
613–615.
http://www.cs.cornell.edu/andru/cs711/2003fa/reading/lampson73note.pdf

The above note concerns itself only with confinement
of information, not confinement of the propagation of
privileges.  As such that reference seems to me
inappropriate in this context.

Beyond that reference, the authors of the Java
extensibility paper simply state that, "It should
not generally be possible for one program to
delegate a privilege to another program (that
right should also be mediated by the system)."
without supporting argument.  As noted in this
message I believe that position is seriously
flawed.  Of course in the object/capability
model the authority to delegate requires
a capability to delegate over and that is
exactly where the only system "mediation"
'should' be applied as that matches up
exactly with what can be enforced regarding
communicating conspirators.

In the above section 4.3 they say, regarding the
"inalienable right to communicate a capability"
(my term) that:

"This is the fundamental flaw in an unmodified
capability system; two programs which can communicate
object references can share their capabilities without
system mediation. This means that any code which is
granted a capability must be trusted to care for it
properly."

Uh, of course.  Isn't this obvious?  That's what you
mean by granting a code a capability - trusting it
with the capability.  Of course any sort of "system"
mediation can be applied in the capabilities that
are granted for communication.  E.g. if all such
capabilities include Horton responsibility re labeling,
then any communicated capabilities will be so
re labeled.  Any needed "system" mediation can be
similarly applied to any capabilities granted
for communication.

Then they say:

"In a mobile code system, the number of such trusted
programs is unbounded.  Thus, it may be impossible to
ever trust a simple capability system."

This really floors me.  If the above reasoning is
sound, then we have some very serious problems with
the capability model.

Firstly, if the number of programs communicated to
by one program is indeed unbounded (e.g. the case
of no confinement that Toby and Duncan focus on),
then it seems to me that the fundamental trust in
the program given the original permission with this
wide ability to communicate needs to be pretty high.
It seems obvious to me that if I trust a program
with a permission (e.g. RW access to a file) and
that program can communicate widely, then the only
thing between me and widespread access to my file
is my faith in the correct operation of that program.
As we know from the communicating conspirators example:

http://www.erights.org/elib/capability/conspire.html

(Is there a reference for this description?)

where MarkM says:

"Can Alice arrange to prevent Bob from giving Mallet
the Power? The answer is simply no."



I'm sure you can tell this is something that
I feel strongly about. I think this is exactly the
sort of topic that is important to discuss on
cap-talk (the "loose caps" concern being high
on the list of concerns about object/capability
systems). I'm a bit worried that there is a paper
accepted for publication on the topic before it
is thoroughly vetted on the list (unless I missed
that discussion).  Of course there are topics on
which reasonable people can simply disagree, but
I believe this one is so fundamental to the
object/capability model and to object programming
in general that I'm afraid a fundamental rift on
this topic may split the community.

I sincerely hope we can work out the issues on
this topic.  I wonder if it would be worthwhile
to seek out any other places that seem to make the
"loose capabilities" argument and examine their
reasoning.  I can see the intuitive appeal of
this argument.  It's just that this is a place
where I believe our intuition is simply wrong.

I believe that with the sort of membrane mechanisms
we have in appropriately extendable capability
systems (e.g. the E examples such as the membrane
instances and Horton) we have available as much
protection as we can get for communicated capabilities
in the face of communicating conspirators.  Asking
for more, particularly in the form of "non-delegatable"
capabilities, I believe to be seriously unwise in
that it breaks a fundamentally important value in
the programming system and gains nothing in return.

--Jed  http://www.webstart.com/jed-signature.html 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.eros-os.org/pipermail/cap-talk/attachments/20071216/315ae786/attachment-0001.html