Class-Integration Testing Sequence Research Based on Dynamic Dependency*

CHEN Jianxun，XIAO Yiran

(College of Computer Science and Technology，Wuhan University of Science and Technology，Wuhan 430065，China)

Class-Integration Testing Sequence Research Based on Dynamic Dependency*

CHEN Jianxun*，XIAO Yiran

(College of Computer Science and Technology，Wuhan University of Science and Technology，Wuhan 430065，China)

The cost of the class－integration－test depends largely on the testing sequence.Therefore，an approach based on dynamic dependency relation for class－integration－test order is proposed in order to obtain a suitable test sequence. Firstly，the class dependencies among those object relational graphs are analysed.Secondly，the loop is removed by applying the edge deletion rules.Lastly，the test order is achieved based on the topological sequence of a directed acycline graph.The simulation results show that42%test stubswere reduced by applying the proposedmethod comparing to the Briand`smethod.It comes to a conclusion that thismethod meets the requirement of reducing the test stubs to theminimum.In addition，it improves test efficiency aswell as reduces the test cost.

object relational graph;dynamic dependency;test stub;test sequence;directed acycline graph

軟件的集成測試在面向對象軟件系統中是一個非常關鍵的過程，與傳統軟件系統不同的是其對功能模塊的測試由于對象的封裝、繼承和多態等特性，變得十分復雜。在面向對象的程序中，類間的聯系通過消息傳遞，一條消息引起連鎖反應形成一條方法調用鏈，稱為依賴關系［1］。由于面向對象的程序設計的特性，使得多個類構成的類簇中的依賴關系形成網狀結構圖，因此從哪里開始測試以及如何安排類間測試順序成為關鍵問題之一。測試樁數量是衡量測試代價的主要方法，因此，改進類間測試順序以減少測試樁的開發，對降低測試成本，縮短測試周期，提高測試效率是一個很有效的途徑。

對于不存在環路的對象關系圖ORD(Object Related Diagram)［2］，類間測試順序可以通過簡單的逆向拓撲序列來解決;對于存在環路的ORD，則需要刪除某些依賴關系，以打破其中的環路，然后給出類間測試序列。因此，確定類間測試順序的核心問題就是打破環路。學者Kung［2］的方法是刪除一條或多條關聯邊以斷開環路，沒有考慮類間的復雜繼承關系以及動態依賴關系。學者Le Traon［3］在Tarjan［4］算法基礎上引入了強連通圖，但沒有區分3種不同依賴類型，影響了測試樁開發的復雜度。學者Briand［5－7］在Tai［8］和Le Traon算法的基礎上使用權重計算的方法，來確定移除哪些依賴關系。該方法即避免了因為移除繼承、聚合關系引起的開發復雜測試樁的問題，也避免了Tai等人的方法在某些場景下將產生多余測試樁的缺陷［9］。

在經過對多種方法的比較分析后，本文在改進參考文獻［10］的算法基礎上結合了有向無環圖算法分配測試順序。該類方法使用有向圖來表示系統中類的依賴關系，并通過分析有向圖的結構，在保證測試樁的數目盡可能少的前提下，利用邊刪除規則去除環路，在此基礎上運用有向無環圖的拓撲序列找到一個合適的測試順序。

1 相關概念

1.1 對象的依賴關系

面向對象程序類間的依賴關系主要包括兩類:一類是靜態依賴關系，另一類是動態依賴關系。

1.1.1 靜態依賴關系

靜態依賴關系指的是整個程序代碼靜態結構中反映出來的類與類之間的關系。面向對象程序中，類間的靜態關系主要有繼承關系、聚合關系和關聯關系。

(1)如果類A是類B的子類，則類A、B為繼承關系，A依賴于B。

(2)如果類A的數據成員具有一個或多個類B的實例，則類A、B為聚合關系，稱A依賴于B。

(3)如果類A的成員方法使用了類B的實例，則類A、B為關聯關系，稱A依賴于B。

在集成測試時若類A依賴于類B，則先測試B再測試A。

類簇以及它們之間的依賴關系可以抽象為對象關系圖(ORD)。ORD中每個節點代表著程序中的一個類，每條邊代表類與類之間繼承、聚合和關聯關系中的一種，分別用I，Ag，As表示。

1.1.2 動態依賴關系

動態依賴關系是指類在程序運行時期形成的一種依賴關系。若類A是類B的子類，且重寫了類B的虛方法，類B是類C的服務類，且調用了類B中被類A重寫的虛方法，則在程序運行時，C和A動態綁定，類C動態依賴于類A［9］。本文是在ORD的基礎上進行類間分析的，因此我們將可能存在的動態依賴關系都標記在ORD中。圖1是擴展后的對象關系圖EORD(Extended Object Relation Graph)其中動態依賴用虛線有向邊表示。

圖1 擴展后的對象關系圖(EORD)

1.2 測試樁

定義:如果類A的一個組件使用一個或多個類B的服務組件，稱為A依賴B，在集成測試過程中，當A集成時，若B尚未被集成，我們不得不模擬B的服務組件，這個模擬組件通常被稱為一個測試樁［10］。

在集成測試過程中，當需要對類A進行測試時，類A所依賴的另一個類B并沒有經過測試，如果很難在短時間內構建類B，則必定會影響到對類A的集成測試。此時需要構建模擬的對象來代替類B。測試樁并不是真正的對象，但是能夠為待測對象提供感興趣的數據或狀態，這樣，待測對象便能夠順利使用依賴對象，或者模擬事件。故而集成測試中測試樁數目的多少決定了測試的成本。

2 改進的類間測試順序算法

在依賴關系中，繼承關系和聚合關系為強聯系關系，動態依賴關系和關聯關系均為弱聯系關系［2］。為了避免刪除強聯系關系而導致EORD中依賴關系的不完整，故而只需要在弱聯系關系中刪除某些邊去除環路。

為了減少測試代價，首先需要識別出EORD中由類以及它們之間的依賴關系形成的SCC，然后查找每一個子強連通分量中所有的環路，統計強連通分量中每條弱關聯關系所涉及的環路數目，刪除涉及環路數目最多的依賴邊，進而將一個有環圖去除環路成為一個有向無環圖。

2.1 EORD中改進的環路消除算法

對于存在環路的EORD，刪除哪些邊消除環路將直接影響到構造測試樁的數量。考慮動態依賴邊對打破環路的影響，同時為了滿足構造的測試樁最少，我們應該遵循刪除最少的邊打破盡量多的環路的原則，下面給出相關的刪除規則。

規則:B是A的父類，且是C的服務類。如果C在A和B之前進行測試，若B是非抽象類，則不需要為A構造測試樁，只需為B構造測試樁［11－13］。

在去除環路過程中，當Dy和As邊涉及環路數目相同時，首先要判斷該SCC中是否存在兩個類有同向邊，若同向邊為As和Dy，則刪除這兩條邊;若同向邊為Ag、I和Dy，則刪除Dy邊。

根據上文提出的邊刪除規則以及算法的改進，下面給出相應的環路消除算法，算法流程圖如圖2所示。

參考文獻［10］算法復雜度為O(n2)，而本文改進的算法復雜度為O(n)，較之前的算法較快速的找到需要刪除的邊。

下面把圖1中所示用例應用到該算法中，對算法的具體步驟說明如下:

表1 SCC{E，F，G，H}中的環路

表2 SCC{E，F，G，H}弱關聯關系中各關聯邊涉及的環路

表3 SCC{A，B，C}中的環路

表4 SCC{A，B，C}弱關聯關系中各關聯邊涉及的環路

根據本節的算法，計算SCC{E，F，G，H}中各條關聯邊和動態依賴邊涉及的環路數目，結果如表2所示。由算法得出刪除E→F即可打破所有的環路。對于SCC{A，B，C}，根據算法，需要刪除邊B→A和邊C→A打破環路。此時，EORD成為了無環圖，如圖3所示。

圖3 消除環路后擴展的對象關系圖

打破EORD中所有環路需要刪除E→F、B→A和C→A這三條邊，分別為這三條邊的源類A，F各自創建1個測試樁，共需要2個測試樁。因此圖1所示的實例需要構建2個測試樁。

2.2 測試順序分配

在程序的執行過程中，消除EORD中的環路以后，程序中仍存在動態依賴關系，由于動態依賴關系在程序運行時期才會存在，在測試一個類之前，該類所依賴的所有類都已經測試，而且在對一個類進行動態測試之前，所有的靜態測試都已經測試完成。

定義:測試級C=(C.goal，C.all，C.type)［14］，其中C.goal為被測試類;C.all為被測試類所依賴的類構成的并集;C.type為測試的類型，靜態測試用S表示，動態測試用Dy表示。對于EORD中的每一個類X，為每個類定義一個靜態測試級C=({X}，S (X)，S);對于滿足D(X)≠Φ的類X，定義一個動態測試級C=({X}，D(X)，Dy)。

以圖3所示EORD為例，首先為每個類各自定義一個靜態測試級，其中類C和類F滿足D(X)≠Φ，那么為C和F定義動態測試級。表5所示為圖6中無環EORD的所有測試級。

表5 圖3中EORD的測試級

這里先不考慮動態依賴邊，所有的靜態依賴邊構成了一個無環的有向圖［15］。對于有向無環圖要找到其拓撲序列的步驟:(1)在有向圖中選一個沒有前驅的頂點并且輸出;(2)從圖中刪除該頂點的所有以它作為尾的邊。重復上述兩步，直到全部頂點均已輸出，或者當前圖中不存在無前驅的頂點為止。然后再考慮動態依賴邊，利用表5中動態依賴邊的測試級，分配動態依賴的測試順序。由于依賴關系的定義，若A依賴于B，則先測試B再測試A。故所得到的拓撲序列逆序即為測試順序。

由上面所述的算法，得到圖3的靜態依賴測試級的拓撲序列為:(H，F，G，A，C，E，D，B)考慮動態依賴邊后所得到的測試級測試順序如圖4所示。

圖4 測試級測試順序

3 實驗仿真及結果分析

根據上述類測試順序的算法設計并實現了一個工具TLOG［16］，該工具的輸入信息是一個描述面向對象系統中類的關系的三元組列表。該列表可以手工輸入也可以根據面向對象系統的統一建模語言設計文檔中的UML類圖獲取。TLOG主要有幾個功能:(1)環路生成模塊;(2)環路消除模塊;(3)測試級排序模塊。以SD空運物流進出口業務處理系統為實例驗證本文方法的有效性。SD系統中包含10個模塊，詳細信息如表6。

SD系統包含1126個環路(不考慮動態依賴)，由于篇幅有限，只簡單給出采用本方法打破靜態依賴關系構成環路的過程，如表7所示。打破環路共刪除95條邊，實際需要構建81個測試樁。考慮動態依賴關系后，增加了39個動態依賴關系，環路數增加至2283個，表8給出了SCC中環路的打破過程。打破EORD中環路共刪除124條邊，實際需要構建95個測試樁。

本文就打破環路所需構造測試樁的數目，分別與文獻［2］中Kung只考慮靜態依賴關系的測試方法和文獻［5－7］中引入SCC概念但沒有用有向無環圖概念的Briand方法進行比較，結果如圖5所示。

實驗結果證明:考慮類間的動態依賴關系后，實例中環路數目明顯增多，Kung方法由于沒有考慮動態依賴，沒有去除EORD中所有的環路，所需測試樁最少，但是測試不完整。本文方法雖然與Briand方法打破的環路數相同，但是本文方法所需測試樁少，且發現的接口錯誤數多。由此，本文改進的算法滿足最小化測試樁的需求，并且打破環路多，發現錯誤多，提高了測試效率，減少了測試成本。

表6 SD系統的詳細信息

表7 打破靜態依賴關系構成的環路過程

表8 增加動態依賴關系后打破環路過程

圖5 3種方法的比較

4 結束語

在類間依賴關系構成環路的情況下，需要刪除某些依賴關系以消除環路，同時建立測試樁。文中的算法首先分析ORD中類間的依賴關系，設定了邊的刪除規則去除環路，在此基礎上運用有向無環圖拓撲序列給出類的測試順序。最后運用測試工具TLOG驗證該方法較其他方法需要較少的測試樁，測試效率有明顯的提高。本文的算法與Kung和Briand的算法相比考慮了動態依賴，并且使用有向無環圖拓撲序列確定測試順序，性能較優，只需要構造較少的測試樁，有效降低了測試成本。但是本文中也存在著不足之處:沒有考慮抽象類的特點，實際上，抽象類會影響類間的依賴性，進而將影響類間測試順序，所以抽象類的研究將是以后工作的重點。

參考文獻:

［1］王正山.基于ORG的OO軟件測試技術研究［D］.合肥:合肥工業大學，2005.

［2］Kung D C，Gao J，Hsia P，etal.Class Firewall，TestOrder，and Regression Testing of Object－Oriented Programs［J］.JOOP，1995，8 (2):51－65.

［3］Le TY，Jeron T，Jezequel JM，etal.EfficientObject－Oriented Integration and Regression Testing［J］.IEEE Transactions on Reliability，2000，49(1):12－25.

［4］Tarjan R.Depth－First Search and Linear Graph Algorithms［J］.SIAMJournal on Computing，1972，1(2):146－160.

［5］Briand L C，Labiche Y，Wang Y.Revisiting Strategies for Ordering Class Integration Testing in the Presence of Dependency Cycles［C］//Software Reliability Engineering，2001.ISSRE 2001.Proceedings.12th International Symposium on.IEEE，2001:287－296.

［6］Briand L C，Feng J，Labiche Y.Using Genetic Algorithms and Coupling Measures to Devise Optimal Integration TestOrders［C］//Proceedings of the 14th International Conference on Software Engineering and Knowledge Engineering.ACM，2002:43－50.

［7］Briand L C，Labiche Y，Wang Y.An Investigation of Graph－Based Class Integration Test Order Strategies［J］.IEEE Transactions on Software Engineering，2003，29(7):594－607.

［8］Tai K C，Daniels F J.Interclass Test Order for Object－Oriented Software［J］.Journal of Object－Oriented Programming，1999，12(4):18－25.

［9］李都.測試順序選擇策略研究［J］.計算機工程與設計，2008，29(4):781－783.

［10］張艷梅，姜淑娟，張紅昌.一種基于動態依賴關系的類集成測試方法［J］.計算機學報，2011，34(6):1075－1089.

［11］李小將，李佑祿，陳啟安.基于類的動態依賴關系的集成測試順序分配策略［J］.裝備指揮技術學院學報，2005，16(1):93－97.

［12］Wang Z，Li B，Wang L，et al.Using Coupling Measure Technique and Random Iterative Algorithm for Inter－Class Integration TestOrder Problem［C］//Computer Software and Applications Conference Workshops(COMPSACW)，2010 IEEE 34th Annual.IEEE，2010: 329－334.

［13］Jiang S，Zhang Y，Yi D.Test Data Generation Approach for Basis Path Coverage［J］.ACMSIGSOFT Software Engineering Notes，2012，37(3):1－7.

［14］Labiche Y，Thevenod－Fosse P，Waeselynck H，et al.Testing Levels for Object－Oriented Software［C］//Proceedings of the 22nd International Conference on Software Engineering.ACM，2000:136－145.

［15］高劍，羅志增.支持向量機在肌電信號模式識別中的應用［J］.傳感技術學報，2007，20(2):366－369.

［16］關樂，褚金奎，王曉東，等.系統級設計方法及其在力學特性集成測試中的應用［J］.傳感技術學報，2006，19(5):1313－1318.

陳建勛(1957－)，男，博士，教授，CCF高級會員，研究領域為軟件工程、計算機圖形學和CAD技術、基于計算機網絡的應用技術，jxwh@wust.edu.cn;

肖亦然(1988－)，女，碩士研究生，研究方向為現代軟件工程技術。

基于動態依賴的類間測試順序研究*

陳建勛*，肖亦然
(武漢科技大學計算機科學與技術學院，武漢430065)

類間集成測試順序決定著測試成本的大小，為了得到合適的測試順序，提出了一種基于動態依賴的類間測試順序的方法。首先分析對象關系圖中類間依賴關系，然后運用邊刪除規則去除環路，最后運用有向無環圖的拓撲序列給出類的測試順序。仿真結果表明，本文的方法較Briand的方法減少了42%的測試樁。此方法滿足最小化測試樁的需要，提高了測試效率，減少了測試成本。

對象關系圖;動態依賴;測試樁;測試順序;有向無環圖

TP311.5

A

1004－1699(2014)01－0064－06

［10］中對算法進行了簡單的描述，但是在一個強連通分量(SCC)中，當Dy和As邊涉及環路數目相同時，沒有明確的算法說明刪除哪些邊，并且在一次判斷結束刪除相應邊以后，SCC中有可能仍然存在環路，文獻中沒有相應的判斷。根據這些不足點，再結合有向無環圖計算的思想，提出本文的改進算法。

2013－10－21修改日期:2013－12－26

C:7210A

10.3969/j.issn.1004－1699.2014.01.012

項目來源:國家自然科學基金項目(61100055，61033003，60974112，91130034);湖北省自然科學基金項目(2011CDB233)