基于啟發(fā)式遺傳算法的模糊測(cè)試樣本集優(yōu)化方案

王志華，王浩帆，程漫漫

（鄭州大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，鄭州 450002）

隨著信息與通信技術(shù)的快速發(fā)展，信息技術(shù)改變了人們的生活方式。然而，伴隨而來的網(wǎng)絡(luò)與信息安全問題也逐漸引起了社會(huì)各個(gè)領(lǐng)域的廣泛關(guān)注。

軟件漏洞挖掘技術(shù)［1］在信息安全領(lǐng)域中占據(jù)了重要地位。模糊測(cè)試［2］則是漏洞挖掘中較為有效的方法之一，其是一種基于缺陷注入的自動(dòng)化軟件測(cè)試技術(shù)，主要依賴于不斷輸入非預(yù)期的數(shù)據(jù)并對(duì)數(shù)據(jù)進(jìn)行監(jiān)控和觀測(cè)的方式發(fā)現(xiàn)軟件是否會(huì)存在異常。傳統(tǒng)的模糊測(cè)試技術(shù)并沒有對(duì)初始樣本集進(jìn)行處理，而是直接進(jìn)行變異分析。樣本的重復(fù)性會(huì)產(chǎn)生大量代碼率低且無用的測(cè)試用例，從而降低了模糊測(cè)試的效率。如何改進(jìn)模糊測(cè)試的缺陷已經(jīng)成為當(dāng)前研究熱點(diǎn)?？紤]模糊測(cè)試樣本集的特點(diǎn)，可以對(duì)其進(jìn)行優(yōu)化，從而精簡(jiǎn)樣本集的數(shù)量，提高樣本集的質(zhì)量，進(jìn)而提升模糊測(cè)試的效率。因此，研究模糊測(cè)試樣本集的高質(zhì)量性精簡(jiǎn)問題，具有很大的理論意義和工程應(yīng)用價(jià)值。本文對(duì)模糊測(cè)試樣本集精簡(jiǎn)進(jìn)行了研究，借助0-1矩陣，在遺傳算法的基礎(chǔ)上進(jìn)行改進(jìn)，將貪心逼近算法與遺傳算法結(jié)合，提出了基于啟發(fā)式遺傳算法的樣本集精簡(jiǎn)解決方案。實(shí)驗(yàn)結(jié)果表明，本文方法是有效的。

1 相關(guān)工作

近年來，眾多學(xué)者從集合覆蓋、機(jī)器學(xué)習(xí)、遺傳算法等角度圍繞模糊測(cè)試樣本集的精簡(jiǎn)問題開展了大量的研究工作。馬金鑫等［3］設(shè)計(jì)了一種貪心逼近的求解算法來優(yōu)化模糊測(cè)試的輸入樣本集，在樣本集覆蓋率不變的前提下求解獲取最小樣本集合；Bhme等［4］把模糊測(cè)試問題建模為Markov模型，并采用特定的策略引導(dǎo)AFL優(yōu)先選擇低頻路徑和變異頻率低的文件作為文件進(jìn)行變異；隨后Bhme等［5］提出采用模擬退火算法對(duì)能逼近特定目標(biāo)位置的測(cè)試輸入分配更高的能量，并優(yōu)先選取高能量種子文件進(jìn)行變異；Wang等［6］提出了一種質(zhì)量感知的測(cè)試用例優(yōu)先級(jí)技術(shù)，優(yōu)先輸入高質(zhì)量的種子，直接定義獲取高質(zhì)量的種子；唐梟［7］利用污點(diǎn)分析和其他技術(shù)來獲取數(shù)據(jù)的執(zhí)行路徑，對(duì)代碼覆蓋率相關(guān)字段進(jìn)行基因編碼，并執(zhí)行遺傳算法的選擇變異過程，對(duì)危險(xiǎn)操作相關(guān)字段執(zhí)行邊界值賦值，產(chǎn)生新的測(cè)試用例。

