鄧?guó)櫜?張海波 左小凱

（武漢數(shù)字工程研究所 武漢 430074）

1 引言

當(dāng)我們對(duì)軟件進(jìn)行測(cè)試時(shí)，需要知道和輸入對(duì)應(yīng)的預(yù)期輸出，當(dāng)實(shí)際輸出和預(yù)期輸出不符時(shí)，可以說軟件出現(xiàn)了錯(cuò)誤。然而，在實(shí)際測(cè)試過程中可能會(huì)出現(xiàn)oracle 問題：一些程序的輸出無法預(yù)測(cè)，或者預(yù)測(cè)時(shí)會(huì)消耗大量資源［1，14］。為了解決oracle問題，Chen 等提出了蛻變測(cè)試的概念，采用這種方法時(shí)，無需構(gòu)造預(yù)期輸出，而是通過發(fā)掘程序輸入輸出之間的內(nèi)在聯(lián)系，構(gòu)造相應(yīng)的蛻變關(guān)系，直接通過判斷原始測(cè)試用例和衍生測(cè)試用例的執(zhí)行結(jié)果之間是否滿足蛻變關(guān)系來測(cè)試程序［2］。

在蛻變測(cè)試中，蛻變關(guān)系的構(gòu)造十分重要，實(shí)驗(yàn)結(jié)果表明，質(zhì)量好的蛻變關(guān)系能夠有效檢測(cè)程序故障，且故障檢測(cè)率與蛻變關(guān)系個(gè)數(shù)沒有直接關(guān)聯(lián)［3］。對(duì)于不同類型的錯(cuò)誤來說，蛻變關(guān)系的檢錯(cuò)能力也不同。如何選擇蛻變關(guān)系并使它們以一種協(xié)作和互補(bǔ)的方式達(dá)到最佳的測(cè)試效果，是蛻變測(cè)試中的一個(gè)重要問題［4］。針對(duì)蛻變關(guān)系選取的研究，主要采用實(shí)例分析的方法，對(duì)某些特定的待測(cè)程序，構(gòu)造出一系列的蛻變關(guān)系，然后通過分析比對(duì)它們的測(cè)試效果和結(jié)構(gòu)特點(diǎn)，總結(jié)出有效蛻變關(guān)系的選擇策略［5］。隨后采用變異測(cè)試的方法，向原始程序中注入故障（即變異），以此來代表程序員經(jīng)常犯的錯(cuò)誤［6］。

蛻變測(cè)試已經(jīng)在很多領(lǐng)域中得到了應(yīng)用，例如數(shù)值型程序、圖像處理軟件、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等存在oracle 問題的地方［11，13，15］。在本文中，由于Fisher 分類器算法本身的復(fù)雜性和模糊性，分類有一定的錯(cuò)誤率，得到的分類結(jié)果并不能與訓(xùn)練樣本完全一致，這就導(dǎo)致難以得到程序的預(yù)期輸出，從而無法判斷程序是否出現(xiàn)了錯(cuò)誤。當(dāng)分類器的類別和屬性增多，數(shù)據(jù)量愈發(fā)龐大，在對(duì)輸出進(jìn)行預(yù)測(cè)的時(shí)候變得更為困難。所以，本文將蛻變測(cè)試應(yīng)用于Fisher 分類器，構(gòu)造了富有針對(duì)性的協(xié)作互補(bǔ)的蛻變關(guān)系，并利用變異測(cè)試技術(shù)進(jìn)行了驗(yàn)證。

2 相關(guān)概念

2.1 蛻變關(guān)系

假設(shè)P 是為了實(shí)現(xiàn)函數(shù)f 的程序，f 的n 組輸入變量為x1，x2，…，xn(n ＞1)，那么將其對(duì)應(yīng)的函數(shù)輸出結(jié)果表示為 f(x1)，f(x2)，…，f(xn) 。如果x1，x2，…，xn滿 足 關(guān) 系r ，很 明 顯 f(x1)，f(x2)，…，f(xn)之間滿足的關(guān)系可以表示為rf，即：

