蛻變關(guān)系敏感度及其聚類分析

謝曉東,彭聲明,劉　艷,汪康煒,王　田,王　成

(華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,福建廈門 361021)

?

蛻變關(guān)系敏感度及其聚類分析

謝曉東,彭聲明,劉艷,汪康煒,王田,王成

(華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,福建廈門 361021)

為緩解軟件測(cè)試的Oracle問題，蛻變測(cè)試通過驗(yàn)證多個(gè)測(cè)試用例及其輸出之間是否滿足蛻變關(guān)系來驗(yàn)證測(cè)試結(jié)果.可見蛻變關(guān)系是蛻變測(cè)試的核心，而現(xiàn)有的蛻變關(guān)系檢錯(cuò)能力的衡量標(biāo)準(zhǔn)，即錯(cuò)誤檢出率(Failure Detecting Rate，F(xiàn)DR)是蛻變關(guān)系對(duì)不同變體的錯(cuò)誤檢出概率的平均值，這掩蓋了蛻變關(guān)系的一些重要特征.因而本文提出蛻變關(guān)系敏感度的概念，即用蛻變關(guān)系對(duì)不同變體的錯(cuò)誤檢出率所構(gòu)成的多維信息向量，來全面地反映蛻變關(guān)系特征，從而為蛻變測(cè)試研究提供更多的可能性.蛻變關(guān)系敏感度的一個(gè)典型應(yīng)用是對(duì)蛻變關(guān)系集合進(jìn)行聚類分析，并挖掘出構(gòu)建蛻變關(guān)系的需求特征與錯(cuò)誤發(fā)現(xiàn)能力之間的關(guān)聯(lián).論文使用經(jīng)典聚類算法k-means進(jìn)行了實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，蛻變關(guān)系敏感度能很好地支持聚類分析計(jì)算，并能挖掘出有用的知識(shí).蛻變關(guān)系敏感度為蛻變測(cè)試的進(jìn)一步研究提供了新的方法和依據(jù).

蛻變測(cè)試;蛻變關(guān)系;蛻變關(guān)系敏感度;聚類算法

1　引言

為緩解軟件測(cè)試中的Oracle問題[1]，Chen[2～4]提出了蛻變測(cè)試方法.蛻變測(cè)試通過驗(yàn)證待測(cè)試程序的多個(gè)測(cè)試用例及它們的輸出結(jié)果之間是否滿足特定的關(guān)系(稱之為蛻變關(guān)系)來確認(rèn)待測(cè)程序是否存在錯(cuò)誤.蛻變測(cè)試無需構(gòu)造預(yù)期輸出即可驗(yàn)證執(zhí)行結(jié)果的正確性，從而緩解了Oracle問題.蛻變關(guān)系是蛻變測(cè)試的核心，是根據(jù)被測(cè)程序的需求特征或約束關(guān)系等構(gòu)造而成的.根據(jù)待測(cè)程序的需求可以構(gòu)造出大量的蛻變關(guān)系[5].這些蛻變關(guān)系從不同側(cè)面表達(dá)了待測(cè)程序部分需求信息和隱式約束.

對(duì)蛻變關(guān)系進(jìn)行研究的一個(gè)重要內(nèi)容是對(duì)其檢錯(cuò)能力進(jìn)行分析.目前通常采用錯(cuò)誤發(fā)現(xiàn)率FDR(failure detecting ration)來刻畫蛻變關(guān)系的檢錯(cuò)效率[6].Cao[7]等研究了BCMD等6種不同的先驗(yàn)衡量方法，通過分析源用例和衍生用例之間執(zhí)行路徑的差別來預(yù)測(cè)蛻變關(guān)系的檢錯(cuò)能力，該研究以FDR為基準(zhǔn).而Dong等在研究復(fù)合蛻變關(guān)系中也使用了FDR[8,9].然而，F(xiàn)DR從統(tǒng)計(jì)上掩蓋了蛻變關(guān)系檢錯(cuò)能力的一個(gè)重要特征：多維特性，即蛻變關(guān)系對(duì)不同類型的錯(cuò)誤的檢錯(cuò)能力是不同的.這使得在研究中可能因缺乏必要的信息難以進(jìn)行更進(jìn)一步的分析.例如，對(duì)蛻變關(guān)系進(jìn)行基于檢錯(cuò)能力的分類，僅依靠FDR將無能為力.

