Jan 21, 2013 - Distributed Resilient Secure ECMAScript (Dr. SES)

Comments

This post is about a project I’ve been working on together with Mark Miller (with the help of many others) which we call “Dr. SES”, for Distributed Resilient Secure ECMAScript”. Dr. SES is a JavaScript extension aimed at secure, distributed computing.

Dr. SES extends JavaScript with three features:

  • SES: Dr. SES builds upon SES, the capability-secure subset of JavaScript. SES enables the safe execution of mobile code.
  • Q: To engage in distributed computing, we need abstractions to send messages to remote objects, and the Promise abstraction to more easily manage asynchronous computations. Mark has previously proposed some extensions to ECMAScript to achieve precisely this. Luckily we do not have to wait for these extensions to land. Except for some syntactic sugar, we can get most of the functionality today via Kris Kowal’s Q library.
  • Ken: Ken is a middleware that provides a persistent heap and reliable messaging between such persistent heaps. By integrating Ken with an existing JavaScript engine, we can achieve a JavaScript platform that persists across failures. One of my students is currently working on integrating Ken with the v8 engine, leading to an engine we call v8-ken.

Mark recently got invited as a speaker at ESOP 2013, and was given the opportunity to publish a paper to go along with the talk. The paper is probably the first written exposition of Dr. SES to date. It got published only recently, here’s a link to the pre-published version. The subject of the paper is not really about Dr. SES, but rather about what type of applications we can achieve on top of a platform such as Dr. SES. Nevertheless, Section 2 provides a good background on what Dr. SES ought to become. The paper is really a progress report, as Dr. SES is still very much a work in progress. Quoting the abstract of the paper:

Contracts enable mutually suspicious parties to cooperate safely through the exchange of rights. Smart contracts are programs whose behavior enforces the terms of the contract. This paper shows how such contracts can be specified elegantly and executed safely, given an appropriate distributed, secure, persistent, and ubiquitous computational fabric. JavaScript provides the ubiquity but must be significantly extended to deal with the other aspects. The first part of this paper is a progress report on our efforts to turn JavaScript into this fabric. To demonstrate the suitability of this design, we describe an escrow exchange contract implemented in 42 lines of JavaScript code.

The paper is based on two earlier talks of Mark:

  • Bringing Object-orientation to Security Programming (video, slides), which provides a good introduction to object-capabilities and the Purse example in particular.
  • Two-phase commit among strangers (slides, audio), which provides a general overview of Dr. SES (with a particular focus on Q) and of the escrow exchange contract, which is discussed in detail in the paper.

The source code discussed in the paper is available.

Jun 14, 2012 - A brief tour of JavaScript's object model

Comments

In this post I will give an overview of Javascript’s object model. To a first approximation, by “object model”, I mean the mental model that a developer has of an object’s structure and behavior. At the end, I will hint at how proxies can be used to implement (variations on) this object model in Javascript itself.

Objects as Maps

Let’s start with the simplest possible model most JS developers have of a Javascript object, and then refine as we go along. At its core, a Javascript object is nothing but a flexible bag of properties, which we can think of as a mapping from strings to values:

var point = {
  x: 0,
  y: 0
};

The point object maps the strings “x” and “y” to the value 0.

Javascript has a fairly large set of operations that one can apply to such maps, including the five basic operations applicable to most generic associative containers: property lookup (e.g. point.x), property addition (e.g. point.z = 0), property update (e.g. point.x = 1), property deletion (e.g. delete point.x;) and property query (e.g. “x” in point).

Method Properties

One of the beautiful parts of Javascript, I think, is that support for object “methods” doesn’t really require a change to this simple object model: in Javascript, a method is really nothing more than a property whose value happens to be a function. This is reflected in the syntax:

var point = {
  x: 0,
  y: 0,
  toString: function() { return this.x + "," + this.y; }
};

The method invocation point.toString() is essentially a lookup of the “toString” property in the object, followed by a function call that sets this to the receiver object and passes in the arguments: (point.toString).apply(point, []). So, we don’t need to adjust our object model to take methods and method invocations into account.

Prototype inheritance

