35

我有一个要进行单元测试的伪随机数生成器 (PRNG) 类。有两种方法：

  1. 编写一个需要大量样本的测试用例，并测试它们是否分布正确。这种方法可能会导致测试用例的执行时间相当长；
  2. “手动”计算一小部分样本并验证 PRNG 算法是否重现它。这种方法可能会导致在不被注意的情况下生成非随机序列；

我想说第一种方法不是真正的单元测试，因为它不执行生成器的白盒测试，但另一方面它正确地测试了类的责任。第二种方法更像是一个真正的单元测试，专注于算法，但它并没有提供太多的证据来证明类是否履行了它的职责。

你更喜欢哪种方法，为什么？

4

13 回答 13

32

获取相同 PRNG 算法的另一个实现，根据已知种子生成少量较长的测试用例，并验证您的算法实现与其他所有人的实现相匹配。你测试的数据越多，它的机会就越大。如果您想认真，请查看如何为算法完成 FIPS 验证。

无需测试输出是否是随机的，因为其他人对该算法所做的研究远远超出了您的复制能力。

如果您已经发明了自己的 PRNG 算法，那么您将遇到一个完全不同的问题，因为除了测试您的代码之外，您还需要测试您的新算法。有很多事情要做——我认为最重要的是对输出的统计测试，以及其他密码学家的同行评审。但是，基本上，如果您要设计一个 PRNG 算法而没有足够的领域知识来知道如何测试它，那么它将是垃圾。

于 2008-10-09T10:12:01.520 回答
14

为了测试 PRNG，我会使用ENT，它是一套统计测试，可以告诉您 PRNG 的执行情况。我想这是方法1。

于 2008-10-09T10:09:43.913 回答
5

我想最终你会想要两个测试 - 因为你想确保以下两个都成立：

(1) 数字分布正确，(2) 特定算法按预期工作。

也许第一个测试只能偶尔运行，而第二个可以用来检查任何代码更改是否没有破坏算法。

于 2008-10-09T10:10:59.947 回答
4

我相信您的第一点（＃1）在测试生成的随机数的质量时会得到更多，这是由所使用的算法决定的。第二点（＃2）在测试算法的实现方面得到更多。如果您设计了算法，那么这两个测试都很重要。如果你实现了一个表现出性能的算法，#2 应该就足够了。虽然，我可能会使用您的特定生成器结构的一些知识来测试多个种子和序列。

于 2008-10-09T10:32:37.237 回答
3

伪随机数生成器中的“随机性”通常表示为一个数字重复之前的平均迭代次数。有许多算法具有不同的“随机性”和性能。 Random.org很好地解释了对其算法进行的一些分析。查看页面一半左右的图片。在静态图像中很容易看出这两种算法的随机性。

PRNG 的一个特性（一个真正的特性，而不是伪装成特性的错误）是它是可预测的。对于给定的种子，应该产生相同的数字序列。这对于测试和调试使用随机（又名随机）方法的程序非常重要和必要。

数列应该近似于某种统计分布。通过生成一个大序列（比如 10^6 个数字）来测试您的 PRNG，并对序列执行多个统计测试，尤其是卡方检验（如果分布正常）。制作样本的直方图，看看它是否看起来像您期望的那样。

如果控制种子的设置方式，那么每次生成的序列应该是一样的，适合做白盒测试。在进行测试时，在收集样本之前运行生成器大约 100 次迭代来“预热”生成器也是一个好主意。

于 2008-10-09T12:08:01.023 回答
3

这是一篇CodeProject 文章，其中包括 Donald Knuth 的第 2 卷半数值算法中提到的 Kolmogorov-Smirnov 测试的实现。正如上面提到的 InSciTek Jeff，有两个问题：测试算法和测试算法的实现。KS 测试可能会发现实现中的错误，它是测试算法本身质量的良好开端。

于 2008-10-18T19:34:28.683 回答
2

请注意：如果您“发明”了您的 PRNG，那么您可能会弄错并产生一些分布不理想的东西。生成器随机性的基本测试是卡方检验

于 2008-10-09T11:07:14.093 回答
2

您可能会发现对这个问题的一些回答很有用。

基本上，您无法“证明”RNG 是随机的，但您可以执行各种测试来提高您的信心。这些测试的复杂性各不相同。 顽固分子是全面的，但它并没有真正提供是/否的答案，更像是几百个“也许”。在频谱的另一端，生成一系列值（至少 10,000 个）然后检查均值和标准偏差/方差是否符合预期非常简单。

于 2008-10-09T22:24:47.673 回答
1

一种方法是将其输出通过管道传输到PractRand。

如果 PractRand 说 PRNG 的输出没问题，那么 PRNG 真的没问题吗？我没有资格判断，但我能说的是 PRNG 足够严格，以至于它认为我在文献或网上找到的各种 LFSR 和 xor-and-shift 算法的输出不能令人满意，并且认为输出还可以RP Brent 的 xorgens。

于 2017-12-16T13:57:09.780 回答
0

严格来说，没有办法测试随机生成器是否真的是随机的 :-) 第一种方法让您知道它是否仅适用于固定数量的样本，无论这个数量有多大。第二种方法可以支持它是否像算法一样表现的知识，但同样适用于固定数量的样本。

你能做的最好的 - 使用两者。

于 2008-10-09T10:37:51.423 回答
0

除非您正在实施给定的 PNRG 算法，否则无法判断数字是随机的，这就是随机性的本质。是的，平均而言，当您的数字生成器趋向无穷大时，它会变得均匀，但您不会测试无限次数的迭代。

如果您正在实施一个已知算法，请检查前几千个数字是否与给定一组种子提供的结果相匹配。虽然可能的种子数量是无限的，但无法确定。

你甚至无法从数学上证明一个数字序列是随机的......

XKCD

替代文字

迪尔伯特

替代文字

被改装下来...

于 2008-10-09T11:45:01.770 回答
0

回到学校的时候，我正在为模拟作业开发一个随机数生成器，并且需要一些方法来识别非随机性。

我想到了取两个随机数并将它们绘制成图形（x，y）的好主意。人类大脑如何能够检测到非随机模式真是令人惊讶。（“随机模式”是矛盾的。）

我调整了 PRNG 以删除图表上出现的条纹和星爆，然后绘制 (log(x), log(y)) 以获得全新的视角并重复该过程。

后来，我被迫进行统计，并了解到你可以做一些奇怪的数学来量化随机性。

于 2008-10-18T19:59:44.420 回答
0

Random.org 使用这个测试套件：http ://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

您可以在以下位置下载软件（unix 和 mac os x）：http ://csrc.nist.gov/groups/ST/toolkit/rng/documents/sts-2.1.1.zip

文档在这里：http ://csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf

于 2014-01-26T22:49:23.673 回答