[Bug libstdc++/106469] New: Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[Bug libstdc++/106469] New: Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[hbucher at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

            Bug ID: 106469
           Summary: Undefined behavior triggered on Mersenne Twister
                    engine due to unsigned integer overflow
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: hbucher at gmail dot com
  Target Milestone: ---

1. the exact version of GCC, as shown by "gcc -v"

This triggers from gcc 9.4.0 (standard Ubuntu 20.04) up to gcc trunk. 

2. the system type

This is reproducible from my Ubuntu 20.04 LTS install to godbolt.org


3. the options when GCC was configured/built

Configured with: ../src/configure -v --with-pkgversion='Ubuntu
9.4.0-1ubuntu1~20.04.1' --with-bugurl=file:///usr/share/doc/gcc-9/README.Bugs
--enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,gm2 --prefix=/usr
--with-gcc-major-version-only --program-suffix=-9
--program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id
--libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
--libdir=/usr/lib --enable-nls --enable-clocale=gnu --enable-libstdcxx-debug
--enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new
--enable-gnu-unique-object --disable-vtable-verify --enable-plugin
--enable-default-pie --with-system-zlib --with-target-system-zlib=auto
--enable-objc-gc=auto --enable-multiarch --disable-werror --with-arch-32=i686
--with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib
--with-tune=generic
--enable-offload-targets=nvptx-none=/build/gcc-9-Av3uEd/gcc-9-9.4.0/debian/tmp-nvptx/usr,hsa
--without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu

4. the exact command line passed to the gcc program triggering the bug 

clang++ -fsanitize=unsigned-integer-overflow test.cpp -o test

5. a collection of source files for reproducing the bug, preferably a minimal 

https://godbolt.org/z/Kr3rr5n8j

#include <random>
int main() {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<uint64_t> ds(1, 8);
    size_t size = ds(gen);
}

6. a description of the expected behavior

The program should run and terminate silent. 

7. a description of actual behavior.

The program runs and prints the following message: 
Program returned: 0
/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/13.0.0/../../../../include/c++/13.0.0/bits/random.tcc:416:33:
runtime error: unsigned integer overflow: 397 - 624 cannot be represented in
type 'unsigned long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior
/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/13.0.0/../../../../include/c++/13.0.0/bits/random.tcc:416:33
in 
/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/13.0.0/../../../../include/c++/13.0.0/bits/random.tcc:416:26:
runtime error: unsigned integer overflow: 227 + 18446744073709551389 cannot be
represented in type 'unsigned long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior
/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/13.0.0/../../../../include/c++/13.0.0/bits/random.tcc:416:26
in 

The problem is discussed on stack overflow: 

https://stackoverflow.com/questions/73157920/undefined-behavior-on-libstdc-stdrandom-due-to-negative-index-on-mersenne-tw

This does not exactly seem to be undefined behavior but it is wrong enough that
it triggers the message. 

The problem is line 416 on /usr/include/c++/13.0.0/bits/random.tcc where there
is this expression:

__k + (__m - __n)

where __k is a variable and __m and __n are template parameters. 

In the mre example __m=397 and __n=624 so (__m-__n) is negative although summed
with __k it becomes positive. 

This is so far the ONLY place where ubsan triggers a message in my entire
codebase. 

The message goes away when I compile my code with clang's libc++
(-stdlib=libc++).

[Bug libstdc++/106469] Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |WONTFIX
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
fsanitize=unsigned-integer-overflow is not a valid thing to do in general for
any defined C code.

[Bug libstdc++/106469] Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=81749,
                   |                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=96829,
                   |                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=91547

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
There is a reason why GCC does not implement this "undefined" sanitize is
because it is not undefined code to wrap for unsigned integer.
It is bad that clang/LLVM implements it and people now think it is undefined
and report bugs like this.

[Bug libstdc++/106469] Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[hbucher at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

--- Comment #3 from Henry <hbucher at gmail dot com> ---
I agree that technically it is not UB. However I still think it is bad
practice. 

So far that single line is the only place in all libstdc++ that triggers that
undefined. 

I cannot believe that a developer consciously chose to let unsigned underflow
happen in such simple expression.

So instead of K + (M - N) why not just change it to (K + M) - N? It is such a
simple change. I have modified it and tested but not to the extent to run all
the libstdc++ unit tests.

[Bug libstdc++/106469] Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Henry from comment #3)
> I agree that technically it is not UB. However I still think it is bad
> practice. 

The only bad practice is the option -fsanitize=unsigned-integer-overflow. Look
at the other bug reports I linked here and you will see there are other areas
of libstdc++ where the bad option will cause issues.

[Bug libstdc++/106469] Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Henry from comment #3)
> So far that single line is the only place in all libstdc++ that triggers
> that undefined. 

No it isn't, we "fixed" another one a few days ago, in perfectly correct code,
just to silence this stupid sanitizer.


> I cannot believe that a developer consciously chose to let unsigned
> underflow happen in such simple expression.

You're wrong, twice. The behaviour of that code is intentional, and there is no
underflow. Unsigned integers cannot underflow or overflow, by definition. They
are defined to wrap around with modulus arithmetic, which is exactly the
behaviour desired for Mersenne twister (and most other PRNGs). If you want
modulus arithmetic and unsigned integers have modulus arithmetic, relying on
that makes perfect sense.

This sanitizer is stupid.

[Bug libstdc++/106469] Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[hbucher at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

--- Comment #6 from Henry <hbucher at gmail dot com> ---

> This sanitizer is stupid.

That is an unjust comment on great work from the LLVM team. An unsigned
overflow in user code is almost always a bug due to some oversight, there is no
denying that. Look at Arianne 5 for an example.

The community at large (aka "the users") might have very low priority on your
priorities list but as there is no way to turn off "unsigned-integer-overflow"
for specific includes, they have to turn off these checks on user code as well.
It has a significant impact on us.  But its your project at the end of the day.

[Bug libstdc++/106469] Undefined behavior triggered on Mersenne Twister engine due to unsigned integer overflow

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
"An unsigned overflow" does not exist.
That is the point here.
And that is why this sanitizer is bogus and should never be used.

And yes overflow wrapping is sometimes a bug in the code but if the code
depends on the wrapping behavior then it is wrong to complain about it. C and
c++ requires wrapping behavior for unsigned types.

This option is bogus and should be removed even from llvm.