Lambda the Ultimate

There was an insightful discussion recently on the capabilities mailing list about confused deputies, and how various language constructs can inadvertently introduce confused deputies. For instance, Alan Karp devised a confused deputy innocently introduced by Java's package scoping. I then reproduced this confused deputy using OCaml's modules.

In any system with encapsulation of some sort, there is an inherent disconnect between a caller's permissions to an object, and the callee's permission to that same object. Whenever the callee has greater authority over an object it's given than a caller, and this authority is granted implicitly (by the type system, for instance), a Confused Deputy can arise. This authority augmentation is called "rights amplification" in the capability security literature.

For example, the abstract OCaml type Confused.O.t is automatically amplified to an out_channel upon calling a function in module Confused.O. This usage is safe however. The only problems arise with binary functions, where the second parameter is also implicitly amplified. One solution proposed on the list was to forbid such implicit rights amplification for all parameters except the first, thus forcing all amplifications to be explicit (cap-talk is generally object-centric, thus the emphasis on the first parameter only).

I wasn't in favour of placing this burden on all binary functions, so I proposed instead to forbid "package-scoped" functions. By this, I mean that only publicly accessible functions are visible even for modules within the same "package" (or scope/nesting/etc.). The OCaml vulnerability is only introduced because module Confused.B can access the internal Confused.O.write function, which is not publicly accessible outside of the Confused "namespace".

If this lax scoping were forbidden, the compiler writer would have to either

1. expose the Confused.O.write function publicly, in which case its obvious that writing to the billing file is possible outside of the compiler's module,
2. split the functionality for writing the log and the billing file into separate modules (the best solution),
3. parameterize Confused.B with a closure to write into a Confused.O instance, effectively making it a separately wielded capability.

In all cases, the authority being wielded is more explicit, and thus accidental vulnerabilities are minimized. My proposal may complicate abstractions provided as a set of co-operating modules however, so I have three questions:

1. How common is it to have two co-operating modules use each other's private functions?
2. Has there been any research on this or similar topics, or does this problem resemble any others that have been studied?
3. Can anyone think of any other possible solutions to this problem, preferably with a minimal burden on the user?

On a final note, there was also some discussion about creating confused deputies just using shared mutable state, so there is yet more evidence of the safety of purely functional programming.