[E-Lang] Immutable map operations

[Mark S. Miller]

At 05:30 PM Sunday 4/1/01, hal@finney.org wrote:
>Isn't it risky to rely for security on the fact that an object will only
>respond to messages with particular names?  

Yes.

>It seems like this kind of
>problem could arise in other contexts.

True.

>I remember one of my concerns
>with the MintMaker code was that Assays and Purses responded to some of
>the same messages and in some contexts you could substitute one for the
>other, causing surprising results.  

An excellent example!

>Is this a serious problem, or can it be easily avoided?

In short, I'm not sure if it can be easily avoided, so for now it should be 
considered a serious problem.  Perhaps the serious problem.  This is the 
kind of issue that cries out for static (type-checking-like) security 
checking technology.  In the meantime, design rules help a lot, such as "No 
subtypes that add authority."

In long:

First, let's contrast E with a hypothetical capability secure variant of 
Java (which I'll refer to as "SafeJ").  This is essentially Java with all 
the parts that break capability security removed, and with the static type 
safety left in.  Even without doing much else, this is already pretty close 
to a usable programming language.  (The mission of Original-E was, among 
other things, to make that language usable.  Unfortunately, Javasoft stood 
in the way.  Btw, I've got safej.{com,org} in case we ever want to revive 
this effort.)

The above problem is somewhat worse in E than it would be in SafeJ, precisely 
because of an issue you allude to above: ".. messages with particular 
names".  In Java (and SafeJ), you only get dynamic polymorphism (runtime 
substitutability) according to message name as declared within declared 
types.  In E, it's just the message name.  SafeJ could prevent accidental 
polymorphism not prevented by E.

(Note: The taxonomy is actually a bit more complicated, as Joule is 
dynamically typed like E, but does polymorphism according to declared types 
like SafeJ, and it would prevent accidental polymorphism in the same sense 
that SafeJ would.  Btw, Joule's technique for doing this was inspired by 
Jonathan Rees' earlier language, T.)

Conventional static type declarations can help catch such bugs, but only 
imperfectly, and mostly not by preventing accidental polymorphism.  A common 
object programming practice in statically typed languages, especially under 
maintenance, is to provide the least specific (super-most) type that enables 
the program to compile without extra casts.  Besides being the least work, 
it leaves the program maximally reusable.

Under this practice, neither of these bugs (the BlobMaker and the MintMaker) 
would have been caught in SafeJ, as the problematic polymorphism was within 
the programmer's model of the types in his code, and therefore the types he 
probably would have declared.  Neither bug was due to accidental polymorphism.

Instead, the programmer should leverage the notion of types-as-contracts, 
and declare a specific enough type to express the contractual properties 
he's counting on.  If the BlobMaker were instead declared as

    def ConstList := <import:org.erights.e.elib.tables.ConstList> asType()

    class BlobMaker(list :ConstList) :any {
        def Blob {
            to get(index) :any { list[index] }
            to getStuff() :ConstList { list }
            .... list ...
        }
    }

either of these new ":ConstList" guards would have caught the problem.  
Likewise for a guard that simply insists on immutability.  (MarcS's 
suggested ":pbc", which stands for PassByConstruction, would have worked in 
this case, although pbc objects are necessarily immutable.  A ":PassByCopy" 
or ":immutable" guard would work, once we have such guards.)


                              Static vs Dynamic, SafeJ vs E


So E can express these constraints as well.  E has two weaknesses compared 
SafeJ:

1) The above accidental vs declared polymorphism issue.  Experience in 
dynamically types OO languages such as Smalltalk say this is more a problem 
in theory than in practice, but this question hasn't been examined in a 
security context.

2) Until we have a static type inference tool we can apply to E (elint), the 
Guard violation above will only be caught at runtime, whereas in SafeJ it 
might have been caught at compile time.  This creates a greater 
vulnerability to denial of service, but not other security problems.  (And E 
does not generally claim to enable resistance to denial of service.)

In compensation, E has some comparative strengths:

a) By being a runtime check, the guard can engage in arbitrary computation, 
and so check conditions infeasible to determine statically (like the range 
checks in the Ode's MintMaker).

b) In concert with auditors, guards can verify not only that an object's 
code alleges that it satisfies some contract, but that it actually does 
satisfy a (restricted category of) contract.  For the above case, since 
Alice and BlobMaker are on the same side, it probably would have been 
adequate for 'list' to allege itself to be immutable.  But for other 
situations, most notably confinement, you want the assurance from something 
you do trust (the ":confined" auditor/guard) that something you don't trust 
is confined.


                  Design Rules for Safer Capability Programming


Even without static security checkers, we can substantially reduce the 
danger by adopting certain design rules when designing our abstractions.  In 
a Joule context, I believe, Dean first coined "No subtypes that add 
authority."  The BlobMaker bug is directly due to my violation of that rule 
in designing E's collection classes: both FlexList and ConstList are 
subtypes of EList, and most of their protocol is defined up in EList.  The 
SafeJ/ELib programmer is in essentially as much danger from this bug 
as is the E programmer.

This design rule is in direct violation of OO conventional wisdom: If type B 
is fully conventionally upwards compatible from type A, then it's 
conventionally fine to make B a subtype of A.  The problem is that adding 
functionality is conventionally considered upwards compatible.  The type-as- 
contract is conventionally understood in terms of what the object must be 
able to do.  For security purposes, we need declarations-as-contracts that 
also say what the object must not be able to do.  The cost of this design 
rule is less polymorphism, and therefore less opportunities for reuse.  This 
is the only currently known issue for which good capability design conflicts 
with the conventional wisdom of good OO design.

The problem with conventional "upwards compatibility" occurs both across 
types and across versions.  A later version of a system may be 
conventionally upwards compatible with the earlier version, while doing new 
things that violate the *inabilities* other code was counting on. Like 
conventional type checking, conventional regression testing is powerless to 
detect these violations of required inabilities.  The corresponding 
versioning rule may be "Later versions should not both add authority and 
claim compatibility with earlier versions."

I don't think the polymorphism-abuse bug you found in the MintMaker would 
have been caught or fixed by the above design rule.  I have remained anxious 
to return to the analysis of that incident to try to understand more 
generally what the problem is, how we fell into it and, and what design 
practices and/or static security checkers would have helped.  It's a great 
example.


        Cheers,
        --MarkM