在循环中的什么时候整数溢出变成未定义的行为?

问题描述 投票:85回答:12

这是一个例子来说明我的问题,其中涉及一些我不能在这里发布的更复杂的代码。

#include <stdio.h>
int main()
{
    int a = 0;
    for (int i = 0; i < 3; i++)
    {
        printf("Hello\n");
        a = a + 1000000000;
    }
}

这个程序在我的平台上包含未定义的行为,因为a将在第3个循环中溢出。

这是否会使整个程序具有未定义的行为,或者仅在溢出实际发生之后?编译器是否可能会发现a会溢出,所以它可以声明整个循环未定义而且不打扰运行printfs,即使它们都发生在溢出之前?

(标记为C和C ++,即使它们不同,因为如果它们不同,我会对这两种语言的答案感兴趣。)

c++ c undefined-behavior integer-overflow
12个回答
106
投票

如果您对纯粹的理论答案感兴趣,C ++标准允许未定义的行为“时间旅行”:

[intro.execution]/5:执行格式良好的程序的一致执行应该产生与具有相同程序和相同输入的抽象机器的相应实例的可能执行之一相同的可观察行为。但是,如果任何此类执行包含未定义的操作,则此国际标准不要求使用该输入执行该程序的实现(甚至不考虑第一个未定义操作之前的操作)

因此,如果您的程序包含未定义的行为,那么整个程序的行为是不确定的。


1
投票

你的例子没有考虑的一件事是优化。 a设置在循环中但从未使用过,优化器可以解决这个问题。因此,优化者完全丢弃a是合法的,在这种情况下,所有未定义的行为都会像boojum的受害者一样消失。

当然,这本身是未定义的,因为优化是不确定的。 :)


0
投票

由于这个问题是双重标记的C和C ++,我将尝试解决这两个问题。 C和C ++在这里采用不同的方法。

在C中,实现必须能够证明将调用未定义的行为,以便将整个程序视为 - 如果它具有未定义的行为。在OPs示例中,编译器证明这一点似乎是微不足道的,因此它是 - 如果整个程序未定义的那样。

我们可以从Defect Report 109看到这一点,它的关键在于:

但是,如果C标准认识到“未定义值”的单独存在(其纯粹的创建不涉及完全“未定义的行为”)那么进行编译器测试的人可以编写如下的测试用例,他/她也可以期待(或者可能要求)一致的实现应该至少编译这个代码(并且可能还允许它执行)而不会“失败”。

int array1[5];
int array2[5];
int *p1 = &array1[0];
int *p2 = &array2[0];

int foo()
{
int i;
i = (p1 > p2); /* Must this be "successfully translated"? */
1/0; /* Must this be "successfully translated"? */
return 0;
}

所以最重要的问题是:上述代码必须“成功翻译”(无论这意味着什么)? (见附件5.1.1.3的脚注。)

而回应是:

C标准使用术语“不确定值”而不是“未定义值”。使用不确定值的对象会导致未定义的行为。子条款5.1.1.3的脚注指出,只要有效的程序仍然正确翻译,实现就可以自由地产生任意数量的诊断。如果在需要常量表达式的上下文中出现一个表示其值得出现未定义行为的表达式,则包含的程序并不严格符合。此外,如果给定程序的每个可能的执行都会导致未定义的行为,则给定的程序不严格符合。一致的实现必须简单地转换严格符合的程序,因为该程序的某些可能的执行将导致未定义的行为。因为foo可能永远不会被调用,所以给定的示例必须通过一致的实现成功翻译。

在C ++中,这种方法似乎更加宽松,并且表明程序具有未定义的行为,无论实现是否可以静态地证明它。

我们有[intro.abstrac]p5说:

执行格式良好的程序的一致实现应该产生与具有相同程序和相同输入的抽象机的相应实例的可能执行之一相同的可观察行为。但是,如果任何此类执行包含未定义的操作,则本文档不要求使用该输入执行该程序的实现(甚至不考虑第一个未定义操作之前的操作)。


-1
投票

The top answer is a wrong (but common) misconception:

未定义的行为是运行时属性*。它不能“时间旅行”!

