基于自適應(yīng)粒子群優(yōu)化算法的測(cè)試數(shù)據(jù)擴(kuò)增方法

王曙燕　溫春琰　孫家澤

摘要：

針對(duì)在回歸測(cè)試中原有測(cè)試數(shù)據(jù)集往往難以滿足新版本軟件測(cè)試需求的問(wèn)題，提出一種基于自適應(yīng)粒子群算法（APSO）的測(cè)試數(shù)據(jù)擴(kuò)增方法。首先，根據(jù)原有測(cè)試數(shù)據(jù)在新版本程序上的穿越路徑與目標(biāo)路徑的相似度，在原有的測(cè)試數(shù)據(jù)集中選擇合適的測(cè)試數(shù)據(jù)，作為初始種群的進(jìn)化個(gè)體；然后，利用初始測(cè)試數(shù)據(jù)的穿越路徑與目標(biāo)路徑的不同子路徑，確定造成兩者路徑偏離的輸入分量；最后，根據(jù)路徑相似度構(gòu)建適應(yīng)度函數(shù)，利用APSO操作輸入分量，生成新的測(cè)試數(shù)據(jù)。該方法針對(duì)四個(gè)基準(zhǔn)程序與基于遺傳算法（GA）和隨機(jī)法的測(cè)試數(shù)據(jù)擴(kuò)增方法相比，測(cè)試數(shù)據(jù)擴(kuò)增效率分別這只是一個(gè)實(shí)例的結(jié)果！平均提高了約56%和81%。實(shí)驗(yàn)結(jié)果表明，所提方法在回歸測(cè)試方面有效地提高了測(cè)試數(shù)據(jù)擴(kuò)增的效率，增強(qiáng)了其穩(wěn)定性。

關(guān)鍵詞：

回歸測(cè)試；目標(biāo)路徑；測(cè)試數(shù)據(jù)擴(kuò)增；路徑相似度；粒子群優(yōu)化算法

中圖分類號(hào)：

TP311.5

文獻(xiàn)標(biāo)志碼：A

Abstract：

It is difficult for the original test data to meet the requirements of the new version of software testing in regression testing， thus a new test data augmentation method based on Adaptive Particle Swarm Optimization （APSO） algorithm was proposed to solve the problem. Firstly， according to the similarity between the cross path in the original test data and the target path in the new version of the program，F(xiàn)irstly， according to the similarity between the cross path and the target path of the original test data in the new version of the program， the appropriate test data in the original test data was chosen as evolutionary individual of initial population. Secondly， taking advantage of different subpaths of the cross path of initial test data and target path， the input component which caused deviation between them was confirmed. Finally， the fitness function was created according to the path similarity， and the new data was generated by using the APSO algorithm to operate the input component. Compared with the genetic algorithm based and random algorithm based test data augmentation methods on four benchmark programs， the augmentation efficiency of the proposed method was improved on average by approximately 56% and 81% respectively. The experimental results show that the proposed method can effectively increase the efficiency and improve the stability of test data augmentation in regression testing.

英文關(guān)鍵詞Key words：

regression testing； target path； test data augmentation； path similarity； Particle Swarm Optimization （PSO） algorithm

0引言

在回歸測(cè)試的過(guò)程中，測(cè)試人員通過(guò)重新測(cè)試新版本軟件，以驗(yàn)證新版本軟件沒(méi)有被加入新的錯(cuò)誤或引起其他代碼產(chǎn)生錯(cuò)誤[1]。為了覆蓋軟件的修改和新增部分，需要對(duì)原有測(cè)試數(shù)據(jù)集進(jìn)行擴(kuò)增。與傳統(tǒng)的測(cè)試數(shù)據(jù)生成相比，測(cè)試數(shù)據(jù)擴(kuò)增在對(duì)比軟件新舊版本、分析軟件修改影響的基礎(chǔ)上，針對(duì)軟件變化產(chǎn)生新的測(cè)試數(shù)據(jù)，以提高軟件的測(cè)試效率。

