基于依賴結構的功能測試集排序方法

曹麗娜，高建華

（上海師范大學 計算機科學與工程系，上海200234）

0 引 言

軟件測試在軟件開發和維護的各個階段至關重要。為了提高軟件質量的可靠性，利用測試用例排序技術在有限的資源內及時發現、糾正程序中的錯誤和缺陷的特點，以達到提高軟件測試的實用效率，節約成本的目的。

為了充分提高軟件測試的有效性，節約成本。王丹等［1］提出了利用控制依賴控制路徑覆蓋的Fuzzing模型，分析提取的脆弱性語句；陳樹蜂等［2］通過分析UML 類圖中的各種靜態關系，提出一種基于UML 類圖的依賴性分析模型，來解決類之間復雜的依賴性問題；高雪娟等［3］利用UML順序圖為主要模型，結合有向圖和順序圖，采用覆蓋準則和深度優先搜索算法遍歷；陳建勛等［4］分析對象關系圖中類間依賴關系，利用邊刪除規則去除環路，最后運用有向無環圖的拓撲序列排序；S.Haidry等［5］根據測試用例之間依賴結構，繪制出有向無環圖，根據算法，得出最優的測試集。然而，這些技術卻沒有考慮下述問題：測試集中的測試用例之間存在功能依賴以及借助什么模型來描述這種依賴關系，并且當測試用例權值相等時怎么去排序。

針對此問題，借鑒上述思想，本文通過改進DSP技術的不足之處，總結出一種表示依賴結構的有向無環圖，作為對測試集生成的約束，將測試用例的權值和代碼覆蓋率相結合根據改進的算法對測試集排序，從而得出最優的測試集，減少測試集的生成，并同時保證代碼覆蓋率。

1 背景及相關知識

1.1 功能依賴

功能依賴是指在測試場景中，一些交互或需求必須要在其它一些交互或需求完成后才能執行。例如：交互或需求要在交互或需求I2之前執行，則稱I2依賴于I1。測試用例之間固有地繼承了這些關系，則相對應的測試用例t1，t2，即t2依賴于t1。

依賴結構可以用有向無環圖 （directed acyclic graph）表示，即G＝ （V，E）其中：節點的有限集合V＝ ｛t1，t2，t3，t4....tn｝，邊的集合E＝ ｛e1，e2，e3....em｝，E則表示是測試用例之間的功能依賴。依賴結構可以分成兩類：開放的依賴結構，封閉的依賴結構。開放的依賴結構是指對于兩個依賴的測試用例t1和t2，即在執行時t1在某些情況下要先于t2執行。封閉的依賴結構是指對于兩個依賴的測試用例t1和t2，t1必須要在t2之前執行，如圖1所示。

圖1 一個有向無環圖的例子

對于圖1中的測試用例，若是開放依賴結構，則測試順序是：I1－I2－D3－D4…。即I1已執行，那么D3和D4就處于開放狀態，若再執行D3，I1不需再次執行，其好處在于減少不必要的冗余。若是封閉的依賴結構，則測試順序是：I1－I2－I1－D3…，如I1已執行，接著執行I2，若接下來執行D3，那么其依賴結構I1就需再次執行。本文將重點介紹開放的依賴結構。

1.2 DAG 在測試集中的應用

DAG 是用來描述測試集內部測試用例之間功能依賴，若要想從測試集內部提取這些依賴性，就需要對一個系統的需求和設計有一定的了解，這樣才能手動的繪制出DAG。通過分析DAG 圖，我們可以找到各個測試用例之間的功能依賴，及復雜交互程度，進而根據算法求出權值，并依次確定各個測試用例的執行順序［6］。

2 依賴結構的圖覆蓋范圍值的測量標準

DSP是根據圖覆蓋范圍值進行優化的，它是對一個測試用例相關性的復雜程度的一個度量，又因為開放的依賴結構和封閉的依賴結構中的測試用例的執行順序的標準不同，所以對于它們必須設置不同的衡量標準［7］。

2.1 開放的依賴結構的標準

（1）一個測試用例的所有依賴關聯的測試用例。其提高了密切相關的測試用例被更早執行的可能性。例如：圖1中的I1的依賴關聯測試用例是：D3，D6，D7，D4，D8。D3的依賴關聯測試用例是：D6和D7。

（2）一個測試用例的直接或間接的最長路徑。其提高了線性相關的測試用例被更早執行的可能性。例如，圖1中的I1有三條路徑，其長度是一樣的，都是其最長路徑。

2.2 封閉的依賴結構的標準

（1）在一條路徑中沒有被執行的測試用例的數量。

（2）在一條路徑中沒有被執行的測試用例的數量比上已經被執行的測試用例的數量。

