[cap-talk] Capabilities for immutable data

[David Barbour]

Not everything that provides authority is necessarily an object capability.

If everything that conveys authority in a system happens to be an
ocap, THEN you've got yourself an object capability system. But not
all systems that provide authority are ocap systems. Other approaches
that might provide or restrict authority include: ambient authority
systems, identity-based authority and authentication,
certificate/SPKI, path-based authority (e.g. Java stack analysis),
port-knocking or secret handshakes (hidden algorithm), type-safety,
information-flow analysis (which is closely related to sub-structural
typing), effect-typing, sandboxing and monads.

Most of these systems are obtuse, expensive, inflexible, and weak
compared to ocap security. (Seriously, ocaps are a silver bullet for
expressing security policy.)  But a few of them are complementary and
orthogonal. I've been happy with mixing in structural interface typing
(but not nominative typing), a dose of information-flow analysis
(mostly to constrain automatic sharding and code distribution), and a
little bit of sub-structural typing (e.g. guarantee at-least-once or
at-most-once properties, exclusive transfer), and a dash of dependent
typing (in-the-small). I consider sealers/unsealers wonderfully useful
as a way to constrain information flow and represent abstract data
types, but somewhat orthogonal to capability systems. Interestingly,
one can sometimes perform static analysis of sealer/unsealer paths as
part of the type-system and optimizations.

A capability is a reference that designates authority - properly, just
by holding the reference and firing messages at it (some form of
communication). (A) If you need to "pass" the reference to some other
object in order to achieve authority, it IS NOT a capability. For
example, passwords are not capabilities, nor are certificates, nor are
sealed values. (B) If you need to use a secret handshake, password,
certificate, sealed value, et cetera to utilize an ambient API, this
is also not a capability. (C) If you have a reference to an object AND
you need a password or sealed value or whatever to actually use the
thing, then you've got a rights-amplification pattern. The reference
is still a capability (can only be obtained under the connectivity
rules for ocaps), but does not designate any real authority on its
own.

Anyhow, with the above in mind, I'll respond to a few of your arguments:

On Thu, Feb 17, 2011 at 1:53 PM, Sandro Magi <naasking at higherlogics.com> wrote:
> [...] an immutable Foo which has an operation
>    makeBar(ImmutableList<string>),
> which only succeeds if there are an even number of list nodes
> and all the strings contain only plural English words.
>
> What definition for authority would exclude simple values
> like integers and strings, but include more sophisticated
> immutable structures like Foo above?

Immutable objects can convey (and attenuate) authority by holding
references to mutable objects. They may also hide information obtained
through a history of exchanges. Simple values and pure computations
cannot exercise authority for you, and cannot attenuate authority. But
they can still hide information (e.g. sealed values or infinite-domain
functions).

>
> The fundamental question then is, what constitutes authority?
> In that thread, the others consider only "side-effects" to constitute
> authority, while I was arguing that this is far too limiting.

My argument is more that side-effects are the basis for all authority.
The distinction is subtle. Access to 'information' can be an
authority, and the current state of information is represented using
immutable values, but all information is (ultimately) gathered through
effects. Unlike arbitrary values, 'information' has a past, an origin,
a future, a destination, a relationship with the world in both time
and space. There are many various issues regarding 'information' such
as authenticity, validity, expiration, secrecy.

I idiomatically use capabilities to represent information. I have a
number of reasons for doing so:
(1) Access to information is an authority. In object capability
systems, all authority should be designated by capabilities.
(2) In any real system, information will be updated. Capabilities
(especially the reactive kind I favor) transparently allow for this.
(3) My goals include automatic sharding of computations. But I must
avoid delivering authority to a remote system that would not be
trusted with it. Access to secret information IS authority. By
associating secret information with a particular capability, I can
have a unified information-flow/contagion/constraint model based
strictly upon controlling access to capabilities... which is FAR
semantically cleaner than controlling access to 'values'.
(4) I really don't consider much to be truly 'immutable' - certainly
not code. There is slow mutation and fast mutation. A truly
'immutable' piece of information is so rare that we treasure them by
calling them 'domain invariants'... and we often get them wrong. Live
programming is the only practical approach in a large scale system
(because at Internet scale you don't have authority to stop and
restart).

In the other thread, you asked how I reconcile the use of
'capabilities' to control access to reflection when, presumably, the
information so gathered is immutable. My answer there was rough
(though accurate) that it ultimately comes down to the relationship
between effects and interaction in the system. Code embeds
information, which is why you might want to restrict access to reflect
upon it. Hopefully the above explanation helps clarify the point
further.

Note that values are neither authority nor information. (Technically,
information is a relationship, e.g. between a value and when and where
you obtained it.) The authority designated by the capability is to
access information and stay up-to-date.

