利用函數(shù)影響力的相似程序間測試用例重用與生成

錢忠勝，宋 佳，俞情媛，成軼偉，孫志旺

（江西財經(jīng)大學(xué)信息管理學(xué)院，江西南昌 330013）

1 引言

由于軟件產(chǎn)業(yè)的飛速發(fā)展，人們對軟件質(zhì)量重要性的認識也逐漸增強.軟件測試在軟件項目實施過程中的重要性日益突出.尋找合適的測試用例是測試工作的重要任務(wù)，它可以提高軟件的正確性、完整性、可靠性［1，2］.

在測試中，回歸測試是一項重要的測試活動，它是指對原來的程序進行變更后，重新對變更后的程序進行測試.本文通過檢測前后程序的相似部分，并重用相似部分的用例，提高回歸測試的效率.

檢測程序變更前后的相似性是本文回歸測試中用例重用與生成的首要工作.目前，不少學(xué)者提出程序相似性檢測方法.其中，有的通過分析相關(guān)的控制流圖來檢驗圖神經(jīng)網(wǎng)絡(luò)估計程序相似度的有效性［3］；有的通過分語言行篩選方法將代碼降維，并對其特征進行匹配，以便快速判定相似程序［4］；有的借用循環(huán)神經(jīng)網(wǎng)絡(luò)、卷積神經(jīng)網(wǎng)絡(luò)等方法學(xué)習(xí)程序特征，以此來構(gòu)建模型［5］.本文從結(jié)構(gòu)和功能上，通過構(gòu)建函數(shù)調(diào)用圖檢測程序變更前后的相似部分，為生成所需用例做準備.

測試用例自動生成已經(jīng)取得了諸多進展，但測試資源未得到充分利用，導(dǎo)致在測試過程中仍存在一些重復(fù)工作.測試用例重用是指再次組織和運用以往測試過程中已生成的測試數(shù)據(jù).與重新生成用例相比，重用已有測試用例不僅可充分利用已有資源，而且可減少測試所需時間.

本文通過程序變更前后的相似性檢測方法獲取已有用例并重用，來提高回歸測試效率，主要展開以下工作：

（1）利用函數(shù)調(diào)用圖檢測程序變更前后相似性，識別可進行用例重用的相似函數(shù)，并將該部分的用例重用到變更后程序的測試中；

（2）經(jīng)相似性檢測后，程序不相似部分則通過改進遺傳算法生成測試數(shù)據(jù)，這里，將函數(shù)影響力作為適應(yīng)度函數(shù)，優(yōu)化遺傳算法，篩選優(yōu)秀用例.

2 函數(shù)關(guān)鍵性的判定與程序相似部分的檢測

根據(jù)函數(shù)在程序中的重要程度，對函數(shù)關(guān)鍵性進行判定，并根據(jù)函數(shù)的調(diào)用情況檢測程序的相似部分.

2.1 函數(shù)關(guān)鍵性的判定

不同的函數(shù)在程序中扮演著不同的角色，在程序中有一些函數(shù)對程序的正常運行起著決定性作用，本文將這些函數(shù)稱為關(guān)鍵函數(shù)（Critical Function，CF）.通過建立函數(shù)調(diào)用圖，對函數(shù)在程序中的層次進行識別，并記錄函數(shù)的調(diào)用程度，以此來識別函數(shù)的關(guān)鍵性.按照每個關(guān)鍵函數(shù)的關(guān)鍵性由大到小排列，形成的序列為關(guān)鍵函數(shù)序列（Critical Function Sequence，CFS）.

為更好地說明函數(shù)關(guān)鍵性的判定方法，下面定義一些相關(guān)概念.

定義1序列（Sequence）［6］.程序每個執(zhí)行路徑可看作一個序列，它是一個有序的事件列表，用S=＜S1，S2，…，Sn＞來表示.序列中的每個元素由二元組（Flg；FName）組成，其中，F(xiàn)lg 為一個事件的進出標識，即程序中的調(diào)用入口或出口，F(xiàn)lg=“I”為調(diào)用入口，F(xiàn)lg=“O”為調(diào)用出口；FName指函數(shù)名.

定義2序列模式（Sequence Pattern，SP）［6］.序列S由多個模式組成，此時的序列即序列模式，用SP=｛P1，P2，…，Pn｝表示，其中，n是構(gòu)成序列SP 的模式數(shù).在每個模式下，函數(shù)的調(diào)用入口就像一扇門，從“I”進入此門，再從“O”出門，可知每個模式P的長度均為偶數(shù).

定義3壓縮序列模式（Condensed Sequence Pattern，CSP）［6］.在刪除了序列模式SP 中相鄰的重復(fù)模式后，剩余的序列被稱為壓縮序列模式.將CSP 中的一級模式劃分為不同級別的子模式，并將它們存儲到壓縮序列模式集SPcsp中.

在文獻［6］模型構(gòu)建方法的基礎(chǔ)上，對函數(shù)調(diào)用關(guān)系進行預(yù)處理，過程如下.

（1）建立初始程序序列.將函數(shù)地址抽象為函數(shù)名，并識別函數(shù)的進出調(diào)用，利用這2 個程序特征對執(zhí)行軌跡進行順序建模.

（2）刪除相鄰重復(fù)模式.為減少重復(fù)循環(huán)模式的時間和內(nèi)存消耗，簡化執(zhí)行序列，在得到程序初始序列后，保留第一時間出現(xiàn)的重復(fù)序列中的一個模式，刪除其他重復(fù)序列，可得到壓縮序列模式.具體過程如算法1所示.

（3）構(gòu)建函數(shù)調(diào)用圖（Function Call Diagram，F(xiàn)CD）.刪除相鄰重復(fù)模式后，利用序列模式級別來度量不同模式間的包含關(guān)系，而序列模式級別由模式中函數(shù)調(diào)入調(diào)出關(guān)系表示，由此構(gòu)成函數(shù)調(diào)用圖.

定義4 模式層級（Mode Level，ML）.CSP 層級關(guān)系中函數(shù)的層次級別，即調(diào)用期間所包含的其他函數(shù)的出度和入度之差，且層級大的函數(shù)被層級小的函數(shù)調(diào)用.

圖1 函數(shù)調(diào)用圖

例1 圖1 描述了長序列模式SP，它包含子模式P1，P2，P3，P4，P5和P6，可知從序列模式的層次關(guān)系來看，若SP 的序列模式層次為ML=1，則P2，P3，P4，P5和P6的序列模式層次分別為ML=2，ML=3，ML=3，ML=4 和ML=3.例如，P6的序列模式層次為ML（P6）=1+5-3=3，其中，“1”表示序列模式本級；“5”表示函數(shù)func1 和func2 間的入度為5，即func2，func3，func4，func3和func2的函數(shù)調(diào)度標識是“I”；同理，“3”表示函數(shù)func1 和func2 間的出度為3，即func3，func3 和func4的函數(shù)調(diào)用標識是“O”.

在程序執(zhí)行序列模式集中，通過分析不同模式的函數(shù)可知，具有相同決策功能的函數(shù)越多，在不同情況下程序執(zhí)行中函數(shù)調(diào)用的可能性越大.可見，關(guān)鍵函數(shù)在程序執(zhí)行中起著決定性作用.

設(shè)計一種基于函數(shù)調(diào)用圖的檢測算法來識別函數(shù)的關(guān)鍵性，主要分兩步：首先，構(gòu)建CSP 的簡單模式，消除重復(fù)模式，得出相應(yīng)的函數(shù)層級關(guān)系；其次，統(tǒng)計在CSP中出現(xiàn)的有相同決策功能的函數(shù)，并計算它們在層級關(guān)系中出現(xiàn)的次數(shù)，根據(jù)函數(shù)的調(diào)用次數(shù)和層級來判定函數(shù)的關(guān)鍵性.

在CSP 中的模式層級關(guān)系確定后，即可判定關(guān)鍵函數(shù)，具體過程如算法2所示.

在算法2 中，第1～6 行計算具有相同決策功能函數(shù)出現(xiàn)的次數(shù)，次數(shù)越多，說明函數(shù)越重要；第7行計算序列模式的層級，層級小的序列模式調(diào)用持續(xù)時間較長，這類調(diào)用被中斷可能會影響整個程序的運行，由此看來層級越小的序列模式中函數(shù)的重要性越大；第8行根據(jù)函數(shù)的調(diào)用次數(shù)和序列模式層級將函數(shù)排序，即可得到根據(jù)函數(shù)的關(guān)鍵性從大到小排列的關(guān)鍵函數(shù)序列.

例2 由圖1 可知，P3和P5是不相鄰的相同模式，只需要歸為一類序列模式，SPcsp=｛P1，P2，P3，P4，P6｝，func1，func2，func3 和func4 在CSP 中的個數(shù)分別為1，2，2 和1.則func2 和func3 在程序中是較為關(guān)鍵的函數(shù).

根據(jù)函數(shù)的調(diào)用次數(shù)由多到少對函數(shù)進行排序，若函數(shù)的調(diào)用次數(shù)相同則比較函數(shù)的層級大小，層級越小就越重要，由此可得關(guān)鍵函數(shù)序列，且在該序列中，一個函數(shù)順序越靠前，它在程序中就越關(guān)鍵.

2.2 程序相似部分的檢測

由于程序相似部分的檢測是回歸測試中待測程序用例重用的前提，因此相似部分的檢測是本文重要的工作之一.從程序動態(tài)執(zhí)行角度出發(fā)，在文獻［6］提出的函數(shù)執(zhí)行序列模式基礎(chǔ)上進行改進，提出一種基于關(guān)鍵函數(shù)序列的程序相似部分檢測方法.由于大部分回歸測試前后程序的變動不會太大，僅對比程序的關(guān)鍵函數(shù)序列不足以檢測出回歸測試前后函數(shù)的相似之處和細微變化，因此，在獲得程序的關(guān)鍵函數(shù)序列后，進一步比較對應(yīng)函數(shù)的關(guān)鍵字序列（即在程序的某一函數(shù)中，依據(jù)關(guān)鍵字出現(xiàn)的先后順序所構(gòu)成的序列）.注意，涉及的關(guān)鍵字有abstract，break，byte，case，catch，char，continue，default，else，extends，float，for，if，int，private，protected，public，return，static，switch，this，throw，try，void，while等.

通過比較關(guān)鍵函數(shù)的相似性來判定程序變更前后的相似性，重用變更前相似函數(shù)測試用例.當已變更的程序重用已知用例后，無法完全滿足自身測試需求時，則利用遺傳算法篩選優(yōu)秀個體，并進化種群，從而生成可用的測試用例.程序相似部分檢測過程如圖2所示.

圖2 程序相似部分檢測

基于函數(shù)調(diào)用圖的函數(shù)關(guān)鍵性判定及程序相似部分檢測的具體過程如下.

（1）將整個程序看作由多個函數(shù)組成，把函數(shù)地址轉(zhuǎn)換為函數(shù)名，并識別函數(shù)的進出調(diào)用關(guān)系，根據(jù)執(zhí)行軌跡的建模來描述整個程序的執(zhí)行情況，即把程序動態(tài)執(zhí)行過程轉(zhuǎn)換為執(zhí)行序列.

（2）對相鄰的重復(fù)程序序列模式進行識別，利用重復(fù)模式刪除算法，來減少程序的冗余執(zhí)行序列，從而得到簡化的程序序列.具體過程如算法1所示.

（3）利用函數(shù)關(guān)鍵性判定算法來識別不同層次上的函數(shù)分布規(guī)律，從而根據(jù)函數(shù)的出現(xiàn)次數(shù)以及層次關(guān)系來判定程序的關(guān)鍵函數(shù).具體過程如算法2所示.

（4）根據(jù)函數(shù)相似度的計算方法來檢測程序之間的相似部分.具體過程如算法3所示.

由2.1 節(jié)得到函數(shù)調(diào)用圖（FCD）后，通過進一步比較程序中函數(shù)同一層級關(guān)系對應(yīng)的函數(shù)關(guān)鍵字，來識別程序間相似部分.將待比較相似部分的程序的FCD中函數(shù)名作為節(jié)點，節(jié)點內(nèi)包含該函數(shù)的關(guān)鍵字序列以及被調(diào)用次數(shù)（注意：不相同模式下具有相同決策功能的函數(shù)為同一種函數(shù)，統(tǒng)計時計算這種函數(shù)的調(diào)用次數(shù)總和即可）.

假定有2 個函數(shù)調(diào)用圖DF1和DF2，DF1=｛A1，A2，…，Am｝，DF2=｛B1，B2，…，Bn｝，m和n分別為DF1和DF2中函數(shù)個數(shù).其中，Ai=＜a1，a2，…，ar＞和Bj=＜b1，b2，…，bs＞都是函數(shù)調(diào)用圖DF1和DF2中的元素，代表對應(yīng)函數(shù)的關(guān)鍵字序列，1≤i≤m，1≤j≤n，au和bv分別為關(guān)鍵字序列Ai和Bj中的關(guān)鍵字，1≤u≤r，1≤v≤s.

根據(jù)函數(shù)調(diào)用圖DF1和DF2，得到在不同層級上的函數(shù)分布，并識別公共函數(shù).在此基礎(chǔ)上，進一步查找對應(yīng)函數(shù)的關(guān)鍵字形成每個函數(shù)對應(yīng)的關(guān)鍵字序列，比較2 個函數(shù)的關(guān)鍵字序列來判斷程序的相似部分.若待比較程序相應(yīng)的函數(shù)關(guān)鍵字序列Ai和Bj相同，則認為這2個函數(shù)相似.此處將函數(shù)調(diào)用圖DF1和DF2的相似部分記為Sim=｛(Ai，Bj)|I(Ai，Bj)，1≤i≤m，1≤j≤n｝，其中，表示DF1中第i個函數(shù)與DF2中第j個函數(shù)相似.

基于函數(shù)調(diào)用圖識別程序相似部分的詳細過程如算法3所示.

3 相似程序間測試用例重用與生成

由于新程序未變更部分較多，利用歷史版本程序的用例可覆蓋新程序的大部分目標路徑，未被用例覆蓋的部分則需借用遺傳算法將可重用舊版本程序的用例引入到種群進化中，通過適應(yīng)度函數(shù)進行篩選，最終生成新程序的優(yōu)秀用例.

3.1 基于函數(shù)影響力的適應(yīng)度設(shè)計

利用遺傳算法來實現(xiàn)回歸測試中相似程序間測試用例的重用與生成，主要過程如下.

（1）在檢測出程序的相似部分后，嘗試利用與待測程序更相近的歷史版本程序的測試用例去覆蓋待測程序的目標路徑，若生成的用例能滿足回歸測試需求，即可直接重用歷史版本程序用例.

（2）若歷史版本程序的用例無法完全滿足覆蓋待測程序目標路徑的任務(wù)，則使用遺傳算法進化生成滿足測試需求的用例.在使用遺傳算法進行相似程序測試用例重用時，將歷史版本程序中具有較高適應(yīng)度值（即函數(shù)影響力（見下文定義11）越大，適應(yīng)度值越高）的用例引入種群進化過程中，種群的其他個體也可學(xué)習(xí)并利用這些用例，這樣即可更迅速地生成所需用例.

適應(yīng)度函數(shù)在進化生成中發(fā)揮著重要作用，接下來介紹與設(shè)計的適應(yīng)度函數(shù)有關(guān)的幾個重要因素，并以圖1中的函數(shù)調(diào)用圖為例進行說明.

定義5函數(shù)調(diào)用率（Function Call Rate，F(xiàn)CR）.具有相同決策功能的函數(shù)的調(diào)用次數(shù)FCall占整個程序所有函數(shù)調(diào)用總次數(shù)PCall的比率.

FCR可表示為

例3圖1 中所有函數(shù)調(diào)用的總次數(shù)為6，函數(shù)func1被調(diào)用了1次，由定義5可知，函數(shù)func1的調(diào)用率為1/6.

定義6函數(shù)關(guān)鍵度（Function Criticality，F(xiàn)C）.指函數(shù)調(diào)用率與函數(shù)在程序中的模式層級比值.

函數(shù)關(guān)鍵度（FC）反映了函數(shù)在程序中被調(diào)用的頻度以及函數(shù)在程序中被調(diào)用的持續(xù)程度.FC可表示為

其中，ML為函數(shù)在函數(shù)關(guān)系調(diào)用圖中的模式層級.

例4圖1 中函數(shù)func1 的層級為1，可得，函數(shù)func1的函數(shù)關(guān)鍵度為（1/6）/1=1/6.

程序變更后，函數(shù)一般有3 種變更類型：增加、刪除、修改.這3種操作對回歸測試有著不同程度的影響.

（1）增加：新版本程序添加了新函數(shù).

（2）刪除：新版本程序剔除了舊版本程序中的函數(shù).

（3）修改：新版本程序更改了函數(shù)名或?qū)瘮?shù)內(nèi)部進行了修復(fù)操作.

定義7函數(shù)關(guān)聯(lián)度（Function Relevance Degree，F(xiàn)RD）.該函數(shù)所關(guān)聯(lián)的其他函數(shù)或者所調(diào)用的子函數(shù)數(shù)量.

例5圖1 中函數(shù)func1 的模式層級為1，其在程序執(zhí)行期間分別調(diào)用了函數(shù)func2，func3，func4，由定義7可知，函數(shù)func1的關(guān)聯(lián)度為3.

定義8函數(shù)變更影響系數(shù).不同變更類型的函數(shù)變更個數(shù)與程序中函數(shù)變更總個數(shù)的比值.函數(shù)變更影響系數(shù)λF可表示為

其中，TF為以上3 種函數(shù)變更類型的個數(shù)，MF為變更函數(shù)總個數(shù).

定義9函數(shù)變更率（Function Modify Rate，F(xiàn)MR）.新版本程序在舊版本程序的基礎(chǔ)上進行變更的程度.

FMR可表示為

其中，HF為舊程序中有變更的函數(shù)個數(shù)；NF為變更后新程序所擁有的函數(shù)總個數(shù)；FRD 為函數(shù)關(guān)聯(lián)度，與變更函數(shù)的關(guān)聯(lián)度越大，受到函數(shù)變更的影響就越大.

定義10函數(shù)穿越率（Function Traversal Rate，F(xiàn)TR）.測試用例對函數(shù)關(guān)鍵字的覆蓋程度，即用例對函數(shù)進行測試時經(jīng)過該函數(shù)中關(guān)鍵字的個數(shù)與該函數(shù)關(guān)鍵字總個數(shù)的比值.

FTR可表示為

其中，NCK是在測試時穿越函數(shù)內(nèi)關(guān)鍵字的個數(shù)，NK是函數(shù)中關(guān)鍵字節(jié)點總個數(shù).

例6若變更后的程序?qū)D1 中函數(shù)func1 做修改（注意：由于此處僅對函數(shù)內(nèi)部進行修改，故不改變原函數(shù)調(diào)用圖），增加了一個if 判斷，其他關(guān)鍵字沒有變動，由上面的定義可知，函數(shù)func1 的變更率為λF×另外，在計算函數(shù)func1的穿越率時，由于新增了一個if關(guān)鍵詞，需將要經(jīng)過的關(guān)鍵字個數(shù)加1.

FC反映了函數(shù)在程序中被調(diào)用的頻度及函數(shù)被調(diào)用的持續(xù)程度.函數(shù)被調(diào)用的次數(shù)越多，且在函數(shù)調(diào)用圖中的模式層次越靠下，該函數(shù)對整個程序影響就越大，在回歸測試中對該函數(shù)的測試也更重要.FMR表示新版本程序在舊版本程序的基礎(chǔ)上進行變更的程度，變更程度越小，重用舊版本程序的測試用例就越有效.FTR 檢測重用舊版本程序的測試用例時對函數(shù)關(guān)鍵字節(jié)點的覆蓋情況，反映了對舊版本程序用例的重用程度.

在測試用例進化生成過程中，賦予FC 以30%的初始權(quán)重，F(xiàn)C 值越大的函數(shù)對整個程序的影響越大，若此類函數(shù)存在問題，很有可能影響整個程序的正常執(zhí)行，應(yīng)使生成的測試用例能盡快覆蓋此類函數(shù)，體現(xiàn)了關(guān)鍵函數(shù)在程序中被重視程度.另外，分別賦予FMR 及FTR 各35%的初始權(quán)重.程序更新后，雖然存在改動的部分目標路徑在重用歷史程序的用例后仍未被覆蓋，但大部分目標路徑能通過FMR 與FTR 來表示重用情況.FMR 越小，表明新程序變更較小，則重用歷史用例效果越明顯；FTR 越大，表明測試用例對目標路徑的覆蓋程度越大.這兩個因素都在一定程度上體現(xiàn)了用例的重用程度，對加快回歸測試中新版本程序用例的進化生成有著更直接的促進作用，給予這兩個因素更大的權(quán)重.特別地，重用后未覆蓋部分需進化生成另外的測試用例.因此，在進化生成的過程中需重點關(guān)注程序的變更部分以及重用后未被覆蓋的部分.

定義11函數(shù)影響力（Function Influence，F(xiàn)I）.函數(shù)在程序中的重要程度，即函數(shù)需要被測試的輕重緩急程度.

FI由FC，F(xiàn)MR和FTR共同決定，可表示為

其中，ω1=30%，ω2=35%以及ω3=35%為3 種測試影響因素的初始權(quán)重.

先用初始權(quán)重進行實驗，通過觀察實驗結(jié)果對權(quán)重進行適當調(diào)整，得出可取得較好測試數(shù)據(jù)生成效果的值（將函數(shù)影響力FI作為適應(yīng)度函數(shù)，對適應(yīng)度函數(shù)權(quán)重的詳細分析見4.1.3節(jié)）.

3.2 測試用例的重用與生成

本小節(jié)提出基于函數(shù)影響力的進化測試生成方法.在測試數(shù)據(jù)生成過程中，以相似程序間用例的重用為方向進行遺傳算法的具體實現(xiàn).從函數(shù)的關(guān)鍵程度、函數(shù)的變更程度及測試數(shù)據(jù)對函數(shù)的覆蓋程度等方面來設(shè)計用例進化生成的適應(yīng)度，從而加快變更后程序測試用例的生成.

根據(jù)3.1 節(jié)設(shè)計的適應(yīng)度函數(shù)（即函數(shù)影響力）給出一種基于函數(shù)影響力的測試進化生成方法，具體實現(xiàn)過程如算法4所示.

算法4 利用改進后的遺傳算法來進化生成測試用例.在該算法中，第1 行和第2 行設(shè)置各個參數(shù)并初始化種群；第3～13 行首先選擇可重用個體，再根據(jù)式（6）計算個體適應(yīng)度值，然后在交叉、變異過程中，引入歷史版本程序可重用的測試用例，并判斷新種群中是否有個體覆蓋了目標路徑，若目標路徑覆蓋集合中沒有該目標路徑，則將該個體加入測試數(shù)據(jù)集；最后，判斷是否滿足算法終止條件，即種群是否達到最大進化代數(shù)或目標路徑已全部被覆蓋，若滿足則終止算法，否則繼續(xù)執(zhí)行種群進化過程.

若重用歷史版本程序的測試用例，可能會出現(xiàn)新版本程序的部分目標路徑未被覆蓋的情況，此時需要利用遺傳算法來進化生成新的測試用例去覆蓋待測程序未被覆蓋的目標路徑.圖3 詳細描述了2.2 節(jié)圖2 中用例重用與生成的進化過程.

圖3 測試用例的重用與進化生成

由圖3可知，在種群進化過程中引入相似部分測試用例，將基于函數(shù)影響力設(shè)計的適應(yīng)度函數(shù)作為衡量種群個體優(yōu)劣的標準，保留適應(yīng)度函數(shù)值較高的用例，與已知相似程序的測試用例共同形成新的用例集來滿足測試需求.

依據(jù)關(guān)鍵函數(shù)的重要程度對該集合中的測試用例進行排序，排在前面的可優(yōu)先進行重用.

4 實驗設(shè)計與分析

為驗證本文方法的有效性，分別針對基準程序和工業(yè)程序設(shè)計對比實驗展開分析.實驗環(huán)境：操作系統(tǒng)為Win10，內(nèi)存為4 GB，主頻為2.3 GHz，系統(tǒng)類型為X64，編程語言為Java.

4.1 實驗過程與結(jié)果分析

本文在傳統(tǒng)遺傳法基礎(chǔ)上根據(jù)函數(shù)影響力設(shè)計適應(yīng)度函數(shù)，以提高測試效率.下面，先簡要介紹隨機法、傳統(tǒng)遺傳法及其他幾種經(jīng)典方法，再分別將本文方法與上述方法進行對比分析.

（1）隨機法：隨機產(chǎn)生輸入數(shù)據(jù)生成待測程序的測試用例.

（2）傳統(tǒng)遺傳法：采用分支距離與層接近度結(jié)合的方法設(shè)計適應(yīng)度函數(shù)，并根據(jù)該適應(yīng)度函數(shù)進化生成測試用例.

（3）文獻［7］方法：將否定選擇策略融入遺傳算法，自動生成覆蓋目標路徑的測試數(shù)據(jù).

（4）文獻［8］方法：對基本的細菌覓食算法進行改進，并應(yīng)用于測試用例的自動生成.

（5）文獻［9］方法：依據(jù)不可達路徑節(jié)點出現(xiàn)的概率計算個體穿越度，進而調(diào)整個體適應(yīng)度函數(shù)的路徑覆蓋測試數(shù)據(jù)生成.

（6）文獻［10］方法：在運用遺傳算法生成測試數(shù)據(jù)時，利用神經(jīng)網(wǎng)絡(luò)模擬計算個體適應(yīng)度值，對適應(yīng)度值較高的個體進行插樁驗證，從而獲得精確的適應(yīng)度值.

特別說明：（1）本文選取基準程序、中小規(guī)模工業(yè)程序和大規(guī)模工業(yè)程序作為待測程序，且在它們歷史版本信息已知的基礎(chǔ)上進行回歸測試實驗；（2）為了更好地體現(xiàn)新版本程序與歷史版本程序間的變更程度，定義程序的“變更率”（即程序變更部分的代碼行數(shù)占變更前總代碼行數(shù)的比例）這一特征.

4.1.1 對基準程序的實驗

基準程序具有結(jié)構(gòu)多樣性、運算各異性以及數(shù)據(jù)類型豐富性的特點，因而常被用于測試領(lǐng)域.這里選取幾種開源程序作為實驗對象，信息見表1.

表1 基準程序信息

程序PG1為三角形判別算法.程序PG2計算給定2個時間的差值.程序PG3為24點算法，根據(jù)已知的4個整數(shù)（必須使用每個數(shù)字，且僅可使用一次），通過加、減、乘、除這4 個運算符及括號，組成一個運算表達式，使其計算結(jié)果為24.程序PG4為經(jīng)典的九宮格算法，將1 到9 這9 個數(shù)不可重復(fù)地放到一個3×3 的表格中，要求表格中的同行、同列及對角線的所有數(shù)字相加等于15.

下面分別利用隨機法、傳統(tǒng)遺傳法及本文方法對表1 中程序進行測試.參數(shù)設(shè)置包括初始種群為100，交叉概率為0.8，變異概率為0.15，最大進化代數(shù)為200，獨立運行次數(shù)為50.實驗結(jié)果見表2.

表2 基準程序上的結(jié)果對比

由表2可知，本文方法通過重用待測程序歷史版本的用例，在平均進化代數(shù)、用例生成數(shù)量及覆蓋率方面均優(yōu)于隨機法和傳統(tǒng)遺傳法.

在測試用例數(shù)量方面，本文方法均少于另外2種方法，如程序PG3，生成測試用例數(shù)量明顯較少，這表明本文方法生成的用例具有較高質(zhì)量.

在覆蓋率方面，本文方法在程序PG1，PG2，PG3，PG4 上的覆蓋率均為100%.特別地，在程序PG4 上，相較于隨機法和傳統(tǒng)遺傳法，本文方法的覆蓋率分別提高約25%和8%，提升效果較為明顯.可見，本文方法在覆蓋率方面效果更優(yōu).

為更直觀地表示不同算法在幾個基準程序上的進化代數(shù)分布情況，這里采用箱型圖進行展示，如圖4所示.

從圖4 的不同算法在幾個程序上的進化代數(shù)分布情況來看，本文方法的進化代數(shù)更少.例如，對于待測程序PG3，本文方法的進化代數(shù)遠低于隨機法和傳統(tǒng)遺傳法，這是由于本文方法重用已有測試用例覆蓋目標路徑，只需再生成新用例去覆蓋有變更的路徑，而隨機法和傳統(tǒng)遺傳法需要重新生成所有用例.

圖4 3種算法在4個程序上的進化代數(shù)對比

在基準程序上，本文方法對傳統(tǒng)遺傳法的改進具有積極效果，在降低平均進化代數(shù)和減少用例生成數(shù)量的同時，還能提升目標路徑的覆蓋率.

4.1.2 對工業(yè)程序的實驗

下面針對工業(yè)程序進一步驗證本文方法的有效性.因本文策略與文獻［7］方法均是對路徑覆蓋測試數(shù)據(jù)生成的改進，且實驗?zāi)康募碍h(huán)境相近，故選擇與該文獻中方法進行比較，參數(shù)設(shè)置成與基準程序的一致.

這里選取Replace，Space，Gzip，Sed_Part和Flex_Part這5 種工業(yè)程序（來源于http：//sir.unl.edu/portal/index.php）實驗.表3 分別列出了這5 種待測程序的基本信息.

表3 中小規(guī)模工業(yè)程序信息

Replace主要實現(xiàn)模式匹配和替換；Space是針對數(shù)組定義語言的解釋器；Gzip，Sed_Part 和Flex_Part 均為Unix工具（Sed_Part和Flex_Part分別是大規(guī)模工業(yè)程序Sed和Flex的一部分）.

對每個待測程序選擇部分函數(shù)進行實驗，其實驗結(jié)果如表4所示.

由表4可知，本文方法的平均進化代數(shù)及測試用例數(shù)量均比文獻［7］方法少，路徑覆蓋率有所提高，這表明本文方法加快了進化過程.

表4 中小規(guī)模工業(yè)程序上的結(jié)果對比

在平均進化代數(shù)方面，對于待測程序PG5，PG6 和PG7（Replace，Space 和Gzip），本文方法略少于文獻［7］方法.程序PG8 和PG9（Sed_Part 和Flex_Part）進化代數(shù)達到實驗設(shè)置的最大值，其原因是這2個程序存在無法覆蓋的目標路徑，在最大進化代數(shù)內(nèi)不能覆蓋所有目標路徑.

在測試用例數(shù)量方面，在稍大程序PG8 和PG9 上，本文方法明顯少于文獻［7］方法.

在覆蓋率方面，2 種方法在程序PG5，PG6 和PG7上，目標路徑覆蓋率均達到100%，而在程序PG8和PG9上均未完全覆蓋目標路徑.對于程序PG8 和PG9，本文方法的覆蓋率未能達到100%的主要原因是程序本身存在無法覆蓋的路徑.雖然待測程序PG8有較大變更，但用本文方法對其進行測試時，覆蓋率還是有所提升，本文方法的目標路徑覆蓋率仍高于文獻［7］方法.這進一步說明本文提出的方法用例生成效率更高，這是因為一方面引入了歷史程序用例，另一方面利用函數(shù)影響力對適應(yīng)度函數(shù)進行設(shè)計獲得優(yōu)秀個體.

以上僅為從中小規(guī)模程序中選擇部分函數(shù)進行測試，接下來選取大規(guī)模工業(yè)程序Sed和Flex（均來源于http：//sir.unl.edu/portal/index.php），以及Go（來源于https：//blog.csdn.net/chongshangyunxiao321/article/details/50997404）進行實驗，將本文方法與文獻［8］方法、文獻［9］方法、文獻［10］方法進行對比.鑒于上述幾種方法的算法類別、參數(shù)設(shè)置、程序設(shè)計語言、操作系統(tǒng)等都不一樣，為比較的公平性和便捷性，此處，本文方法中的實驗參數(shù)均設(shè)置成與相應(yīng)對比方法一致.待測工業(yè)程序詳細信息見表5.

表5 大規(guī)模工業(yè)程序信息

Sed 是Unix 中一種非交互性文本編輯工具；Flex 是Unix 中詞法分析生成器；Go 是一種抽象策略性益智游戲軟件.對這3 個待測程序進行測試，實驗結(jié)果如表6所示.為了更清晰地看出本文方法與其他幾種方法在大規(guī)模工業(yè)程序上就平均進化代數(shù)方面的變化情況，這里增加了“平均進化代數(shù)之差百分比”（即本文方法與其他方法相比，平均進化代數(shù)增加或減少的比率）這一指標.

