audit virtual object manager for non-determinism against adversarial code

[warner]

What is the Problem Being Solved?

@FUDCo and I have talked about a lot of potential non-determinism in the virtual object manager, and we've thought of and/or implemented many defenses, but I'm still nervous. We need to do a careful examination of the API and implementation, to see if there's any way adversarial code can use it to learn about GC events that they're not supposed to have access to.

The requirements are:

• userspace activity is a deterministic function of vat deliveries and syscall return values
• non-GC syscalls are a deterministic function of userspace activity
• objects move from "REACHABLE" to "UNREACHABLE" (using terminology defined in non-deterministic GC #1872 (comment)) only as a result of vat deliveries (either because userspace deletes/drops something, or because liveslots drops a strong reference to an export)
  • however objects move from UNREACHABLE to COLLECTED at random, whenever the engine chooses to perform GC
  • we will force GC at the end of each crank, so everything that was UNREACHABLE by end-of-crank will become COLLECTED in time for liveslots to act upon it
  • but nothing precludes the engine from performing GC earlier
• if liveslots or the VOM needs to provide a Representative (e.g. a device invocation syscall returns a vref that points to a virtual object, or userspace code reads from the state of a Representative, or looks up something in a virtualized collection), it will always provide an existing Representative if one exists, to maintain the property that userspace only ever sees a single Representative (or Presence) per vref at a time
• however if that Representative/Presence JS object is released, then a second access within the same crank may or may not cause a new Representative/Presence to be created, depending upon whether the original made it all the way to COLLECTED in the interim
• userspace must not be able to tell which case occurred
• the resulting vatstore syscalls must not depend upon which case occurred

I want to investigate sneaky things like:

• counting how many times the userspace-provided "kind constructor" is called
  • this probably requires calling the constructor on every deserialization, even if we throw away its value
• self capturing some per-kind-constructor-invocation value that is different each time
• comparing the object identity of the state object against some previous value
  • the initial init()-time state object is special: it is a normal mutable object, so we can sense what properties are added to it
  • it's probably ok if init() always sees a distinct object from all other calls (which merely reanimate the object, as opposed to allocating a new vref)
  • but two sequential reanimations must either always see the same state object (most likely), or always see distinct ones (less likely)
• somehow comparing the self value created by the constructor against other Representatives
• throwing an exception during the construction process
• putting a Proxy in state and measuring how many times it is accessed

Security Considerations

If adversarial userspace code can use virtual object behavior to sense when GC has happened, it can behave differently on some validators than others, causing grief or (worst case) a complete chain halt (if they manage a 50/50 split). If they could target a specific validator, they could get that validator kicked out of the voting set, possibly increasing their own voting power in the process.

Test Plan

I'd like to see a few unit tests that exercise any problems we think up (where the test exercises both a "force GC in the middle" case and a "don't force GC" case). But in general I suspect this is a "read the code and think very carefully about it" task, more than a "write new code" task.

[warner]

I'd also like us to look critically at the inescapableGlobalProperties which were added to prevent userspace code from reaching the real WeakMap and WeakSet. In particular I want a unit test that demonstrates a child Compartment cannot be used to escape the modifications, even if it sets the inescapableGlobalProperties option to something unusual, or if they delete globalThis.WeakMap or something.

And, I want a review of our replacement WeakMap/WeakSet implementations, to make sure e.g. code which subclasses them cannot interfere with their behavior.