基于行為監(jiān)測的嵌入式操作系統(tǒng)堆棧溢出測試*

楊興達(dá),陳 燦,方 菱

(1.安徽大學(xué)物質(zhì)科學(xué)與信息技術(shù)研究院，安徽 合肥 230000；2.中國科學(xué)院合肥物質(zhì)科學(xué)研究院，安徽 合肥 230000)

1 引言

嵌入式操作系統(tǒng)是一種面向安全關(guān)鍵的系統(tǒng)，其堆棧安全至關(guān)重要。豐田的凱美瑞車型曾發(fā)生過嚴(yán)重的意外加速UA(Unintended Acceleration)事故，事故就是由于堆棧溢出造成TASKX死亡所導(dǎo)致的[1]。堆棧溢出通常難以捕捉，因為異常暴露的時間可能滯后于其發(fā)生時間。例如，任務(wù)P的堆棧溢出，并侵占優(yōu)先級較低的任務(wù)Q的私有堆棧，則至少在任務(wù)Q被調(diào)度并運行前，系統(tǒng)看起來一切正常。當(dāng)任務(wù)Q顯露異常時，開發(fā)者難以確定此異常是由任務(wù)Q本身造成的還是由其它任務(wù)的堆棧溢出引起的，更難以定位造成堆棧溢出的具體代碼[2]。另外，為了避免堆棧溢出，開發(fā)者經(jīng)常會無意識地過度分配堆棧，而嵌入式系統(tǒng)是一種資源受限的系統(tǒng)，堆棧資源的浪費將會增加隨機(jī)存取存儲器RAM(Random Access Memory)的成本。在理想的情況下，開發(fā)者為各任務(wù)堆棧預(yù)分配的空間應(yīng)該略大于該任務(wù)實際使用堆棧的極大值。但是，人為地預(yù)估堆?？臻g十分困難，也無法保證預(yù)估結(jié)果的準(zhǔn)確性。

2 相關(guān)研究

關(guān)于堆棧溢出測試，相關(guān)研究人員進(jìn)行了一定的研究。

Zhang等人[3]定義了一種用于描述函數(shù)間調(diào)用行為的樹形結(jié)構(gòu)，并通過在樹形結(jié)構(gòu)中提取極端樹的方式來計算堆棧使用的極大值，從而避免可能的堆棧溢出問題。這種方法雖然可以靜態(tài)地對系統(tǒng)堆棧進(jìn)行評估，但是其分析過程比較復(fù)雜，需要人為考慮所有的極端情形并繪制函數(shù)樹模型，且每種函數(shù)樹的模型都不盡相同，導(dǎo)致此方法在實際工程測試中不夠高效。

Xie等人[4]提出了一種算法，可以將堆棧溢出的檢測問題轉(zhuǎn)化為整數(shù)范圍的分析問題。該算法先使用函數(shù)定位模塊計算代碼檢測范圍，然后將調(diào)用函數(shù)與風(fēng)險函數(shù)庫中的函數(shù)進(jìn)行比對，以掃描檢測范圍內(nèi)所有的風(fēng)險函數(shù)，最后通過對風(fēng)險函數(shù)的參數(shù)進(jìn)行分析來準(zhǔn)確計算當(dāng)前函數(shù)所需堆棧是否會溢出。該算法仍具有一定的局限性，因為它十分依賴風(fēng)險函數(shù)庫。如果被調(diào)函數(shù)不在風(fēng)險函數(shù)庫中，或者造成堆棧溢出的只是一條賦值語句而非函數(shù)，那么該算法就會失效。

Choi等人[5]提出了一種基于靜態(tài)分析配置文件的堆棧最大值動態(tài)監(jiān)測方法。該方法首先通過分析可執(zhí)行與可鏈接格式ELF(Executable and Linkable Format)文件提取與函數(shù)相關(guān)的數(shù)據(jù)，然后使用深度優(yōu)先搜索DFS(Depth First Search)確定堆棧最大值，最后通過監(jiān)測堆棧最大值的地址是否被改寫來捕獲堆棧溢出。該方法雖然可以動態(tài)地發(fā)現(xiàn)堆棧溢出，但是不能定位溢出位置。

