Split Capabilities: Making Capabilities Scale

[Karp, Alan]

> -----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.  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.

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, in which case the permission checking will take a
long time, or I'll need a way to track which ones I need for each request.
If capabilities expire, I'll have to provide a way to get rid of those that
are out of date.

Since e-speak capabilities are so lightweight, presenting them all on every
request is not a problem.  We even simplified the process by constructing a
resource that could hold a collection of e-speak capabilities.  Simply
providing this resource was equivalent to presenting all the capabilities it
contained.  Permission checking involved an integer equality test of each
capability against each permission field in the repository entry.  The
scaling is favorable, being the smaller of N+M and N log M, where M is the
size of the larger field.

A split capability can also be used for control unforeseen when it was
created.  All that is needed is to add an entry to a new or existing
repository entry associating the capability with a new access right.

It is true that we chose to create the e-speak capabilities at the time the
resource entry was created.  This step could have been deferred, with the
resource handler dealing with authentication on a user's first access.
However, e-speak capabilities were so lightweight that we never found early
creation to be a problem.

We also have a function like the one you describe for smearing database
information.  E-speak was designed to encourage service composition.  Hence,
if I want salary information, but I'm not authorized to see individual
records, I can still invoke a service with that right that can return the
summary.  I only need one or more capabilities recognized by the service.
The service only needs one capability to access the entire database.  No new
mechanisms need to be introduced.

_________________________
Alan Karp
Decision Technology Department
Hewlett-Packard Laboratories MS 1U-2
1501 Page Mill Road
Palo Alto, CA 94304
(650) 857-3967, fax (650) 857-6278