A Guide to Undefined Behavior in C and C++

John Regehr
Nov 13, 2019 23 min read

原文链接

第一篇

程序设计语言通常会区分程序的正常动作和错误动作。对于具有图灵完整性的语言， 我们不可能在离线状态下可靠地判定一个程序是否可能执行错误动作， 我们只能运行它并观察结果。

在 安全 的程序设计语言中，一旦出现错误，它会被捕获。 例如，Java 通过使用其异常系统，在很大程度上是安全的。 在 不安全 的程序设计语言中，错误不会被捕获。相反，在执行错误的操作后， 程序继续运行，但却是以潜藏着错误的方式运行， 这种错误的运行方式随后可能产生可观察的后果。 Luca Cardelli 关于类型系统的文章很好地对这类问题进行了清晰的介绍。 C 和 C++ 在强意义下是不安全的： 执行一个错误的操作可能导致整个程序变得没有意义， 而不仅仅是错误操作的结果不可预测。在这类语言中， 我们称错误操作具有未定义行为。

C FAQ 如下定义术语“未定义行为”：

任何事情都可能发生，语言标准不做任何规定。 程序可能无法编译，或者错误地执行（崩溃或静默地产生错误结果）， 也可能恰好以程序员预期的方式执行。

这是一个很好的概述。几乎每个 C 或 C++ 程序员都理解， 访问空指针或者除零是错误的动作，但另一方面， 未定义行为及其与激进的编译器之间的相互作用产生的全部影响则并非众所周知的。 本文将展示这些问题。

未定义行为的模型

现在，我们忽略编译器的存在。我们仅仅假设存在符合 C 标准的 “C 实现” —— 它在执行符合标准的 C 程序时就像 “C 抽象机” 一样。 C 抽象机是一个符合 C 语言标准描述的简单的 C 解释器， 我们用它描述任何 C 程序的语义。

程序的执行过程由简单的步骤组成，例如“将两个数相加”或者“跳转到某个标签”。 如果程序执行的每个步骤都有确切定义的行为，那么整个执行过程是有良好定义的。 需要注意的是，即使是有良好定义的执行过程，也可能由于未指定或实现定义的行为， 产生不同结果。在本文中我们忽略这种情况。

如果程序执行过程中，存在任何具有未定义行为的步骤，则整个执行过程是没有意义的。 这非常重要：这并不是说计算 (1<<32) 会得到不可预计的结果， 而是说任何计算了该表达式的程序执行过程都完全没有意义。另外， 这不是说程序的执行过程在发生未定义行为之前有意义： 未定义的动作造成的恶果可以在该动作之前发生。

作为一个简单的例子，我们观察下列程序：

#include <limits.h>
#include <stdio.h>

int main (void)
{
  printf ("%d\n", (INT_MAX+1) < 0);
  return 0;
}

这个程序要求 C 实现回答一个简单的问题：如果我们将 1 加到最大的可表示的整数上， 结果会是负数吗？对于 C 实现来说，下列行为是完全合法的：

$ cc test.c -o test
$ ./test
1

下列行为也是合法的：

$ cc test.c -o test
$ ./test
0

下列行为同样合法：

$ cc test.c -o test
$ ./test
42

下列行为仍然合法：

$ cc test.c -o test
$ ./test
正在格式化根分区，咔嚓 咔嚓

有人可能会说：上面描述的一些编译器的行为是错误的， 因为 C 标准规定比较运算符必须返回 0 或者 1。 然而，既然这个程序完全没有意义，实现可以做它想做的任何事。 未定义行为直接摧毁 C 抽象机的其他行为。

一个实际的编译器可能产生格式化你的磁盘的代码吗？当然不会， 但请注意经验主义地说，未定义行为通常导致各种坏事， 因为许多安全缺陷都来自于具有未定义行为的内存操作或整数运算。 例如，访问越过数组边界的元素是栈溢出攻击的关键环节。 因此，可以总结：编译器并不产生格式化磁盘的代码。然而， 由于数组访问越界，你的电脑会执行恶意代码，而恶意代码可能格式化你的磁盘。

不要走步

很多人都会说 —— 或者至少想类似下面这样的东西：

x86 ADD 指令被用于实现 C 的带符号加法操作， 该指令在结果溢出时具有 2-补码的行为。 我在 x86 平台上进行开发，因此我可以预测在 32 位带符号整数溢出时， 会得到 2-补码的结果。

这是错的。这就像是说：

有人告诉我，在打篮球的时候，你不能持球跑动。 我找了一个篮球并且试了一下，发现跑得很好。 那个人显然根本不懂篮球。

（这个解释由 Steve Summit 转述自 Roger Miller。）