針對相關(guān)研究中存在的不足，本文提出了一種基于實時堆棧分配與回收行為監(jiān)測的動態(tài)堆棧測試方法。首先，靜態(tài)地確定堆棧行為測試點；接著在測試點上采用一套標(biāo)準(zhǔn)的數(shù)據(jù)采集與分析流程進(jìn)行堆棧監(jiān)測，無需對不同測試點進(jìn)行特殊改動，在測試效率上有所提高，并在靜態(tài)分析方法上進(jìn)行了動態(tài)補(bǔ)充；其次，通過插樁來覆蓋源代碼中所有的堆棧行為測試點，并不依賴于任何第三方庫，不會出現(xiàn)失效問題;最后，不僅可以通過堆棧指針SP(Stack Pointer)地址判定堆棧溢出，還能夠?qū)崟r定位發(fā)生溢出的源代碼，對堆棧溢出測試的功能性進(jìn)行了拓展。

3 堆棧行為動態(tài)監(jiān)測方法

本節(jié)將介紹任務(wù)堆棧分配與回收行為實時監(jiān)測方法的總體設(shè)計與具體實現(xiàn)。

3.1 相關(guān)技術(shù)概述

下面將簡單介紹后文所提及的相關(guān)技術(shù)。

(1)靜態(tài)測試與動態(tài)測試：在嵌入式軟件測試中，靜態(tài)測試是基礎(chǔ)，動態(tài)測試是必要補(bǔ)充[6]。靜態(tài)測試往往是通過提取源代碼編譯生成的匯編代碼或二進(jìn)制代碼中的一些特征進(jìn)行分析，或者構(gòu)建模型后對模型進(jìn)行測試驗證。比如Fang等人[7]先通過形式化方法建模并驗證模型，然后再根據(jù)模型開發(fā)測試用例生成器，對嵌入式實時操作系統(tǒng)進(jìn)行了高效的測試驗證。動態(tài)測試則是通過某種方式獲取程序運行時的軌跡信息進(jìn)行分析[8,9]。動態(tài)測試所發(fā)現(xiàn)的漏洞是軟件中實際存在的，不會誤報，并且動態(tài)測試不需要像靜態(tài)測試那樣進(jìn)行復(fù)雜的數(shù)據(jù)流分析[10]。

(2)軟件插樁技術(shù)：軟件插樁是一種在軟件運行時進(jìn)行的狀態(tài)分析技術(shù)，廣泛應(yīng)用于軟件質(zhì)量評價、漏洞挖掘、性能分析與優(yōu)化等領(lǐng)域中，是解決軟件執(zhí)行路徑收集、關(guān)鍵函數(shù)調(diào)用分析等問題的主要手段[11,12]。

(3)HOOK技術(shù)：HOOK是一種操作系統(tǒng)內(nèi)部的回調(diào)函數(shù)，會在特定的事件到來之際被回調(diào)執(zhí)行。

(4)控制器局域網(wǎng)絡(luò)CAN(Controller Area Network)協(xié)議：CAN是一種用于實時應(yīng)用的串行通信協(xié)議總線，可用于汽車中各種不同元件之間的通信。

(5)分布式處理：將位于不同地點或具有不同功能或擁有不同數(shù)據(jù)的多臺計算機(jī)通過通信網(wǎng)絡(luò)連接起來，協(xié)調(diào)地完成信息處理。

3.2 測試框架概述

本文方法首先靜態(tài)分析了源代碼中所有可能的測試點。對于堆棧溢出測試來說，測試點就是具有堆棧分配或回收行為的代碼行。接著，通過軟件插樁技術(shù)在測試點插入用于采集堆棧數(shù)據(jù)的樁函數(shù)接口。開發(fā)者在編寫代碼時就可以自行插樁，以減輕測試者的負(fù)擔(dān)，樁函數(shù)的插入邏輯和編碼行為類似于HOOK函數(shù)。

