基于依賴結(jié)構(gòu)的功能測(cè)試集排序方法

曹麗娜，高建華

（上海師范大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海200234）

0 引 言

軟件測(cè)試在軟件開(kāi)發(fā)和維護(hù)的各個(gè)階段至關(guān)重要。為了提高軟件質(zhì)量的可靠性，利用測(cè)試用例排序技術(shù)在有限的資源內(nèi)及時(shí)發(fā)現(xiàn)、糾正程序中的錯(cuò)誤和缺陷的特點(diǎn)，以達(dá)到提高軟件測(cè)試的實(shí)用效率，節(jié)約成本的目的。

為了充分提高軟件測(cè)試的有效性，節(jié)約成本。王丹等［1］提出了利用控制依賴控制路徑覆蓋的Fuzzing模型，分析提取的脆弱性語(yǔ)句；陳樹(shù)蜂等［2］通過(guò)分析UML 類圖中的各種靜態(tài)關(guān)系，提出一種基于UML 類圖的依賴性分析模型，來(lái)解決類之間復(fù)雜的依賴性問(wèn)題；高雪娟等［3］利用UML順序圖為主要模型，結(jié)合有向圖和順序圖，采用覆蓋準(zhǔn)則和深度優(yōu)先搜索算法遍歷；陳建勛等［4］分析對(duì)象關(guān)系圖中類間依賴關(guān)系，利用邊刪除規(guī)則去除環(huán)路，最后運(yùn)用有向無(wú)環(huán)圖的拓?fù)湫蛄信判?；S.Haidry等［5］根據(jù)測(cè)試用例之間依賴結(jié)構(gòu)，繪制出有向無(wú)環(huán)圖，根據(jù)算法，得出最優(yōu)的測(cè)試集。然而，這些技術(shù)卻沒(méi)有考慮下述問(wèn)題：測(cè)試集中的測(cè)試用例之間存在功能依賴以及借助什么模型來(lái)描述這種依賴關(guān)系，并且當(dāng)測(cè)試用例權(quán)值相等時(shí)怎么去排序。

針對(duì)此問(wèn)題，借鑒上述思想，本文通過(guò)改進(jìn)DSP技術(shù)的不足之處，總結(jié)出一種表示依賴結(jié)構(gòu)的有向無(wú)環(huán)圖，作為對(duì)測(cè)試集生成的約束，將測(cè)試用例的權(quán)值和代碼覆蓋率相結(jié)合根據(jù)改進(jìn)的算法對(duì)測(cè)試集排序，從而得出最優(yōu)的測(cè)試集，減少測(cè)試集的生成，并同時(shí)保證代碼覆蓋率。

1 背景及相關(guān)知識(shí)

1.1 功能依賴

功能依賴是指在測(cè)試場(chǎng)景中，一些交互或需求必須要在其它一些交互或需求完成后才能執(zhí)行。例如：交互或需求要在交互或需求I2之前執(zhí)行，則稱I2依賴于I1。測(cè)試用例之間固有地繼承了這些關(guān)系，則相對(duì)應(yīng)的測(cè)試用例t1，t2，即t2依賴于t1。

依賴結(jié)構(gòu)可以用有向無(wú)環(huán)圖 （directed acyclic graph）表示，即G＝ （V，E）其中：節(jié)點(diǎn)的有限集合V＝ ｛t1，t2，t3，t4....tn｝，邊的集合E＝ ｛e1，e2，e3....em｝，E則表示是測(cè)試用例之間的功能依賴。依賴結(jié)構(gòu)可以分成兩類：開(kāi)放的依賴結(jié)構(gòu)，封閉的依賴結(jié)構(gòu)。開(kāi)放的依賴結(jié)構(gòu)是指對(duì)于兩個(gè)依賴的測(cè)試用例t1和t2，即在執(zhí)行時(shí)t1在某些情況下要先于t2執(zhí)行。封閉的依賴結(jié)構(gòu)是指對(duì)于兩個(gè)依賴的測(cè)試用例t1和t2，t1必須要在t2之前執(zhí)行，如圖1所示。

