The Wrapper Conundrum

In my information flow research, we have the objective of attaching a security label to every object/value within the running system of a JavaScript VM. Two approaches are immediately evident:

1. Fat Values. We can extend the native encoding of values to include a pointer to the label attached to that value. In JS, this means that we’d have to have, at minimum, a 64-bit representation. Both Spidermonkey and Webkit currently use a 64-bit representation, so we’d have to modify the encoding to account for the label pointer. Performing this modification on such a low-level aspect of a VM is not a trivial undertaking, as it will affect many places.
2. Cloaks (aka. labeled wrappers/proxies). We can also implement the labeling, by wrapping each object/value inside another object, whose sole purpose is to carry the label. At first glance, we would expect fewer modifications to be made to the underlying VM, as this only requires the introduction of a new wrapper/proxy class. The difficulty lies in making the wrapper as transparent as possible, it should not be evident (to the JS programmer) that all values are suddenly wrapped up inside labeling objects.

Let’s throw the first curveball that can let us distinguish between these two choices: primitives. In basically all implementations of JavaScript, primitive values are encoded (via tag bits) into a plain old data type. Evidence of this implementation detail occasionally leaks into view of the JavaScript programmer; Early 32bit implementations would auto-convert any integer which could not be represented in 31bits to a double. From an implementers perspective, having primitives makes operations on common types fast, at the cost of introducing some extra special-case logic for each primitive type. Unfortunately, this logic disperses itself across the entire VM.

To give real support to information flow, we will have to come up with a way of tagging both primitives and objects. Primitives represent a challenge because all of their bits are already in use, there simply isn’t any room to add a label pointer to the data payload. It is possible to create such room by changing the way in which primitives are encoded (as introduced in the fat value approach), but comes at a high cost, because it potentially changes the logic all over the system. Still, there remains a distinct advantage: all datatypes have their label directly attached to their representation (encoded into the payload). Taking this approach it would, with a large amount of engineering effort, be possible to give a labeled, 32bit implementation of JavaScript using a 64bit internal datatype.

Alternatively, we could avoid the cost of changing the data representation at the lowest level, and instead wrap each primitive with an object. Objects can be modified to hold a label in addition to all the other special fields (parent, prototype, etc). This field naturally labels the object, and its contents. To label a primitive, we simply stuff it, and the corresponding label, into a special wrapper class. Clearly, this will make some operations slower, because there will be a layer of indirection when the primitive value is unpacked prior to use.

During implementation, we discovered yet more difficulties that arise when cloaking primitives. There are many places within the VM that expect and require primitive values (such as the length field of an Array). Furthermore, when a wrapped class leaves the VM (other code is allowed to use JavaScript as a client) that code can become confused if the resulting class, a cloak, doesn’t match what was expected. That is, external code has many assumptions that it will get back a specific type, and cloaking breaks those assumptions.

In order to have success with the cloaking approach, we have to be able to introduce a new class into the VM, and keep it transparent at both the JavaScript and the VM levels. That is, we don’t want any JavaScript code to become aware that a primitive has been wrapped with an object (for example, attempting to set properties should be ignored) nor do we want the VM to become too aware, because that will require special case-logic it too many places. I’ve concluded that solving both of these constraints is nigh impossible. For example, let’s take the result of the typeof operator. In order to maintain transparency at the JS level, the cloak will have to lie about its type. A cloaked integer should return “number” and not “object”. However, the cloak can’t simply return the result of a dispatched call to typeof in every case, because that interferes with many places inside the VM that a switch-case decides what to do based on the type of an internal value. A jsvalue that encodes an object reference, yet returns “number” when type inspected confuses the logic of the VM.

There is also a strong semantic difference between the two approaches. When using fat values, the label is attached to data when the value is a primitive, and object references when the value is an object (or interned double). When using cloaks the label is attached only to objects themselves. I haven’t fully explored the difference between having a labeled reference vs having a labeled object, but I think the difference is analogous to having an Access Control Listing by columns vs Object Capabilities by rows, as discussed in Capability Myths Demolished.

At this point I am in favor of the fat value approach, because I’m liking the reference semantics, and the transparency with which primitives can be labeled. I’m also willing to accept the cost of having fatter values.

Now for the second curveball: How would you label interned objects? This primarily comes out of Java, but JavaScript does the same thing. With Java, interned objects have an abstraction leak at the == operator. For example, in Java:

Integer x = 5;
Integer y = 5;
Integer a = 10000;
Integer b = 10000;
System.out.println("Integer(5) == Integer(5)? " + (x==y));
System.out.println("Integer(10000) == Integer(10000)? " + (a == b));
 
---------
Integer(5) == Integer(5)? true
Integer(10000) == Integer(10000)? false

What amounts to an optimization, actually hurts our attempts at security. How should we label what are conceptually two different objects, based on their use in the code, if the VM wishes to intern them at the same location? I think it’s pretty clear, that having the objects contain their own labels will run us into trouble. Of course, it’s possible to wrap interned objects with a cloak, but I think it would be difficult to decide that an object (as opposed to a primitive) should be wrapped. Essentially, such a wrapper would amount to a labeled reference: exactly what the fat value approach already provides.

In my reading of information flow security, so far, I’ve yet to see anyone that is discussing these kinds of implementation details. Many papers invent some ideal (tiny) language, then performs a proof of non-interference for that language. Without a means for translating real-world languages (with prototype chains, dynamic field lookup, generators, co-routines, exceptions, continuations, etc.) into that ideal model, we haven’t made progress. Other papers tackle a subset of the real language, and claim that the approach extends to the full language; after trying to implement this stuff myself, I seriously doubt this claim. Many language features just don’t play well together, and can seriously upset some of the hidden assumptions that allow a proof of safety for the subset to be constructed.