CCTEST：代码补全系统的测试和修复

欢迎大家来到IT世界,在知识的湖畔探索吧!

CCTEST: Testing and Repairing Code Completion Systems

Zongjie Li, Chaozheng Wang, Zhibo Liua, Haoxuan Wang, Shuai Wang, Cuiyun Gao

The Hong Kong University of Science and Technology, Hong Kong SAR

Harbin Institute of Technology, Shenzhen, China

Swiss Federal Institute of Technology Lausanne, Switzerland{zligo,zliudc,shuaiw}@cse.ust.hk, {wangchaozheng}@stu.hit.edu.cn

{gaocuiyun}@hit.edu.cn,

{haoxuan.wang}@epfl.ch

引用

Li Z, Wang C, Liu Z, et al. Cctest: Testing and repairing code completion systems[C]//2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE). IEEE, 2023: 1238-1250.

论文：https://ieeexplore.ieee.org/abstract/document/

摘要

本文提出了CCTEST框架，用于测试和修复代码补全系统，特别是基于大型语言模型（LLM）的系统。这项工作针对的是诸如GitHub Copilot和GPT这类系统，它们通过深度学习从大量非结构化文本和开源代码中学习。CCTEST通过生成变异的代码片段并检测输出中的不一致性来识别潜在的错误，进而选择性地修复这些错误以提高系统的性能。研究发现，即使是流行的代码补全工具也会产生错误，证明了CCTEST在提高这些工具准确性方面的有效性。

1 引言

大型语言模型（LLMs）如GitHub Copilot、OpenAI的Codex和Tabnine正逐渐在软件开发领域中得到广泛应用。这些模型利用机器学习（ML）技术在大量非结构化文本中进行训练，包括网站、书籍和开源代码。这使它们能够根据一些由代码和注释（文档）组成的输入提示生成“补全”。事实上，基于LLM的代码补全框架目前备受推崇，旨在提供一个“AI编程伙伴”，能够根据自然语言规范或代码片段自动生成程序。

尽管代码补全系统是现代软件开发的重要组成部分，但是经常会产生令人困惑甚至错误的结果。我们认为代码补全系统的“次优”行为或错误行为是不可接受的，因为它们可能会降低代码补全的性能和可用性。然而，当前这一问题在研究界尚未受到足够重视，而基于LLM的代码补全框架的初步研究主要集中在其安全影响、成本降低或在不同领域的潜在扩展方面。

我们的研究主要有两个方面。首先，我们设计了一组程序变异策略，即程序结构一致性（PSC）变异，以生成具有相似或相同程序结构的变异代码片段。对于每个（变异的）代码片段的相应代码补全输出集合O，我们通过定义和比较生成的代码补全的程序距离来识别O中的错误情况（即异常值）。与其他变异补全输出相比，生成的代码补全输出的程序距离较长的变异程序将被视为虚假的。我们进一步设计了一个代码修复方案，该方案作为一个后期处理步骤，从多个可能的代码补全结果中，选择那些在整个输出集合中最具代表性的结果来进行修复。我们发现，这种经过挑选的代码补全结果通常与原始的参考输入在结构和质量上高度一致，从而显著提高了代码补全系统的整体准确性。此外，我们的测试和修复策略把代码补全模型当作一个“黑盒”，这意味着我们不需要知道代码补全系统或其底层大型语言模型（LLMs）的具体实现细节。

CCTEST提供了对基于LLM的代码补全系统及其输出正确性的最新评估。在本研究中使用的总共182,464个测试输入中，我们发现了来自八个广泛使用的基于LLM的代码补全系统的33,540个程序暴露出代码补全错误。其中Copilot是一种流行的商业工具，另外七个要么由非营利组织（CodeParrot）积极开发和维护，要么由工业公司（EleutherAI的GPT-Neo和Salesforce的Codegen）托管。通过修复，我们发现代码补全模型的平均性能在两个指标上分别显著提高了40.1%和67%。

总的来说，本研究做出了以下贡献：