由表6 可知，對于程序PG10 和PG11（即Sed 和Flex），本文方法的平均進化代數(shù)均比文獻［8］方法要高，平均進化代數(shù)之差百分比分別為-17.0%和-54.5%（負數(shù)表示本文方法比文獻［8］方法的平均進化代數(shù)相對增加），主要原因是文獻［8］方法僅選取了部分可達路徑作為目標路徑，未考慮不可達路徑，而本文方法在目標路徑選取時未將不可達路徑排除，這使得本文方法需實施更多的進化過程覆蓋這些不可達路徑.另外，程序PG10 和PG11 對于它們的歷史版本程序變更較大，可重用的測試用例數(shù)量較少，通過改進的適應(yīng)度函數(shù)篩選優(yōu)秀個體需更多的進化代數(shù)，從而導(dǎo)致平均進化代數(shù)高于文獻［8］，但在覆蓋率方面分別提高了2%和17%.相比于文獻［9］方法，本文方法在平均進化代數(shù)方面分別減少了38.1%和55.4%，而在覆蓋率方面均達到100%.對于程序PG12，與文獻［10］相比，本文方法的平均進化代數(shù)有所降低，平均進化代數(shù)之差百分比為44.7%，覆蓋率達到了100%，提高了15%.

表6 大規(guī)模工業(yè)程序上的結(jié)果對比

從實驗結(jié)果來看，不論是在基準程序、中小規(guī)模工業(yè)程序，還是在大規(guī)模工業(yè)程序上，本文方法的測試用例生成效率優(yōu)于其他對比方法.具體地，在實現(xiàn)了目標路徑全覆蓋的情況下進化代數(shù)有一定程度的縮減.這表明本文重用歷史版本已知測試信息的有效性，以及運用函數(shù)影響力設(shè)計適應(yīng)度函數(shù)的合理性.

4.1.3 適應(yīng)度函數(shù)權(quán)重分析

根據(jù)以上實驗結(jié)果可得出，不同待測程序的適應(yīng)度函數(shù)影響因素的權(quán)重不同，具體結(jié)果如表7所示.

由表7 可知，大部分被測程序，各適應(yīng)度函數(shù)影響因素的權(quán)重與其初始權(quán)重相比沒有較大變動.ω1的范圍在22%～30%之間，ω2的范圍在30%～39%之間，ω3的范圍在32%～44%之間，都在較小的范圍內(nèi)變動.從表中的最大影響因素這一指標可看出，對于大部分被測程序，ω3影響相對來說最大，ω2次之，ω1最小，即總體上函數(shù)穿越率影響最大，函數(shù)變更率影響次之，函數(shù)關(guān)鍵度影響最小.

表7 適應(yīng)度函數(shù)影響因素的權(quán)重分配

4.2 顯著性分析

從4.1 節(jié)的實驗結(jié)果可見，本文方法具有很大的改進效果.為驗證實驗結(jié)果的可靠性，運用Z 假設(shè)檢驗方法對實驗結(jié)果進行顯著性分析，設(shè)置顯著性水平α=0.05，則Zα=-1.96.因在基準程序、中小規(guī)模工業(yè)程序與大規(guī)模工業(yè)程序上的實驗對比指標存在差異，對基準程序和中小規(guī)模工業(yè)程序?qū)嶒灲⒓僭O(shè)，檢驗本文方法與對比方法的測試用例平均生成數(shù)量是否有顯著差異；對大規(guī)模工業(yè)程序?qū)嶒瀯t建立假設(shè)，檢驗本文方法與對比方法的平均進化代數(shù)是否有顯著差異.

以三角形判別算法為例，設(shè)隨機變量X表示該算法進化生成的用例數(shù)量，它近似地服從正態(tài)分布.比較本文方法與對比方法中的隨機變量均值μ的大小，若μ越小，則說明對應(yīng)的方法可更快地得到所需測試用例，該方法就越有效.根據(jù)以上實驗結(jié)果可知：本文方法、傳統(tǒng)遺傳法和隨機算法的樣本容量均為n1=n2=n3=50，樣本均值依次為樣本方差

首先，建立原假設(shè)H0：μ1≥μ2和H0：μ1≥μ3，則對立假設(shè)H1：μ1＜μ2和H1：μ1＜μ3.然后，計算統(tǒng)計量即

最后，可得Z1≤Zα，Z2≤Zα.故拒絕原假設(shè)H0：μ1≥μ2和H0：μ1≥μ3，接受對立假設(shè)H1：μ1＜μ2和H1：μ1＜μ3.得出驗證結(jié)論：在三角形判別程序中，本文方法與其他2 種對比方法的結(jié)果具有顯著差異，本文方法比另外2種對比方法的用例生成效率更高.

根據(jù)以上檢驗過程，對基準程序和工業(yè)程序的實驗結(jié)果進行統(tǒng)計分析，檢驗結(jié)果如表8所示.

由表8可知，對于基準程序?qū)嶒灪椭行∫?guī)模工業(yè)程序?qū)嶒灒疚姆椒ㄅc隨機法、傳統(tǒng)遺傳法及文獻［7］方法相比，結(jié)果具有顯著差異.由此可知，本文方法生成的測試用例數(shù)量少于文獻［7］方法.本文的策略與文獻［7］方法一樣改進了遺傳算法，同時本文策略重用已知相似程序的測試用例，這是本文方法在一定程度上優(yōu)于文獻［7］方法的部分原因.對大規(guī)模工業(yè)程序中的待測程序PG10，本文方法與文獻［8］方法和文獻［9］方法相比，有顯著差異，本文方法在保證完全覆蓋待測程序目標路徑的前提下，實驗效果仍略優(yōu)于文獻［9］方法.本文方法與文獻［9］方法平均進化代數(shù)雖然均比文獻［8］方法多，但是覆蓋率均達到最佳.對于待測程序PG11，本文方法的覆蓋率達到100%，其平均進化代數(shù)少于文獻［9］方法.本文方法與文獻［10］方法相比，有顯著差異.對于大規(guī)模待測程序PG12，本文方法平均進化代數(shù)少于文獻［10］方法.

