ADCakeyuan's blog

看不见的栈泄漏:给自研 Hack 软件栈做两轮审计

Published on
//
19 分钟读完
/
TL;DR

VM 的 return 无论函数返不返回值,都会在 ARG 指向的位置留一个返回槽;编译器对 void 的 do 调用跳过 pop,于是每次调用漏 1 字,Tetris 玩久了栈顶会顶穿堆区。修完后 ROM 溢出,又靠官方三字 pop 惯用法省回 674 字。最终 7 个检查点屏幕哈希全不变、门级 7/7 零分歧、demo 重发布。

这个 bug 最难受的地方,是它一直看起来不像 bug。

Tetris 跑完一亿七千多万个周期,7 个检查点的屏幕哈希全对,门级模拟器和行为级解释器逐周期一致,测试全绿。然后我翻开编译器生成的 VM 代码,发现每一个 do 调用后面,都少了一条 pop。

也就是说:这个程序一直在漏栈。只是它漏得很安静。

先交代一下战场

这是 Nand2Tetris 的 Hack 计算机,16 位、32768 字的 ROM、512×256 的屏幕。我没有用官方工具,而是把软件栈整个重写了一遍:

  • 汇编器:两遍扫描、符号表、全错误报告;
  • hackrun:行为级 ISA 解释器,1 指令 = 1 周期,作为整条工具链的 oracle;
  • VM 翻译器:全部段、算逻、流控、调用帧;
  • Jack 编译器:词法、递归下降语法分析、AST 到 VM 的代码生成;
  • Jack OS 子集:Memory 分配器、Array、Math、String、Output、Screen、Keyboard、Sys;
  • Tetris:用自己写的语言、自己的编译器、自己的 OS 跑起来。

为了证明“我写的编译器没有把 ROM 编错”,我准备了两把尺子:一把是行为级解释器,一把是硬件轨的门级模拟器。同一份 ROM 喂给两边,逐周期比对 pc、a、d、addressM、writeM、outM,再在 7 个检查点分别对屏幕取 SHA-256。两边一致,才算过关。

这套东西看起来已经挺像回事了。所以第一轮审计修完 10 项之后,我以为剩下的只是收尾。

调用约定里的那一个字

Jack 里的 do 语句用来调用一个函数并丢弃返回值:

do Screen.drawRectangle(0, y1, 511, y2);
do Output.printInt(score);

编译器要为它生成 VM 代码。VM 的调用约定是这样的:

call f n:
  依次压入 返回地址、LCL、ARG、THIS、THAT
  ARG = SP - (n + 5)
  LCL = SP
  goto f
 
return:
  *ARG = pop()
  SP = ARG + 1

注意最后两行。return 根本不看函数签名,它只认栈:从栈顶弹出一个字,写回 *ARG,然后把 SP 设成 ARG + 1。

假设参数已经压好、call 即将执行时 SP = S,n 个参数占着 S-n 到 S-1。call 压入 5 个字后 SP = S+5,ARG = S-n。函数返回时 SP = ARG+1 = S-n+1。参数被消费掉了,调用方本该回到参数入栈前的 S-n;但 return 留下了一个返回槽,SP 停在 S-n+1。想让栈恢复调用前的形状,就必须再弹一次。

对非 void 函数,这个字是返回值。对 void 函数,它弹出来的可能是局部变量、临时值,甚至是被保存的寄存器之一——反正调用方不会读它。但垃圾也要弹。 这是 ABI 的一部分,不是语言层面的“有没有值”。

我之前的编译器不是这么想的:

case "do": {
  compileExpr(st.call, ctx);
  // 旧注释:void callees leave no value on the stack
  if (ctx.subroutineRets.get(calleeFullName(ctx, st.call)) !== "void") {
    out.push("pop temp 0");
  }
  return;
}

注释写得很自信:void 函数不在栈上留值,所以不用弹。可 VM 的 return 不认这句话。它每次都会留下返回槽,不管你是不是 void。

于是每次 do SomeVoid(),SP 净增 1。修复只需要删掉那个条件:

case "do": {
  compileExpr(st.call, ctx);
  // VM return 恒留一个返回槽,void 也一样
  out.push("pop temp 0");
  return;
}

生成的 VM 代码只多了一行,但这一行决定了栈会不会慢慢爬进堆里。

它到底能漏多大

单个字听起来没什么。问题是调用次数。

审计脚本里在一个循环里用 do Memory.dealloc 释放 3222 个块,SP 从约 270 涨到约 3490——每释放一个块,就多留一个字。Hack 的栈区是 256 到 2047,堆从 2048 开始。SP 一旦越过 2048,函数调用的帧和分配器的空闲链表就会重叠,接下来发生的事取决于谁先写谁:可能是 String.new 返回一个指向栈帧的指针,可能是屏幕重绘把堆里的元数据覆盖掉,也可能只是画面某个角落花掉。

