余國清， 周蘭蓉， 羅可

(1. 長沙理工大學(xué) 計算機與通信工程學(xué)院， 湖南 長沙 410114；2. 湖南信息職業(yè)技術(shù)學(xué)院 計算機工程學(xué)院， 湖南 長沙 410200)

?

一種模糊K-means算法在測試用例集約簡中的應(yīng)用

余國清1,2， 周蘭蓉2， 羅可1

(1. 長沙理工大學(xué) 計算機與通信工程學(xué)院， 湖南 長沙 410114；2. 湖南信息職業(yè)技術(shù)學(xué)院 計算機工程學(xué)院， 湖南 長沙 410200)

為了提高軟件測試用例集約簡的成效，提出一種基于模糊K-means的軟件測試集用例約簡算法，引入模糊劃分思想，結(jié)合測試需求集，從各個簇中抽取測試用例，盡可能地發(fā)現(xiàn)相似的用例.實驗結(jié)果表明：算法能夠最小化約簡用例集，用例集覆蓋范圍最廣泛，錯誤率檢測較高.

用例約簡; 模糊K-means算法; 復(fù)雜度; 軟件測試

隨著互聯(lián)網(wǎng)、云計算等技術(shù)的快速發(fā)展，軟件功能及規(guī)模也迅速增大，程序開發(fā)潛在的錯誤和漏洞也逐漸增多[1-3].軟件測試可以在軟件開發(fā)完成之后，使用控制數(shù)據(jù)、加工數(shù)據(jù)等用例進行測試，發(fā)現(xiàn)軟件存在的錯誤，保證軟件的完整性、可靠性和準(zhǔn)確性.但是，大規(guī)模軟件需要設(shè)計較多的測試用例，造成人工測試模式定位難度大、耗費時間較長，不能夠快速定位和修改軟件錯誤[4-5].軟件測試用例約簡已經(jīng)成為降低軟件測試用例數(shù)量和提高測試成效的關(guān)鍵技術(shù)，許多學(xué)者對其進行了研究[6-11]，引入了集合約簡、關(guān)聯(lián)規(guī)則、專家數(shù)據(jù)庫等技術(shù)，在保持較高測試準(zhǔn)確度的條件下，大大減少了用例數(shù)量.軟件測試用例約簡仍存在用例集規(guī)模較大、用例重復(fù)出現(xiàn)、錯誤定位精確度小等問題.本文引入隸屬度函數(shù)改進K-means算法，旨在利用模糊數(shù)學(xué)提高軟件測試用例劃分的準(zhǔn)確度.

1 背景理論

1.1 軟件測試用例約簡

測試用例需要全覆蓋軟件的每一個步驟和環(huán)節(jié)，針對每一行代碼進行測試.軟件測試用例約簡是指在用例集T中，尋找一個最簡化的子集T′，該子集可以滿足所有的測試任務(wù).

1.2 模糊K-means算法

K-means算法采用硬聚類劃分思想，劃分過程較為武斷，不能夠充分地考慮測試用例的多個屬性，導(dǎo)致聚類結(jié)果與實際情況存在偏差.因此，為了能夠提高K-means算法的準(zhǔn)確度，假設(shè)軟件測試用例共有n個，每一個測試用例使用m個特征進行刻畫，則引入了隸屬度函數(shù)，使用隸屬度刻畫測試用例歸屬，提高數(shù)據(jù)對象劃分準(zhǔn)確性，易于解釋和描述．軟件測試用例為

(1)

式(1)中：xi，j表示樣本j的特征i，j=1,2,…,n，i=1,2,…,m.為了能夠更好的保證K-means算法正確執(zhí)行，算法運行之前需要對其檢修歸一化處理，即

(2)

式(2)中： xi，max表示第i個指標(biāo)特征的最大取值；xi，min表示第i個指標(biāo)特征的最小取值；ri，j表示歸一化后xi，j的取值.軟件測試用例集矩陣X歸一化之后為

(3)

軟件測試用例集X假設(shè)存在C個類別，則數(shù)據(jù)集X可以使用模糊識別矩陣進行描述，即

(4)

假設(shè)軟件測試樣本劃分類別h的m個特征向量值作為K-means算法的中心數(shù)據(jù)，則一個具有X個類別的軟件測試用例集擁有C個模糊聚類中心，即

(5)

式(5)中：si，h為類別h指標(biāo)i的歸一化特征值，0≤si，h≤1.

為了滿足不同的聚類用戶處理需求，在模糊聚類執(zhí)行過程中，可以針對不同的劃分設(shè)置不同的特征權(quán)值，以便能夠突出某些特征屬性的貢獻度，即

(6)

模糊K-means算法的目標(biāo)函數(shù)形式為

(7)

2 在測試用例機約簡中的應(yīng)用

在模糊K-means算法中，假設(shè)軟件測試用例集為T={t1,t2,…,tn}，數(shù)據(jù)集擁有的類別數(shù)目為K個，mi為第i個簇的中心，i=1,2,…k.模糊K-means的目標(biāo)函數(shù)為

(8)

式(8)中：b為一個常數(shù)，可以控制模糊K-means隸屬度.通過對模糊K-means的隸屬度函數(shù)求導(dǎo)數(shù)，可以獲取模糊K-means算法的最優(yōu)解，最優(yōu)解的求解過程分別為

(9)

(10)

模糊K-means算法使用程序，迭代執(zhí)行最優(yōu)化求解式(9)，(10)，可以針對軟件測試用例集進行劃分.具體的算法偽代碼流程如下.算法輸入：軟件測試用例約簡類簇數(shù)目K，隸屬度控制常數(shù)參數(shù)b，N個數(shù)據(jù)對象的軟件測試用例集.算法輸出：軟件測試用例約簡后的K個簇.算法有以下4個步驟.

步驟1 隨機化的將N個軟件測試用例分配到K個簇中，分派每一個簇的中心特征向量為mi.

步驟2 使用式(10)準(zhǔn)確計算獲取軟件測試用例的隸屬度函數(shù).

步驟3 使用式(9)重新計算軟件測試用例簇的中心值mi.

步驟4 計算每一個數(shù)據(jù)對象的隸屬度，直到隸屬度不再變化，終止算法運行；否則，返回步驟2.

由于在K-means算法基礎(chǔ)上，引入模糊控制b，可以根據(jù)模糊控制因子的取值經(jīng)驗.當(dāng)b=0.75時，能夠取得較好的約簡效果.基于此，可以分析測試用例的屬性相近程度.

3 實驗結(jié)果分析

3.1 數(shù)據(jù)集

采用SiemensCorporateResearch提供的軟件測試公共數(shù)據(jù)集，數(shù)據(jù)集1,2,3包含的用例數(shù)為30；數(shù)據(jù)集4,5,6,7包含的用例數(shù)為32.

3.2 評價標(biāo)準(zhǔn)

約簡算法的評價標(biāo)準(zhǔn)有算法約簡率(SR)、軟件錯誤檢測率(FDE)、軟件錯誤檢測丟失率(FL)3個方法，分別表示為

圖1 3種算法約簡率Fig.1 Three algorithms reduction rate

其中：|T|為軟件測試用例集的元素數(shù)；|T′|為約簡算法約簡后的軟件測試用例集中的元素數(shù)；|F|為未約簡的用例集測試軟件功能時檢測出來的錯誤數(shù)；|F′|為約簡后的用例集檢測出來的軟件功能錯誤數(shù).

3.3 結(jié)果分析

1) 約簡率比較.3種算法約簡率，如圖1所示.模糊K-means算法引入了模糊控制因子，可以動態(tài)地調(diào)整隸屬度特征權(quán)重，將概率值較為接近的軟件測試用例劃分到一起，在保證全覆蓋的條件下，可以有效提高K-means算法的約簡率，降低軟件測試的復(fù)雜度和工作量.

2) 軟件錯誤檢測率比較.3種算法檢錯率，如圖2所示.模糊K均值算法約簡后的測試用例能夠檢測出更多軟件錯誤數(shù)，表明文中算法約簡后的依然可以保持全覆蓋能力.另外兩種算法約簡后，把一些測試功能不同的用例劃分到一個簇中，這樣造成約簡后的用例無法全覆蓋軟件功能，錯誤檢測率較低.

