錢忠勝,宋 濤

(江西財經(jīng)大學(xué) 信息管理學(xué)院,江西 南昌 3 30013)

軟件測試是為了發(fā)現(xiàn)程序錯誤,以提高程序質(zhì)量的一個過程[1,2].軟件測試貫穿軟件開發(fā)的整個過程,是軟件開發(fā)不可或缺的一個環(huán)節(jié).通常在軟件生命周期中,30%~40%的時間和精力花在軟件測試上[3].研究表明:在軟件測試中,毫無限制地對所有程序進行驗證,將會花費維護費用的50%[4,5].而軟件測試的重用在提高軟件測試質(zhì)量、縮短測試周期和改善測試人員的經(jīng)驗不足等方面,均起著十分重要的作用.目前,軟件測試重用的研究已成為軟件測試工程化研究的熱點之一[6].

軟件測試重用技術(shù)是指在新的軟件測試工作中重復(fù)使用已有的測試資源,其目的是充分利用之前軟件測試中的經(jīng)驗和成果,增強測試的效率和可靠性[7].測試用例的重用是指測試工程師在執(zhí)行回歸測試或者一項新的測試工作時,通過直接調(diào)用或修改已經(jīng)生成的測試用例,并將它們運用測試的過程,而不用每次面對新的測試工作都需要從頭開始設(shè)計測試用例.測試用例作為軟件測試的核心內(nèi)容,它的重用是整個軟件測試重用的關(guān)鍵環(huán)節(jié)[8].

測試用例重用的研究主要包含兩個方面:可重用測試用例的生成和可重用測試用例的管理[9].本文主要研究將程序已有測試用例使用到相似程序測試用例的生成過程中,故檢測待測程序之間的相似度是研究用例重用的前提.

程序代碼相似性的研究技術(shù)基本成熟,主要運用于計算機教學(xué)和軟件剽竊檢測等領(lǐng)域[10].最長公共子串和Levenshtein 距離等程序相似性度量算法重點考察源代碼之間的相似程度,而基于圖的結(jié)構(gòu)特征的相似性分析方法使用圖的結(jié)構(gòu)來反映程序功能特征的相似性分析方法[9].圖的結(jié)構(gòu)特征是較為高級的語法特征,主要包括控制流圖和數(shù)據(jù)流圖兩種:控制流圖反映了程序的邏輯結(jié)構(gòu),數(shù)據(jù)流圖反映了程序的數(shù)據(jù)流轉(zhuǎn)關(guān)系.

可見,程序相似性的判定可以從序列和圖等不同的特征進行.本文研究程序間相似性的目的是研究相似程序間測試用例重用的方法,以此提高測試用例的生成效率,減少軟件測試的工作量.主要做了以下工作.

1)對于待比較相似性的程序,構(gòu)建它們的關(guān)鍵字流圖.比較流圖節(jié)點中的關(guān)鍵字是否相同,具有相同關(guān)鍵字的節(jié)點構(gòu)成公共關(guān)鍵字流圖子圖;

2)程序的關(guān)鍵字流圖和關(guān)鍵字流圖最大公共子圖構(gòu)建完成后,利用最大公共子圖距離方法比較待測程序的相似程度,相似程度較高的程序可用于測試用例的重用;

3)測試用例的重用是將程序已有的測試用例共享于相似程序.采用遺傳算法來完成測試用例的重用,將相似程序已經(jīng)生成的測試用例引用到種群進化的過程中,種群的其他個體通過向這些測試用例學(xué)習(xí)加快進化速度,完成測試用例的重用.

本文第1 節(jié)分析程序相似性及測試用例重用的相關(guān)工作.第2 節(jié)研究相似程序的判定,主要涉及關(guān)鍵字流圖構(gòu)建方法、關(guān)鍵字流圖最大公共子圖的查找以及根據(jù)最大公共子圖距離求得待測程序的相似度.第3 節(jié)提出相似程序間測試用例重用的方法,并闡明將遺傳算法用于測試用例重用的原因;實驗多方面將本文方法與傳統(tǒng)方法在測試用例生成中的效率進行對比,根據(jù)實驗結(jié)果給出本文存在的不足以及有效性分析.第4 節(jié)總結(jié)全文,并提出下一步的研究工作.

1 相關(guān)工作

程序相似性的制定標(biāo)準是一項重要工作,近年來,不少學(xué)者從語義結(jié)構(gòu)和圖等不同方面探究程序的相似性.

Kwon 等人[11]利用子圖作為檢測惡意程序的特征,因為同一個惡意程序家族中的程序會共享子圖.子圖的查找則需要程序樣本中抽取API 調(diào)用建立分層級行為依賴圖,用它們尋找子圖.Wang 等人[12]提出了使用控制流圖和數(shù)據(jù)流圖特征對二進制程序進行相似性比較和同源分析的方法,實驗對象采用微軟不同版本的動態(tài)鏈接庫驗證算法的有效性.該算法比較適用于同一公司發(fā)布的同源良性程序相似度的比較.

1965年,Levenshtein[13]提出Levenshtein 距離算法,該算法常用于字符串的比較,計算兩個字符串差異的大小.源字符串通過添加、修改、刪除等操作變化到目標(biāo)字符串,其最少的改變次數(shù)看作是 Levenshtein 距離.Levenshtein 距離越小,字符串的相似度越大.Wang 等人[14]提出兩種基于雙向比較的最長公共子串算法,該算法將動態(tài)規(guī)劃算法(LCSstrDP)與后綴數(shù)組算法(LCSstrSA)相結(jié)合,有效地解決了動態(tài)規(guī)劃算法計算速度較慢的問題,卻增加了算法的復(fù)雜度,計算效率不高.Rong 等人[15]為了解決程序需要從兩個給定集合中找到所有類似的字符串對的問題,提出一種在單個操作符中支持不同相似閾值的字符串相似性連接的方法,就判定程序相似性閾值的設(shè)定,設(shè)計了新的索引技術(shù),針對不同的程序設(shè)計了不同判定程序相似的閾值,使得判定程序相似性更加準確,但復(fù)雜度較高.

Mc.Cabe[16]提出了圈復(fù)雜度的結(jié)構(gòu)度量技術(shù),該技術(shù)在流圖基礎(chǔ)上計算它的圈度,很多時候需要與其他特征結(jié)合進行程序結(jié)構(gòu)的度量.陳浩與王廣南等人[10]提出了基于程序依賴圖的動態(tài)胎記技術(shù)來檢測程序的相似性,該方法首先對流圖的公共子圖進行胎記標(biāo)記,通過比較最大公共子圖距離來判斷程序相似性.這兼顧了局部特征和整體特征,但公共子圖同構(gòu)判定的局限性比較大.

分析程序相似性的目的是為了探究相似程序間測試用例重用的有效性,而測試用例的生成是用例重用的前提,只有保存足夠的已生成的測試用例,才能完成它們的重用.近年來,國內(nèi)外開展了許多關(guān)于重用測試用例和測試用例的生成等方面的研究工作.

Mayrhauser 等人[17]通過領(lǐng)域建模來構(gòu)造可重用的測試用例,其構(gòu)造包括腳本化、命令模版和參數(shù)值選擇這3 個部分,并開發(fā)出基于領(lǐng)域建模的測試用例生成工具Sleuth.Vouffo-Feudjio 等人[18]提出了基于TTCN 的測試模式,并探討了該模式的重用規(guī)則,包括怎樣在不同產(chǎn)品之間的水平重用和不同版本之間的縱向重用.