圖1 一個(gè)有向無(wú)環(huán)圖的例子

對(duì)于圖1中的測(cè)試用例，若是開(kāi)放依賴結(jié)構(gòu)，則測(cè)試順序是：I1－I2－D3－D4…。即I1已執(zhí)行，那么D3和D4就處于開(kāi)放狀態(tài)，若再執(zhí)行D3，I1不需再次執(zhí)行，其好處在于減少不必要的冗余。若是封閉的依賴結(jié)構(gòu)，則測(cè)試順序是：I1－I2－I1－D3…，如I1已執(zhí)行，接著執(zhí)行I2，若接下來(lái)執(zhí)行D3，那么其依賴結(jié)構(gòu)I1就需再次執(zhí)行。本文將重點(diǎn)介紹開(kāi)放的依賴結(jié)構(gòu)。

1.2 DAG 在測(cè)試集中的應(yīng)用

DAG 是用來(lái)描述測(cè)試集內(nèi)部測(cè)試用例之間功能依賴，若要想從測(cè)試集內(nèi)部提取這些依賴性，就需要對(duì)一個(gè)系統(tǒng)的需求和設(shè)計(jì)有一定的了解，這樣才能手動(dòng)的繪制出DAG。通過(guò)分析DAG 圖，我們可以找到各個(gè)測(cè)試用例之間的功能依賴，及復(fù)雜交互程度，進(jìn)而根據(jù)算法求出權(quán)值，并依次確定各個(gè)測(cè)試用例的執(zhí)行順序［6］。

2 依賴結(jié)構(gòu)的圖覆蓋范圍值的測(cè)量標(biāo)準(zhǔn)

DSP是根據(jù)圖覆蓋范圍值進(jìn)行優(yōu)化的，它是對(duì)一個(gè)測(cè)試用例相關(guān)性的復(fù)雜程度的一個(gè)度量，又因?yàn)殚_(kāi)放的依賴結(jié)構(gòu)和封閉的依賴結(jié)構(gòu)中的測(cè)試用例的執(zhí)行順序的標(biāo)準(zhǔn)不同，所以對(duì)于它們必須設(shè)置不同的衡量標(biāo)準(zhǔn)［7］。

2.1 開(kāi)放的依賴結(jié)構(gòu)的標(biāo)準(zhǔn)

（1）一個(gè)測(cè)試用例的所有依賴關(guān)聯(lián)的測(cè)試用例。其提高了密切相關(guān)的測(cè)試用例被更早執(zhí)行的可能性。例如：圖1中的I1的依賴關(guān)聯(lián)測(cè)試用例是：D3，D6，D7，D4，D8。D3的依賴關(guān)聯(lián)測(cè)試用例是：D6和D7。

（2）一個(gè)測(cè)試用例的直接或間接的最長(zhǎng)路徑。其提高了線性相關(guān)的測(cè)試用例被更早執(zhí)行的可能性。例如，圖1中的I1有三條路徑，其長(zhǎng)度是一樣的，都是其最長(zhǎng)路徑。

2.2 封閉的依賴結(jié)構(gòu)的標(biāo)準(zhǔn)

（1）在一條路徑中沒(méi)有被執(zhí)行的測(cè)試用例的數(shù)量。

（2）在一條路徑中沒(méi)有被執(zhí)行的測(cè)試用例的數(shù)量比上已經(jīng)被執(zhí)行的測(cè)試用例的數(shù)量。

（3）未被執(zhí)行的測(cè)試用例除以這條路徑的長(zhǎng)度。

2.3 DSP依賴結(jié)構(gòu)的弊端

S.Haidry驗(yàn)證了DSP 技術(shù)具有一定的優(yōu)越性，但當(dāng)DAG 測(cè)試用例的權(quán)值相等時(shí)可以有任意的排序，例如圖2中的DAG，若按照S.Haidry 提出的方法進(jìn)行排序有：t1－t2－t4－t6－t3－t5－t7或 者t1－t3－t5－t7－t2－t4－t6，計(jì) 算 兩種路徑的APFD 結(jié)果應(yīng)該是相同的。若我們?cè)诳紤]權(quán)值相同的排序時(shí)結(jié)合測(cè)試用例的代碼覆蓋率去排序，可以得到更優(yōu)的排序結(jié)果。例如圖2 括號(hào)中代表每個(gè)測(cè)試用例的代碼覆蓋率，可以算的以上兩種排序的APFD 值分別為：APFD （t1－t2－t4－t6－t3－t5－t7）＝62%。APFD （t1－t3－t5－t7－t2－t4－t6）＝56%。

