环绕正则表达式：从模糊测试正则表达式库中学到的经验（第二部分）
我稍微迟到了（整整一个月眨眼就过去了！）。让我们继续探讨。
我们简要探讨了模糊测试存在某些局限性的观点，特别关注了与测试工具和输入变异相关的问题。有时候，即使我们做对了所有事情，模糊测试工具仍然难以发现漏洞。正则表达式引擎在这方面表现得尤为明显；让我们通过研究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个漏洞，都是由两名开发人员在空闲时间处理的。
我希望这种有些脱节的思考能帮助其他人制作更好的模糊测试工具，发现更多漏洞，并帮助开发人员修复它们。