Re: UBSAN error in lib/sh/random.c:79

[Greg Wooledge]

On Sat, Jan 07, 2023 at 01:37:30AM +0000, Sam James wrote:
> $ cat /tmp/guess_suffix
> guess_suffix() {
>         tmpdir="${TMPDIR}"/.ecompress$$.${RANDOM}
> }
> guess_suffix

> $ export UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1"
> $ bash -x /tmp/guess_suffix
> + guess_suffix
> random.c:79:21: runtime error: signed integer overflow: 31789 * 127773 cannot 
> be represented in type 'int'
>     #0 0x559791a301ce in intrand32 
> /usr/src/debug/app-shells/bash-5.2_p15/bash-5.2/lib/sh/random.c:79

Well, the code in question looks like this (with comments removed):

static u_bits32_t
intrand32 (last)
     u_bits32_t last;
{
  bits32_t h, l, t;
  u_bits32_t ret;

  ret = (last == 0) ? 123459876 : last;
  h = ret / 127773;
  l = ret - (127773 * h);
  t = 16807 * l - 2836 * h;
  ret = (t < 0) ? t + 0x7fffffff : t;

  return (ret);
}

The line your error refers to is "l = ..." where the multiplication
occurs.  Also of note,

unicorn:/var/tmp/bash/bash-5.2$ grep bits32_t *.h
config.h:#define bits32_t int
config.h:#define u_bits32_t unsigned int
externs.h:extern u_bits32_t get_urandom32 PARAMS((void));

Variables "h" and "l" are both of type int (with a fancy name) on my
platform, and it seems on yours as well, based on your error message.

It would not surprise me if this is a long-standing bug in this RNG, but
I haven't analyzed the code well enough to understand why some of the
variables are defined with a signed type, and some with an unsigned
type.

Here are the comments which accompany the code:

  /* Minimal Standard generator from
     "Random number generators: good ones are hard to find",
     Park and Miller, Communications of the ACM, vol. 31, no. 10,
     October 1988, p. 1195. Filtered through FreeBSD.

     x(n+1) = 16807 * x(n) mod (m).

     We split up the calculations to avoid overflow.

     h = last / q; l = x - h * q; t = a * l - h * r
     m = 2147483647, a = 16807, q = 127773, r = 2836

     There are lots of other combinations of constants to use; look at
     https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-gener
ators.html#Other-random-number-generators */