kindConstructor vs GC sensitivity vs non-metered deserialization

[warner]

What is the Problem Being Solved?

In #3458 we draw up a plan to isolate any GC-sensitive code paths within liveslots in an "unmetered box", to prevent variations in GC timing getting amplified into variance of metering results. @erights raised an important question today: can the userspace "kind constructor", used to regenerate new Representative Objects for virtual objects, be used to violate determinism?

The kind constructor might be invoked any time we deserialize a virtual-object vref. We specifically allow the Representative to be GCed when the JS heap no longer needs it, but retain the ability to make a new one when needed (thus we say the vref identifies an abstract "virtual" object rather than a single concrete Remotable). To make === work (#1968) it is important to have at most one Representative for the virtual object at a time. If determinism were not a consideration, we would simply use a Map of WeakRefs, with a FinalizationRegistry to remove lost Representatives (and this is exactly what liveslots does).

But we have two additional concerns:

• deterministic behavior that is independent of the timing of GC (and therefore the UNREACHABLE-vs-COLLECTED-vs-FINALIZED status of the Representative object)
• deterministic metering results

We decided long ago to withhold WeakRef and FinalizationRegistry from userspace code, so they can't be used to probe the status of arbitrary objects (and thus learn when GC or finalization happens). The involvement of userspace code in the kind constructor makes the task more difficult. @FUDCo and I identified several requirements to support the first concern:

• The sequence of vatStore (get/set/delete) syscalls must not depend upon the GC status.
• Userspace must not be able to tell whether the act of deserialization is able to re-use an existing Representative or has to construct a new one.

To meet these requirements, we made two big changes. First we made the virtual objects perform their vatStore reads at property getter time rather than when the Representative is created. The sequence of property reads (i.e. getter invocation) is deterministic, but the act of creating a Representative might not be. This hurts performance, because we'd really prefer to read the data just once and leave it in RAM, but every syscall.vatStoreRead goes into the transcript, and the transcripts must be consistent across validators. (And unlike syscall.dropImports, we can't strip them from the transcript, because they have critical return values, and the transcript is the only place to record that information for use during replay).

The second was to change the deserialization code to always call the kind constructor, even if there's already a Representative, so that userspace cannot simply count the number of constructor invocations and thus sense the GC state. If the Representative already existed, we discard the newly-constructed one. The act of deseralization is deterministic: it occurs at top-of-crank (on the arguments of a dispatch.deliver or the resolution data of a dispatch.notify), and mid-crank when a virtual object property lookup or virtual weak store value read causes virtualized data to be deserialized. So the number of kind constructor invocations is deterministic. This also hurts performance, because obviously we'd rather only call the kind constructor when really necessary, but we concluded the extra calls were necessary to prevent GC-based nondeterminism from leaking into userspace.

