基于動態調用圖的Java程序修改影響分析技術

劉 震，繆 力

(湖南交通職業技術學院現代教育技術中心，中國 長沙 410132)

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

面向對象軟件技術利用可重用性提高了軟件開發的效率.隨著面向對象軟件開發技術的成熟，軟件的規模越來越大，對其進行小部分修改后要回歸測試．對于面向對象技術所開發的軟件和其他方法所開發的軟件，基于規格的測試是相同的.但對于基于程序的測試有很大區別，因為面向對象技術的特征對測試其所開發的程序有很大影響，相應的回歸測試也一樣受影響.在選擇需重新執行的測試用例時必須考慮面向對象技術的特征．

隨著面向對象技術的成熟，現在的大部分軟件產品使用面向對象方法編寫，所以面向對象的回歸測試技術也逐漸成了回歸測試研究中的重點．面向對象軟件中主要是對象之間的依賴關系以及各種類之間的繼承和組合關系，對象之間通過消息相互操作及影響．Leung和White[3-4]提出了回歸測試的防火墻概念，Kung 等[5-7]針對面向對象的程序擴展為類防火墻，以類為測試的基本單元，先標識出改變的類與受改變影響的類，即構造一個類防火墻，然后對類防火墻中的類根據對象關系圖以一定的順序進行回歸測試．

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

1 基于動態信息的修改影響分析框架

基于動態信息的修改影響分析原理如圖1所示．

圖1 基于動態信息的修改影響分析原理框架圖

首先要獲得動態信息．動態信息一般需要在程序中插樁，使得程序可以輸出運行中的信息，然后才能搜集．與C程序需要對源代碼插樁不同，Java程序被編譯為字節碼在虛擬機上運行，因此可以直接對編譯后的Java字節碼程序插樁．插樁工具可基于Javaassist[8]或者BECL[9]等Java字節碼操控工具提供的接口進行開發．對每條語句插樁將導致巨大的執行軌跡信息，并可能嚴重影響系統性能，導致一些具有實時要求的系統不能運行，因此，本文采用對每個方法插樁，記錄方法調用信息．

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

表1 BECL與Javaassist的接口使用對比表

運行插樁后的Java程序，程序根據插樁的設置輸出執行軌跡信息，搜集軌跡信息并構造動態調用圖；基于動態調用圖，通過修改影響分析可以得出需要重新測試的模塊，從而實現了高效的回歸測試．

2 動態調用圖(Dynamic Call Graph)

函數調用圖是編譯期對程序中函數調用關系的一種靜態描述.在函數調用圖中，節點表示函數，邊表示函數之間的調用關系，因為對于虛函數調用點而言，必須根據運行時接受對象的實際類型才能確定具體調用的目標函數，所以函數調用圖只是對程序運行時函數調用關系的一種近似．如果在編譯期對虛函數調用點采用不同的靜態處理策略，那么所得到的函數調用圖在節點和邊的數目上也不盡相同.然而所有處理策略的目標是一致的，那就是使通過靜態分析構建的函數調用圖能夠更接近于程序運行時實際的函數調用情況．下面是模擬器程序函數調用圖：

圖2 一個函數調用圖的示例

對于虛函數調用點而言，必須根據運行時接受對象的實際類型來確定具體調用的目標函數，因此靜態調用圖是不精確的．

例1一個導致靜態調用圖不精確的例子

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在運行時的可能類型就包括A，B和C．

給出較為精確的面向對象程序的調用關系對于修改影響分析有重要意義.本文提出采用動態調用圖(Dynamic Call Graph，以下簡稱DCG)作為修改影響分析的對象.與靜態調用圖相比，DCG直接從程序執行的動態信息中構造調用圖，無需分析程序源代碼，技術上實現比較簡便.由于采用的是執行信息，無需進行虛函數的動態綁定分析，精度也比靜態調用圖有提高．

動態調用圖構造算法

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

輸出：動態調用圖 DCG

Fori=1…ndo{

For eachmj∈tcido{

Ifmjmarked “in”//調用方法進入

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

Ifminnot in DCG

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

If (top(currentmethod),min)

Addedge (DCG, top(currentmethod)，mj); //如果軌跡中節點的調用關系不在DCG中，增加邊

Else // 調用方法退出

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

}

}

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

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

3 修改影響分析算法與實驗

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

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

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

BSlice(E)m,k的計算方法為標準的圖可達算法.基于該算法，計算修改導致的影響集合．

輸入：動態調用圖 DCG，被修改的方法集合M, 調用層k

輸出：修改影響集合affectedM

For eachmi∈Mdo{

affectedM=affectedM∪BSlice(E)m,k

}

我們以2個Java程序進行實驗，并通過修改一些方法引入錯誤，其中設定k為4，需要重新測試的方法數量由程序開發人員和測試專家確定．

表3 實驗結果對比

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

4 結論

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

參考文獻：

[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.