7

在处理大型软件项目时，我经常使用模糊测试作为测试用例的一部分，以帮助消除可能仅在输入达到特定大小或形状时才会出现的错误。我最常用的方法是使用与我碰巧使用的编程语言捆绑在一起的标准随机数工具。

最近我开始怀疑，忽略一般模糊测试的优点或缺点，在进行模糊测试时使用非密码安全的伪随机数生成器是否是个好主意。弱随机数生成器经常表现出将它们与真正的随机序列区分开来的模式，即使这些模式并不明显。似乎使用弱 PRNG 的模糊测试可能总是无法触发某些仅在某些情况下出现的潜在错误，因为伪随机数可能以一种永远不会触发这些情况的方式相互关联。

使用弱 PRNG 进行模糊测试是否天生不明智？如果在理论上这样做是不合理的，那么在实践中是否仍然合理？

4

3 回答 3

6

您混淆了两种截然不同的“弱点”等级：

  • 统计弱点意味着 PRNG 的输出表现出统计模式，例如某些序列比其他序列更频繁地出现。在极少数情况下，这实际上可能导致无效的模糊测试。统计上强大的 PRNGs 是高性能的并且广泛可用（最突出的是 Mersenne Twister）。
  • 密码学上的弱点意味着RNG的输出在某种程度上是可预测的，除了种子之外的知识（例如输出本身）。要求用于模糊测试的 PRNG 具有强大的加密能力是绝对没有意义的，因为统计上强但加密弱的 PRNG 所展示的“模式”几乎只是一个问题，如果您需要防止精通密码的攻击者从预测输出。
于 2011-03-28T09:32:17.543 回答
4

我认为这并不重要，但我无法证明这一点。

模糊测试只会尝试一些输入，在大多数情况下，可能性很小。无论您使用的 RNG 有多好，它可能会或可能不会找到破坏您的代码的输入之一，这取决于所有可能的输入中破坏您的代码的比例。除非 PRNG 中的模式非常简单，否则在我看来，它不太可能以任何方式与您正在寻找的“坏”输入中的模式相对应，因此它不会多于或少于真正的随机。

事实上，如果你知道如何选择一个 RNG 来最大化它找到错误输入的概率，你可能会使用这些知识来帮助更直接地找到错误......

我认为您不应该使用非常糟糕的 PRNG。rand例如，允许展示非常简单的模式，例如 LSB 交替。如果您的代码在内部使用 PRNG，您可能希望避免在测试中以类似的方式使用相同的 PRNG，以确保您不会意外地仅测试输入数据与内部生成的数字流匹配的用例！当然，风险很小，因为您希望他们会使用不同的种子，但仍然如此。

在给定的语言中，找到加密或至少是安全的哈希库通常并不难。SHA-1 无处不在，并且易于使用来生成流，否则 RC4 对自己的实现是微不足道的。两者都提供了相当不错的 PRNG，虽然不如 Blum Blum Shub 安全。我认为主要关注的是速度 - 例如，如果 Mersenne Twister 可以以 10 倍的速度生成模糊测试用例，并且被测代码相当快，那么它可能更有可能在给定的情况下找到错误的输入时间不管给定 624 个输出，您都可以推断出 RNG 的完整状态...

于 2011-03-28T09:16:10.250 回答
2

您不需要不可预测的来源（这正是加密安全生成器的本质），您只需要具有良好统计属性的来源。

因此，使用通用生成器就足够了 - 它速度快且通常可重现（这意味着问题也是可重现的）。

于 2011-03-29T07:20:18.823 回答