Alternative harden implementation approach

[dtribble]

What is the Problem Being Solved?

The current implementation of harden uses membership in a WeakSet to determine whether various objects, functions, etc. have already been hardened. This prevents infinite recursion and improves performance by preventing walking already-frozen object graphs. The algorithm cannot just use isFrozen for the test because a user could manually freeze objects that reference still-mutable state.

That hardened WeakSet can get very large, whereas in both typical JavaScript programs and in Agoric's model using harden, Object.freeze is rarely used. Can we eliminate the need for the large hardened set?

Description of the Design

This alternative implementation approach is inspired by the assumption that we harden many more objects than we just freeze. So we record the usages of freeze instead.

1. change the hardened WeakSet to a onlyFrozen WeakSet.
2. shim Object.freeze to both freeze the object and add it to the onlyFrozen set
3. isFrozen is unchanged
4. harden just recursively freezes. If it finds a frozen object, it checks whether it's in the onlyFrozen set. If so, it removes it from the set and recurs on it
5. if freeze cannot be shimmed early enough, then lockdown may use a hardened set to recur into frozen things it has not seen before.

As a result, isHardened(o) is isFrozen(o) && !onlyFrozen.has(o)

Security Considerations

3 potential concerns:

1. objects frozen before lockdown is called
2. freezing things without using Object.freeze
3. things that get frozen by the execution semantics

Re #2, @erights had some insight:

Need to also patch Object.preventExtensions, {Object,Reflect}.{defineProperty,defineProperties} since those can make an object frozen. Actually, once an object is non-extensible, it is too easy to make it accidentally frozen, such a property deletion. I think you should mark everything made non-extensible, since that's a narrower funnel. IIUC, it does not hurt to take a non-extensible but non-frozen object and put it into onlyFrozen just in case. [I agree]

[dtribble]

I searched the spec for the various terms that could Searching the spec for the various ways something could become non-extensible (recursively following up the "abstract operations"):

• Object.seal
• Object.freeze
• [[Extensible]]
• [[IsExtensible]]
• [[PreventExtensions]]
• OrdinaryPreventExtensions
• SetIntegrityLevel

In 12.2.9.4, the arrays provide by template literals are frozen via SetIntegrityLevel but can only contain strings, so they qualify as hardened as in.

In 9.4.6, Module Namespace Exotic Objects are specified to simply override [[isExtensible]] to return false. They also have writable properties, but the properties are non-configurable so cannot be made read-only and the specification prevents changing that (from 9.4.6.5: "If Desc.[[Writable]] is present and has value false, return false"). As a result, no program can freeze them even indirectly. Therefore, they cannot have a false positive for being hardened, because isFrozen can never be true for them.

9.2.4.1 %ThrowTypeError% starts out non-extensible. It is already included in our primordials and hardened on lockdown, so not a problem.

Note: @erights pointed out these places where extensibility is relevant in the spec, so the search terms kept expanding until they covered these issues.

Edits to update for comments below.

[erights]

but the properties are non-configurable so cannot be made read-only

This is not why they cannot be made readonly. Normal non-configurable writable properties can be made readonly. Only exotic behavior can refuse to be made readonly. Proxies can implement such exotic behavior. IIRC module namespace objects do too, but I have not looked.

[erights]

because isFrozen can never be true for them.

Unless they're empty, in which case, like the templates array, they're transitively immutable anyway, and so not a threat.

[erights]

Also, Dean found a third case that I forgot: The ThrowTypeError object. But it is already included in our primordials and hardened on lockdown, so not a problem.

[erights]

Still need a hardening weakset to suppress cycles. We need to only remove from onlyFrozen when the harden is done, in case we fail.

[erights]

In progress at #706 . Many things pass but many things fail. Does a lot of self-testing, some of which also fails.

Handed back to @kriskowal until further notice.

[erights]

Does not work

