CodaMosa: Escaping Coverage Plateaus in Test Generation with Pre-trained Large Language Models

Caroline Lemieux1, Jeevana Priya2, Shuvendu K. Lahiri2, Siddhartha Sen2

1University of British Columbia, Canada

2Microsoft Research, USA

引用

Lemieux, C., Inala, J. P., Lahiri, S. K., & Sen, S. (2023, May). CodaMosa: Escaping Coverage Plateaus in Test Generation with Pre-trained Large Language Models. 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE). 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE).

论文：https://doi.org/10.1109/icse48619.2023.00085

仓库：https://github.com/microsoft/codamosa

摘要

本文探讨了代码的大型语言模型（LLM）（例如 OpenAI 的 Codex）是否可以用来帮助 SBST 的探索。我们提出的算法 CODAMOSA 会进行 SBST，直到其覆盖率改进停止，然后要求 Codex 提供未覆盖功能的示例测试用例。这些示例帮助 SBST 将其搜索重定向到搜索空间中更有用的领域。在对 486 个基准的评估中，与仅 SBST 和 LLM 基准相比，CODAMOSA 在更多基准上实现了统计上显着更高的覆盖率，并没有显著降低覆盖率。

1 引言

自动测试用例生成的目标是生成涵盖被测程序所有不同行为的测试用例。涵盖开发人员没有考虑到的行为的测试用例可能会帮助开发人员发现错误或以其他方式提高其程序的质量。

自动生成测试用例的一种方法是基于搜索的软件测试（SBST）。大多数最先进的 SBST 工具都建立在某种形式的进化算法之上。在高层次上，这些算法首先创建一组随机测试用例，反复变异这些测试用例，并保留那些具有较高适应度的测试用例以进行进一步变异。通常，较高的适应性与测试程序的较高覆盖率相关。

当改变测试用例具有不可忽视的增加适应度的可能性时，SBST 效果很好。图 1 中的 Python 模块的情况并非如此。被测试的主函数，bump version，增加程序版本字符串，例如将“1.2.2”更改为“1.2.3”。如图 1 所示，SBST 工具可以生成测试用例，其中对“a\!sUo~AU”等随机字符串调用bump_version。从这里开始，SBST 很难取得进一步的测试进展，因为将“a\!sUo~AU”突变为执行更多测试代码所需的合理版本字符串的概率几乎为零。不幸的是，研究发现像这样的适应度瓶颈（突变的测试用例不太可能增加覆盖率）非常常见 。

导致这些停滞状态的一个核心问题是 SBST 难以以预期方式执行被测程序 (PUT) 。例如，在我们运行的示例中，bump_version期望其第一个参数是特定格式的字符串。或者，程序可能期望特定的函数调用序列来正确构造对象。我们假设，如果我们向 SBST 提供以预期方式执行 PUT 的测试用例，那么 SBST 的搜索就可以摆脱这些停滞状态。困难在于如何生成这些预期的测试用例。

图1

最近，应用于 Codex等代码的大型语言模型 (LLM) 在生成看起来自然的代码方面显示出了令人印象深刻的结果。在本文中，我们研究是否可以有选择地调用 LLM 来生成可以帮助 SBST 摆脱覆盖停滞的测试用例。

我们提出的技术 CODAMOSA 启动 SBST 并监控其覆盖进度。当 CODAMOSA 注意到覆盖率停滞时，它会识别 PUT 中覆盖率较低的可调用对象。然后，它查询 Codex 来生成这些可调用项的测试。为了在这些世代的基础上构建，CODAMOSA 将 Codex 生成的原始字符序列反序列化为 SBST 的内部测试用例表示。这使得它能够利用 SBST 的变异操作和适应度函数来变异和评估 Codex 生成的测试的质量。

在构建此工作流程时，何时以及如何向 Codex 请求测试用例存在一些微妙之处。反序列化测试用例提出了一个核心技术挑战：为了使搜索易于处理，SBST 限制了测试用例中可以出现的语句集。另一方面，Codex 生成任意 Python 代码。我们的反序列化过程可以轻松扩展 SBST 的搜索空间：对 Codex 建议的新函数或新语法结构的调用如果有助于增加覆盖范围，就会集成到测试用例中。