插樁后，樁函數(shù)應(yīng)在被測系統(tǒng)實際運行時動態(tài)收集測試點的堆棧數(shù)據(jù)并進(jìn)行實時分析。為了規(guī)避數(shù)據(jù)分析給操作系統(tǒng)帶來的額外工作負(fù)荷，本文方法采用了分布式處理的設(shè)計思想來進(jìn)行數(shù)據(jù)分析，即被測系統(tǒng)僅采集數(shù)據(jù)，數(shù)據(jù)分析的工作則交由另一臺機(jī)器負(fù)責(zé)。被測系統(tǒng)在完成數(shù)據(jù)采集后立即將數(shù)據(jù)傳送給上測試器UT(Upper Tester)，再由UT完成實時的數(shù)據(jù)分析和溢出判定工作。另外，測試數(shù)據(jù)的統(tǒng)計和堆棧溢出的報警服務(wù)也由UT提供。

因為本文方法的被測系統(tǒng)通過CAN進(jìn)行數(shù)據(jù)傳輸，其在傳輸超過8字節(jié)的數(shù)據(jù)時需要分包，為了進(jìn)一步降低數(shù)據(jù)傳輸對操作系統(tǒng)運行效率的影響，本文方法將采集到的數(shù)據(jù)壓縮成8字節(jié)長度的測試碼，具體的測試碼設(shè)計規(guī)則將在3.4節(jié)中介紹。最后，UT根據(jù)測試碼的設(shè)計規(guī)則來反向解析，得到實時的堆棧數(shù)據(jù)，并進(jìn)行堆棧溢出判定。當(dāng)堆棧溢出發(fā)生時，測試者可以通過UT實時發(fā)現(xiàn)異常，并根據(jù)測試點的信息來定位源代碼中造成堆棧溢出的確切位置。本文方法的測試流程如圖1所示，測試架構(gòu)如圖2所示。

徐進(jìn)步站在一個塔頭上,一點也不知道身后背包里一長截手紙垂下來了。上海女知青謝菲站在另一個塔頭上,用上海話朝他喊:“你把你那尾巴卷起來行不行,拖那么長尾巴,演大老鼠啊!”

Figure 1 Workflow diagram of the proposed method圖1 本文方法工作流程圖

Figure 2 Test frame of the proposed method圖2 本文方法測試框架圖

3.3 消除數(shù)據(jù)解析延遲的影響

測試碼由被測系統(tǒng)發(fā)送至UT顯然需要時間，且UT的解析反饋也會造成無法避免的延遲。為了消除延遲對測試的實時性影響，本文方法的測試碼包含了詳細(xì)的堆棧異常信息，其中包括發(fā)生異常的任務(wù)內(nèi)部函數(shù)編號，使得UT只依靠延遲收到的測試碼也能準(zhǔn)確定位到發(fā)生堆棧溢出的代碼位置。

3.4 基于堆棧結(jié)構(gòu)與行為確定測試點

本文方法中被測操作系統(tǒng)進(jìn)行任務(wù)堆棧分配時，會由高地址向低地址遞減分配，不同任務(wù)的私有堆?？臻g被靜態(tài)確定后，在物理地址上是連續(xù)的，如圖3所示。

Figure 3 Physical structure diagram of task stack圖3 任務(wù)堆棧物理結(jié)構(gòu)圖

每一塊任務(wù)私有堆棧都是由3個區(qū)域組成的，如圖4所示。A區(qū)域用于存放靜態(tài)數(shù)據(jù)，如普通指針、數(shù)組和常量等；B區(qū)域是任務(wù)的內(nèi)部函數(shù)被調(diào)用時所申請的一塊空間，可以在被調(diào)用函數(shù)返回后回收再利用；C區(qū)域只有一個魔術(shù)數(shù)字，被用作堆棧溢出檢測。其中，B區(qū)域的F1和F2是2個不同的函數(shù)，F(xiàn)2在F1的調(diào)用返回后重用了F1的堆?？臻g。F1.1是F1內(nèi)部調(diào)用的一個函數(shù)，其堆棧是緊接著F1的棧頂分配的。圖4中的P1、P3、P5是具有堆棧分配行為的測試點，P2、P4則是具有堆?；厥招袨榈臏y試點，操作系統(tǒng)各任務(wù)中的每個測試點都需要被監(jiān)測。另外，中斷服務(wù)程序ISR(Interrupt Service Routines)的堆棧行為與普通函數(shù)一致。對于A區(qū)域來說，其堆棧的分配行為在編譯器編譯完成后就已經(jīng)確定了，故A區(qū)域只需要一個測試點就可以監(jiān)測整個靜態(tài)數(shù)據(jù)區(qū)的堆棧情況。