可以稱(r，rf)是P 的蛻變關(guān)系［12］。

顯然，如果程序P 是正確的，那么它一定滿足下邊的式子：

其中I1，I2，…，In是程序P 對(duì)應(yīng)于x1，x2，…，xn的實(shí)際輸入，P(I1)，P(I2)，…，P(In)是相應(yīng)的輸出。在進(jìn)行測(cè)試時(shí)，可以通過檢查表達(dá)式（2）成立與否來驗(yàn)證程序P 是否正確。蛻變測(cè)試即是一種基于蛻變關(guān)系的測(cè)試［7］。

2.2 測(cè)試用例

由于蛻變測(cè)試方法的特殊性，往往需要先生成原始測(cè)試用例x1，x2，…，xn(n ＞1)，再結(jié)合蛻變關(guān)系(r，rf)產(chǎn)生相應(yīng)的衍生測(cè)試用例r(x1，x2，…，xn)。

因?yàn)檠苌鷾y(cè)試用例是由原始測(cè)試用例得到的，所以原始用例的選擇是一個(gè)重要環(huán)節(jié)，近幾年的研究提出了一些原始用例的生成方法，主要使用的是特殊值選取、隨機(jī)值選取和迭代生成［7］。

2.3 Fisher分類器

Fisher 分類器是線性分類器的一種，它的目的是通過尋找最佳投影方向把高維分類問題轉(zhuǎn)化為一維問題。具體來說，就是由提供的樣本數(shù)據(jù)（訓(xùn)練數(shù)據(jù)）來訓(xùn)練線性判別函數(shù)，而線性判別函數(shù)又由投影方向W 和閾值w0確定，同時(shí)要滿足投影后不同類的樣本相隔盡可能地遠(yuǎn)，而同類樣本盡可能地聚集。然后測(cè)試數(shù)據(jù)的類別就可以根據(jù)這個(gè)線性判別函數(shù)計(jì)算得到。

舉例來說，可以把兩類的線性判別問題看做是把所有樣本都投影到一個(gè)方向上，然后在這個(gè)一維空間中確定一個(gè)分類的閾值。與投影方向垂直且過這個(gè)閾值點(diǎn)的超平面就是兩類的分類面。

基本原理如圖1 所示，顯然投影方向的選擇對(duì)分類結(jié)果有很大影響。

圖1 投影方向?qū)Ψ诸惤Y(jié)果的影響

3 Fisher分類器程序蛻變關(guān)系的構(gòu)造

蛻變關(guān)系的構(gòu)造是蛻變測(cè)試的關(guān)鍵環(huán)節(jié)，也是蛻變測(cè)試中的難點(diǎn)。Upulee 針對(duì)數(shù)值計(jì)算程序提出了6 條通用蛻變關(guān)系［8］，但是并不完全適用于Fisher 分類器程序。同樣，Xie 在文章中闡述了適用于分類器的蛻變關(guān)系生成方法［9］，Sadam 將這些蛻變關(guān)系的生成方法進(jìn)行了拓展并進(jìn)行了驗(yàn)證［10］，然而這些方法依然無法做到完全通用，需要根據(jù)待測(cè)程序的特性構(gòu)造多樣的蛻變關(guān)系。另外，Jiang在圖像處理軟件的測(cè)試中，結(jié)合經(jīng)驗(yàn)將蛻變關(guān)系的構(gòu)造進(jìn)行了分類概括，從幾何屬性、數(shù)值屬性、算法特性出發(fā)構(gòu)造蛻變關(guān)系［11］。

考慮到Fisher 分類器程序的特性，本文結(jié)合Xie 和Jiang 的方法，從幾何屬性、數(shù)值屬性、算法特性三個(gè)方面出發(fā)，構(gòu)造適用于Fisher 分類器的蛻變關(guān)系。同時(shí)，在Fisher 分類器中，我們將對(duì)分類結(jié)果的判斷簡(jiǎn)化為對(duì)分類面的判斷，這樣能夠更直觀更方便地觀察到分類結(jié)果是否滿足蛻變關(guān)系，而且由于植入變異引發(fā)的變化雖然會(huì)對(duì)分類面產(chǎn)生影響，但并不總是能繼續(xù)影響到分類結(jié)果，所以直接觀察分類面的變化反而更加準(zhǔn)確。

在本文中為了更直觀地展示蛻變測(cè)試的效果，采用二維的Fisher 分類器，其結(jié)果同樣也適用于更高維數(shù)的Fisher分類器。

3.1 幾何屬性蛻變關(guān)系

由于Fisher 分類器程序的輸入是一組二維向量，并且結(jié)果可以用幾何形式表示出來，所以可以考慮從幾何屬性入手構(gòu)造蛻變關(guān)系。程序的輸入是作為訓(xùn)練樣本集的一組二維向量，這些向量采用坐標(biāo)法表示。所以，當(dāng)我們對(duì)輸入數(shù)據(jù)進(jìn)行幾何旋轉(zhuǎn)時(shí)，得到的分類面也會(huì)有相應(yīng)的幾何變化。以(0，0)為坐標(biāo)原點(diǎn)，構(gòu)建橫縱坐標(biāo)，原始輸入數(shù)據(jù)為I ，I 繞x 軸鏡像變換可得到新的輸入數(shù)據(jù)I，，I得到的分類面應(yīng)與I，得到的分類面關(guān)于x 軸鏡像對(duì)稱，即MR1。類似的，輸入數(shù)據(jù)繞y 軸鏡像變換可得到MR2。輸入數(shù)據(jù)繞原點(diǎn)鏡像變換可得到MR3。公式中Tsfx表示繞x 軸做鏡像變換，Tsfy表示繞y 軸做鏡像變換，Tsf 表示繞原點(diǎn)做鏡像變換，Surf 表示分類面。

3.2 數(shù)值屬性蛻變關(guān)系

由于Fisher 分類器程序的輸入是一組二維向量，所以當(dāng)我們將輸入數(shù)據(jù)做整體的增減和縮放時(shí)，根據(jù)分類器的數(shù)學(xué)原理，分類面會(huì)產(chǎn)生相應(yīng)的規(guī)律變化。在程序?qū)崿F(xiàn)的過程中，我們可以很便捷地記錄下分類面的法向量W 和閾值w0，所以此時(shí)可以通過法向量和閾值變化規(guī)律來檢測(cè)變異，更加精確直觀。對(duì)輸入數(shù)據(jù)整體增加常數(shù)b，分類面法向量W 不會(huì)產(chǎn)生變化，閾值w0增加常數(shù)b ，即MR4。同樣對(duì)輸入數(shù)據(jù)整體減去常數(shù)q，分類面法向量W 不會(huì)產(chǎn)生變化，閾值w0減去常數(shù)q，即MR5。對(duì)輸入數(shù)據(jù)整體按比例k 縮放，分類面法向量W 按比例1 k 縮放，閾值w0按比例k 縮放，即MR6。

3.3 算法特性蛻變關(guān)系

得益于分類器的基本性質(zhì)，當(dāng)我們把類標(biāo)簽進(jìn)行交換時(shí)，分類面應(yīng)當(dāng)保持不變。在本文中，把第一類樣本和第二類樣本的類標(biāo)簽進(jìn)行交換，不會(huì)影響分類面，即MR7。當(dāng)把類屬性進(jìn)行交換，在本文中反映為將樣本集的x 和y 交換時(shí)，結(jié)合分類器的數(shù)學(xué)原理，分類面會(huì)關(guān)于y=x 對(duì)稱，即MR8。另外，根據(jù)Fisher 分類器的數(shù)學(xué)特征，離散度越低的樣本集分類準(zhǔn)確度就越高，即MR9。公式中I1，I2表示把輸入數(shù)據(jù)分為兩類，Xi，Yi表示輸入的二維數(shù)據(jù)的橫縱坐標(biāo)，Sw 表示輸入數(shù)據(jù)的離散度，Acc表示分類準(zhǔn)確度，Tsfy=x表示繞y=x 軸做鏡像變換。