在實(shí)際處理過程中，采用集合覆蓋技術(shù)解決樣本集的精簡(jiǎn)或篩選時(shí)，精確算法能夠找到集合覆蓋問題的最優(yōu)解，近似算法能夠取得有質(zhì)量保證的解，但其求解速度較慢，只能求解較小規(guī)模的實(shí)例。采用機(jī)器學(xué)習(xí)方法時(shí)，需要對(duì)數(shù)據(jù)進(jìn)行大量的訓(xùn)練并分類，但由于模糊測(cè)試樣本集的整體性特點(diǎn)，需要人工干預(yù)設(shè)定指標(biāo)，反而降低了模糊測(cè)試的效率。使用傳統(tǒng)的逼近算法可以實(shí)現(xiàn)對(duì)樣本集的縮減，但是沒有考慮樣本在實(shí)際問題中的適用性。

2 基礎(chǔ)理論和評(píng)價(jià)指標(biāo)

2.1 基礎(chǔ)理論

2.1.1 貪心逼近算法

貪心逼近算法［3］是指利用有關(guān)算法解決一些實(shí)際問題的場(chǎng)景或精確度，且給出的解決方法是理論上的最優(yōu)解。在樣本集的精簡(jiǎn)中，貪心逼近算法指的是盡可能精確地給出樣本的最小樣本集，獲取優(yōu)質(zhì)樣本是貪心逼近算法的唯一標(biāo)準(zhǔn)。

2.1.2 遺傳算法

遺傳算法［8］是一種基于生物進(jìn)化原理構(gòu)想出來的搜索最優(yōu)解的仿生算法。其模擬基因重組與進(jìn)化的自然過程，把待解決的問題的參數(shù)編程成二進(jìn)制碼或十進(jìn)制碼（也可編成其他進(jìn)制碼），即基因，若干基因組成一個(gè)染色體（個(gè)體）。對(duì)染色體進(jìn)行類似于自然選擇、配對(duì)交叉和變異運(yùn)算，經(jīng)過多次重復(fù)迭代（世代遺傳）直至得到最后的優(yōu)化結(jié)果。

遺傳算法的步驟如下：

步驟1 初始化第0代種群P0。

步驟2 對(duì)第i代種群Pi迭代執(zhí)行步驟2.1～步驟2.5，直到滿足停止準(zhǔn)則：

2.1 計(jì)算Pi中每個(gè)個(gè)體的適應(yīng)值，并按照適應(yīng)值的大小對(duì)所有個(gè)體進(jìn)行排序。

2.2 將Pi中適應(yīng)值最佳的個(gè)體加入Pi＋1。

2.3 按照適應(yīng)值的大小排序在Pi中選擇2個(gè)父體。

2.4 按概率選擇雜交算子或者變異算子對(duì)兩父體進(jìn)行遺傳操作，將生成的個(gè)體加入Pi＋1。

2.5 如果Pi＋1的規(guī)模已經(jīng)與Pi持平，則i←i＋1并轉(zhuǎn)步驟2，否則轉(zhuǎn)步驟2.3。

步驟3 將最終種群中適應(yīng)度最好的個(gè)體作為遺傳算法的結(jié)果。

2.1.3 集合覆蓋問題

集合覆蓋問題（SCP）［9］：在模糊測(cè)試中，任何樣本集都可以轉(zhuǎn)化為最小集合覆蓋問題，而最小覆蓋集為經(jīng)典的NP-hard問題［10］，難以計(jì)算最優(yōu)解。集合覆蓋問題形式上可以描述如下：令A(yù)＝（aij）為一個(gè)m行、n列的0-1矩陣。C＝（cj）為一個(gè)n維整數(shù)向量。令M ＝｛1，2，…，m｝，N ＝｛1，2，…，n｝表示矩陣A的行向量和列向量維數(shù)。值cj（j∈N）表示某一列的代價(jià)。不失一般性，假定cj＞0，j∈N。如果aij＝1，則認(rèn)為列j∈N覆蓋了行i∈M。集合覆蓋問題要求一個(gè)最小代價(jià)的子集合S?N，這樣每一行i?M 至少被一列j?S覆蓋。集合覆蓋問題的一個(gè)自然的數(shù)學(xué)模型可以描述為：v（SCP）＝m incjxj，服從于aijx˙j≥1，i∈M，xj∈（0，1）（j∈N）；如果xj＝1（j∈S），則xj＝0。

2.2 評(píng)價(jià)指標(biāo)

1）壓縮率。對(duì)比樣本精簡(jiǎn)前和樣本精簡(jiǎn)后的測(cè)試樣本數(shù)量，并計(jì)算壓縮率來表示算法對(duì)樣本集的優(yōu)化程度。

