KeyFuse: Falsification-First Cache-Key Auditing with Minimal Collision Witnesses and Conservative Key Repair

A build cache is a bet that the declared key names everything the build reads. The Nx team's "Can You Trust Your Build Cache?" describes remote cache poisoning and stale-hit classes that follow from keying on declared inputs; expo/expo issue #30930 and facebook/metro issue #918 document Metro cache-key collisions around custom transformers and external inputs; gradle/gradle issue #16144 documents build-cache key normalization problems; and the Gradle and Turborepo documentation devotes entire pages to environment variables that silently enter or fail to enter keys. In each case the failure shape is the same: two builds share a key, produce different outputs, and the cache is confident.

KeyFuse is a falsification-first auditor for that shape. It does not attempt to synthesize a correct key and it does not claim one. Given a deterministic oracle over a finite typed slot universe, a baseline assignment, and a declared input list, it runs one of five probe strategies, records every row whose output differs from the baseline, and reports what it detected: a minimal collision witness pair whose two assignments differ at exactly one slot and whose outputs differ, with per-slot necessity checked at the recorded witness context, and a repaired key over declared union implicated. The witness is the product; the repair is the intervention that follows from detected dependence when the inputs cannot be declared properly — a third-party plugin, a generated config, a vendored tool.

• Typed slot universe: file, env, cwd, locale, timezone, rng, clock, with frozen name forms and baseline/top/sentinel values; slots outside the universe are misses, not defaults.
• Five probe strategies: baseline-toggle, single-trace, ca, ca-ddmin (fallback), cover-with-defaults (default), all deterministic and budget-bounded at 4,096 oracle calls.
• Minimal collision witness: same declared key, different outputs, differing set of size 1, necessity verified at the witness context; 1-minimality of minimized supports verified by exhaustive single-coordinate removal.
• Conservative key repair: declared union implicated, hashed into a 64-bit FNV identifier; a repaired key is a conservative over-approximation of detected dependence, not a guarantee.
• Ground truth by brute force: 24 pure tasks, 408 binary assignments (651 with sentinels), relevantT(1..3), relevantGlobal, and every same-declared-key collision pair enumerated.
• Measured failures reported in place: masking (C1), the anchoring counterexample (C5), value-specific effects (C8), and non-1-minimal minimized witnesses (C9).

The falsification framing is deliberate. The blueprint for this wave was reviewed three times, and the reviews produced corrections C1–C9 that this paper restates as ground truth wherever an earlier draft differed. Two of the corrections killed originally stated claims (C1 covering arrays do not detect every effect; C5 union-of-implicants is not sound without anchoring), and one changed the shipped default after the build (the minimizer-first arm reduced a changing Metro row to the key slot and never emitted the undeclared witness, so the exact arm became the default). The negative results are part of the contribution, not an appendix to it.

Hermetic build systems are the closest prior art. Nix builds in isolation from a hash of declared dependencies; Bazel sandboxes actions and documents hermeticity as the property that an action's inputs are fully declared; Gradle's configuration cache and build cache document environment-variable tracking; Turborepo documents environment gotchas for cache keys. Those systems make keys from declarations. KeyFuse measures the gap between declarations and reads, and the specific slots it targets are the ones a sandbox or a file tracer cannot see: env, cwd, locale, timezone, clock, rng. This is a complement to sandboxing, not a replacement, and no comparison against sandboxes is claimed.

Combinatorial interaction testing supplies the covering-array machinery: Kuhn, Kacker, and Lei's NIST SP 800-142 is the reference for t-way arrays and their practical adequacy. KeyFuse's array construction is a deterministic AETG-style greedy with no RNG, and the paper's use of it is deliberately modest: the array is a cheap sampler whose misses are reported, and its own tuple coverage is verified rather than assumed. Delta debugging (Zeller and Hildebrandt, 2002) supplies the minimization loop; KeyFuse keeps ddmin but replaces its 1-minimality guarantee, which does not apply under non-monotone output differences, with an exhaustive single-coordinate removal check. Reproducibility tooling (reprotest, reproducible-builds) varies build environment to expose unreproducible output; KeyFuse varies a typed slot universe and attributes the change to a specific slot. Record/replay and tracing (rr, strace) capture real reads at syscall or process level; KeyFuse's adapters are facade interposition, which is wrapper-level and cannot see native, mmap, subprocess, or network reads — an explicit limit, not an oversight. Finally, differential testing (McKeeman, 1998) and the mutation-testing line (DeMillo, Lipton, and Sayward, 1978; Jia and Harman, 2011; Papadakis et al., 2019; Just et al., 2014; Inozemtseva and Holmes, 2014) share the habit of judging a program by observed behavior differences; KeyFuse's object is a key collision rather than a mutant score, and it borrows the discipline of measuring what was observed and nothing more.

