傅瑞華， 李 凡， 王俊峰

(四川大學(xué)計(jì)算機(jī)學(xué)院， 成都 610065)

1 引 言

軟件測試是軟件質(zhì)量保證的核心環(huán)節(jié)， 是軟件產(chǎn)品生命周期內(nèi)質(zhì)量保證不可缺少的有效措施.證據(jù)表明，目前完整的軟件測試過程最多可占項(xiàng)目開發(fā)總成本的40%[1]，而早期及時(shí)通過軟件測試可大大降低修復(fù)軟件生命周期中的缺陷的成本[2].但目前，仍有相當(dāng)多的軟件是依靠手工編寫測試用例來進(jìn)行軟件測試.這種人工方式需保證測試人員有較多經(jīng)驗(yàn)和較高技術(shù)水平，且在有高質(zhì)量測試人員情況下依舊會(huì)花費(fèi)較高的成本(時(shí)間、人力)，也并不能完全保證測試用例的高覆蓋率和軟件質(zhì)量.因此研究測試用例自動(dòng)化生成技術(shù)成為了軟件開發(fā)行業(yè)發(fā)展的必然趨勢.

測試用例的自動(dòng)構(gòu)建可視為一個(gè)優(yōu)化問題，即如何在生成最小數(shù)量的測試用例集合的標(biāo)準(zhǔn)下，盡可能覆蓋更多的目標(biāo)，并保證測試數(shù)據(jù)分布的平衡性，使得測試用例高有效.市面上目前已經(jīng)有較多的成熟工具如Logiscope、Load Runner、Web Stress[3]等，可用于軟件測試中測試用例的自動(dòng)生成，但大多數(shù)仍然無法解決如何自動(dòng)生成高質(zhì)量測試、如何使得測試用例全面覆蓋等自動(dòng)化測試痛點(diǎn)問題，所以要實(shí)現(xiàn)真正意義上的自動(dòng)生成測試用例，仍需投入大量研究及技術(shù)支持.

軟件測試方法可大類分為黑盒測試及白盒測試，前者注重在不清楚內(nèi)部結(jié)構(gòu)和細(xì)節(jié)的情況下驗(yàn)證功能可用性；后者基于程序源碼內(nèi)部邏輯知識(shí)，并通過特定的測試覆蓋率標(biāo)準(zhǔn)如語句覆蓋率、分支覆蓋率等，來檢測編碼過程中存在的潛在錯(cuò)誤[4].

根據(jù)不同的軟件測試方法，自動(dòng)生成測試用例的常見算法可分為隨機(jī)測試方法、符號(hào)執(zhí)行方法、UML模型檢測法和基于元啟發(fā)式算法的測試用例自動(dòng)生成方法等[5].李志博等[6]提出的優(yōu)化的固定候選集算法(Fixed Sized Candidate Set，F(xiàn)SCS)在傳統(tǒng)的隨機(jī)測試算法[7]中添加了自適應(yīng)方法，通過生成多個(gè)候選測試用例數(shù)據(jù)，計(jì)算每個(gè)候選數(shù)據(jù)與已執(zhí)行用例數(shù)據(jù)集中最近測試用例數(shù)據(jù)之間的距離，并選擇出距離最大的候選數(shù)據(jù)作為下一個(gè)執(zhí)行數(shù)據(jù)，從而使得測試用例數(shù)據(jù)盡可能均勻地在輸入空間內(nèi)分布.Xiao等[8]提出一種以程序階段特征為指導(dǎo)的新型符號(hào)技術(shù)用于測試用例的自動(dòng)生成，把程序基本塊執(zhí)行次序劃分為不同的執(zhí)行階段，但此種符號(hào)執(zhí)行法易集中在局部代碼塊，導(dǎo)致其他部分的代碼無法被有效測試.Swain等[9]提出將UML行為模型轉(zhuǎn)換為圖形，通過測試場景和測試序列來自動(dòng)生成測試用例的方法.Liu等[10]提出一種通過掃描帶有嵌套循環(huán)過程的源代碼來構(gòu)造程序?qū)幽Ｐ?，并將圖層模型轉(zhuǎn)換為擴(kuò)展的正則表達(dá)式，進(jìn)而獲得測試路徑的方法.但當(dāng)程序復(fù)雜度上升(特指循環(huán)嵌套)時(shí)，該方法會(huì)導(dǎo)致測試序列爆炸問題.