2）執(zhí)行模糊測(cè)試所需要的時(shí)間。假設(shè)模糊測(cè)試初始樣本集數(shù)量為n，模糊測(cè)試時(shí)間函數(shù)為f（n），隨著模糊測(cè)試數(shù)量n的增加，模糊測(cè)試執(zhí)行時(shí)間的增長率與f（n）的增長率正相關(guān)。

3）樣本質(zhì)量。主要由代碼覆蓋率為判斷依據(jù)；代碼覆蓋率為測(cè)試的代碼行數(shù)占總代碼行數(shù)的比例。

3 基于啟發(fā)式遺傳算法的樣本集優(yōu)化

樣本集的精簡(jiǎn)是將數(shù)量龐大的數(shù)據(jù)集進(jìn)行縮減的過程。從本文所解決的問題出發(fā)，對(duì)于模糊測(cè)試集中的樣本，樣本的重復(fù)不僅表現(xiàn)在完全相同的樣本，而且從變異的根源來說，樣本間基本塊的相互覆蓋是導(dǎo)致變異產(chǎn)生大量重復(fù)測(cè)試用例的問題所在。因此，本文在進(jìn)行樣本選取時(shí)，規(guī)定優(yōu)先選取包含代碼基本塊數(shù)最多的樣本（代碼塊數(shù)多的樣本在進(jìn)行變異時(shí)可以得到更多測(cè)試用例），再按照樣本性能依次選擇，直到新樣本集基本代碼塊可以覆蓋原始樣本集的基本代碼塊為止。本文要定義的啟發(fā)式算法是對(duì)染色體選擇的算法，最終獲取所求染色體集合。

3.1 染色體的表示

為了保證在樣本集數(shù)量最少的基礎(chǔ)上得到更優(yōu)質(zhì)的樣本（基本代碼塊數(shù)多且變異能力好），在實(shí)現(xiàn)過程中，引入0-1矩陣［11］，向量x的元素是0或者1，用一個(gè)n位的二進(jìn)制串作為染色體結(jié)構(gòu)，n是矩陣A的列數(shù)，第i位上的值“1”意味著第i列被選擇。

進(jìn)行模糊測(cè)試時(shí)，每個(gè)程序都有自己所包含的基本代碼塊，根據(jù)基本塊地址找到的內(nèi)容就是對(duì)應(yīng)的代碼塊?；緣K地址信息的獲取是比較方便的，故將基本塊地址作為研究對(duì)象（每個(gè)基本地址塊相當(dāng)于遺傳算法中的基因）。每個(gè)樣本看作一個(gè)以基本代碼塊地址為元素的集合（樣本相對(duì)于遺傳算法中的染色體）。樣本中如果存在某個(gè)基本地址塊就用“1”表示，否則用“0”表示，所有的樣本構(gòu)成一個(gè)以0或1為元素的0-1矩陣。矩陣中的“1”即表示染色體的基因，每一列基因的集合相當(dāng)于一個(gè)染色體。

3.2 啟發(fā)式遺傳算法改進(jìn)染色體

選擇的染色體都會(huì)有自己獨(dú)特的基因存在，交叉重疊的基因也不計(jì)其數(shù)。在進(jìn)行集合覆蓋時(shí)，需要確定最小覆蓋集合并保證該集合冗余最小。

在實(shí)際的遺傳過程中，由于變異操作產(chǎn)生的染色體并不適合問題集合，本文不再對(duì)新個(gè)體的變異基因進(jìn)行修復(fù)，而是將變異產(chǎn)生的新個(gè)體直接舍棄（由于原始數(shù)據(jù)較相似，出現(xiàn)新的基因的概率很小）。遺傳算法執(zhí)行后會(huì)保留所有產(chǎn)生的染色體，該啟發(fā)式算法的作用包括以下2點(diǎn)：①消除因?yàn)榛蛑貜?fù)產(chǎn)生的冗余；②選擇更優(yōu)質(zhì)的染色體（包含的基因多且基因組合更豐富）。

啟發(fā)式算法闡述如下：

1）矩陣中的染色體和基因表示。

