#HITS
单元测试是软件开发流程中的一个关键环节,主要用于验证软件中的最小可测试单元,函数或模块是否按预期工作。单元测试的目标是确保每个独立的代码片段都能正确执行其功能,对于提高软件质量和开发效率具有重要意义。
然而,大模型自身无力为复杂待测函数(环复杂度大于 10)生成高覆盖率的测试样例集。为了解决该痛点,北京大学李戈教授团队提出一种全新的提升测试用例覆盖率的方法,该方法借助程序分片思想(Method Slicing),将复杂待测函数依据语义拆解为若干简单片段,进而让大模型为各个简单片段分别生成测试样例。生成单个测试样例时,大模型只需分析原待测函数的一个片段,分析难度减小,生成覆盖该片段的单元测试难度随之减小。由此推广,提升整体测试样例集代码覆盖率。
相关论文《HITS: High-coverage LLM-based Unit Test Generation via Method Slicing》近期被 ASE 2024(at the 39th IEEE/ACM International Conference on Automated Software Engineering)顶会接受。
论文地址:https://www.arxiv.org/pdf/2408.11324
接下来看看北大团队论文研究的具体内容:
HITS 使用大模型进行程序分片
程序分片指将一个程序依据语义划分为若干解决问题的阶段。程序是对一个问题解决方案的形式化表述。一个问题解决方案通常包含多个步骤,每个步骤对应着程序中的一片(slice)代码。如下图所示,一个色块对应着一片代码,也对应着一个问题解决的步骤。
HITS 要求大模型分别为每个代码片设计可以高效覆盖它的单元测试代码。以上图为例,当我们得到如图的分片后,HITS 要求大模型为 Slice 1(绿色),Slice 2(蓝色),Slice 3(红色)分别生成测试样例。为 Slice 1 生成的测试样例要尽可能覆盖 Slice 1,不用考虑 Slice 2 和 Slice 3,其余代码片同理。
HITS 起效的原因有二。其一,大模型要考虑覆盖的代码量降低。以上图为例,为 Slice 3 生成测试样例,则只需考虑 Slice 3 中的条件分支。要覆盖 Slice 3 中的某些条件分支,只需在 Slice 1 和 Slice 2 中找寻一条执行路径即可,无需考虑该执行路径对 Slice 1 和 Slice 2 覆盖率的影响。其二,依据语义(问题解决步骤)分割的代码片有助于大模型掌握代码执行中间状态。为顺序靠后的代码块生成测试样例,需要考虑先前代码对程序状态的改变。由于代码块依据实际问题解决步骤分割,因此可以用自然语言对先前代码块的操作进行描述(如上图中注释部分)。由于当前大语言模型多为自然语言与程序语言混合训练产物,良好的自然语言概括可帮助大模型更精准掌握代码对程序状态的改变。
HITS 使用大模型进行程序分片。问题的解决步骤通常为带有程序员主观色彩的自然语言表述,因而可以直接利用自然语言处理能力超群的大模型。具体而言,HITS 使用上下文学习方法(In-context learning) 调用大模型。团队利用过往在真实场景实践的经验,手工编写若干程序分片样例,经若干次调整后使大模型对程序分片的效果达到了研究团队的预期。
对代码片生成测试样例
给定要覆盖的代码片段,要生成对应测试样例,需经历以下 3 个步骤:1. 对片段的输入进行分析;2. 构造 prompt 指示大模型生成初始测试样例;3. 使用规则后处理和大模型 self-debug 调整测试样例使之可以正确运行。
对片段的输入进行分析,指提取要覆盖的片段所接受的一切外部输入,以备后续 prompt 使用。外部输入,指该片段所应用到的先前片段定义的局部变量,待测方法的形参,片段内调用的方法以及外部变量。外部输入的值直接决定了要覆盖的片段的执行情况,因此将该信息提取出来提示给大模型有助于有针对性地设计测试样例。研究团队在实验中发现大模型拥有良好的提取外部输入的能力,因此在 HITS 中由大模型来完成该任务。
接下来,HITS 构建思维链(Chain-of-thought)形式的 prompt 引导大模型生成测试样例。推理步骤如下。第一步,给定外部输入,分析要满足待覆盖代码片内的各种条件分支的排列组合,外部输入都分别需要满足哪些性质,如:组合 1,字符串 a 需要包含字符’x’,整数变量 i 需要非负;组合 2,字符串 a 需要非空,整数变量 i 需要为质数。第二步,对上一步中的每一种组合,分析相对应的待测代码执行时所处环境的性质,包括但不限于实参的特性,全局变量的设置。第三步,为每一种组合生成一个测试样例。研究团队为每一步手工构建了样例,以便于大模型能够正确理解并执行指令。
最后,HITS 通过后处理和 self-debug 使大模型生成的测试样例得以正确运行。大模型生成的测试样例往往难以直接使用,会出现各式各样的编译错误和来自于错误编写测试样例导致的运行时错误。研究团队根据自身观察及已有论文的总结,设计了若干规则和常见错误的修复案例。首先尝试依据规则修复。如果规则无法修复,则使用大模型 self-debug 的功能进行修复,在 prompt 中提供了常见错误的修复案例以供大模型参考。
HITS 的整体图解
实验验证
研究团队使用 gpt-3.5-turbo 作为 HITS 调用的大模型,分别在大模型学习过和未学习过的 Java 项目中的复杂函数(环复杂度大于 10)上对比 HITS,其他基于大模型的单元测试方法和 evosuite 的代码覆盖率。实验结果显示 HITS 相较于被比较的诸方法有较明显的性能提升。
研究团队通过样例分析展示分片方法如何提升代码覆盖率。如图所示。
该案例中,基线方法生成的测试样例未能完全覆盖 Slice 2 中的红色代码片段。然而,HITS 由于聚焦于 Slice 2,对其所引用的外部变量进行了分析,捕捉到 “如果要覆盖红色代码片段,变量’arguments’ 需要非空 “的性质,根据该性质构建了测试样例,成功实现了对红色区域代码的覆盖。
提升单元测试覆盖率,增强系统的可靠性和稳定性,进而提高软件质量。HITS使用程序分片实验证明,该技术不仅能大幅提升整体测试样例集代码覆盖率,且实施方法简洁直接,未来有望在真实场景实践中,帮助团队更早发现并修正开发中的错误,提升软件交付质量。
#极端黑洞可能存在
数学与宇宙的神奇超乎想象。
为了理解宇宙,科学家常需要考虑那些极端的异常情况。南安普顿大学数学物理学家 Carsten Gundlach 说:「我们总是需要考虑极端情况,就是那些位于边缘的特例。」
黑洞就是宇宙中神秘莫测的极端。根据爱因斯坦的广义相对论,黑洞之中的物质非常致密,任何东西都无法逃离。几十年来,物理学家和数学家们一直在借助黑洞来探究他们有关引力和时空的想法的极限。
但即使黑洞,也有边缘特例 —— 并且这些特例也能为我们带来不同的洞见。黑洞会在空间中旋转。当物质落入其中时,黑洞的旋转速度会加快;如果该物质带电,则黑洞也会带上电。原理上讲,黑洞所带的电荷量或自转速度都有一个极限,这应当取决于其质量。这样的黑洞被称为极端黑洞(extremal black hole)—— 它们是极端中的极端。
这些黑洞具有一些古怪的性质。尤其值得一提的是:这些黑洞的边界(即事件视界)处的表面引力为零。Gundlach 说:「这是一种表面不再吸引任何物质的黑洞。」但如果你把一个粒子轻轻推向该黑洞的中心,它也无法逃离。
1973 年时,著名物理学家斯蒂芬・霍金、约翰・巴丁(John Bardeen)和布兰登・卡特(Brandon Carter)断言真实世界中并不存在这样的极端黑洞 —— 它们根本不可能形成。尽管如此,过去五十年来,极端黑洞依然是理论物理学领域一个有用的模型。罗德岛大学的 Gaurav Khanna 说:「它们有非常好的对称性,能让计算更简单。」这让物理学家可以检验那些有关量子力学和引力之间神秘关系的理论。
斯蒂芬・霍金
现在,两位数学家证明霍金等人的论断是错误的。这两位数学家是麻省理工学院的 Christoph Kehle 和斯坦福大学的 Ryan Unger。他们最近通过两篇论文证明我们已知的物理定律并不能阻止极端黑洞的形成。
- 论文 1:Gravitational collapse to extremal black holes and the third law of black hole thermodynamics; arXiv:2211.15742
- 论文 2:Extremal black hole formation as a critical phenomenon; arXiv:2402.10190
普林斯顿大学数学家 Mihalis Dafermos(也是 Kehle 和 Unger 的博导)说,他们的数学证明「很美,有着技术上的创新,并且有着出人意料的物理学结果」。他补充说,这暗示着宇宙可能比之前人们认为的更加丰富多样,「在天体物理学上,极端黑洞可能存在」。
但这并不意味着它们真的存在。「就算存在一个性质优良的数学解,也并不一定意味着大自然就会用到它。」Khanna 说,「但就算我们以某种方式找到了一个,也会让我们思考我们忽视了什么东西。」他指出,这样的发现有可能带来「一些相当根本性的问题」。
不可能定律
在 Kehle 和 Unger 的证明出现之前,我们有充分的理由相信极端黑洞不可能存在。
1973 年,巴丁、卡特和霍金提出了有关黑洞行为的四条定律。它们类似于四个长期确立的热力学定律 —— 一组神圣的原则,例如:宇宙随着时间的推移变得更加无序、能量既不能被创造也不能被毁灭。
数学家 Christoph Kehle,他最近推翻了 1973 年那个有关极端黑洞的猜想
这三位物理学家在论文中证明了前三个黑洞热力学定律:第零定律、第一定律和第二定律。通过延伸,他们假定第三定律(类似于其对标的标准热力学定律)也正确,不过他们那时还无法证明这一点。
该定律指出:黑洞的表面引力不能在有限的时间内降至零 —— 也就是说,无法创造一个极端黑洞。为支持这一论断,这三位物理学家表示,如果某个过程能让黑洞的电荷量或自转速度到达极限,那么该过程就可能导致该黑洞的事件视界完全消失。人们普遍认为并不存在没有事件视界的黑洞,即裸奇点(naked singularity)。此外,因为已知黑洞的温度正比于其表面引力,所以没有表面引力的黑洞就没有温度。这样的黑洞就没有热辐射 —— 而霍金后来提出黑洞必定会发出热辐射。
1986 年,物理学家 Werner Israel 发表了一份对第三定律的证明,似乎让这个问题尘埃落地了。假设你想基于一个常规黑洞创造一个极端黑洞。你可以让其更快旋转,也可向其添加更多带电粒子。Israel 的证明似乎表明,这样做无法迫使黑洞的表面引力在有限时间内降至零。
正如 Kehle 和 Unger 最终发现的那样,Israel 的论证隐藏了一个缺陷。
第三定律之死
Kehle 和 Unger 原本并不打算寻找极端黑洞。他们的发现完全是偶然。
他们当时正在研究带电黑洞的形成。Kehle 说:「我们意识到我们可以创造所有荷质比的黑洞」。这就包括了电荷量尽可能高的情况,也就是极端黑洞的情况。
在证明了高度带电的极端黑洞在数学上是可能的之后,斯坦福大学的 Ryan Unger 现在已经着手尝试证明高速旋转的黑洞也是如此。但这个问题要困难得多。
Dafermos 认识到他之前的学生发现了巴丁、卡特和霍金的第三定律的一个反例:他们的研究表明,可以在有限的时间内将一个常规黑洞变成极端黑洞。
Kehle 和 Unger 的证明是从一个不旋转且不带电的黑洞开始,然后建模将其放入一个名为标量场的简化环境后的情况。标量场假设背景中存在均匀的带电粒子。然后,他们用来自该场的脉冲冲击黑洞,给它增加电荷。
这些脉冲也会向该黑洞提供电磁能,进而增加其质量。这两位数学家们认识到,通过发送弥散的低频脉冲,黑洞电荷增加的速度会比黑洞质量增长的速度快 —— 这正是他们完成证明所需的。
在与 Dafermos 讨论了这个结果之后,他们仔细研读了 Israel 在 1986 年发表的那篇论文并发现了其中的错误。他们还构建了爱因斯坦广义相对论方程的另外两个解,它们涉及向黑洞添加电荷的不同方式。他们在三种不同情况下证否了巴丁、卡特和霍金的猜想,得到了确定无疑的结果。Unger 说:「第三定律已死。」
这两人还证明,极端黑洞的形成并不会像很多物理学家担忧的那样导致出现裸奇点。相反,极端黑洞似乎处于一个关键阈值上:向致密的带电物质云添加适量的电荷,它就会坍缩形成极端黑洞。如果超过了这个量,这团物质云也不会坍缩成裸奇点,而是会散开。根本就不会形成黑洞。这一结果让 Kehle 和 Unger 倍感兴奋,因为其证明极端黑洞可能存在。
哥伦比亚大学数学家 Elena Giorgi 说:「这是数学回馈物理学的一个绝佳例证。」
曾经不可能,今日已可见
Kehle 和 Unger 证明理论上自然界可以存在极端黑洞,但并不保证它们一定存在。
首先,那些理论示例具有大量电荷。但人类还从未观测到过明显带电的黑洞。找到快速旋转的黑洞的可能性要大得多。在电荷版示例之外,Kehle 和 Unger 想要构建一个旋转达到阈值的示例。
但研究旋转的数学难度不可同日而语。Unger 说:「为了做到这一点,你需要大量新数学和新思路。」他与 Kehle 才刚开始研究这个问题。
与此同时,如果能更好地理解极端黑洞,那么也能帮助我们更好地理解近极端的黑洞 —— 人们相信宇宙中存在大量这类黑洞。「爱因斯坦曾认为黑洞不可能存在,因为它们实在太古怪了。」Khanna 说,「但现在我们知道宇宙中到处都有黑洞。」
出于类似的原因,他补充道:「我们不应该放弃极端黑洞。我只是认为大自然的创造力没有极限。」