針對(duì)蛻變關(guān)系檢錯(cuò)能力的多維特性，本文提出了蛻變關(guān)系敏感度的概念，即用多維信息向量來表示蛻變關(guān)系對(duì)不同變體的錯(cuò)誤發(fā)現(xiàn)率.敏感度的每一維都代表蛻變關(guān)系對(duì)某個(gè)變體或變體子集的檢錯(cuò)效率.敏感度從整體上刻畫了蛻變關(guān)系的檢錯(cuò)能力的特征，更大程度地保留相關(guān)信息，從而為蛻變測(cè)試的研究提供了更好的檢錯(cuò)能力分析依據(jù)和可能性.

例如，聚類分析是一種常用的數(shù)據(jù)挖掘方法，主要用于將對(duì)象分類并分析其相似性[10,11].蛻變測(cè)試中可以產(chǎn)生大量的蛻變關(guān)系，這些蛻變關(guān)系所表達(dá)的需求信息和約束對(duì)程序正確性的影響是非常重要的研究?jī)?nèi)容.基于蛻變關(guān)系敏感度，可以使用聚類算法，如k-means進(jìn)行分類并分析它們之間的關(guān)聯(lián)，而FDR對(duì)此無能為力.

2　相關(guān)背景

蛻變測(cè)試是一種黑盒測(cè)試技術(shù)，它是通過驗(yàn)證蛻變關(guān)系來確認(rèn)待測(cè)程序是否存在錯(cuò)誤.例如，當(dāng)測(cè)試sin(x)的程序時(shí),很難直接得到測(cè)試用例x=29的預(yù)期輸出.但可以利用sin函數(shù)的特性：當(dāng)90>x1>x2>0時(shí)，有sin(x1)>sin(x2)，從而通過驗(yàn)證sin(30)>sin(29)是否成立來判斷待測(cè)程序是否存在錯(cuò)誤.

通常執(zhí)行一次蛻變測(cè)試需要進(jìn)行以下4個(gè)步驟：(1)選擇一個(gè)源用例，如上述例子中的x1=29；(2)根據(jù)蛻變關(guān)系和源用例，給出相應(yīng)的衍生用例，如上例中的x2=30；(3)分別執(zhí)行源用例和衍生用例，得到它們的執(zhí)行結(jié)果；(4)檢查源用例、衍生用例及它們的執(zhí)行結(jié)果是否滿足蛻變關(guān)系，如果滿足則該次測(cè)試通過，否則就發(fā)現(xiàn)一個(gè)錯(cuò)誤.

從一個(gè)待測(cè)程序的需求可以產(chǎn)生很多蛻變關(guān)系.例如，根據(jù)sin函數(shù)的特征，可以給出諸如sin(x)=sin(180-x),sin(x)=sin(360+x),sin(x)=sin(720+x),…，等多個(gè)蛻變關(guān)系.理論上，任一待測(cè)程序的蛻變關(guān)系是無窮多的.因此如何衡量和選擇檢錯(cuò)能力高的蛻變關(guān)系用于蛻變測(cè)試是一個(gè)重要的研究課題.

3　蛻變關(guān)系敏感度模型

3.1蛻變關(guān)系敏感度定義

FDR的定義隱含著一個(gè)假設(shè)：蛻變關(guān)系對(duì)不同錯(cuò)誤的揭示能力是相同的.然而這不正確.例如，令程序P實(shí)現(xiàn)了函數(shù)f(a,b)=a*b,根據(jù)乘法滿足交換律的特征，可以構(gòu)造蛻變關(guān)系MR：f(a,b)=f(b,a).對(duì)該程序的兩個(gè)變體，m1(a,b)=a+b，m2(a,b)=a-b，MR很難發(fā)現(xiàn)變體m1的錯(cuò)誤，卻能輕易發(fā)現(xiàn)m2的錯(cuò)誤.因?yàn)閙1的錯(cuò)誤之處是乘法變成加法，而加法也滿足交換律，MR無法區(qū)分變體和正確程序.因此，蛻變關(guān)系對(duì)不同的錯(cuò)誤有不同的揭示能力.而FDR用平均值來衡量蛻變關(guān)系的檢錯(cuò)能力，掩蓋了蛻變關(guān)系的這一特性.

蛻變關(guān)系敏感度是一個(gè)多維信息向量，當(dāng)需要對(duì)多個(gè)蛻變關(guān)系進(jìn)行排序時(shí)，可以通過簡(jiǎn)單的統(tǒng)計(jì)函數(shù)轉(zhuǎn)化為某種形式的標(biāo)量，例如將各維分量進(jìn)行簡(jiǎn)單的求和或取平均值.使用退化后的度量值對(duì)蛻變關(guān)系進(jìn)行排序的結(jié)果和使用FDR近似.

顯然，蛻變關(guān)系敏感度是將FDR細(xì)化到了每一變體上，從而避免由于平均化而從統(tǒng)計(jì)上掩蓋各蛻變關(guān)系在錯(cuò)誤檢出能力上的差異.

3.2基于變體子集的蛻變關(guān)系敏感度

在3.1節(jié)的討論中所給出的蛻變關(guān)系敏感度的維度等于變體個(gè)數(shù)，這使得敏感度的維度過高不利于后續(xù)的比較.因此，可以采用某些簡(jiǎn)化的方法得到維度較低的蛻變關(guān)系敏感度.

顯然，基于變體子集的蛻變關(guān)系敏感度大大降低了維度，從而降低比較蛻變關(guān)系檢錯(cuò)能力的難度.如何劃分變體集合，對(duì)敏感度的計(jì)算結(jié)果有很大的影響.特別的，當(dāng)將變體集合僅劃分成一個(gè)子集，那么蛻變關(guān)系敏感度將退化成為FDR.在本文的研究中，把通過同一變異算子所產(chǎn)生的變體劃分為一個(gè)子集.由于變異算子的典型性，這種劃分方式使得同一子集中的變體具有一定程度上的相似性，所得到的敏感度與蛻變關(guān)系檢錯(cuò)能力更具有相關(guān)性.

4　基于蛻變關(guān)系敏感度的聚類分析算法

蛻變關(guān)系敏感度是蛻變關(guān)系研究的一種基礎(chǔ)度量，可以運(yùn)用于各種場(chǎng)合.對(duì)蛻變關(guān)系集合進(jìn)行聚類分析是一種典型的應(yīng)用.

在蛻變測(cè)試研究和應(yīng)用中，常常會(huì)產(chǎn)生大量的蛻變關(guān)系.這些蛻變關(guān)系之間存在著一定的關(guān)聯(lián)，如有些蛻變關(guān)系由相同或相似的需求衍生而來，或有部分蛻變關(guān)系是由其他蛻變關(guān)系復(fù)合而成的.因此，如果能將這些蛻變關(guān)系分類，對(duì)研究和應(yīng)用蛻變關(guān)系有重要的意義.

對(duì)大量蛻變關(guān)系進(jìn)行敏感度分析，可得到一個(gè)敏感度矩陣.得到敏感度矩陣后，即可使用經(jīng)典的聚類算法K-means對(duì)蛻變關(guān)系進(jìn)行聚類分析，如算法1所示.算法中的另一輸入?yún)?shù)，蛻變關(guān)系類型數(shù)量k，可根據(jù)蛻變關(guān)系的相關(guān)特征事先指定，也可通過其他算法如層次聚類算法進(jìn)行初步分析得到.

5　實(shí)驗(yàn)

為驗(yàn)證蛻變關(guān)系敏感度對(duì)蛻變關(guān)系檢錯(cuò)能力的評(píng)價(jià)及使用算法1進(jìn)行聚類分析的可行性，進(jìn)行了一系列相關(guān)實(shí)驗(yàn).

5.1實(shí)驗(yàn)程序及變體