Figure 4 Example of task stack allocation and reuse behavior圖4 任務(wù)堆棧分配與復(fù)用行為示例

在測試點插樁后，樁函數(shù)會將相應(yīng)的測試碼通過CAN發(fā)送出去，每個任務(wù)都需要額外承擔(dān)發(fā)送測試碼的工作，所以每個任務(wù)的執(zhí)行時間會加長，并且執(zhí)行用時與測試點數(shù)量成正比。因此，本文通過一個全局宏開關(guān)來控制測試點樁函數(shù)的有效性，只有在測試模式時，宏開關(guān)才會被打開，樁函數(shù)才會得到執(zhí)行。

3.5 堆棧數(shù)據(jù)壓縮與測試碼設(shè)計

測試碼需要記錄各種不同的測試資源，本文方法將測試碼的8字節(jié)作為8個數(shù)位以最大范圍地表示這些資源。

操作系統(tǒng)中每個任務(wù)的堆?？臻g都是靜態(tài)分配的，從任務(wù)堆棧的起始地址(棧底，高地址，變量名為BOS)計算出其結(jié)束地址(棧頂，低地址，變量名為TOS)。因此，測試碼需要記錄BOS，而任務(wù)堆棧的靜態(tài)分配大小是已知的，無需記錄。另外，測試碼還需記錄當(dāng)前任務(wù)SP的實時地址，用于判定堆棧是否溢出，正常堆棧的SP應(yīng)該在[BOS,TOS]。最后，測試碼還應(yīng)記錄任務(wù)中實時調(diào)用的函數(shù)信息，以在堆棧溢出時確定源代碼中發(fā)生異常的具體位置。鑒于某些函數(shù)簽名十分冗長,本文方法為各任務(wù)中的函數(shù)建立了映射，以數(shù)字而非字符串來標(biāo)識不同的函數(shù)，使得測試碼能夠以較大的進(jìn)制在有限的數(shù)位上表示更大的數(shù)據(jù)范圍。測試碼中各數(shù)位的職能信息如表1所示。另外，被測系統(tǒng)中的堆棧地址都具有0x40000000大小的固定偏移，為了壓縮數(shù)位空間，本文方法在采集堆棧地址信息后會移除偏移，以縮小數(shù)據(jù)范圍。例如，UT接收到的16進(jìn)制測試碼“10 5C 10 04 30 30 30 34”表示當(dāng)前任務(wù)已經(jīng)回收了編號為4的函數(shù)所申請的堆?？臻g，并且當(dāng)前SP的地址為0x40001004，當(dāng)前任務(wù)的堆棧上界為0x4000105C。

Table 1 Bit mapping table of test code

3.6 UT設(shè)計

UT接收到測試碼后，會解析測試碼并得到各個數(shù)位的信息。被測系統(tǒng)中測試所需的有效信息都應(yīng)在UT中備份，這樣UT在進(jìn)行數(shù)據(jù)分析時無需被測系統(tǒng)介入。另外，UT除了監(jiān)測堆棧溢出，還需要比對任務(wù)在調(diào)用函數(shù)前后的SP記錄，以保證堆?；厥盏恼_性。如果某測試點的SP在堆棧分配前后不一致，則說明堆?；厥者^程出現(xiàn)了異常，此時UT不能直接定位異常代碼，測試者需要排查其余任務(wù)的堆棧溢出異常來確定此回收異常的原因。

4 實驗與分析

本文通過對基于MPC5748G芯片的車載遠(yuǎn)程信息處理器T-BOX(Telematics BOX)系統(tǒng)進(jìn)行堆棧溢出測試，發(fā)現(xiàn)了如下問題:在1 ms周期性任務(wù)中，雖然沒有發(fā)生堆棧溢出，但是其堆棧被靜態(tài)分配得過大，造成了系統(tǒng)資源的浪費;在500 ms周期性任務(wù)和全球定位系統(tǒng)GPS(Global Positioning System)任務(wù)中，利用本文方法定位到了3處堆棧溢出。