在0-1矩陣中，一列表示一個(gè)染色體，矩陣中的“1”表示某個(gè)染色體包含這個(gè)基因，“0”表示該染色體不包含該基因。算法使用性能代價(jià)比的優(yōu)先思想：性能指的是染色體中某位基因所對(duì)應(yīng)集合中的列包含“1”的個(gè)數(shù)，個(gè)數(shù)越多，則該列覆蓋的行數(shù)就越多，說明該染色體的性能比較高。假設(shè)一組染色體使用遺傳算法時(shí)產(chǎn)生的所有染色體集合為：Sall＝｛s1，s2，s3，s4，s5｝，s1＝｛2，4，6｝，s2＝｛1，6｝，s3＝｛3，5｝，s4＝｛2，3，7｝，s5＝｛1，7｝（本文采用數(shù)字來表示其包含的基因及位置）。

2）染色體的基因交換。

假設(shè)A1和A2是父代的2個(gè)染色體，B1和B2是染色體交換之后所得的孩子染色體。可以覆蓋矩陣A的集合，借助集合C1和C2，用其來存放基因沒有覆蓋的行號(hào)；集合D1和D2用來存放B1和B2包含的全部基因。例如，A1＝｛s1，s5｝，A2＝｛s2，s3，s4｝集合，B1、B2、C1和C2均為空集，D1＝｛1，2，3，4，5，6，7｝，D2＝｛1，2，3，4，5，6，7｝。

①計(jì)算集合A1和A2中每個(gè)基因體的性能η，即每列所包含的“1”的個(gè)數(shù)，“1”越多，表示該染色體能覆蓋行越多，其包含的基因就越多，其性能就越高。此時(shí)各個(gè)基因的性能為：ηs1＝ηs4＝3，ηs2＝ηs3＝ηs5＝2。

②A1和A2中性能最高的染色體放入集合B1，統(tǒng)計(jì)該染色體包含的基因，并在集合D1中將其刪除，計(jì)算其未包含的基因，將這些基因的行號(hào)存入集合C1，再按照相同方法排列A1和A2剩下的基因到B1，最后將其他的基因放入B2。

③在進(jìn)行基因選擇時(shí)，可能會(huì)出現(xiàn)一些基因性能一樣的情況，因此在性能相同的基因中選取最優(yōu)質(zhì)的基因是算法設(shè)計(jì)的關(guān)鍵。例如，假設(shè)集合父輩A1中有2個(gè)性能一樣的基因：s1＝｛2，4，6｝，s2＝｛1，4，6｝，當(dāng)前集合B1中包含一個(gè)基因s3＝｛2，3，5，6｝，s1、s2作為被選擇對(duì)象，s2和s3中相同的代碼塊要多于s1和s3的代碼塊，因此選擇s2比s1更合適。除此之外，模糊測(cè)試樣本在進(jìn)行變異時(shí)，會(huì)根據(jù)自己的代碼塊隨機(jī)變異生成測(cè)試用例。例如，s1＝｛2，4，6｝，s2＝｛1，4，6｝，當(dāng)前集合B1中包含一個(gè)染色體s3＝｛2，3，5，6｝。在染色體s1中，2號(hào)和6號(hào)代碼塊在B1中已經(jīng)出現(xiàn)，代碼塊進(jìn)行變異后，相當(dāng)于產(chǎn)生了一個(gè)新的基因組合。s3中，當(dāng)3號(hào)和5號(hào)基因不變異時(shí)，剩下的2號(hào)和6號(hào)的基因組合與染色體s1在4號(hào)基因不產(chǎn)生變異的基礎(chǔ)上是一樣的效果。相比較，染色體s2除了4號(hào)基因，1號(hào)和6號(hào)基因在進(jìn)行變異時(shí)會(huì)產(chǎn)生新的組合，進(jìn)而產(chǎn)生新的測(cè)試用例。在實(shí)現(xiàn)消除冗余的基礎(chǔ)上，在進(jìn)行下一個(gè)染色體選擇時(shí)，會(huì)出現(xiàn)性能相同的染色體，但其所包含的基因是不同的；在進(jìn)行選擇前，將等待選擇的性能相同的染色體與集合B1中已選的染色體做“差”，記錄“差”集的元素個(gè)數(shù)，按照上述規(guī)則，元素個(gè)數(shù)多的“差”集與已選染色體不相同的個(gè)數(shù)就越多，那么對(duì)應(yīng)的染色體即為下個(gè)候選染色體。

