1

I've been looking at this problem for the last year, and can't understand why there's no standard way to test for randomness in the real world. It seems to be that it's just what make you comfortable.

(I'm ruling out random sequences that are really really not random, like 0123456789...repeating.)

Randomness testing issues lists some widely known tests, and a whole list of issues with them. I can add others. Diehard - how big should the input file be, and should it consist only of 32 bit integers? ENT - only seems suitable for gross errors. Compression /entropy estimate is totally wrong but the chi test is useful. The NIST user manual is >100 pages long - good luck. TestU01 - has compilation issues on certain platforms. And once you've shoehorned it into your computer, is it running correctly? How can you then trust the output? And how do you know if a test has failed? What level of p or KS is considered too extreme?

I would further add that you should consider the development of randomness test suites vis a vis real-politic. It's in an academic's self interest to develop tests that discredit random number generators. After all, you don't get no funding producing results that say "it's all okay, nothing found, no further research (read: money) required".

Consider what happens in the real world that we live in, not on an academic's bookshelf:-

Random.org - used an undergrad to undertake some homebrew tests for a thesis. And essentially count the number of 1's and 0's. ENT does similar. They stake their business model on this.

Hotbits - champion the simplistic ENT, and a hacked version of Dieharder that most people will have difficulty in getting to execute, never mind trying to comprehend myriad test initialisers.

Academic generator papers - much recourse to Knuth's writings and homespun techniques. Some use some of the above tools. Some then accept a number of test failures within those suites.

The only examples I've found so far in this man's universe that seems to carry any real weight (i.e. if it fails you go to prison type of weight) is the certification for:-

Playtech PLC, a UK supplier of gambling software. They supply some of the largest online betting companies where real money changes hands. Still, they use homebrew tests and the Diehard test.

ERNIE for the UK Premium Bonds. They use basic statistics tests for frequency and correlation. Effectively home brew and not using a published suite.

The two latter examples seem to suggest that the current Zeitgeist is being molded by financial bodies. Random numbers are a form of maths, a reasonably established discipline. Why isn't there a tried and tested program suite that everyone uses, and it's output says yea or ney?

Supplemental: Following responses and further research, I'm starting to think that perhaps these questions of validating randomness are somewhat scholastic. There is no standard test for random number generators; because there is no need for such. My 3 1/2 rules for an excellent random number generator:-

  1. The generator must pass some recognised test which may be like Diehard, or home brewed.

  2. The organisational body fronting /validating (see 1) the generator must have gravitas.

  3. The generation algorithm /methodology must sound convincing (see 2).

  4. For true random number generators, the entropy source has to be self evidently naturally random.

I have inferred these rules from observations of what really seems to happen in commercial, financial and legal environments.

Community
  • 1
  • 1
Paul Uszak
  • 377
  • 4
  • 18
  • 4
    You list a bunch of tests people generally use and consider acceptable, then you ask why there isn't some group of tests people generally use and consider acceptable. It almost sounds like you're asking why hasn't someone created a suite of tests that satisfies *you*. – dimo414 Aug 12 '15 at 02:40
  • This is the crux of my question. I'm asking "why hasn't someone created a suite of tests that satisfies everyone?" Mathematics isn't usually subjective. Using all the tests above tells me little. A generator passes DIEHARD but fails the NIST suite (if you can tell whether it has or not). So is the generator good or bad? And if DIEHARDER is so great, how is ERNIE conning the UK Parliament by not using it for Savings Bonds?Should I just rely on ENT as that's the simplest, and you said it was acceptable? – Paul Uszak Aug 12 '15 at 03:34
  • 1
    Sometimes physical processes are used for randomness. But even these can be manipulated. The emission of certain radioactive particles from a standardized source is known to be poisson at some particular rate. But this might be foiled by an EMP nuclear device detonated above it. Similarly, the noise on an unused radio channel is sometimes used as a source of random bits, but if the frequency is revealed by some bad actor named, say, Kenneth, the channel might not remain unused. – Paul Aug 12 '15 at 08:07
  • @Paul At the risk of repeating myself, but I clearly have to:"Also ignore the majority of comments regarding susceptibility to attack. Those scenarios are bandied about as in the writer's department of a Hollywood blockbuster. Those scenarios have near zero probability of enactment unless you're guarding the nation's strategic defence." If you're not having a larf, is resistance to an EMP burst above an inhabited city a design consideration for a generator? Perhaps other things would be on your mind in the subsequent days /weeks /years. And who's Kenneth? – Paul Uszak Sep 11 '15 at 12:15
  • @PaulUszak [Dan Rather and "What's the Frequency, Kenneth?"](https://en.wikipedia.org/wiki/Dan_Rather#.22Kenneth.2C_what_is_the_frequency.3F.22). Although not discussed at length by Wikipedia, the impression I had of this event was that the madman who attacked Rather wanted to know the frequency the media, or perhaps the government, was using for mind control or some similar conspiracy nuttiness. – Paul Sep 12 '15 at 03:00

3 Answers3

6

A standardised, conclusive, binary result PRNG test has not been developed because it is not possible.

First of all, whatever output you deem to be not acceptable, there is some non-zero possibility that a perfect random number generator could legitimately produce it. Right away you're faced with the risk of false failures, so the result of the test cannot be an absolute yes or no.

Second, any PRNG will have some kind of detectable signature if you know the algorithm and can collect enough information about its state. If a hypothetical test knew every possible PRNG algorithm and was able to test for long enough to determine its working state then it would definitively reject all PRNGs tested. By definition no PRNG is adequate according to this test.

Third, already mentioned. Once you nail down a "reasonable" subset of patterns somebody can immediately make a PRNG which passes everything deemed reasonable but is a catastrophic failure on the first characteristic excluded from your list.

In short, we know that all PRNGs should eventually fail a perfect test because they are deterministic machines and by their very definition not random. The test batteries that exist are merely tools comparable to spellcheckers, in that they can highlight common errors but they can't tell you whether or not you're doing it right.

sh1
  • 4,324
  • 17
  • 30
  • Your first and third points are spot-on, but your second point is wrong. Where you write "any PRNG will have some kind of detectable signature if you know the algorithm and can collect enough information about its state", this isn't accurate -- consider a cryptographic-strength PRNG, which by definition has no kind of detectable signature, and thus there's no test to definitively reject it. (If your get-out clause is the "test for long enough", consider that "long enough" might mean "longer than the lifetime of the solar system".) Perhaps delete the second point? – D.W. Sep 10 '15 at 20:41
  • @D.W. I hoped for the logic to stand even if you don't make an appeal to feasibility of implementation. CPRNGs merely push the problem out to infeasibility, rather than implementing a provable "solution" to pseudo-randomness; and that's a bit arbitrary. There are patterns a CPRNG may be incapable of producing (eg., an encrypted counter will repeat when the counter overflows and once a block is produced that block can only ever be seen again after the full period of the counter [practically: that block will never be seen again]), so they can't be considered perfect in any absolute sense. – sh1 Sep 21 '15 at 03:44
  • I think I already covered that with "lifetime of the solar system". Regarding "can't be considered perfect in any absolute sense" -- guess what? Nothing can. The probability of a cosmic ray causing a bit-flip error in your computer that causes a catastrophic problem is far, far higher than the chances you will be able to detect a pattern in a secure CSPRNG. I think the problem is that you have redefined "adequate" to mean "perfect", which is unreasonable, as nothing is perfect. – D.W. Sep 21 '15 at 04:48
  • Yeah, the efficacy of CPRNGs doesn't need to be explained. I'm answering the theoretical question. – sh1 Sep 27 '15 at 03:35
1

If there was a single standard test then there would probably be a certain amount of over-fitting. You could use genetic algorithms to tweak parameters to pass that specific test. It is more useful to have a large variety of fairly different tests, which in fact describes the current situation. Think of it like the immune system. A healthy immune system can resist a whole host of pathogens and not just a single standard pathogen.

John Coleman
  • 51,337
  • 7
  • 54
  • 119
  • The over fitting is a good point. Your biological analogy could be extended even further in that just as there is a battle between antibiotics and antibiotic resistance, there might develop an arms race between the generator creators and the generator testers. – Paul Uszak Aug 17 '15 at 00:49
  • @PaulUszak Extending the biological analogy a bit further -- there has been speciation in random number generators. PRNGs for use in games need speed but statistical profile can be relatively weak - hence the survival of linear congruential generators, ones for Monte Carlo simulations need good statistical profiles but it doesn't really matter if they hide their internal state. Those for cryptography need to make their internal state virtually impossible to recover despite repeated observation. Different niches rule out the idea of a single test. – John Coleman Aug 17 '15 at 01:16
1

Since you've appealed to math, we need to do some math. Let us assume that an algorithm were provably a cryptographically secure PRNG. We need to be a little more precise in our definition there (I'm still going to be sloppy, but hopefully the intuition will hold).

By CSPRNG, I mean a function R(t) = r which returns a single, totally unpredictable value at a given time. This function must be computable in polynomial time. Rather than say "polynomial time" over and over again, I'm going to call it "quickly."

Given that function, let's talk about its inverse: R-1(r) = t. Given some output value, R-1(r) returns some time value for which r would be the output.

So if I told you that R-1(1) = 5, you could verify that very quickly by plugging 5 into R and making sure it returned 1. Things that can be verified quickly are called "NP" and R-1 is a member.

But if I asked you, what is R-1(1), you could not solve that quickly. If you could solve that quickly, then we would violate the rule that R(t) is "totally unpredictable." Things you can solve in polynomial time are called "P". So R-1 is not a member.

Ah, so we have found a function that is provably in NP but is provably not in P. That means P≠NP. Yes! We have solved one of the greatest math questions in existence. We all have this intuition that there probably are functions that are like this, but no one has been able to prove it.

So, in order to build a mathematically provable PRNG, step one is to solve one of the Millennium Prize Problems. In the meantime, we just have elaborate unit testing. And as long as we rely on testing, rather than proofs, we can't get the kind of assurance you're looking for. We can just find bugs; we can't ensure correctness.

Rob Napier
  • 286,113
  • 34
  • 456
  • 610