Undefined behavior (according to clang -fsanitize=integer) on libstdc++ std::random due to negative index on Mersenne Twister engine

Question

I'm using clang++ 10 on Ubuntu 20.04 LTS, with -fsanitize-undefined-trap-on-error -fsanitize=address,undefined,nullability,implicit-integer-truncation,implicit-integer-arithmetic-value-change,implicit-conversion,integer

My code is generating random bytes with

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<uint8_t> dd(0, 255);
    ...
    ch = uint8_t(dd(gen));

This last line causes the sanitizer to report undefined behavior is in bits/random.tcc

template<...> void  mersenne_twister_engine<...>::
    _M_gen_rand(void)   {
      const _UIntType __upper_mask = (~_UIntType()) << __r;
      const _UIntType __lower_mask = ~__upper_mask;

      for (size_t __k = 0; __k < (__n - __m); ++__k)
      {
         _UIntType __y = ((_M_x[__k] & __upper_mask)
               | (_M_x[__k + 1] & __lower_mask));
         _M_x[__k] = (_M_x[__k + __m] ^ (__y >> 1)
               ^ ((__y & 0x01) ? __a : 0));
      }

      for (size_t __k = (__n - __m); __k < (__n - 1); ++__k)
      {
          _UIntType __y = ((_M_x[__k] & __upper_mask)
                   | (_M_x[__k + 1] & __lower_mask));
          _M_x[__k] = (_M_x[__k + (__m - __n)] ^ (__y >> 1)  <<<<===== this line
               ^ ((__y & 0x01) ? __a : 0));
      }

      _UIntType __y = ((_M_x[__n - 1] & __upper_mask)
               | (_M_x[0] & __lower_mask));
      _M_x[__n - 1] = (_M_x[__m - 1] ^ (__y >> 1)
               ^ ((__y & 0x01) ? __a : 0));
      _M_p = 0;
    }

The error reads:

/usr/include/c++/10/bits/random.tcc:413:33: runtime error: unsigned integer overflow: 397 - 624 cannot be represented in type 'unsigned long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/include/c++/10/bits/random.tcc:413:33 in 
/usr/include/c++/10/bits/random.tcc:413:26: runtime error: unsigned integer overflow: 227 + 18446744073709551389 cannot be represented in type 'unsigned long'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/include/c++/10/bits/random.tcc:413:26 in

It appears that there is a difference __m-__n == 397 - 624 that is obviously negative but the operands are all unsigned.

The variables being subtracted are template parameters defined as size_t __n, size_t __m so this is not a random edge case, it's the actual template being implemented.

Is this a bug in this implementation of the STL or my usage is wrong?

A minimal reproducible example: https://godbolt.org/z/vvjWscPnj

---

UPDATE: Issue (not a bug) filed to GCC https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469 - closed as "WONT FIX"

GCC's team called clang's ubsan unsigned integer overflow checks bad practice, because the behaviour is well-defined (as modulo wrapping) in ISO C++. Although modulus arithmetic is used in PRNG, this is not the case in this particular case.

However in most userspace code a unsigned overflow is almost all the time a bug to be caught and this non-bug on the GCC's STL prevents users from benefitting from this useful check.

Singspiel

Seems to me to rather be a false positive from the UB sanitizer. – Radburn

Unsigned integer overflow is not UB in C++. UBSAN disables this check by default. If you enable this check, you should understand what you do. Usually 3rd party code goes to suppressions. The manual: -fsanitize=unsigned-integer-overflow: Unsigned integer overflow, where the result of an unsigned integer computation cannot be represented in its type. Unlike signed integer overflow, this is not undefined behavior, but it is often unintentional. – Woof

I'm running with -ggdb3 -O0 -fsanitize-undefined-trap-on-error -fsanitize=address,undefined,nullability,implicit-integer-truncation,implicit-integer-arithmetic-value-change,implicit-conversion,integer -fno-omit-frame-pointer – Singspiel

@HFTrader The -fsanitize= options nullability, implicit-integer-truncation, implicit-integer-arithmetic-value-change, implicit-conversion and integer all enable UBsan checks which are not flagging actual undefined behavior. You should be careful to not enable them for third party code that may rely on the behavior they flag and that you yourself don't rely on their behavior. The flags are intended only to flag behavior that is often unintentional. See clang.llvm.org/docs/UndefinedBehaviorSanitizer.html. Though it turns out you have library UB here indeed per posted answer – Labe

I think we need to see a minimal reproducible example. – Unthinkable

@TedLyngmo Here we go: godbolt.org/z/vvjWscPnj – Singspiel

"GCC's team alled clang's ubsan unsigned integer overflow's checks bad practice" - what? I have no idea what that was supposed to say. – Fou

@Labe Per the posted answer it is UB to use uint8_t there, but it is the well defined unsigned overflow that the sanitizer is catching and wrongly calling undefined-behavior. – Grubb

@JanHudec Yes, I wrote an answer explaining that after I made the comments above. – Labe

Nice collection of sanitiser warning flags! Assuming their behaviour is not overly pedantic, I should consider using them for my CI builds... – Emlyn

Answer 1

Although as the other answer indicates it is undefined behavior per standard to instantiate std::uniform_int_distribution with uint8_t template argument, the UBsan warning here is unrelated to that.

UBSan is flagging the implementation of the Mersenne twister itself, but the implementation doesn't have any undefined behavior or bug.

If you look closely you see that the offending expression is

_M_x[__k + (__m - __n)]

where __k is a value in the range from (__n - __m) to (__n - 1) via the for loop.

All of the types involved in these operations are std::size_t which is unsigned. As a consequence these operations all use modular arithmetic and therefore even if __m - __n is negative and not representable in the unsigned type, the result of

__k + (__m - __n)

will lie between 0 and __m - 1, so that indexing the array with it is not a problem. No undefined behavior, unspecified behavior or implementation-defined behavior is involved.

The UBSan check which is flagging this is not flagging actual undefined behavior. It is perfectly ok to rely on the wrap-around behavior of unsigned arithmetic like this if one is aware of it. The unsigned overflow check is only meant to be used to flag instances of such wrap-around where it was not intentional. You shouldn't use it on other's code that might rely on it or on your own code if you might be relying on it.

In -fsanitize=address,undefined,nullability,implicit-integer-truncation,implicit-integer-arithmetic-value-change,implicit-conversion,integer all except address and undefined enable UBsan checks which are not flagging actual undefined behavior, but conditions that may be unintentional in many cases. The default -fsanitize=undefined sanitizer flag doesn't enable the unsigned integer overflow check by default for the reasons given above. See https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html for details.

Labe

So the message is misleading then SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ... – Singspiel

@HFTrader I guess they could have worded the message better and used something else than "undefined-behavior" for this check, but you can get that message only if you intentionally enable the check that shouldn't generally be enabled, so I guess one could expect the user to be aware of the actual meaning. It might be worth it to post a bug report or feature request to fix the wording. – Labe

A smaller mre: godbolt.org/z/9T6nqxdvs . Tracks to this: -fsanitize=unsigned-integer-overflow: Unsigned integer overflow, where the result of an unsigned integer computation cannot be represented in its type. Unlike signed integer overflow, this is not undefined behavior, but it is often unintentional. This sanitizer does not check for lossy implicit conversions performed before such a computation – Singspiel

While I agree that the result will be correct, the fact that clang's own libc++ does not display any of this type of behavior tells me this is not intended and works by chance alone. – Singspiel

@MadFred I am sure that the libstdc++ authors know what they are doing and that this construction is intentional. If you look from the point-of-view that arithmetic operators perform modular arithmetic instead of bounded arithmetic, such code makes complete sense and is actually often more elegant than working in bounded arithmetic would be. – Labe

@MadFred Libc++ is not completely avoiding it either. Instead it is using attributes to suppress the unsigned integer overflow check where it is relied on. Look for _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK in the libc++ source code. Libstdc++ doesn't bother adding such annotations because they are not in favor of using the check to begin with. This is just a difference in approach between Clang and GCC developers. – Labe

I'd agree with you IF it was not easier to write (__k+__m)-__n instead. The only danger of that is an unsigned overflow of k+m but that seems impossible given they are indices on an array. I believe it's just an oversight that passed tests. – Singspiel

@MadFred The point is that addition in modular arithmetic is associative. It doesn't matter where you place parentheses. My guess is that they are only placed the way they are to indicate that this index is walking the array shifted by __m-__n from the range that __k itself is walking. I guess it would actually look nicer as __k - (__n - __m) in that regard, but it really doesn't matter. – Labe

I had seriously considered giving the accepted flag to your answer as it is equally good and thoughtful as the one above. But as this was in reality a non-issue, It came down to just the timing of it. – Singspiel

@MadFred If you doubt which answer is best, I'll happily give mine to this one. I like my own answer as a guide to "how to solve the issue" kind of answer. This answer digs into it. I wouldn't mind if you changed your accept vote. Btw, I gave this answer my upvote as soon as I saw it. – Unthinkable

@TedLyngmo Here is the deal: you helped me find the issue and that has the most value at least for me and there's my thank you vote. Admins might disagree. – Singspiel

@MadFred There are no admins deciding which answer is best. I just wanted you to know that I properly liked this answer and the in-depth analysis in it - and deciding to put that as the accepted would be reasonable. I still like my answer though and I'm glad you liked it too. – Unthinkable

Answer 2

The result of using uint8_t in a std::uniform_int_distribution is undefined, so:

std::uniform_int_distribution<uint8_t> dd(0, 255); // Don't do this!

You can use any of short, int, long, long long, unsigned short, unsigned int, unsigned long, or unsigned long long instead.

Quote from rand.req.gen/1.5

Throughout this subclause [rand], the effect of instantiating a template:
that has a template type parameter named IntType is undefined unless the corresponding template argument is cv-unqualified and is one of short, int, long, long long, unsigned short, unsigned int, unsigned long, or unsigned long long.

If that doesn't help, skip the -fsanitize=integer option since

-fsanitize=integer: Checks for undefined or suspicious integer behavior (e.g. unsigned integer overflow). Enables signed-integer-overflow

... and unsigned integer overflow does not have undefined behavior. The check for signed integer overflow will be automatically enabled by using -fsanitize=undefined so you don't have to enable that separately.

If that still doesn't help, it could be a bug in the gcc library implementation used by clang++ that causes this. You can try using clang++'s library implementation to see if that helps:

clang++ -stdlib=libc++ ...

Unthinkable

Cool, TIL. Now I'm curious why this is so! – Radburn

@CaptainGiraffe Yeah, I remember having read it some time ago and corrected a place on cppreference which did not mention this limitation. My edits got reverted until I cited the standard. The standard does not say why, only that this is how it is. – Unthinkable

Is that in the C++ standard? I see no reference there for the types allowed. – Singspiel

@HFTrader eel.is/c++draft/rand.req.genl#1.5 – Labe

Jeez how hard it is to add a check in that template? – Singspiel

@HFTrader At the time that this functionality was added it wasn't common to SFINAE-restrict class template arguments like this. If it was introduced now, I am pretty sure concept checks would be used. But I also don't really understand why this restriction was made. There was apparently a LWG issue about this, but it was closed as not-a-defect (instead a feature request): cplusplus.github.io/LWG/lwg-closed.html#2326 – Labe

@TedLyngmo Ends up commenting this line did not make the message go away. The issue is still in another line: std::uniform_int_distribution<uint64_t> ds(1, maxsize); size_t size = ds(gen); where maxsize has values from 2 to 4096. Even with 2 it triggers. – Singspiel

@HFTrader Ok, I can't see any other cause for UB in the snippet you've shown us so please update the question and put a minimal reproducible example in it. – Unthinkable

@TedLyngmo using libc++ actually makes the message go away – Singspiel

@HFTrader Nice! I then strongly suspect a bug in the gcc library implementation - or how clang++ uses it. – Unthinkable

No need to replace with signed-integer-overflow. -fsanitize=undefined already enables pretty much all checks that check actual undefined behavior, I think except for local-bounds (I think for performance reasons) and float-divide-by-zero (which is defined per IEEE 754 but not per C and C++). – Labe

@Labe Yeah, I noticed that "-fsanitize=undefined: All of the checks listed above other than float-divide-by-zero, unsigned-integer-overflow, implicit-conversion, local-bounds and the nullability-* group of checks". Updated the answer. – Unthinkable

"A stupid clang sanitizer that complains about perfectly valid code" is not sufficient to conclude there's a bug in gcc's std::lib. – Fleta

@JonathanWakely Indeed. I didn't conclude that it is a bug in gcc's std::lib (even though I strongly suspected it was). I read about all the clang specific options OP used and added the possible fix to stop using -fsanitize=integer to the answer. – Unthinkable

I wonder if they also have other "relies on explicit guarantees in the C++ language standard" sanitizers. Maybe an "assumes a byte has at least 8 bits" sanitizer, or an "assumes std::string.c_str() returns a NUL-terminated buffer" sanitizer. – Actinozoan

@CodyGray There are a lot of different sanitizers. I don't think the two you mentioned exists though :-) – Unthinkable

@CodyGray this is the only one I'm aware of that traps for behaviour that has 100% guaranteed, defined behaviour that is not at all "undefined". – Fleta

@CaptainGiraffe Why Aren't std::uniform_int_distribution<uint8_t> and std::uniform_int_distribution<int8_t> Allowed? – Clyster

Ah, the ever troublesome "uniform int distribution is not specialised for char/uint8_t" issue. I really do think that this should be registered as a defect in the C++ standard, if it hasn't been already. It seems fairly arbitrary to not support this (even if the implementation just wraps that for uint16_t and casts the result, which is what I do currently when I need random bytes). – Emlyn

@JonathanWakely In the link phuclv shared, you are cited saying "it was very definitely intentional that single byte integers are not supported, not an accidental omission, and so we should be careful about just changing that without consulting the designers of the C++11" - And since the defect report was closed as "not a defect" I wonder, what was the original reason for not including single byte integers? I assume that those of you who handled the defect report got the motivation from the designers of C++11. – Unthinkable

@Emlyn A defect report was submitted and closed as "not a defect" as can be seen in the link phuclv shared. – Unthinkable

@JonathanWakely I found the answer to my question in a comment to Brian Bi who asked the very same thing: "no, but if I had to guess it's because characters are not integers, integers are not characters". – Unthinkable

Answer 3

unsigned types have well-defined wrapping behaviour in C++. This is one reason why they get used in PRNGs and other bit-manipulation use-cases where that's desired and expected (and necessary for the algorithm), not an error.

GCC devs are right: it's unreasonable to treat all unsigned wrapping as a problem. It's even more unreasonable to print out that it's "undefined behaviour", rather than a possible problem. If clang's ubsan had told you in the first place that it was well-defined in C++ and perhaps intended, you wouldn't have had to bother the GCC devs with a bug report that wasn't useful to them. Or you could have phrased it as a feature request after understanding the issue.

But you're also right: with library functions in headers where they become part of your own code, that makes it very hard to disentangle library code (such as this PRNG) from your own code, when it inlines into the same compilation unit. And ubsan options are per-file.

---

libc++'s implementation of mt19937 disables that ubsan check where necessary. It's a more recent clean-slate implementation of the C++ standard library developed as part of LLVM and mostly used with clang. If any header-library was going to cater to this sanitizer that flags some valid C++ operations as problems, it would be libc++. https://godbolt.org/z/aeY5Yn9c6 shows that adding -stdlib=libc++ to the compile options on Godbolt lets your test case run cleanly. You'd have to get it installed locally to actually use it.

libc++ defines a preprocessor macro _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK as __attribute__((__no_sanitize__("unsigned-integer-overflow"))) (if supported), so it can disable that on a per-function basis. See for example libcxx's <utility> header where various functions use that tag, and mersenne_twister_engine<...>::seed() in <random>. But interestingly, it doesn't use it everywhere, so you can still get the benefit of overflow checking.

Or you could write a wrapper function around random number generation and put that in a separate .cpp you compile without sanitize=integer. In a release build with -flto, it can still get inlined. Or if you don't need as high quality randomness, use libc random(3); it is separately compiled, not an inline header. Linux's random() is non-terrible, although not great either. Other PRNGs like xorshift / xoroshiro are fast and good, but would also use unsigned types and rely on their wrapping for multiply and/or add/sub, unless they only use shifts and xor like an LFSR.

---

There's no way to mark only some unsigned operations as wrapping-expected in ISO C++.

At least one language, Rust, does solve this problem: overflow of the value-range is always an error for plain +, -, *, /, etc. for any integral type including signed and unsigned. You can use x.wrapping_sub(y) to do signed or unsigned subtraction with well-defined wrap-around. Similarly for add/mul/div/rem/shift/pow. And there's saturating_sub/add/etc, and overflowing_... that returns the wrapped result and a boolean, or checked_add/sub/etc that returns a type that can be None instead of holding an integer. So if you want to fuss over integer overflows, Rust might be the language for you.

