Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Practical Program Repair via Bytecode Mutation

作者:Ali Ghanbari, Samuel Benton, and Lingming Zhang

单位:University of Texas at Dallas

出处:ISSTA’19

原文:https://ali-ghanbari.github.io/publications/issta19.pdf


Abstract

自动化程序修复技术(APR: automated program repair)能够在极少的人工干预的前提下直接修复程序错误。尽管各式各样包括基于搜索的和基于语义的先进APR技术被广泛提出,这些技术往往只针对程序的源代码而非字节码来进行修复。在这篇文章中,作者提出了首个工作在字节码层面上的实用APR技术:PraPR,其利用JVM字节码变异技术(JVM bytecode mutation)来修复现实存在的程序错误,例如Defects4J数据集中的程序错误。

实验结果表明,搭配基础的传统变异规则的PraPR能够为17处程序错误生成正确的补丁(genuine),搭配简易的常用APR变异规则的PraPR能够为43处程序错误生成正确的补丁,其表现明显优于已有的APR技术,并能够获得超过10倍的性能提升。作者还使用了大量Defects4J数据集以外的程序错误来评估PraPR和其它已有的APR技术,并首次展现了已有的APR技术存在的过拟合问题(overfitting)。此外,PraPR还成功修复了使用例如Kotlin等其它JVM语言编写的程序中存在的程序错误。

1 Introduction

根据修复程序错误所需要采取的操作,已有的APR技术可以被分为以下两个大类:

  • 运行时监控技术:该技术通过监控程序的动态执行来找到违反特定规则的程序行为,并在反常程序行为发生时,修改程序的运行状态以修复程序;
  • 生成-验证技术(G&V: generate-and-validate):该技术基于各式各样的规则来修改程序代码,随后利用测试用例作为预言机(oracle)来验证生成的候选补丁,以找到合理的补丁(plausible),即能够通过所有测试用例的补丁,最后通过进一步筛选这些合理的补丁,以找到正确的补丁(genuine),即与开发者提交的补丁在语义层面上等同的补丁。

在这篇文章中,作者首次研究了工作在字节码层面上的APR技术,其基于一系列简易的JVM字节码变异规则实现了PraPR,并在Defects4J数据集上进行了广泛的测试。PraPR使用到的JVM字节码变异规则包括1)来源于传统变异测试(mutation testing)的基础变异规则,例如将$a \ge b$转换为$a > b$;2)在现实存在的程序错误修复提交中经常出现的增强变异规则,例如替换访问的变量和调用的函数。

值得注意的是,尽管所涉及到的技术都较为简单,PraPR能够作为已有APR技术的补充,并依旧具有以下优势:

  • PraPR生成的所有补丁都可以直接被验证,而不需要经过预先的编译和加载;
  • PraPR工作在字节码层面上,其避免了意外扰乱程序的源代码的可能性,并能够被用于修复源代码缺失的程序;
  • PraPR针对程序的JVM字节码来进行修复,其不依赖于特定的目标编程语言的语法;
  • PraPR不依赖于复杂的计算或者任何模型训练和数据挖掘来进行修复,其具有很强的适用性,并可以被直接用来作为未来APR技术的基准。

2.1 Mutation Testing

变异测试是评估一组测试用例检测潜在的程序故障的能力的有力手段。变异测试通过在程序中引入人造的程序错误以评估一组测试用例的质量。变异测试的核心便是变异算子(mutation operator),即变异规则,例如将$a + b$转换为$a - b$。

2.2 Generate-and-Validate Program Repair

G&V APR技术通常首先使用已有程序错误定位技术(fault localization)来识别可疑的代码成分,随后按照特定的规则修改、插入、或者删除这些代码成分,生成相应的程序变体,并利用测试用例作为预言机来寻找能够通过所有测试用例的程序变体。

3 PraPR

3.1 Overall Approach

20200106152725

