Go 汇编变异测试

在维护和开发 Go 加密标准库时，我们花在测试上的时间通常远超实现时间。这是好事，也是我们取得优秀安全记录的重要部分。

理想情况下，库中最不安全的部分尤其应该如此。然而，由于汇编核心的恒时性特性，测试它们面临着独特挑战。这一直是一个长期存在的问题。

对于 Go 1.26，我正在为汇编引入一个变异测试框架，它将有效地充当增强的代码覆盖率。这本身不会改进测试，但能让我们看到哪些汇编代码和数据路径未被测试套件覆盖，从而改进测试。

#20040，我的白鲸

加密汇编可以说是我作为 Go 维护者的"起源故事"。早在 2017 年，Cloudflare 的一位同事发现一个证书无法通过 Go 的 crypto/x509 验证。该错误是 P-256 模减法 amd64 汇编实现中进位处理不当导致的。由于在随机输入操作时，该进位标志有 1/2³²的概率被设置，它逃过了所有测试。

Adam Langley 评论说利用它不太可能，而且"会是一篇很酷的论文"。然后 Sean Devlin 和我在巴黎的一家星巴克躲了一整天，而黄背心在外面焚烧警车，我们想出了如何将其变成好莱坞式的密钥恢复攻击。那很有趣，但这是另一个故事了。

快进一年，现在我的工作是防止这种情况再次发生。寻找针对此类错误的稳健对策从此成了我的白鲸。

"Filippo，正常、理智的人不会有白鲸。""好吧，我们什么新东西都没学到，是吧？"

汇编策略（希望）有助于减少引入新的手动编写汇编错误的风险，如果有什么作用的话，那就是因为它使引入新的手动编写汇编变得更加困难。但一个根本问题是我们不知道汇编的测试情况如何，因为代码覆盖率对加密汇编不起作用。

大多数加密代码必须在恒时条件下运行，这意味着无论输入如何，它都执行相同的指令，以避免通过时序侧信道泄露秘密。为了实现这一点，我们通常计算操作的两个"分支"（例如，对于 a - b mod p，同时计算 a - b 和 a - b + p），然后通过恒时选择指令丢弃其中一个结果。问题是，如果运行代码覆盖率，你会看到所有"分支"都被点亮，即使所有测试实际上都丢弃了其中一个的结果。我们可能还有其他未测试的路径，如 #20040，却不知道。

在 2019 年的某个时候，我尝试使用 DynamoRIO 在运行时检测二进制文件，以捕获每个消耗标志的指令之前的标志，以提供更全面的覆盖率报告。它几乎奏效了。"几乎"是决定性的。

变异测试

进入变异测试。变异测试修改程序，例如将!=变为==，并检查每个"变异"的测试是否失败。如果不失败，则该行实际上未被测试。

这实际上比常规测试覆盖率更准确，因为它不仅检查代码是否被执行，还检查结果是否影响测试的成功，以至于产生不同的结果会导致测试失败。

它也非常适合恒时汇编！

例如，如果我们将带进位加法变为常规加法，而测试仍然通过，那么我们实际上没有测试进位被设置的情况。

变异汇编

下一个问题是如何以编程方式变异汇编。我原本打算在源代码级别进行，但 Russ Cox 建议修改汇编器，以避免处理宏和解析。

cmd/asm在解析后、编码前为指令分配虚拟程序计数器。CL 6653751 添加了一个-mutlist标志，用于在此时将列表打印到标准错误，以及一个-mut标志，允许用一个或多个其他指令替换任何具有其程序计数器的指令。实现它相当容易，重用了解析器并修补了指令链表。

$ GOARCH=amd64 go test crypto/ed25519 -asmflags=crypto/internal/fips140/edwards25519/field=-mutlist -c# crypto/internal/fips140/edwards25519/fieldasm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:8: 00001 TEXT   crypto/internal/fips140/edwards25519/field.feMul(SB), NOSPLIT, $0-24[...]asm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:23: 00012 ADDQ  AX, DIasm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:24: 00013 ADCQ  DX, SIasm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:27: 00014 MOVQ  16(CX), DX[...]
$ GOARCH=amd64 go test crypto/ed25519 -asmflags=crypto/internal/fips140/edwards25519/field='"-mut=$GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:13=STC;ADCQ DX, SI"'--- FAIL: TestGenerateKey (0.00s)panic: runtime error: invalid memory address or nil pointer dereference [recovered, repanicked][signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x5a900de]

这些汇编器标志可以在go test期间使用-asmflags=PACKAGE="-mut=..."为特定包启用。幸运的是，cmd/go已经知道将-asmflags参数折叠到汇编器工件的缓存键中，它甚至缓存 stderr 输出，因此即使使用缓存结果，-mutlist输出也可用。