啟發(fā)式遺傳算法在原始種群的基礎(chǔ)上借助于0-1矩陣獲取所需染色體；在不需要改變遺傳算法工作過程的前提下優(yōu)化搜索條件，提升模糊測(cè)試的效率。

3.3 啟發(fā)式遺傳算法實(shí)現(xiàn)

啟發(fā)式遺傳算法的實(shí)現(xiàn)過程在理論意義上與傳統(tǒng)的遺傳算法是沒有區(qū)別的，同樣需要重點(diǎn)考慮以下幾個(gè)方面：①種群大小和種群初始化。種群樣本集的大小可以人為控制，而不隨機(jī)選擇。②父代選擇。在千萬樣本集中選擇2個(gè)樣本集作為父代，這是遺傳算法仿生物的表現(xiàn)。③交叉率。確定父代在染色體的某個(gè)點(diǎn)進(jìn)行交叉繁殖產(chǎn)生來后代。④變異率。產(chǎn)生后代的方法不僅依靠交叉，變異也是新物種最重要的來源。⑤精英比率。直接進(jìn)入下一代而不參與基因交換的優(yōu)秀個(gè)體的比例。⑥停止準(zhǔn)則。傳統(tǒng)的遺傳算法需設(shè)定界限；樣本集合覆蓋問題需要設(shè)定其遺傳的代數(shù)，或者某一個(gè)子代覆蓋了所有測(cè)試路徑時(shí)停止。

1）種群大小和種群初始化。

使用遺傳算法解決實(shí)際問題時(shí)，種群的大小對(duì)遺傳算法所求得的解的質(zhì)量有很大影響。適當(dāng)?shù)姆N群數(shù)量可以提高算法的性能。種群數(shù)量過大，影響算法的效率；種群數(shù)量過小，整個(gè)算法過程起到的作用不大，反而將集合問題復(fù)雜化。在樣本集精簡(jiǎn)問題中，本文算法沒有對(duì)種群的大小進(jìn)行太多的限制，數(shù)量根據(jù)實(shí)際情況自行定義，但是也會(huì)對(duì)不同種群數(shù)量進(jìn)行不同的測(cè)試，以便粗略地獲取較好的種群數(shù)量范圍。

2）父代的選擇。

父代的選擇是對(duì)種群中每個(gè)個(gè)體賦予的產(chǎn)生后代的機(jī)會(huì)。一般選擇方法包括隨機(jī)選擇法、錦標(biāo)賽選擇法和輪盤賭注法。本文采用輪盤賭注法，其基本思想是：個(gè)體被選擇的概率與其適應(yīng)度大小成正比。具體實(shí)現(xiàn)操作如下：

①計(jì)算出種群每個(gè)個(gè)體的適應(yīng)度fi（i＝1，2，…，M，M為種群大小）。

④在［0，1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r。

⑤若r＜q1，則選擇個(gè)體1，否則，選擇個(gè)體k，使得：qk－1＜r≤qk成立。

⑥重復(fù)④、⑤共M次。

3）交叉率［12］的選擇。

交叉是產(chǎn)生新個(gè)體的主要方法，在被選中的父代中確定一個(gè)交叉點(diǎn)，使雙親在交叉點(diǎn)進(jìn)行基因的重組。交叉率是用來設(shè)定交叉池中參與交叉的染色體的個(gè)數(shù)，合理的交叉率可以保證交叉池中不斷產(chǎn)生新個(gè)體，且不會(huì)產(chǎn)生過多的新個(gè)體，導(dǎo)致遺傳秩序破壞。不同的交叉方法對(duì)應(yīng)著不同的交叉率，當(dāng)前主流的方案是采用自適應(yīng)方法。

4）變異率［13］的選擇。

變異率指的是一個(gè)種群中發(fā)生變異的基因數(shù)目與全體基因數(shù)目的比例。變異是產(chǎn)生新個(gè)體的另一種方式，可以通過設(shè)定隨機(jī)變異的基因數(shù)也可以設(shè)定變異率來控制變異情況。在本文所研究的樣本集精簡(jiǎn)中，變異可以將包含獨(dú)特基因的染色體提前納入到所設(shè)定的搜索規(guī)則中，以便于保證遺傳算法的全局性。為此本文采用實(shí)驗(yàn)來設(shè)定合適的變異率，將最后一條含有獨(dú)特基因的染色體混入其他染色體，并使用本文提出的啟發(fā)式遺傳算法來進(jìn)行選擇。

