[cap-talk] Horton vs. ACLs

[Jed Donnelley]

On 10/8/2007 10:38 AM, Mark Miller wrote:
> On 10/8/07, Jed Donnelley <capability at webstart.com> wrote:
...
> Systems like E, where allocation and GC <Garbage Collection>
> are implicit, are vulnerable to denial-of-service by resource
> exhaustion attacks.
> 
> For ocap systems like KeyKOS, EROS, CapROS, Coyotos, GuardOS where
> right to memory is a first class right and the kernel does no implicit
> allocation, we do not yet have practical proposals for membrane
> mechanisms, whether for use by Horton or even for non-kernel remoting
> systems like DCCS. I have heard no proposal for non-kernel remoting
> systems that are invulnerable to memory exhaustion attacks.

Thanks for clarifying that MarkM.  When you refer to memory
exhaustion attacks I assume you are referring to attacks that
result in denial of service - e.g. vs. breaking access control.

I now remember a bit about these resource exhaustion attacks
being mentioned before.  Perhaps I don't take such attacks
seriously enough.  To me the scope of denial of service attacks
that involve resource exhaustion are so broad and so serious
in existing market leading systems, that I tend to place them
into a category of "we'll worry about those issues when they
come to the top of the list" - e.g. a bit like covert channels
such as wall banging with regard to confinement.

>> Aside from any use Horton sorts of mechanisms may have in modeling
>> hybrid systems, I would like to better understand the concerns that
>> Jonathan is expressing about the unsuitability of Horton to
>> practically achieve the auditability value of ACL systems
>> in a pure object capability context - as I believe we have
>> claimed in the Horton paper.
> 
> The only objection I've heard about Horton so far is storage
> management. This is a serious objection, but doesn't contradict any of
> the claims made in our paper.

Ah, and this:

On 10/8/2007 11:16 AM, Jonathan S. Shapiro wrote:
> On Mon, 2007-10-08 at 10:38 -0700, Mark Miller wrote:
>> On 10/8/07, Jed Donnelley <capability at webstart.com> wrote:
...
>>> Aside from any use Horton sorts of mechanisms may have in modeling
>>> hybrid systems, I would like to better understand the concerns that
>>> Jonathan is expressing about the unsuitability of Horton to
>>> practically achieve the auditability value of ACL systems
>>> in a pure object capability context...
>
> Since Jonathan didn't raise any such objections, Jonathan would be
> interested to know about them also.

Ha!  I got a good laugh out of that one.  I hate email in this
regard.  Particularly with someone who I've never had the
opportunity to interact with directly.  I hope we get a
change to talk some time Jonathan.

When you indicated that:

"...I ... agree that there are places where ACLs are a
better solution..." for access control.

I thought you were referring to what one might call functional
interface issues rather than resource exhaustion issues.
Please don't misunderstand me to be dismissive of such
resource exhaustion concerns.  However, I admit that I do place
them into a category that I think of as somewhat lower priority
considering how riddled today's market leading systems are with
such vulnerabilities.

Still, I'm glad to have this topic refreshed as it will help
me be more tuned into the garbage collection issues when
discussing access control alternatives in future.  I believe
that even ACL mechanisms are vulnerable to resource exhaustion
attacks (how large can ACLs get?).  I'm not sure I understand
how capability mechanisms like membranes/Horton add significantly
to such vulnerabilities, though they of course don't solve them.

> But just to be clear whether we are looking at the same problem, let me
> attempt a zero'th-order attempt to state the problem.
>
> The audit problem is to provide a mechanism by which an external
> security auditor (a human using tools) can determine which programs have
> access to which authorities.  There is an intrinsic conflict between the
> desire for and utility of private namespaces and the desire for and the
> importance of auditability.

Hmmm.  This description seems to go beyond any concern about
resource exhaustion issues to more high level functional concerns.

Perhaps this should be a different thread than Horton vs. ACLs?
I'm not sure.

