GC sensing via virtual-object method identity

[warner]

While reviewing #4618, I think I spotted a problem with our plan to prevent userspace from sensing GC. Imagine a stripped-down Purse kind:

const makePurseKit = makeKind('name', () => { currentBalance: 0 }, {
  const purse = { deposit: () => stuff };
  const depositFacet = { receive: purse.deposit };
  return { purse, depositFacet };
});

Now imagine that userspace does:

let p1kit = makePurseKit();
let rx1 = p1kit.purse.deposit;
virtualCollection.set(key, p1kit);
let p1kit = null;
// now GC may or may not happen
let p2kit = virtualCollection.get(key);
let rx2 = p2kit.purse.deposit;
rx1 === rx2;

If GC does not happen, and the p1kit cohort is still in memory, the virtualCollection.get() will call the actualizer (so it can't sense GC by counting invocations) and throw away its value, and p2kit will be the same object as p1kit (although userspace threw away p1kit so it can't sense this directly). In this case, rx2 will be the same as rx1.

If GC did happen, we'll still have the deposit method, but the purse (and indeed the whole cohort) will be gone. So the vc.get() will use the actualizer value, which will have a new deposit method, which will not be the same as rx1. This would mean userspace can sense GC when it's supposed to be oblivious to it.

And, now that I write it, we don't need multiple facets at all: the same problem would occur with just purse.

We established a weakmap from each Representative to the cohort, so that userspace holding on to e.g. p1kit.purse would be sufficient to keep the whole p1kit cohort in memory, preventing them from using this to sense GC. But that doesn't help for interior values.

I'm not seeing an obvious way to fix this. Any new object created by actualize might be comparable, and I don't think we have a way for makeKind to find them all (and use them as WeakMap keys to keep the cohort alive).

This feels a bit like the "every Presence is unique and userspace shouldn't ever compare them" world we were in a year ago, which we escaped by preventing userspace from using distinct Presence Objects as WeakMap keys (the inescapableGlobals.WeakMap = VrefAwareWeakMap trick). But those Presences didn't have internal structure that could be used for identity comparison. And, now that I think about it, #2069 auxdata might open up the same sort of problem on Presences.

cc @erights @FUDCo

[warner]

For #2069 auxdata, since the object graph we're building is immutable and behavior-free, we can enumerate all the individual Objects (records) that make it up, and establish WeakMap links from each to the top-level Presence. That way, any attempt by userspace to retain one of those Objects and use it to compare against a corresponding future incarnation's version will cause the entire graph to be retained.

