Re: doc: Mention rand and srand limitations

[Jeffrey Walton]

Hi Bruno,

On Fri, Nov 10, 2023 at 2:03 PM Bruno Haible <bruno@clisp.org> wrote:>
> rand() is not required to be multithread-safe. So, it's not a bug when rand()
> is not MT-safe on some platforms; it's merely a portability problem worth
> documenting.
>
> The attached program tests the MT-safety. Results: OK on all platforms, except
>
> FreeBSD 13.2  Expected value #7504 not found in multithreaded results. (4 
> failures among 100 runs)
> macOS 12.5    Expected value #31 not found in multithreaded results.
> Solaris 10    Expected value #95981 not found in multithreaded results.
> Solaris 11.4  Expected value #55372 not found in multithreaded results.
> OpenBSD 7.4   rand() is non-deterministic.
> Cygwin 3.4.6  rand() is non-deterministic.
>
> The latter statement regarding Cygwin is not correct. Looking into the Cygwin
> source code, it's clear that the problem is that srand() has no effect on
> other thread - which is a bug since it violates ISO C 23.
>
> On Haiku, rand() is MT-safe while random() is not.
>
>
> 2023-11-10  Bruno Haible  <bruno@clisp.org>
>
>         doc: Mention rand and srand limitations.
>         * doc/posix-functions/rand.texi: Mention multithread-safety problem.
>         * doc/posix-functions/srand.texi: Mention a Cygwin bug.
>
> diff --git a/doc/posix-functions/rand.texi b/doc/posix-functions/rand.texi
> index 2f36a548a7..48b0bc5758 100644
> --- a/doc/posix-functions/rand.texi
> +++ b/doc/posix-functions/rand.texi
> @@ -18,4 +18,7 @@
>  @item
>  This function is only defined as an inline function on some platforms:
>  Android 4.4.
> +@item
> +This function is not multithread-safe on some platforms:
> +macOS 12.5, FreeBSD 13.2, Solaris 11.4.
>  @end itemize
> diff --git a/doc/posix-functions/srand.texi b/doc/posix-functions/srand.texi
> index 3e8f4b429b..710a5a1270 100644
> --- a/doc/posix-functions/srand.texi
> +++ b/doc/posix-functions/srand.texi
> @@ -15,4 +15,8 @@
>  @item
>  This function is only defined as an inline function on some platforms:
>  Android 4.4.
> +@item
> +This function has no effect on @code{rand} invocations in other threads
> +on some platforms:
> +Cygwin 3.4.6.
>  @end itemize

If rand() and friends do not need to be MT-safe, then does it even need a test?

I think the two tests of interest are:

(1) srand() produces a repeatable stream
(2) rand() and friends produce a stream that is uniformly distributed

For (2), compressibility is a poor man's randomness test. 32 bytes
should not be compressible by an algorithm like zlib or zip. Set up a
loop to generate 255 or 1024 sets of 32-bytes, compress each set of
32-bytes, and ensure most of them are not compressible.

You could also use Maurer's Universal Statistical Test for Random Bit
Generators from Journal of Cryptology, 1992. Maurer's test is a test
for physical generators. But a quality pseudo random number generator
will follow a uniform distribution, and it should be indistinguishable
from a physical generator. I know they are indistinguishable for a
cryptographically secure pseudo random number generator.

While rand() is insecure (likely a LCG), it is supposed to produce a
stream that is uniformly distributed. It does not matter that you can
reverse the stream/recover the coefficents and predict the next
generator output. What matters is the uniform distribution, and
non-compressibility of the stream.

Jeff