一種組合式基于調(diào)用棧的程序切片方法

戚曉芳 周曉宇 徐曉晶 張迎周

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210096)

(2南京郵電大學(xué)計(jì)算機(jī)學(xué)院，南京 210003)

程序切片最初是由Weiser提出的一種程序調(diào)試技術(shù)，它通過計(jì)算發(fā)生故障(程序執(zhí)行出錯(cuò))語(yǔ)句的切片來(lái)分解原有程序，確定影響該語(yǔ)句執(zhí)行的語(yǔ)句集，并在該較小的語(yǔ)句集中查找和定位程序錯(cuò)誤，以達(dá)到縮小程序錯(cuò)誤排查范圍、方便程序調(diào)試的目的［1－6］.對(duì)程序的某次執(zhí)行而言，影響發(fā)生故障語(yǔ)句的語(yǔ)句實(shí)際上只與當(dāng)前調(diào)用上文相關(guān)，在遍歷程序依賴圖時(shí)，如果只考慮當(dāng)前調(diào)用上文，那么可去除靜態(tài)切片中因考慮所有調(diào)用上文而引入的冗余語(yǔ)句，提高分析精度.由于調(diào)用上文信息可從當(dāng)前調(diào)用棧中提取，因此本文將這種切片稱作基于調(diào)用棧的程序切片，該切片一般較小，平均約為靜態(tài)切片的30%，且因無(wú)需記錄、分析程序執(zhí)行信息，其精度和效率達(dá)到較好的折中，可進(jìn)行較為有效的程序調(diào)試［7－8］.

基于調(diào)用棧的程序切片計(jì)算一般通過遍歷程序系統(tǒng)依賴圖(SDG)獲?。?－9］，對(duì)大程序來(lái)說(shuō)，SDG龐大復(fù)雜，分析需耗費(fèi)大量的時(shí)間和空間.例如，采用Codesurfer2.1切片工具進(jìn)行實(shí)驗(yàn)，大于6萬(wàn)行的程序平均分析時(shí)間超過1 h，一些復(fù)雜度高的程序則需更長(zhǎng)時(shí)間，如分析4萬(wàn)行左右的Crypto5.2.1 程序時(shí)間超過 5 h［10］.為提高大程序調(diào)試的響應(yīng)速度，本文對(duì)傳統(tǒng)的基于SDG的切片方法進(jìn)行改進(jìn)，提出按需分析的策略，即通過僅分析程序中部分與切片標(biāo)準(zhǔn)相關(guān)的子程序，而不是所有子程序來(lái)提高分析效率，同時(shí)為實(shí)現(xiàn)上述分析策略，提出一種組合式的基于調(diào)用棧的程序切片方法.本文首先給出組合式依賴性分析方法，然后提出相關(guān)子程序分析算法以及組合式的基于調(diào)用棧的程序切片方法，最后給出結(jié)論.

1 組合式子程序依賴性分析

程序內(nèi)的依賴關(guān)系主要包括由控制條件引起的控制依賴和由訪問變量引起的數(shù)據(jù)依賴.程序依賴圖(，PDG)是一個(gè)有向圖，用二元組(S，E)表示，其中S為節(jié)點(diǎn)集，邊集E表示節(jié)點(diǎn)間的控制或數(shù)據(jù)依賴關(guān)系.順序程序中依賴關(guān)系具有傳遞性，子程序內(nèi)的靜態(tài)切片通過簡(jiǎn)單遍歷PDG獲得［9］.子程序間的靜態(tài)切片通過兩趟式遍歷系統(tǒng)依賴圖計(jì)算，SDG由各子程序的PDG通過添加調(diào)用節(jié)點(diǎn)、形參和實(shí)參輸入輸出附加節(jié)點(diǎn)以及調(diào)用邊、參數(shù)依賴邊和參數(shù)可傳遞邊等連接而成［9］，構(gòu)造SDG需一次性分析所有子程序.

