基于動(dòng)態(tài)調(diào)用圖的Java程序修改影響分析技術(shù)

劉 震，繆 力

(湖南交通職業(yè)技術(shù)學(xué)院現(xiàn)代教育技術(shù)中心，中國 長沙 410132)

軟件測試是軟件生命周期中重要的一環(huán)，用在測試上的開銷要占30%～50%[1]．軟件回歸測試指對(duì)修改之后的軟件進(jìn)行的測試，其目的主要是1)修改后新的功能測試；2)修改是否引入新的錯(cuò)誤.由于程序各元素之間的關(guān)系非常復(fù)雜，如果沒有分析方法，程序修改之后一般需要對(duì)整個(gè)程序重新測試，即RETEST-ALL方法．RETEST-ALL方法效率非常低．特別是當(dāng)軟件進(jìn)入開發(fā)后期或者維護(hù)階段，軟件經(jīng)常需要進(jìn)行頻繁卻少量的修改.如果每次修改都需要重新運(yùn)行全部的測試用例，將導(dǎo)致軟件開發(fā)和維護(hù)的效率低下．為了提高測試效率，人們希望對(duì)修改的軟件進(jìn)行分析，找出軟件中由于修改可能影響的部分，這就是修改影響分析.修改影響分析能使測試有目的的進(jìn)行，提高測試效率，降低測試費(fèi)用．如Rothermel通過控制流分析，提出一種安全的(safe)回歸測試技術(shù)[2]，使得回歸測試可以只運(yùn)行與改動(dòng)相關(guān)的小部分測試用例，而測試效果運(yùn)行全部測試用例完全相同．

面向?qū)ο筌浖夹g(shù)利用可重用性提高了軟件開發(fā)的效率.隨著面向?qū)ο筌浖_發(fā)技術(shù)的成熟，軟件的規(guī)模越來越大，對(duì)其進(jìn)行小部分修改后要回歸測試．對(duì)于面向?qū)ο蠹夹g(shù)所開發(fā)的軟件和其他方法所開發(fā)的軟件，基于規(guī)格的測試是相同的.但對(duì)于基于程序的測試有很大區(qū)別，因?yàn)槊嫦驅(qū)ο蠹夹g(shù)的特征對(duì)測試其所開發(fā)的程序有很大影響，相應(yīng)的回歸測試也一樣受影響.在選擇需重新執(zhí)行的測試用例時(shí)必須考慮面向?qū)ο蠹夹g(shù)的特征．

隨著面向?qū)ο蠹夹g(shù)的成熟，現(xiàn)在的大部分軟件產(chǎn)品使用面向?qū)ο蠓椒ň帉懀悦嫦驅(qū)ο蟮幕貧w測試技術(shù)也逐漸成了回歸測試研究中的重點(diǎn)．面向?qū)ο筌浖兄饕菍?duì)象之間的依賴關(guān)系以及各種類之間的繼承和組合關(guān)系，對(duì)象之間通過消息相互操作及影響．Leung和White[3-4]提出了回歸測試的防火墻概念，Kung 等[5-7]針對(duì)面向?qū)ο蟮某绦驍U(kuò)展為類防火墻，以類為測試的基本單元，先標(biāo)識(shí)出改變的類與受改變影響的類，即構(gòu)造一個(gè)類防火墻，然后對(duì)類防火墻中的類根據(jù)對(duì)象關(guān)系圖以一定的順序進(jìn)行回歸測試．

現(xiàn)有的影響分析算法大都基于程序的靜態(tài)分析技術(shù)，通過分析程序源代碼構(gòu)建程序的類、方法等不同粒度的模型，然后基于該模型計(jì)算修改影響的范圍．靜態(tài)分析比較復(fù)雜，且是一種保守的分析技術(shù)，即如果分析得出模塊A與修改相關(guān)，則這種相關(guān)只是可能相關(guān)；而如果分析得出模塊A與修改無關(guān)，則肯定無關(guān).因此，靜態(tài)分析技術(shù)的精度不高．針對(duì)靜態(tài)分析存在的問題，本文提出采用動(dòng)態(tài)分析技術(shù)構(gòu)造程序的類成員防火墻，從而降低計(jì)算復(fù)雜度，并提高分析精度，便于修改影響分析技術(shù)的實(shí)際運(yùn)用．

