Underspecification of liveness creates use-after-free hazards

Open fstirlitz opened this issue 3 years ago • 0 comments

Follow-up to https://es.discourse.group/t/liveness-barriers-and-finalization/1082, where I brought up many of the same examples.

ECMA-262 12th Ed. §9.9.2 defines liveness of objects as follows:

For some set of objects S, a hypothetical WeakRef-oblivious execution with respect to S is an execution whereby the abstract operation WeakRefDeref of a WeakRef whose referent is an element of S always returns undefined.

At any point during evaluation, a set of objects S is considered live if either of the following conditions is met:

Any element in S is included in any agent's [[KeptAlive]] List.

There exists a valid future hypothetical WeakRef-oblivious execution with respect to S that observes the Object value of any object in S.

The notion of ‘observing’ an object is, however, left undefined and therefore up to the implementation to interpret. The apparent intent was to allow fewer objects to be considered observed than one might naïvely expect; for example, a note mentions scalar replacement on properties as an allowed optimization, from which it would follow that accessing obj.x should not be considered observation of obj that necessitates considering obj live.

But it is not actually clear if any operation described in the specification or external to it constitutes observing an object value; successive applications of the as-if rule may move earlier the point where an object as a whole ceases to be used, up to rendering its creation unnecessary in the first place. As such, wildly divergent notions of liveness may emerge from combinations of optimization passes employed by different implementations.

Without explicit guidance from the specification, it is unclear which, if any, such passes should be considered valid, and it becomes difficult or even impossible to write correctly behaving and future-proof code, as implementations may end up finalizing objects earlier than the programmer intended and might have naïvely expected. To remedy this problem, the notion of observing objects needs to be made more precise.

To offer a point of comparison, the Java Language Specification has included a pretty elaborate definition of reachability that attempts to anticipate many of those problems since as early as the third edition. The standard library also offers an explicit reachabilityFence call since Java SE 9.

(This is not the only problem with the definition liveness. Another issue is the apparent circularity of ‘valid hypothetical future WeakRef-oblivious execution’: if an object is live, then any WeakRef-oblivious execution with respect to it is invalid, therefore no future valid WeakRef-oblivious execution with respect to it exists, and so the object is not live. But this phrasing problem should be more easily solvable.)

Case studies

Some of the examples below refer to a hypothetical FFI mechanism; they may equally well be formulated in terms of callouts to WebAssembly, where the holdings value represents a pointer within WebAssembly-managed memory. This is to point out that these hazards can occur with already existing APIs, not just hypothetical future ones.

All examples below should be assumed to have access to the following declarations:

const finreg = new FinalizationRegistry(f => f());

const deathOf =
	obj => new Promise(ok => finreg.register(obj, ok));
const deathOfReferent =
	wr => (wr = wr.deref()) !== void 0 ? deathOf(wr) : Promise.resolve();

Unless otherwise noted, the examples below assume the strongest possible garbage collection mechanism: every object is collected and finalized at the earliest opportunity, and the callback of every registry in which the object has been registered is run with its holdings; no callback invocation should be assumed elided because its registry has been collected.

Use-after-free because of scalar replacement across a suspension point

This served as the initial motivating example.

import { alloc, free, use } from 'my-little-ffi-lib';