某些操作(由标准定义)具有副作用,无法进行优化。执行I / O或访问volatile变量的操作属于此类别。

但是,有一个警告:UB可以是任何行为,包括撤消先前操作的行为。在某些情况下,这可能会影响优化早期代码。

事实上,这与最高答案中的引用一致(强调我的):

执行格式良好的程序的一致实现应该产生与具有相同程序和相同输入的抽象机的相应实例的可能执行之一相同的可观察行为。 但是,如果任何此类执行包含未定义的操作,则此国际标准不要求使用该输入执行该程序的实现(甚至不考虑第一个未定义操作之前的操作)。

是的,这句话确实说“甚至没有关于第一个未定义操作之前的操作”,但请注意这是关于正在执行的代码,而不仅仅是编译。 毕竟,未实际到达的未定义行为不会执行任何操作,并且对于实际到达包含UB的行,其前面的代码必须首先执行!

So yes, once UB is executed, any effects of previous operations become undefined. But until that happens, the execution of the program is well-defined.

但请注意,导致这种情况发生的程序的所有执行都可以针对等效程序进行优化,包括执行先前操作但不执行其操作的任何程序。因此,可以优化前面的代码,只要这样做将等同于它们的效果被撤消;否则,它不能。请参阅下面的示例。

*注意:这与UB occurring at compile time不一致。如果编译器确实可以证明UB代码将始终针对所有输入执行,那么UB可以延伸到编译时。但是,这需要知道所有先前的代码最终返回,这是一个强烈的要求。再次,请参阅下面的示例/解释。


为了使这一点具体,请注意以下代码必须打印foo并等待您的输入,无论其后面是否有任何未定义的行为:

printf("foo");
getchar();
*(char*)1 = 1;

但是,请注意,无法保证在UB发生后foo将保留在屏幕上,或者您输入的字符将不再位于输入缓冲区中;这两个操作都可以“撤消”,这与UB“时间旅行”具有类似的效果。

如果不存在getchar()线,那么只有在输出foo然后“取消”它的情况下,才能将线路优化掉是合法的。

这两者是否无法区分将完全取决于实现(即在您的编译器和标准库上)。例如,你的printf可以阻止你的线程在等待另一个程序读取输出吗?或者会立即返回?

  • 如果它可以在这里阻塞,那么另一个程序可以拒绝读取其完整输出,并且它可能永远不会返回,因此UB可能永远不会实际发生。
  • 如果它可以在这里立即返回,那么我们知道它必须返回,因此优化它完全无法区分执行它然后取消它的效果。

当然,由于编译器知道它的特定版本的printf允许哪些行为,它可以相应地进行优化,因此printf可能在某些情况下而不是其他情况下得到优化。但是,再次证明,这与UB未执行的先前操作无法区分,而不是之前的代码由于UB而“中毒”。


31
投票

首先,让我更正这个问题的标题:

未定义的行为不是(特定)执行领域。

未定义的行为会影响所有步骤:编译,链接,加载和执行。

一些例子来强调这一点,请记住,没有任何部分是详尽无遗的:

  • 编译器可以假设从不执行包含未定义行为的代码部分,因此假设导致它们的执行路径是死代码。请参阅克里斯拉特纳以外的What every C programmer should know about undefined behavior
  • 链接器可以假设在存在多个弱符号定义(由名称识别)的情况下,由于One Definition Rule,所有定义都是相同的
  • 加载器(如果你使用动态库)可以采用相同的方式,从而选择它找到的第一个符号;这通常是(ab)用于在Unix上使用LD_PRELOAD技巧拦截调用
  • 如果你使用悬空指针,执行可能会失败(SIGSEV)

这就是未定义行为的可怕之处:提前几乎无法预测将会发生什么样的确切行为,并且必须在工具链,底层操作系统的每次更新时重新审视此预测,......


我建议观看Michael Spencer(LLVM开发人员)的视频:CppCon 2016: My Little Optimizer: Undefined Behavior is Magic


28
投票

针对16位int积极优化的C或C ++编译器将知道将1000000000添加到int类型时的行为未定义。

任何标准都允许它做任何它想要的东西,包括删除整个程序,留下int main(){}