鞏敦衛(wèi)等人[19]就提高回歸測試中測試數(shù)據(jù)的生成效率,提出一種新的回歸測試數(shù)據(jù)進化生成方法.該方法利用已有的測試數(shù)據(jù)穿越路徑與目標(biāo)路徑的相似程度,選擇相似程度較高的測試數(shù)據(jù)作為初始化種群的部分個體.進一步,根據(jù)已有測試數(shù)據(jù)穿越路徑與目標(biāo)路徑的對比,確定個體實施遺傳操作的位置.姜淑娟等人[20]提出了基于模式組合的粒子群優(yōu)化測試用例生成方法,通過新設(shè)定的交叉算子,將個體中的含有模式的部分組合成新個體,利用遺傳算法生成測試用例的過程中,種群中其他個體均可向該適應(yīng)度較高的新個體進行學(xué)習(xí),加快種群進化速度,提高測試用例生成效率.

將程序的相似性應(yīng)用在計算機教學(xué)和惡性程序檢測等領(lǐng)域的研究比較多:最長公共子串算法[14]比較字符串的相似性,字符串的相似性完全取決于最長字符串的長度,具有片面性;Levenshtein 距離算法[13]比較適用于規(guī)模較小的程序相似性的比較;基于程序依賴圖的動態(tài)胎記技術(shù)[10]來檢測程序的相似性,需要公共子圖的同構(gòu)作為前提條件,局限性比較大.

在前人研究的基礎(chǔ)上,本文提出面向關(guān)鍵字流圖程序相似度的方法.該方法兼顧了源代碼序列和程序功能結(jié)構(gòu)相似度的比較兩個方面.另外,借鑒鞏敦衛(wèi)和姜淑娟等人[19,20]的思想,提出了相似程序間測試數(shù)據(jù)的重用方法,通過相似程序間測試用例的共享實現(xiàn)用例重用.即:待測程序利用遺傳算法生成測試用例,在種群進化階段引入相似程序中已經(jīng)生成的測試數(shù)據(jù);在迭代過程,以一定概率向這些個體學(xué)習(xí).與傳統(tǒng)遺傳算法種群個體之間相互學(xué)習(xí)的進化方式作對比,測試用例生成效率較高,證明了測試用例重用的有效性,而相似程序間測試用例重用的效果證明了判斷相似程序方法的可行性.

2 程序相似性的判定

本文對程序相似性的判定結(jié)果應(yīng)用到相似程序間的測試用例重用中,故程序相似度的判定不僅注重語義上的相似性,更加注重程序功能結(jié)構(gòu)上的異同.本節(jié)提出關(guān)鍵字流圖的構(gòu)建方法,通過構(gòu)建的關(guān)鍵字流圖查找待測程序的關(guān)鍵字流圖最大公共子圖.最后,通過最大公共子圖距離算法求得程序的相似度,程序相似性的比較如圖1所示.本節(jié)給出判定程序相似性的步驟以及與程序相似性判定相關(guān)的定義.程序相似性判定的流程如下.

1)判斷待測程序能否實現(xiàn)測試用例的重用:首先觀察測試程序所輸入的參數(shù)是否受到個數(shù)限制,如果測試待測程序時輸入的參數(shù)數(shù)量都是一定的,而且它們所限定的數(shù)量是不同的,意味著它們的測試用例無法直接共享,本文不作比較;

2)關(guān)鍵字流圖最大公共子圖的構(gòu)建:若待測程序之間能夠?qū)崿F(xiàn)測試用例的重用,則構(gòu)建關(guān)鍵字流圖,利用動態(tài)規(guī)劃算法比較關(guān)鍵字流圖中關(guān)鍵字的異同.若關(guān)鍵字相同,則該關(guān)鍵字所屬的節(jié)點即屬于公共流圖子圖,并對此節(jié)點進行標(biāo)記,以此構(gòu)建待測程序的關(guān)鍵字流圖最大公共子圖;

3)相似度的判定:使用最大公共子圖距離算法計算關(guān)鍵字流圖子圖距離,該距離的大小決定了程序的相似程度.

Fig.1 Determining program similarity圖1 程序相似性的判定

2.1 相關(guān)定義

定義1(關(guān)鍵字).作為代碼核心的標(biāo)識符,用于表示一種數(shù)據(jù)類型或程序結(jié)構(gòu).像Java 和C 語言等編輯語言都有自定義的關(guān)鍵字.本文選擇Java 代碼編寫的程序作為實驗對象,表1 列出了Java 語言中的關(guān)鍵字.

Table 1 Key words of Java language表1 Java 語言的關(guān)鍵字

定義2(關(guān)鍵字流圖).關(guān)鍵字流圖(keyword f low g raph,簡稱KFG)是一個五元組(V,E,keyword,entry,exit),其中:V表示節(jié)點集,源程序的每個基本語句塊都對應(yīng)流圖的相應(yīng)節(jié)點;E是邊集,表示語句的流向;keyword表示關(guān)鍵字集,存儲著節(jié)點中的關(guān)鍵字,若源代碼中無關(guān)鍵字,該節(jié)點儲存字符null;entry 和exit 分別表示程序唯一的入口節(jié)點和出口節(jié)點.

定義3(關(guān)鍵字流圖公共子圖).節(jié)點集V中的每個節(jié)點均是關(guān)鍵字流圖G1中的節(jié)點,同樣又是關(guān)鍵字流圖G2中的節(jié)點,那么節(jié)點集V在流圖上構(gòu)成的圖即為流圖G1和G2的公共子圖.若存在節(jié)點集G,且G1和G2不存在其他的子圖的節(jié)點數(shù)大于G,那么G是G1和G2的一個最大公共子圖[8].

定義4(前綴與后綴)[14].前綴Pref[S,i](1≤i≤L),指從字符串S的第1 個字符開始至字符串的某個位置i結(jié)束的特殊子串,可記為S[1,i];后綴Suffix[S,i](1≤i≤L),指從字符串S的位置i開始至整個串末尾的一個特殊子串,可記為S[i,L].

根據(jù)定義4,公共前綴(后綴)表示一個字符串既是字符串S的前綴(后綴),又是字符串T的前綴(后綴),那么該字符串是字符串S和T的公共前綴(后綴).

定義5(最大公共子圖距離).給定兩個非空圖G1和G2,以及它們的最大公共子圖mcs(G1,G2),它們之間的距離[21,22]可表示為

其中,|G1|和|G2|分別表示G1,G2的節(jié)點數(shù),mcs(G1,G2)表示最大公共子圖的節(jié)點數(shù).那么圖G1與G2的相似度可以定義為

定義6(組間變異和組內(nèi)變異).在統(tǒng)計學(xué)中,組間變異表示數(shù)據(jù)的各組平均數(shù)與總平均數(shù)之間的離均差平方和,記為SSTR;而組內(nèi)變異表示每組數(shù)據(jù)中的每個測量值Xij與該組平均數(shù)之間的離均差平方和,記為SSe.它們的公式分別表示為

其中,ni為第i組的組內(nèi)數(shù)據(jù)個數(shù),k為組數(shù).

定義7(方差分析).在統(tǒng)計學(xué)中,方差分析(analysis of variance,簡稱ANOVA)是用于兩個及兩個以上樣本均數(shù)差別的顯著性檢驗,又稱為“變異數(shù)分析”或“F檢驗”.F值為組間均方MSTR與組內(nèi)均方MSe的比值,表示為

F=MSTR/MSe(4)

其中,MSTR=SSTR/k?1,MSe=SSe/N?k.這里,N為各組數(shù)據(jù)個數(shù)的和,k為組數(shù).

2.2 關(guān)鍵字流圖的構(gòu)建

