引用:
Pietro Braione, Giovanni Denaro, SUSHI: A Test Generator for Programs with Complex Structured Inputs, ACM/IEEE 40th International Conference on Software Engineering: Companion Proceedings, 2018, 21-24
摘要：
随机的和基于搜索的测试生成器基于程序 API 生成实际的测试用例，但是经常缺少依赖复杂数据结构实例的结构化测试目标； 符号执行可以精确地描述那些依赖关系，但不计算方法序列以实例化它们。 我们介绍 SUSHI，这是一种用于具有复杂结构输入的程序的高覆盖率测试用例生成器。 SUSHI 利用符号执行来生成精确描述程序路径和输入数据结构之间关系的路径条件，并将路径条件转换为基于搜索的测试生成问题的适应度函数。 搜索问题的解决方案是合法的方法序列，该方法序列实例化结构化的输入以执行由路径条件标识的程序路径。 我们的实验表明，SUSHI 可以很好地补充当前的自动测试生成工具。
关键词：自动测试用例生成，符号执行，基于搜索的软件工程
1.介绍
自动生成测试用例减轻了编写测试的负担。当前的测试生成器利用随机测试，基于搜索的测试和符号执行。 随机测试生成器通过对方法序列进行随机采样来合成测试用例，以通过其公共接口来运行被测程序。基于搜索的测试生成器利用适合特定代码元素（例如程序分支）执行的适应度函数来指导随机选择。随机和基于搜索的测试生成器都忽略程序控制流和输入数据结构之间的关系。结果，他们可以成功地合成实例化简单数据结构的方法序列，但不能令人满意地处理只能由复杂输入数据结构触发的测试目标。
图 1 中第 14 行的分支体现了对数据结构的复杂依赖。程序采用两个进程列表（第 3 行），将主列表中的进程设置为具有高优先级（第 4-5 行），构建一个新列表，其中包括主列表的所有进程（第 6 行），可能还有次级列表中的所有进程（第 7-10 行），最后通过首先执行高优先级的进程（第 11-13 行）来处理结果列表，同时推迟其他进程（第 14 行）。在第 14 行执行延迟代码的测试用例必须使用一个比物理单元更多进程数量（8 个）的主列表以及一个至少有一个低优先级进程的次级列表才能调用方法 execPool,。最先进的随机和基于搜索的测试生成器（如 Randoop 和 EvoSuite）在 12 小时内没有覆盖图 1 中第 14 行的分支：纯随机抽样发现所需输入的概率可忽略不计;尽管基于搜索的算法没有指导来识别它，但要满足分支条件 p.getPriority
一些符号执行器生成的路径条件精确地表征了对输入数据结构的约束，以执行给定的程序路径，例如，图 1 中第 14 行的分支的路径条件。它们不会直接生成可执行的测试用例，这些用例会实例化满足路径条件的具体数据结构。一些测试生成器通过生成一些绕过程序接口并直接操作内存的测试来解决此问题，但是最近的研究表明，这种做法导致了许多不切实际甚至有时是非法的测试用例。其他符号执行器则利用静态分析来确定满足路径条件的方法序列。他们成功地生成了实例化简单数据结构的测试用例，但由于理论上的局限性以及平衡其静态分析的效率与精度的困难而未能处理复杂的数据结构。
图 1 样例程序 execPool()
本文介绍了 SUSHI，这是一种测试生成器，它可以有效地生成由合法方法调用序列组成的测试用例，这些测试用例将会测试复杂结构输入依赖的程序。SUSHI 实例化了我们在最近的论文中介绍的方法。SUSHI（i）符号执行程序获取能代表程序路径与输入数据结构之间依存关系的路径条件，（ii）选择适当的路径条件子集以解决某些覆盖目标，（iii）将选定的路径条件转换成适合度函数，该函数量化输入状态与满足路径条件的距离，并且（iv）利用适合度函数进行元启发式搜索以生成满足路径条件的方法调用的合法序列。
本文通过详细研究 SUSHI 工具的设计和实现来开展研究论文。 本文（i）阐述了该工具的模块化架构，（ii）指定了 SUSHI 用于在选定的覆盖率标准上最大化覆盖结果的路径选择算法（iii）说明了利用利用由路径条件派生的适应度函数所指导的 EvoSuite 测试生成器的 SUSHI 元启发式搜索阶段（iv）描述了 SUSHI 用于减轻不可行路径对测试收缩过程的影响的反馈循环，以及（v）讨论了最终用户如何使用 SUSHI 自动生成高覆盖率测试用例
2. SUSHI 设计
SUSHI 是为 Java 程序服务的开源测试生成器，它生成了高分支覆盖率的测试套件。图 2 说明了 SUSHI 的模块化体系结构：路径发现器利用程序路径的符号执行去发现程序执行控件并且计算程序路径的执行条件。 路径选择器将如何选择路径子集以最大化分支覆盖范围的任务转换为线性编程问题，可通过专用库解决。 路径评估器实现了我们最近提出的方法，该方法将路径条件转换为可执行的评估条件，从而量化了某一具体状态到满足相应路径条件的状态之间的距离。方法序列生成器使用基于搜索的引擎生成选定路径条件的具体测试用例，该引擎将评估器用作适应度函数。
图 2 SUSHI 体系结构
2.1 路径发现器
SUSHI 利用符号执行器 JBSE 既以深度优先的顺序遍历程序路径（直至某些用户定义的边界），并计算相应的路径条件。 JBS 负责处理符号执行，并包括一组技术来解释结构化输入的结构不变性。
SUSHI 利用 JBSE 收集路径条件和覆盖率信息，即在符号执行过程中遍历的程序分支集。例如，对于图 1 中的程序，JBSE 通过在第 14 行描述执行分支的输入集的路径条件计算了一条遍历第 14 行的分支的路径。
2.2 路径选择器
路径选择器通过将路径选择任务公式化并解决为线性编程问题，从而识别出足够的路径子集来覆盖程序分支。该路径选择器：
（1）将覆盖率信息转换为系数 cij 的矩阵，使得每一行 i 对应于一条探索路径，每列 j 对应于一条探索分支（如果第 i 条路径覆盖第 j 条分支，则系数 cij 为 1，否则为 0 ）
（2）将每个探索的路径与变量 si 关联，求解器将该变量 si 设置为 0 或 1，以指示给定路径是否属于选择路径，并且
（3）使用 GLPK 求解器找到变量的最佳分配，该分配可最大程度地减少选定路径的数量，该选定数量 paths=∑si,同时保证所有分支的覆盖率满足要求,该要求表示为一组线性约束 ∑cij*si >0，对于每个分支 j。产生的分配指示最大化分支覆盖范围的路径子集
SUSHI 目前可以最大程度地扩大分支覆盖范围，可以通过修改 Path Explorer 组件轻松地适应其他结构化测试标准，从而在探索的路径与目标代码元素之间生成合适的映射。
2.3 路径评估生成器
路径评估器生成器将选定的路径条件转换为距离评估器程序，该程序计算满足路径条件中所有子句的测试用例 t 的距离。简而言之，评估程序检查与测试用例 t 相对应的执行状态，以验证其是否符合路径条件中的执行条件。
评估程序是 SUSHI 调用的可执行的方法，SUSHI 使用测试用例 t 当前传递给被测程序的输入来调用它。 如果输入满足相应路径条件中的所有子句，则评估器将返回最小距离 0，否则返回大于 0 的距离。 每个不满足的路径条件子句都会使返回的距离增加（0，1]，对于严重不符合该子句的输入，其值越来越接近 1。
例如，对于第 2.1 节中的路径条件，一个测试用例在进程主列表中有 9 个进程，在次要列表中有 1 个低优先级进程，因为它满足路径条件中的所有子句，所以它的最佳距离为 0。 相反，在主列表中有 8 个进程的测试用例的距离 α> 0，因为它不满足条件 primary.size> 8; 一个在主列表中具有七个进程的测试用例的求值距离为 β>α，因为它错过的相同子句的数量更大，依此类推。 我们向读者推荐“Combining symbolic execution and search-based testing for programs with complex heap inputs”一文，以获取评估器的详细数学定义。
路径评估生成器是 SUSHI 的核心技术特性。 与传统的符号执行程序不同，SUSHI 仅生成与方法调用的合法序列相对应的测试用例：SUSHI 将路径条件转换为元启发式搜索过程的适应度函数，该搜索过程将搜索引导至满足路径条件的可达程序状态的方法序列。
2.4 方法序列生成器
方法序列生成器将路径条件距离评估器集成到元启发式搜索过程中，以生成满足相应路径条件的实例化程序状态的方法调用序列。
方法序列生成器利用 EvoSuite 工具作为基于遗传算法的元启发式搜索引擎。 图 3 说明了搜索算法及其与路径条件距离评估器的集成。搜索算法从随机填充的方法序列的集合可是，然后逐步进行新的迭代。方法序列生成器通过采用进化算子生成的新方法序列（称为后代）扩展当前代，从而构建了新一代序列。标准的进化算子包括突变（随机改变，添加或删除语句）和交叉（交叉），交叉结合了两个方法序列。
图 3 通过路径条件匹配的搜索算法
对于每个新生成的后代，该算法都会计算一个适应度值，该适应度值表示从当前状态开始到能够生成一种方法序列的距离，该方法序列在满足路径条件中所有子句的状态下调用目标方法，从而执行相应的程序路径。搜索算法通过执行方法序列来计算适合度值。如果方法序列未调用目标方法，则测试执行程序将返回最大距离值，因为方法序列无法通过构造的方法覆盖目标路径。否则，在拦截对目标方法的调用后，测试执行程序将使用与目标方法调用相同的参数来执行路径条件距离评估器，并根据评估器返回的距离值来设置适合度值。在多次调用目标方法的情况下，结果适合度值是所有调用中的最佳值。
该算法在确定具有最佳适应度的方法序列后返回测试用例。例如，当使用表示第 2.1 节中讨论的路径条件的评估器时，方法序列生成器将产生图 4 中的测试用例，该用例成功覆盖了图 1 中第 14 行的分支。EvoSuite 的执行受到时间预算的限制，并且当搜索时间超出预计时间时，方法序列生成器可能不会针对路径条件返回测试用例。
图 4 针对图 1 中的程序的一个 SUSHI 测试用例
2.5 处理不可行的路径
仅当所选路径条件对应于可行路径（即有效程序行为）时，方法序列生成器才会生成具体的测试用例。 但是，由于无法确定某些公式的可满足性，因此路径发现器可能会保守地计算一些无法满足的路径条件。但是，路径发现器可能会忽略某些隐式程序不变式，并产生违反这些约束的路径条件。
SUSHI 通过两种补充机制来减轻不可行路径的影响：
（1）它依靠 JBSE 的支持来利用开发人员提供的前提条件和不变式的规范；
（2）它实现了一个反馈循环，以监视方法调用序列的路径条件的具体化。 如果“方法序列生成器”未能具体化路径条件，则 SUSHI 会在路径选择器（图 2）中重新遍历，以考虑有助于实现最佳覆盖范围的替代路径条件。
反馈回路得益于方法序列生成器的并行部署，可提高生成过程的效率：SUSHI 实例化 EvoSuite 过程池，以通过其相应的距离评估器在选定的路径条件下同时工作。 每当 EvoSuite 流程成功生成路径条件的测试用例时，它都会将所覆盖的分支通知路径选择器。在每次迭代中，路径选择器都会优化一个简化的问题，该问题不考虑覆盖的分支以及先前选择的路径条件。
3.使用 SUSHI
SUSHI 既可以从命令行独立访问，也可以作为某些开发环境（即 EclipseIDE）的插件进行访问。 开发人员可以通过将所需选项指定为扩展接口 Sushi.configure.ParametersModifier 的 Java 类来执行 SUSHI，然后使用此类选项启动 SUSHI。 SUSHI 相关选项指定被测方法（或类）的签名，程序的二进制文件和相关性以及 SUSHI 存储生成的测试用例的输出目录。开发人员还可以指定选项以自定义要并行生成的 EvoSuite 进程池的大小，在路径选择阶段要考虑的一组特定目标分支以及从基础工具 JBSE 和 EvoSuite 接受的任何自定义选项，包括符号执行期间使用的不变量以及两种工具的时间预算。SUSHI 生成可执行的 JUnit 测试用例。
SUSHI 在中间输出上具有很高的可见性，从而可以监视测试生成过程的所有阶段并检查中间结果。中间输出包括（i）符号执行跟踪，每个都用 trace-id 标识，该跟踪 ID 允许用户使用 JBSE 重播该特定路径的符号执行，（ii）路径的覆盖率信息，（iii）路径选择器选择的路径条件；（iv）路径评估生成器构建的路径条件距离评估器的 Java 代码；以及（v）运行每个 EvoSuite 实例时生成的日志文件。这些中间输出对于调试 SUSHI 和检查结果都是有价值的信息。中间输出通过提供有关观察到的行为的信息来支持调试，并通过例如支持对选定但未具体化的符号执行跟踪的检查来发现缺失的数据结构不变式，从而提高最终结果的实用性，并通过完善用于符号执行的不变式和前提条件来提高测试生成过程的有效性。
4.评估
我们通过为一组基准程序生成测试用例来评估 SUSHI，这些基准程序使用非平凡的数据结构作为输入。我们将 SUSHI 生成的测试用例的分支覆盖范围与 JBSE，Seeker 和 EvoSuite 生成的测试用例的覆盖范围进行了比较。 JBSE 通过直接操作堆内存来生成测试用例。Seeker 利用静态分析来构建方法序列，从而将符号执行器 Pex 引向未覆盖的分支。 EvoSuite 利用到未覆盖分支的距离作为适应度函数来实现基于搜索的测试。我们对配置有少量（部分）不变变量和全面（准确）不变变量的符号执行器进行了实验。
表 1 报告了所生成测试套件的分支覆盖范围。我们将实验设置，相应的复制程序包和结果的细粒度分析的所有详细信息推荐给读者。结果表明，SUSHI 在所有实验中均不断改善了符号执行的整体其他实施方式（JBSE 和 Seeker），并且针对 EvoSuite 形成了相关的互补分支，并具有部分和准确的不变性。此外，SUSHI 是生成测试套件的唯一工具，该套件可以揭示程序中的错误。结果还表明，不变量的准确性对 SUSHI 的有效性产生了显着影响：与精确不变量相比，与部分不变量一起使用时，SUSHI 始终达到相等或更高的覆盖率。我们计划致力于不变量的自动生成，并进一步利用与 EvoSuite 的互补性来增强测试生成器的有效性。
表 1 使用 SUSHI 和其他同类工具的分支覆盖率
5.结论
我们介绍了 SUSHI，这是一种新颖的 Java 开源测试生成器，专为具有复杂结构化输入的程序量身定制。Java 程序基准测试的初步结果表明，SUSHI 有潜力改进自动测试生成器的技术水平。
致谢
本文由南京大学软件学院 2020 级硕士生曹振飞翻译转述。
感谢国家重点研发计划（2018YFB1003900）和国家自然科学基金（61832009，61932012）支持！
閱讀更多 慕測科技 的文章