圖1給出了變異率在0.5、0.6和0.7時(shí)待選基因隨著初始染色體數(shù)量的增加被啟發(fā)式遺傳算法選入的時(shí)間變化。由圖1可以得出，變異率為0.6時(shí)，花費(fèi)時(shí)間最少。變異率過小會(huì)導(dǎo)致參與變異的染色體過少，并不能將含有獨(dú)特基因的染色體提前錄入集合；變異率過高將會(huì)使得參與變異的染色體過多，更容易產(chǎn)生一些非法的數(shù)據(jù)并且增大時(shí)間開銷。因此，綜合考慮后，本文啟發(fā)式遺傳算法選取的變異率為0.6。

圖1 不同變異率選取染色體時(shí)間折線圖Fig.1 Broken line graph of chromosome selection time with differentmutation rates

5）精英比率。

當(dāng)前種群中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是用來替換掉本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體，本例中設(shè)置精英比率為0.08。

6）停止準(zhǔn)則。

遺傳算法在實(shí)際操作中都要經(jīng)過多代進(jìn)化，直到適應(yīng)值趨于穩(wěn)定，或者找到最優(yōu)解或者達(dá)到規(guī)定的遺傳代數(shù)，進(jìn)化過程結(jié)束。本文的樣本集精簡(jiǎn)目標(biāo)是在不降低代碼覆蓋的前提下盡可能降低測(cè)試用例的數(shù)量。當(dāng)算法執(zhí)行到特定迭代次數(shù)或選擇出的測(cè)試用例不再發(fā)生變化時(shí)，算法停止。

4 實(shí)驗(yàn)設(shè)置與評(píng)估

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

1）實(shí)驗(yàn)環(huán)境。實(shí)驗(yàn)在W indows 10系統(tǒng)下，配置為Intel Core i7-4790 CPU 3.6 GHz，8 GB內(nèi)存，使用peach等工具采用啟發(fā)式遺傳算法對(duì)模糊測(cè)試樣本集進(jìn)行精簡(jiǎn)優(yōu)化。

2）測(cè)試環(huán)境與目標(biāo)程序。在模糊測(cè)試實(shí)驗(yàn)中，本文選取peach［14］作為模糊測(cè)試工具：①安裝方便；②有開放的使用說明；③不同的命令可實(shí)現(xiàn)多種操作，在獲取樣本的執(zhí)行路徑時(shí)無需再借助于其他工具。同時(shí)選取 mspaint、pdfium、VLC Player作為目標(biāo)程序。

3）數(shù)據(jù)來源。本文實(shí)驗(yàn)所需的jpg、PDF、AVI類型數(shù)據(jù)來源于互聯(lián)網(wǎng)開源數(shù)據(jù)集。此數(shù)據(jù)集中包括很多重復(fù)數(shù)據(jù)，并且不同數(shù)據(jù)之間存在交叉；其將增加模糊測(cè)試樣本集錄入的時(shí)間，并使peach在變異時(shí)產(chǎn)生更多重復(fù)甚至沒有任何利用價(jià)值的測(cè)試用例。

4.2 實(shí)驗(yàn)方法與分析

3.3節(jié)闡述了本文方案的算法評(píng)價(jià)指標(biāo)，通過時(shí)間復(fù)雜函數(shù)來展現(xiàn)算法隨著初始數(shù)據(jù)的變化而變化的程度，而這些表現(xiàn)可以多種角度來展示。為了更直觀地展現(xiàn)算法的有效性，設(shè)計(jì)了以下實(shí)驗(yàn)，并以jpg類型數(shù)據(jù)實(shí)驗(yàn)過程進(jìn)行分析。

1）樣本集數(shù)量。