關(guān)鍵字是代碼核心的標(biāo)識符,能夠代表代碼的結(jié)構(gòu)或者數(shù)據(jù)類型.某些代碼中的關(guān)鍵字相同,意味著它們的代碼結(jié)構(gòu)相同.源代碼中,每行代碼或者功能相近的若干行代碼為一個基本塊,每一個基本塊構(gòu)成一個節(jié)點.關(guān)鍵字流圖的節(jié)點中存儲了形成該節(jié)點基本塊中的關(guān)鍵字,若基本塊中無關(guān)鍵字,此節(jié)點存儲字符串null;若該行代碼存在兩個及以上的關(guān)鍵字,記錄第1 個關(guān)鍵字即可.構(gòu)建關(guān)鍵字流圖的步驟類似于控制流圖的構(gòu)造過程,已有很多研究,本節(jié)不再做具體說明.下面是冒泡排序的關(guān)鍵字流圖構(gòu)造示例.

圖2 中,圖2(b)是圖2(a)冒泡排序源碼所對應(yīng)的關(guān)鍵字流圖.可以看出,關(guān)鍵字流圖節(jié)點中存儲了形成該節(jié)點的關(guān)鍵字.例如:生成第2 個節(jié)點的基本塊中含有關(guān)鍵字int,該基本塊在生成關(guān)鍵字流圖過程中將該關(guān)鍵字儲存在相應(yīng)的節(jié)點上.待測程序的關(guān)鍵字流圖構(gòu)建完成,接下來比較待測程序關(guān)鍵字流圖中關(guān)鍵字的異同,構(gòu)建待測程序的關(guān)鍵字流圖最大公共子圖.圖3~圖5 分別給出了冒泡排序的控制流圖、程序流程圖和數(shù)據(jù)流圖等幾種比較常用的軟件結(jié)構(gòu)圖與關(guān)鍵字流圖的比較.通過對比發(fā)現(xiàn):

?關(guān)鍵字流圖比較程序相似性,注重程序的結(jié)構(gòu)和功能上的異同,符合功能結(jié)構(gòu)相同的程序,其測試用例會以更大概率共享的理念;

?控制流圖能表達程序的結(jié)構(gòu),但不能展示圖中每個節(jié)點的功能;

?程序流程圖能清晰地表達程序的流程及功能,但存在許多相似節(jié)點合并的現(xiàn)象;此外,用自然語言總結(jié)節(jié)點功能存在一定的主觀性,會因個人用語不同而存在文字上差別較大的情況;

?數(shù)據(jù)流圖比較詳細地闡述了程序主體及功能,也因此使其更加復(fù)雜,在比較程序相似性方面存在與程序流程圖相同的缺點.

Fig.2 Bubble sorting program and its keyword flow graph圖2 冒泡排序程序示例及其關(guān)鍵字流圖

Fig.3 Control flow graph and keyword flow graph of bubble sorting program圖3 冒泡排序的控制流圖及其關(guān)鍵字流圖

Fig.4 Program flow chart and keyword flow graph of bubble sorting program圖4 冒泡排序的程序流程圖及其關(guān)鍵字流圖

Fig.5 Data flow diagram and keyword flow graph of bubble sorting program圖5 冒泡排序的數(shù)據(jù)流圖及其關(guān)鍵字流圖

2.3 關(guān)鍵字流圖最大公共子圖的生成

待測程序根據(jù)第2.2 節(jié)關(guān)鍵字流圖的構(gòu)造方法生成關(guān)鍵字流圖,在關(guān)鍵字流圖的基礎(chǔ)上尋求它們的最大公共子圖,最大公共子圖的大小關(guān)系到待測程序的相似程度.動態(tài)規(guī)劃算法[14]尋找公共子字符串是解決公共子字符串的經(jīng)典算法之一,該算法能得到全局最優(yōu)解.本節(jié)利用該方法求得相似程序的關(guān)鍵字流圖最大公共子圖.

在利用動態(tài)規(guī)劃算法求解兩個長度分別為p,q的字符串S,T的最長公共子串的問題之前,先給出求它們?nèi)我馇熬Y子串對S[1,i],T[1,j]的最長公共后綴的算法.該問題的遞推關(guān)系如公式(5):

其中,LCSuffix(S[1,i],T[1,j])表示前綴子串對S[1,i],T[1,j]的最長公共后綴.

在字符串S和T所有前綴子串對的最長公共后綴中,長度最大的即為字符串S和T的最長公共子串,即:

其中,LCS(S,T)表示字符串S和T的最長公共子串.

關(guān)鍵字流圖節(jié)點中的關(guān)鍵字可以看作由這些關(guān)鍵字組成的字符串中的一個字符,關(guān)鍵字流圖節(jié)點中的關(guān)鍵字構(gòu)成字符串,利用動態(tài)規(guī)劃算法生成關(guān)鍵字流圖最大公共子圖,步驟如下.

1)利用公式(5)和公式(6)求得最長公共子串;

2)null 字符代替兩個關(guān)鍵字字符串中的最長公共子串.在進行關(guān)鍵字比較時遇到同為null 時,需要考慮null 所在節(jié)點邊的情況,若來源于相同的關(guān)鍵字而且又指向相同的關(guān)鍵字,則將該節(jié)點計入最大公共子圖中;

3)判斷最長公共子串的長度是否大于0:若長度大于0,重復(fù)步驟1)和步驟2);否則,結(jié)束.

例如,字符串S=“public,int,if,null,for,if,null”,T=“public,int,for,for,if,null”,使用遞推關(guān)系(見公式(5)和公式(6))求得字符串S和T所有前綴子串對的最長公共后綴,見表2.

字符串S為快速排序程序關(guān)鍵字流圖的節(jié)點中關(guān)鍵字的組合,T字符串則代表了冒泡排序程序關(guān)鍵字流圖中關(guān)鍵字的組合.從表2 中可以看出:字符串S和T的公共子串為“for,if”和“public,int”,字符串S和T的最大公共子串為“public,int,for,if”.字符串S和T分別為快速排序和冒泡排序關(guān)鍵字流圖節(jié)點存儲信息組合而成.根據(jù)字符串S和T的最大公共子串構(gòu)建關(guān)鍵字流圖最大公共子圖.

Table 2 Finding common keywords using dynamic programming algorithm表2 動態(tài)規(guī)劃法查找公共關(guān)鍵字

圖6 是冒泡排序和快速排序關(guān)鍵字流圖的最大公共子圖(灰色部分).灰色部分節(jié)點存儲了字符串S和T公共子串中的關(guān)鍵字,關(guān)鍵字流圖的最大正是由S和T公共子串的關(guān)鍵字所在的節(jié)點構(gòu)成.

Fig.6 Maximum common sub-graph of keyword flow graph(in gray)圖6 關(guān)鍵字流圖的最大公共子圖(灰色部分)

2.4 程序相似性的判定

待測程序快速排序與冒泡排序的關(guān)鍵字流圖最大公共子圖已經(jīng)生成,本節(jié)利用最大公共子圖距離算法(見定義5)計算程序相似程度.最大公共子圖距離公式(公式(1))中,|G1|和|G2|分別表示程序快速排序和冒泡排序的節(jié)點數(shù),mcs|G1,G2|表示最大公共子圖的節(jié)點數(shù).由圖6 知:冒泡排序與快速排序存儲關(guān)鍵字的節(jié)點都為5,關(guān)鍵字流圖最大公共子圖的節(jié)點為4,故max(|G1|,|G2|)=5,mcs|G1,G2|=4,將具體數(shù)值帶入公式,可得最大公共子圖距離D(G1,G2)=0.2.公式(2)將程序相似度定義為1?D(G1,G2),已知冒泡排序和快速排序的最大公共子圖距離0.2,故兩程序的相似度S(G1,G2)=(1?D(G1,G2))×100%=80%.

