林亞娜

(福州理工學(xué)院，福建 福州 350506)

0 引言

軟件測試中的路徑覆蓋測試是在單元測試階段比較常用的方法，測試用例的自動生成可以提高軟件測試效率，路徑覆蓋是一種重要的覆蓋標(biāo)準(zhǔn)，其目的是尋找覆蓋所有可能路徑的測試用例，進而發(fā)現(xiàn)軟件中存在的缺陷[1]。尋找覆蓋路徑的測試用例可抽象為尋求最優(yōu)路徑的問題，遺傳算法是目前用于測試用例自動生成的有效的常用方法，遺傳算法在解決尋找最優(yōu)路徑問題中有一定優(yōu)勢。

Ahmed等[2]于2008 年首次提出基于遺傳算法（Genetic Algorithm）多路徑測試數(shù)據(jù)進化生成的方法，提出由層接近度和分支距離兩部分構(gòu)成適應(yīng)度函數(shù)，這種方法雖然能夠進化生成測試數(shù)據(jù)，但是計算量較大，效率不高。鞏敦衛(wèi)等[3]提出一種用于多路徑覆蓋的測試數(shù)據(jù)生成方法，設(shè)計的適應(yīng)度函數(shù)綜合考慮了個體穿越路徑與目標(biāo)路徑的匹配程度，該方法可以通過較小的計算量高效地生成測試數(shù)據(jù)，而在匹配目標(biāo)路徑的時候沒有考慮不可達(dá)路徑的問題。范書平等[4]提出利用種群中個體穿越程序分支的均衡度調(diào)整進化過程，使得對程序均衡度影響大的個體具有更多機會參與到后續(xù)進化中，提高測試數(shù)據(jù)的生成效率。夏春艷等[5]提出基于否定選擇遺傳算法的路徑覆蓋測試數(shù)據(jù)生成方法，動態(tài)優(yōu)化遺傳算法的種群數(shù)據(jù)，減少冗余數(shù)據(jù)生成。黃陳輝[6]等提出一種混沌遺傳算法進行測試用例的進化生成，運用反向?qū)W習(xí)策略初始化種群，與簡單遺傳算法比較結(jié)果表明，這種方法可以提升測試用例生成方面的全局尋找最優(yōu)解能力。

本文所提方法的核心由兩部分組成：①通過分析被測程序的流程圖得到可能的目標(biāo)路徑集合，過濾不可達(dá)路徑以便節(jié)省進化數(shù)據(jù)匹配的資源成本；②對遺傳算法的適應(yīng)度函數(shù)進行改進，通過分析分支走向以及加路徑權(quán)重的方式設(shè)計新的適應(yīng)度函數(shù)，最后利用矩陣計算方法計算出適應(yīng)度。當(dāng)遺傳算法生成的測試數(shù)據(jù)路徑與目標(biāo)路徑不匹配時，通過分析路徑走向以及路徑加權(quán)的計算，可以拉大測試數(shù)據(jù)路徑與目標(biāo)路徑的差距，加速算法收斂速度，提高生成可用測試用例的效率。

1 改進遺傳算法生成測試用例的方法

1.1 路徑的構(gòu)建

路徑的構(gòu)建是通過分析程序流程圖，程序結(jié)構(gòu)基本分三類：順序結(jié)構(gòu)、選擇（分支）結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。其中順序結(jié)構(gòu)的程序不涉及路徑變化，在構(gòu)建路徑過程中無需區(qū)分這類結(jié)構(gòu)；選擇（分支）結(jié)構(gòu)和循環(huán)結(jié)構(gòu)是區(qū)分路徑的關(guān)鍵，循環(huán)結(jié)構(gòu)采用Z 路徑覆蓋原則[7]，簡化了循環(huán)的次數(shù)，只考慮循環(huán)1 次和0 次兩種情況。本文主要針對這兩類結(jié)構(gòu)分析目標(biāo)路徑集合，首先定義兩個概念。

定義1路徑中節(jié)點的方向系數(shù)α，表示程序結(jié)構(gòu)的走向，為1或-1。

針對選擇（分支）結(jié)構(gòu)：

定義2路徑中的節(jié)點權(quán)值β，表示每個節(jié)點在當(dāng)前路徑中所占的權(quán)重，越靠近起始點的節(jié)點，其影響越大，進而權(quán)重越大。假設(shè)當(dāng)前路徑有n 個節(jié)點，第i個節(jié)點的權(quán)值為：

