[cap-talk] Recursive Reentrant Invocation (was: Re: Tamed Pict)

Toby Murray toby.murray at comlab.ox.ac.uk
Wed Mar 4 13:32:38 EST 2009

On Wed, 2009-03-04 at 19:10 +0100, Matej Kosik wrote:
> Toby Murray wrote:
> > I need to think harder to work out whether Pict's derived forms for
> > recursive functions allow you to write recursively reentrant code (see
> > http://mail.eros-os.org/pipermail/e-lang/2009-February/013002.html for
> > more on what I mean here).
> I cannot give you sure answer because I do not exactly understand what
> problem you discussed there. In this paragraph:
> "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."
> What do you mean by "While calling the untrusted code, o can be
> invoked recursively." ? What do you mean by "recursively"? Who could
> invoke object o "recursively"?

Thinking just in terms of E (although hopefully it will translate easily
to other languages too), let's say have an object o defined as follows.

def o {

   to foo(obj) {
   to baz() {
        return null
o has two methods: foo(obj) and baz(). Calling o.foo(obj) causes o to
call obj.bar(). Calling o.baz() causes o to return null.

Now suppose we have another object, weird:

def weird {
    to go() {
    to bar() {

And suppose we run

What happens (view the following in a fixed-width font)?
weird.go() calls o.foo(weird),
                 o.foo(weird) calls weird.bar(),
                                    weird.bar() calls o.baz(),
                                                      o.baz() returns,
                                    weird.bar() returns,
                  o.foo(weird) returns,
weird.go() returns,

The call-stack for the single thread that is executing all of the above
grows from left-to-right.

We can see that object o gets recursively invoked.

This recursive invocation can cause problems because it might change
local variables that o doesn't expect to change. 



More information about the cap-talk mailing list