3) 錯誤檢測丟失率比較.3種算法的錯誤檢測丟失率，如圖3所示.由圖3可知：矩陣行列變換算法、關(guān)聯(lián)模式約簡算法非常容易將不同覆蓋類型的用例約簡掉，因此，漏檢率較低，算法約簡效果不好.

圖2 3種算法檢錯率 圖3 3種算法錯誤檢測丟失率Fig.2 Three algorithms error rate Fig.3 Three algorithms error detection loss rate

4 結(jié)束語

在K-means算法中引入了隸屬度函數(shù)，采用模糊數(shù)學(xué)思想提高K-means算法劃分軟件測試用例集，可以提高用例約簡數(shù)量，并且保持用例集檢測軟件錯誤的可靠性.未來研究工作包括兩個關(guān)鍵內(nèi)容：引入模擬退火理論，實現(xiàn)模糊控制因子的自動化確定;針對軟件測試用例集進行泛化，提高算法的穩(wěn)定性和魯棒性.

[1] KUMAR G,BHATIA P K.Software testing optimization through test suite reduction using fuzzy clustering[J].Csi Transactions on Ict,2013,1(3):253-260.

[2] PAKINAM N B,NAGWA L B,MOHAMED H,et al.Test case generation and test data extraction techniques[J].International Journal of Electrical and Computer Sciences,2011,24(5):112-119.

[3] SUN F,TONG X H,XUE S F.A study of relative redundancy in test-suite reduction while retaining or improving fault-localization effectiveness[C]∥Proceedings of the 2010 ACM Symposium on Applied Computing.[S.l.]:ACM,2010:2229-2236.

[4] HAO D,XIE T,ZHANG L,et al.Test input reduction for result inspection to facilitate fault localization[J].Automated Software Engineering,2010,17(1):5-31.

[5] GONG Hongfang,LI Junyi.Generating test cases of cluster-level based on classes dependencies reduction[J].Jouranl of Central South University: Science and Technology,2010,41(1):238-244.

[6] GU Qing,TANG Bao,CHEN Daoxu.A test suite reduction technique for partial coverage of test requirements[J].Chinese Journal of Computers,2011,34(5):879-888.

[7] CHEN Jing,YANG Meihong,WANG Lu,et al.Regression test case reduction model based on association mode[J].Computer Engineering,2011,37(2):63-65.

[8] ZHOU Chongbo,LOU Jungang,CHENG Long.Test suites reduction based on matrix transformation[J].Application Research of Computer,2013,30(3):779-782.

[9] CHEN Yangmei,DING Xiaoming.Test suite reduction methods based on K-medoids[J].Computer Science,2012,39(6):422-424.

[10] SU Xiaohong,GONG Dandan,WANG Tiantian,et al.Automatic fault localization approach combining test case reduction and joint dependency probabilistic model[J].Journal of Software,2014,25(7):1492-1504.

[11] 劉竹松,陳潔.考慮數(shù)據(jù)不確定性的非均勻挖掘算法[J].華僑大學(xué)學(xué)報(自然科學(xué)版),2016,37(3):308-311.

(責(zé)任編輯： 陳志賢 英文審校： 吳逢鐵)

FuzzyK-Means Algorithm of Software Testing Using Case Reduction

YU Guoqing1,2, ZHOU Lanrong2, LUO Ke1

(1. Deptment of Computer and Communication Engineering,Changsha University of Science and Technology, Changsha 410114, China;2. School of Computer Engineering, Hunan College of Information Technology, Changsha 410200, China)

To improve the effectiveness of the software test set reduction, a software test set case reduction algorithm based on fuzzyKmeans is proposed. The fuzzy partition idea is introduced. The test suite is extracted from each cluster, finded similar cases. Experimental results showed that the algorithm can minimize the reduction case set, covers the most extensive and highly detect the error rate.

case reduction; fuzzyK-means software testing; complexity; software testing

10.11830/ISSN.1000-5013.201606024

2016-10-20

余國清(1971-)，男，副教授，主要從事人工智能、智能控制、數(shù)據(jù)挖掘的研究.E-mail:yuguoqing@mail.hniu.cn.

湖南省科學(xué)技術(shù)計劃項目(2011FJ3086)

TP 311

A

1000-5013(2016)06-0778-04