基于圈復(fù)雜度的靜態(tài)測試用例排序方法

陳夢云　高建華

(上海師范大學(xué)信息與機(jī)電工程學(xué)院　上海 200234)

?

基于圈復(fù)雜度的靜態(tài)測試用例排序方法

陳夢云高建華

(上海師范大學(xué)信息與機(jī)電工程學(xué)院上海 200234)

摘要針對如何排列測試用例的問題，提出一種基于圈復(fù)雜度的靜態(tài)測試用例排序方法。首先介紹圈復(fù)雜度和基于方法覆蓋的測試用例排序算法；然后將圈復(fù)雜度應(yīng)用到排序算法中，設(shè)計了兩種新的排序算法；最后通過實驗，檢測改進(jìn)方法在錯誤檢測方面的有效性。實驗結(jié)果表明，與已有的幾種優(yōu)先級技術(shù)對比，上述改進(jìn)方法能夠達(dá)到更高的錯誤檢測效率，有利于提高測試效率。

關(guān)鍵詞測試用例排序圈復(fù)雜度排序算法錯誤檢測效率

0引言

測試用例優(yōu)先級排序技術(shù)主要是將測試用例按照一定的準(zhǔn)則進(jìn)行排序，以便盡早達(dá)到覆蓋率標(biāo)準(zhǔn)或檢錯目標(biāo)。在軟件測試中，不同的測試用例測試的功能點(diǎn)不同，對代碼覆蓋的能力和檢錯能力也不相同。在工程實踐中，測試人員通過使用測試用例優(yōu)先級技術(shù)，能夠更快地找到軟件產(chǎn)品中存在的錯誤和缺陷，從而提高測試效率和軟件產(chǎn)品的可靠性。

目前測試用例優(yōu)先級排序技術(shù)主要分為基于歷史信息的測試用例優(yōu)先級技術(shù)和基于需求的測試用例優(yōu)先級技術(shù)。梅宏[1]等分別針對語句覆蓋和方法覆蓋的情況，提出了八種不同的測試用例排序技術(shù)，這些技術(shù)將測試用例的覆蓋率作為檢錯能力的評估指標(biāo)，依次選取覆蓋率最大的測試用例，從而優(yōu)化測試用例。Srikanth[2]等人通過對需求的重要程度以及對測試不同需求所需的耗費(fèi)進(jìn)行評估，研究了基于需求的測試用例排序技術(shù)。

文獻(xiàn)[1]中基于方法覆蓋的TJ-MM和AJ-MM兩種優(yōu)先級技術(shù)，以測試用例的方法覆蓋率作為測試用例的排序依據(jù)。然而由于每個測試用例覆蓋方法的程序代碼復(fù)雜度不一樣，測試用例的潛在檢錯效率則不同，因此僅僅依靠覆蓋率來評估測試用例的檢錯率不夠完備。

本文對以上技術(shù)進(jìn)行擴(kuò)展，研究測試用例覆蓋方法的圈復(fù)雜度，提出一種基于圈復(fù)雜度的靜態(tài)測試用例排序方法，并設(shè)計新技術(shù)的排序算法。本文主要研究以下四個方面的工作：(1) 分析測試用例的調(diào)用圖，獲取每個測試用例的覆蓋方法。(2) 引入圈復(fù)雜度，計算測試用例覆蓋方法的圈復(fù)雜度。(3) 設(shè)計新的排序算法，將圈復(fù)雜度應(yīng)用到測試用例的排序算法中。(4) 設(shè)計實驗，將新技術(shù)與已有的幾種技術(shù)進(jìn)行對比，證明新技術(shù)的有效性和高效性。

1相關(guān)知識

靜態(tài)測試，是指在非運(yùn)行狀態(tài)下，主要采取代碼走查、技術(shù)評審和代碼審查的方法對軟件產(chǎn)品進(jìn)行測試，檢查軟件是否符合編程標(biāo)準(zhǔn)，達(dá)到發(fā)現(xiàn)錯誤和糾正錯誤的目的。

1.1測試用例優(yōu)先級技術(shù)

測試用例優(yōu)先級技術(shù)在文獻(xiàn)[3]中已提出，其定義如下：