（3）未被執行的測試用例除以這條路徑的長度。

2.3 DSP依賴結構的弊端

S.Haidry驗證了DSP 技術具有一定的優越性，但當DAG 測試用例的權值相等時可以有任意的排序，例如圖2中的DAG，若按照S.Haidry 提出的方法進行排序有：t1－t2－t4－t6－t3－t5－t7或 者t1－t3－t5－t7－t2－t4－t6，計 算 兩種路徑的APFD 結果應該是相同的。若我們在考慮權值相同的排序時結合測試用例的代碼覆蓋率去排序，可以得到更優的排序結果。例如圖2 括號中代表每個測試用例的代碼覆蓋率，可以算的以上兩種排序的APFD 值分別為：APFD （t1－t2－t4－t6－t3－t5－t7）＝62%。APFD （t1－t3－t5－t7－t2－t4－t6）＝56%。

圖2 含有代碼覆蓋率的有向無環圖

3 DSP技術

3.1 開放依賴結構的優先級

根據開放依賴結構的圖形覆蓋范圍值的衡量標準，文獻中把優化測試用例的技術分成兩種，分別是DSP＿volume和DSP＿height。

3.1.1 DSP＿volume

DSP＿volume測量標準給那些具有更多的依賴關聯的測試用例更高的權值。這是因為在依賴結構中緊密相連的測試用例，在被測試的系統本身它們也是密切相關的，并且交互也更頻繁。這樣便能更早的發現更多的錯誤，最終提高錯誤檢錯率。為了計算一個測試用例的DSP＿volume，需先計算出這個測試用例所有直接和間接的依賴關聯測試用例。在本文中我們利用直接的傳遞閉包算法來實現。

算法1：直接的傳遞閉包算法

（1）根據系統的需求和設計得到DAG 圖，如一個DAG 的例子如圖3所示。

圖3 一個有向無環圖的例子

（2）根據圖3得到其鄰接矩陣［8］如圖4所示。

圖4 一個DAG 的鄰接矩陣

（3）根據直接的傳遞閉包算法，得到布爾鄰接矩陣，當D ［i，j］＝1 時，進行D［i，k］＝D［i，k］∨D［j，k］運算，即把第i行和第j列進行 “或”運算之后再賦給第i行，結果如圖5所示。

圖5 一個布爾鄰接矩陣

布爾鄰接矩陣中每個測試用例所在行出現1的總次數，即為測試用例的權值。例如，對于測試用例I1的權值則為5，D3則為2。按照這些權值的大小就可以對測試用例進行排序以達到最優的排序結果。

3.1.2 DSP＿height

DSP＿height測量標準比較傾向于那些具有最長依賴關聯的測試用例。這是因為具有更長依賴關聯的測試用例有可能存在于更長的場景中。測試用例交互越緊密，測試場景則會包含更多的交互，就會有更高的復雜性。為了計算DSP＿height，需算出一個測試用例所在的所有路徑的長度，然后選取最長的路徑作為衡量測試用例的權值。其是基于Floyd－Warshall shortest－path算法來實現。

我們根據DAG 的布爾鄰接矩陣結合算法2進行運算。對于矩陣中的每一項進行D ［i，k］＋D ［k，j］運算，然后再與D ［i，j］做比較，得出最大值再賦給D ［i，j］。即D ［i，j］＝max （D ［i，j］，D ［i，k］＋D ［k，j］）。經過Floyd－Warshall算法的思想，對每個測試用例進行遍歷，算出其最長路徑［9］。

算法2：Floyd－Warshall longest－path algorithm

輸入：G：an n×n Boolean adjacency matrix representing direct dependencies between test cases.

輸出：D：an n×n integer adjacency matrix representing the length of indirect dependencies between test cases.

（1）D：＝copy of G

（2）for（k＝1；k＜＝n；k＋＋）do//k一定放在最外層，確保運行準確性，提高時間效率。

（3） for（i＝1；i＜＝n；i＋＋）do

（4） for（j＝1；j＜＝n；j＋＋）do

（5） D ［i，j］：＝max （D ［i，j］，D ［i，k］＋D ［k，j］）

（6） end for

（7） end for

（8）end for

（9）return D

按照代碼來計算每個測試用例的權值，即每個測試用例所在行的最大值。

3.2 DSP關于測試集的排序

根據算法1或者算法2我們得到了每個測試用例的權值，進而根據依賴結構對測試集進行排序。這樣在一個測試場景中的多個測試集便可以有優先的執行順序，相對于任意的測試順序，可以節約時間和提高工作效率。卻忽略了當權值相等時怎么排序更好的問題。本文對文獻中的測試集排序算法WEIGHTED＿DSF 和算法WEIGHTED＿DFS＿VISIT進行了部分優化［10］，得出了算法3：WEIGHTED＿DSF＿COVERAGE （WDC）和算法4：WEIGHTED＿DFS＿VISIT＿COVERAGE （WDVC）的流程。