(I wouldn't be surprised if LLVM's back-end checking for unsigned overflow was partially motivated by Rust, and someone thought it might sometimes be useful to expose that for use by C++. But expect false positives in code not written with that checker in mind.)

---

GNU C integer wrapping overflow extensions

GCC/Clang and other compilers that understand the GNU dialect of C and C++ have integer-overflow builtins. That includes both signed and unsigned wrapping add/sub/mul. But only for (unsigned) int/long/long long; you'd have to figure out which one to use for size_t in libstdc++. (e.g. on Windows x64, size_t has to be long long, but on x86-64 System V it's long)

unsigned long wrapping_sub(unsigned long x, unsigned long y)
{
    // return x - y;       // ISO C++ without working around sanitize=integer

    unsigned long res;
    bool borrow = __builtin_usubl_overflow(x, y, &res);
    return res;
}

A test case on Godbolt shows that __builtin_usubl_overflow does safely do a wrapping subtract of 1UL, 2UL. (Making asm that doesn't even try to detect wrapping, because we've told the compiler that's not an error on this one operation.) Uncommenting return x-y; does trap the overflow.

It would be very cumbersome to use this for every unsigned operation in standard library code where wrapping isn't an error, which is why libc++ disables the unsigned-wrapping sanitizer on a per-function basis instead.

---

Since unsigned math is well-defined as wrapping, the normal reason for using the unsigned versions of these GNU C builtins is to capture the carry/borrow output, so you know if they wrapped. Instead of using clang's sanitize=integer, you could use these functions on your own unsigned operations, and assert() that the bool result is false (no wrapping overflow).

Feria

Clang supports a out-of-line sanitizer ignore-list based on mangled name, also with wildcards, (clang.llvm.org/docs/SanitizerSpecialCaseList.html) so I guess one could just add offending standard library functions into it or even wholesale ignore C++ standard library functions with a few entries of the form fun:_ZSt*, fun:_ZNSt*, etc. Or maybe the source-file entries also work for template instantiations (haven't tested) and adding an entry of the form src: with a wildcard path to the standard library headers may also be enough. – Labe

Mersenne Twister was a godsend when it appeared 25 years ago, but it has several disadvantages. These days, I'd seriously recommend a more modern PRNG, eg something from the PCG or xorshift families. – Peccary

@Peter Cordes Rust would catch this case by default in non-release code. When something has been done default in a strict language like Rust you know that this issue is very important for the user. – Singspiel

@MadFred: Are you still arguing that people should avoid writing C++ code that does modulo-wrapped unsigned math on purpose, even when that's what they need? How to you propose that libstdc++ should be written? With __builtin_usubl_overflow instead of - in this and many other functions? Or with clang-specific __attribute__(()) controled by an #ifdef like libc++ uses? Or that this case should have cast to ssize_t and back for signed subtraction? – Feria

@MadFred: A newly-designed language like Rust has nice features that make it possible to be more explicit about integer-overflow safety. This wasn't something that the designers of C were thinking about back in the early 70s when the language was being designed, and C++ inherits its semantics. As I explained in my answer, ISO C++ doesn't have a way to indicate that wrapping is expected on only some ops. If you don't like how general C++ works, don't use it. Or only use libraries (like libc++) that cater to the subset of it you want to use, where you define unsigned wrapping as not allowed. – Feria

@PeterCordes Is your opinion (like of GCC's team) that this check is (sic) "stupid" and should be removed from clang tools? – Singspiel

@MadFred: No, it's a useful thing to have if you understand the implications for using it in a C++ world. Like I said in my answer, it's stupid that it claims there's "undefined-behavior", that's highly misleading and confusing, and is what led to this disconnect between you and the GCC team. Instead of asking nicely for them to work around clang's sanitizer so you could use it with libstdc++, you reported a non-bug with a bug-title saying it was undefined behaviour, and suggesting that what the code does was actually wrong. Naturally they're going to be dismissive about it when put that way. – Feria

@MadFred: Also, as user17732522 points out, clang.llvm.org/docs/SanitizerSpecialCaseList.html documents how you can add a list of functions to ignore, so you can filter out libstdc++ functions that would trigger false positives with this sanitizer. – Feria