• 为了在现实环境中研究基于LLM的代码补全系统，并描述出它们的最新能力，我们介绍并倡导一种新的关注重点，即对它们的输出进行全面和大规模的测试和修复。本研究得到的发现将指导未来旨在使用和改进代码补全工具的研究。
• 我们提出了CCTEST，一个用于代码补全系统的自动化测试和修复框架。CCTEST具有PSC，一种特别设计用于测试代码补全系统的新颖测试方案。我们进一步提出了一个黑匣子修复方案，以提高代码补全输出的准确性。CCTEST融合了一系列设计原则和优化，提供了高效的测试和修复工作流程。
• 从经验上讲，我们评估了一个商业代码补全系统和七个流行的免费代码补全系统，成功发现了33540个导致代码补全错误的程序。我们的修复方案进一步提高了代码补全模型的准确性，准确率大大提高，并得出了关于现代基于LLM的代码补全系统的多种观察和启发性发现。

2 技术介绍

图1 CCTEST的工作流程

图1展示了CCTEST在测试和修复代码补全系统方面的概述。具体来说，

① 提示（prompt）变体生成：CCTEST启动PSC并生成一组结构一致的变体P，这些变体是基于输入提示p0生成的。在这里，我们提出了一种新颖的测试方案—PSC，它通过代码结构不变的变换来生成突变体。变异的提示在人类观察者的视角下呈现出密切相关的结构表示。

② 测试预测器（oracle）生成：代码补全模型根据提示变体输出一组代码补全输出。在这里，我们通过比较补全输出之间的结构级一致性（相似性）来形成一个测试预测器。关键观察结果是，对于具有紧密相似结构的提示变体，代码补全输出应始终表现出高度（视觉上的）一致性。因此，“异常值”代码补全输出被视为错误的，其对应的提示变体是缺陷诱发输入。

③ 不一致补全修复。我们注意到上述测试流水线可以扩展到自动修复不一致的代码补全输出。为此，CCTEST识别出结在外观（即代码结构、格式和可能的逻辑）上最接近于这一系列代码补全输出的平均状态的结果作为修复后的结果。

2.1 程序结构一致性（PSC）变异

我们首先介绍PSC变异方案，它对输入prompt执行结构一致性变异。总体而言，我们的关键观察是具有相似/相同控制结构的程序将在相应的补全代码中保持这种一致性。因此，通过观察到某些代码补全输出表现出不一致的控制结构，可以标记潜在的代码补全错误。

PSC测试的工作流程：

1. 执行结构一致变异，生成一组相似的变异提示，其控制结构相似甚至相同，并收集每个变异提示的代码补全输出结果；
2. 利用测试Oracle交叉比较代码补全输出的相似度，并识别异常值，其控制结构与其他值相比具有比较远的距离，这些异常值被视为错误的代码完成错误。

变异方案：我们实现了一组PSC变异，它们对程序的层次结构进行了不同级别的转换，从标识符、指令到基本块。现在将介绍每一种变异，并且只讨论设计和实施的基本要点。

REP R 和 REP C

我们的第一个变异方案对函数参数进行重命名。总体而言，此步骤将在函数参数列表中用一个新标识符替换一个参数，并相应地替换该参数的每个使用。命名方式可以是“调整”或“上下文”。考虑以下情况：

在“常规”方案（REP R）中，将函数参数 b 替换为 Param1。而对于考虑特定上下文的 REP C，我们将函数参数 b 扩展为一个新标识符，它涵盖了函数名 add 和 b。

REL R 和 REL C

与替换参数类似，此步骤将随机选择一个作用域在函数内的局部变量。然后，我们将所有引用该变量的地方都替换为一个新的标识符。考虑以下情况：

对于 REL R，我们将局部变量 res 替换为 LocalVar1。对于考虑上下文信息的 REL C，我们使用包含函数名称Compare 和 res 的新标识符重写局部变量 res。

内部收益率（IRR）

该方案实现了一组映射规则，以便它将搜索和替换某些常见算法操作转化为其语义等价表达式，但具有不同的语法形式。考虑到以下情况：

其中 += 语句被替换为标准加法表达式。总的来说，我们在这一步对不同的常见算术表达式实现了4条替换规则。

RTF

除了改变算术表达式之外，我们还实现 RTF 方案来改变布尔表达式，特别是用于形成分支条件的表达式，及其语义等效版本。考虑以下情况：

其中布尔表达式用始终为真的条件进行扩展。

GRA R 和 GRA C

这种突变会在程序中插入一小块“垃圾代码”，这不会改变程序语义，但会稍微增加程序的控制流复杂性。特别是，我们使用始终为假的条件来形成 if 条件，在该条件中，我们将一小组语句插入到新形成的分支中，这些语句永远不会被执行。与上面提到的突变类似，创建垃圾代码可以考虑上下文信息。考虑以下情况：

其中 GRA R 插入一个 if 条件表达式为”False”的分支，并带有名为 TempVar 的新变量。对于考虑上下文的 GRA C，我们创建了一个函数参数的语法形式为always-false条件，并用它构成if条件表达式。同样，封闭分支中的变量名称也包含函数名称和 TempVar。

INI

最后一次突变将在prompt中插入一条”print”语句。总的来说，这个方案是基于观察程序员在调试过程中经常插入这样的”打印”语句而设计的，这样他们就可以打印一些变量的状态来帮助调试。请参见以下示例：

我们在prompt中插入 print 。虽然这个方案没有改变程序结构，但我们发现它有效地提高了流行的代码补全系统的性能；

2.2 PSC 测试：形成测试预言机

通过比较补全输出之间的结构级一致性（相似性）来形成一个测试预测器。从代码补全输出中找到与参考代码相近的结构。为此，需要计算代码补全输出之间的相似性。一旦找到具有相似结构的代码补全输出，就可以根据这些输出形成测试验证器。具体步骤如算法1所示：

2.3 修复

在代码补全系统生成代码之后，我们收集了一组代码补全输出，其中异常值被排除在外。在这一步中，我们的目标是识别一个与的“平均外观”最为接近的代码补全输出。为此，我们测量每对（,）∈的平均编辑距离。然后，我们寻找一个∈，其与中所有其他元素的平均成对距离最接近。这个将是返回给用户的修复代码补全输出。这个过程通过计算和比较代码补全输出之间的编辑距离，从而找到一个最能代表整体平均状态的代码补全输出。这个输出被认为是经过修复的，更可能是没有错误的，因此可以更安全地返回给用户作为建议代码。

3 实验评估

3.1 实验设置

研究问题：在本文中，我们研究以下研究问题：

RQ1：CCTEST能否生成高质量且结构一致的提示变体？

RQ2：CCTEST检测代码补全缺陷的效果如何？

RQ3：CCTEST可以在多大程度上提高代码补全输出的质量？

解析和修改程序：我们使用tree-sitter解析 Python 代码，tree-sitter 是一个成熟且无依赖的解析器生成器工具，具有开源许可证。它广泛应用于 Codebert 等代码相关项目中，并且不需要输入代码可执行，这意味着没有构建脚本的不完整代码片段也可以被解析。我们首先将提示代码解析为具体的语法树，然后对目标代码进行多次健全性检查，以查看可以执行哪个转换过程。然后，在应用可行的转换后，CCTEST将输出相应的转换代码以及所应用转换步骤的ID。

评估数据集：与该领域的大多数研究一致，我们从托管的Leetcode 答案数据集和 CodesearchNet 形成评估数据集。由于基于LLM的代码补全系统有token大小的限制，我们只选择token长度在64到2048之间的程序。总体而言，每个种子程序都包含一个中等大小的函数，其控制可能很复杂的结构。我们从 Github 存储库中选取了 613 个代码片段作为种子程序。Leetcode程序生成的变体总数为 4296 个。

我们在评估中还采用了另一个常用的数据集CodeSearch-Net。该数据集广泛用于代码表示学习的研究。除了与 Leetcode 类似的数据过滤过程之外，我们只为测试拆分中同一”路径”中的代码保留一个代码片段，以保持结果平衡。该数据集中的每个程序都包含一个具有中等大小和重要控制结构的 Python 函数。我们总共使用了该数据集中的 2297 个代码样本，我们使用 Leetcode 和 CodeSearchNet 生成了 2910 个程序。这些程序是我们针对每个基于 LLM 的代码补全系统的突变方案的种子输入。生成的变体总数为 19898个。每个种子程序都包含一个中等大小的函数，并且具有复杂的控制结构和许多全局变量。

对比方法：我们评估了几个著名的代码补全LLM模型，如Github Copilot、CodeParrot、GPT-Neo、GPT-J和CodeGen，其中还评估同一模型的不同参数量的效果。

RQ1 评估突变体生成的有效性

回答RQ1需要评估突变提示的质量。在此步骤中，对于每个种子提示，我们生成突变体并检查它们是否可以通过编译。特别是，对于每个句子，我们生成最多9个突变体，从而在 2910 个种子提示之上总共生成19898个突变体提示。为了对进行转换后的代码的有效性进行快速健全性检查，我们使用 Python 中的ast模块来编译所有转换后的 Python 提示。我们发现所有这些生成的突变提示都可以通过编译，表明它们是有效的提示。