当然，物理上你可以捡起一个篮球并持球跑动， 甚至在比赛期间你还可以拿着球逃出赛场。 然而，这违反了比赛规则，好的球员根本不会这么做， 而蔡的球员拿着球也逃不了多远就会被抓回来。 在 C 或 C++ 中计算 (INT_MAX+1) 是完全一样的： 它有时候可能工作，但不要以为你可以逃脱未定义行为。 这里的情况有些微妙，所以让我们详细考察一下它。

首先，有没有 C 实现能够保证带符号整数溢出具有 2-补码行为？ 当然是有的。许多编译器在不开优化时都具有这一行为， 而且 GCC 拥有一个选项（-fwrapv）可以在任何优化级别强制保证这一行为。 还有些编译器可能在任何优化级别都默认保持该行为。

同样，不言自明地，也会存在带符号整数溢出时并不具有 2-补码行为的编译器。 甚至还有一些编译器（比如 GCC）多年以来一直保持某种特定的带符号整数溢出行为， 然而某一天优化器变得稍微聪明了一些， 于是整数溢出突然无警告地停止按程序员期望的方式工作。 根据语言标准，这是完全正常的。尽管这对于开发者可能不友好， 但对于编译器团队来说这是一次胜利，因为编译器的性能测试分数得到了提高。

小结：持球跑动并不天生就是坏的， 就像将一个 32 位整数移 33 位也不是天生就有问题。 然而，前者违反了篮球的规则，后者违反了 C 和 C++ 的规则。 而设计这两种游戏的人已经确定了规则，我们要么遵守规则， 要么换一个游戏玩。

未定义行为有什么好处？

C/C++ 中未定义行为的好处 —— 唯一的好处！—— 就是能够简化编译器的工作， 使它能够在特定条件下生成非常高效的代码。通常来说，“特定条件”包括紧循环。 例如，高性能的数组代码不需要进行边界检查， 这样就不需要复杂的将这些检查提出循环的优化过程。 类似地，在编译一个递增带符号整数的循环时， C 编译器无需担心变量溢出并变成负数的情况。这使得一些循环优化成为可能。 我曾经听说一些紧循环在编译器被允许利用带符号溢出的未定义性质后， 能够加速 30% - 50%。类似的，一些 C 编译器允许使用选项， 将无符号整数溢出也规定为未定义的，以加速更多循环。

未定义行为有什么坏处？

当程序员无法保证自己能够准确地避免未定义行为的时候， 我们就会得到行为不正确且没有警告的程序。 这对于 web 服务器或浏览器等需要处理可能有恶意的数据的程序来说是严重的问题， 因为这些程序最后可能被破坏并开始执行从网线接收的恶意代码。 在许多情况下，我们实际上不需要利用未定义行为获得的性能增益， 但由于陈旧的代码和工具链，我们却不得不处理未定义行为的各种负面影响。

一个不太严重但令人恼火的问题是，有时只是为了简化编译器作者的工作， 就规定一个未定义行为，而且并不能由此得到任何性能增益。 例如，C 实现在以下情况具有未定义行为：

词法分析过程中，在一个逻辑代码行中遇到未配对的 ' 或 " 字符。

无意冒犯 C 标准委员会，但这真的纯粹是懒惰。 难道在引号不匹配时产生一个编译错误对于 C 编译器的实现者来说， 会造成无法承受的负担吗？即使是一个 30 年前（当时 C 刚刚被标准化） 的系统编程语言都可以做得更好。 有人怀疑 C 标准习惯于将行为扔进标着“未定义”的桶中，有些忘乎所以。 实际上，由于 C99 标准列出了 191 种不同的未定义行为，可以说他们非常忘乎所以。

从编译器的角度理解未定义行为

设计具有未定义行为的编程语言暗含的关键思想是， 编译器的义务只是考虑行为已有定义的情况。我们下面展示它引发的结果。

如果我们想象一个 C 程序正在被 C 抽象机执行，那么很容易理解未定义行为： 程序进行的每个操作要么是已定义的，要么是未定义的，通常很容易区分。 然而，在我们开始考虑一个程序所有可能的运行过程时，未定义行为就变得难以处理。 例如，应用程序开发者需要保证代码在所有情况下都是正确的，就要这样考虑。 同样，编译器作者需要保证对于所有可能的运行过程都生成正确的机器代码， 也要这样考虑。

讨论“程序的所有可能的运行过程”是有些棘手的，首先我们需要一些简化的假设。 第一，我们只考虑一个 C/C++ 函数，而不是整个程序。 第二，我们假设该函数对于所有输入都一定终止。 第三，我们假设该函数的执行是确定性的， 例如，它不会通过共享内存和其他线程通信。 最后，我们假设我们拥有无限多的计算资源，可以通过穷举法测试该函数。 穷举测试就是说使用所有可能的输入组合测试该函数，输入可能来自于参数， 或者全局变量、文件输入输出等其他的来源。

