---
tags: C語言
---

# 關於 Overflow 的二三事

## 無關緊要的素材

在開始高談闊論之前，先把這首歌推薦給大家放在背景一邊閱讀(?)。

{%youtube xcuDJ4_adKM %}

> [武士道迷因 BushiroadMemes Taiwan](https://www.facebook.com/BushimemeTaiwan/photos/a.665959463858584/1383874785400378/)

## Overflow

[Overflow](https://en.wikipedia.org/wiki/Integer_overflow) 是指算術運算試圖創建一個超出可用位數表示範圍（大於最大值或小於最小值）的數值時所會發生整數溢出。在大部分程式設計師的既定印象中，overflow 似乎讓人感覺是不友善的。確實，overflow 造成的軟體危害確實履見不鮮，一個很經典的例子是 1996 年的 [Ariane 5 火箭因為 overflow 導致升空過程中爆炸](https://hackmd.io/@sysprog/software-failure#Ariane-5-%E7%81%AB%E7%AE%AD%E5%8D%87%E7%A9%BA%E9%81%8E%E7%A8%8B%E4%B8%AD%E7%88%86%E7%82%B8)事件。

不過這些錯誤可不僅是因為過去經驗的不足導致，即使是近期，overflow 的問題仍然會發生，而且發生問題的不是名不見經傳的公司，我相信這些名字大家都耳熟能詳:
* [Google 在 Android 系統上的 overflow 導致 911 無法撥號](https://arstechnica.com/gadgets/2022/01/google-fixes-nightmare-android-bug-that-stopped-user-from-calling-911/?fbclid=IwAR33_VDgInO9ARTGGoX8WvHgTn675HddqY5rOJqRX9GPclhtv0cMrNQ7suM)
* [Microsoft Exchange 因為 long int 的有效位數 overflow 導致無法傳送電子郵件](https://www.bleepingcomputer.com/news/microsoft/microsoft-exchange-year-2022-bug-in-fip-fs-breaks-email-delivery/?fbclid=IwAR33nHd5NBrdZgb2IuCOx_9SnE6NdhHGDqSCdo3M5dXDbnVpzNTIQ71bAZ0#.YdES5rcZD4g.facebook)

按理來說，overflow 的發生原因相對直接，如果是在執行時期，應該是很容易被檢測的，為什麼直至今日我們仍然很容易遇見類似的問題呢。困難點就在於 overflow 並不總是 bug。以語言層面而言，overflow 的存在其實也是一種 feature。實際上，相較於非預期的 overflow 行為，許多的 overflow 其實是撰寫程式時刻意為之。比方說，很多軟體都會依賴於無符號整數(unsinged integer)的 wraparound behavior。正因如此，實際的需求應該要說是檢測 "非刻意為之的 overflow"。在這一層面上，如何檢測就變得相對複雜了。

## Overflow 的分類

我們可以把 overflow 區分為語言未定義與定義行為的兩類，而根據程式撰寫者使用的目的，兩者又可以區分為刻意與否。

### 已定義行為 overflow

在 C 語言中，有明確定義行為的 overflow 即為 unsigned 整數的運算。對於後者，overflow 會以 wraparound 的方式處理，舉例來說，`UINT_MAX + 1` 的結果明確為 `0`。

不過，即使是被定義的運算，其結果卻並不一定是程式撰寫者所預期的，比方以下的程式:

#include <stdio.h>
#include <limits.h>

unsigned int foo(unsigned int x)
{
    unsigned int cnt = 0;
    for(unsigned int y = x + 1; y > x; y--)
    {   
        cnt+=x;
    }   
    return cnt;
}

unsigned int bar(unsigned int x)
{
    unsigned int cnt = 0;
    for(unsigned int i = 0; i > 1;i++)
    {   
        cnt+=x;
    }   
    return cnt;
}

int main(){

    printf("%d %d\n", foo(1), bar(1));
    printf("%d %d\n", foo(UINT_MAX), bar(UINT_MAX));
    return 0;
}

雖然這些函式寫得有些彆扭，不過 `foo` 和 `bar` 看起來是等價的函式，兩個 printf 各會印出兩個相同的數值，對嗎?

當然不對，`foo` 和 `bar` 的等價必須建立在 `x + 1` 總是大於 `x` 這個前提上，然後回想一下我們剛剛所說的定義行為: `UINT_MAX + 1` 會得到 0，換句話說，當 `x` 的輸入是 `UINT_MAX + 1` 時，`foo` 並不會執行到 `cnt+=x` 這一步驟。雖然這個行為是標準中定義清楚的，但是寫程式的人可能當下忽略了這點，導致所謂的『明確定義但非預期』的 overflow。

### 未定義行為的 overflow

對於有號整數的運算，許多類型的組合就是沒有明確定義的了，例如有號整數間的相加減 overflow，對一個負整數進行位元左移(left shift)等，這些都是在標準中沒有定義行為的。

例如以下的例子，在開啟優化的參數下，兩個 printf 是否會印出相同的結果呢? 不彷嘗試看看。

int foo ( int x) {
    return ( x+1 ) > x ;
}

int main ( void ) {
    printf ("% d\n" , ( INT_MAX+1 ) > INT_MAX );
    printf ("% d\n" , foo ( INT_MAX ));
    return 0;
}

值得注意的是，這些未定義行為的 overflow 導致的錯誤可能不容易被立即發現(例如測試階段)，並可能透過多種不同的形式發生。包含隨優化技術進步才產生的錯誤，隨編譯器類型或者版本調整而產生的錯誤。或者，有些時候撰寫程式的人會依賴於特定編譯器所標準化的語法(例如 Implementation defined 的語法)。除此之外，使用的語言標準版本本身的不同，甚至是 C 與 C++ 標準上的不同，也是經常誤觸的地雷。

## 為甚麼不定義 signed integer overflow 的行為?

已定義行為的 unsinged integer 很容易可以被接受，不過你可能會懷疑給 singed integer 的算術運算定為未定義行為，看起來並沒有合適的理由。

當然有了，[CppCon 2016: Chandler Carruth “Garbage In, Garbage Out: Arguing about Undefined Behavior..."](https://www.youtube.com/watch?v=yG1OZ69H_-o&t=2357s&ab_channel=CppCon) 的影片片段中給我們展示了一個相當有趣的範例。


圖中的函式會將 `block` 透過兩個傳遞進來的 `uint_32` 參數取值，並比較兩者是否相同，如果不同，則返回兩者的大小關係，否則將 `i1` 和 `i2` 加一，重複這個 pattern。對照產生的 assembly code 在右方。

如果我們把 `uint` 換成 `int` 結果會如何呢?


產生的 assembly code 現在明顯變少了!這之間到底發生了甚麼?

原理是這樣的，假設我們是在 64 位元的系統上，換句話說，`block` 是一個 64 位元的指標地址。而在 hardware 的觀點上，`block[i]` 的意涵是我們要取出 `block + i * sizeof(uint8_t)` 這個位址上的內容。我們只用 32 位元的整數來存取其中的位置，這很 make sense，畢竟 `block` 中可存取的 entry 數量可能在 32 位元整數的表達範圍中。但對於 `uint`，因為編譯器需要保證 `i` 符合 32 位元的 wraparound，直接把 `i` 加到 `block` 的結果作為 64 位元的地址使用是不正確的，因此編譯器需要額外的指令先處理 `i` 以確保行為符合規範。

但是對於 `int` 來說呢? 由於 overflow 是未定義行為，編譯器可以直接把 index 的 wraparound 當成是符合 64 位元規則的。這個假設給編譯器帶來的好處是，由於地址和 offset 都被當成 unsigned 64 bits 的行為處理，現在直接把 `i` 加到 `block` 的結果作為 64 位元的地址取值是符合規範的!

這個例子順帶向我們展示未定義行為存在的重要目的，無論是 signed integer overflow 或者其他: 透過語言標準中的刻意留空，以允許更激進的優化。

## 小結

Overflow 在軟體中是常見的錯誤類型，在相關的新聞底下，我常常會看到有人留言對此表示嗤之以鼻，並認為 overflow 錯誤是新手才會犯的等級。但在我看來，要精準的避開該種類型的錯誤並不如想像中的容易。就如本文中所闡述的，overflow 可以發生的情境各種各樣，需要對 C 語言標準具有一定程度的熟悉，但我相信在眾多 C 語言的撰寫者間，能對標準完全掌握的人應該還是少數。當然，為了瞭解 overflow 而直接把 C 語言的標準拿出來啃，我認為這是效率不彰的方法。不過，我們可以盡可能去認識 overflow 在實際應用中的案例，看看其他人都是在那些地方跌倒的，才能更準確地避開不願意碰上的非預期行為。

## Reference

[Understanding Integer Overflow in C/C++](https://www.cs.utah.edu/~regehr/papers/overflow12.pdf)