李志博，李清寶，蘭明敬，孫劍帆

（中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué)，河南鄭州 450001）

1 引言

被測程序通常有較大的輸入空間，因此選擇一部分可以有效識別軟件失效的測試輸入作為測試數(shù)據(jù)具有重要意義. 測試數(shù)據(jù)生成技術(shù)指導(dǎo)如何生成高效的測試數(shù)據(jù)，如隨機(jī)測試（RT）數(shù)據(jù)生成方法［1］、基于符號執(zhí)行的測試數(shù)據(jù)生成方法［2］、基于有限狀態(tài)機(jī)的測試數(shù)據(jù)生成方法［3］、基于智能搜索的測試數(shù)據(jù)生成方法［4，5］等. 文獻(xiàn)［6］提出了一種基于變異分支優(yōu)勢度排序的弱變異測試數(shù)據(jù)生成方法，在提高了測試集的錯(cuò)誤檢測能力的同時(shí)提高了效率. 對于MPI 程序的路徑覆蓋測試，文獻(xiàn)［7］提出了一種將集成代理模型（ESM）的估計(jì)集成到測試數(shù)據(jù)生成過程中的方法，以此來降低適應(yīng)度值的計(jì)算量. 文獻(xiàn)［8］提出了一種基于代理輔助進(jìn)化優(yōu)化的MPI 程序路徑覆蓋測試數(shù)據(jù)生成方法，該方法能有效地生成高質(zhì)量的測試數(shù)據(jù).

RT 是一種簡單、易于實(shí)現(xiàn)的測試方法. 它不涉及到復(fù)雜的軟件需求或程序的內(nèi)部結(jié)構(gòu)信息，只需在輸入域內(nèi)隨機(jī)地生成測試數(shù)據(jù)即可.RT 沒有利用被測軟件的任何信息，且生成的測試數(shù)據(jù)具有冗余度高，覆蓋度低，盲目性等缺點(diǎn)，曾被Myers 認(rèn)為可能是最糟糕的測試方法. 但由于RT 具有簡單、易實(shí)現(xiàn)、成本低、無偏性、速度快等優(yōu)點(diǎn)，易與其它測試方法結(jié)合使用，因此被廣泛應(yīng)用在各個(gè)領(lǐng)域的軟件測試和可靠性評估中.同時(shí)，所有測試方法生成的測試數(shù)據(jù)理論上均可由RT生成，因此RT具有發(fā)現(xiàn)一切錯(cuò)誤的潛力［9］.

經(jīng)實(shí)驗(yàn)研究發(fā)現(xiàn)，引發(fā)失效的輸入易于聚集在連續(xù)的區(qū)域. 依此結(jié)論，Chen 提出了ART（Adaptive Random Testing）算法［10］. 與RT 不利用任何信息隨機(jī)產(chǎn)生測試數(shù)據(jù)相比，ART 算法利用已執(zhí)行成功測試數(shù)據(jù)的信息，以及引發(fā)失效的輸入易于集中的特征，使生成的測試數(shù)據(jù)盡可能均勻的分布在輸入空間內(nèi). 實(shí)驗(yàn)表明ART 的檢錯(cuò)有效性較RT 有明顯改善，發(fā)現(xiàn)第一個(gè)錯(cuò)誤所需的測試數(shù)據(jù)數(shù)量更少. 學(xué)術(shù)界提出了各種基于ART 思想的改進(jìn)算法，例如，基于距離的ART 算法（DART）［11］，基于限制的ART 算法（RRT）［12］，基于劃分的ART 算法［13］等. ART 也是一種基礎(chǔ)測試方法，應(yīng)用領(lǐng)域非常廣泛，易于同其他測試數(shù)據(jù)生成方法結(jié)合，提升測試數(shù)據(jù)生成方法的有效性，如ART 與程序的路徑覆蓋信息相結(jié)合用來提升測試數(shù)據(jù)生成的有效性［14］、ART 用于安全測試生成檢測XSS 漏洞的測試數(shù)據(jù)［15］、ART 與基于搜索的測試數(shù)據(jù)生成方法相結(jié)合，在蟻群算法的局部搜索中引入了ART［16］、ART 用于測試數(shù)據(jù)優(yōu)先級排序，將FSCS 算法用于測試數(shù)據(jù)優(yōu)先級排序，檢錯(cuò)能力優(yōu)于隨機(jī)法與貪婪法［17］. 文獻(xiàn)［18］在不同測試場景下對組合測試、RT、ART 進(jìn)行了對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果顯示ART 優(yōu)于RT，并且在96%的測試場景下檢錯(cuò)能力與組合測試相近.

但是ART 算法需要額外的開銷使生成的測試數(shù)據(jù)更加均勻. 尤其是基于距離的ART 算法，距離計(jì)算是算法較大的開銷，這些開銷減少了ART 算法的可用性，降低了ART 算法生成測試數(shù)據(jù)的效率. 鏡像策略是一種有效提高測試數(shù)據(jù)生成效率的手段. 通過鏡像策略，將已生成測試數(shù)據(jù)通過鏡像函數(shù)生成新的測試數(shù)據(jù)，減少了ART算法的計(jì)算開銷，提高了ART算法的效率，但是降低了ART算法的有效性［19］.

2 鏡像策略

根據(jù)鏡像策略在ART 算法中的實(shí)施流程劃分，MART 算法主要包括三個(gè)部分：鏡像劃分、鏡像函數(shù)和鏡像選擇序.

2.1 鏡像劃分

鏡像劃分指將輸入空間劃分子域的方式. 根據(jù)各維度劃分是否均等，分為相等劃分和非等劃分.

假設(shè)N為輸入空間D的維度數(shù)量，即|D| =N，每個(gè)維度用Xi(i=1，2，3，…，N)表示，將維度Xi平均劃分的數(shù)量用ki(i=1，2，…，N)表示. 若對輸入空間D進(jìn)行鏡像劃分后，存在兩個(gè)維度Xi與Xj劃分的數(shù)量不等，即ki≠kj，稱為非等劃分. 若對輸入空間D進(jìn)行鏡像劃分后，任意兩個(gè)維度Xi與Xj劃分的數(shù)量都相等，即ki=kj，稱為相等劃分.

在相等劃分中，若每個(gè)維度劃分后的個(gè)數(shù)ki(i=1，2，…，N)可以用2ω(ω=1，2，3，…)表示，如

稱此類相等劃分為對等劃分，ω為鏡像劃分的深度，子域數(shù)量m=(2ω)N.

2.2 鏡像函數(shù)

通過鏡像劃分方法，將輸入空間劃分為m個(gè)子域.選擇其中一個(gè)子域作為源域，源域中應(yīng)用ART 算法生成測試數(shù)據(jù)，其余m-1 個(gè)鏡像子域中如何對應(yīng)生成測試數(shù)據(jù)，則是通過鏡像函數(shù)將源域中的測試數(shù)據(jù)映像到鏡像域中.

常見的鏡像函數(shù)有平移和對稱.

假設(shè)在n維輸入空間中，源域空間為D0，鏡像子域?yàn)镈k，其中，

在源域空間D0中，測試數(shù)據(jù)生成算法生成的測試數(shù)據(jù)為tc0=(t1，t2，…，tn)，則測試數(shù)據(jù)tc0在鏡像子域Dk中的鏡像測試數(shù)據(jù)tck為：

（1）若鏡像函數(shù)為平移，則：

（2）若鏡像函數(shù)為對稱，則：

如圖1所示，在2維輸入空間中，鏡像劃分深度為1時(shí)，劃分后的鏡像子域的數(shù)量為4. 假設(shè)陰影部分子域作為源域，源域中通過算法生成測試數(shù)據(jù)，根據(jù)鏡像函數(shù)將源域中的測試數(shù)據(jù)鏡像到其余的各子域中，通過平移鏡像函數(shù)生成鏡像測試數(shù)據(jù)如圖1（a）所示，通過對稱鏡像函數(shù)生成鏡像測試數(shù)據(jù)如圖1（b）所示.

圖1 兩種鏡像函數(shù)示意圖

對稱鏡像函數(shù)可能出現(xiàn)如圖2所示的情況，使測試數(shù)據(jù)在整個(gè)輸入域中分布不夠均勻.

圖2 對稱鏡像可能存在的問題

相對來說，平移鏡像函數(shù)較對稱鏡像函數(shù)在鏡像子域中生成測試數(shù)據(jù)更均勻.

2.3 鏡像選擇序

源域中的測試數(shù)據(jù)先執(zhí)行，然后是鏡像域中的測試數(shù)據(jù). 當(dāng)鏡像子域的數(shù)量較多時(shí)，不同鏡像子域內(nèi)測試數(shù)據(jù)執(zhí)行順序?qū)λ惴ㄓ行砸灿杏绊?

鏡像選擇序是不同鏡像域中的測試數(shù)據(jù)執(zhí)行順序，有順序選擇序、隨機(jī)選擇序等.

順序選擇序指選擇鏡像域的順序按從左到右、從上到下的固定順序依次選擇. 將2 維輸入空間劃n行m列，每個(gè)子域順序編序，則選擇鏡像域的順序即xi的下標(biāo)序.

隨機(jī)選擇指隨機(jī)在m·n-1 個(gè)鏡像域中選擇一個(gè)，根據(jù)鏡像函數(shù)生成測試數(shù)據(jù)進(jìn)行執(zhí)行.

3 基于鏡像策略的ART算法

基于鏡像策略的ART 的思想［19］：將輸入空間劃分為多個(gè)不相交的相等子域，源域中使用ART 算法生成測試數(shù)據(jù)，剩余子域中使用鏡像函數(shù)生成鏡像測試數(shù)據(jù). 詳見算法1.

算法1 MART算法輸入：輸入域維度n，劃分深度ω，失效域F隨機(jī)分布在輸入域中.輸出：生成測試用例集E.1. 初始時(shí)，E=?；2. 根據(jù)鏡像相等劃分策略劃分輸入域，一共劃分成2n·ω個(gè)子域；3. 任選一個(gè)子域D1作為源域；4. 在源域D1中依據(jù)ART算法生成一個(gè)測試用例tc；5. 如果tc檢測到失效，轉(zhuǎn)到步驟10；否則，將tc存入E中.6. 根據(jù)鏡像域的選擇序確定測試用例tc待鏡像的下一個(gè)子域m；7. 根據(jù)鏡像函數(shù)，計(jì)算出鏡像子域m中的鏡像測試數(shù)據(jù)tc'；8. 判斷tc'是否檢測到失效，如果檢測到失效轉(zhuǎn)向步驟10；否則，將tc'存入E中.9. 若所有2n·ω-1鏡像子域中已生成測試數(shù)據(jù)tc的鏡像測試數(shù)據(jù)，則轉(zhuǎn)向步驟4；否則，轉(zhuǎn)向步驟6.10. 算法終止.