为了保证利用测试用例作为预言机来验证生成的候选补丁的性能,作者采用了以下优化方案:

  • 首先利用最初失败的测试用例来验证生成的候选补丁,如果该候选补丁能够通过所有最初失败的测试用例,随后利用剩余的测试用例来验证该候选补丁;
  • 所有的候选补丁都是直接在JVM字节码层面上生成的,以避免预先编译和加载大量候选补丁所带来的巨大开销;
  • 预先筛选出覆盖候选补丁修复位置的测试用例,利用这些测试用例来验证该候选补丁,并略过其它的测试用例;

作者强调,PraPR在字节码层面上生成的补丁能够为开发者提供足够的信息来确认或是拒绝该补丁,并将其应用在源代码层面上。

20200106153109

20200106175331

3.2 PraPR Mutators

为了提升性能,PraPR所使用的所有变异规则都是在JVM字节码层面上实现的,其实现支持所有的JVM指令和数据类型。

表中白底的传统变异规则来源于工作在字节码层面上的变异测试引擎PIT,浅灰底的增强变异规则用于替换程序的字节码中的表达式,深灰底的增强变异规则用于在程序的字节码中插入条件表达式。

20200106175511

20200106175644

为了进一步确认PraPR所使用的变异规则的普遍性,作者自动化的提取了HD-Repair数据集中所涉及到的修复模板,该数据集包含了来源于700+个GitHub仓库中的3000+个现实存在的补丁。

20200106175909

4 Experimental Setup

在这篇文章中,作者研究了以下五个研究问题:

  • RQ1:PraPR在自动化修复现实存在的程序错误时的有效性如何?
  • RQ2:PraPR的性能如何?
  • RQ3:PraPR与其它已有的APR技术相比如何?
  • RQ4:PraPR与其它已有的APR技术在修复数据集以外的程序错误时的有效性如何?
  • RQ5:PraPR在修复使用除Java以外的其它JVM语言编写的程序错误时的有效性如何?

作者在Defects4J V1.4.0数据集上对PraPR进行评估,该数据集包含16个现实存在的来源于GitHub的Java程序,这些程序包含已知且能够被重现的现实存在的程序错误。

20200106182605

5 Result Analysis

5.1 RQ1: PraPR Effectiveness

20200106184213

本文是第一篇展现在修复现实存在的程序错误时,普通变异测试和其它已有的APR技术有效性相当的研究。

实验结果展现了PraPR的有效性,并且显示了快速且彻底的补丁生成和验证技术对于自动化程序修复领域的重要性,即更加快速的补丁生成和验证能够允许我们应用更多种类的变异规则,探索更加完善的搜索空间。

20200106194652

20200106194717

5.2 RQ2: PraPR Efficiency

20200106194810

值得注意的是,除了机器运转时间以外,APR技术的修复性能还与人工筛选合理的补丁(plausible),以找到正确的补丁(genuine)的时间有关。因此,作者还列举了正确的补丁在所有合理的补丁中的排名,以进一步评估PraPR的性能。

20200106194909

5.3 RQ3: Comparison with the State-of-Art

为了回答该研究问题,作者将PraPR与其它已有的在Defects4J (V1.2.0)上评估过的APR技术进行了比较,包括SimFix、CapGen、JAID、SketchFix、ELIXIR、ssFix、ACS、HD-Repair、xPAR、NOPOL、jGenProg、jMutRepair、以及jKali。

20200106195006

特别的,作者依据前文对于HD-Repair数据集的数据挖掘结果进一步优化了PraPR的性能,即基于HD-Repair数据集中所涉及到的修复模板的频率,对PraPR生成的合理的补丁进行相应的排序,以优化正确的补丁在所有合理的补丁中的排名,经过优化的PraPR在表中表示为PraPR*。

20200106195043

20200106195121

5.4 RQ4: APR Tools on Additional Bugs

20200106195207

本文是第一篇展现其它已有的APR技术在修复数据集以外的程序错误时存在过拟合问题,而基于简单的字节码变异的APR技术则具有良好的一致性的研究。

5.5 RQ5: PraPR Repair for Real Kotlin Bugs

20200106195225

PraPR是第一个能够修复使用Kotlin语言编写的程序中存在的程序错误的系统。PraPR对于使用Kotlin语言编写的程序和使用Java语言编写的程序中存在的程序错误的修复率也是近似一致的。