王曙燕　溫春琰　孫家澤

摘要：

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

關(guān)鍵詞：

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

中圖分類號：

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引言

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

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

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

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

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

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

為驗(yàn)證本文方法的有效性，選擇基于遺傳算法（GA）和隨機(jī)法的測試數(shù)據(jù)擴(kuò)增方法與本文方法進(jìn)行比較，在相同的條件下，對測試程序各定義一個(gè)或多個(gè)修改點(diǎn)，分別運(yùn)行20次，生成覆蓋目標(biāo)路徑的測試數(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í)作者仍然未改，再問以空中防撞系統(tǒng)Tcas為例，相比遺傳算法需要迭代189.2次、運(yùn)行時(shí)間15.432s，以及隨機(jī)法未能在規(guī)定的最大代數(shù)T=1000中完成測試要求，本文方法只需迭代約19.8次、運(yùn)行時(shí)間0.724s即可生成覆蓋目標(biāo)路徑的測試數(shù)據(jù)。綜合各計(jì)算各種擴(kuò)增方法在不同基準(zhǔn)程序的擴(kuò)增效率，本文方法與基于遺傳算法和隨機(jī)法的測試數(shù)據(jù)擴(kuò)增方法相比，測試數(shù)據(jù)擴(kuò)增效率平均分別提高了約56%和81%。由此可看出本文方法在回歸測試中生成覆蓋目標(biāo)路徑的測試數(shù)據(jù)具有較高的效率。而且，通過多次運(yùn)行結(jié)果求得的標(biāo)準(zhǔn)差可以看出，本文方法在穩(wěn)定性方面也具有較好的優(yōu)勢。

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

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

5結(jié)語

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

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

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

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

參考文獻(xiàn)：

[1]

張智軼，陳振宇，徐寶文，等.測試用例演化研究進(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)，任麗娜.回歸測試數(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)性的回歸測試數(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]

胡旺，李志蜀.一種更簡化而高效的粒子群優(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)化算法的測試數(shù)據(jù)自動(dòng)生成技術(shù)研究[D].徐州：中國礦業(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)縮減的路徑覆蓋測試數(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.