基于關(guān)鍵字流圖判定程序相似度的偽代碼見算法1.

算法1.程序相似度的判定.

輸入:待測程序program1,program2;

輸出:待測程序相似度similarity.

本節(jié)采用自適應(yīng)的方法進行實驗來選取程序是否相似的閾值[23],實驗對象為已知功能相近的程序或者不相近的程序,實驗方法為本節(jié)所提的程序相似性檢測方法.表3 和表4 分別給出了本文方法驗證部分基礎(chǔ)程序及系統(tǒng)中常用功能程序的相似性實驗結(jié)果.

Table 3 Testing of the similarity between basic programs(%)表3 基礎(chǔ)程序間相似性的檢測(%)

Table 4 Testing of similarity between commonly-used programs in the system(%)表4 系統(tǒng)常用功能程序間相似性的檢測(%)

表3 考察了多個查找算法和排序算法兩種不同功能的程序.從表中實驗的數(shù)據(jù)可以看出:功能相近程序的相似性皆超過70%;而不同功能的程序即使程序規(guī)模相近,其相似度也在70%以下.本文將70%設(shè)定為程序是否相似的閾值.

表4 中選用系統(tǒng)中常用的功能程序考察其相似度.用戶登錄a與用戶登錄b是兩種不同腳本的登錄算法,登錄驗證為用戶登錄時后臺的驗證算法.用戶登錄、身份驗證、數(shù)據(jù)處理和信息下載為同一系統(tǒng)下不同功能的算法.表4 中的實驗結(jié)果再次驗證了功能相同的程序間相似性較高,而功能不同的不相似程序的相似度均在70%以下,證明本文將判定程序是否相似的閾值設(shè)定在70%的合理性(在判定規(guī)模較小的程序時存在一定的偶然性,應(yīng)將特例排除).

2.5 用關(guān)鍵字流圖比較程序相似性的優(yōu)勢

公共關(guān)鍵字流圖子圖比較程序相似性具有以下優(yōu)勢.

1)將程序轉(zhuǎn)化成關(guān)鍵字流圖,關(guān)鍵字是代碼的核心標(biāo)識符,關(guān)鍵字相同的節(jié)點意味著生成該節(jié)點的代碼語句結(jié)構(gòu)相同.通過比較關(guān)鍵字流圖來判定程序的相似性,解決了兩個程序功能相同但源代碼差異較大的問題;

2)本文是在關(guān)鍵字流圖最大公共子圖的基礎(chǔ)上比較程序的相似度.相對于最長公共子串比較相似性,公共關(guān)鍵字流圖子圖更大程度比較了兩個程序,避免了最長公共子串比較程序只取決于最長公共子串大小片面性的問題;

3)關(guān)鍵字流圖的節(jié)點代表程序中的基本塊,用關(guān)鍵字流圖比較程序的相似性比較方便.而不在源代碼上直接比較關(guān)鍵字是否相似,因為從源代碼上比較關(guān)鍵字是以行代碼為單位,容易造成程序代碼的書寫格式不同帶來的誤差.

例如,圖7 為冒泡排序另一種編寫方式的部分代碼,由于編程習(xí)慣不同,有些程序員會把第2 行~第4 行代碼寫成“intt,i,j;”,兩種書寫方式功能完全相同.第2 行~第4 行代碼的作用是定義整型變量,屬于一個基本塊,會生成關(guān)鍵字流圖的一個節(jié)點.而基于源代碼進行關(guān)鍵字比較時,則會因為不同的書寫格式造成不同的結(jié)果.

Fig.7 Partial source code of bubble sorting program圖7 冒泡排序部分源代碼

2.6 程序相似性檢驗插件的原型

插件服務(wù)于軟件項目主體,有效地擴展和完善了寄主軟件的功能[24].基于本文第2.2 節(jié)~第2.4 節(jié)程序相似度比較的方法,開發(fā)了一個檢測程序相似程度的插件,如圖8所示.此插件的制作,方便了程序相似性的比較.下一節(jié)探究相似程序間測試用例重用的問題,其前期工作就是需要判斷程序之間的相似程度,此插件將減少了判斷程序相似性的工作.

插件的開發(fā)選用Java 作為編輯語言,開發(fā)環(huán)境為MyEclipse 20 10.計算機配置為Windows(Intel(R)C ore(TM)CPU i5-6500,3.20GHz,8.00GB RAM,64 位操作系統(tǒng).圖8 為檢測程序相似程度的插件運行界面.

Fig.8 Plug-in for detecting program similarity圖8 檢測程序相似性的插件

按鈕“Select pr ogram 1”和按鈕“Select pr ogram 2”是兩個選擇待測程序的按鈕,測試程序的相似度時,分別點擊這兩個按鈕選擇待測程序所在的文件,實驗選擇的待測程序為冒泡排序與快速排序.點擊“Testing”按鈕,將以百分數(shù)的形式顯示兩個待測程序的相似度.

通過檢測,冒泡排序與快速排序的相似度為80%,大于設(shè)定的閾值,可以判定冒泡排序和快速排序為相似程序,并被設(shè)定為下一節(jié)研究相似程序間測試用例重用選擇的實驗對象.

3 基于遺傳算法的相似程序間測試用例的重用

本節(jié)利用遺傳算法完成測試用例的生成,實現(xiàn)測試用例的重用.遺傳算法作為一種基于自然選擇原理和自然遺傳機制的通用搜索算法[25,26],通過進化過程獲得的信息自行組織搜索,適應(yīng)度大的個體具有較高的生存概率,并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu).在進化的遺傳操作中,適應(yīng)度較高的個體以更大概率將更優(yōu)秀的基因遺傳給下一代.

遺傳算法具有良好的可擴展性,容易與其他算法相結(jié)合,也可以調(diào)節(jié)遺傳操作和適應(yīng)度函數(shù)等方式提升算法的效率.本節(jié)在種群進化過程上引入適應(yīng)度較高的個體來提高測試用例生成的效率.其基本思路(重用模型如圖9所示)如下.

1)假設(shè)一個程序適應(yīng)度較高的測試用例已經(jīng)生成,將這些測試用例應(yīng)用到其相似程序的測試中.實驗采用遺傳算法來完成測試用例的重用;

2)利用遺傳算法測試待測程序時,將重用的測試用例引用到遺傳操作的種群進化中,種群的其他個體通過向這些測試用例學(xué)習(xí),目的是加快種群進化速度,提高測試用例的生成效率.

Fig.9 Reuse model of test cases for similar programs圖9 相似程序間測試用例重用模型

3.1 適應(yīng)度函數(shù)

遺傳算法具有種群初始化、個體評價、選擇運算、交叉運算、變異運算、進化終止條件判斷等步驟.遺傳算法的初始種群通常采用隨機的方式生成,個體評價通過相應(yīng)的適應(yīng)度函數(shù)計算種群中各個個體的適應(yīng)度值,選擇運算就是將適應(yīng)度較高的個體進行交叉變異操作,產(chǎn)生的個體組成下一代種群.重復(fù)選擇進化的過程,直至終止條件滿足,算法結(jié)束.

適應(yīng)度函數(shù)是衡量種群個體優(yōu)劣的標(biāo)準[27],根據(jù)優(yōu)勝劣汰的生存法則,通過淘汰生存能力低的個體實現(xiàn)種群的選擇、進化.因此,適應(yīng)度函數(shù)決定了種群的進化速度.合理的適應(yīng)度函數(shù)能夠全面提高種群個體的質(zhì)量,有利于快速進化至最優(yōu)解.適應(yīng)度函數(shù)的設(shè)置是算法操作重要的一環(huán).