Tetris 里每次逻辑帧会触发 1 到 3 次这样的 void 调用。短时间玩没事,玩久了就不是“性能差一点”,而是内存分配器被踩烂。一个看起来正常的游戏,正在以每帧一到三个字的速率走向崩溃。

更值得说的是:为什么这么多测试都没抓到?

  • 编译器测试断言的是最终输出:屏幕内容、RAM 里的值、函数返回值。没有一条断言 SP。
  • VM 那 400 例差分测试很棒,但它喂给翻译器的是程序生成的 VM 表达式,不是编译器生成的 VM 程序。编译器根本不在这条测试链路上。
  • 门级 vs 行为级的对拍更强,但两边跑的是同一份 ROM。编译器的错误已经烤进 ROM 了,门级模拟器和行为级解释器当然会一起错。它们能证明“我的 CPU 和我的解释器一致”,不能证明“我的编译器生成的代码符合调用约定”。
  • 黄金脚本只跑到第 5 个方块。在泄漏把栈顶推到堆区之前,7 个检查点的屏幕哈希可以完美通过。

这是一个很典型的测试盲区:每个层都在假设下面那层是对的。汇编器相信 VM 翻译器的输出,VM 翻译器相信编译器生成的东西,集成测试相信 ROM 里的代码。只要错误在进入 ROM 之前就已经发生,后面的所有对拍都会忠实地复现它。

我补的回归测试很朴素:连续做 100 次 do Main.v()、100 次 do Main.f(),然后停在死循环里读 SP。修复后是 268;泄漏版会是 468——200 次调用,正好多 200 个字。

想省两个字,被语义教育

修复加上去,ROM 从 32540 字涨到 32706。再加上 Screen、String、Tetris 的三处修复,变成了 32958 字。

上限是 32768。

汇编器直接把构建拦了下来。这一点值得单独夸一句:ROM 溢出报错本身也是第一轮审计修出来的。在那之前,超过 32768 字的程序不会报错,你会拿到一份看起来正常、实际上 CPU 根本寻址不到的 ROM。

回到溢出。第一反应是做窥孔优化:call f n; pop temp 0 能不能合成一条特殊调用,调用完直接把 SP 减一,不真的写 temp 0?这样每个 do 调用能省两个字。

想法很合理,测试不同意。

已有的 VM 测试里有这么一段:

call Test.f 0
pop temp 0

然后它去读 RAM[5],期望值是 11。pop temp 0 的语义就是“把栈顶写进 RAM[5]”,这是一个可观察的副作用。编译器当然知道这个值马上会被丢弃,但 VM 翻译器不能知道,也不该知道——它面对的是任意合法 VM 代码,不是只面对自家编译器。

优化必须在语义边界内做。既然不能省掉写入,那就把 pop 本身写短一点。旧写法是四字:

@SP
M=M-1
A=M
D=M

换成官方 VM 翻译器的三字惯用法:

@SP
AM=M-1
D=M

关键在 Hack 的 old-A 语义:M= 的写入地址是这条指令开始前的 A,而 A= 同时把 A 改成新值。AM=M-1 一条指令做了两件事:把 SP-1 写回 RAM[0],并把 A 指向新的栈顶。第三字 D=M 把栈顶读进 D。

这个惯用法被铺到了所有 pop 位置:通用 pop、二元运算、比较、if-goto、return、数组写入。每处省一个字,累计把 32958 字压回了 32094 字,还多出 674 字的余量。

有意思的是,修完 bug 的 ROM 比修之前更小:审计前 32540 字,审计后 32094 字。正确性和紧凑性这次没有打架,前提是你愿意去读官方翻译器怎么写。

另外三颗地雷

栈泄漏是第二轮审计里最严重的一个,但不是唯一一个。另外三处都符合“平时没事,特定输入才炸”的特征。

Screen.drawRectangle 忘了裁剪 y

drawRectangle 会先处理坐标交换,再算屏幕基址:

let base = 16384 + (y1 * 32);

x 方向有裁剪,y 方向没有。如果调用者传进来负数 y,base 就会落到 16384 以下——那是堆区。画一个矩形,等于往堆里写数据。

修复是在交换之后把 y 夹到屏幕范围:

if (y1 < 0) {
    let y1 = 0;
}
if (y2 > 255) {
    let y2 = 255;
}

回归测试直接画 y = -5、y = -200、y = 250..300,然后断言 ram[16384 - 160] 和 ram[16384 - 32] 仍然是 0,同时第 250、255 行确实被点亮。既证明没有越界写,也证明可见部分没被裁没。

String.setInt 不尊重 maxLength

String.new(maxLength) 按容量分配,setInt 却默认“符号位加数字一定放得下”。对一个容量只有 2 的字符串调用 setInt(-32768),它会写 6 个字符,把相邻的堆块踩坏。

修复是在每次写符号和数字之前检查 len < maxLength。测试用 String.new(2) 存 -32768,期望得到 "-3"(长度 2,字符 45 和 51);再用 String.new(0),期望长度保持 0。不是“尽量写”,而是“容量不够就截断”。

