检测C/C++中的带符号溢出

Question

乍一看,这个问题看起来像是如何检测整数溢出的重复？然而,它实际上是显着不同的.

我发现虽然检测无符号整数溢出非常简单,但在C/C++中检测带符号的溢出实际上比大多数人想象的要困难.

最明显但又天真的方式是这样的:

int add(int lhs, int rhs)
{
 int sum = lhs + rhs;
 if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
  /* an overflow has occurred */
  abort();
 }
 return sum; 
}

这个问题是根据C标准,有符号整数溢出是未定义的行为. 换句话说,根据标准,只要您甚至导致签名溢出,您的程序就像取消引用空指针一样无效.因此,您不能导致未定义的行为,然后尝试在事后检测溢出,如上面的后置条件检查示例.

尽管上面的检查很可能适用于许多编译器,但你不能指望它.实际上,因为C标准说未定义有符号整数溢出,所以一些编译器(如GCC)将在设置优化标志时优化上述检查,因为编译器假定有符号溢出是不可能的.这完全打破了检查溢出的尝试.

因此,检查溢出的另一种可能方法是:

int add(int lhs, int rhs)
{
 if (lhs >= 0 && rhs >= 0) {
  if (INT_MAX - lhs <= rhs) {
   /* overflow has occurred */
   abort();
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= INT_MIN - rhs) {
   /* overflow has occurred */
   abort();
  }
 }

 return lhs + rhs;
}

这似乎更有希望,因为我们实际上并没有将两个整数加在一起,直到我们事先确定执行这样的添加不会导致溢出.因此,我们不会导致任何未定义的行为.

但是,遗憾的是,此解决方案的效率远低于初始解决方案,因为您必须执行减法操作才能测试您的添加操作是否有效.即使你不关心这个(小)性能打击,我仍然不完全相信这个解决方案是足够的.表达式lhs <= INT_MIN - rhs看起来就像编译器可能优化的那种表达式,认为签名溢出是不可能的.

那么这里有更好的解决方案吗？保证1)不会导致未定义的行为,2)不为编译器提供优化溢出检查的机会？我想可能有一些方法可以通过将两个操作数转换为无符号来执行它,并通过滚动自己的二进制补码算法来执行检查,但我不确定如何做到这一点.

Answer 1

不,你的第二个代码不正确,但你很接近:如果你设置了

int half = INT_MAX/2;
int half1 = half + 1;

添加的结果是INT_MAX.(INT_MAX总是一个奇数).所以这是有效的输入.但是在你的日常生活中INT_MAX - half == half1,你将会中止.误报.

可以通过放入<而不是<=在两个检查中修复此错误.

但是那时你的代码也不是最优的.以下是:

int add(int lhs, int rhs)
{
 if (lhs >= 0) {
  if (INT_MAX - lhs < rhs) {
   /* would overflow */
   abort();
  }
 }
 else {
  if (rhs < INT_MIN - lhs) {
   /* would overflow */
   abort();
  }
 }
 return lhs + rhs;
}

要看到这是有效的,你必须象征性地lhs在不等式的两边添加,这给出了你的结果超出范围的算术条件.

Answer 2

您的减法方法是正确的,定义明确.编译器无法对其进行优化.

另一种正确的方法,如果你有一个更大的整数类型可用,是在更大的类型中执行算术,然后在转换回来时检查结果是否适合较小的类型

int sum(int a, int b)
{
    long long c;
    assert(LLONG_MAX>INT_MAX);
    c = (long long)a + b;
    if (c < INT_MIN || c > INT_MAX) abort();
    return c;
}

一个好的编译器应该将整个加法和if语句转换为int-sized加法和单个条件跳转溢出,并且从不实际执行更大的加法.

编辑:斯蒂芬指出,我很难得到一个(不那么好)的编译器,gcc,以生成理智的asm.它生成的代码并不是非常慢,但肯定不是最理想的.如果有人知道这个代码的变种会让gcc做正确的事情,我很乐意看到它们.

Answer 3

恕我直言,处理溢出sentsitive C++代码的最东方方法是使用SafeInt<T>.这是一个托管在代码plex上的跨平台C++模板,它提供了您在此所需的安全保证.

• http://safeint.codeplex.com/

我发现它非常直观,因为它提供了许多与正常数值运算相同的使用模式,并通过异常表示流量和流量.

Answer 4

对于gcc的情况,从gcc 5.0发行说明我们可以看到它现在提供了一个__builtin_add_overflow用于检查溢出:

添加了一组用于具有溢出检查的算术的新内置函数:__ builtin_add_overflow,__ builtin_sub_overflow和__builtin_mul_overflow以及与clang和其他变体的兼容性.这些内置函数有两个完整的参数(不需要具有相同的类型),参数扩展为无限精度的有符号类型,+, - 或*对它们执行,结果存储在指向的整数变量中通过最后一个论点.如果存储的值等于无限精度结果,则内置函数返回false,否则返回true.保存结果的整数变量的类型可以与前两个参数的类型不同.

例如:

__builtin_add_overflow( rhs, lhs, &result )

我们可以从gcc文档中看到内置函数执行溢出检查算法:

[...]这些内置函数对所有参数值都有完全定义的行为.

clang还提供了一组经过检查的算术内置函数:

Clang提供了一组内置函数,它们以一种在C语言中快速且易于表达的方式为安全关键应用程序实现检查算法.

在这种情况下,内置将是:

__builtin_sadd_overflow( rhs, lhs, &result )

Answer 5

如果使用内联汇编程序,则可以检查溢出标志.另一种可能性是你可以使用safeint数据类型.我建议在Integer Security上阅读本文.

Answer 6

最快的方法是使用内置的GCC：

int add(int lhs, int rhs) {
    int sum;
    if (__builtin_add_overflow(lhs, rhs, &sum))
        abort();
    return sum;
}

在x86上，GCC将其编译为：

    mov %edi, %eax
    add %esi, %eax
    jo call_abort 
    ret
call_abort:
    call abort

它使用处理器的内置溢出检测。

如果您不能使用GCC内置函数，则下一个最快的方法是对符号位使用位操作。此外，在以下情况下还会发生签名溢出：

• 这两个操作数具有相同的符号，并且
• 结果的符号与操作数的符号不同。

的符号位~(lhs ^ rhs)是当且仅当操作数具有相同的符号，而符号位lhs ^ sum是当且仅当结果比操作数不同的符号。因此，您可以采用无符号形式进行加法操作以避免未定义的行为，然后使用符号位~(lhs ^ rhs) & (lhs ^ sum)：

int add(int lhs, int rhs) {
    unsigned sum = (unsigned) lhs + (unsigned) rhs;
    if ((~(lhs ^ rhs) & (lhs ^ sum)) & 0x80000000)
        abort();
    return (int) sum;
}

编译成：

    lea (%rsi,%rdi), %eax
    xor %edi, %esi
    not %esi
    xor %eax, %edi
    test %edi, %esi
    js call_abort
    ret
call_abort:
    call abort

这比在32位计算机（使用gcc）上转换为64位类型要快得多：

    push %ebx
    mov 12(%esp), %ecx
    mov 8(%esp), %eax
    mov %ecx, %ebx
    sar $31, %ebx
    clt
    add %ecx, %eax
    adc %ebx, %edx
    mov %eax, %ecx
    add $-2147483648, %ecx
    mov %edx, %ebx
    adc $0, %ebx
    cmp $0, %ebx
    ja call_abort
    pop %ebx
    ret
call_abort:
    call abort