False positive in sstring_PeriodsInStrings test (also fails with BoringSSL's RNG)

[jlebar]

My implementation of the Squares PRNG was failing one of the sstring_PeriodsInStrings tests in the Crush suite. I was kind of surprised by this, so I reran this test against BoringSSL's secure rng. It still fails:

sstring_PeriodsInStrings test:
-----------------------------------------------
   N =  1,  n = 300000000,  r =  0,   s =   30

-----------------------------------------------
Number of degrees of freedom          :  302
Chi-square statistic                  : 8.20e+8
p-value of test                       :   eps      *****

Unfortunately I do not have an easy reproducer for you, but the RNG is simply

#include "boringssl/rand.h"
...
uint64 r;
(void)RAND_bytes(reinterpret_cast<unsigned char*>(&r), sizeof(r));
return r;

[pierrelecuyer]

Justin:

In TestU01-2009, the function getBits of an RNG must return a block of 32 bits. This is what Unif01_StripB expects. Please check the documentation.   This is probably the source of your problem. See below.

It will be changed to 64 bits in the forthcoming TestU01-64.

-- Pierre L.

==============================================================

Le problème provient du générateur; il n’est pas censé

Retourner des entiers avec plus de 32 bits.

Tout a été programmé il y a longtemps en supposant que les long avaient 32 bits.

Et tous les générateurs retournent max 32 bits

J’ai remplacé par

|unsigned long rng() {|

|  return 0xbf2d4b4db3d8dfb1 » 32;|

|}|

Ceci dit, il faudra corriger éventuellement la fonction

Unif01_StripB

Elle contient explicitement le nombre de bits 32;

===============================================================

On 11/9/2020 8:32 PM, Justin Lebar wrote:

My implementation of the Squares PRNG was failing one of the sstring_PeriodsInStrings tests in the Crush suite. I was kind of surprised by this, so I reran this test against BoringSSL's secure rng. It still fails:

|sstring_PeriodsInStrings test: ----------------------------------------------- N = 1, n = 300000000, r = 0, s = 30 ----------------------------------------------- Number of degrees of freedom : 302 Chi-square statistic : 8.20e+8 p-value of test : eps ***** |

Unfortunately I do not have an easy reproducer for you, but the RNG is simply

|#include "boringssl/rand.h" ... uint64 r; (void)RAND_bytes(reinterpret_cast<unsigned char*>(&r), sizeof(r)); return r; |

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/umontreal-simul/TestU01-2009/issues/5, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACVHLI6NN7TAC2JW6EJT5ELSPCJZHANCNFSM4TQBWR3Q.

-- Pierre L'Ecuyer, Professeur Titulaire CIRRELT, GERAD, and DIRO, Université de Montréal, Canada http://www.iro.umontreal.ca/~lecuyer

[jlebar]

Indeed, this solves not just this one bug, but all of mine!

Thank you very much for your help, Prof L'Ecuyer.

In case you're interested, I'm finding new and exciting weaknesses in existing RNGs. Confirmed that the three-round version of Squares fails when the counter takes on the values 0, 1, 2**32, 2**32+1, 2**32 * i/2 + (i%2), which simulates how I use it on the GPU. The four-round version seems ok. The author has told me to expect an updated paper soon.

I'm now trying out PCG, which seems to have a similar problem. You can use a single seed to generate many streams of random numbers, and if I consider the sequence generated by [2 values from stream 0, 2 values from stream 1, ...], that also fails the tests.

Let the crushing continue!

Thank you again.