基于路径引导的回归测试用例集扩增方法*

2014-09-13殷鹏川贲可荣

计算机工程与科学 2014年11期

关键词：测试用例测试数据调用

殷鹏川，贲可荣

(海军工程大学计算机工程系，湖北武汉 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