定義1給定一個測試集TS，其中PT為TS中的測試用例所有排列的集合，測試用例優(yōu)先級的問題是找到一種排列PS∈PT，對于?T′∈PT，使得f(PS)>=f(T′)成立，f是與PT相關(guān)的一個函數(shù)，它所得到的實數(shù)值反映了錯誤檢測效率。

1.2圈復(fù)雜度

圈復(fù)雜度是一種代碼復(fù)雜度的衡量標(biāo)準(zhǔn)。在軟件測試中，圈復(fù)雜度用來衡量一個模塊判定結(jié)構(gòu)的復(fù)雜程度。根據(jù)經(jīng)驗，圈復(fù)雜度越大，程序出現(xiàn)錯誤的可能性則越大，本文將測試用例覆蓋方法的圈復(fù)雜度作為測試用例優(yōu)先級排序的重要影響因子。

1.2.1圈復(fù)雜度概念

圈復(fù)雜度的計算是建立在控制流圖的基礎(chǔ)之上的。程序中的語句構(gòu)成控制流圖中的節(jié)點(diǎn)，并由帶箭頭的曲線將節(jié)點(diǎn)按照程序執(zhí)行順序進(jìn)行連接。圈復(fù)雜度計算公式為：

V(G)=E-N+2

(1)

在式(1)中，V(G)表示圈復(fù)雜度，E表示控制流圖的邊的數(shù)量，N表示控制流圖的節(jié)點(diǎn)數(shù)。

本文提供一個簡單的示例來描述方法圈復(fù)雜度。圖1為示例代碼，圖2為示例代碼的控制流圖，其中e1、e2、e3和e4表示邊，A、B、C和D表示節(jié)點(diǎn)。根據(jù)式(1)，可得到示例代碼的圈復(fù)雜度V(G)= 2。

圖1　示例代碼　　　　　　圖2　示例控制流圖

1.2.2不同程序結(jié)構(gòu)的圈復(fù)雜度計算

圖3列舉了四種程序結(jié)構(gòu)的控制流圖，各種復(fù)雜方法的控制流圖都能用以下四種結(jié)構(gòu)表示，根據(jù)式(1)可計算出各程序結(jié)構(gòu)的圈復(fù)雜度，即:Va(G)=1，Vb(G)=2，Vc(G)=3，Vd(G)=2。

圖3　各判斷語句的控制流圖

1.2.3圈復(fù)雜度的度量工具

圈復(fù)雜度是代碼復(fù)雜度的一個的指示器。Java 測試人員可使用一些開放源碼工具來報告圈復(fù)雜度。其中一個工具是 JavaNCSS，測試人員可以利用 Ant 任務(wù)或 Maven 插件配置 JavaNCSS，它通過檢查 Java 源文件來確定方法和類的長度，收集代碼庫中每個方法的圈復(fù)雜度，即測試人員可以從生成的報告獲取代碼庫中每個方法的圈復(fù)雜度。JavaNCSS 不是惟一用于 Java 平臺生成復(fù)雜度報告的工具，其中PMD 和CheckStyle也是具有類似的圈復(fù)雜度規(guī)則的開放源碼項目。除以上列舉的幾種工具外，還存在多種可收集圈復(fù)雜度的源代碼工具。在軟件測試中，可以選取合適的開放源碼工具完成復(fù)雜度的統(tǒng)計工作。

2優(yōu)先排序技術(shù)原理

本文在基于方法覆蓋的優(yōu)先級技術(shù)基礎(chǔ)上，將測試用例覆蓋方法的圈復(fù)雜度應(yīng)用于排序算法中，并將計算結(jié)果作為測試用例的排序依據(jù)。以下描述了優(yōu)先排序技術(shù)的主要步驟，并研究基于圈復(fù)雜度的兩種測試用例優(yōu)先排序算法。

2.1優(yōu)先排序技術(shù)的主要步驟

基于圈復(fù)雜度的測試用例排序方法主要包含如下三個步驟：

(1) 對于待測試程序，給定測試集TS和結(jié)果集PS，PS用于存放排序后的測試用例，初始化時PS賦空值。

(2) 在每次迭代排序過程中，計算每個測試用例覆蓋方法的圈復(fù)雜度，將圈復(fù)雜度應(yīng)用到排序算法中，得到測試用例的測試能力TA(Testing Ability)值，并將具有最大TA值的測試用例從測試集TS中移除到結(jié)果集PS中。若存在TA值相同但不為0的測試用例時，則排序技術(shù)采用隨機(jī)策略，將其中一個測試用例放入測試結(jié)果集PS中。

(3) 重復(fù)第二步，直到TS的測試用例全部移除為止，最后輸出結(jié)果集PS。

2.2全覆蓋排序算法

圖4是全覆蓋排序算法的偽代碼，其中TS表示測試集，用于存放初始狀態(tài)給定的測試用例。γ(t)表示測試結(jié)果集，用于存放排序后的測試用例。TA值表示測試用例覆蓋的所有方法的圈復(fù)雜度的累加和，作為測試用例檢錯能力的評估指標(biāo)。

圖4　全覆蓋排序算法

由圖4可知，全覆蓋排序算法忽略已選擇的測試用例對后續(xù)排序的影響。文獻(xiàn)[1]中基于方法覆蓋的TJ-MM技術(shù)，采用全覆蓋排序算法，以覆蓋方法數(shù)來評估測試用例的檢錯能力，其TA值計算公式如下：

TATJ-MM(t)=|{m|m∈γ(t)}|

(2)

式中， γ(t)表示與測試用例t相關(guān)的方法集，m為γ(t)中的方法，TATJ-MM表示測試用例t覆蓋的方法數(shù)，TJ-MM根據(jù)TATJ-MM的降序來排列測試用例。

本文在TJ-MM的基礎(chǔ)上，考慮測試用例覆蓋方法程序代碼的復(fù)雜度對代碼質(zhì)量的影響，對全覆蓋排序算法進(jìn)行改進(jìn)。本文將測試用例覆蓋方法的圈復(fù)雜度作為測試用例檢錯能力的評估指標(biāo)，并以此作為排序依據(jù)。本文將改進(jìn)后的基于圈復(fù)雜度的全覆蓋排序技術(shù)用T-CC表示，它的 TA值計算公式如下：

(3)

式中， γ(t)和mi與式(2)的γ(t)和m表示的含義相同，n表示測試用例t覆蓋的方法數(shù)，V(Gmi)表示方法mi的圈復(fù)雜度，上述改進(jìn)算法的TAT-CC值，表示測試用例覆蓋的全部方法的圈復(fù)雜度的累加和，作為T-CC技術(shù)檢錯能力的評估指標(biāo)和排序依據(jù)。

2.3遞增覆蓋排序算法

類似全覆蓋算法，圖5是遞增覆蓋排序算法的偽代碼，相對全覆蓋排序算法，其增加了一個數(shù)據(jù)集SS，用于存放排序過程中已選擇的測試用例。

圖5　遞增覆蓋排序算法

由圖5可知，遞增覆蓋排序算法考慮已選擇的測試用例對剩余測試用例排序的影響，通過剔除冗余方法，調(diào)整剩余測試用例的TA值，繼續(xù)迭代排序剩余的測試用例。文獻(xiàn)[1]中基于方法覆蓋的AJ-MM技術(shù)，采用遞增覆蓋排序算法，其TA值計算公式如下：

(4)

式中，γ(t)和m與式(2)中表示的含義相同，SS表示已選擇的測試用例的集合，t′表示SS中的測試用例，γ(t′)表示排序過程中已選擇的測試用例的方法集，TAAJ-MM表示測試用例t未被覆蓋的方法數(shù)，AJ-MM技術(shù)根據(jù)TAAJ-MM降序來排列測試用例。

與全覆蓋排序算法類似，本文也將測試用例覆蓋方法的圈復(fù)雜度應(yīng)用于遞增覆蓋排序算法。本文在AJ-MM的基礎(chǔ)上，對已有的遞增覆蓋排序算法進(jìn)行改進(jìn)，并將改進(jìn)后的基于圈復(fù)雜度的遞增覆蓋排序技術(shù)用A-CC表示，其 TA值計算公式如下：

(5)

式中，γ(t)、mi、n和V(Gmi)與式(3)中表示的含義相同，SS、t′和γ(t′)與式(4)中表示的含義相同，TAA-CC表示測試用例排除已選擇的方法之后剩余方法的圈復(fù)雜度的累加和，作為A-CC技術(shù)檢錯能力的評估指標(biāo)和排序依據(jù)。

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

