摘 要：測(cè)試用例自動(dòng)生成是軟件測(cè)試過(guò)程中的一個(gè)關(guān)鍵環(huán)節(jié)。為解決因集簇特性而導(dǎo)致PSO測(cè)試用例生成算法計(jì)算資源浪費(fèi)的問(wèn)題，提出了分簇競(jìng)爭(zhēng)PSO測(cè)試用例生成算法（CTCC-PSO），采用“集簇度”指標(biāo)對(duì)算法進(jìn)行量化和分析，并通過(guò)實(shí)驗(yàn)證明新算法的有效性。CTCC-PSO算法包括“集簇度量化”與“簇中用例競(jìng)爭(zhēng)約簡(jiǎn)”兩個(gè)重要過(guò)程，根據(jù)“集簇度”動(dòng)態(tài)地驅(qū)動(dòng)簇內(nèi)測(cè)試用例進(jìn)行競(jìng)爭(zhēng)，從而有效地提升測(cè)試用例生成效率。實(shí)驗(yàn)結(jié)果表明，CTCC-PSO算法在不失魯棒性的前提下，與基本PSO測(cè)試用例生成算法相比，能夠有效減少測(cè)試迭代規(guī)模，同時(shí)顯著減少參與計(jì)算的測(cè)試用例總量。

關(guān)鍵詞：粒子群優(yōu)化；測(cè)試用例；分簇競(jìng)爭(zhēng)

DOIDOI：10.11907/rjdk.151963

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：1672-7800（2015）012-0063-04

基金項(xiàng)目基金項(xiàng)目：

作者簡(jiǎn)介作者簡(jiǎn)介：黃劍（1979-），男，江西南昌人，碩士，江西財(cái)經(jīng)大學(xué)網(wǎng)絡(luò)信息管理中心工程師，研究方向?yàn)橛?jì)算機(jī)應(yīng)用。

0 引言

軟件測(cè)試是確保軟件安全的重要環(huán)節(jié)，目的在于盡可能地發(fā)現(xiàn)并改正被測(cè)試軟件中的錯(cuò)誤，提高軟件的正確性和可靠性。

傳統(tǒng)的軟件測(cè)試技術(shù)[1-4]比較復(fù)雜，表現(xiàn)為使用成本高、實(shí)際應(yīng)用難，對(duì)具體而多樣化的測(cè)試目標(biāo)缺乏較好的魯棒性。近十幾年來(lái)，啟發(fā)性算法被廣泛應(yīng)用于測(cè)試用例生成研究，主要研究工作集中在遺傳算法（Genetic Algorithms，簡(jiǎn)稱(chēng)GA）[5-8]、神經(jīng)網(wǎng)絡(luò)（Neural Network，簡(jiǎn)稱(chēng)NN）[9]、蟻群算法（Ant Colony Algorithm，簡(jiǎn)稱(chēng)ACA）[10]等方法上，并已經(jīng)取得較為成熟的成果。這些成果標(biāo)志著具有啟發(fā)性、學(xué)習(xí)性和演進(jìn)性的智能測(cè)試用例算法成為測(cè)試用例生成算法的重要組成部分。

粒子群優(yōu)化（Particle Swarm Optimization，簡(jiǎn)稱(chēng)PSO）[11]測(cè)試用例生成算法是一種啟發(fā)性的自動(dòng)化測(cè)試技術(shù)，該算法將測(cè)試用例（Test Case，簡(jiǎn)稱(chēng)TC）的生成過(guò)程轉(zhuǎn)化為通過(guò)對(duì)種群中TC的評(píng)估和更新得到最優(yōu)解的過(guò)程。PSO測(cè)試用例生成算法具備算法簡(jiǎn)單、魯棒性好的特點(diǎn)，同時(shí)具有很好的導(dǎo)向性和收斂性[12]。

