What Every C Programmer Should Know About Undefined Behavior #2/3

Saturday, May 14, 2011
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html
翻译：李凯

在该系列的第一部分，我们讨论了什么是未定义行为，以及它如何使C和C++编译器产生比“安全”语言更高性能的应用程序。本文讨论什么是“不安全”C，以及未定行为引起的一些令人意想不到的影响。在第3部分，我们将会探讨友好的编译器如何做才能使一些令人意想不到的那些影响减少，尽管他们并不需要这样做。

我喜欢把这叫做"Why undefined behavior is often a scary and terrible thing for C programmers"

编译器优化的相互作用导致出乎意料的结果
一个现代化的编译器的优化单元按一定顺序执行许多优化方法。有时优化会被反复执行，或者执行顺序因为编译器的演进而变化。不同的编译器经常有本质上不同的优化方法。因为编译器是分阶段优化的，因此如果前一阶段的优化改变了代码则会产生突发的影响。

为了让这更形象化，我们来看一个简单的例子（从Linux内核曾经出现的一个漏洞简化而来）：

void contains_null_check(int *P) {
  int dead = *P;
  if (P == 0)
    return;
  *P = 4;
}

在这个例子中，这些代码很明确地检查了空指针。如果编译器在“Redundant Null Check Elimination”通过之前碰巧运行到“Dead Code Elimination”，那么我们将会看到代码将执行下面两步：
void contains_null_check_after_DCE(int *P) {

  //int dead = *P;     // deleted by the optimizer.
  if (P == 0)
    return;
  *P = 4;
}

然后：

void contains_null_check_after_DCE_and_RNCE(int *P) {
  if (P == 0)   // Null check not redundant, and is kept.
    return;
  *P = 4;
}

但是，如果优化器碰巧被设计成别的顺序，程序将会在DCE之前运行RNCE。如下两步所示：

void contains_null_check_after_RNCE(int *P) {
  int dead = *P;
  if (false)  // P was dereferenced by this point, so it can't be null 
    return;
  *P = 4;
}

然后dead code elimination运行：

void contains_null_check_after_RNCE_and_DCE(int *P) {
  //int dead = *P;
  //if (false)
  //  return;
  *P = 4;
}

对于许多程序员来说，从这个函数中删除空指针检测将会使他们非常吃惊（而且他们也许会给编译器提交一个bug：）然而，根据标准，“contains_null_check_after_DCE_and_RNCE” 和 “contains_null_check_after_RNCE_and_DCE” 都是 “contains_null_check” 完全有效的优化方法，而且这些所涉及到的优化方法对各种应用程序的性能都非常重要。

尽管这是一个非常简单的例子，但是这种情况在内联时总是发生：内联函数时往往会产生一些二次优化的情况。这意味着如果优化器决定内联一个函数，那么各种各样的本地优化行为都可以kick in，这样会改变代码的行为。根据标准，这些都是完全有效的，而且对在实际应用中的性能表现很重要。

不要把未定义行为和安全性搅在一起
C被广泛用来写安全性级别要求很高的代码，像内核、setuid 后台程序、web浏览器等等。这种语言面临这样一种问题，当有恶意的输入和bug时会导致各种各样的安全性问题。C语言有一个被广泛提及的优势-----很容易从代码中理解上下文。

然而，未定义行为把这种特性的优势丧失了。毕竟大多数程序员都认为“contains_null_check”会做一个空检查。然而这种情况并不十分可怕（如果通过了一个空检查，代码可能会在内存中冲突，这样相对容易调试），因为在相当大的范围内，C语言的碎片是被认为完全无效的。这种问题已经使得许多项目（包括Linux Kernel, OpenSSL, glibc等），甚至导致了CERT发布vulnerability note来对抗GCC（尽管我个人认为被广泛应用的优化的C编译器都容易受到它的攻击，并不仅仅是GCC）。

让我们来看一个例子。研究一下这段认真写下的C代码：

