張西超，郭向英

(北京控制工程研究所，北京 100190)

一種用于分析MCS-51目標(biāo)碼堆棧深度的方法

張西超，郭向英

(北京控制工程研究所，北京 100190)

在嵌入式軟件中，針對(duì)目標(biāo)碼的堆棧分析是堆棧檢查的常用手段.提出了一種用于MCS-51系列處理器目標(biāo)碼的堆棧深度分析方法，該方法可分析最壞情況下的堆棧深度，并考慮了不同優(yōu)先級(jí)下中斷服務(wù)程序?qū)Χ褩５挠绊?利用該方法可開發(fā)出分析MCS-51目標(biāo)碼的堆棧分析工具，其分析結(jié)果對(duì)堆棧安全檢查和優(yōu)化具有參考意義.

MCS-51; 目標(biāo)碼; 堆棧分析; 堆棧深度

在嵌入式系統(tǒng)中，堆棧溢出往往會(huì)給系統(tǒng)造成致命的危害[1].檢查堆棧深度的方法可分為動(dòng)態(tài)和靜態(tài)兩類.動(dòng)態(tài)方法[2]是運(yùn)行被測(cè)軟件，測(cè)得的最大堆棧深度通常小于軟件的實(shí)際最大堆棧深度[3].靜態(tài)方法是在不運(yùn)行被測(cè)軟件情況下，分析堆棧深度，是一種更為可靠的方法.文獻(xiàn)[3]所述的堆棧分析方法采用了遞歸計(jì)算方法，根據(jù)數(shù)據(jù)流遞歸分析每個(gè)地址的堆棧深度，從而確定目標(biāo)碼的最大堆棧深度，但由于該方法未提取子程序信息，所以不能獲得每個(gè)子程序的最大堆棧深度以及最大堆棧深度形成的路徑，并且當(dāng)目標(biāo)碼包含動(dòng)態(tài)跳轉(zhuǎn)、不平衡循環(huán)等情況時(shí)無法使用該方法.

本文提出的方法不使用遞歸計(jì)算，在分析目標(biāo)碼最大堆棧深度的同時(shí)分析出各個(gè)子程序最大堆棧深度和最大堆棧深度形成的路徑，同時(shí)提出了目標(biāo)碼包含動(dòng)態(tài)跳轉(zhuǎn)、不平衡循環(huán)等情況時(shí)的應(yīng)對(duì)措施.

1 堆棧深度分析方法

該方法的分析思路是根據(jù)MCS-51系統(tǒng)處理器的堆棧結(jié)構(gòu)特點(diǎn)，先基于目標(biāo)碼構(gòu)造出子程序的調(diào)用關(guān)系圖，再逐個(gè)分析每個(gè)子程序的最大堆棧深度，最后求出整個(gè)程序的最大堆棧深度.

1.1MCS-51系列處理器的堆棧特點(diǎn)

MCS-51的堆棧位置是可編程的，棧指針SP是一個(gè)8位專用寄存器，指示堆棧頂在內(nèi)部RAM塊中的位置.系統(tǒng)復(fù)位后，SP被初始化為07H，使得堆棧事實(shí)上默認(rèn)由08H單元開始.由于MCS-51內(nèi)部RAM的08H～1FH單元分屬于工作寄存器區(qū)1～3，最好把SP值該置為1FH或更大的值[4].

但是，SP的初始值越大，可用的堆棧深度就越??；反之，SP的初始值越小，可用的堆棧深度就越深.在MCS-51的指令系統(tǒng)中，除了可以直接改變SP值的指令外，如MOV, SP, #1FH，在執(zhí)行PUSH、POP、各種子程序調(diào)用、中斷影響、子程序返回RET和中斷返回RETI等指令時(shí)，SP值將自動(dòng)增加或減少.

1.2子程序調(diào)用關(guān)系圖構(gòu)建方法

子程序調(diào)用關(guān)系圖的構(gòu)建過程是對(duì)目標(biāo)碼進(jìn)行遍歷，找出所有的子程序并構(gòu)建它們之間的調(diào)用關(guān)系.在MCS-51目標(biāo)碼中尋找子程序的關(guān)鍵點(diǎn)是尋找子程序調(diào)用指令，即ACALL和LCALL指令，指令的目的地址即為子程序入口地址.

