# OVERFLOW
## 算數溢位
算術溢位(arithmetic overflow)，通常直接簡稱overflow，當你目前使用的這塊記憶體空間不足以容納你要運算的數字，就會發生。而如果是有號數(正負號)，數字小於這個記憶體能儲存的最小值，則是叫做underflow。
什麼意思呢？請看以下程式碼：
```clike=
int foo;
foo = 2147483648;
printf("%d", foo);
```
```
輸出結果：-2147483648
```
目前的C編譯器預設int(整數)型別的變數，所能儲存的資料量為4個byte。一個byte = 8 bits，所以說4*8=32，他可以儲存32個二進位的數字。而這段程式碼宣告的int是有號數，所以最高位元數字用來表示這個數字的正負，當它是0的時候表示正數，1的時候表示負數。
例如：
1000 0000 0000 0000 0000 0000 0000 0001 = 1 - (2^31) = -2,147,483,647
1111 1111 1111 1111 1111 1111 1111 1111 = 1 + 2 + 4 + 8 + 16 + ...... - (2^31) = -1
這裡我們先快速學習一下二進位換算十進位的方式：
好，所以上面的程式碼發生了什麼事？
第一行，我們宣告了一個名字叫做"foo"的變數(它是int型別的變數，只能儲存32個bits，而且是有號數)。
```clike=
int foo;
```
第二行，我們硬是在這個變數裡塞進了大於它的最大值的數值。
```clike=
foo = 2147483648;
```
這邊解釋一下，預設的有號整數(signed integer)最大值為：
0111 1111 1111 1111 1111 1111 1111 1111 = 1 + 2 + 4 + 8 + 16 + ...... + (2^30) = (2^31) - 1 = 2,147,483,647
第三行，輸出變數裡的數值到螢幕上。(那個%d的意思是"我要以十進位整數的方式顯示它")
```clike=
printf("%d", foo);
```
這個時候顯示的數字就會依照編譯器不同而改變，但總之不會是你預期的結果。
順帶一提，signed int的最小值為：
1000 0000 0000 0000 0000 0000 0000 0000 = -(2^31) = -2,147,483,648
在這個例子中，塞進了大於最大值的數值之後，顯示出來的反而是最小值。
## 堆疊溢位
堆疊溢位(stack overflow)，則是另一個C語言新手很容易……還是應該說一定會犯過的錯誤？
我們看一下[維基百科](https://zh.wikipedia.org/wiki/%E5%A0%86%E7%96%8A%E6%BA%A2%E4%BD%8D)的解釋：
> 堆疊溢位（英語：stack overflow）在電腦科學中是指使用過多的記憶體時導致呼叫堆疊產生的溢位[1]，也是緩衝區溢位中的一種。堆疊溢位的產生是由於過多的函式呼叫，導致使用的呼叫堆疊大小超過事先規畫的大小，覆蓋其他記憶體內的資料，一般在遞迴中產生。堆疊溢位很可能由無限遞迴（Infinite recursion）產生，但也可能僅僅是過多的堆疊層級。
其實我覺得維基寫得很清楚，這邊就針對專有名詞大概解釋一下。
### 函式呼叫
函式呼叫(function call)，首先必須知道函式是什麼。
```clike=
int foo(int a)
{
return a + 1;
}
int main()
{
printf("%d", foo(2));
}
```
```
輸出結果：3
```
上面這段code中，我們宣告了一條叫做foo的函式，它需要你在呼叫時輸入一個叫做a的整數作為參數，並且會回傳一個a+1的數值給你。例如你丟了a=2給它，它就會給你3。等同於數學中的方程式 `f(x) = x + 1`。
而function call就只是這個呼叫的動作──請看第八行的`foo(2)`，這幾個字的意思就是「我要呼叫foo函式，並且給它一個參數2」。也就是在 `f(x) = x + 1` 中，將x帶入2，變成 `f(2) = 2 + 1`。
### 遞迴
遞迴(recursion)，我們在初學程式的時候常常被教授說這東西很危險，不要用XD
它基本上就是「在函式當中呼叫自己」的一種用法。
例如：
```clike=
int foo()
{
return foo();
}
```
而這段程式碼就是一個絕對會引發stack overflow的範例。
遞迴的應用，最經典的有計算階乘與尋找最大公因數。
這裡以計算階乘來做示範：
```clike=
unsigned int factorial(unsigned int n)
{
if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
```
假設n=5，這段程式碼會在進行到第六行時執行5＊factorial(4)，接著它會暫時把手邊的工作擱置，先去執行factorial(4)；在factorial(4)執行到第六行時，又會去執行factorial(3)……以此類推，一直到執行factorial(1)的時候，因為它符合第三行`if n == 1`這個條件(雙等於是判斷左值是否等於右值的意思)，所以它會直接回傳1這個數值回去。
回去哪裡呢？回去factorial(2)，執行2＊factorial(1)這個動作，而factorial(1)已經計算完並得到1這個數值，所以這裡會是2＊1=2，並且回傳2這個數值；再來就會回到factorial(3)，執行3＊factorial(2)，也就是3＊2……以此類推，一直到回去最初的factorial(5)時，後面那坨東西應該會是4＊3＊2＊1=24，所以這裡計算並回傳一個5＊24=120，函式就結束了，我們算出了一個5階乘。
一個很重要的點是，n會在每次call function時-1，減到n=1時這支函式就不再繼續call自己──這個"條件"使它可以免於陷入無限遞迴。如果無法觸發這個條件，或是一開始就沒設定條件，它就會永無止盡地call自己，造成stack overflow。
### 堆疊
堆疊(stack)，這裡讓我們回過頭看一下上一段的內容：
> 假設n=5，這段程式碼會在進行到第六行時執行5＊factorial(4)，**接著它會暫時把手邊的工作擱置**，先去執行factorial(4)……
請看粗體的部分，這裡提到了你的程式會暫時擱置手邊的工作。那麼擱置的工作該何去何從？它會被存進堆疊裡。
準確來說是它們的記憶體位址會被存進堆疊裡，當目前的函式執行完畢後，程式會去堆疊查看前一個函式的位址在哪，然後回到那裡去。
所以當你的程式出錯，無限增加堆疊時，stack overflow就發生了。這可能會導致你的程式去調用了他不該碰到的記憶體區塊，例如碰到保留給作業系統用的區域導致當機，或是碰到存有使用者隱私資料的記憶體區段導致資安問題──當然現在的編譯器會防呆，如果發生stack overflow，它會強制中止你的程式。
## 緩衝溢位
緩衝溢位(buffer overflow)，不同於前兩種溢位只是單純的程式設計BUG，buffer overflow就是一種確實出自惡意的攻擊行為了。
前面提過C語言當中的變數都有其儲存資料量的限制，其中儲存字串的變數是必須在宣告時就一併宣告它的記憶體大小的。
例如：
```clike=
char text[] = "hello";
```
這個字串的長度就會是5個字母+一個結尾符號=6個byte。
buffer overflow簡單來說是刻意塞進超過字串長度的內容，此時你輸入的文字就有機率覆蓋掉原先stack中的其他資料，惡意使用的話有可能進一步改變整支程式的執行。(通常是以[Shellcode](https://zh.wikipedia.org/wiki/Shellcode)方式來進行)
我曾經在觀察IPS(入侵預防系統)的LOG時看過幾次進行這種攻擊的封包，它偵測的準則是封包payload中出現"0x0C0C0C0C"字串。這個攻擊手法叫做[Heap Spray](https://blog.csdn.net/magictong/article/details/7391397)，~~我要老實說我其實也沒完全弄懂這個手法。~~
關於buffer overflow，更清楚的解說：[[Day23] 攻擊行為－緩衝區溢位 Buffer Overflow](https://ithelp.ithome.com.tw/articles/10188599)
Sign in with Wallet
Connect another wallet