export class Resource {
	#handle;
	static #registry = new FinalizationRegistry(res => { free(res); });
	constructor() {
		Resource.#registry.register(this, this.#handle = alloc());
	}
	use() {
		V: use(this.#handle);
	}
}

Object.freeze(Resource.prototype);

// possible module boundary

(async () => {
	const res = new Resource();
	await Promise.resolve();
	U: res.use();
})();

A strong optimizer may inline V into U, suitably arranging for the private to be accessible. The fact that the #handle private is never modified outside the constructor makes it a candidate for scalar replacement, which elides a reference to res after the suspension point, leaving only a reference to its private value. Since no reference to res needs to be held after suspension, the object becomes eligible for finalization, creating a use-after-free hazard.

Strong reference elision aided by value-range analysis

This revisits an example considered in tc39/proposal-weakrefs#142. A more complicated variant was analysed in https://es.discourse.group/t/liveness-barriers-and-finalization/1082/21.

(async () => {
	const a = {};
	const wr = new WeakRef(a);
	await Promise.resolve();
	X0: console.log(wr.deref() === a);
	X1: console.log(wr.deref() !== void 0);
})();

Value-range analysis allows inferring that at X0 or X1, wr.deref() ∈ { a, undefined } and therefore wr.deref() === a if and only if wr.deref() !== void 0. As such, X0 and X1 produce identical results and one may be rewritten into the other. However X0, taken syntactically, holds a strong reference to a, while X1 does not. If the former is re-written into the latter, the object becomes collectible before the comparison takes place.

If such an optimization is to be allowed, it would follow that mere appearance of a strong reference to an object in an identity comparison does not establish observing the object value. However, a very similar case was explicitly considered in tc39/proposal-weakrefs#142, where it was said that X0 should never return anything other than true. That intent was phrased in terms of forbidding rematerialization-like transformations; it was not, however, expressed in the normative text of the specification, but only in a Note. As the above shows, the emergence of an equivalent effect can be explained in terms not involving rematerialization as such, but merely by predicting the effects of given code. If the intent to prohibit strong reference elision in this case is to be upheld, a more robust notion of observation is required.

Paradoxical registration

This is simplified from https://es.discourse.group/t/liveness-barriers-and-finalization/1082/15.

(async () => {
	const brenda = {};
	W0: await deathOf(brenda);
	W1: await deathOf(brenda);
	P: console.log("Done.");
})();

Under naïve semantics, P is unreachable. Complete liveness analysis arrives at a contradiction: if brenda is never finalized, then execution cannot resume after W0, code that follows it is therefore unreachable, making brenda not live and therefore eligible for finalization. But if the object is collected and finalized, the promise at W0 is resolved, and brenda is subsequently used at W1, contradicting the fact of its finalization. A compliant implementation can only resolve the paradox in favour of no finalization.

However, one can imagine re-writing the code like this:

(async () => {
	const brenda = {};
	const wr0 = new WeakRef(brenda);
	const wr1 = new WeakRef(brenda);
	W0W: await deathOfReferent(wr0);
	W1W: await deathOfReferent(wr1);
	P: console.log("Done.");
})();

Now P can be reached under a quite reasonable interpretation. At W0W, the strong reference to brenda is not live, so the object is eligible for finalization. At W1W, the weak reference has been emptied; as such, deathOfReferent returns an already resolved promise.

This re-write may be justified by the fact that registering an object for finalization doesn’t require having access to the object in its entirety, but merely knowing when it has ceased to exist. An engine may in fact internally implement registration by way of forming an abstract weak reference, followed by adding that abstract weak reference to the registry; the above transformation would then be equivalent in effect to inlining and code motion before a suspension point. But such a re-write is only admissible if registration is not observation.

Ordering dependencies between finalizers

This one I have not brought before, but it probably makes the strongest case for having explicit liveness fences exposed to user code.

import { allocA, allocB, useB, freeB, freeA } from 'my-giant-ffi-lib';

// assume the registries live forever
FA:; const regA = new FinalizationRegistry(({ handle }) => freeA(handle));
FB:; const regB = new FinalizationRegistry(({ handle }) => freeB(handle));

const handlesA = new WeakMap();

class ResourceA {
	constructor() {
		const handle = allocA();
		handlesA.set(this, handle);
		Q0: regA.register(this, { handle });
	}
}

class ResourceB {
	#eye;
	constructor(rA) {
		const handle = this.#eye = allocB(handlesA.get(rA));
		R1: regB.register(this, { handle, rA });
		// R0: regB.register(this, { handle });
	}
	use() {
		useB(this.#eye);
	}
}

// possible module boundary

(async () => {
	const resA = new ResourceA();
	const resB = new ResourceB(resA);
	await Promise.resolve();
	X: resB.use();
})();

Suppose a library gives access to resources of two kinds, (A) and (B), and resource of type (B) internally keeps a reference to a resource of type (A). As such, resource (A) must not be finalized before all (B) that hold it have been. In native code this would have been managed manually, but here, the dependency must be communicated to the garbage collector.

To that end, the above code keeps a reference to the ECMAScript object representing (A) as a property of the holdings value for (B). However, even if we stipulate that the held value must be live before the callback executes, current specification does not imply that a property value of a live object is live. An implementation may notice that the callback at FB does not end up accessing the resA property, and eliminate the property from the holdings value, effectively rewriting R1 into R0. This creates a use-after-free hazard at X, as resA may have become finalized while resB is still usable.

In fact, I consider it quite probable that an optimization pass of this kind will appear in some form, especially for arguments immediately destructured in the parameter list. With the proliferation of option bags in proposals like https://github.com/tc39/proposal-json-parse-with-source, it may become advantageous for engines to internally ‘reshape’ argument lists to perform interprocedural dead store elimination and avoid expensive computations of values that end up not being accessed by the callback anyway. Whether it will be applied to finalization callbacks (or more generally, asynchronous callbacks that are still latent) is less certain, but cannot be ruled out. It might, for example, give a slight performance advantage to perform such reshaping for the regA callback and thus elide the creation of the wrapper object.

Blind nihilism breaking basic invariants

The undefined notion of ‘observing a value’ is the only thing that connects the specification concept of ‘liveness’ to the usual understanding of the term. If the definition is taken purely formally, then it fails to capture even the most basic, incontrovertible, common-sense invariants, such as: that after an object stops being live, it cannot be live again (or conversely, if an object is currently live, it has been incessantly live until now); or that when an object is declared not live, then no references to it will be created in the future, nor will any finalization registrations or callbacks be performed; or even that an unreachable object cannot be live (although the last one is of lesser concern, as it does not present a correctness hazard).

A sufficiently perverse implementation may declare that no operation constitutes observing an object value; because the term is not defined, this does not contradict the specification, especially in light of the previous examples demonstrating how often it is possible to elide a strong reference where one may naïvely seem required. Declaring that value observations never actually happen is just taking the previous case studies to their logical conclusion: an object is not observed when accessing its properties, when registering it for finalization, when comparing it against another object, when wrapping it in a WeakRef, so is it ever observed at all?

From such a definition, it follows that every WeakRef can be cleared and every finalization callback can run at the nearest suspension point. As such, even the function below can actually return true:

async function bringOutYourDead() {
	const iFeelHappy = {};
	R0:; const wr0 = new WeakRef(iFeelHappy);
	W: await deathOf(iFeelHappy);
	R1:; const wr1 = new WeakRef(iFeelHappy);
	X: return wr0.deref() !== iFeelHappy && wr1.deref() === iFeelHappy;
}

At X, iFeelHappy must be live, because it has just been added to the [[KeptAlive]] list by the WeakRef constructor. But between W and R1, it has not yet been added, so the only thing that can make the object live is if any of the subsequent operations constitute observing its identity. It can be argued that none of them do:

X does not observe iFeelHappy, because it can be equivalently re-written as return wr0.deref() === void 0 && wr1.deref() !== void 0 after value-range analysis, as per a previously discussed example.
R1 and R0 do not observe iFeelHappy, as the weak references do not escape the function. The only thing that may be observed is the value of the identity tests evaluated at X. Those tests may be speculatively evaluated, obviating the need to construct weak references in full.
W does not observe iFeelHappy, per the argument under the paradoxical registration example: knowing when an object is finalized does not require having access to the full object.

But if so, then iFeelHappy is eligible for having finalization callbacks run and weak references cleared between W and R1.

In terms of potential code transformations, this interpretation allows re-writing the code as:

async function bringOutYourDead() {
	const iFeelHappy = {};
	const wr = new WeakRef(iFeelHappy);
	R0V:; let wr0Live = true;
	W: await deathOf(iFeelHappy).then(() => wr0Live = false);
	R1V:; let wr1Live = (deathOfReferent(wr).then(() => wr1Live = false), true);
	X: return !wr0Live && wr1Live;
}

which then, of course, can be simplified to just return true.

Feb 04 '22 20:02 fstirlitz