由于 Mersenne Twister 引擎上的负索引，libstdc++ std::random 上的未定义行为（根据 clang -fsanitize=integer）

Question

我在 Ubuntu 20.04 LTS 上使用 clang++ 10，-fsanitize-undefined-trap-on-error -fsanitize=address,undefined,nullability,implicit-integer-truncation,implicit-integer-arithmetic-value-change,implicit-conversion,integer

我的代码正在生成随机字节

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

最后一行导致消毒程序报告未定义的行为位于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;
    }

错误如下：

/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

看起来有一个__m-__n == 397 - 624明显的负数差异，但操作数都是无符号的。

被减去的变量是定义的模板参数，size_t __n, size_t __m因此这不是随机边缘情况，而是正在实现的实际模板。

这是 STL 实现中的错误还是我的用法错误？

一个最小的可重现示例： https: //godbolt.org/z/vvjWscPnj

---

更新：向 GCC 提交的问题（不是错误）https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106469 - 关闭为“不会修复”

GCC 团队称 clang 的 ubsan 无符号整数溢出检查是不好的做法，因为该行为在 ISO C++ 中是明确定义的（作为模换行）。尽管 PRNG 中使用了模运算，但在本例中并非如此。

然而，在大多数用户空间代码中，无符号溢出几乎总是一个需要捕获的错误，而 GCC 的 STL 上的这种非错误会阻止用户从这种有用的检查中受益。

Answer 1

uint8_t在 a 中使用的结果std::uniform_int_distribution是未定义的，因此：

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

您可以使用short、int、long、long long、unsigned short、unsigned int、unsigned long或unsigned long long中的任何一个来代替。

引用自rand.req.gen/1.5

在整个子条款 [rand] 中，实例化具有名为 的模板类型参数的模板的效果IntType是未定义的，除非相应的模板参数是 cv 未限定的并且是short、int、long、long long、unsigned short、unsigned int、unsigned long、 或 之一unsigned long long。

如果这没有帮助，请跳过该-fsanitize=integer选项，因为

-fsanitize=integer：检查未定义或可疑的整数行为（例如无符号整数溢出）。启用signed-integer-overflow

...并且无符号整数溢出没有未定义的行为。对有符号整数溢出的检查将通过使用自动启用-fsanitize=undefined，因此您不必单独启用它。

如果仍然没有帮助，则可能是 gcc 库实现中的错误导致clang++了这种情况。您可以尝试使用clang++的库实现来看看是否有帮助：

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

Answer 2

尽管其他答案表明std::uniform_int_distribution使用uint8_t模板参数实例化是每个标准未定义的行为，但此处的 UBsan 警告与此无关。

UBSan 正在标记梅森扭曲器本身的实现，但该实现没有任何未定义的行为或错误。

如果你仔细观察，你会发现令人反感的表达是

_M_x[__k + (__m - __n)]

其中是通过循环从到__k范围内的值。(__n - __m)(__n - 1)for

这些操作涉及的所有类型都是std::size_t无符号的。因此，这些运算都使用模算术，因此即使__m - __n是负数并且不能用无符号类型表示，结果

__k + (__m - __n)

将位于0和之间__m - 1，因此用它索引数组不是问题。不涉及未定义的行为、未指定的行为或实现定义的行为。

标记此行为的 UBSan 检查并未标记实际的未定义行为。如果人们意识到这一点，那么依赖像这样的无符号算术的环绕行为是完全可以的。无符号溢出检查仅用于标记非故意的此类回绕的实例。您不应该在可能依赖它的其他人的代码上使用它，或者如果您可能依赖它，也不应该在您自己的代码上使用它。

在-fsanitize=address,undefined,nullability,implicit-integer-truncation,implicit-integer-arithmetic-value-change,implicit-conversion,integer所有情况下，除了address并undefined启用 UBsan 检查外，这些检查并不标记实际的未定义行为，而是在许多情况下可能是无意的条件。由于上述原因，默认-fsanitize=undefined清理程序标志默认情况下不会启用无符号整数溢出检查。有关详细信息，请参阅https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html。

Answer 3

unsigned类型在 C++ 中具有明确定义的包装行为。 这就是为什么它们被用于 PRNG 和其他位操作用例的原因之一，在这些用例中这是需要和预期的（并且对于算法来说是必需的），而不是错误。

GCC 开发人员是对的：将所有未签名的换行视为问题 是不合理的。更不合理的是打印出这是“未定义的行为”，而不是一个可能的问题。 如果 clang 的 ubsan 首先告诉您它在 C++ 中定义良好并且可能是有意为之，那么您就不必用对 GCC 开发人员无用的错误报告来打扰他们。或者，您可以在了解问题后将其表述为功能请求。

但你也是对的：头文件中的库函数成为你自己代码的一部分，当库代码（例如这个 PRNG）内联到同一个编译单元时，很难将库代码（例如这个 PRNG）与你自己的代码分开。ubsan 选项是针对每个文件的。

libc++ 的mt19937 实现会在必要时禁用 ubsan 检查。它是 C++ 标准库的最新实现，作为 LLVM 的一部分开发，主要与 clang 一起使用。如果有任何标头库能够满足这种将某些有效的 C++ 操作标记为问题的清理程序的需求，那么它就是 libc++。 https://godbolt.org/z/aeY5Yn9c6显示添加-stdlib=libc++到 Godbolt 上的编译选项可以让您的测试用例干净地运行。您必须在本地安装它才能实际使用它。

libc++ 定义了一个预处理器宏_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK（__attribute__((__no_sanitize__("unsigned-integer-overflow")))如果支持），因此它可以在每个函数的基础上禁用它。例如，请参阅libcxx 的<utility>标头，其中各种函数使用该标记，并且mersenne_twister_engine<...>::seed()在<random>. 但有趣的是，它并没有在任何地方都使用它，因此您仍然可以获得溢出检查的好处。

或者，您可以围绕随机数生成编写一个包装函数，并将其放入单独的.cpp编译中，无需使用sanitize=integer. 在使用 的发布版本中-flto，它仍然可以内联。或者，如果您不需要高质量的随机性，请使用 libc random(3)；它是单独编译的，而不是内联标头。Linuxrandom()并不可怕，但也不是很好。其他 PRNG（如 xorshift / xoroshiro）快速且良好，但也会使用unsigned类型并依赖于它们的乘法和/或加/减包装，除非它们仅使用移位和异或（如 LFSR）。

在 ISO C++ 中，无法仅将某些无符号操作标记为预期包装。

至少一种语言Rust确实解决了这个问题+：对于任何整数类型（包括有符号和无符号），对于 plain 、-、*、等，值范围的溢出始终是一个错误/。您可以使用x.wrapping_sub(y)通过明确定义的环绕进行有符号或无符号减法。类似地，对于 add/mul/div/rem/shift/pow。还有 saturating_sub/add/etc 和 Overflowing_... 返回包装结果和布尔值，或者 check_add/sub/etc 返回可以为 None 而不是保存整数的类型。因此，如果您想解决整数溢出问题，Rust 可能是适合您的语言。

（如果 LLVM 对无符号溢出的后端检查部分是由 Rust 推动的，我不会感到惊讶，并且有人认为有时将其公开以供 C++ 使用可能有用。但是，预计未使用该检查器编写的代码中会出现误报头脑。）

GNU C 整数环绕溢出扩展

GCC/Clang 和其他理解 C 和 C++ 的 GNU 方言的编译器具有整数溢出内置函数。这包括两者signed和unsigned包装 add/sub/mul。但仅限于（无符号）int// ；你必须弄清楚在 libstdc++ 中使用哪一个。（例如，在 Windows x64 上，必须是，但在 x86-64 System V 上是）longlong longsize_tsize_tlong longlong

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;
}

Godbolt 上的测试用例表明，__builtin_usubl_overflow可以安全地对 进行换行减法1UL, 2UL。（使 asm 甚至不尝试检测包装，因为我们已经告诉编译器这不是此操作的错误。）取消注释确实return x-y;会捕获溢出。

对于标准库代码中的每个无符号操作使用它会非常麻烦，其中包装不是错误，这就是为什么 libc++ 在每个函数的基础上禁用无符号包装清理程序。

由于无符号数学被明确定义为换行，因此使用这些 GNU C 内置函数的无符号版本的正常原因是捕获进位/借位输出，以便您知道它们是否换行。您可以在自己的操作中使用这些函数，而不是使用 clang 的 ，并且sanitize=integerbool结果为 false（没有包装溢出）。 unsignedassert()