3.2.1 算法3：WEIGHTED＿DSF＿COVERAGE

算法的核心主要是根據DAG 對獨立的測試用例 （無依賴關聯）根據權值對測試用例進行排序，當測試用例權值相等時結合測試用例的代碼覆蓋率進行排序。例如圖1中的I1和I2就是相互獨立的用例。利用算法3的流程，如圖6所示，可以對它們的執行順序進行排序。

3.2.2 算法4：WEIGHTED＿DFS＿VISIT＿COVERAGE

算法4是對交互的測試集進行排序，對權值相等的情況，采用測試用例的代碼覆蓋率進行排序，相對于DSP 中的排序是一個更佳的排序方法。

權值和代碼覆蓋率的頂點深度優先算法，如圖7所示。

其中第5行是防止已經被執行的測試用例再次運行，減少冗余，提高效率。在實際應用中，可以把以上4 種算法結合起來。針對圖1，我們可以得到一個最優的執行順序：I1－D3－D6－D7－D4－D8－I2－D5－D9－D10。

圖6 權值和代碼覆蓋率的深度優先算法

3.3 封閉的依賴結構的優先級

3.3.1 DSP＿ratio

DSP＿ratio的衡量標準是在一條路徑中未執行的測試用例比上已經執行的測試用例的比值，其值越大，說明其權值就越大。此種標準的目的是為了縮減不能發現新錯誤的測試的測試用例。具體描述如式 （1）所示

其中w（ti）＝ ｛i.0.if seen（ti）otherwise，seen（ti）是真值，如果在當前的測試順序中，ti已經被執行。＃表示一個集合中所包含的測試用例個數。同時，每個測試用例的權值就是在這條路徑中的所代表的索引，＃p代表這條路徑的長度。

3.3.2 DSP＿sum/ratio

DSP＿sum/ratio度量標準是，未執行的測試用例除以這條路徑長度的比值，其優點就在于不用計算每個測試用例的權值。其具體描述如式 （2）所示

4 實驗與討論

本文的實驗主要研究WDC 和WDVC 兩種排序方法的優越性，主要關注以下幾個問題：①采用WDC 和WDVC兩種排序方法是否比隨機或貪婪算法錯誤檢錯率高，甚至跟最優的排序方法結果一致。②針對相關性比較弱的測試集，新的排序方法結果是否更好。

4.1 實驗研究對象

為了驗證改進后的算法對測試集排序的有效性，本文選取了幾個真實的系統進行測試，它們分別是Elite，GSM，CRM，MET，CZT，Bash。

這些系統涉及的范圍比較廣，包括網址，組件，單元，系統等。除了GSM 系統的測試集中的依賴結構是為了評估由測試者自己生成的，其它幾個系統測試集依賴結構都是手動的，由項目的開發者得到的。

表1描述了每個系統的詳細信息，其中依賴結構的密度用式 （3）求得，｜E｜表示DAG 里所有的邊數，｜V｜代表所有的測試用例

4.2 實驗所用的其它測試方法

4.2.1 開放的依賴結構中的其它對比方法

（1）［greedy］：測試用例的排序是選擇發現新的最多的測試用例，這種測試只能限制于已知錯誤的系統。

（2）［untreated］：測試用例的排序順序是在編寫時設定的。

（3）［random］：測試用例的排序是隨機的。

表1 被測系統的度量標準

（4）［optimal］：測試用例的順序是使得嚴重錯誤發現速率獲得最大。

4.2.2 封閉依賴結構中的其它對比方法

這些對比方法依次是cg－fn－total，cg－fn－addtal，random，greedy。

4.3 測試用例排序效果度量

4.3.1 錯誤檢錯率的加權平均值APFD

針對不同的測試用例排序方法，使用G.Rothermel等提出的APFD 來作為度量標準。其計算公式如式 （4）所示

由式 （4）可知，APFD 的取值是從0到1，其數值越大說明發現錯誤速率越高。

4.3.2 All Faults Metrics（AF）

在以前的測量標準中，對每個測試用例都是用一樣的成本來度量，這樣在測試成本上就容易造成極大的浪費。為了緩解這個問題，本文提出了一種衡量標準來制約APFD 的不足，即AF （所有缺陷度量），它和APFD 一樣是對整個測試集百分比的一種描述，如果T 是包括n個測試用例的測試集，那么F則是T 所發現的錯誤個數m 的集合，其計算公式如式 （5）所示

其中TFm是指最后發現第m 個錯誤的測試用例。其值越大，則測試集的測試效率就越低。