A slot is a frozen string name `kind:id` over seven kinds. Each slot has a baseline value, a top value, and optional sentinel values (boundary values used only where declared). The universe is finite, typed, and validated: unique names, non-empty baseline and top, baseline minimum for ordered slots, and n <= KEYFUSE_MAX_SLOTS = 12. A read of a slot outside the universe is recorded as a miss, not silently defaulted. File names carry a relative path (a directory listing uses a trailing slash); env names an environment variable, with absence represented by the distinct sentinel string `A` + NUL + `absent`, never confused with empty; cwd, locale, timezone, rng, and clock are singleton slots whose values are interpreted by injected facades.

assignment a : slot -> value; supp(a, b) = { i : a[i] != b[i] }; ||supp(a,b)|| = d_H(a, b). i is t-relevant iff some a with d_H(a, b) <= t has i in supp(a, b), f(a) != f(b), and resetting i to b[i] (all other coordinates at a) changes the output back. relevantT(t) is the set of t-relevant slots; relevantGlobal is the same existential with no Hamming cap.

originalKey(a) = keyfuseKey(taskId, version, declared, a); witness = (left, right) with supp = { i }, outputLeft != outputRight; keyCollision = originalKey(left) == originalKey(right); repairedKey(a) = keyfuseKey(taskId, version, declared union implicated, a); separated = repairedKey(left) != repairedKey(right).

The anchor assumption is stated as an assumption in the engine docblock, in the paper, and in the UI: every output difference must have a witness reachable by a <=t-support displacement from the baseline that includes a differing slot. It is not a theorem. The counterexample is task threshold-3: f = 1 iff abs(x) >= 3 over four slots with baseline 0. Every slot is globally relevant, but no <=2-support displacement from the baseline changes the output; at strength 2 the audit detects nothing, the certificate is the weak string, and the enumerated residual is reported (55 pairs at strength 2, 12 of them Hamming-1 minimal, 1 documented by name). Masking is a separate demonstrated failure: for f = (a AND b) XOR c with baseline (0,0,0), a strength-2 array can realize (a=1,b=1) only with c=1, where the output equals the baseline, so the pair is missed. The pinned hand array shows changedRows=3 with zero joint-support rows for (a,b); the exact arm finds env:A and env:B, and the array arm records both misses.

export interface WitnessPair {
  readonly left: Assignment;                  // recorded row (witness context)
  readonly right: Assignment;                 // left with one slot collapsed
  readonly differing: readonly string[];      // exactly one slot
  readonly outputLeft: string;
  readonly outputRight: string;
  readonly originalKeyLeft: string;           // key over declared inputs
  readonly originalKeyRight: string;
  readonly repairedKeyLeft: string;           // key over declared union implicated
  readonly repairedKeyRight: string;
  readonly keyCollision: boolean;             // original keys equal and outputs differ
  readonly separated: boolean;                // repaired keys differ
}

export interface Detection {
  readonly slot: string;
  readonly kind: SlotKind;
  readonly witness: WitnessPair;              // per-slot witness-context pair
  readonly minimized: MinimizedWitness | null; // row-level minimized support
  readonly necessary: boolean;                // false is possible in the ca arm
}

Every strategy executes the baseline row first and then rows assigned from the universe. The audit layer, not the probe, interprets rows: it filters changing rows, runs minimization where the strategy requires it, checks per-slot necessity, dedupes detections by slot in deterministic row order, and builds the repair over the deduped set. Detections are evidence, never a claim that no other dependence exists.

If every slot domain is totally ordered with the baseline as minimum and f is coordinatewise monotone, then a strength-t covering array over {baseline, top} detects all <=t-support baseline effects at O(v^t log n) runs.

