业界 | 自动修复Bug正确率达78.3%，北大、微软等提出ACS技术

机器之心

发布于 2018-05-09 16:05:27

1.1K0

发布于 2018-05-09 16:05:27

文章被收录于专栏：机器之心机器之心

转载自微软研究院 AI 头条

机器之心报道

论文编译：黄小天

今年 2 月，微软研究院与剑桥大学宣布合作开发了一种名为 DeepCoder 的新算法，可以根据问题的输入输出自动编写解题程序。但事实上，DeepCoder 的实现是基于一种原创的、极其精简的语言，还不能独立处理较为复杂的问题，目前业界使用的编程语言对于它来说还难以掌握。所以广大程序员们完全不用担心会被机器取代！

那么除此以外程序员们最担心的是什么呢？大概就是调 Bug 了吧~ 鉴于机器已经可以完成简单的编程任务，我们当然希望能利用它更好地辅助程序员的工作。

为此，北京大学、微软亚洲研究院和电子科技大学的研究人员联合开发了一种新技术 ACS (Accurate Condition Synthesis)。该技术可以全自动修复软件系统中的缺陷，无需用户干预。

比如，下面这段代码来源于 Apache Math 库，用于求两个数的最小公倍数。该段代码采用了绝对值函数 Math.abs 来保证返回的值是一个正数。但由于实现上的缺陷，在某些输入的时候会返回负数。

int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b)); return lcm;

这个缺陷的根源是因为负数的数值范围比正数多一个，所以当传给 Math.abs 的值是 Integer.MIN_VALUE 时，Math.abs 并不能将输入转换成正数，进而导致函数产生负数的输出。一个正确的实现应该在这个时候返回 ArithmeticException()。

现在假设有一个测试来捕获这个错误，该测试的输入为 a=Integer.MIN_VALUE 和 b=1，期望的输出为 ArithmeticException。很显然，这个测试将在该程序上运行失败，因为并没有异常被抛出。

但当我们将这个程序和相应的测试提供给 ACS 时，ACS 将会自动生成如下补丁，准确的修复了该缺陷：

int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b)); + if (lcm == Integer.MIN_VALUE) { + throw new ArithmeticException(); + } return lcm;

事实上，缺陷修复技术由来已久。自 2009 年的 GenProg 技术以来，学术界已经提出了数十种不同类别的缺陷修复方法。但传统的缺陷修复技术一直面临一个问题——缺陷修复正确率非常低。这是因为传统缺陷修复系统以通过测试为目标，但实际软件系统中，测试往往数量有限，通过测试并不意味着程序就是正确的。

比如上面这个例子，现有系统可能生成如下补丁：

int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b)); + if (b == 1) { + throw new ArithmeticException(); + } return lcm;

甚至如下补丁：

int lcm=Math.abs(mulAndCheck(a/gdc(a,b), b)); - return lcm; + throw new ArithmeticException();

这些补丁都能通过测试，但却与正确程序差别甚远。其实，在这个例子中，我们可以很容易地找到能够通过测试的上百个不正确的修复，这将导致修复技术的正确率变得非常低。

根据 2015 年初美国麻省理工学院的 Martin Rinard 教授在其 ISSTA 论文中的发现，主流缺陷修复技术在真实缺陷上的正确率不超过 10%。虽然后来出现了一些改进的技术，如麻省理工学院的 Prophet 和新加坡国立大学的 Angelix，但这些技术的正确率也都没有超过 40%。这就意味着，这些技术所产生的补丁中，大多数是错误的。而这样的技术基本没有办法在实践中使用。

而 ACS 技术的正确率和之前的技术相比有了显著提升。在缺陷修复的基准数据集 Defects4J 上的测试结果中，ACS 生成了 23 个补丁，其中 18 个是正确的，修复正确率接近 80%，显著超越了现有技术。而在正确率大幅提升的同时，ACS 在该数据集上正确修复的缺陷数量也是同类方法中最多的。目前 ACS 的修复正确率和修复数量都取得了该数据集上的最好结果。

