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

Perf: bound adversarial complexity and worst-case latency #493

Open

Description

@chrisbbreuer

Parent: #459
Depends on: #460, #461, #473, #475, #487

Goal

Bound adversarial algorithmic complexity and worst-case latency across parser, runtime, collections, RegExp, JSON, GC, modules, and Wasm without input blacklists or semantic shortcuts.

Scope

  • Inventory user-controlled operations with potential superlinear CPU/memory/stack behavior: tokenization/parsing, property/shape chains, hash tables, sparse arrays, proxy/accessor recursion, string search/replace, regex backtracking, JSON depth/width, module graphs, promise fanout, weak processing, GC graph traversal, structured clone, Wasm decode/validate/compile, and debugger/inspector payloads.
  • Add deterministic growth-series benchmarks and complexity assertions using exact work/limits rather than wall time alone where possible.
  • Implement owned algorithmic fixes, randomized/robust hashing, bounded stacks/worklists, cycle detection, budgets, and catchable resource failures consistent with public semantics.
  • Record tail latency and peak memory under concurrency and no-GIL schedules.

No-workaround rules

  • No known-input blacklist, reduced language/profile, arbitrary rejection below documented resource limits, catastrophic case hidden from aggregate results, or third-party parser/regex/hash implementation.

Acceptance

  • Every inventoried surface has a growth-series witness and explicit expected complexity/resource bound.
  • Adversarial cases terminate within declared budgets with exact result or specified catchable error; no crash/hang/stack overflow/leak.
  • Ordinary-case Bench: define the representative dependency-free performance matrix #460 performance does not regress materially.
  • Fuzz, OOM/fault, deep graph, no-GIL, TSan, and sanitizer gates cover boundary cases.
  • Security/performance docs state exact limits and evidence without claiming more than measured.

Foundation

Existing bounded Worker delivery, heap caps, parser diagnostics, regex ownership, structured clone limits, and Wasm hostile-declaration tests.