1 基于動(dòng)態(tài)信息的修改影響分析框架

基于動(dòng)態(tài)信息的修改影響分析原理如圖1所示．

圖1 基于動(dòng)態(tài)信息的修改影響分析原理框架圖

首先要獲得動(dòng)態(tài)信息．動(dòng)態(tài)信息一般需要在程序中插樁，使得程序可以輸出運(yùn)行中的信息，然后才能搜集．與C程序需要對(duì)源代碼插樁不同，Java程序被編譯為字節(jié)碼在虛擬機(jī)上運(yùn)行，因此可以直接對(duì)編譯后的Java字節(jié)碼程序插樁．插樁工具可基于Javaassist[8]或者BECL[9]等Java字節(jié)碼操控工具提供的接口進(jìn)行開發(fā)．對(duì)每條語句插樁將導(dǎo)致巨大的執(zhí)行軌跡信息，并可能嚴(yán)重影響系統(tǒng)性能，導(dǎo)致一些具有實(shí)時(shí)要求的系統(tǒng)不能運(yùn)行，因此，本文采用對(duì)每個(gè)方法插樁，記錄方法調(diào)用信息．

表1為BECL與Javaassist的接口使用對(duì)比，同樣是要插入“System.out.println()”語句以輸出執(zhí)行信息， BECL需要更多的編譯知識(shí)，需要將語句分解為特定的格式插入，而Javaassist更加方便，可以直接插入該語句．

表1 BECL與Javaassist的接口使用對(duì)比表

運(yùn)行插樁后的Java程序，程序根據(jù)插樁的設(shè)置輸出執(zhí)行軌跡信息，搜集軌跡信息并構(gòu)造動(dòng)態(tài)調(diào)用圖；基于動(dòng)態(tài)調(diào)用圖，通過修改影響分析可以得出需要重新測試的模塊，從而實(shí)現(xiàn)了高效的回歸測試．

2 動(dòng)態(tài)調(diào)用圖(Dynamic Call Graph)

函數(shù)調(diào)用圖是編譯期對(duì)程序中函數(shù)調(diào)用關(guān)系的一種靜態(tài)描述.在函數(shù)調(diào)用圖中，節(jié)點(diǎn)表示函數(shù)，邊表示函數(shù)之間的調(diào)用關(guān)系，因?yàn)閷?duì)于虛函數(shù)調(diào)用點(diǎn)而言，必須根據(jù)運(yùn)行時(shí)接受對(duì)象的實(shí)際類型才能確定具體調(diào)用的目標(biāo)函數(shù)，所以函數(shù)調(diào)用圖只是對(duì)程序運(yùn)行時(shí)函數(shù)調(diào)用關(guān)系的一種近似．如果在編譯期對(duì)虛函數(shù)調(diào)用點(diǎn)采用不同的靜態(tài)處理策略，那么所得到的函數(shù)調(diào)用圖在節(jié)點(diǎn)和邊的數(shù)目上也不盡相同.然而所有處理策略的目標(biāo)是一致的，那就是使通過靜態(tài)分析構(gòu)建的函數(shù)調(diào)用圖能夠更接近于程序運(yùn)行時(shí)實(shí)際的函數(shù)調(diào)用情況．下面是模擬器程序函數(shù)調(diào)用圖：

圖2 一個(gè)函數(shù)調(diào)用圖的示例

對(duì)于虛函數(shù)調(diào)用點(diǎn)而言，必須根據(jù)運(yùn)行時(shí)接受對(duì)象的實(shí)際類型來確定具體調(diào)用的目標(biāo)函數(shù)，因此靜態(tài)調(diào)用圖是不精確的．

例1一個(gè)導(dǎo)致靜態(tài)調(diào)用圖不精確的例子

class A extends Object{ A e; void m(){ A a=new A(); e=a; System.out.println(“is A”); }}class B extends A{ void m(){ System.out.println(“is B”); }} class C extends A { void m(){ System.out.println(“is C”); } Public static void main (String args[]){ A d,e; A f=new A(); B b=new B(); C c=new C(); d=b; e=d; e.m(); }}