为了说明突变提示的结构级一致性，我们计算并交叉比较突变提示与同一种子提示的距离。理想情况下，较小的距离表明突变体表现出密切相关的结构，从而证明派生代码补全输出的一致性。我们使用pycode-similar返回比率，表示两个程序的相似程度。我们在表1中报告了”距离得分”的分布。总体而言，很明显，对于绝大多数突变提示（超过98%）结构级距离小于10%，证明突变提示与种子提示具有结构级一致性。

表1 结构一致性分数的分布

RQ1 的答案：TEST 可以生成语法有效且结构一致的高质量提示突变体。

RQ2 错误检测

为了回答RQ2，我们启动测试来检测代码补全缺陷。表2概述了我们的调查结果。请注意，我们使用两个数据集进行测试。例如，Copilot -#Prompts 单元格中的4909+17899 表示我们在 LeetCode 数据集上生成了4909 个突变提示，并且从 CodeSearchNet 数据集生成了 17899 个突变提示。同样，第一个”#Defect T =1″单元格中的”3003 + 12101″意味着使用 LeetCode突变输入找到了 3003 个异常值，而使用其他测试输入检测到了 12101 个异常值放。对于异常值检测评估，我们评估不同超参数 T 值下的性能。对于每个模型（在不同的异常值阈值 T 下），我们量化了两个指标下以及两个杠杆数据集的修复有效性。首先，如表2第二列所示，虽然几乎所有变异提示都可以处理，但我们仍然发现 58 个（0.03%）变异提示在测试的代码补全系统中触发”无响应”。正如预期的那样，鉴于基于 LLM 的生产代码补全系统的高性能和全面性，这种情况很少见。正如前面所阐明的：如果代码补全输出与从同一种子提示突变的 T 代码补全输出有很长的距离，则该代码补全输出被视为异常值。因此，T 是一个整数，范围从1到总数（在我们的实现中为9）。表2报告了根据不同模型和阈值未发现的异常值的数量。总体而言，在总共 个测试用例中，在阈值T 下发现了不同数量的缺陷。特别是，当将阈值 T 设置为 9 时，我们在 LeetCode 和 CodeSearchNet 数据集上分别发现 8 个 LLM 的缺陷为 5912 个和 27628 个。正如预期的那样，我们观察到随着 T 数量的增加，检测到的缺陷（异常值）数量减少。正如我们在算法1中所说明的，异常值选择的严格程度取决于阈值 T ，其中 T 越大表示标准越严格。例如，与 T = 5 相比，LeetCode 上Codeparrot 检测到的异常值数量仅为 904 个，不到前者（3631 个）的四分之一。如果我们设置 T = 1，很明显，几乎所有提示都被视为”异常值”，这意味着误报率很高。由于不一致缺陷数量较少（T = 9 时为293+2184），Copilot 的表现优于其他七名法学硕士。然而，Copilot 的”无响应”故障最多（58 次中有 41次）。我们认为这种观察背后的原因是它的输出与网络质量有关，Copilot即使查询十次也可能拒绝返回任何内容。尽管”无响应”失败的数量很少，但所有其他情况都可以通过一些重要的输出进行分析和补全。

表2 异常值检测和增强结果概述

总的来说，表2说明代码补全系统中的不一致错误是普遍存在的，即使在高度宽容的一致性阈值下仍然存在错误，也可以发现大量缺陷。我们分别在图 2 和图 3 中展示了两个代表性案例。特别地，图2呈现了一种情况，使得种子提示的代码补全输出与真实情况有很大偏差。请注意，当仅给出图 2（b）中的代码补全输出时，确定图2（a）和图 2（b）中的代码补全输出之间的偏差是由于模型容量还是由于模型容量或错误。然而，当参考图2（c） 时，很明显，经过测试的代码补全系统 Copilot 能够生成高质量的代码补全输出，这些输出表现出更接近真实情况的结构表示。请注意，与种子提示相比，我们仅对图 2（c） 中使用的提示的参数名称进行了一些调整。因此，可以准确地假设图 2（b） 表示代码补全的错误，该错误很可能是可修复的。此外，图3（a）呈现了另一种情况，使得种子提示的代码补全输出看起来与地面事实高度相似（图3（b））。相反，当应用 REL R 方案来改变局部变量的名称时，改变提示的代码补全输出（图 3（c））变得与真实情况有很大不同。这清楚地表明代码补全系统存在错误。