這里采用了深度優(yōu)先的方法遍歷目標(biāo)碼，從程序的入口地址開始分析，遍歷所有分支，記錄每個(gè)遇到的ACALL或LCALL指令，取出其目的地址，該地址即為子程序的入口地址.以圖1所示為子程序分支結(jié)構(gòu)圖為例，按照深度優(yōu)先方法，先分析分支①②③⑤，其次分析分支①②③⑥，最后分析分支①②④.

圖1 子程序分支結(jié)構(gòu)圖

分析主程序后，便形成了最上層的調(diào)用關(guān)系圖，然后依次類推，再逐個(gè)分析次層子程序，直至不再有新的子程序產(chǎn)生，具體過程可概述如下：

1)采用深度優(yōu)先的方法從入口地址開始分析主程序，記錄其調(diào)用的子程序，分析完成后將主程序標(biāo)記為已分析，子程序均標(biāo)記為未分析；

2)遍歷沒有被分析的子程序，記錄其調(diào)用的子程序，分析完成后將該子程序標(biāo)記為已分析；

3)重復(fù)步驟2直至所有的子程序均被標(biāo)記為已分析；

4)根據(jù)記錄的信息，形成調(diào)用關(guān)系圖，最上層是主程序，最下層是扇出為0的子程序.

根據(jù)上述方法可快速構(gòu)建出子程序調(diào)用關(guān)系圖，為計(jì)算堆棧深度提供了基礎(chǔ).需要注意的是，分析某些目標(biāo)碼時(shí)上述方法會(huì)遇到障礙，下面介紹這些特殊情況及處理方法.

1.3子程序堆棧深度分析

在介紹子程序堆棧分析方法之前，先定義幾個(gè)表述子程序堆棧深度的名詞：路徑、路徑平衡度、路徑堆棧深度、子程序平衡度和子程序堆棧深度，含義分別如下：

1)路徑：從子程序入口開始，沿子程序內(nèi)的某一控制流執(zhí)行，直到出現(xiàn)RET(或RETI)指令，此時(shí)所經(jīng)歷的所有語句便組成了一條路徑.

2)路徑平衡度：相對(duì)于進(jìn)入路徑第一條語句時(shí)的堆棧深度，沿路徑執(zhí)行到最后一條指令時(shí)產(chǎn)生的堆棧偏移量便是該路徑的平衡度.如果路徑中含有子程序調(diào)用指令，被調(diào)子程序的平衡度計(jì)入本條路徑，如果路徑產(chǎn)生的偏移量為-2(RET和RETI指令對(duì)堆棧的影響均為-2)，則認(rèn)為這是一條平衡路徑.以表1中的路徑為例，其路徑平衡度計(jì)算方法是：-2=1+2+(-2)+(-1)+(-2)，等號(hào)右邊的數(shù)字分別是PUSH、ACALL、子程序SUBP平衡度、POP和RET對(duì)堆棧的影響.

3)路徑堆棧深度：從路徑的起點(diǎn)開始，執(zhí)行至終點(diǎn)過程中達(dá)到的最大堆棧深度，即為路徑堆棧深度.如果路徑中包括了函數(shù)調(diào)用指令，函數(shù)的堆棧深度也計(jì)入該路徑堆棧深度.以表1中的路徑為例，路徑堆棧深度計(jì)算方法是：8=1+2+5，等號(hào)右邊的數(shù)字分別是PUSH、ACALL指令對(duì)堆棧的影響及子程序SUBP的最大堆棧深度.

子程序平衡度：這里將子程序的平衡度定義為其所有路徑中路徑平衡度的最大值，如果該值為-2，那么這是一個(gè)平衡子程序.

子程序堆棧深度：即子程序所有路徑中路徑堆棧深度的最大值.

表1 子程序路徑

分析程序堆棧時(shí)，首先根據(jù)子程序調(diào)用關(guān)系圖確定子程序調(diào)用層次，當(dāng)一個(gè)子程序出現(xiàn)在不同的層次時(shí)，將其歸類在較低的層次，同時(shí)將其調(diào)用的子程序放在更低的層次.如子程序A調(diào)用了子程序B和C，子程序B調(diào)用了C，那么C應(yīng)該處于B的下層.

在子程序?qū)哟未_定后，先分析深層次子程序的堆棧，然后依次類推，直至主程序(主程序也可視為特殊的子程序，扇入為0).采用這種自下而上過程的優(yōu)點(diǎn)是分析一個(gè)子程序時(shí)，其所調(diào)用的子程序(如果扇出不為0)的平衡度和堆棧深度均已知，其對(duì)堆棧的影響可直接計(jì)入當(dāng)前所分析路徑，當(dāng)一個(gè)子程序被多次調(diào)用時(shí)，可避免重復(fù)分析.

