How to test a random number generator (2010)(johndcook.com)
johndcook.com
How to test a random number generator (2010)
https://www.johndcook.com/blog/2010/12/06/how-to-test-a-random-number-generator-2/
43 comments
Addendum: For what it's worth, it seems some people aren't fond of Diehard any more. To quote Chris Doty-Humphrey, the author of PractRand:
> In empirical testing, a classic is the Diehard program by Marsaglia. That program is badly outdated today and should not be used anymore, but it was, so far as I know, the first real standardized battery of such tests.
More information is available on their website: http://pracrand.sourceforge.net/PractRand.txt.
> In empirical testing, a classic is the Diehard program by Marsaglia. That program is badly outdated today and should not be used anymore, but it was, so far as I know, the first real standardized battery of such tests.
More information is available on their website: http://pracrand.sourceforge.net/PractRand.txt.
From what I gather, decent PRNG tests today are
- L'Ecuyer's TestU01 (with SmallCrush, Crush, BigCrush), and
- Doty-Humphrey's pracrand with its PractRand suite
- L'Ecuyer's TestU01 (with SmallCrush, Crush, BigCrush), and
- Doty-Humphrey's pracrand with its PractRand suite
PCG seems to be designed by intuition and experimentation, with practically no theory in its support. I'm not saying it's bad, and I certainly see some potential merit in the idea that a PRNG passing tests with fewer bits is likely more effective than one that needs more state.
The problem is that these test suites are not very comprehensive and while they're OK for discerning an obviously broken RNG, they're not good to vouch for an RNG in general. That is to say, it is fairly easy to write an RNG that passes these test suites despite having some very predictable and easily detectable patterns that you'd find if only you wrote a test that looks for that particular pattern. Kinda like these suites have hyperplane tests to detect LCGs.
There's an old saying about anyone being smart enough to invent crypto they are not smart enough to break themselves. As far as designing RNGs goes, doing one against existing test suites is pretty low bar. I think we can afford a little more theory backing non-cryptographic PRNGs too.
I wouldn't give these test suites so much credit; they're tools for detecting known flaws or broken implementations. That's all.
The problem is that these test suites are not very comprehensive and while they're OK for discerning an obviously broken RNG, they're not good to vouch for an RNG in general. That is to say, it is fairly easy to write an RNG that passes these test suites despite having some very predictable and easily detectable patterns that you'd find if only you wrote a test that looks for that particular pattern. Kinda like these suites have hyperplane tests to detect LCGs.
There's an old saying about anyone being smart enough to invent crypto they are not smart enough to break themselves. As far as designing RNGs goes, doing one against existing test suites is pretty low bar. I think we can afford a little more theory backing non-cryptographic PRNGs too.
I wouldn't give these test suites so much credit; they're tools for detecting known flaws or broken implementations. That's all.
While the PCG paper does not contain such an impressive number of mathematical formula's that makes me instantly want to skip pages, I would not say it has 'practically no theory in its support'.
For the theory around periods, distribution and jumping it can just refer to these properties for LCG's, which are very well studied.
Testing an RNG design against the statistical test suites TestU01 and PractRand seems on first intuition the be the wrong way to go about it. First you should have a theory behind the RNG, and only then test it.
And to me it seems PCG does just that. The various output functions are carefully designed. Which bits are the best and which are the weakest for an LCG? The worst bits are dismissed. How can the best bits be used to pick permutations of the remaining bits? The output functions are well designed, but you will have to watch the video or look at the C++ source to see the theory behind them.
Then just about all known tests and theory to differentiate between true randomness and the results of an RNG are applied. Which are handily packed into test suites. That is the way to look at these tests. Not some sort of specific, arbitrarily chosen test. This is not the situation of Javascript engines that may get optimized to much for some arbitrary benchmark.
And those test where run against severely weakened versions of PCG, just to be sure the tests don't accidentally pass.
But you have a good point: designing solely against test suites is not a good idea. A result are Xorshift128+ and Xoroshiro128+. Even with some theory behind it, they are the result of varying constants until they do not fail any test on BigCrush too consistently. It may even sometimes pass, and that is what is claimed on for example Wikipedia. But along comes another test suite, PractRand, and it fails within a second of testing. It is optimized for BigCrush, but not really statistically good.
For the theory around periods, distribution and jumping it can just refer to these properties for LCG's, which are very well studied.
Testing an RNG design against the statistical test suites TestU01 and PractRand seems on first intuition the be the wrong way to go about it. First you should have a theory behind the RNG, and only then test it.
And to me it seems PCG does just that. The various output functions are carefully designed. Which bits are the best and which are the weakest for an LCG? The worst bits are dismissed. How can the best bits be used to pick permutations of the remaining bits? The output functions are well designed, but you will have to watch the video or look at the C++ source to see the theory behind them.
Then just about all known tests and theory to differentiate between true randomness and the results of an RNG are applied. Which are handily packed into test suites. That is the way to look at these tests. Not some sort of specific, arbitrarily chosen test. This is not the situation of Javascript engines that may get optimized to much for some arbitrary benchmark.
And those test where run against severely weakened versions of PCG, just to be sure the tests don't accidentally pass.
But you have a good point: designing solely against test suites is not a good idea. A result are Xorshift128+ and Xoroshiro128+. Even with some theory behind it, they are the result of varying constants until they do not fail any test on BigCrush too consistently. It may even sometimes pass, and that is what is claimed on for example Wikipedia. But along comes another test suite, PractRand, and it fails within a second of testing. It is optimized for BigCrush, but not really statistically good.
What would you recommend that isn't far worse, though? At least the PCG family tries; throwing that away can't give you better results. There's a good reason the PCG generators have remained robust against new tests, and why the well regarded competitors like the Mersenne Twister and Xoroshiro128+ have not.
Unless the competition is actually using rigorous mathematics to talk about their statistical quality, and as far as I can find they are simply not[1], being empirically better is the only thing to argue about! Thus if O'Neil's approach finds weaknesses in the competitor's tested generators earlier[2], it's a stronger test.
Even from the angle of unknown, theoretical attacks, competitors almost always build on trivially invertible functions, so you cannot expect them to be robust against generalized tests. The inverse transformation is always weak, so if this is trivial they cannot be robust against general classes of correlations.
Unless you can actually show a (useful) non-cryptographic RNG that makes good justifications for its strength in formal terms, which I doubt you can, you're basically left with the fact that the PCG family is the only robustly vetted family in practice.
If that isn't good enough for you, there's always ISAAC.
[1] https://cs.stackexchange.com/questions/50059/why-is-the-mers...
[2] http://www.pcg-random.org/posts/visualizing-the-heart-of-som...
Unless the competition is actually using rigorous mathematics to talk about their statistical quality, and as far as I can find they are simply not[1], being empirically better is the only thing to argue about! Thus if O'Neil's approach finds weaknesses in the competitor's tested generators earlier[2], it's a stronger test.
Even from the angle of unknown, theoretical attacks, competitors almost always build on trivially invertible functions, so you cannot expect them to be robust against generalized tests. The inverse transformation is always weak, so if this is trivial they cannot be robust against general classes of correlations.
Unless you can actually show a (useful) non-cryptographic RNG that makes good justifications for its strength in formal terms, which I doubt you can, you're basically left with the fact that the PCG family is the only robustly vetted family in practice.
If that isn't good enough for you, there's always ISAAC.
[1] https://cs.stackexchange.com/questions/50059/why-is-the-mers...
[2] http://www.pcg-random.org/posts/visualizing-the-heart-of-som...
I think you’re better of reading the relevant chapter in TAOCP. It has more detail, and this doesn’t add anything from past 1970 or so. For example, it doesn’t even _mention_ the diehard and dieharder tests, let alone discuss their merits. (CORRECTION: it does. Thanks to marvy for pointing that out)
Also, I think the final line in this text (”Correct generators usually pass tests, and buggy generators usually fail.”) is at least dangerously misleading.
Firstly, I would use good/bad, not correct/buggy, but that is minor. My major issue is the idea that bad generators usually fail. Only really bad generators usually fail. Somewhat bad generators fail tests less often, and only slightly bad generators can pass many, many tests, only to show their weakness in some particular setting.
For example, if I take the output r1,r2,r3… of a good generator and swap r1 and r2 if r1>r2, r3 and r4 if r3>r4, etc. the result isn’t truly random, but will pass many tests.
If you suspect your generator to have this problem, it is extremely easy to test for it, but if you don’t, that may be hard.
A good array of tests will test subsequences, and find this easily (the average of the odd samples will typically be less than expected, and the average of the even samples will typically be larger)
Also, I think the final line in this text (”Correct generators usually pass tests, and buggy generators usually fail.”) is at least dangerously misleading.
Firstly, I would use good/bad, not correct/buggy, but that is minor. My major issue is the idea that bad generators usually fail. Only really bad generators usually fail. Somewhat bad generators fail tests less often, and only slightly bad generators can pass many, many tests, only to show their weakness in some particular setting.
For example, if I take the output r1,r2,r3… of a good generator and swap r1 and r2 if r1>r2, r3 and r4 if r3>r4, etc. the result isn’t truly random, but will pass many tests.
If you suspect your generator to have this problem, it is extremely easy to test for it, but if you don’t, that may be hard.
A good array of tests will test subsequences, and find this easily (the average of the odd samples will typically be less than expected, and the average of the even samples will typically be larger)
Your example will fail the "Overlapping permutations" test and "Runs test" from the diehard tests.
I don't think it's really meaningful to point out that a bad RNG will pass many of the constituent tests of a particular test battery (e.g. diehard), because each constituent test is generally looking for one particular property.
I don't think it's really meaningful to point out that a bad RNG will pass many of the constituent tests of a particular test battery (e.g. diehard), because each constituent test is generally looking for one particular property.
> For example, it doesn’t even _mention_ the diehard and dieharder tests, let alone discuss their merits
It mentions the DIEHARD test near the beginning. Try ctrl-F.
It mentions the DIEHARD test near the beginning. Try ctrl-F.
This was disappointing. Not a word about correlations between subsequent numbers, period length, all the things that matter if you’re actually generating significant amounts of random numbers.
The chapter is not about writing and then testing new PRNGs. A uniform PRNG of sufficient quality for one's purpose is assumed. The key bit:
"Most testers will be concerned with the second step of the grand strategy: testing code that transforms uniform random sequences into sequences with other distributions. Although very few people develop their own uniform generators, many people have reasons to develop custom nonuniform generators."
"Most testers will be concerned with the second step of the grand strategy: testing code that transforms uniform random sequences into sequences with other distributions. Although very few people develop their own uniform generators, many people have reasons to develop custom nonuniform generators."
Since the discussion seems to have already degenerated into waxing poetic about this RNG or that I'd like to throw in: Do not use pseudo-random number generators. Use cryptographically secure random number generators.
From a performance perspective there are vanishingly few applications where the difference between MT or PCG and AES-CTR is going to make an ounce of difference. Once the question of performance is settled, there simply don't remain any arguments in favor of using PRNGs.
From a performance perspective there are vanishingly few applications where the difference between MT or PCG and AES-CTR is going to make an ounce of difference. Once the question of performance is settled, there simply don't remain any arguments in favor of using PRNGs.
Monte Carlo integration, one of the most important application of PRNG, needs the speed of non-CSPRNG.
However, I do agree that programming languages these day should probably make a CSPRNG the default, and let you switch to a fast PRNG when needed. (Now it's by and large the other way around – you get a fast PRNG and need to switch to a secure one.)
If you know what you're doing, the outcome is the same, but if you don't, in the first case you're unnecessarily slow, while in the second you're unnecessarily insecure.
However, I do agree that programming languages these day should probably make a CSPRNG the default, and let you switch to a fast PRNG when needed. (Now it's by and large the other way around – you get a fast PRNG and need to switch to a secure one.)
If you know what you're doing, the outcome is the same, but if you don't, in the first case you're unnecessarily slow, while in the second you're unnecessarily insecure.
https://github.com/mohae/bench-rng
csprng: 909 ns/Op
Xorhift128+: 2 ns/Op
Xorhift128+ is what all major JS engines use for Math.random().
I don't think it's a good idea if you use a CSPRNG if there isn't any reason for that. Especially if you need a lot of random numbers. E.g. a game might drop some additional frames here and there and your particle effects won't look any better and your AI won't behave any smarter either.
Not to use PRNGs ever is bad advice.
csprng: 909 ns/Op
Xorhift128+: 2 ns/Op
Xorhift128+ is what all major JS engines use for Math.random().
I don't think it's a good idea if you use a CSPRNG if there isn't any reason for that. Especially if you need a lot of random numbers. E.g. a game might drop some additional frames here and there and your particle effects won't look any better and your AI won't behave any smarter either.
Not to use PRNGs ever is bad advice.
> csprng: 909 ns/Op
OK, go ships a lousy csprng. I've been asking the team to replace it but no one has gotten around to it. AES-CTR, for example, is competitive with Xorshift and Xoroshiro.
> Xorshift128+ is what all major JS engines use for Math.random().
Only because two years ago Yang Guo noticed that MWC1616 was garbage. Up until that point engines were shipping a broken generator because someone had been clever. This failure mode happens again and again. java.util.Random, for example.
> I don't think it's a good idea if you use a CSPRNG if there isn't any reason for that
Using insecure random sources opens you up to all sorts of attacks that CSPRNGs insulate you to.
> Especially if you need a lot of random numbers
Over the past year I profiled a huge number of binaries. I found exactly one where fetching random numbers was over 1% of CPU consumption.
> your particle effects won't look any better
Your particle effects are probably running in a shader. That's a whole other ball game.
OK, go ships a lousy csprng. I've been asking the team to replace it but no one has gotten around to it. AES-CTR, for example, is competitive with Xorshift and Xoroshiro.
> Xorshift128+ is what all major JS engines use for Math.random().
Only because two years ago Yang Guo noticed that MWC1616 was garbage. Up until that point engines were shipping a broken generator because someone had been clever. This failure mode happens again and again. java.util.Random, for example.
> I don't think it's a good idea if you use a CSPRNG if there isn't any reason for that
Using insecure random sources opens you up to all sorts of attacks that CSPRNGs insulate you to.
> Especially if you need a lot of random numbers
Over the past year I profiled a huge number of binaries. I found exactly one where fetching random numbers was over 1% of CPU consumption.
> your particle effects won't look any better
Your particle effects are probably running in a shader. That's a whole other ball game.
Three comments:
> I found exactly one where fetching random numbers was over 1% of CPU consumption.
Again, Monte Carlo simulation is the obvious exception, and it is a huge, important field and big consumer of random numbers. Stochastic algorithms (see Sebastian Thrun's Probabilistic Robotics) might be another example.
However, one big problem is that many benchmarks basically benchmark the PRN generation, and so incentivise vendors to default to fast PRNG. And I agree with you, the default should be a CSPRNG.
Lastly, on a side note, I seem to recall that some generators from Vigna's Xoroshiro family suffer a very low quality least significant bit. Not sure whether Xorshift128+ is among them.
EDIT to add more:
BTW, it's surprisingly hard to get researchers in PRNG to give clear, unequivocal recommendations for users. They'll often resort to some version of "it depends" (or plug their own).
Lastly, let me plug my related stackoverflow answer:
https://stackoverflow.com/questions/4720822/best-pseudo-rand...
> I found exactly one where fetching random numbers was over 1% of CPU consumption.
Again, Monte Carlo simulation is the obvious exception, and it is a huge, important field and big consumer of random numbers. Stochastic algorithms (see Sebastian Thrun's Probabilistic Robotics) might be another example.
However, one big problem is that many benchmarks basically benchmark the PRN generation, and so incentivise vendors to default to fast PRNG. And I agree with you, the default should be a CSPRNG.
Lastly, on a side note, I seem to recall that some generators from Vigna's Xoroshiro family suffer a very low quality least significant bit. Not sure whether Xorshift128+ is among them.
EDIT to add more:
BTW, it's surprisingly hard to get researchers in PRNG to give clear, unequivocal recommendations for users. They'll often resort to some version of "it depends" (or plug their own).
Lastly, let me plug my related stackoverflow answer:
https://stackoverflow.com/questions/4720822/best-pseudo-rand...
> Monte Carlo simulation is the obvious exception
It depends. :) Even then very few realistic simulations are going to be RNG bound. Even fewer of those are going to care about the difference between Xoroshiro and AES-CTR (with AESNI).
A common failure mode I've seen is programmers picking Mersenne Twister and then assuming initialization is cheap.
> suffer a very low quality least significant bit
IIRC, the LSB behaves like a LFSR.
> it's surprisingly hard to get researchers in PRNG to give clear, unequivocal recommendations for users
There are about five PRNG researchers in the world and few (none?) of them are doing it full time. L'Ecuyer, the biggest name since Marsaglia died, seems to be dealing with PRNGs mostly as a means to doing operations research.
(Side note: Pierre L'Ecuyer is very likely the strongest over-50 cyclist in Quebec.)
It depends. :) Even then very few realistic simulations are going to be RNG bound. Even fewer of those are going to care about the difference between Xoroshiro and AES-CTR (with AESNI).
A common failure mode I've seen is programmers picking Mersenne Twister and then assuming initialization is cheap.
> suffer a very low quality least significant bit
IIRC, the LSB behaves like a LFSR.
> it's surprisingly hard to get researchers in PRNG to give clear, unequivocal recommendations for users
There are about five PRNG researchers in the world and few (none?) of them are doing it full time. L'Ecuyer, the biggest name since Marsaglia died, seems to be dealing with PRNGs mostly as a means to doing operations research.
(Side note: Pierre L'Ecuyer is very likely the strongest over-50 cyclist in Quebec.)
You should be talking ~50ns for a good CSPRNG, which is almost never going to be the overhead.
Any good CUDA implementations and benchmarks for CSPRNG's?
2/10 would not recommend for technical merit.
8/10 is nice if you want a handwavy human explanation of some rudimentary expectations in crypto
- author spends a few pages thinking about randomness - we have formal definitions of a RNG/PRNG.
- author does basic statistical tests, these seem very unconcerned with actual randomness - i'm not sure what the point is
- author really shouldn't be writing about crypto randomness if they don't do crypto
+1 to higher comment saying reading TAOCP instead.
8/10 is nice if you want a handwavy human explanation of some rudimentary expectations in crypto
- author spends a few pages thinking about randomness - we have formal definitions of a RNG/PRNG.
- author does basic statistical tests, these seem very unconcerned with actual randomness - i'm not sure what the point is
- author really shouldn't be writing about crypto randomness if they don't do crypto
+1 to higher comment saying reading TAOCP instead.
The author specifically mentions he doesn't write about cryptography.
> The idea of what constitutes a good RNG depends on how the RNG is applied. That is why, for example, a generator may be considered high-quality for simulation while being considered unacceptable for cryptography. This chapter looks at tests of statistical quality and does not address tests for cryptographical security.
> The idea of what constitutes a good RNG depends on how the RNG is applied. That is why, for example, a generator may be considered high-quality for simulation while being considered unacceptable for cryptography. This chapter looks at tests of statistical quality and does not address tests for cryptographical security.
He’s writing with the assumption you have a sufficiently good uniform PRNG. Then explains how to test whether the code you wrote to achieve a particular distribution does what you think it does.
"i'm not sure what the point is" - people use random numbers for things besides crypto.
This is a great read. The principles are also applicable to other problems such as evaluating a constant time comparison function, symmetrical cypher, or hash.
So is this a good PRNG?
f(i) = SHA256(i + salt)Discussion: https://crypto.stackexchange.com/questions/9076/using-a-hash...
& http://xoroshiro.di.unimi.it makes reference to how on x86 cpus with AES one could get a very fast prng similar to how you're implying
As a change of 1 bit in an input ideally flips half the bits of the output for a cryptographic hash, this scheme should work
See also https://en.wikipedia.org/wiki/Fortuna_(PRNG)
& http://xoroshiro.di.unimi.it makes reference to how on x86 cpus with AES one could get a very fast prng similar to how you're implying
As a change of 1 bit in an input ideally flips half the bits of the output for a cryptographic hash, this scheme should work
See also https://en.wikipedia.org/wiki/Fortuna_(PRNG)
I don't know much about this stuff, but I think that this would be considered overkill (and thus too slow) if you don't need crypto-level randomness. But other than that it should be really good.
Random, sure. Uniformly distributed? Not sure.
My understanding is that to the extent it's not uniformly distributed, that's viewed as a cryptographic vulnerability.
A PRNG usually doesn’t have parameters once seeded. What’s i in your scheme?
If you’re asking if you can make a good PRNG out of cryptographic primitives, yes, that’s what happens in the bowels of OS CSPRNGs. But a bit more involved.
If you’re asking if you can make a good PRNG out of cryptographic primitives, yes, that’s what happens in the bowels of OS CSPRNGs. But a bit more involved.
No. A feature of a good PRNG is that it should not be predictable. If the salt is weak enough to be cracked, that PRNG can be reversed and predicted.
The salt is the seed. Presumably initialized with /dev/random or whichever system entropy source is available. Any PRNG is weak if the seed is weak
Marsaglia's DieHard, DieHarder, and NIST 800-22 A are historically important, but outdated.
See my related stack overflow answer:
https://stackoverflow.com/questions/4720822/best-pseudo-rand...
See my related stack overflow answer:
https://stackoverflow.com/questions/4720822/best-pseudo-rand...
They suck. At least use TestU01 if you're going to work with an existing test suite. It's still very easy to write a (bad) prng that passes all the testu01 batteries.
Software random number generators are technically
pseudorandom number generators because the output
of a deterministic program cannot really be random.
That's an argument that's persuasive in very specialized regions of spacetime with particular chemistries. Like dorm rooms equipped with bongs.
Also, high in the Earth's atmosphere, where the air doesn't do such a good job of protecting RAM from cosmic ray impacts.
Right, but that's only slightly less silly than claiming programs are non-deterministic because of the quantum handwave equation. Similarly, programs behave non-deterministically because you might drop your phone or spill bongwater on your laptop.
[deleted]
Programs are abstract objects like numbers. The computers executing them are indeed not deterministic (e.g. random bit flips occur occasionally), but pretty smart people do their best to make them appear so, so it's unlikely that you see behavior that is not explainable by a deterministic model.
It seems to me that any new non-cryptographic PRNG should be required to test itself in this manner, or else provide a very good excuse.
[1] http://www.pcg-random.org/paper.html