环绕正则表达式：从模糊测试正则库中汲取的经验（第二部分）
addison 发布于 2024年8月23日
稍微迟了一些（整整一个月眨眼就过去了！）。让我们继续探讨。
我们简要探讨了模糊测试存在一些局限性的观点，特别关注了与测试工具和输入变异相关的问题。有时，即使我们做对了所有事情，模糊测试工具仍然难以发现漏洞。正则表达式引擎在这方面表现得尤为明显；让我们通过研究PCRE2来找出原因。
目标二：PCRE2
PCRE2（很可能！）是全球使用最广泛的正则表达式库。它最初在1998年作为PCRE启动，由于重大的API变更，最终在2014年升级为PCRE2。我强烈推荐阅读Joe Brockmeier关于该库及其主要开发者Philip Hazel的文章——这个库及其作者有着相当惊人的历史。
几个月前，在我探索rust-regex几年之后，我在一个研究项目中偶然发现了PCRE2中的一个漏洞。该漏洞表明PCRE2的即时编译（JIT）组件中存在潜在缺陷。在CISPA，我们被鼓励调查这类旁支问题，而作为一个专注于模糊测试的人，我开始深入研究PCRE2中的模糊测试工具。
OSS-Fuzz，或称：习得性无助
有一个普遍的恐惧是，如果一个项目已经在OSS-Fuzz中，就没有必要再对其进行模糊测试。PCRE2尤其如此：它从一开始就在OSS-Fuzz中！到目前为止，PCRE2可能已经被模糊测试了多个世纪的CPU时间。
然而，OSS-Fuzz项目中仍然存在可通过模糊测试发现的漏洞。我们怎么会错过它们呢？
模糊测试内省器
为了解决这个问题，由David Korczynski领导的OpenSSF在2021年开发了Fuzz Introspector。该工具通过跟踪各种指标来检查模糊测试工具随时间推移的性能，并最显著地部署在OSS-Fuzz上。
通过这个工具，我们可以检查各种测试工具在OSS-Fuzz中的表现如何（或者更常见的是，表现有多差）。
我们可以看到，大多数目标的代码覆盖率非常低。这与人们可能对OSS-Fuzz中模糊测试目标覆盖程度的假设相悖，这也是谷歌花费大量资金试图解决的问题。然而，PCRE2历史上达到了很高的代码覆盖率，那么这里出了什么问题？
Fuzz Introspector的一个局限性是，它只能确定二进制文件中是否存在未覆盖的函数。在PCRE2的情况下，JIT编译器实际上从未包含在模糊测试中。因此，一旦启用，源代码的真实覆盖率显示要低得多：
因此，即使对于代码覆盖率高的程序，也不能仅仅表面认为代码已被充分覆盖。同样，覆盖率并不表示漏洞发现，因此我们不能仅凭覆盖率本身来判断。
你在JIT我吗？
为了改进OSS-Fuzz的测试工具，我提交了更改，使JIT编译器能够与正常执行器一起进行模糊测试。我们这样做是因为仅对JIT编译器进行模糊测试是不够的。
考虑代码覆盖率测量的机制。在libFuzzer中，这是通过SanitizerCoverage传递实现的，它在代码点添加回调，以跟踪某些边的遍历。为了跟踪覆盖率，代码必须在编译时存在。
在存在JIT编译器的情况下，执行的代码不能保证在编译时生成。
当使用JIT编译器时，一些代码在运行时生成。这可能导致奇怪的问题，即我们覆盖了JIT编译代码，但没有覆盖编译后的代码本身。例如：考虑一个像a|(0)的正则表达式（“匹配字面量a或捕获字面量0”）。JIT编译器发出捕获代码，但如果我们仅在输入a上执行这个正则表达式，我们将永远不会实际运行发出的代码，意味着我们永远不会执行执行捕获的代码。实际上，JIT编译器的代码覆盖率代表了已执行正则表达式覆盖率的超集。
为了解决这个问题，当对JIT编译的正则表达式进行模糊测试时，我们还必须在不使用JIT的情况下执行每个正则表达式，以了解执行过程中实际使用了哪些代码区域，以免高估我们实际测试而不仅仅是生成的内容。但即使这样也可能产生误导，因为JIT实现不一定与“经典”实现密切相关。每个实现中可能有需要测试的特定优化，并且不能保证在覆盖率测量的代码中存在与JIT发出的代码区域相对应的代码区域。因此，这是一个不可避免的局限性。
但是Addison，你可以在QEMU或其他东西中测量代码覆盖率！
你不想这样做。JIT区域每次执行程序时都会改变，它实际上将每个测试的正则表达式变成了必须被覆盖的小程序。更重要的是，区分两个正则表达式是否有意义地不同并非易事。如果没有对哪些JIT区域由哪些JIT编译器区域产生和影响的重大投入，这只会导致被认为“有趣”的输入爆炸式增长，而没有实际进展。
TL;DR：不要对JIT编译器使用模拟代码覆盖率。
正则表达式不仅仅是解析器
模糊测试工具最初是针对解析程序（如图像解析器）设计的。这些程序通常很简单；当你解析图像时，到达给定解析区域的方式只有那么多。同样，影响代码如何解析输入相应区域的状态也只有那么多。
正则表达式引擎首先解析模式，然后执行由该模式表示的（非常有限的）程序。当你探索解析器的覆盖率时，你通常探索了解析器的大部分行为（有明显的例外）。当你探索正则表达式引擎的覆盖率时，你只探索了其行为的很小一部分，因为模式先前处理的内容对模式将解析的内容有巨大影响。对于PCRE2尤其如此，它支持引用先前捕获的数据和上下文特定的执行行为控制。
更一般地说，随着程序对输入的解释复杂性增加，更多的程序状态决定各种代码区域的行为，它们的相互作用变得比仅覆盖率更重要。因此，虽然覆盖率在历史上有效地衡量了程序的探索，但它根本无法表达你是否探索了代码区域所有可能的行为方式（更相关的是，它可能如何失败）。这是覆盖引导模糊测试的一个强烈局限性，主要影响需要最多测试的高度复杂目标。到目前为止，在这方面对模糊测试工具的改进很少，任何在“我们是否曾命中代码区域”之外对我们探索复杂程序能力做出有意义、可推广且高性能改进的人，都将彻底改变我们的领域。
既然我们不能仅依赖覆盖率探索，让我们希望我们的变异足够强大，能够创建导致程序行为组合的输入，从而触发更复杂的行为，这些行为在代码覆盖率上无法区分。
不可避免的重新解释问题
上次，我们讨论了如果变异不保留输入的含义，输入可能会被重新解释。虽然rust-regex的测试工具仍然没有稳定的解释（即长度变化仍然可以改变输入的含义），但PCRE2有，因为它使用测试的模式作为输入本身，并且只变异模式。然而，变异仍然可能破坏（或显著修改）输入的解释，因为对格式良好的正则表达式进行字节变异不会合理地转换输入。
例如：仅仅在模式中插入一个(几乎总是导致模式无效，因为括号不匹配（有一些例外，例如：[...(...]）。我们依靠运气对输入进行有意义的修改。
交叉作为灵丹妙药？
交叉是将两个输入组合以产生一个新输入的过程，该新输入表现出两个原始输入的特征。该策略从遗传算法中引入，但遗憾的是也受到重新解释的影响，因为两个输入在交叉时不考虑它们所代表模式的语义。因此，当覆盖率不足时，不能依赖它来“混合”行为从而更好地探索程序。
好吧，那么为什么不制作一个语法并从那里变异呢？
请这样做！
发现
随着模糊测试工具的更新以包括JIT，我发现了JIT编译器中的几个漏洞和一些私下报告的问题。在正常情况下，攻击者无法控制模式时，这些漏洞实际上都无法利用。
差分模糊测试
既然我们已经同时执行正则表达式的“经典”实现和JIT实现，比较它们的输出应该很简单。
对吧？
测试工具很难
我不会深入比较两个输出的细节，但有很多极端情况使比较JIT与经典正则表达式变得非常复杂。主要是，有不同的优化和失败情况，导致一个成功时另一个失败，并且遍历结果有时也不简单。然而，最困难的部分是向用户传达问题究竟是什么——即两个输出产生的具体差异。开发一个测试工具来做到这一点是一个持续数月的过程，但最终确实发现了几个漏洞。
故障定位
找出导致差异的具体原因也可能相当困难。以这个问题为例，它让所有相关人员困惑了两周，我们甚至无法就输入的解释达成一致。由于专门通过差分预言机发现的漏洞根本原因的工具并不广泛可用，每个测试用例必须手动检查和调查。有时，我能够自己诊断原因，但无法确定相关代码区域，但有很多问题我依赖开发人员从头到尾发现根本原因。这是模糊测试的一个主要可用性失败：没有定位或修复建议，开发人员会因差分模糊测试工具发现的漏洞而遭受一种警报疲劳——特别是因为它们彼此之间不易区分。
我非常感谢开发人员忍受我不断的漏洞报告，并对新形式的测试持开放态度，即使这些漏洞似乎毫无意义。
等等，毫无意义的漏洞？
漏洞到底是什么？如果一个漏洞导致程序崩溃，但附近没有理智的用户受到影响，它仍然重要吗？
如果一个漏洞在正常情况下降低性能，并且不影响实际输入，你应该修复它吗？
差分模糊测试发现任何它能发现的差异，并同等抱怨它们，无论任何“真实”用户是否会受到影响。在使用此类工具时，有必要注意开发人员是否会在意，甚至是否愿意修复漏洞，因为它可能实际上不会影响任何人。
早期结论
我早已错过了这篇文章的截止日期。但我认为一些发现是有意义的，并希望在它变得无关之前发布。也许在未来，我会添加一些专门的模糊测试工具来测量和演示这里提到的一些效果，而不是仅仅告诉你在调试时发现了什么，但目前，这必须等待。
我认为这里的主要收获与第一部分相同：你不能依赖模糊测试工具神奇地为你找到所有漏洞，也不能告诉你导致它们的原因。每个测试工具和目标必须单独考虑可能出现的特定障碍或模糊测试工具性能的误报。此外，不要误以为在一个测试工具上花费大量模糊测试时间就是模糊测试可以发现的上限——许多测试工具根本无法发现某些漏洞。最后，在使用这些工具时，要意识到开发人员将如何反应；PCRE2模糊测试工具总共报告了大约50-60个漏洞，都是由两名开发人员在业余时间处理的。
我希望这种有些脱节的思考能帮助其他人制作更好的模糊测试工具，发现更多漏洞，并帮助开发人员修复它们。
标记：模糊测试