4.4 實驗結果

基于開放依賴結構的APFD 實驗結果見表2。

基于開放依賴結構的AF實驗結果見表3。

由表2可知，針對本文介紹的開放依賴結構，實驗中的6 個系統相對于任意的和未處理的測試順序，dsp＿height和dsp＿volume標準有著很大的優勢，并且跟optimal和greedy排序方法結果大體一致。

由表2可知，對于系統中依賴性相對弱的測試場景，采用改進后的測試集排序方法WDC 和WDVC，其APFD結果明顯比文獻中的測試結果理想并更接近optimal和greedy的測試結果。

表2 開放依賴結構的APFD

表3 開放依賴結構的AF

從開放依賴結構的實驗對比中可以得到，本文對DSP改進的方法在APFD 和AF 這兩種度量方法上都有一定的優越性，所以也驗證了我們的假設。但本文在考慮測試用例之間依賴結構和代碼覆蓋率結合來對測試集進行綜合排序，隨著在提高錯誤檢錯率方面有顯著的提高，測試成本也有所增加，這是以后測試技術需考慮的問題。同理對封閉的依賴結構的實驗也可以得到兩組同樣的實驗結果。

5 結束語

本文重點從兩個方面研究了基于依賴結構來優化優先級的技術：①基于測試用例交互的復雜性進行權值分配；②基于直接的傳遞閉包算法和直接的深度優先搜索算法的核心思想，對測試集進行優先排序。結合這兩方面來計算測試用例的APFD 和AF，得出節約時間和成本的測試用例優先順序。在今后研究有關根據依賴性計算權值與排序之間的關系是將來研究工作的重點。

［1］WANG Dan，PAN Qiangzong，ZHU Luhua.Fuzzing model based on control dependence path coverage ［J］.Computer Engineering and Design，2012，33 （8）：3078－3082（in Chinese）.［王丹，潘強宗，朱魯華.基于控制依賴路徑覆蓋的Fuzzing模型 ［J］.計算機工程與設計，2012，33 （8）：3078－3082.］

［2］CHEN Shufeng，ZHEN Hongyuan.Dependence analysis and regression testing of object－oriented software ［J］.Computer Application，2009，29 （11）：3110－3113 （in Chinese）.［陳樹峰，鄭洪源.面向軟件的依賴性分析與回歸測試 ［J］］.計算機應用，2009，29 （11），3110－3113.］

［3］GAO Xuejuan，WU Xiaochun.UML sequence based interlocking test case generation ［J］.Application Research of Computers，2013，30 （9）：2740－2743 （in Chinese）. ［高雪娟，吳曉春.應用UML順序圖的聯鎖測試用例生成方法 ［J］.計算機應用研究，2013，30 （9）：2740－2743.］

［4］CHEN Jianxun，XIAO Yiran.Class－integration testing sequence research based on dynamic dependency ［J］.Chinese Journal of Sensors and Actuators，2014，27 （1）：64－69 （in Chinese）.［陳建勛，肖亦然.基于動態依賴的類間測試順序研究 ［J］.傳感技術學報，2014，27 （1）：64－69.］

［5］Haidry S，Miller T.Using dependency structures for prioritization of functional test suites ［J］.IEEE Trans on Software Engineering，2013，39 （2）：258－275.

［6］Chen Yangjun，Chen Yibin.Decomposing DAGs into spanning trees：A new way to compress transitive closures［C］//IEEE 27th International Conference on Data Engineering，2011：1007－1018.

［7］LUO Wenbing，ZHAO Liang，ZHAO Hongyu.Test suite optimization based on graph analysis ［J］.Journal of Computer Engineering，2010，36 （15）：92－102 （in Chinese）.［羅文兵，趙亮，趙洪宇.基于圖分析的測試用例集優化 ［J］.計算機工程，2010，36 （15）：92－102.］

［8］Selvan S，Nataraj RV.Efficient mining of large maximal Bicliques from 3Dsymmetric adjacency matrix ［J］.IEEE Trans on Knowledge and Data Engineering，2010，22 （12）：1797－1802.

［9］Wahid Nasri，Wafa Nafti.A new DAG scheduling algorithm for heterogeneous platforms ［C］//IEEE 2nd International Conference on Parallel Distributed and Grid Computing，2012：114－119.

［10］Marinescu R.Best－first vs.depth－first AND/OR search for multi－objective constraint optimization ［C］//IEEE 22th International Conference on Tools with Artificial Intelligence，2010：439－446.

［11］Kundu D，Sarma M，Samanta D，et al.System testing for object－oriented systems with test case prioritization ［J］.Software Testing，Verification，and Reliability，2009，19 （4）：97－333.