JSC: DFG: ObjectAllocationSinkingPhase leaves data flow graph inconsistent

While fuzzing JavaScriptCore with fuzzilli, I encountered the following (simplified and commented) JavaScript program which crashes jsc from current HEAD and the stable release:

    function v9() {
        const v14 = {};
        const v15 = {a: 42};
        v14.phantom = v15;

        const v17 = [1];
        v17.toString = [];
        if (!v17) {
            // On this path (which is never taking at runtime),
            // v14 does not escape and thus becomes a sink candidate.
            return 42;
        }

        // This seems to create the necessary control flow form
        // to trigger the bug.
        for (const v18 of \"asdf\") {
            v14.b = 43;
        }

        // v19 will now be an edge to a PhantomAllocation.
        const v19 = v14.phantom;

        let r;
        for (let i = 0; i < 2; i++) {
            r = v19;
        }

        return r;
    }

    for (let v27 = 0; v27 < 100000; v27++) {
        v9();
    }

This sample crashes, in debug builds, with

    At @23: validation failed: !edge->isPhantomAllocation() (../../Source/JavaScriptCore/dfg/DFGValidate.cpp:912).
    ...

indicating a graph inconsistency. In particular, a live operation node (in this case the Return) points to a PhantomObjectAllocation node, which is merely a placeholder indicating that an object allocation was removed as it isn't needed on every CFG path. This scenario should never happen. Instead, the user node (Return) should point to a Materialization node that does allocate (\"materialize\") the object on the paths on which it is needed.

The bug occurs in the ObjectAllocationSinkingPhase. This optimization attempts to compute sinking candidates (heap allocations that aren't needed on all CFG paths) by tracking all Allocations and Pointers to them with a specialized abstract interpreter. For example, after abstractly interpreting the first three lines of v9, there are now two Allocations (v14, v15) and three Pointers to them (v14 -> v14, v15 -> v15, v14.phantom -> v15). The abstract interpreter runs as a fixpoint iteration, each time traversing the entire graph in pre order [1] and merging the final state of a CFG block with the initial state of all its successor blocks. However, while the state merging function [2] appears to copy newly appeared Allocations to successor blocks, it does not appear to copy new Pointers to any successor blocks once they have been reached for the first time. In this case, that is a problem as the pointer v19 (pointing to v15) only \"appears\" during the second iteration. This is because the PutStructure operation that is required to \"get past\" the StructureCheck in front of the assignment to v19 is only executed at the very end of the first iteration due to the blocks scheduling. As such, in the final loop, v19 is not known to point to v15, and thus v15 is converted into a PhantomAllocation node without updating v19 to point to its Materialization, leading to the graph inconsistency.

This inconsistency can then lead to various problems later on, for example, the following slight variation of the above code causes JSC to incorrectly output \"false\" because the ConstantFolding pass gets confused by the references to PhantomAllocations and incorrectly replaces the CompareEq with the constant false:

    function v9() {
        const v14 = {};
        const v15 = {a: 42};
        v14.phantom = v15;

        const v17 = [1];
        v17.toString = [];
        if (!v17) {
            return 42;
        }

        for (const v18 of \"asdf\") {
            v14.b = 43;
        }

        const v19 = v14.phantom;

        let r;
        for (let i = 0; i < 2; i++) {
            r = v19 == v19;
        }

        return r;
    }

    for (let v27 = 0; v27 < 100000; v27++) {
        v9();
    }
    print(v9());

I haven't thoroughly invested the other optimization passes, but I suspect that there could be others that behave erroneously in this situation and potentially cause memory safety violations. As such I'm filing this as security issue as a precaution.

This bug is subject to a 90 day disclosure deadline. After 90 days elapse
or a patch has been made broadly available (whichever is earlier), the bug
report will become visible to the public.

[1] https://github.com/WebKit/webkit/blob/a2ddf838e7370aae3f5ed99f090f91f34b91c8bd/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp#L777
[2] https://github.com/WebKit/webkit/blob/a2ddf838e7370aae3f5ed99f090f91f34b91c8bd/Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp#L454





Found by: saelo@google.com