Let me see if I understand more what you are getting at.  Take
a classical C-list system for example.  In principle a security
auditor (a human using tools) can determine which programs
have access to which authorities by looking at the c-lists
of the programs.  There are of course many practical issues
that may stand in the way of such auditing - e.g. getting access
to the c-lists of the programs, getting enough of a snap shot
of the system state to effectively be able to make sense out
of a very dynamic situation, etc.

How do you consider such an approach to what you seem to refer
to as the "audit problem"?  Incidentally, is this a well enough
known/characterized problem that one might call it The Audit Problem?

I believe what we focused on more with the Horton mechanism
was means to log "who" had accessed (past tense) what in the
sense of an audit log that could be analyzed after the fact.
However, it is true that by looking inside the Horton records
one could observer "who" had access to what (that went through
any particular Horton service).  In some of our presentations
we noted the possibility of asking a Horton service "who"
has access to a particular object serviced through Horton,
and even how any such access was delegated.

The Horton mechanism was intended to be applied at a higher
level than the active object (running program, process) level,
where any given identity would have more long term significance -
e.g. such as being associated with a person or a long term role
(the Horton "who"s).

> I am not aware of anything in Horton that addresses the namespace issues
> one way or the other -- the namespace problem seems largely orthogonal
> to the low-level ACL problem.

Whew.  I think for me to participate in the above it would really
demand an interactive discussion.  In the above you seem to me to
be identifying the 'audit problem' with the 'namespace problem'.
Then I lose you when you say that is orthogonal to the "low-level
ACL problem".

Sorry I don't seem to have enough context to contribute to
the above.  Perhaps MarkM can do better.

>> The only objection I've heard about Horton so far is storage
>> management. This is a serious objection, but doesn't contradict any of
>> the claims made in our paper.
>
> It wasn't intended to.

I'm glad of that much.  Now I'm not sure whether the garbage
collection problem(s) of membranes that Horton shares should
(full disclosure) have been mentioned in the Horton paper.
If people were to mention resource exhaustion denial of
service vulnerabilities in architecture descriptions, I'm
afraid the literature would be rather overwhelmed with
this seemingly redundant information.  Perhaps it is left
to the few non-vulnerable architectures to tout their
additional strength?

I agree with David Chizmadia:

On 10/8/2007 11:55 AM, David Chizmadia (JHU) wrote:
> Karp, Alan H wrote:
>> Shap wrote:
>>> The audit problem is to provide a mechanism by which an external
>>> security auditor (a human using tools) can determine which
>>> programs have access to which authorities.

>> Horton doesn't have anything to say about this problem.  If you meant
>> "people" where you said "programs", then the answer is straightforward.
>> Some of the identity objects in Horton come from the same administrative
>> domain as the auditor, so the auditor can assign meaningful identities
>> to them.  Others may not, in which case the auditor can do no better
>> than to use path based names, e.g., HP employee Alan's MarkM's Shap.
>
>     When I look at the audit problem (as described by Shap), I've
> always felt that the major "social" problem with capabilities is
> that they force the human auditors to confront the ugly limitations
> of *any* audit subsystem.  Namely, that the *most* that the logging
> facility of any software (OS or program) can say is that a
> particular request came from an entity that is associated with some
> (essentially) meaningless number, structure, or string.
>
>     In the case of straight capabilities, this would usually be
> expressed as something along the lines of: "this (specified) request
> originated from an entity holding a capability given to the entity
> that claimed to be ...". In the presence of Horton, it would be
> possible to trace the chain of introductions (i.e., the path-based
> names described above) that led to the issuance of the capability
> used for the invocation. This could be useful in some forensic
> investigations.

at least that the Horton delegation chain auditing can
be used to provide more meaningful forensic information.

Of course something alike could in principle be provided
in traditional ACL systems, though the ambiguity of who
can modify an ACL (e.g. just the "owner") and the
difficulty of doing delegation tend to make any such value
less attractive in traditional ACL based systems such as
Windows and Unix.  Log information such as "The owner opened
up this access to world"  (or even to group ABC) seem
rather less helpful than a log entry that notes that
Alice delegated access to Bob.

--Jed  http://www.webstart.com/jed/