圖2 含有代碼覆蓋率的有向無(wú)環(huán)圖

3 DSP技術(shù)

3.1 開(kāi)放依賴結(jié)構(gòu)的優(yōu)先級(jí)

根據(jù)開(kāi)放依賴結(jié)構(gòu)的圖形覆蓋范圍值的衡量標(biāo)準(zhǔn)，文獻(xiàn)中把優(yōu)化測(cè)試用例的技術(shù)分成兩種，分別是DSP＿volume和DSP＿h(yuǎn)eight。

3.1.1 DSP＿volume

DSP＿volume測(cè)量標(biāo)準(zhǔn)給那些具有更多的依賴關(guān)聯(lián)的測(cè)試用例更高的權(quán)值。這是因?yàn)樵谝蕾嚱Y(jié)構(gòu)中緊密相連的測(cè)試用例，在被測(cè)試的系統(tǒng)本身它們也是密切相關(guān)的，并且交互也更頻繁。這樣便能更早的發(fā)現(xiàn)更多的錯(cuò)誤，最終提高錯(cuò)誤檢錯(cuò)率。為了計(jì)算一個(gè)測(cè)試用例的DSP＿volume，需先計(jì)算出這個(gè)測(cè)試用例所有直接和間接的依賴關(guān)聯(lián)測(cè)試用例。在本文中我們利用直接的傳遞閉包算法來(lái)實(shí)現(xiàn)。

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

（1）根據(jù)系統(tǒng)的需求和設(shè)計(jì)得到DAG 圖，如一個(gè)DAG 的例子如圖3所示。

圖3 一個(gè)有向無(wú)環(huán)圖的例子

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

圖4 一個(gè)DAG 的鄰接矩陣

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

圖5 一個(gè)布爾鄰接矩陣

布爾鄰接矩陣中每個(gè)測(cè)試用例所在行出現(xiàn)1的總次數(shù)，即為測(cè)試用例的權(quán)值。例如，對(duì)于測(cè)試用例I1的權(quán)值則為5，D3則為2。按照這些權(quán)值的大小就可以對(duì)測(cè)試用例進(jìn)行排序以達(dá)到最優(yōu)的排序結(jié)果。

3.1.2 DSP＿h(yuǎn)eight

DSP＿h(yuǎn)eight測(cè)量標(biāo)準(zhǔn)比較傾向于那些具有最長(zhǎng)依賴關(guān)聯(lián)的測(cè)試用例。這是因?yàn)榫哂懈L(zhǎng)依賴關(guān)聯(lián)的測(cè)試用例有可能存在于更長(zhǎng)的場(chǎng)景中。測(cè)試用例交互越緊密，測(cè)試場(chǎng)景則會(huì)包含更多的交互，就會(huì)有更高的復(fù)雜性。為了計(jì)算DSP＿h(yuǎn)eight，需算出一個(gè)測(cè)試用例所在的所有路徑的長(zhǎng)度，然后選取最長(zhǎng)的路徑作為衡量測(cè)試用例的權(quán)值。其是基于Floyd－Warshall shortest－path算法來(lái)實(shí)現(xiàn)。

我們根據(jù)DAG 的布爾鄰接矩陣結(jié)合算法2進(jìn)行運(yùn)算。對(duì)于矩陣中的每一項(xiàng)進(jìn)行D ［i，k］＋D ［k，j］運(yùn)算，然后再與D ［i，j］做比較，得出最大值再賦給D ［i，j］。即D ［i，j］＝max （D ［i，j］，D ［i，k］＋D ［k，j］）。經(jīng)過(guò)Floyd－Warshall算法的思想，對(duì)每個(gè)測(cè)試用例進(jìn)行遍歷，算出其最長(zhǎng)路徑［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一定放在最外層，確保運(yùn)行準(zhǔn)確性，提高時(shí)間效率。