本文針對(duì)目前PSO測(cè)試用例生成算法[13-15]由于集簇特性而導(dǎo)致計(jì)算資源浪費(fèi)的問(wèn)題，提出分簇競(jìng)爭(zhēng)PSO測(cè)試用例自動(dòng)生成算法（PSO Competitive Test Case generation algorithm with Clustering，簡(jiǎn)稱(chēng)CTCC-PSO），并對(duì)CTCC-PSO算法的“集簇度”（Cluster Indicator，簡(jiǎn)稱(chēng)CI）進(jìn)行了定義和分析，提出一種CI驅(qū)動(dòng)的TC競(jìng)爭(zhēng)策略，用于實(shí)現(xiàn)對(duì)測(cè)試用例種群規(guī)模的動(dòng)態(tài)控制，從而達(dá)到節(jié)約計(jì)算資源的目的。通過(guò)對(duì)比實(shí)驗(yàn)與分析，CTCC-PSO與基本PSO測(cè)試用例生成算法（Basic PSO test case generation algorithm， 簡(jiǎn)稱(chēng)B-PSO）相比，在測(cè)試用例生成效率和計(jì)算成本上均有顯著改進(jìn)。

1 基本PSO測(cè)試用例生成算法

1.1 基本思想

圖2 TriTyp基準(zhǔn)實(shí)驗(yàn)CI量化曲線

實(shí)驗(yàn)顯示CI具有兩個(gè)基本特性：①CI隨迭代進(jìn)行而遞增；②隨著迭代的進(jìn)行，CI波動(dòng)性逐漸變小并趨于穩(wěn)定。這兩個(gè)特性表明，TC在簇內(nèi)具有相互吸引的能力，并趨向于保持更緊密的鄰近關(guān)系，即TC在簇內(nèi)表現(xiàn)出位置趨同性，簇內(nèi)TC間相互潛在競(jìng)爭(zhēng)性增強(qiáng)。

2.2 CTCC-PSO

2.2.1 CTCC-PSO算法描述

輸入：D-dimensionalSpaceTC空間特征swarmSize：TC種群規(guī)模iteratorMax：算法最大迭代次數(shù)CImax 簇c競(jìng)爭(zhēng)驅(qū)動(dòng)門(mén)限輸出： 最終TC種群//根據(jù)測(cè)試目標(biāo)入口參數(shù)特征初始化TCswarm = initSwarm（D-dimensionalSpace，swarmSize）； //迭代次數(shù)（iterator）達(dá)到最大值（iteratorMax）或算法已達(dá)到最優(yōu)解（|fitness|=0）時(shí)，算法結(jié)束。iterator=0；while （iterator 0）{ for each TC in swarm{//量化TC適應(yīng)度CaculateTCFitness（TC）； update（pbest）； //更新每個(gè)測(cè)試用例的pbestupdate（gbest）； //更新測(cè)試用例群的gbest }//對(duì)測(cè)試用例群進(jìn)行分簇cluster= cluster（swarm）； for each c in cluster{ CI = calculateCI（c）； //計(jì)算簇c的CI//若CI大于CImax，則驅(qū)動(dòng)簇c內(nèi)的競(jìng)爭(zhēng)策略 if（CI>CImax） performStrategy（c，CI，CImax）； }//對(duì)群中的每個(gè)TC按照以下公式進(jìn)行更新for each TC in swarm{ vid=wvid+c1r1（pid-xid）+c2r2（pgd-xid），vid≤vmaxdvmaxd，vid>vmaxd xid=xid+vid update（TC）；}}outputResult（swarm）； //輸出最優(yōu)解

2.2.2 TC競(jìng)爭(zhēng)策略

輸入： c CTCC-PSO中的軌跡簇CI：簇c的當(dāng)前CI量化值CImax：簇c策略執(zhí)行門(mén)限輸出： 約簡(jiǎn)后的簇c// 計(jì)算簇c的競(jìng)爭(zhēng)系數(shù)σ，CImax為激活簇約簡(jiǎn)策略的邊界σ=CI-CImaxCImax； //c.count為簇c中TC的數(shù)量，c.minCount為簇c中最少需要保留的TC數(shù)量if（c.count-σ×c.count>c.minCount）{//對(duì)簇c內(nèi)粒子按適應(yīng)度由低到高排序orderTC（c）；//對(duì)簇c內(nèi)粒子進(jìn)行競(jìng)爭(zhēng)和淘汰 for each TC in c { if （TC.orderID<σ×c.count）c.kill（TC）； }}//返回調(diào)用者CTCC-PSO；return to CTCC-PSO

3 B-PSO與CTCC-PSO實(shí)驗(yàn)對(duì)比分析