分支距離法[28]和層接近度法[24]是兩個設(shè)置個體適應(yīng)度的經(jīng)典方法.為了便于與主要參考文獻作比較,實驗選用了相同的函數(shù)(即分支距離法)設(shè)置個體的適應(yīng)度.在程序的每個分支節(jié)點都插樁分支函數(shù)fi(插樁方式見圖10),記錄當(dāng)前的測試用例與該分支的距離.當(dāng)某分支被覆蓋時,則將fi設(shè)為0,若該目標(biāo)路徑共含有m個分支節(jié)點,其總的適應(yīng)度函數(shù)值FT的計算見公式(7):

由適應(yīng)函數(shù)的計算公式可以推算出,測試用例的適應(yīng)度跟分支節(jié)點覆蓋率成正比例關(guān)系.特別地,當(dāng)程序的每個分支節(jié)點均被覆蓋時,該測試用例的適應(yīng)度為1.

例如,對于數(shù)組inta[?]={3,4,2}的測試用例測試冒泡排序,參考圖10 冒泡排序插樁后的偽代碼.由于a[0]a[2],該條件語句滿足,此時f4=0.則該測試用例與各個分支的距離為{0,0,1,0,0,0,0},此用例下分支節(jié)點個數(shù)m=7,將數(shù)據(jù)帶入適應(yīng)度函數(shù)計算公式得FT≈0.87.

Fig.10 Pseudo-code of bubble sorting program after being instrumented圖10 冒泡排序插樁后的偽代碼

3.2 測試用例生成算法

測試用例生成算法采用Java 語言編寫,并在MyEclipse 2 010 中運行.計算機配置為Windows(Intel(R)Co re(TM)CPU i5-6500,3.20GHz,8.00GB RAM,64 位操作系統(tǒng).算法的具體流程見算法2(傳統(tǒng)方法).

算法2(傳統(tǒng)方法).

輸入:種群大小pop_size,個體individual,染色體長度chro_size,進化代數(shù)gen_size,交叉概率pc,變異概率pm;

輸出:新種群.

算法2 是利用傳統(tǒng)方法生成測試用例的遺傳算法,采用隨機方式初始化種群,輪盤賭法選擇個體,以一定概率進行交叉與變異等操作,生成新的種群;判斷新種群中是否有個體滿足目標(biāo)路徑被覆蓋,若其被覆蓋,記錄種群的進化代數(shù);判斷是否滿足算法的終止條件,即種群是否達到最大進化代數(shù),若滿足則終止算法,若不滿足則循環(huán)種群進化的過程.

算法3 將測試用例重用到待測程序的測試數(shù)據(jù)生成中,并作為對比實驗檢驗測試用例的重用效果.該算法的初始種群采用算法2 中的初始種群,以避免初始種群不同對實驗結(jié)果造成的影響.在種群交叉進化的遺傳操作過程中,算法3 引入相似程序的測試用例作為個體交叉的對象,其他步驟與算法2 一致.

算法3(本文方法).

輸入:種群大小pop_size,個體individual,染色體長度chro_size,進化代數(shù)gen_size,交叉概率pc,變異概率pm,引入的新個體shared_pop;

輸出:新種群.

3.3 測試用例生成實驗

選取第3 節(jié)討論的兩個相似程序(即冒泡排序和快速排序)為實驗對象,提出兩個問題探究本文判斷程序相似性方法的合理性以及相似程序間測試用例重用的有效性,收集實驗結(jié)果加以分析.具體問題如下:

問題1.本文設(shè)計的關(guān)鍵字流圖比較程序相似性,相對于其他方法比較程序相似性有什么優(yōu)點?如何檢驗方法的有效性?

最長公共子串等方法只比較代碼的相同程度,而忽略了源代碼略有差別、但功能結(jié)構(gòu)卻相同的情況.提出利用關(guān)鍵字流圖比較程序的相似性,將比較全部源代碼簡化為比較代表代碼語句功能結(jié)構(gòu)的關(guān)鍵字.

最大公共子圖距離能夠判斷待測程序的相似程度.而通過遺傳算法將程序已有的測試用例應(yīng)用到相似程序的種群進化的遺傳操作中,檢驗測試用例的生成效率來判斷程序相似性判斷的有效性.即:通過用例的共享,待測程序的測試效率明顯提高,可證明兩個程序相似性判斷是正確的.

問題2.相似程序之間用例的共享能夠減少多少測試工作量,提高多少測試效率?

檢測關(guān)鍵字流圖判別程序有效性的實驗,也能完成用例的重用.我們結(jié)合姜淑娟等人[20]的思想,在初始化種群的環(huán)節(jié)中引入相似程序中已有的測試數(shù)據(jù),種群其他的個體通過向這些測試用例的學(xué)習(xí)加速種群進化,主要通過4 個評判標(biāo)準來檢驗測試效率.評判標(biāo)準見第3.3.2 節(jié).

我們采用對比實驗來解答上面兩個問題.實驗的不同點主要在于種群進化的方式不同.

?傳統(tǒng)方法測試程序,初始種群隨機生成,在初始種群中用輪盤賭法選擇兩個體進行遺傳操作,輪盤賭法選中的兩個個體以一定概率進行變異:若滿足交叉條件,則兩個個體進行交叉,進化成兩個新個體.循環(huán)此操作,直到產(chǎn)生的新種群個體數(shù)與初始種群相同;

?而利用本文方法測試程序,初始種群使用傳統(tǒng)方法生成的種群,以排除初始種群不同對實驗結(jié)果造成的影響.引入相似程序已經(jīng)生成的測試用例集,在種群進化的交叉部分,仍用輪盤賭法選擇的個體與該用例集中的個體交叉,生成兩個新的個體.其他操作與傳統(tǒng)方法相同.

3.3.1 實驗對象

第2 節(jié)表明:冒泡排序和快速排序兩個程序的相似度為80%,判定為相似程序.實驗對象仍選取此相似程序來探究相似程序間測試用例的重用問題.

實驗假設(shè)快速排序的適應(yīng)度較高的測試用例已知.研究測試用例的重用就是將已知的測試用例共享于與其相似的程序,故測試冒泡排序程序時,將引入快速排序已有的測試用例.測試用例有32 個二進制的字符,其中,4 個二進制字符代表一個十進制的阿拉伯?dāng)?shù)字,意味著每個測試用例代表著長度為8 的整數(shù)數(shù)組,整數(shù)大小在0到15 之間.測試用例的生成采用遺傳算法,種群的個數(shù)為40.具體參數(shù)設(shè)置見表5.

Table 5 Para meters setting in genetic algorithms表5 遺傳算法中的參數(shù)設(shè)置

3.3.2 評價標(biāo)準

為了檢驗程序相似性檢測方法的有效性及相似程序間測試用例重用的效果,并便于與丁蕊等人[28]提出的關(guān)鍵點路徑法進行比較,同時也為了將遺傳算法中隨機因素對實驗結(jié)果造成的影響降低到最小,我們將實驗結(jié)果的4 個評價標(biāo)準(即覆蓋率、平均進化代數(shù)、執(zhí)行時間和方差分析)的定義如下.

1)覆蓋率:對程序運行100 次,記錄在最大進化代數(shù)T=1000 內(nèi)目標(biāo)路徑被覆蓋的總次數(shù),覆蓋率為這100次中被覆蓋次數(shù)的平均值,以百分比的形式表示;

2)平均進化代數(shù):目標(biāo)路徑被覆蓋的每個程序運行100 次,若該程序在最大進化代數(shù)T=1000 內(nèi)覆蓋到了目標(biāo)路徑,記錄此時程序的進化代數(shù);若在最大進化代數(shù)內(nèi)目標(biāo)路徑?jīng)]有被覆蓋,記錄最大進化代數(shù),平均進化代數(shù)即為這些記錄值的平均值;