@FUDCo and I spent a bunch of time studying that pathway and decided that userspace could not tell whether their earlier Representative has been collected or not. They don't have WeakRef, and the WeakMap/WeakSet they get is vref-aware, so the only tool they can use is === against a previously-held object. If they're able to ask that question, the answer will always be false (i.e. the one they just created is different than the one they'd held onto from before), meaning their new one will be discarded. The only time the new Representative is used is if the previous one had been collected, and for that to happen, userspace must not be able to ask the === question, so they can't sense the answer.

I believe we also studied the state object closed over by the kind constructors "behavior" function and were satisfied that it couldn't help either (I think maybe each call gets a brand new state object).

The concern that @erights highlighted is that our new desire to maintain deterministic metering results while still tolerating GC timing variations might be threatened by the inclusion of userspace code in the liveslots deserialization pathway. Our plan (#3458) requires us to exclude the GC-sensitive code pathways within liveslots from metering, by disabling metering just before and reenabling it just after. Basically any code that touches a WeakRef or might call a finalizer must be unmetered.

But the userspace kind constructor gets called during deserialization of virtual-object -bearing capdata. And in particular the object created by that constructor will be used or discarded depending upon the GC state, and userspace isn't obligated to produce identically-behaving objects each time.

I think the basic attack would look like:

let counter = 0;

function makeFoo(state) {
  counter += 1;
  function init() {}
  function fast() {}
  function slow() { for (;;) {} }
  const self = Far('foo', {
    bar: counter < 5 ? fast : slow,
  });
  return { init, self };
}

The first few times the kind constructor is called, it produces a Representative whose .bar() method runs quickly. After that, bar() causes an infinite loop (which will cause a metering fault, although a more subtle attack would delay discovery by making a less drastic difference in meter consumption). The timing of GC determines which of these instances gets used later, and the invocation of .bar() by other userspace code must clearly be subject to metering.

In writing this up, I'm realizing that maybe this ability to change behavior on a construction-by-construction basis already violates our belief that userspace cannot distinguish between the "real" and "fake" constructor invocations, and the potential metering variation is just adding one fire to the existing pile of fire.

Userspace must not be able to sense GC timing at all: even if GC happens at the same time across all validators, knowing when it happens would reveal information about other objects within the same vat, which would (noisily) violate confidentiality within the ocap model. Liveslots is allowed to sense GC (and must, to support distributed GC), but we think we want to rely upon liveslots to not leak this GC timing into the metering results and thus validator consensus.

We need to study this more carefully. The fallback is to make GC timing deterministic, so that there is no variation to influence metering results and consensus. But that wouldn't be sufficient to protect the intra-vat confidentiality property.

Security Considerations

Violations of intra-vat inter-object confidentiality.

Consensus failures provoked by local variations in GC timing, leaking into metering results, leaking into "how many cranks go into each block" runPolicy decisions (#3460).

[warner]

I hate to suggest it, but maybe the answer is to abandon the "objects as closures" pattern and use .prototype instead. makeKind() would be called with an object to use as the Representative's prototype, created exactly once, and its methods would reference this to get access to the instance's unique state. I've never been entirely comfortable with this, and I'm a Python guy, so I'd also be ok with defining all the behavior methods to take an extra initial self argument and put the state on that, but I can't imagine any native JS programmer accepting that route.

A more drastic approach that might work would be to create Representatives with state (serializable properties) but without behavior. Or maybe makeKind takes a delegate function handle(representative, methodName, ...args) and a list of method names, and the Representatives are created with methods that forward/dispatch/delegate to that function. Or makeKind takes an object with methods foo(representative, ..args) and each Representative forwards to that, which is just a rearrangement of the .prototype plus (self, ...args) idea above.

The key thing is to not involve userspace in the creation (or re-use) of a Representative, and make that exclusively the job of liveslots (just like it does for Presences).

[zarutian]

A more drastic approach that might work would be to create Representatives with state (serializable properties) but without behavior. Or maybe makeKind takes a delegate function handle(representative, methodName, ...args) and a list of method names, and the Representatives are created with methods that forward/dispatch/delegate to that function. Or makeKind takes an object with methods foo(representative, ..args) and each Representative forwards to that, which is just a rearrangement of the .prototype plus (self, ...args) idea above.

I like that idea but I recommend that representatives be opaque/encapsulated elsewhere than in invocations to that handler function/object.
Heck, it would be much easier if the handler function hand signiture akin to handler(representative, state, methodName, ...args).
Then the representitive can be an opaque handle object while the state of the virtual object lives on the state object.
Now, it is question about the initialization of such virtual objects.
Perhaps makeKind takes two functions as arguments, the aforesaid handler and an init function with the siginture init(representative, state, ...initArgs). initArgs would be whatever the constructor function that makeKind returned gets called with.

This basically splits up the three aspects of usual objects into distinct parts.
The three aspects? object idenitity, state, and behaviour.
Temp object identity is handled by the representitives.
Object behaviour is handled by the handler function.
And object state is handled by the state object.

[warner]

For reference, here's how Payments were defined until @katelynsills recently reverted them (#3357) to be regular Remotables:

export const makePaymentMaker = (allegedName, brand) => {
  const paymentVOFactory = () => {
    return {
      init: () => {},
      self: Far(`${allegedName} payment`, {
        getAllegedBrand: () => brand,
      }),
    };
  };
  const makePayment = makeKind(paymentVOFactory);
  return makePayment;
};

[warner]

In today's kernel meeting, we decided the core problem is the kind constructor's ability to mutate state when called. The kind constructor is shaped like this:

function makeThingInstance(state) { // called at least once for each Representative
  // <- opportunity for mutation!
  function init(args) { // called once per virtual object
  }
  const self = Far('interfacename', {
    behaviorMethod() { // called once per rep.foo() invocation
      // closes over state or external things
    },
  });
  return { init, self };
}
const thingMaker = makeKind(makeThingInstance);

The problem is that "opportunity" area, outside of init (which is called at a GC-independent time) and outside of all behavior methods (also called at GC-independent times). We need to prevent any code from running at that level which might interact with external (-to-the-constructor) mutable state.

We thought of two approaches. The first is to give up on the "objects as closures" pattern by recasting the kind constructor in a more declarative fashion. We can imagine moving the behavior into a single object, which gets its uniqueness from arguments or an implicit this parameter rather than closing over something. The tricky part is where should the state and/or identity go? My very python-inspired example looked like:

const balances = new WeakMap();

function initThing(state, name) {
  state.name = name;
}
const thingInterfaceName = 'thing';
const thingBehavior = {
  getName(self, state) { return state.name; },
  rename(self, state, newName) { state.name = newName; },
  getBalance(self, state) { return balances.get(self); },
}
const thingMaker = makeKind(initThing, thingInterfaceName, thingBehavior);

We could make it one step closer to traditional JS objects by using an implicit this instead of a self argument:

const thingBehavior = {
  getName(state) { return state.name; },
  rename(state, newName) { state.name = newName; },
  getBalance(state) { return balances.get(this); },
}

We must probably keep state separate to make sure behavior code can access it without exposing it to the outside world as properties on .this, and to allow the contents to be virtualized, but another option would be to force all state to live in external virtualized stores:

const names = makeVirtualWeakStore();
const balances = makeVirtualWeakStore();

function initThing(self, name) {
  names.set(self, name);
}
const thingBehavior = {
  getName() { return names.get(this); },
  rename(newName) { names.set(this, newName); },
  getBalance() { return balances.get(this); },
}

The second approach is to keep using the objects-as-closures pattern, but enforce source-code restrictions on the kind constructor. @erights thinks it wouldn't be hard to make an AST-based parser/scanner to reject kind constructors that deviate from a tightly-limited pattern. The constructor would look exactly like our original, but makeKind would be invoked with source code and a set of endowments, instead of the function object:

const thingMaker = makeKind(`${makeThingInstance}`, { balances });

and the first thing makeKind does is to subject the kind-constructor source code to the AST parser. It would reject any function that had code between the opening { and the definition of init, or between init and the definition of self, or any properties in the second argument of Far that were not functions, or any code after Far and before the trailing return { init, self };. Basically any code that might possibly execute during the invocation of the kind constructor would be forbidden. Then, if the source passed these requirements, it would be evaluated in a new Compartment with endowments in scope, and the result used when making new instances and Representatives.

To simplify the scanner, we'd require kind constructors to be written in Jessie, which we know we can parse without the full power of something like Babel (which we really don't want to drag into the vat).

We concluded that we can put off fixing this for a while, because it won't be an issue until we reach adversarial contract code. We'll continue to write our kind constructors in the existing style, and document that as the preferred approach, and then later we can make it mandatory by changing the makeKind() invocation to take source code.

[mhofman]

Thanks for writing this down. Regarding the first approach, a few things we should clarify:

• The representative object would have to be constructed without touching any user code for this pattern to work. If the virtual object representative needs to be internally marked with Far after construction, wouldn't that qualify as user code executing, or do we consider Far to be trusted? I'm actually unsure what making a representative Far means, isn't it the virtual object we really want to make Far, and the representative be recreated as necessary?
• makeRepresentative would take the behavior object and curry each functions before attaching them to the representative to make the representative object behave like it had normal methods. For self / this, it's just a matter of binding as the context or as an argument. In neither case would a detached method be usable to act on something unintended, preserving the behavior of an equivalent closure based implementation.
• The init could actually be a specially handled function on the behavior object that is not attached to the representative. One question is if it should also get a self (or this) reference like other functions of the behavior (e.g. to initialize a virtual store entry)? I believe that's a pattern that isn't currently supported by makeKind, but I'm not sure why.

[warner]

Far is trusted, it's part of @agoric/marshal and liveslots imports its own copy for other purposes. Far does some checks on the object to make sure it qualifies, and then does some magic (a special __prototype__ I think?) so that marshal will recognize it as pass-by-reference later. The Representative wants to be Far so that marshaller.serialize() will recognize it as pass-by-reference and hand it to convertValToSlot, where liveslots will recognize it as an object that it created earlier, and can look up the associated vref. The virtual object isn't a real javascript Object, it's the abstract entity that has state and behavior and identity.. the Representative is how user code interacts with the abstract thing, and yeah Representatives are recreated as necessary.

init does need to get access to self for just that reason, to be used as a key in WeakMaps during initialization. It should currently work, but it's relying upon that const self = being hoisted (our usual pattern of init first, followed by const self =, induces a forward reference, but the only thing that complains is eslint).

[mhofman]

The Representative wants to be Far so that marshaller.serialize() will recognize it as pass-by-reference and hand it to convertValToSlot, where liveslots will recognize it as an object that it created earlier, and can look up the associated vref.

Thanks for explaining, I hadn't managed to thread it through to the point where during serialization, the representative would be "unwrapped" for the virtual object id.

init does need to get access to self for just that reason, to be used as a key in WeakMaps during initialization. It should currently work

My cursory reading of makeRepresentative was that it wouldn't work since init is called before self is registered anywhere, so the weak store wouldn't recognize the object is a representative.

[warner]

Hm, I think I remember @FUDCo and I discussing that. I think our path out was that init is not called until after the kind constructor returns, so the VOM (virtual object manager) calling it gets to see self and register it before invoking init (which can then safely reference it).

[Tartuffo]

@warner is it possible to make the API changes for MN-1, and hold the deep impl of it to MN-1.1?

[warner]

I think this is a non-issue now that defineKind is taking a behavior record (table of functions) and implementing the create-a-Representative "kind constructor" function itself. No userspace function is invoked during deserialization (and we copy the pieces of the behavior record into a new real Object during defineKind, so even if behavior is a Proxy or has getters, they shouldn't get control).

So metering is a function of when deserialization happens, and that's sensitive to GC, but we don't meter deserialization, so even if userspace gains a way to sense metering, they shouldn't be able to sense the GC that provokes/inhibits it.

[mhofman]

Yes, this was my original motivation for suggesting a behavior object approach!

[FUDCo]

Closing per @warner's comment above.