I have a sequence of integers between 0 to 100. Is there any free software like Sage, where I can test randomness of this sequence? I have Linux machine.
I have huge data set. Actually I have my own generator. I want to test its randomness.
$\begingroup$
$\endgroup$
-
$\begingroup$ How many numbers do you have to test? It matters as to which tests can be used. Also, is the range actually 0-100 because that will cause problems? $\endgroup$ – Paul Uszak Nov 3 '16 at 21:56
-
$\begingroup$ I have huge data set. Actually I have my own generator. I want to test its randomness. $\endgroup$ – str Nov 4 '16 at 4:27
-
$\begingroup$ @str Note that the Q you duped also contains pointers to software in this answer (including links) $\endgroup$ – e-sushi Nov 4 '16 at 16:23
-
$\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Nov 4 '16 at 16:27
$\begingroup$
$\endgroup$
Tests of randomness with only data as input can give proof of non-randomness, but never a credible indication of randomness unless their result is coupled with an analysis of how the random data tested has been generated. Without such knowledge, such tests give a falsely reassuring PASS, or a FAIL.
Illustration: consider the PRNG that outputs 512-bit blocks computed as the HMAC-SHA-512 of the previous block under some key. That pass any randomness test for one not knowing the key, yet is trivially predictable from past output with that knowledge.
In cryptography, randomness tests with PASS result can only be useful when and if we have a model of the source tested. This is at the heart of the AIS31 methodology of Common Criteria evaluation for True Random Numbers Generators in things like Smart Cards; see there (under AIS31; the page exists in German only AFAIK, but has links to many documents in English and a Reference implementation of the statistical tests).
Per the AIS 31 methodology, it is made some model matching the device, and justified that per that model, any likely defect that do not raise alarm won't result in using a significantly predictable bitstream. Typically there is:
- a TRNG based on some analog phenomenon, e.g. sampling of a noise source, delivering a bitstream that can be sampled for testing purposes;
- hardware or/and software testing that source, at startup and/or runtime, in order to check that this source delivers entropy; including, at least, something that raise alarm if anything makes that source totally defective (that could be an attacker with a needle, a laser, evaporation of some liquefied gas..);
- a hardware or/and software conditioning of the output of that source, into another bitstream, that won't have discernible bias even if the source is only passable; that conditioned bitstream can be used e.g. as source of randomness for DPA countermeasures, or a key generator.
- possibly, an additional test that conditioning works as intended.
-
$\begingroup$ Do you have any examples of this AIS31 having being used in real life? The papers I've seen (especially for true random number generators) typically use DIEHARD or DIEHARDER. Some still just go with ENT. I should have asked if the generator is a physical one as those tend to have simpler tests. $\endgroup$ – Paul Uszak Nov 4 '16 at 11:54
-
-
$\begingroup$ @Paul Uszak: a problem is that e.g. diode noise sources can fail (perhaps, because there's a power supply glitch, accidental or intentional, or an adversary is pouring liquid gas on the Smart Card), and we want a test that can decide if the output is good enough for use, but does not fail when there's no attack. An option is to make a lenient test of the source (so that it will not fail unless there's something very wrong), and follow it with post conditioning. I know no other practical way for TRNGs working in adversarial conditions. $\endgroup$ – fgrieu♦ Nov 4 '16 at 15:57
$\begingroup$
$\endgroup$
I take it that this has a connection with cryptography, as some of the other SE forums might be able to help with programmatic implementation.
However. With a number range of 0-100, all you'll be able to do is a Chi Squared test to obtain a probability (0-1) that it could occur randomly. This is to check the frequency of occurrences of the 0 -100 values throughout your data set. They should all be even(ish). See Wikipedia for it's use. It's fairly simple. If you rerun the test a 100 times, getting all sorts of p values from 0.0000 - 1.0000, you can then use a Kolmogorov Smirnov (KS) test on those p values to get another p value(!). This does somewhat average out the anomalies from the first where you will get some failures like p=0.0001. I find that commons.math has an easy Java implementation of KS. It also does Chi tests, but I suggest in that case you perform G tests as they're preferred these days.
As you have access to the generator, you might be able to convert it's to output a 0-255 range. That then means you can use some standard tests. I recommend:-
RNGTEST for files in 20Kbit blocks
DIEHARD for files = 10MB
ENT for files 500KB - 2GB
DIEHARDER for files > 10GB(ish)
All these packages can take a feed from standard output so it's easy to connect them to your generator if you have source code access. They are easily downloadable as complied packages for Linux.I wouldn't bother with any other tests such as TESTU01 as they're unreliable in the extreme. And I also suggest that you don't try to write you own versions of theoretical tests unless your can also test that your test code works properly. And what would you test it with?
(How do you manage to get a native 0-100 output from a numeric generator???)
-
1$\begingroup$ Serious question: what is the basis for saying that TestU01 is extremely unreliable? Not doubting you, it's just that this is the first time I'm hearing such harsh criticism of it. Let's be clear that all test packages have "blind spots" - wondering what makes TestU01 so much worse? $\endgroup$ – Dan Nov 4 '16 at 15:41
-
$\begingroup$ @Dan I miss-typed. I meant that the use of TestU01 is unreliable. It's mathematical basis is probably sound, but it's very difficult to get running. The compact guide that comes with it is 219 pages long. You have to compile the package yourself after setting up compilation /path parameters to your satisfaction. I've seen people adapt the tests to their specific cases which to my mind casts doubt on whether it then actually works properly. It's a similar situation to what I said about writing your own test. And it won't really tell you anything more than DIEHARD /ER. $\endgroup$ – Paul Uszak Nov 5 '16 at 0:09
-
$\begingroup$ thanks for the thoughtful and detailed reply. I work primarily in embedded systems, so TestU01's run time (even the smallest suite) just completely rules it out. Somewhere, a while ago, I'd read someone praising TestU01 vis a vis Diehard, so I appreciate the input on TestU01. $\endgroup$ – Dan Dec 4 '16 at 3:29