My interim conclusion from the #706 experiment: This technique is too dangerous when harden's correctness is security critical, as it is for SES. Using this technique, harden will freeze almost all the objects it is supposed to freeze, which is great for catching almost all the accidents that it should catch. The problem is that it is not practical in general to guarantee the crucial invariant that this technique relies on: That there are no objects that have already been made non-extensible before this code gets to patch the methods that would make objects non-extensible: Object.freeze, Object.seal, Object.preventExtensions, Reflect.preventExtensions. As a shim, we only get to patch these properties after the host initializes itself, and seeds the start compartment with objects of its design. On a pristine Node, it turns out, Object.isFrozen(console._times.constructor) is true. Who knew?

(It looks like console._times is an instance of their own SafeMap which is like Map but frozen. I don't know what other differences it might have.)

If we did a complete harden-like property walk of the start compartment ahead of time, we would have caught this one, which reduces our error rate and increases our effectiveness against accidents. But there's no feasible traverse that will reveal all objects that may result from invoking these start-compartment objects. Worse, the danger is not just the objects that have been frozen early. If any part of the host captures any of the non-extensible-making methods before we patch them, to use them later, we're equally sunk. There's certainly no way to detect or prevent that as a shim. And a good thing too!

Finally, any of the existing host means of creating a new realm (vm on Node, iframe on the browser) create a non-isolated realm, it will come with its own fresh copies of these methods, which might innocently cause more violations of the crucial invariant. I emphasize "innocently" because we assume that none of the platform code is purposely malicious. But we only get to assume it upholds invariants we rely on when we assume reasonable invariants.

But

The immediate temporary situation Agoric is in:

• The normal harden technique works well enough on non-XS systems, so don't need to consider this dangerous technique there.
• It is only a short term problem on XS, as we expect this scaling problem to be fixed somehow soon.
• Although we'd like to use XS in a number of places, our only hard immediate requirement for XS is on-chain.
• Agoric's Mainnet 1 threat model does not include on-chain malicious code; only malicious messages.
• Malicious messages cannot directly use this vulnerability.
• Malicious messages can exploit our accidentally vulnerable innocent code. harden makes that code somewhat less exploitable. But a 98% harden is about as good at that as a 100% harden.
• For the on-chain use of XS, we are the host, so we can be careful not to violate the crucial invariant ourselves it setting up each XS instance.

Use only where we must. Kill it soon.

Best would be if we can get the underlying scaling problem fixed before we need to deploy this. But if we must deploy it on XS only on-chain, and kill it before any potentially malicious code is to run on chain, we can cope.

[erights]

The other hazard is that some of our own code accidentally either freezes something early, or samples the freezing functions early, merely because of the order of module initialization. That's why I had to change the import order at https://github.com/endojs/endo/pull/706/files#diff-49d41d34c5a4387e587918e9e0d6de6ee8431bea720f90e81954fca5e953b88c in packages/ses/index.js .

This is not a fatal hazard, but it is a PITA. We don't currently have any good way to prevent this accident under maintenance. The tooling needed to ensure this is upheld would be weird, but certainly possible.

[erights]

If we were to place a complete membrane between SES and all the non-SES host-provided objects on the start compartment's global, that could preserve the crucial invariant on all objects reachable from SES. The key is that the SES-side of the membrane should only present non-extensible objects to SES that are also registered on the onlyNonExtensible weakset. IOW, the membrane's handlers should only use the patched versions of these stabilizing methods to stabilize the membrane objects on the SES side of the membrane. Then, host violations of the crucial invariants elsewhere do not threaten SES.

[erights]

See Agoric/agoric-sdk#3118

@dckc @warner as discussed in the meeting this morning, I've assigned you two. But of course grab me if I can help. Good luck!

[dckc]

Assigning me to Agoric/agoric-sdk#3118 makes sense to me, but not this one.

As a poor-man's notation for blocking dependency, this depends on addressing:

• performance cliff transposed weakmaps - performance cliffs in XS revealed by #3105 Agoric/agoric-sdk#3118

[dtribble]

Closing since we are not pursuing this