基于路徑引導的回歸測試用例集擴增方法*

殷鵬川，賁可榮

(海軍工程大學計算機工程系， 湖北 武漢 430033)

基于路徑引導的回歸測試用例集擴增方法*

殷鵬川，賁可榮

(海軍工程大學計算機工程系， 湖北 武漢 430033)

為了全面測試演化軟件，回歸測試通常需要生成新的測試用例。concolic測試是一種沿著具體執行路徑進行符號執行的軟件驗證技術，通過生成測試數據來執行程序的所有可行路徑。回歸測試中，由于concolic測試關注于程序本身，沒有利用已有測試用例和軟件演化信息，導致生成大量無效測試數據，浪費資源和時間。為解決此問題，提出一種基于路徑引導的回歸測試用例集擴增方法。該方法將目標路徑作為引導，根據軟件演化信息選擇有利于覆蓋目標路徑的測試用例，利用已有測試用例跳過重疊初始子路徑，對后續目標子路徑進行concolic測試并生成覆蓋目標路徑的測試數據。案例分析表明，本文方法相比傳統concolic測試，本方法在覆蓋程序可行路徑的同時，可有效減少concolic測試路徑，提高測試數據生成效率。

回歸測試；concolic測試；測試用例集擴增；測試數據生成；路徑覆蓋

1 引言

回歸測試是指修改現有軟件后，對演化軟件重新測試，以確認新引入的修改沒有妨礙現有未修改部分的功能[1]。為了全面測試演化軟件，需要生成新的回歸測試用例。與傳統測試數據生成相比，回歸測試數據的生成更有針對性。測試用例集擴增通過利用已執行測試用例信息和程序修改信息生成新測試用例集，覆蓋演化程序的修改部分，使新老用例集合滿足演化軟件的測試需求[2]。

concolic測試技術[3]是一種結合了具體(concrete)執行和符號(symbolic)執行的自動化測試技術，可以最大化代碼覆蓋率并生成相應測試數據。但是，用于測試用例集擴增的傳統concolic測試，僅從程序本身出發而未利用程序修改信息作為引導，生成、執行了大量沒有覆蓋目標路徑的測試輸入，浪費資源時間，測試數據生成效率低下。縮小concolic測試范圍、提高測試用例集擴增效率對于暴露演化軟件問題、提高軟件質量具有重要意義。

2 研究背景

出于簡化符號執行的目的，Sen K等人[3]最早提出concolic測試，將具體執行和符號執行結合起來驗證程序，并將實現的CUTE工具應用于含有指針等復雜數據結構的C語言程序。在減少concolic測試路徑數量方面，崔展齊等人[4]將靜態分析得出的可疑語句作為目標指導concolic測試，安靖等人[5]提取重復的外部調用的函數摘要以替代展開測試，王欣等人[6]利用二進制補丁比對結果來指導concolic測試，以上三篇文獻均關注于對concolic測試本身的改進，而本文在改進的同時，將其應用于測試用例集擴增。

本文相關的另一個領域是面向覆蓋的測試用例集擴增技術，其常用方法有遺傳算法和concolic測試。遺傳算法方面，張巖等人[7]將目標路徑分離出子路徑，固定子路徑對應的輸入分量，縮小遺傳操作范圍，但其只適用于可分路徑的程序；基于文獻[7]，鞏敦衛等人[8]根據已有測試數據路徑與目標路徑的相似度進一步縮小初始種群范圍。但相比concolic測試，遺傳算法占用資源開銷較多，效率不高[9]。concolic測試方面，Taneja K等人[10]通過避免探索不相關路徑以及優先探索更有希望檢測到不同行為的路徑，減少了符號執行次數，但其沒有利用已執行測試用例信息；Xu Z等人[11]通過重新執行現有用例，去除與演化軟件修改部分無關的分支，減少了concolic測試路徑數量，但只實現了分支覆蓋。