具體地，在500 ms任務(wù)的數(shù)據(jù)打包函數(shù)中，開發(fā)者申請了一塊數(shù)組空間用于業(yè)務(wù)數(shù)據(jù)采集，當(dāng)數(shù)組容量達(dá)到閾值時會打包上傳當(dāng)前數(shù)據(jù)并清空數(shù)組以復(fù)用。但是，程序在擦除舊數(shù)組時發(fā)生了問題，導(dǎo)致數(shù)組前10個索引上的數(shù)據(jù)沒有被清除。隨著系統(tǒng)的持續(xù)運行，未被清除的垃圾數(shù)據(jù)越積越多，最終造成了任務(wù)堆棧溢出，系統(tǒng)被強(qiáng)制復(fù)位，RAM數(shù)據(jù)全部丟失。本文方法準(zhǔn)確地定位到了這個異常，并且發(fā)現(xiàn)此異常溢出的數(shù)據(jù)覆蓋了與500 ms任務(wù)堆棧相鄰的任務(wù)中的部分?jǐn)?shù)據(jù)。GPS任務(wù)中的1處堆棧溢出則是由于函數(shù)遞歸調(diào)用嵌套太深導(dǎo)致的，因為開發(fā)者在靜態(tài)分配任務(wù)堆棧時忽略了遞歸與ISR所需的堆?？臻g，溢出直接造成了系統(tǒng)崩潰。另外，開發(fā)者違反了MISRA-C標(biāo)準(zhǔn)，該標(biāo)準(zhǔn)明令禁止任何直接的和間接的遞歸函數(shù)調(diào)用。

在修正了堆棧異常的代碼后，500 ms任務(wù)和GPS任務(wù)實際使用的堆棧極值分別為228和164。這2個任務(wù)中共有10個由極端環(huán)境觸發(fā)的硬件保護(hù)函數(shù)未被執(zhí)行，導(dǎo)致測試點未觸發(fā)完全。通過估計并補(bǔ)償這部分函數(shù)所需的堆?？臻g，本文方法最終將500 ms任務(wù)和GPS任務(wù)靜態(tài)分配的堆棧大小優(yōu)化至242和190。

測試發(fā)現(xiàn)的全部堆棧異常信息如表2所示；操作系統(tǒng)中部分任務(wù)堆?？臻g的靜態(tài)分配值和實際使用極大值對照如圖5所示；測試統(tǒng)計數(shù)據(jù)和相關(guān)優(yōu)化如表3所示。

Figure 5 Comparison diagram of actual space used by task stack圖5 任務(wù)堆棧實際使用空間對照圖

Table 2 Exception information table of task stack表2 任務(wù)堆棧異常信息表

Table 3 Statistics table of test data

5 結(jié)束語

本文針對嵌入式操作系統(tǒng)的堆棧安全問題，提出了一種基于實時堆棧分配與回收行為監(jiān)測的動態(tài)堆棧溢出測試方法。該方法不依賴于任何第三方庫，且不會產(chǎn)生誤報，解決了嵌入式操作系統(tǒng)堆棧溢出測試的實際工程問題，在實驗中精確定位到了3處堆棧異常，并檢測到1處受其它任務(wù)堆棧溢出影響而導(dǎo)致的數(shù)據(jù)覆寫異常。實驗結(jié)果表明，使用該方法動態(tài)監(jiān)測嵌入式操作系統(tǒng)中的實時堆棧溢出問題是可行且有效的。另外，本文的測試結(jié)果可以指導(dǎo)操作系統(tǒng)任務(wù)堆棧的靜態(tài)分配。通過對全部6個操作系統(tǒng)任務(wù)插入232個測試點，本文方法共監(jiān)測了232個函數(shù)，并在測試后對異常代碼進(jìn)行了修正，對靜態(tài)分配過大的堆?？臻g進(jìn)行了優(yōu)化。最后，將1 700個雙字的任務(wù)RAM優(yōu)化到了1 071，即壓縮至原RAM空間的63%，開發(fā)者可以利用空余出的堆棧為操作系統(tǒng)增添一些新任務(wù)，或者更換RAM更小的設(shè)備以降低硬件成本。在未來，重點研究一種自動化的插樁工具，用于改善開發(fā)者或測試者需要主動執(zhí)行代碼插樁的情形，以提高測試效率。