實(shí)驗(yàn)選取了一個(gè)圖論的程序代碼以及一個(gè)日期計(jì)算程序作為被測(cè)程序.第一個(gè)程序?qū)崿F(xiàn)了迪杰斯特拉最短路徑算法(Dijkstra's Shortest Path Algorithm,DSPA).該算法是在一個(gè)無向圖G中，尋找節(jié)點(diǎn)a到節(jié)點(diǎn)b的最短路徑.第二個(gè)程序(Days)的輸入為兩個(gè)日期的年月日，輸出為這兩個(gè)日期相差的天數(shù).

實(shí)驗(yàn)程序的變異是通過工具M(jìn)uJava實(shí)現(xiàn)的，各實(shí)驗(yàn)程序使用變異算子得到的變體的數(shù)目如表1所示.在后續(xù)研究中，變體集合根據(jù)變異算子進(jìn)行劃分.對(duì)DSPA程序，共構(gòu)造了9個(gè)蛻變關(guān)系(MR1～MR9)，基本情況如表2所示.對(duì)Days程序，共構(gòu)造了10個(gè)蛻變關(guān)系(MR-1～MR-10)，基本情況如表3所示.

表1　實(shí)驗(yàn)程序的變體情況

5.2實(shí)驗(yàn)步驟和實(shí)驗(yàn)結(jié)果

在實(shí)驗(yàn)過程中，首先生成實(shí)驗(yàn)程序的變體.然后為每一實(shí)驗(yàn)程序生成一個(gè)包含1000個(gè)用例的測(cè)試用例集合，該集合的測(cè)試用例將作為蛻變測(cè)試中的源用例.對(duì)DSPA程序所需要的無向圖，每一無向圖中至少包含10個(gè)頂點(diǎn)，無向圖中頂點(diǎn)的個(gè)數(shù)、頂點(diǎn)之間是否存在邊、邊的權(quán)重等內(nèi)容均隨機(jī)生成.而作為DSPA輸入?yún)?shù)的起點(diǎn)和終點(diǎn)也從無向圖中隨機(jī)選擇.衍生用例根據(jù)蛻變關(guān)系和源用例產(chǎn)生.而對(duì)Days程序，所輸入的年月日數(shù)據(jù)都是簡(jiǎn)單的整數(shù)，因此測(cè)試用例的數(shù)據(jù)是在取值范圍內(nèi)隨機(jī)進(jìn)行選擇.

使用源用例和衍生用例對(duì)變體進(jìn)行測(cè)試，并統(tǒng)計(jì)變體被殺死的情況，可得到相應(yīng)蛻變關(guān)系集合的敏感度矩陣，表4為DSPA的敏感度矩陣，表5為Days的敏感度矩陣.

為使用蛻變關(guān)系敏感度對(duì)蛻變關(guān)系檢錯(cuò)能力進(jìn)行評(píng)價(jià)，表6給出了各蛻變關(guān)系的FDR值及平均敏感度.根據(jù)算法1，對(duì)MR1～MR9以及MR-1～MR-10分別進(jìn)行了聚類分析，分析中類別數(shù)目設(shè)定為2，分析結(jié)果如表7所示.

表2　DSPA的蛻變關(guān)系

表3　Days的蛻變關(guān)系

表4　DSPA蛻變關(guān)系的敏感度矩陣

表5　Days蛻變關(guān)系的敏感度矩陣

表6　FDR與平均敏感度

表7　基于敏感度的聚類

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

從表6可以看出，根據(jù)FDR和平均敏感度對(duì)DSPA蛻變關(guān)系的進(jìn)行檢錯(cuò)能力的排序結(jié)果相同.Days蛻變關(guān)系的排序結(jié)果中，原來MR-5=MR-6>MR-2變成了MR-5=MR-6=MR-2.其原因在于，實(shí)驗(yàn)中使用了子集劃分法簡(jiǎn)化敏感度，當(dāng)對(duì)簡(jiǎn)化敏感度求平均值時(shí)，實(shí)際上是對(duì)原始的敏感度進(jìn)行了加權(quán)平均.而FDR是原始敏感度的簡(jiǎn)單平均值.因此在子集劃分中，如果某個(gè)子集的變體數(shù)目偏少，那么該子集的變體的權(quán)重較大.實(shí)驗(yàn)中，COR和AOD的變體數(shù)較少，因而蛻變關(guān)系對(duì)相應(yīng)子集變體的檢錯(cuò)能力對(duì)敏感度平均值有較大的影響.