與構(gòu)造調(diào)用關(guān)系圖的過程類似，分析堆棧深度仍采用深度優(yōu)先的方法.不同的是前者僅關(guān)注子程序調(diào)用指令，這里需要計(jì)算路徑中所有影響堆棧的指令，具體步驟如下：

1)根據(jù)深度優(yōu)先的原則，分析第一條路徑的堆棧深度，并記錄路徑上各條指令所在地址的堆棧深度值.該路徑分析結(jié)束后，設(shè)置子程序平衡度為第一條路徑的平衡度，子程序堆棧深度為第一條路徑的堆棧深度.

2)分析后繼路徑，如果該路徑上指令已經(jīng)被分析過，且在當(dāng)前路徑上該指令所在地址的堆棧值小于記錄的堆棧值，停止分析該路徑；否則更新該條指令所在地址的堆棧深度值，繼續(xù)分析該路徑上后繼指令.

3)根據(jù)步驟2)中分析出的路徑平衡度與堆棧深度更新函數(shù)的平衡度和堆棧深度.

4)重復(fù)步驟2)、3)直至分析完所有路徑.

這個(gè)過程的優(yōu)點(diǎn)是能夠盡早排除那些不可能產(chǎn)生最大堆棧深度的路徑，避免做無用分析，同時(shí)，由于按照調(diào)用層次自下而上分析子程序，每個(gè)子程序只須分析一次.但與構(gòu)建程序的調(diào)用關(guān)系圖一樣，在分析某些包含特殊情況的路徑時(shí)會(huì)遇到障礙.

2 不確定因素分析及應(yīng)對(duì)措施

前文已經(jīng)提到，有些特殊情況無法使用上面提到的方法進(jìn)行分析，下面介紹這幾種情況及解決方案.

2.1不確定因素分析

(1)動(dòng)態(tài)跳轉(zhuǎn)：MCS-51有一條間接長(zhǎng)轉(zhuǎn)移指令，格式為：JMP @A+DPTR.該指令的轉(zhuǎn)移地址由數(shù)據(jù)指針DPTR和累加器A的內(nèi)容相加形成，從目標(biāo)碼難以確定轉(zhuǎn)移地址，影響子程序調(diào)用關(guān)系圖的構(gòu)建，因此無法按照上面的步驟完成分析.

(2)遞歸：在構(gòu)建子程序調(diào)用關(guān)系圖時(shí)可以檢測(cè)出遞歸程序，但無法確定遞歸次數(shù)，因此無法計(jì)算其堆棧深度.如果一個(gè)子程序調(diào)用了一個(gè)遞歸子程序，調(diào)用遞歸程序的路徑無法確定堆棧深度，因此子程序的堆棧深度也無法確定，依次類推，主程序的堆棧深度也不能確定.

(3)不平衡循環(huán)：這里的不平衡循環(huán)指循環(huán)體不是堆棧平衡的，循環(huán)對(duì)堆棧的影響會(huì)隨著循環(huán)次數(shù)的變化而變化，如下面的循環(huán)，每循環(huán)一次堆棧就會(huì)加1，僅僅基于目標(biāo)碼做靜態(tài)分析難以確定其對(duì)堆棧的最終影響.如果函數(shù)包含了不平衡循環(huán)，那么將無法直接利用1.2節(jié)所介紹的方法對(duì)其進(jìn)行分析.

REL: PUSH A

DJNZ R0, REL

(4)直接改變SP指令：在MCS-51系統(tǒng)中，有一些可以改變SP值的指令，如MOV、INC、ANL等指令，均可以修改SP的值.由于本文介紹的方法為子程序計(jì)算出的堆棧深度是相對(duì)值，即相對(duì)子程序入口點(diǎn)的堆棧深度.當(dāng)子程序中包含直接改變SP的指令時(shí)，無法確定與入口間的相對(duì)值，因此不能用該方法.但MOV SP,#data指令僅在主程序中時(shí)，該方法依然適用.因?yàn)橹鞒绦蛉肟诙褩Ｊ冀K為0，相對(duì)堆棧深度即實(shí)際的堆棧深度，因此依然可以使用該方法進(jìn)行分析.

2.2應(yīng)對(duì)措施

針對(duì)上節(jié)提出的幾種不確定因素，可使用下面兩種方法解決：