由此可見，變量e在運(yùn)行時(shí)的可能類型就包括A，B和C．

給出較為精確的面向?qū)ο蟪绦虻恼{(diào)用關(guān)系對(duì)于修改影響分析有重要意義.本文提出采用動(dòng)態(tài)調(diào)用圖(Dynamic Call Graph，以下簡稱DCG)作為修改影響分析的對(duì)象.與靜態(tài)調(diào)用圖相比，DCG直接從程序執(zhí)行的動(dòng)態(tài)信息中構(gòu)造調(diào)用圖，無需分析程序源代碼，技術(shù)上實(shí)現(xiàn)比較簡便.由于采用的是執(zhí)行信息，無需進(jìn)行虛函數(shù)的動(dòng)態(tài)綁定分析，精度也比靜態(tài)調(diào)用圖有提高．

動(dòng)態(tài)調(diào)用圖構(gòu)造算法

輸入：程序調(diào)用信息的執(zhí)行軌跡集合TC={tc1,tc2,…,tcn},其中tci={mi1in,mi2in,…，mi2out…mi1out…},mijin表示進(jìn)入mij方法，mijout表示退出mij方法；

輸出：動(dòng)態(tài)調(diào)用圖 DCG

Fori=1…ndo{

For eachmj∈tcido{

Ifmjmarked “in”//調(diào)用方法進(jìn)入

Push (mj,currentmethod) ;將當(dāng)前所在的方法壓入堆棧

Ifminnot in DCG

Addnode(DCG,mj)；//如果軌跡中節(jié)點(diǎn)不在DCG中，增加該節(jié)點(diǎn)

If (top(currentmethod),min)

Addedge (DCG, top(currentmethod)，mj); //如果軌跡中節(jié)點(diǎn)的調(diào)用關(guān)系不在DCG中，增加邊

Else // 調(diào)用方法退出

Pop (mj,currentmethod)//將當(dāng)前所在的方法彈出堆棧

}

}

算法說明：算法的輸入是執(zhí)行軌跡集合TC={tc1,tc2,…,tcn}，其中每條軌跡tci記錄了每個(gè)方法m進(jìn)入和退出的信息，分別標(biāo)志為in 和out．

構(gòu)造DCG需要節(jié)點(diǎn)和邊的信息.節(jié)點(diǎn)通過將軌跡中記錄的調(diào)用信息加入DCG中得到，即Addnode(DCG,mj)．注意到方法調(diào)用是以堆棧方式進(jìn)行，即先進(jìn)后出，因此，設(shè)置currentmethod為調(diào)用堆棧，每次遇到標(biāo)志為in的節(jié)點(diǎn)，表示方法被調(diào)用，即將該方法壓入堆棧，此時(shí)，接下來的標(biāo)志為in的節(jié)點(diǎn)都與該方法存在調(diào)用關(guān)系，通過Addedge (DCG, top(currentmethod)，mj)將調(diào)用關(guān)系加入DCG中，直到遇到標(biāo)志為out的節(jié)點(diǎn)，表示該方法調(diào)用退出，此時(shí)彈出堆棧，退回上一層調(diào)用方法．算法從所有的執(zhí)行軌跡中提取方法調(diào)用的信息，從而構(gòu)造出DCG．

3 修改影響分析算法與實(shí)驗(yàn)

得到了DCG之后，就可以用DCG進(jìn)行修改影響分析，通過后向切片來計(jì)算修改影響集合．

定義(k-類方法后向切片)令E是一個(gè)程序，給定切片準(zhǔn)則m∈M.則BSlice(E)m,k是E關(guān)于m的k-類方法切片，若

所謂后向切片，是指BSlice (E)m中的元素與m是調(diào)用關(guān)系而不是被調(diào)用關(guān)系，修改影響分析的假設(shè)是，如果m′調(diào)用m，那么m的修改將影響到m′，而m′的修改并不影響m．k表示調(diào)用層次對(duì)修改的影響關(guān)系，越是靠近m的調(diào)用越可能被影響，設(shè)定k層之后的影響忽略不計(jì)．

BSlice(E)m,k的計(jì)算方法為標(biāo)準(zhǔn)的圖可達(dá)算法.基于該算法，計(jì)算修改導(dǎo)致的影響集合．

輸入：動(dòng)態(tài)調(diào)用圖 DCG，被修改的方法集合M, 調(diào)用層k

輸出：修改影響集合affectedM

For eachmi∈Mdo{

affectedM=affectedM∪BSlice(E)m,k

}

我們以2個(gè)Java程序進(jìn)行實(shí)驗(yàn)，并通過修改一些方法引入錯(cuò)誤，其中設(shè)定k為4，需要重新測試的方法數(shù)量由程序開發(fā)人員和測試專家確定．

表3 實(shí)驗(yàn)結(jié)果對(duì)比

實(shí)驗(yàn)結(jié)果表明本文的方法可以極大地提高修改影響分析的效率.遺漏的需要重測的方法數(shù)量少，具有較高的實(shí)用價(jià)值．遺漏主要是因?yàn)閗的設(shè)置(實(shí)驗(yàn)設(shè)置k=4).當(dāng)k設(shè)置為6時(shí)，將包括所有需要重新測試的方法，但是修改影響的集合將急劇增長到124和202，影響了測試效率．

