張西超，郭向英

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

一種用于分析MCS-51目標碼堆棧深度的方法

張西超，郭向英

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

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

MCS-51; 目標碼; 堆棧分析; 堆棧深度

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

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

1 堆棧深度分析方法

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

1.1MCS-51系列處理器的堆棧特點

MCS-51的堆棧位置是可編程的，棧指針SP是一個8位專用寄存器，指示堆棧頂在內(nèi)部RAM塊中的位置.系統(tǒng)復(fù)位后，SP被初始化為07H，使得堆棧事實上默認由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等指令時，SP值將自動增加或減少.

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

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

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

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

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

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

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

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

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

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

1.3子程序堆棧深度分析

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

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

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

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

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

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

表1 子程序路徑

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

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

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

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

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

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

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

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

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

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

2.1不確定因素分析

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

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

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

REL: PUSH A

DJNZ R0, REL

(4)直接改變SP指令：在MCS-51系統(tǒng)中，有一些可以改變SP值的指令，如MOV、INC、ANL等指令，均可以修改SP的值.由于本文介紹的方法為子程序計算出的堆棧深度是相對值，即相對子程序入口點的堆棧深度.當子程序中包含直接改變SP的指令時，無法確定與入口間的相對值，因此不能用該方法.但MOV SP,#data指令僅在主程序中時，該方法依然適用.因為主程序入口堆棧始終為0，相對堆棧深度即實際的堆棧深度，因此依然可以使用該方法進行分析.

2.2應(yīng)對措施

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

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

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

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

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

3 中斷對堆棧的影響

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

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

(1)軟件使用了一個級別的中斷

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

(2)軟件使用了兩個級別的中斷

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

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

4 實驗驗證

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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

[2] 劉通平.棧溢出的動態(tài)檢測技術(shù)[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系列單片機原理及應(yīng)用[M].北京：北京航空航天大學(xué)出版社，1989，21-22

[5] 常碩, 趙彬, 辛文逵.抽象解釋技術(shù)在嵌入式軟件測試中的應(yīng)用[J].中國測試技術(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—)，男，河南人，工程師，研究方向為嵌入式軟件虛擬測試平臺技術(shù)(e-mail：xichaozhang@163.com).

TP31

A

1674-1579(2010)02-0047-04