組合式的子程序依賴性分析方法根據(jù)實(shí)際需要，分析與程序切片相關(guān)的部分子程序.該方法以子程序?yàn)榛痉治鰡挝?，各子程序依賴圖相對(duì)獨(dú)立，整個(gè)程序的依賴圖由各子程序的依賴圖組合而成，子程序的對(duì)外接口通過參數(shù)間的依賴關(guān)系實(shí)現(xiàn)［6］.根據(jù)子程序調(diào)用結(jié)束后參數(shù)值是否返回，可將參數(shù)分為讀參數(shù)、寫參數(shù)以及讀寫參數(shù)，其中讀參數(shù)指在子程序調(diào)用中作為引用性變量出現(xiàn)、其值不能返回的參數(shù)，寫參數(shù)指作為定義性變量出現(xiàn)、其值可返回的參數(shù)，讀寫參數(shù)指既作為定義性又作為引用性變量出現(xiàn)且其值可返回的參數(shù).

定義1 設(shè)fI，fO分別為子程序P的某讀參數(shù)和寫參數(shù)(當(dāng)該參數(shù)為讀寫參數(shù)時(shí)，fI可能與fO相同)，若對(duì)fO的定義直接或間接依賴于子程序P入口節(jié)點(diǎn)sentry定義的fI，則稱參數(shù)fO依賴于參數(shù)fI，記作PD(fI，fO)，將fO依賴的所有參數(shù)集合稱作fO的參數(shù)依賴集，記為PDS(P，fO).

定義2 設(shè)fO為子程序P的某寫參數(shù)，sexit為子程序P的出口節(jié)點(diǎn)，則子程序P關(guān)于參數(shù)fO的切片是在 sexit處影響 fO值的語(yǔ)句集，記為PSlice(P，fO).

在上述定義中，以〈sexit，{fO}〉為切片標(biāo)準(zhǔn)遍歷子程序P的依賴圖，直至子程序P的入口節(jié)點(diǎn)sentry(在sentry處定義所有的讀參數(shù)和讀寫參數(shù))，在sentry處所依賴的參數(shù)集合即為fO的參數(shù)依賴集.在很多情況下，子程序調(diào)用可能返回多個(gè)參數(shù)值，為區(qū)分對(duì)不同參數(shù)的定義和引用，在每個(gè)子程序調(diào)用處，為每個(gè)寫參數(shù)或讀寫參數(shù)添加一個(gè)實(shí)參附加節(jié)點(diǎn)，這些節(jié)點(diǎn)控制依賴于子程序調(diào)用語(yǔ)句.對(duì)每個(gè)實(shí)參附加節(jié)點(diǎn)s，設(shè)aO為s表示的實(shí)參，fO為相應(yīng)的形參，令s的變量定義集為Def(s)={aO}，變量引用集為并且 aI為 fI對(duì)應(yīng)的實(shí)參}.

根據(jù)形參間的依賴關(guān)系以及形參和實(shí)參之間的映射，可獲得實(shí)參之間的依賴關(guān)系(類似于SDG中的參數(shù)可傳遞邊)［9］，由此子程序調(diào)用語(yǔ)句可作為一般語(yǔ)句處理.在切片過程中，先進(jìn)行子程序內(nèi)切片，然后通過實(shí)參和形參之間的映射，對(duì)調(diào)用上下文中的子程序再作相應(yīng)的切片分析，從而實(shí)現(xiàn)以子程序?yàn)閱挝坏慕M合式分析策略.

2 相關(guān)子程序分析方法

為實(shí)現(xiàn)按需分析策略，需確定與切片標(biāo)準(zhǔn)相關(guān)的子程序集合，在程序依賴性分析前不可能也沒有必要精確確定這些子程序.為此，本文提出一種綜合利用控制流和調(diào)用棧信息保守估算相關(guān)子程序集的方法.

給定某程序P，其子程序調(diào)用圖(CG)用二元組〈N，Ec〉表示，其中N為節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)子程序，Ec為邊集，邊〈pi，pj〉表示子程序pi中調(diào)用了pj.

定義3 給定調(diào)用語(yǔ)句序列cs=(n0n1…nk)，若cs是由程序P在某次執(zhí)行過程中調(diào)用棧中的調(diào)用語(yǔ)句由棧底到棧頂順序排列而成的語(yǔ)句序列，則稱cs為程序P的一個(gè)調(diào)用棧狀態(tài).