我们在 Pynguin 测试套件生成框架之上构建了适用于 Python 的 CODAMOSA。 我们对 486 个 Python 模块进行了 CODAMOSA 大规模评估。 我们发现，与我们的 SBST 和 LLM 基准相比，CODAMOSA 在更多基准（173 和 279）上实现了统计学上显着更高的覆盖率，而不是降低了覆盖率（10 和 4）。 覆盖率增加的平均幅度（10%和9%）也高于平均下降幅度（-4%和-3%）。 在案例研究中，我们发现 Codex 生成特殊字符串原语、调用新函数和引入语法结构的能力对 CODAMOSA 相对 SBST 的改进贡献最大。

总之，我们的贡献如下：

2 技术介绍

考虑图 1 顶部的代码片段。它基于 flutils 项目的包模块。该模块提供的核心功能是bump version，它增加版本字符串中的版本，例如从“1.2.2”到“1.2.3”。 pos 参数指定增加版本的位置，预发布参数创建 alpha 或 beta 版本：bump version(‘1.2.2’, 1, ‘a’) 产生‘1.3a0’。我们的代码片段主要突出显示一个辅助函数，构建版本凹凸位置，它处理 pos 参数中传递的整数值。

假设我们想自动为该模块创建一个测试套件。大多数最先进的测试套件生成工具都是基于搜索的。这些工具使用元启发式优化算法为被测模块生成高覆盖率测试套件。 MOSA和 MIO等最先进的算法是其核心进化算法。他们通过以下方式生成测试用例：(a) 从一组随机生成的测试用例开始，(b) 反复改变这些测试用例，并仅保留最适合的测试用例，如某些（通常与代码覆盖率相关）健身指标所定义的。

假设我们在图1中的被测模块上运行SBST算法MOSA。最初，MOSA将实现对该模块的一些覆盖。但很快，它的覆盖率改进就停止了：即使在重复的突变迭代之后，它生成的突变测试用例也没有覆盖模块中的新代码。我们说算法已经达到了覆盖率停滞。

这种停滞的原因任何人都清楚分析师查看 MOSA 生成的测试用例。图 1 显示了两个这样的测试用例，标记为 (1)。这些测试用例将意外的值传递给bump_version的版本参数：‘a\t!sUo~AU’和 None。这些值会导致在调用bump_version时立即引发异常，因此在包模块中执行的代码很少。

我们提出的技术 CODAMOSA 克服了此类失速，如下所示。 CODAMOSA 通过运行 MOSA 开始。然后，当它到达覆盖停止时，它会请求“提示”。准确地说，它要求针对被测模块中未涵盖的功能的测试用例。例如，它可能会得到图 1 中标记为 (2) 的测试用例。尽管该测试用例的第一个断言的右侧不正确，但它会在有效版本字符串上调用bump_version。 CODAMOSA 将测试用例的核心功能提取为可变测试用例格式：图 1 中的 (3)。它观察到该测试用例增加了被测模块的覆盖范围，并将其添加到其测试用例集中。

然而，这个测试用例由bump_version的正常调用组成，它没有运用 pos 参数的微妙之处。测试用例既不执行处理越界位置的代码，也不执行处理负位置的代码。

幸运的是，探索参数的不同整数值是基于突变的算法（如 MOSA）的优势之一，CODAMOSA 就是基于该算法构建的。因此，CODAMOSA 将从反序列化的测试用例中生成许多突变体，在图 1 中标记为 (4)。有些突变体，如测试用例突变体 0，可能具有 pos 的有效负值，并执行标记为蓝*的代码。其他的，例如测试用例突变体 n，可能具有 pos 的越界值，执行标记为红*的代码。

该示例的主要要点如下。为搜索提供被测模块的预期用途示例可以让 SBST 避免其覆盖范围停滞。

当然，问题是如何获得模块代码的预期用途示例。为了做到这一点，我们需要一个能够理解代码“应该是什么样子”的系统。方便的是，大型代码语言模型（例如 Codex）承诺做到这一点。因此，CODAMOSA 使用 Codex 生成如图 1 中的 (2) 所示的测试用例提示。

图 1 中的示例取自我们评估中的一个真实示例，在该示例中 CODAMOSA 大大优于我们的基线。经过 16 次运行，MOSA 实现了该模块 18.4% 的平均总覆盖率。相比之下，CODAMOSA 的平均总覆盖率达到 91.8%，绝对比 MOSA 提高了 73.4%。 CODAMOSA 的性能还优于 Codex-only 基线，后者在此模块上仅实现 64.5% 的平均总覆盖率。

3 实验评估

3.1 实验设置

