[e-lang] A broken brand?

Mark Miller erights at gmail.com
Mon Mar 3 05:30:49 EST 2008


On Sat, Mar 1, 2008 at 11:38 PM, David Wagner <daw at cs.berkeley.edu> wrote:
> I've been reading the Caja spec.  It includes an example of a brand
>  implemented in Caja, using an implementation technique attributed to
>  Marc Stiegler.  I think I may have found an attack on it, and I was
>  curious whether this was well-known.  I'll re-print the Caja code:
>
>  function Brand() {
>   var flag = false;
>   var squirrel = null;
>
>   return caja.freeze({
>     seal: function(payload) {
>       function box() {
>          squirrel = payload;
>          flag = true;
>       }
>       box.toString = function() {
>         return "(box)";
>       }

That last "}" should be

        };
        return box;
      },


>     unseal: function(box) {
>       flag = false; squirrel = null;
>       box();
>       if (!flag) {
>         throw ...;
>       }
>       return squirrel;
>     }
>   });
>  }
>



>  It seems the problem is that the brand above is not safe in the
>  presence of re-entrant calls.  Put another way, it is subject to "plan
>  interference", to borrow MarkM's term.  It doesn't look too difficult to
>  modify the brand to defend against the above attack (e.g., by resetting
>  flag to false and squirrel to null before unseal() returns), although
>  I haven't checked whether there are any other attacks.
>
>  Does this attack look correct to you?

Yes.


> Is it well-known?

It is not. I no longer remember precisely what MarcS' original did,
but I'm sure we can find it in the archives. Interestingly, I have
seen versions of this same technique which set the flag to false
*only* after calling box. I was able to successfully attack those by
using a box that throws an exception, leaving the flag set. Might your
proposed fix still be vulnerable to this attack? Would

    try {
       box();
       if (!flag) { throw ...; }
       return squirrel;
    } finally {
       flag := false
    }

be necessary or sufficient?


>  P.S. How did I find the attack?  I used trust analysis (aka taint
>  analysis).  For each security perimeter (e.g., each function), you treat
>  the data flowing across that security parameter (e.g., the arguments to
>  that function) as untrusted.  All of the fields/properties of an untrusted
>  object are themselves untrusted.  Invoking an untrusted object gives the
>  attacker a chance to run code; the return value from such an invocation
>  is itself untrusted.

Would not have helped me find it. I already knew to be worried about
exactly these issues, and about plan interference attacks.
Depressingly, none of the following tools would have helped:

a) conventional static type checking
b) auditing (either E or Joe-E style)
c) those fancy type systems I'm aware of, such as effects types and
ownership types
d) tainting analysis - since the correct code would have looked
equally suspicious
e) runtime contract/assert checking
f) coverage checking

I'd be curious if Fred's SCOLL system or Toby's CSP-based authority
analysis frameworks would have been able to catch this.

I wonder how likely we would have been to find this by fuzz testing.


Altogether, between this and your attack on the Cajita Mint, it's
clear we need better tools for this kind of programming to become
adequately robust. (Not that there's any known better alternative.)
Between auditors, SCOLL, and Toby's work, I figured we were advancing
towards having such tools. Now I'm not so sure.

Btw, Ping's branding pattern at
<http://www.erights.org/elang/kernel/auditors/> relies on trademarking
rather than side effects, and doesn't have these vulnerabilities:

def makeBrand() :any {
    def key { }
    interface s {}
    def sealer {
        to seal(contents) :any {
            def envelope implements s {
                to open(k) :any {
                    if (k == key) {
                        return contents
                    }
                }
            }
            return envelope
        }
    }
    def unsealer {
        to unseal(env :s) :any {
            return env.open(key)
        }
    }
    return [sealer, unsealer]
}

Cajita doesn't yet have trademarking, though Mike Stay has a prototype
implementation. Perhaps this should raise the priority of adding
trademarking to Cajita?

-- 
Text by me above is hereby placed in the public domain

    Cheers,
    --MarkM


More information about the e-lang mailing list