检测并解决数值计算溢出问题

问题背景 ##

数据类型是个好东西，类型定义了一种数据组成以及允许在其上进行的操作。 数据类型是个好东西，它定义了一种最基础的“安全”，类型安全。

我们在进行数值运算时，有可能会“超出”类型本身的值域，但是受限于位宽限制，进而表现为“上溢出”。以a+b为例：

• 如果a、b都是有符号数，且其符号相同，有可能超过最大值、最小值而在值域空间中轮转； 两个正数相加，结果却是负数；两个负数相加，结果却是正数.
• 如果a、b都是无符号数，也有可能超过最大值而在值域空间中轮转。

这个很容易理解，今天我们想看下如何解决此类问题。

如何解决溢出问题 ##

升级32位到64位？ ##

这通常是第一反应，它可能是有效的，也可能无效。

• 有效：如果输入int32 a、b是有明确约束保证的，比如任意一个都必须在[-1*1«31,(1«31)-1]， a+b可能对int32可能会溢出，但是如果提升成int64则可以解决问题，前提有这样的约束保证；
• 无效：没有任何输入约束做保证，只是简单提升成int64 a、b是没有用的，极端情况，a=b=1«36-1， a+b很明显就溢出了，这种就需要其他方法做保证。

设计上应该有上限？ ##

在设计上就要有这方面的“数据”上的“安全”的意识，比如：

• 玩家每赛季的经验应该是有上限的，满经验后就提示玩家满经验，后续就不给加了；
• 比如用uint32表示经验值，那么加之前先测一下是否发生了溢出(v=orig+delta, 如果v小于任意一个则溢出) 这很好理解，正常情况下，v应该大于orig、delta，就是逻辑反嘛。 ps：不好理解？把值域想象成一个转盘，delta不可能让v在值域范围内“环绕 (wraparound)”/“转到”orig，反之orig也不能让v转到delta。 如果发生了溢出，则直接将v=maxUint32完事，多出来的就扔掉，提示玩家满经验。
• 或者，这里的满经验不一定要maxUint32，可以是认为设计好的一个小值，比如99999； 如果输入有约束，比较小比如int8 a, int8 b，那么至少可以保证 if a+b > 99999 then v=999999 是ok的， 也不会触及累积量v达到uint32最大值的情况。可能这种情况比较理想化了。

检查是否发生溢出？ ##

言归正传，还是要有办法来比较可靠地检查运算结果a+b是否发生了溢出？

• 可以用大数计算来避免溢出，比如golang里面的math/big包。 比如int32 a,b相加，按int c=a+b的方式，c有可能是个溢出后的错误结果。 但是如果用大数计算，位宽充足可以算出正确结果，只要将其和maxInt32比较下即可知道是否发生了溢出。 如果确实发生了溢出，应该如何处理，如fallback到满经验值不再加经验。
• 也可以不用大数计算，通过一些有趣的副作用也可以知道是否发生了溢出。 比如在x86汇编中，可以通过 test OF,OF 来判断是否发生了溢出。 高级语言中，就没那么直接，比如go，得借助一些其他办法来判断，这就是这个math_test.go要测试的东西。

代码测试：运算时检测溢出 ##

测试代码，请移步：https://github.com/hitzhangjie/codemaster/blob/master/math/math_test.go。

math_test.go中定义了两个函数safeSignedAdd、safeUnsignedAdd来对有符号数、无符号数加法进行安全的计算：

• 如果发生了溢出则返回错误，方便调用方处理；
• 如果没发生错误则返回两数之和；

我们想检测下如何更好地发现一些造成溢出的边界条件，我们使用go fuzztest来帮助发现潜在的问题。 我们设置了边界附近的值作为seed scorpus，这样方便go fuzztest引擎使用mutator微调输入参数时能够覆盖到边界条件。

其实也可以使用go fuzztest的随机构造输入的模式，但是这样往往需要执行更多的时间才有助于发现问题。 ps：改天再写篇文章详细介绍下go fuzztest内部是如何工作的。

这里看起来我们是为了使用go fuzztest而使用fuzztest，比如你怎么精心构造这样的seed scorpus的？其实不是为了用而用。

