Split Capabilities: Making Capabilities Scale

[Norman Hardy]

At 9:16 -0700 00/06/29, Karp, Alan wrote:
>> -----Original Message-----
>> From: Norman Hardy [mailto:norm@netcom.com]
>> Sent: Wednesday, June 28, 2000 8:40 PM
>> To: Karp, Alan; 'e-lang@eros-os.org'
>> Subject: Re: Split Capabilities: Making Capabilities Scale
>>
>>
>> At 9:30 -0700 00/06/27, Karp, Alan wrote:
>> >When we were designing e-speak access control we worried about the
>> >scalability of our system.  Conventional capabilities
>> weren't going to do
>> >the trick.  (Actually, we learned about capabilities after
>> having reinvented
>> >them "wrong", but it's the "wrong" part that's interesting.)
>>  A conventional
>> >capability contains, among other things, a handle for the
>> object being
>> >controlled and the access rights the presenter of the
>> capability will be
>> >granted.
>> >
>> >The problem is the number of capabilities I need to deal
>> with.  After all,
>> >my PC has over 60,000 files on it.  In the most general
>> case, I need a
>> >conventional capability for each operation, e.g., read,
>> write, execute, for
>> >each file.  Some applications, SAP comes to mind, have
>> hundreds or thousands
>> >of methods, each of which I might want to control
>> separately.  The number of
>> >capabilities to be managed becomes a problem quite quickly.
>> >
>> In most capability systems the various capabilities to some particular
>> object need not be created simultaneously with the object.
>> They are created
>> as needed. The general pattern is that a strong capability C
>> is returned to
>> the requester. Invocations of C will produce any of the forseen weaker
>> capabilities. Even capabilities with access discrimination
>> unforseen when
>> code for the object was written can be provided by writing a
>> "front end"
>> object which holds a strong capability to the real object and filters
>> messages to the real object. A capability to the front end is like a
>> capability to the original object with the new rule in place.
>> For instance
>> a data base can be front ended with a noise function that
>> smears but does
>> not hide statictical properties of the salary field of
>> personel records.
>>
>> ....
>> Norman Hardy  <http://www.mediacity.com/~norm>
>>
>
>Of course, you can always issue a single capability that grants several
>access rights, what you call a "strong capability".  That's why I used the
>phrase "in the most general case".  However you do it, if the capability
>holds both the object handle and the access right(s), you'll need a separate
>capability for each distinct object and each separately controllable set of
>access rights on that object.  The scaling is N*M.  Split capabilities
>reduce the scaling to N+M.

Capabilities are a bit like floating point values. You do not need enough
storage to keep every possible floating point value even though in general
a particular computation may in principle use any possible floating point
number. As with fp numbers you may discard them and reproduce them upon
demand. Most Keykos objects were created and destroyed  with few of the
possible capabilities for them ever having existed. Many (most?)
capabilities were created, passed, used and then discarded in less than a
second.

Your pattern may have other strengths, however.


>In the case of multilevel security, I can cover
>all cases with only one e-speak capability per security level, and each user
>gets only one capability.  In the case of Unix-style file access control, I
>only need 3 capabilities for the world, 3 for each group, and 3 for each
>user, and each user only gets 9 of them.  In both cases, files can be added
>to the system at any time without the need to create new capabilities.

If we are to model the access that the Unix directory logic provides to
files we may proceed as follows: The directory object holds a strong
capability to each of its files or subdirectories. A requestor invokes the
directory object via a capability that identifies his uid & gid. The
directory code now has the information to produce and return a capability
of just the right strength. The directory object need not store this
returned capability as it can be easily regenerated on demand. I may
misunderstand your example.

>There's still a problem with the approach you describe.  Namely, over time
>I'll accumulate a large number of capabilities.  Either I'll have to present
>them all on each request,

If the code making that request is capability savvy it whill know exactly
which capability to invoke. It probably depends uniquely on the call site.
I think there is a conceptual mismatch here. Perhaps I am just confused.

Irrelevant anecdote:
Some Prolog systems intern floating point numbers. This has prevented
serious physics from using Prolog at least once. (There might have also
been other problems. This was the first show stopper.)
Norman Hardy  <http://www.mediacity.com/~norm>