Codegen: bounds-check elimination, emitted attributes, thread rules
The security audit's record for the codegen stage (issue #363). It says what
was checked, how, what was found, and which test pins each answer. Base is
main at fc12bf9.
Scope
| File | What was read |
|---|---|
src/bounds.ts |
the WP15 §2 prover: impliesNonNegative, initialiserFacts, differenceFacts, addDisequalityFacts, provesClamp, the loop and call summaries, and the verdicts it writes to nodeProvenIndex |
src/attributes.ts |
the whole-program fixpoint (collectFacts, propagate, propagateCallee), every attribute it emits (readnone/readonly, willreturn, nounwind, nocapture, dereferenceable, align), and the array facts (collectArrayFacts) |
src/escape.ts |
allocation sites (visitCall, isAllocatingBuiltin), flows (flowTarget, assignedLocal, useOutcome), the function arena scope, and the per-pass loop scope (PassWalk.isOld) |
src/parallel.ts |
the parallelMapInto / parallelReduce rules (sharedWriteMessage, reachesDstMessage, resultMessage, arenaMessage, escapeMessage, reduceMessage) and the scope() region rules (collectUses, walkRegion, regionCallMessage, checkDestinations) |
src/emit-arrays.ts |
emitNewArray and its boxed-field twin emitBoxedArrayAssignment (same emitNewArrayLength check; tests/link/cg_sec_boxed_new_array), emitArrayLength, emitBoundsCheck, emitElementAssignment, push and join |
runtime/runtime.c |
nish_alloc_struct, nish_arena_grow, nish_alloc_array, nish_array_grow |
Read beside them, without owning them: src/emit-ops.ts (nsw), the
emitter's inbounds GEPs, src/runtime.ts (the inline allocator and the
runtime declarations' attributes), src/emit-result.ts (orReturn),
runtime/runtime-os.c, runtime/runtime-wasm.c and runtime/runtime-parallel.c.
Threat model
The attacker controls the input of a well-typed program the compiler accepted: every byte it reads, every length or count it parses from that input, every file and directory it is pointed at, and how large those are. The attacker does not write the program and does not choose its flags.
The programmer is honest but writes ordinary code: a length taken from a
header, a name returned from a directory listing, a task spawned on a record. A
finding is a program the compiler accepts, without uncheckedGet or
uncheckedSet, whose run reads or writes outside an object, reads freed
memory, races, or reaches LLVM undefined behaviour because of a check the
compiler removed or an attribute it emitted.
Signed overflow was undefined behaviour by the language's own rule when this
audit ran (--wrapping defined it), so a proof that leaned on nsw was sound
by specification, and --unchecked-indexing is the programmer's explicit
opt-out of the bounds check. Neither was a finding. Since then overflow is a
checked panic (docs/LANGUAGE.md, "Semantics decisions"): every signed
+ - * is either proven to fit — and only then carries nsw — or checked,
so the proofs that lean on a step not passing INT_MAX hold because the step
panics instead, and no nsw the compiler writes is an assumption.
Method
-
Every elimination rule against a counter-program. For each rule in
src/bounds.tsa program was written to reach an out-of-range access once the check is gone: index arithmetic at2^31 - 1,i - 1at 0, negative and fractionalf64indices,u8/u16/u32/i64indices, a bound re-read afterpop,pushand a callee that shrinks through an alias, a hoistedconst n = xs.length, a counter assigned in the body,break,continueand nested loops,for...of, and a function instantiated with a function argument. Each was compiled, the.llread for thenish_panic_indexcall, and the binary run natively. -
Every attribute against its proof. For each attribute kind the emitter writes, the rule in
docs/ARCHITECTURE.md("Attribute soundness rules") was compared with the code that sets it, and a program built to break it: recursion and mutual recursion underwillreturn, panics,expect,charCodeAtand traps;nocaptureon a returned, stored orthis-attached parameter;readonlythrough an alias, a stack literal and an inline array field;align/dereferenceableon inline records.opt -O2 -Sshowed what LLVM did with each.nsw(src/emit-ops.ts) was checked against the overflow rule;nuw,exact,!range,!nonnull, fast-math flags andlifetime.*are not emitted anywhere. -
Every arena scope against a use-after-free. Function scopes and per-pass loop scopes were driven with every allocating builtin, with callees that push or store into a parameter, with
Map/Setkeys built in a loop, a template passthrough, and values handed out through aResult, an interface literal and an array literal. A corruption is visible: the freed bytes are overwritten by the next allocation and read back. -
Every thread rule against a race.
parallelMapInto,parallelReduceandscope()/spawnwere given bodies that write through a stack-literal alias, an identity function, a reassignedlet,this, a constructor, aMap, a wrapper's parameter; a destination reachable through a field; and regions with every early exit. Binaries were built with ThreadSanitizer (clang for the objects,libtsanfor the link) and run. -
Lengths at the
i32boundary. Arrays of2^31 - 1,2^31and2^32 + 5elements were built bypush, bynew Array(n)withnof every numeric type in both number modes, and read from a sparse file, and theirlengthread back. -
What the IR changes.
tests/nish-cmp.jswas run with the base compiler as reference and the declarations emptied, so that every byte this stage moves in the corpus is listed rather than admitted. -
Generated programs against the elision-off oracle and ASan (#883, at
3313da3).tests/differential/soundness.js --gen --asantakes its programs fromtests/differential/proofgen.js, which builds each one out of blocks around the accesses the prover reasons about, 26 kinds in eight families (derived,bounds,pushpop,slice,alias,closure,arena,threads), and makes about half of them end in a one-past variant of their last block, an access that reaches indexlengthand no further.Each program is built twice at
clang -O2, by default and with--no-elision(every proof-backed elision off: the oracle), and both runs must print and end the same. A program must also panicindex out of rangeexactly when it ends in a one-past block, which catches an elision that removes the check both builds share, and its default build runs a third time under AddressSanitizer (tests/differential/asan.js:sanitize_addresson every definition, the runtime built with-fsanitize=address,undefined), where it must panic or finish cleanly as the first run did.A one-past read that stays inside the array's block (
ASAN_BLIND) is not counted as an ASan verdict, andthreads:mapinto's panic belongs to the library (LIBRARY_CHECKED). A failure is reduced by ddmin to amin.tswith the one-past block kept whole. CI runs 600 programs from seed 20261024 on every pull request (nish-cmp, both architectures), and.github/workflows/soundness-fuzz.ymlruns 20 000 from a random, printed seed each week. The results are under "The generated-program pass" below.
Findings
| Id | Severity | Where (base) | Description | Disposition |
|---|---|---|---|---|
| CG-1 | High | src/emit-arrays.ts:1017 (emitNewArray) |
new Array<T>(n) stored n in the header and allocated n * sizeof(T) bytes with no check on n. An i64 n of 2^61 with 8-byte elements wrapped the byte count to 0, in either number mode, so the header claimed 2^61 elements over an empty block and every bounds check passed: a[i] = v wrote wherever i pointed (SIGSEGV in the reproducer, an arbitrary write in general). An f64 n that is NaN or past 2^63 reached fptosi, whose answer is poison; on x86-64 it was -2^63, which wraps the same way. A number parsed from input is enough: new Array<f64>(Number(field)) |
Fixed. newArrayLengthChecked decides when the length needs a check (an i64/u64 or a float in either mode, a u32 under i32 mode; never an i32 or a literal up to 2^31 − 1), and emitNewArrayLength emits one unsigned compare, or two float compares before the fptosi, against min(mode limit, 2^62 / sizeof(T)), then panics with array length out of range. collectArrayFacts reports the panic's callees so willreturn stays exact. Tests: tests/link/cg_sec_new_array_wrap, cg_sec_new_array_f64, cg_sec_new_array_nan, cg_sec_new_array_i64; IR pinned by tests/cases/cg_sec_new_array_guard |
| K1-6 | High | src/emit-arrays.ts:1098 (emitArrayLength); runtime/runtime.c:1164 (nish_array_grow) |
Routed from docs/security/crypto-k1.md. Under --number-mode i32 a.length truncates the i64 length to i32, and nothing stopped an array growing past 2^31 − 1 elements, so sha256, hmacSha256Verify and timingSafeEqual of a 2^32 + 5 byte array saw 5 bytes |
Fixed for the sources this stage owns. nish_array_grow refuses to take any array past 2^31 − 1 elements (it clamps the doubled capacity there, and a push onto a full array of that length fails as an allocation does: nish: out of memory, exit 1; the function is now noinline, which the instruction-count baselines measured as fewer instructions on every map row, not more); new Array(n) refuses such an n under i32 mode (CG-1). The runtime cannot tell which mode compiled its caller, so the push limit holds in f64 mode too: see the doc corrections. Tests: tests/link/cg_sec_push_limit, tests/link/cg_sec_new_array_i64, and the nish_array_grow block of tests/runtime-test.c. Still open for arrays and strings longer than that made elsewhere: readFileBytesSync and readFileSync (runtime/runtime-os.c:112, :120), join and string concatenation, and a C host's nish_alloc_array (CG-3). Since closed by the runtime stage for every source but join: see "Status after the runtime stage" below. Since #427 join is bounded too, so every source is closed and K1-6 is fixed. |
| CG-3 | High | src/bounds.ts:1487 (impliesNonNegative), :1528 (initialiserFacts); root in src/emit-arrays.ts:1099 and src/emit-strings.ts (.length) |
The prover takes every .length to be non-negative and at most the length. Under i32 mode a u8[] of 2^31 + 16 bytes read from a sparse file has length −2147483632, so const n = xs.length; if (n !== 0) { const j = n - 1; xs[j] } was proved in range and indexed xs[-2147483633] with no check (SIGSEGV). A string of that size loses substring's clamp the same way and copies 2 GB from before its start |
Fixed (#427), at the last source: join. The runtime stage had closed readFileBytesSync, readFileSync, concatenation and nish_alloc_array (RT-1, RT-2, RT-7); emitJoin now compares the summed total with 2^31 − 1 once the lengths are added and, for a longer one, asks the allocator for 2^62 bytes instead of the total (a select, so the copy loop is unchanged). No malloc returns such a block, so nish_arena_grow fails it as RT-2's concatenation fails: nish: out of memory, exit 1, in either number mode, before anything is allocated; a result of exactly 2^31 − 1 bytes is still made. With every source bounded, no array or string can pass 2^31 − 1 elements or bytes, so the prover's trust in .length being non-negative under i32 mode holds. Tests: tests/link/cg_sec_join_limit (32 copies of a 64 MiB separator, 2^31 + 33 bytes: before, length read −2147483615; now the out-of-memory exit), tests/cases/cg_sec_join_limit (the compare and the select in the IR, and a join that fits). K1-3's tests/link/crypto_base64url_long_f64 built its 2^31 + 4 byte text with join, which is now refused, so it pins that refusal instead |
| CG-5 | High | src/escape.ts:126 (isAllocatingBuiltin), :470 (visitCall), :1577 (PassWalk.isOld), :911 (handsOutElements), :184 and src/attributes.ts:399 (returnsFreshElements) (lines at 2183bd3, #520's merge) |
readdirSync answers an array whose element strings were bumped by the same call. The scope rules assume a pointer read out of memory was not allocated with it, so const names = readdirSync(d); return names[0] left first with an arena scope that released the name before the caller read it (CORRUPTED, length 1364283729), and keep = names[0] in a loop pass did the same through the per-pass scope |
Fixed. A listing's elements now flow as the listing (isListingCall, the listing mode of flowTarget/assignedLocal), and a pass's element read of a listing it made is not old (isPassListing). The original fix moved no corpus program's IR. Tests: tests/cases/cg_sec_readdir_return, cg_sec_readdir_pass. Since #520 the same rule is followed through callers, which closes four more ways a name could outlive a scope that released it: a wrapper that returns the listing on (listOf, so keep = listOf(dir)[0] in a loop is a listing read, not an old value); a listing passed to a function that answers one of its names (pick calling firstOf(names)); a name assigned to a local that is then returned (named); and a name stored into a field (log.name = names[0]). returnsFreshElements (src/attributes.ts) marks a function whose returned array holds elements the call allocated, isListingCall reads it at the call site, and handsOutElements keeps the conservative answer when an array is handed to anything the walk does not follow (an argument, pop, or any use but .length, join, indexOf and push). Each name is read back intact after churn has reused every byte a wrong release would have freed. Tests: tests/cases/mem_return_array_readdir (all four shapes). The carried-element rule is string-only. Only an array of string or string | null is carried with a returned array: a string is one flat block, so following the elements follows all of it. An array or an object holds pointers of its own and no caller follows a second level down, so a pushed row keeps escaping as it always did. Four nested-listing shapes (a row bound to a local, a for...of over the rows, a function that answers a row's first string, a return inside the loop) were a reproduced use-after-free during review before the rule was narrowed to strings. Test: tests/cases/mem_return_array_nested. A precision loss, not a regression: cg_sec_readdir_pass's @test no longer releases its arena at function exit, because its name now flows with the listing; the golden lost the nish_arena_mark and nish_arena_release calls. That is the conservative direction (memory is held longer, never released early), and the test still pins that the kept name reads back intact. #520 moved a second golden the other way: tests/cases/mem_loop_scope_forof.ll gained a nish_arena_mark/nish_arena_keep pair around the lastWord(30) call, a tighter scope, while the outer release stays |
| CG-6 | High | src/emit-result.ts:538 (emitOrReturn, root); src/parallel.ts (walkRegion) |
r.orReturn() inside a scope() block returned without joining it: the task stayed in the thread's list, and the next scope's join ran it, writing through a destination pointer into memory the first function's arena scope had released, which by then held another function's array (1 5 where 1 5005 is right) |
Fixed by refusal. regionCallMessage refuses a Result's orReturn (resultMethodName) between a scope's first spawn and the end of its block (NL2394, the region rule). The emitter fix — emitScopeJoins before emitScopeExit in both propagate arms of emitOrReturn — is in src/emit-result.ts, outside this stage, and would let the refusal go. Test: tests/cases/cg_sec_scope_or_return |
| CG-12 | High | src/escape.ts:464 (visit), :1265 (localOutcome); src/attributes.ts:2880 (FactCollector.visit), :1930 (noteCaptures), :1551 (isJoinedParts) (lines at this change, on e9716842) |
Found and fixed in the change that let an arrow given to a function parameter read the caller's const locals, before it reached main. The capture is handed to the instance as an extra parameter (%cap.N) that no fact describes, and both passes skip an arrow's body as a separate function, so neither saw the capture as a use of the outer local. A value the arrow stored through a capture could be released while the caller still held it: in mem_join_parts_captured, atLast(n, (i) => { log.last = parts[i] }) did not count as a use of parts, so join released the parts as its single use, and log.last printed <1.0> followed by reused bytes once churn ran. The attributes pass saw the same blind spot: a parameter whose only use is a capture the arrow pushes to or stores, such as fill's keep and boxes, read as readonly nocapture |
Fixed in the same change. A const local an arrow argument captures (noteCaptures) is an escape in localOutcome and in the attributes pass, which takes readonly and nocapture from a captured parameter (escapeParam); isJoinedParts refuses a parts array any arrow names. Only an arrow given to an ordinary function parameter counts (FunctionSig.capturesForCall): a data-parallel form's or a task's captures are read-only and stay inside the call by that form's rules, and their goldens (tests/link/par_capture, par_capture_large, par_map_captured_strings) did not move. Tests: tests/cases/mem_join_parts_captured (the part kept through a capture reads back <1.0> after churn), tests/cases/fnarg_capture_escape (strings and objects pushed through captures read back intact after churn; @fill's keep and boxes carried neither readonly nor nocapture). Since CG-13 a capture is an argument to the arrow rather than an escape: keep and boxes, which the arrow pushes onto but never stores, are nocapture and still not readonly, and what the arrow pushes still escapes |
| CG-13 | High | src/parallel.ts (captureTarget, forwardsOnly); src/escape.ts (captureOutcome, localOutcome, storedIntoReturnedArray, analyzeEscapes); src/attributes.ts (noteCaptures, noteCaptured); src/emit.ts (captureParamAttributes) |
Found in review of the change that reads a capture as an argument to the arrow, before it reached main. CG-12's fix made every capture an escape (localOutcome answered FLOW_LEAKS for a captured local). Reading it as an argument instead lets a captured local be local, which two host rules then accept without ever seeing the arrow. Both rules decide by walking the function's own references (refsOf), and visit stops at NodeKind.Arrow. One is storedIntoReturnedArray's carrier rule (isCarrierUse): a string[] a function fills, captures and returns would carry its strings to the caller while the arrow kept one in an older object. The other is the element rule for a captured listing: a lifted arrow's elementsFree was never decided (analyzeEscapes skipped decideElementParams for a lifted function), so it said nothing about whether the arrow keeps an element. With the carrier guard left out, mem_capture_element_keep's log.last printed [6.0], another pass's bytes, where <1.0> is right |
Fixed in the same change. storedIntoReturnedArray refuses a carrier any arrow captures. analyzeEscapes decides elementsFree for an ordinary arrow's capture parameters (its written ones keep the conservative answer), and captureOutcome makes a captured listing leak unless the arrow proved that parameter free. isJoinedParts keeps refusing a parts array any arrow names, because what decides that release is order, not escape. A capture has a target (captureTarget) only when every function on the way from the call to the arrow is an ordinary instance that only forwards it: a data-parallel form, a chunk loop, a spawn, a task, an async instance and a collections or JSON intrinsic each refuse it, and so does an async arrow, and the capture is then the escape CG-12 made it. Every function the instance's body hands the capture to is walked, not only the arrow, since an ordinary instance may forward the arrow into a parallel one. An object a capture leaves local may be an alloca because a call that passes captures is never a tail call (planTailCall in src/emit.ts) and the arrow runs before it returns. Tests: tests/cases/mem_capture_element_keep (a returned carrier, a captured listing and an array of objects, each element kept by the arrow reading back after churn), mem_capture_forward_keep (forwarded through a second instance), mem_capture_callee_keep (kept by a function the arrow calls), mem_capture_async (an async instance: no alloca), tests/link/mem_capture_parallel_forward (forwarded into parallelMap: every %cap.0 noundef alone, the host's k neither readonly nor nocapture, as before the change) |
| CG-7 | Medium | src/parallel.ts:1035 (collectUses) |
A task argument read out of a variable (s.spawn(sumPt, ps[0], out, 0)) left ps private, so ps[0] = { x: 100, y: 200 } before the join was accepted. A record element is the address of its slot and the task reads it at the join, so the native answer was 300 where Node prints 3, and the two raced under --threads |
Fixed. handOnRoot hands the root variable of such an argument on (through each arm of a ?: or ?? too), and the region refuses the store. tests/link/thread_scope_many_arrays (rows[k] as an argument) still compiles. Test: tests/cases/cg_sec_scope_record_arg |
| CG-2 | Medium | src/runtime.ts:808 (inlineAllocator); src/emit-arrays.ts:1017 |
A negative i32 n in new Array<T>(n) became a byte count past 2^63. The inline allocator adds 7 and adds the offset without an overflow check, so the bump "fits", moves the arena offset backwards, and the memset of ~2^64 bytes writes until it faults. The comment said the arena aborts; it does not. A crash on input (new Array<u8>(parseInt(field))) |
Fixed (#427), by checking n in the IR rather than in the allocator: newArrayLengthChecked now asks for the check on an i32 n (in either number mode; a ranged local is read as an i32, so it is checked too), so emitNewArrayLength's one unsigned compare against the limit refuses a negative n as it refuses one too large, with array length out of range, before anything is rounded or allocated. A literal up to 2^31 − 1 and a narrower unsigned stay unchecked. collectArrayFacts reads the same predicate, so willreturn is taken exactly where the panic is. Every new Array(n) with an i32 n in the corpus gained the compare, std/collections.ts's map and set tables among them (97 tests/cases goldens). Tests: tests/cases/cg_sec_new_array_negative and its _f64 twin (each refused length in a child process, the message pinned), tests/link/cg_sec_new_array_negative; tests/cases/cg_sec_new_array_guard's plain array now shows the compare |
| CG-4 | Medium | src/attributes.ts:439, :1813, propagateCallee |
willReturn starts true and only a non-returning callee clears it, so a function on a call-graph cycle kept willreturn: spin(x) calling itself with the same x was willreturn readnone, and opt -O2 deleted the call, so a program that should hang printed returned and exited 0. Mutual recursion behaves the same. docs/ARCHITECTURE.md says unbounded recursion is allowed by LangRef; it is not |
Fixed (#427). clearRecursiveWillReturn in src/attributes.ts runs before every propagate: it finds the strongly connected components of the user call graph (Tarjan's algorithm, its state kept on each function's facts) and takes willReturn from every member of a component with more than one function and from every function that calls itself, and the fixpoint then takes it from their callers. No proof that a recursion ends is attempted, as LLVM's FunctionAttrs attempts none. docs/ARCHITECTURE.md's willreturn row now says so. Seven tests/cases goldens moved (arr_range_call, cf_fib, cls_this_method_call, fn_arrow, fn_arrow_hoisting, gen_recursive_ground, mem_callee_scope). Tests: tests/cases/cg_sec_recursion_willreturn (a self and a mutual recursion that never end, each run in a child process that must die rather than return, and a recursion that ends, which loses the attribute too) |
| CG-8 | Low | src/runtime.ts:337, :350, :353 |
nish_read_file, nish_write_file and nish_append_file are declared willreturn, but runtime-os.c _exit(1)s on a missing or unwritable file and open() blocks on a FIFO with no writer; every caller inherits willreturn. The allocator's OOM exit is the same pattern, and so is nish_array_grow's new refusal |
Fixed (#427). No miscompile had been observed, because the calls write memory and LLVM cannot delete them, but the attribute was a claim the runtime does not keep. src/runtime.ts declares nish_read_file, nish_write_file, nish_append_file, nish_str_concat and nish_alloc_array nounwind without willreturn (mayNotReturn), and nish_read_file_or_null and nish_read_file_bytes too, since every reader blocks in open() on a FIFO with no writer; the fixpoint then takes willreturn from every caller. Each declaration's comment says why. The allocator's own out-of-memory exit (nish_arena_grow, and so nish_alloc_struct) keeps willreturn: exhausting memory is not modelled, and every allocating function would otherwise lose it. Tests: tests/cases/cg_sec_exiting_runtime (the declarations and four callers, and a run) |
| CG-9 | Low | runtime/runtime-wasm.c:61 |
The wasm32 runtime's nish_alloc_struct rounds and adds without an overflow check, the same shape as CG-2 |
Open, for the runtime stage. Since fixed there as RT-7 (docs/security/runtime.md, tests/link/rt_sec_wasm_arena) |
| CG-10 | Low | src/emit-arrays.ts:1059 (emitElementAssignment) |
xs[0] += grow(xs) computes the slot's address before evaluating the right side, so when grow pushes until xs moves, the store lands in the old block: 1 where JavaScript gives 6. zs[2] += shrink(zs) stores past the new length, inside the old capacity. Arena memory is not freed, so neither is a memory error |
Fixed (#427). emitElementAssignment keeps JavaScript's order (array, index, check, load, right side) and, when the right side can resize the array (rightSideMayResize: a push, a pop, a call the fixpoint says resizes, or a new of a class), checks the index again against the length the right side left and takes the slot's address again before the store. Since CG-11 the predicate is mayResize, which counts a new only when its constructor resizes. A hoisted header and an inline field are left as they were: neither can move. Only programs whose right side can resize change, so no existing golden moved; the plain xs[i] = e already evaluates e before its check and address. collectArrayFacts lists the second check's panic wherever the first was proved away and the right side calls anything, so willreturn cannot survive it. Tests: tests/cases/cg_sec_compound_element_order (+=, *= and ` |
| CG-11 | Low | src/emit-arrays.ts:544 (callMayResize); src/attributes.ts:3205 (bodyMayExtend) (lines at 69e5fe8) |
A loop's array header is hoisted only when nothing in the loop can move it, and the question asked a call's callee but not a new's constructor, though the checker records it for the new in nodeCallees too. A while over xs that runs new P(xs), whose constructor pushes until xs moves, kept the len and data it loaded before the loop: 6 where JavaScript gives 706 (#435). isCountedLoop asked the same question without the constructor, so a for...of whose body runs such a new on every pass, and so never ends over a non-empty array, was willreturn. Arena memory is not freed, so the stale block is a wrong answer rather than a memory error |
Fixed (#435). callMayResize and bodyMayExtend read the callee nodeCallees holds for a new as they do for a call, and so its constructor's fixpoint resizesArray fact; a class with no constructor stores constants only. CG-10's rightSideMayResize counted every new of a class as resizing, so it folds into the same predicate, mayResize, which narrows it to the constructors that resize. Two kinds of code change. A loop whose body runs a new whose constructor resizes now reloads its header on every pass, or loses willreturn. A compound element store whose right side runs a new whose constructor does not resize now checks its slot and takes its address once, where CG-10 did both a second time. Against main's compiler, no golden and no corpus program but the new case moved. Tests: tests/cases/cg_sec_hoist_new_resize (the #435 loop reloads its header each pass and prints what Node prints, 706; a for...of over the same constructor prints 706; new Q(xs), whose constructor only reads, keeps the hoist; forOfGrows is not willreturn; xs[0] += new Q(xs).n stores into the slot it read with no second check) |
The generated-program pass
No miscompile and no unsound acceptance was found, so this pass adds no row
to the table. On x86-64 at 3313da3, with --asan:
| Seed | Programs | Ending one-past | Agree | Differ / unexpected / ASan | Time (4 lanes) |
|---|---|---|---|---|---|
| 20261024 | 6 000 | 2 980 | 6 000 | 0 / 0 / 0 | 734 s |
| 3141592653 | 6 000 | 2 996 | 6 000 | 0 / 0 / 0 | 749 s |
Each family was in 1 444 to 1 554 of seed 20261024's programs and ended
346 to 398 of them one-past; seed 3141592653's were in 1 458 to 1 594
and 353 to 403. The wiring was checked against a compiler that drops every
bounds check unless --no-elision is passed: over six programs it reported
the two that end one-past in an elided access (derived:addlit!,
derived:u16!) as DIFFER, with an ASan heap-buffer-overflow as the
witness, and reduced them to 21 of 32 and 20 of 23 lines.
What this does not cover: the shapes are proofgen's, so a rule the generator
never exercises (an elision added after it, or a combination its blocks do
not form) is not tested; PROOF_MISSES shapes prove nothing to remove; an
ASAN_BLIND one-past read is caught only by the panic check, not by ASan; and
the aarch64 row of CI is the only run on that target.
Status after the runtime stage
The runtime stage (runtime.md) merged after this record was
written and changed three of the dispositions above. The table keeps what this
stage found and did; this section is what is true now.
-
CG-9 is fixed (RT-7): the wasm32 runtime's
nish_alloc_structandnish_arena_growrefuse a size that would overflow. -
CG-3's runtime sources are closed (RT-1, RT-2, RT-7):
readFileSync,readFileSyncOrNullandreadFileBytesSynctreat a file longer than 2^31 − 1 bytes as unreadable, a concatenation or template past that length fails as an allocation does, and both runtimes'nish_alloc_arrayrefuse such a length. Onlyjoinremains (src/emit-arrays.ts), and CG-3 stays open, High, for it. K1-6's residue is the samejoinhalf. Since closed too (#427): ajoinpast 2^31 − 1 bytes fails as a concatenation does, so CG-3 and K1-6 are fixed. -
CG-8 grew:
nish_str_concatandnish_alloc_arraycan now exit, as the allocator always could, so theirwillreturnis the same approximation. Since fixed with the file calls (#427): none of them iswillreturnnow.
CG-6's emitter half is tracked in #382. CG-2, CG-3, CG-4, CG-8 and CG-10 are fixed (#427), CG-11 is fixed (#435), and CG-12 and CG-13 were fixed in the changes that introduced them.
Properties verified
| Property | How it holds | Pinned by |
|---|---|---|
A length new Array cannot hold is refused before anything is allocated, in both modes |
the compare is the first thing after the length is evaluated | tests/cases/cg_sec_new_array_guard (the IR and a run), tests/link/cg_sec_new_array_* |
| No push takes an array past 2^31 − 1 elements | nish_array_grow clamps the capacity and refuses a full array |
tests/link/cg_sec_push_limit, tests/runtime-test.c |
A narrower unsigned and a literal are not checked; an i32, a ranged local among them, is, since CG-2 |
newArrayLengthChecked |
tests/cases/cg_sec_new_array_guard (the plain and literal arrays), tests/cases/cg_sec_new_array_negative |
An index proved by its declared range (u8 into 256 elements, u16 into 65 536) is zero-extended and in range |
convertedRange |
tests/cases/arr_bounds_ranged |
An offset index w[i + c] is proved only where the sum is exact (a signed add) and i >= 0 is known, with a reach of at least c or a literal bound that c more still fits (#561, lines at a6705ed) |
offsetIndex and proves in src/bounds.ts |
tests/cases/arr_bounds_offset, and arr_bounds_offset_reach and _floor, which keep their check and panic |
A computed index is proved by its range only where the arithmetic is exact (a signed i32 or i64), with nothing inside it writing, and against the length its own evaluation left. This makes valueRange, which until then decided only nsw and the overflow checks, a memory-safety proof: a range that is too narrow is now an out-of-bounds access, so a change to it is reviewed as one |
provesByRange and valueRange in src/bounds.ts |
tests/cases/arr_bounds_range, and arr_bounds_range_past, _negative, _call and _new (a constructor reached by new), which keep their check and panic, and _kept, which keeps theirs |
A call gives its array a length only where the callee is a plain function whose body, read as written, builds a fresh array, lets nothing but indexing, .length and push touch it, and returns it; with no arrow, nested function, class or try in the body; with each size a literal, a constant of the caller's own module, or a parameter the body never declares again or writes. A field store takes the length only through this or a const local, which the call cannot rebind. The callee's side tables are never read, so the rule holds whatever order the bodies are checked in |
returnedLength and storedLength in src/bounds.ts |
tests/cases/arr_bounds_returned, and arr_bounds_returned_pop, _passed, _stored, _least, _rebind, _shadow and _shadow_param, which keep their check and panic, and _kept, which keeps its seven |
A helper's array keeps its length through a call only where the callee is a plain function of the caller's own module, named by a name the calling body does not declare, whose parameter is only indexed, read for .length, pushed to, or handed on to another such parameter, and is never returned or stored. A parameter already being followed is taken to keep the length, which is sound because the walk reaches every body of the cycle and a shrink needs a pop or a store there; the walk stops, refusing, past 8 functions. An answer is remembered on the function only when it rested on neither assumption, since one drawn while a cycle was open can be wrong once the cycle closes |
passesKeepingLength and keepsParameter in src/bounds.ts, FunctionSig.keepsLength |
tests/cases/arr_bounds_returned_through, and arr_bounds_returned_through_return, _through_deep, _through_cycle, _through_store, _through_param and _through_memo, which keep their check and panic, and tests/link/arr_bounds_returned_import, which keeps its check |
| A compound element store whose right side resizes the array stores into it as the right side left it, checked again | mayResize in src/emit-arrays.ts |
tests/cases/cg_sec_compound_element_order |
A loop's array header is hoisted only out of a loop nothing in it resizes, a new whose constructor resizes included |
mayResize in src/emit-arrays.ts, reading the constructor's resizesArray |
tests/cases/cg_sec_hoist_new_resize, arr_header_hoist |
A bound re-read after pop, push or a shrinking callee keeps its check |
the checker's prover (src/bounds.ts) drops length facts at a push, a pop and a call whose summary may resize (callSummary); a foreign callee has no summary, so it forgets every length. It does not read resizesArray, the emitter's fact |
tests/cases/arr_bounds_shrink_panic, arr_bounds_store_rhs |
for...of re-reads the length every pass |
the lowering, not a proof | tests/cases/arr_for_of |
| A call through an instantiation with a function argument takes no entry facts from it | the summaries are per instance | tests/cases/arr_bounds_generic_instances* |
willreturn is cleared by a reachable panic, trap, expect or checked charCodeAt, and kept by substring's clamp |
hasTrap, callsNoReturn |
tests/cases/attr_panic_charcodeat, tests/cases/dump_shared_write_panic |
No function on a call-graph cycle is willreturn, and neither is a caller of one |
clearRecursiveWillReturn in src/attributes.ts, then the fixpoint |
tests/cases/cg_sec_recursion_willreturn |
No runtime call that can exit or block on its input is willreturn, and neither is a caller of one |
mayNotReturn in src/runtime.ts, then the fixpoint |
tests/cases/cg_sec_exiting_runtime |
nocapture is withheld from a returned this, an identity function's parameter, a parameter a method stores, and one handed out through Ok, an interface literal or an array literal |
escaping, pointerParams |
tests/cases/mem_callee_scope_escape, mem_callee_scope_return |
| A capture escapes iff the arrow keeps it, or the chain from the call to the arrow is not ordinary instances only; an element of a captured array is kept unless the arrow proved it free, and a captured array is never a carrier | captureTarget in src/parallel.ts; captureOutcome, storedIntoReturnedArray and decideElementParams in src/escape.ts; noteCaptured in src/attributes.ts |
tests/cases/mem_capture_*, fnarg_capture_readonly, fnarg_capture_escape, mem_join_parts_captured, tests/link/mem_capture_parallel_forward, fnarg_capture_forward |
| A callee that pushes into or stores into a parameter denies its caller an arena scope | allocEscapes propagated |
tests/cases/mem_callee_scope*, mem_loop_scope_escape |
| Every allocating builtin is an allocation site | isAllocatingBuiltin |
tests/cases/mem_read_or_null_scope, mem_getenv_scope, mem_readdir_scope, mem_read_import_scope, and now cg_sec_readdir_* |
nsw appears only on signed add/sub/mul, and never on a nish:unsafe wrapping* call |
intOpcode in src/emit-ops.ts |
tests/cases/opt_nsw, unsafe_wrapping |
| A parallel body writes nothing its caller can see, through any alias the facts know | sharedWrite |
tests/cases/reject_par_shared_write, reject_par_shared_write_via |
dst is not reachable from an element of src |
reachingPath |
tests/cases/reject_par_reaches_dst |
Between a scope's first spawn and its join the parent neither reads a destination nor writes what a task reads, and does not return early through orReturn |
walkRegion |
tests/cases/reject_thread_region_*, cg_sec_scope_or_return, cg_sec_scope_record_arg |
break, continue and return join every scope they leave; a spawn argument allocated in a pass lives until the join |
emitScopeJoins |
tests/link/thread_scope_exit_paths, thread_scope_many_arrays |
join writes no byte past the result it allocated: a one-byte part is one load i8 and one store i8 at the cursor, which the summed total already counts (the length is the part's own i64 header, tested == 1, not a guess), and every other part is the memcpy of its length it always was. Nothing is read through the byte, so a secret part (a base64url character) is stored, never used as an address |
emitJoin in src/emit-arrays.ts |
tests/cases/str_join_byte_parts (one-byte parts end to end, mixed with empty and longer parts, between separators, last before the NUL, the top ASCII byte and a NUL byte, an empty array) |
The partition in runtime-parallel.c is contiguous and computed in i64, and nested regions run sequentially |
the runtime | tests/link/par_map_large, par_reduce_blocks |
Doc corrections for the security-policy stage
-
docs/LANGUAGE.md, the array table:push"grows capacity by doubling" should add that an array never grows past 2^31 − 1 elements, in either number mode, and that the push that would fails as an allocation does (nish: out of memory, exit 1).new Array(n)should say that a length past 2^31 − 1 under i32 mode, past 2^53 under f64, a negativei64or a NaN panics witharray length out of range. -
docs/LANGUAGE.md,usingandscope():orReturnis refused between a scope's firstspawnand the end of its block, and so is a store into a variable whose element or field was handed to a task. -
docs/ARCHITECTURE.md, "Attribute soundness rules": thewillreturnrow's "unbounded recursion is allowed by LangRef" is wrong (CG-4; since corrected with the fix, #427); and thenonnull align 8row should say that an inline record of 4-byte fields is passedalign 4. -
std/README.md(crypto): the K1-6 caveat fromcrypto-k1.mdnow reads: an array built bypushornew Arraycannot pass 2^31 − 1 elements, but one read byreadFileBytesSync, and a string read byreadFileSyncor built byjoin, still can, and under i32 mode itslengthis wrong (CG-3). Since every source is bounded (#427), the caveat can go: nothing passes 2^31 − 1. Done:std/README.mdnow says so. -
tests/nish-cmp.js: this stage's IR changes (the eight*_long_f64crypto programs, whosenew Array(n)takes anumbernunder f64 mode) are admitted today only by the existing every-program declaration about!tbaaelement tags, which admits any difference in any file. A declaration of their own would keep the next unrelated difference visible.Since made moot: the reference is now 0.16.0, which carries these changes, so they no longer differ, and the four every-program declarations went with them. The one difference the
!tbaadeclaration was still absorbing was the output name of astd/module the seed reached under its own install (the twocrypto_x25519link programs), whichtests/nish-cmp.jsnow sets aside as it does that root inside a file.