>
> "a reference that simultaneously designates and authorizes
> access to an object". However, this is so general as to
> essentially include all values

Minor nit: use of the word 'access' wrongly connotes that the object
must respond to your communication in some locally observable manner.

>
> Suppose I have a safe capability language which has a means
> to *safely* skip the division-by-zero check when performing a
> division. Does this not make integers capabilities by def'n 3

Even ignoring the issue of whether division is an 'authority', the
answer is certainly: No.

Neither the integer nor a proof of non-zero value constitute a
'reference' that designates authority for unchecked division. A proof
might well convey authority, but is not a reference that designates
authority. The whole setup is much closer, in nature, to a certificate
authority (e.g. SPKI). That is, you take the certified value along
with the numerator and pass the two into an 'ambient' unchecked
division operation. The certification provides the authority to use
said operation.

At no point is an object capability involved.

>
> these are the sorts of runtime properties statically verified in
> "Lightweight Static Capabilities"

Yes, that was my impression too. I consider the title to be a
misnomer, but Oleg can't be blamed. He gets to point at David Walker
et al. who decided to create a 'Capability Language' inspired to
support a few **patterns** seen with object capabilities.

This work is valuable, but the name is a bit misleading. Being
inspired by ocaps is not the same as being an ocap. (If we really want
static ocaps, staged compilation will work just fine.)

On Thu, Feb 17, 2011 at 6:36 PM, Sandro Magi <naasking at higherlogics.com> wrote:
> I'm questioning whether objects that have *no* side-effects
> can be controlled by capabilities, and how those objects differ
> from  "pure data", if at all. So the only visible effects of M||R
> and M'||R are to return different values, E and E', respectively,
> with no other changes to the world

Capabilities aren't *required* to be effectful. But, if they aren't,
the only authority they can designate is access to expired
information.

Even effect-free capabilities can be wrapped inside effectful caps -
e.g. auditing, logging, revocation.

>
> The difference in behaviour between the certified and uncertified
> integer *is* the effect: one may throw an exception, one definitely will
> not. Let's make it worse: suppose instead that division by zero caused
> the program to crash, and this "safe division" prevented that. Is it now
> a capability?

I would suggest that the difference is in the choice of division
operations, not in the integers.

Authority to crash a program is certainly authority, but is not a
capability unless designated by unforgeable reference.

>
> Suppose we had immutable arrays, and I encapsulate the array and a valid
> array index into a "ref" type that could be dereferenced to return the
> array value at that index. Is the ref type a capability?

Yes, assuming the 'ref' type meets the other requirements.

>
> I don't see any real distinction between this and the integer, or a statically
> guaranteed "bounded integer", or any number of other examples of "pure
> data" mediated by code (implicit or explicit).

I see a lot of distinctions. I guess it depends on where you're
looking for them.

>
> why should the semantics of the language primitives be excluded
> too, since they are values mediated by code as well.

Language primitives are, by nature, ambient. They might designate
authority, but they aren't capabilities.

>
> What bothers me about this definition of "authority is a side-effect",
> is that a predicate restricting access or construction can be
> arbitrarily complex, and yet such programs would not be considered to
> use capabilities.

There are many ways to constrain or provide access and construction
that are not capabilities. You shouldn't be bothered by that.

Computation breaks down into two aspects: calculation (all the pure
stuff) and communication (all the impure stuff). Turing equivalence
tells us that the calculations we can perform are the same. Thus, in
practice, the stuff relevant for security is communication (including
access to information). For any open system, the only relevant
authority is effectful - either causing effects, or observing them.

>
> If I write a purely functional operating system [1], then it cannot use
> capabilities by definition if we equate capabilities with side-effects,

Indeed. A simple function application cannot even dereference a cap to
ask for its immutable, expired information. You can still have
out-of-band effects via monadic abstraction or other mechanisms, but I
would challenge that: to whatever extent your operating system is
monadic, it is not purely functional. Controlling monadic effects by
use of capabilities is feasible (in Haskell terms, favor an interface
closer to the ST monad instead of the ambient State monad).

>
> There's either a clear dividing line between "values" and capabilities I'm
> not seeing, or there can be no line at all because any such line would be
> completely arbitrary.

All capabilities are, by definition, references. That's already strong
enough to distinguish capabilities from other values. (You use the
phrase 'dereference' many times. This suggests you already understand
this distinction: what is returned from dereferencing?) Ideally, all
references in a capability system are capabilities (i.e. unforgeable,
global, and allowing ad-hoc levels of attenuation, introduction,
endowment).

Of course, 'clarity' is not an objective property. You might even face
some cognitive dissonance if you have some motive to believe that
value references are the same as the values referenced.