將所有蛻變關(guān)系匯總?cè)缦拢?/p>

4 實(shí)例驗(yàn)證

4.1 原始/衍生測(cè)試用例生成

采用Matlab 對(duì)Fisher 分類器進(jìn)行實(shí)現(xiàn)，使用randn 函數(shù)隨機(jī)生成一組二維向量，并按照橫縱坐標(biāo)是否超越2 倍關(guān)系將其分為兩類，作為輸入樣本集。按照同樣的方法生成三組向量，均用坐標(biāo)法表示，這樣就有了三組原始測(cè)試用例。通過一組原始測(cè)試用例和蛻變關(guān)系，我們可以為每一條蛻變關(guān)系生成一組衍生用例。

4.2 變異的構(gòu)造

在蛻變測(cè)試的驗(yàn)證過程中，選擇合適的變異也是很重要的。在選擇變異時(shí)，要注意變異植入后不能使程序的結(jié)果出現(xiàn)較大偏差，同時(shí)植入的變異是在軟件開發(fā)中常見的錯(cuò)誤，盡量覆蓋到具有代表性的錯(cuò)誤類型。結(jié)合Fisher 分類器程序的實(shí)際情況，本文在程序中植入了五個(gè)變異：

M1：循環(huán)控制語句for i=1：length（X2）替換為

for i=1：length（X1）

M2：賦值語句m1（2，i）=Y1（i）；替換為m1（2，i）=Y2（i）；

M3：閾值計(jì)算語句w0=［mean（［X1 X2］）mean（［Y1 Y2］）］‘；替換為w0=-［mean（［X1 X2］）mean（［Y1 Y2］）］’；

M4：法向量計(jì)算語句W=Sw（M1-M2）；替換為W=（M1-M2）Sw；

M5：矩陣處理語句S1=zeros（2，2）；替換為S1=ones（2，2）；

4.3 測(cè)試結(jié)果

選取4.1中隨機(jī)生成的三組二維向量作為原始輸入，分別通過本文提出的九條蛻變關(guān)系對(duì)原始程序和植入變異后的五個(gè)程序進(jìn)行測(cè)試，Ori 表示未植入變異的原始程序。如果原始測(cè)試用例和衍生測(cè)試用例不滿足蛻變關(guān)系則記為0，相反如果原始測(cè)試用例和衍生測(cè)試用例滿足蛻變關(guān)系則記為1。

具體的執(zhí)行結(jié)果如下。

表1 原始數(shù)據(jù)1蛻變測(cè)試執(zhí)行結(jié)果

表2 原始數(shù)據(jù)2蛻變測(cè)試執(zhí)行結(jié)果

表3 原始數(shù)據(jù)3蛻變測(cè)試執(zhí)行結(jié)果

表4 蛻變關(guān)系對(duì)變異的綜合檢測(cè)率結(jié)果（百分率小數(shù)表示）

5 實(shí)驗(yàn)結(jié)論

通過實(shí)例的驗(yàn)證，綜合測(cè)試結(jié)果，可以得到如下結(jié)論：

1）觀察表1、表2、表3，不管采用三組中的哪一組數(shù)據(jù)，當(dāng)利用本文中提出的蛻變關(guān)系對(duì)變異體進(jìn)行測(cè)試時(shí)，所有的變異都能夠被檢測(cè)出來。同時(shí)，對(duì)于未植入變異的原程序，在相同的測(cè)試用例和條件下，都滿足蛻變關(guān)系，表明了原程序的正確性?？梢钥闯觯疚闹袑?duì)Fisher 分類器程序進(jìn)行的蛻變測(cè)試是行之有效的。

