錢忠勝,宋 濤

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

2 程序相似性的判定

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

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

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

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

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

2.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

F=MSTR/MSe(4)

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

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

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

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

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

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

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

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

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)鍵字流圖最大公共子圖的生成

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

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

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

在字符串S和T所有前綴子串對(duì)的最長(zhǎng)公共后綴中,長(zhǎng)度最大的即為字符串S和T的最長(zhǎng)公共子串,即:

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

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

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

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

3)判斷最長(zhǎng)公共子串的長(zhǎng)度是否大于0:若長(zhǎng)度大于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所有前綴子串對(duì)的最長(zhǎng)公共后綴,見表2.

字符串S為快速排序程序關(guān)鍵字流圖的節(jié)點(diǎn)中關(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é)點(diǎn)存儲(chǔ)信息組合而成.根據(jù)字符串S和T的最大公共子串構(gòu)建關(guān)鍵字流圖最大公共子圖.

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

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

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

2.4 程序相似性的判定

待測(cè)程序快速排序與冒泡排序的關(guān)鍵字流圖最大公共子圖已經(jīng)生成,本節(jié)利用最大公共子圖距離算法(見定義5)計(jì)算程序相似程度.最大公共子圖距離公式(公式(1))中,|G1|和|G2|分別表示程序快速排序和冒泡排序的節(jié)點(diǎn)數(shù),mcs|G1,G2|表示最大公共子圖的節(jié)點(diǎn)數(shù).由圖6 知:冒泡排序與快速排序存儲(chǔ)關(guān)鍵字的節(jié)點(diǎn)都為5,關(guān)鍵字流圖最大公共子圖的節(jié)點(diǎn)為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.程序相似度的判定.

輸入:待測(cè)程序program1,program2;

輸出:待測(cè)程序相似度similarity.

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

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

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

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

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

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

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

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

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

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

例如,圖7 為冒泡排序另一種編寫方式的部分代碼,由于編程習(xí)慣不同,有些程序員會(huì)把第2 行~第4 行代碼寫成“intt,i,j;”,兩種書寫方式功能完全相同.第2 行~第4 行代碼的作用是定義整型變量,屬于一個(gè)基本塊,會(huì)生成關(guān)鍵字流圖的一個(gè)節(jié)點(diǎn).而基于源代碼進(jìn)行關(guān)鍵字比較時(shí),則會(huì)因?yàn)椴煌臅鴮懜袷皆斐刹煌慕Y(jié)果.

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

2.6 程序相似性檢驗(yàn)插件的原型

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

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

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

按鈕“Select pr ogram 1”和按鈕“Select pr ogram 2”是兩個(gè)選擇待測(cè)程序的按鈕,測(cè)試程序的相似度時(shí),分別點(diǎn)擊這兩個(gè)按鈕選擇待測(cè)程序所在的文件,實(shí)驗(yàn)選擇的待測(cè)程序?yàn)槊芭菖判蚺c快速排序.點(diǎn)擊“Testing”按鈕,將以百分?jǐn)?shù)的形式顯示兩個(gè)待測(cè)程序的相似度.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 測(cè)試用例生成算法

測(cè)試用例生成算法采用Java 語(yǔ)言編寫,并在MyEclipse 2 010 中運(yùn)行.計(jì)算機(jī)配置為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,個(gè)體individual,染色體長(zhǎng)度chro_size,進(jìn)化代數(shù)gen_size,交叉概率pc,變異概率pm;

輸出:新種群.

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

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

算法3(本文方法).

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

輸出:新種群.

3.3 測(cè)試用例生成實(shí)驗(yàn)

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

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

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

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

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

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

我們采用對(duì)比實(shí)驗(yàn)來解答上面兩個(gè)問題.實(shí)驗(yàn)的不同點(diǎn)主要在于種群進(jìn)化的方式不同.

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

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

3.3.1 實(shí)驗(yàn)對(duì)象

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

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

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

3.3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

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

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

3.3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

3.4 進(jìn)一步實(shí)驗(yàn)

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

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

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

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

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

Table 11 Basic information of experimental subjects表11 實(shí)驗(yàn)對(duì)象的基本信息

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

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

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

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

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

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

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

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

下面分別從4 個(gè)評(píng)價(jià)標(biāo)準(zhǔn)對(duì)比測(cè)試用例的生成效率.

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

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

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

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

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

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

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

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

3.5 問題回答

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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