本文翻譯自John Regehr的博文?“A Guide to Undefined Behavior in C and C++, Part 1”，原文發(fā)布于2010年7月9日，鏈接見文末。

正文

編程語言通常會區(qū)分正常操作和錯誤操作。對于圖靈完備的語言，我們無法可靠地僅憑源代碼判斷程序是否會出錯，只能運(yùn)行程序，然后查看結(jié)果。

在安全的編程語言中，錯誤會在發(fā)生時被捕獲。例如，Java利用其異常系統(tǒng)保證了大部分情況下的安全。而不安全的編程語言不會捕獲錯誤。相反，程序會悄悄地繼續(xù)運(yùn)行，直到剛才的錯誤操作導(dǎo)致了明顯的后果。Luca Cardelli關(guān)于類型系統(tǒng)的文章對這些問題進(jìn)行了清晰的介紹。C和C++渾身上下都散發(fā)著不安全的氣息：錯誤的操作不僅會導(dǎo)致結(jié)果不可預(yù)測，甚至?xí)?dǎo)致整個程序最終毫無意義。在C和C++中，這些錯誤的操作被稱為“未定義行為 (undefined behavior)”。

《C語言常見問題集》是這樣定義“未定義行為”的：

未定義意味著任何事情都可能發(fā)生，標(biāo)準(zhǔn)在任何情況下都不強(qiáng)加要求。

程序可能無法編譯；也可能無法正確執(zhí)行——程序崩潰，或者默默地產(chǎn)出了錯誤的結(jié)果；亦或是偶然按照程序員的意圖“正確”執(zhí)行了。

這是一個很好的總結(jié)。幾乎每個C/C++程序員都知道解引用空指針和除以零是錯誤的操作。但是，未定義行為更深層的含義，以及它和那些激進(jìn)的編譯器的交互方式，還有待進(jìn)一步的發(fā)掘。而這正是本文的主題。

未定義行為的模型

現(xiàn)在，讓我們忘記編譯器，只關(guān)注“C實(shí)現(xiàn)”。它必須符合C標(biāo)準(zhǔn)，在執(zhí)行符合C標(biāo)準(zhǔn)的程序時，行為與“C抽象機(jī)”相同。C抽象機(jī)是C標(biāo)準(zhǔn)中描述的C語言解釋器。我們用C抽象機(jī)來確定任意C程序的含義。

程序由一些簡單的步驟組成，例如把兩個數(shù)相加，或者跳轉(zhuǎn)到某個標(biāo)簽。如果程序中每個步驟的行為都有明確定義，那么整個程序的執(zhí)行過程就是明確定義的。注意，由于未指明行為(unspecified)和實(shí)現(xiàn)定義行為(implementation-defined)的存在，程序執(zhí)行的結(jié)果可能不是唯一的，我們暫時忽略這兩個因素的存在。

如果程序中任意步驟具有未定義的行為，那么整個執(zhí)行過程都是沒有意義的。這一點(diǎn)很重要：并不是說對表達(dá)式(1 << 32)求值會得到不可預(yù)測的結(jié)果，而是說求值這個表達(dá)式的程序是沒有意義的。此外，也不是說在未定義行為發(fā)生之前，程序的執(zhí)行就有意義：不良影響可能先于導(dǎo)致未定義行為的操作產(chǎn)生。

例如如下程序：

這個程序向C實(shí)現(xiàn)提出了一個小問題：如果在int能表示的最大值上再加1，它會變成負(fù)數(shù)嗎？而對于C實(shí)現(xiàn)而言，以下行為當(dāng)然是合法的：

以下行為也是合法的：

還有這個：

甚至這個：

有人可能會說：這其中某些編譯器的行為不正確！因?yàn)镃語言的比較運(yùn)算符只能返回0或者1。但是請別忘了，這段程序毫無意義，實(shí)現(xiàn)可以為所欲為。未定義行為壓倒C抽象機(jī)的其他所有行為。

一個真正編譯器會產(chǎn)出代碼來粉碎你的磁盤嗎？當(dāng)然不會。但請銘記在心：未定義行為往往導(dǎo)致壞事，安全漏洞往往始于一個引發(fā)未定義行為的內(nèi)存操作或整數(shù)運(yùn)算。例如，訪問越界的數(shù)組元素是典型的棧粉碎攻擊的關(guān)鍵步驟。總之，編譯器無需產(chǎn)出代碼來格式化你的硬盤。相反，在你訪問了越界的數(shù)組元素之后，電腦將開始執(zhí)行利用這些漏洞的代碼，然后格式化你的硬盤。

不要“走步”

人們常說，或者至少認(rèn)同這樣的話：