在定義3中，稱返回cs棧頂元素nk的操作為cs的讀操作，記為Rd(cs)，稱彈出棧頂元素的操作為cs的取操作，記為 Del(cs)，其中 Rd(cs)=nk，Del(cs)=(n0n1…nk－1).

定義4 給定切片標(biāo)準(zhǔn)〈cs，s〉，其中 cs為某調(diào)用棧狀態(tài)，s為某語(yǔ)句，則基于調(diào)用棧cs關(guān)于s的切片是由程序中所有可能影響s在調(diào)用棧cs下執(zhí)行的語(yǔ)句集組成，記為Slice(cs，s).

由切片的定義可知，在切片標(biāo)準(zhǔn)之前執(zhí)行的語(yǔ)句才有可能影響切片標(biāo)準(zhǔn)語(yǔ)句的執(zhí)行，因此可直接獲得下列性質(zhì).

性質(zhì) 1 若語(yǔ)句 s′∈Slice(cs，s)，則 s′在 s之前執(zhí)行.

利用性質(zhì)1，通過計(jì)算在cs下s的所有可能的前驅(qū)所在的子程序集合作為相關(guān)子程序集，具體見算法1.

算法1 相關(guān)子程序集分析算法

輸入:切片標(biāo)準(zhǔn)〈cs，s〉，子程序調(diào)用圖CG和各子程序的控制流圖CFG.

輸出:與Slice(cs，s)相關(guān)的子程序集Q.

在算法1中，首先分析在切片標(biāo)準(zhǔn)以及當(dāng)前調(diào)用棧中調(diào)用語(yǔ)句的前驅(qū)，從中找出子程序調(diào)用節(jié)點(diǎn)對(duì)應(yīng)的子程序，放入集合Q1和工作表W1.W1中的子程序直接或間接調(diào)用其他子程序，通過遍歷子程序調(diào)用圖獲取這些被調(diào)子程序集合Q2.Q2中的子程序在切片標(biāo)準(zhǔn)執(zhí)行之前可能已全部執(zhí)行，需完全分析其中所有子程序的參數(shù)依賴關(guān)系.對(duì)Q中不在Q2中的子程序調(diào)用語(yǔ)句的參數(shù)依賴暫定為參數(shù)間完全依賴并作相應(yīng)標(biāo)記，以便在后續(xù)分析獲得相應(yīng)參數(shù)依賴關(guān)系后重新修改.

3 組合式的基于調(diào)用棧的程序切片

采用組合式的子程序分析方法計(jì)算基于調(diào)用棧的程序切片的具體算法見算法2.

算法2 組合式基于調(diào)用棧的程序切片算法

輸入:子程序依賴圖，切片標(biāo)準(zhǔn)〈cs，s〉.

輸出:關(guān)于〈cs，s〉的切片 Slice(cs，s).

算法2分為2個(gè)階段:第1階段以切片標(biāo)準(zhǔn)s為始點(diǎn)遍歷調(diào)用上文，即直接或間接調(diào)用切片標(biāo)準(zhǔn)所在子程序的PDG;第2階段遍歷第1階段所涉及子程序的調(diào)用下文，即被這些子程序所調(diào)用子程序的PDG.在第1階段，當(dāng)遍歷到實(shí)參附加節(jié)點(diǎn)時(shí)，進(jìn)行實(shí)參到相應(yīng)形參的映射;當(dāng)遍歷到子程序入口時(shí)，從調(diào)用棧的頂端依次向下找到對(duì)應(yīng)的調(diào)用語(yǔ)句，將形參映射為相應(yīng)的實(shí)參，并通過到達(dá)調(diào)用語(yǔ)句的變量定義集找到實(shí)參表達(dá)式中所使用變量的定義語(yǔ)句，上行遍歷.在算法2中，DD(sz，sy)表示sy數(shù)據(jù)依賴于sz，Ref(s)指s中引用的變量集合，In(s)指到達(dá)s時(shí)變量的定義位置集合.算法2對(duì)程序依賴圖進(jìn)行遍歷，其時(shí)間復(fù)雜度為O(n2)，與靜態(tài)切片的時(shí)間復(fù)雜度相同.