元啟發(fā)式測試用例自動(dòng)生成算法是根據(jù)測試充分性標(biāo)準(zhǔn)自動(dòng)生成最優(yōu)解測試用例集，包括粒子群優(yōu)化算法[11]、遺傳算法、模擬退火算法[12]、蟻群算法等[13]，其中遺傳算法應(yīng)用最為廣泛.Bao等[14]提出的改進(jìn)遺傳方法(Improved Adaptive Genetic Algorithm，IAGA)旨在每次迭代中根據(jù)個(gè)體相似度和適應(yīng)度值的差異，動(dòng)態(tài)調(diào)整一些參數(shù)來提高早熟收斂方面的搜索性能.相比于其他算法，元啟發(fā)式算法可適用于更大規(guī)模及更高復(fù)雜度的空間，并能更敏捷地找到最優(yōu)解或近似最優(yōu)解[15].但由于算法受限于適應(yīng)度函數(shù)且依賴于初始種群，容易產(chǎn)生以下問題：算法時(shí)間復(fù)雜度過高、種群過早收斂、非全局最優(yōu)解以及局部最優(yōu)導(dǎo)致數(shù)據(jù)冗余.

為進(jìn)一步解決以上所述的元啟發(fā)式算法缺陷，并使得生成的測試用例在數(shù)量較少的情況下能夠覆蓋盡可能多的路徑，本文提出一種基于損失函數(shù)的白盒測試用例生成方法：在GA算法過程中實(shí)時(shí)判斷種群數(shù)據(jù)的分布并進(jìn)行動(dòng)態(tài)調(diào)整，并根據(jù)分布情況自適應(yīng)調(diào)整交叉變異算子，同時(shí)通過改進(jìn)后的適應(yīng)度及精英策略評估函數(shù)來對種群進(jìn)行選擇，以保證每次迭代的初始輸入種群的有效性，最大程度構(gòu)建出高覆蓋低數(shù)量高有效的最優(yōu)解測試數(shù)據(jù)集.

2 相關(guān)概念

2.1 損失函數(shù)

在機(jī)器學(xué)習(xí)模型中，單個(gè)樣本的真實(shí)值與預(yù)測值的差值稱作損失，損失值越小表示模型越貼合真實(shí)場景.其中用于計(jì)算損失值的函數(shù)被稱作損失函數(shù)，其本質(zhì)是一個(gè)用于找到場景最優(yōu)解的目的函數(shù)，可被用于度量一個(gè)模型的好壞，所以損失函數(shù)是機(jī)器學(xué)習(xí)中檢驗(yàn)?zāi)Ｐ徒Y(jié)構(gòu)風(fēng)險(xiǎn)的重要組成部分.

構(gòu)建的模型能夠通過損失函數(shù)計(jì)算出的損失值，反向去傳播更新各參數(shù)，使得模型生成的預(yù)測值能夠更好地?cái)M合真實(shí)值，從而判斷模型或者決策的好壞.當(dāng)損失值小于既定的閾值后，則可停止學(xué)習(xí)得到最優(yōu)模型.假設(shè)存在離散點(diǎn)(xi，yi)的集合，針對單一參數(shù)預(yù)測函數(shù)f(xi)=α1+α2xi，有平方誤差代價(jià)函數(shù)：

(1)

其中，N為總樣本數(shù)量；i表示第i個(gè)樣本.求解最優(yōu)值即為求解參數(shù)α1，α2，使得函數(shù)J值極小從而獲取最佳預(yù)測函數(shù)與最小誤差.

