程序修复程序：78.3%的“Bug修复正确率”是怎么做到的？
今年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等会议上发表了多篇论文。此外，双方还联合在北京大学开设了《软件分析》课程以培养更多相关优秀人才，等等。三年深耕，成果丰硕，我们期待未来双方在软件分析领域的合作会取得更多重要的成果！
你也许还想看：
感谢你关注“微软研究院AI头条”，我们期待你的留言和投稿，共建交流平台。来稿请寄：msraai@microsoft.com。