3)執(zhí)行時間:該評價指標(biāo)記錄兩種方法(即傳統(tǒng)方法與本文方法)的時間開銷.傳統(tǒng)方法生成測試用例的執(zhí)行時間是測試數(shù)據(jù)或路徑的選擇與測試數(shù)據(jù)生成所消耗的時間總和;本文方法生成測試用例的時間除了測試數(shù)據(jù)或路徑的選擇與測試數(shù)據(jù)生成的時間以外,還包括判定程序相似性和測試用例重用花費的時間;

4)F值:在方差分析中,每個被測程序運行100 次,記錄目標(biāo)個體首次出現(xiàn)的進化代數(shù),將傳統(tǒng)方法與本文方法下獲得的該數(shù)據(jù)作為兩組樣本來計算F統(tǒng)計量,即組間均方與組內(nèi)均方的比值(見定義6 和定義7),該值能驗證隨機因素對實驗結(jié)果造成的影響程度.

傳統(tǒng)方法和本文方法均采用遺傳算法測試同一程序,上面4 種評價標(biāo)準作為衡量兩種方法測試效率優(yōu)劣的指標(biāo),檢驗本文方法是否能夠有效地提高測試用例的生成效率,完成測試用例的重用.

3.3.3 實驗結(jié)果分析

測試冒泡排序來驗證相似程序間測試用例重用的有效性,傳統(tǒng)方法中的測試種群通過輪盤賭法選擇個體進行交叉變異產(chǎn)生下一代,而作為對比實驗的本文方法在種群進化中將引入相似程序快速排序適應(yīng)度較高的測試用例.為了減少隨機因素的影響,兩種實驗均獨立運行100 次,本文方法采用的初始種群為冒泡排序隨機生成的初始種群.種群進化達到最大進化代數(shù)時算法終止,并記錄100 次實驗共有的總時間.

表6 表明:將快速排序適應(yīng)度較高的測試用例運用到冒泡排序的測試中,測試用例的生成效率明顯提高.其中:在傳統(tǒng)方法的100 次獨立實驗中,在種群最大進化代數(shù)前只有15 次能夠覆蓋目標(biāo)路徑,覆蓋率為15%,平均進化代數(shù)為890.9,所用的總時間為8.20s;采用本文方法的實驗中的目標(biāo)路徑覆蓋率為100%,平均進化代數(shù)為3.5,所用總時間為2.74s.其F值為160.36,經(jīng)查表,組數(shù)為2,每組數(shù)據(jù)量在100 時,F界值為3.04,本文方法與傳統(tǒng)方法的目標(biāo)個體的進化代數(shù)作為兩組數(shù)據(jù)所得F值遠遠大于F界值,意味著本文方法有效地改變了目標(biāo)個體的平均進化代數(shù),排除隨機因素對實驗造成的干擾.從實驗結(jié)果可知,目標(biāo)路徑覆蓋率、平均進化代數(shù)和時間3 個衡量指標(biāo)都能證明相似程序間測試用例重用效果明顯.

Table 6 Evaluation result of testing bubble sorting program using traditional method and our method表6 傳統(tǒng)方法和本文方法測試冒泡排序的評判結(jié)果

為更加全面檢測用例重用的效果,實驗將改變種群大小,檢驗種群大小是否對實驗結(jié)果造成較大影響.表7是不同種群大小下傳統(tǒng)方法和本文方法在冒泡排序中的測試結(jié)果.

Table 7 Test results of bubble sorting program under different population sizes表7 不同種群大小下冒泡排序的測試結(jié)果

表7 的實驗結(jié)果驗證了不同種群下對比實驗的覆蓋率和平均進化代數(shù).實驗結(jié)果顯示:隨著種群規(guī)模的增大,傳統(tǒng)方法中的目標(biāo)路徑的覆蓋率有增大的趨勢,平均進化代數(shù)隨之減少,F值變化很小,但仍遠大于F界值3.04.本文方法下的實驗結(jié)果表明:3 種種群大小下的目標(biāo)路徑覆蓋率都為100%,當(dāng)種群的個體數(shù)量增加時,平均進化代數(shù)隨之減少.該方法下的100 次獨立實驗中目標(biāo)路徑皆被覆蓋,平均進化代數(shù)遠低于傳統(tǒng)方法,測試效率比傳統(tǒng)方法明顯要高.表8 是不同變異概率下測試冒泡排序的結(jié)果.

Table 8 Test results of bubble sorting program under different mutation probabilities表8 不同變異概率下冒泡排序的測試結(jié)果

由表8 的實驗結(jié)果可知:變異概率的改變,給實驗結(jié)果帶來了很小的變化.變異概率由0.1 變化到0.3 時,冒泡排序中目標(biāo)路徑的覆蓋率提高了7%,平均進化代數(shù)減少3.7,F值仍遠大于F界值3.04.本文方法測試結(jié)果表明:在3 種變異概率下,其目標(biāo)路徑的覆蓋率皆為100%.對比兩個實驗的實驗結(jié)果可知:3 種變異概率下使用本文方法的測試效率遠遠高于傳統(tǒng)方法,相似程序檢測時用例重用效果較好.

表9 中的數(shù)據(jù)為本文方法和業(yè)界測試用例生成效率較高方法的各性能指標(biāo).為了檢測相似程序間測試用例的重用效果,排除其他因素造成干擾,本實驗遺傳算法的各種參數(shù)和關(guān)鍵點路徑法[20]中的參數(shù)保持一致,并且選擇相同的目標(biāo)路徑.通過比較平均迭代次數(shù)可看出,本文方法實驗中的種群能更早地覆蓋目標(biāo)路徑.

Table 9 Performance comparison between our method and the key-point path method表9 本文方法與關(guān)鍵點路徑法性能比較

3.4 進一步實驗

為了證明面向關(guān)鍵字流圖判斷程序的相似性,并將測試用例重用到相似程序測試用例的生成中的效果較好,實驗特別設(shè)計了基于控制流圖、程序流程圖及數(shù)據(jù)流圖的方法來判斷程序的相似性,并將相似度較高的程序作為實驗對象檢驗測試用例的重用效果,以便于與我們基于關(guān)鍵字流圖的方法作對比.實驗按照與關(guān)鍵字流圖相同的方法計算程序的相似性,例如:利用控制流圖計算程序相似度時,首先將待測程序生成控制流圖,接下來查找控制流圖的最大公共子圖.由于控制流圖的節(jié)點中沒有存儲關(guān)鍵字等信息,故而查找公共節(jié)點時,考察有向邊的數(shù)量與方向.若節(jié)點邊的來向、去向和數(shù)量完全相同,則該節(jié)點屬于公共子圖中的節(jié)點.最后使用最大公共子圖距離算法計算程序的相似度.詳細過程可參考第2 節(jié).表10 為待測程序的基本信息以及實驗結(jié)果.

Table 10 Basic information and experimental results of the program to be tested表10 待測程序的基本信息與實驗結(jié)果