• 当我们设计实现一个函数时，脑海中应该知道输入是啥、输出是啥，过程中的极端case是啥，那你就有了一个输入的值域范围， 或者说不同的参数组合有几种特殊的情况，可以多次调用 f.Seed(v1,v2,…)，来将这些参数作为一个seed scorpus， 以方便后续模糊测试引擎微调这些参数来覆盖特殊分支。
• 你不一定要精心构造出一定能触发异常边界的seed scorpus，你可以设置个大概的值，然后交给模糊测试引擎去做剩下的工作， 假定一个参数是uint32类型，你设置的seed参数设置的是n，那么这个n最终会在[n-100,n+100]的范围内变化，当然下界、 上界要在uint32范围内，每个参数都会这样变化。所以你的seed scorpus不一定刚好触发边界。 模糊测试运行过程中，如果它发现某个输入发生了错误（t.Errorf标记的），或者此输入导致代码覆盖率提升了（给每条语句插桩）， 那么就会将当前输入作为一个新的seed scorpus存起来，在其基础上微调参数执行。
• 最终我们尽可能地覆盖了更多的代码，并尽力去发现可能存在的边界异常。但是确实不能保证一定能找到问题。

随机模式的话，输入参数随机意味着逼近边界异常处需要更多的测试用例，可能耗时很长才能发现，但是也不一定能发现。

测试覆盖：模糊测试!=漫无目的的测试 ##

在执行uint32上溢出模糊测试时，我专门设计了一个seed scorpus，如下所示：

f.Add(uint32(0xffffffff-1000), uint32(0))

此输入下，mutator无能为力，执行了几分钟也发现不了问题，如果知道mutator原理的就很容易明白为什么。

$ go test -v -count=1 -fuzz=Fuzz_overflow_uint32 -run=^$
=== FUZZ  Fuzz_overflow_uint32
fuzz: elapsed: 0s, gathering baseline coverage: 0/1 completed
fuzz: elapsed: 0s, gathering baseline coverage: 1/1 completed, now fuzzing with 16 workers
fuzz: elapsed: 3s, execs: 767120 (255688/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 6s, execs: 1551732 (261545/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 9s, execs: 2352907 (267067/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 12s, execs: 3148542 (265216/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 15s, execs: 3945075 (265509/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 18s, execs: 4751252 (268643/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 21s, execs: 5550572 (266165/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 24s, execs: 6352445 (267419/sec), new interesting: 1 (total: 2)
......................................................................
fuzz: elapsed: 2m33s, execs: 40082850 (257913/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m36s, execs: 40876146 (264475/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m39s, execs: 41660462 (261389/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m42s, execs: 42442111 (260618/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m45s, execs: 43234687 (264132/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m48s, execs: 43994959 (253473/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m51s, execs: 44772385 (258989/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m54s, execs: 45562731 (263543/sec), new interesting: 1 (total: 2)
fuzz: elapsed: 2m57s, execs: 46340129 (259039/sec), new interesting: 1 (total: 2)
^C

然后，进一步可以纠正下错误的测试思想，模糊测试!=漫无目的的测试，seed scorpus matters!

当我们设计上有章法，测试时关注边界，自然知道seed scorpus该如何设置，比如我们改成：

f.Add(uint32(0xffffffff), uint32(0))

继续执行测试，很快就发现了边界case，代码中我们加了模糊测试的次数，发现第9轮它便发现了问题。

go test -v -count=1 -fuzz=Fuzz_overflow_uint32 -run=^$
=== FUZZ  Fuzz_overflow_uint32
fuzz: elapsed: 0s, gathering baseline coverage: 0/1 completed
fuzz: elapsed: 0s, gathering baseline coverage: 1/1 completed, now fuzzing with 16 workers
fuzz: elapsed: 0s, execs: 9 (383/sec), new interesting: 0 (total: 1)
--- FAIL: Fuzz_overflow_uint32 (0.02s)
    --- FAIL: Fuzz_overflow_uint32 (0.00s)
        math_test.go:31: iter-9 4294967198 + 118 = 20, err: overflow
    
    Failing input written to testdata/fuzz/Fuzz_overflow_uint32/a6532fa5f002651bb1003d5aedbea9bb5716a6d2a8fe7afff0b5252599a6d59b
    To re-run:
    go test -run=Fuzz_overflow_uint32/a6532fa5f002651bb1003d5aedbea9bb5716a6d2a8fe7afff0b5252599a6d59b
FAIL
exit status 1
FAIL    github.com/hitzhangjie/codemaster/math  0.026s

小结 ##

总结了下如何解决数值计算时的溢出问题，从编码上、从策略上，以及介绍了如何使用go fuzztest来更好地发现潜在的问题。 关于模糊测试的一点想法，模糊测试 != 漫无目的的测试，seed scorpus的选择和设置很有价值。后面有时间会写下go模糊测试的工作原理。

ps：对于溢出问题、环绕问题，go的类型系统都存在。在编译时，如果发生溢出，编译器会直接抛出错误，比如“constant ??? overflows uint32”；如果是运行时溢出，则会出现环绕（wraparound），此时就需要显示检查并避免环绕了。