在現(xiàn)有的測(cè)試數(shù)據(jù)擴(kuò)增方法中，Santelices等[2]利用控制流圖和數(shù)據(jù)依賴圖，結(jié)合符號(hào)執(zhí)行進(jìn)行分析，提出了測(cè)試數(shù)據(jù)集擴(kuò)增需要滿足鏈需求和狀態(tài)需求；Qi等[3]將PIE （PropagationInfectionExecution）模型[4]引入到測(cè)試數(shù)據(jù)擴(kuò)增方法中，在路徑引導(dǎo)過(guò)程中通過(guò)符號(hào)執(zhí)行和CEPT（Change Effect Propagation Tree）[5]發(fā)現(xiàn)變量在修改后未被執(zhí)行和執(zhí)行后是否發(fā)生變化，以確保擴(kuò)增的測(cè)試數(shù)據(jù)能夠影響輸出結(jié)果；Xu等[6]將Concolic Testing技術(shù)引入到測(cè)試數(shù)據(jù)擴(kuò)增方法中，根據(jù)軟件的演化信息選擇有利于覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)，利用已有測(cè)試用例結(jié)合實(shí)體測(cè)試和符號(hào)測(cè)試產(chǎn)生新的測(cè)試數(shù)據(jù)。

在上述的方法中，Santelices等[2]和Qi等[3]提出的方法沒(méi)有考慮已有測(cè)試數(shù)據(jù)的利用，而Xu等[6]的方法僅對(duì)測(cè)試數(shù)據(jù)的數(shù)量進(jìn)行了縮減，并不能保證篩選出的測(cè)試數(shù)據(jù)的質(zhì)量。針對(duì)上述問(wèn)題，鞏敦衛(wèi)等[7]采用遺傳算法（Genetic Algorithm， GA）進(jìn)行測(cè)試數(shù)據(jù)擴(kuò)增，合理地利用了已有的測(cè)試數(shù)據(jù)形成初始進(jìn)化種群，有效提高了測(cè)試數(shù)據(jù)的生成效率；但是并沒(méi)有將GA中起核心作用的交叉算子與程序演化信息相結(jié)合，降低了遺傳算法全局搜索的能力。

粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法作為一種簡(jiǎn)單高效的智能計(jì)算方法，在很多領(lǐng)域取得了成功，但在測(cè)試數(shù)據(jù)擴(kuò)增中的應(yīng)用還未見公開文獻(xiàn)的報(bào)道。本文研究采用自適應(yīng)粒子群優(yōu)化（Adaptive Particle Swarm Optimization， APSO）算法結(jié)合軟件演化信息進(jìn)行測(cè)試數(shù)據(jù)擴(kuò)增，利用測(cè)試數(shù)據(jù)的穿越路徑與目標(biāo)路徑的相似度矩陣選擇原有的測(cè)試數(shù)據(jù)集，避免了GA的交叉和變異操作，自適應(yīng)地調(diào)整了算法的搜索過(guò)程，作用于穿越路徑與目標(biāo)路徑的偏移分量，以期增強(qiáng)其全局搜索能力，提高其收斂速度。

其中：程序解析模塊是整個(gè)模型的基礎(chǔ)部分，該部分通過(guò)靜態(tài)分析構(gòu)建控制流圖，將原有測(cè)試數(shù)據(jù)集輸入到測(cè)試運(yùn)行模塊得到穿越路徑，然后選擇出新版本程序需要覆蓋的目標(biāo)路徑，并計(jì)算出穿越路徑和目標(biāo)路徑的相似度矩陣，從而選擇出APSO模塊需要的初始種群；APSO是核心模塊，根據(jù)粒子的適應(yīng)值、進(jìn)化方程和慣性權(quán)重調(diào)整公式來(lái)引導(dǎo)粒子向目標(biāo)解進(jìn)化，最終生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)集；測(cè)試運(yùn)行模塊在整個(gè)模型中起到橋梁的作用，通過(guò)接收測(cè)試數(shù)據(jù)，輸出測(cè)試數(shù)據(jù)的穿越路徑。

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

為驗(yàn)證本文方法的有效性，選擇基于遺傳算法（GA）和隨機(jī)法的測(cè)試數(shù)據(jù)擴(kuò)增方法與本文方法進(jìn)行比較，在相同的條件下，對(duì)測(cè)試程序各定義一個(gè)或多個(gè)修改點(diǎn)，分別運(yùn)行20次，生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)，記錄每種方法的進(jìn)化代數(shù)和耗時(shí)，分別計(jì)算它們的平均值和標(biāo)準(zhǔn)差，最終實(shí)驗(yàn)結(jié)果如表2所示。