表10 顯示了3 組待測程序的名稱、子函數(shù)個數(shù)、代碼行數(shù)以及基于關(guān)鍵字流圖、控制流圖、程序流程圖與數(shù)據(jù)流圖方法下的程序相似度.從數(shù)據(jù)中能夠看出:在3 組程序中,關(guān)鍵字流圖下的程序相似度都低于70%,而其他3 種流圖判定該程序的相似度時皆有較高的相似度(這樣就超過了相似度設(shè)定的閾值,把本來不相似的程序也判定成相似了).實驗結(jié)果顯示了待測程序測試用例重用的效果(特別注意:表中的3 個指標(biāo)值是根據(jù)控制流圖、程序流程圖以及數(shù)據(jù)流圖得到的結(jié)果,并且它們的測試過程一樣,因此數(shù)據(jù)一致).從表中的3 個評價指標(biāo)能夠看出:基于控制流圖、程序流程圖以及數(shù)據(jù)流圖判定待測程序的相似度得到較高的值,其測試用例的重用在一定程度上確實降低了目標(biāo)個體的平均進化代數(shù),并且提高了其覆蓋率,但均未達到100%.結(jié)合第3.3.3 節(jié)以及本文其他實驗的結(jié)果,基于關(guān)鍵字流圖相似程序間測試用例的重用的效果更好,其目標(biāo)個體的覆蓋率皆為100%,而目標(biāo)個體的平均進化代數(shù)也較為更低.

控制流圖、程序流程圖和數(shù)據(jù)流圖判定程序相似性時只比較了程序的結(jié)構(gòu)而沒有考察圖中節(jié)點的功能,而基于關(guān)鍵字流圖比較程序相似性時,綜合比較了程序的結(jié)構(gòu)與功能.因此,判定程序的相似度更準確,其測試用例具有更好的重用效果.

接下來,為了證明相似程序間測試數(shù)據(jù)是否可以相互引用,實驗將測試冒泡排序已經(jīng)生成的測試用例重用到快速排序的測試用例生成中.此外,進一步證明相似程序間測試用例重用的有效性.實驗另外選取了兩組典型基準程序和5 組工業(yè)程序作為實驗對象,分別將傳統(tǒng)算法和本文方法利用到這些程序的測試用例生成中.實驗對象的基本信息見表11.

Table 11 Basic information of experimental subjects表11 實驗對象的基本信息

第2 組基準程序的PG3 被廣泛應(yīng)用于驗不同測試數(shù)據(jù)生成方法的有效性[2],PG4 是測試兩個時間之間間隔多少天的函數(shù),測試該函數(shù)與PG3 函數(shù)輸入的參數(shù)類型皆為年月日的形式;PG5 函數(shù)驗證輸入的3 個數(shù)是否能組成三角形,PG6 函數(shù)在此基礎(chǔ)上驗證三角形是否是等腰或者等邊三角形;工業(yè)程序PG7 和PG8 摘選自Github網(wǎng)站不同作者編寫的實現(xiàn)計算器功能的程序;PG7 和PG8 實現(xiàn)的功能相同,但編寫方式和使用的函數(shù)存在不同,故將PG7 和PG8 作為實驗對象.

PG9 是五子棋游戲的贏棋算法,PG10 是在PG9 基礎(chǔ)上做了一定的刪減,去掉了悔棋功能.PG11 是通訊錄系統(tǒng)個人信息的校驗算法.PG12 增加了辦公室電話的校驗功能.本節(jié)對PG9 和PG11 兩個工業(yè)程序做了不同維護類型的修改,用來驗證本文方法是否適應(yīng)于回歸測試.回歸測試是確認修改程序是否引入新的錯誤或?qū)е缕渌a產(chǎn)生錯誤[29].

統(tǒng)計數(shù)據(jù)表明:回歸測試占了軟件測試總預(yù)算的80%,軟件維護階段總費用50%以上.盡管回歸測試的代價如此之高,但它卻是不可或缺的測試[30,31].回歸測試中有效地利用已經(jīng)生成的測試數(shù)據(jù),近幾年得到普遍的關(guān)注.程序PG13 和PG15 來源于SIR 測試平臺的西門子測試程序集[2],常作為程序測試的實驗對象.PG14 和PG16是采用不同方法對PG13 和PG15 更新后的程序.該組程序能夠驗證相似程序間測試用例的重用效果,還能夠驗證本文方法是否適合程序的回歸測試.

為了驗證不相似程序之間測試用例的重用效果,實驗還補充了3 組實驗(見表11 的最后3 組),將不相似程序PG7,PG9 和PG11 的適應(yīng)度較高的測試用例相互引用.對于程序功能規(guī)模差距較大的程序,其測試用例共用的可能性較小.其中,程序ABS_check1 的測試用例無法與程序Calculator1 和Gobang_algorithm1 的測試用例完成重用.而程序Calculator1 和Gobang_algorithm1 的測試用例規(guī)模相近,為了檢驗其重用效果,實驗將Gobang_algorithm1 的測試用例處理成與Calculator1 的測試用例長度一致.

新增實驗仍采用傳統(tǒng)算法和本文方法進行對比,傳統(tǒng)方法測試程序的各種參數(shù)設(shè)置與第3.3.1 節(jié)傳統(tǒng)方法測試冒泡排序的參數(shù)一致.本文方法利用遺傳算法生成測試用例的種群進化過程引用傳統(tǒng)方法生成的測試用例,引用的個數(shù)為10 個.實驗種群大小均為40 個,進化代數(shù)統(tǒng)一為1 000 代,詳細參數(shù)設(shè)置見表12.

Table 12 Population size and maximum evolution times表12 種群規(guī)模及最大進化代數(shù)

表13 為傳統(tǒng)遺傳算法和本文方法測試程序的執(zhí)行結(jié)果,可見,利用本文方法生成測試用例的效率更高.

Table 13 Results of testing under the traditional method and our method表13 傳統(tǒng)方法和本文方法下程序測試的結(jié)果

下面分別從4 個評價標(biāo)準對比測試用例的生成效率.

1)本文方法測試程序的目標(biāo)路徑覆蓋率為100%(注意,PG17 對應(yīng)的是不相似程序);而傳統(tǒng)方法測試程序其目標(biāo)路徑覆蓋率最高為91%,測試PG2 的路徑覆蓋率僅有30%;

2)平均迭代次數(shù)方面,本文方法測試程序的平均迭代次數(shù)均在40 代以內(nèi);傳統(tǒng)方法除測試PG3 的實驗以外,其他程序測試實驗的平均迭代次數(shù)均在130 代以上,甚至超過600 代;

3)用時方面,利用本文方法測試程序的執(zhí)行時間皆少于傳統(tǒng)方法;

4)F值的大小表明隨機因素對實驗的影響.實驗結(jié)果中的F值皆遠大于F界值,則說明排除了隨機因素對該實驗的影響,證明了本文方法的有效性.

實驗PG17 的結(jié)果表明:雖然不相似程序之間測試用例的重用在一定程度上提高了目標(biāo)個體的進化速度,但目標(biāo)路徑覆蓋率有所降低,還是不如相似程序間測試用例的重用效果.

由測試PG2 的實驗結(jié)果可知,本文方法有效地提高了測試用例的生成效率.可證明測試冒泡排序可以引用快速排序已經(jīng)生成的測試用例,測試快速排序也可以使用冒泡排序已經(jīng)生成的測試用例.即,相似程序之間測試用例是通用的.觀察PG9,PG12,PG13 以及PG15 的實驗結(jié)果,本文方法的前3 個評判標(biāo)準都優(yōu)于傳統(tǒng)方法,這說明本文方法運用到回歸測試是可行的.相似程序間測試用例的重用測試程序是將已經(jīng)生成的測試用例重用到相似程序測試用例的生成過程.在種群進化的過程中,種群個體不斷地向引入的優(yōu)秀個體學(xué)習(xí),實驗證明,本文方法能夠提高測試效率.本文方法的測試用例重用能夠取得這么好的結(jié)果,其主要原因包含兩個方面.