下面給出一個(gè)實(shí)例的C++源程序:

實(shí)例中除主函數(shù)main外還包含4個(gè)子程序Acc，Inc，Add和Prod，其子程序調(diào)用圖以及各子程序的PDG如圖1所示.在圖1(b)中，在Acc的調(diào)用處為實(shí)參s和i添加了A1和A2節(jié)點(diǎn)，在Prod調(diào)用處為返回值添加了A3節(jié)點(diǎn).在圖1(d)中，在Acc的調(diào)用處為a對(duì)應(yīng)的實(shí)參x添加了A4節(jié)點(diǎn)，在Inc的調(diào)用處為z對(duì)應(yīng)的實(shí)參y添加了A5節(jié)點(diǎn).在圖1(e)中，在Add的調(diào)用處為a對(duì)應(yīng)的實(shí)參z添加了A6節(jié)點(diǎn).圖1(f)中，在Inc的調(diào)用處為z對(duì)應(yīng)的實(shí)參k添加了A7節(jié)點(diǎn).

圖1 子程序調(diào)用圖及各子程序的PDG圖

下面以S15為例計(jì)算S15在不同調(diào)用棧狀態(tài)下的切片以及S15的靜態(tài)切片.由于子程序調(diào)用返回時(shí)相應(yīng)的調(diào)用語(yǔ)句已從調(diào)用棧中彈出，同一個(gè)調(diào)用棧狀態(tài)可能表示多個(gè)不同的調(diào)用語(yǔ)句歷史記錄.當(dāng)調(diào)用語(yǔ)句歷史記錄為〈S7S12〉和〈S7S12S13S12S7S12〉時(shí)，在這2個(gè)不同的執(zhí)行中調(diào)用棧狀態(tài)相同，兩者都用調(diào)用狀態(tài)〈S7S12〉表示.在實(shí)際執(zhí)行過程中，執(zhí)行S15時(shí)可能有多個(gè)調(diào)用歷史記錄，但只有3種調(diào)用棧狀態(tài)，即〈S7S12〉、〈S7S13S17〉和〈S9S24S17〉.

采用算法1計(jì)算關(guān)于〈(S7S12)，S15〉切片的相關(guān)子程序集為{main，Acc，Inc，Add}，其中 Acc，Inc和Add進(jìn)行完全分析，main進(jìn)行不完全分析.采用算法2計(jì)算切片時(shí)，第1階段訪問的節(jié)點(diǎn)集為{S15，S14，S12，S11，S7，S6，S3，A2，S4，S5，A1，S1}，其中A1和 A2為實(shí)參節(jié)點(diǎn).將{(Acc，{x})，(Acc，{y})}加入PC集，第2階段訪問的節(jié)點(diǎn)集為{A4，S11，S12，S13，A5，A6，S14，S15，S16，S17}.去除附加節(jié)點(diǎn)后，切片為{S1，S3，S4，S5，S6，S7，S11，S12，S13，S14，S15，S16，S17}.

類似地，〈(S7S13S17)，S15〉的切片為{S1，S3，S5，S6，S7，S11，S13，S14，S15，S16，S17}.〈(S9S24S17)，S15〉的切片為{S1，S9，S14，S15，S16，S17，S18，S20，S22，S24}.

同一個(gè)語(yǔ)句s可在不同的調(diào)用棧狀態(tài)下執(zhí)行，這些調(diào)用棧狀態(tài)可從程序的實(shí)際運(yùn)行收集，也可通過程序的靜態(tài)分析獲得，靜態(tài)分析的調(diào)用棧狀態(tài)可能不能在程序的實(shí)際運(yùn)行過程中出現(xiàn).搜索子程序調(diào)用圖中所有列為S的調(diào)用路徑，在每個(gè)調(diào)用路徑上組合各子程序中包含的調(diào)用語(yǔ)句，可靜態(tài)生成所有調(diào)用棧狀態(tài)，記這些調(diào)用棧狀態(tài)集合為 CSS(s).關(guān)于〈cs，s〉的切片 Slice(cs，s)和關(guān)于〈s〉的靜態(tài)切片Slice(s)之間存在下列關(guān)系.