表8 Z檢驗驗證結(jié)果

綜上所述，不論在基準程序還是工業(yè)程序上，本文提出的基于函數(shù)影響力的相似程序間測試用例重用策略與其他對比方法相比均更有優(yōu)勢，同時也驗證了本文策略能夠提高測試數(shù)據(jù)生成效率.

5 相關(guān)工作

當前，程序相似性方面的研究逐漸深入.Gang等［11］提出了一種用于測量代碼功能相似性的方法，其將編碼控制流和數(shù)據(jù)流信息表示為緊湊矩陣，從語義矩陣中學(xué)習(xí)潛在特征，并執(zhí)行二進制分類.Liu 等［12］利用深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Networks，DNN）提取二進制函數(shù)特征，并基于這些特征計算距離來檢測二進制代碼相似度.汪潔等［13］先用數(shù)據(jù)流圖表示程序運行時的行為或事件，再從數(shù)據(jù)流圖中提取特征子圖，將其表示為字符串替代圖的匹配，并通過神經(jīng)網(wǎng)絡(luò)計算子圖間相似性.

以上方法借助不同的程序表達方式考察程序的相似性，且很少運用在回歸測試中.回歸測試前后的程序存在很多相同或相似函數(shù)，通過研究函數(shù)調(diào)用檢測程序修改前后的差異性是可行的.

近年來，在測試用例的重用以及用例生成方面的研究也較為廣泛.Mu等［14］根據(jù)變更函數(shù)和相關(guān)函數(shù)確定要測試的變更路徑，為待測試的變更路徑選擇相似函數(shù)調(diào)用路徑，并對用例進行重用.錢忠勝等［15］通過支持向量機回歸模型預(yù)測適應(yīng)度值并重用初始種群的優(yōu)秀用例，生成測試數(shù)據(jù).王曙燕等［8］利用改進的細菌覓食來生成測試數(shù)據(jù).廖志偉等［16］利用蟻群算法實現(xiàn)多路徑覆蓋測試數(shù)據(jù)生成.夏春艷等［7，9］、姚香娟等［10］、范書平等［17］通過遺傳算法得到了滿足路徑覆蓋的測試數(shù)據(jù).上面諸多啟發(fā)式算法中，遺傳算法具有良好的全局搜索能力，在測試用例生成方面普適性也較高，在求解路徑覆蓋測試數(shù)據(jù)自動生成問題中做適當改進可方便、有效地提高測試效率，得到了更廣泛的應(yīng)用.

從近幾年在測試方面的研究來看，測試用例的重用策略對提升回歸測試效率具有較高的可行性.本文利用程序變更前后的相似性來提高程序變更后測試用例重用的效率.

有效的回歸測試在不斷變化的軟件開發(fā)過程中扮演著重要的角色.Bajaj 等［18］研究發(fā)現(xiàn)自然啟發(fā)方法（如遺傳算法）已被廣泛應(yīng)用于回歸測試優(yōu)化，其目的是盡可能使用最少時間，最大限度查找故障.

在回歸測試中，變更后的新程序與前一版本的程序一般只存在較小差異.本文通過構(gòu)建函數(shù)調(diào)用圖來對變更前后程序的相似部分進行檢測，并將歷史版本程序的用例重用于新版本中，這樣，程序變更后未修改部分的目標路徑就可先被覆蓋；重用測試用例后，新版本程序變更部分的目標路徑可能未被覆蓋，利用函數(shù)影響力設(shè)計適應(yīng)度函數(shù)來篩選進化過程中符合測試需求的種群個體，使生成的用例能夠盡早地覆蓋目標路徑.

6 總結(jié)

本文提出了一種改進的基于函數(shù)影響力的相似程序間測試用例重用進化策略.實驗結(jié)果表明，本文的方法在降低進化代數(shù)、減少測試用例數(shù)量以及提高路徑覆蓋率等方面改善效果明顯，主要貢獻如下.

（1）檢測程序相似部分，為重用測試用例做準備.將歷史版本程序的測試用例運用到新程序的回歸測試中，充分利用已有測試資源，減少不必要的用例生成；對于程序有變更的部分，繼續(xù)利用歷史版本程序的測試用例，借助遺傳算法進化生成新的用例.

（2）根據(jù)函數(shù)影響力設(shè)計新的適應(yīng)度函數(shù)，促進用例進化生成.分析回歸測試前后程序的變更情況，改進適應(yīng)度函數(shù)，加速進化生成所需測試用例，使目標路徑能被迅速覆蓋，同時優(yōu)化用例集，以滿足后續(xù)回歸測試需求.

本文的策略重點在于通過函數(shù)變更等信息改進適應(yīng)度函數(shù)，并重用已知程序相似部分的用例，以提高測試效率.回歸測試中的歷史版本程序與待測程序往往具有較高的相似性，符合重用的要求.本文策略不僅適用于回歸測試，理論上講也可應(yīng)用于其他具有相同或相似結(jié)構(gòu)功能的相似程序間的測試，但其真實效果如何值得進一步研究.