C、C++中未定義行為的指引， 第1部分

作者：John Regehr

原作：http://blog.regehr.org/archives/213

程式設計語言通常區分正常的程式活動與錯誤的活動。對于圖靈完備語言，我們無法可靠地離線确定一個程式是否潛在執行一個錯誤；我們必須運作它來看一下。

在一個安全的程式設計語言中，錯誤在發生時被捕捉。例如，通過其異常系統，Java大體上是安全的。在一個不安全的程式設計語言中，錯誤不被捕捉。相反，在執行一個錯誤操作後，程式繼續運作，但以一個靜默、錯誤的方式，稍後可能有可觀察的後果。Luca Cardelli關于類型系統的論文對這些問題有一個非常清晰的介紹。C與C++在很大程度上是不安全的：相對于讓錯誤操作有一個不可預測的結果，執行一個錯誤操作使得整個程式變得沒有意義。在這些語言中，錯誤操作被稱為具有未定義行為（undefined behavior）。

C FAQ這樣對于“未定義行為”：

任何事情都可能發生；标準沒有強加任何要求。程式可能編譯失敗，或者它可能執行不正确（要麼崩潰，要麼悄悄地産生不正确的結果），或者它可能幸運地正好做了程式員所希望的。

這是一個好的總結。幾乎所有C及C++程式員都了解通路一個空指針以及除0是錯誤的行為。另一方面，未定義行為的完整含義及其與進取編譯器間的互動未能被很好領會。

未定義行為的一個模型

現在，我們可以忽略編譯器的存在。僅存在“C實作”，如果該實作符合C标準——在執行一個合乎标準的程式時，與“C抽象機器”的行為相同。C抽象機器是C标準描述的一個簡單的C解析器。我們可以用它來确定任何C程式的含義。

一個程式的執行包含簡單的步驟，比如兩個數相加或跳轉到一個label。如果在一個程式執行中的每步具有已定義的行為，那麼整個執行是定義良好的。注意即使定義良好的執行也可能因為未指定（unspecified）及實作定義的行為，而沒有唯一的結果；這裡我們将忽略這兩者。