穷举测试算法是很简单的：

  1. 计算下一组输入，如果已经尝试了所有的输入组合，终止
  2. 使用这组输入，在 C 抽象机上执行该函数，记录是否有具有未定义行为的操作被执行
  3. 跳转到第 1 步

枚举所有输入并不是很难，我们从该函数接受的最小输入 （使用二进制位的个数衡量输入规模）开始，尝试具有最小规模的所有位模式， 然后再测试下一个可能的输入规模。这个过程可能终止，也可能不会， 但不用管它，反正我们拥有无限多的计算资源。

对于那些包含未指定或实现定义的行为的程序， 每个输入可能产生几种或许多种不同的执行过程。 本质上，这并不会使情况变得复杂。

我们的思维实验得到怎样的结论呢？现在我们可以知道，对于我们的函数， 它一定属于下列三类中的一类：

  • 第一类：对于所有输入，行为是已定义的
  • 第二类：对于一些输入，行为是已定义的，而对于其它输入是未定义的
  • 第三类：对于所有输入，行为都是未定义的

第一类函数

对于它们的输入不需要任何限制：它们对于所有可能的输入组合都表现良好 （当然，“表现良好”可能包括返回错误代码的情况）。 一般地，API 级别的函数和需要处理未经安全检查的数据的函数应该是第一类的。 例如，下面是一个绝对不会执行未定义行为的整数除法工具函数：

int32_t safe_div_int32_t (int32_t a, int32_t b) {
  if ((b==0) || ((a == INT32_MIN) && (b == -1))) {
    report_integer_math_error();
    return 0;
  } else {
    return a / b;
  }
}

由于第一类函数永远不会执行具有未定义行为的操作， 编译器有义务生成目标代码，使得无论函数输入如何，目标代码都会做一些合理的事。 我们不需要继续讨论这类函数。

第三类函数

这些函数根本没有良好定义的执行过程。严格地说，它们完全没有意义： 编译器甚至都不需要生成一条返回指令。这种函数真的存在吗？回答是肯定的， 而且事实上它们很常见。例如，很容易不小心写出一个使用变量却不初始化它的函数 —— 无论输入如何。编译器识别和利用这种代码进行优化的能力在不断提高。 下面是一个来自 Google Native Client 项目的绝妙例子：

在从可信代码向不可信代码返回时，我们必须对返回地址进行安全检查， 然后再使用该地址。 这保证不可信的代码不能通过系统调用接口将向量执行引导到任意地址。 这项工作由 sel_ldr.h 中的 NaClSandboxAddr 函数负责。 不幸的是，从 r572 开始，该函数在 x86 上不做任何事。

—— 发生了什么？

在一次日常的重构中，代码

aligned_tramp_ret = tramp_ret & ~(nap->align_boundary - 1);

被重构成了

return addr & ~(uintptr_t)((1 << nap->align_boundary) - 1);

除了变量的重命名（这是有意并正确的），我们引入了一个移位操作， 将 nap->align_boundary 当作 bundle 大小对 2 的对数。

我们没有注意到，因为 NaCl 在 x86 上使用 32 位 bundle 大小。 在 x86 和 gcc 编译器上，(1 << 32) == 1。（我记得标准规定这是未定义行为， 但可能我记错了。）因此，整个沙盒包装流程变成了空操作。

这项变更有四位评审人员，其中两位明确表示“代码看上去没有问题”。 没人注意到以上问题。

—— 影响

在 32 位 x86 上，不可信代码可能通过构造一个返回地址并进行系统调用的方式， 解除其指令流的对齐限制。这可能扰乱验证器。类似的安全缺陷可能影响 x86-64。

ARM 由于历史原因不受影响： NaCl 的 ARM 实现使用不同的方法对不可信返回地址施加位掩码。

发生了什么？一次简单的重构，将包含上述代码的函数变成了第三类。 发这封邮件的人认为 x86-gcc 将 (1<<32) 计算为 1， 但根本没有理由认为这个行为是可靠的 （实际上我在一些 x86-gcc 版本上测试的结果就与之不同）。 这个语言构造绝对是未定义的，编译器当然可以做任何它喜欢的事。 作为典型的 C 编译器，它选择完全不生成对应于未定义操作的指令。 （一个 C 编译器的第一目标是生成高效的代码。） 一旦 Google 程序员给了编译器杀人的许可，它马上就向前一步，开始杀人。 有人可能会问：如果编译器在发现第三类函数时给出警告或者类似的提示， 国安民乐，岂不美哉？说得没错，但是这并不是编译器的第一要务。

Native Client 是一个好的例子， 它展示了称职的程序员也会被优化编译器利用未定义行为的粗鄙方式坑害。 从开发者的角度来看， 一个能够非常聪明地识别并暗自摧毁第三类函数的编译器完全就是魔鬼。

第二类函数