（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

按照代碼來(lái)計(jì)算每個(gè)測(cè)試用例的權(quán)值，即每個(gè)測(cè)試用例所在行的最大值。

3.2 DSP關(guān)于測(cè)試集的排序

根據(jù)算法1或者算法2我們得到了每個(gè)測(cè)試用例的權(quán)值，進(jìn)而根據(jù)依賴結(jié)構(gòu)對(duì)測(cè)試集進(jìn)行排序。這樣在一個(gè)測(cè)試場(chǎng)景中的多個(gè)測(cè)試集便可以有優(yōu)先的執(zhí)行順序，相對(duì)于任意的測(cè)試順序，可以節(jié)約時(shí)間和提高工作效率。卻忽略了當(dāng)權(quán)值相等時(shí)怎么排序更好的問(wèn)題。本文對(duì)文獻(xiàn)中的測(cè)試集排序算法WEIGHTED＿DSF 和算法WEIGHTED＿DFS＿VISIT進(jìn)行了部分優(yōu)化［10］，得出了算法3：WEIGHTED＿DSF＿COVERAGE （WDC）和算法4：WEIGHTED＿DFS＿VISIT＿COVERAGE （WDVC）的流程。

3.2.1 算法3：WEIGHTED＿DSF＿COVERAGE

算法的核心主要是根據(jù)DAG 對(duì)獨(dú)立的測(cè)試用例 （無(wú)依賴關(guān)聯(lián)）根據(jù)權(quán)值對(duì)測(cè)試用例進(jìn)行排序，當(dāng)測(cè)試用例權(quán)值相等時(shí)結(jié)合測(cè)試用例的代碼覆蓋率進(jìn)行排序。例如圖1中的I1和I2就是相互獨(dú)立的用例。利用算法3的流程，如圖6所示，可以對(duì)它們的執(zhí)行順序進(jìn)行排序。

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

算法4是對(duì)交互的測(cè)試集進(jìn)行排序，對(duì)權(quán)值相等的情況，采用測(cè)試用例的代碼覆蓋率進(jìn)行排序，相對(duì)于DSP 中的排序是一個(gè)更佳的排序方法。

權(quán)值和代碼覆蓋率的頂點(diǎn)深度優(yōu)先算法，如圖7所示。

其中第5行是防止已經(jīng)被執(zhí)行的測(cè)試用例再次運(yùn)行，減少冗余，提高效率。在實(shí)際應(yīng)用中，可以把以上4 種算法結(jié)合起來(lái)。針對(duì)圖1，我們可以得到一個(gè)最優(yōu)的執(zhí)行順序：I1－D3－D6－D7－D4－D8－I2－D5－D9－D10。

圖6 權(quán)值和代碼覆蓋率的深度優(yōu)先算法

3.3 封閉的依賴結(jié)構(gòu)的優(yōu)先級(jí)

3.3.1 DSP＿ratio

DSP＿ratio的衡量標(biāo)準(zhǔn)是在一條路徑中未執(zhí)行的測(cè)試用例比上已經(jīng)執(zhí)行的測(cè)試用例的比值，其值越大，說(shuō)明其權(quán)值就越大。此種標(biāo)準(zhǔn)的目的是為了縮減不能發(fā)現(xiàn)新錯(cuò)誤的測(cè)試的測(cè)試用例。具體描述如式 （1）所示

其中w（ti）＝ ｛i.0.if seen（ti）otherwise，seen（ti）是真值，如果在當(dāng)前的測(cè)試順序中，ti已經(jīng)被執(zhí)行。＃表示一個(gè)集合中所包含的測(cè)試用例個(gè)數(shù)。同時(shí)，每個(gè)測(cè)試用例的權(quán)值就是在這條路徑中的所代表的索引，＃p代表這條路徑的長(zhǎng)度。

3.3.2 DSP＿sum/ratio