如果在一個程式的執行中任一步具有未定義行為，那麼整個執行是沒有意義的。這是重要的：對(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      

還有這個：

$ cc test.c -o test      

$ ./test      

42      

還有這個：

$ cc test.c -o test      

$ ./test      

Formatting root partition, chomp chomp      

有人可能會說：這些編譯器中的一些行為不正确，因為C标準宣稱一個關系操作符必須傳回0或1。但因為程式完全沒有意義。實作可以做任何它想做的事。未定義的行為超出C抽象機器的其它行為。

一個編譯器實際産生的代碼會破壞你的硬碟嗎？當然不會，但記住實際上來說，未定義行為通常确實導緻壞的事情，因為許多安全漏洞始于具有未定義行為的記憶體或整數操作。例如，通路一個界外數組元素是正常棧破壞攻擊的關鍵部分。總而言之：編譯器不需要産生格式化你硬碟的代碼。相反，随着OOB數組通路，你的計算機将開始執行漏洞利用代碼，正是該代碼格式化你的硬碟。

行不通

人們很容易說——或至少認為這樣：

x86 ADD指令用于實作C有符号數相加操作，在結果溢出時它具有2機制補碼行為。我正在一個x86平台上開發，是以在32位有符号整數溢出時，我應該可以期望2機制補碼語義。

這是不對的。你在表述這樣的東西：

有人曾經告訴我，在籃球比賽中你不能抱着球跑。我拿了籃球嘗試，這樣挺好的。他顯然不了解籃球。

（這個解釋歸功于Roger Miller通過SteveSummit做出）。

顯然實體上撿起籃球，帶着它跑是可能的。在一場比賽中你僥幸這樣做也是可能的。不過，它違反了規則；好的運動員不會這樣做，而差的運動員不會總是好運。在C或C++中對(INT_MAX+1)求值也一樣：有時可能能工作，但不要指望總是這樣。情形實際上有些微妙，讓我們看深入些。

首先，存在在有符号整數溢出時，確定2機制補碼行為的C實作嗎？顯然有的。例如，許多編譯器在關閉優化時具有這個行為，GCC有一個選項（-fwrapv）在所有優化級别強制這個行為。其它編譯器預設在所有優化級别具有這個行為。

不言而喻，也存在編譯器，對有符号溢出，沒有2機制補碼行為。另外，有些編譯器（像GCC）多年來以特定的方式處理整數溢出，然後某個時候優化器變得更聰明些，而整數溢出突然悄悄地不能預期工作了。就标準而言，這完全沒問題。盡管對開發者不友好，它應該被視為編譯器團隊的勝利，因為它将提升基準評分。

總結：帶着一個球跑本質上沒有不對的地方，同樣以33位移位一個32位數本質上也沒有不對。但一個違反了籃球規則，而另一個違反了C與C++的規則。在這兩個情形下，設計遊戲的人已經制訂了随意的規則，我們要麼遵循它們，要麼尋找更喜歡的遊戲。

為什麼未定義行為是好的？

好的——關于C/C++中未定義行為僅有的好處！是：它簡化了編譯器的工作，使得在特定情形下産生高效的代碼成為可能。這些情形通常涉及緊湊循環。例如，高性能數組代碼不需要執行邊界檢查，避免使用複雜的優化遍從循環移出這些檢查。類似地，當編譯一個遞增一個有符号整數的循環時，C編譯器無需擔心該變量溢出及變為負的情形：這使幾種循環優化變得容易。我聽說當允許編譯器利用有符号整數溢出的未定義屬性時，某些緊湊的循環加速了30%~50%。類似地，有C編譯器可選地向無符号整數溢出給出未定義語義，以加速其它循環。

為什麼未定義行為是壞的？

當程式員不能被信任能避開未定義行為時，我們最終具有悄悄不能正确工作的程式。對于像網絡伺服器及網絡浏覽器這樣處理敵對資料的代碼，這已經被證明是一個非常糟糕的問題，因為這些程式最終妥協并運作從網絡來的代碼。在許多情形下，我們實際上不需要利用未定義行為來擷取性能提升，但由于老舊的代碼及工具鍊，我們被惡劣的後果纏住了。

一個不那麼嚴重、更令人煩惱的問題是：行為被未定義，完全在于使得編譯器作者的工作更容易些，并沒有性能的提升。例如一個C實作具有未定義行為，當：

在符号化期間，在一邏輯行上遇到一個未比對的‘或”字元。

無意冒犯C标準委員會，這是懶惰。要求C實作者在引号不比對時發出一個編譯器時錯誤消息，這會是個過分的負擔嗎？這方面一個甚至有30年曆史（C99在那時标準化）的系統程式設計語言都做得更好。有人懷疑C标準隻是習慣把行為丢入“未定義”籮中，并且有點過火了。實際上，C99标準列出191種未定義行為，說他們太過火是公允的。

了解編譯器如何看待未定義行為

設計一個帶有未定義行為的程式設計語言背後關鍵的洞察是：編譯器僅有義務考慮行為是有定義的情形。我們現在将探索這個問題的含義。

如果想象一個C程式将要被C抽象機器執行，未定義行為非常容易了解：程式執行的每個操作要麼是已定義的，要麼是未定義的，通常這相當清楚。當我們開始關注一個程式所有可能的執行，未定義行為開始變得難以處理。應用程式開發者，需要代碼在任何情形下都正确，對此在意，同樣還有編譯器開發者，他們需要産生在所有可能的執行中正确的機器代碼。

讨論一個程式所有可能的執行有點棘手，讓我們做一些簡化的假設。首先，我們将讨論單個C/C++函數，而不是整個程式。其次，我們将假定函數對每個輸入都終止。第三，我們将假定函數的執行是确定性的；例如，它沒有通過共享記憶體與其它線程協作。最後，我們假設具有無限的計算資源，使窮舉測試該函數成為可能。窮舉測試意味着嘗試所有可能的輸入，不管它們來自實參，全局變量，檔案I/O，還是其它。

窮舉測試算法是簡單的：

1. 計算下一個輸入，如果我們已經嘗試了所有，終止
2. 使用這個輸入，在C抽象機器中運作這個函數，記錄是否執行了任何帶有未定義行為的操作
3. 回到步驟1

枚舉所有的輸入不是太困難。

以該函數接受的最小輸入（以比特衡量）開始，嘗試該大小所有可能的比特模式。然後進入下一個大小。這個過程可能終止、也可能不終止，但沒關系，我們有無限的計算資源。

對于包含未指定及實作定義行為的程式，每個輸入可能導緻幾個或許多可能的執行。這不會從根本上使情況變得更複雜。

好了，我們的思維實驗達到了什麼目的？對于我們的函數，現在我們知道它落入了哪個類别：

• 類型1：對所有輸入行為是已定義的
• 類型2：對某些輸入行為是已定義的，而對于其它則沒有
• 類型3：對于所有輸入，行為是未定義的

類型1函數

這些對它們的輸入沒有限制：對于所有可能的輸入，它們都行為良好（當然，“行為良好”可能包括傳回一個錯誤值）。通常，API級别的函數以及處理未淨化資料的函數，應該是類型1的。例如，這是一個進行整數除法，而不會執行未定義行為的實用函數：

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函數永遠不會執行帶有未定義行為的操作，無論函數的輸入是怎樣的，編譯器都有義務産生合理的代碼。我們無需進一步考慮這些函數。

類型3函數

這些函數沒有容許良好定義的執行。嚴格地說，它們完全是無意義的：編譯器甚至沒有義務産生一條return指令。類型3的函數真實存在嗎？是的，而且事實上它們是普遍的。例如，不管輸入，一個函數使用一個變量而不初始化它，是很容易無意地寫出的。在識别及利用這種代碼方面，編譯器越來越聰明。這裡是來自Google NativeClient項目的一個極好的例子：

當從信任或非信任代碼傳回時，在擷取傳回位址之前，我們必須淨化它。這確定非信任代碼不能使用syscall接口向量執行（vector execution）到一個任意位址。這個任務委托給在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位元組的包大小。在x86上使用gcc，(1 << 32) == 1。（我相信标準把這個行為保留為未定義，但我對此生疏）。這樣，整個沙盒序列成了一個空操作。

這個改動有4個登記的稽核者，兩個明确表示我看沒問題。看起來沒有人注意到這個改動。

——影響

在32位x86上的非信任代碼通過構造一個傳回位址，并進行一個syscall，潛在不對齊其指令流的可能。這可以破壞驗證器。一個類似的漏洞可能影響x86-64。

出于曆史原因ARM不受影響：ARM實作使用不同的方法來掩碼非信任傳回位址。

發生了什麼？一個簡單的重構使得包含這個代碼的函數成為類型3。發送這個資訊的人相信x86-gcc把(1<<32)求值為1，但沒有理由期望這個行為是可靠的（事實上，在我嘗試的幾個x86-gcc版本上，不是這個行為）。這種構造絕對是未定義的，編譯器當然可以做任何它想做的事。對應一個未定義操作，典型地，一個C編譯器選擇不生成任何指令（C編譯器的第一要務是産生高效的代碼）。一旦Google程式員給了編譯器殺人執照，它會毫不猶豫地殺戮。有人會問：如果當檢測到一個類型3的函數時，編譯器提供一個警告或類似的東西不是很棒嗎？是的！但這不是編譯器優先要做的。

Native Client是一個好例子，因為它展示了合格的程式員會被一個優化編譯器利用未定義行為的秘密行徑所迷惑。在開發者看來，在識别并悄悄銷毀類型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版本的測試不是巧合。如果你，調用者，違反了這個先決條件，你程式的意義将被破壞。編寫像這樣帶有非平凡先決條件的函數可以嗎？通常，對于内部使用的函數，這完全沒問題，隻要先決條件被清晰文檔化了。

現在讓我們看一下當把這個函數翻譯到目标代碼時，編譯器的工作。編譯器進行一個案例分析：

• 案例1：(b != 0) && (!((a == INT32_MIN) && (b == -1)))

/操作符的行為是已定義的à編譯器有義務産生計算a / b的代碼。

• 案例2：(b == 0) || ((a == INT32_MIN) && (b == -1))

/操作符的行為是未定義的à編譯器沒有特定的義務

現在編譯器作者問他們自己這個問題：什麼是這兩個情形最有效的實作？因為情形2不招緻任何義務，最簡單的做法是不考慮它。編譯器可以僅為情形1産生代碼。

相反，一個Java編譯器在情形2中負有義務，必須處理它（雖然在這個特定的案例中，很可能沒有運作時開銷，因為處理器通常為整數除0提供陷入行為（trapping behavior））。

讓我們看另一個類型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      

類似地，一個預編譯（ahead-of-time）Java編譯器也必須執行加法，因為在一個有符号整數溢出時，Java責令2機制補碼行為（對x86-64我使用GCJ）：

_ZN13HelloWorldApp6stupidEJbii:      

  leal 1(%rsi), %eax      

  cmpl %eax, %esi      

  setl %al      

  ret      

這個未定義行為崩潰案例的觀察提供了一個有力的方式來解釋編譯器實際如何工作。記住，它們的主要目的是給你遵守法律條文的快速代碼，是以它們将嘗試盡可能快地忘記未定義行為，而且不會告訴你這個。

一個有趣的案例分析

大約1年前，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 ...      

}      