將輸入域空間D等分為D1和D2兩部分. 若取D1為源域，D2為鏡像域，僅需在D1中使用ART 算法生成測試數(shù)據(jù)，通過鏡像函數(shù)平移到D2中，使D1與D2中測試數(shù)據(jù)具有相同分布，而只在D1中進(jìn)行了距離的計(jì)算. 假設(shè)輸入域空間D等分為m個(gè)子域，若ART算法與MART 算法生成相同數(shù)量測試數(shù)據(jù)，MART 只需要ART距離計(jì)算的1/m2［20］.

4 基于鏡像選擇序優(yōu)化的MART算法

4.1 問題提出

鏡像隨機(jī)選擇序是隨機(jī)選擇未生成鏡像測試數(shù)據(jù)的鏡像子域，生成鏡像測試數(shù)據(jù). 鏡像域的隨機(jī)選擇序簡單，易實(shí)現(xiàn)，一定程度上較均勻的選擇鏡像子域，從而生成的鏡像數(shù)據(jù)過程也是隨機(jī)的.

鏡像隨機(jī)選擇序可能會出現(xiàn)已生成測試數(shù)據(jù)的子域與被選擇鏡像子域在某個(gè)維度下是屬于同一個(gè)分區(qū)的情況，如圖3所示.

圖3 鏡像隨機(jī)選擇序可能存在的問題

如圖3所示，假設(shè)在二維輸入空間中，鏡像深度ω=2時(shí)，鏡像劃分后，輸入空間被平均劃分成16個(gè)子域，圖中深色正方形區(qū)域?yàn)槭в? 選取標(biāo)號“1”的域?yàn)樵从?，源域中生成測試數(shù)據(jù)后，選擇鏡像子域生成鏡像測試數(shù)據(jù)，如果選擇的鏡像子域在陰影子域內(nèi)，則無法觸發(fā)缺陷，因?yàn)槭в蛟诎咨佑蛩诜秶鷥?nèi). 鏡像子域隨機(jī)選擇序是隨機(jī)的選擇子域，不做任何限制，可能會出現(xiàn)選擇的鏡像子域與已生成測試數(shù)據(jù)的子域在相同行或相同列的現(xiàn)象，也就是選擇生成測試數(shù)據(jù)的鏡像子域在某個(gè)維度或多個(gè)維度上取值范圍相同.

針對鏡像隨機(jī)選擇序可能出現(xiàn)的這種情況，考慮對鏡像選擇序進(jìn)行約束，本文通過限制鏡像子域選擇序，增強(qiáng)鏡像子域選擇序的多樣性，從而提高M(jìn)ART 算法的檢錯(cuò)有效性.

4.2 鏡像受限選擇序

鏡像受限選擇序是每次選擇鏡像子域生成鏡像測試數(shù)據(jù)時(shí)，選擇鏡像子域不是完全隨機(jī)的，是受限制的隨機(jī)選擇方式.

假 設(shè)n維 輸 入 空 間 為D={(d0，d1，…，dn-1)|d0∈D0，d1∈D1，…，d(n-1)∈D(n-1)}，鏡像劃分深度為ω，則每個(gè)維度被劃分為2ω個(gè)區(qū)域，整個(gè)輸入空間被劃分為2n·ω個(gè)鏡像子域. 第i維空間di被劃分的區(qū)域用dij表示，其中0 ≤j≤2ω-1.

定義∑ij表示第i維空間di的第j個(gè)區(qū)域中被選中的鏡像子域的數(shù)量. 當(dāng)∑ij=2ω()n-1時(shí)，表示第i維空間di的第j個(gè)區(qū)域中所有鏡像子域都被選出.

對于某個(gè)子域X={(x0，x1，…，xn-1)}，定義δ(xi)表示子域X在第i維空間中所屬的子域位置. 鏡像受限選擇算法描述如算法2所示.

算法2 鏡像受限選擇序算法輸入：輸入空間D；輸出：子域選擇序；1. 鏡像劃分深度為ω，劃分子域數(shù)量m=2n·ω，初始∑ij=0，其中0 ≤i ≤n-1，0 ≤j ≤2ω-1.2. 隨機(jī)選擇一個(gè)子域作為源域Ds={(d'0，d'1，…，d'n-1)|d'0 ∈D0s，d'1 ∈D1s，…，d'n-1 ∈D( )n-1 s，0 ≤s ≤2ω-1}將源域空間對應(yīng)每個(gè)維度的區(qū)域數(shù)量加1，即∑ij=1，其中，i ∈{0，1，…，n-1}，j=δ(d'i).3. 在所有∑ij=0的子域內(nèi)，隨機(jī)選擇一個(gè)子域D'，同理，將該子域?qū)?yīng)的每個(gè)維度的區(qū)域數(shù)量加1，∑ij=1，其中j=δ(D'i).4. 當(dāng)所有子域全部對應(yīng)的∑ij=1時(shí)，重復(fù)此操作，在所有∑ij=0的子域內(nèi)，隨機(jī)選擇子域. 直至所有子域全部被選出.5. 返回子域選擇出的順序.

如圖4所示，在二維輸入空間中，鏡像劃分深度為2，則每個(gè)維度被劃分成4部分，二維空間被劃分為16個(gè)鏡像子域. 隨機(jī)選擇一個(gè)子域作為源域，如圖4（a）中，標(biāo)號為1的子域，則δ(x0) =1，δ(x1) =1，故∑01=1，∑11=1. 即陰影區(qū)域?yàn)樵从颉?”在每個(gè)維度上的子域所占的區(qū)域，下一個(gè)鏡像子域的選擇不在陰影區(qū)域內(nèi)選擇. 也就是在圖4（a）中的空白子域中，隨機(jī)選擇一個(gè)域作為鏡像子域“2”，如圖4（b）所示，則“2”子域的δ(x0) =2，δ(x1) =3，故∑02=1，∑13=1. 即“2”子域所在的行列子域轉(zhuǎn)換為陰影區(qū)域.同理，在空白子域中隨機(jī)選擇“3”、“4”子域（如圖4（c）、（d）），第一輪子域選擇結(jié)束后，每個(gè)維度的每個(gè)區(qū)域都有選出的鏡像子域，即?(i，j) ∑ij=1，如圖4（d）中所有子域全部為陰影填充.

