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

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

1 引言

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

2 相關(guān)研究

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

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

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

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

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

3 堆棧行為動(dòng)態(tài)監(jiān)測(cè)方法

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

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

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

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

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

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

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

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

3.2 測(cè)試框架概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Table 1 Bit mapping table of test code

3.6 UT設(shè)計(jì)

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

4 實(shí)驗(yàn)與分析

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

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

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

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

Figure 5 Comparison diagram of actual space used by task stack圖5 任務(wù)堆棧實(shí)際使用空間對(duì)照?qǐng)D

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

Table 3 Statistics table of test data

5 結(jié)束語(yǔ)

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