從表7可以看出，通過基于敏感度的蛻變關(guān)系聚類分析算法，將DSPA的蛻變關(guān)系劃分為{MR4,MR5,MR6,MR7}和{MR1,MR2,MR3,MR8,MR9}；而Days的蛻變關(guān)系被劃分為{MR-1,MR-2,MR-3,MR-4,MR-5,MR-6}和{MR-7,MR-8,MR-9,MR-10}.結(jié)合各蛻變關(guān)系本身的特征，可以歸納出一些知識(shí)：(1)起點(diǎn)終點(diǎn)參數(shù)對(duì)DSPS實(shí)驗(yàn)程序有較為重要的影響；(2)在Days實(shí)驗(yàn)程序中，對(duì)年月日進(jìn)行增減這一類的蛻變關(guān)系，其錯(cuò)誤檢出能力較小.

6　結(jié)束語

蛻變測(cè)試能有效地緩解傳統(tǒng)軟件測(cè)試中的Oracle問題.蛻變關(guān)系對(duì)蛻變測(cè)試至關(guān)重要，也是蛻變測(cè)試的研究重點(diǎn).現(xiàn)有文獻(xiàn)中使用FDR作為蛻變關(guān)系檢錯(cuò)能力的衡量準(zhǔn)則，使得蛻變關(guān)系檢錯(cuò)能力的多維特性被掩蓋了.蛻變關(guān)系敏感度是由蛻變關(guān)系對(duì)不同變體的檢錯(cuò)效率構(gòu)成的多維信息向量，能更加全面地反映蛻變關(guān)系的多維特性，從而更有力地支持蛻變測(cè)試的研究.

本文給出了蛻變關(guān)系敏感度及簡(jiǎn)化的基于變體子集劃分的蛻變關(guān)系敏感度的定義和計(jì)算方法.在此基礎(chǔ)上使用k-means聚類算法對(duì)蛻變關(guān)系集合進(jìn)行分類.實(shí)驗(yàn)表明蛻變關(guān)系敏感度能很好地支持聚類分析，并能得到蛻變關(guān)系的有意義的知識(shí).

蛻變測(cè)試研究中的一個(gè)難點(diǎn)是：每一蛻變關(guān)系都是從軟件需求中抽取的，蛻變關(guān)系之間的聯(lián)系很難定義，進(jìn)而難以得到蛻變關(guān)系之間的共性.蛻變關(guān)系敏感度的引入，從檢測(cè)能力的角度揭示了蛻變關(guān)系之間的聯(lián)系，為蛻變關(guān)系的錯(cuò)誤檢測(cè)能力研究提供了一個(gè)新的視角和工具.因此蛻變關(guān)系敏感度將有力地推動(dòng)蛻變測(cè)試的研究.

在本文后續(xù)研究中，將對(duì)變體子集劃分策略做進(jìn)一步的研究.此外，采用更加有效的聚類算法，如層次法，用于蛻變關(guān)系的聚類分析研究也是將來的研究?jī)?nèi)容之一.

[1]EJ Weyuker.On testing non-testable programs[J].The Computer Journal,1982,25(4):465-470.

[2]F Chan,TY Chen,SC Cheung,M Lau,S Yiu.Application of metamorphic testing in numerical analysis[A].In Proceedings of the Lasted International Conference on Software Engineering[C].New York:ACM Press,1998.191-197.

[3]TY Chen,SC Cheung,SM Yiu.Metamorphic testing:A new approach for generating next test cases[R].Technical Report HKUST-CS98-01,Department of Computer Science,Hong Kong University of Science and Technology,1998.1-11.

[4]TY Chen,TH Tse,ZQ Zhou.Fault based testing in the absence of an oracle[A].In Proceedings of the 25th IEEE Annual International Computer Software and Applications Conference[C].New York:IEEE Computer Society,2001.172-178.

