複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/堆棧溢出/1231765
複製
複製成功

堆棧溢出

鎖定
堆棧（Stack）是一種抽象數據結構，是一組相同數據類型的組合，所有的操作均在堆棧頂端進行，具有“後進先出”的特性，即最後一個放入堆棧中的物體總是被最先拿出來。堆棧中兩個最重要的是PUSH（進棧）和POP（出棧）， PUSH操作在堆棧的頂部加入一 個元素，POP操作相反， 在堆棧頂部移去一個元素， 並將堆棧的大小減一。水滿則溢，堆棧是有一定容量限制的，當超出了該容量限制，就會發生溢出。 [1] 
中文名
堆棧溢出
外文名
stack overflow
應用學科
計算機科學
類    別
高級語言
技    術
過程和函數
內    存
連續內存
地    址
固定地址
領    域
計算機安全

目錄

  1. 1 堆棧溢出
  2. ▪ 內存中的堆與棧
  3. ▪ 溢出原理
  1. 2 原因分析
  2. 3 溢出危害
  3. ▪ 一般後果
  1. ▪ 安全威脅
  2. 4 防範措施

堆棧溢出堆棧溢出

堆棧溢出內存中的堆與棧

事實上，堆和棧是不同的數據結構概念，堆棧溢出也可細化為堆溢出和棧溢出兩種。棧有兩個特性：只能從棧的頂端存取數據；數據的存取符合後進先出的原則。所謂後進先出，其實就如同自助餐中餐盤在桌面上一個一個往上疊放，在取用時先拿最上面的餐盤，這是典型的堆棧概念的應用。 [1]  堆是一種樹結構，準確地説是一個完全二叉樹。 [2] 
在內存中，當一個可執行程序被裝入到內存時，主要包括兩個部分 ：代碼和數據。代碼會被裝入到內存中的代碼區，數據區又由 3 部分組成 ：①全局變量：根據其是否有初始值，被裝入到內存中的未初始化數據區和初始化數據區；②局部變量：在函數調用發生時存放在棧中；③動態內存空間：在程序運行時申請的動態內存空間存放在堆中。 [3] 
棧區(stack)是後進先出的結構，向低地址進行擴展，是一塊連續的內存區域，棧頂的地址和棧的最大容量是系統預先規定的，只要棧的剩餘空間大於所申請空間，系統將為程序提供內存，否則將報異常來提示棧發生溢出。棧空間是系統自動分配、釋放的，存放函數的參數值、局部變量的值等。一般來説，進棧的順序首先為主函數中的下一條指令（函數調用語句的下一條可執行語句）的地址先進棧，其次是參數由右往左依次進棧，最後是函數中的局部變量進棧，出棧順序與進棧順序相反，對於程序來説，出棧就意味着函數執行完畢，函數空間將被系統完全釋放掉。 [4] 
內存中的數據區與代碼區 內存中的數據區與代碼區 [4]
堆區一般由程序員自己申請，並指明大小，程序最後進行釋放，若程序員不釋放，程序結束時可能由操作系統回收（注意，如果是C/C++語言，程序不進行對空間回收，而Java語言中有專門的垃圾回收器進行回收），堆區與數據結構中的堆有所不同，分配方式類似於鏈表。堆區向高地址擴展。 [4] 

堆棧溢出溢出原理

堆棧溢出是説堆區和棧區的溢出，二者同屬於緩衝區溢出。從上面關於堆區和棧區的解釋可以看出，一旦程序確定，堆棧內存空間的大小就是固定的，當數據已經把堆棧的空間佔滿時，再往裏面存放數據就會超出容量，發生上溢；當堆棧中的已經沒有數據時，再取數據就無法取到了，發生下溢。需要注意的是，棧分為順序棧和鏈棧，鏈棧不會發生溢出，順序棧會發生溢出。 [5] 

堆棧溢出原因分析

堆棧尺寸設置過小、遞歸調用過深、函數調用層次過深等程序設計不當之處都可能導致堆棧溢出。 [6] 
1、 堆棧尺寸設置過小
由堆棧溢出的定義便可知，堆棧尺寸設置過小時，其能儲存的內容過小，容易發生溢出。 [6] 
2、遞歸層次太深或函數調用層次過深導致堆棧溢出
調用函數時，系統將為調用者構造一個由參數表返回地址組成的活動記錄，並將其押入到由系統提供的運行時刻棧的棧頂，然後將程序的控制權轉移到被調函數。若被調函數有局部變量，則在運行時刻，在棧的棧頂也要為其分配相應的空間，因此，活動記錄和這些局部變量形成了一個可供被調函數使用的活動結構。被調函數執行完畢時，系統將運行時刻棧的棧頂的活動結構退棧，並根據退棧的活動結構中所保存的返回地址將程序的控制權轉移給調用者繼續執行。由此可見，當遞歸層次太深時或者函數調用層次過深時會產生大量的活動記錄和局部變量，當超過棧的空間長度時，即發生溢出。 [7] 
例如C/C++語言中的無限遞歸：
int foo()
{
    return foo()   //重複無限的自我調用
}