在表2中，實(shí)驗(yàn)數(shù)據(jù)，摘要中有必要寫明是Tcas這一個(gè)例子的數(shù)據(jù)是56%和81%，不代表所有吧？但第一次修改時(shí)作者仍然未改，再問(wèn)以空中防撞系統(tǒng)Tcas為例，相比遺傳算法需要迭代189.2次、運(yùn)行時(shí)間15.432s，以及隨機(jī)法未能在規(guī)定的最大代數(shù)T=1000中完成測(cè)試要求，本文方法只需迭代約19.8次、運(yùn)行時(shí)間0.724s即可生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)。綜合各計(jì)算各種擴(kuò)增方法在不同基準(zhǔn)程序的擴(kuò)增效率，本文方法與基于遺傳算法和隨機(jī)法的測(cè)試數(shù)據(jù)擴(kuò)增方法相比，測(cè)試數(shù)據(jù)擴(kuò)增效率平均分別提高了約56%和81%。由此可看出本文方法在回歸測(cè)試中生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)具有較高的效率。而且，通過(guò)多次運(yùn)行結(jié)果求得的標(biāo)準(zhǔn)差可以看出，本文方法在穩(wěn)定性方面也具有較好的優(yōu)勢(shì)。

同時(shí)，通過(guò)比較不同方法在迭代的過(guò)程對(duì)目標(biāo)路徑的覆蓋率，來(lái)評(píng)價(jià)不同回歸測(cè)試數(shù)據(jù)擴(kuò)增方法的性能。以空中防撞系統(tǒng)Tcas為例，不同方法在迭代過(guò)程中對(duì)目標(biāo)路徑的覆蓋率如圖3所示。由圖3可以看出，本文方法與其他兩種方法相比，在覆蓋目標(biāo)路徑方面具有明顯的優(yōu)勢(shì)，且有效地避免了在回歸測(cè)試數(shù)據(jù)擴(kuò)增過(guò)程中測(cè)試數(shù)據(jù)陷入局部最優(yōu)解的問(wèn)題。

通過(guò)上述分析，可以得到如下結(jié)論：對(duì)于基準(zhǔn)程序和西門子工業(yè)程序，本文提出的基于自適應(yīng)粒子群算法的回歸測(cè)試數(shù)據(jù)集擴(kuò)增方法在充分利用原有測(cè)試數(shù)據(jù)集的基礎(chǔ)上，可以消耗較少的代價(jià)，更穩(wěn)定地生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)集。

5結(jié)語(yǔ)

在面向覆蓋的測(cè)試數(shù)據(jù)集擴(kuò)增方法中，如何充分利用已

有測(cè)試數(shù)據(jù)和如何在測(cè)試數(shù)據(jù)的演化過(guò)程中利用更多的路徑信息是提高測(cè)試數(shù)據(jù)擴(kuò)增效率的關(guān)鍵問(wèn)題。本文提出了一種

基于自適應(yīng)粒子群算法的測(cè)試數(shù)據(jù)集擴(kuò)增方法，該方法通過(guò)對(duì)多個(gè)基準(zhǔn)程序和西門子工業(yè)程序進(jìn)行測(cè)試，并與利用遺傳算法和隨機(jī)法的回歸測(cè)試數(shù)據(jù)擴(kuò)增方法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，本文所提方法在生成覆蓋目標(biāo)路徑測(cè)試數(shù)據(jù)的效率和穩(wěn)定性上都具有明顯的提高。

在回歸測(cè)試數(shù)據(jù)的擴(kuò)增過(guò)程中，利用測(cè)試數(shù)據(jù)的穿越路徑和目標(biāo)路徑的相似度來(lái)衡量測(cè)試數(shù)據(jù)的優(yōu)劣，雖然在一定程度上提高了測(cè)試數(shù)據(jù)生成的效率和穩(wěn)定性，但是在復(fù)雜的實(shí)際軟件中，如何在測(cè)試數(shù)據(jù)的演化過(guò)程中利用更多的路徑信息，進(jìn)而提高生成覆蓋目標(biāo)路徑測(cè)試數(shù)據(jù)的效率，是下一步需要繼續(xù)研究的問(wèn)題。