啟發(fā)式遺傳算法在0-1矩陣的基礎(chǔ)上操作，將矩陣中的元素“1”看作是遺傳算法中的染色體。在遺傳算法過程中，通過父代染色體的變異和交叉產(chǎn)生新的染色體，父代的選擇也是樣本精簡(jiǎn)的一個(gè)過程，只選擇性能好的染色體作為父代，直至進(jìn)化到停止準(zhǔn)則要求時(shí)間。實(shí)驗(yàn)中，對(duì)初始樣本集做了定向的選擇。jpg1：隨機(jī)選擇；jpg2：3組jpg1；jpg3：隨機(jī)選擇，jpg4：隨機(jī)選擇。精簡(jiǎn)樣本集的數(shù)量與初始樣本集的數(shù)量關(guān)系在表1中給出。由前2組數(shù)據(jù)可以看出，第2組數(shù)據(jù)在啟發(fā)式遺傳算法后數(shù)量明顯減少，jpg2包含3組jpg1，jpg2的精簡(jiǎn)樣本集數(shù)量與第1組一樣，啟發(fā)式遺傳算法在某種程上可以對(duì)樣本進(jìn)行精簡(jiǎn)，但是jpg2是特殊的數(shù)據(jù)組，不能體現(xiàn)算法的實(shí)用性。jpg3隨機(jī)選取的2 000個(gè)樣本集和jpg4隨機(jī)選擇的4 000個(gè)樣本集，其經(jīng)過啟發(fā)式遺傳算法優(yōu)化后獲得相應(yīng)精簡(jiǎn)樣本集，即啟發(fā)式遺傳算法并不會(huì)受選取樣本的影響。從jpg2和jpg3兩組數(shù)據(jù)可以看出，該啟發(fā)式遺傳算法可以減少樣本集的數(shù)量；從jpg1、jpg3和jpg4的初始樣本集數(shù)量和精簡(jiǎn)樣本集的數(shù)量進(jìn)行觀察，假設(shè)存在精簡(jiǎn)比例，那么jpg3的精簡(jiǎn)樣本集數(shù)量應(yīng)該是818，jpg4的精簡(jiǎn)樣本集數(shù)量應(yīng)該是1 636，而實(shí)際精簡(jiǎn)樣本集數(shù)量卻比期望低。這是因?yàn)椋哼x取樣本集數(shù)越大，該樣本集所包含“基因”越多，其可覆蓋“染色體”就越多，剩余不能覆蓋的“染色體”就越少，那么精簡(jiǎn)樣本集數(shù)量就越少。

表1 樣本集數(shù)量Tab le 1 Num ber of sam p le sets

2）模糊測(cè)試時(shí)間。

為了驗(yàn)證本文啟發(fā)式遺傳算法的有效性及能否提升模糊測(cè)試效率，對(duì)整體模糊測(cè)試時(shí)間進(jìn)行統(tǒng)計(jì)。將表1中所采用的4組數(shù)據(jù)進(jìn)行啟發(fā)式遺傳算法優(yōu)化后進(jìn)行模糊測(cè)試，其花費(fèi)的時(shí)間如表2所示，通過模糊測(cè)試時(shí)間的變化來說明該啟發(fā)式遺傳算法是否可以提升模糊測(cè)試效率。樣本數(shù)量與測(cè)試用例個(gè)數(shù)的對(duì)比情況如圖2所示。在一定程度上，測(cè)試用例的產(chǎn)生主要取決于原始樣本的最小樣本集合。模糊測(cè)試時(shí)間與樣本數(shù)量情況如圖3所示。精簡(jiǎn)后的樣本模糊測(cè)試時(shí)間低于未精簡(jiǎn)樣本的模糊測(cè)試時(shí)間；樣本集精簡(jiǎn)后模糊測(cè)試的時(shí)間比精簡(jiǎn)前降低了22%。本質(zhì)上，模糊測(cè)試用例的數(shù)量由輸入樣本集的數(shù)量來決定，而模糊測(cè)試用例通過啟發(fā)式遺傳算法去除冗余可以提升模糊測(cè)試的效率。

圖2 測(cè)試用例個(gè)數(shù)與樣本數(shù)量Fig.2 Number of test cases and number of samp les

圖3 模糊測(cè)試時(shí)間與樣本數(shù)量Fig.3 Fuzzy testing time and sample size

表2 模糊測(cè)試時(shí)間Tab le 2 Fuzzy testing tim e

3）樣本質(zhì)量。

