馮 霞， 王曙燕， 孫家澤

(西安郵電大學(xué) 計算機(jī)學(xué)院, 陜西 西安 710121)

基于K-means聚類的組合測試用例生成優(yōu)化算法

馮 霞， 王曙燕， 孫家澤

(西安郵電大學(xué) 計算機(jī)學(xué)院, 陜西 西安 710121)

針對組合測試生成的測試用例在程序結(jié)構(gòu)測試中出現(xiàn)冗余的問題，應(yīng)用K-means聚類算法對基于蟻群算法生成的組合測試用例集進(jìn)行聚類優(yōu)化。以白盒測試中的邏輯覆蓋為依據(jù)，將測試用例程序覆蓋差異度作為分類的量化標(biāo)準(zhǔn)，根據(jù)測試代價決定聚類數(shù)目，在每個聚類簇中抽取處于中心點(diǎn)的測試用例構(gòu)成新的集合。實(shí)驗(yàn)結(jié)果表明，該算法可以有效減小測試用例集的規(guī)模；對比分析不同覆蓋準(zhǔn)則，可找到在測試用例標(biāo)準(zhǔn)化過程中最優(yōu)的邏輯覆蓋方法。

K-means聚類算法；蟻群算法；組合測試；白盒測試

軟件測試是保證軟件可信度的重要手段，也是開發(fā)軟件系統(tǒng)的基本環(huán)節(jié)。在測試過程中選擇合適的用例驅(qū)動待測程序可以提高故障檢測能力。組合測試是一種有效的測試用例生成技術(shù)，其充分考慮各個因素以及它們之間的相互作用對軟件系統(tǒng)產(chǎn)生的影響，從統(tǒng)計學(xué)角度設(shè)計測試用例，能夠在保證錯誤檢出率的前提下采用較少的測試用例測試系統(tǒng)，力求用盡可能少的測試用例覆蓋盡可能多的影響系統(tǒng)的參數(shù)。將智能算法運(yùn)用到組合軟件測試中以其進(jìn)行優(yōu)化，如粒子群算法[1]、模擬退火算法[2]和蟻群算法[3]，可以有效降低軟件測試費(fèi)用，然而組合測試屬于黑盒測試，所生成的測試用例在白盒測試中可能會出現(xiàn)冗余。Jangbok Kim等[4]將白盒測試與組合測試相結(jié)合，提出了針對完整系統(tǒng)的兩兩組合測試覆蓋算法WBPairwise，但并沒有考慮到在系統(tǒng)參數(shù)眾多、測試用例數(shù)量十分龐大時如何進(jìn)一步優(yōu)化。

數(shù)據(jù)挖掘是處理大數(shù)據(jù)的有效途徑，在軟件測試中數(shù)據(jù)挖掘具有廣闊的應(yīng)用前景[5-6]。文獻(xiàn)[7]提出通過凝聚層次聚類對用戶交互測試用例進(jìn)行優(yōu)化，但因測試Web應(yīng)用十分復(fù)雜，很難實(shí)際有效地得到應(yīng)用。陳陽梅等[8]采用K中心點(diǎn)算法對測試用例進(jìn)行約簡，該方法采用K個中心點(diǎn)與非中心點(diǎn)的線性距離衡量各測試用例之間相異度，對于非數(shù)字形式的屬性缺乏客觀評價。本文根據(jù)白盒測試邏輯覆蓋準(zhǔn)則對判定路徑進(jìn)行標(biāo)準(zhǔn)化，找到各個測試用例所經(jīng)過的路徑差異，再運(yùn)用K均值聚類算法對蟻群算法優(yōu)化后的組合測試所得用例進(jìn)行分類，根據(jù)實(shí)際需要抽取測試用例，并對用例進(jìn)行優(yōu)化。

1 組合測試模型

某待測軟件系統(tǒng)(Software Under Testing，SUT)有n個參數(shù)，這些參數(shù)可以是外部輸入、內(nèi)部事件或者配置參數(shù)。對n個輸入?yún)?shù)中任意t個參數(shù)的所有取值組合進(jìn)行覆蓋，稱為覆蓋強(qiáng)度為t的組合測試。當(dāng)t=2時，稱為兩兩組合測試[9]。在最終生成的測試用例集中，所有軟件系統(tǒng)外部參數(shù)可能取值的兩兩組合至少覆蓋一次。

假設(shè)有一個待測軟件系統(tǒng)，該系統(tǒng)有4個參數(shù)，每個參數(shù)包含3個因子。如果采用窮舉測試方式，需要34=81個測試用例才能覆蓋所有的可能參數(shù)取值組合，而如果采用兩兩覆蓋組合測試，只需要9個測試用例就可以實(shí)現(xiàn)兩兩覆蓋，檢測出大部分的軟件錯誤[10]。

