基于自適應粒子群優化算法的測試數據擴增方法

王曙燕　溫春琰　孫家澤

摘要：

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

關鍵詞：

回歸測試；目標路徑；測試數據擴增；路徑相似度；粒子群優化算法

中圖分類號：

TP311.5

文獻標志碼：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，Firstly， 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.

英文關鍵詞Key words：

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

0引言

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

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

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

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

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

4.2實驗結果

為驗證本文方法的有效性，選擇基于遺傳算法（GA）和隨機法的測試數據擴增方法與本文方法進行比較，在相同的條件下，對測試程序各定義一個或多個修改點，分別運行20次，生成覆蓋目標路徑的測試數據，記錄每種方法的進化代數和耗時，分別計算它們的平均值和標準差，最終實驗結果如表2所示。

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

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

通過上述分析，可以得到如下結論：對于基準程序和西門子工業程序，本文提出的基于自適應粒子群算法的回歸測試數據集擴增方法在充分利用原有測試數據集的基礎上，可以消耗較少的代價，更穩定地生成覆蓋目標路徑的測試數據集。

5結語

在面向覆蓋的測試數據集擴增方法中，如何充分利用已

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

基于自適應粒子群算法的測試數據集擴增方法，該方法通過對多個基準程序和西門子工業程序進行測試，并與利用遺傳算法和隨機法的回歸測試數據擴增方法進行比較，實驗結果表明，本文所提方法在生成覆蓋目標路徑測試數據的效率和穩定性上都具有明顯的提高。

在回歸測試數據的擴增過程中，利用測試數據的穿越路徑和目標路徑的相似度來衡量測試數據的優劣，雖然在一定程度上提高了測試數據生成的效率和穩定性，但是在復雜的實際軟件中，如何在測試數據的演化過程中利用更多的路徑信息，進而提高生成覆蓋目標路徑測試數據的效率，是下一步需要繼續研究的問題。

參考文獻：

[1]

張智軼，陳振宇，徐寶文，等.測試用例演化研究進展[J].軟件學報，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]

鞏敦衛，任麗娜.回歸測試數據進化生成[J].計算機學報，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]

吳川，鞏敦衛.基于路徑相關性的回歸測試數據進化生成[J].

計算機學報，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]

胡旺，李志蜀.一種更簡化而高效的粒子群優化算法[J].軟件學報，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]

史嬌嬌.基于遺傳粒子群優化算法的測試數據自動生成技術研究[D].徐州：中國礦業大學，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]

張巖，鞏敦衛.基于搜索空間自動縮減的路徑覆蓋測試數據進化生成[J].電子學報，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.