1)利用遺傳算法測試程序的過程中,引用了相似程序適應(yīng)度較高的測試用例,引入的測試用例可以看作是待測程序適應(yīng)度比較高的測試用例,甚至某些測試用例作為目標(biāo)個體參與了種群的進化,因此在種群迭代1 000 次的情況下,種群進化出目標(biāo)個體(覆蓋率100%)是大概率事件;

2)容易陷入局部最優(yōu)是遺傳算法的弊端之一,實驗發(fā)現(xiàn):當(dāng)種群進化到一定代數(shù)之后,種群基因種類較少,許多個體的基因相同或者非常相近,很大程度上阻礙了目標(biāo)個體的生成;而外部個體的引入能夠豐富種群基因,加速目標(biāo)個體的進化.

3.5 問題回答

通過分析第3.3.3 節(jié)和第3.4 節(jié)的實驗結(jié)果,對第3.3 節(jié)開頭中提出的兩個問題做如下回答.

回答問題1.本文設(shè)計的關(guān)鍵字流圖比較程序相似性,相對于其他方法比較程序相似性有什么優(yōu)點?如何來檢驗方法的有效性?

第2.5 節(jié)已經(jīng)討論過關(guān)鍵字流圖比較程序相似性的優(yōu)勢,程序的相似程度可以通過最大公共子圖距離進行判定.通過相似程序間測試用例的共享,實現(xiàn)數(shù)據(jù)用例的重用.可根據(jù)測試用例的重用效果證實關(guān)鍵字流圖比較程序相似性方法的有效性.由表6 傳統(tǒng)方法與本文方法測試程序的評判結(jié)果,傳統(tǒng)方法的覆蓋率為15%,平均進化代數(shù)為890.9 代;而作為引入相似程序測試用例的本文方法的目標(biāo)路徑覆蓋率為100%,平均進化代數(shù)為3.5.表11 增加了兩組基準程序和5 組工業(yè)程序,本文方法測試程序的目標(biāo)路徑覆蓋率皆為100%(注意:PG17 除外,因其為不相似程序的測試),前3 項評判標(biāo)準皆優(yōu)于傳統(tǒng)測試方法,第4 項評價指標(biāo)能夠排除實驗的隨機影響因素,從而證明了本文方法的有效性.由此可知:將相似程序(如,快速排序和冒泡排序)的測試用例相互引入到對方的測試中,測試效率顯著提高.由此證實了本文程序相似性判定方法的有效性.

回答問題2.相似程序間用例的共享能夠減少多少測試的工作量,提高多少測試效率?

從表7 和表8 可看出:在不同的種群規(guī)模和不同的變異概率下,本文方法目標(biāo)路徑的覆蓋率都是100%,4 項評價指標(biāo)充分證明了本文方法優(yōu)于傳統(tǒng)方法.結(jié)合表6 和表13,在所有程序的測試中,本文方法下的目標(biāo)路徑覆蓋率均為100%(注意:PG17 除外,因其為不相似程序的測試),平均進化代數(shù)最高(即最差情況)也僅為36.13;而傳統(tǒng)方法目標(biāo)路徑覆蓋率最大才達到91%,平均進化代數(shù)除PG3 以外均超過130.可見,本文方法的測試效率顯著高于傳統(tǒng)方法.因為本文方法在進化遺傳操作中引入了相似程序適應(yīng)度較高的測試用例,種群在進化時隨機地與這些個體進行交叉,其收斂速度明顯高于傳統(tǒng)方法.

3.6 有效性分析、存在的問題及其初步解決方案

影響實驗效果的因素包括內(nèi)部因素和外部因素.

1)內(nèi)部因素主要是遺傳算法本身對實驗結(jié)果造成的影響.種群初始化采用隨機生成的方法,輪盤賭法選擇個體進行遺傳操作也具有一定的隨機性,為了降低算法隨機性帶來的影響,進行100 次獨立的實驗,實驗結(jié)果取100 次重復(fù)實驗的平均值;

2)外部因素包括程序本身對實驗結(jié)果的影響.與實驗選取的對象有關(guān),本文方法測試不同組的程序,測試用例的重用效果略有差別.另外,實驗發(fā)現(xiàn):本文方法的實驗結(jié)果受引入的測試用例的個數(shù)和適應(yīng)度的影響,一定范圍內(nèi)引入的測試用例個數(shù)越多和采用較好適應(yīng)度的測試用例往往能取到相對較好的結(jié)果,實驗中引入的測試用例為傳統(tǒng)方法生成的測試用例.

針對用例重用的問題,本文探究了相似程序間測試用例的重用,實驗取得了較好的結(jié)果,證明了方法的有效性.然而,本文仍存在以下不足.

1)本文方法在判定規(guī)模較小程序的相似性時會具有一定的偶然性,其準確性有待進一步提高;

2)存在有些相似程序的用例長度不同的情況,測試數(shù)據(jù)無法共享,該條件有一定的局限性.

若判定為相似程序的測試用例長度不同,那么在遺傳算法生成測試用例的過程中,種群個體不能與相似程序的測試用例進行交叉進化.若將引入個體的長度與進化種群個體的大小改成一致,則能夠完成用例長度不同的程序間測試用例的重用.

本文就存在的不足設(shè)想如下初步解決方案.

1)若待測程序的測試用例長度小于相似程序測試用例的長度,減小相似程序測試用例的長度,使待測程序與相似程序的測試用例長度相同,根據(jù)關(guān)鍵字流圖最大公共子圖,刪減不屬于最大公共子圖節(jié)點對應(yīng)測試用例的部分;

2)若待測程序的測試用例長度大于相似程序測試用例的長度,增加相似程序測試用例的長度,使待測程序與相似程序的測試用例長度相同.找出相似程序關(guān)鍵字流圖不存在關(guān)鍵字的節(jié)點所對應(yīng)的位置,隨機增添最大公共子圖對應(yīng)相似程序的測試數(shù)據(jù),至待測程序與相似程序測試用例的長度相同.

4 總結(jié)及進一步研究

本文提出了一種面向關(guān)鍵字流圖判斷相似程序,并重用已知的測試用例來完成相似程序測試的方法.其主要貢獻如下.

1)提出一種面向關(guān)鍵字流圖的程序相似性的比較方法.通過構(gòu)建的關(guān)鍵字流圖求關(guān)鍵字流圖最大公共子圖,利用最大公共子圖距離算法計算程序的相似度.該方法兼顧比較程序的序列和功能結(jié)構(gòu)的相似性.通過關(guān)鍵字流圖判定相似的程序,程序規(guī)模相近,程序功能結(jié)構(gòu)相似;

2)提出一種基于相似程序程度間測試用例重用的方法.將程序已經(jīng)生成的測試用例重用到相似程序的測試用例生成中,在遺傳算法進化時,引入相似程序適應(yīng)度較高的測試用例,種群個體以一定概率與引入的測試用例進行交叉變異,有利于加快種群的進化速度,提高測試用例的生成效率;

3)開發(fā)了一個判定程序相似性的插件,該插件根據(jù)本文所提出的方法對程序相似性進行判定,用戶選擇放在兩個待測程序的文件(每個文件內(nèi)只放待測程序的代碼),點擊測試按鈕運行插件.執(zhí)行結(jié)束返回兩個程序的相似度,并根據(jù)設(shè)定的閾值判定它們是否相似.

在第3.6 節(jié)中分析了本文存在的不足,就測試待測程序需要輸入測試數(shù)據(jù)受到個數(shù)限制而無法重用的問題,設(shè)想了初步的解決方案.在未來的工作中,進一步研究相似程序間測試用例重用的局限性,特別針對相似程序因測試數(shù)據(jù)數(shù)量受限而不能重用的問題,深入分析前面假設(shè)的可行性,以提高相似程序間測試用例重用的通用性與準確性.