(now, would this help if they put the sub-Object in a WeakMap to perform the recognition test? I don't think so. Ugh)

To manage something like this with a virtual object, where new sub-objects could be created by behavior at any time, we'd probably need some sort of membrane to spot them all. Double ugh.

Oh, hey, the same issue probably exists with the .toString method property of plain Presences. Triple ugh.

[FUDCo]

I have an idea, but it's too hazy to write down yet. We should talk.

[erights]

Oh, hey, the same issue probably exists with the .toString method property of plain Presences. Triple ugh.

Where is that?

[warner]

Any method on a Presence Object could be extracted and used as a comparison. Likewise the .prototype could be extracted and compared, if it is unique. I forget if the Presences that HandlePromise creates have any methods or a unique prototype, but I expect toString must be implemented with one of the two, thus providing a handle for userspace to compare.

Hm, and another concern is whether hp = HandledPromise.resolve(presence) deliberately returns the same Promise for a given Presence (e.g. it has a WeakMap from Presence to Promise). If so, userspace might retain the Promise and try to use it as a distinguisher. I suspect that there's also a reference from Promise to Presence, in which case their lifetimes might be roughly the same.

[erights]

Likewise the .prototype could be extracted and compared, if it is unique.

Yes, it is. And it does cause this problem.

This proto does have a Symbol.toStringTag-named property whose value is a string, which is therefore not a problem. Presences do not have their own .toString method. Rather, they just inherit Object.prototype.toString, whose behavior takes into account that Symbol.toStringTag-named property.

[warner]

For both Presences and Representatives, let's use the term "instance" to talk about the JS Object that is created for userspace to work with. For a remote object known to the vat as the vref o-5, at any time there will be zero or one Presence objects that correspond to that vref. The first time we deserialize o-5, we'll create "Presence(o-5) Instance 1". If userspace drops that Presence object, JS will GC it and the Presence will go away. Later, the object might be reintroduced to userspace by a new inbound message or by reading virtualized data. When that happens, the deserialization of o-5 creates "Presence(o-5) Instance 2". But, if GC didn't happen, the slotToVal WeakRef will still be populated, and userspace would be handed Instance 1.

We need to prevent userspace from distinguishing Instance 1 from Instance 2, otherwise userspace can use this to sense when GC happens, and we've decided we don't want to allow that.

The tools that userspace has to work with are === and the modified WeakMap/WeakSet that we impose upon the globals (aka VirtualObjectAwareWeakMap/Set). The "aware" forms recognize objects that have non-precious vrefs associated with them (so Presences and Representatives) and use the vref as a key instead of the actual JS Object. Userspace does not get WeakRef or FinalizationRegistry.

Presences

Here's what the situation looks like for Presences:

The red rounded rectangles are unique Objects created each time we need to deserialize the Presence. The black rounded rectangle is a common Object used by all Presences, so it doesn't cause a problem. The white-background rectangles are Strings, which don't have identity and don't cause a problem.

The prototype that Far() injects is unique to each Instance: it is created when liveslots.js makeImportedPresence uses Remotable to wrap the HandledPromise:resolveWithPresence() return Presence and turn it into a Far object:

    let remotePresence;
    const p = new HandledPromise((_res, _rej, resolveWithPresence) => {
      // Use Remotable rather than Far to make a remote from a presence
      remotePresence = Remotable(
        iface,
        undefined,
        resolveWithPresence(fulfilledHandler),
      );

The Presence object doesn't cause a problem: userspace can't use === to distinguish Instance 1 from Instance 2, because if they hold onto Instance 1 for comparison, later deserializations will use liveslot's WeakRef, so they'll always get back the same instance. So if they try to perform that comparison, the answer will always be true. And it doesn't help to put the Presence in a WeakMap or WeakSet, because they only get the "aware" form, which stores the vref, and both Instances have the same vref.

The prototype is a problem, because they could hold Object.getPrototypeOf(instance1) and === it to one they get from Instance 2. The prototype doesn't keep the Presence alive, so GC could collect Instance 1 and then a new deserialization would create Instance 2 (along with Prototype 2), and the comparison would sense the difference. They could also store the prototype in a WeakMap/WeakSet, because "aware" doesn't assign the prototype a vref: it's just another Object.

I think we can fix this by adding an extra WeakMap and doing wm.set(prototype, presence). This way, any attempt to keep the prototype around (for ===) will also keep the Presence around, so new deserializations should get the old Presence, and thus the old prototype.

[mhofman]

I see 2 kind of objects tied to presences / representatives:

• Things that are walkable from the presence / representative.
• Things that are returned by a call (only applicable to representatives).

For the former we can add those objects to a Set held as value in a WeakMap keyed by the presences/representatives. The problem is mainly figuring out what is unique and stopping at what is shared.

The latter should be prevented by making sure representatives are a pure function of the virtual object's state.

[FUDCo]

Would it work for Far to always use the same prototype object for a given iface string?

[warner]

Representatives / Facets

Here's the situation for virtual objects (which either produce a single Representative, or a cohort of "Facets" which are Representatives that share a state and a lifetime). The dotted black lines indicate where a function "closes over" (aka "captures") some other object. The dotten green lines are a handful of WeakMaps we use to cause related objects to keep each other alive.

In this case, each method (the Function objects) are unique, since we use the objects-as-closures pattern. Most methods will close-over/capture the state object, so they can do their job, but they aren't obligated to (marker facets frequently won't bother). Methods can also capture other objects that were created during actualize(), and those objects will be unique per instance.

We use a few WeakMaps to ensure that any facet of the cohort will keep the cohort alive, and since the cohort is a record of all facets, the reverse is also true. We also ensure that anyone keeping state alive will also keep the cohort alive. Our slotToVal entry actually points at the cohort record, and convertSlotToVal knows how to extract the specific facet from that record when needed. Our finalizer watches the cohort record, not the individual facets.

Each Facet has a vref, so the VirtualObjectAwareWeakMap trick is sufficient to prevent them from being used as a distinguisher. The cohort record and state share a lifetime with the facets, so those probably aren't a problem either.

The methods are known to us during deserialization: we could conceivably walk the facet's properties and establish a WeakMap link from each to the parent Facet object, causing them to share a lifetime.

The big sticking point is the "other objects created during actualize(). We have no way of knowing (ahead of time) what these might be, so we can't use the WeakMap links to force them to have the same lifetime. They won't have vrefs associated with them, so VirtualObjectAwareWeakMap doesn't help. And userspace could use === on them anyways.

The best idea I've had so far (and it's a horrible one) is to impose a Membrane around the facets, and use it to establish a WeakMap link from every object the facet ever returns, to the facet itself. This might provide the GC-insensitivity that we need, but might keep a bunch of other objects alive for longer than they need to be (which might be mitigated by the fact that we expect Representatives to be fairly short-lived, since they're supposed to be virtual anyways).

I've wondered if there's some way to constrain the definition of a Representative that could prevent the creation of (or reference to) additional objects by the behavior. Like, if the behavior was defined by a batch of functions which all take a state argument (instead of closing over one), and these functions were defined exactly once (during makeKind, not during actualize). They could close over static data, like a Brand or some important authorities, but nothing unique per-instance. In this approach, we wouldn't use a user-provided actualize: instead, we'd build the new Representative (facet) by making an object out of wrapper functions that insert the state argument and then call the user-provided single ones.

That would be quite distant from the objects-as-closures pattern, but it would prevent userspace from getting control during deserialization, and thus give us complete control over the unique objects associated with each instance. Then we can WeakMap-link them together and force their lifetimes to be the same.

[warner]

Would it work for Far to always use the same prototype object for a given iface string?

Yeah, although then we need an in-RAM Map from string to shared prototype object, which will outlive the Presences.

I've seen Presences with toStrings like Presence o-12, which means something has a fallback when iface is not provided (and to be honest o-12 is kinda handy when debugging, so I wouldn't mind if all Presences got both iface and the vref, except that userspace probably shouldn't know about vrefs). So I'm not sure how much I'd rely upon there being a small number of strings, over time.

[warner]

The latter should be prevented by making sure representatives are a pure function of the virtual object's state.

Yeah... but. That'd lose some of the expressiveness of our current actualize() scheme, in which facets can refer to each other (which we might compensate for by handing in the cohort record as another argument, in the scheme I sketched out above). I'd like @erights 's thoughts on the developer experience of writing Kinds this way. I don't currently see a way to get our current level of expressivity and prevent access to arbitrary unique-per-instance things.

[mhofman]

I'm confused because I thought I raised this issue months ago about makeKind enabling the representatives to close over state we couldn't control, creating exactly this kind of non-determinism and GC sensitivity issues. At that time I didn't understand fully how our distributed object system worked, so I probably had a difficult time conveying that concern.

I thought that the virtual object as classes that @erights is working on was the way forward to solve this issue, exactly by doing what you suggest, which is making the declaration of the methods of the facets unique per kind, then either binding them to the state and record when creating the representatives, or passing that state as first arguments. In either case, that would nullify both concerns of closed over state per instance, and methods as unique related but gc independent objects.

[warner]

#4905 describes the new API we came up with today (overlapping considerably with proposals made by @mhofman and others a while ago) that should fix this problem.

[warner]

Scratch that, it isn't a complete fix. We're learning more about the set of constraints we need to meet:

• No RAM usage for virtual objects that userspace isn't trying to hold on to. This precludes e.g. a strong Map of all Representatives ever, which means we make Represenatives on demand.
• Userspace can use normal object comparison on Representatives. This precludes having multiple simultaneous Representatives per VO, which means the VOM needs WeakRefs to know whether a Representative already exists, and each act of deserialization may or may not need to produce a new Representative. This will depend upon the timing of organic GC.
• We don't want userspace to be able to sense GC.
• Userspace must either not know when a Representative is created, or must not know that the Representative thus created is actually used. (We currently do the latter, with the proForma flag).
• All objects that are unique to the Representative instances (which includes the Represenatives themselves, the cohort record returned by makeFoo(), the method/Function properties on the Representatives, and the prototypes of all those), which userspace might attempt to compare across instances, must either 1: always be equal, 2: always be different, 3: not be comparable

We can force multiple objects to share a lifetime by establishing a full cycle of references among them. This happens naturally for some directions (Representatives hold strong refs to their method properties, the cohort record holds strong refs to the Represenatives), and we can use an internal WeakMap to establish references for anything else that we know about during deserialization. By making two instance's components to share a lifetime, userspace cannot sense GC by using === between the old instance's component and the new instance's component: they must hold onto the old instance to do the comparison, and doing so keeps everything else in memory, which means the new instance is the same as the old instance, so the comparison will always be true.

We once considered having each act of deserialization return a distinct Representative, which would make the comparison (and that of all its components) false. But that would prevent userspace from using normal object comparison for non-nefarious purposes, so we dropped it, and committed to consistent/stable "one Represenative at a time" deserialization.

Userspace can also perform comparison between instances/components with WeakMap/WeakSet. Unlike ===, this does not require userspace to hold onto the old object. Unless we do something special, WeakSet provides a "recognition predicate" to userspace for any Object that is not mitigated by lifetime management.

We identified this problem for Presences and Representatives a while ago, and attempted to mitigate it by replacing the userspace-visible WeakMap/Set with VirtualObjectAwareWeakMap/Set, which recognizes both Presences and Representatives, and uses their vref as a key instead of the (shorter-lived) Object. This is also necessary for correctness: userspace correctly assumes a wm.set with one instance should enable a wm.get with a later instance (especially because userspace itself cannot be aware that these are two different instances).

However, this doesn't prevent WeakSet-predicate -based distinguishing between the extra components of the Presences/Representatives. For example, userspace could extract the unique prototype object from a Presence, and compare it later:

const ws = new WeakSet();
function one(pres) {
  ws.add(pres);
  ws.add(Object.getPrototypeOf(pres));
}
// time passes, GC happens or does not
// caller sends the same vref
function two(pres) {
  ws.has(pres); // always true, because WeakSet is vref-aware
  if (ws.has(Object.getPrototypeOf(pres)) { // varies
    console.log(`GC did not happen`);
  } else {
    console.log(`GC *did* happen`);
  }
}

To mitigate this, I think we need one of the following:

• 1: Come up with a name for every component of the Presence and Representative cohort (the prototypes, the method objects, the various user-reachable collections that hold them, the state object), set up a WeakMap to look up the name for each component, then teach VirtualObjectAwareWeakMap/Set to use that name for comparison.
• 2: Track all those components in a WeakSet and teach VirtualObjectAwareWeakMap to reject them as keys (@FUDCo suggested we call this behavior/property unweakable, which I love).

The former might be possible. The latter would be pretty awkward to explain to userspace, "sorry, we broke WeakMap a little bit because mumble mumble security".

[warner]

@FUDCo came up with #4905 (comment) to deal with this in a third way: hold those other components strongly iff they're used as a key in a VirtualObjectAwareWeakMap/Set. In combination with the WeakMap-based reference-graph edges we add from all components to the primary Presence/Representative and vice versa, that means any userspace which attempts to build a recognition predicate for a component object will also keep the primary (and all components) alive, which means the next time they deserialize the primary they'll always get back the same instance, which means all the components will be the same, which means their predicate will always return true, so it won't distinguish whether GC happened or not (because GC will never happen). They can unglue themselves from this memory-consuming situation by either explicitly deleting the component from the WeakMap/Set, or dropping the whole WeakMap/Set.

[warner]

Here's a picture of the protective mechanisms we'll have:

If userspace defines any methods at all, those methods will be bound (using some Reflect. API) to a "context argument", which holds { state } and either { facets } cohort record (for multi-faceted Kinds) or { self } (for single-faceted ones). That binding is strong and immutable, so anyone who pulls a method object out of the facet object and retains it will also retain the context argument, from which they'll retain all the facets and also the state.

If userspace does not define any methods, the first state instance is given to the user's finish() function, for the second and later instances aren't given to anybody, so userspace has no second value to compare against the first.

The things we need to add / make sure are present:

• everything must be hardened, of course
• add a weakset.add(Object.getPrototypeOf(facet), facet) for each facet, to prevent someone from stashing one of the facet prototypes (currently unique per Far call) and usefully ===ing it against a later version
• we're already adding similar edges from each facet to the cohort tuple, and from state to the cohort tuple
• add the following objects to unweakables:
  • state
  • the cohort record (named facets), for multi-faceted objects
  • the context argument object
  • every method of every facet
  • the prototype of every facet

Userspace might provide Functions in behavior which have an unusual prototype, however every instance will get the same one (the Reflect binding API won't change the prototype or create a brand new one), so we don't need to mark those.

We should include a comment on the code that creates the context argument that every object we add to it must be marked as unweakable, to prevent this attack.

[warner]

@FUDCo implemented his suggestion by adding preserveUnweakableKey() to virtualObjectManager.js, and updated VirtualObjectAwareWeakMap/Set to call it. This uses a set named unweakable, and virtual object Representatives put their methods into it. We also add the context object, its facets cohort record, and the prototypes of each facet.

We also add the prototype of Kind handles (both durable and virtual).

Since we changed Kind definition (#4905) to provide a bunch of functions, we no longer invoke user code when rebuilding a Representative, which removes some of the original concerns.

I don't think we can close this ticket yet. I need to do a thorough scan, but we're at least not yet adding the prototype of plain Presences.

I'm guessing that everywhere in liveslots that does a Far() or Remotable() (and might do it multiple times for the same vref) needs to follow it up with a unweakable.add(Object.getPrototypeOf(output)).

[erights]

@FUDCo @warner is this fixed? Can we close it?

[warner]

@erights I think we still need to do an audit for this. I'm looking at

agoric-sdk/packages/SwingSet/src/liveslots/liveslots.js

Lines 384 to 388 in 97f8d1d

	remotePresence = Remotable(
	iface,
	undefined,
	resolveWithPresence(fulfilledHandler),
	);

where we use Remotable() when building a Presence object for imports. Is there anything unique to that object which could be reached from userspace that they could retain without also retaining the actual Presence? Like a __prototype__? If so, this grants a GC sensor to userspace.

Also, I wasn't involved in the Far Classes transformation. I suspect they provide fewer troublesome objects than the original design, but we should walk through and make sure that any per-instance objects are properly marked unweakable and/or create strong references to/from the user-visible facets.

[mhofman]

Btw, it occurs to me that in #5000 where I talk about GC sensing through userland WeakMap based on return override + private field stamping, the solution I propose relies on the ability to explicitly create all objects that should be prevented from such trick. The problem is that this wouldn't be compatible with any functions, as you can mint those through Object.create. If no functions are per instance (like I believe it might be the case for Far classes), then we should be good. Something to keep in mind.

[warner]

Having recently overhauled the VOM LRU cache and contextProvider, I'm currently convinced that this is no longer a problem.