模糊中的饱和效应

2020-06-18 01:58:35

我们将模糊器应用于一些非平凡的被测系统(SUT),最初它发现了很多错误。

当这些错误被修复后,SUT就会对这种模糊效果产生免疫力:由模糊效果发现的新错误数量下降,最终接近于零。

第一个绒毛是怎么回事?有两件事正在发生。首先,任何给定的随机输入源触发系统中的错误的频率遵循幂律分布。随着经常触发的错误被发现和修复,我们最终只剩下触发概率极低的错误,以至于在合理的计算预算内实际上无法找到这些错误。其次,即使给定无限的CPU时间,某些bug对于给定的模糊器也是遥不可及的。例如,如果我们使用csmith对GCC进行模糊处理,我们将永远不会在GCC的字符串比较优化中发现错误,因为csmith无法生成比较字符串的代码。类似地,JPEG压缩器的模糊器只构建1000×1000像素的图像,全部是相同的随机颜色,不太可能能够发现大多数错误。这些例子都是基本的,但几乎每一种绒毛器,无论多么复杂,都有类似的局限性。

第二个问题通常是更可取的:我们可以通过在基于世代的模糊器中添加新功能,或者通过为基于突变的模糊器找到一组更好的种子来解决这个问题。即使我们对这些尚未发现的漏洞一无所知,我们也常常可以通过注意到模糊器造成的覆盖率差距来推断它们可能存在。

第一个问题通常更难解决,因为我们通常并不真正理解触发特定bug的测试用例空间如何与我们的模糊工具中隐含的概率分布相交。我们可以调整和调整模糊器中的概率,以改变分布,但如果没有可靠的指导,这通常并不比猜测更好。

关于绒毛饱和度的研究并不多。原则上,基于覆盖率的停止标准就是针对这一点,但大多数标准只是设定了一些中等难度的目标,并假设如果你达到了目标,你就完成了。因为对于任何复杂的SUT,大多数模糊化工作永远不会达到任意的、高代码覆盖率目标,所以这是没有用的。据我们所知,特拉蒙塔纳等人提出了一些与典型饱和度更相关的建议。他们建议将测试工作分成k个子集,每个子集都有自己的覆盖度量,当所有k个子集都有相同的覆盖时停止。k越大,检测饱和度所需的时间就越长,但您越能确信测试已经“完成”。停止点不需要在覆盖率方面;相反,它可以使用自动的bug分类来查看是否所有运行都发现了相同的bug集。

两种不同类型的饱和相互作用是可能的。当然,就缺陷发现而言,最重要的饱和是饱和:一种特殊的测试用例生成方式已经达到了极不可能产生新缺陷的地步。然而,我们不仅仅关注测试中的bug发现;我们还关注覆盖率,并使用覆盖率作为测试进展的信号。关键的是,不只是人类这样做;模糊器使用某种新的覆盖(CFG边缘、路径,甚至数据流)来指导它们的行为。AFL试图覆盖新的道路作为其主要目标,新的撞车事故是一种副作用。然而,这意味着在实践中可能有四种饱和情况:

覆盖面没有饱和,错误也没有饱和。这就是你不需要考虑饱和度的情况。您的测试过程正在频繁地生成新的覆盖率和新的错误;只需继续模糊即可。

覆盖面饱和了,错误也饱和了。相反的情况也很简单:如果既没有生成新的覆盖范围,也没有生成新的bug,那么是时候进行更改了,比如改进Fuzzer,或者可能找到不同的SUT来作为目标。