研究问题。我们的评估调查了以下问题。

RQ1：CODAMOSA 与我们的基准集上的基线相比如何？

RQ2：我们的设计决策（未解释的语句、Codex 超参数、低覆盖率目标、提示）如何 影响测试有效性？

RQ3：为什么从质量上来说，CODAMOSA 取得的覆盖结果与 MOSA 不同？

RQ4：Codex 生成是从被测试模块的代码库中的非提示文件复制的吗？

评估数据集。本研究根据 Pynguin和 BugsInPy的评估，确定了 35 个项目来从中获取模块。我们使用 pipreqs自动识别每个项目的依赖项，并使用 Python 内置的 setuptools.find 包实用程序自动识别每个项目中的模块。对于每个模块，我们都进行了初步测试：运行两次 MOSA，每次一分钟。我们删除了未能产生结果的模块以及在一分钟内实现 100% 覆盖的模块。我们还对共享同一父模块的模块数量进行了下采样。这为我们留下了 27 个项目的 486 个基准模块；表一提供了详细信息。

对比方法。为了进行全面评估，本研究使用了两个基线标准：第一个基线是MOSA，即Pynguin 对 MOSA 的实现，其同时支持路线和分支覆盖；另一个是CODEXONLY，仅使用 Codex 生成测试用例。 CODEXONLY 将其全部搜索预算用于为随机选择的测试对象调用 TARGETEDGEN，并在 Codex 生成的测试上调用 PARSETOTESTCASE 以获取 Pynguin 格式的测试用例。

RQ1 CODAMOSA与基线结果比较

我们在 486 个基准测试中运行了 MOSA、CODEXONLY 和 CODAMOSA。遵循 Arcuri 和 Briand 的指南，我们使用 Mann-Whitney U 检验来比较技术之间覆盖率差异的显着性（p = 0.05）。图 2 显示了 CODAMOSA 和基线之间随时间变化的平均覆盖率差异。每条线代表单独的基准模块。差异是线路分支覆盖率的绝对百分点差异。例如，如果 CODAMOSA 的覆盖范围为 80%，基线的覆盖范围为 20%，则 y 轴上的覆盖范围为 60%。我们强调当时 CODAMOSA 的覆盖率显着高于或低于基线时的平均差异。图 2a 显示了与 MOSA 相比随时间变化的覆盖率平均差异。由于 CODAMOSA 会等到覆盖范围停止才开始调用 Codex，因此我们没有看到覆盖范围立即增加。与图 2b 进行对比，其中 CODAMOSA 的覆盖范围比 CODEXONLY 更高。这反映了这样一个事实：使用随机测试生成来生成测试用例最初比通过查询 Codex 更快。

图2

我们看到，与 MOSA 相比，随着时间的推移，增加的幅度会更大（Codex 测试用例的重复注入会提高覆盖率），而 CODEXONLY 的增加会随着时间的推移而减少（变异测试用例会比 Codex 测试用例提供固定的提升）。图 3a 和 3b 总结了 CODAMOSA（y 轴）和基线（x 轴）实现的搜索结束时平均覆盖率。这些图中沿 x = y 线的圆圈突出显示，在许多基准上，CODAMOSA 的平均覆盖范围与基线没有差异。观察 x = y 线上方的十字，我们看到 CODAMOSA 比 CODEXONLY（图 3b）相比 MOSA（图 3a）实现了更高的覆盖率增加幅度。这与图 2b 中的展平一致。这些结果中出现的一个问题是，图 1 中展示的 SBST 和 Codex 之间的协同作用是否存在于该示例之外，或者 CODAMOSA 是否返回 MOSA 和 CODEXONLY 测试套件的联合。为了评估这一点，我们通过第三方覆盖率工具coverage.py重新运行生成的测试套件。我们通过将第 i 个 MOSA 运行生成的测试用例与第 i 个 CODEXONLY 运行生成的测试用例结合起来创建了 Uniontest 套件。这是对 CODAMOSA 的悲观比较，因为它为 Union 提供了分配给 CODAMOSA 的搜索时间的 2 倍。

图3

