How to compute the dataset size required by dieharder tests?

Question

I am trying to use the dieharder random number test suite.

However, this suite requires massive amount of data (this paper claims 228GB for no rewinding for every test) for most of the tests. I'd like to understand how rewinding is implemented and to know how much data is required for each test. It seems related to the tsamples value but I cannot find an exact correlation.

For example, if I generate 400MiB of data using dd if=/dev/urandom of=random.dat bs=1M count=400, this produces the following (cropped) output:

$ dieharder -a -g 201 -f random.dat
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|                      random.dat|  6.38e+07  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.70238534|  PASSED  
# The file file_input_raw was rewound 1 times
      diehard_operm5|   0|   1000000|     100|0.74169241|  PASSED  
# The file file_input_raw was rewound 2 times
  diehard_rank_32x32|   0|     40000|     100|0.03164866|  PASSED  
# The file file_input_raw was rewound 2 times
    diehard_rank_6x8|   0|    100000|     100|0.18168084|  PASSED  
# The file file_input_raw was rewound 3 times
   diehard_bitstream|   0|   2097152|     100|0.59056568|  PASSED  
# The file file_input_raw was rewound 5 times
        diehard_opso|   0|   2097152|     100|0.19175240|  PASSED  
# The file file_input_raw was rewound 6 times
        diehard_oqso|   0|   2097152|     100|0.67542036|  PASSED  
# The file file_input_raw was rewound 7 times
         diehard_dna|   0|   2097152|     100|0.04906220|  PASSED  
# The file file_input_raw was rewound 7 times
diehard_count_1s_str|   0|    256000|     100|0.80349572|  PASSED  
# The file file_input_raw was rewound 8 times
diehard_count_1s_byt|   0|    256000|     100|0.43003125|  PASSED  
# The file file_input_raw was rewound 8 times
 diehard_parking_lot|   0|     12000|     100|0.07270933|  PASSED  
# The file file_input_raw was rewound 8 times
    diehard_2dsphere|   2|      8000|     100|0.92548415|  PASSED  

I assume that dieharder just loops over the file, keeping its pointer position when jumping to the next test and that The file file_input_raw was rewound N times is just the total count that the pointer reached the end of the file.

Answer 1

I'll be so bold as to say that no one knows for sure how much data you really need. There is no guidance on the homepage, the manpage and this thread from Duke is equally unspecific. Anecdotal evidence suggests that a 'few' GB will return a sane PASS/FAIL answer, but there will still be rewinds. For a 4 GB /dev/urandom test:-

...snip
# The file file_input_raw was rewound 43 times
      rgb_lagged_sum|  27|   1000000|     100|0.75608263|  PASSED  
# The file file_input_raw was rewound 46 times
      rgb_lagged_sum|  28|   1000000|     100|0.88574962|  PASSED  
# The file file_input_raw was rewound 49 times
      rgb_lagged_sum|  29|   1000000|     100|0.69532845|  PASSED  
# The file file_input_raw was rewound 52 times
      rgb_lagged_sum|  30|   1000000|     100|0.93874399|  PASSED  
# The file file_input_raw was rewound 55 times
      rgb_lagged_sum|  31|   1000000|     100|0.59282678|  PASSED  
# The file file_input_raw was rewound 58 times
      rgb_lagged_sum|  32|   1000000|     100|0.88988310|  PASSED  

58 times!

In your case (input file), a rewind is just that; start again from the beginning. Eight rewinds is good. I've seen 1849 rewinds. Honestly I can't understand the reasoning behind that, as all it does is retest what's been tested.

And that could be good or bad as is illustrated with the following walk over a random source. If you test and rewind the contents of box A you might expect a pass. Conversely if you test and rewind box B, monobit and runs tests are likely to fail due to the large 3:1 bias in the x axis. Repetitive rewinding clearly can't help the p values, so perhaps we need a larger sample size such as box C.

All we know for certain is that Dieharder uses a lot. Your paper and my research shows that a free run of Dieharder (with no rewinds) needs approximately 225 - 250 GB! Notice that $58 \times 4 \text{GB}= 232 \text{GB}$.

There are other tests though. A more common test in the TRNG scientific literature is NIST's Statistical Test Suite, (SP 800-22). It's sample requirements are much more predictable.

And now a warning. You have to resist manipulating any randomness tests in order to get a PASS. Tweaking test parameters or selectively choosing individual tests to produce your expected result is dangerous, as a random sample is random no matter how you test it. From the manpage:-

...where a file that is too small will "rewind" and render the test results where a rewind occurs suspect.

Answer 2

In order to get a precise, hopefully definitive answer we can count the number of rewinds for each test. I generated a 1KiB file that was used as an input.

After some source code investigation, dieharder treats input files as a stream that is consumed indefinitely so every new test resumes the stream at the same place where the previous test stopped. Interestingly, dieharder has is an -s strategy flag:

if strategy is the (default) 0, dieharder reseeds (or rewinds) once at the beginning when the random number generator is selected and then never again. If strategy is nonzero, the generator is reseeded or rewound at the beginning of EACH TEST. If [...] a file is used, this means every test is applied to the same sequence (which is useful for validation and testing of dieharder, but not a good way to test rngs).

So running dieharder -a -g 201 -s 1 -f kibibyte.dat (full output) produces the following data:

test_name	ntup	tsamples	psamples	rewinds for 1 KiB	remarks
diehard_birthdays	0	100	100	15000
diehard_operm5	0	1000000	100	390626
diehard_rank_32x32	0	40000	100	500000
diehard_rank_6x8	0	100000	100	234375
diehard_bitstream	0	2097152	100	102400
diehard_opso	0	2097152	100	819200
diehard_oqso	0	2097152	100	546134
diehard_dna	0	2097152	100	256004
diehard_count_1s_str	0	256000	100	25000
diehard_count_1s_byt	0	256000	100	500000
diehard_parking_lot	0	12000	100	9375
diehard_2dsphere	2	8000	100	6250
diehard_3dsphere	3	4000	100	4687
diehard_squeeze	0	100000	100	909090
diehard_sums	0	100	100	77
diehard_runs	0	100000	100	39062	test ran 2x
diehard_craps	0	200000	100	526315	test ran 2x
marsaglia_tsang_gcd	0	10000000	100	7812500	test ran 2x
sts_monobit	1	100000	100	39062
sts_runs	2	100000	100	39062
sts_serial	1-16	100000	100	39062
rgb_bitdist	1	100000	100	78125
rgb_bitdist	2	100000	100	156250
rgb_bitdist	3	100000	100	234375
rgb_bitdist	4	100000	100	312500
rgb_bitdist	5	100000	100	390625
rgb_bitdist	6	100000	100	468750
rgb_bitdist	7	100000	100	546875
rgb_bitdist	8	100000	100	625000
rgb_bitdist	9	100000	100	703125
rgb_bitdist	10	100000	100	781250
rgb_bitdist	11	100000	100	859375
rgb_bitdist	12	100000	100	937500
rgb_minimum_distance	2	10000	1000	78125
rgb_minimum_distance	3	10000	1000	117187
rgb_minimum_distance	4	10000	1000	156250
rgb_minimum_distance	5	10000	1000	195312
rgb_permutations	2	100000	100	78125
rgb_permutations	3	100000	100	117187
rgb_permutations	4	100000	100	156250
rgb_permutations	5	100000	100	195312
rgb_lagged_sum	0	1000000	100	390625
rgb_lagged_sum	1	1000000	100	781250
rgb_lagged_sum	2	1000000	100	1171875
rgb_lagged_sum	3	1000000	100	1562500
rgb_lagged_sum	4	1000000	100	1953125
rgb_lagged_sum	5	1000000	100	2343750
rgb_lagged_sum	6	1000000	100	2734375
rgb_lagged_sum	7	1000000	100	3125000
rgb_lagged_sum	8	1000000	100	3515625
rgb_lagged_sum	9	1000000	100	3906250
rgb_lagged_sum	10	1000000	100	4296875
rgb_lagged_sum	11	1000000	100	4687500
rgb_lagged_sum	12	1000000	100	5078125
rgb_lagged_sum	13	1000000	100	5468750
rgb_lagged_sum	14	1000000	100	5859375
rgb_lagged_sum	15	1000000	100	6250000
rgb_lagged_sum	16	1000000	100	6640625
rgb_lagged_sum	17	1000000	100	7031250
rgb_lagged_sum	18	1000000	100	7421875
rgb_lagged_sum	19	1000000	100	7812500
rgb_lagged_sum	20	1000000	100	8203125
rgb_lagged_sum	21	1000000	100	8593750
rgb_lagged_sum	22	1000000	100	8984375
rgb_lagged_sum	23	1000000	100	9375000
rgb_lagged_sum	24	1000000	100	9765625
rgb_lagged_sum	25	1000000	100	10156250
rgb_lagged_sum	26	1000000	100	10546875
rgb_lagged_sum	27	1000000	100	10937500
rgb_lagged_sum	28	1000000	100	11328125
rgb_lagged_sum	29	1000000	100	11718750
rgb_lagged_sum	30	1000000	100	12109375
rgb_lagged_sum	31	1000000	100	12500000
rgb_lagged_sum	32	1000000	100	12890625
rgb_kstest_test	0	10000	1000	39062
dab_bytedistrib	0	51200000	1	600000
dab_dct	256	50000	1	50000
dab_filltree	32	15000000	1	422619	test ran 2x
dab_filltree2	0-1	5000000	1	113636
dab_monobit2	12	65000000	1	253906

The test which requires the largest amount of data is rgb_lagged_sum which requires 13.2 GB when ntup=32. Ignoring other instances of rgb_lagged_sum, the second and third test with largest input are marsaglia_tsang_gcd which requires 8GB and then rgb_bitdist which requires 960MB.

An interesting take on this is that rewinds do not influence the outcome above 13.2GB (but some tests will reuse the same sequence).

Answer 3

The TestU01 suite for testing pseudorandom number generators incorporates tests from DieHarder (all of them, I think). On pages 5 and 6 of the journal article on the TestU01 suite (see link near bottom of same page), L'Ecuyer and Simard explain that it makes sense to test until the p-values are incredibly small, or continue to remain relatively large. In the former case, the PRNG fails the test; in the latter case, it doesn't. If the p-values are small but not very small, one can re-test several times with disjoint generated sequences "until either failure becomes obvious or suspicion disappears" (p. 5). The same informal principle applies to the subset of TestU01 contained in DieHarder. TestU01 also includes a set of modules intended for the purpose of finding "prediction formulas for the sample size $n_0$ for which the test starts to reject an RNG decisively, as a function of its period length $\rho$" (p. 25).

Of course your random source has to be capable producing that much data without repeating itself, as your question reflects, but DieHarder and TestU01 were designed for modern pseudorandom number generating algorithms with very large periods, i.e. no rewinding--if I understand the terminology in the question--for many steps.

As @fgrieu's comment indicates, passing DieHarder or TestU01 doesn't tell you anything about cryptographic security, but I'm assuming that you're using DieHarder to test whether RNG output satisfies other, non-cryptographic, criteria for RNG quality.

@PaulUszak's answer suggests the NIST SP800-22 suite for cryptographic security properties. Please see @fgrieu's comment below as well. Johnston's book Random Number Generators—Principles and Practices contains an extended survey of SP800-22.