覆盖率是饱和的,但错误并没有饱和。这是一个有趣的案例,其中使用的覆盖度量不够有表现力。换句话说,覆盖率停止增加不是因为不可能对SUT进行进一步有趣的探索,而是因为覆盖率与导致新错误的执行空间探索的种类相关性很差。很容易陷入这种情况,例如,如果覆盖率的概念很弱(语句覆盖率),错误往往依赖于命中特定的路径或状态,而不仅仅是命中错误的代码位置。这可能是自动终止模糊化努力的问题,这可能是因为模糊器看起来已完成,但实际上仍在生成良好的结果,或者(更常见的)当AFL/libFuzzer由于覆盖信号不能帮助其到达输入空间的另一部分(其中覆盖可能不再饱和)而停滞时。AFL/libFuzzer的路径依赖性意味着,只需从相同的语料库重新开始,或者从另一个Fuzzer添加一些新的种子,可能有助于避开这个特定的陷阱。

覆盖率不是饱和的,但是错误是饱和的。这是一种真正的可能性,也是覆盖率驱动型模糊中的一种真正的痛苦。在使用AFL对编译器进行模糊处理时,经常会看到运行陷入困境,生成大量不感兴趣的路径,想必是在探索“让解析器失败的方法”之类的东西,而这些东西很少产生有趣的错误。最近关于指定不计入覆盖范围的代码部分的研究可以帮助解决这个问题。在我们使用AFL对真实编译器进行模糊处理的经验中,“Pending:”字段通常不会变为零,即使没有什么有趣的事情发生,并且Fuzze已经运行了几天或几周。

在真正的模糊化工作中,饱和不是一次性的事情,而是对被测系统中的新代码或模糊化机制中的变化做出响应的潮起潮落。例如,下面的图表显示了我们为Solc Solidity智能合约编译器提交的GitHub问题数量(几乎所有的实际错误,以及少量已知错误的重复),这是一项正在进行的研究工作的一部分,目的是使使用AFL的模糊编译器变得更容易。以下是关于这一模糊努力的更多细节。

我们在2月初开始对编译器进行模糊处理,立即发现了几个bug,既使用了我们的新技术,也使用了普通的旧AFL。然后我们继续运行Fuzzer,但几天来没有发现任何新奇的东西。在2月21日,我们给我们的模糊引擎增加了几个新的突变器(参见例如,这个提交),并“打破”了饱和。然后有一个很长的间隙,在运行Fuzzer一个多月后,在一个由之前任何一次运行发现的每条有趣路径组成的语料库上,最终发现了几个bug,执行了超过10亿次编译。

然而,就在最近,我们做了另一个改变。之前,我们的语料库只基于固态编译器的语法测试;我们在5月14日切换到使用存储库的整个测试子树中的所有固态文件。这导致了一些新的错误,例如在SMTChecker中(之前根本没有进行模糊处理)。“不过,我们可能很快就会恢复饱和!”请注意,在这段时间里,AFL中没有模糊实例(我们已经运行了大量模糊实例)达到路径覆盖饱和。

Bohme和Falk刚刚接受的一篇FSE论文就饱和障碍的性质提供了更明确的经验数据:线性地找到一组给定错误的更多实例需要线性更多的计算能力来对目标进行模糊处理;线性地找到更明显的错误需要指数级更多的模糊计算能力。

除了理解和检测饱和度之外,我们当然希望能够推迟它的开始。也就是说,我们希望在给定的Fuzzer饱和之前找到更多的bug。对于基于突变的模糊者来说,这是一个相对自然和容易的活动,因为我们不仅可以在寻找种子时撒下更大的网,而且我们还可以以一种相对无痛的方式添加新的突变算子,因为突变应该是相互独立的。

从头开始生成代码的Fuzzer是一种更棘手的情况。也许我们所知道的最接近免费午餐的事情是群测试,它在生成新的测试用例之前随机重新配置Fuzzer。目标是避免这样的问题,即大量随机选择的产品最终看起来或多或少都是一样的。(低维示例是一组图像,每个图像都是通过以50%的概率随机将每个像素指定为黑色或白色来创建的。这些都不容易区分。)。

改进卡住的绒毛器,例如通过教它生成更多SUT支持的功能。

最后一种选择可能是最有希望的:目前,将生成性模糊与反馈驱动模糊相结合的技术水平还不是很成熟。我们相信这里还有很大的改进空间。