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

軟件的集成測試在面向?qū)ο筌浖到y(tǒng)中是一個非常關(guān)鍵的過程，與傳統(tǒng)軟件系統(tǒng)不同的是其對功能模塊的測試由于對象的封裝、繼承和多態(tài)等特性，變得十分復(fù)雜。在面向?qū)ο蟮某绦蛑?，類間的聯(lián)系通過消息傳遞，一條消息引起連鎖反應(yīng)形成一條方法調(diào)用鏈，稱為依賴關(guān)系［1］。由于面向?qū)ο蟮某绦蛟O(shè)計的特性，使得多個類構(gòu)成的類簇中的依賴關(guān)系形成網(wǎng)狀結(jié)構(gòu)圖，因此從哪里開始測試以及如何安排類間測試順序成為關(guān)鍵問題之一。測試樁數(shù)量是衡量測試代價的主要方法，因此，改進類間測試順序以減少測試樁的開發(fā)，對降低測試成本，縮短測試周期，提高測試效率是一個很有效的途徑。

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

在經(jīng)過對多種方法的比較分析后，本文在改進參考文獻(xiàn)［10］的算法基礎(chǔ)上結(jié)合了有向無環(huán)圖算法分配測試順序。該類方法使用有向圖來表示系統(tǒng)中類的依賴關(guān)系，并通過分析有向圖的結(jié)構(gòu)，在保證測試樁的數(shù)目盡可能少的前提下，利用邊刪除規(guī)則去除環(huán)路，在此基礎(chǔ)上運用有向無環(huán)圖的拓?fù)湫蛄姓业揭粋€合適的測試順序。

1 相關(guān)概念

1.1 對象的依賴關(guān)系

面向?qū)ο蟪绦蝾愰g的依賴關(guān)系主要包括兩類:一類是靜態(tài)依賴關(guān)系，另一類是動態(tài)依賴關(guān)系。

1.1.1 靜態(tài)依賴關(guān)系

靜態(tài)依賴關(guān)系指的是整個程序代碼靜態(tài)結(jié)構(gòu)中反映出來的類與類之間的關(guān)系。面向?qū)ο蟪绦蛑校愰g的靜態(tài)關(guān)系主要有繼承關(guān)系、聚合關(guān)系和關(guān)聯(lián)關(guān)系。

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

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

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

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

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

1.1.2 動態(tài)依賴關(guān)系

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

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

1.2 測試樁

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

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

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

在依賴關(guān)系中，繼承關(guān)系和聚合關(guān)系為強聯(lián)系關(guān)系，動態(tài)依賴關(guān)系和關(guān)聯(lián)關(guān)系均為弱聯(lián)系關(guān)系［2］。為了避免刪除強聯(lián)系關(guān)系而導(dǎo)致EORD中依賴關(guān)系的不完整，故而只需要在弱聯(lián)系關(guān)系中刪除某些邊去除環(huán)路。

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

2.1 EORD中改進的環(huán)路消除算法

對于存在環(huán)路的EORD，刪除哪些邊消除環(huán)路將直接影響到構(gòu)造測試樁的數(shù)量?？紤]動態(tài)依賴邊對打破環(huán)路的影響，同時為了滿足構(gòu)造的測試樁最少，我們應(yīng)該遵循刪除最少的邊打破盡量多的環(huán)路的原則，下面給出相關(guān)的刪除規(guī)則。

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

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

根據(jù)上文提出的邊刪除規(guī)則以及算法的改進，下面給出相應(yīng)的環(huán)路消除算法，算法流程圖如圖2所示。

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

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

表1 SCC{E，F(xiàn)，G，H}中的環(huán)路

表2 SCC{E，F(xiàn)，G，H}弱關(guān)聯(lián)關(guān)系中各關(guān)聯(lián)邊涉及的環(huán)路

表3 SCC{A，B，C}中的環(huán)路

表4 SCC{A，B，C}弱關(guān)聯(lián)關(guān)系中各關(guān)聯(lián)邊涉及的環(huán)路

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

圖3 消除環(huán)路后擴展的對象關(guān)系圖

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

2.2 測試順序分配

在程序的執(zhí)行過程中，消除EORD中的環(huán)路以后，程序中仍存在動態(tài)依賴關(guān)系，由于動態(tài)依賴關(guān)系在程序運行時期才會存在，在測試一個類之前，該類所依賴的所有類都已經(jīng)測試，而且在對一個類進行動態(tài)測試之前，所有的靜態(tài)測試都已經(jīng)測試完成。

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

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