这类函数对于一些输入具有已定义的行为，对于其他输入，行为则是未定义的。 这对于我们的教学来说是最有趣的。带符号整数除法就是一个很好的例子：

int32_t unsafe_div_int32_t (int32_t a, int32_t b) {
  return a / b;
}

该函数有一个前提条件，它只应该以满足下列条件的参数调用：

(b != 0) && (!((A == INT32_MIN) && (b == -1)))

不出所料，这和我们在第一类函数的例子中写的测试完全一样。 如果你调用函数时不满足这个前提条件，你的程序就会变得毫无意义。 那么写这样的，有非平凡的前提条件的函数是恰当的吗？ 通常来说，对于内部的工具函数，只要在文档中清晰地记录前提条件， 那就没有什么问题。

现在让我们看一下编译器在将该函数翻译成目标代码时会做什么。 编译器会进行分类讨论：

  • 情况 1：(b != 0) && (!((a == INT32_MIN) && (b == -1)))
    / 运算符的行为是有定义的 → 编译器必须生成计算 a/b 的代码
  • 情况 2：(b == 0) || ((a == INT32_MIN) && (b == -1))
    / 运算符的行为是未定义的 → 编译器没有义务考虑这种情况

现在编译器作者会问自己：对于这两种情况，最有效的实现是什么呢？ 由于对于情况 2 编译器没有任何义务，那么最简单的方法就是不考虑它。 编译器只要对于情况 1 生成代码就行了。

而 Java 编译器则不同，它对于情况 2 负有责任，必须处理它 （虽然在这个特例中，不会产生运行时的额外负担， 因为处理器一般都为除零提供了运行时陷阱）。

让我们再看一个第二类函数：

int stupid(int a) {
  return (a+1) > a;
}

该函数可以避免未定义行为的前提条件是：

(a != INT_MAX)

因此，C 或 C++ 语言的优化编译器会进行分类讨论：

  • 情况 1：a != INT_MAX
    + 的行为是有定义的 → 编译器必须返回 1
  • 情况 2：a == INT_MAX
    + 的行为是未定义的 → 编译器不需要做任何事

再一次地，情况 2 是退化的，编译器不会考虑它。既然只需要考虑情况 1， 一个好的 x86-64 编译器会输出：

stupid:
  movl $1, %eax
  ret

如果使用了 -fwrapv 选项告诉 GCC 保证整数溢出的 2-补码行为， 分类讨论就变得不同：

  • 情况 1：a != INT_MAX
    行为是有定义的 → 编译器必须返回 1
  • 情况 2：a == INT_MAX
    行为是有定义的 → 编译器必须返回 0

这样就不能消除分类讨论，编译器只好真的进行加法运算，再检查结果：

stupid:
  leal 1(%rdi), %eax
  cmpl %edi, %eax
  setg %al
  movzbl %al, %eax
  ret

类似地，一个超前编译的 Java 编译器也必须实际进行加法运算， 因为 Java 在带符号整数溢出时强制要求 2-补码行为 （我在使用生成 x86-64 目标代码的 GCJ）：

_ZN13HelloWorldApp6stupidEJbii:
  leal 1(%rsi), %eax
  cmpl %eax, %esi
  setl %al
  ret

对可能有未定义行为的情况进行分类讨论是解释编译器工作流程的优秀方式。 记住，编译器的主要目标是在遵守语言标准的前提下为你生成尽量高速的代码， 因此它们会尽快忘记关于未定义行为的任何事，而且不会告诉你发生了什么。

有趣的案例分析

大约一年前，Linux 内核开始使用一个特殊的 GCC 选项， 告诉编译器不要优化掉没用的空指针检查。导致开发者加入这一选项的代码类似 （我稍微清理了一下代码）：

static void __devexit agnx_pci_remove (struct pci_dev *pdev)
{
  struct ieee80211_hw *dev = pci_get_drvdata(pdev);
  struct agnx_priv *priv = dev->priv;

  if (!dev) return;

  ... do stuff using dev ...
}

这里的写法是，先获取一个指向某设备结构体的指针，检查它是否为空，再使用它。 但这里有个问题！在这个函数中，指针在空指针检查前被解引用了。 这导致优化编译器（例如 -O2 或更高优化级别下的 gcc）进行如下的分类讨论：

  • 情况 1：dev == NULL
    dev->priv 具有未定义行为 → 编译器不需要做任何事
  • 情况 2：dev != NULL 空指针检查不会失败 → 空指针检查是死码，可以删掉

我们可以看到，两种情况都不需要空指针检查。于是空指针检查被删掉了， 结果可能产生一个可以利用的安全缺陷。

当然，这里的问题是我们在检查 pci_get_drvdata() 的返回值之前就使用了它， 而且通过将使用移到检查后面已经修复了这个问题。但是，直到（人工或使用工具） 找出所有类似这样的代码之前，直接告诉编译器不要那么莽也可以让代码至少安全一点。 由于这里 CPU 分支预测可以发挥作用，效率损失可以忽略。 在内核的其他部分也找到了类似的代码。