權(quán)值按照節(jié)點個數(shù)降序排列，即第1 個節(jié)點的權(quán)值β1為n，第2 個節(jié)點權(quán)值β2為n-1，以此類推。將路徑集合表示為一個n行m列的矩陣P，P[i][j]（i=1,2,...,n；j=1,2,...,m）表示第i 條路徑中第j 個節(jié)點所對應(yīng)的值，該值由定義1 的節(jié)點方向系數(shù)與定義2 的節(jié)點權(quán)值相乘組成。

根據(jù)公式⑷可以構(gòu)建出被測程序中所有目標(biāo)路徑的矩陣P[i][j]以及進化生成的測試數(shù)據(jù)實際經(jīng)過的路徑PA[i][j]。

1.2 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)主要的任務(wù)是對比實際路徑與目標(biāo)路徑的差異。差異越小，證明實際數(shù)據(jù)路徑與目標(biāo)路徑越匹配，適應(yīng)度值越接近1。目標(biāo)路徑應(yīng)是一個集合，首先排除目標(biāo)路徑集合中分支點數(shù)與實際路徑分支點數(shù)不同的路徑，分支不同必然不可能匹配；其次，用實際路徑分別與目標(biāo)路徑集合中的路徑做匹配并計算適應(yīng)度，如得到完全匹配的數(shù)據(jù)，則保存當(dāng)前的測試數(shù)據(jù)，并將已經(jīng)匹配的目標(biāo)路徑從目標(biāo)路徑集合中刪除，將該條實際路徑的適應(yīng)度設(shè)置為1；如未完全匹配，則通過計算實際路徑與各個目標(biāo)路徑的適應(yīng)度，計算其平均值即為該條實際路徑的適應(yīng)度。

利用路徑的構(gòu)建方法，將第t 代測試數(shù)據(jù)代入被測程序，通過程序插樁構(gòu)建出第t 代測試數(shù)據(jù)的實際路徑，即1行r列矩陣PA,r表示該條實際路徑經(jīng)過的分支點個數(shù)；目標(biāo)路徑表示為矩陣P，其中P[i]表示目標(biāo)路徑集合中的第i條路徑構(gòu)建的矩陣，為1行r列矩陣，通過矩陣計算得到第t 代測試數(shù)據(jù)實際路徑的適應(yīng)度函數(shù)：

其中，n表示目標(biāo)路徑集合過濾后的路徑條數(shù)，過濾指目標(biāo)路徑集合中去掉不可達(dá)路徑及路徑中節(jié)點數(shù)與實際路徑不一致的路徑，PA表示實際路徑矩陣，P 表示過濾后的目標(biāo)路徑矩陣，i 指P 中的第i 條路徑，T 上標(biāo)表示矩陣的轉(zhuǎn)置。式⑸得到的結(jié)果為一個自然數(shù)，為了便于比較，將結(jié)果限定在一個范圍，做歸一化處理，將式⑸得到的結(jié)果分布到實際路徑矩陣的秩的平方中，將適應(yīng)度值限定在[-1，1]閉區(qū)間內(nèi)，最終得到歸一化后的適應(yīng)度函數(shù)如下：

適應(yīng)度函數(shù)的設(shè)計綜合考慮了不匹配節(jié)點出現(xiàn)的前后位置，不匹配出現(xiàn)的越靠前，則代表實際路徑與目標(biāo)路徑集合中的路徑不匹配程度越大，經(jīng)過公式⑹計算得到的適應(yīng)度值越接近-1，表示該數(shù)據(jù)匹配程度低，在遺傳算法中被選擇為親代數(shù)據(jù)的幾率越小。將路徑抽象為矩陣，經(jīng)過矩陣計算，根據(jù)不匹配節(jié)點出現(xiàn)的位置，計算適應(yīng)度，能夠體現(xiàn)路徑之間的匹配程度，通過式⑴、式⑵方向系數(shù)和式⑶權(quán)值的設(shè)計，可適當(dāng)拉大匹配路徑的差異，加速算法收斂。

預(yù)制裝配式建筑施工技術(shù)及其配套裝備的創(chuàng)新研究…………………………………………………… 王潤華（10-203）

1.3 改進的遺傳算法生成測試用例方法

改進的遺傳算法流程圖如圖1所示：

圖1 改進遺傳算法的流程圖

算法的實現(xiàn)步驟共分六步：

步驟1在待測程序中插樁，構(gòu)建出目標(biāo)路徑集合，判斷分支節(jié)點處是否存在相關(guān)性因素，找出不可達(dá)路徑并從目標(biāo)路徑集合中刪除，構(gòu)建最終的目標(biāo)路徑矩陣；

步驟2通過遺傳算法初始化種群，生成第一代種群的測試數(shù)據(jù)，代入測試數(shù)據(jù)執(zhí)行被測程序，獲取每條測試數(shù)據(jù)的實際執(zhí)行路徑；