為了研究基于圈復(fù)雜度的優(yōu)先排序技術(shù)的有效性，本文引入文獻(xiàn)[1]中基于方法覆蓋的的兩種排序技術(shù)(TJ-MM和AJ-MM)、隨機(jī)排序技術(shù)(ROM)和最優(yōu)排序技術(shù)(OPT)。其中隨機(jī)排序技術(shù)是隨機(jī)排列測試用例的一種排序方法，最優(yōu)排序技術(shù)是發(fā)現(xiàn)錯誤效率最高的一種優(yōu)先級技術(shù)，是一種理想方法。本文將新技術(shù)與這些已有的技術(shù)進(jìn)行對比，重點(diǎn)關(guān)注以下兩個問題：

(1) 與隨機(jī)排序技術(shù)相比，新技術(shù)的檢錯效率如何？能否達(dá)到最優(yōu)排序技術(shù)的檢錯效果？

(2) 與已有的TJ-MM和AJ-MM對比，T-CC與A-CC的錯誤檢測效率是否有所提高？

3.1實驗研究對象

本文選擇的實驗對象是一個理財系統(tǒng)，使用這個系統(tǒng)，用戶可以實現(xiàn)用戶注冊、登錄、查看理財產(chǎn)品、購買理財產(chǎn)品、預(yù)約理財產(chǎn)品和續(xù)投理財產(chǎn)品等功能。為了從錯誤檢錯效率方面來評估新的排序方法的性能，實驗可以在查詢訂單、預(yù)約訂單、取消訂單和續(xù)投訂單等業(yè)務(wù)代碼如MyOrderSearch.java、OrderAppointment.java、OrderCannel.java 和OrderContinuedInvest.java等中注入數(shù)據(jù)引用錯誤、數(shù)據(jù)聲明錯誤和控制流程錯誤等。本文針對不同功能模塊設(shè)計了四組測試集，分別為TS1、TS2、TS3和TS4。表1顯示了這四組測試集的信息。

表1　測試集的錯誤分布信息

3.2測試用例排序效果度量APFD

本實驗以錯誤檢測率作為優(yōu)先排序技術(shù)有效性的主要評估指標(biāo)。本文采用的度量標(biāo)準(zhǔn)是APFD[1](weighted average of the percentage of faults detected)。APFD計算公式如下：

(6)

式中，n表示測試用例的個數(shù)，m表示被檢測錯誤的總數(shù)，TFi表示最早暴露錯誤i所需執(zhí)行的測試用例的個數(shù)。APFD數(shù)值越大說明錯誤發(fā)現(xiàn)速率越快，錯誤檢測效率越高。

3.3實驗結(jié)果分析

表2顯示了四組測試集中各排序技術(shù)排序后的APFD值。圖6以圖的形式更加直觀地呈現(xiàn)四組測試集中各種排序技術(shù)的對比結(jié)果。圖中橫軸表示各種優(yōu)先級排序技術(shù)，縱軸表示優(yōu)先級排序技術(shù)的度量值，即APFD值。由圖6可知改進(jìn)技術(shù)相對已有的基于方法覆蓋的排序技術(shù)在錯誤檢測效率方面有所提高。

表2　測試結(jié)果APFD值

針對問題(1)，圖7顯示了基于圈復(fù)雜度的兩種排序技術(shù)與隨機(jī)排序技術(shù)和最優(yōu)排序技術(shù)對比結(jié)果圖。

由圖7可知， T-CC和A-CC兩種排序技術(shù)的錯誤檢測率都高于隨機(jī)排序技術(shù)的錯誤檢測率，但都不及最優(yōu)排序技術(shù)的錯誤檢測率，驗證了新技術(shù)的有效性。

針對問題(2)，圖8顯示了應(yīng)用全覆蓋排序算法的優(yōu)先排序技術(shù)對比圖。圖9顯示了應(yīng)用遞增覆蓋排序算法的優(yōu)先排序技術(shù)對比圖。

由圖8可知，對于應(yīng)用全覆蓋排序算法的排序技術(shù)，在四組測試集中，T-CC都要比TJ-MM檢錯效率高，證明了基于圈復(fù)雜度的排序技術(shù)在應(yīng)用全覆蓋排序算法的高效性。