The above object model is not complete: we know that Javascript objects also have a special “prototype” link that points to a parent object, from which the object may inherit additional properties. Objects created using the object literal syntax {…} inherit from the built-in Object.prototype object by default. For instance, our point object inherits from this object the built-in method hasOwnProperty, which allows us to ask whether the object defines a certain property:

point.hasOwnProperty("x") // true

The prototype link of an object can be obtained by calling Object.getPrototypeOf(point), although many browsers also simply represent the prototype link as a regular property of the object with the funny name proto.

I don’t like to think of the prototype link as a normal property because this link has a large influence on virtually every operation applied to a Javascript object. The prototype link is really special, and setting point.proto to another object has a very large effect on the subsequent behavior of the point object. So, I’d like to think of the prototype link as the next addition to our object model: a javascript object = a map of normal properties + a special prototype link.

Property attributes

The object model just described (objects as maps of strings -> values + a prototype link) is sufficiently accurate to describe user-defined objects in Ecmascript 3. However, Ecmascript 5 extends the Javascript object model with a number of new features, most notably property attributes, non-extensible objects and accessor properties. John Resig has a nice blog post on the subject. I’ll only briefly summarize the most salient features here.

Let’s start with property attributes. Basically, in ES5, every Javascript property is associated with three attributes, which are simply boolean flags indicating whether the property is:

  • writable: the property can be updated
  • enumerable: the property shows up in for-in loops
  • configurable: the property’s attributes can be updated

Property attributes can be queried and updated using the wordy ES5 built-ins Object.getOwnPropertyDescriptor and Object.defineProperty. For example:

Object.getOwnPropertyDescriptor(point, "x")
// returns {
//   value: 0,
//   writable: true,
//   enumerable: true,
//   configurable: true }
Object.defineProperty(point, "x", {
  value: 1,
  writable: false,
  enumerable: false,
  configurable: false
});

This turns “x” into a non-writable, non-configurable property, which is basically like a “final” field in Java. The objects returned by getOwnPropertyDescriptor and passed into defineProperty are collectively called property descriptors, since they describe the properties of objects.

So, in ES5, we need to adjust our object model so that Javascript objects are no longer simple mappings from strings to values but rather from strings to property descriptors.

Non-extensible objects

ES5 adds the ability to make objects non-extensible: after calling Object.preventExtensions(point), any attempt to add non-existent properties to the point object will fail. This is sometimes useful to protect objects used as external interfaces from inadvertent modifications by client objects. Once an object is made non-extensible, it will forever remain non-extensible.

To model extensibility, we need to extend the Javascript object model with a boolean flag that models whether or not the object is extensible. So now, a Javascript object = a mapping from strings to property descriptors + a prototype link + an extensibility flag.

Accessor properties

ES5 standardized the notion of “getters” and “setters”, i.e. computed properties. For instance, a point whose “y” coordinate is always equal to its “x” coordinate can be defined as follows:

function makeDiagonalPoint(x) {
  return {
    get x() { return x; },
    set x(v) { x = v; },
    get y() { return x; },
    set y(v) { x = v; }
  };
};

var dpoint = makeDiagonalPoint(0);
dpoint.x // 0
dpoint.y = 1
dpoint.x // 1

ES5 calls properties implemented using getters/setters accessor properties. By contrast, regular properties are called data properties. This point object has two accessor properties “x” and “y”. The property descriptor for an accessor property has a slightly different layout than that for a data property:

Object.getOwnPropertyDescriptor(dpoint, "x")
// returns {
//   get: function() { return x; },
//   set: function(v) { x = v; },
//   enumerable: true,
//   configurable: true
// }

Accessor property descriptors don’t have “value” and “writable” attributes. Instead, they have “get” and “set” attributes pointing to the respective getter/setter functions that are invoked when the property is accessed/updated. If a getter/setter function is missing, the corresponding “get”/”set” attribute is set to undefined. Accessing/updating an accessor property with an undefined getter/setter fails.

To accommodate accessor properties, we don’t need to further extend our object model, other than by noting that a Javascript object maps strings to property descriptors, which can now be either data or accessor property descriptors.

So, in conclusion, a Javascript object =

  • a mapping of strings to data or accessor property descriptors
    • a prototype link
    • an extensibility flag

This is an accurate model of user-defined ES5 objects.