exact <=t detection: Theta( sum_{j<=t} C(n,j) (v-1)^j ) non-baseline points (uniform v), or sum over subsets S with card(S)<=t of prod_{i in S} (v_i - 1) with per-slot counts. cover-with-defaults enumerates exactly these points and is the exact general method; a strength-t CA is a cheap approximation whose misses must be reported.

N = O(v^t log n + r*n) oracle calls for r changing rows: gate 4 + probe rows + ddmin + necessity checks + fixpoint re-runs. certificate = "no detected <=t-support effect at covered tuples"; truncated = "budget exhausted before coverage completed". UI copy never strengthens either string.

Necessity (C6) is checked on the recorded pair. For a changing row r and slot i in its differing set, the audit runs collapse(r, i) — all other coordinates kept at r's values — and asks whether the output moves. If it does, i is necessary at r's witness context and the pair (r, collapse(r,i)) is the recorded witness. This is O(card(K)) runs, stronger and cheaper than replaying array rows, and it is the check that catches over-implication in the unminimized ca arm: on and-2way at strength 2 the ca arm reports env:A and env:B as necessary but also env:D, whose collapse leaves the output unchanged; env:D is a false implicate and is marked necessary:false.

The witness is the paper's centerpiece artifact. For every changing probe row, ca-ddmin delta-debugs the differing set: split it by slot-name-sorted halves, collapse coordinates to baseline while keeping the output different from the baseline output, then verify 1-minimality by exhaustive single-coordinate removal. The minimizer's contract is the exhaustive pass, not ddmin's internal stop (C9): output-difference is not monotone under shrinking non-key coordinates, so ddmin can stop early or overshoot, and the verifier is what decides.

// For each changing row r and each slot i in r's minimized support S:
//   right = collapse(r, i)            // every other coordinate stays at r's value
//   necessary = output(right) != output(r)
//   pair = { left: r, right, differing: [i] }
//   keyCollision = originalKey(r) == originalKey(right) && output(r) != output(right)
//   separated    = repairedKey(r) != repairedKey(right)
//
// 1-minimality after ddmin: for each removable subset, collapse to baseline;
// oneMinimal = every single-coordinate removal restores the baseline output;
// verifyRuns is reported per final pass and must equal the support size
// when oneMinimal is true.

Across 360 audits the evidence harness records 521 detections: baseline-toggle 99, ca 203, cover-with-defaults 136, and 83 minimized witnesses from the ca-ddmin arm. The 438 non-minimized detections carry 348 single-slot necessity verifications. Of the 83 minimized witnesses, 81 verify 1-minimal; 2 are flagged and reported, both on maj-3way at strength 3 with support [env:B, env:C, env:E], passes=0 and verifyRuns=3 (the split-based minimizer cannot isolate the 3-subset from that row, and the exhaustive verifier says so). There are 0 verifyRuns mismatches. The gate checks 219 exact and ca-ddmin detections for single-slot witness violations: 0. It counts 101 collision witnesses, of which 0 are unseparated after repair.

implicated = { i : some changing row has i necessary at its witness context }; repairedInputs = sorted(declared union implicated); repairedKey(a) = keyfuseKey(taskId, version, repairedInputs, a). Separation is checked per recorded witness: original keys equal and outputs differ must imply repaired keys differ.

The corpus is 24 pure tasks over 14 families, with universe sizes 3 through 6 on this frozen corpus (the engine bound is 12) and one sentinel value on the port task. Ground truth comes from exhaustive enumeration: 408 binary assignments plus sentinels, 651 full product assignments, relevantT(1), relevantT(2), relevantT(3), relevantGlobal, and every unordered pair with equal declared-key inputs and different outputs (1,533 pairs across the corpus). Brute force is exact at these sizes; no sampling is involved. The evidence script runs all five strategies at strengths 1, 2, and 3 over every task — 24 x 15 = 360 audits — and writes a byte-stable JSON artifact whose digest is 2213e158e53ff94f.