2）從表4 來看，Mr1～Mr8 的檢錯(cuò)效率較高，對(duì)于其檢測(cè)出來的變異都有著百分之百的檢錯(cuò)率。這是因?yàn)樗麄兊耐懽冴P(guān)系都為等式蛻變關(guān)系，并且它們都涉及到了Fisher 分類器核心的數(shù)學(xué)原理，即法向量和閾值。這使得它們對(duì)變異擁有很強(qiáng)的針對(duì)性，但是相應(yīng)的也會(huì)影響他們對(duì)不同變異的適用性。

3）Mr9 對(duì)變異的適用性最廣，出現(xiàn)的五個(gè)變異它都有一定幾率檢測(cè)出來，但是針對(duì)每個(gè)變異的檢錯(cuò)率都不高。這主要是因?yàn)樗捎玫氖遣坏仁降耐懽冴P(guān)系，對(duì)輸出結(jié)果的判定性比較弱，導(dǎo)致檢錯(cuò)率不高。但是由于它來源于分類器的普遍性質(zhì)，所以對(duì)各變異的適用性較廣。

4）Mr1～Mr3 的檢錯(cuò)率和適用性比較接近，Mr4～Mr6 比較接近，Mr7～Mr8 比較接近。蛻變關(guān)系之間根據(jù)檢錯(cuò)率和適用性自發(fā)的產(chǎn)生了分類的效果，這正好和前文蛻變關(guān)系的構(gòu)造過程中我們對(duì)它的分類相一致，分別對(duì)應(yīng)幾何屬性、數(shù)值屬性和算法特性，這說明在分類器的蛻變測(cè)試中，對(duì)蛻變關(guān)系分類構(gòu)造是可行且有效的。

5）綜合來看，Mr6 的檢錯(cuò)效果最好，它兼顧了檢錯(cuò)效率和適用性。它由于是成倍縮放的蛻變關(guān)系，所以對(duì)影響到執(zhí)行結(jié)果的變異比較敏感。從蛻變測(cè)試的執(zhí)行結(jié)果和檢錯(cuò)率情況可以看出，各條蛻變關(guān)系之間，各類蛻變關(guān)系之間可以進(jìn)行很好的互補(bǔ)，保證變異都能夠被檢測(cè)出來。

6）從植入的變異來看，由于影響到了循環(huán)執(zhí)行的次數(shù)，變異1 最容易被檢測(cè)出來。變異2、變異5涉及到了輸入數(shù)據(jù)的缺失和錯(cuò)誤，變異3 對(duì)重要參數(shù)閾值有影響，所以比較好檢測(cè)出。變異4 最難被檢測(cè)出來，因?yàn)樽儺愔踩牒蟪绦虻恼麄€(gè)運(yùn)行過程沒有發(fā)生太大變化，影響到的參數(shù)也比較少，對(duì)分類器原理幾乎沒有改變。

6 結(jié)語

由于Fisher 分類器存在著測(cè)試判定問題，根據(jù)以往的研究結(jié)果表明，蛻變測(cè)試在解決測(cè)試判定問題時(shí)有非常好的效果，所以本文對(duì)蛻變關(guān)系進(jìn)行分類構(gòu)造，從幾何屬性、數(shù)值屬性、算法特性出發(fā)構(gòu)造了適用于Fisher 分類器的蛻變關(guān)系，并將對(duì)分類結(jié)果的判斷簡(jiǎn)化為對(duì)分類面的判斷，這樣在觀察結(jié)果時(shí)更方便直觀，并且更加準(zhǔn)確。測(cè)試結(jié)果表明本文中提出的針對(duì)Fisher 分類器的蛻變測(cè)試是準(zhǔn)確且有效的，并且可以借鑒到一些分類器程序的測(cè)試過程中，使分類器蛻變關(guān)系的構(gòu)造更加簡(jiǎn)便和完善。在以后的工作中，由于變異的位置難以定位，可以考慮使用錯(cuò)誤定位技術(shù)，蛻變關(guān)系的構(gòu)造也可以繼續(xù)優(yōu)化，找出更通用、效果更好的蛻變關(guān)系，也可以對(duì)原始測(cè)試用例的生成方式進(jìn)行發(fā)掘。