每個(gè)樣本都有對(duì)應(yīng)的代碼塊，根據(jù)不同的代碼塊變異而產(chǎn)生測(cè)試用例。在未精簡(jiǎn)時(shí)，重復(fù)樣本產(chǎn)生無用測(cè)試用例。在時(shí)間一定的前提下，輸入同一組初始種群，對(duì)產(chǎn)生的測(cè)試用例進(jìn)行標(biāo)記以保證獲取的測(cè)試用例的不重復(fù)性，統(tǒng)計(jì)精簡(jiǎn)前后變異產(chǎn)生的測(cè)試用例的數(shù)量。本文從jpg3和jpg4中各取一個(gè)子集，名為Test1和Test2。實(shí)驗(yàn)測(cè)試用例數(shù)據(jù)情況如表3所示。測(cè)試時(shí)間一定時(shí)，未精簡(jiǎn)的樣本集短時(shí)間內(nèi)產(chǎn)生的測(cè)試用例大于精簡(jiǎn)后的樣本集所產(chǎn)生的測(cè)試用例，但其標(biāo)記后的測(cè)試用例個(gè)數(shù)小于精簡(jiǎn)后的標(biāo)記個(gè)數(shù)。樣本集在經(jīng)過啟發(fā)式遺傳算法后，其樣本的質(zhì)量有所提升；在相同的時(shí)間內(nèi)，其產(chǎn)生的測(cè)試用例存在的重復(fù)性小，同時(shí)精簡(jiǎn)前后的代碼覆蓋率沒有發(fā)生變化，算法兼顧了樣本質(zhì)量。

表3 測(cè)試用例數(shù)據(jù)Tab le 3 Test case data

4）對(duì)比實(shí)驗(yàn)。

通過比較文獻(xiàn)［3，15］提出的算法，觀察不同模糊測(cè)試樣本集優(yōu)化方案的處理效果。文獻(xiàn)［3，15］對(duì)比實(shí)驗(yàn)按照文獻(xiàn)原文中設(shè)定參數(shù)進(jìn)行精簡(jiǎn)優(yōu)化，對(duì)千兆級(jí)樣本數(shù)據(jù)進(jìn)行處理，實(shí)驗(yàn)數(shù)據(jù)如表4所示。通過表4可以觀察出，使用文獻(xiàn)［3，15］和本文所述樣本集精簡(jiǎn)方案對(duì)初始樣本集進(jìn)行優(yōu)化后，樣本集中數(shù)量有一定下降，且代碼覆蓋率都維持在初始樣本水平，保證了樣本質(zhì)量。但進(jìn)一步觀察，結(jié)合圖4所示，貪心逼近算法運(yùn)算速度較快，但需多次迭代方能達(dá)到和其他算法相同的精簡(jiǎn)數(shù)量，因此其速度卻遠(yuǎn)遠(yuǎn)要慢于啟發(fā)式遺傳算法的速度；并且如表4所示，本文所述方案處理過的樣本集中數(shù)量少于文獻(xiàn)［3，15］提出的方案，說明經(jīng)過本文所述方案優(yōu)化后的樣本集更加有效。

圖4 不同算法產(chǎn)生相同精簡(jiǎn)樣本集所需時(shí)間對(duì)比Fig.4 Comparison of time required for different algorithms to produce the same simplified sample set

表4 多種方案測(cè)試樣本數(shù)量和覆蓋率Table 4 Test sam p le size and coverage rate for m ultip le schem es

5 結(jié) 論

1）啟發(fā)式遺傳算法在遺傳算法上進(jìn)行改進(jìn)并且應(yīng)用到集合覆蓋問題中，通過染色體來表示集合中的覆蓋情況，以高質(zhì)量的染色體為背景，對(duì)染色體進(jìn)行啟發(fā)式改進(jìn)，使之在種群中隨時(shí)進(jìn)化，從而精簡(jiǎn)優(yōu)化樣本集。該方案比傳統(tǒng)方案壓縮率提升約40%，展示了該算法的有效性。

2）本文在進(jìn)行優(yōu)質(zhì)染色體選擇過程中使用0-1矩陣與集合覆蓋的方式來完成優(yōu)質(zhì)染色體的選取工作，并且改進(jìn)了基因交叉的規(guī)則，加快模糊測(cè)試速度，同時(shí)能夠兼顧樣本質(zhì)量和處理時(shí)間，測(cè)試時(shí)間降低了約22%，比傳統(tǒng)方式更加高效。