图2 异常值案例研究。种子提示的代码补全输出有很大偏差，而突变的提示会产生更好的代码补全输出。

图3 异常值案例研究。变异提示的代码补全输出有很大偏差，而种子提示会产生更好的代码补全输出。

RQ2 的答案：尽管在决定距离时使用了不同的阈值，但 CCTEST 在用于测试不同（商业）代码补全系统时识别出大量缺陷。在生产使用中，我们建议将 T = 9 配置为检测异常值的合理阈值。

RQ3 修复效果

为了回答 RQ3，我们首先展示不同评估的代码补全系统的准确性改进。然后，我们评估 CCTEST 中在不同模型中实施的每个 PSC 方案对修复的贡献的效力。

修复后精度增强：如RQ2中所述，我们在表 2 中报告了每个模型相对于编辑距离和 bleu4 得分的准确性改进。请注意，编辑距离和 bleu4 指标在相关研究中通常用于评估LLMs的性能；编辑距离分数或 bleu4 分数越高表示性能越好。为了澄清，表 2 报告了增强率。例如，当根据 LeetCode 数据集评估 Copilot 时，令编辑距离或 bleu4 分数为 s 。我们将增强率计算为，其中s’是修复后的编辑距离/bleu4 分数。此外，对于在这两个指标下评估的所有模型，改进率通常随着 T的增长而提高。我们用蓝色标记每个评估设置的最佳改进。并非所有情况都相同，对于 LeetCode 数据集上的Copilot，当 T = 5 时，bleu4 分数达到峰值。在对应 T= 7 的 Codegen-6B-mono 上也进行了类似的观察。我们将此观察归因于以下事实： Copilot 和 Codegen 比其余的代码补全系统具有相对更好的性能。因此，在严格的阈值 (T = 9) 下决定”异常值”可能会忽略异常值并破坏提高准确性的机会。

转换步骤的效能：在这一步骤中，我们衡量了 CCTEST 中实施的所有九个转换步骤的效能。让代码补全输出 oi 为修复后的输出，使得 oi 是通过使用从转换步骤 ti 突变的提示生成的。我们认为在这种情况下 ti 是“最佳”的转换，成功地为代码补全修复做出了贡献。对于 LeetCode 和 CodeSearchNet，我们分别在图 4 和图 5 中报告了不同模型下选择的不同转换作为“最佳”的分布。总的来说，在两个数据集中，本文设计的所有转换都广泛地被用作“最佳”。特别是，除了 “IRR” 和 “RTF” 外，几乎所有的转换都被选择了大致相等的次数。IRR 的应用范围相对较小，因为 IRR 寻找的特定算术操作，如 “+=”，可能并不普遍使用。类似地，RTF 需要存在一个相对简单的条件的 if 条件，这在我们的测试用例中可能不可用。总的来说，我们解释评估结果是非常鼓舞人心的，显示出所有设计的转换在增强不同模型方面具有很高的适用性和有效性。在使用 LeetCode 数据集时，“IRR” 显然更有助于提供“最佳”情况。通过手动检查，我们发现 LeetCode 中的代码（一个在线评测（OJ）平台）更有可能包含诸如 “+=” 之类的算术操作，与 CodeSearchNet 数据集中的代码相比。

图4 在评估 LeetCode 数据集时贡献修复输出的 PSC 变换的分布

图5 在评估 CodeSearchNet 数据集时贡献修复输出的 PSC 变换的分布

除了报告”最佳”转换的分布之外，我们还报告每个转换在有助于代码补全修复时可以在多大程度上提高代码补全系统的 bleu4 分数。

图6 LeetCode 数据集上不同 PSC 变换贡献的增强率分布。

图7 CodeSearchNet 数据集上不同 PSC 变换贡献的增强率分布。

图 6 和图 7 报告了两个数据集下所有代码补全系统的增强率。与图 4 和图 5 中的观察结果一致，我们发现所有转换步骤在不同的设置和数据集下都表现出不错的增强率。

RQ3 的答案：CCTEST 可以成功提高不同代码补全系统的质量。我们还发现，所有方案都被证明可以有效提高代码补全系统的性能，而不是一种或几种提示突变方案对增强代码补全有显著贡献。

转述人：杨襄龙