2.2 GA算法

遺傳算法已在多學(xué)科中被用作解決全局搜索優(yōu)化的方案，可形式化將該算法內(nèi)容用一個(gè)多元組進(jìn)行表示.

G=(C,F,O(α,β,γ),R(c,m,n),E)

(2)

表1 多元組符號(hào)含義

遺傳算法在每一次迭代中，通過適應(yīng)度函數(shù)選擇更優(yōu)的個(gè)體至下一代，再對種群進(jìn)行交叉或變異操作，從而產(chǎn)生新的種群.

使用遺傳算法實(shí)現(xiàn)測試用例的自動(dòng)生成可描述為:在每輪迭代過程，遺傳算法使用當(dāng)前種群(即測試用例)來驅(qū)動(dòng)被測程序的執(zhí)行，并以最大化程序路徑覆蓋率作為適應(yīng)性函數(shù)進(jìn)行計(jì)算，通過交叉變異等操作優(yōu)化有效性較低的測試用例數(shù)據(jù)，進(jìn)而產(chǎn)生下一代種群至循環(huán)結(jié)束.

2.3 動(dòng)態(tài)符號(hào)化執(zhí)行

動(dòng)態(tài)符號(hào)執(zhí)行在傳統(tǒng)符號(hào)執(zhí)行方法之上，讓具體值和符號(hào)執(zhí)行同時(shí)進(jìn)行[16].動(dòng)態(tài)符號(hào)執(zhí)行技術(shù)在生成測試用例時(shí)使用程序變量的具體值來替換復(fù)雜表達(dá)式或數(shù)據(jù)結(jié)構(gòu)中的符號(hào)變量，通過簡化路徑條件自動(dòng)生成更有效的測試用例，且具有較小的時(shí)間花銷[17].程序生成隨機(jī)數(shù)據(jù)進(jìn)行第一次執(zhí)行，并從當(dāng)前執(zhí)行路徑上的分支語句的謂詞中搜集所有符號(hào)約束，謂詞的定義如后式：P(x1,x2,…,xi)，其中xi為獨(dú)立的個(gè)體(表示不同事物或某種抽象概念)；P表示一種行為約束，刻畫出個(gè)體間的關(guān)系及性質(zhì).

之后對約束進(jìn)行修改生成新路徑的約束序列，并利用約束求解器求解出另一個(gè)可行的新輸入.通過輸入迭代產(chǎn)生變種輸入，從而觸發(fā)程序新狀態(tài)，發(fā)現(xiàn)所有可行路徑下的測試用例數(shù)據(jù).

3 算法概述

本文提出的單元測試用例自動(dòng)化生成算法整體上需達(dá)成的目標(biāo)為：保證測試用例數(shù)據(jù)高覆蓋高有效，平均覆蓋率盡可能達(dá)到α(α>=95%).在測試停止標(biāo)準(zhǔn)中基于測試用例的原則下，非功能性測試用例覆蓋率達(dá)到或超過95%允許正常結(jié)束測試[18].

圖1 種群個(gè)體惡性傾斜示意圖

保證分布平衡，分散重復(fù)路徑分支下的冗余個(gè)體，使得迭代完成后各路徑之間的種群數(shù)量差值β<=5.防止收斂速度過快導(dǎo)致的早熟以及單路徑數(shù)據(jù)爆炸(如圖1)等問題缺陷.圖1中Bi為分支Li為語句，虛線框中的部分代表聚集了較多的種群個(gè)體，因此在迭代中測試重點(diǎn)會(huì)偏向根節(jié)點(diǎn)B1的右子樹路徑上，從而導(dǎo)致失衡，造成最終種群迭代的惡性結(jié)果效應(yīng).

3.1 測試用例自動(dòng)生成模型框架