性質(zhì)2 Slice(s)=∪cs∈CSS(s)Slice(cs，s).

證明 Slice(s)考慮所有的調(diào)用上文，每個(gè)調(diào)用上文對(duì)應(yīng)一個(gè)靜態(tài)調(diào)用棧狀態(tài)，CSS(s)包含了調(diào)用圖中所有靜態(tài)調(diào)用棧狀態(tài)，即所有的調(diào)用上文.因此，Slice(s)=∪cs∈CSS(s)Slice(cs，s).

靜態(tài)切片需考慮切片標(biāo)準(zhǔn)的所有調(diào)用上文，在圖1實(shí)例中，關(guān)于〈S15〉的靜態(tài)切片為{S1，S3，S4，S5，S6，S7，S9，S11，S12，S13，S14，S15，S16，S17，S18，S20，S22，S24}.

合并關(guān)于〈(S7S12)，S15〉、〈(S7S13S17)，S15〉和〈(S9S24S17)，S15〉的切片，可發(fā)現(xiàn)合并結(jié)果與關(guān)于〈S15〉的靜態(tài)切片的計(jì)算結(jié)果完全相同.同時(shí)，從上述切片結(jié)果可看出，同一個(gè)語(yǔ)句在不同的調(diào)用棧狀態(tài)下有不同的影響語(yǔ)句集.與傳統(tǒng)的考慮所有調(diào)用上文的子程序間切片相比，采用基于調(diào)用棧狀態(tài)的子程序間切片可更有效地幫助程序員進(jìn)行程序調(diào)試.

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

比較基于調(diào)用棧的程序切片與靜態(tài)程序切片的大小在文獻(xiàn)［8－9］已作了較為詳盡的研究.本文對(duì)幾個(gè)不同規(guī)模的程序進(jìn)行實(shí)驗(yàn)，初步研究了采用按需分析策略在提高基于調(diào)用棧的程序切片分析效率方面的影響.3個(gè)實(shí)驗(yàn)程序基本信息及Codesurfer分析時(shí)間如表1所示，其中Zlib1.2.3提供壓縮和解壓功能，BNBT是比特流追蹤軟件，Crypto 5.2.1 實(shí)現(xiàn)加密算法［11－13］.實(shí)驗(yàn)環(huán)境為 Windows XP，Visual Studio 2005，Codesurfer2.1，CPU 為 Intel Q840，主頻為 2.66 GHz，內(nèi)存為3 GB，采用 Codesurfer2.1對(duì)上述程序分析.表1中Codesurfer分析時(shí)間指程序通過Codesurfer2.1靜態(tài)分析后可直接進(jìn)行程序切片計(jì)算所需的時(shí)間，包含編譯、分析源程序生成控制流圖(CFG)、子程序調(diào)用圖以及系統(tǒng)依賴圖等時(shí)間，其中構(gòu)建系統(tǒng)依賴圖的時(shí)間占據(jù)了絕大部分分析時(shí)間［8］.

表1 程序基本信息及Codesurfer分析時(shí)間

根據(jù)Codesurfer2.1分析得到的CFG和子程序調(diào)用圖信息，實(shí)現(xiàn)了算法1.根據(jù)子程序調(diào)用圖靜態(tài)生成所有調(diào)用棧，同時(shí)以子程序出口語(yǔ)句作為切片標(biāo)準(zhǔn)，計(jì)算相關(guān)子程序數(shù)占程序中子程序總數(shù)的比值.表2給出了上述3個(gè)程序在不同調(diào)用棧深度下的相關(guān)子程序數(shù)占子程序總數(shù)的平均值，表中Zlib1.2.3，BNBT 和 Crypto5.2.1 的最大調(diào)用深度分別為7，17和13.由表2可看出，相關(guān)子程序集的大小與調(diào)用棧深度關(guān)系不大，沒有明顯的規(guī)律，而與程序本身有關(guān).在一般情況下，相關(guān)子程序數(shù)占總子程序數(shù)的比例較小，約為0.03% ～17.1%，尤其在大規(guī)模程序中，如 Crypto5.2.1中不大于1%.如果采用本文提出的組合式子程序切片方法，將使分析時(shí)間大大縮短.可以預(yù)測(cè)就某個(gè)切片標(biāo)準(zhǔn)而言，其平均分析時(shí)間約為原有時(shí)間的1%，即3 min左右.切片計(jì)算時(shí)間一般很短，可忽略不計(jì)，這將滿足使用基于調(diào)用棧程序切片在調(diào)試過程中快速響應(yīng)的需求.