ACS 主要是利用了多源信息，特别是互联网上广泛存在的代码大数据信息来联合保证修复的正确性。相比已有技术，ACS 综合使用了三种新的信息：

首先，ACS 发现代码中的变量使用在数据依赖关系上呈现明显的局部性特征，并利用依赖信息对补丁中的变量使用进行排序。
其次，ACS 采用自然语言技术分析代码中的 Javadoc，再利用 Javadoc 中的信息对错误补丁进行过滤。
最后，也是最重要的，ACS 对互联网上广泛存在的开源代码进行统计，发现变量和应用在变量上的操作之间的关联信息，从而生成正确的补丁。

在上面的例子中，ACS 先利用代码中的数据依赖确定 lcm 是应该使用在 if 判断中的变量，同时根据互联网上变量和操作之间的关联确定应该进行 ==Integer.MIN_VALUE 的判断，最后再根据测试的预期结果生成 if 语句体中的 throw 语句，从而生成整个完整的补丁。

ACS 系统的相关论文「Precise Condition Synthesis for Program Repair」已发表在 ICSE 2017 上。论文作者包括北京大学熊英飞研究员、北京大学硕士研究生王杰、电子科技大学本科生严润发、北京大学本科生章嘉晨、微软亚洲研究院主管研究员韩石、北京大学黄罡教授和张路教授。在投稿 ICSE 2017 后不久，熊英飞研究员就作为中国大陆唯一代表应邀参加了 2017 程序缺陷修复 Dagstuhl 国际研讨会，就该论文内容进行了特邀报告，并受到了与会者的一致肯定。

从左至右：微软亚洲研究院主管研究员韩石，微软亚洲研究院学术合作经理孙丽君和北京大学熊英飞研究员

三年来，熊英飞研究员和微软亚洲研究院一直保持着密切的科研合作。不仅与微软亚洲研究院副院长张冬梅和主管研究员韩石一起承担了微软亚洲研究院的合作项目「Enhancing Source Code Mining with Semantics」，并在 ICSE 发表了论文，还与张冬梅博士负责的软件分析组成员合作进行了编译器测试的研究，且已经在 ICSE、ICST 等会议上发表了多篇论文。此外，双方还联合在北京大学开设了《软件分析》课程以培养更多相关优秀人才，等等。

论文：Precise Condition Synthesis for Program Repair

地址：https://www.microsoft.com/en-us/research/wp-content/uploads/2017/02/1608.07754.pdf

摘要：由于修复缺陷很困难，很多研究努力贡献在了自动缺陷修复上。对于一个未通过测试案例的带有 bug 的程序，典型的自动修复技术是修改程序以通过所有测试。然而，由于实际项目中的测试程序组通常不充分，通过测试程序组的目标导向经常会导致不正确的补丁。这个问题被称为弱测试组（weak test suites）或者过拟合。

在本论文中，我们旨在生产精确的补丁，即我们生产的所有补丁有一个较高的正确概率。更具体地说，我们致力于条件合成（condition synthesis），结果表明它比现有方法能够修复的缺陷多一半。我们的核心见解有三个方面：第一，知道本地语境中的什么变量用于「if」条件中很重要，我们基于变量之间的依赖关系提出了一种排序方法；第二，我们观察到 API 文档可用于指导修复进程，并且提出文档分析技术以进一步过滤变量；第三，知道在变量集上执行什么谓语很重要，我们建议在现有项目的类似环境中挖掘一组经常使用的谓词。

基于以上见解，我们开发了一个全新的程序修复系统——ACS，它可在故障位置产生精确的条件。鉴于非常精确的生成条件，我们执行了一个之前被认为是过度拟合的修复操作：直接返回测试 oracle 来修复缺陷。通过这一方法，我们成功修复了 Defects4J 的 4 个项目中的 18 个缺陷，这是目前为止数据集中报告的最大数量的完全自动修复的缺陷。更重要的是，我们方法的评估的精度达 78.3%，明显高出通常只有低于 40% 精度的先前方法。