Ｃ語言的有符號加法是用x86 ADD指令實(shí)現(xiàn)的，結(jié)果溢出時會遵循補(bǔ)碼的運(yùn)算規(guī)則。而我恰好在x86平臺開發(fā)，所以我能期待32位有符號整數(shù)溢出時的補(bǔ)碼語義。

但這是錯的。你就像是在說：

有人跟我說打籃球的時候不能抱著球跑。我買了個球試了一下，我不僅能抱著球跑，還能唱跳rap《只因你太美》。這人到底懂不懂籃球??？

物理規(guī)則當(dāng)然允許你抱著籃球到處跑，你甚至能在籃球比賽的時候走步還逃過裁判的法眼。但這違反了籃球規(guī)則。好球員不會這樣做，而壞球員也并不能總是逍遙法外。在C和C++中對(INT_MAX+1)求值是一樣的道理：你可能僥幸觀察到了補(bǔ)碼行為，但別期待每次都能這樣。而實(shí)際情況往往更加微妙，所以我們來看看更深入的細(xì)節(jié)。

首先，是否存在某個C實(shí)現(xiàn)保證有符號整數(shù)運(yùn)算溢出時，按補(bǔ)碼規(guī)則處理？答案是肯定的。許多編譯器在關(guān)閉優(yōu)化的時候都確保這種行為。而GCC則可以通過編譯選項(xiàng)(-fwrapv)在所有優(yōu)化級別強(qiáng)制執(zhí)行這種行為。甚至有的編譯器默認(rèn)在所有優(yōu)化等級都執(zhí)行這種行為。

但是不用說，還有一些編譯器沒有針對有符號整數(shù)算術(shù)溢出的補(bǔ)碼行為。甚至于某些編譯器，例如GCC，多年以來一直以某種方式實(shí)現(xiàn)整數(shù)溢出行為，突然有一天，優(yōu)化器變得聰明了一點(diǎn)，這種行為就悄無聲息地改變了。這對開發(fā)者來說有點(diǎn)不友好，但編譯器團(tuán)隊(duì)卻覺得這是一次勝利，因?yàn)榫幾g器的跑分提高了。

總結(jié)：帶球走沒有什么本質(zhì)上的壞處，把一個32位數(shù)字左移33位也沒有什么本質(zhì)上的壞處。但前者違反了籃球規(guī)則，而后者違反了C/C++的規(guī)則。不論如何，游戲的設(shè)計(jì)者制定了規(guī)則，要么你遵守他們的規(guī)則，要么你另起一套你更喜歡的規(guī)則。

未定義行為的好處

未定義行為唯一的好處，就是簡化了編譯器的工作，使得它可以在特定的情況下產(chǎn)出非常高效的代碼。這些情況通常涉及緊湊的循環(huán)。例如，高性能數(shù)組操作可以無需邊界檢查，避免了棘手的多輪優(yōu)化來將這些檢查提升到循環(huán)之外。類似地，當(dāng)編譯一個不斷遞增有符號整數(shù)的循環(huán)時，編譯器無需擔(dān)心變量溢出然后變成負(fù)數(shù)的情況：這有利于多種循環(huán)優(yōu)化的手段。據(jù)說在允許編譯器利用有符號整溢出的未定義行為時，可將某些緊湊循環(huán)的速度提高30%到50%。類似地，甚至有編譯器可以為無符號數(shù)溢出提供未定義語義，從而加速其他循環(huán)。

未定義行為的壞處

當(dāng)一個不受信任的程序員無法有效避免未定義行為時，我們最終會得到一個默默執(zhí)行錯誤操作的程序。這對于Web服務(wù)器和瀏覽器等程序來說是個非常棘手的問題。因?yàn)樗麄儠r常遭受惡意數(shù)據(jù)攻擊，最終敗下陣來，開始執(zhí)行順著網(wǎng)線爬進(jìn)來的惡意代碼。實(shí)際上，大多數(shù)情況下我們無需為了提高一點(diǎn)點(diǎn)性能而利用未定義行為。但是因?yàn)闅v史遺留的代碼和工具鏈，我們不得不忍受這令人討厭的后果。

而另一個不太嚴(yán)重但頗為惱人的問題是，某些未定義行為真的就只是讓編譯器的工作變簡單了一點(diǎn)，而對提升性能沒有任何幫助。例如C標(biāo)準(zhǔn)就規(guī)定遇到以下情況時程序的行為未定義：

標(biāo)記化期間，在源代碼的邏輯行中遇到了不匹配的單引號或雙引號。