Implementing your own objects

The object model described above can be thought of as the interface to a Javascript object. With the introduction of proxies in ES6, Javascript developers actually gain the power to implement this interface, and define their own objects. Not only could you emulate Javascript’s default object model in Javascript, you could define small variations to explore different object models.

Examples of such variations include Javascript objects with lazy property initialization, non-extractable or bound-only methods, objects with infinite properties, objects with multiple prototype links supporting multiple-inheritance, etc. There’s already some inspiration to be had on github, thanks to David Bruant and Brandon Benvie.

I recently gave a talk at ECOOP that explores these ideas in more detail. The talk builds up by describing Javascript’s object model, ties this up to the literature on meta-object protocols, and finally shows how Javascript’s Proxy API makes the Javascript meta-object protocol explicit for the first time, allowing developers to implement their own objects. Prototype implementations of proxies are currently available in Firefox and Chrome. To experiment with the latest version of the specified ES6 Proxy API, I recommend using the reflect.js shim.

May 7, 2012 - Proxies and Frozen Objects

Comments

This post is about how frozen Javascript objects interact with the upcoming Proxy API.

Since ECMAScript 5th edition, Javascript objects can be frozen. John Resig has a good blog post on the matter. To quote from his post:

Freezing an object is the ultimate form of lock-down. Once an object has been frozen it cannot be unfrozen - nor can it be tampered in any manner. This is the best way to make sure that your objects will stay exactly as you left them, indefinitely.

Once you call Object.freeze(obj) on an object obj, you have basically established two invariants on that object, i.e. properties of the object that will hold forever after:

  • The object becomes non-extensible: once frozen, you (or anyone else) can’t add any more properties to the object, ever.
  • All properties of the object become non-configurable: they can no longer be deleted, updated or have their attributes (like enumerability) changed in any way, ever.

I should note at this point that ECMAScript 5 has additional primitives to apply these invariants to just a subset of an object’s properties (Object.defineProperty), and also introduces the weaker notions of “non-extensible” and “sealed” objects (Object.preventExtensions, Object.seal). See John’s post for more details. Freezing an object is simply the most extreme type of lock-down you can apply to an object, and consequently involves the strongest invariants, so we’ll only focus on frozen objects here.

If you can establish that an object is frozen, i.e. Object.isFrozen(obj) === true, then you can count on the above invariants. For instance, if obj.x isn’t a getter (an “accessor property”), then you can count on the fact that obj.x is effectively a “constant” property: you can read its current value and cache it, knowing the cached value will always be correct.

With the introduction of proxies, an obvious question is whether and how proxies affect these invariants. Can proxies masquerade as frozen objects? And if yes, can they violate the associated invariants? The short answers are yes, and no.

Proxies: brief recap

I wrote earlier about how the Proxy API has undergone several revisions. Here, I’ll briefly introduce the latest revision of the API, called “direct proxies”. The Proxy API allows you to create a proxy for an object (which we will consistently refer to as the proxy’s “target”), as follows:

1
2
3
var target = {x:0,y:0}; // some existing object
var handler = {}; // the handler's methods are called "traps"
var proxy = Proxy(target, handler);

Here, proxy is a special proxy object that can intercept a number of Javascript operations. For instance, the in operator, when applied to a proxy: “x” in proxy, will trigger a corresponding “trap” in the proxy handler, and calls handler.has(target, “x”), which is supposed to return a boolean indicating whether the proxy has a property named “x”. If the trap is undefined, as in the above example, the proxy by default delegates the operation to the target, i.e. “x” in proxy is then interpreted as “x” in target.

Below is a schematic representation that shows the relationship between a proxy, a target and its handler. Proxies can intercept many operations, such as property access and assignment, property lookup, enumeration, and so on. On the left, we show a couple of operations applied to the proxy, and how the proxy interprets them by dispatching to the handler.

Proxy API</img>

In short, the proxy can fully customize the way it advertises its own properties to clients. In general, a proxy is not even obliged to return results that are consistent with its own target:

1
2
3
4
handler.has = function(target, name) { return false; }
"x" in target // returns true
"x" in proxy // returns false
proxy.x // returns 0