(1)人工輔助：盡管上幾種不確定因素會(huì)影響分析，但都可以被檢測(cè)出來，因此可以使用人工輔助的方法.檢測(cè)到異常情況時(shí)，可由測(cè)試人員分析上下文，輔助堆棧分析程序完成后繼工作.為減少人工干預(yù)的工作量，可使用抽象解釋[5]方法強(qiáng)化該方法，增強(qiáng)易用性.

(2)編程規(guī)范約束：由于MCS-51堆棧資源非常有限，最大堆棧深度為128字節(jié)，再除去為數(shù)據(jù)區(qū)保留的空間，實(shí)際可用堆棧尚不足128字節(jié).因此，定義編程規(guī)范來約束開發(fā)人員，盡量避免使用可能造成堆棧溢出指令，是具有實(shí)際意義的.

動(dòng)態(tài)跳轉(zhuǎn)指令使程序的控制流變得不確定，因此應(yīng)該盡量少用；遞歸函數(shù)的每次遞歸調(diào)用都會(huì)使用子程序調(diào)用指令，即使堆棧深度增2，堆棧開銷很大；不平衡循環(huán)由于對(duì)堆棧的影響都循環(huán)次數(shù)的影響，很容易造成堆棧溢出；在子程序中直接修改SP時(shí)，在不同的地方調(diào)用該子程序會(huì)對(duì)堆棧產(chǎn)生不同的影響，也需要慎用.

鑒于上述幾種不確定因素對(duì)堆棧安全的危害性比較大，因此，可考慮制定編程規(guī)范對(duì)這幾種情況進(jìn)行約束，如一旦檢測(cè)到目標(biāo)碼中存在不平衡循環(huán)，可直接認(rèn)定軟件出現(xiàn)了問題[6].

3 中斷對(duì)堆棧的影響

中斷程序有其獨(dú)立的入口地址，在從主程序開始構(gòu)建調(diào)用關(guān)系圖時(shí)無法將中斷程序納入其中.但可以將其視為一個(gè)特殊的獨(dú)立程序，采用與主程序相同的分析過程單獨(dú)分析其最大堆棧深度.

MCS-51共有6個(gè)中斷，分別是外部中斷0、定時(shí)器0、外部中斷1、定時(shí)器1、串行口、定時(shí)器2，共2個(gè)優(yōu)先級(jí)，可通過軟件配置每個(gè)中斷的優(yōu)先級(jí)高低，低級(jí)中斷允許被高級(jí)中斷打斷.由于MCS-51的中斷服務(wù)程序沒有使用獨(dú)立堆棧空間，因此可以分為下面兩種情況計(jì)算軟件的最大堆棧深度：

(1)軟件使用了一個(gè)級(jí)別的中斷

最大堆棧深度=主程序最大堆棧深度+中斷服務(wù)程序堆棧深度的最大值；

(2)軟件使用了兩個(gè)級(jí)別的中斷

最大堆棧深度=主程序最大堆棧深度+高級(jí)中斷服務(wù)程序堆棧深度的最大值+低級(jí)中斷服務(wù)程序堆棧深度的最大值；

采用這種方法計(jì)算的缺點(diǎn)是沒有考慮中斷的開關(guān)情況，由于軟件中經(jīng)常會(huì)有關(guān)中斷事件，所以主程序和中斷服務(wù)程序堆棧深度同時(shí)達(dá)到峰值的情況可能并不會(huì)出現(xiàn).如果考慮開關(guān)中斷情況，平均來說，分析出的堆棧值比直接進(jìn)行堆棧疊加小35%[7].

4 實(shí)驗(yàn)驗(yàn)證

基于上面的論述，可知即使出現(xiàn)動(dòng)態(tài)跳轉(zhuǎn)等不確定因素，也可以人工輔助完成分析.作者正是基于該方法開發(fā)了堆棧分析工具，其分析流程大致如下：

1)選擇被分析軟件使用的中斷及優(yōu)先級(jí)；

2)構(gòu)建主程序的調(diào)用關(guān)系圖，如果構(gòu)建過程中出現(xiàn)了動(dòng)態(tài)跳轉(zhuǎn)，工具提示動(dòng)態(tài)跳轉(zhuǎn)的位置信息，等待人工確定跳轉(zhuǎn)地址；

3)如果人工確定了跳轉(zhuǎn)地址，那么繼續(xù)分析，直至構(gòu)建出完整的調(diào)用關(guān)系圖；否則分析失敗，退出；

