C/C++未定义行为指南 #1
本文翻译自John Regehr的博文 “A Guide to Undefined Behavior in C and C++, Part 1”，原文发布于2010年7月9日，链接见文末。
正文
编程语言通常会区分正常操作和错误操作。对于图灵完备的语言，我们无法可靠地仅凭源代码判断程序是否会出错，只能运行程序，然后查看结果。
在安全的编程语言中，错误会在发生时被捕获。例如，Java利用其异常系统保证了大部分情况下的安全。而不安全的编程语言不会捕获错误。相反，程序会悄悄地继续运行，直到刚才的错误操作导致了明显的后果。Luca Cardelli关于类型系统的文章对这些问题进行了清晰的介绍。C和C++浑身上下都散发着不安全的气息：错误的操作不仅会导致结果不可预测，甚至会导致整个程序最终毫无意义。在C和C++中，这些错误的操作被称为“未定义行为 (undefined behavior)”。
《C语言常见问题集》是这样定义“未定义行为”的：
未定义意味着任何事情都可能发生，标准在任何情况下都不强加要求。
程序可能无法编译；也可能无法正确执行——程序崩溃，或者默默地产出了错误的结果；亦或是偶然按照程序员的意图“正确”执行了。
这是一个很好的总结。几乎每个C/C++程序员都知道解引用空指针和除以零是错误的操作。但是，未定义行为更深层的含义，以及它和那些激进的编译器的交互方式，还有待进一步的发掘。而这正是本文的主题。
未定义行为的模型
现在，让我们忘记编译器，只关注“C实现”。它必须符合C标准，在执行符合C标准的程序时，行为与“C抽象机”相同。C抽象机是C标准中描述的C语言解释器。我们用C抽象机来确定任意C程序的含义。
程序由一些简单的步骤组成，例如把两个数相加，或者跳转到某个标签。如果程序中每个步骤的行为都有明确定义，那么整个程序的执行过程就是明确定义的。注意，由于未指明行为(unspecified)和实现定义行为(implementation-defined)的存在，程序执行的结果可能不是唯一的，我们暂时忽略这两个因素的存在。
如果程序中任意步骤具有未定义的行为，那么整个执行过程都是没有意义的。这一点很重要：并不是说对表达式(1 << 32)求值会得到不可预测的结果，而是说求值这个表达式的程序是没有意义的。此外，也不是说在未定义行为发生之前，程序的执行就有意义：不良影响可能先于导致未定义行为的操作产生。
例如如下程序：
这个程序向C实现提出了一个小问题：如果在int能表示的最大值上再加1，它会变成负数吗？而对于C实现而言，以下行为当然是合法的：
以下行为也是合法的：
还有这个：
甚至这个：
有人可能会说：这其中某些编译器的行为不正确！因为C语言的比较运算符只能返回0或者1。但是请别忘了，这段程序毫无意义，实现可以为所欲为。未定义行为压倒C抽象机的其他所有行为。
一个真正编译器会产出代码来粉碎你的磁盘吗？当然不会。但请铭记在心：未定义行为往往导致坏事，安全漏洞往往始于一个引发未定义行为的内存操作或整数运算。例如，访问越界的数组元素是典型的栈粉碎攻击的关键步骤。总之，编译器无需产出代码来格式化你的硬盘。相反，在你访问了越界的数组元素之后，电脑将开始执行利用这些漏洞的代码，然后格式化你的硬盘。
不要“走步”
人们常说，或者至少认同这样的话：
Ｃ语言的有符号加法是用x86 ADD指令实现的，结果溢出时会遵循补码的运算规则。而我恰好在x86平台开发，所以我能期待32位有符号整数溢出时的补码语义。
但这是错的。你就像是在说：
有人跟我说打篮球的时候不能抱着球跑。我买了个球试了一下，我不仅能抱着球跑，还能唱跳rap《只因你太美》。这人到底懂不懂篮球啊？
物理规则当然允许你抱着篮球到处跑，你甚至能在篮球比赛的时候走步还逃过裁判的法眼。但这违反了篮球规则。好球员不会这样做，而坏球员也并不能总是逍遥法外。在C和C++中对(INT_MAX+1)求值是一样的道理：你可能侥幸观察到了补码行为，但别期待每次都能这样。而实际情况往往更加微妙，所以我们来看看更深入的细节。
首先，是否存在某个C实现保证有符号整数运算溢出时，按补码规则处理？答案是肯定的。许多编译器在关闭优化的时候都确保这种行为。而GCC则可以通过编译选项(-fwrapv)在所有优化级别强制执行这种行为。甚至有的编译器默认在所有优化等级都执行这种行为。
但是不用说，还有一些编译器没有针对有符号整数算术溢出的补码行为。甚至于某些编译器，例如GCC，多年以来一直以某种方式实现整数溢出行为，突然有一天，优化器变得聪明了一点，这种行为就悄无声息地改变了。这对开发者来说有点不友好，但编译器团队却觉得这是一次胜利，因为编译器的跑分提高了。
总结：带球走没有什么本质上的坏处，把一个32位数字左移33位也没有什么本质上的坏处。但前者违反了篮球规则，而后者违反了C/C++的规则。不论如何，游戏的设计者制定了规则，要么你遵守他们的规则，要么你另起一套你更喜欢的规则。
未定义行为的好处
未定义行为唯一的好处，就是简化了编译器的工作，使得它可以在特定的情况下产出非常高效的代码。这些情况通常涉及紧凑的循环。例如，高性能数组操作可以无需边界检查，避免了棘手的多轮优化来将这些检查提升到循环之外。类似地，当编译一个不断递增有符号整数的循环时，编译器无需担心变量溢出然后变成负数的情况：这有利于多种循环优化的手段。据说在允许编译器利用有符号整溢出的未定义行为时，可将某些紧凑循环的速度提高30%到50%。类似地，甚至有编译器可以为无符号数溢出提供未定义语义，从而加速其他循环。
未定义行为的坏处
当一个不受信任的程序员无法有效避免未定义行为时，我们最终会得到一个默默执行错误操作的程序。这对于Web服务器和浏览器等程序来说是个非常棘手的问题。因为他们时常遭受恶意数据攻击，最终败下阵来，开始执行顺着网线爬进来的恶意代码。实际上，大多数情况下我们无需为了提高一点点性能而利用未定义行为。但是因为历史遗留的代码和工具链，我们不得不忍受这令人讨厌的后果。
而另一个不太严重但颇为恼人的问题是，某些未定义行为真的就只是让编译器的工作变简单了一点，而对提升性能没有任何帮助。例如C标准就规定遇到以下情况时程序的行为未定义：
标记化期间，在源代码的逻辑行中遇到了不匹配的单引号或双引号。
恕我直言，C标准委员会就是懒。在编译期检查出未匹配的引号并给出错误信息能给编译器带来多大的负担？三十年前开发的系统语言也比这做得好。有人怀疑委员会只是习惯于把各种行为扔进“未定义”的桶里，还对此自鸣得意。事实上，自C99以来，标准中已经列出了191种未定义行为，委员会确实有些得意忘形了。
编译器眼中的未定义行为
洞悉设计一门含有未定义行为编程语言的关键，就是编译器只需考虑行为已定义的情况。让我们接下来讨论这一点。
假设有一个运行在C抽象机上的C程序，未定义的行为很容易理解：程序执行的每个操作要么是已定义的，要么是未定义的，并且很容易区分。但是，当我们开始关注程序所有可能执行的路径时，未定义行为就变得难以处理了。应用程序开发者需要关注这一点，以确保程序在任何情况下都执行正确，编译器的开发者也是一样，他们需要保证编译器产出的机器码能在任何条件下正确执行。
讨论一个程序所有可能的执行路径有点棘手，让我们稍微做一点简化的假设。首先，我们将讨论单个C/C++函数而不是整个程序。其次，我们假定函数对任意输入都会终止执行。第三，我们假设函数的执行过程是确定的，例如它不会通过共享内存与其他线程交互。最后，假设我们有无限的计算资源，从而可以对函数进行详尽地测试。详尽的测试意味着所有可能的输入都会被考虑，不论他们来自参数、全局变量、文件I/O还是其他。
测试方法很简单：
计算下一个输入，如果所有的输入都已经过测试，就终止；
使用当前输入，在C抽象机中执行这个函数，观察程序是否会触发未定义行为；
回到第一步；
穷举所有输入不算太难。从函数可接受的最小的输入开始（以位为单位），尝试当前大小的所有位模式，然后开始尝试下一个大小。这个过程可能会终止，也可能不会终止，但这并不重要，因为我们拥有无限的计算资源。
对于包含未指定行为和实现定义行为的程序，每个输入都可能导致几个或更多可能的执行路径，但这并未从根本上增加复杂度。
那么，我们的思想实验得出了什么样的结果呢？能将我们的函数分类到一下三种的其中之一：
第一类：对于所有输入都具有明确定义的行为；
第二类：对于部分输入有明确定义，而另一部分输入则未定义；
第三类：对于所有输入都有未定义行为；
第一类函数
这些函数对输入没有任何限制：他们对所有可能的输入都是良定义的。当然，良定义也包括对错误的输入返回相应的错误代码。通常来说，API级别的函数和接收未经处理的数据的函数应该是第一类。例如下面这个用于计算整数除法而不会引发未定义行为的实用函数：
鉴于第一类函数从不执行未定义行为的操作，因此编译器理应生成执行合理操作的代码，不论函数的输入如何。我们无需进一步考虑这类函数。
第三类函数
这些函数不会执行任何良定义的行为。严格来说，他们完全没有意义：编译器甚至可以不产生返回指令。那这种函数真的存在吗？当然存在，并且很常见。例如，你很容易在无意中写出一个函数，它的某个局部变量没有初始化。好在编译器识别这种代码的能力正在变得越来越强。而其中一个反面教材就是Google Native Client项目：
当从可信代码返回到不可信代码时，我们必须在获取返回地址之前检查它。这确保了不受信任的代码不能利用系统调用来引导执行到任意地址。这项任务被托付给了NaClSandboxAddr函数，声明于sel_ldr.h中。不幸的是，自r572以来，这个函数在x86上一直是无操作的。
——起因——
在一次例行重构时，有如下代码：
被改成了如下代码：
除了重命名变量之外，还引入了一个左移操作，将nap->align_boundary视为包大小以2为底的对数。
但我们没有注意到的是x86上的NaCl包大小为32字节。在x86上使用GCC编译时，(1 << 32) == 1。我没记错的话，标准将这一行为视为未定义。如此一来，整个沙盒序列都变成了无操作。
这项变更有四名在列的代码评审员，并且通过了两轮LGTM分析，似乎没有人注意到这一变化。
——影响——
在32位x86上，不受信任的代码有可能通过构造返回地址和进行系统调用来取消其指令流的对齐。这可能绕过验证器。类似的漏洞也可能影响x86_64。
由于历史原因，ARM不受影响：ARM实现使用不同的方法屏蔽了不受信任的返回地址。
你看！一个简单的重构就把包含这段代码的函数打入了第三类。上述引文的作者认为x86-gcc将(1<<32)求值为1，但你没有理由认为这种行为是可靠的。事实上我尝试过数个版本的x86-gcc，都没有复现该行为。这个表达式当然是未定义的，编译器也可以做它想做的任何事。与普通的C编译器一样，gcc选择不产出任何指令。编译器的第一要义是产出高效的代码。一但这位谷歌程序员放开了牵着编译器的缰绳，编译器就会一路向前，哪怕前方是万丈高崖。也许有人会问：如果编译器检测到第三类函数就发出警告或者类似的提示不就好了吗？那固然好，但这不是编译器优先事项。
Google Native Client的例子很好的展示了优秀的程序员是如何被优化编译器利用未定义行为的卑鄙手段诱惑的。在程序员眼中，能识别并悄悄破坏第三类函数的编译器，已经聪明到近乎邪恶了。
第二类函数
这些函数对于某些输入是有定义的，而对其他输入则行为未定义。就本文的目的而言这类函数是最有趣的。有符号整数的除法就是个很好的例子：
这个函数有一个先决条件，只能使用满足下列表达式的参数调用它：
这个表达式看起来很像第一类函数的那个例子中的测试条件，这并非巧合。如果作为调用者的你违反了这个条件，你的程序就失去了它的意义。写出这样具有非平凡先决条件的函数是可行的吗？一般来说，对于内部使用的工具函数，只要在文档中详细说明先决条件，使用这样的函数是完全没问题的。
现在让我们来看看编译器在将这个函数翻译成目标代码时的工作。编译器会作出如下情景分析：
情形一：(b != 0) && (!((a == INT32_MIN) && (b == -1)))，除法运算是有定义的，编译器应该产出相应的代码来计算a/b；
情形二：(b == 0) || ((a == INT32_MIN) && (b == -1))，除法运算的行为未定义，编译器不作出任何保证；
现在轮到编译器的开发者思考了：如何才能高效地兼顾两种情形呢？最简单的方法就是，不考虑情形二！因为编译器无需给出任何保证，只要产生能处理情形一的代码即可。
作为对比的是Java编译器，必须对情形二作出保证，并且处理这种情形。虽然在这个例子中，这几乎不会增加运行时开销，因为现代处理器通常提供硬件级除以零的错误捕获功能。
再来看看另一个第二类函数的例子：
避免此函数引发未定义行为的先决条件是：
编译器同样会进行情景分析：
情形一：(a != INT_MAX)，加法操作是有定义的，编译器保证返回值为1；
情形二：(a == INT_MAX)，加法操作行为未定义，编译器不作出任何保证；
同理，情形二会在编译器的分析过程中退化并消失，只考虑情形一。于是一个优秀的x86-64编译器会产出如下汇编代码：
如果我们通过-fwarpv选项告诉GCC，整数溢出按照补码规则处理，我们就会得到不同的情景分析：
情形一：(a != INT_MAX)为真，加法操作是有定义的，编译器保证返回值为1；
情形二：(a == INT_MAX)为真，加法操作是有定义的，编译器保证返回值为0；
在此情形下，编译器必须考虑两种情形。因此必须产出代码来执行加法操作并检查计算结果：
类似的，Java AOT编译器也必须执行加法操作，因为Java要求有符号整数溢出时，按照补码规则处理。我使用的是x86-64上的GCJ编译器：
这种通过情形分析来观察未定义行为的视角提供了一种解释编译器如何工作的强有力的方法。请记住，编译器的主要目标是在标准条款的限制下，为你提供尽可能高效的代码。因此它们会尽力忽略未定义行为的存在，而且不会告诉你。
一个有趣的情景分析
大约一年前，Linux内核开始使用一个特殊的GCC编译选项来告诉编译器避免优化掉无用的空指针检查。迫使开发人员使用这个编译选项的代码如下所示，我对代码做了一定程度的简化：
这里的惯用手法是先获取一个指向设备结构体的指针，检查它是否为空，然后再使用。但这段代码的问题是，指针在检查是否为空之间就被解引用了。这会导致编译器作出如下情景分析，尤其是开启了-O2或以上优化等级的GCC：
情形一：dev == NULL，则"dev->priv"的行为未定义，编译器不给出任何保证；
情形二：dev != NULL，则空指针检查是无效代码，那部分的代码被当成死代码移除；
不难看出，不论那种情形，都不需要空指针检查。而删除检查的代码则会产生可被利用的安全漏洞。
当然，问题的关键是pci_get_drvdata()函数的返回值在检查之前就解引用了，只需把解引用的代码移到空指针检查之后即可。但类似的代码不止一处，不论是用工具检查还是人工检查，在修复所有问题之前，告诉编译器保守一点总是更安全。像这样可被预测的分支导致的效率损失可以忽略不计。
生活在未定义行为中
从长远来看，不安全的编程语言不会成为主流程序员的选择，它们会被保留在需要高性能和低资源占用的关键地带。与此同时，与未定义行为打交道没有什么万全之法，凡事都得综合考虑，才是最好的：
开启并关注编译器警告，最好能使用多个编译器
使用静态分析器，来获取更多警告。例如Clang的静态分析器、Coverity等。
使用编译器内置的动态检查，例如GCC的-ftrapv选项可以产出捕获整数溢出的代码
使用Valgrind等工具进行额外的动态检查
当使用上述的“第二类”函数时，在文档中注明先决条件和后置条件
使用断言来验证函数的先决条件与后置条件的一致性
尤其是C++中，使用高质量数据结构库
最后：小心谨慎，善用工具，尽人事，听天命。
正文结束
原文链接：https://blog.regehr.org/archives/213
John Regehr
美国犹他大学教授，专注于计算机编译器正确性及未定义行为的研究。其编写的整数溢出检查器被合并入Clang的C编译器，其编写的C编译器模糊测试工具Csmith亦被广泛使用。
