Reading Note: “Whole Test Suite Generation”, TSE 2012

date
Mar 21, 2024
slug
evosuite-tse
status
Published
tags
SE-Paper Reading
summary
type
Post

问题描述

软件测试已经是软件开发中一个不可或缺的部分，一个测试包括了待测软件单元的输入，以及检查它的输出是否符合预期。现在已经有很多关于如何生成测试输入的研究，这些方法能够产生一些高覆盖率的测试用例，但是关于测试预言，我们能做的仍然较少。因此，一个切合实际的目标是自动化输入生成，由人工加上测试预言，这对生成的测试用例提出了两个要求：高覆盖率和尽量短的长度。
Satisfy the chosen coverage criterion (e.g., branch coverage) with the smallest possible test suite.

研究现状

目前常见的方法是一次针对一个分支，尝试生成一个覆盖这个分支的测试用例，最后将这些测试用例组合起来成为一个测试用例套件（test suite）。这个方法存在一些问题，它把所有的分支覆盖目标都当作独立，同等难度，且可行的。但是事实上不同的分支覆盖目标并不是独立的，难度也不近相同，甚至有些分支覆盖目标是不可行的，而判断一个分支是否可行在理论上是一个不可判定问题。在这个方法中，生成的测试用例套件的质量依赖选择目标的顺序，以及不可行分支覆盖目标的数量。比如，如果把测试资源消耗在了不可行的目标，或者比较困难的目标，就会浪费许多资源，但是没有得到覆盖率的提升。

本文方法

概述

本文提出了一个 whole suite 的基于遗传算法的测试生成方法，将多个覆盖目标的适应度同时考虑，克服了传统方法的一些困难。
本文使用的遗传算法在 Algorithm 1 中介绍了，本文使用遗传算法来进行测试用例套件解的搜索，简单来说：
初始时产生一个随机的测试用例套件种群（也就是一个测试用例套件的有限集合）
当覆盖率标准没有被满足，或者测试资源仍未耗尽时，重复进行进化操作。
进化操作对现有的种群进行一系列模仿生物的遗传进化过程的操作：
  1. 选出当前种群的一些最佳个体（elitism），保存在临时存储集合 Z
  1. 当 Z 的大小和当前种群大小不相等，重复以下操作：
      • 通过 rank selection 选择出两个亲代
      • 根据一定的概率，对亲代进行 cross over 操作或者恒等映射产生子代
      • 对子代进行变异操作
      • 计算子代和亲代的适应度和长度
      • 如果子代的适应度更好，或者适应度一样好，但是长度更小，把子代加入 Z，否则把亲代加入 Z
      • 把 Z 作为下一个迭代的当前种群
上述的描述给出了一个框架，有几个地方是这里还未阐明的，在之后的小节中展开：
  1. 如何表示解（solution encoding）
  1. 如何生成 initial population
  1. 如何定义算子：elitism，rank selection, cross over, mutate
  1. 如何定义 fitness function

Solution Encoding

搜索空间中的每个 solution 是一个 test suite，一个 test suite T 是一个 test case 的序列，T = <t1, t2, ..., tn> 是一个大小为 n 的测试用例套件（注意大小和长度并不是一个概念）；每个测试用例 t 是一个程序语句的集合， t = <s1, ..., sL> 是一个大小（以及长度）为 L 的测试用例，测试用例套件的长度由其包含的测试用例的长度之和定义。由于我们希望让产生的测试用例套件可以让人工添加断言，我们希望能够限制测试用例套件最大大小为 n，测试用例大小最大为 L，这样的限制定义了一个尽管十分巨大，但是有限的搜索空间：所有大小为 1 到 n，包含的测试用例长度为 1 到 L 的测试用例套件；在解表示中，每个语句 s 是五种语句中的一种，它有一个值 ，这个值的类型是 ，五种语句如下：
  1. primitive statement
  1. constructor statement
  1. field statement
  1. method statement
  1. assignment statement
相比于源语言的语法（树结构），测试用例程序的语法做了一定的简化（线性结构），这是因为我们根据测试用例程序的一般结构取了我们所需要的语法子集，这种简化的表示可以帮我们更好地开展搜索。

Fitness Function

Fitness Function 用于进化过程中亲代和保留个体的选择，我们希望它作为一个测试用例套件对所有的分支的覆盖程度的度量：
分支距离 是度量测试用例套件离执行某个分支的距离，比如对于谓词 x > 10，分支距离可以定义为 10 - x + k，其中 k 是一个正数。而这里的 d 和传统的分支距离略微不同，具体的定义见文中。
关于为什么要执行两次的谓词才开始使用第二个公式的解释，我的理解是：如果在测试用例套件中只被执行一次的谓词就开始使用第二个公式来计算，搜索就会通过梯度使得谓词包含的变量值向着这个分支被覆盖前进，而其相反分支在其被覆盖之前是没有梯度的；但是如果进化到这个分支被覆盖，原来的它的相反分支又没被覆盖了（因为这个谓词在测试用例套件中只有一处被执行），如果在这个谓词执行两次以上才用第二个公式计算就可以避免这点，因为如果只被执行一次直接分支距离为 1，无法计算梯度，这时候可能就要等测试用例套件进化到执行两次该谓词之后才开始改变相关变量的值。

Bloat Control

在 Genetic Programming 中会出现一种称作 bloat 的现象，出现于微笑的 fitness 提升可以通过更长的解来获得的情况，这导致我们最后获得大小很大的解。本文中应用了一些方法来进行 bloat control。（看起来感觉是暂时不太重要的细节，先略过了）

Search Operator

对于具体的搜索问题，我们需要定义搜索算子，以改变我们定义的形态下的解：
  1. cross over：采用单点交叉的方式，由于测试用例是互相独立的，因此 cross over 产生的子代总是有效的。
  1. mutate：当一个 test suite 被应用一个 mutate 操作的时候，它的每个测试用例有 的概率被应用 mutate 操作（也就是平均来说只有一个 test case 被 mutate），之后会进行一系列添加操作添加若干随机测试用例。对于每个测试用例，有 1 / 3 的概率进行删除，插入，改变（也就是平均来说只应用一个动作）。应用动作之后可能产生不合法的 test case，处理的方法简单来说就是尝试产生新的语句来修复，如果不行就删掉导致不合法的语句。
  1. random test case sampling：通过一个平均分布来获取随机测试用例是不现实的，因为搜索空间中绝大多数的测试用例大小都非常大，在本文中直接采用 r 次插入操作来产生一个长度为 r 的test case；test suite 也是类似道理。

EVOSUITE 工具实现

一些细节：
  1. EVOSUITE 工作在 Java 字节码层级，通过 Java 的反射机制来构建 Test Cluster。
  1. 考虑字节码级别的分支覆盖率。
  1. 通过字节码插桩来手机和计算适应度函数有关的信息，同时也会进行一些程序变换，比如遇到字符串的时候可能改用编辑距离，遇到浮点数时同理等等。

实验

一些细节：
  1. 主要考虑和传统方法进行比较，验证是否有提升
  1. 待测单元需要包含多种软件
  1. 采用经验参数设置
  1. 重复实验

总结

本文提出了一个同时考虑所有覆盖率目标的方法，将所有覆盖率目标的单个适应度聚合成一个标量值，以克服传统方法的一些不足。

© Lifan Sun 2023 - 2024