In the extreme, one can even create a proxy that totally ignores its target object for all operations. This is sometimes useful, e.g. the target could just be a dummy placeholder, and the proxy might represent a remote object (on the server or in a different web worker) or an object stored in a remote database.

Frozen Proxies

Back to frozen objects and proxies. Is it possible to create a frozen proxy? Yes: just create a proxy whose target is frozen:

1
2
3
4
var target = Object.freeze({ x: 0 });
var handler = {};
var proxy = Proxy(target, handler);
Object.isFrozen(proxy) // true!

However, now we’re in a potentially dangerous situation: depending on how the handler implements this proxy’s traps, it may return results that are inconsistent with its target, and may thus potentially violate the invariants of frozen objects. To prevent this, the Proxy API includes an invariant enforcement mechanism, which is simply a series of assertions on the behavior of a proxy handler. If one of the proxy handler’s traps returns a result that is inconsistent with the fact that its target is frozen, an assertion will fail and cause an exception to be thrown, thus notifying clients of the proxy’s misbehavior.

Continuing with the previous example, assume a client of the proxy observes the “x” property:

proxy.x // 0

The handler does not define a “get” trap, so the proxy simply forwards the property access to the (frozen) target, and returns 0. Now, assume that the handler is updated as follows:

handler.get = function(target, name) {
  return 1;
}

Let’s see what happens when we try to access properties on the proxy:

proxy.foo // returns 1, so far so good...
proxy.x // TypeError: cannot report inconsistent value for non-writable, non-configurable property 'x' 

When you encounter such an exception, what Javascript is really telling you is:

Son, this proxy is writing cheques its target can’t cash!

Seriously: proxy.x fails because the proxy knows that target is frozen, and has a property named “x” which is bound to the value 0. It cannot now let the proxy claim that proxy.x is 1, while it returned 0 just a while ago. After all, the proxy is supposedly frozen, and frozen objects wouldn’t exhibit such behavior. In this example, the “get” trap always returns 1, which on the surface seems OK for frozen objects, but in general the “get” trap may return a different value each time it’s called. The proxy instead detects such inconsistencies, and throws.

Since frozen objects are supposedly non-extensible, why is the proxy allowed to report a value for a “foo” property, while the frozen target doesn’t have such a property? The answer has to do with prototypal inheritance: a frozen object can still inherit from a non-frozen object, which may define a “foo”:

1
2
3
4
5
6
var parent = {} ; // note: parent isn't frozen
var child = Object.create(parent); // child inherits from parent
Object.freeze(child);
child.foo // undefined
parent.foo = 1;
child.foo // 1

In the above example, the expression child.foo returned different values even though child is frozen. This is why the above proxy was allowed to return a value for “foo”, even though that property wasn’t defined on the target. The proxy won’t verify whether the target actually inherits from a non-frozen object that has a “foo”, but just assumes that this is possible.

Matters are different if the proxy actually tries to advertise “foo” as an “own” property (i.e. a property defined on the proxy itself, not inherited from some other object):

1
2
3
4
Object.keys(proxy);  // [ "x" ]
handler.keys = function(target) { return [ "x", "foo" ]; };
Object.keys(target); // [ "x" ]
Object.keys(proxy)  // TypeError: keys trap cannot list a new property 'foo' on a non-extensible object

What’s going on here? Object.keys, new since ES5, lists all of an object’s own, enumerable properties. When applied to the proxy, it invokes the handler’s “keys” trap, which should return an array of strings. On line 1, the proxy handler doesn’t yet define a “keys” trap, so just forwards the call to Object.keys to the target, returning the array [“x”]. On line 2, the handler installs a “keys” trap that claims both “x” and “foo” as own properties of the (frozen) proxy. On line 4, the program throws an exception. It would be wrong for Object.keys(proxy) on line 4 to return “foo” in the list of own properties since doing so would violate the invariants of frozen objects. After all, on line 1, the “foo” property was not present, and proxy was supposedly frozen, so clients would be very surprised if later, they noticed proxy had a new property!

Try it yourself

At the time of writing, direct proxies are being prototyped in Firefox. I wrote a little shim that already implements the most recent API in terms of an older revision that is already available since Firefox 4. Just include this script in your page and you’re ready to play around with direct proxies (tested in Firefox 12). This is work-in-progress, so any feedback is more than welcome.