4 結(jié)論

軟件回歸測試指對(duì)修改之后的軟件進(jìn)行的測試.由于程序各元素之間的關(guān)系非常復(fù)雜，如果沒有分析方法，程序修改之后一般需要對(duì)整個(gè)程序重新測試，導(dǎo)致軟件開發(fā)和維護(hù)的效率低下．修改影響分析能使測試有目的的進(jìn)行，提高測試效率，降低測試費(fèi)用．現(xiàn)有的影響分析算法大都基于程序的靜態(tài)分析技術(shù)，分析方法比較復(fù)雜且精度不高．針對(duì)靜態(tài)分析存在的問題，本文提出采用動(dòng)態(tài)分析技術(shù)構(gòu)造Java程序的動(dòng)態(tài)調(diào)用圖，基于動(dòng)態(tài)調(diào)用圖，采用k-類方法后向切片計(jì)算修改影響集合．實(shí)驗(yàn)表明該方法簡便易行，分析精度高，便于修改影響分析技術(shù)在大型Java程序測試中的實(shí)際運(yùn)用．

參考文獻(xiàn)：

[1] BEIZER B. Software testing techniques[M]. New York: Van Nostrand Reinhold, 1990.

[2] ROTHERMEL G, HARROLD M J. A safe, efficient regression test selection technique[J]. ACM Transactionson Software Engineering and Methodology, 1997,6(2): 173-210.

[3] LEUNG H K N, WHITE L. A study of integration testing and software regression at the integration level: proceeding of software maintenance, San Diego, CA, USA November 26-29, 1990[C]. San Diego:[s.n.],1990.

[4] LEUNG H K N, WHITE L. A firewall concept for both control-flow and data-flow in regression integration testing: proceeding of software maintenance, Orlando, FL USA, November 9-12,1992[C]. Orlando:[s.n.],1992.

[5] KUNG D, GAO J, HSIA P,etal. Class firewall, test order, and regression testing of object-oriented programs[J]. J Object-Oriented Program, 1995, 8(2): 51-65.

[6] JANG Y K, CHAE H S, KWON Y R,etal. Change impact analysis for a class hierarchy: proceeding of Asia pacific software engineering, Taibei, Taiwan, December 02-04,1998[C]. Taibei:[s.n.],1998.

[7] BARBARA G R, FRANK T. Change impact analysis for object-oriented programs: PASTE’01 proceeding of the 2001 ACM SIGPLAN-SIGSOFT workshop on program analysis for software tools and engineering, Snowbird, Utah, USA, June 18-19, 2001[C]. New York: ACM, 2001.

[8] CHIBA S. Load-time structural reflection in java[J]. Lecture Notes Comput Sci, 2000, 1850:313-336.

[9] DAHM M. Byte code engineering, java-informations-tage ,Düsseldorf, Germany, September 1999[C].Düsseldorf:[s.n.],1999.