遗传算法辅助的动态符号执行测试方法

谢章伟，崔展齐，郑丽伟，张志华

北京信息科技大学 计算机学院，北京 100101

1 引言

由于软件缺陷的存在，程序在运行过程中可能会出现一些不正常的行为，轻则造成程序功能异常，重则导致系统崩溃。软件测试作为检测软件缺陷的一种重要方法，能够有效检测出程序存在的缺陷，提升软件的可靠性[1]。符号执行作为一种重要的软件测试方法，能够通过生成高覆盖率的测试用例，检测隐藏较深的程序错误。

King 等人[2]于1975 年提出使用符号执行进行软件分析，其基本思想是使用符号值表示输入变量，在运行程序的过程中逐语句转换成符号表达式，收集相应的路径约束条件，并通过约束求解器求得满足路径约束条件的测试用例。当时由于受制于约束求解器求解能力，导致符号执行的路径覆盖率远小于程序分析方法，使得研究陷入了低谷。随着现代计算机计算能力的增强，以及研究人员对于约束求解器的不断优化和改进，例如Z3[3]、MathSAT4[4]等性能优秀的约束求解器的出现，使得符号执行技术重新引起研究人员的关注[5]。常见的符号执行工具有 Symbolic Pathfinder[6]、KLEE[7]、JDart[8]、jCUTE和CUTE[9]等。尽管约束求解器的相关研究取得了突破性的发展，但随着程序规模和复杂程度的剧增，约束求解器依旧面临路径爆炸、求解能力不足等问题[5，10]。

为此，常亮等人[11]提出采用并行化方法减少符号执行中路径探索和约束求解耗时问题，该方法基于Actor模型并行模式，将动态符号执行中的约束求解任务和路径探索任务并行执行，减少耗时代价；Bryant[12]使用积极算法，将SMT公式转换成一个CNF型的命题公式，然后使用SAT求解器进行求解，通过高效地利用SAT求解器提升SMT的求解效率；Nuzzo[13]则提出使用凸规划求解非线性凸的约束条件的可满足性。虽然上述工作能够在一定程度上缓解约束求解器求解能力不足的问题，但动态符号执行的覆盖率仍受限于约束求解器的求解能力。

针对上述问题，本文提出了一种遗传算法辅助的动态符号执行测试方法。首先，通过动态符号执行工具收集约束条件，当约束求解器无法求解当前约束条件或者求解时间超时，使用遗传算法生成测试输入；然后，根据输入变量的数据类型生成一定数量的初始种群，通过适应度函数计算每个个体的适应度，根据适应度大小剔除适应度低的个体，通过对筛选之后的个体进行交叉变异和随机变异生成新的种群；不断迭代上述过程，直到生成满足约束条件的测试输入为止。本文基于所提出的方法开发了原型工具JDart-Ga，并在JDart 提供的测试用例集上进行了实验。实验结果表明，对于存在JDart无法覆盖路径的3 个实验对象，JDart-Ga 的路径覆盖率均取得了提升，路径覆盖率最低提升了16%，最高提升了23%，同时测试时间增加不超过10%。

本文的主要贡献包括：

（1）提出了一种遗传算法辅助的动态符号执行测试方法，为约束求解器不能有效求解的路径生成测试输入。

（2）基于所提出的方法实现了原型工具JDart-Ga，并在一组公开的示例程序上进行实验，以验证该方法的有效性。

2 研究背景

2.1 动态符号执行

动态符号执行[14]结合使用了具体执行和符号执行，不再静态模拟程序执行，而是为程序提供具体的输入，通过实际运行程序，在程序运行中对程序进行动态分析。在动态符号执行的过程中，对符号变量相关的代码段进行符号执行，使用约束求解器求解路径约束条件，为每条路径生成一个测试用例，将测试用例输入并执行程序。通常情况下约束求解器有三种返回结果：如果约束求解器求解返回值为sat，则表示当前约束条件有解并已经找到某个合适的解；返回值为unsat，则表示当前约束条件无解；但如果返回值为don’t know，则表示约束求解器无法判断当前约束条件是否有解。动态符号执行根据约束求解器的返回结果来选择是否应该沿着当前路径继续往下探索。

2.2 遗传算法