但是更大的ints呢?我不知道编译器是做什么的(并且我不是任何方式的C和C ++编译器设计专家),但我想有时编译器针对32位int或更高将会发现循环是无限的(i不会改变)所以a最终会溢出。所以再次,它可以优化输出到int main(){}。我在这里要说的是,随着编译器优化逐渐变得更具攻击性,越来越多的未定义行为结构以意想不到的方式表现出来。

由于您正在写入循环体中的标准输出,因此循环无限的事实本身并未定义。


11
投票

从技术上讲,在C ++标准下,如果程序包含未定义的行为,则整个程序even at compile time(在程序执行之前)的行为是未定义的。

在实践中,因为编译器可能假设(作为优化的一部分)不会发生溢出,所以至少程序在循环的第三次迭代(假设32位机器)上的行为将是未定义的,尽管它您可能会在第三次迭代之前得到正确的结果。但是,由于整个程序的行为在技术上是未定义的,所以没有什么能阻止程序生成完全不正确的输出(包括没有输出),在执行期间的任何时候在运行时崩溃,或者甚至无法完全编译(因为未定义的行为扩展到编译时间)。

未定义的行为为编译器提供了更多优化空间,因为它们消除了对代码必须执行的操作的某些假设。在这样做时,依赖于涉及未定义行为的假设的程序不能保证按预期工作。因此,您不应该依赖于根据C ++标准被视为未定义的任何特定行为。


9
投票

要理解为什么未定义的行为可以'time travel' as @TartanLlama adequately put it,让我们来看看“as-if”规则:

1.9程序执行

1本国际标准中的语义描述定义了参数化的非确定性抽象机器。本国际标准对符合实施的结构没有要求。特别是,它们不需要复制或模拟抽象机器的结构。相反,需要符合实现来模拟(仅)抽象机器的可观察行为,如下所述。

有了这个,我们可以将程序视为带有输入和输出的“黑匣子”。输入可以是用户输入,文件和许多其他内容。输出是标准中提到的“可观察行为”。

标准只定义了输入和输出之间的映射,没有别的。它通过描述“示例黑盒子”来做到这一点,但明确说明具有相同映射的任何其他黑盒子同样有效。这意味着黑匣子的内容无关紧要。

考虑到这一点,在某个时刻发生未定义的行为是没有意义的。在黑盒子的示例实现中,我们可以说它发生的地点和时间,但实际的黑盒子可能是完全不同的东西,所以我们不能说它何时何地发生。从理论上讲,编译器可以例如决定枚举所有可能的输入,并预先计算结果输出。然后在编译期间会发生未定义的行为。

未定义的行为是输入和输出之间不存在映射。程序可能对某些输入具有未定义的行为,但为其他输入定义了行为。那么输入和输出之间的映射就不​​完整了;存在没有输出映射的输入。 问题中的程序对于任何输入都有未定义的行为,因此映射为空。


6
投票

假设int是32位,则在第三次迭代中发生未定义的行为。因此,例如,如果循环只是有条件地可达,或者可以在第三次迭代之前有条件地终止,那么除非实际达到第三次迭代,否则将没有未定义的行为。但是,在未定义的行为的情况下,程序的所有输出都是未定义的,包括相对于未定义行为的调用而言“过去”的输出。例如,在您的情况下,这意味着无法保证在输出中看到3个“Hello”消息。


6
投票

TartanLlama的回答是正确的。未定义的行为可以随时发生,即使在编译期间也是如此。这可能看起来很荒谬,但它是允许编译器做他们需要做的事情的关键特性。成为编译器并不总是那么容易。你必须每次都遵循规范所说的。然而,有时候证明特定行为正在发生可能是非常困难的。如果你还记得暂停问题,那么开发软件就无法证明它是否能够在输入特定输入时完成或进入无限循环。

我们可以让编译器变得悲观,并且不断编译,担心下一条指令可能是问题之类的暂停问题之一,但这是不合理的。相反,我们给编译器一个通道:在这些“未定义的行为”主题上,它们不承担任何责任。未定义的行为包括所有行为,这些行为是如此微妙的邪恶,以至于我们难以将它们与真正令人讨厌的邪恶的停止问题和诸如此类的东西分开。

