林亞娜

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

0 引言

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

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

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

1 改進(jìn)遺傳算法生成測試用例的方法

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)路徑集合，首先定義兩個(gè)概念。

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

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

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

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

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

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

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

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

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

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

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

1.3 改進(jìn)的遺傳算法生成測試用例方法

改進(jìn)的遺傳算法流程圖如圖1所示：

圖1 改進(jìn)遺傳算法的流程圖

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

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

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

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

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

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

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

2 實(shí)驗(yàn)仿真分析

2.1 實(shí)驗(yàn)準(zhǔn)備

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

表1 待測程序基本信息

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

表2 實(shí)驗(yàn)參數(shù)設(shè)置

2.2 算法可行性驗(yàn)證

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

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

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

3 結(jié)束語

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

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