[5]Mayer,Johannes,Ralph Guderlei.An empirical study on the selection of good metamorphic relations[A].In Proceeding of 30th Annual International Computer Software and Applications Conference[C].New York:IEEE Computer Society,2006.475-484.

[6]TY Chen,DH Huang,TH Tse,ZQ Zhou.Case studies on the selection of useful relations in metamorphic testing[A].In Proceedings of the 4th Ibero-American Symposium on Software Engineering and Knowledge Engineering[C].New York:IEEE Computer Society,2004.569-583.

[7]Y Cao,ZQ Zhou,TY Chen.On the correlation between the effectiveness of metamorphic relations and dissimilarities of test case executions[A].In Proceedings of 13th International Conference on Quality Software[C].New York:IEEE Computer Society,2013.153-162.

[8]Dong GW,Xu BW,Chen L,Nie CH,Wang LL.Case studies on testing with compositional metamorphic relations[J].Journal of Southeast University (English Edition),2008,24(4).437-443.

[9]Asrafi M,Liu H,Kuo FC.On testing effectiveness of metamorphic relations:A case study[A].In Proceedings of Fifth International Conference on Secure Software Integration and Reliability Improvement[C].New York:IEEE Computer Society,2011.147-156.

[10]J MacQueen.Some methods for classification and analysis of multivariate observations[A].In Proceedings of Fifth Berkeley Symposium on Mathematical Statistics and Probability[C].University of California,1967.281-297.

[11]PS Bradley,Usama M Fayyad.Refining Initial Points for K-Means Clustering[M].New York:John Wiley and Sons,1998.56-67.

謝曉東(通信作者)男,1976年10月出生，江西贛州人,講師、博士.分別在1997年、2000年和2007年于華中科技大學(xué)獲得工學(xué)學(xué)士、工學(xué)碩士和工學(xué)博士學(xué)位.1997年留校任教，2011年至今在華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院任教.

E-mail:xiaodongxie@hqu.edu.cn

彭聲明男，1990年4月出生，安徽安慶人，碩士研究生.2013年于安慶師范學(xué)院獲得工學(xué)學(xué)士學(xué)位.2013年至今在華僑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院攻讀碩士學(xué)位.

E-mail:pengshen0404@qq.com

Sensitivity of Metamorphic Relationships and Its Cluster Analysis

XIE Xiao-dong,PENG Sheng-ming,LIU Yan,WANG Kang-wei,WANG Tian,WANG Cheng

(CollegeofComputerScienceandTechnology,HuaqiaoUniversity,Xiamen,Fujian361021,China)

Metamorphic testing (MT) is proposed to alleviate oracle problem in software testing,which verifies software under testing (SUT) by checking whether inputs and outputs satisfy metamorphic relation (MR).MR,the constraint constructed from the propriety of SUT,plays a key role in MT and becomes focus in MT researching.Failure detecting ratio (FDR) is a popular measure for failure detecting ability of MR.However,FDR is the mean of failure detecting ratios of a MR applied on different mutants.This averaging covers some important properties of MR.In this paper,sensitivity of MR is defined,which is a multi-dimension information vector consisted of failure detecting ratios on all mutants.Sensitivity of MR reflects more fully characteristics of MR than FDR and allows more possibility in MT researching.One typical application of sensitivity of MR is the cluster analysis on MR set,in order to find some clues of the underlying relevant between the requirement of MR and its failure detecting ability.K-means algorithm,a classical cluster analysis algorithm,based on MR sensitivity is applied in the experiment.The experiment results show that the sensitivity of MR supports cluster analysis strongly and the analysis offers some useful knowledge.Sensitivity of MR will be a good method and essential rationale for MT researching.

metamorphic testing;metamorphic relation;metamorphic relation sensitivity;cluster analysis algorithm

2015-08-19；

2016-02-01；責(zé)任編輯：馬蘭英

國(guó)家自然科學(xué)青年基金(No.61103053，No.61202106，No.61572206)；福建省自然科學(xué)基金(No.2013J01238)；廈門市科技計(jì)劃項(xiàng)目(No.3502Z20143041)

TP311.1

A

0372-2112 (2016)05-1196-06

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.026