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标志允许用一个或多个其他指令替换任何程序计数器的指令。实现起来相当容易，重用了解析器并修补了指令链表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

$ GOARCH=amd64 go test crypto/ed25519 -asmflags=crypto/internal/fips140/edwards25519/field=-mutlist -c
# crypto/internal/fips140/edwards25519/field
asm: 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, DI
asm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:24: 00013 ADCQ  DX, SI
asm: 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将两个寄存器和进位相加，并设置输出标志。

1
2

// Xd = Xn + Xm + C
ADCS Xn, Xm, Xd

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

1
2

// Xd = Xn + Xm
ADDS Xn, Xm, Xd

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

1
2
3
4

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

SBCS是等效的减法指令，我们以相同方式变异它，除了SUBS表现得好像进位（即"无借位”）标志总是被设置，所以我们需要在镜像变异中取消设置它。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// ## 原始
// Xd = Xm - Xn - (C - 1)
SBCS Xn, Xm, Xd

// ## 变异1
// Xd = Xm - Xn
SUBS Xn, Xm, Xd

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

ADC和SBC

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// ## 原始
// Xd = Xn + Xm + C
ADC Xn, Xm, Xd

// ## 变异1
// Xd = Xn + Xm
ADD Xn, Xm, Xd

// ## 变异2
// Xd = Xn + Xm
ADD Xn, Xm, Xd
// Xd = Xd + 1
ADD $1, Xd, Xd

// ## 原始
// Xd = Xm - Xn - (C - 1)
SBC Xn, Xm, Xd

// ## 变异1
// Xd = Xm - Xn
SUB Xn, Xm, Xd

// ## 变异2
// Xd = Xm - Xn
SUB Xn, Xm, Xd
// Xd = Xd - 1
SUB $1, Xd, Xd

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

CSEL

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

将其变异为MOVD很简单。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// ## 原始
// Xd = Xn if X else Xm
CSEL X, Xn, Xm, Xd

// ## 变异1
// Xd = Xn
MOVD Xn, Xd

// ## 变异2
// Xd = Xm
MOVD Xm, Xd

结果

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

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

要了解我与加密汇编斗争的最新情况，请在Bluesky上关注@filippo.abyssdomain.expert或在Mastodon上关注@filippo@abyssdomain.expert。