The five decisive experiments from the plan, as measured. (a) Metro end to end: the exact arm detects env:API_URL in metro-env-1, the recorded pair differs only at that slot with equal original keys and differing repaired keys, and the Node facade adapter in a mkdtemp project pair agrees on the env detection set [env:BUILD_MODE, env:API_URL] with 23 runs and the same separation result; the file slot reads from disk under facade interposition, so file detections are not comparable across adapters and the artifact says so. (b) Planted interactions: at strength 2 the exact arm finds [env:A, env:B] on and-2way and the 2-way effect on maj-3way, while and-3way has no <=2-support effect (relevantT(2) = []) and its 3-way support [env:A, env:B, env:C] appears only at strength 3 for the exact arm; ca-ddmin attributes nothing on and-3way at strength 3 because the split-based minimizer cannot isolate the 3-subset, and that miss is recorded. (c) Minimal witnesses: 83 minimized witnesses, 81 verified 1-minimal, 2 flagged, 0 verifyRuns mismatches; the non-monotone masking task did not produce a flagged witness on this corpus, while maj-3way did. (d) Env invisible to file tracing: on undeclared-secret the single-trace read set is [env:SECRET] with no file reads (a file-only tracer sees nothing), and on combo-with-file the single-trace read set is file-only [file:cfg, file:extra] while the exact arm detects env:MODE; the artifact flags envDetectionsWithNoFileTrace = 1 and envDetectionsInvisibleToFileOnlyTracing = 2. (e) Negative controls: nondeterministic-counter refuses in all 15 cells with deterministic=false, detections=[], the miss "oracle nondeterministic at baseline", and no clock or other implicate; untrappable-ambient records trapped=false in all 15 cells with no implicates and the untrapped-read miss recorded.

• Exact arm: 72 cells, 69 equal to ground truth, 3 refusal cells (nondeterministic-counter at t = 1, 2, 3).
• Fallback honesty: attributed ca-ddmin detections are a subset of exact detections in all 69 compared cells (0 violations); the 53 exact cells where ca-ddmin is absent are classified as minimized-subset (33), over-strength witness (12), unrealized-by-array (5), and value-specific sentinel (3).
• Masking: the pinned hand array has 6 rows and 3 changed rows, zero joint-support rows for (a,b), and the exact arm finds both masked slots; both array misses are recorded.
• Minimality: 83 minimized / 81 oneMinimal / 2 flagged, verifyRuns mismatches = 0.
• Anchor: threshold-3 yields zero detections at strength 2 with the weak certificate; 55 exhaustive residual pairs, 12 Hamming-1 minimal pairs, 1 documented pair.

The headline result is that a small, deterministic, read-only probe can turn a silent cache-key collision into a printed pair. On the Metro toy the declared key is identical for both builds (39603d9ae300dbe1), the outputs differ, and the exact default arm produces a witness that differs only at env:API_URL with original keys equal and repaired keys differing (928bd61e05391f55 vs 4f82f7227ea9348b). The same audit shows why the cheap arms fail: baseline-toggle misses the slot entirely, single-trace never reads it at the baseline, and the minimizer-first fallback reduces the changing row to the key slot and drops it. Those negative arms are the falsification story; they are reported beside the exact arm, not removed.

Where the method misses, and why. First, the anchor failure: at strength 2 no <=2-support displacement of the threshold-3 baseline changes output, so the exact arm detects nothing and the 55 residual pairs (12 Hamming-1 minimal) stay equal under the repaired key; this is the documented assumption failing, and the certificate was never stronger than the weak string. Second, strength caps: and-3way's 3-way support is invisible at strength 2 in the exact arm, and the conservative fallback fails to attribute it even at strength 3, recording "detected effect requires >3 support" or the over-strength witness instead. Third, value-specific effects: binary or two-value domains miss f = 1 iff port == 8080; the port sentinel closes that cell on this corpus, and the limit remains for values the domains do not realize. Fourth, masking: the pinned array misses the (a,b) pair and the exact arm is the only arm that finds it. Fifth, non-monotone minimization: the split-based minimizer produced 2 supports that failed the exhaustive 1-minimality check, both reported. F1 is a sixth item and a different kind: that figure's bar values are not currently reconciled with the evidence script (four of twelve bars disagree under the rule its own caption states, and no gate reads it), so F1 should be read as a qualitative comparison of strategies and not as a source of exact per-family coverage percentages until the intended aggregation rule is fixed. The corpus-wide separation numbers reflect all of this: the exact default leaves 147 of 1,533 enumerated pairs colliding, and the residual is concentrated exactly where the assumption or the strength cap fails (anchor 55, planted-3way 48, negative 28, masking 12, combo-env 4).