恕我直言，C標(biāo)準(zhǔn)委員會就是懶。在編譯期檢查出未匹配的引號并給出錯誤信息能給編譯器帶來多大的負(fù)擔(dān)？三十年前開發(fā)的系統(tǒng)語言也比這做得好。有人懷疑委員會只是習(xí)慣于把各種行為扔進(jìn)“未定義”的桶里，還對此自鳴得意。事實(shí)上，自C99以來，標(biāo)準(zhǔn)中已經(jīng)列出了191種未定義行為，委員會確實(shí)有些得意忘形了。

編譯器眼中的未定義行為

洞悉設(shè)計(jì)一門含有未定義行為編程語言的關(guān)鍵，就是編譯器只需考慮行為已定義的情況。讓我們接下來討論這一點(diǎn)。

假設(shè)有一個運(yùn)行在C抽象機(jī)上的C程序，未定義的行為很容易理解：程序執(zhí)行的每個操作要么是已定義的，要么是未定義的，并且很容易區(qū)分。但是，當(dāng)我們開始關(guān)注程序所有可能執(zhí)行的路徑時，未定義行為就變得難以處理了。應(yīng)用程序開發(fā)者需要關(guān)注這一點(diǎn)，以確保程序在任何情況下都執(zhí)行正確，編譯器的開發(fā)者也是一樣，他們需要保證編譯器產(chǎn)出的機(jī)器碼能在任何條件下正確執(zhí)行。

討論一個程序所有可能的執(zhí)行路徑有點(diǎn)棘手，讓我們稍微做一點(diǎn)簡化的假設(shè)。首先，我們將討論單個C/C++函數(shù)而不是整個程序。其次，我們假定函數(shù)對任意輸入都會終止執(zhí)行。第三，我們假設(shè)函數(shù)的執(zhí)行過程是確定的，例如它不會通過共享內(nèi)存與其他線程交互。最后，假設(shè)我們有無限的計(jì)算資源，從而可以對函數(shù)進(jìn)行詳盡地測試。詳盡的測試意味著所有可能的輸入都會被考慮，不論他們來自參數(shù)、全局變量、文件I/O還是其他。

測試方法很簡單：

1. 計(jì)算下一個輸入，如果所有的輸入都已經(jīng)過測試，就終止；

2. 使用當(dāng)前輸入，在C抽象機(jī)中執(zhí)行這個函數(shù)，觀察程序是否會觸發(fā)未定義行為；

3. 回到第一步；

窮舉所有輸入不算太難。從函數(shù)可接受的最小的輸入開始（以位為單位），嘗試當(dāng)前大小的所有位模式，然后開始嘗試下一個大小。這個過程可能會終止，也可能不會終止，但這并不重要，因?yàn)槲覀儞碛袩o限的計(jì)算資源。

對于包含未指定行為和實(shí)現(xiàn)定義行為的程序，每個輸入都可能導(dǎo)致幾個或更多可能的執(zhí)行路徑，但這并未從根本上增加復(fù)雜度。

那么，我們的思想實(shí)驗(yàn)得出了什么樣的結(jié)果呢？能將我們的函數(shù)分類到一下三種的其中之一：

• 第一類：對于所有輸入都具有明確定義的行為；

• 第二類：對于部分輸入有明確定義，而另一部分輸入則未定義；

• 第三類：對于所有輸入都有未定義行為；

第一類函數(shù)

這些函數(shù)對輸入沒有任何限制：他們對所有可能的輸入都是良定義的。當(dāng)然，良定義也包括對錯誤的輸入返回相應(yīng)的錯誤代碼。通常來說，API級別的函數(shù)和接收未經(jīng)處理的數(shù)據(jù)的函數(shù)應(yīng)該是第一類。例如下面這個用于計(jì)算整數(shù)除法而不會引發(fā)未定義行為的實(shí)用函數(shù)：

鑒于第一類函數(shù)從不執(zhí)行未定義行為的操作，因此編譯器理應(yīng)生成執(zhí)行合理操作的代碼，不論函數(shù)的輸入如何。我們無需進(jìn)一步考慮這類函數(shù)。

第三類函數(shù)

這些函數(shù)不會執(zhí)行任何良定義的行為。嚴(yán)格來說，他們完全沒有意義：編譯器甚至可以不產(chǎn)生返回指令。那這種函數(shù)真的存在嗎？當(dāng)然存在，并且很常見。例如，你很容易在無意中寫出一個函數(shù)，它的某個局部變量沒有初始化。好在編譯器識別這種代碼的能力正在變得越來越強(qiáng)。而其中一個反面教材就是Google Native Client項(xiàng)目：