本文提出的單元測試用例自動(dòng)化生成算法(LFGA)模型如圖2所示.整體方法中含有程序分析、GA優(yōu)化、最優(yōu)種群集合評估等主要模塊，對初始測試程序進(jìn)行插樁測試，并于中間過程引入損失函數(shù)驗(yàn)證，通過及時(shí)判斷迭代各種群個(gè)體是否符合分支預(yù)期，動(dòng)態(tài)根據(jù)路徑前序分支覆蓋情況調(diào)整種群在程序路徑樹的分布，執(zhí)行時(shí)無需過度依賴于初始種群，最后以適當(dāng)收斂速度及迭代次數(shù)來確定最優(yōu)數(shù)據(jù)集，增強(qiáng)此種問題場景下通用模型的整體魯棒性及種群個(gè)體耦合依賴性，并以此可推斷至較為復(fù)雜軟件的用例生成.

圖2 基于損失函數(shù)的測試用例生成模型Fig.2 Test case generation model based on loss function

3.2 程序分析

模型中程序分析采用靜態(tài)預(yù)分析方式，抽取程序片段中的關(guān)鍵信息包括分支節(jié)點(diǎn)、參數(shù)集合、輸入域范圍等，以Java語言為例，借助ASTParser類遍歷形成DOT類型文件數(shù)據(jù)，再利用正則從節(jié)點(diǎn)語句中獲取具體的輸入域范圍，具體DOT數(shù)據(jù)類型如表2所示.

表2 DOT文件數(shù)據(jù)結(jié)構(gòu)字段

生成的dot文件同時(shí)包含了各個(gè)id之間的指向信息，能夠表示各分支之間的層級關(guān)系，訪問者根據(jù)dot文件數(shù)據(jù)中的節(jié)點(diǎn)語句信息可得到分支集合T={t1,t2,...,tn}.給定路徑集合P={p1,p2,...,pn}，其中pi∈T，且pi代表的子集沒有重復(fù)，所有子集的并集涵蓋程序整個(gè)分支集合;若存在pm∈pn則僅保留最長路徑子集.

將所有路徑信息進(jìn)行優(yōu)化后，執(zhí)行統(tǒng)一插樁，把測試數(shù)據(jù)集映射至路徑檢測及定義域初值數(shù)據(jù)集.路徑檢測數(shù)據(jù)集合在分支損失函數(shù)驗(yàn)證階段將被用于控制種群在各路徑上的分布，定義域初始隨機(jī)集合將用于種群(測試用例)初始值的生成.

3.3 初值隨機(jī)生成優(yōu)化

關(guān)于種群迭代演化的測試，前期輸入域有效性間接性確定了后期迭代時(shí)間長短及收斂速度的快慢.之前經(jīng)過對代碼片段的靜態(tài)分析并確定了類的分支行為，在DOT數(shù)據(jù)集合上進(jìn)行二次正則精簡來獲取每一個(gè)分支中可能存在的參考值以及其對應(yīng)范圍符號(hào)，包括：>、<、=、&、！等，然后以預(yù)設(shè)數(shù)量的種群個(gè)體數(shù)在變量參考范圍內(nèi)隨機(jī)生成初始種群，組成由范圍內(nèi)隨機(jī)測試用例組成的測試套件，再用于之后迭代.

由于并非所有程度控制條件中含有明確變量信息(如:無數(shù)值僅有等式約束關(guān)系)，因此考慮符號(hào)化執(zhí)行思想，把輸入變?yōu)榉?hào)值來得到讓特定代碼片段區(qū)域執(zhí)行的輸入組合值或關(guān)系，以圖3為例，獲取路徑分支truefalse序列的約束關(guān)系，，根據(jù)執(zhí)行樹左右子樹進(jìn)行初值的等式約束關(guān)系集取值，從而適應(yīng)于無明確參考值下的種群初值生成.改分支集合序列T中每項(xiàng)為ti-0和ti-1，則ti-0代表true，ti-1代表false，作為路徑集合的存儲(chǔ)信息.

圖3 執(zhí)行樹信息存儲(chǔ)示例Fig.3 Execution tree information store

獲取到各路徑下的參考值范圍或變量狀態(tài)關(guān)系后，將上述變量信息存儲(chǔ)至對應(yīng)分支的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)取值范圍對各路徑設(shè)置相應(yīng)概率閾值，便于在分支損失函數(shù)中進(jìn)行分支碰撞檢測優(yōu)化.

3.4 分支損失函數(shù)驗(yàn)證

在最優(yōu)種群集合評估模塊中，為確保數(shù)據(jù)集至少覆蓋一次決策點(diǎn)的每個(gè)條件的所有可能結(jié)果(即取真、取假分支)，本文提出一種通過分支損失函數(shù)實(shí)時(shí)調(diào)整后序種群分布的驗(yàn)證算法，其中分支損失函數(shù)在流程中作為用于找到最優(yōu)解集合的目的函數(shù)，控制選擇及交叉變異方向，從而增強(qiáng)測試?yán)龜?shù)據(jù)之間的公平性、友好性，流程如圖4所示.

在進(jìn)行整體種群評估后開啟分支損失函數(shù)的驗(yàn)證，貫穿于每代個(gè)體的選擇丟棄和后續(xù)變異的突變方向等，盡可能地去掉某分支條件下的冗余測試數(shù)據(jù)，主要損失函數(shù)的實(shí)現(xiàn)由以下兩部分構(gòu)成.

圖4 分支損失函數(shù)驗(yàn)證流程Fig.4 Branch loss function verification process

第一項(xiàng)：用于迭代選擇過程中判斷個(gè)體累計(jì)是否符合分支覆蓋預(yù)期.由于前序步驟中進(jìn)行了正則切割及插樁等過程，程序能夠獲取存儲(chǔ)的分支數(shù)據(jù)結(jié)構(gòu)信息，包括分支id、分支所含變量范圍及關(guān)系、分支概率閾值等.當(dāng)進(jìn)入某分支的個(gè)體數(shù)占比超過設(shè)定的該分支概率閾值則選擇舍棄，重新隨機(jī)選取其他分支進(jìn)行參考值范圍內(nèi)的數(shù)據(jù)隨機(jī)生成以補(bǔ)位，再結(jié)合精英個(gè)體選擇策略下的剩余種群形成新一代種群數(shù)據(jù)的有效輸入;第二項(xiàng)：提供個(gè)體交叉變異的趨勢判斷.由于適應(yīng)度函數(shù)的設(shè)計(jì)易使測試數(shù)據(jù)后續(xù)匯集在已生成數(shù)據(jù)的路徑上(即概率閾值更大)，考慮在經(jīng)過選擇階段后，通過累計(jì)各路徑個(gè)體，選取數(shù)目相對較多和較少的分支種群集合進(jìn)行交叉變異.算法中的變量含義對應(yīng)關(guān)系如表3所示.

表3 算法變量含義對照表

整體算法思路過程偽代碼如算法1所示.

算法1分支損失函數(shù)驗(yàn)證

1) procedure Branch Cost(，)

2) Pretreatment:T&P←dot類型數(shù)據(jù)

3) Initializa:PopList←Referencevaluerange

4) Evaluate: the primary population

5) whilei< maxGeneration do

6) Select:NewPopList←f(xi)評估

7) while in Function(CostBranch) life

circle do

8)PXover& PMutation: 自適應(yīng)改變

9) if reachedPopListend

10) end while

11) 使用JUnit計(jì)算數(shù)據(jù)覆蓋率

12) if test data optimal←cov(%) max

13) end while

14) 輸出最優(yōu)解集合

15) end procedure

3.5 自適應(yīng)算子設(shè)計(jì)

采取常規(guī)遺傳算法中的策略，交叉函數(shù)對選定的兩個(gè)父級中的基因進(jìn)行交換，變異函數(shù)實(shí)現(xiàn)采用的單點(diǎn)交叉.通常在覆蓋率高的測試用例數(shù)據(jù)上修改某一個(gè)參數(shù)值或用高覆蓋率測試用例中的某幾位參考數(shù)據(jù)替換前一階段新生成的測試用數(shù)據(jù)，往往能夠在適當(dāng)速度范圍內(nèi)加快收斂改善結(jié)果，有效加強(qiáng)進(jìn)化性能[19].

當(dāng)連續(xù)碰撞某分支次數(shù)累計(jì)達(dá)到設(shè)定閾值，認(rèn)為在此分支參考值范圍內(nèi)已經(jīng)設(shè)定了足夠的測試用例，為避免出現(xiàn)過度收斂導(dǎo)致分支不平衡現(xiàn)象，動(dòng)態(tài)地調(diào)整交叉變異算子.根據(jù)測試數(shù)據(jù)累計(jì)分支碰撞閾值，動(dòng)態(tài)改變交叉變異算子的取值.式(3)和式(4)分別表示變異和交叉算子的調(diào)整方式.

(3)

(4)

式中，fmax代表相對適應(yīng)度最大的個(gè)體；fi代表待變異個(gè)體(適應(yīng)度較小的測試用例)的相對適應(yīng)度；favg代表種群個(gè)體平均相對適應(yīng)度.在遺傳算法中Pc，Pm取值范圍一般為[0.25，0.99)及[0.001，0.1)[20]，此處公式中k1及k2、k3及k4，通過隨機(jī)函數(shù)分別取[0.25，0.99)及[0.001，0.1)區(qū)間內(nèi)的值.

相對適應(yīng)度越小的個(gè)體表示進(jìn)入其對應(yīng)分支的概率越大越容易進(jìn)入，相對較大的變異算子在此種情況下更能促進(jìn)進(jìn)入冗余分支測試數(shù)據(jù)的變異.

對于分支概率最大的情況下，fi必定大于favg，使得整體Pm增加，從而對應(yīng)個(gè)體變異的概率增加；對于進(jìn)入分支難的個(gè)體，應(yīng)使Pm變小，從而使這個(gè)個(gè)體更不容易變異順利進(jìn)入下一代.

3.6 GA優(yōu)化模塊

(1) 適應(yīng)度函數(shù)設(shè)計(jì).根據(jù)個(gè)體分支覆蓋情況和所有種群分支覆蓋情況進(jìn)行個(gè)體的適應(yīng)度計(jì)算，每次進(jìn)行更改時(shí)需重新編譯代碼.越易覆蓋的路徑會(huì)有越多的測試數(shù)據(jù)集，適應(yīng)度函數(shù)見式(5).

(5)

其中，N代表種群待選擇個(gè)體總數(shù)；ui為路徑集合個(gè)體pi所含有的測試數(shù)據(jù)數(shù)目；umax為測試用例在pi路徑下達(dá)到理想平衡狀態(tài)下的個(gè)數(shù)，越易被覆蓋的路徑會(huì)有更多的測試數(shù)據(jù)集，對應(yīng)個(gè)體適應(yīng)度值越低，在擇優(yōu)選擇中表現(xiàn)為更劣勢個(gè)體.

(2) 精英策略設(shè)計(jì).結(jié)合分支驗(yàn)證機(jī)制之前，本文先采用輪盤賭個(gè)體選擇策略，將中間步驟得到的最優(yōu)解個(gè)體進(jìn)行保留.結(jié)合分支損失函數(shù)驗(yàn)證后能在確保當(dāng)代種群中最佳成員組作為二代種群的初始有效輸入的條件下動(dòng)態(tài)調(diào)整其余測試數(shù)據(jù)的平衡性，從而防止由遺傳算法過度收斂導(dǎo)致的數(shù)據(jù)極端不平衡.輪盤賭策略對優(yōu)劣個(gè)體的相對適應(yīng)度計(jì)算式如式(6).

rf(i)=f(i)/∑f(i)，i≤N

(6)