有一个我喜欢发帖的例子,虽然我承认我失去了源头,所以我不得不解释。它来自特定版本的MySQL。在MySQL中,他们有一个循环缓冲区,里面装满了用户提供的数据。当然,他们想确保数据没有溢出缓冲区,所以他们检查了一下:

if (currentPtr + numberOfNewChars > endOfBufferPtr) { doOverflowLogic(); }

它看起来很清醒。但是,如果numberOfNewChars真的很大,并且溢出怎么办?然后它环绕并成为比endOfBufferPtr小的指针,因此溢出逻辑永远不会被调用。所以他们在那之前添加了第二张支票:

if (currentPtr + numberOfNewChars < currentPtr) { detectWrapAround(); }

看起来你照顾了缓冲区溢出错误,对吧?但是,提交了一个错误,指出此缓冲区溢出特定版本的Debian!仔细调查显示,这个版本的Debian是第一个使用特别尖端版本的gcc。在这个版本的gcc上,编译器认识到currentPtr + numberOfNewChars永远不会是比currentPtr更小的指针,因为指针的溢出是未定义的行为!这足以让gcc优化整个检查,突然你没有防止缓冲区溢出,即使你编写代码来检查它!

这是规范行为。一切都是合法的(虽然从我听到的,gcc在下一个版本中回滚了这个变化)。这不是我认为的直觉行为,但如果你稍微扩展想象力,很容易看出这种情况的轻微变体如何成为编译器的暂停问题。因此,规范编写者将其定义为“未定义行为”并声明编译器可以完成它所喜欢的任何事情。


4
投票

除了理论答案之外,一个实际的观察是,很长一段时间,编译器已经对循环应用了各种变换,以减少在其中完成的工作量。例如,给定:

for (int i=0; i<n; i++)
  foo[i] = i*scale;

编译器可能会将其转换为:

int temp = 0;
for (int i=0; i<n; i++)
{
  foo[i] = temp;
  temp+=scale;
}

因此,每次循环迭代都可以保存乘法。一种额外的优化形式,编译器适应不同程度的攻击性,将其转化为:

if (n > 0)
{
  int temp1 = n*scale;
  int *temp2 = foo;
  do
  {
    temp1 -= scale;
    *temp2++ = temp1;
  } while(temp1);
}

即使在溢出时有静音环绕的机器上,如果有一些小于n的数字可能会出现故障,当乘以比例时,它会产生0.如果从内存读取的比例不止一次,它也会变成无限循环意外地改变了它的值(在任何情况下,“scale”可以在不调用UB的情况下在循环中改变,编译器将不允许执行优化)。

虽然大多数此类优化在两个短无符号类型相乘以产生介于INT_MAX + 1和UINT_MAX之间的值的情况下不会有任何问题,但gcc在某些情况下循环中的这种乘法可能导致循环提前退出。我没有注意到这些行为源于生成代码中的比较指令,但是在编译器使用溢出来推断循环最多可以执行4次或更少次的情况下,它是可观察到的;默认情况下,如果某些输入会导致UB而其他输入不会产生警告,即使其推断导致循环的上限被忽略,也不会生成警告。


4
投票

根据定义,未定义的行为是灰色区域。你根本无法预测它会做什么或不会做什么 - 这就是“未定义的行为”的含义。

自远古以来,程序员一直试图从未定义的情况中挽救定义的残余。他们有一些他们真正想要使用的代码,但结果证明是未定义的,所以他们试图争辩说:“我知道它是未定义的,但在最坏的情况下,肯定会这样或那样;它永远不会这样做“。有时候这些论点或多或少是正确的 - 但往往是错误的。随着编译器越来越聪明(或者有些人可能会说,偷偷摸摸和偷偷摸摸),问题的界限也在不断变化。

实际上,如果你想编写保证可以工作的代码,并且这种代码将继续工作很长时间,那么只有一个选择:不惜一切代价避免未定义的行为。确实,如果你涉足它,它会回来困扰你。

© www.soinside.com 2019 - 2024. All rights reserved.