DSP＿sum/ratio度量標(biāo)準(zhǔn)是，未執(zhí)行的測(cè)試用例除以這條路徑長(zhǎng)度的比值，其優(yōu)點(diǎn)就在于不用計(jì)算每個(gè)測(cè)試用例的權(quán)值。其具體描述如式 （2）所示

4 實(shí)驗(yàn)與討論

本文的實(shí)驗(yàn)主要研究WDC 和WDVC 兩種排序方法的優(yōu)越性，主要關(guān)注以下幾個(gè)問(wèn)題：①采用WDC 和WDVC兩種排序方法是否比隨機(jī)或貪婪算法錯(cuò)誤檢錯(cuò)率高，甚至跟最優(yōu)的排序方法結(jié)果一致。②針對(duì)相關(guān)性比較弱的測(cè)試集，新的排序方法結(jié)果是否更好。

4.1 實(shí)驗(yàn)研究對(duì)象

為了驗(yàn)證改進(jìn)后的算法對(duì)測(cè)試集排序的有效性，本文選取了幾個(gè)真實(shí)的系統(tǒng)進(jìn)行測(cè)試，它們分別是Elite，GSM，CRM，MET，CZT，Bash。

這些系統(tǒng)涉及的范圍比較廣，包括網(wǎng)址，組件，單元，系統(tǒng)等。除了GSM 系統(tǒng)的測(cè)試集中的依賴結(jié)構(gòu)是為了評(píng)估由測(cè)試者自己生成的，其它幾個(gè)系統(tǒng)測(cè)試集依賴結(jié)構(gòu)都是手動(dòng)的，由項(xiàng)目的開(kāi)發(fā)者得到的。

表1描述了每個(gè)系統(tǒng)的詳細(xì)信息，其中依賴結(jié)構(gòu)的密度用式 （3）求得，｜E｜表示DAG 里所有的邊數(shù)，｜V｜代表所有的測(cè)試用例

4.2 實(shí)驗(yàn)所用的其它測(cè)試方法

4.2.1 開(kāi)放的依賴結(jié)構(gòu)中的其它對(duì)比方法

（1）［greedy］：測(cè)試用例的排序是選擇發(fā)現(xiàn)新的最多的測(cè)試用例，這種測(cè)試只能限制于已知錯(cuò)誤的系統(tǒng)。

（2）［untreated］：測(cè)試用例的排序順序是在編寫(xiě)時(shí)設(shè)定的。

（3）［random］：測(cè)試用例的排序是隨機(jī)的。

表1 被測(cè)系統(tǒng)的度量標(biāo)準(zhǔn)

（4）［optimal］：測(cè)試用例的順序是使得嚴(yán)重錯(cuò)誤發(fā)現(xiàn)速率獲得最大。

4.2.2 封閉依賴結(jié)構(gòu)中的其它對(duì)比方法

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

4.3 測(cè)試用例排序效果度量

4.3.1 錯(cuò)誤檢錯(cuò)率的加權(quán)平均值A(chǔ)PFD

針對(duì)不同的測(cè)試用例排序方法，使用G.Rothermel等提出的APFD 來(lái)作為度量標(biāo)準(zhǔn)。其計(jì)算公式如式 （4）所示

由式 （4）可知，APFD 的取值是從0到1，其數(shù)值越大說(shuō)明發(fā)現(xiàn)錯(cuò)誤速率越高。

4.3.2 All Faults Metrics（AF）

在以前的測(cè)量標(biāo)準(zhǔn)中，對(duì)每個(gè)測(cè)試用例都是用一樣的成本來(lái)度量，這樣在測(cè)試成本上就容易造成極大的浪費(fèi)。為了緩解這個(gè)問(wèn)題，本文提出了一種衡量標(biāo)準(zhǔn)來(lái)制約APFD 的不足，即AF （所有缺陷度量），它和APFD 一樣是對(duì)整個(gè)測(cè)試集百分比的一種描述，如果T 是包括n個(gè)測(cè)試用例的測(cè)試集，那么F則是T 所發(fā)現(xiàn)的錯(cuò)誤個(gè)數(shù)m 的集合，其計(jì)算公式如式 （5）所示