式中， ∑f(i)表示當(dāng)前適應(yīng)度的總和.個(gè)體相對適應(yīng)度rf(i)越高表示個(gè)體更優(yōu)良，將保留至分支損失函數(shù)執(zhí)行階段.

4 實(shí)驗(yàn)與結(jié)果

本文實(shí)驗(yàn)選擇了5種不同復(fù)雜度的被測程序來進(jìn)行所提出方法的評估，并與其他方法和工具進(jìn)行橫向?qū)Ρ葘?shí)驗(yàn)，算法實(shí)現(xiàn)采用Intellij IDEA軟件環(huán)境，開源測試框架JUnit輔助進(jìn)行測試結(jié)果優(yōu)劣分析.實(shí)驗(yàn)評估標(biāo)準(zhǔn)以回答以下兩個(gè)問題：Q1: 本文提出方法是否能夠優(yōu)化數(shù)據(jù)收斂結(jié)果，并提高總體覆蓋率？Q2: 與其他方法相比，本文提出方法是否能夠在相同規(guī)模的測試數(shù)據(jù)集合下，實(shí)現(xiàn)更高的覆蓋率結(jié)果？

4.1 實(shí)驗(yàn)過程

實(shí)驗(yàn)測試采用軟件測試中的經(jīng)典模型Triangle， Next Date， GCD， premium， decision[21]等作為被測程序來驗(yàn)證所提出方法的可行性(如表4).

表4 測試模型信息

本文提出的方法記為LFGA，隨機(jī)算法記為RA，蟻群算法記為ACA，標(biāo)準(zhǔn)遺傳算法記為SGA，開源工具Evosuite中的改進(jìn)遺傳算法記為IGA.Evosuite[22]基于傳統(tǒng)GA算法，然后迭代地使用變異和交叉等遺傳算子來進(jìn)化.

通過使用不同的算法對上述5種待測程序模型進(jìn)行單元測試用例的自動(dòng)生成，并通過Junit進(jìn)行測試用例數(shù)據(jù)的覆蓋率計(jì)算輸出及后續(xù)結(jié)果對比.實(shí)驗(yàn)種群規(guī)模保持為50，最大迭代次數(shù)設(shè)上限500，自適應(yīng)遺傳操作中設(shè)置單點(diǎn)交叉概率上限0.9;變異概率上限0.1.實(shí)驗(yàn)中使用的評估指標(biāo)是在預(yù)先確定的獨(dú)立運(yùn)行次數(shù)上實(shí)現(xiàn)的平均覆蓋率.通常迭代停止機(jī)制的判斷方式為兩種:人為設(shè)定及數(shù)據(jù)收斂趨勢穩(wěn)定或陷入局部最優(yōu)解.

4.2 實(shí)驗(yàn)結(jié)果

通過使用不同算法對同種程序測試模型進(jìn)行測試，生成數(shù)據(jù)的路徑覆蓋率結(jié)果數(shù)據(jù)如圖5所示，其中cov表示多次實(shí)驗(yàn)累計(jì)下的覆蓋率結(jié)果均值.

表5為在每種模型經(jīng)過40輪次實(shí)驗(yàn)后，程序輸出分布結(jié)果趨勢穩(wěn)定情況下的平均迭代次數(shù)(去除最優(yōu)及最壞結(jié)果以盡量降低偶然事件誤差).注:程序輸出的最優(yōu)結(jié)果不代表數(shù)據(jù)一定可用，僅可通過此數(shù)據(jù)判斷種群收斂情況.

表5 程序穩(wěn)定解下的遺傳代數(shù)

圖5 不同方法下的覆蓋率結(jié)果Fig.5 Coverage results under different methods