為進(jìn)一步測(cè)試和分析CTCC-PSO算法的有效性，本節(jié)用面向分支插樁對(duì)TriTyp和BinarySearch程序進(jìn)行測(cè)試。實(shí)驗(yàn)按不同參數(shù)和測(cè)試對(duì)象進(jìn)行分組，驗(yàn)證新算法的有效性。

3.1 實(shí)驗(yàn)安排

CTCC-PSO算法測(cè)試實(shí)驗(yàn)根據(jù)測(cè)試對(duì)象分為兩類(lèi)：①三角分類(lèi)（TriTyp）分支覆蓋測(cè)試；②二分查找算法（BinarySearch）測(cè)試。每類(lèi)實(shí)驗(yàn)分為4組，每組進(jìn)行100次測(cè)試。為加強(qiáng)實(shí)驗(yàn)的可比性，每組測(cè)試中B-PSO算法和CTCC-PSO采用同一組參數(shù)，且該組參數(shù)均可使B-PSO或CCTC-PSO覆蓋測(cè)試路徑。具體實(shí)驗(yàn)編號(hào)與參數(shù)配置詳見(jiàn)表2、表3。

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

圖3為分組實(shí)驗(yàn)數(shù)據(jù)對(duì)比圖，B-PSO與CTCC-PSO性能分析包括3個(gè)方面：①平均迭代次數(shù)分析；②測(cè)試用例數(shù)量分析；③整體效率分析。

平均迭代次數(shù)（Average Iterations，簡(jiǎn)稱(chēng)AI）指某組實(shí)驗(yàn)使用相同參數(shù)進(jìn)行n次實(shí)驗(yàn)，平均每次實(shí)驗(yàn)需要的迭代次數(shù)，即AI=∑ni=1iterationsi/n，iterationsi為第i次實(shí)驗(yàn)需要的迭代數(shù)。對(duì)TriTyp進(jìn)行的4組分支覆蓋測(cè)試中，CTCC-PSO較B-PSO算法AI最小減少9.02%，最大減少22.80%，平均減少14.25%；對(duì)BinarySearch進(jìn)行的4組分支覆蓋測(cè)試中，CTCC-PSO較B-PSO算法AI最小減少25.40%，最大減少32.69%，平均減少27.67%。

參與計(jì)算的測(cè)試用例總數(shù)（Test Cases Used in Total，簡(jiǎn)稱(chēng)TCUT）指某組實(shí)驗(yàn)使用相同參數(shù)進(jìn)行n次實(shí)驗(yàn)，平均每次實(shí)驗(yàn)實(shí)際參與計(jì)算的測(cè)試用例總數(shù)，即TCUT=∑ni=1NTCi/n，NTCi為第i次實(shí)驗(yàn)實(shí)際參與計(jì)算的測(cè)試用例總數(shù)。對(duì)TriTyp進(jìn)行的4組分支覆蓋測(cè)試中，CTCC-PSO較B-PSO算法TCUT最小減少9.42%，最大減少24.48%，平均減少15.05%；對(duì)BinarySearch進(jìn)行的4組分支覆蓋測(cè)試中，CTCC-PSO較B-PSO算法TCUT最小減少62.18%，最大減少66.71%，平均減少64.73%。

通過(guò)上述分析，CTCC-PSO較B-PSO算法可有效減少平均迭代次數(shù)和測(cè)試用例總數(shù)。分析表明，CTCC-PSO是比B-PSO更具性能優(yōu)勢(shì)的測(cè)試用例生成算法。

圖3 B-PSO/CTCC-PSO分組實(shí)驗(yàn)數(shù)據(jù)對(duì)比

4 結(jié)語(yǔ)

本文針對(duì)PSO測(cè)試用例生成算法中TC在搜索空間運(yùn)動(dòng)軌跡的集簇特性，提出分簇競(jìng)爭(zhēng)PSO測(cè)試用例生成算法（CTCC-PSO）。CTCC-PSO包含兩個(gè)新的重要階段：①CI量化階段；②簇內(nèi)競(jìng)爭(zhēng)約簡(jiǎn)階段。實(shí)驗(yàn)分析表明：CTCC-PSO算法可以有效節(jié)省測(cè)試用例的計(jì)算成本，同時(shí)減少算法迭代次數(shù)，是現(xiàn)有測(cè)試用例生成算法的有效補(bǔ)充。