遗传算法由Holland 提出[15]，是一种模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程的全局最优搜索方法，近些年来被广泛运用于信息安全[16]、软件测试[17]等领域。在达尔文进化论中提到，生物是通过不断的基因变异来实现物种的进化，而自然选择主导着进化的方向。基因突变的方向是随机性的，自然选择通过不断淘汰不适应环境的类型，从而定向地改变种群中的基因向适应环境的方向演化。遗传算法正是以此为指导思想，通过对问题的解（称为个体）进行编码，表现成染色体形式，通过模拟基因的随机突变和交叉变异的方式实现个体的进化，并使用适应度函数评估当前个体的适应度，根据适应度的高低衡量个体对目标问题的适应度，选择使用具有高适应度的个体进行遗传，从而增大产生满足目标问题解的概率。

3 遗传算法辅助的动态符号执行测试方法

本文提出的方法框架如图1所示，该方法主要包括两个阶段，左边的是动态符号执行阶段，右边是遗传算法阶段。给定一个程序，首先进行动态符号执行测试，使用动态符号执行工具收集一条路径上的约束条件，将其传递给约束求解器，根据约束求解器的求解结果result选择下一步操作。若求解结果result为sat或unsat，则直接将结果返回给动态符号执行工具，若求解结果result=don’t know或者求解时间超时，则尝试使用遗传算法生成测试用例。通过不断迭代上述过程，以覆盖更多程序路径。

图1 遗传算法辅助的动态符号执行测试框架

3.1 动态符号执行

图2 展示了本文所使用的动态符号执行方法流程。与传统动态符号执行方法相比，增加了一个调用遗传算法生成测试输入的步骤。首先，选择一个目标程序，收集目标程序中的输入变量并将其符号化，给定一个初始输入并运行程序，从而获得一条路径约束条件集合。然后按照深度优先调度策略将路径中的约束取反，获得一条未覆盖路径的约束条件集合，使用约束求解器对约束条件集合进行求解，若约束求解器求解的结果为don’t know或者求解时间超时，则使用遗传算法尝试生成下一条路径的测试输入，否则直接将约束求解器的求解结果传递给动态符号执行工具。不断重复上述过程，直到所有路径都遍历完毕。

图2 动态符号执行方法流程

3.2 遗传算法

遗传算法的优点是在搜索过程中不需要关注问题的内在性质，对于目标函数和约束条件，无论是线性的还是非线性的，离散的还是连续的都可处理。

本文使用遗传算法对约束求解器无法求解的约束条件进求解，具体的求解过程如算法1所示。算法1的输入为一条为约束求解器无法求解的路径约束条件集合constraintsExpr={expr1，expr2，…，expri}，其中，expri表示路径上的约束条件。输出为求解结果result，输出的求解结果有两种，若生成了满足约束条件集合constraintsExpr的测试用例，则result=sat和满足约束条件的测试输入，否则返回result=don’t know。在算法1 中，population表示包含一定数量个体的初始种群，num表示种群进化的最大次数，size表示每次变异后下一代生存的个体数量。

在算法1 中，首先根据传入的约束条件集合con-straintsExpr获取输入变量的数据类型，然后根据输入变量的数据类型生成一定数量的种群population，计算当前种群中每个个体的适应度Fitness，如果当前个体的适应度Fitness=0，则说明当前个体为路径约束条件constraintsExpr中所有约束条件的解，将解返回并结束。如果不满足，则根据适应度的大小从小到大进行排列，保留排序靠前size的个体，通过对个体染色体进行交叉变异和随机变异操作，产生新的种群newPopulation，不断重复上述过程，直到找到满足路径约束条件constraintsExpr的个体为止。但如果种群进化的次数大于num时，仍然没有生成满足路径约束条件constraintsExpr的测试用例时，出于对时间成本的考虑，结束循环并返回result=don’t know。

算法1使用遗传算法生成测试用例

input：constraintsExpr：路径约束条件

output：result：求解结果

1.SymbolicPar=constraintsExpr.containsAl（l）；

2.population=createInitialPopulation（SymbolicPar）；

3.//生成初始种群

4.foreach（evolve（num）） do

5.//进化到第num代之后就结束

6.foreach（chromosome：population）do

7.Fitness=calculate（chromosome）；

8.//计算每个个体的适应度

9.i（fFitness==0）then

10.return result；

11.end

12.newPopulation.sortByFitness（population）；

13.//根据适应度大小排序

14.newPopulation.trim（size）；

15.//剔除第population个之后的所有个体

16.newPopulation.chromosome.crossove（r）；

17.//交叉变异

18.newPopulation.randomChromosome（）；

19.//随机变异

20.population=newPopulation；

21.end

22.end

23.returnresult；

其中，适应度函数是决定是否能成功生成测试输入的关键，适应度函数的合理性决定生成测试用例的效率[18]。由于本文使用遗传算法求解满足路径约束条件的解，故使用公式（1）来评价当前个体的适应度：

其中，length表示当前路径约束条件集合constraintsExpr中约束条件的个数，N表示当前个体满足路径约束条件中约束条件的个数，N越大，适应度的值Fitness越低，说明当前个体越接近满足路径约束条件的解。

3.3 示例

以图3 所示的代码片段为例，该段代码来自JDart提供的示例程序double2long。若使用动态符号执行方法，假设当前输入为x=10.0，则覆盖路径的约束条件集合为constraintsExpr={x≥0.0,(sint64)(x/10.0)＜100} ，根据深度优先遍历策略，将当前路径约束条件集合中的第2个约束条件取反，则获得了一条新的路径约束集合{x≥0.0,(sint64)(x/10.0)≥100} 。此时约束求解器无法求解该条路径的约束条件集合，返回的求解结果为result=don’t know，动态符号执行工具无法覆盖该条路径。若使用本文所提出的方法，当约束求解器返回result=don’t know时，将使用遗传算法生成满足目标路径约束条件的测试输入，将约束条件constraintsExpr={x≥0.0,(sint64)(x/10.0)≥100} 作为参数传递给遗传算法模块，求得当x=1 000.1 时，该路径约束条件有解，则返回result=sat和测试用例x=1 000.1，从而辅助动态符号执行工具覆盖上述路径。

图3 代码示例

4 实验分析

基于上述方法，本文在Java符号执行工具JDart的基础上，实现了符号执行工具JDart-Ga。运行实验的软硬件环境为Intel®Core™i7-7700HQ处理器，主频为2.80 GHz，内存2 GB，操作系统为Ubuntu 14.04，Sun JRE 1.8（64 bit mode）。

JDart[19]是一个基于Java PathFinder 框架的符号执行工具。在检测Java 程序的过程中，JDart 能够同时进行具体执行和符号执行，并将路径约束组合起来，形成约束树。JDart 通过SMT 求解器生成测试用例，并且尝试运行从而收集未探索分支的路径，不断增强约束树。

在实验分析中延用了JDart 的路径分类方式，使用OK PATHS 统计测试用例能覆盖并且不会触发错误的路径数量；使用ERROR PATHS统计检测出存在错误的路径数量，例如断言或者未捕获的异常，断言违规或未捕获的异常等；使用DON’T KNOW PATHS 统计未探索的路径数量；使用TOTAL PATHS 统计总的路径覆盖情况，即 TOTAL PATHS 等于 OK PATHS、ERROR PATHS和DON’T KNOW PATHS之和。

4.1 实验设计

为了验证所提出方法的有效性，本文将JDart 所提供的17个测试示例全部作为实验对象，实验对象信息如表1所示。表1中测试对象的命名方法为“类名称_类内被测试方法名称”。17个测试对象的输入变量包括int、char、double、long和boolean等数据类型。

表1 实验对象基本情况

实验沿用文献[7]所使用的评价方法，使用覆盖路径数量、路径覆盖率和测试的时间开销进行对比分析。其中，路径覆盖率Cov的计算公式如公式（2）所示：

在公式（2）中，okPaths和errorPaths分别表示OK PATHS和ERROR PATH 的值，两者相加表示测试用例能够覆盖的路径数量，max{totalPathsJDart,totalPathsJDart-Ga}表示JDart和JDart-Ga中TOTAL PATHS的最大值。

在统计时间开销的过程中，本文规定测试单个程序的时间上限不超过30 min，超出30 min 则记为超时，时间开销记为30 min，覆盖的路径数量记为30 min内覆盖的路径。在实验过程中，本文将遗传算法中的参数值分别设置为：初始种群中的个体数population=100，每次进化之后下一代生存的个体数量size=100，进化的次数num=1 000。