參考文獻(xiàn)：

[1]

張智軼，陳振宇，徐寶文，等.測(cè)試用例演化研究進(jìn)展[J].軟件學(xué)報(bào)，2013，24（4）：663-674.（ZHANG Z Y， CHEN Z Y， XU B W， et al. Research progress on test case evolution [J]. Journal of Software， 2013， 24（4）： 663-674.）

[2]

SANTELICES R， CHITTIMALLI P K， APIWATTANAPONG T， et al. Testsuite augmentation for evolving software [C]// ASE 08： Proceedings of the 2008 23th IEEE/ACM International Conference on Automated Software Engineering. Washington， DC： IEEE Computer Society， 2008： 218-227.

[3]

QI D， ROYCHOUDHURY A， LIANG Z. Test generation to expose changes in evolving programs [C]// ASE 10： Proceedings of the 25th IEEE/ACM International Conference on Automated Software Engineering. New York： ACM， 2010： 397-406.

[4]

VOAS J M. PIE： a dynamic failurebased technique [J]. IEEE Transactions on Software Engineering， 1992， 18（8）： 717-727.

[5]

PEARL J. Probabilistic Reasoning in Intelligent Systems： Networks of Plausible Inference [M]. San Francisco， CA： Morgan Kaufmann， 1988： 35.

[6]

XU Z， ROTHERMEL G. Directed test suite augmentation [C]// APSEC 2009： Proceedings of the 2009 International Conference on the AsiaPacific Software Engineering. Washington， DC： IEEE Computer Society， 2009： 406-413.

https：//www.computer.org/csdl/proceedings/apsec/2009/3909/00/3909a406-abs.html

XU Z. Directed test suite augmentation [C]// ICSE 11： Proceedings of the 2011 33rd International Conference on Software Engineering. New York： ACM， 2011： 1110-1113.

[7]

鞏敦衛(wèi)，任麗娜.回歸測(cè)試數(shù)據(jù)進(jìn)化生成[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（3）：489-499.（GONG D W， REN L N. Evolitionary generation of regression test data [J]. Chinese Journal of Computers， 2014， 37（3）： 489-499.）

[8]

吳川，鞏敦衛(wèi).基于路徑相關(guān)性的回歸測(cè)試數(shù)據(jù)進(jìn)化生成[J].

計(jì)算機(jī)學(xué)報(bào)，2015，38（11）：2247-2261.（WU C， GONG D W. Evolutionary generation of test data for regression testing based on path correlation [J]. Chinese Journal of Computers， 2015， 38（11）： 2247-2261.）

[9]

BUENO P M S， JINO M. Automatic test data generation for program paths using genetic algorithms [J]. International Journal of Software Engineering and Knowledge Engineering， 2002， 12（6）： 691-709.

[10]

胡旺，李志蜀.一種更簡(jiǎn)化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報(bào)，2007，18（4）：861-868.（HU W， LI Z S. A simpler and more effective particle swarm optimization algorithm [J]. Journal of Software， 2007， 18（4）： 861-868.）

[11]

史嬌嬌.基于遺傳粒子群優(yōu)化算法的測(cè)試數(shù)據(jù)自動(dòng)生成技術(shù)研究[D].徐州：中國(guó)礦業(yè)大學(xué)，2014：34-48.（SHI J J. Study on the automatic test data generation based on genetic algorithm and particle swarm optimization algorithm [D]. Xuzhou： China University of Mining and Technology， 2014： 34-48.）

[12]

張巖，鞏敦衛(wèi).基于搜索空間自動(dòng)縮減的路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成[J].電子學(xué)報(bào)，2012，40（5）：1011-1016.（ZHANG Y， GONG D W. Evolutionary generation of test data for path coverage based on automatic reduction of search space [J]. Acta Electronica Sinica， 2012， 40（5）： 1011-1016.）

[13]

DO H， ELBAUM S， ROTHERMEL G. Supporting controlled experimentation with testing techniques： an infrastructure and its potential impact [J]. Empirical Software Engineering， 2005， 10（4）： 405-435.