Skip to content

形式化求解器证明缓存字节稳定性:x-at-interface 建模,TS→C/C++/Rust 编译 / WASM / 汇编路线 #2149

Closed

Description

@ranxianglei

来源: #2138 (#2138) + PR #2144 分析 缓存无泄漏的代码证明 时发现

背景与边界(严格限定求解器范畴)

#2138 要求「接入代码证明器,主要用于证明缓存无泄漏」。已交付的两层都在本仓库内、不属于本 issue:

本 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 同步门禁(test: code prover proving cache-byte stability across failure paths (#2138) #2144 的字节断言套件充当同步证据)。成本最低但保证强度弱于 1-3。

范围外(明确不做)

验收标准(建议)

  • 定理 1(增长稳定性)与定理 2(ref 单调)在求解器上 Q.E.D.
  • 反例驱动:故意注入一个「改写稳定字节」的 mutation,求解器必须在有限步内产出该反例(证明不是恒真空转)
  • 管线代码变更时求解器检查进入 CI(时长预算另行评估)

Activity

  1. ranxianglei commented on Oct 5, 2026

    @ranxianglei
    OwnerAuthor

    🤖 Powered by ework · qwen3.8-27b

    [bot] 🏷 收到。先查重,再代码勘察与工具链事实核查,最后给方案建议——拍板在你。

    查重判定

    按「形式化 / 求解器 / SMT / 符号执行 / cache-proof」检索全部 issue+PR(含已关闭):无重复。本 issue 与 #2138(断言层,PR #2144 已交付)、#2139(运行时账本)在 OP 中明确分层,属「机器可检定理」层,三层互补不重叠,保持打开进入正常 Triage。

    代码勘察(可行性判断的事实基础)

    • f 的真实面比「上万行」小得多:定理对象是 (history, model)→outbound body 的重建+序列化函数,实际面 = kernel/src/rebuild.ts(79) / render-refs.ts(165) / refs.ts(123) / segment.ts / block-map.ts + src/loop/adapter-{anthropic,openai,responses,google}.ts(~2645)+ wire-body / system-anchor / chain-checkpoint / image-note(~995)≈ 4.1k 行。server.ts 的 7.7k 行主要是编排/IO,按定理定义天然在界外。难点③(路径爆炸)从「万行」降为「4k 行 + 有界输入」。
    • 「接口处设 x」在这套代码上成本≈零:该路径上的不纯点极少且全部接口可定位——adapter 组 Date.now()(response id / created 字段)、src/loop/core.ts:1070 的 debug dump(仅 dump 开启时);kernel/src/rebuild.ts 对 Date/fetch/crypto/random/env/fs 的调用为零。无需抽纯函数、无需动生产代码,不纯点直接建模为自由函数即你的原话方向。
    • ref 不变量有代码锚点:refs.ts assignRefsNode 的 cursor = highestUsedIndex(map)+1(AGENTS.md Kernel Contract 明文),定理 2 就是对这个不变量 + id-never-reused 公理的编码,不是凭空立的规约。

    工具链事实核查(2026-10 逐项验证)

    路线 核查结果
    Kani(AWS,Rust SMT 模型检查) 生产级,首选。bit-precise BMC,z3/cvc5 后端,kani::any() 符号输入,官方 GitHub Action(model-checking/kani-github-action),ASE'26 论文。CBMC v6 官网原文「For Rust, get Kani」——CPROVER 系官方把 Rust 统一指向 Kani
    TS→C/C++ 编译(路线 1 字面义) 不存在这种工具链(也没有语义经核验的翻译器)。路线 1 唯一可行形态 = 对 ~4k 行纯核做 clean-room Rust 移植 + Kani 证明。本质约束:「TS 没有求解器」的问题不会因编译消失,而是转化为翻译信任边界——移植体↔真实 TS 代码之间必须靠差分测试(随机历史 → 两侧输出逐字节相等)+ #2144 门禁桥接;这是目前能拿到的最强桥
    WASM 符号执行(路线 2) 只有学术原型:SeeWasm / WASEM(PKU-ASAL,18–48 stars,2024 后停滞或低频)、wasm-sym(2018 归档)。核心就算编成 WASM,也没有生产级执行器驱动。不作主路线,生态成熟再重估
    汇编 harness(路线 3) 严格劣于 Rust 路线:手写 SMT 后端工作量更大、工具面更小(裸汇编无现成 Kani/CBMC)、证明强度无增益。仅作书面兜底保留
    JS/TS 符号执行前端直挂 只有学术引擎:ExpoSE(229★,末次提交 2025-01)、JaVerT2.0(2020 后停摆)。无一 CI 可用,适配是月级研究工作量

    方法要点(消解难点②):关系型两跑属性不需要真双跑——一个 harness 同时算出 f(H) 与 f(H+[m]) 两个 body(共享同一 x 向量:同一时间戳 x、同一组自由函数取值),在二元对上断言前缀关系。关系属性归约为单跑 BMC 义务,标准 Kani/CBMC 地盘。

    方案建议(明确推荐,拍板在你)

    阶段 1 —— 立即可交付,三条验收标准在规约层面全满足:

    1. Z3(seq<Byte> 理论天然表达字节最长公共前缀;cvc5 备选)写定理 1+2:规约 = 四线序列化契约 + 注入槽位规则(声明载体存在量化:chain checkpoint tag / nudge / imgNote / retrieval note,内容=任意字节放行)+ ref 分配不变量;
    2. 反例驱动:向规约注入一个「改写稳定字节」的 mutation,求解器必须在有限步产出反例(证明不是恒真空转);
    3. CI 路径过滤接入(仅 src/loop/**、kernel/src/{rebuild,render-refs,refs,segment,block-map}、serializer 族文件变更触发),时长预算在 PR 里实测给出;
    4. code↔spec 同步门禁 = test: code prover proving cache-byte stability across failure paths (#2138) #2144 字节断言套件(当前 open,合并后即常设门禁)——正是 issue 预定它扮演的角色。

    成本:天级;零生产代码改动、零新 npm 依赖、零配置面新增(z3 二进制是 CI 构建侧工具,ubuntu runner 预装)。

    阶段 2 —— 「编译到其他语言」的实质落地,建议阶段 1 落地后拆独立 issue 跟踪:

    1. ~4k 行纯核 clean-room Rust 移植(不纯点为接口函数,x-at-interface;移植体放新顶层目录如 proof/,不改 kernel/**,不触 human-gate);
    2. Kani 证定理 1+2(最坏分解上限:4 线 × 2 定理 = 8 个义务);
    3. 差分模糊 lane(TS ≡ Rust 逐字节)+ test: code prover proving cache-byte stability across failure paths (#2138) #2144 门禁双兜底。

    成本:周级;CI 新增 rustup + kani-verifier(开发/CI 工具,非 npm 依赖)。

    明确不建议:WASM 路线(无生产级执行器)、汇编路线(被 Rust 路线严格支配)、JS 符号前端直跑(纯学术品)。

    我的明确建议:批准即从阶段 1 动工;阶段 2 拆独立 issue(理由:两阶段验收标准各自独立,拆分避免长命分支,且阶段 1 本身已满足本 issue 全部三条验收标准)。你若要求两阶段在本 issue 一处跟踪,说一声即可。

  2. ranxianglei commented on Oct 5, 2026

    @ranxianglei
    OwnerAuthor

    同意 继续

  3. ranxianglei commented on Oct 5, 2026

    @ranxianglei
    OwnerAuthor

    🤖 Powered by ework · qwen3.8-27b

    [bot] 🏷 Phase 1 开工进度播报(你已拍板「同意 继续」,按批准的路线执行中):

    1. 分支 2026-10-05_solver-theorems-phase1 已从 master 拉出(test: code prover proving cache-byte stability across failure paths (#2138) #2144 已合入 master,同步门禁依赖解除,字节断言套件现在就是 standing gate)。
    2. 代码勘察完成,定理落点确认:T2(ref 单调)锚定 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 点全部按你的定调在接口处建模为自由函数,零生产代码改动。
    3. 求解器环境:沙箱内无 z3,正在后台获取 pin 死的 z3-solver==4.9.1.0(wheel),下载速率受限,预计还需一段时间。CI lane 用同 pin,保证本地/CI 判定一致。
    4. 规格设计已完成(SMT2,保守核心理论:UF + 序列 + 数组 + 线性整数,兼容 Z3 4.8+):9 个求解义务——T1×2 场景(锚点翻转 / 锚点不动)各含「上下文一致性 SAT + 定理 UNSAT + 稳定字节 mutation SAT」、T2×3(单调 cursor ⇒ 不重用 UNSAT;archive 后 cursor 重算 ⇒ 反例 SAT,机器化复现 fix: archive blocks across omp native compaction instead of silently deactivating them (#395) #421 残余窗口;上下文一致性)。每个公理都有 grounding 测试钉回真实代码(esc 同质性钉 JSON 序列化器、mktag 钉 indexToRef、cursor 方程钉 refs.ts),另加 test: code prover proving cache-byte stability across failure paths (#2138) #2144 套件作 code↔spec 同步证据。
    5. 待下载完成:写 proof/spec/*.smt2 + tests/cache-theorem.test.ts(无求解器时 solver 子项 skip、grounding 恒跑,主 npm test 不受影响)+ 独立 CI workflow(paths 过滤),迭代到 9/9 绿后提 PR。

    有结果我会回来报七问结论。

  4. ranxianglei commented on Oct 5, 2026

    @ranxianglei
    OwnerAuthor

    🤖 Powered by ework · qwen3.8-27b

    [bot] 🏷 Phase 1(路线 4:模型规约 + Z3)已交付 → PR #2159(Closes #2149,等人工合并 + CI)。

    按批准的方案执行:两条定理在 Z3 上 Q.E.D.,反例驱动门禁成立,求解器检查已进 CI。路线 1–3(真实管线编译到 symex 前端)作为后续增强项保留,owner 若要继续可在此线程拍板再立项。

    七问结论:

    1. 是什么问题:需要一个机器可检的定理——f(H+[m]) 与 f(H) 在存在量化的声明载体位置之外逐字节前缀相等,且 ref 编号单调不重用——而不是只有机制面回归断言(test: code prover proving cache-byte stability across failure paths (#2138) #2144)和运行时观测(feat: per-call outbound body-stability proof in the cache ledger (#2131) #2139)。
    2. 什么原因导致的(立项理由回顾):TS 生态无现成符号执行前端;要证的是关系型两跑属性而非单跑终止性;万行重建路径路径爆炸。故按 owner 定调走 x-at-interface 建模:不纯点(网络/session store/时钟)直接建模为接口处自由函数/自由输入,不抽纯函数——实际勘察证实 kernel/src/rebuild.ts 内部零不纯调用,此立场工程成本≈0。
    3. 怎么修复的(实现策略):字节级契约规约(SMT-LIB String 理论建模字节串)+ 九个义务:T1 增长稳定性两个场景(merge 锚点翻转 S1 / 驻留 S2,载体族 = MERGE nudge/hint + TAIL imgNote/checkpoint-stamp/fresh-turn,checkpoint 携带时钟即 x-at-interface 实例),反证式 UNSAT;T2 ref 不复用在持久化单调游标下 UNSAT,其 mutation 孪生 SAT 且模型精确给出 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 的诚实强度。
    4. 是否有回归问题:无生产代码改动(纯 proof/tests/workflow 表面),kernel/** 只读未动,零行为变更,无回归面。
    5. 是否破坏缓存:不涉及——不改任何运行时路径、重试、游标或去重键。
    6. 是否改了设计方向:新增顶层 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 照跑,主套件保持绿。
    7. 是否引入了新的配置:无新 env/config/CLI flag/默认值。

    验收标准对照:① 定理 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 如需推进请在此线程指示。

  5. added a commit that references this issue on Oct 5, 2026
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

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions