分簇競爭PSO測試用例自動生成算法

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

關(guān)鍵詞：粒子群優(yōu)化；測試用例；分簇競爭

DOIDOI：10.11907/rjdk.151963

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2015）012-0063-04

基金項目基金項目：

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

0 引言

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

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

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

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

1 基本PSO測試用例生成算法

1.1 基本思想

圖2 TriTyp基準實驗CI量化曲線

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

2.2 CTCC-PSO

2.2.1 CTCC-PSO算法描述

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

輸入： c CTCC-PSO中的軌跡簇CI：簇c的當前CI量化值CImax：簇c策略執(zhí)行門限輸出： 約簡后的簇c// 計算簇c的競爭系數(shù)σ，CImax為激活簇約簡策略的邊界σ=CI-CImaxCImax； //c.count為簇c中TC的數(shù)量，c.minCount為簇c中最少需要保留的TC數(shù)量if（c.count-σ×c.count>c.minCount）{//對簇c內(nèi)粒子按適應(yīng)度由低到高排序orderTC（c）；//對簇c內(nèi)粒子進行競爭和淘汰 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實驗對比分析

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

3.1 實驗安排

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

3.2 實驗結(jié)果與分析

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

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

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

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

圖3 B-PSO/CTCC-PSO分組實驗數(shù)據(jù)對比

4 結(jié)語

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

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

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

參考文獻參考文獻：

[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] 陳繼鋒， 朱利， 沈鈞毅. 一種基于路徑的測試數(shù)據(jù)自動生成算法[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)蟻群算法的測試用例自動生成[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算法粒子運動軌跡穩(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.

（責任編輯：黃 ?。?