其中TFm是指最后發(fā)現(xiàn)第m 個(gè)錯(cuò)誤的測(cè)試用例。其值越大，則測(cè)試集的測(cè)試效率就越低。

4.4 實(shí)驗(yàn)結(jié)果

基于開(kāi)放依賴結(jié)構(gòu)的APFD 實(shí)驗(yàn)結(jié)果見(jiàn)表2。

基于開(kāi)放依賴結(jié)構(gòu)的AF實(shí)驗(yàn)結(jié)果見(jiàn)表3。

由表2可知，針對(duì)本文介紹的開(kāi)放依賴結(jié)構(gòu)，實(shí)驗(yàn)中的6 個(gè)系統(tǒng)相對(duì)于任意的和未處理的測(cè)試順序，dsp＿h(yuǎn)eight和dsp＿volume標(biāo)準(zhǔn)有著很大的優(yōu)勢(shì)，并且跟optimal和greedy排序方法結(jié)果大體一致。

由表2可知，對(duì)于系統(tǒng)中依賴性相對(duì)弱的測(cè)試場(chǎng)景，采用改進(jìn)后的測(cè)試集排序方法WDC 和WDVC，其APFD結(jié)果明顯比文獻(xiàn)中的測(cè)試結(jié)果理想并更接近optimal和greedy的測(cè)試結(jié)果。

表2 開(kāi)放依賴結(jié)構(gòu)的APFD

表3 開(kāi)放依賴結(jié)構(gòu)的AF

從開(kāi)放依賴結(jié)構(gòu)的實(shí)驗(yàn)對(duì)比中可以得到，本文對(duì)DSP改進(jìn)的方法在APFD 和AF 這兩種度量方法上都有一定的優(yōu)越性，所以也驗(yàn)證了我們的假設(shè)。但本文在考慮測(cè)試用例之間依賴結(jié)構(gòu)和代碼覆蓋率結(jié)合來(lái)對(duì)測(cè)試集進(jìn)行綜合排序，隨著在提高錯(cuò)誤檢錯(cuò)率方面有顯著的提高，測(cè)試成本也有所增加，這是以后測(cè)試技術(shù)需考慮的問(wèn)題。同理對(duì)封閉的依賴結(jié)構(gòu)的實(shí)驗(yàn)也可以得到兩組同樣的實(shí)驗(yàn)結(jié)果。

5 結(jié)束語(yǔ)

本文重點(diǎn)從兩個(gè)方面研究了基于依賴結(jié)構(gòu)來(lái)優(yōu)化優(yōu)先級(jí)的技術(shù)：①基于測(cè)試用例交互的復(fù)雜性進(jìn)行權(quán)值分配；②基于直接的傳遞閉包算法和直接的深度優(yōu)先搜索算法的核心思想，對(duì)測(cè)試集進(jìn)行優(yōu)先排序。結(jié)合這兩方面來(lái)計(jì)算測(cè)試用例的APFD 和AF，得出節(jié)約時(shí)間和成本的測(cè)試用例優(yōu)先順序。在今后研究有關(guān)根據(jù)依賴性計(jì)算權(quán)值與排序之間的關(guān)系是將來(lái)研究工作的重點(diǎn)。

［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）.［王丹，潘強(qiáng)宗，朱魯華.基于控制依賴路徑覆蓋的Fuzzing模型 ［J］.計(jì)算機(jī)工程與設(shè)計(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）.［陳樹(shù)峰，鄭洪源.面向軟件的依賴性分析與回歸測(cè)試 ［J］］.計(jì)算機(jī)應(yīng)用，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）. ［高雪娟，吳曉春.應(yīng)用UML順序圖的聯(lián)鎖測(cè)試用例生成方法 ［J］.計(jì)算機(jī)應(yīng)用研究，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）.［陳建勛，肖亦然.基于動(dòng)態(tài)依賴的類間測(cè)試順序研究 ［J］.傳感技術(shù)學(xué)報(bào)，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）.［羅文兵，趙亮，趙洪宇.基于圖分析的測(cè)試用例集優(yōu)化 ［J］.計(jì)算機(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.