當(dāng)從可信代碼返回到不可信代碼時，我們必須在獲取返回地址之前檢查它。這確保了不受信任的代碼不能利用系統(tǒng)調(diào)用來引導(dǎo)執(zhí)行到任意地址。這項(xiàng)任務(wù)被托付給了NaClSandboxAddr函數(shù)，聲明于sel_ldr.h中。不幸的是，自r572以來，這個函數(shù)在x86上一直是無操作的。

——起因——

在一次例行重構(gòu)時，有如下代碼：

被改成了如下代碼：

除了重命名變量之外，還引入了一個左移操作，將nap->align_boundary視為包大小以2為底的對數(shù)。

但我們沒有注意到的是x86上的NaCl包大小為32字節(jié)。在x86上使用GCC編譯時，(1 << 32) == 1。我沒記錯的話，標(biāo)準(zhǔn)將這一行為視為未定義。如此一來，整個沙盒序列都變成了無操作。

這項(xiàng)變更有四名在列的代碼評審員，并且通過了兩輪LGTM分析，似乎沒有人注意到這一變化。

——影響——

在32位x86上，不受信任的代碼有可能通過構(gòu)造返回地址和進(jìn)行系統(tǒng)調(diào)用來取消其指令流的對齊。這可能繞過驗(yàn)證器。類似的漏洞也可能影響x86_64。

由于歷史原因，ARM不受影響：ARM實(shí)現(xiàn)使用不同的方法屏蔽了不受信任的返回地址。

你看！一個簡單的重構(gòu)就把包含這段代碼的函數(shù)打入了第三類。上述引文的作者認(rèn)為x86-gcc將(1<<32)求值為1，但你沒有理由認(rèn)為這種行為是可靠的。事實(shí)上我嘗試過數(shù)個版本的x86-gcc，都沒有復(fù)現(xiàn)該行為。這個表達(dá)式當(dāng)然是未定義的，編譯器也可以做它想做的任何事。與普通的C編譯器一樣，gcc選擇不產(chǎn)出任何指令。編譯器的第一要義是產(chǎn)出高效的代碼。一但這位谷歌程序員放開了牽著編譯器的韁繩，編譯器就會一路向前，哪怕前方是萬丈高崖。也許有人會問：如果編譯器檢測到第三類函數(shù)就發(fā)出警告或者類似的提示不就好了嗎？那固然好，但這不是編譯器優(yōu)先事項(xiàng)。

Google Native Client的例子很好的展示了優(yōu)秀的程序員是如何被優(yōu)化編譯器利用未定義行為的卑鄙手段誘惑的。在程序員眼中，能識別并悄悄破壞第三類函數(shù)的編譯器，已經(jīng)聰明到近乎邪惡了。

第二類函數(shù)

這些函數(shù)對于某些輸入是有定義的，而對其他輸入則行為未定義。就本文的目的而言這類函數(shù)是最有趣的。有符號整數(shù)的除法就是個很好的例子：

這個函數(shù)有一個先決條件，只能使用滿足下列表達(dá)式的參數(shù)調(diào)用它：

這個表達(dá)式看起來很像第一類函數(shù)的那個例子中的測試條件，這并非巧合。如果作為調(diào)用者的你違反了這個條件，你的程序就失去了它的意義。寫出這樣具有非平凡先決條件的函數(shù)是可行的嗎？一般來說，對于內(nèi)部使用的工具函數(shù)，只要在文檔中詳細(xì)說明先決條件，使用這樣的函數(shù)是完全沒問題的。

現(xiàn)在讓我們來看看編譯器在將這個函數(shù)翻譯成目標(biāo)代碼時的工作。編譯器會作出如下情景分析：

• 情形一：(b != 0) && (!((a == INT32_MIN) && (b == -1)))，除法運(yùn)算是有定義的，編譯器應(yīng)該產(chǎn)出相應(yīng)的代碼來計(jì)算a/b；

• 情形二：(b == 0) || ((a == INT32_MIN) && (b == -1))，除法運(yùn)算的行為未定義，編譯器不作出任何保證；

現(xiàn)在輪到編譯器的開發(fā)者思考了：如何才能高效地兼顧兩種情形呢？最簡單的方法就是，不考慮情形二！因?yàn)榫幾g器無需給出任何保證，只要產(chǎn)生能處理情形一的代碼即可。

作為對比的是Java編譯器，必須對情形二作出保證，并且處理這種情形。雖然在這個例子中，這幾乎不會增加運(yùn)行時開銷，因?yàn)楝F(xiàn)代處理器通常提供硬件級除以零的錯誤捕獲功能。

再來看看另一個第二類函數(shù)的例子：

避免此函數(shù)引發(fā)未定義行為的先決條件是：