圖4 鏡像受限選擇序

然后依此規(guī)則，開始第二輪迭代，選出相應(yīng)的鏡像子域，第二輪迭代結(jié)束后，每個(gè)維度的每個(gè)區(qū)域都有選出的2 個(gè)鏡像子域，即?(i，j) ∑ij=2，第k輪次迭代后，?(i，j) ∑ij=k，直至k=2ω()n-1時(shí)（圖中示例k=4 時(shí)），全部鏡像子域被選出.

有時(shí)可能會出現(xiàn)鏡像子域受限選擇沖突現(xiàn)象，如圖5所示.

圖5 鏡像受限選擇序沖突現(xiàn)象

當(dāng)?shù)谝惠喌Y(jié)束后，?(i，j) ∑ij=1，此時(shí)清空所有陰影底紋，恢復(fù)為白色，開始第二輪迭代，從剩余的空白鏡像子域中隨機(jī)選擇一個(gè)，如圖5（a）所示，選擇鏡像子域“5”. 如圖5（a）所示，則“2”子域的δ(x0) =2，δ(x1) =0，故∑02=2，∑10=2. 即“5”子域所在的行列子域轉(zhuǎn)換為陰影區(qū)域. 同理，在空白子域中隨機(jī)選擇“6”、“7”子域（如圖5（b）、（c）），此時(shí)，僅?！?0=1，∑12=1，其余∑ij=2，i∈{0，1}. 而僅剩的白色子域“4”已經(jīng)被選出，此現(xiàn)象為鏡像子域受限選擇沖突現(xiàn)象. 算法針對此情況的沖突解決方案是，清空所有陰影底紋，恢復(fù)為白色，然后從所有空白且沒有標(biāo)號的子域中隨機(jī)選擇一個(gè)子域，進(jìn)入下一輪迭代，直至所有子域均為選出.

4.3 基于鏡像受限選擇序的MART算法

根據(jù)鏡像受限選擇序思想，本文提出了基于鏡像受限選擇序的MART 算法. 通過限制待鏡像的鏡像域，使得鏡像域的選擇序更加均勻，保證了測試數(shù)據(jù)盡可能的在每個(gè)維度上均勻分布.

算法3 基于鏡像受限選擇序的MART算法輸入：n維輸入空間，鏡像深度ω；輸出：測試數(shù)據(jù)集E.1. 對于n維輸入空間，鏡像深度ω，將輸入域劃分為2n·ω個(gè)子域.2. 從子域中任選一個(gè)作為源域，其余子域?yàn)殓R像域.3. 源域中使用ART算法生成測試數(shù)據(jù)tc，放入E中.4. 測試數(shù)據(jù)tc執(zhí)行被測程序若觸發(fā)缺陷，轉(zhuǎn)向步驟6，否則通過鏡像函數(shù)映像生成鏡像測試數(shù)據(jù)tc'.5. 鏡像測試數(shù)據(jù)生成順序取決于鏡像選擇序（參考算法2：鏡像受限選擇序算法），其中檢驗(yàn)生成的鏡像測數(shù)據(jù)tc'（放入E中）是否觸發(fā)缺陷，若觸發(fā)缺陷，轉(zhuǎn)向步驟6，否則到步驟3.6. 算法終止，返回已生成測試數(shù)據(jù)集E.

如圖6所示，在二維輸入空間中，鏡像劃分深度為2時(shí)，整個(gè)輸入空間被劃分為16個(gè)子域，假設(shè)選取標(biāo)號為“1”的子域空間為源域，即在1 號子域中根據(jù)ART 算法生成測試數(shù)據(jù). 根據(jù)鏡像受限選擇序MART 算法的基本思想，依次選擇鏡像子域通過鏡像函數(shù)生成鏡像測試數(shù)據(jù)t. 第2 號子域被隨機(jī)選出，只須保證與1 號子域不同行不同列. 同理，第3 號子域被隨機(jī)選出，只須保證與1、2號子域不同行不同列. 第一輪次選出的4個(gè)子域如圖6（a）所示，依此原則，第二、三輪每輪次內(nèi)依次選擇不同行不同列的子域，如圖6（b）（c）所示. 直至第4輪次執(zhí)行完畢，如圖6（d）所示，所有16個(gè)鏡像子域被選出，生成子域序列s. 在源域中使用ART 算法生成的測試數(shù)據(jù)根據(jù)鏡像函數(shù)，按照子域序列s的順序依次生成測試數(shù)據(jù)，每次生成一個(gè)鏡像測試數(shù)據(jù)，執(zhí)行被測程序檢驗(yàn)是否觸發(fā)缺陷，如果觸發(fā)缺陷則算法終止，否則依次執(zhí)行完序列s中所有的測試數(shù)據(jù)，若還未發(fā)現(xiàn)缺陷，則需在源域中根據(jù)ART 算法生成第二個(gè)測試數(shù)據(jù)，以上述原則產(chǎn)生鏡像子域的選擇序，生成鏡像測試數(shù)據(jù)，直至發(fā)現(xiàn)缺陷或達(dá)到迭代終止條件.

圖6 基于鏡像受限選擇序的MART算法

5 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

5.1 仿真實(shí)驗(yàn)

5.1.1 實(shí)驗(yàn)設(shè)計(jì)

仿真實(shí)驗(yàn)涉及的參數(shù)主要為維度、失效率、失效模式、測試方法、實(shí)驗(yàn)次數(shù)等，具體如下：

（1）維度. 表示待測程序輸入?yún)?shù)的個(gè)數(shù). 假定以二、三、四、五維輸入域進(jìn)行分析對比，每個(gè)維度坐標(biāo)取值范圍為［1，1 000］，如二維輸入域?yàn)檎叫危S輸入域?yàn)檎襟w，以此類推.

（2）失效率. 為引發(fā)失效的輸入域占整個(gè)輸入域的比例，顯然，失效率θ∈[0，1]. 失效域大小由失效率確定，失效率=塊狀失效模式大小/整個(gè)輸入空間大小，失效域的位置隨機(jī)出現(xiàn)在輸入域內(nèi). 失效率取值范圍為θ∈[0.000 1，0.1].

（3）失效模式. 使用代碼模擬輸入空間中的塊狀失效模式、條狀失效模式和點(diǎn)狀失效模式. 根據(jù)實(shí)驗(yàn)設(shè)置的輸入空間大小D，失效率θ，計(jì)算失效區(qū)域F=D×θ.塊狀失效模式模擬在輸入空間內(nèi)隨機(jī)生成一個(gè)面積或體積為F的正方形（二維）或立方體（三維）區(qū)域；條狀失效模式模擬在輸入空間中的一個(gè)長條區(qū)域，通過在X軸、Y軸正向坐標(biāo)軸上各自隨機(jī)選取一個(gè)點(diǎn)，兩個(gè)點(diǎn)連接后的直線作為長條失效域的長度，寬度由失效域面積F確定，使得長寬比例圍成的條狀區(qū)域面積為F；點(diǎn)狀失效模式模擬在輸入空間內(nèi)隨機(jī)生成k個(gè)不相交的相等大小的正方形區(qū)域，假定每個(gè)正方形的面積為S，則k個(gè)正方形區(qū)域面積之和k×S等于失效域面積F，本實(shí)驗(yàn)中k取值為10，即模擬10個(gè)離散點(diǎn)狀失效域. 失效模式的影響分析時(shí)，考慮三種失效模式，除此之外，無特殊說明時(shí)，失效模式均為塊狀失效模式.

（4）測試數(shù)據(jù)生成算法. 實(shí)驗(yàn)算法為ART 算法、鏡像順序選擇序MART 算法、鏡像隨機(jī)選擇序MART 算法、鏡像受限選擇序MART 算法. 三類MART 算法均采用對等劃分的方式對輸入空間進(jìn)行子域劃分，鏡像函數(shù)包括平移和對稱兩種. 源域中測試數(shù)據(jù)生成算法均采用FSCS算法. 詳見表1.

表1 實(shí)驗(yàn)中的算法列表

隨機(jī)測試（RT）：隨機(jī)測試算法，F(xiàn)measure理論值為1/θ(其中θ為失效率).

ART 算法：為ART 算法中的經(jīng)典DART 算法之一FSCS算法，基于距離計(jì)算的自適應(yīng)隨機(jī)測試算法，其中候選測試數(shù)據(jù)集大小設(shè)為10.

鏡像順序選擇序MART 算法：鏡像子域選擇方式為順序方式. 鏡像隨機(jī)選擇序MART 算法：鏡像子域選擇方式為順序方式. 鏡像受限選擇序MART 算法：為4.3節(jié)提出的新算法.

（5）檢錯(cuò)有效性度量指標(biāo). 使用各類算法生成測試數(shù)據(jù)，當(dāng)測試數(shù)據(jù)落入模擬的失效域中時(shí)，觸發(fā)缺陷，記錄第一個(gè)發(fā)現(xiàn)缺陷時(shí)已生成測試數(shù)據(jù)的數(shù)量. 每次執(zhí)行算法發(fā)現(xiàn)第一個(gè)缺陷所需的測試數(shù)據(jù)的數(shù)量為Fcount，則本實(shí)驗(yàn)中Fmeasure值為10 000次Fcount的平均值.算法有效性度量采用Fmeasure值，是首次觸發(fā)缺陷生成測試數(shù)據(jù)數(shù)量的期望值. 為了便于對比不同失效率下ART 算法相對RT 算法的Fmeasure改進(jìn)程度，定義Fratio=FARTFRT，F(xiàn)ratio反映了ART 算法相對RT 算法的改進(jìn)程度. 若Fratio＜1，則說明ART 算法檢錯(cuò)有效性比RT 算法強(qiáng)，當(dāng)Fratio≥1 時(shí)，說明ART 算法相對RT 算法檢錯(cuò)有效性無優(yōu)勢.

（6）數(shù)據(jù)展示標(biāo)識. 實(shí)驗(yàn)結(jié)果圖形展現(xiàn)時(shí)，ART 算法使用黑色實(shí)線標(biāo)識，使用平移鏡像函數(shù)的各類MART算法（MART_T、MART_T、MART_T_N）使用實(shí)線標(biāo)識（分別對應(yīng)品紅色、藍(lán)色與紅色），使用對稱鏡像函數(shù)的各類MART 算法（MART_R、MART_R_R、MART_R_N）使用虛線標(biāo)識（分別對應(yīng)品紅色、藍(lán)色與紅色）.

5.1.2 實(shí)驗(yàn)結(jié)果分析

5.1.2.1 失效模式的影響分析

二維輸入空間中，鏡像劃分深度為2，劃分子域數(shù)量為16 時(shí)；以及鏡像劃分深度為3，劃分子域數(shù)量為64時(shí)，分析各類MART 算法在塊狀失效模式、條狀失效模式和點(diǎn)狀失效模式下檢錯(cuò)有效性.

如圖7（a）（b）所示，塊狀失效模式中，鏡像深度為2時(shí)，各類MART 算法中，鏡像平移函數(shù)的MART 算法優(yōu)于鏡像對稱MART 算法. 鏡像深度為3 時(shí)，同類MART算法中鏡像平移函數(shù)的MART 算法與鏡像對稱MART算法差異不大. MART_T_N 算法在各類MART 算法中檢錯(cuò)有效性最強(qiáng).

如圖7（c）（d）所示，條狀失效模式下，鏡像順序選擇序算法在各類MART算法中表現(xiàn)優(yōu)異，F(xiàn)ratio值小于其他算法. 分析鏡像順序選擇算法在條狀失效模式下的優(yōu)勢，主要由模擬仿真方式?jīng)Q定. 因?yàn)闂l狀模式代碼中失效區(qū)域與X軸、Y軸的正向軸相交，而鏡像順序選擇算法的順序也是從坐標(biāo)原點(diǎn)開始，沿X軸依次順序選擇，然后向Y軸正向方向擴(kuò)展. 這種條狀失效模式模擬方式有利于鏡像順序選擇序觸發(fā)缺陷，所以該類算法Fratio值較小.

如圖7（e）（f）所示，點(diǎn)狀失效模式下，各類ART 算法檢錯(cuò)有效性增強(qiáng). 隨著深度增加，各類算法檢錯(cuò)有效性均有所降低. 整體來看，MART_T_N 算法檢錯(cuò)有效性略強(qiáng)于其他MART算法.

圖7 不同失效模式，2～3鏡像深度，各類算法Fratio值

三種失效模式下，各類ART 算法都隨著鏡像子域增多，檢錯(cuò)有效性有所降低.MART_T_N 算法在塊狀失效模式與點(diǎn)狀失效模式中較其他MART 算法相比檢錯(cuò)能力略強(qiáng).

5.1.2.2 鏡像劃分的影響分析

分析鏡像劃分深度不同時(shí)，ART算法及各類MART算法的有效性對比. 失效率為0.01時(shí)，鏡像深度分別取ω=1，2，3，4，二維空間時(shí)子域數(shù)量為4、16、64、256，三維空間時(shí)子域數(shù)量為8、64、512、4 096. 對比實(shí)驗(yàn)Fratio值如圖所示.

圖8 中，不同鏡像深度時(shí)，平移鏡像函數(shù)普遍優(yōu)于對稱鏡像函數(shù)，三維空間中，平移鏡像函數(shù)的優(yōu)勢比在二維空間中更大.MART_T_N 算法在三維空間，深度為4時(shí)，較MART_T_R算法優(yōu)勢明顯.

總得來說，當(dāng)鏡像劃分的子域數(shù)量與RT 算法的理論Fmeasure值相近時(shí)，各類MART 算法的檢錯(cuò)能力最強(qiáng).鏡像劃分的子域數(shù)量增大時(shí)，各類MART 算法的檢錯(cuò)能力都下降. 鏡像受限選擇序算法檢錯(cuò)有效性優(yōu)于其他MART 算法. 隨著深度的增加，MART_T_N 算法優(yōu)勢更加明顯.

5.1.2.3 維度的影響分析

（1）鏡像劃分深度相同，維度不同

失效率為0.01（RT 算法理論Fmeasure值為100），2～6維輸入，鏡像劃分2，各算法Fratio值如圖9.

在低維空間中，不同鏡像序的MART 算法差異不大，隨著維度的增大，MART_T_N 算法比MART_T_R 算法的優(yōu)勢增大，除了當(dāng)維度和深度確定的子域數(shù)量與RT 的理論Fmeasure值近似時(shí)，各類MART 算法的Fratio值最低.

（2）劃分子域數(shù)量相同，維度不同

分別考慮失效率為0.01 時(shí)與0.001 時(shí)，不同維度時(shí)而相同子域數(shù)量進(jìn)行實(shí)驗(yàn)驗(yàn)證.

本次實(shí)驗(yàn)設(shè)置失效率為0.01 時(shí)（RT 算法理論Fmeasure值為100），子域數(shù)量最接近的值為64，分別對2、3、6維輸入空間進(jìn)行鏡像劃分3、2、1時(shí)得到64個(gè)子域，各算法的Fratio值如圖10（a）所示. 實(shí)驗(yàn)設(shè)置失效率為

圖8 失效率0.01，2～3維空間，劃分深度1～4，各算法Fratio值

圖9 失效率0.01，鏡像深度為2，2～6維度各算法Fratio值0.001 時(shí)（RT 算法理論Fmeasure值為1 000），子域數(shù)量最接近的值為1 024，分別對2、5 維輸入空間進(jìn)行鏡像劃分5、2時(shí)得到1 024個(gè)子域，各算法的Fratio值如圖10（b）所示.

圖10 子域數(shù)量與RT理論Fmeasure相近時(shí)，各算法Fratio值