在生活中应对未定义行为

长远地看，主流开发者在未来将不再使用不安全的编程语言， 但在高性能和低系统资源占用至关重要的场合仍然会被保留。 在当下，并没有非常直接的完全解决未定义行为的方法， 似乎最好的办法是采用下面的逐步修补的策略：

  • 启用并留心注意编译器警告，最好使用多个编译器
  • 使用静态分析器（例如 Clang 附带的，或者 Coverity，等等） 得到更多警告
  • 使用编译器支持的动态检查，例如 gcc 的 -ftrapv 选项生成在带符号整数溢出时陷入的代码
  • 使用 Valgrind 等工具进行更多动态检查
  • 在写出上述的“第二类”函数时，在文档中记录其前提条件和终止状态
  • 使用断言，验证函数的前提条件和终止状态被满足
  • 使用高质量的数据结构库，特别是对于 C++ 语言

简单来说：提高警惕，使用好的工具，并期望得到最好的结果。

第二篇

在类似于 GCC 边界检查功能、Purify、Valgrind 之类的工具最早出现时， 我们认为随便找一个 UNIX 工具程序，用它们运行，会非常有趣。 检查器的输出表明，这些工具程序尽管能够正常工作， 但却包含大量内存安全问题，例如使用未初始化数据、数组访问越界， 等等。仅仅运行 grep 或者别的什么工具就会触发数十个甚至数百个这类错误。

这是为什么呢？简单来说，C/UNIX 执行环境的某些特性恰巧使得这些错误 （通常是）非致命的。例如，malloc() 返回的内存块前后通常有填充空间， 这些空间可以吸收掉某些越界存储，只要不要越出太远。 那么还有必要消除这类 bug 吗？当然了。首先，在特性不同的执行环境中， 例如嵌入式系统的 malloc() 通常提供更少的填充空间， 此时非致命的略有越界的数组写入就会突然变成烦人的堆损坏 bug 。 其次，同一个 bug 可能在不同的情况下导致程序崩溃或者执行错乱， 即使运行环境不变。开发者一般会认为上述论证很有道理， 因此现在多数 UNIX 程序的 Valgrind 检查结果已经变得比较干净。

检查整数相关的未定义行为的工具并没有内存不安全行为的检查器那样完善。 C 和 C++ 中整数的恶劣行为包括溢出、除零、移位超过位数，等等。 近年来它们日益严重，原因是：

  • 整数相关的缺陷是重大安全问题的来源之一
  • C 编译器在利用整数未定义行为生成更高效的代码时变得相当激进

最近我的学生 Peng Li 写了一个检查整数未定义行为的工具。 我们使用它在许多程序中找到了相关的 bug ，例如半数以上的 SPECINT2006 基准测试执行一种或更多的整数未定义行为。在许多方面， 整数问题的现状就像 1995 年时内存问题的情况一样。 需要说明的是，整数检查工具一直存在，但它们并未被广泛使用， 而且大多数在二进制代码上进行检查，这已经太迟了。 实际上有必要在编译器有机会发现 —— 然后删除 —— 具有未定义行为的操作之前检查源代码。

这篇文章的剩余部分展示我们在 LLVM 中找到的一些整数未定义行为， 它是一个中等大小（约 800 千代码行）的开放源代码 C++ 代码库。 当然我并不是对 LLVM 挑剔：它的源代码质量很高。我们的想法是， 通过观察一些潜伏在这样经过仔细测试的代码中的问题， 或许可以学到如何在未来避免这类问题。

值得一提的是，如果我们认为 LLVM 代码是 C++0x 而非 C++98 ， 那么将会发现大量额外的移位相关的未定义行为。 我将会在下一篇文章中讨论 C++0x 对移位操作的新限制（和 C99 相同）。

我对工具的输出进行了简单的清理，以提高可读性。

整数溢出 #1

错误消息：

UNDEFINED at <BitcodeWriter.cpp, (740:29)> :
Operator: -
Reason: Signed Subtraction Overflow
left (int64): 0
right (int64): -9223372036854775808

代码：

int64_t V = IV->getSExtValue();
if (V >= 0)
  Record.push_back(V << 1);
else
  Record.push_back((-V << 1) | 1);

在所有 2-补码机器上运行的现代 C/C++ 变体中，对一个值为 INT_MIN 的 int 取负值（或者对于本例， 是值为 INT64_MIN 的 int64_t）都是未定义行为。 解决这一问题的方法是特判这种情况。

编译器会利用该未定义行为吗？会的：

[regehr@gamow ~]$ cat negate.c
int foo (int x) __attribute__ ((noinline));
int foo (int x)
{
  if (x < 0) x = -x;
  return x >= 0;
}