表2 不同調(diào)用棧深度下平均相關(guān)子程序比例 %

5 結(jié)語(yǔ)

為提高分析效率，本文首先提出一種與切片標(biāo)準(zhǔn)相關(guān)的相關(guān)子程序分析算法，以實(shí)現(xiàn)按需分析策略，然后在此基礎(chǔ)上提出組合式基于調(diào)用棧的程序切片方法.該方法以子程序?yàn)橐蕾囆苑治鰡挝?，通過參數(shù)間的映射實(shí)現(xiàn)子程序間的分析.初步的相關(guān)子程序分析實(shí)驗(yàn)結(jié)果表明，本文提出的方法是可行的，可有效地提高大程序的分析效率，改善調(diào)試響應(yīng)時(shí)間.在今后的工作中，將在本文工作的基礎(chǔ)上，實(shí)現(xiàn)基于調(diào)用棧的組合式程序切片方法，并進(jìn)行相應(yīng)的實(shí)驗(yàn)分析.

References)

［1］ Weiser M.Program slicing［J］.IEEE Transactions on Software and Engineering，1984，10(5):498－509.

［2］ Xu B，Qian J.A brief survey of program slicing［J］.ACM SIGSOFT Software Engineering Notes，2005，30(2):1－36.

［3］Binkley D，Gold N，Harman M.An empirical study of static program slice size［J］.ACM Transactions on Software Engineering and Methodology，2007，16(2):1－30.

［4］ Harman M，Binkley D，Gallagher K，et al.Dependence clusters in source code［J］.ACM Transactions on Programming Languages and Systems，2009，32(1):1－33.

［5］戚曉芳，徐寶文，周曉宇.一種基于程序可達(dá)圖的并發(fā)程依賴性分析方法［J］.電子學(xué)報(bào)，2007，35(2):287－291.Qi Xiaofang，Xu Baowen，Zhou Xiaoyu.An approach to analyzing dependence of concurrent programs based on program reachability graph［J］.Acta Electronica Sinica，2007，35(2):287－291.(in Chinese)

［6］徐寶文，陳振強(qiáng)，周曉宇.基于依賴性分析的面向?qū)ο驛da95程序切片［J］.軟件學(xué)報(bào)，2001，12(增刊):208－213.Xu Baowen，Chen Zhenqiang，Zhou Xiaoyu.Slicing object－oriented Ada95 programs based on dependence analysis［J］.Journal of Software，2001，12(supp)，208－213.(in Chinese)

［7］ Horwitz S，Liblit B，Polishchuk M.Better debugging via output tracing and callstack－sensitive slicing［J］.IEEE Transaction on Software Engineering，2010，36(1):7－19.

［8］ Krinke J.Effects of context on program slicing［J］.Journal of System and Software， 2006， 79(9):1249－1260.

［9］ Horwitz S，Reps T，Binkley D.Inter－procedural slicing using dependence graphs［J］.ACM Transactions on Programming Languages and Systems，1990，12(1):26－60.

［10］ Gramma Tech.Codesurfer2.1［EB/OL］.(2007－05－30) ［2011－05－25］.http://www.grammatech.com/products/codesurfer/overview.html.

［11］ Gailly J，Adler M.Zlib1.2.3［EB/OL］.(2005－07－18)［2011－05－25］.http://gnuwin32.sourceforge.net/packages/zlib.htm.

［12］ Hogan T. BNBT easytracker beta7.7 ［EB/OL］.(2003－09－05) ［2011－05－25］.http://sourceforge.net/projects/bnbteasytracker/.

［13］ Dai W.Crypto++5.2.1［EB/OL］.(2004－07－21)［2011－05－25］.http://www.cryptopp.com/.