這裡的習語是得到指向一個裝置結構體的指針，測試它是否空，如果使用它。但有一個問題！在這個函數裡，在空指針檢查前該指針被提領了。這導緻一個優化編譯器（例如，gcc在-O2或更高優化級别）執行以下案例分析：

• 案例1：dev == NULL

dev->priv有未定義行為 à 編譯器沒有特定的義務

• 案例2：dev != NULL

空指針檢查不會失敗 à 空指針檢查是死代碼，可能被删除

正如我們現在很容易看出，沒有一個案例使得空指針檢查成為必須。該檢查被移除，潛在地建立了一個可利用的安全漏洞。

當然，這個問題是pci_get_drvdata()傳回值的檢查前使用，這必須通過把使用移到檢查後來修正。但直到可以審查所有這樣的代碼（人工或通過工具）前，告訴編譯器稍微保守些，被認為更安全。由于像這樣的可預測分支導緻的效率損失總體可以忽略不計。在核心的其它部分也找到類似的代碼。

與未定義行為和平共處

從長遠來看，非安全的程式設計語言将不會為主流開發者使用，而是專用于高性能及低資源足迹是關鍵的情形。與此同時，未定義行為的處理不完全是直截了當的，拼湊（patchwork）的做法看起來是最好的：

• 啟用并注意編譯器警告，最好使用多個編譯器
• 使用靜态分析器（像Clang，Coverity等）來得到更多警告
• 使用編譯器支援的動态檢查；例如，gcc的-ftrapv标記産生捕捉有符号整數溢出的代碼
• 使用像Valgrind的工具來得到額外的動态檢查
• 當函數是上面分類的“類型2”時，歸檔它們的先決條件與後承條件
• 使用斷言來驗證該函數的先決條件是實際成立的後承條件
• 特别在C++中，使用高品質的資料結構庫

最基本地：非常小心，使用好的工具，抱樂觀的希望。