#include <limits.h>
#include <stdio.h>

int main (void)
{
  printf (“%d\n”, -INT_MIN);
  printf (“%d\n”, foo(INT_MIN));
  return 0;
}
[regehr@gamow ~]$ gcc -O2 negate.c -o negate
negate.c: In function ‘main’:
negate.c:13:19: warning: integer overflow in expression [-Woverflow]
[regehr@gamow ~]$ ./negate
-2147483648
1

在 C 编译器精神分裂的时候，-INT_MIN 既是负的又是非负的。 如果第一个真正的 AI 用 C 或 C++ 编写，我觉得它会直接推断出 “自由”就是“奴役”，“爱”就是“恨”，“和平”就是“战争”。

整数溢出 #2

错误消息：

UNDEFINED at <InitPreprocessor.cpp, (173:39)> :
Operator: -
Reason: Signed Subtraction Overflow
left (int64): -9223372036854775808
right (int64): 1

代码：

MaxVal = (1LL << (TypeWidth - 1)) - 1;

在 C/C++ 中这样计算最大的带符号整数值是非法的。 应该使用更好的方法，例如创建一个全 1 的值再清除其最高位。

整数溢出 #3

错误消息：

UNDEFINED at <TargetData.cpp, (629:28)> :
Operator: *
Reason: Signed Multiplication Overflow
left (int64): 142996016075267841
right (int64): 129

代码：

Result += arrayIdx * (int64_t)getTypeAllocSize(Ty);

这里分配的大小是合理的，但数组索引可能超过任何可想象的数组的边界， 结果导致溢出。

移位超过位数 #1

错误消息：

UNDEFINED at <InstCombineCalls.cpp, (105:23)> :
Operator: <<
Reason: Unsigned Left Shift Error: Right Operand is negative or is greater than or equal -
to the width of the promoted left operand
left (uint32): 1
right (uint32): 63

代码：

unsigned Align = 1u << std::min(BitWidth – 1, TrailZ);

这就完全是个 bug：BitWidth 被设定为 64，但其实应该是 32。

移位超过位数 #2

错误消息：

UNDEFINED at <Instructions.h, (233:15)> :
Operator: <<
Reason: Unsigned Left Shift Error: Right Operand is negative or is greater than or equal -
to the width of the promoted left operand
left (uint32): 1
right (uint32): 32

代码：

return (1<<(getSubclassDataFromInstruction() >> 1)) >> 1;

当 getSubclassDataFromInstruction() 返回一个 128-131 之间的值时， 左移操作符的右侧操作数会变成 32。 移位（无论朝哪个方向）的位数大于或等于整数位宽是一个错误， 因此该函数要求 getSubclassDataFromInstruction() 返回不超过 127 的值。

总结

通常来说，让程序做出错误的行为，而不通知开发者他们的代码做出了错误行为， 是非常恶劣的。C 的一项设计理念是“信任程序员”，但信任和信任是不同的。 比如，我信任我家 5 岁的小孩，但我不会让他自己穿过一条车水马龙的街道。 而用 C/C++ 写一大堆要求高可靠性或高安全性的代码完全就和闭着眼睛横穿 8 车道高速公路一样。

第三篇

一个 C 或 C++ 实现必须按照程序指定的次序执行有副作用的操作。 例如，如果一个程序执行下列代码行：

printf ("Hello\n");
printf ("world.\n");

那么像下面这样的输出是不行的：

world.
Hello

这很显然，但是请注意你的程序进行的其他操作可以被编译器随便重新排序。 例如，如果程序以某种顺序递增了一些变量：

a++;
b++;

则编译器可以产生以不同顺序递增它们的代码：

incl    b
incl    a

优化器在它认为可以提高性能，而且不会改变程序的可见行为时，会进行这种变换。 在 C/C++ 中，“可见行为” 是 “副作用” 的同义词。你可能会反对说 “这个重排序其实是可见的”，没错：如果 a 和 b 是全局变量， 则内存映射的输入输出设备、信号处理函数、 中断处理函数或另一个线程都可能发现 b 已经写入但 a 却没有的内存状态。 然而，这个重排序仍然是合法的，因为在语言中存储全局变量并未被定义成副作用。 （为了让事情变得更令人迷惑，标准说存储全局变量是副作用， 但没有真实存在的编译器这样认为。参阅本文最后的说明。）

有了这个看似不起眼的背景材料，我们可能会问： 段错误或者其他的崩溃在 C 和 C++ 中是具有副作用的操作吗？ 具体地说，如果一个程序因为执行除零或解引用空指针这样的非法操作而崩溃， 那么崩溃会被认为是副作用吗？答案是绝对否定的。

例子

由于造成崩溃的操作根本不是副作用，编译器可以将它们和其他操作重排序， 就像之前对 a 和 b 的存储被重排序一样。然而，真实的编译器会利用这一自由度吗？ 确实会。考虑下列代码：

volatile int r;

int s;

void foo1 (unsigned y, unsigned z, unsigned w)
{
  r = 0;
  s = (y%z)/w;
}

foo1 首先写入 r，这是有副作用的操作，因为 r 是 volatile 变量。 之后 foo1 计算一个表达式并且存储结果到 s。 赋值表达式的右边有执行具有未定义行为的操作的可能性：除零。 在绝大多数系统上这导致程序触发数学异常并崩溃。

下面是最近版本的 GCC 输出的结果：

foo1:
  pushl   %ebp
  xorl    %edx, %edx
  movl    %esp, %ebp
  movl    8(%ebp), %eax
  divl    12(%ebp)        # <-- 可能导致程序崩溃
  movl    $0, r           # <-- 具有副作用的操作
  movl    %edx, %eax
  xorl    %edx, %edx
  divl    16(%ebp)
  popl    %ebp
  movl    %eax, s
  ret

注意一条 divl 指令 —— 如果除数为 0 会杀死程序 —— 在对 r 的存储之前。 Clang 的输出也差不多：

foo1:
  pushl   %ebp
  movl    %esp, %ebp
  movl    8(%ebp), %eax
  xorl    %edx, %edx
  divl    12(%ebp)        # <-- 可能导致程序崩溃
  movl    %edx, %eax
  xorl    %edx, %edx
  divl    16(%ebp)
  movl    $0, r           # <-- 具有副作用的操作
  movl    %eax, s
  popl    %ebp
  ret

Intel CC 的输出也一样：

foo1:
  movl    8(%ebp), %ecx
  movl    4(%esp), %eax
  xorl    %edx, %edx
  divl    %ecx            # <-- 可能导致程序崩溃
  movl    12(%esp), %ecx
  movl    $0, r           # <-- 具有副作用的操作
  movl    %edx, %eax
  xorl    %edx, %edx
  divl    %ecx
  movl    %eax, s
  ret

对于编译器而言，这里的问题是在 foo1 的第一行和第二行之间没有依赖关系。 因此，编译器在有合适理由时可以随便重排它们。当然，宏观来看，它们有依赖关系： 因为在重拍后如果对 s 进行赋值时导致程序崩溃，则与 r 相关的计算就不会执行。 但是 —— 正如平常一样 —— C/C++ 标准制定规则，编译器只是遵守规则。

另一个例子

下列 C 代码调用一个外部函数，然后进行一些数学运算：

void bar (void);

int a;

void foo3 (unsigned y, unsigned z)
{
  bar();
  a = y%z;
}

Clang 会在函数调用之前进行数学运算：

foo3:
  pushl   %ebp
  movl    %esp, %ebp
  pushl   %esi
  subl    $4, %esp
  movl    8(%ebp), %eax
  xorl    %edx, %edx
  divl    12(%ebp)         # <-- 可能导致程序崩溃
  movl    %edx, %esi
  call    bar              # <-- 可能有副作用
  movl    %esi, a
  addl    $4, %esp
  popl    %esi
  popl    %ebp
  ret

为了拼凑一个完整的程序，我们可以写出：

void bar (void)
{
  setlinebuf (stdout);
  printf ("hello!\n");
}

int main (void)
{
  foo3 (1, 0);
  return 0;
}

下面我们可以编译并运行它：

regehr@john-home:~$ clang -O0 biz_main.c biz.c -o biz
regehr@john-home:~$ ./biz
hello!
Floating point exception
regehr@john-home:~$ clang -O1 biz_main.c biz.c -o biz
regehr@john-home:~$ ./biz
Floating point exception

正如我们通过观察 foo3() 的汇编代码预测的那样， 在优化启用时，除法指令在无缓冲的 printf() 之前导致程序崩溃。

这有什么关系？

前面的例子应该比较显然了，但我还是会再明确地说明一下。 比如说你正在调试一个奇怪的段错误：

  1. 你在调用 foo() 前加了一个 printf() 这里 foo() 是一堆复杂的包含可疑的指针操作的逻辑。 当然 —— 正如我们在之前的例子中做的那样 —— 你会关掉 stdout 的缓冲， 保证在程序继续执行前输出行会被实际推送到终端。
  2. 你运行程序，发现在段错误之前 printf() 没有执行。
  3. 你断定 foo() 没有引起崩溃，崩溃必然是之前的代码导致的。

如果 foo() 中的一些危险操作被移动到 printf() 之前， 然后触发段错误，步骤 3 的推导就是错的。 当你在调试中进行这样的错误推导时，就会南辕北辙，可能浪费大量时间。

解决方案

如果你遇到了这类问题，或者担心它的发生，你应该怎么做呢？ 显然，可以关掉优化或者单步执行程序。但是，对于嵌入式系统开发者， 这两种方法可能都不能用。

一种仍然出人意料地失败的解决方法是添加编译器屏障。 这种方法把 foo1 改为：

void foo2 (unsigned y, unsigned z, unsigned w)
{
  r = 0;
  asm volatile ("" : : : "memory");
  s = (y%z)/w;
}

新加的一行是 GCC 的一种惯用法（Intel CC 和 Clang 也能识别它）， 它意味着“这行内嵌汇编虽然没有指令，但可能修改整个内存。” 它的效果基本就是为代码强行增加大量的依赖关系， 保证在它之前所有寄存器值被保存到内存中，在它之后再重新加载。 新的代码使得 Intel CC 和 GCC 在计算 s 的右侧的任何表达式之前完成对 r 的存储，但 Clang 却不管它，生成代码：

foo1:
  pushl   %ebp
  movl    %esp, %ebp
  movl    8(%ebp), %eax
  xorl    %edx, %edx
  divl    12(%ebp)         # <-- 可能导致程序崩溃
  movl    %edx, %eax
  xorl    %edx, %edx
  divl    16(%ebp)
  movl    $0, r            # <-- 有副作用的操作
  movl    %eax, s
  popl    %ebp
  ret

我认为 Clang 在正确工作。编译器屏障增加了一些额外的依赖关系， 但它们不足以防止除法指令被移动到存储 volatile 变量之前。

问题的真正解决方案 —— 非常好理解， 但对于我们这些必须使用 C 和 C++ 的人并没有什么用 —— 是为除零和解引用空指针等异常情况指定语义。 只要语言作出规定，就能限制优化器对操作进行可能有危险的重排。 Java 在这方面就做得很好。

关于 C 和 C++ 中副作用的技术说明

C99 标准说：

访问 volatile 对象，修改对象，修改文件，或调用进行上述操作的函数， 都是副作用，它们可能改变运行环境的状态。

在 C 标准中 “对象” 就是 “变量”。C++0x 草案包含了非常类似的定义。 “修改对象” 的条款根本没有道理，它 —— 和顺序点语义结合起来 —— 会禁止编译器消除类似下面的程序包含的冗余存储操作：

x = 0;
x = 0;

没有 C 或 C++ 优化编译器会认为“修改对象”具有副作用。

挑剔地说，由于函数内联，“调用进行上述操作的函数” 也经常被忽略。 内联函数中的代码可能具有副作用，但函数调用本身却并不被视为副作用。

2010 年 8 月 19 日的更新

CompCert 是现有的，最实际的，经过形式化验证的 C 编译器， 它是一项令人惊叹的工作。我花了一些时间试图让它产生前文展示的那种目标代码 —— 一些危险操作被移动到有副作用的操作之前 —— 结果我失败了。 CompCert 项目的负责人 Xavier Leory 对我说：

实际上，您正在接触一个比较深层次的语义问题。

我们都认同，C 编译器不需要考虑未定义行为： 一个数组越界的源程序运行时未必崩溃。 人们可以为此感到遗憾（如果数组越界时程序直接崩溃，可以避免许多安全漏洞）， 但我们基本上认为，考虑未定义行为的代价太高了 （需要引入数组边界检查之类的东西）。

现在，一个只考虑已定义的行为的编译器有两种可选策略：

1- 如果源程序触发了未定义行为，编译出的代码可以做任何事。

2- 如果源程序触发了未定义行为， 编译出的代码需要像未定义行为之前的源代码指定的那样执行， 并产生可观测的效应，然后可以做任何事（崩溃或者继续执行并产生任意效果）。

如果我正确地理解了您的文章，您应该是看到了选择 1，并指出选择 2 不仅更加直观，而且在调试时更有帮助。我觉得自己同意您的观点， 但一些编译器作者真的喜欢选择 1 ……

对于 CompCert，我已经证明的高阶正确性定理都是第 1 类的： 如果源程序有错，那么不会保证编译出的代码的任何行为。 但是，我通过逐步模拟构造的一些引理实际上证明了上面的第 2 类行为： 编译出的代码不能比源代码“更早”崩溃，而且崩溃前必须产生相同的可观测效果， 之后可能再产生一些可观测效果。所以或许我应该加强我的高阶正确性定理 ……

考虑“什么是可观测的”这一问题，我认同您的观点，即 C 标准在胡说八道： 写入非 volatile 变量显然是不可观测的，调用函数也是不可观测的 （只有函数中可能进行的系统调用可观测）。

所以我们得到了结论：CompCert 可被证明没有这类问题， 但证明方式比较复杂。在后续的邮件中 Xavier 提到他正在考虑如何加强 CompCert 的高阶定理，以证明这种问题不会发生。很好！

Undefined Behavior Series
John Regehr
John Regehr
Professor