編譯器同樣會進(jìn)行情景分析：

• 情形一：(a != INT_MAX)，加法操作是有定義的，編譯器保證返回值為1；

• 情形二：(a == INT_MAX)，加法操作行為未定義，編譯器不作出任何保證；

同理，情形二會在編譯器的分析過程中退化并消失，只考慮情形一。于是一個優(yōu)秀的x86-64編譯器會產(chǎn)出如下匯編代碼：

如果我們通過-fwarpv選項(xiàng)告訴GCC，整數(shù)溢出按照補(bǔ)碼規(guī)則處理，我們就會得到不同的情景分析：

• 情形一：(a != INT_MAX)為真，加法操作是有定義的，編譯器保證返回值為1；

• 情形二：(a == INT_MAX)為真，加法操作是有定義的，編譯器保證返回值為0；

在此情形下，編譯器必須考慮兩種情形。因此必須產(chǎn)出代碼來執(zhí)行加法操作并檢查計(jì)算結(jié)果：

類似的，Java AOT編譯器也必須執(zhí)行加法操作，因?yàn)镴ava要求有符號整數(shù)溢出時，按照補(bǔ)碼規(guī)則處理。我使用的是x86-64上的GCJ編譯器：

這種通過情形分析來觀察未定義行為的視角提供了一種解釋編譯器如何工作的強(qiáng)有力的方法。請記住，編譯器的主要目標(biāo)是在標(biāo)準(zhǔn)條款的限制下，為你提供盡可能高效的代碼。因此它們會盡力忽略未定義行為的存在，而且不會告訴你。

一個有趣的情景分析

大約一年前，Linux內(nèi)核開始使用一個特殊的GCC編譯選項(xiàng)來告訴編譯器避免優(yōu)化掉無用的空指針檢查。迫使開發(fā)人員使用這個編譯選項(xiàng)的代碼如下所示，我對代碼做了一定程度的簡化：

這里的慣用手法是先獲取一個指向設(shè)備結(jié)構(gòu)體的指針，檢查它是否為空，然后再使用。但這段代碼的問題是，指針在檢查是否為空之間就被解引用了。這會導(dǎo)致編譯器作出如下情景分析，尤其是開啟了-O2或以上優(yōu)化等級的GCC：

• 情形一：dev == NULL，則"dev->priv"的行為未定義，編譯器不給出任何保證；

• 情形二：dev != NULL，則空指針檢查是無效代碼，那部分的代碼被當(dāng)成死代碼移除；

不難看出，不論那種情形，都不需要空指針檢查。而刪除檢查的代碼則會產(chǎn)生可被利用的安全漏洞。

當(dāng)然，問題的關(guān)鍵是pci_get_drvdata()函數(shù)的返回值在檢查之前就解引用了，只需把解引用的代碼移到空指針檢查之后即可。但類似的代碼不止一處，不論是用工具檢查還是人工檢查，在修復(fù)所有問題之前，告訴編譯器保守一點(diǎn)總是更安全。像這樣可被預(yù)測的分支導(dǎo)致的效率損失可以忽略不計(jì)。

生活在未定義行為中

從長遠(yuǎn)來看，不安全的編程語言不會成為主流程序員的選擇，它們會被保留在需要高性能和低資源占用的關(guān)鍵地帶。與此同時，與未定義行為打交道沒有什么萬全之法，凡事都得綜合考慮，才是最好的：

• 開啟并關(guān)注編譯器警告，最好能使用多個編譯器

• 使用靜態(tài)分析器，來獲取更多警告。例如Clang的靜態(tài)分析器、Coverity等。

• 使用編譯器內(nèi)置的動態(tài)檢查，例如GCC的-ftrapv選項(xiàng)可以產(chǎn)出捕獲整數(shù)溢出的代碼

• 使用Valgrind等工具進(jìn)行額外的動態(tài)檢查

• 當(dāng)使用上述的“第二類”函數(shù)時，在文檔中注明先決條件和后置條件

• 使用斷言來驗(yàn)證函數(shù)的先決條件與后置條件的一致性

• 尤其是C++中，使用高質(zhì)量數(shù)據(jù)結(jié)構(gòu)庫

最后：小心謹(jǐn)慎，善用工具，盡人事，聽天命。

正文結(jié)束

原文鏈接：https://blog.regehr.org/archives/213

John Regehr

美國猶他大學(xué)教授，專注于計(jì)算機(jī)編譯器正確性及未定義行為的研究。其編寫的整數(shù)溢出檢查器被合并入Clang的C編譯器，其編寫的C編譯器模糊測試工具Csmith亦被廣泛使用。