AVATAR：通过修复静态分析冲突的模式来修复语义错误

原文作者：Kui Liu，Anil Koyuncu，Dongsun Kim，Tegawende F. Bissyandè
原文标题：AVATAR: Fixing Semantic Bugs with Fix Patterns of Static Analysis Violations
原文链接：https://ieeexplore.ieee.org/abstract/document/8667970
原文来源：2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER)
笔记作者：bight@SecQuan

解决的问题

基于修复模式的补丁程序生成是自动程序修复（APR）的一个有希望的方向。在软件工程社区中，重点主要放在修复语义错误上，即使程序行为偏离开发人员意图的那些错误。测试套件可以检测到此类错误。然后，APR研究人员开发了修复管道，在该管道中，不仅利用程序测试用例来对错误进行本地化，而且还利用其对生成的补丁进行验证。不幸的是，考虑到测试套件可能不完整，典型的APR系统易于生成可能违反预期程序行为或简单引入测试套件未涵盖的其他缺陷的无意义的补丁。Smith等人的最新研究对此问题进行了彻底调查，发现过度拟合的补丁实际上很常见：这些补丁可以通过所有可用的测试用例，但实际上并不正确。

论文主要贡献

• 作者发现，尽管静态错误查找工具可以从Defects4J数据集中检测到相对较少的真实世界中的语义错误，但从补丁中推断出的解决模式（针对静态检测到的错误）可以在针对语义错误的APR管道中提供相关成分。
• 作者提出了AVATAR（基于静态分析冲突的基于固定模式的自动程序修复），这是一种新颖的基于固定模式的程序自动修复方法。该方法与开发人员补丁程序数据集中的相关工作不同，后者可用于提取固定成分。AVATAR基于从已通过漏洞检测工具验证为真正的错误修复的补丁中提取的模式。给定静态分析工具检测到的错误类型的冗余度，相关的修补程序在直观上更加相似，从而推断出可靠的通用修补程序模式。AVATAR可从以下网址获得：https：//github.com/SerVal-Repair/AVATAR。
• 作者在Defects4J基准上报告了对AVATAR的经验评估。将该方法与基于不同评估方面的最新技术进行了比较，包括固定错误的数量，固定错误的排他性，补丁正确性等。在多项评估中，发现AVATAR能够生成正确的错误。当假设一个完美的故障定位场景时，AVATAR能够为34个错误生成正确的补丁，为5个错误生成部分正确的补丁。

挖掘静态冲突的修复模式

下面，我们将静态分析冲突的修复模式挖掘过程概括为三个基本步骤（如图1所示）：数据收集，数据预处理和修复模式挖掘。  

1.数据收集

此步骤的目的是收集与静态分析冲突有关的补丁。根据开放源代码项目的提交历史记录，通过实施严格的策略将更改的数据集限制为与静态分析冲突相关的更改数据集，从而在野外完成此步骤。为此，有必要针对程序的每个修订版系统地运行静态错误检测工具。
仅当代码更改（即补丁程序）被标识为冲突修复更改时，此步骤才会收集它们。对于给定的冲突实例，假设更改提交是该实例在提交后消失的（候选）修补程序：即冲突实例在程序的修订版中标识，但在连续修订版中不再标识。然后，有必要弄清楚更改是实际解决了冲突实例还是只是巧合地消失了。如果受影响的代码行位于提交的代码更改diff中，则它将被视为给定冲突实例的实际修复。否则，仅通过删除方法、类甚至文件就可以删除冲突实例。最终，将收集与已标识的固定冲突实例关联的所有代码更改diff，以形成用于修复模式挖掘的输入数据。

2.数据预处理

模式挖掘研究利用程序抽象语法树（AST）的编辑脚本。具体地说，错误版本（即可以找到冲突的程序修订文件）和固定版本（即没有出现冲突的连续程序修订文件）作为GumTree的输入，GumTree是一种基于AST的代码差异工具，用于生成相关的AST编辑脚本。此编辑脚本以细粒度的方式描述修补程序中实现的修复操作。图2提供了一个bug修复补丁的GNU Diff示例，而图3说明了相关的AST编辑脚本。

3.修复模式挖掘

给定一组编辑脚本，模式挖掘步骤的目标是将“相似”脚本分组，以推断出编辑操作的公共子集，即整个组中的一致模式。作者利用深度表示学习框架（即CNN）来学习编辑脚本的功能，然后将其用于查找相似的编辑脚本的集群。基于X均值算法执行聚类。最后，将群集中所有编辑脚本中最大的编辑操作公共子集视为模式。

AVATAR

1.故障定位

作者依靠GZoltar框架来自动执行每个程序的测试用例。在该框架中，利用Ochiai排名度量标准来实际计算可能是错误代码位置的语句的可疑分数。

2.修复模式匹配

在维修管道的运行中，一旦故障定位产生了可疑代码位置的列表，AVATAR就会反复尝试将这些位置中的每个位置与挖掘出的修复模式数据库中的给定模式进行匹配。每个模式实际上都是针对特定AST节点类型的修复操作的编辑脚本。然后，将与错误代码位置关联的AST节点视为与固定模式匹配的上下文：即，对照固定模式编辑脚本中涉及的节点检查这些节点。仅当此位置的所有AST节点上下文与该模式的AST节点匹配时，该模式才与错误的代码位置相关。

3.补丁生成

给定可疑的代码位置和相关的匹配修复模式，AVATAR会在模式的编辑脚本中应用修复操作，以生成候选补丁。

4.补丁验证

必须对AVATAR生成的候选补丁进行系统评估。最终，论文使用测试用例来验证候选补丁是否是合理的补丁。论文针对两种可能的补丁：

• 完全修复的修补程序，这些修补程序可使程序通过所有可用的测试用例。验证了此类补丁后，将停止AVATAR的执行迭代。
• 部分修复的补丁程序，这些补丁程序使程序不仅可以通过所有先前通过的测试用例，而且还可以通过先前失败的测试用例的一部分。

实验与评估

论文评估了Defects4J上的AVATAR，该软件广泛用于针对Java程序的最新APR系统。下表总结了Defects4J版本1.2.0中可用的bug和测试用例的统计信息。

“Bugs”，“kLoC”和“Tests”分别表示错误的数量，以kLoC为单位的程序大小（即数千行代码）以及每个主题的测试用例数量。

下表提供了可以通过静态分析工具检测到并已由AVATAR成功修复的Defects4J错误的详细信息。在Defects4J版本1.2.0上，SpotBugs，Facebook Infer和Google ErrorProne分别可以检测到14、4和7个错误中，AVATAR可以成功生成3、2和1个错误的正确补丁：

安全学术圈招募队友-ing, 有兴趣加入学术圈的请联系secdr#qq.com

本文始发于微信公众号（安全学术圈）：AVATAR：通过修复静态分析冲突的模式来修复语义错误