来源: ranxianglei/billion-context#2138 (https://github.com/ranxianglei/billion-context/issues/2138) + PR #2144 分析 缓存无泄漏的代码证明 时发现 ## 背景与边界(严格限定求解器范畴) #2138 要求「接入代码证明器,主要用于证明缓存无泄漏」。已交付的两层都在本仓库内、不属于本 issue: - **断言层**(PR #2144,`tests/cache-proof.test.ts`):真实 proxy + 真实 kernel 打向理想前缀缓存计费裁判,逐对字节最长前缀断言;易变载体按声明标记结构化定位(链点标签 / retrieval note / image note / nudge),其余字节必须全等;含 RETRY/SWITCH/RESEND/HOSTRW/FOLD/DEGEN 六类路径。这是「机制面回归门禁」,不是机器可检定理。 - **运行时账本 lane**(#2139):观测证据,与证明无关。 **本 issue 只跟踪一件事**:用形式化求解器(SMT/symbolic execution)给出机器可检的定理—— > ∀ 历史 H、消息 m、(history, model) → outbound body 的管线函数 f: > f(H+[m]) 与 f(H) 在「存在量化的声明载体位置」之外逐字节前缀相等; > 且 ref 编号单调不重用(kernel id-never-reused 契约作为基础公理引入)。 ## 建模立场(owner 定调) - **不需要把 impure 点抽成纯函数**。网络调用、session store、时间戳等不纯点直接建模为自由函数(x 放在接口处,owner 原话方向),符号执行时作为未定义输入/摘要处理。抽取只是工程便利,不是方法论前提。 - 真正的工程难点(立项理由):① TS 生态没有现成的符号执行前端;② 要证的是**关系型两跑属性** f(H) vs f(H+[m]),不是单跑终止性;③ ~万行 server+kernel 重建路径的路径爆炸。 ## 候选路线(owner 指示:想办法编译到其他语言 / WASM / 底层汇编) 1. **TS→C/C++/Rust 编译后接 SMT 前端**:KLEE 系(C)、CBMC 系(C/C++)、或 Rust 符号执行工具链;管线的纯逻辑部分(消息重建、序列化、注入槽位计算)编译为目标语言,I/O 边界以自由函数建模。 2. **WASM 符号执行**:管线核心编译为 WASM,用 WASM 符号执行器(如 KLEE-WASM / wasmtime 系探索)驱动。 3. **底层汇编 harness**:核心重建函数编译为裸汇编/机器码片段,配手写 SMT 后端接口(最重,兜底路线)。 4. **模型规约替代(对照方案)**:不跑真实代码,把「序列化契约 + 注入槽位规则」写成 Z3 规约,定理证在规约上,另加 code↔spec 同步门禁(#2144 的字节断言套件充当同步证据)。成本最低但保证强度弱于 1-3。 ## 范围外(明确不做) - 运行时观测(#2139 的活) - 断言层增强(已在 #2144 交付,后续增量走 #2138/#2144 线程) - `kernel/**` 改动(human-gated,Kernel Boundary) ## 验收标准(建议) - 定理 1(增长稳定性)与定理 2(ref 单调)在求解器上 Q.E.D. - 反例驱动:故意注入一个「改写稳定字节」的 mutation,求解器必须在有限步内产出该反例(证明不是恒真空转) - 管线代码变更时求解器检查进入 CI(时长预算另行评估)
Activity
ranxianglei commentedon Oct 5, 2026
[bot] 🏷 收到。先查重,再代码勘察与工具链事实核查,最后给方案建议——拍板在你。
查重判定
按「形式化 / 求解器 / SMT / 符号执行 / cache-proof」检索全部 issue+PR(含已关闭):无重复。本 issue 与 #2138(断言层,PR #2144 已交付)、#2139(运行时账本)在 OP 中明确分层,属「机器可检定理」层,三层互补不重叠,保持打开进入正常 Triage。
代码勘察(可行性判断的事实基础)
Date.now()(response id / created 字段)、src/loop/core.ts:1070的 debug dump(仅 dump 开启时);kernel/src/rebuild.ts 对 Date/fetch/crypto/random/env/fs 的调用为零。无需抽纯函数、无需动生产代码,不纯点直接建模为自由函数即你的原话方向。assignRefsNode的 cursor =highestUsedIndex(map)+1(AGENTS.md Kernel Contract 明文),定理 2 就是对这个不变量 + id-never-reused 公理的编码,不是凭空立的规约。工具链事实核查(2026-10 逐项验证)
kani::any()符号输入,官方 GitHub Action(model-checking/kani-github-action),ASE'26 论文。CBMC v6 官网原文「For Rust, get Kani」——CPROVER 系官方把 Rust 统一指向 Kani方法要点(消解难点②):关系型两跑属性不需要真双跑——一个 harness 同时算出 f(H) 与 f(H+[m]) 两个 body(共享同一 x 向量:同一时间戳 x、同一组自由函数取值),在二元对上断言前缀关系。关系属性归约为单跑 BMC 义务,标准 Kani/CBMC 地盘。
方案建议(明确推荐,拍板在你)
阶段 1 —— 立即可交付,三条验收标准在规约层面全满足:
seq<Byte>理论天然表达字节最长公共前缀;cvc5 备选)写定理 1+2:规约 = 四线序列化契约 + 注入槽位规则(声明载体存在量化:chain checkpoint tag / nudge / imgNote / retrieval note,内容=任意字节放行)+ ref 分配不变量;src/loop/**、kernel/src/{rebuild,render-refs,refs,segment,block-map}、serializer 族文件变更触发),时长预算在 PR 里实测给出;成本:天级;零生产代码改动、零新 npm 依赖、零配置面新增(z3 二进制是 CI 构建侧工具,ubuntu runner 预装)。
阶段 2 —— 「编译到其他语言」的实质落地,建议阶段 1 落地后拆独立 issue 跟踪:
proof/,不改 kernel/**,不触 human-gate);成本:周级;CI 新增 rustup + kani-verifier(开发/CI 工具,非 npm 依赖)。
明确不建议:WASM 路线(无生产级执行器)、汇编路线(被 Rust 路线严格支配)、JS 符号前端直跑(纯学术品)。
我的明确建议:批准即从阶段 1 动工;阶段 2 拆独立 issue(理由:两阶段验收标准各自独立,拆分避免长命分支,且阶段 1 本身已满足本 issue 全部三条验收标准)。你若要求两阶段在本 issue 一处跟踪,说一声即可。
ranxianglei commentedon Oct 5, 2026
同意 继续
ranxianglei commentedon Oct 5, 2026
[bot] 🏷 Phase 1 开工进度播报(你已拍板「同意 继续」,按批准的路线执行中):
2026-10-05_solver-theorems-phase1已从 master 拉出(test: code prover proving cache-byte stability across failure paths (#2138) #2144 已合入 master,同步门禁依赖解除,字节断言套件现在就是 standing gate)。kernel/src/refs.ts的assignRefs/allocateFreeRef(cursor = max(nextIndex,1)、existing untouched、BLOCKED 不耗号、smallestFree 只扫 live map)+ fix: archive blocks across omp native compaction instead of silently deactivating them (#395) #421 archive 的 cursor 重置残余窗口;T1(增长稳定性)载体族 = merge-last-user(wire-body.ts nudge/hint)+ tail-append(imgNote 条件性 / chain-checkpoint stamp,stampOutbound(nowMs)即 x-at-interface 的钟);impure 点全部按你的定调在接口处建模为自由函数,零生产代码改动。z3-solver==4.9.1.0(wheel),下载速率受限,预计还需一段时间。CI lane 用同 pin,保证本地/CI 判定一致。proof/spec/*.smt2+tests/cache-theorem.test.ts(无求解器时 solver 子项 skip、grounding 恒跑,主npm test不受影响)+ 独立 CI workflow(paths 过滤),迭代到 9/9 绿后提 PR。有结果我会回来报七问结论。
ranxianglei commentedon Oct 5, 2026
[bot] 🏷 Phase 1(路线 4:模型规约 + Z3)已交付 → PR #2159(Closes #2149,等人工合并 + CI)。
按批准的方案执行:两条定理在 Z3 上 Q.E.D.,反例驱动门禁成立,求解器检查已进 CI。路线 1–3(真实管线编译到 symex 前端)作为后续增强项保留,owner 若要继续可在此线程拍板再立项。
七问结论:
kernel/src/rebuild.ts内部零不纯调用,此立场工程成本≈0。hui=3 creset=4 n3=4 n4=5——死高位号 5 被重发,即文档化的 fix: archive blocks across omp native compaction instead of silently deactivating them (#395) #421 残余窗口的机器刻画(窗口开当且仅当游标跌破某个已死且曾发出的编号)。定理用显式共享前缀项 P(blen(P)=D)编码,这是 ∃p≥D 量化形式的可判定强化(量化形式 Z3 返回 unknown,已在 spec 头注释记录)。代码↔规约同步靠两层:grounding 测试把每条公理钉到真实代码(esc 代数→JSON 字符串编码器 200 随机对、mktag→indexToRef 20 万往返、分配规则→assignRefs/allocateFreeRef),test: code prover proving cache-byte stability across failure paths (#2138) #2144 套件提供整包粒度同步证据。信任边界在 proof/README.md 开头写死:定理说的是「满足公理的任一组装函数」,不是「代码满足公理」——后者由两层机制补全,这是路线 4 的诚实强度。proof/目录 + 独立 CI lane(ci-theorem.yml,ubuntu-only、paths 过滤到组装面、钉 z3-solver==4.9.1.0),不动现有架构与 ci.yml;npm test在无 z3 的机器(含 windows leg)上 solver 子测试按设计 skip、grounding 照跑,主套件保持绿。验收标准对照:① 定理 1+2 在求解器上 Q.E.D. ✓(UNSAT×3,含 T1 双场景);② 反例驱动 ✓(三个 mutation 孪生全部被有限步内抓到,T2 模型精确复现 #421 残余);③ CI 门禁 ✓(时长实测 <1s,远低于任何预算)。验证覆盖两个求解器版本:Z3 4.9.1.0(CI 钉版,native)与 4.16.0.0(WASM 本地迭代)verdicts 与模型完全一致。
诚实局限(README 有完整版):有界实例化(固定角色形状 S1/S2、T2 四步会话;推广到任意 N 是机械的但未参数化);帧/封套函数保持未解释(承载性的是槽位放置,已被断言;精确字节交给 #2144);esc 长度界用最坏 ×6。
收工判定:Phase 1 完成,PR #2159 待合并;合并后本 issue 关闭,路线 1–3 如需推进请在此线程指示。
Merge pull request #2159 from ranxianglei/2026-10-05_solver-theorems-…
feat: machine-checked cache-stability theorems via Z3 (route 4, ranxi…