如圖10 所示，在失效率0.01 與0.001 時(shí)，在子域數(shù)量與RT 算法的理論Fmeasure值相近時(shí)，各類平移鏡像函數(shù)MART 算法（MART_T、MART_T_R、MART_T_N）的檢錯(cuò)有效性最強(qiáng)，并且對維度變化不敏感.ART 算法、各類對稱鏡像函數(shù)MART 算法（MART_R、MART_R_R、MART_R_N）受維度變化影響大，隨著輸入空間維度增大，F(xiàn)ratio值增大.

5.1.2.4 失效率的影響分析

由于鏡像順序選擇序MART 算法在子域數(shù)量大于RT 的理論Fmeasure值時(shí)，檢錯(cuò)有效性迅速下降. 所以下面分析只涉及到鏡像隨機(jī)選擇序MART 算法、鏡像受限選擇序MART算法.

分析在三維輸入空間中，失效率分別為0.1、0.05、0.01、0.005、0.001時(shí)（RT 的理論Fmeasure值為10、20、100、200、1 000），鏡像深度分別取ω=1，2，3，4，子域數(shù)量分別為8、64、512、4 096，ART 算法、鏡像隨機(jī)選擇序MART 算法、鏡像受限選擇序MART 算法的Fratio值如圖11所示.

（1）不同失效率時(shí)，F(xiàn)ratio值分析

深度為1、2、3 對應(yīng)的子域數(shù)量（8、64、512）與失效率0.1、0.01、0.005（RT 的理論Fmeasure值為10、100、200）相近. 如圖11（a）、（c）、（e）所示，失效率為0.1、0.01、0.001 時(shí)，鏡像平移函數(shù)的MART 算法分別在深度為1、2、3 時(shí)Fratio值最低，且MART_T_R、MART_T_N 算法Fratio值相近. 隨著深度的增大，MART_T_N 算法比MART_T_R算法的優(yōu)勢增大，F(xiàn)ratio值差距增大.

如圖11（a）、（b）、（d）所示，各類MART 算法的Fratio值都高于ART 算法，隨著深度的增加，子域數(shù)量的增多，MART_T_N 算法與MART_T_R 算法的Fratio值差異增大，優(yōu)勢增大.

（2）不同失效率時(shí)，F(xiàn)ratio值分析

分析MART_T_N 算法在鏡像劃分深度分別為1、2、3、4時(shí)的表現(xiàn)，以便指其在實(shí)際應(yīng)用中鏡像劃分深度參數(shù)的設(shè)置.

如表2 所示，鏡像劃分深度與RT 算法的理論Fmeasure值相近時(shí)，MART_T_N 算法具有較高的檢錯(cuò)能力，甚至優(yōu)于ART 算法的Fratio值. 整體來看，隨著鏡像劃分深度的增加，子域數(shù)量的增大，MART_T_N 在各失效率下檢錯(cuò)能力下降.

表2 不同失效率，不同深度下MART_T_N算法的Fratio值

5.2 實(shí)例實(shí)驗(yàn)

5.2.1 實(shí)驗(yàn)設(shè)計(jì)

5.2.1.1 測試基準(zhǔn)程序

本次實(shí)驗(yàn)有四個(gè)真實(shí)程序，其中Trityp 程序和TCAS 程序是來源于Software artifact Infrastructure Repository（SIR）的被測程序.Integer 程序源于JDK 中java.lang.Integer 類. DSCompiler 類來源于org.apache.commons.math3.analysis.differentiation包. 詳情如表3所示.

表3 四個(gè)實(shí)例被測程序的詳情

Trityp 程序?yàn)槿切畏诸惓绦颍? 個(gè)整型輸入作為三邊長度，輸出是否能構(gòu)成三角形以及屬于哪類三角形.Mujava 變異測試工具用來生成被測程序的變異體，每個(gè)變異體是在源程序中注入一個(gè)錯(cuò)誤來生成的.Trityp 程序一共生成462 個(gè)變異體. 去除72 個(gè)等價(jià)變異體，剩余390 個(gè)變異體. 假定整型輸入域范圍為［1，100］，每個(gè)變異體的失效率通過程序輸入?yún)?shù)遍歷整個(gè)輸入域計(jì)算得到. 實(shí)驗(yàn)選擇失效率在（0.000 1，1）范圍內(nèi)的368個(gè)變異體.

TCAS是經(jīng)典的西門子程序之一，是有12個(gè)輸入?yún)?shù)的防撞系統(tǒng)源代碼. 輸入域范圍為［0，1 000］. 變異體來源于SIR，這些變異體種的失效源于真實(shí)的錯(cuò)誤.變異體失效率在［0.000 01，0.04］范圍內(nèi).

Integer 程序源于JDK 中java.lang.Integer 類，2 個(gè)輸

圖11 在3維空間，各算法1～4深度的Fratio值（除順序鏡像序）入?yún)?shù)取值范圍為［1，1 000］. Integer 程序使用mujava生共160 個(gè)變異體，去除21 個(gè)等價(jià)變異體，剩余139 個(gè)變異體的失效率在［0.000 9，1）范圍內(nèi).

DSCompiler 類來源于org.apache.commons.math3.analysis.differentiation 包，Apache Commons 類 庫 中math3 類庫為輕量級數(shù)學(xué)和統(tǒng)計(jì)組件. 使用Mujava 生成共計(jì)7 294 個(gè)變異體，失效率為［0.000 01，1）范圍內(nèi).

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