步驟3評價實際路徑與目標(biāo)路徑的匹配程度，如有完全匹配的測試數(shù)據(jù)，則保留該條數(shù)據(jù)作為測試用例，并將匹配上的目標(biāo)路徑從目標(biāo)路徑集合中刪除；如未完全匹配，根據(jù)公式⑸、⑹計算個體的適應(yīng)度進而計算第一代測試數(shù)據(jù)的整體適應(yīng)度；

步驟4判斷遺傳終止條件是否滿足，如已經(jīng)滿足轉(zhuǎn)至步驟6，如未滿足終止條件，則繼續(xù)執(zhí)行步驟5；遺傳終止條件為當(dāng)前目標(biāo)路徑集合中已無待匹配路徑，表示所有與目標(biāo)路徑匹配的測試用例均已經(jīng)生成或達(dá)到指定的進化代數(shù)上限；

步驟5根據(jù)初始化設(shè)置的交叉率、變異率執(zhí)行遺傳算法中的交叉、變異程序，再次計算整體適應(yīng)度；生成下一代種群進化的測試數(shù)據(jù)，跳轉(zhuǎn)回步驟4，再次判斷遺傳條件是否終止；

步驟6終止遺傳算法，輸出生成的測試數(shù)據(jù)。

2 實驗仿真分析

2.1 實驗準(zhǔn)備

為了評價本文提出的改進的遺傳算法的有效性以及性能，選取四個基本測試進行測試，被測程序的基本信息如表1所示。

表1 待測程序基本信息

本文改進的遺傳算法采用輪盤賭選擇交叉的親代，單點交叉、單點變異進而生成下一代測試數(shù)據(jù)。每次實驗的參數(shù)設(shè)置如表2所示。實驗運行環(huán)境基本配置為2.3GHz 四核 Inter（R）i5-6300HQ 處理器，8GB 內(nèi)存，Windows10 操作系統(tǒng)，JVM 版本1.8.0_121，開發(fā)語言為Java語言，集成平臺為Eclipse2019-09。

表2 實驗參數(shù)設(shè)置

2.2 算法可行性驗證

本文算法與隨機算法做比較，分別針對四個基本測試程序構(gòu)建路徑并生成測試用例。對生成數(shù)據(jù)的覆蓋率、生成的測試用例數(shù)量、迭代的次數(shù)以及生成測試數(shù)據(jù)的時間等幾個關(guān)鍵指標(biāo)進行對比，由于算法存在不確定性，每個算法得到的測試數(shù)據(jù)為該算法執(zhí)行100次的平均結(jié)果，詳細(xì)數(shù)據(jù)如表3所示。

表3 改進的遺傳算法與隨機算法針對四組待測程序執(zhí)行結(jié)果對比

通過分析實驗結(jié)果可得，在程序簡單、分支較少的程序中，本文算法與隨機算法的覆蓋率、生成測試用例個數(shù)與運行時間相差無幾，但是在分支數(shù)較多的程序中，比如在判斷三角形Angles 程序中，在生成測試用例數(shù)相同的情況下，本文算法的覆蓋率為100%，隨機算法為91%，本文算法覆蓋率高于隨機算法。在獲取下一天NextDate 程序中，本文算法生成的測試用例個數(shù)少于隨機算法，在此情況下，本文算法的覆蓋率仍高于隨機算法。當(dāng)程序分支數(shù)變多時，在生成測試用例數(shù)量相同時，改進的算法覆蓋率仍可保持100%覆蓋路徑。在復(fù)雜程序中，改機的算法與隨機算法相比，覆蓋率提升4%～9%。通過本文改進遺傳算法生成數(shù)據(jù)，可以針對待測程序的具體情況，調(diào)整交叉率及變異率，改善算法的收斂速度，這是隨機算法無法做到的。

3 結(jié)束語

自動生成測試用例是自動化測試研究中的核心環(huán)節(jié)，本文將測試用例自動生成的問題抽象為尋求最優(yōu)解問題，通過改進遺傳算法的適應(yīng)度函數(shù)計算方法加快遺傳算法收斂，與隨機算法相比，能夠更快速的尋找到最適合的測試數(shù)據(jù)。設(shè)計適應(yīng)度函數(shù)，拉大不匹配路徑之間的差距，從而快速獲得符合條件的測試數(shù)據(jù)，減少冗余測試數(shù)據(jù)的生成，提高測試覆蓋率。

將本文算法應(yīng)用到基礎(chǔ)測試代碼中實驗，經(jīng)過與隨機算法對比，得出本文算法在測試覆蓋率和進化代數(shù)方面具有一定的優(yōu)越性。在過濾不可達(dá)路徑的過程中，尚未使用程序自動化完成，未來將針對這一步驟做進一步研究。