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

[Greg Wooledge]

On Fri, Jan 06, 2023 at 09:00:30PM -0500, Greg Wooledge wrote:
> On Sat, Jan 07, 2023 at 01:37:30AM +0000, Sam James wrote:
> > 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);
> }

>   /* 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.

I've now read the first half of the paper (it's easily readable up until
the section entitled "THEORY").  Bash's C implementation is derived from
this code presented in the paper:


function Random : real;
const
  a = 16807;
  m = 2147483647;
  q = 127773;     (* m div a *)
  r = 2836;       (* m mod a *)
var
  lo, hi, test : integer;
begin
  hi := seed div q;
  lo := seed mod q;
  test := a * lo - r * hi;
  if test > 0 then
    seed := test
  else
    seed := test + m;
  Random := seed / m
end;


with the additional global variable "seed" of type integer.  The paper
promises that no value will ever overflow a 32-bit variable, and
specifically mentions that the "test" variable can safely be a 32-bit
signed value.

However, it's pretty clear that "hi" and "lo" are not signed values.
Even when rewriting the mod calculation as a multiplication and a
subtraction, "lo" (aka "l") should never be negative.

I think this patch might be correct:


--- lib/sh/random.c.orig        2023-01-07 12:26:09.049950519 -0500
+++ lib/sh/random.c     2023-01-07 12:26:27.469974730 -0500
@@ -70,8 +70,8 @@
      There are lots of other combinations of constants to use; look at
      
https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html#Other-random-number-generators
 */
 
-  bits32_t h, l, t;
-  u_bits32_t ret;
+  bits32_t t;
+  u_bits32_t h, l, ret;
 
   /* Can't seed with 0. */
   ret = (last == 0) ? 123459876 : last;


I tested it briefly, and it builds cleanly and produces the same random
results as the unpatched version, at least on my system (compiled with
gcc 10.2.1).