本實(shí)驗(yàn)對比的鏡像隨機(jī)選擇序算法、鏡像受限選擇序算法. 通過第5.1 節(jié)仿真實(shí)驗(yàn)分析，平移鏡像函數(shù)在MART 算法中較對稱鏡像函數(shù)更有效，所以本實(shí)驗(yàn)只考慮平移鏡像函數(shù).

鏡像隨機(jī)選擇序MART算法（MART_T_R）：采用對等劃分的方式對輸入空間進(jìn)行子域劃分，鏡像函數(shù)為平移鏡像函數(shù)，鏡像子域選擇方式為隨機(jī)序方式，源域中測試數(shù)據(jù)生成算法采用FSCS算法.

鏡像受限選擇序MART 算法（MART _T_N）：為本文提出的方法，鏡像函數(shù)為平移鏡像函數(shù).

實(shí)驗(yàn)執(zhí)行過程如下：分別使用MART_T_R 和MART_T_N 算法生成測試數(shù)據(jù)，執(zhí)行源程序及變異體.若變異體與源程序運(yùn)行結(jié)果不同，則此算法殺死該變異體，記錄當(dāng)前已生成測試數(shù)據(jù)數(shù)量.

針對每個(gè)有效變異體，分別記錄MART_T_R 和MART_T_N 殺死該變異體所需測試數(shù)據(jù)數(shù)量F-count，實(shí)驗(yàn)重復(fù)2 000 次均值作為Fmeasure. 令Frandom與Fnew分別 表 示MART_T_R 和MART_T_N 的Fmeasure，F(xiàn)ratio為MART_T_N 與MART_T_R 的Fmeasure比值，即MART_T_N 算法相對MART_T_R 算法檢錯(cuò)有效性改進(jìn)程度. 若Fratio＜1，說明MART_T_N算法優(yōu)于MART_T_R算法.

5.2.2 實(shí)驗(yàn)結(jié)果分析

四個(gè)程序使用MART_T_R 和MART_T_N 運(yùn)行后的Fratio值統(tǒng)計(jì)結(jié)果如表4所示. 表中列出每個(gè)程序變異體數(shù)量，統(tǒng)計(jì)出MART_T_N 算法與MART_T_R 算法的Fratio值大于等于1和小于1的情況. 在Trityp程序的368個(gè)變異體中，F(xiàn)ratio＜1 的變異體數(shù)量為294 個(gè)，即79.9%的變異中，MART_T_N 算法的檢錯(cuò)能力優(yōu)于MART_T_R 算法.Integer 程序的139 個(gè)變異體中，F(xiàn)ratio＜1 的變異體數(shù)量為112 個(gè)，即80.6%的變異中，MART_T_N 算法的檢錯(cuò)能力優(yōu)于MART_T_R 算法. TCAS 程序的20 個(gè)變異體中，F(xiàn)ratio＜1 的變異體數(shù)量為16 個(gè)，即80%的變異中，MART_T_N 算法的檢錯(cuò)能力優(yōu)于MART_T_R 算法.DSCompiler 類的7 294 個(gè)變異體中，F(xiàn)ratio＜1 的變異體數(shù)量為5 568個(gè)，即76.3%的變異中，MART_T_N算法的檢錯(cuò)能力優(yōu)于MART_T_R算法.

表4 實(shí)例程序變異體Fratio結(jié)果

在實(shí)例實(shí)驗(yàn)中，從MART_T_N 算法對各變異體檢錯(cuò)能力來看，MART_T_N 算法在實(shí)際程序代碼中，具有高于MART_T_R算法的檢錯(cuò)能力.

6 小結(jié)

鏡像策略將輸入域劃分多個(gè)鏡像子域，通過鏡像函數(shù)將源域中測試數(shù)據(jù)生成方法生成的測試數(shù)據(jù)鏡像到各鏡像子域中，從而生成整個(gè)輸入域內(nèi)的測試數(shù)據(jù).將鏡像策略用于ART 算法的測試數(shù)據(jù)生成過程中，減少了ART 算法的計(jì)算開銷，通過鏡像函數(shù)即可生成鏡像測試數(shù)據(jù).

但鏡像策略融入ART 算法后，雖然提高了測試數(shù)據(jù)生成的效率，但降低了算法的有效性. 本文對MART算法進(jìn)行了研究，針對鏡像函數(shù)將源測試數(shù)據(jù)鏡像到各子域時(shí)的鏡像順序，對比分析鏡像選擇序與鏡像函數(shù)對MART 算法的影響，提出了基于鏡像受限選擇序的MART 算法. 實(shí)驗(yàn)結(jié)果顯示，針對鏡像策略中鏡像選擇序的優(yōu)化，提高了MART 算法的檢錯(cuò)有效性，得到以下結(jié)論：

（1）鏡像平移函數(shù)的MART 算法多數(shù)情況下優(yōu)于鏡像對稱函數(shù)的MART算法，或與其相當(dāng)；

（2）當(dāng)鏡像劃分的子域數(shù)量與RT 算法理論Fmeasure值相近時(shí)，各類MART算法檢錯(cuò)能力最強(qiáng).

（3）當(dāng)劃分子域數(shù)量大于RT算法理論Fmeasure值，鏡像選擇序?qū)ART 算法影響較大. 鏡像順序選擇序的MART 算法的檢錯(cuò)能力急速下降，所以，不適宜用于鏡像劃分子域數(shù)量較多的場景.

（4）本文提出的鏡像受限選擇序MART 算法檢錯(cuò)有效性高于鏡像隨機(jī)選擇序MART 算法. 隨著鏡像劃分深度、輸入空間維度越大，鏡像受限選擇序MART 算法的優(yōu)勢越明顯.