镜像站点 · 本页由第三方 GitHub 只读镜像提供,非 GitHub 官方站点,不接受任何登录或凭据输入。前往 github.com
Skip to content

JSON.stringify: index active cycle membership #556

Closed

Description

@chrisbbreuer

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.

Activity

  1. added
    performanceMeasured runtime, memory, scaling, or build performance
    runtimeJavaScript runtime and builtin implementation
    on Aug 14, 2026
  2. chrisbbreuer commented on Aug 14, 2026

    @chrisbbreuer
    MemberAuthor

    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.

  3. chrisbbreuer commented on Aug 14, 2026

    @chrisbbreuer
    MemberAuthor

    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.

  4. chrisbbreuer commented on Aug 14, 2026

    @chrisbbreuer
    MemberAuthor

    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.

  5. chrisbbreuer commented on Aug 14, 2026

    @chrisbbreuer
    MemberAuthor

    #556 is complete on main.

    Commits:

    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.

  6. chrisbbreuer commented on Aug 14, 2026

    @chrisbbreuer
    MemberAuthor

    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.

  7. chrisbbreuer commented on Sep 1, 2026

    @chrisbbreuer
    MemberAuthor

    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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    performanceMeasured runtime, memory, scaling, or build performanceruntimeJavaScript runtime and builtin implementation

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions