Embedded in Academia

C 和 C++ 中 Undefined Behavior 指南，第一部分

另请参阅第二部分和第三部分。

编程语言通常会区分正常的程序行为和错误的行为。对于图灵完备的语言，我们无法可靠地离线判断一个程序是否有可能执行错误；我们必须运行它才能知道。

在一个_安全_的编程语言中，错误会在发生时被捕获。例如，Java 在很大程度上通过其异常系统是安全的。在一个_不安全_的编程语言中，错误不会被捕获。相反，在执行了一个错误的操作后，程序会继续运行，但以一种静默错误的方式，可能会在以后产生可观察的后果。Luca Cardelli 关于类型系统的文章对这些问题有一个清晰的介绍。C 和 C++ 在很大程度上是不安全的：执行一个错误的操作会导致整个程序变得毫无意义，而不仅仅是错误的操作产生不可预测的结果。在这些语言中，错误的操作被称为具有 undefined behavior（未定义行为）。

C FAQ 对“undefined behavior”的定义如下：

任何事情都可能发生；标准不施加任何要求。程序可能无法编译，或者它可能执行不正确（崩溃或静默地生成不正确的结果），或者它可能侥幸地完全按照程序员的意图执行。

这是一个很好的总结。几乎每个 C 和 C++ 程序员都明白，访问空指针和除以零是错误的行为。另一方面，undefined behavior 的全部含义及其与激进编译器的交互并没有得到充分的理解。这篇文章探讨了这些主题。

Undefined Behavior 的模型

现在，我们可以忽略编译器的存在。只有“C 实现”，如果实现符合 C 标准，那么在执行符合标准的程序时，它的行为与“C 抽象机”相同。C 抽象机是 C 标准中描述的 C 的简单解释器。我们可以用它来确定任何 C 程序的含义。

程序的执行包括简单的步骤，例如将两个数字相加或跳转到标签。如果程序执行中的每个步骤都有定义的行为，那么整个执行都是良好定义的。请注意，即使是良好定义的执行也可能由于未指定的和实现定义的行为而没有唯一的结果；我们在这里将忽略这两者。

如果程序执行中的任何步骤具有 undefined behavior，那么整个执行就毫无意义。这很重要：不是说评估 (1<<32) 会产生不可预测的结果，而是说评估此表达式的程序的整个执行都是毫无意义的。而且，不是说执行在 undefined behavior 发生之前是有意义的：不良影响实际上可能发生在未定义操作之前。

作为一个快速的例子，让我们来看一下这个程序：

**#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
Formatting root partition, chomp chomp**

有人可能会说：这些编译器中的一些行为不正确，因为 C 标准规定关系运算符必须返回 0 或 1。但是由于该程序根本没有任何意义，因此实现可以做任何它喜欢的事情。Undefined behavior 胜过 C 抽象机的其他所有行为。

真正的编译器会发出格式化磁盘的代码吗？当然不会，但请记住，实际上，undefined behavior 通常会导致糟糕的事情，因为许多安全漏洞都始于具有 undefined behavior 的内存或整数运算。例如，访问越界数组元素是典型的堆栈粉碎攻击的关键部分。总而言之：编译器不需要发出格式化磁盘的代码。相反，在进行 OOB 数组访问之后，您的计算机会开始执行利用代码，而该代码将格式化您的磁盘。

禁止带球跑

人们经常会说，或者至少会想到这样的话：

x86 ADD 指令用于实现 C 的有符号加法运算，当结果溢出时，它具有补码行为。我正在为 x86 平台开发，因此我应该能够在 32 位有符号整数溢出时期望补码语义。

这是错误的。你正在说这样的话：

有人曾经告诉我，在篮球比赛中你不能拿着球跑步。我拿了一个篮球并尝试了一下，它工作得很好。他显然不了解篮球。

（此解释归功于 Roger Miller，通过 Steve Summit。）

当然，在身体上可以拿起篮球并带着它奔跑。在比赛中你也可能侥幸成功。但是，这是违反规则的；优秀的球员不会这样做，而糟糕的球员也不会长时间侥幸成功。在 C 或 C++ 中评估 (INT_MAX+1) 完全相同：它有时可能会起作用，但不要期望一直侥幸成功。这种情况实际上有点微妙，所以让我们更详细地看一下。

首先，是否有 C 实现保证有符号整数溢出时的补码行为？当然有。例如，许多编译器在关闭优化时会具有此行为，并且 GCC 有一个选项 (-fwrapv) 用于在所有优化级别强制执行此行为。其他编译器默认会在所有优化级别都具有此行为。

同样不用说的是，也有一些编译器在有符号溢出方面没有补码行为。此外，还有一些编译器（如 GCC），在许多年中，整数溢出的行为方式是确定的，然后在某个时候，优化器变得更聪明了一点，并且整数溢出突然而悄无声息地停止了按预期工作。就标准而言，这完全可以。虽然这对开发人员可能不太友好，但编译器团队会认为这是一个胜利，因为它会提高基准分数。

总而言之：手里拿着球跑步本身并没有什么不好，将一个 32 位数字移动 33 位也没有什么不好。但是，前者违反了篮球规则，后者违反了 C 和 C++ 的规则。在这两种情况下，游戏的设计者都创建了任意规则，我们要么必须遵守这些规则，要么找到我们更喜欢的游戏。

Undefined Behavior 为什么好？

C/C++ 中 undefined behavior 的优点——也是唯一的优点！——是它简化了编译器的工作，从而可以在某些情况下生成非常高效的代码。通常，这些情况涉及紧密循环。例如，高性能数组代码不需要执行边界检查，从而避免了需要进行棘手的优化过程才能将这些检查提升到循环之外。类似地，在编译递增有符号整数的循环时，C 编译器不需要担心变量溢出并变为负数的情况：这有助于进行一些循环优化。我听说，当允许编译器利用有符号溢出的未定义性质时，某些紧密循环的速度会提高 30%-50%。类似地，有些 C 编译器可以选择性地为无符号溢出赋予未定义的语义，以加快其他循环的速度。

Undefined Behavior 为什么不好？

当程序员不能被信任以可靠地避免 undefined behavior 时，我们最终会得到静默地行为不端的程序。对于处理恶意数据的 Web 服务器和 Web 浏览器之类的代码来说，这已经变成了一个非常糟糕的问题，因为这些程序最终会被破坏并运行通过网络到达的代码。在许多情况下，我们实际上并不需要通过利用 undefined behavior 获得的性能，但是由于遗留代码和遗留工具链，我们仍然面临着不良后果。

一个不太严重的问题，更像是一种烦恼，是行为在某些情况下未定义，而在这些情况下，它所做的只是使编译器编写者的工作更容易一些，而没有获得任何性能。例如，当以下情况发生时，C 实现具有 undefined behavior：

在标记化期间，在逻辑源行上遇到不匹配的 ' 或 " 字符。

恕我直言，对于 C 标准委员会来说，这太懒惰了。要求 C 实现者在引号不匹配时发出编译时错误消息真的会给他们带来不适当的负担吗？即使是 30 年前（C99 标准化时）的系统编程语言也可以做得更好。人们怀疑 C 标准机构只是习惯于将行为扔进“未定义”的垃圾桶，并且有点得意忘形。实际上，由于 C99 标准列出了 191 种不同的 undefined behavior，因此可以公平地说他们有点得意忘形了。

理解编译器对 Undefined Behavior 的看法

设计具有 undefined behavior 的编程语言背后的关键见解是，编译器仅有义务考虑行为已定义的情况。现在，我们将探讨这其中的含义。

如果我们想象一个 C 程序由 C 抽象机执行，那么 undefined behavior 非常容易理解：程序执行的每个操作要么已定义，要么未定义，通常很清楚是哪种。当我们开始关注程序的所有可能执行时，undefined behavior 变得难以处理。需要代码在每种情况下都正确的应用程序开发人员关心这一点，需要发出在所有可能的执行中都正确的机器代码的编译器开发人员也关心这一点。

谈论程序的所有可能执行有点棘手，因此让我们做一些简化的假设。首先，我们将讨论单个 C/C++ 函数而不是整个程序。其次，我们假设该函数对每个输入都会终止。第三，我们假设该函数的执行是确定性的；例如，它不会通过共享内存与其他线程合作。最后，我们假装我们拥有无限的计算资源，从而可以穷尽地测试该函数。穷举测试意味着尝试所有可能的输入，无论它们来自参数、全局变量、文件 I/O 还是其他任何东西。

穷举测试算法很简单：

  1. 计算下一个输入，如果已经尝试了所有输入，则终止
  2. 使用此输入，在 C 抽象机中运行该函数，跟踪是否执行了任何具有 undefined behavior 的操作
  3. 转到步骤 1

枚举所有输入并不太困难。从函数接受的最小输入（以位为单位测量）开始，尝试该大小的所有可能的位模式。然后移至下一个大小。此过程可能会或可能不会终止，但这无关紧要，因为我们拥有无限的计算资源。

对于包含未指定和实现定义行为的程序，每个输入可能会导致几个或许多可能的执行。这并没有从根本上使情况复杂化。

好的，我们的思想实验完成了什么？我们现在知道，对于我们的函数，它属于以下哪个类别：

类型 1 函数

这些函数对其输入没有任何限制：它们对所有可能的输入都表现良好（当然，“表现良好”可能包括返回错误代码）。通常，API 级别的函数和处理未经清理数据的函数应为类型 1。例如，这是一个用于执行整数除法而不执行 undefined behavior 的实用程序函数：

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

由于类型 1 函数永远不会执行具有 undefined behavior 的操作，因此编译器有义务生成无论函数的输入如何都有意义的代码。我们不需要进一步考虑这些函数。

类型 3 函数

这些函数不承认任何良好定义的执行。严格来说，它们是完全没有意义的：编译器甚至没有义务生成返回指令。类型 3 函数真的存在吗？是的，而且实际上很常见。例如，无论输入如何，使用未初始化变量的函数很容易无意中编写。编译器在识别和利用这种代码方面变得越来越聪明。这是一个来自 Google Native Client 项目的很好的例子：

当从受信任的代码返回到不受信任的代码时，我们必须在获取返回地址之前对其进行清理。这确保了不受信任的代码无法使用 syscall 接口将执行矢量化到任意地址。此角色委托给 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 视为捆绑大小的 log2。 我们没有注意到这一点，因为 x86 上的 NaCl 使用 32 字节的捆绑大小。在带有 gcc 的 x86 上，(1 << 32) == 1。（我相信标准使此行为未定义，但我生疏了。）因此，整个沙盒序列变成了空操作。 此更改有四个列出的审阅人，并由两个显式 LGTM'd。似乎没有人注意到该更改。 -- 影响 32 位 x86 上的不受信任的代码有可能通过构造返回地址并进行 syscall 来取消对齐其指令流。这可能会破坏验证器。类似的漏洞可能会影响 x86-64。 由于历史原因，ARM 不受影响：ARM 实现使用不同的方法来屏蔽不受信任的返回地址。

发生了什么？一个简单的重构将包含此代码的函数置于类型 3。发送此消息的人员认为 x86-gcc 将 (1<<32) 评估为 1，但是没有理由期望此行为可靠（实际上，在我尝试过的几个版本的 x86-gcc 上并非如此）。这种构造绝对是未定义的，当然编译器可以做任何它想做的事情。与 C 编译器一样，它选择简单地不发出与未定义操作相对应的指令。（C 编译器的首要目标是发出高效的代码。）一旦 Google 程序员授予编译器杀戮许可证，它就继续杀戮。有人可能会问：如果编译器在检测到类型 3 函数时提供警告或类似的东西，那会不会很棒？当然！但这不是编译器的首要任务。

Native Client 示例是一个很好的示例，因为它说明了有能力的程序员如何被优化编译器以一种隐蔽的方式利用 undefined behavior 所欺骗。从开发人员的角度来看，一个非常擅长识别和静默销毁类型 3 函数的编译器实际上变得邪恶。

类型 2 函数

这些函数的行为对于某些输入已定义，而对于其他输入未定义。这是我们目的中最有趣的情况。有符号整数除法是一个很好的例子：

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

此函数具有一个前提条件；它只能使用满足此谓词的参数来调用：

**`(b != 0) && (!((a == INT32_MIN) && (b == -1)))`**

当然，此谓词看起来很像此函数的类型 1 版本中的测试并非巧合。如果您（调用者）违反此前提条件，则程序的含义将被破坏。编写像这样的具有非平凡前提条件的函数可以吗？通常，对于内部实用程序函数，只要清楚地记录了前提条件，这就可以。

现在让我们看一下编译器在将此函数转换为目标代码时的工作。编译器执行案例分析：

现在，编译器编写者问自己一个问题：这两个案例最有效的实现是什么？由于情况 2 不会产生任何义务，因此最简单的事情就是根本不考虑它。编译器可以仅为情况 1 发出代码。

相比之下，Java 编译器在情况 2 中具有义务，并且必须处理它（尽管在这种特殊情况下，很可能不会有运行时开销，因为处理器通常可以为整数除以零提供陷阱行为）。

让我们看一下另一个类型 2 函数：

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

避免 undefined behavior 的前提条件是：

**(a != INT_MAX)**

此处，优化的 C 或 C++ 编译器进行的案例分析是：

同样，情况 2 是退化的，并且从编译器的推理中消失了。情况 1 才是最重要的。因此，一个好的 x86-64 编译器将发出：

**stupid:
 movl $1, %eax
 ret**

如果我们使用 -fwrapv 标志告诉 GCC 整数溢出具有补码行为，我们将获得不同的案例分析：

在这里，案例无法折叠，编译器有义务实际执行加法并检查其结果：

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

类似地，提前 Java 编译器也必须执行加法，因为 Java 强制要求有符号整数溢出时的补码行为（我正在使用 GCJ for x86-64）：

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

这种对 undefined behavior 的案例折叠观点提供了一种强大的方法来解释编译器如何真正工作。请记住，他们的主要目标是为您提供遵守法律条文的快速代码，因此他们将尝试尽快忘记 undefined behavior，而不会告诉您发生了这种情况。

一个有趣的案例分析

大约一年前，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）执行以下案例分析：

正如我们现在可以轻松地看到的那样，这两种情况都不需要空指针检查。该检查被删除，从而可能产生可利用的安全漏洞。

当然，问题在于在检查之前使用了 pci_get_drvdata() 的返回值，必须通过将使用移至检查之后来解决此问题。但是在可以检查所有此类代码（手动或通过工具）之前，认为仅告诉编译器保守一些会更安全。由于像这样的可预测分支而导致的效率损失完全可以忽略不计。在内核的其他部分中也发现了类似的代码。

与 Undefined Behavior 共存

从长远来看，不安全的编程语言不会被主流开发人员使用，而是保留用于高性能和低资源占用至关重要的情况。与此同时，处理 undefined behavior 并非完全简单，一种拼凑方法似乎是最好的：

基本上：非常小心，使用好的工具，并希望一切顺利。 2010 年 7 月 9 日 regehr 计算机科学，软件正确性

29 条回复 “C 和 C++ 中 Undefined Behavior 指南，第一部分”

  1. Michael Norrish 说： 2010 年 7 月 9 日 上午 6:13 不错的文章！
  2. Eric LaForest 说： 2010 年 7 月 9 日 上午 6:56 引人深思的文章，谢谢。 但我很困惑：哪种类型的优化可以推断出 stupid() 或空指针检查的不确定性？我没听说过。 编译器根据它在编译时拥有的知识来决定做什么不是更好吗？ 例如：stupid(foo) 会编译完整的代码，而 stupid(5) 会像常量传播和表达式简化一样，编译成一个文字。 类似地，在 NULL 检查的情况下，为什么要麻烦呢？ dev 的值在编译时是未知的，并且在 NULL 的情况下，第一次解引用会触发段错误。
  3. regehr 说： 2010 年 7 月 9 日 上午 10:13 嗨，Eric - 我可能需要更新这篇文章，以使这些事情更清楚一点！ 我不认为这些优化有任何特定的名称，我也不认为它们写在教科书中。但基本上它们都属于“标准数据流优化”的范畴。换句话说，编译器会学习一些事实并传播它们，以便在其他地方进行更改。唯一的区别在于所学习事实的细节。 需要明确的是，这些优化绝对是基于编译器在编译时拥有的知识。我在这篇文章中描述的所有内容都只是一个普通的编译时优化。 stupid(foo)——其中 foo 是一个自由变量——使用案例分析编译为“return 1”。 关于空值检查示例，请记住这是在 Linux 内核中。在最好的情况下，访问空指针会导致计算机崩溃。在最坏的情况下，没有崩溃：当您访问空指针时，利用代码正在等待接管计算机。这正是内核程序员担心的情况。这不是理论：如果您的 Linux 内核访问了空指针，我可能会拥有您的计算机。
  4. Matthias Felleisen 说： 2010 年 7 月 9 日 上午 10:44 谢谢。 真正可悲的是，一些所谓的像 Scheme 这样的高级语言也有意包含未定义的行为。这可能使 Scheme 最终看起来像一种真正的系统语言。 长期以来，我一直在 PL 课程中宣扬“不安全和未定义福音”。的确，我已经宣讲了这么长时间，以至于以前的学生仍然穿着印有我的引言“Scheme 和 FORTRAN 一样糟糕”的 T 恤，这都是因为同样的问题。实际上，一些 HotSpot 编译器作者可能仍然拥有这件 T 恤。 可悲的是，我从未获得 Rice 的“真正”编译器同事或系统人员的支持。真正的人只会应付。闭嘴并工作。 因此，感谢您作为“系统”人员发声。
  5. regehr 说： 2010 年 7 月 9 日 上午 11:15 嗨，Matthias - 谢谢您的注意！ 我觉得某些语言是由编译器人员设计和为编译器人员设计的。优化好，其他一切：无关紧要。希望这些语言会丢失（或被修改）以应对机器资源相对便宜且程序错误相对昂贵的现代情况。当然，多核可能会在程序正确性方面使我们倒退几十年…… 得知 Scheme 的未定义行为让我感到非常惊讶。
  6. Matthias Felleisen 说： 2010 年 7 月 9 日 下午 12:23 您写道“当然，多核可能会在程序正确性方面使我们倒退几十年……” 多么悲伤，多么真实！ 就 Scheme 而言，幸运的是，编译器可以实现一种安全且确定的语言，这正是 Matthew 的 PLT Scheme 所做的，也是 Racket 现在所做的。可悲的是，编译器编写者喜欢不确定的规范，他们更喜欢编写语言规范。也许后者是我们永远无法摆脱这些糟糕语言的真正原因。
  7. Adam Morrison 说： 2010 年 7 月 10 日 下午 12:20 我不确定 Google Native 客户端示例。在我看来，编译器发出了 x86 代码，该代码在传递 32 作为输入时，将计算 (1<<32) == 1。 碰巧的是，此函数始终使用 “bundle_size” 作为 32 调用，因此它在语义上变成了空操作。它没有像应该的那样屏蔽掉地址的低位。
  8. Ben L. Titzer 说： 2010 年 7 月 12 日 下午 5:43 尽管我完全同意使程序的语义尽可能明确（当然与实现和目标机器无关）的想法，但总会有漏洞可以钻。例如，大多数语义都假设目标机器有足够的资源来实际运行该程序。当然，然后他们定义如果机器没有足够的资源会发生什么——OutOfMemoryError、StackOverFlowError 等。但是，当机器 几乎 有足够的资源时，该怎么办？然后，可以感受到优化的影响。例如，类元数据占用了多少堆？即使具有相同的堆大小，相同的程序也可能运行完成（或继续工作），或者在不同的 VM 上引发 OutOfMemory。堆栈大小也是如此——如果编译器或 VM 执行尾递归消除，则程序可能运行良好，但在没有尾递归消除的情况下立即失败（请注意，没有符合标准的 JVM 这样做）。 尽管可以定义语义为非确定性的，但为了使某些部分不确定而费力地正式定义它们是不寻常的。我们尝试根除它，但非确定性不断涌入，就像 Java 中的这些选择示例一样：