ImperialViolet

Software Fault Prevention by Language Choice: Why C is Not my Favourite Language [via DNM]

The following is a result of an IRC conversation with Zooko and tvoj and may well only make sense if one was a part of that conversation

This article (from the E homepage) suggests that capability systems cannot stop communicating conspirators. I think that either the author of that (MarkM?) or myself are misunderstanding something here. Capabilities can stop communicating conspirators (I'll show that in a sec) - but part of the situation definition in the article is "Bob may also communicate with Mallet" - which is a different problem. The article is, I think, talking about the following situation:

A has a capability cap and can communicate with B. A and B wish for B to be able to use cap but A cannot transfer cap to B

In that situation A can proxy requests for B and in that way B can use cap

Now, there is a separate discussion about a different situation. I think we were confusing the two last night. The situation this time seems to me to be:

A has access to secret information and wishes to communicate/leak this to B. The capability system seeks to prevent this

Now I think that a capability system can ensure this. Proof by induction: Suppose for a moment that A and B have no capabilities. Thus they cannot do anything at all and so cannot communicate. If you only give them access to objects that do not allow communication then neither can communicate.

The problem is that the number of objects which do not allow communication is small and it's hard to find them. (I should mention at this point that this is a problem that Multics tried to solve - interested parties should Google for some papers from that).

If we give A and B access to integers and simple operations (add, multiply, divide) then they can perform simple tasks and still not communicate - even if we give them capabilities to the same integer objects. Integers are environment free - they have no state. An object which is environment free is also side-effect free and deterministic (the result only depends on the inputs). You can also think as side-effect free as does not write to to environment and deterministic as does not read the environment. In the following I mean deterministic (D) to mean mearly deterministic, the same for side-effect free (SEF)

Of course such properties only hold if the inputs are at least as strong. For example if you pass a deterministic object to an environment free function, then that function may set some global variable through the input.

To stop A and B communicating you must stop their environments from touching. You can give them EF objects with no problem. You can give them EF and SEF objects with no problem, same for EF and D objects. However, as soon as they have SEF and D objects you may have a problem as the D objects could write to something which the SEF objects could read.

Now, if A and B are running on the same computer then they share objects like the CPU. Give B a clock and they can communicate via the lengths of time-slices etc. Give them the ability to malloc and they may be able to communicate via the VM etc. This is why it's such a hard problem.