類似應(yīng)用全覆蓋排序算法的排序技術(shù)，由圖9可知，對于應(yīng)用遞增覆蓋排序算法的排序技術(shù)， A-CC都要比AJ-MM的檢錯效率高，證明了基于圈復(fù)雜度的排序技術(shù)在應(yīng)用遞增覆蓋排序算法的高效性。

4結(jié)語

本文通過對已有的基于方法覆蓋的排序技術(shù)進(jìn)行擴(kuò)展，主要從兩個方面研究了基于圈復(fù)雜度的測試用例排序方法：(1) 分析測試用例覆蓋方法的的圈復(fù)雜度、全覆蓋排序算法和遞增覆蓋排序算法。(2) 設(shè)計新的排序算法，將圈復(fù)雜度應(yīng)用于兩種排序算法中，以方法的圈復(fù)雜度取代方法覆蓋率作為測試用例的排序依據(jù)。通過實驗，驗證了基于圈復(fù)雜度的測試用例排序方法的有效性和高效性。本文的不足在于實際工業(yè)程序的錯誤分布不均衡，使用圈復(fù)雜度來評估程序代碼質(zhì)量存在一定的局限性，如何更精確地確定圈復(fù)雜度與排序技術(shù)之間的關(guān)系，在今后還需進(jìn)一步研究。

參考文獻(xiàn)

[1] Mei Hong,Hao Dan,Zhang Lingming,et al.A static approach to prioritizing junit test cases[J].IEEE Transactions on Software Engineering,2012,38(6):1258-1275.

[2] Srikanth H,Williams L.On the economics of requirements based test case prioritization[C]//Proceedings of the International WorkShop on Economics-driven Software Engineering Research,2005:1-3.

[3] Rotherme1 G,Untch R H,Chu C,et al.Prioritiz-ing test cases for regression testing[J].IEEE Transactions on Software Engineering,2001,27(10):929-948.

[4] 屈波,聶長海,徐寶文.基于測試用例設(shè)計信息的回歸測試優(yōu)先級算法[J].計算機(jī)學(xué)報,2008,31(3):431-439.

[5] 高建華,殷定媛.回歸測試中路徑覆蓋生成方法研究及其應(yīng)用[J].小型微型計算機(jī)系統(tǒng),2009,30(3):398-404.

[6] 肖自乾,王弗雄,陳經(jīng)優(yōu).基本路徑測試方法之圈復(fù)雜度計算[J].軟件導(dǎo)刊,2009,8(7):10-12.

[7] 司艷艷.通過軟件測試提高軟件可靠性研究[J].軟件導(dǎo)刊,2013,12(9):43-46.

[8] 楊廣華,包陽,李東紅,等.基于需求的測試用例優(yōu)先級排序[J].計算機(jī)工程與設(shè)計,2011,32(8):2724-2728.

[9] 李華瑩,胡兢玉.回歸測試用例優(yōu)先級排序技術(shù)研究[J].計算機(jī)仿真,2013,30(10):298-301.

STATIC TEST CASES SORTING METHOD BASED ON CYCLOMATIC COMPLEXITY

Chen MengyunGao Jianhua

(SchoolofInformationMechanicalandElectricalEngineering,ShanghaiNormalUniversity,Shanghai200234,China)

AbstractFor the problem of how to collocate test cases, in this paper we propose a cyclomatic complexity-based static test cases sorting method. We first introduce the cyclomatic complexity and the method coverage-based test cases sorting algorithm; and then we design two new sorting algorithms by applying the cyclomatic complexity to sorting algorithm; At last, through an experiment we test the validity of the improved approach in fault detection. Experimental result shows that compared with other existing priority techniques, this improved method is able to achieve higher fault detection efficiency and is conducive to improving test efficiency.

KeywordsTest cases sortingCyclomatic complexitySorting algorithmFault detection efficiency

中圖分類號TP311.5

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.01.001

收稿日期：2014-06-29。國家自然科學(xué)基金項目(61073163)；上海市引進(jìn)技術(shù)的吸收與創(chuàng)新年度計劃項目(12CH-19)；上海市企業(yè)自主創(chuàng)新專項資金項目(滬CXY-2013-88)。陳夢云，碩士生，主研領(lǐng)域：軟件可靠性理論與設(shè)計。高建華，博士。