Tetris 的长按只动三次

按住方向键时,Tetris 用一个 repeatCnt 做自动重复:计数没超过 3 就继续处理方向。但计数只增不减,超过 3 之后就再也不会回到可触发区间——按住右键,方块横移三次,然后永远停住。

修复是让计数回绕:

// wrap the counter so a held key keeps auto-repeating
if (repeatCnt > 3) {
    let repeatCnt = 0;
}

测试从第一个检查点开始按住右键 4000 万周期,每 10 万周期采样一次方块横坐标,直到方块落地;断言移动次数大于 3。修复前这个数字会卡在 3。

第一轮的十项,大多是“错误不够响”

第一轮审计集中在工具链外围,修的东西没有栈泄漏这么戏剧性,但共同点是:它们让错误变得可见。

位置问题
VM 翻译器label/goto/if-goto 用模块作用域,同名 label 跨函数串地址;改为函数作用域
VM 翻译器数组读窥孔覆盖了 THAT 的副作用,let a[i] = a[j] 可能写错地址
hackrun检查点 dump 共享同一块 RAM,所有检查点看到的都是最终状态;改为逐检查点快照
hackrunrun() 的 maxCycles 差一
汇编器用原型链判断预定义符号,@toString 被误判;改用 Object.hasOwn
汇编器ROM 超过 32768 字不报错;改为显式失败
VM 解析器无参指令带了参数也不报错
disasm标签类型判断错误
CLI不剥 UTF-8 BOM
jackc多类共享静态区没有警告

这些 bug 单独看都不致命,但它们的共同效果是“让错误安静地通过”。审计的价值有时候不是修一个惊天大 bug,而是把系统里所有“静默”改成“吵闹”。

改完怎么证明没改坏

这是我最喜欢的部分:修了编译器、VM 翻译器、OS 和游戏逻辑,怎么证明 Tetris 的行为没变?

答案是黄金检查点。重录之后:

  • 7 个检查点的屏幕 SHA-256 全部不变,从开局 376f24bd… 到终局 eb9348b8…;
  • 最终局面不变:LINES 1 · SCORE 100;
  • ROM 从 32540 字变成 32094 字,romSha256=aaa3b68c…40de;
  • 总周期从 175,296,393 变成 166,446,228。

最后一条一开始让我愣了一下:哈希全一样,周期怎么少了 885 万?

因为指令变少了。三字 pop 让每个 pop 位置少一条指令,整份 ROM 小了一截;do 修复虽然增加了 pop,但总体上还是净减少。屏幕哈希不变、周期数下降,这正好是“语义没变、执行路径变短”的签名。如果哈希变了,才说明我们把行为改坏了;如果周期没变,才说明优化没生效。

接着是更重的一关:门级模拟器。把同一份 ROM 和 25 条输入事件交给硬件轨的门级计算机,跑满 166,446,228 个周期:

  • oracleDiff.ok = true,firstDivergence = null;
  • 7/7 检查点的门级屏幕哈希 = 行为级 oracle = 黄金记录;
  • 全程十几分钟,门级模拟大约 20 万周期/秒。

以及浏览器里的行为级 demo:重新部署到 Cloudflare Pages,线上 tetris.hack、input.txt、meta.json、engine.js、ui.js、index.html 的哈希全部与本地构建一致;Chromium 里开机渲染、方向键移动、黄金脚本回放到 LINES 1 · SCORE 100,画布哈希 1723327576,控制台零错误。

测试数从审计前的 58 条变成 71 条。新增的不是“多跑几个用例”,而是四类以前没有的断言:栈平衡、屏幕边界、字符串容量、长按重复。

审计之后留下的

这次两轮审计一共 16 项发现,修了 14 项。剩下两项我没有硬修,而是明确写进了文档:

  • VM 的 gt/lt 采用 nand2tetris 参考翻译器的 16 位环绕差值判定,异号且差值绝对值大于等于 32768 时和数学比较不一致。防溢出的内联展开每处约多 14 字,Tetris 有 76 处比较,ROM 余量不够,所以保留紧凑实现并加固定用例。
  • 未定义标签的链接检查还没实现:@Missing 会被当成新变量分配,而不是报错。这是 Hack 汇编器的传统行为,但对一个自称全错误报告的工具链来说,是个缺口。

我不觉得这是什么光彩的收尾,但审计报告如果只写修好的部分,那它就是公关稿,不是报告。

如果让我只留一条结论,大概是这个:差分测试证明的是一致性,不是正确性。 当两个实现共享同一个错误时,它们会相处得非常融洽。真正能抓住这类 bug 的,是断言不变量——SP 应该回到哪里、堆边界有没有被越过、ROM 有没有超限——以及偶尔真的去读一眼生成的代码。

现在再跑一次 Tetris,最后一行还是 LINES 1 · SCORE 100。画面和修复前一模一样,但栈底那些多出来的字终于不再往上爬了。

Demo 还在这里:nand-computer-demo.pages.dev