本文結合文獻[11]的優勢，利用已有測試用例信息和程序修改信息，提出了一種基于路徑引導的回歸測試用例集擴增方法，縮小concolic測試范圍，實現對程序可行路徑的高效覆蓋。

3 回歸測試用例集擴增算法

建立回歸測試用例集擴增問題的模型。記原來的程序為P，修改后的程序為P′，P的測試用例集為T。已知P和P′的控制流圖CFG(Control Flow Graph)，對此處的CFG有如下要求：(1)每個節點的出度不大于2，將switch等多分支判斷轉換成多個嵌套的if分支，且不考慮并行程序；(2)不存在回路，將while、for等循環(n為最大循環次數)轉換為執行循環0次、1次、2次、m次(m

因此，本文提出基于路徑引導的回歸測試用例集擴增算法，如算法1所示，分為三個步驟：首先選擇可能發現演化軟件變化的測試用例(步驟1，調用3.1節的算法2)；然后，找到目標路徑中與選擇后用例路徑的重疊部分，跳過其中初始子路徑(步驟2，調用3.2節的算法3)；最后，采用concolic測試覆蓋目標路徑中剩余的子路徑并生成測試數據(步驟4，調用3.3節的算法4)。

算法1基于路徑引導的回歸測試用例集擴增算法

輸出：T′。

步驟1調用SelectTC;

步驟2調用SameSub;

步驟4調用DirectedConcolic;

步驟5end if

3.1 選擇有效測試用例

回歸測試中，T可以覆蓋P′的大部分路徑，對于P′中沒有覆蓋到的路徑，需要利用軟件演化信息，從T中選出有利于覆蓋目標路徑的測試用例，以提高生成覆蓋目標路徑的測試用例的效率。

算法2測試用例選擇算法SelectTC

輸入：T、CFGP、CFGP′。

步驟1調用DejaVu分析CFGP和CFGP′，找到所有敏感邊eDangerous;

步驟2重新執行T;

步驟5將T中經過這些eDangerous的用例加入TiSelected;

步驟6endfor

3.2 處理重疊初始子路徑

擴增測試用例集時，利用已執行測試用例信息可有效減少無效用例的生成，提高測試用例集擴增效率。本節考察目標路徑中與用例路徑重疊的子路徑(多條邊的序列)，利用經過重疊初始子路徑的用例數據，縮小concolic測試范圍，減少需要展開執行的邊。

算法3重疊初始子路徑處理算法SameSub

步驟2foreachtj∈TiSelecteddo

步驟3得到重疊子路徑

步驟5找到重疊子路徑中經過e1的子路徑，記錄該子路徑的有向邊數量;

步驟6endif

步驟7endfor

步驟9endfor

3.3 路徑引導concolic測試

傳統concolic測試通過不斷取反路徑條件以期覆蓋CFG中所有可行路徑，但其沒有限制需要取反的路徑條件范圍。回歸測試中，T可以覆蓋P′與P相同的部分，我們關注的是P′的修改部分能否被覆蓋，沒有必要取反所有路徑條件。因此，在已知目標路徑的前提下，僅需將目標路徑作為引導，縮小需要取反的路徑條件范圍，減少約束求解器的調用次數。

傳統concolic測試流程如下：

(1)將一組特定的變量選為輸入變量，符號執行過程中，這些變量將被視為符號變量。所有其他變量將被視為具體的值。

(2)插裝待測程序，以便在具體執行的同時記錄符號變量值和路徑條件。

(3)選擇任意測試數據開始。

(4)執行程序。

(5)沿該路徑重新符號執行程序，生成了一套符號約束(包括路徑條件)。

(6)取反最后一個尚未取反的路徑條件，以訪問一個新的執行路徑。如果不存在這樣的路徑條件，算法終止。

(7)調用約束求解器生成新的測試數據。如果沒有測試數據能夠滿足約束條件，則返回(6)，以嘗試下一個執行路徑。

(8)返回(4)。

算法4路徑引導concolic測試算法DirectedConcolic

步驟5取反ej源節點的路徑條件，調用約束求解器生成新的測試數據tGenerated;

步驟6if沒有測試數據能夠滿足約束條件

步驟8endif

步驟10endif

步驟11endfor

步驟13endfor

需要注意的是，算法4每完成一次循環得到計算結果，算法2和算法3就可以利用這一步結果優化下一步的計算，即將算法4最新生成的用例加入到算法2和算法3的用例處理中，可以進一步縮小concolic測試范圍，節省開銷。

4 實例分析

為了驗證本文方法的有效性，采用軟件測試中常用的三角形分類程序作為基準程序P。對比本文方法與傳統concolic測試，以生成覆蓋所有可行路徑的測試數據為終止條件，將整個過程中concolic測試取反次數(或者是concolic測試路徑數量)作為評價指標，取反次數越少，則調用約束求解器次數越少，concolic測試所需開銷也就越小。

分析P的CFG，如圖1a所示，輸入三條邊長，輸出“不是三角形”(n2)、“等邊三角形”(n4)、“等腰三角形”(n6)、“不規則三角形”(n7)，分支節點n1、n3、n5分別判斷是否是三角形、等邊三角形、等腰三角形。修改后程序P′的變化之處如圖1b所示：分支節點n6、n9、n7、n11分別判斷是否是直角三角形、銳角三角形、直角三角形、銳角三角形。覆蓋P中所有路徑的測試用例t1=(1,2,3)，t2=(3,3,3)，t3=(2,2,3)，t4=(3,4,5)。

Figure 1 Control flow graphs of the program before and after modification圖1 程序修改前后的控制流圖

然后使用傳統concolic測試方法。根據3.3節給出的傳統concolic測試流程，可以得到concolic測試取反次數為8。

通過上述分析知道，在縮小concolic測試范圍方面，本文方法優于傳統concolic測試，在覆蓋程序可行路徑的同時，可以有效減少concolic測試路徑數量。

5 結束語

針對回歸測試中concolic測試生成測試數據時缺乏指導，導致生成和執行大量不能覆蓋目標路徑的測試數據、消耗大量測試資源的問題，本文提出一種基于路徑引導的回歸測試用例集擴增方法。以目標路徑為引導，測試經過了敏感邊的測試用例，跳過最長的重疊初始子路徑，采用concolic測試覆蓋目標路徑中剩余的子路徑并生成測試數據，縮小concolic測試范圍，提高測試數據生成效率。

盡管本文方法有效提高了concolic測試用例集擴增效率，但受限于concolic測試采用的約束求解器，只對常規數據類型輸入變量的程序才有明顯的優越性。實際軟件可能含有結構體等數據類型復雜的輸入變量，如何擴大適用范圍是需要進一步研究的問題。

[1]YooS,HarmanM.Regressiontestingminimization,selectionandprioritization:Asurvey[J].SoftwareTesting,VerificationandReliability,2012,22(2):67-120.

[2]ZhangZhi-yi,ChenZhen-yu,XuBao-wen,etal.Researchprogressontestcaseevolution[J].JournalofSoftware,2013,24(4):663-674. (inChinese)

[3]SenK,MarinovD,AghaG.CUTE:AconcolicunittestingengineforC[C]∥Procofthe13thACMSIGSOFTInternationalSymposiumonFoundationsofSoftwareEngineering,2005:263-272.

[4]CuiZhan-qi,WangLin-zhang,LiXuan-dong.Target-directedconcolictesting[J].ChineseJournalofComputers,2011,34(6):953-964. (inChinese)

[5]AnJing,ZhongJin-xin,WeiGeng-yu,etal.Applicationsoffunctionsummaryinconcolictesting[J].JournalofBeijingUniversityofPostsandTelecommunications, 2012, 35(1):24-27. (inChinese)

[6]WangXin,GuoTao,DongGuo-wei,etal.Concolictestingbasedonpatchcomparisons[J].JournalofTsinghuaUniversity(Science&Technology), 2013, 53(12):1737-1742.(inChinese)

[7]ZhangYan,GongDun-wei.Evolutionarygenerationoftestdataforpathcoveragebasedonautomaticreductionofsearchspace[J].ChineseJournalofElectronics,2012, 40(5):1011-1016. (inChinese)

[8]GongDun-wei,RenLi-na.Evolutionarygenerationofregressiontestdata[J].ChineseJournalofComputers, 2014, 37(3):489-499. (inChinese)

[9]XuZ,KimY,KimM,etal.Directedtestsuiteaugmentation:Techniquesandtradeoffs[C]∥Procofthe18thACMSIGSOFTInternationalSymposiumonFoundationsofSoftwareEngineering,2010:257-266.

[10] Taneja K,Xie T,Tillmann N,et al.Guided path exploration for regression test generation[C]∥Proc of the 31st International Conference on Software Engineering-Companion, 2009:311-314.

[11] Xu Z,Rothermel G.Directed test suite augmentation[C]∥Proc of Asia-Pacific Software Engineering Conference,2009:406-413.

[12] Pressman R S.Software engineering:A practitioner’s approach[M].7th ed.New York:McGraw Hill Higher Education, 2009.

[13] Rothermel G,Harrold M J.A safe,efficient regression test selection technique[J].ACM Transactions on Software Engineering and Methodology,1997,6(2):173-210.

附中文參考文獻：

[2] 張智軼, 陳振宇, 徐寶文, 等. 測試用例演化研究進展[J]. 軟件學報, 2013, 24(4):663-674.

[4] 崔展齊, 王林章, 李宣東. 一種目標制導的混合執行測試方法[J]. 計算機學報, 2011, 34(6):953-964.

[5] 安靖, 鐘金鑫, 魏更宇, 等. 函數摘要在Concolic測試方法中的應用[J]. 北京郵電大學學報, 2012, 35(1):24-27.

[6] 王欣, 郭濤, 董國偉, 等. 基于補丁比對的Concolic測試方法[J]. 清華大學學報(自然科學版), 2013, 53(12):1737-1742.

[7] 張巖, 鞏敦衛. 基于搜索空間自動縮減的路徑覆蓋測試數據進化生成[J]. 電子學報, 2012, 40(5):1011-1016.

[8] 鞏敦衛, 任麗娜. 回歸測試數據進化生成[J]. 計算機學報, 2014, 37(3):489-499.

YINPeng-chuan,born in 1990,MS candidate,his research interest includes software quality assurance.

Path-directedregressiontestsuiteaugmentation

YIN Peng-chuan，BEN Ke-rong

(Department of Computer Engineering,Naval University of Engineering,Wuhan 430033,China)

To test the evolution software fully,new test cases need to be generated in regression testing typically.concolic testing is a hybrid software verification technique that performs symbolic execution along a concrete execution path,and can perform all the feasible paths of a program by generating test data.Concolic testing only focuses on the program under test with both existing test cases and software evolution information unexploited in regression testing, which results in a large number of invalid test data generation,wasting resources and time.To address this problem,a path-directed regression test suite augmentation approach is proposed. With the guidance of target paths,the approach selects the test cases conducive to cover target paths according to software evolution information,skips initial overlapping sub-paths by using the existing test cases,takes the follow-up target sub-path to guide concolic testing and generates test data covering the target paths.Case analysis demonstrates that the proposed approach can effectively reduce concolic testing paths in comparison to traditional concolic testing, and improves the efficiency of test data generation while covering feasible paths of the program.

regression testing;concolic testing;test suite augmentation;test data generation;path coverage

1007-130X(2014)11-2159-05

2014-07-10;

：2014-09-10

國家自然科學基金資助項目(61272108)

TP311.55

：A

10.3969/j.issn.1007-130X.2014.11.018

殷鵬川(1990),男，湖北孝感人，碩士生，研究方向為軟件質量保證。E-mail:ypciehnnu@163.com

通信地址：430033 湖北省武漢市解放大道717號233信箱

Address:Mail Box 233,717 Jiefang Avenue,Wuhan 430033,Hubei,P.R.China