Reading Note: “CODAMOSA: Escaping Coverage Plateaus in Test Generation with Pre-trained Large Language Models”, ICSE 2023
date
Mar 24, 2024
slug
codamosa
status
Published
tags
SE-Paper Reading
summary
type
Post
问题描述
单元测试生成的目标：给定待测软件，生成高覆盖率和可理解性高的测试用例。
应用遗传算法来做单元测试生成时取得效果依赖的一个因素是：当我们对当前的测试用例做变异的时候，需要有不可忽略的概率使得它的适应度提升。但是这件事情并不总是成立，距离来说，如果我们有一个函数，它接受一个字符串类型的参数，代表一个版本号字符串，功能是提升版本号。这个参数对人类来说有特定的语义，它有特定的合法格式，如果我们从所有字符串的空间中随机抽样得到一个字符串，它几乎不可能符合这个格式。这时候，我们对这个随机产生的初始字符串进行变异，也几乎不可能产生合法格式的字符串，因此也就无法提升适应度，这时候我们称作陷入了覆盖率瓶颈（Coverage Plateaus）。
一个导致陷入覆盖率瓶颈的重要因素是，基于遗传算法（更广泛地讲，基于搜索算法）的方法中，我们不知道如何以一种合适的方式去调用一个程序，因为这往往和它的语义有关。在本文中，作者提出了一个假设，认为如果能够给基于搜索的算法提供一些以合适的方式调用待测程序的测试用例，搜索就可以逃离覆盖率瓶颈，而如何产生这样的测试用例就是本文要解决的问题。
研究现状
目前有两类主流的方法，一类是基于程序分析的方法，比如基于遗传算法，基于符号执行等，这类方法通常能够产生覆盖率较高的测试；另一类是基于深度学习和大语言模型的方法，这类方法通常能够产生更适合人类理解的测试用例；近年来也开始出现一些两者结合的方法。
本文方法
概述
本文提出的方法 CODAMOSA，其主框架仍然是基于搜索的测试生成方法 MOSA，在其基础上，如果 MOSA 的迭代陷入了覆盖率瓶颈（覆盖率连续 N 次没有提升），则向 Codex 发出询问，请求它生成针对当前一个覆盖率比较低的函数的测试用例，并加入当前的测试用例种群，继续进行迭代。
相关细节
在这个方法框架中有几个比较重要的细节：
- 何时向 Codex 发出询问
- 如何向 Codex 发出询问（提示工程）
- SBST 工具只支持目标语言的子集，但是 Codex 生成的测试用例源代码可能包含目标语言的任意语法结构，如何处理
以上三个问题在本文中的处理如下：
- 当覆盖率 N 轮没提升就向 Codex 询问，N 是一个参数。
- 在本文中提示工程比较简单，只用了待测单元实现 + 指令 + 测试函数头
- 增加对 import 新 syntax construct 的支持
实验
一些细节：
- 27 个 python 项目中的 486 个模块。
- 每个方法跑 16 次，每次 600 s
- 比较基线：MOSA，Codex-only
仍然面对的挑战
- 提示工程：提示仍然可以优化，作者尝试了 ICL，但是没有明显提升。
- 如何增强发现错误的能力，比如自动生成符合语义的断言。
- 如何使生成的测试用例更具有可读性和可理解性。
总结
本文的思路比较简单，但是取得了较好的效果（覆盖率超过 SBST-only + LLM-only 之和），主要是利用了 LLM 和 SBST 各自的长处，来解决传统的 SBST 和 LLM-based 的方法中的不足。