2 基于蟻群算法的組合測試

2.1 蟻群算法

蟻群算法是根據(jù)蟻群覓食活動規(guī)律建立的一個利用群體智能進(jìn)行優(yōu)化搜索的算法。蟻群算法包括兩個階段：適應(yīng)階段和協(xié)作階段。算法本身是根據(jù)一定規(guī)則隨機(jī)尋找最優(yōu)解。

(1)剛開始螞蟻隨機(jī)選擇路徑，每條從出發(fā)節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的路徑都對應(yīng)于一個解決方案，并且附有該路徑的增益。

(2)當(dāng)每只螞蟻到達(dá)結(jié)束節(jié)點(diǎn)時，在路徑的每條邊上釋放信息素，信息素的取值為信息素?fù)]發(fā)與螞蟻釋放信息素的綜合。

(3)螞蟻在選擇路徑時按照概率去選擇增益較大的邊。某一路徑經(jīng)過的螞蟻越多，后面的螞蟻選擇該路徑的概率越大。

最終，所有螞蟻會選擇一條增益較大的路徑，這是一個最優(yōu)或接近最優(yōu)的解。

2.2 基于蟻群算法的組合測試優(yōu)化方法

將蟻群算法應(yīng)用到組合測試中，采用one-test-at-a-time策略，以獲得最高總增益(即最優(yōu)測試質(zhì)量)為目標(biāo)生成測試用例。對每只螞蟻選擇的路徑進(jìn)行排序，將增益最大的作為當(dāng)前最優(yōu)解。蟻群算法具有一定的并行性，螞蟻的搜索過程彼此獨(dú)立，可以減少計算時間。此外，蟻群算法具有正反饋特性，通過判斷路徑信息素濃度選擇較短路徑。這樣可以保證在較少的時間內(nèi)生成有效的測試用例，減小測試用例集規(guī)模，降低測試成本。

假設(shè)某測試用例集有n個參數(shù)

F=(f1,f2,…,fn)，

每個參數(shù)有m個屬性

Vi=(Vi1,Vi2,…,Vim)。

每個屬性對應(yīng)有表示其重要程度的權(quán)值wim。

基于蟻群的組合測試用例生成算法[11]步驟如下。

步驟1 輸入螞蟻數(shù)、信息素矩陣，禁忌表置零。螞蟻?zhàn)畛蹼S機(jī)選擇下一節(jié)點(diǎn)并將其記錄到禁忌表中，修改所經(jīng)過路徑的信息素濃度。

步驟2 當(dāng)螞蟻選擇節(jié)點(diǎn)不在禁忌表中時，該節(jié)點(diǎn)可以訪問。依據(jù)轉(zhuǎn)移概率式[12]

(1)

計算下一節(jié)點(diǎn),其中h表示可訪問節(jié)點(diǎn),τij(t)表示t時刻邊(i,j)的信息素濃度，ηij(t)表示邊(i,j)相應(yīng)的啟發(fā)式的值。α和β分別反映了信息素濃度和啟發(fā)式的影響程度。

步驟3 螞蟻完成一次節(jié)點(diǎn)遍歷后，根據(jù)螞蟻選擇的路徑[12]，按照

步驟4 所有螞蟻巡回完畢后，對生成的候選解進(jìn)行排序，依據(jù)最優(yōu)解更新禁忌表。

步驟5 按步驟2至步驟4不斷循環(huán)，直到所選擇的路徑獲得最高增益。

3 基于K-means測試用例優(yōu)化算法

3.1 K-means算法

K-means算法是數(shù)據(jù)挖掘中著名的劃分聚類算法，它根據(jù)某一目標(biāo)函數(shù)將給定的數(shù)據(jù)劃分為k個簇，簇內(nèi)對象相似，而與其他簇中的對象差異較大。K-means算法把簇內(nèi)點(diǎn)的均值作為簇的中心。在聚類過程中先隨機(jī)選擇k個聚類中心，通過計算余下的點(diǎn)與中心點(diǎn)的歐式距離劃分所有數(shù)據(jù)，之后不斷迭代改變簇內(nèi)的變差。分別求出各個簇上一次迭代后所生成聚類簇的均值作為新的聚類中心，重新對所有數(shù)據(jù)進(jìn)行分類，直到分配的k個簇不再發(fā)生變化或滿足迭代次數(shù)。

3.2 K-means測試用例優(yōu)化技術(shù)