表5 圖3中EORD的測試級

這里先不考慮動態(tài)依賴邊，所有的靜態(tài)依賴邊構(gòu)成了一個無環(huán)的有向圖［15］。對于有向無環(huán)圖要找到其拓?fù)湫蛄械牟襟E:(1)在有向圖中選一個沒有前驅(qū)的頂點并且輸出;(2)從圖中刪除該頂點的所有以它作為尾的邊。重復(fù)上述兩步，直到全部頂點均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點為止。然后再考慮動態(tài)依賴邊，利用表5中動態(tài)依賴邊的測試級，分配動態(tài)依賴的測試順序。由于依賴關(guān)系的定義，若A依賴于B，則先測試B再測試A。故所得到的拓?fù)湫蛄心嫘蚣礊闇y試順序。

由上面所述的算法，得到圖3的靜態(tài)依賴測試級的拓?fù)湫蛄袨?(H，F(xiàn)，G，A，C，E，D，B)考慮動態(tài)依賴邊后所得到的測試級測試順序如圖4所示。

圖4 測試級測試順序

3 實驗仿真及結(jié)果分析

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

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

本文就打破環(huán)路所需構(gòu)造測試樁的數(shù)目，分別與文獻(xiàn)［2］中Kung只考慮靜態(tài)依賴關(guān)系的測試方法和文獻(xiàn)［5－7］中引入SCC概念但沒有用有向無環(huán)圖概念的Briand方法進行比較，結(jié)果如圖5所示。

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

表6 SD系統(tǒng)的詳細(xì)信息

表7 打破靜態(tài)依賴關(guān)系構(gòu)成的環(huán)路過程

表8 增加動態(tài)依賴關(guān)系后打破環(huán)路過程

圖5 3種方法的比較

4 結(jié)束語

在類間依賴關(guān)系構(gòu)成環(huán)路的情況下，需要刪除某些依賴關(guān)系以消除環(huán)路，同時建立測試樁。文中的算法首先分析ORD中類間的依賴關(guān)系，設(shè)定了邊的刪除規(guī)則去除環(huán)路，在此基礎(chǔ)上運用有向無環(huán)圖拓?fù)湫蛄薪o出類的測試順序。最后運用測試工具TLOG驗證該方法較其他方法需要較少的測試樁，測試效率有明顯的提高。本文的算法與Kung和Briand的算法相比考慮了動態(tài)依賴，并且使用有向無環(huán)圖拓?fù)湫蛄写_定測試順序，性能較優(yōu)，只需要構(gòu)造較少的測試樁，有效降低了測試成本。但是本文中也存在著不足之處:沒有考慮抽象類的特點，實際上，抽象類會影響類間的依賴性，進而將影響類間測試順序，所以抽象類的研究將是以后工作的重點。

參考文獻(xiàn):

［1］王正山.基于ORG的OO軟件測試技術(shù)研究［D］.合肥:合肥工業(yè)大學(xué)，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，F(xiàn)eng 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］.計算機工程與設(shè)計，2008，29(4):781－783.

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

［11］李小將，李佑祿，陳啟安.基于類的動態(tài)依賴關(guān)系的集成測試順序分配策略［J］.裝備指揮技術(shù)學(xué)院學(xué)報，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］高劍，羅志增.支持向量機在肌電信號模式識別中的應(yīng)用［J］.傳感技術(shù)學(xué)報，2007，20(2):366－369.

［16］關(guān)樂，褚金奎，王曉東，等.系統(tǒng)級設(shè)計方法及其在力學(xué)特性集成測試中的應(yīng)用［J］.傳感技術(shù)學(xué)報，2006，19(5):1313－1318.

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

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

基于動態(tài)依賴的類間測試順序研究*

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

類間集成測試順序決定著測試成本的大小，為了得到合適的測試順序，提出了一種基于動態(tài)依賴的類間測試順序的方法。首先分析對象關(guān)系圖中類間依賴關(guān)系，然后運用邊刪除規(guī)則去除環(huán)路，最后運用有向無環(huán)圖的拓?fù)湫蛄薪o出類的測試順序。仿真結(jié)果表明，本文的方法較Briand的方法減少了42%的測試樁。此方法滿足最小化測試樁的需要，提高了測試效率，減少了測試成本。

對象關(guān)系圖;動態(tài)依賴;測試樁;測試順序;有向無環(huán)圖

TP311.5

A

1004－1699(2014)01－0064－06

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

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

C:7210A

10.3969/j.issn.1004－1699.2014.01.012

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