我们能够通过覆盖率.py 成功重放 429 个基准测试的 CODAMOSA 和 Union 测试用例。在这些基准测试中，CODAMOSA 的覆盖率效果明显更好与Union在 72 个基准上的覆盖范围相比，在 314 个基准上没有显着差异，在 43 个基准上显着更差。事实上，CODAMOSA 在 17% 的基准测试中表现明显优于 Union，并且在 73% 的基准测试中表现与 Union 相当（尽管搜索时间只有 Union 的一半），这表明在我们的激励示例中看到的 SBST 和 LLM 的有意义的组合是不是一次性的。此外，这些覆盖范围的增加似乎并没有以测试套件膨胀为代价。平均而言，所有基准测试中，CODAMOSA 创建的测试套件包含 11 项测试，而 MOSA 则包含 10 项测试。测试套件大小的差异似乎与覆盖范围的差异相关。在 CODAMOSA 的覆盖率显着高于 MOSA 的基准上，其平均测试套件大小为 18，而 MOSA 为 15。同时，在 MOSA 覆盖率显着更高的基准上，MOSA 的平均测试套件大小为 18，而 CODAMOSA 为 17。测试套件较小，平均包含 7 个测试。但是，正如前面所讨论的，它们的覆盖率始终较低。

RQ2 设计决策

在构建 CODAMOSA 时，我们做出了多项设计决策。我们详细评估了其中每一个的效果。

1）未解释的语句：CODAMOSA 的未解释的语句允许它生成具有任意右侧表达式的赋值语句。我们将 CODAMOSA 的性能与禁用未解释语句的 CODAMOSA 版本 (CODAMOSA-NOUNINTERP) 进行比较。图 3c 显示了 y 轴上 CODAMOSA 的每个基准实现的平均覆盖率，与 x 轴上的 CODAMOSA-NOUNINTERP 相比。总体而言，使用未解释的语句导致 57 个基准的覆盖率显着增加，而 57 个基准的覆盖率显着下降8 个基准。未解释的语句可以执行只能由复杂结构（例如迭代）执行的函数行为。然而，未解释的语句也可能导致测试用例中包含无用的语句。这使得遗传算法更难通过变异取得进展，从而减少其实现的覆盖范围。

2）温度：Codex 与其他LLM一样，通过学习给定前缀的下一个标记的概率分布来学习生成代码。有多种策略可以根据这些概率分布生成代码。我们使用温度来控制采样的贪婪程度。当温度为 0 时，Codex 始终返回最有可能的下一个标记，而当温度为 1 时，它返回根据学习的概率分布采样的下一个标记。

默认情况下，我们使用温度 0.8 来对 Codex 进行采样。图 3d 显示了使用此默认值（在 y 轴上）实现的覆盖范围与温度为 0.2 的 CODAMOSA（在 x 轴上）实现的覆盖范围之间的比较。 CODAMOSA 在 113 个基准上的覆盖率明显高于 CODAMOSA-TEMP-0.2，但在 9 个基准上的覆盖率明显较低。

较低的温度意味着 Codex 更有可能在给定特定提示的情况下对最预期的测试用例进行采样。但是，这也会导致多样性减少。因此，如果 Codex 最预期的测试用例对 CODAMOSA 没有用，则返回类似预期测试用例的重复查询将不会增加覆盖率。较高的温度可能需要更多的查询才能获得最预期的测试用例，但在最预期的测试用例无用的情况下会更加稳健。

3) 低覆盖率目标：回想一下，CODAMOSA 提示 Codex 为低覆盖率测试对象生成测试。我们通过与 CODAMOSA-RANDOM 进行比较来评估此采样的实用性，CODAMOSA-RANDOM 会提示 Codex 使用随机选择的测试对象。图 3e 在 y 轴上显示 CODAMOSA 的平均覆盖率，在 x 轴上显示 CODAMOSA-RANDOM 的平均覆盖率。在 50 个基准上，CODAMOSA 的覆盖率明显高于 CODAMOSA-RANDOM，但 CODAMOSA-RANDOM 在 14 个基准上的覆盖率显着更高。此外，与使用未解释的语句或高温相比，针对低覆盖率可调用项不会产生大幅的覆盖率增加：在图 3e 中，除了 x = y 线上方的三个点之外，所有点都位于该线的正上方。我们预计 CODAMOSA-当低覆盖率提示降级为随机提示时，RANDOM 的行为类似于 CODAMOSA。例如，当测试对象很少时，或者当所有测试对象均等覆盖时。此外，如果无法增加低覆盖率函数的覆盖率，CODAMOSA-RANDOM 的性能可能会比 CODAMOSA 更好。

