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

[Greg Wooledge]

On Sat, Jan 07, 2023 at 07:08:06PM +0100, Andreas Schwab wrote:
> On Jan 07 2023, Greg Wooledge wrote:
> 
> > 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).
> 
> The assignment t = 16807 * l - 2836 * h can still overflow, because if l
> and h are unsigned, the computed value can never be negative, but it
> becomes bigger than INT_MAX if 2836 * h is bigger than 16807 * l (the
> unsigned result is computed modulo UINT_MAX+1).

t is still signed.  It has to be.  The final check at the end of
the function is (t < 0).  My patch doesn't change that.

> I think the original overflow can only happen if the argument of
> intrand32 is bigger than INT_MAX.

The original bug report complains about the calculation of l, not t.

The variable l is a modulus, so its largest possible value is 127772.
If the code simply said "l = ret % 127773;" then it wouldn't even be
an issue.  But the % was rewritten, presumably for efficiency.

The only thing that matters in terms of this bug report is that the
calculation of l's value is done using unsigned 32-bit integers at all
points, up until the final assignment to the variable l.  The original
code has l as a signed variable, which is OK if the value is calculated
using unsigned arithmetic for the intermediate steps, followed by an
implicit cast to bits32_t at the end.

The OP's bug report implies that they have some sort of compiler or
runtime environment where the intermediate arithmetic is done using
signed values.

The goal of my patch is to force *any* compiler to use unsigned arithmetic
at all points while calculating l.

Now, you mentioned t... and yeah, I can see how the calculation of t
might have similar issues, where the intermediate steps have to be done
with unsigned values, but in this case, the final value *must* be held
in a signed variable.

I'll have to defer to C experts here.  Is the code correct as written,
and it's simply the OP's compiler or runtime environment that's in
violation?  Or should the code do the multiplications with unsigned
values, store them in unsigned variables, and then replace the subtraction
with some kind of conditional that checks which of the two is greater?
Off the top of my head, I don't know.