ReviewOS

zig-utils/zig-js

Parser: securely seed cover-grammar identity indexes

#855
Closed chris opened this 9 days ago ·
9 days ago

Parent: #493 Related: #496, #761

Problem

The parser's rest_trailing_comma_arrays, pending_cover_inits, pending_proto_dup, and paren_wrapped indexes use AutoHashMapUnmanaged's default fixed hash context. User source controls the number and insertion order of the arena-allocated AST nodes stored in these tables. Arena/ASLR address placement is incidental process state, not an explicit keyed defense against adversarial collision families.

These tables preserve cover-grammar facts by exact node identity, so replacing them with content keys or scans would either change semantics or introduce attacker-proportional repeated work.

Implementation

  • Add an exact-identity hash context keyed from the parser's existing lazy parse-root secure seed.
  • Keep exact pointer/integer equality; only the bucket hash changes.
  • Share one seed across nested template-substitution parsers, matching declaration-name indexes.
  • Publish a newly derived seed only after the first table insertion succeeds, so OOM remains failure-atomic.
  • Keep empty lookup/removal paths allocation- and entropy-free.
  • Preserve arena ownership and avoid adding per-node metadata or another parse pass.

Acceptance

  • All four cover-grammar identity indexes use the keyed context.
  • A deterministic adversarial witness proves keys colliding under the old fixed context disperse under an installed seed while exact identity remains correct.
  • Failed first insertion leaves both the index and shared secure state empty; retry succeeds.
  • Parentheses, array-rest trailing comma, CoverInitializedName, and duplicate __proto__ parse semantics remain exact.
  • Focused parser/OOM tests, full unit suite, exact-parent Test262 frontend evidence, threadfuzz, and public/private ABI gates pass.

No-workaround rules

No source blacklist, arbitrary grammar limit, linear membership scan, address secrecy assumption, third-party hash table, or weakened early error.

9 days ago

Implemented and pushed to main as fix(parser): seed cover-grammar identity indexes (#855).

What landed:

  • all four default-seeded cover-grammar identity tables now use exact-identity maps keyed from the parser's existing lazy parse-root secure seed;
  • nested template parsers share that seed; empty lookup/removal remains allocation- and entropy-free; first publication occurs only after successful insertion;
  • arena ownership and all early-error semantics remain intact—no blacklist, linear scan, grammar cap, or address-secrecy assumption.

Exact-tree evidence:

  • 32 identities colliding in one legacy 1,024-bucket partition disperse across at least 24 keyed buckets; exact lookup/removal remains correct;
  • failed first insertion leaves zero capacity, zero entries, and no seed; retry succeeds;
  • complete allocation-failure replay covers all four grammar paths and nested sharing;
  • parser Debug and TSan: 59 passed, 0 failed, 0 leaked each;
  • full unit suite: 2,266 passed, 1 skipped, 0 failed, 0 leaked;
  • threadfuzz: 400 programs from seed 1, 0 failures;
  • exact-parent Test262 expressions: 11,037 pass and the same one pre-existing TCO runtime failure; logs are byte-identical (SHA-256 3d077cdbead5da1cf115c0713f14f72f98d94c52fe3f3855b076d15211b0c2b5), so 0 flips. Of 11,095 source files, 57 are outside the scored denominator;
  • C API: 117/117; Home private ABI: 447/447 owned symbols and 392/392 runtime shims.

Infrastructure note: the first full run executed every test cleanly, but low disk truncated one shard's final summary and the aggregator rejected it. After preserving the logs and deleting only reproducible caches, the isolated rerun produced the clean denominator above.

Sign in to comment on this issue.