4) 提示：CODAMOSA 发送到 Codex 的提示仅包含被测试的源代码和测试函数头。我们在初步实验中观察到，有时 Codex 会重复输出与 Pynguin 测试用例格式相差太远的代码，以致于 CODAMOSA 无法使用。例如，Codex 有时会生成主要是 Python 测试框架样板的测试用例。一个自然的问题是，向 Codex 提供一个格式良好的测试用例示例是否可以改善这些结果。在 CODAMOSA-TESTCASEPROMPT 中，我们在 Codex 的提示中添加了一个已生成的测试用例的示例。我们选择存档中最小的非空测试用例，因为我们发现 Codex 在进行较长测试时过于模仿 Pynguin 格式。在 49 个基准测试中，CODAMOSA 的覆盖率明显高于 CODAMOSATESTCASEPROMPT。 CODAMOSA 在 24 个基准上的覆盖率明显较低。图 3f 显示这 24 个基准的覆盖范围差异通常较大。这包括一个基准，CODAMOSATESTCASEPROMPT 的性能优于 MOSA，而 CODAMOSA 的性能比 MOSA 差。

RQ3 覆盖结果比较

我们分析了为什么 MOSA 和 CODAMOSA 的结果不同，以及它们差异最大的基准。

1) 覆盖率提高的原因：回想一下，CO-DAMOSA 在 173 个基准上实现了比 MOSA 更高的覆盖率，这些基准太多而无法手动分析。因此，我们分析了 CODAMOSA 相对 MOSA 平均覆盖率增幅最大的 20 个基准（从 24.2% 到 73.4% 绝对百分点）。

2) 覆盖率下降的原因：与 MOSA 相比，CODAMOSA 在 10 个基准上的覆盖率显着下降（从 -0.2% 到 -15.9%）；我们对它们进行了全部分析。覆盖率下降的核心原因是浪费了探索时间。平均而言，所有基准测试中，CODAMOSA 向 Codex 发出 60 个查询，并花费 413 秒等待这些查询。在表现最差的基准测试中，该时间上升至 480 秒。如果我们可以减少 Codex 查询时间，CODAMOSA 可能会表现得更好。例如，如果我们将性能较差的基准的查询时间从 494 秒减少到 49 秒，CODAMOSA 将获得 62.6% 的覆盖率，而 MOSA 则获得 43.5% 的覆盖率（155 秒）。

RQ4 CodeX生成

正如之前所提到的，Codex 是在来自 Github 的大量代码库上进行训练的。由于我们无法访问 Codex 的训练集，因此我们无法确认基准测试模块中的代码是否属于该集的一部分。一个自然的问题是 Codex 是否与我们的基准过度拟合。为了评估这一点，我们将 Codex 为每个模块生成的测试与模块源存储库中存在但不存在于模块定义文件中的测试函数进行比较。这些测试函数不在 CODAMOSA 发送给 Codex 的提示中，因此我们不应期望 Codex 生成它们。

代码抄袭检测的指标删除了函数名称和原始值以关注代码结构，但没有适当地捕捉测试用例相似性的概念。例如，copyDetect会输出 ast.parse(‘‘x’’) 与 collections.Counter(‘‘abb’’) 高度相似。

因此，我们将最大相似度定义如下。对于项目 P 中的模块 m 的 Codex 生成的测试用例 t* 和 TP（在 m 之外的 P 中定义的测试函数集），最大相似度为我们使用 edit distance 来计算距离。

图 4 显示了每个项目 Codex 生成的测试用例的累积百分比，最大相似度小于 x 轴阈值。我们看到大多数生成的测试用例的相似度≤ 0.4。对于某些项目，没有测试用例是非常相似的（apimd、sty、thonny），而对于其他项目（例如上面提到的flutes），则存在具有较高相似性的长尾测试用例。图最右侧的垂直线段表示一些精确复制的测试用例：但其中 99.1% 只是语句通过。

我们的测试项目之一 flutils 托管在 GitLab 而不是 GitHub 上，因此不太可能出现在 Codex 的训练集中。这使我们能够评估 CODAMOSA 如何在“新”代码上工作。在我们评估的 9 个 flutils 模块中，CODAMOSA 在 7 上的覆盖率高于 MOSA（p 值 = 8 × 10−3 至 2 × 10−8），在 1 上的覆盖率较低（p 值 = 4 × 10−3），并且1 个模块没有覆盖率差异（p 值 = 0.51）。虽然样本量很小，但这种 7/1/1 分割比我们在其他基准测试中看到的 166/9/296 分割要好。

图4

转述：尚也