本文提出的CTCC-PSO算法具有以下特點(diǎn)：①對(duì)測(cè)試用例群演進(jìn)過(guò)程中產(chǎn)生的集簇性具有量化能力（Clustering Indicator Quantization，簡(jiǎn)稱(chēng)CIQ），該能力為基于集簇特性的測(cè)試用例競(jìng)爭(zhēng)提供了決策基礎(chǔ)；②CTCC-PSO算法包含了簇內(nèi)TC競(jìng)爭(zhēng)約簡(jiǎn)策略，淘汰本簇中的劣質(zhì)TC。該策略構(gòu)建于CIQ，是CTCC-PSO算法優(yōu)于B-PSO算法的關(guān)鍵。

CTCC-PSO與基本的B-PSO算法相比，迭代次數(shù)更少，測(cè)試用例更精簡(jiǎn)，有效地節(jié)約了系統(tǒng)計(jì)算資源。

參考文獻(xiàn)參考文獻(xiàn)：

[1] LEE D， YANNAKAKIS M. Principles and methods of testing finite state machines-a survey[J].Proceedings of the IEEE，1996， 84（8）：1090-1123.

[2] JARD C， JERRON T. TGV： theory， principles and algorithms[J]. International Journal on Software Tools for Technology Transfer，2005， 7（4）： 297-315.

[3] AMMANN P E， BLACK P E. A specification-based coverage metric to evaluate test sets[C]. Washington， D.C.， USA： IEEE Computer Society Press， 1999：239-248.

[4] 陳繼鋒， 朱利， 沈鈞毅. 一種基于路徑的測(cè)試數(shù)據(jù)自動(dòng)生成算法[J]. 控制與決策，2005，20（9）：1065-1068.

[5] JONES B， STHAMER H， EYRES D. Automatic structural testing using genetic algorithms[J].Software Engineering Journal， 1996， 11（5）： 299-306.

[6] PARGAS R P， HARROLD M J， PECK R R. Test-data generation using genetic algorithms[J].Software Testing，Verification and Reliability，1999（9）： 263.

[7] GIRGIS M R. Automatic test data generation for data flow testing using a genetic algorithm[J].Journal of Universal Computer Science，2005.

[8] GHIDUK A S， HARROLD M J，GIRGIS M R.Using genetic algorithms to aid test-data generation for data-flow coverage[C].Nagoya， Japan： IEEE Computer Society Press， 2007：41-48.

[9] ZHAO R L， LV S S.Neural-network based test cases generation using genetic algorithm[C].Melbourne， Victoria， Australia： IEEE Press， 2007：97-100.

[10] 陳明師， 劉曉潔， 李濤. 基于多態(tài)蟻群算法的測(cè)試用例自動(dòng)生成[J]. 計(jì)算機(jī)應(yīng)用研究，2009， 26（6）： 1347-1348.

[11] KENNEDY J， EBERHART R. Particle swarm optimization[C]. Perth， Australia： IEEE Press， 1995：1942-1948.

[12] 周龍甫， 師奕兵. PSO算法粒子運(yùn)動(dòng)軌跡穩(wěn)定收斂條件分析[J]. 控制與決策，2009， 24（10）： 1499-1503.

[13] LI A G， ZHANG Y L. Automatic generation method of test data for software structure based on PSO[J]. Computer Engineering， 2008， 34（6）： 189-193.

[14] CUI H， CHEN L， ZHU B， et al.An efficient automated test data generation method[C].Changsha， China： IEEE Computer Society， 2010：453-456.

[15] BUENO P M S， WONG W E， JINO M. Automatic test data generation using particle systems[C]. Fortaleza， Ceara， Brazil ： ACM Press， 2008：809-814.

[16] HLA K H S， CHOI Y， PARK J S. Applying particle swarm optimization to prioritizing test cases for embedded real time software retesting[C].Sydney， Australia： Institute of Electrical and Electronics Engineers， 2008：527-532.

[17] THORNDIKE E L. Animal intelligence： experimental studies[M]. New Jersey， USA： Transaction Publishers， 2000： 297.

[18] BANDURA A. Social foundations of thought and action：a social cognitive theory[M].New Jersey， USA： Prentice Hall， 1986： 544.

（責(zé)任編輯：黃 健）