测试框架

驱动这些测试相对简单。

首先，我们运行go test -c -asmflags=PACKAGE=-mutlist以获取潜在目标的列表。

然后，对于每个目标指令的每个变异，我们运行go test -failfast -asmflags=PACKAGE="-mut=file.s:123=MUTATION"，并确保它失败。为了加速，我们首先使用-short运行，然后仅在短测试通过时运行不带它的测试。此外，我们首先运行-c以确保我们的变异能够编译。

变异

最后，我们需要决定变异哪些目标指令以及如何变异。变异将行为因标志而异的指令转变为等效的、行为如同标志始终设置或从未设置的指令。它们不能改变任何其他东西，以避免意外破坏测试运行并导致变异测试假阴性。特别是，我们不能使用任何寄存器，并且需要保持最终标志不变。

让我们看几个 arm64 示例。

ADCS 和 SBCS

ADCS 将两个寄存器和进位相加，并设置输出标志。

// Xd = Xn + Xm + CADCS Xn, Xm, Xd

将其变异为忽略进位标志的指令很容易，我们只需将其变为 ADDS。

// Xd = Xn + XmADDS Xn, Xm, Xd

为了向另一个方向变异，我们在前面添加一条设置 C 标志的指令。我们不关心破坏其他标志，因为 ADCS 无论如何都会重置它们。

// C = 1 (即无借位，有进位)SUBS ZR, ZR, ZR// Xd = Xn + Xm + CADCS Xn, Xm, Xd

SBCS 是等效的减法指令，我们以相同的方式变异它，只是 SUBS 的行为如同进位（即"无借位"）标志始终设置，因此我们需要在镜像变异中取消设置它。

// ## 原始// Xd = Xm - Xn - (C - 1)SBCS Xn, Xm, Xd
// ## 变异1// Xd = Xm - XnSUBS Xn, Xm, Xd
// ## 变异2// C = 0 (即有借位，无进位)ADDS ZR, ZR, ZR// Xd = Xm - Xn - (C - 1)SBCS Xn, Xm, Xd

ADC 和 SBC

ADC 和 SBC 是不设置输出标志的相应指令。

这使事情有点不同，因为我们不能用前置指令破坏标志，但另一方面，我们不需要担心准确地设置它们。

我们不是事先设置进位位，而是在之后对目标加一或减一。

// ## 原始// Xd = Xn + Xm + CADC Xn, Xm, Xd
// ## 变异1// Xd = Xn + XmADD Xn, Xm, Xd
// ## 变异2// Xd = Xn + XmADD Xn, Xm, Xd// Xd = Xd + 1ADD $1, Xd, Xd
// ## 原始// Xd = Xm - Xn - (C - 1)SBC Xn, Xm, Xd
// ## 变异1// Xd = Xm - XnSUB Xn, Xm, Xd
// ## 变异2// Xd = Xm - XnSUB Xn, Xm, Xd// Xd = Xd - 1SUB $1, Xd, Xd

还有一个问题：如果其中一个操作数是零寄存器 ZR，则等效的 ADD 或 SUB 无法编码，因为如果不设置标志，向零加减而不是存储就没有意义。在这些情况下，我们变异为适当的 MOVD。

CSEL

CSEL 是一个恒时选择，根据标志（通常是相等或进位标志）存储一个值或另一个值。

将其变异为 MOVD 很简单。

// ## 原始// Xd = Xn if X else XmCSEL X, Xn, Xm, Xd
// ## 变异1// Xd = XnMOVD Xn, Xd
// ## 变异2// Xd = XmMOVD Xm, Xd

结果

我最初在 arm64 P-256 汇编上运行了这个，出于白鲸和硬件可用性的原因，它发现了一些未测试的指令，包括……在 p256SubInternal 中，该死。

编写测试来覆盖它们很繁琐，有时非常困难，因为像 P-256 字段溢出深藏在函数中这样的 2^-32 边缘情况很难明确命中。这是另一个迹象，表明这个汇编核心应该被分解为更小、更易于测试的操作。

要了解我与加密汇编斗争的最新情况，请在 Bluesky 上关注 @filippo.abyssdomain.expert 或在 Mastodon 上关注 @filippo@abyssdomain.expert。更多精彩内容 请关注我的个人公众号 公众号（办公 AI 智能小助手）对网络安全、黑客技术感兴趣的朋友可以关注我的安全公众号（网络安全技术点滴分享）

公众号二维码

办公AI智能小助手

公众号二维码

网络安全技术点滴分享