(define (foo) (foo)) //這樣定義會造成死循環，但不會導致堆棧溢出
(define (foo) (+(foo)1)) //這樣的定義會產生堆棧溢出
3、動態申請空間使用之後沒有釋放
如果是C語言，由於沒有垃圾資源自動回收機制，因此，需要程序主動釋放已經不再使用的動態地址空間，如果不釋放，程序結束後該部分空間依然存在，還可以繼續訪問，也就是説這部分依然佔據着堆空間，剩餘的堆空間減少，就可能造成堆區溢出。 [3]  而如果是Java語言則因為有專門的垃圾回收器回收則不會有此問題。 [4] 

堆棧溢出溢出危害

從小處看，堆棧溢出會改變臨近堆棧的空間中的內容，從而導致程序運行異常，發生故障； [6]  從大處看，堆棧溢出和計算機網絡安全密切相關。堆棧溢出攻擊是計算機被攻擊的最為常見的一種形式，遠程網絡的攻擊絕大多數是針對堆棧溢出的漏洞，這種攻擊可以使得一個匿名的Internet用户有機會獲得一台主機的部分或全部控制權。 [8] 

堆棧溢出一般後果

堆棧溢出時會訪問不存在的RAM空間，造成代碼跑飛，這時無法得到溢出時的上下文數據，也無法對後續的程序修改提供有用信息。 [6] 

堆棧溢出安全威脅

堆棧溢出常見的攻擊類型有：修改函數的返回地址，使其指向攻擊代碼，當函數調用結束時程序跳轉到攻擊者設定的地址而不是原先的地址，修改函數指針，長跳轉緩衝區來找到一個可供溢出的緩衝區。 [8] 
攻擊者通過緩衝區溢出來重寫存儲在返回地址內的值從而達到控制程序的執行流程的目的。程序函數就像是一個大程序中的小程序。它是相對獨立的，對傳給它的數據做相應的處理然後將處理的結果返回給主函數。因為數據在一個函數內進行處理，因此它用棧作為數據的臨時存儲區域。當一個程序調用函數時，它將所有的數據壓棧，包括返回地址，如圖所示
發生函數調用時堆棧的情況 發生函數調用時堆棧的情況 [9]
。當函數被調用時，指令指針指向的就是函數的返回地址。這一點很重要，因為當被調用函數執行結束以後，主程序要回到被調用函數的返回地址處，接着執行下一條指令。返回地址存儲在RET中，當被調用函數執行結束，該返回地址傳遞給指令指針，以便主函數能夠回到函數調用之前的地址繼續執行。如果攻擊者能夠使緩衝區溢出並且重寫存儲在RET中的值，將惡意代碼的地址賦值給RET，那麼指令指針將指向惡意代碼，從而執行惡意代碼。
利用堆棧溢出攻擊原理示意圖 利用堆棧溢出攻擊原理示意圖 [10]
[9] 
堆是程序中動態分配的內存空間，因為程序在執行前所需要的內存數量是未知的，因此堆內存在程序需要時進行動態分配，不需要時進行動態釋放。堆和棧的主要區別在於，堆沒有像棧那樣的返回地址，這使得在棧溢出中用於控制程序執行流程的相關技術不可用。堆溢出可能導致重寫數據或者指向其他函數的指針。這樣，攻擊者可以重寫這些指針使其指向惡意代碼，而不是指向原來的內存區域。 [9] 
利用堆棧溢出攻擊計算機的最典型的例子是1988年利用fingerd漏洞進行攻擊的蠕蟲病毒。 [11] 

堆棧溢出防範措施

通常的代碼要設置堆棧緩衝區，最好能檢測堆棧運行形況，設置堆棧溢出檢測算法。對於遞歸引起的堆棧溢出，可以採用循環處理。 [6] 
針對堆棧溢出可能造成的計算機安全問題，通常有以下這些防範措施：
（1） 強制按照正確的規則寫代碼
（2） 通過操作系統使得緩衝區不可執行，從而阻止攻擊者植入攻擊代碼。但由於攻擊者並不一定要通過植入代碼來實現攻擊，同時linux在信號傳遞和GCC的在線重用都使用了可執行堆棧的屬性，因此該方法依然有一定弱點。
（3） 利用編譯器的邊界檢查來實現緩衝區的保護。該方法使得緩衝區溢出不可能出現，完全消除了緩衝區溢出的威脅，但代價較大，如性能速度變慢。
（4） 程序指針完整性檢查，該方法能阻止絕大多數緩衝區溢出攻擊。該方法就是説在程序使用指針之前，檢查指針的內容是否發生了變化。 [8] 
參考資料
展開全部 收起