為了驗(yàn)證被測程序的測試數(shù)據(jù)生成在改進(jìn)方法下的有效性，繪制了在本文所提出的思路下，種群數(shù)據(jù)的收斂趨勢(以Triangle為例)，如圖6所示，并以標(biāo)準(zhǔn)遺傳算法SGA下的過程中種群數(shù)據(jù)分布趨勢作為對照.圖中橫坐標(biāo)表示種群的迭代次數(shù)，縱坐標(biāo)表示為種群個(gè)數(shù)，其中每一條折線表示：一條路徑分支上的種群個(gè)數(shù)在迭代過程中的變化.

以含有4條分支路徑的Triangle程序?yàn)槔?，兩幅圖中從上到下的折線依次代表4條路徑上種群數(shù)量的變化.經(jīng)過20余次迭代后，在圖7的SGA算法中，每條路徑上的種群數(shù)量變化波動(dòng)較大且無明顯收斂趨勢；而在圖6的LFGA算法中，每條路徑上的種群數(shù)量變化趨于平緩，且各路徑之間的分布的種群數(shù)量差值也呈現(xiàn)越來越小的趨勢.

圖6 LFGA種群收斂趨勢(以Triangle為例)Fig.6 Convergence trend of LFGA population (take Triangle as an example)

圖7 SGA種群分布圖(以Triangle為例)Fig.7 SGA population distribution trend (take Triangle as an example)

4.3 數(shù)據(jù)分析

根據(jù)實(shí)驗(yàn)結(jié)果，結(jié)合第4節(jié)開篇，Q1和Q2數(shù)據(jù)分析情況如下.Q1:從表5展現(xiàn)的數(shù)據(jù)中可看出傳統(tǒng)方式生成數(shù)據(jù)雖然經(jīng)過較少的迭代總數(shù)，但測試數(shù)據(jù)可用性遠(yuǎn)遠(yuǎn)低于本文提出的方法，說明傳統(tǒng)算法使得種群數(shù)據(jù)過快收斂或陷入局部最優(yōu)中，從而通過本文中的分支損失函數(shù)驗(yàn)證方式，能夠較好地讓種群數(shù)據(jù)分布得到有效的篩選，并通過圖5生成測試數(shù)據(jù)的路徑分布圖可看出，整體數(shù)據(jù)以適當(dāng)速度進(jìn)行較穩(wěn)定的收斂，最終達(dá)成最優(yōu)解較均勻覆蓋目標(biāo)路徑目標(biāo).Q2: 橫向?qū)Ρ确绞较氯绫?數(shù)據(jù)，本文方法生成數(shù)據(jù)對于幾個(gè)測試程序來講生成了較好的覆蓋率且高于SGA算法，數(shù)據(jù)可用性更高，同時(shí)Evosuite開源工具數(shù)據(jù)覆蓋率比較穩(wěn)定可作為本文方法參考目標(biāo)覆蓋率，LFGA算法中的覆蓋率與Evosuite數(shù)據(jù)覆蓋率也更為接近，說明文本所提出損失函數(shù)方法適用于測試數(shù)據(jù)的自動(dòng)生成.

5 結(jié) 論

本文提出了一種基于損失函數(shù)的方法，目的是通過判斷算法過程中平衡性變化，改進(jìn)種群適應(yīng)度及精英策略評估方式，并利用分支信息優(yōu)化自適應(yīng)交叉變異算子，自動(dòng)完成數(shù)據(jù)收斂過程，生成最小高覆蓋有效測試用例集.經(jīng)過大量實(shí)驗(yàn)及數(shù)據(jù)表明，本文方法能夠有效收斂種群，增強(qiáng)算法全局尋優(yōu)能力，并較好解決初值依賴、收斂早熟、局部尋優(yōu)能力滯后等傳統(tǒng)缺陷，盡可能地提升搜索效率及數(shù)據(jù)有效率，將測試覆蓋度達(dá)到一個(gè)滿意的值，對快速生成滿足測試要求的數(shù)據(jù)有著重要意義.由于本文所提算法能夠通過判斷用例數(shù)據(jù)分布情況來自動(dòng)完成數(shù)據(jù)收斂的過程，后續(xù)引入神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練是值得嘗試和研究的.