Mar 29, 2012 - Membranes in JavaScript

Comments

Membranes are a powerful new feature enabled by Javascript proxies, with various use cases. The goal of a membrane is to fully isolate two object graphs. Before I can dive into more practical applications of membranes, I need to explain what a membrane is in more detail, so bear with me.

What is a membrane?

A membrane is a wrapper around an entire object graph, as opposed to a wrapper for just a single object. Typically, the creator of a membrane starts out wrapping just a single object in a membrane. The key idea is that any object reference that crosses the membrane is itself transitively wrapped in the same membrane. Object references typically cross the membrane in one direction (out->in) by passing parameters to an object’s method, and in the opposite direction (in->out) by being returned as a value from a method or by being thrown as an exception.

To ease speaking about membranes, I will use the term “wet objects” for objects that live inside of the membrane, and the term “dry objects” to refer to objects that live outside of the membrane. The key thing about membranes is that they convert any outbound reference to a wet object that crosses them into a proxy, which is a dry object representing the corresponding wet object on the other side of the membrane. Similarly, the membrane converts any inbound dry object reference into a proxy which is a wet object that represents the corresponding dry object on the other side of the membrane.

Here’s a simple example of how a membrane can be constructed:

var wetB = { y: 0 }
var wetA = { x: wetB }
var dryA = makeMembrane(wetA)

So now, dryA is a proxy to the corresponding wetA object. Once a dry wrapper like dryA is created, it is possible for clients to navigate transparently through the wrapped object graph via the dry wrapper, yet never getting a direct reference to the wet objects:

var dryB = dryA.x

Now, dryB is a wrapper for the corresponding wetB object. Typically, primitives are passed through the membrane unwrapped:

dryB.y === 0

After executing all this code, we end up with the following object graph:

Membrane 1</img>

The full circles represent regular Javascript objects, the half-circles represent proxies. Now, if we want to add references in the other direction, we’ll need to add a method to one of our wet objects:

wetA.m = function(wetC) { var wetD = { z: wetC }; return wetD; }

If the outside (dry) world now passes in a dry object to m, the membrane will receive a wrapped version instead:

var dryC = {};
var dryD = dryA.m(dryC);

And we end up with the following object graph:

Membrane 2</img>

Revocable Membranes

This is all fine, but why is it useful? A membrane provides its creator with the power to intervene whenever a reference crosses the membrane (either in->out or out->in). One simple use case is for instance to install a kill-switch on the membrane: while the switch has not yet been triggered, all the wrappers belonging to the same membrane do nothing but transparently and dutifully forwarding all operations to their corresponding targets on the other side of the membrane. However, once the kill-switch is triggered, these wrappers instantaneously stop forwarding, drop the reference to their target, and will complain whenever clients still try to access their target. In effect, the membrane has hermetically sealed off its wrapped object graph from the world outside it: clients that only have membrane-wrapped references will hold on to nothing but useless pointers. After revocation, we are left with the following object graph:

Membrane 3</img>

Such membranes are called “revocable” membranes, and triggering the kill-switch is also called “revoking” the membrane. Revocable membranes are useful to exercise the principle of least authority in application design: module A may only want to provide module B with access to its objects for a limited amount of time. A can thus wrap its objects in a membrane, pass the wrapped version to B, and when A (the rightful owner of the objects) decides that B no longer has the right to access its objects, it revokes the membrane.

Revocable membranes require a slightly updated API: when we create a new revocable membrane, we don’t get back just the wrapped object, but also a revoke() function that we can call to trigger the kill-switch:

var wetB = { y: 0 }
var wetA = { x: wetB }
var membrane = makeMembrane(wetA)
var dryA = membrane.wrapper
var revoke = membrane.revoke
// by the way, destructuring in ES6 will turn the above 3 lines
// into the following pleasant one-liner:
// let { wrapper: dryA, revoke } = makeMembrane(wetA)

Again, a client object receiving only dryA can make use of the object as if it was the wetA object: the membrane will dutifully mimic the corresponding object inside of the membrane:

var dryB = dryA.x
dryB.y // returns 0

But now for the interesting part: the moment the membrane creator calls revoke, clients with access to dryA or dryB only lose all ability to continue using these objects:

// membrane creator calls:
revoke();
// in client code:
dryA.x // error: membrane was revoked
dryB.y // error: membrane was revoked

Of course, if some code has access to both the original wetA and the wrapped dryA, then that code can still continue using the wetA object (but not via the revoked dryA reference). Often when using membranes, the code will arrange for the original wrapped objects to be well encapsulated (perhaps hidden within the scope of a closure) so that clients can only ever get wrapped references to it.

How are membranes implemented?

I will not go into full detail in this post, but let me just mention a couple of points.

Naturally, membranes require Harmony proxies in order to implement the transparent wrappers. Until the new direct proxies API lands, I have been experimenting with membranes using my DirectProxies.js shim, which implements the new direct proxies API in terms of the older one.

Perhaps surprisingly, proper membranes also require WeakMaps, another Harmony feature (the one-line summary is that WeakMaps are like object-identity-keyed hashtables that hold on to their key weakly, ideal for building caches). Membranes need WeakMaps for two reasons: first, to preserve object identity across the membrane. Consider the following:

var dryB = dryA.x
var dryB2 = dryA.x
// dryB === dryB2 ?

We would like the answer to this question to be yes. In other words: a membrane should cache whatever wrapper it creates for wetB and consistently return the same wrapper whenever wetB crosses the membrane (in this case, by being accessed via wetA’s x property).

The second reason is more subtle and has to do with preserving object identity on either side of the membrane. Consider the following:

wetA.test = function(x) { return x === wetB; }
dryA.test(dryB) // returns true or false?

Here, again, we would expect true to be returned. For this to happen, however, when dryB (which is an in->out wrapper for wetB) crosses the membrane (in the out->in direction), we want the x parameter to be bound to the original wetB object, i.e. we want the membrane wrapper to be automatically unwrapped. Again, the membrane implementation needs WeakMaps to be able to distinguish and unwrap its own wrappers. The same kind of unwrapping is needed in the other direction (in->out):

wetA.identity = function(x) { return x; }
var result = dryA.identity(dryC);
// result === dryC? yes!

My current experimental version of membranes doesn’t uphold identity yet, but a sketch of how it would work using the old proxy API is still available here. Update: a membrane implementation using the latest direct proxies API, which upholds object identity across both sides of the membrane, is available here.

Only scratching the surface…

Revocable membranes only scratch the surface of what membranes can support. Often one can think of the wet objects inside of the membrane as some precious resource needing protection. But one can think of opposite use cases as well, where the dry outside world wants to be protected from the wet objects inside of the membrane. For instance, Mark Miller (designer of the Caja secure subset of Javascript) came up with the idea of wrapping (a secure version of) the Javascript eval function in a membrane so that any untrusted third-party code eval-ed with this wrapped eval function is born inside of a membrane: any references that code ever establishes to the outside environment would be wrapped. When the untrusted third-party code is no longer needed or wanted, the membrane can be revoked. Not only does this render the third-party code harmless (it no longer has access to anything in the enclosing environment), if the membrane is carefully implemented and the Javascript engine fully supports WeakMaps, then the GC can recognize that the membraned object graph is now fully isolated, and can be garbage-collected.

Feb 16, 2012 - Operational Semantics of AmbientTalk

Comments

Together with PhD students Christophe Scholliers and Dries Harnie, I recently completed an operational semantics of our AmbientTalk programming language. We believe this is the first formal account of an actor language based on communicating event loops. The paper is currently available as a techreport. From the abstract:

We present an operational semantics of a key subset of the AmbientTalk programming language, AT-Lite. The subset focuses on its support for asynchronous, event-driven programming. AmbientTalk is a concurrent and distributed language that implements the so-called communicating event loops model.

Christophe has written an executable version of the operational semantics in PLT Redex. You can read all about that here.

The operational semantics builds on that of a similar model, JCobox, but significantly adapts it to more accurately reflect the semantics of AmbientTalk’s futures, which are based on E’s promises and are entirely non-blocking. And unlike JCoBox, AmbientTalk does not support cooperative multitasking within an actor, only purely sequential, run-to-completion execution of incoming messages, much like a Javascript per-frame event loop.