Complexity Theory of Randomised Testing
本文通过将生成器建模为图灵转换器，为随机测试建立了首个复杂度理论基础，以刻画高效及空间受限输入的生成极限，揭示了生成复杂度与判定复杂度之间的本质区别，并证明了高效生成需要特定的证书方案，且无法从一般的逻辑谓词中进行组合式推导。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下你是一名游戏开发者，正在测试一个全新的、宏大的世界。为了确保你的游戏不会崩溃，你需要一个机器人，它能吐出数百万个随机的关卡、角色和道具，以此来观察是否会有东西出错。这个机器人被称为生成器（generator）。多年来，开发者们一直通过手工构建这些机器人，不断微调它们，直到它们足够好用。但没有人真正了解这些机器人实际能力的理论极限是什么——它们能否生成任何可能的关卡？它们生成的效率是否足够高，以至于具有实用价值？
来自帝国理工学院和开泰（Kaihong）的研究小组决定用复杂度理论（Complexity Theory）——研究问题求解难度的数学——将这些机器人置于显微镜下进行观察。他们不仅观察了代码，还将这些机器人建模为“图灵机”（最完美的理论计算机），这些机器通过“吃掉”随机的数据并“吐出”游戏关卡来进行工作。以下是他们的发现。
“什么可以被制造出来”的清单
首先，他们提出了一个问题：一个生成器的绝对极限是什么？
他们发现，如果你给生成器无限的时间和内存，它所能产生的集合与标准计算机能够“识别”的集合完全一致。在数学领域，这被称为**递归可枚举（Recursively Enumerable, RE）**语言。
- 好消息： 如果一组输入（例如“所有有效的 C 程序”）可以被计算机识别，那么理论上生成器就可以产生它们。
- 坏消息： 如果一组输入过于“诡异”，以至于无法被计算机识别（例如“所有永远不会停止运行的程序”），那么没有任何生成器能够产生它们。这不是你代码中的 Bug，而是宇宙的基本法则。你无法构建一个能吐出所有无限循环的机器人，因为数学证明了列举它们是不可能的。
“路障”问题
接下来，他们问到：如果我们要求生成器必须很快呢？ 在现实世界中，你不能等待一百万年才得到一个测试用例。你需要几秒钟内就能得到结果。
研究人员发现了一个令人惊讶的转折：能够“检查”某物是否有效，并不等同于能够“制造”出有效的东西。
- SAT 求解器示例： 想象一个谜题，你必须找到一组特定的开关组合来点亮一盏灯。检查一个组合是否有效是很困难的（它是“NP 完全”问题）。但研究人员表明，你可以构建一个快速的机器人来生成这些有效的组合。它的原理是“植入见证者”：机器人先秘密挑选一个获胜的组合，然后围绕它来构建谜题。
- 哈希碰撞陷阱： 然而，他们同时也证明了对于某些问题，即使检查答案很容易，制造答案也可能无法快速完成。他们研究了“哈希碰撞”（寻找两个产生相同数字指纹的不同输入）。检查两个指纹是否匹配非常快。但寻找一对匹配的输入呢？如果你能构建一个快速的机器人来做这件事，你就会破坏几乎所有现代加密技术的安全性。
- 结论： 除非密码学世界被破解，否则存在这样一类问题：检查很容易，但生成很难。 你不能仅仅通过愿望让生成器变快；有时，数学本身就不允许这样做。
“内存”约束（模糊测试与反馈）
许多现代测试工具（如“模糊测试器/fuzzer”）不仅仅是随机吐出数据，它们还会记住之前尝试过的内容。如果一个测试导致了程序崩溃，模糊测试器会记住这一点，并尝试通过微调输入来再次触发崩溃。这就像一个从每个线索中学习侦探。
研究人员将此建模为一个具有有限**内存（空间）**的生成器。他们发现，即使拥有这种“内存”和反馈循环，生成器仍然受到限制。
- 极限： 如果生成器拥有多项式级别的内存（这涵盖了几乎所有的实用工具），它只能生成属于 PSPACE 类别的对象。
- 现实检查： 这意味着，即使是最聪明、最耗费内存的模糊测试工具，也无法为“EXPTIME 完全”（即需要指数级时间求解的问题）类别的题目生成输入。如果一个问题过于复杂，以至于 PSPACE 机器都无法解决，那么再多的反馈或内存也无法帮助生成器创建测试用例。
“组合性”的神话
最后，他们挑战了软件工程师的一个梦想：我们能否构建一套生成器的“乐高套装”？
想象一下，你拥有这样一个工具：你说“我想要一个生成 A 且 B 的生成器”，或者“我想要一个生成 非 A 的生成器”，然后该工具会自动将它们组合成一个新的、快速的生成器。
该论文在标准假设下对这个梦想给出了坚定的回答：不（NO）。
- 规则： 你不能通过“与”（AND）或“非”（NOT）自动组合生成器，并保证它们依然保持快速。
- 原因： 如果你能做到这一点，你就能解决那些目前被认为无法快速解决的问题。
- 例外： 对于非常简单、受限的逻辑类型（如“线性 Datalog”或“NL”问题），你可以这样做。但一旦加入了复杂的“与”或“非”逻辑，这种魔力就会消失。如果你想组合复杂的规则，你必须放弃对速度的保证，或者接受你的生成器可能只是通过“尝试并失败”（拒绝采样）来碰运气。
大局观
论文总结道，生成数据是一个与“判定数据是否有效”截然不同、且通常更具挑战性的任务。
- 已证实的： 他们证明了所有可生成事物的集合恰好是递归可枚举的集合。他们证明了某些难题（如 SAT）存在快速生成器，但对于其他问题（如假设加密安全的哈希碰撞）则不然。他们证明了基于反馈的工具受限于 PSPACE。
- 被排除的可能性： 他们排除了构建一个通用的、快速的、可组合的库来处理任何逻辑组合规则的可能性。他们排除了“易于检查”必然意味着“易于生成”的可能性。
简而言之，如果你正在构建一个测试机器人，你不能仅仅指望它变得既快又聪明。数学已经在沙滩上画出了一道分界线：有些事情是无法生成的，有些事情是无法快速生成的，有些事情如果你想进行组合，就必须牺牲速度。但现在，我们终于知道这些分界线究竟在哪里了。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。