4.2 实验结果及分析

在实验过程中，使用JDart和JDart-Ga分别对表1中测试对象进行测试，并收集了相关的路径覆盖信息，实验结果如表2和图4所示。其中，表2为三种路径的覆盖情况，图4为路径覆盖率。从表2中可以看出，当DON’T KNOW PATHS为零时，即表示不存在SMT求解器无法求解的约束条件，所以JDart-Ga 和JDart 覆盖的OKPATHS、ERROR PATHS 和 TOTALS PATHS 都相等。在17个测试对象中，有11个测试对象不存在SMT求解器无法求解的路径约束条件，剩余6个测试对象中存在无法探索的路径。其中，对于solvers_foo、nested_bar 和double2long_foo 3 个测试对象，JDart-Ga 的路径覆盖数量高于JDart，路径覆盖率分别提升了20%、23%和16%。具体来说，OK PATHS 分别增加了 0、2 和 1 条，ERROR PATHS分别增加了1、1和0条，TOTALS PATHS分别增加了0、6和0条。

表2 不同路径覆盖情况对比

图4 路径覆盖率对比

对JDart-Ga 提升上述3 个实验对象路径覆盖率的原因进行分析发现：（1）如果路径约束条件中涉及强制类型转换，有可能会出现同一输入变量在路径约束条件中存在两种不同的数据类型的情况，约束求解器求解此类约束条件时间开销过大，导致超出规定的时间，nested_bar 和double2long_foo 中存在这种类型的约束条件，例如：nested_bar 中的路径约束条件{d<3.141，（sint32）d+65>64，5×（（sint32）d+65）>325，（sint32）d+65!=66}；（2）当存在约束求解器不能求解的复杂约束条件时，可以利用遗传算法优势，根据测试用例的适应度不断变异生成趋近于满足路径约束条件的解，例如：对于solvers_foo中的路径约束条件{d≥ 0.0，d≤ 6.283 185 307 179 586，sin（d）<0.0，cos（d）>0.0}，JDart无法求解，而JDart-Ga可以成功生成测试输入d=4.715 407 046 706 579。

表3对JDart和JDart-Ga测试17个实验对象的时间开销进行了统计。由于JDart-Ga相比于JDart增加了一个求解判断模块，所以测试实验对象所需的时间花销要比JDart略长。如表3所示，与JDart相比，JDart-Ga测试solvers_foo、nhandler_foo、functions_foo、fields_foo 和double2long_foo 5 个实验对象的时间开销增幅超过10%；测试nested_bar 的时间开销减少了99.8%；测试剩余11 个实验对象的时间开销增幅低于10%，与预期相符。对5 个时间开销增幅超过10%的实验对象进行代码分析发现：（1）solvers_foo 和 double2long_foo 中均存在JDart 无法覆盖的路径，JDart-Ga 覆盖了更多的程序路径，从而导致时间开销分别增加了15.2%和14.8%；（2）fields_foo、functions_foo和nhandler_foo中的DON’T KNOW PATHS 为约束求解器报告错误，实际上应该为unsat，而遗传算法并不能从逻辑上去判断约束条件是否有解，这导致JDart-Ga仍尝试使用遗传算法生成覆盖上述路径的测试输入，消耗了大量无效时间，时间开销分别增加了596.6%、400.9%和372.7%。对测试时间开销大幅降低的nested_bar 进行分析，发现在该程序中有8条路径约束条件都含有强制类型转换操作，故约束求解器在无法判断该类型的路径约束条件是否有解的过程中消耗了大量的时间，而JDart-Ga 可以快速求解，从而节省了大量时间开销。

表3 测试时间对比 ms

5 总结

本文深入研究了现有符号执行测试方法面临的问题和挑战，提出了一种遗传算法辅助的动态符号执行测试方法。该方法能够弥补动态符号执行中约束求解器所存在的求解能力不足的问题，从而达到提升路径覆盖的目的。实验结果表明，本文提出的方法能够有效地提升路径覆盖率。在下一步工作中，将尝试将优化本方法应用于更加复杂的输入数据类型和更大规模程序。