[e-lang] Reentrancy via Recursion

[Toby Murray]

Hello all,

A while back, David Wagner posted examples of attacks against
well-studied object-capability language abstractions, namely

http://www.eros-os.org/pipermail/e-lang/2008-March/012508.html

and

http://www.eros-os.org/pipermail/e-lang/2008-March/012516.html

The thing that both of these attacks had in common was that they
exploited reentrancy-via-recursion. In both cases, an object, o,
implementing some abstraction must maintain some invariant. o must also
call some untrusted code. While calling the untrusted code, o can be
invoked recursively. This reentrant invocation of o causes its internal
invariants to be broken.

E, and other object-capability systems based on event-loop concurrency
like Waterken, go to great lengths to minimise
reentrancy-via-concurrent-execution -- namely where two threads are
invoking the same object at the same time. This form of reentrancy has
long been recognised as a source of difficult-to-diagnose-and-fix bugs.

I'd like to argue that reentrancy-via-recursion presents similar
problems and that these, like concurrency related bugs, are also very
difficult to diagnose and fix. I'll argue that they could be at least as
difficult (if not more) to find as concurrent-reentrancy bugs (which I
think is pretty uncontroversial) and that fixing them is often
non-trivial. (The discussion between Mark Miller and David Wagner
following his attack on a Mint (the second link above) proves this.)

Reentrancy via recursion is recognised as a primary source of "plan
interference" in E, which is why E provides eventual sends etc. The
"listener" pattern example from the paper on E's concurrency model
(http://www.erights.org/talks/promises/) makes this very clear. The
solution presented there is to use eventual sends to prevent this kind
of plan interference.

The natural question to ask then is whether the (implementations of the)
patterns that David Wagner broke could easily be made invulnerable to
reentrancy via recursion attacks by re-implementing them using eventual
sends to call untrusted objects.

I think the answer, in general, is "no" and that there are cases in
which the answer must be "no". I think the "brand" example (which I
prefer to call "Sealer-Unsealer" since my brain thinks that "brands" and
"trademarks" are the same thing) is such a case. The original code
(which David broke) rendered in E is:

def makeSealerUnsealer() {
  var flag := false;
  var squirrel := null;

  def seal(payload) {
      def box() {         
         squirrel := payload;
         flag := true;
      }
      return box
  }
  def unseal(box) {
      flag := false; squirrel := null;
      box();           // problem lies in this call
      if (!flag) {
        throw ...;
      }
      return squirrel;
  }
  return [seal, unseal]
}

The problem lies in the immediate-call to 'box' in 'unseal'.

We could modify it to use an eventual send instead, changing

box()
// etc.

to
when (box <- run()) -> {
   // etc.
}

'unseal' would now return a promise for the box contents that is
fulfilled later, after the box has divuleged its contents.

However, this has the following problem:

Suppose Alice has a real box and a fake box. She does

realbox <- run()
def p = unsealer(fakebox)
when (p) -> {
    // p could be the contents of realbox
}

Here, the unsealer will set 'flag = false' and 'squirrel = null'.
The eventual send to realbox might then be executed, setting 'squirrel =
payload' and 'flag = true'. The eventual send to fakebox might then run,
causing nothing to happen. The unsealer's promise for the eventual send
to fakebox will then be resolved causing the 'when' block to be
executed. At this point, the unsealer finds 'flag = true' and thus
returns the contents of 'realbox' incorrectly.


We're left with the possibility that these kinds of recursive-reentrancy
bugs are really nasty -- even more so than traditional
concurrent-reentrancy bugs since we have no good way to guard against
them in cases such as the above. 

I wonder, therefore, whether language features that restrict
recursive-reentrancy should be investigated, in the same way that
language features that prohibit concurrent-reentrancy have been to great
effect by the object-capability community. 

Is it fair, for example, in the two cases that David Wagner identified,
for the Unsealer and the Mint respectively, to mark themselves as "not
recursively invocable during this invocation" when invoking untrusted
objects? 

Would the addition of another invocation operator (on top of "." and
"<-") to E that means
"immediate-call-to-untrusted-object-that-shouldn't-be-able-to-recursively-call-me"
be fair? Being able to use such an operator would enable the programmer
not to have to worry about these kinds of bugs.

Alternatively, could E automatically support this restriction except for
those objects that have passed some guard (SafeForRecursiveInvocations),
perhaps.

How often is recursive-reentrant invocation actually required? Is it one
of those features that we could do away with in most cases?

I'd be interested to get others' thoughts here.

Cheers, and apologies for what turned out to be a very long message,

Toby