JSON.stringify: index active cycle membership

Parents: #473, #493 Related: #460, #461, #515, #519

Problem

JSON.stringify implements the specification's active Stack cycle check by linearly scanning every currently active ancestor for every object it serializes. An attacker-controlled non-circular chain of depth n therefore performs O(n²) pointer comparisons before the existing native/logical stack guard. Repeated aliases in sibling branches are legal and cannot be rejected by a global visited set.

Scope

• Land benchmark-first acyclic depth-growth rows, a shallow repeated-sibling control, and a deep real-cycle control with frozen topology/output/checksums and source construction outside the timed invocation.
• Add an invocation-local exact-identity membership index for the active specification stack while retaining its ordered push/pop behavior.
• Keep the shallow common path allocation-free; activate bounded index storage only after a fixed stack threshold.
• Preserve callback-observable toJSON, replacer, Proxy, getter, alias, error, indentation, and property-order semantics.

No-workaround rules

• No lower depth cap, skipped cycle check, permanent object/header marking, process/realm-global visited state, treating sibling aliases as cycles, input preprocessing, benchmark recognition, or changed callback order.
• Do not touch stacks, queues, jobs, Promise/microtask, or Worker lifecycle code.

Acceptance

• Benchmark source, depths, controls, checksums, jobs, warmup, and timed boundary land before the runtime change.
• Active-cycle membership is O(1) expected time beyond a fixed shallow threshold and total index construction/work is O(n), with bounded invocation-local storage.
• Acyclic chains, real ancestor cycles, repeated sibling aliases, toJSON/replacer-created cycles, and Proxy identity preserve exact specification behavior.
• Shallow stringification performs no new membership allocation; index allocation failure leaves stack/index state coherent and propagates OOM.
• JSON.stringify test262, focused OOM/deep/GC/TSan witnesses, forced execution modes where eligible, and full units pass without regressions.
• Seven-pair exact-parent evidence publishes wall, CPU, peak RSS, instructions/cycles/energy availability, thermal state, and dispersion with no discarded samples; shallow control remains neutral.

Security boundary

Object depth, graph shape, aliasing, Proxy/replacer/toJSON callbacks, and allocation pressure are attacker-controlled. The fix must bound cycle-membership work without weakening the exact active-ancestor rule or turning an allocation failure into stale membership state.

Benchmark-first commit landed on main as 4be2bc64: bench(json): add stringify cycle-depth rows (#556).

Frozen rows:

• acyclic active-ancestor depths 512, 1,024, 2,048, and 4,096;
• a real depth-4,096 back-edge that must throw TypeError;
• a shallow 4,096-element array containing the same object reference in every slot, which must serialize legally and prevents a global-visited-set substitution.

Graph construction happens during workload selection, before ten one-job warmups and the scored invocation. Every scored job performs a real JSON.stringify and validates exact encoded length, leaf offset, opening/closing code units, error class where applicable, and frozen checksum. The one-job checksums are 8946, 17650, 35058, 69874, 1004096, and 45243.

Clean-parent diagnostics retire approximately 7.86M / 21.25M / 64.14M / 227.62M instructions across the depth rows, exposing growth that accelerates beyond the linear serialization/output work. The full benchmark validation family, exact-parent harness self-test, and 18/18 representative matrix structural checks pass. No runtime fix is included in this commit.

Runtime commit landed on main as 63d05437: perf(json): index active stringify cycles (#556).

The implementation retains the specification-ordered active ancestor path and lazily promotes membership after 32 objects into an invocation-local exact hash index. Managed objects use relocation-stable GC identities; arena/static objects use a separately tagged address identity, so the two identity domains cannot collide. Promotion and indexed insertion acquire all needed capacity before publishing either representation, and teardown releases both the ordered path and temporary index on every success, throw, or OOM exit.

Semantic coverage now includes legal repeated sibling aliases, direct cycles, toJSON-created cycles, replacer-created cycles, repeated Proxy aliases, Proxy-mediated cycles, deep promoted paths, failed index promotion, and exact LIFO removal. The same deep witness produces identical results under forced tree-walker and required-bytecode execution, with one required-bytecode template compile and zero fallback.

Validation:

• focused JSON units: 9/9 Debug and 9/9 TSan, zero failures/leaks;
• test/built-ins/JSON/stringify: 66/66 pass, zero failures;
• full units: 1,630 passed, 1 expected skip, zero failures/leaks (four shards);
• the sole failure in an initially saturated ten-shard run was the pre-existing shared-nursery timeout assertion; its exact isolated rerun passed in 2.6 s versus 45.9 s under saturation, and the complete four-shard rerun passed.

The remaining acceptance work is the focused precise-GC witness and seven-pair exact-parent performance evidence, including the shallow neutrality control.

Focused precise-GC coverage landed as 3a67f66d: test(json): cover GC-requested cycle indexing (#556).

The witness builds a managed object path beyond the 32-object promotion threshold, requests collection from inside the replacer, validates the complete output plus legal sibling aliases, confirms the requested collection ran, then performs a moving compaction and revalidates the Context-rooted result after invocation-local index teardown. It passes in Debug and TSan as part of the 10/10 focused JSON set, with zero failures and zero leaks.

The exact parent/candidate benchmark runners are also built and preserved. The seven-pair measurements are intentionally paused because the reference host is currently at 9% battery and discharging; publishing samples under that power state would violate the repository's benchmark-evidence rules. No samples have been collected or discarded.

#556 is complete on main.

Commits:

• benchmark-first 4be2bc64
• runtime 63d05437
• focused precise-GC witness 3a67f66d
• exact-parent evidence ac9dc52b

The implementation keeps the exact ordered active-ancestor path, promotes after 32 objects into an invocation-local relocation-stable identity index, remains allocation-free for shallow membership, and makes promotion/insertion failure-atomic. Repeated siblings stay legal; direct, Proxy, toJSON, and replacer-created ancestor cycles still throw TypeError.

Validation is complete: test/built-ins/JSON/stringify 66/66; focused Debug and TSan 10/10 with zero leaks; OOM/deep/precise-GC/moving-compaction and forced tree-walker/required-bytecode witnesses; full units 1,630 passed, 1 expected skip, zero failures/leaks.

The exact-parent overview publishes 84 fresh-process samples across six rows, all on AC power with nominal thermal state and no discarded samples. The real 4K cycle improves to 0.3688× retired instructions and 0.422× median wall; acyclic instruction ratios improve progressively to 0.8252× at 4K; the shallow repeated-alias control is 1.0124× instructions / 1.006× wall.

The measurement also separated a different deep-output amplification: successful nested object results are recopied through ancestor-local temporary buffers. That is now tracked without scope creep in #558.

Follow-up #558 is complete. 3ec9847f removes the recursive successful-output copying isolated by #556, and 61652299 publishes the exact-parent depth/control rows. At depth 4,096, median peak RSS falls from 1,836,728,320 to 57,098,240 bytes and retired instructions to 0.2341x.

Follow-up #858 is complete in c9d414ae. It leaves #556’s ordered path, depth-32 promotion, stable identity domains, callbacks, GC, and OOM semantics intact while replacing only the promoted table’s default hash placement with a lazy secure context. Exact-parent JSON.stringify diagnostics remain byte-identical at 66/66.