蟻群算法的組合測試用例生成技術(shù)雖然能夠有效的減少測試用例，但其基本思想仍然是黑盒測試。黑盒測試沒有清晰簡明的規(guī)格，缺乏對程序結(jié)構(gòu)的考慮。從白盒測試角度進(jìn)行分析時，測試用例可能會出現(xiàn)冗余。在白盒測試中，邏輯覆蓋包括語句覆蓋、判斷覆蓋、條件覆蓋、判斷/條件覆蓋、條件組合覆蓋和路徑覆蓋。本文以6種覆蓋方法為依據(jù)，結(jié)合覆蓋方案的不同要求，對已經(jīng)生成的測試用例進(jìn)行聚類優(yōu)化。

假設(shè)某待測系統(tǒng)有n個輸入?yún)?shù)，每個參數(shù)有m個可選項(xiàng)。通過蟻群算法后可以生成Z個測試用例，每個測試用例都含有n個參數(shù)?，F(xiàn)使用K-means聚類方法對Z個測試用例進(jìn)行分類。由于測試用例集與一般的數(shù)據(jù)不同，它們沒有固定的量化標(biāo)準(zhǔn)，因此測試用例聚類劃分標(biāo)準(zhǔn)的選擇尤為重要。對判定條件執(zhí)行進(jìn)行標(biāo)準(zhǔn)化記錄，根據(jù)測試用例在程序運(yùn)行時不同邏輯覆蓋準(zhǔn)則對判定條件執(zhí)行結(jié)果的要求不同，將測試用例轉(zhuǎn)化為由0-1表示的路徑數(shù)組，0表示沒有經(jīng)過該路徑，1表示經(jīng)過該路徑。轉(zhuǎn)化后，Z個測試用例由Z個路徑數(shù)組表示。

語句覆蓋要求程序中每條語句至少被執(zhí)行一次。判斷覆蓋要求每個判斷至少取一次為真，取一次為假，即程序中每個if條件的分支至少要執(zhí)行一次。條件覆蓋要求判斷中每個條件的每種可能性至少運(yùn)行一遍，如果if條件中包含多個判斷語句，每條語句為真為假的情況都應(yīng)區(qū)分開，成為不同的劃分路徑。判斷/條件覆蓋滿足了判斷覆蓋準(zhǔn)則，同時也滿足條件覆蓋準(zhǔn)則。條件組合覆蓋要求判斷中各條件結(jié)果可能性的組合至少出現(xiàn)一次。路徑覆蓋可以對程序進(jìn)行徹底的測試，設(shè)計用例測試所有可能的判定路徑。

以判斷/條件覆蓋為例，假設(shè)程序中有i個判斷條件，每個條件有成立或者不成立兩條路徑，即每個測試用例有2i項(xiàng)。這樣，每個測試用例所選擇的判斷路徑都可以唯一表示。在進(jìn)行聚類時，將每個測試用例與作為簇中心的測試用例相異或所求的選擇路徑差異程度D作為對測試用例進(jìn)行分類的量化標(biāo)準(zhǔn)。當(dāng)用例經(jīng)過的路徑相同或者相似時，參數(shù)D大小相近。在基于判斷/條件的聚類分析中，D是有效的分類依據(jù)。實(shí)際軟件測試過程中，可以依據(jù)測試的現(xiàn)實(shí)狀況，如程序結(jié)構(gòu)、時間緊迫性、規(guī)格要求等指定所需測試用例的個數(shù)k。依照K-means的一般算法將用例集劃分為k類即可得到k個簇。在各個簇中進(jìn)行抽樣，得到約簡后的測試用例集。算法的流程如圖1所示。

第二，組織做好《條例》的宣傳培訓(xùn)。按照干部職工牢固掌握、相關(guān)人員深入理解、社會公眾了解支持的要求，在“六五”普法期間，深入開展《條例》的宣傳。積極發(fā)揮新聞媒體、網(wǎng)絡(luò)的作用，通過多種方式和途徑在全流域廣泛開展宣傳活動，進(jìn)一步增強(qiáng)全社會愛水、護(hù)水、節(jié)水意識和水法制觀念，努力營造規(guī)模大、密度高、形式新的宣傳氛圍，確保廣大干部群眾深刻領(lǐng)會《條例》確立的基本原則、主要制度，準(zhǔn)確把握《條例》的深刻內(nèi)涵，增強(qiáng)貫徹實(shí)施的自覺性，保障《條例》的全面、順利、有效實(shí)施，全面提升流域綜合管理能力。

圖1 K-means組合測試用例生成優(yōu)化流程

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

4.1 實(shí)驗(yàn)設(shè)計