4)計(jì)算主程序和各個(gè)子程序的堆棧深度，同時(shí)檢測(cè)是否有遞歸子程序，以及子程序中是否包含不平衡循環(huán)和直接修改SP的指令；

5)如果子程序中包含遞歸、不平衡循環(huán)或直接修改SP的指令，分析失敗，退出；

6)按照上面的步驟分析各中斷服務(wù)程序?qū)Χ褩５挠绊懀?/p>

7)根據(jù)中斷優(yōu)先級(jí)，將中斷服務(wù)程序?qū)Χ褩５挠绊懪c主程序的堆棧深度進(jìn)行累加，求出軟件最大堆棧深度.

表2是使用該工具分析4個(gè)MCS-51軟件所得出的統(tǒng)計(jì)數(shù)據(jù)，其中子程序總數(shù)包括了中斷服務(wù)程序，其中所示的例子中遞歸和不平衡循環(huán)沒有出現(xiàn)，動(dòng)態(tài)跳轉(zhuǎn)指令出現(xiàn)的次數(shù)也較低.盡管本文提出的方法無法自動(dòng)解決目標(biāo)碼中可能存在的不確定因素，但這些因素出現(xiàn)的次數(shù)較低時(shí)，仍可以使用人工輔助的方法彌補(bǔ)其不足.

表2 不確定因素指令統(tǒng)計(jì)

5 結(jié) 論

本文所提出的基于目標(biāo)碼的堆棧分析方法過程簡(jiǎn)單、易于實(shí)現(xiàn)，可從MCS-51程序的目標(biāo)碼中直接分析出最壞情況下軟件使用的堆棧深度，對(duì)堆棧安全性檢查和優(yōu)化具有參考意義.但值得注意的是，靜態(tài)方法分析堆棧的問題在于分析出的堆棧深度往往大于實(shí)際的堆棧深度，因?yàn)榉治龀龅穆窂娇赡軐?shí)際上并不會(huì)被執(zhí)行.因此，如果采用靜態(tài)方法分析出的堆棧值超過了允許范圍，不可盲目認(rèn)定是軟件堆棧溢出，需要根據(jù)產(chǎn)生最大堆棧深度的路徑信息確認(rèn)該路徑是否有效.

[1] Kleidermacher D N.Practical application of static analysis for embedded systems[J].Ada User Journal，2008, 29(1): 38-42

[2] 劉通平.棧溢出的動(dòng)態(tài)檢測(cè)技術(shù)[J].計(jì)算機(jī)科學(xué),2007,34(9):282-286

[3] Regehr J.Say not to stack overflow embedded systems design[Z].http:// www.embedded.com/columns/technicalinsights/47101892?_requestid=440562#

[4] 孫涵芳, 徐愛卿.MCS-51/96系列單片機(jī)原理及應(yīng)用[M].北京：北京航空航天大學(xué)出版社，1989，21-22

[5] 常碩, 趙彬, 辛文逵.抽象解釋技術(shù)在嵌入式軟件測(cè)試中的應(yīng)用[J].中國測(cè)試技術(shù),2007,33(6):93-95

[6] Dennis B, Niels D, Jens P.Static checking of interrupt-driven software[C].The 23rdInternational Conference on Software Engineering (ICSE) , Toronto, Canada ,May 2001

[7] Regehr J, Alastair R, Kirk W.Eliminating stack overflow by abstract interpretation[C].The 3rdInternational Conference on Embedded Software (EMSOFT), Philadelphia, PA，October 2003

AnApproachtoMCS-51ObjectStackDepthAnalysis

ZHANG Xichao, GUO Xiangying

(BeijingInstituteofControlEngineering,Beijing100190,China)

In an embeded software, an object code-based stack analysis is a common means of stack inspection.An analysis-based approach is proposed to analyse MCS-51 series processor’s object code.This approach can obtain the worst case stack depth and also takes into account effects of interrupt service routines on the stack under different priorities.Using this method, a stack analysis tool for MCS-51 object can be quickly developed and its analyzed results give a reference to stack safety inspection and optimisation.

MCS-51; object code; stack analysis; stack depth

2009-11-06

張西超(1983—)，男，河南人，工程師，研究方向?yàn)榍度胧杰浖摂M測(cè)試平臺(tái)技術(shù)(e-mail：xichaozhang@163.com).

TP31

A

1674-1579(2010)02-0047-04