Activity

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

    @chrisbbreuer
    MemberAuthor

    The collection-complexity boundary from #513 landed in c797973a. Ordinary object/Symbol keys no longer force ordered O(n) scans, one hash collision no longer disables unrelated buckets, hashes are securely seeded, and deterministic collision/OOM/bounded-growth plus moving-GC/no-GIL/TSan witnesses are checked. This closes one inventory surface, not #493: the remaining parser/runtime/RegExp/JSON/GC/module/Wasm growth-series inventory is still open.

  3. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    #514 is complete on main and closes the strong-collection tombstone-growth complexity boundary. Stable logical cursors preserve mutation-during-iteration while physical storage compacts at a bounded threshold; focused OOM, moving-GC, no-GIL, TSan, and deterministic growth/capacity witnesses pass. Implementation/evidence chain is linked in #514.

  4. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    #513 is complete on main and closes the strong-collection identity-key linear-scan/collision-disable complexity boundary. Exact-parent base and anti-specialization rows both use about 0.619x instructions, with identical checksums; Map remains 204/204 and Set 383/383 on both revisions. Full evidence and caveats are linked in #513 / 4adcc0d.

  5. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    #515 is complete on main in e7d430f and closes a JSON adversarial-depth denial-of-service boundary. Deterministic subprocess coverage exercises 50,000-level arrays/objects, 20,000 mixed containers, raw JSON, reviver traversal, a valid shallow boundary, and syntax-error classification. Before: SIGSEGV/139. After: exact catchable RangeError with no JSON.parse test262 regressions.

  6. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    Closed the temporary-copy component of JSON worst-case allocation pressure in #516. 88b5b169 avoids parser-arena allocation for every unescaped string while preserving escaped decoding and syntax rejection. A fail-on-first-allocation witness covers the property directly; exact-parent evidence measures 0.9787x / 0.9786x retired instructions across representative and anti-specialization inputs.

  7. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    Closed the JSON reviver-source quadratic surface in #517. The 16k/32k/64k ReleaseFast growth series changes from 0.21/0.73/2.94 user-seconds to 0.05/0.05/0.10, while preserving exact parse-record mutation semantics (, moved siblings, duplicates, numeric key order). Seven-pair exact-parent evidence measures 0.1248x instructions with matching checksums and no discards.

  8. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    Correction to the preceding summary: the implementation preserves ECMA-262 SameValue semantics, including the +0/-0 distinction, as well as moved-sibling, duplicate-key, and numeric-key ordering behavior.

  9. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    Closed the quadratic JSON.stringify replacer-membership surface as #519. The ordered allowlist now has a per-invocation hash index, with duplicate/coercion/abrupt-completion semantics covered. Isolated membership work fell to 0.0336x instructions; exact measurement then exposed and fixed temporary bucket retention. Implementation: c823cfba and 2e48c838. Evidence: 11833827.

  10. chrisbbreuer commented on Aug 10, 2026

    @chrisbbreuer
    MemberAuthor

    Closed another adversarial frontend surface in #520. Strict ordinary-function duplicate validation is now expected-linear with exact string equality; 1,024/2,048/4,096 growth rows use 0.2229x/0.1531x/0.0733x instructions versus the exact parent. No parameter limit or semantic shortcut was added. The 4,096 row is 0.126x wall time, the compared function/method corpus remains 1,275/1,275, and the concurrent scratch path is TSan-clean. Evidence: 39c617e4.

  11. 92 remaining items

  12. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Completed another adversarial-complexity boundary in #863 via fix(private-abi): harden heap snapshot identity (#863).

    Heap-snapshot/reachability raw cell identities and persistent arena stable IDs now use lazy secure per-map hashing with failure-atomic context publication. Dense root indices use O(1) flags instead of hashing. Exact snapshot/reachability tests pass in Debug, ReleaseSafe, and TSan; full units pass 2,280 with 1 skip and no failures/leaks; public C and pinned Home/Bun ABI/runtime gates pass. Test262 is N/A for this host-only ABI change.

  13. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Completed the aggregate-exception graph hardening follow-up in #864 via fix(wasm): seed exception collection identity (#864).

    This removes predictable pointer hashing from Wasm GC exception traversal with a lazy secure exact identity set, failure-atomic publication, iterative cycle handling, and no shared exception epoch. #864 contains the exact Debug/ReleaseSafe/TSan, Wasm inventory, threadfuzz, full-unit, C API, and pinned ABI evidence.

  14. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Completed the private Wasm streaming capability hardening in #865 via fix(wasm): harden streaming compiler handles (#865).

    The context-free pinned addBytes feed no longer uses predictable sequential authority tokens or default integer hashing. Handles and registry placement use separate secure entropy, exact live collisions resample, and entropy/allocation failure publishes no partial state. #865 records exact Debug/ReleaseSafe/TSan, pinned ABI, Wasm inventory, threadfuzz, docs, and clean full-suite evidence.

  15. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Follow-up hardening landed via #866 in c6642bb2: serialized-script owner handles are now secure capabilities with separately seeded exact lookup, collision resampling, failure-atomic publication, and exact single-winner release.

  16. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Completed the process-global script-context hash-table slice in #867 via fix(private-abi): seed script context registry (#867). Home-controlled 32-bit identities now use lazy independently seeded exact placement with failure-atomic first publication and transfer; exact full units, TSan, threadfuzz, and pinned ABI/runtime gates are green.

  17. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Follow-up #869 is complete in fix(private-abi): harden VM identity registries (#869). The remaining VM-owned canonical-object and contiguous-vector identity registries now use independent lazy secure exact-identity maps with failure-atomic first publication and allocation-free moving-GC rekeying. Full validation evidence is recorded in #869.

  18. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Follow-up #870 is complete in 17dea421 — fix(private-abi): harden lifecycle registry (#870). The process-global private lifecycle table now uses independent lazy secure exact-pointer hashing, failure-atomic publication, centralized exact retirement, and empty-table reset/reseed, with Debug/ReleaseSafe/TSan, external fixtures, fuzz, full units, ABI audits, and docs gates passing.

  19. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Security/latency follow-up #871 is complete in 516a8d59: context and worker inspector refs now use independently randomized capabilities in one securely keyed exact-token registry. Forged, stale, wrong-kind, and wrong-thread inputs are rejected before dereference; adversarial legacy-bucket collisions are covered.

  20. chrisbbreuer commented on Sep 2, 2026

    @chrisbbreuer
    MemberAuthor

    Build-gate follow-up #872 is complete in 99e534be: all four public C/C++ hosts now link and pass under TSan, closing the sanitizer coverage gap exposed while hardening inspector capabilities.

  21. chrisbbreuer commented on Sep 3, 2026

    @chrisbbreuer
    MemberAuthor

    Related hardening landed: #873 securely seeds the exact-thread-ID ThreadLocal value index, preserves lifecycle/GC semantics, and is implemented by 3cf4429e.

  22. glennmichael123 commented on Sep 15, 2026

    @glennmichael123
    Contributor

    #926 now has a measured growth curve rather than a code-inspection suspicion, so it is a confirmed instance of this issue's class.

    Parser.checkPrivateNameUses copies every inherited private name into a fresh map per nested class. Against frozen workloads at 256/512/1024/2048, retained parse-arena bytes grow x3.89 per doubling for N sibling inner classes and x3.85 for an N-deep chain, against a x2.01 source. Both controls stay linear, so the cost is the inherited copy and not the nesting: at N=2048 the growth shape runs 194x slower and retains 31x more memory than a control that parses the same number of nested classes with nothing to copy — 297 MB of retained arena for a 98 KB source.

    The source is linear and attacker-controlled in shape, which is the property this issue cares about. Allocation counts were identical across iterations and across three independent runs. Workloads and the semantic baseline landed in 411b901 ahead of any parser change; measurement detail is in #926.

    One correction worth carrying here: the deep shape was drafted as a control on the reasoning that a chain copies a growing set once per level. That is quadratic too (1+2+...+N), so it is a second growth shape, not a control — it now measures at 0.479 of the siblings constant, as N^2/2 vs N^2 predicts.

  23. glennmichael123 commented on Sep 15, 2026

    @glennmichael123
    Contributor

    #926 is closed, fixed and measured in e07b13b — the first of this issue's quadratics to be taken all the way from suspicion to a landed fix with a before/after curve.

    Parser.checkPrivateNameUses no longer copies the inherited private-name set per nested class; it extends the enclosing set in place and unwinds it. At width 2048 that is 154x faster and 25x less retained memory (232.6 ms -> 1.51 ms, 297.0 MB -> 11.6 MB), and the speedup grows with N — 51x at 1024, 154x at 2048 — because the exponent changed rather than the constant. Growth per doubling is now x2.08 against a x2.01 source. Both controls sit at or below their baseline, which is what confirms the win is the removed copy and not removed work. test262 across the four affected subtrees: 0 fail, every count matching baseline.

    The generalizable part for the rest of this issue's class: the copy was replaceable by an undo log only because the structure is asked exactly one question (contains, over a void value). Worth checking that property first on the other candidates — where a scope map carries a payload, the same trick does not port. #927 is precisely that case.

    Two more instances of the same copy-per-nested-scope shape are now filed, both verified by reading the code and both deliberately carrying no performance claim until measured:

    Method note worth carrying forward from #926: retained bytes are a cleaner algorithmic signal than wall time. Once the arena passes a few hundred MB the time ratio picks up a memory-system tax and overshoots the true exponent (x5.3 where N^2 predicts x4.0), while the byte ratio converged on x3.89. Allocation counts were bit-identical across three independent runs; timings on sub-millisecond controls spread up to 3x on three samples and needed 15.

  24. glennmichael123 commented on Sep 16, 2026

    @glennmichael123
    Contributor

    #928 is closed and fixed in 0fb72d2, the second of this issue's quadratics taken from suspicion to a measured fix after #926.

    checkLexicalDupes no longer re-collects the whole subtree's var names at every nested scope. At width 2048: 199x faster and 46x less retained memory (166.7 ms -> 0.84 ms, 291.5 MB -> 6.4 MB). As with #926 the speedup climbs with N (19x -> 42x -> 88x -> 199x), and time now grows x2.00 per doubling. 11,890 test262 tests across 15 subtrees: 0 fail under both the old and new parser.

    Refinement to the note I left here after #926. I wrote that the undo-log trick works "only because the structure is asked exactly one question" and does not port where a scope map carries a payload. #928 is a counterexample to the second half: its map does carry a payload (a depth), and it still worked. What actually mattered was that the question is answerable from state that is stack-disciplined, so a scope can restore exactly what it changed. The payload only meant the undo log must restore a previous value rather than delete a key. That seems the better test for the remaining candidates, including #927.

    What both fixes had in common, worth reusing: freeze the workloads first, and include a control that separates the two plausible causes. For #928 that was wide: N sibling blocks run the scan exactly as often as the growth shape does, yet stayed flat, which showed the cost was each scan's depth and not the number of scans. Removing the lexical names would not have shown that, because it turns the scan off altogether.

    Adversarially reviewing #928 also turned up 22 pre-existing early-error bugs, each confirmed by execution against node and against the pre-fix parser: #929 (2 valid programs rejected) and #930 (20 invalid programs accepted). One #930 family, function bodies the walk never reaches, would widen the walk. That is exactly the change that could bring #928's quadratic back, so anyone fixing it should re-run the frozen #928 rows.

  25. glennmichael123 commented on Sep 16, 2026

    @glennmichael123
    Contributor

    Two more instances from this stretch, one fixed and one newly measured:

    A caveat worth carrying for the whole class: the #926 and #928 frozen workloads parse top-level scripts, so they are blind to anything confined to function bodies. #932 is one such effect, and plain nested blocks inside a function also show steepening growth (x2.44 then x4.05). The #926/#928 results stand for the shapes they measured, but function-body variants of those workloads should be added before treating this class as closed.

  26. chrisbbreuer commented on Oct 7, 2026

    @chrisbbreuer
    MemberAuthor

    Closed #1029 in 18a6fb2: nested template substitutions now evaluate through an explicit action stack instead of native recursion. The depth-300 regression passes normally and under TSan; the current-main full unit gate passed 2,567/2,568 with one skip, and the retained 20,000-link flat-chain path showed no measured regression.

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

    enhancementNew feature or requestperformanceMeasured 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