某文字處理軟件為待測系統(tǒng)，該軟件如表1所示，包含字體、字號、字體顏色、效果、字符間距、段落格式6個功能標(biāo)簽，每個標(biāo)簽包含10個選項(xiàng)，對于寫入其中的文字可以進(jìn)行設(shè)置。通過蟻群算法優(yōu)化選項(xiàng)的組合進(jìn)行測試，將6個功能標(biāo)簽作為旅行商問題中的城市節(jié)點(diǎn)，10個選項(xiàng)作為城市之間的不同路徑。之后在程序中執(zhí)行所得測試用例集，根據(jù)不同的邏輯覆蓋準(zhǔn)則進(jìn)行通過路徑的標(biāo)準(zhǔn)化，最后使用K-means聚類。觀察所得測試用例集的特點(diǎn)，這樣就可以驗(yàn)證所提出優(yōu)化算法的有效性。

表1 待測軟件系統(tǒng)

待測軟件系統(tǒng)的程序偽代碼為

If(commonly used typeface && textsize<50){

If(character scaling)

Then road1

If (warm color || good text effect){

Then road2

算法在eclipse編程環(huán)境下采用Java語言實(shí)現(xiàn)。其中蟻群算法涉及到的參數(shù)為：迭代次數(shù)150，螞蟻20只，α=1,β=3，信息素?fù)]發(fā)速率ρ=0.6，系統(tǒng)初始信息素濃度為0.5。對軟件系統(tǒng)進(jìn)行回歸測試時，根據(jù)時間緊迫程度以及實(shí)際任務(wù)需要，將測試用例聚集為4類。所以K-means得到的最終用例個數(shù)為4。

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

實(shí)驗(yàn)中首先使用微軟公司的配對測試工具PICT對于系統(tǒng)6個參數(shù)進(jìn)行兩兩配對組合測試，生成測試用例173個；其次使用經(jīng)過蟻群算法優(yōu)化后的組合測試用例生成方法生成73個測試用例；最后在第二項(xiàng)基礎(chǔ)上，采用基于K-means的測試用例優(yōu)化算法生成4個測試用例，通過聚類選擇出最佳測試用例，明顯減小了測試用例集。圖2為使用Weka數(shù)據(jù)挖掘軟件對本文提出的聚類算法進(jìn)行仿真，經(jīng)過多次迭代后所生成的4個聚類簇的分布狀況。

圖2 聚類結(jié)果

根據(jù)邏輯覆蓋中不同的覆蓋準(zhǔn)則對基于蟻群算法的組合測試進(jìn)行標(biāo)準(zhǔn)化后，使用K-means對測試用例進(jìn)行分類，4類的聚類情況如表2所示。表中的判定路徑表示，測試用例標(biāo)準(zhǔn)化時,由于覆蓋準(zhǔn)則的要求不同，程序執(zhí)行的判定結(jié)構(gòu)也不同。聚類簇1、聚類簇2、聚類簇3和聚類簇4為K-means聚類后生成的4個簇。6種邏輯覆蓋準(zhǔn)則發(fā)現(xiàn)錯誤的能力由弱至強(qiáng)變化，判定路徑越來越多，覆蓋范圍越來越全面。在語句覆蓋和判定覆蓋中，各測試用例的可選路徑較少，路徑差異小，所以聚類后測試用例分布不平衡，出現(xiàn)第四類用例個數(shù)為0，語句覆蓋中第一類占比63%，判定覆蓋中第二類占比56.2%的情形。隨著條件覆蓋、判斷/條件覆蓋、條件組合覆蓋、路徑覆蓋或者判定路徑逐漸增多，測試用例間的路徑差異會越來越大，故在使用K-means進(jìn)行劃分時，簇間差異會加大。路徑覆蓋對于程序結(jié)構(gòu)的檢測最為全面，判定路徑也最多，經(jīng)過多次聚類迭代后，4個簇中測試用例的數(shù)目接近25%，測試用例劃分均勻，聚類效果最好。

表2 K-means具體聚類情況分析

通過實(shí)驗(yàn)仿真，可以觀察到測試用例標(biāo)準(zhǔn)化時，采用路徑覆蓋準(zhǔn)則對于用例間差異路徑的區(qū)別最為詳盡。在此基礎(chǔ)上使用K-means聚類，可以克服組合測試所生成的測試用例在白盒測試方面出現(xiàn)的冗余。

5 結(jié)束語

將數(shù)據(jù)挖掘中K-means聚類算法與蟻群算法優(yōu)化后的兩兩組合測試用例生成技術(shù)相結(jié)合，提出了一種新的組合測試用例約簡算法。該算法采用白盒測試中邏輯覆蓋方法對測試用例進(jìn)行數(shù)據(jù)挖掘標(biāo)準(zhǔn)化，并在6種覆蓋方法中找到路徑覆蓋作為最優(yōu)方案。實(shí)驗(yàn)結(jié)果證實(shí)了該優(yōu)化算法的靈活性和有效性，可以依據(jù)測試需求決定測試用例個數(shù)，通過聚類選擇最優(yōu)測試用例，在保證所得軟件增益的情況下，去除程序結(jié)構(gòu)測試中冗余的測試用例，從而降低了測試成本。

[1] 潘爍, 王曙燕, 孫家澤. 基于K-均值聚類粒子群優(yōu)化算法的組合測試數(shù)據(jù)生成[J]. 計算機(jī)應(yīng)用, 2012, 32(4): 1165-1167.

[2] 王博, 王曙燕. 一種新的基于模擬退火的測試用例生成與約簡算法[J]. 計算機(jī)應(yīng)用與軟件, 2013, 30(2): 78-81.

[3] Liu Dan, Wang Jianmin, Zheng Lijuan. Automatic test paper generation based on ant colony algorithm[J]. Journal of Software, 2013, 8(10): 2600-2606.

[4] Kim J, Choi K, Hoffman D. White box pairwise test case generation[C]//Seventh International Conference on QualitySoftware. Piscataway: IEEE Press, 2007: 286-291.

[5] Ilkhani A, Abaee G. Extracting test case by using data mining; reducing the cost of testing[C]//2010 International Conference on Computer Information Systems and Industrial Management Applications (CISIM). Krackow: IEEE Press, 2010: 620-625.

[6] Zeng Fanping, Li Ling, Li Juan. Research on test suite reduction using attribute relevance analysis[C]//Eigth IEEE/ACIS International Conference on Computer and Information Science. Shanghai: IEEE Press, 2009: 961-966.

[7] Liu Yue, Wang Kang, Wei Wang. User-session-based test cases optimization method based on agglutinate hierarchy clustering[C]//2011 IEEE International Conferences on Internet of Things, and Cyber, Physical and Social Computing. Dalian: IEEE Press, 2011: 413-418.

[8] 陳陽梅, 丁曉明. 一種基于K中心點(diǎn)算法的測試用例集約簡方法[J]. 計算機(jī)科學(xué), 2012, 39(6A): 422-424.

[9] 孫家澤.程序不變量驅(qū)動的組合測試用例約簡方法[J].西安郵電學(xué)院學(xué)報, 2012, 17(2):71-74.

[10] 嚴(yán)俊, 張健. 組合測試: 原理與方法[J]. 軟件學(xué)報, 2009, 20(6): 1393-1405.

[11] 張馳, 王曙燕, 孫家澤. 基于序優(yōu)化蟻群算法的成對交互測試用例集生成[J]. 計算機(jī)應(yīng)用與軟件, 2013, 30(1): 71-74.

[12] Liu Weimin, Li Sujian, Zhao Fanggeng. An ant colony optimization algorithm for the multiple traveling salesmen problem[C]//ICIEA 2009.4th IEEE Conference on Industrial Electronics and Applications. Xi’an: IEEE Press, 2009: 1533-1537.

[責(zé)任編輯:祝劍]

Combinatorial test case optimization based on K-means clustering

FENG Xia, WANG Shuyan, SUN Jiaze

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

To eliminate test suite redundancy of combinatorial testing in white-box testing，optimized pairwise test suites are generated based on K-means algorithm merging with ant colony algorithm. While building test suites，the logic coverage strategy in white-box testing is adopted. The difference of program coverage is used as quantitative criteria to classify test cases. The clustering number is decided by test cost. A new test suite is built through clustering system choosing data at clusters’ center. Simulation experiments show that this method reduces the size of test set effectively. Moreover, this paper presents a method of test standardization by applying different coverage criteria, and thus provides a better solution for test suite data mining technology.

K-means clustering algorithm, ant colony algorithm, combinatorial testing, white-box testing

2014-09-01

國家自然科學(xué)基金資助項(xiàng)目(61050003);西安郵電大學(xué)青年教師科研基金資助項(xiàng)目(ZL2013-26)

馮霞(1989-)，女，碩士研究生，研究方向軟件測試、數(shù)據(jù)挖掘。E-mail:fengxia166@sina.com 王曙燕(1964-)，女，博士，教授，從事軟件測試、數(shù)據(jù)挖掘、智能信息處理研究。E-mail:wsylxj@126.com

10.13682/j.issn.2095-6533.2015.01.009

TP301

A

2095-6533(2015)01-0044-05