void process_something(int size) {
  // Catch integer overflow.
  if (size > size+1)
    abort();
  ...
  // Error checking from this code elided.
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

这段代码做了相应的检测，以确保有足够大的内存容下从文件中读取的数据（因为一个空的终止字节需要加进来），如果产生了整型数溢出错误就跳出。然而，这就是我们之前给出的例子，在那个例子中编译器被允许（有效地）优化这个检测。这意味着对编译器来说完全有可能把这段代码转变为如下:

void process_something(int *data, int size) {
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

当在一个64位平台上built时， “size”是INT_MAX（也许是硬盘上一个文件的大小）时，这非常有可能是一个可利用的bug。让我们来分析一下这是个多么严重的错误：一个代码审计师在阅读这个代码时会理所当然地认为这是一个正常的溢出检查。人们测试这个代码时会发现并没有错误，除非特别地只测试那个error path。这段安全码看起来已经运行了，直到有人进一步调试并发现这个漏洞。总的说来，这是一个令人惊讶并相当可怕的一类bug。幸运的是，在这种情形下，解决方法很简单，只要令"size == INT_MAX"或者类似的操作都可以。

事实证明，有很多原因可以说明整型数溢出是一个安全性问题。即使你在使用完全定义的整型运算（-fwrapv或无符号整型数），仍然有可能会出现一个完全不同的整型溢出bug类。幸亏这种类在代码中是可见的，有见识的安全审计员经常能意识到这种错误。

调试已优化的代码可能没有任何意义
一些人（比如喜欢看生成的机器代码的底层嵌入式程序员）在优化器一直开启的状态下进行他们所有的研发。因为代码在正在开发时经常有bug，这些人最终会看到数量及其大的意想不到的优化，这会在运行时导致调试程序非常困难。例如，在第一节的“zero_array”例子中偶然地忘记写“i=0”，这使得编译器完全地跳出循环（把zero_array编译为“return”）,因为它使用了一个未定义的变量。

另一个有趣的例子是使用（全局）函数指针时发生的。一个简化的例子如下所示：

static void (*FP)() = 0;
static void impl() {
  printf("hello\n");
}
void set() {
  FP = impl;
}
void call() {
  FP();
}

这可以优化为：

void set() {}
void call() {
  printf("hello\n");
}

这种做法是可以的，因为空指针的调用未定义，这允许它假设set()必须在call()之前调用。在这种情形下，开发人员忘了调用“set”，在引用空指针的情况下程序并没有崩溃，而当其他人运行debug时他们的代码会遭到破坏。

其结果是，这是一个可以解决的问题：如果你怀疑一些奇怪的事情会发生，可以尝试在-O0建立，在这里编译器不太可能进行任何优化。

当编译器演化或改进后，以前正常代码中使用未定义行为也许会异常
我们已经看过许多例子，在一个应用程序看起来能工作的时候，当一个新的LLVM用来建立应用程序或应用程序从GCC转移到LLVM时，就出问题了。尽管LLVM偶尔自身会有一两个bug，但是这种事情却会经常发生的，因为如今应用程序中的潜在错误被编译器暴露出来了。这可以以各种不同的方式产生，下面是两个例子：

一个未初始化的变量，被luck “before”初始化为0，现在它得到其他一些不是0的寄存器。这通常是由寄存器分配的变化而体现出来的。
一个堆栈中的数组溢出，是从那个实际中很重要的变量开始，还不是已经无用的变量。当编译器重新整理它往堆栈中存东西的方式，或者对于那些在运行时间的变量不重叠的变量，能更积极主动地获得共享堆栈空间时，它们才会体现出来。

一个很重要且很恐怖的事情将会显现，那就是在未来任何时间内任何基于未定义行为的优化都可能会触发buggy代码。内联，循环展开，等等其他优化方法会越来越好，它们存在的一个有意义的原因是像上面第一个一样体现二次优化。

对我来说，这是远远不能满足的，一部分原因是由于编译器最终都无可避免的会被指责，也有一部分原因是由于这意味着庞大的C代码等待着被摧毁。这甚至会更糟糕，因为……

没有可靠的方式来说明一个大型的代码库中是否有未定义行为
一个让这块“雷区”成为更糟糕的地方的事实是：现在没有一个好的方式来决定一个大型的应用程序是否有未定义行为，这种状况在未来也不容易打破。现在有许多工具能帮助找到一些bugs，但没有一个能有足够信心保证你的代码在将来不会中断。让我们来看一下其中一些options，并一起看一下它们的优点和弱点：

Valgrind memcheck tool是一种找到所有种类的未定义变量和内存bug的奇妙方法。由于Valgrind运行时非常慢，所以这种方法受到了限制，它只能找到还存在于生成的机器码中的bug（所以不能找到优化器去掉的bug），同时它不知道源语言是C语言（所以它不能找到移出范围的或有符号整数溢出的bug）。
Clang有一个实验性的-fcatch-undefined-behavior模式，这种模式通过运行时插入检查来找错误，比如移位超出范围，一些简单的数组越界等。这种方式因为降低了应用程序的运行速度而且不能解决随机指针的引用问题（Valgrind可以）而受到限制，但是它能找到其他重要的bug。Clang还完全支持-ftrapv标志（不要和-fwrapv弄混），这种标志能在运行时对有符号整型溢出bug设置陷阱（GCC也有这个标志，但是以我经验来看它完全不可靠）。下面是-fcatch-undefined-behavior的快速演示：
1. /* t.c */
2. int foo(int i) {
3. int x[2];
4. x[i] = 12;
5. return x[i];
6. }
7. int main() {
8. return foo(2);
9. }
1. $ clang t.c
2. $ ./a.out
3. $ clang t.c -fcatch-undefined-behavior
4. $ ./a.out
5. Illegal instruction
编译警告信息对找到一些类型的bug有帮助，比如未初始化变量和简单整型溢出bug。它有两个基本的限制条件：1）它没有代码在执行时的动态信息，2）它必须运行的很快，因为它做的任何分析都会降低编译时间。
Clang的静态分析器进行了更深入的分析来试图找到bug（包括未定义行为的使用，比如空指针调用）。你可以把它想像成产生编译器警告信息的模块，因为它不受正常警告的编译时间的限制。静态分析器的最基本的不足如下：1）当程序运行时它没有程序的动态信息，2）对许多开发者来说，它并不是被熟练使用的工具链（它被纳入LLVM "Klee" Subproject使用象征分析方法，通过一段代码来"试着找到各种可能的路径"，找到代码中的bug并产生一个测试用例。这是一个伟大的小项目，绝大多数时间段内，受限于不能有效地运行在大型应用程序上。
尽管我从来没有尝试过，Chucky Ellison 和 Grigore Rosu研究的C-Semantics tool非常有意思，这种工具能显著地找到某一类的bug（比如sequence point violations）。它目前仍然是一个研究课题，但是也许会在（小的并且self-contained）程序中找bug有用处。我推荐读一下John Regehr关于它的文章来获取更多的信息。

最终的结果是我们的工具箱中有许多方案可以找到一些bug，但是没有更好的方法来证明一个应用程序不受未定义行为的影响。在本系列的最后一部分，会总结当处理未定义行为时C编译器所可能考虑的各种选择，尤其是Clang。

Topic: sohulinux

What Every C Programmer Should Know About Undefined Behavior #2/3

最新评论

最新日志

Topic

我们俩的联系方式

订阅地址